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,\mathrm {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={\frac {6\ln 2}{\pi ^{2}}}\left[3\ln 2+4\gamma -{\frac {24}{\pi ^{2}}}\zeta '(2)-2\right]-{\frac {1}{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)={\frac {1}{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^{-{\frac {1}{6}}+\epsilon })$
mit beliebigem $\epsilon >0$.