wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> "Integer" Packing
        
(Message started by: Barukh on Sep 14^th, 2006, 4:03am)

Title: "Integer" Packing
Post by Barukh on Sep 14^th, 2006, 4:03am

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?

Title: Re: "Integer" Packing
Post by towr on Sep 14^th, 2006, 4:26am

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.

Title: Re: "Integer" Packing
Post by Whiskey Tango Foxtrot on Sep 14^th, 2006, 4:53am

Maybe he meant for us to generalize it Icarus.

Title: Re: "Integer" Packing
Post by Barukh on Sep 14^th, 2006, 5:17am

on 09/14/06 at 04:26:58, towr wrote:

??? Could you please elaborate on this? I am not sure I understand this.

Title: Re: "Integer" Packing
Post by towr on Sep 14^th, 2006, 6:42am

on 09/14/06 at 05:17:18, 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.

Title: Some clarity
Post by irrational on Sep 14^th, 2006, 9:27am

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.

Title: Re: Some clarity
Post by Barukh on Sep 14^th, 2006, 9:37am

on 09/14/06 at 06:42:46, 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 09/14/06 at 09:27:10, 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).

Title: Re: Some clarity
Post by towr on Sep 14^th, 2006, 9:57am

on 09/14/06 at 09:27:10, 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. ;D

Title: Re: "Integer" Packing
Post by irrational on Sep 14^th, 2006, 12:43pm

I think the best packing density of the spheres in a cube is ~ 74%.

Googled a bit and here (http://www.tiem.utk.edu/~gross/bioed/webmodules/spherepacking.htm) 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.

Title: Re: "Integer" Packing
Post by THUDandBLUNDER on Sep 14^th, 2006, 4:18pm

on 09/14/06 at 12:43:13, 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?

Title: Re: "Integer" Packing
Post by Barukh on Sep 14^th, 2006, 11:09pm

on 09/14/06 at 16:18:07, 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? ;)

Title: Re: "Integer" Packing
Post by Grimbal on Sep 15^th, 2006, 4:33am

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.

Title: Re: "Integer" Packing
Post by Barukh on Sep 15^th, 2006, 4:34am

Correct, Grimbal!

But how do you show that your claim is correct?

Title: Re: "Integer" Packing
Post by rmsgrey on Sep 15^th, 2006, 1:08pm

on 09/15/06 at 04:34:46, Barukh wrote:

Correct, Grimbal!

But how do you show that your claim is correct?

Quite easily:

[hideb]
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)
[/hideb]

Title: Re: "Integer" Packing
Post by Barukh on Sep 15^th, 2006, 11:27pm

on 09/15/06 at 13:08:57, rmsgrey wrote:

Quite easily:

Nice! :D

Title: Re: "Integer" Packing
Post by SMQ on Sep 16^th, 2006, 7:00am

In fact, isn't this a face-centered-cubic close packing (http://mathworld.wolfram.com/CubicClosePacking.html) of spheres, and therefore optimal even without the integer coordinate restriction?

--SMQ

Title: Re: "Integer" Packing
Post by rmsgrey on Sep 16^th, 2006, 10:03am

on 09/16/06 at 07:00:12, SMQ wrote:

In fact, isn't this a face-centered-cubic close packing (http://mathworld.wolfram.com/CubicClosePacking.html) 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...

Title: Re: "Integer" Packing
Post by Barukh on Sep 17^th, 2006, 12:27am

on 09/16/06 at 07:00:12, SMQ wrote:

In fact, isn't this a face-centered-cubic close packing (http://mathworld.wolfram.com/CubicClosePacking.html) 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.

Title: Re: "Integer" Packing
Post by towr on Sep 17^th, 2006, 7:13am

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?

Title: Re: "Integer" Packing
Post by Grimbal on Sep 18^th, 2006, 10:05am

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.

Title: Re: "Integer" Packing
Post by towr on Sep 18^th, 2006, 1:52pm

on 09/18/06 at 10:05:01, 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)

Title: Re: "Integer" Packing
Post by rmsgrey on Sep 19^th, 2006, 6:05am

on 09/18/06 at 13:52:34, towr 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...

Title: Re: "Integer" Packing
Post by towr on Sep 19^th, 2006, 6:21am

on 09/19/06 at 06:05:53, rmsgrey wrote:

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.

Title: Re: "Integer" Packing
Post by irrational on Sep 19^th, 2006, 10:05am

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.

http://static.flickr.com/93/247580696_c3751701d4_m.jpg

Title: Re: "Integer" Packing
Post by towr on Sep 19^th, 2006, 1:17pm

on 09/19/06 at 10:05:37, 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.

Title: Re: "Integer" Packing
Post by Deedlit on Sep 19^th, 2006, 2:00pm

It's not clear to me. Why can't r be irrational?

Title: Re: "Integer" Packing
Post by SWF on Sep 19^th, 2006, 5:31pm

If you construct three mutually orthogonal vectors of the same length that have all components integers then you can construct a grid of cubes, that can be used to construct one of the requried FCC sphere packings.

