Division polynomials $\psi_n$ of the curve $y^2=x^3+Ax+B$

edit · history · discussion · files · short url · elliptic curves polynomial number theory

Polynomials

$n$

$\psi_n(x,y)$

2*y

3*x^4 + 6*x^2*A - A^2 + 12*x*B

4*x^6*y + 20*x^4*y*A - 20*x^2*y*A^2 + 80*x^3*y*B - 4*y*A^3 - 16*x*y*A*B - 32*y*B^2

5*x^12 + 62*x^10*A - 105*x^8*A^2 + 380*x^9*B - 300*x^6*A^3 + 240*x^7*A*B - 125*x^4*A^4 - 696*x^5*A^2*B - 240*x^6*B^2 - 50*x^2*A^5 - 80*x^3*A^3*B - 1920*x^4*A*B^2 + A^6 - 100*x*A^4*B - 240*x^2*A^2*B^2 - 1600*x^3*B^3 - 32*A^3*B^2 - 640*x*A*B^3 - 256*B^4

6*x^16*y + 144*x^14*y*A - 728*x^12*y*A^2 + 1344*x^13*y*B - 2576*x^10*y*A^3 - 1884*x^8*y*A^4 - 9152*x^9*y*A^2*B - 5376*x^10*y*B^2 - 2576*x^6*y*A^5 + 1536*x^7*y*A^3*B - 39744*x^8*y*A*B^2 - 728*x^4*y*A^6 - 6720*x^5*y*A^4*B - 5376*x^6*y*A^2*B^2 - 44544*x^7*y*B^3 + 144*x^2*y*A^7 - 3584*x^3*y*A^5*B - 8064*x^4*y*A^3*B^2 - 32256*x^5*y*A*B^3 + 6*y*A^8 + 192*x*y*A^6*B - 3072*x^2*y*A^4*B^2 - 25088*x^3*y*A^2*B^3 - 10752*x^4*y*B^4 + 192*y*A^5*B^2 - 512*x*y*A^3*B^3 - 27648*x^2*y*A*B^4 + 1024*y*A^2*B^4 - 12288*x*y*B^5

7*x^24 + 308*x^22*A - 2954*x^20*A^2 + 3944*x^21*B - 19852*x^18*A^3 - 112*x^19*A*B - 35231*x^16*A^4 - 92568*x^17*A^2*B - 42896*x^18*B^2 - 82264*x^14*A^5 - 31808*x^15*A^3*B - 571872*x^16*A*B^2 - 111916*x^12*A^6 - 161840*x^13*A^4*B - 615360*x^14*A^2*B^2 - 829696*x^15*B^3 - 42168*x^10*A^7 - 608160*x^11*A^5*B - 297472*x^12*A^3*B^2 - 2132480*x^13*A*B^3 + 15673*x^8*A^8 - 425712*x^9*A^6*B - 1192800*x^10*A^4*B^2 - 2603776*x^11*A^2*B^3 - 928256*x^12*B^4 + 14756*x^6*A^9 - 53824*x^7*A^7*B - 831936*x^8*A^5*B^2 - 3727360*x^9*A^3*B^3 - 3293696*x^10*A*B^4 + 1302*x^4*A^10 + 57288*x^5*A^8*B - 190400*x^6*A^6*B^2 - 1314560*x^7*A^4*B^3 - 7069440*x^8*A^2*B^4 - 1555456*x^9*B^5 + 196*x^2*A^11 + 1680*x^3*A^9*B + 134400*x^4*A^7*B^2 - 168448*x^5*A^5*B^3 - 2293760*x^6*A^3*B^4 - 7127040*x^7*A*B^5 - A^12 + 392*x*A^10*B + 3696*x^2*A^8*B^2 + 152320*x^3*A^6*B^3 + 394240*x^4*A^4*B^4 - 3698688*x^5*A^2*B^5 - 2809856*x^6*B^6 + 160*A^9*B^2 + 7168*x*A^7*B^3 + 96768*x^2*A^5*B^4 + 831488*x^3*A^3*B^5 - 3039232*x^4*A*B^6 + 3328*A^6*B^4 + 64512*x*A^4*B^5 + 544768*x^2*A^2*B^6 - 802816*x^3*B^7 + 24576*A^3*B^6 + 229376*x*A*B^7 + 65536*B^8

