Calculate the number of nearest neighbours in particular graphs on $\mathbb Z^d$ I have some discrete set of points $\Lambda \subset \mathbb Z^d$ such that we have $|x-y| > \alpha$ for some $\alpha > 0$ for all $x,y \in \Lambda$. Here $|\cdot|$ denotes the euclidean norm in $\mathbb R^d$. I am trying to prove that 
$$\max_{x\in\Lambda} \sum_{y\in\Lambda} e^{-|x-y|} \leq C_d \alpha^{-d}$$for some constant $C_d$ only depending on the dimension $d$.
Progress:
I consider the maximal infinite graph $G\subset\mathbb Z^d$ with the length of all edges equal to $\alpha$. For example, in $1$ dimension this is just $\alpha \mathbb Z$ and in $2$ dimensions $G$ is a hexagonal tessellation of $\mathbb R^2$ such that each edge has length $\alpha$. Now I fix $x \in G$. I would then like to say that for each $n \in \mathbb N$ we can define a constant $N_d(n)$ satisfying
$$N_d(n) = |\{y \in G : n\alpha < |x- y| \leq (n+1)\alpha \}|.$$
This means $N_d(n)$ is the number of points in $G$ that are in an annulus of width $\alpha$ and inner radius $n\alpha$ about $x$. We can now write 
$$\sum_{y\in\Lambda} e^{-|x-y|} \leq \sum_{y\in G} e^{-|x-y|} = \sum_{n=0}^\infty \sum_{y\in G \text{ such that }\\ n < |x-y| \leq n+1} e^{-|x-y|} \leq \sum_{n=0}^\infty N_d(n)e^{-\alpha n}$$
Now I hope we can write $N_d(n)$ as a polynomial in n and so this is bounded.
Questions


*

*Is there a closed formula for $N_d(n)$?

*What are the graphs "$G$" called?

*Is there a better way of seeing the inequality that we are trying to prove?

*For dimension d = 3 and higher how do we even calculate the number of nearest neighbours in graphs like $G$?
 A: The points are isolated by the radius $\alpha$, so we might as well consider them $d$-balls of radius $\alpha$.
Any $d$-ball of radius $\alpha$ whose center lies in an annulus of $A(r, R)$ must be entirely contained the annulus $A(r-\alpha, R+\alpha)$.
We have that the volume $V_d(\alpha)$ of a $d$-ball with radius $\alpha$ is
$$V_d(\alpha) =K_d \,\alpha^d,$$
where
$$K_d = \frac{{\pi}^{d/2}}{\Gamma\left(\frac{d}2+1\right)}.$$
It follows that the volume of $A(r-\alpha, R+\alpha)$ is
$$K_d\Big[(R+\alpha)^d-(r-\alpha)^d\Big].$$
Hence, an upper bound on $N_d(n)$ is
$$\frac{\text{Vol}\Big(A(n\alpha - \alpha, (n+1)\alpha + \alpha)\Big)}{V_d(\alpha)}
=
\frac{\text{Vol}\Big(A\big((n-1)\,\alpha, (n+2)\,\alpha \big)\Big)}{V_d(\alpha)}
=
(n+2)^d-(n-1)^d,$$
which is polynomial as you desired.

EDIT: Just pointing out that the only thing that matters is that the points be $\alpha$ distance apart.
The annulus estimate holds regardless of a lattice disposition or of the existence of some particular graph $G$ and follows from the partition of $\mathbb R^d$ itself into annuli.
A: Remarks (an answer will follow):


*

*It is not clear why it is enough to consider the "worst case graph $G$". Why do you have $\sum_{y\in\Lambda} e^{-|x-y|} \leq \sum_{y\in G} e^{-|x-y|}$? You gave no proof of this inequality.

*Why would such a $G$ even exist? $G$ is a subset of the integer lattice by $\alpha>0$ can be any real. And even in the plane with $\alpha=1$ your hexagonal lattice is not contained in $\mathbb Z^2$.

*I don't see a way to get an optimal result, since finding the optimal sets $G$ is likely to be an unsolved problem.


I think it's best not to compare to any $G$, but to calculate directly.
Estimation annulus by annulus is a good idea.
Take any $x\in\Lambda$.
Denote $A(r,R)=\bar B(x,R)\setminus B(0,r)$; this is the closed annulus of outer radius $R$ and inner radius $r$.
Let us denote $S=\sum_{y\in\Lambda} e^{-|x-y|}$.
We can estimate this by
$$
S\leq\sum_{k=0}^\infty s(k),
$$
where
$$
s(k)=\sum_{y\in\Lambda\cap A(k+1,k)}e^{-|x-y|}.
$$
If some point has integer distance to $x$, it can be double counted in the right-hand side.
For any $y\in\Lambda\cap A(k+1,k)$ we have $|x-y|\geq k$, so $e^{-|x-y|}\leq e^-k$.
Thus
$$
s(k)
\leq
e^{-k}|\Lambda\cap A(k+1,k)|.
$$
Estimating the sizes of these finite sets is where $\alpha$ comes in.
This is probably easiest to do by volume estimates.
Consider the balls $B(y,\alpha/2)$ for $y\in \Lambda\cap A(k+1,k)$.
These balls are disjoint (because the distances between the centers are at least twice the radius) and contained in the annulus $A(k+1+\alpha/2,k-\alpha/2)$.
Therefore the sum of the volumes of the balls is bounded by the volume of the annulus.
The volume of the ball $B(x,r)$ is $cr^d$, so we get
$$
|\Lambda\cap A(k+1,k)|c(\alpha/2)^d
\leq
c(k+1+\alpha/2)^d
-
c(k-\alpha/2)^d.
$$
On the right-hand side both terms (for the bigger ball and the smaller ball) have the term $ck^d$ when expanded, and they cancel out, which might give you a slightly bigger estimate.
The estimate we get is
$$
S
\leq
\sum_{k=0}^\infty e^{-k} \frac{(k+1+\alpha/2)^d-(k-\alpha/2)^d}{(\alpha/2)^d}.
$$
Your question doesn't seem to go further than this, so perhaps you want to figure out whether something like this gives the desired final estimate $S\leq C\alpha^{-d}$?
