LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passaudited 2026-08-26

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

If $\gcd (∥ a ∥, m) = 1$ then the shift stabiliser of $a$ is trivial, so its orbit has exactly $m$ elements

Statement

Let $m \geq 1$ and let $a$ be a word of length $m$ of integers whose weight is coprime to $m$ , that is $\gcd (∥ a ∥, m) = 1$ (Coprime integers: $\gcd (a, b) = 1$ , Cyclic shifts of an integer word and its periodic partial-sum function). Then, for the action of $Z / m$ on words of length $m$ by cyclic shifts (Cyclic shifting is an action of $Z / m$ on the words of length $m$ over a set):

the stabiliser of $a$ is the trivial subgroup ${[0]_{m}}$ (The orbit $G \cdot x$ and stabilizer $G_{x}$ of a point in a group action);
the orbit of $a$ is finite with exactly $m$ elements.

Facts & Assumptions

Given: a natural number $m \geq 1$ and a word $a$ of length $m$ of integers with $\gcd (∥ a ∥, m) = 1$ .

[F1]

$(σ^{j} a)_{i} = a_{(i + j) m o d m}$ for $0 \leq i < m$ , and $j m o d m$ is the unique $r$ with $j = q m + r$ and $0 \leq r < m$ (Cyclic shifts of an integer word and its periodic partial-sum function).

[F2]

$S_{a} (j) = q ∥ a ∥ + \sum_{i < r} a_{i}$ for $j = q m + r$ with $0 \leq r < m$ ; $S_{a} (0) = 0$ ; and $S_{a} (j) - S_{a} (j - 1) = a_{(j - 1) m o d m}$ for every $j \in Z$ (Cyclic shifts of an integer word and its periodic partial-sum function).

[L1]

$σ^{0}$ is the identity, $σ^{j} (σ^{k} a) = σ^{j + k} a$ , and $[j]_{m} \cdot a : = σ^{j} a$ is a well-defined left action of the additive group $Z / m$ on the words of length $m$ (Cyclic shifting is an action of $Z / m$ on the words of length $m$ over a set, clauses 1 and 2).

[L2]

A property that holds at $0$ and passes from every natural number to its successor holds at every natural number: if a property $P$ satisfies $P (0)$ and ( $P (n) \Rightarrow P (σ (n))$ ) for all $n$ , then $P (n)$ holds for all $n \in N$ (The principle of mathematical induction).

[L3]

For $d, x \in Z$ , $d$ divides $x$ when $x = d q$ for some $q \in Z$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L4]

For $x, y \in Z$ not both $0$ there are integers $x_{0}, y_{0}$ with $x x_{0} + y y_{0} = \gcd (x, y)$ (Bézout's identity: for integers $a, b$ not both zero, $\gcd (a, b)$ is the least positive element of ${a x + b y : x, y \in Z}$ ; in particular $a x + b y = \gcd (a, b)$ has an integer solution).

[L5]

$\gcd (x, y)$ is the greatest common divisor of $x$ and $y$ , and $\gcd (x, y) \geq 1$ when $x$ and $y$ are not both $0$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ).

[L6]

Integers $x$ and $y$ are coprime when $\gcd (x, y) = 1$ (Coprime integers: $\gcd (a, b) = 1$ ).

[L7]

If $d ∣ x$ and $d ∣ y$ then $d ∣ x z + y w$ for all $z, w$ (Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ , clause 3).

[L8]

Every class in $Z / m$ contains exactly one integer $r$ with $0 \leq r < m$ , and $∣ Z / m ∣ = m$ (For $n \geq 1$ , every class in $Z / n$ has one representative $r$ with $0 \leq r < n$ , so $∣ Z / n ∣ = n$ ; while $Z / 0$ is in bijection with $Z$ ).

[L9]

$Z / m$ is a commutative ring under the induced operations, so its addition makes it an abelian group with identity $[0]_{m}$ (For every natural $n$ , $(Z / n, +)$ is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold).

[L10]

If $A$ is finite and $f : A \to B$ is a bijection then $B$ is finite and $∣ B ∣ = ∣ A ∣$ (The cardinality $∣ A ∣$ of a finite set).

Proof

technique · direct

1.1F1L1L8

Suppose $[d]_{m}$ lies in the stabiliser of $a$ , with $0 \leq d < m$ chosen as the representative supplied by [L8]. Then $σ^{d} a = a$ , that is $a_{(i + d) m o d m} = a_{i}$ for every $i$ with $0 \leq i < m$ .

