stein-cubics-2011-11-17

186 days ago by WilliamStein

 
       
 
       
 
       
 
       

Solving Cubic Equations


Benedict Gross (Harvard) and William Stein (Univ of Washington)


 November 2011
 
       
 
       
 
       
 
       
 
       
 
       
 
       

Algebraic Equations

Mathematicians solve many types of equations:

x^2 + y^2 = z^2 has solutions (3,4,5), (5,12,13), \ldots.

There are solutions on a Babylonian tablet from 1800 BCE:

There are solutions on a Babylonian tablet from 1800 BCE:

 

 
 
       

Finding all of the solutions    

x^2 + y^2 = z^2 has general solution x=p^2-q^2, y=2pq, z=p^2+q^2.

See this by considering the line of slope t=p/q through (0,-1) intersected with the unit circle.
%hide @interact def _(t=(1/16,1/8,..,1)): t0 = t x,y,t=var('x,y,t') show([x==(1-t^2)/(1+t^2), y==2*t/(1+t^2)]) t = t0 (x,y) = ((1-t^2)/(1+t^2), 2*t/(1+t^2)) a = 1/3 html('<center>') G = circle((0,0), 1, color='blue', thickness=3) G += text("$(0,%s)$"%latex(t), (-.2, t+.2), fontsize=20, color='black') G += text("$(%s,%s)$"%(latex(x),latex(y)), (x+.3, y+.3), fontsize=20, color='black') G += arrow((-1-a,-t*a), (x+a,y+t*a), head=2, color='red') G += point((0,t), pointsize=150, color='black', zorder=100) G += point((-1,0), pointsize=150, color='black', zorder=100) G += point((x,y), pointsize=190, color='lightgreen', zorder=100) G.show(aspect_ratio=1, ymax=1.4, xmax=2, fontsize=0, figsize=6) html('</center>') 
       
t 

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

Cubic Curves    

x^3 + y^3 = 1
var('x,y') implicit_plot(x^3 + y^3 == 1, (x,-2,2), (y,-2,2), figsize=5, gridlines=True) 
       
 
       
 
       
 
       

y^2 - y = x^3 - x
implicit_plot(y^2 - y == x^3 - x, (x,-2,2), (y,-1,2), figsize=5, gridlines=True) 
       
 
       
 
       
 
       

New solutions from old ones: The Secant Process
%hide E = EllipticCurve([0,0,1,-1,0]) html('<center><font size=+2>$%s$</font></center>'%latex(E)) G = E.plot(plot_points=600, thickness=2) G += arrow((-2,1), (3,-4), head=2, color='red', width=2) G += points([(-1,0), (0,-1), (2,-3)], color='black', pointsize=70, zorder=50) G += text("$(2,-3)$", (1.1,-3), fontsize=18, color='black') G.show(gridlines='minor', frame=True, figsize=[4,4]) 
        
y^2 + y = x^3 - x 


y^2 + y = x^3 - x
 
       
 
       

New solutions from old ones: The Tangent Process
%hide E = EllipticCurve([0,0,1,-1,0]) html('<center><font size=+2>$%s$</font></center>'%latex(E)) G = E.plot(plot_points=600, thickness=2) G += arrow((-1,1), (2,-2), head=2, color='red', width=2) G += points([(0,0), (1,-1)], color='black', pointsize=70, zorder=50) G += text("$(1,-1)$", (1.4,-.5), fontsize=16, color='black') G.show(gridlines=True, frame=True, figsize=[4,4], xmin=-2, xmax=3) 
        
y^2 + y = x^3 - x 


y^2 + y = x^3 - x
 
       

Large solutions    

We can turn this into an abelian group law on the set of solutions. Is it finite or infinite?

If the group is infinite, the solutions become very large.

P=(0,0) on y^2-y=x^3-x

Compute x-coordinate of nP:
%hide @interact def _(n=(1..65)): E = EllipticCurve([0,0,1,-1,0]) P = E([0,0]) show((n*P)[0]) 
       
n 

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

Even the simplest solution can be large    

Simplest solution to y^2=x^3+7823:

x = \frac{2263582143321421502100209233517777}{143560497706190989485475151904721}

y = \frac{186398152584623305624837551485596770028144776655756}{1720094998106353355821008525938727950159777043481}

