A Portion of the Book

January 31, 2011

Algebraic Number Theory: Norm and Trace (Part 4)

Filed under: Algebra,Galois Theory,Number Theory — by Masoud Zargar @ 8:41 pm

This is a continuation of the the previous post, regarding separability, in the Algebraic Number Theory series. Now that we have worked with separable polynomials, separable extensions, and separable elements, we will define norms and traces, and prove some results connecting this post to the previous posts in the series. Finally, I will apply all that we have learned so far to describe a method useful in combinatorics.

Suppose $E/F$ is a finite separable extension with $K$ an algebraic closed field with $F\hookrightarrow K$ the inclusion map. Then by separability, we have $|E:F|$ extensions $\sigma_i:E\hookrightarrow K$ of the inclusion map. Now if $a_1,\hdots, a_n$ is a basis for $E$ as an $F$ -vector space, then we define $V^*(a_1,\hdots,a_n)=\det(\sigma_i(a_j))_{i,j}$ . Now if $b_1,\hdots,b_n$ is another basis for the aforementioned vector space, we may write $b_j=\sum_{k=1}^n\mu_{jk}a_k$ for all $j$ . So it follows that $\sigma_i(b_j)=\sum_{k=1}^n\mu_{jk}\sigma_i(a_k)$ . Therefore, $V^*(b_1,\hdots,b_n)=V^*(a_1,\hdots,a_n)\det(\mu_{ij})$ .

The Theorem of Primitive Elements states that if $E=F(\alpha,\beta)$ , where $\alpha$ is separable and $\beta$ is algebraic, then $E$ is a simple extension of $F$ . It follows that $E/F$ is a finite separable extension iff $E=F(\alpha)$ , where $\alpha$ is a separable element. Finding this $\alpha$ for the above extension, we see that we can find a separable element $\alpha$ such that $\{\alpha^{j-1}\}_{j\in [n]}$ is a basis for $E$ . It then follows that $V^*(1,\alpha,\hdots,\alpha^{n-1})=V(\sigma_1(\alpha),\hdots,\sigma_n(\alpha))\neq 0$ . So $V^*\neq 0$ for any chosen basis.

We now define the trace $\text{tr}_{E/F}$ and norm $\text{N}_{E/F}$ of an element $\alpha$ by

$\text{tr}_{E/F}(\alpha):=\sum_{i}\sigma_i(\alpha)$

and

$\text{N}_{E/F}(\alpha):=\prod_i\sigma_i(\alpha)$

By the fact that $\sigma_i$ are field homomorphisms, $\text{tr}_{E/F}:E\rightarrow E$ is $F$ -linear, and $\text{N}_{E/F}:E^*\rightarrow E^*$ is a homomorphism. We also have the following: $\text{tr}_{E/F}(E), \text{N}_{E/F}(E)\subseteq F$ . We can extend $E/F$ to a Galois extension $L/F$ . Then since $G:=\text{Gal}(L|F)$ has the fixed field $F$ , and that $\tau|_{E}$ is an extension of $F\hookrightarrow K$ for all $\tau\in G$ , we see that $\{\tau|_E\sigma_i\}$ is a permutation of $\{\sigma_i\}$ for all $\tau\in G$ . So $\text{tr}_{E/F}(\alpha)$ and $\text{N}_{E/F}(\alpha)$ are in the fixed field of $G$ , which is $F$ , as required.

Given a basis $a_1,\hdots,a_n$ of $E/F$ , we define its discriminant by $d(a_1,\hdots,a_n)=\det(\text{tr}_{E/F}(a_ia_j))_{i,j}$ , which is in turn

$\det((\sigma_i(a_j))_{i,j}(\sigma_i(a_j))^T_{i,j})=V^*(a_1,\hdots,a_n)^2\neq 0$ .

So $(\text{tr}_{E/F}(a_ia_j))_{i,j}$ is non-singular, and so $\text{tr}_{E/F}:E\rightarrow F$ is nonzero somewhere. As a result of $F$ -linearity, trace is surjective. Having done these, it is now easy to prove that $\text{tr}_{E/L}=\text{tr}_{F/L}\circ\text{tr}_{E/F}$ , and a similar formula holds for $\text{N}_{E/L}$ , where we have $L\subseteq F\subseteq E$ .

