-- 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 3 Jun 2010 00:40 The grid family of packings is generalized and improved by using rhombic hexagonal-lattice groups of unit circles. The two most recent posts here dealt with the specific case when p/q = 5/3 is the associated fraction underestimating sqrt(3); we now deal with general p/q. ------------------------------------------------------------------------- Grid packings are associated with fractions p/q which underestimate sqrt(3). [For example, in the grid packing for n = 39 <http://hydra.nat.uni-magdeburg.de/packing/csq/csq39.html>, the distance between the centers of the unit circles in the lower left and lower right corners is slightly less than 6 sqrt(3) and thus q = 6, while the distance between the centers of the unit circles in the lower left and upper left corners is slightly more than 10 and thus p = 10. That packing's associated fractional underestimate for sqrt(3) is then p/q = 10/6 = 5/3.] But grid packings can often be improved by forming rhombic hexagonal-lattice groups. Examples include n = 137 (p = 20, q = 12) <http://hydra.nat.uni-magdeburg.de/packing/csq/csq137.html> and n = 208 (p = 25, q = 15) <http://hydra.nat.uni-magdeburg.de/packing/csq/csq208.html>. These are actually slightly different types of packings. In the latter, there are rhombic groups containing 25 unit circles. (And of course, those groups are cut into halves at the sides of the square, and into fourths at two corners.) In the former, in addition to rhombic groups containing 9 unit circles (shown in orange), there are "diagonal single-file buffers" (in yellow) between those groups. Despite the difference between these two types of packings, we can conveniently provide a unified treatment for all such packings. They form a family which, for want of a better name, will be called, at least temporarily, the rhombic family of packings of unit circles in squares. (Suggestions for better names are welcome.) Most important things about the family can be encapsulated in a short program, in Mathematica, which generates the necessary data for members of the family. [The program should be mostly self-explanatory. But anyway... It begins with the list of rhombic packings being empty. GCD means greatest common divisor. n is the number of unit circles packed; d depends upon whether index j is even or odd; r is to be used as a radicand; x and y are coordinates of a point, to be explained later; and s is the precise side length of the square. The condition n <= 10^4 is merely due to the fact that no packings beyond n = 10^4 are currently shown at Packomania; the two following conditions make sure that the packing is valid. When those conditions are passed, the list of packings is appended with data for the packing: {n, {p, q}, j, s approx. to 32 decimal places, {x, y} approx. similarly}. The denominatorial index q goes up to 120 (and correspondingly, index j to 120/q) in order to get rhombic packings up to n = 10^4.] | listRhombic = {}; | Do[ | p = Floor[q*Sqrt[3]]; | If[GCD[p, q] == 1, | Do[ | n = Ceiling[(1/2)*(1 + j*p)*(1 + j*q)]; d = (3 + (-1)^j)/2; | m = (j - d)/2; r = d^2*(p^2 + q^2) - m^2*(p - Sqrt[3]*q)^2; | x = 1 + ((3 - d)/(p^2 + q^2))*(m*q*(p - Sqrt[3]*q) + p*Sqrt[r]); | y = 1 + (d - 1)*m + (((3 - d)*q)/(p^2 + q^2))*(m*(Sqrt[3]*p + q) + Sqrt[r]); | s = 2 + ((2*p*q)/(p^2 + q^2))*(m*(Sqrt[3]*p + q) + Sqrt[r]); | If[n <= 10^4 && FullSimplify[r] >= 0 && FullSimplify[x] >= 2, | listRhombic = Append[listRhombic, {n, {p, q}, j, N[s, 32], N[{x, y}, 32]}]], | {j, 1, 120/q}]], | {q, 1, 120}] An example item from listRhombic, giving a new packing for n = 407, is {407, {12, 7}, 3, 38.277987109269550230616036940070, {2.7184679719007525887473983084269, 4.0231655924391291858846697450059}} See the packing at <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs407sq.gif>. ------------------------------------------------------------------------- The point {x, y}: Each of these packings has a right-triangular hexagonal-lattice group of circles near the square's lower right corner, which is taken to be the origin of our coordinate system. The point {x, y} is the center of the only circle outside that group which is tangent to the uppermost circle of the group. [For example, in the figure above for n = 407, the right-triangular group consists of circles #1, 2, 26 and 50, of which #2 is the uppermost; {x, y} is the center of circle #20, the only circle, outside the group, which is tangent to #2. For another example, now using the type of packing with "diagonal single-file buffers", in the contact diagram for the packing for n = 137 at <http://hydra.nat.uni-magdeburg.de/packing/csq/csq137.html>, {x, y} is the center of circle #21.] For any rhombic packing, just knowing {x, y} and using a little thought, all coordinates of unit circle centers can be obtained by adding integers and integer multiples of sqrt(3), x and y. ------------------------------------------------------------------------- listRhombic, generated by the Mathematica program as shown above (for n <= 10^4), consists of 225 packings. Several of those were known prior to this thread, but 111 of those packings are improvements over packings currently shown at Packomania. A list of those 111 packings is given below my signature, each item shows n, {p, q} and then the amount of reduction in side length. (1) For some, the improvement may seem quite large. As an extreme example, {7130, {22, 13}, 3.786078123540279861959129122}, meaning that the rhombic packing for n = 7130 has a side length which is smaller by 3.786... than that of the grid packing now shown at Packomania. That might seem exciting at first glance. But 22/13 is not a good approximation to sqrt(3), and so that rhombic packing is almost certainly not optimal, despite its large improvement over the grid packing. (2) On the other hand, for some, the improvement is small. As an extreme example, {9503, {45, 26}, 0.0000092541165770106766076}, but this might well be an optimal packing since 45/26 is a fairly good approximation to sqrt(3). ------------------------------------------------------------------------- The program which produced listRhombic was designed to generate, for each denominator q, only the "best" packing in the rhombic family. And that means that the program, as shown above, does not generate all members of the family. But there are times when it may be desirable to generate all members. To do so, only two small changes are needed: (1) Remove the condition that GCD[p, q] be 1. (2) Allow p to take values smaller than Floor[q*Sqrt[3]] also. Example: It was claimed that the rhombic family generalizes the grid family. That means that every grid packing must also be a rhombic packing. Now consider that, for the grid packing for n = 513, we must use p = 40, q = 24. But since 40/24 is not in lowest terms, we must remove the condition that GCD[p, q] == 1 if we want our program to generate that grid packing. And that is not enough. For q = 24, taking p = 41 gives the best underestimate to sqrt(3). But since we need p = 40, we must also allow p to be smaller than Floor[q*Sqrt[3]]. ------------------------------------------------------------------------- Examining the entire rhombic family, one finds that, for certain n, there are several different packings. In most such cases, just one of those is the best. But there are cases in which there is a tie for best rhombic packing. For example, the rhombic family contains two different packings for n = 1570 having the same side length s, approx. 74.555974218539100461232073880141. One of those packings can be obtained by putting together four copies of the rhombic packing for n = 407, mentioned above. The other, which uses larger rhombi and "diagonal single-file buffers", is shown at <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs1570sq-1.gif>. ------------------------------------------------------------------------- In this post, only two new links to figures of rhombic packings have been given. But all rhombic packings look like one or the other of those. (For anyone who wants to see more, from my two previous posts, here are four rhombic packings, with p/q = 5/3: <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs513sq.gif> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs1527sq.gif> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs644sq.gif> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs952sq.gif>) ------------------------------------------------------------------------- Conjecture: The rhombic family contains infinitely many optimal packings. David W. Cantrell ------------------------------------------------------------------------- Each item in the following list of 111 rhombic packings has the form {n, {p, q}, reduction in side length compared to the best packing previously known}: {407, {12, 7}, 0.000545048395698306462480650} {513, {5, 3}, 0.017475383484262134278915633} {644, {5, 3}, 0.029672443220312005037587602} {760, {8, 5}, 0.062361699110191562375034023} {806, {17, 10}, 0.003414406603371245068536665} {952, {5, 3}, 0.046636422191274840015519836} {986, {19, 11}, 0.000061379181472810074885877} {1026, {8, 5}, 0.220181400689181945733126656} {1098, {12, 7}, 0.002422549549526739390711319} {1129, {5, 3}, 0.043731898908956810388646687} {1320, {5, 3}, 0.114624009802070141725961989} {1333, {8, 5}, 0.124877163155133850151485227} {1340, {22, 13}, 0.006863273882455117402937806} {1353, {13, 8}, 0.107509187720911575000875242} {1415, {17, 10}, 0.002276195921762579408120937} {1527, {5, 3}, 0.061268260510775002098516259} {1570, {12, 7}, 0.001453456929308577628068179} {1679, {8, 5}, 0.380617581532579893052527493} {1733, {19, 11}, 0.000054559218676591001605132} {1748, {5, 3}, 0.154868796298946135519826558} {1936, {13, 8}, 0.064377958568124346276936050} {1985, {5, 3}, 0.081761011723482687662960030} {2009, {27, 16}, 0.010651574272658028263945232} {2066, {8, 5}, 0.208515763419859278293258957} {2125, {12, 7}, 0.005087812838741301682528721} {2193, {17, 10}, 0.011383234916991263487239361} {2236, {5, 3}, 0.201458433991029658324286017} {2288, {29, 17}, 0.003852909167358042219000139} {2359, {22, 13}, 0.004575282078245002351111992} {2492, {8, 5}, 0.588088387968483818356870100} {2503, {5, 3}, 0.105226711735288854026552788} {2585, {31, 18}, 0.000568721683174820586635047} {2622, {13, 8}, 0.226582862058285371314002505} {2688, {19, 11}, 0.000272797265982613760494485} {2765, {12, 7}, 0.002906972094917553916618181} {2784, {5, 3}, 0.254568122508456496529281367} {2813, {32, 19}, 0.014620540093911700645565031} {2959, {8, 5}, 0.313555482920121484159228392} {3081, {5, 3}, 0.131684660276137665921961245} {3142, {17, 10}, 0.006828813206742490137073332} {3392, {5, 3}, 0.314406389485183267495005106} {3413, {13, 8}, 0.128857681548125967974049642} {3465, {8, 5}, 0.846206393866013858655120124} {3488, {12, 7}, 0.008723101439791132144487271} {3543, {27, 16}, 0.007100591536195495291178651} {3663, {22, 13}, 0.022883429999302540280360157} {3719, {5, 3}, 0.161156984127403072253049795} {3853, {19, 11}, 0.000163677773288730813706897} {4012, {8, 5}, 0.440362801378363891466253312} {4037, {29, 17}, 0.002568549875321790227209016} {4060, {5, 3}, 0.381219788690069588414973231} {4130, {39, 23}, 0.010160301319105200018494441} {4260, {17, 10}, 0.023911905376056099589503064} {4296, {12, 7}, 0.004845099099053478781422636} {4307, {13, 8}, 0.390480964667547627047649969} {4417, {5, 3}, 0.193668737817765802623441217} {4526, {41, 24}, 0.004460258893261527330190829} {4563, {31, 18}, 0.000379146634407776061483360} {4788, {5, 3}, 0.455298857098593984171464093} {4940, {43, 25}, 0.001189365915051788657621745} {4967, {32, 19}, 0.009746299719222121742055505} {5175, {5, 3}, 0.229248019604140283451923979} {5187, {12, 7}, 0.013329232685846621843073119} {5225, {8, 5}, 0.589400062769716565164691997} {5226, {19, 11}, 0.000572877952340622301131414} {5254, {22, 13}, 0.013726547764910234805875615} {5306, {13, 8}, 0.215018375441823150001750480} {5372, {45, 26}, 0.000013881175578775776311042} {5508, {27, 16}, 0.035516707693831445626480639} {5549, {17, 10}, 0.013658528402647138726281180} {5576, {5, 3}, 0.536985706262922605666796173} {5699, {46, 27}, 0.007192024117514228831628431} {5993, {5, 3}, 0.267926104032679517081104481} {6163, {12, 7}, 0.007267939908855120178893227} {6278, {29, 17}, 0.012844436907527138767853171} {6364, {147, 85}, 2.433600812282536814503039434} {6408, {13, 8}, 0.600778217676580214505342054} {6424, {5, 3}, 0.626683773591682855650603337} {6598, {8, 5}, 0.761235163065159786105054980} {6644, {50, 29}, 0.000593076349777420762818170} {6809, {19, 11}, 0.000327356015615813013070433} {6871, {5, 3}, 0.309737592597892271039653116} {6975, {154, 89}, 2.446297895357108412913461673} {7007, {17, 10}, 0.041009475970243853661217332} {7098, {31, 18}, 0.001895767804567362905121889} {7130, {22, 13}, 3.786078123540279861959129122} {7222, {12, 7}, 0.018907259121750145205533419} {7268, {157, 91}, 2.432881189729809200184409355} {7301, {39, 23}, 0.006773244703595670041763694} {7520, {53, 31}, 0.005121699482653326427642309} {7615, {13, 8}, 0.323041873039045984543986475} {7728, {32, 19}, 0.048753328444974056912168739} {7809, {5, 3}, 0.354720584273350262587813774} {7906, {27, 16}, 0.021303148545316056527890465} {7920, {164, 95}, 2.444816795580871662839937352} {8003, {41, 24}, 0.002973452566619792308921979} {8051, {55, 32}, 0.001856273147509600673034783} {8131, {8, 5}, 0.956554057551702355505395052} {8366, {12, 7}, 0.010175625677482603365057437} {8600, {19, 11}, 0.000982085636530362061381338} {8636, {17, 10}, 0.022766469833982526974478728} {8737, {43, 25}, 0.000792906973783655720936264} {8807, {5, 3}, 0.402916867982059316648572037} {8925, {13, 8}, 0.859639457228574451467913101} {8925, {174, 101}, 2.443500088223450248384694127} {9013, {29, 17}, 0.007705818334716084438000283} {9293, {22, 13}, 0.027455902726620954230196597} {9503, {45, 26}, 0.0000092541165770106766076} {9593, {12, 7}, 0.025458469776477833441886157} {9824, {8, 5}, 1.176176775936967636713740200} {9865, {5, 3}, 0.454372139416441330455322243}
From: David W. Cantrell on 10 Jun 2010 06:40 A few comments have been added to the discussion of the rhombic family. David W. Cantrell <DWCantrell(a)sigmaxi.net> wrote: > The grid family of packings is generalized and improved by using rhombic > hexagonal-lattice groups of unit circles. The two most recent posts > here dealt with the specific case when p/q = 5/3 is the associated > fraction underestimating sqrt(3); we now deal with general p/q. > > ------------------------------------------------------------------------- > > Grid packings are associated with fractions p/q which underestimate > sqrt(3). [For example, in the grid packing for n = 39 > <http://hydra.nat.uni-magdeburg.de/packing/csq/csq39.html>, the > distance between the centers of the unit circles in the lower left and > lower right corners is slightly less than 6 sqrt(3) and thus q = 6, while > the distance between the centers of the unit circles in the lower left > and upper left corners is slightly more than 10 and thus p = 10. That > packing's associated fractional underestimate for sqrt(3) is then > p/q = 10/6 = 5/3.] > > But grid packings can often be improved by forming rhombic > hexagonal-lattice groups. Examples include > n = 137 (p = 20, q = 12) > <http://hydra.nat.uni-magdeburg.de/packing/csq/csq137.html> and > n = 208 (p = 25, q = 15) > <http://hydra.nat.uni-magdeburg.de/packing/csq/csq208.html>. > These are actually slightly different types of packings. In the latter, > there are rhombic groups containing 25 unit circles. (And of course, > those groups are cut into halves at the sides of the square, and into > fourths at two corners.) In the former, in addition to rhombic groups > containing 9 unit circles (shown in orange), there are "diagonal > single-file buffers" (in yellow) between those groups. Despite the > difference between these two types of packings, we can conveniently > provide a unified treatment for all such packings. They form a family > which, for want of a better name, will be called, at least temporarily, > > the rhombic family > > of packings of unit circles in squares. (Suggestions for better > names are welcome.) > > Most important things about the family can be encapsulated in a short > program, in Mathematica, which generates the necessary data for members > of the family. [The program should be mostly self-explanatory. But > anyway... It begins with the list of rhombic packings being empty. > GCD means greatest common divisor. n is the number of unit circles > packed; d depends upon whether index j is even or odd; Whether the factor j is even or odd determines, respectively, whether the packing does or does not have "single-file buffers" between its rhombic groups. > r is to be used as a radicand; x and y are coordinates of a point, to be > explained later; and s is the precise side length of the square. The > condition n <= 10^4 is merely due to the fact that no packings beyond > n = 10^4 are currently shown at Packomania; the two following conditions > make sure that the packing is valid. When those conditions are passed, > the list of packings is appended with data for the packing: > {n, {p, q}, j, s approx. to 32 decimal places, {x, y} approx. similarly}. > The denominatorial index q goes up to 120 (and correspondingly, index j > to 120/q) in order to get rhombic packings up to n = 10^4.] > > | listRhombic = {}; > | Do[ > | p = Floor[q*Sqrt[3]]; > | If[GCD[p, q] == 1, > | Do[ > | n = Ceiling[(1/2)*(1 + j*p)*(1 + j*q)]; d = (3 + (-1)^j)/2; > | m = (j - d)/2; r = d^2*(p^2 + q^2) - m^2*(p - Sqrt[3]*q)^2; > | x = 1 + ((3 - d)/(p^2 + q^2))*(m*q*(p - Sqrt[3]*q) + p*Sqrt[r]); > | y = 1 + (d - 1)*m + (((3 - d)*q)/(p^2 + q^2))*(m*(Sqrt[3]*p + q) + Sqrt[r]); > | s = 2 + ((2*p*q)/(p^2 + q^2))*(m*(Sqrt[3]*p + q) + Sqrt[r]); > | If[n <= 10^4 && FullSimplify[r] >= 0 && FullSimplify[x] >= 2, > | listRhombic = Append[listRhombic, {n, {p, q}, j, N[s, 32], N[{x, y}, 32]}]], > | {j, 1, 120/q}]], > | {q, 1, 120}] > > An example item from listRhombic, giving a new packing for n = 407, is > > {407, {12, 7}, 3, 38.277987109269550230616036940070, > {2.7184679719007525887473983084269, 4.0231655924391291858846697450059}} > > See the packing at > <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs407sq.gif>. > > ------------------------------------------------------------------------- > > The point {x, y}: > > Each of these packings has a right-triangular hexagonal-lattice group of > circles near the square's lower right corner, which is taken to be the > origin of our coordinate system. The point {x, y} is the center of the > only circle outside that group which is tangent to the uppermost circle > of the group. [For example, in the figure above for n = 407, the > right-triangular group consists of circles #1, 2, 26 and 50, of which #2 > is the uppermost; {x, y} is the center of circle #20, the only circle, > outside the group, which is tangent to #2. For another example, now using > the type of packing with "diagonal single-file buffers", in the contact > diagram for the packing for n = 137 at > <http://hydra.nat.uni-magdeburg.de/packing/csq/csq137.html>, {x, y} > is the center of circle #21.] > > For any rhombic packing, just knowing {x, y} and using a little thought, > all coordinates of unit circle centers can be obtained by adding integers > and integer multiples of sqrt(3), x and y. > > ------------------------------------------------------------------------- > > listRhombic, generated by the Mathematica program as shown above (for > n <= 10^4), consists of 225 packings. Several of those were known prior > to this thread, but 111 of those packings are improvements over packings > currently shown at Packomania. A list of those 111 packings is given > below my signature, each item shows n, {p, q} and then the amount of > reduction in side length. The paragraph above is correct. However, after posting that list of 111 packings, I realized that many of those packings do not satisfy my conjectured upper bound for side length. A more selective list, now replacing the original list below my signature, consists of 40 rhombic packings which both (a) improved on packings which had been shown at Packomania and (b) satisfy my conjectured bound. > (1) For some, the improvement may seem quite large. As an extreme > example, {7130, {22, 13}, 3.786078123540279861959129122}, meaning that > the rhombic packing for n = 7130 has a side length which is smaller by > 3.786... than that of the grid packing now shown at Packomania. That > might seem exciting at first glance. But 22/13 is not a good > approximation to sqrt(3), and so that rhombic packing is almost > certainly not optimal, despite its large improvement over the grid > packing. (2) On the other hand, for some, the improvement is small. As > an extreme example, {9503, {45, 26}, 0.0000092541165770106766076}, but > this might well be an optimal packing since 45/26 is a fairly good > approximation to sqrt(3). > > ------------------------------------------------------------------------- > > The program which produced listRhombic was designed to generate, for each > denominator q, only the "best" packing in the rhombic family. And that > means that the program, as shown above, does not generate all members of > the family. But there are times when it may be desirable to generate all > members. To do so, only two small changes are needed: > (1) Remove the condition that GCD[p, q] be 1. > (2) Allow p to take values smaller than Floor[q*Sqrt[3]] also. > > Example: It was claimed that the rhombic family generalizes the grid > family. That means that every grid packing must also be a rhombic > packing. Now consider that, for the grid packing for n = 513, we must > use p = 40, q = 24. But since 40/24 is not in lowest terms, we must > remove the condition that GCD[p, q] == 1 if we want our program to > generate that grid packing. And that is not enough. For q = 24, taking > p = 41 gives the best underestimate to sqrt(3). But since we need p = > 40, we must also allow p to be smaller than Floor[q*Sqrt[3]]. > > ------------------------------------------------------------------------- > > Examining the entire rhombic family, one finds that, for certain n, there > are several different packings. In most such cases, just one of those is > the best. But there are cases in which there is a tie for best rhombic > packing. For example, the rhombic family contains two different packings > for n = 1570 having the same side length s, approx. > 74.555974218539100461232073880141. One of those packings can be obtained > by putting together four copies of the rhombic packing for n = 407, > mentioned above. The other, which uses larger rhombi and "diagonal > single-file buffers", is shown at <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs1570sq-1.gif>. To explain more fully, we reconsider this example. Removing the condition GCD[p, q] == 1 from the program, we see that four lines are printed for rhombic packings with n = 1570. From those lines, we get {p, q}, j and side length s as shown below: {12, 7}, 6, 74.555974218539100461232073880141; {24, 14}, 3, 74.555974218539100461232073880141; {36, 21}, 2, 74.557427675468409038860142058843; {72, 42}, 1, 74.557427675468409038860142058843. The last two lines actually give the same packing. It is the grid packing, which is suboptimal. In general, whenever j is 1 or 2, the rhombic packing degenerates to the grid packing (because the "rhombic group" then consists of just one unit circle). The first two lines give the distinct equally-good packings discussed in my original post. For j = 6, since j is even, we get a packing with "single-file buffers", shown at the above link. For j = 3, since j is odd, we get a packing without such "single-file buffers" between the rhombi. ------------------------------------------------------------------------- A triviality As noted above, when j = 1 or 2, the rhombic packing degenerates to the grid packing. But there is an even more degenerate case; it was not included in our program: If we allow j = 0, then we always get the packing of one unit circle in a square of side length s = 2. Therefore, that simple packing may also be considered to be in the rhombic family. ------------------------------------------------------------------------- > Conjecture: The rhombic family contains infinitely many optimal packings. David W. Cantrell ------------------------------------------------------------------------- Each item in the following list of 40 rhombic packings has the form {n, {p, q}, j, {reduction in side length s compared to the best packing previously known, difference between my conjectured upper bound and s}}. All of these packings are now shown at Packomania: <http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html>. {407, {12, 7}, 3, {0.000545048396, 0.318881150}} {513, {5, 3}, 8, {0.0174753835, 0.0637335554}} {644, {5, 3}, 9, {0.0296724432, 0.0324574360}} {806, {17, 10}, 3, {0.00341440660, 0.181214950}} {986, {19, 11}, 3, {0.0000613791815, 0.380257040}} {1098, {12, 7}, 5, {0.00242254955, 0.266875223}} {1340, {22, 13}, 3, {0.00686327388, 0.0429240393}} {1415, {17, 10}, 4, {0.00227619592, 0.116855449}} {1570, {12, 7}, 6, {0.00145345693, 0.248819563}} {1733, {19, 11}, 4, {0.0000545592187, 0.381555514}} {2125, {12, 7}, 7, {0.00508781284, 0.211298197}} {2193, {17, 10}, 5, {0.0113832349, 0.0365843850}} {2288, {29, 17}, 3, {0.00385290917, 0.0952986481}} {2585, {31, 18}, 3, {0.000568721683, 0.292439762}} {2688, {19, 11}, 5, {0.000272797266, 0.359453621}} {2765, {12, 7}, 8, {0.00290697209, 0.188193057}} {3488, {12, 7}, 9, {0.00872310144, 0.155140786}} {3853, {19, 11}, 6, {0.000163677773, 0.355049489}} {4296, {12, 7}, 10, {0.00484509910, 0.128172167}} {4526, {41, 24}, 3, {0.00446025889, 0.00590880112}} {4563, {31, 18}, 4, {0.000379146634, 0.257095421}} {4940, {43, 25}, 3, {0.00118936592, 0.202347361}} {5187, {12, 7}, 11, {0.0133292327, 0.0992409882}} {5226, {19, 11}, 7, {0.000572877952, 0.335795355}} {5372, {45, 26}, 3, {0.0000138811756, 0.402520243}} {6163, {12, 7}, 12, {0.00726793991, 0.0686970574}} {6364, {147, 85}, 1, {2.43360081, 0.371780083}} {6644, {50, 29}, 3, {0.000593076350, 0.256349133}} {6809, {19, 11}, 8, {0.000327356016, 0.328786912}} {6975, {154, 89}, 1, {2.44629790, 0.390030558}} {7098, {31, 18}, 5, {0.00189576780, 0.208875901}} {7222, {12, 7}, 13, {0.0189072591, 0.0439262264}} {7268, {157, 91}, 1, {2.43288119, 0.273932931}} {7920, {164, 95}, 1, {2.44481680, 0.292100797}} {8051, {55, 32}, 3, {0.00185627315, 0.111457438}} {8366, {12, 7}, 14, {0.0101756257, 0.00974189879}} {8600, {19, 11}, 9, {0.000982085637, 0.311242774}} {8737, {43, 25}, 4, {0.000792906974, 0.133412091}} {8925, {174, 101}, 1, {2.44350009, 0.194432862}} {9503, {45, 26}, 4, {9.25411658*10^-6, 0.400375622}}
From: David W. Cantrell on 13 Jun 2010 13:33 We discuss a family of packings which are hybrids of rhombic and columnar-shift packings. ------------------------------------------------------------------------ Terminological note: Packings previously called "shift" packings in this thread will henceforth, more descriptively, be called "columnar-shift" packings. ------------------------------------------------------------------------ Two important packing families, the rhombic and the columnar-shift, were developed earlier in this thread. Each of these families contains many highly dense packings and, conjecturally, infinitely many optimal packings. Some good packings can also be obtained by "hybridization" between those families, thereby giving a new family: (rhombic, columnar-shift) hybrids. It's helpful to look at an example of such a hybrid which is already known. Consider the packing for N = 87 shown at <http://hydra.nat.uni-magdeburg.de/packing/csq/csq87.html>. After a casual glance, one might think the following: At the right, there are three columns of unit circles, the middle column being shifted slightly above the other two. The other unit circles, to the left of those three columns, are arranged in a grid packing. But that description is not precisely correct. Each circle which looks as though it might be at the bottom of a column is actually slightly to the left of the circles above it. And the arrangement of the other circles only approximates a grid packing. As this example indicates, packings in the (rhombic, columnar-shift) hybrid family cannot be specified in a way which is both precise and simple. But we can specify, precisely and simply, an "archetype" hybrid packing which _approximates_ optimized packings. For n = 87, the archetype has three columns at the right, the circle at the top of the middle column touching the top of the square and circles at the bottoms of the other columns touching the bottom of the square. The other circles are grid-packed in a rectangle, the right side of which touches the circles in the leftmost of the three columns. The archetype approximates the optimized packing fairly well: Side length s for the optimized packing is 18.2831..., while side length s_a for the archetype is 18.2876... [A general algebraic expression for s_a, in terms of p and q for the rhombic part and n for the number of columns, could be given. But Mathematica's result for s_a is huge, occupying many pages. Perhaps there is liitle reason to be interested in a precise expression for s_a since it is, after all, itself just an approximation for s.] The (rhombic, columnar-shift) hybrid family is like a "structure class" as the term is used in _New Approaches to Circle Packing in a Square_, P.G. Szabo et al. (Springer, 2007). Their term "pattern class" describes a family of packings whose members are precisely characterized, in general. Then concerning "structure class", they say (p. 123) "The modified notation (from pattern class to structure class) is based on the argument that this time the coordinates of the optimal, and the best known packings are not given, just a well approximating structure is defined." Since the hybrid family's archetypal and optimized packings differ somewhat, we endeavor to present here all good packings in the family for N < 1000, putatively optimized. ---------------------------------------------------------------- ---------------------------------------------------------------- Rhombic + One Column Most good hybrid packings have just one column appended to a rhombic packing. And when there is just one column and the rhombic packing is just a grid packing, the algebraic expression for the side length s_a of the archetypal packing is simple. If p/q is the associated fractional overestimate for sqrt(3), then s_a = 2(1 + p (p + q sqrt(p^2 + q^2 - 1))/(p^2 + q^2)). N = 28 and 53: <http://hydra.nat.uni-magdeburg.de/packing/csq/csq28.html> and <http://hydra.nat.uni-magdeburg.de/packing/csq/csq53.html> These known packings are both approximated by a (non-grid) rhombic part plus one column. (Where are the rhombic groups? Well, there are no whole rhombi in these two packings. Rather, each has a half rhombus at the left and two quarter rhombi at top and bottom, next to the column.) N = 217: <http://hydra.nat.uni-magdeburg.de/packing/csq/csq217.html> This presumably optimized packing has s = 28.1872... It is approximated well by the archetype, having a grid part plus one column, with s_a = 28.1895... (Note the rattler in the upper left corner. Having a rattler in one of the corners is often seen in these hybrid packings.) N = 408: <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs408sq.gif> This new, presumably optimized packing has s = 38.46859362531026410351... Note that there are many (whole) rhombic groups, as well as several half rhombi and two quarter rhombi. The packing currently shown at Packomania has side length 38.4691... N = 493: <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs493sq.gif> This new, presumably optimized packing has s = 42.07935786113438806132... The packing currently shown at Packomania has side length 42.079357890..., while that of the archetype is s_a = 42.079757629... N = 659: <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs659sq.gif> This new, presumably optimized packing has s = 48.73889807193830467232... The packing currently shown at Packomania is the archetype, with s_a = 48.7769... N = 766: <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs766sq.gif> This new, presumably optimized packing has s = 52.36670958083337373750... The packing currently shown at Packomania is the archetype, with s_a = 52.3754... ---------------------------------------------------------------- ---------------------------------------------------------------- Rhombic + Two Columns N = 69: <http://hydra.nat.uni-magdeburg.de/packing/csq/csq69.html> This known packing has s = 16.2910... and is approximated well by the archetype, a grid part plus two columns, having s_a = 16.2959... N= 248: <http://hydra.nat.uni-magdeburg.de/packing/csq/csq248.html> This known packing has s = 30.18346610619051817070... The archetype has a (non-grid) rhombic part but, just like the packings for N = 28 and 53, no whole rhombic groups appear. N = 539: <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs539sq.gif> This new, presumably optimized packing has s = 44.07907689044332029600... For comparison, the archetype has s_a = 44.07947... ---------------------------------------------------------------- ---------------------------------------------------------------- Rhombic + Three Columns N = 87: <http://hydra.nat.uni-magdeburg.de/packing/csq/csq87.html>. This was the example discussed in the introduction. N = 281: <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs281sq.gif> This new, presumably optimized packing has s = 32.18078157808499508358... For comparison, the archetype has s_a = 32.18260... It is particularly interesting to compare the new packing with the one currently shown at Packomania, <http://hydra.nat.uni-magdeburg.de/packing/csq/csq281.html>, having side length 32.18222... It is reasonable to think of that former packing as also being in the hybrid family, even though its three columns are not next to each other. N = 587: <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/circs587sq.gif> This new, presumably optimized packing has s = 46.07863725422414128830... The archetype has a (non-grid) rhombic part but, just like the packings for N = 28, 53 and 248, no whole rhombic groups appear. ---------------------------------------------------------------- ---------------------------------------------------------------- Most good hybrid packings consist of a rhombic (often, just a grid) part with only a single appended column. As the number of appended columns increases, the packings tend to get worse. There may not be any good hybrid packings (having a nonempty rhombic part) with four or more appended columns. There might be infinitely many packings in the (rhombic, columnar-shift) hybrid family which are optimal. But hybrid packings are presumably never density records. All of the new hybrid packings above will be submitted to Packomania soon, and a few other good ones for 1000 < N < 10000 will be submitted in the next few days. David W. Cantrell
From: James Waldby on 13 Jun 2010 14:47 On Sun, 13 Jun 2010 17:33:22 +0000, David W. Cantrell wrote: > We discuss a family of packings which are hybrids of rhombic and > columnar-shift packings. .... > Terminological note: Packings previously called "shift" packings in this > thread will henceforth, more descriptively, be called "columnar-shift" > packings. .... > Two important packing families, the rhombic and the columnar-shift, were > developed earlier in this thread. Each of these families contains many > highly dense packings and, conjecturally, infinitely many optimal > packings. > > Some good packings can also be obtained by "hybridization" between those > families, thereby giving a new family: (rhombic, columnar-shift) hybrids. .... > As this example indicates, packings in the (rhombic, columnar-shift) .... > The (rhombic, columnar-shift) hybrid family is like a "structure class" > as the term is used in _New Approaches to Circle Packing in a Square_, .... Re terminology, "columnar-shift" grates badly each time I read it. I think "column-shift" would be better; it's adequately grammatically correct and expresses the same thing. > Most good hybrid packings consist of a rhombic (often, just a grid) part > with only a single appended column. As the number of appended columns > increases, the packings tend to get worse. There may not be any good > hybrid packings (having a nonempty rhombic part) with four or more > appended columns. 1. Can you make a sort of 'periodic table' that characterizes best- packing type vs index? Or at least a summary table? 2. Do you think that for all N > some large number, all optimal packings fall into specific families? Or will there be occasional singletons with patterns that fall into no previously-recognized family? > There might be infinitely many packings in the (rhombic, columnar-shift) > hybrid family which are optimal. But hybrid packings are presumably > never density records. .... When I first read that last sentence, it seemed intuitively correct, but after a little thought I don't see a reason why there shouldn't be an occasional exception. Is there an obvious reason? Do density record patterns have no (or quite few) rattlers? Do they always exhibit symmetry on several axes? -- jiw
From: David W. Cantrell on 14 Jun 2010 09:34
James Waldby <no(a)no.no> wrote: > On Sun, 13 Jun 2010 17:33:22 +0000, David W. Cantrell wrote: > > We discuss a family of packings which are hybrids of rhombic and > > columnar-shift packings. > ... > > Terminological note: Packings previously called "shift" packings in > > this thread will henceforth, more descriptively, be called > > "columnar-shift" packings. > ... > > Two important packing families, the rhombic and the columnar-shift, > > were developed earlier in this thread. Each of these families contains > > many highly dense packings and, conjecturally, infinitely many optimal > > packings. > > > > Some good packings can also be obtained by "hybridization" between > > those families, thereby giving a new family: (rhombic, columnar-shift) > > hybrids. > ... > > As this example indicates, packings in the (rhombic, columnar-shift) > ... > > The (rhombic, columnar-shift) hybrid family is like a "structure class" > > as the term is used in _New Approaches to Circle Packing in a Square_, > ... > > Re terminology, "columnar-shift" grates badly each time I read it. > I think "column-shift" would be better; it's adequately grammatically > correct and expresses the same thing. Thanks for that observation. I'll think about it, and will probably take your suggestion. > > Most good hybrid packings consist of a rhombic (often, just a grid) > > part with only a single appended column. As the number of appended > > columns increases, the packings tend to get worse. There may not be any > > good hybrid packings (having a nonempty rhombic part) with four or more > > appended columns. > > 1. Can you make a sort of 'periodic table' that characterizes best- > packing type vs index? Or at least a summary table? For those packings which do happen to fall into one of the recognized families, something like that could be done. But such packings are actually rather sparse. I do plan, however, to eventually give something like a 'periodic table' for the (even sparser) density record packings. > 2. Do you think that for all N > some large number, all optimal > packings fall into specific families? No. (Of course, one might get that incorrect impression by looking at the packings _currently_ shown at Packomania for 500 < N < 10000. But that's just because, when N is large, good packings are very difficult to find _unless_ there happens to be a recognized pattern for that N.) But perhaps if the number of recognized families were greatly increased and if membership in a family were rather loosely defined, then we could get much closer to answering "Yes" to your question. Browsing through the Overview section at Packomania might be useful. Look, for example, at <http://hydra.nat.uni-magdeburg.de/packing/csq/d35.html>, which shows packings for N = 409-420. The packings from N = 409 through 415 are alike in some sense. Should they all be in the same family? Maybe, but I'm not sure how that family should be defined or how useful it would be. But take a look at N = 418. It does fit a family which I recognize (but haven't mentioned before) and note that, between 415 and 418, there were two other packings. Now look at <http://hydra.nat.uni-magdeburg.de/packing/csq/d32.html>. Packings for N = 373-375 (as well as for N = 372, shown on the previous page) are of the same sort as 409-415, then there are two other packings, and N = 378 is in the same family as N = 418. Is that just coincidence? > Or will there be occasional > singletons with patterns that fall into no previously-recognized > family? Not just occasional singletons; rather, frequent groups (unless, as I said above, the number of recognized families were greatly increased and membership in a family were rather loosely defined). > > There might be infinitely many packings in the (rhombic, > > columnar-shift) hybrid family which are optimal. But hybrid packings > > are presumably never density records. > ... > > When I first read that last sentence, it seemed intuitively correct, > but after a little thought I don't see a reason why there shouldn't > be an occasional exception. Is there an obvious reason? Whether the reason is obvious depends on how much one has thought about such things. Having density greater than that for any smaller N is clearly a very stingent requirement. To achieve such density, the packing needs to be very close to a single hexagonal lattice. But in a (rhombic, column-shift) hybrid packing, assuming rhombic and columnar parts are both nonempty, the rhombic part and its nearby column will never be very close to being in a hexagonal lattice. Rather, that column and the circles which touch it from the rhombic part tend, more or less, to be in a _square_ lattice. > Do density record patterns have no (or quite few) rattlers? Good question. This is premature... but to help answer your question, let's look at part of the density record table: {N, density} family {407, 0.872662} rhombic {447, 0.874373} none? {448, 0.876254} none? {449, 0.878148} grid {572, 0.878581} grid and then look at <http://hydra.nat.uni-magdeburg.de/packing/csq/d38.html>. N = 449 is an excellent grid packing. Its density is so high that we can remove one or two circles from it, readjust the remaining circles somewhat, and we _still_ get density records for N = 448 and 447. (A la Reagan's "trickle-down" economics, this might be called trickle-down density.) The _current_ packings for N = 447 and 448 have very many rattlers. But that should be a temporary situation. I suspect that the optimal packings for those would have few rattlers. So to answer your question: It seems likely that density record packings, once optimized, should have few rattlers. (By the way, also notice at the above link that packings for N = 450-454 are of the same sort as previously mentioned for N = 372-375 and 409-415.) > Do they always exhibit symmetry on several axes? No. Best regards, David W. Cantrell |