Proving that $\sum_{(m,n)\in \Bbb Z \times \Bbb Z}\frac{1}{m^2+n^2+1}$ diverges. I must prove that $$\sum_{(m,n)\in \Bbb Z \times \Bbb Z}\frac{1}{m^2+n^2+1}$$ diverges. I understand that given $K > 0$, I must find a finite subset of $\Bbb Z \times \Bbb Z$, say, $F$, such that $\sum_{(m,n)\in F}\frac{1}{m^2+n^2+1} > K$.
I know that I can't be lazy and just walk in diagonals, because $\sum 1/(2n^2+1) < +\infty$.
Call $Q_n = ([-n,n]\times[-n,n])\cap (\Bbb Z \times \Bbb Z)$. Sure, $Q_n$ is finite for all $n$. Given $K > 0$, I want to find $n$ such that the sum over $Q_n$ goes over $K$. I can't think of a better choice of finite set to compute the sum over: I'm going in all directions, certainly it should blow up. For example, $Q_2$:

Using and abusing of symmetry, I got so far (hopefully correct): $$ \sum_{(a,b)\in Q_n}\frac{1}{a^2+b^2+1} = 1+4\sum_{i=1}^n\frac{1}{i^2+1} +4\sum_{i=1}^n\frac{1}{2i^2+1} +8\sum_{1\leq i<j\leq n}\frac{1}{i^2+j^2+1}.$$
Needless to say, this is too complicated of an expression for me to find $n = n(K)$ to do the job - I don't know even how to find closed expressions for each term above. Maybe using $Q_n$ is overkill, and we can find a smaller set to compute the sum over.
Hints, ideas, a magic solution? Thanks!
 A: You can compare with an integral, as in the case of the harmonic series when you compute the integral of $x^{-1}$.
Note that

$$\int_{\Bbb R^2}{dxdy\over x^2+y^2+1}=\int_{0}^{2\pi}\int_0^\infty {rdrd\theta\over r^2+1}=\infty.$$

and by sampling the function over boxed sectors $[n,n+1)\times [m,m+1)$ you have that the upper and lower sums bound the integral on each side and are equal (up to removal of finitely many terms) your sum.
A: It includes $\frac{1}{p+1}$ for every prime $p\equiv 1\pmod 4$, and $\sum_{p\equiv 1\pmod 4} \frac{1}{p}$ diverges by Dirichlet. Then use $\frac{1}{p+1}>\frac{1}{2p}$.
A: By the Gauss circle problem, it is well known that the number of lattice points in the set $\{x^2+y^2\leq R^2\}$ is given by $\pi R^2 + O(R)$, hence the series is divergent by comparison with the harmonic series, once we estimate the number of lattice points in the annulus $R_1^2\leq x^2+y^2\leq R_2^2$.
A: You have already done some of the work in setting up your equation. You didn't immediately get a solution because of your choice of decomposition of $\mathbb{Z}\times\mathbb{Z}$. Try instead to break it in infinite vertical lines $(i,n): i\text{ fixed and }n\in \mathbb{Z}$. There you will have the sum $\displaystyle\sum_{n=1}^{\infty}\frac{1}{i^2+n^2+1}>\sum_{n=i}^{\infty}\frac{1}{(n+1)^2}$ (actually twice that sum to account for negative $n$ also). 
Can you show now that this sum is greater than $\frac{1}{i+2}$? If not, think about the integral test... After this you should be done, using that the harmonic series diverges.
A: If you partition $\mathbf{Z} \times \mathbf{Z}$ into "(boundary) squares of side $2k + 1$", i.e., you let $S_{k} = Q_{k} \setminus Q_{k-1}$ denote the set of pairs $(i, j)$ satisfying (i) $|i| = k$ or $|j| = k$ and (ii) $|i| \leq k$ and $|j| \leq k$, then for each $k \geq 1$ you have:


*

*A disjoint union $\bigcup_{k=1}^{n} S_{k} = Q_{n} \setminus\{(0, 0)\}$;

*$S_{k}$ contains $8k$ elements;

*$\dfrac{1}{i^{2} + j^{2} + 1} \geq \dfrac{1}{2k^{2} + 1}$ for each $(i, j)$ in $S_{k}$ (since $i^{2} + j^{2} \leq 2k^{2}$).
The sum over $Q_{n}$ is therefore bounded below by a (multiple of) a partial sum of the harmonic series.
A: Compute a lower bound for the summation in $j$ for each $i$ using
$$
\begin{align}
\sum_{j\in\mathbb{Z}}\frac1{i^2+j^2+1}
&\ge\overbrace{\vphantom{\int}\frac1{i^2+1}}^{j=0}+\overbrace{2\int_1^\infty\frac{\mathrm{d}x}{i^2+x^2+1}}^{j\ge1\text{ and }j\le-1}\\
&=\frac1{i^2+1}+\frac2{\sqrt{i^2+1}}\int_{\frac1{\sqrt{i^2+1}}}^\infty\frac{\mathrm{d}x}{x^2+1}\\
&\ge\frac1{i^2+1}+\frac2{\sqrt{i^2+1}}\int_1^\infty\frac{\mathrm{d}x}{x^2+1}\\
&\ge\frac1{i^2+1}+\frac{\pi/2}{\sqrt{i^2+1}}\\
\end{align}
$$
Now show that this series diverges when summed in $i$ by comparing with the harmonic series.
