Draft:Gauss congruence

In mathematics, Gauss congruence is a property held by certain sequences of integers, including the Lucas numbers and the divisor sum sequence. Sequences satisfying this property are also known as Dold sequences, Fermat sequences, Newton sequences, and realizable sequences. The property is named after Carl Friedrich Gauss (1777–1855), although Gauss never defined the property explicitly.

Sequences satisfying Gauss congruence naturally occur in the study of topological dynamics, algebraic number theory and combinatorics.

Definition

A sequence of integers $(a_{1},a_{2},\dots )$ satisfies Gauss congruence if

$\sum _{d\mid n}\mu (d)a_{n/d}\equiv 0{\pmod {n}}$

for every $n\geq 1$, where $\mu$ is the Möbius function. By Möbius inversion, this condition is equivalent to the existence of a sequence of integers $(b_{1},b_{2},\dots )$ such that

$a_{n}=\sum _{d\mid n}b_{d}d$

for every $n\geq 1$. Furthermore, this is equivalent to the existence of a sequence of integers $(c_{1},c_{2},\dots )$ such that

$a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{n-1}a_{1}+nc_{n}$

for every $n\geq 1$. If the values $c_{n}$ are eventually zero, then the sequence $(a_{1},a_{2},\dots )$ satisfies a linear recurrence.

A direct relationship between the sequences $(b_{1},b_{2},\dots )$ and $(c_{1},c_{2},\dots )$ is given by the equality of generating functions

$\sum _{n\geq 1}c_{n}x^{n}=1-\prod _{n\geq 1}(1-x^{n})^{b_{n}}$.

Examples

Below are examples of sequences $(a_{n})_{n\geq 1}$ known to satisfy Gauss congruence.

• $(a^{n})$ for any integer $a$, with $c_{1}=a$ and $c_{n}=0$ for $n>1$.
• ${\rm {tr}}(A^{n})$ for any square matrix $A$ with integer entries.
• The divisor-sum sequence $(1,3,4,7,6,12,\dots )$, with $b_{n}=1$ for every $n\geq 1$.
• The Lucas numbers $(1,3,4,7,11,18\dots )$, with $c_{1}=c_{2}=1$ and $c_{n}=0$ for every $n>2$.

In dynamical systems

Consider a discrete-time dynamical system, consisting of a set $X$ and a map $T:X\to X$. We write $T^{n}$ for the $n$^th iteration of the map, and say an element $x$ in $X$ has period $n$ if $T^{n}x=x$.

Suppose the number of points in $X$ with period $n$ is finite for every $n\geq 1$. If $a_{n}$ denotes the number of such points, then the sequence $(a_{n})_{n\geq 1}$ satisfies Gauss congruence, and the associated sequence $(b_{n})_{n\geq 1}$ counts orbits of size $n$.

For example, fix a positive integer $\alpha$. If $X$ is the set of aperiodic necklaces with beads of $\alpha$ colors and $T$ acts by rotating each necklace clockwise by a bead, then $a_{n}=\alpha ^{n}$ and $b_{n}$ counts Lyndon words of length $n$ in an alphabet of $\alpha$ letters.

In algebraic number theory

Gauss congruence can be extended to sequences of rational numbers, where such a sequence $(a_{n})_{n\geq 1}$ satisfies Gauss congruence at a prime $p$ if

$\sum _{d\mid n}\mu (d)a_{n/d}\equiv 0{\pmod {n}}$

for every $n=p^{r}$ with $r\geq 1$, or equivalently, if $a_{p^{r}}\equiv a_{p^{r-1}}{\text{ mod }}p^{r}$ for every $r\geq 1$.

A sequence of rational numbers $(a_{n})_{n\geq 1}$ defined by a linear recurrence satisfies Gauss congruence at all but finitely many primes if and only if

$a_{n}=\sum _{i=1}^{r}q_{i}{\mathrm {Tr} }_{\mathbb {K} \mid \mathbb {Q} }(\theta _{i}^{n})$,

where $\mathbb {K}$ is an algebraic number field with $\theta _{1},\dots ,\theta _{r}\in \mathbb {K}$, and $q_{1},\dots ,q_{r}\in \mathbb {Q}$.

See also

• Necklace polynomial
• Necklace ring