We will now apply the tools that have been developed so far to describe a technique in combinatorics.

One way to study the divisibility of expressions regarding subsets of a set whose sums of elements are divisible by an integer $n$ is the following . Suppose we are given $n$ integers $a_1,\hdots,a_m$ . We take a polynomial $f\in\mathbb{Z}[z]$ and $n|\sum_{i\in I}a_i$ iff $\zeta_n^{\sum_{i\in I}a_i}=1$ , where $\zeta_n:=e^{\frac{2\pi i}{n}}$ . Then we consider the expression $\omega:=\prod_{i=1}^mf(\zeta_n^{a_i})$ , and so $\displaystyle \text{tr}_{\mathbb{Q}(\zeta_n)/\mathbb{Q}}(\omega)=\sum_{k\in \Pi(n):=\{(a,n)=1, 1\leq a\leq n\}}\prod_{i=1}^mf(\zeta_n^{ka_i})$ . If for example, $f(z)=a+bz$ , then we have

$\displaystyle\sum_{k\in \Pi(n)}\prod_{i=1}^m(a+b\zeta_n^{ka_i})=\sum_{\emptyset\subseteq I\subseteq [m]}a^{m-|I|}b^{|I|}\sum_{k\in\Pi(n)}\left(\zeta_n^{\left(\sum_{j\in I}a_j\right)}\right)^k$

Note that as soon as we let $n=p$ , $p$ a prime, then we are able to analyze properties related to the number of subsets of $\{a_i:i\in [m]\}$ whose sum of elements are divisible by $p$ .

This is the end of this post! The next post in the series will be on the set of algebraic integers and transcendental numbers.

Leave a Comment

January 25, 2011

Algebraic Number Theory: Separability (Part 3)

Filed under: Algebra,Number Theory — by Masoud Zargar @ 12:04 am

Starting with this post, which is a continuation of the last post, I will define separability, separable extensions, perfect fields, and discriminants, and also prove results germane to these objects. In the next post, in which norm and trace are discussed, I will apply these tools for $\mathbb{Q}(\zeta_p)/\mathbb{Q}$ to prove a beautiful result in combinatorial number theory.

To study the multiplicity of the roots of a polynomial, the following formal derivative is useful:

Definition. Given the polynomial $f\in F[X]$ , $F$ a field, such that $f=a_0+a_1X+\hdots+a_nX^n$ , we define $f'=a_1+2a_2X+\hdots+na_nX^{n-1}$ .

It is easy to see that this definition satisfies the usual properties of differentiation, e.g. linearity and the product rule.

Suppose now that we are given a polynomial $f\in F[X]$ of degree $n$ . Then we may choose the splitting field of $f$ over $F$ (or any field extension of the splitting field), say $L$ , and write $f=a\prod_{i=1}^n(X-\alpha_i)$ , $a\neq 0$ . If we have that the $\alpha_i$ s are distinct, then $f$ is said to be a separable polynomial.

(more…)

Comments (1)

January 22, 2011

Algebraic Number Theory: Introduction (Part 2)

Filed under: Algebra,Number Theory — by Masoud Zargar @ 11:14 pm

I am currently in the course of writing a post about the applications of topology (mainly algebraic topology) to algebra. I hope I finish it soon. Meanwhile, I would like to continue my Algebraic Number Theory series. But before I begin, I think that it is necessarily to resolve an ambiguity: the title of each post is of the form Algebraic Number Theory: (section name) (part number). Soon, the section called Introduction will end and a new section (regarding separability, discriminant, norm, trace, etc.) will begin. We now continue the previous post.

In this series, we shall call an ideal of a ring $\mathfrak{o}$ an $\mathfrak{o}$ -ideal. We define the set of algebraic integers over a finite field extension $K/\mathbb{Q}$ , denoted $\mathfrak{o}_K$ , to be the set of all elements $a\in K$ such that there exists a monic polynomial $f\in\mathbb{Z}[X]$ such that $f(a)=0$ . In fact, this is a ring.

