# Superpolynomial period lengths of the winning positions in the subtraction
game

István Miklós  Logan Post

###### Abstract

Given a finite set of positive integers, $A$, and starting with a heap of $n$
chips, Alice and Bob alternate turns and on each turn a player chooses $x\in
A$ with $x$ smaller or equal than the current number of chips and subtract $x$
chips from the heap. The game terminates when the current number of chips
becomes smaller than $\min\\{A\\}$ and no moves are possible. The player who
makes the last move is the winner. We can define $w^{A}(n)$ to be $1$ if Alice
has a winning strategy with a starting heap of $n$ chips and $0$ if Bob has a
winning strategy. By the Pigeonhole Principle, $w^{A}(n)$ becomes periodic,
and it is easy to see that the period length is at most an exponential
function of $\max\\{A\\}$. The typical period length is a linear function of
$\max\\{A\\}$, and it is a long time open question if exponential period
length is possible.

We consider a slight modification of this game by introducing an initial seed
$S$ that tells for the few initial numbers of chips whether the current or the
opposite player is the winner. In this paper we show that the initial seed
cannot change the period length of $w^{A}(n)$ if the size of $A$ is $1$ or
$2$, but it can change the period length with $|A|\geq 3$. Further, we exhibit
a class of sets $A$ of size $3$ and corresponding initial seeds such that the
period length becomes a superpolynomial function of $\max\\{A\\}$.

##  1 Introduction

Game Theory is the theory of interactive situations or games among rational
decision-makers or players in which the decisions of each player are
contingent on the decisions of the others. Combinatorial Game Theory considers
games with perfect information and without elements of chance. That is, at all
times during the game, players have perfect information about the state of the
game, and further, the moves in the game are entirely decided by the players,
there is no elements of chance once the game has begun. We further require
that a combinatorial game must end with a clear winner.

An example of a two-player combinatorial game is the subtraction game. For a
finite set $A\subset\mathbb{N}_{+}$, the _$A$ -subtraction game_ is a two-
player combinatorial game which proceeds as follows. We begin with heap of
$n$-chips. Players Alice and Bob alternate turns, and on each turn a player
chooses $x\in A$ with $x\leq n$, and subtracts $x$ chips from the heap,
leaving $n-x$ remaining. The game terminates when $n<\min(A)$ and thus no
moves are possible. The player who makes the last move is the winner. In
general we consider a fixed $A$ and ask for which values of $n$ each player
has a winning strategy. Note that when Alice makes a move $x$, Bob and Alice
switch roles and we reduce to the $n-x$ game.

The subtraction game is also in the large class of combinatorial games called
_impartial games_. An impartial game is a combinatorial game in which the
allowable moves depend only on the position and not on which of the two
players is currently moving, and where the payoffs are symmetric. It is also
in _normal mode_ , meaning that the winner is who can make the last possible
move. The Sprague-Grundy theorem [11, 8] says that any impartial game in
normal mode is equivalent with a Nim game, which is the disjunctive sum of
$\mathbb{N}_{+}$-subtraction games. Despite this reduction, we know little
about the patterns of the winning positions of the subtraction game.

For any finite set $A\subset\mathbb{N}_{+}$, a dynamic programming recursion
can compute which player has the winning strategy starting with a pile of size
$n$. Simple reasoning by Pigeonhole Principle shows that the pattern of
winning positions will eventually become periodic as $n$ takes all possible
positive integers, and the period length cannot be longer than $2^{\max(A)}$.
It is a long time open question if exponential period lengths exist in the
substraction game. Althöfer and Bültermann conjectured that superpolynomial
period lengths might exist if $|A|\geq 5$ [1].

For some $A$, the subtraction game has a pre-period in the winning positions
before becomeing periodic, that is, a pattern of winning positions for small
$n$ that is never repeated. We also know little about for which $A$ the
subtraction game has a pre-period and for which $A$ it is _purely periodic_ ,
that is, has no pre-period.

In this paper, we generalize the subtraction game by modifying who is the
winner for some small $n$. We call this initial pattern a _seed_. We give a
complete analysis of subtraction games with seeds for $|A|=1$ and $2$. We
prove that for all seeds the game has no pre-period if $|A|=1$ or $2$. For
$A=\\{a\\}$, the period length is $2a$. For $A=\\{a,b\\}$, the period length
can be any divisor of $a+b$, with a few exceptions. If $a$ and $b$ are
relatively prime then the period can be any divisor except $1$, $4$, and $6$.
We also compute the number of possible distinct period lengths over all seeds.
When $|A|=3$, then there might be pre-periods. We give characterisations of
period and pre-period lengths for a large class of possible sets $A$. Finally,
we show that superpolynomial period lengths exist already when $|A|=3$.

##  2 Preliminaries

######  Definition 1.

Let $w^{A}(n)$ be the winning indicator function of $A$, so $w^{A}(n)=1$ if
Alice (the first player) has a winning strategy and $w^{A}(n)=0$ if Bob has a
winning strategy.

For brevity, we may use $w(n)$ to refer to $w^{A}(n)$. By definition, $w$
satisfies the recurrence relation

$w(n)=\begin{cases}1&w(n-x)=0\text{ for some }x\in A\\\ 0&w(n-x)=1\text{ for
all }x\in A\end{cases}=1-\min\\{w(n-x)\mid x\in A\\}.$ (1)

This follows from the observation that for a particular $n$, Alice is in a
winning position if she can subtract some $x$ to give Bob a losing position.
Otherwise, she will certainly move to a winning position for Bob, and he will
win. We can then also describe $w^{A}$ as the lexicographically least sequence
in $n$ such that for all $x\in A$, $w(n)=0\implies w(n+x)=1$.

Note that it is natural to define $w(0):=0$, because if a player has
previously made a move to $0$, then the next player will lose. Therefore, to
satisfy recurrence relation (1) we shall define $w(n):=1$ for all $n<0$.

To describe an entire sequence $\\{w^{A}(n)\\}_{n=0}^{\infty}$ of winning
positions, abbreviated as $\\{w^{A}\\}$, we use exponents to denote repeated
values. A noted example in [3, p. 86] is the set $\\{2,4,7\\}$. We find that
$\\{w^{\\{2,4,7\\}}\\}=0,0,1,1,1,1,0,1,1,0,\ldots$, which can be abbreviated
to
$\\{w^{\\{2,4,7\\}}\\}=0^{2}1^{4}01^{2}0\ldots=0^{2}1^{2}(1^{2}0)^{\infty}$.
In this example we have $w(0)=0$, $w(1)=0$, and $w(2)=1$. This follows from
the rule that if $n<2$, Alice is unable to move, but at $n=2$, Alice may
subtract 2 chips and win the game. Similarly $w(6)=0$ because for any move
Alice makes, Bob can respond with a winning move. In general, if we present a
prefix of $\\{w^{A}\\}$ of length $\ell$, we use “$\underset{\ell}{\ldots}$”
to indicate the continuation of the sequence and clarify the prefix’s length
for the reader. For example,
$\\{w^{\\{2,4,7\\}}\\}=0^{2}1^{4}\underset{6}{\ldots}$ may indicate that the
first $6$ values of $w$ are given and the rest are not yet derived. Throughout
the paper, we refer to $\alpha=\max(A)$. The following example is an easy
generalization of one in [3, p. 103].

######  Example 2.1.

Suppose $A=\\{1,2,\ldots,\alpha\\}$. Then
$w^{A}(n)=\begin{cases}0&(\alpha+1)\mid n\\\ 1&\text{otherwise}\end{cases}$,
so $\\{w^{A}\\}=\big{(}\,01^{\alpha}\,\big{)}^{\infty}$.

###### Proof.

Suppose $n=k(\alpha+1)$. We claim Bob has a winning strategy. If Alice
subtracts $x$, then Bob can subtract $\alpha+1-x$, reducing to
$(k-1)(\alpha+1)$ chips. Bob can repeat this until there are $(0)(\alpha+1)$
chips, winning the game. Suppose $n=k(\alpha+1)+y$. Then Alice has a winning
strategy. She may $y$ chips, reducing the game to $k(\alpha+1)$, then play as
Bob would by countering each of his moves $x$ with $\alpha+1-x$. ∎

We define a notation for repeated concatenation of strings. By analogy to
addition, for strings $w_{1},w_{2},\ldots w_{k}$, let

$\sum_{i=1}^{k}w_{i}=w_{1}\circ w_{2}\circ\ldots\circ w_{k}.$

This notation satisfies the equality
$\left\lvert\sum_{i=1}^{k}w_{i}\right\rvert=\sum_{i=1}^{k}\left\lvert
w_{i}\right\rvert$. Recall that sequence concatenation is not a commutative
operation, although the usual summation of numbers is one. When we use a
summation symbol for a concatenation of strings, we will always use an index
that defines the order of the concatenation.

######  Definition 2.

A sequence $\\{w^{A}(n)\\}$ is _periodic_ over $p$ if there is some
$N\in\mathbb{N}$ such that for all $n\geq N$, $w^{A}(n)=w^{A}(n+p)$. We say
the _period_ of $w^{A}(n)$ is the least such $p$ and the _preperiod_ is the
least such $N$. We denote these by $\operatorname{Per}(A)$ and
$\operatorname{PrePer}(A)$ respectively.

