Monthly Archives: March 2008

The wording of proofs

Dear Sir,

This may seem like a stupid question, but it has been bugging me for ages..

Is there a difference between me saying there are or there exist?

Similarly, is suppose equivalent to let and if? Also, is hence equivalent to therefore, so, i.e. ?

What I mean by “is there a difference” I mean could I lose marks in an exam if I write something equivalent?

Reply:

The short answer is this: If you write a clear and logical proof, you will never have marks taken off for using one phraseology or another. The point is that when you read proofs in a book or lecture notes, you should understand precisely what’s meant by the sentences used, rather than trying to memorize the precise adverbs, prepositions, etc. Now of course, since mathematical language depends on conventions like any other language, you should eventually learn them naturally . But it’s safe to say that in a proof, the primary focus should be on correctness and clarity . To achieve this, the most important point is obviously understanding .

To answer your specific questions:

-I can’t think of any particular situation where there would be a difference between `there are’ and `there exist’.

-`Suppose,’ ‘let,’ and, ‘if’ are used in different contexts so I can’t answer this question without some sample sentences you have in mind. Perhaps you are thinking of sentences that begin

`Let X be…’
`If X is…’
`Suppose X is…’

in which case they seem to be mostly equivalent.

-‘Therefore,’ ‘hence,’ and ‘so,’ are interchangeable in any mathematical sentence I can think of where they are used asĀ  connectives leading to a conclusion. ‘Hence’ and ‘so’ are a bit more informal, while ‘therefore’ might be more likely to occur in final conclusions. ‘i.e.’ is usually different. As in common parlance, it means ‘that is,’ and is used mostly to just rephrase something.

If your sensitivity to differences in the turns of phrases arises from a lack of confidence in following mathematical arguments, you should definitely take it seriously. You need to make your understanding immune to insubstantial differences. (In particular, you should have a good sense of which differences are ‘insubstantial.’)

Travel

This is to let students know that I am at a conference in Bangalore, India. I will have occasional access to the internet and will try to get to your questions as soon as possible, but you have to expect some delays until 5 April.

Local and global maxima

Hi Professor!

Just very quickly, what’s the difference between the global maximum/minimum of a function and the local maximum/minimum of a function? I understand that if a function achieves a global maximum at a point then it automatically achieves a local maximum, but vice versa is not necessarily true.

Also, the definitions look identical besides the local maximum def. containing epsilon.

Cheers!

Reply:

A function f has a local maximum at c if f(c) is \geq all the values at nearby points. f has a global maximum at c if f(c) is \geq the values at all points (in the domain). Therefore, a global maximum is a local maximum, but *not* vice versa. The best way to show the difference would be to draw a picture, but my graphic skills on the computer are very limited. So I’ll just have to write down a formula. Consider

f(x)=x^3-x

You should be able to see that f(x) has a local maximum at c=-1/\sqrt{3}. Near that point, the graph of f(x) is like a hill with apex above that point. What is the global maximum? Of course there is none, because f(x) keeps getting bigger as you move to the right along the x axis (at least starting from the point x=1/\sqrt{3}). One sometimes turns this into a problem with a global maximum by restricting the domain. That is, if we take the same function except with domain only on the closed interval [-100,100], you should be able to see that the global maximum is at x=100.

Chinese remainder theorem

Dear Professor Kim,

Do we need to prove the chinese remainder theorem by using bezouts lemma or by showing it is a bijective mapping?

Reply:

The Chinese remainder theorem says exactly that some map is bijective, so of course you need to show bijectivity. On the other hand, in proving the surjectivity part of it, one way is to use Bezout’s lemma.

One important point about the use of Bezout’s lemma is that it gives a constructive proof of surjectivity. Do you see what I mean by that?

Office hour today

I told a number of students that I would hold office hours today again in the 5th floor common room, but I had not realized that the college would actually be closed. There’s no way for me to reach the secretary for a group email either, so I’m putting a post here apologizing for the confusion.

Check your email after the end of the closure period, and I’ll send something about continuation.

L-functions

The theory of zeta and L-functions is an indispensable part of modern number theory. Recently, there was a conference on L-functions at the American Institute of Mathematics where some interesting new results of Andrew Booker and Ce Bian of Bristol were announced. At the n-category cafe, David Corfield posted a question about that article, to which I responded in vague terms. However, I did give a very brief summary of what L-functions are about. So I am attaching a link here for students interested in number theory.

More on canonical forms

Dear Professor Kim,

I encountered some problems when practising on the past papers.

1. In the proof of the Primary Decomposition Theorem, since the minimal polynomial m(T)=0, then Ker(m(T))=V, why is that?

2. I am still confused with how to use rank and null to decide a Jordan basis.

3. In the final process of finding the Real/Complex Jordan Canonical Form, if I have to multiply matrices E&(E transpose) with complex elements to get the Real JCF, is it right or I made a mistake (problem is I’ve checked several times that I didn’t make any mistake in the previous calculation)?

4. Relating to the previous question, is it possible to have real JCF and complex JCF the same?

Finally, since I’m in China right now I can’t access the web blog. Would you please copy the answers to my email? Thanks a lot!!

Reply:

1. As you say, if m(x) is the minimal polynomial, then m(T) is the *zero* endomorphism. What does it mean for the endomorphism to be zero?

2. The whole topic of computing Jordan bases is important, but hard to describe on the blog. It’s important to ask very specific questions. However, I can guess what difficulty you’re trying to express. For an endomorphism T and each eigenvalue a, we compute the Jordan basis corresponding to that eigenvalue. In the process, very relevant things to analyze are the kernels of

(T-aI)^k

for various k. For example, for k=1, the kernel is exactly the eigenspace corresponding to a. (Make sure you understand why this is so. I still find many people confused on this elementary point.) For k>1, we call these kernels the generalized eigenspaces. Also very important is that these kernels are nested:

Ker(T-aI) \subset Ker(T-aI)^2 \subset Ker(T-aI)^3 \subset \cdots

This also, make sure you understand why. The final important general relation is that

(T-aI)(Ker(T-aI)^{k+1})\subset (T-aI)^{k}

Anyways, in terms of the Jordan basis that you’ll see arranged in an array either in the notes or in my notes for 12-11-07, the bottom row is a basis for the kernel of (T-aI). The bottom *two* rows is a basis for the kernel of (T-aI)^2, and so on. Thus, the nullities of these powers of (T-aI) encode information about the shape of that array, from which one can extract the precise Jordan canonical form. Remind yourself precisely what the heights of the columns mean. These heights are exactly what you need for the precise Jordan canonical form.

Now to your question: Sometimes, you’ll see yourself given the *rank* of (T-aI)^k rather than its nullity. But don’t you know how to recover one from the other?

3. As a matter of terminology, the real or complex canonical forms of a symmetric bilinear form (or a quadratic form) are *not* called the *Jordan* canonical forms. If your confusion of the two reflects a conceptual confusion, you should clear it up right away. One very important distinction is that *similarity* of matrices is different from *congruence* of matrices. Look this up.

Anyways, *no*, you should not use complex matrices when finding the real canonical form even though it might luckily give you the right answer. The reason is that the real canonical form refers to a basis for R^n, and if you use complex transformations, the basis you end up with may be a basis for C^n.

