Non-classical polynomials and the inverse theorem

In this note we characterize when non-classical polynomials are necessary in the inverse theorem for the Gowers $U^k$-norm. We give a brief deduction of the fact that a bounded function on $mathbb F_p^n$ with large $U^k$-norm must correlate with a classical polynomial when $kleq p+1$. To the best of our knowledge, this result is new for $k=p+1$ (when $p>2$). We then prove that non-classical polynomials are necessary in the inverse theorem for the Gowers $U^k$-norm over $mathbb F_p^n$ for all $kgeq p+2$, completely characterizing when classical polynomials suffice.

Large deviations in random Latin squares

In this note, we study large deviations of the number $mathbf{N}$ of intercalates ($2times2$ combinatorial subsquares which are themselves Latin squares) in a random $ntimes n$ Latin square. In particular, for constant $delta>0$ we prove that $Pr(mathbf{N}le(1-delta)n^{2}/4)leexp(-Omega(n^{2}))$ and $Pr(mathbf{N}ge(1+delta)n^{2}/4)leexp(-Omega(n^{4/3}(log n)^{2/3}))$, both of which are sharp up to logarithmic factors in their exponents. As a consequence, we deduce that a typical order-$n$ Latin square has $(1+o(1))n^{2}/4$ intercalates, matching a lower bound due to Kwan and Sudakov and resolving an old conjecture of McKay and Wanless.

Majority Dynamics: The Power of One

Consider $n=ell+m$ individuals, where $ellle m$, with $ell$ individuals holding an opinion $A$ and $m$ holding an opinion $B$. Suppose that the individuals communicate via an undirected network $G$, and in each time step, each individual updates her opinion according to a majority rule (that is, according to the opinion of the majority of the individuals she can communicate with in the network). This simple and well studied process is known as majority dynamics in social networks. Here we consider the case where $G$ is a random network, sampled from the binomial model $mathbb{G}(n,p)$, where $(log n)^{-1/16}le ple 1-(log n)^{-1/16}$. We show that for $n=ell+m$ with $Delta=m-ellle(log n)^{1/4}$, the above process terminates whp after three steps when a consensus is reached. Furthermore, we calculate the (asymptotically) correct probability for opinion $B$ to win and show it is [Phibigg(frac{pDeltasqrt{2}}{sqrt{pi p(1-p)}}bigg) + O(n^{-c}),] where $Phi$ is the Gaussian CDF. This answers two conjectures of Tran and Vu and also a question raised by Berkowitz and Devlin. The proof technique involves iterated degree revelation and analysis of the resulting degree-constrained random graph models via graph enumeration techniques of McKay and Wormald as well as Canfield, Greenhill, and McKay.

A Gaussian fixed point random walk

In this note, we design a discrete random walk on the real line which takes steps $0, pm 1$ (and one with steps in ${pm 1, 2}$) where at least $96%$ of the signs are $pm 1$ in expectation, and which has $mathcal{N}(0,1)$ as a stationary distribution. As an immediate corollary, we obtain an online version of Banaszczyks discrepancy result for partial colorings and $pm 1, 2$ signings. Additionally, we recover linear time algorithms for logarithmic bounds for the Koml{o}s conjecture in an oblivious online setting.

Rank deficiency of random matrices

Let $M_n$ be a random $ntimes n$ matrix with i.i.d. $text{Bernoulli}(1/2)$ entries. We show that for fixed $kge 1$, [lim_{nto infty}frac{1}{n}log_2mathbb{P}[text{corank }M_nge k] = -k.]

Popular differences for matrix patterns

