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

[Benoît Jubin]

One can also prove that a(n), b(n) = Theta(n^2).

For the upper bound: given n >= 2 points in the plane, you can form no
more than 3*choose(n, 2) - 2 = (3/2)n(n-1) - 2 squares on them: choose
two points and decide that they are either a diagonal or an edge of
the square (with the square lying on either side in the second case,
hence the factor 3).  Also, note that if you chose a pair of points
realizing the diameter of the figure, then the squares having this
pair as diagonal are too large to be in the figure, hence the "minus
2".

For the lower bound: if n = m^2, consider the figure formed by all the
points in [0,m-1]^2.  To count the squares it contains, note that by
choosing a in [0, m-2] and b in [1, m-1], the square with edge [(a,
0), (0, b)] has other vertices (b, a+b) and (a, a+b).  Therefore,
there are (m - (a+b))^2 translates of this square in our figure.
Therefore, the total number of squares is
S = \sum_{a=0}^(m-2) \sum_{b=1}^(m-1) (m-(a+b))^2
  = \sum_{a=0}^(m-2) \sum_{b=1}^(m-1-a) (m-(a+b))^2
  = \sum_{a=0}^(m-2) \sum_{k=a+1}^(m-1) (m-k)^2  [change of variables
(a, k) := (a, a+b)]
  = \sum_{k=1}^(m-1) \sum_{a=0}^(k-1) (m-k)^2
  = \sum_{k=1}^(m-1) k(m-k)^2
  = (1/12) m^2*(m^2 - 1)  [expand; use sums of first (m-1) integers,
squares, cubes; refactor]

Therefore, when n is a square, a(n) = (1/12)n(n-1).

Now, since a(n) is non-decreasing and square gaps are of order n =
o(n^2), the result follows.

Benoît

On Wed, Sep 29, 2021 at 5:18 PM Neil Sloane <njasloane at gmail.com> wrote:
>
> Update on A051602
>
> The original definition allowed the points to be anywhere, and the sequence
> gave 16 terms of  which only the first 6 (which were trivial) were known to
> be correct.  So I changed the definition to require the points to be grid
> points. Now there seems a much better chance of getting 16 terms exactly.
>
> However, there is still some uncertainty, because Sean's program only
> searches in a bounded portion of the grid. I don't know the details, but
> now surely we can get more than 6 or 7 exact terms.
>
> In the comments in A051602 I use b(n) for the unrestricted case, (that is,
> the original definition), and I will add the two proofs from hv and Benoit
> that b(7) = 3 there.
>
> Best regards
> Neil
>
> Neil J. A. Sloane, Chairman, OEIS Foundation.
> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
> Phone: 732 828 6098; home page: http://NeilSloane.com
> Email: njasloane at gmail.com
>
>
>
> On Wed, Sep 29, 2021 at 8:18 AM Benoît Jubin <benoit.jubin at gmail.com> wrote:
>
> > Another proof that a(7) = 3 (that is, a planar figure with 7 points
> > contains at most 3 squares, and there are figures realizing this
> > number):
> >
> > First, note that two different squares cannot share three vertices.
> > If a 7-point figure contains (at least) 3 squares, then by simple
> > counting there is a pair of squares sharing two vertices.  There are
> > only two possibilties:
> > (1) they share an edge;
> > (2) an edge of one of them is a diagonal of the other.
> > None of these 6-point figures contain a third square.  Therefore, if
> > the 7-point figure contains other squares, they are formed from a 7th
> > point, and three points in the 6-point figure (and not all three
> > belonging to the same square of that figure, by the preliminary
> > remark).  The triples of points in these 6-point figures that are in
> > square-position are few: two (one up to symmetry) in case (1), and
> > three (two up to symmetry) in case (2).  They lead to the two 7-point
> > 3-square configurations (since one of the cases in (2) yields the same
> > figure as the one from (1)).  None of these two figures contain a
> > fourth square.
> >
> > Benoît
> >
> > On Wed, Sep 29, 2021 at 6:54 AM <hv at crypt.org> wrote:
> > >
> > > I should have said: I worked below _without_ the assumption that the
> > > points had integer coordinates, so if accurate this proves something
> > > slightly stronger. _With_ that assumption, it would not have been
> > > safe to assume we can scale any arrangement to make the smallest
> > > square be a unit square.
> > >
> > > Hugo
> > >
> > > I wrote:
> > > :Neil Sloane <njasloane at gmail.com> wrote:
> > > ::It seems that surprisingly little is known - see A051602. Even a(7) is
> > an
> > > ::open question, although it is easy to see that a(7) >= 3.
> > > :
> > > :Unless I'm missing something, the 7-point case doesn't seem too hard.
> > > :
> > > :Fix 4 points on the standard unit square, and wlog assume this is the
> > > :smallest square in the final combination. There are then four
> > > :possibilities.
> > > :
> > > :A) There's another square of the same size, sharing two points with the
> > > :first. Then the 7th point can only give us a third square in two
> > > :symmetrically placed ways, of side sqrt(2). No fourth is possible.
> > > :
> > > :B) There's another square of the same size, sharing one point with the
> > > :first. Then all 7 points are accounted for. Any third square must use
> > > :two points from each of the existing two squares, so again can only
> > > :have a side of sqrt(2); that is possible, but there can't be a fourth.
> > > :
> > > :C) There's another square of a different size, sharing two points with
> > > :the first; this can only have side sqrt(2). The only ways to select
> > > :three of those points such that the 7th point can be added to give a
> > > :square in each case reduce us to case A or B.
> > > :
> > > :D) There's another square of a different size, sharing one point with
> > > :the first. All points are accounted for, and any additional square
> > > :must share two points with each of the first two squares; but then
> > > :any such third square must reduce us to case A or C.
> > > :
> > > :So the possibilities are:
> > > :
> > > :.XX
> > > :XXX
> > > :XX.
> > > :
> > > :and
> > > :
> > > :.X.
> > > :XXX
> > > :XXX
> > > :
> > > :Hugo
> > >
> > > --
> > > Seqfan Mailing list - http://list.seqfan.eu/
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/