Grimbal is correct that all such cubes have integer length of side. Suppose you have constructed 2 of the 3 orthogonal "integer vectors", and their magnitude is L. The third vector orthogonal to both of them is found by taking cross product of the 2 orthogonal vectors and scaling it so its length is L. The cross product has magnitude L² and all its components are integers. All those components must be divided by L for the third orthogonal vector to have magnitude L, and for all components of the scaled vector to end up being integers, L cannot be irrational. Since L is the the square root of a some integer, it is either an integer or irrational. It follows that L must be an integer for there to be three mutually orthogonal "integer vectors" of the same length.

Are there three mutually orthogonal integer vectors of the same length that are not trivially aligned with the original grid? Yes, for example (12,9,20) (-15,20,0) and (-16,-12 15).

Title: Re: "Integer" Packing
Post by Deedlit on Sep 19^th, 2006, 8:07pm

Another proof is to notice that three independent vectors with integer coordinates generate a lattice; each fundamental region has integral volume, equal to the number of lattice points per region. So the side length is the cube root of a positive integer, but it's also the square root of a positive integer, so it must be an integer.

We know that

cube with integral vertices => optimal packing with integral vertices

But what we need is the converse. Is this clear?

Title: Re: "Integer" Packing
Post by Grimbal on Sep 20^th, 2006, 9:51am

on 09/18/06 at 10:05:01, Grimbal wrote:

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.

Maybe I should leave it like that and see if it gets the same fate as Fermat's sidenote. ;)

OK, here it goes. Sorry if the explanations is a little confusing.

The FCC with diameters sqrt(2) is based on a cubic lattice with period 2. I have to show that any other FCC is based on cubes with sides a multiple of 2.

Let's take a cubic lattice with integer coordinates. Let's call A the period or cube size.
A vertex joins 2 points with integer coordinates, therefore A² is in integer.
The Volume of each cube must cover an integer number of unit cubes, therefore A³ is an integer.
Since A³ and A² are both integers, A = A³/A² must be a rational. But if the square of that rational is an integer, it must be an integer.

So, A is an integer. But we wanted a multiple of 2. For this, remember we need the center of the cube on integer coordinates.

Suppose A is odd. I will show that the center can not have integer coordinates.
The square of A is the sum of the squares of dx, dy and dz, the distances on x, y and z of any 2 adjacent points. A² is odd. To get an odd sum, you need 1 or 3 of dx, dy, dz odd. That means that between 2 adjacent points, an odd number of coordinates have a different parity, that comes to say that 2 adjacent points have different parity (i.e. parity of x+y+z). On a cube, you can see that it implies that opposite vertices have different parity.
Now, if the center of the cube had integer coordinates, you could go from one vertex to the opposite in 2 identical steps in integer coordinates, which would imply that opposite vertices have same parity. But since it is not the case, the center can not have integer coordinates. So, if A is odd, you can not build an FCC on that lattice. A must be even.

This shows that an FCC with integer coordinates can only have a period a multiple of 2, having sphere diameters a multiple of sqrt(2).

But that is not all: an optimal packing does not require an FCC in fact. You can get the same density by superposing layers of triangular 2D lattices. My proof doesn't cover that.

Title: Re: "Integer" Packing
Post by Grimbal on Sep 20^th, 2006, 9:55am

Oops, I just realized Deedlit just outlined part of my proof. :-[

Title: Re: "Integer" Packing
Post by Barukh on Sep 20^th, 2006, 10:10am

on 09/20/06 at 09:51:53, Grimbal wrote:

But that is not all: an optimal packing does not require an FCC in fact. You can get the same density by superposing layers of triangular 2D lattices. My proof doesn't cover that.

Correct. Consider the following:

http://barukh.ziv.googlepages.com/densest_packings.PNG/densest_packings-full;init:.PNG

The FCC is obtained when the superposition of layers is strictly periodic (123 or 132). In fact, it is the only optimal lattice packing.

All other “layer arrangements” should therefore include a sequence NMN, that is, two identical layers separated by third. Is it true that such an arrangement can not be totally integral?

Title: Re: "Integer" Packing
Post by SWF on Sep 20^th, 2006, 5:28pm

on 09/20/06 at 10:10:18, Barukh wrote:

In fact, it is the only optimal lattice packing.

Don't you mean "cubic lattice"? Hexagonal close packed (HCP) is considered a "lattice" structure and is the crystal structure of magnesium, for example.

Title: Re: "Integer" Packing
Post by Barukh on Sep 21^st, 2006, 12:37am

on 09/20/06 at 17:28:30, SWF wrote:

Don't you mean "cubic lattice"?

No.

Quote:

Hexagonal close packed (HCP) is considered a "lattice" structure and is the crystal structure of magnesium, for example.

HCP may be considered as a “lattice structure”, but formally it’s not: Sphere packing is called a lattice if it has the following 2 properties: (1) 0 is a center of a sphere; (2) If there are spheres with centers a and b, then there are also spheres with centers a+b and a-b.

Now, in the drawing above, HCP corresponds to the layers arrangement …NMNMNM… Let's take …121212… as an example. It is not difficult to see that if a sphere at position 1 touches a sphere at position 2, then a sphere at position 3 must touch one of them in a lattice packing. Therefore, HCP is not a lattice. But it is in the class of packings called "regular".

BTW, I think it’s not difficult to show that in HCP not all the centers can be put at integer points.