On the number of Hadamard matrices via anti-concentration

Many problems in combinatorial linear algebra require upper bounds on the number of solutions to an underdetermined system of linear equations Ax = b, where the coordinates of the vector x are restricted to take values in some small subset (e.g. {+/- 1}) of the underlying field. The classical ways of bounding this quantity are to use either a rank bound observation due to Odlyzko or a vector anti-concentration inequality due to Halasz. The former gives a stronger conclusion except when the number of equations is significantly smaller than the number of variables; even in such situations, the hypotheses of Halasz's inequality are quite hard to verify in practice. In this paper, using a novel approach to the anticoncentration problem for vector sums, we obtain new Halisz-type inequalities that beat the Odlyzko bound even in settings where the number of equations is comparable to the number of variables. In addition to being stronger, our inequalities have hypotheses that are considerably easier to verify. We present two applications of our inequalities to combinatorial (random) matrix theory: (i) we obtain the first nontrivial upper bound on the number of n x n Hadamard matrices and (ii) we improve a recent bound of Deneanu and Vu on the probability of normality of a random {+/- 1} matrix.