5 ms·

Try this one. I give you a megabox: a million dimensional hypercube spanning one meter along each axis. I also provide a bunch of megaspheres, million-dimensio

Try this one. I give you a megabox: a million dimensional hypercube spanning one meter along each axis. I also provide a bunch of megaspheres, million-dimensional hyperspheres scaled to be 0.99 meters in diameter. How many megaspheres can you fit into the megabox?

sudhirj 8y ago
The first answer in my head is 1, but I'm guessing this is more akin to 'how many circles can you fit in a sphere?'?
- Strilanc 8y ago
  The spheres and the cubes are of the same dimension, so it's not like trying to put flat things inside of a thing with volume. (Technically I should have said million dimensional balls instead of spheres. Sorry if that was confusing.)
  - sudhirj 8y ago
    Then isn’t the answer 1? For 2 dimensions, one circle fits in a square, in three dimensions one sphere fits in a cube. Should be the same for any value of n?
    - Strilanc 8y ago
      Consider that the distance between opposite corners of a square is √2 meters, but for a cube it's √3 meters. In general, for an n-dimensional hypercube of diameter 1m, the exactly-opposite corners are √n meters apart. Meaning, in a million-dimensional meter-diameter hypercube, exactly-opposite corners will be a kilometer apart. There's a lot more diagonal wiggle room than you think.
      - therein 8y ago
        That blew my mind but it still sounds like it would generalize, wouldn't it?
jstanley 8y ago
I'd love to hear the correct answer to this, with explanation.
- OscarCunningham 8y ago
  I can't tell you the exact answer, but it's at least 10^100000. The coordinates of the centre of each megasphere have to lie in the range [0.49,0.51]. Let's just think about megaspheres which are pushed as far as they will go into some corner, so their coordinates are each either 0.49 or 0.51. For each of the one million directions, the distance between the centres of two megaspheres in that dimension will either be 0.02 or 0, depending if their coordinates are the same or different. So by Pythagoras' Theorem the total distance between their centres will be sqrt(n)0.02, where n is the number of dimensions in which their coordinates differ. In order for them to fit the distance must be at least 0.99, so we need sqrt(n)0.02 >= 0.99, which means we need n >= 2451. But we have 1000000 coordinates to choose from, so it's not hard at all to make sure that at least 2451 of them differ. We can start with the sphere whose centre has all coordinates equal to 0.49. Then the sphere with coordinates 0.51 in the first 2451 dimensions, and all others 0.49. Then the sphere with coordinate 0.51 in the next 2451 dimensions. And so on. That squeezes in at least 1000000/2451 = 407 spheres, but even after that there's loads more room. How about the sphere that has coordinates 0.49 and 0.51 alternating? Or changing every 3? In fact if we just assign coordinates at random then each dimension has a 50/50 chance of being different, so we would expect them to be different in 500000 dimensions. The probability of them being different in only 2450 dimensions is given by (1000000 C 2450)/(2^1000000) = 10^-293570. The number of pairs of spheres is quadratic in the number of spheres. So if we just shove the spheres into corners at random we can expect to place about sqrt(1/10^-293570) = 10^146785 spheres before two of them collide. And that still leaves loads of room away from the corners! The point at (0.5,...,0.5) is still a distance of sqrt(1000000)0.01 = 10 away from the centre of any sphere we've placed so far, so there's still plenty of space for more spheres. EDIT: The coordinates should actually be 0.495 and 0.505, but the principle is the same.
  - deleted 8y ago
    [deleted]
- 8y ago

sudhirj 8y ago

The first answer in my head is 1, but I'm guessing this is more akin to 'how many circles can you fit in a sphere?'?

Strilanc 8y ago
The spheres and the cubes are of the same dimension, so it's not like trying to put flat things inside of a thing with volume. (Technically I should have said million dimensional balls instead of spheres. Sorry if that was confusing.)
- sudhirj 8y ago
  Then isn’t the answer 1? For 2 dimensions, one circle fits in a square, in three dimensions one sphere fits in a cube. Should be the same for any value of n?
  - Strilanc 8y ago
    Consider that the distance between opposite corners of a square is √2 meters, but for a cube it's √3 meters. In general, for an n-dimensional hypercube of diameter 1m, the exactly-opposite corners are √n meters apart. Meaning, in a million-dimensional meter-diameter hypercube, exactly-opposite corners will be a kilometer apart. There's a lot more diagonal wiggle room than you think.
    - therein 8y ago
      That blew my mind but it still sounds like it would generalize, wouldn't it?

jstanley 8y ago

I'd love to hear the correct answer to this, with explanation.

OscarCunningham 8y ago
I can't tell you the exact answer, but it's at least 10^100000. The coordinates of the centre of each megasphere have to lie in the range [0.49,0.51]. Let's just think about megaspheres which are pushed as far as they will go into some corner, so their coordinates are each either 0.49 or 0.51. For each of the one million directions, the distance between the centres of two megaspheres in that dimension will either be 0.02 or 0, depending if their coordinates are the same or different. So by Pythagoras' Theorem the total distance between their centres will be sqrt(n)0.02, where n is the number of dimensions in which their coordinates differ. In order for them to fit the distance must be at least 0.99, so we need sqrt(n)0.02 >= 0.99, which means we need n >= 2451. But we have 1000000 coordinates to choose from, so it's not hard at all to make sure that at least 2451 of them differ. We can start with the sphere whose centre has all coordinates equal to 0.49. Then the sphere with coordinates 0.51 in the first 2451 dimensions, and all others 0.49. Then the sphere with coordinate 0.51 in the next 2451 dimensions. And so on. That squeezes in at least 1000000/2451 = 407 spheres, but even after that there's loads more room. How about the sphere that has coordinates 0.49 and 0.51 alternating? Or changing every 3? In fact if we just assign coordinates at random then each dimension has a 50/50 chance of being different, so we would expect them to be different in 500000 dimensions. The probability of them being different in only 2450 dimensions is given by (1000000 C 2450)/(2^1000000) = 10^-293570. The number of pairs of spheres is quadratic in the number of spheres. So if we just shove the spheres into corners at random we can expect to place about sqrt(1/10^-293570) = 10^146785 spheres before two of them collide. And that still leaves loads of room away from the corners! The point at (0.5,...,0.5) is still a distance of sqrt(1000000)0.01 = 10 away from the centre of any sphere we've placed so far, so there's still plenty of space for more spheres. EDIT: The coordinates should actually be 0.495 and 0.505, but the principle is the same.
- deleted 8y ago
  [deleted]
8y ago