In Example 2.1 we have $\operatorname{Per}(\\{1,\ldots,\alpha\\})=\alpha+1$
and $\operatorname{PrePer}(\\{1,\ldots,\alpha\\})=0$. We also observe that
$\operatorname{Per}(\\{2,4,7\\})=3$ and $\operatorname{PrePer}(\\{2,4,7\\}=4$,
because for all $n\geq 4$ it holds that $w(n)=w(n+3)$.

######  Lemma 2.2.

For any finite set $A\subset\mathbb{N}_{+}$, $\\{w^{A}(n)\\}$ is periodic.

###### Proof.

To prove this fact, we define a new tool called the vector of previous values.
Given $A\subset\mathbb{N}_{+}$, let

$\vec{v}^{A}(n):=\left\langle
w(n-\alpha),\ldots,w(n-2),w(n-1)\right\rangle=\left\langle
v_{1},\ldots,v_{\alpha}\right\rangle\in\mathbb{Z}_{2}^{\alpha}.$ (2)

As shown above, $\vec{v}(n)$ will be an element of $\mathbb{Z}_{2}^{\alpha}$.
Next, we use the recurrence relation to define a function
$\mathcal{F}:\mathbb{Z}_{2}^{\alpha}\to\mathbb{Z}_{2}^{\alpha}$.

$\mathcal{F}(\vec{v}):=\left\langle
v_{2},v_{3},\ldots,v_{\alpha-1},1-\min\\{v_{\alpha-x}\mid x\in
A\\}\right\rangle$ (3)

Thus by Recurrence 1, we have
$\vec{v}(n+1)=\mathcal{F}\big{(}\vec{v}(n)\big{)}$. Note that
$\mathbb{Z}_{2}^{\alpha}$ has $2^{\alpha}$ elements, so by the Pigeonhole
Principle there must be distinct integers $0\leq N<M\leq 2^{\alpha}$ such that
$\vec{v}(N)=\vec{v}(M)$. Therefore for all $n\geq N$, we have the equality

$\vec{v}(n)=\mathcal{F}^{n-N}\big{(}\vec{v}(N)\big{)}=F^{n-N}\left(\vec{v}(M)\right)=\vec{v}(n+M-N).$

Therefore a single repeated vector guarantees periodicity of length $M-N$. ∎

Indeed this Lemma often fails for infinite set games.

######  Proposition 2.3.

For some $k\geq 2$, suppose $A=\\{n^{k}\mid n\in\mathbb{N}\\}$. Then the
sequence $w^{A}$ is not periodic.111For $k=2$, the losing positions of this
sequence are in the Online Encyclopedia of Integer Sequences [10, A030193]

###### Proof.

We first show there must be infinitely many losing positions by contradiction.
Suppose there are $\ell$ losing positions. Among all integers
$\leq(2\ell)^{k}$, there are $2\ell$ elements of $A$. Because each winning
position can be expressed as a losing position plus some $x\in A$, there can
be combinatorially at most $2\ell^{2}$ distinct winning positions
$\leq(2\ell)^{k}$. This implies $\ell+2\ell^{2}\geq(2\ell)^{k}$, which
contradicts finiteness of losing positions. Thus $\\{w^{A}\\}$ has infinitely
many zeros. If we suppose $w$ is periodic after some $N$ with period $p$, then
there is some $n>N$ with $w(n)=0$. This implies that after $p^{k-1}$ periods,
we will have $w(n+p^{k})=0$, contradicting $p^{k}\in A$. ∎

The proof of Lemma 2.2 gives the result that for any finite $A$,
$\operatorname{PrePer}(A)+\operatorname{Per}(A)\leq 2^{\alpha}$. We can get a
slightly tighter bound for dense sets, but no less than exponential in
$\alpha$.

######  Theorem 2.4.

For $A=\\{a_{1},a_{2},\ldots,\alpha^{\prime},\alpha\\}$, let
$\beta=\min(\alpha,a_{1}+\alpha^{\prime})$. Then

$\operatorname{PrePer}(A)+\operatorname{Per}(A)\leq(\beta+1)2^{\alpha-|A|}.$
(4)

###### Proof.

First, we show that there cannot be a string of ones longer than $\beta$ in
$\\{w^{A}\\}$. If some $w(n)$ is preceded by a string of $\alpha$ ones, then
$w(n-x)=1$ for all $x\in A$, so $w(n)=0$. Alternately, if $n$ is preceded by a
string of $a_{1}+\alpha^{\prime}$ ones, this implies that in particular
$w(n-a_{1})=1$, and $(n-a_{1})$ is preceded by $\alpha^{\prime}$ ones. This
means that for all $a_{i}\in A$ except for $\alpha$, we have
$a_{i}\leq\alpha^{\prime}$ and therefore $w(n-a_{1}-a_{i})=1$. Because
$w(n-a_{1})=1$, by process of elimination we conclude that
$w(n-a_{1}-\alpha)=0$. Therefore $w(n-\alpha)=1$. Thus $w(n-x)=1$ for all
$x\in A$, so $w(n)=0$. Hence $\beta$ bounds the number of consecutive ones in
$\\{w^{A}\\}$.

Now, let $n_{i}$ be the $i^{th}$ zero in $\\{w^{A}\\}$. By the proof above
$n_{i}-n_{i-1}\leq\beta+1$, so $n_{i}\leq i(\beta+1)$. In order to have
$w(n_{i})=0$, we require that within the vector $\vec{v}(n_{i})$, the
${\alpha-x}^{\text{th}}$ entry $\vec{v}(n_{i})_{\alpha-x}=1$ for all $x\in A$.
This fixes $|A|$ entries, so there are $2^{\alpha-|A|}$ possibilities for
$\vec{v}(n_{i})$. By the Pigeonhole Principle, there is some repeated vector
$\vec{v}_{n_{N}}=\vec{v}_{n_{M}}$ for some $N<M\leq 2^{\alpha-|A|}$, and
$n_{M}\leq(\beta+1)2^{\alpha-|A|}$. This proves the claim. ∎

A similar argument can give a bound of $(|A|+1)2^{\alpha-|A|}$. Using the
approach from Proposition 2.3, we can see that there are at most
$(2^{\alpha-|A|}-1)\cdot(|A|)$ ways to express a winning position less than
$n_{2^{\alpha-|A|}}$, which yields this improved constant.

###  2.1 Initial Seed

We can generalize the subtraction game by changing the end state of the game.
In [1, (ix)], Althöfer and Bülterman suggest that this variant “may be
interpreted as simulations of certain computing devices,” and pose open
questions about this game. Through the analysis in Sections 3, 4, and 6 we
find that this generalization also provides insights into the original game.
We begin with two motivating examples.

######  Example 2.5.

The _Miseré_ mode of the $A$-subtraction game is the same game except the
player to make the last move is the loser.

######  Example 2.6.

The _Greedy_ mode of the $A$-subtraction game is the same game except a player
may take $x>n$ chips, thereby making the heap negative. The game concludes
when then heap is negative, and the player to make the last move is the
winner. This is close to the version studied in [1].222The exact game studied
in [1] is the same but has $w(0):=0$; this cannot be generated from a seed as
there is no function $w:\mathbb{Z}\to\\{0,1\\}$ satisfying recurrence 1 for
all $n\in\mathbb{N}$. For example, if $A=\\{1,3\\}$, we desire $w(0)=0$,
$w(1)=1$, and $w(2)=1$. Any choice of $w(-1)$ leads to a contradiction.

Notice that for $n\geq\alpha$, the recurrence relation for both of these games
is the same as Equation (1), but the ultimate sequence of winning positions
may be different because of the players’ final goals. We can account for this
by adjusting negative values of $w(n)$, then allowing the recurrence relation
to proceed for $n\geq 0$.

######  Definition 3.

Define the _seed_ $S$ of a game to be the value of $\vec{v}(0)$, determining
$w(n)$ for $n\in[-\alpha,0)$. The recurrence relation follows, so
$\vec{v}(n):=\mathcal{F}^{n}(S)$, with $\mathcal{F}$ defined in Equation (3).
We define $\\{w^{A,S}(n)\\}_{n=0}^{\infty}$ to be the sequence generated by
seed $S$. Further define $\operatorname{Per}(A,S)$ and
$\operatorname{PrePer}(A,S)$ to be the period and preperiod of
$\\{w^{A,S}\\}$.

For ease of notation, we interpret $S$ more generally as the negative values
of $w^{A}(n)$. Ordinarily $|S|\leq\alpha$, and if not then $\vec{v}^{A,S}(0)$
is taken to be the last $\alpha$ elements of $S$. Similarly, if $|S|<\alpha$,
then we presume $S$ to be preceded by infinitely many $1$’s, so let
$w^{\\{A,S\\}}:=w^{\\{A,1^{\alpha-|S|}S\\}}$. It follows from this convention
and Definition 2 that
$\operatorname{Per}(A)=\operatorname{Per}(A,1^{\alpha})$, and thus in general
we refer to a game with seed $1^{\alpha}$ as having ‘no seed’.

In Example 2.5, we observe that $S=0^{\min(A)}1^{\alpha-\min(A)}$ generates
the sequence of winning positions for the Miseré mode of the subtraction game,
and in Example 2.6, we see that $S=0^{\alpha}$ generates the sequence for the
Greedy game. By considering all seeds in $\mathbb{Z}_{2}^{\alpha}$ we describe
a larger class of games. Some seeds generate games which are similar or
identical to the original, while some are dramatically different. For example,
the Miseré and Greedy modes cause only a translation in $w(n)$ by $\min(A)$
and $\alpha$ respectively.

Notice that Results 2.2 \- 2.4 consider the recurrence in generality and
therefore hold for all seeds. In order to characterize $w^{A,S}$ over all
seeds, we provide the following notation for the set of all winning sequences
and their periods.

$\displaystyle\mathcal{W}^{A}$
$\displaystyle:=\Big{\\{}\\{w^{A,S}(n)\\}_{n=0}^{\infty}\mid
S\in\\{0,1\\}^{\alpha}\Big{\\}}$ (5) $\displaystyle\mathcal{P}^{A}$
$\displaystyle:=\Big{\\{}\operatorname{Per}(A,S)\mid
S\in\\{0,1\\}^{\alpha}\Big{\\}}$ (6)

Thus $\mathcal{W}^{A}$ is the set of all $(A,S)$ games, i.e. all sequences
satisfying recurrence relation 1, and $\mathcal{P}^{A}$ is the set of their
periods. For general $A$, a natural open question is to find
$\max(\mathcal{P}^{A})$.

###  2.2 Properties of Subtraction Games.

If the elements of $A$ are not coprime, we can interpret the sequence $w$ as
multiple games $(w)_{i}$ proceeding in parallel. Formally, choose finite
$A\subset\mathbb{N}_{+}$ with maximum $\alpha$ and $\gcd$ $1$, and denote
$kA=\\{kx\mid x\in A\\}$. Then given some seed $S$ with $|S|=k\alpha$, where
$S=\left\langle S(m)\mid m\in\\{0,\ldots,k\alpha-1\\}\right\rangle$, we break
$S$ into classes modulo $k$ by defining $S_{i}$ for $i\in\\{0,\ldots k-1\\}$
such that for all $m\in\\{0,\ldots\alpha-1\\}$, we have $S_{i}(m):=S(mk+i)$.
Thus $|S_{i}|=\alpha$ and $S$ can be decomposed into $S_{i}$’s. By analogy,
similarly define $(w^{kA,S})_{i}(m):=w^{kA,S}(mk+i)$. We observe that
$\\{(w^{kA,S})_{i}(m)\\}_{m=0}^{\infty}$ depends only on $S_{i}$.

######  Proposition 2.7 (Multiplicative Linearity).

For any $k\in\mathbb{N}$, set $A$, and seed $S$ with $|S|=k\alpha$, then

$(w^{kA,S})_{i}(m)=w^{A,S_{i}}(m)$ (7)

So if $S_{i}=S_{0}$ for all $i\in\\{0,\ldots,k-1\\}$, then
$\operatorname{Per}(kA,S)=k\operatorname{Per}(A,S_{0})$ and
$\operatorname{PrePer}(kA,S)=k\operatorname{PrePer}(A,S_{0})$. This condition
holds for $S=1^{k\alpha}$, implying that
$\operatorname{Per}(kA)=k\operatorname{Per}(A)$ and
$w^{kA}(n)=w^{A}(\left\lfloor n/k\right\rfloor)$. $\square$

Proposition 2.7 follows by applying the recurrence relation to
$(w^{kA,S})_{i}(m)$.

######  Definition 4 (Extension).

Choose set $A\subset\mathbb{N}_{+}$ and seed $S$. We say
$b\in\mathbb{N}\setminus A$ is an _extension_ of $(A,S)$ if
$w^{A\cup\\{b\\},S}=w^{A,S}$.

######  Proposition 2.8 (Better Definition of Extension).

For $b\in\mathbb{N}\setminus A$ is an extension of $(A,S)$ if and only if for
all $n\in\mathbb{N}$ it holds that $w^{A,S}(n)=0\implies w^{A,S}(n-b)=1$.

###### Proof.

Let $B=A\cup\\{b\\}$. Suppose it holds that $w^{A,S}(n)=0\implies
w^{A,S}(n-b)=1$, but $w^{B,S}\neq w^{A,S}$, and choose the least
$n\in\mathbb{N}$ where they differ. If $w^{A,S}(n)=1$, then for some $x\in A$,
$w^{A,S}(n-x)=w^{B,S}(n-x)=0$, so $w^{B,S}(n)=1$. If instead $w^{A,S}(n)=0$,
then $w^{A,S}(n-b)=w^{B,S}(n-b)=1$, so indeed $w^{B,S}=0$, contradicting that
$w^{B,S}\neq w^{A,S}$.

In the other direction, suppose $w^{B,S}=w^{A,S}$ but there is some $n$ with
$w^{B,S}(n)=w^{A,S}(n)=0$ and $w^{B,S}(n-b)=w^{A,S}(n-b)=0$. This contradicts
the recurrence relation for $B$. ∎

This means that we can identify redundant elements of a set $A$ if they are
extensions of the other elements. The following proposition is a digression,
but

######  Proposition 2.9.

For all finite or infinite sets $A\subseteq\mathbb{N}_{+}$, if
$\operatorname{PrePer}(A)=0$ and $\operatorname{Per}(A)=p$, then
$w^{A}=w^{A\cap\\{1,\ldots,p\\}}$, so every element of $A$ greater than $p$ is
redundant as an extension of $A\cap\\{1,\ldots,p\\}$. There is no analogous
statement for sequences with preperiods; for example
$\\{w^{\\{1,4,7,\ldots\\}}\\}=0(101)^{\infty}$, but no other set generates
that sequence.

###### Proof.

For the first statement, let $B=A\cap\\{1,\ldots,p\\}$. Suppose for the sake
of contradiction there is some least $n$ such that $w^{A}(n)\neq w^{B}(n)$. By
the recurrence relation it must be that $w^{A}(n)=1$ and $w^{B}(n)=0$, and
$w^{A}(n-a)=0$ for some $a\in A\setminus B$. By our definitions $a>p$ so
$n>p$. Then $w^{B}(n-p)=w^{A}(n-p)=1$ so there is some $x\in B$ such that
$w^{B}(n-p-x)=0$. Therefore $w^{B}(n-x)=0$, so $w^{B}(n)=1$, a contradiction.
For the second statement, suppose $w^{A}=0(101)^{\infty}$. Suppose $x\equiv
0\pmod{3}$. Then $w^{A}(2)=w^{A}(2+x)=0$, so $x\notin A$. Suppose $x\equiv
2\pmod{3}$. Then $w^{A}(0)=w^{A}(x)=0$, so $x\notin A$. Therefore $A\subseteq
3\mathbb{N}+1=\\{1,4,7,\ldots\\}$. It is easy to see that $A=3\mathbb{N}+1$ is
a valid choice. Suppose $A\subsetneq 3\mathbb{N}+1$, and $3k+1$ is the least
element of $3\mathbb{N}+1\setminus A$. Then surely
$w^{A}(n)=w^{3\mathbb{N}+1}(n)$ for all $n<3k+1$. However, for all $3j+1\in
A$, $j<k$, $w^{A}(3k+1-(3j+1))=w^{A}(3(k-j))=1$, so $w^{A}(3k+1)=0$, a
contradiction. Thus $3\mathbb{N}+1$ is the only set generating this sequence.∎

The following proposition gives another way to identify these extensions,
which we use later in the paper.

######  Proposition 2.10.

If $\\{w^{A}\\}$ is periodic over $p$ and $\operatorname{PrePer}(A)=0$, then
for all $x\in A$ and $k\geq 1$, $b=kp+x$ is an extension of $A$.

###### Proof.

Suppose $\operatorname{Per}(A)\mid p$ and $\operatorname{PrePer}(A)=0$. Choose
any $x\in A$ and $k\geq 1$, and $n\in\mathbb{N}$ such that $w^{A}(n)=0$. By
the recurrence $w^{A}(n-x)=1$. If $n-x-kp\geq 0$, then by periodicity
$w^{A}(n-x-kp)=1$. Otherwise, $w^{A}(n-x-kp)=1$ because we have no seed. Thus
by the better definition $b$ is an extension of $A$. ∎

The following elementary example can be found in [9, thm 1].

######  Example 2.11.

If $A=\\{1\\}$, then $\\{w^{A}\\}=(01)^{\infty}$, so $\operatorname{Per}(A)=2$
and $\operatorname{PrePer}(A)=0$. Because $1\in A$, any odd number $2k+1$ is
an extension of $A$.

From Example 2.1, if $\\{1,\ldots,k-1\\}\subseteq B$ and $B\cap
k\mathbb{N}=\emptyset$, then $\\{w^{B}\\}=(01^{k-1})^{\infty}$ and
$\operatorname{Per}(B)=k$. The set $B=\\{1\\}\cup\\{p\mid p\text{ prime}\\}$
is an example for $k=4$.

We must be careful to note that Proposition 2.10 does not hold for all seeds.
If we do allow for initial seeds $|S|\leq\alpha$, the induction step fails for
$n\in[p+x-\alpha,p)$. This margin leads to many counterexamples; we provide
two. Let $A=\\{3,5\\}$ and $S=0110$. We find $\operatorname{Per}(A,S)=8$ and
$\operatorname{PrePer}(A,S)=0$, so let $b=8+3=11$. Then:

$\\{w^{A,S}\\}=(01^{5}0^{2})^{\infty}\hskip 20.0pt\text{and}\hskip
20.0pt\\{w^{A\cup\\{b\\},S}\\}=01^{5}0101^{3}(01)^{\infty}$

These are vastly different and we even caused a preperiod of length $12$. As
another example:

$\\{w^{\\{3,6,8\\},0^{2}1^{3}}\\}=(011^{3}(01)^{3})^{\infty}\hskip
20.0pt\text{and}\hskip
20.0pt\\{w^{\\{3,6,8,12\\},0^{2}1^{3}}\\}=(01^{4}01^{3}001^{3})^{\infty}.$

We also note that the converse of Proposition 2.10 does not hold, though it
appears to hold if $|A|\leq 3$. For example, let $A=\\{1,2,6,11\\}$. Then
$\\{w^{A}\\}=0\big{(}1^{2}01^{3}(01^{2})^{2}\big{)}^{\infty}$, so
$\operatorname{Per}(A)=12$, $\operatorname{PrePer}(A)=1$. However it is true
that for all $k\geq 1$ and $x\in A$, $b=12k+x$ is indeed an extension of $A$.
Also see the counterexample $\\{1,8,13,16\\}$.

Contrasting these complex examples with Example 2.11, we see that sequences
are easiest to examine with no seed and no preperiod. The following Lemma can
simplify the process of checking whether a sequence is in this form.

######  Lemma 2.12 (Translating zeros).

Given a set $A$, then for any $p\in\mathbb{N}$, $w^{A}$ is periodic over $p$
and has no preperiod if and only if it holds for all $x\in A$ and $m<x$ that

$w^{A}(m)=0\hskip 10.0pt\implies\hskip 10.0ptw^{A}(m+p-x)=1.$

We call this “translating zeros” because $w(m)=0\implies w(m+p-x)=1$ suggests
that $w(m+p)=0$, but does not discuss the translation of the $1$’s. Note that
it does not _a priori_ imply that the zeros translate, since only $m<x$ is
considered.

###### Proof.

Suppose for the sake of contradiction that the premise $w(m)=0\implies
w(m+p-x)=1$ holds but there is some least $m\in\mathbb{N}$ such that $w(m)\neq
w(m+p)$. There are two cases.

  1. (i)

If $w(m)=1$, then $w(m+p)=0$, so there is some $x\in A$ such that $w(m-x)=0$
but $w(m+p-x)=1$. Because there is no seed this implies $m-x\geq 0$, and
because $w(m-x)\neq w(m-x+p)$ this contradicts the minimality of $m$.

  2. (ii)

If $w(m)=0$, then $w(m+p)=1$, so there is some $x\in A$ with $w(m+p-x)=0$ but
$w(m-x)=1$. If $m-x\geq 0$, then this would contradict the minimiality of $n$.
Otherwise, $m<x$ and $w(m)=0$, so the premise implies that $w(m+p-x)=1$, a
contradiction.

Either case leads to a contradiction, so for all $m\geq 0$, we have
$w(m)=w(m+p)$. In the other direction, if $w$ is periodic with no preperiod
then the condition follows by definition. ∎

######  Corollary 2.12.1.

If $A=\\{a,b,c\\}$ for any $a<b,c$, then $\operatorname{Per}(A)\mid(b+c)$ and
$\operatorname{PrePer}(A)=0$ if and only if $w^{A}(b+c-i)=1$ for all
$i\in[1,a]$.

###### Proof.

Apply Lemma 2.12 for $p=b+c$. For all $x\in A$, if $x=b$, then $w(m)=0\implies
w(m+p-b)=w(m+c)=1$ by the recurrence. If $x=c$, then $w(m)=0\implies
w(m+p-c)=w(m+b)=0$. If $x=a=\min(A)$, then we note that for all $m<a$,
$w(m)=0$. Therefore it suffices to check that for $m\in[0,a-1]$, we have
$w^{A}(b+c+m-a)=0$. Simplify by substituting $i=a-m\in[1,a]$. ∎

This Corollary will likely help in proving Conjecture 3.

######  Corollary 2.12.2.

If $A=\\{1,b,c\\}$, then $\operatorname{Per}(A)\mid(b+c)$ and
$\operatorname{PrePer}(A)=0$ if and only if $w^{A}(b+c-1)=1$. $\square$

These corollaries give some insight to the usefulness of the translating zeros
Lemma. For Corollary 2.12.2 we can determine the period and preperiod by
checking one value of the sequence! This will be used in Section 4.

######  Lemma 2.13.

The following statements are equivalent.

  1. (i)

$w$ is periodic over $p$ with no preperiod

  2. (ii)

For all $n\geq 0$, $w(n)=w(n+p)$

  3. (iii)

For all $n\geq\alpha$, $\vec{v}(n)=\vec{v}(n+p)$

  4. (iv)

$\vec{v}(\alpha)=\vec{v}(\alpha+p)$

  5. (v)

For all $x\in A$, for each $m<x$, we have $w(m)=0\implies w(m+p-x)=1$.
$\square$

##  3 The $\\{a,b\\}$ case

We first inspect the case when $|A|=1$. If $A=\\{a\\}$, then the recurrence
relation in Equation 1 gives that $w^{A}(n)=1-w^{A}(n-a)$ for all
$n\in\mathbb{N}$. This gives us an immediate characterization of the
periodicity for all possible seeds.

######  Proposition 3.1.

Let $A=\\{a\\}$. For all seeds $S$, let $\overline{S}$ be the string
exchanging $0$’s and $1$’s. Then
$\\{w^{A,S}\\}=\big{(}\,\overline{S}\,S\,\big{)}^{\infty}$, so
$\operatorname{Per}(A,S)\mid 2a$ and $\operatorname{PrePer}(A,S)=0$. $\square$

This gives the result that
$\mathcal{W}^{\\{a\\}}=\big{\\{}(\,\overline{S}\,S\,\big{)}^{\infty}\mid
S\in\\{0,1\\}^{a}\\}\big{\\}}$ and thus
$\left|\mathcal{W}^{\\{a\\}}\right|=2^{a}$.

######  Proposition 3.2.

Let $A=\\{a\\}$, and let $a=2^{k}c$, where $c$ is odd. Then
$\mathcal{P}^{A}=\\{2^{k+1}d:d\mid c\\}$. $\square$

###### Proof.

First, we show that $p=\operatorname{Per}(A,S)$ must be of the form
$2^{k+1}d$. We know that $\\{w^{A,S}\\}$ will always be periodic over $2a$, so
$p\mid 2a$. Additionally, we know $w^{A,S}(n)\neq w^{A,S}(n+a)$ for all $n$,
so $p\mid\\!\\!\\!\\!/\,\,a$. Therefore $2^{k+1}\mid p$. We now show that for
any $d\mid c$ we have $2^{k+1}d\in\mathcal{P}^{\\{a\\}}$. Because $c/d$ is odd
let $c=(2x+1)d$. Then let $S=\left(1^{2^{k}d}0^{2^{k}d}\right)^{x}1^{2^{k}d}$,
so we conclude
$\\{w^{A,S}\\}=\left(\left(1^{2^{k}d}0^{2^{k}d}\right)^{x}1^{2^{k}d}\
\left(0^{2^{k}d}1^{2^{k}d}\right)^{x}0^{2^{k}d}\right)^{\infty}=\left(1^{2^{k}d}0^{2^{k}d}\right)^{\infty}$
and $\operatorname{Per}(\\{a\\},S)=2^{k+1}d$. ∎

These initial results are apparent at first inspection of the problem. With
more work will get similarly general results for $|A|=2$.

######  Theorem 3.3.

Let $A=\\{a,b\\}$. For all seeds $S$, $\operatorname{Per}(A,S)\mid a+b$ and
$\operatorname{PrePer}(A,S)=0$.

###### Proof.

Let $A=\\{a,b\\}$. For all $n\in\mathbb{N}$, in the case where $w(n)=0$ we
have $w(n+a)=w(n+b)=1$, which implies that $w(n+a+b)=0$. Alternately, if
$w(n)=1$, then $w(n-a)=0$ or $w(n-b)=0$, so by the $0$-case we know $w(n+b)=0$
or $w(n+a)=0$ respectively. This means $w(n+a+b)=1$. ∎

The following Theorem on $2$-set games with no seed is well known and can be
found in [4, p. 530].

######  Theorem 3.4.

Let $A=\\{a,b\\}$ with $a<b$, and let $b=qa+r$ with $0\leq r<a$. Then

$\\{w^{A}\\}=\begin{cases}(0^{a}1^{a})^{q/2}0^{r}1^{a}&q\text{ is even.}\\\
(0^{a}1^{a})^{\left\lceil q/2\right\rceil}1^{r}&q\text{ is odd.}\end{cases}\
=\Big{(}\underbrace{0^{a}1^{a}0^{a}1^{a}\ldots}_{b}1^{a}\Big{)}^{\infty}$ (8)

so $\operatorname{Per}(A)=2a$ if $b$ is an odd multiple of $a$ and
$\operatorname{Per}(A)=a+b$ otherwise.

###### Proof.

For $n<b$, we note that by having no seed $w^{A}(n-b)=1$. This implies
$w^{A}(n)=w^{\\{a\\}}(n)$. This yields the sequence
$\\{w^{A}\\}=\underbrace{0^{a}1^{a}0^{a}1^{a}\ldots}_{b}$ . For $n\in[b,a+b)$,
we note that $n-b\in[0,a)$ so $w^{A}(n-b)=0$ and thus $w^{A}(n)=1$. Theorem
3.3 implies that this period repeats. ∎

###  3.1 A Preliminary Tool: Studying $\\{1,b\\}$

Theorem 3.4 characterizes the period structure for the default seed. Our next
goal is to describe the sequence under all seeds. One corollary of the
following theorems is that for any $a,b$ coprime,
$4,6\notin\mathcal{P}^{\\{a,b\\}}$. At present, it seems like it should be
possible to find a seed which generates a period of $4$ or $6$ as long as
$4\mid a+b$ or $6\mid a+b$, but in fact it is not. We will give a full
characterization of all period structures and lengths which will make this
fact obvious. To do this, we first analyze the special case where $a=1$.

######  Theorem 3.5.

Suppose we have $A=\\{1,b\\}$ and a string $X$ with no-subperiod. Then
$X^{\infty}\in\mathcal{W}^{A}$ if and only if $|X|\Big{|}(1+b)$ and $X$ is
some concatenation of $01$ and $011$ under some rotation.

###### Proof.

$\implies$ Suppose that $\\{w^{A,S}\\}=X^{\infty}$. By the assumption that $X$
has no sub-period, $\operatorname{Per}(A)=|X|$, so by Theorem 3.3
$|X|\Big{|}(1+b)$. Next we will show that $X$ has no two consecutive $0$’s or
three consecutive $1$’s. By the recurrence relation, $w(n)=0$ implies
$w(n+1)=1$. Additionally, suppose for some sufficiently large $n$ that
$w(n)=w(n-1)=1$ This implies $w(n-b)=0$, so by Theorem 3.3
$w(n-b+b+1)=w(n+1)=0$. These two restrictions mean that $X$ is a concatenation
of $01$ and $011$ under some rotation. $\Longleftarrow$ Suppose that
$k|X|=(1+b)$ for $k\geq 1$ and $X$ is some concatenation of $01$ and $011$.
For the seed $S$ we can simply choose $X^{k}$, so it suffices to show that
$X^{\infty}$ satisfies the recurrence relation. Choose $n\in\mathbb{N}$.
First, suppose $X^{\infty}(n-1)=0$. Because there are no consecutive $0$’s,
$X^{\infty}(n)=1$, which satisfies the recurrence relation. Now suppose
$X^{\infty}(n-1)=1$ and $X^{\infty}(n+1)=0$. Because there are no consecutive
$0$’s, $X^{\infty}(n)=1$. Additionally because $X^{\infty}$ is periodic over
$|X|$, $X^{\infty}(n+1-k|X|)=X^{\infty}(n-b)=0$, so indeed $X^{\infty}(n)=1$
satisfies the recurrence. Now consider the last case
$X^{\infty}(n-1)=X^{\infty}(n+1)=1$. Because there are no three consecutive
$1$’s, this implies $X^{\infty}(n)=0$. Additionally
$X^{\infty}(n+1-k|X|)=X^{\infty}(n-b)=1$ and by assumption
$X^{\infty}(n-1)=1$, so $X^{\infty}(n)=0$ satisfies the recurrence. ∎

Recall from Theorem 3.3 that $\\{w^{A,S}\\}$ can never have a preperiod, so
Theorem 3.5 completely characterizes all possible sequences for $\\{1,b\\}$.
We also note that instead of considering strings $X$ with $|X|\big{|}(b+1)$
and no subperiod, we can equivalently consider all $X$ with $|X|=(b+1)$ and
allow for any subperiod of length $p\mid(b+1)$. Define the sets

$\mathcal{Q}:=\\{X\in\\{0,1\\}^{\ell}\mid\ell\in\mathbb{N},\ X\text{ is a
concatenation of 01 and 011 under some rotation}\\},$

and $\mathcal{Q}(\ell):=\\{X\in\mathcal{Q}\mid|X|=\ell\\}$. Sequences of this
form can be generated iteratively by hand or by computer. For example,
$\mathcal{Q}(2)=\\{01,10\\}$, $\mathcal{Q}(3)=\\{011,101,110\\}$, and
$\mathcal{Q}(6)=\\{010101,101010,$
$011011,101101,110110\\}$. Theorem 3.5 proves that
$\mathcal{W}^{\\{1,b\\}}=\\{X^{\infty}\mid X\in\mathcal{Q}(b+1)\\}$. We can
also provide an explicit enumeration of the possible sequences.

######  Theorem 3.6.

Let $\phi$ be the plastic constant and $z,\bar{z}$ be the other two complex
roots of $x^{3}-x-1$, and let
$Q(\ell):=\phi^{\ell}+z^{\ell}+{\bar{z}}^{\ell}$. Then the number of distinct
sequences $\\{w^{\\{1,b\\},S}\\}$ over all seeds $S$ is

$\big{|}\mathcal{W}^{\\{1,b\\}}\big{|}=\left\lvert\mathcal{Q}(1+b)\right\rvert=Q(1+b).$
(9)

###### Proof.

To find a recurrence relation, we consider the four possible forms for the
period structure $X$ to take, and how each can be reduced to a different form.
We will then add the sequences which count each of these forms.

$\displaystyle Q_{1}(\ell)$ $\displaystyle X=0\ldots 01$ $\displaystyle
Q_{1}(\ell-2)+Q_{2}(\ell-2)$ by removing the last two numbers $\displaystyle
Q_{2}(\ell)$ $\displaystyle X=0\ldots 11$ $\displaystyle Q_{1}(\ell-1)$ by
removing the last number $\displaystyle Q_{3}(\ell)$ $\displaystyle X=1\ldots
01$ $\displaystyle Q_{2}(\ell)$ by rotating one character left $\displaystyle
Q_{4}(\ell)$ $\displaystyle X=1\ldots 10$ $\displaystyle
Q_{1}(\ell)+Q_{2}(\ell)$ by rotating one character right
$Q(\ell)=Q_{1}(\ell)+Q_{2}(\ell)+Q_{3}(\ell)+Q_{4}(\ell)=3Q_{2}(\ell)+2Q_{1}(\ell)=3Q_{1}(\ell-1)+2Q_{1}(\ell).$

We note $Q_{1}(\ell)=Q_{1}(\ell-2)+Q_{1}(\ell-3)$, so to follows that
$Q(\ell)=Q(\ell-2)+Q(\ell-3)$. This is a linear recurrence relation, meaning
$Q(\ell)$ is a linear combination of the form
$c_{1}\phi^{\ell}+c_{2}z^{\ell}+c_{3}{\bar{z}}^{\ell}$, where $\phi,$ $z$, and
$\bar{z}$ are the roots of $x^{3}-x-1$. We give initial conditions $Q(1)=0$,
$Q(2)=|\\{01,10\\}|=2$, and $Q(3)=|\\{011,101,011\\}|=3$.

To find the coefficients we compute that $Q(0)=3$, so $c_{1}+c_{2}+c_{3}=3$.
Additionally, $Q$ is real so $c_{2}=c_{3}$. Finally, we know that
$x^{3}-x-1=(x-\phi)(x-z)(x-\bar{z})=x^{3}-(\phi+z+\bar{z})x^{2}+\ldots$, so
$\phi+z+\bar{z}=0=Q(1)$. Therefore $c_{1}=c_{2}=c_{3}=1$. ∎

$Q(\ell)$ is in the OEIS, known as the Perrin sequence [10, A001608].

####  3.1.1 Distinct Periodicities.

If we analyze $\mathcal{W}^{\\{1,5\\}}$, or equivalently $\mathcal{Q}(6)$, we
find that all of the sequences ‘look like’ some form of $(01)^{\infty}$ or
$(011)^{\infty}$, with some initial shift that we call a ‘rotation’. This is
true for many sequences, motivating a formal notion of similarity between
period structures.

######  Definition 5.

We call two strings $X_{1},X_{2}$ similar if they have a common subperiod,
i.e. $X_{1}^{k_{1}}=X_{2}^{k_{2}}$ for $k_{1},k_{2}\geq 1$, or if $X_{2}$ is
some rotation of $X_{1}$, i.e. $|X_{1}|=|X_{2}|=\ell$ and
$X_{2}(n)=X_{1}(n+x\pmod{\ell})$. We define $\simeq$ to be the equivalence
relation generated by these two criteria. We say $X$ and $Y$ are distinct if
$X\not\simeq Y$.

######  Definition 6.

We denote $\mathcal{Q}/\\!\simeq$ as the set of equivalence classes of
$\mathcal{Q}$ under $\simeq$. The length of a class $[Y]$ is the length of its
smallest element, i.e. the smallest subperiod of $Y$ or the period length of
$Y^{\infty}$.

Recall that $\mathcal{Q}(\ell)$ is the set of all strings in $\mathcal{Q}$
with length $\ell$, which is in bijection with $\mathcal{W}^{\\{1,\ell-1\\}}$.
Therefore $\mathcal{Q}(\ell)/\simeq$ is the set of distinct periodicites in
$\mathcal{Q}(\ell)$, so

$\mathcal{W}^{\\{1,b\\}}/\\!\simeq\ \ \ =\ \
\big{\\{}X^{\infty},[X]\in\mathcal{Q}(\ell)/\simeq\big{\\}}$ (10)

######  Definition 7.

We define $(\mathcal{Q}/\\!\simeq)(\ell)$ to be set of distinct periodicities
of $\mathcal{Q}/\\!\simeq$ with length $\ell$. Similarly
$(\mathcal{W}^{A}/\\!\simeq)(\ell)$ is the set of distinct periodicites in
$\mathcal{W}^{A}/\\!\simeq$ with length $\ell$.

It follows that

$(\mathcal{W}^{\\{1,b\\}}/\\!\simeq)(\ell)\ \ \ =\ \
\big{\\{}X^{\infty},[X]\in\mathcal{(}Q/\simeq)(\ell)\big{\\}}.$ (11)

This implies that $p\in\mathcal{P}^{\\{1,b\\}}$ if and only if $p\mid(1+b)$
and $\left\lvert(\mathcal{Q}/\\!\simeq)(p)\right\rvert>0$, as means there is
some non-periodic string $X\in\mathcal{Q}$ with length $|X|=p$ and thus
$X^{\infty}\in(\mathcal{W}^{\\{1,b\\}}/\\!\simeq)(p)$.

######  Example 3.7.

If we want to find the distinct periodicities of length three, six, and eight,
we observe that $(\mathcal{Q}/\\!\simeq)(3)=\\{[011]\\}$,
$(\mathcal{Q}/\\!\simeq)(6)=\emptyset$, and
$(\mathcal{Q}/\\!\simeq)(8)=\\{[01101101]\\}$. In contrast, if we wish to know
all distinct periodicites of $\\{1,2\\}$, $\\{1,5\\}$, and $\\{1,7\\}$, we
instead consult $(\mathcal{Q}(3)/\\!\simeq)=\\{[011]\\}$,
$(\mathcal{Q}(6)/\\!\simeq)=\\{[(01)^{3}],[(011)^{2}]\\}$, and
$(\mathcal{Q}(8)/\\!\simeq)=\\{[(01)^{4}],[01101101]\\}$.

It follows that because the periodicites of $\mathcal{Q}(\ell)$ must have some
length $d\mid\ell$, we can enumerate $\mathcal{Q}(\ell)/\simeq$ by
partitioning over period length. The following is a natural result of
Equations 10 and 11.

$|\mathcal{W}^{\\{1,\ell-1\\}}/\simeq|=\sum_{d\mid\ell}|(\mathcal{W}^{\\{1,\ell-1\\}}/\simeq)(d)|\hskip
20.0pt=\hskip
20.0pt|\mathcal{Q}(\ell)/\simeq|=\sum_{d\mid\ell}|(\mathcal{Q}/\simeq)(d)|$
(12)

In the rest of this section we will enumerate the sets
$\mathcal{W}^{\\{a,b\\}}$, $\mathcal{W}^{\\{a,b\\}}/\\!\simeq$, and
$(\mathcal{W}^{\\{a,b\\}}/\\!\simeq)(\ell)$ for all $\\{a,b\\}$. Recall that
Theorem 3.6 gives $|\mathcal{W}^{\\{1,b\\}}|=Q(n)$.

######  Proposition 3.8.

Define

$N^{\prime}(\ell):=\frac{\displaystyle Q(\ell)-\sum_{d!|\ell}d\cdot
N^{\prime}(d)}{\ell}\hskip 30.0ptN(L):=\sum_{\ell\mid L}N^{\prime}(\ell),$
(13)

where $d!|\ell$ represents proper divisors of $\ell$. Then the number of
distinct periodicities of $\\{1,b\\}$ of length $\ell\mid(1+b)$ is
$|(\mathcal{W}^{\\{1,b\\}}/\\!\simeq)(\ell)|=N^{\prime}(\ell)$, and the total
number of distinct perioditicites is
$|\mathcal{W}^{\\{1,b\\}}/\\!\simeq|=N(b+1)$.

###### Proof.

We will show $N^{\prime}(\ell)=|(\mathcal{Q}/\simeq)(\ell)|$. First we
consider all strings $X\in\mathcal{Q}(\ell)$. In particular suppose $X$ has
period $p$, so $\ell/p=k$ and $X=Z^{k}$ for some $Z$ having no subperiod, i.e.
$[Z]\in(\mathcal{Q}/\simeq)(p)$. Because $Z$ has no subperiod, it has $p$
different rotations and therefore $p$ representatives
$X_{1},\ldots,X_{p}\in\mathcal{Q}(\ell)$. Since $p$ can be any divisor of
$\ell$, we conclude
$|\mathcal{Q}(\ell)|=\sum_{p\mid\ell}p|(\mathcal{Q}/\simeq)(p)|$/ We can
rearrange this to conclude
$|(\mathcal{W}^{\\{1,b\\}}/\\!\simeq)(\ell)|=|(\mathcal{Q}/\simeq)(\ell)|=N^{\prime}(\ell)$
as written in Equation 13. Note that we do not need a base case to compute
$N^{\prime}$ explicitly because $1$ has no proper divisors. Equation 12
implies $|\mathcal{W}^{\\{1,b\\}}/\\!\simeq|=N(b+1)$. ∎

Note that $N^{\prime}(\ell)$ does not depend on $b$, and in fact the set of
distinct periodicities of length $\ell$ is equal for any $b$ as long as
$\ell\mid(1+b)$. The OEIS contains sequences $N^{\prime}(\ell)$ [10, A113788]
and $N(L)$ [10, A127687], motivating an interesting bijection.

It is known that $Q(\ell)$ counts the maximal independent sets in vertex
labeled cycles $C_{\ell}$ (see, for example, Example 1.2 in [7]). In 2007,
Bisdorff et. al demonstrated that $N(b+1)$ counts the number of unlabeled
maximal independent sets of the cycle $C_{b+1}$ [5]. The correspondence
between a binary sequence $Y$ and a vertex set $S\subseteq V(C_{b+1})$ is
simple; we include the $i^{\text{th}}$ vertex in $S$ exactly when $Y(i)=0$.
For example $\mathcal{Q}(10)\ni(01)^{2}(011)^{2}\mapsto\\{1,3,5,8\\}\subseteq
V(C_{10})$. The conditions for a string to be valid are equivalent to those
for a maximal independent set. We cannot have two adjacent vertices of $S$ by
independence, and $Y$ cannot have two consecutive zeros by Theorem 3.5. We
also cannot have three adjacent non-vertices in $S$ by maximality, or else we
could add the middle vertex to $S$. Similarly $Y$ cannot have three
consecutive ones. By our construction, it is clear that $N$ counts these sets
in $C_{b+1}$ up to rotation, but not reflection. For example, the sequence
$(01)(011)(01)^{2}(011)(01)^{3}(011)\not\simeq(01)^{3}(011)(01)^{2}(011)(01)(011)$
because one cannot be rotated to the other, so they belong to different
equivalence classes of $\mathcal{Q}/\simeq$. Thus, $N(21)$ will count them
both. However a reflection automorphism of $C_{21}$ would map the
corresponding independent sets to each other. Moving forward, Table 1 shows
the sequences $Q(\ell)$, $N^{\prime}(\ell)$, and $N(\ell)$ for
$\ell\in\\{0,\ldots,20\\}$.

###  3.2 Generalizing to $\\{a,b\\}$

We will use a simple multiplicative permutation of $w^{A,S}$ to reduce every
$\\{a,b\\}$ case to a version of $\\{1,b^{\prime}\\}$. This will induce the
strict structure of Theorem 3.5 on the seemingly complex periodicities of the
$\\{a,b\\}$ case. We will generally assume that $a,b$ are coprime. If not, we
can divide out $g=\gcd(a,b)$ and then find $g$ parallel copies of sequences
$(w)_{i}$ for the coprime set $A=\\{a/g,b/g\\}$ using Multiplicative Linearity
Proposition 2.7.

######  Definition 8.

Given some $a,b$ coprime, define the permutation
$\sigma_{a,a+b}:\\{0,1\\}^{a+b}\mathrel{\mathrlap{\hookrightarrow}}\mathrel{\mkern
2.0mu\twoheadrightarrow}\\{0,1\\}^{a+b}$ by $\sigma_{a,a+b}(Y)=X$, where
$X(n)=Y(an\pmod{a+b})$ for all $n\in\\{0,\ldots a+b-1\\}$.

Because $a$ and $a+b$ are coprime, $\sigma_{a,a+b}(Y)$ is a permutation of the
string $Y$ for all $Y\in\\{0,1\\}^{a+b}$. This means $\sigma_{a,a+b}$ is
invertable, so it is a permutation of the collection $\\{0,1\\}^{a+b}$.

######  Theorem 3.9 (Bijection).

Suppose $A=\\{a,b\\}$ with $a,b$ coprime and let $A^{\prime}=\\{1,a+b-1\\}$.
For any string $Y$ with $|Y|=a+b$, let $X=\sigma_{a,a+b}(Y)$. Then
$Y^{\infty}\in\mathcal{W}^{A}$ if and only if
$X^{\infty}\in\mathcal{W}^{A^{\prime}}$.

