NOAH KRAVITZ'S QUALIFYING EXAM Committee: Noga Alon (chair), Peter Sarnak, Yunqing Tang. Special topics: analytic number theory, combinatorics. Friday, October 8, 2021 at 3:30pm in Noga's office. KEY: [A]=Alon, [S]=Sarnak, [T]=Tang. I have probably forgotten some of the questions, and they're certainly not all in the right order, but here is more or less how the exam went. ---- We agreed to start the exam at 3:30 because I was attending a seminar at 2:30. This became relevant later because everyone was eager to go home by the time we got to the later parts of the exam. Peter, Yunqing, and I all arrived at Noga's office at the same time. After some discussion of who would sit where (for social distancing purposes), Noga said that, per my request, we would start with algebra. They asked me what books I had read to prepare. Peter made some comments about the choice of algebra textbooks at Yale. ---- ALGEBRA Yunqing had brought a list of prepared algebra questions, so everyone decided that she should start. Peter stepped out briefly (to get something from his office, I think), but Yunqing went ahead and started anyway. [T]: Give an example of a field extension with Galois group D_8. I wrote down x^4-3 and said that you adjoin the roots of this polynomial to \mathbb{Q}. I drew a picture of the four roots in the complex plane and said that the Galois group of the field extension is just the symmetries of the square formed by the roots since you can write down all of the automorphisms. [T]: While we're talking about D_8, tell me how many irreducible representations it has. I wrote down the 5 conjugacy classes. [T]: How many 1-dimensional irreducible representations are there (over \mathbb{C})? I said that the sum of the squares of the dimensions is 8, so the dimensions have to be 1,1,1,1,2. At some point Noga said that we should slow down and wait for Peter to get back so that he wouldn't miss all of algebra. [T]: Can you show in another way that there are 4 1-dimensional irreps? I wasn't sure what Yunqing was looking for here. I mumbled a few things, and I think I pointed at the conjugacy classes and said explicitly what the 1-dimensional irreps are (trivial, send s to -1, send r to -1, send s and r to -1). Peter returned somewhere during this exchange and asked me how you can use a representation of a subgroup to get a representation of the whole group. I defined the induced representation using the explicit matrix definition and tried to look at the subgroup generated by r, but this didn't help because (as I realized at Peter's prodding) any induced representation from a proper subgroup will have dimension bigger than 1. After some back-and-forth: [S]; But what is a 1-dimensional representation, really? I said that a 1-dimensional representation is a character, in the sense of a group homomorphism to \mathbb{C}^{\times}. I eventually remembered since that a 1-dimensional representation has to be trivial on all commutators, the 1-dimensional representations are just the representations of the abelianization. I defined the commutator subgroup and the abelianization, and then everyone was happy. [A]: Show that the multiplicative group of a finite field is cyclic. I said that it boils down to the fact that a degree-d polynomial has at most d roots. Noga wanted a bit more, so I said that if you have elements in an abelian group of orders a and b, then you can find an element of order lcm(a,b). Someone mentioned that I also could have used the structure theorem for finite abelian groups and asked me to prove that. I offered to classify finitely generated modules over a PID instead, and the comittee approved. I sketched the Smith Normal Form proof. Peter wanted clarification on how column and operations correspond to multiplying on the left and right by invertible matrices. [S]: Okay, how do you use this to classify finitely generated abelian groups? I said that the module is the group and the PID is \mathbb{Z}. Peter asked me why \mathbb{Z} is a PID. We would come back to finitely generated modules over a PID soon. In the meantime: [A]: Do you know Cauchy's Theorem? I said that if G is a finite group and p is a prime dividing |G|, then G contains an element of order p. Noga wanted a proof. I didn't remember a nice proof of Cauchy's Theorem, but I said that I could prove Sylow instead. This wasn't necessary, but I used the ideas from Sylow (induction on |G|, look at whether or not p divides |Z(G)|) to sketch a proof. Noga said that there was also a more combinatorial proof involving looking at the action of G on p-tuples of elements of G, but none of us could remember the details, so we moved on. [T]: Give an example of a ring that is not a PID. I wrote down \mathbb{Z}[\sqrt{-5}]. [S]: How about a UFD that isn't a PID? I wrote down \mathbb{C}[x,y], where is not principal. Someone asked me to classify the maximal ideals of \mathbb{C}[x,y]. I too quickly blurted out something about modding out by an irreducible polynomial, and then before I could correct myself Peter made me state Hilbert's Nullstellensatz. This precipitated a short exchange between Noga and Peter about the Combinatorial Nullstellensatz. Anyway, while they were talking, I remembered that the maximal ideals of \mathbb{C}[x,y] are just points, i.e., ideals of the form . [S]: Can you diagonalize matrices? I said that you can't diagonalize (1 1 0 1), and then someone asked me to prove Jordan normal form. I gave the standard argument using the structure theorem for finitely generated modules over a PID (which luckily was still on the board). Peter asked me why \mathbbb{C}[x] is a PID, and then he made a comment about how the only useful thing anyone learns in high school is long division. I wrote down the basis that you use for \mathbb{C}[x]/(x-\lambda)^e, and that was enough. Peter was satisfied. Yunqing hadn't gotten to ask all of her prepared questions, but everyone agreed that we should move on in the interest of time. ---- COMPLEX [S]: What is the group of automorphisms of the unit disk? I accidentally said "Blaschke product" instead of "fractional linear transformation" and then remembered that this problem is easier to solve in the upper half plane. I said that the map (z-i)/(z+i) sendsthe upper half plane to the unit disk, so this was fine. I then stated without proof that the automorphisms of the upper half plane are the fractional linear transformations. I wrote down SL_2(\mathbb{R}) and Peter reminded me that I meant PSL. He asked if I knew anything about Lie groups; I said that I didn't, so we didn't pursue it. [S]: State the Riemann Mapping Theorem. I wrote it on the board: If \Omega is a simply connected region properly contained in \mathbb{C} and z_0 \in \Omega, then there is a unique conformal map f from \Omega to the unit disk such that f(z_0)=0 and f'(z_0)>0. Peter asked me if I knew how to prove it. I said that I knew Koebe's proof from Ahlfors' book, and Peter said that he wouldn't make me give the details. (Of course, we had the obligatory short discussion of the prununciation of "Koebe".) We then talked about Riemann's original attempted proof. I knew only the vague outline, so Peter walked me through many of the steps. We discussed: -Riemann's big-picture plan. We try to find a mapping of the form f(z)=(z-z_0)e^{g(z)}. After a few false starts, I wrote down that we need Re(g(z))=(\log|z-z_0|)^{-1}. -The Dirichlet problem and Green's functions. Peter asked me how to solve the Dirichlet problem. I said that the easiest thing is to use the Riemann Mapping Theorem and then solve the problem explicitly on the disk. Peter didn't like this so I talked about... -Perron's method and subharmonic functions. We talked about compactness, and Peter was happy when I made comments about how some of the ideas in Koebe's proof are analogous. At some point in this exchange Peter asked me to prove the Mean Value Property for harmonic functions. He wouldn't let me assume that the harmonic function was the real part of a holomorphic function, so I wrote down A(r)=1/(2\pi) \int_{0}^{2\pi} u(r e^{i \theta}) d\theta. I said that I wanted to differentiate both sides with respect to r, and I more or less wrote down the Laplacian in polar coordinates (I always forget the theta part, but that didn't matter here). Peter didn't let me do that, and instead he asked me to show that A(r) (meaning A(z)=A(|z|)) is itself a harmonic function. I tried to say that an average of harmonic functions is harmonic, and Peter suggested that I find things that commute with the Laplacian. I eventually figured out that the Laplacian commutes with rotation. So rA''(r)+A'(r)=0, and A(r)=B+C\log(r) (just find 2 linearly independent solutions). Taking r to 0 shows that C=0 and B=u(0), as needed. (I was happy to learn this proof since it's nicer than the argument in Ahlfors' book.) [S]: State the Uniformization Theorem. I stated it but said that I had no idea how to prove it. [S]: What about compact Riemann surfaces that aren't simply connected? I drew a torus of genus 2, and then thankfully Peter didn't ask anything else. [A]: Do you know how to prove Liouville? I said that I did, and nobody wanted to see the proof. Noga asked Yunqing if she had anything to add and suggested that she make me compute a contour integral. That didn't happen, though. [A]: State Picard's Theorem. I asked which one he wanted (little) and stated it. I volunteered that I didn't know the proof, and I mentioned that e^z shows that it's possible for an entire function to miss one point. [S]: Draw an annulus. Now draw a doubly connected region. Are these conformally equivalent? I said that the doubly connected region was conformally equivalent to some annulus but necessarily to the one that I had drawn. [S]: When are two annuli conformally equivalent? I said that I knew the proof from Rudin and the proof using the Schwarz Reflection Principle. Peter said that he didn't want to see Rudin's proof ("Rudin is too slick"), so I outlined the proof with the reflection principle. Peter stopped me once I had extended the conformal mapping to all of \mathbb{C}. [S]: What can you conformally map a triply connnected region to? I drew an annulus with a circular slit missing but didn't explain how I would find the mapping. Peter asked me to count the parameters involved (3), said a few words about moduli space, and was done. ---- REAL Now the committee briefly went into "definition mode". [S]: What is a Lebesgue measurable set? I started by defining the outer measure, and at some point Peter interrupted and asked me to define the Borel sigma- algebra. I gave Caratheodory's definition of the Lebesgue sigma-algebra (since that's what I had learned), but Peter didn't like it very much. [S]: Are all Lebesgue measurable sets Borel? I gave a counterexample (courtesy of Trajan Hammonds): Let c(x) be Cantor's function (the "devil's staircase" function), and consider the map f: [0,1]-->[0,2] given by f(x)=x+c(x). Then f is a continuous bijection (note that it's monotonically increasing). In particular, f maps Borel sets to Borel sets. Note that the image under f of the complement of the middle-third Cantor set has measure 1, so the image of the Cantor set also has measure 1. Then you can find a non-measurable subset A of the latter image and take the preimage under f: This preimage is certainly Lebesgue measurable (it's a subset of a measure-0 set), but it's not Borel measurable since A isn't even Lebesgue. At this point, Peter pointed out that the Lebesgue sigma-algebra is the completion of the Borel sigma-algebra obtained by adding in all subsets of measure-0 sets, which was what my example was "really" getting at. [S]: Construct a set that isn't Lebesgue measurable, since you mentioned it. I asked if I could just give an example of a non-measurable subset of the unit interval, and then I gave the standard construction of the Vitali set. Peter hinted that I was using a "big axiom" in my answer. I said that I was using the Axiom of Choice and that I knew this was necessary. [A]: Let A be a subset of the reals with positive measure. Need it contain an interval? I said that the irrationals are a counterexample. Follow-up: [A]: What about A-A? I said that you can use the Lebesgue Density Theorem to find a point of high density in A and then use the Pigeonhole Principle to find an interval in A-A. Either Peter or Noga suggested that Yunqing ask a question since she had been quiet for a while. [T]: What's the dual of L^p? If 1 \leq p<\infty, then it's L^q, where 1/p+1/q=1. If p=\infty, then it's something that properly contains L^1. I wasn't asked to prove this. [S]: You've been doing well so far, so we're going to ask some harder questions. Do you know what a Sobolev space is? When I said that I didn't know, Peter was surprised (especially since my undergrad adviser was an analyst). [S]: Okay, well, consider the space of continuous functions. What's its dual? I blanked and asked if I should talk about distributions (bad idea). Peter said that I could just look at the space of continuous L^1 functions on [0,1], and he suggested that I try integrating against something. I said that we could integrate against a probability measure, for instance. Peter asked why the measure had to be a probability measure, and I eventually said that we could take any finite measure. There followed an informal discussion of a bunch of things from functional analysis that I didn't feel comfortable with (since I never took functional analysis). Peter moved in the direction of Banach-Alaoglu, which I managed to mis-state a few times. I defined the weak topology, and then Peter told me what Banach-Alaoglu actually says. We ended up talking about compactness for spaces of measures, and Peter said that I should learn about this since I'm interested in ergodic theory. I think that at some point in this exchange Peter asked me to state Hahn-Banach. Also, Noga suggested that we talk about Fourier analysis, but Peter shot down that idea since, as he put it, there would be plenty of Fourier analysis in the analytic number theory section. [A]: Do you know anything about the Banach-Tarski Theorem? Before I got a chance to answer, Peter said that it should be called the Hausdorff-Banach-Tarski Theorem. This gave me a moment to think, but I still couldn't articulate a nice answer. I said something about breaking a sphere into parts and rearranging the parts to create two spheres each identical to the one that we started with, but I needed a lot of help to get any reasonably precise statement. [A]: Can something similar happen for a segment in 1 dimension? I said that I thought not but wasn't sure why. Noga pointed out that if it were possible to get a Banach-Tarski-type paradox for the segment, then I probably would have heard about it. [S]: What's the automorphism group of \mathbb{R}? I said that you can translate and reflect, and everyone was happy when I wrote down the semidirect product of \mathbb{R} with \mathbb{Z}/2\mathbb{Z}. [S]: And what's the automorphism group of the 2-sphere? I said that you could rotate, but I couldn't produce "SO(3)". Peter asked me if SO(3) is abelian. I said that of course it isn't. He asked me how nonabelian it is, and Noga asked me to name the "most" nonabelian group that I know. I mentioned the free group and then remembered that the idea of Banach-Tarski is to find a copy of the free group F_2 in SO(3). Once the committee saw the lightbulb go off, they moved on. I think this was the end of real analysis. It was a few minutes before 5:00, and we were all ready to take a short break. Yunqing and Peter left to get snacks, and I stayed and chatted with Noga for a few minutes while we both ate snacks. (Pro tip: bring a snack for the break since the exam is tiring.) Noga told me that he was happy with how the exam was going so far. He also explained the 1-dimensional Banach-Tarski question since Peter hadn't ever given him a chance to finish. (The point is that it's possible to define a finitely additive measure on ALL subsets of \mathbb{R} that is invariant under the automorphism group of \mathbb{R}. We didn't talk about how one actually does that.) ---- ANALYTIC NUMBER THEORY Peter mentioned that I had taken his undergrad analytic number theory class last Spring. I said that I had done the homework assignments, and he asked if I had gotten all of the questions right. I said that I hadn't gotten quite all of them, and Peter asked (jokingly) which ones I had gotten wrong so that he could ask me about them. (I couldn't remember.) Peter then said that since I "must" know classical analytic number theory well from the class and I'd been doing so much work on the Green-Tao papers, he would examine me only on the circle method. (I was slightly disappointed since I had spent a while reviewing classical analytic number theory.) The next 40 minutes or so of the exam was more a conversation than a series of questions and answers. Many of Peter's questions were broad or philosophical, and he mostly wanted me to talk about big-picture ideas and limitations of the method. I didn't get to prove much or write many precise statements. It also wasn't always clear what the question was (that's how conversations work), and there were a few times when we misunderstood each other and ended up coming back to things after a few minutes. We covered roughly the following: -Try to solve a_1x_1+a_2x_2+a_3x_3=b in primes. (That is, a_1, a_2, a_3, b are fixed, and x_1, x_2, x_3 have to be primes.) Peter asked if I can solve this equation "in general". I wasn't sure what he meant (at that point it wasn't clear what was fixed and what was variable), and I said that you can't always solve it--for instance, there could be a local obstruction, like if all of the a_i's are even and b is odd. Peter asked if there's anything else preventing a solution from existing. I mentioned that it's still not always possible to find a solution if b is small and the a_i's are positive (since you need b to be big in order to get an asymptotic count of the solutions.) So Peter said that we could allow the x_i's to be prime or -1 times a prime, and then I think he backtracked and said that the x_i's had to be positive but we would make a_1 and a_2 have different signs. I said that in this case you could run Vinogradov's method to get an asymptotic for the number of solutions. Peter was not yet happy with this, and he asked me set up the circle method. I wrote S_i(\alpha)=\sum_{k \leq N} \Lambda(k) e(a_i k \alpha) and said that the (weighted) number of representations is \int_0^1 S_1(\alpha) S_2(\alpha) S_3(\alpha) e(-b \alpha) d\alpha. Noga asked me to define the von Mangoldt function. I defined the major and minor arcs, and then Peter asked me to jump straight to the asymptotic formula, which I couldn't do in my head. -We stopped and Peter asked me where S_i(\alpha) is maximized. After a moment, I got that it is big at \alpha=0, where it has size roughly N (by the Prime Number Theorem). Peter wanted me to talk about the value at \alpha=a/q, but without actually doing the computation. (Normally you substitute e(h/q)=1/\phi(q) \sum_{\chi (mod q)} \tau(\chi bar) \chi(h) and use Siegel-Walfisz to ignore all but the principal character. For the principal character you use the Prime Number Theorem to estimate the contribution by a rescaled sum of a geometric progression.) Anyway, I said that I would split the sum modulo q, after which the primes should equidistribute on the residue classes relatively prime to q, and Peter was satisfied. He emphasized how tiny the major arcs are, as a portion of the circle. -Eventually I just wrote down the singular series for the ordinary Vinogradov 3 primes problem (since I wanted to write something). Peter pointed out that in general there could be a whole variety of local obstructions coming from the singular series (i.e., the fact that p is the only prime that's 0 mod p), not just the example local obstruction that I had given at the beginning of our conversation. I was slightly annoyed because about 10 minutes earlier I had said that the singular series for this type of problem is recording the density of solutions mod p where you assume equidistribution on all of the nonzero residue classes, but apparently Peter had heard me wrong. -Peter also asked me about the singular series for Waring's problem. Here, we pick up the p-adic density of solutions, so you have to look mod higher powers of p. We mentioned Hensel's Lemma but didn't say anything about it. Peter said something about how this is a reason that the primes are nice, but I didn't quite catch it. -I mentioned how the singular integral contributes the growth rate of the main term and said a few words about how one would use Vinogradov's method and Vaughan's identity to bound the minor arc contribution. I described how you pull out the L^infinity norm for S_1 and then extend the remaining integral to all of [0,1). Peter stopped me after I used Dirichlet's Principle to find a rational approximation a/q to any \alpha in the minor arcs, with (crucially) both upper and lower bounds on q. -The next question was why the circle method doesn't solve Goldbach. The main term is of order N. If you try to pull out the L^infinity norm of S_1, this gives you N with some log savings. The remaining L^1 norm of S_2 is probably of order square root, which is way too big. (I mentioned that I didn't actually know how to prove that this L^1 norm has this square root lower bound, but Peter wasn't concerned with it. I also said that I knew the L^1-L^2-L^4 convexity of norms trick for lower-bounding some L^1 norms of this type.) The other thing you could try is just taking the L^1 norm of S_1 S_2, but this is of order N \log(N), which is also too big. Cauchy-Schwarz similarly fails. I think this pretty much ended what Peter had in mind for the circle method, and he suggested that Yunqing ask a question. She didn't really want to ask anything, but eventually she asked me how to determine whether or not a given positive- definte binary quadratic form represents a particular integer. I wasn't sure how to do this. I said a few true but irrelevant facts about Gauss reduced form and counting the number representations by inequivalent forms of given discriminant that. Yunqing started giving hints for what she had in mind (something I didn't catch about looking at some class group), and Peter took pity on me and said that this question wasn't fair because it was algebraic number theory (which I hadn't studied). Yunqing then asked what happens if I want to represent a number as a sum a_1x_1^2+...+a_4x_4^2. Peter liked this and asked me if I could solve it with the circle method. (I think we agreed that the a_i's don't all have the same sign.) I said that if we want to count solutions with the x_i's up to N, then the main term would have order ~N (actually, this should have been ~N^2, but none of us noticed at the time). Peter got excited and jumped in to say that the minor arc error term was doomed to be too big (look at L^4 norms, along the lines of what I had mentioned while we were talking about Goldbach). He said that for 5 or more squares, however, the circle method would indeed work. (He talked only very briefly about why.) It was now a few minutes before 6:00, so we moved onto the last topic. ---- COMBINATORICS Peter asked Noga to make his questions super short since it was so late. I basically didn't write anything on the board. Noga just wanted to see that I was generally familiar with some topics of interest. [A]: State Ramsey's Theorem. I stated the version for r-regular hypergraphs but forgot about half of the setup since I was rushing. [A]: State the Hales-Jewett Theorem. I tried to save time by saying that Hales-Jewett says that high-dimensional tic-tac-toe can't end in a draw. This didn't cut it, so I defined combinatorial lines and gave a precise statement of the theorem. [A]: Use this to prove van der Waerden's Theorem. I stated van der Waerden and said that you just interpret elements of [N]^n as integers written in base n. Noga pointed out that here Hales-Jewett gives a strengthening of van der Waerden because you get a restriction on the common differences of the arithmetic progressions. [A]: Can you find graphs with high girth and high chromatic number? I said that you can take G(n,p) with the right parameters. You find an upper bound on the expected number of short cycles, and with probability at least 1/2 the actual number of short cycles is at most double the expectation (say). At the same time, the independence number is small with high probability. Delete one vertex from each short cycle. The committee didn't want more details. [S]: What about an explicit construction of these graphs? I didn't come up with anything immediately, so Sarnak told me that expander graphs work. [A]: While we're on this topic, what can you say about the connection between a graph's spectrum and its independence number? I remembered that the smallest (i.e., most negative) eigenvalue controls the independence number, but I couldn't write down a formula. Before I got a chance to try thinking, Noga just dictated Hoffman's bound to me: If G is a d-regular graph on n vertices and -\lambda is its smallest eigenvalue, then \alpha(G) \leq n\lambda/(d+\lambda). (I would have needed many hints to produce this myself, so I was lucky that we were going at lightning speed.) [A]: State the Cauchy-Davenport Theorem. How do you prove it? I wrote down the statement of the theorem and said that you can prove it with the Combinatorial Nullstellensatz. Noga asked me if I knew another proof. I said that I thought there was some shifting argument using induction on |A+B|, or maybe induction on min{|A|,|B|}. I tried to write down the Dyson transform (I was thinking of the proof of Kneser's Theorem, which is similar). While I was staring at the board, Peter interjected with a historical note about why Davenport cared about ths problem, and Noga said that Cauchy had similar interests. Anyway, this didn't give me enough time to come up with a proof, so Noga told me that I should replace A and B with A union B and A intersect B (after which I was able to see how the rest of the proof goes). [A]: Do you know Szemeredi's Regularity Lemma? I started to state it, and Noga said that he just wanted to know whether or not I knew it. He asked me if I knew the proof, and he specified that he didn't want me to say more than "yes". [A]: Use Szemeredi to prove Roth's Theorem on arithmetic progressions. I said that you use the Triangle Removal Lemma, and I drew the relevant graph. [A]: Do you also know Roth's proof (for the integers)? I said that I did, and Noga said that he believed me. [A]: What are the best current bounds? I wrote down Bloom's new bound from last summer (|A|<>N/(e^\sqrt{\log N})) and said that the argument boils down to the fact that you can't find 3 collinear points on the surface of a sphere. ---- It was 6:20, and Peter pretty much declared that we were done. The committee kicked me out for a few minutes and then told me that I had passed! Yunqing and Peter congratulated me on their way out, and I stayed to chat with Noga for a few minutes. ---- COMMENTS I thought that the exam was fun! I was nervous in the weeks leading up the exam, but the committee was very relaxed and friendly. The professors seemed to care more about what I did know than what I didn't know. The second half of the exam felt more like a conversation than like a sequence of test questions. Like most people, I ended up studying a lot of things that didn't appear on the exam, but I learned a bunch of things along the way. My friends did two mock exams for me leading up to the real exam--those were quite helpful, especially for motivation to study. I would suggest doing a lot of practice problems early on in order to identify topics that you need to brush up on. I made the mistake of doing most of my studying before looking at any old exams, and I realized only later on that what I needed to review/learn wasn't quite the same as what I had thought I needed to review/learn.