On the counting problem in inverse Littlewood–Offord theory
On the counting problem in inverse Littlewood–Offord theory
复制标题
关于逆Littlewood-Offford理论中的计数问题
DOI：
10.1112/jlms.12409
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Wojciech Samotij
中科院分区：
文献类型：
--
作者：
Asaf Ferber;Vishesh Jain;K. Luh;Wojciech Samotij
令 ε1,…,εn 为独立且同分布的 Rademacher 随机变量，取值 ±1，每个概率为 1/2。给定一个整数向量 a=(a1,…,an) ，其集中概率为数量 ρ(a):=supx∈ZPr(ε1a1+⋯+εnan=x) 。 Littlewood-Offford 问题要求在 a 的各种假设下确定 ρ(a) 的界限，而由 Tai 和 Vu 提出的逆 Littlewood-Offford 问题则要求对 ρ(a) 较大的所有向量 a 进行表征。在本文中，我们研究相关的计数问题：属于指定集合的整数向量 a 有多少个具有较大的 ρ(a) ？我们研究的动机是，在典型应用中，逆Littlewood-Offford定理仅用于获得此类计数估计。对于这个问题，使用更直接的方法，我们获得的界限比使用 Tai 和 Vu 以及 Nguyen 和 Vu 的逆 Littlewood-Offord 定理获得的界限要好得多。此外，我们开发了一个框架，用于利用我们的计数结果推导随机离散矩阵奇点概率的上限。为了说明这些方法，我们提出了以下两个模型的奇点概率的第一个“指数类型”（即，对于某个正常数 c 的 exp(−cnc) ）上限：（i）稠密有符号随机正则有向图的邻接矩阵，其中先前最著名的边界是 O(n−1/4) ，这是由 Cook 提出的； (ii) 稠密行正则 {0,1} 矩阵，对于任何常数 C>0 ，先前最著名的边界是 OC(n−C) ，这是由 Nguyen 提出的。
Let ε1,…,εn be independent and identically distributed Rademacher random variables taking values ±1 with probability 1/2 each. Given an integer vector a=(a1,…,an) , its concentration probability is the quantity ρ(a):=supx∈ZPr(ε1a1+⋯+εnan=x) . The Littlewood–Offord problem asks for bounds on ρ(a) under various hypotheses on a , whereas the inverse Littlewood–Offord problem, posed by Tao and Vu, asks for a characterization of all vectors a for which ρ(a) is large. In this paper, we study the associated counting problem: How many integer vectors a belonging to a specified set have large ρ(a) ? The motivation for our study is that in typical applications, the inverse Littlewood–Offord theorems are only used to obtain such counting estimates. Using a more direct approach, we obtain significantly better bounds for this problem than those obtained using the inverse Littlewood–Offord theorems of Tao and Vu and of Nguyen and Vu. Moreover, we develop a framework for deriving upper bounds on the probability of singularity of random discrete matrices that utilizes our counting result. To illustrate the methods, we present the first ‘exponential‐type’ (that is, exp(−cnc) for some positive constant c ) upper bounds on the singularity probability for the following two models: (i) adjacency matrices of dense signed random regular digraphs, for which the previous best‐known bound is O(n−1/4) , due to Cook; and (ii) dense row‐regular {0,1} ‐matrices, for which the previous best‐known bound is OC(n−C) for any constant C>0 , due to Nguyen.
随机积分矩阵：满射性和 cokernel 的普遍性
影响因子：
3.1
作者：
Nguyen, Hoi H.;Wood, Melanie Matchett
通讯作者：
Wood, Melanie Matchett