On the number of zeropatterns of a sequence of polynomials
HTML articles powered by AMS MathViewer
 by Lajos Rónyai, László Babai and Murali K. Ganapathy PDF
 J. Amer. Math. Soc. 14 (2001), 717735 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 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.References

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 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 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 10.1016/00220000(92)90047M
 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, Colloq. Math. Soc. János Bolyai, Vol. 10, NorthHolland, Amsterdam, 1975, pp. 91–108. 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 10.1112/S0025579300011621
 József Beck and Tibor Fiala, “Integermaking” theorems, Discrete Appl. Math. 3 (1981), no. 1, 1–8. MR 604260, DOI 10.1016/0166218X(81)900226
 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 10.1007/BF01202040
 Morgan Ward and R. P. Dilworth, The lattice theory of ova, Ann. of Math. (2) 40 (1939), 600–608. MR 11, DOI 10.2307/1968944
 W. Dale Brownawell, Bounds for the degrees in the Nullstellensatz, Ann. of Math. (2) 126 (1987), no. 3, 577–591. MR 916719, DOI 10.2307/1971361
 A. R. Collar, On the reciprocation of certain matrices, Proc. Roy. Soc. Edinburgh 59 (1939), 195–206. MR 8, DOI 10.1017/S0370164600012281
 Paul Erdős and Joel Spencer, Probabilistic methods in combinatorics, Probability and Mathematical Statistics, Vol. 17, Academic Press [Harcourt Brace Jovanovich, Publishers], New YorkLondon, 1974. 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 10.1016/00224049(90)90159F
 P. Frankl and R. M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), no. 4, 357–368. MR 647986, DOI 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.
 Saunders MacLane and O. F. G. Schilling, Infinite number fields with Noether ideal theories, Amer. J. Math. 61 (1939), 771–782. MR 19, DOI 10.2307/2371335
 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 10.1016/03043975(83)900026
 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 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 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 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 10.1090/S00029939196401613399
 Hugh L. Montgomery, Topics in multiplicative number theory, Lecture Notes in Mathematics, Vol. 227, SpringerVerlag, BerlinNew York, 1971. MR 0337847, DOI 10.1007/BFb0060851
 K. A. Hirsch, On skewgroups, Proc. London Math. Soc. 45 (1939), 357–368. MR 0000036, DOI 10.1112/plms/s245.1.357
 C. J. Everett Jr., Annihilator ideals and representation iteration for abstract rings, Duke Math. J. 5 (1939), 623–627. MR 13
 C. J. Everett Jr., Annihilator ideals and representation iteration for abstract rings, Duke Math. J. 5 (1939), 623–627. MR 13
 P. Pudlák and V. Rödl, A combinatorial approach to complexity, Combinatorica 12 (1992), no. 2, 221–226. MR 1179258, DOI 10.1007/BF01204724
 Dijen K. RayChaudhuri and Richard M. Wilson, On $t$designs, Osaka Math. J. 12 (1975), no. 3, 737–744. MR 392624
 Saunders MacLane and O. F. G. Schilling, Infinite number fields with Noether ideal theories, Amer. J. Math. 61 (1939), 771–782. MR 19, DOI 10.2307/2371335
 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 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
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, 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
 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.  © Copyright 2001 American Mathematical Society
 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
 MathSciNet review: 1824986