Another better lower bound for n=17 square packing | Hacker News Reader

Another better lower bound for n=17 square packing

gus-massa.blogspot.com

30 pointsgus_massa8 comments

Responding to a couple comments here: there is no picture or new arrangement of squares because those are _upper_ bounds for the problem. The best known arrangement, i.e. the best known upper bound, has not changed.

After thinking for a while, the title should have been a "Another better higher lower bound for n=17 square packing" to avoid confusion with "Another better lower upper bound for n=17 square packing". But I was copying the title of the previous post, because it heavily builds on it.

It's tricky because even if you've seen the pictures before, it's not obvious whether the formal problem is defined in terms of minimizing the size of the big square or maximizing the size of the little squares (which are equivalent as far as the pictures are concerned).

Some of these point arrangements superficially resemble Chladni figures (https://chalkdustmagazine.com/regulars/on-the-cover/cover-ch...) coming from the vibrations of a square drum.

Orthogonally, I wonder if these arrangements are generalizable to give lower bounds for N = n^2 + 1

The old n^2+1 uses a n*(n+2) grid, but the n+2 get's hidden when you look at the symmetric version. I hope that calculating a non-symmetric version of the new weight may show an structure that is easier to understand and generalize.

Also increasing the grid may be helpful to understand which are atoms, if some ideal atoms get split to fix in the grid, and if the bars in the center are real or an artifact. (Is there a 45° rotated square in the center?). So this also may help to understand and generalize the result. But the run time grows very fast for big grids, so I'm less optimistic about this possible improvement.

None of the images has any squares.

The n=17 case is a famous math meme.

But where is the picture for this lower bound packing?

The famous one is the upper bound that shows that is possible to pack the 17 unit squares into a 4.6756... square. It's nice because you can draw the 17 unit squares and see how they fit.

This is about the lower bound that shows that it's imposible(?) to pack them into a 4.5058 square. It's harder to show, because there are no 17 unit squares because they can't fit because it's impossible(?). (Let's add a "(?)" for now until it ages.)

The first example is easy to understand. Green choose 16 points in a 4.4452... square and proved using geometry that any unit square must contain at least one of them. It can be printed on paper and you can cut a unit square and play with it and try to avoid all the points, that is an impossible task.

The later two are more difficult because each point has a weight, and it's harder to check visually.

Reply on news.ycombinator.com