來自 U群 Itst 的證明。

欽定點的值域為 \([0,R]\)。首先只考慮右下凸包，即凸包上斜率大于 \(0\) 且嚴格遞增的部分。由于不存在三點共線，所以斜率互不相同。設右下角凸包點數上界為 \(T\)，則整個凸包點數上界為 \(4T\)。

將右下凸包上的點按照橫坐標排序，記第 \(i\) 個點的坐標為 \((x_i,y_i)\)。

取兩個相鄰的點 \(u(x_i,y_i),v(x_{i+1},y_{i+1})\)，不妨設 \(\scr l_{uv}\) 的斜率為 \(\dfrac{p_i}{q_i}\)，這里是一個既約分數。由右下凸包，我們可以得到 \((x_{i+1} + y_{i+1}) - (x_i + y_i) \geq p + q\)。

推廣到整個右下凸包上的點，我們可以得到：

又因為有：

接下來需要證明的是分子分母和 前 \(i\) 小的既約分數 的分子分母和超過 \(2 \times R\)。

構造一個下標從 \(1\) 開始的不降自然數序列 \(P\) 使得對于 \(i \geq 1,\dfrac{i \times (i - 1)}{2} < j \leq \dfrac{i \times (i + 1)}{2}\)，有 \(P_j = i\)。

記 \(S_i\) 表示 分子分母和 前 \(i\) 小的既約分數 的分子分母和，\(sum_{P_i}\) 為序列 \(P\) 前 \(i\) 項的和，有 \(S_i \geq sum_{P_i}\)。因為要證 \(S_T \geq 2 \times R\)，所以只需要證明 \(sum_{P_T} \geq 2 \times R\)。

取 \(t = \lfloor \sqrt{T} \rfloor\)，有：

又有：

帶入 \(T = 4 \times R^{\frac{2}{3}}\)，得到：

故得證命題：坐標范圍為 \([0,R]\) 的整點凸包在不存在三點共線的前提下，凸包上的點數為 \(R^{\frac{2}{3}}\) 量級。