What is the period of Langton's ant on a torus?

Question

Langton's ant runs on an infinite white grid. At every white square, it turns right, flips the color of the square, and moves forward one square. At every black square, it turns left, flips the color of the square, and moves forward one square. After many interations, you get complex emergent behavior, such as "recurrent highways" starting at step ~10,000.

Let's suppose that Langton's ant awakens instead on a torus of size $n \times n$. It follows its two rules, thus changing the coloring of the torus. At some point, however, it encounters a colouration it has seen before, while being in the same spot as before, and finds itself in a cycle. How do we find the length of a cycle for a size $n$ torus, and is this result known? We can get a stupid upper bound by observing that there are at most $2^{n^2}$ colorings, $n^2$ positions, and $4$ orientations, so a cycle cannot be longer than $2^{n^2+2}n^2$. Is there a closed form for this, or at least some tighter bounds?

EDIT 1

I ran some quick calculations just to get a feel for the magnitudes of the numbers¹. Here's an animation of Langton's ant on a $3 \times 3$ torus, where the cycle takes 22 steps:

Some more results I got are: $$\begin{matrix} \text{Size} & \text{Steps} & \text{Factorization}\\ \hline 1 & 2 & 2\\ 2 & 8 & 2^3\\ 3 & 66 & 2 \cdot 3 \cdot 11\\ 4 & 96 & 2^5 \cdot 3\\ 5 & 11,710 & 2 \cdot 5 \cdot 1171\\ 6 & 4,592 & 2^4 \cdot 7 \cdot 41\\ 7 & 64,165,598 & 2 \cdot 7^2 \cdot 31 \cdot 21121\\ 8 & 11,502,464 & 2^7 \cdot 73 \cdot 1231\\ 9 & 919,057,222,998 & 2 \cdot 3^2 \cdot 51058734611 \\ 10 & 150,192,928,160 & 2^{5}\cdot5\cdot11\cdot85336891 \\ 11 & >5.7 \cdot 10^{11} & \\ 12 & >5.6 \cdot 10^{11} & \\ \end{matrix}$$

The values for $n=9$ and $10$ are due to Connor Harris.

This does not, to my knowledge, match any sequence in OEIS.

EDIT 2

The only real pattern I've found thus far is in the prime factorizations—for odd-sized tori, there is (so far) exactly one factor of 2 in the factorization. However, in even-sized tori, the factors of 2 have multiplicities 3, 5, 4, and 7, which seems interesting. Is there any reason to believe this pattern holds for all even/odd-sized periods?

Footnotes

1: as per Connor Harris's comment, I only checked until the initial state reappeared (i.e., the torus became blank).
2: using Connor Harris's definition of a quasi-cycle as the amount of time it takes to get back to a blank (or full) grid.

Answer 1

Not an answer, but a quick table with the number of turns until the recurrence of the initial position on rectangular grids small enough to be testable by computer.

The ant is initially facing up (that is, along a column); this matters for non-square boards that may have different periods depending on whether the ant starts by facing in the "long" or the "short" direction. Numbers show the length of time until the first full recurrence: an all-white board with the ant in the original position facing up. A bracketed number before the entry indicates that a "quasi-recurrence," or an all-white or all-black grid with the ant in any cell facing either up or down (or left and right, in the case of a square grid), occurs before the first full recurrence. The development of the board after a quasi-recurrence is isomorphic to that of the actual initial position, but translated, rotated, and (if the board is all black at the beginning of the quasi-recurrence) mirrored across the ant's initial line of sight. The bracketed number shows the number of quasi-recurrences up to and including the first full recurrence; thus, an entry of $[3]~66$ means quasi-recurrences on turns 22 and 44 before a full recurrence on turn 66.

\begin{array}{r|rrrrrrrrr} \downarrow\text{rows/cols}\rightarrow&2&3&4&5&6&7&8&9&10 \\ \hline 2 & [2]~8 & 16 & 16 & 16 & 16 & 16 & 16 & 16 & 16\\ 3 & 8 & [3]~66 & 72 & [3]~954 & 196 & 208 & 3{,}008 & 6{,}064 & 304 \\ 4 & 8 & [2]~56 & [2]~96 & 624 & 696 & 3{,}448 & 2{,}336 & 13{,}360 & 2{,}608\\ 5 & 8 & [5]~170 & 96 & [5]~11{,}710 & 16{,}804 & [5]~344{,}300 & 606{,}688 & [5]~14{,}988{,}170 & 1{,}544{,}720\\ 6 & 8 & 120 & 96 & 4{,}184 & 4{,}592 & [3]~296{,}736 & 507{,}056 & 1{,}824{,}688 & 2{,}045{,}304 \\ 7 & 8 & [7]~322 & 96 & 17{,}432 & 714{,}592 & [7]~64{,}165{,}598 & 34{,}882{,}576 & 299{,}407{,}462 & 58{,}495{,}320 \\ 8 & 8 & 208 & 96 & [2]~31{,}600 & 147{,}424 & 10{,}003{,}800 & [2]~11{,}502{,}464 & [2]~1{,}634{,}057{,}664 & [2]~4{,}622{,}916{,}480 \\ 9 & 8 & [9]~522 & 96 & [9]~1{,}568{,}880 & 8{,}066{,}144 & [9]~2{,}508{,}401{,}214 & 3{,}586{,}271{,}200& [9]~919{,}057{,}222{,}998 & 133{,}648{,}022{,}836\\ 10 & 8 & [5]~320 & 96 & [5]~5{,}445{,}220 & 10{,}426{,}496 & [5]~2{,}107{,}770{,}700 & 2{,}084{,}996{,}112 & [5]~374{,}647{,}259{,}920 & 150{,}192{,}928{,}160 \end{array}

