<p>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$. </p>

<p>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. </p>

CC BY-SA 3.0
2018-01-10T12:18:47.137Z
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
Amaury Pouly
CC BY-SA 3.0
2017-10-29T17:53:17.117Z
Please check whether my edit accurately reflects the problem you are asking about.
D.W.
CC BY-SA 3.0
2017-10-29T17:55:07.353Z
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$?
D.W.
CC BY-SA 3.0
2017-10-30T14:16:12.197Z
@AndrásSalamon, better now?
D.W.
<polynomials><decidability><fixed-points>
Deciding reachability under iterated independent polynomial mapping
Liam_math
# Deciding reachability under iterated independent polynomial mapping

(Asked by: username_0 on 2017-10-28)

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.

**Tags:** polynomials, decidability, fixed-points

> **Comments:**
> **username_2**: Please check whether my edit accurately reflects the problem you are asking about.  
> **username_2**: 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$?  
> **username_2**: @AndrásSalamon, better now?  
> **username_1**: 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  

---

## 0 answers

