Mathematics of Computation

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Computing the torsion points of a variety defined by lacunary polynomials

Author: Louis Leroux
Journal: Math. Comp. 81 (2012), 1587-1607
MSC (2010): Primary 11Y16; Secondary 12Y05, 68W30
Posted: October 21, 2011
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

[AS08] I. Aliev, C. Smyth, Solving algebraic equations in roots of unity, preprint, (2008), arXiv:0704.1747v3.
[AD06] 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 (2007g:11073), http://dx.doi.org/10.1112/S0010437X06002004
[AV09] F. Amoroso, E. Viada, Small points on subvarieties of tori, Duke Mathematical Journal, To appear.
[BS02] 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 (2004b:11029)
[BZ95] E. Bombieri and U. Zannier, Algebraic points on subvarieties of 𝐆ⁿ_{𝐦}, Internat. Math. Res. Notices 7 (1995), 333–347. MR 1350686 (96h:11061), http://dx.doi.org/10.1155/S1073792895000250
[CTV09] 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 (2011h:68067), http://dx.doi.org/10.1007/s00224-008-9158-2
[CJ76] 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 0422149 (54 #10141)
[DP07] 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 (2008h:11068)
[FGS08] 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 (2010a:11238), http://dx.doi.org/10.1017/CBO9780511721274.012
[FS04] Michael Filaseta and Andrzej Schinzel, On testing the divisibility of lacunary polynomials by cyclotomic polynomials, Math. Comp. 73 (2004), no. 246, 957–965 (electronic). MR 2031418 (2004m:11207), http://dx.doi.org/10.1090/S0025-5718-03-01589-8
[GG03] Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757 (2004g:68202)
[Ha53] G. Hajós, Solution of Problem 41, (Hungarian), Mat. Lapok 4, (1953), 40-41.
[K70] 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 (54 #11839)
[LS96] 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.
[Lan83] Serge Lang, Fundamentals of Diophantine geometry, Springer-Verlag, New York, 1983. MR 715605 (85j:11005)
[Lau84] Michel Laurent, Équations diophantiennes exponentielles, Invent. Math. 78 (1984), no. 2, 299–327 (French). MR 767195 (86j:11062), http://dx.doi.org/10.1007/BF01388597
[Ler08] 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.
[P84] 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 (85j:68043), http://dx.doi.org/10.1016/0304-3975(84)90130-0
[PR98] 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 (electronic). MR 1612877 (98k:52027), http://dx.doi.org/10.1137/S0895480195281246
[Re02] G. Rémond, Sur les sous-variétés des tores, Comp. Math., (2002), 337-366.
[Ro07] 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 (2009g:68077)
[RS62] J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 0137689 (25 #1139)
[Ru93] Wolfgang M. Ruppert, Solving algebraic equations in roots of unity, J. Reine Angew. Math. 435 (1993), 119–156. MR 1203913 (94c:11054), http://dx.doi.org/10.1515/crll.1993.435.119
[S96] Wolfgang M. Schmidt, Heights of points on subvarieties of 𝐺ⁿ_{𝑚}, Number theory (Paris, 1993–1994) London Math. Soc. Lecture Note Ser., vol. 235, Cambridge Univ. Press, Cambridge, 1996, pp. 157–187. MR 1628798 (99h:11070), http://dx.doi.org/10.1017/CBO9780511662003.008
[SS71] A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 0292344 (45 #1431)
[Z09] 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 (2011d:11001)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|