I might have misunderstood, but if we take the 4 corner points (and have the remaining N-4 points inside), then their convex hull is a square with O(N) lattice points on every edge...

A heuristic approach: take all the irreducible lattice vectors in [0, a]² for some a, and sort them by the angle. Now construct the lower right envelope by taking prefix sums of the sorted list of those vectors. Expected gain in both x and y coordinate per point is Θ(a), and the number of vectors should be Θ(a²). If you plug in , the last prefix sum is (Θ(N), Θ(N)), and the lower right envelope contains points.

As for the other direction, it seems hard. I couldn't find a coherent proof for the 2-dimensional case on the Internet.

There's a paper in German ("Über die Gitterpunke auf konvexen Kurven" by Vojtěch Jarník) that proves a Θ(l^2 / 3) bound for convex C¹ curves F of length l with 0 ≤ F' ≤ 1.

If we have a convex polygon, we can draw a convex C¹ curve through all its vertices and apply his result to each octant. (The length of the curve is O(N).) This gives a O(N^2 / 3) bound for convex polygons.

Edit: The paper also talks about convex polygons. One result is that the maximum number of vertices a convex polygon with integer coordinates and circumference x can have is

A simplified proof for the fact that a convex lattice polygon with coordinates in [0, N] has at most O(N^2 / 3) vertices:

Let (x₀, y₀), ..., (x_n, y_n) be the vertices with (x₀, y₀) = (x_n, y_n). Let (a_i, b_i) = (x_i + 1 - x_i, y_i + 1 - y_i) be the i-th line segment. W.l.o.g. let (a₀, b₀), ..., (a_k, b_k) be the line segments with 0 ≤ a_i ≤ b_i (the ones in one octant). We'll only look at these segments. Note that

so there are at most N^2 / 3 indices i with b_i ≥ N^1 / 3. Let's call those segments long and the other ones short. Let m + 1 be the number of short segments and (a_sj, b_sj) be the j-th short segment. Then

so

On the other hand, by restriction on the octant and convexity of the polygon, the sequence is sorted, so using a_i ≤ b_i we get

so m ≤ 2N^2 / 3 hence k ≤ 3N^2 / 3. Summing up over all 8 octants, we get an upper bound of 24N^2 / 3 for the number of vertices.