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

Rónyai, Lajos¹ ; Babai, László² ; Ganapathy, Murali²

¹ Computer and Automation Research Institute, Hungarian Academy of Sciences, H-1111 Budapest, Lágymányosi u. 11, Hungary
² Department of Computer Science, University of Chicago, Chicago, Illinois 60637

Journal of the American Mathematical Society, Tome 14 (2001) no. 3, pp. 717-735

Résumé

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.

Détail

DOI : 10.1090/S0894-0347-01-00367-8

Bibliographie

[1] Alon, Noga Ramsey graphs cannot be defined by real polynomials J. Graph Theory 1990 651 661

[2] Alon, Noga Tools from higher algebra 1995 1749 1783

[3] Babai, Lã¡Szlã³, Gã¡L, Anna, Wigderson, Avi Superpolynomial lower bounds for monotone span programs Combinatorica 1999 301 319

[4] Babai, Lã¡Szlã³, Nisan, Noam, Szegedy, Mã¡Riã³ Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs J. Comput. System Sci. 1992 204 232

[5] Baranyai, Zs. On the factorization of the complete uniform hypergraph 1975 91 108

[6] Basu, Saugata, Pollack, Richard, Roy, Marie-Franã§Oise On the number of cells defined by a family of polynomials on a variety Mathematika 1996 120 126

[7] Beck, Jã³Zsef, Fiala, Tibor “Integer-making” theorems Discrete Appl. Math. 1981 1 8

[8] Beimel, Amos, Gã¡L, Anna, Paterson, Mike Lower bounds for monotone span programs Comput. Complexity 1996/97 29 45

[9] Ward, Morgan, Dilworth, R. P. The lattice theory of ova Ann. of Math. (2) 1939 600 608

[10] Brownawell, W. Dale Bounds for the degrees in the Nullstellensatz Ann. of Math. (2) 1987 577 591

[11] Collar, A. R. On the reciprocation of certain matrices Proc. Roy. Soc. Edinburgh 1939 195 206

[12] Erdå‘S, Paul, Spencer, Joel Probabilistic methods in combinatorics 1974 106

[13] Fitchas, Noaã¯, Galligo, Andrã©, Morgenstern, Jacques Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields J. Pure Appl. Algebra 1990 1 14

[14] Frankl, P., Wilson, R. M. Intersection theorems with geometric consequences Combinatorica 1981 357 368

[15] Maclane, Saunders, Schilling, O. F. G. Infinite number fields with Noether ideal theories Amer. J. Math. 1939 771 782

[16] Graham, S. W., Ringrose, C. J. Lower bounds for least quadratic nonresidues 1990 269 309

[17] Heintz, Joos Definability and fast quantifier elimination in algebraically closed fields Theoret. Comput. Sci. 1983 239 277

[18] Karchmer, M., Wigderson, A. On span programs 1993 102 111

[19] Kollã¡R, Jã¡Nos Sharp effective Nullstellensatz J. Amer. Math. Soc. 1988 963 975

[20] Larman, D. G., Rogers, C. A., Seidel, J. J. On two-distance sets in Euclidean space Bull. London Math. Soc. 1977 261 267

[21] Van Lint, J. H., Wilson, R. M. A course in combinatorics 1992

[22] Lovã¡Sz, L. Flats in matroids and geometric graphs 1977 45 86

[23] Milnor, J. On the Betti numbers of real varieties Proc. Amer. Math. Soc. 1964 275 280

[24] Montgomery, Hugh L. Topics in multiplicative number theory 1971

[25] Hirsch, K. A. On skew-groups Proc. London Math. Soc. 1939 357 368

[26] Everett, C. J., Jr. Annihilator ideals and representation iteration for abstract rings Duke Math. J. 1939 623 627

[27] Everett, C. J., Jr. Annihilator ideals and representation iteration for abstract rings Duke Math. J. 1939 623 627

[28] Pudlã¡K, P., Rã¶Dl, V. A combinatorial approach to complexity Combinatorica 1992 221 226

[29] Ray-Chaudhuri, Dijen K., Wilson, Richard M. On 𝑡-designs Osaka Math. J. 1975 737 744

[30] Maclane, Saunders, Schilling, O. F. G. Infinite number fields with Noether ideal theories Amer. J. Math. 1939 771 782

[31] Thom, Ren㩠Sur l’homologie des variétés algébriques réelles 1965 255 265

[32] Warren, Hugh E. Lower bounds for approximation by nonlinear manifolds Trans. Amer. Math. Soc. 1968 167 178

[33] Wegener, Ingo The complexity of Boolean functions 1987