These are usually much smaller than the trivial upper bound in your comment. Periods seem quite erratic in general, especially for boards with at least one small dimension: for example, the periods of boards with 3 rows and 18, 19, and 20 columns are respectively 10,930,388, 592, and 30,519,840. The relative infrequency of quasi-recurrences is striking, as a randomly chosen state of the board is much more likely to be a quasi-recurrence than a the initial state.

Edit: Some other observations. The square toruses of odd side-length $n \in \{3, 5, 7, 9\}$ all have a period divided into $n$ quasi-recurrences, and none of their period lengths is divisible by $4$. Furthermore, with the exception of the $2 \times 2$ torus (for which the quasi-recurrence occurs after turn $4$ with a black grid and the ant rotated 180 degrees in its starting square), every quasi-recurrence I have found in a square or rectangular torus has left a white grid with the ant moved forward or backward within its initial column, but not moved side to side or rotated. For anyone who wants to do their own experimenting, I have a C program (not especially well designed, but workable) here.

Answer 2

We can tighten the upper bound by looking at the symmetries on the torus. The ant's behavior will be the same no matter which of the $n²$ squares it starts on or which of the $4$ directions it is facing. In addition, a reflection coupled with a color inversion is another symmetry. These correspond to the symmetry groups $\mathbb{Z}_n \times \mathbb{Z}_n$, $\mathbb{Z}_4$, and $\mathbb{Z}_2 \times \mathbb{Z}_2$, respectively. The maximum order of any element of $\mathbb{Z}_n \times \mathbb{Z}_n$ is $n$. This means that the ant will find itself on a blank grid but possibly in the wrong position after $2^{n²+2}$ steps, but after doing this $n$ times it must be in the right position. Similarly, the maximum order of any element of $\mathbb{Z}_2 \times \mathbb{Z}_2$ is $2$, so after $2^{n²}n²$ steps we may end up reflected and inverted, but doing this twice we'll end up where we started. The maximum order of $\mathbb{Z}_4$ is $4$, so the symmetry of rotation doesn't help us.

Combining these two symmetries, a better upper bound is $\mathbf{2^{n²+1}n}$.

Answer 3

I've figured out some lower bounds for the number of factors of 2 in the period. This applies to any configuration, not just the all-white one.

It's more convenient if we say that at each time step, the ant is located at the middle of an edge, facing the center of one cell or the other.

Every step flips the color of one cell, so each cell is visited an even number of times, which means the period has to be divisible by 2.

Now consider a torus with an even number of columns. Separate the cells into two sets according to their horizontal coordinate modulo 2. Assume that the ant is pointing horizontally towards a cell in column $i$. In the next two steps, there are four possibilities for its path, but all of them visit two cells in column $i$, and afterwards the ant is horizontal again and pointing towards column $i-1$ or $i+1$. So every path visits two even cells, followed by two odd cells, then two even, two odd, and so on. That means that the period is divisible by 4.

Now let's examine a torus that is even in both directions. Put the cells into four equivalence classes by their coordinates modulo 2. The ant always travels through all four classes in a repeating cycle, either $(0,0), (0,1), (1,1), (1,0)$ or the reverse. To return to the same state, each class must be visited an even number of times, and each class is visited the same number of times, so the period is divisible by 8.

2019-08-23: There's a conservation law we can use. Choose any row. Add up the number of black squares modulo $2$. If the ant is located inside the row, pointed left or right towards one cell in the row, add another $1$ to the total. This value will always stay the same. (Consider three cases: the ant enters the row, the ant leaves the row, and the ant visits a cell not in the row.) This also works for columns.

If you add the values for all rows and columns, each black cell gets counted twice, and the ant is counted exactly once, so you always get $1$. That means that once you know the values for all lines but one, you know the value for the last one. We can use this fact to divide the states for an $m$ by $n$ torus into $2^{m+n-1}$ classes of equal size. This gives a loose upper bound of $m n 2^{(m-1)(n-1)+2}$ for the period. If both $m$ and $n$ are even, then the ant can never visit the same location pointed in opposite directions. In this case, each class can be divided in half, and the period upper bound is also halved.

In the original state, all columns have value $0$, except for the column with the ant. The same is true for a quasi-recurrence, so the ant has to be in its initial column. This explains Connor Harris's observation.