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 , … ) {\displaystyle (a_{1},a_{2},\dots )} satisfies Gauss congruence if
∑ d ∣ n μ ( d ) a n / d ≡ 0 ( mod n ) {\displaystyle \sum _{d\mid n}\mu (d)a_{n/d}\equiv 0{\pmod {n}}}
for every n ≥ 1 {\displaystyle n\geq 1} , where μ {\displaystyle \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 , … ) {\displaystyle (b_{1},b_{2},\dots )} such that
a n = ∑ d ∣ n b d d {\displaystyle a_{n}=\sum _{d\mid n}b_{d}d}
for every n ≥ 1 {\displaystyle n\geq 1} . Furthermore, this is equivalent to the existence of a sequence of integers ( c 1 , c 2 , … ) {\displaystyle (c_{1},c_{2},\dots )} such that
a n = c 1 a n − 1 + c 2 a n − 2 + ⋯ + c n − 1 a 1 + n c n {\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{n-1}a_{1}+nc_{n}}
for every n ≥ 1 {\displaystyle n\geq 1} . If the values c n {\displaystyle c_{n}} are eventually zero, then the sequence ( a 1 , a 2 , … ) {\displaystyle (a_{1},a_{2},\dots )} satisfies a linear recurrence. A direct relationship between the sequences ( b 1 , b 2 , … ) {\displaystyle (b_{1},b_{2},\dots )} and ( c 1 , c 2 , … ) {\displaystyle (c_{1},c_{2},\dots )} is given by the equality of generating functions
∑ n ≥ 1 c n x n = 1 − ∏ n ≥ 1 ( 1 − x n ) b n {\displaystyle \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 ≥ 1 {\displaystyle (a_{n})_{n\geq 1}} known to satisfy Gauss congruence.
( a n ) {\displaystyle (a^{n})} for any integer a {\displaystyle a} , with c 1 = a {\displaystyle c_{1}=a} and c n = 0 {\displaystyle c_{n}=0} for n > 1 {\displaystyle n>1} .
t r ( A n ) {\displaystyle {\rm {tr}}(A^{n})} for any square matrix A {\displaystyle A} with integer entries. The divisor-sum sequence ( 1 , 3 , 4 , 7 , 6 , 12 , … ) {\displaystyle (1,3,4,7,6,12,\dots )} , with b n = 1 {\displaystyle b_{n}=1} for every n ≥ 1 {\displaystyle n\geq 1} . The Lucas numbers ( 1 , 3 , 4 , 7 , 11 , 18 … ) {\displaystyle (1,3,4,7,11,18\dots )} , with c 1 = c 2 = 1 {\displaystyle c_{1}=c_{2}=1} and c n = 0 {\displaystyle c_{n}=0} for every n > 2 {\displaystyle n>2} .
In dynamical systems Consider a discrete-time dynamical system, consisting of a set X {\displaystyle X} and a map T : X → X {\displaystyle T:X\to X} . We write T n {\displaystyle T^{n}} for the n {\displaystyle n} th iteration of the map, and say an element x {\displaystyle x} in X {\displaystyle X} has period n {\displaystyle n} if T n x = x {\displaystyle T^{n}x=x} . Suppose the number of points in X {\displaystyle X} with period n {\displaystyle n} is finite for every n ≥ 1 {\displaystyle n\geq 1} . If a n {\displaystyle a_{n}} denotes the number of such points, then the sequence ( a n ) n ≥ 1 {\displaystyle (a_{n})_{n\geq 1}} satisfies Gauss congruence, and the associated sequence ( b n ) n ≥ 1 {\displaystyle (b_{n})_{n\geq 1}} counts orbits of size n {\displaystyle n} . For example, fix a positive integer α {\displaystyle \alpha } . If X {\displaystyle X} is the set of aperiodic necklaces with beads of α {\displaystyle \alpha } colors and T {\displaystyle T} acts by rotating each necklace clockwise by a bead, then a n = α n {\displaystyle a_{n}=\alpha ^{n}} and b n {\displaystyle b_{n}} counts Lyndon words of length n {\displaystyle n} in an alphabet of α {\displaystyle \alpha } letters.
In algebraic number theory Gauss congruence can be extended to sequences of rational numbers, where such a sequence ( a n ) n ≥ 1 {\displaystyle (a_{n})_{n\geq 1}} satisfies Gauss congruence at a prime p {\displaystyle p} if
∑ d ∣ n μ ( d ) a n / d ≡ 0 ( mod n ) {\displaystyle \sum _{d\mid n}\mu (d)a_{n/d}\equiv 0{\pmod {n}}}
for every n = p r {\displaystyle n=p^{r}} with r ≥ 1 {\displaystyle r\geq 1} , or equivalently, if a p r ≡ a p r − 1 mod p r {\displaystyle a_{p^{r}}\equiv a_{p^{r-1}}{\text{ mod }}p^{r}} for every r ≥ 1 {\displaystyle r\geq 1} . A sequence of rational numbers ( a n ) n ≥ 1 {\displaystyle (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 = ∑ i = 1 r q i T r K ∣ Q ( θ i n ) {\displaystyle a_{n}=\sum _{i=1}^{r}q_{i}{\mathrm {Tr} }_{\mathbb {K} \mid \mathbb {Q} }(\theta _{i}^{n})} , where K {\displaystyle \mathbb {K} } is an algebraic number field with θ 1 , … , θ r ∈ K {\displaystyle \theta _{1},\dots ,\theta _{r}\in \mathbb {K} } , and q 1 , … , q r ∈ Q {\displaystyle q_{1},\dots ,q_{r}\in \mathbb {Q} } .
See also Necklace polynomial Necklace ring
References