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 present it to a bunch of students who were clearly older than me.

1. Preliminaries

1.1. Modular arithmetic

In middle school you might have encountered questions such as

Exercise 1. What is $3^{2016} \pmod{10}$?

You could answer such questions by listing out $3^n$ for small $n$ and then finding a pattern, in this case of period $4$. However, for large moduli this “brute-force” approach can be time-consuming.

Fortunately, it …

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 the fancier generalizations using Pontryagin duality and the Peter-Weyl theorem.

In what follows, we let $\mathbb T = \mathbb R/\mathbb Z$ denote the “circle group”, thought of as the additive group of “real numbers modulo $1$”. There is a canonical map $e : \mathbb T \rightarrow \mathbb C$ sending $\mathbb T$ to the complex unit circle, given by $e(\theta) = \exp(2\pi i \theta)$

I will tell you a story about the Reciprocity Law. After my thesis, I had the idea to define $L$-series for non-abelian extensions. But for them to agree with the $L$-series for abelian extensions, a certain isomorphism had to be true. I could show it implied all the standard reciprocity laws. So I called it the General Reciprocity Law and tried to prove it but couldn’t, even after many tries. Then I showed it to the other number theorists, but they all laughed at it, and I remember Hasse in particular telling me it couldn’t possibly be true.

Still, I kept at it, but nothing I tried worked. Not a week went by — for three years! — that I did not try to prove the Reciprocity Law. It was discouraging, and meanwhile I turned to other things. Then one afternoon I had nothing …

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 $N \ge 2$ is prime and $A, B \subseteq Z = \mathbb Z_N$. Assume that $$\delta \gg \sqrt{\frac{(\log \log N)^3}{\log N}}$$ is such that $\min\left\{ \mathbf P_ZA, \mathbf P_ZB \right\} \ge \delta$. Then $A+B$ contains a proper arithmetic progression of length at least $$\exp (\mathrm{C\; \dots }$$

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 first part of my presentation.

1. Synopsis

In the previous few lectures we’ve worked hard at developing the notion of characters, Bohr sets, spectrums. Today we put this all together to prove some Szemerédi-style results on arithmetic progressions of $\mathbb Z_N$.

Recall that Szemerédi’s Theorem states that:

Theorem 1 (Szemerédi)

Let $k \ge 3$ be an integer. Then for sufficiently large $N$, any subset of $\{1, \dots, N\}$ with density at least $$\frac{1}{(\log \log N)^{2^{-2^k+9}}}$$ contains a length $\mathrm{k\; \dots }$

Happy Pi Day! I have an economics midterm on Wednesday, so here is my attempt at studying.

1. Mechanisms

The idea is as follows.

• We have $N$ people and a seller who wants to auction off a power drill.
• The $i$-th person has a private value of at most $\$1000$ on the power drill. We denote it by $x_i \in [0,1000]$.
• However, everyone knows the $x_i$ are distributed according to some measure $\mu_i$ supported on $[0, 1000]$. (Let’s say a Radon measure, but I don’t especially care). Tacitly we assume $\mu_i([0,1000]) = 1$.

Definition 1. Consider a game $M$ played as follows:

• Each player $i=1,\dots ,\mathrm{N\; \dots }$

These notes are from the February 23, 2016 lecture of 18.757, Representations of Lie Algebras, taught by Laura Rider.

Fix a field $k$ and let $G$ be a finite group. In this post we will show that one can reconstruct the group $G$ from the monoidal category of $k[G]$-modules (i.e. its $G$-representations).

1. Hopf algebras

We won’t do anything with Hopf algebras per se, but it will be convenient to have the language.

Recall that an associative $k$-algebra is a $k$-vector space $A$ equipped with a map $m : A \otimes A \rightarrow A$ and $i : k \hookrightarrow A$ (unit), satisfying some certain axioms.

Then a $k$-coalgebra is …

The following is an excerpt from a current work of mine. I thought I’d share it here, as some people have told me they enjoyed it.

As I’ll stress repeatedly, a matrix represents a linear map between two vector spaces. Writing it in the form of an $m \times n$ matrix is merely a very convenient way to see the map concretely. But it obfuscates the fact that this map is, well, a map, not an array of numbers.

If you took high school precalculus, you’ll see everything done in terms of matrices. To any typical high school student, a matrix is an array of numbers. No one is sure what exactly these numbers represent, but they’re told how to magically multiply these arrays to get more arrays. They’re told that the matrix

$$(\begin{array}{cccc}1& 0& \dots & 0\\ 0& 1& \dots & 0\\ \mathrm{⋮}& \mathrm{⋮}& \ddots & \mathrm{⋮}\\ 0& \mathrm{0\; \dots }\end{array}$$

This post has now become a PDF handout on my website.

Let $V$ be a normed finite-dimensional real vector space and let $U \subseteq V$ be an open set. A vector field on $U$ is a function $\xi : U \rightarrow V$. (In the words of Gaitsgory: “you should imagine a vector field as a domain, and at every point there is a little vector growing out of it.”)

The idea of a differential equation is as follows. Imagine your vector field specifies a velocity at each point. So you initially place a particle somewhere in $U$, and then let it move freely, guided by the arrows in the vector field. (There are plenty of good pictures online.) Intuitively, for nice $\xi$ it should be the case that the trajectory resulting is unique. This is the main take-away; the proof itself is just for …