3
$\begingroup$

Suppose I have a lattice $L$ that's just $\mathbb{Z}^k$ but scaled in every coordinate by some (potentially different) real numbers. Now I want to construct a finite set of lattice points $S \subset L$ such that I know $S$'s $L_1$-diameter (max of pairwise $L_1$ distances) is bounded above by some $d$. I want to maximize $|S|$.

I looked around and couldn't find an answer. Naively, it seems like the following argument should work:

  1. This should be "almost like" maximizing the volume of a convex (if there are "holes" you can move extremal points into the holes without increasing the diameter) body $B$ (in our case it seems we can assume a polytope, but not necessarily a lattice polytope) with diameter $d$.
  2. The $B$ that solves this constraint "should" be the $L_1$-ball, which should have volume $d^k/k!$.
  3. $B$ should have "about" $\frac{d^k}{k! \operatorname{vol}(L_0)}$ lattice points, where $\operatorname{vol}(L_0)$ is the volume of the fundamental parallelopiped of $L$.

I'm having trouble making these arguments rigorously and I'm a bit wary of reinventing the wheel, so... does this approach "morally" work? If so, are there good references? Most of the sources I've seen start with the convex body and then compute things like $L \cap B$, but here it's a bit awkward as I'm moving from the diameter on the lattice points to the convex body and I need to justify the optimization problem translates correctly.

One particular complaint about the problem (or just my incompetence!) is that it does not seem obvious that I can reduce to the case $\mathbb{Z}^k$, because it is not that obvious that the $L_1$-constraints of the "squished" $\mathbb{Z}^k$ plays well with the approximation to a polytope. But even this would be a useful step (then it starts looking closer to e.g. the Gauss circle problem).

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ You want to maximize $|S|$ given some diameter constraint $d$. It seems equivalent to maximize $\frac{|S|}{d^n}$, where $d^n$ is introduced to make the quantity scale-invariant (sort of --- here I am being imprecise and identifying $|S|$ with volume of the convex hull of $S$). Equivalently, you can minimize $\frac{d^n}{|S|}$. At least in $\ell_2$, this is often called the "thickness of the lattice covering", and there is quite a bit written about it, say for example in Conway and Sloane's Sphere Packings, Lattices, and Groups. This isn't an answer as your setting both has $|S|$ as a point $\endgroup$
    – Mark Schultz-Wu
    Commented Feb 14, 2023 at 10:00
  • $\begingroup$ count, rather than a volume, and is $\ell_1$, and not $\ell_2$, but hopefully this is still somewhat useful. $\endgroup$
    – Mark Schultz-Wu
    Commented Feb 14, 2023 at 10:00
  • $\begingroup$ Yeah I feel the hard part is making the "point count to volume" rigorous here, but this is a novel direction for me to search / learn as well, so thanks! $\endgroup$
    – Yan X Zhang
    Commented Feb 14, 2023 at 19:18
  • $\begingroup$ it isn't rigorous in that it leads to an equality, but you can get bounds. For example, it is straightforward to see that $|S\cap\mathbb{Z}^n| \leq \mathsf{vol}(S + \mathcal{B}_\infty^n(1/2))$, where $+$ is the Minkowski sum, and $B_\infty^n(1/2) = [-1/2,1/2]^n$ is the $\ell_\infty$ ball of radius $1/2$. Then, if you care about $\ell_1$ diameter, you can write something like $S\subseteq B_1^n(\mathsf{diam}(S)/2)$ and $B_\infty^n(1/2) \subseteq B_1^n(n/2)$ to get an upper bound on the point count in terms of solely $\ell_1$ quantities. I remember there being a similar argument for the lower $\endgroup$
    – Mark Schultz-Wu
    Commented Feb 14, 2023 at 19:52
  • $\begingroup$ bound, but don't recall it offhand. $\endgroup$
    – Mark Schultz-Wu
    Commented Feb 14, 2023 at 19:52

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .