A cool problem about function composition

(David here.) It's been a while since the last blog post, so I thought I'd share a problem that I found interesting recently.

(Moscow 2003, 10.6) Let $P_1, P_2, P_3, ...$, be a sequence of real polynomials. Does there always exist a finite set of functions $f_1, f_2, ..., f_N$ such that each polynomial can be expressed as a composition of such functions? (For instance, $P_1(x) = f_1(f_3(f_1(x)))$ and so on.)

Why did this problem stand out to me? From the statistics, out of 678 participants there was only 1 correct solution, and it was given a special grade (marked with +!, compared to the usual + for "correct"). The problem statement also felt very conceptual and clean.

My attempt

My immediate thought was that even the constant case seemed nontrivial - maybe we could try having just a sequence of constant functions $p_1, p_2, ...$?

One idea (abusing the notation for $p_1$ to refer to the output value) is to think about functions as a directed graph. So a natural thing to consider is to string these constants up in a line: $$\newcommand{\redto}{{\ \color{red} \to\ }} \newcommand{\blueto}{{\ \color{blue} \to\ }} p_1 \redto p_2 \blueto p_3 \redto p_4 \blueto \cdots$$

If the $\{p_i\}$'s are distinct (which we can assume), then the red and blue arrows never share startpoints, so each can be a function (which we call $\color{red} f$ and $\color{blue} g$). Thus, we can make any constant function $p_i$ by first sending $x$ to $p_1$, and alternately applying $f$ and $g$ to get $p_k$.

What about the general case? Let's think about linear functions (so instead of $p_1$, we have $P_1(x) = p_1x$). Maybe it's not too crazy to think that we have such a chain per $x$? But the issue is that maybe between chains we could have collisions (e.g. $p_1 x_1 = p_2 x_2$) so we wouldn't have consistent function definitions.

The real trick is to think about the pair $(x, p_i)$, which are guaranteed to be distinct, and what we need is a bijection between $\mathbb R^2$ and $\mathbb R$ (which exist!). So instead, we have $f$ and $g$ defined by $$(x, p_1) \redto (x, p_2) \blueto (x, p_3) \redto (x, p_4) \blueto \cdots \qquad \text{for each }x$$ and an evaluation map $(x, p) \mapsto px$.

It's not hard to extend this to general polynomials, where you have $x$ and some sequence of coefficients that are eventually 0.

Teaser: if we had functions instead of polynomials, would we still be able to do this?

The official solution

So what solution deserves a special prize? The idea is that the function $\tan(x)$ is a bijection from $(-\pi/2, \pi/2)$ to $\mathbb R$. So, we are able to compress the information of $P_i$ onto (say) $((i-1/2)\pi, (i+1/2)\pi)$, then we can have a single function $h$ that captures all of this information.

What's left to do is then to encode the input using $\tan^{-1}$, shift it suitably many times using $s(x) = x+\pi$, and call $h$ on it.