Today is the 60th anniversary of Israel's independence. Alon has a very nice post on the occasion, describing what his father did on the day Israel gained independence. In reading that post, I was reminded of the story of another friend's father's memory of Indian independence.
My friend's father and his family lived in Lahore (in present day Pakistan). Being Hindu, when news of independence and the partition of India and Pakistan arrived, it was clear that they had to flee Lahore. But how to flee safely---atrocities were being committed in the name of religion. Turns out that they had a loyal Muslim driver who offered to drive them across the border. So the whole family hid in the back of a lorry (truck) and the Muslim driver drove it toward the border. Along the way a mob stopped the lorry and asked to search the back for fleeing Hindus. But the driver stared down the mob, using his own religious persuasion to convince the mob that there was no need to look in the back. Fortunately, the mob let the lorry go without a search and they escaped to India. My friend's father went on to become a very senior government official in India.
For a powerful dramatization of Lahore right before and during independence, I strongly recommend the movie 1947 Earth starring Aamir Khan and Nandita Das. It's a story told through the eyes of a little Parsi girl growing up in Lahore (the Parsis were viewed as being neutral in the Hindu-Muslim conflict). Aamir Khan is absolutely amazing and the climactic scene in the movie haunts me to this day.
Thursday, May 8, 2008
Sunday, May 4, 2008
What is Mathematics: Prime numbers
This is the second in the series of posts on the book What is Mathematics. This post is about some important results on prime numbers.
One of the most basic results is that there are infinitely many primes. As a kid in middle or high school, I remember being fascinated by the proof of this result. The proof, given by Euclid, is straightforward and is a great example of an "indirect proof". You start by assuming that there are only a finite number of primes. Then consider the number, n, that is one more than the product of all these primes. Since n is larger than all the primes, it is not prime, and must have prime factors. But n is clearly not divisible by any of these primes (by construction, dividing by any prime leaves a remainder of 1). This leads to a contradiction, so that our assumption must be false and there are, indeed, infinitely many primes.
The fundamental theorem of arithmetic (again given by Euclid) states that every integer greater than 1 can be factored into a product of primes in only one way. The book has a very nice proof of this theorem (again an "indirect proof" that starts by assuming that the prime factorization is not unique).
There have been various attempts to find formulae that produce primes, though no such general formula has been found. However, the prime number theorem provides a remarkable formula for the distribution of primes. Let An denote the number of primes from 1 to n. Then the prime number theorem states that (An / n) tends to (1 / log n) as n tends to infinity (where log n is the natural logarithm of n). The proof of this theorem requires advanced methods and is not discussed in the book (though there's apparently some discussion toward the end).
The book introduces some interesting open problems related to primes. Of these, the most famous is Goldbach's conjecture. This conjecture states that any even number greater than 2 can be expressed as a sum of two primes. Goldbach proposed this in 1742 in a letter to Euler, asking Euler to prove or disprove it. Empirically the result appears to be true. However, while much progress has been made, the proof remains elusive.
Finally, a fundamentally important theorem due to Fermat (also called Fermat's little theorem) states that if p is a prime that does not divide the integer a then
where (mod p) says that the congruence (≡) is modulo p (i.e., both sides have the same remainder when divided by p). The proof in the book is based on observing that no pair of multiples of a of the form ka (where 1 ≤ k < p) can be congruent modulo p. For if k1a ≡ k2a (mod p), then (k1 - k2)a ≡ 0 (mod p) which implies that a is divisible by p (since both k1 and k2 are less than p). Similarly, ka cannot be congruent to 0 (mod p). Thus, each of the above (p - 1) multiples of a are congruent to (a distinct) one of 1, 2, ..., (p - 1), and therefore
from which the result follows.
On a side note, Fermat's little theorem plays a central role in the Miller-Rabin primality test. Primality testing is essential to the RSA public key cryptosystem that is used to secure various web-based activities like ecommerce, online banking, and online stock trading using https.
One of the most basic results is that there are infinitely many primes. As a kid in middle or high school, I remember being fascinated by the proof of this result. The proof, given by Euclid, is straightforward and is a great example of an "indirect proof". You start by assuming that there are only a finite number of primes. Then consider the number, n, that is one more than the product of all these primes. Since n is larger than all the primes, it is not prime, and must have prime factors. But n is clearly not divisible by any of these primes (by construction, dividing by any prime leaves a remainder of 1). This leads to a contradiction, so that our assumption must be false and there are, indeed, infinitely many primes.
The fundamental theorem of arithmetic (again given by Euclid) states that every integer greater than 1 can be factored into a product of primes in only one way. The book has a very nice proof of this theorem (again an "indirect proof" that starts by assuming that the prime factorization is not unique).
There have been various attempts to find formulae that produce primes, though no such general formula has been found. However, the prime number theorem provides a remarkable formula for the distribution of primes. Let An denote the number of primes from 1 to n. Then the prime number theorem states that (An / n) tends to (1 / log n) as n tends to infinity (where log n is the natural logarithm of n). The proof of this theorem requires advanced methods and is not discussed in the book (though there's apparently some discussion toward the end).
The book introduces some interesting open problems related to primes. Of these, the most famous is Goldbach's conjecture. This conjecture states that any even number greater than 2 can be expressed as a sum of two primes. Goldbach proposed this in 1742 in a letter to Euler, asking Euler to prove or disprove it. Empirically the result appears to be true. However, while much progress has been made, the proof remains elusive.
Finally, a fundamentally important theorem due to Fermat (also called Fermat's little theorem) states that if p is a prime that does not divide the integer a then
ap - 1 ≡ 1 (mod p)
where (mod p) says that the congruence (≡) is modulo p (i.e., both sides have the same remainder when divided by p). The proof in the book is based on observing that no pair of multiples of a of the form ka (where 1 ≤ k < p) can be congruent modulo p. For if k1a ≡ k2a (mod p), then (k1 - k2)a ≡ 0 (mod p) which implies that a is divisible by p (since both k1 and k2 are less than p). Similarly, ka cannot be congruent to 0 (mod p). Thus, each of the above (p - 1) multiples of a are congruent to (a distinct) one of 1, 2, ..., (p - 1), and therefore
1 × 2 × ... × (p - 1) ap - 1 ≡ 1 × 2 × ... × (p - 1) (mod p)
from which the result follows.
On a side note, Fermat's little theorem plays a central role in the Miller-Rabin primality test. Primality testing is essential to the RSA public key cryptosystem that is used to secure various web-based activities like ecommerce, online banking, and online stock trading using https.
Friday, May 2, 2008
Better hair care
There's been a lot of talk about how electronic health care records can dramatically transform and improve the health care industry. But Alon has a better idea: hair care records!
Securing your wireless network
In a previous post I questioned the utility of securing your wireless network. Nonetheless, suppose you do want to secure it. Ars Technica has this great post on the ABCs of securing your wireless network. Check it out if you're at all concerned about the issue. Here's the bottom line:
Generally speaking, any router that supports WPA is "good enough" in terms of its overall security. WEP, as we've previously stated, is an "only if you must" protocol, but it's still a better option than transmitting in the clear.
WEP (Wired Equivalent Privacy) is an older security standard than WPA (Wi-Fi Protected Access). While there are different flavors of WPA available, Ars Technica notes that the differences between them are small compared to the improvement of WPA over WEP. So use WPA (unless you want your Nintendo DS to connect to your network--the DS doesn't support WPA).
Early in the article they debunk various myths that:
...do more harm than good by lulling the end-user into a false sense of security.
These include hiding or changing the SSID (the name of your wireless network), disabling DHCP, or filtering MAC addresses. This last method happens to be the one I use currently. From a security perspective:
The problem with filtering by MAC address, however, is that these addresses are easily faked and readily detected by anyone using appropriate monitoring software.
However, it may be appropriate given my earlier post about not really needing security:
...filtering MAC addresses is the only one with even a minimal level of value. MAC address filtering can keep obnoxious and non-tech-savvy neighbors from easily freeloading on your wireless network, but it won't do much else.
Generally speaking, any router that supports WPA is "good enough" in terms of its overall security. WEP, as we've previously stated, is an "only if you must" protocol, but it's still a better option than transmitting in the clear.
WEP (Wired Equivalent Privacy) is an older security standard than WPA (Wi-Fi Protected Access). While there are different flavors of WPA available, Ars Technica notes that the differences between them are small compared to the improvement of WPA over WEP. So use WPA (unless you want your Nintendo DS to connect to your network--the DS doesn't support WPA).
Early in the article they debunk various myths that:
...do more harm than good by lulling the end-user into a false sense of security.
These include hiding or changing the SSID (the name of your wireless network), disabling DHCP, or filtering MAC addresses. This last method happens to be the one I use currently. From a security perspective:
The problem with filtering by MAC address, however, is that these addresses are easily faked and readily detected by anyone using appropriate monitoring software.
However, it may be appropriate given my earlier post about not really needing security:
...filtering MAC addresses is the only one with even a minimal level of value. MAC address filtering can keep obnoxious and non-tech-savvy neighbors from easily freeloading on your wireless network, but it won't do much else.
Sunday, April 20, 2008
What is Mathematics: Mathematical Induction
This is the first in my series on some interesting and important techniques and results described in the book What is Mathematics. The first chapter introduces the natural numbers, 1, 2, 3, ... In Leopold Kronecker's words: "God created the natural numbers; everything else is man's handiwork."
After introducing the basics of natural numbers, the authors introduce the fundamental technique of the principle of mathematical induction. This is a very simple, yet powerful, method for proving theorems about an infinite sequence of cases. In its simplest form, suppose you want to prove that a property An for all positive integers n (e.g., An might be the proposition that (1 + p)n ≥ (1 + np) for any p > -1). The principle of mathematical induction states that you can prove this using two steps:
The proposition that (1 + p)n ≥ (1 + np) for any p > -1 can be easily established using mathematical induction (this will prove to be a useful little inequality).
The principle of mathematical induction needs to be applied with care. The authors demonstrate the pitfalls of this method with the following "proof" that all numbers are, in fact, equal!
Let An be the statement "If a and b are any two positive integers such that max(a, b) = n, then a = b". The base case is certainly true: when n = 1, a and b must both be 1 (being positive integers). For the inductive case, assume Ar holds and let a and b be such that max(a, b) = r + 1. Clearly, then max(a - 1, b - 1) = r, and hence by assumption a - 1 = b - 1. Hence a = b. So An holds for all n. In particular, for any a and b, if max(a, b) = r, then Ar holds and hence for any a and b, a = b!
Can you see the hole in this proof?
After introducing the basics of natural numbers, the authors introduce the fundamental technique of the principle of mathematical induction. This is a very simple, yet powerful, method for proving theorems about an infinite sequence of cases. In its simplest form, suppose you want to prove that a property An for all positive integers n (e.g., An might be the proposition that (1 + p)n ≥ (1 + np) for any p > -1). The principle of mathematical induction states that you can prove this using two steps:
- First, you prove that A1 holds, i.e., the property holds when n = 1 (often called the base case).
- Next, for every r ≥ 1 you show that if Ar holds then Ar+1 also holds (this is often called the inductive step).
The proposition that (1 + p)n ≥ (1 + np) for any p > -1 can be easily established using mathematical induction (this will prove to be a useful little inequality).
The principle of mathematical induction needs to be applied with care. The authors demonstrate the pitfalls of this method with the following "proof" that all numbers are, in fact, equal!
Let An be the statement "If a and b are any two positive integers such that max(a, b) = n, then a = b". The base case is certainly true: when n = 1, a and b must both be 1 (being positive integers). For the inductive case, assume Ar holds and let a and b be such that max(a, b) = r + 1. Clearly, then max(a - 1, b - 1) = r, and hence by assumption a - 1 = b - 1. Hence a = b. So An holds for all n. In particular, for any a and b, if max(a, b) = r, then Ar holds and hence for any a and b, a = b!
Can you see the hole in this proof?
What is Mathematics
In a previous post I mentioned that I was going to get a copy of the book What is Mathematics by Richard Courant and Herbert Robbins. Well, I've now got a copy of it and I'm reading through it. And I'm thoroughly enjoying it! The book is a mathematics book---it talks about the techniques and results in mathematics, often with proofs (at least when the proofs don't involve advanced techniques). But it's written in a very conversational style---as if Courant was sitting across the dining table from you and sharing with you his love of mathematics. (That imagery makes sense only if you can imagine discussing mathematics at the dinner table...:-)
As I read this book, I thought I'd put together a series of posts highlighting some of the most interesting and important methods and theorems that I encounter. Part of my purpose is to share this with you (and encourage you to get the book); but the other part is to summarize it for my own benefit. I'll keep this post updated with the list of all posts in this series. Here are the posts.
As I read this book, I thought I'd put together a series of posts highlighting some of the most interesting and important methods and theorems that I encounter. Part of my purpose is to share this with you (and encourage you to get the book); but the other part is to summarize it for my own benefit. I'll keep this post updated with the list of all posts in this series. Here are the posts.
Thursday, April 3, 2008
International Bar-Code of Life
My friend Alon has a great post about his recent visit to Costa Rica where he learned about the International Bar-Code of Life Project from his host Dan Janzen, a Kyoto Prize winning biologist.
Subscribe to:
Posts (Atom)