Consider the following theorem:
There is no 2-digits number that is the sum of the squares of its digits.One crude measure of elegance is to minimize the number of numbers that you need to check directly are not the sum of the squares of their digits. With this in mind. With this in mind, here are several proof sketches.
- One could proof this by enumerating all possible 2-digit numbers. If you wrote a program for this then you could use it on similar problems. Even so, I suspect most of us would call this proof NOT ELEGANT. This requires 89 CHECKS.
- There is a proof that first easily eliminates 10, 20, 30, 40, 50, 60, 70, 80, 90 and then looks at every interval [11,19], [21,29], ..., [91,99]. More elegant than enumeration and certainly shorter. This required 8 CHECKS.
- There is a proof that looks at the equation 10a + b = a2 + b2. We look at it mod 2, mod 4, and mod 10. This gives what I thought was the most elegant proof; however, after writing it down carefully it was about the same length as the interval proof. This required 2 CHECKS.
There is no x ≥ 2 that is the sum of the squares of its digits.The cases of 2 ≤ x ≤ 9 and x ≥ 100 can be done with zero checks, so using the best proof of the last theorem, we can do this theorem with 2 checks.
Consider the following theorem.
The only 3-digits number that is the sum of the cubes of its digits is 153. (NOTE ADDED LATER: This is INCORRECT. A commenter pointed out that 370, 371, 407 also work. I will fix the proof and statement later and see if these are the only ones. Score a point for the `do it by a computer enumeration' argument!)I have a proof of this which is... not quite elegant but not brute force. I get it down to only 21 CHECKS. If you have a better proof in terms of NUMBER OF CHECKS that is not contrived to reduce NUMBER OF CHECKS I would be very interested to see it. Of course, I cannot define contrived rigorously or elegantly.
In my opinion, if you have a completely finitary process, then checking the elements one by one is the most elegant proof technique. The reason is that enumeration discovers all the structure, and exactly the structure, inherent in that finite set. Furthermore this process is a priori known to be correct and perfect.
ReplyDeleteUsing any set of more general axioms is a process that is only accidentally correct --- namely, perhaps there could be a tighter proof, but you were lucky and the axioms happened to cover the finite set closely enough.
One should not confuse elegance with simplicity or conciseness.
Actually, one could argue quite to the contrary that, by enumeration, one learns nothing new about the structure, i.e.
Deleteafter having checked all elements one knows wether they have
some property or not, but one did not gain any understanding why this is the case.
But for a finitary process, there is ultimately no reason why anything holds. It is, at the end, nothing more than a coincidence.
DeleteA nice essay could be written comparing and contrasting elegant proofs with natural proofs, with the former criterion regarded as a (mainly) algebraic aesthetic, and the latter as (mainly) a geometric one. As Grothendieck said of the latter:
ReplyDelete------
“The unknown thing to be known appeared to me as some stretch of earth or hard marl, resisting penetration. . . the sea advances insensibly in silence, nothing seems to happen, nothing moves, the water is so far off you hardly hear it. . . yet it finally surrounds the resistant substance.”
------
So is there a rarified class of proofs whose methods are both elegant and natural?
About the sum of the cubes problem: what about 370, 371, and 407?
ReplyDeleteWoops! I ammended the post and will fix the proof later- I suspect
ReplyDeletethe theorem will really be the only numbers are 153, 370, 371, 407.
But I will see.
THANKS!
Look at the equation 10a+b=a^2+b^2; has obvious solution a=10, b=0 in integers
ReplyDelete40a+4b=4a^2+4b^2
(2a-10)^2+(2b-1)^2=101
101 is prime, 1 mod 4, hence there is a unique way to represent it as sum of two squares of natural numbers (Gauss primes), namely as 10^2+1^2 (coming from a=10,b=0), hence b=1 or 0, and a=0 or 10
How many checks is that?
I may be an odd case, but I reject that a computerized search is inherently inelegant. This is a belief that is bound to become more widespread as the role of computers increases in theorem proving. I think it's much more likely that a problem solvable by search is an inelegant problem.
ReplyDeleteAs Bill suggests, measuring the number of checks is a good proxy for elegance, at least in the case of human-readable proofs. If you allow that computer-aided proofs may be elegant, then we might want to expand that definition. Certainly, an elegant snippet of C code that runs quickly and solves the problem should be considered an elegant proof.
Here is a more general proxy. For a solution to be elegant, consider the minimum over:
1. Elegance of search code (that runs in "reasonable" time)
2. Length of computer-readable proof starting from scratch
3. Length of computer-readable proof depending on "natural" results, however deep
4. Program running time on a computer (of "reasonable" source complexity)
5. Inverse-elegance of human readable proof
This revision still has a long way to go. In the case of 2, for instance, there may be computer-readable proofs that are short but take unintelligible leaps of logic. A similar situation occurs when a computer chess program arrives at a baffling but powerful move. Is such an unintelligible proof elegant? Maybe to a computer... Probably not to a human, at least right now.
Item 3 would also give a proxy for measuring the elegance of the problem. Does it depend on a major result almost to the point that it is equivalent? Probably inelegant. Does it combine several deep results in a simple way? Probably elegant.
kl
The idea of counting the number of checks seems to me partially a proxy for "are we doing something more clever than brute-force search?" In this latter formulation, this was one of the original motivations for P vs NP. Especially in the Russian school, NP problems were literally known as "perebor" or "brute-force" and the P vs NP problem was called the "problem of perebor."
ReplyDeleteIn this sense, and along the lines of what kl suggested, when one can attach a natural family of decision problems to a proof---that is, a family of statements, say parametrized by a natural number n, or any of the usual coterie of combinatorial objects we use in complexity---then one can ask about the complexity of the theorem-proving procedure for this family. Generically speaking, one might expect brute-force computer searches to be exponential, or NP at best, and more elegant techniques might lead to polynomial-time proofs/algorithms.
Although we are often only interested in finit(ary) statements, we are also technically only ever interested in fint(ary) inputs to algorithms, and yet we still consider asymptotic complexity a good guide to something-like-efficiency. In the case of proofs, complexity in the usual sense (in addition to proof complexity proper) might perhaps offer at least a hint of elegance.
Here's a sketch:
ReplyDeleteSuppose that 10a+b=a²+b² ˂=˃ b(b-1)=a(10-a) with
aϵ{1,...,9}, bϵ{0,1,...,9}.
Enumerating all possible cases we get:
For b(b-1) the set {9x8, 8x7, 7x6, 6x5, 5x4, 4x3, 3x2, 2x1, 1x0, 0x(-1)}
For a(10-a) the set {9x1, 8x2, 7x3, 6x4, 5x5, 4x6, 3x7, 2x8, 1x9}
But the sets for b(b-1) and a(10-a) don’t have any value in common. Therefore there’s no 2-digits number that is the sum of the squares of its digits.