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!
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.
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 \(\begin{pmatrix}1& 0\\ 0& 1/\sqrt{2}\end{pmatrix}\); that would not stretch the \(x\)-axis, but shrinks in the \(y\) axis by the appropriate amount.
However, one can also think of both conics in such a transformation as coming from matrices. Compare these: \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\; .\end{equation*} 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 (recall Section 14.3).
The Sage reference manual even uses our example to demonstrate this: \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*} Both of these should fulfill Fermat's result about primes modulo \(8\) in the discussion around Fact 14.3.1; as an example, both should represent 11. Clearly \(11=3^2+2\cdot 1^2\) works, but what about the other version?
Looks like \(x=2,y=1\) will do it. The real reason behind this is that \begin{equation*}x^2+2xy+3y^2=(x+y)^2+2y^2\end{equation*} is a coordinate transformation.)
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 had better give integer output, which would be a lattice point!
If \(2y=x^2\), we just look at it as \(2\mid x\), so that requiring \(x\) even will give lattice points.
And so on.
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 the following two setups in interacts. In one I create the line through two integer points on the conic, in the other I create the tangent line through one integer point.
In both cases you get another integer point! Could this be coincidence?
