For a vector $v = (x, y)$, define $\|v\| = |x| + |y|$, the so-called taxicab distance (or taxicab norm). Embed the array of points in the plane such that they correspond to the lattice points in $\{(x, y) : 1 \le x, y \le 2004\}$.

Consider a convex $n$-gon drawn in our square array, and imagine that we walk along the edges in a counterclockwise direction. Then we can orient each edge and obtain a set of $n$ nonzero vectors $S = \{v_i = (x_i, y_i)\}$, with integer coordinates, whose sum is $(0,0)$. $S$ has several further properties. First, no two vectors in $S$ are positive multiples of each other by convexity (if $i \ne j$ and the directed edges $v_i$ and $v_j$ are parallel and pointing in the same direction, then our polygon cannot be strictly convex.) Second, the sum of the $x_i$ which are positive is at most $2003$, and the same is true for the sum of the $y_i > 0$, as well as the sums of the $|x_i|$ and $|y_i|$ for $x_i < 0$ and $y_i < 0$. This is true because all the vectors with, say, $x_i$ positive will correspond to adjacent edges (by convexity), and if one traces these edges in order on the polygon, one must start from a point within $\{(x, y) : 1 \le x, y \le 2004\}$ and finish at a point in that same region; therefore the total displacement in the $x$-dimension is bounded by $2003$. In particular, this implies that $\sum \|v_i\| \le 8012$. Third, given $S$ that satisfies the above properties, we can construct a convex polygon that fits within the bounds: since the polygon should be convex, we must place the vectors end to end ordered by the angle (measured counterclockwise) that they make with the positive $x$-axis, and the resulting polygon will fit within the array because of the given inequalities.

We now show that it is impossible to draw a $562$-gon in the array. We will prove that for every set $S$ of $562$ vectors such that no two are positive multiples of each other, $\sum \|v_i\| > 8012$. We can even ignore the condition that $\sum v_i = (0,0)$. Let us now try to minimize $\sum \|v_i\|$. Since no two vectors in $S$ are positive multiples of each other, we may assume that for each $i$, $\gcd(|x_i|, |y_i|) = 1$, or else we might as well scale that vector down by that gcd (it will only reduce $\sum \|v_i\|$).

Now:

Lemma For any positive integer $k$, the maximum number of distinct $v_i = (x_i, y_i)$ that satisfy $\|v_i\| = k$ and $\gcd(|x_i|, |y_i|) = 1$ is $4\phi(k)$. Recall that $\phi(k)$ is Euler's totient function, which counts the number of positive integers $z \le k$ that satisfy $\gcd(z, k) = 1$.

Proof: For $k=1$, the lemma is trivial. For $k \ge 2$, the gcd condition forces that neither of $x_i$ or $y_i$ can ever be $0$. So, it suffices to show that the number of $v_i$ with $x_i > 0$ and $y_i > 0$ is $\phi(k)$, because there are exactly $4$ ways to choose pairs of signs, for the coordinates of each $v_i$. Well, since $\|v_i\| = k$, this means that $|x_i| + |y_i| = k$. Hence $\gcd(|x_i|, |y_i|) = 1 \Rightarrow \gcd(|x_i|, k) = 1$. By definition of $\phi(k)$, there are precisely $\phi(k)$ ways to choose positive $x_i$ to satisfy this condition; each way yields exactly one positive choice for $y_i$, so we are done with the proof of this lemma. ■

Now for $n = 562$, since $\sum_{k=1}^{21} 4\phi(k) = 560$, we minimize $\sum \|v_i\|$ when we use all $560$ vectors with $\|v_i\| \le 21$, and $2$ more vectors with $\|v_i\| = 22$. The value of this sum is $\sum \|v_i\| \ge \sum_{k=1}^{21} 4k\phi(k) + 2 \cdot 22 = 8032 > 8012$, as was claimed. Thus $n \le 561$.

Indeed, we now construct a $561$-gon in the array by constructing a suitable set $S$. Start by setting $S$ to be the set of all $560$ integer vectors $(x_i, y_i)$ with norm at most $21$ and $\gcd(|x_i|, |y_i|) = 1$. By symmetry, the vector sum of these $560$ vectors is $(0, 0)$. Also by symmetry, the sum of all of the positive $x_i$ is exactly $1/4$ of the sum of all of the taxicab norms, so it is $\sum_{k=1}^{21} k\phi(k) = 1997$. This is the span of the $560$-gon in the $x$-dimension. Similarly, that is also the span of the $560$-gon in the $y$-dimension.

Next, remove from $S$ the vectors $(20, 1)$ and $(-11, 10)$, and insert the vectors $(5, 17)$, $(-17, -5)$, and $(21, -1)$. Now we have a $561$-gon. Since the vector sum of $(20, 1)$ and $(-11, 10)$ is equal to the vector sum of the $3$ new vectors, this preserves the fact that $\sum v_i = (0, 0)$, so we can still have a closed, convex polygon. Let us see what has happened to the $x$-span and $y$-span: we removed $20$ from the sum of positive $x_i$, but added back $5$ and $21$. This is a net gain of $6$, so the sum of positive $x_i$ will increase from $1997$ to $2003$—this exactly matches the upper limit imposed by the second observation at the beginning of the proof. Similarly, the sum of positive $y_i$ will lose summands of $1$ and $10$ from the deletion, but it will gain $17$ from the insertion. This is also a net gain of $6$, so we also have $2003$ as the final sum of positive $y_i$. Since the vector sum of all $v_i$ is $(0, 0)$, similar results with $2003$ hold for the negative $x_i$ and $y_i$. By the third observation at the beginning of the proof, we are done.