With counting being such an integral part of our everyday lives, it's nearly impossible to imagine a world without numbers. How could one trade goods without measuring the quantities being exchanged? How might a shepherd, unable to count sheep, learn that wolves were curtailing his flock? It is not surprising that there are clear remnants of counting systems in use by humans from as long as 30,000 years ago.
One with some background in anthropology will know that the bones of human skeletons (and other animals) were used by the earliest humans to make a myriad of bone tools. Tools for hunting and for building were commonplace, but archaeologists have also recovered ancient bone tools used for counting. The Ishango bone, a tally stick made from a baboon fibula, is thought to be more than 20,000 years old. In fact, the word tally has its origins in the Latin word talus, which literally means heel (think of the derivative word talon).
In one way or another, humans have been counting since our earliest days. However, it was only around 5000 years ago when the ancient Babylonians and Egyptians began the first endeavors into true mathematics. By a series of abstractions, counting led the numeral systems which led to arithmetic and eventually to algebra and geometry. Later, the Greeks laid the foundation for a still actively studied subject called Number Theory, which we'll discuss today.
Let's start with the natural numbers. That is, let $\mathbb{N}$ be the numbers $1, 2, 3, \dots$. For the remainder of this post, we will use the word number to mean a natural number unless otherwise stated.
If a number can be decomposed into a product of two non-unit numbers it is said to be composite. For example, the number $12$ is composite because it can be written as the product of $4$ and $3$; that is, $12 = 4 \cdot 3$. All remaining non-unit numbers are called prime.
Observe that the divisor $4$ of $12$ is also composite since $4 = 2 \cdot 2$. Thus, we can write $12$ as a product of primes $12 = 2 \cdot 2 \cdot 3$. This expression is called a prime factorization. The fact that every non-unit number has a unique prime factorization is known as the fundamental theorem of arithmetic.
That each number $n$ can be written as a unique factorization of primes $n = p_1 p_2 \dots$ leads one to ask questions about these prime numbers. How many are there? What is their distribution like? Do they follow a simple formula? Can we use an algorithm to test if a number is prime? Finding answers to this class of questions has been the focus of research in number theory for millennia and still to this day. We address the first question today and will discuss some elementary results regarding the distribution of primes.
The fact that there are infinitely many primes is known as Euclid's theorem. Every mathematician should know this theorem and Euclid's proof. It goes something like this:
Suppose, by way of contradiction, that there are finitely many primes. There is thus a largest prime $n$. Consider the number $k = 2 \cdot 3 \cdots (n-1) \cdot n + 1$. Clearly $k$ is larger than $n$ and hence, by our assumption, it must be divisible by a prime $p \leq n$. But, observe that $p$ cannot divide $k$ as it would leave a remainder of $1 / p$. This contradiction completes our proof, and there are thus infinitely many primes.
So, now that we know that there are infinitely many primes, where are they? A first step to addressing this question might be to ask how many primes tend to be less than a given number $n$. In other words, as we step through the natural numbers, how often do we come across a number that is prime?
Consider the number ${2n \choose n} = \frac{2n!}{n!n!}$. Observe that every prime number $p$ in the range $n \leq p < 2n$ is in the prime factorization of ${2n \choose n }$, and hence
\[\prod_{n \leq p < 2n} p \leq {2n \choose n}.\] We can furthermore bound ${2n \choose n}$ using Stirling's approximation (see this post) to show that ${2n \choose n} \leq 4^n$. Hence, it follows that
\[ \prod_{n \leq p < 2n} p \leq 4^n. \] We can use this inequality to bound the frequency of primes. Let $\pi(n)$ be the numbers of primes less than $n$. Since
\[n^{\pi(2n) - \pi(n)} \leq \prod_{n \leq p < 2n} p\] we can conclude that
\[n^{\pi(2n) - \pi(n)} \leq 4^n\] which simplifies to
\[\pi(2n) - \pi(n) \leq \log{4} \frac{n}{\log{n}}\] by taking the logarithm of both sides. By induction, it follows immediately that $\pi(n)$ is $O(\frac{n}{\log{n}})$.
We can use a similar approach to show an equivalent lower bound; that is, there are constants $c_1,c_2$ such that
\[ c_1 \frac{n}{\log{n}} \leq \pi(n) \leq c_2 \frac{n}{\log{n}}. \] One of the great achievements in mathematics in the 19th century was a proof that the inequality holds when $c_1 = c_2 = 1$ as $n$ tends to infinity. This result is known as the prime number theorem, which can be restated as
\[ \pi(x) \sim \frac{x}{\log{x}}. \]
The fun of prime numbers does not stop here. Understanding the distribution of primes is at the core of solving the Riemann hypothesis, one of the most famous outstanding problems in all of mathematics. Moreover, prime numbers have extremely practical applications (e.g. RSA encryption), where one requires algorithms to find large prime numbers. We will discuss some of these topics in later posts.
No comments :
Post a Comment