Here is one way to do it. I figured this out through experimentation.
For any grid of size $n \geq 100$ we completely fill out the following diagonals:
$$[0, -1, 2, -5, 8, -15, 20, -31, -42, 48, 67, -76]$$
We fill these out from top left to bottom right where diagonal $0$ is the top-left to bottom-right diagonal (slope -1) starting at index $G_{0,0}$. Diagonal $i$ is the slope -1 diagonal starting at index $G_{0,i}$ if $i \geq 0$ or the slope -1 diagonal starting at index $G_{|i|,0}$ if $i < 0$. This means diagonal 20 starts at $G_{0,20}$ and diagonal -5 starts at $G_{5,0}$. The first few on a small $10 \times 10$ grid would look like this:
|0123456789
-+----------
0|1010000010
-1|1101000001
-2|0110100000
-3|0011010000
-4|0001101000
-5|1000110100
-6|0100011010
-7|0010001101
-8|0001000110
-9|0000100011
After you have determined one of the entries in the diagonal does not cause a rectangle, the rest will follow by symmetric translation$^*$. For instance in this example, consider entry $G_{5,0}$. It lines up with the following entries vertically:
$$[G_{0,0}, G_{1,0}]$$
And the following entries horizontally:
$$[G_{5,4}, G_{5,5}, G_{5,7}]$$
We can take each pair of these to determine which diagonal would have to be present to form a rectangle:
- $G_{0,0}$ and $G_{5,4}$ need entry $G_{0,4}$ on diagonal $4$.
- $G_{0,0}$ and $G_{5,5}$ need entry $G_{0,5}$ on diagonal $5$.
- $G_{0,0}$ and $G_{5,7}$ need entry $G_{0,7}$ on diagonal $7$.
- $G_{1,0}$ and $G_{5,4}$ need entry $G_{1,4}$ on diagonal $3$.
- $G_{1,0}$ and $G_{5,5}$ need entry $G_{1,5}$ on diagonal $4$.
- $G_{1,0}$ and $G_{5,7}$ need entry $G_{1,7}$ on diagonal $6$.
This is why the "next" available diagonal is diagonal $8$ because all others would cause rectangles with the existing diagonals. You can use similar logic to show that diagonals $[-2, -3, -4]$ would have cause rectangles earlier. This logic can apply to all of the diagonals above for grids of size $83 \times 83$ or larger.
We can prove this setting will always give over $8n$ entries present $P(n)$. For $n \geq 76$, the number of entries present with the given diagonals is:
$$\begin{align*}
P(n) &= n + (n-1) + (n-2) + (n-5) + (n-8) + (n-15) + (n-20) + (n-31) + (n-42) + (n-48) + (n-67) + (n-76)\\
P(n) &= 12n - 315\\
\end{align*}$$
Clearly for $n = 100$ this satisfies:
$$1200-315 =885 \geq 800$$
Then for any $n' = n + 1$ where $n \geq 100$ we simply get:
$$\begin{align*}
P(n') & \geq 8n'\\
12 + P(n) & \geq 8n+8\\
12 & \geq 8 & \square
\end{align*}$$
$^*$ I add this asterisk because this is not quite always correct. It is correct for $n \geq 100$ but not in general. Consider the following diagonals on a $7 \times 7$ grid:
$$[0, -1, 2, -5, 6]$$
We get:
|0123456
-+-------
0|1010001
-1|1101000
-2|0110100
-3|0011010
-4|0001101
-5|1000110
-6|0100011
We see this is fine for $n = 7$, however, when we move to $n=8$, this diagonals will not work:
|01234567
-+--------
0|10100010
-1|11010001<
-2|01101000
-3|00110100
-4|00011010
-5|10001101<
-6|01000110
-7|00100011
^ ^
There is a rectangle made of the rows and columns I've pointed out. So this does not always hold with translation symmetry because sometimes the grid size is actually helping us by preventing further rows and columns from conflicting on the diagonals.
My procedure for finding this was just to "select the next non-conflicting diagonal" and this actually works really well for small grids. For instance, it is perfect for $n \leq 13$ we get (best comes from A072567):
n | best | I filled | diagonals to use
---+------+----------+-----------------
2 | 3 | 3 | 0, -1
3 | 6 | 6 | 0, -1, 2
4 | 9 | 9 | 0, -1, 2
5 | 12 | 12 | 0, -1, 2
6 | 16 | 16 | 0, -1, 2, -5
7 | 21 | 21 | 0, -1, 2, -5, 6
8 | 24 | 24 | 0, -1, 2, -5
9 | 29 | 29 | 0, -1, 2, -5, 8
10 | 34 | 34 | 0, -1, 2, -5, 8
11 | 39 | 39 | 0, -1, 2, -5, 8
12 | 45 | 45 | 0, -1, 2, -5, 8, -11
13 | 52 | 52 | 0, -1, 2, -5, 8, -11, 12
14 | ? | 54 | 0, -1, 2, -5, 8
15 | ? | 59 | 0, -1, 2, -5, 8
16 | ? | 65 | 0, -1, 2, -5, 8, 15
You can see there is a pattern arising, but it's not consistent as you can see it changes when we get to certain values of $n$. To show how close of an approximation this gets, we can use the examples in Apass.Jack's answer:
n | best | I filled | diagonals to use
----+------+----------+-----------------
21 | 105 | 98 | 0, -1, 2, -5, 8, -15, 18
31 | 186 | 171 | 0, -1, 2, -5, 8, -15, 20, -27, 30
91 | 910 | 777 | 0, -1, 2, -5, 8, -15, 20, -31, -42, 48, 67, -76
133 | 1596 | 1335 | 0, -1, 2, -5, 8, -15, 20, -31, -42, 48, 67, -76, -100, 112
So it's clearly a lower bound. There also doesn't seem to be a known pattern in the diagonals other than the trivial pattern of "this is what I calculated under these constraints". What is interesting is if we only use non-negative diagonals then we get pattern A025582. However, I cannot find a pattern for positive and negative diagonals.
