Functional equation $f(px)+p=[f(x)]^2$

Let $p\in\mathbb{N}$ and $p>1$. Consider the functional equation $$f(px)+p=[f(x)]^2$$ I need to find all functions $f:\mathbb{R}\to\mathbb{R}$ that is continuous at $0$ and satisfies above functional equation for all $x\in\mathbb{R}$.

For $p=2$, it can be showed that there exists a solution, the function $f:\mathbb{R}\to\mathbb{R}$ defined by $f(x)=2\cos(\alpha x)$ where $\alpha\in\mathbb{R}\cup i\mathbb{R}$ is arbitrary.

How can we find solutions for $p>2$ ? It possible to prove the existence since there exists constant solutions.

Solution 1:

This is a complete answer and goes a long way to explaining why the answer to this question is much more difficult than initially made out to be. Basically, there are such functions, and not only that : you can characterize them as well. I'll be going into some difficult notation, but I hope it will sort itself out at the end. Nevertheless, the experiences I had while solving this exercise were quite rewarding in themself.

Let us tag the equation $$ [f(x)]^2 - p = f(px) \tag{*} $$ Solving $(*)$ for $f(x)$ gives $$ f(x) = \pm \sqrt{f(px)+p} \tag{**} $$

First, note that $f(0)$ must be defined as one of $\frac{1 \pm \sqrt{1+4p}}{2}$ by inserting $x=0$ in $(*)$ to get $f(0)^2 = f(0)+p$.

Consider , for a fixed $x$, the following question : if I FIX $f(x)$, for what other real $y$ is the value of $f(y)$ constrained by $(*)$?

Well, the answer is simple : $(*)$ determines the value of $f(px), f(p^2x), f(p^3x)$ and so on exactly, while it determines the values of $f(\frac xp), f(\frac x{p^2}),...$ up to a choice of $\pm$. By continuity, since the sequence $xp^{-m}$ goes to zero as $m \to \infty$, we know that $f(0)$ is determined as well. To write it succinctly, $S_x = \{0\} \cup \{xp^{k} : k \in \mathbb Z\}$ are the set of inputs which are constrained under the fixation of $f(x)$.

Note that $S_0= \{0\}$ : although the continuity at $0$ constraints values near zero (the $\epsilon-\delta$ constraint), we don't count this because it still leaves uncountably many choices.

Let us define a relation on $\mathbb R$, given by $x \sim y$ if there exists an integer $k$ such that $xp^k = y$. This is an equivalence relation, and note that the equivalence class of every $x \neq 0$ is $S_x \setminus \{0\}$. Let the set of equivalence classes under this relation be given by $S$. Let $\{x_i\}_{i \in I}$ be a set of representatives for $S$ i.e. a set such that for every $s \in S$ there is exactly one $i \in I$ with $x_i \in s$.

Claim : A set of representatives for $S$ is $T = (-p,-1] \cup [1,p) \cup \{0\}$.

Proof : Let $x \neq y\in T$. We claim that $x \not\sim y$. It is obvious that $x,y \neq 0$. Note that if $\frac xy = p^k$ for some $k$ , then $x,y$ must have the same sign. Suppose without loss of generality that $|x|>|y|$, then we know that $k>0$, so $|x| \geq p|y|$. Since $|y| \geq 1$ we must have $|x| \geq p$, a contradiction. Thus, $x \not \sim y$.

On the other hand, let $r$ be any real number. If $r=0$ then we are done, otherwise consider the double sequence $rp^{m}$. As $n \to \infty$, this goes to either $\pm \infty$ and as $m \to -\infty$ this goes to $0$. In particular, we know that the sequence definitely crosses $p$ in absolute value at some point. Suppose that $|rp^{m}| \geq p$ and $|rp^{m-1}|<p$. Then, note that $|rp^{m-1}| \geq 1$ and $|rp^{m-1}|< p$, so $rp^{m-1}$ is a representative of $r$ in $T$,and we are done.

