Tag Archives: field

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

Leave a comment

Filed under Combinatorics, Number theory

Ring of integers of cyclotomic field

Let \zeta=\zeta_n=e^\frac{2\pi i}{n} be a primitive n-th root of unity, and let K=\mathbb Q(\zeta). I am going to outline a proof that \mathcal O_K=\mathbb Z[\zeta], based on several homework problems from one of my recent courses. There are probably many other proofs of this, but I particularly like this one because it’s easy to follow, touches on a wide range of topics, and I worked hard through it!

First, let n=p^m be a prime power. The minimal polynomial of \zeta is the n-th cyclotomic polynomial

\displaystyle\Phi_n(X)=\Phi_{p^m}(X)=\sum_{j=0}^{p-1}X^{jp^{m-1}}.

Let f(X)=\Phi_n(X+1).

Exercise 1. Following the above notation, show that f satisfies the conditions of Eisenstein’s criterion for the prime p.

Consider the discriminant \Delta(f)=\Delta(R), where R=\mathbb Z[\zeta-1]. If q is a prime factor of \Delta(f), then f must have a multiple root modulo q. Hence X^{p^m}-1 will also have a multiple root modulo q. But \gcd(X^{p^{m}}-1, p^{m}X^{p^{m}-1})=1 in \mathbb Z/q\mathbb Z unless q=p. Thus \Delta(f)=\Delta(R)=[\mathcal O_K:R]^2\Delta(\mathcal O_K) is a power of p. In particular, [\mathcal O_K:R] is a power of p.

Exercise 2. Suppose that f\in\mathbb Z[X] satisfies the conditions of Eisenstein’s criterion for a prime number p. Let \alpha be a root of f and let R=\mathbb Z[\alpha]. Prove that there is exactly one prime ideal P\subseteq R that contains p, and that the local ring R_P is a DVR with uniformiser \alpha.

Now if Q\subseteq R is another prime ideal, then p\not\in Q. So [\mathcal O_K:R]\not\in Q.

Exercise 3. Let K be a number field and R\subseteq\mathcal O_K a subring of finite index d. If Q\subseteq R is a prime ideal not containing d, show that R_Q is a DVR.

I’ll include this solution because I love it!

Solution. Let D=\mathcal O_K. By going up, there is a prime ideal \tilde Q\subseteq D with \tilde Q\cap R=Q. We’ll show that D_{\tilde Q}=R_Q, so the result will follow.

Let a/b\in R_Q, so that a\in R, b\in R\setminus Q. If b\in \tilde Q, then b\in R\cap \tilde Q=Q, a contradiction. Hence b\not\in\tilde Q, i.e. a/b\in D_{\tilde Q}. Thus R_Q\subseteq D_{\tilde Q}.

Now let a/b\in D_{\tilde Q}, so that a\in D, b\in D\setminus\tilde Q. Then da\in R, db\in R, and a/b=(da)/(db). Note that b\not\in\tilde Q\supseteq Q, and d\not\in Q by assumption. So db\not\in Q since Q is a prime ideal. Thus a/b=(da)/(db)\in R_Q, i.e. D_{\tilde Q}=R_Q. \square

So R localised at any prime ideal is a DVR, implying that R=\mathbb Z[\zeta] is a Dedekind domain. Thus R=\mathcal O_K. This completes the proof for the prime power case.

Now we proceed by induction on the number of distinct prime factors of n. The base case has already been taken care of. So suppose that n=ab, where a,b>1 are coprime integers. Let L=\mathbb Q(\zeta_a) and M=\mathbb Q(\zeta_b). By the induction hypothesis, \mathcal O_L=\mathbb Z[\zeta_a] and \mathcal O_M=\mathbb Z[\zeta_b].

Exercise 4. Let L and M be number fields with discriminants \lambda and \mu respectively. Let \{a_1,\dots,a_m\} and \{b_1,\dots,b_n\} be integral bases for L and M respectively. Let K=LM=\mathbb Q(a_1,\dots,a_m,b_1,\dots,b_n) be the composite field of L and M. Suppose that [K:\mathbb Q]=[L:\mathbb Q][M:\mathbb Q] and that \gcd(\lambda,\mu)=1. Show that \{a_ib_j:1\le i\le m; 1\le j\le n\} is an integral basis for K.

So our main result will follow from exercise 4 once we have checked that all the hypotheses are satisfied.

(i) Checking K=LMFirstly, LM contains \zeta_a\zeta_b=e^{\frac{2\pi i(a+b)}{n}}=\zeta^{a+b}.

Exercise 5. If \gcd(a,b)=1, show that \gcd(a+b,ab)=1.

So writing j=a+b shows that \gcd(j,n)=1 and \zeta^j\in LM. If j^{-1}\in\{1,\dots,n\} is the multiplicative inverse of j\pmod n, then \zeta=(\zeta^j)^{j^{-1}}\in LM. Thus K\subseteq LM.

Again, since \zeta^a=\zeta_b and \zeta^b=\zeta_a, we have LM\subseteq K. Thus K=LM.

(ii) Checking [K:\mathbb Q]=[L:\mathbb Q][M:\mathbb Q]. We have

[K:\mathbb Q]=\varphi(n)=\varphi(ab)=\varphi(a)\varphi(b)=[L:\mathbb Q][M:\mathbb Q].

(iii) Checking \gcd(\lambda,\mu)=1This is slightly harder. We need a few more facts.

Exercise 6. Let E=\mathbb Q(\alpha) be a number field, and let f be the minimal polynomial of \alpha. Show that

\Delta(\alpha)=(-1)^{\binom{\deg(f)}{2}}N_{E/\mathbb Q}(f'(\alpha)).

Solution. Let f(x)=(x-\alpha_1)\cdots(x-\alpha_n). Then

\displaystyle\Delta(\alpha)=(-1)^{\binom n2}\prod_{i\neq j}(\alpha_i-\alpha_j)=(-1)^{\binom n2}\prod_i\prod_{j\neq i}(\alpha_i-\alpha_j).

Using Leibniz’s rule,

\displaystyle f'(x)=\sum_i\prod_{j\neq i}(x-\alpha_i)\Rightarrow f'(\alpha_i)=\prod_{j\neq i}(\alpha_i-\alpha_j).

Hence

\displaystyle\Delta(\alpha)=(-1)^{\binom n2}\prod_if'(\alpha_i)=(-1)^{\binom n2}N_{E/\mathbb Q}(f'(\alpha)). \square

Exercise 7. Using the previous exercise, show that \Delta(\zeta_n)\mid n^{\varphi(n)}.

Hint. Write X^n-1=\Phi_n(X)g(X), and use Leibniz’s rule to get n\zeta_n^{n-1}=\Phi_n'(\zeta_n)g(\zeta_n).

So \lambda=\Delta(\zeta_a) divides some power of a, and \mu=\Delta(\zeta_b) divides some power of b. Since \gcd(a,b)=1, we conclude that \gcd(\lambda,\mu)=1.

1 Comment

Filed under Algebra, Number theory

An application of Zorn’s lemma: Transcendence bases

Zorn’s lemma is a very useful result when it comes to dealing with an infinite collection of things. In ZFC set theory it is equivalent to the well-ordering theorem (every set can be well-ordered) and to the axiom of choice (a Cartesian product of non-empty sets is non-empty). I happened to use it a few days ago in proving the existence of transcendence bases, hence this post!

Zorn’s lemma. If every chain in a poset P has an upper bound in P, then P contains a maximal element.

Let K/k be a field extension. We call a subset S\subseteq K algebraically independent if for any m\ge 0 and s_1,\dots,s_m\in S, p(s_1,\dots,s_m)=0 implies p=0, where p\in k[X_1,\dots,X_m] is a polynomial. A maximal (with respect to \subseteq) algebraically independent subset is called a transcendence base.

Theorem. Every field extension has a transcendence base.

Proof. If K/k is algebraic, the transcendence base is the empty set. Suppose that K/k is not algebraic. Let \mathcal F be the family of all algebraically independent subsets S\subseteq K. By Zorn’s lemma, it suffices to show that every chain in \mathcal F has an upper bound. Let \mathcal C be a chain in \mathcal F, and let

T=\displaystyle\bigcup_{S\in \mathcal C} S.

It suffices to show that T\in\mathcal F, since then T would be an upper bound for \mathcal C in \mathcal F.

Let P(m) be the statement:

If t_1,\dots,t_m\in T are distinct, and p(t_1,\dots, t_m)=0 for some p\in k[X_1,\dots,X_m], then p=0.

If t_1\in T, then t_1\in S for some S\in \mathcal C. Since \mathcal S is algebraically independent, p(t_1)=0 implies p=0 in k[X_1]. Thus P(1) is true.

Suppose P(m-1) is true. Let t_1,\dots,t_m\in T be distinct such that p(t_1,\dots,t_m)=0 for some p\in k[X_1,\dots,X_m]. We can view p(t_1,\dots,t_m) as a polynomial in t_m with coefficients in k[t_1,\dots,t_{m-1}], i.e. say

\displaystyle p(t_1,\dots,t_m)=\sum_{i=0}^n p_i(t_1,\dots,t_{m-1})t_m^i=0.

Since P(1) is true, it folows that p_i(t_1,\dots,t_{m-1})=0 for each i=0,1,\dots,n. But then p_i=0 for each i by our hypothesis. Thus p=0, implying P(m) is true.

Therefore, by induction, T is algebraically independent, i.e. T\in\mathcal F. \square

Leave a comment

Filed under Algebra, Set theory

Finite automata 1: Automatic sets

In one of my recent courses I had to learn about finite automata theory. The main purpose was to understand a generalisation of the celebrated Skolem-Mahler-Lech theorem in positive characteristic. Let \mathbb N_0 denote the set of non-negative integers and K be a field. For a linear recurrence f:\mathbb N_0\to K, define its zero set to be \{n\in\mathbb N_0 : f(n)=0\}. Then the Skolem-Mahler-Lech theorem states the following:

Theorem (Skolem-Mahler-Lech, 1953). The zero set of a linear recurrence f:\mathbb N_0\to\mathbb K, where K is a field of characteristic 0, is a finite union of arithmetic progressions along with a finite set.

Derksen in his 2005 paper was able to provide the correct analogue of this result in positive characteristic for the first time:

Theorem (Derksen, 2007). The zero set of a linear recurrence f:\mathbb N_0\to K, where K is a field of characteristic p>0, is a p-automatic set.

To understand this theorem we need to know about finite automata. In this and the next few posts I want to write about some interesting elementary results about automatic sets. Since my knowledge of computer science is epsilon(!), I will mostly touch on some very basic mathematical aspects.

A deterministic finite-state automaton (DFA) is a directed multigraph \Gamma satisfying certain properties. Firstly, its vertex-set Q (which we call the set of states) contains a special vertex (or state) q_0, called the initial state. We also have a finite non-empty set \Sigma of symbols. Each edge of \Gamma is labelled with a symbol from \Sigma. As a result, we have a transition function \delta:Q\times\Sigma\to Q such that if an edge from q_1 to q_2 is labelled with the symbol a\in\Sigma, then we write \delta(q_1,a)=q_2. Finally, we have a set F\subseteq Q (possibly empty) called the set of accepting or final states.

So \Gamma can be formally written as a quintuple (\Sigma,Q,q_0,\delta,F).

Let \Sigma^* be the free monoid on \Sigma. We can extend the transition function \delta to a map \delta:Q\times\Sigma^*\to Q by setting \delta(q_0,wa)=\delta(\delta(q_0,a),w) for all a\in\Sigma and w\in\Sigma^*. Thus, to \Gamma we can associate a language

\mathcal L_\Gamma:=\{w\in\Sigma^*:\delta(q_0,w)\in F\}\subseteq\Sigma^*.

We call such a language produced from a DFA a regular language. If w\in\mathcal L_\Gamma for some w\in\Sigma^*, we say that w is accepted by \Gamma.

Let \mathbb N denote the set of the positive integers, and let k>1 be an integer. Define \Sigma_k:=\{0,1,\dots,k-1\}. A subset S\subset\mathbb N is said to be k-automatic if there exists a DFA \Gamma=(\Sigma_k,Q,q_0,\delta,F) such that S is precisely the set of those j\in\mathbb N whose base-k representation, when regarded as a string in \Sigma^*, is accepted by \Gamma. If S\subseteq\mathbb N is k-automatic for some k>1, we say S is an automatic set.

For w=w_nw_{n-1}\cdots w_0\in\Sigma_k^* with each w_i\in\Sigma_k we define

[w]_k:=w_nk^n+w_{n-1}k^{n-1}+\cdots+w_0.

In this case we also define |w|:=n+1 to be the length of w.

So S\subseteq\mathbb N is k-automatic precisely when S=\{[w]_k:w\in\mathcal L_\Gamma\} for some DFA \Gamma.

Note that we can set \delta(q,0) to be in Q\backslash F for every q\in Q (if F=Q, just create a new state). Thus we may without loss of generality assume that all our DFAs only accept words without leading zeros.

A basic result about regular languages is the pumping lemma:

Lemma (Pumping lemma). If \mathcal L is an infinite regular language, then there exist words a,b,c with |b|\ge 1 such that ab^nc\in\mathcal L for all n\ge 0.

Proof. Since \mathcal L is infinite, there are words of arbitrarily large length in \mathcal L. Let w=w_nw_{n-1}\cdots w_0\in\mathcal L be a word of sufficient length. Then there exist 0\le i<j\le n such that w_i\cdots w_0=w_j\cdots w_0\in\mathcal L. Taking a=w_n\cdots w_j, b=w_{j-1}\cdots w_i, c=w_{i-1}\cdots w_0 shows that ab^nc\in\mathcal L for all n\ge 0. Moreover, since i<j, it follows that |b|\ge 1. \square

In the following posts we are going to use the pumping lemma, together with other machinery, to derive some interesting results on the automaticity of certain sets.

Leave a comment

Filed under Algebra, Combinatorics, Number theory