Saturday, May 12, 2018

A theorem of Lee—Yang on root of polynomials

A recent MathOverflow post asked for a proof that the roots of certain polynomials were located on the unit circle. A comment by Richard Stanley pointed to a beautiful theorem of T. D. Lee and C. N. Yang. By the way, these two authors were physicists, got the Nobel prize in physics in 1957, and were the first Chinese scientists to be honored by the Nobel prize.

This theorem appears in an appendix to their paper, Statistical Theory of Equations of State and Phase Transitions.IL Lattice Gas and Ising Model, published in Phys. Review in 1952, and devoted to properties of the partition function of some lattice gases. Here is a discussion of this theorem, following both the initial paper and notes by Shayan Oveis Gharan.

Let A=(ai,j)1i,jnA=(a_{i,j})_{1\leq i,j\leq n} be a Hermitian matrix (ai,j=aj,ia_{i,j}=\overline{a_{j,i}} for all i,ji,j). Define a polynomial
F(T)=S{1,,n}iSj∉Sai,jT#S. F(T) = \sum_{S\subset\{1,\dots,n\}} \prod_{\substack{i\in S \\ j\not\in S}} a_{i,j} T^{\# S}.

Theorem 1 (Lee-Yang). — If ai,j1\lvert a_{i,j}\rvert\leq 1 for all i,ji,j, then all roots of FF have absolute value 11.

This theorem follows from a multivariate result. Let us define
P(T1,,Tn)=S{1,,n}iSj∉Sai,jiSTi. P(T_1,\dots,T_n) = \sum_{S\subset\{1,\dots,n\}} \prod_{\substack{i\in S \\ j\not\in S}} a_{i,j} \prod_{i\in S} T_i .
Say that a polynomial FC[T1,,Tn]F\in\mathbf C[T_1,\dots,T_n] is good if it has no root (z1,,zn)Cn(z_1,\dots,z_n)\in\mathbf C^n such that zi<1\lvert z_i\rvert <1 for all ii.

Proposition 2 (Lee-Yang). — If ai,j1\lvert a_{i,j}\rvert\leq 1 for all i,ji,j, then PP is good.

For every pair (i,j)(i,j), set ai,jS=ai,ja^S_{i,j}=a_{i,j} if ii belongs to SS, but not jj, and set ai,jS=1a^S_{i,j}=1 otherwise. Consequently,
P(T1,,Tn)=S{1,,n}i,jai,jSkSTk. P(T_1,\dots,T_n) = \sum_{S\subset\{1,\dots,n\}}\prod_{i,j} a^S_{i,j} \prod_{k\in S} T_k.
In other words, if we define polynomials
Pi,j(T1,,Tn)=S{1,,n}ai,jSkSTk, P_{i,j} (T_1,\dots,T_n) = \sum_{S\subset\{1,\dots,n\}} a^S_{i,j} \prod_{k\in S} T_k,
then PP is the “coefficientwise product” of the polynomials Pi,jP_{i,j}.
We also note that these polynomials have degree at most one with respect to every variable. These observations may motivate the following lemmas concerning good polynomials.

Lemma 1. — If P,QP,Q are good, then so is their product.

Lemma 2. — If P(T1,,Tn)P(T_1,\dots,T_n) is good, then P(a,T2,,Tn)P(a,T_2,\dots,T_n) is good for every aCa\in\mathbf C such that a1\lvert a\rvert \leq 1.

This is obvious if a<1\lvert a\rvert <1; in the general case, this follows from the Rouché theorem — the set polynomials (of bounded degree) whose roots belong to some closed subset is closed.

Lemma 3. — If a1\lvert a\rvert \leq 1, then 1+aT1+aT is good.

This is obvious.

Lemma 4. — If a1\lvert a\rvert\leq 1, then P=1+aT1+aˉT2+T1T2P=1+aT_1+\bar a T_2+ T_1T_2 is good.

If a=1\lvert a\rvert =1, then P=(1+aT1)(1+aˉT2)P=(1+aT_1)(1+\bar aT_2) is good, as the product of two good polynomials.
Now assume that a<1\lvert a\rvert <1. Let (z1,z2)(z_1,z_2) be a root of PP such that z1<1\lvert z_1\rvert<1. One has
z2=1+az1z1+aˉ. z_2 = - \frac{1+az_1}{z_1+\bar a}.
Since the Möbius transformation z(z+aˉ)/(1+az)z\mapsto (z+\bar a)/(1+a z) defines a bijection from the unit open disk to itself, one has z2>1\lvert z_2\rvert >1.

Lemma 5. — If P=a+bT1+cT2+dT1T2P=a+bT_1+cT_2+dT_1T_2 is good, then Q=a+dTQ=a+dT is good.

