# On the Equationy2=x3-pqx

Authors: Iftikhar A. Burhanuddin; Ming-Deh A. Huang
Journal: Journal of Numbers
 (2014)

---

## Abstract

We consider certain quartic twists of an elliptic curve. We establish the rank of these curves under the Birch and Swinnerton-Dyer conjecture and obtain bounds on the size of Shafarevich-Tate group of these curves. We also establish a reduction between the problem of factoring integers of a certain form and the problem of computing rational points on these twists.


---

## Body

## 1. Introduction

In this paper, we investigate certain quartic twists of the elliptic curvey2=x3-x and present some of their interesting properties. Specifically, we consider the family of elliptic curves ED:y2=x3-Dx, where D=pq with p and q distinct prime numbers, p≡q≡3mod⁡16. These elliptic curves have complex multiplication by Q(i). The 2-torsion point (0,0) generates the torsion subgroup of the Mordell-Weil group ED(Q). Our first result concerns the rank of ED(Q) and an interesting valuational property of points in ED(Q). More specifically we obtain the following.Theorem 1.
LetED:y2=x3-Dx, where D=pq with p and q distinct prime numbers and p≡q≡3mod⁡16. Then the rank of the Mordell-Weil group ED(Q) is less than or equal to 1. If the rank is one, then for every point R of ED(Q) which is not in 〈(0,0)〉+2ED(Q), the p-adic and q-adic valuations of x(R) must have opposite parity. Moreover, under the Birch and Swinnerton-Dyer conjecture, the rank of ED(Q) is one.The situation wherep and q do not satisfy the congruence condition in Theorem 1 is less clear. Recently Li and Zeng [1] showed, under the Birch and Swinnerton-Dyer conjecture, that, for D=pq where p and q are distinct odd primes, there exists an elliptic curve E2rD:y2=x3-2rDx, where r depends on the classes of p and q modulo 8, such that the elliptic curve has rank 1 and the valuations at p and q of x-coordinate x([k]Q) are not equal for odd k, where Q is a generator of the Mordell-Weil group E2rD(Q).By assuming conjectures, in addition to the Birch and Swinnerton-Dyer conjecture, we also obtain the following.Theorem 2.
LetED:y2=x3-Dx, where D=pq with p and q distinct prime numbers and p≡q≡3mod⁡16. Then the following holds under the Birch and Swinnerton-Dyer conjecture, the elliptic curve analog of the Brauer-Siegel theorem, and the Hardy-Littlewood’s F conjecture. For every ϵ>0 there are infinitely many ED with D=pq and p and q prime with p≡q≡3mod⁡16, such that #III(ED)≫|Δ(ED)|1/12-ϵ, where III(ED) is the Shafarevich-Tate group of ED and Δ(ED) is the minimal discriminant of ED.LetE be an elliptic curve over Q. The naïve height of the elliptic curve is defined to be
(1)h*(E)=112log⁡max⁡{|c4(E)|3,|c6(E)|2},
where c4(E) and c6(E) are the c-invariants associated to a minimal model of E.LetF vary over a family of number fields of a fixed extension degree over Q. Let ΔF, hF, and RF denote, respectively, the discriminant, the class number, and the regulator of F. The Brauer-Siegel theorem [2] states that if |ΔF| tends to infinity then log⁡hFRF~log⁡|ΔF|1/2. The elliptic curve analog of the Brauer-Siegel Theorem [3] asserts that, for a family of elliptic curves defined over a fixed number field K such that the height h*(E) tends to infinity, log⁡(#III(E)Reg(E))~h*(E).The Hardy and Littlewood conjectureF [4] concerns polynomials of the form ax2+bx+c, where a,b,c are integers and a is positive. It asserts that if the greatest common divisor of the coefficients is 1 and b2-4ac is not a square, and either a+b or c is odd, then asymptotically, the number P(n) of primes less than n of the form ax2+bx+c is given by λ(n/alog⁡n), where λ is a constant depending only on a,b,c.The curveED has y2=x3-Dx as a minimal model, with discriminant Δ=64D3 and naïve height h*=(1/4)log⁡48D=(1/12)log⁡|Δ|+(1/4)log⁡12. The elliptic analog of Brauer-Siegel implies that #III≪|Δ|1/12+ϵ, and Theorem 2 implies that the bound is essentially tight.We remark that a result of de Weger [5] demonstrates that for every ϵ>0 there exist infinitely many elliptic curves of rank 0 with
(2)#III(E)≫|Δ(E)|1/12-ϵ,
assuming the BSD conjecture in the rank 0 case and a conjecture of Shintani and Shimura that the Riemann hypothesis holds for the Ranking-Selberg zeta function associated to the weight 3/2 modular form associated to an elliptic curve by the Shintani-Shimura lift.The result was improved in [6] where it was shown that, for every ϵ>0, there are infinitely many elliptic curves E of rank 0 such that
(3)#III(E)≫|Δ(E)|(1/2)-ϵ
assuming the BSD conjecture in the rank 0 case and the conjecture of Shintani and Shimura.The proof of Theorem1 is given in Section 2. The proof of Theorem 2 is given in Section 3. By Theorem 1, any point R of the Mordell-Weil group ED(Q) which is not in 〈(0,0)〉+2ED(Q) must behave differently with respect to p-adic and q-adic valuations. This sets the stage for reductions between the problem of factoring integers of the form D and the problem of computing nontorsion rational points on ED. This is discussed in Section 4. In one direction, it is shown that how given a rational nontorsion point P, the factors p and q of D can be found in time polynomial in the height of P. We note that the cases where ED have rational points of small height are those that give rise to large Shafarevich-Tate groups (see Section 3).


## 2. Proof of Theorem1

This section is devoted to the proof of Theorem1. Part of the analysis closely follows Sections X.6 and X.4.9 from Silverman’s book [7]. First we recall some facts that follow as the exposition in Example X.4.8 and Proposition X.4.9 applies to our situation. We also adopt the notation there.LetED over Q be the elliptic curve
(4)ED:y2=x3-Dx,
where D∈Z (the subscript D will be dropped when it is clear from the context). Then ED is isogenous to the elliptic curve
(5)ED′:Y2=X3+4DX
via the isogeny ϕ:ED→ED′,(x,y)↦(y2/x2,-y(D+x2)/x2). The kernel E[ϕ] of ϕ consists of (0,0) and O, the identity of ED. Let ϕ^:ED′→ED be the dual isogeny of ϕ.LetMQ be the set of primes of Z and ∞. Let S⊂MQ that consists of ∞ and all primes dividing 2 or D. Let Qν denote the completion of Q with respect to the absolute value associated to ν∈S. In particular, Q∞ denotes R and for ν∈S∖{∞}, Qν denotes the ν-adic numbers. Let Q(S,2) be the subgroup of Q*/Q*2 defined as follows:
(6)Q(S,2):={b∈Q*Q*2∣ν(b)≡0mod⁡2,∀ν∉S}.Now letD=pq, where p and q are odd and distinct primes, and the group Q(S,2) is generated by -1, 2, p and q.LetWC(E) denote the Weil-Châtelet group of E, the group of equivalence classes of homogeneous spaces for E over Q. For each d∈Q(S,2), the corresponding homogeneous spaces Cd∈WC(E) and Cd′∈WC(E′), also referred to as quartics, are given by the equations
(7)Cd:dw2=d2+4pqz4,Cd′:dW2=d2-pqZ4.IdentifyingE[ϕ] with μ2, we have H1(GQ,E[ϕ])≅Q*/Q*2, under which the ϕ-Selmer group can be viewed as a subset of Q(S,2) as follows:
(8)S(ϕ)(E)≅{d∈Q(S,2):Cd(Qν)≠∅,∀ν∈S}.
The ϕ^-Selmer group S(ϕ^)(E′) has an analogous isomorphism where Cd is replaced by Cd′.There is the well-known exact sequence:(9)0⟶E′(Q)ϕ(E(Q))⟶S(ϕ)(E)⟶III(EQ)[ϕ]⟶0,
where the map E′(Q)/ϕ(E(Q))→S(ϕ)(E) is defined through the connecting homomorphism δ:E′(Q)→H1(GQ,E[ϕ]) with δ(E′(Q))⊂S(ϕ)(E). Under the isomorphism H1(GQ,E[ϕ])≅Q*/Q*2 we have δ(0,0)=4D and δ(x,y)=x if x≠0,∞.Similarly there is an injectionf:E(Q)/ϕ^(E′(Q))→S(ϕ^)(E′) sending (0,0) to -16D and (x,y) to x if x≠0,∞.Thus, the images of(0,0), the 2-torsion point of E′(Q), and E(Q) in the Selmer groups are given by
(10)pq∈S(ϕ)(E),-pq∈S(ϕ^)(E′),
respectively.We now restrict our attention to(11)E=ED:y2=x3-Dx,
where D=pq and p and q are distinct primes such that p≡q≡3mod⁡16. Also swapping p and q if necessary we have (p/q)=(-q/p)=1.Below is a descent analysis on the2-isogenous elliptic curves E and E′. We would like to thank an anonymous referee for valuable suggestions, which we adopt here. Our original analysis can be found in [8, Appendix B].WhenK=Q or Qν, we have an injection
(12)f:E(K)ϕ^(E′(K))⟶K*K*2
induced from the connecting homomorphism δ:E′(K)→H1(GK,E[ϕ])≅K*/K*2 sending (0,0) to -16D and (x,y) to x if x≠0,∞. When K=Qν, we write S(ϕ^)(K) for the actual image of f. By virtue of the exact sequence
(13)0⟶E′(K)ϕ(E(K))⟶H1(GK,E[ϕ])⟶WC(E)[ϕ]⟶0
it follows that S(ϕ^)(E′) consists of a∈Q(S,2) with localizations in S(ϕ^)(Qν) for all ν.SupposeP∈E(Qν), ν being equal to 2, or a place of good reduction then 2∣ν(x(P)) and we find that f(P)∈Zν*.Forν=p or ν=q, E has bad, type III reduction. The group E(Qν) is generated by E0(Qν) and the point T=(0,0) [7, Table 15.1]. Since both E1(Qν)≅Zν and E0(Qν)/E1(Qν)≅E¯ns(Fν)≅Fν (the last isomorphism due to the type of reduction being additive) are divisible by 2, so is the group E0(Qν). It follows that S(ϕ^)(Qν)=〈-pq〉. We recall that it is assumed that p≡q≡3mod⁡16, labeled so that (p/q)=(-q/p)=1. Since p and -q are squares modulo q and modulo p, respectively, we have illustrated that S(ϕ^)(Qp)=〈p〉 and S(ϕ^)(Qq)=〈-q〉.Ford∈Q(S,2) to be an element of S(ϕ^)(E′), it is necessary and sufficient that when localized it maps to a unit in S(ϕ^)(Qv) when ν is 2 and when ν is a place of good reduction and to an element of S(ϕ^)(Qv) when ν is p and q. It follows that the Selmer group S(ϕ^)(E′) is 〈p,-q〉.Next, we consider the groupS(ϕ)(E). If P∈E′(R) then x(P)≥0. This fact coupled with reasoning similar to the preceding paragraphs shows that S(ϕ)(E)=〈pq〉.From the exact sequences(14)0⟶E′(Q)ϕ(E(Q))⟶S(ϕ)(E)⟶III(EQ)[ϕ]⟶00⟶E(Q)ϕ^(E′(Q))⟶S(ϕ^)(E′)⟶III(E′Q)[ϕ^]⟶0,0⟶E′(Q)[ϕ^]ϕ(E(Q)[2])⟶E′(Q)ϕ(E(Q))⟶E(Q)2E(Q)⟶E(Q)ϕ^(E′(Q))⟶0
following an analysis similar to that used in proving Proposition X.6.2(c) [7], we obtain
(15)rE+dim2III(EQ)[2]=dim2S(ϕ)(E)+dim2S(ϕ^)(E′)-2=1,
where rE denotes the rank of E(Q) and dim2 is the dimension as a Z/2Z-vector space. In particular, rE≤1.WhenrE=1, then dim2III(EQ)[2]=0. Since
(16)dim2III(EQ)[2]=dim2III(E′Q)[ϕ^]+dim2III(EQ)[ϕ]
it follows that III(E′/Q)[ϕ^] is trivial, so f gives an isomorphism E(Q)/ϕ^(E′(Q))→S(ϕ^)(E′). So the points on E(Q) map onto S(ϕ^)(E′)=〈p,-q〉. Since the image of (0,0) is -pq, we find that, for any point R in E(Q) but not in 〈(0,0)〉+2E(Q), νp(x(R)) and νq(x(R)) have opposite parity.To finish the proof of Theorem1, we need to argue, on BSD, that the elliptic curves ED have Mordell-Weil rank 1. To this end we investigate the zeros of the L-series of E at s=1. For the curves of interest the global root number w(E) can be computed from the formulae in [9] and it equals −1. Evaluating the functional equation ΛE(s) at s=1, we have ΛE(1)=-ΛE(1) and hence ΛE(1)=0. This implies that LE(1)=0; in other words, the analytic rank rEan>0.IfrEan=1; that is, LE(1)(1)≠0, then rE=1, by a result of Kolyvagin [10]. Alternatively, since rE≤1 and rEan>0, it follows from the BSD conjecture that rE=rEan=1.This completes the proof of Theorem1.


## 3. Proof of Theorem2

The curveED has y2=x3-Dx as a minimal model, with discriminant Δ=64D3 and height (1/4)log⁡48D. The 2-torsion point (0,0) generates the torsion subgroup of the Mordell-Weil group ED(Q).LetED′ denote y2=x3+4Dx the isogenous curve of ED, and let Cd′ represent the homogeneous spaces dW2=d2-DZ4 of ED′.One way to compute a rational point ofED is to search for a rational point on the homogeneous spaces: Cp′:W2=p-qZ4,C-q′:-W2=q-pZ4 (assuming (p/q)=1) and this gives us a rational point of ED via the map ψ:Cd′→E,ψ(Z,W)=(d/Z2,dW/Z3). For example if Cp′:W2=p-qZ4 has a rational point (z,w), where the numerator and denominator of z are polynomially bounded in D, then a rational point on ED can be found of canonical height O(log⁡D).We note that in the special case wherep-q is a square the curve ED does have a small rational point (-q,qp-q). Thus if there are infinitely many such pairs of primes p and q, then there are infinitely many ED with D=pq with a rational point of height bounded by O(log⁡D). In the simplest case taking q=3, the question boils down to whether there are infinitely many primes p of the form 3+16n2. The answer is affirmative under Hardy-Littlewood’sF conjecture [4].Thus assuming Hardy-Littlewood’sF conjecture and BSD, there is a subfamily of infinitely many ED such that D=pq with p and q prime and p≡q≡3mod⁡16 such that, for any ϵ, 0<ϵ<1, Reg(ED)<Dϵ for sufficiently large D. Theorem 2 now follows from the elliptic analog of the Brauer-Siegel theorem and the fact that ED has minimal discriminant Δ=64D3 and height (1/4)log⁡48D.


## 4. Implications on Computational Complexity

In Theorem1 we argue that any point R of the Mordell-Weil group ED(Q) which is not in 〈(0,0)〉+2ED(Q) must behave differently with respect to p-adic and q-adic valuations. This sets the stage for reductions between the problem of factoring integers of the form D and the problem of computing nontorsion rational points on ED.We discuss below that how given a rational nontorsion pointP, the factors p and q of D can be found in time polynomial in the height of P.Letden(r) and num(r) be the numerator and denominator of r∈Q, respectively. Let h(r)=log⁡2max⁡(|num(r)|,|den(r)|), the naïve logarithmic height of r∈Q∖{0}. And let h(S) be the naïve logarithmic height of S∈{ED(Q)∖〈(0,0)〉} which is log⁡2max⁡(h(x(S)),h(y(S))).Suppose we are givenP, a nontorsion rational point on ED. A point R∈ED(Q)∖(ED[ϕ]+2ED(Q)) can be constructed by “halving” P using the duplication formula [7, Algorithm 2.3 (d)]. We note that the canonical height of R is not greater than that of P. From the reasoning above we have vp(x(R))≠vq(x(R)). Below we describe how p and q can be recovered from R.Clearing the denominators of pointR, we consider u·x(R), where u=den(x(R))·den(y(R)). (Taking u to be lcm(den(x(R)),den(y(R))) will also suffice for our argument but might lead to trickier analysis). We note that the integer u·x(R) can be viewed as the x-coordinate of a point on the projective curve y2·z=x3-D·x·z2.Sincevp(u·x(R))≠vq(u·x(R)), it follows that computing gcd(u·x(R)/Dk,D) gives us either p or q but neither 1 nor D, where k∈Z≥0 such that Dk∣u·x(R) but Dk+1 does not. Moreover, h(u·x(R))≤3·h(R). Suppose u·x(R)=c·Dk, for c∈Z; then h(u·x(R))=h(c)+k·h(D)≤3·h(R). The fact that h(c)>0 implies k·h(D)≤3·h(R)-h(c)<3·h(R) and hence k<3·h(R)/h(D). The integer k can be found using the usual doubling trick in O(log⁡2k) bits operations. And the running time of the reduction is
(17)O(log⁡2k)·M(3·h(R)),
where M(b) is the bit operations to multiply two b-bits numbers. Therefore the overall time complexity of the reduction is softly linear in the height of the point R for fixed D.Further, suppose that height of the pointP is a polynomial in the height of the elliptic curve ED; then the time complexity of the reduction is polynomial in log⁡2D.We note that in the special case wherep-q is a square the curve ED does have a small rational point (-q,qp-q), and finding such a point is easily reduced to factoring D. Therefore in this case finding a rational point on ED and factoring D are polynomial time equivalent.More generally we remark that one of the procedures to compute a rational point ofED is to search for a rational point on the homogeneous spaces: Cp′:W2=p-qZ4, C-q′:-W2=q-pZ4 (assuming (p/q)=1) and this gives us a rational point of ED via the map ψ:Cd′→E,ψ(Z,W)=(d/Z2,dW/Z3). The knowledge of the two factors p and q allows us to write down the equation of the homogeneous spaces. Moreover suppose either one of the two homogeneous spaces has a small rational point, say Cp′:W2=p-qZ4 has a rational point (w,z) where the numerator and denominator of z are polynomially bounded in log⁡D. Then a rational point (w,z) can be found by exhaustive search (since z is so small), and a rational point of ED can be obtained from such (w,z). Consequently in such cases finding a rational point on ED and factoring D are polynomial time equivalent. Note that these are also cases that give rise to large III groups in Theorem 2.In general it is an interesting open question to determine to what extent finding a rational point onED and factoring D are polynomial time equivalent.In light of the question of finding a rational point onED, it may be interesting to investigate the efficiency of Heegner point computation when restricted to these elliptic curves ED. Assuming BSD we observe the dependence of the Heegner index on #III(ED), which may be big (for instance under the Brauer-Siegel Analogue for elliptic curves). It follows that factoring numbers of the form D by computing a point in ED(Q) via the Heegner point method would be computationally expensive. We refer to [8] for a detailed discussion.



---

*Source: 825634-2014-07-16.xml*