Szemerédi–Trotterの定理

$I:=I(P,\mathcal{L})$ とする。$l=0$ なら $I=0$ なので $l\ge1$ とする。相異なる 2 点 $p\neq p'$ と直線 $\ell$ の組で $p,p'\in\ell$ となるもの $(p,p',\ell)$ を数える。直線 $\ell$ ごとに数えると $\sum_\ell k_\ell(k_\ell-1)$ 個である。相異なる 2 点を通る直線は 1 本しかないので、点の順序対 $(p,p')$ ごとに数えると $n(n-1)$ 個以下である。よって
$$ \sum_\ell k_\ell^2\le n(n-1)+\sum_\ell k_\ell=n(n-1)+I $$
である。Cauchy–Schwarzの不等式 により $I^2=\bigl(\sum_\ell k_\ell\bigr)^2\le l\sum_\ell k_\ell^2$ なので、$I^2\le l\,n(n-1)+lI\le ln^2+lI$ である。$I$ についての 2 次不等式 $I^2-lI-ln^2\le0$ を解くと
$$ I\le\frac{l+\sqrt{l^2+4ln^2}}{2}\le\frac{l+(l+2n\sqrt l)}{2}=n\sqrt l+l $$
を得る（$(l+2n\sqrt l)^2=l^2+4nl\sqrt l+4ln^2\ge l^2+4ln^2$）。
2 つ目の不等式は、点と直線の役割を入れ替えて同じ議論をすればよい。相異なる 2 本の直線は 1 点以下でしか交わらないので、$\sum_pr_p(r_p-1)\le l(l-1)$ であり、上と同じ計算で $I\le l\sqrt n+n$ を得る。$\square$

$n=0$ なら $I(P,\mathcal{L})=0$ なので、$n\ge1$ とする。$P$ の点を 1 つも含まない直線を取り除いても接続の個数は変わらず、直線の本数は増えないので、どの直線も $P$ の点を 1 つ以上含むとしてよい。
グラフを作る。 頂点の集合を $P$ とするグラフ $G$ を次のように作る。各直線 $\ell\in\mathcal{L}$ の上の $P$ の点を直線に沿って順に並べ、隣り合う 2 点を辺で結ぶ。相異なる 2 点を通る直線は 1 本しかないので、同じ 2 点が 2 本の直線から結ばれることはなく、$G$ は多重辺も自己ループもない単純グラフである。直線 $\ell$ からは $k_\ell-1$ 本の辺ができるので、$G$ の辺の本数は
$$ m=\sum_\ell(k_\ell-1)=I(P,\mathcal{L})-l $$
である。
描画の交差を数える。 各頂点をその点に、各辺を両端を結ぶ線分に対応させた描画 $D$ を考える。これは 交差数(グラフ) の定義「良い描画と交差数」の意味の良い描画である。実際、(D1) 辺の線分の内部には、同じ直線の上の $P$ の点はなく（隣り合う 2 点を結んだから）、ほかの $P$ の点もない（線分の内部の点で $P$ に属するものは、その直線の上の点だから）。(D2) 端点を共有する 2 辺は、同じ直線の上なら共有する端点の両側にのび、違う直線の上なら 2 直線の共有点が共有する端点そのものなので、ほかに共有点はない。(D3) 端点を共有しない 2 辺は、同じ直線の上なら交わらず、違う直線の上なら共有点は 1 個以下である。
同じ直線の上の辺の内部は互いに交わらないので、内部どうしが交わる 2 辺は違う直線の上にある。2 本の直線 $\ell\neq\ell'$ の共有点は 1 個以下で、その点を内部に含む辺は $\ell$ の上と $\ell'$ の上に 1 本ずつ以下である。よって描画 $D$ の交差の個数は直線の対の個数 $\binom l2$ 以下であり、
$$ \operatorname{cr}(G)\le\operatorname{cr}(D)\le\binom l2\le\frac{l^2}{2} $$
である。
交差数補題を当てる。 $m\ge4n$ なら、交差数(グラフ) の定理「交差数補題」（頂点 $n\ge1$ 個、辺 $m\ge4n$ 本の単純グラフについて $\operatorname{cr}(G)\ge m^3/(64n^2)$）により
$$ \frac{m^3}{64n^2}\le\operatorname{cr}(G)\le\frac{l^2}{2} $$
であり、$m^3\le32n^2l^2$、すなわち $m\le32^{1/3}(nl)^{2/3}< 4(nl)^{2/3}$ である（$32< 64$）。$m< 4n$ の場合と合わせて、どちらの場合も $m\le4(nl)^{2/3}+4n$ である。$I(P,\mathcal{L})=m+l$ なので主張が従う。$\square$