Assume otherwise, so that a<d\lvert a\rvert <\lvert d\rvert. By symmetry, we assume bc\lvert b\rvert\geq \lvert c\rvert. We write P(T1,T2)=(a+cT2)+(b+dT2)T1P (T_1,T_2) = (a+cT_2) + (b+dT_2) T_1.
Choose z2Cz_2\in\mathbf C such that dz2dz_2 and bb have the same argument; if, moreover z2z_2 is close enough to 11 and satisfies z2<1\lvert z_2\rvert <1, then
b+dz2=b+dz2>a+c>a+cz2. \lvert b+dz_2\rvert=\lvert b\rvert +\lvert dz_2\rvert > \lvert a\rvert+\lvert c\rvert>\lvert a+cz_2\rvert.
Consequently, the polynomial P(T1,z2)P(T_1,z_2) is not good; a contradiction.

Lemma 6. — If P,QP,Q are good polynomials of degree at most one in each variable, then so is their coefficientwise product.

We first treat the case of one variable: then P=a+bTP=a+bT and Q=a+bTQ=a'+b'T, so that their coefficientwise product is given by R=aa+bbTR=aa'+bb'T. By assumption ab\lvert a\rvert \geq \lvert b\rvert and a0a\neq 0;
similarly, ab\lvert a'\rvert \geq \lvert b'\rvert and a0a'\neq 0. Consequently, aa0aa'\neq0 and aabb\lvert aa'\rvert \geq \lvert bb'\rvert, which shows that RR is good.
We prove the result by induction on nn. For every subset SS of {1,,n1}\{1,\dots,n-1\}, let aSa_S and bSb_S be the coefficients of iSTi\prod_{i\in S}T_i and of iSTiTn\prod_{i\in S} T_i \cdot T_n in PP; define similarly cSc_S and dSd_Swith QQ. The coefficientwise product of PP and QQ is equal to
R=S(aScS+bSdSTn)iSTi. R= \sum_S (a_S c_S +b_S d_S T_n ) \prod_{i\in S} T_i .
Let zCz\in\mathbf C be such that z1\lvert z\rvert \leq 1, so that
P(T1,,Tn1,z)=S(aS+bSz)iSTi P(T_1,\dots,T_{n-1},z)= \sum _S (a_S+b_S z) \prod_{i\in S} T_i is good, by lemma 2. Similarly, for wCw\in\mathbf C such that w1\lvert w\rvert\leq 1, $Q(T_1,\dots,T_{n-1},w)
=\sum _S (c_S+d_S w) \prod_{i\in S} T_i$ is good. By induction, their coefficientwise product, given by
Rz,w=S(aS+bSz)(cS+dSw)iSTi R_{z,w} = \sum_S (a_S+b_S z)(c_S+d_S w) \prod_{i\in S} T_i
is good as well.
We now fix complex numbers z1,,zn1z_1,\dots,z_{n-1} of absolute value <1<1. By what precedes, the polynomial
\[ S(T,U) = (\sum_S a_S c_S z_S) + (\sum_S b_Sc_S z_S) T + (\sum_S a_S d_S z_S) U
+ (\sum_S b_S d_S z_S) TU \]
is good, where zS=iSziz_S=\prod_{i\in S}z_i. According to lemma 4, the polynomial
R(z1,,zn1,T)=(SaScSzS)+(SbSdSzS)T R(z_1,\dots,z_{n-1},T) = (\sum_S a_S c_S z_S) + (\sum_S b_S d_S z_S) T
is good. This proves that RR is good.

Proof of theorem 2. — We have already observed that the polynomial PP is the coefficientwise product of polynomials Pi,jP_{i,j}, each of them has degree at most one in each variable. On the other hand, one has
Pi,j=(1+ai,jTi+aj,iTj+TiTj)ki,j(1+Tk), P_{i,j} = (1+a_{i,j} T_i + a_{j,i} T_j + T_i T_j) \prod_{k\neq i,j} (1+T_k),
a product of good polynomials, so that Pi,jP_{i,j} is good. This proves that PP is good.

In fact, more is true. Indeed, one has
\[
\begin{align*} T_1\dots T_n P(1/T_1,\dots,1/T_n)
& = \sum_ S \prod_{\substack{i\in S \\ j\notin S}} a_{i,j} \prod_{i\notin S} T_i \\
& =P^*(T_1,\dots,T_n)
\end{align*}
\]
where PP^* is defined using the transpose matrix of AA. Consequently, PP has no root (z1,,zn)(z_1,\dots,z_n) with zi>1\lvert z_i\rvert >1 for every ii.

Proof of theorem 1. — Let zz be a root of PP. Since the polynomial PP is good, so is the one-variable polynomial F(T)=P(T,,T)F(T)=P(T,\dots,T). In particular, F(z)=0F(z)=0 implies z1\lvert z\rvert \geq 1. But the polynomial has a symmetry property, inherited by that of PP, namely TnF(1/T)=F(T) T^n F(1/T)=F^*(T), where FF^* is defined using the transpose matrix of AA. Consequently, F(1/z)=0F^*(1/z)=0 and 1/z1\lvert 1/z\rvert \geq 1. We thus have shown that z=1\lvert z\rvert=1.




2 comments :

  1. Nice! Thanks Antoine for this post

    ReplyDelete
  2. C'était un de mes oraux pour l'entrée à l'ENS ! Malheureusement j'avais été complètement incapable de le résoudre.

    ReplyDelete