2025-11-29T01:31:19.347032

A note on the Littlewood-Offord problem for discrete log-concave distributions

Marsiglietti, Melbourne

We present an extension of the famous Littlewood-Offord problem when Bernoulli distributions are replaced with discrete log-concave distributions. A variant of the Littlewood-Offord problem for arithmetic progressions, as well as an entropic version, is also discussed. Along the way, we recover and extend a result of Madiman and Woo (2015) on the entropy power inequality for discrete uniform distributions.

academic

A note on the Littlewood-Offord problem for discrete log-concave distributions

基本信息

论文ID: 2510.25869
标题: A note on the Littlewood-Offord problem for discrete log-concave distributions
作者: Arnaud Marsiglietti (University of Florida), James Melbourne (Centro de Investigaciónes en Matemáticas)
分类: math.PR (Probability Theory)
提交时间: 2025年10月29日
论文链接: https://arxiv.org/abs/2510.25869

摘要

本文将著名的Littlewood-Offord问题从Bernoulli分布推广到离散对数凹分布。文章讨论了算术级数的Littlewood-Offord问题变体以及熵版本。在此过程中，作者恢复并扩展了Madiman和Woo (2015)关于离散均匀分布的熵功率不等式的结果。

研究背景与动机

问题背景

Littlewood-Offord问题是概率论和组合数学中的经典问题。给定向量 $a = (a_1, \ldots, a_n) \in (\mathbb{R} \setminus \{0\})^n$ 和独立的Rademacher随机变量 $X_1, \ldots, X_n$ （即 $P(X_k = \pm 1) = 1/2$ ），问题是估计：

$\sup_{x \in \mathbb{R}} P(a_1X_1 + \cdots + a_nX_n = x)$

经典的Littlewood-Offord和Erdős结果表明该上界为 $O(1/\sqrt{n})$ 。

研究动机

理论扩展需求：经典结果主要针对参数为1/2的Bernoulli分布，Fox等人(2018)提出是否可以将问题扩展到任意参数的Bernoulli分布
分布类推广：离散对数凹分布是一个重要的分布类，包括均匀分布、Bernoulli分布、二项分布、Poisson分布、几何分布等
实际应用：该问题与反集中不等式、组合数论等领域密切相关
理论统一：试图为更广泛的分布类提供统一的理论框架

现有方法局限性

大多数变体主要处理参数为1/2的Bernoulli分布
对于任意参数的Bernoulli分布，直到Melbourne等人(2023)才给出完整解答
缺乏对整个离散对数凹分布类的系统性结果

核心贡献

主要定理推广：将Littlewood-Offord问题扩展到所有有限支撑的离散对数凹分布（定理1.1），证明了： $\sup_{a \in (\mathbb{R}\setminus\{0})^n} \sup_{x \in \mathbb{R}} P(a \cdot X = x) \leq \frac{1}{\sqrt{1 + c\sum_{k=1}^n \text{Var}(X_k)}}$ 其中 $c=1$ ，对于关于某点对称的分布可取 $c=2$
熵版本：提出了Littlewood-Offord问题的Rényi熵功率版本（定理1.2），建立了熵功率的下界
算术级数变体：解决了算术级数上的Littlewood-Offord问题（定理1.3），给出了 $P(a \cdot X \in A_{l,m}(x))$ 的上界
熵功率不等式：恢复并扩展了Madiman和Woo关于离散均匀分布的熵功率不等式（定理1.4）
最优性分析：证明了所得界在常数意义下是紧的

方法详解

任务定义

给定独立的离散对数凹随机变量 $X_1, \ldots, X_n$ 和系数 $a = (a_1, \ldots, a_n) \in (\mathbb{R} \setminus \{0\})^n$ ，目标是找到：

点概率上界： $\sup_{a,x} P(a \cdot X = x)$ 的最优上界
熵功率下界： $\inf_a N_\alpha(a \cdot X)$ 的最优下界
算术级数概率： $\sup_x P(a \cdot X \in A_{l,m}(x))$ 的上界

其中 $A_{l,m}(x) = \{x + mj\}_{j=1}^l$ 是算术级数。

核心技术框架

1. 主控原理（Majorization Theory）

论文的关键技术工具是主控理论。对于概率分布 $p, q$ ，若： $\sum_{i=1}^k q_i \geq \sum_{i=1}^k p_i, \quad \forall k$ 则称 $p$ 被 $q$ 主控，记为 $p \prec q$ 。

关键引理2.2：若 $Y$ 是有限值随机变量， $f$ 是确定性函数，则 $Y \prec f(Y)$ 。

2. 压缩重排（Squeezed Rearrangement）

对于整数值随机变量 $X$ ，定义其压缩重排 $X^\#$ ：将支撑集压缩到连续整数上，保持概率质量函数值的顺序。

