What kind of curve is uniquely defined by these two points? A
line.
How about three points? A circle.
This basic geometry is ancient history. Euclid
proved it more than two thousand years ago
in his seminal math treatise "Elements."
Now try to figure out the shape of a curve that passes through a million points in a 1,000 dimensions
and is super twisty. What would that look like?
Although daunting, finding a solution to this problem is
fundamental to probing deeper principles of math. And the
solution also holds the potential to improve digital
data storage, the security of your crypto wallet, and the
privacy of electronic communications. It's called the
interpolation problem. And two young mathematicians, Eric
Larson and Isabel Vogt of Brown University have solved it.
The interpolation problem asks, If you fix some general
collection of points, when is there a curve of some specified
type through those points?
In search of answers, the pair chipped away at the problem for
years,
We started out tackling cases in small dimensional spaces to try
to get our hands dirty and see the sort of techniques that we
would need. And then I think around 2019 or so we came up
with a good idea that we thought might help us solve the whole
problem.
Along the way, their collaboration took on a whole
new dimension,
Well, we got married in 2017.
Much of the groundwork for a potential solution was laid out
150 years ago by German mathematicians, Alexander von
Brill and Max Noether
Before you can ask what properties does a given type of
curve have, you need to first answer the question of what
types of curves are there?
The theorem predicts what types of curves can exist based on
three properties. The first is dimension,
You can think about a curve in actual physical space, that
would be a three dimensional space. But we don't constrain
ourselves to two dimensions or three dimensions.
The second quantity is the degree of a curve.
So you should think, here, like how twisty or wobbly the curve
is.
The third is the genus or number of holes a curve has.
Curves themselves, have a sort of topological property. But if
you were to look at the solutions over the complex
numbers, then it's going to look like something that's two
dimensional. So it could look like a sphere. Or it could look
like the surface of a doughnut. Or it could look like the
surface of a two-hole doughnut. In general, it can have any
number of holes.
It wasn't until the 1980s that modern math offered a proof of
Brill-Noether. And this opened doors to the interpolation
problem. Larson and Vogt, we're determined to solve the problem
for all possible types of curves.
We had to come up with three different ways of breaking the
curve into simpler curves. So we take some curve, it's
complicated, it's very wobbly. So we take this wobbly curve,
and we break it in three different ways.
By breaking down the complex curve in multiple steps, Larson
and Vogt were able to get something simple enough that
they could attack it with their bare hands.
We knew how slippery it was, how you really had to work hard to
get everything to match up,
Larson and Vogt's proof confirmed the interpolation
problem in all cases, showing that curves will always
interpolate through the expected number of points with only four
exceptions, which they also explained. The couple's proof is
a powerful tool for exploring a whole new class of ideas.
Bit of a surprise to finally complete it,
you know, it's you've just been thinking, oh, this is what I do
is I work on this problem, but then you're like, wow, it's
done.
More than 2,000 years ago, the Greek mathematicians Zenodorus
argued that a sphere is the optimal shape of a single
bubble. This may seem obvious, but it took until the late 19th
century to prove it mathematically. What about a
cluster of multiple bubbles?
Researchers study bubbles to both better understand their
geometric properties and potentially improve everything
from computer algorithms and biological cell models to
firefighting foams. For decades, mathematicians have sought the
optimal configuration of larger bubble clusters. But it turns
out the solution is one of the hardest problems in geometry.
The bubble problem can be stated simply: What configuration of
bubbles encloses a given number of volumes while minimizing
surface area.
And the key point is that the surfaces are allowed to, like, if I
smashed my bubbles together I'm allowed to save the surface
that's between them. I mean, it's an optimization problem.
And that's such a universal kind of problem with all kinds of
applications.
From our own experience of blowing bubbles, we know that
larger clusters of bubbles tend to form tight clumps rather than
a long chain. But how can we know whether these formations
are actually optimal?
In the 1990s, John Sullivan, now of the Technical University of
Berlin, formed a guiding conjecture,
He described what we now call a standard bubble or a standard
bubble cluster. They're spheres. They meet at 120 degree angles.
They all touch. There could be lots of different ways to
achieve that. It turns out that that's not the case.
Sullivan's conjecture states, if the number of volumes you want
to enclose is at most one greater than the dimension,
there's one cluster configuration, that's the best.
There's basically one way to achieve this and his conjecture
was that this way is the optimal way.
To visualize Sullivan's optimal cluster place four points
equidistant on a sphere. Inflate the points into bubbles or disks
on the surface until they bump into each other. Keep inflating
them until the entire sphere is covered. We end up with a
symmetric cluster that all touch and meet at 120 degree angles.
Now place the sphere on a flat plane. Add a light at the north
pole to cast a two dimensional shadow of three bubbles. Rolling
the sphere around creates clusters of Sullivan's shadow
bubbles that can enclose any three areas.
By 2002, mathematicians had proved Sullivan's conjecture for the
double bubble. And at this point, some speculated another
100 years would pass before a proof for three bubbles could be
found. But then Emanuel Milman of Technion University, and Joe
Neeman of the University of Texas, Austin entered the
picture.
So what we were working on was sort of the probabilistic
version of this problem. And we were interested, actually,
originally, we were just we would have been happy to do
double bubble at the beginning. We were like, you know, we have
to come up with something new. Right. And so we came up with
some new things.
After some success solving the analogous probabilistic bubble
problem, the pair hit a snag transferring their new
techniques to the geometric one.
So we were stuck on this for a long time. And definitely a
breakthrough came when we actually, we kind of gave up to
be honest.
Milman and Neeman realized that if you give bubbles, one extra
dimension of space, you get a bonus: The best bubble cluster
will have mirror symmetry across a central plane.
We were like, okay, let's give up on what we were trying to do
and see what we can get from the symmetry. And then as soon as we
had that symmetry that, you know, that symmetry combined
with what we had been working on for the previous three years,
all of a sudden, like then we were able to move on from there.
But Milman and Neeman's proof of Sullivan's conjecture for
triple bubbles in dimensions three and up is not the end of
the story.
We're stuck at a maximum of five bubbles right now. But I feel
like it's just like a tiny little thing that we are not
seeing and then that problem will go away.
Take a set of points and start randomly connecting them with
lines. At what point will an interesting pattern emerge? Like
a triangle or a Hamiltonian cycle, a chain of lines that
passes through each point exactly once. In a branch of
math called combinatorics, graphs like these are valuable
tools for probing the inner workings of complex systems.
A graph is just another name for a network.
Networks are everywhere like Facebook network. You can think
about traffic networks, you know, or business networks and
things like that.
But real life networks can be huge and hard to study. So
mathematicians use random graphs to model their properties.
In the random graph theory, finding thresholds is a central
subject. People worked on finding threshold for each of
interesting properties.
Interesting properties can emerge as you increase the
density of lines in a random graph. The sudden moment of
change is defined by a threshold. In nature thresholds
are responsible for abrupt transformations and the
emergence of complex patterns.
But it turns out that determining threshold is
extremely difficult.
Instead, mathematicians use a method to arrive at a ballpark
figure.
There is a very natural lower bound to the threshold that we
call the expectation threshold. The expectation threshold turns
out to be much easier to estimate or determine.
In 2006, mathematicians Jeff Kahn and Gil Kalai posed their
expectation threshold conjecture. It states that the
gap between the expectation threshold and the real threshold
is at most a logarithmic factor, but sometimes smaller, or even
nonexistent.
The Kahn-Kalai conjecture just gives one simple solution to
find out the location of the threshold for many, many
interesting properties. So it's just so powerful, and it was
hard to believe that this conjecture is true.
That was until two mathematicians at Stanford,
Jinyoung Park and Huy Pham, stumbled onto an elegant six
page solution after a long sleepless night.
It really came about by really not working or aiming directly
at the Kahn-Kalai conjecture.
It was a surprise that we found out another way.
The pair were instead working on several related conjectures.
Like, you know, you're like taking a walk that you aim at a
seemingly very different and distant destination, but on the
way, you are suddenly able to find some very surprising hidden
beauty.
A key breakthrough was the realization that a method
developed in the pursuit of one conjecture could be used in a
different manner to solve Kahn-Kalai. The solution
utilized a mathematical object called a cover.
You can think about a cover as essentially a kind of necessary
condition, a witness to the fact that the network satisfies the
properties.
Park and Pham employed an algorithm to sample subsets of a
random graph to home in on the cover.
In the end, we verify this cover is small, in particular, so that
is exactly how we prove the conjecture.
Park and Pham's concise proof of Kahn-Kalai is expected to lead
to new breakthroughs.
This would allow us to get a much better handle on complex
properties of networks and this is certainly usefull in many
applications not just in math or in probabilistic
combinatorics, because networks are involved everywhere.