Average order of an arithmetic function

In number theory, an average order of an arithmetic function is some simpler or better-understood function which takes the same values "on average".

Let f be an arithmetic function. We say that an average order of f is g if

${\displaystyle \sum _{n\leq x}f(n)\sim \sum _{n\leq x}g(n)}$

as x tends to infinity.

It is conventional to choose an approximating function g that is continuous and monotone. But even thus an average order is of course not unique.

Examples

• An average order of d(n), the number of divisors of n, is log(n);
• An average order of σ(n), the sum of divisors of n, is nπ² / 6;
• An average order of φ(n), Euler's totient function of n, is 6n / π²;
• An average order of r(n), the number of ways of expressing n as a sum of two squares, is π;
• An average order of ω(n), the number of distinct prime factors of n, is log log n;
• An average order of Ω(n), the number of prime factors of n, is log log n;
• The prime number theorem is equivalent to the statement that the von Mangoldt function Λ(n) has average order 1;
• An average order of μ(n), the Möbius function, is zero; this is again equivalent to the prime number theorem.

Better average order

This notion is best discussed through an example. From

${\displaystyle \sum _{n\leq x}d(n)=x\log x+(2\gamma -1)x+o(x)}$ 

(${\displaystyle \gamma }$  is the Euler-Mascheroni constant) and

${\displaystyle \sum _{n\leq x}\log n=x\log x-x+O(\log x),}$ 

we have the asymptotic relation

${\displaystyle \sum _{n\leq x}(d(n)-(\log n+2\gamma ))=o(x)\quad (x\rightarrow \infty ),}$ 

which suggests that the function ${\displaystyle \log n+2\gamma }$  is a better choice of average order for ${\displaystyle d(n)}$  than simply ${\displaystyle \log n}$ .

Mean values over F_q[x]

Definition

Let h(x) be a function on the set of monic polynomials over F_q. For ${\displaystyle n\geq 1}$  we define

${\displaystyle {\text{Ave}}_{n}(h)={\frac {1}{q^{n}}}\sum _{f{\text{ monic}},{\text{ deg}}(f)=n}h(f)}$ .

This is the mean value of h on the set of monic polynomials of degree n. We define the mean value of h to be

${\displaystyle \lim _{n\rightarrow \infty }{\text{Ave}}_{n}(h)}$  provided this limit exists.

Zeta function and Dirichlet series in F_q[X]

Let F_q[X]=A be the ring of polynomials over the finite field F_q.

Let h be a polynomial arithmetic function (i.e. a function on set of monic polynomials over A). Its corresponding Dirichlet series define to be

${\displaystyle D_{h}(s)=\sum _{f{\text{ monic}}}h(f)|f|^{-s}}$ ,

where for ${\displaystyle g\in A}$ , set ${\displaystyle |g|=q^{deg(g)}}$  if ${\displaystyle g\neq 0}$ , and ${\displaystyle |g|=0}$  otherwise.

The polynomial zeta function is then

${\displaystyle \zeta _{A}(s)=\sum _{f{\text{ monic}}}|f|^{-s}}$ .

Similar to the situation in N, every Dirichlet series of a multiplicative function h has a product representation (Euler product):

${\displaystyle D_{h}(s)=\prod _{P}(\sum _{n\mathop {=} 0}^{\infty }h(P^{n})|P|^{-sn})}$ ,

Where the product runs over all monic irreducible polynomials P.

For example, the product representation of zeta function still holds: ${\displaystyle \zeta _{A}(s)=\prod _{P}(1-|P|^{-s})^{-1}}$ .

Unlike the classical zeta function, ${\displaystyle \zeta _{A}(s)}$  is very simple:

${\displaystyle \zeta _{A}(s)=\sum _{f}(|f|^{-s})=\sum _{n}\sum _{\text{deg(f)=n}}q^{-sn}=\sum _{n}(q^{n-sn})=(1-q^{1-s})^{-1}}$ .

In a similar way, If ƒ and g are two polynomial arithmetic functions, one defines ƒ * g, the Dirichlet convolution of ƒ and g, by

${\displaystyle {\begin{aligned}(f*g)(m)&=\sum _{d\,\mid \,m}f(m)g\left({\frac {m}{d}}\right)\\&=\sum _{ab\,=\,f}f(a)g(b)\end{aligned}}}$ 