4. The answer is yes. And I’m going to ask you back the question `*when* are they the same?’ Make sure you know the answer and the reason for it.

Norms

Just a quick question.

The norm of an ideal, e.g. , is taken to be |N(a)|. I am not sure I understand what this means exactly. For instance, the norm of is 2, but i am not sure how they used this fact.
Thanks.

Also, when are u available for consultation from here onwards and is there a revision class planned? ————————————————————————————————————————
Hi again.
I sent you a question earlier regarding the norm of an ideal, but i think i may have confused myself (and possibly you!)

Firstly, I understand the use of N()=|N(a)| but i think, now, that we are to use a different equation for multiple element ideals. I think that is why I was confused for .
Also, i should have mentioned in the example that we were in Z[sqrt(-17)], but i think you figured that already.
————————————————————————————————————————

Reply:

Actually, the ideal wasn’t transmitted properly, but I can guess what it was.

First of all, the norm of an ideal is related to the norm of a number, but not the same:

If A is a non-zero ideal inside the ring R of algebraic integers in an algebraic number field K, then

N(A)=|R/A|

the number of elements inside the finite ring R/A. In particular, it is always a positive number. The relation with the norm of a number is that if A=(a), i.e., it is generated by a single element a, then

N(A)=|N(a)|

Note that the absolute value symbol here is used in the usual sense, and gives a positive number. When we used it above, it meant the cardinality of a set. You should get used to both notations and figure out what makes sense from the context.

When the ideal has many generators, the relation is more complicated. So for A=(a,b) we have

(a)\subset A,

and hence,

N(A) \leq N((a))=|N(a)|

or, more precisely,

N(A) divides |N(a)| using some theorem from the notes. (Find it!)

A basic case for computing norms is for a maximal ideal in the ring of integers of a field extension as described by Dedekind’s theorem. For the case

Q(\sqrt{-17})

you mention, the ring of integers is

Z[\sqrt{-17}],

so that we can compute the decomposition of ideals by consider the reductions of x^2+17. For example,

x^2+17 \equiv  (x-1)^2\ \  mod\  2,

so that

(2)=P_2^2

in Z[\sqrt{-17}]

for the maximal ideal P_2=(2, \sqrt{-17}-1). You’ll find in the discussion of Dedekind’s theorem a proof of the fact that N(P_2)=2.

The point that is

Z[\sqrt{-17}]/P_2

is a field extension of Z/2 of degree equal to the degree of x-1, i.e., 1. That is to say,

Z[\sqrt{-17}]/P_2 =Z/2

So

N(P_2)=|Z/2|=2.

Do a bunch of exercises that compute norms of numbers and ideals. A basic useful fact of course is that

N(IJ)=N(I)N(J)

for any (non-zero) $I,J$. Thus, once you have the norms of prime ideals, you have the norm of any ideal (provided you have the prime decomposition, of course). Of course, this fact is more commonly used the other way around, that is, to *compute* the prime decomposition.

What are the norms of the numbers \sqrt{2} and \sqrt{3} in

Q(\sqrt{2},\sqrt{3})?

What is the norm of the ideal

(2^{1/3}, 5)

in Z[2^{1/3}]?

Some algebra questions

I was wondering whether you can help me with some issues I am having:

Notation:

Aut(R)

is the set of automorphism of a ring R.

1) how can you formally show that Aut(R) is a “group under composition”? I am not quite sure what the question is asking to show!

2) the other day you gave me an easy way of showing ring isomorphisms, and was wondering how to show

Aut(Q[x]/((x^2)-p))

is isomorphic to C2 (cyclic group of order 2) and describe the nontrivial element explicitly (where p is prime)

3) not sure how to approach questions like this

Aut(F2[x]/((x^3)+x+1)) = ?

and

Aut(Q) is trivial

would i have to use Eisensteins criterion?

4) how can i show that any automorphism of reals is continuous and that

Aut(R)

is trivial?
————————————————————————————————————————
Also, would you be able to tell me how to compute the complete factorization into Q-irreducible factors for these polynomials:

i)a P[x] in the form of

(x^a + 1)

where a is a positive integer, eg (x^10 + 1) or (x^16 + 1)

ii) (x^5 + 10x^4 + 13x^3 – 25x^2 -68x – 60)
————————————————————————————————————————
Show that R[x]/(x^2 + a) is isomorphic to Complex if a>0 and RxR if a0 and RxR if a<0 where R is Real.

Reply:

(1) You’ve probably learned that the set of bijections of any set is a group under composition. Now when the set is a ring R, then Aut(R) is the subset of the group of bijections from R to R consisting of the maps that preserve the two laws of composition and the unit(s). Now what does it take to show that a subset is in fact a subgroup?

(2) To get a ring homomorphism from Q[x]/(x^2-p) to itself, you need to have a map

f:Q[x]->Q[x}

that takes x^2-p to x^2-p. Such a ring homomorphism is entirely determined by the value f(x). (Why?) But to preserve the polynomial, we must have f(x)=x or -x. Both of these will induce automorphisms of Q[x]/(x^2-p) .

Incidentally, depending on what you’ve learned and what’s expected in class, you might have to provide much more detail than I’ve written here. (The same goes for the other problems.)

(3) Eisenstein’s criterion, dealing with irreducibility of integer coefficient polynomials, is irrelevant here. But for polynomials of degree 2 or 3, a straightforward criterion for irreducibility is the non-existence of a root in the field. Use this to check that x^3+x+1 is irreducible. As a result, F_2[x]/(x^3+x+1) is a field extension of F_2 of degree 3. So the group of automorphisms is of order at most 3. Now, for a field of characteristic 2, the squaring map

a-> a^2

is a ring homomorphism. Think about this carefully. It might be convenient to note also that an endomorphism of a finite field is automatically bijective. (Why?)

To see the triviality of Aut(Q), note that any ring homomorphism f:Q->Q must have f(0)=0 and f(1)=1. But then, by additivity of the map, f(n)=n for any natural number. If you have a positive rational number r=n/m with m>0, then

f(mr)=mf(r)

on the one hand, and

f(mr)=f(n)=n

on the other. So

mf(r)=n

and

f(r)=n/m=r.

Now deal with the negative numbers in some obvious way.

(4) This is quite an interesting fact. The point is that a field automorphism of R must preserve the *order* of R. This is because

a>b

iff

a-b>0

iff

x^2-(a-b)

has a root in R. This is a property that is preserved by any field automorphism. Now can you check that an order-preserving map of R is necessarily continuous? Here, you might have to review the precise definition of continuity from basic analysis.

Once you have the continuity, the triviality of Aut(R) follows from the corresponding fact for Q and the *densenesss* of Q in R.
————————————————————————————————————————
(i) There is a recursive algorithm. A basic statement is that

x^p-1=(x-1)(x^{p-1}+x^{p-2}+…+x+1)

and

(x^{p-1}+x^{p-2}+…+x+1)

is irreducible. You can show this using the substitution x->x+1 and Eisenstein’s criterion. For other cases, do some research on cyclotomic polynomials, as you seem to have done already. Remember to look for the *recursive* algorithm, which is the most efficient way. These polynomials are very important in algebraic number theory, but also its applications to information theory.

(ii) You seem to have figured out already the substitution that reduces this to Eisenstein’s criterion. Unfortunately, I don;’t know any clever method for finding such substitutions. There might be other proofs of irreducibility for this polynomial, depending on what else you’ve learned.
———————————————————————————————————————–
I hope you’ve learned already that C is isomorphic to R[x]/(x^2+1). Once you see this the first part of the problem is rather straightforward. That is, if a>0, can you cook up an isomorphism

R[x]->R[x]

that takes x^2+a to x^2+1? Why doesn’t it work when a<0?

In fact, when a<0, we get

x^2+a=x^2-(-a)=(x-\sqrt{-a})(x+\sqrt{-a}).

Now use the Chinese remainder theorem.

Education, in Singapore and elsewhere

On the mathematical physics web log `The n-category cafe,’ a number of people have been discussing the teaching of mathematics, prompted by an article in the Los Angeles times. I ended up contributing a few scattered comments. A link is included here for the possible amusement of my UCL students.