"Everything can be made radically elementary." ~Steven Rudich

Category: Math



As usual, post solutions in ROT13.


Harry Potter and the Method of Entropy

I did some Aversion Factoring and found that my main aversion to writing math is the terrible LaTeX support on WordPress. For now, I’ll try writing things up offline and posting PDFs.

HPMoE is a sequence on the entropy method in combinatorics. It should be fun to think about for anyone interested in information theory and probability as well.


Please post solutions to the exercises in ROT13.

Solzhenitsyn’s Yin Yang

If only it were all so simple! If only there were evil people somewhere insidiously committing evil deeds, and it were necessary only to separate them from the rest of us and destroy them. But the line dividing good and evil cuts through the heart of every human being. And who is willing to destroy a piece of his own heart?
Aleksandr Solzhenitsyn, The Gulag Archipelago 1918-1956

Solzhenitsyn states that the line dividing good and evil cuts through every human heart. This can’t literally be true – human hearts are somewhat evenly distributed around the globe.

The first question we might ask is: instead of a line, what’s the simplest surface we can draw that cuts through the heart of every human being? But simply cutting through is a boring interpolation question. If you’re an idealist like me, you’d think every human heart is exactly half good and half evil. So the real question is: what’s the simplest surface that bisects every human heart?

Read the rest of this entry »

Ramanujan Graphs

Here is an exposition of the construction of bipartite Ramanujan graphs for my own benefit, starting from basics about expanders: RamanujanGraphs.

Solutions to Exercises from the Probabilistic Method

I have compiled my solutions to exercises of the first 9 chapters of Alon and Spencer’s excellent book The Probabilistic Method (second edition). Hopefully in the future I will fill out the solutions to the remaining chapters. Here they are: solutions_compilation. Please send comments/corrections to alkjash876@gmail.com.

The Heilbronn Triangle Problem

I recently gave a talk (here is an outline) about the work of K. F. Roth on the famous triangle problem of Heilbronn, and was shocked and saddened to discover that Roth passed away that same day. Terry Tao wrote a great post about some of Roth’s most important results in analytic number theory.

Today I will discuss the general approach of Roth, later refined by Komlos, Pintz, and Szemeredi, in proving upper bounds for the Heilbronn Triangle Problem. At the end of the day, the most interesting step comes from a quasi-orthogonality property between indicator functions of bounded strips in the plane. Let \tau be a pair of points in the plane and let \phi_{\tau}(w,X) be the indicator function of the strip of points at most w away from the line through \tau. We cut off these functions outside some convex region, say the unit circle – call this the cutoff region. Then, it is natural to consider the “expansion function”

\Phi_{\tau}(w,w',X) = \frac{1}{w}\phi_{\tau}(w,X) - \frac{1}{w'}\phi_{\tau}(w',X),

which measures the weighted difference between two strips of different widths w, w' around the same line. The point is that if we integrate this expansion function against the indicator function f of a given set of points in the plane, then (\Phi_{\tau}, f) counts the change in the density of points when we expand from a strip of width w to a strip of width w'.

Read the rest of this entry »

Primitive Sets with Small Gaps

A primitive set is a set S of positive integers such that no pair of distinct elements a,b\in S satisfies a | b.

A square-primitive set is a set of positive integers S such that no pair of distinct elements a, b \in S has ratio a/b equal to an square integer.

In the following writeup, I show how to construct square-primitive sets with very short gaps O_{\epsilon} ((\log N)^2 (\log \log N)^{\epsilon}). This relies on dividing the poset \mathbb{N} ordered by divisibility into antichains A_m consisting of all numbers in \mathbb{N} with exactly m (not necessarily distinct) prime factors, and then picking one randomly.

Square Primitive Sets With Small Gaps

Read the rest of this entry »