A nonuniform Littlewood-Offord inequality for all norms

DOI10.1016/J.DISC.2021.112366MaRDI QIDQ2022155zbMATH OpenOpenAlexFDO

Authors Kyle Luh, David Xiang

Publication date 28 April 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.12341

zbMATH Keywords

anti-concentrationLittlewood-Offord theorysmall-ball probability

Mathematics Subject Classification ID

Combinatorial probability (60C05) Inequalities; stochastic orderings (60E15)

Abstract: Let $mathbf{v}_i$ be vectors in $mathbb{R}^d$ and $varepsilo{n}_i$ be independent Rademacher random variables. Then the Littlewood-Offord problem entails finding the best upper bound for $su{p}_{mathbfxinmathbb{R}^d}mathbbP(sumvarepsilo{n}_{i}mathbf{v}_i=mathbfx)$. Generalizing the uniform bounds of Littlewood-Offord, ErdH{o}s and Kleitman, a recent result of Dzindzalieta and Juv{s}keviv{c}ius provides a non-uniform bound that is optimal in its dependence on $|mathbfx{|}_2$. In this short note, we provide a simple alternative proof of their result. Furthermore, our proof demonstrates that the bound applies to any norm on $mathbb{R}^d$, not just the $el{l}_2$ norm. This resolves a conjecture of Dzindzalieta and Juv{s}keviv{c}ius.

Recommendations

• A non-uniform Littlewood-Offord inequality
• On the Littlewood‐Offord problem for arbitrary distributions
• Resilience for the Littlewood-Offord problem
• The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi
• Non-abelian Littlewood-Offord inequalities

Cites work

• A Combinatorial Theorem on Systems of Sets
• A non-uniform Littlewood-Offord inequality
• Estimates for the concentration function of combinatorial number theory and probability
• scientific article; zbMATH DE number 3099315 (Why is no real title available?)
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• Non-abelian Littlewood-Offord inequalities
• On a combinatorial conjecture of Erdös
• On a lemma of Littlewood and Offord
• Optimal inverse Littlewood-Offord theorems
• Resilience for the Littlewood-Offord problem
• Singularity of random Bernoulli matrices
• The Littlewood-Offord problem and invertibility of random matrices
• Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property

Cited in

(6)

• The Littlewood-Offord problem for Markov chains
• A non-uniform Littlewood-Offord inequality
• The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi
• Non-abelian Littlewood-Offord inequalities
• Inverse Littlewood-Offord problems for quasi-norms
• Improved Berry-Esseen bound for Rademacher sum

This page was built for publication: A nonuniform Littlewood-Offord inequality for all norms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2022155)