Definition

Let $E$ be the short Weierstrass curve $y^2=x^3+Ax+B$ with formal coefficients $A$ and $B$. The entry is the $n$-th division polynomial $\psi_n$ [1] of $E$, stored as an element of $\mathbb{Z}[x,y,A,B]$ that is linear in $y$.

Parameters

$n$

— division-polynomial index ($n\geq1$)

Formulas

(1)

$\psi_0=0$, $\psi_1=1$, $\psi_2=2y$, $\psi_3=3x^4+6Ax^2+12Bx-A^2$, and $\psi_4=4y(x^6+5Ax^4+20Bx^3-5A^2x^2-4ABx-A^3-8B^2)$.

(2)

For $m\geq2$, $\psi_{2m+1}=\psi_{m+2}\psi_m^3-\psi_{m-1}\psi_{m+1}^3$. For $m\geq3$, $\psi_{2m}=(\psi_m/\psi_2)(\psi_{m+2}\psi_{m-1}^2-\psi_{m-2}\psi_{m+1}^2)$, where $\psi_m/\psi_2$ is taken in the coordinate ring of $E$.

(3)

If $f_n$ is PARI/GP's elldivpol(E,n) or Sage's default E.division_polynomial(n) [3] for the short model $E:y^2=x^3+Ax+B$, then $f_n(x)=\psi_n(x)$ for odd $n$ and $f_n(x)=\psi_n(x,y)\cdot2y$ for even $n$. Sage's E.division_polynomial_0(n) [3] gives $\psi_n$ for odd $n$ and $\psi_n/(2y)$ for even $n$.

Comments

(4)

This is the full division polynomial $\psi_n$. For even $n$ it includes the factor $\psi_2=2y$ rather than the $x$-only quotient $\psi_n/\psi_2$.

(5)

The variables are named $x$, $y$, $A$ and $B$. Specialise $A$ and $B$ to elements of a field $K$ whose characteristic does not divide $2n$, with $4A^3+27B^2\ne0$. As a function on $E$, $\psi_n$ then vanishes exactly at the points $P\ne O$ of $E(\overline{K})$ with $nP=O$; for odd $n$, its roots in $x$ are the $x$-coordinates of those points.

Programs

(P1)

Sage

S.<A,B> = QQ[]
F = S.fraction_field()
E = EllipticCurve(F, [A, B])
R.<x,y> = S[]
n = 8
q = sum(R(S(c))*x^i for i, c in enumerate(E.division_polynomial_0(n).list()))
psi = q if n % 2 else 2*y*q
psi       # the row for n = 8, in the table's convention

Links

[1]

Wikipedia: Division polynomials

[2]

PARI/GP manual: elldivpol

[3]

SageMath reference: division_polynomial

Similar tables

Division polynomials $\psi_n$ of elliptic curves over $\mathbb{Q}$ — holds division polynomials for individual curves over $\mathbb{Q}$ in their reduced global minimal Weierstrass models; this table keeps $A$ and $B$ formal in a short model

Highest known ranks of elliptic curves over $\mathbb{Q}$ with prescribed torsion subgroup — records the highest known rank for each rational torsion subgroup, while the roots of $\psi_n$ detect torsion points on individual curves

Data properties

Entries are of type: integral polynomial

How well the digits are known: exact

Table is complete: no (it holds every $n$ with $1\leq n\leq7$)

How they were obtained:

The generator computes in the coordinate ring of $y^2=x^3+Ax+B$, representing every polynomial as $u(x,A,B)+y\,v(x,A,B)$ and reducing products by the exact relation $y^2=x^3+Ax+B$.

It verifies the degree and leading coefficient of every stored $\psi_n$ and checks specialisations at five nonsingular integer pairs $(A,B)$ against PARI/GP's exact elldivpol [2]; for even $n$, the comparison uses the convention in Formula (3).