从近似度到近似秩下届的探索

### 从近似度到近似秩下届的探索 在许多数学和计算机科学的研究中，我们常常需要对函数进行近似处理。而近似度、近似权重和近似秩是衡量函数近似性质的重要指标。本文将深入探讨如何从函数的近似度推导出近似权重的下界，再从近似权重的下界得到近似秩的下界。 #### 1. 从高近似度到高近似权重 首先，我们定义一个 3 位索引小工具 `idx`： - 定义 `idx: { - 1,1}^2 X { - 1,1} -> { - 1,1}`，通过 `idx(x, y, z) = (z ∧ x) ∨ (z ∧ y)`。即如果 `z = -1`，则 `idx` 输出 `x`；如果 `z = +1`，则 `idx` 输出 `y`。 对于任意实值函数 `p: { - 1,1}^n -> R`，`weight(p)` 是 `p` 的傅里叶系数的 `l1` 范数。 有如下引理： - **引理 10.9**：设 `f: { - 1,1}^n -> { - 1,1}` 是一个布尔函数，并且假设 `f` 满足 `deg_ε(f) > d`。那么 `weight_{ε - 2^{-d/2}}(f ∘ idx) > 2^{d/2}`。 ##### 最优近似技术 定理 10.9 表明，构造 `f ∘ idx` 的低权重 `ε` - 近似的以下方法本质上是最优的： 1. 取 `f` 的最低度 `ε` - 近似多项式 `p`。 2. 设 `q` 是精确计算 `idx` 的多线性多项式。 3. 考虑通过组合 `p` 和 `q` 得到的多项式。 显然，`p ∘ q` 是 `f ∘ idx` 的 `ε` - 近似，并且由于 `idx` 是仅作用于 3 位的布尔函数，`weight(q) < 3`。因此，`weight(p ∘ q) < weight(p) • 3^{deg(p)}`。如果 `weight(p) < 2^{O(d)}`，定理 10.9 证明了在指数上达到常数因子的匹配下界，并且在误差上有一个附加的 `2^{d/2}` 损失。 ##### 近似权重的对偶形式 在证明定理 10.9 之前，我们引入近似权重的对偶形式。一个对偶多项式 `φ: { - 1,1}^n -> R` 表明 `deg_ε(f) > d` 必须满足： 1. 与 `f` 是 `ε` - 相关的，即 `(f, φ) > ε • ||φ||_1`。 2. 与度至多为 `d` 的多项式不相关。 为了证明 `weight_{ε - 2^{-d/2}}(f) > 2^{d/2}`，对偶见证只需要满足第一个条件，而第二个条件变为：`φ` 与所有奇偶校验（无论度如何）的相关性至多为 `2^{-d}`。 具体来说，固定一个感兴趣的函数 `f: { - 1,1}^n -> { - 1,1}` 和一个权重界 `W`。任何权重至多为 `W` 的多项式（无论其度如何）在奇偶校验基上对 `f` 进行近似的最小误差是多少？答案是以下线性规划的值： ```plaintext min_{p,ε} ε s.t. |p(x) - f(x)| < ε for all x ∈ { - 1,1}^n weight(p) < W ``` 取对偶得到： ```plaintext max_{φ} - W • γ + ∑_{x∈{ - 1,1}^n} φ(x)f(x) s.t. ∑_{x∈{ - 1,1}^n} |φ(x)| = 1 |∑_{x∈{ - 1,1}^n} φ(x)χ_S(x)| ≤ γ for all parity functions χ_S ``` 假设 `ε = e` 并设 `M = max_{S⊆[n]} |∑_{x∈{ - 1,1}^n} φ(x)χ_S(x)|`。通过设置 `γ = M`，我们得到上述对偶规划的一个可行解，目标值为 `e - W • M`，从而证明 `deg_{ε - W • M}(f) > W`。 ##### 定理 10.9 的证明 设 `φ` 是 `deg_ε(f) > d` 的对偶见证。我们可以构建 `f ∘ idx` 的对偶见证 `ν` 作为 `φ` 与 `idx` 的合适对偶见证 `ψ` 的对偶块组合。 - 设 `ψ: { - 1,1}^3 -> R` 是 `deg_±(idx) > 1` 的自然对偶见证，即 `ψ` 是 `h` 适当缩放以使其 `l1` 范数为 1。 - 定义 `ν := φ * ψ`。具体来说，如果我们将 `f ∘ idx` 的输入写为 `(x, y, z) ∈ ({ - 1,1}^n)^3`，则 `ν(x, y, z) = 4^{-n} • (φ ∘ idx)(x, y, z)`。 通过定理 7.3 可知 `||ν||_1 = 1`，定理 7.6 表明 `(ν, f ∘ idx) = (φ, f) > ε`。还需要证明对于所有 `S ⊆ [3n]`，`∑_{(x,y,z)∈{ - 1,1}^{3n}} ν(x, y, z)χ_S(x, y, z) < 2^{-d}`。 通过明确写出 `ν` 的傅里叶系数与 `φ` 的傅里叶系数的关系，我们可以证明上述不等式。 ##### 对 `idx` 性质的讨论 在定理 10.9 的证明中，我们利用了 3 位索引小工具 `idx` 的两个性质： 1. **平衡性**：`idx` 的度为 0 的傅里叶系数为 0，这确保了 `idx`（适当缩放以使其 `l1` 范数为 1）是自对偶的。 2. **傅里叶系数的有界性**：`idx` 的所有傅里叶系数的幅度至多为 `1/2`，这使得 `φ * ψ` 的傅里叶系数按指数级小，满足近似权重对偶见证的