$\newcommand{\nest}{\operatorname{nest}}$Let's define a function $\nest(f, x, k)$, which takes a function $f$, an input $x$, and a non-negative integer $k$, and calls $f$ on $x$ repeatedly ($k$ times). For example, $$ \nest(f, x, 0) = x\\ \nest(f, x, 1)=f(x)\\ \nest(f, x, 2)=f(f(x))\\ \nest(f, x, 3)=f(f(f(x)))$$ Formally, this function can be written as $$ \nest(f, x, k)= \begin{cases} x & \text{if } k=0\\ \nest(f, f(x), k-1) & \text{otherwise} \end{cases}$$

For a given $k$ and a polynomial $p$, how can I find a function $f: \mathbb C \to \mathbb C$ such that $\nest(f, x, k)=p(x)$?

If it's not possible to do so in the general case, is it possible with $p(x)=c+x^2$?

  • 2
    $\begingroup$ I don't know about $c+x^2$ but I found the function $f(x)=\sqrt{x^2+\frac{c}{k}}$ for $p(x)=\sqrt{c+x^2}$ $\endgroup$ – Shrey Joshi Jul 19 '18 at 20:11
  • 2
    $\begingroup$ It's not to hard to find a function $f$ of that sort. For $k = 2$, for example, start with two arbitrary numbers $a$ and $b$, and define $f$ to act according to the chain $a \mapsto b \mapsto a^2 +c \mapsto b^2 + c \mapsto (a^2 + c)^2 + c \mapsto \cdots$. Then take two other starting numbers that don't appear in that chain and repeat. (If separate chains eventually overlap, then join them into a tree structure.) Whether any function $f$ with a remotely interesting functional form exists, of course, is a different question. $\endgroup$ – Connor Harris Jul 19 '18 at 20:17
  • 2
    $\begingroup$ Doubt you can find one for $p(x)=c+x^2$. At least if you want $f$ to be holomorphic. Such functions fold the complex plane onto itself. Compositions will fold the plane a power of that original number. For example, if $f$ doesn't fold the plane, neither will any of its further nestings. If $f$ folds the complex plane with two layers, the 2nd nesting will fold the plane with four layers. $3$ layers will result in $9$ layers on the next nesting. $2$ is not a tenable power for foldings of a nesting. Probably can be made rigorous with the Argument principle. $\endgroup$ – coffeecaracal Jul 19 '18 at 20:29
  • $\begingroup$ I tried to find a series expansion for $f(x)$ with $k=2$ and $p(x)=1+x^2$ over $[0,1]$ using $11$ equally spaced points and minimizing the SSR. I get $f(x)\approx0.643+0.033x+0.940x^2-0.201x^3$. It fits so well that I'd assume $f(x)$ exists in this case. But whether it has a closed form or exists over all of $\mathbb{C}$ is another question. Regardless, you might be able to find approximations to your $f(x)$'s Graph: desmos.com/calculator/vf5fdpjbwi $\endgroup$ – Jam Jul 19 '18 at 20:41
  • 3
    $\begingroup$ What you're looking for are called fractional iterates of the (polynomial) function; see e.g. this WIkipedia bit or this one or this previous math.se question $\endgroup$ – Steven Stadnicki Jul 19 '18 at 21:06

You are really asking about functional iterates, normally denoted by $f^ n(x)\equiv \operatorname{nest}(f, x, n)$. I gather you are interested in problem solving methods over rigor.

They are normally obtained by functional iteration through Schröder's equation, but even your simple quadratic $p(x)=x^2+c$ does not have closed solutions, except, e.g., for $c=-2$, a "chaotic" logistic map , as you may see from the examples in the WP article linked above.

In that celebrated special case, a closed form (p302) was found by Ernst Schroeder himself (1870).

Namely, for
$$ p(x)= x^2-2, $$ it follows directly that for $$ y=\frac{x\pm \sqrt{x^2-4}}{2} $$ that is $$ x=y+y^{-1}, $$ one has $$ p(x)=y^2+y^{-2}\equiv p^1 (x). $$ Whence,
$$ p^n (x)= y^{2^n}+ y^{-2^n}. $$

More formally, in E.S.'s language of conjugacy, $$ \psi(p(x))=g(\psi(x)),\\ \psi(x)=\frac{x\pm \sqrt{x^2-4}}{2}\\ g(y)=y^2 \qquad \Longrightarrow \\ g^n(y)=y^{2^n};$$ so that $p(x)= \psi^{-1} \circ g \circ \psi (x)$, and $$p^n= \psi^{-1} \circ g^n \circ \psi ~.$$

I am restricting this to real variables and domains where the objects treated make sense. Your particular question $f^k (x)=x^2-2=p(x)$ then can produce $p^{1/k}(x)$ for suitable domains for you to explore. There are, of course, a plethora of solution-seeking texts on the subject, like C Efthimiou's Introduction to Functional Equations, AMS 2011, ISBN: 978-0-8218-5314-6 , online. A conjugacy iteration approximation method is available in our 2011 paper: Approximate solutions of Functional equations.