Remark. It may be quite annoying to prove that $\mathfrak{o}_K$ is closed under addition and multiplication, i.e. it is annoying to directly prove that this set is in fact a ring. Do not worry about the properties of $\mathfrak{o}_K$ for the moment. In the next section, I will prove that the generalization of $\mathfrak{o}_K$ satisfies such properties.

As we saw in the previous post, unique factorization may fail in the rings we consider, e.g. $\mathbb{Z}[\sqrt{-6}]$ . Therefore, it would be desirable to prove unique factorization for a ring whose underlying set contains $\mathfrak{o}_K$ -ideals. In other worlds, we want to prove that $\mathfrak{o}_K$ -ideals can be uniquely (up to ordering) be factorized as a product of prime $\mathfrak{o}_K$ -ideals. We shall later see this in practice. (more…)

Comments (1)

Algebraic Number Theory: Introduction (Part 1)

Filed under: Algebra,Number Theory — by Masoud Zargar @ 1:07 am

Starting with this post, I am going to write a series of posts regarding algebraic number theory, and in the course of doing so, I will solve problems. This series is intended for those who are comfortable with ring theory, module theory (modules, exact sequences, tensor products, etc.), field theory, Galois extensions, group theory, and a bit of analysis and topology (for example completeness, compactness, topologies, etc.) In other words, I will not explain the basics of algebra and analysis that a graduate student should know by the time he or she enters his or her, resp., second year.

Crudely stated, algebraic number theory is the study of algebraic number fields (finite algebraic extensions $K/\mathbb{Q}$ ). It is through the study of these larger fields that we can obtain new insight into the solutions of Diophantine equations. In fact, it was the study of Diophantine equations that brought algebraic number theory into existence. Here, we will not take the chronological development of the concepts into consideration; we will rather introduce “modern” algebraic number theory. One of the benefits of studying these larger fields is that when asked to prove a property over a field $F$ , we may embed this into a field extension $K/F$ and use the properties of $K$ along with algebraic tools to reach the desired property. We will often embed the ring of algebraic integers into a larger ring, and then proceed as above. In other words, we want to understand the interplay of rings (and fields) and their extensions.

A motivational theorem that makes use of the embedding $\mathbb{Z}\hookrightarrow\mathbb{Z}[i]$ is Fermat’s theorem regarding the representation of odd primes as a sum of two squares (in $\mathbb{Z}$ ).

(Fermat) An odd prime $p$ is representable in the form $p=x^2+y^2,\ x,y\in\mathbb{Z}$ iff $p\equiv 1\bmod 4$ .

Proof. First, we prove the only if case. Note that $p$ is odd, and since $0$ and $1$ are the only squares $\bmod 4$ , $x^2+y^2\not\equiv 3\bmod 4$ . Therefore, $p\equiv 1\bmod 4$ , as required.

Conversely, suppose $4|p-1$ . Then consider the cyclic group $G:=\mathbb{F}^*_p$ of order $p-1$ . Since $4|p-1=|G|$ , and $G$ is cyclic, $G$ has an element of order $4$ , say $g$ . Note that $g^2$ has order $2$ and the only element of order $2$ is $-1$ . Therefore, $p|g^2+1$ . Consider the extension of $\mathbb{Z}$ to $\mathbb{Z}[i]$ . If $p$ were irreducible as an element of $\mathbb{Z}[i]$ (this is a Euclidean domain), then $p|g^2+1=(g+i)(g-i)$ implies $p|g+i$ or $p|g-i$ . Then we would have $p|g\implies 1\equiv 0\bmod p$ , a contradiction. So $p$ is reducible in $\mathbb{Z}[i]$ , say $p=zw$ , where $z,w\in\mathbb{Z}[i]$ . Consider the norm $N$ on $\mathbb{Z}[i]$ defined by $N(z):=|z|^2$ . Then $p^2=|z|^2|w|^2$ . It is easy to show that $u\in\mathbb{Z}[i]^*$ iff $N(u)=1$ (why?). Since $z,w$ were non-units, we must have $|z|^2=|w|^2=p$ . If $z=x+iy$ , then $p=x^2+y^2$ , as desired. $\Box$