###### Proof.

It suffices to show that $Y^{\infty}$ obeys the recurrence relation if and
only if $X^{\infty}$ does, as we could then use the seeds $Y^{(a+b)/|Y|}$ and
$X^{(a+b)/|X|}$ respectively. Let $a^{\text{-}1}$ be the multiplicative
inverse of $a\pmod{a+b}$. This means
$Y^{\infty}(n)=X^{\infty}(a^{\text{-}1}n\pmod{a+b})$, so
$Y=\sigma_{a^{\text{-}1},a+b}(X)$. By leveraging the periodicity of
$Y^{\infty}$ and $X^{\infty}$ over $a+b$, and noting that
$b\equiv-a\pmod{a+b}$, we get

$\displaystyle Y^{\infty}(n)$ $\displaystyle=X^{\infty}(a^{\text{-}1}n)$
$\displaystyle Y^{\infty}(n-a)$
$\displaystyle=X^{\infty}(a^{\text{-}1}n-a^{\text{-}1}a)$
$\displaystyle=X^{\infty}(a^{\text{-}1}n-1)$ $\displaystyle Y^{\infty}(n-b)$
$\displaystyle=X^{\infty}(a^{\text{-}1}n-a^{\text{-}1}(-a))=X^{\infty}(a^{\text{-}1}n+1)$
$\displaystyle=X^{\infty}(a^{\text{-}1}n-(a+b-1))$

Therefore $Y^{\infty}$ follows the recurrence relation of $A=\\{a,b\\}$ if and
only if $X^{\infty}$ follows the recurrence relation of
$A^{\prime}=\\{1,a+b-1\\}$. ∎

Theorem 3.9 implies that the set of all period structures of $\\{a,b\\}$ can
be obtained by applying the inverse permutation
$\sigma_{a,a+b}^{\text{-}1}=\sigma_{a^{\text{-}1},a+b}$ to each period
structure of $\\{1,a+b-1\\}$. Because $\sigma_{a,a+b}$ is a permutation of
$\\{0,1\\}^{a+b}$, it bijects the set $\mathcal{W}^{\\{a,b\\}}$ of all
$\\{w^{\\{a,b\\},S}\\}$ sequences with the set $\mathcal{W}^{\\{1,a+b-1\\}}$.
In particular, we conclude precisely that if $a$ and $b$ are coprime, then

$\mathcal{W}^{\\{a,b\\}}=\\{Y^{\infty}\mid Y=\sigma_{a^{\text{-}1},a+b}(X),\
X\in\mathcal{Q}(a+b)\\},$ (14)

or informally
$\mathcal{W}^{\\{a,b\\}}=\sigma_{a^{\text{-}1},a+b}\left[\mathcal{W}^{\\{1,a+b-1\\}}\right]$.
Therefore Theorem 3.9 implies that we can generalize the results of Section
3.1.

######  Corollary 3.9.1.

Choose any $A=\\{a,b\\}=\\{\tilde{a}g,\tilde{b}g\\}$, where $g=\gcd(a,b)$.
Then $|\mathcal{W}^{A}|=(Q(\tilde{a}+\tilde{b}))^{g}$. $\square$

The power of $g$ follows from Linearity Proposition 2.7. Each of the
independent parallel sequences $(w^{A,S})_{i}(m)$ for $i\in\\{0,\ldots,g-1\\}$
is equal to some $\\{\tilde{a},\tilde{b}\\}$ game. Thus we can count
$g$-tuples of strings in
$\sigma_{\tilde{a}^{\text{-}1},\tilde{a}+\tilde{b}}\left[\mathcal{Q}(a+b)\right]$
to arrive at the total, which we formalize in Theorem 3.10. Next, we find that
$\sigma_{a,a+b}$ also bijects the classes of distinct periods.

######  Corollary 3.9.2.

Let $a,b$ be coprime and $A=\\{a,b\\}$. Then
$|\mathcal{W}^{A}/\\!\simeq(\ell)|=N^{\prime}(\ell)$ is the number of distinct
periodicities of length $\ell\mid(a+b)$, and
$|\mathcal{W}^{A}/\\!\simeq|=N(a+b)$ is the total number of distinct
periodicities of $A$.

###### Proof.

It suffices to show that $\sigma_{a,a+b}$ preserves rotational symmetries and
subperiods. Suppose some sequences $Y$ and $Y^{\prime}$ are rotated copies of
each other, i.e. there is some $r$ such that $Y(n)=Y^{\prime}(n+r\pmod{\ell})$
for all $n$. This implies $(\sigma Y)(n)=(\sigma
Y^{\prime})(n+ar\pmod{\ell})$, so $\sigma Y$ and $\sigma Y^{\prime}$ are
rotated copies of each other with shift $ar$. Additionally, suppose $Y$ has
some subperiod, i.e. there is some $r\not\equiv 0\pmod{\ell}$ such that
$Y(n)=Y(n+r\pmod{\ell})$. This implies $Y$ is a rotated copy of itself, so
indeed $\sigma Y$ is a rotated copy of itself with shift $ar\not\equiv
0\pmod{\ell}$, since $\ell\mid(a+b)$ and $\gcd(a,a+b)=1$. We conclude that for
all $X$ and $Y$, $X\simeq Y$ if and only if $\sigma X\simeq\sigma Y$, so
equivalence classes of $\simeq$ are bijected by $\sigma_{a,a+b}$. ∎

If $a$ and $b$ are not coprime, it is more complicated to count the number of
distinct periodicities, but we can use a generalization of Proposition 3.8.

######  Theorem 3.10.

Choose any $A=\\{a,b\\}=\\{\tilde{a}g,\tilde{b}g\\}$, where $g=\gcd(a,b)$.
Define the following functions for all $g,\ell\in\mathbb{N}\setminus\\{0\\}$
and $L=g\ell$:

$N^{\prime}(L,g):=\frac{\displaystyle Q(\ell)^{g}-\sum_{d!|L}d\cdot
N^{\prime}\left(d,\gcd(d,g)\right)}{L}\hskip 30.0ptN(L,g):=\sum_{p\mid
L}N^{\prime}(p,\gcd(p,g))$ (15)

Then $|\mathcal{W}^{A}/\\!\simeq(p)|=N^{\prime}(p,\gcd(p,a,b))$ is the number
of distinct periodicities of $A$ with length $p$, and
$|\mathcal{W}^{A}/\\!\simeq|=N(a+b,g)$ is the total number of distinct
periodicities of $A$.

###### Proof.

First we will justify that the total number of strings in
$\mathcal{W}^{\\{a,b\\}}$ which are periodic over $p$ is
$\left(Q(\frac{p}{\gcd(p,g)})\right)^{\gcd(p,g)}$, not considering similarity
under $\simeq$. Denote this set by $\mathcal{W}^{\\{a,b\\}}(p)$. Let
$\ell=\tilde{a}+\tilde{b}$. We know by Theorem 3.3 that $\\{w\\}$ is always
periodic over $g\ell=a+b$, so for all $S$, $\\{w^{A,S}\\}=Y^{\infty}$ for some
$Y$ with $|Y|=g\ell$. Using Linearity Proposition 2.7, we can write $Y$ as a
collection of parallel strings $Y_{i}$ for $i\in\\{0,\ldots g-1\\}$ where
$|Y_{i}|=\ell$, and for all $m\in\\{0,\ldots,\ell-1\\}$, $Y_{i}(m)=Y(gm+i)$.
Additionally, for each $i$, $Y_{i}^{\infty}$ must satisfy the recurrence
relation for $\\{\tilde{a},\tilde{b}\\}$. Suppose that $Y$ is also periodic
over length $p\mid\ell$, so $Y^{\infty}\in\mathcal{W}^{\\{a,b\\}}(p)$. Using
the division algorithm let $p=xg+r$, where $r<g$ and $x\in\mathbb{N}$.
Additionally, let $\gamma=\gcd(p,g)$ and $\tilde{g}=g/\gamma$. We will prove
that the following conditions are sufficient and necessary for this to occur.

  1. (i)

For all $i\in\\{0,\ldots,\gamma-1\\}$, and all $m$,
$\displaystyle{Y_{i}(m)=Y_{i}(m+p/\gamma)}$

  2. (ii)

For all $i\in\\{\gamma,\ldots,g-1\\}$ and all $m$,
$\displaystyle{Y_{i}(m)=\begin{cases}Y_{i-r}(m-x)&i\geq r\\\
Y_{i-r+g}(m-x-1)&i<r\\\ \end{cases}}$

We first show necessity. Assuming $Y$ is periodic over length $p$, this means
for all $m,i$, we have

$\displaystyle Y_{i}(m)=Y(mg+i)$
$\displaystyle=Y(mg+i-p)=Y(mg+i-xg-r)=\begin{cases}Y_{i-r}(m-x)&i\geq r\\\
Y_{i-r+g}(m-x-1)&i<r\\\ \end{cases}$
$\displaystyle=Y(mg+i+\tilde{g}p)=Y(mg+i+gp/\gamma)=Y_{i}(m+p/\gamma),$

This proves stronger versions of (i) and (ii).

Next, we show sufficiency. Assume (i) and (ii) hold. For any $n$, use the
division algorithm to get $n=mg+i$. We hope to show that $Y(n)=Y(n-p)$.
Suppose that $i\in\\{\gamma,\ldots,g-1\\}$. Then by condition (ii),

$Y(n)=Y_{i}(m)=\begin{cases}Y_{i-r}(m-x)&i\geq r\\\ Y_{i-r+g}(m-x-1)&i<r\\\
\end{cases}=Y(mg-gx+i-r-gx)=Y(n-p)$ (16)

Alternately, suppose that $i\in\\{0,\ldots,\gamma-1\\}$, and consider the set
of indices $i,i+r,i+2r,\ldots,i+(\tilde{g}-1)r$, taken modulo $g$. We denote
these $I_{j}\equiv i+rj\pmod{g}$ for $j\in\\{0,\ldots,\tilde{g}-1\\}$. Because
$\gamma\mid r$, this means $I_{j}\equiv i\pmod{\gamma}$ for all $j$.
Additionally, we know that the order of $r$ in the group $\mathbb{Z}_{g}^{+}$
is $g/\gcd(g,r)=\tilde{g}$, which means that $I_{j}\neq i$ for
$j\in\\{1,\ldots,\tilde{g}-1\\}$. This means that only $I_{0}$ can be in the
set $\\{0,\ldots,\gamma-1\\}$ and for all $j>0$ we must have
$I_{j}\in\\{\gamma,\ldots,g-1\\}$.

Now, let $n^{\prime}=n-\tilde{g}p$, and consider the sequence of values
$Y(n^{\prime}),Y(n^{\prime}+p),\ldots,Y(n^{\prime}+(\tilde{g}-1)p)$. We know
that $Y(n^{\prime})=Y_{i}(m-p/\gamma)=Y_{i}(m)=Y(n)$ by condition (i). We also
observe that for all $j\in\\{0,\ldots,\tilde{g}-1\\}$, we have
$Y(n^{\prime}+pj)=Y_{I_{j}}(m_{j})$ for some $m_{j}$. Because we know
$I_{j}\in\\{\gamma,\ldots,g-1\\}$, Equation 16 implies that
$Y(n^{\prime}+pj)=Y(n^{\prime}+p(j-1))$. Therefore

$Y(n)=Y(n^{\prime})=Y(n^{\prime}+p)=\ldots=Y(n^{\prime}+(\tilde{g}-1)p)=Y(n-p).$

Therefore we have shown that conditions (i) and (ii) are equivalent to
$Y^{\infty}$ being periodic over length $p$, and we now enumerate the strings
satisfying these conditions. To satisfy (i) we may choose any $\gamma$-tuple
of sequences in $\mathcal{W}^{\\{\tilde{a},\tilde{b}\\}}$ which are periodic
over $p/\gamma$ for $Y_{0},\ldots,Y_{\gamma-1}$. To satisfy (ii) we must let
$Y_{\gamma},\ldots,Y_{g-1}$ be the appropriate translations of these
sequences, so they are fixed. Thus we find the total number of possibilities
$\left\lvert\mathcal{W}^{\\{a,b\\}}(p)\right\rvert=(Q(p/\gamma))^{\gamma}$.

An argument similar to Proposition 3.8 shows that
$\left\lvert\mathcal{W}^{\\{a,b\\}}(p)\right\rvert=\sum_{d\mid
p}d\left\lvert\mathcal{W}^{A}/\\!\simeq(d)\right\rvert$. Letting
$N^{\prime}(d,\gcd(d,g))=\left\lvert\mathcal{W}^{A}/\\!\simeq(d)\right\rvert$,
these can be rearranged to Equation 15. Note that we can also derive
$N^{\prime}(p,1)=N^{\prime}(p)$ for all $p$, meaning that if $g=1$, we have
reduced to the case of $\\{a,b\\}$ coprime. ∎

$\ell$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$Q(\ell)$ | 0 | 2 | 3 | 2 | 5 | 5 | 7 | 10 | 12 | 17 | 22 | 29 | 39 | 51 | 68 | 90 | 119 | 158 | 209 | 277
$N^{\prime}(\ell)$ | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 5 | 7 | 8 | 11 | 13
$N(\ell)$ | 0 | 1 | 1 | 1 | 1 | 2 | 1 | 2 | 2 | 3 | 2 | 4 | 3 | 5 | 6 | 7 | 7 | 11 | 11 | 16
Table 1: $Q(\ell)$ counts the possible sequences $\\{w^{A,S}\\}$ over all $S$
for $A=\\{a,b\\}$ if $a,b$ coprime and $a+b=\ell$. $N^{\prime}(\ell)$ counts
the number of distinct periodicities of length $\ell$. $N(\ell)$ counts the
number of distinct periodicities of any length for $A=\\{a,b\\}$.

In the simpler case when $a,b$ are coprime, refer to the sequences
$Q(\ell),N^{\prime}(\ell),$ and $N(\ell)$ in Table 1. As a result of the
general enumeration we find that for all $g\mid L$, $N(L,g)=0$ exactly when
$L=g$ or $L=4g$ or $(L,g)=(6,1)$. Thus

$\mathcal{P}^{\\{a,b\\}}=\Big{\\{}p\ \Big{|}\ p|(a+b),\ p\not|\gcd(a,b),\
p\neq 4\gcd(p,a,b),\ (p,\gcd(p,a,b))\neq(6,1)\Big{\\}}$

We also see that for any coprime $a,b$ and any $\ell\leq 10$, there is at most
one distinct periodicity of $a$ and $b$ of length $\ell$ over all $S$. Given
some $A=\\{1,11k-1\\}$ for $k\geq 1$, the two periodicites of length $11$ are
$\mathcal{(}\mathcal{Q}/\\!\simeq)(11)=\big{\\{}\big{[}(01)^{4}(011)\big{]},\,\big{[}(01)(011)^{3}\big{]}\big{\\}}$.
This means that for any $\\{a,b\\}$, with $11\mid a+b$, the two periodicities
are $\sigma_{a^{\text{-}1},11}\big{(}(01)^{4}(011)\big{)}$ and
$\sigma_{a^{\text{-}1},11}\big{(}(01)(011)^{3}\big{)}$.

######  Example 3.11.

Consider the set $A=\\{3,11\\}$. There are $N(14)=5$ periodicites, where
exactly $N^{\prime}(14)=3$ have period $14$. First we write the 5
periodicities of $B=\\{1,13\\}$, given by

$\mathcal{Q}(14)/\simeq=\Big{\\{}\left[(01)(011)^{4}\right],\
\left[(01)^{4}(011)^{2}\right],\ \left[(01)^{3}(011)(01)^{1}(011)\right],\
\left[((01)^{2}(011))^{2}\right],\ \left[(01)^{7}\right]\Big{\\}}.$

Next, we permute these strings. $3^{\text{-}1}\equiv 5\pmod{14}$, so we
compute $Y=\sigma_{5,14}(X)$. For the first string:

$n$ | $\mathbf{0}$ | $\mathbf{1}$ | $\mathbf{2}$ | $\mathbf{3}$ | $\mathbf{4}$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ | $13$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$X$ | $\mathbf{0}$ | $\mathbf{1}$ | $\mathbf{0}$ | $\mathbf{1}$ | $\mathbf{1}$ | $0$ | $1$ | $1$ | $0$ | $1$ | $1$ | $0$ | $1$ | $1$
$\sigma(X)$ | $\mathbf{0}$ | $0$ | $1$ | $\mathbf{1}$ | $1$ | $0$ | $\mathbf{0}$ | $1$ | $1$ | $\mathbf{1}$ | $0$ | $1$ | $\mathbf{1}$ | $1$
$5n\pmod{14}$ | $\mathbf{0}$ | $5$ | $10$ | $\mathbf{1}$ | $6$ | $11$ | $\mathbf{2}$ | $7$ | $12$ | $\mathbf{3}$ | $8$ | $13$ | $\mathbf{4}$ | $9$

This yields $\sigma_{5,14}\big{(}01(011)^{4}\big{)}=(0^{2}1^{3})^{2}(01^{3})$.
Repeating this procedure, we get the following:

$\displaystyle\sigma_{5,14}\big{(}01(011)^{4}\big{)}$ $\displaystyle=$
$\displaystyle=(0^{2}1^{3})^{2}(01^{3})$
$\displaystyle\sigma_{5,14}\big{(}(01)^{4}(011)^{2}\big{)}$
$\displaystyle=01^{3}0^{3}1^{3}(01)^{2}$ $\displaystyle\simeq
1^{2}0^{3}1^{3}(01)^{3}$
$\displaystyle\sigma_{5,14}\big{(}(01)^{1}011(01)^{3}011\big{)}$
$\displaystyle=0^{2}1^{3}0^{3}1^{5}0$ $\displaystyle\simeq
0^{3}1^{3}0^{3}1^{5}$
$\displaystyle\sigma_{5,14}\big{(}(01)^{2}011)^{2}\big{)}$
$\displaystyle=01^{4}0^{3}1^{4}0^{2}$ $\displaystyle\simeq(0^{3}1^{4})^{2}$
$\displaystyle\sigma_{5,14}\big{(}(01)^{7}\big{)}$ $\displaystyle=$
$\displaystyle=(01)^{7}$ $\mathcal{W}^{\\{3,11\\}}\\!/\\!\simeq\ \
=\Big{\\{}\left[\big{(}\,(0^{2}1^{3})^{2}(01^{3})\,\big{)}^{\infty}\right],\left[\big{(}\,1^{2}0^{3}1^{3}(01)^{3}\,\big{)}^{\infty}\right],\left[\big{(}\,0^{3}1^{3}0^{3}1^{5}\,\big{)}^{\infty}\right],\left[(0^{3}1^{4})^{\infty}\right],\left[(01)^{\infty}\right]\Big{\\}}$

