User:Zvishem/sandbox

Mean values of arithmetic functions over N

Definition

Let F(n) be an arithmetic function. F has a mean value (or average value) c if

$\lim _{N\rightarrow \infty }{\frac {1}{N}}\sum _{n\mathop {=} 1}^{N}F(n)=c$

The above sum sometimes grows too fast for the mean value to exist. Often though, one can show that the growth is dominated by a simple function of n.

Calculating mean values using Dirichlet series

In case F is of the form

$F(n)=\sum _{d\mathop {|} n}f(n),$
for some arithmetic function f(n), one has,

$\sum _{n\leq x}F(n)=\sum _{d\leq x}f(d)\sum _{n\leq x,d|x}1=\sum _{f\leq d}f(d)[x/d]=x\sum _{d\leq x}{\frac {f(d)}{d}}{\text{ }}+O(\sum _{d\leq 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 Q_k of k-th-power-free integers is

$Q_{k}:=\{n\in \mathbb {Z} |\;n{\text{ is not divisible by }}d^{k}{\text{ for any integer }}d\geq 2\}$.

We calculate the natural density of these numbers in N, that is, the average value of 1_Qk, 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|n}f(d))n^{-s}$.

By comparing the coefficients, we get

$\delta (n)=\sum _{d|n}f(d)n^{-s}$.

Using (1), we get

$\sum _{d\leq x}\delta (d)=x\sum _{d\leq x}(f(d)/d)+O(x^{1/k})$.

We conclude that,

$\sum _{n\in Q_{k},n\leq 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}}}$.

Mean values over F_q[x]

Definition

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

${\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

$\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

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

where for $g\in A$, set $|g|=q^{deg(g)}$ if $g\neq 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 zeta function still holds: $\zeta _{A}(s)=\prod _{P}(1-|P|^{-s})^{-1}$.

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

$\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{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 $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 $\delta (f)$ to be 1 if $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 $\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}}}$

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 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, we get that

$b_{n}={\begin{cases}\;\;\,q^{n}&n\leq 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)$.

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 _{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)=xlog_{q}(x)+x$ which resembles closely the analogous result for integers $\sum _{k\mathop {=} 1}^{n}d(k)=xlogx+(2\gamma -1)x+O({\sqrt {x}})$, where $\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 $\zeta _{A}(s)$.

Examples and applications

The average order of Euler totient function

Let $\varphi$ Euler totient function, and define it's polynomial analogue, $\Phi$, to be the number of elements in the group $(A/fA)^{*}$. We have the following results:

• $\sum _{{\text{deg}}f=n,f{\text{monic}}}\Phi (f)=q^{2n}(1-q^{-1})$
• $\sum _{n\leq x}\varphi (n)={\frac {3}{\pi ^{2}}}x^{2}+O(xlogx)$
• $\lim _{N\rightarrow \infty }{\frac {1}{N}}\sum _{n\mathop {=} 1}^{N}{\frac {\varphi (n)}{n}}={\frac {6}{\pi ^{2}}}$
  

Visibility of lattice points

The latter formula has an interesting application concerning the distribution of lattice points in the plane which are visible from the origin.

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=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 ${\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\leq 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|n}d^{\alpha }$.

The following are true: $\sum _{n\leq x}\sigma _{\alpha }(n)={\begin{cases}\;\;\sum _{n\leq x}\sigma _{\alpha }(n)={\frac {\zeta (\alpha +1)}{\alpha +1}}x^{\alpha +1}+O(x^{\beta }){\mbox{if }}\alpha {\mbox{ is positive}}\\\;\;\sum _{n\leq x}\sigma _{-1}(n)=\zeta (2)x+O(logx){\mbox{if }}\alpha =-1\\\;\;\sum _{n\leq x}\sigma _{\alpha }(n)=\zeta (-\alpha +1)x+O(x^{max(0,1+\alpha )}){\mbox{otherwise }}\end{cases}}$

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

Polynomial Divisor function

Analogously, at F_q[X], we define

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

We will compute ${\text{Ave}}_{n}(\sigma _{k})$ for $k\geq 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 _{{\text{deg}}m=n})u^{n}$, and by Cauchy product we get,

${\text{RHS}}=\sum _{n}(q^{n}({\frac {1-q^{k(n+1)}}{1-q^{k}}}))u^{n}$.

Finally we get that,

${\text{Ave}}_{n}\sigma _{k}={\frac {1-q^{k(n+1)}}{1-q^{k}}}$.

Connection to Prime Number Theorem

Consider the two arithmetic functions:$\Lambda (n)$- von Mangoldt function and $\mu (n)$- Möbius function. It can be shown that $\Lambda$ has mean value 1, and $\mu$ has mean value 0. In fact, those facts are logically equivalent to Prime Number Theorem. Unlike the situation in N, it's not hard to calculate the mean values of the polynomial versions of these functions. In the next example we will calculate the mean value of the polynomial version of Mangoldt function.

Polynomial von Mangoldt function 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\geq 1,\\0&{\mbox{otherwise.}}\end{cases}}$

Proposition. $\Lambda _{A}$ has mean value $log(q)$.

Proof. First, notice that,

$\sum _{f|m}\Lambda _{A}(f)=log|m|$.

Hence,

$\zeta _{A}*\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 _{{\text{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,

$Ave_{n}\Lambda _{A}(m)=log(q)$.

Representations of a natural number as a sum

• The average number of representations of a natural number as a sum of two squares is π.

• The average number of representations of a natural number as a sum of three squares is 4π/3

• The average number of decompositions of a natural number into a sum of one or more consecutive prime numbers is log2.

References

• Tom M. Apostol (1976), Introduction to Analytic Number Theory, Springer Undergraduate Texts in Mathematics, ISBN 0-387-90163-9
• Michael Rosen (2000), Number Theory in Function Fields, Springer Graduate Texts In Mathematics, ISBN 0-387-95335-3
• Hugh L. Montgomery , Robert C. Vaughan (2006), Multiplicative Number Theory, Cambridge University Press, ISBN 978-0521849036
• Michael Baakea, Robert V. Moodyb, Peter A.B. Pleasantsc (2000), Diffraction from visible lattice points and kth power free integers, Discrete Mathematics- Journal {{citation}}: line feed character in |title= at position 54 (help)CS1 maint: multiple names: authors list (link)