Average order of an arithmetic function explained

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$$\backslash sum\_\; f(n)\; \backslash sim\; \backslash sum\_\; g(n)$$as x tends to infinity.

It is conventional to choose an approximating function

g that is continuous and monotone. But even so an average order is of course not unique.

In cases where the limit$$\backslash lim\_\; \backslash frac\backslash sum\_\; f(n)=c$$

exists, it is said that

f has a mean value (average value) c . If in addition the constant c is not zero, then the constant function g(x) = c is an average order of f .

Examples

• An average order of, the number of divisors of, is ;
• An average order of, the sum of divisors of, is ;
• An average order of, Euler's totient function of, is ;
• An average order of, the number of ways of expressing as a sum of two squares, is ;
• The average order of representations of a natural number as a sum of three squares is ;
• The average number of decompositions of a natural number into a sum of one or more consecutive prime numbers is ;
• An average order of, the number of distinct prime factors of, is ;
• An average order of, the number of prime factors of, is ;
• The prime number theorem is equivalent to the statement that the von Mangoldt function has average order 1;
• An average value of, the Möbius function, is zero; this is again equivalent to the prime number theorem.

Calculating mean values using Dirichlet series

In case

F is of the form$$F(n)=\backslash sum\_\; f(d),$$for some arithmetic function f(n) , one has,

Generalized identities of the previous form are found 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-power-free integers in

For an integer

k \geq 1 the set Q _{k} of k^th-power-free integers is$$Q\_k\; :=\backslash .$$

We calculate the natural density of these numbers in, that is, the average value of

1 _{Q _{k}} , denoted by

\delta(n) , in terms of the zeta function.

The function

\delta is multiplicative, and since it is bounded by 1, its Dirichlet series converges absolutely in the half-plane \operatorname{Re}(s)> 1 , and there has Euler product$$\backslash sum\_n^\; =\; \backslash sum\_n\; \backslash delta(n)n^=\; \backslash prod\_p\; \backslash left(1+p^+\backslash cdots\; +p^\backslash right)=\; \backslash prod\_p\; \backslash left(\backslash frac\backslash right)\; =\; \backslash frac.$$

By the Möbius inversion formula, we get$$\backslash frac\; =\; \backslash sum\_\backslash mu(n)n^,$$where

\mu stands for the Möbius function. Equivalently,$$\backslash frac=\backslash sum\_f(n)n^,$$where f(n) = \begin{cases} \mu(d) & n = d ^{k} \\ 0 & otherwise , \end{cases} and hence,$$\backslash frac\; =\; \backslash sum\_n\; \backslash left(\backslash sum\_f(d)\backslash right)n^.$$

By comparing the coefficients, we get$$\backslash delta(n)=\backslash sum\_f(d).$$

Using, we get$$\backslash sum\_\backslash delta(d)=x\backslash sum\_(f(d)/d)+O(x^).$$

We conclude that,$$\backslash sum\_\; 1\; =\; \backslash frac+O(x^),$$where for this we used the relation$$\backslash sum\_n\; (f(n)/n)=\backslash sum\_n\; f(n^k)n^=\backslash sum\_n\; \backslash mu(n)n^=\backslash frac,$$which follows from the Möbius inversion formula.

In particular, the density of the square-free integers is $\backslash zeta(2)^=\backslash frac$.

Visibility of lattice points

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, 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

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

Thus, one can show that the natural density of the points which are visible from the origin is given by the average,$$\backslash lim\_\; \backslash frac\backslash sum\_\; \backslash frac\; =\; \backslash frac=\backslash frac.$$

$\backslash frac$ is also the natural density of the square-free numbers in . In fact, this is not a coincidence. Consider the k-dimensional lattice,

Z ^{k} . The natural density of the points which are visible from the origin is $\backslash frac$, which is also the natural density of the k-th free integers in .

Divisor functions

Consider the generalization of

d(n) :$$\backslash sigma\_\backslash alpha(n)=\backslash sum\_d^\backslash alpha.$$

The following are true:where

\beta =max ( 1 ,\alpha) .

Better average order

