Skip to content

Descending Proofs Into Algorithms

August 28, 2016


A way to make indirect reasoning more palpable

Worthies_of_Britain'_(_Nicholas_Saunderson)_by_John_Bowles
Wikimedia Commons source

Nicholas Saunderson was the fourth Lucasian Professor at Cambridge, two after Isaac Newton. He promoted Newton’s Principia Mathematica in the Cambridge curriculum but channeled his original work into lecture notes and treatises rather than published papers. After his death, most of his work was collected into one book, The Elements of Algebra in Ten Books, whose title recalls Euclid’s Elements. It includes what is often credited as the first “extended” version of Euclid’s algorithm.

Today we raise the idea of using algorithms such as this as the basis for proofs.

Saunderson was blind from age one. He built a machine for doing what he called “Palpable Arithmetic” by touch. As described in the same book, it was an enhanced abacus—not a machine for automated calculation of the kind a later Lucasian professor, Charles Babbage, attempted to build.

We take the “palpable” idea metaphorically. Not only beginning students but we ourselves still find proofs by contradiction or “infinite descent” hard to pick up at first reading. We wonder how far mathematics can be developed so that the hard nubs of proofs are sheathed in assertions about the availability and correctness of algorithms. The algorithm’s proof may still involve contradiction, but there’s a difference: You can interact with an algorithm. It is hard to interact with a contradiction.

An Example

It was known long before Euclid that the square root of 2 is irrational. In the terms Saunderson used, the diagonal of a square is “incommensurable” with its side.

Alexander Bogomolny’s great educational website Cut the Knot has an entire section on proofs. Its coverage of the irrationality of {\sqrt{2}} itemizes twenty-eight proofs. All seem to rely on some type of infinite descent: if there is a rational solution then there is a smaller one and so on. Or they involve a contradiction of a supposition whose introduction seems perfunctory rather than concrete. We gave a proof by induction in a post some years ago, where we also noted a MathOverflow thread and a discussion by Tim Gowers about this example.

We suspect that one reason the proof of this simple fact is considered hard for a newcomer is just that it uses these kinds of descent and suppositions. Certainly the fact itself was considered veiled in antiquity. According to legend the followers of Pythagoras treated it as an official secret and murdered Hippasus of Metapontum for the crime of divulging it. To state it truly without fear today, we still want a clear view of why the square root of 2 is irrational.

Our suggestion below is to avoid the descent completely. Of course it is used somewhere, but it is encapsulated in another result. The result is that for any co-prime integers {r} and {s} there are integers {x} and {y} such that

\displaystyle  rx + sy = 1.

The {x} and {y} are given by the extended Euclidean algorithm. Incidentally, this was noted earlier by the French mathematician Claude Bachet de Méziriac—see this review—while Saunderson ascribed the general method to his late colleague Roger Cotes two pages before his chapter “Of Incommensurables” (in Book V) where he laid out full details.

An Old Attempt

Here is the closest classical proof we could find to our aims. We quote the source verbatim (including “it’s” not “its”) and will reveal it at the end.



Proposition 15. If there be any whole number, as {n}, whose square root cannot be expressed by any other whole number; I say then that neither can it be expressed by any fraction whatever.

For if possible, let the square root of {n} be expressed by a fraction which when reduced to it’s least integral terms is {\frac{a}{b}}, that is, let {\frac{a}{b} = \sqrt{n}}, then we shall have {\frac{a}{b}\frac{a}{b} = \frac{n}{1}\;}; but the fraction {\frac{a}{b}\frac{a}{b}} is in it’s least terms, by the third corollary to the twelfth proposition, because the fraction {\frac{a}{b}} was so; and the fraction {\frac{n}{1}} is in it’s least terms, because 1 cannot be further reduced; therefore we have two equal fractions {\frac{a}{b}\frac{a}{b}} and {\frac{n}{1},} both in their least terms; therefore by the tenth proposition, these two fractions must not only be equal in their values, but in their terms also, that is, {aa} must be equal to {n}, and {bb} to 1: but {aa} cannot be equal to {n}, because {a} is a whole number by the supposition, and {n} is supposed to admit of no whole number for its root; therefore the square root of {n} cannot possibly be expressed by any fraction whatever. Q.E.D.



The cited propositions are that two fractions in lowest whole-number terms must be identical and that if {a} and {b} are co-prime to {c} then so is {ab}. The proof of the latter starts with the for-contradiction words “if this be denied,” so the absence of such language above gets only part credit. This all does not come trippingly off the tongue; rather it sticks trippingly in the throat. Let’s try again.

A Proof

In fact, we don’t need the concepts of “lowest terms” or co-primality or the full statement of the identity named for Étienne Bézout. It suffices to assert that for any whole numbers {r} and {s}, there are integers {x} and {y} such that the number

\displaystyle  d = rx + sy

divides both {r} and {s}. This is what the extended Euclidean algorithm gives you.

Then for the proof, suppose that {\sqrt{n} = \frac{r}{s}} for integers {r} and {s}. We take {x} and {y}, and let {r_0 = r/d}, {s_0 = s/d} be the resulting integers. Now let’s do some simple algebra:

