= Cycle lemma
{title2=$\sum_i b_i=1$}
= Dvoretzky-Motzkin cycle lemma
{c}
{synonym}
The <cycle lemma> turns a constraint at every prefix into a choice of where to start reading a circular <sequence>. Think of a <lattice path> whose vertical increments record votes for two candidates: $+1$ for one candidate and $-1$ for the other. Its <partial sums> are the running lead. Rotating the increments preserves the final lead, but changes whether that lead stays strictly positive throughout. This makes rotation useful for counting <lattice paths> subject to prefix constraints; the sum-one <cycle lemma> also supplies the cyclic prefix condition in the <cyclic Turán covering construction>.
\b[The sum-one form.] Let $b=(b_1,\ldots,b_n)$ be any nonempty <sequence> of <integers> with $\sum_{i=1}^n b_i=1$. A starting position $r\in\{0,\ldots,n-1\}$ means reading the rotated <sequence>
$$
b^{(r)}=(b_{r+1},\ldots,b_n,b_1,\ldots,b_r).
$$
Call $r$ good when every nonempty <partial sum> of $b^{(r)}$ is strictly positive, including the full <sum>:
$$
P_j^{(r)}=\sum_{i=1}^{j}b_i^{(r)}>0\qquad(1\leq j\leq n).
$$
The <cycle lemma> says there is exactly one good starting position. Negative entries, zero entries and positive entries larger than one are all allowed in this sum-one form. The empty <partial sum> is zero and is excluded from the positivity requirement. Douglas West's exercise 1.3.46(a) states a stronger result for arbitrary <integer> entries: take its case with all $n$ <partial sums> positive. https://api.pageplace.de/preview/DT0400.9781108889520_A49236431/preview-9781108889520_A49236431.pdf#page=72[West, Combinatorial Mathematics, exercise 1.3.46(a), p. 50]{ref}
\b[A worked sum-one example.] For $b=(2,-2,0,1)$, the <partial sums> starting at zero are $S_0,S_1,S_2,S_3,S_4=0,2,0,0,1$. Starts $0,1,2$ fail: they have, respectively, a zero second <partial sum>, a negative first <partial sum>, and a zero first <partial sum>. Start $3$ reads $(1,2,-2,0)$ and has nonempty <partial sums> $1,3,1,1$, all positive. This example both allows an increment larger than one and shows why touching zero fails.
\b[Why the last minimum works.] Put $S_0=0$ and $S_j=\sum_{i=1}^j b_i$. Choose the last index $r$ attaining the <minimum> of the proper <partial sums> $S_0,\ldots,S_{n-1}$: include $S_0$ and exclude $S_n$. After that index, later proper <partial sums> are strictly larger than $S_r$; also $S_n=1>S_r$, since $S_r\leq0$. Before wrapping, the new <partial sums> are therefore positive differences $S_j-S_r$. After wrapping, they are $1+S_j-S_r\geq1$. In the worked example the last <minimum> is at $r=3$; choosing the first <minimum> at $r=0$ would fail. Uniqueness takes one further observation: two good starts would split the circle into two nonempty arcs, each having a positive <integer> <sum>, yet their <sum> would be one.
Back to article page
