Dan is walking paths that I am having trouble following. But I have been thinking about this some more, and I think I can rigorize my thoughts to a certain extent. To be sure we are talking about the same thing, let me restate Jim's conjecture as explicitly as I can. Let B be a finite subset of Z, and let B[n] = { x + n | x in B }. So B[0] is B itself, and B[4] is a translation of B 4 units to the right. A packing of Z by B is a set { B[n] | n in T }, where T is a subset of Z, such that for all i and j in T, B[i] and B[j] are disjoint. (I read Jim's original statement to exclude reflections of B, that is, sets of the form (-B)[n].) That is, the translated copies of B are not permitted to overlap. In this discussion, T is usually infinite; we call T the "index set" of the packing. If P is a packing of Z by B, then we allow ourselves to breezily say that an integer x is "in P" if x is in some member of P. Let f(n) be the number of integers x such that |x| <= n and x is in P. If the limit of f(n)/(2n+1) as n -> oo exists, call that limit the density of P. Jim reports having proven, using compactness, that over all packings of Z by B that have densities, some packing actually exhibits the maximum achievable density. A set of integers S is periodic with period n, exactly when S[n] = S. A packing is periodic exactly when its index set is periodic. Jim conjectures, and my intuition strongly agrees with his, that for any finite subset B of Z, that the maximal density can be achieved with a periodic packing of Z by B. (His compactness proof only guarantees a packing, not necessarily a periodic packing.) At this point I am pretty sure I can prove Jim's conjecture, using a "finite state" argument. The states that I am envisioning are, roughly, the possible "shapes" of the upper end of a partial packing, where the index set is all less than some upper limit K. We would show that all "reasonable" packings by B can be constructed by adding copies B[n] one at a time, in increasing order of n, in such a way that the upper end would always show one of a finite set of configurations. The word "reasonable" covers a few simple properties of a packing, for which we can easily show that the maximum density can always be achieved by a "reasonable" packing. I am too tired tonight to complete the argument. Perhaps another funster will do it for me, or better yet, Jim will see where I am going and finish it himself. If nobody steps up, I will finish up another time. On Thu, Jul 27, 2017 at 9:51 PM, Dan Asimov <dasimov@earthlink.net> wrote:
I see now that I completely overlooked a general type of "periodic" packing of the finite packing body B: where there is
----- a) a finite set F of group elements of Isom(Z) = the isometry group of the integers
and
b) an integer n in Z-{0}
such that all the sets of the form
g(B) + K*n
for any g in F and any K in Z *are disjoint*. ----- This is much more general than what I originally This definition depends on what kind of transformations are allowed to be in the finite set F. Can they be all isometries of Z (i.e., all mappings for the form x |—> x + j and of the form x |—> j - x for some integer j), or just the first kind (translations)?
Jim, is this approximately what you mean by a "periodic packing of the integers" by a finite packing body B ???
—Dan
---- I don't think the initial set of "states" is finite: It is all periodic packings of the finite set B.
I take this to mean all packings pack(B, n) of the form
pack(B,n) = {B + K*n | K in Z}
for some fixed n in Z-{0}, such that it is in fact a packing, i.e.:
B + K*n is disjoint from B + L*n for all K <> L.
However, it should be fairly easy to exclude all but a finite number of n as candidates for the *densest* packing.
When there is a packing for a given n in Z-{0}, I guess the density is just
dens(pack(B,n) = |B| / n
. Let
diam(B) = max{|i - j| | i,j in B}
. Then it seems clear to me that if we let
n_0 = diam(B) + 1
then any n > n_0 cannot possibly give rise to a denser
packing than pack(B,n_0). (Which is a packing since the
translates of B by multiples of n_0 must miss each other.)
From: Allan Wechsler <acwacw@gmail.com> Sent: Jul 27, 2017 3:28 PM
I think this would be approached via the same "finite state machine" technique that Rich sketched regarding Ed Pegg's "Mrs. Perkins's Quilt" phenomena. Because the set of states is finite, a search algorithm looking for an optimal packing will eventually enter a periodic regime. Obviously what I just said is not a proof, but rather a "reason to believe", with a possible pointer in the direction of a proof. I would be super-surprised if the conjecture is false.
On Thu, Jul 27, 2017 at 6:02 PM, James Propp <jamespropp@gmail.com> wrote:
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.)
PS: I just posted this on MathOverflow ( https://mathoverflow.net/questions/277426/maximal- packings-of-the-integers ), so if you "go with the 'flow", consider posting there.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun