TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 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.

The cycle lemma (Dvoretzky–Motzkin): if every $a_{i} \leq 1$ and $∥ a ∥ = k \geq 1$ , then exactly $k$ of the $m$ cyclic shifts of $a$ have all partial sums positive

Statement

Orientation convention, fixed here and cited wherever it is used. A shift $σ^{j} a$ is counted when all of its partial sums $\sum_{i < r} (σ^{j} a)_{i}$ , for $1 \leq r \leq m$ , are strictly positive, and shifts are indexed by starting position, so $σ^{j} a$ begins at position $j m o d m$ of $a$ (Cyclic shifts of an integer word and its periodic partial-sum function).

Let $m \geq 1$ and let $a$ be a word of length $m$ of integers with $a_{i} \leq 1$ for every $i < m$ and $∥ a ∥ = k \geq 1$ . Then exactly $k$ of the $m$ indices $j$ with $0 \leq j < m$ are such that $σ^{j} a$ has all its partial sums positive.
Boxes and circles. Let $p, n, μ \in N$ with $m : = p + n \geq 1$ , and let $a$ be a word of length $m$ in which $p$ positions carry the letter $1$ and the remaining $n$ positions carry the letter $- μ$ . Then $∥ a ∥ = p - μ n$ , and if $p - μ n \geq 1$ then exactly $p - μ n$ of the $m$ indices $j$ with $0 \leq j < m$ are such that $σ^{j} a$ has all its partial sums positive.

Facts & Assumptions

Given: a natural number $m \geq 1$ and a word $a$ of length $m$ of integers, with the hypotheses of the clause being proved.

[F1]

$∥ a ∥ = \sum_{i < m} a_{i}$ ; $(σ^{j} a)_{i} = a_{(i + j) m o d m}$ ; and the finite sum satisfies $\sum_{i < 0} c_{i} = 0$ and $\sum_{i < r + 1} c_{i} = \sum_{i < r} c_{i} + c_{r}$ (Cyclic shifts of an integer word and its periodic partial-sum function).

[L1]

For $∥ a ∥ \geq 1$ and $j \in Z$ : every partial sum $\sum_{i < r} (σ^{j} a)_{i}$ with $1 \leq r \leq m$ is positive if and only if $S_{a} (i) > S_{a} (j)$ for every integer $i > j$ , that is exactly when $j$ is a strict right minimum of $S_{a}$ ( $σ^{j} a$ has all partial sums positive exactly when $S_{a} (i) > S_{a} (j)$ for every $i > j$ ).

[L2]

If $a_{i} \leq 1$ for every $i < m$ and $k = ∥ a ∥ \geq 1$ , then for every $j_{0} \in Z$ the set of strict right minima of $S_{a}$ lying in ${j_{0}, \dots, j_{0} + m - 1}$ is finite with exactly $k$ elements (If every $a_{i} \leq 1$ and $∥ a ∥ \geq 1$ , the strict right minima form a two-sided increasing list on which $S_{a}$ increases by exactly $1$ at each successive index, clause 3).

[L3]

For a commutative monoid $M$ and $g : N \to M$ : $\prod_{i < p + n} g_{i} = (\prod_{i < p} g_{i}) \cdot (\prod_{j < n} g_{p + j})$ ; and if $π$ is a permutation of the von Neumann natural $ℓ$ and $h_{i} = g_{π (i)}$ for every $i < ℓ$ , then $\prod_{i < ℓ} h_{i} = \prod_{i < ℓ} g_{i}$ (Generalised associativity: in a monoid the product of a finite list does not depend on the bracketing, and in a commutative monoid it does not depend on the order of the factors either, clauses 1 and 3).

[L4]

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).

[L5]

$∣ n ∣ = n$ for a natural number $n$ , and a bijection transports finiteness and cardinality (The cardinality $∣ A ∣$ of a finite set).

Proof

technique · direct

1.1L1

By [L1] an index $j$ is such that $σ^{j} a$ has all its partial sums positive exactly when $j$ is a strict right minimum of $S_{a}$ ; so the set of indices to be counted in clause 1 is the set of strict right minima lying in ${0, 1, \dots, m - 1}$ .

2.1L2L5step 1.1

By [L2] with $j_{0} = 0$ that set is finite with exactly $k$ elements, which is clause 1.

3.1F1L3L4step 2.1∎

For clause 2, first compute the weight. Reordering the positions is a permutation of the index set, so by the permutation clause of [L3] the weight of $a$ equals the weight of the word $b$ whose first $p$ letters are $1$ and whose remaining $n$ letters are $- μ$ ; the splitting clause of [L3] gives $∥ b ∥ = \sum_{i < p} 1 + \sum_{j < n} (- μ)$ , and induction with the finite-sum clause of [F1] evaluates a sum of $p$ copies of $1$ as $p$ and a sum of $n$ copies of $- μ$ as $- μ n$ ; hence $∥ a ∥ = p - μ n$ . Each letter is at most $1$ , since $1 \leq 1$ and $- μ \leq 1$ for $μ \geq 0$ , so if $p - μ n \geq 1$ then clause 1 applies with $k = p - μ n$ and gives clause 2.

Remarks

The orientation convention is the one place this statement can silently go wrong. Dershowitz and Zaks cut a necklace at a valid origin and count shifts by strict domination; Krattenthaler's Lemma 10.4.6 states a version with weak domination below a line. These are the same lemma read in opposite directions, and a page that mixes them gets a one-to- $k$ correspondence pointing the wrong way. The convention above is strict positivity of every partial sum, with shifts indexed by starting position, and it is cited rather than restated wherever it is used.
Indices, not words. The count is of indices $j$ in ${0, \dots, m - 1}$ . Two different indices can give the same word, and then the same word is counted twice; that happens exactly when the shift stabiliser of $a$ is nontrivial, and the case the applications need is the one where the weight is coprime to $m$ and the $m$ shifts are pairwise distinct (If $\gcd (∥ a ∥, m) = 1$ then the shift stabiliser of $a$ is trivial, so its orbit has exactly $m$ elements).
What the hypotheses buy. Boundedness of the letters above by $1$ makes the strict right minima succeed one another at value steps of exactly $1$ ; positive weight makes them exist. Neither is a normalisation, and the companion of each is recorded in If every $a_{i} \leq 1$ and $∥ a ∥ \geq 1$ , the strict right minima form a two-sided increasing list on which $S_{a}$ increases by exactly $1$ at each successive index.

Depends on

Used by

Dependency tree · two levels

44 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

N. Dershowitz and S. Zaks, "The Cycle Lemma and Some Applications", Europ. J. Combinatorics 11 (1990) 35–40, §§1–1.1 (standard reference, not scraped)
C. Krattenthaler, "Lattice Path Enumeration", ch. 10 of the Handbook of Enumerative Combinatorics, §10.4, Lemma 10.4.6 (standard reference, not scraped)
A. Postnikov (notes by A. Lin), MIT 18.212 Algebraic Combinatorics, Spring 2019, Claim 11 (standard reference, not scraped)

The cycle lemma (Dvoretzky–Motzkin): if every ai≤1ai​≤1 and ∥a∥=k≥1∥a∥=k≥1, then exactly kk of the mm cyclic shifts of aa have all partial sums positive