Why is it that some mathematical problems with seemingly simple statements end up soliciting extremely complicated and groundbreaking proofs or remain unsolved for extended periods of time? (Ex. Collatz conjecture, FLT, Twin prime conjecture, abc conjecture, Legendre's conjecture, etc.) Do they share anything in common?
Asked
Active
Viewed 389 times
3
-
5I strongly disagree with the votes to close. – Noah Schweber Jun 12 '16 at 02:51
-
1Isn't this just a result of statistics - giving a very large number of possible simple problems in mathematics some will be at the far tail of the distribution for complexity. Then add is observation bias - these problems get a lot more attention than other simple problems which aren't complex.. – Ian Miller Jun 12 '16 at 03:48
1 Answers
7
I'm not sure how to answer "Do they share anything in common?" But here's a reason why we'll always find simple conjectures with surprisingly long proofs:
Godel's incompleteness theorem says (among other things) that the set of sentences which can be proved by a fixed "reasonable" set of axioms is never computable. That is, as long as $T$ is a "reasonable" set of axioms, there is no computer program that when fed a sentence $\varphi$ will output "Yes" iff $\varphi$ is a theorem of $T$, and "No" iff $\varphi$ is not a theorem of $T$.
This has an important corollary for the lengths of proofs. Fix some axiom system - say, Peano Arithmetic. Then I claim:
There is no computable function $f$ such that any sentence of length $n$ which is provable in $PA$ has a proof of length at most $f(n)$.
Why? Well, otherwise let $f$ be such a function; to tell if $PA$ proves some sentence $\varphi$, just search through all (finitely many) proofs of length $\le f(\vert\varphi\vert)$. If you don't find one, then $\varphi$ is not a theorem of $PA$!
This means we will always see "surprisingly long" proofs: for example, there will be some theorem of $PA$ which when written down is $n$ characters long, but whose shortest proof in $PA$ has length $$n^{n^{n^{...}}}\quad\mbox{($n^{100000}$-many times)}.$$ Of course, this says nothing$^*$ about how to find such surprisingly hard-to-prove theorems, especially natural examples of same. A kind of mathematical optimism (well, I think it's optimism :P) says that we should always expect natural examples of all possible logical phenomena, but that's not a theorem, that's an opinion (and maybe a silly one at that :P).
$^*$Actually we can effectively generate such examples. But they're really artificial.
Noah Schweber
- 245,398
-
-
3@Colbi There's a ton! Google "proof speedup" or "lengths of proofs" or "proof complexity." I have to go play Super Smash Bros. with my sister now, but I'll add some more links when I get the time. Tl;dr - this is indeed a very cool thing! – Noah Schweber Jun 12 '16 at 02:52
-
@Colbi: Look up Kolmogorov complexity and Chaitin's constant and incompleteness theorem, which are information-theoretic analogues of minimal proof length and Godel's incompleteness theorems. In some sense they are easier to understand and hence it is easier to grasp the intrinsic structure that 'allows deceptively simple mathematical conjectures'. For a geometric example, by encoding Turing machines into square tiles with protrusions, you can construct a finite set of tiles such that whether they can tile some rectangle is equivalent to whether ZFC is inconsistent. [continued] – user21820 Jun 12 '16 at 07:07
-
[continued] Now the set is going to be quite large, but it means that the generalized problem of whether or not an arbitrary set of polygonal tiles can tile a rectangle is deceptively simple but sometimes independent of the formal system, worse than just being hard to prove or disprove! – user21820 Jun 12 '16 at 07:09