Computing the torsion points of a variety defined by lacunary polynomials
type: Item
instance of: scholarly article
title: Computing the torsion points of a variety defined by lacunary polynomials
zbMATH Open document ID: 1263.11115
DOI: 10.1090/S0025-5718-2011-02548-2
author: Louis Leroux
published in: Mathematics of Computation
publication date: 2012-06-29T00:00:00Z
full work available at URL: https://arxiv.org/abs/0911.2594
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 12Y05
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 6051350
zbMATH Keywords: algorithm
zbMATH Keywords: torsion points
zbMATH Keywords: algebraic torus
zbMATH Keywords: roots of unity
MaRDI profile type: Publication
arXiv ID: 0911.2594
cites work: Solving algebraic equations in roots of unity
cites work: Points de petite hauteur sur une sous-variété d'un tore
cites work: Small points on rational subvarieties of tori
cites work: Q4432295
cites work: Q4853852
cites work: Efficient algorithms for sparse cyclotomic integer zero testing
cites work: Trigonometric diophantine equations (On vanishing sums of roots of unity)
cites work: Minorations des hauteurs normalisees des sous-varietes des puissances des courbes elliptiques
cites work: Irreducibility and greatest common divisor algorithms for sparse polynomials
cites work: On testing the divisibility of lacunary polynomials by cyclotomic polynomials
cites work: Q4406533
cites work: Q4766043
cites work: Q4227351
cites work: Q3309989
cites work: Exponential diophantine equations
cites work: New NP-hard and NP-complete polynomial and integer divisibility problems
cites work: The Number of Intersection Points Made by the Diagonals of a Regular Polygon
cites work: Q4797991
cites work: Q5447351
cites work: Approximate formulas for some functions of prime numbers
cites work: Solving algebraic equations in roots of unity.
cites work: Q4233884
cites work: Fast multiplication of large numbers
cites work: Lecture Notes on Diophantine Analysis
OpenAlex ID: W2056622035
review text: In this article, the following problem is considered: given \(F_1,\ldots, F_k\in\mathbb{Z}[X_1,\ldots, X_n],\) compute the solutions of the system of equations NEWLINE\[NEWLINE F_1(X_1,\ldots, X_n)=\ldots=F_k(X_1,\ldots, X_n)=0 NEWLINE\]NEWLINE in roots of unity. This problem appears in a lot of applications with geometric background. For instance, when solving trigonometric equations.NEWLINENEWLINEThe problem has been solved for \(n=1\) in [\textit{M. Filaseta, A. Granville} and \textit{A. Schinzel}, Lond. Math. Soc. Lect. Note Ser. 352, 155--176 (2008; Zbl 1270.11129)], the complexity of which is quasilinear in the logarithm of the degree of the input polynomials. The main challenge for \(n\geq 2,\) is that the system above may have an infinite number of solutions in roots of unity, so another description of the sets of solutions may be needed if one wants to develop an efficient algorithm. The main result of this article is the following:NEWLINENEWLINENEWLINE\textbf{Theorem:} There exists a deterministic algorithm which has the following property: \newline let \(F_1,\ldots, F_k\in\mathbb{Z}[X_1,\ldots, X_n]\) be polynomials given by their sparse encoding, and \(V\subset \big(\overline{\mathbb{Q}}\big)^n\) the variety defined by these polynomials. The algorithm computes a family of torsion cosets \(B_1,\ldots, B_t\) such that NEWLINE\[NEWLINE\bigcup_{i=1}^tB_i=\overline{V}_{\text{tors}}, NEWLINE\]NEWLINE with at most \(\mathcal{O}\left(N^{nkN}\big(M(\log\,d))\log\log(d)+h)\big)\right)\) bit operations, where \(N\) denotes the maximum number of nonzero terms in each \(F_i,\) and \(d\) (resp. \(h\)) is an upper bound for their total degree (resp. height).NEWLINENEWLINENEWLINEHere, \(\overline{V}_{\text{tors}}\) is the subset of \(V\) of those points which are coordinate-wise roots of unity, and a \textit{torsion coset} of this space is a coset of the form \(\eta\,H,\) with \(H\) being an algebraic subgroup of \(\big(\overline{\mathbb{Q}}^\times\big)^n\), and \(\eta\…
reviewed by: Carlos D'Andrea
description: scientific article; zbMATH DE number 6051350