# 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.

• The off-diagonal coefficients of $U,V$ are typically integers of size $O(\sqrt{n})$ (and the diagonal entries equal to $n$), so the symmetric $m \times m$ matrices $U,V$ are concentrated on a set of cardinality $O(\sqrt{n}^{\frac{m^2-m}{2}})$. Cauchy-Schwarz then gives $P(U=V) \gtrsim \sqrt{n}^{-\frac{m^2-m}{2}}$. It seems reasonable to conjecture a matching upper bound also (it seems plausible that existing Littlewood-Offord theory can bound the probability density of $U$ or $V$ by $O( \sqrt{n}^{-\frac{m^2-m}{2}} )$ with enough effort). Dec 21, 2019 at 20:36
• @TerryTao, thank you! Can you please post your comment as an answer so I can accept it, since it answers everything I wanted to know? Dec 21, 2019 at 21:00

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.