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[11], 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[3]]=11... if perhaps that is of use.

  • 1
    $\begingroup$ 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. $\endgroup$ – flinty Sep 22 at 11:57
  • $\begingroup$ 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. $\endgroup$ – 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[2]], n]

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

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

(* 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$.

| improve this answer | |
  • 1
    $\begingroup$ 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! $\endgroup$ – David G. Stork Sep 22 at 21:26
  • $\begingroup$ 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. $\endgroup$ – flinty Sep 22 at 21:33
  • $\begingroup$ Take a look here: math.stackexchange.com/questions/3835531/… $\endgroup$ – David G. Stork Sep 22 at 21:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.