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
LIP6 - Laboratoire d'Informatique de Paris 6, Inria de Paris
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.
Type de document :
Communication dans un congrès
International Symposium on Symbolic and Algebraic Computation (ISSAC 2016), Jul 2016, Waterloo, Canada. ACM, Proceedings of ISSAC 2016, pp.223-230, 〈10.1145/2930889.2930927〉
Liste complète des métadonnées

Littérature citée [36 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01314651
Contributeur : Pierre-Jean Spaenlehauer <>
Soumis le : mercredi 18 mai 2016 - 17:37:21
Dernière modification le : lundi 29 mai 2017 - 14:22:44
Document(s) archivé(s) le : vendredi 19 août 2016 - 10:25:41

Fichiers

fewnomials.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Copyright (Tous droits réservés)

Identifiants

Collections

Citation

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. ACM, Proceedings of ISSAC 2016, pp.223-230, 〈10.1145/2930889.2930927〉. 〈hal-01314651〉

Partager

Métriques

Consultations de la notice

287

Téléchargements de fichiers

87