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

%I #161 Jan 13 2023 19:09:58

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

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

%C _Sascha Kurz_ has proved that one can assume that the points belong to the square grid Z X Z.

%C 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.

%C 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.

%C 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].

%C 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.

%C A more detailed account will be found in the report by Sascha Kurz et al. which is nearing completion.

%C [Comments revised to this point by _N. J. A. Sloane_, Nov 02 2021]

%C 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.

%C Asymptotic behavior:

%C One has a(n), b(n) = Theta(n^2):

%C 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.

%C 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.

%C We actually have better lower and upper bounds:

%C 0.09... = (1-2/Pi)/4 <= liminf a(n)/n^2 <= limsup b(n)/n^2 <= 1/6 = 0.16...

%C 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.

%C 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.

%C 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

%C 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

%D Elekes, Erdos, Similar configurations and pseudo grids, Coll. Math. Soc. Janos Bolyai 63 Intuitive Geometry, Budapest (Hungary), 1994.

%D J. Matousek, Lectures on Discrete Geometry, GTM 212, Springer, 2002.

%H Bernardo M. Abrego, Silvia Fernandez-Merchant, and David B. Roberts, <a href="http://arxiv.org/abs/1102.5347">On the maximum number of isosceles right triangles in a finite point set</a>, arXiv:1102.5347 [math.CO], 2011. Also in Involve, 4:1 (2011), 27-42.

%H Bernardo M. Abrego, Silvia Fernandez-Merchant, Daniel J. Katz and Levon Kolesnikov, <a href="http://arxiv.org/abs/1501.00076">On The Number of Similar Instances of a Pattern in a Finite Set</a>, arXiv:1501.00076 [math.CO], 2015.

%H Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a051/A051602.java">Java program for a(n)</a> (github) [The program is not guaranteed to be correct because it searches only grid points in [1, ceil(sqrt(n))]^2.]

%H Sean A. Irvine, <a href="/A051602/a051602.pdf">Illustrations for n = 4 through 16</a>, 2021.

%H Sascha Kurz, <a href="http://arxiv.org/abs/2112.12716">Plane point sets with many squares or isosceles right triangles</a>, arXiv:2112.12716 [math.CO], 2021.

%H Sascha Kurz, Peter Munn, and Hugo van der Sanden, <a href="/A051602/a051602_2.pdf">Plane point sets with many squares</a>, Preprint, Jan 13 2022

%H Peter Munn, <a href="/A051602/a051602_2.txt">Asymptotics for circular regions</a>, SeqFan post, Oct 04 2021.

%H N. J. A. Sloane, <a href="/A051602/a051602_1.txt">Sascha Kurz's table of the best results presently known for 4 <= n <= 100</a>, taken from the Nov 03 2021 version of Sascha Kurz et al., Plane point sets with many squares.

%H N. J. A. Sloane, <a href="https://arxiv.org/abs/2301.03149">"A Handbook of Integer Sequences" Fifty Years Later</a>, arXiv:2301.03149 [math.NT], 2023, p. 21.

%H Hugo van der Sanden and Benoit Jubin, <a href="/A051602/a051602.txt">At most three squares can be formed from seven points in the plane</a>

%F 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

%e Lower bounds:

%e 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).

%e For instance, the first representation encodes the sequence of configurations

%e X

%e XX ; XXX ; XXX ; XXX ; etc.

%e XX ; XX ; XXX ; XXX

%e ----------

%e n = 4--11

%e 435

%e 0016

%e 0027

%e ----------

%e n = 12--19

%e ..7

%e 4003

%e 00005

%e 00006

%e 1002

%e ----------

%e n = 20--36

%e .GA78B

%e .93100C

%e E500000

%e F400000

%e .600000

%e .D2000

%e ----------

%e n = 37--47

%e .60007

%e 5000008

%e 0000000

%e 00000009

%e 0000000A

%e 4000003

%e .20001

%e ----------

%e n = 48--50

%e ..0000

%e .000000

%e 20000000

%e 00000000

%e 00000000

%e .0000000

%e .000000

%e ...001

%e ----------

%e In particular, a(25)>=51, a(36)>=109, a(37)>=117, a(48)>=198, a(49)>=207, a(50)>=216.

%e ----------

%e Another optimal configuration for a(8) = 4 due to Sascha Kurz:

%e .XX

%e XXXX

%e .XX

%e ----------

%e Configurations and values for larger values of n can be found in the links below.

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

%Y A348768 gives the number of inequivalent solutions.

%K nonn,hard,more,nice

%O 0,7

%A _Erich Friedman_

%E a(13)-a(16) from _Sean A. Irvine_, Sep 23 2021

%E a(13)-a(16) confirmed and a(17) from _Sascha Kurz_, Oct 30 2021

%E 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

%E Partially revised by _N. J. A. Sloane_, Nov 02 2021