Calculate the number of nearest neighbours in particular graphs on $\mathbb Z^d$

Question

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

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

2. What are the graphs "$G$" called?

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

4. For dimension d = 3 and higher how do we even calculate the number of nearest neighbours in graphs like $G$?

Answer 1

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.

Answer 2

Remarks (an answer will follow):

1. 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.
2. 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$.
3. 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}$?