Given $k\ge 2$, for which polynomials $P\in \mathbb{Z}[X]$ does there exist a function $h:\mathbb{N}\rightarrow\mathbb{N}$ with $h^{(k)}(n)=P(n)$?
Problem
Source: hmm (unsolved)
Tags: algebra unsolved, algebra
CANBANKAN
29.01.2022 07:18
Sadly the answer has no closed form.
If $P(x)=x+c$ then $h^{k+1}(x)=h(x+c)=h(x)+c$. Clearly $h$ is injective. I claim $k|c$ is sufficient and necessary. It is sufficient because $f(x)=x+\frac ck$ works.
Now I prove it's necessary. Since $h(x)$ is surjective mod $c$, it followos that $\{h(1),\cdots,h(c)\}$ is a surjection mod c. Let $d(x)=h(x)-x$ for $x\in \mathbb{N}$. Then $d(x)=d(x+c)$ and $h^k(1)+\cdots+h^k(c)=h^{k-1}(1)+\cdots+h^{k-1}(c)+\sum\limits_{j=1}^c d(x) = \sum\limits_{j=1}^c j + k\sum\limits_{j=1}^c d(x)$.
We know $h^{k+1}(1)+\cdots+h^{k+1}(c)=k\sum\limits_{j=1}^c d(x) + \sum\limits_{j=1}^c h(j)$
On the other hand, $h^{k+1}(1)=h(1)+c$ so this implies $\sum\limits_{j=1}^c d(x) = \frac{c^2}{k}$. Since $c\mid \sum\limits_{j=1}^c d(x)$ because $x+d(x)$ and $x$ when $1\le x\le c$ are both bijections mod $c$, $c\mid \frac{c^2}{k}$ so $k\mid c$, as needed.
Say $P(x)$ is not of the form $x+c$ and is positive whenever $x\in \mathbb{N}$ for now.
Draw an arrow from $x$ to $P(x)$. For all $x$, either there exists $m$ such that $P^m(x)=x$, or $x, P(x), P(P(x)), \cdots,$ is injective. Since $\mathbb{N}\backslash Im(P)$ is an infinite set, there are infinitely many $x$ such that $x$ is the root of a chain $x\rightarrow P(x)\rightarrow \cdots$. For size reasons, the number of $x$ such that $P^m(x)=x$ for some $x$ is finite because the leading coefficient of $P$ must be positive and for all sufficiently large $x$, $P(x)>x$.
If $P^m(x)=x$ has no solutions where $P(x)\ne x$ then we can have $h(x)=x\forall P(x)=x$ and for all other chains, you interweave them as follows:
suppose you have $k$ chains, call $x_1\rightarrow P(x_1)\rightarrow \cdots \rightarrow$, $x_2\rightarrow P(x_2)\rightarrow \cdots \rightarrow$, $\cdots$, $x_k\rightarrow P(x_k)\rightarrow \cdots \rightarrow$. If $P(x_i)=x_{i+k}$ then $h(x_i)=x_{i+1}$ works.
$P^m(x)=x$ makes things a lot harder because if a number with $t,P(t),\cdots,P^m(t)$ injective has $h(t), h^2(t), \cdots, h^n(t)$ injective. This means $x$ cannot be in $h^k(t)$. We also know that $h^{km}(x)=x$.
If $\gcd(m,k)=1$ there exists $ma\equiv k(\bmod\; 1)$; if $x_i=P(x_{i-1})$ then $x_{j+m}=x_j$ and we set $f(x_i)=x_{i+k}$.
If $\gcd(m,k)\ne 1$ this gets too messy...
RenheMiResembleRice
29.01.2022 09:03
quite beautiful assuming all the working out is correct
navi_09220114
11.02.2022 02:51
bumpppp!
Tintarn
11.02.2022 22:40
navi_09220114 wrote: bumpppp! What do you mean? It was already explained in #2 that your question has no meaningful answer in general...
navi_09220114
11.02.2022 23:11
But how do you know for sure that it has no meaningful answer in general?
CANBANKAN
12.02.2022 10:20
I will work on this tomorrow and give a detailed characterization of all working $P$ based on its orbits (i.e. for each $l$, find number of integers such that $P^l(x)=x$ but $P(x), P^2(x), \cdots, P^{l-1}(x)$ aren't equal to $x$. If you want, have fun characterizing all $x$ such that $P^l(x)-x$ has exactly $t$ positive integer roots... I forgot to state that $P(x)>0$ for all $x\in \mathbb{N}$ as well is another important condition in my characterization...
navi_09220114
30.05.2022 22:15
It can be proven that the following is true: If $P$ is an integer valued polynomial with the following conditions: i) $P(n)>0$ for all $n\in \mathbb{N}$ ii) $P(a)=P(b) \Rightarrow a=b$ for all $a, b\in \mathbb{N}$ iii) $k\mid |X|$ or $|X|=\infty$, where $X=\mathbb{N}\backslash \{P(n): n \in \mathbb{N} \}$ [The former case is mostly there just to deal with the case $x+c$] Then there exist a function $f:\mathbb{N}\rightarrow \mathbb{N}$ with $f^k(n)=P(n)$ for all $n\in \mathbb{N}$. [Without injectivity though, then the orbit structure can be quite annoying..]