Tuesday, October 09, 2012

Supergod challenge: proving a $300 inequality Spyridon Michalakis of Quantum Frontiers (a fun blog with John Preskill: not only about quantum computation) offered his readers a wonderful challenge with a$300 bounty that the first contributors kindly postponed to the first solver of another challenge, the Supergod challenge – which happened to be your humble correspondent who sort of needed the payment due to some recent expenses.

The Supergod challenge is the following problem: (use the minimalistic mobile template)
Using no calculators and no "uncertain" assumptions about inequalities, prove that$\frac{1}{2}\cdot\frac{3}{4}\cdot\frac{5}{6}\cdot\frac{7}{8}\cdot \cdots \cdot \frac{99}{100} \lt 0.08.$ The increasingly difficult problems "1", "2", and "God challenge" had $$1/10$$, $$1/11$$, and $$1/12$$ on the right hand side. Each new task was almost 10% harder than the previous one. The improvement from God challenge to Supergod challenge was just 4% or so but this step was arguably the most technically challenging because, as the people who are allowed to use calculators know, the left hand side equals 0.0795892, just 0.5% away from the Supergod challenge!

If you feel technically strong, try to solve the Megagod challenge whose right hand side is 0.0796. ;-)
We will soon switch to methods that (many?) Russian middle-schoolers are claimed to have mastered, but before we do so, let's try to solve it using the "powerful tools" one expects among professional physicists or mathematicians.

What are these methods? Well, the left hand side may also be written with many extra factors of $$2$$ that cancel:$\frac{1/2}{2/2}\cdot\frac{3/2}{4/2}\cdot\frac{5/2}{6/2}\cdot\frac{7/2}{8/2}\cdot \cdots \cdot \frac{99/2}{100/2}$ You see that the "big denominator" is nothing else than $$50!$$, the product of integers between $$1$$ and $$50$$. Similarly, if you know the Gamma function, the "big numerator" is $$(49.5)!$$ times $$(-0.5)!$$ but $$(-0.5)!=\sqrt{\pi}$$, exactly.

To calculate the ratio of these factorials, we would need to use Stirling's approximation for the generalized factorial (valid for large arguments)$n!\approx \sqrt{2\pi n} \zav { \frac{n}{e} }^n$ This is valid in the sense that the limit of the ratio of both sides for $$n\to\infty$$ goes to one. With this approximation, the left hand side of the challenge is$\frac{49.5! }{50!\sqrt{\pi}}\approx \frac{49.5^{50}\sqrt{e}}{50^{50.5}\sqrt{\pi}}\approx 0.0795879.$ This is really wonderfully close to the exact result $$0.0795892$$ but we couldn't quite compute it this accurately without a calculator. Moreover, we would need to remember some boring messy formulae to be sure that the error of the figure is small enough to keep us below $$1/10$$, $$1/11$$, $$1/12$$, or $$1/12.5$$, the latter is the Supergod right hand side in a different form.

