April Fool
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.
AFR
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:
Theorem: If
, then
is irrational.
Proof: Suppose ![{ \sqrt[n] 2 = x/y}](https://s0.wp.com/latex.php?latex=%7B+%5Csqrt%5Bn%5D+2+%3D+x%2Fy%7D&bg=ffffff&fg=000000&s=0 "{ \sqrt[n] 2 = x/y}")
But, this contradicts Fermat’s Last Theorem, proved by Andrew Wiles.
Theorem: For each
large enough, there is an
Proof: Let 
by a famous theorem of Béla Bollobás. However, by the Four Color Theorem all planar graphs can be colored in 
as 
Theorem: There are an infinite number of primes, if integer factorization requires super-polynomial time.
Proof: Suppose all the primes are
for some finite 
- If
, the algorithm stops.
- For all
check if
. If yes, then
; the algorithm stops. If not,
- For all
check if
divides
Open Problems
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.
Trackbacks
- The Top 10 April Fool’s Day Hoaxes of All Time | Gearone.in
- Tachoblog » Archives » Scoop! No More Smelly Exhaust Fumes Thanks To Aromatab – The Tacho Blog
- pet tax « Hot News
- Top Posts — WordPress.com
- Google April Fool Jokes | Hot Daily Gossip
- Matando moscas a cañonazos | Gaussianos
- Wiskundemeisjes » Blog Archive » Eén-april-resultaten
- Mersenne number | MathFax.com
- Interstellar Quantum Computation | Gödel's Lost Letter and P=NP
- Wait Wait… Don’t Fool Me! | Gödel's Lost Letter and P=NP
- April Fool | Gödel's Lost Letter and P=NP
In the spirit of the your final example:
Theorem: There are an infinite number of primes, assuming the Goldbach Conjecture.
Proof: Suppose there are only finitely many primes, and let p be the largest prime. Then 2p+2 is not the sum of two primes.
I like this one even better!
Thanks.
Similarly, it follows from the odd Goldbach conjecture (proved by Helfgott): if $p$ is the largest prime, then $3p+2$ is not a sum of 3 primes. https://en.wikipedia.org/wiki/Goldbach%27s_weak_conjecture I guess one would have to go through the proof though and maker sure that it does not use the infinitude of primes in order for the reasoning not to be circular.
Faadosly Polir himself might come rather close, if the criterion is
length of proof of the theorem being employed
——————————————————— .
length of the (rest of the proof) of the new result
Is the classification of finite simple groups still the record-holder for the numerator? Then, are there algorithms that run in polynomial time (or yea-time) on account of the finiteness of the sporadic cases? I couldn’t immediately tell whether anything like this was implicit in this paper with Polir as 2nd author, but maybe you can ask him :-).
Theorem. There is an infinite number of primes.
Proof. Suppose by contrary that the set of primes is {p1, p2, …, pk}. Then each integer N can be encoded as a tuple (a1, a2, …, ak). Thus, the Kolmogorov complexity K(N) = O(k log N), but there are integeres such that K(N) = Omega(N). QED.
Oops, K(N) = O(log log N) and K(n) = Omega(log N), respectively.
If N photons are sent through an interferometer, each registering a “0” or “1”—depending on whether the photon “click” is registered on the up or down photo-diode—then the Kolmogorov complexity of almost all data records will be O(N); therefore observed quantum mechanical systems exhibit random dynamics. QED
Notes: (1) N~10^{16} in typical experiments, (2) The randomness in von Neumann-style projective models of quantum measurement can be analyzed emergently, as a coarse-grained approximation to fine-grained Kolmogorov randomness.
John — I am familiar with Kolmogorov complexity, but not with the phenomenon you describe. Could you give a reference to how “von-Neumann style projective models can be analyzed as a coarse-grained approximation to fine-grained Kolmogorov randomness,” and what exactly this all means?
Josh, regarding coarse-grained versus fine-grained descriptions of quantum measurement, I want to warn you in advance that the literature is long on lengthy statistical calculations, and short on snappy philosophical insights.
One approach is to reflect that in classical dynamics—both in the abstract and in practical simulation codes—thermodynamical laws are coarse-grained approximations to fine-grained stochastic processes. Classical simulationists call these processes “thermostats” (and there is a vast literature on them).
In the quantum domain, the thermostat processes are called a Lindblad process (and there is a vast literature on them). Carlton Caves has some nice on-line notes on the stochastic properties of Lindblad processes; the BibTeX is appended.
Just is it is feasible-but-kinda-boring to work out thermodynamical laws arise as the coarse-grained limit of fine-grained stochastic dynamics, it is feasible-but-kinda-boring to show that von Neumann quantum projective measurements arise as the coarse-grained limit of fine-grained quantum Lindblad processes. Our quantum system engineering group has an article that works through the details in the on-line journal New Journal of Physics (BibTeX appended).
So where’s the excitement, the mystery, the mathematical challenge in quantum measurement? Well, if you asked a dozen researchers, you’d likely get a dozen differing answers!
But here is one emerging direction that *I* like to think about. Classical (quantum) simulationists expend a lot of energy pulling-back from large-dimension Newtonian (Hilbert) state-spaces onto lower-dimension curvilinear (Kählerian) state-spaces.
A paradigmatic example of curvilinear classical state-spaces are bond-angle spaces of molecular dynamics; of curvilinear quantum state-spaces is a tensor network state-space. A paradigmatic example of classical dynamical pullback onto a low-dimension state-space is a thermostatic process; of quantum pullback is a Lindblad process. A paradigmatic example of a large-scale classical numerical algorithm is SHAKE; of a large-scale quantum algorithm is DFT.
In both the classical and the quantum cases, simulation accuracy and efficiency improves every year … with no obvious end in sight.
Gosh … this makes classical and quantum simulation seem very much alike … so what’s the difference between them? Well, one big difference is that Newtonian space is only approximately Euclidean … as we know from general relativity. Whereas, Hilbert space is (axiomatically) Euclidean … and we know that it is physically Euclidean from … from … from … well … we don’t *actually* have all that much evidence that the state-space of QM is exactly Euclidean … we know only that it is approximately Euclidean.
This is where the main physical mystery, and the key mathematical challenges, and the engineering opportunities of QM, all three reside. The mystery is, is QM Euclidean? That math challenge is, how can we formulate QM—field theory especially, but fermions are tough too—on non-Euclidean state-spaces? The engineering challenge is, how can we carry through these calculations efficiently and accurately for biological and nanoscale systems … in the quantum, classical, and hybrid domains?
It is pretty much impossible to work on any one of these three “big” QM questions without working on the other two also … that’s why it’s fun!
——-
@unpublished{Author = {C. M. Caves}, Note = {On-line memorandum to C. A. Fuchs and J. Renes: \url{http://info.phys.unm.edu/~caves/reports/lindblad.pdf}}, Title = {Completely positive maps, positive maps, and the\ {L}indblad form}, Year = 2000}
@article{Journal = {New Journal of Physics}, Number = {6}, Pages = {065002 (96pp)}, Title = {Practical recipes for the model order reduction, dynamical simulation, and compressive sampling of large-scale open quantum systems}, Volume = {11}, Year = {2009}}
Theorem: In any sufficiently large group of people, there will be two people who are either friends or not friends.
Proof:
Represent each person in the group by a vertex, and let there be an edge between two vertices iff the corresponding people are friends. By Ramsey’s theorem, for a sufficiently large number of vertices, there will either be a clique of size 2 in the graph or an independent set of size 2. Our theorem follows.
Very cool proof. May I add you could have used the Paris-Harrington version of Ramsey. Since this theorem cannot proved in Peano, your proof would lie outside Peano arithmetic.
Though the invocation of Fermat’s last theorem for irrationality of $\sqrt[n]{2}$ and Goldbach’s conjecture for infinitude of primes clearly steal the ball – which makes this proof seem dwarf in comparison of its AFRity – here is another AFR for infinitude of primes.
We know that Bertrand’s postulate is true and therefore there is a prime between $n$ and $2n$ for all $n \in \N$; there is clearly an infinite number of those
Isn’t it possible to have circular proofs?
The advanced results have to use some basic results. Maybe one of them are built upon the proof that there are infinite number of primes.
That’s y this is about april fool~
I can’t stop laughing at the planar graph one.
ilyaraz: As matter of fact i liked your proof very much. Existence of uncompressible strings is derived using simple counting afterall.
See
http://blog.computationalcomplexity.org/2008/08/ridiculously-hard-proof-of-easy-theorem.html
for the story of a high school student who seriously proved that their are an infinite number of primes
by invoking the Greene-Tao theorem. This theorem states that there are arb large arithmetic sequences of
primes.
Great…thanks Bill
Very interesting
If number of prime is finite then #{p<=x:p is a prime} is bounded .
So #{p0 as x–> infinity ,which contradicts prime number theorem.
http://mathoverflow.net/questions/42512/awfully-sophisticated-proof-for-simple-facts
AFRs have useful purpose outside of the april fool’s joke. It shows that a sophisticated theorem is a generalization of a basic fact! This purpose remain useful even if the proof is circular, e.g., in algorithms and complexity theory, this is used for understanding a problem.
A supporting example of my comment above is proving the linear programming duality using the existence of Nash Equilibrium. Nash’s theorem uses a more sophisticated machinery of fixed point theorem. LP duality can be proven by using elementary math (essentially using Gaussian elimination, which gets introduced in high school).
This indirect proof of LP duality gives us some understanding of zero sum games and also makes the Nash theorem more intuitively believable, and also demonstrates how randomization is helpful, which is somewhat equivalent to fractional relaxation in the setting.