Smallest circle that intersects N number of points on the coordinate plane?

I don’t see how the upper bound is radius of 20. How does that circle have “20 intersection points?”

3:4:5 works because there are two ways to get to the radius: 0^2+5^2 and 3^2+4^2. So technically there are four answers in each quadrant. Four of them are shared, however, leaving 12 unique points.

I’m thinking the radius must be expressible as the sum of 2 pairs of squares, not including 0. (or 3 including 0). a^2+b^2= c^2+d^2 = r^2.

@6rant6 Actually, it should be a radius 25 circle that has 20 intersection points.

I still don’t see what you are saying. 20 intersection points with what?

It has 20 points that are grid points on the coordinate plane. Perhaps intersection is not the best word to use? Maybe integer points?

For radius=20
They are
20,0
-20,0
0,20
0,-20
7,24
7,-24
-7,24
-7,-24
24,7
-24,7
24,-7
-24,-7
15,20
15,-20
-15,20
-15,-20
20,15
20,-15
-20,15
-20,-15

Lattice points is the phrase I am looking for.

I searched the Web. You may find this of interest, though it does not solve your problem. It does seem to indicate that the problem may be difficult.
Are you familiar with Pick’s Theorem?

You’ve conflated radius 20 and 25. You should have put 0, 25 and it’s reflections, not 0,20.

It works because 25^2 = 0^2+25^2 = 7^2+24^2=15^2+20^2.

a circle of Radius of Sqrt(325) has 12 integer-integer points:
15,10
17,6
18,1
and their reflections. Note that their are no points on the axes.

It appears that all 12-point circles have a radius that is a multiple of 5.

other radii of interest.

1105 ( 16 ; 24,23 31,12 32,9 33,4)
4225 (20 ; 52,39 56,33 60,25 63,16 [65^2])
5525 ( 24 ; 55,50 62,41 70,25 71,22 73,14 74,7)
27625 ( 32 ; 120,115 132,101 141,88 144,83 155,60 160,45 164,27 165,20)
105625 (32 ; 253,204 260,195 280,165 300,125 312,91 315,80 323,36, [325^2])
71825 (36 ; 191,188 208,169 215,160 236,127 247,104 257,76 260,65 265,40 268,1)
138125 ( 40 ; 275,250 301,218 310,205 317,194 334,163 350,125 355,110 365,70 370,35 371,22)
160225(48 ; 300,265 311,252 329,228 337,216 356,183 360,175 375,140 384,113 392,81 393,76 399,32 400,15)

I’m doing brute force calculations, which doesn’t help obtaining a generalized solution. Nor does my method assure I am getting the smallest circles, but I think they are.

One more, and my computer has to go back to work…

The first column is the square of the radius, in case that wasn’t obvious. If the first number is a perfect square, then the radius will be an integer.

*** Square:
1221025 ; 56 integer points ; 817,744 855,700 884,663 943,576 952,561 975,520 1001,468 1020,425 1071,272 1073,264 1092,169 1100,105 1104,47 [1105^2] *** note: 1105 was also on this list!!! I wonder if a circle or radius 1221025 would be here.

*** Square:
3553225 ; 56 ; 1365,1300 1508,1131 1596,1003 1624,957 1643,924 1725,760 1740,725 1760,675 1813,516 1827,464 1836,427 1859,312 1872,221 [1885^2]

2442050 ; 56 ; 1105,1105 1151,1057 1205,995 1261,923 1337,809 1343,799 1445,595 1469,533 1495,455 1513,391 1519,367 1547,221 1555,155 1561,73

1795625 ; 60 ; 955,940 1040,845 1069,808 1075,800 1157,676 1180,635 1216,563 1235,520 1256,467 1285,380 1300,325 1325,200 1328,179 1339,52 1340,5

801125 ; 64 ; 655,610 703,554 710,545 722,529 766,463 769,458 785,430 815,370 830,335 862,241 865,230 874,193 881,158 886,127 890,95 895,10

2082925 ; 72 ; 1027,1014 1107,926 1133,894 1170,845 1230,755 1245,730 1261,702 1322,579 1331,558 1338,541 1342,531 1378,429 1395,370 1405,330 1430,195 1434,163 1437,134 1443,26

4005625 ; 80 ; 1483,1344 1500,1325 1555,1260 1604,1197 1645,1140 1685,1080 1692,1069 1780,915 1800,875 1811,852 1875,700 1899,632 1920,565 1941,488 1960,405 1965,380 1973,336 1995,160 1996,147 2000,75

__oops. The number of points should be eight times the number of pairs of numbers that can be squared and summed to reach the total plus 4 iff the number is a perfect square__

So 1105 would be 4*8 = 32 points and 105625 would be 7*8 + 4 = 60 points.

Seems to me that any Pythagorean triple will generate a circle, centered at the origin, intersecting 12 lattice points (two in the interior of each quadrant plus the axis intercepts). Have we identified a circle intersecting 16 points?

The smallest radius of a circle centered at the origin that intersects 16 integer lattice points is √65. The points are obtained by reflecting the points {1,8} and {4,7} through the two axes and the diagonal. Use the Mathematica functions SquaresR and PowersRepresentations to find these numbers (both can be used in WolframAlpha). The underlying mathematics is presented here.

I did some more searching for this. There is a rather compact formula for determining how many ways a number can be expressed as the sum of two squares. It is given by the formula r2(n) = 4(d1(n) – d3(n)), where d1(n) is the number of divisors of n that equal 1 mod 4 and d3(n) is the number of divisors of n that equal 3 mod 4. Of course computing d1(n) and d3(n) requires finding the prime factorization, which is no easy matter.

Note that the formula includes both positive and negative numbers and distinguishes (x,y) from (y,x), which is exactly what you would want for the problem posed by OP. For example, 325, given above by @6rant6, can be factored as 5^2 * 13. 5 and 13 both equal 1 mod 4. There are therefore 3*2=6 divisors of 325, all equal to 1 mod 4. That gives 24 representations of 325 as the sum of two squares, in agreement with what @6rant6 found, after he made his correction.

I am not sure that I can follow the proof of the formula. For those who want to give it a go, you can find it here on page 12.

One further note. I plugged (x^2 + y^2) = 325 into WolframAlpha and it did what I hoped it would do, which was to find the 24 solutions. That site can get a bit scary in what it is capable of doing.

@ratboy Enjoyable math link, even if I don’t understand it. My mathematical background puts it right at the boundary between what I used to know (some Diophantine analysis) and what I never knew (elliptic integrals).

r^2 has to be an integer, but how often is r itself an integer? This would yield 4 additional points at (+/- r,0) and (0, +/- r), i.e., the circle intersects the axes at lattice points. I note that 65 and 325, specific values of r^2 given above, are both of form n^2+1. Is that the rule?

My apologies to @ratboy for not going through the complete link.

To find the smallest radii for circles intersecting a fixed number of points, it seems that we should to look at numbers that are the product of prime numbers congruent to 1 mod 4. Even if the primes are all known, it takes some fiddling to determine which ones to use. There is a tradeoff between size of the largest prime and powers to which the smaller ones are raised. It reminds me of the problem of determining highly composite numbers, which are numbers that have more divisors than any smaller number (2,4 ,6 and 12 are the first ones).

Is there proof that the smallest circle is centered on 0?