# How can one calculate this Limit?

Let $f(n)$ denote the number of integer solutions of the equation $$3x^2+2xy+3y^2=n$$

How can one evaluate the limit $$\lim_{n\rightarrow\infty}\frac{f(1)+...f(n)}{n}$$

Thanks

-
Did you mean $3x^2 + 2xy + 3y^2$? – Stefan Nov 8 '12 at 15:08
Did you mean to have $y^2$ in the last term on the left side? – coffeemath Nov 8 '12 at 15:08
Yes it is, i will edit. – Tomás Nov 8 '12 at 15:09
$f(1)+f(2)+..+f(n)$ is the number of solutions to the inequality $3x^2+2xy+3y^2\leq n$ – Thomas Andrews Nov 8 '12 at 15:16
This is almost certainly going to equal the area of the region $\{(u,v)\in\mathbb R^2: 3u^2+2uv+3v^2<1\}$. This is an ellipse. – Thomas Andrews Nov 8 '12 at 15:17

Let us elaborate the solution by Thomas Andrews. Though the idea is simple and repeatedly used in other answers, here we want to give a meticulously detailed solution.

As we have observed, the number $f(1) + \cdots + f(n)$ is equal to the integer solution $(x, y)$, or equivalently the number of integer points $(x, y) \in \Bbb{Z}^2$, of the inequality

$$3x^2 + 2xy + 3y^2 \leq n. \tag{1}$$

Now let

$$S_n = \{ (x, y) \in \Bbb{Z}^2 : (x, y) \text{ satisfies } (1) \}$$

be the set of integer solutions $(x, y)$ of $(1)$, and let

$$E_n = \{ (x, y) \in \Bbb{R}^2 : (x, y) \text{ satisfies } (1) \}$$

be the set of points $(x, y) \in \Bbb{R}^2$ satisfying $(1)$. Plainly, $S_n$ is the set of integer points contained in $E_n$ and in this notation we have

$$\#(S_n) = f(1) + \cdots + f(n),$$

where $\#$ denotes the cardinality of a set. We also define

$$A_n = \{ (x, y) \in \Bbb{Z}^n : C(x, y) \subset E_n \},$$

and

$$B_n = \{ (x, y) \in \Bbb{Z}^n : C(x, y) \cap E_n \neq \varnothing \},$$

Now for each integer point $p = (x, y) \in \Bbb{Z}^2$, we associate a unit square

$$C(p) = C(x, y) = \left[x-\tfrac{1}{2}, x+\tfrac{1}{2} \right] \times \left[y-\tfrac{1}{2}, y+\tfrac{1}{2} \right]$$

centered at $p = (x, y)$. Then it is plain to observe that

$$A_n \subset S_n \subset B_n$$

Also, by definition it is clear that we have

$$\# (A_n) = \mathrm{Area}\Bigg( \bigcup_{p \in A_n} C(p) \Bigg) \leq \mathrm{Area}(E_n) \leq \mathrm{Area}\Bigg( \bigcup_{p \in B_n} C(p) \Bigg) = \# (B_n), \tag{2}$$

Now let us digress to a rudimentary real analysis and prove some basic facts. Let $(M, d)$ be a metric space. For $p \in M$ and $\varnothing \neq A \subset M$, consider the minimum distance between $p$ and $A$

$$\mathrm{dist}(p, A) = \inf \{ d(p, q) : q \in A \}$$

and correspondingly the $\epsilon$-neighborhood $A^{\epsilon}$ of $K$ defined by

$$N_{\epsilon}(A) = \{ q \in M : \mathrm{dist}(q, A) < \epsilon \}.$$

Then we have the following proposition.

Proposition. If $F$ is closed, $\bigcap_{\epsilon > 0} N_{\epsilon}(F) = F$.

Proof. Let $F' = \bigcap_{\epsilon > 0} N_{\epsilon}(F)$. Since $F \subset N_{\epsilon}(F)$ for each $\epsilon > 0$, we have $F \subset F'$. To show the converse, let $p \in F'$. Then for each $n$ we have $p \in N_{1/n}(F)$ and hence there exists $q_n \in F$ such that $d(p, q_n) < \frac{2}{n}$. This shows that $q_n \to p$. Since $F$ is closed, the limit must lie in $F$. Therefore $p \in F$ and hence $F' = F$. ////

Now let us return to the original problem. For each $p \in B_n \setminus A_n$, we have $C(p) \cap \partial E_n \neq \varnothing$. This implies that

