Video : Proof theory foundations (2013) by Franck Pfenning [
1 |
2 |
3 |
4 ]
Misleading Patterns in Mathematics
(7:52) by Zach (MajorPrep, 2019年01月04日).
Zero-Knowledge Proof
(33:37) by Avi Wigderson
(Numberphile2, 2021年02月09日).
ZKP: Zero-Knowledge Proof
(10:17) Xavier Decuyper =
Savjee (2019年01月14日).
Zero-Knowledge Proofs
(10:17) by Scott Twombly for CSC555 (2016年04月28日).
An example is no proof. (Yiddish proverb)
In ordinary mathematical discourse, we may say that something is true by inspection when there are only finitely many possible instances and the statement is easily checked for every single one of them.
In the past, we'd only make the claim when there were only a few cases to check; possibly too many to list, possibly a tedious task but not an overwhelming one. In the computer era, we may also claim that something is true by inspection when a (relatively simple) computer program has checked all the possible cases.
Arguably, proper mathematics consists in producing proofs of statements applicable to infinitely many things, not statements true by inspection.
Infinity marks the beginning of proper mathematics.
To a mathematician, proofs are not restricted to mere tests. Arguably, the aforementioned word negative doesn't mean much, since grammatical form is only incidental. To play along, we'll dub the first of the following sentences positive and the second one negative :
Both statements are true in the realm of integers. The first one can be proved by just one example (the most popular of many is 25 = 16+9). On the other hand, the second statement tells that counterexamples do not exist... The evidence for such an affirmation can only be a detailed piece of rigorous reasoning; a proper proof. A lack of solutions can't be established by many failed attempts. That's probably what was meant by whoever coined the above proverb, which doesn't apply to mathematical proofs.
A proof that a cube can't be the sum of two cubes can be given using the Method of Infinite Descent due to Pierre de Fermat (1601-1665). A simpler example of that method is a clever 2-line proof (which repays study) that there's no rational whose square is 2 :
Since 1 < Ö2 < 2, if a positive integer n was making nÖ2 an integer, the smaller positive integer m = (Ö2-1) n would make mÖ2 an integer also! QED
Another proof invokes the concept of divisibility. It may be easier and more intuitive, but it's less elementary (it relies on more previous knowledge).
The elementary type of induction (as taught at the high-school level) pertains to integers: To establish that some statement P(n) is true for all nonnegative integers, you only have to show that:
Although the first part is pleonastic (it's only a special case of the second part with n=0, with a vacuous induction hypothesis) it's useful to keep it, since the proof of the second part would otherwise almost always start with a distinction between n=0 and the other cases.
That type of elementary induction could be reformulated to apply to the elements of any countable set.
However, the general concept of induction (sometimes known as structural induction ) has no such restrictions. Loosely stated:
If something is true of the simplest things and can be shown to hold true of more complex things by assuming it's true of simpler ones, then it holds true of the most complex things.
In this context, it's just assumed that those "most complex things" are structually composed of simpler ones in a predefined way. For example, Conway's surreal numbers are simply built from simpler surreal numbers. Structural induction can thus be used to establish the validity of a statement about all surreal numbers (there are uncountably many of them) in a way that does not reduce to simple induction on integers.
If it probably exists, then it does (4:24) (SackVideo, 2022年07月24日).
One celebrated example is the iterated Rabin-Miller test which tells (beyond the shadow of a doubt) whether a large number is prime or not, without actually proving anything when that number happens to be prime... For a composite number, each iteration stands a substantial chance (over 75%) of proving it's not prime. Thus, if several iterations fail to provide such a proof, we may be very confident that the number is indeed prime (the probability of error decreases exponentially with the number of iterations).
Another example consists in determining whether a (large) finite group is cyclic (knowing the factorization into primes of its order). A finite group is cyclic if and only if it has a primitive root. It turns out that a random element of a cyclic group is primitive with a fairly large probability (and it can be proved to be primitive very efficently if the prime factors of the group's order are known). Thus, if many random elements turn out not to be primitive, then the group is "almost surely" not cyclic.
For example, I argue (against the dominant opinion) that there are probably infinitely many Wieferich primes, although only two of them are known (in spite of great efforts to find a third).
A proper heuristic argument is not a hasty generalization. It's actually a strict mathematical proof about a modified problem, where part of the original mathematical structure is substituted with a probabilistic model. Quantitative conclusions from such a model can be enlightening while an exact solution to the original problem remains elusive. This may be construed as "relaxing" some mathematical constraints while retaining the problem's essential aspects.
A good heuristic argument must be supported with convincing justifications of the probabilistic assumptions underlaying the model. A heuristical argument is never foolfproof (or else it would be a proper mathematical proof) but it should be nearly so... The qualifier "heuristic" shouldn't be an excuse for sloppiness !
The accepted heuristic arguments gave the wrong answer for a paradoxical result which has now been proved rigorously: Maier's theorem (1985).
They were able to reduce the general case to 1936 special cases that could not be reliably checked by hand. The fact that a legitimate proof of a major theorem had not been verified by a human being raised eyebrows at the time.
At a more modest level, I once produced (2002年07月08日) a satisfying proof of a long-standing conjecture of mine by reducing it to 1172 very simple computations. In that case, it would have taken only a few hours to do so by hand, but I must confess that I never did. There was no need for that, as I could write a tiny computer program to do it for me.
The fact that I had previously enlisted the help of a computer to find the magic modulus 1171 (and other larger suitable ones) is irrelevant to the final proof. The creativity involved, if you must call it that, resides entirely in the idea that such a modulus might exist.
Such proofs are getting more and more common these days. Admittedly, they ultimately rely on the proper working of a computer. However, the correctness of the computerized procedure has to be established the old-fashioned way. Therein lies the crux of the proof.
The
four-color theorem (historical perspective) by
John J. O'Connor
and Edmund F. Robertson.
Kenneth Appel (1932-2013)
|
Wolfgang Haken (1928-)
Generations of mathematicians have attempted to prove Euclid's fifth postulate of plane geometry from the other four axioms of Euclidean geometry. It is now known that such a proof is not possible. The reason why this is so is rather subtle:
If Euclidean geometry (including the fifth postulate about parallel lines) is at all consistent, then it can serve as a framework to describe other surfaces besides a plane. One such surface is the sphere...
The geometry of the surface of a sphere provides one example where the first four axioms of Euclid are verified with suitable redefinitions of the concepts involved ("points" are actually pairs of diametrically opposite locations and "lines" are great circles). Yet, the fifth postulate is not verified, as all "lines" intersect (there is no such thing as two "parallel" great circles).
Therefore, the fifth postulate cannot be a consequence of the other four. Note that this conclusion can be reached without settling the question of whether the Euclidean postulates are consistent or not. We just note that if they are consistent, then a consistent "model" can be constructed (spherical geometry) where the fifth one is false. Hence, that fifth postulate is truly an independant axiom which may be assumed to be true or false.
In examples of lesser historical significance, similar arguments can be used to rule out some types of proofs for a given statement. For example, "Fermat's last theorem" can be shown to be false within certain "models" (involving beasts like p-adic integers). This shows that it is a so-called global statement whose proof must involve some peculiar property of the rational integers besides ordinary algebra, ordering and divisibility by finitely many prime numbers. The proof must involve something very specific to the integers, like the validity of Fermat's own infinite descent method...
In mathematics, any proven result can be called a theorem. However, that name is best reserved to general results which give rise to interesting proving techniques. Here are a few examples:
The Most Overpowered Theorems (Mathematics Stack Exchange, Nov. 2013)
Inspired by Greg Egan (2018年09月16日) John Baez remarked (2018年09月21日) that the following equality holds when n is below 9.8 1042 but surely fails when it's above 7.4 1043.
[画像: Come back later, we're still working on this one... ]
Greg soon proved that this equality holds if and only if:
n < 15341178777673149429167740440969249338310889 =わ 1.534... 1043
Patterns that eventually fail by John Baez (2018年09月20日).
Famous open problems have always attracted the attention of people poorly equipped to tackle them. Well, the very fact that a problem remains open long enough to become famous shows that almost nobody is up to it!
If you ever find an easy solution to something which has resisted the attacks of the best mathematicians for decades (or centuries) you can be dead sure that you've made a mistake somewhere. Problems with easy solutions get solved before they become famous.
Legend has it that a prestigious mathematics department once entrusted graduate students to fill out a pre-printed form in reply to proposed proofs of Fermat's last theorem, just pointing out the location of the first mistake.
As I received one such claim again in print a couple of days ago. It looked at first like a classical mistake. I was wrong (it was something even more trivial) but the mistake I had in mind is interesting enough to discuss as an example of what not to do. Here we go:
We only have to consider odd values of the exponent n, since a solution for any other exponent beyond 2 would translate into a solution either for exponent 4 (a well-known impossibility) or for such an odd exponent n :
c n = a n + b n (a > 0, b > 0, n ≥ 3 is odd)
In this, c n must be divisible by s = a+b > 1 since, for any odd n :
Let x = a + b - c. We have c = s - x and, by the binomial theorem :
As this sum and its first terms are divisible by s, so is the last term (i = n). That means that x n is divisible by s > 1. (So, x and s aren't coprime.)
Let w be the greatest common divisor of x and s, which is to say that we have two coprime positive integers u and v such that:
x = w u and s = w v (where u < v since x < s).
As we knew both sides of our last equation to be divisible by v w, we may cancel one w and obtain an equation whose two sides are divisible by v:
The last term of the rightmost sum is -u n, which is coprime with v because u is. As v divides its other terms, that sum is coprime with v.
Therefore, the overall divisibility by v (only) proves that v divides wn-1.
The mistake would have been to ignore that possibility and carelessly cancel all factors of w leading to a contradiction and a fake "proof".
