Re: [math-fun] Maximal packings of the integers
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.
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
Allan is right, and the MathOverflow user named "fedja" has explained it to me very clearly: https://mathoverflow.net/questions/277426/maximal-packings-of-the-integers Jim On Thursday, July 27, 2017, Allan Wechsler <acwacw@gmail.com <javascript:_e(%7B%7D,'cvml','acwacw@gmail.com');>> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I was thinking of translations only. More specifically, I think of a packing of Z by translates of the finite set B as being determined by a set S (a subset of the integers) such that the sets B+s are disjoint (as s ranges over S), and I call the packing periodic if the indicator function of the set S is periodic. Sorry for not saying this sooner. Jim On Thursday, July 27, 2017, 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 <javascript:;>> 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 <javascript:;>> 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 <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Jul 28, 2017, at 6:25 AM, James Propp <jamespropp@gmail.com> wrote:
I was thinking of translations only. So that excludes the Socolar-Taylor monotile I was thinking of, as inspiration for a counterexample in 2D (this tiling requires both rotations and reflections of the tile).
But here’s a related challenge: Construct a finite set of "lattice tiles for Z^2" (finite subsets of Z^2, not necessarily connected by adjacency), such that the maximum packing density in the lattice torus (Z/B)^2, of translates of the tiles, is strictly less than the supremum of the packing density in Z^2, again by translates, for arbitrarily large B. Certainly some such set of lattice tiles can be constructed using the Socolar-Taylor tile as a guide, but the tiles will comprise many lattice points. My challenge is therefore to find such a set that also minimizes the cardinality of lattice points (in the tile set). -Veit
More specifically, I think of a packing of Z by translates of the finite set B as being determined by a set S (a subset of the integers) such that the sets B+s are disjoint (as s ranges over S), and I call the packing periodic if the indicator function of the set S is periodic.
Sorry for not saying this sooner.
Jim
participants (4)
-
Allan Wechsler -
Dan Asimov -
James Propp -
Veit Elser