# Monthly Archives: July 2015

## A countability argument

Here is a countability argument that I like because it relies on almost nothing. Let $A$ be a ring.

Theorem. If $A$ is countable, then the polynomial ring $A[X]$ is countable.

Proof. Since $A$ is countable, there is an injection $f:A\to\mathbb N$. Let $p_0 be prime numbers and consider the map

\begin{aligned}g:A[X]&\to\mathbb N\\ a_0+a_1X+\cdots+a_nX^n&\mapsto p_0^{f(a_0)}p_1^{f(a_1)}\cdots p_n^{f(a_n)}.\end{aligned}

By unique factorisation in $\mathbb N$ it follows that $g$ is an injection. Thus $A[X]$ is countable. $\square$

We can use this to prove in a rather simple manner that

Corollary 1. The set $\mathbb A$ of all algebraic numbers is countable.

Proof. It follows from the above that $\mathbb Z[X]$ is countable. Let $\alpha\in\mathbb A$ be a root of some minimal polynomial $f_\alpha\in\mathbb Z[X]$. We can assign to each $\alpha\in\mathbb A$ a unique element $f\in\mathbb Z[X]$ as follows: if $\alpha_1(=\alpha),\dots,\alpha_n$ are the zeros of $f_\alpha\in\mathbb Z[X]$, assign $jf_\alpha$ to $\alpha_j$. This gives an injection from $\mathbb A$ to $\mathbb Z[X]$, as desired. $\square$

More generally,

Corollary 2. A countable union of countable sets is countable.

Proof. Let $A_0,A_1,\dots$ be countable sets. Then there are injections $A_i\to X^i\mathbb Z$ for $i=0,1,\dots$. Hence we have an injection

$\displaystyle\bigcup_{i=0}^\infty A_i\to \bigcup_{i=0}^\infty X^i\mathbb Z\subseteq\mathbb Z[X]$,

showing that $\bigcup_{i=0}^\infty A_i$ is countable. $\square$

Filed under Set theory

## Number of irreducible polynomials over a finite field

I and some friends just came up with this. (We came up with some ideas for the proof, after coming across the formula on the internet.) This is the coolest application of the Möbius inversion formula that I’ve seen so far.

Let $q$ be a prime power and $n$ any positive integer. We wish to count the number $C(n)$ of monic irreducible polynomials of degree $n$ over the finite field $\mathbb F_q$.

Note that the zeros of

$\displaystyle F_d(X):=\prod_{\deg(f)=d}f(X)$

are precisely the elements of degree $d$ over $\mathbb F_q$, where the product is taken over monic irreducible polynomials $f\in\mathbb F_q[X]$. Further, we have the following:

Lemma 1. Let $g\neq h$ be relatively prime polynomials over a field $k$. Then $g$ and $h$ have no common zeros.

Proof. Since $k[X]$ is a PID, there are polynomials $u,v\in k[X]$ such that $ug+vh=1$. If $\alpha$ is a common zero of $g$ and $h$ in some extension $K/k$, then $X-\alpha$ divides $1=ug+vh$ in $K[X]$, a contradiction. $\square$

Lemma 2. If $f$ is irreducible over a field $k$, then $f$ has distinct zeros.

Proof. Note that any multiple zero of $f$ must be a common zero of $f$ and its formal derivative $f'$. Since $f$ is irreducible over $k$, it follows that $f$ and $f'$ are relatively prime over $k$. Now apply lemma 1 to $f$ and $f'$. $\square$

It follows that the zeros of

$\displaystyle \prod_{d\mid n}F_d(X)$

are all distinct and are precisely the elements of the union of all the subfields of $\mathbb F_{q^n}$, which is just $\mathbb F_{q^n}$. This implies

$(*)\qquad\qquad\qquad\qquad\quad\displaystyle\prod_{d\mid n}F_d(X)=X^{q^n}-X$,

since $\mathbb F_{q^n}$ is the splitting field of $X^{q^n}-X$ over $\mathbb F_q$. Now a comparison of the degrees of both sides reveals that

$\displaystyle\sum_{d\mid n}dC(d)=q^n$.

Finally, Möbius inversion gives

$\displaystyle \boxed{C(n)=\frac 1n\sum_{d\mid n}\mu(d)q^{n/d}}$.

Filed under Combinatorics, Number theory

## Proof of a well-known identity involving Euler’s phi function

Let $\phi(n)$ be Euler’s function, i.e., the number of positive integers not exceeding $n$ that are coprime to $n$. A famous identity goes as follows:

$\displaystyle\sum_{d\mid n}\phi(d)=n$

where the sum is taken over all positive divisors of $n$. Here is a counting argument for a proof.

Let $S=\{1,\dots,n\}$. For each divisor $d$ of $n$, let us count the number of elements $m\in S$ with $\gcd(m,n)=d$. When $d=1$, this is just $\phi(n)$. What about when $d=2$? If $n$ is odd then clearly there is no such $m$. Otherwise, $\gcd(m,n)=2$ implies that $m$ and $n$ must both be even. Moreover, this happens iff $\gcd(m/2,n/2)=1$. Hence, as before, the number of such $m$ is $\phi(n/2)$.

This works in general: for any $d\mid n$, the number of elements $m\in S$ such that $\gcd(m,n)=d$ is $\phi(n/d)$. So summing $\phi(n/d)$ over all $d\mid n$, which is the same as summing $\phi(d)$ over all $d\mid n$, gives the total number of elements of $S$, which is $n$. This proves the desired result.

This begs for a generalisation. I will add it here when I come up with one. (I really need to sleep now!)