Wednesday, December 06, 2006
Tuesday, December 05, 2006
Answers, and what to bring to the final
One twist:
To the final you may bring one double-sided sheet of handwritten notes, and your midterms. One question from the midterms will make a surprise appearance!
1a. Let a,b be integers such that a2 = b3.
Is b necessarily a square?
If yes, prove it, otherwise, give a counterexample (a pair {a,b}).
ANSWER. Yes, it's true. Write out the prime factorizations, and look at the power of a prime p occurring in the equation: 2ap = 3bp. Hence each bp must be even. Then the product over all p of p(bp/2) is an integer, and a square root of b.
1b. Let a,b be integers such that a10 = b15.
Is b necessarily a 10th power?
If yes, prove it, otherwise, give a counterexample (a pair {a,b}).
ANSWER. No. In fact this equation is just the 5th power of the one above! For a small solution to the equation above, take b = 22 = 4, a = 23 = 8. Then this second equation holds but b=4 is not a 10th power of an integer.
1c. Let a,b be integers such that a323 = b391.
Then a,b are both powers of some other integer. What are those powers?
ANSWER. Follow the same analysis as in 1a to get 323ap = 391bp. To simplify this equation, divide by the gcd of 323 and 391, which we can calculate with Euclid's algorithm. 391-323 = 68, 323-4*68 = 323-272 = 51, 68-51 = 17, 51-3*17 = 0. So 17 is the gcd, and dividing we get 19ap = 23bp. Hence each bp is a multiple of 19, and b is a 19th power of some guy, where a is the 23rd power of that same guy.
2. Prove by induction that sumi=1...n 1/i(i+1) = 1 - 1/(n+1).
ANSWER. The easiest base case is n=0, where this says 0=0. (If you wanted to do the base case n=1 where this says 1/1*2 = 1 - 1/2, that's not so hard either, but it is harder.)
Then for n>0, the LHS can be rewritten as (sumi=1...n-1 1/i(i+1)) + 1/n(n+1) by separating out the last term. (When n=0, there is no term at all, much less a last term.) By induction, the first part of that adds up to 1-1/n. Then we check that
1-1/n + 1/n(n+1) = 1 - 1/(n+1)
which is easy.
3. Let k,n be natural numbers, such that n! > kn. Show that for all N > n, N! > kN.
ANSWER. By induction on N. The base case is N=n, which is given to us. (So in fact we're going to show it for all N greater than or equal to n.)
Now we can assume that it's true for N, and wish to prove it for N+1. Look first at (N+1)! = (N+1) N! > (N+1) kN. We would like for that to be > kN+1, i.e. we would like N+1 > k.
We know N+1 > n. Do we know n > k? If not, then n is less than or equal to k, in which case n! is a product of n numbers less than or equal to k, and this product is therefore less than or equal to kn. But we were told that isn't true.
Having reached that contradiction, we learn n > k, so N+1 > k, which was the remaining step in showing that (N+1)! > kN+1. This completes the induction step.
4. Let R,S be two equivalence relations on the same set X.
a. Show that R intersect S is an equivalence relation (where "intersect" means as sets of ordered pairs).
ANSWER. Let x,y,z denote elements of X.
Reflexive: since R,S are reflexive, (x,x) is in R and S, hence in the
intersection.
Symmetric: if (x,y) is in R intersect S, it's in both R and S. Since R and S are symmetric, that implies (y,x) is in both R and S. Hence it's in the intersection.
Transitive: same deal as symmetric. If (x,y) and (y,z) are in R intersect S, they're in both R and S. Since R and S are transitive, (x,z) is in both R and S. Hence it's in the intersection.
b. Let RuS denote the union of R and S. Of the three conditions required of an equivalence relation, which ones does RuS automatically satisfy? For each condition {reflexive, symmetric, transitive}, either show that RuS satisfies it, or give an example of X,R,S where RuS doesn't satisfy it.
Reflexive. Yes. Since for any x we know (x,x) is in R, it's in RuS.
Symmetric. Yes. Say (x,y) is in RuS. Then it's in either R or S. If it's in R, then (y,x) is in R since R is symmetric, so (y,x) is in RuS. Same proof for "in S".
Transitive. No. Say X has three elements {x,y,z}, and R has the associated partition { {x,y}, {z} }, whereas S has the associated partition { {x}, {y,z} }. Then (x,y) is in R, and (y,z) is in S, so both elements are in RuS, but (x,z) is not in RuS.
5. "Let b,c,n be integers, such that bn > cn. Then for all N>n, bN > cN." State the negation of this statement and prove that.
ANSWER. Rewrite with quantifiers explicit:
"For all b,c,n integers, such that bn > cn, for all N>n, bN > cN."
To negate:
"There exists b,c,n integers, such that bn > cn,
and there exists N>n, where bN is less than or equal to cN."
Proof: let n=2, b=-3, c=2, N=3. Then (-3)2 > 22, but (-3)3 is less than 23.
Basically a trick question, in that it had silly negative numbers to confuse you, but at least it wasn't a "Prove or disprove" gotcha question.
To the final you may bring one double-sided sheet of handwritten notes, and your midterms. One question from the midterms will make a surprise appearance!
1a. Let a,b be integers such that a2 = b3.
Is b necessarily a square?
If yes, prove it, otherwise, give a counterexample (a pair {a,b}).
ANSWER. Yes, it's true. Write out the prime factorizations, and look at the power of a prime p occurring in the equation: 2ap = 3bp. Hence each bp must be even. Then the product over all p of p(bp/2) is an integer, and a square root of b.
1b. Let a,b be integers such that a10 = b15.
Is b necessarily a 10th power?
If yes, prove it, otherwise, give a counterexample (a pair {a,b}).
ANSWER. No. In fact this equation is just the 5th power of the one above! For a small solution to the equation above, take b = 22 = 4, a = 23 = 8. Then this second equation holds but b=4 is not a 10th power of an integer.
1c. Let a,b be integers such that a323 = b391.
Then a,b are both powers of some other integer. What are those powers?
ANSWER. Follow the same analysis as in 1a to get 323ap = 391bp. To simplify this equation, divide by the gcd of 323 and 391, which we can calculate with Euclid's algorithm. 391-323 = 68, 323-4*68 = 323-272 = 51, 68-51 = 17, 51-3*17 = 0. So 17 is the gcd, and dividing we get 19ap = 23bp. Hence each bp is a multiple of 19, and b is a 19th power of some guy, where a is the 23rd power of that same guy.
2. Prove by induction that sumi=1...n 1/i(i+1) = 1 - 1/(n+1).
ANSWER. The easiest base case is n=0, where this says 0=0. (If you wanted to do the base case n=1 where this says 1/1*2 = 1 - 1/2, that's not so hard either, but it is harder.)
Then for n>0, the LHS can be rewritten as (sumi=1...n-1 1/i(i+1)) + 1/n(n+1) by separating out the last term. (When n=0, there is no term at all, much less a last term.) By induction, the first part of that adds up to 1-1/n. Then we check that
1-1/n + 1/n(n+1) = 1 - 1/(n+1)
which is easy.
3. Let k,n be natural numbers, such that n! > kn. Show that for all N > n, N! > kN.
ANSWER. By induction on N. The base case is N=n, which is given to us. (So in fact we're going to show it for all N greater than or equal to n.)
Now we can assume that it's true for N, and wish to prove it for N+1. Look first at (N+1)! = (N+1) N! > (N+1) kN. We would like for that to be > kN+1, i.e. we would like N+1 > k.
We know N+1 > n. Do we know n > k? If not, then n is less than or equal to k, in which case n! is a product of n numbers less than or equal to k, and this product is therefore less than or equal to kn. But we were told that isn't true.
Having reached that contradiction, we learn n > k, so N+1 > k, which was the remaining step in showing that (N+1)! > kN+1. This completes the induction step.
4. Let R,S be two equivalence relations on the same set X.
a. Show that R intersect S is an equivalence relation (where "intersect" means as sets of ordered pairs).
ANSWER. Let x,y,z denote elements of X.
Reflexive: since R,S are reflexive, (x,x) is in R and S, hence in the
intersection.
Symmetric: if (x,y) is in R intersect S, it's in both R and S. Since R and S are symmetric, that implies (y,x) is in both R and S. Hence it's in the intersection.
Transitive: same deal as symmetric. If (x,y) and (y,z) are in R intersect S, they're in both R and S. Since R and S are transitive, (x,z) is in both R and S. Hence it's in the intersection.
b. Let RuS denote the union of R and S. Of the three conditions required of an equivalence relation, which ones does RuS automatically satisfy? For each condition {reflexive, symmetric, transitive}, either show that RuS satisfies it, or give an example of X,R,S where RuS doesn't satisfy it.
Reflexive. Yes. Since for any x we know (x,x) is in R, it's in RuS.
Symmetric. Yes. Say (x,y) is in RuS. Then it's in either R or S. If it's in R, then (y,x) is in R since R is symmetric, so (y,x) is in RuS. Same proof for "in S".
Transitive. No. Say X has three elements {x,y,z}, and R has the associated partition { {x,y}, {z} }, whereas S has the associated partition { {x}, {y,z} }. Then (x,y) is in R, and (y,z) is in S, so both elements are in RuS, but (x,z) is not in RuS.
5. "Let b,c,n be integers, such that bn > cn. Then for all N>n, bN > cN." State the negation of this statement and prove that.
ANSWER. Rewrite with quantifiers explicit:
"For all b,c,n integers, such that bn > cn, for all N>n, bN > cN."
To negate:
"There exists b,c,n integers, such that bn > cn,
and there exists N>n, where bN is less than or equal to cN."
Proof: let n=2, b=-3, c=2, N=3. Then (-3)2 > 22, but (-3)3 is less than 23.
Basically a trick question, in that it had silly negative numbers to confuse you, but at least it wasn't a "Prove or disprove" gotcha question.
Monday, December 04, 2006
Office hours and practice final
I will be available for office hours from 10-1 on Tuesday and Wednesday. HOWEVER these are not drop-in times -- if you want to see me, email me (ideally the night before, or at least half an hour in advance).
I will be putting up practice final questions tonight, with answers posted tomorrow night. Here are the first few:
1a. Let a,b be integers such that a2 = b3.
Is b necessarily a square?
If yes, prove it, otherwise, give a counterexample (a pair {a,b}).
1b. Let a,b be integers such that a10 = b15.
Is b necessarily a 10th power?
If yes, prove it, otherwise, give a counterexample (a pair {a,b}).
1c. Let a,b be integers such that a323 = b391.
Then a,b are both powers of some other integer. What are those powers?
2. Prove by induction that sumi=1...n 1/i(i+1) = 1 - 1/(n+1).
3. Let k,n be natural numbers, such that n! > kn. Show that for all N > n, N! > kN.
4. Let R,S be two equivalence relations on the same set X.
a. Show that R intersect S is an equivalence relation (where "intersect" means as sets of ordered pairs).
b. Let RuS denote the union of R and S. Of the three conditions required of an equivalence relation, which ones does RuS automatically satisfy? For each condition {reflexive, symmetric, transitive}, either show that RuS satisfies it, or give an example of X,R,S where RuS doesn't satisfy it.
5. "Let b,c,n be integers, such that bn > cn. Then for all N>n, bN > cN." State the negation of this statement and prove that.
I will be putting up practice final questions tonight, with answers posted tomorrow night. Here are the first few:
1a. Let a,b be integers such that a2 = b3.
Is b necessarily a square?
If yes, prove it, otherwise, give a counterexample (a pair {a,b}).
1b. Let a,b be integers such that a10 = b15.
Is b necessarily a 10th power?
If yes, prove it, otherwise, give a counterexample (a pair {a,b}).
1c. Let a,b be integers such that a323 = b391.
Then a,b are both powers of some other integer. What are those powers?
2. Prove by induction that sumi=1...n 1/i(i+1) = 1 - 1/(n+1).
3. Let k,n be natural numbers, such that n! > kn. Show that for all N > n, N! > kN.
4. Let R,S be two equivalence relations on the same set X.
a. Show that R intersect S is an equivalence relation (where "intersect" means as sets of ordered pairs).
b. Let RuS denote the union of R and S. Of the three conditions required of an equivalence relation, which ones does RuS automatically satisfy? For each condition {reflexive, symmetric, transitive}, either show that RuS satisfies it, or give an example of X,R,S where RuS doesn't satisfy it.
5. "Let b,c,n be integers, such that bn > cn. Then for all N>n, bN > cN." State the negation of this statement and prove that.
Monday, November 20, 2006
Friday Nov 17 and Mon Nov 20
Inversions of a permutation = number of pairs (i < j) such that pi(i) > pi(j).
Neighborly transpositions = (i i+1), in cycle notation.
Theorem: pi can be written as a product of invs(pi) many neighborly transpositions.
Theorem: if pi is written as a product of k neighborly transpositions, then k is greater than or equal to invs(pi), and k is congruent to invs(pi) mod 2.
Definition. An even permutation is one with invs(pi) even, similar def for odd permutations.
Theorem: invs(pi) + invs(rho) is congruent to invs(pi o rho) mod 2.
Theorem: invs(any transposition) is odd.
Theorem: if pi is written as a product of k transpositions, then k is congruent to invs(pi) mod 2.
Theorem: the Sam Loyd 14-15 puzzle is insoluble.
Neighborly transpositions = (i i+1), in cycle notation.
Theorem: pi can be written as a product of invs(pi) many neighborly transpositions.
Theorem: if pi is written as a product of k neighborly transpositions, then k is greater than or equal to invs(pi), and k is congruent to invs(pi) mod 2.
Definition. An even permutation is one with invs(pi) even, similar def for odd permutations.
Theorem: invs(pi) + invs(rho) is congruent to invs(pi o rho) mod 2.
Theorem: invs(any transposition) is odd.
Theorem: if pi is written as a product of k transpositions, then k is congruent to invs(pi) mod 2.
Theorem: the Sam Loyd 14-15 puzzle is insoluble.
Last HW, due Wednesday Nov 29
1. Let w0 denote the permutation of {1..n} with the most inversions. Show that w0 o w0 = identity.
2. For any pi, show that invs(pi) + invs(w0 o pi) = invs(w0). Also show invs(w0 o pi) = invs(pi o w0).
[More coming in a couple of days]
2. For any pi, show that invs(pi) + invs(w0 o pi) = invs(w0). Also show invs(w0 o pi) = invs(pi o w0).
Thursday, November 16, 2006
Wednesday Nov 15
Midterm review.
Chinese Remainder Theorem.
Permutations: one-line notation and cycle notation.
Chinese Remainder Theorem.
Permutations: one-line notation and cycle notation.
HW due Monday (short)
1. Let pi be a permutation of {1..n}. When written out in cycle notation (including each i s.t. pi(i)=i as a cycle of length 1), let k be the number of cycles.
Let (i j) be the permutation that switches i and j, and leaves the other elements alone. (So this permutation has n-1 cycles, according to the definition above.)
Show that the product pi * (i j) has either k-1 or k+1 cycles, and explain when it's k-1 and when it's k+1.
5.3 #34,35,38
Let (i j) be the permutation that switches i and j, and leaves the other elements alone. (So this permutation has n-1 cycles, according to the definition above.)
Show that the product pi * (i j) has either k-1 or k+1 cycles, and explain when it's k-1 and when it's k+1.
5.3 #34,35,38
Tuesday, November 14, 2006
Midterm results
The midterm, with answers, is here.
Grade histogram:
Grade histogram:
| 100-80 | A | ****** |
| 80-60 | B | **** |
| 60-40 | C | ****** |
| 40-20 | D | ** |
| 20-0 | F |
Monday, November 13, 2006
Answers to the real midterm
We'll be grading the second midterm tomorrow. In the meantime, you can find the answers here.
Answers to the actual midterm
We'll be grading the second midterm tomorrow. In the meantime, you can find the answers here.
Answers to the actual midterm
We'll be grading the second midterm tomorrow. In the meantime, you can find the answers here.
Answers to the practice midterm
1. Say that p is prime, and p | a. Show that for some integer m,
p2 | ma.
Let m=p. Then p | a
=> a = pb for some b
=> ma = mpb = p2b for some b
=> ma is a multiple of p2
=> p2 | ma.
2. Let X be a set with 5 elements, and Y a set with 0 elements.
Show that every function from X to Y is 1:1.
It is impossible to make a function from X to Y, since the elements in X have nowhere to go. So indeed, every function from X to Y is
3. Let S be a subset of X, where S has m>0 elements and X has n elements.
We already showed that the number of functions from X to S is mn.
How many f:X->S have the property that f(s)=s for all s in S? Prove your answer.
To specify a function from X to S, we need to say where each element of X goes. We already know where the m elements of S go: to themselves. It remains to specify where the other n-m elements of X go, in S. Each has m independent possibilities, giving mn-m, just as when we counted all functions X->S.
4. Let X be a set. How big can X be, if
Each one of these has an answer, like "17 elements, no more". In which case give an example with 18 elements that doesn't have the property.
Sym: 1. The relation {(a,b)} on {a,b} is not symmetric.
Trans: 1. The relation {(a,b),(b,a)} is not transitive.
Ref: 0. The relation {} on {a} is not reflexive.
5. Let X={red,green,blue}, Y={0,1,2}, and Z={even,odd}. Let p:Y->Z be the parity function, so p(0)=p(2)=even, p(1)=odd. Describe the functions f:X->Y such that the composite p o f:X->Z is not onto. Show there are nine of them. How many of those f are 1:1? Draw three of them (put X, Y in columns, and draw arrows from each x to f(x)).
For p o f to not be onto, either everything in X goes to even, or to odd.
If X all goes to odd, then f:X->Y has to take everything to 1. One function so far.
If X all goes to even, then f:X->Y is really a function to {0,2}, and there are 23 such functions. Eight more.
Forgive me for not drawing these in ASCII.
6. (The "Freshman's Dream".) Let a,b be integers. Show that
(a+b)3 is congruent to a3+b3 mod 3.
(a+b)3 = a3 + 3a2b + 3ab2 + b3.
So the difference between that and a3 + b3 is 3(a2b + ab2), a multiple of 3.
7. Is the same true with each 3 replaced by 4?
(I shouldn't have to add:) If true, prove it; if false, provide a counterexample.
No; let a,b=1. Then (a+b)4 is 0 mod 4, but a4+b4 is 2 mod 4.
(In fact it holds for all prime exponents.)
Saturday, November 11, 2006
Some practice midterm questions
If having thought about a question you decide you're really stuck, leave a comment asking for a hint. Conversely, if you have a hint to suggest, leave that comment!
1. Say that p is prime, and p | a. Show that for some integer m,
p2 | ma.
2. Let X be a set with 5 elements, and Y a set with 0 elements.
Show that every function from X to Y is 1:1.
Yes, really. This question is written correctly, and means exactly what it says.
3. Let S be a subset of X, where S has m>0 elements and X has n elements.
We already showed that the number of functions from X to S is mn.
How many f:X->S have the property that f(s)=s for all s in S? Prove your answer.
(I'll leave the actual number in the comments, but then you still should think about proving it.)
4. Let X be a set. How big can X be, if
Each one of these has an answer, like "17 elements, no more". In which case give an example with 18 elements that doesn't have the property.
5. Let X={red,green,blue}, Y={0,1,2}, and Z={even,odd}. Let p:Y->Z be the parity function, so p(0)=p(2)=even, p(1)=odd. Describe the functions f:X->Y such that the composite p o f:X->Z is not onto. Show there are nine of them. How many of those f are 1:1? Draw three of them (put X, Y in columns, and draw arrows from each x to f(x)).
6. (The "Freshman's Dream".) Let a,b be integers. Show that
(a+b)3 is congruent to a3+b3 mod 3.
7. Is the same true with each 3 replaced by 4?
(I shouldn't have to add:) If true, prove it; if false, provide a counterexample.
1. Say that p is prime, and p | a. Show that for some integer m,
p2 | ma.
2. Let X be a set with 5 elements, and Y a set with 0 elements.
Show that every function from X to Y is 1:1.
Yes, really. This question is written correctly, and means exactly what it says.
3. Let S be a subset of X, where S has m>0 elements and X has n elements.
We already showed that the number of functions from X to S is mn.
How many f:X->S have the property that f(s)=s for all s in S? Prove your answer.
(I'll leave the actual number in the comments, but then you still should think about proving it.)
4. Let X be a set. How big can X be, if
Each one of these has an answer, like "17 elements, no more". In which case give an example with 18 elements that doesn't have the property.
5. Let X={red,green,blue}, Y={0,1,2}, and Z={even,odd}. Let p:Y->Z be the parity function, so p(0)=p(2)=even, p(1)=odd. Describe the functions f:X->Y such that the composite p o f:X->Z is not onto. Show there are nine of them. How many of those f are 1:1? Draw three of them (put X, Y in columns, and draw arrows from each x to f(x)).
6. (The "Freshman's Dream".) Let a,b be integers. Show that
(a+b)3 is congruent to a3+b3 mod 3.
7. Is the same true with each 3 replaced by 4?
(I shouldn't have to add:) If true, prove it; if false, provide a counterexample.
Friday, November 10, 2006
Office hour today 3-4 / Midterm topics
Usually it's 4-5 (after class), but there being no class I'm moving
it up an hour.
This midterm will be run the same as the last one. Focus on number theory, equivalence relations, and 1:1/onto properties of functions.
it up an hour.
This midterm will be run the same as the last one. Focus on number theory, equivalence relations, and 1:1/onto properties of functions.
Wednesday, November 01, 2006
Wednesday Nov 1
Properties of functions: injective AKA 1:1, surjective AKA onto, bijective.
Functions have inverses iff they're 1:1 and onto.
If f,g are injective, so is g o f.
If g o f is injective, so is f (maybe not g).
Statement: every function X -> Y can be factored as a surjection X -> X/~, then a bijection X/~ -> S, then the inclusion of a subset S -> Y.
We'll prove it next time.
Functions have inverses iff they're 1:1 and onto.
If f,g are injective, so is g o f.
If g o f is injective, so is f (maybe not g).
Statement: every function X -> Y can be factored as a surjection X -> X/~, then a bijection X/~ -> S, then the inclusion of a subset S -> Y.
We'll prove it next time.
Monday Oct 30
Equivalence relations vs. "partitions" of a set.
From a partition, we built an equivalence relation, and vice versa.
(There's lots to check about these recipes, and it took the whole hour, without even getting to prove that each recipe was the other's inverse.)
From a partition, we built an equivalence relation, and vice versa.
(There's lots to check about these recipes, and it took the whole hour, without even getting to prove that each recipe was the other's inverse.)
Monday, October 30, 2006
Wednesday, October 25, 2006
Friday, October 20, 2006
Friday Oct 20
Finished proving unique factorization.
Noted that in other contexts, like Z[i] and Z[sqrt{-5}], the primes may be different, and unique factorization may fail.
Used unique factorization to study the following question: what fraction of integer points in the plane are visible from the origin? Answer: 6/pi2.
Notation: pa || n if p is prime and pa|n but pa+1 doesn't |n.
Noted that in other contexts, like Z[i] and Z[sqrt{-5}], the primes may be different, and unique factorization may fail.
Used unique factorization to study the following question: what fraction of integer points in the plane are visible from the origin? Answer: 6/pi2.
Notation: pa || n if p is prime and pa|n but pa+1 doesn't |n.
Wednesday Oct 18
Midterm review.
We proved existence of factorization of natural numbers into primes (by strong induction).
We started proving uniqueness.
We proved existence of factorization of natural numbers into primes (by strong induction).
We started proving uniqueness.
Tuesday, October 17, 2006
Monday, October 16, 2006
Results of midterm #1 -- LINK CORRECTED
The midterm with answers is available here in PDF. (Really this time!)
The grading is done. The number -> letter correspondence is as follows:
What do these letters mean?
If the term ended today, and all records of your homework disappeared so that only midterm #1 could form the basis of your grade, that's what I'd give you. It's only here so that your final grade won't be a big surprise.
I am not going to toss out the number and average together the letters you get, at the end of the course. So there is no point worrying about "I got a 74 instead of a 76 -- please give me two more points!" It's exactly like someone with a 76 looking for a 78.
The grading is done. The number -> letter correspondence is as follows:
| 0- 20 F | 1 of these |
| 20- 40 D | 4 of these |
| 40- 55 C | 5 of these |
| 55- 75 B | 5 of these |
| 75-100 A | 4 of these |
What do these letters mean?
If the term ended today, and all records of your homework disappeared so that only midterm #1 could form the basis of your grade, that's what I'd give you. It's only here so that your final grade won't be a big surprise.
I am not going to toss out the number and average together the letters you get, at the end of the course. So there is no point worrying about "I got a 74 instead of a 76 -- please give me two more points!" It's exactly like someone with a 76 looking for a 78.
Thursday, October 12, 2006
Topics of midterm #1
From [FP]: sections 1.2-1.6, 2.2, 3.1-3.2.
From class: definitions from class related to graphs. (They'll be written on the test, too, but better if you already know them!)
There will be problems of the form
"Here is an English statement.
Which of the following statements follow from it?
[big mess of for-alls vs. there-exists in various different orders]."
You should be able to write out a proof by weak induction -- base cases, induction step, everything in place.
From class: definitions from class related to graphs. (They'll be written on the test, too, but better if you already know them!)
There will be problems of the form
"Here is an English statement.
Which of the following statements follow from it?
[big mess of for-alls vs. there-exists in various different orders]."
You should be able to write out a proof by weak induction -- base cases, induction step, everything in place.
Wednesday, October 11, 2006
Wednesday Oct 11
We finished proving that Euclid's algorithm works. This required strong, not just weak, induction.
The main consequence: the GCD of A and B can be written as mA+nB for some integers m,n. With this we'll eventually prove that integers have unique factorizations into primes.
Next time (Friday) we'll review the course to date, in preparation for the first midterm, on Monday October 16. See the course web page for details.
The main consequence: the GCD of A and B can be written as mA+nB for some integers m,n. With this we'll eventually prove that integers have unique factorizations into primes.
Next time (Friday) we'll review the course to date, in preparation for the first midterm, on Monday October 16. See the course web page for details.
Monday, October 09, 2006
HW #2 solutions (non-book problems)
1. Show that n3-n is a multiple of 6, for any integer n.
Answer. Write n = 6m + r, where r is one of 0,1,2,3,4,5.
Then n3-n = (6m+r)3 - (6m+r) = some multiple of six plus r3 - r.
Then we check r3-r for each possible r, getting 0,0,6,24,60,120, each of which is a multiple of six.
2. Let G be a connected graph and v a vertex of degree 1. Using the
vertex-based definition we came up for of connectedness, prove that
the deletion G\v is also connected.
("Let w,x be any two vertices of G\v. We want to show that there
exists a chain in G\v...")
A. Let w,x be any two vertices of G\v. We want to show that there
exists a chain in G\v of vertices v_1..v_n such that v_1=w, v_n=x,
and {v_i,v_{i+1}} is an edge for each i=1..n-1.
Since G is assumed connected, we know there exists such a chain
of vertices in G, call it (w_1..w_m). (So w_1=w, w_m=x.)
(If for all i, w_i is not v, then this chain is also in G\v,
but we have to deal with the possibility that some w_i=v.)
Let u be the unique vertex such that {u,v} in E_G (unique by the
assumption that degree(v)=1).
For each i such that w_i=v, the only possibility for w_{i-1},w_{i+1} are
that each is equal to u. (Note that i is not 1 or n, since w,x are not v.)
Remove w_i, w_{i+1} from the chain, so that the new, shorter chain
goes ...,w_{i-1},w_{i+2},... We need to be sure that this still
has each vertex adjacent to the next one:
{w_{i-1},w_{i+2}} = {u,w_{i+2}} = {w_{i+1},w_{i+2}} in E_G. Voila.
In this way, we have constructed a chain of vertices connecting w to x,
none of which are equal to v. So this new, shorter chain is in G\v.
Since w,x were any two vertices of G\v, this shows G\v is connected.
3. Let G be a graph and v a vertex of degree 1. Assume that the
deletion G\v has a nontrivial decomposition. Construct a decomposition of G.
("Let V1, V2 be a nontrivial decomposition of G\v. We will use this to
build one of G itself...")
A. Let V1, V2 be a nontrivial decomposition of G\v. We will use this to
build one of G itself.
As in #2, let u be the unique element of V_G to which v is connected.
Note that u is not equal to v, so u is a vertex of G\v.
There are then two cases: u in V1, or u in V2, since V1 union V2 = V_(G\v).
Assume u in V1. Let V1' = V1 union {v}.
Then we claim that (V1', V2) is a decomposition of G.
There are several things to prove:
1. V1' union V2 = V_G
2. V1' intersect V2 = {}
3. For any vertex a in V1' and b in V2, {a,b} is not in E_G.
We take them in order.
1. V1' union V2 = {v} union V1 union V2 = {v} union V_{G\v} = V_G,
by the definition of V_{G\v} as V_G with only v ripped out.
Also, we know V1 union V2 = V_{G\v} by the assumption that
they form a decomposition of G\v.
2. We know V1 intersect V2 = {}, by the assumption that they form
a decomposition of G\v. So the only chance for V1' to
share an element with V2 is if v is in both. But since
V1 union V2 = V_{G\v} doesn't contain v, V2 doesn't.
So V1' intersect V2 is empty.
3. a is either in V1, or a=v. Since V1,V2 is a decomposition,
if a is in V1 then there is no b in V2 with {a,b} in E_G.
So the other case is a=v. But then the only b in V_G such that
{a,b} is in E_G is b=u. And u is in V1, by assumption.
Hence u is not in V2, since V1 intersect V2 = {}.
So there is no b in V2 such that {a,b} is in E_G.
The other case, u in V2 instead of V1, is exactly the same except
with "V1","V2" switched throughout the proof.
4. What's the relation between #2 and #3?
A. We proved (mostly) in class that a graph has a decomposition iff it
is not connected. In light of that, #2 is equivalent to the
contrapositive of #3.
G connected ===> G\v connected
has contrapositive
G\v disconnected ===> G disconnected
or equivalently
G\v has a nontrivial decomposition ===> G has a nontrivial decomposition
Answer. Write n = 6m + r, where r is one of 0,1,2,3,4,5.
Then n3-n = (6m+r)3 - (6m+r) = some multiple of six plus r3 - r.
Then we check r3-r for each possible r, getting 0,0,6,24,60,120, each of which is a multiple of six.
2. Let G be a connected graph and v a vertex of degree 1. Using the
vertex-based definition we came up for of connectedness, prove that
the deletion G\v is also connected.
("Let w,x be any two vertices of G\v. We want to show that there
exists a chain in G\v...")
A. Let w,x be any two vertices of G\v. We want to show that there
exists a chain in G\v of vertices v_1..v_n such that v_1=w, v_n=x,
and {v_i,v_{i+1}} is an edge for each i=1..n-1.
Since G is assumed connected, we know there exists such a chain
of vertices in G, call it (w_1..w_m). (So w_1=w, w_m=x.)
(If for all i, w_i is not v, then this chain is also in G\v,
but we have to deal with the possibility that some w_i=v.)
Let u be the unique vertex such that {u,v} in E_G (unique by the
assumption that degree(v)=1).
For each i such that w_i=v, the only possibility for w_{i-1},w_{i+1} are
that each is equal to u. (Note that i is not 1 or n, since w,x are not v.)
Remove w_i, w_{i+1} from the chain, so that the new, shorter chain
goes ...,w_{i-1},w_{i+2},... We need to be sure that this still
has each vertex adjacent to the next one:
{w_{i-1},w_{i+2}} = {u,w_{i+2}} = {w_{i+1},w_{i+2}} in E_G. Voila.
In this way, we have constructed a chain of vertices connecting w to x,
none of which are equal to v. So this new, shorter chain is in G\v.
Since w,x were any two vertices of G\v, this shows G\v is connected.
3. Let G be a graph and v a vertex of degree 1. Assume that the
deletion G\v has a nontrivial decomposition. Construct a decomposition of G.
("Let V1, V2 be a nontrivial decomposition of G\v. We will use this to
build one of G itself...")
A. Let V1, V2 be a nontrivial decomposition of G\v. We will use this to
build one of G itself.
As in #2, let u be the unique element of V_G to which v is connected.
Note that u is not equal to v, so u is a vertex of G\v.
There are then two cases: u in V1, or u in V2, since V1 union V2 = V_(G\v).
Assume u in V1. Let V1' = V1 union {v}.
Then we claim that (V1', V2) is a decomposition of G.
There are several things to prove:
1. V1' union V2 = V_G
2. V1' intersect V2 = {}
3. For any vertex a in V1' and b in V2, {a,b} is not in E_G.
We take them in order.
1. V1' union V2 = {v} union V1 union V2 = {v} union V_{G\v} = V_G,
by the definition of V_{G\v} as V_G with only v ripped out.
Also, we know V1 union V2 = V_{G\v} by the assumption that
they form a decomposition of G\v.
2. We know V1 intersect V2 = {}, by the assumption that they form
a decomposition of G\v. So the only chance for V1' to
share an element with V2 is if v is in both. But since
V1 union V2 = V_{G\v} doesn't contain v, V2 doesn't.
So V1' intersect V2 is empty.
3. a is either in V1, or a=v. Since V1,V2 is a decomposition,
if a is in V1 then there is no b in V2 with {a,b} in E_G.
So the other case is a=v. But then the only b in V_G such that
{a,b} is in E_G is b=u. And u is in V1, by assumption.
Hence u is not in V2, since V1 intersect V2 = {}.
So there is no b in V2 such that {a,b} is in E_G.
The other case, u in V2 instead of V1, is exactly the same except
with "V1","V2" switched throughout the proof.
4. What's the relation between #2 and #3?
A. We proved (mostly) in class that a graph has a decomposition iff it
is not connected. In light of that, #2 is equivalent to the
contrapositive of #3.
G connected ===> G\v connected
has contrapositive
G\v disconnected ===> G disconnected
or equivalently
G\v has a nontrivial decomposition ===> G has a nontrivial decomposition
Monday Oct 9
Weak induction proof of the "division algorithm".
GCDs. Euclid's algorithm for computing GCDs.
We started proving, by strong induction, that this does actually compute GCDs, but didn't finish it.
GCDs. Euclid's algorithm for computing GCDs.
We started proving, by strong induction, that this does actually compute GCDs, but didn't finish it.
Friday, October 06, 2006
Friday Oct 6
Examples of weak induction proofs.
Thm: 1 + 2 + ... + n = (n+1 choose 2).
Thm: The number of subsets of X is 2|X|, for X finite.
Thm: If G is a finite graph, the sum of the degrees is even.
Next time: Euclid's algorithm for computing GCDs, and a proof that it works, using strong induction.
Thm: 1 + 2 + ... + n = (n+1 choose 2).
Thm: The number of subsets of X is 2|X|, for X finite.
Thm: If G is a finite graph, the sum of the degrees is even.
Next time: Euclid's algorithm for computing GCDs, and a proof that it works, using strong induction.
Wedneday Oct 4
Two properties we will need of the naturals: only 0 is not a successor, and every nonempty subset has a least element (Well-Ordering). Examples of non-well-ordered sets.
Weak induction. Strong induction.
Theorem about theorems: weak induction proofs are actually proofs. Proof: uses Well-Ordering.
Sample weak induction proof: If n>4, then 2n > n2.
Weak induction. Strong induction.
Theorem about theorems: weak induction proofs are actually proofs. Proof: uses Well-Ordering.
Sample weak induction proof: If n>4, then 2n > n2.
Monday Oct 2
Basic proof technique: splitting into cases.
Sample theorem: For any integer n, n(n-1)/2 is an integer too.
Proofs by contradiction are "really" splits into the cases "what I want to be true is true vs. what I want to be true is false."
When a proof by contradiction is silly.
Why proofs by contradiction are dangerous.
Sample theorem: For any integer n, n(n-1)/2 is an integer too.
Proofs by contradiction are "really" splits into the cases "what I want to be true is true vs. what I want to be true is false."
When a proof by contradiction is silly.
Why proofs by contradiction are dangerous.
Monday, October 02, 2006
HW #2: due Oct 9
1. Let n be an integer. Prove that n3-n is a multiple of 6.
2. Let G be a connected graph and v a vertex of degree 1. Using the vertex-based definition we came up for of connectedness, prove that the deletion G\v is also connected.
("Let w,x be any two vertices of G\v. We want to show that there exists a chain in G\v...")
3. Let G be a graph and v a vertex of degree 1. Assume that the deletion G\v has a nontrivial decomposition. Construct a decomposition of G.
("Let V1, V2 be a nontrivial decomposition of G\v. We will use this to build one of G itself...")
4. What's the relation between #2 and #3?
From [FP]:
1.4 #56,58,59,67
1.5 #84,90
1.6 #93,99,100,102
2. Let G be a connected graph and v a vertex of degree 1. Using the vertex-based definition we came up for of connectedness, prove that the deletion G\v is also connected.
("Let w,x be any two vertices of G\v. We want to show that there exists a chain in G\v...")
3. Let G be a graph and v a vertex of degree 1. Assume that the deletion G\v has a nontrivial decomposition. Construct a decomposition of G.
("Let V1, V2 be a nontrivial decomposition of G\v. We will use this to build one of G itself...")
4. What's the relation between #2 and #3?
From [FP]:
1.4 #56,58,59,67
1.5 #84,90
1.6 #93,99,100,102
Friday, September 29, 2006
Friday Sep 29
Last time we defined a graph to be "connected" if there were a series of edges connecting any two vertices. But the graph with just one vertex has no edges. Surely we'd like it to be connected, though.
Fix #1: ask instead for a series of vertices.
Fix #2: ask for a series of edges connecting any two different vertices.
Union of sets, intersection, subset.
Def. A decomposition of a graph.
We started proving
Thm. A graph is connected iff it has no nontrivial decompositions.
Proof. => Assume G is connected. If it has a nontrivial decomposition... well, no it doesn't.
Next time: we'll go the other direction, and discuss proofs by contradiction; sections 1.4-1.6 of [FP].
Fix #1: ask instead for a series of vertices.
Fix #2: ask for a series of edges connecting any two different vertices.
Union of sets, intersection, subset.
Def. A decomposition of a graph.
We started proving
Thm. A graph is connected iff it has no nontrivial decompositions.
Proof. => Assume G is connected. If it has a nontrivial decomposition... well, no it doesn't.
Next time: we'll go the other direction, and discuss proofs by contradiction; sections 1.4-1.6 of [FP].
Wednesday, September 27, 2006
Wednesday Sep 27
Converse, inverse, contrapositive. CAPalert example: "If it's not suitable for children, it's not suitable for adults!"
Definition. The deletion of a vertex from a graph.
Definition. A graph is connected if...
Question. Say G is regular, and v in VG. When is the deletion again regular?
Answer (we didn't prove yet): iff v is connected to all, or to no, other vertices.
Definition. The deletion of a vertex from a graph.
Definition. A graph is connected if...
Question. Say G is regular, and v in VG. When is the deletion again regular?
Answer (we didn't prove yet): iff v is connected to all, or to no, other vertices.
Monday Sep 25
Reiteration: "A => B" meaning more in English (actual causation) than it does in mathematese.
First taste of sets: they are determined by their elements, with no concept of order or repetition. Just in or out.
So {3,7} = {7,3} or {3,7,3,3,7}, but not {7} or {3,{7}}.
Set-forming notation.
Definition. A graph G is a pair of sets VG, EG where each element of EG is a pair of (two different) elements of V.
(Frequent construction: "Definition. An X (noun) is a Y that Z.")
Definition. The degree of a vertex... a couple of versions.
Definition. A graph is regular if all vertices have the same degree... also a couple of versions.
(Frequent construction: "Definition. An X is Y (adjective) if it does Z.")
First taste of sets: they are determined by their elements, with no concept of order or repetition. Just in or out.
So {3,7} = {7,3} or {3,7,3,3,7}, but not {7} or {3,{7}}.
Set-forming notation.
Definition. A graph G is a pair of sets VG, EG where each element of EG is a pair of (two different) elements of V.
(Frequent construction: "Definition. An X (noun) is a Y that Z.")
Definition. The degree of a vertex... a couple of versions.
Definition. A graph is regular if all vertices have the same degree... also a couple of versions.
(Frequent construction: "Definition. An X is Y (adjective) if it does Z.")
Monday, September 25, 2006
HW #1 due Monday Oct 2
1. Consider the following propositions about a function f(x,y) of two real numbers:
a. For the following functions f, which of P1-P6 are true?
i. f(x,y) = 0 everywhere. ANSWER: "P1,P2,P3,P4,P5,P6 are all true."
ii. f(x,y) = x+y.
iii. f(x,y) = x3-xy2
iv. f(x,y) = y-x2.
v. f(x,y) = x+y2.
vi. f(x,y) = x2+y2-1
b. How do things change in part (a) if we allow x,y to be complex numbers?
2. Consider the following propositions about a function f(x,y,z) of three real numbers:
a. Write down a function f(x,y,z) that satisfies P1 but not P2. Explain how to find the y required in P1, and why the x in P2 doesn't exist.
b. Write down a function f(x,y,z) that satisfies P2 but not P1. Explain how to find the x and z required in P2, and in P1 give an x for which there is no good y.
Warning: the reason this question is hard is that it has a bajillion possible answers, all equally good. Answering this question is more art than science.
3. Definition. A graph G is vague-ular if for all {v,w} in EG, degree(v) = degree(w).
a. Prove that if a graph G is regular, it is vague-ular.
b. Show that the converse, "if a graph G is vague-ular, it is regular" is not true.
(What does this mean, "show this implication is not true"? It means give an explicit example of a graph that is vague-ular but not regular.)
The rest are from [FP], meaning, Fletcher and Patty. They're not as hard -- more just to help you check that you know what's going on.
1.1 #2, 3, 4, 8, 11
1.2 #21 (true, false, sometimes), 27
1.3 #52 (write these out with quantifiers)
a. For the following functions f, which of P1-P6 are true?
i. f(x,y) = 0 everywhere. ANSWER: "P1,P2,P3,P4,P5,P6 are all true."
ii. f(x,y) = x+y.
iii. f(x,y) = x3-xy2
iv. f(x,y) = y-x2.
v. f(x,y) = x+y2.
vi. f(x,y) = x2+y2-1
b. How do things change in part (a) if we allow x,y to be complex numbers?
2. Consider the following propositions about a function f(x,y,z) of three real numbers:
a. Write down a function f(x,y,z) that satisfies P1 but not P2. Explain how to find the y required in P1, and why the x in P2 doesn't exist.
b. Write down a function f(x,y,z) that satisfies P2 but not P1. Explain how to find the x and z required in P2, and in P1 give an x for which there is no good y.
Warning: the reason this question is hard is that it has a bajillion possible answers, all equally good. Answering this question is more art than science.
3. Definition. A graph G is vague-ular if for all {v,w} in EG, degree(v) = degree(w).
a. Prove that if a graph G is regular, it is vague-ular.
b. Show that the converse, "if a graph G is vague-ular, it is regular" is not true.
(What does this mean, "show this implication is not true"? It means give an explicit example of a graph that is vague-ular but not regular.)
The rest are from [FP], meaning, Fletcher and Patty. They're not as hard -- more just to help you check that you know what's going on.
1.1 #2, 3, 4, 8, 11
1.2 #21 (true, false, sometimes), 27
1.3 #52 (write these out with quantifiers)
Friday Sep 22
First class, partly about logistics, and the main goals.
And, or, implies (chapter 1.1, 1.2). The main thing to know about how mathematicians use the phrase "X implies Y" is that they don't really care about causality -- just that whenever X is true, Y will definitely also be true.
Quantifiers (chapter 1.3). The perils of reordering them, and how they interact with "not".
And, or, implies (chapter 1.1, 1.2). The main thing to know about how mathematicians use the phrase "X implies Y" is that they don't really care about causality -- just that whenever X is true, Y will definitely also be true.
Quantifiers (chapter 1.3). The perils of reordering them, and how they interact with "not".
Fall 2006: Math 109, Mathematical Reasoning
Here's the web page for Math 109, where one finds the slower-changing facts about it. On this blog I'll keep a description of day to day occurrences, including homework assignments.
While I may enable commenting on some of these posts, it's not the surest way to get a rapid response from me -- much better to email me, "allenk", at the ucsd address. (Parse that, spambots!)
While I may enable commenting on some of these posts, it's not the surest way to get a rapid response from me -- much better to email me, "allenk", at the ucsd address. (Parse that, spambots!)
Monday, June 12, 2006
Last class!
Plucker embedding, Veronese map, Segre embedding.
Line bundles and sections. Sections of O(m) on projective space. Contravariance in spaces of sections.
Associated bundle construction.
Statement of the Borel-Weil theorem.
Line bundles and sections. Sections of O(m) on projective space. Contravariance in spaces of sections.
Associated bundle construction.
Statement of the Borel-Weil theorem.
Friday, June 09, 2006
Extra class Monday 12:30 PM
We'll have an extra class Monday 12:30-2 PM, location still to be determined.
Thursday June 8
Some puzzle stuff: through four generic lines in space, two pass.
Proj of a graded algebra over C. The special case that the ring is generated in degree 1.
Lemma we didn't prove.
1) If G an algebraic group acts on R, hence on Proj R, the stabilizers have finitely many connected components.
2) If a point x is not G-fixed, then the G-orbit through x isn't closed, and the extra stuff in the closure is of lower dimension.
Borel's theorem. If B is the group of upper triangular matrices, acting on R hence on Proj R, then B has a fixed point in Proj R.
Proposition. Let V be a rep of GLn. Then each closed orbit X of GLn on the projective space PV is a GLn-equivariant image of GLn/B. If V is irreducible, then it is the linear span of the affine cone over X.
GLn/B is a flag manifold, which embeds in a product of Grassmannians. The Plucker embedding of a Grassmannian.
Proj of a graded algebra over C. The special case that the ring is generated in degree 1.
Lemma we didn't prove.
1) If G an algebraic group acts on R, hence on Proj R, the stabilizers have finitely many connected components.
2) If a point x is not G-fixed, then the G-orbit through x isn't closed, and the extra stuff in the closure is of lower dimension.
Borel's theorem. If B is the group of upper triangular matrices, acting on R hence on Proj R, then B has a fixed point in Proj R.
Proposition. Let V be a rep of GLn. Then each closed orbit X of GLn on the projective space PV is a GLn-equivariant image of GLn/B. If V is irreducible, then it is the linear span of the affine cone over X.
GLn/B is a flag manifold, which embeds in a product of Grassmannians. The Plucker embedding of a Grassmannian.
Tuesday, June 06, 2006
Tuesday 6/6/6
Grassmannians. The Stiefel manifold. Orbits of N on the Grassmannian. Schubert varieties, which give a basis for homology. An intersection calculation in the cohomology ring of a Grassmannian. Factoid: the cohomology ring of the Grassmannian, with the Schubert basis, is isomorphic to the puzzle ring with its statuatory basis.
Tuesday, May 30, 2006
Tuesday May 30
The hive -> honeycomb bijection.
The puzzle -> honeycomb injection, and its image.
clambda,munu nonzero
<=> there exist integral hives with that boundary
=====> there exist real hives with that boundary
<=> that boundary satisfies all puzzle inequalities
<=> for certain smaller integer honeycombs, the boundary satisfies certain inequalities
<=> for certain smaller (lambda',mu',nu') with clambda',mu'nu' nonzero, (lambda,mu,nu) satisfy certain inequalities.
This becomes a recurrence once one can reverse the long arrow, which is now called the saturation theorem. The recursion was conjectured by Horn, in the context of the sums of Hermitian matrices.
The puzzle -> honeycomb injection, and its image.
clambda,munu nonzero
<=> there exist integral hives with that boundary
=====> there exist real hives with that boundary
<=> that boundary satisfies all puzzle inequalities
<=> for certain smaller integer honeycombs, the boundary satisfies certain inequalities
<=> for certain smaller (lambda',mu',nu') with clambda',mu'nu' nonzero, (lambda,mu,nu) satisfy certain inequalities.
This becomes a recurrence once one can reverse the long arrow, which is now called the saturation theorem. The recursion was conjectured by Horn, in the context of the sums of Hermitian matrices.
Thursday, May 18, 2006
Exercises #7
1. Show that the number of rhombi pointing at one side of a puzzle is the number of inversions on that side (counting counterclockwise).
2. Break a puzzle into regions by joining two pieces if they are of the same shape and share an edge, so there are 0-regions, 1-regions, and rhombus regions. Show that each region is convex, and that rhombus regions are parallelograms.
3. Orient the edges in a puzzle that separate regions; clockwise around 0-regions, counterclockwise around 1-regions. (Erase the other edges.) Classify the possible local pictures this directed graph can take around an interior or exterior vertex.
4. Let alpha,beta be two strings of k 1s and n-k 0s, labeling the SW and SE edges of a puzzle triangle read left to right.
a) If there is a puzzle, filling in this triangle, show that the last i entries of alpha have as many or more 1s as the first i entries of beta (for each i=1..n), a sort of dominance condition.
b) Show the converse -- if this dominance holds, then there is a filling.
2. Break a puzzle into regions by joining two pieces if they are of the same shape and share an edge, so there are 0-regions, 1-regions, and rhombus regions. Show that each region is convex, and that rhombus regions are parallelograms.
3. Orient the edges in a puzzle that separate regions; clockwise around 0-regions, counterclockwise around 1-regions. (Erase the other edges.) Classify the possible local pictures this directed graph can take around an interior or exterior vertex.
4. Let alpha,beta be two strings of k 1s and n-k 0s, labeling the SW and SE edges of a puzzle triangle read left to right.
a) If there is a puzzle, filling in this triangle, show that the last i entries of alpha have as many or more 1s as the first i entries of beta (for each i=1..n), a sort of dominance condition.
b) Show the converse -- if this dominance holds, then there is a filling.
Thursday May 18
Every overlapping combination of rhombus inequalities with no dependence on the interior is a positive combination of nonoverlapping ones, and every nonoverlapping combination can be uniquely labeled to make a puzzle. (We didn't, and won't, prove these.)
Harder fact: the only puzzles that give important inequalities are the ones that can filled in uniquely given their boundary.
Deflation of puzzles. Consequences for the number of each kind of piece.
The puzzle ring for (n,k), and its relation to the hive ring. (We have yet to prove that the natural map is a ring homomorphism.)
Definition of honeycombs.
Harder fact: the only puzzles that give important inequalities are the ones that can filled in uniquely given their boundary.
Deflation of puzzles. Consequences for the number of each kind of piece.
The puzzle ring for (n,k), and its relation to the hive ring. (We have yet to prove that the natural map is a ring homomorphism.)
Definition of honeycombs.
Tuesday, May 16, 2006
Exercises #6
1. There is a better RSK correspondence:
{matrices of natural numbers with row sums mu1 and column sums mu2}
correspond to
{pairs (A,B) of two semistandard Young tableaux of the same shape, A content mu1 and B content mu2}
(semistandard means weakly increasing in each row, strictly in each column).
a. Show how the RSK we defined in class is a special case.
b. Show how to derive this from the hive associator, by tensoring with Alti Cn at each step (for various i) rather than just Cn as we did.
2. Find all the puzzles of size 3.
3. Assume that a puzzle has only one 1 on one side. Give a description of all such puzzles. Show that for each size n, there are {n+1 choose 2} of them.
4. Consider a positive linear combination of rhombus inequalities where no two rhombi overlap in a triangle. If the dependence on the interior all cancels, show that the coefficients on the rhombi are all equal (so may as well be scaled to 1).
correspond to
{pairs (A,B) of two semistandard Young tableaux of the same shape, A content mu1 and B content mu2}
(semistandard means weakly increasing in each row, strictly in each column).
a. Show how the RSK we defined in class is a special case.
b. Show how to derive this from the hive associator, by tensoring with Alti Cn at each step (for various i) rather than just Cn as we did.
2. Find all the puzzles of size 3.
3. Assume that a puzzle has only one 1 on one side. Give a description of all such puzzles. Show that for each size n, there are {n+1 choose 2} of them.
4. Consider a positive linear combination of rhombus inequalities where no two rhombi overlap in a triangle. If the dependence on the interior all cancels, show that the coefficients on the rhombi are all equal (so may as well be scaled to 1).
Tuesday May 16
An application of hive associativity: the RSK correspondence, which says that
words <-> pairs consisting of a GC pattern and a standard Young tableau.
Puzzles. Each puzzle gives an inequality on the possible boundary values of a hive.
words <-> pairs consisting of a GC pattern and a standard Young tableau.
Puzzles. Each puzzle gives an inequality on the possible boundary values of a hive.
Thursday, May 11, 2006
Thursday May 11
Hives define an associative ring; the octahedron recurrence provides an associator.
Henriques' theorem (statement only): the associator satisfies the pentagon identity.
The accessibility lemma from linear programming (statement only).
Consequence for hives: if we can figure out all the ways to add up rhombus functionals such that the dependence on the interior vertices cancels, we'll learn the possible boundaries of real hives.
Henriques' theorem (statement only): the associator satisfies the pentagon identity.
The accessibility lemma from linear programming (statement only).
Consequence for hives: if we can figure out all the ways to add up rhombus functionals such that the dependence on the interior vertices cancels, we'll learn the possible boundaries of real hives.
Tuesday, May 09, 2006
Tuesday May 9
For Sasha Postnikov's talk:
Schur polynomials. Schur functions. Schur positivity.
Example of a tensor product calculation using hives.
Definition of the hive not-necessarily-associative ring.
Proposition: as a ring, Rep(GL(n)) = Z[the fundamental reps, and det-1].
Schur polynomials. Schur functions. Schur positivity.
Example of a tensor product calculation using hives.
Definition of the hive not-necessarily-associative ring.
Proposition: as a ring, Rep(GL(n)) = Z[the fundamental reps, and det-1].
Thursday, May 04, 2006
Exercises #5
1. Use the Steinberg rule to prove the Pieri rule.
2. Show that the hive theorem is true for the following cases:3. A hive is defined by its convexity. Hence, if we add a linear function to a hive we get another one. What is the corresponding statement about tensor products?
4. Fix lambda,mu,nu. Show that the space of real hives with this boundary is bounded (hence compact).
5*. Fix lambda,mu,kappa. What does the Steinberg rule say about the limit of
cN lambda,muN lambda + kappa as N -> infinity? (We dealt with the case that lambda is regular dominant, i.e. has no repeats.)
2. Show that the hive theorem is true for the following cases:3. A hive is defined by its convexity. Hence, if we add a linear function to a hive we get another one. What is the corresponding statement about tensor products?
4. Fix lambda,mu,nu. Show that the space of real hives with this boundary is bounded (hence compact).
5*. Fix lambda,mu,kappa. What does the Steinberg rule say about the limit of
cN lambda,muN lambda + kappa as N -> infinity? (We dealt with the case that lambda is regular dominant, i.e. has no repeats.)
Thursday May 4
The Steinberg tensor product formula. The flopping-and-subtraction interpretation. Statement of the Pieri rule. Certain limits of tensor product multiplicities are weight multiplicities. Decomposing a double tensor product vs. computing the invariant space in a triple tensor product.
Definition of hives. Statement of the theorem: hives compute tensor products.
Definition of hives. Statement of the theorem: hives compute tensor products.
Thursday, April 27, 2006
Thursday April 27 - no class next Tuesday
Side note: to compute the character of a GL(n) rep on an arbitrary element of GL(n), take its eigenvalues and feed that diagonal matrix into the WCF.
Given the multiplicity diagram of a G-rep V, apply difference operators in the direction of the negative roots, and the result (in the dominant Weyl chamber) tells you the multiplicities of the irreps in V.
The branching rule from GL(n) to GL(n-1).
The weight of a Gel'fand-Cetlin pattern is the list of differences in the row sums.
Theorem: there is a basis of Vlambda indexed by Gel'fand-Cetlin patterns, where each basis vector is a T-weight vector whose weight is that of the GC pattern.
I am away next Tuesday.
Given the multiplicity diagram of a G-rep V, apply difference operators in the direction of the negative roots, and the result (in the dominant Weyl chamber) tells you the multiplicities of the irreps in V.
The branching rule from GL(n) to GL(n-1).
The weight of a Gel'fand-Cetlin pattern is the list of differences in the row sums.
Theorem: there is a basis of Vlambda indexed by Gel'fand-Cetlin patterns, where each basis vector is a T-weight vector whose weight is that of the GC pattern.
I am away next Tuesday.
Tuesday, April 25, 2006
Tuesday April 25
Statement of the Weyl character formula (WCF) with a single denominator, Den.
The Kostant partition function.
The Kostant multiplicity formula, as the Fourier transform of WCF.
Pictures of the weight multiplicity diagrams as given by the Kostant multiplicity formula, for the GL(3) case.
Proof that the WCF is actually a Laurent polynomial with integer coefficients (given by the Kostant multiplicity formula).
Weyl's proof that the WCF is the character of an irrep, indeed of Vlambda.
Gel'fand-Cetlin patterns, the integer points in the (compact, convex) Gel'fand-Cetlin polytope.
Example: Gel'fand-Cetlin polytopes for GL(3).
The Kostant partition function.
The Kostant multiplicity formula, as the Fourier transform of WCF.
Pictures of the weight multiplicity diagrams as given by the Kostant multiplicity formula, for the GL(3) case.
Proof that the WCF is actually a Laurent polynomial with integer coefficients (given by the Kostant multiplicity formula).
Weyl's proof that the WCF is the character of an irrep, indeed of Vlambda.
Gel'fand-Cetlin patterns, the integer points in the (compact, convex) Gel'fand-Cetlin polytope.
Example: Gel'fand-Cetlin polytopes for GL(3).
Friday, April 21, 2006
No office hour next Tuesday
There's a special combinatorics seminar next Tuesday at 2:30, so no office hour after class that day.
Thursday, April 20, 2006
Thursday April 20
Lemma. Let D be an Sn-invarant weight multiplicity diagram with some Dmu > 0. Then D defines a class function ChiD:U(n) -> C. If the integral over U(n) of |ChiD|2 = 1, then D is the weight diagram of an irrep.
Weyl integration formula, in terms of volumes of conjugacy classes.
Volumes of conjugacy classes of U(n). (statement, no proof; look in the notes on the class web page for full details)
The Weyl denominator Den, as a sort of square root of the volume of the conjugacy class.
Statement of the Weyl character formula (WCF), manifestly Sn-invariant version.
Theorem. GL(2) acting on Symk C2 is an irrep.
The WCF for GL(2).
The rho-shifting in Den * WCF.
Weyl integration formula, in terms of volumes of conjugacy classes.
Volumes of conjugacy classes of U(n). (statement, no proof; look in the notes on the class web page for full details)
The Weyl denominator Den, as a sort of square root of the volume of the conjugacy class.
Statement of the Weyl character formula (WCF), manifestly Sn-invariant version.
Theorem. GL(2) acting on Symk C2 is an irrep.
The WCF for GL(2).
The rho-shifting in Den * WCF.
Wednesday, April 19, 2006
Exercises #4
1. Figure out how to compute the Sym2 and Alt2 of a weight multiplicity diagram. Do so for the diagram for Sym3 C3 = V(3,0,0). In particular, show that Sym2 Sym3 C3 contains Sym6 C3 plus one other irrep, and Alt2 Sym3 C3 contains Sym3 Alt2 C3 plus one other irrep. Write down all the high weights in this example.
2. Give an example of a group homomorphism in which the center doesn't go to the center.
3. Using our construction of the irreps of GL(n), show that in an irrep GL(n) -> GL(m) the center does go to the center. More concretely, how does the center of GL(n) act on Vlambda?
4. Using Schur's lemma, show that in any irrep G -> GL(m) the center goes to the center.
2. Give an example of a group homomorphism in which the center doesn't go to the center.
3. Using our construction of the irreps of GL(n), show that in an irrep GL(n) -> GL(m) the center does go to the center. More concretely, how does the center of GL(n) act on Vlambda?
4. Using Schur's lemma, show that in any irrep G -> GL(m) the center goes to the center.
Tuesday, April 18, 2006
Tuesday April 18
Define Vlambda as the irrep of high weight lambda we already constructed.
Lemma. There are finitely many dominant weights dominated by a given weight.
Corollary. Every Sn-invariant multiplicity diagram is a Z-linear combination of characters of Vlambdas.
Theorem. The Vlambdas are all the irreps of U(n).
Lemma. If a polynomial on Mn vanishes on U(n), it vanishes everywhere.
Def. Rational rep of GL(n).
Thm. Every rep of U(n) extends uniquely to a rational rep of GL(n).
Then we described (without proof) the multiplicity diagrams of irreps of U(3), and computed the decomposition of the tensor square of V(2,1,0).
Lemma. There are finitely many dominant weights dominated by a given weight.
Corollary. Every Sn-invariant multiplicity diagram is a Z-linear combination of characters of Vlambdas.
Theorem. The Vlambdas are all the irreps of U(n).
Lemma. If a polynomial on Mn vanishes on U(n), it vanishes everywhere.
Def. Rational rep of GL(n).
Thm. Every rep of U(n) extends uniquely to a rational rep of GL(n).
Then we described (without proof) the multiplicity diagrams of irreps of U(3), and computed the decomposition of the tensor square of V(2,1,0).
Monday, April 17, 2006
Exercises #3
1. Show that dominance order is indeed a partial order.
2. Let lambda be dominant, and mu a convex combination of the permutations of lambda.
(This means: let xpi be a nonnegative real number for each permutation pi in Sn, with \sum_pi xpi = 1. Let mu = \sum_pi xpi pi.lambda . Then mu is a "convex combination".)
Show that lambda is more than mu in dominance order.
3. Call a weight multiplicity diagram D "saturated" if the conditions
a) mu is integral
b) mu is a convex combination of weights in D
together imply that mu is itself a weight of D.
Show that Symn C2 is the smallest S2-symmetric saturated multiplicity diagram with high weight (n,0), for some appropriate definition of "smallest".
4. Show that the reducible representations we made by tensoring fundamental representations together are saturated.
2. Let lambda be dominant, and mu a convex combination of the permutations of lambda.
(This means: let xpi be a nonnegative real number for each permutation pi in Sn, with \sum_pi xpi = 1. Let mu = \sum_pi xpi pi.lambda . Then mu is a "convex combination".)
Show that lambda is more than mu in dominance order.
3. Call a weight multiplicity diagram D "saturated" if the conditions
a) mu is integral
b) mu is a convex combination of weights in D
together imply that mu is itself a weight of D.
Show that Symn C2 is the smallest S2-symmetric saturated multiplicity diagram with high weight (n,0), for some appropriate definition of "smallest".
4. Show that the reducible representations we made by tensoring fundamental representations together are saturated.
Thursday April 13
Gah! I'm already slipping on keeping this blog up-to-date.
Lemma (b). The "fundamental representations" Altk Cn have weights all of multiplicity 1. The high weight is (1,...,1,0,...,0) with k 1s and n-k 0s. The other weights are permutations thereof, and all other weights are less than the high weight in dominance order.
Lemma (c). Call a rep "good" if the high weight is multiplicity one, and all other weights are smaller in dominance order. (So the high weight is unique.) Then the tensor product of two such reps is again "good", and the new high weight is the sum of the two individual high weights.
Theorem 1. Every irrep has a dominant high weight.
Theorem 2. For every dominant weight, there is an irrep with that high weight, and it's "good".
Lemma (b). The "fundamental representations" Altk Cn have weights all of multiplicity 1. The high weight is (1,...,1,0,...,0) with k 1s and n-k 0s. The other weights are permutations thereof, and all other weights are less than the high weight in dominance order.
Lemma (c). Call a rep "good" if the high weight is multiplicity one, and all other weights are smaller in dominance order. (So the high weight is unique.) Then the tensor product of two such reps is again "good", and the new high weight is the sum of the two individual high weights.
Theorem 1. Every irrep has a dominant high weight.
Theorem 2. For every dominant weight, there is an irrep with that high weight, and it's "good".
Tuesday, April 11, 2006
Tuesday April 11
We won't prove that compact Lie groups have finite, positive, left-invariant measures -- leave that for a differential topology class. With that, our character theorems apply to any continuous representations.
Weight lattices of tori. Weight multiplicity diagrams. Ex: Symn C2.
Theorem. Two reps of U(n) are isomorphic iff when restricted to T = diagonals, they're isomorphic. (This is why we did character theory.) So we can study reps by their multiplicity diagrams.
Ex: Symn C2 @ Symm C2 ~ \sum_{k satisfying triangle inequalities, same parity as m+n} Symk C2 @ det@(m+n-k).
Highest weight of a rep. Dominant weight. Dominance order.
Stated the classification of irreps of U(n) in terms of their highest weights; will prove it next time.
Lemma (a): if V is a U(n)-rep, its multiplicity diagram is Sn-invariant.
Weight lattices of tori. Weight multiplicity diagrams. Ex: Symn C2.
Theorem. Two reps of U(n) are isomorphic iff when restricted to T = diagonals, they're isomorphic. (This is why we did character theory.) So we can study reps by their multiplicity diagrams.
Ex: Symn C2 @ Symm C2 ~ \sum_{k satisfying triangle inequalities, same parity as m+n} Symk C2 @ det@(m+n-k).
Highest weight of a rep. Dominant weight. Dominance order.
Stated the classification of irreps of U(n) in terms of their highest weights; will prove it next time.
Lemma (a): if V is a U(n)-rep, its multiplicity diagram is Sn-invariant.
Thursday, April 06, 2006
Exercises #2 (corrected)
I'll write tensor product as @.
1. If V,W are two reps of G, show that ChiV @ W = ChiV ChiW.
2. If V,W are two reps of G, and |ChiV(g)| < dim V except for g=1, show that W is isomorphic to a subrepresentation of V@V@....@V for some number of factors.
3. Show that the condition in #2 holds for G simple, V notzeroa trivial representation.
4. If V is a rep, compute the character of G on the symmetric tensors Sym2V and the alternating tensors Alt2V, in terms of the character of V. For each irrep W of S4, confirm that the characters of Sym2W and Alt2W are nonnegative integer combinations of the irreducible characters.
1. If V,W are two reps of G, show that ChiV @ W = ChiV ChiW.
2. If V,W are two reps of G, and |ChiV(g)| < dim V except for g=1, show that W is isomorphic to a subrepresentation of V@V@....@V for some number of factors.
3. Show that the condition in #2 holds for G simple, V not
4. If V is a rep, compute the character of G on the symmetric tensors Sym2V and the alternating tensors Alt2V, in terms of the character of V. For each irrep W of S4, confirm that the characters of Sym2W and Alt2W are nonnegative integer combinations of the irreducible characters.
Thursday April 6
We defined the averaging operator piV on a representation, and proved it to be a projection onto V's invariant subspace. Schur's lemma. Orthonormality of irreducible characters. Class functions. Reps are isomorphic iff they have the same character. Some character table stuff, with S3, S4 as examples.
We didn't prove that irreducible characters give an orthonormal basis of class functions; you can find that in the notes on the course web page.
We didn't prove that irreducible characters give an orthonormal basis of class functions; you can find that in the notes on the course web page.
Wednesday, April 05, 2006
Main results of the survey
Surprisingly, noone circled "Combinatorics is a scourge" without also circling "is fun, interesting, and instructive". I suppose such people were scared off by the course description, as is probably best.
Almost everybody circled "Pretty solid" or "Please, don't bore me" for tensor products. As such, I'm not going to do them in class. You can find them in any book entitled "Algebra", e.g. Hungerford, Artin, Lang.
People liked having office hours directly after class.
Almost everybody circled "Pretty solid" or "Please, don't bore me" for tensor products. As such, I'm not going to do them in class. You can find them in any book entitled "Algebra", e.g. Hungerford, Artin, Lang.
People liked having office hours directly after class.
Exercises #1 (corrected)
I'm putting these here so you can check that you're keeping up. If you find something weird, or want a (nother) hint, post a comment. (If you've got a hint, you can post that too.) Or you can just come and ask me about them after class.
1. Let V be a finite-dimensional irrep of an abelian group A (possibly infinite, even infinitely generated!). Show that V is 1-dimensional.
Hint: either every group element acts a multiple of the identity, or some element doesn't.
2. Let G be a finite abelian group. Show that the number of distinct irreps of G is |G|. (Hint: start with the cyclic case.)
3. Let G be a group, and Rep(G) resp. Irr(G) the set of {reps resp. irreps of G up to isomorphism}. Let Pic(G) be the set of {1-d reps of G up to isomorphism}. Show that Pic(G) is a group under tensor product (which includes checking some well-definedness), and that Pic(G) acts on Rep(G) by tensor product, preserving the subset Irr(G).
4. Calculate Pic(S3), and find an element of Rep(S3) that is fixed under the action from #3.
5. Generalizing #2 & #3, show thatIrr(G)Pic(G) is isomorphic to G/[G,G]. Warning: there is no natural isomorphism!
1. Let V be a finite-dimensional irrep of an abelian group A (possibly infinite, even infinitely generated!). Show that V is 1-dimensional.
Hint: either every group element acts a multiple of the identity, or some element doesn't.
2. Let G be a finite abelian group. Show that the number of distinct irreps of G is |G|. (Hint: start with the cyclic case.)
3. Let G be a group, and Rep(G) resp. Irr(G) the set of {reps resp. irreps of G up to isomorphism}. Let Pic(G) be the set of {1-d reps of G up to isomorphism}. Show that Pic(G) is a group under tensor product (which includes checking some well-definedness), and that Pic(G) acts on Rep(G) by tensor product, preserving the subset Irr(G).
4. Calculate Pic(S3), and find an element of Rep(S3) that is fixed under the action from #3.
5. Generalizing #2 & #3, show that
Tuesday April 4
I outlined the main topics I hope to cover (as on the course web page), and for each one a key result that I hope to get to. Those results were
1. irreps of compact groups are determined by their characters
2. classification and construction of irreps of U(n) & GLn(C)
3. Weyl character formula and Kostant multiplicity formula for GLn, Gel'fand-Cetlin patterns, Young tableaux
4. hives compute tensor product multiplicities
5. the Borel-Weil theorem for GL(n)
6. the link between tensor products and sums of Hermitian matrices.
Then we discussed finite-dimensional complex representations. Isomorphisms, intertwiners, subreps. Decomposable vs. reducible. Unitary reps are direct sums of irreps. Reps of finite groups (or groups with left-invariant measures) are unitarizable.
Next time: characters and their orthonormality. Representation rings.
1. irreps of compact groups are determined by their characters
2. classification and construction of irreps of U(n) & GLn(C)
3. Weyl character formula and Kostant multiplicity formula for GLn, Gel'fand-Cetlin patterns, Young tableaux
4. hives compute tensor product multiplicities
5. the Borel-Weil theorem for GL(n)
6. the link between tensor products and sums of Hermitian matrices.
Then we discussed finite-dimensional complex representations. Isomorphisms, intertwiners, subreps. Decomposable vs. reducible. Unitary reps are direct sums of irreps. Reps of finite groups (or groups with left-invariant measures) are unitarizable.
Next time: characters and their orthonormality. Representation rings.
Spring quarter 2006: Representations of GL(n)
This quarter I'm teaching a topics-in-algebra graduate class, Representations of GL(n). The course web site is here.
Subscribe to:
Posts (Atom)