|
| |
|
|
A051602
|
|
a(n) is the maximal number of squares that can be formed from n points in the plane.
|
|
7
|
|
|
|
0, 0, 0, 0, 1, 1, 2, 3, 4, 6, 7, 8, 11, 13, 15, 17, 20, 22
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,7
|
|
|
COMMENTS
|
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.
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
|
|
|
REFERENCES
|
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.
|
|
|
LINKS
|
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.]
|
|
|
FORMULA
|
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
|
|
|
EXAMPLE
|
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.
|
|
|
CROSSREFS
|
A348768 gives the number of inequivalent solutions.
|
|
|
KEYWORD
|
nonn,hard,more,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
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
|
|
|
STATUS
|
approved
|
| |
|
|
