Examples of statements that provably can't be proved using a promising looking method - MathOverflow

Examples of statements that provably can't be proved using a promising looking method

2010-06-12T12:56:50Z

Motivation: In Razborov and Rudichs article "Natural proofs" they define a class of proofs they call "natural proofs" and show that under certain assumptions you can't prove that $P\neq NP$ using a "natural proof". I know that this kind of results is common in complexity theory, but I don't know any good examples from other fields. This is why I ask:

Question: Can you give an example of a statement S that isn't known to be unprovable (it could be an unsolved problem or but it could also be a theorem), a promising-looking class of proofs and a proof that a proof from this class can't prove S.

I'm interested in both famous unsolved problems and in elementary examples, that can be used to explain this kind of thinking to, say, freshmen.

Answer by Thomas Bloom for Examples of statements that provably can't be proved using a promising looking method

2010-06-12T15:18:08Z

One example is Roth's theorem: that any set of integers with positive density contains an arithmetic progression of length 3. This has been proven now in several different ways (usually using Fourier analysis) but one might hope for a more elementary proof.

That is, just by applying Cauchy-Schwartz and the pigeonhole principle in clever ways one can often prove quite a lot about the additive structure of sets. Behrend's example, however, gives a set in $[1,N]$ of size $$>cNe^{-O(\sqrt{\log N})}$$

for some constant $c>0$ with no arithmetic progressions of length 3. In the words of Tao and Vu (Additive Combinatorics, Exercise 10.1.4),

This rules out a number of elementary approaches to proving Roth's theorem or Szemeredi's theorem (e.g. arguments based entirely on Cauchy-Schwarz and pigeonhole principle type arguments) as these tend to only give polynomial type bounds.

Answer by Timothy Chow for Examples of statements that provably can't be proved using a promising looking method

2010-06-12T16:10:17Z

The fact that Fermat's Last Theorem is false over the $p$-adics shows that it cannot be proved using arguments using congruences.

The fact that the Steiner-Lehmus Theorem is false over the complexes shows that it cannot be proved using what John Conway calls "equality-chasing" arguments.

This one is probably not explainable at the freshman level but the fact that the Paris-Harrington theorem and the Robertson-Seymour graph minor theorem are not provable in first-order Peano arithmetic shows that some kind of "infinitary" reasoning or sophisticated induction is needed to prove them.

Answer by darij grinberg for Examples of statements that provably can't be proved using a promising looking method

2010-06-12T19:10:10Z

