Arithmetic function

In number theory, an arithmetic, arithmetical, or number-theoretic function[1][2] is for most authors[3][4][5] any function f(n) whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their definition the requirement that an arithmetical function "expresses some arithmetical property of n".[6]

An example of an arithmetic function is the divisor function whose value at a positive integer n is equal to the number of divisors of n.

There is a larger class of number-theoretic functions that do not fit the above definition, for example, the prime-counting functions. This article provides links to functions of both classes.

Arithmetic functions are often extremely irregular (see table), but some of them have series expansions in terms of Ramanujan's sum.

Multiplicative and additive functions

An arithmetic function a is

Two whole numbers m and n are called coprime if their greatest common divisor is 1, that is, if there is no prime number that divides both of them.

Then an arithmetic function a is

  • additive if a(mn) = a(m) + a(n) for all coprime natural numbers m and n;
  • multiplicative if a(mn) = a(m)a(n) for all coprime natural numbers m and n.

Notation

In this article, and mean that the sum or product is over all prime numbers:

and

Similarly, and mean that the sum or product is over all prime powers with strictly positive exponent (so k = 0 is not included):

The notations and mean that the sum or product is over all positive divisors of n, including 1 and n. For example, if n = 12, then

The notations can be combined: and mean that the sum or product is over all prime divisors of n. For example, if n = 18, then

and similarly and mean that the sum or product is over all prime powers dividing n. For example, if n = 24, then

Ω(n), ω(n), νp(n) – prime power decomposition

The fundamental theorem of arithmetic states that any positive integer n can be represented uniquely as a product of powers of primes: where p1 < p2 < ... < pk are primes and the aj are positive integers. (1 is given by the empty product.)

It is often convenient to write this as an infinite product over all the primes, where all but a finite number have a zero exponent. Define the p-adic valuation νp(n) to be the exponent of the highest power of the prime p that divides n. That is, if p is one of the pi then νp(n) = ai, otherwise it is zero. Then

In terms of the above the prime omega functions ω and Ω are defined by

ω(n) = k,
Ω(n) = a1 + a2 + ... + ak.

To avoid repetition, whenever possible formulas for the functions listed in this article are given in terms of n and the corresponding pi, ai, ω, and Ω.

Multiplicative functions

σk(n), τ(n), d(n) – divisor sums

σk(n) is the sum of the kth powers of the positive divisors of n, including 1 and n, where k is a complex number.

σ1(n), the sum of the (positive) divisors of n, is usually denoted by σ(n).

Since a positive number to the zero power is one, σ0(n) is therefore the number of (positive) divisors of n; it is usually denoted by d(n) or τ(n) (for the German Teiler = divisors).

Setting k = 0 in the second product gives

φ(n) – Euler totient function

φ(n), the Euler totient function, is the number of positive integers not greater than n that are coprime to n.

Jk(n) – Jordan totient function

Jk(n), the Jordan totient function, is the number of k-tuples of positive integers all less than or equal to n that form a coprime (k + 1)-tuple together with n. It is a generalization of Euler's totient, φ(n) = J1(n).

μ(n) – Möbius function

μ(n), the Möbius function, is important because of the Möbius inversion formula. See Dirichlet convolution, below.

This implies that μ(1) = 1. (Because Ω(1) = ω(1) = 0.)

τ(n) – Ramanujan tau function

τ(n), the Ramanujan tau function, is defined by its generating function identity:

Although it is hard to say exactly what "arithmetical property of n" it "expresses",[7] (τ(n) is (2π)−12 times the nth Fourier coefficient in the q-expansion of the modular discriminant function)[8] it is included among the arithmetical functions because it is multiplicative and it occurs in identities involving certain σk(n) and rk(n) functions (because these are also coefficients in the expansion of modular forms).

cq(n) – Ramanujan's sum

cq(n), Ramanujan's sum, is the sum of the nth powers of the primitive qth roots of unity:

Even though it is defined as a sum of complex numbers (irrational for most values of q), it is an integer. For a fixed value of n it is multiplicative in q:

If q and r are coprime, then

ψ(n) - Dedekind psi function

The Dedekind psi function, used in the theory of modular functions, is defined by the formula

Completely multiplicative functions

λ(n) – Liouville function

λ(n), the Liouville function, is defined by

χ(n) – characters

All Dirichlet characters χ(n) are completely multiplicative. Two characters have special notations:

The principal character (mod n) is denoted by χ0(a) (or χ1(a)). It is defined as

The quadratic character (mod n) is denoted by the Jacobi symbol for odd n (it is not defined for even n):

In this formula is the Legendre symbol, defined for all integers a and all odd primes p by

Following the normal convention for the empty product,

Additive functions

ω(n) – distinct prime divisors

ω(n), defined above as the number of distinct primes dividing n, is additive (see Prime omega function).

Completely additive functions

Ω(n) – prime divisors

Ω(n), defined above as the number of prime factors of n counted with multiplicities, is completely additive (see Prime omega function).

νp(n) – p-adic valuation of an integer n

For a fixed prime p, νp(n), defined above as the exponent of the largest power of p dividing n, is completely additive.

Logarithmic derivative

, where is the arithmetic derivative.

Neither multiplicative nor additive

π(x), Π(x), θ(x), ψ(x) – prime-counting functions

These important functions (which are not arithmetic functions) are defined for non-negative real arguments, and are used in the various statements and proofs of the prime number theorem. They are summation functions (see the main section just below) of arithmetic functions which are neither multiplicative nor additive.

π(x), the prime-counting function, is the number of primes not exceeding x. It is the summation function of the characteristic function of the prime numbers.

A related function counts prime powers with weight 1 for primes, 1/2 for their squares, 1/3 for cubes, ... It is the summation function of the arithmetic function which takes the value 1/k on integers which are the k-th power of some prime number, and the value 0 on other integers.

θ(x) and ψ(x), the Chebyshev functions, are defined as sums of the natural logarithms of the primes not exceeding x.

The Chebyshev function ψ(x) is the summation function of the von Mangoldt function just below.

Λ(n) – von Mangoldt function

Λ(n), the von Mangoldt function, is 0 unless the argument n is a prime power pk, in which case it is the natural log of the prime p:

p(n) – partition function

p(n), the partition function, is the number of ways of representing n as a sum of positive integers, where two representations with the same summands in a different order are not counted as being different:

λ(n) – Carmichael function

λ(n), the Carmichael function, is the smallest positive number such that   for all a coprime to n. Equivalently, it is the least common multiple of the orders of the elements of the multiplicative group of integers modulo n.

For powers of odd primes and for 2 and 4, λ(n) is equal to the Euler totient function of n; for powers of 2 greater than 4 it is equal to one half of the Euler totient function of n:

and for general n it is the least common multiple of λ of each of the prime power factors of n:

h(n) – Class number

h(n), the class number function, is the order of the ideal class group of an algebraic extension of the rationals with discriminant n. The notation is ambiguous, as there are in general many extensions with the same discriminant. See quadratic field and cyclotomic field for classical examples.

rk(n) – Sum of k squares

rk(n) is the number of ways n can be represented as the sum of k squares, where representations that differ only in the order of the summands or in the signs of the square roots are counted as different.

D(n) – Arithmetic derivative

Using the Heaviside notation for the derivative, the arithmetic derivative D(n) is a function such that

  • if n prime, and
  • (the product rule)

Summation functions

Given an arithmetic function a(n), its summation function A(x) is defined by

A can be regarded as a function of a real variable. Given a positive integer m, A is constant along open intervals m < x < m + 1, and has a jump discontinuity at each integer for which a(m) ≠ 0.

Since such functions are often represented by series and integrals, to achieve pointwise convergence it is usual to define the value at the discontinuities as the average of the values to the left and right:

Individual values of arithmetic functions may fluctuate wildly – as in most of the above examples. Summation functions "smooth out" these fluctuations. In some cases it may be possible to find asymptotic behaviour for the summation function for large x.

A classical example of this phenomenon[9] is given by the divisor summatory function, the summation function of d(n), the number of divisors of n:

An average order of an arithmetic function is some simpler or better-understood function which has the same summation function asymptotically, and hence takes the same values "on average". We say that g is an average order of f if

as x tends to infinity. The example above shows that d(n) has the average order log(n).[10]

Dirichlet convolution

Given an arithmetic function a(n), let Fa(s), for complex s, be the function defined by the corresponding Dirichlet series (where it converges):[11]

Fa(s) is called a generating function of a(n). The simplest such series, corresponding to the constant function a(n) = 1 for all n, is ζ(s) the Riemann zeta function.

