Remote Access Journal of the American Mathematical Society
Green Open Access

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


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?)

  • 1. M. Ajtai, A Non-linear Time Lower Bound for Boolean Branching Programs, Proc. 40th Annual Symp. on Foundations of Comp. Sci. (FOCS'99), IEEE 1999, pp. 60-70.
  • 2. N. Alon, Ramsey graphs cannot be defined by real polynomials. J. Graph Theory 14 (1990) 651-661. MR 92a:05090
  • 3. N. Alon, Tools from higher algebra, Handbook of Combinatorics, Elsevier and MIT Press, 1995 (R. Graham, M. Grötschel, L. Lovász, eds.), 1749-1783. MR 97a:05004
  • 4. N. Alon, A. Orlitsky, Repeated communication and Ramsey graphs. IEEE Transactions on Information Theory 41 (1995) 1276-1289. CMP 96:05
  • 5. L. Babai, P. Frankl, Linear Algebra Methods in Combinatorics, Preliminary Version 2 (1992). Department of Computer Science, University of Chicago.
  • 6. L. Babai, A. Gál, A. Wigderson, Superpolynomial lower bounds for monotone span programs. Combinatorica 19 (1999) 301-320. MR 2000j:68061
  • 7. L. Babai, N. Nisan, M. Szegedy, Multiparty protocols, pseudorandom generators for Logspace, and time-space trade-offs. J. Comp. Sys. Sci. 45 (1992) 204-232. MR 93m:68048
  • 8. Zs. Baranyai, On the factorization of the complete uniform hypergraph, In: Infinite and finite sets, Proc. Coll. Keszthely, 1973, A. Hajnal, R. Rado and V.T. Sós, eds., Colloquia Math. Soc. János Bolyai 10, North-Holland, 1975, pp. 91-107. MR 54:5047
  • 9. S. Basu, R. Pollack, M-F. Roy, On the number of cells defined by a family of polynomials on a variety. Mathematika 43 (1996) 120-126. MR 97h:14076
  • 10. J. Beck, T. Fiala, ``Integer-making'' Theorems. Discrete Applied Mathematics 3 (1981) 1-8. MR 82d:05088
  • 11. A. Beimel, A. Gál, M. Paterson, Lower bounds for monotone span programs. Computational Complexity 6 (1996/97) 29-45. MR 98c:68086
  • 12. R.C. Bose, A note on Fisher's inequality for balanced incomplete block designs. Ann. Math. Stat. 20 (1949) 619-620. MR 11:306e
  • 13. W.D. Brownawell, Bounds for the degrees in the Nullstellensatz. Annals of Mathematics (2) 126 (1987) 577-591. MR 89b:12001
  • 14. P. Erdos, Some remarks on the theory of graphs. Bull. A.M.S. 53 (1947) 292-294. MR 8:479d
  • 15. P. Erdos, J. Spencer, Probabilistic Methods in Combinatorics, Academic Press, 1974. MR 52:2895
  • 16. N. Fitchas, A. Galligo, J. Morgenstern, Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields. J. Pure Appl. Algebra 67 (1990) 1-14. MR 91j:03010
  • 17. P. Frankl, R.M. Wilson, Intersection theorems with geometric consequences. Combinatorica 1 (1981) 357-368. MR 84g:05085
  • 18. 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. CMP 2000:12
  • 19. D. Gale, A theorem on flows in networks. Pacific J. Math. 7 (1957) 1073-1082. MR 19:1024a
  • 20. S.W. Graham, C.J. Ringrose, Lower bounds for least quadratic nonresidues, Analytic number theory (Allerton Park, IL, 1989), Progr. Math., Vol. 85, Birkhäuser, Boston, MA, 1990, pp. 269-309. MR 92d:11108
  • 21. J. Heintz, Definability and fast quantifier elimination in algebraically closed fields. Theor. Comp. Sci. 24 (1983), 239-278. MR 85a:68062
  • 22. M. Karchmer, A. Wigderson, On span programs, Proc. 8th Ann. Symp. Structure in Complexity Theory, IEEE 1993, pp. 102-111. MR 96a:68035
  • 23. J. Kollár, Sharp effective Nullstellensatz. J. Amer. Math. Soc. 1 (1988) 963-975. MR 89h:12008
  • 24. D.G. Larman, C.A. Rogers, J.J. Seidel, On two-distance sets in Euclidean space. Bull. London Math. Soc. 9 (1977) 261-267. MR 56:16511
  • 25. J.H. Lindsey: see [15, p. 88], [7, Prop. 2.3].
  • 26. J.H. van Lint, R.M. Wilson, A Course in Combinatorics, Cambridge Univ. Press, 1992. MR 94g:05003
  • 27. L. Lovász, Flats in matroids and geometric graphs, In: Combinatorial surveys, Proc. 6th British Comb. Conf., Egham 1977 (P.J. Cameron, ed.), Academic Press, 1977, pp. 45-86. MR 58:310
  • 28. J. Milnor, On the Betti numbers of real varieties. Proc. Amer. Math. Soc. 15 (1964) 275-280. MR 28:4547
  • 29. H.L. Montgomery, Topics in multiplicative number theory, Springer Lecture Notes in Math., Vol. 227, Springer-Verlag, 1971. MR 49:2616
  • 30. É.I. Neciporuk, On a Boolean function. Soviet. Math. Doklady 7 (1966) 999-1000. MR 36:1237 9pt
  • 31. A.O. Ole{\u{\i}}\kern.15emnik, Estimates of the Betti numbers of real algebraic hypersurfaces. Mat. Sbornik (N.S.) 28 (1951) 635-640 (in Russian). MR 13:489b
  • 32. A.O. Ole{\u{\i}}\kern.15emnik, I.B. Petrovski{\u{\i}}\kern.15em, 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.) MR 13:978c
  • 33. P. Pudlák, V. Rödl, A combinatorial approach to complexity. Combinatorica 12 (1992) 221-226. MR 93m:68054
  • 34. D.K. Ray-Chaudhuri, R.M. Wilson, On $t$-designs. Osaka J. Math. 12 (1975) 737-744. MR 52:13441
  • 35. H. J. Ryser, Combinatorial properties of matrices of zeros and ones. Canad. J. Math. 9 (1957) 371-377. MR 19:379d
  • 36. R. Thom, Sur l'homologie des variétés algébriques réelles, Differential and Combinatorial Topology (Stewart S. Cairns, ed.), Princeton University Press, 1965. MR 34:828
  • 37. H.E. Warren, Lower bounds for approximation by non-linear manifolds. Trans. Amer. Math. Soc. 133 (1968) 167-178. MR 37:1871
  • 38. I. Wegener, The complexity of Boolean functions, Wiley-Teubner, 1987. MR 89b:03066

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

László Babai
Affiliation: Department of Computer Science, University of Chicago, Chicago, Illinois 60637

Murali K. Ganapathy
Affiliation: Department of Computer Science, University of Chicago, Chicago, Illinois 60637

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

American Mathematical Society