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

For any non-zero polynomial $P$ in one or more variables and complex coefficients we define its height to be

$$h(P):=\log\max|c|,\quad\text{where $c$ ranges over all coefficients of $P$.}$$

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$

(1)

$$h(\Phi_{N})=6\psi(N)\big{[}\log N-2\kappa_{N}+O(1)\big{]}$$

where

$$\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},$$

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

$$h(\Phi_{l})\leq 6l\log l+16l+14\sqrt{l}\log l.$$

In the general case, the second author [Paz19] obtained in his Corollary 4.3, via a different method,

(2)

$$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{]}.$$

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

$$\lambda_{N}:=\sum_{p^{n}\|N}\frac{p^{n}-1}{p^{n-1}(p^{2}-1)}\log p.$$

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 $\mathrm{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

$$-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,$$

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

(4)

$$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{]}.$$

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. Our 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}$.

Denote the complex upper half-plane by

$$\mathbb{H}:=\{z\in\mathbb{C}\;|\;\mathop{\mathrm{Im}}(z)>0\}.$$

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

$$j:\mathbb{H}\longrightarrow\mathbb{C}$$

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

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

$$\gamma(\tau):=\frac{a\tau+b}{c\tau+d},\quad\text{where}\quad\gamma=\left(\begin{matrix}a&b\\ c&d\end{matrix}\right)\in\mathrm{SL}_{2}(\mathbb{Z}).$$

A fundamental domain for this action is given by

$$\mathcal{F}=\{\tau\in\mathbb{H}\;:\;|\tau|\geq 1,\;-\frac{1}{2}<\mathrm{Re}(\tau)\leq\frac{1}{2}\;\mathrm{and}\;\mathrm{Re}(\tau)\geq 0\;\mathrm{if}\;|\tau|=1\}.$$

Thus every $\tau\in\mathbb{H}$ is $\mathrm{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 $\mathrm{SL}_{2}(\mathbb{Z})$-invariant. We define

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

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

$$j(\tau)=\frac{1}{q}+744+196884q+\ldots.$$

We denote by $\Delta$ the modular discriminant function

$$\Delta:\mathbb{H}\longrightarrow\mathbb{C},$$

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

$$\Delta(\tau)=q\prod_{n=1}^{\infty}(1-q^{n})^{24}=q-24q^{2}+252q^{3}+\cdots.$$

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$,

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

We have

$$\#C_{N}=\psi(N)=N\prod_{p|N}\left(1+\frac{1}{p}\right).$$

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

$$\gamma=\left(\begin{matrix}a_{\gamma}&b_{\gamma}\\ 0&d_{\gamma}\end{matrix}\right)\in C_{N},$$

we let

$$\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}.$$

Then the natural map

$$E\longrightarrow E_{\gamma},\quad(z\bmod\Lambda_{\tau})\longmapsto(z\bmod\Lambda_{\gamma})$$

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

$$\Phi_{N}\big{(}X,j(\tau)\big{)}=\prod_{\gamma\in{C_{N}}}\big{(}X-j(\tau_{\gamma})\big{)}.$$

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

(5)

$$S_{N}(\tau)=\displaystyle{\sum_{\gamma\in{C_{N}}}\log\max\big{(}1,|j(\tau_{\gamma})|\big{)}}$$

by

(6)

$$h(\Phi_{N}(X,j))\leq S_{N}(\tau)+\log\binom{\psi(N)}{\psi(N)/2}\leq S_{N}(\tau)+\psi(N)\log 2.$$

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 $\left(\begin{matrix}a&b\\ c&d\end{matrix}\right)\in\mathrm{SL}_{2}(\mathbb{Z})$ for which

$$\tilde{\tau}_{\gamma}=\frac{a\tau_{\gamma}+b}{c\tau_{\gamma}+d}\in\mathcal{F}$$

is reduced. Since

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

we obtain

(7)

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

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

$$\tilde{\Delta}_{\gamma}:=\Delta(\tilde{\tau}_{\gamma})=(c\tau_{\gamma}+d)^{12}\Delta(\tau_{\gamma})=:(c\tau_{\gamma}+d)^{12}\Delta_{\gamma},$$

so

	$\displaystyle\log|\Delta_{\gamma}|$	$\displaystyle=\log|\tilde{\Delta}_{\gamma}|-12\log|c\tau_{\gamma}+d|$
(8)			$\displaystyle=\log|\tilde{\Delta}_{\gamma}|+6\big{[}\log\mathop{\mathrm{Im}}(\tilde{\tau}_{\gamma})-\log\mathop{\mathrm{Im}}(\tau_{\gamma})\big{]}.$

Note that by [Paz19, Lemma 2.4] we have

(9)

$$\log\mathop{\mathrm{Im}}(\tilde{\tau}_{\gamma})-\log\mathop{\mathrm{Im}}(\tau)\leq\log N$$

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

$$\prod_{\gamma\in C_{N}}\Delta(\gamma(\tau))=\big{[}-\Delta(\tau)\big{]}^{\psi(N)},$$

so we get

(10)

