Tuesday, May 5, 2020

The Prime Numbers

The Ancient Greeks loved to classify numbers.  Numbers that could be represented as the ratio of two whole numbers were rational numbers.  Numbers such as $\sqrt{2}$ which could not were irrational numbers.  A perfect number, such as 6,  is equal to the sum of its proper divisorsAmicable numbers, such as 220 and 284, are pairs of numbers where each is the sum of the proper divisors of the other.

Without a doubt, the most important of these classifications was the concept of a prime number.  A prime number is any positive integer that has exactly two divisors.  $5$ is a prime number but $8$ is not.  $1$ is not, $0$ is not, and negative numbers are not.  While the definition is clear, one might immediately ask, why should one care.

There are two big reasons why we should care.  If mathematics is the study of patterns, some of the most amazing and surprising patterns relate to prime numbers.  Investigating prime numbers turns out to be a royal path to deep mathematical insights.  For example, one of the most important problems in mathematics today is the Reimann Hypothesis which concerns the relationship between prime numbers and the complex zeta function.  By the way, if anyone solves it, there's a million dollar prize waiting to be claimed.

The other reason to care about primes is that their properties have become fundamental to the very running of global eCommerce.   Prime numbers start out very common and become surprisingly rare as one starts to consider very large numbers.  It turns out that determining whether a number is prime can take a significant computation effort if the prime is large enough.  In fact, one of the great pursuits of spare computation capacity is the search for new primes.  Each time a new largest prime is discovered, it is worthy of a news headline.  For example, here is a news headline from NPR in 2018.

Because there are an infinite number of primes (more about that later) and because it is possible to find primes up to the limits of current computational power, they have become an excellent foundation for security.  Indeed, this is the foundation of public key encryption.  For example, RSA, one of the earliest public key encryptions is based on the difficulty of factoring the product of two large prime numbers.

But let's start smaller.  Let's focus on fundamental patterns.  For me, there are two incredibly surprising facts about primes that can serve as a starting point.  Of course, one or both may not be surprising to you.  First, each positive number is characterized by a unique combination of primes.

