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

\sum_{n \le x} f(n) \sim \sum_{n \le x} 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

\lim_{N\rightarrow \infty}\frac{1}{N}\sum_{n \le N} f(n)=c

exists, it is said that f has a mean value (average value) c.

Examples

Calculating mean values using Dirichlet series

In case F is of the form

F(n)=\sum_{d \mid n} f(d),

for some arithmetic function f(n), one has,

\sum_{n \le x} F(n)=\sum_{d \le x} f(d) \sum_{n\le x, d\mid n} 1=\sum_{d \le x} f(d)[x/d] = x\sum_{d \le x} \frac{f(d)}{d} \text{ } + O(\sum_{d \le x} |f(d)|).\qquad\qquad (1)

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 N

For an integer k ≥ 1 the set Qk of k-th-power-free integers is

Q_k :=\{n \in \mathbb{Z}\mid n \text{ is not divisible by } d^k \text{ for any integer } d\ge 2\}.

We calculate the natural density of these numbers in N, that is, the average value of 1Qk, denoted by δ(n), in terms of the zeta function.

The function δ is multiplicative, and since it is bounded by 1, its Dirichlet series converges absolutely in the half-plane Re(s)>1, and there has Euler product

\sum_{Q_k}n^{-s}=\sum_n \delta(n)n^{-s}=\prod_p (1+p^{-s}+\cdots +p^{-s(k-1)})=\prod_p \left(\frac{1-p^{-sk}}{1-p^{-s}}\right)=\frac{\zeta(s)}{\zeta(sk)}.

By the Möbius inversion formula, we get

\frac{1}{\zeta(ks)}=\sum_{n}\mu(n)n^{-ks},

where \mu stands for the Möbius function. Equivalently,

\frac{1}{\zeta(ks)}=\sum_{n}f(n)n^{-s},

where f(n)=\begin{cases} \;\;\, \mu(d) & n=d^{k}\\ \;\;\, 0 & \text{otherwise}, \end{cases}

and hence,

\frac{\zeta(s)}{\zeta(sk)}=\sum_n (\sum_{d\mid n}f(d))n^{-s}.

By comparing the coefficients, we get

\delta(n)=\sum_{d\mid n}f(d)n^{-s}.

Using (1), we get

\sum_{d \le x}\delta(d)=x\sum_{d \le x}(f(d)/d)+O(x^{1/k}).

We conclude that,

\sum_{n\in Q_k, n \le x}1=\frac{x}{\zeta(k)}+O(x^{1/k}),

Where for this we used the relation

\sum_n (f(n)/n)=\sum_n f(n^k)n^{-k}=\sum_n \mu(n)n^{-k}=\frac{1}{\zeta(k)},

which follows from the Möbius inversion formula.

In particular, the density of the square-free integers is \zeta(2)^{-1}=\frac{6}{\pi^{2}}.

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 gcd(a, b) = d > 1, then writing a = da2, b = db2 one observes that the point (a2, b2) 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 \frac{\varphi(n)}{n} is the probability of a random point on the square \{(r,s)\in \mathbb{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,

\lim_{N\rightarrow \infty} \frac{1}{N}\sum_{n\le N} \frac{\varphi(n)}{n} = \frac{6}{\pi^2}=\frac{1}{\zeta(2)}.

interestingly, \frac{1}{\zeta(2)} is also the natural density of the square-free numbers in N. In fact, this is not a coincidence. Consider the k-dimensional lattice, \mathbb{Z}^{k}. The natural density of the points which are visible from the origin is \frac{1}{\zeta(k)}, which is also the natural density of the k-th free integers in N.

Divisor functions

Consider the generalization of d(n):

\sigma_\alpha(n)=\sum_{d\mid n}d^\alpha.

The following are true:

\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, \\ \;\;\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.} \end{cases}

where \beta=max(1,\alpha).

Better average order

This notion is best discussed through an example. From

\sum_{n\le x}d(n)=x\log x+(2\gamma-1)x+o(x)

(\gamma is the Euler–Mascheroni constant) and

\sum_{n\le x}\log n=x\log x-x+O(\log x),

we have the asymptotic relation

\sum_{n\le x}(d(n)-(\log n+2\gamma))=o(x)\quad(x\rightarrow\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 Fq[x]

Definition

Let h(x) be a function on the set of monic polynomials over Fq. For n\ge 1 we define

\text{Ave}_n(h)=\frac{1}{q^n}\sum_{f \text{ monic},\deg(f)= n}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

\text{Ave}_n(h) \sim g(n)

as n tends to infinity.

In cases where the limit,

\lim_{n\rightarrow\infty}\text{Ave}_n(h)=c

exists, it is said that h has a mean value (average value) c.

Zeta function and Dirichlet series in Fq[X]

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

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_{h}(s)=\sum_{f\text{ monic}}h(f)|f|^{-s},

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

The polynomial zeta function is then

\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):

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 the zeta function is as for the integers: \zeta_{A}(s)=\prod_{P}(1-|P|^{-s})^{-1}.

Unlike the classical zeta function, \zeta_{A}(s) is a simple rational function:

\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

\begin{align} (f*g)(m) &= \sum_{d\,\mid \,m} f(m)g\left(\frac{m}{d}\right) \\ &= \sum_{ab\,=\,m}f(a)g(b) \end{align}

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 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 Fq[X]

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 Fq[X], in the same fashion as in the integers.

By multiplicativity of \delta:

\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}}=\frac{\zeta_A(s)}{\zeta_A(ks)}

