On the number of zero-patterns of a sequence of polynomials (Q2719034)

Let \(f=(f_1, f_2, \ldots, f_m)\) be a sequence of polynomials of degrees \(\leq d\) in \(n\) variables over a field \(F\). The zero-pattern of \(f\) at a point \(u \in F^n\) is the set of those \(i\) \((1 \leq i \leq m)\) for which \(f_i(u) =0;\) the point \(u\) is called the witness of the zero-pattern. The number of zero-patterns of \(f\) as \(u\) ranges over \(F^n\) is denoted by \(Z_F(f)\). NEWLINENEWLINELet \(d_i\) be the degree of \(f_i\). The authors obtain the following results: NEWLINE\[CARRIAGE_RETURNNEWLINEZ_F(f) \leq {\binom{n+ \sum_{i=1}^m d_i}{n}};CARRIAGE_RETURNNEWLINE\]NEWLINEIf \(d_i \leq 1\) then \(Z_F(f) \leq \sum_{j=0}^n {\binom{m}{j}};\)NEWLINENEWLINEIf \(d=\max_i d_i \geq 1\) and \(m \geq n\) then \(Z_F(f) \leq {\binom{md-(d-2)n}{n}}.\)NEWLINENEWLINEThe bounds can be summarized by the expression \(Z_F(f) \leq \left( \frac{\text{e} m d}{n} \right)^n,\) which is optimal within a factor of \((7.25)^n\) NEWLINENEWLINEThe elegant proof is a half-page long argument based on elementary linear algebra. The remainder of the paper is devoted to nontrivial applications from quantifier elimination, projective dimension graphs and Ramsey properties of matrices.