A somewhat easier calculation would involve the rewriting of the approximation above as$\frac{49.5^{50}\sqrt{e}}{50^{50.5}\sqrt{\pi}} = \zav{\frac{49.5}{50}}^{50}\sqrt{ \frac{e}{50\pi} }$ The first factor looks like the limiting "many years of small interest rates" formula for the exponential,$\lim_{N\to\infty} \zav{ 1+\frac{x}{N} }^N = \exp(x)$ and in this way, it produces nothing else than $$\exp(-1/2)$$ which cancels against the $$\sqrt{e}$$ factor in the second part of the expression. So the Supergod left hand side may be approximated by $$\sqrt{1/50\pi}\approx 0.0797885$$ which is still wonderfully accurate. But we probably needed a calculator or Mathematica (although the square root of $$50\pi$$ is not so bad: $$50\pi\gt 50\cdot 3.14 = 157\gt 156.25=12.5^2$$) and we would need extra messy discussions (well, yes, the maximum relative error of Stirling's basic formula for $$n!$$ is $$\exp(1/12n)-1$$ which is about $$1/600$$ in our case, and most of it actually cancels between $$49.5$$ and $$50$$) to prove that the error in our approximation doesn't spoil the inequalities, especially in the case of the hardest one.

One could make the accuracy even more stunning by using a more accurate version of the Stirling's formula, e.g. one that has $$\sqrt{2\pi(n+1/6)}$$ instead of just $$\sqrt{2\pi n}$$. For example, the exact ratio of these improved Stirling's approximations would yield $$0.0795892$$: at least six significant figures would agree and maybe more. With those improvements, the computational difficulty would become even more inhuman, however.

Tatu, 30 minutes, English version: lyrics

Going to the Russian middle school for some explosive methods

So instead, let us use elementary maths. The easier challenges up to God were kind of independently solved by Anthony Leverrier and Alex Ridgway. My method probably overlaps in the spirit but I have found mine independently so I can't tell you whether the core is quite the same. Greg Kuperberg offered clarifying comments in all the situations.

First, note that the Stirling's discussion above featured the square root of $$\pi$$, among other things. This suggests it's useful to square the formula to get rid of the square roots. We will immediately see another advantage of the squaring: the two copies of the integers may be divided to individual factors in a "split way". At any rate, let's square and invert the original Supergod inequality. After we conveniently divide the formula by $$101$$ as well, the original inequality is equivalent to$\frac{2^2}{1\cdot 3}\cdot \frac{4^2}{3\cdot 5}\cdot \frac{6^2}{5\cdot 7}\cdot \cdots \cdot \frac{100^2}{99\cdot 101}\gt \frac{1}{101}\cdot 12.5^2$ or, using a more explicit-integer-based notation,$\frac{4}{3} \cdot \frac{16}{15}\cdot \frac{36}{35}\cdot \cdots\cdot \frac{10,000}{9,999}\gt \frac{625}{404}.$ Note that the left hand side is the product of 50 factors each of which is greater than one but they approach one rather quickly. We need to collect a "sufficient number of excesses over one" from these factors to surpass $$625/404$$ on the right hand side.

If we just multiply $$4/3\cdot 16/15\cdot 36/35$$, we get $$256/175\approx 1.463$$ which is enough to surpass the God challenge threshold $$12^2/101\approx 1.426$$ but isn't enough for the Supergod challenge threshold $$625/404\approx 1.547$$. To get over the Supergod threshold by picking several initial factors and replacing others by one, we would need roughly ten factors – and the integers we would generate would be too large.

Clearly, we can't afford to completely ignore almost all the factors: we must treat them and include them "collectively" in some way. It turns out that it's enough to beat Supergod if we only keep $$4/3$$ as a genuine multiplicative factor and we "linearize" all other factors by the inequality$(1+x_2)(1+x_3)\cdot \cdots \cdot (1+x_{50}) \gt 1+(x_2+x_3+\cdots x_{50}).$ Even with this reduction defined by the linearization – we just neglect terms of second order and higher order in the "perturbations" $$x_i$$ – it will be enough to beat Supergod. In our particular case, we have$\eq{ x_i &= \frac{1}{4i^2-1},\\ (x_2,x_3,\dots x_{50}) &= ( \frac{1}{15},\frac{1}{35},\cdots \frac{1}{9,999} ). }$ A funny and clever thing is that the sum of these 49 terms $$x_i$$ may actually be computed analytically, using a simple formula. Greg Kuperberg reminded me that this sum is known as the telescoping sum (one displaying the telescoping cancellation). If we had all of them, we would get$\frac{1}{3}+\frac{1}{15}+\cdots \frac{1}{4n^2-1} = \frac{n}{2n+1}.$ It's that simple. You may prove this formula by the mathematical induction. For $$n=1$$, both sides give $$1/3$$ and you may go from $$n-1$$ to $$n$$ because both sides jump by the last term of the left hand side. That's the telescoping calculation: it's helpful to compute five or four partial sums to see that the result is really simple. More imaginatively, the term in the sum may be rewritten as$\frac{1}{4n^2-1} = \frac{1}{4n-2} - \frac{1}{4n+2}$ and in this difference form, we see that all the terms in the sum except for the first one, $$1/2$$, and the last one, $$-1/(4n+2)$$, cancel against their neighbors. The sum is therefore $$+1/2-1/(4n+2)=n/(2n+1)$$.

For $$n=50$$ which is our case, the right hand side above is $$50/101$$. But we need to subtract $$x_1=1/3$$ because we need to treat the first term multiplicatively, not to lose the largest "higher-order terms", so the sum $x_2+\cdots +x_{50} = \frac{50}{101} - \frac{1}{3} = \frac{49}{303}.$ Now add the term $$1$$ and multiply by $$4/3$$ to see that$\frac{4}{3} \cdot \frac{16}{15}\cdot \frac{36}{35}\cdot \cdots\cdot \frac{10,000}{9,999}\gt \frac{4}{3} \zav{ 1+\frac{49}{303} }.$ I suppose you're able to calculate that the result, the right hand side, is $$4/3\cdot 352/303=1,408/909$$. The final step of the proof requires us to demonstrate that $$1,408/909$$ is still greater (despite the modest generosity with which we reduced the left hand side) than the Supergod threshold $$625/404$$. After we cancel $$101$$ again, we need to show that$\frac{1,408}{9} \gt \frac{625}{4}$ But if we multiply both sides by the denominators, it is equivalent to$4\cdot 1,408 = 5,632\gt 5,625 = 625\cdot 9$ which is indeed the case (although it was a close call). QED. You may try to solve the Megagod challenge. A few tips how to improve the accuracy are mentioned at the Quantum Frontiers blog (mine and other people's tips). However, once your method needs a calculator, you are going in a direction that has no point: after all, using a calculator, you may calculate the exact value rather quickly. ;-)

1. Lumo, do you really mean that you have just won this bounty for solving the Supergod Problem ?
This is soooo cool, I heartily congratulate you :-D !!!
Now you should run for the Milner Prize too ... ;-)

Cheers

