5
$\begingroup$

My previous puzzle asked for the maximum number of 4-point circles attainable from a configuration of $n=10$ points drawn on a plane. I am now interested in generalizations of this puzzle to arbitrary $n$.

I wrote a hill-climbing program that searches for configurations with integer coordinates. Here are the best solutions it has found so far:

$n=8$, 12 circles: (2,16) (10,20) (7,26) (12,6) (7,16) (12,11) (22,11) (16,14) enter image description here

$n=9$, 14 circles: (9,17) (8,18) (5,17) (6,16) (7,19) (7,15) (6,18) (7,17) (8,16) enter image description here

$n=11$, 30 circles: (5,27) (41,29) (29,37) (44,40) (35,33) (19,35) (35,7) (23,28) (35,37) (30,32) (17,19) enter image description here

$n=12$, 43 circles: (27,7) (33,5) (37,17) (27,47) (21,5) (32,7) (12,17) (27,22) (42,17) (27,2) (17,17) (22,7) enter image description here

Here are the questions I want answered:

  1. Can you improve any of these solutions? You can use either integer or non-integer coordinates.
  2. Can we construct any upper/lower bounds on the maximum number of circles possible for an arbitrary $n$?
  3. The solutions for $n$=8, 10 and 12 use two concentric polygons. Can we conjecture that for even $n \geq 8$ the best solution will use two concentric $(n/2)$-polygons?
  4. For $n=13$ my best solution uses 43 circles, which is exactly like the $n=12$ case. Surely that extra point must be useful for a few more circles?
$\endgroup$
  • $\begingroup$ The sequence for this problem has been finally published. Even Neil Sloane liked it! oeis.org/A337747 $\endgroup$ – Dmitry Kamenetsky Oct 5 '20 at 6:12
3
$\begingroup$

A simple upper bound:

Since three points in the plane determine a circle any two distinct circles cannot have a triplet in common. We thus get an upper bound by counting all triplets and dividing by the number of triplets in a quadruplet $\left\lfloor\frac{\begin{pmatrix} n \\ 3 \end{pmatrix}}{\begin{pmatrix} 4 \\ 3 \end{pmatrix}}\right\rfloor=\left\lfloor\frac{\begin{pmatrix} n \\ 3 \end{pmatrix}}{4}\right\rfloor=\left\lfloor\frac{n(n-1)(n-2)}{24}\right\rfloor$

This evaluates to $n=7 \rightarrow 8;n=8 \rightarrow 14;n=9 \rightarrow 21;n=11 \rightarrow 41;n=12 \rightarrow 55$

A simple lower bound:

Construction: n even: 2 concentric parallel regular n/2-gons. This creates lots of trapezia with two points in either n/2-gon each permitting a circle. For n odd we can add the center point and use the same construction for n-1. IF (n-1)/2 is odd we can place the parallel sides of the (n-1)/2-gons opposite to each other and adjust the sizes of the two (n-1)/2-gons to create (n-1)/2 more circles all passing through the center, 2 points of the smaller (n-1)/2-gon and one point of the larger one. We can make a similar construction for (n-1)/2 even by rotating one (n-1)/2-gon so its corners align with the centers of the sides of the other. Also, note that if four points happen to be collinear we can still count them because we can use inversion in a circle centered at a point in general position to transform all such straight lines into proper circles.

Counting circles yields $2 + \frac {(n-1)[(n-1)(n-5)+16]} {32}$ for $n\equiv 1 \mod 4;n\ge9\ $,$\ 2 + \frac {(n-1)[(n-3)^2+16]} {32}$ for $n\equiv 3 \mod 4;n\ge11\ $,$\ 2 + \frac {n[(n-2)^2+4]} {32}$ for $n\equiv 0 \mod 4;n\ge8$ and $2 + \frac {n(n-2)^2} {32}$ for $n\equiv 2 \mod 4;n\ge10$

This evaluates to $n=8 \rightarrow 12;n=9 \rightarrow 14;n=11 \rightarrow 27;n=12 \rightarrow 41$

The lower bound constuction for $n=13$ beats OP by a single cirlce:

enter image description here The full configuration (bottom right panel) is obtained as 3 rotated overlays of the two templates (top right and bottom left panels, 6 circles each) plus the circumcircles of the two hexagons and six circles through the center (top left panel) for a total of 44.

Lower bound at $n=14$:

enter image description here The full configuration (right panel) is obtained as 7 rotated overlays of the template (left panel, 9 circles each) plus the circumcircles of the two heptagons for a total of 65.

