一天證明一個 Normal Distribution 的性質 Day9： Poisson Summation Formula
小時候就學過無窮等比級數:
\[ \sum_{n=0}^{\infty} r^n = \frac{1}{1-r}, \quad |r|<1 \] 當時候胡思亂想，想說指數部分如果改成平方怎麼算? \[ \sum_{n=0}^{\infty} r^{n^2} = ? \] 嗯… 當然是完全不會算，沒想到在大學的殿堂裡還會再次遇見他… Poisson Summation Formula (PSF)。
這真的是數學中最奇怪又深奧的恆等式。
柏松求和公式 - 高斯函數
柏松求和公式 (Poisson Summation Formula) 告訴我們，如果上面那個函數叫做 \(S(t)\): \[ S(t) := \sum_{n=-\infty}^{\infty} e^{-\pi t n^2} \qquad \forall t > 0 \] 對於所有 \(t>0\) 都有定義，這裡我們稍微未卜先知，做了一個變數變換 \(r=e^{-\pi t}\)，不過這是等價的。
那麼我們可以把它寫成另一個無窮級數: \[ S(t) = \frac{1}{\sqrt{t}} \sum_{k=-\infty}^{\infty} e^{-\frac{\pi k^2}{t}} = \frac{1}{\sqrt{t}} S\left(\frac{1}{t}\right) \tag{1}\label{eq:psf_s} \] 疑，形式還是 \(S\) 但是 input \(t\) 變成了倒數 \(\frac{1}{t}\)。前面還乘以 \(\frac{1}{\sqrt{t}}\)。
你說，這樣有了 \(S(t)\) 跟 \(S(\frac{1}{t})\) 的關係，我們還是沒辦法算出來啊？對！但這個對稱性本身，暗示了一個更宏大的幾何結構。
Jacobi Theta Function 與神秘的空間 M [Optional]
當一個函數滿足一個 functional equation (函數方程式) 的時候，這時候我們就要來研究是否有唯一解? 若不唯一，那解有哪些?
我們很自然地可以將 \(S(t)\) 定義到複數平面 (只要實部大於 0)。 這樣我們就可以把 \(S(t)\) 視為一個所謂的 Jacobi Theta Function: \[ \theta(z; \tau) := \sum_{n=-\infty}^{\infty} e^{\pi i \tau n^2} e^{2 \pi i n z} \] 這邊 \(z \in \mathbb{C}\)，\(\tau \in \mathbb{H}\) (上半平面，對應原本的 \(it\))。因為 \(n^2\) 跑得比 \(n\) 快，所以我們只需要 \(\tau\) 的虛部大於 0 就可以保證收斂性。
常見的 theta function 總共有四種，我們這邊用到的是 \(\theta_3\)（當 \(z=0\) 時就是我們原本的級數）。
這時候，讓我們退一步看。剛剛那個 \(S(t) = \frac{1}{\sqrt{t}}S(1/t)\) 的性質，用複數語言寫出來，其實是在說這個函數在經過特定的「變換」（比如 \(\tau \to -1/\tau\)）後，會變回自己乘以一個因子。
那我們能不能用將這個等式推廣到複數函數 \(\theta(0; \tau)\) 上呢？ 可以的! 經過一些複雜的分析技巧，我們可以得到: \[ \theta(0; \frac{-1}{\tau}) = \sqrt{\frac{\tau}{i}} \, \theta(0; \tau) \]
這類具有高度對稱性的函數，居住在一個叫做 模形式 (Modular Forms) 的向量空間 \(M\) 裡。
簡單來說，如果一個函數 \(f\) 滿足： \[ f\left(\frac{a\tau+b}{c\tau+d}\right) = (c\tau+d)^k f(\tau) \qquad , \forall \begin{pmatrix} a & b \\ c & d \end{pmatrix} \in SL(2, \mathbb{Z}), \forall \tau \in \mathbb{H} \] 我們就說它是權重為 \(k\) 的模形式。我們的 \(\theta\) 函數大致上就是這樣的一個東西（權重 \(k=1/2\)）。
這個空間 \(M\) 是有限維的！
在某些特定的限制條件下(例如 \(k=12\))，這個空間的維度甚至只有 1。這意味著什麼？這意味著如果我們在這個空間裡找到了兩個函數，它們極有可能是同一個東西（或是只差一個常數倍）。這也就是為什麼數論學家能用 Theta Function 解決很多整數拆分問題的原因——因為路只有一條。
這邊有點含糊了，因為當 \(k=1/2\) 根號複數 \(\sqrt{c\tau+d}\) 會有選分支的問題。所以其實權重 \(k=1/2\) 的模形式要退縮到一個較小的子群，通常是 Level 4 的同餘子群 \(\Gamma_0(4)\)。而在空間 \(M_{1/2}(\Gamma_0(4))\) 中，其維度為 1。
這以後有機會再深入講解。
離散高斯
且讓我們看著 \(\theta\) 的定義式，是不是長得有點像特徵函數 (Characteristic Function) 呢？
讓我們回憶一下機率論。對於一個連續的高斯分佈 (Normal Distribution)，其機率密度函數 (PDF) 是 \(e^{-x^2}\) 的形式，而它的特徵函數 (Characteristic Function, Fourier Transform of PDF) 算出來依然是 \(e^{-\xi^2}\) 的形式。
那如果是離散的呢？
假設我們有一個隨機變數 \(X\)，它只能取整數值 \(n \in \mathbb{Z}\)，而且取 \(n\) 的機率正比於高斯分佈: \[ P(X=n) \propto e^{-\pi t n^2} \] 這就是一個 Discrete Gaussian。
那麼這個離散變數的特徵函數 (Characteristic Function) 是什麼？定義是 \(\mathbb{E}[e^{i \omega X}]\)： \[ \phi_X(\omega) = \sum_{n=-\infty}^{\infty} P(X=n) e^{i n \omega} \propto \sum_{n=-\infty}^{\infty} e^{-\pi t n^2} e^{i n \omega} \] 確實就是 \(\theta_3(z; \tau)\) 阿! (只要令 \(\omega = 2\pi z\), \(\tau = -i t\))
所以，我們可以這樣理解：
- 連續世界：高斯函數的傅立葉變換是高斯函數。
- 離散世界：Theta Function 其實就是「離散高斯分佈」的特徵函數。
不過這邊是成正比，分母還差了一個 \(\theta_3(0; it)\)，這是為了讓機率加總為 1。
附錄：Poisson Summation Formula (PSF) 的證明
雖然前面講得很玄，但數學還是要回歸嚴謹。為什麼 \(\sum f(n)\) 會等於 \(\sum \hat{f}(k)\)？這裡給出一個完整的證明。
定理敘述: 假設 \(f(x) \in L^1(\mathbb{R})\) 是一個連續函數，且滿足足夠的衰減條件（見證明）。定義其傅立葉變換為 \(\hat{f}(\xi) = \int_{-\infty}^\infty f(x)e^{-2\pi i\xi x}dx\)。則： \[ \sum_{n=-\infty}^{\infty} f(n) = \sum_{k=-\infty}^{\infty} \hat{f}(k) \]
證明：
我們引入一個輔助函數，將 \(f(x)\) 進行「週期化 (Periodization)」，假設級數收斂： \[ F(x) := \sum_{n=-\infty}^{\infty} f(x+n) \]
第一步：確認 \(F(x)\) 的性質
顯然 \(F(x)\) 是一個週期為 1 的函數。
既然是週期函數，我們就可以將其展開為 傅立葉級數 (Fourier Series)： \[ F(x) = \sum_{k=-\infty}^{\infty} c_k e^{2\pi i k x} \] 其中係數 \(c_k\) 的計算公式為： \[ c_k = \int_{0}^{1} F(x) e^{-2\pi i k x} dx \]
第二步：連結 \(c_k\) 與 \(\hat{f}\) (關鍵步驟)
將 \(F(x)\) 的定義代入 \(c_k\)： \[ c_k = \int_{0}^{1} \left( \sum_{n=-\infty}^{\infty} f(x+n) \right) e^{-2\pi i k x} dx \]
這裡我們遇到了一個數學上的危險操作：積分與求和交換 (Interchange of Summation and Integration)。 \[ \int_{0}^{1} \sum_{n} (...) \stackrel{?}{=} \sum_{n} \int_{0}^{1} (...) \] 交換的條件： 根據 Fubini 定理或控制收斂定理 (Dominated Convergence Theorem)，我們需要 \(f(x)\) 衰減得夠快。一個充分條件是存在常數 \(C>0\) 與 \(\delta > 0\)，使得： \[ |f(x)| \le \frac{C}{(1+|x|)^{1+\delta}} \] 這保證了 \(\sum |f(x+n)|\) 是一致收斂的，積分與求和便可交換。
交換後： \[ c_k = \sum_{n=-\infty}^{\infty} \int_{0}^{1} f(x+n) e^{-2\pi i k x} dx \] 利用 \(e^{-2\pi i k x}\) 的週期性， \(e^{-2\pi i k x} = e^{-2\pi i k (x+n)}\)，我們可以把積分變數變換 \(y = x+n\)： \[ c_k = \sum_{n=-\infty}^{\infty} \int_{n}^{n+1} f(y) e^{-2\pi i k y} dy \] 觀察這個式子，這是把實數軸切成一段一段長度為 1 的區間，然後全部加起來。根據積分的可加性，這等於從 \(-\infty\) 積到 \(\infty\)： \[ c_k = \int_{-\infty}^{\infty} f(y) e^{-2\pi i k y} dy = \hat{f}(k) \]
第三步：代回並取值
現在我們知道 \(F(x) = \sum_{k} \hat{f}(k) e^{2\pi i k x}\)。
令 \(x=0\)，我們得到： \[ F(0) = \sum_{k=-\infty}^{\infty} \hat{f}(k) \] 回顧 \(F(x)\) 的原始定義 \(F(0) = \sum_{n} f(n)\)，兩式合併即得證： \[ \sum_{n=-\infty}^{\infty} f(n) = \sum_{k=-\infty}^{\infty} \hat{f}(k) \]
Q.E.D.