The inequality $x\left(x-y\right)\left(x-z\right)+y\left(y-z\right)\left(y-x\right)+z\left(z-x\right)\left(z-y\right)\geq 0$ for all nonnegative reals $x$, $y$, $z$ (a particular case of Schur's inequality) cannot be proven by substituting $x=A^2$, $y=B^2$, $z=C^2$ and writing the left hand side as sum of squares of polynomials. This is the reason why Hilbert's 17th problem needs squares of rational functions rather than squares of polynomials.

Answer by Akhil Mathew for Examples of statements that provably can't be proved using a promising looking method

2010-06-12T22:04:40Z

The fact that there exist oracles $A,B$ such that $P^A = NP^A$, $P^B \neq NP^B$ (a theorem of Baker, Gill, and Soloway) implies that the $P=NP$ question cannot be resolved using "standard" methods (because they would relativize to any oracle).

Edit: Most of the methods used to prove inequalities of complexity classes (e.g. diagonalization in the proof of the space and time hierarchy theorems) work even if the model of computation is changed to allow for one bit of computation to become "free" (i.e. if the Turing machine can access an oracle). The fact that such standard "relativizing" methods cannot suffice (by this theorem) to prove either $P=NP$ or its negation is taken as evidence that $P=NP$ is a nontrivial, serious question. The same is true for $NP$ versus $coNP$. Incidentally, it is true that $P^A \neq NP^A$ relative to a random oracle (where "random oracle" means that membership of any string in $A$ is decided randomly) with probability 1,* though this does not mean that $P \neq NP$.

An example of a nonrelativizing method is the arithmetization of boolean formula (which converts a boolean formula to a polynomial which is nonzero at an assignment of the variables to zeros and ones iff the formula is satisfiable with those as the corresponding inputs), used in the proof of Shamir's theorem that $IP=PSPACE$, a fact not true relative to arbitrary oracles.

*The probability has to be zero or one by Kolmogorov's zero-one law, incidentally.

There is a very interesting discussion of the Baker-Gill-Soloway theorem on Terence Tao's blog, here.

Answer by Timothy Chow for Examples of statements that provably can't be proved using a promising looking method

2010-06-12T22:14:48Z

The statement, though unfortunately maybe not the proof, of Wilkie's solution to Tarski's high-school algebra problem, is certainly accessible to freshmen.

Answer by John Stillwell for Examples of statements that provably can't be proved using a promising looking method

2010-06-13T00:16:05Z

Like the graph minor theorem, which has already been mentioned, Kruskal's tree theorem cannot be proved by finitary methods. Also, it has a somewhat simpler statement (because it involves embedding rather the graph minor relation):

Any infinite sequence of trees contains an infinite monotonic subsequence, under the embedding relation.

This statement can surely be explained to freshmen. The fact that it is unprovable by finitary methods is quite subtle however, because the fact that the statement involves an arbitrary infinite sequence means that the theorem cannot even be stated in Peano arithmetic. There are ways around this, such as "Friedman's finite form" of Kruskal's theorem.

Answer by Terry Tao for Examples of statements that provably can't be proved using a promising looking method

2010-06-13T10:10:31Z

When solving an initial value problem for a PDE, with initial data in some function space class, one popular way to proceed is to apply the contraction mapping (or Picard iteration) method in a suitable function space (usually one related to the function space that the data is in). When this works, this usually gives local or global existence of the solution, as well as uniqueness (if one restricts the class of solutions to an appropriate function space), and continuous (in fact, Lipschitz and analytic) dependence on the initial data (in certain metrics).

However, for some equations it is known that (Lipschitz or analytic) continuous dependence or uniqueness fails at certain regularities. As such, this precludes the possibility of using Picard iteration to build solutions at that regularity, even if existence of the solution can be obtained by other means.

This is particularly the case for "supercritical" equations in which the regularity provided by the various a priori controlled quantities is too weak. Unfortunately, this class of equations includes important examples such as three-dimensional Navier-Stokes, which is a large reason as to why the global regularity problem for this equation is considered hard (see my blog post http://terrytao.wordpress.com/2007/03/18/why-global-regularity-for-navier-stokes-is-hard/ for more discussion).

Answer by Terry Tao for Examples of statements that provably can't be proved using a promising looking method

2010-06-13T10:22:08Z

There are examples (possibly due to Hecke?) of zeta-like functions which obey almost all of the known properties of the Riemann zeta function, such as the functional equation, Euler product, and asymptotics at infinity, but which have nontrivial zeroes off the critical line. This strongly indicates that one cannot hope to prove the Riemann hypothesis purely by complex analytic methods; at some point, one needs to use something more about the integers than just the fundamental theorem of arithmetic (encoded here as the Euler product), the Poisson summation formula (encoded here as the functional equation), and asymptotic distribution in the reals (encoded here as asymptotics of zeta).

In a related spirit, there are examples (due to Diamond, Montgomery, and Vorhauer) of Beurling integers (generated by a set of Beurling primes, which have asymptotic distribution similar to that of the rational integers) whose zeta function either has non-trivial zeroes or fails to be analytically continued beyond the classical zero-free region. Admittedly this example does not have the functional equation, but it does seem to indicate that multiplicative number theory methods alone are insufficient to resolve the Riemann hypothesis.

EDIT: It turns out that my first paragraph here is based on outdated information. It is currently possible that all functions in the Selberg class (whose members obey all the axioms above, in addition to the Ramanujan conjecture) could obey the RH. I don't know though if anyone is seriously proposing that this much more general conjecture is the right way to attack RH and its relatives, though.

Answer by gowers for Examples of statements that provably can't be proved using a promising looking method

2010-06-13T10:52:10Z

An elementary example is the fact that unique factorization fails in $Z[\sqrt{-5}]$, which shows that there is no obvious proof of the fundamental theorem of arithmetic.

Answer by gowers for Examples of statements that provably can't be proved using a promising looking method

2010-06-13T11:22:37Z

Another elementary example concerns the fact that the integers are unbounded in R. It surprises many people that the completeness axiom is needed to prove that, but one can show that that is the case by finding ordered fields that extend R (e.g. an appropriate ordering on rational functions does the job) where it fails.

Answer by Joel David Hamkins for Examples of statements that provably can't be proved using a promising looking method

2012-11-15T23:55:43Z

Gödel had conjectured that large cardinals might settle the continuum problem. He thought, for example, that perhaps the existence of a measurable cardinal would imply $\neg\text{CH}$. Such a perspective surely gained support with Dana Scott's theorem (1961) that measurable cardinals imply $V\neq L$.

Nevertheless, the Levy-Solovay theorem (1967) shows that measurable cardinals, and all the other large cardinals commonly considered, are preserved by small forcing. Since both $\text{CH}$ and its negation $\neg\text{CH}$ are forceable by small forcing, it follows that measurable cardinals cannot settle the continuum hypothesis.

The general conclusion is that the existence of large cardinals, in principle, cannot settle any set-theoretic question, like CH, whose truth value can be changed by small forcing.

Answer by fedja for Examples of statements that provably can't be proved using a promising looking method

2012-11-16T03:12:51Z

This is an old thread but since it got revived, I like the following completely elementary example:

Statement A: A disk of diameter one cannot be covered by strips of total width less than 1.

Proof: Look at the hemisphere over this disk. The area of the spherical strip is proportional to the width regardless of the position and the trivial area comparison finishes the problem off.

Statement B: An equilateral triangle with altitude of length one cannot be covered by strips of total width less than 1.

One would be certainly tempted to try something similar to the previous approach until he realizes that the proof above also shows that you cannot cover the disk twice by strips of total width less than 2. However it is easy to cover the triangle twice by 5 strips of width 1/3 each.

Answer by Timothy Foo for Examples of statements that provably can't be proved using a promising looking method

2012-11-28T10:07:10Z

Terry Tao has a great post on his blog explaining the limitations of the circle method with respect to the binary Goldbach conjecture.