These are the notes of my last lecture in the 18.099 discrete analysis seminar. It is a very high-level overview of the Green-Tao theorem. It is a subset of this paper. 1. Synopsis This post as in overview of the proof of: Theorem 1 (Green-Tao) The prime numbers contain arbitrarily long arithmetic progressions. Here, Szemerédi's… Continue reading A Sketchy Overview of Green-Tao
Category: Mathematics
Formal vs Functional Series (OR: Generating Function Voodoo Magic)
Epistemic status: highly dubious. I found almost no literature doing anything quite like what follows, which unsettles me because it makes it likely that I'm overcomplicating things significantly. 1. Synopsis Recently I was working on an elegant problem which was the original problem 6 for the 2015 International Math Olympiad, which reads as follows: Problem… Continue reading Formal vs Functional Series (OR: Generating Function Voodoo Magic)
New algebra handouts on my website
For olympiad students: I have now published some new algebra handouts. They are: Introduction to Functional Equations, which cover the basic techniques and theory for FE's typically appearing on olympiads like USA(J)MO. Monsters, an advanced handout which covers functional equations that have pathological solutions. It covers in detail the solutions to Cauchy functional equation. Summation,… Continue reading New algebra handouts on my website
Approximating E3-LIN is NP-Hard
This lecture, which I gave for my 18.434 seminar, focuses on the MAX-E3LIN problem. We prove that approximating it is NP-hard by a reduction from LABEL-COVER. 1. Introducing MAX-E3LIN In the MAX-E3LIN problem, our input is a series of linear equations $latex {\pmod 2}&fg=000000$ in $latex {n}&fg=000000$ binary variables, each with three terms. Equivalently, one… Continue reading Approximating E3-LIN is NP-Hard
Vinogradov’s Three-Prime Theorem (with Sammy Luo and Ryan Alweiss)
This was my final paper for 18.099, seminar in discrete analysis, jointly with Sammy Luo and Ryan Alweiss. We prove that every sufficiently large odd integer can be written as the sum of three primes, conditioned on a strong form of the prime number theorem. 1. Introduction In this paper, we prove the following result:… Continue reading Vinogradov’s Three-Prime Theorem (with Sammy Luo and Ryan Alweiss)
The Structure Theorem over PID’s
In this post I'll describe the structure theorem over PID's which generalizes the following results: Finite dimensional vector fields over $latex {k}&fg=000000$ are all of the form $latex {k^{\oplus n}}&fg=000000$, The classification theorem for finitely generated abelian groups, The Frobenius normal form of a matrix, The Jordan decomposition of a matrix. 1. Some ring theory… Continue reading The Structure Theorem over PID’s
Miller-Rabin (for MIT 18.434)
This is a transcript of a talk I gave as part of MIT's 18.434 class, the ``Seminar in Theoretical Computer Science'' as part of MIT's communication requirement. (Insert snarky comment about MIT's CI-* requirements here.) It probably would have made a nice math circle talk for high schoolers but I felt somewhat awkward having to… Continue reading Miller-Rabin (for MIT 18.434)
Things Fourier
For some reason several classes at MIT this year involve Fourier analysis. I was always confused about this as a high schooler, because no one ever gave me the ``orthonormal basis'' explanation, so here goes. As a bonus, I also prove a form of Arrow's Impossibility Theorem using binary Fourier analysis, and then talk about… Continue reading Things Fourier
Artin Reciprocity
I will tell you a story about the Reciprocity Law. After my thesis, I had the idea to define $latex {L}&fg=000000$-series for non-abelian extensions. But for them to agree with the $latex {L}&fg=000000$-series for abelian extensions, a certain isomorphism had to be true. I could show it implied all the standard reciprocity laws. So I… Continue reading Artin Reciprocity
18.099 Transcript: Bourgain’s Theorem
As part of the 18.099 Discrete Analysis reading group at MIT, I presented section 4.7 of Tao-Vu's Additive Combinatorics textbook. Here were the notes I used for the second half of my presentation. 1. Synopsis We aim to prove the following result. Theorem 1 (Bourgain) Assume $latex {N \ge 2}&fg=000000$ is prime and $latex {A,… Continue reading 18.099 Transcript: Bourgain’s Theorem
Power Overwhelming 