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

Neil Sloane njasloane at gmail.com
Thu Sep 30 03:14:40 CEST 2021 

By the way, for the lower bound you could have referred to A002415
(although there is a lot to be said for having a self-contained proof).

Thanks for the typos!

I thought you were in Luxembourg?  Glad someone else likes to work at
03:00.

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 9:06 PM Benoît Jubin <benoit.jubin at gmail.com> wrote:

> Thanks Neil. You may have noticed the typo
> (a, a+b) --> (a+b, a)
> and towards the end, a(n)>=... and not =, although equality is likely.
> Benoît
>
>
> Le jeu. 30 sept. 2021 à 01:15, Neil Sloane <njasloane at gmail.com> a écrit :
>
> > Benoit,  That is very nice!  I will add it to A051602.
> > 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 4:40 PM Benoît Jubin <benoit.jubin at gmail.com>
> > wrote:
> >
> > > 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/
> > >
> > > --
> > > Seqfan Mailing list - http://list.seqfan.eu/
> > >
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>

More information about the SeqFan mailing list