43
$\begingroup$

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.

Improve this question
$\endgroup$

13 Answers 13

Reset to default
36
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Very interesting. Can you give a reference for the unprovability of the graph minor theorem in first-order Peano arithmetic? $\endgroup$
    – Tony Huynh
    Commented Jun 12, 2010 at 23:26
  • 1
    $\begingroup$ See the article "The metamathematics of the graph minor theorem" by Friedman, Robertson, and Seymour" in Logic and Combinatorics (Contemporary Mathematics, Vol. 65, AMS 1987). $\endgroup$
    – John Stillwell
    Commented Jun 12, 2010 at 23:58
26
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ Interesting - do you know any good expositions of these examples? $\endgroup$
    – Thomas Bloom
    Commented Jun 13, 2010 at 16:33
  • 1
    $\begingroup$ The examples are Dirichlet series with an analytic continuation and functional equation resembling those of zeta-functions, but provably having zeros in the critical strip that are off the critical line. A key point here is that these series do not have any kind of expected Euler product decomposition; the Euler product should be considered an essential structure for those (interesting) cases where RH ought to hold. A concrete example is based on $Z(s) = \sum_{(x,y)} 1/(x^2 + 5y^2)^s$, the sum running over integer pairs other than (0,0). The series converges for Re($s$) > 1 and (contd.) $\endgroup$
    – KConrad
    Commented Nov 16, 2012 at 6:47
  • 1
    $\begingroup$ the function $V(s) = 20^{s/2}(2\pi)^{-s}\Gamma(s)Z(s)$ has an analytic continuation to ${\mathbf C} - \{0,1\}$ and we have the functional equation $V(1-s) = V(s)$. The function $V(s)$ has zeros in the critical strip that are off the critical line (proved in 1935 by H.S.A. Potter and Titchmarsh; the initial H is short for Harold, so you could consider him to be Harry Potter). $\endgroup$
    – KConrad
    Commented Nov 16, 2012 at 6:50
23
$\begingroup$

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.

Improve this answer
$\endgroup$
18
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Very interesting! Makes you wonder about tropical examples along the same lines. $\endgroup$
    – Victor Protsak
    Commented Jun 13, 2010 at 3:56
  • $\begingroup$ This is very cool. $\endgroup$
    – Bart Snapp
    Commented Jun 14, 2010 at 0:56
11
$\begingroup$

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.

Improve this answer
$\endgroup$
10
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is statement B true? $\endgroup$
    – Sune Jakobsen
    Commented Nov 16, 2012 at 20:50
  • 2
    $\begingroup$ Yes. (Bang's theorem: No convex body of width $1$ (in any dimension) can be covered by strips of total width less than $1$). There are many "generalizations" and "applications" but I wouldn't say we know everything there, far from it. It is not even known if making a tiny hole near the center of the disk makes any difference in this covering problem. :-) $\endgroup$
    – fedja
    Commented Nov 16, 2012 at 21:46
10
$\begingroup$

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 Solovay) 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-Solovay theorem on Terence Tao's blog, here.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ As someone who doesn't know much about this field, but finds your statement intriguing, is there any chance you could amplify on your reply for non-specialists. $\endgroup$
    – Dan Piponi
    Commented Jun 12, 2010 at 22:07
  • 1
    $\begingroup$ I'm very much a nonspecialist myself but have expanded on the answer. $\endgroup$
    – Akhil Mathew
    Commented Jun 13, 2010 at 0:08
8
$\begingroup$

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.

Improve this answer
$\endgroup$
8
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ An example suitable for freshmen is the ODE $y'=y^{1/3}$ that has non-unique solutions. This motivates Peano's existence theorem, whose proof is non-constructive in that it uses Arzela-Ascoli theorem (in view of non-uniqueness, we don't expect to obtain a "canonical" solution in the course of the proof). $\endgroup$
    – Victor Protsak
    Commented Jun 13, 2010 at 12:34
8
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 5
    $\begingroup$ One possible reason for the surprise is that if one begins with the integers and thinks about the construction of the reals from it then the unboundedness is crystal-clear. That is, the need to appeal to completeness comes about only if we treat the reals as a black box, and those who are surprised may not have been doing this. An analogue is the fact that there are no integers strictly between 0 and 1. By "classical" induction or construction it is crystal-clear, but if we allow the well-ordering principle and not "classical" induction then it becomes a bit more contorted to prove this. $\endgroup$
    – Boyarsky
    Commented Jun 20, 2010 at 4:00
  • $\begingroup$ @Boyarsky, what proof do you have in mind? Granted only WOP (which I suppose means here that the positive integers are well ordered?), I would let $n$ be the least positive integer, and observe that, were it between $0$ and $1$, then $n^2$ would be smaller. $\endgroup$
    – LSpice
    Commented Feb 5, 2019 at 22:54
8
$\begingroup$

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.

Improve this answer
$\endgroup$
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 12
    $\begingroup$ But the very same failure does make the infinitude of primes obvious (granting basic commutative algebra, none of which depends on infinitude of primes), since a Dedekind domain with finitely many primes is a PID by Chinese Remainder Theorem! (This incredible argument is due to Larry Washington.) $\endgroup$
    – Boyarsky
    Commented Jun 20, 2010 at 4:03
3
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .