[seqfan] Re: Lattice Squares

[David Radcliffe]

On Sat, Jul 18, 2009 at 1:13 PM, <franktaw at netscape.net> wrote:
> And, without going into detailed calculations, one would expect this to
> be a 4th degree polynomial: there are two degrees of freedom for the
> top left corner, and two more for the top right corner; the remaining
> corners are then determined.  So A014820 is certainly correct.

That's an excellent point. If we know that the function is a polynomial, then
it is easy to determine the correct polynomial. I have an argument for this,
but perhaps it is overly complicated.

Let the vertices be (x1, y1), (x2, y2), (x3, y3), and (x4, y4), where
(x_i, y_i) is a lattice point in the i-th quadrant.

These four points are the vertices of a square iff they satisfy a system of
linear equations:

  x2 - x1 = y2 - y3 = x3 - x4 = y1 - y4
  y1 - y2 = x2 - x3 = y4 - y3 = x1 - x4

Let L be the set of lattice points satisfying these conditions. This is a
four-dimensional sublattice of Z^8.

Let P be the polytope defined by the following inequalities:
  0 <= x1, y1, -x2, y2, -x3, -y3, x4, -y4 <= 1.

Then the number of squares whose vertices are lattice points in [-n,n]^2 with
one vertex in each quadrant is equal to #(L \cap nP). This is known to be
a polynomial of degree 4 by Ehrhart's theorem.
(http://en.wikipedia.org/wiki/Ehrhart_polynomial)

Now, this includes squares with one or more vertices on a coordinate axis.
But if we set some of the coordinates equal to zero, then we still obtain a
polynomial function for the number of squares, and the inclusion-exclusion
formula yields a polynomial equation for the number of squares with no
vertices on the coordinate axes.

David Radcliffe