Determining if a number $n$ is a prime number or not is an important problem in computational number theory. Two simple ways of proving primality rely on the prime factorizations of $n-1$ and $n+1$. In general finding these factorizations is probably a harder problem than testing the primality of $n$, so the methods are only applicable in special cases, but are they are interesting nonetheless.

At a high level, the $n-1$ method works by showing that a subgroup of $\newcommand{\Z}{\mathbb{Z}}\Z^*_n$ is so large that $n$ must be prime. Specifically, a subgroup of order $n-1$ is demonstrated, which implies that $\Z_n^*$ is as large as possible, namely the full set of nonzero residues $\{1,2,\dotsc,n-1\}$; if even one element was missing then there would be less than $n-1$ elements in $\Z_n^*$. But $\Z_n^*=\{1,2,\dotsc,n-1\}$ means that every positive integer strictly less than $n$ is coprime to $n$, and so $n$ is prime.

To show that $\Z_n^*$ contains a subgroup of size $n-1$, we find an element $a\in\Z_n^*$ whose order is $n-1$ (such an element is called a primitive root). To do this, we show that

\[ a^{n-1} \equiv 1 \pmod{n} \tag{1} \]

and

\[ a^{(n-1)/p} \not\equiv 1 \pmod{n} \tag{2} \]

for all primes $p$ which divide $n-1$. This is enough to show that the order of $a$ is $n-1$; if the true order was $r<n-1$ then using Bézout’s identity one would be able to derive $a^{\gcd(r,n-1)}\equiv1\pmod{n}$ and this would contradict (2) for some $p$.

When $n$ is prime, there isn’t any known efficient algorithm which is guaranteed to find a primitive root $a$ satisfying (1) and (2), but in practice this isn’t a concern. In fact, there are $\varphi(n-1)=\Theta(n/\ln\ln n)$ primitive roots (where $\varphi$ denotes Euler’s totient function), so if one simply tests if random $a$ satisfies (1) and (2) then one should quickly find one which works, and thereby prove that $n$ is prime. As mentioned, the real problem with applying this method in practice is finding the primes $p$ which divide $n-1$.

Incidentally, when $n$ isn’t prime, this is usually easy to show since condition (1) will often fail to hold, and all primes satisfy (1) for all $a\in\Z_n^*$. However, some composite numbers still satisfy (1) for all $a\in\Z_n^*$. In such a case a more stringent form of (1) can be used to prove compositeness, and this method can be employed in practice since it only requires the “evenness factorization” $n-1=2^r\cdot m$ with $m$ odd, which is simple to compute.

The $n+1$ method is similar to the $n-1$ method, except it works in the group $(\Z_n[\sqrt{d}])^*$, where $d$ satisfies $(\frac{d}{n})=-1$, i.e., $d$ is not a quadratic residue mod $n$. We assume that $n$ is odd (otherwise the problem is trivial), so that in practice $d$ can be found by computing the Jacobi symbol $(\frac{d}{n})$ for multiple values of $d$ until one works. Note that when $n$ is prime we have $\newcommand{\F}{\mathbb{F}}\Z_n[\sqrt{d}]\cong\F_{n^2}$, the finite field of size $n^2$, so there still exist primitive roots $a$ which generate $(\Z_n[\sqrt{d}])^*$. We’ll denote the conjugate of $a$ by $\bar{a}$, so if $a:=b+c\sqrt{d}$ with $b$, $c\in\Z_n$ then $\bar{a}=b-c\sqrt{d}$.

As you might expect in relation to the above, the $n+1$ method finds a subgroup of $(\Z_n[\sqrt{d}])^*$ of size $n+1$ by finding an $a\in(\Z_n[\sqrt{d}])^*$ which has order $n+1$. Actually, we need something a bit stronger than this; we need to show

\[ a^{n+1} \equiv 1 \pmod{n} \tag{3} \]

and

\[ \gcd((a^{(n+1)/p}-1)(\bar{a}^{(n+1)/p}-1),n)=1 \tag{4} \]

for all primes $p$ which divide $n+1$. Condition (4) not only implies that $a^{(n+1)/p} \not\equiv 1 \pmod{n}$, but also that $a^{(n+1)/p} \not\equiv 1 \pmod{q}$ where $q$ is any prime divisor of $n$. To see that this, we show the contrapositive. Suppose that $q$ is a prime divisor of $n$ and that $q\mid a^{(n+1)/p}-1$.¹ It follows that $q$ also divides $(a^{(n+1)/p}-1)(\bar{a}^{(n+1)/p}-1)\in\Z$, and thus divides the gcd in (4), so (4) fails to hold.

Since condition (3) implies that $a^{n+1}\equiv1\pmod{q}$ and condition (4) implies that $a^{(n+1)/p}\not\equiv1\pmod{q}$, just like before one knows that $a\pmod{q}$ has order $n+1$. In particular, there must be at least $n+1$ elements in $(\Z_q[\sqrt{d}])^*$.

Toward a contradiction, suppose that (3) and (4) hold and that $n$ is not prime. Let $q$ be the smallest prime divisor of $n$, so that $q^2\leq n$. As we just saw, $a\pmod{q}$ has order $n+1$, so we get the lower bound

\[ n+1 \leq \lvert(\Z_q[\sqrt{d}])^*\rvert . \]

However, $\Z_q[\sqrt{d}]$ has $q^2$ elements, and so

\[ \lvert(\Z_q[\sqrt{d}])^*\rvert \leq q^2-1 \leq n-1 , \]

which contradicts the lower bound. Thus $n$ must in fact be prime.

When $n$ is prime, an $a$ which satisfies (3) and (4) can be found by taking a primitive root of $\F_{n^2}$ and raising it to the power $n-1$, since in this case $(a^{n-1})^{n+1}\equiv1\pmod{n}$ and $n$ will not divide $(a^{n-1})^{(n+1)/p}-1$ or its conjugate. As mentioned, there isn’t a guaranteed procedure to find a primitive root, but since there are $\varphi(n^2-1)=\Theta(n^2/\ln\ln n)$ of them, in practice it shouldn’t be too hard to find one; the sticking point is finding the factorization of $n+1$.

Incidentally, the $n+1$ test is often presented using Lucas sequences rather than $\F_{n^2}$. But that’s a topic for another post.

Previously I discussed the prime number theorem and proved Chebyshev’s weak form of it, namely that $\pi(n)=\Theta(n/\ln n)$. Chebyshev was also able to show the conditional result that if

\[ \lim_{n\to\infty}\frac{\pi(n)}{n/\ln n} \]

exists, then its value is $1$. While this might seem to be quite close to the prime number theorem, there is no especially good reason why the limit should exist. In fact, in a sense this result makes the limit less likely to exist; after our previous proof all one knows is that the limit lies between $0.34$ and $4.16$ (supposing it exists), but now it can have only one possible value!

Some new functions

Before proving this result, it is useful to introduce the von Mangoldt function defined by

\[ \Lambda(n) := \begin{cases}
\ln p & \text{if $n\geq2$ is a perfect power of the prime $p$} \\
0 & \text{otherwise}
\end{cases} \]

and the Chebyshev function defined as the partial sums of the von Mangoldt function,

\[ \psi(n) := \sum_{m\leq n}\Lambda(m) . \]

For each prime $p$ there are $\lfloor\log_p n\rfloor$ perfect powers of $p$ less than or equal to $n$ and strictly greater than $1$, so an alternate way of writing this function is

\[ \psi(n) = \sum_{p\leq n}\lfloor\log_p n\rfloor\ln p . \]

Upper bound on $\psi(n)$

By removing the floor and using the logarithm change-of-base formula one gets an upper bound on $\psi(n)$:

\[ \psi(n) \leq \sum_{p\leq n}(\log_p n)\ln p = \sum_{p\leq n}\ln n = \pi(n)\ln n \]

In particular, using the previously established $\pi(n)=O(n/\ln n)$ this implies

\[ \psi(n) = O(n) . \tag{1} \]

Lower bound on $\psi(n)$

By removing every term in the sum defining $\psi(n)$ except when $m$ is a prime larger than $n’$, and using $\pi(n’)=O(n’/\ln n’)$, one gets a similar lower bound on $\psi(n)$:

