Archive for September 6th, 2012

EDP26 — three generalizations

September 6, 2012

This short post is designed as a possible way in to EDP for anyone who might be interested in participating but daunted by the idea of reading large amounts of material. One of the natural strategies for proving EDP is to try to formulate and prove stronger statements. At first that sounds paradoxical: isn’t it even harder to prove a stronger statement? But the answer to that question is often no. To give a slightly silly example, suppose you were asked to prove that for every c>0 there exists N such that for every n\geq N if n is odd and has at least c\log n prime factors (counted with multiplicity), then 2^{\phi(n)}\equiv 1 mod n, where \phi is Euler’s totient function. You could make the problem easier by proving Euler’s theorem, that a^{\phi(n)}\equiv 1 mod n for every n and every a that is coprime to n. You wouldn’t have as many hypotheses to use, but that’s good, since they can’t be used. Perhaps a better and more relevant example is when you generalize the class of numbers you are working with so as to allow a wider set of methods. For instance, suppose you want to prove that the largest possible product of three positive integers that add to 300 is at most 10^6. If you replace positive integers by positive reals, then you suddenly have available methods that you didn’t have before — for example, you could use compactness plus a lemma that says that if any two numbers are not equal then you can increase the product by replacing both of them by their average. (I’m not saying that’s the easiest proof — just that it’s a proof that you can’t do without first generalizing the statement.)