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:

${\bullet }$ The first is a proof of irrationality due to W. H. Schultz.

Theorem: If ${n \ge 3}$, then ${ \sqrt[n] 2}$ is irrational.

Proof: Suppose ${ \sqrt[n] 2 = x/y}$ for some positive integers ${x}$ and ${y}$. Raising to the ${n^{th}}$ power yields, ${2 = x^{n}/y^{n}}$, and thus

$\displaystyle y^{n} + y^{n} = x^{n}.$

But, this contradicts Fermat’s Last Theorem, proved by Andrew Wiles.

$\Box$

${\bullet }$ The second is a proof there are non-planar graphs of arbitrary size.

Theorem: For each ${n}$ large enough, there is an ${n}$ vertex non-planar graph.

Proof: Let ${G_{n}}$ be a random graph on ${n}$ vertices with edge probability ${p=1/2}$. The chromatic number ${\chi(G_{n})}$ is known with high probability to be,

$\displaystyle \left(1/2 +o(1) \right) \log 2 \frac{n}{\log n}$

by a famous theorem of Béla Bollobás. However, by the Four Color Theorem all planar graphs can be colored in ${4}$ colors. Since

$\displaystyle \frac{n}{\log n} \rightarrow \infty$

as ${n \rightarrow \infty}$, the theorem follows. $\Box$

${\bullet }$ 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

$\displaystyle p_{1} < \dots < p_{m}$

for some finite ${m}$. Then, consider the following algorithm for finding a factor of a number ${N}$.

1. If ${N=1}$, the algorithm stops.
2. For all ${i = 1,\dots,m}$ check if ${p_{i} = N}$. If yes, then ${N}$ is prime, the corresponding ${p_i}$; the algorithm stops. If not, ${N}$ is composite, proceed to the next step.
3. For all ${i=1,\dots,m}$ check if ${p_{i}}$ divides ${N}$. Since ${N}$ is composite, one of ${p_i}$‘s has to divide ${N}$. Output that ${p_i}$ and stop.

$\Box$

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.

March 31, 2010 10:07 pm

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.

April 1, 2010 2:58 am

I like this one even better!

April 1, 2010 6:50 am

Thanks.

2. March 31, 2010 10:48 pm

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🙂.

April 1, 2010 6:47 am

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.

April 1, 2010 11:37 am

Oops, K(N) = O(log log N) and K(n) = Omega(log N), respectively.

4. April 1, 2010 9:53 am

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.

April 3, 2010 10:59 pm

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?

• April 4, 2010 6:01 pm

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}}

April 1, 2010 11:20 am

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.

April 1, 2010 1:04 pm

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.

6. April 1, 2010 10:26 pm

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

7. April 3, 2010 2:49 am

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.

• August 15, 2011 8:06 am

That’s y this is about april fool~

April 5, 2010 8:30 am

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.

April 6, 2010 10:13 am

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.

April 6, 2010 12:55 pm

Great…thanks Bill

April 30, 2010 2:46 am

Very interesting

July 11, 2010 8:44 am

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.