-- Packing unit circles in squares: new results
in [Math]
|
Prev: Delayed differential equation
Next: Ordered computation of eigenvalues from good initial estimates, without explicit sorting
From: David W. Cantrell on 28 Apr 2010 17:01 ThomasCR <protokol2020(a)gmail.com> wrote: > Some new results with a new packing program at > <http://critticall.com/SQU_cir.html> Many thanks, Thomas, for that link! (I don't know if you are associated with that web page or not. But in any event, I am also sending a copy of this to Nevenka Kristan.) There is a particular reason that I'm delighted with some of the new results on that web page: On Mar. 7, 2009, in this newsgroup, I conjectured an upper bound for the inradius r of the smallest square into which N unit circles could be packed. Recast in terms of the side length s, my conjectured upper bound is (#) s <= (c1 + sqrt(4 sqrt(3) N (9 + 4 sqrt(2)) + c2))/(4 + sqrt(2)) where constants c1 = 5 + 3 sqrt(2) - 2 sqrt(3) and c2 = 55 + 30 sqrt(2) - 52 sqrt(3) - 20 sqrt(6). At that time, Packomania gave packings continuously up to N = 300. Of those packings, only N = 251, 253, 257 and 258 violated (#). In the meantime, although I did look for packings for those four N values which would satisfy (#), I didn't consider finding such packings to be a high priority because I felt confident that such packings would eventually be found. However, I did happen to find packings for N = 253 and 258 which satisfied (#) but hadn't gotten around to posting them here yet. But anyway, the above link now shows that Critticall has found packings for N = 257 and 258 which satisfy (#), and its packing for N = 258 is better than mine. Below, I now give my packing for N = 253, and so that leaves N = 251 as the only case for N <= 300 for which a packing satisfying (#) has yet to be found. ------------------------------------ N = 253 s = 30.59239739099812868316... 669 contacts <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs253sq.gif> According to (#), we needed to have s <= 30.6476... But the best packing previously known had side length s = 30.6534... and 637 contacts. ------------------------------------ Packomania has also been extended in the meantime, now giving packings continuously up to N = 420. The only packings there for 300 < N <= 420 which do not satisfy (#) are N = 354, 355, 390, 391, 392 and 420. Of course I would be particularly interested to see if Critticall (or some other program or person) could find packings for N = 251, 354, 355, 390, 391, 392 and 420 which satisfy (#). [In the interest of "full disclosure", perhaps I should note that I actually already have packings which satisfy (#) for a few of those N. But none of those packings are optimized yet. As an example, for N = 390, according to (#), we should have s <= 37.803... The packing currently shown at Packomania has s = 37.818... My figure <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs390sq.gif> has s = 37.738, using three large hexagonal lattice groupings.] Recently, responding here to Christian Bau, I said that > Only a few days ago did I finally get a copy of _New Approaches to Circle > Packing in a Square_, P.G. Szabo et al. (Springer, 2007). Once I've had a > chance to digest certain parts of it, I'll be making comments about it in > this thread. Well, it happens that they give some proven bounds. I will be quite interested to see how those relate to my conjectured bounds. I hope to post a comparison here soon! Best regards, David W. Cantrell
From: ThomasCR on 29 Apr 2010 10:06 Hi David! Yes I am associateed with that site, as Nevenka Kristan is also. Check www.algit.eu also. In 24 hours you will see the new (better) result for the 251 circles in a square. We will let it calculate some more, despite the fact, that we already have a new result. Best regards, Tomaž Kristan (hum ... I have ThomasCR Google account but also much better Thomas Google account but I have to retrieve the password somehow ... never mind ...)
From: ThomasCR on 30 Apr 2010 11:34 The result of 251 circles is up. http://critticall.com/SQU_cir.html at the bottom. Check it out. Besides, you can download, install and run the software Packntile.exe. Every (new best) result is scrambled, but we can unscramble it, if you send it to my mail. We will publish it along with your name. Another option is, if you register the version. This way you can IMPROVE any old result further. In any case, the tool is powerful. Best regards, Thomas
From: David W. Cantrell on 1 May 2010 11:44 ThomasCR <protokol2020(a)gmail.com> wrote: > The result of 251 circles is up. > > <http://critticall.com/SQU_cir.html> > > at the bottom. > > Check it out. Congratulations! And many thanks! Now, for all N < 354, we know packings which obey my conjectured upper bound (#) s <= (c1 + sqrt(4 sqrt(3) N (9 + 4 sqrt(2)) + c2))/(4 + sqrt(2)) where constants c1 = 5 + 3 sqrt(2) - 2 sqrt(3) and c2 = 55 + 30 sqrt(2) - 52 sqrt(3) - 20 sqrt(6). In a previous response to you, I said > Recently, responding here to Christian Bau, I said that >> Only a few days ago did I finally get a copy of _New Approaches >> to Circle Packing in a Square_, P.G. Szabo et al. (Springer, 2007). >> Once I've had a chance to digest certain parts of it, I'll be >> making comments about it in this thread. > > Well, it happens that they give some proven bounds. I will be quite > interested to see how those relate to my conjectured bounds. I hope > to post a comparison here soon! That comparison of bounds will be posted in a few days. However, since one of their bounds is based on certain families of packings, it makes sense to mention those families first, relating them to the two packing families, compression and shift, which I had discussed previously in this thread. This will probably appear here later today or tomorrow. Best regards, David W. Cantrell
From: David W. Cantrell on 2 May 2010 12:47
We discuss how the two families of packings, mentioned here earlier, are related to patterns discussed in _New Approaches to Circle Packing in a Square_. An existing conjecture concerning an infinite subfamily of optimal packings in the compression family is broadened, and another conjecture, perhaps new, concerning an infinite subfamily of optimal packings in the shift family is presented. (For readers' convenience, previous comments about the compression and shift families are copied below my signature.) ------------------------------------------------- In _New Approaches to Circle Packing in a Square_ (NACPS), P.G. Szabo et al. (Springer, 2007), several more packing families are discussed than the two I had mentioned here. Those two families interested me because they seemed to have the potential to contain infinitely many optimal packings. I had not considered other families because I assumed that each of them would contain only finitely many optimal packings. Although that assumption appears to be correct, I had not noticed that considering such families could still be useful in obtaining a bound for the packings. (Readers interested in specifics of those other families may refer to section 10.1, Finite pattern classes, pp. 113-130 in NACPS.) ------------------------------------------------- The Compression Family and a Broadened Conjecture The family of packings obtained by compressing a hexagonal lattice packing, as discussed here previously, includes some members of two pattern classes, PAT_1(k(k + 1)) and PAT(k^2 + floor(k/2)), discussed in section 10.1 of NACPS. But more significantly, the compression family is closely related to the discussion in their section 10.2, A conjectured infinite pattern class. Due to my lack of familiarity with the literature, it is hardly surprising that what I had presented here about the compression family is very similar to previously published work; see the 1999 paper <http://cms.math.ca/cmb/a149060> by Nurmela et al. They relate the packings in this family, much as I had done, to rational approximations of sqrt(3). And they conjecture that, by using every second convergent obtained from the continued fraction, we always obtain optimal packings. Significantly, they say that "From elementary Diophantine approximation theory it is known that a 'good approximation' to an irrational number is necessarily a partial fraction in the continued fraction expansion of this number..." Using denominators q through 100, for example, their procedure would yield four packings -- for N = 2, 12, 120 and 1512. But the compression family, as noted here previously, contains many more packings in that range which are optimal or presumably so. Since it seems a pity to exclude more packings than necessary from the conjectured subfamily of optimal packings, I propose that the "usefulness" of a fractional approximation be defined differently here, thereby allowing the conjecture to be broadened: For a given power r, if p'/q' is a previous used fractional approximation to sqrt(3), then p/q (not necessarily in lowest terms) will also be used if q^r |p/q - sqrt(3)| < q'^r |p'/q' - sqrt(3)| We now examine how this definition of usefulness of an approximation works, using various values of r, in relation to the compression family. A short program in Mathematica will be used for illustration. Since we are dealing with the compression family, only fractions which _under_estimate sqrt(3) are considered. [Notes: s denotes, as before in this thread, the side length of the smallest square into which N unit circles can be packed, while m denotes the maximal pairwise distance between N points in the unit square. And in Mathematica, the function N[.], which gives a numerical approximation, is not to be confused with N denoting the number of circles or points.] r = 2; Print[{"N", {p, q}, delta, m, s}]; delta = 1; Do[p = Floor[q Sqrt[3]]; d = q^r (Sqrt[3] - p/q); If[d < delta, delta = d; m = Sqrt[p^-2 + q^-2]; Print[{Ceiling[(p + 1)(q + 1)/2], {p, q}, N[delta], m, N[2(1 + 1/m)]}]], {q, 1, 100}] {N, {p, q}, delta, m, s } {2, {1, 1}, 0.732051, Sqrt[2], 3.41421} {12, {5, 3}, 0.588457, Sqrt[34]/15, 7.14496} {120, {19, 11}, 0.578148, Sqrt[482]/209, 21.0394} {1512, {71, 41}, 0.577408, Sqrt[6722]/2911, 73.0106} Notice above that, with power r = 2, our definition of usefulness gives exactly the fractional approximations to sqrt(3) and the associated packings given by the conjecture of Nurmela et al. If we decrease the power, now using r = 1, we get four more packings in the same range, all of which are again at least presumably optimal: N = 6, 52, 621 and 8281. Of course the power r may not be decreased with impunity. If we decrease it too much, we eventually get packings which are known to be suboptimal. The first case of this occurs when r is about -3.9 with the introduction of the compression packing for N = 407. [Although that packing is known to be suboptimal, it is interesting that its side length is only a mere 0.00047% larger than s = 2 (487 + 504 Sqrt[3] + 42 Sqrt[2797 + 168 Sqrt[3]])/193 for the presumably optimal packing for N = 407.] Conjecture 1: Using some power r <= 1, the packings generated by the above procedure will always be optimal. I do not feel comfortable guessing specifically the smallest possible power r which would generate only optimal packings. But it would be nice if we could use r = -5/3. This would give, using denominators q through 100 again, for example, fifteen compression packings, all at least conjecturally optimal: r = -5/3; Print[{"N", {p, q}, delta, m, s}]; delta = 1; Do[p = Floor[q Sqrt[3]]; d = q^r (Sqrt[3] - p/q); If[d < delta, delta = d; m = Sqrt[p^-2 + q^-2]; Print[{Ceiling[(p + 1)(q + 1)/2], {p, q}, N[delta], m, N[2(1 + 1/m)]}]], {q, 1, 100}] {N, {p, q}, delta, m, s } {2, {1, 1}, 0.732051, Sqrt[2], 3.41421} {6, {3, 2}, 0.0730914, Sqrt[13]/6, 5.32820} {12, {5, 3}, 0.0104778, Sqrt[34]/15, 7.14496} {27, {8, 5}, 0.00903215, Sqrt[89]/40, 10.48} {39, {10, 6}, 0.0033003, Sqrt[17/2]/15, 12.2899} {52, {12, 7}, 0.000693539, Sqrt[193]/84, 14.0929} {99, {17, 10}, 0.000690514, Sqrt[389]/170, 19.2387} {120, {19, 11}, 0.0000878211, Sqrt[482]/209, 21.0394} {304, {31, 18}, 0.0000795006, Sqrt[1285]/558, 33.1324} {449, {38, 22}, 0.0000276619, Sqrt[241/2]/209, 40.0788} {621, {45, 26}, 5.61637*10^-6, Sqrt[2701]/1170, 47.025} {1512, {71, 41}, 7.04598*10^-7, Sqrt[6722]/2911, 73.0106} {3978, {116, 67}, 6.40152*10^-7, Sqrt[17945]/7772, 118.035} {5935, {142, 82}, 2.21935*10^-7, Sqrt[3361/2]/2911, 144.021} {8281, {168, 97}, 4.49482*10^-8, Sqrt[37633]/16296, 170.007} Regrettably, the list above still omits the compression packings for N = 18, 161 and 188, all thought to be optimal, but r cannot be reduced enough to include those packings without also including other packings known to be suboptimal. In conclusion of this section, if our new Conjecture 1 is true, the infinite class of optimal packings conjectured by Nurmela et al. can be significantly broadened, including many more packings from the compression family. -------------------------------------------------------------- The Shift Family and an Infinite Conjecturally Optimal Subfamily The family of packings obtained by shifting rows in a hexagonal lattice packing, as discussed here previously, includes the four presumably optimal packings in the PAT_2(k(k + 1)) pattern class discussed in section 10.1 of NACPS. But the shift family and that pattern class are different; most members of the shift family do not have N = k(k + 1), as required for that pattern class. As noted here previously, just as for the compression family, not all members of the shift family are optimal packings. But we conjecture that it has an infinite subfamily in which all members are optimal. It will again be convenient to illustrate how members of such a subfamily can be generated using a short Mathematica program. Please recall that, for the shift family, we will always use fractions which _over_estimate sqrt(3) and which have _odd_ numerators. To obtain such fractions, we could simply use every fourth convergent from the continued fraction; doing so would give us a fairly "safe" conjecture. But then our procedure would fail to include many optimal or conjecturally optimal shift packings. Therefore, we shall define the usefulness of a fractional approximation just as we did when dealing with the compression family, providing flexibility by allowing us to choose the power r. If we choose r = 1, then the fractions used are just every fourth convergent. Using denominators q through 100, for example, the procedure generates just two packings: r = 1; Print[{"N", {p, q}, delta, m, s}]; delta = 1; Do[p = Ceiling[q Sqrt[3]]; d = q^r (p/q - Sqrt[3]); If[OddQ[p] && d < delta, delta = d; m = Simplify[(2(q(p - 1) - Sqrt[4(q^2 + 1)-(p - 1)^2]))/(q(p + 1)(p - 3))]; Print[{((p + 1)(q + 1))/2, {p, q}, N[delta], m, N[2(1 + 1/m)]}]], {q, 1, 100}] {N, {p, q}, delta, m, s } {20, {7, 4}, 0.0717968, (6 - Sqrt[2])/16, 8.97808} {2793, {97, 56}, 0.00515478, (384 - Sqrt[17])/18424, 98.9998} Continuing to use just denominators q through 100 in all of our examples: If we choose r = 0, the procedure generates five packings. If we choose r = -4, it generates ten packings. Conjecture 2: Using some power r < 0, packings generated by the above procedure will always be optimal. Just as for the compression packings, I do not feel comfortable guessing specifically the smallest possible power r which would generate only optimal packings. But it would be particularly nice if we could use a power at least as small as r = -5.966 approximately. This would give thirteen shift packings, all at least conjecturally optimal: r = -5.966; Print[{"N", {p, q}, delta, m, s}]; delta = 1; Do[p = Ceiling[q Sqrt[3]]; d = q^r (p/q - Sqrt[3]); If[OddQ[p] && d < delta, delta = d; m = Simplify[(2(q(p - 1) - Sqrt[4(q^2 + 1)-(p - 1)^2]))/(q(p + 1)(p - 3))]; Print[{((p + 1)(q + 1))/2, {p, q}, N[delta], m, N[2(1 + 1/m)]}]], {q, 1, 100}] {N, {p, q}, delta, m, s } {20, {7, 4}, 4.594*10^-6, (6 - Sqrt[2])/16, 8.97808} {30, {9, 5}, 4.593*10^-6, (20 - Sqrt[10])/75, 10.9086} {42, {11, 6}, 2.307*10^-6, (15 - Sqrt[3])/72, 12.8532} {56, {13, 7}, 1.136*10^-6, (42 - Sqrt[14])/245, 14.8077} {143, {21, 12}, 6.541*10^-9, (40 - Sqrt[5])/396, 22.9724} {340, {33, 19}, 1.126*10^-10, (304 - Sqrt[106])/4845, 34.99236} {672, {47, 27}, 2.509*10^-11, (621 - Sqrt[201])/14256, 48.9857} {1050, {59, 34}, 2.367*10^-12, (493 - Sqrt[79])/14280, 60.9946} {1591, {73, 42}, 1.25*10^-12, (1512 - Sqrt[469])/54390, 74.98988} {2150, {85, 49}, 2.18*10^-13, (2058 - Sqrt[638])/86387, 86.9956} {2793, {97, 56}, 3.422*10^-15, (384 - Sqrt[17])/18424, 98.9998} {4464, {123, 71}, 3.100*10^-15, (4331 - Sqrt[1321])/264120, 124.9994} {6525, {149, 86}, 1.459*10^-15, (6364 - Sqrt[1921])/470850, 150.9991} Remarkably, using r = -5.966 generates _all_ shift packings which are optimal or currently thought to be so. But of course r can not be decreased with impunity. If we tried to use, say, r = -7.2, the procedure would generate its first packing known to be suboptimal, the shift packing for N = 195. -------------------------------------------------- In a day or two, I expect to post a comparison between my previously conjectured bounds and the proven bounds given in NACPS. David W. Cantrell /////////////////////////////////////////////////////////////////// My previous comments about the compression and shift families of packings: -------------------------------------------------- > Several of the density records are given by packings which, in a sense, > are "regular". And in these cases, we can give precise expressions for > the side length s of the square. In "The packing of equal circles in a > square", Math. Mag. 43:1 (1970) pp. 24-30, Michael Goldberg mentions the > two most prominent families of regular packings. > One family is obtained from a hexagonal lattice by the "shift method", > exemplified by packings for N = 30 and 340. A glance at > <http://hydra.nat.uni-magdeburg.de/packing/csq/csq340.html> will make the > structure evident. There are also best known, but not density record, > packings in this family for N = 20, 42 and 143. And also N = 56. > Members of this family > are engendered by integer ratios which slightly overestimate sqrt(3) and > have odd numerators. Suppose that p/q is such an approximation. Then the > side length s of the square in which N = (p + 1)(q + 1)/2 unit circles > may be packed by the "shift method" is > s = (2 + q (q + p q + sqrt(4 q^2 + (3 - p)(1 + p))))/(1 + q^2) > Example: Since 9/5 is a bit larger than sqrt(3) and has an odd > numerator, by the "shift method", we can get a packing of > N = (9 + 1)(5 + 1)/2 = 30 unit circles in a square of side length > s = (126 + 5 sqrt(10))/13. > The other members of this family, N = 20, 42, 143 and 340, have the > associated fractions 7/4, 11/6, 21/12 and 33/19, resp. Note that the > fractions are not necessarily convergents of the continued fraction for > sqrt(3) and are not necessarily in lowest terms. > Another family is obtained from a hexagonal lattice by "compression", > exemplified by packings for N = 39, 52, 99, 120, 188 and 304. A glance at > <http://hydra.nat.uni-magdeburg.de/packing/csq/csq188.html> will make the > structure evident. Members of this family are engendered by integer > ratios which slightly underestimate sqrt(3). Suppose that p/q is such an > approximation. Then the side length s of the square in which N unit > circles may be packed by "compression" is > s = 2 ( 1 + p / sqrt(1 + (p/q)^2) ) > where, > if p or q is odd, N = (p + 1)(q + 1)/2 > if p and q are both even, N = ((p + 1)(q + 1) + 1)/2. > Example: Since 24/14 is a bit smaller than sqrt(3), by "compression", we > can get a packing of N = ((24 + 1)(14 + 1) + 1)/2 = 188 unit circles in > a square of side length s = 2 + 336/sqrt(193). > The other members of this family, N = 39, 52, 99, 120 and 304, have the > associated fractions 10/6, 12/7, 17/10, 19/11 and 31/18, resp. And there are other members for smaller N; see program output below. > [I do not know if the general formulae above have appeared in the > literature, but they are not given by Goldberg.] Each line of output has the form {N, s}, where N is the number of unit circles packed in a square of side length s. If a packing for N is known which is better than the packing obtained by the shift or compression method, I have added # at the beginning of the appropriate line. (For N > 420, I have no information about better packings.) -------------------------------------- Shift method: Do[p = Ceiling[q*Sqrt[3]]; If[OddQ[p], Print[{((p + 1)*(q + 1))/2, (2 + q*(q + p*q + Sqrt[4*q^2 + (3 - p)*(1 + p)]))/(1 + q^2)}]], {q, 1, 33}] {20, (1/17)*(2 + 4*(32 + 4*Sqrt[2]))} {30, (1/26)*(2 + 5*(50 + 2*Sqrt[10]))} {42, (1/37)*(2 + 6*(72 + 4*Sqrt[3]))} {56, (1/50)*(2 + 7*(98 + 2*Sqrt[14]))} {143, (1/145)*(2 + 12*(264 + 6*Sqrt[5]))} # {168, 424/17} # {195, (1/197)*(2 + 14*(364 + 2*Sqrt[53]))} {340, (1/362)*(2 + 19*(646 + 2*Sqrt[106]))} # {378, (1/401)*(2 + 20*(720 + 8*Sqrt[7]))} # {418, (1/442)*(2 + 21*(798 + 2*Sqrt[118]))} {460, (1/485)*(2 + 22*(880 + 4*Sqrt[31]))} {672, (1/730)*(2 + 27*(1296 + 2*Sqrt[201]))} {725, (1/785)*(2 + 28*(1400 + 2*Sqrt[209]))} {780, (1/842)*(2 + 29*(1508 + 2*Sqrt[217]))} -------------------------------------- Compression method: Do[p = Floor[q*Sqrt[3]]; Print[{Ceiling[((p + 1)*(q + 1))/2], 2 + (2*p*q)/Sqrt[p^2 + q^2]}], {q, 1, 33}] {2, 2 + Sqrt[2]} {6, 2 + 12/Sqrt[13]} {12, 2 + 15*Sqrt[2/17]} {18, 2 + 24/Sqrt[13]} {27, 2 + 80/Sqrt[89]} {39, 2 + 30*Sqrt[2/17]} {52, 2 + 168/Sqrt[193]} # {63, 2 + 208/Sqrt[233]} # {80, 2 + 45*Sqrt[2/17]} {99, 2 + 340/Sqrt[389]} {120, 2 + 209*Sqrt[2/241]} # {137, 2 + 60*Sqrt[2/17]} {161, 2 + 572/Sqrt[653]} {188, 2 + 336/Sqrt[193]} # {208, 2 + 75*Sqrt[2/17]} # {238, 2 + 864/Sqrt[985]} # {270, 2 + 493*Sqrt[2/565]} {304, 2 + 1116/Sqrt[1285]} # {330, 2 + 1216/Sqrt[1385]} # {368, 2 + 680/Sqrt[389]} # {407, 2 + 504/Sqrt[193]} {449, 2 + 418*Sqrt[2/241]} {480, 2 + (897*Sqrt[2/41])/5} {525, 2 + 1968/Sqrt[2257]} {572, 2 + 1075*Sqrt[2/1237]} {621, 2 + 2340/Sqrt[2701]} {658, 2 + 2484/Sqrt[2845]} {711, 2 + 672/Sqrt[193]} {765, 2 + 2900/Sqrt[3341]} {806, 2 + 1020/Sqrt[389]} {864, 2 + 1643*Sqrt[2/1885]} {924, 2 + 3520/Sqrt[4049]} {986, 2 + 627*Sqrt[2/241]} -------------------------------------- |