A063542 -id:A063542 - cp's OEIS frontend

A051602 a(n) is the maximal number of squares that can be formed from n points in the plane.

0, 0, 0, 0, 1, 1, 2, 3, 4, 6, 7, 8, 11, 13, 15, 17, 20, 22

Offset: 0

Sascha Kurz has proved that one can assume that the points belong to the square grid Z X Z.
So we obtain the same values if we replace the definition by: a(n) is the maximal number of squares that can be formed from n points chosen from the infinite square grid.
In other words, take the infinite square grid. Pick a set S of n grid points, and let c(S) be the number of subsets of four points of S that form a square of any (nonzero) size. Then a(n) = maximum of c(S) over all choices of S.
The general problem of estimating the maximal number of similar figures within point-configurations was studied in [Elekes--Erdos]. 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].
The following remarks are out of date, and will be revised soon to reflect progress made in October 2021 by a number of members of the Sequence Fans Mailing List.
A more detailed account will be found in the report by Sascha Kurz et al. which is nearing completion.
[Comments revised to this point by N. J. A. Sloane, Nov 02 2021]
Values for n <= 9 [now 16] 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 gcd of side lengths equal to 1) have a diameter at most f(n) with f of moderate growth would permit exact computation of values from exhaustive searches.
Asymptotic behavior:
One has a(n), b(n) = Theta(n^2):
Upper bound: Since two vertices determine squares, one has b(n) = O(n^2). More explicitly: a pair of points uniquely determines the square that has it as diagonal, and a square has two diagonals, so b(n) <= n(n-1)/4 ~ n^2/4.
Lower bound: 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 nondecreasing, one has a(n) >= (n-1)(n-2)/12 ~ n^2/12.
We actually have better lower and upper bounds:
0.09... = (1-2/Pi)/4 <= liminf a(n)/n^2 <= limsup b(n)/n^2 <= 1/6 = 0.16...
The upper bound is given in [AFR] (which counts isosceles right triangles, so their value has to be divided by four, the number of isosceles right triangles formed on a square). This gives b(n) <= (2/3*(n - 1)^2 - 5/3)/4.
Lower bound (due to Peter Munn, see SeqFan post in the links): 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 lens-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 every 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 (aka rectilinear, or Manhattan) distance between A and B is even (being opposite vertices, they are two sides apart), so we have to divide that area by 2. There are approximately 2*Pi*r grid points at a distance approximately r from the origin, so at first order, S ~= Integral_{r=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 ~= (1-2/Pi)/4 n^2.
Conjecture: the asymptotic density of the numbers n such that there is no maximal arrangement formed by all the grid points within a suitably chosen circle, is 0. - Peter Munn, Sep 30 2021
For the known values of a(n) (n <= 17), there is a maximal arrangement formed using circles as specified by the conjecture above. For n <= 100 no arrangement has yet been found to contain more squares than the best attained using a circle as specified by A348469. - Peter Munn, Nov 12 2021

			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.  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
0016
0027
----------
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(25)>=51, a(36)>=109, a(37)>=117, a(48)>=198, a(49)>=207, a(50)>=216.
----------
Another optimal configuration for a(8) = 4 due to Sascha Kurz:
.XX
XXXX
.XX
----------
Configurations and values for larger values of n can be found in the links below.

Elekes, Erdos, Similar configurations and pseudo grids, Coll. Math. Soc. Janos Bolyai 63 Intuitive Geometry, Budapest (Hungary), 1994.
J. Matousek, Lectures on Discrete Geometry, GTM 212, Springer, 2002.

Bernardo M. Abrego, Silvia Fernandez-Merchant, and David B. Roberts, On the maximum number of isosceles right triangles in a finite point set, arXiv:1102.5347 [math.CO], 2011. Also in Involve, 4:1 (2011), 27-42.
Bernardo M. Abrego, Silvia Fernandez-Merchant, Daniel J. Katz and Levon Kolesnikov, On The Number of Similar Instances of a Pattern in a Finite Set, arXiv:1501.00076 [math.CO], 2015.
Sean A. Irvine, Java program for a(n) (github) [The program is not guaranteed to be correct because it searches only grid points in [1, ceil(sqrt(n))]^2.]
Sean A. Irvine, Illustrations for n = 4 through 16, 2021.
Sascha Kurz, Plane point sets with many squares or isosceles right triangles, arXiv:2112.12716 [math.CO], 2021.
Sascha Kurz, Peter Munn, and Hugo van der Sanden, Plane point sets with many squares, Preprint, Jan 13 2022
Peter Munn, Asymptotics for circular regions, SeqFan post, Oct 04 2021.
N. J. A. Sloane, Sascha Kurz's table of the best results presently known for 4 <= n <= 100, taken from the Nov 03 2021 version of Sascha Kurz et al., Plane point sets with many squares.
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 21.
Hugo van der Sanden and Benoit Jubin, At most three squares can be formed from seven points in the plane

Cf. A002415, A063542, A186705, A186926, A258146, A348469.

A348768 gives the number of inequivalent solutions.

If n = m^2, then a(n) >= m^2*(m^2-1)/12 (see A002415). If n = m^2-1, then a(n) >= (m-1)*(m-2)*(m^2+3*m+6)/12. - N. J. A. Sloane, Sep 28 2021

a(13)-a(16) from Sean A. Irvine, Sep 23 2021
a(13)-a(16) confirmed and a(17) from Sascha Kurz, Oct 30 2021
Revised following a rich discussion on the seqfan mailing list, with contributions by the persons cited in the text, Allan Wechsler, Alex Meiburg, and Benoit Jubin. - Benoit Jubin, Oct 07 2021
Partially revised by N. J. A. Sloane, Nov 02 2021

A276096 a(n) is the least number of empty convex pentagons ("convex 5-holes") spanned by a set of n points in the Euclidean plane in general position (i.e., no three points on a line).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 3, 6, 9, 11

Offset: 1

Manfred Scheucher, Aug 18 2016

The value a(10) = 1 was determined by Harborth, who also constructed a set of 9 points without convex 5-holes. The values a(11) = 2 and a(13) = 3 were determined by Dehnhardt. Aichholzer found point sets showing that a(14) <= 6 and a(15) <= 9, and the exact values a(13) = 3, a(14) = 6, and a(15) = 9 were determined in the Bachelor's thesis of Scheucher, supervised by Aichholzer and Hackl.

The value a(16) = 11 was determined using a ILP/SAT solver. For more information check out the link below with title "On 5-Holes". - Manfred Scheucher, Aug 18 2018

K. Dehnhardt, Leere konvexe Vielecke in ebenen Punktmengen, PhD thesis, TU Braunschweig, Germany, 1987, in German.

O. Aichholzer, M. Balko, T. Hackl, J. Kynčl, I. Parada, M. Scheucher, P. Valtr, and B. Vogtenhuber, A superlinear lower bound on the number of 5-holes, arXiv:1703.05253 [math.CO], 2017.
O. Aichholzer, R. Fabila-Monroy, T. Hackl, C. Huemer, A. Pilz, and B. Vogtenhuber, Lower bounds for the number of small convex k-holes, Computational Geometry: Theory and Applications, 47(5):605-613, 2014.
EuroGIGA - CRP ComPoSe, A set of 13 points with 3 convex 5-holes
EuroGIGA - CRP ComPoSe, A set of 14 points with 6 convex 5-holes
EuroGIGA - CRP ComPoSe, A set of 15 points with 9 convex 5-holes
EuroGIGA - CRP ComPoSe, A set of 16 points with 11 convex 5-holes
H. Harborth, Konvexe Fünfecke in ebenen Punktmengen, Elemente der Mathematik, 33:116-118, 1978, in German.
M. Scheucher, Counting Convex 5-Holes, Bachelor's thesis, Graz University of Technology, Austria, 2013, in German.
M. Scheucher, On 5-Holes.

Cf. A063541 and A063542 for convex 3- and 4-holes, respectively.

Cf. A006247 and A063666 for equivalence classes (w.r.t. orientation triples) of point sets in the plane.

From Manfred Scheucher, Mar 22 2017: (Start)
a(n) = Omega(n log^(4/5)(n)) and a(n) = O(n^2).
Conjecture: a(n) = Theta(n^2). (End)

a(16) from Manfred Scheucher, Mar 22 2017

cp's OEIS Frontend

A051602 a(n) is the maximal number of squares that can be formed from n points in the plane.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A063541 Least number of empty triangles determined by n points in the plane.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A276096 a(n) is the least number of empty convex pentagons ("convex 5-holes") spanned by a set of n points in the Euclidean plane in general position (i.e., no three points on a line).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions