Root, root, root your boat

The key fact is that the number of distinct complex roots of a polynomial $p$ is equal to the degree of $p$ minus the degree of gcd $(p',p)$ . (This is because a root that appears with multiplicity $k$ in $p$ appears with multiplicity $k-1$ in gcd $(p',p)$ .)

So if we are to minimize the number of distinct roots of $f(f(x))$ , we want to maximize the degree of the gcd of it and its derivative. Its derivative is $f'(f(x))f'(x),$ and note that since $f$ has no repeated roots, $f'$ and $f$ are relatively prime. So $f'(f(x)$ and $f(f(x))$ are relatively prime. So the gcd of $f(f(x))$ and its derivative reduces to gcd $(f(f(x)), f'(x))$ .

This gcd has degree at most deg $f'(x) = 2012$ , so the number of distinct zeroes is at least $2013^2-2012.$ To show that this lower bound is attained, we need to find an $f$ such that this gcd has degree $2012$ , that is, a polynomial $f$ such that $f'(x)$ divides $f(f(x))$ .

Take $a$ to be a complex number satisfying $a^{2012} = -1$ . Then let $f(x) = x^{2013} + a$ . Then an easy computation shows that $f(f(x))$ is divisible by $x^{2012}$ , which is a constant multiple of $f'(x)$ . Hence we are done.

Finally, $2013^2 - 2012 \equiv 13^2 - 12 \equiv \fbox{157}$ mod $1000$ .

If the distinct roots of $f(x) = 0$ are $\lambda_1,\ldots,\lambda_{2013}$ , then the set of roots of $f(f(x))=0$ is the set $R \; = \; \bigcup_{j=1}^{2013} R_j \; = \; \bigcup_{j=1}^{2013}\big\{x \in \mathbb{C} \big| f(x) = \lambda_j\big\}$ Certainly $R_i \cap R_j = \varnothing$ for $i \neq j$ , and so $|R| \; = \; \sum_{j=1}^{2013} |R_j|$ .

If $\mu \in R_j$ is a repeated root of the equation $f(x) = \lambda_j$ , then $f(x) - \lambda_j = (x-\mu)^ag(x)$ for some $a \ge 2$ and some polynomial $g(x)$ . But then $f'(x) = (x-\mu)^{a-1}h(x)$ for some polynomial $h(x)$ , and hence $\mu$ is an $(a-1)$ -fold repeated root of the polynomial $f'(x)$ , which has degree $2012$ . The effect of $\mu$ is to reduce the size of $|R_j|$ by $a-1$ . Thus $|R|$ is equal to $2013\times2013$ minus a reduction due to the effects of repeated roots in the sets $R_j$ . Each such repeated root contributes to this reduction by an amount equal to its multiplicity as a zero of $f'(x)$ . Thus the greatest possible theoretical reduction to $|R|$ that is due to repeated roots is $2012$ , the degree of $f'(x)$ . That would make the least theoretically possible size of $|R|$ to be $2013\times2013 - 2012 \; = \; 4050157$ It remains to show that this least theoretically possible size is achievable. If we define $\lambda = e^{\frac{i\pi}{2012}}$ , so that $\lambda^{2012} = -1$ , consider $f(x) = x^{2013} + \lambda$ . Certainly the zeros of $f(x)$ are the $2013$ distinct $2013$ th roots of $-\lambda$ . Since $\lambda^{2013}+\lambda = \lambda(\lambda^{2012}+1) = 0$ , $\lambda$ is one of these. But $0$ is a $2013$ -fold repeated root of $f(x) = \lambda$ .

In other words, it is possible to achieve this maximum possible reduction of $2012$ to the size of $|R|$ , and so the minimum possible size of $|R|$ is indeed $4050157$ .

If $S_a$ is the solution set of $f(x)=a$ , then the number of distinct (complex) roots of $f(f(x))$ is $\sum_{a\in S_0} |S_a|$ . (The $S_a$ sets are all distinct, since $f(x)$ cannot have two different values for the same $x$ .)

But if $x$ is a double [triple, quadruple, etc.] root of $f(x)=a$ , then it is a single [respectively double, triple, etc.] root of $f'(x)=0$ . That is to say,

$\sum_{a\in S_0} (2013- |S_a|) \le deg (f') = 2012$

so $\sum_{a\in S_0}|S_a| \ge 2013^2- 2012$ .

On the other hand, $f(x)=(x+2)^{2013}-1$ has no multiple roots, and it yields

$\sum_{a\in S_0}|S_a| = 2013*2012 + |S_{-1}| = 2013*2012 +1$

which is the same as $2013^2- 2012 =4050157$ , and the last three digits are $157$ .

Suppose $f(x)=a(x-a_1)\cdot...\cdot(x-a_{2013}).$ Then the roots of $f(f(x))$ are the roots of $f(x)-a_i,$ for $i=1,2,...,2013.$ Since for $i\neq j$ $a_i\neq a_j,$ so for a fixed $x$ $f(x)$ cannot equal $a_i$ and $a_j$ simultaneously. Thus, none of the roots of $f(x)-a_i$ is a root of $f(x)-a_j.$ The following lemma is useful for more than just this problem.

Lemma. If $x_0$ is a root of a polynomial $g,$ then its multiplicity in $g$ is exactly one bigger than its multiplicity in $g',$ the derivative of $g.$ (if $x_0$ is not a root of $g',$ then we say that its multiplicity in $g'$ is zero).

Proof. If the multiplicity of $x_0$ in $g$ is $k\geq 1,$ then $g(x)=(x-x_0)^k\cdot h(x),$ where $h(x_0)\neq 0.$ So $g'(x)=k(x-x_0)^{k-1}h(x)+(x-x_0)^{k}h'(x)=(x-x_0)^{k-1}\left( kh(x)+ (x-x_0)h'(x)\right)$ Note that $kh(x_0)+ (x_0-x_0)h'(x_0)=kh(x_0)\neq 0,$ so the lemma is proven.

For each $i,$ the total number of roots of $f(x)-a_i,$ if counted with multiplicity, is $2013,$ for a total of $2013^2$ roots of $f(f(x)).$ Since we count the roots once, we must subtract $k-1$ for each root $x_0$ of some $f(x)-a_i$ of multiplicity $k$ . By the above lemma, applied to $g(x)=f(x)-a_i,$ this number $k-1$ equals the multiplicity of $x_0$ in $g'(x).$ Note that for every $i$ $g'(x)=f'(x),$ so the sum of the numbers $(k-1)$ that we need to subtract, over all roots of $f(x)-a_i,$ is at most the degree of $f'(x),$ which equals $2012.$ Therefore, the total number of roots is at least $2013^2-2012.$ We will now construct an example of $f(x)$ that achieves this bound.

Consider $f(x)=x^{2013}+c,$ where $c$ is some complex number, such that $c^{2012}=-1.$ Clearly, all roots of $f$ are simple (by the Lemma above, or directly). Then $f(f(x))=(x^{2013}+c)^{2013}+c=\left(x^{2013^2}+...+2013x^{2013}c^{2012}+c^{2013}\right) +c$ Note that $c^{2013}+c=0,$ so $0$ is a root of $f(f(x))$ with multiplicity $2013.$ Therefore, the total number of roots of $f(f(x))$ , counted without multiplicity, is at most $2013^2-2012.$

Finally, the last three digits of $2013^2-2012$ are the same as $13^2-12=157.$