Search

Let A be an n\times 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-2\exp (-\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 \[ \lVert \widetilde {A}\rVert = O(\sqrt {n/\epsilon }). \] 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 n\times n random matrix whose upper-diagonal entries are i.i.d. with mean 0 and variance 1. [ABSTRACT FROM AUTHOR]

The following combinatorial conjecture arises naturally from recent ergodic-theoretic work of Ackelsberg, Bergelson, and Best. Let M_1, M_2 be k\times k integer matrices, G be a finite abelian group of order N, and A\subseteq G^k with |A|\ge \alpha 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^k\setminus \{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 the algebraic closure \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 additional spectral conditions. [ABSTRACT FROM AUTHOR]