Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6834 (online) ISSN 0894-0347 (print)

The 2020 MCQ for Journal of the American Mathematical Society is 4.79.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

On the number of zero-patterns of a sequence of polynomialsHTML articles powered by AMS MathViewer

by Lajos Rónyai, László Babai and Murali K. Ganapathy
J. Amer. Math. Soc. 14 (2001), 717-735 Request permission

Abstract:

Let $\mathbf {f} =(f_1,\dots ,f_m)$ be a sequence of polynomials of degree $\le d$ in $n$ variables $(m\ge n)$ over a field $F$. The zero-pattern of $\mathbf {f}$ at $u\in F^n$ is the set of those $i$ ($1\le i\le m$) for which $f_i(u)=0$. Let $Z_F(\mathbf {f})$ denote the number of zero-patterns of $\mathbf {f}$ as $u$ ranges over $F^n$. We prove that $Z_F(\mathbf {f}) \le \sum _{j=0}^n \binom {m}{j}$ for $d=1$ and \begin{equation*} Z_F(\mathbf {f})\le \binom {md}{n}\tag {$*$} \end{equation*} for $d\ge 2$. For $m\ge nd$, these bounds are optimal within a factor of $(7.25)^n$. The bound ($*$) improves the bound $(1+md)^n$ proved by J. Heintz (1983) using the dimension theory of affine varieties. Over the field of real numbers, bounds stronger than Heintz’s but slightly weaker than ($*$) follow from results of J. Milnor (1964), H. E. Warren (1968), and others; their proofs use techniques from real algebraic geometry. In contrast, our half-page proof is a simple application of the elementary “linear algebra bound”. Heintz applied his bound to estimate the complexity of his quantifier elimination algorithm for algebraically closed fields. We give several additional applications. The first two establish the existence of certain combinatorial objects. Our first application, motivated by the “branching program” model in the theory of computing, asserts that over any field $F$, most graphs with $v$ vertices have projective dimension $\Omega (\sqrt {v/\log v})$ (the implied constant is absolute). This result was previously known over the reals (Pudlák–Rödl). The second application concerns a lower bound in the span program model for computing Boolean functions. The third application, motivated by a paper by N. Alon, gives nearly tight Ramsey bounds for matrices whose entries are defined by zero-patterns of a sequence of polynomials. We conclude the paper with a number of open problems.
References
Similar Articles
• Lajos Rónyai
• Affiliation: Computer and Automation Research Institute, Hungarian Academy of Sciences, H-1111 Budapest, Lágymányosi u. 11, Hungary
• Email: lajos@nyest.ilab.sztaki.hu
• László Babai
• Affiliation: Department of Computer Science, University of Chicago, Chicago, Illinois 60637
• Email: laci@cs.uchicago.edu
• Murali K. Ganapathy
• Affiliation: Department of Computer Science, University of Chicago, Chicago, Illinois 60637
• Email: gmkrishn@cs.uchicago.edu
• Received by editor(s): July 25, 2000
• Received by editor(s) in revised form: December 22, 2000
• Published electronically: February 27, 2001
• Additional Notes: The first author was partially supported by grants from OTKA, NWO-OTKA and AKP
The second author was partially supported by NSF grant CCR-9732205.