11 平滑参数与格上的高斯质量 整理日期：2026-10-16。09 高斯函数与离散高斯分布 、10 傅里叶变换与 Poisson 求和公式 。
设 Λ = L ( B ) ⊆ R n \Lambda=\mathcal L(B)\subseteq\mathbb R^n Λ = L ( B ) ⊆ R n 0 < ε < 1 0<\varepsilon<1 0 < ε < 1
ρ s , c ( x ) = e − π ∥ x − c ∥ 2 / s 2 , ρ s = ρ s , 0 . \rho_{s,c}(x)=e^{-\pi\|x-c\|^2/s^2},
\qquad
\rho_s=\rho_{s,0}. ρ s , c ( x ) = e − π ∥ x − c ∥ 2 / s 2 , ρ s = ρ s , 0 . 1. 平滑参数的定义
格 Λ \Lambda Λ ε \varepsilon ε
η ε ( Λ ) = min { s > 0 : ρ 1 / s ( Λ ∗ ∖ { 0 } ) ≤ ε } . \boxed{
\eta_\varepsilon(\Lambda)
=
\min\left\{
s>0:
\rho_{1/s}\!\left(\Lambda^*\setminus\{0\}\right)
\le\varepsilon
\right\}.
} η ε ( Λ ) = min { s > 0 : ρ 1/ s ( Λ ∗ ∖ { 0 } ) ≤ ε } . 其中
ρ 1 / s ( Λ ∗ ∖ { 0 } ) = ∑ y ∈ Λ ∗ y ≠ 0 e − π s 2 ∥ y ∥ 2 . \rho_{1/s}\!\left(\Lambda^*\setminus\{0\}\right)
=
\sum_{\substack{y\in\Lambda^*\\y\ne0}}
e^{-\pi s^2\|y\|^2}. ρ 1/ s ( Λ ∗ ∖ { 0 } ) = y ∈ Λ ∗ y = 0 ∑ e − π s 2 ∥ y ∥ 2 . 因此，η ε ( Λ ) \eta_\varepsilon(\Lambda) η ε ( Λ ) 所有非零对偶向量的高斯总质量 压到 ε \varepsilon ε s s s
随着 s s s 1 / s 1/s 1/ s Regev，Fall 2004，最坏情况到平均情况归约讲义，§2，PDF 第 4 页，Definition 6 。
由于零向量贡献恒为 1 1 1
ρ 1 / s ( Λ ∗ ) ≤ 1 + ε . \rho_{1/s}(\Lambda^*)\le 1+\varepsilon. ρ 1/ s ( Λ ∗ ) ≤ 1 + ε . 2. 超过平滑参数后，高斯总质量近似恒定
第十篇已经得到：对任意中心 c ∈ R n c\in\mathbb R^n c ∈ R n
∣ det ( Λ ) s n ρ s , c ( Λ ) − 1 ∣ ≤ ρ 1 / s ( Λ ∗ ∖ { 0 } ) . \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 } ) . 因此，只要 s ≥ η ε ( Λ ) s\ge\eta_\varepsilon(\Lambda) s ≥ η ε ( Λ )
( 1 − ε ) s n det ( Λ ) ≤ ρ s , c ( Λ ) ≤ ( 1 + ε ) s n det ( Λ ) 对所有 c ∈ R n . \boxed{
(1-\varepsilon)\frac{s^n}{\det(\Lambda)}
\le
\rho_{s,c}(\Lambda)
\le
(1+\varepsilon)\frac{s^n}{\det(\Lambda)}
\qquad
\text{对所有 }c\in\mathbb R^n.
} ( 1 − ε ) det ( Λ ) s n ≤ ρ s , c ( Λ ) ≤ ( 1 + ε ) det ( Λ ) s n 对所有 c ∈ R n . 这是对所有中心同时成立的相对误差界 。其主项为
s n det ( Λ ) = 高斯函数的总积分 × 格点的平均密度 . \frac{s^n}{\det(\Lambda)}
=
\text{高斯函数的总积分}
\times
\text{格点的平均密度}. det ( Λ ) s n = 高斯函数的总积分 × 格点的平均密度 . 当 c = 0 c=0 c = 0 ε \varepsilon ε
对离散高斯
D Λ , s , c ( x ) = ρ s , c ( x ) ρ s , c ( Λ ) D_{\Lambda,s,c}(x)
=
\frac{\rho_{s,c}(x)}{\rho_{s,c}(\Lambda)} D Λ , s , c ( x ) = ρ s , c ( Λ ) ρ s , c ( x ) 而言，这意味着其归一化常数可以统一估计为 s n / det ( Λ ) s^n/\det(\Lambda) s n / det ( Λ )
这一质量估计也可由 Micciancio《The Gaussians Distribution》，Fall 2019，§6，PDF 第 10–11 页，Lemma 15 通过缩放得到。
3. 为什么称为“平滑”
考虑连续高斯随机变量 X X X
f s , 0 ( x ) = ρ s ( x ) s n . f_{s,0}(x)=\frac{\rho_s(x)}{s^n}. f s , 0 ( x ) = s n ρ s ( x ) . 将 X X X
T ∈ P ( B ) = B [ 0 , 1 ) n , X − T ∈ Λ . T\in\mathcal P(B)=B[0,1)^n,
\qquad
X-T\in\Lambda. T ∈ P ( B ) = B [ 0 , 1 ) n , X − T ∈ Λ. 对 t ∈ P ( B ) t\in\mathcal P(B) t ∈ P ( B ) t + v t+v t + v v ∈ Λ v\in\Lambda v ∈ Λ t t t T T T
p s ( t ) = 1 s n ∑ v ∈ Λ ρ s ( t + v ) = ρ s , − t ( Λ ) s n . p_s(t)
=
\frac{1}{s^n}\sum_{v\in\Lambda}\rho_s(t+v)
=
\frac{\rho_{s,-t}(\Lambda)}{s^n}. p s ( t ) = s n 1 v ∈ Λ ∑ ρ s ( t + v ) = s n ρ s , − t ( Λ ) . 基本区域上的均匀分布具有密度
u ( t ) = 1 det ( Λ ) . u(t)=\frac{1}{\det(\Lambda)}. u ( t ) = det ( Λ ) 1 . 当 s ≥ η ε ( Λ ) s\ge\eta_\varepsilon(\Lambda) s ≥ η ε ( Λ )
∣ p s ( t ) − u ( t ) ∣ ≤ ε det ( Λ ) . |p_s(t)-u(t)|
\le
\frac{\varepsilon}{\det(\Lambda)}. ∣ p s ( t ) − u ( t ) ∣ ≤ det ( Λ ) ε . 于是，两者的统计距离满足
Δ ( p s , u ) = 1 2 ∫ P ( B ) ∣ p s ( t ) − u ( t ) ∣ d t ≤ ε 2 . \boxed{
\Delta(p_s,u)
=
\frac12
\int_{\mathcal P(B)}
|p_s(t)-u(t)|\,dt
\le
\frac{\varepsilon}{2}.
} Δ ( p s , u ) = 2 1 ∫ P ( B ) ∣ p s ( t ) − u ( t ) ∣ d t ≤ 2 ε . 这就是“平滑”的概率含义：足够宽的连续高斯对格取模后，在基本区域上接近均匀分布。 这一结论见 Regev，Fall 2004，§2，PDF 第 3–4 页，Lemma 5 。
这里接近均匀的是连续高斯取模后的分布。无限格上的离散高斯仍然是一个按距离赋权的离散分布。
4. 两个基本性质
误差要求越严格，平滑参数越大。
由定义直接得到
0 < ε 1 ≤ ε 2 < 1 ⟹ η ε 1 ( Λ ) ≥ η ε 2 ( Λ ) . 0<\varepsilon_1\le\varepsilon_2<1
\quad\Longrightarrow\quad
\eta_{\varepsilon_1}(\Lambda)
\ge
\eta_{\varepsilon_2}(\Lambda). 0 < ε 1 ≤ ε 2 < 1 ⟹ η ε 1 ( Λ ) ≥ η ε 2 ( Λ ) . 格整体放大，平滑参数同比放大。
对任意 a > 0 a>0 a > 0
η ε ( a Λ ) = a η ε ( Λ ) . \boxed{
\eta_\varepsilon(a\Lambda)
=
a\,\eta_\varepsilon(\Lambda).
} η ε ( a Λ ) = a η ε ( Λ ) . 这是因为 ( a Λ ) ∗ = a − 1 Λ ∗ (a\Lambda)^*=a^{-1}\Lambda^* ( a Λ ) ∗ = a − 1 Λ ∗
ρ 1 / s ( ( a Λ ) ∗ ∖ { 0 } ) = ∑ y ∈ Λ ∗ y ≠ 0 e − π ( s / a ) 2 ∥ y ∥ 2 . \rho_{1/s}\!\left((a\Lambda)^*\setminus\{0\}\right)
=
\sum_{\substack{y\in\Lambda^*\\y\ne0}}
e^{-\pi(s/a)^2\|y\|^2}. ρ 1/ s ( ( a Λ ) ∗ ∖ { 0 } ) = y ∈ Λ ∗ y = 0 ∑ e − π ( s / a ) 2 ∥ y ∥ 2 . 缩放性质也说明：平滑参数与格向量长度具有相同的尺度。
5. 与格几何参数的关系
5.1 由最短对偶向量得到下界
取最短非零对偶向量 y y y y y y − y -y − y
ρ 1 / s ( Λ ∗ ∖ { 0 } ) ≥ 2 e − π s 2 λ 1 ( Λ ∗ ) 2 . \rho_{1/s}\!\left(\Lambda^*\setminus\{0\}\right)
\ge
2e^{-\pi s^2\lambda_1(\Lambda^*)^2}. ρ 1/ s ( Λ ∗ ∖ { 0 } ) ≥ 2 e − π s 2 λ 1 ( Λ ∗ ) 2 . 要求总质量不超过 ε \varepsilon ε ε \varepsilon ε
η ε ( Λ ) ≥ 1 λ 1 ( Λ ∗ ) ln ( 2 / ε ) π . \boxed{
\eta_\varepsilon(\Lambda)
\ge
\frac{1}{\lambda_1(\Lambda^*)}
\sqrt{\frac{\ln(2/\varepsilon)}{\pi}}.
} η ε ( Λ ) ≥ λ 1 ( Λ ∗ ) 1 π ln ( 2/ ε ) . 这个下界直接来自定义。短对偶向量会阻碍其对应的非零频率衰减，因此需要更大的高斯尺度。
但仅控制最短向量的贡献还不够：平滑参数控制的是全部非零对偶向量的总质量。
5.2 由第 n n n
一个常用上界是
η ε ( Λ ) ≤ ln ( 2 n ( 1 + 1 / ε ) ) π λ n ( Λ ) . \boxed{
\eta_\varepsilon(\Lambda)
\le
\sqrt{
\frac{\ln\!\left(2n(1+1/\varepsilon)\right)}{\pi}
}
\,\lambda_n(\Lambda).
} η ε ( Λ ) ≤ π ln ( 2 n ( 1 + 1/ ε ) ) λ n ( Λ ) . 见 Micciancio–Regev《Worst-case to Average-case Reductions based on Gaussian Measures》，2005-12-14 作者稿，PDF 第 11 页，Lemma 3.3 。
这里先记结论。其证明利用 n n n λ n ( Λ ) \lambda_n(\Lambda) λ n ( Λ )
这个上界把“存在一组短的线性无关格向量”转化成了“多大的高斯尺度足以达到给定误差”。所有对数 ln \ln ln
平滑参数由此连接了三件事：对偶格上的非零高斯质量、原格上的归一化常数，以及连续高斯取模后的均匀程度。 后续进入 q q q
引用此笔记