$$\sum_{\gamma\in C_{N}}\log|\Delta_{\gamma}|=\psi(N)\log|\Delta|.$$

Furthermore, [Aut03, Lemme 2.3] says

$$\sum_{\gamma\in C_{N}}\log\frac{d_{\gamma}}{a_{\gamma}}=\psi(N)(\log N-2\lambda_{N}),$$

which combined with

$$\mathop{\mathrm{Im}}(\tau_{\gamma})=\mathop{\mathrm{Im}}\left(\frac{a_{\gamma}\tau+b_{\gamma}}{d_{\gamma}}\right)=\frac{a_{\gamma}}{d_{\gamma}}\mathop{\mathrm{Im}}(\tau)$$

gives

(11)

$$-\sum_{\gamma\in C_{N}}\log\mathop{\mathrm{Im}}(\tau_{\gamma})=\psi(N)\big{(}\log N-2\lambda_{N}-\log\mathop{\mathrm{Im}}(\tau)\big{)}.$$

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

(12)

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

whereas [Paz19, (3.18)] gives, for any $\gamma\in C_{N}$,

(13)

$$\log\max(|\tilde{\Delta}_{\gamma}|,|j_{\gamma}\tilde{\Delta}_{\gamma}|)\leq\log(9.02).$$

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

We note that the identities (10) and (11) from [Aut03] involve the non-reduced $\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).

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

	$\displaystyle S_{N}(\tau)=$	$\displaystyle\sum_{\gamma\in C_{N}}\log\max(|\Delta_{\gamma}|,|j_{\gamma}\Delta_{\gamma}|)-\sum_{\gamma\in C_{N}}\log|\Delta_{\gamma}|$
	$\displaystyle=$	$\displaystyle\sum_{\gamma\in C_{N}}\log\max(|\Delta_{\gamma}|,|j_{\gamma}\Delta_{\gamma}|)-\psi(N)\log|\Delta|\quad\text{(by (\ref{eq:Aut2.2}))}$
	$\displaystyle=$	$\displaystyle\sum_{\gamma\in C_{N}}\log\max(|\tilde{\Delta}_{\gamma}|,|j_{\gamma}\tilde{\Delta}_{\gamma}|)+6\sum_{\gamma\in C_{N}}\big{[}\log\mathop{\mathrm{Im}}(\tilde{\tau}_{\gamma})-\log\mathop{\mathrm{Im}}(\tau_{\gamma})\big{]}-\psi(N)\log|\Delta|\quad\text{(by (\ref{eq:cDelta})),}$

hence we get

	$\displaystyle S_{N}(\tau)\leq\;$	$\displaystyle\psi(N)\log(9.02)+6\sum_{\gamma\in C_{N}}\big{[}\log\mathop{\mathrm{Im}}(\tilde{\tau}_{\gamma})-\log\mathop{\mathrm{Im}}(\tau_{\gamma})\big{]}-\psi(N)\log|\Delta|\quad\text{(by (\ref{eq:Paz3.18}))}$
	$\displaystyle=\;$	$\displaystyle\psi(N)\log(9.02)+6\psi(N)\big{(}\log N-2\lambda_{N}-\log\mathop{\mathrm{Im}}\tau\big{)}$
		$\displaystyle+6\sum_{\gamma\in C_{N}}\log\mathop{\mathrm{Im}}(\tilde{\tau}_{\gamma})-\psi(N)\log|\Delta|\quad\text{(by (\ref{eq:Aut2.3}))}$
(15)		$\displaystyle\leq\;$	$\displaystyle 6\psi(N)\big{[}\log N-2\lambda_{N}+0.367\big{]}+6\sum_{\gamma\in C_{N}}\log\mathop{\mathrm{Im}}(\tilde{\tau}_{\gamma})-\psi(N)\log\big{[}|\Delta|(\mathop{\mathrm{Im}}\tau)^{6}\big{]}.$

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

	$\displaystyle S_{N}(\tau)\leq\;$	$\displaystyle 6\psi(N)\big{[}\log N-2\lambda_{N}+0.367\big{]}+6\psi(N)[\log N+\log\mathop{\mathrm{Im}}\tau]-\psi(N)\log\big{[}|\Delta|(\mathop{\mathrm{Im}}\tau)^{6}\big{]}$
(16)		$\displaystyle\leq\;$	$\displaystyle\psi(N)[12\log N+2.199-\log|\Delta|].$

