Tag Archives: polynomial

09/09/2015 · 12:42 am

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

Tagged as irrational number, polynomial

25/07/2015 · 12:55 pm

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

Tagged as polynomial, ring

03/07/2015 · 2:23 am

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

Tagged as field, polynomial, prime power

09/06/2015 · 11:28 am

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 $R$ –algebra, 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

Tagged as permutation, polynomial, ring

06/04/2015 · 7:31 pm

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=LM$ . Firstly, $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)=1$ . This 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$ .