The Orbit Problem consists of determining, given a matrix
A in Rdxd and vectors
x, y in Rd,
whether there exists a positive integer n such that
An = y.
This problem was shown to be decidable in a seminal work of Kannan and
Lipton in the 1980s. Subsequently, Kannan and Lipton noted that the
Orbit Problem becomes considerably harder when the target y is
replaced with a subspace of Rd. Recently, it was shown that the
problem is decidable for vector-space targets of dimension at most
three, followed by another development showing that the problem is in
PSPACE for polytope targets of dimension at most three.
In this work,
we take a dual look at the problem, and consider the case where the
initial vector x is replaced with a polytope
P1, and the target is a
polytope P2. Then, the question is whether there
exists a positive integer n such
that An P1 intersects
P2. We show that the problem can be decided in PSPACE
for dimension at most three. As in previous works, decidability in the
case of higher dimensions is left open, as the problem is known to be
hard for long-standing number-theoretic open problems.
Our proof begins by formulating the problem as the satisfiability of a
parametrized family of sentences in the existential first-order theory
of real-closed fields. Then, after removing quantifiers, we are left
with instances of simultaneous positivity of sums of
exponentials. Using techniques from transcendental number theory, and
separation bounds on algebraic numbers, we are able to solve such
instances in PSPACE.
Proceedings of ICALP 17, LIPIcs 80, 2017. 14 pages.
PDF
© 2017 Shaull Almagor, Joël Ouaknine, and James Worrell.