(Found by Michael Stoll in 2002.)

 
 
       
 
       
 
       
 
       
 
       
 
       
 
       
 
       

The Rank

The rank of E is the number of independent solutions of infinite order.
         rank(E) = 0 means there are finitely many solutions.

Example: Curve E(a): with equation y(y+1) = x(x-1)(x+a).
Has rank = 0, 1, 2, 3, 4, 5, 6 for a = 0, 1, 2, 4, 16, 79, 298.
%hide @interact def _(a=(2, (0..300))): E = EllipticCurve([0,(a-1),1,-a,0]) html("<center><font size=+1>$y(y+1)=x(x-1)(x+%s)$,    rank = %s</font>"%(a,E.rank())) v = E.gens() v = [(t[0],t[1]) for t in v] G = E.plot(thickness=3, plot_points=600) xmin = min(G.xmin(), min(t[0] for t in v+[(0,0)])) xmax = max(G.xmax(), max(t[0] for t in v+[(-xmin/2,0)])) G = E.plot(thickness=3, xmin=xmin, xmax=xmax, plot_points=600) G += points([(t[0],t[1]) for t in v], color='black', pointsize=50, zorder=50) G.show(figsize=4, frame=True) show(v) html("</center>") 
       
a 

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

How big can the rank be?

We don’t know if the ranks of elliptic curves can be arbitrarily large.

The current record is rank(E) = 28 for Noam Elkies' curve E below, with independent points:

P1 = [-2124150091254381073292137463, 259854492051899599030515511070780628911531] 
P2 = [2334509866034701756884754537, 18872004195494469180868316552803627931531]
P3 = [-1671736054062369063879038663, 251709377261144287808506947241319126049131]
P4 = [2139130260139156666492982137, 36639509171439729202421459692941297527531]
P5 = [1534706764467120723885477337, 85429585346017694289021032862781072799531]
P6 = [-2731079487875677033341575063, 262521815484332191641284072623902143387531]
P7 = [2775726266844571649705458537, 12845755474014060248869487699082640369931]
P8 = [1494385729327188957541833817, 88486605527733405986116494514049233411451]
P9 = [1868438228620887358509065257, 59237403214437708712725140393059358589131]
P10 = [2008945108825743774866542537, 47690677880125552882151750781541424711531]
P11 = [2348360540918025169651632937, 17492930006200557857340332476448804363531]
P12 = [-1472084007090481174470008663, 246643450653503714199947441549759798469131] 
P13 = [2924128607708061213363288937, 28350264431488878501488356474767375899531] 
P14 = [5374993891066061893293934537, 286188908427263386451175031916479893731531]
P15 = [1709690768233354523334008557, 71898834974686089466159700529215980921631]
P16 = [2450954011353593144072595187, 4445228173532634357049262550610714736531]
P17 = [2969254709273559167464674937, 32766893075366270801333682543160469687531] 
P18 = [2711914934941692601332882937, 2068436612778381698650413981506590613531] 
P19 = [20078586077996854528778328937, 2779608541137806604656051725624624030091531]
P20 = [2158082450240734774317810697, 34994373401964026809969662241800901254731]
P21 = [2004645458247059022403224937, 48049329780704645522439866999888475467531]
P22 = [2975749450947996264947091337, 33398989826075322320208934410104857869131]
P23 = [-2102490467686285150147347863, 259576391459875789571677393171687203227531]
P24 = [311583179915063034902194537, 168104385229980603540109472915660153473931]
P25 = [2773931008341865231443771817, 12632162834649921002414116273769275813451] 
P26 = [2156581188143768409363461387, 35125092964022908897004150516375178087331] 
P27 = [3866330499872412508815659137, 121197755655944226293036926715025847322531] 
P28 = [2230868289773576023778678737, 28558760030597485663387020600768640028531]
E = EllipticCurve([1,-1,1, -20067762415575526585033208209338542750930230312178956502, 34481611795030556467032985690390720374855944359319180361266008296291939448732243429]) E 
        
Elliptic Curve defined by y^2 + x*y + y = x^3 - x^2 -
20067762415575526585033208209338542750930230312178956502*x +
344816117950305564670329856903907203748559443593191803612660082962919394\
48732243429 over Rational Field
Elliptic Curve defined by y^2 + x*y + y = x^3 - x^2 - 20067762415575526585033208209338542750930230312178956502*x + 34481611795030556467032985690390720374855944359319180361266008296291939448732243429 over Rational Field
 
       
 
       
 
       
 
       

