How typical are integer isometries on a hypercube? Littlewood-Offord problem for Bernoulli Gram matrices

Question

Let $m\geq 3$ be fixed and $n\to\infty$. Consider $v=(v_j)_{j\leq m}$ with $v_1,\ldots,v_m\in \{-1,+1\}^n$. Let:

• $N_I(v)$ be the number of sequences $u_1,\ldots,u_m\in \{-1,+1\}^n$ isometric to $v$ in $\mathbb{R}^n$, i.e. $u_j=Qv_j$ for some orthogonal matrix $Q$.
• $N_S(v)$ be the number of sequences $u_1,\ldots,u_m\in \{-1,+1\}^n$ isometric to $v$ in $\{-1,+1\}^n$, i.e. $u_j=Qv_j$ for some integer orthogonal matrix $Q$.

How does the average of $N_S(v)/N_I(v)$ over $2^{nm}$ choices of the sequence $v$ behave as $n\to\infty$. In other words, how typical are hypercube symmetries among all isometries of finite subsets of $\{-1,+1\}^n$?

---

Instead of looking at the average of the ratio, we can compute the corresponding probabilities. Let $u_1,\ldots,u_m$ and $v_1,\ldots, v_m$ be chosen uniformly at random from $\{-1,+1\}^n$ and let $$U=(u_i\cdot u_j)_{1\leq i,j\leq m},\quad V=(v_i\cdot v_j)_{1\leq i,j\leq m}$$ be the Gram matrices for these two sequences, so the probability that these two sequences are isometric in $\mathbb{R}^n$ is $\Pr(U=V).$ It is not difficult to estimate using Sterling's formula that the probability that these sequences are isometric in $\{-1,+1\}^n$ has the leading order $$\sim\left(\frac{1}{\sqrt{n}}\right)^{2^m-1}.$$ The probability $\Pr(U=V)$ is bigger, so it is reasonable to expect that the leading order $$\Pr(U=V)\sim \left(\frac{1}{\sqrt{n}}\right)^{c_m}$$ for some constant $c_m\leq 2^m-1$. Is $c_m<2^m-1$? Any pointers are appreciated.

Answer 1

By the Chernoff bound, we see that for each $1 \leq i < j \leq m$, one has $u_i \cdot u_j = O(\sqrt{n})$ with probability at least $1-\frac{1}{10m^2}$ (say), where implied constants are allowed to depend on the fixed constant $m$. Thus, with probability at least $1-\frac{1}{10}$, the random variable $U$ takes values in the set $S$ of $n \times n$ symmetric matrices with diagonal entries $n$ and off-diagonal entries $O(n^{1/2})$. This set has cardinality $O( n^{\frac{m(m-1)}{4}} )$. Since $V$ has the same distribution, we conclude from Cauchy-Schwarz that \begin{align*} {\bf P}(U=V) &\geq \sum_{A \in S} {\bf P}(U=V=A) \\ &= \sum_{A \in S} {\bf P}(U=A)^2\\ & \geq \frac{1}{|S|} (\sum_{A \in S} {\bf P}(U=A))^2 \\ &\gg n^{-\frac{m(m-1)}{4}} {\bf P}(U \in S)^2\\ & \gg n^{-\frac{m(m-1)}{4}}. \end{align*}

Conversely, we claim that for any $m \times m$ matrix $A$, we have ${\bf P}(U=A) \ll n^{-\frac{m(m-1)}{4}}$, which implies the matching upper bound \begin{align*} {\bf P}(U=V) &= \sum_A {\bf P}(U=A) {\bf P}(V=A)\\ &\ll n^{-\frac{m(m-1)}{4}} \sum_A {\bf P}(V=A)\\ & = n^{-\frac{m(m-1)}{4}}. \end{align*} To prove this claim, it suffices by induction to show that for almost all choices of $u_1,\dots,u_{m-1}$ (excluding events of exponentially small probability), and any $a_1,\dots,a_{m-1}$, the event $$ u_m \cdot u_j = a_j \hbox{ for all } j=1,\dots,m-1$$ occurs with probability $O( n^{-\frac{m-1}{2}} )$ (after conditioning $u_1,\dots,u_{m-1}$ to be fixed). One can write this event as $$ (a_1,\dots,a_{m-1}) = \epsilon_1 w_1 + \dots + \epsilon_n w_n$$ where $w_i$ is the vector $w_i = (u_{1,i},\dots,u_{m-1,i})$ consisting of the $i^{th}$ coordinates of $u_1,\dots,u_{m-1}$, and $\epsilon_1,\dots,\epsilon_n = \pm 1$ are iid Bernoulli signs. By the Chernoff bound, we see that outside of an event of exponentially small probability, the $w_1,\dots,w_n$ are approximately equidistributed in the cube $\{-1,1\}^{m-1}$ in the sense that each vector in this cube appears $\gg n$ times. The claim now follows from the Esseen concentration inequality (see e.g. Lemma 7.17 of my book with Van Vu) and a routine calculation.