# MAT 338 Day 25 2011

## 2851 days ago by kcrisman

Last time we saw that an investigation of integers points led us through rational points back to integer points. So today, and probably a little of next time, we will look at integer lattice points exclusively.  Remember the three types of curves we talked about at the very end of last time.

• $y^3=x^2+2$
• $x^2+2y^2=9$
• $x^2-2y^2=1$

Let's start by talking about $y^3=x^2+2$ as a type of curve.  Recall from early in the semester that Bachet de Méziriac first asserted this had one positive integer solution in 1621 - very early in the development of modern number theory.  What is it?

This equation is one of a more general type called the Mordell equation: $$y^3=x^2+k\; , \;\; k\in\mathbb{Z}$$  Mordell, an American-born British mathematician, indeed proved some remarkable theorems about this class of equations.

Notice that Mordell's set of curves are not quadratic/conic but rather cubic, which makes them more mysterious (and, as it happens, more useful for cryptography, though we won't really get into that).  It is a theorem that they can only have finitely many integer points (in fact, there are even useful bounds for how many that depend only on the prime factorization of $k$).  At the same time, they are apparently "simple" enough that they can still have infinitely many rational points; Gerd Faltings won a Fields Medal for proving that higher-degree curves cannot.

var('x,y') @interact def _(k=(2,[-15..15]),viewsize=10): g(x,y)=y^3-x^2 plot1 = implicit_plot(g-k,(-viewsize,viewsize),(-viewsize,viewsize),plot_points = 100) grid_pts = [[i,j] for i in [-viewsize..viewsize] for j in [-viewsize..viewsize]] plot_grid_pts = points(grid_pts,rgbcolor=(0,0,0),pointsize=2) lattice_pts = [coords for coords in grid_pts if (coords[1]^3-coords[0]^2==k)] plot_lattice_pts = points(lattice_pts, rgbcolor = (0,0,1),pointsize=20) show(plot1+plot_grid_pts+plot_lattice_pts, figsize = [5,5], xmin = -viewsize, xmax = viewsize, ymin = -viewsize, ymax = viewsize) html("Integer points on the Mordell equation $y^3=x^2+%s$ in this window"%k)

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

Proving things about Mordell's equation is quite tricky, but once in a while there is something you can do.  For instance, we can verify something we can see above.

Fact: There are no integer solutions to $x^3=y^2-7$.

Proof:

• We look at the equation modulo 4, which gives $$x^3\equiv y^2-3\text{ mod (4)}$$
• If $x$ is even, this reduces to $y^2\equiv 3\text{ mod }(4)$, which we already know is not possible.
• Likewise, if $x\equiv 3$ mod (4), then $x^3\equiv 3$ as well, so that $y^2\equiv 6\equiv 2\text{ mod }(4)$, also impossible.
• So it remains to look at the possibility that $x\equiv 1\text{ mod }(4)$.  But then we do a cute trick.
• Since $7$ is one less than a perfect cube, we can rewrite the original equation as $$x^3+8= y^2+1\Rightarrow (x+2)(x^2-2x+4)= y^2+1$$
• So $$(x+2)\mid y^2+1\; .$$  But then any prime divisor of $x+2$ must divide $y^2+1$.
• Since $x\equiv 1\text{ mod }(4)$, we have that $$x+2\equiv 3\text{ mod }(4)\; ,$$ so at least one of those prime divisors must also be $p\equiv 3\text{ mod }(4)$.  But then $$p\mid (y^2+1)\Rightarrow y^2\equiv -1\text{ mod (}p)\, ,$$ which is impossible by our theorem we proved using geometry a few times ago!

In homework there will be something similar.  In fact, it turns out that there is even a more general statement; the one we just did is $M=2$, $N=1$.

Fact: There is no solution to $$y^2=x^3+(M^3-N^2)$$ if

• $M\equiv 2\text{ mod }(4)$,
• $N\equiv 1\text{ mod }(2)$, and
• all prime divisors $p$ of $N$ are of the form $4k+1$.

The proof basically follows the same outline, and we won't spend time proving it.  There are lots of similar statements one can prove too.  But hopefully you get the point - if you want to prove anything about these guys with current methods we have access to, we have no hope of getting any general results.

Let's see what I mean here by returning to Bachet's original equation, $y^3=x^2+2$.