If I take any set of primes (for example $2,3,5$) at a specific power (for this example, we'll choose the power of $1$), then there is ONLY one number equal to their product.  In this case, $30$.  This property is called unique factorization.  The natural numbers are characterized by unique factorization.  If there is a prime that divides one but not the other number, they are not equal.  If there is a power of a prime that divides one but not the other,  they are not equal.    From this perspective, they provide an opportunity to simplify reasoning about very large numbers.  If I have two very complicated equations which I want to compare, I can quickly see that they are not equal if a prime divides one but does not the other.  For example, I can say without a doubt for all integer values of $x$ and $y$, the following will never be equal:

$$4^x \ne 7^y$$

I mentioned in a previous post that natural numbers are just one of many types of numbers.  One of the most surprising facts for me is that not all number systems are characterized by unique factorization.  In other words, there are numbers where they are products of different primes and yet they are still equal.  With our intuitions about the concept of number from the whole numbers and the integers, this may seem impossible.  If don't believe me, you can check it out for yourself.  For example, not all quadratic integers are characterized by unique factorization.  Even the great genius Leonhard Euler (pronounced Oiler) was not beyond making a bad assumption about unique factorization.  If you are interested, I provide the details of his mistake here.

Unique factorization is such as an important properties of integers that the theorem that establishes unique factorization is called the Fundamental Theorem of Arithmetic.

In my next blog post, I will walk through a simple proof of this fundamental theorem.

Sunday, May 3, 2020

The Natural Numbers

A number, as a concept, is a surprisingly ambiguous term.  There are whole numbers, fractions, negative numbers, real numbers, irrational numbers, imaginary numbers, and transcendental numbers.  It may not be intuitively obvious what they all have in common.  There are also mathematical operations that are not defined and are probably not numbers at all such as $\dfrac{1}{0}$ (see here) or $0^0$ (see here).  The concept of infinity is another difficult to nail down concept.  Is it a number?  It turns out that there are different types of infinity.  For example, the number of counting numbers (1, 2, 3, ...) is less than the number of points in an infinitely divisible line (see here).  I will tackle these more advanced topics later

Historically, the concept of number began with the activities of counting and measuring.  Counting led to the whole numbers which did not include 0 at the very beginning and measuring led to simple fractions (more complicated fractions require a more complicated number system).  

The most important historical breakthroughs which we pretty much take for granted today are:
In mathematics, the set of positive whole numbers and zero is called the Natural Numbers and is represented by N;.    When combined with the set of negative numbers, it becomes the sets of Integers which is represented by Z. (Why Z, it comes from the German word Zahlen for 'numbers')

The study of the properties of Integers is called number theory and this will be the primary focus of this blog.    

In my view, the most surprising and deepest insight in all of mathematics is that natural numbers, despite their appearances of being the simplest of mathematical objects, contain some of the most challenging and important problems known to mathematics.  

These challenges have led to the development of public key cryptography which today powers the global economy.  Innovations such as block chain, which build on top of the complexity of mathematical problems, will further transform our economic, social, and political institutions that depend on hierarchy and centralized authority.  

One popular definition of Mathematics is "the study of patterns" (see here for an interesting overview).  Many of the most surprising and profound patterns can be found in Number Theory.

Saturday, May 2, 2020

A Change In Direction

Starting today, I will update this blog on a regular basis.  I will use this blog as an exploration of the fundamental properties of primes as well as an attempt to generalize ideas.

If the past is any indication, my attempts will usually reflect a misunderstanding of a fundamental or a mistake in one step of my argument.  So, when I make my attempts, I will make sure to provide a thorough explanation of the mistakes that I made.

I will organize the blog posts as an attempt at a book.  So, as the blog proceeds, I will re-edit previous blog posts in the attempt to create a consistent narrative.  So, in theory, a person could start on the first blog post and proceed from there or start on what will become the table of contents and jump from there into any topic of interest.

I will start with very elementary ideas.  This will be a very personal journey.  So, I will proceed from the elementary ideas based on my interests and my attempt to generalize standard results.

I hope that others will find this interesting.  I warn everyone that while I am a serious amateur, I will make mistakes.  These blog posts will be primarily interesting to other amateurs.  For serious math students, I strongly recommend going to the blogs of professional mathematicians such as Terence Tao and Andrew Granville who are two of the most amazing writers and brilliant mathematicians.

Since I am an amateur, I will also make every effort to call out my sources and so that if my argument is unclear, it is possible to go to the source to find a professional explanation.

Most importantly, enjoy.  The journey is the purpose.  :-)


Tuesday, February 25, 2020

There are at least $n$ primes between $n$ and $n^2$

Theorem 1: $\pi(2^k) \le 3\dfrac{2^k}{k} $

(1)  For $k \le 5$:

$\pi(2^1) = 1 \le 2\dfrac{2^1}{1} = 4$
$\pi(2^2)  = 2 \le 2\dfrac{ 2^2}{2} = 4$
$\pi(2^3) = 4 \le 2\dfrac{2^3}{3} = \dfrac{16}{3} > 5$
$\pi(2^4) = 6 \le 2\dfrac{2^4}{4} = 8$
$\pi(2^5) = 11 \le 2\dfrac{2^5}{5} = \dfrac{64}{5} > 12$

(2)  Assume it is true up to some $k \ge 5$

(3) $\pi(2n) - \pi(n) \le (2n)\dfrac{\log 2}{\log n}$ since:

(a) $2^{2n} = \sum\limits_{i \le 2n}{{2n}\choose i}$

(b) $n^{\pi(2n) - \pi(n)} \le p^{\pi(2n) - \pi(n)} \le \prod\limits_{n < p \le2n}p \le {{2n}\choose{n}} \le 2^{2n}$

(c) $(\pi(2n) - \pi(n))\log n \le (2n)\log 2$

(d) $\pi(2n) - \pi(n) \le (2n)\dfrac{\log 2}{\log n}$

(4) $\pi(2^{k+1}) - \pi(2^k) \le (2^{k+1})\dfrac{\log 2}{\log 2^{k}}$ so that $\pi(2^{k+1}) \le \pi(2^k) + (2^{k+1})\dfrac{\log 2}{\log 2^{k}}$

(5)  $\log 2^{k} = k\log 2$ so that $\dfrac{1}{k} = \dfrac{\log 2}{\log 2^{k}}$

(6)  $5k+5 < 6k$ so that $\dfrac{5}{k} < \dfrac{6}{k+1}$

(7)  $\pi(2^{k+1}) \le \pi(2^k) + \dfrac{2^{k+1}}{k} \le \dfrac{3\times2^k}{k} + \dfrac{2\times2^k}{k} = \dfrac{5\times2^k}{k} \le \dfrac{3\times2^{k+1}}{k+1}$


Corollary: $\pi(x) \le 6 \log 2 \dfrac{x}{\log x}$

(1)  For $x \le 4, \pi(x) \le 6\log 2 \dfrac{x}{\log x}$

$\pi(2) = 1 \le 6\log2\dfrac{2}{\log 2}$ since $\log 2 < 12\log 2$

$\pi(3) = 2 \le 6\log 2\dfrac{3}{\log 3}$ since $2\log 3 < 18\log 2$

$\pi(4) = 2 \le 6\log 2\dfrac{4}{\log 4}$ since $2\log 4 < 24\log 2$

(2)  There exists $k$ such that $2^k \le x \le 2^{k+1}$

(3)  $\dfrac{1}{k+1} < \dfrac{\log 2}{\log 2^{k}}$ since $\log 2^k < (k+1)(\log 2)$

(4)  $\pi(x) \le \pi(2^{k+1}) \le 3\dfrac{2^{k+1}}{k+1} \le 6\dfrac{2^{k}}{k+1} < 6\log 2\dfrac{2^k}{\log 2^k} \le 6\log 2\dfrac{x}{\log x}$

Let $v_p(n)$ be the maximum power of $p$ that divides $n$

Lemma 1: $v_p(n!) = \sum\limits_{m \ge 1}\left\lfloor\dfrac{n}{p^m}\right\rfloor$

There are $\left\lfloor\dfrac{n!}{p}\right\rfloor$ instances of numbers divisible by $p$.

There are $\left\lfloor\dfrac{n!}{p^2}\right\rfloor$ instances of numbers divisible by $p^2$

And so on.

Lemma 2: $\lfloor{2x}\rfloor - 2\lfloor{x}\rfloor \in \{0, 1\}$

(1)  Let $\{x\}$ be the fractional part of $x$

(2)  If $\{x\} < \dfrac{1}{2}$, then $\lfloor{2x}\rfloor - 2\lfloor{x}\rfloor = 0$

(3)  If $\{x\} \ge \dfrac{1}{2}$, then $\lfloor{2x}\rfloor - 2\lfloor{x}\rfloor = 1$

Theorem 2: $\pi(x) \ge \dfrac{\log 2}{2}\dfrac{x}{\log x}$

(1) If $m > \dfrac{\log 2n}{\log p}$, then $\left\lfloor\dfrac{2n}{p^m}\right\rfloor - 2\left\lfloor\dfrac{n}{p^m}\right\rfloor = 0$

(2)  $v_p\left({{2n}\choose{n}}\right) = \sum\limits_{m \ge 1}\left(\left\lfloor\dfrac{2n}{p^m}\right\rfloor - 2\left\lfloor\dfrac{n}{p^m}\right\rfloor\right) \le
\left\lfloor\dfrac{\log 2n}{\log p}\right\rfloor$

(3)  $\dfrac{2^{2n}}{2n} \le {{2n}\choose{n}}$

(4) $2n\log 2 - \log 2n \le \log {{2n}\choose{n}} \le \sum\limits_{p \le 2n}\left\lfloor\dfrac{\log 2n}{\log p}\right\rfloor\log p \le \sum\limits_{p \le 2n}\log 2n = \pi(2n)\log 2n$

(5) $\pi(2n) \ge \log 2\dfrac{2n}{\log 2n} - 1$

