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.{{cite journal |last1=Byszewski |first1=Jakub |last2=Graff |first2=Grzegorz |last3=Ward |first3=Thomas |title=Dold sequences, periodic points, and dynamics |journal=Bull. Lond. Math. Soc. |date=2021 |volume=53 |issue=5 |pages=1263–1298|doi=10.1112/blms.12531 |arxiv=2007.04031 }} The property is named after Carl Friedrich Gauss (1777–1855), although Gauss never defined the property explicitly.{{cite journal |last1=Smyth |first1=Chris |title=A coloring proof of a generalisation of Fermat's little theorem |journal=American Mathematical Monthly |date=1986 |volume=93 |issue=6 |page=469-471|doi=10.1080/00029890.1986.11971858 }}

Sequences satisfying Gauss congruence naturally occur in the study of topological dynamics, algebraic number theory and combinatorics.{{cite journal |last1=Zarelua |first1=A. V. |title=On congruences for the traces of powers of some matrices |journal=Tr. Mat. Inst. Steklova |date=2008 |volume=263 |pages=85–105}}

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_dd$

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_1a_{n-1}+c_2a_{n-2}+\cdots+c_{n-1}a_1+nc_n$

for every $n\geq 1$ .{{cite journal |last1=Du |first1=Bau-Sen |last2=Huang |first2=Sen-Shan |last3=Li |first3=Ming-Chia |title=Newton, Fermat and exactly realizable sequences |journal=J. Integer Seq. |date=2005 |volume=8 |pages=Article 05.1.2|bibcode=2005JIntS...8...12D }} 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_nx^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^nx=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}$ .{{cite journal |last1=Minton |first1=Gregory |title=Linear recurrence sequences satisfying congruence conditions |journal=Proc. Amer. Math. Soc. |date=2014 |volume=142 |issue=7 |pages=2337–2352|doi=10.1090/S0002-9939-2014-12168-X |doi-access=free }}

References

Category:Integer sequences

Category:Mathematical theorems