Sequences and Series – Infinite Sequence of Digits Without Consecutive Repeating Subsequences

irrational-numbersreal numberssequences-and-series

Problem description:

Suppose we use a set of digits $\{0,1,2\}$ to form a sequence, for example
\begin{equation}
120210120102012102010210120212010\cdots
\end{equation}
The length can be finite or infinite.

The sequence is invalid if there are two finite subsequences appears consecutively. For example, the following sequences are invalid
\begin{equation}
0{\bf 11}\cdots, \quad 010{\bf 201\, 201 }\cdots
\end{equation}
where the consecutive subsequences are highlighted.

Question: Does there exist a valid sequence of infinite length?
(a non-constructive proof is also acceptable; but a constructive one would be better.)

One way to think about it:

We can transform the sequence to a (base 3) real number,
\begin{equation}
120\cdots \rightarrow 0.120\cdots
\end{equation}
Then the only possible infinite sequence should be a irrational number. Irrational number has no period, which means the pattern will not repeat infinite many times, but may repeat finite many times. A famous example is the Feynman point,

The Feynman point is a sequence of six 9s that begins at the 762nd
decimal place of the decimal representation of $\pi$.

So not all irrational number($\le 1$) are valid sequences.

I use a short program to do enumeration, but it quickly falls in exponential growth of candidates. I failed to come up with a contraction.

Generalization:

Can we take a larger set like $\{0,1,2,3, \cdots, n\}$? Can we relax the constraint to be three consecutive repetition or more?

Motivation

This problem origins from threefold repetition rule in chess,

In chess and some other abstract strategy games, the threefold
repetition rule (also known as repetition of position) states that a
player can claim a draw if the same position occurs three times, or
will occur after their next move, with the same player to move. The
repeated positions do not need to occur in succession. The idea behind
the rule is that if the position occurs three times, no progress is
being made.

It reduces to the proposed problem if we modify the this rule to be "the same position occurs two times with the same sequences of moves".

Thanks for your help.

Edit: I find a related question: Largest binary sequence with no more than two repeated subsequences

Best Answer

Yes, there are "valid" infinite sequences with three digits. They are called square-free words. Quoting the Wikipedia article:

In combinatorics, a square-free word is a word (a sequence of characters) that does not contain any subword twice in a row.

Thus a square-free word is one that avoids the pattern $XX.$

One example of an infinite square-free word over an alphabet of size $3$ is the word over the alphabet $\{0,\pm1\}$ obtained by taking the first difference of the Thue–Morse sequence. That is, from the Thue–Morse sequence $$0,\ 1,\ 1,\ 0,\ 1,\ 0,\ 0,\ 1,\ 1,\ 0,\ 0,\ 1,\ 0,\ 1,\ 1,\ 0,\dots$$ one forms a new sequence in which each term is the difference of two consecutive terms of the Thue–Morse sequence. The resulting square-free word is $$1,\ 0,\ −1,\ 1,\ −1,\ 0,\ 1,\ 0,\ −1,\ 0,\ 1,\ −1,\ 1,\ 0,\ −1,\dots$$ (sequence A029883 in OEIS).

Another example found by John Leech is defined recursively over the alphabet $\{a,\ b,\ c\}.$ Let $w_1$ be any word starting with the letter $a$. Define the words $\{w_i \mid i \in \mathbb{N} \}$ recursively as follows: the word $w_{i+1}$ is obtained from $w_i$ by replacing each $a$ in $w_i$ with $abcbacbcabcba,$ each $b$ with $bcacbacabcacb,$ and each $c$ with $cabacbabcabac.$ It is possible to check that the sequence converges to the infinite square-free word $$abcbacbcabcbabcacbacabcacbcabacbabcabacbcacbacabcacb\dots$$

Related Solutions

[Math] Example of an infinite sequence of irrational numbers converging to a rational number

Pick any irrational number $\alpha$ you like, then consider the sequence $\{x_n=\alpha/n\}_{n=1}^\infty$. Then each term of the sequence $x_n$ is irrational and it converges to zero as $n$ tends to infinity.

[Math] What’s the fairest turn sequence for n players

