In number theory , the average order of magnitude of a number theoretic function denotes a simpler function that “on average” takes on the same values.
definition
Let it be a number theoretic function. It is said that the average magnitude of is when for the asymptotic equality
f
{\ displaystyle f}
f
{\ displaystyle f}
G
{\ displaystyle g}
n
→
∞
{\ displaystyle n \ to \ infty}
∑
x
≤
n
f
(
x
)
∼
∑
x
≤
n
G
(
x
)
{\ displaystyle \ sum _ {x \ leq n} f (x) \ sim \ sum _ {x \ leq n} g (x)}
applies. It is common practice to choose an approximation function that is continuous and monotonic . But even with this it is by no means clearly determined.
Examples
Values and average order of magnitude of r
2 (n)
Values and average order of magnitude of r
4 (n)
Values and average order of magnitude of r
8 (n)
Values and average order of magnitude of σ
1
Values and average order of magnitude of ω and Ω
The average order of magnitude of the sum of squares function is determined from the sum
r
k
(
n
)
{\ displaystyle r_ {k} (n)}
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}
.
This is clearly the number of (integer) grid points in a -dimensional sphere with the radius and therefore approximately equal to the sphere volume. More precisely, it can be derived recursively (using Landau's O notation )
k
{\ displaystyle k}
x
{\ displaystyle {\ sqrt {x}}}
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}})}
,
where the constants are the volumes of the -dimensional unit spheres:
V
k
{\ displaystyle V_ {k}}
k
{\ displaystyle k}
V
1
=
2
,
V
2
=
π
,
V
3
=
4th
3
π
,
V
4th
=
1
2
π
2
,
...
{\ displaystyle V_ {1} = 2, \; V_ {2} = \ pi, \; V_ {3} = {\ frac {4} {3}} \ pi, \; V_ {4} = {\ frac {1} {2}} \ pi ^ {2}, \; \ dotsc}
The average order of magnitude of is thus , e.g. B. .
r
k
{\ displaystyle r_ {k}}
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}}
r
2
(
n
)
∼
π
{\ displaystyle r_ {2} (n) \ sim \ pi}
Further examples
The average magnitude of the Euler's phi function is .
φ
(
n
)
{\ displaystyle \ varphi (n)}
6th
π
2
n
{\ displaystyle {\ tfrac {6} {\ pi ^ {2}}} n}
The average order of magnitude of the divisor number function is . More precisely applies with Euler's constant
d
(
n
)
: =
σ
0
(
n
)
{\ displaystyle d (n): = \ sigma _ {0} (n)}
ln
n
{\ displaystyle \ ln n}
γ
{\ 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}})}
.
The average order of magnitude of the divisor function for is with the Riemann zeta function .
σ
k
(
n
)
{\ displaystyle \ sigma _ {k} (n)}
k
>
0
{\ displaystyle k> 0}
ζ
(
k
+
1
)
n
k
{\ displaystyle \ zeta (k + 1) \ n ^ {k}}
ζ
(
s
)
{\ displaystyle \ zeta (s)}
The average size of the order , so the number of (not necessarily distinct) prime factors of such also is the number of distinct prime factors . More precisely ( theorem of Hardy and Ramanujan )
Ω
(
n
)
{\ displaystyle \ Omega (n)}
n
{\ displaystyle n}
ω
(
n
)
{\ displaystyle \ omega (n)}
ln
ln
n
{\ displaystyle \ ln \ ln n}
∑
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)}
with the constants ( Mertens constant ) and
B.
1
=
0.261
49
...
{\ displaystyle B_ {1} = 0 {,} 26149 \ dots}
B.
2
=
1.034
65
...
{\ displaystyle B_ {2} = 1 {,} 03465 \ dots}
In addition, the average and normal magnitudes are the same for both functions .
See also
Web links
Eric W. Weisstein : Mertens Constant . In: MathWorld (English).
Individual evidence
↑ E. Krätzel: Number theory . VEB Deutscher Verlag der Wissenschaften, Berlin 1981, p. 132 .
↑ GH Hardy , EM Wright: Introduction to Number Theory . R. Oldenbourg, Munich 1958, p. 300 .
↑ E. Krätzel: Number theory . VEB Deutscher Verlag der Wissenschaften, Berlin 1981, p. 197 .
<img src="https://de.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">