-- 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: ThomasCR on 7 May 2010 02:51 I am glad that David's conjecture has been proven right to 353. We will put some computer effort now to 354, to include it, but may take a while to get the result. In fact, anybody can try with downloading and running the Packntile software from www.algit.eu - Regards Thomas
From: David W. Cantrell on 8 May 2010 10:03 Two weak conjectures are stated and then the compression and shift families of packings are expanded, after my response to Thomas. (One of the bound comparisons which I had promised should be posted in a day or two. Sorry for the delay.) ThomasCR <protokol2020(a)gmail.com> wrote: > I am glad that David's conjecture has been proven right to 353. We > will put some computer effort now to 354, to include it, but may > take a while to get the result. I look forward to your result! > In fact, anybody can try with downloading and running the Packntile > software from www.algit.eu Yes, it would be great to get more people involved. ------------------------------------------------------------------ Two weak conjectures In my most recent post about the compression and shift families of packings, I mentioned three conjectures -- one by Nurmela et al. and two by me. But I forgot to mention two significant conjectures which are much more likely to be true: 1. There are infinitely many optimal packings in the compression family. 2. There are infinitely many optimal packings in the shift family. These two conjectures are weaker because, unlike the three previously mentioned conjectures, they do not attempt to identify specific members of the families as being optimal. ------------------------------------------------------------------ Expanding the compression family of packings In _New Approaches to Circle Packing in a Square_ (NACPS), P.G. Szabo et al. (Springer, 2007), they use the term "grid packing" for the type of packing discussed in their section 10.2. They relate grid packings to fractional approximations of sqrt(3), much as I had done for compression packings. And yet, the program which I had originally presented here 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}] to generate compression packings does not generate the grid packing for N = 5, an optimal packing! Why the discrepancy? The explanation is easy. I was interested in generating compression packings which had a good chance of being optimal and hence, for each denominator q, I considered only p = floor(q sqrt(3)) as a possible numerator. After all, using any numerator p' < floor(q sqrt(3)) gives an approximation p'/q of sqrt(3) which is poorer than p/q. In particular, for q = 2, we have p = floor(2 sqrt(3)) = 3 and so we use 3/2 as an underestimate of sqrt(3), giving the compression packing for N = 6, which is optimal. But for q = 2, if we had _also_ used p = 2, then we would have had 2/2 as another underestimate of sqrt(3), and this approximation, poor though it is, happens to lead to the optimal packing for N = 5. This is a grid packing, and it should also be considered a compression packing. The grid and compression families should be identical. The compression family should not have been limited as my little program above seemed to imply. If we wish to generate _all_ members of the family, then for each denominator q, instead of using just p = floor(q sqrt(3)), we should use all integers p such that q <= p <= floor(q sqrt(3)). Below is a program revised so as to generate all members of the family, using denominators q through some maximum, qmax. For each member of the family, it prints the number N of unit circles, the numerator p and denominator q of the associated fraction which underestimates sqrt(3), and the side length s of the square: | Do[ | s = 2 + (2 p q)/Sqrt[p^2 + q^2]; | Print[{Ceiling[(p + 1)(q + 1)/2], {p, q}, s}], | {q, 1, qmax}, {p, q, Floor[q Sqrt[3]]}] Expanded in this way, the compression family has many more members. For comparison, if we choose to stop at qmax = 10, the program above generates 45 compression packings, whereas, if only p = floor(q sqrt(3)) had been used, only 10 packings would have been generated. In the expanded family, we have more than one packing for certain values of N. For example, the fractions 6/4 and 5/5 both generate compression packings for N = 18, the former being optimal, the latter not. And it appears that, in the expanded family, the _only optimal_ packing with p < floor(q sqrt(3)) is the packing for N = 5. Since the expansion has introduced many more packings to the family and yet only one of those is optimal, it may seem that the expansion has "watered down" the family. Nonetheless, it seems that expanding the compression family, so that it is identical to the family of grid packings, is the "correct" thing to do. (And of course, with hindsight, it's what I should have done initially.) ------------------------------------------------------------------ Expanding the shift family of packings Expansion of the shift family is very similar to expansion of the compression family. The shift family is generated by fractions which overestimate sqrt(3). For a given denominator q, instead of using just p = ceiling(q sqrt(3)) when p is odd, we should now use all odd numerators p such that ceiling(q sqrt(3)) <= p <= 2q + 1. Below is a program revised so as to generate all members of the family, using denominators q through qmax: | Do[ | If[OddQ[p], | s = (2 + q (q + p q + Sqrt[4 q^2 + (3 - p)(1 + p)]))/(1 + q^2); | Print[{(p + 1)(q + 1)/2, {p, q}, s}]], | {q, 1, qmax}, {p, Ceiling[q Sqrt[3]], 2 q + 1}] Expanded in this way, the shift family has many more members. For comparison, if we choose to stop at qmax = 10, the program above generates 17 shift packings, whereas, if only p = ceiling(q sqrt(3)) when p is odd had been used, only 4 packings would have been generated. In the expanded family, we have more than one packing for certain values of N. For example, the fractions 383/194 and 359/207 both generate shift packings for N = 37440, the latter perhaps being optimal. The shift family now includes the square lattice packings (called the PAT(k^2) pattern class in section 10.1 of NACPS). It appears that, in the expanding the family, perhaps the only newly introduced optimal packings are the square lattice packings for N = 4, 9, 16, 25 and 36. ------------------------------------------------------------------ David W. Cantrell
From: David W. Cantrell on 9 May 2010 10:06 A bound proven in NACPS is compared with a bound previously conjectured in this thread. ------------------------------------------------------------------ A Comparison of Two Bounds It is well known that the problem of packing N unit circles in a square of minimum side length s is equivalent to the problem of maximizing the minimum-pairwise-distance m between N >= 2 points in a unit square. Much of the literature deals with the latter problem. It's trivial to convert between the two problems using s = 2(1 + 1/m) and m = 2/(s - 2). Using the latter equation, the lower bound for s, previously conjectured in this thread to be valid except at N = 4 and 9, is now converted to an upper bound for m: m <= 4/(sqrt(2 sqrt(3) (4N - 3) + 4) - 1 - sqrt(3)) In _New Approaches to Circle Packing in a Square_ (NACPS), P.G. Szabo et al. (Springer, 2007), their Theorem 3.2 can be used to give an upper bound for m: m <= min(m1, m2) where m1 = (sqrt(2 (N - 1)/sqrt(3) + 1) + 1)/(N - 1) and m2 = 1/(sqrt(sqrt(3) N/2 + (2 - sqrt(3))(floor(sqrt(N)) - 1/2)) - 1) The figures at <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/ubcomp20.gif> (for N = 2..20) and <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/Sq/ubcomp185to345.gif> (for N = 185..345) show both upper bounds, together with distances m for configurations for N points in the unit square. The second figure makes particularly clear how much tighter my conjectured upper bound is than the proven bound from NACPS. Distances m in the first figure are based on configurations which have been proved optimal. But distances m in the second figure are based merely on the best configurations currently known; as such, it is, of course, conceivable that my conjectured upper bound could be disproven simply by finding a configuration which is so extraordinarily good that its m exceeds my conjectured bound. (Based on the current data at Packomania <http://hydra.nat.uni-magdeburg.de/packing/csq/>: For 9 < N <= 500, the smallest difference between my conjectured upper bound and m is 0.000036..., occuring at N = 449. And at N = 986 (the only configuration currently shown beyond 500) the difference is 0.000033...) Some may wonder why I was satisfied to conjecture a bound which is not valid at N = 4 and 9. The reason is that I wanted a bound which (1) was fairly tight for large N and (2) had a simple algebraic form. (More complicated and tighter bounds could be designed, no doubt.) To satisfy those two requirements. I thought it best to sacrifice validity at N = 4 and 9, preferring to think of those square lattice configurations as being too exceptional, "freakishly good". ------------------------------------------------------------------ I'm working on a similar comparison of lower bounds for m. That is much more complicated, but also much more interesting. It may be a week or two until that comparison is finished. David W. Cantrell
From: Phil Carmody on 10 May 2010 03:45 David W. Cantrell <DWCantrell(a)sigmaxi.net> writes: > A bound proven in NACPS is compared with a bound previously conjectured in I've heard of NAACP, but what's NACPS? National Association for Colored Peoples' Segregation? Phil -- I find the easiest thing to do is to k/f myself and just troll away -- David Melville on r.a.s.f1
From: David W. Cantrell on 10 May 2010 05:14
Phil Carmody <thefatphil_demunged(a)yahoo.co.uk> wrote: > David W. Cantrell <DWCantrell(a)sigmaxi.net> writes: > > A bound proven in NACPS is compared with a bound previously conjectured > > in > > I've heard of NAACP, but what's NACPS? National Association for > Colored Peoples' Segregation? I had used the abbreviation earlier in the thread. Furthermore, in the same post you responded to, I repeated what it stood for, right before I stated their bound: > > In _New Approaches to Circle Packing in a Square_ (NACPS), P.G. Szabo > > et al. (Springer, 2007), their Theorem 3.2 can be used to give an upper > > bound for m David |