The generating function of the Möbius function is the inverse of the zeta function:

Consider two arithmetic functions a and b and their respective generating functions Fa(s) and Fb(s). The product Fa(s)Fb(s) can be computed as follows:

It is a straightforward exercise to show that if c(n) is defined by

then

This function c is called the Dirichlet convolution of a and b, and is denoted by .

A particularly important case is convolution with the constant function a(n) = 1 for all n, corresponding to multiplying the generating function by the zeta function:

Multiplying by the inverse of the zeta function gives the Möbius inversion formula:

If f is multiplicative, then so is g. If f is completely multiplicative, then g is multiplicative, but may or may not be completely multiplicative.

Relations among the functions

There are a great many formulas connecting arithmetical functions with each other and with the functions of analysis, especially powers, roots, and the exponential and log functions. The page divisor sum identities contains many more generalized and related examples of identities involving arithmetic functions.

Here are a few examples:

Dirichlet convolutions

    where λ is the Liouville function.[12]
     [13]
      Möbius inversion
     [14]
      Möbius inversion
     [15]
     [16][17]
     [18]
      Möbius inversion
     
      Möbius inversion
     
      Möbius inversion
     
    where λ is the Liouville function.
     [19]
      Möbius inversion

Sums of squares

For all     (Lagrange's four-square theorem).

[20]

where the Kronecker symbol has the values

There is a formula for r3 in the section on class numbers below.

where ν = ν2(n).    [21][22][23]

where [24]

Define the function σk*(n) as[25]

That is, if n is odd, σk*(n) is the sum of the kth powers of the divisors of n, that is, σk(n), and if n is even it is the sum of the kth powers of the even divisors of n minus the sum of the kth powers of the odd divisors of n.

   [24][26]

Adopt the convention that Ramanujan's τ(x) = 0 if x is not an integer.

   [27]

Divisor sum convolutions

Here "convolution" does not mean "Dirichlet convolution" but instead refers to the formula for the coefficients of the product of two power series:

The sequence is called the convolution or the Cauchy product of the sequences an and bn.
These formulas may be proved analytically (see Eisenstein series) or by elementary methods.[28]

   [29]
   [30]
   [30][31]
   [29][32]
    where τ(n) is Ramanujan's function.    [33][34]

Since σk(n) (for natural number k) and τ(n) are integers, the above formulas can be used to prove congruences[35] for the functions. See Ramanujan tau function for some examples.

Extend the domain of the partition function by setting p(0) = 1.

   [36]   This recurrence can be used to compute p(n).

Peter Gustav Lejeune Dirichlet discovered formulas that relate the class number h of quadratic number fields to the Jacobi symbol.[37]

An integer D is called a fundamental discriminant if it is the discriminant of a quadratic number field. This is equivalent to D ≠ 1 and either a) D is squarefree and D ≡ 1 (mod 4) or b) D ≡ 0 (mod 4), D/4 is squarefree, and D/4 ≡ 2 or 3 (mod 4).[38]

Extend the Jacobi symbol to accept even numbers in the "denominator" by defining the Kronecker symbol:

Then if D < −4 is a fundamental discriminant[39][40]

There is also a formula relating r3 and h. Again, let D be a fundamental discriminant, D < −4. Then[41]

Let   be the nth harmonic number. Then

  is true for every natural number n if and only if the Riemann hypothesis is true.    [42]

The Riemann hypothesis is also equivalent to the statement that, for all n > 5040,

(where γ is the Euler–Mascheroni constant). This is Robin's theorem.

   [43]
   [44]
   [45]
   [46]

Menon's identity

In 1965 P Kesava Menon proved[47]

This has been generalized by a number of mathematicians. For example,

  • B. Sury[48]
  • N. Rao[49]
    where a1, a2, ..., as are integers, gcd(a1, a2, ..., as, n) = 1.
  • László Fejes Tóth[50]
    where m1 and m2 are odd, m = lcm(m1, m2).

In fact, if f is any arithmetical function[51][52]

where stands for Dirichlet convolution.

Miscellaneous

Let m and n be distinct, odd, and positive. Then the Jacobi symbol satisfies the law of quadratic reciprocity:

Let D(n) be the arithmetic derivative. Then the logarithmic derivative

See Arithmetic derivative for details.

Let λ(n) be Liouville's function. Then

    and
   

