Tuesday, August 31, 2010

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).

T! his 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 ma! thematics, 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 divisibl! e by any prime not on the list. This result is trivial if one ! knows th at 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-W! horf.

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.


prime factorization

No comments:

Post a Comment