It's really great to be back at Georgia
Tech I was a post doc here three years ago
I'm going to talk about
some geometric problems and
Euclidean space so sphere packing
spirital codes and kissing numbers.
In high dimensions and of course that
sounds like a purely geometric problem and
not really relevant to the topic here but
what I want to convince you is that
by looking at a kind of hard core model
you can say something about this and
there's some interesting problems.
To deal with randomness and algorithms
related to these geometric things
OK so I'll describe you know
the problems sphere packings and
spiritual codes and
higher dimensions and what's known.
Sort of survey what's known then
I'll define the hard sphere model so
this is the continuous version
of the hard core model.
Maybe my from my favorite topic
in math some of you know that
I'm obsessed with it.
And then I'll then I'll describe how
you can get some lower bounds for
these geometric objects using
this hard sphere model and
then in the end I'll conclude by
describing you know some intuition
you know describe what some of the
physicists think about these problems how
it relates to random graphs and
to mark up chains and algorithms.
OK so what's the maximum sphere
packing density in Euclidean space
is just the largest fraction of volume you
can cover and Euclidean space dimensions
with non-overlapping
spheres of the same size so
here is a little portion of
the best sphere packing and
dimension to we all we all know how
to line up pennies on a table to.
Cover the most area.
So what's known so
dimension one is trivial dimension
two you see the answer here but
it still requires a proof dimension three
we would all know how to stack tennis
balls in the best way that's the right
answer but it took a really long time.
To prove this is Thomas Hales proof and
this was gigabytes and
gigabytes of proof and required I
think a decade to do a computer for
verification of it so already there is
something quite difficult going on.
Just last year there was
a proof Maria just go the of
a Dimension eight so there was a candidate
construction for Dimension eight for
the best for packing and
she proved that this is indeed optimal and
then with some collaborators did the same
for dimension twenty four so eight and
twenty for this special dimensions because
there are these really nice lot of
says that this and the leech lattice and
these gave the candidate constructions but
the challenge was to actually show
that these are the best possible.
OK so what what's the kissing number
the kissing number in Dimension D.
is the largest number of non-overlapping
spheres of the same size
that can touch one central sphere So
here I've
proved by picture to you that the kissing
number in Dimension two is six.
And so what's what's known here so
dimension two is six
the kissing number in dimension three is
twelve so this is some history to this
problem it's sometimes called the Newton
Gregory problem because Isaac Newton and
Gregory had a dispute about this so
Newton said you can only do twelve so
I guess he was packing like cricket
balls around one cricket ball.
But it's not like to mention two so
in dimension to you saw the picture
it's rigid you can't fit you can't
move things around once you do it and
dimension three is not
rigid any of these spheres
these top spheres can move around
completely freely and so Gregory thought
if you pack it really well you can stick
one more on and so it wasn't until one
nine hundred fifty that it was proved that
actually you can't do better than twelve.
OK the next Progress was again
Dimension eight and twenty four so
this lattice sphere packings.
Actually give you.
Rigid kissing configurations.
And so exactly the same lot of as they get
from the spirit back to give you optimal
kissing configurations and
to mention it in twenty four.
The really challenging result
was to mention four and
so here the question was Was it twenty
five or twenty four and it wasn't until
two thousand and eight that likeness and
determine it's actually twenty four but
of all all the kissing results
this one is the most challenging.
That's that's the topic of the talk so
great great question yeah so.
Very good so this is yeah.
I'll tell you afterwards.
So yes so those are all the exact numbers
but we're interested in asymptotic so
and so what happens in high dimensions
if we go to dimension a million
What's the kissing number like what's
the best fear packing density how do these
behave is the tends to infinity and
in some sense much less is known.
And I'll describe what's known OK so let's
not start with Sphere packings and so
many peers for the second time in the
conference there's a very a one sentence
lower bound of two of the minus thirty so
just keep putting spheres in space until
you can't anymore now double all
the Radia this better cover space because
otherwise you could have put a center in
the empty space and since it covers and
everything's doubled the original density
must have been to the minus to OK So
I call this the covering lower bound.
OK that's nice.
You can also get a factor too by
doing something clever you know.
The big progress was by Rodgers in
one thousand nine hundred seven and
he proved that you can
get an extra factor D.
So D.
times through the minus the and
this uses he picks a random.
Lattice according to some
sort of hard measure and
uses something called the SIEGEL
mean value theorem to prove this so
really using lattice is here and so
since then there have been improvements
in using lots of interesting mathematics
important Rogers Keith
ball Stephanie Vance Tesh.
And this improves the leading
constants of the current
best constant is did I actually
think that something large I think.
One hundred thousand or something but
it's still a constant and
especially the last two papers what they
do is they still use a random lattice but
they pick a random lot as with lots and
lots of symmetries so
they use group theory to get this
better constant and in a very sparse
sequence of dimensions actually I think a
test that's a log log the factor as well.
So that's going to miss.
Things.
Yes So this is quite a big
improvement this last one
there was a lot of work
done in just improving.
Little stuff in the original Ok so
this is the lower bout And so
we've gone from the trivial
low down to the minus D.
to something D.
time through the minus D..
The upper bound is
exponentially far away so
this is due to chance
the unleavened shine in seventy.
And its two to the minus
point five nine nine D.
and and so the main takeaway is there's
a huge gap between the upper and
lower bound Henrico and you've recently
made a constant factor improvement to this
upper bound that I'll mention in in a
second but this is the state of affairs so
a linear factor improvement to
the lower bound we have this.
Really nice upper bound.
From one hundred seventy eight but
this big gap.
Are there what about kissing numbers so
to.
To tell you the results for kissing
numbers I need to describe some spiritual
geometry so a kissing configuration you
can think of as a set of unit vectors.
In dimensions whose angle
is at least PIO over three.
And so the if you project from the centers
of the kissing spheres to the center of
the central sphere these vectors have
to have angle at least over three.
And you know this is exactly a kissing
configuration a matter of the dimension
and so this is just a special
case of a sphere of code so
what's a spiritual code you
have some angle theta and
you want a set of unit vectors
whose angle is at least data and
always think of the angle as being
an acute angle between zero and pirates.
And so A of D.
theta will just be the maximal size of
a satirical code of angle theta and
dimensions and that means you
can write the kissing number is.
Over three.
So what are the bounds on the.
Size of spiritual codes.
So describe this and just say what I
mean by a spherical cap you have some X.
on the unit sphere and
the sphere a cap of angle theta is
just all unit vectors whose angle
is less than or equal to with X.
This is the purple the public out.
And.
If we take the normalized surface area
the fraction of the surface area of
the unit sphere that's covered by
such a cap if the angles acute then
this is exponentially small indie the base
of the exponents like sine data and
there is a one over routine as well.
So this is just the normalized surface
area of this cap of angle theta
OK so here is a simple lower bound on the
size of sphere of gold codes it's the same
argument as the sphere packing thing
just packed these unit vectors until you
can't anymore it better be that these
caps of angle theta cover the sphere or
else you could put another code
word another vector and so
the size of the spherical
code has to be at least
one divided by this normalize surface
area and so this is like Route D..
Times signed it into the minus to
this is really the exact
same one sentence argument.
OK for kissing numbers you
can compute the constant and
the basis of the exponent
is two of a root three.
OK so the upper bound is due to
come in Johnston Leben Stein and
they use this method of this sort of
linear programming based method for
codes and the balance for kissing numbers
is two to the point four zero one D.
again this is an exponential
gap with those lower bound.
And then the their upper bound for
sphere packing is actually
derived from this upper bound on spherical
codes with a geometric argument and so
the the improvement of Henry a new phase
in proving this geometric argument but
it still starts with
the spiritual code upper bound.
So on the one hand we have this.
Really simple lower bound on
the other hand we have this
covered John skin them in stand down and
there's a huge gap between.
OK So as far as far as I know this
with these were the only bounds on for
this problem.
And so here is the result that all
describe we get an extra factor D.
in the lower bound and so
the the maximal size of
a spherical coat of angle
faders some constant D.
to the three halves Santa
to the minus two so
this is you can think of this
an analogy like this extra D.
factor from a sphere packing.
But that you know there is a good
reason why the methods that work for
sphere packings don't work for
spherical codes for
example you can't pick
a random random let us.
OK so we can prove this by a factor D.
and the reason I'll tell you guys
about this is because it uses
some sort of hard cap model from
statistical physics to prove this beyond.
Any questions about the result
of the the history.
OK So some questions I think that you know
the main question is what's the truth
is the truth close to this is the lower
bound or is it close to this upper bound.
That's that's a mystery.
And maybe a different way of phrasing
this question is if you look at the best
spear packings in high dimensional
space do they look ordered Do they look
like a lot of says you know this is very
ordered structures or are they disordered.
Who knows and
then what role can algorithms and
randomness play in understanding
these geometric questions
OK so what's the hard to your model so
I'll talk in terms of spheres but
you can always for everything I say from
now on you can think of spiritual taps
if you want to do spiritual codes
instead of spear packings OK so
the hard sphere model is a simple
model of a gas and particles are just
represented by random non-overlapping
spheres and what happens what's
thought to happen let's say a dimension
three is that as the density increases
this model undergoes a phase transition
where we go from disordered configurations
on the left to ordered crystalline
configurations on the right but
this is completely open mathematical
problem there's no proof of this and
it seems pretty challenging
to prove that this I curse.
There's different ways of defining define
a fish transition in a few slides this one
definition but there's lots of definitions
I'll try to mention a couple but
let's say decay of
correlations thing I want.
OK so the hard sphere model provides us
with a model of random sphere packings
that aren't lattice packings because
if you think the best sphere packings
aren't lot of packings you need a model
to get your hands on some of them.
And we can use a similar model to
obtain random spiritual codes which
is a what's the model one way of saying
the model is you have some finite subset
of already you do a pause on point process
of intensity lambda and just condition on
the event that the spheres of volume one
around these points in the Point process
form a packing OK so it's just a post on
point process conditioned on the overlap.
Land as the guy city so it sort of
controls the density What's the partition
function OK so the partition function
is going to be the sum over K.
greater than zero lambda death OK
time some other partition function
what is this other
partition functions e hat.
It's if you think of the configuration
space of all sets of K.
tuples of points in S.
That's configuration space Z.
hat is first you look at the volume and
configuration space
that's occupied by a valid sphere
packings and then divide by K.
factorial to make them an ordered.
So the heart of K.
is somehow the probably that K.
unordered points from S.
form a valid sphere packing OK And
you're you're adding this up to get
the the other partition function.
So another way of defining the hard sphere
model is to say the canonical hard sphere
model is just a uniformly chosen
packing of case fears such a packing
exists and then the grand canonical
model with lambda you first choose K.
according to this weighted distribution
landed to the cazy hat of K.
divided by Z.
and then choose the packing
from the canonical model so
it's a uniformly chosen sphere packing but
you're waiting exponentially
the number of years in the packing.
OK So
historical note if you don't know this
the metropolis algorithm was actually
invented to sample from this model so
it has a long history I guess is
the reason we're here right now.
And there's lots of nice Markov
chains to sample from this model so
glad we're dynamics you could
pick a small region and
just resemble based on
the boundary conditions.
I'll say if you if you want to read more
about this Mark German recently applied
their partial rejection sampling framework
through the heart of your model and
it's like a nice illustration of
both the heart of your model and
their partial rejection
sampling out of them so
look that up OK So the partition
function tells us almost everything
we want to know about these models.
So in terms of phase transitions if we
look at the model on let's say a ball of
volume n b n take the logarithm of
the partition function divide by N.
and take the limit we get some function F.
of lambda and.
The physics definition of a phase
transition would be that there is a non
analytic point in this function F.
of lambda in so this answers your
question if you knew this function so
if you knew this function you could answer
the question of a HARD TO YOUR FACE
transition just to see if there's
a non-elect point you can also
determine the next packing density
just by taking lambda to infinity and
looking at the behavior so somehow
this one function captures both these
really challenging interesting
problems and high dimensions.
OK I'll also say this canonical partition
functions e hat also in code some
interesting information so say
the entropy of sphere packings a density
Alpha is a limit of this
canonical partition function so
basically you want to you want to say how
many how many sphere packings are there
of a certain density Well that question
doesn't make sense there's infinitely many
you also can't say what the volume of
syrup packing is at some density you know
space is infinite so instead take a big
ball look at the volume of packing
of this density in this ball take
a log of them and divide by N.
and look at this this is somehow
the large deviation rate function if you
if you throw points at random into a big
ball of volume in most of probably this
forms of packing but it's some measurement
of how plentiful sphere packings are.
OK So our goal is to understand
something about sphere packings or
spiritual codes by understanding
these partition functions.
So the first thing all say about this is
we can look at the expected density so
like and Alister Sinclair's talk about
these averages and that using model.
We can define the expected density
of the random packing from model
is just the expected size of this.
POS on point process
divided by the volume.
And this can be written in terms
of the partition function so
it's a calculation to see this you can
write this as a lead over the volume Z.
prime overeasy or in other words it's
it's like the logarithmic derivative
of the partition function.
What this also means is that you can write
the partition function by integrating this
expected density.
Since Alpha is zero and zero.
OK so here is somehow a general
approach to lots and lots of problems.
You can use the relationship
between Alpha and Z.
to prove bounds on either one so if you
can prove interesting bounds on alpha
you can integrate to obtain bounds on Z.
OK and if you can you can use this
relationship between often Z.
to locally constrain the model to
prove bounds on Alpha because of this
this isn't just for sphere packings or
anything like that this also works for say
independent sets and graphs or matchings
and graphs a lot of different things
OK so here's here's here's the result
what will prove say in the setting of
sphere packings is that if land is bigger
than three to the minus the over two
then the expected density of
this packing for any set S.
is at least this.
Time.
And so of course this this gives a lower
bound on the sphere packing density
not you know not as good
as the known balance but
also with some work it gives a lower bound
on the the entropy of sphere packings so
by integrating the bound
we've got we've got some.
Some non-trivial bound on
the entropy because so
some remarks the constant doesn't match.
There's a lot of space methods for
sphere packings.
And then it's hard to interpret this.
This bound on the entropy but
it it's better
by a factor log Do you than the there's
a trivial bound you can get on the entropy
just take the existence of a packing
shrink the sphere is a little bit and
let them rattle OK I don't know
besides the method I'll describe
I don't know any other method to get
a bound on a lower bound on the entropy.
And this is this is far off so
it gives you something non-trivial there.
And then the case of spherical Koza
kissing numbers this lower bound is new
That's the new result I mentioned.
OK So here's the proof idea it's a short
short proof and a short proof idea.
The idea is to come up with two different
lower bounds for Alpha both written as
expectations involving the partition
function of some random set to OK So T.
will be some subset of the starting
set us all describe it in a second.
But the nice thing is that these two
bounds compete against each other so
one of the bands is large when T.
is large one of the bounds is larger and
T.
is small and so you can use this
tension to get the lower bound.
OK so what's the set T.
so it's formed in by a two part
experiment and so the one thing to take
away from this method is this two
part experiment that I'll describe.
Because so first you sample your
sphere packing from the model.
And then and apparently you
choose a point in your set S.
uniformly at random.
OK And then this set T.L.
called the local view of first set
of words than a list of show you some
pictures but it's going to be the set of
all points in the double
the double ball so the A B.
R.
is the ball of volume one B.
two hours of what volume
ball of volume two D.
around V.
so all points in this double ball
around V that aren't blocks from
being in the sphere are packing by some
center that's outside of this double ball.
And so called is the set of all X.
totally uncovered points
in this fear around V OK so
that you know that's a lot of words
what does that actually mean so
what did I say first you take
this random sphere packing So
here's my random sphere packing these
are the double balls around the centers So
these these balls are allowed to overlap
but they can't include another center OK
then and apparently you pick this
point v uniformly in your set and
you're going to look at
the double ball around V.
Now the first thing you do is you
race any center that's within view
we don't care about any center that.
Is in the double ball around V.
so we race that that center and
now this random set T.
is just what's not cut out by these
double balls of the centers outside and
so we cut out everything and
then that city.
OK So this is this is the random set and
then good so this is a random set but
it's just a set in our decern comes
with its own partition function.
And we proved to lower bounds and they're
not they're not hard to prove to lower
bounds on Alpha One is that
Alpha is at least lend at times
you to the minus expectation of law a
partition function of this random set and
the others as at least some constant turns
expectation of the log partition function.
OK And the point is that if
you measure the smallness and
largeness by the partition function
the first bound is large when
she is small and
the second bound is large when T.
is large.
OK And OK so they can compete
against each other this expectation
is just a number so
we can set up this min max thing alpha is
at least the minimum overall numbers
of the maximum of these two quantities
OK One is increasing one's decreasing and
so the minimum is when there are equal.
And then it's just calculus from there so
the the solution when there are equal
is evaluation of this Lambert W.
function.
And then if you do have to set land it in
a certain way you have to set it small
enough but
also large enough but if you if you choose
the right thing then you get the result.
OK so you also get a you get this
lower bound of the free energy
by integrating the bounden Alpha.
And then you can obtain
this bound on the entropy.
OK so in the last few minutes I just want
to say something about this random graph
intuition.
OK so here's some intuition so.
Our our intuition is that somehow
dimensional Euclidean space is
somehow like a delta regular graph with
sparse neighborhoods where Delta is like
two to the D.
OK you can believe that or not.
So you know earlier we had proved a result
for independent sets and triangle for
graphs that the average independent set
density is like a log Do you ever do.
OK so this match is sure is bound for
the maximum independent set but
this is the average independent set and
city and
actually it turns out that you are new
this proof as well but then write it down.
And.
So there is a possible factor too to be
gained and shearers bound you know.
This is the important problem and
coming to tour exploit this
down on the average independence
that density is tight and
achieved by the random Delta
regular graph asymptotically and
Delta and so there's the intuition so
the intuition is saying that.
For these Euclidean space
problems fewer packing
numbers spherical codes things
are at least as good as they are for
random Delta regular graphs
the random graphs are a lower bound.
But OK so the real question is could
this conceivably be close to the truth
is is Euclidean space like
a random Delta regular graph.
No one knows of course but
the physicists reasons and
pony have a very detailed picture of what
would happen in the hard sphere model or
the sphere packing problem if there
were no very dense lot of packings so
they somehow they just assume that
there is no dense lot of packages and
then use their cavity method to describe
what you know what would happen.
And so in this case the conjecture
that there is a phase transition but
it's a glassy phase transition.
You know this is like independence
at random to regular graphs and
then the maximum sphere
packing fraction is only D.D.
logged the times through the minus D.
So if their intuition is right we're
actually very close to the truth
with the lower bounds were just
like a log to factor a way.
OK You know this depends on
whether you believe them or not.
So open problems.
You know I think one very interesting
question is is the right way to understand
packing coverings and things like this and
why dimensions is it with algebra
these constructions or
is it with stuff that maybe we know better
probabilities statistical physics and
things like this so
it's first fair packings algebra
is one thing but for spiritual.
Codes statistical physics is one so
you know I guess we're biased so
we shouldn't say our opinion about this.
OK So on one open problem I think is
improve the lower bound on the kissing
number even by a constant factor because
as far as I can tell argument is actually
really tight with a constant and so even
improving it by a constant would be nice.
But here's here's here's a open problem or
for the audience.
Show that the Glauber dynamics for
sampling sphere packings mix
rapidly up to density D.
times to the minus to.
OK so.
Why do I say this this this is
somehow equivalent to asking.
To show that the glob or dynamics for
independent sets on a random do regular
graph mix rapidly up to log over to.
Density OK so that's a challenge but I
guess when we think maybe this is true but
it's not true for
a random deregulate bipartite graph.
Write a random to regular bipartite graph
mixes slowly after tree uniqueness like
something like one over to you over to.
OK And so so I think this is really
nice it just becomes a question mark of
chain mixing times and I think if you
could show this then you've gone a long
way to show that the physics picture
is right OK But but it's sort of turns
a problem on its head you don't have
to say something about high density or
anything like that it's just a question
of low density Markov chains OK but
if you could show this then I think
then we would really have a good
understanding of sphere packings and
higher dimensions and it would
it would be saying that this physics
cavity picture is close to the truth.
OK that's it thanks.
OK.
Yeah yeah.
I.
Know.
This my argument works like somehow like.
Really locally in like a random
deregulate graph so you know boxes
I would say are like a random bipartite
graph there are these great ground states.
And this argument doesn't see them and
that's the real question
is is Euclidean space with spheres is it
like a bipartite graph or is it like a.
Random not bipartite graph.
Who knows as.
I should have said this to the minus D.
and so.
Yeah so to the minus D.
and graphs it's like one over D..
So it's like the uniqueness but
it's not you know it's also like
you know you always know there's
an independent set of size one over D.
plus one or whatever.
So it's around that balland and
now we're trying to get this D.
times to the minus D.
or like log Delta over
Delta in the graph case.
I mean there's I think Robbie can on and
Montenegro they have they have a proof of
fast mixing and it is a very simple
couple an argument for to them honestly.
So random we should be able to go
beyond that but we don't know how.