1
$\begingroup$

I have been looking for litterature on results obtained by deep neural networks to find dense (and quite possibly non-lattice, perhaps even non-periodic) sphere packings, but I have not been too successful. In fact, I am only aware of a 2002 paper by Cornforth.

What are more recent references ? If none exists, is that because there is an obvious no-go result, or is it only that nobody really tried ?

There have been numerical enumerations of best non-lattice packings in small dimensions (see e.g. the answer by Yoav Kallus to this question), so there is data to compare the results of the neural network, and if successful there, to be a little bit confident that its higher dimensional candidates are interesting too.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Sphere packing to me is an optimization problem. What should be the training data for a neural network? $\endgroup$
    – quarague
    Sep 13, 2019 at 7:04
  • $\begingroup$ Precisely the enumeration I mentionned, and the known optimal packings in dimension 8 and 24. A neural network that converges fast in all those dimensions must be doing something right, and its proposed solutions in other dimension worth looking at : in fact, we'd readily see if those beat the record holders or not. $\endgroup$
    – Archie
    Sep 13, 2019 at 17:06

1 Answer 1

Reset to default
7
$\begingroup$

There’s definitely a lot of potential for finding great packings using computers. I don’t believe the known sphere packings up through 24 dimensions are all optimal, and a clever heuristic algorithm could plausibly beat some of them. (Dimensions 19 and 21 might be the lowest-hanging fruit.) I don’t think this would be easy, but it seems like it could reasonably be within reach.

I’m not an expert on neural networks, but I’m a little skeptical that they are the right tool for this problem. There are several issues I imagine you could overcome. For example, you’d need far more training data than anyone has currently, but you could try producing it with various other optimization algorithms. Another issue is that neural networks would probably perform better with softer constraints, but there are various problems of this sort that converge to sphere packing in suitable limits.

However, the one that stumps me is feature selection. If you want to train a neural network to generate good sphere packings across a range of dimensions, how are you going to represent the packings? For example, representing a lattice using a basis doesn’t strike me as useful. I haven’t tried it, so maybe I’m totally off base here, but I’m skeptical that a neural network would find this an informative and usable representation of the lattice. (Maybe it could detect patterns in beautiful bases for particularly symmetric lattices, but I don’t expect that to generalize nicely to many dimensions.)

So my take on this is that if you have a good idea for how to go about it, it’s worth trying, but I don’t have a proposal for how you could even get started. In particular, I don’t know of any recent references, and I’d bet there are few, if any.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you very much for this detailed answer, I couldn't wish for more! $\endgroup$
    – Archie
    Sep 14, 2019 at 17:51
  • $\begingroup$ Bonus question (but please do not feel forced to answer) : might a polymath type search be a framework in which you'd be tempted to participate (at least from the sidelines, or pehaps more actively still) ? $\endgroup$
    – Archie
    Sep 14, 2019 at 17:56
  • $\begingroup$ @HenryCohn Why do you think $19$ and $21$ dimensions might be amenable? $\endgroup$
    – Turbo
    Sep 13, 2021 at 5:53
  • 1
    $\begingroup$ In 18, 20, and 22 dimensions, there are non-lattice packings that beat the known lattices, but nobody has found analogous constructions in 19 and 21 dimensions. Maybe there aren't any (it's conceivable that it's a weird parity effect), but I'm guessing that this is more a reflection of what people have tried than what's really out there, and that improvements in 19 and 21 dimensions are possible. $\endgroup$
    – Henry Cohn
    Sep 16, 2021 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.