|
|||||
|
|
On the number of zero-patterns of a sequence of polynomials |
|
| Authors: | Lajos Ró nyai Lá szló Babai Murali K. Ganapathy |
| Affiliation: | 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 ; Department of Computer Science, University of Chicago, Chicago, Illinois 60637 |
| Abstract: | Let for 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 |
| 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 |
| 点击此处可从《Journal of the American Mathematical Society》浏览原始摘要信息 | |
| 点击此处可从《Journal of the American Mathematical Society》下载全文 | |
be a sequence of polynomials of degree 
in 
variables 
over a field 
. The zero-pattern of 
at 
is the set of those 
( 
) for which 
. Let 
denote the number of zero-patterns of 
as 
ranges over 
. We prove that 
for 
and 
. For 
, these bounds are optimal within a factor of 
. The bound (
) improves the bound 
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'. 
, most graphs with 
vertices have projective dimension 
(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.