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