離散フーリエ変換の加法的整数論への利用
次の命題と証明に出会った：
「$S\subset F_p^*$ とする。$|S|≧p^{3/4}$ならば、任意の$x \in F_p$に対して、
$a_1 b_1+a_2 b_2+a_3 b_3 = x$を満たす $a_1,a_2,a_3,b_1,b_2,b_3 \in S$が存在する」
（https://math.stackexchange.com/questions/4492588/let-p-be-a-prime-number-and-s-subseteq-1-2-cdots-p-1-be-a-subset-such-th）
この命題は上記リンクのコメント欄にあるリンク先の資料の「補題１」に過ぎない（そこに証明がある）。
証明は離散フーリエ変換を使い、命題の非自明さの割に短くて驚き、理解のために自分の言葉で説明を試みた。
（手法は解析的で、直感的な解釈はあまりつかめずにいる。）
資料では、もっと奥が深い内容に進んでいくのであるが、今回は踏み込まなかった。
[余談]
Cauchy-Davenport Theoremというものを知った。
$A,B\subset F_p$に対して$|\{a+b|a∈A,b∈B\}| \geq min\{p,|A|+|B|-1\}$が成り立つ。
この視点では、例えば$|S|>p/3$ならば上記の結論が言える。
pが小さいときにはこちらの条件の方が強い主張となるが、
pが大きいときには上記の命題のほうが強く、この方針ではうまくいかない。
[離散フーリエ変換]
$f(x)$の離散フーリエ変換$\widehat{f}(w)$は、
$\widehat{f}(w) = \sum_{x\in F_p} f(x)exp(2πixw/p)$ で定義され、次のような性質がある。
[1] 逆変換：$f(x) = 1/p\cdot\sum_{w\in F_p} \widehat{f}(w)exp(-2πixw/p) $
[2] $f$と$g$の畳み込みを
$(f*g)(x) = \sum_{a,b\in F_p, a+b=x} f(a)g(b) = \sum_{y\in F_p}f(x-y)g(y)$で定義すると、
畳み込みのフーリエ変換＝フーリエ変換の積：
$\widehat{(f*g)}(w) = \widehat{f}(w)\widehat{g}(w)$
[3] 線形結合：$\widehat{(af+bg)}(w) = a\widehat{f}(w)+b\widehat{g}(w)$
[4] スケール変更：$s\in F_p^*$に対し、$f(s^{-1}x)$のフーリエ変換は、$\widehat{f}(sw)$
[5] パーセバルの定理：$\sum_{w\in F_p}|\widehat{f}(w)|^2 = p\sum_{x\in F_p} |f(x)|^2$
[本題]
$a\in F_p$ に対して、指示関数$\chi(a)$を、
$a\in S$のとき$\chi(a)=1$
そうでないとき$\chi(a)=0$
と定義する。
$x\in F_p$に対して、$f(x) = \sum_{s\in S}χ(s^{-1}x)$ を考えると、次の性質がある：
$f(x)>0$ ⇔ $ab = x$ を満たす $a,b \in S$ が存在する
（より詳しく、$f(x)$は$x=ab$を満たす$a,b \in S$の組の個数である）
（計算式の$χ(s^{-1}x)=1$となる項に対して、$a=s, b=s^{-1}x$を考えれば良い）
---
・方針
3重畳み込み$(f*f*f)(x) = \sum_{a,b,c\in F_p, a+b+c=x} f(a)f(b)f(c)$ を考えると、次の性質がある
$(f*f*f)(x)>0$ ⇔ $a_1 b_1+a_2 b_2+a_3 b_3 = x$ を満たす $a_1,a_2,a_3,b_1,b_2,b_3 \in S$が存在する
従ってこの関数の値が0より大きいことを示せば良い
$(f*f*f)(x) = 1/p\cdot\sum_{w\in F_p} \widehat{(f*f*f)}(w)exp(-2πixw/p)$ ([1]による)
$ = 1/p\cdot\sum_{w\in F_p} \widehat{f}(w)^3 exp(-2πixw/p)$ ([2]による)
$ = 1/p\cdot\widehat{f}(0)^3 + 1/p\cdot\sum_{w\in F_p^*} \widehat{f}(w)^3 exp(-2πixw/p)$ (和の範囲の分解)
フーリエ変換と$f$の定義により $\widehat{f}(0) = \sum_{x\in F_p}{f}(x) = |S|^2 $ なので、
$\sum_{w\in F_p^*} \widehat{f}(w)^3 exp(-2πixw/p) > -|S|^6$ を示せば目的を達成する。
特に $\sum_{w\in F_p^*} |\widehat{f}(w)|^3 < |S|^6$ を示せば目的を達成する。
---
・準備1：$|\widehat{f}(w)|^2 < \sqrt{p} |S|$
$|\widehat{f}(w)|^2 = |\sum_{s\in S} \widehat{\chi}(sw)|^2$ ([3],[4]による)
$ \leq \sum_{s\in S} 1^2 \cdot \sum_{s\in S} |\widehat{\chi}(sw)|^2 $ (コーシーシュワルツ)
$ < |S|\cdot\sum_{u\in F_p} |\widehat{\chi}(u)|^2 $ (和の範囲のかさ増し)
$= |S|\cdot p\sum_{y\in F_p} |{\chi}(y)|^2 $ ([5]による)
$= p|S|^2$
---
・準備2：$\sum_{x\in F_p} |{f}(x)|^2 \leq |S|^3$
これは、$f(x)$が0から$|S|$の間の整数であることと、$f(x)$の和が$|S|^2$である制約から従う。
(二乗和)＝(和の二乗)＋(分散)で、和が$|S|^2$と決まっているので、分散が最大の時に二乗和が最大である。
具体的に、$|S|$個の$x$に対して$|S|$、残り$p-|S|$個の$x$に対して$0$となる関数の二乗和が最大値$|S|^3$を与える。
補足：$f$がこの形でない関数の場合は、$1\leq f(x_1)\leq f(x_2)\leq |S|-1$となる$x_1,x_2$が存在し、
$f(x_1)$を1つ減らして$f(x_2)$を1つ増やせば、制約を満たしたまま二乗和がより大きくなる。
---
・本題
$\sum_{w\in F_p^*} |\widehat{f}(w)|^3 < \sqrt{p}|S|\cdot\sum_{w\in F_p^*} |\widehat{f}(w)|^2$ (準備1による)
$ <\sqrt{p}|S|\cdot\sum_{w\in F_p} |\widehat{f}(w)|^2$ (和の範囲のかさ増し)
$ < \sqrt{p}|S|\cdot p\sum_{x\in F_p} |{f}(x)|^2$ ([5]による)
$ \leq \sqrt{p}|S|\cdot p|S|^3$ (準備2による)
$ = \sqrt{p}|S|\cdot p|S|^3$
$ = p^{3/2} |S|^4 $
$ \leq |S|^6 $ (問題文の仮定による)
で目的が達成された。
[ちょっと考察]
$(f*f)(x)$を同様の方法で評価しても有益な結果を得られなかった。
$(f*\chi*\chi)(x)$を同様の方法で評価すると、同じ条件で次も言えそうに見えた。
「任意の$x \in F_p$に対して、$a_1 b+a_2+a_3 = x$を満たす $a_1,a_2,a_3,b \in S$が存在する」
2022/7/21
ノート一覧
