Balls in balls in R^n

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Fafnir43
Posts: 98
Joined: Mon Apr 14, 2008 11:11 pm UTC

Balls in balls in R^n

In R^n under the Euclidean metric, show that there do not exist two disjoint closed unit balls inside any closed ball of radius 2. Show that there do, however, exist (1+c)^n disjoint closed unit balls inside any closed ball of radius 2.001, for some absolute constant c > 0.

I've been squinting at this for a while, and I don't even see where to begin. The first part is easy - just assume B_1(x) and B_1(y) are proper subsets of B_2(z). Then the fact that they're disjoint implies d(x, y) > 2. Then just extend the line between x and y by a unit in each direction. Then one end (a, say) must be in B_1(x) and the other (b, say) must be in B_2(y), and by the equality case of the triangle inequality in R^n we have d(a, b) > 4 which gives a contradiction.

But the second part is just nasty. I'm pretty sure you can only fit two balls in in R^2 and R^3, which gives 2^(1/2) - 1 <= c < 3^(1/3) - 1. And c has to depend somehow on the radius of the larger ball, here 2.001. And I can see the general idea is that more dimensions give more space to work with, since the "volume" of an n-sphere of radius greater than 1 goes up rapidly as n increases. But beyond that I'm clueless... Any hints?

(Disclaimer: this is a homework problem for a metric/topological spaces course, specifically one of the questions at the end of the sheet that hardly anyone tries. To give you an idea of the likely difficulty, the next question on there asks you to solve Kuratowski's Closure-Complement Problem and give an example of a 14-set.)

Edit: Fixed typo. Now the first part of the question makes sense.
Last edited by Fafnir43 on Sun Sep 07, 2008 1:02 am UTC, edited 1 time in total.
This post brought to you by the language C and the number F.

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Re: Balls in balls in R^n

Hmm, just a quick thought:

Fafnir43 wrote:And c has to depend somehow on the radius of the larger ball, here 2.001.

I'd be inclined to think that the figure 2.001 is arbitrary (i.e., that there is some absolute c s.t. the theorem holds for any 2+epsilon, epsilon>0. Of course, for large epsilon, you may get even more balls.).
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Balls in balls in R^n

Long story short, can anyone provide an example of 3 radius 1 spheres inside of a radius 2.001 sphere in any dimension?

I don't believe you can do this in 3 dimensions.

Given an example in n dimensions, take the 3 centres of the small balls, plus the centre of the large ball. These 4 points define a 3-space. Intersect that 3-space with the example and you should get an example in 3 dimensions. (The 3 dimensional balls have the correct radius by choice of the space)
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

Harg
Posts: 130
Joined: Thu Jul 10, 2008 8:24 pm UTC

Re: Balls in balls in R^n

How do these four points give a three dimensional subspace and not a four dimensional one?

PS: The OP should put "... closed unit balls..." in the first problem, for posterity
Last edited by Harg on Sat Sep 06, 2008 7:35 pm UTC, edited 1 time in total.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Balls in balls in R^n

Harg wrote:How do these four points give a three dimensional subspace and not a four dimensional one?

The same way 2 points give a line, 3 a plane.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

Frimble
Posts: 480
Joined: Thu Apr 10, 2008 6:57 pm UTC
Location: UK

Re: Balls in balls in R^n

I agree with mike-I, you would need a circle of radius 1+(2/(3^0.5))=2.1547... or greater to contain three circles of radius 1. It follows (I think) that you would need an n-sphere of radius 1+(2/(3^0.5)) or greater to contain three n-spheres of radius 1

Ed. Geometry calculations corrected.

PS. Wait, the text says balls, not spheres. Does that mean we are trying to fit lumps of plasticine into a sphere?
"Absolute precision buys the freedom to dream meaningfully." - Donal O' Shea: The Poincaré Conjecture.
"We need a reality check here. Roll a D20." - Algernon the Radish
"Should I marry W? Not unless she tells me what the other letters in her name are" Woody Allen.

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Balls in balls in R^n

Frimble wrote:I agree with mike-I, you would need a circle of radius 1+(2/(3^0.5))=2.1547... or greater to contain three circles of radius 1. It follows (I think) that you would need an n-sphere of radius 1+(2/(3^0.5)) or greater to contain three n-spheres of radius 1

Ed. Geometry calculations corrected.

PS. Wait, the text says balls, not spheres. Does that mean we are trying to fit lumps of plasticine into a sphere?

An open ball is the inside of a sphere, a closed ball is the inside of the sphere, plus the sphere itself. I'm inclined to agree with mike-I too, for precisely the reasons he stated.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Fafnir43
Posts: 98
Joined: Mon Apr 14, 2008 11:11 pm UTC

Re: Balls in balls in R^n

Harg wrote:PS: The OP should put "... closed unit balls..." in the first problem, for posterity

Whoops... Fixed now.

Frimble wrote:PS. Wait, the text says balls, not spheres. Does that mean we are trying to fit lumps of plasticine into a sphere?

"Ball" is a standard term when dealing with metric spaces - the open ball of radius r about x is denoted by B_r(x), and means the set {y: d(x, y) < r}, where d is the metric of the space you're working in. So in R, balls are open intervals (we have d(x, y) = |y - x|). In R^2 they're open discs, in R^3 they're open spheres, and in R^n they're open n-dimensional spheres. Here we're talking about closed balls rather than open balls, so in a slight abuse of notation I'm using B_r(x) to mean {y: d(x, y) <= r}. Some people call them "neighbourhoods" instead - sorry for any confusion!

mike-l wrote:Given an example in n dimensions, take the 3 centres of the small balls, plus the centre of the large ball. These 4 points define a 3-space. Intersect that 3-space with the example and you should get an example in 3 dimensions. (The 3 dimensional balls have the correct radius by choice of the space)

I'm admittedly low on sleep, but that sounds watertight to me after a little checking. I've double-checked the question and I didn't make any (other) errors in transcribing it, so it looks like it's wrong. Which sort of explains why I couldn't do it! Thanks guys.
This post brought to you by the language C and the number F.

Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Balls in balls in R^n

Fafnir43 wrote:
mike-l wrote:Given an example in n dimensions, take the 3 centres of the small balls, plus the centre of the large ball. These 4 points define a 3-space. Intersect that 3-space with the example and you should get an example in 3 dimensions. (The 3 dimensional balls have the correct radius by choice of the space)

I'm admittedly low on sleep, but that sounds watertight to me after a little checking. I've double-checked the question and I didn't make any (other) errors in transcribing it, so it looks like it's wrong. Which sort of explains why I couldn't do it! Thanks guys.

If you ask your teacher about it and get a proof or a correct reformulation, could you update us about it?

Fafnir43
Posts: 98
Joined: Mon Apr 14, 2008 11:11 pm UTC

Re: Balls in balls in R^n

Sure thing, although it'll probably be in about a month's time.
This post brought to you by the language C and the number F.

lgonick
Posts: 17
Joined: Sun Jun 22, 2008 2:48 pm UTC

Re: Balls in balls in R^n

This problem is what professional mathematicians call, um, a ball-buster.

tachobg
Posts: 1
Joined: Wed Jun 20, 2007 4:17 am UTC

Re: Balls in balls in R^n

Fafnir43 wrote:more dimensions give more space to work with, since the "volume" of an n-sphere of radius greater than 1 goes up rapidly as n increases.

I'm not sure how to attempt the second part, but the volume of an n-ball has a global maximum as you vary dimension. Since the volume is defined in terms of the gamma function, you can have continuous "dimension", which gives a global maximum at n = 5 point something. So it really would depend on how the volumes of the small n-balls compare with the volume of the larger n-ball as n grows, as opposed to the total volume of the large one.

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Balls in balls in R^n

You don't need to know the volume of the large ball to know that its volume is 2.001d times the volume of the smaller balls in dimension d. So regardless of whether volume increases or has a global maximum at 5, the relative volume increases exponentially. Volume is obviously not the limiting factor here. mike-l already pointed out the limiting factor.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Fafnir43
Posts: 98
Joined: Mon Apr 14, 2008 11:11 pm UTC

Re: Balls in balls in R^n

Yup, turns out the problem was wrong. The corrected version now reads as follows:

For this question we work in R^n with the Euclidean metric. Show that there do not exist two disjoint closed unit balls inside any closed ball of radius 2. Show that there do, however, exist (1+c)^n disjoint closed unit balls inside any ball of radius 3.001, for some absolute constant c>0. Do there exist exponentially many disjoint closed unit balls inside a ball of radius 2.001?

(This isn't a request for help, by the way - I just thought I'd satisfy people's curiosity.)
This post brought to you by the language C and the number F.

Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Balls in balls in R^n

Thanks for the update! That problem seems more reasonable.

Cycle
Posts: 146
Joined: Mon Feb 25, 2008 1:55 am UTC

Re: Balls in balls in R^n

Shouldn't have read this topic before taking a shower, I couldn't stop thinking about this.

Note: I'm going to use open balls here, so I can say 2 balls of radius 1 fit in a ball of radius 2.

OK, so we can do the same sort of thing the Hilbert space l2. Now, mike's argument works exactly the same in this case, so we can say that only two unit balls fit into a ball of radius 2 in l2. On the other hand, it's clear that we can fit infinitely many unit balls in the ball of radius 3 (put their centers at the orthonormal basis vectors). Therefore, there's some number r0, such that infinitely many unit balls fit in a ball of radius r0, but for any smaller radius, only finitely many fit. Is there any way to calculate this number?

There are other questions too. We can do the same thing for any finite value: let rn be the smallest radius such that n unit balls fit in a ball of radius rn. Then rn is a bounded, increasing sequence, with limit r0. Is rn eventually constant? Phrased another way, is there an n such that: if n unit balls fit in a larger ball, then necessarily infinitely many do?

Note that, by using n-dim slicing trick, rn is also equal to the smallest radius in Rn so that n unit balls fit into a larger ball. So you can calculate everything in finite dimensional space. I kind of doubt these numbers have a formula though, since it's like sphere packing from hell.

treolor
Posts: 25
Joined: Fri Mar 27, 2009 2:06 pm UTC

Re: Balls in balls in R^n

Fafnir43 wrote:Yup, turns out the problem was wrong. The corrected version now reads as follows:

For this question we work in R^n with the Euclidean metric. Show that there do not exist two disjoint closed unit balls inside any closed ball of radius 2. Show that there do, however, exist (1+c)^n disjoint closed unit balls inside any ball of radius 3.001, for some absolute constant c>0. Do there exist exponentially many disjoint closed unit balls inside a ball of radius 2.001?

(This isn't a request for help, by the way - I just thought I'd satisfy people's curiosity.)

hmm, i'm still stuck? now the radius is 3.001, how do you do it??

wootle
Posts: 3
Joined: Wed Dec 31, 2008 6:19 pm UTC

Re: Balls in balls in R^n

In R3 put balls at
(a,a,a)
(a,a,-a)
(a,-a,a)
(a,-a,-a)
(-a,a,a)
(-a,a,-a)
(-a,-a,a)
(-a,-a,-a)

where a = 1+e (e>0 is tiny)
Then any two distinct balls have centres differing by 2a in at least one coordinate, so distance between them is 2a > 2.
Generalise in the obvious way , this gives 2^n balls in R^n

edit: fail, they're not inside the ball of radius 3 once n gets sufficiently large, since modulus of their centres is sqrt(n*a)

wootle
Posts: 3
Joined: Wed Dec 31, 2008 6:19 pm UTC

Re: Balls in balls in R^n

Its enough to solve the problem for the radius exactly 3, but using open balls. This just makes things neater

For R^n:
Let $a = \frac{2}{\sqrt{n}}$
Now any vector with each coordinate +a or -a has modulus at most 2. So a unit ball with this vector as its centre fits inside the ball of radius 3.
Suppose x,y are two such vectors that differ in at least n/4 components. Then [imath]|x-y| \geq \sqrt{(n/4)(2a)^2} = \sqrt{(n/4)(16/n)} = 2[/imath]
So if we have a subset X of [imath]\{0,1\}^n[/imath] such that any two members of X differ in at least n/4 places, then we can map each member of X to a vector with components + or - a (in the obvious way), and place a unit ball on each of these vectors - then these balls will fit inside the ball of radius 3, will be pairwise disjoint, and there will be |X| of them.
So its enough to construct such an X, having size exponential in n.

pmaj
Posts: 2
Joined: Wed Apr 29, 2009 5:39 pm UTC

Re: Balls in balls in R^n

As Cycle says, packing problems are generally rather difficult; however the case of [imath]k[/imath] disjoint open unit balls inside a ball has a simple and complete answer in the [imath]n[/imath]-dimensional Euclidean space if $k\leq n+1,$ and in an infinite dimensional Hilbert space with no restrictions. In this case it is available a configuration of [imath]k[/imath] pairwise tangent unit balls (so the centers are the vertices [imath]a_1,..,a_k[/imath] of a regular [imath](k+1)[/imath] dimensional symplex with edge [imath]2[/imath]; this is easily realized starting from an orthonormal basis). A small computation shows that the distance of each vertex from the baricenter is $\sqrt{2\Big(1-\frac{1}{k} \Big)}.$ Moreover, any other point of the space necessarily has a larger distance from at least one of the [imath]k[/imath] vertices. In terms of inclusions of balls, this reads: the [imath]k[/imath] open unit balls centered in [imath]a_1,..,a_k[/imath] are included in a ball of radius $r_k:=1+\sqrt{2\Big(1-\frac{1}{k} \Big)},$ which is minimal for this configuration. To show that the configuration is also optimal, let [imath]x_1,...,x_k[/imath] be the centers of [imath]k[/imath] disjoint open unit balls contained in a ball of radius [imath]r[/imath] centered in a point [imath]x_0[/imath]. Consider the map from the finite set [imath]\{x_1,..x_k\}[/imath] into [imath]\{a_1,..a_k\}[/imath] taking [imath]x_j[/imath] in the corresponding [imath]a_j[/imath] for each [imath]1\leq j\leq k[/imath]. Since for all [imath]1\leq i<j\leq k[/imath] it holds [imath]\|a_i-a_j\|=2\leq\|x_i-x_j\|[/imath] this map is 1-Lipschitz and by the Kirszbraun's theorem it extends to a 1-Lipschitz map globally defined; in particular there exists a point [imath]a_0[/imath] such that for all [imath]1\leq j\leq k[/imath] one has [imath]\|a_0-a_j\|\leq\|x_0-x_j\|[/imath], therefore [imath]r_k\leq1+\|a_0-a_j\|\leq 1+\|x_0-x_j\|\leq r[/imath]. This shows that there are k disjoint unit open balls in a ball of radius r if and only if [imath]r\geq r_k[/imath]. Notice that in an infinite dimensional Hilbert space this implies that there are infinitely many disjoint open unit balls inside a ball of radius r if and only if $r\geq 1+\sqrt{2},$ For instance, the unit balls centered in [imath]\sqrt{2}e_j[/imath], where [imath]\{e_j\}_j[/imath] is an orthonormal basis, are disjoint and included in a ball of radius [imath]1+\sqrt{2}[/imath] centered in the origin. Moreover, for [imath]r<1+\sqrt{2},[/imath] the maximum number of disjoint open unit balls inside a ball of radius [imath]r[/imath] is $\Big\lfloor\frac{2}{2-(r-1)^2}\Big\rfloor.$.

Quincunx
Posts: 10
Joined: Sat May 02, 2009 11:50 am UTC

Re: Balls in balls in R^n

A bit off-topic, but has anyone ever noticed how the circle, sphere, etc, gets smaller and smaller in comparison with a box it is put in? (square, cube, etc), as it gets rounder and more corners are cut off? By the 11th dimension, this corner weaste is 99.91%; so that a hendecaglome which exactly fits in a hendecacube box, occupies less than a thousandth the space, yet touches the all 22 decacube sides. Vanishing space.

pmaj
Posts: 2
Joined: Wed Apr 29, 2009 5:39 pm UTC

Re: Balls in balls in R^n

Yes, it's a big source of troubles for life in a many dimensional world ( as the ones conjectured by modern phisic theories ). Consider for instance the following situation. You live in a 50 dimensional spheric planet, say of the same diameter of our old 3D Earth. Imagine you are having your whisky, or a gin tonic if you prefer, at home, so you have taken some small cubes of ice from the fridge, and now you go to the terrace with your glass. Now suppose you forgot one ice cube on the table in the kitchen... Question: how much will the level of seas on the planet be increased, due to your lazy behaviour?

Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Balls in balls in R^n

S_{49} = 50 C_50 r^(49)
with C_50 = pi^25 / 25!

V(50-dimensional cube with side x) = x^50

R =~ 6 378.1 km
x =~ 3 cm

Using the V_50 (volume of a 50 dimensional sphere) equation might actually be easier:
V_50 = pi^25 R^50 / 25!

Volume(base planet) =~ pi^25 / 25! * (6000 km)^50=~ 10^(326) m^50
Volume(ice cube) =~ 10^-76 m^50
Adding the ice cube to the planet we get ... crap, it broke my calculator.

R^50 pi^25/25! = (6000 km)^50 pi^25/25! + (3 cm)^50
R^50 = (6000 km)^50 + (3 cm)^50 * 25!/(pi^25)
= 8.08281277 × 10^238 m^50 + (3 * 10^-2m)^50 25!/(pi^25)
= 8.08281277 × 10^238 m^50 + ~(10^-75) m^50 25!/(pi^25)
= 10^239 m^50 + 10^-62 m^50
R^50 = 10^239 m^50 * (1 + 10^-401) m^50
= ~Radius of earth *~ (1+10^-8)

10^-8 * 6000 km = 6 cm.

So that is my back of napkin estimate.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

hocl
Posts: 82
Joined: Thu Apr 16, 2009 3:18 am UTC

Re: Balls in balls in R^n

I take it you just have to show that there exist more than (1+c)^n balls, not that this is the best bound?

pmaj wrote:Yes, it's a big source of troubles for life in a many dimensional world ( as the ones conjectured by modern phisic theories ). Consider for instance the following situation. You live in a 50 dimensional spheric planet, say of the same diameter of our old 3D Earth. Imagine you are having your whisky, or a gin tonic if you prefer, at home, so you have taken some small cubes of ice from the fridge, and now you go to the terrace with your glass. Now suppose you forgot one ice cube on the table in the kitchen... Question: how much will the level of seas on the planet be increased, due to your lazy behaviour?
I don't follow. How would sea levels be affected?

Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Balls in balls in R^n

The 3 cm x 3 cm x 3 cm ice cube melts.

There is enough volume in the ice cube to create enough water to cover the entire 50 dimensional planet about 6 cm deep. Which seems off, actually.

(Then again, I probably messed up my approximation of how much it causes things to get covered.)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: Balls in balls in R^n

Yakk wrote:R^50 = 10^239 m^50 * (1 + 10^-401) m^50
= ~Radius of earth *~ (1+10^-8)

Sanity check - if a number is bigger than one, it gets smaller if you take the 50th root.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.