math 414: 20100308 -- congruent number problem

697 days ago by wstein

The Congruent Number Problem

Connection with Elliptic Curves (proof by computer)

Explicit Bijection

In fact, there is a bijection between


 A = \left\{(a,b,c) \in \mathbf{Q}^3 \,:\, \frac{ab}{2} = n,\, a^2 + b^2 = c^2\right\}

and

 B = \left\{(x,y) \in \mathbf{Q}^2 \,:\, y^2 = x^3 - n^2 x, \,\,\text{with } y \neq 0\right\}

given by the maps

  f(a,b,c) = \left(-\frac{nb}{a+c},\,\, \frac{2n^2}{a+c}\right)

and

  g(x,y) = \left(\frac{n^2-x^2}{y},\,\,-\frac{2xn}{y},\,\, \frac{n^2+x^2}{y}\right).

Define bijection between rational right triangles with area n and points on the elliptic curve y^2=x^3-n^2x with y\neq 0.
def f(a,b,c, n): return (-n*b/(a+c), 2*n^2/(a+c)) def g(x,y, n): return ((n^2-x^2)/y, -2*x*n/y, (n^2+x^2)/y) 
       

Use computer to verify that this is a bijection.
R.<a,b,c,n> = QQ[] x,y = f(a,b,c, n) g(x,y, n) 
        
((a^2 - b^2 + 2*a*c + c^2)/(2*a + 2*c), b, (a^2 + b^2 + 2*a*c +
c^2)/(2*a + 2*c))
((a^2 - b^2 + 2*a*c + c^2)/(2*a + 2*c), b, (a^2 + b^2 + 2*a*c + c^2)/(2*a + 2*c))

By working in the quotient polynomial ring and avoiding fractions we get that the composition g \circ f is the identity map.
Q = R.quotient([a^2 + b^2 - c^2, a*b-2*n]) v1 = g(x,y, n) v2 = (a,b,c) for i in range(3): print Q(v1[i].numerator() - v2[i].numerator()*v1[i].denominator()) 
        
0
0
0
0
0
0
R.<x,y,n> = QQ[] a, b, c = g(x,y,n) 
       
Q = R.quotient([y^2 - (x^3-n^2*x)]) v1 = f(a,b,c, n) v2 = (x,y) for i in range(2): print Q(v1[i].numerator() - v2[i].numerator()*v1[i].denominator()) 
        
0
0
0
0

So we know that the claimed bijections are valid.
 
       
def cong(n): G = EllipticCurve([-n^2,0]).gens() if len(G) == 0: return False x,y,_ = G[0] return ((n^2-x^2)/y,-2*x*n/y,(n^2+x^2)/y) 
       
for n in [1..15]: print n, cong(n) 
        
1 False
2 False
3 False
4 False
5 (3/2, 20/3, 41/6)
6 (3, 4, 5)
7 (-24/5, -35/12, 337/60)
8 False
9 False
10 False
11 False
12 False
13 (323/30, 780/323, 106921/9690)
14 (-8/3, -21/2, 65/6)
15 (4, 15/2, 17/2)
1 False
2 False
3 False
4 False
5 (3/2, 20/3, 41/6)
6 (3, 4, 5)
7 (-24/5, -35/12, 337/60)
8 False
9 False
10 False
11 False
12 False
13 (323/30, 780/323, 106921/9690)
14 (-8/3, -21/2, 65/6)
15 (4, 15/2, 17/2)
@interact def _(n=6, triangles=(1..10), maxtime=(3..30)): x,y = var('x,y') C = EllipticCurve(y^2 == x^3 - n^2*x) try: alarm(maxtime) t = walltime() G = C.gens() print "time = %.2f seconds"%walltime(t) except RuntimeError: print "Sage is unable to provably find generators" return except KeyboardInterrupt, msg: print "Too hard -- timed out after %s seconds"%maxtime return html("rank = %s\n\n"%len(G)) if len(G) == 0: print "%s is not a congruent number"%n; return def g(x,y,n): return ((n^2-x^2)/y, -2*x*n/y, (n^2+x^2)/y) P = G[0] html('<h3><font color="red">Rational Right Triangles with Area %s</font></h3>'%n) for i in [1..triangles]: a,b,c = g((i*P)[0], (i*P)[1], n) html("(a,b,c) = $%s$\n"%latex((a,b,c))) 
       

Click to the left again to hide and once more to show the dynamic interactive window

Tunnell's Criterion:
def cong_number_sets(n): """ Given a positive integer n, returns the two sets appearing in the conjectural criterion for when a number is congruent. """ n = ZZ(n) n = ZZ(prod([p for p, e in n.factor() if e%2 == 1])) if n % 2 == 0: # even case E = [] # with c even O = [] # with c odd a_bound = floor(sqrt(n/8) + 1) c_bound = floor(sqrt(n)/4 + 1) half_n = n//2 for c in range(-c_bound, c_bound+1): c_square = c^2 for a in range(-a_bound, a_bound+1): a_square = a^2 z = half_n - 4*a_square - 8*c_square try: b = z.sqrt(extend=False) if b.denominator() == 1: b = b.numerator() assert 4*a^2 + b^2 + 8*c^2 == n/2 if c % 2 == 0: E.append((a,b,c)) else: O.append((a,b,c)) except ValueError: pass else: E = [] # with c even O = [] # with c odd a_bound = floor(sqrt(n/2)+1) c_bound = floor(sqrt(n/8) + 1) for c in range(-c_bound, c_bound+1): c_square = c^2 for a in range(-a_bound, a_bound+1): a_square = a^2 z = n - 2*a_square - 8*c_square try: b = z.sqrt(extend=False) if b.denominator() == 1: b = b.numerator() assert 2*a^2 + b^2 + 8*c^2 == n if c % 2 == 0: E.append((a,b,c)) else: O.append((a,b,c)) except ValueError: pass return E, O def is_conj_cong_number(n): """ Returns True if n is conjecturally a congruent number, according to the Birch and Swinnerton-Dyer conjecture. """ E, O = cong_number_sets(n) return len(E) == len(O) 
       

First congruent number \equiv 3 \pmod{8}
time is_conj_cong_number(219) 
        
True
Time: CPU 0.02 s, Wall: 0.03 s
True
Time: CPU 0.02 s, Wall: 0.03 s
219 % 8 
        
3
3
cong(219) 
        
(55/4, 1752/55, 7633/220)
(55/4, 1752/55, 7633/220)

This year isn't congruent:
time is_conj_cong_number(2010) 
        
False
Time: CPU 0.02 s, Wall: 0.02 s
False
Time: CPU 0.02 s, Wall: 0.02 s
cong(2010) 
        
False
False
time is_conj_cong_number(2011) 
        
False
Time: CPU 0.02 s, Wall: 0.04 s
False
Time: CPU 0.02 s, Wall: 0.04 s
time is_conj_cong_number(2012) 
        
True
Time: CPU 0.02 s, Wall: 0.02 s
True
Time: CPU 0.02 s, Wall: 0.02 s
cong(2012) 
        
Traceback (click to the left of this block for traceback)
...
Try increasing descent_second_limit then trying this command again.
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_63.py", line 9, in <module>
    open("___code___.py","w").write("# -*- coding: utf-8 -*-\n" + _support_.preparse_worksheet_cell(base64.b64decode("Y29uZygyMDEyKQ=="),globals())+"\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/tmp/tmptRTSZC/___code___.py", line 3, in <module>
    cong(_sage_const_2012 )
  File "", line 1, in <module>
    
  File "/tmp/tmpKsNmc0/___code___.py", line 4, in cong
    G = EllipticCurve([-n**_sage_const_2 ,_sage_const_0 ]).gens()
  File "/home/wstein/sage/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_rational_field.py", line 1931, in gens
    "\nTry increasing descent_second_limit then trying this command again."
RuntimeError: Unable to compute the rank, hence generators, with certainty (lower bound=0, generators found=[]).  This could be because Sha(E/Q)[2] is nontrivial.
Try increasing descent_second_limit then trying this command again.
E = EllipticCurve([-2012^2,0]) 
       
E.analytic_rank() 
        
1
1