Author
|
Topic: Proof (Read 545 times) |
|
rhinoceros
Archon
Gender: 
Posts: 1318
Reputation: 8.40
Rate rhinoceros
My point is ...
  
|
 |
Proof
« on: 2005-04-06 03:53:38 » |
 |
While chatting with Lucifer in IRC/#virus, I mentioned how the joy of mathematics is hard to share with others around you who are not already in the know. Then I remembered that Ian Stewart has been trying to do exactly that in his columns. Here is one:
http://www.fortunecity.com/emachines/e11/86/forgeries.html
(Appeared in Scientific American, May 1995)
<snip>
"Name's Adam Smasher. I'm a nuclear physicist. I have a little puzzle I'll ask you. What's the next number in the sequence 1, 1, 2, 3, 5, 8, 13, 21?"
"Nineteen," I grunted automatically, while battling with a bread roll seemingly baked with cement.
"You're not supposed to answer," he said. "Anyway, you're wrong - it's 34. What made you think it was 19?"
I drained my glass. "According to Carl E Linderholms great classic "Mathematics Made Difficult", the next term is always 19, whatever the sequence : 1, 2, 3, 4, 5 - 19 and 1, 2, 4, 8, 16, 32 - 19. Even 2, 3, 5, 7, 11, 13, 17 - 19."
"That's ridiculous."
"No, it's simple and general and universally applicable and thus superior to any other solution. The Laplace interpolation formula can fit a polynomial to any sequence whatsoever, so you can choose whichever number you want to come next, having a perfectly valid reason. For simplicity, you always choose the same number."
"Why 19?", Dennis asked.
"It's supposed to be one more than your favourite number," I said, "To fool anyone present who likes to psychoanalyse people based on their favourite number."
"Nonsense, I'll tell you the real answer," Adam said. "Each number is the sum of the previous two. So the next is 13+21, or 34, then 55, then 89, then 144 and so on. It's the -"
"Fibonacci sequence," I interrupted. "God, I'm so fed up with the blasted Fibonacci sequence! even the name's phoney! Leonardo Fibonacci, son of Bonacci!" That's a nickname invented by Guillame Libri in 1838, long after Fibonacci died.
The famed Fibonacci was in fact named Leonardo Pisano Bigolo. Pisano means that he lived in Pisano one knows what Bigollo means. At any rate, his sequence ought to be called the Leonardo Pisano Bigollo sequence, except that's too long."
"You mathematicians have a lot of attitude." Dicky remarked. "At least, an attitude that differs from most other people's."
"Proof," Adam declared." Mathematicians always want to prove things. That's certainly a strange attitude. Never understood why myself. If you keep trying it, and it keeps working, it's got to be right! So why waste time getting into all sorts of logical tangles proving the silly thing?"
"Well, why don't you physicists bother doing experiments? If a theory tells you what you want to hear, why not just assume it's true?" "Because you can't just go around believing theories without testing them!"
"And mathematicians don't think you can go around believing theorems without proving them. Alexander why do lawyers insist on cases being tried in court? Why not just let the judge look at the evidence and decide whether the defendant has committed the crime?"
"You can't do that! There would be a miscarriage of justice!"
"Right. That's what mathematicians worry about when they insist on proofs. They don't want to find out later that they were wrong. It might be embarassing."
Adam shook his head sadly, "You know full well it's not like that. Mathematics is basically simple. If you can see an obvious pattern it can't be coincidence. Why bother to prove it?"
I thought for a few sceconds, "I'll give you an example. Here's a sequence, and I want you to tell me the next number."
"I'll do my best."
"1, 1, 2, 3, 5, 8, 13, 21, 34, 55," I said.
He looked puzzled. "Don't be silly. I just asked you that one. It's the Fibonacci sequence."
"Is it? Then what's next?"
"89," Adam replied.
"Wrong, it's 91."
"But it looks like the -"
"You're leaping to conclusions, Adam based on previous prejudices. Most injudicious. Your sequence was the Fibonacci sequence, but the nth in my sequence is the least integer not less than sqrt(e exp n-2), where e=2.71828, the base of the natural logarithms. I want the 11th term, which is the least integer not less than, or 90.017. That's 91."
"Humph. Well that's an accident, a rare exception. I'll believe you if you can show me some more examples of misleading sequences."
Alexander interjected, "Can you? Or have you exhausted your repetoire?"
<snip>
I proposed one last puzzle.
"What is the next term in the sequence 3, 5, 7, 11, 13, 17, 19.." - I carried on for some time, listing the odd primes, "....331, 337?"
"Those are odd primes," Adam said, "You can't generate that many primes by accident. The next term must be 347."
"Are you sure?" I asked quietly...
(The author leaves this one dangling, and the answer is given at the end of the page.)
Odd Prime Sequence: Forgery. The sequence 3, 5, 7,....331, 337 and so on consists of all the numbers n that divide (2 exp n-1)-1 exactly. The next term is 341,which is not prime (11 x 31 = 341) but divides (2 exp 340)-1.
(There is also this comment about numeric sequences used in IQ tests.)
[Note that number sequences are used in intelligence tests and often there is a presumed correct answer and if you don't get that then you are said to be unintelligent - given that interpolation techniques can generate any answer from a given sequence - the intelligence test is really not a matter of generating THE answer - but generating AN answer that is logically consistent and follows a reasoned argument.]
|
|
|
|
|
rhinoceros
Archon
Gender:
Posts: 1318
Reputation: 8.40
Rate rhinoceros
My point is ...
|
|
Re:Proof
« Reply #1 on: 2005-04-06 04:29:29 » |
|
I should have mentioned that the discussion about maths which made me recall Stewart's columns was triggered by this recent article about proof in the age of the computer:
http://www.economist.com/science/displayStory.cfm?story_id=3809661
Proof and beauty
Mar 31st 2005
QUOD erat demonstrandum. These three words of Latin, meaning, "which was to be shown", traditionally mark the end of a mathematical proof. And, for centuries, a proof was exactly that: showing something by breaking it down into readily agreed-upon steps. Proving something was a matter of convincing one's peers that it has indeed been shown--no more, and no less.
<snip>
The use of computers to prove mathematical theorems is forcing mathematicians to re-examine the foundations of their discipline.
<snip>
What, then, does constitute a proof in the modern age? Two recent examples of how computers have been used to prove important mathematical results illustrate how the field is changing.
A colouring problem
The first is the "four colour theorem", which is perhaps the mathematical theorem most likely to bedevil a toddler. It states that any planar map (that is to say, a flat one) can be coloured with at most four colours in a way that no two regions with the same colour share a border. It was first proposed in 1852 but, despite efforts by a century's worth of mathematicians, went unproven until 1976, when...
<snip>
A new proof, in a paper just written by Georges Gonthier, of Microsoft Research, in Cambridge, England, also uses a computer. Dr Gonthier used similar techniques to those of Dr Appel and Dr Harken in his proof. However, rather than have part of the proof done by hand, and part by computer, he has automated the entire proof, and done so in such a manner that it is a formal proof.
Formal proof is a notion developed in the early part of the 20th century by logicians such as Bertrand Russell and Gottlob Frege, along with mathematicians such as David Hilbert (who can fairly be described as the father of modern mathematics) and Nicolas Bourbaki, the pseudonym of a group of French mathematicians who sought to place all of mathematics on a rigorous footing. This effort was subtle, but its upshot can be described simply. It is to replace, in proofs, standard mathematical reasoning which, in essence, relies on hand-waving arguments (it should be obvious to everyone that B follows from A) with formal logic.
The benefit of formal logic is that it is pure syntax. At no point does proceeding from one step to the next require understanding, let alone mathematical intuition. It is merely a matter of applying an agreed-upon set of rules (for instance, that any thing is equal to itself, or that if something is true for all members of a set of objects, it is true for any one specific object) to a set of agreed-upon structures, such as sets of objects. Formal proofs, however, never gained a foothold in the mainstream mathematical community because they are tedious--they take many steps to prove something in cases in which a mathematician might just take one. To those who would use a computer, however, they have two virtues.
The first is that computers, with their tolerance for tedium, are particularly suited to writing the steps of a formal proof down. The second is that, by writing those steps down in what is called a "proof witness" instead of just announcing that a program had arrived at a true result, outsiders might gain greater confidence in a result derived from a computer.
<snip>
Dr Gonthier says he is going to submit his paper to a scientific journal in the next few weeks. But he would do well not to get his hopes up about getting his paper published anytime soon. A 1998 paper which proved another long-standing conjecture using a computer, by Thomas Hales, of the University of Pittsburgh, has only recently been accepted by the Annals of Mathematics, perhaps the field's most prestigious journal, and is scheduled to be published later this year.
The music of the spheres
Dr Hales proved Kepler's conjecture, which is that the most efficient way to pack spheres in a box is the way grocers usually pack oranges--in a so-called "face-centred cubic lattice"--the arrangement whereby each layer of oranges is shifted so that an orange touches four oranges in the layer below. Kepler posited the conjecture in 1611, and it had long resisted efforts at proof. Indeed, Hilbert made it one of his list of the 23 most difficult and fundamental questions in mathematics, in 1900. Dr Hales proved the conjecture by using a trick different in nature to Dr Gonthier's.
Rather than argue by contradiction, he reduced what was a problem about an infinite number of things (the Kepler conjecture considers an infinite number of spheres in an infinitely large space) to a statement about a finite, but very large, number of mathematical objects.
<snip>
Although the Annals will publish Dr Hales's paper, Peter Sarnak, an editor of the Annals, whose own work does not involve the use of computers, says that the paper will be accompanied by an unusual disclaimer, stating that the computer programs accompanying the paper have not undergone peer review.
<snip>
Dr Sarnak points out that maths may become "a bit like experimental physics" where certain results are taken on trust, and independent duplication of experiments replaces examination of a colleague's paper.
Some of the movement towards that direction may be forestalled by efforts of Dr Gonthier's type to use computers to provide formal proofs and proof witnesses. It is possible that mathematicians will trust computer-based results more if they are backed up by transparent logical steps, rather than the arcane workings of computer code, which could more easily contain bugs that go undetected. Indeed, it is for this exact reason that Dr Hales is currently leading a collaborative project to provide a formal proof of the Kepler conjecture.
<snip>
Why should the non-mathematician care about things of this nature? The foremost reason is that mathematics is beautiful, even if it is, sadly, more inaccessible than other forms of art. The second is that it is useful, and that its utility depends in part on its certainty, and that that certainty cannot come without a notion of proof.
|
|
|
|
|
|
Logged
