Skip to Main content Skip to Navigation
Conference papers

Computing Small Certificates of Inconsistency of Quadratic Fewnomial Systems

Jean-Charles Faugère 1 Pierre-Jean Spaenlehauer 2 Jules Svartz 3, 1
1 PolSys - Polynomial Systems
Inria de Paris, LIP6 - Laboratoire d'Informatique de Paris 6
2 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : Bézout 's theorem states that dense generic systems of n multivariate quadratic equations in n variables have 2 n solutions over algebraically closed fields. When only a small subset M of monomials appear in the equations (fewnomial systems), the number of solutions may decrease dramatically. We focus in this work on subsets of quadratic monomials M such that generic systems with support M do not admit any solution at all. For these systems, Hilbert's Nullstellensatz ensures the existence of algebraic certificates of inconsistency. However, up to our knowledge all known bounds on the sizes of such certificates —including those which take into account the Newton polytopes of the polynomials— are exponential in n. Our main results show that if the inequality 2|M| − 2n ≤ √ 1 + 8ν − 1 holds for a quadratic fewnomial system – where ν is the matching number of a graph associated with M, and |M| is the cardinality of M – then there exists generically a certificate of inconsistency of linear size (measured as the number of coefficients in the ground field K). Moreover this certificate can be computed within a polynomial number of arithmetic operations. Next, we evaluate how often this inequality holds, and we give evidence that the probability that the inequality is satisfied depends strongly on the number of squares. More precisely, we show that if M is picked uniformly at random among the subsets of n + k + 1 quadratic monomials containing at least Ω(n 1/2+ε) squares, then the probability that the inequality holds tends to 1 as n grows. Interestingly, this phenomenon is related with the matching number of random graphs in the Erdös-Renyi model. Finally, we provide experimental results showing that certificates in inconsistency can be computed for systems with more than 10000 variables and equations.
Document type :
Conference papers
Complete list of metadata

Cited literature [36 references]  Display  Hide  Download
Contributor : Pierre-Jean Spaenlehauer Connect in order to contact the contributor
Submitted on : Wednesday, May 18, 2016 - 5:37:21 PM
Last modification on : Saturday, October 16, 2021 - 11:26:10 AM
Long-term archiving on: : Friday, August 19, 2016 - 10:25:41 AM


Files produced by the author(s)





Jean-Charles Faugère, Pierre-Jean Spaenlehauer, Jules Svartz. Computing Small Certificates of Inconsistency of Quadratic Fewnomial Systems. International Symposium on Symbolic and Algebraic Computation (ISSAC 2016), Jul 2016, Waterloo, Canada. pp.223-230, ⟨10.1145/2930889.2930927⟩. ⟨hal-01314651⟩



Record views


Files downloads