-- Packing unit circles in circles: new results
David W. Cantrell
most classic of packing problems. This thread will present some new
packings, over the course of a month or so. At the end of the thread,
conjectured bounds for this packing problem will be given.
For previously known packings, see the appropriate section of Eckard
Specht's excellent Packomania:
<http://hydra.nat.uni-magdeburg.de/packing/cci/cci.html>.
(Note that, once he has shown my new packings at his site, the links
given below may become invalid.) In my figures, tangencies between
circles are indicated by a small normal segment, and unit circles are
color-coded according to their number of tangencies: red, 0; purple, 3;
green, 4; yellow, 5; orange, 6. (Also note that my radius r corresponds
with Specht's ratio, rather than his radius.)
------------------------------------
N = 144 : r = 13.250964369219..., symmetry group D_2
<http://img169.imageshack.us/img169/3156/circles144so5.gif>
The best packing previously known has r = 13.2538... and is not symmetric.
------------------------------------
N = 183 : r = 14.870824502675..., symmetry group C_3
<http://img169.imageshack.us/img169/9633/circles183rd1.gif>
The best packing previously known has r = 14.8750... and is not symmetric.
------------------------------------
N = 206 : r = 15.738543703311..., symmetry group D_2
<http://img169.imageshack.us/img169/9237/circles206ns9.gif>
The best packing previously known has r = 15.7439... and is not symmetric.
------------------------------------
N = 207 : r = 15.770271663575..., symmetry group D_3
<http://img167.imageshack.us/img167/3208/circles207mo1.gif>
The best packing previously known has r = 15.7817... and is not symmetric.
------------------------------------
David W. Cantrell
David W. Cantrell
This second post adds new packings for N = 219, 253 and 309.
See below. (Progress has been slow!)
N = 219 : r = 16.169155113016..., symmetry group D_3
<http://img229.imageshack.us/img229/5512/circles219wd0.gif>
The best packing previously known has r = 16.1922... and is not
symmetric.
------------------------------------
N = 253 : r = 17.345956322669..., symmetry group C_6
<http://img388.imageshack.us/img388/271/circles253cu1.gif>
The best packing previously known has r = 17.3464... and has
the same symmetry group as the new packing.
------------------------------------
N = 309 : r = 19.146749238541..., symmetry group D_3
<http://img82.imageshack.us/img82/7052/circles309mc0.gif>
The best packing previously known has r = 19.1658... and is not
symmetric.
------------------------------------
Note: Although the information given here and in the figures
completely determines the packings, I will supply the coordinates of
the centers, if requested. (For each packing, the coordinates of the
centers were obtained by solving a system of equations; therefore, it
was easy to calculate the coordinates with great accuracy.)
David W. Cantrell
David W. Cantrell
This third post adds new packings for N = 258, 276, 321, 339
and 401 - 403. See below.
> Packing N unit circles in a circle of smallest radius r is perhaps the
> most classic of packing problems. This thread will present some new
> packings, over the course of a month or so. At the end of the thread,
> conjectured bounds for this packing problem will be given.
>
> For previously known packings, see the appropriate section of Eckard
> Specht's excellent Packomania:
> <http://hydra.nat.uni-magdeburg.de/packing/cci/cci.html>.
> (Note that, once he has shown my new packings at his site, the links
> given below may become invalid.) In my figures, tangencies between
> circles are indicated by a small normal segment, and unit circles are
> color-coded according to their number of tangencies: red, 0; purple, 3;
> green, 4; yellow, 5; orange, 6. (Also note that my radius r corresponds
> with Specht's ratio, rather than his radius.)
>
N = 258 : r = 17.552744782035..., symmetry group D_3
<http://img525.imageshack.us/img525/7899/circles258re4.gif>
The best packing previously known has r = 17.5573... and is not
symmetric.
------------------------------------
N = 276 : r = 18.123058535144..., symmetry group D_3
<http://img525.imageshack.us/img525/4492/circles276ro7.gif>
The best packing previously known has r = 18.1300... and is not
symmetric.
------------------------------------
N = 321 : r = 19.492954740445..., symmetry group D_3
<http://img525.imageshack.us/img525/1258/circles321qv2.gif>
The best packing previously known has r = 19.4945... and has
the same symmetry group as the new packing.
------------------------------------
N = 339 : r = 20.029283859598..., symmetry group D_3
<http://img525.imageshack.us/img525/6167/circles339zc0.gif>
The best packing previously known has r = 20.0510... and is not
symmetric.
------------------------------------
N = 402 (and 401) : r = 21.734369994310..., symmetry group D_3
<http://img525.imageshack.us/img525/9610/circles402if0.gif>
The best packing previously known for N = 402 has r = 21.7678...
and has symmetry group D_1.
Furthermore, the best packing previously known for N = 401 has r =
21.7456... Consequently, by removing any unit circle from the new packing
for N = 402, we get an improved packing for N = 401. (Of course, I'm not
suggesting that such a packing for N = 401 might be optimal. After removing
some circle from the packing for N = 402, we should probably be able to
reduce the radius slightly.)
------------------------------------
N = 403 : r = 21.773164022089..., symmetry group D_6
<http://img525.imageshack.us/img525/1479/circles403uy6.gif>
The best packing previously known has r = 21.7758... and has
the same symmetry group as the new packing.
------------------------------------
David W. Cantrell
David W. Cantrell
This fourth post adds new packings for N = 262, 284 and 472.
Also, previously mentioned packings have been rearranged into
numerical order, preceding the newest packings.
N = 262 : r = 17.667596591484..., symmetry group D_1
<http://img516.imageshack.us/img516/2370/circles262ei2.gif>
The best packing previously known has r = 17.6763... and is not
symmetric.
------------------------------------
N = 284 : r = 18.361799569923..., symmetry group D_2
<http://img516.imageshack.us/img516/7875/circles284rh4.gif>
The best packing previously known has r = 18.3954... and is not
symmetric.
------------------------------------
N = 472 : r = 23.515455800214..., symmetry group D_2
<http://img377.imageshack.us/img377/4022/circles472ia5.gif>
The best packing previously known has r = 23.5338... and is not
symmetric.
------------------------------------
David W. Cantrell
amy666
i cant make much sense of it ...
you speak of colors like red and purple ?
but i dont see as many colors as you mention :
http://hydra.nat.uni-magdeburg.de/packing/cci/d42.html
what " conjectures " are you talking about ?
KEPLERS conjecture ???
conjectures about how many " purples " occur for a prime number of unit circles ?
looking for constants like pi/sqrt(n) ?
kissing numbers ?
and no , i dont accept " computer proofs ".
regards
tommy1729
David W. Cantrell
> David W. Cantrell wrote :
>
> > Packing N unit circles in a circle of smallest radius r is perhaps the
> > most classic of packing problems. This thread will present some new
> > packings, over the course of a month or so. At the end of the thread,
> > conjectured bounds for this packing problem will be given.
> >
> > For previously known packings, see the appropriate section of Eckard
> > Specht's excellent Packomania:
> > <http://hydra.nat.uni-magdeburg.de/packing/cci/cci.html>
My statement about colors concerned "my figures". Please look at any
of _my_ figures, using the ImageShack links provided above. (Although
I hadn't made any statement about the colors used in Packomania, it
happens that my choice of colors was influenced by those used in
the "contact" figures there, such as
<http://hydra.nat.uni-magdeburg.de/packing/cci/ctc/cci144.ctc.html>.)
> what " conjectures " are you talking about ?
I had said "At the end of the thread, conjectured bounds for this
packing problem will be given." Since we haven't reached the end of
the thread, your question is premature. My conjectured bounds will
possibly be influenced by improved packings which have not appeared
here yet.
The answer to your four questions below is NO.
David W. Cantrell
amy666
since im the only replying to this thread ; it is the end of this thread ^_^
spudnik
> since im the only replying to this thread ; it is the end of this thread ^_^
thus:
doesn't follow "logically;"
of what necessity is a "sea of positrons," if,
by that, you are meaning what others call "the vacuum?"
however, noting that 2.8 is about the second root
of eight (or two times the second root of two), it still
might make an interesting gedanken,
to show the properties of this "sea," if
it can be constrained from combining with the electrons
in the 99.nines per cent of matter that is plasma.
I agree, that "quarks" are really an indivisible symmetry
of some fundamental quanta (which seems to agree
with the mainstream data/theory), and it is good
to try to explain gvavity beyond Kepler's orbital constraints,
unlike Newtonism.
> It is the mass and magnetic-moment coupled together that makes the
> Electron-Positron pair
> unique to the Dirac Equation and allows for only a Positron Sea as
> Space itself.
>
> Now the above was news in the 1930s with Stern and Gerlach and others
> in experiments.
> But what followed in the history of physics was not to say that the
> electron and positron were
> fundamental particles of which the proton and neutron were built
> thereof as a composite of
> the electron and positron, instead, what was done was to dismiss the
> Dirac Equation as
> incomplete and to start the erroneous theory of quarks.
thus:
the amuzement is that the projective plane is the same
as the mobius strip, properly considered; I hint.
> The common point P of the line bundle would be mapped onto a common point T(P) of
> concentric circles, which does not exist in the Euclidean plane. The projective plane
> with complex as well as real coordinates might offer a way out:
>
> in the projective plane we have the so-called isotropic points at infinity: A = (1, i, 0)
> and B = (1, -i, 0) inhomogeneous coordinates. All circles pass through these two points,
> and conversely, any conic section passing through the isotropic points is a circle.
>
> Therefore any mapping of the line bundle at P onto a set of concentric circles must map P
> into one of the isotropic points at infinity, say into point A. All these circles also
> pass through point B. The original of B is necessarily a second common point of the
> concurrent lines, different from P, which does not exist. So our last hope of such
> mappings has vanished.
thus:
um, free the LaRouche Seven ?!?
> So, how do we maximize the rule of truth, and minimize the rule of
> arbitrary power, in professional science?
thus:
"the consortium" of newspapers reported,
a full year after the fact, that Gore would have won
*in a full recount.* what I don't recall, if any
of those three papers, bothered to note that
Gore could have *asked* for a full recount
-- it was that close --
instead of bringing the first suit for a partial birth choice....
when the desideratum is the actual "intent of the voters,"
as legislated in Texas under His Shrubness,
the condition of the chad shall be fully noted -- a-hem!
> > Uh, who carried Florida?
thus:
here is an etymology of THE PHOTON:
photoelectrical effect "hits" measuring device,
"ballistically" imparting its momentum
of one quantum (per Planck h-bar) at some frequency;
the bug is a feature, proven statistically by Bose
(lies, polls, statistics !-)
> where did you ever refute Uncle Al's experiments?
--USA out of Darfur Cruizade!
http://larouchepub.com/other/2008/3537willl_zardari_survive.html
--ROTC, your summer vacation in the Sahara Desert ( S u d a n ) ;
presage the Draft for your middleschool class of '12 --
brought to you by Allstate (tm) and Oxford U.Press!
http://larouchepub.com/pr/2008/080813moloch_brown.html
http://wlym.com
--Wikipedia deletes notice of nullification
of "preclearance rule" of Voting Rights Act
in LaRouche v. Fowler, March 27, 2000;
is the VRAo1965 a dead letter?
http://en.wikipedia.org/wiki/Voting_Rights_Act#Pre-Clearance_2
David W. Cantrell
N = 340, 372, 399, 421, 433 and 499.
A cumulative list of my new packings will be given later in the
thread.
------------------------------------
N = 340 : r = 20.069025103897..., symmetry group D_2
<http://img440.imageshack.us/img440/7334/circles340dx8.gif>
The best packing previously known has r = 20.0745... and is not
symmetric.
------------------------------------
N = 372 : r = 20.950281533076..., symmetry group D_3
<http://img368.imageshack.us/img368/2750/circles372dv2.gif>
The best packing previously known has r = 20.9543... and is not
symmetric.
------------------------------------
N = 399 : r = 21.685484846039..., symmetry group C_3
<http://img366.imageshack.us/img366/6587/circles399et0.gif>
The best packing previously known has r = 21.6900... and is not
symmetric.
------------------------------------
N = 421 : r = 22.139682983447087..., symmetry group C_6
<http://img122.imageshack.us/img122/9803/circles421bu0.gif>
The best packing previously known has r = 22.139682983447142... It is
stated at Packomania to have symmetry group C_3, but the figure
provided there,
<http://hydra.nat.uni-magdeburg.de/packing/cci/cci421.html>, does not
seem to indicate exactly that stated symmetry.
Note that the radius of my packing is only slightly smaller than that
of the best packing previously known.
------------------------------------
N = 433 : r = 22.537671607459..., symmetry group D_3
<http://img122.imageshack.us/img122/6594/circles433oa5.gif>
Trivial rearrangements (by "flipping sextants", so to speak) give
equally good packings with other symmetry groups, such as C_6.
The best packing previously known has r = 22.5420... and is not
symmetric.
------------------------------------
N = 499 : r = 24.062520362757..., symmetry group D_6
<http://img157.imageshack.us/img157/4503/circles499ff3.gif>
The best packing previously known has r = 24.0641... and is not
David W. Cantrell
and 295.
When I started this thread, I had estimated that I'd be finished
finding new packings in about a month. It has now been longer than
that, but I'm continuing to find improved packings. The more, the
merrier! Below are given just my two most recent packings.
A cumulative list of new packings will be given later in the thread.
------------------------------------
N = 108 : r = 11.524032175680..., symmetry group C_2
<http://img221.imageshack.us/img221/1893/circles108uj7.gif>
This is interesting because -- very curiously, I think -- none of the
packings currently shown at Packomania <http://hydra.nat.uni-
magdeburg.de/packing/cci/cci.html> have symmetry group C_2.
The best packing previously known has r = 11.5249... and is not
symmetric.
------------------------------------
N = 295 : r = 18.655217522104..., symmetry group D_3
<http://img356.imageshack.us/img356/2936/circles295iz3.gif>
Trivial rearrangements (by "flipping sextants", so to speak) give
equally good packings with other symmetry groups, such as C_6.
The best packing previously known has r = 18.6559... and symmetry
group D_1.
------------------------------------
David W. Cantrell
David W. Cantrell
will be given later in the thread.)
Also, a comment from my previous post is corrected.
------------------------------------
N = 270 : r = 17.887265667708..., symmetry group C_3
<http://img385.imageshack.us/img385/3987/circles270rx1.gif>
The best packing previously known has r = 17.9041... and is not
symmetric.
------------------------------------
N = 333 : r = 19.825693603974..., symmetry group D_3
<http://img385.imageshack.us/img385/895/circles333uv9.gif>
The best packing previously known has r = 19.8331... and is not
symmetric.
------------------------------------
N = 349 : r = 20.241408667106..., symmetry group C_6
<http://img385.imageshack.us/img385/9922/circles349wn1.gif>
The best packing previously known,
<http://hydra.nat.uni-magdeburg.de/packing/cci/cci349.html>,
has r = 20.241412... The symmetry group stated for it is D_6,
but it actually appears to be D_1 instead.
------------------------------------
In my previous post, I had said:
> ------------------------------------
>
> N = 108 : r = 11.524032175680..., symmetry group C_2
> <http://img221.imageshack.us/img221/1893/circles108uj7.gif>
> This is interesting because -- very curiously, I think -- none
> of the packings currently shown at Packomania
> <http://hydra.nat.uni-magdeburg.de/packing/cci/cci.html>
> have symmetry group C_2.
>
> The best packing previously known has r = 11.5249... and is not
> symmetric.
>
> ------------------------------------
But in fact the best known packing for N = 28 has symmetry group C_2.
I apologize for having overlooked that.
David W. Cantrell
David W. Cantrell
thread) for the radius of a circle in which N unit circles can be
packed. That bound is the primary _raison d'etre_ for this thread.
Since I started this thread, there has been much progress on this
packing problem! (Only a small amount of that progress has been due to
me.) Eckard Specht has updated Packomania
<http://hydra.nat.uni-magdeburg.de/packing/cci/cci.html>,
the site of record for this packing problem, many times. Packomania
now shows the packings mentioned previously in this thread, with the
exception of several for which even better packings have been found
more recently by Eckard himself.
Also, new packings for N = 547, 583, 637, 684 and 721 are presented.
In later posts in this thread, I plan to give a conjectured lower
bound and an approximation formula for r, as well as several packings
with N beyond the range currently being considered at Packomania.
----------------------------------------------------------
A Conjectured Upper Bound for r
Let r denote the radius of the smallest circle in which N unit circles
can be packed, and let k denote pi/(2 sqrt(3)), i.e., the density of
the hexagonal lattice packing. We conjecture that
(*) k r (r - 2) + r/2 + 1 <= N
for all N >= 1, and that equality holds in (*) only when N = 2. From
(*), we get our conjectured upper bound for r:
(UB) r <= 1 + (sqrt((4k - 1)^2 + 16k(N - 1)) - 1)/(4k)
----------------------------------------------------------
How Many of the Best Known Packings Violate the Conjectured Bound?
Before this thread started, the best packings known for N = 337-340,
399-402, 434, and 467-472 violated (*). During this thread, however, I
gave the first packings which showed that (*) holds for N = 339, 340,
399, 401, 402 and 472; more recently, Eckard has given packings which
show that (*) also holds for N = 337, 338 and 471. Thus, the only
values of N up to 500 for which (*) has not yet been shown to hold are
400, 434, and 467-470. I eagerly await improvements for those from
Eckard (and guess that he might already have found packings which show
that (*) holds for them).
Packomania has only recently been extended beyond N = 500 and
improvements have, at least recently, been appearing daily. Many of
the current packings for 500 < N <= 600 violate (*) and the great
majority of the current packings for 600 < N <= 704 violate (*). To
see this, refer to the graph shown at
<http://img356.imageshack.us/img356/6620/data081205cp4.gif>.
The vertical axis shows the difference between left and right sides
of (*); thus, if a point is above the horizontal axis, (*) fails
there.
Points in blue are derived from the current data at Packomania; the
points in red represent the first four new packings given below.
------------------------------------
N = 547 : r = 25.248664945320..., symmetry group C_6
<http://img529.imageshack.us/img529/1695/circles547uq1.gif>
The best packing previously known has r = 25.2678..., which was
already small enough to show that (*) holds. Our new r is small enough
to show that (*) holds not only for N = 547 but also for N = 546.
------------------------------------
N = 583 : r = 26.024361054329..., symmetry group C_6
<http://img399.imageshack.us/img399/9475/circles583lt7.gif>
The best packing previously known has r = 26.0493... and is not small
enough to satisfy (*). Our new r is small enough to show that (*)
holds not only for N = 583 but also for N = 582.
------------------------------------
N = 637 : r = 27.159153681123..., symmetry group C_6
<http://img399.imageshack.us/img399/5515/circles637di2.gif>
The best packing previously known has r = 27.1764..., which was
already small enough to show that (*) holds. Our new r is small enough
to show that (*) holds for N = 637-635.
------------------------------------
N = 684 : r = 28.153339004379..., symmetry group D_3
<http://img399.imageshack.us/img399/7085/circles684gd9.gif>
The best packing previously known has r = 28.2600... and is not small
enough to satisfy (*). Our new r is small enough to show that (*)
holds not only for N = 684 but also N = 683.
------------------------------------
N = 721 : r = 28.868157038689..., symmetry group C_6
<http://img201.imageshack.us/img201/4688/circles721dx8.gif>
(No packing has previously been suggested.)
Our r is small enough to show that (*) holds for N = 721-719.
----------------------------------------------------------
Other Items:
1. Estimated probability of proving/disproving (*): low/very low,
resp.
2. Any information about bounds which have previously appeared in the
literature would be greatly appreciated.
Watch this thread and Packomania for further developments!
David W. Cantrell
David W. Cantrell
Also, new packings of unit circles in circles are presented
for N = 453, 745 and 1483.
"David W. Cantrell" <DWCan...@comcast.net> wrote:
> This post gives a conjectured bound (promised at the beginning of this
> thread) for the radius of a circle in which N unit circles can be
> packed. That bound is the primary _raison d'etre_ for this thread.
>
> Since I started this thread, there has been much progress on this
> packing problem! (Only a small amount of that progress has been due to
> me.) Eckard Specht has updated Packomania
> <http://hydra.nat.uni-magdeburg.de/packing/cci/cci.html>,
> the site of record for this packing problem, many times. Packomania
> now shows the packings mentioned previously in this thread, with the
> exception of several for which even better packings have been found
> more recently by Eckard himself.
> In later posts in this thread, I plan to give a conjectured lower
> bound and an approximation formula for r, as well as several packings
> with N beyond the range currently being considered at Packomania.
The first such packing (for N = 1483) is given below.
> ----------------------------------------------------------
>
> A Conjectured Upper Bound for r
>
> Let r denote the radius of the smallest circle in which N unit circles
> can be packed, and let k denote pi/(2 sqrt(3)), i.e., the density of
> the hexagonal lattice packing. We conjecture that
>
> (*) k r (r - 2) + r/2 + 1 <= N
>
> for all N >= 1, and that equality holds in (*) only when N = 2. From
> (*), we get our conjectured upper bound for r:
>
> (UB) r <= 1 + (sqrt((4k - 1)^2 + 16k(N - 1)) - 1)/(4k)
>
> ----------------------------------------------------------
>
> How Many of the Best Known Packings Violate the Conjectured Bound?
>
> Before this thread started, the best packings known for N = 337-340,
> 399-402, 434, and 467-472 violated (*). During this thread, however, I
> gave the first packings which showed that (*) holds for N = 339, 340,
> 399, 401, 402 and 472; more recently, Eckard has given packings which
> show that (*) also holds for N = 337, 338 and 471. Thus, the only
> values of N up to 500 for which (*) has not yet been shown to hold are
> 400, 434, and 467-470. I eagerly await improvements for those from
> Eckard (and guess that he might already have found packings which show
> that (*) holds for them).
I didn't have to wait long!
(*) has now been shown to hold for all N <= 500.
> Packomania has only recently been extended beyond N = 500 and
> improvements have, at least recently, been appearing daily. Many of
> the current packings for 500 < N <= 600 violate (*)
On Dec. 8, Eckard noted that, for 500 < N <= 600, there were 45 packings
which violated (*). But, as of Dec. 12, that number has been reduced to 35.
> and the great
> majority of the current packings for 600 < N <= 704 violate (*). To
> see this, refer to the graph shown at
> <http://img356.imageshack.us/img356/6620/data081205cp4.gif>.
Here's an updated graph, using the ratio data (in blue) from Packomania on
Dec. 12 and also from my recent packings (in red) for N = 721, 745 and
1483:
<http://img518.imageshack.us/img518/3088/data081212bl9.gif>
> The vertical axis shows the difference between left and right sides
> of (*); thus, if a point is above the horizontal axis, (*) fails there.
New packings:
------------------------------------
N = 453 : r = 23.004335671524..., symmetry group C_3
<http://img176.imageshack.us/img176/6964/circles453jm0.gif>
The best packing previously known has r = 23.0062... and is not
symmetric.
------------------------------------
N = 745 : r = 29.316511442916..., symmetry group C_6
<http://img370.imageshack.us/img370/623/circles745rc0.gif>
(No packing has previously been suggested.)
Our r is small enough to show that (*) holds for N = 745-742.
------------------------------------
N = 1483 : r = 41.11348109..., symmetry group C_6
<http://img139.imageshack.us/img139/7470/circles1483at6.gif>
The figure shows the outer portion of one sextant. (For reference, line
segments radiating from the origin at angles -pi/6 and pi/6 are shown.)
Circles in that sextant which were not shown have their centers on the
hexagonal lattice.
(No packing has previously been suggested.)
Our r is small enough to show that (*) holds for N = 1483-1480.
David W. Cantrell
for N = 647, 783, 847, 1015, 1027 and 1039.
David W. Cantrell <DWCan...@sigmaxi.net> wrote:
> This post gives a conjectured bound (promised at the beginning of this
> thread) for the radius of a circle in which N unit circles can be
> packed. That bound is the primary _raison d'etre_ for this thread.
>
> Since I started this thread, there has been much progress on this
> packing problem! (Only a small amount of that progress has been due to
> me.) Eckard Specht has updated Packomania
> <http://hydra.nat.uni-magdeburg.de/packing/cci/cci.html>,
> the site of record for this packing problem, many times. Packomania
> now shows the packings mentioned previously in this thread, with the
> exception of several for which even better packings have been found
> more recently by Eckard himself.
>
> In later posts in this thread, I plan to give a conjectured lower
> bound and an approximation formula for r, as well as several packings
> with N beyond the range currently being considered at Packomania.
>
> ----------------------------------------------------------
>
> A Conjectured Upper Bound for r
>
> Let r denote the radius of the smallest circle in which N unit circles
> can be packed, and let k denote pi/(2 sqrt(3)), i.e., the density of
> the hexagonal lattice packing. We conjecture that
>
> (*) k r (r - 2) + r/2 + 1 <= N
>
> for all N >= 1, and that equality holds in (*) only when N = 2.
> From (*), we get our conjectured upper bound for r:
>
> (UB) r <= 1 + (sqrt((4k - 1)^2 + 16k(N - 1)) - 1)/(4k)
>
> ----------------------------------------------------------
New packings:
------------------------------------
N = 649 : r = 27.406456150964..., symmetry group C_6
<http://img214.imageshack.us/img214/285/circles649mq5.gif>
Our r is small enough to show that (*) also holds for N = 648 and 647.
The best packing previously known has r = 27.4080... and is not symmetric.
------------------------------------
N = 783 : r = 30.049134898750..., symmetry group C_3
<http://img228.imageshack.us/img228/2159/circles783ux4.gif>
Our r is small enough to show that (*) also holds for N = 782 and 781.
(No packing has previously been suggested.)
------------------------------------
N = 847 : r = 31.221103720988..., symmetry group C_6
<http://img184.imageshack.us/img184/9711/circles847lr3.gif>
Our r is small enough to show that (*) also holds for N = 846 through 844.
(No packing has previously been suggested.)
------------------------------------
N = 1015 : r = 34.139858541148..., symmetry group D_6
<http://img214.imageshack.us/img214/2004/circles1015uf3.gif>
Our r is small enough to show that (*) also holds for N = 1014.
The best packing previously known has r = 34.1453... and is not symmetric.
------------------------------------
N = 1027 : r = 34.328702627679..., symmetry group D_6
<http://img522.imageshack.us/img522/6813/circles1027ze1.gif>
Our r is small enough to show that (*) also holds for N = 1026 and 1025.
The best packing previously known has r = 34.3315 ... and appears to
have symmetry group D_1 (although Eckard does not claim that).
------------------------------------
N = 1039 : r = 34.552359944699..., symmetry group D_6
<http://img214.imageshack.us/img214/3851/circles1039je1.gif>
The best packing previously known has r = 34.5670... and is not symmetric.
------------------------------------
Any information about bounds which have previously appeared in
David W. Cantrell
having symmetry group D_1; the best packings previously known are
asymmetric.
(Packomania's <http://hydra.nat.uni-magdeburg.de/packing/cci/
cci.html>
was last updated on Dec. 18. I expect that there will be a large
update soon.)
------------------------------------
N = 113 : r = 11.749965818893...
<http://img379.imageshack.us/img379/9767/circles113ws4.gif>
The best packing previously known has r = 11.7522...
------------------------------------
N = 114 : r = 11.796646166362...
<http://img107.imageshack.us/img107/8048/circles114td9.gif>
The best packing previously known has r = 11.7988...
------------------------------------
N = 149 : r = 13.435548518285...
<http://img172.imageshack.us/img172/446/circles149yh6.gif>
The best packing previously known has r = 13.435550...
------------------------------------
N = 155 : r = 13.674217236035...
<http://img390.imageshack.us/img390/8760/circles155nt1.gif>
The best packing previously known has r = 13.6787...
------------------------------------
N = 185 : r = 14.93814483546934...
<http://img107.imageshack.us/img107/5538/circles185gw0.gif>
The best packing previously known has r = 14.93814483546985...,
which is only very slightly larger than the radius of our new
symmetric
spudnik
that is *verrrry interestig*.
did you see the *SciAm* article on integer-diameter packings
of a circle -- was taht what it was?
> for N = 113, 114, 149, 155 and 185. All of these improved packings
> having symmetry group D_1; the best packings previously known are
> asymmetric.
thus:
well, it looks as if it ~converges to 0.9999...5, and
we can toss the rest of it, because it changes, BUT
the nines get longer, to which we apply Stevin's algebra.
you know, the part where he said that
it ~converges to 0.9999...1,
was teh first time that I saw that
he wasn't just BSing us. (and,
you know what the tilde means, hereinat,
in the gnu pedagogy .-)
> What happened to the 4 digit?...
> Using Windows Calculator, I get, where s(x) is sqrt(x):
> s(0.9) = 0.94868329805051379959966806332982
> s(0.99) = 0.99498743710661995473447982100121
> s(0.999) = 0.99949987493746091013572606111579
> s(0.9999) = 0.99994999874993749609347654199058
> s(0.99999) = 0.99999499998749993749960937226560
> s(0.999999) = 0.99999949999987499993749996093747
thus:
what does the tilde (~) mean?
> From the description of Stirling-numbers 2'nd kind (see *1)
> we know, that the equation with matrix/vectors of infinite size
> V(x)~ * U = V(e^x-1)~
--Marching too Darfuria, Darfuria --
with Trickier Dick Cheeny from the N.Admin.!!
quasi
<DWCan...@comcast.net> wrote:
>In this update, new packings of unit circles in circles are presented
>for N = 113, 114, 149, 155 and 185. All of these improved packings
>having symmetry group D_1; the best packings previously known are
>asymmetric.
Are there any values of N for which the true optimal packing is
asymmetric?
quasi
David W. Cantrell
Thanks for the question, quasi. I had planned to discuss the issue of
symmetry, and so now would be a good time to do that.
1. Optimal packings are most often asymmetric.
Presumably, for _most_ N, the optimal packing is asymmetric. I say
"Presumably" because optimality has been proven for only a few packings. It
has been proven through N = 11 (Melissen, 1994). Furthermore, I think that,
in 1999, Fodor proved optimality for N = 19, although I haven't seen his
paper. (Optimality may also have been proven for some N of which I'm
unaware.) But surely, for small N, most of the best packings currently
known are optimal. N = 22 is the smallest value for which the presumably
optimal packing is asymmetric; see
<http://hydra.nat.uni-magdeburg.de/packing/cci/cci22.html>.
2. Why are all of my improved packings symmetric?
I didn't look for any asymmetric packings! And the reason that I didn't
look for any asymmetric packings is that I _couldn't_, due to a limitation
of the optimization software which I've used. (Specifically, my version of
Math Optimizer Professional requires that the total number of variables and
constraints be no more than 2000.)
3. Two comments about symmetry groups listed at Packomania
(Note that the penultimate column of the main table at
<http://hydra.nat.uni-magdeburg.de/packing/cci/cci.html> lists the symmetry
groups for the packings.)
a. Some packings which are symmetric are not listed as such, i.e., their
symmetry group is stated to be C_1 mistakenly. Examples: The packings for
N = 99 and 115, <http://hydra.nat.uni-magdeburg.de/packing/cci/cci99.html>
and <http://hydra.nat.uni-magdeburg.de/packing/cci/cci115.html>, actually
have symmetry groups C_3 and D_1, resp.
b. Above the main table, it is stated that "C_1 (D_1) means that the
packing has actually no symmetry C_1 but has the potential to become a
symmetric packing D_1". The designation C_1 (D_1) is used for several
packings, but as best I can tell, whenever that designation is used, in
order to achieve a packing with the stated ratio, the packing _must_ be
asymmetric. Example: Consider the packing for N = 68
<http://hydra.nat.uni-magdeburg.de/packing/cci/cci68.html>.
It is designated C_1 (D_1) and the ratio is given as 9.22977... But as best
I can tell, for N = 68, the smallest ratio for a D_1 packing is 9.22983...
[Of course, I suppose it's possible that there is a D_1 packing which I
failed to find which has ratio 9.22977... But if that were the case, then I
would suggest that that D_1 packing be the one shown and that the symmetry
group be listed simply as D_1.]
4. Quasi-symmetry
Quite a few packings, although not symmetric, are very close to being
symmetric. The packing mentioned above, for N = 68, is a good example. One
might call such packings "quasi-symmetric", although I don't know how such
a thing should be rigorously defined. It might be interesting to devise a
measure M (from 0 to 1, say) to indicate how close a given packing is to a
given symmetry. Then for example, we would want to have M(68, D_1) slightly
less than 1 and M(68, C_3) close to 0.
Three questions:
For N > 15, are all symmetry groups of optimal packings subgroups of D_6,
that is, C_1, C_2, C_3, C_6, D_1, D_2, D_3 or D_6? I would suppose so.
Is symmetry correlated with density? That is, do optimal packings which
have high symmetry tend to have greater density than optimal packings which
have low symmetry? I don't know.
Is 55 <http://hydra.nat.uni-magdeburg.de/packing/cci/cci55.html> the
largest value of N for which the hexagonal lattice gives an optimal
packing?
David W. Cantrell
David W. Cantrell
whether it can be improved. I also mention new packings for N = 690 and
2053.
(BTW, Eckard informs me that Packomania's
<http://hydra.nat.uni-magdeburg.de/packing/cci/cci.html>
should be updated in a few days. I'm guessing that it will be a large
update.)
Earlier in this thread, I had said:
----------------------------------------------------------
A Conjectured Upper Bound for r
Let r denote the radius of the smallest circle in which N unit circles
can be packed, and let k denote pi/(2 sqrt(3)), i.e., the density of
the hexagonal lattice packing. We conjecture that
(*) k r (r - 2) + r/2 + 1 <= N
for all N >= 1, and that equality holds in (*) only when N = 2.
From (*), we get our conjectured upper bound for r:
(UB) r <= 1 + (sqrt((4k - 1)^2 + 16k(N - 1)) - 1)/(4k)
----------------------------------------------------------
A rationale for my conjectured upper bound
The term k r^2 on the right side of (*) should come as no surprise since,
esp. for large N, the central parts of our packings tend to look like
hexagonal lattice packings. A term of the form b r is present to account
for the behavior of the packings near the bounding circle. And a constant
term c was thrown in "for good measure", giving us a quadratic polynomial:
k r^2 + b r + c
Now the packing when N = 2 is the worst one, and so it makes sense to
choose b and c such that k r^2 + b r + c = N when N = 2 and r = 2. Of
course, that one condition doesn't uniquely determine b and c, but a little
experimentation to see what seemed reasonable, together with choosing "nice
looking" coefficients, gave (*).
----------------------------------------------------------
Can the lower bound be improved?
Undoubtedly one could devise a tighter lower bound, but it would probably
be much more complicated. And (*) is very simple and also tight enough to
be quite useful.
An interesting thing, which I did just today, was to use the data for
N <= 500 at Packomania (as of Dec. 18) to see what coefficients b and c
would make
k r^2 + b r + c <= N
yield as tight a lower bound as possible.
Using a numerical minimization in Mathematica, I obtained b = -1.30739
and c = 0.987189 .
I was delighted! Those values are close to those I had already used in (*),
namely, b is close to 1/2 - pi/sqrt(3) = -1.313... and c is close to 1.
This makes me like (*) even more.
----------------------------------------------------------
New packings:
N = 690 : r = 28.246728054450..., symmetry group D_3
<http://img156.imageshack.us/img156/1775/circles690ih5.gif>
The best packing previously known has r = 28.3553...
N = 2053 : r = 48.258550312368..., symmetry group D_6
(I haven't prepared a figure for posting.)
No packing has previously been given. Our r is small enough to show
that (*) also holds for N = 2052-2050.
----------------------------------------------------------
I expect to post a conjectured upper bound, in the same form as (*),
together with an approximation for r in terms of N, soon after Packomania's
next update.
David W. Cantrell
DWCan...@comcast.net
in terms of N will be given in a later post, once Packomania has been
brought up to date.)
As background, I repeat the following, from earlier in this thread:
> ----------------------------------------------------------
>
> A Conjectured Upper Bound for r
>
> Let r denote the radius of the smallest circle in which N unit circles
> can be packed, and let k denote pi/(2 sqrt(3)), i.e., the density of
> the hexagonal lattice packing. We conjecture that
>
> (*) k r (r - 2) + r/2 + 1 <= N
>
> for all N >= 1, and that equality holds in (*) only when N = 2.
> From (*), we get our conjectured upper bound for r:
>
> (UB) r <= 1 + (sqrt((4k - 1)^2 + 16k(N - 1)) - 1)/(4k)
>
> ----------------------------------------------------------
A Lower Bound for r
For all packings currently known (i.e., those now shown at
Packomania),
(**) k r (r - (2 sqrt(13) + 1)) + (55 - c)/(2 sqrt(13) + 1) r + c
>= N
with c = 4.104017592181609... (and with k as before).
Equality holds in (**) when N = 55, by design. And the value of c
could be determined precisely so that we also have equality in (**)
when N = 421, but the precise expression for c would be messy.
I am reluctant to conjecture that (**), with the given value of c,
holds for all N. It is quite possible that dense packings will
eventually be found which would necessitate that the value of c be
reduced in order for (**) to continue to hold for all known packings.
From (**), it is trivial to obtain a lower bound for r, valid for
packings currently known with N >= 4:
Letting p = 2 sqrt(13) + 1 and q = k p^2 - 55 + c for convenience
of notation,
(LB) r >= (q + sqrt(q^2 - 4 k p^2 (c - N)))/(2 k p)
David W. Cantrell
mollwollfumble
wrote:
Hello David. I'd like to refer to these conjectured bounds in a
journal article about digital communications (although I actually know
very little about digital communications). Is that OK? What's the best
way to add it to a reference list?
David W. Cantrell
> On Mar 23, 2:53 pm, "DWCantr...@comcast.net" wrote:
> > In this post, I give a lower bound. (My promised approximation for
> > r in terms of N will be given in a later post, once Packomania has
> > been brought up to date.)
Despite several large updates at Packomania recently, it seems that there
is still a backlog.
> Hello David. I'd like to refer to these conjectured bounds in a
> journal article about digital communications (although I actually
> know very little about digital communications). Is that OK?
Of course. And thanks for your interest!
> What's the best way to add it to a reference list?
Good question. I'm not sure what the best way would be. How about something
like the folllowing?
Cantrell, David W. "-- Packing unit circles in circles: new results", sci.math
<http://groups.google.com/group/sci.math/browse_thread/thread/48cafaebe3041fd9>
(Upper and lower bounds were given on Dec. 6, 2008 and Mar. 23, 2009, resp.)
Perhaps others will have better ideas about how it should be referenced.
Best regards,
David
David W. Cantrell
(There still seems to be a backlog at Packomania. But once it has been
brought up to date, I will post my promised approximation for r in terms
of N.)
------------------------------------
N = 327 : r = 19.649180991046..., symmetry group C_3
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circles327.gif>
The best packing previously known has r = 19.6504... and is not symmetric.
------------------------------------
N = 402 : r = 21.733062157664..., symmetry group C_3
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circles402.gif>
The best packing previously known has r = 21.7342... and is not symmetric.
------------------------------------
N = 403 : r = 21.769628263694..., symmetry group C_6
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circles403.gif>
The best packing previously known has r = 21.7731... and is not symmetric.
------------------------------------
N = 565 : r = 25.575806310403..., symmetry group C_6
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circles565.gif>
The best packing previously known has r = 25.575885... and is not symmetric.
------------------------------------
Note: Much earlier in this thread, I had posted packings for N = 402 and
403 which had symmetry groups D_3 and D_6, resp. Since that time, better
asymmetric packings were found. And now, I have once again found better
symmetric ones, albeit not as highly symmetric as my previous packings.
David W. Cantrell
David W. Cantrell
N = 144: r = 13.247789225080..., symmetry group C_2
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circles144.gif>
Much earlier in this thread, I had posted a packing for N = 144 which had
symmetry group D_2. Since that time, a better asymmetric packing was found,
having 13.2480... And now, I have once again found a better symmetric one,
albeit not as highly symmetric as my previous packing.
Curiously, no circle in my new packing has six tangencies.
David W. Cantrell
DWCan...@comcast.net
> In this post, one new packing is given:
>
> N = 144: r = 13.247789225080..., symmetry group C_2
> <http://i403.photobucket.com/albums/pp113/DWCantrell_photos/circles144.gif>
As of June 1, the packing above has appeared in Packomania, but
attributed to Wenqi Huang and Tao Ye (and stated to be asymmetric). I
do not know when they may have discovered the packing, but it
appeared
in this thread on the date indicated.
Here is a new packing:
N = 522: r = 24.692197122227..., symmetry group D_3
<http://i403.photobucket.com/albums/pp113/DWCantrell_photos/
circles522.gif>
The best packing previously known has r = 24.70609 ... and is
asymmetric.
David W. Cantrell