Suppose you have a turtle graphics system with a set "turning angle" $\delta$, in which the turtle can execute three commands:
- $F$: Go forward, by unit length, in the current direction. (The initial direction is irrelevant.)
- $+$: Turn $\delta$ degrees to your left.
- $-$: Turn $\delta$ degrees to your right.
(For example, L-systems are drawn using a very similar setup.) I will write $+^n$ and $-^n$ to mean "turn $n\delta$ degrees to your left/right", where $n$ is an integer.
Given $\delta$, I want to know which points on the plane the turtle can reach. Specifically, I'm interested in whether the set of reachable points is dense in $\Bbb R^2$ or not.
If $\delta/2\pi$ is irrational, the set of reachable angles is dense in $[0, 2\pi]$. Informally, this means you can move arbitrarily small distances by making really sharp turns: find some integer $n$ so that $n\delta$ is almost 90 degrees. Then $+^nF-^{2n}F+^n$ will move a very tiny bit in the current direction. Since there's then a way to move arbitrarily small distances at arbitrary angles, I'm quite sure this means the set of reachable points is dense in $\Bbb R^2$.
If $\delta/2\pi$ is rational, then $\delta = (a/b)2\pi$ for some irreducible fraction $a/b$. Since $a$ and $b$ are coprime, there is some $n$ so that $n\delta = (1/b)2\pi$ (modulo $2\pi$), so we can reduce the problem to the case $\delta = 2\pi/b$ for some positive integer $b$.
Here's where I'm stuck. I know that for e.g. $b=4$, the turtle can only turn at 90° angles, and is obviously stuck on a square lattice; similarly, if $b=3$ or $b=6$ the turtle is stuck on a triangular lattice moving only at 120° or 60° angles. $b=1$ or $b=2$ means the turtle is stuck on a given line.
How can I prove that the set of reachable points is not dense in the plane for precisely these values of $b$?
(I think what I'm looking at can be described as the additive subgroup of $(\Bbb C, +)$ generated by the bth roots of unity: the roots $z_0, z_1 \dots z_{b-1}$ correspond to the turtle commands $F$, $-F+$, $-^2F+^2$, etc. For which $b$ is this group's underlying set dense in $\Bbb C$? Therefore, I've tagged this question group-theory.)
For $b=1$, the turtle can only reach equidistant points within a ray; it cannot move backwards, so that case does not yield a group.
In the following I will assume that $b$ is an integer greater than $1$.
Let the turtle start at $0$ in the complex plane with direction $1$. There are exactly $b$ possible directions for the turtle, and we can represent those directions as $\zeta_b^k = \exp(\mathrm{i}k\delta) = \exp\left(\frac{2\pi\mathrm{i}k}{b}\right)$ for $k\in\{0,\ldots,b-1\}$.
For each direction $\zeta_b^k$ we can maintain a step counter $a_k\in\mathbb{N}_0$ that is incremented whenever the turtle steps in that direction. Then the turtle's position can be given as $$z = \sum_{k=0}^{b-1} a_k\zeta_b^k$$ I claim that the set of all possible $z$ remains unchanged if we allow negative integer values for the $a_k$ as well. In other words, the equivalent of backward moves is possible. This can be deduced from the fact that $$\sum_{k=0}^{b-1} \zeta_b^k = 0\quad\text{for $b>1$}$$ (Note that this requires $b>1$ which is why that case had to be separated.) Concretely, let $a_{\text{min}} = \min_{k=0,\ldots,b-1} a_k$, then $$\sum_{k=0}^{b-1} \underbrace{(a_k - a_{\text{min}})}_{\geq0}\,\zeta_b^k = \underbrace{\left(\sum_{k=0}^{b-1} a_k\zeta_b^k\right)}_z - a_{\text{min}}\underbrace{\sum_{k=0}^{b-1} \zeta_b^k}_0 = z$$ So we can make all step counters nonnegative by adding $-a_{\text{min}}$ to all of them without changing the turtle position $z$.
As a result, the set of all possible turtle positions can be identified with $\mathbb{Z}[\zeta_b]$, the ring of all polynomials in $\zeta_b$ with integer coefficients.
Another thread unveils the cases when $\mathbb{Z}[\zeta_b]$ is dense in $\mathbb{C}$: Since $\zeta_b$ is an algebraic integer (it solves $X^b - 1 = 0$), $\mathbb{Z}[\zeta_b]$ is dense in $\mathbb{C}$ if and only if the degree of (the minimal polynomial of) $\zeta_b$ over $\mathbb{Q}$ is greater than $2$.
The minimal polynomial of $\zeta_b$ over $\mathbb{Q}$ is the cyclotomic polynomial $\Phi_b$, its degree is $\phi(b)$ where $\phi$ is Euler's totient function: $$\phi(b) = b\prod_{\substack{p\text{ prime}\\p\mid b}}\frac{p-1}{p}$$
$\phi(b)$ is a positive integer, so we just need to exclude those $b$ that have $\phi(b)\in\{1,2\}$. These are $b \in \{1,2,3,4,6\}$; to see that there are no more $b$, note that
Consequently, $\mathbb{Z}[\zeta_b]$ is dense in $\mathbb{C}$ if and only if $b\not\in\{1,2,3,4,6\}$.
@Rahul has indicated another approach which may seem easier to grasp:
Obviously, $b>2$ is necessary and sufficient for the turtle to move in more than one dimension. So let us assume $b>2$. Note that $+F--F+$ moves forward $2\cos\delta$. Replacing $F$ with $(+F)^{b-1}+$ moves backward instead. So we can effectively move in the current direction with any step size from the $\mathbb{Z}$-span of $1$ and $2\cos\delta$. Therefore, if $\cos\delta\not\in\mathbb{Q}$, the set of available step sizes is dense in $\mathbb{R}$. Combined with the ability to move in more than one dimension once $b>2$, this makes the set of reachable turtle positions dense in $\mathbb{R}^2$ if $\cos\delta$ is irrational.
In yet another thread, a useful lemma has been given:
Proof: Assuming $\frac{3\delta}{\pi}=\frac{c}{n}$ with $c,n$ coprime integers and $n>0$, we have $$2\cos(n\delta)=2\cos\frac{c\pi}{3}=u \quad\text{for some}\quad u\in\{\pm1,\pm2\}$$ and $$2\cos(n\delta) = D_n(x)\quad\text{where}\quad x = 2\cos\delta\tag{*}$$ where the $D_n(x)$ are Dickson polynomials of the first kind (with second parameter $\alpha=1$). Their essential property is $$D_n\left(z+\frac{1}{z}\right) = z^n + \frac{1}{z^n}$$ Setting $z=\exp(\mathrm{i}\delta)$ yields $(*)$. Those Dickson polynomials can be defined recursively as $$\begin{align} D_0(x) &= 2 \\ D_1(x) &= x \\ D_n(x) &= x\,D_{n-1}(x) - D_{n-2}(x) &&\text{for $n>1$} \end{align}$$ By induction we can see that the Dickson polynomial $D_n$ has integral coefficients, degree $n$ and is monic for $n>0$. The same holds for $D_n(x) - u$ (at least for $n>0$ which we assume), a root of which is $x=2\cos\delta$. Therefore $2\cos\delta$ is an algebraic integer.
Consequently, if $\cos\delta$ is rational, then $2\cos\delta$ must be an integer. Since $\cos\delta$ is bounded to not exceed absolute value $1$, the only possibilities are $2\cos\delta\in\{-2,-1,0,1,2\}$ which correspond to $b\in\{2,3,4,6,1\}$. All other $b$ therefore yield irrational $\cos\delta$ and result in turtle position sets that are dense in $\mathbb{R}^2$.