A Prediction

Peter Swinnerton-Dyer and Bryan Birch made a prediction for the rank
based on the average number of solutions at each prime number p.
 
       
 
       
 
       
 
       

   Prime Numbers

    A prime is a number not divisible by any smaller number: 2, 3, 5, 7, 11, ...
prime_range(200) 
        
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139,
149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]

Counting Primes
plot(prime_pi, 0,100, figsize=[8,2]) 
       
 
       
 
       
 
       
 
       
 
       
 
       

There are infinitely many primes

The largest known prime is p=2^{43112609} -1 with 12,978,189 digits
%hide s_bigp = str(2^43112609 - 1) @interact def _(d=(5..10000)): print "Showing %.5f percent of the digits"%(100*2.0*d/len(s_bigp)) print "p = " + s_bigp[:d] + ' ... ' + s_bigp[-d:] 
       
d 

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

Solutions Modulo p

What do we mean by a solution of the cubic equation at the prime number p?
Why are there finitely many solutions A(p)?
%hide @interact def _(p=(7,tuple(prime_range(500))), show_coords=False): E = EllipticCurve([0,0,1,-1,0]) html('<center><font size=+1>$%s$ modulo $%s$<br>'%(latex(E),p)) if E.conductor()%p == 0: html('<br><br>Curve has bad reduction...') else: html('<font color="blue" size=+1>$\\infty$</font><br>') G = E.change_ring(GF(p)).plot(pointsize=50) G.show(gridlines=True, figsize=4, frame=True, axes=False) if show_coords: print ', '.join(['(%s,%s)'%(z[0],z[1]) if z[2] else 'infinity' for z in E.change_ring(GF(p)).points()]) html('<br>$A(%s) = %s$'%(p,p+1-E.ap(p))) html('</font></center>') 
       
p 
show_coords 

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

The L-Function

Hasse proved: p+1 - 2\sqrt{p} < A(p) < p+1 + 2\sqrt{p}

It is common to write: A(p) = p+1-a(p)

and to define the L-function of E by the infinite product

L(E,s) = \prod_p (1-a(p)p^{-s}+p^{1-2s})^{-1} = \sum a(n) n^{-s}

This only makes sense as a function when s>3/2, where the product converges.
%hide E = EllipticCurve([0,0,1,-1,0]) L = E.lseries().dokchitser(20) html('<h3>$L$-series of $%s$</h3>'%(latex(E))) G = line([(s,L(s).real()) for s in [3/2, 3/2+0.2, .., 8]]) G += text('?', (.6,.1), color='red', fontsize=26) G.show(xmin=-1, ymin=-.1, figsize=4, frame=True, gridlines=True) 
        
L-series of y^2 + y = x^3 - x 


L-series of y^2 + y = x^3 - x
 
       
 
       
 
       
 
       
 
       
 
       
 
       

The L-function at 1

If we formally set s = 1 in the product, we get

\prod_p(1 - a(p)p^{-1} + p^{-1})^{-1} = \prod_p \frac{p}{A(p)}

If A(p) is large on average compared with p, this product will approach zero.  The larger A(p) is on average, the faster it will tend to zero.
%hide @interact def _(E = ['y^2 + y = x^3 - x^2', 'y^2 + y = x^3 - x', 'a rank 4 curve', 'elkies rank>=28 curve']): if E == 'y^2 + y = x^3 - x^2': E = EllipticCurve([0,-1,1,0,0]) r = E.rank() elif E == 'y^2 + y = x^3 - x': E = EllipticCurve([0,0,1,-1,0]) r = E.rank() elif E == 'a rank 4 curve': E = EllipticCurve([1, -1, 0, -79, 289]) r = 4 elif E == 'elkies rank>=28 curve': E = EllipticCurve([1,-1,1, -20067762415575526585033208209338542750930230312178956502, 34481611795030556467032985690390720374855944359319180361266008296291939448732243429]) r = ">=28" L_approx = 1 print '%4s%6s%5s%9s%20s'%('p', 'A(p)', 'p/Ap', ' prod p/Ap', 'Rank = %s'%r) v = [] t = '' for p in primes(500): if E.discriminant()%p: Ap = p+1-E.ap(p) L_approx *= float(p/Ap) t += '%4s%4s%8.3f%8.3f\n'%(p, Ap, float(p/Ap), L_approx) v.append((p, L_approx)) print t line(v).show(figsize=[8,2]) 
       
