Explicit bounds on the coefficients of modular polynomials for the elliptic $j$-invariant

Abstract

We obtain an explicit upper bound on the size of the coefficients of the elliptic modular polynomials $\Phi _N$ for any $N\geq 1$. These polynomials vanish at pairs of $j$-invariants of elliptic curves linked by cyclic isogenies of degree $N$. The main term in the bound is asymptotically optimal as $N$ tends to infinity.

1. Introduction

For any nonzero polynomial $P$ in one or more variables and complex coefficients, we define its height to be

$$\begin{equation*} h(P) \coloneq \log \max |c|, \quad \text{where $c$ ranges over all coefficients of $P$.} \end{equation*}$$

Let $N$ be a positive integer and denote by $\Phi _N = \Phi _N(X,Y) \in \mathbb{Z}[X,Y]$ the (classical) modular polynomial, which vanishes at pairs of $j$-invariants of elliptic curves linked by a cyclic $N$-isogeny; see La87, Chapter 5. Alternatively, if we view $j$ as the function on the complex upper half-plane where $j(\tau )$ is the $j$-invariant of the complex elliptic curve $\mathbb{C}/(\mathbb{Z}+\tau \mathbb{Z})$, then $\Phi _N(X, j(\tau ))$ is the minimal polynomial of $j(N\tau )$ over $\mathbb{C}(j(\tau ))$.

Modular polynomials have important applications in cryptography and certain algorithms for computing $\Phi _N$ require explicit bounds on the size of the coefficients, so one is interested in explicit bounds on $h(\Phi _N)$.

Paula Cohen Tretkoff Coh84 proved that when $N$ tends to $+\infty$

$$\begin{equation} h(\Phi _N) = 6\psi (N)\big [\log N - 2\kappa _N + O(1)\big ] {\tag{1}} \end{equation}$$

where

$$\begin{equation*} \psi (N) = N\prod _{p|N}\left(1 + \frac{1}{p}\right)\quad \text{and}\quad \kappa _N = \sum _{p|N}\frac{\log p}{p}, \end{equation*}$$

but the implied bounded function is not explicit.

In the case where $N=l$ is prime, Bröker and Sutherland BrSu10 estimated the constants in Cohen’s argument to obtain

$$\begin{equation*} h(\Phi _l) \leq 6l\log l + 16 l + 14\sqrt {l}\log l. \end{equation*}$$

In the general case, the second author obtained Paz19, Corollary 4.3 via a different method,

$$\begin{equation} h(\Phi _N) \leq \psi (N)\big [ 6\log N + \log \psi (N) + 6\log (12 \log N + 2\log \psi (N) + 25.2) + 15.7\big ]. {\tag{2}} \end{equation}$$

Inequality 2 has the merit of being completely explicit for all $N\geq 1$, but the main term is slightly too big when compared with the asymptotic of 1.

The goal of the present paper is to prove the following result, where we solve this issue and provide an upper bound with the correct main term for all $N$. Let us first define

$$\begin{equation*} \lambda _N \coloneq \sum _{p^n\|N}\frac{p^n-1}{p^{n-1}(p^2-1)}\log p. \end{equation*}$$

Theorem 1.1.

Let $N\geq 2$. The height of the modular polynomial $\Phi _N(X,Y)$ is bounded by

$$\begin{equation} h(\Phi _N) \leq 6\psi (N)\big [\log N -2\lambda _N + \log \log N + 4.436\big ]. {\tag{3}} \end{equation}$$

We prove this theorem using a different path than the one followed in Paz19. The main new ingredient is a finer estimate of the Mahler measure of $j$-invariants, coming from previous work of Pascal Autissier Aut03. We also use precise analytic estimates for the discriminant modular form on the fundamental domain of the upper half-plane (under the classical action of $\operatorname {SL}_2(\mathbb{Z})$), and a classical interpolation method to help us derive bounds on the height of a polynomial in two variables, from knowledge of the height of several specializations of this polynomial.

