Content-Type: multipart/mixed; boundary="-------------0009200508626" This is a multi-part message in MIME format. ---------------0009200508626 Content-Type: text/plain; name="00-371.keywords" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="00-371.keywords" Grace's theorem, Grace-like polynomials, Lee-Yang zeros ---------------0009200508626 Content-Type: application/x-tex; name="grace.tex" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="grace.tex" \magnification=1200 \def\qed{\unskip\kern 6pt\penalty 500\raise -2pt\hbox {\vrule\vbox to 10pt{\hrule width 4pt\vfill\hrule}\vrule}} \centerline{GRACE-LIKE POLYNOMIALS.} \bigskip\bigskip \centerline{by David Ruelle\footnote{*}{IHES. 91440 Bures sur Yvette, France. $<$ruelle@ihes.fr$>$}.} \bigskip\bigskip\bigskip\bigskip\noindent {\leftskip=2cm\rightskip=2cm\sl Abstract. Results of somewhat mysterious nature are known on the location of zeros of certain polynomials associated with statistical mechanics (Lee-Yang circle theorem) and also with graph counting. In an attempt at clarifying the situation we introduce and discuss here a natural class of polynomials. Let $P(z_1,\ldots,z_m,w_1,\ldots,w_n)$ be separately of degree 1 in each of its $m+n$ arguments. We say that $P$ is a Grace-like polynomial if $P(z_1,\ldots,w_n)\ne0$ whenever there is a circle in ${\bf C}$ separating $z_1,\ldots,z_m$ from $w_1,\ldots,w_n$. A number of properties and characterizations of these polynomials are obtained.\par} \bigskip\bigskip\bigskip\bigskip\noindent \vfill\eject \bigskip\bigskip {\sl I had the luck to meet Steve Smale early in my scientific career, and I have read his 1967 article in the Bulletin of the AMS more times than any other scientific paper. It took me a while to realize that Steve had worked successively on a variety of subjects, of which ``differentiable dynamical systems'' was only one. Progressively also I came to appreciate his independence of mind, expressed in such revolutionary notions as that the beaches of Copacabana are a good place to do mathematics. Turning away from scientific nostalgy, I shall now discuss a problem which is not very close to Steve's work, but has relations to his interests in recent years: finding where zeros of polynomials are located in the complex plane.} \medskip {\bf 0 Introduction.} \medskip One form of the Lee-Yang circle theorem [3] states that if $|a_{ij}|\le1$ for $i,j=1,\ldots,n$, and $a_{ij}=a^*_{ji}$, the polynomial $$ \sum_{X\subset\{1,\ldots,n\}}z^{{\rm card}X} \prod_{i\in X}\prod_{j\notin X}a_{ij} $$ has all its zeros on the unit circle $\{z:|z|=1\}$. \medskip Let now $\Gamma$ be a finite graph. We denote by $\Gamma'$ the set of dimer subgraphs $\gamma$ (at most one edge of $\gamma$ meets any vertex of $\Gamma$), and by $\Gamma''$ the set of unbranched subgraphs $\gamma$ (no more than two edges of $\gamma$ meet any vertex of $\Gamma$). Writing $|\gamma|$ for the number of edges in $\gamma$, on proves that $$ \sum_{\gamma\in\Gamma'}z^{|\gamma|} $$ has all its zeros on the negative real axis (Heilmann-Lieb [2]) and $$ \sum_{\gamma\in\Gamma''}z^{|\gamma|} $$ has all its zeros in the left-hand half plane $\{z:{\rm Im}z<0\}$ (Ruelle [6]). \medskip The above results can all be obtained in a uniform manner by studying the zeros of polynomials $$ P(z_1,\ldots,z_n) $$ which are {\it multiaffine} (separately of degree $1$ in their $n$ variables), and then taking $z_1=\ldots=z_n=z$. The multiaffine polynomials corresponding to the three examples above are obtained by multiplying factors for which the location of zeros is known and performing {\it Asano contractions}: $$ Auv+Bu+Cv+D\qquad\rightarrow\qquad Az+D $$ The {\it key lemma} (see [5]) is that if $K$, $L$ are closed subsets of ${\bf C}\backslash\{0\}$ and if $$ u\notin K, v\notin L\qquad\Rightarrow\qquad Auv+Bu+Cv+D\ne0 $$ then $$ z\notin-K*L\qquad\Rightarrow\qquad Az+D\ne0 $$ where we have written $K*L=\{uv:u\in K,v\in L\}$. \medskip To get started, let $P(z_1,\ldots,z_n)$ be a multiaffine {\it symmetric} polynomial. If $W_1,\ldots,W_n$ are the roots of $P(z,\ldots,z)=0$, we have $$ P(z_1,\ldots,z_n)={\rm const.}\sum_\pi\prod_{j=1}^n(z_j-W_{\pi(j)}) $$ where the sum is over all permutations $\pi$ of $n$ objects. {\it Grace's theorem} asserts that if $Z_1,\ldots,Z_n$ are separated from $W_1,\ldots,W_n$ by a circle of the Riemann sphere, then $P(Z_1\ldots,Z_n)\ne0$. For example, if $a$ is real and $-1\le a\le1$, the roots of $z^2+2az+1$ are on the unit circle, and therefore $$ uv+au+av+1 $$ cannot vanish when $|u|<1$, $|v|<1$; from this one can get the Lee-Yang theorem. \medskip In view of the above, it is natural to consider multiaffine polynomials $$ P(z_1,\ldots,z_m,w_1,\ldots,w_n) $$ which cannot vanish when $z_1,\ldots,z_m$ are separated from $w_1,\ldots,w_n$ by a circle. We call these polynomials Grace-like, and the purpose of this note is to study and characterize them. \bigskip \centerline{\bf I. General theory.} \bigskip We say that a complex polynomial $P(z_1,z_2,\ldots)$ in the variables $z_1$, $z_2,\ldots$ is a Multi-Affine Polynomial ({\it MA-nomial} for short) if it is separately of degree 1 in $z_1$, $z_2,\ldots$. We say that a circle $\Gamma\subset{\bf C}$ {\it separates} the sets $A'$, $A''\subset{\bf C}$ if ${\bf C}\backslash\Gamma=C'\cup C''$, where $C'$, $C''$ are open, $C'\cap C''=\emptyset$ and $A'\subset C'$, $A''\subset C''$. We say that the MA-nomial $P(z_1,\ldots,z_m,w_1,\ldots,w_n)$ is Grace-like (or a G-nomial for short) if it satisfies the following condition \medskip (G) {\sl Whenever there is a circle $\Gamma$ separating $\{Z_1,\ldots,Z_m\}$, $\{W_1,\ldots,W_n\}$, then} $$ P(Z_1,\ldots,W_n)\ne0 $$ [Note that we call circle either a straight line $\Gamma\subset{\bf R}$ or a {\it proper circle} $\Gamma=\{z\in{\bf C}:|z-a|=R\}$ with $a\in{\bf C}$, $0n$, each monomial in $P$ would have a factor $z_i$, hence $$ P(0,\ldots,0,1,\ldots,1)=0 $$ in contradiction with the fact that $\{0,\ldots,0\}$, $\{1,\ldots,1\}$ are separated by a circle. Thus $k\le n$, and similarly $k\le m$.\qed \medskip {\bf 2 Lemma} (degree). \medskip {\sl If all the variables $z_1,\ldots,w_n$ effectively occur in the G-nomial $P$, then $m=n$ and $P$ has degree $k=n$.} \medskip By assumption $$ (\prod_{i=1}^mz_i)(\prod_{j=1}^nw_j)P(z_1^{-1},\ldots,w_n^{-1}) $$ is a homogeneous MA-nomial $\tilde P(z_1,\ldots,w_n)$ of degree $m+n-k$. If $Z_1,\ldots,W_n$ are all $\ne0$ and $\{Z_1,\ldots,Z_m\}$, $\{W_1,\ldots,W_n\}$ are separated by a circle $\Gamma$, we may assume that $\Gamma$ does not pass through $0$. Then $\{Z_1^{-1},\ldots,Z_m^{-1}\}$, $\{W_1^{-1},\ldots,W_n^{-1}\}$ are separated by $\Gamma^{-1}$, hence $\tilde P(Z_1,\ldots,W_n)\ne0$. Let ${\cal V}$ be the variety of zeros of $\tilde P$ and $$ {\cal Z}_i=\{(z_1,\ldots,w_n):z_i=0\}\qquad, \qquad{\cal W}_j=\{(z_1,\ldots,w_n):w_j=0\} $$ Then $$ {\cal V}\subset({\cal V}\backslash\cup_{i,j}({\cal Z}_i\cup{\cal W}_j)) \cup\cup_{i,j}({\cal Z}_i\cup{\cal W}_j) $$ Since all the variables $z_1,\ldots,w_n$ effectively occur in $P(z_1,\ldots,w_n)$, none of the hyperplanes ${\cal Z}_i$, ${\cal W}_j$ is contained in ${\cal V}$, and therefore $$ {\cal V}\subset \hbox{closure}({\cal V}\backslash\cup_{i,j}({\cal Z}_i\cup{\cal W}_j)) $$ We have seen that the points $(Z_1,\ldots,W_n)$ in ${\cal V}\backslash\cup_{i,j}({\cal Z}_i\cup{\cal W}_j)$ are such that $\{Z_1,\ldots,Z_m\}$, $\{W_1,\ldots,W_m\}$ cannot be separated by a circle $\Gamma$, and the same applies to their limits. Therefore $\tilde P$ again satisfies (G). Applying Lemma 1 to $P$ and $\tilde P$ we see that $k\le\min(m,n)$, $m+n-k\le\min(m,n)$. Therefore $m+n\le2\min(m,n)$, thus $m=n$, and also $k=n$.\qed \medskip {\bf 3 Proposition} (reduced G-nomials). \medskip {\sl If $P(z_1,\ldots,z_m,w_1,\ldots,w_n)$ is a G-nomial, then $P$ depends effectively on a subset of variables which may be relabelled $z_1,\ldots,z_k,w_1,\ldots,w_k$ so that $$ P(z_1,\ldots,z_m,w_1,\ldots,w_n) =\alpha R(z_1,\ldots,z_k,w_1,\ldots,w_k) $$ where $\alpha\ne0$, the G-nomial $R$ is homogeneous of degree $k$, and the coefficient of $z_1\cdots z_k$ in $R$ is 1.} \medskip This follows directly from Lemma 2.\qed \medskip We call a G-nomial $R$ as above a {\it reduced} G-nomial. \medskip {\bf 4 Lemma} (translation invariance). \medskip {\sl If $P(z_1,\ldots,w_n)$ is a G-nomial, then $$ P(z_1+s,\ldots,w_n+s)=P(z_1,\ldots,w_n) $$ {\it i.e.,} $P$ is translation invariant.} \medskip If there is a circle $\Gamma$ separating $\{z_1,\ldots,z_m\}$, $\{w_1,\ldots,w_n\}$, then the polynomial $$ p(s)=P(z_1+s,\ldots,w_n+s) $$ satisfies $p(s)\ne0$ for all $s\in{\bf C}$. This implies that $p(s)$ is constant, or $dp/ds=0$, for $(z_1,\ldots,w_n)$ in a nonempty open subset of ${\bf C}^{2n}$. Therefore $dp/ds=0$ identically, and $p$ depends only on $(z_1,\ldots,w_n)$. From this the lemma follows.\qed \medskip {\bf 5 Proposition} (properties of reduced G-nomials). \medskip {\sl If $P(z_1,\ldots,w_n)$ is a reduced G-nomial, the following properties hold: \medskip {\rm (reduced form)} there are constants $C_\pi$ such that $P$ has the reduced form $$ P(z_1,\ldots,w_n)=\sum_\pi C_\pi\prod_{j=1}^n(z_j-w_{\pi(j)}) $$ where the sum is over all permutations $\pi$ of $(1,\ldots,n)$ \medskip {\rm (conformal invariance)} if $ad-bc\ne0$, then $$ P({az_1+b\over cz_1+d},\ldots,{aw_n+b\over cw_n+d}) =P(z_1,\ldots,w_n)\prod_{j=1}^n{ad-bc\over(cz_j+d)(cw_j+d)} $$ in particular we have the identity $$ (\prod_{i=1}^kz_i)(\prod_{j=1}^kw_j)R(z_1^{-1},\ldots,w_k^{-1}) =(-1)^kR(z_1,\ldots,w_k) $$ \indent {\rm (roots)} the polynomial $$ \hat P(z)=P(z,\ldots,z,w_1,\ldots,w_n) $$ is equal to $\prod_{k=1}^n(z-w_k)$, so that its roots are the $w_k$ (repeated according to multiplicity).} \medskip Using Proposition 3 and Lemma 4, the above properties follow from Proposition A2 and Corollary A3 in Appendix A.\qed \medskip {\bf 6 Proposition} (compactness). \medskip {\sl The space of MA-nomials in $2n$ variables which are homogeneous of degree $n$ may be identified with ${\bf C}^{({2n\atop n})}$. The set $G_n$ of reduced G-nomials of degree $n$ is then a compact subset of ${\bf C}^{({2n\atop n})}$. We shall see later (Corollary 15) that $G_n$ is also contractible.} \medskip Let $P_k\in G_n$ and $P_k\to P_\infty$. In particular $P_\infty$ is homogeneous of degree $n$, and the monomial $z_1\cdots z_n$ occurs with coefficient 1. Suppose now that $$ P_\infty(Z_1,\ldots,Z_m,W_1,\ldots,W_n)=0 $$ with $\{Z_1,\ldots,Z_m\}$, $\{W_1,\ldots,W_n\}$ separated by a circle $\Gamma$. One can then choose discs $D_1$, \dots, $D_{2n}$ containing $\{Z_1,\ldots,W_n\}$ and not intersecting $\Gamma$. Lemma A1 in Appendix A would then imply that $P_\infty$ vanishes identically in contradiction with the fact that $P_\infty$ contains the term $z_1\cdots z_n$. Therefore $P_\infty\in G_n$, {\it i.e.}, $G_n$ is closed. \medskip Suppose now that $G_n$ were unbounded. There would then be $P_k$ such that the largest coefficient (in modulus) $c_k$ in $P_k$ tends to $\infty$. Going to a subsequence we may assume that $$ c_k^{-1} P_k\to P_\infty $$ where $P_\infty$ is a homogeneous MA-nomial of degree $n$, and does not vanish identically. The same argument as above shows that $P_\infty$ is a G-nomial, hence (by Proposition 3) the coefficient $\alpha$ of $z_1\cdots z_n$ does not vanish, but since $\alpha=\lim c_k^{-1}$, $c_k$ cannot tend to infinity as supposed. $G_n$ is thus bounded, hence compact.\qed \medskip {\bf 7 Proposition} (the cases $n=1$, $2$). \medskip {\sl The reduced G-nomials with $n=1,2$ are as follows: \medskip\noindent For $n=1$: $P=z_1-w_1$. \medskip\noindent For $n=2$: $P=(1-\theta)(z_1-w_1)(z_2-w_2)+\theta(z_1-w_2)(z_2-w_1)$ with real $\theta\in[0,1]$.} \medskip We use Proposition 5 to write $P$ in reduced form. \medskip\noindent In the case $n=1$, we have $P=C(z_1-w_1)$, and $C=1$ by normalization. \medskip\noindent In the case $n=2$, we have $$ P=C'(z_1-w_1)(z_2-w_2)+C''(z_1-w_2)(z_2-w_1) $$ In view of (G), $C'$, $C''$ are not both $0$. Assume $C'\ne0$, then (G) says that $$ {z_1-w_1\over z_1-w_2}:{z_2-w_1\over z_2-w_2} +{C''\over C'}\ne0\eqno{(1)} $$ when $\{z_1,z_2\}$, $\{w_1,w_2\}$ are separated by a circle. If $C''/C'$ were not real, we could find $z_1,z_2,w_1,w_2$ such that $$ {z_1-w_1\over z_1-w_2}:{z_2-w_1\over z_2-w_2} =-{C''\over C'}\eqno{(2)} $$ but the fact that the cross-ratio in the left hand side of (2) is not real means that $z_1,z_2,w_1,w_2$ are not on the same circle, and this implies that there is a circle separating $\{z_1,z_2\}$, $\{w_1,w_2\}$. Therefore (1) and (2) both hold, which is impossible. We must therefore assume $C''/C'$ real, and it suffices to check (1) for $z_1,z_2,w_1,w_2$ on a circle. The condition that $\{z_1,z_2\}$, $\{w_1,w_2\}$ are separated by a circle is now equivalent to the cross-ratio being $>0$, and therefore (G) is equivalent to $C''/C'\ge0$. If we assume $C''\ne0$, the argument is similar and gives $C'/C''\ge0$. The normalization condition yields then $C'=1-\theta$, $C''=\theta$ with $\theta\in[0,1]$\qed \medskip {\bf 8 Proposition} (determinants). \medskip {\sl Let $\Delta_z$ be the diagonal $n\times n$ matrix where the $j$-th diagonal element is $z_j$ and similarly for $\Delta_w$. Also let $U$ be a unitary $n\times n$ matrix ($U\Delta_wU^{-1}$ is thus an arbitrary normal matrix with eigenvalues $w_1,\ldots,w_n$). Then $$ P(z_1,\ldots,z_n,w_1,\ldots,w_n)=\det(\Delta_z-U\Delta_wU^{-1}) $$ is a reduced G-nomial. We may assume that $\det U=1$ and write} $$ \det(\Delta_z-U\Delta_wU^{-1})=\det((U_{ij}(z_i-w_j))) $$ \medskip Let $\{z_1,\ldots,z_n\}$, $\{w_1,\ldots,w_n\}$ be separated by a circle $\Gamma$. We may assume that $\Gamma$ is a proper circle. Suppose first that the $z_j$ are inside the circle $\Gamma$ and the $w_j$ outside. We want to prove that $\det(\Delta_z-U\Delta_wU^{-1})\ne0$. By translation we may assume that $\Gamma$ is centered at the origin, say $\Gamma=\{z:|z|=R\}$; then, by assumption, using the operator norm, $$ ||\Delta_z||1$ because $a$ is of degree $\le1$ in each variable $z_3,\ldots,w_n$. Therefore if $-(b_0+c_0)^2/4a+d=0$, {\it i.e.}, if $a$ divides $(b_0+c_0)^2$, then $a$ divides $(b_0+c_0)$ and the quotient is homogeneous of degree 1. But then $(b_0+c_0)^2/4a$ contains some variables with an exponent 2, in contradiction with the fact that in $d$ all variables occur with an exponent $\le1$. In conclusion $-(b_0+c_0)^2/4a+d$ cannot vanish identically. \medskip By a small change of $z_3,\ldots,w_n$ we can thus assume that $$ a\ne0\qquad,\qquad-{(b_0+c_0)^2\over4a}+d\ne0\eqno{(8)} $$ We shall first consider this case and later use a limit argument to prove (A) when (8) does not hold. By the change of coordinates $$ z_1=u_1-{b_0+c_0\over2a}\qquad,\qquad z_2=u_2-{b_0+c_0\over2a} $$ (linear in $z_1$, $z_2$) we obtain $$ p_\alpha =au_1u_2+{1\over2}(b_\alpha-c_\alpha)(u_1-u_2)-{(b_0+c_0)^2\over4a}+d $$ (Note that $b_\alpha+c_\alpha=b_0+c_0$). Write $$ A=(b_0+c_0)^2-4ad\qquad,\qquad\beta={\sqrt A\over2a} \qquad,\qquad\lambda(\alpha)={b_\alpha-c_\alpha\over\sqrt A} $$ for some choice of the square root of $A$, and $$ u_1=\beta v_1\qquad,\qquad u_2=\beta v_2 $$ then $$ p_\alpha={A\over4a}(v_1v_2+\lambda(\alpha)(v_1-v_2)-1) $$ If we write $v_1=(\zeta_1+1)/(\zeta_1-1)$, $v_2=(\zeta_2+1)/(\zeta_2-1)$, the condition $p_\alpha\ne0$ becomes $$ \zeta_1(1-\lambda(\alpha)) +\zeta_2(1+\lambda(\alpha))\ne0\eqno{(9)} $$ \indent Note that $\lambda(\alpha)=\pm1$ means $(b_\alpha-c_\alpha)^2-A=0$, {\it i.e.}, $ad-b_\alpha c_\alpha=0$ and $$ p_\alpha=a(z_1-S_\alpha)(z_2-T_\alpha) $$ \indent By assumption $p_0(z,z)\ne0$ when $z\in\Delta$. Therefore, the image $\Delta_v$ of $\Delta$ in the $v$-variable does not contain $+1$, $-1$, and the image $\Delta_\zeta$ in the $\zeta$-variable does not contain $0$, $\infty$. In particular $\Delta_\zeta$ is a circular disc or a half-plane, and thus {\it convex}. \medskip If $\lambda(\alpha)$ is real and $-1\le\lambda(\alpha)\le1$, (9) holds when $\zeta_1,\zeta_2\in\Delta_\zeta$. [This is because $\Delta_\zeta$ is convex and $\Delta_\zeta\not\ni0$]. Therefore in that case (A) holds. \medskip We may thus exclude the values of $\alpha$ such that $-1\le\lambda(\alpha)\le1$, and reduce the proof of the proposition to the case when at most one of $\lambda(0)$, $\lambda(1)$ is in $[-1,1]$, and the other $\lambda(\alpha)\notin[-1,1]$. Exchanging possibly $P_0$, $P_1$, we may assume that all $\lambda(\alpha)\notin[-1,1]$ except $\lambda(1)$. Exchanging possibly $z_1$, $z_2$, ({\it i.e.}, replacing $\lambda$ by $-\lambda$) we may assume that $\lambda(1)\ne1$. We may finally assume that $$ |\lambda(0)+1|+|\lambda(0)-1| \ge|\lambda(1)+1|+|\lambda(1)-1|\eqno{(10)} $$ where the left hand side is $>2$ while the right hand side is =2 if $\lambda(1)\in[-1,1]$. \medskip For $\alpha\in[0,1]$ we define the map $$ f_\alpha: \zeta\mapsto{\lambda(\alpha)+1\over\lambda(\alpha)-1}\zeta $$ When $\alpha=0,1$ the inequality (9) holds by assumption for $\zeta_1,\zeta_2\in\Delta_\zeta$. [Note that the point $v=\infty$, {\it i.e.}, $\zeta=1$ does not make a problem: if $\lambda\ne\pm1$ this is seen by continuity; if $\lambda=\pm1$ this follows from $\Delta_\zeta\not\ni0$]. Therefore $$ \Delta_\zeta\cap f_0\Delta_\zeta=\emptyset\qquad, \qquad\Delta_\zeta\cap f_1\Delta_\zeta=\emptyset $$ We want to show that $\Delta_\zeta\cap f_\alpha\Delta_\zeta=\emptyset$ for $0<\alpha<1$. In fact, it suffices to prove $$ \Delta'_\zeta\cap f_\alpha\Delta'_\zeta=\emptyset $$ for slightly smaller $\Delta'\subset \Delta_\zeta$, {\it viz}, the inside of a proper circle $\Gamma'$ such that 0 is outside of $\Gamma'$. Since we may replace $\Delta'$ by any $c\Delta'$ where $c\in{\bf C}\backslash\{0\}$, we assume that $\Delta'$ is the interior of a circle centered at $\lambda(0)-1$ and with radius $r^0_-<|\lambda(0)-1|$. Then $f_0\Delta'$ is the interior of a circle centered at $\lambda(0)+1$ and with radius $r^0_+$. The above two circles are disjoint, but we may increase $r^0_-$ until they touch, obtaining $$ r^0_-+r^0_+=2\qquad,\qquad r^0_+=|{\lambda(0)+1\over\lambda(0)-1}|r^0_- $$ {\it i.e.}, $$ r_-^0={2|\lambda(0)-1|\over|\lambda(0)+1|+|\lambda(0)-1|}\qquad, \qquad r_+^0={2|\lambda(0)+1|\over|\lambda(0)+1|+|\lambda(0)-1|} $$ We define $r_-^\alpha$ and $r_+^\alpha$ similarly, with $\lambda(0)$ replaced by $\lambda(\alpha)$ for $\alpha\in[0,1]$. To prove that $\Delta'\cap f_\alpha\Delta'=\emptyset$ for $0<\alpha<1$, we may replace $\Delta'$ by ${\lambda(\alpha)-1\over\lambda(0)-1}\Delta'$ (which is a disc centered at $\lambda(\alpha)-1$) and it suffices to prove that the radius $|{\lambda(\alpha)-1\over\lambda(0)-1}|r_-^0$ of this disc is $\le r_-^\alpha$, {\it i.e.}, $$ {2|\lambda(\alpha)-1|\over|\lambda(0)+1|+|\lambda(0)-1|} \le{2|\lambda(\alpha)-1|\over|\lambda(\alpha)+1|+|\lambda(\alpha)-1|} $$ or $$ |\lambda(0)+1|+|\lambda(0)-1| \ge|\lambda(\alpha)+1|+|\lambda(\alpha)-1|\eqno{(11)} $$ Note now that $\{\lambda\in{\bf C}:|\lambda+1|+|\lambda-1|=const.\}$ is an ellipse with foci $\pm1$, and since $\lambda(\alpha)$ is affine in $\alpha$, the maximum value of $|\lambda(\alpha)+1|+|\lambda(\alpha)-1|$ for $\alpha\in[0,1]$ is reached at 0 or 1, and in fact at 0 by (10). This proves (11). \medskip This concludes the proof of (A) under the assumption (8). Consider now a limiting case when (8) fails and suppose that (A) does not hold. Then, by Lemma A1, $p_\alpha$ vanishes identically. In particular this would imply $p_\alpha(z,z)=0$, in contradiction with the assumption that $P_0$ is a G-nomial. \medskip We have thus shown that $P_\alpha$ is a G-nomial, and since it is homogeneous of degree $n$ in the $2n$ variables $z_1,\ldots,w_n$, and contains $z_1\cdots z_n$ with coefficient 1, $P_\alpha$ is a reduced G-nomial.\qed \medskip {\bf 15 Corollary} (contractibility). \medskip {\sl The set $G_n$ of reduced G-nomials is contractible.} \medskip In the linear space of MA-nomials $P(z_1,\ldots,w_n)$ satisfying the conditions of Proposition A2 we define a flow by $$ {dP\over dt} =-P+\textstyle{({n\atop 2})}^{-1}\sum\textstyle{^*}\pi P\eqno{(12)} $$ where $\Sigma^*$ is the sum over the $({n\atop 2})$ transpositions $\pi$, {\it i.e.} interchanges of two of the variables $z_1,\ldots,z_n$ of $P$. In view of Proposition 14, the positive semiflow defined by (12) preserves the set $G_n$ of reduced G-nomials. Condition (b)$_n$ of Proposition A2 shows that the only fixed point of (12) is, up to a normalizing factor, Grace's polynomial $P_\Sigma$. We have thus a contraction of $G_n$ to $\{P_\Sigma\}$, and $G_n$ is therefore contractible.\qed \bigskip \centerline{\bf A. Appendix.} \bigskip {\bf A1 Lemma} (limits). \medskip {\sl Let $D_1,\ldots,D_r$ be open discs, and assume that the MA-nomials $P_k(z_1,\ldots,z_r)$ do not vanish when $z_1\in D_1$, \dots, $z_r\in D_r$. If the $P_k$ have a limit $P_\infty$ when $k\to\infty$, and if $P_\infty(\hat z_1,\ldots,\hat z_r)=0$ for some $\hat z_1\in D_1$, \dots, $\hat z_r\in D_r$, then $P_\infty=0$ identically.} \medskip There is no loss of generality in assuming that $\hat z_1=\ldots=\hat z_r=0$. We prove the lemma by induction on $r$. For $r=1$, if the affine function $P_\infty$ vanishes at 0 but not identically, the implicit function theorem shows that $P_k$ vanishes for large $k$ at some point close to 0, contrary to assumption. For $r>1$, the induction assumption implies that putting any one of the variables $z_1,\ldots,z_r$ equal to 0 in $P_\infty$ gives the zero polynomial. Therefore $P_\infty(z_1,\ldots,z_r)=\alpha z_1\cdots z_r$. Fix now $z_j=a_i\in D_i\backslash\{0\}$ for $j=1,\ldots,r-1$. Then $P_k(a_1,\ldots,a_{r-1},z_r)\ne0$ for $z_r\in D_r$, but the limit $P_\infty(a_1,\ldots,a_{r-1},z_r)=\alpha a_1\cdots a_{r-1}z_r$ vanishes at $z_r=0$ and therefore identically, {\it i.e.}, $\alpha=0$, which proves the lemma.\qed \medskip {\bf A2 Proposition} (reduced forms). \medskip {\sl For $n\ge1$, the following conditions on a MA-nomial $P(z_1,\ldots,z_n,w_1,\ldots,w_n)$ not identically zero are equivalent: \medskip (a)$_n$ $P$ satisfies} $$ P(z_1+\xi,\ldots,w_n+\xi)=P(z_1,\ldots,w_n)\qquad \qquad\hbox{(translation\quad invariance)} $$ $$ P(\lambda z_1,\ldots,\lambda w_n)=\lambda^nP(z_1,\ldots,w_n)\qquad \qquad\hbox{(homogeneity of degree $n$)} $$ \indent{\sl (b)$_n$ There are constants $C_\pi$ such that $$ P(z_1,\ldots,w_n)=\sum_\pi C_\pi\prod_{j=1}^n(z_j-w_{\pi(j)}) $$ where the sum is over all permutations $\pi$ of $(1,\ldots,n)$.} \medskip We say that (b)$_n$ gives a {\it reduced form} of $P$ (it need not be unique). \medskip Clearly (b)$_n\Rightarrow$(a)$_n$. We shall prove (a)$_n\Rightarrow$(b)$_n$ by induction on $n$, and obtain at the same time a bound $\sum|C_\pi|\le k_n.||P||$ for some norm $||P||$ (the space of $P$'s is finite dimensional, so all norms are equivalent). Clearly, (a)$_1$ implies that $P(z_1,w_1)=C(z_1-w_1)$, so that (b)$_1$ holds. Let us now assume that $P$ satisfies (a)$_n$ for some $n>1$. \medskip If $X$ is an $n$-element subset of $\{z_1,\ldots,w_n\}$, let $A(X)$ denote the coefficient of the corresponding monomial in $P$. We have $$ \sum_XA(X)=P(1,\ldots,1)=P(0,\ldots,0)=0 $$ In particular $$ \max_{X',X''}|A(X')-A(X'')|\ge\max_XA(X) $$ Note also that one can go from $X'$ to $X''$ in a bounded number of steps exchanging a $z_j$ and a $w_k$. Therefore one can choose $z_j$, $w_k$, $Z$ containing $z_j$ and not $w_k$, and $W$ obtained by replacing $z_j$ by $w_k$ in $Z$ so that $$ |A(Z)-A(W)|\ge\alpha(\sum_X|A(X)|^2)^{1/2} $$ where $\alpha$ depends only on $n$. \medskip Write now $$ P=az_jw_k+bz_j+cw_k+d $$ where the polynomials $a$, $b$, $c$, $d$ do not contain $z_j$, $w_k$. We have thus $$ P=P_1+{1\over2}(b-c)(z_j-w_k) $$ where $$ P_1=az_jw_k+{1\over2}(b+c)(z_j+w_k)+d $$ Let $\tilde a$, $\tilde b$, $\tilde c$, $\tilde d$ be obtained by adding $\xi$ to all the arguments of $a$, $b$, $c$, $d$. By translation invariance we have thus $$ az_jw_k+bz_j+cw_k+d =\tilde a(z_j+\xi)(w_k+\xi)+\tilde b(z_j+\xi)+\tilde c(w_k+\xi)+\tilde d $$ $$ =\tilde az_jw_k+(\tilde a\xi+\tilde b)z_j+(\tilde a\xi+\tilde c)w_k +\tilde a\xi^2+(\tilde b+\tilde c)\xi+\tilde d $$ hence $\tilde b-\tilde c=b-c$. Therefore $b-c$ satisfies (a)$_{n-1}$ and, using the induction assumption we see that $$ {1\over2}(b-c)(z_j-w_k) $$ has the form given by (b)$_n$. In particular $P_1$ again satisfies (a)$_n$. \medskip We compare now the coefficients $A_1(X)$ for $P_1$ and $A(X)$ for $P$: $$ \sum_X|A(X)|^2-\sum_X|A_1(X)|^2 \ge|A(Z)|^2+|A(W)|^2-{1\over2}|A(Z)+A(W)|^2 $$ $$ ={1\over2}|A(Z)-A(W)|^2\ge{\alpha^2\over2}\sum_X|A(X)|^2 $$ so that $$ \sum|A_1(X)|^2\le(1-{\alpha^2\over2})\sum_X|A(X)|^2 $$ We have thus a geometrically convergent approximation of $P$ by expressions satisfying (b)$_n$, and an estimate of $\sum|C_\pi|$ as desired.\qed \medskip {\bf A3 Corollary} \medskip {\sl If the MA-nomial $P(z_1,\ldots,w_n)$ satisfies the conditions of Proposition A2, the following properties hold: \medskip {\rm (conformal invariance)} if $ad-bc\ne0$, then $$ P({az_1+b\over cz_1+d},\ldots,{aw_n+b\over cw_n+d}) =P(z_1,\ldots,w_n)\prod_{j=1}^n{ad-bc\over(cz_j+d)(cw_j+d)} $$ \indent {\rm (roots)} the polynomial $$ \hat P(z)=P(z,\ldots,z,w_1,\ldots,w_n) $$ has exactly the roots $w_1,\ldots,w_n$ (repeated according to multiplicity).} \medskip These properties follow directly if one writes $P$ in reduced form.\qed \medskip {\bf References.} [1] H. Epstein. ``Some analytic properties of scattering amplitudes in quantum field theory.'' in M. Chretien and S. Deser eds. {\it Axiomatic Field Theory.} Gordon and Breach, New York, 1966. [2] O.J. Heilmann and E.H. Lieb. ``Theory of monomer-dimer systems.'' Commun. Math. Phys. {\bf 25},190-232(1972); {\bf 27},166(1972). [3] T. D. Lee and C. N. Yang. ``Statistical theory of equations of state and phase relations. II. Lattice gas and Ising model.'' Phys. Rev. {\bf 87},410-419(1952). [4] G. Polya and G. Szeg\"o. {\it Problems and theorems in analysis II.} Springer, Berlin, 1976. [5] D. Ruelle. ``Extension of the Lee-Yang circle theorem.'' Phys. Rev. Letters {\bf 26},303-304(1971). [6] D. Ruelle. ``Counting unbranched subgraphs.'' J. Algebraic Combinatorics {\bf 9},157-160(1999); ``Zeros of graph-counting polynomials.'' Commun. Math. Phys. {\bf 200},43-56(1999). [7] L. H\"ormander. {\it An introduction to complex analysis in several variables.} D. Van Nostrand, Princeton, 1966. \end ---------------0009200508626--