Sharp Bounds for Discrete Cube Skeleta

Abstract

Fix integers $0\le k<n$. Let $F_{n,k}(N)$ be the least size of a finite set $B\subset {\mathbb{Z}}^n$ that contains a filled axis-parallel cube $k$-skeleton centered at each point of some $N$-point set. We prove that $F_{n,k}(N)$ has order $N^{1-(n-k)/(2n^2)}$, with constants depending only on $n$ and $k$. Thornton proved the upper bound and lower bounds with every smaller exponent; the endpoint lower bound was open for $k\ge 1$. For square boundaries in ${\mathbb{Z}}^2$, the exponent is $7/8$. A midpoint count and Shearer's inequality handle large radii; induction in lattice cells handles small radii.

arXiv comment8 pages