Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComputing modular polynomials in quasi-linear time
110
0
0.0
(
0
)
Added by
Andreas Enge
Publication date
2008
fields
Informatics Engineering
and research's language is
English
Authors
Andreas Enge
Ask ChatGPT about the research
No Arabic abstract
We analyse and compare the complexity of several algorithms for computing modular polynomials. We show that an algorithm relying on floating point evaluation of modular functions and on interpolation, which has received little attention in the literature, has a complexity that is essentially (up to logarithmic factors) linear in the size of the computed polynomials. In particular, it obtains the classical modular polynomials $Phi_ell$ of prime level $ell$ in time O (ell^3 log^4 ell log log ell). Besides treating modular polynomials for $Gamma^0 (ell)$, which are an important ingredient in many algorithms dealing with isogenies of elliptic curves, the algorithm is easily adapted to more general situations. Composite levels are handled just as easily as prime levels, as well as polynomials between a modular function and its transform of prime level, such as the Schlafli polynomials and their generalisations. Our distributed implementation of the algorithm confirms the theoretical analysis by computing modular equations of record level around 10000 in less than two weeks on ten processors.
rate research
Read More
We discuss practical and some theoretical aspects of computing a database of classical modular forms in the L-functions and Modular Forms Database (LMFDB).
We give algorithms for computing the singular moduli of suitable nonholomorphic modular functions F(z). By combining the theory of isogeny volcanoes with a beautiful observation of Masser concerning the nonholomorphic Eisenstein series E_2*(z), we obtain CRT-based algorithms that compute the class polynomials H_D(F;x), whose roots are the discriminant D singular moduli for F(z). By applying these results to a specific weak Maass form F_p(z), we obtain a CRT-based algorithm for computing partition class polynomials, a sequence of polynomials whose traces give the partition numbers p(n). Under the GRH, the expected running time of this algorithm is O(n^{5/2+o(1)}). Key to these results is a fast CRT-based algorithm for computing the classical modular polynomial Phi_m(X,Y) that we obtain by extending the isogeny volcano approach previously developed for prime values of m.
Let f in Q[z] be a polynomial of degree d at least two. The associated canonical height hat{h}_f is a certain real-valued function on Q that returns zero precisely at preperiodic rational points of f. Morton and Silverman conjectured in 1994 that the number of such points is bounded above by a constant depending only on d. A related conjecture claims that at non-preperiodic rational points, hat{h}_f is bounded below by a positive constant (depending only on d) times some kind of height of f itself. In this paper, we provide support for these conjectures in the case d=3 by computing the set of small height points for several billion cubic polynomials.
We present a deterministic algorithm which computes the multilinear factors of multivariate lacunary polynomials over number fields. Its complexity is polynomial in $ell^n$ where $ell$ is the lacunary size of the input polynomial and $n$ its number of variables, that is in particular polynomial in the logarithm of its degree. We also provide a randomized algorithm for the same problem of complexity polynomial in $ell$ and $n$. Over other fields of characteristic zero and finite fields of large characteristic, our algorithms compute the multilinear factors having at least three monomials of multivariate polynomials. Lower bounds are provided to explain the limitations of our algorithm. As a by-product, we also design polynomial-time deterministic polynomial identity tests for families of polynomials which were not known to admit any. Our results are based on so-called Gap Theorem which reduce high-degree factorization to repeated low-degree factorizations. While previous algorithms used Gap Theorems expressed in terms of the heights of the coefficients, our Gap Theorems only depend on the exponents of the polynomials. This makes our algorithms more elementary and general, and faster in most cases.
We develop a new algorithm to compute a basis for $M_k(Gamma_0(N))$, the space of weight $k$ holomorphic modular forms on $Gamma_0(N)$, in the case when the graded algebra of modular forms over $Gamma_0(N)$ is generated at weight two. Our tests show that this algorithm significantly outperforms a commonly used algorithm which relies more heavily on modular symbols.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
