# A family of polynomials whose zeros all lie on the unit circle

I had posted the following problem on stack exchange before.

Suppose $\lambda$ is a real number in $\left( 0,1\right)$, and let $n$ be a positive integer. Prove that all the roots of the polynomial $$f\left ( x \right )=\sum_{k=0}^{n}\binom{n}{k}\lambda^{k\left ( n-k \right )}x^{k}$$ have modulus $1$.

I do not seem to know how to do it, to show if the roots of the polynomial have modulus one. Putnam 2014 B4 Show that for each positive integer $n,$ all the roots of the polynomial $\sum_{k=0}^n 2^{k(n-k)}x^k$ are real numbers. This problem is very similar to the Putnam problem.

• One key observation is that the polynomial is palindromic, and with real coefficients, that is, $x^nf(1/x) = f(x)$. Thus, apriori, roots come in quadruplets, $z$, $1/z$ and their conjugates. Somehow, the binomial coefficients forces all such quadruplets to "degenerate" and essentially be roots paired with their inverse-conjugate. – Per Alexandersson May 3 '18 at 10:31
• Possibly related to the following MO problem: mathoverflow.net/questions/296465 In any case, the $k(n-k)$ exponent appears there, too. – Joe Silverman May 3 '18 at 11:12
• Where does the question come from? Why do you believe this to be true? – Igor Rivin May 3 '18 at 12:19
• I am not sure what the intended solution of the Putnam problem is, but I assume that this follows from the fact that the coefficient sequence of your second polynomial is log concave. This, of course, is false of the first polynomial, however, I believe the argument should go as follows: 1. Your polynomial is palindromic, so $f(x) = g(x+1/x)$ for some polynomial $g$ (with real coefficients. Such a polynomial can be obtained by simple linear algebra, or by using a basis of Chebyshev polynomials. 2. The coefficient sequence of $g$ should be log concave, so all of its roots should be real, so all – Igor Rivin May 3 '18 at 15:08
• The result follows immediately from the Lee-Yang Circle Theorem. See for instance Theorem 17.5 of homes.cs.washington.edu/~shayan/courses/cse599-s/…. – Richard Stanley May 11 '18 at 13:26

## 4 Answers

This is a special case of the Lee-Yang theorem. Let $G$ be a finite graph with vertex set $V$ and edge set $E$. Let $\beta \in (0,1)$ be a real number. Let $\sigma$ denote a spin function" $\sigma: V \to \{ -1, 1\}$. Put $m(\sigma)$ to be the number of vertices with positive spin, and $d(\sigma)$ to be the number of edges with vertices of opposite spin. Form the polynomial $$Z_\beta(x) = \sum_{\sigma} \beta^{d(\sigma)} x^{m(\sigma)},$$ where the sum is over all possible choices of the spins $\sigma$. The Lee-Yang theorem then states that all the zeros of $Z_{\beta}(x)$ lie on the unit circle. Amazing!

Apply the Lee-Yang theorem to the complete graph on $n$ vertices. The polynomial $Z_{\beta}(x)$ in this case is exactly $\sum_{k=0}^{n} \binom{n}{k} \beta^{k(n-k)} x^k$, and so this polynomial has all its roots on the unit circle.

For a discussion of the Lee-Yang theorem see these notes from a course by Nikhil Srivastava. The original Lee-Yang paper can be found here (behind a paywall). For more work on the Lee-Yang theorem (among other things), see Borcea and Branden. In particular, Theorem 8.4 there states the following more general form of the Lee-Yang theorem: Let $A=(a_{ij})$ be a Hermitian $n\times n$ matrix with all entries inside the closed unit disc. Then the polynomial $$f(z) = \sum_{S\subset [n]} z^{|S|} \prod_{\substack{i\in S \\ j\not\in S}} a_{ij}$$ has all its zeros on the unit circle. (Here $S$ runs over all subsets of $[n]=\{1, \ldots, n\}$.)

• Amazing!! it seems that this theorem tie moon to the earth... – Shahrooz Janbaz May 7 '18 at 6:00

The claim is true for $\lambda = 0$, when $f(x) = x^n + 1$, and for $\lambda = 1$, when $f(x) = (x+1)^n$. We show that this implies the claim for all intermediate $\lambda$, by proving that the number of zeros on the unit circle is a non-decreasing function of $\lambda$.

Let $\lambda = e^t$ with $-\infty < t < 0$, and $x = e^{iu}$ with $u \in {\bf R} \bmod 2\pi {\bf Z}$. Then $$f(x) = \exp\bigl[t\bigl(\frac{n}2\bigr)^2 + i\bigl(\frac{n}2\bigr)u\bigr] \cdot F_t(u),$$ where $$F_t(u) = \sum_{k=0}^n {n \choose k} \exp\bigl[-t\bigl(k-\frac{n}{2}\bigr)^2 + i\bigl(k-\frac{n}{2}\bigr)u\bigr]$$ is a real-valued function (the $k$ and $n-k$ terms are complex conjugates, a symmetry already noted in the comments) and $F_t(u+2\pi) = (-1)^n F_t(u)$ for all $u,t$. Now the key observation is that $F$ satisfies the heat equation $$\frac{\partial}{\partial t} F_t(u) = \sum_{k=0}^n -\frac{(2k-n)^2}{4} {n \choose k} \exp\bigl[-t\bigl(k-\frac{n}{2}\bigr)^2 + i\bigl(k-\frac{n}{2}\bigr)u\bigr] = \frac{\partial^2}{\partial^2 \! u} F_t(u).$$ Thus as $t$ increases the periodic function $F_t(u)$ can lose zeros (as when two zeros merge and then split into the complex plane) but never gain them. Since $F_t$ has $n$ zeros in ${\bf R} / 2\pi {\bf Z}$ for $t<0$ of sufficiently large $|t|$, while $F_0$ still has an $n$-fold zero at $u = \pi$, it follows that $F_t$ must still have $n$ zeros for all $t<0$ as well.

Added later: Much the same argument proves that for $\lambda>1$ the polynomial has all roots on the negative real axis. Here we write $x = e^u$, $\lambda = e^{-t}$, and $f(x) = \exp[-t(n/2)^2+(n/2)u] G_t(u)$, and again check that $G_t(u)$ satisfies the heat equation because it is a linear combination of heat-equation solutions $\exp(tm^2+mu)$ with $m = k-\frac{n}{2}$. For large $\lambda$ there are $n$ real roots because $f$ changes sign near the negative root of $${n \choose k-1} \lambda^{(k-1)(n-k+1)} x^{k-1} + {n \choose k} \lambda^{k(n-k)} x^k$$ for each $k=1,\ldots,n$. For $\lambda = 1$ there is still an $n$-fold root at $x=-1$, and of course there are no nonnegative roots for any $\lambda$. Hence $f$ has $n$ negative real roots for all $\lambda > 1$.

• Could you please elaborate on why $F_t$ can lose zeroes but never gain them ? I am not familiar with the heat equation. – Ewan Delanoy May 7 '18 at 12:46
• Good question. It will be a few days before I can look for a reference (maybe somebody else here can supply one), but the intuition is that the heat equation describes the diffusion of heat as a function of time $t$, from which "no new zeros" follows. For example, if a zero appeared in the interior of an interval on which $F$ was positive before, then a local minimum $F(u_0)$ became even smaller $-$ but the differential equation says its time derivative was $F''_t(u)$ which is positive near a local minimum, so heat diffusion would increase $F''_t(u_0)$, not decrease it. – Noam D. Elkies May 7 '18 at 23:28
• The non-increase of the number of zeroes seems to be a result of Sturm: link.springer.com/content/pdf/10.1007/3-7643-7359-8_8.pdf – Ian Agol May 8 '18 at 2:35
• [correction to my previous comment: heat diffusion would increase $F_t(u_0)$, not $F''_t(u_0)$.] – Noam D. Elkies May 8 '18 at 4:22

This follows from Julienne's answer. Fix $\lambda \in (0,1)$ and let $$f_n(x) = \sum_{k=0}^n {n \choose k} \lambda^{k(n-k)}x ^k.$$ Each $f_n$ satisfies condition (a) for $\mu = 1$. As for (b), we can compute the derivative of $f_n$ to get $$f_n ' (x) = n \lambda^{n-1} f_{n-1} \left(\frac{x}{\lambda}\right).$$ Now use induction on $n$: for $n=1$ we have $f_1(x) = 1+x$, so $x=-1$ is its only root. If $f_{n-1}$ has all roots on the unit circle, then all roots $x_0$ of $f_n'$ satisfy $$n\lambda^{n-1}f_{n-1}\left( \frac{x_0}{\lambda}\right)=0$$ and so $x_0=\lambda z_0$ for some $z_0$ on the unit circle, by the induction hypothesis. Hence, as $\lambda \in (0,1)$, $x_0$ lies inside the unit circle. By induction on $n$, (b) holds for all $f_n$ and so the result follows from Cohn.

(Sorry for not leaving this as a comment to Julienne's answer, I do not have enough reputation to comment.)

Edit: corrected formula for $f_n'$ thanks to Ian Agol's correction.

• Very nice indeed! – Lucia May 9 '18 at 16:45
• That is nice. I'll also mention that if you write the polynomial as $f_n(x,\lambda)$ and differentiate with respect to $\lambda$, then there should be some sort of recursion relating $df_n/d\lambda$ to $f_{n-2}$. See my answer to mathoverflow.net/questions/296465 for the case that $x=-1$, but the general case should be the same. (But note that $\lambda$ in this problem is $x$ in the other problem!) – Joe Silverman May 9 '18 at 16:49
• Neat. The observation relating $f'_n(x)$ to $f_{n-1}(x_0/\lambda)$ should also give an easier route to the result that the roots are all real for $\lambda>1$. – Noam D. Elkies May 9 '18 at 17:23
• There seems to be a typo, I found $f_n'(x)=n\lambda^{n-1}f_{n-1}(x/\lambda)$, which of course doesn't affect the answer. – Ian Agol May 10 '18 at 4:47
• For the record: a related paper about Grace's theorem – Wolfgang May 11 '18 at 9:51

In [Uber die Anzahl der Wurzeln einer algebraischen Gleichung in einem Kreise, Math. Z., 14, 1922, 110-148], A. Cohn established the following result:

Let $p_n(z) = \sum_{k=0}^n a_k z^k$ be a polynomial of degree $n$ with complex coefficient, then all zeros of $p_n(z)$ lie on the unit circle if and only if $p_n(z)$ satisfies

(a) $a_{n-k} = \mu \bar{a}_k$, $0 \leq k \leq n$, $|\mu| = 1$;

(b) all the zeros of $p'_n(z)$ lie in or on the unit circle.

Edit You can find a lot of papers dealing with the same type of problem in the literature and such kind of polynomials are called self-reciprocal polynomials.

• Sorry, what does this have to do with the problem? – Lucia May 9 '18 at 13:38
• I am not sure, but, OP said that he doesn't know how to prove the given problem. So I quoted Cohn's theorem which provides a good idea on how to approach the original problem. – Julienne Franz May 9 '18 at 13:51
• You were right! – Lucia May 9 '18 at 16:46
• Very interesting approach, which provides moreover a kind of converse to a special case of the Gauss-Lucas theorem! – Wolfgang May 11 '18 at 9:33