论文标题
二次多项式的广义sylvester-gallai型定理
A generalized Sylvester-Gallai type theorem for quadratic polynomials
论文作者
论文摘要
在这项工作中，我们证明了二次多项式的Sylvester-Gallai定理的一个版本，它使我们更近一步，获得了确定性的多项式时间算法，用于测试$σ^{[3]}πσπ^{[2]} $ Circuits的$σ^{[3]}的zeroness。具体而言，我们证明，如果一组有限的二次多项式$ \ nathcal {q} $满足，每两个多项式$ q_1，q_2 \ in \ in \ nathcal {q} $ in \ natcal {q} $都有一个子集合$ \ nathcal $ \ nthcal {k} \ supset \ supcal \ mathc $ qu} \ Mathcal {k} $以及每当$ q_1 $和$ q_2 $消失时，$ \ prod_ {i \ in \ Mathcal {k}} q_i $ nishes vanishes nishes nishes nishes nishes nishes nishes nishes nishes in polynomials的线性跨度，然后在$ \ nathcal {q} $中的polynomials的线性跨度。这扩展了较早的结果[shpilka19]，该结果在$ | \ Mathcal {k} |时显示了类似的结论。 = 1 $。 我们证明的重要技术步骤是一个定理，将二次多项式产物的所有可能情况分类为当其他两个二次多项式消失时消失。即，当产物处于理想的自由基时，这两个四边形会产生。此步骤扩展了[shpilka19]的结果，该结果研究了一个二次多项式在其他两个二次学的根本上。
In this work we prove a version of the Sylvester-Gallai theorem for quadratic polynomials that takes us one step closer to obtaining a deterministic polynomial time algorithm for testing zeroness of $Σ^{[3]}ΠΣΠ^{[2]}$ circuits. Specifically, we prove that if a finite set of irreducible quadratic polynomials $\mathcal{Q}$ satisfy that for every two polynomials $Q_1,Q_2\in \mathcal{Q}$ there is a subset $\mathcal{K}\subset \mathcal{Q}$, such that $Q_1,Q_2 \notin \mathcal{K}$ and whenever $Q_1$ and $Q_2$ vanish then also $\prod_{i\in \mathcal{K}} Q_i$ vanishes, then the linear span of the polynomials in $\mathcal{Q}$ has dimension $O(1)$. This extends the earlier result [Shpilka19] that showed a similar conclusion when $|\mathcal{K}| = 1$. An important technical step in our proof is a theorem classifying all the possible cases in which a product of quadratic polynomials can vanish when two other quadratic polynomials vanish. I.e., when the product is in the radical of the ideal generates by the two quadratics. This step extends a result from [Shpilka19]that studied the case when one quadratic polynomial is in the radical of two other quadratics.
