Lasers

(Andrew here.) 

In research, it often happens that people rediscover results lost to the sands of time, which always makes me wonder what gemstones have been lost and are waiting to be rediscovered. It also means that a lot of surprising things can be learned from reading old papers. Today I'm going to present a fun curiosity that I saw on Mathologer (luckily somebody did the 'reading old papers' bit for me and spared me having to decipher old French) just because I think it ought to be better known. We'll then see where it takes us.

In 1867 an Austrian military engineer by the name of M. E. Lill published the following method of finding real roots of polynomial equations: 

Let $p(x)= a_nx^n + a_{n-1}x^{n-1} + \cdots a_0$ be a polynomial with real coefficients. Starting at the origin $O$ in the coordinate plane, face the direction of the positive $x-$axis. Walk the signed distance $a_n$ (this means that if $a_n$ is negative then walk backwards) and turn $90$ degrees counterclockwise. Then walk the signed distance $a_{n-1}$ in the new direction and turn $90$ degrees counterclockwise. Repeat until you have exhausted all the coefficients. Call this path the polynomial path corresponding to $p(x)$. Note that if $a_k$ is 0 for some $k$ you don't walk but still turn. Call the final point of this path $P$ and denote by $l_i$ the lines where you walked a distance of $a_i$.

We now play with a laser which doesn't obey the classical laws of physics because I don't like physics. Instead of bouncing off walls such that the angle of incidence is equal to the reflected angle, the laser is going to bounce so that the outgoing ray makes a 90 degree angle with the incoming ray. Shoot the laser from the origin such that when it hits $l_n$, reflects at an angle of 90 degrees,  continues until it hits $l_{n-1}$ and reflects, and so on. We will suspend all physical and other types of disbelief and take it on faith that the laser can somehow decide which direction to go in order to hit the next line (or you can pretend that these are actual mirrors set up in the correct way if you really want). Let $k$ be the initial slope of a laser trajectory which hits $l_{0}$ at $P$. Then $-k$ is a root of the polynomial $p(x)$!

Figure 1: extracted from the Wikipedia article illustrating an instance of this method. For those who like pretty pictures there are lots of other illustrations of Lill's method on the internet, of much better quality than my artistically challenged self can hope to produce.

Verifying that this is in fact a root is a routine exercise which boils down to  $((a_{n}x+a_{n-1})x+a_{n-2})x +\dots$ being $0$ when $x$ is a root, which is my best guess for how Lill came up with this method in the first place. For those who are interested, the article Resolution graphique des equations algebriques qui ont des racines imaginaires deals with the case of complex roots. If you were to take a moment here and stare at some diagrams, you might note that the path traced out by the laser corresponding to a root $x_0$ is again a path made out of $n$ straight lines at right angles to each other, so after rotation this defines another path where we can shoot lasers. This path corresponds to the polynomial $\frac{p(x)}{x-x_0}$, as a bit of elementary trigonometry shows, so one can iterate this to completely factorise polynomials! Applying this to the polynomials $(x+1)^n$ gives a nice alternate incarnation of Pascal's triangle, which has been animated at the end of the Mathologer video.

There has been some interest in this method in the 21st century because this gives a method of root finding/approximation that even a computer is capable of doing: shoot the laser and adjust until you get really close. Unlike some other methods you aren't going to accidentally shoot off to infinity or whatever. I'm not a numerical analyst so I am not qualified to compare the merits of various approaches. Instead, let's see how you might extract roots exactly in a detour to origami.

Origami

Suppose you have drawn the polynomial path for a cubic on a sheet of paper and are looking to find a laser trajectory. Reflect the segment of length $a_3$ on line $l_3$ in $l_2$ and the segment of length $a_0$ on $l_0$ in $l_1$. Denote by $P'$ and $O'$ the images of $P$ and $O$ respectively, and let $l_4$ be the line through $O'$ perpendicular to $l_3$ and $l_5$ be the line through $P'$ perpendicular to $l_0$. Now fold the paper such that $P$ lands on $l_5$ and $O$ lands on $l_4$. The point where the crease intersects $l_1$ is the point where you should aim the laser. Again, showing this is an elementary exercise in geometry. (Note the lines are well defined even if the coefficients are 0.)

Figure 2: origami helps to find the path of the laser.

The attentive reader will realise that I am now able to 'construct' $2^{\frac{1}{3}}$, which isn't possible with ruler and compass!

This is because the fold I used is what's called the Beloch fold, named for the Italian algebraic geometer M. P. Beloch: Given two points $P_1$ and $P_2$ and two lines $l_1$ and $l_2$ we can, whenever possible, make a single fold that places $P_1$ onto $l_1$ and $P_2$ onto $l_2$ simultaneously. When folding a point $P$ onto a point $P'$ on a fixed line $l$, what happens is that the perpendicular to $l$ at $P'$ meets the crease line at a $X$ which is equidistant from $P$ and $P'$, so the locus of such $X$ is a parabola and the crease lines are tangents to this parabola. Being able to do the Beloch fold then finds the common tangent to two parabolas, which is equivalent to solving a cubic, so origami is more powerful than ruler and compass. (To make this completely precise, the list of things that one is allowed to do in straight-crease, one-fold-at-a-time origami is the list of Huzita-Hatori axioms.) 

To drive this point home, here's how to trisect an arbitrary angle with origami: Given a rectangular piece of paper $ABDE$ with an arbitrary point $C$ on $DE$, the angle CAB is trisected by making two folds: $PP'$, parallel to the base, and $QQ'$, halfway in between. Then point $P$ is folded over to lie on line $AC$ and at the same time point $A$ is made to lie on line $QQ'$ at $A'$. The angle $A'AB$ is one third of the original angle $CAB$. This is because $PAQ$, $A'AQ$ and $A'AR$ are three congruent triangles. 

Solving cubics is in a sense best possible in straight-crease, one-fold-at-a-time origami, as discussed in the article 'Origami and geometric constructions'. However, in 'Folding the algebraic closure of the rational numbers' the authors show that if arbitrary numbers of simultaneous folds are allowed then it is possible to find the roots any polynomial.  

There are loads of other cool things that one can do with origami, but I'm afraid that will have to wait until another time.

Olympiad Maths and Lasers

Going back to lasers, it turns out that there are a handful of grid problems which can be solved by shooting lasers into the grid and analysing their behaviour subject to the problem conditions. The difficulty in turning this into a training set is that there are so few of them: it is unclear whether this is useful training, and more importantly I can't find any intuition for when the laser thing should work. For example, does there exist a lasers solution to ISL 2016 C8? In an effort to pad this list I searched on AoPS for problems which somebody had solved by lasers, or had a setup which outright asked you to analyse some laserlike behaviour. I don't claim that all of the problems here should be solved by lasers. Here are the lasers problems I found (the last two are the ones which inspired me to try and actually come up with something vaguely looking like a training set):

• Let $ABC$ be an acute-angled triangle. Find a periodic laser path in $ABC$, i.e. a laser path that closes up.
• (Arithmetic Billiards) Consider a rectangle with integer sides $a, b$ and construct a path inside this rectangle as follows: start in a corner, and move along the straight line which makes a 45° angle with the sides. Every time that the path hits a side, reflect it with the same angle (the path makes either a left or a right 90° turn). Suppose that eventually (i.e. after a finite number of reflections) the path hits a corner and there it stops. Divide the rectangle into $a \cdot b$ unit squares.
• How many unit squares does the path cross?
• Suppose that none of the two side lengths divides the other. Then the first segment of the arithmetic billiard path contains the point of self-intersection which is closest to the starting point. What is the number of unit squares crossed by the first segment of the path up to that point of self-intersection?
• (Spain) Let $n$ be a positive integer. In a $n \times n$ square grid, some cells have a two-sided mirror in one of their diagonals. Outside each of the cells in the left and right sides of the grid there is a laser pointer facing towards the grid. Lasers in each of the sides are numbered from $1$ to $n$, from top to bottom. We say that a laser beam is red if it exits the grid (after being reflected in some mirrors) from the top side, and green if it exits the grid from the bottom side. If each laser exits the grid from either the top or the bottom sides, then prove that the sum of the numbers of the red lasers is less than or equal to the sum of the numbers of the green lasers.
• I'm somewhere in the interior of a square room whose walls are mirrors. Can I arrange finitely many of my friends inside (or on the border of) this square room in a particular way so that I cannot see my own reflection?
• (APMO 2018) Let $ABC$ be an equilateral triangle. From the vertex $A$ we draw a ray towards the interior of the triangle such that the ray reaches one of the sides of the triangle. When the ray reaches a side, it then bounces off following the law of reflection, that is, if it arrives with a directed angle $\alpha$, it leaves with a directed angle $180^{\circ}-\alpha$. After $n$ bounces, the ray returns to $A$ without ever landing on any of the other two vertices. Find all possible values of $n$.
• (USA TSTST 2013) Divide the plane into an infinite square grid by drawing all the lines $x=m$ and $y=n$ for $m,n \in \mathbb Z$. Next, if a square's upper-right corner has both coordinates even, color it black; otherwise, color it white (in this way, exactly $1/4$ of the squares are black and no two black squares are adjacent). Let $r$ and $s$ be odd integers, and let $(x,y)$ be a point in the interior of any white square such that $rx-sy$ is irrational. Shoot a laser out of this point with slope $r/s$; lasers pass through white squares and reflect off black squares. Prove that the path of this laser will form a closed loop.
• (USAMTS 2014-15) A finite set $S$ of unit squares is chosen out of a large grid of unit squares. The squares of $S$ are tiled with isosceles right triangles of hypotenuse $2$ so that the triangles do not overlap each other, do not extend past $S$, and all of $S$ is fully covered by the triangles. Additionally, the hypotenuse of each triangle lies along a grid line, and the vertices of the triangles lie at the corners of the squares. Show that the number of triangles must be a multiple of $4$.
• Given a regular hexagon in which every interior side are covered with mirror. In every vertex, there is a small hole. From one of the six holes, a laser is shot into the hexagon. Prove that we can construct the laser's shooting angle such that the laser ray will continue to reflect inside the hexagon without ever going out from one of the holes.
• (MEMO 2015) Let $N$ be a positive integer. In each of the $N^2$ unit squares of an $N\times N$ board, one of the two diagonals is drawn. The drawn diagonals divide the $N\times N$ board into $K$ regions. For each $N$, determine the smallest and the largest possible values of $K$.
• (USA TSTST 2016) In the coordinate plane are finitely many walls; which are disjoint line segments, none of which are parallel to either axis. A bulldozer starts at an arbitrary point and moves in the $+x$ direction. Every time it hits a wall, it turns at a right angle to its path, away from the wall, and continues moving. (Thus the bulldozer always moves parallel to the axes.) Prove that it is impossible for the bulldozer to hit both sides of every wall.
• (China TSTST 2017) Every cell of a $2017\times 2017$ grid is colored either black or white, such that every cell has at least one side in common with another cell of the same color. Let $V_1$ be the set of all black cells, $V_2$ be the set of all white cells. For set $V_i (i=1,2)$, if two cells share a common side, draw an edge with the centers of the two cells as endpoints, obtaining graphs $G_i$. If both $G_1$ and $G_2$ are connected paths (no cycles, no splits), prove that the center of the grid is one of the endpoints of $G_1$ or $G_2$.
• (ISL 2023 C6) Let $N$ be a positive integer, and consider an $N \times N$ grid. A right-down path is a sequence of grid cells such that each cell is either one cell to the right of or one cell below the previous cell in the sequence. A right-up path is a sequence of grid cells such that each cell is either one cell to the right of or one cell above the previous cell in the sequence. Prove that the cells of the $N \times N$ grid cannot be partitioned into less than $N$ right-down or right-up paths.

Research Maths and Lasers

Warning: possible spoilers for some of the problems.

Lasers are more commonly known as billiards in the research world (where they obey the law of reflection) and have long been the subject of a huge amount of attention from many excellent mathematicians. In spite of this, or perhaps because of this, there are a lot of open problems. I'll try to give a flavour of some questions that researchers are interested in, though this is naturally skewed to my own tastes. Everything I cover here is for the two dimensional case, but you can, as others have done, ask similar questions in higher dimensions. 

Rational Polygons

