1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Terry Tao Dec 21 '19 at 20:36
  • $\begingroup$ @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? $\endgroup$ – D_809 Dec 21 '19 at 21:00
3
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Great, thank you! $\endgroup$ – D_809 Dec 22 '19 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.