4 out of 5 dentists recommend this site

Month: January, 2014

Algebraic field extensions: a continuation

We shall talk about the algebraic extension F(\alpha,\beta). We shall assume that both \alpha and \beta are algebraic over the field F.

Assume \deg(F(\alpha),F)=m. Hence, the basis for the vector space F(\alpha) over F is 1,\alpha,\alpha^2,\dots,\alpha^{m-1}. Now say \deg(F(\alpha,\beta),F)=n. Then the basis of F(\alpha,\beta) over F(\alpha) is 1,\beta,\beta^2,\dots,\beta^{n-1}.

It is known that the basis of F(\alpha,\beta) over F is \begin{pmatrix} 1 & \beta&\beta^2 & \ldots & \beta^{n-1} \\ \alpha & \alpha\beta & \alpha\beta^2 & \ldots & \alpha\beta^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \alpha^{m-1} & \alpha^{m-1}\beta & \alpha^{m-1}\beta^2 & \ldots & \alpha^{m-1}\beta^{n-1}\end{pmatrix} (arranged as a matrix).

None of these can be dependant on each other (by definition). Also, they are mn in number.

Now let us first construct F(\beta) from F. Say \deg(F(\beta): F)=s. Then the basis of F(\beta) over F is 1,\beta,\beta^2,\dots,\beta^{s-1}. Now let us assume \deg(F(\alpha,\beta)) over F is r. The basis matrix of F(\alpha,\beta) over F will hence be F(\alpha,\beta) over F is \begin{pmatrix} 1 & \beta&\beta^2 & \ldots & \beta^{s-1} \\ \alpha & \alpha\beta & \alpha\beta^2 & \ldots & \alpha\beta^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \alpha^{r-1} & \alpha^{r-1}\beta & \alpha^{r-1}\beta^2 & \ldots & \alpha^{r-1}\beta^{s-1}\end{pmatrix}.

It is possible that not a single term in the two matrices are the same. However, mn=rs.


Field extensions…..things that books won’t explicitly point out.

This is going to flesh out some real details.

First, something exceedingly important. When doing elementary algebra for the first time (say in grade 4), one often asks “what is x?” The answer to that is “x” is just a useful construct that is temporarily holding place, waiting for an actual number to pop in and satisfy the equation. x is not an actual number. There is no number in the real number line called “x“. OK.

Say F is a field, and we have the polynomial ring F[x]. Then if a\in F satisfies the equation f(x)=0 (f(x)\in F[x]), then x has the same sense as that used in your grade 4 algebra. x doesn’t actually belong to the field F. It is just waiting for a\in F to pop in and satisfy the equation. x does technically belong to the polynomial ring F[x], but we’re concerned only with F here. We can think of the whole of F[x] as a useful construct to help us deal with our problems. But just you wait.

If p(x)\in F[x] is irreducible over F, then the **field** F[x]/\langle p(x)\rangle contains the element x (technically, the element is x+\langle p(x)\rangle). Yes. There is an equation in  \frac{F[x]}{\langle p(x)\rangle}[X] such that when you punch in x, the equation is satisfied. So x has moved on from being an imaginary filler for another element to actually being an element of the field itself.

Now we shall discuss some fundamental facts concerning field extensions:

1. If f(x)\in F[x] is irreducible in F[x], then there exists a field extension such that f(x) has a root in that extension- The irreducibility property is important here. The proof proceeds by creating a field F[x]/\langle f(x)\rangle, and saying this is the field in which f(x)=0. But F[x]/\langle f(x)\rangle is a field, and not a ring. \frac{F[x]}{\langle f(x)\rangle}[X] is the corresponding ring of the field. Assume f(x)(\in F[x])=a_0+a_1x+a_2x^2+\dots+a_nx^n. Then this is mapped isomorphically to a_0+a_1X+a_2X^2+\dots+a_nX^n in \frac{F[x]}{\langle f(x)\rangle}[X], and is satisfied by x+\langle f(x)\rangle \in \frac{F[x]}{\langle f(x)\rangle}. Hence, \frac{F[x]}{\langle f(x)\rangle} is the field extension of F which contains a root of the irreducible (in F) polynomial f(x).

2. Say we have F(\alpha) such that \alpha is algebraic over F. Then every element in F(\alpha) is algebraic over F. The proof of this is based on the pigeonhole principle, and is quite clever. Any standard textbook on algebra will have this proof.

Problem-solving, Olympiads and Life

This post was long due.

First, my motivation for writing this post. I was never much into mathematics in India. It was only when I went to Singapore that I became deeply immersed in it. I still remember Mr. Scheelbeek’s end-of-term class, when he told us about Fermat’s Last Theorem. I resolved to prove it, and invested most of my time in it. This has been detailed in an earlier post.

The IB (International Baccalaureate) is a tough and demanding course, quite unlike the rote-learning oriented education system in the sub-continent. The exams would be hard in the sense that we’d almost always be asked to analyze and solve new problems. An example would be:

The chapter was functions. We started off by graphing fairly elementary functions like f(x)=x and f(x)=x^2, and then proceeded to functions like f(x)=\sin x and f(x)=\sin 2x. Towards the end of the problem set, we had functions like f(x)=\frac{1}{1-x}. The difficulty level was not much, clearly, but because the course was centred on self-study rather than exhaustive teaching, students of formidable intelligence too faced some problems with these new concepts.

In our end-of-sem paper, we were asked to graph f(x)=\frac{x^2+2x+3}{(x-3)(x-4)}.

One might say that graphing such a function is fairly easy. No. It is not easy to solve such a problem in exam-time when the hardest problem in the problem set was much more elementary than this.

As a result of this, in our papers of approximately 110 to 115 marks, the highest grade of 7 would be given at 65 or above. And only 2-3 students out of 60 would manage to get such a score. And our batch was extremely competitive. More than half the student population consisted of scholars from various Asian countries. Many of them went on to secure full scholarships to universities like Harvard, Oxford, UBC, NUS, etc. Intelligence is a tricky thing to measure, but they were definitely more motivated than the students at BITS Pilani.

In my two math papers, I got 110/110 and 125/128. I also won the Math prize.

This might appear immodest on my part, but I mention this only for a full exposition. I was fairly good at math, and my teacher thought I’d end up at MIT, Caltech, or some other top college. I didn’t. The rest of the post explains why.

Like any other student wishing to pursue math, I started preparing for the Math Olympiad program. I never tried to solve those problems on my own. I thought I would just look at the solutions, and that would enable me to solve similar problems. That didn’t quite work out, as I soon forgot the solutions, and even when I took extra pains to remember them, I could never quite spot a running pattern amongst problems.

I won the bronze medal at the Singapore Math Olympiad (Seniors) and an honorable mention at the Singapore Math Olympiad (Open). This is really not that big a deal. Medals and honorable mentions were given to many. There were 10 gold medals, in fact. I was hugely disappointed. I applied to Caltech, University of Chicago and Princeton for math, and didn’t get into any. I got scholarships to attend Illinois Institute of Technology, Hofstra and NTU, but they did not cover the whole cost. So I decided to stay in India.

While preparing for IIT-JEE, I bought a book on Math Olympiads. Why? Because I thought if I’d be able to solve Olympiad problems, I’d be able to solve any problem on the JEE paper (this has been a consistent and recurring trend in my life. I also invested time in reading Newton’s Principia because I thought if I understood his original thoughts, I’d be able to solve any mechanics problem). I could solve the elementary RMO problems, but not much more. I’d see a problem like: Prove that for every n\in\Bbb{N}, the sequence a_{n+1}=a_n+\lfloor \sqrt{a_n}\rfloor contains the square of an integer, where a_1=n.

I would be stumped. How would one solve such a problem? I had not been taught an algorithmic way of solving such a problem anywhere. Something I would be comfortable solving, for instance, would be determining the roots of a quadratic equation, etc. I would try to draw an exhaustive list of methods of attack, but would seldom succeed. I would look at the solution, and be hugely frustrated. It would seem rather long, messy and RANDOM. Why would ANYONE think along this arbitrary line? I never quite grasped the “trick” that problem solvers used to arrive at such a method. Soon, I began doubting my abilities as a problem-solver. Keep in mind that this was only after three years of shoddy problem solving. A less arrogant person would have given up much sooner.

On joining BITS, I soon realised my true interests lay in Mathematics rather than in Mechanical engineering, and began studying it day and night.  I would understand a lot of intricate concepts deeply and easily. However, when it came to proofs, however much I would dissect it and understand it, I would soon forget it. I have written blog posts on proofs that I soon forgot. Soon, I realised that it was my weak problem-solving aptitude that was causing this. I returned to my problem solving books sporadically, but without much success.

I began googling things like “become good mathematician bad problem solving”. Many mathematicians are of the opinion that bad problem solvers become good theory builders, and that a math olympiad experience harms one’s mathematical journey rather than helps it. It helped me regain some confidence in myself. However, alongside all this, I also read things like Terence Tao participated in math olympiad programs at the age of 11. Many math prodigies had shown exceptional potential in such competitions at the ages of 13-14. 13-year olds were capable of solving problems that I were beyond me, at the age of 21. I had always been fairly arrogant. But it began registering that maybe I would not be able to do anything noteworthy in this field. I began taking random IQ tests to see whether I was really smart “enough”. I bothered my girlfriend fairly often with all this, which amused her to no end.

In the winter holidays of 2013-2014, I returned to my Olympiad problem solving textbooks. There is a small paragraph in Paul Zeitz’s “Art and Craft of Problem Solving” that I had never quite read closely; this time I did. The gist was “get your hands dirty. GAUSS DID THE SAME”. WHY? How would it help? Didn’t proofs and solutions and methods automatically appear in front of brilliant people? Had I taken the wrong bloody approach for 5 years now? I suppose you might have guessed the answers to those questions by now.

Take the Putnam problem I had mentioned earlier:  Prove that for every n\in\Bbb{N}, the sequence a_{n+1}=a_n+\lfloor \sqrt{a_n}\rfloor contains the square of an integer, where a_1=n. Now, like an uneducated illiterate Barbarian, crunch numbers.

n                                      Sequence (until you get a square)

1                                                                                 1

2                                                                             2,3,4

3                                                                              3,4

4                                                                                4

5                                                                           5,7,9

6                                                                    6,8,10,13,16

7                                                                           7,9

8                                                                     8,10,13,16

9                                                                             9

10                                                                   10,13,16

11                                                                11,14,17,21,25

12                                                         12,15,18,22,26,31,36

13                                                                     13,16

14                                                                14,17,21,25

15                                                          15,18,22,26,31,36

16                                                                        16


I know you see a pattern! I know you do!! If you don’t, generate sequences until n=25. Then you surely will!

I hope this is helpful to anyone preparing for the olympiads, or anyone doing math for that matter. I have solved lots of IMO problems since then, and this approach of getting my hands dirty has also led me to understand undergraduate math much better.

More power to you.