2.1F1F2L2step 1.1

For every $j \in N$ one has $S_{a} (j + d) = S_{a} (j) + S_{a} (d)$ . At $j = 0$ this is $S_{a} (d) = 0 + S_{a} (d)$ by [F2]. If it holds at $j$ , then applying the one-step difference identity of [F2] at $j + 1 + d$ and at $j + 1$ gives $S_{a} (j + 1 + d) = S_{a} (j + d) + a_{(j + d) m o d m}$ and $S_{a} (j + 1) = S_{a} (j) + a_{j m o d m}$ , and step 1.1 makes the two added letters equal, since $(j + d) m o d m = ((j m o d m) + d) m o d m$ and $j m o d m$ lies in the index range; so the identity holds at $j + 1$ . Induction gives it for all $j$ .

3.1F2L2L3step 2.1

For every $k \in N$ one has $S_{a} (k d) = k S_{a} (d)$ : at $k = 0$ both sides are $0$ , and the inductive step is step 2.1 with $j = k d$ . Taking $k = m$ gives $m S_{a} (d) = S_{a} (m d)$ , while $m d = d \cdot m + 0$ exhibits $m d$ in the form $q m + r$ with $q = d$ and $r = 0$ , so $S_{a} (m d) = d ∥ a ∥$ by [F2]. Hence $m S_{a} (d) = d ∥ a ∥$ , and therefore $m$ divides $d ∥ a ∥$ .

4.1L3L4L5L6L7step 3.1

Since $m \geq 1$ , the pair $∥ a ∥$ , $m$ is not both zero, so [L4] gives integers $x_{0}, y_{0}$ with $∥ a ∥ x_{0} + m y_{0} = \gcd (∥ a ∥, m)$ , which is $1$ by hypothesis and [L6]. Multiplying by $d$ gives $d = (d ∥ a ∥) x_{0} + m (d y_{0})$ ; by step 3.1 the integer $m$ divides $d ∥ a ∥$ , and it divides $m$ , so [L7] makes it divide $d$ . With $0 \leq d < m$ this forces $d = 0$ : writing $d = m q$ , any $q \geq 1$ would give $d \geq m$ and any $q \leq - 1$ would give $d < 0$ . So the stabiliser contains only $[0]_{m}$ , which is clause 1.

5.1L1L8L9L10step 4.1∎

The map $Z / m \to Z / m \cdot a$ sending $[j]_{m}$ to $[j]_{m} \cdot a$ is surjective by the definition of the orbit and injective: if $[j]_{m} \cdot a = [j^{'}]_{m} \cdot a$ then applying the inverse of $[j^{'}]_{m}$ in the abelian group $Z / m$ and using the action axioms of [L1] and [L9] gives $[j - j^{'}]_{m} \cdot a = a$ , so $[j - j^{'}]_{m} = [0]_{m}$ by step 4.1 and $[j]_{m} = [j^{'}]_{m}$ . Since $∣ Z / m ∣ = m$ by [L8], transport along this bijection by [L10] makes the orbit finite with exactly $m$ elements, which is clause 2.

Remarks

The hypothesis is exactly what the Catalan application supplies. There the word has weight $1$ , and $\gcd (1, m) = 1$ for every $m$ , so the orbit of every such word has full size and the count of orbits is the count of words divided by $m$ . Without a coprimality hypothesis a word can repeat: the word $1, - 1, 1, - 1$ has weight $0$ and is fixed by the shift by two positions.
No orbit-stabiliser theorem is used. The orbit size is obtained from the injectivity of $[j]_{m} \mapsto [j]_{m} \cdot a$ , which is what a trivial stabiliser says directly; invoking the coset bijection would then require counting the cosets of the trivial subgroup, which is the same computation one step further away.

Depends on

Used by

Dependency tree · two levels

45 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

A. Postnikov (notes by A. Lin), MIT 18.212 Algebraic Combinatorics, Spring 2019, Claim 10 (standard reference, not scraped)
N. Dershowitz and S. Zaks, "The Cycle Lemma and Some Applications", Europ. J. Combinatorics 11 (1990) 35–40, §1 (standard reference, not scraped)

If gcd⁡(∥a∥,m)=1gcd(∥a∥,m)=1 then the shift stabiliser of aa is trivial, so its orbit has exactly mm elements