Computing the torsion points of a variety defined by lacunary polynomials

Leroux, Louis

doi:10.1090/S0025-5718-2011-02548-2

Computing the torsion points of a variety defined by lacunary polynomials
HTML articles powered by AMS MathViewer

by Louis Leroux PDF

Math. Comp. 81 (2012), 1587-1607 Request permission

Abstract:

We present an algorithm for computing the set of torsion points satisfying a given system of multivariate polynomial equations. Its complexity is quasilinear in the logarithm of the degree and in the height of the input equations but exponential in their number of variables and nonzero terms.

References

I. Aliev, C. Smyth, Solving algebraic equations in roots of unity, preprint, (2008), arXiv:0704.1747v3.
Francesco Amoroso and Sinnou David, Points de petite hauteur sur une sous-variété d’un tore, Compos. Math. 142 (2006), no. 3, 551–562 (French, with English and French summaries). MR 2231192, DOI 10.1112/S0010437X06002004
F. Amoroso, E. Viada, Small points on subvarieties of tori, Duke Mathematical Journal, To appear.
F. Beukers and C. J. Smyth, Cyclotomic points on curves, Number theory for the millennium, I (Urbana, IL, 2000) A K Peters, Natick, MA, 2002, pp. 67–85. MR 1956219
E. Bombieri and U. Zannier, Algebraic points on subvarieties of $\mathbf G^n_m$, Internat. Math. Res. Notices 7 (1995), 333–347. MR 1350686, DOI 10.1155/S1073792895000250
Qi Cheng, Sergey P. Tarasov, and Mikhail N. Vyalyi, Efficient algorithms for sparse cyclotomic integer zero testing, Theory Comput. Syst. 46 (2010), no. 1, 120–142. MR 2574648, DOI 10.1007/s00224-008-9158-2
J. H. Conway and A. J. Jones, Trigonometric Diophantine equations (On vanishing sums of roots of unity), Acta Arith. 30 (1976), no. 3, 229–240. MR 422149, DOI 10.4064/aa-30-3-229-240
Sinnou David and Patrice Philippon, Minorations des hauteurs normalisées des sous-variétés des puissances des courbes elliptiques, Int. Math. Res. Pap. IMRP 3 (2007), Art. ID rpm006, 113 (French). MR 2355454
Michael Filaseta, Andrew Granville, and Andrzej Schinzel, Irreducibility and greatest common divisor algorithms for sparse polynomials, Number theory and polynomials, London Math. Soc. Lecture Note Ser., vol. 352, Cambridge Univ. Press, Cambridge, 2008, pp. 155–176. MR 2428521, DOI 10.1017/CBO9780511721274.012
Michael Filaseta and Andrzej Schinzel, On testing the divisibility of lacunary polynomials by cyclotomic polynomials, Math. Comp. 73 (2004), no. 246, 957–965. MR 2031418, DOI 10.1090/S0025-5718-03-01589-8
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757
G. Hajós, Solution of Problem 41, (Hungarian), Mat. Lapok 4, (1953), 40-41.
Donald E. Knuth, The analysis of algorithms, Actes du Congrès International des Mathématiciens (Nice, 1970) Gauthier-Villars, Paris, 1971, pp. 269–274. MR 0423865
G. Labahn and A. Storjohann, Asymptotically fast computation of Hermite normal forms of integer matrices, In Proc. Internat. Symp. on Symbolic and Algebraic Computation: ISSAC ’96, (1996), 259-266.
Serge Lang, Fundamentals of Diophantine geometry, Springer-Verlag, New York, 1983. MR 715605, DOI 10.1007/978-1-4757-1810-2
Michel Laurent, Équations diophantiennes exponentielles, Invent. Math. 78 (1984), no. 2, 299–327 (French). MR 767195, DOI 10.1007/BF01388597
L. Leroux, Recherche d’un point de torsion dans une courbe définie par un polynôme lacunaire, Prépublication Université de Caen (France), Déc 2008, downloadable from http://hal.archives-ouvertes.fr/docs/00/35/25/64/PDF/PointsDeTorsion.pdf.
David A. Plaisted, New NP-hard and NP-complete polynomial and integer divisibility problems, Theoret. Comput. Sci. 31 (1984), no. 1-2, 125–138. MR 752098, DOI 10.1016/0304-3975(84)90130-0
Bjorn Poonen and Michael Rubinstein, The number of intersection points made by the diagonals of a regular polygon, SIAM J. Discrete Math. 11 (1998), no. 1, 135–156. MR 1612877, DOI 10.1137/S0895480195281246
G. Rémond, Sur les sous-variétés des tores, Comp. Math., (2002), 337-366.
J. Maurice Rojas, Efficiently detecting torsion points and subtori, Algebra, geometry and their interactions, Contemp. Math., vol. 448, Amer. Math. Soc., Providence, RI, 2007, pp. 215–235. MR 2389244, DOI 10.1090/conm/448/08667
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
Wolfgang M. Ruppert, Solving algebraic equations in roots of unity, J. Reine Angew. Math. 435 (1993), 119–156. MR 1203913, DOI 10.1515/crll.1993.435.119
Wolfgang M. Schmidt, Heights of points on subvarieties of $\textbf {G}^n_m$, Number theory (Paris, 1993–1994) London Math. Soc. Lecture Note Ser., vol. 235, Cambridge Univ. Press, Cambridge, 1996, pp. 157–187. MR 1628798, DOI 10.1017/CBO9780511662003.008
A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
Umberto Zannier, Lecture notes on Diophantine analysis, Appunti. Scuola Normale Superiore di Pisa (Nuova Serie) [Lecture Notes. Scuola Normale Superiore di Pisa (New Series)], vol. 8, Edizioni della Normale, Pisa, 2009. With an appendix by Francesco Amoroso. MR 2517762