Let λ(n) be Carmichael's function. Then

    Further,

See Multiplicative group of integers modulo n and Primitive root modulo n.  

   [53][54]
   [55]
   [56]     Note that      [57]
   [58]   Compare this with 13 + 23 + 33 + ... + n3 = (1 + 2 + 3 + ... + n)2
   [59]
   [60]
    where τ(n) is Ramanujan's function.    [61]

First 100 values of some arithmetic functions

nfactorization𝜙(n)ω(n)Ω(n)𝜆(n)𝜇(n)𝜆(n)π(n)𝜎0(n)𝜎1(n)𝜎2(n)r2(n)r3(n)r4(n)
111001100111468
22111−1−10.69123541224
33211−1−11.10224100832
422212100.69237214624
55411−1−11.613262682448
62 · 322211034125002496
77611−1−11.95428500064
823413−100.6944158541224
932612101.10431391430104
102 · 54221104418130824144
11111011−1−12.40521212202496
1222 · 3423−10056282100896
13131211−1−12.566214170824112
142 · 76221106424250048192
153 · 5822110642426000192
1624814100.6965313414624
17171611−1−12.837218290848144
182 · 32623−1007639455436312
19191811−1−12.948220362024160
2022 · 5823−1008642546824144
213 · 712221108432500048256
222 · 1110221108436610024288
23232211−1−13.14922453000192
2423 · 3824100986085002496
25522012101.6193316511230248
262 · 1312221109442850872336
27331813−101.109440820032320
2822 · 71223−1009656105000192
29292811−1−13.3710230842872240
302 · 3 · 5833−1−10108721300048576
31313011−1−13.431123296200256
32251615−100.6911663136541224
333 · 112022110114481220048384
342 · 171622110114541450848432
355 · 72422110114481300048384
3622 · 321224100119911911430312
37373611−1−13.61122381370824304
382 · 191822110124601810072480
393 · 13242211012456170000448
4023 · 51624100128902210824144
41414011−1−13.71132421682896336
422 · 3 · 71233−1−10138962500048768
43434211−1−13.76142441850024352
4422 · 112023−100146842562024288
4532 · 52423−100146782366872624
462 · 232222110144722650048576
47474611−1−13.8515248221000384
4824 · 31625−100151012434100896
49724212101.95153572451454456
502 · 522023−1001569332551284744
513 · 173222110154722900048576
5222 · 132423−100156983570824336
53535211−1−13.97162542810872432
542 · 3318241001681204100096960
555 · 11402211016472317200576
5623 · 724241001681204250048192
573 · 193622110164803620048640
582 · 292822110164904210824720
59595811−1−14.08172603482072480
6022 · 3 · 516341001712168546000576
61616011−1−14.11182623722872496
622 · 313022110184964810096768
6332 · 73623−100186104455000832
64263216100.6918712754614624
655 · 1348221101848444201696672
662 · 3 · 112033−1−1018814461000961152
67676611−1−14.20192684490024544
6822 · 173223−1001961266090848432
693 · 234422110194965300096768
702 · 5 · 72433−1−1019814465000481152
71717011−1−14.2620272504200576
7223 · 322425−10020121957735436312
73737211−1−14.29212745330848592
742 · 37362211021411468508120912
753 · 524023−1002161246510056992
7622 · 193623−1002161407602024480
777 · 116022110214966100096768
782 · 3 · 132433−1−1021816885000481344
79797811−1−14.3722280624200640
8024 · 53225−10022101868866824144
81345414101.1022512173814102968
822 · 41402211022412684108481008
83838211−1−14.42232846890072672
8422 · 3 · 72434100231222410500048768
855 · 17642211023410875401648864
862 · 434222110234132925001201056
873 · 295622110234120842000960
8823 · 11402410023818010370024288
89898811−1−14.492429079228144720
902 · 32 · 5243410024122341183081201872
917 · 1372221102441128500048896
9222 · 234423−1002461681113000576
933 · 31602211024412896200481024
942 · 474622110244144110500961152
955 · 197222110244120941200960
9625 · 3322610024122521365002496
97979611−1−14.57252989410848784
982 · 724223−1002561711225541081368
9932 · 116023−100256156111020721248
10022 · 524024100259217136711230744
nfactorization𝜙(n)ω(n)Ω(n)𝜆(n)𝜇(n)𝜆(n)π(n)𝜎0(n)𝜎1(n)𝜎2(n)r2(n)r3(n)r4(n)