\displaystyle  r_0 x + s_0 y = 1,\quad\text{so}\quad r_0 = \frac{1 -s_0 y}{x},\quad\text{so}\quad x^2r_0^2 = (1 - s_0 y)^2;

\displaystyle  n = \frac{r^2}{s^2} = \frac{r_0^2}{s_0^2},\quad\text{so}\quad r_0^2 = s_0^2 n.

It follows that

\displaystyle  x^2 s_0^2 n = (1 - s_0 y)^2 = 1 - 2s_0 y + s_0^2 y^2.

Now divide both sides of this by {s_0}. We get

\displaystyle  \frac{1}{s_0} = 2y + s_0 x^2 n - s_0 y^2 = \text{some integer}.

The conclusion is that {s_0 = 1}, hence {s = d}. Thus {\sqrt{n} = \frac{r}{d}}. But {d} also divides {r}. So {\sqrt{n}} is an integer—the same end as the classical proof.

This is a contradiction. But it is a palpable contradiction. For instance, of course we can see that {\sqrt{2}} isn’t an integer. Thus we claim that the effect of this proof is more concrete.

Open Problems

Is this a new proof? We doubt it. But the proof is nice in that it avoids any recursion or induction. The essential point—the divisibility of {d} into {r} and {s}—is coded into the Euclidean algorithm.

Is ours at least smoother than the classical proof we quoted? The latter is from Saunderson’s book, on pages 304–305 which come soon after his presentation of the algorithm on pages 295–298.

What other proofs can benefit from similar treatment by “reduction to algorithms”?

[fixed missing n in last line of proof, some word tweaks]

A Surprise For Big-Data Analytics

August 14, 2016


A simple but interesting issue with analyzing high-dimensional data

LandweberLazarPatel

Peter Landweber, Emanuel Lazar, and Neel Patel are mathematicians. I have never worked with Peter Landweber, but have written papers with Larry and Laura Landweber. Perhaps I can add Peter one day.

Today I want to report on a recent result on the fiber structure of continuous maps.

Read more…

Do results have a “teach-by-date?”

August 9, 2016


Teaching automata theory

Unknown

Noam Chomsky is famous for many many things. He has had a lot to say over his long career, and he wrote over 100 books on topics from linguistics to war and politics.

Today I focus on work that he pioneered sixty years ago.

Yes sixty years ago. The work is usually called the Chomsky hierarchy(CH) and is a hierarchy of classes of formal grammars. It was described by Noam Chomsky in 1956 driven by his interest in linguistics, not war and politics. Some add Marcel-Paul Schützenberger’s name to the hierachry. He played a crucial role in the early development of the theory of formal languages—see his joint
paper with Chomsky from 1962. Read more…

The Mathematics Of Dan’s Inferno

July 25, 2016


A possible error with mathematical ramifications

DanBrownFactCheck
Non-technical fact-check source

Dan Brown is the bestselling author of the novel The Da Vinci Code. His most recent bestseller, published in 2013, is Inferno. Like two of his earlier blockbusters it has been made into a movie. It stars Tom Hanks and Felicity Jones and is slated for release on October 28.

Today I want to talk about a curious aspect of the book Inferno, since it raises an interesting mathematical question. Read more…

The World Turned Upside Down

July 10, 2016


Some CS reflections for our 700th post

Lin-Manuel Miranda is seen in New York, New York on Tuesday September 2, 2015.
MacArthur Fellowship source

Lin-Manuel Miranda is both the composer and lyricist of the phenomenal Broadway musical Hamilton. A segment of Act I covers the friendship between Alexander Hamilton and Gilbert du Motier, the Marquis de Lafayette. This presages the French co-operation in the 1781 Battle of Yorktown, after which the British forces played the ballad “The World Turned Upside Down” as they surrendered. The musical’s track by the same name has different words and melodies.

Today we discuss some aspects of computing that seem turned upside down from when we first learned and taught them.
Read more…

Getting to the Roots of Factoring

June 29, 2016


We revisit a paper from 1994

RichardRelaxed2

Richard Lipton is, among so many other things, a newlywed. He and Kathryn Farley were married on June 4th in Atlanta. The wedding was attended by family and friends including many faculty from Georgia Tech, some from around the country, and even one of Dick’s former students coming from Greece. Their engagement was noted here last St. Patrick’s Day, and Kathryn was previously mentioned in a relevantly-titled post on cryptography.

Today we congratulate him and Kathryn, and as part of our tribute, revisit a paper of his on factoring from 1994.
Read more…

Theory In The Time of Big Data

June 18, 2016


What is the role of theory today?

AnnaAtri

Anna Gilbert and Atri Rudra are top theorists who are well known for their work in unraveling secrets of computation. They are experts on anything to do with coding theory—see this for a book draft by Atri with Venkatesan Guruswami and Madhu Sudan called Essential Coding Theory. They also do great theory research involving not only linear algebra but also much non-linear algebra of continuous functions and approximative numerical methods.

Today we want to focus on a recent piece of research they have done that is different from their usual work: It contains no proofs, no conjectures, nor even any mathematical symbols.
Read more…

Follow

Get every new post delivered to your Inbox.

Join 2,770 other followers