In this post I’ll describe the structure theorem over PID’s which generalizes the following results:

• Finite dimensional vector fields over $k$ are all of the form $k^{\oplus n}$,
• 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 prerequisites

(Prototypical example for this section: $R = \mathbb Z$.)

Before I can state the main theorem, I need to define a few terms for UFD’s, which behave much like $\mathbb Z$: Our intuition from the case $R = \mathbb Z$ basically carries over verbatim. We don’t even need to deal with prime ideals and can factor elements instead.

Definition 1. If $R$ is a UFD, then $p \in R$ is a …

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.