Cyclic shifts of an integer word and its periodic partial-sum function

Throughout, $m$ is a natural number with $m\ge 1$, and a word of length $m$ over a set $X$ is a function $a$ from $\{0,1,\dots ,m-1\}$ to $X$, written $a=a_0{a}_1\cdots a_{m-1}$ (Finite words, contiguous factors, avoidance and proper-prefix states).

Remainders. For every $j\in \mathbb{Z}$ there is exactly one pair $(q,r)$ of integers with $j=qm+r$ and $0\le r<m$ (Division with remainder for any nonzero divisor: for $a\in \mathbb{Z}$ and $b\mathrm{\ne }0$ there are unique $q,r\in \mathbb{Z}$ with $a=qb+r$ and $0\le r<\mathrm{\mid }b\mathrm{\mid }$, whose bound $0\le r<\mid m\mid$ is $0\le r<m$ here because $m\ge 1$, The absolute value $\mathrm{\mid }a\mathrm{\mid }$ of an integer). Write $j<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>m:=r$ for that remainder, so $0\le j<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>m<m$ for every integer $j$, including negative $j$.

Cyclic shifts. For $j\in \mathbb{Z}$ the shift ${\sigma }^{j}a$ of a word $a$ of length $m$ over $X$ is the word of length $m$ over $X$ given by

$({\sigma }^{j}a{)}_i:=a_{(i+j)<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>m}(0\le i<m)\mathrm{.}$

Since $(i+j)<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>m$ lies in $\{0,\dots ,m-1\}$ this is again a word of length $m$, and ${\sigma }^{j}a$ begins at the position $j<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>m$ of $a$.

Weight. Let now $a$ be a word of length $m$ of integers (The integers as equivalence classes of pairs of naturals). Its weight is

$\parallel a\parallel :={\sum }_{i<m}{a}_i,$

the finite sum in the commutative monoid $(\mathbb{Z},+,0)$ (The integers form a commutative ring, Semigroup and monoid), that is the finite product of The product $g_0{g}_1\cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ($n=0$) equal to the identity written additively, whose two clauses read ${\sum }_{i<0}{a}_i=0$ and ${\sum }_{i<r+1}{a}_i={\sum }_{i<r}{a}_i+a_r$.

The periodic partial-sum function. Define $S_a:\mathbb{Z}\to \mathbb{Z}$ by

$S_a(j):=q\parallel a\parallel +{\sum }_{i<r}{a}_i\text{where }j=qm+r,0\le r<m\mathrm{.}$

This is well defined because the pair $(q,r)$ is unique. Defining $S_a$ on all of $\mathbb{Z}$ by a closed formula, rather than by extending a one-sided sequence, is what makes the statements below about all integers $j$ available at once.

Three identities, proved here because everything below uses them.

(a) On the first period $S_a$ is the ordinary partial sum. For $0\le j\le m$ one has $S_a(j)={\sum }_{i<j}{a}_i$. For $j<m$ this is the definition with $q=0$ and $r=j$; for $j=m$ it is the definition with $q=1$ and $r=0$, giving $S_a(m)=\parallel a\parallel ={\sum }_{i<m}{a}_i$. In particular $S_a(0)=0$.

(b) Quasiperiodicity. $S_a(j+m)=S_a(j)+\parallel a\parallel$ for every $j\in \mathbb{Z}$: if $j=qm+r$ with $0\le r<m$ then $j+m=(q+1)m+r$ with the same $r$, so the two values differ by exactly one copy of $\parallel a\parallel$.

(c) The one-step difference. $S_a(j)-S_a(j-1)=a_{(j-1)<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>m}$ for every $j\in \mathbb{Z}$. Write $j-1=qm+r$ with $0\le r<m$, so $(j-1)<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>m=r$ and $S_a(j-1)=q\parallel a\parallel +{\sum }_{i<r}{a}_i$. If $r+1<m$ then $j=qm+(r+1)$, so $S_a(j)=q\parallel a\parallel +{\sum }_{i<r+1}{a}_i$ and the difference is $a_r$ by the second clause of the finite sum. If $r+1=m$ then $j=(q+1)m+0$, so $S_a(j)=(q+1)\parallel a\parallel$ and the difference is $\parallel a\parallel -{\sum }_{i<m-1}{a}_i$, which is $a_{m-1}=a_r$ by the same clause applied at $r=m-1$.

• The shift index is a position, not a rotation count in the other direction. ${\sigma }^{j}a$ reads $a$ starting at position $j<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>m$, so ${\sigma }^{1}a$ drops the first letter of $a$ and appends it at the end. The sources cut necklaces at both ends and a page that mixes the two conventions gets the correspondences of the cycle lemma pointing the wrong way; the convention here is fixed once, in this definition, and is restated where it is used.

• The weight is an integer and may be negative or zero. Nothing in this definition constrains the letters. The hypotheses $a_i\le 1$ and $\parallel a\parallel \ge 1$ that the cycle lemma needs are stated in the results that use them, not built into the objects.