Rectangle with lattice points

Given a positive integer $n\geq 2$, consider all the lattice points with each coordinate between $1$ and $n$, inclusive. At least how many points must we choose to guarantee that some four points form a rectangle with sides parallel to the axes?

$2n-1$ points do not suffice, because we can select the points $$(1,1),(1,2),\dots,(1,n),(2,1),(3,1),\dots,(n,1),$$ then no rectangle is formed.

For $n=2$, the answer is obviously $4$.

For $n=3$, even $2n=6$ points do not suffice. We can choose $$(1,1),(1,2),(2,1),(2,3),(3,2),(3,3),$$ and again there is no rectangle. However, with $7$ points, some row is chosen completely, and since some other row must have at least two points, this forms a rectangle.

This is a very interesting question. That's not an exact answer, but rather an approximate solution that shows that there exist examples with about $n^{3/2}$ points.

First, let there be $c_i$ points chosen in the $i$-th column and $S$ points chosen in total, and let the subset of column $i$ that we've chosen be $C_i\subset\{1,2,\ldots,n\}$. Then a rectangle not existing amounts to there being no pairs $(i,j)$ such that there are two columns whose $i$-th and $j$-th entries are both among the chosen points, or equivalently that $|C_k\cap C_l|<2$ for all $k\neq l$.

This gives the bound $$ \sum_{i=1}^n {c_i\choose 2} \leq {n\choose 2}$$ and since ${c_i\choose 2}$ is convex, Jensen's inequality gives that $$S(S/n-1) \leq n(n-1)$$ with the inequality being sharpest when the $c_i$ are as equal as they can be. From this we see that approximately $S^2/n\leq n^2$, which says that we approximately have $S\leq n^{3/2}$.

Now here's a construction that achieves $S=\Theta(n^{3/2})$ (Everything I say from now on should be taken in some approximate sense). Assume $n=p^2$ for some prime $p$, and consider the lines $ax+b$ as $a,b$ range over $\mathbb{F}_p$. Each such line determines a subset of $\mathbb{F}_p^2$ called its graph, consisting of the points $(x,ax+b)$ as $x$ ranges over $\mathbb{F}_p^2$. Each two lines intersect at at most one point. Thus the graphs of all these $p^2$ lines give us $p^2$ subsets of $\mathbb{F}_p^2$, each two of which intersect at at most one point.

We can then unroll these subsets to $p^2=n$ subsets of $\{1,2,\ldots,p^2\}=\{1,2,\ldots,n\}$, each of size $p=\sqrt{n}$, which tell us the sets $C_i$. This results in a set of chosen points where no two $C_i$-s intersect in more than 1 point.

Edit: to justify why I'm saying this gives $\Theta(n^{3/2})$, observe that even if $n$ is not the square of a prime number, there is some prime $p$ in $[\sqrt{n}/2,\sqrt{n}]$ by Bertrand's postulate, and we can use that (we'll just restrict ourselves to a $p^2\times p^2$ subgrid and we lose at most a factor of $4$ from $n$).

Further edit: Thinking about this some more, I find it unlikely that there's a nice closed-form answer for general $n$. A version of this problem appears as problem 208 in this book of All-Russian olympiads. There the same approach is employed, and the authors remark that beyond the clean cases with nice number-theoretic properties we don't know much.

Further further edit: It has come to my attention that this is an instance of a more general problem in extremal graph theory called the Zarankiewicz problem. It is essentially a version of Turan's problem where all the graphs are bipartite :)