An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
复制标题
二次 Littlewood-Offford 问题的代数逆定理及其在 Ramsey 图上的应用
作者：
Matthew Kwan;Lisa Sauermann
考虑二次多项式 $fleft(xi_{1},dots,xi_{n}
ight)$ 独立伯努利随机变量。关于 $f$ 对任何单一值的集中可以说什么呢？这概括了经典的 Littlewood-Offford 问题，该问题对线性多项式提出相同的问题。与线性情况一样，众所周知，$f$ 的点概率可以大到大约 $1/sqrt{n}$，但仍然知之甚少的是，如果 $f$ 具有与此界限相当的点概率，则表征 $f$ 必须具有的代数和算术特征的“逆”问题。在本文中，我们证明了代数风格的一些结果，表明如果 $f$ 的点概率远大于 $1/n$ 那么它一定接近低秩的二次形式。我们还给出了 Ramsey 图的应用，渐进地回答了 Kwan、Sudakov 和 Tran 的问题。
Consider a quadratic polynomial $fleft(xi_{1},dots,xi_{n}
ight)$ of independent Bernoulli random variables. What can be said about the concentration of $f$ on any single value? This generalises the classical Littlewood--Offord problem, which asks the same question for linear polynomials. As in the linear case, it is known that the point probabilities of $f$ can be as large as about $1/sqrt{n}$, but still poorly understood is the "inverse" question of characterising the algebraic and arithmetic features $f$ must have if it has point probabilities comparable to this bound. In this paper we prove some results of an algebraic flavour, showing that if $f$ has point probabilities much larger than $1/n$ then it must be close to a quadratic form with low rank. We also give an application to Ramsey graphs, asymptotically answering a question of Kwan, Sudakov and Tran.
DOI：
10.1017/s0305004120000183
发表时间：
2021
影响因子：
0.8
作者：
FOX, JACOB;KWAN, MATTHEW;SAUERMANN, LISA
通讯作者：
SAUERMANN, LISA
影响因子：
4.9
作者：
Chattopadhyay, Eshan;Zuckerman, David
通讯作者：
Zuckerman, David
影响因子：
--
作者：
Fox, Jacob;Sauermann, Lisa
通讯作者：
Sauermann, Lisa