Английская Википедия: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 <math>f</math> be an arithmetic function. We say that an average order of <math>f</math> is <math>g</math> if <math display="block"> \sum_{n \le x} f(n) \sim \sum_{n \le x} g(n) </math> as <math>x</math> tends to infinity.
It is conventional to choose an approximating function <math>g</math> that is continuous and monotone. But even so an average order is of course not unique.
In cases where the limit <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>.
Examples
- An average order of Шаблон:Math, the number of divisors of Шаблон:Math, is Шаблон:Math;
- An average order of Шаблон:Math, the sum of divisors of Шаблон:Math, is Шаблон:Math;
- An average order of Шаблон:Math, Euler's totient function of Шаблон:Math, is Шаблон:Math;
- An average order of Шаблон:Math, the number of ways of expressing Шаблон:Math as a sum of two squares, is Шаблон:Math;
- The average order of representations of a natural number as a sum of three squares is Шаблон:Math;
- The average number of decompositions of a natural number into a sum of one or more consecutive prime numbers is Шаблон:Math;
- An average order of Шаблон:Math, the number of distinct prime factors of Шаблон:Math, is Шаблон:Math;
- An average order of Шаблон:Math, the number of prime factors of Шаблон:Math, is Шаблон:Math;
- The prime number theorem is equivalent to the statement that the von Mangoldt function Шаблон:Math has average order 1;
- An average value of Шаблон:Math, the Möbius function, is zero; this is again equivalent to the prime number theorem.
Calculating mean values using Dirichlet series
In case <math>F</math> is of the form <math display="block">F(n)=\sum_{d \mid n} f(d),</math> for some arithmetic function <math>f(n)</math>, one has, Шаблон:NumBlk 1 = \frac{x}{\zeta(k)}+O(x^{1/k}), </math> where for this we used the relation <math display="block">\sum_n (f(n)/n)=\sum_n f(n^k)n^{-k}=\sum_n \mu(n)n^{-k}=\frac{1}{\zeta(k)},</math> which follows from the Möbius inversion formula.
In particular, the density of the square-free integers is <math display="inline">\zeta(2)^{-1}=\frac{6}{\pi^{2}}</math>.
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 Шаблон:Math, 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 <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.
Thus, one can show that the natural density of the points which are visible from the origin is given by the average, <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 Шаблон:Math. 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 Шаблон:Math.
Divisor functions
Consider the generalization of <math>d(n)</math>: <math display="block">\sigma_\alpha(n)=\sum_{d\mid n}d^\alpha.</math>
The following are true: <math display="block"> \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} </math> where <math>\beta=\max(1,\alpha)</math>.
Better average order
This notion is best discussed through an example. From <math display="block"> \sum_{n\le x}d(n)=x\log x+(2\gamma-1)x+o(x)</math> (<math>\gamma</math> is the Euler–Mascheroni constant) and <math display="block"> \sum_{n\le x}\log n=x\log x-x+O(\log x),</math> we have the asymptotic relation <math display="block">\sum_{n\le x}(d(n)-(\log n+2\gamma))=o(x)\quad(x\to\infty),</math> which suggests that the function <math>\log n+2\gamma</math> is a better choice of average order for <math>d(n)</math> than simply <math>\log n</math>.
Mean values over Шаблон:Math
Definition
Let h(x) be a function on the set of monic polynomials over Fq. For <math>n\ge 1</math> we define <math display="block">\text{Ave}_n(h)=\frac{1}{q^n}\sum_{f \text{ monic},\deg(f)= n}h(f).</math>
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 <math display="block">\text{Ave}_n(h) \sim g(n)</math> as n tends to infinity.
In cases where the limit, <math display="block">\lim_{n\to\infty}\text{Ave}_n(h) = c</math> exists, it is said that h has a mean value (average value) c.
Zeta function and Dirichlet series in Шаблон:Math
Let Шаблон:Math be the ring of polynomials over the finite field Шаблон:Math.
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 <math display="block">D_{h}(s)=\sum_{f\text{ monic}} h(f)|f|^{-s},</math> where for <math>g\in A</math>, set <math>|g|=q^{\deg(g)}</math> if <math>g\ne 0</math>, and <math>|g|=0</math> otherwise.
The polynomial zeta function is then <math display="block">\zeta_{A}(s)=\sum_{f\text{ monic}} |f|^{-s}.</math>
Similar to the situation in Шаблон:Math, every Dirichlet series of a multiplicative function h has a product representation (Euler product): <math display="block">D_{h}(s) = \prod_{P} \left(\sum_{n=0}^{\infty} h(P^{n}) \left|P\right|^{-sn}\right),</math> where the product runs over all monic irreducible polynomials P.
For example, the product representation of the zeta function is as for the integers: <math display="inline">\zeta_{A}(s) = \prod_{P} \left(1 - \left|P\right|^{-s}\right)^{-1}</math>.
Unlike the classical zeta function, <math>\zeta_{A}(s)</math> is a simple rational function: <math display="block">\zeta_{A}(s)=\sum_{f}(|f|^{-s})=\sum_{n} \sum_{\deg(f) = n} q^{-sn} = \sum_{n}(q^{n-sn}) = (1-q^{1-s})^{-1}. </math>
In a similar way, If f and g are two polynomial arithmetic functions, one defines f * g, the Dirichlet convolution of f and g, by <math display="block">\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}</math> 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 <math>D_h D_g =D_{h*g}</math> 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 Шаблон:Math
Define <math>\delta(f)</math> to be 1 if <math>f</math> is k-th power free and 0 otherwise.
We calculate the average value of <math>\delta</math>, which is the density of the k-th power free polynomials in Шаблон:Math, in the same fashion as in the integers.
By multiplicativity of <math>\delta</math>: <math display="block">\sum_f \frac{\delta(f)}{|f|^s} = \prod_{P} \left(\sum_{j=0}^{k-1}(|P|^{-js})\right) = \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)}</math>
Denote <math>b_n</math> the number of k-th power monic polynomials of degree n, we get <math display="block">\sum_{f}\frac{\delta(f)}{|f|^{s}}=\sum_{n}\sum_{\text{def}f=n}\delta(f)|f|^{-s}=\sum_{n}b_{n}q^{-sn}. </math>
Making the substitution <math>u=q^{-s}</math> we get: <math display="block">\frac{1-qu^k}{1-qu}=\sum_{n=0}^\infty b_{n}u^{n}.</math>
Finally, expand the left-hand side in a geometric series and compare the coefficients on <math>u^{n}</math> on both sides, to conclude that <math display="block">b_{n}=\begin{cases}
q^{n} & n\le k-1 \\
q^{n}(1-q^{1-k}) &\text{otherwise}
\end{cases}</math>
Hence, <math display="block">\text{Ave}_{n}(\delta) = 1-q^{1-k} = \frac{1}{\zeta_{A}(k)}</math>
And since it doesn't depend on n this is also the mean value of <math>\delta(f)</math>.
Polynomial Divisor functions
In Шаблон:Math, we define <math display="block">\sigma _{k}(m)=\sum_{f|m, \text{ monic}}|f|^k.</math>
We will compute <math>\text{Ave}_{n}(\sigma_{k})</math> for <math>k\ge 1</math>.
First, notice that <math display="block">\sigma_{k}(m)=h*\mathbb{I}(m)</math> where <math>h(f)=|f|^{k}</math> and <math>\mathbb{I}(f)=1\;\; \forall{f}</math>.
Therefore, <math display="block">\sum_{m}\sigma_{k}(m)|m|^{-s}=\zeta_{A}(s)\sum_{m}h(m)|m|^{-s}.</math>
Substitute <math>q^{-s}=u</math> we get, <math display="block">\text{LHS}=\sum_n\left(\sum_{\deg(m)=n} \sigma_k(m)\right)u^n,</math>and by Cauchy product we get, <math display="block">\begin{align} \text{RHS} &=\sum_n q^{n(1-s)}\sum_{n}\left(\sum_{\deg(m)=n}h(m)\right)u^n \\ &=\sum_n q^n u^n \sum_{l}q^l q^{lk}u^l \\ &=\sum_n \left(\sum_{j =0}^{n}q^{n-j}q^{jk+j}\right) \\ &=\sum_n \left(q^n\left(\frac{1-q^{k(n+1)}}{1-q^k}\right)\right) u^n. \end{align}</math>
Finally we get that, <math display="block"> \text{Ave}_n\sigma_k=\frac{1-q^{k(n+1)}}{1-q^k}. </math>
Notice that <math display="block">q^n \text{Ave}_n\sigma_{k} = q^{n(k+1)}\left(\frac{1-q^{-k(n+1)}}{1-q^{-k}}\right) = q^{n(k+1)}\left(\frac{\zeta(k+1)}{\zeta(kn+k+1)}\right)</math>
Thus, if we set <math>x=q^n</math> then the above result reads <math display="block">\sum_{\deg(m)=n, m \text{ monic}} \sigma_k(m) = x^{k+1}\left(\frac{\zeta(k+1)}{\zeta(kn+k+1)}\right)</math> which resembles the analogous result for the integers: <math display="block">\sum_{n\le x}\sigma_{k}(n)=\frac{\zeta(k+1)}{k+1}x^{k+1}+O(x^{k})</math>
Number of divisors
Let <math>d(f)</math> be the number of monic divisors of f and let <math>D(n)</math> be the sum of <math>d(f)</math> over all monics of degree n. <math display="block">\zeta_A(s)^2 = \left(\sum_{h}|h|^{-s}\right)\left(\sum_g|g|^{-s}\right) = \sum_f\left(\sum_{hg=f} 1 \right)|f|^{-s} = \sum_f d(f)|f|^{-s}=D_d(s) = \sum_{n=0}^\infty D(n)u^{n}</math> 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>
Substitute <math>x=q^n</math> the above equation becomes: <math display="block">D(n)=x \log_q(x)+x</math> which resembles closely the analogous result for integers <math display="inline">\sum_{k=1}^n d(k) = x\log x+(2\gamma-1) x + O(\sqrt{x})</math>, where <math>\gamma</math> 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 <math>\zeta_{A}(s)</math>, and that it has no zeros.
Polynomial von Mangoldt function
The Polynomial von Mangoldt function is defined by: <math display="block">\Lambda_{A}(f) = \begin{cases} \log |P| & \text{if }f=|P|^k \text{ for some prime monic} P \text{ and integer } k \ge 1, \\ 0 & \text{otherwise.} \end{cases}</math> where the logarithm is taken on the basis of q.
Proposition. The mean value of <math>\Lambda_{A}</math> is exactly 1.
Proof. Let m be a monic polynomial, and let <math display="inline">m = \prod_{i=1}^{l} P_{i}^{e_i}</math> be the prime decomposition of m.
We have, <math display="block">\begin{align} \sum_{f|m}\Lambda_{A}(f) &= \sum_{(i_1,\ldots,i_l)|0\le i_j \le e_j} \Lambda_A\left(\prod_{j=1}^l P_j^{i_j}\right) = \sum_{j=1}^l \sum_{i=1}^{e_i}\Lambda_A (P_j^i) \\ &= \sum_{j=1}^l \sum_{i =1}^{e_i}\log|P_j|\\ &= \sum_{j=1}^l e_j\log|P_j| = \sum_{j=1}^l \log|P_j|^{e_j} \\ &= \log\left|\left(\prod_{i=1}^l P_i^{e_i}\right)\right|\\ &= \log(m) \end{align}</math>
Hence, <math display="block">\mathbb{I}\cdot\Lambda_A(m)=\log|m|</math> and we get that, <math display="block">\zeta_{A}(s)D_{\Lambda_{A}}(s) = \sum_{m}\log\left|m\right|\left|m\right|^{-s}.</math>
Now, <math display="block">\sum_m |m|^s = \sum_n \sum_{\deg m = n} u^n=\sum_n q^n u^{n}=\sum_n q^{n(1-s)}.</math>
Thus, <math display="block">\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\left|f\right|\left|f\right|^{-s}.</math>
We got that: <math display="block">D_{\Lambda_A}(s) = \frac{-\zeta'_A(s)}{\zeta_{A}(s)}</math>
Now, <math display="block">\begin{align} \sum_{m}\Lambda_A (m)|m|^{-s} &= \sum_n \left(\sum_{\deg(m)=n}\Lambda_A(m)q^{-sm}\right) = \sum_n \left(\sum_{\deg(m)=n} \Lambda_A(m)\right)u^n \\ &= \frac{-\zeta'_A(s)}{\zeta_A(s)} = \frac{q^{1-s}\log(q)}{1-q^{1-s}} \\ &= \log(q) \sum_{n=1}^\infty q^n u^n \end{align}</math>
Hence, <math display="block">\sum_{\deg(m)=n}\Lambda_A (m)=q^n \log(q),</math> and by dividing by <math>q^n</math> we get that, <math display="block">\text{Ave}_n \Lambda_A(m)=\log(q)=1. </math>
Polynomial Euler totient function
Define Euler totient function polynomial analogue, <math>\Phi</math>, to be the number of elements in the group <math>(A/fA)^{*}</math>. We have, <math display="block">\sum_{\deg f=n, f\text{ monic}}\Phi(f)=q^{2n}(1-q^{-1}).</math>
See also
- Divisor summatory function
- Normal order of an arithmetic function
- Extremal orders of an arithmetic function
- Divisor sum identities
References
- Шаблон:Hardy and Wright pp. 347–360
- Шаблон:Cite book
- Шаблон:Citation
- Шаблон:Citation
- Шаблон:Citation
- Шаблон:Citation
