In der Zahlentheorie bezeichnet die durchschnittliche Größenordnung einer zahlentheoretischen Funktion eine einfachere Funktion, die „im Mittel“ dieselben Werte annimmt.[1] [2]
Werte und durchschnittliche Größenordnung von r2 (n)
Werte und durchschnittliche Größenordnung von r4 (n)
Werte und durchschnittliche Größenordnung von r8 (n)
Werte und durchschnittliche Größenordnung von σ 1
Werte und durchschnittliche Größenordnung von ω und Ω
Die durchschnittliche Größenordnung der Quadratsummen-Funktion
r
k
(
n
)
{\displaystyle r_{k}(n)}
bestimmt man aus der Summe[3]
R
k
(
x
)
:=
∑
n
=
0
x
r
k
(
n
)
=
∑
a
1
2
+
a
2
2
+
⋯
+
a
k
2
≤
x
1
{\displaystyle R_{k}(x):=\sum _{n=0}^{x}r_{k}(n)=\sum _{a_{1}^{2}+a_{2}^{2}+\dotsb +a_{k}^{2}\leq x}1}
.
Das ist anschaulich die Anzahl der (ganzzahligen) Gitterpunkte in einer
k
{\displaystyle k}
-dimensionalen Kugel mit dem Radius
x
{\displaystyle {\sqrt {x}}}
und darum näherungsweise gleich dem Kugelvolumen. Genauer lässt sich (mit der Landau’schen O-Notation ) rekursiv ableiten
R
k
(
x
)
=
V
k
x
k
2
+
O
(
x
k
−
1
2
)
{\displaystyle R_{k}(x)=V_{k}x^{\frac {k}{2}}+O(x^{\frac {k-1}{2}})}
,
wobei die Konstanten
V
k
{\displaystyle V_{k}}
die Volumina der
k
{\displaystyle k}
-dimensionalen Einheitskugeln sind:
V
1
=
2
,
V
2
=
π
,
V
3
=
4
3
π
,
V
4
=
1
2
π
2
,
…
{\displaystyle V_{1}=2,\;V_{2}=\pi ,\;V_{3}={\frac {4}{3}}\pi ,\;V_{4}={\frac {1}{2}}\pi ^{2},\;\dotsc }
Die durchschnittliche Größenordnung von
r
k
{\displaystyle r_{k}}
ist damit
r
k
(
n
)
∼
k
2
V
k
n
k
2
−
1
{\displaystyle r_{k}(n)\sim {\tfrac {k}{2}}V_{k}n^{{\tfrac {k}{2}}-1}}
, also z. B.
r
2
(
n
)
∼
π
{\displaystyle r_{2}(n)\sim \pi }
.
Weitere Beispiele
Die durchschnittliche Größenordnung der Eulerschen Phi-Funktion
φ
(
n
)
{\displaystyle \varphi (n)}
ist
6
π
2
n
{\displaystyle {\tfrac {6}{\pi ^{2}}}n}
.
Die durchschnittliche Größenordnung der Teileranzahlfunktion
d
(
n
)
:=
σ
0
(
n
)
{\displaystyle d(n):=\sigma _{0}(n)}
ist
ln
n
{\displaystyle \ln n}
. Genauer gilt mit der Eulerschen Konstanten
γ
{\displaystyle \gamma }
∑
x
≤
n
d
(
x
)
=
n
ln
n
+
(
2
γ
−
1
)
n
+
O
(
n
)
{\displaystyle \sum _{x\leq n}d(x)=n\ln n+(2\gamma -1)n+O({\sqrt {n}})}
.
Die durchschnittliche Größenordnung der Teilerfunktion
σ
k
(
n
)
{\displaystyle \sigma _{k}(n)}
für
k
>
0
{\displaystyle k>0}
ist
ζ
(
k
+
1
)
n
k
{\displaystyle \zeta (k+1)\ n^{k}}
mit der Riemannschen Zetafunktion
ζ
(
s
)
{\displaystyle \zeta (s)}
.
Die durchschnittliche Größenordnung der Ordnung
Ω
(
n
)
{\displaystyle \Omega (n)}
, also der Anzahl der (nicht notwendigerweise verschiedenen) Primfaktoren von
n
{\displaystyle n}
wie auch von
ω
(
n
)
{\displaystyle \omega (n)}
als Anzahl der verschiedenen Primfaktoren ist
ln
ln
n
{\displaystyle \ln \ln n}
. Genauer gilt (Satz von Hardy und Ramanujan )
∑
x
≤
n
ω
(
x
)
=
n
ln
ln
n
+
B
1
n
+
o
(
n
)
{\displaystyle \sum _{x\leq n}\omega (x)=n\ln \ln n+B_{1}n+o(n)}
∑
x
≤
n
Ω
(
x
)
=
n
ln
ln
n
+
B
2
n
+
o
(
n
)
{\displaystyle \sum _{x\leq n}\Omega (x)=n\ln \ln n+B_{2}n+o(n)}
mit den Konstanten
B
1
=
0,261
49
…
{\displaystyle B_{1}=0{,}26149\dots }
(Mertens-Konstante ) und
B
2
=
1,034
65
…
{\displaystyle B_{2}=1{,}03465\dots }
Für beide Funktionen sind außerdem durchschnittliche und normale Größenordnung gleich.
Der Primzahlsatz ist äquivalent zur Feststellung, dass die durchschnittliche Größenordnung der Mangoldtfunktion
Λ
(
n
)
{\displaystyle \Lambda (n)}
gleich
1
{\displaystyle 1}
ist.
E. Krätzel : Zahlentheorie . VEB Deutscher Verlag der Wissenschaften, Berlin 1981, S. 132 .
G. H. Hardy , E. M. Wright : Einführung in die Zahlentheorie . R. Oldenbourg, München 1958, S. 300 . E. Krätzel : Zahlentheorie . VEB Deutscher Verlag der Wissenschaften, Berlin 1981, S. 197 .