How not to define density of a subset of $\mathbb{Z}^2$ The next exercise illustrates a bad definition of density of a subset of $\mathbb{Z}^2$ (it always ends up being either $0$ or $1$).

Let $S\subset \mathbb{Z}^2$. Define  $$d_k(S)=\max
 \limits_{\substack{A,B\subset \mathbb{Z}  \\ |A|=|B|=k}}\frac{|S\cap
 (A\times B)|}{|A||B|}.$$ Show that $\lim \limits_{k\to \infty} d_k(S)$
exists and is always either 0 or 1.


*

*This is the original version of the problem but I think it is more correctly to replace $\max$ with  $\sup$, i.e. $$d_k(S)=\sup
 \limits_{\substack{A,B\subset \mathbb{Z}  \\ |A|=|B|=k}}\frac{|S\cap
 (A\times B)|}{|A||B|}.$$


*I have no idea how to attack this problem but after some thoughts I was able to solve the problem in particular case, when $S\subset\mathbb{Z}^2$ is a bounded set. More precisely, if $S\subset [-N,N]^2$ for some $N\in \mathbb{N}$, then $d_k(S)=\dfrac{|S|}{k^2}$ for $k\geq 4N$. Therefore, $\lim \limits_{k\to \infty} d_k(S)=0$.
But I think the solution should be different since there are unbounded sets  with density zero also.
I'd be very grateful if someone can show the solution please. Thank you!
 A: The key result needed is following theorem by in Fox, Sudakov "Density theorems for biparite graphs and related Ramsey-type results" (slightly simplified):

Let $H$ be a biparite graph, $\varepsilon > 0$. Then for large enough $N$, if $G$ is a graph with $N$ vertices and at least $\varepsilon {N \choose 2}$ edges, then $H$ is a subgraph of $G$.

We want to prove that $\lim\limits_{k \to \infty} d_k$ exists and is equal to $0$ or $1$.
This is equivalent to proving that if $\neg (\lim \limits_{k \to \infty} d_k) = 0)$ then $\lim \limits_{k \to \infty} d_k) = 1$.
Assume the limit doesn't exist or isn't equal to $0$. This is equivalent $$\exists \varepsilon_0 > 0 \forall M \exists n > M \exists A, B: |A| = |B| = n \wedge |S \cap A\times B| > \varepsilon_0 n^2 \tag{1}$$
We will show that this implies $\forall k \exists A', B': |A'| = |B'| = k \wedge A'\times B' \subset S$ (and thus $d_k(S)$ is actually $1$ for any $k$, and $\lim \limits_{k \to \infty} d_k = 1$).
Take some $k > 0$. Let $H$ be $K_{k, k}$ and $\epsilon = \varepsilon_0 / 4$ in cited theorem.
Let $M$ in $(1)$ be $N$ from the theorem.
For integer $n$, let $n'$ and $n''$ be two distinct copies of $n$ (for example, $n' = \langle n, 0\rangle$ and $n'' = \langle n, 1\rangle$).
Let $G$ in theorem be graph with vertices $\{x' | x \in A\} \cup \{y''| y \in B\}$ and edges are $\{\{x', y''\} | x \in A, y \in B, (x,y) \in S\}$.
In other words, vertices are rows and columns, and there is an edge between two vertices if $S$ contains element on intersection of this row and column.
Then $G$ has $2M > N$ vertices and at least $4 \varepsilon M^2 > \varepsilon {2M \choose 2}$ edges, so it satisfies conditions of theorem, and so $H$ is it's subgraph. Thus, there are subsets $A' \subseteq A$ and $B' \subseteq B$ of size $k$ s.t. $A'\times B' \subset S$.
UPD: actually, what we need from the theorem, is that for any $\varepsilon$ and $k$, large enough biparite graph with edge density at least $\varepsilon$ contains a complete biparite subgraph $K_{k, k}$. It is corollary of Kővári–Sós–Turán theorem that actually even $O(n^{2 - 1/k})$ edges is enough.
A: Let's show that the limit exists. Firstly, we'll show our sequence is monotone. To do that, suppose
$$
A = \{a_i, 1 \leq i \leq n\} \qquad B = \{b_i, 1 \leq i \leq n\}
$$
Denote
$$
A_j = \{a_i, 1 \leq i \leq n, i \neq j \} \qquad B_k = \{b_i, 1 \leq i \leq n, i \neq k \}
$$.
Then
$$\frac{|S\cap (A\times B)|}{n^2} =  \frac{ \sum_{1 \leq j,k \leq n} |S\cap (A_j\times B_k)|}{n^2(n-1)^2} = \\
= \frac{\sum_{1 \leq j,k \leq n} \frac{ |S\cap (A_j\times B_k)|}{(n-1)^2 }}{n^2} \leq \frac{\sum_{1 \leq j,k \leq n} d_{n-1}(S)}{n^2} = d_{n-1}(S)
$$
where first equality hold because each pair $\{a_i, b_i\}$ is in exactly $(n-1)^2$ sets of the form $A_j \times B_k$.Thus, we have proven that
$d_n(S) \leq d_{n-1}(S)$. By bounded monotone sequence convergence, our limit exists.
