# Hardness of Approximation for Langton's Ant on a Twisted Torus
## 1 Introduction
For a coloring \(\theta_{n}\) with black vertices in only \(\mathbb{Z}_{n}\times\mathbb{Z}_{n}\), let \(f_{\theta_{n}}(N,T)\) be the number of vertices in \(\mathbb{Z}_{N}\times\mathbb{Z}_{N}\) that the ant starting from the origin will visit after \(T\) steps. We call \(\mathbb{Z}_{n}\times\mathbb{Z}_{n}\)_microscopic_ field, while \(\mathbb{Z}_{N}\times\mathbb{Z}_{N}\)_macroscopic_ one. If highway conjecture holds, we have \(\forall\theta\ =\ \{\theta_{n}\}_{n},\rho_{1}(\theta)=11/\sqrt{2}\) for \(\rho_{c}(\theta)\ :=\ \lim_{n\to\infty}\lim_{N\to\infty}\lim_{T\to\infty}f_{\theta_{n}}(N,T)/N^{c}\). However, we do not even know \(\forall\theta,\rho_{2}(\theta)<1\), that is, the ant may visit almost all vertices for some \(\theta\). The only known previous result is \(\forall\theta,\rho_{1}(\theta)>0\), that is, the ant's trajectory must always be unbounded [10]. Although \(\rho_{2}(\theta)\) measures \(N^{2}\)-order convergence rather than more accurate \(N\)-order one required in highway conjecture, its impact is substantial on the related fields. For example, if \(\forall\theta,\rho_{2}(\theta)=0\), mathematical analysis may have a chance to prove highway conjecture on square lattice, as they have done in triangular lattice [9; 12]  
Figure 2: A highway. and one-dimensional lattice [7; 12]. If \(\exists\theta,\rho_{2}(\theta)=1\), cryptographic applications [19; 20; 21; 22; 23] may find finite configurations producing infinitely long pseudo-random bits generated by the ant's trajectory. This paper will show that \(\rho_{2}(\theta)\) is hard to approximate on a _twisted torus_. A torus is the standard boundary condition to extend a coloring \(\phi\) on \(\mathbb{Z}_{N}\times\mathbb{Z}_{N}\) to \(\mathbb{Z}\times\mathbb{Z}\) by \(\phi(x,y)=\phi(x+N,y)=\phi(x,y+N)\) for \((x,y)\in\mathbb{Z}\times\mathbb{Z}\). Long-run computer simulation of square lattice cellular automata usually takes this topology [19; 20; 22]. An \(h\)_-twist_ (\(h/N\)-pitch) of the torus is \(\phi(x,y)=\phi(x+N,y)=\phi(x+h,y+N)\). It appears in related models, for example, square-lattice Ising models ([PERSON]'s ant is a typical one) [26; 27]. When \(h=\pm 11\), \(\rho_{2}(\theta)=1\) may occur even under highway emergence, as described in Figure 3. For this specific case, we can prove the following theorem. Theorem 1: _On \(\pm 1\)1-twist torus, it is PSPACE hard to distinguish between \(\rho_{2}(\theta)=1\) and \(0\)._  
It states that modern computers cannot predict whether the ant on the twisted torus will ever visit almost all vertices or nearly none of them, even under the promise that either of these cases must occur. Notice that \(\rho_{2}(\theta)\) is a time-independent measurement, counting the ever visiting vertices. Our proof will measure the _period_ that an initial configuration of the cellular automaton appears again, too. Any closed loop of [PERSON]'s ant's propagating configurations must contain the initial one [6]. Let \(g_{\theta_{n}}(N)\) be the period of [PERSON]'s ant on \(\mathbb{Z}_{N}\times\mathbb{Z}_{N}\) with an initial coloring \(\theta_{n}\) on \(\mathbb{Z}_{n}\times\mathbb{Z}_{n}\). Let \(\xi_{c}(\theta):=\lim_{n\to\infty}\lim_{N\to\infty}g_{\theta_{n}}(N)/N^{c}\). Theorem 2: _On \(\pm 1\)1-twist torus, it is PSPACE hard to distinguish between \((\rho_{2}(\theta),\xi_{2}(\theta))=(1,\frac{208}{11})\) and \((0,0)\)._  
Figure 3: A screwing highway. Consequently, no computer-aided analysis can calculate [PERSON]'s ant's macroscopic quantities from an initial finite configuration in polynomial time, unless \(\mathrm{P}=\mathrm{PSPACE}\). We note that even under the (twisted) tours's boundary condition, Lorentz lattice gas can measure the ant's diffusion speed for triangular lattice [9], particle diffusion dynamics can do it for both triangular and one-dimensional lattices [12], and discrete propagation kinetics the diffusion speed or period of the ant's rules for one-dimensional lattice [7]. Theorem 2 indicates that these currently known methods cannot measure them for square lattice.