This notion is best discussed through an example. From$$\backslash sum\_d(n)=x\backslash log\; x+(2\backslash gamma-1)x+o(x)$$(

\gamma is the Euler–Mascheroni constant) and$$\backslash sum\_\backslash log\; n=x\backslash log\; x-x+O(\backslash log\; x),$$we have the asymptotic relation$$\backslash sum\_(d(n)-(\backslash log\; n+2\backslash gamma))=o(x)\backslash quad(x\backslash to\backslash infty),$$which suggests that the function log n +2 \gamma is a better choice of average order for d(n) than simply log n .

Mean values over

Definition

Let h(x) be a function on the set of monic polynomials over F_q. For

n\ge 1 we define$$\backslash text\_n(h)=\backslash frac\backslash sum\_h(f).$$

This is the mean value (average value) of h on the set of monic polynomials of degree n. We say that g(n) is an average order of h if$$\backslash text\_n(h)\; \backslash sim\; g(n)$$as n tends to infinity.

In cases where the limit,$$\backslash lim\_\backslash text\_n(h)\; =\; c$$exists, it is said that h has a mean value (average value) c.

Zeta function and Dirichlet series in

Let be the ring of polynomials over the finite field .

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$$D\_(s)=\backslash sum\_\; h(f)|f|^,$$where for

g\in A , set |g| = q ^{\deg(g)} if g\ne 0 , and |g| =0 otherwise.

The polynomial zeta function is then$$\backslash zeta\_(s)=\backslash sum\_\; |f|^.$$

Similar to the situation in, every Dirichlet series of a multiplicative function h has a product representation (Euler product):$$D\_(s)\; =\; \backslash prod\_\; \backslash left(\backslash sum\_^\; h(P^)\; \backslash left|P\backslash right|^\backslash right),$$where the product runs over all monic irreducible polynomials P.

For example, the product representation of the zeta function is as for the integers: $\backslash zeta\_(s)\; =\; \backslash prod\_\; \backslash left(1\; -\; \backslash left|P\backslash right|^\backslash right)^$.

Unlike the classical zeta function,

\zeta _{A} (s) is a simple rational function:$$\backslash zeta\_(s)=\backslash sum\_(|f|^)=\backslash sum\_\; \backslash sum\_\; q^\; =\; \backslash sum\_(q^)\; =\; (1-q^)^.$$

In a similar way, If f and g are two polynomial arithmetic functions, one defines f * g, the Dirichlet convolution of f and g, bywhere 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

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.

Examples

The density of the k-th power free polynomials in

Define

\delta(f) to be 1 if f is k-th power free and 0 otherwise.

We calculate the average value of

\delta , which is the density of the k-th power free polynomials in, in the same fashion as in the integers.

By multiplicativity of

\delta :$$\backslash sum\_f\; \backslash frac$$

^s

= \prod_ \left(\sum_^(|P|^)\right) = \prod_\frac = \frac = \frac = \frac

Denote

b _{n} the number of k-th power monic polynomials of degree n, we get$$\backslash sum\_\backslash frac$$

^

=\sum_\sum_\delta(f)|f|^=\sum_b_q^.

Making the substitution

u = q ^{-s} we get:$$\backslash frac=\backslash sum\_^\backslash infty\; b\_u^.$$

Finally, expand the left-hand side in a geometric series and compare the coefficients on

u ^{n} on both sides, to conclude that

Hence,$$\backslash text\_(\backslash delta)\; =\; 1-q^\; =\; \backslash frac$$

And since it doesn't depend on n this is also the mean value of

\delta(f) .

Polynomial Divisor functions

In, we define$$\backslash sigma\; \_(m)=\backslash sum\_|f|^k.$$

We will compute

Ave _{n} (\sigma _{k} ) for k\ge 1 .

First, notice that$$\backslash sigma\_(m)=h*\backslash mathbb(m)$$where

h(f) = |f| ^{k} and I (f) =1 \forall{f} .

Therefore,$$\backslash sum\_\backslash sigma\_(m)|m|^=\backslash zeta\_(s)\backslash sum\_h(m)|m|^.$$

