On the number of zero-patterns 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), 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
- ajtai 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.
- 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 time-space trade-offs, J. Comput. System Sci. 45 (1992), no. 2, 204–232. Twenty-first Symposium on the Theory of Computing (Seattle, WA, 1989). MR 1186884, DOI 10.1016/0022-0000(92)90047-M
- 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, North-Holland, Amsterdam, 1975, pp. 91–108. MR 0416986
- Saugata Basu, Richard Pollack, and Marie-Franç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, “Integer-making” theorems, Discrete Appl. Math. 3 (1981), no. 1, 1–8. MR 604260, DOI 10.1016/0166-218X(81)90022-6
- 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 York-London, 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/0022-4049(90)90159-F
- 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/0304-3975(83)90002-6
- 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/S0894-0347-1988-0944576-7
- D. G. Larman, C. A. Rogers, and J. J. Seidel, On two-distance 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/S0002-9939-1964-0161339-9
- Hugh L. Montgomery, Topics in multiplicative number theory, Lecture Notes in Mathematics, Vol. 227, Springer-Verlag, Berlin-New York, 1971. MR 0337847, DOI 10.1007/BFb0060851
- K. A. Hirsch, On skew-groups, Proc. London Math. Soc. 45 (1939), 357–368. MR 0000036, DOI 10.1112/plms/s2-45.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. Ray-Chaudhuri 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/S0002-9947-1968-0226281-1
- Ingo Wegener, The complexity of Boolean functions, Wiley-Teubner 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, 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. - © Copyright 2001 American Mathematical Society
- 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
- DOI: https://doi.org/10.1090/S0894-0347-01-00367-8
- MathSciNet review: 1824986