Is this P3? I see two P2's posted rn.

Nice problem, bump!

My problem! I was originally thinking about "what if an FE was almost satisfied", which led me to an equation like $|f^{f(m)}(n)-f^{f(n)}(m)|=1$. But as I worked through it, I realized I could drop a lot of conditions and generalize deductions, leading the the current formulation. I knew this problem was hard, but considering how there are no solutions posted yet, the problem was probably harder than expected. Here's my original solution: Let $f$ be as above, and assume that $|f^{f(m)}(n)-f^{f(n)}(m)|\leq N$ for all $m,n$. Lemma 1: $f$ is injective. Proof: If $f(a)=f(b)$, then $f^{f(a)}(b)=f^{f(b)}(a)$, which is impossible unless $a=b$. $\square$ Lemma 2: For any $n$, if $f^i(n)=f^j(n)$, then $i=j$. Proof: Suppose $f^i(n)=f^j(n)$ for some $i\neq j$. Then the set $S=\{f^k(n)\}$ must be finite. But by assumption, for all $m$, $f^{f(n)}(m)$ is within $N$ of some element of $S$, and there are only finitely many such numbers. Thus, there exist some $m_1\neq m_2$ with $f^{f(n)}(m_1)=f^{f(n)}(m_2)$. But then by injectivity, we must have $m_1=m_2$, which is a contradiction. Thus, our assumption was wrong, so $i=j$. $\square$ Let a chain be a (potentially infinite) list of the form $\dots\to f^{-1}(n)\to n\to f(n)\to f^2(n)\to\dots$ Note that by injectivity and no cycles, all chains are distinct, disjoint, and infinite. Lemma 3: There are at most $2N+1$ chains. Proof: Assume there were at least $2N+2$ chains, and let $m_1,\dots,m_k$ be numbers in distinct chains. Let $B>\max\{f(m_1),\dots,f(m_k)\}$, and let $m=m_i,n=f^{B-f(m_i)}(n)$ in the boundedness condition. We get $$\left|f^B(n)-f^{f^{B-f(m_i)+1}(n)}(m_i)\right|\leq N$$Thus, the chain with $m_i$ must intersect $\left[f^B(n)-N,f^B(n)+N\right]$, which has $2N+1$ elements. Thus, if there were $2N+2$ distinct chains, two chains would meet in this set, which would imply they were the same chain, which is a contradiction. Thus, there are at most $2N+1$ chains. $\square$ Lemma 4: There is only one chain, and it only extends infinitely in one direction. Proof: Fix some integer $c$. I claim that all but finitely many numbers are ahead of $c$ in its chain (are of the form $f^k(c)$ with $k\geq 1$). Call a number bad if it is not of this form. Note that as $n$ varies, $f^{f(c)}(n)$ achieves all sufficiently large integers, since there are only finitely many chains. Thus, if $A,B$ are sufficiently large integers, every value in $[A,B]$ is achieved as $f^{f(c)}(n)$. But then $f^{f(n)}(c)\in [A-N,B+N]$ for all such $n$, and these values are all distinct, since $f^{f(n)}(c)=f^{f(m)}(c)\implies f(n)=f(m)\implies n=m$. Thus, for all sufficiently large $A,B$, the interval $[A-N,B+N]$ contains at least $B-A+1$ numbers of the form $f^{f(n)}(c)$, so at there are at most $2N$ bad numbers in this interval. But if there were infinitely many bad numbers, then for some large $A,B$, $[A-N,B+N]$ would contain at least $2N+1$ such numbers, which is a contradiction. Thus, there are only finitely many bad numbers. Now, if there were at least 2 chains, the chain without $c$ would have infinitely many bad numbers. Similarly, if the chain with $c$ extended infinitely in both directions, then there would also be infinitely many bad numbers (every number of the form $f^{-k}(c)$). Thus, there is exactly one chain and it only extends infinitely in one direction. $\square$ If we let $c$ be the starting point of the chain, every integer is of the form $f^k(c)$, where $k\geq 0$. (Let $f^0(c)=c$). For ease of notation, define a function $g:\mathbb{N}_0\to\mathbb{N}$ with $g(k)=f^k(c)$. ($\mathbb{N}_0=\mathbb{N}\cup\{0\}$) By our above lemmas, $g$ is a bijection. By letting $m=f^a(c),n=f^b(c)$, the two conditions are equivalent to $|g(g(a+1)+b)-g(g(b+1)+a)|\leq N$, and $g(g(a+1)+b)\neq g(g(b+1)+a)$ for all $a\neq b$. Thus, $g(a+1)-a\neq g(b+1)-b$ for all $a\neq b$. Lemma 5: For all $M$, there exists an integer $x$ with $g(x)\leq x-M$ Proof: Assume not, so $g(x)-x$ is bounded below. But $g(x)-x$ is injective by above (assuming $x\geq 1$), so for any $K$, there exists $B$ such that $g(x)-x\geq K$ for all $x\geq B$. But then $\{g(B+1),g(B+2),\dots\}\subseteq [B+K,\infty)$, while $\{g(0),\dots,g(B)\}$ only achieves $B+1$ values. Thus, at least $K-1$ values are not achieved by $g$, which is a contradiction. Thus, $g(x)-x$ is not bounded below. $\square$ Now pick $B$ such that $g(B)+N\leq B$. By setting $b=B-g(a+1)$, we get $$|g(B)-g(g(B+1-g(a+1))+a)|\leq N$$for all $a$ with $g(a+1)\leq B$. Let $t=\max\{g^{-1}(g(B)-N),g^{-1}(g(B)-N+1),\dots,g^{-1}(g(B)+N)\}$. Note that $g(t)\leq g(B)+N\leq B$ and $t\geq 1$, so setting $a=t-1$, we have $g(a+1)\leq B$, so we can plug in $a$ to get $$|g(B)-g(t-1+g(B+1-g(t)))|\leq N$$Thus, $t-1+g(B+1-g(t))\in\{g^{-1}(g(B)-N),\dots,g^{-1}(g(B)+N)\}$. But $t$ was the maximum such element, which means $g(B+1-g(t))=1$, or $B+1-g(t)=g^{-1}(1)$. Since $|g(t)-g(B)|\leq N$, we have $|(B-g(B))+1-g^{-1}(1)|\leq N$. Thus, there are only finitely many values for $B-g(B)$. But there are infinitely many $B$ with $g(B)+N\leq B$ by Lemma 5, which is a contradiction since $g(x)-x$ is injective. Thus, our original assumption was wrong, so $|f^{f(n)}(m)-f^{f(m)}(n)|$ must be unbounded. $\square$

Assume for sake of contradiction that such an $f$ does exist so that $\Delta(m,n)$ is bounded. Claim 1: $f$ is injective If $f(a)=f(b)$ but $a\neq b$, then we have $\Delta(a,b)=0$, contradiction. Now this implies that $f$ is a union of chains and cycles. Claim 2: $f$ has no cycles Suppose $f$ has a cycle. By injectivity, nothing "feeds into" this cycle. Suppose $n$ is in a cycle. Then $f^{f(m)}(n)$ is bounded. However, we can pick an $m$ (either in a chain, or an arbitrarily large cycle) so that $f^{f(n)}(m)$ is arbitrarily large, which contradicts the fact that $\Delta$ is bounded. Call a chain bidirectional if every element in the chain has an inverse, and call a chain unidirectional if there exists an uninvertable element in the chain. Claim 3: all chains are unidirectional Suppose we have a bidirectional chain containing $a$. Let $f^{-a}$ denote the inverse of $f$ applied $a$ times. Choose $n=f^{-f(m)}(a)$. Choose an $m$ in a chain so that all terms past $m$ are above some constant $C$. Then the left term in $\Delta$ is fixed. However, the term on the right of $\Delta$ is above our arbitrary constant $C$, so we get a contradiction from the boundedness of $\Delta$. Now replace $\Delta$ with $\epsilon(a,b)=f^{a-1}(b)-f^{b-1}(a)$ for convenience. Let the domain of $\epsilon$ be all numbers other than the starts of chains. Then clearly the problem conditions are equivalent to $\epsilon(a,b)$ being both nonzero and bounded. Claim 4: There are a finite number of chains Suppose we have two chains $A$ and $B$. Suppose $A$ contains $a$ (not at the start), and $B$ contains $b$ (also not at the start). Further suppose $\epsilon$ is bounded by an integer $C$. Then there must exist an element of $A$ within $C$ of $f^{a-1}(b).$ Similarly, there must exist an element of $A$ within $C$ of $f^{a-1}(f(b))=f^{a}(b)$. We can repeat this to get that after some point, every element of $B$ has an element in $A$ within $C$ of it. Say we have $B$ and $2C+1$ other chains. Then these other chains must all track $B$ eventually, however there are only $2C$ possible values within $C$ of each element of $B$, so we get a contradiction. Now for the most difficult part of the proof. This is a fairly involved argument. Claim 5: $f(x)-x$ is bounded Plugging in for our definition of $\epsilon$, $\epsilon(a,b)=f^{a-1}(b)-f^{b-1}(a)$ $\epsilon(f^n(a),b-n)=f^{f^n(a)-1}(b-n)-f^{b-1}(a)$ Subtracting these, we see that we must have $f^{f^n(a)-1}(b-n)-f^{a-1}(b)$ is bounded by some constant $C$. We can get $b-1$ of these expressions as $n$ varies from $1$ to $b-1$. This means that $g(a,b,n)=f^{f^n(a)-1}(b-n)$ takes on at most $2C+1$ values as $n$ varies from $1$ to $b-1$ for any given choice of $a, b$. Now examine what happens when $g(a,b,i)=g(a,b,j)$. Clearly $b-i$ and $b-j$ must be in the same chain. Let the start of the chain be $a$, and assume that $i$ is $I$ from the start of the chain and $j$ is $J$ from the start of the chain. Then matching exponents we must have $f^i(a)+J-1=f^j(a)+I-1 \iff f^j(a)-J=f^i(a)-I$. Assume $f(x)-x$ is unbounded for the sake of contradiction. Now choose $b$ sufficiently large for the rest of the argument to work and focus on the chain $A$. Then we have at most $2C$ possible values of $g$ over the elements of chain $A$ which are less than $b$. However, from before, this implies we have at most $2C$ possible values of $f^i(a)-I$, where $i$ is such that $b-i$ is in chain $A$. Since all chains must eventually track $A$, we know that $A$ has positive density in the integers (specifically, density approaching at least $\frac{1}{2C+1}$. Thus we have at least a constant proportion of $i$'s such that $b-i$ is in chain $a$. Now observe that since for all $a$ we have at most $2C$ possible values of $f^i(a)-I$, say $x_1,\cdots,x_X$ we also have at most $2C$ possible values of $f^i(f(a))-I=f^{i+1}(a)-I$, say $y_1,\cdots y_Y$. This means we have at most $4C^2$ possible differences between an $x$ term and a $y$ term. However, consider the difference between $f^i(a)-I$ and $f^{i+1}(a)-I$, which is $f^{i+1}(a)-f^i(a)$. We know that $f^{i+1}(a)-f^i(a)$ can only take on at most $4C^2$ values for $b-i$ in chain $A$. This means $f^{i+1}(a)-f^i(a)$ takes on at most $4C^2(2C+1)$ values on all chains. Now given that $f$ is unbounded, it must be unbounded on some chain. Choose $a$ in that chain. Then $f^{i+1}(a)-f^{i}(a)$ can take on arbitrarily many consecutive values of $f(x)-x$ on this chain by choosing $b$ large. This is a contradiction, thus $f(x)-x$ is bounded. Now let $k$ be such that $f(x)-x$ is bounded by $k$ Okay now that we're done with that, time for the cleanup. Claim 6: $f$ consists of a single chain Fixing our value of $a$ in $\epsilon$, we get that $f^{b-1}(a)$ is bounded by some constant $K$ plus $f^{a-1}(b) \le b+(a-1)k = b+(a-1)k$. If $f$ consists of multiple chains, each with positive density, then $f^{b-1}(a)$ should grow at least a constant greater than one times faster then the identity function (because a positive proportion of the possible values are taken up by another chain). This is a contradiction. Claim 7: such $f$ does not exist. Let $F(x)$ be the number of iterations of $f$ from the start of the chain required to get to $x$. Then from the fact that $\epsilon$ is nonzero, we get that $F(a)+b-1\neq F(b)+a-1 \iff F(a)-a \neq F(b)-b$. This means that eventually, we have $F(x)-x$ has magnitude above some arbitrarily large constant. However, observe that $(F(f(x))-f(x))-(F(x)-x)=x-f(x)+1$, which is bounded. This implies that eventually $F(x)-x$ is strictly positive or strictly negative, since it changes by a bounded amount. If $F(x)-x$ grows so that it is eventually arbitrarily large and positive, then this means that the number of iterations of $f$ to reach $x$ is eventually arbitrarily larger than $x$. However this poses a clear contradiction, because up to any constant $N$ ($i$ ranges from $1$ to $N$) there exists a value at least $N$ in $f^i$ of the start of the chain. Similarly, if $F(x)-x$ grows so that it is eventually arbitrarily small and negative, this means that the number of iterations of $f$ to reach $x$ is less than $x$ by an arbitrary quantity. However, this implies that we will necesarilly "skip over" some integers in our chain, never to return to them which means there are multiple chains, contradicting claim 6.

AdventuringHobbit wrote: Subtracting these, we see that we must have $f^{f^n(a)-1}(b-n)-f^{a-1}(b)$ is bounded by some constant $C$. We can get $b-1$ of these expressions as $n$ varies from $1$ to $b-1$. This means that $g(a,b,n)=f^{f^n(a)-1}(b-n)$ takes on at most $2C+1$ values as $n$ varies from $1$ to $b-1$ for any given choice of $a, b$. Now examine what happens when $g(a,b,i)=g(a,b,j)$. Clearly $b-i$ and $b-j$ must be in the same chain. Let the start of the chain be $a$, and assume that $i$ is $I$ from the start of the chain and $j$ is $J$ from the start of the chain. Then matching exponents we must have $f^i(a)+J-1=f^j(a)+I-1 \iff f^j(a)-J=f^i(a)-I$. Shouldn't this be $b - i$ and $j - i$ for start of chain, giving something like $f^{j}(a) + J = f^{i}(a) + I$?

Reducted

lol why did this take me like 8 hours over two days same solution as #4 up to cosmetic differences: namely to prove lemma 4 I did the following:

also i insisted on using a sequence of $a_i$'s instead of defining $g$. mistake. when i needed the inverse i was so close to defining $b_{a_n} = n$ and then decided to define $a(n) := a_n$ instead. nice to know that $f(x) - x$ is bounded re #5, i thought this for so long but couldn't prove it : god this is such a good problem