$\endgroup$
  • $\begingroup$ This is excellent work Paul! Are you sure your lower bound is correct. For $n=14$ it gives me 65, but I can only find 57 so far. $\endgroup$ – Dmitry Kamenetsky Sep 8 '20 at 6:29
  • $\begingroup$ @DmitryKamenetsky Not 100% sure I did the counting right in every single case but $N=14$ seems correct, see updated answer. $\endgroup$ – Paul Panzer Sep 8 '20 at 9:30
  • $\begingroup$ @PaulPanzer "2 concentric parallel regular n/2-gons": this does not work for multiples of 4. (unless you count 4 points on a row as a circle of infinite size). Some shifting as in the picture for 8 is needed, and it is not clear if this is possible for 12+. Or am I missing something? $\endgroup$ – Retudin Sep 8 '20 at 10:08
  • $\begingroup$ @Retudin That's what the "inversion in a circle centered at a point in general position" is for. It basically allows us to treat straight lines as circles. $\endgroup$ – Paul Panzer Sep 8 '20 at 10:27
  • $\begingroup$ Ah yes your n=14 is correct. My program struggles to place heptagons on integer coordinates. $\endgroup$ – Dmitry Kamenetsky Sep 9 '20 at 22:17
1
$\begingroup$

I rewrote my solver so it is smarter and can handle non-integer coordinates. I have managed to improve $n=12$:

I can get 45 circles with (1.551724138, 2.379310345) (3, 3) (-1, -1) (0, 1) (0.729729730, 1.378378378) (1.153846154, 1.769230769) (0.931034483, 2.172413793) (0.333333333, 1.666666666) (2.2, 1.4) (0.529411765, 0.882352941) (1.153846154, 0.230769231) (1.615384615, 1.923076923). I am not sure if this solution is possible with integer coordinates.

enter image description here

I also improved $n=13$:

I can get 47 circles. Surprisingly there is no obvious symmetry in this solution: (1.153846154,0.769230769) (3,4) (2.6,3.2) (2,1) (4.2,1.6) (1.551724138,1.379310345) (1,0) (3,2) (1,2) (3,1) (1.975609756,0.780487805) (2.846153846,1.230769231) (0.529411765,1.882352941)

enter image description here

I made a small improvement to $n=15$:

I can get 73 circles: (1.411764706, 1.352941176) (0.6, 2.2) (2.04, 0.72) (2.12, 0.84) (3.6, 0.2) (5, 1) (1.846153846, 0.769230769) (0.705882353, 1.823529412) (1.294117647, 1.176470588) (3.2, -0.4) (2, 1) (3, -2) (0.588235294, 1.647058824) (1.216216216, 1.297297297) (0.2, 1.6)

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Nice work! Interestingly, the cross ratios of any four of these points lying on a circle are still rational with small denominator. For your 13 point example (count ⨉ cross ratio): 4 ⨉ 1/13;13 ⨉ 1/4;10 ⨉ 5/13;3 ⨉ 4/13;4 ⨉ 3/16;1 ⨉ 4/9;1 ⨉ 5/32;1 ⨉ 1/9;3 ⨉ 3/8;2 ⨉ 1/40;2 ⨉ 1/16;2 ⨉ 1/25;2 ⨉ 2/5;2 ⨉ 1/3;1 ⨉ 1/2;2 ⨉ 1/5;2 ⨉ 1/6; The counts add to 55 because there are two circles with 5 points on them. This may vaguely explain why integers worked so well in the first place. For A,B,C,D to lie on a cirlce the cross ratios need to sum to one: (A,B;C,D) + (A,C:B,D) = 1. Seems easier for rationals. $\endgroup$ – Paul Panzer Sep 16 '20 at 3:29
  • 1
    $\begingroup$ I wonder if one could directly base the search on cross ratios instead of coordinates? I also wonder whether Pythagorean triples have a role to play here since they help keeping distances rational which presumably makes it easier to get rational cross ratios. $\endgroup$ – Paul Panzer Sep 16 '20 at 3:35
  • $\begingroup$ Also of note: Your new 12 point solution has superior structure compared to the two hexagon construction, because the two hexagons waste quite a few potential cirlces of four by collapsing them onto circles of six. Your solution only has circles of four. $\endgroup$ – Paul Panzer Sep 16 '20 at 3:44
  • $\begingroup$ Interesting idea to search over cross ratios. I need to think about it. If I give you a set of cross ratios, are you able to reconstruct a solution? $\endgroup$ – Dmitry Kamenetsky Sep 16 '20 at 9:28
  • $\begingroup$ Not sure, for $n$ large enough just by counting degrees of freedom it should be possible in principle. I checked a tiny bit deeper: the cross ratios are all rational not because all distances are, but because lengths like $\sqrt 5$ are combined in such a way that the result is rational. $\endgroup$ – Paul Panzer Sep 16 '20 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.