Notes

  1. Long (1972, p. 151)
  2. Pettofrezzo & Byrkit (1970, p. 58)
  3. Niven & Zuckerman, 4.2.
  4. Nagell, I.9.
  5. Bateman & Diamond, 2.1.
  6. Hardy & Wright, intro. to Ch. XVI
  7. Hardy, Ramanujan, § 10.2
  8. Apostol, Modular Functions ..., § 1.15, Ch. 4, and ch. 6
  9. Hardy & Wright, §§ 18.1–18.2
  10. Gérald Tenenbaum (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics. Vol. 46. Cambridge University Press. pp. 36–55. ISBN 0-521-41261-7.
  11. Hardy & Wright, § 17.6, show how the theory of generating functions can be constructed in a purely formal manner with no attention paid to convergence.
  12. Hardy & Wright, Thm. 263
  13. Hardy & Wright, Thm. 63
  14. see references at Jordan's totient function
  15. Holden et al. in external links The formula is Gegenbauer's
  16. Hardy & Wright, Thm. 288–290
  17. Dineva in external links, prop. 4
  18. Hardy & Wright, Thm. 264
  19. Hardy & Wright, Thm. 296
  20. Hardy & Wright, Thm. 278
  21. Hardy & Wright, Thm. 386
  22. Hardy, Ramanujan, eqs 9.1.2, 9.1.3
  23. Koblitz, Ex. III.5.2
  24. Hardy & Wright, § 20.13
  25. Hardy, Ramanujan, § 9.7
  26. Hardy, Ramanujan, § 9.13
  27. Hardy, Ramanujan, § 9.17
  28. Williams, ch. 13; Huard, et al. (external links).
  29. Ramanujan, On Certain Arithmetical Functions, Table IV; Papers, p. 146
  30. Koblitz, ex. III.2.8
  31. Koblitz, ex. III.2.3
  32. Koblitz, ex. III.2.2
  33. Koblitz, ex. III.2.4
  34. Apostol, Modular Functions ..., Ex. 6.10
  35. Apostol, Modular Functions..., Ch. 6 Ex. 10
  36. G.H. Hardy, S. Ramannujan, Asymptotic Formulæ in Combinatory Analysis, § 1.3; in Ramannujan, Papers p. 279
  37. Landau, p. 168, credits Gauss as well as Dirichlet
  38. Cohen, Def. 5.1.2
  39. Cohen, Corr. 5.3.13
  40. see Edwards, § 9.5 exercises for more complicated formulas.
  41. Cohen, Prop 5.3.10
  42. See Divisor function.
  43. Hardy & Wright, eq. 22.1.2
  44. See prime-counting functions.
  45. Hardy & Wright, eq. 22.1.1
  46. Hardy & Wright, eq. 22.1.3
  47. László Tóth, Menon's Identity and Arithmetical Sums ..., eq. 1
  48. Tóth, eq. 5
  49. Tóth, eq. 3
  50. Tóth, eq. 35
  51. Tóth, eq. 2
  52. Tóth states that Menon proved this for multiplicative f in 1965 and V. Sita Ramaiah for general f.
  53. Hardy Ramanujan, eq. 3.10.3
  54. Hardy & Wright, § 22.13
  55. Hardy & Wright, Thm. 329
  56. Hardy & Wright, Thms. 271, 272
  57. Hardy & Wright, eq. 16.3.1
  58. Ramanujan, Some Formulæ in the Analytic Theory of Numbers, eq. (C); Papers p. 133. A footnote says that Hardy told Ramanujan it also appears in an 1857 paper by Liouville.
  59. Ramanujan, Some Formulæ in the Analytic Theory of Numbers, eq. (F); Papers p. 134
  60. Apostol, Modular Functions ..., ch. 6 eq. 4
  61. Apostol, Modular Functions ..., ch. 6 eq. 3

References

Further reading

  • Schwarz, Wolfgang; Spilker, Jürgen (1994), Arithmetical Functions. An introduction to elementary and analytic properties of arithmetic functions and to some of their almost-periodic properties, London Mathematical Society Lecture Note Series, vol. 184, Cambridge University Press, ISBN 0-521-42725-8, Zbl 0807.11001
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.