Substitute

q ^{-s} = u we get,$$\backslash text=\backslash sum\_n\backslash left(\backslash sum\_\; \backslash sigma\_k(m)\backslash right)u^n,$$and by Cauchy product we get,

Finally we get that,$$\backslash text\_n\backslash sigma\_k=\backslash frac.$$

Notice that$$q^n\; \backslash text\_n\backslash sigma\_\; =\; q^\backslash left(\backslash frac\backslash right)\; =\; q^\backslash left(\backslash frac\backslash right)$$

Thus, if we set

x = q ^{n} then the above result reads$$\backslash sum\_\; \backslash sigma\_k(m)\; =\; x^\backslash left(\backslash frac\backslash right)$$which resembles the analogous result for the integers:$$\backslash sum\_\backslash sigma\_(n)=\backslash fracx^+O(x^)$$

Number of divisors

Let

d(f) be the number of monic divisors of f and let D(n) be the sum of d(f) over all monics of degree n.$$\backslash zeta\_A(s)^2=\; \backslash left(\backslash sum\_|h|^\backslash right)\backslash left(\backslash sum\_g|g|^\backslash right)=\; \backslash sum\_f\backslash left(\backslash sum\_\; 1\; \backslash right)|f|^=\; \backslash sum\_f\; d(f)|f|^=D\_d(s)=\; \backslash sum\_^\backslash infty\; D(n)u^$$where u = q ^{-s} .

Expanding the right-hand side into power series we get,$$D(n)=(n+1)q^n.$$

Substitute

x = q ^{n} the above equation becomes:$$D(n)=x\; \backslash log\_q(x)+x$$ which resembles closely the analogous result for integers $\backslash sum\_^n\; d(k)\; =\; x\backslash log\; x+(2\backslash gamma-1)\; x\; +\; O(\backslash sqrt)$, where \gamma is Euler constant.

Not much is known about the error term for the integers, while in the polynomials case, there is no error term. This is because of the very simple nature of the zeta function

\zeta _{A} (s) , and that it has no zeros.

Polynomial von Mangoldt function

The Polynomial von Mangoldt function is defined by:where the logarithm is taken on the basis of q.

Proposition. The mean value of

Λ _{A} is exactly 1.

Proof.Let m be a monic polynomial, and let $m\; =\; \backslash prod\_^\; P\_^$ be the prime decomposition of m.

We have,

Hence,$$\backslash mathbb\backslash cdot\backslash Lambda\_A(m)=\backslash log|m|$$and we get that,$$\backslash zeta\_(s)D\_(s)\; =\; \backslash sum\_\backslash log\backslash left|m\backslash right|\backslash left|m\backslash right|^.$$

Now,$$\backslash sum\_m\; |m|^s\; =\; \backslash sum\_n\; \backslash sum\_\; u^n=\backslash sum\_n\; q^n\; u^=\backslash sum\_n\; q^.$$

Thus,$$\backslash frac\backslash sum\_m\; |m|^s\; =\; -\backslash sum\_n\; \backslash log(q^n)q^\; =-\backslash sum\_n\; \backslash sum\_\; \backslash log(q^n)q^=\; -\backslash sum\_f\; \backslash log\backslash left|f\backslash right|\backslash left|f\backslash right|^.$$

We got that:$$D\_(s)\; =\; \backslash frac$$

Now,

Hence,$$\backslash sum\_\backslash Lambda\_A\; (m)=q^n\; \backslash log(q),$$and by dividing by

q ^{n} we get that,$$\backslash text\_n\; \backslash Lambda\_A(m)=\backslash log(q)=1.$$

Polynomial Euler totient function

Define Euler totient function polynomial analogue,

\Phi , to be the number of elements in the group (A/fA) ^{*} . We have,$$\backslash sum\_\backslash Phi(f)=q^(1-q^).$$

See also

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

References

• pp. 347–360
• Book: Introduction to Analytic and Probabilistic Number Theory . Gérald Tenenbaum . Cambridge studies in advanced mathematics . 46 . . 1995 . 0-521-41261-7 . 0831.11001 . 36–55 .