Author |
Topic: "Integer" Packing (Read 4694 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
"Integer" Packing
« on: Sep 14th, 2006, 4:03am » |
 Quote  Modify
|
Consider packing spheres into 3-dimensional space, such that the centers of spheres can be put only at the points with integral coordinates.
What maximum density can be obtained by such a packing?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: "Integer" Packing
« Reply #1 on: Sep 14th, 2006, 4:26am » |
Quote Modify
|
Depends on the size of the spheres, doesn't it?
If you rescale the grid and spheres, such that you end upo with unit spheres, then the larger the spheres you start with, the better the coordinates can approximate the real-number coordinates for densest packing.
And of course if the spheres have a radius of half a unit or less, the best you can do is a cube packing.
|
| « Last Edit: Sep 14th, 2006, 4:28am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Whiskey Tango Foxtrot
Uberpuzzler
Sorry Goose, it's time to buzz a tower.
Gender:
Posts: 1672
|
|
Re: "Integer" Packing
« Reply #2 on: Sep 14th, 2006, 4:53am » |
Quote Modify
|
Maybe he meant for us to generalize it Icarus.
|
|
IP Logged |
"I do not feel obliged to believe that the same God who has endowed us with sense, reason, and intellect has intended us to forgo their use." - Galileo Galilei
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: "Integer" Packing
« Reply #3 on: Sep 14th, 2006, 5:17am » |
Quote Modify
|
on Sep 14th, 2006, 4:26am, towr wrote:Depends on the size of the spheres, doesn't it?
If you rescale the grid and spheres, such that you end upo with unit spheres, then the larger the spheres you start with, the better the coordinates can approximate the real-number coordinates for densest packing. |
|
 Could you please elaborate on this? I am not sure I understand this.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: "Integer" Packing
« Reply #4 on: Sep 14th, 2006, 6:42am » |
Quote Modify
|
on Sep 14th, 2006, 5:17am, Barukh wrote:| Could you please elaborate on this? I am not sure I understand this. |
|
By rescaling, effective you use rational coordinates.
And for every set of real coordinates, you can find rational coordinates approximating them up to an arbitrarily small error.
Hence the maximum density you can achieve is arbitrarily close to that for real coordinates.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
irrational
Junior Member
Gender:
Posts: 52
|
|
Some clarity
« Reply #5 on: Sep 14th, 2006, 9:27am » |
Quote Modify
|
Barukh do you mean a cube when you say "3-D Space"
or else, the space can be a sphere and 1 sphere for the whole space ... Density of space = Density of sphere 
Can the spheres intersect ?
@towr I think the question calls for integral co-ordinates.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Some clarity
« Reply #6 on: Sep 14th, 2006, 9:37am » |
Quote Modify
|
on Sep 14th, 2006, 6:42am, towr wrote:| And for every set of real coordinates, you can find rational coordinates approximating them up to an arbitrarily small error. |
|
Ah, got it. No, the approximate solutions are not allowed (or, if you wish, there is a restriction on the size of the spheres that prevents getting a solution with required accuracy – see also irrational’s remark  ).
on Sep 14th, 2006, 9:27am, irrational wrote:| Barukh do you mean a cube when you say "3-D Space" |
|
A cube.
Quote:| Can the spheres intersect ? |
|
No (it’s packing).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Some clarity
« Reply #7 on: Sep 14th, 2006, 9:57am » |
Quote Modify
|
on Sep 14th, 2006, 9:27am, irrational wrote:| @towr I think the question calls for integral co-ordinates. |
|
That doesn't matter though; it's just a matter of multiplying by the divisor of whatever rationals you use in the rescaled version.
But Barukh just undercut that approach; if there's an upper limit to the ball size, it doens't work.
Oh well, my solution for balls with diameters of less than a unit still stands.. (putting one at all integral coordinates)
Quote:| Can the spheres intersect ? |
|
If that were allowed, you could put an arbitrary number of spheres at each coordinate, or even at one. 
|
| « Last Edit: Sep 14th, 2006, 10:00am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
irrational
Junior Member
Gender:
Posts: 52
|
|
Re: "Integer" Packing
« Reply #8 on: Sep 14th, 2006, 12:43pm » |
Quote Modify
|
I think the best packing density of the spheres in a cube is ~ 74%.
Googled a bit and here you go!!
Those grocers do know something about geometry
-------EDIT----------
Of course this is assuming that the 3 dimensions of the cube are also integers.
|
| « Last Edit: Sep 14th, 2006, 12:44pm by irrational » |
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: "Integer" Packing
« Reply #9 on: Sep 14th, 2006, 4:18pm » |
Quote Modify
|
on Sep 14th, 2006, 12:43pm, irrational wrote:I think the best packing density of the spheres in a cube is ~ 74%.
|
|
But with the face-centred and hexagonal packing that gives ~74%, some of the centres of the spheres must be at irrational coordinates, right?
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: "Integer" Packing
« Reply #10 on: Sep 14th, 2006, 11:09pm » |
Quote Modify
|
on Sep 14th, 2006, 4:18pm, THUDandBLUNDER wrote:
But with the face-centred and hexagonal packing that gives ~74%, some of the centres of the spheres must be at irrational coordinates, right?
|
|
What would you say, irrational?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: "Integer" Packing
« Reply #11 on: Sep 15th, 2006, 4:33am » |
Quote Modify
|
With a diameter of sqrt(2), you can put a sphere at every "even" coordinate (x+y+z is even) and get an optimal packing.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: "Integer" Packing
« Reply #12 on: Sep 15th, 2006, 4:34am » |
Quote Modify
|
Correct, Grimbal!
But how do you show that your claim is correct?
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2872
|
|
Re: "Integer" Packing
« Reply #13 on: Sep 15th, 2006, 1:08pm » |
Quote Modify
|
on Sep 15th, 2006, 4:34am, Barukh wrote:Correct, Grimbal!
But how do you show that your claim is correct? |
|
Quite easily:
| hidden: |
Any packing with spheres or diameter more than 1 can't have sphere-centres at more than half the lattice points as there'd then have to be at least one pair occupying adjacent lattice points which would then intersect. Since the proposed packing does have spheres centered on half the points, it is optimal for spheres with diameter bigger than 1 and not more than sqrt(2)
|
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: "Integer" Packing
« Reply #14 on: Sep 15th, 2006, 11:27pm » |
Quote Modify
|
on Sep 15th, 2006, 1:08pm, rmsgrey wrote:
Nice! 
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: "Integer" Packing
« Reply #15 on: Sep 16th, 2006, 7:00am » |
Quote Modify
|
In fact, isn't this a face-centered-cubic close packing of spheres, and therefore optimal even without the integer coordinate restriction?
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: "Integer" Packing
« Reply #16 on: Sep 16th, 2006, 10:03am » |
Quote Modify
|
on Sep 16th, 2006, 7:00am, SMQ wrote:In fact, isn't this a face-centered-cubic close packing of spheres, and therefore optimal even without the integer coordinate restriction?
--SMQ |
|
Seems that way, but rather than proving the Kepler Conjecture, it's easier to prove optimality under the restricted conditions...
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: "Integer" Packing
« Reply #17 on: Sep 17th, 2006, 12:27am » |
Quote Modify
|
on Sep 16th, 2006, 7:00am, SMQ wrote:In fact, isn't this a face-centered-cubic close packing of spheres, and therefore optimal even without the integer coordinate restriction?
--SMQ |
|
Yes, it is. The purpose of my question was to show that fcc can be placed in the Cartesian system in a way that the centers of the spheres are at integer coordinates.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: "Integer" Packing
« Reply #18 on: Sep 17th, 2006, 7:13am » |
Quote Modify
|
So for which radii can we achieve this in an integer lattice?
(Aside from [sqrt]2 and multiples thereof)
And are there interesting densest packings for values in between?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: "Integer" Packing
« Reply #19 on: Sep 18th, 2006, 10:05am » |
Quote Modify
|
You can't have an optimal fcc in integer coordinates with diameters that are not a multiple of sqrt(2).
But I have no time yet to write the proof.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: "Integer" Packing
« Reply #20 on: Sep 18th, 2006, 1:52pm » |
Quote Modify
|
on Sep 18th, 2006, 10:05am, Grimbal wrote:| You can't have an optimal fcc in integer coordinates with diameters that are not a multiple of sqrt(2). |
|
Are you telling me that any cube that can be placed with its vertices on integer coordinates has integer sidelengths? Because that's what it comes down to.
(And in case someone wants to nitpick, I did mean integer multiples of [sqrt]2)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: "Integer" Packing
« Reply #21 on: Sep 19th, 2006, 6:05am » |
Quote Modify
|
on Sep 18th, 2006, 1:52pm, towr wrote:
Are you telling me that any cube that can be placed with its vertices on integer coordinates has integer sidelengths? Because that's what it comes down to.
(And in case someone wants to nitpick, I did mean integer multiples of [sqrt]2)
|
|
I admit I'm not entirely gifted with 3D visualisation, but I can't seem to find any cubes with side length [sqrt]2 - Octahedra, yep; cubes with side-length 2, yep. No cubes of side-length [sqrt]2 though...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: "Integer" Packing
« Reply #22 on: Sep 19th, 2006, 6:21am » |
Quote Modify
|
on Sep 19th, 2006, 6:05am, rmsgrey wrote:| I admit I'm not entirely gifted with 3D visualisation, but I can't seem to find any cubes with side length [sqrt]2 - Octahedra, yep; cubes with side-length 2, yep. No cubes of side-length [sqrt]2 though... |
|
That sidenote in my last post applied to my post before that; because any number is some real multiple of [sqrt]2...
So any cube with a sidelength that's not an integer would be fine.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
irrational
Junior Member
Gender:
Posts: 52
|
|
Re: "Integer" Packing
« Reply #23 on: Sep 19th, 2006, 10:05am » |
Quote Modify
|
Dang it!!!... Grimbal beat me to it
But if you see this image of the maximum packing density then I think it will make it clear why the radius of the sphere should be sqrt(2) or multiples there of.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: "Integer" Packing
« Reply #24 on: Sep 19th, 2006, 1:17pm » |
Quote Modify
|
on Sep 19th, 2006, 10:05am, irrational wrote:| But if you see this image of the maximum packing density then I think it will make it clear why the radius of the sphere should be sqrt(2) or multiples there of. |
|
Only if you can't fit noninteger cubes in the grid. Otherwise it's straightforward to show you can; just a matter of scaling (by noninteger factor) and rotating.
Hence the question, can that be done? There is no a priori reason I can think of why not, although I haven't been able to find another orthogonal set of 3 equal length vectors starting at the origin.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print