Note that the period lengths of $2$, $7$, and $14$ are conserved under the
permutation, as shown in Corollary 3.9.2. This procedure yields all 5
periodicites of $\\{3,11\\}$.

The asympotic behavior of these functions is generally well behaved. Because
$|z|=|\bar{z}|<1$, where $z$ and $\bar{z}$ are the non-real roots of
$x^{3}-x-1$, we have the convergence
$Q(\ell)=\phi^{\ell}+z^{\ell}+{\bar{z}}^{\ell}\underset{{}^{\ell\to\infty}}{\to}\phi^{\ell}$.333For
all $\ell\geq 10$, we have the exact equality
$Q(\ell)=\text{round}(\phi^{\ell})$. For the following analysis, let
$A=\\{a,b\\}=g\\{\tilde{a},\tilde{b}\\}$ with $g=\gcd(a,b)$, and assume that
$\tilde{a}+\tilde{b}\geq 2.37\ln g$, which excludes relatively few sets. Then
$\left\lvert\mathcal{W}^{\\{a,b\\}}\right\rvert=Q(\tilde{a}+\tilde{b})^{g}\sim\phi^{a+b}$.
The set of seeds $\\{S\mid S\in\\{0,1\\}^{b}\\}$ has cardinality
$2^{b}\geq\sqrt{2}^{a+b}$. Because $\phi\approx 1.32<\sqrt{2}$ this means that
the set of seeds grows faster than the sequences they generate, the number of
seeds converging to the same sequence $\\{w\\}$ grows exponentially as $a+b$
increases. This approximation of $Q(\ell)$ also implies that
$N^{\prime}(\ell)\sim\phi^{\ell}/\ell$ and $N(\ell)\sim N(\ell)$. We can can
also derive $\phi^{L}/L\sim N^{\prime}(L,g)\sim N(L,g)$, giving a strong
estimation of the of the number of possible period structures for large $a,b$.

##  4 The $\\{1,b,c\\}$ case

Analogously to Section 3.1, a good starting point for understanding the
$\\{a,b,c\\}$ game is the $\\{1,b,c\\}$ game. This case was studied by Ho in
[9, sec. 2], where he solves the game for $c<4b$. We provide a full analysis
by constructing $\\{w^{\\{1,b,c\\}}\\}$ for all $b$ and $c$ with no seed,
where most importantly we specify the existence and structure of preperiods.

For the remainder of the paper we will use $x:\equiv y\pmod{z}$ to define $x$
as the least non negative remainder of $y$ modulo $z$.

######  Theorem 4.1.

Suppose we have some $1<b<c$, and let $A=\\{1,b,c\\}$. Denote $q:=\left\lfloor
c/(b+1)\right\rfloor$, $r:\equiv c\pmod{b+1}$. This means $c=q(b+1)+r$.
Additionally let $k:=b/2$ and $\gamma:=\frac{b-r-2}{2}$; we will only use
these when they take on integer values.

Case | Conditions | $\operatorname{Per}(A)$ | $\operatorname{PrePer}(A)$ | $\\{w^{A}\\}$
---|---|---|---|---
i |  $b,c$ odd, | $2$ | $0$ | $\left[01\right]^{\infty}$
ii |  $b$ odd, $c$ even, | $b+c$ | $0$ | $\left[(01)^{c/2}1^{b}\right]^{\infty}$
iii |  $b$ even, $c=b+1$ | $2b$ | $0$ | $\left[(01)^{k}1^{b}\right]^{\infty}$
iv |  $b$ even, $r\in\\{1,b\\}$ | $b+1$ | $0$ | $\left[(01)^{k}1\right]^{\infty}$
v |  $b$ even, $r>1$ odd | $b+c$ | $0$ | $\left[((01)^{k}1)^{q+1}1^{r-1}\right]^{\infty}$
vi |  $b$ even, $r=b-2$ | $c+1$ | $0$ |  $\left[((01)^{k}1)^{q}(01)^{k-1}1\right]^{\infty}$
vii |  $b$ even, $c>b+1$, $r<b-2$ even, $q>\gamma$ | $c+1$ | $\gamma(b+c+2)-b-1$ |  Equation 17
viii |  $b$ even, $c>b+1$, $r<b-2$ even, $q<\gamma$ | $b+c$ | $q(b+c+2)-b-1$ |  Equation 17
ix |  $b$ even, $c>b+1$, $r<b-2$ even, $q=\gamma$ | $b-1$ | $q(b+c+2)-a-1$ |  Equation 17

Figure 1: Theorem 4.1 proves that $\operatorname{PrePer}(\\{1,b,c\\})\neq 0$
exactly when $b$ is even, $c>b+1$, and $r<b-2$ is even, with $r:\equiv
c\pmod{b+1}$.

The last three cases yield the most interesting results, providing an exact
specification of the existence and structure of preperiods. These can be
visualized in Figures 1 and 2.

###### Proof (i).

If $b$ and $c$ are odd, then they are both extensions of $\\{1\\}$ as in
Example 2.11, so $\\{w^{A}\\}=\\{w^{\\{1\\}}\\}=(01)^{\infty}$. ∎

###### Proof (ii).

Suppose $b$ is odd and $c$ is even. For $n<c$, $w(n-c)=1$, so
$w(n)=1-\min\\{w(n-1),w(n-b),1\\}$, and therefore
$w^{A}(n)=w^{\\{1,b\\}}(n)=w^{\\{1\\}}(n)$, because $b$ is an extension of
$\\{1\\}$. Thus $\\{w^{A}\\}=(01)^{c/2}\underset{c}{\ldots}$ Now for all
$n\in[c,c+b)$, we find that $n-b<c$ and $n-c<c$. Therefore if $n$ is odd, then
$n-b$ is even so $w(n-b)=0$ and therefore $w(n)=1$. If $n$ is even then $n-c$
is even so $w(n-c)=0$ and therefore $w(n)=1$. Thus:

$\\{w^{A}\\}=(01)^{c/2}1^{b}\underset{b+c}{\ldots}$

Because $w^{A}(b+c-1)=1$, Corollary 2.12.2 of the translating zeros lemma
implies that this is the entire period with no preperiod.

∎

###### Proof (iii).

Suppose $b=2k$ and $c=b+1$. For $n<c$ we have a single period of $\\{1,b\\}$,
specifically $\\{w^{A}\\}=(01)^{k}1\underset{c}{\ldots}$ Next, for
$n\in[b+1,2b)$, we find that $n-b<b+1$ and $n-c<b$. If $n$ is odd, then $n-c$
is even so $w(n-c)=0$ and thus $w(n)=1$. If $n$ is even, then $n-b$ is even so
$w(n-b)=0$ and thus $w(n)=1$. This yields
$\\{w^{A}\\}=(01)^{k}1^{b}\underset{b+c}{\ldots}$. Because
$\vec{v}(b+c)=\vec{v}(0)=1^{c}$, this is the entire period with no preperiod,
as implied by Lemma 2.13. ∎

###### Proof (iv).

Suppose $b=2k$ and $r\in\\{1,b\\}$. Then $c$ is an extension of $\\{1,b\\}$ by
Proposition 2.10, so
$\\{w^{A}\\}=\\{w^{\\{1,b\\}}\\}=\big{(}(01)^{k}1\big{)}^{\infty}$. ∎

###### Proof (v).

Suppose $b=2k$ and $r>1$ is odd. As above, for the first $c$ elements of the
sequence, $\\{w^{A}\\}$ is equal to $\\{w^{\\{}1,b\\}\\}$.

$\\{w^{\\{1,2k\\}}\\}=\big{(}(01)^{k}1\big{)}^{q}(01)^{\frac{r\text{-}1}{2}}0\underset{c}{\ldots}$

Now let $n=q(b+1)+m$ for $m\in[r,b)$. This means that $n-b<q(b+1)$ and
$n-c=m-r$. If $m$ is odd, then $n-b$ is odd so $w(n-b)=0$, so $w(n)=1$. If $m$
is even, then $w(n-1)=1$ and $w(n-b)=1$ and $w(n-c)=w(m-r)=1$, so $w(n)=0$.
This extends the sequence to

$\\{w^{A}\\}=\big{(}(01)^{k}1\big{)}^{q}(01)^{k}\underset{q(b+1)+b}{\ldots}$

We just showed $w(q(b+1))=0$, so $w(q(b+1)+b)=1$.

$\\{w^{A}\\}=\big{(}(01)^{k}1\big{)}^{q}(01)^{k}1\underset{(q+1)(b+1)}{\ldots}$

Now let $n=(q+1)(b+1)+m$ for $m\in[0,r-1)$. If $m$ is odd, then
$n-b=q(b+1)+m+1$, which has an even remainder less than $b$, so $w(n-b)=0$ and
therefore $w(n)=1$. If $m$ is even, then $n-c=b+1-(r-m)$, which is even and
less than $b+1$, so $w(n-c)=0$ and therefore $w(n)=1$. We then extend the
sequence.

$\\{w^{A}\\}=\big{(}(01)^{k}1\big{)}^{q}(01)^{k}1^{r}\underset{b+c}{\ldots}=\big{(}(01)^{k}1\big{)}^{q+1}1^{r-1}\underset{b+c}{\ldots}$

Because $w^{A}(b+c-1)=1$, we may again apply Corollary 2.12.2 to claim that
this is the complete period with no preperiod.

Note that if $r=1$, this solution still works and has sub-period $b+1$, which
agrees with (iv). ∎

Figure 2: Theorem 4.1 proves that
$\operatorname{PrePer}(\\{1,b,c\\})=\min\left(\left\lfloor\frac{c}{b}\right\rfloor,\frac{a-r-2}{2}\right)(b+c+2)-b-1$
whenever it is nonzero. This is approximately quadradic in $c$ when $c$ is
close to $b$, and transitions to linear when $c\gg b$.

###### Proof (vi, vii, viii, ix).

Assume $b=2k$, $r$ is even, and $c>b+1$, and recall $\gamma=\frac{b-r-2}{2}$.
All four of the remaining cases are expressed in the following equation.
Interestingly, the preperiod structure is the same for all cases.

$\\{w^{A}\\}\\!=\sum_{i=0}^{\min(q,\gamma)-1}\Big{(}((01)^{k}1)^{q-i}((01)^{k-1}1)^{i}(01)^{r/2+i}1^{2(\gamma-i)+1}(01)^{k-(\gamma-i)}1\Big{)}\\\
\left(\begin{cases}((01)^{k}1)^{q-\gamma}((01)^{k-1}1)^{\gamma+1}&\gamma\leq
q\\\ ((01)^{k-1}1)^{q}(01)^{r/2+q}1^{2(\gamma-q)+1}(01)^{r/2+q}1&\gamma\geq
q\end{cases}\right)^{\infty}$ (17)

A proof of this Equation is given in Subsection 4.1. We simply check that the
recurrence relation is satisfied.

In case (vi) where $r=b-2$, this means $\gamma=0$ so the summation is empty
and there is no preperiod. Because we assume $q\geq 1$, this falls into the
$\gamma\leq q$ case of Equation 17, which has length $q(b+1)+(b+1)-2=c+1$.

In the remaining cases both $q$ and $\gamma$ are nonzero, and each term in the
preperiod summation has length

$(q-i)(b+1)+i(b-1)+(r+2i)+2(\gamma-i)+1+2(k-(\gamma-i))+1\\\
=q(b+1)-2i+r+2i+2k+2=c+b+2.$

Examine the last $b+1$ values of the last term in the summation,
$2^{2(\gamma-\min(q,\gamma)+1)}(01)^{k-(\gamma-\min(q,\gamma)+1)}1$. If
$\gamma\leq q$, this is $1^{2}(01)^{k-1}1$, which is equal to the last $b+1$
values of the period structure. If $q\leq\gamma$, this is equal to
$2^{2(\gamma-q+1)}(01)^{k-\gamma+q-1}1=2^{2(\gamma-q+1)}(01)^{r/2+q}$, which
is also equal to the last $b+1$ values of the period structure. This implies
that the preperiod transitions into the period $b+1$ steps earlier than
depicted in Equation 17, and has length $\min(q,\gamma)(b+c+2)-b-1$.

In cases (vii) and (viii), $\operatorname{Per}(A)$ can be computed simply by
counting the length of the strings in Equation 17. The period for $\gamma\leq
q$ has length

$(b+1)(q-\gamma)+(b+1-2)(\gamma+1)=(b+1)q-2\gamma+b-2+1=(b+1)q+r+1=c+1.$

The period for $q\leq\gamma$ has length

$q(a+1-2)+(r+2q)+(2\gamma-2q+1)+(r+2q)+1=q(a+1)+2r+2\gamma+2=b+a.$

In case (ix), where $\gamma=q$, recall that $r+2\gamma=2k-2$. This allows us
to simplify $r/2+q=r/2+\gamma=k-1$, so the two period structures are
equivalent and can be expressed as $((01)^{k-1}1)^{\infty}$, which has period
$b-1$.

We might also notice that Equation 17 also holds if $r=b$ (with no preperiod)
and agrees with case (iv). In this case we would have $\gamma=-1$ so
$\gamma\leq q$ and $\\{w^{A}\\}=((01)^{k}1)^{\infty}$. ∎

One result of this is that preperiod lengths can be arbitrarily longer than
periods in the $\\{1,b,c\\}$ case. This can be seen in Figure 2, where the
preperiod length appears quadratic in $c$.

######  Example 4.2.

Let $b=2k$ and $c=k(b+1)$. Then $A=\\{1,2k,2k^{2}+k\\}$. This means $q=k$,
$r=0$, and $\gamma=k-1$. Noting that $\gamma<q$, Equation 17 yields

$\\{w^{A}\\}\\!=\sum_{i=0}^{k-2}\Big{(}((01)^{k}1)^{k-i}((01)^{k-1}1)^{i}(01)^{i}1^{2(k-i)-1}(01)^{i+1}1\Big{)}\\\
\left((01)^{k}1((01)^{k-1}1)^{k}\right)^{\infty}$ (18)

and Theorem 4.1 (case vii) gives $\operatorname{Per}(A)=2k^{2}+k+1$, and
$\operatorname{PrePer}(A)=(k-1)(2k+2k^{2}+k+2)-2k-1=2k^{3}+k^{2}-3k-3$.

If we instead choose $b=2k$ and $c=(k-1)(b+1)$, we would have $q=\gamma$ (case
ix) so $\operatorname{Per}(A)=2k-1$ and
$\operatorname{PrePer}(A)=2k^{3}-3k^{2}+2k-4$.

For general 3-sets, Althöfer and Bülterman [1, problem (vi)] provided the
example $A=\\{2s,4s+1,22s+2\\}$ with $\operatorname{Per}(A)=26s+3$, though
they err in giving $\operatorname{PrePer}(A)=24s^{2}-4s+1$ for $s\in[2,20]$
while actually $\operatorname{PrePer}(A)=24s^{2}-4s-1$ for all $s\in[2,200]$.
Another example follows from [6, thm 2]. If $A=\\{k,k+2,2k+3\\}$, then
$\operatorname{PrePer}(A)=\frac{1}{2}(3k^{2}-5)$ and
$\operatorname{Per}(A)=2$. Thus for general $3$-sets,
$\operatorname{PrePer}(A)$ is not bounded by any function of
$\operatorname{Per}(A)$, whereas for $A=\\{1,b,c\\}$, Theorem 4.1 shows that
$\operatorname{PrePer}(A)=\mathcal{O}(\operatorname{Per}(A)^{3})$.

In Section 3, we used the $A=\\{1,b\\}$ case to characterize all possible
$2$-sets using a permutation of $w^{A}$. A similar strategy may be possible if
we could characterize all periodicities of $\\{1,b,c\\}$, though this would be
more complicated. In particular, note that the length of the periods are
highly dependent on seeds, unlike the $\\{a,b\\}$ case. An example of this is
proven in Section 6 and visualized in Figure 7.

Suppose $A=\\{a,b,c\\}$ and we are given any string $Y$ with $|Y|=p$. If
$\gcd(a,p)=1$, then we let $a^{\text{-}1}$ be the multiplicative inverse of
$a$ in $\mathbb{Z}^{\times}_{p}$ and $b^{\prime}:\equiv
a^{\text{-}1}b\pmod{p}$ and $c^{\prime}:\equiv a^{\text{-}1}c\pmod{p}$. We see
$X=\sigma_{a,p}(Y)$ is a permutation of $Y$, so we could show in a manner
similar to Theorem 3.9 that $Y^{\infty}\in\mathcal{W}^{\\{a,b,c\\}}$ if and
only if $X^{\infty}\in\mathcal{W}^{\\{1,b^{\prime},c^{\prime}\\}}$. Thus as
long as $p$ and $a$ are coprime, we have
$\mathcal{W}^{a,b,c}(p)=\sigma_{a^{\text{-}1},p}\left[\mathcal{W}^{1,b^{\prime},c^{\prime}}(p)\right]$.
This observation carries little information without further understanding of
$\mathcal{W}^{1,b,c}$.

As an example we apply Lemma 6.1. Choose any $n\in\mathbb{N}$ and $d\geq 1$.
Let $b=4n+2d+1$ and let $p=2(n+1)b+1$. Lemma 6.1 will imply that
$p\in\mathcal{P}^{\\{1,b,b+1\\}}$. 2 is coprime to $p$, so calculate that
$2^{\text{-}1}=(n+1)b+1$ and
$2^{\text{-}1}b=(2n+d)+2^{\text{-}1}=(n+1)b+2n+d+1$, and finally
$2^{\text{-}1}(b+1)=2n+d+1$. Therefore there is some seed $S$ such that
$\operatorname{Per}(\\{2,2n+d+1,(n+1)b+2n+d+1\\},S)=2(n+1)b+1$.

###  4.1 Building the preperiod sequence for $\\{1,b,c\\}$

The statements in Theorems 4.1, 5.1, and Lemma 6.1 are somewhat tedious, so we
provide three proofs of distinct flavors. In this section we provide a visual
verification of Equation 17 to complete the proof of Theorem 4.1.

###### Proof.

We claim that if $b=2k$, $q=\left\lfloor c/(b+1)\right\rfloor$, $r=c-qb$ is
even $c>b+1$, and $\gamma=\frac{b-r-2}{2}$, then Equation 17 holds.

To verify the construction of the preperiod, we will confirm that for each
term $i\in\\{0,\ldots,\min(q-1,\gamma)\\}$, the recurrence relation holds. If
$i=0$, note that the first $c$ entries proceed as $w^{1,b}$, so
$\\{w^{A}\\}=\big{(}(01)^{k}1)^{q}(01)^{r/2}\underset{{}^{c}}{\ldots}$, which
agrees with the $i=0$ term of Equation 17. Thus when considering prefixes we
may assume $i\geq 1$. Suppose the $i^{\text{th}}$ term starts at entry $m$,
and assume that the previous $i-1$ terms follow Equation 17.

The “alignment diagram” on the left hand side in Figure 3 re-writes the
structure presented in Equation 17 on two lines such that $w^{A}(n)$ on the
first line is horizontally justified with $w^{A}(n-c)$ on the second line. To
interpret this diagram, we simply confirm that for all $n$, if $w^{A}(n)=0$,
then then look directly below to check that $w^{A}(n-c)=1$. Further, if
$w^{A}(n)=1$, then either $w^{A}(n-1)=0$ on the left, or $w^{A}(n-c)=0$
directly below (shown in bold), or neither is true and we must have
$w^{A}(n-b)=0$ (underlined).

$\\{w^{A}(n)\\}=\underset{m}{\ldots}\overbrace{0(10)^{k-1}1\textbf{1}\big{(}(01)^{k-1}01\textbf{1}\big{)}^{q-i-1}}^{\big{(}(01)^{k}1\big{)}^{q-i}}\overbrace{\\!\big{(}(01)^{k-2}01\textbf{1}\big{)}^{i-1}(01)^{k-1}\hskip
58.0pt\textbf{1}}^{\big{(}(01)^{k-1}1)\big{)}^{i}}\overbrace{(01)^{r/2+i-1}01(\textbf{1}\textbf{\text@underline{1}})^{\gamma-i}\textbf{1}}^{\big{(}01\big{)}^{r/2+i}1^{{}^{2(\gamma-i)+1}}}\overbrace{(01)^{k-\gamma+i-1}01\textbf{1}}^{(01)^{k-(\gamma-i)}1}\ldots$
$\\{w^{A}(n-c)\\}=\\!\underset{m-c}{\ldots}\\!1(01)^{k-1}1\underbrace{\\!\textbf{0}\big{(}(10)^{k-1}11}_{\big{(}(01)^{k}1\big{)}^{q-i-1}}\underbrace{\\!\textbf{0}\big{)}^{q-i-1}\\!\big{(}(10)^{k-2}11}_{\big{(}(01)^{k-1}1\big{)}^{i-1}}\underbrace{\\!\textbf{0}\big{)}^{i-1}(10)^{r/2+i-2}1^{2(\gamma-i)+4}}_{\big{(}01\big{)}^{r/2+i-1}1^{{}^{2(\gamma-i+1)+1}}}\underbrace{\textbf{0}\,(10)^{r/2+i-1}11}_{\big{(}01\big{)}^{k-(\gamma-i+1)}1}\underbrace{(\textbf{0}\underline{1})^{\gamma-i}\textbf{0}(10)^{k-\gamma+i-1}11}_{\big{(}01\big{)}^{k}1}\\!\textbf{0}\ldots$
$\\{w^{A}(n)\\}=\underset{m}{\ldots}\overbrace{(01)^{\gamma-i}(01)^{k-(\gamma-i)-1}011\big{(}(01)^{k-1}011\big{)}^{q-i-1}}^{\big{(}(01)^{k}1\big{)}^{q-i}}\overbrace{\big{(}(01)^{k-1}1\big{)}\
\big{(}(01)^{k-1}1\big{)}^{i-1}}^{\big{(}(01)^{k-1}1)\big{)}^{i}}\,\overbrace{\,(01)^{r/2+i}(1\textbf{\text@underline{1}})^{\gamma-i}\hskip
29.0pt1}^{\big{(}01\big{)}^{r/2+i}1^{{}^{2(\gamma-i)+1}}}\,\overbrace{(01)^{k-(\gamma-i)-1}011}^{(01)^{k-(\gamma-i)}1}\ldots$
$\\{w^{A}(n-b)\\}=\\!\underset{m-b}{\ldots}\\!(11)^{\gamma-i}(1\underbrace{\\!\\!0)^{k-(\gamma-i)-1}11}_{(01)^{k-(\gamma-(i-1))}1}\\!\underbrace{\\!0\big{(}(10)^{k-1}110\big{)}^{q-i-1}\hskip
7.0pt(10)^{k-1}1\ \hskip
4.0pt\big{(}(1\\!}_{\big{(}(01)^{k}1\big{)}^{q-i}}\underbrace{\\!\,0)^{k-1}1\big{)}^{i-1}\big{(}(10)^{r/2+i}(1\textbf{0})^{k-r/2-1-i}1\big{)}(1}_{\big{(}(01)^{k-1}1\big{)}^{i}}\underbrace{\\!0)^{r/2+i}\hskip
20.0pt1}_{\big{(}01\big{)}^{r/2+i}}\\!1*\ldots$

Figure 3: Two alignments diagrams re-writing the structure presented in
Equation 17. See text for details.

Consider the additional case where $q\leq\gamma$ and $i=q$. The diagram nearly
holds until the last $b+1$ entries. In particular, we note that
$((01)^{k}1)^{q-i}=\emptyset$, so the $w^{A}(n-c)$ sequence should conclude
with $(01)^{k-1}1(01)0$ instead of $(01)^{k}10$. Therefore the $q^{\text{th}}$
term can be modified to
$((01)^{k-1}1)^{q}(01)^{{r/2}+q}1^{2(\gamma-q)+1}(01)^{k-(\gamma-q)-1}10101$.

The alignment diagram on the right hand side in Figure 3 similarly re-writes
the structure such that $w^{A}(n)$ is horizontally justified with
$w^{A}(n-b)$. We must confirm that if $w^{A}(n)=0$, then directly below,
$w^{A}(n-b)=1$. We also confirm that the underlined entry has $w^{A}(n-b)=0$.

Therefore for all $i\in[0,\ldots,\min(q-1,\gamma)]$, the $i^{\text{th}}$ term
follows the recurrence. Note that the $*$ does not affect the recurrence, but
represents that the value is unknown. This value is $1$ if $i<\gamma$ but $0$
if $i=\gamma$. In either case, the recurrence holds. Now we consider the
$\gamma\leq q$ case. As justified above, after the $\gamma-1^{\text{th}}$
term, the $\gamma^{\text{th}}$ term begins at index $m_{1}$ with

$\displaystyle\\{w^{A}\\}$
$\displaystyle=\underset{m_{1}}{\ldots}\big{(}(01)^{k}1\big{)}^{q-\gamma}\big{(}(01)^{k-1}1)^{\gamma}(01)^{r/2+\gamma}1^{2(\gamma-\gamma)+1}(01)^{k-(\gamma-\gamma)}1\ldots$
$\displaystyle=\underset{m_{1}}{\ldots}\big{(}(01)^{k}1\big{)}^{q-\gamma}\big{(}(01)^{k-1}1)^{\gamma}(01)^{k-1}1(01)^{k}1\ldots$
$\displaystyle=\underset{m_{1}}{\ldots}\big{(}(01)^{k}1\big{)}^{q-\gamma}\big{(}(01)^{k-1}1)^{\gamma+1}(01)^{k}1\ldots$

We now observe that for
$Y=\big{(}(01)^{k}1\big{)}^{q-\gamma}\big{(}(01)^{k-1}1)^{\gamma+1}$, the
sequence $Y^{\infty}$ satisfies the recurrence. Because $Y$ has length $c+1$,
it suffices to check that $Y(n)=1$ if and only if $Y(n-1)=0$ or $Y(n+1)=0$ or
$Y(n-2k)=0$. $Y$ satisfies this criterion by inspection.

Now consider the $q\leq\gamma$ case. As justified above, after the
$q-1^{\text{th}}$ term, the $q^{\text{th}}$ term begins at index $m_{1}$ with

$\displaystyle\\{w^{A}\\}$
$\displaystyle=\underset{m_{1}}{\ldots}((01)^{k}1)^{q-q}((01)^{k-1}1)^{q}(01)^{r/2+q}1^{2(\gamma-q)+1}(01)^{k-(\gamma-q)-1}10101\ldots$
$\displaystyle=\underset{m_{1}}{\ldots}((01)^{k-1}1)^{q}(01)^{r/2+q}1^{2(\gamma-q)+1}(01)^{r/2+q}1\hskip
7.0pt0101\ldots$

Now, we show that for
$Y=((01)^{k-1}1)^{q}(01)^{r/2+q}1^{2(\gamma-q)+1}(01)^{r/2+q}1$, the sequence
$Y^{\infty}$ satisfies the recurrence using alignment diagrams. Note that
$|Y|=b+c$, and we start the diagram at $Y(-1)$ to simplify the diagram.

$\displaystyle Y^{\infty}(n)$ $\displaystyle=\underset{-1}{\ldots}\hskip
7.0pt1\overbrace{\\!\big{(}(01)^{k-2}01\textbf{1}\big{)}^{q-1}(01)^{k-1}\hskip
59.0pt\textbf{1}}^{\big{(}(01)^{k-1}1)\big{)}^{q}}\overbrace{(01)^{r/2+q-1}01\hskip
1.0pt(\textbf{1}\textbf{\text@underline{1}})^{\gamma-q}\textbf{1}}^{\big{(}01\big{)}^{r/2+q}1^{{}^{2(\gamma-1)+1}}}\overbrace{\\!(01)^{r/2+q-1}\hskip
4.0pt01\textbf{1}}^{(01)^{r/2+q}1}\ldots$ $\displaystyle Y^{\infty}(n-c)$
$\displaystyle=\\!\\!\underset{-1-c}{\ldots}\underbrace{\textbf{0}\big{(}(10)^{k-2}11}_{\big{(}(01)^{k-2}1\big{)}^{q-1}}\underbrace{\\!\textbf{0}\big{)}^{i-1}(10)^{r/2+q-1}1^{2(\gamma-q)+2}}_{\big{(}01\big{)}^{r/2+q}1^{{}^{2(\gamma-q)+1}}}\underbrace{\textbf{0}\,(10)^{r/2+q-1}11}_{\big{(}01\big{)}^{r/2+q}1}\underbrace{(\textbf{0}\underline{1})^{\gamma-q}\textbf{0}(10)^{k-\gamma+q-2}\hskip
1.0pt11}_{\big{(}01\big{)}^{k-1}1}\\!\textbf{0}\ldots$

Similarly checking the recurrence for $b$:

$\displaystyle Y^{\infty}(n)$
$\displaystyle=\underset{0}{\ldots}\overbrace{\big{(}(01)^{k-1}\hskip
53.0pt1\big{)}\big{(}(01)^{k-1}1\big{)}^{q-1}}^{\big{(}(01)^{k-1}1)\big{)}^{q}}\,\overbrace{\,(01)^{r/2+q}(1\textbf{\text@underline{1}})^{\gamma-i}\hskip
29.0pt1}^{\big{(}01\big{)}^{r/2+i}1^{{}^{2(\gamma-i)+1}}}\,\overbrace{(01)^{r/2+q}1}^{(01)^{r/2+q}1}\ldots$
$\displaystyle Y^{\infty}(n-b)$ $\displaystyle=\underset{0-b}{\ldots}\hskip
3.0pt(11)^{\gamma-q}(1\underbrace{\\!0)^{k-\gamma+q-1}1\hskip
5.0pt\big{(}(1\\!}_{(01)^{r/2+q}1}\underbrace{\\!\,0)^{k-1}1\big{)}^{q-1}\big{(}(10)^{r/2+q}(1\textbf{0})^{k-r/2-1-i}1\big{)}(1}_{\big{(}(01)^{k-1}1\big{)}^{q}}\underbrace{\\!\\!0)^{r/2+q}1}_{\big{(}01\big{)}^{r/2+q}}\\!\ldots$

These diagrams verify that $Y^{\infty}$ satisfies the recurrence, and this
completes the proof that Equation 17 holds. ∎

##  5 The $\\{a,b,a+b\\}$ case

In [4, p. 531], Berlekamp et. al state without proof that the period lengths
of the $\\{a,b,a+b\\}$ game are quadratic and give a formula for the period
length of the Grundy sequence $\mathcal{G}(n)$. In [1], Althöfer and Bülterman
prove a particular example of this case (Example 5.2). In this section we
provide a proof for the general $\\{a,b,a+b\\}$ game by finding $\\{w^{A}\\}$
explicitly, which was presented as open by Ho in [9, table 4].

######  Theorem 5.1.

Suppose $A=\\{a,b,a+b\\}$ with $a<b$. Define
$k=\left\lfloor\frac{b-1}{2a}\right\rfloor$, $\sigma_{i}:\equiv ib\pmod{a}$,
and $\delta_{i}:=\mathbf{1}(\sigma_{i}>\sigma_{i-1})$, with the exception
$\delta_{1}=0$.444This means $\delta_{i}=1$ if $\sigma_{i}>\sigma_{i-1}$ and
$\delta_{i}=0$ if not. Let $\tilde{a}=a/\gcd(a,b)$. Then

$\\{w^{A}\\}=\begin{cases}\displaystyle\left(\sum_{i=1}^{\tilde{a}-1}\left((0^{a}1^{a})^{k-\delta_{i}}0^{\sigma_{i}}1^{b}0^{a-\sigma_{i}}1^{a}\right)0^{a}1^{a+b}\right)^{\infty}&1\leq
b<a\pmod{2a}\\\
\left((0^{a}1^{a})^{k}0^{a}1^{a+b}\right)^{\infty}&\text{Otherwise}\end{cases}$
(19)

It follows that

$\operatorname{Per}(A)=\begin{cases}\tilde{a}(2b-2ka)&1\leq b<a\pmod{2a}\\\
b+2a\left(k+1\right)&\text{Otherwise}\end{cases}$ (20)

Figure 4: Two plots of $\operatorname{Per}(\\{a,b,a+b\\})$ with fixed $a$.
Note the phase transition from linear period lengths to quadratic, as well as
the dips when $\gcd(a,b)\neq 1$. See Figure 6 for a more extreme example.

Berlekamp et. al [4, p. 531] inspire an alternate formulation of Equation 20.
If we let $b=2ha+\rho$ for $\rho\in(-a,a]$, then the following also holds:

$\operatorname{Per}(A)=\begin{cases}\tilde{a}(2b+\rho)&1\leq\rho<a\\\ \ \
\,2b+\rho&\rho\leq 0\text{ or }\rho=a\end{cases}$

###### Proof.

We separate this proof into $2$ cases, beginning with the simpler linear case.

Case 1: If $b\geq a\pmod{2a}$ or $b\equiv 0\pmod{2a}$, we can let $b=qa+r$ for
odd $q=2k+1$ and $r\in[0,a]$.

For $n<b$ we find $w^{A}(n)=w^{\\{a\\}}(n)$, and
$\\{w^{\\{a\\}}\\}=(0^{a}1^{a})^{\infty}$. Because $q$ is odd,

$\displaystyle\\{w^{A}\\}=\ $ $\displaystyle\
\left(0^{a}1^{a}\right)^{k}0^{a}1^{r}\ \underset{b}{\ldots}$

Next, for all $n\in[b,b+qa)$, we see that if $w(n-b)=0$ then both $w(n)=1$ and
$w(n+a)=1$. This fills in the next portion of the sequence; we use underline
and bold characters to highlight the structure of the recurrence.

$\displaystyle\\{w^{A}\\}=\ $ $\displaystyle\
\left(\underline{0}^{a}1^{a}\right)^{k}\underline{0}^{a}1^{r}\left(\underline{1}^{a}\textbf{1}^{a}\right)^{k}\underline{1}^{a}\textbf{1}^{a}\
\ =\ \ \left(0^{a}1^{a}\right)^{k}0^{a}1^{a+b}\underset{b+qa+a}{\ldots}$

We now observe that $\vec{v}\big{(}b+(q+1)a\big{)}=1^{a+b}=\vec{v}(0)$, which
proves that $\operatorname{Per}(A)=b+2a(k+1)$ with no preperiod. We now move
to the quadratic case.

Case 2: If $1\leq b<a\pmod{2a}$, then we will have $b=qa+r$, for $r\in[1,a)$
and $q=2k$. Again for $n<b$, the sequence is identical to $w^{\\{a\\}}$.

$\displaystyle\\{w^{A}\\}=\ $ $\displaystyle\
\left(0^{a}1^{a}\right)^{k}0^{r}\underset{b}{\ldots}$

Once again for $n\in[b,2b)$, we notice that if $w^{A}(n-b)=0$, then by the
recurrence $w^{A}(n)=w^{A}(n+a)=1$. This means that for all
$n\in[b,2b)\cup[(2b-r)+a,2b+a)$, we have $w(n)=1$, as illustrated in the
equation below. This leaves a gap of length $a-r$. In this gap
$n\in[2b,(2b-r)+a)$, we find $w(n-a)=w(n-b)=w(n-a-b)=1$, so indeed $w(n)=0$.

$\displaystyle\\{w^{A}\\}=\ $ $\displaystyle\
\underbrace{\left(\underline{0}^{a}1^{a}\right)^{k}\underline{0}^{r}}_{b}\underbrace{(\underline{1}^{a}\textbf{1}^{a})^{k}\underline{1}^{r}}_{b}0^{a-r}{\
}\textbf{1}^{r}\underset{2b+a}{\ldots}\ \ =\ \
\left(0^{a}1^{a}\right)^{k}0^{r}1^{b}0^{a-r}{\ }1^{r}\underset{2b+a}{\ldots}$

Because we showed $n\in[2b,2b+a-r)$ has $w(n)=0$, this implies $w(n+a)=1$, so
we may append $(a-r)$ $1$’s after $2b+a$.

$\displaystyle\\{w^{A}\\}=\ $ $\displaystyle\
\left(0^{a}1^{a}\right)^{k}0^{r}1^{b}0^{a-r}{\
}1^{a}\underset{2b+2a-r}{\ldots}$

This completes the first term in the summation, where $\sigma_{1}=r$ and
$\delta_{1}=0$. Using this as a base case for induction, we now show that the
$i+1^{\text{th}}$ term in the summation succeeds the $i^{\text{th}}$ term.
Suppose

$\displaystyle\\{w^{A}\\}=\ $ $\displaystyle\
\ldots\left(0^{a}1^{a}\right)^{k-\delta_{i}}0^{\sigma_{i}}1^{b}0^{a-\sigma_{i}}1^{a}\ldots$

We need only consider recent values of $w(n)$ back to $w(n-a-b)$, so define
the index $m$ such that
$\\{w^{A}\\}=\underset{m}{\ldots}1^{b-a+\sigma_{i}}0^{a-\sigma_{i}}{\
}1^{a}\ldots$ Now let $m_{1}=m+(b-a+\sigma_{i})$ and notice that
$\vec{v}(m_{1})$ ends with a long string of ones. In particular we find that
for all $n\in[m+a+b,m_{1}+b)$, we have $w^{A}(n-a-b)=1$ and $w^{A}(n-b)=1$, so
$w^{A}$ proceeds identically to $w^{\\{a\\}}$ for a length of precisely
$b-2a+\sigma_{i}$. We must now consider sub-cases for parity, where
$\sigma_{i}+r<a$ or $\sigma_{i}+r\geq a$. We show the two cases below

$\displaystyle\\{w^{A}\\}=\ $ $\displaystyle\
\ldots\left(0^{a}1^{a}\right)^{k-\delta_{i}}0^{\sigma_{i}}1^{b}\underbrace{0^{a-\sigma_{i}}1^{a}\
\ \ 0^{a}1^{a}0^{a}1^{a}\ldots}_{b}\underset{m_{1}+b}{\ldots}$
$\displaystyle=\ $ $\displaystyle\
\begin{cases}\underset{m_{1}}{\ldots}\,{0^{a-\sigma_{i}}1^{a}\ \ \
(0^{a}1^{a})^{k-1}0^{\sigma_{i}+r}}\hskip
20.0pt\underset{m_{1}+b}{\ldots}&\sigma_{i}+r<a\\\
\underset{m_{1}}{\ldots}\,{0^{a-\sigma_{i}}1^{a}\ \ \
(0^{a}1^{a})^{k-1}0^{a}1^{\sigma_{i}+r-a}}\underset{m_{1}+b}{\ldots}&\sigma_{i}+r\geq
a\end{cases}$

Note that in the two cases we can plug in $\sigma_{i+1}=\sigma_{i}+r=$ and
$\sigma_{i+1}=\sigma_{i}+r-a$ respectively. In the second case, where
$\sigma_{i}+r\geq a$, then for
$n\in\big{[}(m_{1}+b),(m_{1}+b)+(a-\sigma_{i+1})\big{)}$, we find
$w^{A}(n-a)=0$ so $w^{A}(n-a)=1$. For
$n\in\big{[}(m_{1}+b)+(a-\sigma_{i+1}),(m_{1}+b)+a\big{)}$, we find
$w^{A}(n-a)=w^{A}(n-b)=w^{A}(n-a-b)=1$, so $w(n)=0$. Extend this second case
below, defining $m_{2}$ as the frontier of the sequence:

$\displaystyle\\{w^{A}\\}=\ $ $\displaystyle\
\begin{cases}\underset{m_{1}}{\ldots}\,{0^{a-\sigma_{i}}1^{a}\ \ \
(0^{a}1^{a})^{k-1}0^{\sigma_{i+1}}}\hskip
20.0pt\underset{m_{2}}{\ldots}&\sigma_{i}+r<a\\\
\underset{m_{1}}{\ldots}\,0^{a-\sigma_{i}}1^{a}\ \ \
(0^{a}1^{a})^{k-1}0^{a}\mathbf{1}^{a}0^{\sigma_{i+1}}\underset{m_{2}}{\ldots}&\sigma_{i}+r\geq
a\end{cases}$

This adds another copy of $0^{a}1^{a}$ to the sequence in the second case, and
observe that $\delta_{i+1}=1$ in the first case and $\delta_{i+1}=0$ in the
second. We can therefore combine cases. Additionally, we find that for
$n\in[m_{2},m_{2}+b)$, if $w(n-b)=0$ then $w(n)=w(n+a)=1$. This leads to
another string of $1^{b}$ with a gap of length $a-\sigma_{i+1}$ which is
filled with zeros. This is shown below, where $m_{3}=m_{2}+b+a$,

$\\{w^{A}\\}=\ldots\,(\underline{0}^{a}1^{a})^{k-\delta_{i+1}}\underline{0}^{\sigma_{i+1}}\underbrace{(\underline{1}^{a}\textbf{1}^{a})^{k}\underline{1}^{\sigma_{i+1}}}_{b}\underbrace{0^{a-\sigma_{i+1}}\textbf{1}^{\sigma_{i+1}}}_{a}\underset{m_{3}}{\ldots}$

For $n\in\big{[}m_{3},m_{3}+(a-\sigma_{i+1})\big{)}$, we see $w(n-a)=0$ so
$w(n)=1$. This completes the inductive step as we show below:

$\\{w^{A}\\}=\ldots\left(0^{a}1^{a}\right)^{k-\delta_{i}}0^{\sigma_{i}}1^{b}0^{a-\sigma_{i}}1^{a}\
\ \
\left(0^{a}1^{a}\right)^{k-\delta_{i+1}}0^{\sigma_{i+1}}1^{b}0^{a-\sigma_{i+1}}1^{a}\ldots$

By induction this pattern will repeat. Let $\tilde{a}=\frac{a}{\gcd(a,b)}$,
which is the order of $b$ in $\mathbb{Z}_{a}^{+}$. Thus the
$\tilde{a}^{\text{th}}$ iteration is the first such that
$\sigma_{\tilde{a}}=0$ and $\delta_{\tilde{a}}=0$ so the sequence is

$\\{w^{A}\\}\ \ =\ \
\sum_{i=1}^{\tilde{a}-1}\Big{(}(0^{a}1^{a})^{k-\delta_{i}}0^{\sigma_{i}}1^{b}0^{a-\sigma_{i}}1^{a}\Big{)}\
(0^{a}1^{a})^{k}1^{b}\underset{m_{4}}{\ldots}$ (21)

We see that $\vec{v}(m_{4})=1^{a+b}=\vec{v}(0)$, so this is the entire period.
We see that the $i^{\text{th}}$ term of the summation has length
$2ka-2a\delta_{i}+b+2a$, and there are $\tilde{a}$ total terms. We also
compute that $\frac{r\cdot\tilde{a}}{a}$ is the number of terms $j$ for which
$\sigma_{j}<\sigma_{j-1}$, so if we include the first term $\delta_{1}=0$ and
exclude the last term $\delta_{\tilde{a}}=0$, there are precisely
$r/\gcd(a,b)$ terms in the summation where $\delta_{j}=0$, and the rest have
$\delta_{i}=1$. Therefore
$\sum_{i=1}^{\tilde{a}-1}\delta_{i}=(\tilde{a}-1)-r/\gcd(a,b)$. We conclude
that the total period length is

$\displaystyle\operatorname{Per}(A)$
$\displaystyle=\sum_{i=1}^{\tilde{a}-1}(2ka-2a\delta_{i}+b+2a)+2ka+b$
$\displaystyle=(2ka(\tilde{a}-1)-2a((\tilde{a}-1)-r/\gcd(a,b))+b(\tilde{a}-1)+2a(\tilde{a}-1))+2ka+b$
$\displaystyle=2ka\tilde{a}+2ar/\gcd(a,b)+b\tilde{a}$
$\displaystyle=3\tilde{a}b-2ka\tilde{a}\qed$

The following example is given as a Theorem in [1].

    -------------1111111111111---11111111111111111111111111111----------1111111111111
                              ------11111111111111111111111111111-------1111111111111
                              ---------11111111111111111111111111111----1111111111111
                              ------------11111111111111111111111111111-1111111111111
    -------------1111111111111--11111111111111111111111111111-----------1111111111111
                              -----11111111111111111111111111111--------1111111111111
                              --------11111111111111111111111111111-----1111111111111
                              -----------11111111111111111111111111111--1111111111111
    -------------1111111111111-11111111111111111111111111111------------1111111111111
                              ----11111111111111111111111111111---------1111111111111
                              -------11111111111111111111111111111------1111111111111
                              ----------11111111111111111111111111111---1111111111111
                              -------------111111111111111111111111111111111111111111

Figure 5: Let $a=13$, $b=2a+3$, and $A=\\{13,29,42\\}$. We compute
$\operatorname{Per}(A)=793$, and the period structure is shown above, with -
used for $0$.

######  Example 5.2.

[1, Thm 3.1] Let $A=\\{a,2a+1,3a+1\\}$. Then Equation (19) gives the following
sequence, where $b=2a+1$, $k=1$, and $\sigma_{i}=i$ so $\delta_{i}=1$ for all
$i\in[1,a-1)$.

$\displaystyle\\{w^{A}\\}\ \ $ $\displaystyle=\ \
\Bigg{(}0^{a}1^{a}\sum_{i=1}^{a-1}\Big{(}0^{i}1^{b}0^{a-i}1^{a}\Big{)}\
0^{a}1^{a+b}\Bigg{)}^{\infty}$ $\displaystyle=\ \ \Bigg{(}0^{a}1^{a}\ \
0^{1}1^{b}0^{a-1}1^{a}\ \ \ 0^{2}1^{b}0^{a-2}1^{a}\ \ \
0^{3}1^{b}0^{a-3}1^{a}\ \ \ \ldots\ \ \ 0^{a}1^{a+b}\Bigg{)}^{\infty}$

Additionally
$\operatorname{Per}(A)=(6a^{2}+3a)-2a^{2}=4a^{2}+3a\sim\frac{2}{9}\max(A)^{2}$.

This class of sets appears to be the only case for $|A|=3$ which can have
superlinear period lengths with no seed. Further generalizations using this
result and Theorem 4.1 might bring the following conjecture within reach.

######  Conjecture 1.

For all $a<b<c$ such that $a+b\neq c$,

$\operatorname{Per}(\\{a,b,c\\})<2c$ (22)

We have verified Conjecture 1 computationally for all
$\\{a,b,c\\}\in{[200]\choose 3}$. If this conjecture is true, it must relate
in part to some invariant of the structure caused by the initial seed of
$1^{\alpha}$, because it fails entirely for different seeds, even if $a,b,$
and $c$ are coprime. This invariant would therefore be carried through the
quadratic length preperiods seen in Section 4.

Figure 6: The period lengths for $\\{a,b,a+b\\}$ where $a=360$, a superior
highly composite number.

##  6 Super-polynomial Period lengths with initial Seeds.

In this section we consider a particular family of sets which demonstrate that
super-polynomial period lengths exist for 3-sets, given properly chosen
initial seeds. This family will relate to an intersection of the cases of
Sections 4 and 5.

######  Lemma 6.1.

For any $n\in\mathbb{N}$, choose some odd $b>4n+1$ and let $A=\\{1,b,b+1\\}$
and $S=(01^{3})^{n}$. Then $\operatorname{Per}(A,S)=2(n+1)b+1$ and
$\operatorname{PrePer}(A,S)=0$.

A proof of this Lemma is found in Section 6.1. If we denote $b=4n+1+2d$, where
$d\geq 1$, then the structure of the periodicity is exactly

$\\{w^{A,S}\\}=\ldots\left(\sum_{i=0}^{n-1}\Big{(}(11)^{d}(1^{3}0)^{i}11(01^{3})^{n-i}\
(01)^{d}0(1^{3}0)^{i}11(01^{3})^{n-i-1}0\Big{)}\ (11)^{d}(1^{3}0)^{n}1^{2}\
(01)^{d}0(1^{3}0)^{n}\right)^{\infty},$

To choose a seed generating this structure it suffices to choose any sub-
string of length $a+1$, so we choose the first $a+1$ entries, namely
$(11)^{d}11(01^{3})^{n}\approx(01^{3})^{n}$. Lemma 6.1 contradicts the
generalization of Conjecture 1 over all seeds, since it implies quadratic
period lengths. Figure 7 plots all period lengths for $\\{1,b,b+1\\}$, which
shows that this Lemma only scratches the surface of the periodicities of
$3$-sets.

Figure 7: This figure shows all periods of $\\{1,b,b+1\\}$ for $b+1\leq 35$.
The points highlighted in blue are given by Lemma 6.1 and the points in red
are the default periods. Note that some points close together are overlapping.
For example,
$\mathcal{P}^{\\{1,31,32\\}}=\\{3,7,11,21,33,63,125,167,187,249,251,311,313,$
$373,375,377,435,437,439,497,499,501,503,563,565,629\\}$, while Lemma 6.1
gives only $\\{63,125,187,$
$249,311,373,435,497\\}$.

######  Theorem 6.2 (Superpolynomial Period Lengths).

For $n\geq 1$, define $b_{n}=4n-1$, $A_{n}=\\{n,nb_{n},nb_{n}+n\\}$, and
$S_{(n)}=\sum_{j=1}^{n-1}0^{j}1^{b_{n}-j}$. For the family of pairs
$\\{A_{n},S_{(n)}\\}_{n=1}^{\infty}$, where $\alpha_{n}=\max(A_{n})$, it holds
that

$\operatorname{Per}(A_{n},S_{(n)})=e^{\Omega(\sqrt{\alpha_{n}})}.$

###### Proof.

Fix $n$, so we have $b=4n-1$ and $A=\\{n,bn,bn+n\\}$. We now construct the
seed $S$ dependent on $n$. Because $A$ has greatest common divisor $n$, let
$B=\\{1,b,b+1\\}$ and apply Multiplicative Linearity Proposition 2.7 to see
that the parallel sequences satisfy
$(w^{A,S})_{i}(m)=w^{A,S}(mn+i)=w^{B,S_{i}}(m)$ where
$S_{i}\in\\{0,1\\}^{b+1}$ for $i\in\\{0,\ldots,n-1\\}$. We now apply Lemma 6.1
by letting $S_{i}=(01^{3})^{i}\approx 1^{4(n-i)}(01^{3})^{i}$, so we have
$\operatorname{Per}(B,S_{i})=2(i+1)b+1$. By combining all $S_{i}$ in parallel,
this construction yields
$S=\sum_{i=0}^{n-1}1^{n-i}0^{i}1^{3n}=\sum_{j=1}^{n}0^{i}1^{b-i}$. Now,
suppose $\\{w^{A,S}\\}$ is periodic over some $p\in\mathbb{N}$. This implies
that for all $m\in\mathbb{N}$ and $i\in\\{0,\ldots,n-1\\}$, we have

$w^{B,S_{i}}(m)=w^{A,S}(mn+i)=w^{A,S}(mn+i+np)=w^{B,S_{i}}(m+p),$

so $\\{w^{B,S_{i}}\\}$ must also be periodic over $p$, i.e.
$\operatorname{Per}(B,S_{i})\mid p$. Because this is true for all $i$, we
conclude that $\operatorname{lcm}\\{2(i+1)b+1\mid 0\leq
i<n\\}\leq\operatorname{Per}(A_{n},S)$. A result from [2, Problem 10797]
regarding the lcm of arithmetic progressions implies a somewhat loose bound of
$\operatorname{lcm}(2b+1,4b+1,6b+1,\ldots,2na+1)\geq e^{n-o(n)}$.555In
particular it says that
$\lim_{n\to\infty}\frac{\log(\operatorname{lcm}(\ldots))}{n}=\frac{1}{\varphi(k)}\sum\frac{2b}{m}$
with the summation taken over units of $\mathbb{Z}_{2b}^{\times}$. This is an
average of numbers greater than $1$. Therefore for all $n$, we note that
$\alpha_{n}\sim 4n^{2}$, and conclude
$\operatorname{Per}(A_{n},S_{n})=e^{\Omega(n)}=e^{\Omega(\sqrt{\alpha_{n}})}$.
∎

Table 2 demonstrates the construction for $n=2$. This family proceeds as
follows

  * •

$n=1$, $b=3$, $A_{1}=\\{1,3,4\\}$, $S_{1}=\emptyset$, and
$\operatorname{Per}(A_{1},S_{1})=\operatorname{lcm}\\{7\\}=7$

  * •

$n=2$, $b=7$, $A_{2}=\\{2,14,16\\}$, $S_{2}=01^{6}$,
$\operatorname{Per}(A_{2},S_{2})=2\cdot\operatorname{lcm}\\{15,29\\}=870$

  * •

$n=3$, $b=11$, $A_{3}=\\{3,33,36\\}$, $S_{3}=01^{10}0^{2}1^{9}$,
$\operatorname{Per}(A_{3},S_{3})=3\cdot\operatorname{lcm}\\{23,45,67\\}=208\,035$

  * •

$n=4$, $b=15$, $A_{4}=\\{4,60,64\\}$, $S_{4}=01^{14}0^{2}1^{13}0^{3}1^{12}$,
$\operatorname{Per}(A_{4},S_{4})=4\cdot\operatorname{lcm}\\{31,61,91,121\\}=83\,287\,204$

  * •

$n=5$, $b=19$, $A_{5}=\\{5,95,100\\}$,
$S_{5}=01^{18}0^{2}1^{17}0^{3}1^{16}0^{4}1^{15}$, and
$3\,364\,005\,645\mid\operatorname{Per}(A_{5},S_{5})$; we have not computed
the exact period.

It is natural to predict that we have a multiple of $n$ in the period length,
but we have not proven this to be the case. To prove Theorem 6.2 we used a
rough bound on $\operatorname{lcm}\\{2b+1,\ldots,2nb+1\\}$ and the few
periodicities from Lemma 6.1, as shown in Figure 7. It is unclear if more
periodicities and a stronger bound on their $\operatorname{lcm}$, would yield
an asymptotically better result, but this does not appear to be the case.
Figure 8 shows that $e^{\Omega(\sqrt{\alpha_{n}})}$ appears to be best
possible.

