Pi from the Menger Sponge

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
phlip
Restorer of Worlds
Posts: 7542
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Pi from the Menger Sponge

Postby phlip » Wed Apr 13, 2016 12:19 pm UTC

Time for some completely-useless recreational number-crunching...

So, I was watching this YouTube video about pi and the Sierpinski Carpet/Menger Sponge, which talks about this interesting fact:

Say you build a Sierpinski Carpet, starting with a 2x2 square, but instead of always cutting the square into 3x3 and taking out the centre square, you cut it into successive odd numbers and take out the middle square. That is, for the first level you cut each square into 3x3 and take out the centre 1, then for the next level you cut each of the 8 squares into 5x5 and take out the centre 1, and so on. Then the area of the final carpet no longer converges to zero... you get the product of (8/9) * (24/25) * (48/49) * ..., which you can massage into the Wallis product, and you end up with an area of pi. In particular, you end up that this carpet has the same area as a unit circle inscribed in the original square. Apparently this is also called the Wallis sieve.

Go up a level. Say you build a Menger Sponge in the same way. You start with a 2x2x2 cube, and cut it into 3x3x3, remove the middle axes, then cut each of the remaining 20 cubes into 5x5x5 and remove the middle axes, and so on. Now, I don't know enough about solving infinite products to really understand why, but the video references an article called "Squeezing Pi from a Menger Sponge" that says this converges to a volume of 4/3pi... the same volume as a unit sphere inscribed in the original cube.

Now, after watching this video, I was curious if it continued to higher dimensions. Now, I don't have the knowhow to actually solve any of these infinite products, but I do have Wolfram|Alpha and a list of n-ball volume formulae from Wikipedia...

If you take a 4D hypercube, and divide it into 3x3x3x3, punch out the middles (specifically, remove any subhypercube that is in the middle third on at least two axes), you're left with 48/81. Then divide it into 5x5x5x5, punch out the middles, and you're left with 512/625. Then continue.

For step i, you're dividing it into (2i+1)4 cubes, and keeping (16i4 + 32i3) of them. I have no idea how you derive it, but if you take that infinite product, multiply it by 16, and plug it into Wolfram|Alpha, you get pi2/2. Which is exactly the volume of the unit 4-ball.

To continue even higher:

For a n-dimensional Menger sponge, start with a 2n hypercube. Then, for the i-th term, you're dividing each cube into (2i+1)n subcubes, and then you're keeping the ones which are either (a) not in the centre on any axis, or (b) in the centre on exactly one axis. In a sense, these are the corners and the edges of the sponge.

For part (a), this is simple enough - on each axis, there are 2i coordinates that aren't in the centre, so this covers (2i)n cubes. For part (b), there are n dimensions that can be in the centre, and (2i)n-1 values for the other coordinates, for a total of n(2i)n-1 cubes.

So, putting it all together, the question is: is
2n * product i=1 to infinity of ((2i)n + n(2i)n-1) / (2i+1)n
equal to the area of the unit n-sphere?

Wolfram|Alpha claims it's correct at least as far as n=8... beyond that, the calculation times out. But does it hold for all n? And can you prove it? For that matter, can you prove it for these specific cases, in a way that doesn't involve "and then I plugged it into W|A and then magic happened"?

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25727
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Pi from the Menger Sponge

Postby gmalivuk » Wed Apr 13, 2016 12:52 pm UTC

I wonder if there might be something simpler to work with if you consider the volumes that are removed at each step.

It would give you a sum to work with instead of a product, though each successive term of the sum wouldbe the product of an increasing number of terms itself, so maybe that wouldn't help after all.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Derek
Posts: 2125
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Pi from the Menger Sponge

Postby Derek » Thu Apr 21, 2016 1:07 am UTC

If it's true up to n=8, then I would be fairly confident in hypothesizing that it's true for all n. I feel like this could be proven inductively using the recursive formula for the volume of an n-ball: V_n = V_(n-2) * 2pi/n. The general form of the volume for an n-dimensional Wallis Sieve (with side length 1) is: W_n = product(k=0 to infinity, 1 - (2nk + 1)/(2k+1)^n). We already have two base cases, so it would only be necessary to prove the inductive step:

2pi/(n+2) * 2^n * W_n = 2^(n+2) * W_(n+2)

Or simplifying slight:

pi/2 * W_n = (n+2) * W_(n+2)

But I'm not good enough with infinite products to approach this. I poked around with it a bit, but got nowhere.

User avatar
phlip
Restorer of Worlds
Posts: 7542
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Pi from the Menger Sponge

Postby phlip » Thu Apr 21, 2016 6:33 am UTC

Yeah, I tried coming at it from a similar angle... but that addition inside the product term makes manipulating the product complicated, and the fact that "n" makes an appearance as a multiplicand, rather than just exponents, makes inducting on it also complicated...

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
eta oin shrdlu
Posts: 448
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: Pi from the Menger Sponge

Postby eta oin shrdlu » Thu Apr 21, 2016 5:29 pm UTC