• Let's look at naive things we can say.
• It should be clear that $x$ and $y$ must have the same parity.
• If they are both even then $y^3$ is divisible by 4 but $x^2+2\equiv 2\text{ mod }(4)$, which is impossible.
• So $x$ and $y$ are both odd.
• That doesn't really narrow things down too much, really.
• Euler nearly proves that $x=5,y=3$ is the only positive solution.
• This is related to the use of complex numbers in proving for which primes $p=a^2+b^2$, so it's worth giving an overview.
• Just as there, we try to factor the $x^2+2$.   But it can't be done in $\mathbb{Z}[i]$.
• So we instead use the square root of $-2$, and define $$\mathbb{Z}[\sqrt{-2}]=\{a+b\sqrt{-2} \mid a,b\in\mathbb{Z}\}$$
• Then $$y^3=(x-\sqrt{-2})(x+\sqrt{-2})$$
• In the integers, if $y^3=pq$ and $gcd(p,q)=1$, then $p$ and $q$ must both be perfect (integer) cubes.
• So Euler assumes this works in $\mathbb{Z}[\sqrt{-2}]$ as well, and that the factors of $x^2+2$ are 'coprime' (whatever that means).
• Then some basic algebraic manipulation of $$x-\sqrt{-2}=\left(a+b\sqrt{-2}\right)^3$$ and and divisibility considerations end up showing that $b \mid 1$ and $a=\pm b$, which ends up showing $x=\pm 5$ and $y=3$.  (We will skip these details, since we will not take this further.)

It turns out you can say that a product which is a cube is a product of cubes in this situation, but it requires some (geometrically motivated) proof, like with $\mathbb{Z}[i]$.  In his 1765 "Vollständige Anleitung zur Algebra," sections 187-188 and 191, he explicitly says that this just works - in any number system with $\mathbb{Z}[\sqrt{c}]$.  He solves this one in section 193, and solves $x^2+4=y^3$ using the same technique in section 192, without realizing the problem.

But we shouldn't be too hard on Euler!  He was one of the first people to even consider some essentially random new number system of this type.    And, in 1738, he gives a correct and full proof of the observation we made a long time ago that $8$ and $9$ is the only time a perfect square is preceded by a perfect cube, which is Mordell's equation for $k=-1$.

If you are interested in more information about how to prove cases of Mordell's equation, there are many good resources, including a nice one here.

On the other hand, finding lattice points on a quadratic curve is much more tractable.  This is because we understand conic sections so well, after having worked with them for two thousand years!

a=1 b=2 c=9 var('x,y') viewsize=math.sqrt(c)+1 g(x,y)=a*x^2+b*y^2 plot1 = implicit_plot(g-c,(-viewsize,viewsize),(-viewsize,viewsize),plot_points = 200) grid_pts = [[i,j] for i in [-viewsize..viewsize] for j in [-viewsize..viewsize]] plot_grid_pts = points(grid_pts,rgbcolor=(0,0,0),pointsize=2) lattice_pts = [coords for coords in grid_pts if (a*coords[0]^2+b*coords[1]^2==c)] plot_lattice_pts = points(lattice_pts, rgbcolor = (0,0,1),pointsize=20) show(plot1+plot_grid_pts+plot_lattice_pts, figsize = [5,5], xmin = -viewsize, xmax = viewsize, ymin = -viewsize, ymax = viewsize, aspect_ratio=1)

Here we see our second prototype, $x^2+2y^2=9$.  You can see that, in addition to the obvious solution where $y=0$, there is the (nearly as obvious, because the numbers are small, but still interesting) solution $x=1,y=2$.

In general, for our purposes an ellipse is special because there are only finitely many lattice points to check.  So much for the computational problem - just get a fast computer!

However, I just want to mention where a general theory for such things might come from.  After all, it gets harder to check with 'industrial strength' ellipses, and we want theorems.

Although it's being removed from the curriculum nowadays, there is something that often happens in high school mathematics or first-year college calculus where you learn how to transform one conic section to another one of the same type with a matrix.   In particular, we can get from the circle $x^2+y^2=9$ to $x^2+2y^2=9$ by multiplying the vector $(x,y)$ by the matrix $\pmatrix{1& 0\\ 0& 1/\sqrt{2}}$; that would not stretch the $x$-axis, but shrinks in the $y$ axis by the appropriate amount.

