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

Published

Journal Article

© Canadian Mathematical Society 2018. A theorem of Gekeler compares the number of non-isomorphic automorphic representations associated with the space of cusp forms of weight k on Γ 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 Γ 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.

### Full Text

### Duke Authors

### Cited Authors

- Gu, M; Martin, G

### Published Date

- March 1, 2019

### Published In

### Volume / Issue

- 62 / 1

### Start / End Page

- 81 - 97

### Electronic International Standard Serial Number (EISSN)

- 1496-4287

### International Standard Serial Number (ISSN)

- 0008-4395

### Digital Object Identifier (DOI)

- 10.4153/CMB-2018-035-0

### Citation Source

- Scopus