7

Let $n\geq 2$. What is the minimum $k$ so that if we take $k$ lattice points on the plane with each coordinate between $1$ and $n$ inclusive, then some four points lie on a circle?

If we find a $k$ so that some four points must be vertices of a rectangle, then they must also lie on a circle. If we choose $2n-1$ points on $(1,1),(1,2),\ldots,(1,n),(2,1),(3,1),\dots,(n,1)$, then no four points are vertices of a rectangle, but in fact the four points $(1,2),(1,3),(2,1),(3,1)$ still lie on a circle.

user336268
  • 2,339

2 Answers2

0

To answer the question (originally present in the OP):

if we choose $2n$ points, are we guaranteed to get a rectangle?

You can choose $2n$ points on an $n \times n$ grid such that no four form a rectangle (for $n > 2$). Just take two adjacent points in each column, staggered to form a "staircase".

E.g., for $n = 3$, enter image description here, and for $n=4$, enter image description here

However, even though there are no rectangles among these $2n$ points, there are still four that lie on a circle:

enter image description here enter image description here

Your proposed example with $2n-1$ points also has four points that lie on a circle, for any $n > 2$:

enter image description here

There are, however, different examples with $2n-1$ points with no four points on a circle, for $n = 3, 4, 5, 6, 7$:

Points at (1,1), (1,2), (1,3), (2,1), (3,2) Points at (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 4), (4, 1) Points at(1, 1), (1, 2), (1, 3), (2, 2), (3, 3), (4, 3), (4, 5), (5, 3), (5, 4) Points at (1, 1), (1, 2), (1, 3), (1, 4), (1, 6), (2, 3), (3, 1), (4, 4), (5, 5), (6, 5), (6, 6) Points at (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 7), (2, 3), (3, 5), (4, 6), (5, 2), (6, 1), (7, 6), (7, 7)

Any set of $2n$ points do have at least one circle through four of the points, for $n = 3,4,5,6$.

However, for $n = 7$, 14 points do not suffice. There is a set of 14 points with no circle through any four points:

Points at (1,1), (1,2), (1,4), (1,5), (1,7), (2,2), (3,2), (4,6), (5,6), (5,7), (6,3), (6,7), (7,1), (7,3)

The closely related question "How many points on an $n \times n$ grid force some four points to lie on a generalized circle?" (meaning, a circle or a straight line) was posed by Erdős, and is known as the no-four-on-circle problem. It remains open. This is Problem F3 in Guy's Unsolved Problems in Number Theory.

The 1995 paper "The no-four-on-circle problem" by T. Thiele (DOI 10.1016/0097-3165(95)90007-1) establishes a lower bound of $(\frac 1 4 - \epsilon)n$ for the maximum number of points with no four on a circle.

Nick Matteo
  • 9,006
  • You're right. I've edited accordingly. – user336268 May 12 '17 at 01:48
  • -1. None of the diagrams show which lattice points were chosen. The mathematics might be OK but the diagrams are inadequate. – Rosie F Feb 03 '23 at 14:12
  • @RosieF: But they do show the chosen points. Are you perhaps using a browser extension which alters the images? – Nick Matteo Feb 03 '23 at 23:56
  • @RosieF: Hey, I noticed that I also listed the chosen lattice points as alt text. – Nick Matteo Feb 03 '23 at 23:58
  • @NickMatteo I am visually impaired, so, to reduce glare from the screen, I use dark-mode extensions. This makes backgrounds black by default. Where an image contains something which is meant to be seen against a background, generally it's a bad idea to use transparent for that background --- you never know how a user's browser will render that background. // Isn't alt text supposed to appear in a tool-tip when you hover the cursor over the image. I see no tool-tips for these images. – Rosie F Feb 04 '23 at 07:18
0

Why settle for four? Any circle passing through at least three rational points passes through infinitely many of them. So by magnification you can pass a circle through an arbitrarily large number of integer points.

Oscar Lanzi
  • 39,403
  • How hard is it to prove that three rational points $\implies$ infinitely many? – A. Thomas Yerger May 12 '17 at 02:30
  • @alferd: first off, if there are three rational points the center is another rational point. With the rational pount center and one rational point on the circle rotate the point on circle by $arc \cos (3/5) $ around the center. Repeat this rotation which is not a rational multiple of $\pi $. – Oscar Lanzi May 12 '17 at 02:42
  • 1
    We're not "settling" for four; four is the smallest number of points that don't trivially lie on a circle. This answer is exactly like responding to the No-three-in-line problem by saying "Why settle for three? Any line through two integer points goes through infinitely many, so you can pass a line through arbitrarily many integer points." – Nick Matteo May 19 '17 at 20:45