Author 
Topic: "Integer" Packing (Read 4311 times) 

Barukh
Uberpuzzler
Gender:
Posts: 2276


"Integer" Packing
« on: Sep 14^{th}, 2006, 4:03am » 
Quote Modify

Consider packing spheres into 3dimensional 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: 13729


Re: "Integer" Packing
« Reply #1 on: Sep 14^{th}, 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 realnumber 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 14^{th}, 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: 1667


Re: "Integer" Packing
« Reply #2 on: Sep 14^{th}, 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 14^{th}, 2006, 5:17am » 
Quote Modify

on Sep 14^{th}, 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 realnumber 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: 13729


Re: "Integer" Packing
« Reply #4 on: Sep 14^{th}, 2006, 6:42am » 
Quote Modify

on Sep 14^{th}, 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 14^{th}, 2006, 9:27am » 
Quote Modify

Barukh do you mean a cube when you say "3D 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 coordinates.


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Some clarity
« Reply #6 on: Sep 14^{th}, 2006, 9:37am » 
Quote Modify

on Sep 14^{th}, 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 14^{th}, 2006, 9:27am, irrational wrote:Barukh do you mean a cube when you say "3D 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: 13729


Re: Some clarity
« Reply #7 on: Sep 14^{th}, 2006, 9:57am » 
Quote Modify

on Sep 14^{th}, 2006, 9:27am, irrational wrote:@towr I think the question calls for integral coordinates. 
 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 14^{th}, 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 14^{th}, 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 14^{th}, 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 14^{th}, 2006, 4:18pm » 
Quote Modify

on Sep 14^{th}, 2006, 12:43pm, irrational wrote:I think the best packing density of the spheres in a cube is ~ 74%. 
 But with the facecentred 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 14^{th}, 2006, 11:09pm » 
Quote Modify

on Sep 14^{th}, 2006, 4:18pm, THUDandBLUNDER wrote: But with the facecentred 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: 7515


Re: "Integer" Packing
« Reply #11 on: Sep 15^{th}, 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 15^{th}, 2006, 4:34am » 
Quote Modify

Correct, Grimbal! But how do you show that your claim is correct?


IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2840


Re: "Integer" Packing
« Reply #13 on: Sep 15^{th}, 2006, 1:08pm » 
Quote Modify

on Sep 15^{th}, 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 spherecentres 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 15^{th}, 2006, 11:27pm » 
Quote Modify

on Sep 15^{th}, 2006, 1:08pm, rmsgrey wrote: Nice!


IP Logged 



SMQ
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 2084


Re: "Integer" Packing
« Reply #15 on: Sep 16^{th}, 2006, 7:00am » 
Quote Modify

In fact, isn't this a facecenteredcubic close packing of spheres, and therefore optimal even without the integer coordinate restriction? SMQ


IP Logged 
SMQ



rmsgrey
Uberpuzzler
Gender:
Posts: 2840


Re: "Integer" Packing
« Reply #16 on: Sep 16^{th}, 2006, 10:03am » 
Quote Modify

on Sep 16^{th}, 2006, 7:00am, SMQ wrote:In fact, isn't this a facecenteredcubic 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 17^{th}, 2006, 12:27am » 
Quote Modify

on Sep 16^{th}, 2006, 7:00am, SMQ wrote:In fact, isn't this a facecenteredcubic 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: 13729


Re: "Integer" Packing
« Reply #18 on: Sep 17^{th}, 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: 7515


Re: "Integer" Packing
« Reply #19 on: Sep 18^{th}, 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: 13729


Re: "Integer" Packing
« Reply #20 on: Sep 18^{th}, 2006, 1:52pm » 
Quote Modify

on Sep 18^{th}, 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: 2840


Re: "Integer" Packing
« Reply #21 on: Sep 19^{th}, 2006, 6:05am » 
Quote Modify

on Sep 18^{th}, 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 sidelength 2, yep. No cubes of sidelength [sqrt]2 though...


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13729


Re: "Integer" Packing
« Reply #22 on: Sep 19^{th}, 2006, 6:21am » 
Quote Modify

on Sep 19^{th}, 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 sidelength 2, yep. No cubes of sidelength [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 19^{th}, 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: 13729


Re: "Integer" Packing
« Reply #24 on: Sep 19^{th}, 2006, 1:17pm » 
Quote Modify

on Sep 19^{th}, 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



