Exact Escape Times of Langton's Ant in Four Rows

Hao Ke

Preprint ·

Abstract

How long can Langton’s ant remain inside a rectangle with four rows? We maximize the time of its first exit over every initial colouring and every starting position and heading. For a rectangle of width n, the exact maximum is S_(4, n) = 34n − 150 for all n ≥ 13; we also determine every smaller case. This proves Etse’s conjectured upper bound S_(4, n) ≤ 34n and matches his lower-bound family from width fourteen onward. The main difficulty is that a returning ant encounters the colours changed on its previous visits, so a block cannot be replaced by a device that resets after each crossing. We classify blocks by their responses to repeated entries, retaining the changed response after each return. Exactly 269 response types occur for each choice of entry side and parity, and this collection is closed under adjoining a column. A weighted version gives an exact recurrence for the maximum escape time. Finite integer inequalities then prove its affine behaviour for every larger width. The proof combines an induction covering arbitrarily wide rectangles with exact finite certificates, and reconstructs colourings attaining each maximum.

Citation

Hao Ke (2026). Exact Escape Times of Langton's Ant in Four Rows. Zenodo. 10.5281/zenodo.23675964

@misc{ke2026langtonsantfourrowescape,
  author = {Hao Ke},
  title = {{Exact Escape Times of Langton's Ant in Four Rows}},
  year = {2026},
  doi = {10.5281/zenodo.23675964},
  url = {https://doi.org/10.5281/zenodo.23675964},
  note = {Preprint, version 0.1.1}
}

CC BY 4.0.