Feynman on Fermat's Last Theorem
lbatalha.com
lbatalha.com
Of course, we now know that FLT is related to deep ideas in number theory.
One story I heard is that a computer scientist tried to explain the P=NP? problem to him; Feymnan couldn't understand why this was a problem. It was obviously true that P != NP, what even needed proving?
Then, I think it is clear the statement is not true. NP is trivially definitionally not equivalent (equal) to P.
?
Why would Feynman not have published a full(er) proof?
As for why Feynman didn't publish a full(er) proof: a full(er) proof of what? He didn't have anything near a proof of P != NP or of Fermat's Last Theorem... There was nothing of the sort to publish.
NP=non-deterministic algorithms in polynomial time
See, it is a definitionally trivial logical negation.
That's the joke!
Edit: Also, why cannot I report/flag your post? Your personal malignment is uncalled for.
You should be directing your disbelief at Feynman's remains. He is the one that made the claim. I just explained the joke.
Anyway, it is still true that the physical model of P != NP is definitionally trivial.
Anyway. Nevermind that. Feynman joked that P was trivially not equal to NP? Where can I find that joke given by Feynman?
Approximately 6 parents up this comment tree.
I'll address your other comment here (HN has an inexplicably bad rate limit):
The physical model is the literal characters:
P != NP
:)
I wouldn't consider it authoritative though.
You can't downvote or flag comments that are replies to you.
(You seem to be implying logical negation. But P is not meant to be a logical statement, thus can't be negated.)
Plus what Chinjut said.
See my replies elsewhere.
Alas, jokes and sarcasm don't travel well over text. One of the reasons they are frowned upon in the HN guidelines.
As another example, consider the question of whether there exists a right-angled triangle with rational sides, having an area of 157.
Once he had 1e-33 for all n > 100 that could mean that even trying with 1M computers where each tries 10G solutions per second (1e6*1e10) some millions of years could pass without the positive result. Then it's exactly reasonable to say "for my money Fermat’s theorem is true" as in, really not worth trying blindly.
Imagine somebody came to you at these "early" times (Wiles proved the theorem in 1995) with a "grand project" to use a lot of computers to search for a possible "solution," being able to try 10 billion Ns in one second. What would be your argument against such a project? Would you try some similar derivation to get an estimate of success?
I know, brute forcing all integers is impossible, but you can even "imagine" a "superquantum (and now not existing) computer" which can do a lot of small integers in parallel.
And yes, I know, probabilities aren't proofs, especially not for integers. One counterexample is enough:
3987^{12} + 4365^{12} = 4472^{12}
Also interesting to see the accidental(?) order of magnitude of the numbers involved.
https://people.math.ethz.ch/~kowalski/probabilistic-number-t...
I am also not 100% sure Feynman wrote something like this. However the 2014 Fields Medal was awarded to Manjul Bhargava for studying random elliptic curves.
https://www.quantamagazine.org/20140812-the-musical-magical-...
It's very possible that it's an unprovable true conjecture, which is kind of interesting in itself.
* every even number can be written as a sum of two primes
There are also probably many conjectures like this. Freeman Dyson constructed one, that no digits of powers of two, reversed, make a power of 5. The reasoning being that the digits grow big quickly, and the base 10 representation is basically random and uncorelared with it.
I think other conjectures about digits of numbers are similar. E.g. Mathematicians have found it impossible to prove that any numbers are normal, or even if pi contains infinite 5's, and many similar properties. These things may only be probabilistically true.
For example, to show that no elephants exist, start with the (infinite) set of all possible chromosome sets. The proportion of them that produces an elephant is zero. QED.
Examples from mathematics:
The number 42 does not exist (logic: pick an integer. The probability that it equals 42 is zero. QED)
There are no even primes.
There are no primes.
There are no integers.
There are no rational numbers.
All numbers are transcendental.
Continuous functions do not exist.
There are no regular polygons.
"the integers don't exist, because the percent of real numbers that are integers is effectively 0" is what the parent post is implying, which "works", in the sense that using this proof methodology "works"
In fact, there's the classic result that this probability is about 1/log(N) [1], which diverges towards infinity. Hence you would probabilistically expect infinite primes and would be correct.
Mathematicians of course, would not do that. They do use the technique of estimating the solution size to get a feeling for the difficulty of a problem, but always try to pick a reference set that is such that the exercise teaches them anything, and starting with all reals doesn't (how do they know that? Intuition, or they may do it anyway, but realize half-way through that it is silly, or even publish it, and, eventually, get corrected)
Feynman's solution has more good math, but still makes the fatal mistake of stating that "measure zero implies does not occur" (although he probably knew, since he states it was good enough for him)
One can 'prove' the non-existence of any countable infinite set of numbers this way.
> The number 42 does not exist (logic: pick an integer. The probability that it equals 42 is zero. QED)
I object! What is your probability distribution function over the integers? Your phrasing sort of implies a uniform distribution, but there is no such thing as a uniform distribution on an infinite set, and as soon as you pick a plausible pdf the argument stops working.
What's the chance that a random number in [n] is 42? It's 1/n, if n is at least 42. Sum that over all x in [n] and you get 1, i.e. the probability that there is a number in [n] that is 42.
Feynmann's argument is clumsy and wrong. This kind of approximation is ok for a physicist but it doesn't work for mathematics.
This is not obvious. If you're going to postulate an infinite number of possible chromosome sets, you're also going to have to admit that an infinite subset of them all produce elephants.
For example, if you show genome A which does not produce an elephant, perhaps I could show genome A', consisting of (1) genome A; (2) a reference elephant genome; (3) some chromosomes that have the effect of disabling genome A.
Can someone explain what probability means here in relation to N? From my understanding, it depends on what N is for you. If it's a constant, that probability is obviously 0 or 1. So that can't be it. Then N must be some kind of random variable. But with what distribution? And in what kind of system can the probability of event(random_variable) involve random_variable itself?
I would consider something like the following a valid question: "Let N be a random integer between 0 and M-1 with uniform distribution. What is the probability that N is even?"
Then an answer could be "the probability that N is even is 1/2 if M is even and (M+1)/(2M) if M is odd". See this does not involve N but does involve M which is a parameter for the distribution of N.
Your explanation seems to invoke some "common sense" which I am not able to unify with my understanding of probability theory.
Edit: define f(N) as the number of numbers below N that match. Consider the function f(N)/N. We call a function of N the probability of N matching if it asymptomatically approaches f(N)/N.
To match up to your example. "For a number M, m is the remainder of M: m = M - floor(M), what is the probability that m is zero given M"
Either globally: Proposition P is true for n of the numbers from 1:N -> p(P,N) = n/N
or locally: Proposition P is true for n of the numbers from N-k to N+k -> p(P, N, k) = n/k
and pick a reasonable k (where p(P, N, K) is relatively stable for a neighborhood around k)
For an exposition on some heuristics mathematicians use, https://terrytao.wordpress.com/2015/01/04/254a-supplement-4-... is a good read (although it's aimed at readers already having some background in number theory).
Mathematicians do use this kind of back of the envelope calculations to get a feeling for whether a statement may be true, but they can never prove something.
https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell2/cald6.h...
Up to sign? The smallest prime is even.
One isn't typically called a prime for the same reason as mathematicians typically say 0^0 equals 1; it makes many theorems and proofs look better.
First, the smallest prime (2) is even.
Second, your first statement can substitute "an even number is prime" with "a multiple of n is prime" for all prime n, leading us to conclude that the odds of any multiple of 3, 5, 7, 11, 13, et al being prime are zero thus seemingly statistically disproving the existence of any prime number which is absurd.
However Number Theory is a different beast altogether
It has as much to do with "regular" math as English and Latin have in common, even though they are written with the same alphabet.
That is probably a significant reason for his enduring appeal; a streetwise, bongo-playing physicist with a talent for quips.
Can you elaborate on this?
I find it hard to believe Feynman concluded from this that the theorem is probably correct. it only takes 1 case among an infinity to make the theorem false.
It would be quite unusual to have a problem stated in such simple terms and require a solution so far away. Thus this probability is used to infer just how large such a number must be, and eventually you're going to hit a point where there is more information encoded in the number than there is necessary to solve the problem, as which point no larger number could be a solution.
This is basically how induction works anyway: you produce a base case and an algorithm, and infer that the information contained therein meets the needs of the problem. Then any number which would encode more information is irrelevant (and thus sufficient) and you have an inductive proof.
Or just in n-dimensional cubes from the start: 1 n-dimensional cube of side-length a + 1 n-dimensional cube of side-length b to cover the volume of 1 n-dimensional cube of side-length c.
Of course, both of these don't amount to much different than just saying a^n + b^n = c^n directly. :)
I don't suspect that decomposing it into a^(n - k) a^k + b^(n - k) b^k = c^(n - k) c^k for arbitrary k is particularly helpful, and, for reasons as illustrated above, I suspect the aid to intuition from thinking in terms of volume and tessellations geometrically isn't very great, but, I'm not an expert on Fermat's Last Theorem. (For all I know, something like this does get used in the proof...)
That's intriguing! What's special about the number 100 that you can prove the case for n≤100?
Note that, if you have proven Fermat's Little Theorem for some exponent, then you have also proven it for every multiple of that exponent. Thus, to prove it for all exponents (> 2) up to some limit, it suffices to prove it for all odd prime exponents up to that limit, as well as for exponent 4. Fermat himself gave an argument which worked for exponent 4, so afterwards, one could consider only odd prime exponents.
Note also that, if p is prime, and we have a solution to x^p + y^p = z^p, then out of {x, y, z}, precisely 0, 1, or all 3 are divisible by p (i.e., if any two were divisible by p, then so would be the third). If indeed all 3 are divisible by p, we may accordingly divide all through by p to obtain a smaller solution; thus, if there is any solution, there is a minimal solution where precisely 0 or 1 of {x, y, z} are divisible by p.
So to prove Fermat's Little Theorem for prime exponent p, it suffices to prove both of the following claims for all solutions to x^p + y^p = z^p:
(A) It cannot be the case that precisely 0 of {x, y, z} are divisible by p
(B) It cannot be the case that precisely 1 of {x, y, z} is divisible by p
If this can be done for every odd prime p up to some limit, FLT is established for all exponents up to that limit.
Germain did not do this. She did not have a strategy for proving (B). This prevented her from establishing FLT in full for any exponent.
Germain did manage, however, to discover a strategy for establishing (A) for various p. Specifically, she discovered a sufficient condition for (A) was the existence of another prime t in a certain decidable relation to p. Germain then manually searched for and discovered such t for each prime p < 100.
Why'd she stop there? Because it seemed like a nice place to stop. Nothing special about 100 except the human factor. One could keep going, and indeed, Legendre extended Germain's results to each prime < 197. Germain and Legendre were both aided by certain techniques they had developed in order to quickly identify certain candidate t that could work as the auxiliary primes for particular exponents p; however, these techniques broke down at 197, and while it is possible to find by brute force an auxiliary prime t in the appropriate relation to p = 197, the smallest such t is very large and the scale of the calculation was beyond feasible at the time.
I may still not have gotten the story exactly correct, or noted all the pertinent details, but for more, see https://www.agnesscott.edu/lriddle/women/germain-FLT/SGandFL..., on which I based the above description.
Lemma: If x and y are coprime, then the gcd of x + y and (x^n + y^n)/(x + y) divides n.
Proof: Expand out the polynomial division (note that x + y does indeed divide x^n + y^n), and then divide the result by (x + y) again, observing a remainder of ny^(n - 1). Thus, the gcd of interest is the same as gcd(x + y, ny^(n - 1)). As y^(n - 1) is coprime to x + y (by coprimeness of x and y), this is furthermore the same as gcd(x + y, n), completing the proof.
Lemma: If x^p + y^p + z^p = 0, for odd prime p, with z indivisible by p, then (x + y) and (x^p + y^p)/(x + y) are coprime p-th powers.
Proof: As z is indivisible by p, so is -z^p = x^p + y^p, and thus so is its factor x + y. At this point, invoking the above lemma and the primeness of p, we find that (x + y) and (x^p + y^p)/(x + y) are coprime; as their product is a p-th power (-z^p), we conclude they are furthermore each p-th powers.
Sophie Germain's theorem: Suppose p is an odd prime, t is a prime, and the mod-t exponent-p case of FLT is true (in the sense that there is no solution to x^p + y^p + z^p = 0 (mod t) where x, y, and z are nonzero (mod t)), but the non-modular exponent-p (A) case of FLT fails (in the sense that there IS some solution to x^p + y^p + z^p = 0 in integers, all indivisible by p, which we can assume minimal so that x, y, and z are pairwise coprime). Then p is a p-th power modulo t.
Proof: Invoking the above lemma, we have some a, b, c such that a^p = y + z, b^p = x + z, and c^p = x + y.
Furthermore, since mod-t FLT is true, we have that (precisely) one of x, y, or z is zero mod t; WLOG, let this be x. But as 2x = b^p + c^p - a^p, we can invoke mod-t FLT again to conclude that one of b, c, or a is zero mod t. It cannot be b or c, as y and z, respectively, are nonzero mod t; thus, a is zero mod t. Thus, y + z = 0 (mod t), and therefore, by expanding out the polynomial (y^p + z^p)/(y + z), we see that its integer value is equal to py^(p - 1) modulo t. As x is zero mod t, we must have furthermore that (x^p + y^p)/(x + y) must be y^(p - 1) modulo t (note that this is nonzero modulo t). As the former and latter are both p-th powers by the above lemma, so is their ratio in modulo t arithmetic, which is p, completing the proof.
We can now rephrase Sophie Germain's theorem like so: To establish the (A) case of FLT for exponent p, it suffices to find some prime t such that BOTH the mod-t exponent-p case of FLT is true AND p is not a p-th power modulo t.
Such a t is the auxiliary prime for p discussed above. Note that the truth or falsehood of this condition on t relative to p is decidable by finite search.
A couple more comments: As a consequence of the multiplicative group modulo a prime being cyclic, we have that, for primes p and t, EVERY value is a p-th power modulo t unless t is 1 mod p. Thus, an auxiliary prime t for odd prime p must be of the form kp + 1. Furthermore, as t cannot be 2, it must be an odd prime, and therefore k must be even. Finally, we can also rule out k divisible by 3 by again invoking the cyclicity of the multiplicative group modulo t (were k divisible by 3, we would have some primitive cube root of 1 modulo t which was furthermore a p-th power; the three powers of this value would sum to zero and thus provide a counterexample to the mod-t exponent-p case of FLT). So when searching for auxiliary t to prime p, we are looking for primes of the form kp + 1 where k is an even value not divisible by 3; for all such k up through 16, Germain and Legendre managed to prove that conversely, whenever kp + 1 is prime, it satisfies all the conditions to be an auxiliary prime for p (with a slight exception for the two cases where p = 3 and k is 14 or 16), which provides auxiliary primes for each p < 197; however, at p = 197, one must go beyond this, to a minimal k of 38.
I do not at the moment know if there are auxiliary primes for each p (and I suspect no one does?), nor how one goes about showing that, for various k, kp + 1 is automatically an auxiliary prime whenever prime (or whether this generalizes beyond k = 16). Oh well. More to learn, always.
It's too bad he didn't live to see machine learning take off. Feynman thought statistically, and probably could have advanced the field.
Couldn't we argue in the same way that there are unlikely to be any solutions to the simpler equation x^n = z^n?
After all, taking p(x) = x^(1/n - 1)/n to be the probability that x is an n-th power, as Feynman does, and then integrating p(x^n) dx from x = x_0 to infinity to find the expected number of n-th powers of the form x^n for x > x_0, as Feynman does with p(x^n + y^n), we find for n > 2 that this comes out to 1/(x_0^(n - 2) * n * (n - 2)), which is quite small for sizable x_0 and n.
This yields, for example, that the expected number of solutions (and thus an upper-bound for the probability of the existence of any solutions) to the equation x^100 = z^100 with x > 10 should be 1 out of 98 googol. This is about as certain as certain gets that there are no solutions... and yet solutions are as ubiquitous as ubiquitous gets!
The downside of Feynman's approach is that it can't get you any intuition about the structure, the things that aren't statistical randomness. And whether FLT was true or false depended exactly on whether the structure pointed one way or the other. So I have no idea why he was so confident in this analysis.
Actually, I'd say it is odd to find this sort of analysis to give great confidence about the results, not just because it ignores the possibility of structure, but also because it ignores the possibility of coincidence!
After all, there are some things which we probably want to call mathematical coincidences which heuristic argument would tell us are bogglingly unlikely and yet which nonetheless happen. For example, another probabilistic argument: Consider the basic arithmetic 2-ary operations +, -, * , and ^. There are 20!/(10! * 11!) full binary trees with 11 leaf nodes, 10^4 ways to label their internal nodes with one of these 4 operations, and 11! ways to assign the values 0 through 10 to those leaf nodes in some permutation. Thus, there are at most 20!/10! * 10^4 (overall, less than 10^16) values which can be generated using these operators and the natural numbers up through 10 once each (and this is an overestimate, ignoring the structure of, e.g., commutativity of + and * which causes less distinct values to be produced).
We would expect, therefore, that the closest we could get one of those values to line up with a particular unrelated mathematical constant, even focusing only on the fractional part, is no more than about 16 or so decimal digits. If there are thousands of mathematical constants we might compare it to, perhaps we'd get a match to about 20 digits on one.
And yet! And yet (1 + 9^(0 - 4^(6 * 7)))^(3^(2^(10 * 8 + 5))) lines up with e to 18457734525360901453873570 digits.
Now, what's happening here is that we have this other nice lining up of 9^(4^(6 * 7)) = 3^(2^(10 * 8 + 5)), which we can then plug into e ~= (1 + 1/n)^n with huge n. And this, in turn, is because 9 = 3^2 and 4 = 2^2 and 1 + 2 * 6 * 7 = 10 * 8 + 5. There's a bit of an explanation. And yet... surely if anything is a coincidence, this is?
So... I guess what I'm saying is, it is odd to use probabilistic arguments to rule out coincidence. The whole thing that makes a coincidence remarkable is that it is the sort of thing we would consider unlikely, and yet such things do occur, even in mathematics.
I'm basically saying that Feynman's argument rules out seemingly random counterexamples like 27^5 + 84^5 + 110^5 + 133^5 = 144^5, which disproved the sum of powers conjecture.
He could've gotten away with the pun "took A. Wile to put together."