We now define sign sequences. A sign sequence is a sequence with elements from $\pm 1$. So for example, a particular sign sequence is $+1,-1,+1,-1,+1,+1,-1,-1,-1,...$ and so on. A sign sequence will be denoted by $\mathcal S$, whose terms will be denoted by $s_i$, $i=1,2,3,...$. Now, we define a formal double-recurrence as follows : given a sign sequence $\mathcal S$, a $t \neq 0\in T$ and a $y \in \mathbb R$, the (double) recurrence $x^t : \mathbb Z \to \mathbb R$ given by $x^t(0) = y$ and $$ x^t(i+1) = x^t(i)^2-p \quad \forall i \geq 0 \\ x^t(i-1) = s_{|i-1|}\sqrt{x^t(i)+p} \quad \forall i \leq 0 $$

is called the double recurrence associated to $t$ and $\mathcal S$. We first talk about the solvability of the double recurrence.

Lemma : Fix a sign sequence $\mathcal S$ , a $t \in T$ with $t \neq 0$ and a $y \in \mathbb R$. Define $g(z) = z^2-p$, and the $n$-fold composition $g^n(z) = g(g(\ldots(g(z))))$ where the $g$ comes $n$ times. Let $i^*$ be the first occurrence of $-1$ i.e. we have $s_{i^*} = -1$ and $s_{j} = 1$ for all $0<j<i^*$. Then, the double recurrence corresponding to $t,\mathcal S , y$ is uniquely defined and takes real number values if and only if $-p \leq y \leq g^{i^*}(p)$. Furthermore, if $i^* = \infty$ (which is the case if the sign sequence is the constant $+$) then the double recurrence is defined if and only if $-p \leq y$.

For example, if the sign sequence is $+,-,+,-,-,+,...$ then the first occurrence of a $-$ is $i^* = 2$, so the recurrence has a solution if and only if $-p \leq y \leq g^2(p) = g(g(p)) = (p^2-p)^2 - p$.

Proof : Note that irrespective of $\mathcal S$ and $y$, we know that $x^t(i)$ are real for all $i \geq 0$. Therefore, we only need to look at $i<0$.

We start with the following claim.

Claim : Suppose that $|x^t(i)| \leq p$ for some $i \leq 0$. Then, $|x^t(i-1)| \leq p$.

Proof : We have that $|x^t(i-1)| = |\sqrt{x^t(i)+p}| \leq \sqrt{2p} \leq p$ for $p \geq 2$. $\blacksquare$

Let $i^*$ be the first occurence of a negative sign in $S$. If $i^* = \infty$, then we can easily see that $y \geq -p$ if and only if $x^t(-1)$ is well defined and non-negative, and from that point on, one easily argues by induction that $x^t(-i)$ are well defined and non-negative for all $i>0$. Now, we let $i^* < \infty$. Note that the above induction then holds till $i^*$ i.e. we have $x(-1),...,x(-i^*+1) \geq 0$.

Now let us consider the situation $s_{|i-1|} = -1$ for some $i$. Then, through a simple algebraic manipulation, we can see that $x^t(i-1)$ is well-defined, and $0 \geq x^t(i-1) \geq -p$, if and only if $-p \leq x^t(i) \leq p^2-p$. Therefore by induction and the claim, $p^2-p \geq p \geq x^t(j) \geq -p$ for all $j \leq i$ if and only if $x^t(i) \geq -p$. Thus, remembering the role of $i^*$, the sequence is well defined if and only if $-p \leq x^t(-i^*+1) \leq p^2-p$.

But now we use the increasing nature of the function $g$. Indeed, $x(-i^*+1) \leq p^2-p$ occurs if and only if $\sqrt{-x(i^*+2)+p} \leq p^2-p$ i.e. $x(-i^*+2) \leq (p^2-p)^2-p= g(g(p))$, and then by induction, this iterates all the way up to $y \leq g^{i^*}(p)$ via induction.

We used, in the above if and only ifs, the fact that $g$ is an increasing function (on its domain), but that finishes the lemma. $\blacksquare$.

Once the lemma is done, we are now ready to write down a general theorem that characterises all functions that satisfy the recurrence $(*)$ (but are not necessarily continuous at zero). I must admit that I profited from some very nice choice of functions in this process, hail Matthew Stuart Cash.

