[math-fun] Discretized disk-packing
Let d_n be the greatest density achieved by any subset of Z^2, no two points of which are closer in Euclidean distance than sqrt(n). What is known about d_n? Is it known to be always rational? I can use a compactness argument to show that the supremum density is achieved (that's why I felt free to write "the greatest density" above) but I can't prove that it's achieved by a doubly-periodic set (which would imply rational density). I get n d_n approx 2/sqrt(3) for large n using a back-of-the-envelope calculation, but I may have mis-programmed the envelope, especially since it's not an envelope but rather a bag for a pizza-slice-to-go --- a medium with no track-record as a calculation-aid. Jim Propp
Focussing on small n rather than on the asymptotics, I get d_1 = 1, d_2 = 1/2 (and can prove both of those). d_3 = d_4 <= 1/4, but I can't prove equality. For n = 5 I can see a pattern with density 1/5, and I think this generalizes to all n that are the sum of two squares (though I can't prove it can be bettered). On Tue, Mar 12, 2013 at 5:32 PM, James Propp <jamespropp@gmail.com> wrote:
Let d_n be the greatest density achieved by any subset of Z^2, no two points of which are closer in Euclidean distance than sqrt(n). What is known about d_n? Is it known to be always rational? I can use a compactness argument to show that the supremum density is achieved (that's why I felt free to write "the greatest density" above) but I can't prove that it's achieved by a doubly-periodic set (which would imply rational density).
I get n d_n approx 2/sqrt(3) for large n using a back-of-the-envelope calculation, but I may have mis-programmed the envelope, especially since it's not an envelope but rather a bag for a pizza-slice-to-go --- a medium with no track-record as a calculation-aid.
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Allan writes "d_3 = d_4 <= 1/4, but I can't prove equality." Allan's proof is presumably the same as mine: divide the grid into 2x2 blocks and apply the pigeonhole principle. On the other hand, the set 2Z x 2Z has the required property, which gives the reverse inequality, for both n=3 and n=4. For d(5), we get the upper bound 1/5 by dividing the grid into 5-vertex subgraphs shaped like plus-signs (and applying pigeonhole), and the lower bound 1/5 by taking the sublattice of ZxZ spanned by (1,2) and (2,-1). (Right?) What is the first value of n for which it becomes hard to get a pigeonhole-principle upper bound and a doubly-periodic-set lower bound that match? Jim On Tuesday, March 12, 2013, Allan Wechsler <acwacw@gmail.com> wrote:
Focussing on small n rather than on the asymptotics, I get d_1 = 1, d_2 = 1/2 (and can prove both of those). d_3 = d_4 <= 1/4, but I can't prove equality. For n = 5 I can see a pattern with density 1/5, and I think this generalizes to all n that are the sum of two squares (though I can't prove it can be bettered).
On Tue, Mar 12, 2013 at 5:32 PM, James Propp <jamespropp@gmail.com> wrote:
Let d_n be the greatest density achieved by any subset of Z^2, no two points of which are closer in Euclidean distance than sqrt(n). What is known about d_n? Is it known to be always rational? I can use a compactness argument to show that the supremum density is achieved (that's why I felt free to write "the greatest density" above) but I can't prove that it's achieved by a doubly-periodic set (which would imply rational density).
I get n d_n approx 2/sqrt(3) for large n using a back-of-the-envelope calculation, but I may have mis-programmed the envelope, especially since it's not an envelope but rather a bag for a pizza-slice-to-go --- a medium with no track-record as a calculation-aid.
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Tue, Mar 12, 2013 at 5:32 PM, James Propp <jamespropp@gmail.com> wrote:
Let d_n be the greatest density achieved by any subset of Z^2, no two points of which are closer in Euclidean distance than sqrt(n). What is known about d_n? Is it known to be always rational? I can use a compactness argument to show that the supremum density is achieved (that's why I felt free to write "the greatest density" above) but I can't prove that it's achieved by a doubly-periodic set (which would imply rational density).
I get n d_n approx 2/sqrt(3) for large n using a back-of-the-envelope calculation, but I may have mis-programmed the envelope, especially since it's not an envelope but rather a bag for a pizza-slice-to-go --- a medium with no track-record as a calculation-aid.
Wait, shouldn't d_n increase with n, not decrease? As n goes to infinity, you should be able to closely approximate a hexagonal close-packing. Andy
d_n scales like 1/n because of the way it's defined. We could alternatively define D(c), for every positive real number c, as the greatest density (in R^2) of any subset of cZ x cZ, no two points of which are closer than distance 1. D(c) would be a discontinuous function, and I'm not convinced it would be literally increasing, but it should definitely show an overall upward trend as the grid-spacing c approaches 0. (Or am I confused?) Jim On Wednesday, March 13, 2013, Andy Latto <andy.latto@pobox.com> wrote:
On Tue, Mar 12, 2013 at 5:32 PM, James Propp <jamespropp@gmail.com> wrote:
Let d_n be the greatest density achieved by any subset of Z^2, no two points of which are closer in Euclidean distance than sqrt(n). What is known about d_n? Is it known to be always rational? I can use a compactness argument to show that the supremum density is achieved (that's why I felt free to write "the greatest density" above) but I can't prove that it's achieved by a doubly-periodic set (which would imply rational density).
I get n d_n approx 2/sqrt(3) for large n using a back-of-the-envelope calculation, but I may have mis-programmed the envelope, especially since it's not an envelope but rather a bag for a pizza-slice-to-go --- a medium with no track-record as a calculation-aid.
Wait, shouldn't d_n increase with n, not decrease? As n goes to infinity, you should be able to closely approximate a hexagonal close-packing.
Andy
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Allan Wechsler -
Andy Latto -
James Propp