(6)  For $2 \le x \le 16, \pi(x) \ge \dfrac{\log 2}{2}\dfrac{x}{\log x}$

  • $\pi(2) = 1 = \dfrac{\log 2}{2}\dfrac{2}{\log 2} = 1$
  • $\pi(3) = 2  > \dfrac{3}{2} > \dfrac{\log 2}{2}\dfrac{3}{\log 3}$
  • $\pi(4) = 2 =  \dfrac{4}{2} > \dfrac{\log 2}{2}\dfrac{4}{\log 4}$
  • $\pi(5) = 3 \ge \dfrac{5}{2} > \dfrac{\log 2}{2}\dfrac{5}{\log 5}$
  • $\pi(6) = 3 = \dfrac{6}{2} > \dfrac{\log 2}{2}\dfrac{6}{\log 6}$
  • $\pi(7) = 4 > \dfrac{7}{2} > \dfrac{\log 2}{2}\dfrac{7}{\log 7}$
  • $\pi(8) = 4 = \dfrac{8}{2} > \dfrac{\log 2}{2}\dfrac{8}{\log 8}$
  • $\pi(9) = 4  > \dfrac{3}{2} = \dfrac{\log 2}{3\log 2}\dfrac{9}{2} > \dfrac{\log 2}{2}\dfrac{9}{\log 9}$
  • $\pi(10) =4 > \dfrac{5}{3} = \dfrac{\log 2}{3\log 2}\dfrac{10}{2} > \dfrac{\log 2}{2}\dfrac{10}{\log 10}$
  • $\pi(11)=5 > \dfrac{11}{6} = \dfrac{\log 2}{3 \log 2}\dfrac{11}{2} > \dfrac{\log 2}{2}\dfrac{11}{\log 11}$
  • $\pi(12)=5 > 2 = \dfrac{\log 2}{3 \log 2}\dfrac{12}{2} > \dfrac{\log 2}{2}\dfrac{12}{\log 12}$
  • $\pi(13)=6 > \dfrac{13}{6} = \dfrac{\log 2}{3 \log 2}\dfrac{13}{2} > \dfrac{\log 2}{2}\dfrac{13}{\log 13}$
  • $\pi(14)=6 > \dfrac{7}{3} = \dfrac{\log 2}{3 \log 2}\dfrac{14}{2} > \dfrac{\log 2}{2}\dfrac{14}{\log 14}$
  • $\pi(15)=6 > \dfrac{5}{2} = \dfrac{\log 2}{3 \log 2}\dfrac{15}{2} > \dfrac{\log 2}{2}\dfrac{15}{\log 15}$
  • $\pi(16)=6 > \dfrac{8}{3} = \dfrac{\log 2}{3 \log 2}\dfrac{16}{2} > \dfrac{\log 2}{2}\dfrac{16}{\log 16}$


(7)  There exists $n$ such that $16 \le 2n < x \le 2n+2$

(8)  $\dfrac{2n}{\log 2n} - \dfrac{n+1}{\log 2n} = \dfrac{n-1}{\log 2n} \ge \dfrac{7}{\log 16} = \dfrac{7}{4\log 2} > \dfrac{4}{4\log 2} = \dfrac{1}{\log 2}$

(9) $\pi(x) \ge \pi(2n) \ge \log 2\dfrac{2n}{\log 2n} - 1 = \dfrac{2n\log 2 - \log 2n}{\log 2n} = \dfrac{\log\frac{2^{2n}}{2n}}{\log 2n}$

(10) for $n=8$, $2^6 > 8$

(11)  $2(2^{n-2}) = 2^{(n+1)-2} > 2n > n+1$ so that $\dfrac{2^{n-2}}{n} > 1$ and $\dfrac{2^{n-1}}{2n} > 1$ and $\dfrac{2^{2n}}{2n} > 2^{n+1}$

(12)  $\dfrac{\log\frac{2^{2n}}{2n}}{\log 2n} \ge \dfrac{\log 2^{n+1}}{\log (2n+2)} = \dfrac{(n+1)\log 2}{\log (2n+2)}$

(13)  Since $n+1 = \dfrac{2n+2}{2} \ge \dfrac{x}{2}$, it follows that $\dfrac{(n+1)\log 2}{\log (2n+2)} \ge \dfrac{x\log 2}{2\log x}$

Corollary: For $46 \ge n \ge 4$, there are at least $n$ primes between $n$ and $n^2$

