Wednesday, January 23, 2019 Chair: Noga Alon (A) Other Member: Ze'ev Dvir (D) Other Member: Peter Sarnak (S) Me: Ryan Alweiss (R) Wording may not be exact, and there may be inaccuracies. Probably some things are out of order, oops. The exam is 2 PM - 5 PM (3 total hours) and in A's office (Fine 706), though at this point I guess I don't know exactly when it will end, though I have some idea. I come in a little early and talk to A. D than arrives and S right after. I become a bit nervous. I tell S that we should start with complex analysis, as is traditional. S says that there is no such traditional order, but that I get to choose! He says sure, we can start with complex analysis. In anticipation of the first few questions, I write the Cauchy integral formula down on the board, in fact the version for the nth derivative of z. S asks what I am writing down. For what functions does that thing hold? We get into a discussion about what functions are differentiable, what functions are entire, how the thing I wrote down only works when the region is simply connected, and so on. I'm confused exactly what he wants me to say at some parts, but we talk about the Cauchy integral formula until I say everything and he is satisfied. Specifically I talk about how this works on simply connected regions, how you can use this to show infinite differentiability, the Cauchy Riemann equations, Cauchy's theorem (he even asks how to prove Cauchy, I talk about the triangle proof from Stein-Shakarchi), and so on. Then there is discussion of harmonic functions. I think I write an upside down triangle at some point, meaning gradient, when I should have written the right side up triangle for Laplacian. Peter corrects me. S: What can you say about a bounded above harmonic function? R: I know it's constant, there is the trick where you subtract epsilon*log(z) and use the mean value theorem for harmonic functions because I saw it on Colin's quals. S smiles as I say I know this S: How do you prove the mean value theorem? R: Uhh well you can first assume there is a harmonic conjugate using Cauchy-Riemann S: No don't use that. R: Uhh idk. I know that it's some details. S: NO!!! You should know how to do this, it's a problem for undergrads. OK fine use harmonic conjugates. How do you prove that it exists? R: Well you can use Jensen's formula! OK that's obviously not allowed. Stutters and then talks about how you can do the simplest thing you can do to solve any differential equation, integrate along a rectangle once you know the derivatives. S: ANY differential equation? R: Well I meant that it is the simplest among all techniques that are used to solve differential equations, not that it is applicable to all differential equations. The word "any" is ambiguous like that. S: You make so much commentary! Anyway, how do you prove the mean value theorem if you can assume a harmonic conjugate? R: Uhhh S: Do you know how to actually compute a complex integral? R: Yeah parameterize. S: OK do that! I do it and it works COOL S: OK now for the fun part, I'm sure you know this one since I ask it to literally everyone. A function holomorphic in a half-disc function is bounded by 1 in magnitude on the diameter and 2 on the circumference. Bound it on the inside. me: Sure, map it to the quarter plane and use that log|z| is subharmonic. S: OK sure, this is actually unnecessary and you can just instead look directly at the angle. Also you are using something. You can't just do this for any function. R: I am using..? Oh that the limit at infinity exists after you invert, because the center of inversion maps to the point at infinity. S doesn't know what "inversion" means in this context, I tell him that in olympiad euclidean geometry things like 1/z (really 1/bar(z)) are called "inversion." S then explains how we have a harmonic function of the angle here and there is no need to pass to the quarter plane. Also at some point in this section there was something about the Dirichlet problem, and I mentioned that Brownian motion can be used to solve the Dirichlet problem, but I said I didn't want to get into that. S said this was a wise choice, because he said if I bring something up I should know about it. I think I also mention Perron's subharmonic method at some point? I am really surprised that Peter doesn't ask about doubly connected regions, but he says that once you ask enough people something then it becomes easy. Anyway at some point Peter is satisfied, and we move to real analysis. First there is something about L^p spaces, I think Peter asks me to define measurable functions and L^p spaces. I mention that L^p requires measurable. S asks what a measurable set is. I say that you take the sigma algebra of the intervals, this gives you a measure on Borel sets, and you extend the sigma algebra by saying that all subsets of measure 0 sets are measure 0. I spent the first minute or two saying some facts about real valued functions. S: Write down what Fourier is over say L^1(R). R: Writes down the Fourier transform over L^1(R), says that you get it from Schwartz functions, defines those, a little back and forth with Peter about what the range is, I say L^infty and goes to 0 at infinity, proved using banach isomorphism theorem, talk about the sin(2*pi*x)*sin(2*pi*n*x)/x^2 function. S: Pronounced BanaCHHH (not Banak). How do you show that this thing works? R: OK so you agree you substitute variables and it becomes showing sin(x)/x has L^1 norm infinity? S: Yes R: OK well then the nth hump has L^1 norm \Theta(1/n) and harmonic series diverges. S is satisfied A: So \sum 1/n diverges, how about \sum 1/p? R: That's around log(log(n)). some discussion of the proof of this, I say there is PNT but Noga says you actually don't need that (but no one asks me to prove this) A: How many prime factors does n typically have? R: log(log(n)), right this is from chapter 3 of your book, you look at indicator variables for each prime and compute expectation and second moments. S: Wow you're citing specific chapter numbers now! There was some discussion about Noga's book, which by the way is fantastic. S: Can the FT of a compactly supported function be compactly supported? me: No because the FT of a compactly supported function can be extended to an entire function on the complex plane which is not 0 and then it vanishes on a line and so has to be 0. S: OK you know about the relationship between decay of the function and derivatives of Fourier? R: Yeah Fourier interchanges multiplication by x and taking the derivatives. S: Right you use integration by parts. R: You know I never liked integration by parts, I always preferred to guess the answer. S doesn't like that I express my dislike of "integration by parts" even though what I mean by this is that whenever I am asked to integrate something by parts I just guess the answer instead. S: Actually you know what? I want to make sure that you know what you are talking about, write some things down on the board. R: I write down the Fourier transform of f'(x) and want to show that it's x * fourier transform of f(x), I subtract out a term corresponding to x * fourier transform of f(x). S: The other term? R: Uhh oh you want me to say the integral is 0. S: Good. So what can you say about Schwartz functions? R: Right so they go to Schwartz functions, because of this relationship under Fourier between multiplication by x and taking the derivative. S: What if a function is holomorphic on an OPEN set containing the unit circle. What can you say about its Fourier series? R: I write down the formula for Fourier series for functions on a circle, S is happy now about the 2*pi. So certainly it will decay faster than any polynomial, it will be very smooth. S: indicates that "very smooth" is the right kind of thing to look at R: Uhhhhh S: It's OK you don't have to know how to do everything in these exams. In fact it will be harmonic! How do you think you prove this fact? R: Uhhh... Move the contour? I mean, what else can you do. S: Right, you move the contour of integration. S seems happy now, and algebra begins. This means that someone other than S is finally going to start asking questions. A: What can you say about solvable groups? R: Proceeds to describe was solvable groups are. A: What can you say about the commutator subgroup? R: Uhh wait what's that? OK so commutators are aba^{-1}b^{-1} S: Is that a subgroup? R: Uhh no. S: But they generate a subgroup. What can you say about it? A: Is it normal? R: OH YEAH and G/(that group) is the Abelianization of G, the largest abelian subgroup of G, and so you can use this to solve any solvable group. S: OK prove it's normal. R: OK so say you have g*(aba^{-1}b^{-1}...yzy^{-1}z^{-1})*g^{-1}. R: This is bad notation S: No it's fine R: But g is a letter of the alphabet so it's inside that product S: Whatever R: OK, then you can write this is as (gaba^{-1}b^{-1}g^{-1})*... so it suffices to show it for gaba^{-1}b^{-1}g^{-1}. Now uhh... ok this can't be that hard, like there are only O(1) things to try. S: O(1) things! I like the way this guy thinks! Also I like your commentary. R: Do you actually like my commentary? S: No not really, it's kind of annoying. It's better to just think and answer. R: Oops. I think commentary makes me less stressed. Anyway Uhhhh A: Put g somewhere R: Uhhhh S: Whatever good enough. R: How do you actually do this? This is embarrassing, I mean this is just combinatorics on words, how hard can this possibly be? D (speaking for the first time I think): Put g between everything. R: Oh yeah (gag^{-1})*(gbg^{-1}*(ga^{-1}g^{-1})*(gb^{-1}g^{-1})=(a')(b')(a')^{-1}(b')^{-1} where a'=gag^{-1}, b'=gbg^{-1}. Oops! A: Can you solve groups of order pq? R: Sure. In fact they are Abelian except when q is 1 mod p. I write down the Sylow theorems and talk about groups of order pq and p^2. At some point S interrupts that A was just asking to prove these are solvable and not to classify them. Then at some point S interrupts again to ask how to prove Sylow. I confess my ignorance and say that I studied previous generals and never saw a proof of it. S says I should have studied it, but praises my honesty. When I am talking about groups and use the phrase "class equation" though S seems happy, he says that that is how you prove the Sylow theorems. S then asks about rational canonical form, Jordan normal form, fundamental theorem of modules over a PID. I describe this and outline proofs of these. I also describe the matrix exponentiation and I think mention the fact about a negative number of Jordan blocks because this is something S always asks about. S: How do you prove this fundamental theorem? R: Well it's the same as the proof of the one for finitely generated Abelian groups. Can I talk about that setting because it's more intuitive? S: Sure. R: Right so I like to think about it as having some sort of lattice and I want to make it orthogonal. It's the same as Smith normal form (which I learned a few months ago oops), you write down unitary matrices. S: Good! But you mean determinant 1 and not unitary. Unitary is something else! R: Yeah I do good point. S: One last thing, why is the multiplicative group of a finite field cyclic? R: does the argument with order, and sum d|n phi(d)=n S: That's a nice elementary proof. Can you do it with what you just proved? R: No. Uhh can I? S: Using the classification theorem? R: Right, so you write it down in the standard form and take the largest number... S: Which is called? R: The exponent of the group. If lambda is the exponent of the group x^{\lambda}-1 has >lambda roots, oops. S: OK time for special topics! R: OK so Ze'ev has been awfully quiet, and I think has been bored. Let's let him go first, we'll do complexity first. D: What is #P? R: describes #P D: What is the PCP theorem? R: states PCP theorem D: Assume PCP. Prove it's NP-hard to approximate 3-SAT. R: You do some Cook-Levin type things. I proceed to repeat something about Cook-Levin type things A: Let's make sure you actually know what you are talking about, I think you do but if someone didn't know complexity before they would be confused. S: I'm confused. After a few minutes I eventually say that you can reduce determining membership in an NP hard language to figuring out whether the associated PCP has a probability 1 or <.99 of being verified as true, which you can do by constructing a 3SAT clause according to the randomness of the verifier. A and D are satisfied. I am embarrassed that I stuttered on this just as I stuttered on the commutator stuff. But the committee seems pretty forgiving and it wasn't that long, maybe only a few minutes. S: Show us some circuit lower bound. R: Any circuit lower bound? S: Yeah just show me one, I'm curious to see how they work. R: describes using Hastad's switching lemma to prove parity is not in AC0, gets asked by A why it's called the switching lemma and describes how you switch AND guys to OR gates and then merge them. A: Why is primality testing in NP? R: In fact it's in P. But it's because a certificate consists of a factorization of p-1 and a verifying that all those are prime and so on. So you just need to show how a factorization of p-1 gives you what you want. S: OK so why is a factorization of p-1 good? R: If you have a verified factorization the verifier also gives you a primitive root w and if you check that for all primes q|(p-1), w^{(p-1)/q} is not 1 mod p but w^{p-1} is 1 mod p, then this shows that indeed there is an element of the multiplicative group of order p-1 so you're happy. S: Prove this problem is NP-hard. Does there exist a factor of n between x and y? This is a beautiful result of Alon and Killian. What problem do you think you would reduce it to? R: Wait what?!?! That's NP-hard?!?! I know that you think factoring is in P, but I guess it takes a long time to write out all those factors. Uhh... (I stare in amazement and bewilderment). There is some discussion of this, A says something about it (it's his result after all!) and I ask D if he knows how to do it, D doesn't seem to know how to do it either. It is typical of S to sometimes just state hard and interesting things that he does not expect you to solve. I like this, because generals are supposed to also be a learning experience. S: Subset sum. Anyway it's a nice problem. A: OK we can talk now about combinatorics. What should I ask you about? A: You know what a doubly stochastic matrix is? R: defines doubly stochastic matrices A: This is a convex polytope of linear combinations of the permutation polytopes. How do you prove that is the permanent is positive? What theorem does it sound like? me: Uhh Bregman? Hall? A: It sounds like Hall, so prove it. me: OK so you have k rows, assume they meet fewer than k columns. A: OK what can you say now? me: Oh yeah of course so those k rows have all mass on those