Factorization Tests and Algorithms Arising from Counting Modular Forms and Automorphic Representations

Gu, Miao ; Martin, Greg

Canadian mathematical bulletin, Tome 62 (2019) no. 1, pp. 81-97

Résumé

A theorem of Gekeler compares the number of non-isomorphic automorphic representations associated with the space of cusp forms of weight $k$ on $\unicode[STIX]{x0393}_{0}(N)$ to a simpler function of $k$ and $N$, showing that the two are equal whenever $N$ is squarefree. We prove the converse of this theorem (with one small exception), thus providing a characterization of squarefree integers. We also establish a similar characterization of prime numbers in terms of the number of Hecke newforms of weight $k$ on $\unicode[STIX]{x0393}_{0}(N)$.It follows that a hypothetical fast algorithm for computing the number of such automorphic representations for even a single weight $k$ would yield a fast test for whether $N$ is squarefree. We also show how to obtain bounds on the possible square divisors of a number $N$ that has been found not to be squarefree via this test, and we show how to probabilistically obtain the complete factorization of the squarefull part of $N$ from the number of such automorphic representations for two different weights. If in addition we have the number of such Hecke newforms for even a single weight $k$, then we show how to probabilistically factor $N$ entirely. All of these computations could be performed quickly in practice, given the number(s) of automorphic representations and modular forms as input.

Détail

DOI : 10.4153/CMB-2018-035-0

Mots-clés : modular form, automorphic representation, squarefree number, primality testing, factorization algorithm

Bibliographie

[1] Agrawal, M., Kayal, N., and Saxena, N., PRIMES is in P . Ann. of Math. (2) 160(2004), no. 2, 781–793. . Google Scholar | DOI

[2] Casandjian, C., Challamel, N., Lanos, C., and Hellesland, J., Reinforced concrete beams, columns and frames: mechanics and design. John Wiley & Sons, Hoboken, NJ, 2013, 267–276. . Google Scholar | DOI

[3] Gekeler, E.-U., A remark on dimensions of spaces of modular forms . Arch. Math. (Basel) 65(1995), no. 6, 530–533. . Google Scholar | DOI

[4] The LMFDB Collaboration, The L-functions and Modular Forms Database. http://www.lmfdb.org/ModularForm/GL2/Q/holomorphic. Google Scholar

[5] Martin, G., Dimensions of the spaces of cusp forms and newforms on 𝛤(N) and 𝛤(N) . J. Number Theory 112(2005), no. 2, 298–331. . Google Scholar | DOI

[6] Rosser, J. B. and Schoenfeld, L., Approximate formulas for some functions of prime numbers . Illinois J. Math. 6(1962), 64–94. Google Scholar

[7] Shoup, V., A computational introduction to number theory and algebra . Cambridge University Press, Cambridge, 2005. . Google Scholar | DOI