Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(online) ISSN 0894-0347(print)

 

On the number of zero-patterns of a sequence of polynomials


Authors: Lajos Rónyai, László Babai and Murali K. Ganapathy
Journal: J. Amer. Math. Soc. 14 (2001), 717-735
MSC (2000): Primary 12E05, 05A16; Secondary 15A03, 05E99, 05D40, 05D99, 05C62, 05C80, 05D10, 68Q05, 68R05, 03C10, 03C60
Published electronically: February 27, 2001
MathSciNet review: 1824986
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract:

Let ${\ensuremath{{\bf f}}\xspace} =(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 ${\ensuremath{{\bf f}}\xspace}$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({\ensuremath{{\bf f}}\xspace})$ denote the number of zero-patterns of ${\ensuremath{{\bf f}}\xspace}$as $u$ ranges over $F^n$. We prove that $Z_F({\ensuremath{{\bf f}}\xspace}) \le \sum_{j=0}^n \binom{m}{j}$ for $d=1$ and \begin{equation*}Z_F({\ensuremath{{\bf f}}\xspace})\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 [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 12E05, 05A16, 15A03, 05E99, 05D40, 05D99, 05C62, 05C80, 05D10, 68Q05, 68R05, 03C10, 03C60

Retrieve articles in all journals with MSC (2000): 12E05, 05A16, 15A03, 05E99, 05D40, 05D99, 05C62, 05C80, 05D10, 68Q05, 68R05, 03C10, 03C60


Additional Information

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

DOI: http://dx.doi.org/10.1090/S0894-0347-01-00367-8
PII: S 0894-0347(01)00367-8
Keywords: Polynomials, zero-patterns, linear algebra bound, sign-patterns, real algebraic geometry, affine varieties, algebraically closed fields, quantifier elimination, asymptotic counting, counting patterns, graph representation, projective dimension of graphs, probabilistic method, nonconstructive proof, Ramsey theory, models of computation, span-programs, extremal combinatorics
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.
Article copyright: © Copyright 2001 American Mathematical Society