For any $1\leq i\leq m$, $f_i: \mathbb{Q}\rightarrow \mathbb{Q}$ is a polynomial mapping over $x_i$, where $\mathbb{Q}$ is the set of rationals. For $\vec{a}_0=(a_1, \cdots, a_m)\in \mathbb{Q}^m$, we define $\vec{y}_n=(f_1^n(a_1), f_2^n(a_2), \cdots, f_m^n(a_m))$, where $f_i^n$ represents the $n$-fold composition of $f_i$, i.e., $f_i(f_i(\cdots(\cdot)))$. The problem is to decide, given $f_i,\vec{a},\vec{c},d$, whether there exists some $n\geq 0$ such that $\vec{c}\cdot \vec{y}_n=d$, i.e., $\vec{y}_n$ lies in the hyperplane given by $\vec{c}\cdot \vec{y}=d$.

Is this problem decidable? I conjecture it is not. What I know is that even for $m=2$ and each $f_i$ being linear, the problem is undecidable if $f_i$ were defined over $(x_1, \cdots, x_m)$. However, here coordinates are independent so the undecidability does not seem to be straightforward.

  • $\begingroup$ Please check whether my edit accurately reflects the problem you are asking about. $\endgroup$ – D.W. Oct 29 '17 at 17:53
  • $\begingroup$ What are your thoughts? Have you figured out anything about some special cases? It appears to be decidable when all the $f_i$'s have degree 1. Have you thought about the degree-2 case? Do you have an algorithm for the case where $m=1$? $m=2$? $\endgroup$ – D.W. Oct 29 '17 at 17:55
  • $\begingroup$ @AndrásSalamon, better now? $\endgroup$ – D.W. Oct 30 '17 at 14:16
  • $\begingroup$ This is a very interesting question, where does it come from? I have the feeling that it might be loosely related to the following: given a piecewise affine function $f:\mathbb{R}\to\mathbb{R}$ and and interval $[a,b]$, does there exists $n\in\mathbb{N}$ such that $f^m(x)\in[a,b]$. This is your problem with $m=1$ and a piecewise affine of polynomial mapping. This problem is not known to be decidable or undecidable, and is related to "strange billiards". See Reachability problems in low-dimensional iterative maps, Oleksiy Kurganskyy Igor Potapov and Fernando Sancho Caparrini $\endgroup$ – Amaury Pouly Jan 10 '18 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.