CRYPTOGRAPHY MATH 0209A
Popular in Course
verified elite notetaker
Popular in Mathematics (M)
verified elite notetaker
This 251 page Class Notes was uploaded by Kaylin Wehner on Friday September 4, 2015. The Class Notes belongs to MATH 0209A at University of California - Los Angeles taught by Staff in Fall. Since its upload, it has received 165 views. For similar materials see /class/177832/math-0209a-university-of-california-los-angeles in Mathematics (M) at University of California - Los Angeles.
Reviews for CRYPTOGRAPHY
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/04/15
Structure and pseudoI39andomness in combinatorics FOCS 2007 tutorial October 20 2007 Terence Tao UCLA Large data In combinatorics one often deals With high complexity objects such as 0 Functions f F3 gt R on a Hamming cube 0 Sets A C F3 in that Hamming cube F3 or 0 Graphs G V E on V N vertices One should think of 2quot and N as being very large thus these objects have a large amount of informational entropy In this talk we will be primarily concerned with dense objects eg 0 Functions f F3 gt R with ExElFSfx gin 2336193 large 0 Sets A C F3 with A2quot large 0 Graphs G V E with large In particular we shall regard sparse objects or sparse perturbations of dense objects as negligible All of the above objects can be modeled as elements of a real finite dimensional Hilbert space H o The functions f F3 gt R form a Hilbert space H with inner product f 9 ExEFQ o A set A C F3 can be identi ed With its indicator function 1A F3 gt 0 l which lies in H o A graph G V E can be identified With a symmetric function 1E V x V gt 0 l in the Hilbert space of functions f V X V gt R With norm ltfa ggtH EvwEVfvv wgva The dimension of these Hilbert spaces is nite but extremely large Thus these objects have many degrees of freedom In combinatorics one often has to deal With arbitrary objects in such a class objects With no obvious usable structure Structure and pseudorandomness I While the space H of arbitrary objects under consideration has a huge number of degrees of freedom the space of interesting or structured objects typically has a much smaller number of degrees of freedom What structured means varies from context to context Examples of structure 0 Functions f F3 gt R which exhibit linear Fourier behaviour 0 Functions f F3 gt R Which exhibit low degree polynomial Reed Muller behaviour 0 Sets A C F3 Which only depend on a few of the coordinates of F3 dictators juntas 0 Graphs G V E Which are determined by a low complexity vertex partition eg complete bipartite graphs One might also consider computational complexity notions of structure Sometimes it is important to distinguish between several quality levels of structure a A lOO structured object might be one in which some statistic measuring structure is exactly equal to its theoretical maximum 0 A 99 structured object might be one in which some statistic measuring structure is very close to its theoretical maximum 0 A l structured object might be one in which some statistic measuring structure is within a multiplicative constant of its theoretical maximum Example linearity o A function f F3 gt 1 1 is 100 linear if we have fa y fafy for all 51231 6 F3 0 A function f F3 gt 1 1 is 99 linear if we have fa y fafy for at least 1 e of all 93 y 6 F3 0 A function f F3 gt 1 1 is 1 linear if we have fa y fafy for at least 3 e of all 51331 6 F3 A 99 linear function is always close to a 100 linear one Blurn Luby Rubinfeld a 1 linear function always correlates with a 100 linear one Plancherel s theorem 9 Given a concept of structure one can often de ne a dual notion of pseudorandom objects objects which are almost orthogonal or have low correlation With structured objects One can often show by standard probabilistic counting or entropy arguments that random objects tend to be almost orthogonal to all structured objects thus justifying the terminology pseudorandom 10 Examples of pseudorandornness as duals of structure 0 Functions f F3 gt R which are Fourier pseudorandorn ie have low Fourier coef cients dual of Fourier structure 0 Functions f F3 gt R which are polynornially pseudorandorn ie have low correlations with low degree polynomials dual of Reed Muller structure 0 Sets A C F3 in which each coordinate has small low height Fourier coef cients dual of dictators and juntas 0 Graphs G V E which are e regular dual of 11 complete bipartite graphs 12 In the previous examples we began by de ning structure and then created a dual notion of pseudorandomness Thus pseudorandomness is de ned extrinsically by measuring its correlation with structured objects In many cases we have an opposite situation we begin with an intrinsically defined notion of pseudorandomness and wish to discover its dual notion of structure the obstructions to that conception of pseudorandomness Computing such duals explicitly can sometimes be dif cult but is also very worthwhile it provides a way to test whether a given object is structured or pseudorandom or a combination of both 13 Examples of intrinsic pseudorandornness 0 Functions f F3 gt R Whose pair correlations ExEF3fafa h are small for most h 6 F3 0 Functions f F3 gt R Whose k point correlations ExEFQ x M fa bk are small for most h1hk EFS 0 Functions f F3 gt R Whose Gowers norms d HfHUdurg 3 EL Fg JE QEZUEFS Hweng 1397 LW12 are small 0 Graphs With a near minimal for a given edge density number of 4 cycles 14 Examples of structure as duals of pseudorandomness o A bounded function f F3 gt R has many large pair correlations if and only if has a large Fourier coef cient Plancherel s theorem 0 A bounded function f F3 gt R has large Gowers norm fUdaF3gt if and only if it has large correlation With a Reed Muller codeword of degree at most d l Gowers inverse conjecture only completely proven for d g 3 o A graph has a large number of 4 cycles if and only if it is not e regular ie it correlates With a complete bipartite graph Chung Graham Wilson 15 General principles I 0 Negligibility pseudorandom objects tend to have negligible impact on statistics averages or correlations l Dichotomy Objects which are not pseudorandom tend to correlate With a structured object and Vice versa 16 2 Structure theorem Arbitrary objects can be decomposed into pseudorandom and structured components possibly up to a small error 3 Rigidity Objects which are almost statistically or locally structured tend to be close to objects Which actually are structured 4 Classi cation Structured objects can often be classi ed algebraically by using various bases These principles give a strategy to understand arbitrary objects by splitting them into their pseudorandom and structured components 17 Structure theorems in Hilbert spaces Let us now focus on more rigorous formulations of the structure theorem principle Speci cally given a bounded vector f E H we would like to decompose f fstr fpsd ferr Where f5 is Strucmred fpsd is pseudorandom and few is a small error One can view fstr as an effective version of f since fpsd and few are often negligible Sometimes we also want to enforce some orthogonality between fstra fpsda and ferr 18 Example orthogonal projection Theorem 1 Let V be a subspace of H con sisting of the structured vectors Then eV ery f E H can be uniquely decomposed as f fstr fpsd fem Where 0 fstr lies in V o fpsd is orthogonal to V and ferr 19 We recall that there are two standard proofs of this theorem the rst using the Gram Schmidt orthogonalisation process and the other by minimising M f fstr 1 over all fstr E V The latter proof is more relevant here it relies on the dichotomy that if f fstr is not orthogonal to V then one can adjust fstr in V in order to decrease f ung One can View this variational approach as a prototype of an energy decrement argument approach to structure theorems 20 Example thresholding Theorem 2 Let 211 vn be an orthonor mal basis of H representing the fundamental structured vectors Let 0 lt e g 1 Then every f E H with fH g 1 can be uniquely decomposed as f fstr fpsd fem Where 39 fstr Zia civi is such that I g 152 and e lt g l o fpsd 21 civi is such that ltfpsd g e for all 239 and ferr Also fstr and fpsd are orthogonal 21 This theorem can be proven quickly from the Fourier inversion formula f 1221022 and the PlanCherel identity ltf v gt2 But it is instructive to see a proof that relies less on these identities and instead runs Via the following algorithm a Step 0 Initialise I Z fstr fem 0 and fpsd f a Step 1 If ltfpsd g e for all 2 then STOP 0 Step 2 Otherwise locate an 2 suCh that ltfpsol7 gt e and transfer 2 to I and fwd Uigt UZgt to fstr Now return to Step 1 22 Note that at each stage of this algorithm the energy fstr 1 of fstr increases by at least 52 by Pythagoras theorem or equivalently the energy of fpsd 1 decreases by at least 52 Also by Pythagoras theorem we hve 0 g fstr 1 g 31 So the algorithm must terminate after at most le2 steps One can View this algorithmic approach as a prototype of the energy increment argument approach to structure theorems 23 Now we consider a common situation in which we have a nite set S C H of fundamental structured vectors which have magnitude at most 1 but which are not necessarily orthogonal We would like to decompose an arbitrary f E H with fH g 1 into components f fstr fpsd femquot Where a fstr can be ef ciently represented as a bounded linear combination of a few vectors from S o fpsd has low correlations with any vector from S and o fen has a small norm ferrllH 24 Examples of the set S of fundamental structured vectors a 8 could be the set of linear functions a I gt 1 on F3 Fourier characters a 8 could be the set of polynomial functions of degree at most d on F3 Reed Muller codewords o 8 could be the set of indicator functions leg V X V gt 01 Where AB C V Our arguments here Will not depend on the exact nature of 8 other than the hypothesis that every vector in S has at most unit magnitude 25 If we x 8 we can de ne structure and pseudorandornness rnore quantitatively De nition A vector f E H is MK structured if one can write f 1 civi for some vi 6 S and some real numbers Ci With c g M De nition A vector f E H is pseudomndom if we have ltfvgt g e for all 21 E S 26 The orthogonal projection theorem Theorem 1 applied With V equal to the space spanned by 8 allows one to decompose f fstr fpsd fem Where fpsd is 0 pseudorandom and fem H 0 but the only thing one gets to say about fstr is that it is M K structured for some M K lt 00 no bound is provided The thresholding theorem Theorem 2 in contrast gives a decomposition f fstr fpsd fem Where fpsd is e pseudorandom ferrH 0 and fstr is l 152 structured but it requires the vectors in S to be orthonormal 27 One can generalise Theorem 2 to non orthonormal systems Weak structure theorem Let 0 lt e g 1 Then every f E H With fH g 1 can be de composed as f fstr fpsd fem where o fstr is 0511e2 struotured o fpsd is e pseudorendom ferr The decomposition is no longer unique 28 The proof proceeds by a slight modi cation of the energy decrement argument 0 Step 0 Initialise fstr ferr O and fpsd f a Step 1 If fpsd is e pseudorandom then STOP 0 Step 2 Otherwise locate a v E S such that ltfpsd vgt gt 5 Transfer a small multiple of v to fstr ehough to decrease fpsd 1 by at least 52 Now return to Step 1 It is not dif cult to show that this algorithm establishes the theorem 29 The weak structure theorem is often insuf cient for many applications because the pseudorandomness of fpsd is not particularly good compared With the complexity of fstr However it can be iterated to a better theorem Strong structure theorem Let 0 lt e g l and let F Z gt R be an arbitrary func tion Then every f E H With fH g 1 can be decomposed as f fstr fpsd fem Where o fstr is M M structured for some M 01251 0 fpsd is lFM pseudorandom llferrllH S 5 30 Thus the pseudorandornness of fpsd can exceed the structure of fstr by an arbitrary amount The catch is that the bound on M is poor and that we must also allow the error few to be non zero With a bit of additional effort one can make fstr fpsd and few orthogonal 31 Sketch of proof 0 Set M0 l and Mi FM 1 for each iLaann o For each 239 we can decompose f fstryi fpsdyi Where fpsdyi is lMi pseudorandorn and fsm is essentially Mi M structured a One can arrange matters so that all the fstryiirl fstryi are orthogonal to each other In particular fstr7 1 is increasing By the pigeonhole principle we can thus nd 239 051 such that llfsmllig llfstr 1llia S 8 NOW set fstr fStr l fpsd f fstr a M Mfr 17 32 and ferr fstr fstri 1 33 As typical applications of the strong structure theorem one can establish the graph regularity lemma of Szemer di and the arithmetic regularity lemma of Green One can also obtain a hypergraph regularity lemma by a slightly more intricate application of the same ideas These lemmas have a number of applications for instance to establishing the testability of various graph theoretic and arithmetic properties In these applications the growth function F usually needs to be exponential growth Since M is basically obtained by iterating F about Xe 01 times the bounds obtained by these methods is usually tower exponential or worse in nature 34 Structure theorems in measure spaces I In many cases the Hilbert space H arises from a probability space X X u as the space L2X X u of square integrable X measurable functions For instance a For functions f F3 gt R X X u is the space X F3 with uniform probability measure u and the discrete a algebra X o For graphs G V E X X u is the space X V x V with uniform probability measure u and the discrete a algebra B X is typically a finite set so X is a partition of X 35 In such contexts one often wants the following properties a Positivity preservation if f is non negative then fstr should also be non negative 0 Comparison principle if f g 9 then one should have fstr g gstr For instance if f is bounded pointwise by 1 then fstr should be also The Hilbert space structure theorems do not provide such properties However this can be xed by working with factors instead of vectors and using conditional expectation instead of orthogonal projection 36 A quick review of measure theory on nite sets De nition A factor of X X n is a triplet 3 Y37T Where Y is a set 3 is a 0 algebra or partition on Y and 7T X gt Y is a measurable map thus 7T13 is a coarsen ing of X The orthogonal projection Ef3 of f E L2XXu to L2X7T13u is called the conditional expectation of f relative to Y Example 1 If X Y are discrete u is uniform measure 7T X gt Y is a colouring of X into distinct colour classes 7T1y y E Y and f X gt R then Ef393 I EWx 7Txfx 37 Example 2 Any function f X gt R generates a factor 3 R 8 f Where B is the Borel a algebra this is the minimal factor with respect to Which f is measurable and is generated by the level sets f 1a of f Example 3 In many applications one needs a discretised version 3135 of the above construction in which 8 is now generated by the intervals 715 n le for n E Z thus f is almost measurable With respect to 3135 Which is generated by the level sets f 1n n le For technical reasons one sometimes has to shift the intervals 71 e n le by a random translation 38 Conditional expectation is better than other orthogonal projections because it preserves positivity 1 20 gt EMUgt20 and also enjoys a comparison principle lfl S g gt Ef3 S E93 39 De nition If 3 Y 3 7T and 31 Y 31 7T are two factors of X X u we let yvy Y x Y 3 x 32 7T7T be the join of 3 and 32 Useful Pythagorean identities fi2 Ef37lli2 llf Ef37lli2 Ef3V37 lli2 Ef3lli2EfyV339 Ef3lli2 40 We now represent structure not by a collection 8 of vectors but instead by a collection of factors eg factors generated by Reed Muller codewords or by complete bipartite graphs Fixing we can then define structure and pseudorandornness De nition A function f is M structured if it is measurable With respect to 313m for some m g M Where each 4 lies in De nition A function f is e pseudorandorn if we have Ef3L2 g e 41 By modifying the energy increment arguments discussed previously one can obtain weak and strong structure theorems Weak structure theorem If fL2X g 1 and e gt 0 then we can decompose f fstr fpsd fem Where o fstr is 152 structured In fact we have fstr Ef3 for some 152 structured factor 3 o fpsd is e pseudorandom ferr 42 Strong structure theorem If fL2X g 1 E gt 0 and F Z gt R then we can decom pose f fstr fpsd fem Where 0 fstr is M structured for some M O 11751 In fact we have fstr Ef3 for some M structured factor 3 o fpsd is 1FM pseudorandom errrllL2 S 839 43 A weak structure theorem of this type with the condition fL2X g 1 replaced by a weaker condition together with the comparison principle was decisive in establishing that the primes contained arbitrarily long arithmetic progressions Strong structure theorems of this type are related to structural theorems in ergodic theory and can be used for instance to establish Szemer di s theorem on arithmetic progressions 44 Gowers uniformity I Now we specialise to a very speci c notion of structure and pseudorandomness given by the Gowers uniformity norm d HfHUdaF3 3 EDIEg JE QEx H fix LW12 gang of a function f F3 gt R for d 2 l The dth Gowers norm re ects the extent to Which f behaves like a Reed Muller codeword of order d l ie 1P Where P is a polynomial over F2 of degree at most d 45 Examples HfHUlaFg lExeiFgf93f93 Mil2 lExEF3fxl Hf ilmg lExhkEF3f of a mm loft h W4 llflImg EmhkzEFfasfx hfa k fa h k l18 Functions with small U d norm are called Gowers uniform of order d l 46 Some easy facts 0 Monotonieity fU1SfU2 S fU3 S S llfllLoo o Cauchy SchwerZ Gowers inequality Emilee H fw93Lwl H mum wng 2ng 0 Norm properties llf 9HUd S HfHUd llgllyd IICfHUd lclllfllyd HfHUdO ltgt f0f0rd22 47 If f takes values in 11 then llfllUd ranges between 0 and 1 If f2Udd 1 5 then we have the identity fa H faw1h1wdhd wlwd01w1wd7 0 for randomly Chosen xh1 hd 6 F3 with probability 1 52 For instance if 1 5 then 1Pfafxhfaskfahk1 52 48 From this one can show 100 inverse structure theorem Let f F3 gt 11and d 2 1 Then llfllUd 1 if and only if f is a Reed Muller codeword of order d 1 99 inverse structure theorem Let f F3 gt 11 d 2 1 and e gt 0 Then if fUd 2 1 6 for some suf ciently small 6 68 d gt 0 f is Within 5 in L2 norm of a Reed Muller codeword of order d 1 49 The rst result is easy to prove by exploiting functional equations such as fa fa hfa kfa h The second result is due to Alon Kaufman Krivelevich Litsyn Ron and implies that Reed Muller codes are locally testable The rough idea is to use expressions such as fa hfa kfa h k as a vote as to What f should be and then use majority vote to discover the Reed Muller codeword Another approach is to proceed inductively observing that if f has large Ud norm then fThf Will have large UdL norm for most h Where Thfa fa h is the shift off by h 50 The following result is conjectured 1 inverse structure theorem Let f F3 gt ll d 2 l and e gt 0 Then if M f llUd 2 5 then there exists a Reed Muller codeword g of order d l such that f ggt gtgtd75 1 This is known for d g 2 by Plancherel s theorem and also for d 3 Sarnorodnitsky It remains open for d gt 3 and is known as the Gowers inverse conjecture for F3 Very recently Ben Green and I have been able to verify this conjecture in the case that f is a Reed Muller codeword of much higher but bounded degree In the converse direction one can easily show that 51 M f llUd 2 f ggt for all Reed Muller codewords g of order d 1 52 The Gowers inverse conjecture when combined with the general structured theorems discussed earlier would have many useful applications Basically one would be able to split any function f into a bounded number of Reed Muller codewords of order d 1 plus an error fpsd which is Gowers uniform of order d l and perhaps another small error fem This decomposition would allow us to understand local arithmetic patterns in functions in much the same way that the Szemer di regularity lemma allows us to understand local patterns inside large graphs 53 Philosophy 135 Spring 2008 Tony Martin Introduction to Metalogic 1 The semantics of sentential logic The language E of sentential logic Symbols of E i sentence letters pg7 p1 p2 ii connectives m V iii parentheses 7 Remarks a We shall pay little or no attention to the use mention distinction For instance7 we are more likely to write pl is a sentence letter77 than pl is a sentence letter77 b There are several standard variants of our list of connectives Trivial variants can be gotten by using literally different symbols to play the roles ours play For example7 it is common to use N in place of our Other variants can be gotten by using additional symbols that play different roles from those ours play7 eg7 connectives A a and lt gt We do not do this7 in order to keep de nitions and proofs as short and simple as possible We will7 however7 introduce the symbols mentioned above as abbreviations Instead of adding connectives to our list7 one could replace our connectives with others For example7 one could drop V and replace it by A We shall occasionally make remarks on how such changes would affect our de nitions of semantic and deductive concepts Formulas of E i Each sentence letter is a formula 11 If A is a formula7 then so is A A iii If A and B are formulas7 then so is A V B iv Nothing is a formula unless its being one follows from i7iii Let us officially regard formulas as sequences of symbols Thus the formula P1 V pz is of cially a sequence of length 6 This official stance will make little practical difference We often want to prove that all formulas have some property P A method for proving this is formula induction To prove by formula induction that every formula has property P we must prove i ii and iii below i Each sentence letter has property P ii If A is a formula that has property P then A has P iii If A and B are formulas that have property P then A V B has P If we prove i iii for P then clause iv in the de nition of formulas guarantees that all formulas have property P The proof of the following lemma is an example of proof by formula induction Lemma 11 Every formula contains the same number of occurrences of left parentheses as occurrences of right parentheses Proof Let P be the property of being a formula with the same number of left as right parentheses i Sentence letters have no parentheses so clearly they have property P ii Assume that A is a formula and that A has P Since A has the same occurrences of left and right parentheses as does A A has P iii Assume that A and B are formulas having property P The number of left parentheses in A V B is m n 1 where m is the number of left parentheses in A and n is the number of left parentheses in B and the number of right parentheses in AVB is m n 1 where m is the number of right parentheses in A and n is the number of right parentheses in B By assumption m m and n n so mn1 m n 1 Thus AVB has P The lemma follows by formula induction D Lemma 12 For euery formula A exactly one of the following holds 1 A is a sentence letter 2 There is a formula B such that A is B 5 There are formulas B and C such that A is B V C Proof Evidently at most one of 173 can hold for any formula so we need only show that for each formula at least one of 173 holds Since all the formulas given by instances of clauses i7iii in the de nition of formula are of these forms the desired conclusion follows by clause iv Lemma 13 For euery formula A a euery initial segment of A has the at least as many left as right parentheses b ifA is a disjunction ie is B V C for some formulas B and C then euery proper initial segment ofA ie euery initial segment ofA that is not the whole of A that has length greater than 0 has more left than right parentheses Proof Let P be the property of being a formula for which a and b hold We use formula induction to prove that all formulas have P In each of steps and ii the proof that a holds is similar to the corresponding step of the proof of Lemma 11 For steps and ii b holds vacuously We need then only prove that b holds for A V B on the assumption that A and B have property P Let C be a proper initial segment of A V B of length greater than 0 C contains the initial and does not contain the nal The desired conclusion follows from the assumption that a holds for A and B Lemma 14 No proper initial segment of a formula is a formula Proof We use formula induction with P the property of being a formula no proper initial segment of which is a formula Note that is trivial Note also that iii follows from Lemmas 13 and 11 This is because part b of Lemma 13 says that non zero length proper initial segments of disjunctions have more left than right parentheses while Lemma 11 says that formulas have the same number of left as right parentheses For ii assume that A has P Let D be a proper initial segment of A Since the empty sequence is not a formula we may assume that D has length gt 0 Thus D is A where A is a proper initial segment of A Since A has P A is not a formula It follows from this fact and Lemma 12 that A is not a formula D Theorem 15 Unique Readability Let A be a formula Then exactly one of the following holds I A is sentence letter 2 There is a unique formula B such that A is B 5 There are unique formulas B and C such that A is B V C Proof If A does not begin with a left parenthesis then Lemma 12 implies that exactly one of 1 or 2 holds Assume that A begins with a left parenthesis Then there must be formulas B and C such that A is B V C Assume that there are formulas B and Cquot such that B is different from B and A is B V C Then one of B and B must be a proper initial segment of the other contradicting Lemma 14 Exercise 11 Prove by formula induction that for every formula A the number of occurrences of sentence letters in A is one more than the number of occurrences of V in A Truth and logical implication We now know that our language has an unambiguous grammar Our next task is to introduce for it semantic notions such as meaning and truth The natural way to proceed is from the bottom up rst to give meanings to the sentence letters then to give meanings to the connectives and to use this to give meaningsiand truth conditionsito the formulas of E Let us rst consider the sentence letters As the name suggests they are to be treated as whole declarative sentences To give them a meaning we should specify what statement or proposition each of them expresses Sentential logic is sometimes called propositional logic and sentence letters are sometimes called proposition letters One way to do this would be to assign to each sentence letter a declarative sentence of English whose translation it would be The sentence letter would then have the same meaning express the same proposition as the English sentence If we did what was just suggested then each sentence letter would be given a meaning once and for all Once we speci ed the meanings of the connectives then E would be a language in the usual sense albeit an arti cial and a very simpli ed one But we do not want to use E in this way to express particular propositions Instead we want to use it to study logical relations between propositions to study relations between propositions that depend only on the logical forms of the propositions Therefore we shall not specify a xed way of assigning a proposition to each sentence letter but we shall try to consider all ways in which this might be done all ways in which the language could be turned into a language in the usual sense We want to de ne the general notion of what we might call an inteijnre tation of E or a model for E but what we shall actually call a ualuation for E We could de ne a valuation to be an assignment of a declarative En glish sentence to each sentence letter This seems however too restrictive a notion since there are surely many propositions that are not expressed by any English sentence We could instead de ne a valuation as an assignment of a proposition to each sentence letter But we shall have no reason to be concerned with the content of the propositions assigned to the sentence let ters We shall only need to deal with their tmth ualues with whether or not they are true or false Because we shall be doing truth functional logic the truth conditions for complex formulas will depend only on the truth values of the sentence letters that occur in them and not on what propositions the sentence letters express We de ne then a ualuation 12 for E to be a function that assigns to each sentence letter of E a truth ualue T or F Let 12 be a valuation for E The valuation 12 directly gives us a truth value to each sentence letter We next describe how it indirectly gives a truth value to each formula of E To do this we de ne a function 12 that assigns a truth value to each formula of E so that a if A is a sentence letter then 12 A 12A i F if 12A T W U FA T if 12A F T if 12A T and 12B T 7 7 i ltcgt WV B i 1 T and 53 i F if 12A F and 12B F We de ne a formula A to be true under the valuation 12 if 12A T and to be false under 12 if 12A F Have we actually de ned the function 12 We have for each of the three kinds of formulas told by an equation what 12 assigns to formulas of that kind But 12 appears on the right side as well as on the left side of these equations so this is not an ordinary de nition It is what is called a recursiue or inductiue de nition An example will make it intuitively clear that clauses a7c determine what truth value 12 assigns to any given formula Consider ups V P1 Vp3 Assume that vp1 T and vp3 F Then W291 T by a W293 F by a Naps T by 10 vp1Vps T by 6 vnp1Vps F by 10 UTP3VTP1VP3 T by 6 Thus pg V p1 Vp3 is true under 1 The de nition of 12 is an example of de nition by recursion on formulas This is a method for de ning a function h Whose domain is the set of all formulas To de ne h by this method one must a de ne hA from A for sentence letters A b de ne h A from A and hA for formulas A c de ne hA V B from A B hA and hB for formulas A and B Here we are being a little imprecise in order to be comprehensible Re maining at the same level of imprecision let us sketch how to use formula induction to prove that doing a7c determines a unique function h Whose domain is the set of all formulas Suppose a7c have been done Let P be the property of being a formula A for which a unique value hA is determined by the de nitions of a7c For and ii use the de nitions of a and b and the trivial parts of Unique Readability For iii assume that A and B are formulas that have P The de nition of c determines a value of hA V B from the values of hA and hB given by the fact that A and B have P The uniqueness of this value follows from the uniqueness of hA and hB together with Unique Readability It will be convenient to make to introduce some abbreviations A A B for A V B A a B for AV B A lt gt B for A a B A B a Bear in mind that A a and lt gt are not actually symbols of E Given a formula abbreviated by the use of these symbols one may eliminate the symbols via the contextual de nitions just given thus getting a genuine formula Let us also consider 3 as an abbreviation for a and N as an abbre viation77 for n since some students may be more used to these symbols than to the of cial ones It is not hard to see that the de ned symbols A a and lt gt obey the following rules T ifuATand uBT F ifuATand uBF d U AAB F ifuA F and 12B T F ifuAFand uBF T ifuATand uBT F ifuATand uBF e U AFB T ifuA F and 12B T T ifuAFand uBF T ifuATand uBT F ifuATanduBF f U AHB F if mEA F and uBT T if uA F and 12B F Exercise 12 Let u be the valuation for E de ned as follows 7 T ifi is even U U F ifi is odd Using the tables above7 determine which of the following two formulas are true under 12 1 P1 lt F191 V191 2 190 AM A F195 H FPO Exercise 13 Prove that the formula po lt gt p0 is true under 1 for every valuation u for E Exercise 14 Use de nition by recursion on formulas to de ne a function h such that7 for every formula A7 hA is the rst sentence letter occurring in A Let F be a set of formulas of E and let A be a formula of E Consider the argument F A with set of premises F and conclusion A We say that this argument is ualid if the formula A is true under every valuation u for E such that all the formulas in F are true under 1 To express this more brie y7 let us say that a set of formulas is true under a valuation u if all the formulas belonging to the set are true under 1 Then F A is a valid argument if and only if A is true under every valuation under which P is true There is a different way to talk about valid arguments and we shall usually talk in this second way If P is a set of formulas and A is a formula then say that P logically implies A if P A is a valid argument We write P A to mean that P logically implies A A special case of valid arguments and logical implication occurs when P is the empty set 0 We usually write l A instead of Q l A When l A we say that A is valid or that A is a tautology A formula is a tautology if and only if it is true under every valuation for E A formula is satis able if it is true under some valuation Similarly a set of formulas is satis able if it is true under some valuation ie if there is a valuation under which all the formulas in the set are true Exercise 15 Which of the following are tautologies Prove your answers 1 190 H191 H192 p P1 A192 2 190 H191V191 H192 Exercise 16 Which of the following are statements are true Prove your answers 1 2 If A and B are formulas then by A B we mean that A l B PO A ppm 192 V190 H191 V192 um l upo ups V190 V191 pm A pm 190 H192 M93 l P1 Exercise 17 Let P and A he sets of formulas and let A B and A1 AL be formulas Prove each of the following 1 PUA lB ifand only ifP AHB 2 A1An lBifand only if l A1 a HAnHB 3 A is satis able if and only if A p0 A po 4 If P C for every C belonging to A and if A l B then P l B When we omit parentheses in a formula as we did in 2 we make use of a convention that omitted parentheses group to the right Thus A1 a gt An gt B abbreviates A1 a gt An a B Mathematical induction To prove that all natural numbers have some prop erty P7 one may use mathematical induction To do this one must prove and ii below i 0 has P ii If n is a natural number that has P7 then it 1 has P One can de ne functions by de nition by recursion on natural numbers as well as by recursion on formulas Recursion on natural numbers is a method for de ning a function h whose domain is the set N of all natural numbers To de ne h by this method7 one must a de ne h0 b de ne hn 1 from n and hn for natural numbers n Example The clauses i h0 0 ii hn 1 hn11 give a de nition by recursion of the doubling function in terms of the suc cessor function 1 Exercise 18 The factorial function is the function h with domain N such that h0 1 and7 for every n gt 07 hn is the product of all the positive integers n Show how to de ne the factorial function by recursion on natural numbers We now embark on the proof of the Compactness Theorem7 one of the main theorems about our semantics for E Say that a set P of formulas is nitely satis able if every nite subset ofF is satis able The Compactness Theorem will assert that every nitely satis able set of formulas is satis able Lemma 16 Let P be a nitely satis able set of formulas and let A be a formula Then either P U A is nitely satis able or P U A is nitely satis able Proof Assume for a contradiction neither P U A nor P U A is nitely satis able It follows that there are nite subsets A and A of P such that neither A U A nor A U A is satis able Since P is nitely satis able7 the nite subset A U A of P is satis able Let u be a valuation under which A U A is true If A is true under 1 then A U A is true under 1 and so is satis able Otherwise A U A is true under 1 and is satis able In either case we have a contradiction D Lemma 17 Let P be a nitely satis able set of formulas There is a set P of formulas such that 1 P Q 1 2 P is nitely sati able 5 for euery formula A either A belongs to P or A belongs to 1 Proof We can list all the formulas in an in nite list as follows Think of the symbols of E as forming an in nite alphabet with the alphabetical order T V 7 71907 1917 p27 First list in alphabetical order all the nitely many formulas that have length 1 and contain no occurrences of sentence letters other than p0 Next list in alphabetical order all the remaining formulas that have length 2 and contain no occurrences of sentence letters other than p0 and p1 Next list in alphabetical order all the remaining formulas that have length 3 and contain no occurrences of sentence letters other than p0 p1 and p2 Continue in this way If we gave the details what we would be doing in describing this list would be to de ne a function by recursion on natural numbersithe function that assigns to n the formula called An in following paragraph Let the formulas of E in the order listed be A07 A17 A27 A37 We de ne by recursion on natural numbers a function that associates with each natural number n a set D of formulas Let P0 P Let P 7 D U An if D U An is nitely satis able 1 7 D U An otherwise Let 1 U Tn Because P F0 Q l W has property F0 is nitely satis able By Lemma 16 if D is nitely satis able then so is Tn By mathematical induction every D is nitely satis able If A is a nite subset of 1 then A Q R for some n Since D is nitely satis able A is satis able Thus W has property Because either 14 or An belongs to D for each n and because each R Q l W has property It will be convenient to introduce the symbol 6 as an abbreviation for belongs to77 Lemma 18 Let P be a set of formulas having properties and described in the statement of Lemma 17 Then P is satis able Proof De ne a valuation v for E by setting vA T if and only if A E W for each sentence letter A Let P be the property of being a formula A such that 12A T if and only if A E F We prove by formula induction that every formula has property P i For sentence letters this is true by de nition of 1 ii First we show that A E P if and only if A W for any formula A By 3 we have that A E W or A E F Suppose that both A and A belong to P Then A A is a nite subset of F By 2 we get the contradiction that A A is satis able Now let A be a formula that has property P Then 12 A T if and only if 12A F if and only if A W if and only if A E W iii We rst show that A V B E P if and only if either A E W or B E l for any formulas A and B Assume rst that A V B E F but that A W and B F By 3 A E W and B E F Thus A V B A B is a nite subset of F By 2 we get the contradiction that AVB A B is satis able Next assume that A E F but AVB W By 3 A V B E l and so A A V B is a nite subset of F By 2 we get the contradiction that A A V B is satis able A similar argument shows that if B E F then A V B E F Now let A and B be formulas that have property P Then UAVB T if and only if 12A Tor 12B T if and only if A E W or B E W if and only if A V B E W Since in particular 12A T for every member of A of l we have shown that W is satis able Exercise 19 Suppose that we added A as an official symbol of E extend ing the de nition of truth using the table for A on page 7 Then proof by formula induction would have an extra step showing that AAB has prop erty P if both A and B have P Supply this A A B case for the proof by formula induction just given Theorem 19 Compactness Let P be a nitely satis able set of for mulas Then P is satis able Proof By Lemma 177 let V have properties 173 of that lemma By Lemma 187 W is satis able Hence P is satis able D Corollary 110 Compactness Second Form Let P be a set of for mulas and let A be a formula such that P l A Then there is a nite subset A ofP such that A l A Exercise 110 Prove Corollary 110 2 Deduction in Sentential Logic Though we have not yet introduced any formal notion of deductions ie of derivations or proofs we can easily give a formal method for showing that formulas are tautologies Construct the truth table of a given formula ie compute the truth value of the formulas for all possible assignments of truth values to the sentence letters occurring in it If all these truth values are T then the formula is a tautology This method extends to give a formal method for showing that P A provided that P is nite The method even extends to the case P is in nite since the second form of Compactness guarantees that if P l A then A l A for some nite A Q P Nevertheless we are now going to introduce a different system of formal deduction This is because we want to gain experience with the metatheory of a more standard deductive system The system SL Axioms From now on we shall often adopt the convention of omitting outmost parentheses in formulas For any formulas A B and C each of the following is an axiom of our deductive sytem 1 AHAB 2 BHAB 3 AVBHW4HB 4 oAHB H oAHoB H A 5 AH BHCD H AHB HMHC Remarks a Note that 175 are not axioms but axiom schemas There are in nitely many instances of each of these schemas since A B and C may be any formulas whatsoever b Note also that we have used abbreviations in presenting these axiom schemas For example the except for outer parentheses unabbreviated Axiom Schema 1 is A V A V B Rule of Inference A AHB Modus Ponens MP B 13 For any formulas A and B7 we say that B follows by modus ponens from A and A a B Deductions A deduction in SL from a set P of formulas is a nite sequence D of formulas such that whenever a formula A occurs in the sequence D then at least one of the following holds 1 A e P 2 A is an axiom 3 A follows by modus ponens from two formulas occurring earlier in the sequence D If A is the nth element of the sequence D7 then we say that A is on line 71 ofD or even that A is line 71 of D A deduction in SL of A from P is a deduction D in SL from P with A on the last line of D We write P FSL A and say A is deducible in SL from P to mean that there is a deduction in SL of A from P Sometimes we may express this by saying P proves A in SL We write FSL A for Q FSL A We shall mostly omit the subscript SL and the phrase in SL77 during our study of sentential logic7 since SL will be the only system we consider until we get to predicate logic Example 1 Let A and B be any formulas Here is a very short deduction of A a B a A from 0 This deduction shows that b A a B a A 1 AgtBgtA AX2 AH BVA ln square brackets we have rewritten line 1 in a less abbreviated way7 in order to show that it is an instance of Axiom Schema 2 The formula A is the B of the schema7 and the formula B is the A of the schema Example 2 Below we give a deduction of A a A from 0 This deduction shows that b A a A 1 A gt AHA HA gt AH A HA gt AHA AX 5 2 AgtAgtAgtA Ax2 3 A gt A gt A gt A gt A 12MP 4 AH AHA AX 2 5 AgtA 34MP Theorem 21 Deduction Theorem Let P be a set offormulas and let A and B be formulas IfP U A F B then P F A gt B Proof Assume that PU A F B Let D be a deduction of B from PU We prove that P F A a C for every line C of D Assume that this is false Consider the rst line C of D such that P V A a C Assume that C either belongs to P or is an axiom The following gives a deduction of A a C from P 1 C 2 C gt A gt C AX 2 3 A gt C 12MP Assume next that C is A We have already shown that F A a A Thus P F A a A Finally assume that C follows from formulas E and E a C by MP These formulas are on earlier lines of D than C Since C is the rst bad line of D let D1 be a deduction of A a E from P and let D2 be a deduction of A a E a 0 from F We get a deduction of A a C from P by beginning with D1 following with D2 and then nishing with the lines AH gt HAgtC AX5 AHEgtAgtC MP A a 0 MP This contradiction completes the proof that the bad line C cannot exist Applying this fact to the last line of D we get that P F A a B D Remarks a The converse of the Deduction Theorem is also true Given a de duction of A a B from P one gets a deduction of B from P U A by appending the lines A and B the latter coming by MP b The proof of the Deduction Theorem would still go through if we added or dropped axioms as long as we did not drop Axiom Schemas 2 and 5 It would not in general go through if we added rules of inference and it would not go through if we dropped the rule of modus ponens Exercise 21 Show that the following hold for all formulas A and B a F A n W4 n 3 b t A a A A set P of formulas is inconsistent in SL if there is a formula B such that P F B and P F B Otherwise P is consistent Theorem 22 LetP and A be sets offormulas and letA B and A17An be formulas I PUAFBifandonlyifPFAgtB 2 PUA1A LFB ifandonly ifPFA1 HgtAngtB 5 P is consistent if and only if there is some formula C such that PVC 41fPFCforallCEA andz39fAFB thenPFB Proof We begin with Let D be a deduction of B from A We can turn D into a deduction of B from P as follows whenever a formula C E A is on a line of D7 replace that line with a deduction of C from P 1 is just the combination of the Deduction Theorem and its converse For 27 forget the particular T A1 7A 7 and B for the moment and let P be the property of being a positive integer n such that 2 holds for every choice of P 1417An7 and B By a variant of mathematical induction beginning with 1 instead of with 0 we show that every positive integer has P The integer 1 has P by Assume that n is a positive integer that has P Let T A1 714711 and B be given By 1 we have that PU A1An1 F B if and only ifPU A1An F AnsrjL a B Since n has P7 this holds if and only if P F A1 a a An a B For the if part of 37 assume that P is inconsistent Let B be such that P F B and P F B Let C be any formula Using Axiom Schema 2 and Ml7 we get that P F C a B and P F C a B The formula C AB gt CH B gt C is an instance of Axiom Schema 4 Two applications of MP show that P F C The only if77 part of 3 is obvious 16 Lemma 23 For any formulas A and B a e14 a 3 F AB a A b A a 13 F B A A Proof a By the Deduction Theorem7 it is enough to show that AHB B F A Let P A a B7 B Axiom Schema 2 and MP give that P F A a B The formula AHB gt AH B gt A is an instance of Axiom Schema 4 Two applications of MP show that P F A b Since F A a A by part b of Exercise 217 we can use the Deduction theorem and easily get that A a B F A a B But A a 13 F B a A by part a D Exercise 22 Exhibit a deduction of pg a 191 from ipl a p2 Do not appeal to the deduction theorem Hint First write out the deduction D of p1 from pl a pg7 pg that is implicitly given by the proof of part a of Lemma 23 Now use the proof of the Deduction Theorem to get the desired deduction The proof of the Deduction Theorem shows us how to put pg a in front of all the lines of the given deduction and then to x things up There is one simpli cation here If one puts pg a in front of the formula pl a pg that is on line 3 of D7 one gets an axiom Thus one can forget about lines 1 and 2 of D and just begin with this axiom Exercise 23 Show the following a F AaB H lB b F A V AA A system S of deduction for E is sound if7 for all sets P of formulas and all formulas A7 if P Fg A then P l A An example of a system of deduction that is not sound can be gotten by adding to the axioms and rules for SL the extra axiom p0 For this system S7 one has that 0 F3 pg7 but 0 t pg 17 Theorem 24 Soundness Let P be a set of formulas and let A be a formula IfP FSL A then P A In other words SL is sound Proof Let D be a deduction in SL of A from F We shall show that for every line C of D P C Applying this to the last line of D this will give us that P l A Assume that what we wish to show is false Let C be the rst line of D such that P b C If C E P then trivially P C and so we have a contradiction It can easily be checked that all of our axioms are tautologies If C is an axiom we have then that C and so that P l C Note that the rule of modus ponens is a valid rule ie D D a E for any formulas D and E Assume that C follows by MP from B and B a C where B and B a C are on earlier lines of D Since C is the rst bad line of D P B and P B a C By the validity of MP it follows that P l C D A system S of deduction for E is complete if for all sets P of formulas and all formulas A if P l A then P kg A Remark Sometimes the word complete used to mean what we mean by sound and complete77 We are now going to embark on the task of proving the completeness of SL The proof will parallel the proof of the Compactness Theorem In particular the lemma that follows is the analogue of Lemma 16 Lemma 25 Let P be a consistent in SL set of formulas and let A be a formula Then either P U A is consistent or P U A is consistent Proof Assume for a contradiction neither P U A nor P U A is consis tent It follows that there are formulas B and B such that i P U A k B ii P U A k AB iii r o m4 k B iv P U A k B Using Axiom Schema 4 together with iii iv and the Deduction The orem we can show that P k A 18 This fact together with and ii allows us to show that P F B and P F B Thus we have the contradiction that P is inconsistent D Now we turn to the analogue of Lemma 17 Lemma 26 Let L be a consistent set of formulas There is a set L of formulas such that I L Q L 39 2 L is consistent 5 for euery formula A either A belongs to L or A belongs to L5 Proof Let A07 A171427 A37 be the list de ned in the proof of Lemma 17 of all the formulas of E As in that proof we de ne by recursion on natural numbers a function that associates with each natural number n a set D of formulas Let P0 P Let P 7 D U An if D U An is consistent 1 7 D U An otherwise Let 1 U Tn Because P LO Q l W has property F0 is consistent By Lemma 25 if D is consistent then so is Ln By mathematical induction every D is consistent Suppose in order to obtain a contradiction that W is inconsistent Let B be a formula such that W F B and W F B Let D1 and D2 be respectively deductions of B from W and of B from P Let A be the set of all formulas belonging to F that are on lines of D1 or of D2 Then A is a nite subset of l and so A Q R for some n But then D F B and D F B This contradicts the consistency of BL Thus W has property Because either 14 or An belongs to D for each n and because each R Q l W has property Next comes the analogue of Lemma 18 Lemma 27 Let L be a set of formulas hauing properties and described in the statement of Lemma 26 Then L is satis able 19 Proof De ne a valuation v for E by setting vA T if and only if A E W for each sentence letter A Let P be the property of being a formula A such that 12A T if and only if A E F We prove by formula induction that every formula has property P i For sentence letters this is true by de nition of 1 ii First we show that A E P if and only if A W for any formula A By 3 we have that A E W or A E F If both A and A belong to 1 then P is inconsistent contrary to Now let A be a formula that has property P Then 12 A T if and only if 12A F if and only if A W if and only if A E W iii We rst show that A V B E P if and only if either A E W or B E l for any formulas A and B Assume rst that A V B E F but that A W and B F By 3 A E W and B E F Using the instance A V B a A a B of Axiom Schema 3 and two applications of MP we see that W F B Since W F B we get the contradiction that W is inconsistent Next assume that A E F but A V B W By 3 A V B E F Using the instance A a A V B of Axiom Schema 1 we again get the contradiction that W is inconsistent The assumption that B E F but A V B W yields a similar contradiction with the aid of Axiom Schema Now let A and B be formulas that have property P Then UAVB T if and only if 12A Tor 12B T if and only if A E W or B E W if and only if A V B E W Since in particular 12A T for every member of A of l we have shown that W is satis able Theorem 28 Let P be a consistent set offormulas Then P is satis able Proof By Lemma 26 let V have properties 173 of that lemma By Lemma 27 W is satis able Hence P is satis able D 20 Theorem 29 Completeness Let P be a set offormulas and let A be a formula such that P l A Then T FSL A In other words SL is complete Proof Since P l A PU A is not satis able By Theorem 28 FU A is inconsistent Let B be a formula such that PU A F B and PU A F B By the Deduction Theorem P F A a B and P F A a B Using Axiom Schema 4 we can use these facts to show that P F A D Exercise 24 Derive Theorem 28 from Theorem 29 Remark Soundness and completeness imply compactness To see this assume that P is a set of formulas that is not satis able By part 3 of Exercise 17 P p0 A po By completeness P F p0 A po Let D be a deduction of po A po from P Let A be the set of all formulas C E P such that C is on a line of D Then A is a nite subset of P and A F poA po By soundness A p0 A po By part 3 of Exercise 17 A is not satis able Thus P is not nitely satis able Exercise 25 Prove that AA B F AVB and that AVB F A A B You may use any of our theorems lemmas etc Exercise 26 We de ne by recursion on natural numbers a function that assigns to each natural number n a set Formula of formulas Let Formulae be the set of all sentence letters Let A belong to Formulan if and only if at least one of the following holds i A 6 Formula ii there is a B E Formulan such that A is B iii there are B 6 Formula and C 6 Formula such that A is B v C It is not hard to prove that A is a formula if and only if A belongs to Formulan for some a You may assume this Use mathematical induction to prove that every formula has an even number of parentheses Exercise 27 Show without using Completeness and Soundness that F B gt A a A v B Exercise 28 Suppose we changed our system of deduction by replacing the Axiom Schemas 1 and 2 by the rules A B AVB AVB Would the resulting system be sound Would it be complete Exercise 29 Show7 without using completeness and soundness7 that AHC397 BHC F AVB 0 Exercise 210 Use the Deduction Theorem and its converse to give a brief proof that F B a A a 3 The semantics of pure rstorder predicate logic We now begin our study of what is called among other things predicate logic quanti cational logic and rst order logic We shall use the term rst order logic for our subject The term predicate logic suggests formal languages that have predicate lettrers but not function letters and we do not want to leave out the latter Both predicate logic and quanti cational logic fail to suggest that higher order and in nitary logics are excluded andiexcept for a brief consideration of second order logic at the end of the courseiwe do intend to exclude them In order that our rst pass through rst order logic be as free of complex ities as possible we study in this section a simpli ed version of rst order logic one whose formal languages lack two important kinds of symbols a function letters b an identity symbol We call this simpli ed logic pure rst order predicate logic In the next section we shall see what changes have to be made in our de nitions and proofs to accommodate the presence of these symbols The languages D5 of pure predicate logic For each any set C of constant symbols we shall have a language Ea Symbols of Ca i sentence letters p0 p1 p2 ii for each n 2 1 n place predicate letters P1 P2 iii variables v0 v1 v2 iv constant symbols constants all members of C v connectives V vi quanti er V vii parentheses Constants and variables will more or less play the role played in natural languages by nouns and pronouns respectively Predicate letters will more or less play the role that predicates play in natural languages In combination these symbols will give our formal language a new kind of basic formulas the simplest of which will play the role that subject predicate sentences play in natural languages The quanti er V will play the role that the phrase for all77 can play in natural languages Formulas of 3 1 Each sentence letter is a formula 2 For each n and i if t1 tn are variables or constants then Pintl tn is a formula 3 4 5 6 Nothing is a formula unless its being one follows from 175 If A is a formula then so is A If A and B are formulas then so is A V B If A is a formula and z is a variable then VmA is a formula The formulas given by 1 and 2 are called atomic formulas The method of proof by formula induction applies to 3 as it does to E To prove by formula induction that every formula of 3 has property P we must prove i ii iii and iv below i Each atomic formula has property P 1 If A is a formula that has property P then A has P iii If A and B are formulas that have property P then A V B has P A 1v If x is a variable and A is a formula that has property P then VmA has P Not only is there a step step iv that was absent in the case of E but also there is an extra part to step ii the part corresponding to atomic formulas of the form Pintl tn Unique readability holds for 3 as it does for E Here are the new ver sions of the Lemmas 11714 that were used to prove the unique readability theorem Theorem 15 The proofs are similar to the proofs of the earlier lemmas and theorem Lemma 31 Every formula of 3 contains the same number of occur rences of left parentheses as occurrences of right parentheses Lemma 32 For euery formula A of a euery initial segment of A has the at least as many left as right parentheses b ifA is a disjunction ie ifA is BVC for some B and C then every proper initial segment of A ie every initial segment of A that is not the whole of A that has length greater than 0 has more left than right parentheses Lemma 33 For every formula A of exactly one of the following holds 1 A is an atomic formula 2 There is a formula B such that A is B 5 There are formulas B and C such that A is B V C 4 There is a formula B and there is a variable m such that A is VmB Lemma 34 No proper initial segment of a formula of EEis a formula of 3 Theorem 35 Unique Readability Let A be a formula of 3 Then exactly one of the following holds 1 A is an atomic formula 2 There is a unique formula B such that A is B 5 There are unique formulas B and C such that A is B V C 4 There is a unique formula B and there is a unique variable m such that A is VmB Remark Note that we could have phrased Lemma 13 exactly as Lemma 32 is phrased without altering its content in any signi cant way Truth and logical implication As we did with the sentential language E we want to introduce semantic notions for the languages Ea If we want to keep as close as possible to the methods of 17 then we might try to extend the notion of a valuation v so that v assigns a truth value to all atomic formulas7 not just all sentence letters But consider an atomic formula like P12v3c The symbol v3 is a variable7 ie7 we are not going to use it to denote any particular object The language of arithmetic does not provide a truth value for an expression like m lt 377 and the English language does not provide a truth value for sentences like He is fat77 To get a truth value for the former7 one needs to assign the variable x to some particular number To get a truth value for 25 the latter one needs a context in which he denotes a particular person or animal or whatever Similarly the semantics of D5 will not by itself provide a truth value for P121136 In addition there will have to be an assignment of v3 to some particular object What are the objects over which our variables are to range A natural answer would be that they range over all objects If we made this choice then we could interpret va as saying for all objects v377 However there are reasons for not wanting to make a matter of logic that eg there are more than 17 objects and requiring that our variables range over all objects would make this a matter of logic Therefore we allow the variables to range over any set of objects and we make the speci cation of such a set part of any interpretatation of our language The rst step in providing an interpretation of D5 or as we shall say a model for D5 is thus to specify a set D as the domain or universe of the model It is standard to require that D be a non empty set because doing so avoids certain technical complexities We make this requirement The second step is to provide a way to assign truth values to atomic formulas when their variables are assigned to particular members of D To accomplish this in an indirect way we specify the truth values of sentence letters and ii we specify what property of elements of D or relation among elements of D each predicate letter is to stand for We do this by telling for each n and i which n tuples d1 dn of elements of D the predicate P is true of The nal step in determining a model for D5 is to specify what element of D each constant denotes Here is the formal de nition A model for D5 is a triple 93 D v x where i D is a non empty set the domain or universe of 93 ii v is a function the valuation of 93 that assigns a truth value to each sentence letter and each n 1 tuple of the form Pin 11 dn for all dn members of D iii X is a function the constant assignment of 93 that assigns to each constant an element of D Note that except for the sentence letters the things to which v assigns truth values are not actually formulas In describing the v of a model we shall often nd it convenient to list the set of things to which v assigns T Let us call this the v truth set Examples a Let Ca Let 931a DavaXa where Da 11412 viz truth set p2 P1 11 P270114127 P27 12412 XaC d2 b Let C 0 0 Let 9311 D5 125 X17 where Db 012 vb truth set Pl 0 U PZ mn l m 2 n Xbc 0 Xbc 1 Whenever we omit the subscript of a predicate letter as we have done in describing these two models let us take the omitted subscript to be 0 Let 9 D ax be a model for 3 Let s be a variable assignment a function that assigns a member 5z of D to each variable m For each variable or constant 25 let s i 3t ift is a variable lemma 7 Xt ift is a constant By a modi ed version of recursion on formulas we de ne a function 12ng that assigns a truth value to each formula i The case of A atomic a Ui pi Wm b U3XP t1tn UP denfmt1 denfmtn H s F ifv9AT 11 WW T if gm F T if ug m T and 413 T T 1fv9ATandv9BF s 7 93E 93E 7 1 DNA V Bl T if ng F and yaw T F if ug m F and 1413 F T if for all d e D uggtm T iv ug WmA where s is like 3 except that sm d F otherwise 9 satis es A under 3 if and only if u A T An occurrence of a variable x in a formula A is free if the occurrence is not within any subformula of A of the form VzB A sentence or closed formula is a formula with no free occurrences of variables Example The third occurrence of U1 in the formula V112 VU1P31U1 V P12111112 is free7 and so this formula is not a sentence It is not hard to verify that whether or not 9 satis es A under s does not depend on the whole of s but only on the values sz for variables x that have free occurrences in A For sentences A7 we may then de ne 1293A to be the common value of all u A We de ne a sentence A to be true in 93 if 1293A T and false in 93 if 1293A F 9 satis es a set P of formulas under 3 if and only if all 9 satis es each member of P under s A set of sentences is true in 93 if and only if all its members are true in 93 We introduce one more abbreviation HmA for Vz A It is not hard to verify that the de ned symbol 3 obeys the following rule T if for some d e D uggtm T v ug mA where s is like 3 except that sm d F otherwise Example Here are some sentences true in the model 93 described on page 27 Plc Vu ug P2121122 3121192 A P2121121 Exercise 31 For each of the following sentences7 tell in which of the mod els 931a and 93117 the sentence is true Explain your answers brie y and infor mally a 3mm P2112111 b V111 P1111 V P2014 c VU1P1U1 gt pg 1 3111P1u1 H192 If P is a set of formulas and A is a formula then we say that P logically implies A in symbols P l A if and only if for every model 93 and every variable assignment 3 if 9 satis es P under s then 9 satis es A under s A formula or set of formulas is valid if it is satis ed in every model under every variable assignment it is satis able if it is satis ed in some model under some variable assignment As in sentential logic a formula A is valid if and only if Q l A and we abbreviate Q l A by l A We shall be interested in the notions of implication validity and satis ability mainly for sets of sentences and sentences In this case variable assignments 3 play no role For example a set E of sentences implies a sentence A if and only if for every model 93 if E is true in 93 then A is true in 93 Exercise 32 For each of the following pairs F A tell whether P l A If the answer is yes explain why If the answer is no then describe a model or a model and a variable assignment showing that the answer is no a P V Ula uz P2111112 A 3U2V U1 P2111112 b P 3U1V U2 P2111112 A va vl P2111112 C P V111 P2U1U1P26162 A P126261 PC V111va P2111112 A V UgV Ul P2111112 e P P1121 A V121 P1121 Exercise 33 Describe a model in which the following sentences are all true a V Ula ug P2111112 b VU1VU2P2 U1 U2 gt szgvl c VU1V U2V U3P2 U1 U2 A P2112113 gt P2111113 Can these three sentences be true in a model whose universe is nite Ex plain Exercise 34 Show that the four statements of Exercise 17 hold for for mulas of 3 For sentential logic valid formulas and tautologies are by de nition the same For predicate logic the notion of a tautology is different from that of a valid formula We now explain how this difference arises Call a formula of any of our formal languages sententially atomic if it is neither a negation nor a disjuction ie if it is not A for any A and it is not A V B for any A and B The sententially atomic formulas of E are the sentence letters The sententially atomic formulas of D5 are the atomic formulas and the quanti cations the formulas of the form VzA Note that every formula can be gotten from the sententially atomic formulas using only negation and conjunction An extended ualuatz39on for any of our languages is a function that assigns a truth value to each sententially atomic formula Let u be an extended valuation We as follows de ne a function 12 that assigns a truth value to each formula a if A is sententially atomic then uA uA 7 i F if uA T b 1 T ifuAF T if uA T and 12B T at T ifuATand uBF C U AVE T ifuA F and 12B T F if uA F and 12B F We de ne a formula A to be true under the extended valuation u if uA T and to be false under 1 if uA F We de ne a set P of formulas to be true under 1 if and only if all members of P are true under u If P is a set of formulas and A is a formula then say that P sententially implies A if and only if A is true under every extended valuation under which P is true We write P 51 A to mean that P sententially implies A A formula A is a tautology if and only if 0 51 A ie if and only if A is true under every extended valuation We usually write l51 A instead of Q l51 A For the language E the new de nition of tautology agrees with the old de nition It is easy to see that for both E and 3 every tautology is valid The converse while true for E is false for 3 For example the formula V Ul P1111 V Pl Ul is valid but is not a tautology 30 We now begin the proof of the Compactness Theorem for 3 As we did with E we call a set P of formulas of 3 nitely satis able if every nite subset of P is satis able The Compactness Theorem we shall prove states that every nitely satis able set of sentences is satis able The stronger statement with sentences replaced by formulas is true The reasons why we prove only the weaker one are a simplicity and b considerationsito be explained lateriinvolving the theory of deduction The analogue for formulas of the following lemma is true and has a proof like that of the lemma Lemma 36 Let P be a nitely satis able set of sentences of 3 and let A be a sentence of 3 Then either P U A is nitely satis able or P U A is nitely satis able Proof The proofis like the proof of Lemma 16 Assume for a contradiction neither P U A nor P U A is nitely satis able It follows that there are nite subsets A and A of P such that neither A U A nor A U A is satis able Since P is nitely satis able the nite subset A U A of P is satis able Let 9 be a model in which A U A is true If yg A T then A U A is true in 93 and so A U A is satis able Otherwise A U A is true in 93 and so A U A is satis able In either case we have a contradiction Simplifying assumption From now on we assume that the members of the set C can be arranged in a nite or in nite list In the technical jargon of set theory this is the assumption that C is countable Most of the facts we shall prove can be proved without this assumption but the proofs involve concepts beyond the scope of this course Our next lemma is the analogue for D5 of Lemma 17 The main dif ference from the earlier lemma is that the set F has a fourth property This property will be needed for the proof of Lemma 38 the analogue of Lemma 18 If A is a formula z is a variable and t is a variable or constant then Azt is the result of replacing each free occurrence of z in A by an occurrence of t A set P of formulas is Henkin if and only if for each formula A and each variable x if below holds then ii also holds i Az c E P for all c E C ii WA 6 r 31 Lemma 37 Let P be a nitely satis able set of sentences of Ca Let C be a set gotten from C by adding in nitely many new constants There is a set P of sentences of such that I P Q P 39 2 P is nitely sati able 5 for every sentence A of EB either A belongs to P or A belongs to P 4 P is Henkin Proof In keeping with our simplying assumption let c0 c1 be all the constants of D5 Since has symbols that are not symbols of E we need to specify an alphabetical order for the symbols of Let that order be as follows v V7 7 7 V7 110111 112 606162 P07 P17 P27 p3p11p21 12021212 1222 Now we give a method for listing all the sentences of Eat in an in nite list First list in alphabetical order all the sentences that have length 1 and contain no occurrences of variables constants sentence letters or pred icate letters with any subscript or superscript larger than 0 Next list in alphabetical order all the sentences that have length 2 and contain no oc currences of variables constants sentence letters or predicate letters with any subscript or superscript larger than 1 Next list in alphabetical order all the sentences that have length 3 and contain no occurrences of vari ables constants sentence letters or predicate letters with any subscript or superscript larger than 2 Continue in this way Let the sentences of 3 in the order listed be A0 141142 A3 We de ne by recursion on natural numbers a function that associates with each natural number n a set D of sentences of 3 Let P0 P 32 For each n we shall make sure that at most two sentences belong to BL but not to BL Since none of the constants added to C to get 0 occur in sentences in P it follows that for each 71 only nitely many of the new constants occur in sentences in Tn We de ne Ln from D in two steps For the rst step let P 7 D U An if D U An is nitely satis able 7 D U An otherwise Let Ln Pl unless both of the following hold a An 6 Pg b An is Vann for some variable zn and formula B Suppose that both a and b hold Let in be the least i such that the constant c does not occur in any formula belonging to Pg Such an i must exist since only nitely many of the in nitely many new constants occur in sentences in KL Let Pn1 U 3 Let F U Tn Because P LO Q l W has property We prove by mathematical induction that D is nitely satis able for each 71 F0 is nitely sati able by hypothesis1 Assume that D is nitely satis able Lemma 36 implies that Pl is nitely satis able lf Ln UL then BL is nitely satis able Assume then that a and b hold and so Ln Pl U Bnzncn and in order to derive a contradiction assume that BL is not nitely satis able For some nite subset A of Pg A U Bnzn 0 is not satis able Since Pl is nitely satis able and fty 6 Pg A U An is satis able Let 9 D UX be a model for 5 in which A U An is true Since An is anBn Vann is false in 93 This means that there is a d E D such that 125103 F for any variable assignment 3 such that 5zn d Let 931 D UX be just like 93 except let xcn d 1Actually there is a subtlety here The assumption that F is nitely satis able if precisely formulated says that every nite subset of F is true in some model for 23 But we want F0 to be nitely satis able in the sense that every nite subset of F0 is true in a model for fy Nevertheless there is no problem Any model for 23 can be made into a model for 5 by de ning X of the new constants in an arbitrary way Since F0 contains none of the new constants subsets of it will be true in the resulting model if and only if they are true in the given one 33 Since oi does not occur in B 7 UM Bnni 3 F39 Since oi does not occur in A7 A is true in 931 Thus we have the contra diction that A U Bnzn 0 is satis able If A is any nite subset of l 7 then A Q Tn for some n Since Tn is nitely satis able7 A is satis able Thus W has property Because either An or An belongs to BL for each n and because each Tn Q l 7 W has property Suppose that A is anBn lf An l 7 then An Tn and so An 6 BL But this implies that Bnmncin 6 BL Q P By property 2 of l 7 it follows that Bnmncin F This argument shows that W has property D Lemma 38 Let P be a set of sentences of a language having proper ties 2 5 and described in the statement of Lemma 37 Then P is satis able Proof De ne a model 93 D7v7X for 3 as follows i D 0 ii a vpi T if and only if pl 6 F b uPLc1cn T if and only if Ping 0n e r iii xc c for each c E 0 Let P be the property of being a sentence A such that UgmA T if and only if A E W We prove7 by a variant of formula induction7 that every sentence of has property P ia Sentence letters have P because Ugjtpi vpi ib Atomic sentences Pincl on have P because vanPL01cn Pl 7 X 317 an UMP 017 7 ii and iii The proof that A has P if A has P and that A V B has P if A and B have P are just like the corresponding steps of the proof of Lemma 18 34 iv Let A be a formula with no free occurrences of variables other than the variable m Assume that for every 0 E 0 Az c has P We prove that VmA has P Ug VmA T iff for all sv A T iff for all c E 0 for all s with sz c 1233A T iff for all c E 0 vmAm c T iff for all c E 0 Az c E F iff VmA E T The rst iff77 is by the de nition of um and the fact that no variable besides z occurs free in A The second iff77 is by the fact that no variable besides z occurs free in A and the fact that D 0 The third iff77 is by the fact that xc c for each c E 0 The fourth iff77 is by the fact that the sentences Az c have property P To see that the if part of the last iff77 holds assume that VmA E F and that for some 0 E 0 Amc P By 3 Amc E P Thus VzA Az 0 is a nite subset of P But this subset is not satis able contradicting The only if77 part of the last iff77 holds by Since in particular 1293A T for every member of A of P we have shown that F is satis able Theorem 39 Compactness Let P be a nitely satis able set of sen tences of C Then P is satis able le true in a model for C Proof By Lemma 37 let F have properties 174 of that lemma By Lemma 38 F is satis able Let 931 be a model for C in which F is true By 1 P is true in 931 We can turn 931 into a model for C in which P is true by throwing away the part of the X of F that assigns objects to the constants in 0 that do not belong to 0 The resulting model 93 is called the reduct of 931 to D Corollary 310 Compactness Second Form Let P be a set of sen tences of C and let A be a sentence such that P A Then there is a nite subset A ofP such that A A Proof The proof is just like that of Corollary 110 D 35 Exercise 35 For each of the following pairs l 7 A7 tell whether P 51 A Prove your answers a P V111 P11117 VU1P139U1 131112 A P1112 b P Vvl Plvl gt po7 VUg P1112 gt p0 A vaPlvg V 3111 P1111 Exercise 36 Let F be a set of sentences having properties 2 and 3 described in the statement of Lemma 37 Show that W is Henkin if and only if7 for each formula A and each variable x if iii below holds7 then iv also holds iii 325A 6 Pt iv Az c E W for some 0 E 0 Exercise 37 Let C 071727 7 where7 eg7 7 is the numeral 7 Let 93 D7127 7 where D 012 U truth set P27m7n l m 2 n U P37m7n7p l m n p UP13mnp We 19 X01 71 Let E be the set of all sentences true in 93 Prove that there is a model 931 D7 v 7X such that a E is true in 931 b there is a d E D such that7 for every natural number 71 P27 d7 x n belongs to the v truth set Hint Let 0 C U Describe the set U of sentences involving 0 that need to be true in 931 if c is to be a d Witnessing that b holds Next show that E U H is nitely satis able To do this7 assume that A is a nite subset of H Show that 93 can be made into a model 95 D7 1 2 ofEU A by an appropriate choice of 20 Apply the Compactness Theorem to get a model 931 of E U H Finally let 931 be the reduct of 931 to 3 36 4 The semantics of full rstorder logic In this section we make two additions to the languages D5 of 3 The rst is the addition of a symbol for identity The second is the addition of symbols that are used to denote functions The languages C of predicate logic with identity For each set C of constant symbols we have a language 20 Symbols of C All symbols of De plus the symbol Formulas of C Modify the de nition given on page 24 of formulas of 3 by renumbering clause 6 as clause 7 and adding the following clause 6 If t1 and t2 are variables or constants then t1 t2 is a formula Remark Unique readability holds for C by a proof very similar to the proof that it holds for 3 Models for C Models for C are the same as models for 3 Satisfaction and truth for C The notions of a variable assignment and of denfm are the same as for 3 The de nition of 12ng is the same as that for E C except that there is an extra subclause of the atomic clause i T if dens t1 dens 752 S 7 7 m m 7 C 2mm t2 7 F if denfmt1 75 denfmaZl Satisfaction and truth are de ned as for 3 Logical implication for E C Logical implication validity and satis ability are de ned as for 3 Example The following formulas are valid a U1 111 d 111 v2 gt P1111 lt gt P1112 b V Ul U1 U1 e VU1V U2 U1 U2 H P1111 lt gt 131112 CHU1U1U1 fv1cgtcvggtvlvg The proof of the Compactness Theorem for C is similar to that for 3 but there is one important difference as we shall see 37 Lemma 41 LetP be a nitely satis able set of sentences of 20 and letA be a sentence of 20 Then either PU A is nitely satis able or PU A is nitely satis able Proof The proof is exactly like that of Lemma 36 D Lemma 42 Let P be a nitely satis able set of sentences of E G Let C be a set gotten from C by adding in nitely many new constants There is a set P of sentences of E Ct such that 1 P Q 1 2 P is nitely sati able 5 for euery sentence A of 20 either A belongs to P or A belongs to P 4 P is Henhin Proof The only change we have to make in the proof of Lemma 37 is that we must specify an alphabetical order for the symbols of C Let us do this by letting the new symbol come immediately after V Lemma 43 Let P be a set of sentences of a language 20 hauing prop erties 2 5 and described in the statement of Lemma 42 Then P is satis able Proof We wish to begin as we did in the proof of Lemma 38 by using P to de ne a model for C But we must not de ne the model as we did before on page 34 To see this assume that we did use the old de nition Let c1 and cg be two distinct members of 0 and suppose that the sentence c1 cg belongs to l as is possible Since xc1 c1 XltCzgt cg and c1 and Cg are distinct objects the new clause in the de nition of 12ng implies that UgjtltCl cg F Thus it is not the case that for all formulas A 129314 T if and only if A E P But for the proof of Lemma 38 it was critical that this was the case If we are to de ne a model for which it is the case then we must make sure that if c1 Cg E 1 then xc1 X62 A 2 place relation R on a set X is an equivalence relation on X if and only if all three of the following conditions are satis ed a R is reflexive Rzz holds for all z E X 38 b R is symmetric if z E X and y E X and Fay holds then Rym holds c R is transitive if z E X y E X z E X and both Fay and Ryz hold then Rmz holds If R is an equivalence relation on X then R divides X up into equivalence classes For m E X let mR the equivalence class ofz with respect to R be de ned by MR y E X 1 Pay holds Let R be the relation on 0 de ned by R6162 holds iff C1 Cg E l We shall prove that R is an equivalence relation on 0 For re exivity we must show that C C belongs to W for all members C of 0 Assume that C C F By property 3 of l C 7 C E l where we use t 7 t as an abbreviation for t t But then C 7 C is a nite subset of F that is not satis able contradicting For symmetry we must show that for all members C1 and Cg of 1 if C1 Cg E 1 then Cg C1 6 F Assume that C1 Cg E F but cg C1 F Using 3 we get that C1 cg cg 7 C1 is a nite subset of F Once again we contradict For transitivity we must show that for all members C1 cg and C3 of 1 if C1 Cg E W and Cg C3 6 1 then C1 C3 6 F Assume that C1 Cg E W and Cg C3 6 F but C1 C3 F By 3 C1 CgCg C3C1 7 C3 is a nite subset of l contradicting De ne a model 93 D UX for C as follows lt1 D MR 1 c6 0 n a up b M iii XC CR for each C E 0 T if and only if p E F 71 l C1R CnR T ifand only if PinclCn E F To see that iib is a genuine de nition we need to show that the truth value it assigns does not depend on the choice of representatives Cj of the equivalence classes To show this assume that CAR C jlg for 1 g j g it By the de nition of the equivalence classes we have that RCjCj holds for 1 g j g it By the de nition of R we get that the sentence Cj C belongs J to W for 1 g j g n We must show that PinclCn E P if and only if 39 Pine1 0 E P For the only if77 direction assume that Pincl on E F and that Pine1 43 P By 3 Pinc 1 43 E P Thus n 71 PiclcnPiclcclclcn n is a nite subset of P By 2 it is satis able This is a contradiction The if direction is similar Let P be the property of being a sentence A such that Ug A T if and only if A E F We prove by the same variant of formula induction as we used in the proof of Lemma 38 that every sentence of E C has property P There are only two cases that are signi cantly different from the corre sponding cases in the proof of Lemma 38 so we omit the other cases ic Atomic sentences 1 62 have P because U9301 02 T iff X01 X02 iff CilR 0le iff C1 62 E 18 iv Let A be a formula with no free occurrences of variables other than the variable m Assume that for every 0 E 0 Az c has P We prove that VmA has P UngxA T iff for all s Ug A T iff for all c E 0 for all s with 5z MR 1233A T iff for all c E 0 vmAmc T iff for all c E 0 Az c E P iff VmA E 18 The rst iff77 is by the de nition of 1ng and the fact that no variable besides z occurs free in A The second iff77 is by the fact that no variable besides z occurs free in A and the fact that D MR l c E 0 The third iff77 is by the fact that xc 0 for each c E 0 The fourth iff77 is by the fact that the sentences Az c have property P The proof that the fth iff77 holds is exactly the same as the corresponding step in the proof of Lemma 38 Since in particular Ug A T for every member of A of P we have shown that F is satis able The proof of the two 00mpactness Theorems that follow are just like the proofs Theorem 39 and Theorem 310 40 Theorem 44 Compactness Let P be a nitely satis able set of sen tences of 20 Then T is satis able ie true in a model for 20 Corollary 45 Compactness Second Form Let P be a set of sen tences of C and let A be a sentence such that P A Then there is a nite subset A ofP such that A A Exercise 41 Exhibit a sentence of 0 that is true in every model with exactly three elements and is false in all other models Exercise 42 Tell which of the following sentences of E C are valid If a sentence is valid explain brie y why If it is invalid give a model in which it is false a V111 c c c Vu1P1u1 gt 3112111 112 A 131112 b Vu1Vu2P2u1u2 gt Vu1Vu2 U1 112 d Vu1P1u1 gt Vu2P1u2 gt U1 112 The languages E of full rstorder logic For each set C of constant symbols we have a language g Symbols of E All symbols of all symbols of C plus n place function letters for each n 2 1 Terms of EC 1 Each variable or constant is a term 2 For each n and i if t1 tn are terms then Fftl tn is a term 3 Nothing is a term unless its being one follows from 172 Example of a term FEFZZCFOIMUGFOIC Remarks a As we shall see terms are expressions that in a model and under a variable assignment denote a member of the domain of the model The terms of 3 and E C areilet us retroactively specifyithe variables and constants Variables and constants are the atomic terms of a language The new ingredients of EC are the complex terms given by clause 2 above 41 b Just as we can do proof by formula induction and de nition by recur sion on formulas so we can do term induction and de nition by recursion on terms In proving by term induction that all terms have a property P we must 1 show that all variables and constants have P and 2 show that whenever t1 tn are terms that have P then Fftl tn has P Formulas of E Replace clauses 2 and 6 in the de nition of formulas of C by the following clauses 2 For each n and i if t1 tn are terms then Pintl tn is a formula 6 If t1 and t2 are terms then t1 t2 is a formula Note that with our retroactive de nition of term for 3 and C the new clauses 2 and 6 have the same meaning as the old 2 and Remark The proof of unique readability for formulas of E has a pre liminary step One rst needs to prove Unique Readability for Terms This states that every term is either a variable or constant or else is Fftl tn for unique n i and t1 tn The rest of the proof of unique readability for formulas is similar to the proof for the other languages Models for E A model for E is a triple 93 D u x satisfying conditions and ii in the de nition of a model for C and satisfying the following condition iii X is a function that assigns a a member of D to each constant b a member of D to each n 1 tuple of the form d1 dn for all dn members of D Satisfaction truth and logical implication for E The notion of a uariable assignment is the same as for 3 and E C The de nition of denfm for the other languages has to be extended so that denfmt is de ned for all terms t The de nition is by recursion on terms 1 denfmt st ift is a variable and denfmt xt ift is a constant 42 2 denfmF t1tn xF denfmt1 denfmtn The de nitions of satisfaction truth logical implication ualidity and satis ability are word for word the same as for E C The proof of the Compactness Theorem for ET is very much like that for E C We list the lemmas and indicate the ways the proofs of the analogous earlier lemmas are to be modi ed Lemma 46 Let P be a nitely satis able set of sentences of ET and let A be a sentence of ETCL Then either P U A is nitely satis able or P U A is nitely satis able Lemma 47 Let P be a nitely satis able set of sentences of ETCL Let C be a set gotten from C by adding in nitely many new constants There is a set P of sentences of ET such that I P Q P 39 2 P is nitely sati able 5 for euery sentence A of 3 either A belongs to P or A belongs to P 4 P is Henkin Proof The only change we have to make in the proof of Lemma 42 is that we must specify an alphabetical order for the symbols of 0 Let us do this by letting the new symbols come after the symbols of E Ci ordered rst by superscript and then by subscript Lemma 48 Let P be a set of sentences of a language L hauing proper ties 2 5 and described in the statement of Lemma 47 Then P is satis able Proof We need to make two additions to the proof of Lemma 43 First we let XFln7 lcllR77lCan lClR iff W01 C 6 PT It fairly easy to see that the de nition does not depend on the choice of elements of equivalence classes It is also easy to showiand we need to do soithat for all c1 cn there is a c such that chl on c E F 43 We also need to change clause iib to make it analogous to the clause above The other change we have to make is in the atomic cases and of the proof that all formulas have property P Before considering the proofs of these facts we rst prove another fact that we will need in these proofs Say that a term 25 containing no variables has property Q if and only if for every 0 E 0 if dengmt 0 then if c E l where dengmt is the common value of the denfmt We prove by a variant of term induction that all terms without variables have Q 1 lft is a constant then dengmt 213 By de nition of MR 25 0 belongs to P if and only if 25 MR Thus if has Q 2 Assume that 251 tn have Q and let t be Fintl tn Let dengmt cllg for 1 g i g 71 Since the ti have Q the sentence ti 0 belongs to W for each i Let dengmt MR By the de nition of denim it follows that dena Fz Ci Gn XltltFin7 31le 7 lcan dengmF t1 tn dengmt lclR By the de nition of UF 01R onR we have that Final quoton 0 belongs to F Assume that Fintl quottn c does not belong to F By property 3 of l Fintltn 7 0 belongs to F Since 25 c E W for every 2 the set 751 cl tncn Finclcnc Fintpntny c is a nite subset of F This set is not satis able and so we have contradicted property 2 of F In doing so we have shown that t has Q Now we are ready for cases and of the property P proof Let dengytlttigt cllg for 1 g i g 71 Since the ti have Q ti Ci 6 W for each i vgmP t1tn T iff vPLdengjtt1 dengmtn T iff Pl 7 01lR77 we T iff Pincl 6 Pk iff P t1t 6 P where the last iff is by properties 2 and 3 of F The proof for case is similar and we omit it D 44 Theorem 49 Compactness Let P be a nitely satis able set of sen tences of E Then P is satis able 239e true in a model for E Corollary 410 Compactness Second Form Let P be a set of sen tences of El and let A be a sentence such that P l A Then there is a nite subset A ofP such that A l A Exercise 43 Which of the following sentences are valid For each one7 explain or give the relevant part of a counter model a Hungugcug U1 b V UlV U2 U1 7 v2 gt F1111 7 F1112 gt Vul ugFlug U1 Exercise 44 Give the omitted case in the proof of Lemma 48 45 5 Deduction in FirstOrder Logic The system FOLC Let C be a set of constant symbols FOLC is a system of deduction for the language El Axioms The following are axioms of FOLC 1 All tautologies 2 Identity Axioms a t t for all terms if b 251 252 H At1 H At2 for all terms t1 and 252 all variables m and all formulas A such that there is no variable y occurring in 251 or 252 with a free occurrence of z in A in a subformula of A of the form VyB 3 Quanti er Axioms VmA a Am t for all formulas A7 variables x and terms if such that there is no variable y occurring in t with a free occurrence of z in A in a subformula of A of the form VyB Rules of Inference Modus Ponens MP Quanti er Rule QR provided the variable x does not occur free in A Discussion of the axioms and rules 1 We would have gotten an equivalent system of deduction if instead of taking all tautologies as axioms we had taken as axioms all instances in E ofthe ve schemas on page 13 All instances ofthese schemas are tautologies7 so the change would have not have increased what we could deduce In the 46 other direction7 we can apply the proof of the Completeness Theorem for SL by thinking of all sententially atomic formulas as sentence letters The proof so construed shows that every tautology in E is deducible using MP and schemas 175 Thus the change would not have decreased what we could deduce 2 Identity Axiom Schema a is self explanatory Schema b is a formal version of the Indiscemibility of Identicals7 also called Leibniz s Law 3 The Quantifer Axiom Schema is often called the schema of Uniuersal Instantidtion lts idea is that whatever is true of a all objects in the domain is true of whatever object t might denote The reason for the odd looking restriction is that instances where the restriction fails do not conform to the idea Here is an example Let A be 3122121 7 122 let x be U1 and let t be 122 The instance of the schema would be Vu13u2 U1 7 112 gt 3112112 7 U2 The antecedent is true in all models whose domains have more than one element7 but the consequent is not satis able MP Modus ponens is the rule we are familiar with from the system SL QR As we shall explain later7 the Quanti er Rule is not a valid rule The reason it will be legitimate for us to use it as a rule is that we shall allow only sentences as premises of our deductions How this works will be explained in the proof of the Soundness Theorem Deductions A deduction in FOLC from a set P of sentences is a nite se quence D of formulas such that whenever a formula A occurs in the sequence D then at least one of the following holds 1 AET 2 A is an axiom A 3 A follows by modus ponens from two formulas occurring earlier in the sequence D or follows by the Quanti er Rule from a formula occurring earlier in D A deduction in FOLC of a formula A from a set P of sentences is a deduction D in FOLC from P with A on the last line of D We write P FFQLC A and say A is deducible in FOLC from P to mean that there is a deduction in FOLC of A from F We write FFQLC A for Q FFQLC A 47 Announement For the rest of this section we shall omit subscripts FOLC and phrases in FOLC77 except in contexts where we are consid ering more than one set C In order to avoid dealing directly with long formulas and long deductions it will be useful to begin by justifying some derived rules Lemma 51 Assume that P F Aiforl 1 n andA1An51B Then T F B See page 30 for the de nition of 51 Proof If we string together deductions witnessing that P F A for each i then we get a deduction from P in which each A is a line The fact that A1 An 51 B gives us that the formula A1HA2HA7LgtB is a tautology Appending this formula to our deduction and applying MP n times we get B D Lemma 51 justi es a derived rule which we call SL A formula B follows from formulas A1 AL by SL iff A1 An l51 B Lemma 52 IfF F A then P F VzA Proof Assume that P F A Begin with a deduction from P with last line A Use SL to get the line P0 V upo H A Now apply QR to get p0 V po a VzA Finally use SL to get VzA D Lemma 52 justi es a derived rule which we call Gen A VxA Lemma 53 For all formulas A and B F VxA gt B gt VmA gt VmB Gen Proof Here is an abbreviated deduction 1 VmltA gt B gt A gt B QAX 2 VxA gt A QAX 3 VmA gt B A VxA gt B 12 SL 4 VmA gt B A VxA gt VzB 3 QR 5 VxA gt B gt VmA gt VxB 4 SL 48 Lemma 54 For allformulas A F HmVyA gt VszA Proof Here is an abbreviated deduction 1 VyA a A QAx 2 AAHavyA 1SL 3 Vz A a VyA 2 Gen 4 Vz A a VyA a Vm A a Vz VyA Lemma 53 5 Vm A gt Vz VyA 34 MP 6 Vm VyA gt Vz A 5 SL HmVyA gt HmA 7 HmVyA gt VyHmA 6 QR Exercise 51 Show that F 3121 P1121 a 3122 P1122 Exercise 52 Show that V121 P1121 F 3121 P1121 Lemma 55 If r F A a B then r F VzA a V B Proof Start with a deduction from P with last line A a B Use Gen to get the line VmA a B Then apply Lemma 53 and MP D Theorem 56 Deduction Theorem Let P be a set of sentences let A be a sentence and let B be a formula IfP U A F B then P F A gt B Proof The proof is similar to the proof of the Deduction Theorem for SL Assume that P U A F B Let D be a deduction of B from P U We prove that P F A a C for every line C of D Assume that this is false Consider the rst line C of D such that P V A a C Assume that C either belongs to P or is an axiom Then T F C and A a C follows from C by SL Hence P F A a C Assume next that C is A Since A a A is a tautology7 P F A a A Assume next that C follows from formulas E and E a C by MP These formulas are on earlier lines of D than C Since C is the rst bad line of D7FFAHEandFFAHEHC Since A n EL A n E A CD Fs1A H C 49 P h A gt C Finally assume that C is E a VmF and that C follows by QR from an earlier line E a F of D Since C is the rst load line of D P k A a E a Starting with a deduction from P of A a E a F we can get a deduction from P of A a E a VmF as follows it AgtEgtF n1 AAEgtF nSL n2 AAEgtVF nngR n3 AgtEgtVzF n2SL Note that the variable x has no free occurrences in A because A is a sentence and we know that it has no free occurrences in E because we know that QR was used in D to get E a VmF from E a F This contradiction completes the proof that the bad line C cannot exist Applying this fact to the last line of D we get that P k A a B D A set P of sentences of E is inconsistent in FOLC if there is a formula B such that P FFQLC B and P FFQLC B Otherwise P is consistent Theorem 57 Let P and A be sets of sentences let A and A1 An be sentences and let B be a formula 1PUAF B ifand only ika AH B 2 PUA1An hB ifand only ika A1 gt gtAngtB 5 P is consistent if and only if there is some formula C such that P l7 C 41fPthorallCEA andifAkB thenPkB Proof The proof is like the proof of Theorem 22 except that we may now use the derived rule SL instead of the particular axioms and rules of the system SL A system S of deduction for E is sound if for all sets P of sentences and all formulas A if P kg A then P l A A system S of deduction for E is complete if for all sets P of sentences and all formulas A if P l A then P kg A Remark These de nitions are like the de nitions of soundness and com pleteness of systems for E except that the new de nitions require P to consist of sentences not just formulas We hereby make the analoguous de nitions for our other languages Theorem 58 Soundness The systems FOLC are sound Proof The proof is similar to the proof of soundness for SL Theorem 24 Let D be a deduction in FOLC of a formula A from a set P of sentences We shall show that for every line C of D P l C Applying this to the last line of D this will give us that P l A Assume that what we wish to show is false Let C be the rst line of D such that P t C The cases that C E P that C is an axiom and that C follows by MP from earlier lines of D are just like the corresponding cases in the proof of Theorem 24 The only remaining case is that C is B a VmE and C follows by QR from an earlier line B a E of D Since C is the rst bad line of D P l B a E Let 9 D UX be any model and let 3 be any variable assignment We assume that U5XP T ie that T for each H E P and we show that y B a VmE T For this we assume that y B T and we show that yg WzE T Let 1 be any element of D and let 3 be any variable assignment that agrees with 3 except that sm d We must show that T Since P is a set of sentences 12531 T Since the variable x does not occur free in B v tB T Since r p B a E it follows that 1153E T Lemma 59 Let L be a set of sentences of El consistent in FOLC and let A be a sentence of ETCL Then either L U A is consistent in FOLC or L U A is consistent in FOLC Proof The proof is like that of Lemma 25 D Lemma 510 Let L be set of sentences of El consistent in FOLC Let C be a set gotten from C by adding in nitely many new constants There is a set L of sentences of Eli such that 1 P Q 1 2 L is consistent in FOLm 39 5 for every sentence A of 3 either A belongs to L or A belongs to L 4 P is Henkm Proof Let 0001132 be all the constants of 3 Let A07 A171427 A37 be the list de ned in the proof of Lemma 47 of all the sentences of Eli As in that proof we de ne by recursion on natural numbers a function that associates with each natural number n a set D of formulas Let P0 P As in the proofs of Lemmas 37 42 and 47 we shall make sure that for each n at most two sentences belong to BL but not to BL As in the earlier proofs it follows that for each 71 only nitely many of the new constants occur in sentences in Tn We de ne Ln from D in two steps For the rst step let P D U An if D U An is consistent in FOLm D U An otherwise Let D Pl unless both of the following hold a An 6 Pg b An is Vann for some variable zn and formula B Suppose that both a and b hold Let in be the least i such that the constant oi does not occur in any formula belonging to KL Such an i must exist since only nitely many of the in nitely many new constants occur in sentences in Pg Let Pn1 U 3 Let 1 U Tn Because P LO Q l W has property We prove by mathematical induction that D is consistent for each 71 F0 ie F is consistent in FOLC by hypothesis but we must prove that it is consistent in FOLm Observe that any deduction D from P in FOLm of a formula of E can be turned into a deduction from P in FOLC of the same formula just replace the new constants occurring in D by distinct variables that do not occur in D It follows easily that P is inconsistent in FOLC if it is inconsistent in FOLm Assume that D is consistent in FOLm Lemma 59 implies that Pl is consistent If D Pg then D is consistent Assume then that D 52 PU Bnmn 0 and7 in order to derive a contradiction assume that Ln is not consistent By Theorem 577 every formula of E is deducible from Ln in FOLm Hence Ln l FOLC p0 A po In other words7 PL U uBMmm CM FFOLO 190 A pm By the Deduction Theorem7 PL FFOLO anWmcm H 190 A W90 Let D be a deduction from P in FOLm with last line Bnmncin a po A p190 Let y be a variable not occurring in D Let D come from d by replacing every occurrence of oi by an occurrence of y Since oi does not occur P or in Bm D is a deduction from P in FOLm with last line Bnzny a po A po We can turn D into a deduction from P in FOLm with last line anBn a po A po as follows n T Bnniy gtp0ATp0 n1 upoA poH nmw nSL n2 TltFOATPOHVann n1QR n 3 VyBMxn y H Bn QAX n4 p0A p0 AB n2n3SL n5 p0A p0 HanBn n4gQR n 6 anBn gt p0 A po n 5 SL This shows that P l FOLC anBn a pOA po But P PU Vann so it follows that P l FOLC p0 A po By SL7 we get the contradiction that UL is inconsistent in FOLm As in the proof of Lemma 267 the consistency of all the Ln implies that consistency of W Hence W has property Because either An or HA belongs to BL for each n and because each Ln Q l 7 W has property lf An l 7 then An BL and so HA 6 Ln But this implies that Bnzn Ci 6 Ln Q P if An anBn Hence W has property D Exercise 53 Show that VU1V U2P2 U1 U2 V P2U2U1 b V UlPZ Ul Ul 53 Exercise 54 Show that F Vv nglvl U2 Exercise 55 Let 1 and 02 be constants Show that cl 02 F 02 cl Lemma 511 Let P be a set of sentences of a language E having prop erties 2 3 and described in the statement of Lemma 510 Then P is satis able Proof We rst note a useful fact about F T For all sentences A of 3 if F F A then A E F To see why holds assume that W F A but A F By 3 5A E F Thus W F 5A contradicting Remark Though we did not state it the analogue of held for the set F of Lemma 27 As in the proofs of Lemmas 43 and 48 we shall de ne a model whose domain is a set of equivalence classes of constants As in the proof of Lemma 43 let R be the relation on 0 de ned by R6162 hOldS iff Cl 62 6 FL We shall prove that R is an equivalence relation on 0 For re exivity we must show that c 0 belongs to W for all members 0 of 0 Since 0 c is an instance of Identity Axiom Schema a F c c and so FFec By T 0061 For symmetry we must show that for all members 01 and 02 of 1 if 01 02 E 1 then 02 01 E W Assume that 01 02 E F By Exercise 55 P F 62 61 By 62 61 6 PL Before proving transitivity we show that Cl 02 0263 F C1 63 for any constants 01 02 and 03 1 01 02 Premise 2 62 Cg Premise 3 02 01 1 Exercise 55 4 02 cl gt CZ 03 gt cl Cg ldAXb 5 Cl Cg 234 SL For transitiVity7 we must show that7 for all members 01 02 and 03 of l 7 if 01 62 E W and 62 Cg E l 7 then 01 Cg E F Assume that 01 02 E W and 02 03 E F By what we have just proved7 W F 01 03 By Cl Cg E P We de ne a model 93 D7127 x exactly as in the proof of Lemma 487 that is ii a pi T if and only if pi E F b v i 013 onR T if and only if Ping 0 E F iii a xc 0 for each c E 0 b Fi 7 013 onR 0 if and only if Final on c E F We must show that the de nitions given in clauses iib and iiib do not depend on the choice of elements of equivalence classes In the case of clause iiib7 we need to show something additional See below A special case of the proof that clause iiib is independent of the choice of elements of equivalence classes is Exercise 567 and the proof for the general case is merely an elaboration of the proof for the special case The case of iib is a bit simpler The additional fact we to show concerning clause iiib is that7 for all F1 and all 01 cm that there is a c such that Finclcnc E 1 Suppose there is no such 0 By property 3 of l 7 Finclon7c 6 P5 By property 4 of l 7 VvlFinclcn 7 U1 6 P5 Since Vvlfgnclon vl E P gt chlcn7 F clcn 55 is an instance of the Quanti er Axiom Schema P hFinclcn But chl on 7 Final on is an instance of Identity Axiom Schema a and so P is inconsistent contradicting property 2 of P Let P be the property of being a sentence A such that Ug A T if and only if A E W As in earlier proofs we use a variant of formula induction to show that every sentence has property P The case of atomic sentences is like that case in the proof of Lemma 48 except for one change Recall that in proving atomic cases and ic we rst used a variant of term induction to demonstrate that all terms without variables have property Q where t has property Q if and only if for every 0 E 0 if dengmt 0 then if c E W In the course of this demonstration we got a contradiction from the assump tion that A Q l where At1cltnometltncF clon7 c This assumption contradicted the hypothesis that W was nitely satis able What we need to show in our new context is that it contradicts the hypoth esis that W is consistent Obviously A F Final cn 7 0 Thus it is enough to show that A F Final on c 1 t1 01 Premise n tn on Premise 77 1 t1 Cl gt Ft1t2tn1tn C H Fncltgtn1tn C 2n 2an Fincch cn1tn c gt F Cng on1 c ldAxb 2n1 Finclcnc 12nSL Cases cases ii and iii of the proof that all formulas have property P are like the corresponding cases in the proof of Lemma 27 Case iv is like the corresponding case in the proof of Lemma 48 except for one change The last step in case iv proof was to show that for all e E 0 Amc E W iff VmA E W The if part of this iff77 was proved using the fact that W was nitely satis able In the new context we must prove it using the fact that W is consistent To do this assume that VmA E F Notice that for each c E 0 the sentence VxA gt Am c is an instance of the Quanti er Axiom Schema Thus W F Az c By T Az c E F As in our earlier proofs we have in particular that 129314 T for every member of A of l and this means we have shown that W is satis able D Theorem 512 Let P be a consistent set of sentences of ETCT Then P is satis able Proof By Lemma 510 let V have properties 173 of that lemma By Lemma 27 W is satis able Hence P is satis able D Theorem 513 Completeness Let P be a set of sentences of E and let A be a formula of ET such that P A Then T FFQLC A In other words FOLC is complete Proof Since P A for every model 93 and every variable assignment 3 if P is true in 93 then 12534 T Let m1 mn be all the variables occurring free in A Let 9 be any model in which P is true For every variable assignment 3 12314 T This means that Vzl VznA is true in 931 Thus P Vzl VznA Since P Vzl anA PU le VznA is not satis able By Theo rem 512 PU le VznA is inconsistent Let B be a formula such that P U le VznA F B and P U le VznA F B By the Deduction Theorem P F Vz1VznA a B and P F le VznA a B By SL P F le anA Using the Quanti er Axiom Schema and MP n times we get that P F A D Exercise 56 In the proof of Lemma 5117 clause iiib of the de nition of the model 93 says that xFn01RcnR clg iff W61cnc P Show7 in the special case n 2 and i 07 that this de nition does not depend on the choice of elements of equivalence classes In other words7 assume that 1 MR CllR and 0le 3 le 2 F20102 c E P and FZClcZ c E l and prove that 6 The semantics of secondorder logic The languages E of second order logic For each set C of constant symbols we have a language 6 Symbols of 6 All symbols of El plus n place predicate variables Vonv V1n7 V2n7m for each n 2 1 In this section we shall speak of v0v1 as individual variables Remark It is common also to have n place function variables but we omit them in the interest of simplicity Terms of E The de nition of terms is the same as that for El Formulas of E Modify the de nition of formulas of E by changing clauses 2 and 5 as follows 2 For each n and i if t1 tn are terms then Pintl tn and Vintl tn are formulas 5 If A is a formula and X is an individual or predicate variable then VXA is a formula Models for 3 Models for E are the same as models for El Truth and logical implication for E For each model 93 D v x a variable assignment is a function 3 that assigns an element of D to to each individual variable and an n place relation on D to each n place predicate variable To the de nition of denim we add the stipulation that denfm for all n and i The de nition of vg is the same as that for except for two changes First there is an extra subclause of the atomic clause i d vg Ltl tn T if and only if denfmV den jtt1 denfmtn holds Second clause iv needs to be reinterpreted so that the variable x can be of either kind The de nition of a free occurrence of a variable is as before except that it now applies to both kinds of variables Satisfaction and truth are de ned as for and so are logical implication validity and satis ability Consider the following sentence of 6 HVZWU UglZvlvg A VU1VU2V2 U1 U2 gt Vzvgvl A VU1VU2VU3V2 U1 U2 A VZ UZ US gt V2U1U3 Call this sentence lnf The solution to Exercise 33 shows that lnf can be true only in a model with an in nite domain Conversely lnf is true in every model with an in nite domain This is because every in nite set can be linearly ordered in such a way that there is no greatest element If the domain D of 93 is in nite then lnf is shown to be true in 93 by the variable assignment that assigns such a linear ordering of D to V2 Theorem 61 Compactness fails for 6 Proof For n 2 2 let Bn be the following sentence of El and so of EI UlE Un U1 U2 A A 1117311 A Ugy vg AA Un1vn There is a conjunct v 7 127 for all i and j such that 1 g i lt j g For each n B is true in all models whose domain has size 2 n and it is false in all models whose domain has size lt n Let P lnf U B2 B3 B4 Clearly P is not satis able The theorem will be proved if we can show that P is nitely satis able Let A be a nite subset of P Let n be the largest number such that Bn 6 A If 93 is any model whose domain is nite and has size 2 n then A is true in 93 Remark Since compactness holds for E there can be no sentence like lnf in and so also there is no sentence like lnf in El Indeed there is no set of sentences in E that does what lnf does Exercise 61 Prove that there is no set E of sentence of El such that E is true in every model with a nite domain and false in every model with an in nite domain Hint Consider the union of E and the set of all the B 60 GALOIS DEFORMATION AND INVARIANT HARUZO HIDA 1 LECTURE 2 The notation is as in the rst lecture F a totally real eld7 p gt 2 is a xed prime For simplicity7 we assume that p splits completely in FQ We start with a Galois representation pp GalF a GL2W associated to a Hilbert modular form on GL2F with coef cients in W We assume the ordinarity of pp pFlDw g op 02 With n 0417 gle Nkil and CYFUF 1 on the decomposition group and the inertia group Ip C Dp C GalQF for all prime factor p of p in F Here NU E Z is the p adic cyclotomic character with exp eXpN2LZM for all n gt 0 and k gt 1 is an integer Again for simplicity7 we assume that p is unrami ed outside p We consider the universal nearly ordinary couple Rp GalF a GL2R considered in the rst lecture where R is a pro Artinian local K algebra The couple R7 p is universal among Galois deformations pA GalF a GL2A for Artinian local K algebras A with AmA K such that K1 unrami ed outside p K2 pAlGalpFp 3044 with em E 04 mod 111A and the local cyclotomy condition ifp does not split completely in F K3 detlt Agt det 9F K4 pA E pp mod 111A Recall Pp 1pr 7 AL GalltFpprFp ldentify WHPFH with WHXFH by 7 lt gt 1Xp Since PloaipFp g 3 5 6304l Pp a R induces an algebra structure on R over WHXFH Thus R is an algebra over KHXFHMP Here is the theorem we have seen in the rst lecture Theorem 11 Derivative Suppose R KHXFHMP Then ifltp o p pp far the lacal Artm symbal pFp FTObp we have 66nlP7Fnl 6 Land Adpp Adpp det X 1X70HlongWMlvanl w Greenberg proposed a conjectural recipe of computing the invariant When V Adpp7 his de nition goes as follows Under some hypothesis7 he found a Date August 7 2008 The second lecture 90 minutes at TIFR on August 17 2008 The author is partially supported by the NSF grant DMS 02444017 DMS 0456252 and DMS 0753991i 1 GALOIS DEFORMATION AND L INVARIANT 2 unique Eibspace H C H1FAdpp of dimension 6 represented by cocycles c GalQF a Adpp such that 1 c is unrami ed outside p 2 c restricted to Dp is upper triangular after conjugation for all plp By the condition 2 clIp modulo upper nilpotent matrices factors through the cyclo tomic Galois group GalltQpprQp because Fp Q17 and hence chp modulo upper nilpotent matrices becomes unrami ed everywhere over the cyclotomic Zp extension FooF so the cohomology class c is in Sele Adpp but not in SelFAdpF Take a basis cph p of H over K Write 7aa i 60 lt 0 LAW for 039 E Dpr With any p lp Then an DP a K is a homomorphism His invariant is de ned by ltAdltpFgtgt det aplvaF lpp p10gp YF 71aFl YF 7FP lPP lp71gt The above value is independent of the choice of the basis cub As we remarked in the rst lecture assuming the following condition ns p p mod 111W has nonsoluble image by using basically a result of Fujiwara and potential modularity of Taylor plus a very recent work of Lin Chen we have R E KHXFHMP The following conjecture for the arithmetic L function is almost a theorem except for the nonvanishing Adpp 31 0 see HMI Theorem 527 combined with 526 there Conjecture 12 Greenberg Suppose ns Let Mithnn F07 LsAdpF ltIgtZrith yl 9 71 then LsAdpp has zen 0f Order equal t0 6 and far the canstnnt Adpp E KX speci ed by the determinant as in the thearem we have L7 sAd gig ltAdltppgtgtise1QltInd Adwm 1 KQ If with the identity is up t0 units The factor 8Adp does not show up in the above formula lf pp is crystalline at p writing SFAdpF for the Bloch Kato Selmer group HFAdp we have sawing Adppl1 WP 8AdpplSFAdppl1KQpl up to units and the value lSFAdpFl1KQpl is directly related to the primitive complex L value L1Adpp up to a period see MFG page 284 In the following section we describe the Selmer group and how to specify H 11 Greenberg s Selmer Groups Write FpF for the maximal extension un rami ed outside p and 00 Put 5 GalFpF and 6M GalFpM Let V Adpp We x a W lattice T in V stable under 5 Write D Du C 5 for the decomposition group of each prime factor plp Choosing a basis of pp so that pFlD is upper triangular we have a 3 step ltration ord V 3 fgv 3 tV 3 0 GALOIS DEFORMATION AND L INVARIANT 3 where fp V is made up of upper triangular matrices and fV is made up of upper nilpotent matrices7 and on fVV D acts trivially getting eigenvalue 1 for Frobp Since V is self dual7 its dual V1 HomKV7 K N again satis es ord Let MF be a sub eld of F077 and put 6M GalFpM We write p for a prime of M over p and q for general primes of M We put V LVKR HWIV 1447 n er SS in H vav De ne for the image LpVT of LpV in H1M7 VT 1 11 SelMA KerH1Q MA a H W for A V VT p F The classical Selmer group of V is given by SelMVT We de ne the 7 Selmer group replacing LFA in the above de nition by 7 V LP V KerRes H1M V gt H1I m Lemma 13 Vanishing Suppose R g KHXFHMP Then SelV g HomKmRm 3 K and SelpV 0 Ppoof We consider the space DerKR7 K of continuous K derivations Let Kle Ktt2 for the dual number 8 t mod t2 Then writing K algebra homomor phism b R a Kle as 150quot 1500 1r8 and sending to to 151 E DerKRK7 we have HomKalgRK8 E DerKRK HomKmRm 3K Note here that 151 By the universality of Pup7 we have 2 p GalQF a GL2K8lp satis es the condtions K1 4 HomKalgR7 Pick p as above Write po p0o p10398 Note here again p1 Then 6 plp l can be easily checked to be a 1 cocycle having values in M2K D V Since detp detpp Trcp 07 6 has values in V By the reducibility condition K27 cpl E SelV We see easily that p E p gt cpl opl We can reverse the above argument starting with a cocycle 6 giving an element of SelV to construct a deformation pc with values in Thus we have p GalF a GL2K8llp satis es the condtions K1 4 N 2 SelV Since the algebra structure of R over WHXFHMP is given by Spozgl the K derivation 6 R a K corresponding to a K8 deformation p is a WHXpH derivation if and only if p GaKFWFM 3 3 which is equivalent to cpl E SelFV7 because we already knew that Trcp 0 Thus we have SelFV DerWHXpMR K 0 D If ple is isomorphic to lg 877 for a nite order character 77 of DF and a cocycle E Dp a K1 of the form 50 limn oo PWFYA for a non unit on E F7 we call p multiplicative at p If p comes from an elliptic curve EF7 E has multiplicative reduction modulo p if and only if it is multiplicative at p We order primes plp so that p is multiplicative at pi if and only ifi S b The number b can be zero GALOIS DEFORMATION AND L INVARIANT 4 We need to have a slightly different de nition of Selmer groups behaving well under Tate duality For each prime q E plp we put 12 i KerH1ijV a H1ij c LMV if q p withj b q Lq V otherwise Once ZqV is de ned7 we de ne fqV1 fqVL under the local Tate duality between H1FqV and H1FqV17 where V1 HomKVQp1 as Galois modules Then we de ne the balanced Selmer group V resp FV1 by the same formula as in 11 replacing LpV resp LFV1 by fpV resp ZFV1 By de nition7 SelFV C SelFV Lemma 14 lsomorphism Let V be AdpE We have H1F V v SI V0 H1 V quot ltgt eFltgt lt gt H LN F117 Proof Since V C SelFV7 the assumption implies V 0 Then the Poitou Tate exact sequence tells us the exactness of the following sequence 7 H1 F V 7 SelpV gt H1c V gt H gt SelpV1 temp L W It is an old theorem of Greenberg which assumes criticality at s 1 that dimFV dimFV1 see G Proposition 2 or HMl Proposition 382 so7 we have the assertion ln HMl7 Proposition 382 is formulated in terms of SelQlnd V and QHndg V1 de ned in HMl 34117 but this does not matter because we can easily verify dlndg E 190 similarly to HMl Corollary 381 D Actually7 for the Selmer group with coef cients in a Galois representation of adjoint type in characteristic 07 we will later prove in the fourth lecture that mam SelpV 2 GREENBERG7S 71NVARIANT Here is Greenbergls de nition of V The long exact sequence of fVV gt Vf fV a Vfp V gives a homomorphism7 noting Fp Q17 and writing 53 G31FnFn7 H1FfVfV Hom abp rpmEV L 111l1FMLV11111 l1Fn7VH H1Fn7VRV E H1In7VfJV Note that Hom al p7 ng fV fVV2 K2 canonically by 45l Yanl b T long 7 lP7Fnl Spectral and Pseudospectral Methods Pascal Getreuer March 14 2008 For my Math 269B nal project I have studied spectral and pseudospectral methods mostly from the book Chebyshev and Fourier Spectral Methods by John P Boyd Boyd7s book is in his words ruthlessly practical77 deferring theory to other texts For my experience the book was to the point and fun to read The rst part of this report explains the fundamentals of spectral and pseudospectral methods based on my notes in reading Boyd7s book The second part demonstrates several numerical experiments using pseudospectral methods 1 Introduction The de ning feature of spectral and pseudospectral methods is to approximate the unknown function with a truncated series expansion under some basis on7 N uNx Z anonw 1 rLO Then we may approximately solve for u by solving for the spectral coc cicnts an Consider the problem Luz fx7 71lt z lt1 2 where L is a linear differential operator Then7 substituting uN for u7 the goal is to choose the spectral coef cients an such that uN approximately satis es the problem That is7 de ning the approrimatiori residual 396 a LUN f7 3 we want to nd an such that R is small7 There are various approaches to making R small The pseudospectral method is to choose a grid of collocation points or grid points i 07 7N and then solve for an such that Rz a Rxia0 i0N W4 0 1 2 3 x which amounts to solving a linear system Using many collocation points encourages Rz a m 0 for all x and under some conditions7 R a 0 uniformly as N a 00 Another way to think of the pseudospectral method is as interpolation we solve for an such that LuN agrees with f at the xi In the Galerkin method and other methods7 there is no grid of interpolation points lnstead7 R is sampled by inner products against test functions77 wi ltwiRa07 i0N Let be a set of Gaussian quadrature points7 then the pseudospectral method is the same as computing the inner products using Gaussian quadrature 11 Basis functions Some desirable basis properties are that the basis is complete has fast convergence small truncation error and that the basis functions are easy to evaluate The standard choices of the basis functions ltpn are Fourier series and Chebyshev polynomials Depending on the problem geometry other bases may be more ef cient for example spherical harmonics when on the surface of the sphere Boundary conditions are not so much an issue for spectral methods In some cases the basis may be chosen such that the boundary conditions are automatically satis ed Otherwise similar to the situation in nite difference schemes boundary conditions impose some of the equations in the linear system when solving for the an 12 Types of Error Spectral and pseudospectral methods have several sources of error 0 Truncation error ETN the error in neglecting the series terms for n gt N o Discretization error EDN the difference between the rst N 1 terms of the exact solution and the N 1 terms computed by the method a Interpolation error EIN for pseudospectral the error from approximat ing functions by interpolations Boyd7s rule of thumb is the assumption of equal errors that ET ED and E1 all have the same order of magnitude So we can estimate the total error from ET By Darboux7s principle the domain convergence and rate of convergence is deter mined by the singularity in the complex plane with the greatest strength That is the worst complex singularity controls the truncation error ET and hence by the assumption of equal errors the total error 2 Galerkin s Method De ne the inner product where w is a nonnegative weight function7 and let be the induce norm Recall that Rz a LuN 7 f The method of mean weighted residuals solves for small R by ltwRltzagtgt o 239 o N 7 for some test functions77 Common choices for wi are wi 6Q 7 Pseudospectral observe ltw Rmagt Rzia Method of moments numerically unstable for N greater than N 6 Leas Least squares so called since this choice for a minimizes HLuN 7 wi Galerkin We shall focus on the Galerkin method Suppose that is an orthonormal basis7 then R has the expansion 13431 Zrnwypna n0 with rna ltltpn7 Rgt The Galerkin method imposes rna 07 or equivalently7 N ltltpi7Rgt 2 m Lltpngt 7 M fgt 0 n0 lf gal is complete7 then R a 0 as N a 00 The Galerkin residual constraints may be expressed as the matrix equation HM filtltPi7fgt 177N1 If the inner products are evaluated with Gaussian quadratures with N 1 abscissas gi7 with 5 xi7 then Galerkin7s method is equivalent to the pseudospectral method using the abscissas as the collocation points So the pseudospectral method inherits the power of the Galerkin method while retaining its simplicity of interpolation This is why pseudospectral methods are so popular 3 Pseudospectral Methods Theorem 1 Gauss Jacobi lntegration If the abscissas are chosen as the zeros of PNH where PNHL is the N 1 degree polynomial of the set of polynomials orthogonal with respect to 4 then the quadrature b N wpfz dx x is exact for all f that are polynomials of degree at most 2N 1 The Chebyshev polynomials Tn are such an orthogonal set for the interval 711 with weight function odd 1x17z2 Thus the roots of the N 1 degree Chebyshev polynomial TNJHL are a smart choice of collocation points since these make accurate quadrature abscissas Recall that pseudospectral methods impose Rpi a 07 which is equivalently the interpolating condition Instead of quadrature abscissas7 another choice of the collocation points is those that minimize interpolation error Theorem 2 Cauchy lnterpolation Error Formula Let PNx be a degree N poly nomial interpolating f E CN1ab at the points then fltN1gtlt gt N fp 7 PNx i 7 for some g 6 ab To minimize interpolation error Hf 7 PNHOO the collocation points minimize N min z 7 u The optimal over the interval 711 are again the roots of the N 1 degree oo Chebyshev polynomial TN m7cos i0N 6 The roots of TN1 are simultaneously the optimal abscissas for quadrature with weight w 1x1 7 x2 and the optimal points in terms of interpolation errorl Thus 6 is an excellent choice for the collocation points In general Boyd7s advice is to choose as the abscissas of a Gaussian quadrature for the basis set For problems on a periodic domain composite trapezoidal and midpoint rules are Gaussian quadratures in that they are exact for trigonometric polynomials of degree 2N 7 2 constant plus the rst N 7 2 cosines plus the rst N 7 2 sines Thus for the periodic case uniformly spaced is the right choice 31 Grid Point Values lt gt Series Coef cients A set of cardinal functions 07 has the property CAM 67 At every grid point xi exactly one of the cardinal functions is one and the rest are zero For orthogonal polynomials 2 where are the roots of ltpN1 the functions x cm Mg 1H j0N 95 1ltPN195739 are a set of cardinal functions Through cardinal functions it is possible to use the pseudospectral method either through the series coef cients an or the grid point values For nonlinear problems it is useful to jump between the two representations For the linear problem Lu f we may solve the problem in two ways series coef cients grid point values and cardinal functions where u f fz and HM WWW Lu LODWD V De ne g by Mij pijwj HogH2 where 10 is the quadrature weight then L For the other direction g il notice that g 71 g so Mi pgxi In other words M71 simply sums the spectral series at the grid points 32 Nonlinear Problems The pseudospectral method adapts easily to nonlinear problems where an is the solution to a nonlinear system solved by Newton7s method for example Alterna tively the Newton Kantorovich method linearizes the differential equation about the current iterate to solve the problem Example from Boyd Um CYU12 emu 0 u0 0 u1 1 Approximate the solution with the quadratic polynomial u2x z 12z2 7 For this simple example there is just one unknown 12 to determine Choosing the collocation point z and setting Rz i 12 0 yields 0 2 7 a22aa2oz0 For 04 1 we obtain u2x z 7 0317z2 7 x which matches very closely to the 71 1 39012 exact solution 4 Numerical Experiments 41 1D Boundary Value Problem For my rst experiment7 I use the pseudospectral method with a Chebyshev basis to solve the one dimensional boundary value problem um 8sin47rzu 71 1171 a u1 B The plot below shows the result using 87 127 and 20 basis functions 8 basis functions We can look at the series coef cients can to get an idea of the truncation error ETN The plot below shows the magnitude of the series coef cients can for 30 basis functions a l Coe iCIent Magnitudes 10 1072 W AV 104e 1076 0 8 12 20 30 n We see that 19 and all have signi cant magnitudes greater than 1027 but an stays below this threshold for n 2 12 This explains why the result using 12 basis functions is much more accurate than the result using 8 basis functions Now7 since it seems that the method is successfully converging to the true solution7 we can estimate the total error by comparing uN to U100 HUN uloolloo 0 84 0 090 Lquot0 Error 100 000090 10 2 10 4 105 l l l i 8 12 30 The L2 error HUN 7 ulOOHZ decays similarly A potential numerical problem is the conditioning of the N gtlt N linear system that must be solved How does the condition number of matrix g vary with N7 Condition Number 3900 104 260 6 70 l l 102 100 i l l l l 8 12 20 30 N The condition number grows quickly with N For N 1007 the condition number is 19 X106 42 Laplace Equation My second experiment applies the pseudospectral method to the Laplace equation on the square 9 711 gtlt 7117 umuyy0 in 711 gtlt 711 u h on the boundary7 where May cos47m if y 1 and lt i and May 0 otherwise I use a tensor product of the basis used in the rst experiment Solution using 202 basis elements y N 39439 C 39W The condition number of g is approximately 5800 The exact solution obtained by mapping the problem into the unit square and ap plying separation of variables is 3072 cos Ek sin2 16 Wu 1 gm m singkz 1 expgky 1 7 1 Comparing against the exact solution7 the Lquot0 and L2 errors are N Lquot0 error L2 error 202 00117 00124 302 00112 00123 402 00093 00097 lncreasing N beyond 202 improves the accuracy only slightly It seems that spectral methods are poorly suited for this particular problem 10 43 Poisson Equation The third experiment is the Poisson equation with forcing function sgnx umuyysgnz in 711 gtlt 711 u 0 on the boundary which should produce a solution that is concave up where z gt 0 and concave down where z lt 0 The pseudospectral computed solution indeed has this behavior Solution using 202 basis elements I found that for this expiment7 the condition number of g is again approximately 5800 This is because the matrix g with entries Hij Leg is the same Unfortunately I dont know the exact solution to this problem7 beyond the observa tion that antisymmetry implies that the solution is zero along the x axis A Code Listing pspecbvpm The following MATLAB code solves the boundary value problem dgumd1umd0uf 71ltxlt1 114 w MD 6 Via the pseudospectral method using a basis of Chebyshev polynomials The code is based on the FORTRAN listing in Boyd7 p 124 function u pspecbvpd2dld0falphabeta a Solve d2 LLXX d1 LLX d0 u f with u7l alpha ul beta Algorithm parameters N Z r NPlot 100 NBasis N 7 2 Number of Chebysnev polynomials Number of plotting points e a a Number of basis functions ijX LPjCEl 0 x1 cos pl 1 NBaSlS 39 NBaSlSl m B x aiphauiexMZ betalx2 BX Bx beta 7 alpha2 B39X g fXl d0xl4BXl 7dlxiBx gf7LB for i l2NBasis x xi i phiphixphixx basis xNBasis Hi d2xphixx39 dlxphix39 d0xphi 39 end a Hg Solve the matriX equation for spectral coefficients 2 linspace7llNPlot for i l2NPlot phi e basisziNBasis 111 phi 39a BZi end pspecpoissonm The following MATLAB code solves the Poisson problem um uyy f in 711 gtlt 711 u h on the boundary Via the pseudospectral method using a basis of ChebysheV polynomials function zu pspecpoissonfhhxxhyy Solves LLXX utyy fXy in llXll with u h on the boundary Algorithm parameters N 22 NPlot 35 NBasis N 7 2 Number of Chebyshev polynomials Number of grid plotting points in each dimension Number of basis functions ijXy ijilil 0 e e 0 xi COSpllNBaSlS 39NBasisl xxyyyl meshgridxixi B xy h7ly 41X2 hiy lx2 hx7l4liy2 hxlly2 7 h7l7l4lix4liy4 e h7ll Alix ly4 7 hl7llxliy4 e hll4lxly4 LapB xy hxmx lyuleywz hxxxl4ly2 hid 14 Mien2 binLy Mum2 fXXIYY LapBxxyy W3 g g Construct the square matriX H for il l2NBasis for i2 l2NBasis y xi i1 x xi i2 phiphixphixx basis xNBasis psipsiypsiyyl baSis yNBasis PthX psi 2 phixx 2 39 Phlyy p51yyph1 39 Hil 1271NBaSls2 dxyPhixx 39 Phiyy 39 end end a Hg Solve the matriX equation for spectral coefficients 2 linspace7llNPlot for il l2NPlot for i2 l2NPlot y 211 x zi2 phi basisxNBasis psi basisyNBasis Phi pSliphli39 uili2 Phi Ra Bxy Sum the series to get u Math 149 W02 BB Cubic B zier curves 1 Overview Bezier curves are a method of designing polynomial curve segments When you want to control their shape in an easy way Bezier curves make sense for any degree but we ll concentrate on cubic ones the most important case Bezier Bay zee ay To specify a cubic Bezier curve you give four points called control points The rst and last are on the curve the middle two may not be When you change the control points the shape of the curve changes It is helpful to indicate the control points by connecting them With line segments to form the control polygon although this is not a polygon in the usual sense as it is not closed Some examples are shown in Figure 1 Figure 1 Some Bezier curves It does not matter Which end you consider to be the rst and Which the last you get the same points for the curve either way Observe that the curve is tangent to the rst and last legs of the control polygon 2 Details The Bezier curve is just a particular linear combination of the control points With time varying coef cients If the control points are P0 P1 P2 Pg then the curve is given by Pt 1 03130 31 021131 31 tt2Pg 3133 for 0 g t g 1 Why these coef cients They arise in a way related to binomial expan sions Recall that 3 33 3321 33152 t3 Now consider these terms individually rather than added together and put 1 t for 3 You get four functions of t called the Bernstein polynomials These are Jam 1 03 11 031 1310 31 31 13205 31 ttquot 30 0112 1330 t3 MILt 3 Thus for a Bezier curve PW Javagt130 Jana1 lumpy 11301 As you Will see the Bernstein polynomials have nice properties that are re ected in the properties of Bezier curves Bernstein polynomials and Bezier curves can be de ned for any degree n by using the expansion of 3 tquot but let s continue to concentrate on the case of degree 3 since that case is most frequently used P1 Figure 2 Example Example Suppose the control polygon has P0 231 1 051 2 1 2 and Pg 21 as in Figure 2 Then P Javagt130 391quot J3 OH lintgt132 11301 1 t32 3 31 005 31 tt2 1 2 15311 2 6t 312 313 3 6t 2712 1913 BB2 In other words PO with 2 it 312 3153 and ya 3 6t 27152 19153 3 Some properties of the cubic Bernstein polynomials 0 Values at 0 and 1 1330 1 1331 0 13710 0 1331 2 0 1320 0 1331 0 0 Unit sum property 1390 131 J3 20 13305 l for all t o Nonnegativity J 2 0 for 0 g t g 1 0 Graphs See Figure 3 Figure 3 Graphs of Bernstein polynomials of degree 3 0 First derivatives at 0 and 1 Mo 3 491 0 1330 3 1331 0 1320 0 1321 3 1330 0 1331 3 Second derivatives at 0 and 1 400 6 401 0 410 12 411 6 z 6 z 12 4130 0 4131 6 0 Maximum property The maximum value of ng ft occurs at t g for k 0123 0 Linear sum property If m an m2 are evenly spaced ie form an arithmetic progression then for all t mis t m1J33 me mg mg the linear function that runs from 770 to as t runs from 0 to 1 Symmetry POT 6 0113 13141 t 733446 Basis Jana 3105 3205 I330 form a basis for the vector space of all polynomials of degree at most three In contrast the standard basis is Lt 152153 Some properties of cubic Be zier curves Let Pt be the Bezier curve With four control points Pg P1 P2 B3 Degree Pt has degree at most 3 one less than the number of control points Special values P Pg P1 B3 c Tangency At t 0 the Bezier curve is tangent to the rst leg of its control polygon at t 1 it is tangent to the last leg Convex hull For 0 g t g 1 the Bezier curve lies entirely in the convex hull of its control points 0 First derivative at ends P 3P1 Pg and P 1 31 3 P2 Second derivative at ends P 0 6Pg 2P1 P and P 1 6P1 2P2 P3 Af ne compatibility The Bezier construction is compatible with af ne transformations T In other words T is the same as the point at time t on the Bezier curve with control points T Pg T P1 TP2 o Evenly spaced control points If Pg P1 Pg Pg are evenly spaced along a straight line then Pt reduces to the usual parametric form of a line segment namely P0 Pg tPg Pg 0 Maximum in uence For k 0123 the control point P1 has its maximum in uence ie its coef cient is at a maximum at time t Symmetry P1 t is the same as the Bezier curve with control points in the opposite order Pg Pg P1 Pg 0 Halfway point P is of the way from the midpoint of the seg ment Png to the midpoint of the segment P1132 o Generality algebraically For any cubic parametric curve Pt its portion 0 S t S 1 is a Bezier curve for suitable chosen control points Generality geometrically Any segment of a cubic parametric curve has the same points as some Bezier curve with suitably chosen control points 5 Properties of Be zier curves of any degree Generalizing the idea of a cubic Bezier curve a Bezier curve of degree at most 7 based on n 1 control points Pg P is de ned by Pt JngtPg O JnntPn where the Bernstein polynomial Jnaka is de ned by Jnaka 1 tquot tquot The properties of cubic Bezier curves listed above generalize as you might expect they would In addition here is a nice derivative property that ex plains some of the derivative properties already mentioned for cubic Bezier curves 0 Derivative at any point If P0 is the Bezier curve with control points Pg P then P t nQt where is the Bezier curve of degree at most 7 1 based on the control points APg P1 Pg P2 P1 Apn1 Pu P7171 Thus we get a factor of n reminiscent of the derivative of atquot and another Bezier curve based on differences of control points of PU 6 Some applications 1 Making a loop Use a Bezier curve in which the rst and last control points coincide as in Figure 4 BB5 Figure 5 Arcs 2 Making an arc Just use these control points or similar ones depending on the shape you want as in Figure 5 The control points in this example are 0 0 25 25 75 25 1 0 If you instead want an arc of this exact shape between other given points Q0 and Q1 find an af ne matrix that does a rotation uniform scaling and translation to move the segment 0 01 0 to Q0631 To do this write Q0 c d and 11 Q1 Q0 and then use the extended l QQ a b matrix b a c d 3 Making a curved arrow Add an arrowhead to a curved arc For the arc in Figure 5 a suitable arrowhead goes from 95 0 to 1 0 to 1 05 For a curved arrow with similar shape in a different position apply an af ne transformation as above See Figure 6 Figure 6 A curved arrow 4 Making an S curve Just use a control polygon of the kind shown in Figure 7 Adjust as desired If you add an arrowhead you could use such a curve in a flow chart to show a path from a box on one level to a box on a lower level C Figure 7 An S curve Hermite data Suppose you want to nd a cubic curve that has given values of 30 31 Q 0 and Q 1 Let s call these values Q0 Q1 63 and 63 respectively They represent the initial and nal positions and velocity vectors as indicated in the left diagram below This kind of problem is called an Hermite air meet problem after the French mathematician Hermite There is exactly one solution A solution is to use a Bezier curve with appropriate control points P0 P1 P2 Pg As you see P0 Q0 and Pg Q1 Also from the rst derivative property 3P1 P0 63 and 3Pg P2 These last two equations can be solved for P1 and P2 We get these Bezier control points as shown in the right hand portion of Figure 8 P0 Q0 P1 Q0Q P2 Q1 Q 1 P3 Q1 Q1 Q 0 Figure 8 Hermite data 7 Problems Problem BBl Prove the half way point property of Bezier curves Problem BB2 a Find the coordinate functions of the Bezier curve with control points 00 10 11 02 b Sketch this curve Instead of BB7 plotting many points it is usually better to plot a few points and find the tangent vectors there to tell the direction of the curve Problem BB3 Here is a graphical construction of a cubic Bezier curve For each If value you want first mark the point corresponding to t on each segment P0P P1132 and P2133 Call the resulting points Q0 Q1 Q2 For example if t each Q is the midpoint of its segment Then mark the point corresponding to t on Q0631 and Q1632 Call the resulting points R0 R1 Finally mark the point corresponding to t on ROB Call the resulting point 30 Then Pt 30 a Carry out this construction for the control points in Problem BB 2 for the cases t 25 t 5 t 75 b Prove algebraically that the construction works Express the 63 R and So in terms of t and the Pi and simplify c Prove the Half way Point property by reasoning graphically why does the point come out three quarters of the way from the midpoint of P0133 to the midpoint of P1132 Problem BB4 Which of the properties listed for the cubic Bernstein poly nomials are fairly evident from the graphs shown and which are not as evi dent Problem BB5 Prove the unit sum property of the cubic Bernstein poly nomials Problem BBG Prove the values given for the first and second derivatives of the cubic Bernstein polynomials at t 0 and t 1 Problem BB7 Prove the maximum property for the cubic Bernstein poly nomials Do derivatives help for all k Problem BB8 Prove the linear sum property for the cubic Bernstein polynomials One way First consider just the case where ark g for k 0123 The general case follows from this case and the unit sum property Problem BB9 Prove the basis property for the cubic Bernstein polyno mials Since the dimension of the vector space is known to be four it is enough to show either that the cubic Bernstein polynomials span the vector space 0quot BB8 that they are linearly independent For the first way Show how to express each of 1 15152153 as a linear combination of cubic Bernstein polynomials For the second way Given a linear combination that is the zero function ie is zero for all values of 1 look at the values of the linear combination at t 0 and at t 1 and also the values of the first derivative at the same places Problem BB10 Give an example of a cubic Bezier curve using the 73 that actually has a degree 1 b degree 0 c degree 2 Recall that the degree of a polynomial parametric curve is the maximum of the degrees of its coordinate polynomials Problem BBll For cubic Bezier curves verify a the formulas for the first derivatives at t 0 and t 1 b the formulas for the second derivatives at t 0 and t 1 c the tangency property by using a You may quote any relevant properties of cubic Bernstein polynomials Problem BB12 Prove this version of Taylor s Theorem for cubic Bezier curves Pt P0 3151 Pg 60 2P1 P 6 Pg 3P1 3P2 One method algebraic expansion Another method Verify that both sides have the same values and first second and third derivatives at t 0 because then by the regular Taylor s Theorem they must have the same cubic polynomials for each coordinate Problem BB13 Prove the convex hull property of cubic Bezier curves You may quote any needed properties of convex combinations and of cubic Bernstein polynomials Problem BB14 If the four control points for a cubic Bezier curve are all equal then Pt is constant Prove this fact two ways a Using the convex hull property of cubic Bezier curves and b using the unit sum property of Bernstein polynomials Problem BB15 Consider the af ne compatibility property of cubic Bezier curves On what property of af ne transformations and linear combinations does it depend Problem BB16 a In pictures of examples like those of Section 1 why is it acceptable not to indicate the and y axes and a scale b Why is it acceptable not to indicate which end of the curve has t 0 You may quote relevant properties of Bezier curves if you explain how they apply Problem BB17 Prove the property of Bezier curves with evenly spaced control points You may quote any relevant properties of cubic Bernstein polynomials Problem BB18 Find the coordinate functions of the Bezier curve Pt for the control points P0 123123 P1 124124 P2 125125 and Pg 126126 Do not attempt a long algebraic method instead quote any relevant properties of Bezier curves Problem BB19 In the upper left diagram in Figure 1 indicate the point on the curve where each of the two non end control points has its maximum in uence Trace the curve and control polygon regard the vertices as the vertices of the unit square calculate the two points of maximum in uence and indicate them Problem BB20 For an unspecified positive constant 1 consider the loop made by taking a Bezier curve with control points 0 0 h 0 0 h 0 0 a Find P b Find the value of t at which the coordinate is largest and the corresponding point on the curve c For what value of 1 would the loop just fit inside a unit square Problem BB21 a Find control points for a cubic Bezier curve that has exactly the same shape as the arc in Example 2 of Section 5 but goes from 1 0 to 21 b Find points that give an arrowhead so that the whole curved arrow has exactly the same shape as the one in Example 3 of Section 0 Problem BB22 Prove the formulas given for nding Bezier control points from Hermite data Problem BB23 Sketch a cubic parametric curve such that 30 01 31 01 1 Q 0 60 and Q U 60 Problem BB24 Prove the algebraic generality property of cubic Bezier curves Method Write Pt You may quote the basis property of Bernstein polynomials A suitable linear combination of them gives the art and similarly for How should you choose the control points Problem BB25 Prove the geometric generality property of cubic Bezier curves BB 10 Method The difference from the algebraic generality property is that you must consider any segment of a cubic parametric curve not just the segment 0 S t S 1 Accordingly suppose C is a cubic parametric curve and con sider a segment given by a S t S b Say how to make a re parameterization that gives the same points but for Which the same segment is given by 0 S t S 1 Then use the algebraic generality property Problem BB26 a Prove this derivative property of Bernstein polynomi als J mt n 771411 Jn11 t except that a term is omitted if its secondsubscript is out of bounds specifically JnAH and 7711710 are omitted 2 n z 7 Method Xou Will need the fact that 7 MW k Discuss separately the end cases With omitted terms b Prove the derivative property at any point for Bezier curves of any degree as given in Section 5 c Use the derivative property at any point to prove the derivative properties listed in Section 4 for cubic Bezier curves Problem BB27 a Starting from the fact that S t2 32 2st t invent the quadratic Bernstein polynomials and define quadratic Bezier curves using three control points b Sketch the quadratic Bezier curve with control points 1 0 0 0 0 1 for 0 S t S 1 c Extend your sketch to 2 S t S 3 Problem BB28 Show that in R2 any quadratic Bezier curve With non collinear control points can be mapped onto any other quadratic Bezier curve with non collinear control points by a suitable affine transformation so that the control polygon of the first is mapped onto the control polygon of the second Noncollinear means not in a straight line ou may assume any needed properties of quadratic Bezier curves that are similar to properties of cubic Bezier curves These curves are parabolas unless they are lines so this problem says that arbitrary parabolas can be taken to arbitrary parabolas by an affine transformation but it says more This can be done so that the t values match up With Pt on one curve going to on the other for every 75 Problem BB29 Find the coordinate functions at yt of a Bezier curve in R 3 With control points 0 00 100 010 001 BB 11 Problem BB30 Show that in R3 any nonplanar cubic Bezier curve can be mapped by an af ne transformation to any other nonplanar Bezier curve You may quote any relevant properties of Bezier curves Problem BB31 Show that as a parametric function of t the first deriva tive of the cubic Bezier curve with control points Pg13 is the same as the quadratic Bezier curve with control points 31 Pg 3P2 P1 and 31 P2 One method Expand both sides Another method Verify that both sides have the same values and first second and third derivatives at t 0 because then by Taylor s Theorem they must have the same cubic polynomials for each coordinate Problem BB32 A certain machine tool is programmed to follow a cubic Bezier curve in R2 However it is not necessarily at point Pt at time t Instead the and y coordinates are driven by separate identical motors and there is a maximum rate at which each motor can go Therefore the machine is programmed so that at any moment either the motor or the 3 motor is going at its maximum speed whether forwards or backwards For example it might be that for the points with 0 S t S 21 on the curve the motor is at its maximum rate then for 21 S t S 53 the 3 motor is at its maximum rate and then for 53 S t S 10 the motor is at its maximum rate again In this example there were three ranges of t Find the maximum number of ranges there could be for a cubic Bezier curve in general Method Imagine the path in R2 of the velocity vector P By Problem BB 31 this curve is a quadratic Bezier curve itself By an earlier problem the graph is a parabola In which regions of R2 is the ar motor limiting and in which regions is the y motor limiting Into how many pieces could the curve be broken by these regions Problem BB33 For given Hermite data is there necessarily a quadratic Bezier curve that satisfies the data Either give a method or give a coun terexample Problem BB34 a Invent a half way derivative property for cubic Bezier curves by expressing P in terms of the control points and looking for a geometrical interpretation It will involve a vector between midpoints of two sides of the control polygon times a factor b Show that at t the curve is parallel to the line segment joining the midpoints of the first and last legs of the control polygon Problem BB35 When we say a cubic Bezier curve we really mean a Bezier curve with four control points and of degree at most 3 Invent BB 12 a criterion for a cubic Bezier curve to have degree at most two Express your criterion in terms of the control points If possible given a pictorial interpretation Method A curve is quadratic when its third derivative is always zero Anal ogously to the Second derivative at ends property derive a Third deriva tive at ends property Actually since the third derivative of a cubic function is constant the third derivative will be the same at both ends and everywhere else Now set the third derivative 0 Problem BB36 For each graph in Figure 1 do the following separately for each Choose 71 y axes so that the lower left vertex is at the origin and so that all control points have integer coordinates with all their coordinates together having greatest common divisor 1 Then calculate in decimals and see if it does seem to match the graph Problem BB37 Plot the following functions together on one graph for Problem BB38 On a single graph plot the Bezier curve with control points 1 0 1 1 0 1 and also the three other Bezier curves whose control points are the same as these times Rgge nge and Rg7ge respectively This gives a pretty good approximation to a circle Problem BB39 For a Bezier curve of degree 4 with control points Pg P4 invent a Half way Point Property in terms of Pg and the midpoints of PgP4 and P1133 Problem BB40 Sketch a parametric cubic curve Pt for which P 10P110P 0 3a3P 133 Problem BB41 Show that for a cubic Bezier curve with control points Pg P1 P2 Pg the center of mass of the control triangle for P t is the same as the missing leg Pg Pg as a vector in the original control polygon You may quote the result of Problem BB 31 Problem BB42 Find the set of t with 0 g t g 1 for which Jgg has the largest value among the four Bernstein polynomials of degree 3 This is the BB 13 n d GRAPHS PROPERTIES AND APPLICATIONS Benny Sudakov Princeton University 39 A GRAPH RAND o What are the essential properties of random graphs 0 How can one tell when a given graph behaves like a random graph 0 How to create deterministically graphs that look random like A PO SSIB LE ANSW39ER Probably the most important characteristic of truly random graph is its edge distribution Thus may be a pseudo random graph is a graph whose edge distribution resembles the one of a random graph with the same edge density SPECTRA OF GRAPHS NOTATION The adjacency matrix AG of a graph G has aw number of edges from u to v It is a symmetric matrix with real eigenvalues 1 2 A2 2 gt n G is an n7 d graph if it is d regular has n vertices and maxiii S 1 32 0 If G is d regular then 1 d 0 Iden2 and G is n7d7 then AZMQg illl EDGE DISTRIBUTION NOTATION Let G be an ndA graph For B7 C Q VG eBCibc EG i beBc Ci eB THEOREM eB B i b b 6 56 i b b 6 3H Alon Alon Chung 80 395 o For any B7 C Q VG not necessarily disjoint d eia C giBiiCi i AxiBHCi o For any B Q VG d B2 93 1 Bi SEAiBilt1iTgt D 5U im INDEPENDENCE NUMBER AND hLAXCUT COROLLARY Hoffman The independence number of an n7 d graph G is at most MG d The maximum number of edges in a cut of G dn7eG n lt MaXCutG7 4 2 4 The vertex boundary ofX C VG in a graph G is 8X y E VGX HXEX X7y E E COROLLARY Alon Miman 84 Tanner 84 If G is an ndA graph G and X C VG of size at most n2 then 2014 8X 2 VERSE RESULT THEOREM Alon 1986 If G is d regular graph with eigenvalues 1 d 2 A2 2 2 n such that 8X 2 X for every X C V7 X n2 then 2 C ltd77 2 42c2 THEOREM Biu and Linia 2004 If G V7 E is d regular graph with eigenvalues 1 dZAQZ2n such thatforevery BCC V d 937 CBHC SaWBHCL then max AQ Mn 01 ogda CTHRLMATIC NUMBER Chromatic number MG is the minimum number of colors needed to color VG such that adjacent vertices get different colors litmus I If G is and n7 d graph then xG1 gt1l Q J lmmwmsw l IfGisndandd 2n3then XG OltWgt l Time3M in mm W The choice number of G satisfies a similar inequality 1 containing all vertices of G THEOREM Kriveevich and S 02 If G is and n7 d7 graph with Graph G is hamiltonian if it has Hamilton cycle ie a cycle SMALL SUBGRAPHS o H fixed graph with 5 vertices r edges and max degree A o G V7 E is an ndA graph and U Q V of size In THEOREM Alon If In gtgt A then U contains ltgt39 copies of H If d gt An 1 then G contains a complete graph K1 I u ET ini n q p SPECTRAL TURAN39B THEOREM How large can be K1 free subgraph of I77 d graph Every G has such subgraph with at least 503 edges THEOREM 5 Szabo Vu 2005 Let r 2 2 and let G be an n7 d graph with d gt n 1 Then the size of the largest K1 free subgraph of G is feG0eG o The complete graph Kn has d n 71 and 1 Thus we have an asymptotic extension of Turan39s theorem 0 The theorem is tight for r 2 By a result of Alon there are n7 d7 graphs with d2 An which contain no triangles EXAMPLE F n d GRAPHS For every fixed 6 gt O and d 2 3 a random d regular graph on n vertices is asymptotically almost surely an n7 d7 A graph with 7 xdilJre o VG Zp where p is a prime p 1 mod 4 0 i7j E EG ifF i ij r2 mod p is a quadratic residue G is an n7 d graph with 71 1 np7 dpi7 T EXAMPLES OF n d GRAPHS ERD s RENYI CRAP G is polarity graph of linespoint incidence graph of finite projective plane of order q o VG lines through the origin in F3 q is a prime power 0 Two lines are adjacent if they orthogonal G has no 4 cycles and is an n7 d7 graph with nq2q17 dq17 6 im EXAMPLE OF n d GRAPHS LUBOTZKY PHILLIPS SARNAK 96 NIARGULIS 98 For every d p 1where p is prime p 1 mod 4 there are infinitely many n7d72xd71 graphs For every k7 3 Xk there is a trianglefree n7 d7 graph with n 23k7 d 14 01n23 9 01n13 APPLICATIONS MAXCUT fG the number of edges in MaXCut ie a maximum bipartite subgraph of G CLAIM Folkore Every graph G with m edges contains a cut of size at least m2 THEOREM Edwards 7375 Every graph G with m edges contains a cut a bipartite subgraph of size at least GbggH v88m1g 9W CUT IN TRIANGLE FREE GRAPHS C ONJECTURE E rd s 70 395 If G contains no short cycles than it has bigger cut THEOREM Alon 96 improving Erdc J39s Lov sz Pojak Tuza Shearer If G is trianglefree and has In edges then as 2 g 9m45 The constant 45 tight PROOF OF TIGHTNE S S Use an n7 d7 graph with d z in z 9n13 no triangles V UT IN GRAPHS OF HIGH GIRTH THEOREM Alon Boloba39s Kriveevich and S 02 If G has girth length of the shortest cycle r and m edges then fG2gQmr1 This is tight for r 5 and r 4 PROOF OF TIGHTNE S S Uses a random modification of ErdosRenyi graph which is C4 free 3977 d 3 n12 n14 graph Hence m Qn32 and n m 54 56 lt m MaXCut 2 i 2 i On 2 i O Exponent H1 is tight also for all r gt 5 CUT IN H FREE GRAPHS For every fixed H there is 6 gt 34 such that if G is an H free graph with m edges then THEOREM Alon Kriveevich and S 05 o H cycle of length r 46710 then 6 o H K2S complete bipartite graph with parts of size 2 and s 2 2 then 6 56 0 H K3S complete bipartite graph with parts of size 3 and s 2 3 then 6 45 A GEOMETRIC PROBLEM PROBLEM Lova sz 79 Estimate fn max ELI vi where I v ER and 1 0 Among any three v39s some two are orthogonal o Konyagin 81 Qn03954 fn n23 23 0 KashIn Konyagln 83 QltIogmngt fn THEOREM Alon 94 fn 2 167 01n23 A GEOMETRIC PROBLEM PROOF OF LOW39ER BOUND G is a triangle free n7 d7 graph with d Qn23 On13 A is its adjacency matrix A i I is positive semidefinite so there is matrix B such that BTB A I Let v1 v2 Vn be the columns of B Then 0 Each 1 0 Among any three v39s some two are orthogonal C HimH2 ZEAIU n Yd Qn43 inl d f UNIVERSAL GRAPHS Given H a family of graphs eg all trees planar graphs and etc G is called H universal if it contains copy of every H E H OAL motivated by VLSI design Find sparse universal graph G for H Use limited resources to achieve max flexibility THEOREM Bhatt Chung Leighton Rosenberg 89 If H is all trees on n vertices of maximum degree at most D then there is universal G of order n with maximum degree 3 fD PANNING TREES IN n d GRA THEOREM Alon Kriveevich S 06 extending Friedman Pippenger 87 Let D 2 2 O lt e lt 12 and let G be an n7 d graph such that g Q lt 05 Ig2egt Then G contains a copy of every tree with 17 en vertices and with maximum degree at most D Random regular graphs Lubotzky Phillips Sarnak graphs etc are universal for almost spanning trees of bounded degree EMBEDDING STRATEGY VERY BRIEF SKETCH 0 Cut tree T into pieces T17 T575 fD7 e of decreasing size Embed T piece by piece respecting previous embedding 0 Use result of Friedman Pippenger that if every subset X of graph G of size at least 2k satisfies that i8Xi 2 DiXi then G contains every tree on k vertices with maximum degree D 0 Use the fact that if induced subgraph of I77 d graph has minimal degree at least GOV5 then it is a very good expander There is a constant CD such that n7 d7 graph with d gt CD contains every spanning tree of maximum degree at most D EDGE DELETION PROBLEMS A graph property 73 is monotone if it is closed under deleting edges and vertices It is dense if there are n vertex graphs with Qn2 edges satisfying it EXAMPLES o 73 G is 5 colorable o 73 G is triangle free o 73 G has a 2 edge coloring with no monochromatic K6 DEFINITION Given a graph G and a monotone property 73 denote by E73G smallest number of edge deletions needed to turn G into a graph satisfying 73 APPROXINL TION AND HARDNESS THEOREM Alon Shapira S 2005 o For every monotone 73 and e gt 0 there exists a linear time deterministic algorithm that given graph G on n vertices computes number X such that lX 7 E73Gl EH2 o For every monotone dense 73 and 6 gt 0 it is NP hard to approximate E73G for graph of order n up to an additive error of n2 5 Prior to this result it was not even known that computing E73G precisely for dense 73 is NP hard We thus answer in a stronger form a question of Yannakakis from 1981 Inner models and ultrafilters in LGR Itay Neeman Department of Mathematics University of California Los Angeles Los Angeles CA 90095 1555 ineeman mathucaedu Part 2 1 Review 2 Iteration trees and directed systems 3 Supercompactness measure on Pwlmw 4 Ultrafilter on 73w1ltw1 5 Forcing over LGR to collapse NW to col 0 Large cardinal assumption For each u e R there is a class model M sth 1 u E M 2 M has a Woodin cardinals say with sup 6 3 736M is countable in V and 4 M is iterable Any statement with real parameters forced to hold in the symmetric collapse of M holds in the true LR Ultrafilter on wl aM first measurable of M CM 2 aP P a linear iterate of M Used to show that for every X C cal in LR have M so that either CM C X or CM C X 1 Ultrafilter on w1ltw1 m the first measurable limit of measurables in M 75 g lt 7 lists the measurables of M below m in increasing order em lt2 I ltvgt GM as before The sets CM generate an ultrafilter Used to get bddness Used bddness in forcing Next aim to do the same with NW instead of 411 In general iterations may be non linear Non linear iterations are called iteration trees Iteration trees involve some choices at limit stages M is iter able if these choices can be made in a way which secures well foundedness A correct iteration tree on an iterable M is one which follows the limit choices needed to secure wellfoundedness Mw1 Mw M7 M5 M3 913 M1 jo1 Already at the level of linear iterations there is an implicit notion of correctness A linear iteration of length or is correct if a is well founded This correctness for linear iterations is Hf In the claim of boundedness last time it was the contribution of correctness to the complexity of the set El an iterate P of M aPxu holds in a symmetric collapse of P that made it 2 For iteration trees the complexity of correct ness is higher How high depends on the large cardinals involved in the iteration Let M be iterable and let 739 e M be least such that LMl7 IZHT is Woodin For iteration trees on M using extenders from below 739 correctness is roughly H5 Let M now be fine structural over a real u Any two correct iterates of M can be com pared In other words for any two correct iterations jl M gt P1 and 3 2 M gt P2 there are further iterations hl P1 gt Q1 and h2 P2 gt Q2 so that Q1 2 Q2 Q1 Q2 m h2 P1 P2 j1M4 Further the embeddings given by correct iter ations are unique by the Dodd Jensen lemma k1 M gt Q and k2 M gt Q both iteration em beddings then k1 k2 Use Mg for the iteration emb from M to Q In the situation of the comparison above the uniqueness implies that hl ojl equals I12 03 5 By iteration from now on we mean a correct iteration of countable length Comparisons allow considering the directed sys tem of all iterates of M Let D be the set of pairs P 13 so that P is a an iterate of M and 1 belongs to P For P 13 and P x gt both in D set P 13 N P x gt iff in the comparison of P and P get ha hx N is an equivalence relation on 7 Define further P 13 6 P x gt iff in the com parison of P and P get h13 E h13 6 induces a wellfounded relation on DN Set MOO transitive collapse of YDN 6 M00 is the direct limit of all countable iterates of M Have 7rM700 from M into MCgtO defined by wM7wx equivalence class of ltM13gt We are working in LUR tag is equal to 6 w3 w4 etc are all singular cardinals of cofinality tag NW is the size of a homogeneous tree for H5 sets Nw1 is equal to 6 Suppose M is iterable 739 7M is least such that LMl7 IZHT is Woodin and 739 is count able in V Theorem Woodin 7TM700T is equal to NW This is connected to the fact that correctness for trees below 739 is roughly H5 Recall our scheme for getting ultrafilters Define aM somehow Set CM 2 aP P is an iterate of M Use the CMS to generate an ultrafilter Here we want an ultrafilter on 73w1Nw So we need aM E Pwlmw Natural attempt set aM M700 7M Then aM E 73w1Nw and CM C Pwlmw As before the sets CM generate an ultrafilter It s the supercompactness measure on Pwlmw The finite intersection property takes more work here than in the case of M More on this in the next talk 8 Proof of normality Fix f e LGR on Pwlmw such that fX E X for all X Wlog f is definable from a real u Fix p so that 04 iff LUR ltpuXa Take M satisfying LC assumption with u E M Let 739 be least so that LMl7 IZHT is Woodin Look at 04 faM oz belongs to aM FMyoOIT Have a lt 739 in M so that f7TMooT 7TMoo54 This statement about M 739 and a is true in LGR hence true in the symmetric collapse of M hence true in the symmetric collapse of every iterate P of M about P M47147 and M71460 hence true in LGR about P M47147 and M71460 So faP f7TPoo7TMPT 7TPoo7TMP54 7711700034 2 or for every iterate P of M In other words fX a for all X 6 CM 10 An ultrafilter on 73w1Nwltw1 Let M be an iterable fine structural model over a real u Say that 739 e M is good if MM 739 l 739 is Woodin Suppose M has a measurable limit of good cardinals and let m 2 MM be the least such Suppose m is countable in V Let 75 g lt 7 list the good cardinals of M below m in increasing order For each or lt 7 let ya be generic over M for col lapsing SUDT g lt 04 Let Ma denote Mga Ta is the first good cardinal of Ma Mga Ga WMa7OOITQ Ga I 01 lt Then each aa belongs to Pwlmw and aM belongs to 73w1Nwltw1 11 Set CM 2 aP P is an iterate of M Our earlier proofs all carry over to the current settings The sets CM generate an ultrafilter on 73w1Nwltw1 call it 7quot The ultrafilter concentrates on long sequences The projection of J to 73w1Nw1 is precisely our earlier filter namely the supercompactness measure on 73w1Nw The projection of J to Pwlmw o is the or length iteration of the supercompactness mea sure 12 The proof of boundedness for the filter on w1ltw1 also carries over to current settings Recall that in that proof we defined E to be the set of reals 1 so that El an iterate P of M aPxu holds in a symmetric collapse of P E was 2 and this allowed proving bounded ness for functions into tag 2 6 In the current settings being a correct iterate is H5 E is therefore 2 and the proof of boundedness works for 6 NW4d We get Claim Let g 73w1Nwltw1 gt NW4d Then there is a set X e J so that ng is bounded below NW4d For the so measure on Pwlmw as opposed to the iterated measure on 73w1N1ltw1 bound edness is due to Becker 1979 by classical methods 13 An application to forcing over LGR Recall can use J to define a forcing notion Conditions are pairs tY where t belongs to 73w1Nwltw1 Y is a set of extensions of t and s t s E Y is nice X C 73w1Nwltw1 is nice if X E 7quot X is ctbly closed and r 5W 6 X e J for each s E X The order on conditions is defined in the natu ral way t Y lt tY if 25 extends t Y C Y and t E Y Let A be this poset Let H be A generic over LGR A is countany closed So it does not add reals It follows wl is not collapsed by A and that 6 is not changed 14 H introduces a sequence a5 g lt cal with each a5 a countable subset of NW The genericity of H implies that U a5 2 NW Thus H collapses NW to col ltW1 Boundedness implies that Nw1 is not collapsed So Nw1 becomes tag in the generic extension N 21 6 W2 6 NW w3 H w2 a 55 L01 wl LGR LRH Since 6 does not change we have LGR H 5 2 tag 15 Steel VanWesep Woodin m1980 show how to force over LGR and introduce the axiom of choice without collapsing tag Their methods adapt to forcing over LRH giving Theorem N Woodin independently It is consistent with ZFC and ADLR that 5 412 Same argument works for higher levels Can get the so measure on 73w1gt for any A g 6 Can collapse or lt 6 to cal without collapsing 6 Get the consistency of ZFC ADLUR 5 412 16 VANISHING OF THE u INVARIANT OF p ADIC HECKE LFUNCTIONS HARUZO HIDA CONTENTS 1 Modular Curves 2 11 The tower of modular curves 2 12 Hecke invariant subvarieties 4 2 Geometric modular forms 8 21 Moduli Problem 8 22 Modular forms of P p 8 23 p Adic modular forms 9 24 Hecke invariant subvarieties 9 3 p adic Hecke L functions and its u invariant 10 References 13 Date December 27 2008 Two lectures at Kyoto December 17 2008 the author is partially supported by the NSF grants DMS 02444017 DMS 0456252 and DMS 07539911 VANISHING OF THE M INVARIANT OF p ADIC HECKE L FUNCTIONS 2 First Talk This series of two lecture is an introductory discussion of problems concerning vanishing of the lwasawa u invariant of p adic L functions This type of results for Kubota Leopoldt p adic L has found good applications in divisibility problems of class numbers see W1 FW and ICE Chapter 7 and in proofs of the main conjectures in lwasawa7s theory Recently new methods of proving the vanishing emerged in the work of Vatsal Finis and myself In these two lectures we describe a geometric method which was started by Sinnott in Si and Si1 and has been generalized in H04 H08 and H07 via the theory of Shimura varieties We rely on a general philosophical principle proposed by Chai Oort and others A Hecke invariant subvariety of a Shimura variety is a Shimura subvariety and we can prove this for the Hilbert modular variety and its self products In this talk we only deal with modular curves and their self products for simplicity however any essential ingredients for the general facts shows up in this simpler case Write G GL2Z with center Z g GmZ 1 MODULAR CURVES We study subvariety of self product of modular curves stable under toric action 11 The tower of modular curves We study classi cation problem of elliptic curves EA over a ring A which is an algebra over a base ring B In other words we consider the following moduli functor of level TN 5rN4A E7 N 3 ZNZ2 g ENlt N1707 N071gt C for all ZC algebras A where C is a generator of MN Here is the Weil pair ing We know classically SFN CC PNfj If we remove the contribution upon C and consider the functor SFNA E NA de ned on the category of Z algebras we have 8pm 91quotN and this functor is represented by a geometri cally non connected scheme MNN and YN de ned over if N 2 3 Note that YawMW um YltN with nltNgtltltcgt 2 WW We can let a constant group 04 E SL2ZNZ act on and hence on X N by E H E o 04 Since 15 o a10 O 0401 SEW the same action of 04 E GZNZ induces an automorphism of YNZ and XNZ which is induced by the Galois action N H glam on SpecZCN The group imN GZNZ acts on the limit Y imN YN which is a pro scheme de ned over Q and SL2Z preserves the connected component 1400 imN Y N A remarkable fact Shimura found is that this action of GZ can be extended to the nite adele group GA see lAT Chapter 6 An interpretation by Deligne of this fact is equally remarkable see PAF 421 To explain Deligne7s idea we de ne the Tate module TE imN EN for an elliptic curve EA for a Q algebra A Strictly speaking taking a geometric point 5 Speck E SpecA for an algebraically closed eld k in each connected component of SpecA we are thinking of the i module TE imN EN as is well known the choice of s does not matter see PAF Chapter 4 Appendix Then VANISHING OF THE prINVARlANT OF p ADIC HECKE L FUNCTIONS 3 TE g Z2 and VE TE 8 Q g A 2 Deligne realized that Y represents the following functor de ned over Q ALG 5lt A Eyn i A0 2 VEAisogenies Here N is the nite adele ring Then g E GA sends a point E77A E Slt A to E77 o g A for the projection gm of g to N Take the prime to p quotient 307 limMNYN YGL2ZP Put VpE TE 82 Am and consider the prime to p level structure 770 Ap 2 V E Then Yp represents the following functor de ned over Zp ALG 80 A E77 Am ol2 V EAprime to p isogenies where an isogeny b is prime to p if the order of the kernel of b is prime to p This pro scheme Yp is de ned over Z07 so its ber YE over SpecEp is the Ep scheme classifying E77pA for Ep algebras A On 507 again GYM acts by 770 H 770 o g If we have a prime to p noncentral endomorphism Oz E a E then E has complex multiplication by M QM and we can write 04 o 77 77 o pa for pa E GA Thus if x E77 E YA we nd that pax x For any elliptic curve E we have Q C EndE 8 Q so the central element 5 E QX C GA acts trivially on Y Thus x E 77 has CM by an imaginary quadratic eld M if and only if MXQX is the stabilizer of x in AutY Pick an elliptic curve E with complex multiplication by the integer ring RAof M We suppose that p splits into p pp in R Consider W WEp inside CZ p We put W W Q which is a strict henselization of Z07 We suppose that p R 111W and El n is etale over W Assume EC CCR Since the isomorphism class of E over C is determined by the principal ideal class of R we write this elliptic curve as X XR Then we can pick a level p structure 77 ppm 2 pm and 77 QPZp XE Write 771 772771 ppm gtlt QPZp leml gtlt XE and de ne a homomorphism pp of Ra into the diagonal torus of GZp by 0477 77 0 ppm for 04 6 PW Thus 77 0 ppm 0477p identifying RF with Z and 775 0 ppm 04077 writing 6 RF 2 RE Fix a base wl mg of E07 over Z07 and identify My with Ap 2 The choice induces prime to p level structure 770 Ap 2 g R 8 AW VpX We put 77 7717 gtlt 770 De ne p Ra a GAp by nopd 0407 Thus p pp gtlt p07 prgt a GZp gtlt NW9 Since 04 6 Ray induces an isogeny Oz X a X sending 047707 npppd the point MR XRnp is xed by Ma Pick a fractional ideal a D R prime to p For any a E M13005X with LE M a so a 1 E E we de ne x01 ppa 1xR XR77 o pa 1 which gives another point on 507 By tensoring XR with the exact sequence 0 a R a a a aR a 0 we get another exact sequence 0 a Xala71lW H XRW L XRw R Cl XClW w 07 tale VANISHING OF THE illINVARIANT OF p ADIC HECKE L FUNCTIONS 4 where XaCC CCa Then we have the following commutative diagram 130200 TpXR 7 ll lw 1730200 4 TpgtXa nltFgtopFa Thus writing Ma Xa 77 we have ppa xa Mom this fact if a Z Ra the point u is different from Consider the formalfompletion Y YmW of YSg along x Ma 6 Y Fp Then by the universality of Y Y satis es WA 2 M where A runs through p pro nite local W algebras with AmA Wmw E and ETA EAE A E XaE lndeed Y classi es EnpA with Em XAFP Xanp but 770 uniquely determines 77 so we can drop the datum of the level structure By the deformation theory of Serre Tate Y E Gm canonically lndeed rst EM 6 8A is determined by the extension Elpmlquot gt Elpml a Elpmlet of the Barsotti Tate groups By Serre Tate such an extension over A is classi ed by H0mElpoolet7 Elpoolo g H0mQPZpA7Hp A h l pr A For this identi cation we need to x 7 ppm 2 Xap and its dual inverse 7715f QPZp E Xa Since up 1 the above identi cation is independent of a and a Since pa x Ma it acts on Y We admit the following lemma Lemma 11 Identifying Y with Em SpflimnWtt 1lt71 ifa E MX we have pat take far camplex canjugatian 6 Note that if 04 E MX is not prime to p the action of pa is an endomorphism of Y not an automorphism A proof of this can be found in H08 as Proposition 34 We regard pMX C GAp as the group of Q rational points of a torus Tm Then the action of pa on the Serre Tate coordinate is given by t H take factoring through GAp ZQ since ZQ acts trivially on the Shimura variety Y 12 Hecke invariant subvarieties Write l E7 WmW WmW Let a be a fractional ideal of M with up RP We write Ia for the irreducible component of Y Y gtltW 19 containing Ma Note the following fact HOS Proposition 38 which is obvious since dim Y0 1 but not trivial in the Hilbert modular case F Fact 11 IfH C Y is an irreducible clased subscheme cantaining 01 stable under the actian 0f ap adic Open subgraup 0f TmZp Then either H xa or H Ia VANISHING OF THE wINVARlANT OF p ADIC HECKE L FUNCTIONS 5 Let a and b be fractional ideals of M with up hp RP with ab l 2R for z E MEMV Then pz gives a morphism of Ia onto Ib for any 6 R87 and we have a skew diagonal AW lmpa gtlt pz C Ia gtlt1F Ib for 04 6 R87 We want to give a sketch of a proof of the following two theorems HOS Corollaries 316 and 319 Theorem 12 Suppose that H C Ia gtlt1F Ib is an irreducible clased subscheme cahtaz39m39hg xaxb E Isl1F gtlt1F Ib stable under the actz39zm Of a p adz39c Open sabgraap 0f TmZp Thea ez39ther H 2501 gtlt Ib 0r H Ia gtlt 251 or H AW fora 6 Ba Theorem 13 Let H g I 11 gtlt1F gtlt1F Ian with n 2 2 be a praper clased irreducible subscheme with a dammaat prajectz39zm t0 the pradact 0f the rst 71 7 1 factar and t0 the last factar IfH is stable under the diagzmal actz39zm Of a p adz39c Open sabgraap 0meZp up t0 permatatz39zms 0f the rst 7171 factars we have H I 11 gtlt gtlt Ian2 gtlt Awe where AM is de ned with respect t0 113 an1an We start with general lemmas We suppose that the two projections to Ia and Ib are dominant Take al 6 MAX with LlR ai and am Llgt00 1 Replacing H by pa1 gtlt gtlt pa H7 we may assume that a1 a2 an R so7 we write x MR I IR and x xx x E I Let T C TmRp be the open subgroup under p adic topology xing H by the diagonal action of pm gtlt gtlt pa 04 E T Then the formal completion H along x is also stable under T7 since x is xed by T By the Serre Tate theory7 H C SEF Let X1LF E Z be the formal cocharacter group Then7 by a rigidity result of Chai eg7 H08 Lemma 377 11 HUW ZFLCLL L where L runs over nitely many Zp direct summand of of rank n 7 1 Let H 7 H be the normalization of H Since H is an excellent irreducible scheme7 H is reduced equidimensional so7 all L as above has rank n 7 1 Since H is irreducible7 H is irreducible By 117 each point over x ofH is indexed by L7 and for the point gm 6 H over x corresponding to L7 HyL is etale over Sm 8 L Write Im I gtlt I for I I quot 1 and I I for the last component Lemma 14 The scheme H is nite flat aver I araaad xn l In particular each L is 0f rank n 7 1 and prajects dawn t0 an Open sabgraap 0f X1f1 Z24 If me Of L surjects dawn mta 751 all Of L surjects dawn Oats XIA and the prajectz39zm H 7 I is e tale m39te araaad 4 Proof Since the projection of the rst 71 7 1 factor I I quot 1 is dominant7 at least one of L7 call it L07 projects down to an open Zp submodule of X46751 If there is L with image in X1 of rank lt n 7 17 the non at locus an C H of H 7 I is a nonempty proper closed subscheme of H Since dim Sm 8 L rank L n 7 17 an has dimension n 7 1 equal dimH so7 H has to be reducible7 a contradiction Thus H 7 I is nite at around xm l via a faithfully at descent from to HI If one of L7 call it L07 surjects down to and another L1 has image smaller than X1I 7 the rami ed locus Hquotquot of H 7 I is nontrivial proper closed subscheme of VANISHING OF THE it INVARIANT OF p ADIC HECKE L FUNCTIONS 6 dimension n 71 again a contradiction to the irreducibility of H so H a I is etale nite around xm l again via a faithfully at descent from HI to HI B When n 2 by applying a power of the p power Hobenius or its dual to H that is applying pd for 04 generating pRp or its dual pamp we may assume that at least one L surjects down to XIA so by the above lemma all L surjects down to Thus we may assume that H a I is etale nite around xm l Now assume it 2 Then over an open dense subscheme U C H containing all points above 252 the two projections nL U a I I and 7TB U a I I are etale nite We consider the universal elliptic curve EI We pull it back to H A nEE and B n E Pick a point y E H over 252 Then H Hy tbt lt 6 IA C IAgtlt Since nj H a I is etale nite around y we may assume that ab E R a so we may assume that b 1 Identifying X XRF with the bers Ay By of A and B at y we regard the unit a E EndXp as a homomorphism a Ayp Xp gt leml Bylpml We note the following fact see H08 Proposition 315 Lemma 15 C L Chai Farther shrinking the Open neighbarhaad U afy in H we may assume that the isamarphism a Ayp Xp a Xp Byp extends t0 5 AUp a BUp This implies that Hu Gm by tt5 lt gt t at any paintn E Here is a sketch of a proof of the above lemma Since a can be approximated p adically by an E Pap modulo p a can be extended to Man Ap a Blpnl Passing to a limit we have an extension 6 Ap a Blpml Write O for the stalk of 9H at y so H Spf5 Since 6 is determined by its restriction a to Ayp it is a unique extension of a Since 5 80 5 is reduced because of excellency of O the pull back of E by two projections H XHH a H coincides so 6 satis es the descent datum with respect to 50 getting desired U Proof of Theorem 12 Since the two projections 79 H a I j LR are dominant we have EndA 8 Q EndB 8 Q Q Let YH A gtltH B Thus there are only two possibilities of EndQY EndYH 8 Q Either EndQY Q gtlt Q or EndQY M2Q Suppose that EndQY M2Q By semi simplicity of the category of abelian schemes we have two commuting idempotent ej E EndQY such that eAY A and eBY B Since EndQY M2Q we can nd an invertible element 5 in GL2Op C M2Q such that 60 6A 63 so 5 A a B is an isogeny whose specialization to the ber of A and B at y gives rise to an endomorphism 6 EndXR 8 Q Thus the isogeny B is induced by pm and we conclude AU H We suppose EndQY Q gtlt Q and try to get a contradiction in order to prove that EndQY M2Q We pick a suf ciently small open compact subgroup K C GAp maximal at p so that the normalization HK of HK C YK gtlt YK is smooth at the image of y The variety YK is naturally de ned over a nite extension FqFp as the solution of the moduli problem ElmK The universal elliptic curve EK is therefore de ned over mm and HK is a variety of nite type over Fq Let 7 be the generic point of HKFq and write n for the geometric point over 77 and PAW for the separable algebraic closure PAW of E107 in Fq Take an odd prime Z 31 p and consider the Z adic Tate VANISHING OF THE prINVARlANT OF p ADIC HECKE L FUNCTIONS 7 module TAYW for the generic ber Y of Y We consider the image of the Galois action lmGalqu 55pFqn in GLOMOZ Then by a result of Zarhin DAV Theorem V47 the Zariski closure over Q of lmGalqu 55pFqn is a reductive subgroup g of GLQMQATAYW 8 Q and lmGalqu 55pFqn is an open subgroup of QQl Moreover by Zarhinls theorem the centralizer of g in EndquZ TAY Q is EndY Ql Since the reductive subgroups of GL2 are either tori or contain SL2 the derived group 91Ql of QQl has to be SL2Q gtlt Q1 By Chebotarevls density we can nd a set of closed points u E HKlF with positive density such that the Zariski closure in g of the subgroup generated by the Hobenius element Frobu E lmGalqu SBPFqn at u with 7T7u uj uj E IKlF is a torus containing a maximal torus Tu TU1 gtlt Tu2 gl of the derived group 91 of g In particular the centralizer of TM in 91 is itself Thus Yu is isogenous to a product of two non isogenous elliptic curves Y1 Eu1 and Y2 Eu2 de ned over a nite eld The endomorphism algebra Mj EndQOj is a CM quadratic extension of Q generated over Q by the relative Hobenius map 15739 induced by Frobu The relative Hobenius map Frobu acting on XIAu g 017 has one eigenvalue 155170 for the CM type 21 a of Y1 which differ from the eigenvalues of 152 E EndY2 on XIu2 Op Since we have proven that over the open dense subscheme U of H the formal completion of U at u E U with u 111112 6 X C V2 is canonically isomorphic to a formal subtorus 2 C IAul gtlt I22 with co character group X Z17 we may assume that our point u 111112 as above is in the open dense image UK of U in HK Projecting down to the left and the right factors IK the projection map a XIAuj is actually an injection commuting with the action of Frobu Thus Frobu has more than one distinct eigenvalues on X42 which is a contradiction Thus we conclude that EndQY M2Q for any choice of small open compact subgroups K maximal at p As we have remarked at the beginning EndQY M2Q implies that we have an isogeny E A a B over H Writing 7771 339 A B for the prime to p level structure of A and B inducing the prime to p level structure already chosen for XR Ay By we nd that Bo 775417 77g 0 g for g E GAp Specializing at y we have g pm for 6 EndQXR M Thus Hy C Hmz C 7 gtlt 7 is given by tt 17clt E for nonzero 6 PW Suppose that y corresponds to L so Hy C Igtlt Icoincides with m L On the other hand we have the skew diagonal Ag AU 2 E I C I gtlt I The formal completion 3 along x x therefore coincides with Hy and am 8 L C Hm inside Thus A C H By the irreducibility of H we conclude H Ag Since A is smooth A H and hence H is smooth everywhere D There are two way of proving Theorem 13 One is an induction reducing things to Theorem 12 and another is to prove that EndY Q M2Q gtlt Q 2 for Y H 7GB for the projection 79 of H to j th component I after a permutation of the factors I VANISHING OF THE prINVARlANT OF p ADIC HECKE L FUNCTIONS 8 Second Talk In this second talk7 we relate the result proven in the rst talk with linear independence modulo p of classical and p adic modular forms 2 GEOMETRIC MODULAR FORMS We study classi cation problem of elliptic curves EA with a differential w over a ring 21 Moduli Problem Consider the following moduli functor of level UN7 73PNltA E7 N7wIHOE7 QEA Aw E7 NA E 5PNltAl 7 for all ZC algebras A Again we remove the contribution upon C and consider the functor 73FNA E NwA de ned on the category of l algebras7 we have PFN 73pm and this functor is represented by a geometrically non connected af ne scheme MN SpecRpN de ned over if N 2 3 When N 17 over Ma 73ml is represented by M1Z SpecR for R Z92gg for A g 7 27g 7 where 9293 are variables So7 for simplicity7 we assume that our base ring B has 16 in it The universal elliptic curve with universal differential is given by EmM moimix Y ZiZYZ 7 4X3 M22 52323 We can let a E Gmm act on PFN by Ew H Eaw so7 R is naturally a graded algebra RFUV neZRnPN In particular7 97 has degree 2739 for j 23 Then YN ProjRPN SpecR0PN Write G Zggg3 C R and de ne GPN by the integral closure of G Then GPN is naturally a graded algebra7 and XN ProjGPN is a smooth compacti cation of the af ne curve YN 22 Modular forms of P p Let B be a base Z algebra7 and A denote a general B algebra A level P1p structure on EwA is an embeddingz MP gt Ep de ned over A Consider the following Pl version of the moduli functor 73p1pnA E239wA Then Plum is again representable by an af ne scheme RP1 We take the following moduli theoretic de nition of modular form on P1 19 a modular form f E GkP1 19 B is a functorial morphism for all B algebras A7 pF1pquotA Eyiywm a A1A A satisfying the following conditions Regarding f as a function of isomorphism classes of E239wA with fE239wA E A satisfying G1 fE239awA a kfE239wA for a E AX GmA G2 If p A a A is a morphism of B algebras7 then we have fE729WA XA Al 0fE7 7wA G3 The function has q expansion in Bqudll 0 lt dip at the Tate curves with level P1p structure VANISHING OF THE wINVARlANT OF p ADIC HECKE L FUNCTIONS 9 The direct sum GP1p A Kkez GkP1p A is a normal graded algebra ln particular7 when n 07 we have P1jA ProjGP11A li rojG7 and In ProjGP1 19 leP1jFp is the lgusa tower We can think of l O version7 replacingi by a subgroup C C Ep isomorphic to ppn etale locally Then elements in GkP0p A are functorial rules 73p0pnA ECwA a A1A A satisfying the conditions G1 3 replacing P1p level structures i by P0p level structures 0 23 p Adic modular forms A p adic modular form f over a p adic base ring B limn Bp B is a functorial rule Ei 77 ppm gt Elp A H fEi E A for a p adic B algebra A ApnA In other words7 f satis es the following conditions P1 fEaiA a kfEiA for a E AX GmA P2 If p A a A is a p adically continuous morphism of p adic B algebras7 then fE7 A XA A pfE7 A P3 We have the q expansion fq in BM at the Tate curves with the canonical iam ppm a Tateq and the t expansion ft ing E W ll T til for the universal deformation E of XR over 37517 Em x By de nition7 the functor pflpwB p adic B ALG a SETS given by 73r1pltgtltgtA EJ 3 2200 g ElpoolONA is pro represented by the formal completion of A700 SpecRF1pnBMB along its mod p ber The level P1p structure i induces an isomorphism of formal group i am g E and cup i on E Thus if f is a modular form on P0p as above7 we can de ne jEi fEiipnwp7 and in this way7 we may consider a modular form as a p adic modular form They have the same q expansion and t eXpansion Write So0 for the formal completion of 307 along the ordinary locus of Y Let I00 gt SOC be the lgusa tower whose reduction mod p is the irreducible component containing x xR mod p We have 21 fq E 0 mod p ltgt ft E 0 mod p ltgt flIw E 0 mod p because of the irreducibility of the lgusa tower over IF a result of lgusa 24 Hecke invariant subvarieties We recall the result we proved in the rst lecture Recall the imaginary quadratic eld M in which the prime p splits We write I for the irreducible component of Y Yp gtltW l9 containing Recall ALE Theorem 21 Let H C I gtlt1FI gtlt1F gtlt1FI with n 2 2 be a prbper clbsed irreducible subscheme with a dbmihaht prbjectibh t0 the prbdiict 0f the rst it 7 1 factbr and t0 the last factbr IfH is stable under the diagzmal actizm 0f 1 p adic bpeh subgrbiip bmeZp n72 F a up t0 permutatibhs 0f the rst it 7 1 factbrs we have H I gtlt gtlt I XAa where AM is the shewed diagbhal po zp zlz E I C I gtlt I VANISHING OF THE it INVARIANT OF p ADIC HECKE L FUNCTIONS 10 Consider 11 an E R Z distinct modulo RQme T1Zp thus aiaj Z MX if 239 7 339 Corollary 22 Fix a weight k gt 0 Let h E GkP0pTW be a lift 0f the Hasse invariant Prepare an m 1 set hf1 fam C GkP1pT W 0f madulm farms linearly independent madula mw far in gt 0 Then the nm set 0f madp madulm farms fi1t i fimtaiij madula mw is linearly independent in 1Ftt 1 Proof We consider the completion 5 537m m along x mod 111W 6 m gt YplF Then R acts on llt7 t ll by t H tai Thus we can think of z A ltP 3 Oymm 1F JF wam a 0 given by ltpf1t f1t 1f2t 2fnt quot Note that ft for f E GkP1p W since we may assume that h E 1 mod 111W lf Kerltp 07 we get the desired result7 since fl1 h7 C Oypm lf not7 Kerltp de nes an irreducible closed subscheme X of SpecOypm 1F 1F Oypm I Let X be the Zariski closure of X in I Then X is invariant under the action of 04 E TmZp since it acts by t H take commuting with p By induction on n7 we may assume that the projection to the rst n 7 1 factor I of I of X and the last factor is dominant Then by the above theorem7 permuting the indices 239 lt n7 we nd 046 E MX such that X C In gtlt Awe which implies MAan 046 6 MX after permuting indices of ii for j lt n7 a contradiction Thus Kerltp 07 and we are done D 3 p ADIC HECKE L FUNCTIONS AND ITS M INVARIANT ln 18997 Hurwitz studied an analogue of the Riemann zeta function 1 L4k m abieZi70 of Gaussian integers Zli and showed that for positive integer k L4k 1 dx dx i i E Q 2 7 7 eriod of the lemn1scate 94k Q 0 17964 7y p Nowadays7 we regard this value as a special value of a Hecke L function Ls A Z AaNa 9 of the Gaussian eld QM Here A is a Hecke ideal character of QM with Aa of and L4k 4L0 A We shall give a sketch of a proof of non vanishing modulo p of almost all Hecke L values for general imaginary quadratic elds M QB7D The Hurwitz formulation is modular For any lattice L Z1111 ng C C we can think about 1 1 E2kL 7 Eisenstein series7 2 aw bw 2k aw1sz26L 1 2 VANISHING OF THE prINVARlANT OF p ADIC HECKE L FUNCTIONS 11 which is a function of lattices satisfying E2k04L aCZkE2kL The quotient CL gives rise to an elliptic curve XL C P2 by Weierstrass theory Since XL has a unique nowhere vanishing differential du for the variable u of C and we can recover out of XLdu the lattice L as f7 duly E H1EZ7 we can think of Egk as a function of the pairs Ew of an elliptic curve E and a nowhere vanishing differen tial to satisfying E2kEozw aCZkE2kEw Note that E4Ew g Euu and E6Ew g Ew More generally7 Egk is a rational isobaric polynomial of 92 and 93 Thus Egk is a modular form f of weight 2k Fix an imaginary quadratic eld M Write R for the integer ring of M We assume that p splits into p p in B so that p gives rise to a p adic place 23917 Q gt Q17 Recall the ring W of Witt vectors with coef cients in the algebraic closure l9 E7 of FF and regard it as a valuation subring of CI 3 p in other words7 W is the closure in CI of the p adic integer ring of the maximal unrami ed extension of Q17 So W 21W with maximal ideal Q3 111W lmportant facts are E1 For a lattice a C R prime to p a is prime to p if R a is prime to p7 Xa is p integrally de ned over W C Q E2 Egk up to a simple constant which we ignore in this lecture is de ned over Q actually over Z07 for almost all k by the q expansion principle E3 Let u Qdu be a generator of H0XRQXRW lt2 H0XaQXaW Wu because a is prime to p Thus 9 fvw for a 1 cycle y with Rwy H1XaZp Then E2kamp w is the partial L value of the ideal class of aCl E2kXaw i E2kXaQdu i E2kXadu i La712k 6 Ma C a C mom C 9 because W a712k ZbNa1AbNbC2k for a Hecke character A with Aa of In order to get p integrality and an Up eigenform7 we modify the Eisenstein series Egk into 82kz E2kz 7 E2kpz Then we have 82kXaw E W A ray class character X modulo p with values in C is called p anticyclotomic if Xa0 XctC1 for complex conjugation G Let On be the ring class group of Ra Zp R Then X as above is anticyclotomic if and only if X factors through On Let Coo On The pro nite group 000 is isomorphic to A gtlt P for a nite group A and a multiplicative group P isomorphic to the additive group Z17 By results of Hurwitz7 Damerell7 Weil7 Shimura7 Katz combined7 we have 2 71 EU A W E W for p anticyclotomic X7 where L 07 AX 1 7 AXppC11 7 AXE L0X Katz and others constructed a p adic measure duX on 000 such that 2k71LP0 WA lt gt lt x 000 92k 6 W for Z anticyclotomic X VANISHING OF THE prINVARlANT OF p ADIC HECKE L FUNCTIONS 12 We project down the measure to P getting the anticyclotomic p adic Hecke L function L E Since g is a UFD7 we can decompose L pf L for a power series L E prime to p Then we have Theorem 31 pr gt 2 we have u 0 The result in the above imaginary quadratic cases are also treated by Finis see F1 and under different assumptions by a different method see also Vatsalls papers V17 V2 and V3 for related topics Here we shall give a very brief sketch of the proof of this special case7 assuming for simplicity that P 1 pr and MQ rami es only at one prime If we take a represen tative set 11 ah of ideals representing CooF7 under the above assumption that the projection Aj of 11 to P is independent modulo Ra in the following sense 31 AiAj a1 0a e MX ifz39 7 339 We can identify P with a subgroup of R Z which is isomorphic to Z by R gtlt REX 9 ab H ab 1 6 Z Thus the image of Aj E Z satis es A dye for 04739 E mod p generating 11 Choose Li 6 MAX with LgR 11 and a am 1 Consider S 8 We regard S as a p adic modular form Recall X XR over W and over W Wpnw lts formal group X is isomorphic to Em by the level H structure 7717 77 ppm Xp over lV7 we have a canonical identi cation 3 Em induced by 77 over W Then XW has a differential cup df writing m SpflVss 17 where Wml Wmlvan 7 1 The modular from S has t expansion with respect to the Serre Tate coordinate it around MR 6 00 Since 2 21 6 Tum2 R gtlt 1292 acts on ngA swim f by t H t1 we can think of 8tz7 which is only de ned over Gm Im Y p Since paxa MB for an idele a 6 MAX with up acO 17 we can think of Spa 1Enpw SEnp o pa 1w Then Spa 1 is a modular form with 5l0a 1XR777R7wR 5Xa7na7wa The automorphic proof of this theorem consists of the following two steps Step1 t expansz39on Essentially7 the t expansion of Z Aaj 18pa1tA1 gives the expansion of the p adic L function L putting it 1 T This follows from Katzls construction of the measure mainly his explicit relation of the invariant differentiation on Yzlp Gm with the Maass Shimura differential operator via the Gauss Manin connection If we write cup 7794 pr by a result of KatZShimura7 we have 6mm mwrlA gleam ZAW 1aZ 1 Ch6 k82kzm M0 A gt 7 TL sz2n sz2n sz2n sz2n 7 p where 9 737 3k is the Maass Shimura differential operator and An is a Hecke character whose in nity type is 2k n1 7 6 de ned modulo p and Wai MalAgl Thus the Lecture 6 Part I Professor Yau Allowable singularities and Compactifications To treat the class VII surfaces with b11 and b2 0 but with curves on the surface one needs to think about extending the idea of sections of bundles to sections with specified polar sets along the curves and metrics with singular sets of a certain type The basic idea comes from thinking about the metric of constant negative Gauss curvature on a compact Riemann surface with punctures other than CP1 if there is only one puncture One can compute easily enough what the expected form of the metric is near a puncture In a coordinate system where the puncture is at 20 it should look like 1 lzl 1n lzl 2 dx2 dy2 This form arises from noting that the upper half plane covers by fz exp iz the unit disc with 0 removed The pushdown of the Poincare metric on the upper half plane is a rotationally symmetric metric on the punctured unit disc and using the fact that the Poincare metric on the upper half plane is 1y2 dx2 dy2 one computes directly the form of the metric as given Here one notes that the y of the preimage of a point of absolute value r is flog r from which the log 2 term in the metric arises The Chem form for the holomorphic tangent bundle which is 7 127I Gauss curvature oriented area form in the Riemann surface case is easily computed to have finite integral in this case in polar coordinates one is integrating down to 0 the function 1r 1 1n r2 which has finite integral Looking at this carefully one sees that in fact the integral over the punctured surface of the first Chem form is the first Chem class of the line bundle corresponding to holomorphic 10 forms with at most simple poles at the punctures This is checked by a direct examination of the limiting behavior of integral at the puncture showing that each puncture adds 1 to what would be the negative of Euler characteristic integral while the degree of the bundle as described is simply the degree of the canonical bundle plus the number of punctures This whole observation can be transferred to higher dimensions with the distinguished points the punctures as it were replaced by curves or more generally divisors with normal crossings For instance for curves on a surface if a curve is defined locally by 210 then one allows differentials of the form f dzl 21 dzz In general one can look at this from the sheaf viewpoint and include in the normal crossing case of a curve defined by 2122 0 singularities for the differentials of the form f dzl 21 d2 22 This can be extended to higher dimensions as well One considers again a divisor with normal crossings and looks at singular metrics with the same Poincaretype singularities as described in other words sums of terms of the form 1 Izil 2 ln zi 2 dz 2 for each i from 1 to k ifthe normal crossing ofthe divisor is de ned by 21 zk 0 An Hermitian metric on a line bundle on the complement of the divisor in the manifold is called quotgoodquot Mumford s terminology if the curvature Fh arising from the h determined connection on L does not grow faster than the Poincare type of growth indicated In this case one can de ne integration of tr F11 Fh as a closed current in M Then the Chem forms defined as before represent the Chem classes of the extension of the bundle to allow singularities of the divisor type in exact analogy to the situation of divisors on Riemann surfaces This turns out to work in the situation of Hermitian symmetric spaces One takes an Hermitian symmetric domain Deg the Siegel upper half space of matrices of the form XiY where X and Y are symmetric and Y is positive definite Then one considers a quotient of the form M D F where F is a discrete group of holomorphic transformations of D The quotient may be compact or not but if noncompact is usually required to be of finite volume Then one forms compactif1cations of this quotient item What compactif1cation means in this case is more specific than just topological compactif1cation We require that M is a complex variety and M 7M is a subvariety of M so M is a quotZariski open set in the compactif1cation M There are a number of such compactif1cation BailleyBorel Satake But especially important for our purposes is the Mumford quottoroidal compactificationquot This is important because in this case M is smooth and M 7M has normal crossings Mumford showed that all natural bundles satisfy his quotgoodnessquot condition with natural metrics quotGoodnessquot here of course depends on the compactif1cation actually To understand class V110 case 2 one could try to look at a similar idea The examples known in fact look like HxC F quotient by a discrete group recall that F acts by affine linear transformations in this case The group does not preserve a metric fit is not quite like an Hermitian symmetric space case But it does preserve the affine structure It should be possible one hopes not done yet to do compactif1cation to get a situation where there is a complete metric outside a finite union of curves which is projectively at on the bundlewith singularitiesallowed considered earlier Ideas for complex dimension 3 First question Which manifolds have a complex structure with a Kahler form 03 having 66aquot1 0 Note that this does not always happen Last time we saw that the quot 66 quot Lemma gave a condition in principle intermediate on a compact manifold between being a Kahler manifolda complex manifold admitting a Kahler metric and just being a complex manifold Here is another such condition that a holomorphic 10 form is always closed On a compact Kahler manifold a holomorphic form or of type p0 is always closed for any pgt0 To see this consider the Hodge decomposition of or relative to 6 harmonic theory Since at is 6 closedit must be that or is the sum ofa form in the image of 6 and a 6 harmonic form But by types the image of 6 part is 0 So at is 6 harmonic and hence dharmonic and hence closed This is a global fact of course f dzl f a locally defined nonconstant holomorphic function 21 a local coordinate function is a holomorphic 10 form which is not closed This is actually implied by the quotbalancedquot condition we defined earlier that 6660 1 0 This is proved by integration by parts In detail recall that we showed earlier that I60 A r 0 if and only if Ia A 6139 0 and similarly that 6 and of course d itself can be quotmoved to the other sidequot This was a simple consequence of Stokes39 Theorem the two integrals are in fact always equal up to a sign Now consider for a balanced metric and a 10 holomorphic form 6 I66 A A mm HARMONIC ANALYSIS TERENCE TAO Analysis in general tends to revolve around the study of general classes of func tions often realvalued or complexvalued and operators which take one or more functions as input and return some other function as output Harmonic analysis1 focuses in particular on the quantitative properties of such functions and how these quantitative properties change when apply various often quite explicit operators A good example of a quantitative property is for a function being uniformly bounded in magnitude by an explicit upper bound M or perhaps being square integrable with some bound A thus f dz S Al A typical question in har monic analysis might then be the following if a function f R A R is square integrable and its gradient Vf exists and is also square integrable does this imply that f is uniformly bounded The answer is yes when n 1 no when n gt 2 and just barely no when n 2 this is a special case of the Sobolev embedding theorem which is of fundamental importance in the analysis of PDEi If so what are the precise bounds one can obtain Real and complex functions such as a realvalued function of one real variable I E R are of course very familiar in mathematics starting back in high school In many cases one deals primarily with special functions polynomials exponentials trigonometric functions and other very explicit and concrete functionsi Such func tions typically have a very rich algebraic and geometric structure and there are many techniques from those elds of mathematics that can be used to give exact solutions to many questions concerning these functions In contrast analysis is more concerned with general classes of functions functions which may have some qualitative property such as measurability boundedness continuity differentiability smoothness analyticity integrability decay at in nity etci ut which cannot be usefully expressed as a special function and thus has little or no algebraic or geometric structure These types of generic functions occur quite frequently for instance in the study of ordinary and partial differential equations since the solutions to such equations often cannot be given in an explicit algebraic orm but are nevertheless known to obey various qualitative properties such as differentiabilityi In other cases the functions can be very explicit and structured but for one reason or another it is dif cult to exploit this structure in a purely algebraic manner and one must rely at least in part on more analytical tools 1Strictly speaking this sentence describes the eld of realeiariable harmonic analysis There is another eld of abstract harmonic analysis which is primarily concerned with how real or complexevalued functions often on very general domains can be studied using symmetries such as translations or rotations for instance via the Fourier transform and its relatives this eld is of course related to realevariable harmonic analysis but is perhaps closer in spirit to representation theory and functional analysis and will not be discussed here 1 2 TERENCE TAO instead A typical example is the Airy function Aiz I ff ei g d5 which is given as an explicit integral but in order to understand such basic questions as whether Aiz is always a convergent integral and whether this integral goes to zero as I A ioo it is easiest to proceed using the tools of harmonic analysis In this case one can use the principle of stationary phase to answer both these questions affirmatively although there is the perhaps surprising fact that the Airy function decays almost exponentially fast as r A 00 but only polynomially fast as r A fool Harmonic analysis as a sub eld of analysis is particularly interested in the study of quantitative bounds on these functions For instance instead of merely assuming that a function f is bounded one could ask how bounded it is in particular what is the best bound M 2 0 available such that S M for all or almost all z E R this number is known as t e sup norm or L norm of f and is denoted H fHLooi Or instead of assuming that f is absolutely integrable one can quantify this by introducing the L1 norm I f dz more generally one can quantify p hpower integrability for 0 lt p lt 00 via the L17 norm I drypi Similarly most of the other qualitative properties mentioned above can be quan ti ed by a variety of norms which assign a nonnegative number or 00 to any given function and which provide some quantitative measure of one characteristic of that function Besides being of importance in pure harmonic analysis quantitative estimates involving these norms are also useful in applied mathematics for instance in performing an error analysis of some numerical algorithmi Functions tend to have in nitely many degrees of freedom and it is thus unsur prising that the number of norms one can place on a function are similarly in nite there are many ways one can quantify how large a function is These norms can often differ quite dramatically from each other For instance it is possible for a function f to have large L norm but small L1 norm think ofa very spiky function which is large on a very small set but zero elsewhere or conversely to have small L norm but large L1 norm think of a very broad function which is very small but spread out over a very large set Similarly if one compares the L2 norm with the L1 or L normsi However it turns out that the L2 norm lies in some sense between the L1 and L norms in the sense that if one controls both the L1 and L norms then one also automatically controls the L2 normi lntuitively the point is that L control eliminates all the spiky functions and L1 control eliminates most of the broad functions and the remaining functions end up being well behaved in the intermediate norm L2i More quantitatively we have the inequality Han Hfuifwui i which is a simple consequence of the algebraic fact that if S M then S This is a special case of Holder s inequality which is one of the fundamental inequalities in harmonic analysis the idea that control of two ex treme norms automatically implies further control on intermediate norms can be generalized tremendously and leads to the very powerful and convenient methods of interpolation theory which is another basic tool in harmonic analysis HARMONIC ANALYSIS 3 The study of a single function and all its norms eventually gets somewhat tire some thoug As in many other elds of mathematics the subject gets a lot more interesting when one not only considers these objects functions in isolation but also introduces maps from one object to another these maps which take one or more functions as input and returns another as output are usually referred to as operators or transforms Operators may seem like fairly complicated mathematical objects after all their inputs and outputs are functions which in turn have in puts and outputs which are usually numbers however they encode many natural operations one performs on these functions such as di erentiation M e fife and its wellknown partial inverse integration M e f y a A less intuitive but particularly important example is the Fourier transform M H fltzgt e2myfltygt dy lt1 It is also of interest to consider operators which take two or more inputs two particularly common examples are pointwise product fr79r H fryr7 and convolution ltfltzgtgltzgtgt H f gltzgt m fyyz 7 y at There are of course many other operators of interest in harmonic analysis His torically harmonic analysis was rst concerned with the operations that were con nected to Fourier analysis real analysis and complex analysis nowadays however the methods of harmonic analysis have been brought to bear on a much broader set of operators These techniques have been particularly fruitful in understanding the solutions of various linear and nonlinear partial differential equations with the solution being viewed as an operator applied to the initial data as well as in analytic and combinatorial number theory when one is faced with understanding the oscillation present in various expressions such as exponential sumsi Harmonic analysis has also been applied to analyze operators which arise in geometric mea sure theory probability theory ergodic theory numerical analysis and differential geometry A primary concern of harmonic analysis is in obtaining both qualitative and quan titative information about how these sorts of operators act on generic functions A typical example of a quantitative estimate is the inequality llfgllLoo S HgHL2 for all fg 6 L2 which is a special case of Young s inequality and is easily proven using the CauchySchwarz inequality as a consequence of this we have the qualita tive conclusion that the convolution of two L2 functions is necessarily continuous this is basically because the continuous functions form a closed subspace of L and because L2 functions can be approximated to arbitrary accuracy by smooth compactly supported functions We give some further examples of qualitative and quantitative analysis of operators in the next section 4 TERENCE TAO 1 EXAMPLE FOURIER SUMMATION To illustrate the interplay between quantitative and qualitative results we sketch some of the basic theory of summation of Fourier series which historically was one of the main motivations for studying harmonic analysis in the rst place In this section the function f under consideration will always be assumed be pe riodic with period 2 thus 27f for all z for instance f could be a trigonometric polynomial such as 3 sinz 7 2cos31i If f is also a continuous function or at least an absolutely integrable one then we can de ne the Fourier coefficients for all integers n by the formula A 1 27 I O fze mx dzi The theory of Fourier series then suggests one has the identity 00 fI Z 706quot n7oo but the rigourous justi cation of this identity requires some effort If f is a trigono metric polynomial ie a nite linear combination of functions of the form sinnz and cosnz then all but nitely many of the coefficients are zero and the identity is easily veri ed however the problem becomes more subtle when f is not a trigonometric polynomiali It is then natural to introduce the Dirichlet summation operators SN for N 01 2 3 i H by N A SNfz Z fnequotwi n7N One can then ask whether SNf necessarily converges to f as N A 00 The answer to this question turns out to be surprisingly complicated depending on how one de nes convergence and on what assumptions one places on the function For instance one can construct examples of continuous f for which SNf fails to con verge uniformly to f or even to converge pointwise however SNf will necessarily converge to f in the L17 topology for any 0 lt p lt 00 and will also converge point wise almost everywhere ie the set where pointwise convergence fails will have measure zero If instead one only assumes f to be absolutely integrable then it is possible for the partial sums SNf to diverge pointwise everywhere as well as being divergent in the L17 topology for any 0 lt p S 00 All of these results ultimately rely on very quantitative results in harmonic analysis and in particular on various L17 type estimates on the Dirichlet sum SNfz as well as the closely related maximal operator supNgt0 As these results are a little tricky to prove let us rst discuss a simpler result in which the Dirichlet summation operators SN are replaced by the Fej r summation operators FN de ned for N 1 2 i i by the formula 1 FN i NltSoiuSN71l HARMONIC ANALYSIS 5 One can verify the identity 7r sin2 N y 2 W Nsin2y2 Also it is easy to show that FNf converges uniformly to f whenever f is a trigono metric polynomial since this will imply that SNf f for all but nitely many values of Ni To extend this result from trigonometric polynomials to a larger class of functions such as continuous functions let us make the quantitative estimate llFNfHLw S HfHLw for all continuous periodic functions f and all N 2 1 Indeed from the triangle 2 inequality and the positivity of we have 7r sin2ny2 FN I lt l f gt 4 WNW But FN1 1 and the claim follows Using this quantitative estimate one can now deduce that FNf converges uniformly to f for any continuous To see this rst observe by the Weierstrass approximation theorem that given any continuous FNfI f1 i y dy Hle dy FN1IHfHL f and any 5 gt 0 there exists a trigonometric polynomial 9 such that igHLoo S 5 Applying the above estimate and the linearity of FN we also have HFNf 7 FNgHLoo S 5 for all Ni Finally since 9 is a trigonometric polynomial we have HgiFNgHLoo S 5 for all suf ciently large Ni By the triangle inequality we conclude that 7 FNfHLoo S 35 for all suf ciently large N and the claim follows A similar argument using Minkowski7s integral inequality instead of the triangle inequality shows that HFNfHLP S for all 1 S p S 00 f 6 L17 S As a consequence one can modify the above argument to show that FNf converges to f in the L17 topology for every f E L A slightly more dif cult result relying on a basic result in harmonic analysis known as the HardyLittlewood maximal inequality asserts that for every 1 lt p S 00 there exists a constant Cp such that one has the maximal inequality supN lFNleLp S CprHLP for all f 6 L17 as a consequence one can show that FNf converges to f pointwise almost everywhere for every f E L17 and 1 lt p S 00 A slight modi cation of this argument also allows one to treat the endpoint case when f is merely assumed to be absolutely integrable see the discussion on the HardyLittlewood maximal inequality in the next section Now we return brie y to Dirichlet quot Using t 1 39 quot techniques in harmonic analysis such as Calderon Zygmund theory one can show that when 1 lt p lt 00 the Dirichlet operators SN are bounded in L17 uniformly in N or in other words there exists a constant 0 lt C1 lt 00 such that HSNfHLp S CprHLp for all f E L17 and all Ni As a consequence one can show that SNf converges to f in the L17 topology for all f E L17 and 1 lt p lt 00 However the quantitative estimate on SN fails at the endpoints p 1 and p 00 and from this one can also show that the convergence result also fails at these endpoints either by explicitly constructing a counterexample or by using general results such as the uniform boundedness principle The question of almost everywhere pointwise convergence is signi cantly harderi It is known that one has an estimate 6 TERENCE TAO of the form supN lSNleLp S CprHLP for l lt p lt 00 this result the Carleson Hunt t eorem imp ies in particular that the Dirichlet sums of an L17 function converge almost everywhere when l lt p S 00 On the other hand this estimate fails at the endpoint p l and in fact there is an example of Kolmogorov of an absolutely integrable function whose Dirichet sums are everywhere divergenti These results require quite a lot of harmonic analysis theory in particular using man decompositions of both the spatial variable and the frequency variable keeping the Heisenberg uncertainty principle in mind and then reassembling these pieces carefully and exploiting various manifestations of orthogonalityi To summarize quantitative estimates such as L17 estimates on various operators provide an important route to establishing qualitative results such as convergence of certain series or sequences In fact there are a number of principles notably the uniform boundedness principle and Stein s maximal principle which assert that in certain circumstances this is the only route in the sense that a quantitative estimate must exist in order for the qualitative result to be true 2 SOME GENERAL THEMES IN HARMONIC ANALYSIS DECOMPOSITION OSCILLATION GEOMETRY One feature of harmonic analysis methods is that they tend to be local rather than global for instance it is quite common for a function f to be analyzed by applying cutoff functions in either the spatial or frequency variables to decompose f into a number of localized piecesi These pieces would then be estimated separately and then recombined lateri One reason for this divide and conquer strategy is that a generic function f tends to have many different features eg f could be very spiky discontinuous or high frequency in some places and smooth or low frequency in others and it would be dif cult to treat all of these features at once A well chosen decomposition of the function f can isolate these features from each other so that each component only has one salient feature that could cause dif culty In reassembling the estimates from the individual components one can use crude tools such as the triangle inequality or more re ned tools for instance those relying on some sort of orthogonality or perhaps a clever algorithm that groups the components into manageable clusters The main drawback of the decomposition method other than aesthetic concerns is that it tends to give bounds that are not quite optimal however in many cases one is content with estimates which differ from the best possible one by a multiplicative constanti To give a simple example of the method of decomposition let us consider the Fourier transform of a function f R A C de ned for suitably nice functions by the formula flt5gt Rfze 2m dz From the triangle inequality it is clear that if f lies in L1 then f lies in L i The Plancherel theorem implies among other things that if f lies in L2 then f also lies in L The question is then what happens if f lies in an intermediate L17 space for some I lt p lt 2 Since L17 is not contained in either L1 or in L2 one HARMONIC ANALYSIS 7 cannot use either of the above two results directly However by decomposing f into two pieces one supported on where f is large eigi where 2 A for some suitable threshold A and one where f is small eigi lt A then one can apply the triangle inequality to the rst piece which will be in L1 since S lfzlpp 1 here and the Plancherel theorem to the second piece where S AQ pl z p to obtain a good estimate Indeed by utilizing this strategy for all A and then combining all these estimates together one can obtain the Hausdor Young inequality which asserts that for every 1 lt p lt 2 there exists a constant Op such that HfHLP S CprHLp for all f 6 L17 where p I pp 71 is the dual exponent to p This particular decomposition method is an example of the method of real interpolation It does not give the best possible value of Op which turns out to be p12pp12p and is computed by more delicate methodsi Another basic theme in harmonic analysis is the attempt to quantify the elusive phenomenon of oscillation lntuitively if an expression oscillates wildly in phase then its average value should be relatively small in magnitude For instance if a 27r periodic function f is smooth then its Fourier coefficients if fze im will be rapidly decreasing as n A ioo in other words limnniDo 0 for any xed h This assertion is easily proven by repeated integration by parts Generalizations of this phenomenon include the principle of stationary phase which among other things allows one to obtain precise control on the Airy function Aiz discussed earlier as well as the Heisenberg uncertainty principle which relates the decay and smoothness of a function to the decay and smoothness of its Fourier transformi A somewhat different manifestation of oscillation lies in the principle that if a se quence of functions oscillate in different ways then their sum should be smaller than what the triangle inequality would predict For instance the Plancherel theorem in Fourier analysis implies among other things that a trigonometric polynomial EnSN cneim has an L2 norm of 1 27r N N Z Cneinr 212 Z Cyl 2127 0 n7N n7N which is smaller than the upper bound of ESSN lcnl that can be obtained from the triangle inequality This identity can be viewed as a special case of Pythagoras theorem together with the observation that the harmonics em are all orthogonal to each other with respect to the inner product ltfggt I few dzi This concept of orthogonality has been generalized in a number of ways for instance to a more general and robust concept of almost orthogonality which roughly speaking means that a collection of functions have inner products which are small rather than vanishing completely Many arguments in harmonic analysis will at some point involve a combinatorial statement about certain types of geometric objects such as cubes balls or boxes For instance one useful such statement is the Vitali covering lemma which asserts that given any collection B1 i i i Bk of balls in Euclidean space B there exists a subcollection of balls Bil i i i Bim which are disjoint and furthermore contain a Unitary representations of super Lie groups V S Varadarajan University of California L03 Angeles USA vsvmathuclaedu H Super manifolds and super Lie groups E0 The category of unitary representations of a super Lie group 9 Super systems of imprimitivity on purely even super homoge neous spaces F Representations of super semi direct products QTY Super particles and their multiplet structure 1 Super manifolds and super Lie groups 11 Introduction Supersymmetry was discovered by the physi cists in the early 1970s Since then an enormous effort has been devoted to constructing supersymmetric versions of the fundamental theories of elementary particles their fields and their interactions In these and the other lectures in this conference an attempt is being made to give a sys tematic account of the mathematical aspects of supersymmetry Everyone knows that the idea of symmetry and the role of group the ory in describing it goes back to very ancient times However it was only in the twentieth century that it became possible to erect a fully satisfactory mathematical theory namely the theory of Lie groups and their repre sentations that was adequate and powerful for all the applications This theory based on differential and algebraic geometry was one of the ma jor achievements of mathematics in the last century But in the 19707s 1 the physicists driven by the desire to explain the main features of the physical world at the most fundamental level came up with a rather re markable generalization of symmetry in particular spacetime symmetry that went beyond conventional limits Indeed the idea that one can gen eralize the notion of symmetry of spacetime beyond what was known for centuries is extraordinary and one has to thank the physicists for their daring and imagination to have come up with such a generalization The effort to build a proper mathematical foundation for the discoveries of the physicists led to the development of an entirely new part of mathematics namely the theory of super manifolds and super Lie groups This is a development of geometry beyond its conventional limits and it is not clear at this time in what directions it will continue in the future Certainly the happenings in the world of elementary particles and their fields will have a lot to say about the future growth of what may be called super geometry From the historical point of view it is remarkable that already in 1854 Riemann in his Gottingen inaugural address had speculated on the structure of space in its microscopic parts and raised the possibility that the manifold structure may not be present in the infinitely small parts He also advocated the point of view that we have to look for physics to tell us what this micro structre should be Here is what he wrote Now it seems that the empirical notions on which the metric deter minations of Space are based the concept of a solid body and a light ray lose their validity in the in nitely small it is therefore quite def initely conceivable that the metric relations of Space in the in nitely small do not conform to the hypotheses of geometry and in fact one ought to assume this as soon as it permits a simpler way of ezrplaining phenomena An answer to these questions can be found only by starting from that conception of phenomena which has hitherto been approved by ezrperience for which Newton laid the foundation and gradually modifying it under the compulsion of facts which cannot be ezrplained by it Investigations like the one just made which begin from general concepts can serve only to ensure that this work is not hindered by too restricted concepts and that the progress in comprehending the connection of things is not obstructed by traditional prejudices The beginnings of supersymmetry can be traced to quantum field theory in which the Hilbert space of one particle states is an orthogonal 2 direct sum H H0 69 H1 here the vectors of H0 resp H1 de ne the states where the particle is a Boson resp Fermion Supersymmetries then became transformations that exchanged the Bosonic and Fermionic states In mathematical terms one may say that the Hilbert spaces of quantum eld theory are Z2 graded The attempt to have a uni ed way of treating this dual aspect of fundamental particles soon led to linear algebra over Zg graded spaces namely vector spaces with a distinguished decomposition into odd and even subspaces However the essential point of departure came when physicists like Salam and others realized that one has to construct a graded generalization of classical geometry itself so that after quantization one obtains the graded Hilbert spaces so characteristic of quantum eld theory Now the manifolds in classical geometry are non linear and are studied using local coordinates The ideas of Salam and others then led to the creation of a generalization of classical geometry in which the usual local coordinates were supplemented by a set of Grass mann coordinates The heuristic meaning of the Grassman coordinates was that they encoded the fermionic aspects of matter in particular the Pauli exclusion principle that is at the basis of all properties of matter in the bulk The automorphisms of such super manifolds were to be viewed as the supersymmetries which on quantization led to the Fermi Bose sym metries of quantum eld theory Because of the novelty and conceptual dif culty of this type of generalization of classical geometry the notion of supersymmetry was formulated at first only in nitesimally based on the concept of a super Lie algebra Indeed the concept of a super Lie alge bra itself was born in the attempts by physicists to formulate this type of symmetry Once the concept of supersymmetry was formulated albeit in nitesimally the goals of the physical side of the theory became clear to work out electrodynamics and more generally Yang Mills theories and Einstein gravity under the umbrella of supersymmetry The structure of these supersymmetric theories is such that they offer many advantages over conventional theories softer divergences reduction of possible La grangians and so on Although the global as opposed to in nitesimal formulation of supersymmetry was implicit in the physical theories it was not fully revealed because of the dif culties in capturing the notion of super Lie groups as opposed to the technically much simpler notion of super Lie algebras In order to understand properly the global geometric nature of super manifolds and supersymmetry it is necessary to look more closely at the nature of super geometry as a profound generalization of classical differen 3 tial geometry and the age old problem of the structure of the space we live in The development of classical geometry which goes back to Euclid in ancient times started in the modern era with Riemann7s discovery of Rie mannian geometry evolving ultimately into the modern theory of smooth manifolds and its algebraic counterpart namely Grothendieck7s theory of schemes Supersymmetry through the concepts of a super manifold and a super scheme continues this evolutionary development in an entirely new direction It adds to the usual commuting local coordinates an additional set of anti commuting Grassmann coordinates which cannot be seen nu merically but which play a fundamental role in determining the theories that are possible on a spacetime with such a local structure However the presence of the Grassmann coordinates which are nilpotent and invisible has the consequence that the mathematics of the theory of super manifolds can be developed cleanly only by using the methods and techniques that Grothendieck has created in modern algebraic geometry especially the theory of schemes This method called the functorial method by math ematicians is in fact extremely transparent and is the one that mirrors completely all the calculations that the physicists make so much so that one can have the advantage of working in the informal way that is most characteristic of physics and yet lose nothing in mathematical rigor These lectures are in three parts In the first part l 3 which is foundational I shall try to make precise the concept of a super manifold and its automorphisms the supersymmetries and explain the functorial method based on the functor of points This leads naturally to the concept of a super Lie group and the associated concept of a super Lie algebra I shall then discuss the concept of a unitary representation of a super Lie group In the second part 4 I shall discuss the super semi direct products and their irreducible unitary representations In particular I shall set up the super version of the Mackey Wigner machine of little groups In the last part 5 I shall apply this theory to describe the super spacetimes and the super Poincare groups in all dimensions Minkowski signature their unitary irreducible representations and the applications to the classification of super particles and super multiplets 12 The category of ringed spaces If X is a classical smooth 00 in nitely differentiable manifold then for each open set U C X we have the R algebra O U of smooth real functions on U The property of smoothness is local and the mathematical concept that captures this is 4 that of a sheaf expressed by saying that the assignment U gt gt 00 U is a sheaf of functions The rings O U are the local rings lf XY are two smooth manifolds a morphism ie a smooth map from X to Y is a continuous map 11 of X to Y such that for each open U C Y the pull back map 1quot is a homomorphism of O U into O 1U In this way we have the category of smooth manifolds and smooth maps But in order to de ne supermanifolds where there are Grassmann coordinates locally that are numerically unobservable the above notion of a sheaf of functions has to be generalized signi cantly in two steps The first step of such a generalization is already present in the notion due to Grothendieck of a ringed space This is obtained by giving up the idea that the local rings consist of numerical functions defined on open sets U but are rather abstract commutatiue rings denoted usually by OXU Unlike numerical functions the elements of these abstract local rings cannot be restricted to open subsets and so we have to build the restriction maps as a part of the data defining a ringed space Thus for open sets U V with V C U we have restriction maps OxU 0xV f H fIV with the property that if W C V C U are open the restriction from U to W is the same as restricting rst to V and then to W The local nature of these functionsllis expressed by the requirement that the assignment Ugt gt OXU is a sheaf of rings The sheaf axiom which is the exact encoding of locality is the following if U is an open set and is an open covering of U and if fi 6 OXUZ are given then the following two statements are equivalent a there is a unique element f E OXU such that f U fi for all indices i b for any two indices i1i2 fil Of OXU1 as elements Uil Ui2 fi2 Uil UiQ A ringed space is thus a pair X OX 0 where X is a topological space and O is a sheaf of commutative rings on X A morphism of a ringed space X into a ringed space Y is a continuous map 11 X a Y together with a 5 pull back map 1quot of Oy into OX above 11 this means that for each open U C Y 1quot is a homomorphism of OyU into OX 11 1U Notice that unlike the case when the rings of the sheaves are rings of functions the pull backs 1quot for any open set U C Y have to be speci ed as part of the data de ning morphisms and that these pull backs have to be compatible with restrictions One thus obtains the category of ringed spaces and their morphisms One may view the open sets in X as a category where the set of morphisms from U to V is empty unless U C V in which case it consists of the natural inclusion of U in V Then a presheaf is a contravariant functor from the category of open sets in to the category of rings and the morphisms of ringed spaces are natural transformations between these functors Super manifolds are generalizations of ringed spaces In order to introduce these we have to make the second step of the generalization mentioned above In the concept of a ringed space introduced above we have made the assumption that the local rings are commutative How ever to reach the concept of a super manifold or more generally a super geometric object such as a super ringed space we must give up the com mutativity assumption on the local rings and make them more general at least general enough to include the algebras in the commutative and Grassmann coordinates characteristic of the physicists7 supersymmetric description of space time and matter Moreover in order to encode the fact that the supersymmetries exchange the classical and Grassmann co ordinates we must make sure that the local rings do not contain any more information other than the possibility that local Grassmann coordinates can be introduced It turns out that the correct condition is that the local rings are super commutative This means that they are Z2 graded and commutative in the super sense that is instead of the relation ab ba between arbitrary elements of the ring we will have ab iba where the sign is always plus unless both a and b are odd in which case the minus sign is taken Thus a super ringed space is a pair X OX where OX is a sheaf of super commutative rings on the topological space X A super manifold is a super ringed space with the property that X is a classical smooth manifold and that locally the sheaf looks like the sheaf of rings on RP of the form U l Ai 1552w75ql 6 where the 5 are Grassmann variables satisfying 530 sews0 lt j12qgt so that M51 q is the exterior algebra over R in q indeterminates The reader who is familiar with quantum field theory will recognize in the requirement of super commutativity for the local rings the idea that to make the transition from a description of classical elds to Fermi fields one should replace the classical commutators by anticommutators It is clear that one can formulate the notion of a real analytic or even a complex analytic super manifold by replacing the underlying classical manifold by a real or complex analytic super manifold The natural end of this line of thought is the concept of a super scheme 13 The category of super vector spaces and super algebras If A is an abelian group and we have a direct sum decomposition A GBAZEI we say that A is graded by I if I itself is an abelian group and AiAj C Ai v for ij E I The AZ are sometimes referred to as the homogeneous components of A The most common index group I is Z the ring of integers If V is a vector space and SVEV are the symmetric and exterior algebras of V then SV and EV are graded in a natural manner by Z In supergeometry grading by Z2 Z2Z is fundamental if A is Z2 graded the elements of A0 are called even and those of A1 are called odd The infinitesimal structure of a super manifold at a point is captured by the properties of the category of super vector spaces namely the cat egory of Zg graded vector spaces This is a category with direct sum 69 dual and tensor product 8 and is a prime example of a tensor category where the objects are abstract and the category has the three operations above with suitable functorial properties that imitate those of the vector space category In particular we have isomorphisms cUV CUV I U E V E V E U which through various requirements such as the hexagon axiom capture the essential properties of the isomorphisms in the vector space category There the isomorphisms are given by cUV zu v gt gt 71pup v 81 a E Uv E V 7 Here pac is the parity of x and is either 0 or 1 These structural as sumptions explain all the characteristic features of the practical use of super vector spaces sign rule de nition of super commutativity super Lie algebras and so on Moreover they hide77all the signs in the various de nitions In what follows we shall discuss a few of these The reader should note that almost everything makes sense for abstract tensor cate gories and this more general interpretation gives great insight Finally the eld over which all vector spaces and more generally the tensor category is de ned is assumed to be of characteristic 0 in applications it is either R or C For instance an algebra in the super category is an object A with a map M A 8 A a A It is commutative which means super commu tative if M M o 0AA For super vector spaces this means the relation ab ilp pbba between any two elements a b of A a first example of the sign rule in any classical formula whenever two odd elements are in terchanged there should appear a minus sign The Guy can be generalized to an action of the symmetric group 6N in N letters on V 8 V 8 8 V N factors A Lie algebra in the tensor category is an algebra object g with multiplication denoted by having the properties l a 0w 0 in lulllt1 002 0 where o is the automorphism of g 8 9 8 g induced by the permutation 123 a 312 If we unscramble these de nitions we obtain the usual working de nition of a super Lie algebra Historically super Lie algebras first came up in the work of the physicists when the first supersymmetric infinitesimal transformations were written down Gol7fand Likhtman and Volkov Akulov discovered the minimal SUSY extension of the Poincare Lie algebra in the early 1970s Wess Zumino discovered a little later in 1974 the first example of a simple super Lie algebra namely the minimal SUSY extension of the conformal Lie algebra In 1975 V Kac formally defined super Lie algebras and carried out the super version of the Cartan Killing classi cation of simple Lie algebras over C Super Lie algebras A Lie super algebra or super Lze algebra is a super vector space g with a bracket l which is a morphism from g 8 g to g with the following properties a la bl 771gtPltagtPltbgtb a b The super Jacobi identity la lb all lt71gtPltagtipltbgtPltCgt1 lb la an lt71gtPltCgtipltagtPltbgt1 0 la bu 0 One can hide the signs above by rewriting these relations as we did previ ously using egg and the action of 63 on g g g Thus b shows that the super Jacobi identity has the same form as the ordinary Jacobi identity for ordinary Lie algebras Thus the super Lie algebra is defined in exactly the same manner in the category of super vector spaces as an ordinary Lie algebra is in the category of ordinary vector spaces It thus appears as an entirely natural object One might therefore say that a super Lie algebra is a Lie object in the category of super vector spaces There is a second way to comprehend the notion of a super Lie algebra which is more practical The bracket is skew symmetric if one of the elements is even and symmetric if both are odd The super Jacobi identity has 8 special cases depending on the parities of the three elements 1 b c If all three are even the definition is simply the statement that go is a ordinary Lie algebra The identities with 2 even and 1 odd say that g1 is a go module The identities with 2 odd and 1 even say that the bracket 91 91 A90 is a symmetric gO map Finally the identities for all three odd elements reduce to 1bc0 1bc g1 where is cyclic summation in 1 b c It is not dif cult to see that the last requirement is equivalent to 1 1 1H 0 1 6 Q1 Thus a super Lie algebra is a super vector space g on which a bilinear bracket is defined such that a go is an ordinary Lie algebra for b g1 is ago module for the action 1 gt gt ad1 b gt gt 1 b b 6 Q1 c 1 b gt gt 1 b is a symmetric gO module map from g1 g1 to go d For all 1 E g1 we have 1 1 1 0 Except for d the other conditions are linear and can be understood within the framework of ordinary Lie algebras and their representations The 9 condition d is nonlinear and is the most dif cult to verify in applications when Lie super algebras are constructed by putting together an ordinary Lie algebra and a module for it satisfying a c If A is a super algebra we define 1 b ab 7 71papbba a b e A It is then an easy verification that converts A into a super Lie algebra It is denoted by AL but often we omit the suf x L If A EndV we often write gV for the corresponding Lie algebra if V Rpiq we write MN for NV Let g be a super Lie algebra and for X E g let us define adngeg adXYXY Then ad X gt gt ad X is a morphism of g into gg The super Jacobi identity is just the relation ad X ad Y ad XY XY e g The development of super linear algebra including the theory of mod ules over super commutative rings has no real surprises till we come to the generalization of the determinant the Berezz m an Let R be a super commutative algebra over a field k of characteristic 0 and Rpiq be the free module of dimension pig over B Let GLpiqR be the group of invertible even morphisms of Rpiq Then the Berezinian is a morphism of GLpiqR into BOX the group of units of the even part R0 of R given by Berac detA a BD lO detD 1 g g Beracy BerxBery where We have This is the superversion of the determinant discovered by F A Berezin one of the pioneers of super algebra and super analysis Since the entries 10 of B and O are nilpotent x is invertible if and only if A and D whose entries are in the commutative ring R0 are invertible The usual deter minant in the commutative category can be interpreted as the result of an action on the top part of the exterior algebra for the super category the generalization of such an interpretation is homological and lies at a deeper level 14 Properties of super manifolds We outline in brief some of the properties of the category of super manifolds Functor of points Exactly as in the theory of schemes there is another notion of points of a super manifold which is the true geometric one Let X be a super manifold For any super manifold T we write XT for the set of maps T 6 X and view the elements of XT as the T points of X If T is a single point viewed as a purely even manifold XT is the set of topological points of X XT is a contravariant functor in T and for any super manifold Y the set HomX Y can be recovered precisely as the set of natural transformations XT a YT Yoneda7s lemma One can use this to de ne the products of super manifolds the product X1 gtlt gtlt XN is the super manifold whose T points are X1T gtlt gtlt XN In this context we introduce the usual de nition of when a contravariant functor T gt gt fT is representable namely when there is a super manifold M such that MT fT Morphisms Because the local rings 00 151 xp61 qu are not algebraically generated by the 1 xp61 q one has to be ap parently careful in defining morphisms Actually the situation is exactly as in the algebraic case and this is the reason why the theory of super manifolds can be developed for the most part as the theory of classical manifolds lf MN is a super manifolds and 1 xp 61 Qq are coor dinates on N to define a morphism from M to N it is suf cient to specify the images of th mi 6 Differential calculus Because of the above result on morphisms one has a theory of differentiation on super manifolds that is completely analogous to the theory on classical manifolds The differential criteria for a map to be a local diffeomorphism the structure of submanifolds etc remain essentially the same Integral calculus Let 91 9i16i2eik I iHi1 lt i2 lt lt ik ll On the integral is a linear map agt gt adq6 0 iflIlltq 91M l ifIQl2q Integration is also differentiation 1 In the local ring with coordinates f b sdpxdq63deac 828161 I de ned by The change of variables formula For a morphism given locally as WWH two we de ne the Jacobian matrix Then s wltsgtBerltJwgt for compactly supported sections of the local ring For arbitrary mani folds we use partitions of unity as in the classical case This beautiful formula goes back to Berezin The justification for the peculiar definition of integration in the anticommuting variables is the change of variables formula The global section functor Finally we have the global section functor which associates to any 00 manifold M the super algebra AM of global sections namely AM OM It is possible to show that 12 M can be recovered from AM more precisely the functor of globals sections is fully faithful Heuristic conception of a super manifold ln calculations with super manifolds physicists work with coordinates and manipulate the odd variables more or less on the same footing as the classical commuting coordinates The functor of points approach is essentially a way to make sense of such calculations The intuitive picture of M is that of a classical smooth manifold surrounded by a grassmannian cloud The cloud cannot be seen in any measurement the odd variables will be 0 because they are nilpotent Thus measurement sees only the underlying classical manifold lM Nevertheless the presence of the cloud eventually has consequences that are striking 15 Super Lie groups and their Lie algebras Super Lie groups are group objects in the category of super manifolds Thus to say that G is a super Lie group is to say that G is a super manifold and that we have morphisms MGgtltGgtG LZG G that have the associativity properties usually ascribed to multiplication and inverse together with the identity element 6 point a G From the perspective of functor of points the functor GT takes values in groups so that a super Lie group may be defined as a contravariant functor from the category of super manifolds to the category of groups which is representable The theory of super Lie groups may be built up in the same way as the theory of classical Lie groups but some of the technical aspects become more involved because things have to be done using the functor of points One can define on any super Lie group the notion of left or right invariant vector fields and hence the notion of a Lie algebra of a super Lie group This is a super Lie algebra and the correspondence between G and its super Lie algebra g has essentially all the features of the classical correspondence Super HarishChandra pairs Of great importance for us is a theorem which allows one to describe a super Lie group in more concrete l3 terrns Given a super Lie group G we have a pair G0g Where G0 is the classical Lie group underlying G and g is the super Lie algebra of G We have 1 go 2 G0 has an action on g and its differential is the adjoint action of go on 9 Such pairs Gog can be also introduced a priori Without reference to a super Lie group They are then called super Ham39sh C39handm pairs The basic theorem Which is fundamental for us is the result that G l 0079 is a covariant functor Which is an equivalence of categories from the cate gory of super Lie groups to the category of super Harish Chandra pairs 2 The category of unitary representations of a super Lie group 21 Introduction The study of unitary representations of super Lie algebras began not long after super Lie algebras were discovered and clas si ed However unitary representations of super Lie groups are a different story because of the subtle manner in which a super Lie group differs from an ordinary Lie group and their study has lagged far behind that of the representations of super Lie algebras In this section I shall discuss how to make the correct de nition for a unitary representation of a super Lie group It seems likely that further developments of the representation the ory of super Lie groups will require a theory of representations of super Lie groups in Banach and even Frechet spaces but we shall not take up these generalizations here Our point of view is that a super Lie group may be identi ed with a super Harish Chandra pair G0g This is reasonable since as we saw earlier the category of super Lie groups is equivalent to the category of super Harish Chandra pairs Let me recall that G0g is a super Harish Chandra pair if G0 is a classical Lie group and g is a super Lie algebra with an action of G0 on it such that i LieG0 go the even part of g ii The action of G0 on g is the adjoint action of G0 more precisely the adjoint action of go on g is the differential of the action of G0 on g We shall make no distinction between super Lie groups and super Harish Chandra pairs If we carry over this principle to representations we are led to the idea that a representation of a super Lie group G0g may be thought of as a triple 71390 yH where 71390 is an even representation of G0 in a super Banach or Frechet space H this means that 7r0g is even for all g 6 G0 and y is a super representation of g in H compatible with 71390 We shall only be interested in the case of unitary representations This means that H is a super Hilbert space 71390 is unitary and y satisfies an appropriate condition that re ects the unitarity of the representation It turns out that one should require that yX be skew self adjoint in the super sense for all X E g There is in addition a technical point for X E m XX 6 go and yX 2 yX2 and so the operators E g1 will in general be unbounded this means that there are 15 domain considerations to be taken care of In the next section we shall address both these points 22 The basic de nitions All sesquilinear forms are linear in the first argument and conjugate linear in the second opposite to the physicists7 convention regrettablyl A super Hilbert space is a Zg graded Hilbert space H where the Hil 0 l are closed mutually orthogonal subspaces If at ygt is defined as lpmpy y then ltx ygt is an even super Hermitian form For bounded operators T H 6 H the adjoint with respect to the super form is denoted by Tl and is related to the usual Hilbert space adjoint by Tl T or ilT according as T is even or odd We de ne Tl for unbounded T by this rule in terms of Tquot In order to motivate our definition of unitary representations of super Lie groups we begin by observing that in the even case of an ordinary Lie group the unitarity of a representation 7r of it is usually expressed at the in nitesimal level as follows if d7r is the representation of the Lie algebra then for all X in the Lie algebra the operators d7rX are skew Hermitian If we carry this over to the super setting the condition should be that the d7rX should be skew super Hermitian for all X E g This means that for X 6 go we should require that d7rX should be skew Hermitian while for X 6 Q1 we should have d7rX ild7rX ignoring domain considerations Let C eiiw l Then this last condition can be written as the condition that pX CdWX X E 91 be Hermitian symmetricThus at the formal level we define a unitary rep resentation of G0g to be a triple W0 yH where 71390 is an even uni tary representation in a super Hilbert space H y is a representation of g that is compatible with the action of G0 on g with y d7r0 on go and pX C yX Hermitian symmetric for all X E g1 In other words unitary representations are triples 71390 p H with the appropriate compat ibility and symmetry conditions described above To make this definition precise we have to bring in the domains of the operators pX for X E m It is natural to start with the assumption that they should have a common dense domain Initially we shall suppose that this domain is the space of all differentiable vectors for 7r0 but this will 16 be relaxed later and we shall see that even if one starts with a different domain the compatibility and symmetry conditions force the operators E g1to be well de ned on the space of all di erentiable vectors for no We therefore make the following de nition A unitary representa tion of a super Lie group G0g is a triple n0p7l with the following properties i no is an even unitary representation of G0 in the super Hilbert space ii p is a linear map of g1 into the subspace of odd endomorphisms of O 7r0 Here 00 7r0 is the space of differentiable vectors for no it is super linear ie it contains the odd and even components of each of its elements iii p satisfies the requirements below a Plt90X 77090PX7709071 X 6 9190 6 Go compatibility o pwit 71390 pX with domain 00 7r0 is symmetric for all X E g1 This means that the adjoint pX is an extension of pX for X E g1 lt fidvroaxm pltXgtpltYgt pltYgtpltXgtltXY e m on owe Theorem 1 If n0p7l is a unitary representation of G0g then for any X E g1 the operator pX with domain 00 7r0 is essentially self adjoint and T O V 7139 XO X1 H d7r0X0 C 1pX1X0 e g0X1 6 Q1 is a super representation of the super Lie algebra g in 00 7r0 compatible with no The choice of 00 7r0 as the domain for the operators pX while natural might seem arbitrary For instance one might use the analytic uectors instead of the differentiable ones It turns out that this objection is illusory ie any alternative system leads always to a unitary represen tation in the above sense This makes it clear that in spite of appearances our de nition of a unitary representation of a super Lie group is a very vi able notion To make these remarks more precise let us consider a system no p BH with the following properties i 8 is a dense super linear subspace of H invariant under no no being an even unitary representation of GO in the super Hilbert space H 17 Moreover B C Dd7r0Z for all Z 6 g1g1 DA denoting the domain of the operator A Here for any Z 6 go we write 4id7r0Z for the unique self adjoint operator in H such that 7r0exp tZ exp td7r0Z for all t E R Each pX for X E g1 is a linear operator in H with 8 C DpX such that X gt gt pX is a linear map of g1 into Hom8H More over H H a pX is symmetric for all X 6 Q1 C PXBz39 C Hi1mod 2 for all X E 91 d p is compatible with 7r0 ie Wo9pX7ro9 1 99X oanor g E G0X E g1 e pXB C DpY for all XY 6 Q1 and fidWoGX Yl pXpY pYpX for all XY E g1 on 8 Theorem 2 Let 71390pBH be as above Then for anyX 6 Q1 pX is essentially self adjoint on B and 00 7r0 C Let us write X for the restriction of pX to O 7r0 Then W0FH is a unitary rep resentation of G0g If 71390pH is a unitary representation of G0g such that B C DpX and pX restricts to pX on B for all X 6 Q1 then p E Remark For operators AB in H write A 4 B if DA C DB and B coincides with A on DA Let A be a densely de ned symmetric operator which is essentially self adjoint Then A the closure of A which exists because A is symmetric is the unique self adjoint extension of A moreover ifB is any symmetric operator such that A 4 B we haveA B so that A 4 B 4 A B Thus as a consequence of the first statement in Theorem 2 we see that extension by closure of pX is self adjoint and its domain contains O 7r0 This is the key fact in the theorems In the classical theory of representations of semi simple or reductive Lie groups the K nite vectors play a decisive role The space of K finite vectors although in general a subspace of the space of analytic vectors is not invariant under the group but only under the Lie algebra So it would 18 appear useful to have a variant of Theorem 2 where B is a subspace of O 7r0 the space of analytic vectors of no with B stable under g rather than G0 We then have the following theorem Theorem 3 If 71390p7 is a unitary representation of G0g then the pX for X 6 Q1 map O 7r0 into itself and 7r as in Theorem 1is a representation ofg in O 7r0 Let Go be connected let 8 be a dense super linear subspace of O 7r0 and let 7r be a representation ofg in B such that 7rZ 4 d7r0Z for all Z 6 go and pX 7139X symmetric for X 6 Q1 Then for any X 6 Q1 pX is essentially self adjoint on B and 00 7r0 C Let us write X for the restriction of pX to O 7r0 Then W0EH is a unitary representation of G0g Finally if 71390pH is a unitary representation of G0g such that B C DpX and pX restricts to pX on B for all X 6 Q1 then p p With these theorems we have realized our objective namely to in troduce a viable category of unitary representations of a super Lie group A morphism from H 71390p7 to H 7r6pH is a bounded linear map AH a H that intertwines 7r07rJ and pp Note that as soon as A intertwines g and 7T6 it maps 00 7r0 into O 7r6 and so the statement that A intertwine p p makes sense If A an isomorphism and unitary we speak of unitary equivalence H is a subrepresentation of H if H is a closed graded subspace of H invariant under 7r0 H 00 7r0 is invariant under p and 716 resp a is the restriction of g resp p to H resp H C 7r0 If H is a proper nonzero subrepresentation of H H HL and 71396 is the restriction of g to H then 00 7r0 is the direct sum od 00 7r6 and O 7r6 and it follows from the essential self adjointness of E g1 that O 7r is stable under all the pX if p is the restriction of p to O 7r6 then H 2 n3 p H is a unitary representation of G0g and H H 69 H H is irreducible if the only subrepresentation of H that is non zero is H itself We have the following theorem Theorem 4 H is irreducible if and only if HomH H C Let H be a unitary representation of G0g and let PX be the spectral measure of pX for X 6 Q1 If H is a closed super linear subspace of H then the following statements are equivalent a H is stable under g and H 00 7r0 is stable under all E g1 b H is stable under g and all the projections Pg F Borel and C R In particular H 19 is irreducible if and only if there is no nonzero proper closed super linear subspace invariant under no and all Pf X E g1 23 Some comments on the proofs The most striking aspects of the above theorems are the essential self adjointness of the pX X E g1 and the fact that 00 7r0 C It is clearly because of these facts that no matter what subspace B we start from all the operators pX extend naturally to 00 7r0 and we obtain a unitary representation in the precise sense we have de ned I shall try to explain the idea behind proving these facts First let us introduce some definitions lf A is a closable operator and D C DA a dense linear subspace we say that D is a core for A if A is the closure of its restriction to D Let A be symmetric We say that a vector 11 E DA is analytic for A if 11 E DA for all n and the series 7 W converges for some t gt 0 It is a well known result that if A C DA contains a dense set of vectors analytic for A then A is essentially self adjoint and A is a core for A In SUSY quantum mechanics the key assumption is that the Hamilto nian H L2 L being an odd symmetric operator It is usually suggested that this assumption implies the positivity of the energy operator H Ac tually this condition has deep consequences not just to the positivity of the energy but to our entire theory Let us consider the context of Theo rem 2 Then for X E g1 we have on 8 MW pXXigt id quaXll Now 1 Us 7r0exptXX eZtK where K is self adjoint by Stone7s theorem Under our hypotheses K 2pX2 on B The key lemma in the proofs of the theorems stated above is the following Lemma Let H be a self adjoint operator and Us eitH Let A C DH be a dense linear subspace Assume that A satis es one of the two conditions a A is invariant under the one parameter group Ut b A contains a dense set of vectors analytic for H We then have the following 20 A is a core for H Let L be a symmetric operator with A C DL such that LA C DL so that A C DL2 and L2 coincides with H on A Then L is essentially self adjoint and A is a core for it Moreover H L2 In particular H 2 0 DH C DZ Remark This lemma not only gives the precise conditions under Which we can say that a SUSY Hamiltonian is positive but also shows how the odd square root77of the Hamiltonian is itself controlled by the Hamilto nian 21 3 Super systems of imprimitivity on purely even super homogeneous spaces 31 Special subgroups and associated super systems of imprim itivity For ordinary Lie groups the central results of representations of semi direct product Lie groups follow as an application of the imprimitivity theorem which establishes a functorial equivalence between the category of unitary representations of a closed subgroup H0 of the Lie group G0 and systems of imprimitivity for G0 based on Q GOHO Actually the theory is valid in the wider category of locally compacts second countable groups but we are interested only in the case of Lie groups Also we shall assume that GOHO has a GO invariant measure although this is not an essential restriction A system of imprimitivity SI for G0 based on Q is noting more than a representation of the GO action on 9 More precisely it is a pair 7rP that consists of a unitary representation 7r of G0 in a Hilbert space H and a projection valued measure P on Q in H such that 7rgPE7rg 1 Pg 9 E G0E Borel C lf 039 is a unitary representation of H0 in a Hilbert space IC then one can associate canonically to 039 a 81 7r 7P 7 for G0 based on 9 7r 7 is the representation of G0 induced by 039 and P 7 is the natural projection valued measure on Q in the space of 7r Here we must recall that the Hilbert space H of71quot7 is the space of equivalence classes of measurable functions f from G0 to IC such that a ac U 1fac for each 5 6 Hg for almost all x and b f lt 00 in view of a the IC norm of at is really de ned on Q and die is the invariant measure on For any Borel E C Q the projection Pg is the map f gt gt XEf f E H where XE is the characteristic function of E The imprimitivity theorem is the statement that 039 gt gt 71quot7 P is a functorial equivalence from the category of unitary representations of H0 to the category of Sls based on Q It is well known how this theo rem leads in a straightforward manner to the classification of irreducible unitary representations of regularquot semi direct products The semi direct product To gtlt L0 is regular T0 being an abelian group if the action of L0 on the dual group To is nice in the Borel sense ie there is a Borel cross section for the orbits 22 Our intention in this section is to formulate a generalization of this result in the super setting Exactly as in the classical theory such a gener alization will lead to a classification of irreducible unitary representations of super semi direct products To this end we work with a super Lie group G0 g and a closed super subgroup H0 We shall assume that the sub group is special namely that 1 g1 or that the odd part off coincides with the odd part ofg This means that the associated homogeneous space is classical namely 9 GOHO At this moment it is not entirely clear how to remove this restriction However this condition is still adequate enough to provide a solution to our main problem that of classifying the irreducible unitary representations of regular super semi direct products 32 The super imprimitiVity theorem A super system of imprimi tivity SSl based on Q GOHO is a system 7r p 7 l P where 7r p 7 l is a unitary representation of the super Lie group G0g 7r7P is a classical system of imprimitivity for G0 based on Q and p7r commutes with P this means that the spectral projections of the p7r E g1 commute with the projections PEE Borel C The last condition characteristic of the fact that we are dealing with special SSls reduces in practice to verifying the following if B is a common core for all the p7r E g1 which is left invariant by all the pX and the operators 2 f0 udP where u 6 0509 then the pquotX and commute on B in the usual sense We shall now associate to any unitary representation 0 p K of the super Lie group H0 b a SSl of G0g0 To this end we must define 7r and pquot We shall use the exibility provided by Theorem 32 and define the pquotX on a suitable space 8 We define 7r by 7 Go 7r 7 lndHOo in the Hilbert space H introduced earlier Let B 05 00 the space of 00 vectors for 7r in H which as functions from G0 to IC are smooth and have compact support mod H0 It can be shown as a consequence of the Dixmier Malliavin theorem that B is precisely the space of all smooth functions f from G0 to IC such that flt gt o 1facac E G0 6 H0 and have compact support mod H0 It is then easy to see that tthe values of any f E lbb lie in O o so that all the operators p 7XX 6 b1 g1 act on all the values of any f E B We define WXVW pquot 1Xfx f 6 835 6 GO 23 Of course the projection valued measure is the standard one associated to 7139 We then have the following theorem Theorem 1 7rpquotBP is a SSI for the super Lie group Gg based on Q GOHO The assignment mpa C H of is a functorial equivalence of categories from the category of unitary rep resentations of H0 in to the category of SSIs for G0g based on Q GOHO In particular we have a bijection from irreducible unitary repre sentations of H0 b with irreducible SSIs for G0g based on GOHO 24 4 Representations of super semi direct products 41 Super semi direct products We start with a classical semi direct product G0 T0 gtlt L0 where T0 is a real nite dimensional vector space the spacetime translation group and L0 a closed unimodular subgroup of GLT0 acting naturally on T We shall assume that the semi direct product is regular namely that for the action of L0 on the dual T3 there is a Borel cross section this is equivalent to saying that all the LO orbits in T3 are locally closed Effros Let 0 LieT0 0 LieL0QO LieG0 By a super translation group we mean a super Lie group To t where to acts trivially on t1 In particular this means that t1t1 C 0 Suppose now that t1 is an LO module and that the super commutator map a b gt gt a b is Loequivariant from 1 gtlt t1 into to Then g 2 0 69 t is a super Lie algebra with go 0 69 t0 LieG0g1 t1 The super Lie group S G0g is the super semi direct product of L0 and the super translation group T0t For any closed subgroup SO C L0 we have H0 T050 is a closed subgroup of GO and H0 b is a special super Lie subgroup of GO g where l mean 0 being LieH0 if50 LieSO then b weak We are interested in describing all the irreducible unitary representations of G0g The super Poincare groups that occur in the physical literature are special cases of the above construction where L0 is an orthogonal group rather its two fold cover the spin group with respect to a nondegenerate quadratic form on to and t1 is chosen as a spin module for L0 But in this section we shall discuss the general case The aim is to show that the irreducible unitary representations of the super semi direct product may be classified by the Frobenius Mackey Wigner method of little groups For any A 6 T3 let L3 be the stabilizer of A in L0 and let 9A to e 3 egg 3 LieL3 We shall refer to the super Lie group S 2 T0L3g as the super little group at A It is a special sub super Lie group of S G0g Given a unitary representation ILJquot of SA we shall say that it is A admissible if ot ei wU for all t E To A itself is called admissible if there is an irreducible unitary representation of SA which is A admissible Let TJAeTg A admissible 25 It is easy to see that T0 is LO invariant Given a unitary representation 7Tp7r of the super Lie group S we obtain a spectral measure on P on T by Fourier transformation of the restriction of 7r to T0 7rt Tei tdPA teT If E is any LO invariant Borel set the spectrum of the unitary represen tation is said to be in E if PE I Theorem 1 The spectrum of every irreducible unitary representation of the super Lie group S G0g is in some orbit in T0 For each orbit in T0 and choice ofA in that orbit the assignment that takes a A admissible unitary representation 7 ILJquot of SA into the unitary representation U7 of G0g induced by it is a functor which is an equivalence of cate gories between the category of the A J 39 1 unitary rep t39 of SA and the category of unitary representations of G0 g with their spectra in that orbit Varying A in that orbit changes the functor into an equiva lent one In particular this functor gives a bijection between the respective sets of equivalence classes of irreducible unitary representations Proof Sketch Since T0 acts trivially on g1 it follows that for any unitary representation 7rpquot of S the operators 7rtt E To commute with pquotXX E g1 and so the spectral measure P and p7r commute with each other If 7rpquot is irreducible and E is a LO invariant Borel set PE commutes with 7r also and so PE 0 or I Thus by regularity of the semi direct product PO I for some orbit 0 If A E O we can view P as a projection valued measure on LOLS Clearly 7rpquotP is a SSl for S based on LOLS By the super imprimitivity theorem this is the SSI associated to a unitary representation ILJquot of S From the classical theory one knows that ot e ml for all t E To lf 7rpquot is irreducible ILJquot is irreducible and so A is admissible ie A E T Remark The reader should notice the sharp difference between the clas sical and super symmetric situations In the classical theory all orbits in T3 are allowed while in the SUSY case only those in T0 are Actu ally when everything is even T0 T3 in fact given any A the map tac gt gt ei tt E T0 at 6 L3 is well defined and gives an one dimensional irreducible unitary representation of TOLS thus showing that A E T0 But 26 when super symmetry is present the restriction to T0 is a genuine selec tion rule We shall see below that T04r may be interpreted as the condition of the positivity of energy This is very different from the classical the ory where representations of negative energy tachyons are theoretically possible and have to be excluded ad hoc Suppose A 6 T3 and ILJquot is a unitary representation of S such that ot e ml for all t E To Then fidoZ AZI Z 6 to On the other hand if X1X2 6 Q1 then X1X2 E 0 Thus lP X1PUX2l 2 gtX15X2I XlaXZ E 91 where A is the symmetric bilinear form on g1 gtlt g1 defined by IDX1X2 12lX1X2l If we now take X1 X2 X we see that P0002 QAOQL QAX QanX X 691 on 00 o Since pquot is essentially self adjoint on O o it follows that QMX 2 0 X 691 This is thus a necessary condition that there should exist a unitary repre sentation o p with ot e ml for all t E To Theorem 2 For a A 6 T3 the following are equivalent a There is an irreducible unitary representation ILJquot of SA with ot e ml for all t E To b There is a unitary representation 0 p ofSA with ot e ml for all t E To C QAltX 2 0 for all X Egl Remark When the super serni direct product is specialized to the super Poincare group the condition Q 2 0 is the same as the positivity of the 27 energy This is the reason why we refer to this condition as the positive energy condition in the general case 42 Cli 39ord structure when Q 2 0 To complete the proof of Theorem 2 we must show that if Q 2 0 then there is an irreducible unitary representation a p of SA sich that 015 ci WU for allt E To Actually it is necessary to construct all such so that we can get a description of all irreducible unitary representations of the super semi direct product S G0g This depends on exploiting the Clifford structure that arises from the quadratic form Q The form Q is invariant under L8 Moreover the condition pquot X2 QAXI shows that the operators pquotX are bounded self adjoz39mf so that the situation is much nicer than for the big group We de ne C as the quotient of the tensor algebra generated by g1 with respect to the relations X2 QAXX E g1 lf Q is non degenerate this would be the Clifford algebra associated to the quadratic form Q by abuse of language we shall refer to it as the Clifford algebra associated to Q even if Q is singular Clearly pquot may now be viewed as a representation of C in a super Hilbert space IC such that pquotX is odd and self adjoint for all X E g1 SA representations Now L3 acts on g1 and leaves Q invariant Hence its action lifts to an action 7 a gt gt u on C Then the unitary representations of SA are pairs 07 where tau is an SA representation and 039 a unitary representation in the space of 739 such that Tza Ux raaac 1 for a E Cm 6 L8 While there is nothing really dif cult in the determination of the pairs 0 T it is technically involved and I do not want to go into all the details To simplify matters I shall assume the following condition is satis ed L3 2 A gtlt T A simply connected and normal T a torus C This condition may look artificial but in its defense let me say that it is satisfied when S G0g is a super Poincare group It is also close to the exact conditions needed for the lemma below Since Q may have a radical say t we introduce 91A 91 t 28 Then QA de nes a non degenerate quadratic form on gm which we denote by 62 Since L3 preserves QA and is connected we have a map j 1L3quot SOltQlAgt Then there are two possibilities l The Inapj lifts to a map this is the case when L8 is simply connected E L8 Sping1 2 j does not lift as in l but there is a two fold cover HA of L8 such that j lifts to a map HA 2gt Sping1 In this case the covering Inap H A 6 L8 has kernel i1 We write 5 for the non trivial element of this kernel In this case we can take HA A gtlt TN where TN is a torus which is a two fold cover of T and 5 l t Then there is a character X of H such that 95 71 Lemma 1 We have the following a There exist irreducible SA representations of CA These are nite dimensional unique if dirng1 is odd unique up to parity reuersal if dirng1 is even b Let TA be an irreducible SA representation ofC Then in the pres ence of condition C there is an even unitary representation HA of L3 in the space of TA such that Tica HATaHA 1 an 6 L8 a 6 CA HA is unique up to multiplication by a character of L3 Proof Sketch a is a variant of the standard theory of Clifford alge bras Let us now look at The spin group Sping1gt is irnbedded inside the even part of the Clifford algebra of gm and TA may be viewed as a 29 representation of this Clifford algebra lts restriction u say to the spin group is than an even unitary representation of the spin group compatible with the action of gA1 It now L3 is simply connected or more generally if j lifts to a map j as in case 1 we may take HA u o u lfj exists only on a two fold cover a u 0 de nes the unitary representation we seek It may happen that 5amp5 71 it is i1 in this case changing a to XHA we get a unitary representation which descends to L3 which we may take as HA Theorem 2 Let A be such that Q 2 0 and suppose that condition C on L3 is satis ed Let p lm and let o elkm be the unitary representation of TOLS We then have the following a 0Ap is an irreducible unitary representation of the little super group SA which restricts to e on T0 b The unitary representations ILJquot restricting to e on T0 are pre cisely those of the form o6 n p 1 p where 6 is a purely euen unitary representtaion of L3 c The assignment I 6 gt gt 6 elkm 1 8 p is an equivalence of categories from the category of purely euen unitary representations of L3 to the category of unitary representations of the little super group S which restrict to e on T0 Remark 1 We have thus reached the situation where the irreducible unitary representations functorially determine the irreducible unitary rep resentations of S which restrict to e on T0 Theorems 411 412 and 422 complete the theory of unitary representations of regular super semi direct products Remark 2 The pair eiAm pk is called the fundamental representation of SA Once it is determined the whole structure of the irreducible uni tary representations of the original super semi direct product S is made transparent The determination of HA and the verification of the condition C are thus the crucial ingredients that remain to be described in the super Poincare case 30 5 Representations of super Poincare groups and multiplet structure of super particles 51 Super Poincare groups Super Poincare groups are super semi direct products that are super symmetric extensions of the Poincare group in D2 4 spacetime dimensions More precisely in terms of the earlier notation we take a T0 RliD l the Minkowski space of signature 1 D 71 with D 2 4 The Minkowski bilinear form is ltaygt 950 i 2 Eye 19934 b L0 Spin1 D 7 1 which is the simply connected covering group of SO1 D 7 1 It is actually a 2 fold cover a g1 is a spin module for L0 ie a direct sum over C of irreducible spin modules In order to have a super translation group we saw that we need a non zero symmetric LO equivariant bilinear form 91 X 91 6 07 aab gt gt a7 It can be proved that when g1 is a spin module for L0 such forms always exist The classi cation of these forms then provides a classi cation of all super Poincare groups that extend the classical Poincare group of signature 1 D 7 1 The simplest situation is when g1 is irreducible over R In this case the space of forms B is of dimension 1 Let Pu f0 no gt 0 ltuu 2 0 Thus F is the closed forward light cone origin being excluded in to It turns out that we can choose as a basis for this one dimensional space a form with the following positivity property XX e m 0 X e g1 31 This is remarkable because it says that for any non zero form A satisfying B the values of the quadratic map X gt gt AXXX 31 0 takes values either in the forward light cone or the backeard light cone hence by con nectitivity in one of the two entirely It is not dif cult to show that P is equivalent to vXXgt0fora1107 X g1vEP0 P where the index 0 denotes interior Using this basis element or any other which is a positive multiple of it we have a super Poincare algebra hence a super Poincare group in which the positivity condition P is automat ically satisfied A consequence of this is the result that in any unitray representation of the super Poincare group the elements of F which can be written as sums ZjXjXjXj E g1 have nonnegative spectra This is a form of the principle of positivity of energy Of course it is not necessary to assume that g1 is an irreducible spin module If N is the number of irreducible spin modules in g1 physicists speak of N extended super symmetry when the odd commutator map 91 x91 etc XXH XX lt0 Xeg1gt takes values in Pf The de nition of super Poincare algebra assumes this positivity One can then classify all super Poincare algebras We shall not go into this classification here 52 Representations of super Poincare groupsThe theory of Chap ter 5 applies at once for S G0g a super Poincare group Because of the Minkowski form we can identify 3 with to itself For 1 E F the stabilizer L8 is given by SpinlD 7 1 if pp gt 0 L8 RD 2 gtlt SpinD 7 2 if 1913 0190 gt 0 L0 ifp 0 Thus except when D 4130 gt 0 pp 0 the stabilizer L8 is simply connected in the exceptional case of zero mass in 4 space time dimensions the stabilizer is R2 gtlt T where T is a circle group and so still falls within the condition C described in Section 52 The key lemma which shows the nature of TJr in this case is the following 32 Lemma 1 We have Qp20ltgtp020ltppgt20 Proof Sketch If u 6 TWO lt1 gt 0 for all 0 7E X E g1 by the structure of the super Poincare algebra positivity of the odd commuta tors By going to the limit we see that for p E P ltp X 2 0 for all X 6 Q1 This is just the statement that 62 2 0 For the converse suppose that 62 2 0 but ltppgt lt 0 Then L8 2 SpinlD 7 2 On the other hand we have a map L8 6 SOg1p Since Spinl D 72 is simple and non compact it cannot have a nontrivial map into a compact group Hence L8 acts trivially on glp Thus the action of L8 on g1 contains the trivial representation of L8 But L0 acts as a spin module and it is not difficult to show that the action of L8 is a sum of spin modules and so cannot contain the trivial representation Theorem 2 The irreducible unitary representations of a super Poincare group S G0g are parametrized by the orbits ofp with pg 2 0 ltppgt 2 0 and for such p by irreducible unitary representations of the stabilizer L8 at p Let Tp be an irreducible SA representation of the Cli ord algebra Cp and let Hp be the representation of L8 in the space of Tp de ned earlier Then for any irreducible unitary representation 6 of L8 the pair ILJquot de ned by oeipbl np p 7Xl rpX Xegl is an irreducible unitary representation of the little super group Sp T011830 69 8 69m and all irreducible unitary representations of Sp are obtained in this manner The unitary representation ope of the super Lie group S induced by it is irreducible and all irreducible unitary representa tions ofS are obtained in this manner the correspondence pbl gt gt ope being bijectiue up to equivalence Remark 1 The reader can see that in the presence of supersymmetry only representations of positive energy come in in contrast to the classical situation where we could not exclude the tachyonic orbits Otherwise the reduction to the little group is exactly as before parametrized by the irreducible unitary representations of L8 except that it has to be tensored 33 with the pair Hp Tp Thus the determination of Hp 7p is the basic new ingredient Remark 2 The correspondence with representations of the Little group allows us to treat zero mass super particles with in nite spin somehting not available in the physics literature Also the SUSY transformations are given on the full space of super particle states not only on those with a fixed momentum 53 Multiplets and fundamental multiplet The irreducible unitary representations of the super Poincare group are the models for super par ticles If we restrict the representation of GO it will in general decompose into a direct sum of particles and this set is called the multiplet defined by the super particle The operators E g1 then give the trans formations between particles of different spin parities The fundamental muptiplet is the one corresponding to the trivial representation of L8 The irreducible unitary representations into which Hp splits then de ne the classical particles of the fundamental multiplet The calculation of Hp can be carried out very explicitly When D 4 and 91 is the Majorana spinor the multiplet with mass m gt 0 has the spins 7 gt 0 0 0 0 For m 0 the mulitplet has spins helicities 712 71 12 These results are the source for the prediction that supersymmetry forces the known elementary particles to have super partners Whether these partners can be seen when the new LHC opens is at best speculative since we do not know the threshold of supersymmetry breaking in the development of the early universe Summary In going over from the representation theory of the Poincare group to that of the super Poincare group the little group method remains valid The additional feature is that the space of the representation of the little super group is lCClassical Call Md The second factor carries the action of the odd operators of the little super group and the even representation of the little super group is 6 8 HP Thus the states of the 34 little group are the classical states tensored with the Clifford states on the latter both the odd operators and the classical part of the little super group act This theory allows a discussion of super particles of mass 0 with in nite spin which is new The SUSY transformations of particle states are globally given which is also new the usual formulas are restricted to states of fixed momentum References Basics 4 N 9 5 QTY Varadarajan V S Supersymmetry for Mathematicians An Intro duction AMS Courant lnstitute Lecture Notes 2004 Providence Rl Deligne P and Morgan J Notes on supersymmetry following Joseph Bernstein Quantum elds and strings a course for mathe maticians vol 1 41 97 American Mathematical Society Providence R11999 Kostant B Graded manifolds graded ie theory and prequantization in Di erential geometrical methods in mathematical physics Proc Symp UNiv Bonn Bonn 1975 Lecture Notes in Mathematics Springer Berlin 1977 Leites D Introduction to the theory of super manifolds Usp Mat Nauk 351 3 57 1980 Russ Math Surveys 351 1 64 1980 Manin Yu 1 Gauge eld theory and complex geometry Grundlehren der Mathematischen Wissenschaften 289 Springer Berlin 1988 35 String Duality and Localization Kefeng Liu UCLA and Zhejiang University Yamabe Conference University of Minnesota September 18 2004 String Theory should be the final theory of the world and should be unique But now there are Five different looking string theories Physicists these theories should be equivalent in a way dual to each other their partition functions should be equivalent Question How to compute partition functions Localizations modern version of residue theo rem on infinite dimensional spaces Path integrals Reduce to integrals of Chern classes The identifications of partition functions of dif ferent theories have produced many surpris ingly beautiful mathematics like the famous mirror formula The mathematical proofs of such formulas de pend on Localization Techniques on vari ous finite dimensional moduli spaces More precisely integrals of Chern classes on moduli spaces Combined with various mathematics Chern Simons knot invariants combinatorics of sym metric groups Kac Moody algebras represen tations Calabi Yau geometry and topology of moduli space of stable maps Localization has been very successful in prov ing many conjectures from physics see my ICM2002 lecture for more examples Functoria Localization transfers computations on complicated spaces to simple spaces Connects computations of mathematicians and physicists Papers Containing the Results 1 A Proof of a conjecture of Mari 39o Vafa on Hodge Integrals JDG 2003 2 A Formula of Two Partition Hodge Inte grals mathAGO310273 C C Liu K Liu and J Zhou 3 A Mathematical Theory of Topological Vertex mathAGO408426 4 Topological String Partition Functions as Equivariant Incices preprint J Li C C Liu K Liu and J Zhou Spirit of the Results 1 Duality Gauge theory Chern Simons lt2 Calabi Yau in String theory 2 Convolution formulas encoded in the mod uli spaces and in the combinatorics of symmet ric groups gt Differential equation cut and join equation from both representation theory and geometry 3 Mathematical theory of Topological Ver tex Vafa group s works on duality for the past several years 4 Integraity in GW invariants ltgt Incices of elliptic operators in Gauge theory Gopakumar Vafa conjecture I will first talk about the Marino Vafa conjec ture and then several other results The Mari39no Vafa Conjecture To compute mirror formula for higher genus we need to compute Hodge integrals ie in tersection numbers of A classes and w classes on the Deligne Mumford moduli space of sta ble curves My the most famous orbifold It has been studied since Riemann and by many Fields Medalists A point in Mg consists of Cx1xh a nodal curve and n smooth points on C The Hodge bundle E is a rank 9 vector bundle over Mg whose fiber over Cx1xh is H0Cw0 The A classes are Chern Classes M QUE E H2imgh Q The cotangent line T5020 of C at the i th marked point xi gives a line bundle Li over M9 The d classes are also Chern classes 1 01Lz E H2mgh Q Define Agar u9 A1u91 19Ag Mari o Vafa formula Generating series of triple Hodge integrals Aglg7g T 1 Mgih ng l can be expressed by close formulas of finite expression in terms of representations of sym metric groups or Chern Simons knot invari ants Here 739 is a parameter 7 Conjectured from large N duality between Chern Simons and string theory Remark Moduli space has been the sources of many interests from Math to Physics Mumford computed some low genus numbers Witten conjecture is about the integrals of the w classes Conifold transition Resolve singularity in two ways Conifold X 33 y C4xw yzO z w 1 Deformed conifold TS3 33 ygt C4ixw yze z w 6 real positive number 2 Resolved conifold X O 1 O 1 gt P1 33 y xyeizzl ZoZ1ltZ wgt P1XC439 Zw Zle X C P1 x C4 l l X C C4
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'