Denote b_n the number of k-th power monic polynomials of degree n, we get

\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 the substitution u=q^{-s} we get:

\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 u^{n} on both sides, to conclude that

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

Hence,

\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 \delta(f).

Polynomial Divisor functions

In Fq[X], we define

\sigma _{k}(m)=\sum_{f|m, \text{ monic}}|f|^k.

We will compute \text{Ave}_{n}(\sigma_{k}) for k\ge 1.

First, notice that

\sigma_{k}(m)=h*\mathbb{I}(m)

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

Therefore,

\sum_{m}\sigma_{k}(m)|m|^{-s}=\zeta_{A}(s)\sum_{m}h(m)|m|^{-s}.

Substitute q^{-s}=u we get,

\text{LHS}=\sum_n(\sum_{\deg(m)=n} \sigma_k(m))u^n, and by Cauchy product we get,
\begin{align} \text{RHS} &=\sum_n q^{n(1-s)}\sum_{n}(\sum_{\deg(m)=n}h(m))u^n \\ &=\sum_n q^n u^n \sum_{l}q^l q^{lk}u^l \\ &=\sum_n (\sum_{j \mathop =0}^{n}q^{n-j}q^{jk+j}) \\ &=\sum_n (q^n(\frac{1-q^{k(n+1)}}{1-q^k})) u^n. \end{align}

Finally we get that,

\text{Ave}_n\sigma_k=\frac{1-q^{k(n+1)}}{1-q^k}.

Notice that

q^n \text{Ave}_n\sigma_{k}=q^{n(k+1)}(\frac{1-q^{-k(n+1)}}{1-q^{-k}})=q^{n(k+1)}(\frac{\zeta(k+1)}{\zeta(kn+k+1)})

Thus, if we set x=q^n then the above result reads

\sum_{\deg(m)=n, m \text{ monic}} \sigma_k(m)=x^{k+1}(\frac{\zeta(k+1)}{\zeta(kn+k+1)})

which resembles the analogous result for the integers:

\sum_{n\le x}\sigma_{k}(n)=\frac{\zeta(k+1)}{k+1}x^{k+1}+O(x^{k})

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.

\zeta_A(s)^2=(\sum_{h}|h|^{-s})(\sum_g|g|^{-s})=\sum_f(\sum_{hg=f}1)|f|^{-s}=\sum_f d(f)|f|^{-s}=D_d(s)=\sum_{n \mathop =0}^\infty D(n)u^{n}

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 \log_q(x)+x which resembles closely the analogous result for integers \sum_{k \mathop =1}^n d(k)=x\log x+(2\gamma-1) x + O(\sqrt{x}), where \gamma is Euler constant.

It is interesting to note that not a lot 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: \Lambda_{A}(f) = \begin{cases} \log |P| & \mbox{if }f=|P|^k \text{ for some prime monic} P \text{ and integer } k \ge 1, \\ 0 & \mbox{otherwise.} \end{cases}

Where the logarithm is taken on the basis of q.

Proposition. The mean value of \Lambda_{A} is exactly 1.

Proof. Let m be a monic polynomial, and let m=\prod_{i \mathop =1}^{l}P_{i}^{e_i} be the prime decomposition of m.

We have,

\begin{align} \sum_{f|m}\Lambda_{A}(f) &= \sum_{(i_1,\ldots,i_l)|0\le i_j \le e_j} \Lambda_A(\prod_{j \mathop =1}^l P_j^{i_j})=\sum_{j \mathop =1}^l \sum_{i \mathop =1}^{e_i}\Lambda_A (P_j^i) =\sum_{j \mathop =1}^l \sum_{i \mathop =1}^{e_i}\log|P_j|\\ &= \sum_{j \mathop =1}^l e_j\log|P_j| =\sum_{j \mathop =1}^l \log|P_j|^{e_j}=\log|(\prod_{i \mathop =1}^l P_i^{e_i})|\\ &= \log(m) \end{align}

Hence,

\mathbb{I}\cdot\Lambda_A(m)=\log|m|

and we get that,

\zeta_{A}(s)D_{\Lambda_{A}}(s)=\sum_{m}log|m||m|^{-s}.

Now,

\sum_m |m|^s = \sum_n \sum_{\deg m=n} u^n=\sum_n q^n u^{n}=\sum_n q^{n(1-s)}.

Thus,

\frac{d}{ds}\sum_m |m|^s=-\sum_n \log(q^n)q^{n(1-s)}=-\sum_n \sum_{\deg(f)=n} \log(q^n)q^{-ns}=-\sum_f \log|f||f|^{-s}.

We got that:

D_{\Lambda_A}(s)=\frac{-\zeta'_A(s)}{\zeta_{A}(s)}

Now,

\sum_{m}\Lambda_A (m)|m|^{-s}=\sum_n(\sum_{\deg(m)=n}\Lambda_A(m)q^{-sm})=\sum_n(\sum_{\deg(m)=n}\Lambda_A(m))u^n=\frac{-\zeta'_A(s)}{\zeta_A(s)}=\frac{q^{1-s}log(q)}{1-q^{1-s}} = \log(q) \sum_{n\mathop=1}^\infty q^n u^n

Hence,

\sum_{\deg(m)=n}\Lambda_A (m)=q^n \log(q),

and by dividing by q^n we get that,

\text{Ave}_n \Lambda_A(m)=\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,

\sum_{\deg f=n, f\text{ monic}}\Phi(f)=q^{2n}(1-q^{-1}).

See also

References

This article is issued from Wikipedia - version of the Friday, August 14, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.