グラフ理論で数論の定理を証明する(小ネタ)

\displaystyle

 

おもしろい証明を見つけたのでかくことにしました

(追記){\displaystyle f(n)\gg g(n)とはある定数CについてNがあり任意のm \ge Nについてf(m) \ge Cg(m)となるという意味です}

以下のページを訳しただけ説があります

The crossing number inequalityterrytao.wordpress.com

交差数定理という次のグラフ理論についての定理があります

定理（交差数定理）
\[cr(G)\gg \frac{|E|^3}{|V|^2}\]

ここでcr(G)とはグラフを平面に書いたときにGの辺の交点数の最小です({\displaystyle K_5}で1)
ちなみに右辺の定数に関しては\displaystyle \frac{|E|}{|V|} が大きければ大きいほどでかくなり、 {\displaystyle \frac{|E|}{|V|} \ge 4}  の時1/64とかです
これは結構強い定理で最小交差数自体特別なグラフに関して求めるのが大変なのに下界がわかるというのがやばい気がします

この定理の証明もめっちゃエモいのですが今回は本筋からそれるため次の記事でやろうと思います 
驚くべきことにこの定理は加法的数論に応用を持っており次の定理が示されます

定理（Elekes）　 Aを自然数の部分集合とすると\[max\{|A+A|,|A\cdot A|\}\gg |A|^\frac{5}{4}
\]

ただし\displaystyle A+A={a+b|∃a,b∈A},A\cdot A={ab|∃a,b∈A}です

この定理のイメージは\displaystyle Aが等差数列の時|A+A|\sim |A|でAが等比数列の時は |A\cdot A|\sim|A|となるが流石にどっちかは十分大きいだろみたいなイメージです

冷静に右辺の定数も決定可能です

proof.

 {\displaystyle P=(A\cdot A)×(A+A),L=\{l⊆R^2|∃a,b∈A, l=\{ay=x+ab\}\},I(P,L)=\{(l,p)∈L×P|p∈l\}}とすると{\displaystyle |P|=|A\cdot A||A+A|,|L|=|A|^2}であり、

L内の直線lを一つ固定すると{\displaystyle am=x,b+m=y}と媒介変数表示でき、{\displaystyle |A|}個の点がl上にあることがわかるので{\displaystyle|I(P,L)|=|A|^3}である

Pを頂点とし、L上隣り合っている頂点(間に他の頂点がない)を辺で結んだグラフを考えそれをGとすると、{\displaystyle\mathbb |V|=|P|=|A\cdot A||A+A|,|E|=|I(P,L)|-|L|=|A|^3-|A|^2}なので

{\displaystyle\mathbb |A|^4 \gg {}_{|L|} C_2 \ge cr(G) \gg \frac{|E|^3}{|V|^2} \gg \frac{|A|^9}{|A\cdot A|^2|A+A|^2}}

よって{\displaystyle|A\cdot A||A+A| \gg |A|^\frac{5}{2}}なので{\displaystyle max\{|A+A|,|A\cdot A|\}\gg |A|^\frac{5}{4}}となり、示された

 

めっっっっっちゃ頭良いなって感じですね

交差数定理は前から好きだった定理なのでどっかに応用したいなあと思っていたらめっちゃ頭いい感じで受けてしまった