In all dimensions the identity is a form of the Wallis product. Basically all you have to do is count the factors in the numerator and denominator of the infinite product and shuffle the factors into the Wallis-product form, making sure that you keep the product convergent.

Let's start by looking at the Wallis product. In one form it's
    pi/4 = Prod 4n(n+1)/(2n+1)2 = lim 4N N! (N+1)! / (2N+1)!!2
(infinite products will all run over n=1,2,3,...; limits are as N goes to infinity).

[It can also be written as
    pi/4 = Prod [1 - 1/(2n+1)2]
from which you can see that the product is absolutely convergent (the factors approach 1 faster than harmonically). We can shuffle factors around without too much worry as long as we keep the product absolutely convergent.]

Let's start with the simple case of D=3 dimensions. In the nth step, we divide each cube into (2n+1)3 subcubes and remove 6n+1 of them, leaving 8n3+12n2 of them. So we want to compute the infinite product
    Prod (8n3+12n2)/(2n+1)3 = Prod 4n2(2n+3)/(2n+1)3 .
The factors (2n+3)/(2n+1) telescope, giving us something more like the Wallis product. More precisely this product is
      = lim (4N N!2 (2N+3)!!) / (3 (2N+1)!!3)
      = lim [4N N! (N+1)! / (2N+1)!!2] * (2N+3)/(3(N+1))
      = (pi/4) (2/3) = pi/6
(the bracketed quantity is the Wallis product) and so if we start with a 2*2*2 cube the limiting volume is 8pi/6=4pi/3.

So the idea is to try to regroup the factors into Wallis products so that whatever leftovers there are have a finite nonzero limit. (We want the rational function left over on the right side to have numerator and denominator degree equal.)

In the D-dimensional case the numerator is (as asserted in the original post) (2n)D+D(2n)D-1 = (2n)D-1(2n+D). If D is odd the factor 2n+D is odd and will cancel with one of the denominator factors as in the D=3 case, leaving a denominator (2n+1)D-1 and so (D-1)/2 Wallis products and (D-1)/2 factors of pi; if D is even we don't get this cancellation and so there are D/2 factors of pi.

In the even-D case the product is then
    Prod 2D nD-1 (n+D/2) / (2n+1)D
      = lim (2ND N!D-1 (N+D/2)!) / ((D/2)! (2N+1)!!D)
      = lim [4N-1 (N-1)! N! / (2N-1)!!2]D/2 * (2D ND/2 (N+D/2)!) / ((D/2)! N! (2N+1)D)
      = (pi/4)D/2 / (D/2)! .
(Again the bracketed quantity is again the Wallis product. For N>>D, we find the limit of the extra factors on the right by grouping (N+D/2)!/N! ~ ND/2, giving ~ (2N)D / ((D/2)! (2N+1)D) ~ 1/(D/2)!.) For a hypercube of side 2 the volume is then 2D times this, or piD/2/(D/2)!. The odd-D case is similar.

Cauchy
Posts: 599
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Pi from the Menger Sponge

Postby Cauchy » Thu Apr 21, 2016 9:14 pm UTC

I'd like to point out that the formula doesn't work for n = 1. The length of a 1-dimensional unit ball is 2, but the length of the 1-sponge is 2*[2/3*4/5*6/7*...], which is decidedly less than 2 (since it's 0).

Derek
Posts: 2125
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Pi from the Menger Sponge

Postby Derek » Fri Apr 22, 2016 12:08 am UTC

Yeah, it doesn't work for n=1, but I think it works for everything above that.

User avatar
phlip
Restorer of Worlds
Posts: 7542
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Pi from the Menger Sponge

Postby phlip » Fri Apr 22, 2016 1:05 am UTC

1 dimension works, but the sponge definition gets a bit degenerate...
phlip wrote:
(specifically, remove any subhypercube that is in the middle third on at least two axes)
Since we don't have two axes, there are no intervals (hypocubes?) that are in the middle on at least two axes, so we never remove anything. The 1-dimensional sponge is just the complete interval.

And looking at the formula:
phlip wrote:
2n * product i=1 to infinity of ((2i)n + n(2i)n-1) / (2i+1)n
With n=1 this is just
2 * product i=1 to infinity of (2i + 1) / (2i + 1)
which isn't too hard to calculate.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

Derek
Posts: 2125
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Pi from the Menger Sponge

Postby Derek » Fri Apr 22, 2016 12:04 pm UTC

I don't think that's right. If you look at the formula I came up with:

product(k=0 to infinity, 1 - (2nk + 1)/(2k+1)^n)

I need to think more about the relation between your formula and mine. My initial (egocentric) guess is that your's is wrong, but I need to think about this more when I'm not about to fall asleep.

Cauchy
Posts: 599
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Pi from the Menger Sponge

Postby Cauchy » Fri Apr 22, 2016 10:25 pm UTC

You're right, philip. I had got it into my head that you remove 1/(2n+1)^d of the measure each step, but that obviously can't be right since that's a decreasing function of d, and more needs to be removed as d increases, since the ratio of the measures of a d-ball and the d-cube that contains it decreases as d increases.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 8 guests