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
Additional Information
- Louis Leroux
- Affiliation: Laboratoire de Mathematiques Nicolas Oresme, Univerite de Caen BP 5186, 14032 Caen cedex, France
- Email: louis.leroux@math.unicaen.fr
- Received by editor(s): December 3, 2009
- Received by editor(s) in revised form: March 21, 2011
- Published electronically: October 21, 2011
- Additional Notes: The author was partially supported by the CNRS PICS “Properties of heights of arithmetic varieties”, (2009-2011).
- © Copyright 2011
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 81 (2012), 1587-1607
- MSC (2010): Primary 11Y16; Secondary 12Y05, 68W30
- DOI: https://doi.org/10.1090/S0025-5718-2011-02548-2
- MathSciNet review: 2904592