Let us now discuss the optimality of the bound. The main term is the expected one. For lower order terms, notice that

$$\begin{equation*} -0.385 < -\sum _{p|N}\frac{\log p}{p(p+1)} \leq \lambda _N - \kappa _N \leq \sum _{p|N}\frac{\log p}{p(p^2-1)} < 0.186, \end{equation*}$$

so one changes little replacing $\lambda _N$ by $\kappa _N$ in Theorem 1.1. On the other hand, one would like to get rid of the spurious $\log \log N$ term, but for practical purposes this might be less useful than keeping the constant as small as possible.

It is interesting to consider the functions $b_\lambda (N)$ and $b_\kappa (N)$ for which

$$\begin{equation} h(\Phi _N) = 6\psi (N)\big [\log N -2\lambda _N + b_\lambda (N)\big ] = 6\psi (N)\big [\log N -2\kappa _N + b_\kappa (N)\big ]. \tag{4} \end{equation}$$

These functions are plotted in Figure 1 for $N\leq 400$, based on computations of $\Phi _N$ by Andrew Sutherland Suth using the algorithms in BKS12 (for prime $N$) and BOS16 (for composite $N$).

The content of Cohen’s theorem is that $b_\kappa (N)$ and thus also $b_\lambda (N)$ are bounded functions. Theorem 1.1 is equivalent to $b_\lambda (N) \leq \log \log N + 4.436$, which is clearly seen to hold for $N\leq 400$; in fact, $b_\lambda (N) < 2.1$ in this range.

In our proof of Theorem 1.1 we may thus assume that $N > 400$. We explain in Remark 3.2 and in Lemma 3.3 that more computations for $N > 400$ lead to minor improvements on the constant $4.436$.

From Figure 1 it appears that $b_\lambda (N)$ is bounded more tightly than $b_\kappa (N)$, thus suggesting that $\lambda _N$ is a more natural function to use in the bound for $h(\Phi _N)$ than is $\kappa _N$.

2. Preliminary results

Denote the complex upper half-plane by

$$\begin{equation*} \mathbb{H}\coloneq \{z\in \mathbb{C}\mid {\mathrm{\mathop{Im}}}(z) > 0 \}. \end{equation*}$$

Every $\tau \in \mathbb{H}$ defines a lattice $\Lambda _\tau = \mathbb{Z}+ \tau \mathbb{Z}$ in $\mathbb{C}$, and it is well known that every complex elliptic curve is isomorphic to $\mathbb{C}/\Lambda _\tau$ for some $\tau \in \mathbb{H}$. If we denote the $j$-invariant of this elliptic curve by $j(\tau )$, then

$$\begin{equation*} j : \mathbb{H}\longrightarrow \mathbb{C} \end{equation*}$$

defines an analytic function on $\mathbb{H}$.

The group $\operatorname {SL}_2(\mathbb{Z})$ acts on the upper half-plane $\mathbb{H}$ by

$$\begin{equation*} \gamma (\tau ) \coloneq \frac{a\tau + b}{c\tau + d}, \quad \text{where}\quad \gamma = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \in \operatorname {SL}_2(\mathbb{Z}). \end{equation*}$$

A fundamental domain for this action is given by

$$\begin{equation*} \mathcal{F}=\{\tau \in \mathbb{H}: mid \tau \vert \geq 1, -\frac{1}{2} < \operatorname {Re}(\tau ) \leq \frac{1}{2} \text{ and } \operatorname {Re}(\tau ) \geq 0 \text{ if } |\tau |=1\}. \end{equation*}$$

Thus every $\tau \in \mathbb{H}$ is $\operatorname {SL}_2(\mathbb{Z})$-equivalent to an element $\tilde{\tau }\in \mathcal{F}$, which we call reduced.

The modular function $j : \mathbb{H}\rightarrow \mathbb{C}$ is $\operatorname {SL}_2(\mathbb{Z})$-invariant. We define

$$\begin{equation*} q = e^{2\pi i \tau }, \quad \tau \in \mathbb{H}, \end{equation*}$$

then the Fourier expansion at infinity of $j$ can be written as a $q$-expansion

$$\begin{equation*} j(\tau ) = \frac{1}{q}+744+196884q+\cdots . \end{equation*}$$

We denote by $\Delta$ the modular discriminant function

$$\begin{equation*} \Delta : \mathbb{H}\longrightarrow \mathbb{C}, \end{equation*}$$

which is a weight 12 cusp form for $\operatorname {SL}_2(\mathbb{Z})$. We normalize $\Delta$ so that its $q$-expansion is

$$\begin{equation*} \Delta (\tau ) = q\prod _{n=1}^{\infty }(1-q^n)^{24} = q -24q^2 + 252q^3 + \cdots . \end{equation*}$$

We point out that the discriminant of the elliptic curve $E_\tau$ is given by $(2\pi )^{12}\Delta (\tau )$, which is why most sources (e.g., La87) normalize $\Delta$ differently, multiplying the above product by the factor $(2\pi )^{12}$. We choose our normalization to be consistent with Paz19, which contains estimates that we will use.

Let us denote, for $N\geq 1$,

$$\begin{equation*} C_N=\left\{\begin{pmatrix} a & b \\ 0 & d \end{pmatrix} : a,b,d\in \mathbb{Z}, ad=N, a\geq 1, 0\leq b\leq d-1, \gcd (a,b,d)=1 \right\}. \end{equation*}$$

We have

$$\begin{equation*} \#C_N = \psi (N) = N\prod _{p|N}\left(1 + \frac{1}{p}\right). \end{equation*}$$

The elements of $C_N$ encode cyclic $N$-isogenies in the following way. Let $E_\tau$ be an elliptic curve. For each

$$\begin{equation*} \gamma = \begin{pmatrix} a_\gamma & b_\gamma \\ 0 & d_\gamma \end{pmatrix}\in C_N, \end{equation*}$$

we let

$$\begin{equation*} \tau _\gamma = \gamma (\tau ) = \frac{a_\gamma \tau + b_\gamma }{d_\gamma }, \quad \Lambda _\gamma = \mathbb{Z}+ \tau _\gamma \mathbb{Z}, \quad \text{and}\quad E_\gamma = E_{\tau _\gamma } = \mathbb{C}/\Lambda _\gamma . \end{equation*}$$

Then the natural map

$$\begin{equation*} E \longrightarrow E_\gamma , \quad (z \bmod \Lambda _\tau ) \longmapsto (z \bmod \Lambda _\gamma ) \end{equation*}$$

is a cyclic $N$-isogeny.

Furthermore, up to isomorphism, every cyclic $N$-isogeny with source $E$ arises in this way. In particular, we have the factorization

$$\begin{equation*} \Phi _N\big (X, j(\tau )\big )=\prod _{\gamma \in {C_N}}\big (X-j(\tau _\gamma )\big ). \end{equation*}$$

Our goal is to bound the coefficients of the modular polynomial $\Phi _N(X,Y)$. By interpolation, it is enough to estimate the height of $\Phi _N(X, j(\tau ))$ for several carefully chosen $\tau \in \mathbb{H}$.

By BrZu20, Lemma 1.6 the height of $\Phi _N(X,j(\tau ))$ is bounded in terms of its Mahler measure

$$\begin{equation} S_N(\tau )={\sum _{\gamma \in {C_N}}\log \max \big (1, \vert j(\tau _\gamma )\vert \big )} {\tag{5}} \end{equation}$$

by

$$\begin{equation} h(\Phi _N(X,j)) \leq S_N(\tau ) + \log \binom{\psi (N)}{\psi (N)/2} \leq S_N(\tau ) + \psi (N)\log 2. {\tag{6}} \end{equation}$$

We will concentrate on estimating $S_N(\tau )$ for a fixed $\tau \in \mathbb{H}$.

In general, $\tau _\gamma$ won’t be reduced, so we choose

