Allen Knutson's other class

Lie algebra from Dynkin diagram

2010-04-27T13:36:00.000-07:00

Here is the construction I gave in class for a Lie algebra given its Dynkin diagram.

Next will be some stuff about Weyl groups and Weyl chambers, delaying the fact that simple reflections generate N(T)/T.

We're going to do other chapters from here next, though in a different order: first the Bruhat decomposition, then stuff about Weyl chambers, filling the hole mentioned above, and then the Borel-Weil theorem that lets us construct all the irreps for complex reductive Lie groups.

April 14

2010-04-14T10:21:00.000-07:00

If K is compact with discrete center, pi_1(K) is finite. Hence there are finitely
many Lie groups with that Lie algebra. Proof: use Hurewicz to connect to H^1, and Lie algebra cohomology to show that H^1 vanishes over R.

The angle between any two roots must be 90, 120, 135, 150, or 180.

There are at most two root lengths in a connected root system, and if two they differ by a factor of sqrt(2) or sqrt(3).

Next time: simple systems, Dynkin diagrams, their classification.

Old notes

2010-04-12T08:21:00.000-07:00

Here are my notes from a previous incarnation of this class. The bottom one is the one we followed to get to root systems.

Feb 15, 17, 21

2010-02-23T12:36:00.000-08:00

