1 Introduction and main results
The ubiquitous Prouhet–Thue–Morse sequence,
$$ \begin{align*} \textbf{t} = 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, \ldots, \end{align*} $$
is a well-studied sequence with intriguing properties and a wide range of applications in mathematics [Reference Allouche, Shallit, Ding, Helleseth and Niederreiter1]. This sequence first appeared in a work of Eugène Prouhet in 1851 and was later popularised by Thue [Reference Thue7, Reference Thue, Nagell, Selberg, Selberg and Thalberg8], who established some of its combinatorial properties. One notable property is that the sequence is overlap-free, meaning that it does not contain segments of the form
$axaxa$
, where a is any number belonging to
$ \{0,1\}$
and x is any finite (or empty) string of numbers in
$\{0,1\}$
. For example, in the sequence
$\textbf {t}$
, there are no segments
$0,1,0,1,0$
or
$1,0,0,1,0,0,1$
.
The Thue–Morse sequence has a natural generalisation known as the digit sum sequence in base
$M $
modulo m, denoted by
$\textbf {t}_{M,m}$
[Reference Allouche and Shallit2, Reference Cusick and Ciungu6]. The original Thue–Morse sequence corresponds to the case
$M=m=2$
, and is usually represented by
${\textbf {t}=\textbf {t}_{2,2}}$
. The digit sum sequence finds direct applications in problems such as the Prouhet–Tarry–Escott problem [Reference Bolker, Offner, Richman and Zara5].
We develop further generalisations by introducing additional variations of the digit sum sequence. Specifically, we propose a simple procedure of shifting the bases, which leads to a new family of sequences denoted by
$\mathcal {B}_{M,N,m}$
, with
$\textbf {t}_{M,m}$
being a special case. We explore combinatorial properties of
$\mathcal {B}_{M,N,m}$
, uncovering some intriguing patterns and structures.
In Section 2, we establish the necessary notation and definitions commonly used in the field of combinatorics of words, following the standard conventions outlined in [Reference Berstel, Lauve, Reutenauer and Saliola4]. We introduce the sequences
$\mathcal {B}_{M,N}$
and
$\mathcal {B}_{M,N,m}$
, along with their corresponding morphisms
$\mu _{M,N}$
and
$\mu _{M,N,m}$
. These sequences and morphisms are the fundamental objects of study throughout this work. In Section 3, we characterise the sequence
$\mathcal {B}_{M,N}$
using the morphism
$\mu _{M,N}$
. Specifically, we prove that
$\mathcal {B}_{M,N}$
is the fixed point of the morphism
$\mu _{M,N}$
at
$0$
. Section 4 presents two results on palindromes and squares in
$\mathcal {B}_{M,N,m}$
. These results are partial generalisations of the results in [Reference Allouche and Shallit2, Reference Cusick and Ciungu6].
Theorem 1.1 (Palindrome theorem).
$\mathcal {B}_{M,N,m}$
contains arbitrarily long palindromes if and only if
$m=2$
.
Theorem 1.2 (Square theorem).
-
(1) For
$N\geq 2$
,
$\mathcal {B}_{M,N,m}$
contains the single letter square
$aa$
if and only if the multiplicative inverse of
$M-N$
exists in the set
$\{(N^k-1)/(N-1)\}_{1\leq k \leq m}$
, where the calculations are performed in the ring
$\mathbb {Z}_m=\{0,1,2,\ldots ,m-1\}$
. -
(2) For
$M\geq 2, N\leq M$
and
$m\geq 2$
,
$\mathcal {B}_{M,N,m}$
contains arbitrarily large squares.
Section 5 focus on overlaps and periods within the sequence
$\mathcal {B}_{M,N,m}$
. We present the following theorem regarding the overlap-free property.
Theorem 1.3 (Overlap-free property).
If
$m\geq M$
and the greatest common divisor of N and m is
$1$
, then
$\mathcal {B}_{M,N,m}$
is overlap-free, that is, it contains no overlaps.
In the final section, we present some open questions and directions for future research.
2 Definitions and notation
We use the symbol
$\mathfrak {A}$
to represent the alphabet of letters, which can encompass either a finite or infinite set of symbols. For a positive integer
$m\geq 1$
,
$\mathfrak {A}_m$
denotes the alphabet
$\{0,1,2,\ldots m-1\}$
and
$\mathfrak {A}_{\omega }=\{0,1,2,3,\ldots \}$
.
The free monoid generated by
$\mathfrak {A}$
is denoted by
$\mathfrak {A}^{*}$
, where concatenation serves as multiplication. The empty word is denoted by
$\epsilon $
and serves as the neutral element. The set of nonempty words is denoted by
$\mathfrak {A}^+=\mathfrak {A}^{*}\backslash \{\epsilon \}.$
For a word
$w=a_1a_2\cdots a_k\in \mathfrak {A}^*$
, a word
$w_1$
is a factor of w if there exist words
$x,y$
in
$\mathfrak {A}^*$
such that
$w=xw_1y$
; it is a proper factor if
$xy\neq \epsilon $
. A word u is called a prefix of w if
$w=uy$
for some word y, and it is a proper prefix if
$y\neq \epsilon $
; suffix and proper suffix are defined similarly. The reversal of a word
$w=a_1a_2\cdots a_k$
is denoted by
$\tilde {w}:=a_k\cdots a_2a_1$
. A nonempty finite word w is called a palindrome if its reversal
$\tilde {w}$
is equal to w. A square is a nonempty finite word of the form
$ww$
and an overlap is a finite word of the form
$axaxa$
, where
$a \in \mathfrak {A}$
is a letter and
$x\in \mathfrak {A}^*$
is a word. When x is empty, an overlap reduces to a cube
$aaa$
.
A function
$\mu :\mathfrak {A}^*\rightarrow \mathfrak {A}^*$
is called a morphism if
$$ \begin{align*} \mu(w_1w_2)=\mu(w_1)\mu(w_2) \quad\mbox{for } w_1, w_2 \in \mathfrak{A}^*. \end{align*} $$
Here,
$w_1w_2$
is the word formed by concatenating the words
$w_1$
and
$w_2$
. It is straightforward to verify that a morphism is determined by its image on the alphabet
$\mathfrak {A}$
. The length of a word
$w\in \mathfrak {A}^*$
, denoted by
$|w|$
, is the total number of letters it contains, with the empty word having a length of zero. The morphism
$\mu $
is called k-uniform if the length of the word
$\mu (a)$
is k for every letter
$a\in \mathfrak {A}$
and
$\mu $
is nonerasing if
$\mu (a)\neq \epsilon $
for all
$a\in \mathfrak {A}$
. The morphism
$\mu $
is prolongable on the letter
$x_0$
if there exists a nonempty word
$u\in \mathfrak {A}^{+}$
such that
$\mu (x_0)=x_0 u.$
Proposition 2.1. Any nonerasing, prolongable morphism
$\mu $
on the letter
$x_0$
generates a unique infinite word
$\mu ^{\omega }(x_0)$
defined by
$$ \begin{align*} \mu^{\omega}(x_0):=\lim_{n\rightarrow \infty}\mu^n(x_0). \end{align*} $$
Proof. This property can be proved by induction. First, we claim for every
$k\geq 0$
,
$\mu ^k(x_0)$
is a proper prefix of
$\mu ^{k+1}(x_0)$
, and thus ensure the existence of the limit.
For
$k=0$
,
$x_0$
is a proper prefix of
$\mu (x_0)$
from the assumption about
$\mu $
. Assume that for
$k=l$
,
$\mu ^l(x_0)$
is a proper prefix of
$\mu ^{l+1}(x_0)$
and let
$\mu ^{l+1}(x_0)=\mu ^l(x_0)u$
. Then,
$\mu ^{l+2}(x_0)=\mu (\mu ^{l+1}(x_0))=\mu (\mu ^{l}(x_0)u)=\mu ^{l+1}(x_0)\mu (u)$
. This proves the claim.
The morphism
$\mu $
is called square free if, for every word w,
$\mu (w)$
has no square factor whenever w has no square factor. Similarly,
$\mu $
is called overlap free if
$\mu (w)$
has no overlap factor whenever w does not have such a factor.
Definition 2.2. Let
$M\geq 2, N\geq 1$
and
$ m\geq 2$
be integers. For
$n\geq 0$
, write
${n=\sum _{i=0}^{\nu }c_iM^i}$
in base M, where
$0\leq c_i\leq M-1$
for
$0\leq i \leq \nu $
, and represent n as a string of digits
$n=(c_\nu ,\ldots ,c_1,c_0)_M$
. Define
$\mathcal {B}_{M,N}(n)$
to be the integer whose digits in base N are exactly those of n expressed in base M, that is,
$$ \begin{align*} \mathcal{B}_{M,N}(n):=(c_\nu,\ldots,c_1,c_0)_N=\sum_{i=0}^{\nu}c_iN^i. \end{align*} $$
The modulo m version of
$\mathcal {B}_{M,N}$
is
$\mathcal {B}_{M,N,m}$
defined by
$$ \begin{align*} \mathcal{B}_{M,N,m}(n):=\mathcal{B}_{M,N}(n) \ (\textrm{mod}\;m). \end{align*} $$
We use
$\mathcal {B}_{M,N}(\mathbb {N})$
or simply
$\mathcal {B}_{M,N}$
to represent the sequence
$\{\mathcal {B}_{M,N}(n)\}_{n\geq 0}$
. Note that when
$N=1$
,
$\mathcal {B}_{M,1}(n)$
is the sum of digits of n in base M. For more information about these sequences in the case of
$N=1$
, see [Reference Allouche and Shallit3].
Definition 2.3. For integers
$M\geq 2, N\geq 1$
and
$ m\geq 2$
, the morphism
${\mu _{M,N}:\mathfrak {A}_{\omega }\to \mathfrak {A}^*}$
is defined by
$$ \begin{align*} \mu_{M,N}(n):=(Nn)(Nn+1)(Nn+2)\cdots(Nn+M-1)\quad \textrm{for }n\in \mathfrak{A}_{\omega}. \end{align*} $$
Here, each
$Nn+k$
is first treated as a number, allowing for the arithmetic operations. Subsequently, each
$Nn+k$
is interpreted as a single letter, and the resulting expressions are simply concatenated, rather than multiplied. The round brackets are used for visual convenience, not as a letter or meaningful symbol.
Similarly, the morphism
$\mu _{M,N,m}: \mathfrak {A}_{\omega } \to \mathfrak {A}^*$
is defined by
$$ \begin{align*} \mu_{M,N,m}(n) = (Nn \bmod m)(Nn+1 \bmod m)\cdots(Nn+M-1 \bmod m), \end{align*} $$
where the modulo m operation is applied to each
$Nn+k$
before it is treated as a letter.
Lemma 2.4. The sequence
$\mathcal {B}_{M,N}$
satisfies the recurrence relation
$$ \begin{align*} \mathcal{B}_{M,N}(Mn+r)=N\mathcal{B}_{M,N}(n)+r,\quad 0\leq r \leq M-1. \end{align*} $$
Proof. If n has the digits
$(c_p,c_{p-1},\ldots ,c_1,c_0)$
in base M, then the digits of
$Mn+r$
in base M are
$(c_p,c_{p-1},\ldots ,c_1,c_0,r)$
. Applying the definition of
$\mathcal {B}_{M,N}$
yields the desired result.
3 Characterising
$\mathcal {B}_{M,N}$
by the morphism
$\mu _{M,N}$
For a word
$w=x_1x_2\cdots x_{\nu }\in \mathfrak {A}^*$
, and integers a and b, we define an affine transformation of w by
$$ \begin{align*}aw+b:=(ax_1+b)(ax_2+b)\cdots(ax_{\nu}+b)\in \mathfrak{A}^*.\end{align*} $$
Again, each
$ax_k+b$
is treated as a letter and these letters are concatenated.
By the definition of the morphism
$\mu _{M,N}$
, the word
$\mu _{M,N}(0)$
has length M. By induction, for
$n\geq 0$
, the word
$\mu _{M,N}^n(0)$
has length
$M^n$
.
Lemma 3.1. For
$n\geq 1,$
the word
$\mu _{M,N}^n(0)$
has the form
$$ \begin{align} \mu_{M,N}^n(0)=w(w+N^{n-1})(w+2N^{n-1})\cdots(w+(M-1)N^{n-1}), \end{align} $$
where
$w=\mu _{M,N}^{n-1}(0)$
.
Proof. The morphism
$\mu _{M,N}$
is clearly nonerasing, M-uniform and prolongable at
$0$
. By Proposition 2.1,
$\mu _{M,N}^{n-1}(0)$
is a prefix of
$\mu _{M,N}^n(0)$
.
We prove the lemma by induction on n. For
$n=1$
, the lemma is true by the definition of
$\mu _{M,N}$
. Now assume (3.1) is true for all
$n\leq l$
. Then,
$$ \begin{align*} \mu_{M,N}^{l+1}(0)=\mu_{M,N}(\mu_{M,N}^l(0)) = \mu_{M,N}(w(w+N^{l-1})(w+2N^{l-1})\cdots(w+(M-1)N^{l-1})). \end{align*} $$
For
$w=a_1a_2\cdots a_{\nu }$
, consider the affine word
$w+k$
. By the definition of
$\mu _{M,N}$
,
$$ \begin{align*} &\mu_{M,N}(w+k) = \mu_{M,N}((a_1+k)(a_2+k)\cdots(a_{\nu}+k))\\ &\quad= \left\{\begin{matrix} N(a_1+k)&(N(a_1+k)+1)&\cdots &(N(a_1+k)+M-1) \cdot\\ \cdot N(a_2+k)&(N(a_2+k)+1)&\cdots &(N(a_2+k)+M-1) \cdot\\ \vdots &\vdots&\vdots& \vdots \\ \cdot N(a_{\nu}+k)&(N(a_{\nu}+k)+1)&\cdots& (N(a_{\nu}+k)+M-1)\\ \end{matrix} \right.\\ &\quad = (Na_1)(Na_1+1)\cdots(Na_1+M-1)\cdots (Na_{\nu})(Na_{\nu}+1)\cdots (Na_{\nu}+M-1) +Nk. \end{align*} $$
So we have
$\mu _{M,N}(w+k)=\mu _{M,N}(w)+Nk$
and
$$ \begin{align*} \mu_{M,N}^{l+1}(0)=\mu_{M,N}(w)(\mu_{M,N}(w)+N^l)\cdots (\mu_{M,N}(w)+(M-1)N^l). \end{align*} $$
By the induction hypothesis,
$w=\mu _{M,N}^{l-1}(0)$
, so the proof is complete.
For a word
$w\in \mathfrak {A}^*$
, we denote by prefix
$[w]_k$
the prefix of w with length k, provided that w has length at least k.
Lemma 3.2. For
$n,l\geq 0$
,
$$ \begin{align*} \mathrm{prefix}[\mu_{M,N}^{n+l}(0)]_{M^n}=\mu_{M,N}^n(0). \end{align*} $$
Proof. To prove the lemma, we fix n and use induction on l. For
$l=1$
, the result is given by Lemma 3.1. For general l and
$l+1$
,
$\mu _{M,N}^l(0)$
and
$\mu _{M,N}^{l+1}(0)$
also have the same prefix by Lemma 3.1. This completes the proof by induction.
By Proposition 2.1, the limit word
$\mu _{M,N}^{\omega }(0)$
is of infinite length. We can interpret this limit word as a sequence by associating the nth letter with the nth term of the sequence. Throughout the paper, we treat an infinite word as a sequence in this way.
Theorem 3.3. The limit word
$\mu _{M,N}^{\omega }(0)$
is equivalent to the sequence
$\mathcal {B}_{M,N}$
.
Proof. Denote by
$\mu _{M,N}^{\omega }[n]$
the nth term of the sequence
$\mu _{M,N}^{\omega }(0), n\geq 0$
. We will prove that if n has the expansion
$(c_p,c_{p-1},\ldots ,c_1,c_0)_M, c_p\neq 0$
, in base M, then
$$ \begin{align} \mu_{M,N}^{\omega}[n]=\sum_{k=0}^{p}c_kN^k, \end{align} $$
which matches the definition of
$\mathcal {B}_{M,N}(n)$
. We will prove (3.2) by induction on p.
When
$p=0$
, n has only one digit in its base M expansion, that is,
$n=c_0\leq M-1$
. In this case,
$\mu _{M,N}^{\omega }[n]=c_0=c_0N^0$
, as desired.
Suppose n has two digits in its base M expansion, say
$n=(c_1,c_0)_M$
. Since
${n\leq M^2-1}$
, the letter
$\mu _{M,N}^{\omega }[n]$
is contained in prefix
$[\mu _{M,N}^{\omega }]_{M^2}$
. We partition this prefix into blocks of length M. Then, n is in the
$(c_1+1)$
th block, and in the
$(c_0+1)$
th position of this block. By definition of
$\mu _{M,N}$
, the first block of size M of this
$M^2$
length prefix is
$w=012\cdots (M-1)$
. Hence, by Lemma 3.1, the
$(c_1+1)$
th block is the word
$w+c_1N^1$
. Also by Lemma 3.1,
$$ \begin{align*} \mu_{M,N}^{\omega}(w+c_1)=\mu_{M,N}^{\omega}(w)+c_1N. \end{align*} $$
Thus,
$\mu _{M,N}^{\omega }[n]=c_0+c_1N$
since the
$(c_0+1)$
th position of w has value
$c_0$
.
Next, we assume that (3.2) holds for all integers
$n=(c_p,\ldots ,c_1,c_0)_M$
,
$c_p\ne 0$
, for some p. Consider
$n=(c_{p+1},c_p,\ldots ,c_1,c_0)$
, where
$c_{p+1}\ne 0$
. Set
$n_1=(c_p,\ldots ,c_1,c_0)_M$
, so that
$n=n_1+c_{p+1}M^{p+1}$
. Since
$n\leq M^{p+2}-1$
, the letter
$\mu _{M,N}^{\omega }[n]$
is contained in prefix
$[\mu _{M,N}^{\omega }]_{M^{p+2}}$
. Partition this prefix into M blocks each of length
$M^{p+1}$
. Then,
$\mu _{M,N}^{\omega }[n]$
is in the
$(c_{p+1}+1)$
th block and
$\mu _{M,N}^{\omega }[n_1]$
is in the first block. Denote the first block by w. By Lemma 3.1,
$$ \begin{align*} \mu_{M,N}^{\omega}(w+c_{p+1})=\mu_{M,N}^{\omega}(w)+c_{p+1}N^{p+1}, \end{align*} $$
and by the induction hypothesis,
$\mu _{M,N}^{\omega }[n_1]=\sum _{k=0}^{p}c_kN^k$
. Hence,
$\mu _{M,N}^{\omega }[n]$
has the desired form.
We have shown that the sequence
$\mathcal {B}_{M,N}$
is the fixed point of the morphism
$\mu _{M,N}$
. A similar argument shows that
$\mathcal {B}_{M,N,m}$
has the same relationship with the corresponding morphism, namely
$$ \begin{align*} \mu_{M,N,m}^{\omega}(0)=\mathcal{B}_{M,N,m}. \end{align*} $$
The properties of the sequence
$\mathcal {B}_{M,N,m}$
are closely related to the properties of the morphism
$\mu _{M,N,m}$
. For example, if
$\mu _{M,N,m}$
is square free, then the sequence
$\mathcal {B}_{M,N,m}$
has no squares. This is because any square in
$\mathcal {B}_{M,N,m}$
must be contained in some
$M^n$
prefix of
$\mu _{M,N,m}^{\omega }(0)$
, and each such prefix is the image of
$0$
under a finite iteration of
$\mu _{M,N,m}$
. Since
$0$
is certainly square-free and
$\mu _{M,N,m}$
is square-free, it follows that
$\mathcal {B}_{M,N,m}$
is square-free as well.
4 Valuation, palindrome and square
In this section, we fix M and N, and discuss the sequence
$s(n):=\mathcal {B}_{M,N}(n)$
for
$n\geq 0$
, and the modulo sequences
$s_m(n):=\mathcal {B}_{M,N,m}(n)$
for
$n\geq 0$
. We observe that for any k,
$(N+km)^n\equiv N^n$
(mod m). This implies that
$\mathcal {B}_{M,N+km,m}=\mathcal {B}_{M,N,m}$
. Thus, without loss of generality, we can restrict our consideration to the range
$1\leq N\leq m-1$
.
Definition 4.1. For
$M\geq 2$
, the valuation
$\nu _M(n)$
is the highest power d such that
$M^d\mid n$
, but
$M^{d+1}\not \mid n $
. When the base M is clear from the context, we often simplify the notation to
$\nu (n)$
.
The next two lemmas, which are easy to verify, are adapted from [Reference Allouche and Shallit2].
Lemma 4.2. We have
$$ \begin{align*} \nu(n_1+n_2) \begin{cases} =\min\{\nu(n_1),\nu(n_2)\} & \text{if}\ \nu(n_1)\neq \nu(n_2),\\ \geq \nu(n_1) & \text{if } \nu(n_1)=\nu(n_2). \end{cases} \end{align*} $$
Lemma 4.3. For any set of
$2M^p$
consecutive numbers
$\{n_1,n_1+1,\ldots , n_1+2M^p-1\}$
, there exists at least one number in this set with a valuation of p.
Proof. Any
$M^p$
consecutive numbers must contain some
$n_k$
that is a multiple of
$M^p$
. Since
$n_k$
and
$n_k+M^p$
cannot both be multiples of
$M^{p+1}$
, exactly one of
$\nu (n_k)$
and
$\nu (n_k+M^{p})$
equals p.
The next lemma generalises the corresponding result in [Reference Allouche and Shallit2, Reference Cusick and Ciungu6].
Lemma 4.4. We have
$$ \begin{align*} s_m(n)-s_m(n-1)\equiv \begin{cases} 1-(M-1)\nu(n) \pmod m & \text{if}\ N=1, \\ N^{\nu(n)}-(M-1)\dfrac{N^{\nu(n)}-1}{N-1} \pmod m & \text{if}\ N\geq 2. \end{cases} \end{align*} $$
Proof. Suppose n has the digits
$(\ldots ,c_{p+1},c_{p},0,0,\ldots ,0)_M$
in base M, where the string of zeros has length
$p=\nu (n)$
and
$c_{p}\geq 1$
. Then,
$n-1$
has the digits
$(\ldots ,c_{p+1}, c_{p}-1,M-1,M-1,\ldots ,M-1)_M$
. The difference of
$s_m(n)$
and
$s_m(n-1)$
becomes
$$ \begin{align*} s_m(n)-s_m(n-1)\equiv N^{\nu(n)}-(M-1)\sum_{k=0}^{\nu(n)-1}N^k\ (\text{mod}\;m). \\[-44pt] \end{align*} $$
Definition 4.5. For
$n\geq 1$
, n is called a jump if
$s_m(n)-s_m(n-1)\not \equiv 1\pmod m$
.
Lemma 4.6. When
$M-N\equiv 0 \pmod m$
, no n is a jump, and hence
$\{s_m(n)\}_{n\geq 0}$
is the periodic sequence with period m, that is,
$$ \begin{align*} 0,1,2,3,\ldots,m-1,0,1,2,\ldots,m-1,0,1,\ldots. \end{align*} $$
When
$M-N\not \equiv 0 \pmod m$
,
$$ \begin{align*} n \text{ is a jump }\iff \begin{cases} (M-1)\nu(n)\not \equiv 0 \pmod m & \mbox{for } N=1, \\ (M-N)\dfrac{N^{\nu(n)}-1}{N-1}\not\equiv 0 \pmod m & \mbox{for } N\geq 2. \end{cases} \end{align*} $$
In both cases, if
$\nu (n)=0$
, then n is not a jump, and every jump n is a multiple of M.
Proof. We present the proof for the case
$N\geq 2$
, the case
$N=1$
follows a similar argument. For
$N\geq 2$
,
$$ \begin{align*} n \text{ is a jump} & \iff N^{\nu(n)}-(M-1)\frac{N^{\nu(n)}-1}{N-1}\not \equiv 1 \pmod m,\\ & \iff (M-N)\frac{N^{\nu(n)}-1}{N-1}\not \equiv 0 \pmod m. \end{align*} $$
So when
$M-N\equiv 0 \;(\textrm {mod}\;m)$
, no n can be a jump, which is the first assertion. When
$M-N\not \equiv 0 \; (\textrm {mod}\;m)$
and
$\nu (n)=0$
,
${(N^{\nu (n)}-1)}/{(N-1)}$
is always
$0$
, which is the second assertion.
Now, we are ready to prove Theorem 1.1, extending the corresponding result in [Reference Cusick and Ciungu6], and Theorem 1.2.
Proof of Theorem 1.1.
First, suppose there are arbitrarily long palindromes. In the middle of a palindrome with length
$\geq 4$
, we see words of the form
$baab$
or
$cbabc$
, according to whether the palindrome is of even or odd length, where
$a,b,c\in \mathfrak {A}_m$
.
If the case
$baab$
appears, denote the right letter
$a=s_m(n)$
. It follows that
${s_m(n)-s_m(n-1)= a-a = 0 \not \equiv 1 \;(\textrm {mod}\;m)}$
, so n is a jump. According to Lemma 4.6, every two jumps are separated by multiples of M. This implies that
$n+1$
and
$n-1$
are not jumps. Consequently,
$s_m(n+1)-s_m(n)=b-a\equiv 1 \pmod m$
and
$s_m(n-1)-s_m(n-2)=a-b\equiv 1 \pmod m$
. These two equations lead to
$2\equiv 0\pmod m$
or equivalently
$m=2$
, since we assume
$m\geq 2$
.
If the case
$cbabc$
appears, let
$a=s_m(n)$
and distinguish the following two cases.
Case 1:
$M\geq 3$
. Then,
$$ \begin{align*} n \text{ is a jump} & \Longrightarrow n-1 \text{ and } n+1 \text{ are not jumps.}\\ n+1 \text{ is a jump } & \Longrightarrow n \text{ and } n+2 \text{ are not jumps.} \end{align*} $$
If one of
$\{n,n+1\}$
is a jump, then
$n-1$
and
$n+2$
are not jumps, since the minimal distance between jumps is
$M\geq 3$
. As
$n-1$
is not a jump,
$s_m(n-1)- s_m(n-2)= b-c\equiv 1\pmod m$
. Similarly,
$n+2$
being a non-jump implies
$s_m(n+2)- s_m(n+1)=c-b\equiv 1\pmod m$
. Combining these two equations yields
$2\equiv 0\pmod m$
, leading to
$m=2$
.
If neither of
$\{n,n+1\}$
is a jump, we have
$s_m(n)-s_m(n-1)=a-b\equiv 1 \;(\textrm {mod}\;m)$
and
$b-a\equiv 1\;(\textrm {mod}\;m)$
, again resulting in
$m=2$
.
Case 2:
$M=2$
. Consider
$cbabc=s_m(n-2)s_m(n-1)s_m(n)s_m(n+1)s_m(n+2)$
.
Suppose n is even. Since all the jumps are multiples of
$M=2$
,
$n-1$
and
$n+1$
are not jumps. This gives
$b-c\equiv b-a\equiv 1 \pmod m$
, implying
$a\equiv c\pmod m$
. Since n and
$n+2$
are even, and exactly one of them is not a multiple of
$4$
, either
$\nu _M(n)=1$
or
$\nu _M(n+2)=1$
. If
$\nu _M(n)=1$
, by Lemma 4.4,
$$ \begin{align*} s_m(n)-s_m(n-1)=a-b\equiv N-1\;(\textrm{mod}\;m). \end{align*} $$
Combining this with
$b-a\equiv 1\;(\textrm {mod}\;m)$
gives
$N\equiv 0\;(\textrm {mod}\;m)$
, which contradicts our assumption that
$N\in \{1,2,\ldots ,m-1\}$
. If, instead,
$\nu _M(n+2)=1$
, we have
${s_m(n+2)-s_m(n)=c-b\equiv N-1\equiv -1\pmod m}$
, resulting in the same contradiction
${N\equiv 0\pmod m}$
.
If n is odd, then
$n-2,n,n+2$
are all not jumps. This gives
$a-b=c-b\equiv 1\;(\text {mod}\;m)$
. Since one of
$n-1$
or
$n+1$
has valuation
$1$
, applying Lemma 4.4 in either case leads to the contradiction
$N\equiv 0\;(\textrm {mod}\;m)$
.
Combining all the above cases, we have shown that
$m=2$
.
For the converse implication, suppose
$m=2$
. Then,
$N=1$
since we assume
${N\leq m-1}$
. This corresponds to the case of the sum of digits. Following the argument of Cusick et al. [Reference Cusick and Ciungu6], we consider the following two cases.
Case 1: M is odd. We prove by induction that the first
$M^n$
elements of
$\mathcal {B}_{M,1,2}$
are a palindrome. When
$n=1$
, the first M elements are
$0101\cdots 010$
, which is a palindrome.
Assuming the block
$A=\mu ^n_{M,1,2}(0)$
is a palindrome of length
$M^n$
, by Lemma 3.1,
$\mu ^{n+1}_{M,1,2}$
can be expressed as
$A(A+1)\cdots (A+M-1)=A\overline {A}A\overline {A}\cdots A\overline {A}A$
, where
$\overline {A}$
denotes the block whose digits are the complements modulo
$2$
of the digits of A. Since
$\overline {A}$
is also a palindrome, the entire block
$A\overline {A}A\overline {A}\cdots A\overline {A}A$
is a palindrome.
Case 2: M is even. We use induction to show that the first
$M^{2n}$
terms of
$\mathcal {B}_{M,1,2}$
form a palindrome. For
$n=0$
, this holds trivially. Suppose
$A=\mu _{M,1,2}^{2n}(0)$
is a palindrome of length
$M^{2n}$
. By Lemma 3.1,
$$ \begin{align*} \mu_{M,1,(2)}^2(A):=B=\underbrace{A\overline{A}A\overline{A}\cdots A\overline{A}}_{\textrm{length}=M^{n+1}}\underbrace{A\overline{A}A\overline{A}\cdots A\overline{A}}_{\text{length}=M^{n+1}}\cdots \underbrace{A\overline{A}A\overline{A} A\cdots\overline{A}}_{\textrm{length}=M^{n+1}}. \end{align*} $$
Direct computation reveals that the reversal of the word B of length
$M^{2n+2}$
is equal to itself, confirming that B is a palindrome.
Proof of Theorem 1.2.
First, consider a single letter square. By Lemma 4.4, we see that
$s_m(n-1)s_m(n)$
is a square
$aa$
if and only if
$$ \begin{align*} s_m(n-1)\equiv s_m(n) & \iff N^{\nu(n)}-(M-1)\frac{N^{\nu(n)}-1}{N-1}\equiv 0 \pmod m,\\ & \iff (M-N)\frac{N^{\nu(n)}-1}{N-1} \equiv1 \pmod m. \end{align*} $$
Here,
$\nu (n)$
can take any nonnegative integer value and
$\{{(N^k-1)}/{(N-1)}\}_{k\geq 1}$
is periodic in
$\mathbb {Z}_m$
, so the result follows.
For the second part of the theorem, first consider the case
$M=N$
. By Lemma 4.6,
$\mathcal {B}_{M,M,m}$
is periodic; therefore, it contains arbitrarily large squares. It remains to consider the case
$N<M$
. We prove that the sequence
$\mathcal {B}_{M,N}$
has arbitrarily large squares, implying that the modulo sequence
$\mathcal {B}_{M,N,m}$
also contains corresponding large squares.
Consider the word
$$ \begin{align*} w_1=s(N)s(N+1)\cdots s(M-1)s(M)\cdots s(2M-N-1). \end{align*} $$
For a nonnegative integer k such that
$N{\kern-1pt}+{\kern-1pt}k {\kern-1pt}\leq{\kern-1pt} M{\kern-1pt}-{\kern-1pt}1$
, the base M representation of
$N{\kern-1pt}+{\kern-1pt}k$
is
$(\ldots ,0,0, N+k)_M$
. By definition,
$s(N+k)=N^0(N+k)=N+k$
. The base M representation of
$M+k$
is
$(\ldots ,0,0,1,k)_M$
. By definition,
$s(M+k)=N^11+N^0k=N+k$
. From these observations,
$s(N){\kern-1pt}={\kern-1pt}s(M){\kern-1pt}={\kern-1pt}N,s(N{\kern-1pt}+{\kern-1pt}1){\kern-1pt}={\kern-1pt}s(M{\kern-1pt}+{\kern-1pt}1){\kern-1pt}={\kern-1pt}N{\kern-1pt}+{\kern-1pt}1,\ldots ,s(M-1)= s(2M-N-1)=M-1$
. Thus,
$w_1$
is a square of length
$2(M-N)$
.
In general, consider the first
$M^n$
elements in
$\mathcal {B}_{M,N}$
. By Lemma 3.1, this block has the form
$$ \begin{align*} \mu_{M,N}^n(0)=w (w+N^{n-1})(w +2N^{n-1})\cdots (w+NN^{n-1})\cdots (w+(M-1)N^{n-1}). \end{align*} $$
Let
$A_n$
be the suffix factor of
$\mu _{M,N}^n(0)$
from the
$(N+1)$
th sub-block to the Mth sub-block, that is,
$$ \begin{align*} A_n=(w+N^n)\cdots (w+(M-1)N^{n-1}). \end{align*} $$
By Lemma 3.1, the
$M^n$
block of elements following
$\mu _{M,N}^n(0)$
can be expressed as
$$ \begin{align*} \mu_{M,N}^n(0)+N^n=(w+N^n)(w+N^{n-1}+N^n)\cdots(w+(M-1)N^{n-1}+N^n). \end{align*} $$
Let
$B_n$
be the prefix factor of
$\mu _{M,N}^n(0)+N^n$
, from the first block to the
$(M-N)$
th block, that is,
$$ \begin{align*} B_n=(w+N^n)(w+N^{n-1}+N^n)\cdots(w+(M-N-1)N^{n-1}+N^n). \end{align*} $$
It can be seen that
$A_n=B_n$
and the concatenation
$A_nB_n$
forms a square of size
${2(M-N)N^{n-1}}$
. This completes the proof.
5 Overlaps and periods
In this section, we prove Theorem 1.3, which is a partial extension of the corresponding theorem in [Reference Cusick and Ciungu6].
Proof of Theorem 1.3.
In the definition of
$\mathcal {B}_{M,N,m}$
, we need
$M\geq 2$
. Assume
$\mathcal {B}_{M,N,m}$
contains some overlap
$bBB$
, where
$b\in \mathfrak {A}_m$
,
$B\in \mathfrak {A}^+_{m}$
and B ends with b. We also assume this overlap is the foremost one, meaning that any other overlap cannot begin before the position of letter b, and among all the overlaps that begin with b,
$bBB$
is the shortest one.
First, we claim that the word B cannot contain a jump. Suppose in contrast that some n is a jump and the letter
$s_m(n)$
is in the left word B. Then,
$n+|B|$
is also a jump in the second word B, because B ends with b. By Lemma 4.6, every jump is a multiple of M. Since
$M\mid n$
and
$M\mid (n+|B|)$
, it follows that
$M\text { divides }|B|$
. If
$|B|=pM$
and
$b=s_m(i)$
, then
$$ \begin{align*} bBB=s_m(i)s_m(i+1)\cdots s_m(i+pM)s_m(i+pM+1)\cdots s_m(i+2pM) \end{align*} $$
and
$$ \begin{align*} s_m(i+n)=s_m(i+pM+n), \quad 0\leq n \leq pM. \end{align*} $$
Suppose
$i=qM+r$
, where
$0\leq r \leq M-1$
. For
$n=jM$
with
$0\leq j \leq p$
, we have
$s_m(qM+r+jM)=s_m(qM+r+pM+jM)$
. By the recurrence relation in Lemma 2.4,
$$ \begin{align*} Ns_m(q+j)\equiv Ns_m(q+p+j)\pmod m, \quad 0\leq j\leq p. \end{align*} $$
Since we assume
$\gcd (N,m)=1$
, multiplying by the inverse of N on both sides gives
$s_m(q+j)\equiv s_m(q+p+j)\pmod m$
for
$0\leq j\leq p$
. This means the word
$$ \begin{align*} s_m(q)s_m(q+1)\cdots s_m(q+p)s_m(q+p+1)\cdots s_m(q+2p) \end{align*} $$
is an overlap that begins at or before b but is strictly shorter than
$bBB$
, which is a contradiction.
Since B cannot contain a jump, neither can
$bBB$
. By Lemma 4.3,
$|BB|<2M$
and
$$ \begin{align*} s_m(j+1)\equiv s_m(j)+1\pmod m, \quad i\leq j\leq i+2|B|-1. \end{align*} $$
Combining this with
$s_m(i)\equiv s_m(i+|B|)\equiv s_m(i)+|B|\pmod m$
, we see that m divides
$|B|$
. However, this contradicts
$|B|<M$
and
$m\geq M$
.
Remark 5.1. When
$N=1$
, the results in [Reference Allouche and Shallit2, Reference Cusick and Ciungu6] show that
$\mathcal {B}_{M,1,m}$
contains no overlaps if and only if
$m\geq M$
.
When
$N\geq 2$
, there are some
$m\geq M$
which result in overlaps. For example:
-
• in
$\mathcal {B}_{3,2,4}$
,
$s(0)\cdots s(18)=0,1,2,2,3,0,0,1,2,0,1,2,2,3,0,0,1,2,0$
; -
• in
$\mathcal {B}_{4,3,6}$
,
$s(48)\cdots s(64)=3,4,5,0,0,1,2,3,3,4,5,0,0,1,2,3,3$
.
However,
$\mathcal {B}_{2,3,6}$
has no overlaps up to
$2^{10}$
and
$\mathcal {B}_{3,4,10}$
has no overlaps up to
$3^{6}$
. These examples suggest that the converse of Theorem 1.3 may not be true, that is, there might be some overlap free sequences with
$\gcd (m,N)\neq 1$
.
Theorem 5.2. For
$N\geq 2$
, if
$\mathcal {B}_{M,N,m}$
is ultimately periodic, then for some integer t,
$N^t(N-1)(M-N)\equiv 0\pmod m$
.
Proof. The case
$N=1$
has been investigated by [Reference Cusick and Ciungu6]. Assume that
${B}_{M,N,m}=\{s_m(n)\}_{n\geq 0}$
is ultimately periodic, starting from index
$N_0$
. Let p be the shortest period and
${p=M^tq}$
, where
$M\nmid q$
. Take
$\alpha $
sufficiently large so that
$n=M^{\alpha m}>N_0$
and
$\alpha m>t+1$
. By periodicity,
$$ \begin{align*} &s_m(n+p)=s_m(n+Mp) \quad\mbox{and}\quad s_m(n+p-1)=s_m(n+Mp-1)\\ & \Longrightarrow s_m(n+p)-s_m(n+p-1)=s_m(n+Mp)-s_m(n+Mp-1). \end{align*} $$
By Lemma 4.4,
$$ \begin{align*} N^{\nu(n+p)}-(M-1)\frac{N^{\nu(n+p)}-1}{N-1}\equiv N^{\nu(n+Mp)}-(M-1)\frac{N^{\nu(n+Mp)}-1}{N-1} \;(\text{mod}\;m). \end{align*} $$
Since
$p=M^tq$
and
$n=M^{\alpha m}$
with
$\alpha m>t+1$
, we have
$\nu (n+p)=t$
and
$\nu (n+Mp)=t+1$
. After simplification, we find
$N^t(N-1)(M-N)\equiv 0\;(\text {mod}\;m)$
.
6 Future research directions
The following remarks suggest further problems concerning the sequences
$\mathcal {B}_{M,N,m}$
.
-
(1) Theorem 1.2 provides no information regarding the presence of squares in
$\mathcal {B}_{M,N,m}$
when
$N>M$
. -
(2) Numerical experiments suggest that when
$m<M$
,
$\mathcal {B}_{M,N,m}$
always contains overlaps for
$N\geq 2$
. However, we currently lack a simple method to locate these overlaps. Using Mathematica, the author has examined the first
$5001$
terms of the sequence
$\mathcal {B}_{4,3,6}$
; in the range from
$\mathcal {B}_{4,3,6}(0)$
to
$\mathcal {B}_{4,3,6}(5000)$
, no repeating pattern was observed. This suggests that the sequence
$\mathcal {B}_{4,3,6}$
mentioned in Remark 5.1 may not be ultimately periodic, yet contains overlaps. How to find all sequences that contain overlaps is still unclear. -
(3) Since the digit sum sequence provides a partition scheme for the Prouhet–Tarry– Escott problem [Reference Bolker, Offner, Richman and Zara5], we hope that some
$\mathcal {B}_{M,N,m}$
inherit similar properties, particularly for
$m=M$
and
$\gcd (N,M)=1$
.
Acknowledgement
I would like to thank the anonymous referee for a careful reading of the paper.
