[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 12:07:38 CEST 2021 

Thanks Neil for this summary.  I'll think about these questions.

The upper bound I gave can be divided by 6, giving a(n) <= b(n) <=
floor(n(n-1)/4).  This is because when you choose 2 points among n (to
be vertices of a square) and multiply by 3 (the three squares on these
two vertices), then you count each square choose(4, 2) = 6 times.

Benoît
PS: I am now in Paris and shouldn't be awake that late!

On Thu, Sep 30, 2021 at 7:38 AM Neil Sloane <njasloane at gmail.com> wrote:
>
> This is just about a(n), A051602, where the n points are restricted to the
> integer lattice Z x Z.
> The values for n = 1..16 given in A051602 are
> 0, 0, 0, 1, 1, 2, 3, 4, 6, 7, 8, 11, 13, 15, 17, 20,
> and the first 12 terms came from the original submission from Erich
> Friedman,
> and a(13) - a(16)  from Sean's program.
>
> We now know 0, 0, 0, 1, 1, 2, 3 are correct (because they are correct even
> for b(n), when the points are allowed to be anywhere in the plane).
>
> Sean tells me his program searched for all ways to choose n points from a
> square grid of m X m points,
> where m = ceiling( sqrt(n)).
>
> To prove that a(8), a(9), ... are correct, we could use Sean's program if
> we could prove that we can restrict the search to a square grid of size G X
> G for some moderate G.
>
> The next hopeful case would seem to be a(9). The 3X3 grid gives 6 squares
> (see Benoit's last message, or A002415). If we have 9 points with 7
> squares, there has to be at least one point outside the 3X3 box.  So G >=
> 4. But 16-choose-9  is already a pretty big number, 11400,  and G might
> need to be larger than 4.
>
> Is there a clever argument that says that if n = m^2, the square mXm grid
> arrangement  is optimal?
>
> A lot has been published about problems in combinatorial geometry.  Maybe
> this is a solved problem.
> Should someone ask Math Overflow?
>
> 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:14 PM Neil Sloane <njasloane at gmail.com> wrote:
>
> > 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/
> >>
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/

More information about the SeqFan mailing list