Circle through four lattice points 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.
 A: 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$, ,
and for $n=4$, 
However, even though there are no rectangles among these $2n$ points, there are still four that lie on a circle:


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

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

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.
A: 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.
