How many solutions are there to $F(n,m)=n^2+nm+m^2 = Q$?

Let $n,m$ be two positive integers, we consider: $$F(n,m)=n^2+nm+m^2$$

Let $Q$ be one value reach by $F(n,m)$.

How many different pairs $(n,m)$ verify $F(n,m)=Q$?

-
The trick in this instance is that $n^2+nm+m^2$ is the norm in the ring $\mathbb{Z}[\omega]$ where $\omega=\frac{1+\sqrt{-3}}2$. Then $N(n+m\omega)=n^2+nm+m^2$. Since $\mathbb{Z}[\omega]$ is a unique factorization domain, you get results like the result for the sum of two squares. –  Thomas Andrews Jun 8 '11 at 17:46
@Eric and Ray: Sorry about my erroneous answer; I was too quick to "jump the gun" and as I pursued the problem after posting, I realized I overlooked the restriction to positive m, n...and further, I realized there are far more solutions than my erroneous post revealed. –  amWhy Jun 8 '11 at 17:47
@Thomas Andrews: That is an excellent point! I wish had seen that comment before typing my answer. –  Eric Naslund Jun 8 '11 at 18:35
@Amwhy: It happens to all of us, no worries. (I have jumped the gun like this many times!) –  Eric Naslund Jun 8 '11 at 18:42

1 Answer

As it turns out, we can give a complete answer to this question. The exact number of solutions depends on the prime factorization of $Q$ Specifically, it is a function of the exponents of the prime factors which are congruent to $1$ mod $3$, with the condition that all the factors congruent to $2$ modulo $3$ have their prime factors appear with even multiplicity.
Note: I have not yet provided a proof, the result that primes of the form $1+3k$ can be represented is a theorem of Jacobi.

Let $$Q=\prod_i q_i^{\alpha_i} \prod_i p_i^{\beta_i}$$ where the $q_i$ are $1$ mod $3$ and the $p_i$ are $2$ mod $3$. Our equation $n^2+nm+m^2$ has solutions if and only if each $\beta_i$ is even.

Proof: Take the equation modulo $3$. By case analysis for $n,m$ the right hand side cannot be congruent to $2$, and hence the statement follows.

Remark: Notice the following similarity to the sum of squares problem (points on a circle).

The Answer: Suppose that as before $$Q=\prod_i q_i^{\alpha_i} \prod_i p_i^{\beta_i}$$ where the $q_i$ are $1$ mod $3$ and the $p_i$ are $2$ mod $3$. Suppose as well that all of the $\beta_i$ are even. (Otherwise we can have no solutions)

Let $$B=(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_n+1).$$ Then the number of non-negative integer solutions to $$m^2+mn+n^2=Q$$ is exactly $$\left\lceil\frac{B}{2}\right\rceil.$$
(Again notice the similarity to the sum of squares function)

In particular, if $l(n)$ is the number of representations where $n,m$ are any integers, (that is positive or negative) then $$l(n)=2B.$$

Hope that helps.

-
This is a very nice answer. One comment: I'm not sure why you're diagonalizing -- you don't seem to use it anywhere. More fundamentally, the given quadratic form is the norm form of the maximal order of $\mathbb{Q}(\sqrt{-3})$, whereas $x^2 + 3y^2$ is the norm form of the nonmaximal order $\mathbb{Z}[\sqrt{-3}]$, which is not a UFD. So in fact if you wanted to study the form $x^2 + 3y^2$ you would do it by comparing to $x^2 + xy + y^2$, not the other way around. Note also that even without the change of variables you are looking for lattice points on an ellipse. –  Pete L. Clark Jun 8 '11 at 18:45
Well, just to be clear, $\mathbb{Z}[\sqrt{-3}]$ is not a UFD: see e.g. Section 3 of math.uga.edu/~pete/8430notes2.pdf for some commentary. (Note also that the quadratic form cannot be diagonalized over $\mathbb{Z}$, only over $\mathbb{Q}$.) –  Pete L. Clark Jun 8 '11 at 19:11
@Pete: Ok, thanks for the note! I don't know why I thought it wasn't. –  Eric Naslund Jun 8 '11 at 19:27