[seqfan] Re: How many squares can you make from n points in the plane?

[Kurz, Sascha]

Doing it systematically I found a few further improvements:
a(37)>=117, a(48)>=198, a(49)>=207, a(50)>=216

Currently best known configurations are given by:
4-11:
324
XX15
XX16

12-19:
  7
4XX3
XXXX5
XXXX6
1XX2

20-36:
 GA78B
 931XXC
E5XXXXX
F4XXXXX
 6XXXXX
 D2XXX

37-47:
 6XXX7
5XXXXX8
XXXXXXX
XXXXXXX9
XXXXXXXA
4XXXXX3
 2XXX1

48-50:
  XXXX
 XXXXXX
2XXXXXXX
XXXXXXXX
XXXXXXXX
 XXXXXXX
 XXXXXX
   XX1

Here the Xs mark a starting configuration and then points are added in the
order 1,2,...,9,A,B,...

Note that all these examples have the following shape. Pick some
convex k-gon on the integer grid and choose all grid points inside.
(Also the two other optimal configurations for n=6 and n=7 are of that
shape.) Except for the step from 4 to 6, only 1-point extensions are used for
each starting configuration.

The starting configurations for n=12 and n=37 are very symmetric octagons.
Has anybody computed the asymptotics for "the" octagon yet? I would guess
that the starting positions for n=20 and n=48 may be just artefacts of my randomly
chosen 1-point extensions. So, starting from an easy-to-describe shape, where can
we get by just 1-point extensions and can we even describe the order of the
extensions? (spiral-shaped??)

Anyway, can somebody improve upon the corresponding lower bounds or should
we even extend to larger number of points to see the pattern?

A few remarks on the grid point and optimality discussion. Starting from a grid
configuration 1-point extensions will keep us on this grid (even without scaling).
2-point extensions might require to scale by a factor of two in order to stay on
the integer grid. It can be shown that for small n all optimal configurations
can be obtained from a sequence of 1- and 2-point extension starting from the
unit square. However, at least at n=13 we have to also take different possibilities
into account. There exists a constant weight code of weight 4, minimum Hamming
distance 6 , length 13, and size 13, i.e., there exist 13 4-subsets of {1,...,13} pairwise
sharing at most one element (moreover every element is contained in exactly four
4-subsets). Most likely, there is no geometric realization with squares generated
by a plane point set. Any ideas for a simple proof? While b(13)>=13 cannot be
surpassed this way, there might be more complicated configurations with just a
few squares sharing a common pair of vertices. However, I would be surprissed
if there are such examples.

I completely agree, its really fun and I like the discussion very much.

Best wishes,
Sascha


> That shows that a(49)>=202 if I counted correctly, but Sascha has an
> example with 205 apparently.
>
>Peter, Sascha: can you give me your optimal configurations ? (best
>would be: in place of an "x" to denote a vertex, put the number of
>squares it belongs to)
>
>Neil: since Sascha is on a 3-day trip, I may wait Monday or Tuesday to
>update the entry, if that's ok with you.
>
>Benoît