定理2.3（关键结果）：若 $X_1, \ldots, X_n$ 独立且 $X_1^\#, \ldots, X_n^\#$ 对数凹，则： $X_1 + \cdots + X_n \prec X_1^\# + \cdots + X_n^\#$

3. 符号约化（Sign Reduction）

定理3.1（核心技术定理）：对于系数 $a_i \in \mathbb{R}\setminus\{0\}$ 和独立对数凹整数值随机变量 $X_i$ ，存在符号 $v_i \in \{\pm 1\}$ 使得： $a \cdot X \prec v \cdot X$

证明思路：

首先通过线性变换 $T: \mathbb{R} \to \mathbb{Q}$ 将实系数约化为整系数
利用压缩重排， $(T(a_i)X_i)^\# = v_i X_i$ ，其中 $v_i = \text{sign}(T(a_i))$
应用定理2.3完成约化

模型架构

论文的证明架构可概括为以下层次结构：

离散对数凹分布 → 符号约化 → Bernoulli型问题
        ↓              ↓              ↓
   主控理论 ← Schur凹性 ← 方差界/熵界
        ↓
   最终不等式

定理1.1的证明（主要结果）

约化步骤：由定理3.1，对任意 $a$ ，存在符号 $v$ 使得 $a \cdot X \prec v \cdot X$
应用已知界：利用定理2.1（Aravinda和Bobkov等人的结果）： $M(X) \leq \frac{1}{\sqrt{1 + \text{Var}(X)}}$ 对于对数凹随机变量
方差计算： $\text{Var}(v \cdot X) = \sum_{i=1}^n \text{Var}(X_i)$ （因为 $v_i = \pm 1$ ）
结论： $M(a \cdot X) \leq M(v \cdot X) \leq \frac{1}{\sqrt{1 + \sum_{k=1}^n \text{Var}(X_k)}}$

定理1.2的证明（熵版本）

Schur凹性：Rényi熵 $H_\alpha$ 是Schur凹的
主控传递：由定理3.1， $N_\alpha(a \cdot X) \geq N_\alpha(v \cdot X)$
熵-方差关系：利用 $N_\alpha(X) \geq 1 + \text{Var}(X)$ （由定理2.1和单调性）
特殊情况优化：当 $1 < \alpha \leq 2$ 时，可用更强的界 $N_\alpha(X) \geq 1 + 4\text{Var}(X)$

技术创新点

统一框架：通过主控理论和符号约化，将一般离散对数凹分布问题统一约化为符号问题
压缩重排技巧：巧妙利用压缩重排将任意系数问题转化为符号问题，这是关键创新
熵-概率双重视角：建立了点概率估计和熵功率估计之间的联系，通过 $M(X) = e^{-H_\infty(X)}$
算术级数处理：将算术级数问题转化为与均匀分布的卷积问题： $P(Y \in A_{l,m}(x)) = l \cdot P(Y - mU_l = x)$ 其中 $U_l$ 是 $\{1, \ldots, l\}$ 上的均匀分布
Fourier分析应用（第5节）：对Bernoulli分布，使用Hausdorff-Young不等式和Hölder不等式得到更精细的界

实验设置

注：本文是纯理论数学论文，不包含数值实验。所有结果都是严格的数学证明。

理论验证方法

紧性分析（Remark 3.2）：
- 下界： $\frac{1}{\sqrt{1 + 12\sum \text{Var}(X_k)}}$
- 上界： $\frac{1}{\sqrt{1 + \sum \text{Var}(X_k)}}$
- 说明常数因子的最优性
特殊情况恢复：
- Rademacher分布：恢复经典的 $O(1/\sqrt{n})$ 界
- Bernoulli分布：恢复Melbourne等人(2023)的结果
- 均匀分布：恢复并改进Madiman-Woo (2015)的结果

比较基准

论文与以下已有结果进行比较：

经典Littlewood-Offord-Erdős界： $\sup P(a \cdot X = x) \leq \frac{1}{2^n}\binom{n}{\lfloor n/2 \rfloor} = O(1/\sqrt{n})$
Melbourne-Madiman-Roberto (2023)：对Bernoulli分布， $c=2$
Aravinda (2024) 和 Bobkov-Marsiglietti-Melbourne (2022)：对数凹分布的方差-集中函数关系

实验结果

主要理论结果

结果1：一般对数凹分布（定理1.1）

对于独立有限支撑的离散对数凹随机变量： $\sup_{a,x} P(a \cdot X = x) \leq \frac{1}{\sqrt{1 + \sum_{k=1}^n \text{Var}(X_k)}}$

推论3.3：对于i.i.d. Bernoulli( $p$ )分布： $\sup_{a,x} P(a \cdot X = x) \leq \frac{1}{\sqrt{1 + np(1-p)}}$

结果2：对称分布改进

当随机变量关于某点对称时，常数可改进为 $c=2$ ： $\sup_{a,x} P(a \cdot X = x) \leq \frac{1}{\sqrt{1 + 2\sum_{k=1}^n \text{Var}(X_k)}}$

结果3：熵功率界（定理1.2）

对于 $\alpha \in [0, +\infty]$ ： $\inf_a N_\alpha(a \cdot X) \geq 1 + \sum_{k=1}^n \text{Var}(X_k)$

特别地，当 $1 < \alpha \leq 2$ 时可取 $c=4$ 。

结果4：算术级数（定理1.3）

$\sup_x P(a \cdot X \in A_{l,m}(x)) \leq \frac{l}{\sqrt{1 + \sum_{k=1}^n \text{Var}(X_k) + \frac{l^2-1}{12}}}$

特殊情况分析

案例1：两点分布（命题3.4）

对于 $X_i \in \{x_i, x_{i+1}\}$ ， $x_i, x_{i+1} \in \mathbb{Z}$ ： $\sup_a M(a \cdot X) \leq \frac{1}{\sqrt{1 + 2\sum_{i=1}^n \frac{\text{Var}(X_i)}{(x_i - x_{i+1})^2}}}$

这统一了Erdős的结果和Bernoulli分布的结果。

案例2：均匀分布的熵功率不等式（定理1.4）

对于独立的整数集上均匀分布 $U_1, \ldots, U_n$ ，当 $\alpha \in [0, 2]$ ： $N_\alpha\left(\sum_{k=1}^n U_k\right) \geq \sum_{k=1}^n N_\alpha(U_k) - (n-1)$

这扩展了Madiman-Woo (2015)的 $\alpha=1, n=2$ 情况。

案例3：Bernoulli分布的精细化（第5.1节）

使用Fourier分析，对于Bernoulli分布和算术级数： $\sup_x P(a \cdot X \in A_l) \leq \frac{(2A)^{1/p} l}{\sqrt{1 + 2\sum_{k=1}^n \text{Var}(X_k) + \frac{l^2-1}{12} \cdot 4\pi A^2}}$

其中 $A$ 由隐式方程确定。Remark 5.1 指出当 $l=2$ 时， $4\pi A^2 \geq 1$ ，因此该界总是优于定理1.3。

紧性分析

下界构造（Remark 3.2）：通过已知的上界 $N_\alpha(X) \leq 1 + \frac{4(3\alpha-1)}{\alpha-1}\text{Var}(X)$ （对 $\alpha > 1$ ），得到： $\inf_a N_\alpha(a \cdot X) \leq 1 + \frac{4(3\alpha-1)}{\alpha-1} \sum_{i=1}^n \text{Var}(X_i)$

这表明定理1.2的界在常数意义下是最优的。

理论发现总结

方差的核心作用：所有界都依赖于方差和 $\sum \text{Var}(X_k)$ ，这是自然且最优的
对称性改进：对称分布可获得常数2倍的改进
熵-概率统一：通过 $M(X) = e^{-H_\infty(X)}$ ，点概率问题是熵问题的特例
主控理论的威力：符号约化技术将复杂问题优雅地简化

结论与讨论

主要结论

核心定理：成功将Littlewood-Offord问题推广到所有有限支撑的离散对数凹分布，界为： $\frac{1}{\sqrt{1 + c\sum \text{Var}(X_k)}}$ 其中 $c \in \{1, 2\}$ 取决于对称性
方法论贡献：建立了符号约化技术，这是处理一般系数问题的关键工具
理论统一：通过Rényi熵功率框架，统一了点概率估计、熵不等式和算术级数问题
已有结果恢复：作为特例恢复了多个已知重要结果

局限性

常数因子：
- 定理1.1中的常数 $c=1$ 可能不是最优的
- 对于特定分布（如Bernoulli），已知 $c=2$ 是可达的
- 常数的紧性分析表明存在改进空间（下界涉及常数12）
对称性条件：
- 对称分布可获得 $c=2$ 的改进，但非对称情况只能取 $c=1$
- 对于特定的非对称分布，可能存在更好的界
有限支撑假设：
- 所有结果都要求随机变量有限支撑
- 对于无限支撑的对数凹分布（如Poisson），需要额外的技术处理
算术级数结果：
- 定理1.3的界在 $l$ 较大时可能不够精细
- Remark 5.1指出对Bernoulli分布需要 $p \geq 2$ 的条件限制了适用性
Rényi熵参数范围：
- 定理1.2对不同的 $\alpha$ 范围给出不同的常数
- 当 $\alpha > 2$ 时，常数退化为 $c=1$