Note that the ring $\mathbb{Z}[i]$ of Gaussian integers (often used by Gauss), was essential to our proof. Whenever we solve a problem pertaining to Diophantine equations, this will be the flavor of our solutions. That being said, there are nuances that need to be taken care of. For example, which primes $p$ can be written in the form $p=x^2+6y^2,\ x,y\in\mathbb{Z}$ ? The same proof cannot work in this case, because $\mathbb{Z}[\sqrt{-6}]$ is not a unique factorization domain: $-6=-2\cdot 3=\sqrt{-6}\cdot\sqrt{-6}$ (it can be checked that these two are distinct representations of $-6$ as a product of irreducible elements).

Often, the rings we consider will not be Unique factorization domains. To compensate for such a lack, we work with rings in which ideals can be uniquely factorized into prime ideals. In particular, we study Dedekind domains (which will be introduced later). Of course, much more than this has to be done. For example, we will find a generalization of the above norm $N$ and much more!

Due to a lack of time (it’s late), I will end this here. This was a slow introduction and contained very little (if any) algebraic number theory, but it will certainly become faster and more technical soon.

Comments (2)

January 18, 2011

Return: Two Problems

Filed under: Combinatorics,Galois Theory,Modules,Number Theory — by Masoud Zargar @ 1:19 am

Prior to beginning the discussion of the topic of this relatively short post, I would like to thank the people who reminded that I should right more. Someone mentioned that I had stated that my inactivity was due to the election; however, I do not recall stating such a thing. Although my interests and priorities (regarding reading) did change around that time, the main reason for not writing was that my studies focused on algebraic topology, commutative algebra, functional analysis, and Galois theory. As a result of trying to absorb the material rather than think about nontrivial problems, I did not have much to write about. That being said, laziness should also be taken into account.

In this post, two (beautiful) results, due to Dehn and Burnside, will be briefly discussed. Both proofs given can be considered as applications of algebra to (partially) geometric problems. Other than simply obtaining the pleasure of discussing two beautiful results, I would also like to fuel the interests of readers who are not interested in algebra. Familiarity with tensor products and Galois theory, in particular $N_{K/F}$ for a field extension $K/F$ , will be prerequisites for the material in this post. (more…)

Comments (3)

July 27, 2009

Chevalley-Warning and Combinatorics

Filed under: Combinatorics,Number Theory — by Masoud Zargar @ 2:29 pm

Recently, I have been studying the two theorems that are of importance to zero-sum theory: Combinatorial Nullstellensatz and the Chevalley-Warning Theorem. The former method of proof is also referred to as the Noga Alon polynomial method. You may read Combinatorial Nullstellensatz, a very interesting paper attributed to Noga Alon. That being said, I would like to discuss the latter theorem along with several of its applications in combinatorics. The Chevalley-Warning Theorem is concerned with the solutions to a system of polynomial equations over finite fields. As far as combinatorial problems are concerned, the construction of this system is crucial. Usually, when working over $\mathbb{F}_p$ , the Chevalley-Warning theorem coupled with Fermat’s Little Theorem form the basis for the construction of the system.

Zero-sum problems comprise a class of combinatorial problems that are of the form: given a finite abelian group $G$ and an integer $n$ , find the smallest integer $k$ such that among any sequence of $k$ elements of $G$ , there are $n$ of them that sum to $0$ . For example, we obtain the Erdős-Ginzburg-Ziv theorem when $G:=\mathbb{Z}\slash n\mathbb{Z}$ , i.e. among any $2n-1$ integers, you can find exactly $n$ of them whose sum is divisible by $n$ .

After an elementary proof of the Chevalley-Warning theorem has been provided, a proof of the Erdős-Ginzburg-Ziv will be given. Then a graph theoretic problem followed by a lemma of Alon and Dubiner (a crucial step in C. Reiher’s proof of Kemnitz’s conjecture in 2003) will be in order. (more…)

Leave a Comment

July 19, 2009

Cauchy’s Method of Induction

Filed under: Miscellaneous — by Masoud Zargar @ 6:47 pm

