Asymptotic growth of the clique number for the "Prime-Visibility Graph" on an $N \times N$ grid

Background & Definition

In lattice geometry, two points $A, B \in \mathbb{Z}^2$ are said to be visible to one another if the open line segment between them contains no other lattice points. Equivalently, if $A = (x_A, y_A)$ and $B = (x_B, y_B)$, they are visible if $\gcd(|x_A - x_B|, |y_A - y_B|) = 1$.

I am interested in a concept which I'll call $\mathbb{P}$-visibility (Prime-Visibility). Let $\mathbb{P}$ denote the set of prime numbers.

Two lattice points $A$ and $B$ are $\mathbb{P}$-visible if the number of integer lattice points strictly in the interior of the line segment connecting them is exactly a prime number.

Since the number of interior lattice points on the segment is given by $\gcd(|x_A - x_B|, |y_A - y_B|) - 1$, the condition for $\mathbb{P}$-visibility is strictly: $$ \gcd(|x_A - x_B|, |y_A - y_B|) - 1 \in \mathbb{P} $$

The Problem

Let $S_N = \{1, 2, \dots, N\}^2$ be the standard $N \times N$ grid. We define the Prime-Visibility Graph $G_N$ as the undirected graph whose vertex set is $S_N$, with an edge between $A$ and $B$ if and only if they are $\mathbb{P}$-visible.

Let $\omega(G_N)$ denote the clique number (the size of the largest complete subgraph) of $G_N$.

Question: What is the asymptotic growth rate of $\omega(G_N)$ as $N \to \infty$? Is $\omega(G_N)$ bounded by a universal constant, or does it diverge? If it diverges, what is the best known asymptotic bounds for it?

My Attempts & Partial Results

To show this is non trivial, I've made a few observations, mostly centering around parity obstructions.

1. The 1-Dimensional Case is Strictly Bounded: If we restrict our points to a single horizontal line (for example $y_A = y_B$), the condition simplifies to $|x_A - x_B| - 1 = p$. This means the distance between any two points in a 1D clique must be $p+1$. If we have a clique of size 4, say $x_1 < x_2 < x_3 < x_4$, then let the consecutive differences be $d_1, d_2, d_3$. We require:

• $d_1 = p_1 + 1$
• $d_2 = p_2 + 1$
• $d_1 + d_2 = p_4 + 1 \implies p_1 + p_2 + 1 = p_4$

If $p_1$ and $p_2$ are both odd primes ($\ge 3$), their sum is even, making $p_4$ an even prime, which forces $p_4 = 2$. This contradicts $p_1, p_2 \ge 3$. Thus, 1D cliques are severely restricted by parity and cannot grow arbitrarily large.

2. The 2D Case Escapes the Parity Trap: In two dimensions, the $\gcd$ function prevents the simple linear parity lock. I was able to construct a clique of size 3 (a triangle). For example, the vertices $V_1 = (0,0)$, $V_2 = (3,0)$, and $V_3 = (0,3)$.

• $\gcd(3,0) - 1 = 2 \in \mathbb{P}$
• $\gcd(0,3) - 1 = 2 \in \mathbb{P}$
• $\gcd(-3,3) - 1 = 2 \in \mathbb{P}$

3. Connection to Prime Tuples: For $\omega(G_N)$ to grow arbitrarily large, we would need to find sets of pairs $(\Delta x, \Delta y)$ where the $\gcd$s of all $\binom{k}{2}$ pairwise combinations minus 1 yield prime numbers. This feels tangentially related to the generalized Hardy-Littlewood $k$-tuple conjecture or Schinzel's Hypothesis H, but projected through the greatest common divisor onto a 2D lattice grid.

A trivial upper bound on the maximum degree of $G_N$ via the Prime Number Theorem gives $\Delta(G_N) = \mathcal{O}(N^2 / \log N)$, which loosely upper-bounds the clique number, but I suspect the actual growth rate is vastly slower—perhaps even logarithmic or bounded by a constant $\mathcal{O}(1)$ due to modular arithmetic constraints across multiple dimensions.

Does anyone know if this specific graph construction has been studied, or can anyone spot a geometric/algebraic obstruction that firmly bounds $\omega(G_N)$?