Author |
Topic: "Integer" Packing (Read 4695 times) |
|
Deedlit
Senior Riddler
Posts: 476
|
 |
Re: "Integer" Packing
« Reply #25 on: Sep 19th, 2006, 2:00pm » |
 Quote  Modify
|
It's not clear to me. Why can't r be irrational?
|
|
 IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: "Integer" Packing
« Reply #26 on: Sep 19th, 2006, 5:31pm » |
Quote Modify
|
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 L2 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).
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: "Integer" Packing
« Reply #27 on: Sep 19th, 2006, 8:07pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7526
|
|
Re: "Integer" Packing
« Reply #28 on: Sep 20th, 2006, 9:51am » |
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).
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 A2 is in integer.
The Volume of each cube must cover an integer number of unit cubes, therefore A3 is an integer.
Since A3 and A2 are both integers, A = A3/A2 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. A2 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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: "Integer" Packing
« Reply #29 on: Sep 20th, 2006, 9:55am » |
Quote Modify
|
Oops, I just realized Deedlit just outlined part of my proof. 
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: "Integer" Packing
« Reply #30 on: Sep 20th, 2006, 10:10am » |
Quote Modify
|
on Sep 20th, 2006, 9:51am, 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:
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?
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: "Integer" Packing
« Reply #31 on: Sep 20th, 2006, 5:28pm » |
Quote Modify
|
on Sep 20th, 2006, 10:10am, 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.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: "Integer" Packing
« Reply #32 on: Sep 21st, 2006, 12:37am » |
Quote Modify
|
on Sep 20th, 2006, 5:28pm, 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.
|
| « Last Edit: Sep 21st, 2006, 12:38am by Barukh » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print