Tag Archives: polynomial

Chebyshev polynomials and algebraic values of the cosine function

Let p be an odd prime and let T_n(X) be the n-th Chebyshev polynomial of the first kind. By Lemma 1 on page 5 of this paper, T_p(X)/X is irreducible over \mathbb Q. Now

\displaystyle T_p(\cos\frac{\pi}{2p})=\cos\frac{\pi}{2}=0,

so the minimal polynomial of \cos(\pi/2p) over \mathbb Q is T_p(X)/X. (Note that we are slightly abusing terminology here. By definition, the minimal polynomial is a monic polynomial. But let us drop precision for the sake of brevity.)

By definition (and induction, if you may), \deg(T_n)=n. Hence we deduce the following:

Proposition 1. \cos(\pi/2p) is an algebraic number of degree p-1.

Since T_p(X)/X consists of only even powers of X, T_p(\cos(\pi/2p)) can be expressed as a polynomial in \cos(\pi/p)=2\cos^2(\pi/2p)-1. Therefore:

Proposition 2. \cos(\pi/p) is an algebraic number of degree (p-1)/2.

A nice corollary of this is Niven’s theorem:

Corollary (Niven’s theorem). If \theta\in (0,\pi/2) is a rational multiple of \pi such that \cos\theta is rational, then \theta=\pi/3.

Proof. Note that if \cos\theta is rational, then so is \cos(n\theta)=T_n(\cos\theta) for any positive integer n. So, (reduction 1) without loss of generality, \theta=k\pi/p for some odd prime p and positive integer k<p/2. (The case p=2 is dealt with trivially.)

Further, multiplying by the inverse of k\pmod p, (reduction 2) one may assume k=1 without any loss of generality.

Now being rational is the same as being algebraic of degree 1. Hence, by the above, we must have p=3 and the conclusion follows immediately. \square

Exercise. Find all rational multiples \theta\in(0,\pi/2) of \pi such that \cos\theta is a quadratic irrational.

Leave a comment

Filed under Algebra, Number theory

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<p_1<\cdots 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

Leave a comment

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

Leave a comment

Filed under Combinatorics, Number theory

Symmetric polynomials in two variables

Let R be a commutative ring. The fundamental theorem of symmetric polynomials says that any symmetric polynomial in R[X,Y] can be expressed uniquely as a polynomial in X+Y and XY.

Recently I was thinking about this along the following lines. Let R[X,Y]^{S_2} denote the set of all symmetric polynomials in R[X,Y]. Then the theorem above is saying that R[X,Y]^{S_2} is generated by \{X+Y,XY\} as an Ralgebra, i.e., R[X,Y]^{S_2}=R[X+Y,XY]. Being unsuccessful at utilising this I ended up with the following. (I can’t see the best way of showing that a set generates an algebra.)

Let f(X,Y)=\sum_{i,j}a_{i,j}X^iY^j\in R[X,Y]^{S_2}. Since f(X,Y)=f(Y,X), we have a_{i,j}=a_{j,i} for all i,j. Hence f(X,Y)=\sum_{i\le j}a_{i,j} (XY)^i(X^{j-i}+Y^{j-i}). So it suffices to show that X^n+Y^n can be expressed as a polynomial in X+Y and XY for each n\ge 0. But this follows easily by induction and the following identity

X^n+Y^n=(X+Y)(X^{n-1}+Y^{n-1})-XY(X^{n-2}+Y^{n-2}).

However, this argument doesn’t generalise immediately to more variables, and I don’t particularly like any of the proofs that I’ve found so far.

Leave a comment

Filed under Algebra

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