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
as x tends to infinity.
In cases where the limit
exists, it is said that f has a mean value (average value) c.
- 1 Examples
- 2 Calculating mean values using Dirichlet series
- 3 Better average order
- 4 Mean values over Fq[x]
- 5 See also
- 6 References
- An average order of d(n), the number of divisors of n, is log(n);
- An average order of σ(n), the sum of divisors of n, is nπ2 / 6;
- An average order of φ(n), Euler's totient function of n, is 6n / π2;
- An average order of r(n), the number of ways of expressing n as a sum of two squares, is πn
- The average order of representations of a natural number as a sum of three squares is 4πn/3
- The average number of decompositions of a natural number into a sum of one or more consecutive prime numbers is nlog2.
- An average order of ω(n), the number of distinct prime factors of n, is log log n;
- An average order of Ω(n), the number of prime factors of n, is log log n;
- 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.
Calculating mean values using Dirichlet series
In case F is of the form
for some arithmetic function f(n), one has,
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
By the Möbius inversion formula, we get
where stands for the Möbius function. Equivalently,
By comparing the coefficients, we get
Using (1), we get
We conclude that,
Where for this we used the relation
which follows from the Möbius inversion formula.
In particular, the density of the square-free integers is .
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=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 is the probability of a random point on the square 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,
interestingly, is also the natural density of the square-free numbers in N. In fact, this is not a coincidence. Consider the k-dimensional lattice, . The natural density of the points which are visible from the origin is , which is also the natural density of the k-th free integers in N.
Consider the generalization of :
The following are true:
Better average order
This notion is best discussed through an example. From
( is the Euler-Mascheroni constant) and
we have the asymptotic relation
which suggests that the function is a better choice of average order for than simply .
Mean values over Fq[x]
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
as n tends to infinity.
In cases where the limit,
exists, it is said that h has a mean value (average value) c.
Zeta function and Dirichlet series in Fq[X]
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
where for , set if , and otherwise.
The polynomial zeta function is then
Similar to the situation in N, every Dirichlet series of a multiplicative function h has a product representation (Euler product):
Where the product runs over all monic irreducible polynomials P.
For example, the product representation of the zeta function is as for the integers: .
Unlike the classical zeta function, is a simple rational function:
In a similar way, If ƒ and g are two polynomial arithmetic functions, one defines ƒ * g, the Dirichlet convolution of ƒ and g, by
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 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 Fq[X]
Define to be 1 if 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 Fq[X], in the same fashion as in the integers.
By multiplicativity of :
Denote the number of k-th power monic polynomials of degree n, we get
Making the substitution we get:
Finally, expand the left-hand side in a geometric series and compare the coefficients on on both sides, to conclude that
And since it doesn't depend on n this is also the mean value of .
Polynomial Divisor functions
In Fq[X], we define
We will compute for .
First, notice that:
where and .
Substitute we get,
, and by Cauchy product we get,
Finally we get that,
Thus, if we set then the above result reads
which resembles the analogous result for the integers:
Number of divisors
Let be the number of monic divisors of f and let be the sum of over all monics of degree n.
Expanding the right-hand side into power series we get,
Substitute the above equation becomes:
which resembles closely the analogous result for integers , where 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 , and that it has NO zeros.
Polynomial von Mangoldt function function
The Polynomial von Mangoldt function is defined by:
Where the logarithm is taken on the basis of q.
Proposition. The mean value of is exactly 1.
Proof. Let m be a monic polynomial, and let be the prime decomposition of m.
and we get that,
We got that:
and by dividing by we get that,
Polynomial Euler totient function
Define Euler totient function polynomial analogue, , to be the number of elements in the group . We have,
- Divisor summatory function
- Normal order of an arithmetic function
- Extremal orders of an arithmetic function
- Hardy, G. H.; Wright, E. M. (2008) . An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921986-5. Zbl 1159.11001. Pp. 347–360
- Gérald Tenenbaum (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics 46. Cambridge University Press. pp. 36–55. ISBN 0-521-41261-7. Zbl 0831.11001.
- 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