---------------------------- Original Message ---------------------------- Subject: [seqfan] Re: How many squares can you make from n points in the plane? From: "Peter Munn" Date: Mon, October 4, 2021 3:31 pm To: "Sequence Fanatics Discussion list" -------------------------------------------------------------------------- On Fri, October 1, 2021 11:27 pm, Alex Meiburg wrote: > I ran the computation for what happens if you take a circular region of > points in a grid. It's fairly straightforward in the asymptotic case, > because it all just comes down to computing (and integrating) areas, and > we > don't have to actually worry about the integrality of points; and a result > it becomes rotationally invariant. As I mentioned in my previous post, I think this is a good approach. I now give details of my similar method for disc-approximating configurations. I consider each qualifying square to be represented by a pair of its vertices: the vertex furthest from the centre of the disc and the opposite vertex. I ignore squares that have 2 or more vertices furthest from the centre, as such squares are 0% of the total asymptotically. I look to establish the proportion of pairs of grid points within the disc that represent a qualifying square. Pairs must satisfy 2 criteria: span an even rectilinear distance, and qualify "regionally": with one in an appropriate region of the disc relative to the other. For k >= 0, consider pairs whose larger distance from the disc centre is in the interval (k^2, (k+1)^2]. I assume the proportion of regionally qualifying pairs converges as k -> oo to the proportion of the area of a disc that contains, for a given (vertex) point on the circumference, the opposite vertex of a square that is contained within the disc. For a disc radius 1 centre (0, 0) with circumferential vertex (-1, 0), the other vertex (x, y) must satisfy abs(y) <= sqrt(2-x^2) - 1 (it lies between 2 arcs of radius sqrt(2), centred (0, -1) and (0, 1)). As a proportion of the disc, the relevant area is 1 - 2/pi. So, asymptotically, (1 - 2/pi) of grid point pairs qualify regionally. Half of these will have even rectilinear distance, giving (0.5 - 1/pi) = A258146. Multiplying by total pairs of grid points gives n(n-1)/2 * A258146 ~= n^2/11.008. For square regions it's n^2/12. This implies that disc-approximating configurations perform better, asymptotically, than squares of points. Best regards, Peter -- Seqfan Mailing list - http://list.seqfan.eu/