| cite | improve this answer | |
  • $\begingroup$ Not sure that you present Schroeder's example at the end in an optimal way, anecdotally because you seem to use the notation $f$ for another object than the OP, and mainly because your function $\psi$ is not defined unambiguously. Remember that the OP asks for some function $f:\mathbb C\to\mathbb C$ such that $f(f(z))=p(z)$ for every $z$ in $\mathbb C$, where $p:\mathbb C\to\mathbb C$ denotes the polynomial $p(z)=z^2-2$. Schroeder's approach (and everybody's approach after him) starts with the remark that, for every $z\ne0$, $$p(z+z^{-1})=z^2+z^{-2}$$ Thus, if one can find some ... $\endgroup$ – Did Jul 25 '18 at 18:41
  • $\begingroup$ ... function $\psi:\mathbb C\to\mathbb C^*$ such that, for every $z$ in $\mathbb C$, $$z=\psi(z)+\psi(z)^{-1}\tag{1}$$ then the function $f$ defined formally by $$f(z)=\psi(z)^{\sqrt2}+\psi(z)^{-\sqrt2}$$ is a solution. Now, this approach obviously meets some serious problems that must be solved before one can consider that it addresses the question, such as the fact that, for every complex number $z$ not in the subset $[2,+\infty)$ of the real line, no solution $\psi(z)$ of the identity $(1)$ is real and nonnegative hence, one must explain how one should define $\psi(z)^\sqrt2$, ... $\endgroup$ – Did Jul 25 '18 at 18:41
  • $\begingroup$ ... since $\sqrt2$ is not an integer. These aspects of the problem surely can be straightened out, but such a work is not done in your answer. $\endgroup$ – Did Jul 25 '18 at 18:42
  • $\begingroup$ "I'm not sure what you are objecting to" ?? Did you read my comments? $\endgroup$ – Did Jul 25 '18 at 18:59
  • $\begingroup$ I mean, in routine physics applications, one restricts to real fields and avoids juicy definitional ambiguities of plain powers, the case for $\psi^{1/k}$... $\endgroup$ – Cosmas Zachos Jul 25 '18 at 19:00

I will discuss quadratic $p(x)$, although the general method applies to $p(x)$ with an attractive fixed point. First consider $p(x)=x(a-x)$, with $|a|<1$, then there is an attractive fixed point at $0$. We look for a function $H(x)$ such that equation 1 is obeyed:

$H(p(x))=aH(x)$. ( 1)

We can then put Equation 2:

$p^n(x)=H^{-1} (a^nH(x))$. ( 2)

It is straightforward to expand $H(x)$ as a power series $H(x)= x+x^2/(a(a-1)+...$, but the higher order terms are relatively complex rational functions of a.

One can compute $H(x)$ by computing $y=p^n(x)$ with $n$ sufficiently large that the power series is accurate for $H(y)$ then put $H(x)=a^{-n}H(y)$.

I did numerical experiments for $a=1/2$, and the taylor series for $H(x)$ out to order 10. Equation 1 was obeyed to high accuracy, $H(x)$ appears smooth on its domain, which is the basin of the 0 attractor. $H(x)$ is singular on the boundary of its domain, the Julia set, and I don't think it can be continued beyond there.

$H(x)=0$ for all 0's of $p^n(x)=0$ and any integer $n$. It appears to be analytic on its domain. Equation 2 allows us to differentiate with respect to n and create a continuous flow map in the complex plane. I have not had time to study the inverse map. Clearly it must be multiple valued, but I believe it has regions where single valued definitions exist. In particular, for $p^n(x)=H^{-1} (a^nH(x))$ and $n$ small, we can use $x$ as the starting point of an iterative method to find $H^{-1} (a^nH(x))$.

The function $x^2+c$ has a quadratic fixed point at $\infty$. In this case we transform the mapping to $q(x)=x^2/(1+cx^2)$ and develop a power series about $0$. Because the fixed point is quadratic the functional equation is different. I have not studied this case much yet.

| cite | improve this answer | |

Similar to tippy2tina's answer, one can easily numerically generate such functions on $\mathbb R$ when they converge monotonically to a fixed-point if a fixed-point exists. Let $f^k(x)=\operatorname{nest}(f,x,k)$. In this case consider for $c\le-1/4$:


where the inverse, $q$, has $q^n(x)\to\beta=\frac{1+\sqrt{1-4c}}2$ monotonically and


describing its rate of convergence


which implies we can have


and thus we may define


In your case, you desire to find


which will converge to a real solution over $[a,\infty)$ for some $a\le0$. Note that $p$ has two inverses, so only a part of the solution is accounted for, while the other part cannot be real due to issues described in the linked posts.

Graphically for solving in the case of $c=-3.6$ and $k=3:$

enter image description here

| cite | improve this answer | |

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.