wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> hypersphere packing
        
(Message started by: JocK on Jul 25^th, 2004, 1:30pm)

Title: hypersphere packing
Post by JocK on Jul 25^th, 2004, 1:30pm

In N dimensions, N+1 equally sized hyperspheres can be configurated in a cluster such that each hypersphere touches all other hyperspheres.

For N[to][infty] calculate the radius of the smallest hypersphere that can contain such a cluster (assign a radius of unity to the spheres in the cluster).

J8)CK

Title: Re: hypersphere packing
Post by Eigenray on Jul 26^th, 2004, 6:59am

First let's inductively find (n+1) equally spaced vectors in S^n-1 [subset] [bbr]ⁿ.
[hide]For n=1 we have of course v₀=-1, v₁=1.
Suppose v₀, ..., v_n are equally spaced in S^n-1. Now let's rotate each of these up into the (n+1)th dimension, giving vectors v_i' = (v_i*sqrt(1-t²),t) [in] Sⁿ, which gives us room to insert the vector (0, -1).
Let d_n = <v_i,v_j>, i [ne] j. d₁ = -1.
We pick t in such a way to make them equally spaced, i.e.,
d_n+1 = <v_i', v_j'> = <v_k',(0,-1)>
d_n(1-t²) + t² = -t
t = ~~-1,~~ d_n/(d_n-1).
d_n+1 = -d_n/(d_n-1)
Inductively we find d_n = -1/n.
The distance r_n between two of these vectors is given by
r_n² = <v_i-v_j, v_i-v_j> = 1 + 1 - 2(-1/n) = 2 + 2/n.
So, with our equally spaced vectors in place, we scale them such that each pair are a distance 2 apart to make room for the hyperspheres:
w_i = v_i*2/r_n
The radius of the containing hypersphere is |w_i|+1 = [sqrt](2n/(n+1)) + 1 [to] 1+[sqrt]2[/hide]

Title: Re: hypersphere packing
Post by Eigenray on Jul 27^th, 2004, 6:14am

Compare to this packing (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1065293213), where the radius of the inscribed hypersphere is unbounded as n[to][infty].

Title: Re: hypersphere packing
Post by JocK on Jul 31^st, 2004, 12:15pm

Correct Eigenray!

Your reference to the inscribed hypersphere problem is interesting, as it is (losely) related to the follow-up question:

Things get a bit more complicated as we now investigate unequally sized hyperspheres:

In n dimensions, if properly sized, n+2 hyperspheres can be configurated in a cluster such that each hypersphere touches all other hyperspheres. In particular, for n dimensions this holds for properly chosen [alpha][subn]>1 if the hyperspheres have radii R, [alpha][subn] R, [alpha][subn]^2 R, .. , [alpha][subn]^(n+1) R.

This means that an infinite nesting of hyperspheres can be constructed with each subsequent hypersphere being a factor 1/[alpha] smaller in size, such that within this nesting each group of n+2 subsequently sized hyperspheres consist of hyperspheres that all touch each other. For such a cluster of n+2 subsequent hyperspheres, the smallest hypersphere is the inscribed hypersphere of the n+1 larger spheres.

For n=3, [alpha] < 2. Can you prove this? What is the exact value?

What happens if we increase n beyond 3? What is the value for [alpha][subn] for n [to] [infty]? And how does [alpha][subn]^n (the volume-ratio of subsequent hyperspheres) behave for n [to] [infty]?

J8)CK