2

Suppose $f(x)$ is a function from $\mathbb{R} \rightarrow \mathbb{R}$ such that $f(f(x)) = f(x)^{2013}$. Show that there are infinitely many such functions, of which exactly four are polynomials.

I found a solution here. It goes as following (only the part relevant to this post):

If $f$ is a polynomial, then either $f$ is constant or $f$ is non-constant. In the first case, say $f(x) = c$, we get $c = c^{2013}$, so $c \in \{-1, 0, 1\}$. In the second case, the range of $f$ contains infinitely many values since $f$ is continuous, so by the identity theorem, $f(x) = x^{2013}$ is forced. Thus there are only four polynomials $f$ that work -- three constant polynomials and $f(x) = x^{2013}$.

My doubt is how exactly did they conclude $f(x) = x^{2013}$? How does the range of $f$ having infinitely many values force $f$ to be $x^{2013}$?

zaemon_23
  • 465
  • 1
    If $y$ is anything in the image of $f$, then $f(y) = y^{2013}$. – Daniel Schepler Oct 10 '23 at 21:49
  • 1
    The idea of this approach may be to apply https://en.wikipedia.org/wiki/Identity_theorem to the analytic functions $f(z)$ and $z^{2013}$, which the given information implies are equal on the set ${f(x): x \in \mathbb{R}}$. (You may note that the theorem on Wikipedia only kicks in when this set has an accumulation point in the domain, which is not guaranteed if you only know that the set is infinite. Depending on the form of the "identity theorem" being used, this may be a hole in the argument.) – leslie townes Oct 10 '23 at 21:50
  • 1
    @leslietownes The identity theorem also applies on polynomials: if $f$ and $g$ agree at infinitely many points, then that implies $f-g$ has infinitely many roots, so it must be the zero polynomial. – Daniel Schepler Oct 10 '23 at 21:51
  • @DanielSchepler Thanks. I have adjusted my comment accordingly (I have only heard the term "identity theorem" used for analytic functions, and per Google, it mostly seems to be used that way. I think this comment interaction may therefore be helpful to some readers.) – leslie townes Oct 10 '23 at 21:53
  • Not that important, but it's interesting that the provided answer only deals with half the question, to show that there are four polynomial solutions to the functional equation. The other part of the question is to show that there are infinitely many nonpolynomial solutions. – Zubin Mukerjee Oct 10 '23 at 22:17
  • @ZubinMukerjee That's because OP didn't quote the full answer. The missing part constructs solutions where $f(0) = 0, f(1) = 1$ and $f(x) = 1$ 0 or 1, which clearly satisfies the conditions. – Calvin Lin Oct 11 '23 at 03:22

1 Answers1

1

For any $y$ in the image of $f$, i.e. where there is an $x$ with $f(x)=y$, you have $f(y)=f(f(x))=f(x)^{2013}=y^{2013}$.

For an infinite number of solutions:

  • partition the reals into subsets using the equivalence relation $x_1 \equiv x_2$ when $x_1 = x_2^{2013^n}$ for some integer $n$, taking advantage of $x^{2013}$ being bijective, with one such set being for example $\{\ldots, \sqrt[2013]{2}, 2, 2^{2013}, 2^{2013^2}, \ldots\}$ and the three sets of fixed points $\{-1\}$, $\{0\}$, $\{1\}$ being others.

  • Now choose some (at least one, possibly all) of the partition sets to be subsets of the image of $f$, and their union to be the image of $f$. For elements $y$ in the image, use $f(y)=y^{2013}$ and thus $f(f(y))=f(y)^{2013}$.

  • For each other real $x$ not in the image, choose any $y$ from the image with $f(x)=y$ so $f(f(x))=f(y)=y^{2013} = f(x)^{2013}$.

Any of these possibilities will be a solution. There are an infinite number of sets from the equivalence relation partition, so an infinite number of choices of which to include or not in the image of $f$, and more choices of the $f(x)$ for those $x$ not in the image, so an infinite number of possible solutions.

The only polynomial solutions come either when you choose the image to be one of $\{-1\}$, $\{0\}$, $\{1\}$ or when you chose it to be the whole of $\mathbb R$, as in the continuity argument in the solution given. You have $f(y)=y^{2013}$ for all $y$ in the image, and so in that final case for all $y \in \mathbb R$.

Henry
  • 157,058
  • I am not quite convinced this is all the possibilities: I suspect you may be able to choose "half" a partition set (an $x_0$ and all $x_0^{2013^n}$ for non-negative integer $n$) to be in the image and the "other half" not if you wish. – Henry Oct 11 '23 at 00:03