On the number of zeropatterns of a sequence of polynomials
Authors:
Lajos Rónyai, László Babai and Murali K. Ganapathy
Journal:
J. Amer. Math. Soc. 14 (2001), 717735
MSC (2000):
Primary 12E05, 05A16; Secondary 15A03, 05E99, 05D40, 05D99, 05C62, 05C80, 05D10, 68Q05, 68R05, 03C10, 03C60
DOI:
https://doi.org/10.1090/S0894034701003678
Published electronically:
February 27, 2001
MathSciNet review:
1824986
Fulltext PDF Free Access
Abstract  References  Similar Articles  Additional Information
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 zeropattern 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 zeropatterns 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 halfpage 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 zeropatterns of a sequence of polynomials. We conclude the paper with a number of open problems.

ajtai M. Ajtai, A Nonlinear Time Lower Bound for Boolean Branching Programs, Proc. 40th Annual Symp. on Foundations of Comp. Sci. (FOCS’99), IEEE 1999, pp. 60–70.
 Noga Alon, Ramsey graphs cannot be defined by real polynomials, J. Graph Theory 14 (1990), no. 6, 651–661. MR 1079214, DOI https://doi.org/10.1002/jgt.3190140605
 Noga Alon, Tools from higher algebra, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1749–1783. MR 1373688 orlitsky N. Alon, A. Orlitsky, Repeated communication and Ramsey graphs. IEEE Transactions on Information Theory 41 (1995) 1276–1289. bfr L. Babai, P. Frankl, Linear Algebra Methods in Combinatorics, Preliminary Version 2 (1992). Department of Computer Science, University of Chicago.
 László Babai, Anna Gál, and Avi Wigderson, Superpolynomial lower bounds for monotone span programs, Combinatorica 19 (1999), no. 3, 301–319. MR 1723251, DOI https://doi.org/10.1007/s004930050058
 László Babai, Noam Nisan, and Márió Szegedy, Multiparty protocols, pseudorandom generators for logspace, and timespace tradeoffs, J. Comput. System Sci. 45 (1992), no. 2, 204–232. Twentyfirst Symposium on the Theory of Computing (Seattle, WA, 1989). MR 1186884, DOI https://doi.org/10.1016/00220000%2892%2990047M
 Zs. Baranyai, On the factorization of the complete uniform hypergraph, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. I, NorthHolland, Amsterdam, 1975, pp. 91–108. Colloq. Math. Soc. Ján\B{o}s Bolyai, Vol. 10. MR 0416986
 Saugata Basu, Richard Pollack, and MarieFrançoise Roy, On the number of cells defined by a family of polynomials on a variety, Mathematika 43 (1996), no. 1, 120–126. MR 1401711, DOI https://doi.org/10.1112/S0025579300011621
 József Beck and Tibor Fiala, “Integermaking” theorems, Discrete Appl. Math. 3 (1981), no. 1, 1–8. MR 604260, DOI https://doi.org/10.1016/0166218X%2881%29900226
 Amos Beimel, Anna Gál, and Mike Paterson, Lower bounds for monotone span programs, Comput. Complexity 6 (1996/97), no. 1, 29–45. MR 1436301, DOI https://doi.org/10.1007/BF01202040 bose R. C. Bose, A note on Fisher’s inequality for balanced incomplete block designs. Ann. Math. Stat. 20 (1949) 619–620.
 W. Dale Brownawell, Bounds for the degrees in the Nullstellensatz, Ann. of Math. (2) 126 (1987), no. 3, 577–591. MR 916719, DOI https://doi.org/10.2307/1971361 erdos P. Erdős, Some remarks on the theory of graphs. Bull. A. M. S. 53 (1947) 292–294.
 Paul Erdős and Joel Spencer, Probabilistic methods in combinatorics, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New YorkLondon, 1974. Probability and Mathematical Statistics, Vol. 17. MR 0382007
 Noaï Fitchas, André Galligo, and Jacques Morgenstern, Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields, J. Pure Appl. Algebra 67 (1990), no. 1, 1–14. MR 1076744, DOI https://doi.org/10.1016/00224049%2890%2990159F
 P. Frankl and R. M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), no. 4, 357–368. MR 647986, DOI https://doi.org/10.1007/BF02579457 gal A. Gál, A characterization of span program size and improved lower bounds for monotone span programs, Proc. of the 30th ACM Symp. on Theory of Computing (STOC’98), ACM, 1998, 429–437. Gale D. Gale, A theorem on flows in networks. Pacific J. Math. 7 (1957) 1073–1082.
 S. W. Graham and C. J. Ringrose, Lower bounds for least quadratic nonresidues, Analytic number theory (Allerton Park, IL, 1989) Progr. Math., vol. 85, Birkhäuser Boston, Boston, MA, 1990, pp. 269–309. MR 1084186
 Joos Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci. 24 (1983), no. 3, 239–277. MR 716823, DOI https://doi.org/10.1016/03043975%2883%29900026
 M. Karchmer and A. Wigderson, On span programs, Proceedings of the Eighth Annual Structure in Complexity Theory Conference (San Diego, CA, 1993) IEEE Comput. Soc. Press, Los Alamitos, CA, 1993, pp. 102–111. MR 1310791, DOI https://doi.org/10.1109/SCT.1993.336536
 János Kollár, Sharp effective Nullstellensatz, J. Amer. Math. Soc. 1 (1988), no. 4, 963–975. MR 944576, DOI https://doi.org/10.1090/S08940347198809445767
 D. G. Larman, C. A. Rogers, and J. J. Seidel, On twodistance sets in Euclidean space, Bull. London Math. Soc. 9 (1977), no. 3, 261–267. MR 458308, DOI https://doi.org/10.1112/blms/9.3.261 lindsey J. H. Lindsey: see [15, p. 88], [7, Prop. 2.3].
 J. H. van Lint and R. M. Wilson, A course in combinatorics, Cambridge University Press, Cambridge, 1992. MR 1207813
 L. Lovász, Flats in matroids and geometric graphs, Combinatorial surveys (Proc. Sixth British Combinatorial Conf., Royal Holloway Coll., Egham, 1977) Academic Press, London, 1977, pp. 45–86. MR 0480111
 J. Milnor, On the Betti numbers of real varieties, Proc. Amer. Math. Soc. 15 (1964), 275–280. MR 161339, DOI https://doi.org/10.1090/S00029939196401613399
 Hugh L. Montgomery, Topics in multiplicative number theory, Lecture Notes in Mathematics, Vol. 227, SpringerVerlag, BerlinNew York, 1971. MR 0337847 neciporuk É. I. Nečiporuk, On a Boolean function. Soviet. Math. Doklady 7 (1966) 999–1000. oleinik A. O. Oleĭnik, Estimates of the Betti numbers of real algebraic hypersurfaces. Mat. Sbornik (N. S.) 28 (1951) 635–640 (in Russian). op A. O. Oleĭnik, I. B. Petrovskiĭ, On the topology of real algebraic surfaces. Izv. Akad. Nauk SSSR 13 (1949) 389–402 (in Russian). (Transl. Amer. Math. Soc. 7 (1962) 399–417.)
 P. Pudlák and V. Rödl, A combinatorial approach to complexity, Combinatorica 12 (1992), no. 2, 221–226. MR 1179258, DOI https://doi.org/10.1007/BF01204724
 Dijen K. RayChaudhuri and Richard M. Wilson, On $t$designs, Osaka Math. J. 12 (1975), no. 3, 737–744. MR 392624 Ryser H. J. Ryser, Combinatorial properties of matrices of zeros and ones. Canad. J. Math. 9 (1957) 371–377.
 René Thom, Sur l’homologie des variétés algébriques réelles, Differential and Combinatorial Topology (A Symposium in Honor of Marston Morse), Princeton Univ. Press, Princeton, N.J., 1965, pp. 255–265 (French). MR 0200942
 Hugh E. Warren, Lower bounds for approximation by nonlinear manifolds, Trans. Amer. Math. Soc. 133 (1968), 167–178. MR 226281, DOI https://doi.org/10.1090/S00029947196802262811
 Ingo Wegener, The complexity of Boolean functions, WileyTeubner Series in Computer Science, John Wiley & Sons, Ltd., Chichester; B. G. Teubner, Stuttgart, 1987. MR 905473
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, H1111 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
Keywords:
Polynomials,
zeropatterns,
linear algebra bound,
signpatterns,
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,
spanprograms,
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, NWOOTKA and AKP
The second author was partially supported by NSF grant CCR9732205.
Article copyright:
© Copyright 2001
American Mathematical Society