LemmaStatement: AI-adaptedProof: 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.

$σ^{j} a$ has all partial sums positive exactly when $S_{a} (i) > S_{a} (j)$ for every $i > j$

Statement

Let $m \geq 1$ , let $a$ be a word of length $m$ of integers with $∥ a ∥ \geq 1$ , and let $j \in Z$ (Cyclic shifts of an integer word and its periodic partial-sum function).

For every $r$ with $0 \leq r \leq m$ ,

$\sum_{i < r} (σ^{j} a)_{i} = S_{a} (j + r) - S_{a} (j) .$
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$ .

Call $j \in Z$ a strict right minimum of $S_{a}$ when $S_{a} (i) > S_{a} (j)$ for every integer $i > j$ . Clause 2 says that the shift $σ^{j} a$ has all of its partial sums positive exactly when $j$ is a strict right minimum of $S_{a}$ .

Facts & Assumptions

Given: a natural number $m \geq 1$ , a word $a$ of length $m$ of integers with $∥ a ∥ \geq 1$ , and an integer $j$ .

[F1]

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

[F2]

$S_{a} (0) = 0$ ; $S_{a} (j) - S_{a} (j - 1) = a_{(j - 1) m o d m}$ for every $j \in Z$ ; $S_{a} (j + m) = S_{a} (j) + ∥ a ∥$ for every $j \in Z$ ; 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]

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

[L2]

For $x, b \in Z$ with $b \neq 0$ there is exactly one pair $(q, r)$ of integers with $x = q b + r$ and $0 \leq r < ∣ b ∣$ (Division with remainder for any nonzero divisor: for $a \in Z$ and $b \neq 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < ∣ b ∣$ ).

Proof

technique · direct

1.1F1F2L1

Clause 1 holds by induction on $r$ . At $r = 0$ both sides are $0$ by [F2]. If it holds at $r$ with $r < m$ , then the finite-sum clause gives $\sum_{i < r + 1} (σ^{j} a)_{i} = \sum_{i < r} (σ^{j} a)_{i} + (σ^{j} a)_{r}$ , which by the inductive hypothesis and [F1] is $S_{a} (j + r) - S_{a} (j) + a_{(j + r) m o d m}$ , and the one-step difference identity of [F2] applied at $j + r + 1$ turns the last two terms into $S_{a} (j + r + 1) - S_{a} (j)$ .

2.1F2L1L2step 1.1

For every $t \in N$ and every $i \in Z$ one has $S_{a} (i + t m) = S_{a} (i) + t ∥ a ∥$ : at $t = 0$ this is trivial, and the step is the quasiperiodicity clause of [F2]. Hence, if every partial sum of $σ^{j} a$ over $1 \leq r \leq m$ is positive, then $S_{a} (j + r) > S_{a} (j)$ for those $r$ by step 1.1, and for an arbitrary integer $i > j$ we may write $i - j - 1 = t m + r^{'}$ with $0 \leq r^{'} < m$ and $t \geq 0$ by [L2], since $i - j - 1 \geq 0$ ; putting $r : = r^{'} + 1$ , so $1 \leq r \leq m$ and $i = j + r + t m$ , gives $S_{a} (i) = S_{a} (j + r) + t ∥ a ∥ \geq S_{a} (j + r) > S_{a} (j)$ because $∥ a ∥ \geq 1$ and $t \geq 0$ .

3.1step 1.1step 2.1∎

Conversely, if $S_{a} (i) > S_{a} (j)$ for every integer $i > j$ , then in particular $S_{a} (j + r) > S_{a} (j)$ for $1 \leq r \leq m$ , so every partial sum of $σ^{j} a$ over that range is positive by step 1.1. The two directions together are clause 2.

Remarks

Why the condition is stated for all $i > j$ and not for one period. The one-period form is what a shift's partial sums see, and the unbounded form is what the succession structure of the strict right minima is stated in. The equivalence needs $∥ a ∥ \geq 1$ : with weight $0$ the function $S_{a}$ is periodic, $S_{a} (j + m) = S_{a} (j)$ , and no index is a strict right minimum. In that case the full-period partial sum is also $0$ , so no shift has every nonempty partial sum positive.
The strict right minima are a property of $S_{a}$ alone. They do not refer to the word except through its partial-sum function, and that is what makes the counting argument of the cycle lemma a statement about $Z$ rather than about words.

Depends on

Used by

Dependency tree · two levels

18 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 (standard reference, not scraped)

σjaσja has all partial sums positive exactly when Sa(i)>Sa(j)Sa​(i)>Sa​(j) for every i>ji>j