E 

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

Birch and Swinnerton-Dyer's Precise Conjecture

  1. The function L(E,s) has an analytic continuation to a neighborhood of s = 1.

  2. The order of vanishing at s = 1 is equal to the rank of E.
 
       

Tate's Refinement

This conjecture was refined by John Tate, to give the leading term
in the Taylor expansion at s = 1 in terms of other arithmetic
invariants of E.

L(E,s) \sim c(E)\cdot (s-1)^{\text{rank}(E)}\qquad s\to 1

 
       
 
       
 
       
 
       
 
       
 
       
 
       

Analytic Continuation

The analytic continuation was proved using the method of Andrew Wiles and Richard Taylor: the function

F(\tau) = \sum a(n) e^{2\pi i n\tau}
is a modular form.
%hide E = EllipticCurve([0,0,1,-1,0]) L = E.lseries().dokchitser(30) complex_plot(L, (-1,3), (-1,1), plot_points=30) 
       
 
       
 
       
 
       

Work of Gross-Zagier and Kolyvagin when r=0 and r=1

Combining work of Benedict Gross and Don Zagier with work of Victor Kolyvagin, one can show:

  • If L(E,1)\neq 0 the rank is zero.

  • If L(E,1)=0 and L'(E,1)\neq 0 the rank is one.
 
       
 
       
 
       
 
       
 
       
 
       
 
       
 
       
 
       

When r=2 and r=3

  • Can prove rank conjecture for specific curves one at a time using a computer.

  • I don't know of a systematic careful attempt to do this for many curves.
E = EllipticCurve([0, 1, 1, -2, 0]) E.rank() 
        
2
2
L = E.lseries(); L(1) 
        
-1.33174198778018e-19
-1.33174198778018e-19
L.L1_vanishes() 
        
True
True
L.taylor_series() 
        
-2.69129566562797e-23 + (1.52514901968783e-23)*z + 0.759316500288427*z^2
- 0.430302337583362*z^3 - 0.193509313829981*z^4 + 0.459971558373642*z^5
+ O(z^6)
-2.69129566562797e-23 + (1.52514901968783e-23)*z + 0.759316500288427*z^2 - 0.430302337583362*z^3 - 0.193509313829981*z^4 + 0.459971558373642*z^5 + O(z^6)
 
       
 
       
 
       
 
       
 
       

When r\geq 4

Conjecture not proved for even a single elliptic curve.

Do not know conjecture for this rank 4 curve: y^2 + xy = x^3 - x^2 - 79x + 289

Proving the conjecture for this particular curve would be a major result.
E = EllipticCurve([1, -1, 0, -79, 289]) L = E.lseries(); L.taylor_series() 
        
5.54631009473167e-24 + (-2.08951550639391e-23)*z +
(-4.15704192504384e-22)*z^2 + (1.66720224204167e-21)*z^3 +
8.94384739590089*z^4 - 33.6950287693207*z^5 + O(z^6)
5.54631009473167e-24 + (-2.08951550639391e-23)*z + (-4.15704192504384e-22)*z^2 + (1.66720224204167e-21)*z^3 + 8.94384739590089*z^4 - 33.6950287693207*z^5 + O(z^6)
%hide L = E.lseries().dokchitser(20) eps = 0.025 G = line([(s,L(s).real()) for s in [-0.1,-0.1+eps, .., 4]]) G.show(figsize=[6,2], frame=True, gridlines=True, ymin=-1, ymax=10) 
       
 
       
 
       
 
       
 
       
 
       

Questions?
 
       
 
       
 
       
 
       
 
       
 
       
 
       
 
       
 
       

The Average Rank

Manjul Bhargava has recently made progress on the study of the average rank, for ALL cubic curves with rational coefficients.

Every such curve has an equation of the form y^2 = x^3 + Ax + B where A and B are integers. It is unique if no prime p satisfies p^4 divides A and p^6 divides B.