\begin{align*}
\psi(n) &\geq \sum_{n'<p\leq n}\ln p \\
&\geq \sum_{n'<p\leq n}\ln n’ \\
&= \ln n’\bigl(\pi(n)-\pi(n’)\bigr) \\
&= \pi(n)\ln n’ + O(n’)
\end{align*}

Now, this holds for all $n'<n$, so take $n’:=n/\ln n$ (it is actually not necessary to ensure that $n’$ is an integer). Then the lower bound becomes

\[ \psi(n) \geq \pi(n)(\ln n-\ln\ln n) + O\Bigl(\frac{n}{\ln n}\Bigr) = \pi(n)\ln(n) + O\Bigl(\frac{n\ln\ln n}{\ln n}\Bigr) . \]

Combining the bounds on $\psi(n)$

Since the error term here is $o(n)$, combining with the upper bound $\psi(n)\leq\pi(n)\ln n$ we get the nice relation

\[ \psi(n) = \pi(n)\ln n + o(n) . \]

Dividing by $n$, we find that

\[ \frac{\psi(n)}{n} = \frac{\pi(n)}{n/\ln n} + o(1) . \tag{2} \]

This is a very strong asymptotic relation between $\psi(n)/n$ and $\pi(n)/(n/\ln n)$; it says that the difference between these functions goes to zero as $n$ increases. So as $n$ gets large, the functions essentially become identical.

The first estimation of $\ln(n!)$

The proof now proceeds by estimating the quantity $\ln(n!)$ in two different ways. The first way is a weak form of Stirling’s approximation:

\[ \ln(n!) = n \ln n + O(n) \tag{3} \]

A simple proof of this proceeds by estimating $\newcommand{\d}{\,\mathrm{d}}\int_1^n\ln t\d t$ by rectangles of width $1$:

Note that $\ln(n!)=\sum_{m=1}^\infty \ln m$, so the area formed by the rectangles is exactly the quantity to estimate in (3).

As shown in the diagram, this quantity is closely under-estimated by $\int_1^n\ln t\d t$ (the dark green area); the amount of under-estimation is given by the light green area. Although this is difficult to evaluate exactly, by sliding the light green triangle-like shapes to the right they all fit inside the final rectangle, which has area $\ln n$. Thus the dark green area under-estimates the area of the rectangles by at most $\ln n$, and we have

\begin{align*}
\ln(n!) &= \int_1^n\ln t\d t + O(\ln n) \\
&= \bigl[t\ln n – t\bigr]_1^n + O(\ln n) \\
&= n\ln n \mathbin- n + O(\ln n)
\end{align*}

which is a stronger form of (3).

The second estimation of $\ln(n!)$

The second method of estimation relies on the prime factorization of $n!$. Recall we had already determined the exponent of $p$ in the prime factorization (also known as the $p$-adic order) of $n!$ to be $\nu_p(n!) := \sum_{k=1}^\infty\lfloor n/p^k\rfloor$. Using this, we have:

\begin{align*}
\ln(n!) &= \ln\Bigl(\prod_{p\leq n}p^{\nu_p(n!)}\Bigr) \\
&= \sum_{p\leq n}\nu_p(n!)\ln p \\
&= \sum_{p^k\leq n}\biggl\lfloor\frac{n}{p^k}\biggr\rfloor\ln p \\
&= \sum_{m\leq n}\Bigl\lfloor\frac{n}{m}\Bigr\rfloor\Lambda(m) \\
&= \sum_{m\leq n}\Bigl(\frac{n}{m} + O(1)\Bigl)\Lambda(m) \\
&= n\sum_{m\leq n}\frac{\Lambda(m)}{m} + O\bigl(\psi(n)\bigr)
\end{align*}

We can evaluate $\sum_{m\leq n}\Lambda(m)/m$ using a trick known as Abel’s summation formula:

\begin{align*}
\sum_{m\leq n}\frac{\Lambda(m)}{m} &= \sum_{m\leq n}\frac{\psi(m)-\psi(m-1)}{m} \\
&= \sum_{m\leq n}\frac{\psi(m)}{m} \mathbin- \sum_{m\leq n-1}\frac{\psi(m)}{m+1} \\
&= \sum_{m\leq n-1}\psi(m)\Bigl(\frac{1}{m}-\frac{1}{m+1}\Bigr) + \frac{\psi(n)}{n} \\
&= \sum_{m\leq n-1}\psi(m)\Bigl[-\frac{1}{t}\Bigr]_m^{m+1} + \frac{\psi(n)}{n} \\
%&= \sum_{m\leq n-1}\psi(m)\int_m^{m+1}\frac{\!\d t}{t^2} + \frac{\psi(n)}{n} \\
&= \sum_{m\leq n-1}\int_m^{m+1}\frac{\psi(t)}{t^2}\!\d t + \frac{\psi(n)}{n} \\
&= \int_1^n\frac{\psi(t)}{t^2}\!\d t + \frac{\psi(n)}{n}
\end{align*}

Most of this is just algebra; the fact that $\psi(m)=\psi(t)$ for $t\in[m,m+1)$ justifies pulling $\psi(m)$ into the integral. Putting these together and using (1), we get our second estimate on $\ln(n!)$:

\[ \ln(n!) = n\int_1^n\frac{\psi(t)}{t^2}\!\d t + O(n) \tag{4} \]

Putting the estimates together

Combining (3) and (4) and dividing by $n$ we find that

\[ \int_1^n\frac{\psi(t)}{t^2}\!\d t = \ln n + O(1) . \tag{5} \]

Using (5) to derive the result

Suppose that the limit in question exists and equals $1+\epsilon$ for some $\epsilon>0$. Then, taking the limit as $n\to\infty$ in (2), we have

\[ \lim_{n\to\infty}\frac{\psi(n)}{n} = \lim_{n\to\infty}\frac{\pi(n)}{n/\ln n} = 1 + \epsilon . \]

It follows that there is some $N$ such that $\psi(t)/t\geq 1+\epsilon/2$ for all $t\geq N$. Now, $N$ only depends on the constant $\epsilon$, so taking $N$ fixed as $n\to\infty$ we have
\[ \int_1^n\frac{\psi(t)}{t^2}\d t \geq \int_N^n\frac{\psi(t)}{t^2}\d t \geq \int_N^n\frac{1+\epsilon/2}{t}\d t = \Bigl(1+\frac{\epsilon}{2}\Bigr)\ln n + O(1) . \]

This contradicts (5), since the coefficient on the leading term $\ln n$ is larger than $1$; for example, this implies that $\int_1^n\psi(t)/t^2\d t-\ln n=\Omega(\ln n)$, which is not $O(1)$ as given by (5).

Similarly, if the limit in question exists and equals $1-\epsilon$ for some $\epsilon>0$ then we have $\lim_{n\to\infty}\psi(n)/n = 1-\epsilon$, so there exists some $N$ such that $\psi(t)/t\leq1-\epsilon/2$ for all $t\geq N$. Then as $n\to\infty$ we have

\[ \int_1^n\frac{\psi(t)}{t^2}\d t \leq O(1) + \int_N^n\frac{1-\epsilon/2}{t}\d t = \Bigl(1-\frac{\epsilon}{2}\Bigr)\ln n + O(1) , \]

which contradicts (5), since this says that the coefficient on the leading term $\ln n$ is less than $1$.

Therefore, we conclude that if $\lim_{n\to\infty}\pi(n)/(n/\ln n)$ exists it cannot be strictly larger than or strictly less than $1$, so it must be exactly $1$.

Here’s another interesting question regarding the convergence of a series. Does

\[ \sum_{n=1}^\infty\frac{\cos n}{n} \]

converge or diverge?

The question I meant to ask on Sunday was whether $\sum_{m,n=1}^\infty1/(m^2+n^2)^2$ converges or diverges, so I’ll give my solution to that problem now. In fact, the methodology closely resembles the divergence proof I gave for the alternate sum, even though this sum converges.

Since all terms in the sum are positive, the sum either converges absolutely or diverges (the sum cannot be conditionally convergent). In either case the terms of the sum may be rearranged without affecting the convergence. For suppose the sum diverges but converges for some rearrangement: since the terms of the rearranged sum are still positive, the rearranged sum would have to converge absolutely, and therefore converge for all rearrangements, contradicting the supposed diverging arrangement.

Therefore we can rearrange the terms as we please; in particular, we can sort the terms in decreasing order, which has the effect of grouping together all terms of the form $1/k^2$ where $k$ is a sum of two squares. The term $1/k^2$ will appear in the sum once for each solution of $m^2+n^2=k$ in positive integers $m$, $n$.¹

For our purposes it is sufficient to note there are at most $\sqrt{k}$ solutions to $m^2+n^2=k$. This follows since we know that $1\leq m\leq\sqrt{k}$ and for each value of $m$ there is at most one solution; the only possible value of $n$ which could work is $\sqrt{k-m^2}$.

The argument proceeds as follows:

\[ \newcommand{\N}{\mathbb{N}}\begin{align*}
\sum_{m,n\in\N}\frac{1}{(m^2+n^2)^2} &= \sum_{k=2}^\infty\sum_{\substack{m,n\in\N\\m^2+n^2=k}}\frac{1}{k^2} \\
&\leq \sum_{k=2}^\infty\frac{\sqrt{k}}{k^2} \\
&= \sum_{k=2}^\infty\frac{1}{k^{3/2}} \\
&= \zeta(3/2)-1
\end{align*} \]

The final sum converges since it is a $p$-series (truncated). By the comparison test, the sum in question also converges.

Previously I asked if the summation $\sum_{m,n=1}^\infty1/(m^2+n^2)$ converges or diverges. Actually, the I intended the denominator of the summation term to be $(m^2+n^2)^2$. But never mind, let’s solve the problem as given. To do this, we’ll employ the comparison test.

First, note that

\[ m^2+n^2 \leq m^2+2mn+n^2 = (m+n)^2 , \]

so $1/(m^2+n^2)\geq1/(m+n)^2$.

Next, assume the sum converges; since all terms are positive the sum absolutely converges and the terms may be rearranged without affecting its value. In particular, we rearrange the terms in decreasing order, by grouping all terms equal to $1/k^2$ together for each possible value of $k$.

Finally, we use the fact that there are exactly $k-1$ solutions to $m+n=k$ in positive integers $m$, $n$. Putting it all together, the argument goes as follows:

\begin{align*}
\newcommand{\N}{\mathbb{N}}
\sum_{m,n\in\N}\frac{1}{m^2+n^2} &\geq \sum_{m,n\in\N}\frac{1}{(m+n)^2} \\
&= \sum_{k=2}^\infty\sum_{\substack{m,n\in\N\\m+n=k}}\frac{1}{k^2} \\
&= \sum_{k=2}^\infty\frac{k-1}{k^2} \\
&\geq \frac{1}{2}\sum_{k=2}^\infty\frac{1}{k} \\
&= \infty
\end{align*}

The final inequality just uses $k-1\geq k/2$ for $k\geq2$ and we are left with a harmonic series, which diverges. By the comparison test the original sum diverges; this contradicts the assumption that it converges, so the sum really does diverge, as required.

Next up, I’ll show the question I intended to ask: does $\sum_{m,n=1}^\infty1/(m^2+n^2)^2$ converge or diverge?

Here’s another cute math problem. Does

\[ \sum_{m=1}^\infty\sum_{n=1}^\infty\frac{1}{m^2+n^2} \]

converge or diverge? I’ll post my solution in a day or two.

A month ago I posed the problem of showing that a monic $\newcommand{\Z}{\mathbb{Z}}f\in\Z[x]$ is squarefree over $\newcommand{\C}{\mathbb{C}}\C$ if and only if it is squarefree over $\Z$.

One direction is straightforward, although the easiest way to see it is to consider the contrapositive. If $f$ is not squarefree over $\Z$ then its factorization over $\Z$ is of the form $hg^2$ where $h$, $g\in\Z[x]$ and $g$ is nonconstant. Since $f$ can only factor farther in $\C$ it follows that $f$ is also not squarefree over $\C$; in particular any root $\alpha\in\C$ of $g$ will have multiplicity at least $2$ in the factorization of $f$ in $\C$.

Thus if $f$ is squarefree over $\C$ it is also squarefree over $\Z$. Conversely, if $f$ is not squarefree over $\C$ then it has some multiple root $\alpha\in\C$ and its factorization is of the form $k\cdot(x-\alpha)^2$, so $f’=k'(x-\alpha)^2+2(x-\alpha)k$ and $\alpha$ is also a root of $f’$.

Since $f$ and $f’$ are polynomials with integer coefficients with $\alpha$ as a root, the minimal polynomial $g$ of $\alpha$ over $\newcommand{\Q}{\mathbb{Q}}\Q$ divides both $f$ and $f’$. In particular, there must be some $h\in\Q[x]$ such that $f=gh$. Then $f’=g’h+h’g$ and since $g\mid f’$ and $g\mid h’g$ we must have $g\mid g’h$. However, $g\nmid g’$ since $g’$ has a smaller degree than $g$ and is $g’$ is nonzero (as the characteristic of $\Q$ is $0$).

Being a minimal polynomial, $g$ is irreducible, and it is also prime as $\Q[x]$ is a UFD. Thus from $g\mid g’h$ and $g\nmid g’$ we must have $g\mid h$, i.e., $g^2\mid f$ and $f$ is not squarefree over $\Q$. By Gauss’ Lemma the factorization $f=g^2(h/g)$ over $\Q$ may actually be taken to be over $\Z$ (by replacing $g$ and $h$ with their primitive parts), so $f$ is not squarefree over $\Z$, as required.

Note that the requirement that $f$ be monic is necessary (at least, the content of $f$ should be squarefree). For example, if $f:=4$ then $f=2\cdot2$ is not squarefree over $\Z$, but is technically squarefree over $\C$, since $4$ is a unit in $\C$!

Here’s an interesting polynomial property that arose in my recent number theory project.

Let $f$ be a monic polynomial with integer coefficients. Show that $f$ is squarefree over $\mathbb{C}$ if and only if $f$ is squarefree over $\mathbb{Z}$.

The function $\pi(n)$ counts the number of primes $p$ in the range $1\leq p\leq n$. One of the most spectacular theorems in mathematics is the so-called prime number theorem, which states that

\[ \lim_{n\to\infty}\Bigl(\pi(n)\Bigm/\frac{n}{\ln n}\Bigr) = 1 . \]

This is a strong condition on the asymptotic behaviour of $\pi(n)$ as $n$ increases without bound—unlike some asymptotic results, even the base of the logarithm is significant here.

Last year I worked through a proof of the prime number theorem. Two of the main results used were Euler’s product and Cauchy’s residue theorem—it was breathtaking. It still hasn’t completely “coalesced” in my head, but I periodically revisit it. Today I want to prove a weaker form of the prime number theorem, namely that

\[ \pi(n) = \Theta\Bigl(\frac{n}{\ln n}\Bigr) . \]

This uses asymptotic notation, and says that the growth rate of $\pi(n)$ is eventually within a constant factor of $n/\ln n$.

The proof is by Chebyshev and proceeds by finding the following bounds on the central binomial coefficient $\binom{2n}{n}$:

\begin{align}
2^n \leq \binom{2n}{n} &\leq 4^n \tag{1} \\
n^{\pi(2n)-\pi(n)} \leq \binom{2n}{n} &\leq (2n)^{\pi(2n)} \tag{2}
\end{align}

Upper bound of (1)

Using the binomial theorem to expand $(1+1)^{2n}$ gives

\[ 4^n = 2^{2n} = (1+1)^{2n} = \sum_{i=0}^{2n}\binom{2n}{i} \geq \binom{2n}{n} \]

since all the terms in the sum are positive.

Lower bound of (1)

However, note that the central term ($i=n$) in the sum is the largest (to go from term $i$ to term $i+1$ you multiply by $\frac{2n-i}{i+1}$, which is greater than $1$ until $i\geq n$), so we have:

\[ 4^n = 2^{2n} = (1+1)^{2n} = \sum_{i=0}^{2n}\binom{2n}{i} \leq (2n+1)\binom{2n}{n} \]

The required inequality follows after dividing by $2^n$ and using the fact that $2n+1\leq2^n$ (which holds for $n\geq3$, however the required inequality may explicitly be checked to hold for $n<3$).

Lower bound of (2)

Examining the prime factorization of $\binom{2n}{n}=(2n)!/(n!)^2$, we see that it contains all the primes $p$ in the range $n<p\leq 2n$, since they appear in the numerator but not in the denominator. There are $\pi(2n)-\pi(n)$ primes in this range, and they are all larger than $n$, so it follows that:

\[ \binom{2n}{n} \geq \prod_{n<p\leq 2n} p \geq n^{\pi(2n)-\pi(n)} \]

Upper bound of (2)

Note that there are $\lfloor n/p\rfloor$ multiples of $p$ in the range $1\leq p\leq n$. We can use this fact to determine the exponent on $p$ in the prime factorization of $n!$. There will be $\lfloor n/p\rfloor$ factors of $p$ in $n!$, but we also need to count the additional $\lfloor n/p^2\rfloor$ factors of $p$ which are contributed by multiples of $p^2$, and in general an additional $\lfloor n/p^k\rfloor$ factors of $p$ contributed by multiples of $p^k$. The exponent of $p$ in the prime factorization of $n!$ is thus

\[ \sum_{k=1}^\infty \biggl\lfloor\frac{n}{p^k}\biggr\rfloor , \]

where the sum is zero for $k>\log_p n$. It follows that the exponent of $p$ in the prime factorization of $(2n)!/(n!)^2$ is

\[ \sum_{k=1}^{\lfloor\log_p(2n)\rfloor} \biggl(\biggl\lfloor\frac{2n}{p^k}\biggr\rfloor – 2\biggl\lfloor\frac{n}{p^k}\biggr\rfloor\biggr) . \]

An interesting fact about the function $\lfloor 2x\rfloor-2\lfloor x\rfloor$ is that it is either $0$ or $1$ (plot it and you’ll see why), so this sum is actually at most $\lfloor\log_p(2n)\rfloor$. Since $\binom{2n}{n}$ only contains primes $p$ in the range $1\leq p\leq 2n$, it follows that:

\[ \binom{2n}{n} \leq \prod_{1\leq p\leq 2n}p^{\log_p(2n)} = \prod_{1\leq p\leq 2n} 2n = (2n)^{\pi(2n)} \]

Using the bounds

Putting both (1) and (2) together and taking logarithms yields the following bounds:

\begin{gather}
n\ln 2 \leq \pi(2n)\ln(2n) \tag{3} \\
(\pi(2n)-\pi(n))\ln n \leq n\ln 4 \tag{4}
\end{gather}

The lower bound on $\pi(n)$

From (3) we have that

\[ \pi(2n) \geq \frac{\ln2}{2}\frac{2n}{\ln(2n)} , \]

which is shows the required lower bound for even numbers. But it can be slightly modified to work for odd numbers as well (note that $\ln(2n)\leq\ln(2n+1)$):

\[ \pi(2n+1) \geq \pi(2n) \geq \frac{2n+1}{2n+1}\frac{\ln2}{2}\frac{2n}{\ln(2n)} \geq \frac{2n}{2n+1}\frac{\ln2}{2}\frac{2n+1}{\ln(2n+1)} \]

Since $2n/(2n+1)$ is lower bounded by a constant (e.g., $2/3$) for all positive $n$, this shows that $\pi(n)=\Omega(n/\ln n)$.

The upper bound on $\pi(n)$

First we will show the required upper bound for powers of two. That way we will be able to apply (4) not only on $n$ but also recursively on half of $n$ until $n=1$ is reached. However, to get a nice telescoping sum we modify (4) by subtracting $\pi(n)\ln(n/2)$ from both sides. After rearranging and simplifying with $\ln n-\ln(n/2)=\ln2$, we find

\[ \pi(2n)\ln n – \pi(n)\ln(n/2) \leq n\ln4 + \pi(n)\ln 2 \leq (3\ln 2)n \tag{5} \]

since $\pi(n)\leq n$ and $\ln4+\ln2=3\ln2$.

We now sum together (5) used on $n{,}~n/2{,}~\dotsc{,}~1$ to get

\[ \sum_{i=0}^{\log_2 n}\biggl(\pi\Bigl(\frac{n}{2^{i-1}}\Bigr)\ln\Bigl(\frac{n}{2^i}\Bigr)-\pi\Bigl(\frac{n}{2^i}\Bigr)\ln\Bigl(\frac{n}{2^{i+1}}\Bigr)\biggr) \leq (3\ln 2)\sum_{i=0}^{\log_2 n}\frac{n}{2^i} . \]

However, by telescoping the left sum is equal to $\pi(2n)\ln n$ and by the formula for the summation of a geometric series the right sum is at most $(3\ln2)2n$. In other words, when $n$ is a power of two we have

\[ \pi(2n) \leq (6\ln2)\frac{n}{\ln n} , \]

and the required bound follows using $\frac{n}{\ln n}<\frac{2n}{\ln(2n)}$, a consequence of the fact that $\frac{n}{\ln n}$ is an increasing function (for $n\geq3$, although the required bound still holds for $n<3$).

As before, a slight modification shows the bound holds for all numbers, not just powers of two. Let $m$ be an arbitrary integer in the range $n\leq m<2n$ where $n$ is a power of two. Then

\[ \pi(m) \leq \pi(2n) \leq (6\ln 2)\frac{n}{\ln n} \leq (6\ln 2)\frac{m}{\ln m} \]

which shows that $\pi(n)=O(n/\ln n)$.

Yesterday I had a discussion with a friend about computing minimal polynomials. For example, say you are given algebraic numbers $\alpha$ and $\beta$ as specified by minimal polynomials which have degrees $n$ and $m$. How do you compute the minimal polynomial of $\alpha+\beta$, for example?

The method I was taught, which seems to be fairly standard (e.g., see Dummit and Foote Chapter 13.2) is the following:

Multiply $\alpha+\beta$ by $\alpha^i\beta^j$ for each $i=0{,}~1{,}~\dotsc{,}~n-1$ and $j=0{,}~1{,}~\dotsc{,}~m-1$, and use the minimal polynomials of $\alpha$ and $\beta$ to reduce the resulting expressions to linear combinations of $\alpha^i\beta^j$ (again with $0\leq i<n$ and $0\leq j<m$). In other words, what you are doing is computing a matrix $M$ which satisfies

\[ (\alpha+\beta)\left[\alpha^i\beta^j\right]_{i,j} = M\left[\alpha^i\beta^j\right]_{i,j} \]

where $[\alpha^i\beta^j]_{i,j}$ is a column vector containing the $\alpha^i\beta^j$.

From this we see that $\alpha+\beta$ is an eigenvalue of $M$ and therefore is a root of the characteristic polynomial $p_M$ of $M$. If $p_M$ is irreducible then it will be the minimal polynomial of $\alpha+\beta$, but in general the minimal polynomial will divide $p_M$, and so it will be necessary to factor $p_M$.

However, once $p_M$ has been factored, how does one tell which factor is the required minimal polynomial? The obvious answer is to evaluate each factor at $\alpha+\beta$ and see which one gives zero. “You could do that numerically”, my friend says, and I respond with “…or symbolically”. But then he asks if I will always be able to determine if the symbolic expression is zero or not. Well, I hadn’t thought of that, and I admitted I wasn’t sure, but claimed “anything you can do numerically I can do symbolically!”

I spent several hours yesterday trying to solve that problem, but eventually had to go to bed. This morning, after looking in Cohen I found the following passage:

…it does not make sense to ask which of the irreducible factors $\alpha+\beta$ is a root of, if we do not specify embeddings in $\mathbb{C}$…

Wait, what? I got excited as I realized I had just uncovered a misconception of mine!

Note that if the conjugates of $\alpha$ are $\alpha_i$ then they are all “symbolically identical”: $\mathbb{Q}(\alpha_i)$ is isomorphic for each conjugate. From that, I had assumed that the values of $\alpha_i+\beta_j$ would also be symbolically identical for all conjugates of $\alpha$ and $\beta$. Not true! As a trivial counterexample, if $\alpha$ is a root of $x^3-2$ and $\beta$ is a root of $x^3+2$ then two possible values for $\alpha+\beta$ are $0$ and $\sqrt[3]{2}\sqrt{3}i$, and these have very different algebraic behaviour.

So the whole problem of computing the minimal polynomial of $\alpha+\beta$ was not well defined unless you specify which roots $\alpha$, $\beta$ you are talking about—for example, by specifying them numerically.