Divisibility of the coefficients of modular polynomials

Florian Breuer · 2025

Read Divisibility of the coefficients of modular polynomials by Florian Breuer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-06423.txt.

Introduction

Coefficients of modular polynomials are far more divisible than they look, notes Florian Breuer in a 2025 paper. The modular polynomial for a level N vanishes exactly at pairs of j-invariants of elliptic curves joined by a cyclic isogeny of that degree. Breuer studies its coefficients after shifting both variables by an algebraic number J, especially zero and other singular moduli.

Those coefficients turn out to be highly divisible by small primes at which J has supersingular reduction, a special arithmetic behavior of the matching curve. The note links the polynomial's arithmetic to the reduction of the shift point, in a few exact statements.

Catalog record

CREATORFlorian Breuer
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-06423

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Divisibility of the coefficients of modular polynomials Florian Breuer Abstract . Let N > 1 N>1 and let Φ N ​ ( X , Y ) ∈ ℤ ⁡ [ X , Y ] \Phi_{N}(X,Y)\in\mathbb{Z}[X,Y] be the modular polynomial which vanishes precisely at pairs of j j -invariants of elliptic curves linked by a cyclic isogeny of degree N N . In this note we study the divisibility of the coefficients Φ N ​ ( X + J , Y + J ) \Phi_{N}(X+J,Y+J) for certain algebraic numbers J J , in particular J = 0 J=0 and J = 1728 J=1728 . It turns out that these coefficients are highly divisible by small primes at which J J is supersingular. 1991 Mathematics Subject Classification 11G07; 11G15 1. Introduction Let N be a positive integer and consider the classical modular polynomial \Phi_{N}(X,Y)\in\mathbb{Z}[X,Y] which vanishes precisely at pairs (j_{1},j_{2}) of j -invariants of elliptic curves linked by a cyclic N -isogeny. It has degree \deg_{X}\Phi_{N}(X,Y)=\deg_{Y}\Phi_{N}(X,Y):=\psi(N)=N\prod_{p|N}\left(1+\frac{1}{p}\right). While the coefficients of \Phi_{N}(X,Y) are notoriously large [ 1 , 2 , 4 , 6 ] they are also highly divisible by small primes. Our first main result is the following. Theorem 1.1 . Let N>1 , and write \Phi_{N}(X,Y)=\sum_{0\leq i,j\leq\psi(N)}a_{i,j}X^{i}Y^{j}. Then for i+j<\psi(N) the following hold. (1) If 2\nmid N , then v_{2}(a_{i,j})\geq 15(\psi(N)-i-j) . (2) If 3\nmid N , then v_{3}(a_{i,j})\geq 3(\psi(N)-i-j) ; moreover, v_{3}(a_{i,j})\geq\lceil\frac{9}{2}(\psi(N)-i-j)\rceil if N\equiv 1\bmod 3 . (3) If 5\nmid N then v_{5}(a_{i,j})\geq 3(\psi(N)-i-j) . (4) If p\geq 11 and p\nmid N , then v_{p}(a_{i,j})\geq 3(C_{0}(N,p)-i-j) , where C_{0}(N,p):=\mathrm{ord}_{X}(\Phi_{N}(X,0)\bmod p) . When p\leq 5 , this was conjectured by Wang in [ 14 ] , who proved a number of special cases and showed moreover that it suffices to prove Theorem 1.1 for prime N . The result has applications to the study of reduction types of elliptic curves, see [ 15 ] . The polynomials \Phi_{N}(X,Y) have important applications in cryptography and computational number theory. Theorem 1.1 allows us to save some space storing the coefficients of \Phi_{N}(X,Y) , as one only needs to store the factors not predicted by Theorem 1.1 . When N=5 (see Table 1 ) this reduces the number of decimal digits needed from 523 to 298, a 43\% saving. However, for larger N the relative savings dwindle, for example when N=101 we only get a reduction from 6,383,216 to 5,606,370 decimal digits, a mere 12\% saving. Given finer bounds on the sizes of individual coefficients a_{i,j} , Theorem 1.1 might lead to tighter bounds on the Chinese Remainder Theorem primes required for CRT-based algorithms (e.g. [ 3 , 5 , 10 ] ) to compute \Phi_{N}(X,Y) . More generally, we study the coefficients of \Phi_{N}(X+J,Y+J) for certain algebraic numbers J , see Theorem 2.1 below. In particular, when J=1728 we have Theorem 1.2 . Let N>1 and write \Phi_{N}(X+1728,Y+1728)=\sum_{0\leq i,j\leq\psi(N)}a_{i,j}X^{i}Y^{j}. Then for i+j<\psi(N) the following hold. (1) If 2\nmid N , then v_{2}(a_{i,j})\geq 9(\psi(N)-i-j) ; moreover, v_{2}(a_{i,j})\geq 10(\psi(N)-i-j) if N\equiv 1\bmod 4 . (2) If 3\nmid N , then v_{3}(a_{i,j})\geq 6(\psi(N)-i-j). (3) If 7\nmid N then v_{7}(a_{i,j})\geq 2(\psi(N)-i-j) . (4) If p\geq 11 and p\nmid N , then v_{p}(a_{i,j})\geq 2(C_{1728}(N,p)-i-j) , where C_{1728}(N,p):=\mathrm{ord}_{X}\big(\Phi_{N}(X+1728,1728)\bmod p\big) . When J=j(E) is a singular modulus, i.e. the elliptic curve E has complex multiplication by an order of discriminant D in an imaginary quadratic field, then by Proposition 3.2 below, we only get non-trivial divisibility conditions for primes p at which the reduction of E is supersingular, i.e. when \displaystyle\left(\frac{D}{p}\right)\neq 1 . In these cases, we have an explicit expression for C_{J}(N,p) in terms of the theta series of the quaternion order {\mathrm{End}}_{\bar{\mathbb{F}}_{p}}(E) , which is positive only for primes p<|D|N , see Proposition 3.3 . \begin{array}[]{ll}a_{0,0}&=\mathbf{2^{90}\cdot 3^{18}\cdot 11^{9}}\cdot 5^{3}\\ a_{1,0}&=\mathbf{2^{75}\cdot 3^{15}\cdot 11^{6}}\cdot 2^{2}\cdot 3\cdot 5^{3}\cdot 31\cdot 1193\\ a_{1,1}&=\mathbf{2^{60}\cdot 3^{12}\cdot 11^{3}}\cdot-1\cdot 2^{2}\cdot 3\cdot 26984268714163\\ a_{2,0}&=\mathbf{2^{60}\cdot 3^{12}\cdot 11^{3}}\cdot 3\cdot 5^{2}\cdot 13^{2}\cdot 3167\cdot 204437\\ a_{2,1}&=\mathbf{2^{45}\cdot 3^{9}}\cdot 2^{2}\cdot 3\cdot 5^{4}\cdot 53359\cdot 131896604713\\ a_{3,0}&=\mathbf{2^{45}\cdot 3^{9}}\cdot 2^{3}\cdot 5^{2}\cdot 31\cdot 1193\cdot 24203\cdot 2260451\\ a_{2,2}&=\mathbf{2^{30}\cdot 3^{6}}\cdot 3^{2}\cdot 5^{4}\cdot 7\cdot 13\cdot 1861\cdot 6854302120759\\ a_{3,1}&=\mathbf{2^{30}\cdot 3^{6}}\cdot-1\cdot 2\cdot 3\cdot 5^{3}\cdot 327828841654280269\\ a_{4,0}&=\mathbf{2^{30}\cdot 3^{6}}\cdot 3\cdot 5\cdot 13^{2}\cdot 3167\cdot 204437\\ a_{3,2}&=\mathbf{2^{15}\cdot 3^{3}}\cdot 2^{2}\cdot 3\cdot 5^{3}\cdot 2311\cdot 2579\cdot 3400725958453\\ a_{4,1}&=\mathbf{2^{15}\cdot 3^{3}}\cdot 2^{5}\cdot 3\cdot 5^{3}\cdot 12107359229837\\ a_{5,0}&=\mathbf{2^{15}\cdot 3^{3}}\cdot 2^{2}\cdot 3\cdot 5\cdot 31\cdot 1193\\ a_{3,3}&=-1\cdot 2^{2}\cdot 5^{2}\cdot 11\cdot 17\cdot 131\cdot 1061\cdot 169751677267033\\ a_{4,2}&=3\cdot 5^{3}\cdot 167\cdot 6117103549378223\\ a_{5,1}&=-1\cdot 2\cdot 3\cdot 5^{2}\cdot 1644556073\\ a_{6,0}&=1\\ a_{4,3}&=2^{5}\cdot 3\cdot 5^{2}\cdot 197\cdot 227\cdot 421\cdot 2387543\\ a_{5,2}&=2^{5}\cdot 5^{2}\cdot 13\cdot 195053\\ a_{4,4}&=2^{3}\cdot 5^{2}\cdot 257\cdot 32412439\\ a_{5,3}&=-1\cdot 2^{2}\cdot 3^{2}\cdot 5\cdot 131\cdot 193\\ a_{5,4}&=2^{3}\cdot 3\cdot 5\cdot 31\\ a_{5,5}&=-1\\ \end{array} Table 1. Coefficients of \Phi_{5}(X,Y)=\sum_{i,j}a_{i,j}X^{i}Y^{j} with factors predicted by Theorem 1.1 in bold 2. Proof of the main results Let K be a complete valued field with valuation v , valuation ring A , uniformizer \pi and algebraically closed residue field A/\pi of characteristic p>0 . For N>1 and J\in A , we define C_{J}(N,v):=\mathrm{ord}_{X}\big(\Phi_{N}(X+J,J)\bmod\pi\big). We have the following general result, which implies Theorems 1.1 and 1.2 when p\geq 5 . Theorem 2.1 . Let E/K be an elliptic curve with good reduction and J=j(E)\in A . Let N>1 with p\nmid N . Suppose that p\geq 5 or v(J)=0 and let n_{v}=\left\{\begin{array}[]{ll}3&\text{if $v(J)>0$ and $p\geq 5$}\\ 2&\text{if $v(J-1728)>0$ and $p\geq 5$}\\ 1&\text{if $v(J)=v(J-1728)=0$.}\end{array}\right. Then the coefficients of \Phi_{N}(X+J,Y+J)=\sum_{0\leq i,j\leq\psi(N)}a_{i,j}X^{i}Y^{j}\in A[X,Y] satisfy v(a_{i,j})\geq n_{v}(C_{J}(N,v)-i-j) for all i+j<C_{J}(N,v) . 2.1. An interpolation lemma Lemma 2.2 . Let f(Y)=a_{0}+a_{1}Y+\ldots+a_{d}Y^{d}\in K[Y] . Fix n\in\mathbb{Z} and let y_{0},y_{1},\ldots,y_{d}\in K be such that (1) v(y_{0})=v(y_{2})=\cdots=v(y_{d})=n , (2) v(y_{k}-y_{l})=n for all k\neq l . Then v(a_{j})\geq\min_{0\leq k\leq d}v(f(y_{k}))-nj\quad\text{for all $j=0,1,2,\ldots,d$}. Conversely, if v(a_{j})\geq B-nj for all j , then clearly v(f(y_{k}))\geq B . Proof. We solve for the coefficients a_{j} in the linear system a_{0}+a_{1}y_{k}+\cdots+a_{d}y_{k}^{d}=f(y_{k}),\quad k=0,1,2,\ldots d. By Cramer’s rule, we get a_{j}=\frac{M_{j}}{V} , where V=\det(y_{k}^{i})_{0\leq k,i\leq d}=\pm\prod_{k<i}(y_{k}-y_{i}) is the Vandermonde determinant and M_{j} is the determinant where the j th column of V has been replaced by (f(y_{k}))_{0\leq k\leq d} . By assumption, we have v(V)=\sum_{k<i}v(y_{k}-y_{i})=\frac{d(d+1)}{2}n . Factoring out suitable powers of \pi from the columns of M_{j} , we find that v(M_{j})\geq\left(\frac{d(d+1)}{2}-j\right)n+\min_{0\leq k\leq d}v(f(y_{k})). The result follows. ∎ Our main tool is the following result. Proposition 2.3 . Let N>1 with p\nmid N . Let n\geq 1 and suppose that there exist elliptic curves E_{k}/K , k=0,2,\ldots,\psi(N) satisfying the following conditions: (1) Each E_{k} has good reduction; (2) v(j(E_{k})-J)=v(j(E_{k})-j(E_{l}))=n for all k\neq l ; (3) For every k and every elliptic curve \tilde{E}_{k} linked to E_{k} by a cyclic isogeny of degree N , we have v(j(\tilde{E}_{k})-j(E_{k}))>0\Longrightarrow v(j(\tilde{E}_{k})-j(E_{k}))\geq n. Then the coefficients of \Phi_{N}(X+J,Y+J)=\sum_{0\leq i,j\leq\psi(N)}a_{i,j}X^{i}y^{j}\in A[X,Y] satisfy v(a_{i,j})\geq n(C_{J}(N,v)-i-j) for all i+j<C_{J}(N,v) . Proof. Write \displaystyle\Phi_{N}(X+J,Y+J)=b_{0}(Y)+b_{1}(Y)X+\cdots+b_{\psi(N)-1}(Y)X^{\psi(N)-1}+X^{\psi(N)} \displaystyle b_{i}(Y)=a_{i,0}+a_{i,1}Y+\cdots+a_{i,\psi(N)}Y^{\psi(N)},\quad i=0,\ldots,\psi(N). For each k , let y_{k}=j(E_{k})-J . The roots of \Phi_{N}(X,y_{k}+J) are the j -invariants of elliptic curves E_{k,m} linked to E_{k} by a cyclic N -isogeny. Since v(N)=0 , E[N] is unramified and these elliptic curves and isogenies are all defined over K . By definition, C_{J}(N,v) of these roots j(E_{k,m}) , m=1,2,\ldots,C_{J}(N,v) , satisfy v(j(E_{k,m})-J)>0 , so v(j(E_{k,m})-J)\geq v(j(E_{k,m})-j(E_{k}))\geq n , and the rest satisfy v(j(E_{k,m})-J)=0 . The coefficients b_{i}(y_{k}) of \Phi_{N}(X+J,y_{k}+J) are symmetric forms in the roots j(E_{k,m})-J which satisfy v(j(E_{k,m})-J)\geq n for m=1,2,\ldots,C_{J}(N,v) , so it follows that v(b_{i}(y_{k}))\geq n(C_{J}(N,v)-i),\quad i=0,1,\ldots,C_{J}(N,v). Now applying Lemma 2.2 to the polynomials b_{i}(Y) with the interpolation points y_{k} completes the proof.

Read the complete text