# Solving an equation with compounded functions

This is a Mathematica-based question derived directly from this math question.

Given that f[x] is monotonically increasing and f[f[x]] == x^2 + 2, find f, where x and f[x] are in the integers.

I tried applying inverse functions (and found the inverse of the compounded functions is $$-\sqrt{x-2}$$), and all obvious applications of Solve without luck. Note that f[f]=11... if perhaps that is of use.

• Possibly related to mathematica.stackexchange.com/questions/227863/… and mathematica.stackexchange.com/questions/817/… but for integers instead of the reals. Unfortunately the Carleman matrix method won't work here due to the nature of x^2+2 - it's an even function so the matrix is singular. – flinty Sep 22 at 11:57
• f[x_] := If[x > 0, -x^2, -x + 2] will work if you sacrifice 'monotonically increasing' and restrict the range to x > 0. The first application of y = f[x] will 'save or 'memorize' the value of x^2 by sticking it in the negative numbers so that the second application knows if y is negative then it just has to add two. Of course, this feels like cheating, but it leads me to suspect it's impossible to construct a function that has all these properties simultaneously and works on all the integers. If the domain is finite, there may be a permutation which works though. – flinty Sep 22 at 21:59

I came across this answer here https://math.stackexchange.com/a/3599697/775158. It's miraculous that it works, at least I think so. The resulting half-iterate $$h$$ is not perfect as $$\forall x\in\mathbb{Z} : h(x)$$ is not necessarily an integer. But it is true that $$\forall x\in\mathbb{Z^+}: h(h(x))\in\mathbb{Z^+}$$ and $$h$$ is monotone over the positive reals.

g[n_] := Nest[Function[{x}, Evaluate[Sqrt[#[(x^2 + 2)] - 2]]] &,
Function[{x}, Abs[x]^Sqrt], n]

(* we get very good convergence for n > 3 *)
h = g;

(** g is this thing
Function[{x}, Sqrt[-2 +
Sqrt[-2 +
Sqrt[-2 +
Sqrt[-2 + Abs[2 + (2 + (2 + (2 + x^2)^2)^2)^2]^Sqrt]]]]]
**)

N[h[h]]
(* result 11. *)
`

So we have a good approximation for the half-iterate like this: $$h(x)\approx\sqrt{\sqrt{\sqrt{\sqrt{\left(\left| \left(\left(\left(x^2+2\right)^2+2\right)^2+2\right)^2+2\right| ^{\sqrt{2}}\right)^{\sqrt{2}}-2}-2}-2}-2}$$ I also looked for an integer $$x$$ such that $$h(x)$$ is close to an integer and I found $$h(36)\approx159.001$$. We also have $$h(11)\approx 30.014$$.

• Gee.... that's a lot of work and an awkward function. Definitely worth $+1$, but I'll keep the question open just in case there's a "more perfect" (and integer) solution. Thanks! – David G. Stork Sep 22 at 21:26
• Yes functional equations are very weird and the literature on them is all over the place. There doesn't seem to be a one-size-fits-all solution to these kinds of problems out there. I tried my pytorch neural network solver from my question I linked in the comments. There's something about the evenness / symmetry of some functions that makes the convergence very poor. Whereas an odd function like a cubic would probably have a strange half iterate but one that could be easily found using the Carleman matrices or the Newtonian method as I mentioned earlier. – flinty Sep 22 at 21:33
• Take a look here: math.stackexchange.com/questions/3835531/… – David G. Stork Sep 22 at 21:55