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

Category: Math

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?

The Polynomial Ham Sandwich Theorem states that in n-space, we can bisect \binom{n+k}{n} - 1 measures with a degree k variety. What’s the lowest degree polynomial surface in \mathbb{R}^3 that bisects every human heart from this argument?

By the Ham Sandwich Theorem, we need surprisingly few! With n = 3,  the smallest k for which \binom{n+k}{n} - 1 \ge 7280000000 is k \approx 3520. This is as expected a cubic reduction in dimension (hidden underneath is the fact that a polynomial of degree k in 3-space actually has O(k^3) degrees of freedom, so it’s not exactly surprising), so there is a degree 3520 algebraic variety that not only passes through, but cuts every human heart exactly in two.

That’s all well and good, but clearly Solzhenitsyn envisioned his problem on the 2-sphere, where “line” actually means line or curve and not plane or surface. So really the right question to ask is: what is the smallest degree polynomial curve embedded in the unit sphere S^2 that bisects 7280000000 heart-shaped regions? We get a nice answer to this modified question by simply intersecting the degree 3520 variety above with the sphere. Phew!

It’s fun to think about what this degree 3520 algebraic curve on the sphere looks like. It cuts the sphere into a bunch of connected components, some components are good, some components are evil. But it’s a line between good and evil, so good components are only next to evil components, and evil components must be next to good components! Does this present problems? Happily, if you draw a generic smooth curve on the plane or sphere without lifting your pen, the map of the regions is 2-colorable (exercise: the graph will have only even cycles for faces), so this checks out. Phew!

The number of connected components will in general be quite large. In real algebraic geometry, these components are called nodal domains, and the maximum (and generic) number is essentially k^2. We will thus expect on the order of 10 million connected components on the sphere cut by our single curve of degree 3520.

I will henceforth call this map Solzhenitsyn’s Yin Yang – an algebraic checkerboard of black and white regions cut out by a single continuous curve that passes through every human heart. What an interesting development over the traditional Yin Yang! Well, maybe more cliché than interesting. If you tried to draw Solzhenitsyn’s Yin Yang there would be so many tiny black and white regions everything would look gray from space.

Solzhenitsyn’s Yin Yang



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'.

Lemma. Two expansion functions \Phi_{\tau_1}(w_1,w'_1,X) and \Phi_{\tau_2}(w_2,w'_2,X) are orthogonal unless the corresponding strips are parallel or intersect on the boundary of the cutoff region.

Proof. The intersection of two strips is a parallelogram whose area is proportional to the widths of each strip. \Box

Thus, the set of functions \Phi_{\tau}(w,w',X) form a quasi-orthogonal set, to which we can apply a generalization of Bessel’s inequality. One option is the generalization of Bombieri:

\sum_{\tau} (\Phi_{\tau}(w,w',X),f)^2 \le \|f\|_2 ^2 \cdot \max_{\tau} \Big(\sum_{\tau'} |(\Phi_{\tau}, \Phi_{\tau'})|\Big)

The point is that the left side must be small because they are all Fourier coefficients of f with respect to an essentially orthogonal set. But the left side can be thought of as the “mean square expansion” of the strips in question, that is to say we have found a bound telling us that on average, no strips acquire too many more points than expected when we expand them from width w to a much wider width w'.

To finish the proof, one may simply observe that there are few points in very narrow strips – otherwise any three such points will form a triangle of tiny area. Then, apply the “mean square expansion” bound above and we see that there are also few points in wide strips, which contradicts something like the pigeonhole principle since there are many wide strips and many points in total.

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

I’m interested in the much harder problem of constructing primitive sets with similarly small gaps. To do this using the same method requires a way to randomly generate infinite antichains of \mathbb{N}. Here is a naive way to do this: take every positive integer n and attach to it a weight f(n)\in [0,1]. Sort the naturals by size, and at each n, flip an f(n)-weighted coin in our antichain A if no divisor of n has been included yet, and add n to A if it comes up heads. In general, we should expect A to always be infinite if f(1)=0, and hopefully have small gaps.


Geometric Progression-Free Sequences with Small Gaps II

Zero-sum Subsequences of Length kq over Finite Abelian p-Groups

Geometric Progression-Free Sequences with Small Gaps

Cross Number Invariants of Finite Abelian Groups

On the Classification of Universal Rotor-Routers