Porter-Konstante
# Porter-Konstante

Die Porter-Konstante beschreibt die durchschnittliche Anzahl von Rechenschritten, die zur Lösung des euklidischen Algorithmus benötigt wird. Sie ist nach dem englischen Mathematiker John William Porter benannt.

## Definition

Allgemein wird mithilfe des euklidischen Algorithmus der größte gemeinsame Teiler $\operatorname {ggT} (n,m)$ von zwei positiven natürlichen Zahlen $n$ und $m$ bestimmt. Die Anzahl der Schritte des Algorithmus sei $T(n,m)$, die mittlere Anzahl der Schritte bei festem n ist:

    $T(n)={\frac {1}{n}}\sum _{0\leq m<n}T(n,m)$.

Da das die Analyse vereinfacht, wird stattdessen das Mittel über teilerfremde (n,m) betrachtet:

    $\tau _{n}={\frac {1}{\phi (n)}}\sum _{0\leq m<n,ggT(m,n)=1}T(n,m)$

wobei $\phi (n)$ die Eulersche Phi-Funktion ist und

    $T(n)={\frac {1}{n}}\sum _{d|n}\phi (d)\tau _{d}$

Porter zeigte 1975:

    $\tau _{n}={\frac {12\ln 2}{\pi ^{2}}}\ln n+C+O(n^{-{\frac {1}{6}}+\epsilon })$

Dabei stellt $O$ ein Landau-Symbold dar und $\epsilon >0$ ist beliebig.

C ist die Porter-Konstante:

    $C={{6\ln 2} \over {\pi ^{2}}}\left[3\ln 2+4\gamma -{{24} \over {\pi ^{2}}}\zeta '(2)-2\right]-{{1} \over {2}}=1.4670780794\ldots$

Dabei steht:

* $\gamma$ für die Euler-Mascheroni-Konstante.
* $\zeta (s)$ für die riemannische Zeta-Funktion und $\zeta ^{\prime }(2)$ für den Wert von deren Ableitung an der Stelle 2.

Der Vorfaktor des führenden logarithmischen Terms wurde schon zuvor von Hans Arnold Heilbronn (er fand einen Fehlerterm $O(\ln \ln \,n)^{4}$, der von T. Tonkov auf $O(\ln \ln \,n^{2})$ verbessert wurde) und unabhängig von John D. Dixon erhalten.

Betrachtet man das Mittel über $m,n<N$:

    $A(N)={1 \over {N^{2}}}\sum _{\begin{matrix}1\leq m<N\\1\leq n<N\end{matrix}}T(n,m)$,

bewies Norton 1990:

    $A(N)={\frac {12\ln 2}{\pi ^{2}}}\left(\ln N-{\frac {1}{2}}+{\frac {\zeta ^{\prime }(2)}{\zeta (2)}}\right)+C-{\frac {1}{2}}+O(N^{-{1 \over 6}+\epsilon })$

mit beliebigem $\epsilon >0$.

