§27.10 Periodic Number-Theoretic Functions

Notes:: See Apostol (1976, Chapter 8).
Keywords:: Dirichlet characters, Fourier series, Gauss sums, Ramanujan’s sum, finite Fourier series, number-theoretic functions, number theory, separable Gauss sum
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$ .

Symbols:: $k$ : positive integer, $n$ : positive integer and $f(n)$ : function
Permalink:: http://dlmf.nist.gov/27.10.E1
Encodings:: TeX, pMML, 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}},$

Symbols:: $e$ : base of exponential function, $k$ : positive integer, $m$ : positive integer, $n$ : positive integer, $f(n)$ : function and $g(m)$ : periodic function
Permalink:: http://dlmf.nist.gov/27.10.E2
Encodings:: TeX, pMML, 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}}.$

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

An example is Ramanujan’s sum:

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

Defines:: $\mathop{c_{{k}}\/}\nolimits\!\left(n\right)$ : Ramanujan’s sum
Symbols:: $\mathop{\chi\/}\nolimits\!\left(n\right)$ : Dirichlet character, $e$ : base of exponential function, $k$ : positive integer, $m$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.10.E4
Encodings:: TeX, pMML, png

where $\mathop{\chi\/}\nolimits _{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 $\mathop{c_{{k}}\/}\nolimits\!\left(n\right)=\sum _{{d\divides\left(n,k\right)}}d\mathop{\mu\/}\nolimits\!\left(\frac{k}{d}\right).$

Symbols:: $\mathop{\mu\/}\nolimits\!\left(n\right)$ : Möbius function, $\mathop{c_{{k}}\/}\nolimits\!\left(n\right)$ : Ramanujan’s sum, $d$ : positive integer, $k$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.10.E5
Encodings:: TeX, pMML, 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, pMML, png

is a periodic function of $n\;\;(\mathop{{\rm 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}},$

Symbols:: $e$ : base of exponential function, $k$ : positive integer, $m$ : positive integer, $n$ : positive integer and $a_{k}(m)$ : coefficients
Permalink:: http://dlmf.nist.gov/27.10.E7
Encodings:: TeX, pMML, 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}.$

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

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

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

Defines:: $\mathop{G\/}\nolimits\!\left(n,\mathop{\chi\/}\nolimits\right)$ : Gauss sum
Symbols:: $\mathop{\chi\/}\nolimits\!\left(n\right)$ : Dirichlet character, $e$ : base of exponential function, $k$ : positive integer, $m$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.10.E9
Encodings:: TeX, pMML, png

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

$\mathop{G\/}\nolimits\!\left(n,\mathop{\chi\/}\nolimits\right)$ is separable for some $n$ if

27.10.10 $\mathop{G\/}\nolimits\!\left(n,\mathop{\chi\/}\nolimits\right)=\conj{\mathop{\chi\/}\nolimits}(n)\mathop{G\/}\nolimits\!\left(1,\mathop{\chi\/}\nolimits\right).$

Symbols:: $\mathop{\chi\/}\nolimits\!\left(n\right)$ : Dirichlet character, $\mathop{G\/}\nolimits\!\left(n,\mathop{\chi\/}\nolimits\right)$ : Gauss sum, $\conj{z}$ : complex conjugate and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.10.E10
Encodings:: TeX, pMML, png

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

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

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

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

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

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

Symbols:: $\mathop{\chi\/}\nolimits\!\left(n\right)$ : Dirichlet character, $\mathop{G\/}\nolimits\!\left(n,\mathop{\chi\/}\nolimits\right)$ : Gauss sum, $\conj{z}$ : complex conjugate, $e$ : base of exponential function, $k$ : positive integer, $m$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.10.E12
Encodings:: TeX, pMML, png