Average order of an arithmetic function: Difference between revisions

Revision as of 16:40, 8 August 2014

Revision as of 06:35, 9 August 2014

Line 7:

as ''x'' tends to infinity.

It is conventional to choose an approximating function ''g'' that is [[Continuous function|continuous]] and [[Monotonic function|monotone]]. But even thus an average order is of course not unique.

==Calculating mean values using Dirichlet series==

In case ''F'' is of the form

<math>F(n)=\sum_{d \mathop |n} f(n),</math></br /> for some arithmetic function ''f(n)'', one has,

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

Line 17 ⟶ 18:

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 {{math|'''N'''}}===

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

<math>Q_{k}:=\{n \in \mathbb{Z}|\;n \text{ is not divisible by } d^k \text{ for any integer } d\ge 2\}</math>.

We calculate the [[natural density]] of these numbers in {{math|'''N'''}}, that is, the average value of [[indicator function|'''1_{Q_k}''']], 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]]

Line 67 ⟶ 68:

which follows from the Möbius inversion formula.

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

Line 85:

* 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]].

===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.

Line 94 ⟶ 95:

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>\lim_{N\rightarrow \infty}\frac{1}{N}\sum_{n\le N}\frac{\varphi(n)}{n}=\frac{6}{\pi^{2}}=\frac{1}{\zeta(2)}</math>.

Line 101 ⟶ 102:

===Divisor functions===

Consider the generalization of <math>d(n)</math>:

<math>\sigma_{\alpha}(n)=\sum_{d|n}d^{\alpha}</math>.

Line 125 ⟶ 126:

we have the asymptotic relation

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

===Definition===

Let ''h(x)'' be a function on the set of [[monic polynomial]]s over [[finite field|'''F_q''']]. For <math>n\ge 1</math> we define

Line 137 ⟶ 139:

<math>\lim_{n\rightarrow\infty}\text{Ave}_{n}(h)</math> provided this limit exists.

===Zeta function and Dirichlet series in {{math|'''F'''_'''q'''[X]}}===

Let {{math|'''F_q[X]'''}}=''A'' be the [[ring of polynomials]] over the [[finite field]] {{math|'''F_q'''}}.

Line 144 ⟶ 146:

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

Line 173 ⟶ 175:

where the sum extends over all monic [[divisor]]s ''d'' of&nbsp;''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.

====The density of the k-th power free polynomials in {{math|'''F'''_'''q'''[X]}}====

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 δ, which is the density of the k-th power free polynomials in {{math|'''F'''_'''q'''[X]}}.

By multiplicativity of <math>\delta</math>:

Line 206 ⟶ 208:

===Examples===

====Polynomial Divisor functions====

At {{math|'''F_q[X]'''}}, we define

Line 213 ⟶ 216:

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

First, notice that:</br />

<math>\sigma_{k}(m)=h*\mathbb{I}(m)</math>

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

Line 231 ⟶ 234:

<math> \text{Ave}_{n}\sigma_{k}=\frac{1-q^{k(n+1)}}{1-q^{k}}</math>.

'''Number of divisors'''

Line 286:

Hence,

<math>\sum_{deg(m)=n}\Lambda_{A}(m)=q^{n}log(q)</math>,</br /> and by dividing by <math>q^n</math> we get that,

<math>Ave_{n}\Lambda_{A}(m)=log(q)</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,

Line 301:

==References==

* {{Hardy and Wright|citation=cite book}} Pp.&nbsp;347–360

* {{cite book | title=Introduction to Analytic and Probabilistic Number Theory | author=Gérald Tenenbaum | series=Cambridge studies in advanced mathematics | volume=46 | publisher=[[Cambridge University Press]] | year=1995 | isbn=0-521-41261-7 | zbl=0831.11001 | pages=36–55 }}

* {{Citation