Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 50 min ago
Peer-reviewedCC BY 4.0Forum of Mathematics, Sigma

Bounds on the realizations of zero-nonzero patterns and sign conditions of polynomials restricted to varieties and applications

  • Saugata Basu1
  • Laxmi Parida2
  1. 1Purdue University
  2. 2IBM T. J. Watson Research Center
Open at sourceDOICite

Abstract

We obtain upper bounds, independent of the ambient dimension, for the number of realizable zero-nonzero patterns and (over ordered fields) sign conditions of a finite family of polynomials P 𝒫 script upper P restricted to an algebraic subset V of affine or projective space. The bounds depend only on card ( P ) card(𝒫) card left parenthesis script upper P right parenthesis and the degrees of the polynomials in P 𝒫 script upper P , together with deg ⁡ ( V ) deg (V) degree left parenthesis upper V right parenthesis and dim ⁡ ( V ) dim (V) dimension left parenthesis upper V right parenthesis , and not on the dimension of the space in which V is embedded. This feature is particularly useful when V has small intrinsic dimension but is presented in a very high-dimensional ambient space.

We describe several applications. First, we extend existing results on bounding the ε $\varepsilon $ epsilon -entropy of real algebraic varieties. Second, we derive lower bounds (in terms of the number of connected components) for membership testing in semi-algebraic sets in the algebraic computation tree model. Finally, motivated by quantum complexity theory, we introduce additive and multiplicative notions of relative rank in finite-dimensional vector spaces and algebras with respect to a fixed algebraic subset, generalizing the classical notion of tensor rank. We prove a general lower bound on the maximum relative rank of finite subsets with respect to algebraic sets of bounded degree and dimension that is again independent of the ambient dimension. As an illustration, we obtain a quantum analog of Shannon’s classical lower bound. We prove that if Δ n Δ n normal upper Delta Subscript n is an algebraic family of allowed gates with dim ⁡ Δ n = poly ( n ) , log ⁡ deg ⁡ Δ n = poly ( n ) , dim Δn= poly(n), logdegΔn= poly(n),

then some Boolean functions require 2 n / poly ( n ) 2n/poly(n) 2 Superscript n Baseline divided by poly left parenthesis n right parenthesis gates from Δ n Δ n normal upper Delta Subscript n , even when individual gates in Δ n Δ n normal upper Delta Subscript n may be highly nonlocal.

Related

  1. Irreducible polynomials with restricted digits in base b(T)
    Juan Arévalo, Matilde Lalín
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  2. Polynomials with restricted support and maximal zeros on a finite Cartesian set
    Dipak K. Bhunia, Eduardo Camps-Moreno, Ignacio GarcÍa-Marco +2
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  3. Hyperbolicity and fundamental groups of complex quasi-projective varieties (III): applications
    Benoit Cadorel, Ya Deng, Katsutoshi Yamanoi
    HALPreprintPublisher termsFull textAlgebra & number theoryAnalysis & PDEsHAL
  4. Marchal-type lemmas for the restricted (N+1)-body problem with their applications
    Kuo-chang Chen, Guowei Yu
    arXivPreprintarXiv licenceFull textDynamical systemsarXiv
  5. Bilinear generating functions of the multivariable Al-Salam-Carlitz polynomials and applications
    Qi Chen, Xinrong Ma, Jin Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@article{basu2026bounds,
  title = {{Bounds on the realizations of zero-nonzero patterns and sign conditions of polynomials restricted to varieties and applications}},
  author = {Saugata Basu and Laxmi Parida},
  journal = {Forum of Mathematics, Sigma},
  year = {2026},
  month = oct,
  doi = {10.1017/fms.2026.10290},
  url = {https://www.cambridge.org/core/product/identifier/S2050509426102904/type/journal_article},
  note = {CC BY 4.0},
}
RIS
TY  - JOUR
TI  - Bounds on the realizations of zero-nonzero patterns and sign conditions of polynomials restricted to varieties and applications
AU  - Saugata Basu
AU  - Laxmi Parida
PY  - 2026
DA  - 2026/10/20
JO  - Forum of Mathematics, Sigma
DO  - 10.1017/fms.2026.10290
UR  - https://www.cambridge.org/core/product/identifier/S2050509426102904/type/journal_article
AB  - We obtain upper bounds, independent of the ambient dimension, for the number of realizable zero-nonzero patterns and (over ordered fields) sign conditions of a finite family of polynomials P 𝒫 script upper P restricted to an algebraic subset V of affine or projective space. The bounds depend only on card ( P ) card(𝒫) card left parenthesis script upper P right parenthesis and the degrees of the polynomials in P 𝒫 script upper P , together with deg ⁡ ( V ) deg (V) degree left parenthesis upper V right parenthesis and dim ⁡ ( V ) dim (V) dimension left parenthesis upper V right parenthesis , and not on the dimension of the space in which V is embedded. This feature is particularly useful when V has small intrinsic dimension but is presented in a very high-dimensional ambient space.  We describe several applications. First, we extend existing results on bounding the ε $\varepsilon $ epsilon -entropy of real algebraic varieties. Second, we derive lower bounds (in terms of the number of connected components) for membership testing in semi-algebraic sets in the algebraic computation tree model. Finally, motivated by quantum complexity theory, we introduce additive and multiplicative notions of relative rank in finite-dimensional vector spaces and algebras with respect to a fixed algebraic subset, generalizing the classical notion of tensor rank. We prove a general lower bound on the maximum relative rank of finite subsets with respect to algebraic sets of bounded degree and dimension that is again independent of the ambient dimension. As an illustration, we obtain a quantum analog of Shannon’s classical lower bound. We prove that if Δ n Δ _n normal upper Delta Subscript n is an algebraic family of allowed gates with dim ⁡ Δ n = poly ( n ) , log ⁡ deg ⁡ Δ n = poly ( n ) , dim Δ_n= poly(n), logdegΔ_n= poly(n),  then some Boolean functions require 2 n / poly ( n ) 2^n/poly(n) 2 Superscript n Baseline divided by poly left parenthesis n right parenthesis gates from Δ n Δ _n normal upper Delta Subscript n , even when individual gates in Δ n Δ _n normal upper Delta Subscript n may be highly nonlocal.
SN  - 2050-5094
ER  -