Sunday, March 8, 2009

Euclid, Unique Prime Factorization and Sapir-Whorf

Unique prime factorization is a basic fact about the positive integers that many of us learn from a young age. Start with any positive integer and express it is as a product of prime numbers, say 105=3*5*7. This prime factorization is unique. That is to say, except for rearranging the order of these primes, there is no other way to express 105 as a product of prime numbers. Thus, for example, I don’t need to do any calculations to know that 105 is not equal to 11 *13. We can do this for any positive integer and regardless of what integer we start with we will get a unique result. (Another way of stating this is that if two people are both given the same number and told to factor it into primes, they will always get the same result as each other).

This idea is often called the "Fundamental Theorem of Arithmetic." Unique factorization is taught to children as young as 6th grade. When I have helped to teach number theory to high school students at PROMYS, many students take unique prime factorization for granted. Indeed, it often takes effort to convince them that the statement needs to be proved and is not just an obvious fact.

Despite the “obviousness” of unique prime factorization to the modern mind, the ancient Greeks did not know about unique prime factorization. This apparent failure of the ancient Greeks is well known to historians

of mathematics, but not known by many mathematicians. The only math text I am aware of which mentions this is Hardy and Wright's “Introduction to the Theory of Numbers. Euclid in his seminal work “The Elements” has many results that are close to unique prime factorization. For example, Euclid was able to show that, if a is relatively prime to b and relatively prime to c, then a is relatively prime the produc of b and c. This result is almost as powerful as unique prime factorization, but it is not all the way there.

Why did the ancient Greeks not have this result? Simply put, they lacked the words to express the statement. To a mathematician of ancient Greece, there was no way to say "take a bunch of numbers and take their product." A product of two numbers x and y was easy; it was the area of a rectangle with sides of length x and y. Similarly, a product of three numbers -- x, y and z -- was the volume of a box with side lengths x,y and z. Fixed in this geometric mindset and with no concept of higher dimensions, the ancient Greeks could not talk about general products. Being unable to talk about general products, they apparently did not think about them.

To be sure, they groped towards this result. For example, Euclid proved a result that in modern language would be stated as follows: if n is the least positive integer divisible by some list of distinct primes p1,p2.p3… pk, then n is not divisible by any prime not on the list. This result is trivial if one knows that prime factorization is unique this is obvious since one can simply has n=p1 * p2... *pk.

Apparently, the ancient Greeks, including Archimedes, Euclid and Diophantus, along with many lesser luminaries could not conceive of this idea because they lacked the language to express it. This failure is closely related to a hypothesis in psychology and linguistics known as the Sapir-Whorf hypothesis. Sapir-Whorf states that our language constrains our thought processes. There are different degrees of Sapir-Whorf. Very strong versions of the hypothesis are obviously false (if they were to be believed, translation between languages would be impossible) while very weak versions border on the trivial. This failure of the ancient Greeks is evidence for some strong form of Sapir-Whorf.

There's a lesson here for people other than psychologists. We cannot know how much we are missing simply because we lack the language to express an idea. Mathematicians over the last three centuries have taken this idea very seriously and spent much time trying to find optimal notation to express ideas. Yet, we cannot tell if there is some fundamental idea that we simply do not notice or appreciate because we lack the necessary language.

8 comments:

sniffnoy said...

What really strikes me as funny about this is that they seem to have had no trouble with the idea of a *sum* of arbitrarily many numbers, e.g. for defining "perfect number". Obviously this is more easily visualized - take a bunch of lengths and and lie them end to end - but when you're applying to number-theoretic things which are not really geometrically relevant in the first place, it seems strange that you wouldn't make the generalization.

E said...

How do you know that it wasn't lacking the concept that caused the inability to talk about the concept, rather than the other way around?

Joshua said...

E, that's a valid question. The reply I'd give is that more often than not in mathematics notation comes before a concept. For example, in the 19th century, there was a lot of discussion about the value of the infinite series 1 - 1 + 1 - 1 + 1...
The primary reason this confusion occurred is because they had a notation but no concept behind it. One sees this in other examples as well. Euler for example engaged in much formal manipulation without any clear concept behind it. Look at his proof for the Euler product of the Riemann zeta function if you want a good example of this.

Dan said...

Doesn't Euclid's proof of the infinitude of primes contradict your claim? It clearly involves an arbitrarily large finite product (of primes).

Joshua said...

As I understand it, Euclid's original proof doesn't actually take the product of all the primes on the list and add 1. Instead he took a number that was a divisible by each of the primes on the list and added one.

Brad said...

Euclid's original proof actually only deals with 3 primes at a time:
Quoting the translation:
"Let A, B, and C be the assigned prime numbers. I say that there are more prime numbers than A, B, and C. " etc...

His final result is abstracted to the general case, so I guess you could still say he was thinking about multiplying more than 3 together, but his proof is only for 3.

It is the modern translations that restate it in the general case from the beginning:
Let E=p1xp2xp3x...xpn ... etc.

Joshua said...

Thanks Brad for clarifying that for those of us who can't read greek.

Anonymous said...

Hey I did a video on this for kids your students might like:
http://www.youtube.com/watch?v=5kl28hmhin0