$$\begin{equation*} \begin{pmatrix} a & b \\ c & d\end{pmatrix}\in \operatorname {SL}_2(\mathbb{Z}) \end{equation*}$$

for which

$$\begin{equation*} \tilde{\tau }_\gamma = \frac{a\tau _\gamma + b}{c\tau _\gamma +d} \in \mathcal{F} \end{equation*}$$

is reduced. Since

$$\begin{equation*} {\mathrm{\mathop{Im}}}(\tilde{\tau }_\gamma ) = {\mathrm{\mathop{Im}}}\left(\frac{a\tau _\gamma + b}{c\tau _\gamma + d}\right) = \frac{{\mathrm{\mathop{Im}}}(\tau _\gamma )}{|c\tau _\gamma + d|^2}, \end{equation*}$$

we obtain

$$\begin{equation} -\log |c\tau _\gamma + d| = \frac{1}{2}\big [\log {\mathrm{\mathop{Im}}}(\tilde{\tau }_\gamma ) - \log {\mathrm{\mathop{Im}}}(\tau _\gamma )\big ]. {\tag{7}} \end{equation}$$

Also, since $\Delta$ is a modular form of weight $12$ for $\operatorname {SL}_2(\mathbb{Z})$, we find that

$$\begin{equation*} \tilde{\Delta }_\gamma \coloneq \Delta (\tilde{\tau }_\gamma ) = (c\tau _\gamma + d)^{12}\Delta (\tau _\gamma ) \eqcolon (c\tau _\gamma + d)^{12}\Delta _\gamma , \end{equation*}$$

so

$$\begin{align} \log |\Delta _\gamma | &= \log |\tilde{\Delta }_\gamma | - 12\log |c\tau _\gamma + d| \\ &= \log |\tilde{\Delta }_\gamma |+ 6\big [ \log {\mathrm{\mathop{Im}}}(\tilde{\tau }_\gamma ) - \log {\mathrm{\mathop{Im}}}(\tau _\gamma ) \big ]. {\tag{8}} \end{align}$$

Note that by Paz19, Lemma 2.4 we have

$$\begin{equation} \log {\mathrm{\mathop{Im}}}(\tilde{\tau }_\gamma ) - \log {\mathrm{\mathop{Im}}}(\tau ) \leq \log N {\tag{9}} \end{equation}$$

for each $\gamma \in C_N$, provided that $\tau \in \mathcal{F}$.

We need a few more preliminaries.

By Aut03, Lemme 2.2, we have

$$\begin{equation*} \prod _{\gamma \in C_N} \Delta (\gamma (\tau )) = \big [-\Delta (\tau )\big ]^{\psi (N)}, \end{equation*}$$

so we get

$$\begin{equation} \sum _{\gamma \in C_N} \log |\Delta _\gamma | = \psi (N)\log |\Delta |. {\tag{10}} \end{equation}$$

Furthermore, Aut03, Lemme 2.3 says

$$\begin{equation*} \sum _{\gamma \in C_N}\log \frac{d_\gamma }{a_\gamma } = \psi (N)(\log N - 2\lambda _N), \end{equation*}$$

which combined with

$$\begin{equation*} {\mathrm{\mathop{Im}}}(\tau _\gamma ) = {\mathrm{\mathop{Im}}}\left( \frac{a_\gamma \tau + b_\gamma }{d_\gamma } \right) = \frac{a_\gamma }{d_\gamma }{\mathrm{\mathop{Im}}}(\tau ) \end{equation*}$$

gives

$$\begin{equation} -\sum _{\gamma \in C_N}\log {\mathrm{\mathop{Im}}}(\tau _\gamma ) = \psi (N)\big (\log N - 2\lambda _N -\log {\mathrm{\mathop{Im}}}(\tau )\big ). {\tag{11}} \end{equation}$$

Finally, since $\tilde{\tau }_\gamma \in \mathcal{F}$, Paz19, (2.22) gives us—if we denote $j_\gamma =j(\tau _\gamma )$—

