CoCalc Public Fileswww / 168 / notes / 2005-10-17 / cong.sageOpen with one click!
Author: William A. Stein
Compute Environment: Ubuntu 18.04 (Deprecated)
1
"""
2
Functions related to the congruent number problem for elliptic curves.
3
4
AUTHOR: William Stein, 2005-10-17
5
6
EXAMPLES:
7
sage: attach "cong.sage"
8
sage: cong_number_sets(101)
9
([], [])
10
sage: is_conj_congruent_number(101)
11
True
12
sage: is_congruent_number(101)
13
True
14
sage: print conj_congruent_number_list(30)
15
[5, 6, 7, 13, 14, 15, 20, 21, 22, 23, 24, 28, 29, 30]
16
sage: cong_number_curve(101)
17
Elliptic Curve defined by y^2 = x^3 - 10201*x over Rational Field
18
sage: congruent_curve_gens(101)
19
Entering qsieve::search: y^2 = 1x^3 + 0x^2 + -10201x^1 + 0
20
...
21
sage: P = _[0]
22
sage: congruent_triangle(P)
23
(44538033219/1326635050,
24
267980280100/44538033219,
25
2015242462949760001961/59085715926389725950)
26
sage: congruent_triangle(2*P)
27
(-3808424574270625821973109905486908673845521/238144087377294983538196567899844505175900,
28
-48105105650213586674715706715768590045531800/3808424574270625821973109905486908673845521,
29
18482628628473862825682187406224713731933103369206814890394108346849598187226371761441/906953794584941364348309838871418957694907021279988390325859242498283526441532143900)
30
"""
31
32
def cong_number_sets(n):
33
"""
34
Given a positive integer n, returns the two sets appearing in the
35
conjectural criterion for when a number is congruent.
36
"""
37
n = ZZ(n)
38
n = ZZ(prod([p for p, e in n.factor() if e%2 == 1]))
39
40
if n % 2 == 0: # even case
41
E = [] # with c even
42
O = [] # with c odd
43
a_bound = (sqrt(n/8) + 1).integer_part()
44
c_bound = (sqrt(n)/4 + 1).integer_part()
45
half_n = n//2
46
for c in range(-c_bound, c_bound+1):
47
c_square = c^2
48
for a in range(-a_bound, a_bound+1):
49
a_square = a^2
50
z = half_n - 4*a_square - 8*c_square
51
try:
52
b = z.square_root()
53
if b.denominator() == 1:
54
b = b.numerator()
55
assert 4*a^2 + b^2 + 8*c^2 == n/2
56
if c % 2 == 0:
57
E.append((a,b,c))
58
else:
59
O.append((a,b,c))
60
except ValueError:
61
pass
62
else:
63
E = [] # with c even
64
O = [] # with c odd
65
a_bound = (sqrt(n/2)+1).integer_part()
66
c_bound = (sqrt(n/8) + 1).integer_part()
67
for c in range(-c_bound, c_bound+1):
68
c_square = c^2
69
for a in range(-a_bound, a_bound+1):
70
a_square = a^2
71
z = n - 2*a_square - 8*c_square
72
try:
73
b = z.square_root()
74
if b.denominator() == 1:
75
b = b.numerator()
76
assert 2*a^2 + b^2 + 8*c^2 == n
77
if c % 2 == 0:
78
E.append((a,b,c))
79
else:
80
O.append((a,b,c))
81
except ValueError:
82
pass
83
return E, O
84
85
def is_conj_congruent_number(n):
86
"""
87
Returns True if n is conjecturally a congruent number, according
88
to the Birch and Swinnerton-Dyer conjecture.
89
"""
90
E, O = cong_number_sets(n)
91
return len(E) == len(O)
92
93
def is_congruent_number(n):
94
"""
95
Returns True if n is provably a congruent number. This computes
96
the rank of the corresponding elliptic curve.
97
"""
98
return cong_number_curve(n).rank() > 0
99
100
def conj_congruent_number_list(bound):
101
"""
102
Returns the conjectural congruent numbers up to a given bound.
103
"""
104
return [n for n in range(1,bound+1) if is_conj_congruent_number(n)]
105
106
def cong_number_curve(n):
107
"""
108
Returns the elliptic curve corresponding to the integer n. This
109
curve has positive rank if and only if n is a congruent number.
110
"""
111
return EllipticCurve([-n^2,0])
112
113
def congruent_curve_gens(n, verbose=True):
114
"""
115
Returns generators for the Mordell-Weil group of the elliptic
116
curve corresponding to n.
117
"""
118
E = cong_number_curve(n)
119
return E.gens(verbose=verbose)
120
121
def congruent_triangle(P):
122
"""
123
Returns the triangle corresponding to the point P on a congruent
124
number elliptic curve. The point P must have nonzero y coordinate.
125
"""
126
m = P.curve().a_invariants()[3]
127
n = (-m).square_root()
128
(x, y) = (P[0],P[1])
129
if y == 0:
130
raise ArithmeticError, "point does not define a rational right triangle"
131
T = ((n^2-x^2)/y, -2*x*n/y, (n^2+x^2)/y)
132
assert (T[0]^2 + T[1]^2 == T[2]^2), "bug in program."
133
return T
134
135
def point_from_triangle(a,b,c):
136
"""
137
Return the point on $y^2=x^3-n^2x$ corresponding to the
138
right triangle with side lengths $a,b,c$.
139
"""
140
n = a*b/2
141
E = EllipticCurve([-n^2, 0])
142
return E([-n*b/(a+c), 2*n^2/(a+c)])
143
144
145
146