(1)  For $n \ge 28$, then:

  • Between $4$ and $16$, there are 4 primes: $\{5, 7, 11, 13\}$
  • Between $5$ and $25$, there are 6 primes: $\{7,11,13,17,19,23\}$
  • Between $6$ and $36$, there are more than $6$ primes: $\{7,11,13,17,19,23,\dots\}$
  • Between $7$ and $49$, there are more than $7$ primes: $\{11,13, 17, 19, 23, 29, 31,\dots\}$
  • Between $8$ and $64$, there are more than $8$ primes: $\{11, 13,17,19,23,29,31,37,\dots\}$
  • Between $9$ and $81$, there are more than $9$ primes: $\{11,13,17,19,23,29,31,37,41,\dots\}$
  • Between $10$ and $100$, there are more than $10$ primes: $\{11,13,17,19,23,29,31,37,41,43,dotts\}$
  • Between $11$ and $121$, there are more than $11$ primes: $\{13,17,19,23,29,31,37,41,43,47,53,\dots\}$
  • Between $12$ and $144$, there are more than $12$ primes: $\{13,17,19,23,29,31,37,41,43,47,53,59,\dots\}$
  • Between $13$ and $169$, there are more than $13$ primes: $\{17,19,23,29,31,37,41,43,47,53,59,61,67,\dots\}$
  • Between $14$ and $196$, there are more than $14$ primes: $\{17,19,23,29,31,37,41,43,47,53,59,61,67,71,\dots\}$
  • Between $15$ and $225$, there are more than $15$ primes: $\{17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,\dots\}$
  • Between $16$ and $256$, there are more than $16$ primes: $\{17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,\dots\}$
  • Between $17$ and $289$, there are more than $17$ primes: $\{19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,\dots\}$
  • Between $18$ and $324$, there are more than $18$ primes: $\{19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,\dots\}$
  • Between $19$ and $361$, there are more than $19$ primes: $\{23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,\dots\}$
  • Between $20$ and $400$, there are more than $20$ primes: $\{23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,\dots\}$
  • Between $21$ and $441$, there are more than $21$ primes, $\{23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,\dots\}$
  • Between $22$ and $484$, there are more than $22$ primes, $\{23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113\dots\}$
  • Between $23$ and $529$, there are more than $23$ primes, $\{29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,\dots\}$
  • Between $24$ and $576$, there are more than $24$ primes, $\{29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,\dots\}$
  • Between $25$ and $625$, there are more than $25$ primes, $\{29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,\dots\}$
  • Betwen $26$ and $676$, there are more than $26$ primes, $\{29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,\dots\}$
  • Between $27$ and $729$, there are more than $27$ primes, $\$\{29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,\dots\}$


(2)  $\pi(n^2) - \pi(n) \ge \dfrac{(n^2)\log 2}{2\log (n^2)} - \dfrac{(6n)\log 2}{\log n} = \dfrac{(n^2)\log 2}{4\log (n)} - \dfrac{(6n)\log 2}{\log n} = \dfrac{(\frac{n}{4} - 6)(n\log 2)}{\log n}$


Thursday, January 29, 2015

An infinitude of primes

Euclid provided a proof for the infinitude of primes.  The following proof is based on his argument:

Theorem 1:  There are an infinite number of primes

(1)  Assume that $p_n$ is the largest prime.
(2)  Let $q = p_n! + 1$
(3)  Since $q > p_n$, $q$ cannot be a prime (by our assumption).
(4)  So, therefore a prime $p$ divides $q$
(5)  But if $p \le p_n$, then $p | p_n!$ and $p | (p_n! + 1) - p_n! = 1$ which is impossible.
(6)  Therefore, we have a contradiction since $p > p_n$ but $p$ is a prime.

QED


Sunday, December 28, 2014

Introduction

The purpose of this blog will be for me to focus on primes and the fundamental theorems related to them.

These will represent my notes.  The goal is to present the fundamental ideas of number theory in as clear a manner as I can without requiring any background beyond standard arithmetic, a genuine interest in math, and an openness to the concepts involved.

The content will be taken straight from number theory text books, classic math papers, and forums on math web sites.

My favorite math web site for asking questions about mathematics is math.stackexchange.com.  If you haven't been to this site, I encourage you to visit if you have any questions.