Paul Erdős had this notion that God kept a book of the best proofs. Erdős called God’s book simply “the book.” Springer recently published Proofs from THE BOOK, a collection of elegant proofs that the authors suppose might be in God’s book.
For many mathematicians, the first proof that comes to mind as a candidate for a proof in the book is Euclid’s proof that there are infinitely many primes. The proof is so short and simple that it can almost be written within the 140-character limit of Twitter. I give the proof in my AlgebraFact Twitter account as follows.
There are infinitely many primes. Proof: If not, multiply all primes together and add 1. Now you’ve got a new prime.
Several people pointed out that I was a little too terse. If N is the supposed product of all primes + 1, N itself doesn’t have to be a new prime. It could be that N has a factor that is a new prime. The smallest prime factor of N must be a prime not on the list. Either way “you’ve got a new prime,” but the proof above leaves out some important details.
Here’s an example. Suppose we believed the only primes were 2, 3, 5, 7, 11, and 13. Let N = 2*3*5*7*11*13 + 1 = 30031. Now N cannot be divisible by 2, 3, 5, 7, 11, or 13 because there is a remainder of 1 when dividing N by any of these numbers. Maybe N is a new prime, or maybe N is composite but N has a prime factor not on our list. The latter turns out to be the case: 30031 = 59*509.
If you can find a better summary of Euclid’s proof in 140 characters or less, please leave it in the comments. Please include the character count with your proposal.
“I couldn’t put it down.” “A real page-turner.” That’s how you might describe a good novel to take on vacation. But for more serious reading, a good book is one you have to put down. Thoreau put it this way:
A truly good book teaches me better than to read it. I must soon lay it down, and commence to living on its hint.
Some books take a long time to read, not because they are dull, but because they are exciting. You have to put them down frequently to think about what you’ve read before reading more. It may not be the content of the book per se but the thoughts the book sparks that make you have to put it down.
What are some books you had to put down frequently because they stirred your thinking?
py2exe is a program that takes Python code and produces a Windows executable that can run on computers that do not have Python installed. My focus here is in using py2exe on Python code that depends on SciPy.
py2exe is itself a Python program, and its latest version is built for Python 2.6. The code I want it to compile is written with Python 2.5 because the latest version of SciPy depends on Python 2.5. How do I tell py2exe that my code uses an earlier version of Python?
It took me a while to realize this, but py2exe has two version numbers: one for the version of py2exe and one for the version of Python. The key was to download and install py2exe-0.6.9.win32-py2.5.exe. This is the latest version of py2exe (version 0.6.9) for an earlier version of Python (version 2.5). The py2exe software runs in the same version of Python as the code it is compiling.
I tested py2exe on a script hellpscipy.py as follows:
from scipy.special import gamma
print "Gamma(1/2) = ", gamma(0.5)
The instructions given in the py2exe tutorial don’t quite work because of the dependence on SciPy, but the site gives an example of how to modify the setup.py file to specify the dependence on SciPy. Here’s where things get a little murky. The instructions don’t say exactly how to modify the setup.py file, but they give strong hints. I know my code depends on scipy.special, but I don’t know what further dependencies I might have. Here’s the setup file I used.
This worked. The output listed 94 additional SciPy dependencies that I might need to include, some of which were clearly not needed. I was pretty sure, for example, that my program did not need email.Utils. Apparently I didn’t need any of these because the code worked fine.
It’s not clear just what files need to be distributed along with the .exe file that py2exe produces. py2exe creates a dist directory with the .exe file as well as other files that you might need, primarily .dll and .pyd files. Many of these were obviously unnecessary. I knew, for example, that my little command line program did not depend on Tk graphics. I deleted these and the code worked fine as expected.
Waldir Pimenta asked me whether it is possible to test the condition
max(a, b) / min(a, b) < r
without computing max(a, b) or min(a, b). Here a> 0, b> 0, and r > 1. (If r ≤ 1, the condition is always false.) The inequality has to be evaluated in an inner loop of a real-time image processing application and so the time saved by avoiding computing the max and min might matter.
We can multiply the original inequality by min(a, b) since a and b are positive. The condition becomes
max(a, b) < r min(a, b) = min(ra, rb).
We then expand this inequality into four simple inequalities:
a < ra b < ra a < rb b < rb
Since r > 1, we know that a < ra and b < rb and so we only need to check a < rb and b < ra. In C notation we would evaluate
( a < r*b && b < r*a )
rather than
( max(a,b) / min(a,b) < r )
Whether this saves any time depends on context, though it’s plausible that the former might be more efficient. Some portion of the time the condition a < r*b will evaluate to false and the second half of the condition will not be evaluated.
(C evaluates an expression like (p && q) from left to right. If p is false, q is not evaluated since it is known at that point that the expression (p && q) will evaluate to false regardless of the value of q.)
Challenge: How often will the condition a < r*b evaluate to false? What are your assumptions? Leave your answers below.
Update: Combining the ideas of Carlos Santos and Christian Oudard in the comments below, you could implement the inequality as
a < b ? (b < r*a) : (a < r*b)
There are too many other good ideas in the comments for me to keep editing the blog post so I’ll just ask that you scroll down. I’m surprised at all the ideas that came out of evaluating a simple expression.
I’m growing increasingly frustrated with amateur software. Before I explain why, let me first be clear on what I do not mean by amateur.
Amateur does not mean low quality. Some amateur software is outstanding, and some professional software is terrible.
Amateur does not mean open source. Some amateur projects are open source and some are not.
I’m using “amateur software” to mean software projects developed by volunteers. I imagine most amateur software is written by professional developers. These are folks paid to write software for a company by day who then work on something else they love by night.
Open source software is not necessarily amateur software. Linux, for example, is now professional software. Around 75% of Linux kernel development is carried out by people paid to work on Linux. Some of the best software is both open source and at least partially professional.
Volunteers do what they want to do by definition. The problem is that the reverse is also true: volunteers do not do what they do not want to do. And for software developers, writing documentation usually falls in the “do not want to do” column. So does making software easy to install. So does testing in multiple environments.
When a company has an interest in a piece of software, they can pay people to do the tasks the volunteers don’t want to do. In fact, if they’re smart, they will concentrate their efforts precisely on the tasks volunteers don’t want to do. In this way even one or two paid staff can make an enormous contribution to a largely volunteer project.
Some amateur projects are highly polished. These may be small projects lead by rare individuals who pay attention to details beyond pure software development. More often, these are large mature projects that have so many volunteers that they have a few who are willing to do tasks that most developers do not want to do.
My family loves the Little House on the Prairie books. We read them aloud to our three oldest children and we’re in the process of reading them with our fourth child. We just read the chapter describing when the entire Ingalls family came down with malaria, or “fever ‘n’ ague” as they called it.
The family had settled near a creek that was infested with mosquitoes. All the settlers around the creek bottoms came down with malaria, though at the time (circa 1870) they did not know the disease was transmitted by mosquitoes. One of the settlers, Mrs. Scott, believed that malaria was caused by eating the watermelons that grew in the creek bottoms. She had empirical evidence: everyone who had eaten the melons contracted malaria. Charles Ingalls thought that was ridiculous. After he recovered from his attack of malaria, he went down to the creek and brought back a huge watermelon and ate it. His reasoning was that “Everybody knows that fever ‘n’ ague comes from breathing the night air.”
It’s easy to laugh at Mrs. Scott and Mr. Ingalls. What ignorant, superstitious people. But they were no more ignorant than their contemporaries, and both had good reasons for their beliefs. Mrs. Scott had observational data on her side. Ingalls was relying on the accepted wisdom of his day. (After all, “malaria” means “bad air.”)
People used to believe all kinds of things that are absurd now, particularly in regard to medicine. But they were also right about many things that are hard to enumerate now because we take them for granted. Stories of conventional wisdom being correct are not interesting, unless there was some challenge to that wisdom. The easiest examples of folk wisdom to recall may be the instances in which science initially contradicted folk wisdom but later confirmed it. For example, we have come back to believing that breast milk is best for babies and that a moderate amount of sunshine is good for you.
Mike Croucher wrote a post the other day explaining why he’s going to buy an iPad. He said that one of the objections to the iPad he’d heard was
Apple are evil because they take away control of how we use their devices.
I teased Mike that I would never say “Apple are evil.” On this side of the Atlantic we’d say “Apple is evil.” But in the UK it is accepted usage to say “Apple are evil.”
“Apple” is a collective noun when used to refer to Apple Inc. British English treats collective nouns as plural, but American English treats them as singular. Although the British usage sounds odd to my American ears, it makes sense just as much sense as the American convention. You could argue for plural verbs because corporations are made of individual people, or you could argue for singular verbs because the corporations act as a single entity. See Grammar Girl’s tip on collective nouns for more background.
By the way, I don’t believe Apple is evil. They’re just a company, no more or less virtuous than most other companies.
I have five Twitter accounts that send out one tip per day, including a new one I just added last week.
Regular expressions
@RegexTip started over today. It’s a cycle of tips for learning regular expressions. It sticks to the regular expression features common to Python, Perl, C#, and many other programming languages. This account posts Monday through Friday.
Keyboard shortcuts
@SansMouse gives one tip a day on using Windows without a mouse. By practicing one keyboard shortcut a day, you can get into the habit of using your mouse less and your keyboard more. This cycle of tips started over January 29 with the most common and most widely useful shortcuts. I’m also sprinkling in a few extra tips that are less well known. This account also posts Monday through Friday.
Math
I have three mathematical accounts. These post seven days a week.
@AlgebraFact, just started February 2. It will be a mixture of linear algebra, number theory, group theory, etc.
@ProbFact gives one fact per day from probability. Usually these facts are theorems, but sometimes they include a note on history or applications.
@AnalysisFact gives facts from real and complex analysis. The topics range from elementary to advanced.
What if I don’t use Twitter?
You can visit the page for a Twitter account just like any other web page. And every Twitter account has an RSS feed link allowing you to subscribe just as you would subscribe to a blog.
How do you write these?
I write up content for these accounts in bulk. I may sit down on a Saturday and come up with several weeks worth of tips. Then I use HootSuite to schedule the tips weeks in advance. Sometimes I’ll post something spontaneously, such as link to something relevant, but most of the work is done in advance. I use my personal Twitter account for live interaction.
I ran across a long rant from Steve Yegge this evening about junior programmers. In a nutshell, Yegge says they like to play around with metadata rather than getting real work done.
Here’s an insightful observation Yegge makes along the way.
And Haskell, OCaml and their ilk … try to force people to model everything. Programmers hate that. These languages will never, ever enjoy any substantial commercial success, for the exact same reason the Semantic Web is a failure. You can’t force people to provide metadata for everything they do. They’ll hate you.
What is the Carnival of Mathematics? Math bloggers submit articles they have written recently and each month a host writes a post linking to the submitted posts. The sister carnival, Math Teachers at Play, focuses on math education and on math up through high school level. For a more thorough description of the two carnivals and some FAQs, please see Mike Croucher’s article What is a Maths Carnival?
I’m taking a turn hosting this month. Tradition dictates that the host begin with some trivia about the number of the post. As this is the 62nd Carnival of Mathematics, here are a few facts about 62.
62 is the only number whose cube (238328) consists of 3 digits each occurring 2 times.
Louis Pasteur developed the first rabies vaccination at age 62.
And now onto the posts.
Math and science teacher Cory Poole sends in a video that he created along with his partners and students. The video features a 64-foot Sierpenski triangle about of 12,000 tortilla chips. Read more about the story of the video. Also, here are the bloopers from making the video.
St. Swithun’s day is a sort of British analog of America’s Groundhog Day. If it rains on St. Swithun’s day, it is supposed to rain for the next 40 days. Is there some truth to the legend? See Jon McLoone‘s article Mathematica Tests the St. Swithun’s Day Proverb posted at Wolfram Blog.
Rachel Thomas presents Beautiful symmetry provides glimpse into quantum world (link died). This article reports on a low-termperature experiment that implies that the exceptional Lie group E8 is at work.
Did you know that sine and cosine are equal for all x? Heather (Xi) submitted a pseudo-proof in A=B implies that 1=1, therefore? by her colleague TwoPi at 360. (If there is ever a 360th Carnival of Mathematics, Heather should host it.)
Update: The 360 blog has agreed to host the 360th Carnival of Mathematics, tentatively scheduled for December 1, 2034. (Mike, I hope it’s OK that I scheduled this date without consulting you. ;))
Annarita Ruberto from Matem@ticaMente presents the article “How heavy the fish?” The original post was written in Italian, and here is Google’s translation of the page into English.
Peter Rowlett from Travels in a Mathematical World presents Substitution ciphers: Ancient – Renaissance, video included below.
You can keep up with Carnival of Mathematics news on Twitter by following @CarnivalOfMath. You may also be interested in daily math facts on Twitter from @ProbFact (probability), @AnalysisFact (real and complex analysis), and @AlgebraFact (algebra and number theory).