Gel'fand-Cetlin patterns.
Theorem: they compute weight multiplicities iff V_lambda (for GL(n)) decomposes as the sum of V_mu (for GL(n-1)) where mu intersperses between lambda.
(We'll prove this later.)

Weyl integration formula.

Bruhat decomposition for GL(n).

The character of T acting on a polynomial ring is formally a rational function.

The weight multiplicities in V_lambda are bounded above by those in a certain polynomial ring.

That's not S_n invariant; so let's hit it with S_n to symmetrize it.
Theorem next time: the Weyl character formula, which says that that's the right answer.

Feb 10

2010-02-10T10:29:00.000-08:00

Thm. Multiplicity diagrams of U(n) reps are S_n-symmetric.
Proof. Use S_n to define maps between the weight spaces.

Thm.
1. If V is pointed at lambda, then V contains a unique irrep pointed at lambda.
2. If V,W are pointed at lambda,mu, then V tensor W is pointed at lambda+mu.
3. Alt^k(C^n) is pointed at (1,...1,0,...0) with k 1s.

Thm.
For every weakly decreasing lambda, there exists a unique irrep pointed at lambda, and these are all the irreps of U(n) or GL(n).

Proof. Tensor together Alt^ks to produce a rep pointed at lambda.
Let V be any rep; we'll try to write it as a sum of these V_lambda.
It's enough to check U(n)-isomorphism, and for that, it's enough to check the character, i.e. the multiplicity diagram.
Prove inductively that we can write any S_n-symmetric Z-valued function on Z^n, of finite support, as a linear combination of characters of these V_lambda.
Since irreducible characters are orthogonal, there can't be any other irreps.

Feb 3,8

2010-02-08T19:36:00.000-08:00

Representations of tori. Weights. Weight multiplicity diagrams.
The Lie algebras of GL(n), SL(n), U(n), SU(n).
Weyl's unitary trick for those groups. Corollary: complete reducibility.
Thm: the irreps of SL(2) are exactly the Sym^k(C^2).

Dominance order on Z^n.

(Nonstandard) Definition: a representation V of U(n) is pointed at lambda if lambda is a weight of V, its multiplicity is 1, and lambda dominates all the other weights of V.

Feb 1

2010-02-02T10:24:00.000-08:00

Orthonormality of characters extends to measurable representations of groups for which one can define an invariant, finite, measure, e.g. S^1.
We know enough irreps of S^1, namely z |-> z^n for each integer n, that (by Fourier theory) we must have found all the characters of irreps. So that's them and they're all 1-dim.

Def. Algebraic subgroup of GL(n).
Def. Algebraic representation, meaning all the matrix coefficients are polynomials in the original matrix entries or det^{-1}.
(Changes of basis are given by linear polynomials, so the definition doesn't really depend on choice of basis.)

Non-ex. C acts on C by z |-> exp(lambda z). That's a smooth rep, but not algebraic.
Ex. SL(2) acting on Sym^2 C^2. The matrix entries are homogeneous quadratic.

Thm. Let N_+ be the upper triangular 2x2 matrices with 1s on the diagonal.
Then in any continuous representation, there are 1-dim invariant subspaces.
If the representation is algebraic, then those subspaces are trivial representations.

Let's look for representations of G = SL(2). They should all occur inside algebraic functions on SL(2), which is C[a,b,c,d] / (det = 1).
Rather, for each irrep V, we should find V @ V^*.
So take the 1 x N_+ invariants, to try to cut down V^* to something smaller, but by the theorem, nonzero.
Claim. The only 1 x N_+ invariant functions on SL(2) are C[a,c].
(We'll complete this proof next time.)

Cor. Each irrep occurs inside some Sym^k(C^2).
Next time: the Sym^k(C^2) are actually irreducible, and each has a unique N_+-invt vector.

Jan 27

2010-01-31T18:12:00.000-08:00

We proved:
Irreps of GxH are each the tensor product of an irrep of G with one of H.
C[G] is the sum over irreps V of V^* @ V, as a GxG-representation.
Character tables are square, i.e. the number of irreps is the number of conjugacy classes.
If G > H, two finite groups, then H misses some conjugacy class of G.
If G = U(n), H = T^n, then H hits every conjugacy class of G.

We didn't prove, but it's true:
As an algebra, C[G] is the direct sum of matrix algebras End(V), V running over irreps.

Jan 25

2010-01-25T10:41:00.001-08:00

Overview:
1. Representation theory of finite groups.
2. ... of SL(2).
3. ... of U(n) and GL(n).
4. The adjoint representation of a Lie group; root system and Weyl group.
5. Classification of nice Lie groups.
6. Rep theory of general Lie groups.

Defs. Reps of finite groups on finite-dim complex vector spaces.
Irreducible, indecomposable.
Hom(V,W) as a rep. Equivariant maps.
Schur's lemma.
\pi_G|_V = 1/|G| \sum_G g|_V is a projection whose image is the G-invariants,
and whose trace is the dimension of the G-invariants.

Thm. Orthonormality of characters.
Cor. # irreps is at most # conjugacy classes.
Ex. S_3, S_4.

Welcome to Math 6500

2010-01-25T10:40:00.000-08:00

The class homepage is here.

Final exam with answers

2008-06-12T07:37:00.000-07:00

Here.

Answers to practice problems

2008-06-10T22:32:00.000-07:00

1a. Let a,b be natural numbers, a < b. Assume there exist x,y in the naturals such that xa + yb = gcd(a,b). Show y < 10.

A. It depends on whether a=0 or a>0.

If a=0, then the gcd is b. x doesn't matter, and y must be 1. 1 < 10, huzzah.

If a>0, then the largest the gcd can be is a. On the other hand, the smallest positive number that xa+yb can be is a. So both must be a. Hence x=1, y=0. 0 < 10, huzzah redux.

b. Give an example where x > 10.

A. Apparently we're in the a=0 case, since otherwise x would have to be 1.
So y must be 1, and x and b are free to roam. Take x = 57 and b = 1066, for example.

2. What are the last two decimal digits of 11²⁰⁰⁸?

A. 81.
More generally, 11ⁿ == 10n + 1 mod 100.
This is easy to prove by induction: multiply both sides by 11, obtaining
11ⁿ⁺¹ == 110n + 11 == 10n + 11 == 10(n+1) + 1 mod 100.

3a. Draw an example of finite sets X,Y,Z and functions f:X->Y, g:Y->Z where |X| > |Y|, f is not onto, but the composite g o f is onto.

A. Say X = {a,b,c}, Y = {taupe,vermilion}, Z = {cheese}. Let f(x) = taupe for any x, and g be the only function Y->Z.

b. Prove that |Y| is not equal to |Z| (not just in your example, but in any example).

A. Since g o f is onto, the map image(f) -> Z (made by restricting g) is also onto.
Hence |Z| is less than or equal to |image(f)|. Since image(f) is contained in Y, |image(f)| is less than or equal to |Y|. But f is not onto, so it's strictly contained. Hence |image(f)| < |Y|.

4. In each of the following: can you turn the following two congruences into one, and if so, what?

v1. b congruent to 2 mod 6, b congruent to 7 mod 10.

A. No you can't; the first says b is even, the second says it's odd.
Whereas any single congruence does have solutions.

v2. b congruent to 1 mod 6, b congruent to 7 mod 10.

A. The first can be rewritten as "b congruent to 7 mod 6". Hence 6 and 10 divide b-7, or equivalently, 30 divides b-7. So they can be rewritten as e.g. b-2 congruent to 5 mod 30.

5. Say b == a+7 mod 27, and a² == b² mod 27.
Figure out a,b mod 27.

A. a² - b² == 0 mod 27.
So (a+b)(a-b) == 0 mod 27.
So (a+b)(-7) == 0 mod 27.
Since gcd(7,27) = 1, we can cancel the 7.
So a+b == 0 mod 27.
So 2a+7 == 0 mod 27.
How to cancel the 2? Subtract 27 from both sides, for example; 2a-20 == 27 == 0 mod 27.
So a-10 == 0 mod 27. Hence a == 10 mod 27, b == 17 == -a mod 27.

109 roundup

2008-06-09T16:21:00.000-07:00

Definitions.
Quantifiers.
Proofs. Case check, contradiction, induction, series of reductions.
Make sure during induction that the chain of implications isn't broken anywhere.
To prove sets are equal, show both inclusions.
To prove functions are equal, check them on every element.
Functions; 1:1, onto, invertible.
Baby number theory. The division algorithm, Euclid's algorithm, the fact that the gcd can be written as an integer linear combination of the two numbers, unique factorization into primes. Congruences. Chinese Remainder Theorem.
Partitions and equivalence relations.
(n choose k) and the Pascal recurrence for it.

Office hours

2008-06-09T15:34:00.000-07:00

I'll be in my office (7450 APM) Tuesday 11-4 and Wednesday 11-2. I'll be giving preference to my Math 109 students on Tuesday and my Ma 20b students on Wednesday, but anyone will be welcome any time.
If you want to call ahead to check "Are you already tied up with the other class?", feel free; my office number is 858-534-6450.
(Don't get 7450 and 6450 confused!)

Practice problems for the final

2008-06-08T20:57:00.000-07:00

I'm having some writer's block coming up with extra problems, but I'll keep working at it. Here are three so far. (As usual, it's trickier than what's actually on the final.)

1a. Let a,b be natural numbers, a < b. Assume there exist x,y in the naturals such that xa + yb = gcd(a,b). Show y < 10.

b. Give an example where x > 10.

2. What are the last two decimal digits of 11²⁰⁰⁸?

3a. Draw an example of finite sets X,Y,Z and functions f:X->Y, g:Y->Z where |X| > |Y|, f is not onto, but the composite g o f is onto.

b. Prove that |Y| is not equal to |Z| (not just in your example, but in any example).

4. In each of the following: can you turn the following two congruences into one, and if so, what?

v1. b congruent to 2 mod 6, b congruent to 7 mod 10.

v2. b congruent to 1 mod 6, b congruent to 7 mod 10.

5. Say b == a+7 mod 27, and a² == b² mod 27.
Figure out a,b mod 27.

Answers to HW #6

2008-06-07T10:59:00.000-07:00

1. What are all the partitions of {1,2,3,4}?

A. Organized by the number of cells:
With 1 cell, there's just {{1,2,3,4}}.
With 2 cells, their sizes could be 1+3 or 2+2. There are four of the first type, like {{2},{1,3,4}}, and three of the second, like {{1,3},{2,4}}.
With 3 cells, the only way to break them up is 2+1+1. There are (4 choose 2) of these, like {{2,4},{1},{3}}.
With 4 cells, there's just {{1},{2},{3},{4}}.
In all, 1+4+3+6+1 = 15.

2. Let PowerSet(X) denote the set of subsets of X, and Partitions(X) denote the set of partitions of X. Let f:X->Y be a function from X to Y.

a. Define a function (properly called PowerSet(f)) from PowerSet(X)->PowerSet(Y), in a nontrivial way. Once you've found the right one, you should be able to prove that if f is injective, then PowerSet(f) is too; do prove this.

A. If S is a subset of X, define PowerSet(f) (S) = {f(x) : x in S}.
Sometimes this is denoted f(S), by the way.

To show this is injective, let S,T be two subsets of X, and assume PowerSet(f)(S) = PowerSet(f)(T). Then for all s in S, f(s) is in PowerSet(f)(S), so f(s) is in PowerSet(f)(T), so there exists t in T such that f(s) = f(t). But then s = t, since f is assumed 1:1. This shows that S is a subset of T. The same argument works to show T is a subset of S. So they are equal.

b. Also, if f is surjective, show that PowerSet(f) is too.

A. Let T be a subset of Y, and let S = f^-1(T). Then I claim that PowerSet(f)(S) = T,as follows. An element y of Y is in PowerSet(f)(S) iff there exists s in S such that f(s) = y. By our definition of S, such a y must be in T. So far this shows that PowerSet(f)(S) is contained in T.
To show the opposite inclusion, we use the fact that f is onto: for any t in T, there does indeed exist s in f^-1(T) such that f(s)=t.

c. Define a function (properly called Partitions(f)) from Partitions(Y)->Partitions(X) -- it goes backwards! Once you've found the right one, you should be able to prove that if f is surjective, then Partitions(f) is injective; do prove this.

A. Given a partition P of Y, there is a natural surjection Y ->> P. Compose the maps X -> Y -> P and define Partitions(f)(P) to be the partition of X induced by the map X -> P.

Given a partition Q of X, we can almost make a partition P of Y; let P = {f(S) : S in Q}.
It is easy to check that the subsets f(S) of Y are disjoint and nonempty; the only worry is that they may not cover Y. But if f is onto, then they do.
It is also easy to check that if we start with a partition of Y, build a partition of X as above, and then build a partition of Y as just described, we get back where we started. That shows that Partitions(f) is injective.

d. Also, if f is injective, show that Partitions(f) is surjective.

A. Let Q be a partition of X, and let P' = {f(S) : S in Q}.
This isn't quite a partition of Y, as explained above; it may not cover Y.
So let P = P' union { Y \ image(f) }, i.e. add an extra cell containing the rest of Y.
Then it is easy to see that Partitions(f)(P) = Q.

3. Let X be a subset of Y, where Y is finite. How many subsets of Y contain X? Give (and explain) a formula in terms of |X|, |Y|.

A. The subsets of Y containing X correspond in an obvious way to the subsets of Y \ X,
of which there are 2^{|Y \ X|} = 2^{|Y| - |X|}.

4. Let f(x) be a polynomial of degree m. Show that f can be written as a linear combination of the polynomials {x choose k} for k=0,1,...,m. (I shouldn't need to say it, but hint: induction.)

A. Let C be the coefficient of x^m in f(x). Then f(x) - C m! {x choose m} is a polynomial of degree at most m-1. If m=0, we're done; otherwise we use induction on m to say that f(x) - C m! {x choose m} is a linear combination of {x choose k} for k=0,1,...,m-1. Add on C m! {x choose m} to that combination, and we get the desired conclusion.

5a. Say f(x) = sum_k=0^m c_k x^k/k!.
Give a formula for the polynomial f'(x).

A. f(x) = sum_k=0^m-1 c_k+1 x^k/k!.
This takes a couple of steps; first compute the derivative, then notice that we can drop the k=0 term because it's 0 anyway, then shift k by 1.

b. Say f(x) = sum_k=0^m c_k {x choose k}.
Give a formula for the polynomial f(x+1)-f(x).

A. f(x+1) - f(x) = sum_k=0^m-1 c_k+1 {x choose k}.
This is proved using the Pascal recurrence {x+1 choose k} - {x choose k} = {x choose k-1}. After that do the same as in part (a).

c. Use (b) to prove that a polynomial f(x) takes on integer values for every integer x if and only if it is an integer combination of {x choose k}s.
(So we come full circle: one of the first things we proved was that {x choose 2} is such a polynomial.)

A. Since the {x choose k} take on only integer values (at x integer), if the (c_k) are all integer then f(x) will only take on integer values too. That's the easy direction.

Now assume that f(x) only takes on integer values. Hence f(x+1) - f(x) is also always integer. We calculated it a moment ago:
f(x+1) - f(x) = sum_k=0^m-1 c_k+1 {x choose k}.
This is a polynomial of degree < deg f(x). So by induction, its coefficients are all integers.
So far we know that c₁, c₂, ..., c_m are integers.
But what about c₀?
Luckily, c₀ = f(0), which was assumed to be an integer. So all the coefficients are integers.

[The point of this question was to give a good way of understanding the surprising fact that a noninteger polynomial may take on only integer values. It says that the usual way of writing polynomials, as combinations of (x^k), is not good for studying this question. Rather one should work with combinations of (x choose k)s.]

Monday June 2

2008-06-02T18:04:00.000-07:00

To any partition P of X, we associated the natural surjection X ->> P.
To any function f : X -> Y, we associated a partition of X, where the cells are the preimages of elements of image(f).

This lets us refine our previous theorem about factoring functions f : X -> Y;
any function factors uniquely as X -natural surjection->> P -> S -inclusion-> Y,
where P is a partition of X, S is a subset of Y, and P->S is 1:1 and onto;
in particular, P must be the partition associated to f, and S must be the image of f.

We defined relations, and associated to any partition of X, a relation ~_P from X to X.
Then pointed out three properties it has: reflexive, symmetric, transitive.
Any relation with those properties is an equivalence relation.
Then we looked at a bunch of relations, and figured out how they failed to be equivalence relations.

Q. Is the following an equivalence relation on N?
a ~ b iff there exists an m such that a | b^m, b | a^m.

Friday May 29

2008-05-31T23:54:00.001-07:00

We defined a partition of a set X: it is a set P of subsets of X, with the properties that
(1) union_{S in P} S = X, i.e. x in X <=> there exists S in P with x in S
(2) for any two distinct S₁, S₂ in P, the intersection is empty
(3) the empty set is not an element of P.

We also defined the {n choose k} notation for binomial coefficients, proved the Pascal recurrence combinatorially, and proved the formula with factorials in two different ways (by induction and using a bijection).

(Note that the Wikipedia article differs from how I did things in terms of which one is the definition and which one is the theorem. I think the order given there is silly.)

Something I didn't have time to emphasize: the middle expression in

makes sense for arbitrary n, not just for integers. (k should still be an integer.) This is important for the last HW question.

Applications of number theory

2008-05-29T13:54:00.000-07:00

I mentioned RSA encryption a number of times. What is exceptionally notable about it is that you can tell everyone "Send me messages in this secure way", and you can read the messages, but nobody else can read one another's messages. So it doesn't require you, as your first step, to smuggle a code book.

Lots more in Schroeder's Number theory in science and communication, which the library seems to have four copies of (in various editions). This is where I learned about the golden ratio's use in designing speakers.

Last HW due Friday June 6

2008-05-29T12:09:00.000-07:00

1. What are all the partitions of {1,2,3,4}?

2. Let PowerSet(X) denote the set of subsets of X, and Partitions(X) denote the set of partitions of X. Let f:X->Y be a function from X to Y.

a. Define a function (properly called PowerSet(f)) from PowerSet(X)->PowerSet(Y), in a nontrivial way. Once you've found the right one, you should be able to prove that if f is injective, then PowerSet(f) is too; do prove this.

b. Also, if f is surjective, show that PowerSet(f) is too.

c. Define a function (properly called Partitions(f)) from Partitions(Y)->Partitions(X) -- it goes backwards! Once you've found the right one, you should be able to prove that if f is surjective, then Partitions(f) is injective; do prove this.

d. Also, if f is injective, show that Partitions(f) is surjective.

3. Let X be a subset of Y, where Y is finite. How many subsets of Y contain X? Give (and explain) a formula in terms of |X|, |Y|.

4. Let f(x) be a polynomial of degree m. Show that f can be written as a linear combination of the polynomials {x choose k} for k=0,1,...,m. (I shouldn't need to say it, but hint: induction.)

5a. Say f(x) = sum_k=0^m c_k x^k/k!.
Give a formula for the polynomial f'(x).

b. Say f(x) = sum_k=0^m c_k {x choose k}.
Give a formula for the polynomial f(x+1)-f(x).

c. Use (b) to prove that a polynomial f(x) takes on integer values for every integer x if and only if it is an integer combination of {x choose k}s.
(So we come full circle: one of the first things we proved was that {x choose 2} is such a polynomial.)

Wednesday May 28

2008-05-28T19:48:00.001-07:00

When does ab congruent to ac mod n imply b congruent to c mod n? Answer: if gcd(a,n)=1.
In general, we only learn b congruent to c mod n/gcd(a,n).

Def: the image of a function.
Theorem: every function factors as a surjection followed by an injection.
This was an existence statement; we made a uniqueness statement, which we'll prove next time.

Answers to midterm #2

2008-05-27T20:33:00.000-07:00

Here.

Spread on midterm #2

2008-05-27T19:26:00.000-07:00

70+ A
50-70 B
30-50 C
10-30 D
<10 F

Remember, this is only what you'd get if through some rip in the space-time continuum all other data going into your class grade were lost. Your actual letter grade will be calculated using the number, not this letter above, so don't worry about being on a cusp between two letters.

No office hours this week

2008-05-19T16:27:00.000-07:00

I'm out of town.

Answers to HW #5

2008-05-19T00:58:00.000-07:00

Given a natural number n and a prime p, let n_p denote the power to which p appears in the unique factorization of n. So n = product of {p^n_p : p prime}, where most of the factors are p⁰ = 1.

1. Write down necessary and sufficient conditions on the exponents {b_p, c_p} for b|c to be true.

A. For every p, b_p should be less than or equal to c_p. (I'm only writing out the English because I don't know how to produce the symbol in HTML.)

2. Give a formula for gcd(b,c)_p in terms of b_p, c_p.

A. gcd(b,c)_p = min(b_p, c_p), the minimum of the two.

3. Prove that gcd is associative, in that gcd(a,gcd(b,c)) = gcd(gcd(a,b),c).

A. Either way, the exponent on p is min(a_p, b_p, c_p).

4. Let d be a common divisor of b,c. Show that gcd(b/d, c/d) | gcd(b,c).

A. Looking at just the p-exponents, we know d_p is less than or equal to b_p, c_p. Then the statement is that for all p,
min(b_p - d_p, c_p - d_p) is less-or-equal min(b_p, c_p).
This is true; indeed, the difference is d_p.
So the better statement was
gcd(b/d, c/d) * d = gcd(b,c).

5. The continued fractions expansion of a positive irrational real number r is
r = n₁ + 1/(n₂ + 1/(n₃ + 1/...
where each n_i is a positive natural number.
OOPS possibly n₁=0, but the others are definitely positive.
If r is rational, one can do the same thing, but the expansion terminates.

a. Show that "the" continued fractions expansion exists uniquely for any rational r.
(Actually this holds for real r too, but one needs to study convergence properly to make sense of that statement, and we haven't and won't.)

First we address existence. Let r = n/d, for "numerator" and "denominator".

Proof by induction on d (which is at least 1).
If d=1, then r = n, so take n₁ = n and that's the complete expansion.
If d > 1, let n₁ be the greatest integer < r.
So r = n₁ + (n - d*n₁)/r, where the new numerator is in (0,r).
By induction, the fraction r/(n - d*n₁) has a finite continued fractions expansion.
(Here we crucially used n - d*n₁ < r to justify the invocation of induction.)
Sticking it into r = n₁ + 1 / r/(n - d*n₁), we get a c.f.exp. of r.

Now uniqueness, also done by induction on d.
If d=1, then r = n is the only c.f.exp., because having another term will spoil integrality.
Now assume d>1.
If r = n₁ + 1/(n₂ + 1/(n₃ + 1/... = m₁ + 1/(m₂ + 1/(m₃ + 1/...,
then the greatest integers less-or-equal to these three equal numbers must be the same.
For the second and third, said greatest integers are n₁, m₁.
Subtract those off, invert both sides, and you have an equality between two c.f.expansions of a rational with smaller denominator than you started (as in the previous proof).
So by the same induction, these two expansions must be equal.

b. Optional: Compute it for the square root of 5.

A. Playing around with a calculator, it is easy to see that the first few n_i are 2,4,4,4,4... which suggests that one is stuck in a loop. Proving that involves a little bit of algebra with sqrt(5).

c. Compute it for 140/49.

140/49 = 2 + 1/(42/49)

49/42 = 1 + 1/(42/7)

42/7 = 6

so 140/49 = 2 + 1/(1 + 1/6).

d. Explain the relation to the Euclidean algorithm (computing gcd(m,n) vs. expansion of m/n).

A. They're really "the same".
At each step of the Euclidean algorithm, one must compute the remainder after division of m by n. If one instead wrote down the multiple of n being subtracted,the sequence of such multiples is exactly the sequence of n_i.
The sneaky thing is that to compute the continued fractions expansion of m/n, it is not important that m,n are in lowest terms. If one never simplifies them during the computationg of the c.f.exp., the last denominator one meets is gcd(m,n). For example, gcd(140,49)=7 in the one above.

Answers to HW #4

2008-05-19T00:43:00.000-07:00

1. We claimed several properties of gcds when stating the Euclidean algorithm. Prove them all:

a. gcd(a,b) = gcd(-a,b) = gcd(a,-b)

b. gcd(0,a) = a

c. gcd(a,b) = gcd(b,a).

A. Let's do (b) first.
Plainly a|0 and a|a, since 0 = 0*a and a = 1*a.
If b|0 (which it always does) and b|a, then b|a.
So we've checked that a is indeed a gcd of 0 and a.

Now (a) and (c). Let g be any of gcd(a,b), gcd(-a,b), gcd(b,a) (as the proofs are similar).
Then g|a and g|b. (If g|-a, then g|a, etc.)
So it is a common divisor.
Now let c be such that c|a and c|b.
Then we argue that c|g. (If g = gcd(b,a) this is easy; otherwise we use c|a <=> c|-a, etc.)
Hence g is a gcd of a and b.

2. Prove gcd is in some sense associative, in that gcd(a,gcd(b,c)) = gcd(gcd(a,b),c) for all a,b,c in Z.

A. Each one boils down to g|a, g|b, g|c, and for any h such that h|a, h|b, h|c, one has h|g.
At that point the proof becomes the same as the one showing that gcds are unique, as we did in class.

3. Prove that nⁿ > n! * 1000 (meaning n * (n-1) * ... * 3 * 2 * 1 * 1000), for all n at least 10.

A. Check the case n=10 by computer: 10! ~ 3.6 million < 10⁷, so 10! * 1000 < 10¹⁰.
Now assume n>10. We know
(n-1)^n-1 > (n-1)! * 1000 by induction.
Multiply both sides by n:
n * (n-1)^n-1 > n! * 1000
and observe that the left side is smaller than
n * n^n-1 = nⁿ.

4. For all a,b,c, show that gcd(ab,c) | gcd(a,c) gcd(b,c), and give an example where they are unequal.

A. Actually I don't know how to do this without prime factorization; with that it becomes easy.
Really I assigned it to make people appreciate prime factorization once we have it.

For an example, take a=b=c=2. Then it says 2 | 4.

Answers to HW #3

2008-05-19T00:30:00.000-07:00

1. Let f(n) be a function from N -> N (the naturals), satisfying f(0) = 0 and for n>0, f(n) = 2 * f(n-1) + 1.
Prove that for all n in the naturals, f(n) = 2ⁿ - 1.

A. The proof is by induction on n.
The base case is n=0, which is given to us.
Now assume n>0. Then
f(n) = 2 f(n-1) + 1
= 2 (2^n-1 - 1) + 1 by induction
= 2ⁿ - 2 + 1
= 2ⁿ - 1, as we wanted to show.

2. Prove that for all n at least 2 (this induction doesn't start from 0, or from 1!),
that the product of the numbers {1 - 1/i : i = 2,...,n} is 1/n.

(I guess you can start from 1 if you want, regarding the LHS as an empty product, so = 1. But the problem doesn't ask you to think about that.)

A.
For n=2, the statement is that 1 - 1/2 = 1/2, which is true.
Now assume n>2.
Then product_i=2ⁿ (1 - 1/i) = (1 - 1/n) product_i=2^n-1 (1 - 1/i)
= (1 - 1/n) 1/(n-1) by induction
= 1/n, as was to be shown.

3. Let f:N->N satisfy
f(0) = 38
f(1) = 39
for all n at least 2, f(n) = 3f(n-1) - 2f(n-2).
Prove that for all n in N, f(n) = 2ⁿ + 37.

A. The formula is easy to check for n=0,1.
Now assume n is at least 2.
Then f(n) = 3 f(n-1) - 2 f(n-2)
= 3 (2^n-1 + 37) - 2 (2^n-2 + 37) by (strong) induction; each of n-1, n-2 are < n
= (3-1) 2^n-1 + 37
= 2ⁿ + 37 as was to be shown.

Practice midterm #2

2008-05-19T00:28:00.000-07:00

Here.

Some links on recent material

2008-05-15T13:49:00.001-07:00

Euclidean algorithm
GCD
Prime factorization and its existence and uniqueness
Next time:
Chinese Remainder Theorem

HW #5 due Friday May 16 (problem 5 edited)

2008-05-12T11:59:00.000-07:00

Wednesday & Friday May 7 & 9

2008-05-09T14:12:00.000-07:00

Wednesday:
Subrings of the complex numbers.
Irreducible vs. prime.
In {a + b sqrt(-5)}, 2 is irreducible but not prime.
Prime => irreducible.

Friday:
In Z, irreducible => prime.
Unique factorization.
We did unique factorization by weak induction on the number of primes being multiplied together; maybe it would have been more intuitive to do it by strong induction on n. (We found two factorizations of n/p_k, and could have said "since n/p_k < n, by induction we know that...")

Monday May 5

2008-05-07T10:35:00.000-07:00

We proved that the Euclidean algorithm does, indeed, calculate gcd(a,b).
I mentioned a couple of fun properties of it, like the relation to Khinchin's constant.

Then we proved what will be a much more useful result:
for any a,b in Z, there exist x,y in Z such that gcd(a,b) = xa+yb.

HW #4 due Friday May 9 (back on schedule)

2008-05-03T06:22:00.000-07:00

In the below you're only allowed to discuss gcd using the definition from class, not stuff you might know about it related to e.g. prime factorization. We haven't proven that yet.

1. We claimed several properties of gcds when stating the Euclidean algorithm. Prove them all:

a. gcd(a,b) = gcd(-a,b) = gcd(a,-b)

b. gcd(0,a) = a

c. gcd(a,b) = gcd(b,a).

2. Prove gcd is in some sense associative, in that gcd(a,gcd(b,c)) = gcd(gcd(a,b),c) for all a,b,c in Z.

3. Prove that nⁿ > n! * 1000 (meaning n * (n-1) * ... * 3 * 2 * 1 * 1000), for all n at least 10.

4. For all a,b,c, show that gcd(ab,c) | gcd(a,c) gcd(b,c), and give an example where they are unequal.

Answers to HW #2

2008-05-02T17:15:00.000-07:00

Let f:X->Y and g:Y->Z be functions.

1. Give an example where g o f is onto, but f is not onto.

Let X = {a}, Y = {3,green}. Let f = {(a,green)}, and g = {(3,a),(green,a)} (the only possibility for g).

2. Assume g o f is 1:1, and f is onto. Show that g is 1:1.

Let y1,y2 in Y have g(y1)=g(y2). We want to show y1=y2.
Since f is onto, there exist x1,x2 such that f(x1)=y1, f(x2)=y2.
So (g o f)(x1) = g(f(x1)) = g(y1) = g(y2) = g(f(x2)) = (g o f)(x2).
Since g o f is 1:1, x1 = x2.
Hence f(x1) = f(x2), i.e. y1=y2.
So g is 1:1.

3. Let X have 2 elements and Y have n elements. Show, by induction on n, that the number of 1:1 functions from X to Y is n²-n.

[Actually it was silly to do this by induction, I realized later -- one can count all function, n², and subtract the noninjective ones, in which both elements of X go the same place. There are obviously n of those, depending on the choice of place.]

If Y is empty, there are no functions, and 0 = 0² - 0.
Otherwise, we may pick an element y in Y.
The functions f from X to Y that don't hit y (i.e. such that there doesn't exist any x s.t. f(x)=y) are exactly the same as the functions from X to Y \ {y}.
By induction, the number of those is (n-1)² - (n-1) = n² - n - 2(n-1).
So how many more 1:1 functions are there from X to Y, that do hit y?
Call the elements of X be {a,b}.
Then either f(a) = y, and f(b) is not y (since f is 1:1); there are n-1 choices for f(b).
Or f(a) is not y, in which case f(b) must be y (since f hits y); there are n-1 choices for f(a).
So there are 2(n-1) more functions,
for a total of (n² - n - 2(n-1)) + 2(n-1) = n² - n.

4. Assume that X=Z, so g:Y->X.
The function I:X->X such that I(x)=x for all x in X is called the identity function.
(Every set's got one!)
Call g a left inverse of f if g o f is the identity function on X.

a. If g is a left inverse of f, show that f is 1:1.

Let x1,x2 be in X, and assume f(x1)=f(x2). Apply g to both sides. Then x1 = I(x1) = (g o f)(x1) = (g o f)(x2) = I(x2) = x2.

b. If f is 1:1 and X is nonempty, show that f has a left inverse.

Since X is nonempty, we may pick some element x₀ in X.
Define g:Y->X as follows.
For each y in Y such that there exists an x in X with f(x)=y, let g(y)=x.
For the remaining y in Y, let g(y) = x₀.

First we have to argue that this g really is a function, i.e. that it assigns a unique value to every y. Certainly it assigns a value, since we caught any stragglers with "for the remaining y...". If in the first line, g(y) was pointed toward x1 and x2, then f(x1)=y=f(x2). But since f is 1:1, this forces x1=x2.

Second, we have to show that this g is a left inverse.
For all x in X, g(f(x)) = x by the first line of the definition of g.

[One could also define g as a set of ordered pairs; it is the union of {(y,x) : (x,y) in f} and {(y,x₀) : there doesn't exist x in X with f(x)=y}. Then one again has to use injectivity of f to show that this is indeed a function.]

c. If X is empty, show that f is 1:1, and determine when it has a left inverse.

One definition of f 1:1 started with "given two elements x1,x2 of X, unequal, ..." but there are no two such elements. So the condition is vacuously true.

For g to be a function from Y to an empty set X, Y has to itself be empty. In this case f has a left inverse: the empty function.

Friday May 2

2008-05-02T16:41:00.000-07:00

We talked about induction, and proved by induction that n² = 2n² for all naturals n. (Proof: n=0 is easy. Then for n>0, use the equation at step n to get the one at step n+1. No division by zero occurs.)

I talked about a curious induction proof in which the base case is at n=5. The cubic equation is solvable, and was solved by Tartaglia, but equations of degree 5 and higher are not.

Then we showed that gcds are unique. The case of gcd(a,b)=0 had to be made separately.

I stated the Euclidean algorithm to compute gcds, but didn't show that it terminates nor that it, in fact, computes gcds.

Wednesday April 2

2008-05-02T12:02:00.000-07:00

First we proved that there are no natural numbers between 0 and 1, hence only one integer strictly between -1 and 1.
This is handy later; it says that the only multiple of d strictly between -d and d is 0.
Then we proved the "division algorithm":
given an integer n and a natural d>0, there exist unique integers p,r with r in [0,d) such that n=pd+r.
Then we introduced the "divides" notation a|b, and proved a couple of easy things about it. More to come.

Second midterm Friday May 23

2008-05-01T23:11:00.001-07:00

The second midterm will be on Friday May 23.

HW #3 due Monday May 5 (yes, Monday)

2008-04-29T21:22:00.000-07:00

More practicing proofs by induction.

1. Let f(n) be a function from N -> N (the naturals), satisfying
f(0) = 0
for n>0, f(n) = 2 * f(n-1) + 1.
Prove that for all n in the naturals, f(n) = 2ⁿ - 1.

2. Prove that for all n at least 2 (this induction doesn't start from 0, or from 1!),
that the product of the numbers {1 - 1/i : i = 2,...,n} is 1/n.

(I guess you can start from 1 if you want, regarding the LHS as an empty product, so = 1. But the problem doesn't ask you to think about that.)

3. Let f:N->N satisfy
f(0) = 38
f(1) = 39
for all n at least 2, f(n) = 3f(n-1) - 2f(n-2).
Prove that for all n in N, f(n) = 2ⁿ + 37.

Book:
11.6, 11.10, 11.15.
Think hard about 11.7 but don't turn anything in about it.

Scope of lexical binding

2008-04-28T12:37:00.000-07:00

Aris asked a very good question: why do we write proofs as "Let x in X...[good thing happens] Since x was arbitrary, we've proven that for all x in X,..." rather than simply "For all x in X, [good thing happens]" ?

I think it has to do with lexical scoping.
When we say "for all x in X", that typically ties up the letter x to mean a certain something until the end of the sentence, or possibly the paragraph. But no further.
For example, one may say "for all i in 1,2,3,...,n" in every sentence, and have i free to mean something different each time.
But when we start out a proof with "Let x be in X" then the reader may assume that x will mean the same fixed element, for the rest of the proof.

Mind you, we're not discussing mathematics here; we're only discussing how mathematics is written and read.
And it's not to say that it isn't prone to error. All the time, in lectures, one hears the speaker (or the audience) say "where this n is not that n" or even just "where n doesn't equal n, of course"

HW #2 due Wednesday April 30 (acceptable Friday)

2008-04-26T18:11:00.000-07:00

Let f:X->Y and g:Y->Z be functions.

1. Give an example where g o f is onto, but f is not onto.

2. Assume g o f is 1:1, and f is onto. Show that g is 1:1.

3. Let X have 2 elements and Y have n elements. Show, by induction on n, that the number of 1:1 functions from X to Y is n²-n.

4. Assume that X=Z, so g:Y->X.
The function I:X->X such that I(x)=x for all x in X is called the identity function.
(Every set's got one!)
Call g a left inverse of f if g o f is the identity function on X.

a. If g is a left inverse of f, show that f is 1:1.
b. If f is 1:1 and X is nonempty, show that f has a left inverse.
c. If X is empty, show that f is 1:1, and determine when it has a left inverse.

Midterm with answers

2008-04-23T10:40:00.000-07:00

Here.

Office hours Thursday

2008-04-22T09:27:00.001-07:00

I am traveling and will be back tomorrow; the Tuesday office hour is moved to Thursday.
Answers to the first midterm will be up soon.

Answers to practice midterm

2008-04-18T22:52:00.001-07:00

Here.

Practice midterm

2008-04-16T22:58:00.000-07:00

It's here, in PDF.
The actual midterm won't be as tough!

Monday April 14

2008-04-16T12:38:00.000-07:00

More about induction proofs.
v1. Case check: either there are no counterexamples (yay), or there is a least one; ... we find a smaller one, and reach a contradiction.
v2. A rewriting of that.
v3. [the contrapositive] if P(m) is true for all m < n, then ... it's true for n; "hence we're done".

Example: every natural number is a product of prime numbers.

Weak induction only uses n-1 to prove n, rather than all m < n to prove n.

Examples: every natural number is even or odd. The sum of the first n integers is n(n+1)/2.

Friday April 11

2008-04-11T16:20:00.000-07:00

Proofs.
Proof by case check.
When the cases are "Q is true or Q is false", the proof gets abbreviated, and is called a proof by contradiction. Underneath, it's still really a case check.
Well-ordering axiom of the natural numbers.
Proving something for all natural numbers: if it's not true, then there's a least counterexample.
We saw one way of writing a "proof by induction", using a counterexample to produce a smaller counterexample.

Wednesday April 9

2008-04-10T12:26:00.001-07:00

We went back through the proof that subgraphs of bipartite graphs are bipartite.
The main point to absorb here was that
to show something exists (here, a splitting of the subgraph),
the best thing to do is EXHIBIT an example.
This isn't always how it works; there are a very few "pure existence" proofs that don't actually construct an example. But they are very rare, and your first impulse should be to find a recipe for an example.

Here's an example I didn't give in class:
Theorem. For any real number x, there exists a real number y such that x < y < x+1.
Proof. Let y = x + 1/37. Then y satisfies the desired properties. QED.

Note that lots of other recipes would have worked just as well -- we only needed one.

Then we defined circuits in graphs, and headed toward the theorem that circuits in bipartite graphs are always of even length. (Someday we'll prove a converse to this.)

Monday April 7

2008-04-07T22:01:00.000-07:00

We reiterated the definition of a graph (V,E) and the degree of a vertex.
We gave a couple of definitions of "regular graph", in which all vertices have the same degree.
I drew two examples thereof, one being the Petersen graph:

We defined bipartite graph and subgraph, and started proving that subgraphs of bipartite graphs are themselves bipartite.

HW #1 due Friday April 11

2008-04-03T14:24:00.000-07:00

[Solow] denotes the book. Since not everybody has it I'm typing in these problems.

Turn in
Ch 1, problems 4-9
4. Unpack these English sentences to determine the hypothesis and the conclusion.
a. The sum of the first n positive integers is n(n+1)/2.
b. r is irrational if r is real and satisfies r²=2.
c. If p and q are positive real numbers with SquareRoot(p*q) not = (p+q)/2, then p not = q.
d. When x is a real number, the minimum value of x(x-1) is at least -1/4.

5. "If I do not get my car fixed, I will miss my job interview," says Jack. Later, you come to know that Jack's car was repaired but that he missed his job interview. Was Jack's statement true or false? Explain.

6. Using Table 1.1 (namely, our class definition of "implies" as a mathematical term), determine the conditions on the hypothesis and the conclusion under which the following statements are true and false and give your reason.
a. If 2>7, then 1>3.
b. If 2<7, then 1<3.
c. If x=3, then 1<2.
d. If x=3, then 1>2.

7. Suppose someone says to you that the following statement is true: "If Jack is younger than his father, then Jack will not lose the contest." Did Jack win the contest?

8. If you are trying to prove that "A implies B" and you know B is false, do you want to show A is true or false? Explain.

9. By considering what happens when A is true and when A is false, it was decided that when trying to prove the statement "A implies B" is true, you can assume that A is true and your goal is to show that B is true. Use the same type of reasoning to derive another approach for proving that "A implies B" is true by considering what happens when B is true and when B is false.

Ch 7, problems 2,7,8.
2. Rewrite each of the following using nested quantifiers.
a. A set S of real numbers has the property that, no matter which element is chosen in the set, you can find another element in the set that is strictly larger.
b. A function of a single variable has the property that for some real number, the absolute
value of the function is always less than that real number
7. Prove that for every real number x>2, there is a real number y<0 such that x=2y/(1+y).
8. Prove that if S = {real numbers x>0 : x² < 2}, then for every real number epsilon > 0, there is an element x in S such that x² < 2 - epsilon.

Read Chapter 1 and the other problems within.

~~I. Let (V,E) be a graph and V' a subset of V, E' a subset of E. What condition need we add in order to say that (V',E') is also a graph?~~ We did this one in class.

(turn in this one too)
II. For p a person and t a time, let fooled(p,t) be true if p is fooled at time t.
Use quantifier notation to write out "You can fool some of the people all of the time, and all of the people some of the time, but you can't fool all the people all of the time." (Abraham Lincoln, paraphrased)

More generally, how is "but" rendered in mathematics-ese?

Wednesday April 2

2008-04-03T13:55:00.000-07:00

"or" in English means exclusive or, "or" in mathematics means inclusive.
"implies" in English suggests a logical connection, where "A => B" only means "it never occurs that A is true and B is false". So e.g. if B is always true, then "A => B" is true as a mathematical statement, even if they seem completely unrelated. Same if A is always false!
"is" in English often doesn't translate as =, but as "is an element of". So "Felix is a cat" doesn't mean any cat = Felix, but that Felix is an element of {the set of cats}.

Sets are determined by their elements. Subsets, power sets, union, intersection, cardinality.

Definition of an empty set. Theorem: there is only one empty set (meaning, any two such are equal). Proof: the only thing we know about sets is that they are equal if they have the same elements, which is true for any two empty sets. QED.

Next time: graphs.

Monday March 31

2008-04-01T14:33:00.000-07:00

I listed the main things we'll cover: proofs, by checking cases / contradiction / induction, quantifiers, set theory, baby number theory e.g. Euclid's algorithm and prime factorization.

Then we did a bunch of conversion of a quantifier statement and the corresponding English sentence, e.g. the true statement "for every person in the class, there exists a name, such that the person has that name" vs. the false statement "there exists a name, such that for every person in the class, the person has that name". According to the rolls everybody has a name, but not everybody has the same name.

The first homework will be assigned on Friday, though suggested reading in the book will come sooner.

Please print and fill out the survey on the course web page and give it to me on Wednesday.

Welcome to Math 109

2008-04-01T14:31:00.000-07:00

This is now the blog for my Math 109 class, where you'll find homework and other timely things. For more static things, see the course website.

Class Friday June 8th

2007-06-07T18:41:00.000-07:00

Be there or b².

Answers to the qual, and appointments next Friday

2007-06-01T11:16:00.000-07:00

The answers to the qual are here.

I will be back Thursday and Friday of next week (the 7th and 8th). If you want to meet with me on that Friday, write me now to set up an appointment. (Feel free to try dropping in, but I'm likely to be crazy busy.)

Canceled class

2007-05-29T11:40:00.000-07:00

Due to a family emergency, class is canceled until further notice.
Lance Small will be taking the reins when qual season winds down; this will be announced here.

Speaking of quals, the algebra qual is graded and will be available soon.

HW due Wednesday May 30

2007-05-19T10:07:00.000-07:00

For those who want practice with Hilbert series...

1. Let I in R=C[a,b,c,d] be the ideal < a,b > intersect < c,d >, which for your information happens to be generated by < ac,ad,bc,bd >. Compute the Hilbert function of R/I, and compute the Hilbert series as a rational function.

2. Let X be the space of rank 1 matrices with entries
[a b c]
[d e f].
a. What are the equations that say that X is rank at most 1?
b. Let I be the ideal they generate, and compute the Hilbert function/series for C[a,b,c,d,e,f]/I.

3. Define a quasipolynomial f:Z->Z to be a function s.t. there exists a d>0 s.t. f is a polynomial on {a in Z : a = k mod d}, for each k=1..d. For example f(n) = (-1)ⁿ is a quasipolynomial with d=2 (or any multiple).

Let R be a Noetherian graded ring, with R₀ a field F, and let M be a finitely generated graded R-module.

a. Show that the Hilbert function of M is eventually a quasipolynomial.
b. Show that the Hilbert series of M is a rational function.

Composition of separability

2007-05-10T17:45:00.000-07:00

Some people asked me whether F >= E >= K separable implies F >= K separable.
(Here >= means greater than or equal to.)
Here's my argument yes.

Lemma 1. A >= B >= C >= D, with A >= D separable, implies B >= C separable.
Proof. A >= D is a condition on individual elements of A, so we can restrict to A=B.
Given b in B, let f(x) be its minimal polynomial in D[x], separable.
This factors in C[x], one factor of which (still separable) is the new min poly of b.
QED.

Lemma 2. If A >= B is separable and purely inseparable, they are equal.
We did this in class.

Okay, now for the theorem.
Let f be the element we want to test, with m(x) in K[x] its minimal polynomial.
If m(x) isn't separable, then (by the derivative and GCD trick from the homework) all its exponents are divisible by p^b for some positive power of p; choose b largest. Then m(x) = n(x^{p^b}) for a unique n(x), necessarily separable and irreducible. In particular f^{p^b} is separable over K.
Now consider the chain F >= E[f] >= E[f^{p^b}] >= E.
The middle extension is purely inseparable. By lemma 1, it's separable. Hence by lemma 2, E[f] = E[f^{p^b}].
Now we have the chain E[f^{p^b}] = E[f] >= K[f] >= K.
Since f^{p^b} is separable over K, this big extension is separable;
hence by lemma 1, K[f] is separable over K, which was to be proven.

Midterm Friday May 11

2007-05-09T21:55:00.000-07:00

Just fields, just up through Monday. You may bring a cheat sheet.

A practice question:

Let F be a finite field with 2⁶ = 64 elements.

a. How many of them are primitive (i.e. have multiplicative order 63)?

b. Recall that Gal(F/F₂) is generated by the Frobenius.
Show that it preserves the primitive elements.

c. How many orbits does Gal(F/F₂) have on the set of primitive elements?

HW due May 4

2007-04-28T19:41:00.000-07:00

1. Let F be Galois over K, and f in F be algebraic over K. Let {f_i} be the orbit of f under the Galois group.
a. Show that the set {f_i} is finite, and
b. the polynomial \Prod (x-f_i) is in K[x], irreducible, and has f as a root.

2. Let S_n act on the field Q(a₁,...,a_n) of rational functions in n variables. Let e_i^S be the ith elementary symmetric polynomial in the {a_j, j in S}. As that Wikipedia page (v. 4/28/07) indicates, the invariant subfield is generated by the {e_i^1,2,...,n =: e_i}.

a. What is the minimal polynomial of a₁, in Q(e₁,...,e_n)?
b. Let n=4. Describe all subgroups of S₄ up to conjugacy.
For each conjugacy class of subgroup of S₄, write down generators for the fixed field.
For each such field F, write down the minimal polynomial in F[x] for each a_i.

3. Let F be a field of characteristic p.
a. If F is finite, show that the Frobenius is onto.
b. If F is algebraically closed, show that the Frobenius is onto.
c. Give an example where it's not onto.

Fri Apr 20

2007-04-20T14:06:00.000-07:00

Finite fields are Galois over F_p. The Galois group is generated by the Frobenius.

Nailed down the Galois correspondence. Lemma: If F > E > H > K, E > H is finite, and H''=H, then E''=E. Galois correspondence when applied to H=K.

An extension is Galois iff the Galois group is big enough.

Normal subgroups <-> subfields E stable under the Galois group, which in turn implies that F/E, E/K are Galois extensions, and there is a short exact sequence of Galois groups.

HW due Fri Apr 27

2007-04-20T11:41:00.000-07:00

1. Let F > K be an algebraic field extension, f in F, p(x),q(x) two nonzero polynomials in K[x] of which f is a root. Assume that p(x) has lowest degree. Show that p is irreducible and p|q.

2. Define the derivative q' of a polynomial q without using limits, so that you can apply it to polynomials with arbitrary coefficients.

a. If p,q are two polynomials such that p² | q, show that p divides gcd(q,q').

b. If q is an irreducible polynomial in K[x] where K is a field of characteristic zero, and F is a field extension of K, show that q cannot have a repeated factor when factored in F[x].

3. Let F = F_p(a), the field of rational functions. Consider the map F[x] -> F_p(b) taking x |-> b, a |-> b^p.

a. Prove that x^p-a is irreducible in F[x].
Hint. For r(b) in F_p[b], show that r(b^p) = r(b)^p, a nice extension of the Freshman's Dream. Then reconsider the map above.

b. Let F_p(b) be the extension suggested above, where b^p = a. Show that b is the only root of the irreducible polynomial x^p-a.

4. Let p(x) = the polynomial x^pⁿ - x in F_p[x].

a. Show that p(x) has no repeated roots.

b. Show that p(x) is the product of all monic irreducible polynomials in F_p[x] of degree ~~at most~~ dividing n.

c. Write out this factorization for p=2, n=4.

HW due Friday April 20

2007-04-15T08:12:00.000-07:00

1. Show that Q[cube root of two, omega] is a simple extension, where omega = exp(2 pi i/3).

2. Let F = K[u], a finite simple extension, where u satisfies an irreducible polynomial p(x) in K[x].

a. Let u' be another root in F. Show there exists an automorphism of F taking u to u'.

b. Show |Gal(K/F)| is at most ~~deg(f)~~ deg(p).

c. Determine Gal(Q[cube root of two, omega] / Q), meaning, for each group element write down what it does to those two field elements.

3. Let F > K denote a field extension, with R a ring in between the two.

a. Give an example where R is not a field.

b. If F is algebraic over K, show R is indeed a field.

4. Let R be a domain, K the fraction field of R (so, not matching the notation in #3), F an extension of K, and f in F algebraic over K.
Show there exists a nonzero r in R such that rf is integral over R.

5. What are all the rings between Z and Q?
Which ones are finitely generated as Z-algebras?
Which ones are finitely generated as Z-modules?

Fri Apr 6

2007-04-09T12:40:00.000-07:00

This was a one-shot lecture in case prospective students showed up.

Composites of left adjoints are left adjoints.
In particular, the symmetric algebra of a module is a quotient of the tensor algebra.
The universal enveloping algebra of an anticommuting algebra.
The Jacobi identity.
Lie algebras.
Statement of the Poincare-Birkhoff-Witt theorem.

HW #1 due Friday Apr 13

2007-04-07T08:31:00.000-07:00

1. In class we lamented that for G acting on a finite set X, we could hardly figure out anything about the action knowing only X^G.

Let Z^X be the free abelian group generated by X; the action of G on X extends in a unique way to an action on Z^x by group automorphisms.

What can you determine about the action of G on X, knowing (Z^X)^G?

2. Define an R-supermodule as...
oh, this sounds so exciting! ...
... a pair (M₀,M₁) of modules. And a morphism thereof is just a pair of morphisms of R-modules. Pretty pedestrian really.
There are several forgetful functors R-SuperMod -> R-Mod, but the one we want is (M₀,M₁) |-> M₀ + M₁ (direct sum).

Slightly more interesting: if R is commutative, so that the tensor product of two R-modules is naturally an R-module again, define
(M₀,M₁) @_R (N₀,N₁) = (M₀ @_R N₀ + M₁ @_R N₁, M₀ @_R N₁ + M₁ @_R N₀).

a. Make (detailed) sense of the following statement, and prove it (not much detail):
"The functors Forget o @ and @ o Forget are naturally isomorphic."

Define an R-superalgebra as an R-supermodule M plus an associative "multiplication" M @_R M -> M.

b. Given an R-module N, define a superalgebra structure on the supermodule (R,N).

Call a superalgebra (M₀,M₁) supercommutative if M₀ commutes with everything, and M₁ anticommutes with itself, i.e. ab = -ba for a,b in M₁. (Cohomology rings from topology are examples, where M₀ is the sum of the even-degree parts, M₁ the odd.)

c. Given a supermodule M, define the "free supercommutative superalgebra" on M. It should be a left adjoint to the forgetful functor from supercommutative superalgebras to supermodules.

3. Let R = Q[x] / < x² - n >, where Q is the rationals and n is an integer. Assume R is not a field. Describe R in terms of more familiar rings.

4. Let H be a subgroup of G. Show there is a unique largest normal subgroup of H and give a way to check whether h in H is an element thereof.

Final exam

2007-03-17T17:57:00.000-07:00

The final exam is take-home, open [Hungerford] and notes, and THREE HOURS. After you first look at it, you're done three hours later. If you're in the class, you can't discuss it with people who have taken or are taking it, until you yourself have finished taking it.

You can download it here but probably best not until you're ready to take it.

When you're done, turn it in to the front office before they close on Friday. (Don't tempt fate, eh?) Then check "has everyone within earshot and 200B taken the final?" before discussing it.

Obviously there are tricky ways to circumvent the spirit of this law while adhering to the letter, and I count on you to be clever enough to think of them. Don't do those either. That ought to cover it I think.

HW due Fri Mar 9 (2c corrected)

2007-03-02T15:30:00.000-08:00

1. Let R->S be a ring homomorphism such that S is a finitely generated R-module. Let M be a finitely generated S-module. (Example: the complex numbers over the reals. Non-example: R[x] as a module over R.)
Show that M is a finitely generated R-module. (Example: finite-dim complex vector spaces are finite real-dim too.)

2. Let R = C[x,y] / < xy > (not < x,y > as I miswrote at first). Let Rⁿ be the usual free module.

a) Find a non-principal ideal of R.

b) Nonetheless, show that any submodule of Rⁿ is finitely generated.

c) Let A be an n x k matrix with entries from R, where k is very big ( > 2n, maybe even infinite).
i. Show that by invertible row and column operations, we can reduce A to having at most 2n nonzero columns.
ii. Further, v1: one can in addition ask the left n columns are [a diagonal matrix involving x and no y] + [a matrix involving y and no x], and the next n columns involve y and no x.
iii. Further, v2: one can in addition to (i) ask that the second n columns are [a diagonal matrix involving y and no x].

HINT: Prove 2c(ii) or 2c(iii), which proves 2c(i) and from there 2b.

3. Say R is a subring of a domain S,
a,b in S,
p(x) = x³ + p₂x² + p₁x + p₀,
q(x) = x³ + q₂x² + q₁x + q₀,
p(a),q(b)=0.
Construct R-polynomials s,t with leading coefficient 1 such that s(a+b)=0, t(ab)=0.

N.B. I will grudgingly accept an abstract construction rather than the actual polynomials. Maybe 3 and 3 were already too big. : -8 (

4a. Let R be a ring, I an ideal, and P a prime ideal containing I.
Show that P contains the radical of I, denoted rad(I) for the rest of this question.

b. Assume R is a PID, and P = rad(I) is prime. Show that I is a power of P.

c. Assume R = C[x,y]/< xy >, and I = < x + cy > for c nonzero.

i. Show that rad(I) = < x,y >, and that this ideal is prime. Call it P.

ii. Compute the C-dimensions of R/I, R/P, R/P². Show that I is not a power of P.

5a. Let R be a PID. Show that the set of ideals with a given radical is countable.

b. Show that the ideals < x + cy > from 4c are all different, i.e. uncountably many ideals with the same radical.

6. Let R be a PID contained in S, and S finitely generated as an R-module.
Let M be a finitely generated S-module.

a. If M is a torsion S-module, does that imply that M is a torsion R-module?

b. Show that multiplication by any s in S gives a map M->M that is a R-module homomorphism.

c. Let p be a prime element of R, and let M_p denote the elements of M killed by some power of p. Show that M_p is not only an R-submodule of M, but an S-submodule. (This is most interesting when M is a torsion R-module; see if you can guess why.)

Fri Feb 23 and Mon Feb 26

2007-02-26T14:42:00.000-08:00

Friday:
Spec of a ring, as a functor CommRing^op -> Set.

Monday:
Ascending chains of ideals in a PID terminate.
We used that to finally give the first description of a finitely generated module over a PID.
CRT: Let R be a PID. The map R/< p^a m > -> R/< p^a > + R/< m >, where p is a prime not dividing m, is an isomorphism. Showing it was 1:1 used domain, but onto used PID.

HW due tomorrow; lose Q4

2007-02-25T14:22:00.000-08:00

I'm ditching question 4 entirely, as it's much too late to properly patch it up now. I do apologize.

HW due Friday Mar 2

2007-02-25T10:32:00.000-08:00

1. In class we determined the Spec of C[x], using the fact that complex polynomials of degree > 1 all factor. It had a nice description as C union a weird extra point. (Don't confuse that point with the very different point at infinity in the Riemann sphere!)
Determine the Spec of R[x] (here R is the reals), and describe the map Spec C[x]-> Spec R[x].

2. We showed that a finitely generated torsion free module over an ED is free.
Show that the ring C[z,z^-1] of Laurent polynomials, considered as a module over the subring C[z], is torsion free but not free (i.e. it doesn't have a basis).

3. Let R = F[[z]], power series in one variable, with coefficients in some field F.

a. Show that r in R is invertible iff r not in < z >.

b. What are the elements of Spec R?

c. If F = C, so that we understand Spec C[z], describe the map Spec C[[z]] -> Spec C[z] induced by the inclusion C[z] -> C[[z]].

4. Let f:R->S be a homomorphism and r in R. Show that S @_R (R/< r >) is isomorphic to S/< f(r) > as an S-module.

5. Let V be a finite-dimensional complex vector space, and T:V->V an endomorphism. Consider it as a C[z]-module in the usual way.

a. Let C[z]->C take z |-> lambda, making C a C[z]-algebra.
Show that C @_C[z] V is finite-dimensional over C, and that its dimension is that of the lambda eigenspace of T.

b. Show that C[z,z^-1] @_C[z] V is finite-dimensional over C, and that its dimension is the number of nonzero eigenvalues (with multiplicity) of T.

c. Show that C[[z]] @_C[z] V is finite-dimensional over C, and that its dimension is the lowest degree occurring in T's characteristic polynomial.

HW due Fri Mon Feb 26

2007-02-22T11:23:00.000-08:00

The "+" in what follows are direct sums.

1. Let R be a ring, and F₀ > F₁ > F₂ > ... be a succesion of abelian subgroups of the additive group R. Assume F₀ = R. Write
gr_FR = R/F₁ + F₁/F₂ + ...

Figure out an obvious condition on the {F_k} such that gr_FR is a ring in a "natural" way. Your condition should be general enough to include the case {F_k = I^k} where I is a 2-sided ideal, and it should imply that each F_k is an ideal.
(It was pointed out to me that I didn't define I^k in class. It is generated by all k-fold products of elements from I.)

HINT. The "gr" stands for "graded", where the "kth graded piece" (gr_FR)_k := F_k/F_k+1. Set up the multiplication so that (gr_FR)_k times (gr_FR)_j goes into (gr_FR)_j+k. In particular, each graded piece is a module over (gr_FR)₀ = R/I, and hence a module over R.

This condition makes F into a decreasing filtration.

2. Let R = C[x], I an ideal, and F_k = I^k. F is called the I-adic filtration.

a) If I = < x >, show that gr_FR is isomorphic to R.

b) If I = < x² >, show that gr_FR is not isomorphic to R.

3. Let M be a left R-module, and define
gr_FM = M/F₁M + F₁M/F₂M + F₂M/F₃M + ...

a) Show that gr_FM is naturally a gr_FR-module.

b) Indeed, figure out how to use "extension of scalars" to make this happen automatically. (Lots has to be invented for this -- e.g. where's the ring homomorphism?)

CORRECTION. While there is a map from the tensor product suggested by extension of scalars to gr_FM, it doesn't seem to always be 1:1. Show that it is in the case that F_j = < b^j >, i.e. the < b >-adic filtration.

4a) Now let G₀ < G₁ < ... be an increasing filtration, and define gr_GM := G₁M/G₀M + G₂M/G₁M + ...
The same condition from before makes gr_GR into a ring.

If gr_GM is finitely generated, it doesn't follow that M is finitely generated. Find a nice condition on G under which one can draw the conclusion of finite generation.

HINT. It can fail when R = C[x] and G_i = C for all i.

HINT. This should remind you of the "N and M/N f.g. => M f.g." question from last week.

4. Let I be an ideal in C[x,y]. Let G_j = {polynomials with highest x power at most j}, H_j = {polynomials with highest y power at most j}

a) Let J = gr_G gr_H I. It is a module over gr_Ggr_HC[x,y] ~ C[x,y]. Show that J is generated by monomials.

b) [Combinatorics.] Show that any ideal in C[x,y] generated by monomials is generated by finitely many such.

c) Infer that all ideals are finitely generated as C[x,y]-modules.

Mon Feb 12

2007-02-13T13:17:00.000-08:00

Def. Nilpotents, radical ideals, zero divisors, domain, principal ideal, principal ideal domain, Euclidean domain.

Prop. If R has no nilpotents, but ab=0, we can embed R in R/< a > + R/< b >.

Theorem. EDs are PIDs.
Warning: EDs are a stupid concept, not the same level of importance as PIDs.

HW due Fri Feb 16

2007-02-12T11:49:00.000-08:00

1a. Let A be an (R,S)-bimodule, and B an abelian subgroup that is both an R-submodule and a (right) S-submodule. Show that A/B is again naturally an (R,S)-bimodule.
(Don't worry about proving naturality.)

b. Let I,J be two-sided ideals of R. Show that the (R,R)-bimodule R/I @_R R/J is isomorphic to R/K for some other ideal K.

2. Let M > N be a pair of R-modules. If N and M/N are finitely generated, show M is also finitely generated.

3. Let I be a 2-sided ideal of R, and for any module M, let IM := { sum_j i_j m_j }.

a. Show that IM is an R-submodule.

b. Show that M/IM is naturally an R/I-module (not just an R-module).
(Don't worry about proving naturality.)

c. Figure out how to describe M/IM as a degenerate sort of "extension of scalars" (!).

d. If M a free module over R, show M/IM is a free module over R/I.

4. Let R be the (commuting) polynomial ring C[x,y] and I the ideal < x, y > generated by the variables. Show I is not a free module.

Wed Feb 7 and Fri Feb 9

2007-02-12T11:40:00.000-08:00

Friday:

"Bilinearity" is only a good notion for commutative rings, and is then closely related to tensor products.

How to show a tensor product is big or small.

If R,S are k-algebras, and A,B are modules over them, then A @_k B is a module over R @_k S.
In the R=S case, sometimes there are interesting "comultiplications" R -> R @_k R.

Def. Symmetric algebra, group algebra, monoid algebra.

The co-commutative comultiplication on a monoid algebra.

Modified question 4

2007-02-11T21:06:00.000-08:00

Sorry for this being so late, but only now do I see why question 4 was so nonsensical. It's been modified.

Mon Feb 5

2007-02-05T17:02:00.000-08:00

Part of the proof that tensor is adjoint to Hom.
Extension of scalars.
The tensor algebra of an abelian group -- the left adjoint of Ring -> Ab.
The tensor algebra of a (k,k)-bimodule -- the left adjoint of k-Alg -> (k,k)-BiMod.

HW due Fri Feb 9Mon Feb 12 (to avoid the complex analysis midterm)

2007-02-04T07:18:00.000-08:00

1a. Let R be a subring of S, and A_S, _SB be two modules. Define a surjection A@_RB ->> A@_SB.

1b. Can you extend this to a natural transformation between two functors between something-or-other? This question is intentionally ill-defined, and I imagine different people will experience different creative urges.

2. Let A,B be right R-modules and C,D left R-modules. Let + denote direct sum. Define isomorphisms (A + B) @_R C ~ A@_RC + B@_RC and B @_R (C + D) ~ B@_RC + B@_RD.

...a very dull question, but it leads to...

3. Let M_n(C) denote the ring of nxn complex matrices, and C^{k x n} denote the (M_k(C),M_n(C))-bimodule of kxn complex matrices. Show that matrix multiplication
C^{k x n} x C^{n x m} -> C^{k x m}
induces a map
C^{k x n} @_{M_n(C)} C^{n x m} -> C^{k x m}
and that this map is an isomorphism.

4. An isomorphism D: R -> R^op is called an anti-automorphism of R. For example, the identity function is an anti-automorphism iff R is commutative.

a. Let M_R be a right R-module. Use D to define a left module structure on it.

b. Let _RN be a left R-module. Using D, we can make N^* := Hom_R(N,R) a left R-module. Using D again, we can make (N^*)^* a left R-module. Find a condition on D that guarantees that this new left R-module structure on N^** agrees with the old one.

c. Show the converse: if this new left R-module structure on N^** agrees with the old one for all N, then D satisfies that condition.

b. Even if D is just an anti-homomorphism, not necessarily invertible, say how to use it to turn any right R-module into a left R-module.

c. Let M be a left R-module, which we turn into a right module, then into a left module again. Determine the condition on D under which this new module structure agrees with the old one (for arbitrary M).

5. Forgetting module theory for a moment, an inner product < , > on a real vector space V induces an isomorphism V -> V^*, taking v |-> (w |-> < v,w >). This looks weird to us now, in that it's an isomorphism of a left module with a right module.

a. Use question 4 to state the definition of an inner product on a real vector space, being careful about left vs. right modules. (This being an algebra class, you can skip nonalgebraic conditions like "positive definite".)

b. Use question 4 to define a Hermitian inner product on a complex vector space, being careful about left vs. right modules.

6. Let A,B be two finite abelian groups (aka (Z,Z)-bimodules!). Show that A @_Z B is again a finite abelian group, and say how to calculate it.

Fri Feb 2

2007-02-02T14:18:00.000-08:00

Representable functors.
Yoneda lemma.
Given modules _SA, _RB_S, we get a functor
Hom_S(A,Hom_R(B,*)) -> Set,
which we claim is representable by "B @_S A".
Definition of @.
Example: Reals @_Z Z ~ Reals.

Wed Jan 31

2007-02-02T14:14:00.000-08:00

Generating a module. Finite generation. Cyclic modules.
A -> Hom_R^op(Hom_R(A,R)).
Right modules, bimodules.
Hom_R(_RA_S,_RB_T) is an (S,T)-bimodule.

Mon Jan 29

2007-01-30T14:17:00.001-08:00

The category R-Mod of left R-modules and R-linear maps.
Z-Mod = abelian groups.
C-Mod = complex vector spaces.
C[x]-Mod = complex vector spaces equipped with specific endomorphisms.
Isomorphism classes in this last category correspond to Jordan canonical forms.

Submodules, quotient modules. Infinite products vs. infinite direct sums.
Left ideals.
Given m in an R-module M, we get an R-linear map R -> M, whose kernel is a left ideal.
Conversely, given a left ideal I, we get a map R -> R/I of R-modules (not rings).

I claimed that R is a (R x R^op)-module. Not so. It is a left R-module, and a left R^op-module, but we can't glue them together so easily; this will await tensor products.

Mon Jan 29

2007-01-30T14:17:00.000-08:00

HW #3 due Fri Feb 2 -- corrected

2007-01-29T10:15:00.000-08:00

1a. Let f:R->S be a ring homomorphism, and M a left S-module. Show that M has also the structure of an R-module.

b. Even better... show that there is a functor S-Mod -> R-Mod (the categories of left modules), where the above says what to do with the objects.

c. Even better... show that there is a functor Ring^op -> Cat, taking R |-> R-Mod.

2. Let M be a left R-module, and A,B two submodules. Show that the abelian subgroups A+B, A intersect B are also submodules.

3a. Let b be an element of the ring R. Show that the smallest 2-sided ideal containing b is RbR := {sum_i r_ibs_i}.

b. Let R = M_n(C), nxn complex matrices, and b a nonzero matrix. Show that RbR = R, i.e. this R is a "simple" ring.

4. Let A,B be two abelian groups. Show that Hom(A,B) is not only an abelian group, but a left ~~End(A)^op x End(B) module~~ End(B)-module, and also a left End(A)^op module.
(We will later show it to be a left End(A)^op tensor End(B) module.)

5. Recall the definitions of initial (resp. terminal) object X in a category; there exists a unique morphism out of X to (resp. into X from) any other object Y.

Find an initial and a terminal object in the category Ring = {rings with units, s.t. homomorphisms preserve the units}. (As the example Set shows, they need not be the same object.)

Office hours

2007-01-25T09:34:00.000-08:00

Wednesday after class, 2-2:45
Thursday morning 11-12
Anytime you find me (10-2 most likely) if you're lucky
7450 APM

Wed Jan 24

2007-01-25T09:29:00.000-08:00

(2-sided) ideals are exactly the kernels of ring homomorphisms.

The "multiplicative group" functor Ring -> Grp. Note that this only makes sense if ring homomorphisms are required to preserve the unit.

3 defs of G-set:
1. functor from C_G to Set
2. action map G x X -> X satisfying some properties
3. group homomorphism G -> Sym(X).

3 defs of left R-module:
1. additive functor from C_R to Ab
2. action map R x M -> M satisfying some properties
3. ring homomorphism R -> End(M).

Examples of modules. Sections of the Mobius bundle over the circle.

Mon Jan 22

2007-01-22T14:02:00.000-08:00

The category Ab of abelian groups is an "additive category".
The inclusion Ab -> Grp has a left adjoint, "abelianization", G |-> G/G'.

Categorical def: a ring is a 1-object additive category.
Unpacked, we get the usual definition of ring-with-unit.

Def: additive functor. Consequently, we get a def: ring homomorphism. (Preserving unit!)

Some examples of rings: M_n(C), Z[i], Fun(X -> Reals), Z[x-hat, d/dx].

HW due Friday Jan 26 -- corrected

2007-01-19T14:13:00.000-08:00

1. Define a category Graph whose objects are digraphs, and define a forgetful functor Cat -> Graph.

2. Show that the "free category on a digraph" (from last HW) extends to a functor Graph -> Cat.

3. Show that these two functors (in #1 and #2) are adjoint.

4. Call a category a pre-poset if any two objects A,B have at most one morphism A->B. This defines a subcategory Pre-poset of Cat. Show that the inclusion functor Pre-poset -> Cat has a ~~right~~ left adjoint Cat -> Pre-poset. (In particular, figure out how to assign a pre-poset to a category.)

[This left adjoint is almost a right adjoint... there is a natural transformation from one of the relevant set-valued hom functors to the other; it's just not an isomorphism.]

5. Define the cardinality |C| of a category C as a sum over the isomorphism classes of objects, of 1 / |Aut(X)|. (This definition rarely makes sense -- Aut(X) may be infinite, or the sum may diverge -- but it's cool when it does.)

a. Check that |FinSet| = e, where FinSet is the category of finite sets.

b. Let X be a G-set (both finite), and X/G the category defined in class, whose objects are X and Hom(x,y) = {g : gx = y}. Show that |X/G| = |X|/|G|.

(If you think this stuff is cool, you might check out this chatty paper for lots more about it!)

6. Let C be a category that has products. For every X,Y objects in C, pick a product of X and Y; call this choice P : CxC -> C. Show that P can be extended to a functor.

7. Let Mon be the category of monoids, and Grp -> Mon the inclusion functor. Find left and right adjoints of this functor (two ways of assigning a group to a monoid).

Fri Jan 19

2007-01-19T14:10:00.000-08:00

The "opposite category" is a functor Cat -> Cat.

The functors Hom(X,*) : C -> Set and Hom(*,X) : C^op -> Set.

Natural isomorphisms.

The product of two categories.

Given functors C->D or D->C, we get functors C^op x D -> Set.
If they're naturally isomorphic, call the functors adjoint.

Left adjoints of several forgetful functors. The right adjoint of forget : Top -> Set.

Wed Jan 17

2007-01-18T21:18:00.000-08:00

Recall: group = a set + three operations + some axioms. Group homomorphism: a function preserving the operations.
Recall: category = two sets (objects and morphisms) + two operations + some axioms. Define a functor as two functions preserving the operations.

Some examples:
Forgetful functors (-> Set).
The vector space with given basis (Set -> Vec).
The one-object category made from a group (Grp -> Cat, G |-> C_G).
G-sets (C_G -> Set).

Natural transformations of functors.

TA office hours and section

2007-01-17T15:26:00.000-08:00

"Office hours are 1-2pm Tuesday in AP&M 6446 this quarter. Also, graduate TAs are supposed to hold sections this quarter. I decided on 4-5 pm Wednesday as a time, and they said we could hold the section in the basement calc lab."

HW #1 due Friday Jan 19 -- major correction

2007-01-10T21:26:00.000-08:00

1. Prove the assertion from class that "disjoint union with basepoints amalgamated" really is the coproduct in the category of sets-with-basepoints.

2. A directed graph or digraph (V,E,h,t) is a pair of sets V and E (called "vertices" and "edges") plus two functions h,t: E -> V called "head" and "tail".
(In particular, these digraphs may have repeated edges, and h(e)=t(e), whatever.)

a. Given a category, come up with a definition of "the underlying directed graph".

b. Given a directed graph, come up with a (more interesting) definition of "the free category on the directed graph".

You can check that you have the right notion using the following:

c. Given a poset P, define a directed graph G such that the free category on G is the category we associated to P. Oops, this isn't quite possible for infinite P. So assume P finite.
OOPS. Not any poset will do. Assume that there is at most one chain p > q > ... > s connecting any two elements p,s.

d. Let v,w be two vertices of a directed graph G. If the corresponding objects in the free category on G are isomorphic, show v=w.

3. Define a monomorphism f as one such that whenever f o g = f o h, it follows that g = h. (Here f,g,h are various morphisms in C for which o is defined.)

a. Let C = Set. Show f is monic (i.e. a monomorphism) iff f is 1:1.

b. (Harder.) Let C = Grp. Show f is monic iff f is 1:1.

Probably some more as I think of them; Monday at the latest.

Wed Jan 10 -- NO CLASS FRIDAY OR MONDAY

2007-01-10T17:16:00.000-08:00

The opposite category to a category.
Terminal objects. Which are...
"Unique up to unique isomorphism." Some examples. Initial objects.
Given A,B in Obj(C), we defined a category C_A,B where a terminal object is a product of A and B.
Coproducts.
Coproduct in Set = disjoint union.
Coproduct in Set_* = disjoint union with basepoints amalgamated.
Coproduct in Grp = free product of groups.

No class on Friday (I am attending a funeral) or Monday (MLK birthday), so see you next Wednesday.

200B begins, and first day's topics

2007-01-09T13:04:00.000-08:00

200B will focus on [Hungerford] chapters 10 (categories), 3,4,8 (commutative rings and modules). It is no longer in the Halkin room but in 7421.

First day (1/8):

Before starting categories...
Groups of permutations are certain special collections of functions.
Abstract groups aren't -- you don't "evaluate them on elements". You can only think about the group multiplication (and identity and inverses).

Definition of a category. Examples, consisting of collections of objects and certain special collections of functions, e.g. Set, Vec, Top, Grp, Top_*.
More abstract examples: any poset (where each hom-set has at most one element), any group (a single-object category), X/G where X is a G-set.

Definition: a product of two objects in a category.
We pretty nearly proved that products are unique up to unique isomorphism, but it got really rushed, so we'll attack it anew and slightly differently next time.

Answers to the final

2006-12-08T18:20:00.000-08:00

I've posted the answers here.

This test was too long. I apologize for that.

Anyway, what's a test like this about? It's not what we're really using to measure your progress in the UCSD PhD program. That's what the qualifying exams are for. I think I can assert safely that they will have easier questions than my half of this test. So, take this as an upper bound.

Office hours finals week

2006-12-04T23:24:00.000-08:00

I'm available for office hours from 10-1 each day this week. These are not drop-in times; rather, email me the night before saying something like "I'll be by tomorrow starting a little after 11 for office hours". Emailing half an hour before also has a chance of working but is less recommended.

You can of course drop by 7450 to try your luck, but it may not be very good.

Friday Nov 17

2006-11-17T14:32:00.000-08:00

The number of p-Sylows is congruent to 1 mod p, and divides |G| / p^k.
Every p-subgroup is in a Sylow.
Sylow subgroups are all conjugate.
They're normal iff they're unique.
If |G|=2p, p an odd prime, then G is either Z_2p or D_p.

HW due Fri Nov 24Mon Nov 27

2006-11-17T14:20:00.000-08:00

1. Let G be a p-group (i.e. |G|=p^k for p some prime). Use the action of G on itself by conjugation to show that G has nontrivial center.

2. Let G > H > N be a chain of groups, where N is normal in G. If H/N is normal in G/N, show that H is normal in G.

3. Let G be a p-group. Show that G has a normal subgroup of order p. Then show that G has subgroups of every order p^j dividing |G|. (Hint: a better statement is true -- it has a chain of normal subgroups.)

4. Find a 3-Sylow subgroup of each of S₆, S₉, S₁₅, and S₂₇. (If it helps, they have nice descriptions as semidirect products.)

5. Let p divide |G|, where |G| < p². Show that G has a normal p-Sylow. (Analytic number theory question: what fraction of numbers |G| have such p? Answer: log 2, or most of them.)

6. Let p^a || |G|, q^b || |G|, where p,q are prime. Assume that the number of q-Sylows is not a multiple of p. Show that G has a subgroup of order p^a q^b.

Wednesday Nov 15

2006-11-15T14:50:00.000-08:00

Lagrange's thm. A₄ violates the converse statement.
p^k || m.
Def. Sylow subgroup, Syl_p(G).
Statement of Sylow's theorems.
Lemma. p doesn't divide (m choose p^k).
Lemma. If H,N finite subgroups of G, then |HN| = formula, and if H normalizes N, then HN is a subgroup.
Thm. Sylow subgroups exist. Pf. By acting on p^k-element subsets by left mult.
Thm. When S acts on Syl_p by conjugation, the only fixed point is itself.

HW due Fri Nov 17

2006-11-13T14:43:00.000-08:00

1. Let G act diagonally on unordered pairs of group elements, g.{a,b} = {ga,gb}.
Describe the set of orbits, and the stabilizers, and (for G finite) the formula |pairs| = sum |orbits|.

[Some people asked whether a can equal b. Answer: the math doesn't particularly care. You may as well leave that possibility out, since it's kinda dumb. If you've already written this up with a=b allowed, that's fine too.]

2. Let S_n act on itself by conjugation. Explain how to compute the size of the conjugacy class of a permutation pi. What equation do you get for S₅?
(I.e. 5! = sum |conjugacy classes|, what are they?)

[H]
1.5 #18
1.6 #1,5,11

Monday Nov 6, Wednesday Nov 8, Monday Nov 13

2006-11-13T14:24:00.000-08:00

k-transitivity and the Mathieu groups (for culture only).
Every transitive G-set is isomorphic to a coset space G/H.
Thm. Let G act on X finite. Then |X| = sum |G/Stab_i|, the stabilizers appearing.
Example: Let S_n act on the power set. Then 2ⁿ = sum (n choose k).
Cor. |G| = |X| |Stab|. Ex. |Rot(cube)| = #faces * (rotations of a face) = 6*4.

When is there a map from G/H -> G/K?
Classifying such. If H=K is finite, then they're automatically invertible.
Ex. Let Rot(cube) act on unordered pairs of vertices.
Then the orbits correspond to distance 1, distance 2, distance 3.
There is a Rot(cube)-equivariant map from {distance 1} -> {distance 3}, but none between any other pair of distinct orbits.

No class Friday (Veteran's Day, observed).

Let |G|=pⁿ act on X. Then |X| = |X^G| mod p.
Ex. G = Z_p acting on Fun(G,{1,...,n}) gives n^p = n mod p.
Center of a group.
Conjugacy classes in S_n.
In A_n they're more complicated: A₅ example.

HW due Fri Nov 10 Mon Nov 13

2006-11-03T14:49:00.000-08:00

...since Nov 10 is a holiday.

1. Fix n>0 a natural number.
Call a function f:Z->Z is of period n if f(x+n) = f(x) + n for all x.
Let Jug_n denote the set of such f that are bijections.

A. Show that Jug_n is a group under function composition, i.e. the inverse of a function of period n is again of period n.
B. Show that Jug_n has an easy group homomorphism onto S_n, and that the kernel is isomorphic to Zⁿ.
C. Show that the map Jug_n ->> S_n has a one-sided inverse S_n -> Jug_n (a group homomorphism).
D. Infer that Jug_n is a semidirect product.

2. Let S_n act diagonally on {1,...,n}⁴, i.e. on 4-tuples.
How many orbits are there, as a function of n = 0,1,2,... ?

3. Say G,H are abelian, and G |X H is a semidirect product (i.e. H is the normal one). Assume that G is also normal. Show that G |X H is abelian.

4. Let Ad g:G -> G denote the function h |-> g h g^-1.
A. Show that Ad g is an automorphism of G.
B. Show that the map Ad: G -> Aut(G) is a group homomorphism.
C. What is its kernel?
D. Show that its image is a normal subgroup of Aut(G).

[H]
1.5 #6,11,16

Fri Nov 3

2006-11-03T14:38:00.000-08:00

Transitive and simply transitive G-sets. G-equivariant maps and isomorphisms. G acting on a disjoint union of G-sets.
Theorem. Every G-set is G-equivariantly isomorphic to a disjoint union of transitive G-sets.
Free actions.
Theorem. If G acts freely on X finite, then |X| = |G| |X/G|.

Scary example: X = circle, G acts by antipode, X/G a circle again. Then the bijection used in the above theorem is not continuous. (Of course, continuity isn't very relevant when X is finite.)

Next time: we'll classify transitive G-sets and describes all morphisms between them.