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.



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