Theorem : For each $t \in T$ with $t\neq 0$, consider an arbitrary sign sequence $\mathcal S_t$, and a value $y_t$ such that if $i_t^*$ is the first occurrence of $-1$ in $\mathcal S_t$ then $y_t \leq g^{i_t^*}(p)$. Now, for any real number $x \neq 0$, write $x = tp^l$ where $t \in T$ and $l \in \mathbb Z$. Define a function $f$ as follows : $f(0) = \frac{1 \pm \sqrt{1+4p}}{2}$ and $f(x) = x^t(l)$ where $x^t$ is the double recurrence corresponding to $t , \mathcal S^t$ and $y_t$. Then, $f$ satisfies $(*)$. Furthermore, every $f$ that satisfies $(*)$ is uniquely determined by the $\mathcal S^t$ and $y_t$ for each $t$, along with $f(0)$.

Proof : It's clear that the $f$ above can be constructed, since the conditions on $y_i$ ensure that the double recurrence takes real values, and $(*)$ is satisfied at each step because the recurrence is satisfied at each step. Furthermore, if any $f$ satisfies $(*)$, then we've already seen that the double recurrence must be satisfied along each equivalence class, so the result is pretty straightforward. The fact that $f$ is determined from its values on $T$ and a corresponding sign sequence for each $t \in T$ is also obvious since $T$ is a set of representatives and by creating double recurrences starting from each $t \in T$ and the image $f(t)$, we can reconstruct $f$ completely. $\blacksquare$

Which sets up the second leg of this fascinating tie.

Now, we can discuss continuity at $0$. Before that, let's take a quick peek into what continuity at zero really means, and how it relates to the double sequences we've defined.

For a set $U \subset \mathbb R$ and a real number $r$, we will use the common notation $rU = \{ru: u \in U\}$. Now, continuity at zero is characterized by the behaviour of $f$ in arbitrarily small neighbourhoods of zero. In particular, if you recall one of the basics of topology, if we find a "local basis" of open sets at $0$ which can be expressed nicely in terms of $T$ (which is the set of inputs on which $f$ is being defined arbitrarily) then we could certainly work backwards from the local basis to $T$.

Here's what I mean : It's not difficult to see, that $\cup_{m=M}^{\infty} p^{-m}T = (-p^{-m+1} , p^{-m+1})$. Try to prove it yourself.

Now, as $m$ grows larger and larger, the intervals on the RHS shrink to the empty set, but each of them contains zero. In particular, this implies that the given intervals are the local basis that we are looking for.

Now, let's take the definition of continuity at zero, and modify it so that we are looking at the definition of continuity that we can directly use.

Usual definition : for all $\epsilon>0$, there is a $\delta>0$ such that $|f(x)-f(0)|<\epsilon$ is true for all $|x|<\delta$.

This is equivalent, by a typical local-base argument (or otherwise) to : for all $\epsilon>0$, there is an $m>0$ such that $|f(x)-f(0)|<\epsilon$ for all $|x|<p^{-m+1}$.

This is equivalent, by the beautiful union expression that we saw earlier, to : for all $\epsilon>0$, there is an $M>0$ such that $|x^t(-m)-f(0)|<\epsilon$ for all $m>M$ and $t \in T$.

Now then. Now. Then. We've got what we need, haven't we? A way to relate continuity to zero, to something occurring for all the double sequences together. Let's see how we can put this to use.

Let's write down our first lemma.

Suppose that $f$ is continuous at zero. Then

• There is an $M>0$ such that for all $t \in T$ and all $m>M$, $s^t_m$ has the same sign as $f(0)$.
• The set $\{f(t) : t \in T\}$ is a bounded set.

Proof : We need to make observations. First, note that $f(0) \neq 0$, so it's on either side of $0$. Using the equivalent definition with $\epsilon = \frac{|f(0)|}{2}$ tells us that after some large $M$, for all $t$, $x^t(-m)$ has the same sign as $f(0)$ for all $m > M$ and $t \in T$. Furthermore, $x^t(-m) \leq \frac{|3f(0)|}{2}$.

