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