On the number of zero-patterns of a sequence of polynomials
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)\). Let \(d_i\) be the degree of \(f_i\). The authors obtain the following results: \[ Z_F(f) \leq {\binom{n+ \sum_{i=1}^m d_i}{n}}; \] If \(d_i \leq 1\) then \(Z_F(f) \leq \sum_{j=0}^n {\binom{m}{j}};\) If \(d=\max_i d_i \geq 1\) and \(m \geq n\) then \(Z_F(f) \leq {\binom{md-(d-2)n}{n}}.\) The 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\) The 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.
- On the zeros of sequences of polynomials
- scientific article; zbMATH DE number 3992072
- On the Zeros of a Special Sequence of Polynomials
- On the zeros of some combinatorial polynomials
- On the number of distinct zeros of a polynomial
- On the zeros of some polynomials with combinatorial coefficients
- Polynomial sequences with prescribed power sums of zeros
- scientific article; zbMATH DE number 575909
- Counting polynomials with zeros of given multiplicities in finite fields
- Counting polynomials with distinct zeros in finite fields
- ``Integer-making theorems
- A combinatorial approach to complexity
- A Note on Fisher's Inequality for Balanced Incomplete Block Designs
- A theorem on flows in networks
- Bounds for the degrees in the Nullstellensatz
- Combinatorial Properties of Matrices of Zeros and Ones
- Definability and fast quantifier elimination in algebraically closed fields
- scientific article; zbMATH DE number 4012495 (Why is no real title available?)
- scientific article; zbMATH DE number 51878 (Why is no real title available?)
- scientific article; zbMATH DE number 3478938 (Why is no real title available?)
- scientific article; zbMATH DE number 3482343 (Why is no real title available?)
- scientific article; zbMATH DE number 3561367 (Why is no real title available?)
- scientific article; zbMATH DE number 863501 (Why is no real title available?)
- scientific article; zbMATH DE number 3223507 (Why is no real title available?)
- Intersection theorems with geometric consequences
- Lower Bounds for Approximation by Nonlinear Manifolds
- Lower bounds for monotone span programs
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- On t-designs
- On the Betti Numbers of Real Varieties
- On the number of cells defined by a family of polynomials on a variety
- On Two-Distance Sets in Euclidean Space
- Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
- Ramsey graphs cannot be defined by real polynomials
- Repeated communication and Ramsey graphs
- Sharp Effective Nullstellensatz
- Some remarks on the theory of graphs
- Superpolynomial lower bounds for monotone span programs
- Topics in multiplicative number theory
- On the hardness of approximating max-satisfy
- Sequences of polynomials whose zeros lie on fixed lemniscates
- Zero-patterns of polynomials and Newton polytopes.
- VC density of definable families over valued fields
- On the enumeration of polynomials with prescribed factorization pattern
- On the asymptotic proportion of connected matroids
- The minrank of random graphs over arbitrary fields
- The (minimum) rank of typical fooling-set matrices
- Two notions of unit distance graphs
- Counting dope matrices
- On graphs of minimum skew rank 4
- ZERO SETS OF ENTIRE GENERATING FUNCTIONS OF PÓLYA FREQUENCY SEQUENCES OF FINITE ORDER
- On Linear Secret Sharing for Connectivity in Directed Graphs
- scientific article; zbMATH DE number 4059787 (Why is no real title available?)
- On the number of biased graphs
- On zeros of a polynomial in a finite grid
- Counting problems and ranks of matrices
- Zeroes of polynomials on definable hypersurfaces: pathologies exist, but they are rare
- Ramsey properties of algebraic graphs and hypergraphs
- The Multivariate Schwartz--Zippel Lemma
- On the complexity of computing a random Boolean function over the reals
- Generic classification and asymptotic enumeration of dope matrices
- Lower bounds for comparison based evolution strategies using VC-dimension and sign patterns
- Induced subgraph density. VI: Bounded VC-dimension
- Simplified PIR and CDS protocols and improved linear secret-sharing schemes
- Polynomial secret sharing schemes and algebraic matroids
- Most \(q\)-matroids are not representable
- On the construction of a family of transversal subspaces over finite fields
- Expected values of parameters associated with the minimum rank of a graph
- An asymptotically tight bound on the number of semi-algebraically connected components of realizable sign conditions
This page was built for publication: On the number of zero-patterns of a sequence of polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2719034)
