Maximal packings of the integers

Question

How does one show that for a given packing body $B$ (a finite set of integers) there is a periodic packing of the integers by disjoint translates of $B$ that achieves as its density the supremum of the set of densities achieved by all periodic packings?

I know (via a compactness argument) that the supremum is achieved by some packing, but my argument does not give a packing that is periodic.

Surely this result is in the literature? Maybe it's easy but I'm just not seeing it. (It can't be completely trivial since corresponding assertions in higher dimensions are false, at least if we allow ourselves several packing bodies: consider aperiodic tilings, conceived of as packings of full density.)

Answer 1

Once you have it for some packing (and the standard mumbo-jumbo about achieving (as true density) the supremum of upper densities over all packings, periodic or not), the (upper) density of certain not too long intervals $A---A$ ($A$ here is some not too short packing pattern) is positive (because every sufficiently long interval contains an interval of that sort with some $A$ and there are only finitely many possible $A$ and finitely many possible pattern lengths). If $---A$ has strictly lower density than the supremum, you can improve the upper density of your packing by replacing each occurrence of $A---A$ by a single $A$, which we assumed impossible. Otherwise $---A---A---A---$ is the packing you want.

Answer 2

The difference between this and higher dimensions is that the evolving boundary is finite.

I think I could make this explanation tighter, but maybe this will be clear enough: I will describe a particular finite directed graph $G.$ A packing corresponds to a certain walk in $G$ and, if it makes the (or an) optimum choice at a certain node, then there is no reason not to have it do the same thing every future time it arrives that node.

Given $B$ with minimum element $0$ and maximum element $b$, a packing is some union $P=\bigcup_{i \in \mathbb{Z}}B+x_i.$ We can stipulate that $x_i \lt x_j$ when $i \lt j.$ Then an initial segment is $P_j=\bigcup_{i \lt j}B+x_i.$ For convenience, call an integer an empty space or full space of $P$ or $Pj$ according as it is not or is an element. To get to from $P_j$ to $P_{j+1}$ a choice has to be made of $x_{j} \in [x_{j-1}+1,x_{j-1}+b+1]$ with $B+x_{j}$ disjoint from $P_j.$

The state at $P_j$ is the pattern of empty and full spaces relevant to the choice of of $x_j.$ Specifically, the set $S_j \subseteq\{{1,2,\cdots,b-1\}}$ determined as follows. let $z$ be leftmost empty space greater than $x_{j-1}.$ Then $S_j=\{{t-z \mid t \in P_j ,t \gt z\}}.$

The graph $G$ consists of the possible states with a directed edge from $S$ to $S'$ if a single copy of $B$ could turn a partial packing with state $S$ to one with state $S'.$ Then a packing corresponds to an infinite (in the past and future) walk in this graph.

Answer 3

The same approach as the annswer by Aaron Meyerowitz, fleshed out a bit differently: Given a finite subset $B$ of $\mathbb Z$, let $d=\max(B)-\min(B)$ be its diameter. Consider the following finite directed "packing graph" $\Gamma$ with $\leq 3^d$ vertices: A vertex of $\Gamma$ is a word $\mathbf w=w_1\ldots w_d$ of length $d$ in $\{\alpha,0,\omega\}^d$ such that that there exists a packing of translates of $B$ with the smallest element of $B$ in positions marked $\alpha$, with the largest element of $B$ in positions marked $\omega$, letters $0$ correspond either to an unoccupied place or a place occupied by a non-extremal element of $B$. A vertex $\mathbf w$ of $\Gamma$ encodes thus a packing of translates of $B$ "viewed in an observational window of length $d-1$".

A directed edge joins a vertex $w_1\ldots w_d$ to all vertices of the form $w_2\ldots w_dx$ (with $x$ in $\{\alpha,0,\omega\}$) in $\Gamma$. Edges of $\Gamma$ encode thus the effect of "shifting the window of observation". Every vertex $w_1\ldots w_d$ is the starting point and the endpoint of at least one directed edge. The maximal number of arriving or parting edges is two: If $w_1=\alpha$ then $w_1\ldots w_d$ ends at $w_2\ldots w_d\omega$ and it always ends at $w_2\ldots w_dx$ with $x$ in $\{0,\alpha\}$ otherwise. Vertices of $\Gamma$ can be 'weighted' by the relative density in the corresponding window realized by an associated packing. Any packing of $\mathbb Z$ by translates of $B$ gives now rise to an infinite path in $\Gamma$. Maximal density is realized by a (not necessarily unique) loop of maximal density (defined in the obvious sense) inside $\Gamma$. (The proof that the maximum is indeed achieved by a loop needs a bit of winnowing. By the way, loops of maximal densities might intersect leading to a non-enumerable set of maximal packings).