On the 2D Rotation Rounding Problem

Here’s a simple dynamical system. You start with a 2D integer vector v = (x,y). Now you rotate this vector around the origin by a fixed angle. This gives you a vector Mv(where M is the rotation matrix). You now round this vector to the nearest integer lattice point, producing a new integer vector [Mv]. You can repeat this process of rotation and rounding to produce [M[Mv]], [M[M[Mv]]] and so on.
The 2D Rotation Rounding Problem is very easy to state: Does this sequence always end up repeating?

It doesn’t sound very hard, and if you change the question slightly, it becomes quite simple. If there was no rounding the answer is YES if the angle is a root of unity, and NO if it’s not (essentially by definition).

If we always rounded down (towards the origin), there’s only a finite number of integer vectors at the same or smaller distance from the origin and so by the pigeonhole principle , eventually you must repeat.

But by going to the nearest integer point we sometimes round up, and its juuust possible that – to quote Joel – “the planets align perfectly” and you keep getting to round up often enough to escape to infinity and beyond.

I tried testing a few examples.

Here’s an illustration of what happens with v = (83,143) and angle 36  \pi /47

Colors change from dark to light over time

It repeats at the 715th iteration.

In all the examples I tried, the sequence started to repeat within the first 1000 iterations. The authors of Reachability in dynamical systems with rounding never found a non-repeating sequence either, and they conjecture none exist.

The trouble is that large starting vectors are more likely to diverge to infinity (more options to avoid being pigeonholed), so running simulations for a finite number of starting points doesn’t confirm anything.

So the only way forward is to prove that all sequences repeat (or not). But how?

Points that get rounded up (yellow), down (red) or stay the same distance from the origin (blue).

Leave a Reply

Your email address will not be published. Required fields are marked *