Computing the torsion points of a variety defined by lacunary polynomials (Q2894522)

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\) a torsion point of \(\big(\overline{\mathbb{Q}}^\times\big)^n.\)NEWLINENEWLINEFrom the algorithm described in the Theorem, as a corollary the author gets a bound on the number of torsion cosets (the parameter \(t\) above) in terms of \(N,\,n\) and \(k\).