1731-The Congruent Number Problem.sagews

The Congruent Number Problem

• A relevant webpage [aimath.org]

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))

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

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

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)

@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)))

---

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

219 % 8

3

cong(219)

(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

cong(2010)

False

time is_conj_cong_number(2011)

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

cong(2012)

Traceback (most recent call last): File "<stdin>", line 1, in <module> File "_sage_input_63.py", line 9, in <module> exec compile(ur'open("___code___.py","w").write("# -*- coding: utf-8 -*-\n" + _support_.preparse_worksheet_cell(base64.b64decode("Y29uZygyMDEyKQ=="),globals())+"\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in <module> File "/tmp/tmptRTSZC/___code___.py", line 3, in <module> exec compile(ur'cong(_sage_const_2012 )' + '\n', '', 'single') 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