2. Yes, I immediately got the money by PayPal, Spiros is generous and honest so if he repeatedly manipulated himself into the bounty, he had to expect and he arguably did expect that one of the winners of the successive games will ultimately take the words seriously. ;-) I had lots of recent extra expenses - more expensive food etc., the supplements - and reduced income due to the yeast beast.

3. cool solution, glad to see you're still smarter than the average russian middle schooler ;-)

What do you think the 2 line proof that spiros mentions Aleksander Kubica showed them for the product less than 1/10 is?

4. Thanks, James. I think that when one omits justifications and pedagogical extra comments, the most streamlined derivation by Anthony may already be squeezed to 2 lines. The first line rewrites the original inequality as 4/3*16/15...*10000/9999 is greater than (some fraction, depending on the difficulty). The second line calculates the product of the first three factors as a rational number and shows that it's indeed greater.

The Supergod challenge solution can't be squeezed to 2 decent lines, I think.

6. I guess something like that, in fact A < B is pretty trivial (compare factors A=(1/2)(3/4)...(99/100) B=(2/3)(4/5)...(100/101)), so combined with AB=1/101< (1/10)^2 is enough for the A < (1/10) estimate.

Spiros made it sound like he really did something unusual ("he barely escaped with his life!")

7. I thought that "he barely escaped with his life" simply meant "he barely squeezed those things into the two lines, otherwise he would probably have to commite harakiri".

8. I was going for hyperbole... Once we saw how simple the proof was (as James demonstrated above), we wanted to take back the hour we spent trying all kinds of "brilliant" approaches... Of course, the truth is that we all enjoyed the challenge!

For me the best person to target for having fun being a physicist fan and for befriending a Milner millionaire, all in one, is not Witten (mainly because he not witty enough) but Motl. :-)

10. Hi Lumo,

Great post; I enjoyed reading it, and I can understand the math :-)

It's usually called a "telescoping" sum (not telescopic).

11. Brian G ValentineOct 14, 2012, 6:45:00 AM

Taking the log of the LHS we have

log(1 - 1/2) + log(1 -1/4) +...+ log(1 -1/100)

and using the well-known (?) inequalities

log x ≤√x – 1/√x for all x

and

(sum on √n from 1 to k) ≤ (2/3) k√k + (1/2)√k

and finally approximating the exponentials by two terms of their expansions does seem to reproduce the result

12. A cute method!

13. Brian G ValentineOct 14, 2012, 8:40:00 AM

$300 for this? Frankly, this isn't as hard as your average PhD candidacy prob in applied math 14. I agree, it would be a nice deal to have it every day. Still, the solution, when it's actually complete with numbers etc. - yours is not, so far - looks cool. I think that its value is at least$300 at the end.

15. Brian G ValentineOct 14, 2012, 9:13:00 AM

Sorry about that for every positive and decreasing f
on 1 ≤ x < ∞ we have

f (n) ≤ (sum on
f (k) from 1 to n) – (integral from 1 to n on f(x)dx) ≤ f (1)

as a result of the integral test for convergence of a
series

16. Hi Lubos, I have a (distantly) related question which you may or may not want to address. In neuroscience it is estimated there may be a trillion neurons, each of which is connected to an average of 10,000 other neurons. I am trying to estimate the number of combinations of a trillion things taken 10,000 at a time. The on-line calculators seems to break down with such large numbers. thanks, Luke

17. Dear Luke, I am not sure what you mean by a "combination" here. The number of combinations in the math sense, ie subsets with 10,000 elements in a trillion-element set, is just 1 trillion choose 10,000 which is "just" 1 trillion to the 10,000th power or so, or 10^{120,000}. However, this has no implications for types of brains or states of the brain because the 1 trillion neurons to start with are more or less indistinguishable. The number of trees how you can connect 1 trillion neurons so that the number of links per neighbor is at most 10,000 is much larger still. For any conceivable purpose, it is infinite. An estimate is: each neuron has to make 10,000 choices, each of which has 1 trillion types, so it's 1 trillion to the power of 10,000 to the power of 1 trillion which is 1 trilion to 120,000 trillion which is 10^{12 * 1,2e17) - about 10^{10^{18}}, close to the "googolplex" type of numbers.

18. Thanks. I'm not sure what I meant either, exactly. I was vaguely wondering about how many conscious brain states there might be in order to account for the amazing number of experiences we can remember in the course of navigating through life. (In old age you have a lot of memories!) To say nothing of recognizing and identifying and interpreting all the stuff in our ever-changing surroundings.

I've read that "neurons that wire together fire together" and that the brain cycles around 100 times a second. Assuming that the collection of neurons that are firing at any one instant represents a state, I was wondering how many states (combinations?) there might be. I would imagine it is a trans-astronomical number -- maybe even bigger than the number of possible "solutions" in the string-theory landscape.

I suppose one way to estimate the number of neurons firing at any given instant would be to measure the total rate of metabolism and divide by the energy consumed by the average firing of a single neuron. Those fMRI images show which parts of the brain are lighting up but don't really tell us very much. Not enough temporal or spatial resolution.