Software Musings

The Importance of Being 17

Posted on: 19/11/2006

I have now twice used Proofs From THE BOOK to determine someone’s interest in pure mathematics, once for someone just going off to university and once for someone having just completed his first year there. The test is simple: read this book. If you see an unrelated string of clever tricks then you’re not a pure mathematician.

Push that thought onto the stack for a moment; we’ll pop it off again shortly. In the interim, let me tell you about an exercise, which wasn’t intended to be anything special. I was going to spend a few minutes writing out the well known proof of the irrationality of sqrt(2) for the young son of a friend. To make it clearer, I decided to do sqrt(10). As you know, one assumes a/b (a,b integers) is a fraction in its lowest form which squares to give 10 and then shews that both a and b are even. Therefore it wasn’t in its lowest form. Quod erat, as they say, demonstrandum.

I certainly hadn’t (and haven’t) any intention to try to derive this all the way from the Peano Axioms but I did want to make the proof clear even to someone a little sceptical. I was also not going to bring up the question of the validity of reductio ad absurdum.

Even trying to address a slight scepticism, however, involved lemmata. Some of these were trivial but involved yet another lemma: for example, “if n2 is even then n is even” required the additional lemma that the product of two odd numbers is odd (awkward to argue without using algebra). One lemma, however, was quite awkward: to get the proof going one needs to be confident that every fraction can be written in a unique “lowest form”. This seems to rely both on the unique factorisation of positive integers and every set of positive integers having a least member.

I’ve known the “normal” proof of the irrationality of sqrt(2) for as long as I can remember, certainly for over 40 years, and I have often sketched it out for people but have never really tried to understand why it always made me slightly uneasy. I realise now that it was the lack of those lemmata which never seem to be prepended to the proof. Is it really obvious that, if n2 is even, then n is as well? Is it really obvious to anyone that any fraction has a unique lowest form? If it isn’t, then the proof loses a lot of its cleanliness.

This brings me back to Proofs from THE BOOK. I don’t know about you, but whenever I want to demonstrate the power, beauty, cleverness or whatever of mathematics I roll out the same tired examples: the number of primes, Cantor’s diagonal argument and the irrationality of sqrt(2). I don’t think that I’m alone in this. Even Hardy uses them in his Apology and almost every popular mathematics website seems to contain them.

These proofs have their WOW! factor because they each prove very quickly something that superficially looks to be extremely difficult. For a new century (OK, I’m a few years late but I need some sort of terminus a quo) I feel we should select a new set of proofs to demonstrate the mathematician’s art. They must be short, accessible to the amateur without a great deal of explanation and have a major AH HA! factor. May I suggest the following?

  • in any subset of n+1 numbers taken from {1, 2, 3, …, 2n} there are two numbers such that one divides the other
  • the size of the power set is always greater than the size of the set (although my wife, reading over my shoulder, says that everyone would find that obvious (at least for sets with two or more members), even without a proof—perhaps the AH HA! factor here is the necessity of a proof for infinite sets, but that brings us back to Cantor and his diagonals)

I’ve been reading the available chapters of Alexandre Borovik’s Mathematics Under the Microscrope and it might be proper to add Coxeter’s proof of Euler’s theorem (If an orientation-preserving isometry of the affine Euclidean space AR3 has a fixed point then it’s a rotation) to this list.

On an unrelated point, in his first chapter Borovik describes the rhythm of a woman on a train completing a Sudoko puzzle and, although he doesn’t mention it, I was reminded of having read somewhere that at least 17 squares need to be prefilled to make the puzzle deterministic. I Googled this and found this site which proves, using an Eigenvalue argument of a type I hadn’t seen before, that at least 16.8952381 squares need to be completed. I also stumbled across a site entitled Minimum Sudoku which contains 36628 Suduko puzzles, each with 17 entries. I’ve never really analysed either the mathematics or the psychology behind these puzzles, although I did write a program to solve them, but it does seem that there should be a proof of that 17 argued from linear algebra principles (I certainly seem to be solving sets of linear equations when I solve a Sudoko). Does anyone know of a simple proof of the necessity of 17 pre-defined entries that could be added to my list of nice proofs above?

As a postscript, we know that the actual symbols in a Sudoko puzzle don’t matter and are arbitrarily set to the integers 1 to 9. Had other symbols been chosen (hearts, diamonds, spades, clubs, elephants, giraffes, etc.) I can imagine a proof of the 17 number starting with the statement “as the symbols being used are arbitrary, map them to the integers 1 to 9 and recast the problem as being that each 3×3 square, each column and each row must total to 45. Then it is easy to see that…”

Advertisements

1 Response to "The Importance of Being 17"

I do not understand The Sudoku Eigenfunction Calculation; I’ll put it that way: the style of exposition is alien to me. Still, I am quite puzzled what is the minimal number of hints in a standard 9 times 9 Sudoku which makes it deterministic. 17 indeed appears to be the most feasible conjecture.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

November 2006
M T W T F S S
« Oct   Dec »
 12345
6789101112
13141516171819
20212223242526
27282930  

Disclaimer

The author of this blog used to be an employee of Nortel. Even when he worked for Nortel the views expressed in the blog did not represent the views of Nortel. Now that he has left, the chances are even smaller that his views match those of Nortel.
%d bloggers like this: