Isoperimetric stability in lattices

NEW

Problem: Reconstructed conjecture: for fixed finite generating $B\subset \mathbb Z^d$, if a large finite set $A\subset\mathbb Z^d$ has vertex expansion

within a constant factor of the minimum possible for sets of size $|A|$, then $A$ can be covered by $O(1)$ homothetic copies of

whose total Lebesgue volume is $O(|A|)$. The constants may depend on $B,d$, and the boundary-factor, but not on $A$.

This is the natural reading of the concluding sentence, since immediately before it the paper says “large sets $A$ for which $|A+B|-|A|$ is within a multiplicative $O(1)$ factor of its minimum value.”

Result: The conjecture is false.

Take $d=2$ and

Then $C(B)=\operatorname{conv}\{(0,0),(1,0),(0,1)\}$, a right triangle of area $1/2$.

Let $L$ be large and set

Choose $L$ points $p_1,\dots,p_L$ very far from $Q_L$ and from each other, so that all translates $p_i+B$ are pairwise disjoint and disjoint from $Q_L+B$. Define

Then

Also

and each isolated point contributes exactly $2$ new points, so

For any finite $S\subset\mathbb Z^2$, if $r$ is the number of occupied rows and $c$ the number of occupied columns, then $|S|\le rc$, while $S+B\setminus S$ contains at least $\max(r,c)$ points. Hence the minimum possible value of $|S+B|-|S|$ for $|S|=n$ is at least $\sqrt n$. Thus $A$ is within a constant factor of the optimum.

Now suppose constants $N,V$ existed such that every such $A$ could be covered by at most $N$ homothetic copies of $C(B)$ with total area at most $V|A|$. Choose $L>N$, and choose the $p_i$ pairwise separated by distance greater than $2\sqrt{V|A|}$. Any homothetic copy of $C(B)$ with area at most $V|A|$ has diameter at most $2\sqrt{V|A|}$, so it can contain at most one of the points $p_i$. Hence $N$ copies cover at most $N<L$ of the isolated points, contradiction.

Therefore no $O(1)$-copy, $O(|A|)$-volume exact covering statement can hold.

Citation: Counterexample above. Source for notation: Barber, Erde, Keevash, Roberts, “Isoperimetric stability in lattices,” Proc. Amer. Math. Soc. 151 (2023), 5021–5029; arXiv:2007.14457, §4.