However, one can also think of it as both conics coming from matrices. $$\pmatrix{x & y}\pmatrix{1& 0\\ 0& 1}\pmatrix{x\\ y}=x^2+y^2$$ while $$\pmatrix{x & y}\pmatrix{1& 0\\ 0& 2}\pmatrix{x\\ y}=x^2+2y^2\; .$$  Gauss was interested in extending Fermat's question - namely, what numbers are representable in these ways, as opposed to just a sum of squares?  It turns out that many such quadratic forms represent the same sets of integers.

The Sage reference manual even uses our example to demonstrate this: $$\pmatrix{x & y}\pmatrix{1& 0\\ 0& 2}\pmatrix{x\\ y}=x^2+2y^2\text{ and }\pmatrix{x & y}\pmatrix{1& 1\\ 1& 3}\pmatrix{x\\ y}=x^2+2xy+3y^2$$ both would fulfill Fermat's result about primes modulo $8$ we mentioned earlier.  So both should represent 11.  Clearly $11=3^2+2\cdot 1^2$ works, but what about the other version?

var('x,y') @interact(layout=[['a','b'],['c','d'],['output']]) def _(a=1,b=1,c=1,d=3,output=11): viewsize=ceil(math.sqrt(output)+1) g(x,y)=a*x^2+(b+c)*x*y+d*y^2 plot1 = implicit_plot(g-output,(x,-viewsize,viewsize),(y,-viewsize,viewsize),plot_points = 200) grid_pts = [[i,j] for i in [-viewsize..viewsize] for j in [-viewsize..viewsize]] plot_grid_pts = points(grid_pts,rgbcolor=(0,0,0),pointsize=2) lattice_pts = [coords for coords in grid_pts if (a*coords[0]^2+(b+c)*coords[0]*coords[1]+d*coords[1]^2==output)] plot_lattice_pts = points(lattice_pts, rgbcolor = (0,0,1),pointsize=20) show(plot1+plot_grid_pts+plot_lattice_pts, figsize = [5,5], xmin = -viewsize, xmax = viewsize, ymin = -viewsize, ymax = viewsize, aspect_ratio=1) html("Integer lattice points on $%sx^2+%sxy+%sy^2=%s$"%(a,b+c,d,output))

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

Looks like $x=2,y=1$ will do it.  (That's because, as one of you pointed out, $$x^2+2xy+3y^2=(x+y)^2+2y^2$$ and this is a coordinate transformation.)

So there is some very deep theory there, which is another place where lie the beginnings of algebraic number theory, just like with the Gaussian integers.  But we'll let it rest there.

Instead, we will continue looking for integer points on a given specific curve.  Assuming that ellipses are doable by simply counting, what is next?

The parabola comes to mind.   A general parabola would look like $ny=mx^2$; this can be thought of in your usual terms as $y=ax^2$ and $a=m/n$.

Then I can just check all $x\in\mathbb{Z}$ such that $n\mid mx^2$.  Since $gcd(m,n)=1$ for this (lowest terms), we would just need in fact that $n\mid x^2$ (so if $n$ is prime, $n\mid x$ suffices)!

So if $y=mx^2$ for integer $m$, any $x$ will do.  That makes sense; integer input better give integer output, which would be a lattice point!

If $2y=x^2$, we just look at it as $2|x$, so that requiring $x$ even will give lattice points.  And so on.

var('x,y') @interact def _(m=1,n=2): viewsize=3*n^2 f(x,y)=(m/n)*x^2 plot1 = plot(f,-viewsize,viewsize) grid_pts = [[i,j] for i in [-viewsize..viewsize] for j in [0..viewsize^2]] plot_grid_pts = points(grid_pts,rgbcolor=(0,0,0),pointsize=2) lattice_pts = [coords for coords in grid_pts if (m*coords[0]^2==n*coords[1])] plot_lattice_pts = points(lattice_pts, rgbcolor = (0,0,1),pointsize=20) show(plot1+plot_grid_pts+plot_lattice_pts, figsize = [5,5], xmin = -viewsize, xmax = viewsize, ymin = -1, ymax = (m/n)*viewsize^2)

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

So much for integer points on the parabola.

But before we go on, I want to point something very interesting out.  Look at the following two setups - one where I create the line through two integer points on the conic, the other where I create the tangent line through one integer point:

a=1 b=2 var('x,y') viewsize=10 R.<x,y> = ZZ[] f(x)=(a/b)*x^2 plot1 = plot(f,-viewsize,viewsize) grid_pts = [[i,j] for i in [-viewsize..viewsize] for j in [0..viewsize^2]] plot_grid_pts = points(grid_pts,rgbcolor=(0,0,0),pointsize=2) lattice_pts = [coords for coords in grid_pts if (a*coords[0]^2==b*coords[1])] plot_lattice_pts = points(lattice_pts, rgbcolor = (0,0,1),pointsize=20) line1 = plot((f(2)-f(4))/(2-4)*(x-2)+f(2),-viewsize,viewsize,color='red') line2 = plot((f(2)-f(4))/(2-4)*x,-viewsize,viewsize,color='red',linestyle='--') line3 = plot((f(2)-f(4))/(2-4)*(x+2)+f(-2),-viewsize,viewsize,color='red',linestyle='--') show(plot1+plot_grid_pts+plot_lattice_pts+line1+line2+line3,ymin=-1,ymax=viewsize^2/2)
a=1 b=2 var('x,y') viewsize=10 R.<x,y> = ZZ[] f(x)=(a/b)*x^2 plot1 = plot(f,-viewsize,viewsize) grid_pts = [[i,j] for i in [-viewsize..viewsize] for j in [0..viewsize^2]] plot_grid_pts = points(grid_pts,rgbcolor=(0,0,0),pointsize=2) lattice_pts = [coords for coords in grid_pts if (a*coords[0]^2==b*coords[1])] plot_lattice_pts = points(lattice_pts, rgbcolor = (0,0,1),pointsize=20) line1 = plot(2*(a/b)*4*(x-4)+f(4),-viewsize,viewsize,color='red') line2 = plot(2*(a/b)*4*x,-viewsize,viewsize,color='red',linestyle='--') line3 = plot(2*(a/b)*4*(x+2)+f(-2),-viewsize,viewsize,color='red',linestyle='--') show(plot1+plot_grid_pts+plot_lattice_pts+line1+line2+line3,ymin=-1,ymax=viewsize^2/2)

Notice that in both cases you get another integer point!  This is not a coincidence.  In fact, there is the following fact:

Fact: The set of rational points on a conic section is an Abelian group.

However, often we will in fact get integer points.  For our purposes, that means that we can try to create new points by either doing the slope-through-two-points thing ('adding' points) or the tangent-slope thing ('doubling' a point).  We will use this momentarily below.

I doesn't always work, of course, as we are only guaranteed rational points; see below where I try this on the ellipse.

a=1 b=2 c=9 var('x,y') viewsize=ceil(math.sqrt(c)+1) f=a*x^2+b*y^2 g(x,y)=f plot1 = implicit_plot(g-c,(-viewsize,viewsize),(-viewsize,viewsize),plot_points = 200) grid_pts = [[i,j] for i in [-viewsize..viewsize] for j in [-viewsize..viewsize]] plot_grid_pts = points(grid_pts,rgbcolor=(0,0,0),pointsize=2) lattice_pts = [coords for coords in grid_pts if (a*coords[0]^2+b*coords[1]^2==c)] plot_lattice_pts = points(lattice_pts, rgbcolor = (0,0,1),pointsize=20) line1 = plot(x+3,-viewsize,viewsize,color='red') line2 = plot(x+1-2,-viewsize,viewsize,color='red',linestyle='--') line3 = plot(x-1-2,-viewsize,viewsize,color='red',linestyle='--') show(plot1+plot_grid_pts+plot_lattice_pts+line1+line2+line3, figsize = [5,5], xmin = -viewsize, xmax = viewsize, ymin = -viewsize, ymax = viewsize, aspect_ratio=1)

But it turns out it works very nicely indeed for the last conic section, the hyperbola. So that's what we'll start with next time!

Homework:

1. Tell me what day you are presenting.  Remember that April 13th will probably be the date for the other midterm.
2. Show that the equation $x^3=y^2-999$ has no integer solutions.
3. Show that the Pell equation with $d=1$ ($x^2-y^2=1$) has only two solutions.  Generalize this to when $d$ happens to be a perfect square.
4. Look up the current best known bound on the number of integer points on a Mordell equation curve.