38
$\begingroup$

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.

$\endgroup$
12
  • 2
    $\begingroup$ 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. $\endgroup$ May 3, 2018 at 10:31
  • $\begingroup$ Possibly related to the following MO problem: mathoverflow.net/questions/296465 In any case, the $k(n-k)$ exponent appears there, too. $\endgroup$ May 3, 2018 at 11:12
  • 6
    $\begingroup$ Where does the question come from? Why do you believe this to be true? $\endgroup$
    – Igor Rivin
    May 3, 2018 at 12:19
  • 1
    $\begingroup$ 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 $\endgroup$
    – Igor Rivin
    May 3, 2018 at 15:08
  • 2
    $\begingroup$ 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/…. $\endgroup$ May 11, 2018 at 13:26

4 Answers 4

55
+25
$\begingroup$

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\}$.)

$\endgroup$
1
  • 9
    $\begingroup$ Amazing!! it seems that this theorem tie moon to the earth... $\endgroup$
    – Shahrooz
    May 7, 2018 at 6:00
31
$\begingroup$

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$.

$\endgroup$
4
  • 2
    $\begingroup$ Could you please elaborate on why $F_t$ can lose zeroes but never gain them ? I am not familiar with the heat equation. $\endgroup$ May 7, 2018 at 12:46
  • 1
    $\begingroup$ 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. $\endgroup$ May 7, 2018 at 23:28
  • 7
    $\begingroup$ 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 $\endgroup$
    – Ian Agol
    May 8, 2018 at 2:35
  • 1
    $\begingroup$ [correction to my previous comment: heat diffusion would increase $F_t(u_0)$, not $F''_t(u_0)$.] $\endgroup$ May 8, 2018 at 4:22
22
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Very nice indeed! $\endgroup$
    – Lucia
    May 9, 2018 at 16:45
  • 3
    $\begingroup$ 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!) $\endgroup$ May 9, 2018 at 16:49
  • $\begingroup$ 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$. $\endgroup$ May 9, 2018 at 17:23
  • $\begingroup$ 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. $\endgroup$
    – Ian Agol
    May 10, 2018 at 4:47
  • 1
    $\begingroup$ For the record: a related paper about Grace's theorem $\endgroup$
    – Wolfgang
    May 11, 2018 at 9:51
19
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Sorry, what does this have to do with the problem? $\endgroup$
    – Lucia
    May 9, 2018 at 13:38
  • 5
    $\begingroup$ 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. $\endgroup$ May 9, 2018 at 13:51
  • 5
    $\begingroup$ You were right! $\endgroup$
    – Lucia
    May 9, 2018 at 16:46
  • $\begingroup$ Very interesting approach, which provides moreover a kind of converse to a special case of the Gauss-Lucas theorem! $\endgroup$
    – Wolfgang
    May 11, 2018 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.