Happy April Fool’s Day
Faadosly Polir, is the older brother of Lofa Polir—you may recall she claimed a great result on factoring last year. She is still working out the details of her result, but she is also, I hear, working on a variety of other problems from complexity theory.
Today I want to talk about a concept Faadosly as has invented: AFR’s. I will shortly define them, and present a few examples. I hope you can help him collect some additional ones. I understanding he is planning a book, and he would like to have as many examples as possible.
An AFR is an April Fool Result: a proof of a simple mathematical fact using much harder mathematics than needed. It is using sledge hammer to break a toothpick, or a blowtorch to light a candle. Here are three examples:
The first is a proof of irrationality due to W. H. Schultz.
Theorem: If , then is irrational.
Proof: Suppose for some positive integers and . Raising to the power yields, , and thus
But, this contradicts Fermat’s Last Theorem, proved by Andrew Wiles.
The second is a proof there are non-planar graphs of arbitrary size.
Theorem: For each large enough, there is an vertex non-planar graph.
Proof: Let be a random graph on vertices with edge probability . The chromatic number is known with high probability to be,
as , the theorem follows.
The last is a proof there are an infinite number of primes—based on a standard complexity assumption.
Theorem: There are an infinite number of primes, if integer factorization requires super-polynomial time.
Proof: Suppose all the primes are
for some finite . Then, consider the following algorithm for finding a factor of a number .
- If , the algorithm stops.
- For all check if . If yes, then is prime, the corresponding ; the algorithm stops. If not, is composite, proceed to the next step.
- For all check if divides . Since is composite, one of ‘s has to divide . Output that and stop.
The main open problem is to have a fun April Fool’s day. If you have any interesting AFR’s let me know what they are, and I will pass them on to Faadosly.