Let $P \subset \mathbb{R}^2$ be a polygon with rational coordinates, and consider discrete billiards inside $P$, where a ball (of zero radius) moves by steps of fixed length on each step, in a rational direction, bouncing off walls. This system is reversible, and you can approximate it efficiently (by fixed or floating point arithmetic). Can you approximate it reversibly and efficiently?
You could extend this in many directions, by generalizing $P$ (higher dimensions, curves, obstacles inside), or you could have multiple bouncing bodies, friction, etc. I'll concentrate on polygonal billiards but a general method is of interest.
First, let's agree on a specific flavor of billiards. Fix once and for all some (non-intersecting) closed polygon $P \subset \mathbb{R}^2$ with rational coordinates (we just need that we can algorithmically quickly figure out approximations to them). Fix also a number $R$, and let $D$ be the closed disc of radius $R$. Now, billiards is the (abstract) dynamical ($\mathbb{N}$-)system $s : P \times D \to P \times D$ where $s(p, d)$ is obtained by moving $p$ forward by offset $d$, with usual (zero radius) billiard collisions. (If you hit a corner, we just canonically pick an infinitesimal side that's hit.)
I'll write some formulas for completeness. We define $s(p, d) = s'(p, d, d)$ where $s' : P \times D \times D \to P \times D$ is defined like so: Write $[u, v] = \{\alpha u + (1-\alpha) v \;|\; \alpha \in [0,1]\}$ for the line segment between $u$ and $v$, and $[u, v)$ is the half-open segment. If $[p, p + d'] \subset P$, define $s(p, d, d') = (p + d', d)$. Otherwise, there is a maximal $\alpha \in [0,1)$ such that $[p, p + \alpha d'] \subset P$, write $q = p + \alpha d'$. Suppose the line segment containing $q$ is $[u, v)$ where $u, v$ are vertices of $P$ in counterclockwise order. Let $v_0 = (v-u)/|v-u|$ be the tangent, and $v_1 = e^{\pi/2 i} v_0$ the normal, write $d = d_0 v_0 + d_1 v_1$, $d' = d_0' v_0 + d_1' v_1$ and define $$ s'(p, d, d') = s'(q, d_0 v_0 - d_1 v_1, d_0' v_0 - d_1' v_1). $$
A couple of points.
- For these formulas to well-define $s$, you need that there are finitely many bounces, i.e. the induction reaches the base case. This is not obvious syntactically, but if you've played billiards before it's easy to see there is actually a bound on the number of bounces independently of $(p, d) \in P \times D$. One way to see this: The main issue are corners. When the ball gets near a corner, think of the sides as mirrors and unfold the corner sort sort of like the Riemann surface of $\log$, and observe that the billiard path becomes a straight line; you see that the maximal number of bounces before leaving the vicinity of the corner is bounded by $\pi/\alpha + 1$ where $\alpha$ is the angle.
- The map $s$ is bijective on $P \times D$. Namely, $s^{-1}(p, d) = (q, -d')$ where $s(p, -d) = (q, d')$.
- If you like, you can do everything with rationals, since $s(p, d) \in \mathbb{Q}^4$ whenever $p \in P \cap \mathbb{Q}^2$ and $d \in D \cap \mathbb{Q}^2$, and $P$ has rational coordinates. By the formula for the inverse, this restriction of $s$ is also bijective.
Second, let's agree on what an approximation scheme for such a system is. If $M$ is a metric space and $f : M \to M$ is a function, an $\epsilon$-approximation scheme for $(M, f)$ is a tuple $(S, g, \imath, o)$ where $g : S \to S$, $\imath : M \to S$, $o : S \to M$, such that $\imath \circ o = \text{id}_S$, and $o \circ i \approx_{\epsilon} \text{id}$ and $o \circ g \circ \imath \approx_{\epsilon} f$ where $\approx_{\epsilon}$ for two functions means they are at Hausdorff distance less than $\epsilon$ as relations. You can think of the conditions on $\imath \circ o$ and $o \circ \imath$ as saying that $S \subset M$ is an $\epsilon$-net, and the condition on $o \circ g \circ \imath$ says that every point $x$ has a close by point of $S$ that's moved by $g$ roughly as $f$ does, and vice versa. An approximation scheme is finite if $S$ is.
On $P \times D$, we use the Euclidean metric. The following should be straightforward to prove, just use fixed-point arithmetic for the calculation. For the direction that every $x \in M$ is tracked by some $y \in S$, observe that discontinuities are rare and take a small enough $\epsilon > 0$. I haven't written an argument down; if you can refute this claim that's an acceptable answer.
Claim. For all $\epsilon$, there exist a finite $\epsilon$-approximation scheme for $(P \times D, s)$.
For the rest of this post I'll assume that's true. Now, while $(P \times D, s)$ is reversible, it is not clear that the arithmetic magically always rounds so there are no collisions, and so the naive fixed-point approximation might not be bijective. Let us say a finite $\epsilon$-approximation scheme is reversible if $g$ is bijective on $S$. My gut says that the following is easy to obtain from Hall's theorem, though I'm not sure how to proceed to get a clean proof:
Claim-ish conjecture. For all $\epsilon$, there exists a finite reversible $\epsilon$-approximation scheme for $(P \times D, s)$.
The idea for the proof would be that you fix a discrete set of directions and a discrete set of positions. If you have a single wall, you can match up the directions to roughly their mirrored versions, and if you have a point cloud hit the wall, some geometry of numbers shows that the point cloud's $\epsilon$-blow up contains more points of $S$ than the cardinality of the point cloud, which is what Hall's theorem needs. For multiple collisions interacting there are some issues and I didn't do the calculations. If you can refute the conjecture, that's an acceptable answer. If you have a clean proof of the conjecture, that's very interesting (but not an acceptable answer). For the rest of the post I'll assume this conjecture is true.
The third and final ingredient is the fully polynomial-time approximation scheme. (I'm borrowing the term from complexity theory since I feel it's close in spirit.) A fully polynomial-time approximation scheme or FPTAS for a system $(M, f)$ is a four-tuple $(S, g, \imath, o) = (S_n, g_n, \imath_n, o_n)_{n \in \mathbb{Z}_+}$. The tuple $(S_n, g_n, \imath_n, o_n)$ must be a $1/n$-approximation scheme for $(M, f)$. Additionally, $S_n \subset \Sigma^{p(n)}$ for some polynomial $p(n)$ and finite alphabet $\Sigma$, and it should be polynomial-time computable uniformly in $n$. Similarly, $g_n : S_n \to S_n$ is a polynomial-time computable function (so it's a function in the class FP) uniformly in $n$. We similarly define a strong FPTAS, with the difference that $(S_n, g_n, \imath_n, o_n)$ is a $1/2^n$-approximation scheme for all $n$. Such a scheme is reversible if all the $(S_n, g_n, \imath_n, o_n)$ are.
Claim. There exists a strong FPTAS for $(P \times D, s)$.
I haven't written a careful proof of this, but its proof should be the same as for the claim above: the proof is completely algorithmic and the number of bounces is bounded by a constant (independent of $\epsilon$) so the calculations go through in polynomial time. (If you can refute this claim that's an acceptable answer.)
Now, assuming the above claims are true, we can state the question I'm interested in.
Question. Does there exist a reversible FPTAS for $(P \times D, s)$? A reversible strong FPTAS?
For the first question, you could imagine just listing a concrete discretization, and realizing Hall's theorem (if it works the way I think), but I don't know if there is a relevant "polynomial-time Hall's theorem". For the latter, you'd presumably need some real understanding of what's going on.