Figure 8: Using the periods from Figure 7, we can construct sets $A_{b}$ with many parallel $\\{1,b,b+1\\}$ periods, specifically we get $A_{b}=|\mathcal{P}^{\\{1,b,b+1\\}}|\cdot\\{1,b,b+1\\}$ and some seed $S$ comprised of $S_{0},\ldots,S_{|\mathcal{P}^{\\{1,b,b+1\\}}|}$ such that $\operatorname{Per}(A_{b},S)\geq\operatorname{lcm}(\mathcal{P}^{\\{1,b,b+1\\}})$. This gives a heuristic for the longest period possible, which appears to approximate $e^{\mathcal{O}(\sqrt{\max(A_{b})})}$. 1 |  |  1 |  |  1 |  |  1 |  |  0 |  |  1 |  |  0 |  |  1 |  |  0 |  |  1 |  |  0 |  |  1 |  |  …
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
|  0 |  |  1 |  |  1 |  |  1 |  |  0 |  |  1 |  |  0 |  |  1 |  |  1 |  |  0 |  |  1 |  |  1 |  …
Table 2: In the construction for Theorem 6.2, we have $A_{2}=\\{2,14,16\\}$.
The sequences $(w^{A,S})_{i}(m)$ for $i\in\\{0,1\\}$ are independent, and
these have periods of lengths $2\cdot 7+1=15$ and $4\cdot 7+1=29$. We find
that $\operatorname{Per}(A_{2},01^{6}))=2\cdot\operatorname{lcm}(15,29)=870$.

###  6.1 Proof of Lemma 6.1.

The final proof uses different approach to the previous ones. Rather than
constructing the sequence from scratch, we will exploit a structural pattern
to extend a simple period. This was the method used to discover Lemma 6.1, and
might be a productive strategy moving forward.

###### Proof.

First, we note that if $n=0$, then Theorems 4.1 and 5.1 coincide to give that
$\operatorname{Per}(A)=2b+1$ with no seed, so we are done. Next, fix $n\geq
1$.

Observe that if $\beta=4n+1$ and $B=\\{1,\beta,\beta+1\\}$ then the string
$X=110(1^{3}0)^{n}$ is a valid period structure of $B$ with period length
$\beta+2$. This follows from the fact that $X^{\infty}(n)=1$ if and only if
$X^{\infty}(n-1)=0$, $X^{\infty}(n+1)=0$, or $X^{\infty}(n+2)=0$, meaning each
zero is separated by $2$ or $3$ ones. We use this fact to explicitly build
period structures for odd $b>\beta$.

Write $2n+1$ copies of $X$ in a $(2n+2)\times(\beta+1)$ grid so that the rows
$0,\ldots,2n+1$ are the following: The $k^{\text{th}}$ even row indexed from
zero reads $(1^{3}0)^{k}11(01^{3})^{n-k}$ and the $k^{\text{th}}$ odd row
reads $0(1^{3}0)^{k}11(01^{3})^{n-k-1}0$, except for the last row, (the
$n^{\text{th}}$ odd row), and this reads $0(1^{3}0)^{n}$. Table 3 gives two
examples of such a filling. Notice that this filling has the following three
properties.

  * •

Reading across all of the rows yields $X^{2n+1}$ in order.

  * •

Even rows are fully filled. These begin and end with strings $1^{3}$ or $11$.
Their length is $\beta+1=|X|-1$ so they contain all of $X$ except for a $0$.

  * •

Odd rows have $\beta-1$ entries, except for row $n$ which has $\beta$ entries.
These begin and end with $0$, and contain all of $X$ except either $1^{3}$ or
$11$.

1 | 1 | 0 | 1 | 1 | 1
---|---|---|---|---|---
0 | 1 | 1 | 0 |  |
1 | 1 | 1 | 0 | 1 | 1
0 | 1 | 1 | 1 | 0 |

1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1
---|---|---|---|---|---|---|---|---|---
0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |  |
1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1
0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |  |
1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1
0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |

Table 3: Left. Setting $n=1$, we get $B=\\{1,5,6\\}$. We place $2n+1=3$ copies
of $X=1101^{3}0$ into a grid, so odd rows start and end with $0$. Right.
Setting $n=2$, we get $B=\\{1,9,10\\}$. We place $5$ copies of
$X=1101^{3}01^{3}0$ into a grid. Alternating copies of $X$ are bolded to
illustrate the pattern.

Denote $x(i,j)$ as the element in row $i$ and column $j$, both indexed from
$0$. We can now re-interpret the recurrence relation on $w^{B}(n)$ in terms of
$x$. The following identities must hold for all $i,j$.

$x(i,j)=\begin{cases}1-\min\\{x(i,j-1),x(i-1,j),x(i-1,j+1)\\}&i\text{ is odd
and }j>0\\\ 1-\min\\{x(i,j-1),x(i-1,j-2),x(i-1,j-1)\\}&i>0\text{ is
even},\beta>j>1\\\ \\\ 1-\min\\{x(i-1,\beta),x(i-1,0),x(i-1,1)\\}&i\text{ is
odd and }j=0\\\ 1-\min\\{x(0,j-1),x(2n+1,j),x(2n+1,j-1)\\}&i=0,\beta>j>0\\\
1-\min\\{x(2n+1,\beta-1),x(2n+1,0),x(2n,\beta)\\}&i=0,j=0\\\
1-\min\\{x(0,\beta-1),x(0,0),x(2n+1,\beta-1)\\}&i=0,j=\beta\\\
1-\min\\{x(i,\beta-1),x(i,0),x(i-1,\beta-2)\\}&i>0\text{ is even},j=\beta\\\
1-\min\\{x(i,0),x(i-1,0),x(i-2,\beta)\\}&i>0\text{ is even},j=1\\\
1-\min\\{x(i-1,\beta-2),x(i-2,\beta),x(i-2,\beta-1)\\}&i>0\text{ is
even},j=0\end{cases}$ (23)

We focus on the first two cases which are the most general. It might also help
to recall that for odd $i$, $x(i,0)=0$ and for even $i$,
$x(i,0)=x(i,1)=x(i,\beta-1)=x(i,\beta)=1$. These follow from the
specifications of the grid filling.

Next, we will choose any odd $b=\beta+2d$ for $d>0$, and let
$A=\\{1,b,b+1\\}$. We will extend the grid to create a period structure for
$A$ with length $2(n+1)b+1$. We add $d$ copies of the first two columns on the
left side, as shown below.

1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1
---|---|---|---|---|---|---|---|---|---|---|---
0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |  |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1
0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 |

=  (11)d+1 0 1 1 1 (01)d+1 1 0 (11)d+1 1 0 1 1 (01)d+1 1 1 0

Table 4: Example of extending the grid for $b=\beta+2d$ with $n=1$ and $d=3$.

We call the elements of this modified grid $y(i,j)$, with $i$ indexed from $0$
and $j$ indexed from $-2d$. Thus for $j\geq 0$ we have $y(i,j)=x(i,j)$. If
$j<0$ is even we have $y(i,j)=x(i,0)$ and if $j<0$ is odd we have
$y(i,j)=x(i,1)$. Because of the specifications for filling $x$, we note that
this entails prepending $(11)^{d}$ to even rows and $(01)^{d}$ to odd rows.

Claim. Reading across the rows of this table yields $Y$, a valid period
structure for $A$ with length ${2(n+1)b+1}$. First we have added $(2n+2)2d$
entries to the table, and we started with $X^{2n+1}$, so the total length is

$(2n+2)2d+(2n+1)(\beta+2)=(2n+2)2d+(2n+2)\beta+1=2b(n+1)+1$

Next we show that the recurrence relation is satisfied. To do this, write the
recurrence relation
$w^{A}(n)=1-\min\\{w^{A}(n-1),w^{A}(n-\beta-2d),w^{A}(n-\beta-1-2d)$ in terms
of $y(i,j)$. The rows are extended by the same length as the recurrence, so
the following rules very are similar to Equation 23.

$y(i,j)=\begin{cases}1-\min\\{y(i,j-1),y(i-1,j),y(i-1,j+1)\\}&i\text{ is odd
and }j>-2d\\\ 1-\min\\{y(i,j-1),y(i-1,j-2),y(i-1,j-1)\\}&i>0\text{ is
even},\beta>j>1-2d\\\ \\\ 1-\min\\{y(i-1,\beta),y(i-1,0),y(i-1,1)\\}&i\text{
is odd and }j=0\\\ 1-\min\\{y(0,j-1),y(2n+1,j),y(2n+1,j-1)\\}&i=0,\
\beta>j>-2d\\\
1-\min\\{y(2n+1,\beta-1),y(2n+1,\beta),y(2n+1,-2d)\\}&i=0,j=-2d\\\
1-\min\\{y(0,\beta-1),y(0,-2d),y(2n+1,\beta-1)\\}&i=0,j=\beta\\\
1-\min\\{y(i,\beta-1),y(i,-2d),y(i-1,\beta-2)\\}&i>0\text{ is even},j=\beta\\\
1-\min\\{y(i,-2d),y(i-1,-2d),y(i-2,\beta)\\}&i>0\text{ is even},j=-2d+1\\\
1-\min\\{y(i-1,\beta-2),y(i-2,\beta),y(i-2,\beta-1)\\}&i>0\text{ is
even},j=-2d\end{cases}$ (24)

From here it is possible to check that the nine cases in Equation 24 hold for
all $j\geq 0$ and $j<0$ using Equation 23, the definition of $y(i,j)$ and the
three properties of the filling. We will show only the two main cases; the
rest follow suit.

If $i$ is odd and $0<j<\beta$, then we confirm

$y(i,j)=x(i,j)=1-\min\\{x(i,j-1),x(i-1,j),x(i-1,j+1)\\}\\\
=1-\min\\{y(i,j-1),y(i-1,j),y(i-1,j+1)\\}.$

If $i$ is odd and $-2d<j\leq 0$ is even, then we know $y(i,j)=x(i,0)=0$, so we
confirm

$y(i,j)=1-\min\\{y(i,j-1),y(i-1,j),y(i-1,j+1)\\}=1-\min\\{1,1,1\\}=0.$

If $i$ is odd and $-2d<j<0$ is odd, then we know $y(i,j)=x(i,1)=1$, so we
confirm

$y(i,j)=1-\min\\{y(i,j-1),y(i-1,j),y(i-1,j+1)\\}=1-\min\\{0,1,0\\}=1.$

If $i>0$ is even and $1<j<\beta$, then

$y(i,j)=x(i,j)=1-\min\\{x(i,j-1),x(i-1,j-1),x(i-1,j-2)\\}\\\
=1-\min\\{y(i,j-1),y(i-1,j-1),y(i-1,j-2)\\}.$

If $i>0$ is even and $-2d+1<j\leq 1$ is odd, then we know $y(i,j)=x(i,1)=1$,
so we confirm

$y(i,j)=1-\min\\{y(i,j-1),y(i-1,j-1),y(i-1,j-2)\\}=1-\min\\{1,0,1\\}=1.$

If $i>0$ is even and $-2d+1<j\leq 0$ is even, then we know $y(i,j)=x(i,0)=1$,
so we confirm

$y(i,j)=1-\min\\{y(i,j-1),y(i-1,j-1),y(i-1,j-2)\\}=1-\min\\{1,1,0\\}=1.$

Such verification can be completed for the seven edge cases to show that
$y(i,j)$ obeys Equation 24, and therefore $Y^{\infty}\in\mathcal{W}^{A}$.

Finally, we check for subperiods of $Y$. Note that as long as $d>0$, there are
exactly $(n+1)$ copies of the substring $(01)^{d+1}$ present in $Y$, each at
the beginning of a row. Additionally, the last row uniquely has length $b$,
meaning the instances of $(01)^{d+1}$ are unequally spaced throughout $Y$.
This prevents a sub-period of $Y$ from occurring. ∎

##  7 Closing

We close the paper by setting up a few conjectures. First, we recall the
observation that the converse of Proposition 2.10 holds for all $(A,S)$ where
$|A|\leq 3$, and state it explicitly in a conjecture.

######  Conjecture 2.

If $|A|\leq 3$, then for all $S\in\\{0,1\\}^{\alpha}$, let
$p=\operatorname{Per}(A,S)$. Then if $kp+x$ is an extension of $A$ for all
$k\in\mathbb{N}_{+}$ and $x\in A$, then $\operatorname{PrePer}(A,S)=0$.

It suffices to check the case $k=1$. If $S=\emptyset$ this is precisely the
converse of Proposition 2.10; otherwise the converse is not true.

The following conjecture is based on computer simulations of
$A\in{[200]\choose 3}$. It provides a very limited characterization of the
general $\\{a,b,c\\}$ case but provides an example of its complex behavior.

######  Conjecture 3.

Suppose $A=\\{a,b,c\\}$ with $1<a<b<c$. Use the division algorithm to obtain
the following variables:

$\displaystyle b$ $\displaystyle=q\ a+r$ $\displaystyle c$
$\displaystyle=q_{c}(a+b)+r_{c}$ $\displaystyle r_{c}$
$\displaystyle=q_{a}(2a)+r_{a}$ $\displaystyle c-a$
$\displaystyle=q_{c}^{\prime}(a+b)+r_{c}^{\prime}$ $\displaystyle
r_{c}^{\prime}$ $\displaystyle=q_{a}^{\prime}(2a)+r_{a}^{\prime}$

Then $\operatorname{Per}(A)=b+c$ and $\operatorname{PrePer}(A)=0$ if and only
if one of the following holds:

  1. (i)

$q$ is even and $r_{c}^{\prime}>0$, $r_{a}^{\prime}\leq r$, and
$2q_{a}^{\prime}\leq q$, and if $2q_{a}^{\prime}=q$ then $r_{a}^{\prime}\leq
2r-a$.

  2. (ii)

$q$ is odd and $r\neq 0$, $r\leq r_{a}\leq a$, and if $q_{a}=0$ then
$r_{a}<a$.

  3. (iii)

$q$ is odd and $r=0$, and $r_{a}\neq a$

The following conjecture has been verified for all $A\in{[25]\choose 3}$, for
all seeds $S$. Together with Conjecture 1 these are a strengthening of a
conjecture by Althöfer and Bültermann in [1, (i)].

######  Conjecture 4.

If $A=\\{a,b,c\\}$ with $a<b<c$, and if $\gcd(a,b,c)=1$, then for all seeds
$S\in\\{0,1\\}^{\alpha}$, we have $\operatorname{Per}(A,S)<c^{2}$.

This would imply that the construction in Theorem 6.2 can only occur if $A$
has a greatest common divisor. It would also provide the general bound that if
$g=\gcd(a,b,c)$ and $\tilde{c}=c/g$, then for all seeds $S$,
$\operatorname{Per}(A,S)\leq\tilde{c}^{2g}$, which is $\mathcal{O}(e^{2c/e})$
in the worst case but ordinarily much less than $(\min(a+b,c)+1)2^{c-3}$, the
bound derived in Theorem 2.4.

From computer simulations of $A\in{[25]\choose 3}$ with $\gcd A=1$, we note
that for all seeds $S$, if the period is super-linear, i.e.
$\operatorname{Per}(A,S)>2c$, then $(a+b)\mid c$, with the following eight
exceptions. These sets have $\max(\mathcal{P}^{A})>2\alpha$, with example
seeds given.

$\operatorname{Per}(\\{11,16,20\\},(01)^{2}1^{4}01^{2})$ | $=61$
---|---
$\operatorname{Per}(\\{3,11,21\\},0^{2}101^{2}0)$ | $=61$
$\operatorname{Per}(\\{7,17,23\\},(010)^{2}01^{2})$ | $=73$
$\operatorname{Per}(\\{10,21,23\\},0^{2}101^{4})$ | $=78$
$\operatorname{Per}(\\{5,11,24\\},01^{2}0^{3}1^{2}010)$ | $=65$
$\operatorname{Per}(\\{11,16,25\\},01^{2}010^{2}1^{4})$ | $=56$
$\operatorname{Per}(\\{16,21,25\\},0^{2}(101^{3})^{2}01^{2})$ | $=61$
$\operatorname{Per}(\\{13,23,25\\},0^{2}1^{2}010^{2}1^{5})$ | $=83$

A characterization of these sets may relate to the solution to Conjecture 1
and/or 4.

## Acknowledgement

IM was supported by NKFIH grant K132696. The project is a continuation of the
work done at the 2022 Spring semester at Budapest Semesters in Mathematics.
Both authors thank to Mariam Wael Abu-Adas for participating in the very early
phase of the research work at the BSM leading to the results presented in this
paper. Both authors would like to thank the BSM for running the program.

## References

  * [1] Ingo Althöfer and Jörg Bültermann.  Superlinear period lengths in some subtraction games.  Theoretical Computer Science, 148(1):111–119, 1995.
  * [2] P. T. Bateman, Jeffrey Kalb, and Allen Stenger.  A limit involving least common multiples: 10797.  Am. Math. Mon., 109:393–394, 2002.
  * [3] Elwyn R Berlekamp, John H Conway, and Richard K Guy.  Winning ways for your Mathematical Plays, volume 1.  AK Peters, 2001.
  * [4] Elwyn R Berlekamp, John H Conway, and Richard K Guy.  Winning ways for your Mathematical Plays, volume 3.  AK Peters/CRC Press, 2004.
  * [5] Raymond Bisdorff and Jean-Luc Marichal.  Counting non-isomorphic maximal independent sets of the n-cycle graph.  Journal of Integer Sequences, 11, 02 2007.
  * [6] Grant Cairns and Nhan Bao Ho.  Ultimately bipartite subtraction games.  Australas. J Comb., 48:213–220, 2010.
  * [7] Zoltán Füredi.  The number of maximal independent sets in connected graphs.  J. Graph Theory, 11(4):463–470, 1987.
  * [8] P. M. Grundy.  Mathematics and games.  Eureka, 2:6–8, 1939.
  * [9] Nhan Bao Ho.  On the expansion of three-element subtraction sets.  Theoretical Computer Science, 582:35–47, 2015.
  * [10] OEIS Foundation Inc.  The On-Line Encyclopedia of Integer Sequences, 2023.  Published electronically at http://oeis.org.
  * [11] R. P. Sprague.  Über mathematische kampfspiele.  Tohoku Mathematical Journal (in German), 41:438–444, 1936.