グラフ理論で数論の定理を証明する(小ネタ)
おもしろい証明を見つけたのでかくことにしました
(追記)
以下のページを訳しただけ説があります
The crossing number inequalityterrytao.wordpress.com
交差数定理という次のグラフ理論についての定理があります
定理(交差数定理)
\[cr(G)\gg \frac{|E|^3}{|V|^2}\]
\[cr(G)\gg \frac{|E|^3}{|V|^2}\]
ここでcr(G)とはグラフを平面に書いたときにGの辺の交点数の最小です(で1)
ちなみに右辺の定数に関しては が大きければ大きいほどでかくなり、 の時1/64とかです
これは結構強い定理で最小交差数自体特別なグラフに関して求めるのが大変なのに下界がわかるというのがやばい気がします
この定理の証明もめっちゃエモいのですが今回は本筋からそれるため次の記事でやろうと思います
驚くべきことにこの定理は加法的数論に応用を持っており次の定理が示されます
定理(Elekes) Aを自然数の部分集合とすると\[max\{|A+A|,|A\cdot A|\}\gg |A|^\frac{5}{4}
\]
\]
ただしです
この定理のイメージはとなるが流石にどっちかは十分大きいだろみたいなイメージです
冷静に右辺の定数も決定可能です
proof.
とするとであり、
L内の直線lを一つ固定するとと媒介変数表示でき、個の点がl上にあることがわかるのでである
Pを頂点とし、L上隣り合っている頂点(間に他の頂点がない)を辺で結んだグラフを考えそれをGとすると、なので
よってなのでとなり、示された
めっっっっっちゃ頭良いなって感じですね
交差数定理は前から好きだった定理なのでどっかに応用したいなあと思っていたらめっちゃ頭いい感じで受けてしまった