It's cool to see a piece of mathematics that I am personally very interested in show up on HN!
From a pure mathematics standpoint, I am most interested in asymptotics (what happens as n becomes very large).
Some tidbits which might be interesting:
* Here's an argument saying there must always be a triangle of area less than about 1/n. Divide the unit square into n/3 vertical strips. By the pigeonhole principle one of the strips must contain three points. The strip has area about 1/n, so the triangle also has area at most 1/n.
* In contrast, the best known lower bound is something like (log n)/n^2 - very far from 1/n.
* After quite a bit of work by a number of authors, Komlós, Pintz & Szemerédi proved in 1981 an upper bound essentially of the form n^(-8/7), still quite far from the n^2 lower bound!
* Remarkably, there was no progress for over 40 years, until a few years ago two PhD students at MIT (Alex Cohen and Dima Zakharov) along with Cosmin Pohoata beat this upper bound by some small factor, and then later improved it to n^(-7/6) a year or so later. (See [1] for an overview of their work.)
* This problem is related to a more general family of incidence geometry problems called 'lower bounds for incidences': given some collection of geometric objects (say, points and lines), under what conditions can we guarantee that there are in fact more 'almost incidences' than we originally expect?
> This problem is related to a more general family of incidence geometry problems called 'lower bounds for incidences': given some collection of geometric objects (say, points and lines), under what conditions can we guarantee that there are in fact more 'almost incidences' than we originally expect?
I wonder if there are some other related problems for small-n cases that I could add somewhere on this website?
1. One can ask the same problem but for k-gons instead of triangles.
2. Given a set of point-line pairs (x1, l1), ..., (xn, ln) [[that is, each xj lies in the line lj]], consider the smallest distance between some xi and lj where i != j. Then as in Heilbronn's problem we want configurations so that this smallest distance is as large as possible.
In 2 here we already see a key feature of 'incidence lower bounds' problems: we need to assume some initial 'trivial incidences' for the problem to make sense at all. If we didn't require them; we could put all the points at the top, and the lines at the bottom, and call it a day! The 'trivial incidences' force the points and lines to be spatially mixed; then we want to find a 'non-trivial incidence'.
Asymptotics for problem 1 are very open (seems decently harder than Heilbronn) but problem 2 was recently solved by Cosmin [1]
Actually, information about (2) immediately gives you something about the Heilbronn problem: take your n points, and use them to define n/2 lines. This gives a family of n/2 points and n/2 lines (forgetting about the 'other' point on each line). Apply the best answer you get to (2), to find a point of distance r to some line. Since that line originally came from two other points, you get a triangle of area ~ r. This is where the best known asymptotics for Heilbronn's problem come from.
I made this website to showcase the Heilbronn problem, which is a classic problem in optimization. Lately there has been a wave of contributions of new records made by amateur mathematicians - you could be one of them!
If you want to make a PR to put in a new submission, feel free to do so. There's no particular reason why the site currently stops at 35-36 points, other than computational limits.
It's cool to see a piece of mathematics that I am personally very interested in show up on HN!
From a pure mathematics standpoint, I am most interested in asymptotics (what happens as n becomes very large).
Some tidbits which might be interesting:
* Here's an argument saying there must always be a triangle of area less than about 1/n. Divide the unit square into n/3 vertical strips. By the pigeonhole principle one of the strips must contain three points. The strip has area about 1/n, so the triangle also has area at most 1/n.
* In contrast, the best known lower bound is something like (log n)/n^2 - very far from 1/n.
* After quite a bit of work by a number of authors, Komlós, Pintz & Szemerédi proved in 1981 an upper bound essentially of the form n^(-8/7), still quite far from the n^2 lower bound!
* Remarkably, there was no progress for over 40 years, until a few years ago two PhD students at MIT (Alex Cohen and Dima Zakharov) along with Cosmin Pohoata beat this upper bound by some small factor, and then later improved it to n^(-7/6) a year or so later. (See [1] for an overview of their work.)
* This problem is related to a more general family of incidence geometry problems called 'lower bounds for incidences': given some collection of geometric objects (say, points and lines), under what conditions can we guarantee that there are in fact more 'almost incidences' than we originally expect?
[1] https://www.quantamagazine.org/the-biggest-smallest-triangle...
Fun fact the city of Heilbronn uses the code HN on license plates (it’s named after a person not the city though)
Being born in Heilbronn and living in the are this was a "the what problem" moment indeed.
> This problem is related to a more general family of incidence geometry problems called 'lower bounds for incidences': given some collection of geometric objects (say, points and lines), under what conditions can we guarantee that there are in fact more 'almost incidences' than we originally expect?
I wonder if there are some other related problems for small-n cases that I could add somewhere on this website?
Maybe here are the easiest ones to state:
1. One can ask the same problem but for k-gons instead of triangles.
2. Given a set of point-line pairs (x1, l1), ..., (xn, ln) [[that is, each xj lies in the line lj]], consider the smallest distance between some xi and lj where i != j. Then as in Heilbronn's problem we want configurations so that this smallest distance is as large as possible.
In 2 here we already see a key feature of 'incidence lower bounds' problems: we need to assume some initial 'trivial incidences' for the problem to make sense at all. If we didn't require them; we could put all the points at the top, and the lines at the bottom, and call it a day! The 'trivial incidences' force the points and lines to be spatially mixed; then we want to find a 'non-trivial incidence'.
Asymptotics for problem 1 are very open (seems decently harder than Heilbronn) but problem 2 was recently solved by Cosmin [1]
Actually, information about (2) immediately gives you something about the Heilbronn problem: take your n points, and use them to define n/2 lines. This gives a family of n/2 points and n/2 lines (forgetting about the 'other' point on each line). Apply the best answer you get to (2), to find a point of distance r to some line. Since that line originally came from two other points, you get a triangle of area ~ r. This is where the best known asymptotics for Heilbronn's problem come from.
[1] https://arxiv.org/pdf/2607.20422
Hi there,
I made this website to showcase the Heilbronn problem, which is a classic problem in optimization. Lately there has been a wave of contributions of new records made by amateur mathematicians - you could be one of them!
It seems like this post got put into some kind of "second chance" queue - thanks @dang! I'm around to answer questions if anyone has them.
Github repo for the site: https://github.com/tejstead/heilbronn-site
Also, check out the entry for square n=16, I added a pretty cool animation there.
What's the criterion for getting listed as the current best known value? (I'm kind of confused why that list isn't infinitely long.)
If you want to make a PR to put in a new submission, feel free to do so. There's no particular reason why the site currently stops at 35-36 points, other than computational limits.
Came here for the Magic Soap
what?