where the sum extends over all monic divisors d of m, or equivalently over all pairs (a, b) of monic polynomials whose product is m. The identity ${\displaystyle D_{h}D_{g}=D_{h*g}}$  still holds. Thus, like in the elementary theory, the polynomial Dirichlet series and the zeta function has a connection with the notion of mean values in the context of polynomials. The following examples illustrate it.

The density of the k-th power free polynomials in F_q[X]

Define ${\displaystyle \delta (f)}$  to be 1 if ${\displaystyle f}$  is k-th power free and 0 otherwise.

We calculate the average value of δ, which is the density of the k-th power free polynomials in F_q[X].

By multiplicativity of ${\displaystyle \delta }$ :

${\displaystyle \sum _{f}{\frac {\delta (f)}{|f|^{s}}}=\prod _{P}(\sum _{j\mathop {=} 0}^{k-1}(|P|^{-js}))=\prod _{P}{\frac {1-|P|^{-sk}}{1-|P|^{-s}}}={\frac {\zeta _{A}(s)}{\zeta _{A}(sk)}}={\frac {1-q^{1-ks}}{1-q^{1-s}}}}$ 

Denote ${\displaystyle b_{n}}$  the number of k-th power monic polynomials of degree n, we get

${\displaystyle \sum _{f}{\frac {\delta (f)}{|f|^{s}}}=\sum _{n}\sum _{{\text{def}}f=n}\delta (f)|f|^{-s}=\sum _{n}b_{n}q^{-sn}}$ .

Making substitution ${\displaystyle u=q^{-s}}$  we get:

${\displaystyle {\frac {1-qu^{k}}{1-qu}}=\sum _{n\mathop {=} 0}^{\infty }b_{n}u^{n}}$ .

Finally, expand the left-hand side in a geometric series and compare the coefficients on ${\displaystyle u^{n}}$  on both sides, we get that

${\displaystyle b_{n}={\begin{cases}\;\;\,q^{n}&n\leq k-1\\\;\;\,q^{n}(1-q^{1-k})&{\text{otherwise}}\\\end{cases}}}$ 

Hence,

${\displaystyle {\text{Ave}}_{n}(\delta )=1-q^{1-k}={\frac {1}{\zeta _{A}(k)}}}$ 

And since it doesn't depend on n this is also the mean value of ${\displaystyle \delta (f)}$ .

Number of divisors

Let ${\displaystyle d(f)}$  be the number of monic divisors of f and let ${\displaystyle D(n)}$  be the sum of ${\displaystyle d(f)}$  over all monics of degree n.

${\displaystyle \zeta _{A}(s)^{2}=(\sum _{h}|h|^{-s})(\sum _{g}|g|^{-s})=\sum _{f}(\sum _{hg=f}1)|f|^{-s}=\sum _{d(f)}|f|^{-s}=D_{d}(s)=\sum _{n\mathop {=} 0}^{\infty }D(n)u^{n}}$ 

where ${\displaystyle u=q^{-s}}$ .

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

${\displaystyle D(n)=(n+1)q^{n}}$ .

Substitute ${\displaystyle x=q^{n}}$  the above equation becomes:

${\displaystyle D(n)=xlog_{q}(x)+x}$  which resembles closely the analogous result for integers ${\displaystyle \sum _{k\mathop {=} 1}^{n}d(k)=xlogx+(2\gamma -1)x+O({\sqrt {x}})}$ , where ${\displaystyle \gamma }$  is Euler constant. It is a famous problem in elementary number theory to find the error term. In the polynomials case, there is no error term. This is because of the very simple nature of the zeta function ${\displaystyle \zeta _{A}(s)}$ .

See also

• Divisor summatory function
• Normal order of an arithmetic function
• Extremal orders of an arithmetic function

References

• Hardy, G. H.; Wright, E. M. (2008) [1938]. An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921986-5. MR 2445243. Zbl 1159.11001. Pp.347–360
• Gérald Tenenbaum (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics. Vol. 46. Cambridge University Press. pp. 36–55. ISBN 0-521-41261-7. Zbl 0831.11001.