But then, looking at the definition, $x^t(-m)$ has the same sign as $s^t_m$! Therefore, the first statement follows. The second follows from the fact that $x^t(-M-1) \leq \frac{|3f(0)|}{2}$ so by the increasing nature of $g$, we have that $x^t(0) \leq g^{M+1}(\frac{|3f(0)|}{2})$ for all $t$, and the RHS is some bounded number, so the boundedness of $\{f(t) : t \in T\}$ follows. $\blacksquare$.

Now, the question is : how can we go the other way? Well, to prove continuity, we need to prove something about all the double-sequences together. This means, that we can't really do whatever we want with the initial values : not controlling these values will let the double sequences run haywire. The question is, what amount of control we want.

We do, though, have a huge upper hand. See, the necessary condition that all sign sequences , after some fixed(and independent of $t\in T$) point of time have to have the same sign, makes the problem much easier because we are in the iteration domain. Indeed, if the sign stays constant after some time, then you're basically only having to discuss the sign sequences $+,+,+,+,+,+,...$ and $-,-,-,-,-,...$ : anything that happens before this can be ignored in the context of convergence(as long as their well-definition is taken care of, which is important!).

Since we are in iteration domain, let's try to use the biggest iteration convergence weapon : the Banach fixed point theorem. We basically have two iterations in play : one is given by the function $h_+(x) = +\sqrt{x+p}$ and the other by $h_-(x) = -\sqrt{x+p}$. Let's find out the domains in which these are contractive functions. Obviously you need their derivative for that.

The derivative of $h_+(x)$ is $\frac{1}{2\sqrt{x+p}}$, and likewise that for $h_-$ is $\frac{-1}{2\sqrt{x+p}}$. The absolute value of both is the same. Solving : $$ \left|\frac{1}{2\sqrt{x+p}}\right| <1 \iff \sqrt{x+p} > \frac 12 \iff x > \frac 14 - p $$

and therefore, $h^+$ and $h^-$ are contractive on $(\frac 14 - p, +\infty)$. Useful information, because a partial converse (to be followed by the full converse) can now be sorted out:

Lemma : Suppose that there is a fixed $M$ such that for $m>M$ and $t \in T$, $f(0)$ and $s^t_m$ have the same sign. Suppose that $\{x^t(-M) : t \in T\}$ is a bounded set. Then, $f$ is continuous at zero.

Proof : Let's first consider the case that $f(0)>0$. In that case, $\{x^t(-M-1) : t \in T\}$ is a bounded set of non-negative numbers.

Let's modify one of the beautiful result that I state and prove here, in the middle of another long answer!. I'll state just a simpler version, you can easily see why it works out.

Let $X \subset R$ , and $f:X \to X$ be a (not necessarily continuous) function , such that $f$ is contractive on $X$, and furthermore $X$ is a bounded set. Suppose that $f$ has a unique fixed point $x^*$ (and this is an assumption, not a conclusion) in $X$. Then, the sequence of functions $f_n$ converge uniformly to the function $ g(x)=x^*$ for all $x \in X$.

This works out, because continuity is used only to prove that the fixed point exists, and contractivity does the rest of the heavy lifting. So let's use it.

Note that in this case, $h^+$ satisfies the following properties :

• $h^+$ is a map from $\{x^t(-n) : n >M, t \in T\}$ to $\{x^t(-n) : n > M, t \in T\}$, obviously. This set is bounded by the assumptions of the lemma.
• It has a unique fixed point in this region i.e. $f(0)$.
• It is contractive because $\{x^t(-n) : n >M, t \in T\} \subset [-\frac 14+p,\infty)$, I mean, it's a set of non-negative numbers!

Finally, we conclude using the theorem that $h_+$ iterated, converges uniformly on the given set to $f(0)$.

Now, let's see why $f$ is continuous at $0$. Pick an $\epsilon>0$. For this $\epsilon>0$, by uniform convergence of $h_+$ iterated, the following : there exists an $M'>0$ such that for all $t \in T$, and $n>m,m>M'$, $|h_+^{(m)}(x^t(-n))-f(0)|<\epsilon$. However, note that $h_+^{(m)}(x^t(-n)) = x^t(-n-m)$ because of our assumptions on the sign-sequence being constantly $+$! It follows that if $M'' = M'+M$, then $m>M''$ implies that $|x^t(-m) - f(0)| < \epsilon$ for all $t \in T$.

