NTIC Points on Quadratic Curves

Section 15.4 Points on Quadratic Curves

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!

🔗

In Figure 15.4.1 we see our second prototype,

$x^2+2y^2=9\text{.}$ You can see that, in addition to the obvious solution where

$y=0\text{,}$ there is the (nearly as obvious, because the numbers are small, but still interesting) solution

$x=1,y=2\text{.}$

🔗

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, in this chapter I'd like to just start investigating 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. The next section gives a couple hints of an algebraic nature, and then we will take a third, more geometric hint, a bit further in the end of the chapter.

🔗

Subsection 15.4.1 Transforming conic sections

🔗

Although it's being removed from the curriculum nowadays, students in high school mathematics or first-year college calculus often learn how to use matrices to transform one conic section to another of the same type.

🔗

Example 15.4.2.

We can get from the circle $x^2+y^2=9$ to the ellipse $x^2+2y^2=9$ by multiplying the vector $(x,y)$ by the matrix $\begin{pmatrix}1& 0\\ 0& 1/\sqrt{2}\end{pmatrix}\text{;}$ that would not stretch the $x$ -axis, but shrinks the $y$ axis by the appropriate amount.

🔗

Since this approach uses matrices with non-integer coefficients, it might not seem promising to use matrices. However, one can also think of both conics in such a transformation as coming from matrices.

🔗

Compare the following so-called quadratic forms:

$\begin{equation*} \begin{pmatrix}x & y\end{pmatrix}\begin{pmatrix}1& 0\\ 0& 1\end{pmatrix}\begin{pmatrix}x\\ y\end{pmatrix}=x^2+y^2 \end{equation*}$

$\begin{equation*} \begin{pmatrix}x & y\end{pmatrix}\begin{pmatrix}1& 0\\ 0& 2\end{pmatrix}\begin{pmatrix}x\\ y\end{pmatrix}=x^2+2y^2\text{.} \end{equation*}$

🔗

Fermat's question essentially asked what integers

$n$ can be represented as the first one; Gauss was interested in extending this to ask numbers are representable in by a more general expression of the form

$ax^2+2bxy+cy^2\text{.}$ This generalizes the sum of squares where

$a=1=c,b=0\text{,}$ and is achieved by using the matrix

$\begin{pmatrix}a& b\\ b& d\end{pmatrix}$ instead. It turns out that many such expressions represent precisely the same sets of integers (recall Section 14.3).

🔗

The Sage reference manual uses our example to demonstrate. Consider two seemingly unrelated expressions:

$\begin{equation*} \begin{pmatrix}x & y\end{pmatrix}\begin{pmatrix}1& 0\\ 0& 2\end{pmatrix}\begin{pmatrix}x\\ y\end{pmatrix}=x^2+2y^2\text{ and }\begin{pmatrix}x & y\end{pmatrix}\begin{pmatrix}1& 1\\ 1& 3\end{pmatrix}\begin{pmatrix}x\\ y\end{pmatrix}=x^2+2xy+3y^2 \end{equation*}$

🔗

By the theory of quadratic forms, Fermat's result (recall the discussion around Fact 14.3.1) that a prime number congruent to

$1$ or

$3$ modulo

$8$ can be written as a sum of a square and twice a square should apply to the second expression as well.

🔗

As an example, both should represent the number 11. Clearly

$11=3^2+2\cdot 1^2$ works for the first one, but what about

$x^2+2xy+3y^2\text{?}$ One can try this out in the interact below.

xxxxxxxxxx
 
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)
    pretty_print(html("Integer lattice points on $%sx^2+%sxy+%sy^2=%s$"%(a,b+c,d,output)))

🔗

Looks like

$x=2,y=1$ will do it!

🔗

In this case, the mystery is not deep; we can go between the two expressions with the coordinate transformation

$\begin{equation*} x^2+2xy+3y^2=(x+y)^2+2y^2\text{.} \end{equation*}$

🔗

In general there is some very deep theory involved in deciding which integers can be represented by various forms, 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.

🔗

Subsection 15.4.2 More conic sections

🔗

Let's trace back to looking for integer points on a given curve. Assuming that ellipses are doable by simply counting, what is next?

🔗

The parabola comes to mind. A straightforward parabola could look like

$ny=mx^2\text{;}$ this can be thought of more directly as

$y=ax^2\text{,}$ with

$a=m/n$ in lowest terms.

🔗

Then I can just check all

$x\in\mathbb{Z}$ such that

$n\mid mx^2\text{.}$ Since

$\gcd(m,n)=1$ (again, lowest terms), we would just need to check that

$n\mid x^2$ (so if

$n$ is prime,

$n\mid x$ suffices).

🔗

Example 15.4.3.

If $y=mx^2$ for integer $m\text{,}$ any $x$ will do. That makes sense; integer input had better give integer output, which would be a lattice point!

🔗

Example 15.4.4.

If $2y=x^2\text{,}$ we just look at it as requiring $2\mid x\text{.}$ Then any even $x$ will yield a lattice point, and odd $x$ will not.

🔗

It is not hard to come up with simple divisibility criteria for other parabolas. Try the following interact to check your own hypotheses.

xxxxxxxxxx
 
@interact
def _(m=1,n=2):
    viewsize=3*n
    f(x)=(m/n)*x^2
    plot1 = plot(f,-viewsize,viewsize)
    grid_pts = [[i,j] for i in [-viewsize..viewsize] for j in [0..viewsize^2*(m/n)]]
    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)

🔗

One might think this is all there is to say about points on the parabola. But before we go on, I want to point out something very interesting.

🔗

Look at Figure 15.4.6. In both graphics we examine

$2y=x^2$ and look at some lines. In the first one I create a line (solid red) through two integer points on the conic, in the other I create the tangent line through one integer point. Then in both cases I translate this line so it goes through the points

$(0,0)$ and

$(-2,2)$ of the parabola.

🔗

In both cases the dashed line intersects the parabola in a second point. But in these examples the new point has integer coordinates! Could this be coincidence?