How typical are integer isometries on a hypercube? Littlewood-Offord problem for Bernoulli Gram matrices 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.
 A: 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.
