Mathematicians have long noticed that in many fields, theorems have exceptions for small integers. Some theorems for compact differentiable manifolds can be proved for n bigger than 4, but things go haywire for 1, 2, 3, 4, especially 4. The finite simple groups have all been classified as being in one of several infinite families, with a finite list of exceptions, the largest being of order less than 10^54. (Well, that is small relative to most numbers!) The largest exceptional Lie group is a manifold of dimension 248.
Perhaps math gets better behaved for very large integers. This suggests a conjecture:
THE BIG NUMBER CONJECTURE CONJECTURE (sic)
If P(n) is a mathematical statement with one free variable n that ranges over the positive integers, then there is a number B_P depending only on the form of P with the property that, in order to prove that P(n) is true for all positive integers, it is sufficient to prove P(n) for all positive integers less than B_P.
Remarks:
a) This is precisely a conjecture that a meaningful conjecture exists.
b) The BNC is not a proper conjecture until I define “mathematical statement” precisely. Anyway, it may be true for some forms of statements and not others.
c) B_P has to depend on P because you could replace P(n) by P(f(n)) where f(n) is some slow growing function, such as the greatest integer in log log n.
d) But the dependence of B_P on P must be on the FORM of P in some sense (number of quantifiers or some such thing). Otherwise the conjecture is trivially true.
Send to Kindle
Note from Ilya Zakharevich (posted by Charles Wells)
Note that it is manifestly true when “the complexity” is of the form
of the length of the statement of the conjecture. (Since there is
only a finite number of statements of length < = L, there number of
“minimal counterexamples” is finite as well, so there is an upper bound.)
So the questions of the limit being calculatable should also enter the
conjecture.
So the questions of the limit being calculatable should also enter the conjecture.
Unfortunately, that can’t be true in full generality. Suppose P belongs to some class of statements for which there is an algorithm that decides the truth of each individual statement P(n) but so that there is no algorithm that decides whether such a statement holds for all n. Then there can be no algorithm to compute the bound B_P.
One example of such a class comes from the halting problem: suppose we choose a Turing machine P that takes no input, and let P(n) denote the statement that P runs for at least n steps without halting. For any specific n this can easily be checked, but no algorithm can determine whether a arbitrary Turing machine eventually halts.
There is a quickly growing body of mathematical work which is recently often referred to as “high-dimensional phenomena” in which all the content is quite counter to the philosophy of this conjecture. Typically one is studying some phenomenon in n-dimensional space (although n may be some other parameter, like the number of vertices of a graph) where n is finite but very large. The results one is interested in are inequalities between geometric quantities which, for each n, are known to be bounded above and below; and constants independent of n whose values are not necessarily known.
The point is that these inequalities are trivial to prove for all small n (where “small” can mean smaller than any constant you choose) simply by picking the constants appropriately. But the statement that there exist some choices of constants which make such an inequality true for all n simultaneously can be very nontrivial.
The comments by Anonymous and Mark Meckes mesh with the ideas in the article by Ian Stewart, How hard can it be?, in New Scientist, issue for June 21-28, pages 46ff. The gist is that the n-stamp problem is solvable in polynomial time for each n, but the general problem for all n is NP-complete.
There may be some wiggle room for the big number c.c., which says that a statement is true if it is true for large enough n, where “large enough” depends on the statement. The results mentioned in the comments and in Stewart’s article talk about the difficulty of proof for all n. But not much wiggle room, since the results suggest that the big number c.c. will be horribly difficult to prove…
To consider in what forms the BNCC might be true it’s worth considering how the types of theorems cited in the post (to do with, say, n-dimensional topology) are different from the types of theorems I alluded to (to do with, say, quantitative n-dimensional convex geometry). In particular, the quantifiers are different. Namely, the original post was about theorems that say things like, “for every n, for every n-dimensional manifold M, P(M)”.
On the other hand, the kinds of theorems I am talking about say things like, “there exists C>0 such that for every n, for every n-dimensional convex body K, P(C,K)”. With respect to this formulation, what I said in my last post is that it is typically trivial to prove that “for every n there exists C>0 such that for every n-dimensional convex body K, P(C,K)”. The hard part is showing that the first two quantifiers can be transposed.
It seems to me that the existential quantifier at the beginning means that the results I’m talking about don’t really fit into the format discussed in the post. This is why I only said that these results run counter to the philosophy of the BNCC; I don’t think they’re really counterexamples to (a suitably precise interpretation of) it.
Incidentally, that existential quantifier and the first universal quantifier are often buried in this area. The results are typically stated in the form “for every n-dimensional convex body K, P(C,K)”, often but not always followed with “where C is a constant independent of K and n”. I’ve seen this create confusion among general mathematical audiences going to talks on the subject many times.
Unfortunately this conjecture is false. Consider the statement over the natural numbers
S = forall n, P(n)
where S is undecidable and P(n) has no quantifiers. Obviously there is no natural number n for which P(n) is false, otherwise S would be easy to prove false but (by assumption) S is undecidable. So S is in fact true, as a statement about the natural numbers. But obviously there is no particular N such that showing P(n) for n<=N will suffice to establish S, since after all *nothing* can establish S. (At least, not in the axiomatic system relative to which S is undecidable.)
PS Hi Dr. Wells, glad to see you blogging! Brings back fond memories of your classes.