Forbidden mirror sequences

Edited 12/27 to try to clarify, and to correct regular expression formatting (\* is needed so * doesn't turn into italization)

On some level its obvious that the set of mirror sequences are characterized by the list of finite substrings that can never occur, if you allow lists to be infinite, and if you count the closure of the set of mirror trajectories as mirror trajectories. (There might be subtle issues of what happens when a light beam hits exactly at the edge of a mirror: in this case, if you allow both outcomes that are the limits of its perturbation, it gives a closed set). But I don't think this is what you meant. It reminds me of having to use a word such as "industrious" in a sentence in 2nd grade. My teacher didn't like my sentences, "'Industrious' is a word."

Perhaps a better formulation of the question is to ask whether the set of mirror sequences is a regular language, and if so, to describe it. For some presumably easier cases, the set of arrangements of mirrors can be specialized to range over some particular subset, such as parallel mirrors, or mirrors all at angles of the form $k \pi / n$ for some $n$.

Thus, for two mirrors a and b, the language is b?(ab)*a?, interpreted with the usual regular expression convention where ? means 0 or 1 occurrence of the preceding term and * means 0 or more occurrences. This is equivalent to not(.*aa.*) and not(.*bb.*) where . matches any symbol.

For three parallel mirrors, you can have a sequence such as (ab)+(cb)+(ab)+, where + denotes 1 or more occurrence of the previous term, but this sequence implies that c is sandwiched between a and b, so you can't have any more c's after that. I won't try to write out a complete regular expression, but

Claim: For any number of parallel mirrors, the set of possible sequences (as the positions of mirrors and the initial beam are vaired) is a regular language. Furthermore, the number of possible sequences of length $n$ grows only as a polynomial in $n.

Proof: One may assume that the beam is coming from the left and angling upward. (The cases that it is vertical or horizontal are trivial).

To make a finite state automaton (FSA) to recognize valid mirror sequences, first make a nondeterministic finite state automaton (NDFSA) whose states are possible arrangements of the mirrors and the current position of the beam in relation to them: the relevant data is the horizontal linear order, the question of whether the beam is going to the left or right, and the vertical partial order of the tops and bottoms of the mirrors and the beam, where the partial order $x < y$ on points in the plane is whether $y$ is in the cone bounded by beams at $x$ at the beam angle and its mirror image. Each time the beam hits a mirror, the point where it hits has a one of a finite number of positions in the new partial order, inserting the new point and removing the previous position of the beam; this gives an NDFSA. The (deterministic) FSA has states which are sets of states of the NDFSA, and the transition takes a set of states to the set of all possible states obtained by an NDFSA transition from one of them.

There are probably nice methods to actually implement this. Instead of a set of linear orders, we can keep track of a partially ordered set of mirrors that we have seen; each new letter pair xy tells us either that x < y or x > y. A letter can either occur at only odd positions, or only even positions --- when the mirrors are parallel, it's impossible for the beam to reflect from the front, then get around to the other side and hit the back. Whenever we see such as yx[^y]*xy, where [^y] means a character that is not y, it implies that the mirrors other than x in the [^y]* substring are sandwiched between x and y, and the beam has gone above them: they can never occur again.

Perhaps you can see or intuit from the way the finite-state mirror model evolves that it's impossible to get branching recurrence, so the number of sequences grows only as a polynomial. Instead of trying to make this precise, there's a proof-by-authority for this last point: pass to a surface obtained by taking two copies of the plane, cutting slits where the mirrors are, and gluing them together along the slits so that the light rays follow geodesics on the resulting surface (with exceptional points where the trajectories fork at the ends of the mirrors.) The trajectories now become simple curves on the resulting surface, generically going out to the point at infinity at both ends. It is known that the set of all homotopy classes of simple curves on any surface grows as a polynomial of degree 6g-6, where $g$ is the "genus" or number of holes of the surface, since simple closed curves are lattice points in the space of measured laminations on a surface.

The same proof works when mirrors are confined to angles of the form $2\pi/n$, where you take $2n$ copies of the plane, one for each reflected image of the plane, mod translations. Cf. "A rational billiard flow is uniquely ergodic in almost every direction" by Kerckhoff, Masur and Smillie for a masterful use of this technique of passing to a surface obtained by gluing multiple copies.

Even though the number of mirror sequences has polynomial growth in the case of mirrors at angles $\pi/n$, nonetheless, even when $n= 2$ i.e. for mirrors that are vertical or horizontal, mirror sequences are not a regular language. The classicla special case of a rectangular billiard table illustrates this: for a rectangle you can glue four copies together to get a torus, where the trajectories become lines of constant slope. These sequences have been well studied, for instance in computer graphics, where they give sequences of pixels used to depict a thin straight line. They have a simple recursive characterization (essentially the Euclidean algorithm), but they are not determined by a finite state machine. For an arbitrary arrangement of four mirrors, the richest sequences are those that come from the billiard table --- otherwise, mirror sequences degenerate to a case of 2 or 3 parallel mirrors at the start and/or finish. Thus, there is no finite set of excluded sequences for this case.

For more less restricted arrangements, the conditons will only become more complicated.

In the general case, there are some constraints having to do with inequalities that can be deduced on angles of the mirrors.

First, if there is a sequence of length $n$ alternating between two mirrors x and y, it implies that one of the two angles between the two mirrors is less than $\pi/(n-1)$. You can see this by starting with mirrors that form an angle $\alpha$, and reflecting it around. A light ray hitting mirror $x$ unfolds as a straight line crossing this pattern, so if it crosses $k$ edges, the $k-1$ angles between them cannot add to more than $\pi$.

Using this, for a complicated enough sequence involving just 3 letters, you get inequalities concerning the three angles of the triangle formed by extending the mirrors.

I don't know whether there is a good general algorithm to decide if a sequence is a mirror sequence. I suspect that there should be an algorithm that in practice is fairly efficient, generalizing the idea from the case of parallel mirrors to describe increasingly restrictive geometric inequalities about the arrangement of mirrors, perhaps as a first approximation using floating point inequalities.

I suspect that the number of mirror sequences probably has polynomial growth even in the general case when no conditions are imposed on the angles of the mirrors, but I haven't thought through a proof. If there are $m$ mirrors, then when the angles are restricted to have the form $\pi k / n$, the covering surface where trajectories are simple proper arcs (tending to infinity at both ends) has Euler characteristic $-2 n ( m-1)$. The dimension of the space of measured geodesic laminations on the covering surface grows linearly with $n$, but the light trajectories are integral curves of a quadratic differential that has an equivariance property with respect to deck transformations, which limits its dimension. The dimension of the moduli space of mirror arrangements with any given constant angle depends only on the number of mirrors: we can normalize the first mirror to be the unit interval in the $x$-axis, and then each additional mirror has 3 degrees of freedom (when its angle is fixed), so the dimension is $3m-3$. This should equal the degree of the polynomial growth for mirror sequences with such mirrors. However, since mirror sequences are not determined by an FSA, the number of valid mirror sequences is probably not the set of values of an actual polynomial except when the mirrors are parallel, so one would need estimates of initial behavior or particular constants to conclude that the limit has polynomial growth.

A weaker question is whether the shift map on mirror sequences has topological entropy 0 (i.e, it can be recoded into a sequence with bit rate 0). I think this follows. If we add the extra information of the angles of the mirrors to the dynamical system (usually this is probably redundant anyway), then each particular set of angles defines a closed invariant subset. The angle of the beam at any time is in the subgroup of $S^1$ generated by the angles of the mirrors, which is an abelian group of rank at most $m$. There is an infinite-sheeted covering surface where the trajectories become simple, and the covering surface can be thought of as equivariantly embedded in $\mathbb R^m$ (provided $m \ge 3$; for $m = 3, make it an immersion if it's hard to get an embedding). This setup seems to imply that the topological entropy is 0. Perhaps some expert can confirm or deny.

I think it would probably be worth expanding the notation to distinguish between hitting the front and back of a given mirror, perhaps using capitalization, x vs X.

Here is a possible way of producing such forbidden configurations. Suppose you have $(ab)^k$ for some large $k$. Then I'd like to claim that $a$ and $b$ must be nearly parallel (see Thurston's answer). So produce a sequence with three mirrors containing $(ab)^k$, $(bc)^k$, $(ac)^k$ and a forbidden configuration for parallel mirrors such as the one you gave above (which you then have to prove also is forbidden for nearly parallel mirrors).