# A counting problem on the integer lattice

Let $K$ be a subset of the integer lattice $\mathbb Z^2$such that it contains elements of the form $k=(k_1,k_2)$ where $k_1,k_2$ are integers and $k_2\neq 0$. Find $m$, an integer if possible, such that the number of negative elements of the set $\{|k|^2-m^2:k \in K\}$ is odd. Here $|k|^2=k_1^2+k_2^2$. Is it possible to characterize all such $m$'s.

• If I understand the question, we need to consider the set $K'$ consisting of $|k|^2$ for $k\in K$. Sort this set in increasing order $j_1<j_2<\dots$. Then the desired $m$ values are those with $m^2$ satisfying $j_{2i-1} \leq m^2 < j_{2i}$. Whether this set admits a nicer description will depend on $K$. – Hugh Thomas Sep 29 '14 at 18:38
• @ Hugh Thomas Many thanks for your comment. – Shibi Vasudevan Sep 29 '14 at 20:10

## 1 Answer

If you let $p_r=1$ if there are any elements of $K$ at distance $\sqrt{r}$ from the origin and $p_r=0$ otherwise, then what you want is the set of $m$ such that $\sum_{r=1}^{m-1}p_r$ is odd.

• @ David Bevan: Thanks for the answer. But why are you counting all such points. Wouldn't points that share a four fold symmetry contribute only once? – Shibi Vasudevan Sep 29 '14 at 16:02
• @Shibi, I'd misread the question. I've now corrected my answer. It's not just 4-fold symmetry you have to worry about. For example, $(1,7)$ and $(5,5)$ are at the same distance from the origin. – David Bevan Oct 20 '14 at 12:42