§ 27.10. Periodic Number-Theoretic Functions

Notes:: See Apostol (1976, Chapter 8).
Permalink:: http://dlmf.nist.gov/27.10

If $k$ is a fixed positive integer, then a number-theoretic function $f$ is periodic (mod $k$ ) if

27.10.1 $f(n+k)=f(n),$ $n=1,2,\dots$ .

Defines:: $f(n)$ : function
Symbols:: $k$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.10.E1
Encodings:: TeX, pMathML, png

Examples are the Dirichlet characters (mod $k$ ) and the greatest common divisor $\left(n,k\right)$ regarded as a function of $n$ .

Every function periodic (mod $k$ ) can be expressed as a finite Fourier series of the form

27.10.2 $f(n)=\sum _{{m=1}}^{k}g(m)e^{{2\pi imn/k}},$

Defines:: $g(m)$ : periodic function
Symbols:: $k$ : positive integer, $m$ : positive integer, $n$ : positive integer and $f(n)$ : function
Permalink:: http://dlmf.nist.gov/27.10.E2
Encodings:: TeX, pMathML, png

where $g(m)$ is also periodic (mod $k$ ), and is given by

27.10.3 $g(m)=\dfrac{1}{k}\sum _{{n=1}}^{k}f(n)e^{{-2\pi imn/k}}.$

Defines:: $g(m)$ : periodic function
Symbols:: $k$ : positive integer, $m$ : positive integer, $n$ : positive integer and $f(n)$ : function
Permalink:: http://dlmf.nist.gov/27.10.E3
Encodings:: TeX, pMathML, png

An example is Ramanujan's sum:

27.10.4 $c_{{k}}\!\left(n\right)=\sum _{{m=1}}^{k}\chi _{1}(m)e^{{2\pi imn/k}},$

Defines:: $c_{{k}}\!\left(n\right)$ : Ramanujan's sum
Symbols:: $k$ : positive integer, $m$ : positive integer, $n$ : positive integer and $\chi$ : Dirichlet character
Permalink:: http://dlmf.nist.gov/27.10.E4
Encodings:: TeX, pMathML, png

where $\chi _{1}$ is the principal character (mod $k$ ). This is the sum of the $n$ th powers of the primitive $k$ th roots of unity. It can also be expressed in terms of the Möbius function as a divisor sum:

27.10.5 $c_{{k}}\!\left(n\right)=\sum _{{d\divides\left(n,k\right)}}d\mu\!\left(\frac{k}{d}\right).$

Defines:: $c_{{k}}\!\left(n\right)$ : Ramanujan's sum
Symbols:: $\mu\!\left(n\right)$ : Möbius function, $d$ : positive integer, $k$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.10.E5
Encodings:: TeX, pMathML, png

More generally, if $f$ and $g$ are arbitrary, then the sum

27.10.6 $s_{k}(n)=\sum _{{d\divides\left(n,k\right)}}f(d)g\left(\frac{k}{d}\right)$

Symbols:: $d$ : positive integer, $k$ : positive integer, $n$ : positive integer, $f(n)$ : function and $g(m)$ : periodic function
Permalink:: http://dlmf.nist.gov/27.10.E6
Encodings:: TeX, pMathML, png

is a periodic function of $n\;\;(\textrm{mod}k)$ and has the finite Fourier-series expansion

27.10.7 $s_{k}(n)=\sum _{{m=1}}^{k}a_{k}(m)e^{{2\pi imn/k}},$

Defines:: $a_{k}(m)$ : coefficients
Symbols:: $k$ : positive integer, $m$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.10.E7
Encodings:: TeX, pMathML, png

where

27.10.8 $a_{k}(m)=\sum _{{d\divides\left(m,k\right)}}g(d)f\left(\frac{k}{d}\right)\frac{d}{k}.$

Defines:: $a_{k}(m)$ : coefficients
Symbols:: $d$ : positive integer, $k$ : positive integer, $m$ : positive integer, $f(n)$ : function and $g(m)$ : periodic function
Permalink:: http://dlmf.nist.gov/27.10.E8
Encodings:: TeX, pMathML, png

Another generalization of Ramanujan's sum is the Gauss sum $G\!\left(n,\chi\right)$ associated with a Dirichlet character $\chi\;\;(\textrm{mod}k)$ . It is defined by the relation

27.10.9 $G\!\left(n,\chi\right)=\sum _{{m=1}}^{k}\chi(m)e^{{2\pi imn/k}}.$

Defines:: $G\!\left(n,\chi\right)$ : Gauss sum and $\chi$ : Dirichlet character
Symbols:: $k$ : positive integer, $m$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.10.E9
Encodings:: TeX, pMathML, png

In particular, $G\!\left(n,\chi _{1}\right)=c_{{k}}\!\left(n\right)$ .

$G\!\left(n,\chi\right)$ is separable for some $n$ if

27.10.10 $G\!\left(n,\chi\right)=\bar{\chi}(n)G\!\left(1,\chi\right).$

Symbols:: $G\!\left(n,\chi\right)$ : Gauss sum, $n$ : positive integer and $\chi$ : Dirichlet character
Permalink:: http://dlmf.nist.gov/27.10.E10
Encodings:: TeX, pMathML, png

For any Dirichlet character $\chi\;\;(\textrm{mod}k)$ , $G\!\left(n,\chi\right)$ is separable for $n$ if $\left(n,k\right)=1$ , and is separable for every $n$ if and only if $G\!\left(n,\chi\right)=0$ whenever $\left(n,k\right)>1$ . For a primitive character $\chi\;\;(\textrm{mod}k)$ , $G\!\left(n,\chi\right)$ is separable for every $n$ , and

27.10.11 $|G\!\left(1,\chi\right)|^{2}=k.$

Symbols:: $G\!\left(n,\chi\right)$ : Gauss sum, $k$ : positive integer and $\chi$ : Dirichlet character
Permalink:: http://dlmf.nist.gov/27.10.E11
Encodings:: TeX, pMathML, png

Conversely, if $G\!\left(n,\chi\right)$ is separable for every $n$ , then $\chi$ is primitive (mod $k$ ).

The finite Fourier expansion of a primitive Dirichlet character $\chi\;\;(\textrm{mod}k)$ has the form

27.10.12 $\chi(n)=\frac{G\!\left(1,\chi\right)}{k}\sum _{{m=1}}^{k}\bar{\chi}(m)e^{{-2\pi imn/k}}.$

Symbols:: $G\!\left(n,\chi\right)$ : Gauss sum, $k$ : positive integer, $m$ : positive integer, $n$ : positive integer and $\chi$ : Dirichlet character
Permalink:: http://dlmf.nist.gov/27.10.E12
Encodings:: TeX, pMathML, png