Average order of an arithmetic function: Difference between revisions

Revision as of 05:14, 1 April 2023

Latest revision as of 08:09, 25 August 2025

(10 intermediate revisions by 8 users not shown)

Line 10:

<math display="block">\lim_{N \to \infty} \frac{1}{N}\sum_{n \le N} f(n)=c</math>

exists, it is said that <math>f</math> has a '''mean value''' ('''average value''') <math>c</math>. If in addition the constant <math>c</math> is not zero, then the constant function <math>g(x)=c</math> is an average order of <math>f</math>.

==Examples==

Line 17:

* An average order of {{math|''φ''(''n'')}}, [[Euler's totient function]] of {{math|''n''}}, is {{math|6''n''{{thinsp|/}}π²}};

* An average order of {{math|''r''(''n'')}}, the number of ways of expressing {{math|''n''}} as a sum of two squares, is {{math|π}};

* TheAn average order of representations of a natural number as a sum of three squares is {{math|4π''n''{{thinsp|/}}3}};

* TheAn average number of decompositions of a natural number into a sum of one or more consecutive prime numbers is {{math|''n'' log2}};

* An average order of {{math|''ω''(''n'')}}, the [[Prime factors|number of distinct prime factors]] of {{math|''n''}}, is {{math|loglog ''n''}};

* An average order of {{math|Ω(''n'')}}, the [[Prime factors|number of prime factors]] of {{math|''n''}}, is {{math|loglog ''n''}};

* The [[prime number theorem]] is equivalent to the statement that the [[von Mangoldt function]] {{math|Λ(''n'')}} has average ordervalue 1;

* AnThe average value of {{math|''μ''(''n'')}}, the [[Möbius function]], is zero; this is again equivalent to the [[prime number theorem]].

==Calculating mean values using Dirichlet series==

Line 32:

= x\sum_{d \le x} \frac{f(d)}{d} \text{ } + O{\left(\sum_{d \le x} |f(d)|\right)}. </math>|{{EquationRef|1}}}}

GeneralizationsGeneralized identities of the previous identityform are found [[Divisor_sum_identities#Average_order_sum_identities|here]]. This identity often provides a practical way to calculate the mean value in terms of the [[Riemann zeta function]]. This is illustrated in the following example.

===The density of the ''k''^th-th power -free integers in {{mathmathbb|N}}===

For an integer <math>k \geq 1</math> the set <math>Q_k</math> of '''''k''-^th-power-free''' integers is

<math display="block">Q_k :=\{n \in \mathbb{Z}\mid n \text{ is not divisible by } d^k \text{ for any integer } d\ge 2\}.</math>

We calculate the [[natural density]] of these numbers in {{mathmathbb|'''N'''}}, that is, the average value of [[indicator function|<math>1_{Q_k}</math>]], denoted by <math>\delta(n)</math>, in terms of the [[zeta function]].

The function <math>\delta</math> is multiplicative, and since it is bounded by 1, its [[Dirichlet series]] converges absolutely in the half-plane <math>\operatorname{Re}(s)>1</math>, and there has [[Euler product]]

Line 57:

By comparing the coefficients, we get

<math display="block">\delta(n)=\sum_{d\mid n}f(d)n^{-s}.</math>

Using {{EquationNote|1|(1)}}, we get

Line 73:

We say that two lattice points are visible from one another if there is no lattice point on the open line segment joining them.

Now, if {{math|1=gcd(''a'', ''b'') = ''d'' > 1}}, then writing ''a'' = ''da''², ''b'' = ''db''² one observes that the point (''a''², ''b''²) is on the line segment which joins (0, 0) to (''a'', ''b'') and hence (''a'', ''b'') is not visible from the origin. Thus (''a'', ''b'') is visible from the origin implies that (''a'', ''b'') = 1. Conversely, it is also easy to see that gcd(''a'', ''b'') = 1 implies that there is no other [[integer lattice point]] in the segment joining (0, 0) to (''a'', ''b'').

Thus, (''a'', ''b'') is visible from (0, 0) if and only if gcd(''a'', ''b'') = 1.

Notice that <math>\frac{\varphi(n)}{n}</math> is the probability of a random point on the square <math>\{(r,s)\in \mathbb{N} : \max(|r|,|s|)=n\}</math> to be visible from the origin.

Line 81:

<math display="block">\lim_{N\to\infty} \frac{1}{N}\sum_{n\le N} \frac{\varphi(n)}{n} = \frac{6}{\pi^2}=\frac{1}{\zeta(2)}. </math>

<math display="inline">\frac{1}{\zeta(2)}</math> is also the natural density of the square-free numbers in {{mathmathbb|'''N'''}}. In fact, this is not a coincidence. Consider the ''k''-dimensional lattice, <math>\mathbb{Z}^{k}</math>. The natural density of the points which are visible from the origin is <math display="inline">\frac{1}{\zeta(k)}</math>, which is also the natural density of the ''k''-th free integers in {{mathmathbb|'''N'''}}.

===Divisor functions===

Line 91:

\sum_{n\le x}\sigma_{\alpha}(n)=

\begin{cases}

\;\;\sum_{n\le x}\sigma_\alpha(n)=\frac{\zeta(\alpha+1)}{\alpha+1}x^{\alpha+1}+O(x^\beta) & \text{if } \alpha>0,\alpha \ne 1, \\

\;\;\sum_{n\le x}\sigma_{1}(n)=\frac{\zeta(2)}{2}x^2+O(x \log x) & \text{if } \alpha=1, \\

\;\;\sum_{n\le x}\sigma_{-1}(n)=\zeta(2)x+O(\log x) & \text{if } \alpha=-1, \\

\;\;\sum_{n\le x}\sigma_\alpha(n)=\zeta(-\alpha+1)x+O(x^{\max(0,1+\alpha)}) & \text{otherwise.}

Line 220 ⟶ 221:

where <math>u=q^{-s}</math>.

Expanding the right-hand side into [[power series]] we get,

<math display="block">D(n)=(n+1)q^n.</math>