I have found an answer in the shape of an essentially brute-force Python 3 program I threw together. I will not accept my own answer because I'm hoping there are better takes on this, like a proper recursion or Lindenmayer system to quickly construct this solution. I am not entirely sure at this point, whether the resulting sequence generalizes Thue-Morse in all possible ways regarding "turn order fairness" but it at least does in one particular way:

Say there are two players taking turns, each trying to be the first to score a point throwing basketballs through hoops.
Both players have a low probability $\epsilon \approx 0$ of making the shot.
Conversely, they have a chance of $1-\epsilon$ to miss.
Acknowledging that a naive alternating turn order gives an unfair advantage to player 1, they decide on the following policy:
Whoever currently is the "underdog", that is, they have a lower probability of winning the game, goes next.
This, it turns out, gives the Thue-Morse-sequence of turns in the limit $\epsilon \to 0$.

Here is how it works:

The two players assign who may go first with a random coin flip. That person will be called player $A$, the other one player $B$. The current probability score for each player can be kept track of in a pair $(p_1, p_2)$. So after the first throw the score looks like this: $(\epsilon, 0)$.
Player $B$ has now become the underdog and gets the next turn. Since the game might already have ended, their winning probability is slightly lower though: $\left(\epsilon, \epsilon\left(1-\epsilon\right)\right) = \left(\epsilon, \epsilon-\epsilon^2\right)$
So at this point they still are the underdog and get to throw again: $\left(\epsilon, \epsilon\left(1-\epsilon+\left(1-\epsilon\right)^2\right)\right) = \left(\epsilon, 2\epsilon - 3\epsilon^2 + \epsilon^3\right)$.
At this point, since $\epsilon \approx 0$, $2\epsilon-3\epsilon^2$ will definitely be larger than $\epsilon$, so the next turn goes to player $A$ again. The turn order thus far was $A, B, B, A$ and if you keep following this process, you will generate the entire Thue-Morse sequence. (The referenced paper, however, mentions this other paper to construct a strictly fairer sequence. If I read it right, that sequence can't be easily constructed though. Unless somebody has further insight into this, I will stick with Thue-Morse for now.)

Here is the same algorithm now applied to three players. Initially, nobody has taken a turn. Since the turn order is determined by linear combinations of $(1-\epsilon)^n$ after $n$ turns, the matrix you see simply contains the (positive) integer coefficients if you expand the corresponding turn value. The top row denotes whether the column counts positively or negatively. We are always looking for the currently most disadvantaged player, so we are looking, from left to right, which player has the lowest winning probability. (Note, since I pulled out the sign to the top of the table, for negative columns we are looking for the maximum instead. Or just keep in mind that those values have a $-$ in front, then we are always minimizing.)

$$ \begin{matrix} & + \\ A & \mathbf{0} \\ B & 0 \\ C & 0 \end{matrix} $$

In a patt situation (As far as I could tell this only ever happens at the very beginning, but a proof of that would be nice), I give the first player the move. Below the matrix you can see the current sequence:

$$ \begin{matrix} & + \\ A & 1 \\ B & \mathbf{0} \\ C & 0 \end{matrix} \\ a $$

Higher turns require more columns for keeping track of everything:

$$ \begin{matrix} & + & - \\ A & 1 & 0 \\ B & 1 & 1 \\ C & \mathbf{0} & 0 \end{matrix} \\ ab $$

Let's jump ahead a little , to turn 6. The fat element denotes which element determines the next turn's player:

$$ \begin{matrix} & + & - & + & - & + & -\\ A & 2 & 5 & 10 & 10 & 5 & 1 \\ B & 2 & 5 & 6 & 4 & 1 & 0 \\ C & 2 & 5 & \mathbf{4} & 1 & 0 & 0 \end{matrix} \\ abccba $$

So the next turn goes to player $C$. Since they just got to play, this player now gets penalized with a term $(1-\epsilon)^6$ which will have coefficients according to $(-1)^k \begin{pmatrix} 6 \\ k \end{pmatrix}$, where $\begin{pmatrix} n \\ k \end{pmatrix}$ is the binomial coefficient, so, after adding another column to make room for all of the values, the following will be added to $C$'s row: $\begin{pmatrix}1 & 6 & 15 & 20 & 15 & 6 & 1\end{pmatrix}$, so:

$$\begin{matrix}& 2 & 5 & 4 & 1 & 0 & 0 & 0 \\ + &1 & 6 & 15 & 20 & 15 & 6 & 1 \\ \hline & 3 & 11 & 19 & 21 & 15 &6 & 1 \end{matrix}$$

The other two rows remain unchanged, save for the additional 0, so the next step would look like this:

$$ \begin{matrix} & + & - & + & - & + & - & +\\ A & 2 & 5 & 10 & 10 & 5 & 1 & 0 \\ B & 2 & 5 & \mathbf{6} & 4 & 1 & 0 & 0 \\ C & 3 & 11 & 19 & 21 & 15 &6 & 1 \end{matrix} \\ abccbac $$

and the next turn would go to b. This same basic idea can be applied to any number of players.

EDIT: I was externally asked to include some pseudo code. So there you go:

Definitions:

Let ${n\choose k} = \frac{n!}{k!\left(n-k\right)!}$ be the usual binomial coefficient.
Let ${\text{turn}_n}{\left(\tau\right)}$ be the $\tau^\text{th}$ turn in a game of $n$ players.
Let ${P^\tau}{\left(\epsilon\right)}$ be the polynomial $\left(1-\epsilon\right)^\tau$, associated with turn $\tau$.
Let $P_k^\tau$ be the $k^\text{th}$ coefficient of $P^\tau$: $\left(-1\right)^k {\tau \choose k}$.
Let $_iP^\tau$ be the polynomial of the $i^\text{th}$ player.
Let $_iP_k^\tau$ be the $k^\text{th}$ coefficient of $_iP^\tau$.

Initialize:

$_iP^0 = 0$

for each turn $\tau$, do:

find the player $i$ where the coefficient $_iP_0^\tau$ is minimal.
If multiple qualify, discard the disqualified ones, and check the next coefficient $_iP_1^\tau$ of the remaining players, and so on.
If a subset of players have the exact same associated polynomial $_iP^\tau$, arbitrarily pick the first one. (This will only happen initially and define the turn order.)
${\text{turn}_n}{\left(\tau\right)}=i$
$_iP^{\tau+1} = {_iP^\tau} + P^\tau$
$i$ here is only the minimal-coefficient player $i$ found before! Not all of them.

Next, here is a Python implementation (I'm sure there are plenty of ways to optimize this still, aside from just finding a proper recursion or substitution solution):

import functools
from itertools import count


@functools.lru_cache(maxsize=None)
def binomial_coeff(n, k):

    if n < 0:
        return 0
    if k > n // 2:
        return binomial_coeff(n, n - k)
    if k < 0:
        return 0
    if k == 0:
        return 1
    if k == 1:
        return n
    return binomial_coeff(n-1, k-1) + binomial_coeff(n-1, k)


def turns(player_count):
    # first n turns are always just the the players in standard order
    sequence = [turn for turn in range(player_count)]
    yield from sequence
    # setting up state to where it would be after first n turns plus some house keeping
    players = [[1, 0] for _ in range(player_count)]
    column_turn_number = [player_count, 1]
    column = 1
    sign = -1
    # once that's done, for every turn,
    for turn_number in count(player_count):
        # start with updating the current column to the most recent state
        for turn in range(column_turn_number[column], turn_number):
            players[sequence[turn]][column] += sign * binomial_coeff(turn, column)
            column_turn_number[column] += 1
        # then search for all occurrences of the minimum value in that column
        target_column = [player[column] for player in players]
        min_in_column = min(target_column)
        duplicates = [duplicate[0] for duplicate in
                      filter(lambda x: x[1] == min_in_column, enumerate(target_column))]
        # if there are more than one, then
        while len(duplicates) > 1:
            column += 1  # move to the next column and update it
            sign *= -1  # and update the sign accordingly
            try:
                for turn in range(column_turn_number[column], turn_number):
                    players[sequence[turn]][column] += sign * binomial_coeff(turn, column)
                    column_turn_number[column] += 1
            except IndexError:  # if it doesn't exist yet, just add a new column and try again
                for player in players:
                    player.append(0)
                    column_turn_number.append(column)
                for turn in range(column_turn_number[column], turn_number):
                    players[sequence[turn]][column] += sign * binomial_coeff(turn, column)
                    column_turn_number[column] += 1
            target_column = [players[index][column] for index in duplicates]
            min_in_column = min(target_column)
            duplicates = [duplicate[0] for duplicate in
                          filter(lambda x: x[1] == min_in_column, zip(duplicates, target_column))]
        turn = duplicates[0]  # once all duplicates are gone, the remaining value is your next turn
        yield turn  # return the turn,
        sequence.append(turn)  # store it for future reference, and
        column, sign = 0, 1  # reset the column and sign

Be careful: The way I implemented this, It's lazily generating more and more elements as I request them. If you try generating a list via list-comprehension it'll try generating the entire list for you which, it being infinitely long, will crash your computer.
Instead, use it like this:

turn = turns(3)  #  "3" for 3 players
print([next(turn) for _ in range(99)])  #  "99" for 99 turns

This will give you the first 99 turns for 3 players:

>>> [0, 1, 2, 2, 1, 0, 2, 1, 0, 0, 1, 2, 1, 2, 0, 0, 2, 1, 0, 2, 1, 1, 2, 0, 2, 1, 0, 0, 1, 2, 1, 0, 2, 2, 0, 1, 0, 2, 1, 1, 2, 0, 2, 1, 0, 0, 1, 2, 1, 0, 2, 2, 0, 1, 0, 2, 1, 1, 2, 0, 1, 2, 0, 0, 2, 1, 0, 2, 1, 1, 2, 0, 2, 1, 0, 0, 1, 2, 0, 1, 2, 2, 1, 0, 2, 1, 0, 0, 1, 2, 1, 0, 2, 2, 0, 1, 2, 0, 1]

Here are the first 100 turns for four players:

>>> [0, 1, 2, 3, 3, 2, 1, 0, 3, 2, 1, 0, 0, 1, 2, 3, 2, 1, 3, 0, 0, 3, 1, 2, 0, 3, 1, 2, 2, 1, 3, 0, 1, 3, 2, 0, 0, 2, 3, 1, 2, 0, 3, 1, 1, 3, 0, 2, 3, 1, 0, 2, 2, 0, 1, 3, 0, 1, 2, 3, 3, 2, 1, 0, 2, 1, 3, 0, 0, 3, 1, 2, 3, 0, 1, 2, 2, 1, 0, 3, 1, 2, 0, 3, 3, 0, 2, 1, 0, 2, 3, 1, 1, 3, 2, 0, 3, 2, 1, 0]

and, to show that it also generates Thue-Morse, here are the first 100 turns for two players:

>>> [0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0]

As you can see, none of the various series in my question actually are the fairest possible turn order. None of them start $0, 1, 2, 2, 1, 0$.

Open subjects:

are there nice substitution or recursion rules to generate the n-player series in this sense?
are there other reasonable notions of "fair" turn order which result in different sequences?

EDIT: I tried plotting what happens for a large number of players $n$. Unfortunately I can't check with sufficient resolution but I conjecture that, as $n$ approaches $\infty$, each subset of $2n$ turns (excluding turns in previous subsets, so the set of turns $0\dots 2n-1$, $2n\dots 4n-1$, etc.) gives a (in the player limit) continuous boundary that ought to likely look fractal. (in the limit of turns $2n + i | i \in \left\{0\dots 2n-1 \right\} , n \to \infty$)

With the code as stated I fairly quickly run into memory problems, but here are the first few thousand turns that my computer could handle.

Note how each image is mirror symmetric. This is true for every $2n$ turns with $n$ players. To get much farther (more players, more turns) I need a more efficient approach.

$128$ players, moves $0 - 4607$, in chunks of $256 \ (= 2\times 128)$ moves each. Horizontal axis denotes turn, vertical the player ID (labelled from $0-127$).

(There is no text past these images.)