1：$P$ の点を $k$ 個以上含む直線の全体を $\mathcal{L}$ とすると、$I(P,\mathcal{L})\ge kl$ である。thm-st-main と $l\le\frac k2l$ から $kl\le4(nl)^{2/3}+4n+\frac k2l$、すなわち $\frac k2l\le4(nl)^{2/3}+4n$ である。右辺の 2 つの項の少なくとも一方は $\frac k4l$ 以上である。$4n\ge\frac k4l$ なら $l\le16n/k$ である。$4(nl)^{2/3}\ge\frac k4l$ なら $l^{1/3}\le16n^{2/3}/k$、すなわち $l\le4096n^2/k^3$ である。
2：$\mathcal{L}$ の直線が $k$ 本以上通る点の全体を $P'$ とすると、$I(P',\mathcal{L})\ge kn'$ である。thm-st-main と $4n'\le\frac k2n'$（$k\ge8$）から $\frac k2n'\le4(n'l)^{2/3}+l$ である。$l\ge\frac k4n'$ なら $n'\le4l/k$ であり、$4(n'l)^{2/3}\ge\frac k4n'$ なら $n'\le4096l^2/k^3$ である。$\square$

$N:=\lvert A\rvert$、$X:=\lvert A+A\rvert\,\lvert A\cdot A\rvert$ とおく。$N=1$ なら $X=1\ge\frac1{91}$ なので、$N\ge2$ とする。$A^*:=A\setminus\{0\}$、$M:=\lvert A^*\rvert$ とすると $M\ge N-1\ge N/2$ である。
点の集合を $P:=(A+A)\times(A\cdot A)$（$\lvert P\rvert=X$）とし、$a\in A^*$、$b\in A$ について直線 $\ell_{a,b}:=\{(x,y)\mid y=a(x-b)\}$ を考える。傾き $a$ と $x$ 切片 $b$ が直線を決めるので、これらは相異なる $NM$ 本の直線である。$c\in A$ について点 $(b+c,ac)$ は $\ell_{a,b}$ の上にあり、$b+c\in A+A$、$ac\in A\cdot A$ なので $P$ に属する。$c$ が違えば点も違うので、各直線は $P$ の点を $N$ 個以上含み、接続は $N\cdot NM=N^2M$ 個以上ある。thm-st-main により
$$ N^2M\le4(XNM)^{2/3}+4X+NM $$
である。$N\ge2$ なので $NM\le\frac12N^2M$ であり、$\frac12N^2M\le4(XNM)^{2/3}+4X$ となる。右辺の 2 つの項の少なくとも一方は $\frac14N^2M$ 以上である。
$4X\ge\frac14N^2M$ なら $X\ge\frac1{16}N^2M\ge\frac1{32}N^3\ge\frac1{32}N^{5/2}$ である。$4(XNM)^{2/3}\ge\frac14N^2M$ なら $XNM\ge\frac{1}{64}(N^2M)^{3/2}$、すなわち $X\ge\frac1{64}N^2M^{1/2}\ge\frac{1}{64\sqrt2}N^{5/2}$ である。$64\sqrt2< 91$ なので、どちらの場合も $X\ge N^{5/2}/91$ である。最後の主張は $\max\{u,v\}^2\ge uv$ と $\sqrt{91}< 10$ から従う。$\square$