Being in the course of writing a couple of blog entries on a couple of technical topics, in the meantime, I would like to discuss a method of induction that is believed to have originated from Cauchy’s works. I will illustrate the method by proving a couple of inequalities. Initially, I will discuss a proof of the Arithmetic-Geometric Means inequality followed by a proof of a nice inequality.

For those readers who are unaware of the Arithmetic-Geometric Means inequality:

(Arithmetic-Geometric Means Inequality) If $a_1,\hdots,a_n\geq 0$ are real numbers, then $\displaystyle \frac{1}{n}\sum_ia_i\geq\sqrt[n]{\prod_{i}a_i }$ .

Let’s demonstrate Cauchy’s method of induction by proving this ubiquitous inequality. (more…)

Comments (2)

July 9, 2009

Invariants

Filed under: Combinatorics — by Masoud Zargar @ 11:52 pm

Problem 2. You are given markers each being one of the three colors green, blue, and red. A

step is composed of taking two markers of dierent colors and replacing them with a marker of the

third color. Prove that the color of the last marker remaining either does not depend on the way

you perform the steps or could be any of the three colors.

When I was in high school (last year), I wrote about 50 pages (two chapters) on a wide range of topics in number theory and combinatorics. Each chapter was divided into short sections on independent topics followed by a collection of problems with their solutions. The first section was on the invariance principal. Here, I have reproduced that section for this blog; however, I have refrained from posting the solutions in order to eliminate some temptations to look at the solutions.

***

The invariance principle says that if there is change, look for the properties that does not change, i.e. look for the invariants.

This principle can sometimes be used to solve problems that involve a fixed set of legal moves. Consider the following problem as an example.

Given three numbers $a,b,c$ on a blackboard, a step is composed of taking any of the three numbers and adding to it the difference of the other two numbers multiplied by any rational numbers. For example, you can map $(a,b,c)\mapsto \left( a+|b-c|\frac{p}{q},b,c\right)$ , where $\frac{p}{q}\in\mathbb{Q}$ . Can you obtain the set $\{0,2,\sqrt{3}\}$ starting with $\{0,1,\sqrt{3}\}$ ?

At first sight, this problem may seem very diffcult. If you notice that when you perform a step, $(a,b,c)\mapsto \left( a+|b-c|\frac{p}{q},b,c\right)$ , you are in fact translating a point by vector, then you may think of a geometric interpretation of this problem.

So what can we do? Let’s find a property that remains invariant.

(more…)

Comments (1)

June 8, 2009

A Word on p+22

Filed under: Number Theory — by Masoud Zargar @ 12:12 am

There is a class of conjectures that deal with the integral solutions $(p,n)$ to $p=f(n)$ , where $p$ is a prime and $f\in\mathbb{Z}[x]$ with $\deg f=2$ . For example, it is open whether or not the above equation has an infinite number of solutions when $f(X)=X^2+1$ . In this entry, I would like to discuss the solutions to $p+22=n^2$ , where $p$ is a prime and $n\in\mathbb{Z}$ . Notice that this is easier to approach than finding all prime numbers of the form $n^2+1$ due to the fact that one can discuss quadratic residues modulo $11$ or $22$ for the former equation, whereas the latter equation is not susceptible to such approaches at first sight. I claim the following:

Theorem. If $p$ is a prime of the form $n^2-22$ , then if $p\neq 3$ , then $p\equiv\{59,131\}\pmod{144}$ .

Proof. Equivalently, we have to prove that if $p+22$ is a perfect square, then $p\equiv\{59,131\}\pmod{144}$ , hence the name of the entry. Notice that $p=3$ satifies $3+22=5^2$ , so $3$ is of the desired form. Suppose now that $p\neq 3$ . Notice that $0,1$ are the only squares $\bmod 3$ . Assume that $3\nmid n$ . Then it follows that

$p+1\equiv p+22\equiv n^2\equiv 1\pmod 3\implies 3|p\implies p=3$ ,

a contradiction to our assumption. So $3|n$ . Therefore, $9|n^2$ , and $p+4\equiv p+22\equiv 0\pmod{9}\implies p\equiv 5\pmod{9}$ .

