Putnam 2008, Problem A-5

Let $n \geq 3$ be an integer. Let $f(x)$ and $g(x)$ be polynomials with real coefficients such that the points $(f(1), g(1)), (f(2), g(2)), \ldots, (f(n), g(n))$ in $\mathbb{R}^2$ are the vertices of a regular $n$-gon in counterclockwise order. Prove that at least one of $f(x)$ and $g(x)$ has degree greater than or equal to $n-1$.

Solution:
Form the polynomial $P(z) = f(z) + ig(z)$ with complex coefficients. It suffices to prove that $P$ has degree at least $n-1$, as then one of $f,g$ must have degree at least $n-1$.

By replacing $P(z)$ with $aP(z) + b$ for suitable $a,b \in \mathbb{C}$, we can force the regular $n$-gon to have vertices $\zeta_n, \zeta_n^2, \ldots, \zeta_n^n$ for $\zeta_n = \exp(2\pi i/n)$. It thus suffices to check that there cannot exist a polynomial $P(z)$ of degree at most $n-2$ such that $P(i) = \zeta_n^i$ for $i = 1, \ldots, n$.

We will prove more generally that for any complex number $t \notin \{0,1\}$, and any integer $m \geq 1$, any polynomial $Q(z)$ for which $Q(i) = t^i$ for $i = 1, \ldots, m$ has degree at least $m-1$. There are several ways to do this.

**First solution:** If $Q(z)$ has degree $d$ and leading coefficient $c$, then $R(z) = Q(z+1) - tQ(z)$ has degree $d$ and leading coefficient $(1-t)c$. However, by hypothesis, $R(z)$ has the distinct roots $1,2,\ldots,m-1$, so we must have $d \geq m-1$.

**Second solution:** We proceed by induction on $m$. For the base case $m = 1$, we have $Q(1) = t^1 \neq 0$, so $Q$ must be nonzero, and so its degree is at least $0$. Given the assertion for $m-1$, if $Q(i) = t^i$ for $i = 1, \ldots, m$, then the polynomial $R(z) = (t-1)^{-1}(Q(z+1) - Q(z))$ has degree one less than that of $Q$, and satisfies $R(i) = t^i$ for $i = 1, \ldots, m-1$. Since $R$ must have degree at least $m-2$ by the induction hypothesis, $Q$ must have degree at least $m-1$.

**Third solution:** We use the method of finite differences (as in the second solution) but without induction.

Namely, the $(m-1)$-st finite difference of $P$ evaluated at $1$ equals
$$\sum_{j=0}^{m-1} (-1)^j \binom{m-1}{j} Q(m-j) = t(1-t)^{m-1} \neq 0,$$
which is impossible if $Q$ has degree less than $m-1$.

**Remark:** One can also establish the claim by computing a Vandermonde-type determinant, or by using the Lagrange interpolation formula to compute the leading coefficient of $Q$.