$$C(p) \subset N_{2}(\partial E_n).$$

But by the scaling and the homogeneity of the polynomial $3x^2 + 2xy + 3y^2$, clearly we have

$$E_n = \sqrt{n} E_1 = \{ (\sqrt{n}x, \sqrt{n}y) : (x, y) \in E_1 \}$$

and accordingly

$$N_{2}(\partial E_n) = \sqrt{n} N_{2/\sqrt{n}}(\partial E_1)$$

This shows that

\begin{align*} \# (B_n \setminus A_n) & = \mathrm{Area} \Bigg( \bigcup_{p \in B_n \setminus A_n} C(p) \Bigg) \leq \mathrm{Area} \big(N_{2}(\partial E_n)\big) \\ & = \mathrm{Area} \big(\sqrt{n} N_{2/\sqrt{n}}(\partial E_1)\big) = n \mathrm{Area} \big(N_{2/\sqrt{n}}(\partial E_1)\big) \tag{3} \end{align*}

• From $(3)$, we have $$0 \leq \frac{\#(B_n) - \#(A_n)}{n} \leq \mathrm{Area} \big(N_{2/\sqrt{n}}(\partial E_1)\big),$$ which goes to zero as $n \to \infty$ by the monotonicity of the Lebesgue measure together with the fact that $\mathrm{Area}(\partial E_1) = 0$. Here we used the proposition above.

• Thus from $(2)$, we have \begin{align*} \mathrm{Area}(E_1) = \frac{\mathrm{Area}(E_n)}{n} &\leq \frac{\#(B_n)}{n} \leq \frac{\#(A_n)}{n} + \frac{\#(B_n) - \#(A_n)}{n} \\ &\leq \frac{\mathrm{Area}(E_n)}{n} + o(1) = \mathrm{Area}(E_1) + o(1) \end{align*} and therefore $$\mathrm{Area}(E_1) = \lim_{n\to\infty} \frac{\#(A_n)}{n} = \lim_{n\to\infty} \frac{\#(S_n)}{n} = \lim_{n\to\infty} \frac{\#(B_n)}{n} = \mathrm{Area}(E_1).$$

Now it remains to evaluate the area of the ellipse $E_1$. Let

$$A = \begin{pmatrix} 3 & 1 \\ 1 & 3 \end{pmatrix}$$

so that $\left< \mathrm{x}, A\mathrm{x} \right> = 3x^2 + 2xy + 3y^2$ for $\mathrm{x} = (x, y)$. Then by spectral theory for symmetric matrices, there exists a rotation matrix $R$ such that $\left< R\mathrm{x}, DR\mathrm{x} \right>$ for $D = \mathrm{diag}(\lambda_1, \lambda_2)$. Then with a new coordinate $(X, Y) = R\mathrm{x}$, we have $\lambda_1 X^2 + \lambda_2 Y^2 \leq 1$. Therefore the area of the ellipse $E_1$ is given by

$$\mathrm{Area}(E_1) = \frac{\pi}{\sqrt{\lambda_1 \lambda_2}} = \frac{\pi}{\sqrt{\det A}} = \frac{\pi}{2\sqrt{2}}.$$

-
Nice and clear! Thank you. – Theo Nov 8 '12 at 17:56

The ellipse $Ax^2 + Bxy + Cy^2 = n$ with discriminant $\Delta=-B^2 + 4AC > 0$ has an area of $$\rm{Area} = \frac{2\pi n}{\sqrt{\Delta}}$$ In this case we have $A=3$, $B=2$ and $C=3$ for an area of $\frac{\pi n}{2\sqrt{2}}$. It is rather well known that the number of lattice points inside an ellipse is given by $$N = \mathrm{Area} + \mathcal{O}\left(\sqrt{n}\right)$$ So your limit is $$\lim_{n\rightarrow \infty}\frac{\frac{\pi n}{2\sqrt{2}} + \mathcal{O}(\sqrt{n})}{n} = \lim_{n\rightarrow \infty}\frac{\pi}{2\sqrt{2}} + \mathcal{O}\left(n^{-\frac{1}{2}}\right) = \frac{\pi}{2\sqrt{2}}$$ For a reference to the above results if unfamiliar, see Advanced Number Theory by Cohn, page 160-161.

-
This is much cleaner than my approach! +1. – coffeemath Nov 8 '12 at 16:30