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

Benoît Jubin benoit.jubin at gmail.com
Tue Oct 5 01:09:07 CEST 2021


Hi all,

Here is an attempt at summarizing what has been found so far on
oeis.org/A051602.  Please tell me if I forgot something or if I
misattributed some results or forgot to credit or mention you (knowing
that the simpler or more trivial remarks and results can be left
unattributed and considered folklore).  Since this will serve as a
draft to my edit, please also tell me if I'm going against some OEIS
conventions, in particular notational conventions.

Sascha: what are you run-times ? How far can you compute these
configurations ? Can you compute one around n = 140 ? This could
probably tell circles and octagons appart (my bet is now on circles).

Peter: I reworded your proof.  Your and my wordings may appeal to
people with different backgrounds.  Should I copy yours in a txt file
to be joined to the sequence ?  Or do you prefer the other way around
?

Thanks,
Benoît
________________________________________________________________________________
New values
a(0) = 0 (Neil: I'm sure you saw that coming!)
____________________
General comments
This sequence, a, enumerates squares whose vertices are grid points
(points in G := ZZ x ZZ).  The similar sequence where vertices are not
required to be on the grid is denoted by b.  One has a(n) <= b(n) and
we do not know whether a = b.  If and when we find a value n such that
a(n) < b(n), an OEIS entry will be added for b.  Given that a square
with two vertices in G has its other two vertices either in G or in G
+ (1/2, 1/2), so that dilating the configuration yields a
"grid-configuration", it is likely that a = b.

The general problem of estimating the maximal number of similar
figures within point-configurations was initiated in [Elekes--Erdos]
and references can be found in [Matousek, p. 47] and [AFKK].  Note
that the present problem concerning squares shares several properties
with the case of right isosceles triangles treated in [AFR].
____________________
Exact values
Values for n <= 9 are exact and are the same for a and b (see proofs
below by Hugo van der Sanden and Benoît Jubin for n<=7 and Sascha Kurz
for n<= 9, which furthermore classify all optimal configurations for
these values).
Values for n > 9 are conjectural since they were obtained by
exhaustive search for grid points within a square of side
ceil(sqrt(n)), which is a reasonable assumption.  A proof that optimal
configurations (with least side length equal to 1) have a diameter at
most f(n) with f of reasonable growth would permit exact computation
of values from exhaustive searches.
____________________
Lower bounds
Computer searches, using glutton algorithms starting with all grid
points in a convex polygon and adding successive points, have given
the following current record configurations, which thus yield lower
bounds for a(n).  They are due mainly for n <= 36 to Sean A. Irvine
and for 37 <= n <= 50 to Sascha Kurz, with preliminary work by Hugo
van der Sanden.
The representations below are given for ranges of n, and the integers
indicate at what stage a given node is added (the letters A--Z encode
the integers 10--36).  For instance, the first representation encodes
the sequence of configurations
                  X
XX ; XXX ; XXX ; XXX ; etc.
XX ; XX  ; XXX ; XXX
----------
n = 4--11
435
00016
00027
----------
n = 12--19
  7
4003
00005
00006
1002
----------
n = 20--36
 GA78B
 93100C
E500000
F400000
 600000
 D2000
----------
n = 37--47
 60007
5000008
0000000
00000009
0000000A
4000003
 20001
----------
n = 48--50
  0000
 000000
20000000
00000000
00000000
 0000000
 000000
   001
----------
In particular, a(37)>=117, a(48)>=198, a(49)>=207, a(50)>=216.
____________________
Asymptotic behavior
One has a(n), b(n) = Theta(n^2):
Upper bound:  since squares are determined by two vertices, one has
b(n) = O(n^2).  More explicitly: a pair of points uniquely determines
the square who has it as diagonal, and a square has two diagonals, so
b(n) <= n(n-1)/4 ~ n^2/4.
Lower bound:  we give two proofs:
First proof:  When n = m^2, the set of all grid points in [0, m-1]^2
yields S = n(n-1)/12 squares.  Indeed, for a in [0, m-1] and b in [1,
m], the square formed on (a,0) and (0,b) (as its "lower-left side")
has other vertices (a+b,b) and (a,a+b), so there are (m-(a+b))^2
translates of that square.  Therefore, S = sum_{a=0}^{m-1} sum_{b=1}^m
(m-(a+b))^2.  By change of summation indices ((a,c):=(a,a+b)),
expanding, using the sum of the first m integers, squares, cubes, and
refactoring, one obtains S = n(n-1)/12. Since a is non-decreasing, one
has a(n) >= (n-1)(n-2)/12 ~ n^2/12.
Second proof (due to Peter Munn):  For r >= 0, denote by D(r) the disc
centered at the origin with radius r.  If A is a point on the boundary
of D(r), then the set of points B such that the square with diagonal
AB is included in D(r) is a lense-shaped region of area (pi-2)r^2 (as
a proportion of the disc area, this is twice A258146).  Therefore, the
number S of grid-squares included in D(R) can be estimated as follows:
since the set of squares with at least two vertices equidistant from
the origin is negligible, we can assume that evey square has a unique
vertex furthest from the origin, say at distance r, which corresponds
to the A above.  Then, the opposite vertex B is in the region computed
above, and the L^1 distance between A and B is even, so we have to
divide that area by 2.  There are approximately 2*pi*r grid points at
distance approximately r from the origin, so at first order, S \simeq
int_0^R pi r (pi-2)r^2 dr = pi(pi-2)/4 R^4.  Since the disc D(R)
contains approximately pi R^2 points, one obtains S \simeq (1-2/pi)/4
n^2.  Therefore, a(n) >~ (1-2/pi)/4 n^2.
That second proof actually gives liminf a(n)/n^2 >= (1-2/pi)/4.
______________________________________
EXTENSIONS
Revised following a rich discussion on the seqfan mailing list, with
contributions by the persons cited in the text, Allan Wechsler, Alex
Meiburg, and Benoît Jubin, Oct 5 2021.

________________________________________________________________________________
LINKS/REFERENCES
Elekes, Erdos, Similar configurations and pseudo grids
Matousek, Lectures on Discrete Geometry
Bernardo M. Abrego, Silvia Fernandez-Merchant, David B. Roberts, On
the maximum number of isosceles right triangles in a finite point set,
https://arxiv.org/abs/1102.5347
Bernardo M. Abrego, Silvia Fernandez-Merchant, Daniel J. Katz, Levon
Kolesnikov, On The Number of Similar Instances of a Pattern in a
Finite Set, https://arxiv.org/abs/1501.00076



More information about the SeqFan mailing list