10 傅里叶变换与 Poisson 求和公式 整理日期：2026-10-16。02 基本区域、格行列式与正交化 、07 对偶格与对偶基 、09 高斯函数与离散高斯分布 。
设 Λ = L ( B ) ⊆ R n \Lambda=\mathcal L(B)\subseteq\mathbb R^n Λ = L ( B ) ⊆ R n Λ ∗ = B − T Z n \Lambda^*=B^{-\mathsf T}\mathbb Z^n Λ ∗ = B − T Z n
以下可取 f f f
1. 傅里叶变换
采用如下约定：
f ^ ( y ) = ∫ R n f ( x ) e − 2 π i ⟨ x , y ⟩ d x , y ∈ R n . \boxed{
\widehat f(y)
=
\int_{\mathbb R^n}
f(x)e^{-2\pi i\langle x,y\rangle}\,dx,
\qquad y\in\mathbb R^n.
} f ( y ) = ∫ R n f ( x ) e − 2 π i ⟨ x , y ⟩ d x , y ∈ R n . 其中 i 2 = − 1 i^2=-1 i 2 = − 1 y y y
f ^ ( 0 ) = ∫ R n f ( x ) d x , \widehat f(0)=\int_{\mathbb R^n}f(x)\,dx, f ( 0 ) = ∫ R n f ( x ) d x , 即零频值等于函数的总积分。
后面用到两个性质：
g ( x ) = f ( x − c ) ⟹ g ^ ( y ) = e − 2 π i ⟨ c , y ⟩ f ^ ( y ) ; g(x)=f(x-c)
\quad\Longrightarrow\quad
\widehat g(y)
=
e^{-2\pi i\langle c,y\rangle}\widehat f(y); g ( x ) = f ( x − c ) ⟹ g ( y ) = e − 2 π i ⟨ c , y ⟩ f ( y ) ; h ( x ) = f ( x / s ) , s > 0 ⟹ h ^ ( y ) = s n f ^ ( s y ) . h(x)=f(x/s),\quad s>0
\quad\Longrightarrow\quad
\widehat h(y)=s^n\widehat f(sy). h ( x ) = f ( x / s ) , s > 0 ⟹ h ( y ) = s n f ( sy ) . 平移引入相位因子；空间中的伸缩对应频率尺度的反向变化。上述约定与性质见 Regev《Lecture 9: Fourier Transform》，Fall 2004，PDF 第 3 页，Definition 3 与 Theorem 3 。
2. 高斯函数的傅里叶变换
沿用第九篇的记号：
ρ ( x ) = e − π ∥ x ∥ 2 , ρ s ( x ) = e − π ∥ x ∥ 2 / s 2 . \rho(x)=e^{-\pi\|x\|^2},
\qquad
\rho_s(x)=e^{-\pi\|x\|^2/s^2}. ρ ( x ) = e − π ∥ x ∥ 2 , ρ s ( x ) = e − π ∥ x ∥ 2 / s 2 . 高斯函数的一个关键性质是
ρ ^ = ρ . \widehat\rho=\rho. ρ = ρ . 一维情形可以用简短推导说明：对 ρ ^ ( y ) \widehat\rho(y) ρ ( y )
d d y ρ ^ ( y ) = − 2 π y ρ ^ ( y ) , ρ ^ ( 0 ) = 1. \frac{d}{dy}\widehat\rho(y)
=
-2\pi y\,\widehat\rho(y),
\qquad
\widehat\rho(0)=1. d y d ρ ( y ) = − 2 π y ρ ( y ) , ρ ( 0 ) = 1. 因此 ρ ^ ( y ) = e − π y 2 \widehat\rho(y)=e^{-\pi y^2} ρ ( y ) = e − π y 2 n n n
再应用伸缩性质，得到
ρ s ^ ( y ) = s n e − π s 2 ∥ y ∥ 2 = s n ρ 1 / s ( y ) . \boxed{
\widehat{\rho_s}(y)
=
s^n e^{-\pi s^2\|y\|^2}
=
s^n\rho_{1/s}(y).
} ρ s ( y ) = s n e − π s 2 ∥ y ∥ 2 = s n ρ 1/ s ( y ) . 所以，高斯函数经过傅里叶变换后仍是高斯函数，尺度由 s s s 1 / s 1/s 1/ s s n s^n s n Regev，PDF 第 3 页，Example 3 。
对于第九篇的归一化密度 f s , 0 = ρ s / s n f_{s,0}=\rho_s/s^n f s , 0 = ρ s / s n f ^ s , 0 = ρ 1 / s \widehat f_{s,0}=\rho_{1/s} f s , 0 = ρ 1/ s
3. 为什么频率落在对偶格上
考虑一个基本振荡函数
χ y ( t ) = e 2 π i ⟨ t , y ⟩ . \chi_y(t)=e^{2\pi i\langle t,y\rangle}. χ y ( t ) = e 2 π i ⟨ t , y ⟩ . 要求它沿任意格向量 v ∈ Λ v\in\Lambda v ∈ Λ
χ y ( t + v ) = χ y ( t ) , \chi_y(t+v)=\chi_y(t), χ y ( t + v ) = χ y ( t ) , 等价于
e 2 π i ⟨ v , y ⟩ = 1 ⟺ ⟨ v , y ⟩ ∈ Z . e^{2\pi i\langle v,y\rangle}=1
\quad\Longleftrightarrow\quad
\langle v,y\rangle\in\mathbb Z. e 2 π i ⟨ v , y ⟩ = 1 ⟺ ⟨ v , y ⟩ ∈ Z . 这个条件对所有 v ∈ Λ v\in\Lambda v ∈ Λ y ∈ Λ ∗ y\in\Lambda^* y ∈ Λ ∗
因此，与格周期相容的频率，正好组成对偶格。
对于一般函数 f f f R n \mathbb R^n R n
4. Poisson 求和公式
对满秩格 Λ \Lambda Λ
∑ x ∈ Λ f ( x ) = 1 det ( Λ ) ∑ y ∈ Λ ∗ f ^ ( y ) . \boxed{
\sum_{x\in\Lambda}f(x)
=
\frac{1}{\det(\Lambda)}
\sum_{y\in\Lambda^*}\widehat f(y).
} x ∈ Λ ∑ f ( x ) = det ( Λ ) 1 y ∈ Λ ∗ ∑ f ( y ) . 它把原格上的函数值求和，转化为对偶格上的傅里叶变换值求和。系数也可写为
det ( Λ ∗ ) = 1 / det ( Λ ) \det(\Lambda^*)=1/\det(\Lambda) det ( Λ ∗ ) = 1/ det ( Λ ) Micciancio《The Gaussians Distribution》，Fall 2019，§4，PDF 第 7–8 页，Theorem 5 与 Corollary 6 。
证明的关键是将 f f f
F ( t ) = ∑ x ∈ Λ f ( t + x ) . F(t)=\sum_{x\in\Lambda}f(t+x). F ( t ) = x ∈ Λ ∑ f ( t + x ) . 此时 F ( t + v ) = F ( t ) F(t+v)=F(t) F ( t + v ) = F ( t ) Λ ∗ \Lambda^* Λ ∗ y ∈ Λ ∗ y\in\Lambda^* y ∈ Λ ∗ a y a_y a y
a y = 1 det ( Λ ) ∫ P ( B ) F ( t ) e − 2 π i ⟨ t , y ⟩ d t = 1 det ( Λ ) ∫ R n f ( u ) e − 2 π i ⟨ u , y ⟩ d u = f ^ ( y ) det ( Λ ) . \begin{aligned}
a_y
&=
\frac{1}{\det(\Lambda)}
\int_{\mathcal P(B)}
F(t)e^{-2\pi i\langle t,y\rangle}\,dt\\
&=
\frac{1}{\det(\Lambda)}
\int_{\mathbb R^n}
f(u)e^{-2\pi i\langle u,y\rangle}\,du\\
&=
\frac{\widehat f(y)}{\det(\Lambda)}.
\end{aligned} a y = det ( Λ ) 1 ∫ P ( B ) F ( t ) e − 2 π i ⟨ t , y ⟩ d t = det ( Λ ) 1 ∫ R n f ( u ) e − 2 π i ⟨ u , y ⟩ d u = det ( Λ ) f ( y ) . 第二步使用了两个事实：基本区域的格平移覆盖整个空间；对偶条件保证平移格向量时相位不变。
于是
F ( t ) = 1 det ( Λ ) ∑ y ∈ Λ ∗ f ^ ( y ) e 2 π i ⟨ t , y ⟩ . F(t)
=
\frac{1}{\det(\Lambda)}
\sum_{y\in\Lambda^*}
\widehat f(y)e^{2\pi i\langle t,y\rangle}. F ( t ) = det ( Λ ) 1 y ∈ Λ ∗ ∑ f ( y ) e 2 π i ⟨ t , y ⟩ . 令 t = 0 t=0 t = 0
5. 应用于格上的高斯总质量
将 f = ρ s f=\rho_s f = ρ s
ρ s ( Λ ) = s n det ( Λ ) ρ 1 / s ( Λ ∗ ) . \boxed{
\rho_s(\Lambda)
=
\frac{s^n}{\det(\Lambda)}
\rho_{1/s}(\Lambda^*).
} ρ s ( Λ ) = det ( Λ ) s n ρ 1/ s ( Λ ∗ ) . 这里 ρ s ( A ) = ∑ x ∈ A ρ s ( x ) \rho_s(A)=\sum_{x\in A}\rho_s(x) ρ s ( A ) = ∑ x ∈ A ρ s ( x )
ρ s ( Λ ) = s n det ( Λ ) ( 1 + ∑ y ∈ Λ ∗ y ≠ 0 e − π s 2 ∥ y ∥ 2 ) . \rho_s(\Lambda)
=
\frac{s^n}{\det(\Lambda)}
\left(
1+
\sum_{\substack{y\in\Lambda^*\\y\ne0}}
e^{-\pi s^2\|y\|^2}
\right). ρ s ( Λ ) = det ( Λ ) s n 1 + y ∈ Λ ∗ y = 0 ∑ e − π s 2 ∥ y ∥ 2 . 这是一个精确等式。零频项贡献 s n / det ( Λ ) s^n/\det(\Lambda) s n / det ( Λ )
当非零项的总和足够小时，就有
ρ s ( Λ ) ≈ s n det ( Λ ) . \rho_s(\Lambda)\approx\frac{s^n}{\det(\Lambda)}. ρ s ( Λ ) ≈ det ( Λ ) s n . 这个主项也符合体积直觉：高斯函数的总积分为 s n s^n s n 1 / det ( Λ ) 1/\det(\Lambda) 1/ det ( Λ )
6. 平移中心与下一篇的联系
第九篇定义了 ρ s , c ( x ) = ρ s ( x − c ) \rho_{s,c}(x)=\rho_s(x-c) ρ s , c ( x ) = ρ s ( x − c )
ρ s , c ( Λ ) = s n det ( Λ ) ∑ y ∈ Λ ∗ ρ 1 / s ( y ) e − 2 π i ⟨ c , y ⟩ . \rho_{s,c}(\Lambda)
=
\frac{s^n}{\det(\Lambda)}
\sum_{y\in\Lambda^*}
\rho_{1/s}(y)e^{-2\pi i\langle c,y\rangle}. ρ s , c ( Λ ) = det ( Λ ) s n y ∈ Λ ∗ ∑ ρ 1/ s ( y ) e − 2 π i ⟨ c , y ⟩ . 去掉零频项，再利用相位因子的模为 1 1 1
∣ det ( Λ ) s n ρ s , c ( Λ ) − 1 ∣ ≤ ρ 1 / s ( Λ ∗ ∖ { 0 } ) . \boxed{
\left|
\frac{\det(\Lambda)}{s^n}\rho_{s,c}(\Lambda)-1
\right|
\le
\rho_{1/s}\!\left(\Lambda^*\setminus\{0\}\right).
} s n det ( Λ ) ρ s , c ( Λ ) − 1 ≤ ρ 1/ s ( Λ ∗ ∖ { 0 } ) . 右侧与中心 c c c ε \varepsilon ε s n / det ( Λ ) s^n/\det(\Lambda) s n / det ( Λ ) ε \varepsilon ε
这种展开与估计见 Regev 的最坏情况到平均情况归约讲义，§2，PDF 第 3–4 页，Lemma 5 的证明 。
下一篇将通过平滑参数 描述：为了让非零对偶向量的高斯总质量足够小，尺度 s s s
引用此笔记
