wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> 157
        
(Message started by: ThudanBlunder on Jul 4^th, 2008, 8:02am)

Title: 157
Post by ThudanBlunder on Jul 4^th, 2008, 8:02am

Find the smallest rational number x (smallest in the sense of smallest numerator and denominator) such that there exist rational numbers y and z and

x² - 157 = y²
x² + 157 = z²

Title: Re: 157
Post by Barukh on Jul 4^th, 2008, 10:42am

[hide]It's Congruent[/hide]!

Title: Re: 157
Post by ThudanBlunder on Jul 4^th, 2008, 11:21am

157 is indeed congruent. Is that your final answer? :)

Title: Re: 157
Post by Eigenray on Jul 5^th, 2008, 7:24am

Brute force (Google) search gives

x = 224403517704336969924557513090674863160948472041 / 17824664537857719176051070357934327140032961660.

::)

Title: Re: 157
Post by ThudanBlunder on Jul 5^th, 2008, 7:39am

on 07/05/08 at 07:24:44, Eigenray wrote:

Brute force (Google) search gives

x = 224403517704336969924557513090674863160948472041 / 17824664537857719176051070357934327140032961660.

::)

I was hoping it was Google-proof. What did you search for? I wonder what the fraction is for 2008. :)

(I have thought of a good name for a porn search engine. How about Goggle?) ;D

Title: Re: 157
Post by towr on Jul 5^th, 2008, 8:23am

on 07/05/08 at 07:39:03, ThudanBlunder wrote:

(I just thought of a good name for a porn search engine. How about Goggle?) ;D

I think the classic is Ogle

Title: Re: 157
Post by Barukh on Jul 5^th, 2008, 10:28am

on 07/05/08 at 07:24:44, Eigenray wrote:

Brute force (Google) search gives

x = 224403517704336969924557513090674863160948472041 / 17824664537857719176051070357934327140032961660.

::)

The question is how to arrive at this answer? Using a complex derivation based on Elliptic Curves is one way; is there another (more elementary)?

Title: Re: 157
Post by Eigenray on Jul 5^th, 2008, 11:28am

I searched for '157 congruent'. The first result was wrong, so I tried searching both its numerator and denominator.

Let E be given by y² = x³ - p²x. We are looking for a non-torsion point on this curve. I'm not sure how the point was actually found, but I'll tell you how one might find it, using the algorithm described in Silverman's "The Arithmetic of Elliptic Curves".

The complete 2-torsion of E, E[2], is (0,0), (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gifp,0), and the point at infinity. Since these are all rational, it turns out there is a bilinear pairing

E/2E x E[2] http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif^*/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif^*2.

(The definition is a bit involved, but basically it is induced from the Weil pairing using the connecting homomorphisms of the Kummer sequences for http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif^* and E.)

But the image of this pairing is actually finite: it is contained in S = { http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif1, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif2, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gifp, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif2p }. Since E[2] = (Z/2Z)² is also finite, we have an explicit embedding of E/2E into the finite group Hom(E[2], S) = S². For each element of this group, we can try to find a point which maps to it, or prove there is no such point (but there is no known algorithm for this in general). But if we can figure out which elements of this group actually come from points on E, we get a set of representatives for the quotient E/2E, and a bit of work will give the generators for E.

So, what you actually try to do is find a point which maps to, say (-1, 1). If you look at the definitions, this amounts to trying to solve
a² + b² = 2p
a² - c² = p
in rationals. Note that it is similar to the system we started with. In practice, what is done is to repeatedly apply this procedure ("2-descent"), or more generally with an isogeny of degree 2. But in any case, this system has the solution

a=780871468723/53156661805
b=526771095761/53156661805
c=407598125202/53156661805.

(I found this by working backwards from the point on E, but in practice you would find this first.) Now

x = p-a² = -166136231668185267540804 / 53156661805²
y = -abc = -167661624456834335404812111469782006 / 53156661805³

is a point on E. This point has x<0, but if we double it, we get a point with x-value
(224403517704336969924557513090674863160948472041 / 17824664537857719176051070357934327140032961660)².

[edit]Thinking about it some more, we can start with the homogeneous space
C_p' : pw² = p² + p²/4 z⁴
for the curve E': y² = x³ + p²/4 x. The point
(z,w) = (1143522/356441, 8345595903385/356441²)
on C_p' maps via http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/psi.gif(z,w) = (p/z², pw/z³) to
(x,y) = (19946879277517/1143522², 467029870255557087245/1143522³)
on E', which maps to
(x,y) = (69648970982596494254458225/407598125202², 538962435089604615078004307258785218335/407598125202³)
on E under the isogeny http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif(x,y) = ((y/x)², y(p²/(4x²)-1)).
This point then doubles to the same point. However, to continue the descent on C_p' requires passing to a larger number field I think.

Title: Re: 157
Post by ThudanBlunder on Jul 5^th, 2008, 5:34pm

Yes, that's the proof I was thinking of. ::) ;D

You are amazing, Eigenray! :)

Title: Re: 157
Post by BenVitale on Jul 7^th, 2008, 3:08pm

Thanks Eigenray,

You can also find an interesting discussion of the congruent number problem at

http://www.math.umd.edu/~eve/cong_num.html

Title: Re: 157
Post by ThudanBlunder on Jul 7^th, 2008, 9:55pm

on 07/07/08 at 15:08:31, BenVitale wrote:

You can also find an interesting discussion of the congruent number problem at

http://www.math.umd.edu/~eve/cong_num.html

Thanks for the link.

You would make a good researcher, Ben. Poacher turned gamekeeper, so to speak. LOL

Title: Re: 157
Post by Barukh on Jul 8^th, 2008, 12:56am

Another good article is this (http://www.math.rug.nl/~top/Chandrasekar.pdf).

Title: Re: 157
Post by Eigenray on Jul 8^th, 2008, 4:35am

on 07/07/08 at 15:08:31, BenVitale wrote:

You can also find an interesting discussion of the congruent number problem at
http://www.math.umd.edu/~eve/cong_num.html

Yes that's the one that has a typo in the numerator.

Googling some more I found [link=http://www.math.cornell.edu/~alozano/info/buscando_extra.pdf]this[/link] (pagina 19, ejemplo 6.8). So it is done via 2-isogeny:
Original curve E : y² = x³ - p²x
Auxiliary curve E' : y² = x³ + 4p²x
Homogeneous space C_d : dw² = d² + 4p²z⁴, d http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif {http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif1, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif2, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gifp, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif2p}.
According to that pdf, for the curve C_p, we parameterize
w² = p(1+4Z²)
[It is a conic, so we can find one solution, say Z₀=3/11 (since p = 11² + 4*3²); then set w=w₀+ut, Z=Z₀+vt, and eliminate t, giving Z in terms of integers u,v.] Then use this parameterization to find a solution where Z=z² is a square, and map it back to a point on E. There must be a way to optimize this though because the required (u,v) are either (7687738, 49921) or (2768294, 322213), and it seems like those would take as long to find as testing each z.

Note that the maps are elementary: that is, if we find a point on an associated homogeneous space it's easy to see we get a point on E; the hard part is proving that [mod the image of the dual isogeny] any point of E comes from one of these. In fact I recall reading somewhere that when Euler(?) proved y² = x³ + 1 has no 'non-trivial' solutions [(2,3) generates the order 6 torsion subgroup], he was really using 2-isogenies, though of course that's not what they were called at the time. I believe some of Fermat's descent falls into this category too.