Done! So $f$ is continuous.

What about the negative case? Let's assume now that $f(0)<0$.

Here, we have to deal with the problem that containment within the contractive region is not immediate : what if $x^t(-m) = -p$ or something like that, right? This doesn't lie in the contractive region!! Well, we need not worry : just go some iterations further!

We already know that $\{x^t(-M-1) : t \in T\}$ will have to lie between $-p$ and $0$ for $t \in T$, by the claim we made way earlier before coming to continuity. Now, suppose that $x^t(-M-1)$ is between $p$ and $0$. Then, since $h_-$ is decreasing, $x^t(-M-2) = h_-(x^t(-M-1))$ is between $-\sqrt p$ and $0$. But, $-\sqrt p \geq \frac 14 - p$ for $p \geq 2$, as can be easily checked. Therefore, $x^t(-M-2)$ lies within the contractive region, and you can easily show the following now by induction : the entire set $\{x^t(-n) : n > M+2 , t \in T\}$ lies in the contractive set.

To again use the Banach lemma, note that :

• $h_-$ is a function from $\{x^t(-n) : n > M+2 , t \in T\}$ to $\{x^t(-n) : n > M+2 , t \in T\}$.
• It has a unique fixed point $f(0)$.
• It is contractive in this set.

Now, repeating pretty much the argument for the positive case analogously, gives us the lemma. $\blacksquare$

Let us now make a simple observation : for any $m$, $\{x^t(-m) : t \in T\}$ is bounded if and only if $\{y_t : t \in T\}$ is bounded. This is quite obvious from the bounds we've been deriving all the way. But the most important thing we've proved, if you put everything above together , is :

$f$ is continuous at zero if and only if:

• There is a fixed $M>0$ such that for all $t \in T$, $s^t_m$ has the same sign as $f(0)$ for $m>M$.
• $\{f(t) : t \in T\}$ is bounded.

Which, along with everything we've seen about $f$ so far, provides the following ultimate characterization theorem for functions satisfying $(*)$ which are continuous at zero.

Theorem: For each $t \in T$ with $t\neq 0$, consider a sign sequence $\mathcal S_t$, and a value $y_t$ such that

• If $i_t^*$ is the first occurrence of $-1$ in $\mathcal S_t$ then $y_t \leq g^{i_t^*}(p)$.
• There is an $M>0$ such that for all $t \in T$, $m>M$, $s^t_m$ all have the same sign, say $s \in \{\pm 1\}$.
• $\{y_t : t \in T\}$ is bounded.
  Now, for any real number $x \neq 0$, write $x = tp^l$ where $t \in T$ and $l \in \mathbb Z$. Define a function $f$ as follows : $f(0) = \frac{1 +s\sqrt{1+4p}}{2}$and $f(x) = x^t(l)$ where $x^t$ is the double recurrence corresponding to $t , \mathcal S^t$ and $y_t$. Then, $f$ satisfies $(*)$ and is continuous at zero. Furthermore, every $f$ that satisfies $(*)$ and is continuous at zero, is uniquely determined by an appropriate choice of $\mathcal S^t$ and $y_t$ for each $t$, along with $f(0)$.

which completes our investigation. I'll improvise this answer on the morrow, putting in the headings and summary, but I sincerely hope the content is clear!

Solution 2:

Some initial thoughts. Define $$g(t)=f(p^t)$$ Then $$f(p^{t+1})+p=f^2(p^t)$$ $$g(t+1)+p=g^2(t)$$ Then it looks as though we can choose arbitrary values for $g(t)$ in a unit range, say $[0,1)$, and this relationship will determine $g(t)$ for all other values of $t$.

What about the requirement that $f(x)$ is continuous at $0$? I think this just means that $g(t)$ is continuous at $-\infty$. But this happens automatically since $$g(t-1)=\sqrt{g(t)+p}$$ and as we step back in $t$ we always get that $\lim_{t \to -\infty}g(t) $ is the solution of $g^2=g+p$.

So I claim that we can choose arbitrary $g(t)$ on $[0,1)$ and this gives all possible solutions.

Equivalently, we choose arbitrary $f(x)$ on $[1,p)$ and then define all other values by the given relationship.