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

Benoît Jubin benoit.jubin at gmail.com
Thu Sep 30 03:06:04 CEST 2021 

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/
>

More information about the SeqFan mailing list