$$\begin{equation} {\mathrm{\mathop{Im}}}(\tilde{\tau }_\gamma ) \leq \frac{1}{2\pi }\log (|j_\gamma |+970.8), {\tag{12}} \end{equation}$$

whereas Paz19, (3.18) gives, for any $\gamma \in C_N$,

$$\begin{equation} \log \max (|\tilde{\Delta }_\gamma |,|j_\gamma \tilde{\Delta }_\gamma |) \leq \log (9.02). {\tag{13}} \end{equation}$$

This last estimate depends on our choice of normalization of $\Delta (\tau )$.

We note that the identities 10 and 11 from Aut03 involve the nonreduced $\tau _\gamma$, whereas the estimates 9, 12, and 13 from Paz19 depend on the reduced $\tilde{\tau }_\gamma$. The main idea of this paper is to combine these ingredients using 8.

3. Proof of Theorem 1.1

We are now ready to start our main calculation on the sum $S_N(\tau )$ from 5.

$$\begin{align} S_N(\tau )= & \sum _{\gamma \in C_N}\log \max (|\Delta _\gamma |,|j_\gamma \Delta _\gamma |) - \sum _{\gamma \in C_N}\log |\Delta _\gamma | \\ = & \sum _{\gamma \in C_N}\log \max (|\Delta _\gamma |,|j_\gamma \Delta _\gamma |) - \psi (N)\log |\Delta | \quad \text{(by \xhref[disp-formula]{#texmlid1}{10})} \\ = & \sum _{\gamma \in C_N} \log \max (|\tilde{\Delta }_\gamma |,|j_\gamma \tilde{\Delta }_\gamma |) \tag{14}\\ & \quad +6 \sum _{\gamma \in C_N} \big [\log {\mathrm{\mathop{Im}}}(\tilde{\tau }_\gamma ) - \log {\mathrm{\mathop{Im}}}(\tau _\gamma )\big ] - \psi (N)\log |\Delta | \quad \text{(by \xhref[disp-formula]{#texmlid6}{8}),} \end{align}$$

hence we get

$$\begin{align} S_N(\tau ) & \leq \psi (N)\log (9.02)\\ & \quad +6 \sum _{\gamma \in C_N} \big [\log {\mathrm{\mathop{Im}}}(\tilde{\tau }_\gamma ) - \log {\mathrm{\mathop{Im}}}(\tau _\gamma )\big ] - \psi (N)\log |\Delta | \quad \text{(by \xhref[disp-formula]{#texmlid5}{13})} \\ & = \psi (N)\log (9.02) + 6\psi (N)\big (\log N - 2\lambda _N -\log {\mathrm{\mathop{Im}}}\tau \big ) \\ & \quad + 6\sum _{\gamma \in C_N} \log {\mathrm{\mathop{Im}}}(\tilde{\tau }_\gamma ) - \psi (N)\log |\Delta | \quad \text{(by \xhref[disp-formula]{#texmlid2}{11})} \\ & \leq 6\psi (N)\big [\log N - 2\lambda _N + 0.367\big ]\\ & \quad + 6\sum _{\gamma \in C_N} \log {\mathrm{\mathop{Im}}}(\tilde{\tau }_\gamma ) - \psi (N)\log \big [|\Delta |({\mathrm{\mathop{Im}}}\tau )^6\big ]. {\tag{15}} \end{align}$$

At this point we record the following intermediate result. If $\tau \in \mathcal{F}$ then we may apply 9 and obtain

$$\begin{align} S_N(\tau ) & \leq 6\psi (N)\big [\log N - 2\lambda _N + 0.367\big ]\\ & \quad +6\psi (N)[\log N + \log {\mathrm{\mathop{Im}}}\tau ] - \psi (N)\log \big [|\Delta |({\mathrm{\mathop{Im}}}\tau )^6\big ] \\ & \leq \psi (N)[12\log N + 2.199 - \log |\Delta |]. {\tag{16}} \end{align}$$

We continue our calculation from 15.