We continue our calculation from (15).

	$\displaystyle S_{N}(\tau)\leq\;$	$\displaystyle 6\psi(N)\big{[}\log N-2\lambda_{N}+0.367\big{]}-\psi(N)\log\big{[}|\Delta|(\mathop{\mathrm{Im}}\tau)^{6}\big{]}$
		$\displaystyle+6\sum_{\gamma\in C_{N}}\log\Big{[}\frac{1}{2\pi}\log(|j_{\gamma}|+970.8)\Big{]}\quad\text{(by (\ref{eq:Paz2.22}))}$
	$\displaystyle=\;$	$\displaystyle 6\psi(N)\big{[}\log N-2\lambda_{N}+0.367\big{]}-\psi(N)\log\big{[}|\Delta|\mathop{\mathrm{Im}}(\tau)^{6}\big{]}$
		$\displaystyle+6\psi(N)\log\prod_{\gamma\in C_{N}}\Big{[}\frac{1}{2\pi}\log(|j_{\gamma}|+970.8)\Big{]}^{1/\psi(N)}$
	$\displaystyle\leq\;$	$\displaystyle 6\psi(N)\big{[}\log N-2\lambda_{N}+0.367\big{]}-\psi(N)\log\big{[}|\Delta|\mathop{\mathrm{Im}}(\tau)^{6}\big{]}$
		$\displaystyle+6\psi(N)\log\Big{[}\frac{1}{2\pi\psi(N)}\sum_{\gamma\in C_{N}}\log(|j_{\gamma}|+970.8)\Big{]},$

where the last inequality follows by the arithmetic-geometric mean inequality.

For any real number $x$, the inequality $x+970.8\leq 971.8\max\{1,x\}$ holds, so we finally obtain

	$\displaystyle S_{N}(\tau)=\;$	$\displaystyle\sum_{\gamma\in C_{N}}\log\max(1,|j_{\gamma}|)$
	$\displaystyle\leq\;$	$\displaystyle 6\psi(N)\big{[}\log N-2\lambda_{N}+0.367\big{]}-\psi(N)\log\big{[}|\Delta|\mathop{\mathrm{Im}}(\tau)^{6}\big{]}$
		$\displaystyle+6\psi(N)\big{[}\log S_{N}(\tau)+\log\log(971.8)-\log\psi(N)-\log(2\pi)\big{]}$
(17)		$\displaystyle\leq\;$	$\displaystyle 6\psi(N)\big{[}\log N-2\lambda_{N}+\log\big{(}S_{N}(\tau)/\psi(N)\big{)}+0.458]-\psi(N)\log\big{[}|\Delta|\mathop{\mathrm{Im}}(\tau)^{6}\big{]}.$

To deduce an explicit bound on $S_{N}(\tau)$, we start with a crude bound on $S_{N}(\tau)/\psi(N)$, then strengthen our result recursively. More precisely, we prove the following technical lemma.

The interpolation lemma [BrSu10, Lemma 20] gives, for real $L>1$,

$$h(\Phi_{N}(X,Y))\leq\max_{L\leq j\leq 2L}h(\Phi_{N}(X,j))+\psi(N)\left(\frac{\log L+1}{L}+3\log 2\right),$$

so by (6) we get

(19)

$$h(\Phi_{N}(X,Y))\leq\max_{L\leq j(\tau)\leq 2L}S_{N}(\tau)+\psi(N)\left(\frac{\log L+1}{L}+4\log 2\right).$$

It is well-known that the $j$-function takes non-negative real values on the following path on the boundary of the fundamental domain $\mathcal{F}$:

$$\Gamma:=\{e^{i\theta}\;|\;\frac{\pi}{3}\leq\theta\leq\frac{\pi}{2}\}\cup\{ix\;|\;x\in[0,\infty)\}$$

and the function $j:\Gamma\rightarrow[0,\infty)$ is a bijection.

We now define, for the values $c_{n}(\tau)$ in Lemma 3.1 with $N_{0}=400$,

$$c(\tau):=\inf_{n\geq 0}c_{n}(\tau).$$

Optimizing on the interval $L\leq j\leq 2L$, we obtain

$$h(\Phi_{N}(X,Y))\leq 6\psi(N)\big{[}\log N-2\lambda_{N}+\log\log N+c_{n}(\tau)\big{]}\big{|}_{j(\tau)=2L}+\psi(N)\left(\frac{\log L+1}{L}+4\log 2\right).$$

Optimizing $c(\tau)$ (using SageMath [Sage]) when $L>1$, we obtain the strongest upper bound when we choose $L=166.48$, then $\tau=j^{-1}(L)=e^{i\cdot 1.257}$ and

$$a(\tau)\leq 1.5004,\quad b(\tau)\leq 8.1532,\quad c(\tau)\leq 3.9655.$$

Putting all of this together, we obtain

$$h(\Phi_{N})\leq 6\psi(N)\big{[}\log N-2\lambda_{N}+\log\log N+4.436\big{]}$$

for $N\geq N_{0}=400$.

As can be seen from Figure 1, the result also holds for $N\leq 400$, thus completing the proof of Theorem 1.1.

∎

Let us add the following remark.

If one takes $\tau=e^{i\cdot 1.257}$ and $n\to+\infty$ in (20) we obtain the following inequality, valid for any $N_{0}\geq 3$ and any $N\geq N_{0}$:

(21)

$$h(\Phi_{N})\leq 6\psi(N)\left[\log N-2\lambda_{N}+\log\log N+3.293\frac{\log N_{0}}{\log N_{0}-1}+\frac{\log\log N_{0}}{\log N_{0}-1}+0.46537\right].$$

Explicit computation of $c_{n}(\tau)$ will generally give better numerical values of course, but this equation (21) gives an idea of how these estimates will vary with $N_{0}$.