Niether $2$ nor $11$ are primes of the desired form, so $(p,22)=1$ . Modulo $p$ , $22$ is a quadratic residue, so by the Quadratic Reciprocity law,

$1=\left(\frac{22}{p}\right)=\left(\frac{2}{p}\right)\left(\frac{11}{p}\right)=(-1)^{\frac{p^2-1}{8}}\left(\frac{p}{11}\right)(-1)^{\frac{(p-1)(11-1)}{4}}$

Since modulo $11$ , $p\equiv n^2\pmod{11}$ , $\left(\frac{p}{11}\right)=1$ . Ergo, $1=(-1)^{\frac{p^2-1}{8}+\frac{p-1}{2}}$ . So we want to have $2|\frac{p^2+4p-5}{8}$ , i.e. $(p+2)^2-9\equiv p^2+4p-5\equiv 0\pmod{16}$ . A simple calculation gives that only $x\equiv 3,5,11,13\pmod{16}$ satisfy $x^2\equiv 9\pmod{16}$ . Cosequently, $p\equiv 1,3,9,11\pmod{16}$ . But not all of these satisfy our needs. Since $p\neq 2$ ( $2+22=24$ is not a perfect square), $p+22=n^2$ must be an odd square. So modulo $8$ ,

$p-2\equiv p+22\equiv n^2\equiv 1\pmod{8}\implies p\equiv 3\pmod 8$ .

Thus, only $p\equiv 3,11\pmod{16}$ are possible. The rest is a simple result of the Chinese Remainder Theorem given

$\begin{cases}p\equiv 5\pmod 9\\ p\equiv 3\pmod{16}\end{cases}$

$\begin{cases}p\equiv 5\pmod{9}\\ p\equiv 11\pmod{16}\end{cases}$ .

These lead to $p\equiv\{59,131\}\pmod{144}$ , as required. $\Box$

This approach may certainly be extended to more general results, but I will leave the investigation to the reader for now. Any new insight regarding primes of the form $n^2-22$ is certainly welcome.

Leave a Comment

June 7, 2009

The Fundamental Theorem of Algebra I

Filed under: Complex Analysis — by Masoud Zargar @ 6:43 pm

As a result of the very beautiful mathematics out there, it has been very difficult to keep my word about regularly posting here. I have been procrastinating to complete the last post on Fourier series and its applications (Fourier Series, Geometry, and Summation) for I would like to continue it with a discussion of infinite pre-Hilbert spaces and their applications. In this post, however, I would like to include two proofs of the Fundamental Theorem of Algebra, i.e. $\mathbb{C}$ is algebraically closed.

There are many proofs of the Fundamental Theorem of Algebra, but there are two that I particularly like because of their elegance and the way they seem to be far from intuition at first sight: a topological proof and another using complex analysis. Trying to make this post self contained, brief proofs of the results used will be given. Furthermore, for motivational purposes, non-related applications, e.g. the Borsuk-Ulam and the Brouwer Fixed Point theorems in two dimensions, of the proved results will be given.

A formal stating the fundamental theorem of algebra:

Every nonconstant $f\in\mathbb{C}[z]$ has a root in $\mathbb{C}$

Notice that this implies the following ubiquitous theorem (also known as the fundamental theorem of algebra) that many take for granted:

Every polynomial $f(z)=a_nz^n+\hdots+a_0$ with $\deg f=n\geq 1$ has precisely $n$ roots. If these roots are $z_1,\hdots,z_n$ (not necessarily distinct), then $f(z)=a_n(z-z_1)\hdots(z-z_n)$ .

You may be wondering how this latter result follows from the former.

The former result states that $f$ has a roots, say $z_1$ . Then $f(z)=f((z-z_1)+z_1)=\sum_{k=0}^na_k((z-z_1)+z_1)^k$ . By Newton’s Binomial Theorem, expanding $((z-z_1)+z_1)^k$ for all $k$ results in $f(z)=b_n(z-z_1)^n+\hdots+b_1(z-z_1)+b_0$ . Since $b_0=f(z_1)=0$ , we have $f(z)=(z-z_1)g(z)$ , $\deg g=n-1$ . By induction on the degree of polynomials in $\mathbb{C}[z]$ , the result follows.