The most general case asks what happens if you have a piecewise smooth curve as the boundary of a region where you shoot lasers. This is almost hopelessly intractable (as far as I'm aware it is not even known if every triangle has a periodic laser path) so mathematicians ask questions about restricted classes of objects. A rational polygon $P$ is a polygon whose angles are rational multiples of $\pi$. A generalised diagonal is a laser path which starts and ends at vertices of the polygon. (We assume that the laser paths never hit vertices except at the start and the end.)  Let $N_P(L)$ be the number of generalised diagonals in $P$ of length at most $L$. Groundbreaking work of Eskin, Mirzakhani, and Mohammadi, for which Maryam Mirzakhani was awarded the Fields Medal in 2014, shows that $\lim_{L \to \infty} \frac{N_P(L)}{L^2}$ exists for every $P$ and is a non-zero real number. Furthermore, there are only countably many possibilities.  (Heuristically, this is proportional to the number of grid points within a ball of a certain radius in the Euclidean plane, which is proportional to area, so you expect the growth of $N_P(L)$ to be roughly quadratic. Try and compute this limit for the unit square.)

Equidistribution

A problem that many people get given in the earlier stages of their training is this: Suppose you have two points $A,B$ on the same side of a line $l$. What is the shortest path from $A$ to $B$ that passes through a point on $l$? The answer, as you may well remember, is you reflect the point $B$ in $l$ and draw the straight line, then reflect the second half back across to $B$. But this shows that many people are aware of an idea of fundamental importance in this field: instead of letting the laser reflect, you can reflect the polygon/area under consideration instead! We can define the unfolding of a polygon $P$ as follows: consider all possible compositions of reflections in the sides of $P$. There are only finitely many of these precisely when $P$ has angles which are rational multiples of $\pi$ so we assume that. Call the images $g_1P \cdots g_nP$. These can be translated in the plane so that they are disjoint. Let $r$ be a reflection in one of the sides of $g_kP$. Then we glue together the corresponding sides of $g_kP$ and $r(g_kP)$, i.e. when a laser goes in one edge it emerges from the other edge, like in the early mobile phone game Snake (yes I'm old).

For example, if you do this with the square you get the following identifications:

Figure 3: if you take a piece of paper and glue the sides labelled $a$ to each other and the sides labelled $b$ to each other you will get a donut, otherwise known as a 2-torus.

If a laser hits a side labelled $a$ it will emerge from the other side labelled $a$, and so on.

Now I need to explain what I mean by equidistribution: Given a sequence $(x_n)$ of real numbers, we say that it is equidistributed if for any interval $I$ in $[0,1]$, the proportion of $x_n$ whose fractional part is in $I$ is approximately the length of $I$. In other words, the sequence is equally distributed and doesn't look like it clusters anywhere. (I am being a little imprecise here for the sake of exposition). The classic example, which apparently lots of contestants at IMO 2024 had on their minds, is the equidistribution theorem: for any irrational number $\alpha$ the sequence $x_n=n\alpha$ is equidistributed. 

One can ask the same thing in two dimensions: given a sequence of points in a surface, are they equidistributed, i.e. is the proportion that you see in a given area proportional to the area? Modulo the right technical definitions, you can ask this of lines too. To get a feel for this, try the square: if you start at the bottom right corner of the square, and shoot a laser at rational slope, it will stay on its trajectory, which is just a finite number of lines in the square. If you shoot a laser at irrational slope however, you will never visit the same point twice and go 'all over the place' very chaotically. These are equidistributed (this requires proof, but you see why it's believable). A satisfying result is that in any such unfolded polygon, if you pick a generic direction you will end up with an equidistributed line in exactly the same way.

The illumination problem

Given a (not necessarily convex) polygon $P$ and two points $x$ and $y$, say that $y$ is illuminated by $x$ if there is a laser trajectory going from $y$ to $x$. G. Tokarsky constructed in 1995 an example of a polygon which has points $x_0$ and $y_0$ that don't illuminate each other. The short and clever construction is as follows: by unfolding an isosceles right angled triangle $ABC$ with right angle at $B$ one can see that there is no laser path which starts and ends at $A$.

Figure 4: Tokarsky's polygon. The figure comes from Tabashnikov's excellent book 'Geometry and Billiards' which I consulted when writing this blog post.

The domain is constructed in such a way that all points labelled $B$ and $C$ are its vertices. I claim there is no laser path from $A_0$ to $A_1$. If there were such a path it would have to go through the interior of one of the eight right isosceles triangles adjacent to point $A_0$. Call this triangle $T$. Then the billiard path folds down to a billiard trajectory in $T$ that starts at $A_0$ and returns back to $A_0$, which we have just argued is impossible.

If your intuition says that this should somehow be a rare occurrence, e.g. because lasers can bounce around and hit lots of stuff, you may feel vindicated to know that in 2019, A. Wolecki proved that for rational polygons there are only finitely many pairs of points which don't illuminate each other. This again relies on the results of Eskin, Mirzakhani, and Mohammadi.

A related problem is the following: call a polygon $P$ secure if for any two points $A,B$ there is a finite set of points $C_i$ such that any laser path from $A$ to $B$ passes through some $C_i$. One can modify this definition to ask this for any Riemannian manifold. As an exercise, try to classify the secure regular polygons.

Physics and Lasers

Apparently a lot of mathematicians don't share my disdain for physics, so let me comment very briefly and vaguely on a couple of connections to physics despite not knowing anything about physics. The motivation from the physical side is obviously the study of optics, acoustics, mechanics and so on. I will spare you my attempt to butcher these topics, but I do recommend this video.

The study of what's known as symplectic topology is the natural tool for analysing lasers: it was quite literally built for the purpose of analysing motion of particles in physics by keeping track of both the position and the direction of the particle, or in this case the laser. For example, one can attempt to show the existence of periodic laser paths using this, or find so-called integrals of motion, which are roughly speaking quantities which don't change as the laser darts around. Think of angular momentum being conserved while objects spin.

Less obviously, one can study the quantum mechanics version of lasers, because why not. Much like how objects have natural frequencies where they resonate, quantum mechanical systems have certain eigenstates from which the overall behaviour is built up. The unexpected phenomenon displayed here is known as scarring, where these eigenstates 'know about' the laser path from classical mechanics (the probability density clusters around these paths). Now that's freaky.