This is the third installment, do read the previous posts. I left some standing questions in the last post, and I am going to answer at least one of them: Can we squeeze an $l_p$ ball´s volume out of a generalized Wallis sieve?. At the same time I will generalize and simplify the proof from the xkcd post. First, lets generalize the Wallis sieve.
In $d$ dimensions, starting with a $p$ sided hypercube and cutting it appropriately (I leave to the reader to draw it), we get the product,
$$A_n^d = \prod_{n=1}^\infty \frac{p^d n^{d-1} \Big(n+\frac{d}{p}\Big)} {(pn+1)^d},$$
which can be rewritten as the limit
$$A_n^d = lim_{n\to\infty} \frac{p^{nd}\Gamma(n+1)^{d-1}\Gamma\Big(n+1+\frac{d}{p}\Big)\Gamma\Big(1+\frac{d}{p}\Big)^d}{p^{nd}\Gamma(1+\frac{d}{p})\Gamma\Big(n+1+\frac{1}{p}\Big)^d}$$
where I have made use of the Euler gamma function recurrent properties (see previous posts).
Note that the $d$ in $A_n^d$ is an index, not an exponent.
The limit can be separated into two factors (after cancelling the $p^{nd}$),
$$A_n^d = lim_{n\to\infty}\Bigg[ \frac{\Gamma(n+1)^{d-1}\Gamma\Big(n+1+\frac{d}{p}\Big)}{\Gamma\Big(n+1+\frac{1}{p}\Big)^d} \Bigg]\Bigg[\frac{\Gamma\Big(1+\frac{1}{p}\Big)^d}{\Gamma(1+\frac{d}{p})}\Bigg]$$.
Remember that $\frac{\Gamma(n+a)}{\Gamma(n)}\sim n^a$, so the first term when $n\to\infty$
$$ \frac{\Gamma(n+1)^{d-1}\Gamma\Big(n+1+\frac{d}{p}\Big)}{\Gamma\Big(n+1+\frac{1}{p}\Big)^d} = \frac{\Gamma(n+1)^{d-1}\Gamma\Big(n+1+\frac{d}{p}\Big)}{\Gamma\Big(n+1+\frac{1}{p}\Big)^{d-1}\Gamma\Big(n+1+\frac{1}{p}\Big)} \sim \frac{n^{\frac{d-1}{p}}}{n^{\frac{d-1}{p}}}\sim 1.$$
So we obtain, finally,
$$A_n^d = lim_{n\to\infty} \frac{\Gamma\Big(1+\frac{1}{p}\Big)^d}{\Gamma(1+\frac{d}{p})} = V_d^p\Big(\frac{1}{2}\Big).$$
The value of the limit is the volume of the $l_p$ ball, with the case of the hypersphere $p=2$ being a particular case.
Another remarkable case happens when $p=1$ and we obtain the volume of the $d$-dimensional cross-polytope, of radius $R=\frac{1}{2},$ which is $\frac{1}{d!},$ . The cross-polytope is the generalization of the octahedron to $n$ dimensions and is the dual of the hypercube we start with.
This formula lets us also interpret the volume of various fat Cantor and other Smith-Cantor-Volterra sets.
The question still standing from last post is: Is there a geometrical interpretation for the intermediate $A_n^d$? And of course, What more can we learn from this relation between $l_p$ and these sets?
Showing posts with label gamma function. Show all posts
Showing posts with label gamma function. Show all posts
Tuesday, April 26, 2016
Saturday, April 23, 2016
Wallis sieve, and lp n-balls II
This post is a continuation of this one. In it I talked about this video by Matt Parker and some
of its consequences for two dimensions. In the video, he also asserted that, for three dimensions, the approach of cutting off pieces of a cube in tha same way that is done in the Wallis sieve but in three dimensions, would give back the volume of a sphere (see the pretty drawings in the post by Evelyn Lamb).
This opened the question of whether this would happen in higher dimensions. Someone in twitter (thanks!) pointed me to this post in the xkcd forum, where they proof this fact. I am going to transcript, dissect and explain this proof. The original ideas are all from the post, and the mistakes all mine.
First, remember the basic Wallis product formula,
$$\frac{\pi}{4}=\prod_{n=1}^{\infty}\frac{4n(n+1)}{(2n+1)^2}=lim_{n\to\infty} \frac{4^n n! (n+1)!}{(2n+1)!!^2}.$$
Remember that the doble factorial is the product $n!! = n(n-2)(n-4)\cdots~$ which stops when the terms would cease to be positive, i.e. with $⌈n/2⌉$ terms. An important property of the double factorial is that it can be written in terms of Euler gamma function,
$$\Gamma\Big(n+\frac{1}{2}\Big) = \frac{(2n-1)!!\sqrt{\pi}}{2^n}.$$
Remember also that the volume of an $l_p$ hyperball is
$$V_d^p(R) = \frac{(2\Gamma(\frac{1}{p} + 1)R)^d}{\Gamma(\frac{d}{p} + 1)}.$$
So the, taking into account $\Gamma\big(\frac{3}{2}\big)=\frac{\sqrt{\pi}}{2}$, the volume of an d-hypersphere, which is the $l_2$ hyperball is
$$V_d^2(R) = \frac{R^d\pi^{d/2}}{\Gamma(\frac{d}{2} + 1)}.$$
The Wallis product can be written,
$$\frac{\pi}{4}=\prod_{n=1}^{\infty}\Bigg[1-\frac{1}{(2n+1)^2}\Bigg],$$
which is convergent, and we can move around terms (if we are careful), because the series
$$\sum_{n=0}^{\infty}a_n=\sum_{n=0}^{\infty}\frac{1}{(2n+1)^2},$$
is absolutely convergent and we can apply the test for product convergence.
The general product for d dimensions for the Wallis sieve turns out to be
$$\prod_{n=1}^\infty\frac{2^dn^{d-1}(n+\frac{d}{2})}{(2n+1)^d}.$$
For even $d$ we can write this product as
$$lim_{n\to\infty} \frac{2^{nd}(n!)^{d-1}(n+\frac{d}{2})!}{(\frac{d}{2})!((2n+1)!!)^d}.$$
What we have done here is that the factors coming from $n+\frac{d}{2}$ have been expanded into
$\frac{(n+\frac{d}{2})!}{(\frac{d}{2})!}$. This is the tricky part where we have assumed $
d$ to be even. For odd $d$ we can either rewrite in terms of $k$, i.e. $d=2k+1$, and follow a similar approach or be more general and use the gamma function.
The trick to calculate the limit is to separate it into the product of two parts, one of which can be identified as a Wallis product, between square brackets,
$$lim_{n\to\infty} A_n^d = lim_{n\to\infty} \Bigg[\frac{4^{n-1} n! (n-1)!}{(2n-1)!!}\Bigg]^{d/2}\Bigg(\frac{2^dn^{d/2}(n+\frac{d}{2})!}{(\frac{d}{2})!n!(2n+1)^d}\Bigg),$$
$$lim_{n\to\infty} A_n^d =\Big(\frac{\pi}{2}\Big)^{d/2}\Bigg(\frac{2^dn^{d/2}(n+\frac{d}{2})!}{(\frac{d}{2})!n!(2n+1)^d}\Bigg).$$
The last part is to show that the right term converges to $\Big(\frac{d}{2}\Big)!$.
We show it by parts, first, when $n \to \infty$
$$\frac{\Big(n+\frac{d}{2}\Big)!}{n!}=(n+1)(n+2)\cdots(n+\frac{d}{2}) \sim n^{d/2},$$
so the limit can be rewritten as
$$lim_{n\to\infty} A_n^d =\Big(\frac{\pi}{2}\Big)^{d/2}\Bigg(\frac{(2n)^d}{(\frac{d}{2})!(2n+1)^d}\Bigg).$$.
Finally, for big enough $n$, we can use approximate the second term as,
$$\frac{(2n)^d}{(\frac{d}{2})!(2n+1)^d}\sim\frac{1}{(\frac{d}{2})!}=\frac{1}{\Gamma(\frac{d}{2}+1)},$$
so
$$lim_{n\to\infty} A_n^d = \frac{(\frac{\pi}{4})^{d/2}}{\Gamma(\frac{d}{2} + 1)}=V_d^2\Big(\frac{1}{2}\Big).$$
So, now that we have the general formula for $d$ dimensions, the question still stands, can we interpret $A_n^d$ in geometrical terms as we did for $d=2$? What about $l_p$ for $p\neq2$? Stay tuned.
of its consequences for two dimensions. In the video, he also asserted that, for three dimensions, the approach of cutting off pieces of a cube in tha same way that is done in the Wallis sieve but in three dimensions, would give back the volume of a sphere (see the pretty drawings in the post by Evelyn Lamb).
This opened the question of whether this would happen in higher dimensions. Someone in twitter (thanks!) pointed me to this post in the xkcd forum, where they proof this fact. I am going to transcript, dissect and explain this proof. The original ideas are all from the post, and the mistakes all mine.
First, remember the basic Wallis product formula,
$$\frac{\pi}{4}=\prod_{n=1}^{\infty}\frac{4n(n+1)}{(2n+1)^2}=lim_{n\to\infty} \frac{4^n n! (n+1)!}{(2n+1)!!^2}.$$
Remember that the doble factorial is the product $n!! = n(n-2)(n-4)\cdots~$ which stops when the terms would cease to be positive, i.e. with $⌈n/2⌉$ terms. An important property of the double factorial is that it can be written in terms of Euler gamma function,
$$\Gamma\Big(n+\frac{1}{2}\Big) = \frac{(2n-1)!!\sqrt{\pi}}{2^n}.$$
Remember also that the volume of an $l_p$ hyperball is
$$V_d^p(R) = \frac{(2\Gamma(\frac{1}{p} + 1)R)^d}{\Gamma(\frac{d}{p} + 1)}.$$
So the, taking into account $\Gamma\big(\frac{3}{2}\big)=\frac{\sqrt{\pi}}{2}$, the volume of an d-hypersphere, which is the $l_2$ hyperball is
$$V_d^2(R) = \frac{R^d\pi^{d/2}}{\Gamma(\frac{d}{2} + 1)}.$$
The Wallis product can be written,
$$\frac{\pi}{4}=\prod_{n=1}^{\infty}\Bigg[1-\frac{1}{(2n+1)^2}\Bigg],$$
which is convergent, and we can move around terms (if we are careful), because the series
$$\sum_{n=0}^{\infty}a_n=\sum_{n=0}^{\infty}\frac{1}{(2n+1)^2},$$
is absolutely convergent and we can apply the test for product convergence.
The general product for d dimensions for the Wallis sieve turns out to be
$$\prod_{n=1}^\infty\frac{2^dn^{d-1}(n+\frac{d}{2})}{(2n+1)^d}.$$
For even $d$ we can write this product as
$$lim_{n\to\infty} \frac{2^{nd}(n!)^{d-1}(n+\frac{d}{2})!}{(\frac{d}{2})!((2n+1)!!)^d}.$$
What we have done here is that the factors coming from $n+\frac{d}{2}$ have been expanded into
$\frac{(n+\frac{d}{2})!}{(\frac{d}{2})!}$. This is the tricky part where we have assumed $
d$ to be even. For odd $d$ we can either rewrite in terms of $k$, i.e. $d=2k+1$, and follow a similar approach or be more general and use the gamma function.
The trick to calculate the limit is to separate it into the product of two parts, one of which can be identified as a Wallis product, between square brackets,
$$lim_{n\to\infty} A_n^d = lim_{n\to\infty} \Bigg[\frac{4^{n-1} n! (n-1)!}{(2n-1)!!}\Bigg]^{d/2}\Bigg(\frac{2^dn^{d/2}(n+\frac{d}{2})!}{(\frac{d}{2})!n!(2n+1)^d}\Bigg),$$
$$lim_{n\to\infty} A_n^d =\Big(\frac{\pi}{2}\Big)^{d/2}\Bigg(\frac{2^dn^{d/2}(n+\frac{d}{2})!}{(\frac{d}{2})!n!(2n+1)^d}\Bigg).$$
The last part is to show that the right term converges to $\Big(\frac{d}{2}\Big)!$.
We show it by parts, first, when $n \to \infty$
$$\frac{\Big(n+\frac{d}{2}\Big)!}{n!}=(n+1)(n+2)\cdots(n+\frac{d}{2}) \sim n^{d/2},$$
so the limit can be rewritten as
$$lim_{n\to\infty} A_n^d =\Big(\frac{\pi}{2}\Big)^{d/2}\Bigg(\frac{(2n)^d}{(\frac{d}{2})!(2n+1)^d}\Bigg).$$.
Finally, for big enough $n$, we can use approximate the second term as,
$$\frac{(2n)^d}{(\frac{d}{2})!(2n+1)^d}\sim\frac{1}{(\frac{d}{2})!}=\frac{1}{\Gamma(\frac{d}{2}+1)},$$
so
$$lim_{n\to\infty} A_n^d = \frac{(\frac{\pi}{4})^{d/2}}{\Gamma(\frac{d}{2} + 1)}=V_d^2\Big(\frac{1}{2}\Big).$$
So, now that we have the general formula for $d$ dimensions, the question still stands, can we interpret $A_n^d$ in geometrical terms as we did for $d=2$? What about $l_p$ for $p\neq2$? Stay tuned.
Wednesday, April 20, 2016
Wallis sieve, and lp n-balls
I heard about the Wallis sieve the first time in this video by Matt Parker, which is fascinating. Instantly I recognized the pattern. I thought the relation between the Wallis sieve and the formula for the volume of an lp n-ball would be trivial and well-known, it turns out it is neither. Later, I read the blog post in scientific american by Evelyn Lamb and I still thought it would be easy to relate both. Finally, I sat down and did the work and found that the result is not only surprising, but (at least to me), completely non-obvious and has the potential to be very interesting.
The volume of an $l_p$ n-ball, a generalized ball is of radius $R$ is, (for more details and the calculation and history of the formula, see Xiafu Wang's paper),
$$V_d^p(R) = \frac{(2\Gamma(\frac{1}{p} + 1)R)^d}{\Gamma(\frac{d}{p} + 1)}.$$
Note that the ball for $l_2$ is an hypersphere of dimension $d$.
This explains the relation between the Euler gamma function and $\pi$, one of my favorites,
$$\Gamma\Big(\frac{3}{2}\Big) = \frac{\sqrt{\pi}}{2}.$$
At the same time, the gamma function is a generalization of the factorial and satisfies all sorts of recursive formulas similar to the Wallis sieve.
I will refer you to Evelyn Lamb's post for a detailed introduction, but the Wallis sieve can be easily written as a limit using the gamma formula,
$$\frac{\pi}{2} = \prod_{n=1}^{\infty}\Bigg[\frac{(2n)^2}{(2n-1)(2n+1)}\Bigg] = \frac{2\cdot 2\cdot 4\cdot 4\cdot 6\cdot 6\ldots}{1\cdot 3\cdot 3\cdot 5\cdot 5\cdot 7\ldots},$$
which can be rewritten as a limit,
$$\lim_{n\to\infty} \frac{2^{4n}}{n{{2n}\choose{n}}^2} = \pi \lim_{n\to\infty} \frac{n \Gamma(n)^2}{\Gamma(\frac{1}{2}+n)^2} = \pi.$$
We can then apply the gamma duplication formula,
$$\Gamma(z)\Gamma(z+\frac{1}{2})= 2^{1-2z}\sqrt{\pi}\Gamma(2z),$$
and the functional relation,
$$\Gamma(z+1) = z\Gamma(z),$$
to rewrite again the limit,
$$\pi = \lim_{n\to\infty} n\Bigg[\frac{\Gamma(n)^2}{\Gamma(2n)2^{1-2n}}\Bigg]^2 = \lim_{n\to\infty} \frac{1}{n}\Bigg[\frac{\Gamma(1+n)^2 2^{2n}}{\Gamma(2n+1)}\Bigg]^2,$$
so
$$\pi = \lim_{n\to\infty}\frac{V_2^{\frac{1}{n}}(2^n)^2}{4n}.$$
This is, to say the least, surprising. Instead of hyperspheres and a trivial relationship, we get something which looks like an astroid (the image comes from Wikipedia).
So it is the limit of the square of the volume of this figure as it collapses upon itself, its inner radius getting smaller while the outer radio grows. This result is bizarre and not at all trivial.
The formula can be generalized (I will play with this the next time I have some free time) to higher dimensions. The video talks about this, but I have not written their formula down. Also, it will be interesting if fat Cantor sets can be written in terms of hyperballs too.
I have the conjecture which it will be related with the taxicab measure astroid ball, whatever that is.
Edit: fixed a missing n in the denominator in the limit.
The volume of an $l_p$ n-ball, a generalized ball is of radius $R$ is, (for more details and the calculation and history of the formula, see Xiafu Wang's paper),
$$V_d^p(R) = \frac{(2\Gamma(\frac{1}{p} + 1)R)^d}{\Gamma(\frac{d}{p} + 1)}.$$
Note that the ball for $l_2$ is an hypersphere of dimension $d$.
This explains the relation between the Euler gamma function and $\pi$, one of my favorites,
$$\Gamma\Big(\frac{3}{2}\Big) = \frac{\sqrt{\pi}}{2}.$$
At the same time, the gamma function is a generalization of the factorial and satisfies all sorts of recursive formulas similar to the Wallis sieve.
I will refer you to Evelyn Lamb's post for a detailed introduction, but the Wallis sieve can be easily written as a limit using the gamma formula,
$$\frac{\pi}{2} = \prod_{n=1}^{\infty}\Bigg[\frac{(2n)^2}{(2n-1)(2n+1)}\Bigg] = \frac{2\cdot 2\cdot 4\cdot 4\cdot 6\cdot 6\ldots}{1\cdot 3\cdot 3\cdot 5\cdot 5\cdot 7\ldots},$$
which can be rewritten as a limit,
$$\lim_{n\to\infty} \frac{2^{4n}}{n{{2n}\choose{n}}^2} = \pi \lim_{n\to\infty} \frac{n \Gamma(n)^2}{\Gamma(\frac{1}{2}+n)^2} = \pi.$$
We can then apply the gamma duplication formula,
$$\Gamma(z)\Gamma(z+\frac{1}{2})= 2^{1-2z}\sqrt{\pi}\Gamma(2z),$$
and the functional relation,
$$\Gamma(z+1) = z\Gamma(z),$$
to rewrite again the limit,
$$\pi = \lim_{n\to\infty} n\Bigg[\frac{\Gamma(n)^2}{\Gamma(2n)2^{1-2n}}\Bigg]^2 = \lim_{n\to\infty} \frac{1}{n}\Bigg[\frac{\Gamma(1+n)^2 2^{2n}}{\Gamma(2n+1)}\Bigg]^2,$$
so
$$\pi = \lim_{n\to\infty}\frac{V_2^{\frac{1}{n}}(2^n)^2}{4n}.$$
This is, to say the least, surprising. Instead of hyperspheres and a trivial relationship, we get something which looks like an astroid (the image comes from Wikipedia).
So it is the limit of the square of the volume of this figure as it collapses upon itself, its inner radius getting smaller while the outer radio grows. This result is bizarre and not at all trivial.
The formula can be generalized (I will play with this the next time I have some free time) to higher dimensions. The video talks about this, but I have not written their formula down. Also, it will be interesting if fat Cantor sets can be written in terms of hyperballs too.
I have the conjecture which it will be related with the taxicab measure astroid ball, whatever that is.
Edit: fixed a missing n in the denominator in the limit.
Subscribe to:
Posts (Atom)