Overdetermined systems of sparse polynomial equations

DOI10.1007/S10208-014-9207-YzbMATH Open1310.11119arXiv1307.5788OpenAlexW2065658438MaRDI QIDQ2340503FDOQ2340503

Louis Leroux, Francesco Amoroso, Martín Sombra

Publication date: 20 April 2015

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Abstract: We show that, for a system of univariate polynomials given in sparse encoding, we can compute a single polynomial defining the same zero set, in time quasi-linear in the logarithm of the degree. In particular, it is possible to determine whether such a system of polynomials does have a zero in time quasi-linear in the logarithm of the degree. The underlying algorithm relies on a result of Bombieri and Zannier on multiplicatively dependent points in subvarieties of an algebraic torus. We also present the following conditional partial extension to the higher dimensional setting. Assume that the effective Zilber conjecture holds. Then, for a system of multivariate polynomials given in sparse encoding, we can compute a finite collection of complete intersections outside hypersurfaces that defines the same zero set, in time quasi-linear in the logarithm of the degree.

Full work available at URL: https://arxiv.org/abs/1307.5788

Recommendations

• Overdetermined Systems of Linear Equations
• Affine solution sets of sparse polynomial systems
• Positive solutions of sparse polynomial systems
• A Polyhedral Method for Solving Sparse Polynomial Systems
• Decomposable sparse polynomial systems
• Systems of linear equations with dense univariate polynomial coefficients
• Efficient algorithms for solving overdefined systems of multivariate polynomial equations
• Solving systems of linear algebraic equations of a special kind with sparse polynomial and numerical coefficients
• Overdetermined systems of equations on toric, spherical, and other algebraic varieties
• Elimination for generic sparse polynomial systems

zbMATH Keywords

sparse polynomialalgebraic torusoverdetermined system of equationsunlikely intersections

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Solving polynomial systems; resultants (13P15)

Cites Work

• Some problems of unlikely intersections in arithmetic and geometry. With appendixes by David Masser
• Computing the torsion points of a variety defined by lacunary polynomials
• Title not available (Why is that?)
• Lecture Notes on Diophantine Analysis
• Title not available (Why is that?)
• Exponential diophantine equations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Anomalous Subvarieties—Structure Theorems and Applications
• Title not available (Why is that?)
• Algebraic curves and multiplicative equations.
• On the Bounded Height Conjecture
• Relations de d\'ependance et intersections exceptionnelles (Dependence relations and exceptional intersections)
• EXPONENTIAL SUMS EQUATIONS AND THE SCHANUEL CONJECTURE
• On the reducibility of polynomials and in particular of trinomials
• Sparse complex polynomials and polynomial reducibility
• The intersection of a curve with a union of translated codimension-two subgroups in a power of an elliptic curve
• Title not available (Why is that?)
• Irreducibility and greatest common divisor algorithms for sparse polynomials
• Title not available (Why is that?)

Cited In (6)

• Computing the multilinear factors of lacunary polynomials without heights
• Positive solutions of sparse polynomial systems
• Affine solution sets of sparse polynomial systems
• Overdetermined systems of equations on toric, spherical, and other algebraic varieties
• Global residues for sparse polynomial systems
• Unlikely intersections and multiple roots of sparse polynomials

This page was built for publication: Overdetermined systems of sparse polynomial equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2340503)