The following combinatorial conjecture arises naturally from recent ergodic-theoretic work of Ackelsberg, Bergelson, and Best. Let $M_1$, $M_2$ be $ktimes k$ integer matrices, $G$ be a finite abelian group of order $N$, and $Asubseteq G^k$ with $|A|gealpha N^k$. If $M_1$, $M_2$, $M_1-M_2$, and $M_1+M_2$ are automorphisms of $G^k$, is it true that there exists a popular difference $d in G^ksetminus{0}$ such that [#{x in G^k: x, x+M_1d, x+M_2d, x+(M_1+M_2)d in A} ge (alpha^4-o(1))N^k.] We show that this conjecture is false in general, but holds for $G = mathbb{F}_p^n$ with $p$ an odd prime given the additional spectral condition that no pair of eigenvalues of $M_1M_2^{-1}$ (over $overline{mathbb{F}}_p$) are negatives of each other. In particular, the rotated squares pattern does not satisfy this eigenvalue condition, and we give a construction of a set of positive density in $(mathbb{F}_5^n)^2$ for which that pattern has no nonzero popular difference. This is in surprising contrast to three-point patterns, which we handle over all compact abelian groups and which do not require an additional spectral condition.

Anticoncentration versus the number of subset sums

Let $vec{w} = (w_1,dots, w_n) in mathbb{R}^{n}$. We show that for any $n^{-2}leepsilonle 1$, if [#{vec{xi} in {0,1}^{n}: langle vec{xi}, vec{w} rangle = tau} ge 2^{-epsilon n}cdot 2^{n}] for some $tau in mathbb{R}$, then [#{langle vec{xi}, vec{w} rangle : vec{xi} in {0,1}^{n}} le 2^{O(sqrt{epsilon}n)}.] This exponentially improves the $epsilon$ dependence in a recent result of Nederlof, Pawlewicz, Swennenhuis, and Wk{e}grzycki and leads to a similar improvement in the parameterized (by the number of bins) runtime of bin packing.

Optimal and algorithmic norm regularization of random matrices

Let $A$ be an $ntimes n$ random matrix whose entries are i.i.d. with mean $0$ and variance $1$. We present a deterministic polynomial time algorithm which, with probability at least $1-2exp(-Omega(epsilon n))$ in the choice of $A$, finds an $epsilon n times epsilon n$ sub-matrix such that zeroing it out results in $widetilde{A}$ with [|widetilde{A}| = Oleft(sqrt{n/epsilon}right).] Our result is optimal up to a constant factor and improves previous results of Rebrova and Vershynin, and Rebrova. We also prove an analogous result for $A$ a symmetric $ntimes n$ random matrix whose upper-diagonal entries are i.i.d. with mean $0$ and variance $1$.

On the smallest singular value of symmetric random matrices

We show that for an $ntimes n$ random symmetric matrix $A_n$, whose entries on and above the diagonal are independent copies of a sub-Gaussian random variable $xi$ with mean $0$ and variance $1$, [mathbb{P}[s_n(A_n) le epsilon/sqrt{n}] le O_{xi}(epsilon^{1/8} + exp(-Omega_{xi}(n^{1/2}))) quad text{for all } epsilon ge 0.] This improves a result of Vershynin, who obtained such a bound with $n^{1/2}$ replaced by $n^{c}$ for a small constant $c$, and $1/8$ replaced by $(1/8) + eta$ (with implicit constants also depending on $eta > 0$). Furthermore, when $xi$ is a Rademacher random variable, we prove that [mathbb{P}[s_n(A_n) le epsilon/sqrt{n}] le O(epsilon^{1/8} + exp(-Omega((log{n})^{1/4}n^{1/2}))) quad text{for all } epsilon ge 0.] The special case $epsilon = 0$ improves a recent result of Campos, Mattos, Morris, and Morrison, which showed that $mathbb{P}[s_n(A_n) = 0] le O(exp(-Omega(n^{1/2}))).$ The main innovation in our work are new notions of arithmetic structure -- the Median Regularized Least Common Denominator and the Median Threshold, which we believe should be more generally useful in contexts where one needs to combine anticoncentration information of different parts of a vector.

Singularity of discrete random matrices

Let $xi$ be a non-constant real-valued random variable with finite support, and let $M_{n}(xi)$ denote an $ntimes n$ random matrix with entries that are independent copies of $xi$. For $xi$ which is not uniform on its support, we show that begin{align*} mathbb{P}[M_{n}(xi)text{ is singular}] &= mathbb{P}[text{zero row or column}] + (1+o_n(1))mathbb{P}[text{two equal (up to sign) rows or columns}], end{align*} thereby confirming a folklore conjecture. As special cases, we obtain: (1) For $xi = text{Bernoulli}(p)$ with fixed $p in (0,1/2)$, [mathbb{P}[M_{n}(xi)text{ is singular}] = 2n(1-p)^{n} + (1+o_n(1))n(n-1)(p^2 + (1-p)^2)^{n},] which determines the singularity probability to two asymptotic terms. Previously, no result of such precision was available in the study of the singularity of random matrices. (2) For $xi = text{Bernoulli}(p)$ with fixed $p in (1/2,1)$, [mathbb{P}[M_{n}(xi)text{ is singular}] = (1+o_n(1))n(n-1)(p^2 + (1-p)^2)^{n}.] Previously, only the much weaker upper bound of $(sqrt{p} + o_n(1))^{n}$ was known due to the work of Bourgain-Vu-Wood. For $xi$ which is uniform on its support: (1) We show that begin{align*} mathbb{P}[M_{n}(xi)text{ is singular}] &= (1+o_n(1))^{n}mathbb{P}[text{two rows or columns are equal}]. end{align*} (2) Perhaps more importantly, we provide a sharp analysis of the contribution of the `compressible part of the unit sphere to the lower tail of the smallest singular value of $M_{n}(xi)$.