I heard it from @benjamin_leis, and he says he heard it from @CMonMattTHINK, and I love it:

The number of integer solutions to $x^2 + xy + y^2 = a$ appears to be a multiple of six for all $a \in \mathbb{Z_+}$ . Why?

How good a puzzle is this? I started my swimming class on Thursday and decided to swim non-stop until I solved it. Forty lengths later they kicked me out of the pool.

As always, spoilers below the line.

This is a very pretty puzzle. Some observations to start with:

  • The curve describes an ellipse
  • There are two lines of symmetry to the ellipse, $x=y$ and $x=-y$.
  • The extreme points of the ellipse are on the lines $x+2y=0$ and $2x+y=0$.

How I did it

I think it’s useful to break my solution into two bits, and acknowledge that the “correct”, underlying answer came after a lot of head-scratching and missteps. The key bit of reasoning was:

If $(X,Y)$ is an integer solution, fixing $y=Y$ gives a quadratic $x^2 + Yx + Y^2-a=0$. > I could solve that explicitly, but I don’t need to; $Y^2-a$ is an integer, so the second solution is also an integer; the solutions sum to $-Y$, so the other solution is $x=-X-Y$, which (for convenience) I’ll call $Z$.

That means, if $(X,Y)$ is an integer solution, so is $(Z,Y)$. Applying similar reasoning to the resulting point, fixing $x=Z$ gives a solution at $(Z,X)$.

We can carry on around to get $(Y,X)$, $(Y,Z)$ and $(X,Z)$ before returning to $(X,Y)$, giving six algebraically distinct solutions.

BUT! Rotational symmetry also gives a solution at $(-X, -Y)$ - so changing the signs on all of the points we found before gives a further six solutions, a total of 12.

However, they aren’t all necessarily distinct! If any pair of $X$, $Y$ and $Z$ are equal, then each point we’ve found appears twice, leaving us with six solutions (in fact, two lie on the minor axis and the remaining four at the extreme points).

Underlying group structure

I wasn’t happy with my answer until I managed to shoehorn a group structure onto the solutions. The points can be classified by three pieces of information:

  • Which letter is missing (isomorphic to $\mathbb{Z}_3$, with $X \sim 0$, $Y \sim 1$ and $Z \sim 2$)
  • Whether the signs are + or - (isomorphic to $\mathbb{Z}_2$)
  • Whether the second letter immediately follows the first (isomorphic to $\mathbb{Z}_2$ as well). By convention, $Y$ follows $X$, $Z$ follows $Y$ and $X$ follows $Z$ in a pleasing cycle.

And this gives a natural way to combine any pair of integer solutions!

The point $(X,Z)$ has $Y$ missing, positive signs and is out of order.

The point $(-Y,-X)$ has letter $Z$, negative signs and is out of order.

Combining them together, $Y + Z \sim (1 + 2)$, which is $0 \sim X$; the sign is negative, and the letters must be in order, giving $(-Y, -Z)$.

This is a group, because it’s isomorphic to $\mathbb{Z}_3 \times \mathbb{Z}_2 \times \mathbb{Z}_2$, and has order 12.

(In the degenerate case when a pair of variables is equal, each point coincides with exactly one other.)

Even more underlying

After reading around a bit on Diophanitine equations - by which I mean scanning a few paragraphs in a huff - I realised that the ellipse equation can be rewritten as:

  • $2x^2 + 2xy + y^2 = 2a$
  • $x^2 + x^2 + 2xy + y^2 + y^2 = 2a$
  • $x^2 + (x+y)^2 + y^2 = 2a$

Or, equivalently, $x^2 + (-x-y)^2 + y^2 = 2a$. Why that way?

To tell the truth, that’s still a bit nebulous. However, it has the lovely pair of properties:

  • by symmetry, if $(X,Y)$ is a solution, any permutation of two elements of ${ X, Y, -X-Y }$ is also a solution
  • by a different symmetry, if $(X,Y)$ is a solution, any permutation of two elements of ${-X, -Y, X+Y}$ is also a solution.

If $X$, $Y$ and $-X-Y$ are all different, then there are six solutions from the first set and six from the second; if two are the same, then there are three from each.

In either case, the number of solutions is a multiple of six.

Can I stop swimming now? I need to put my computer in rice.