Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.00716 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914490132463616 |
|---|---|
| author | Narang, Ijay Ju, Muchen |
| author_facet | Narang, Ijay Ju, Muchen |
| contents | We resolve a conjecture of Rob Morris concerning bijections on the hypercube. Specifically, we show that for any bijection $f : \{-1,1\}^n \to \{-1,1\}^n$, \[ \Pr_{x,y \in \{-1,1\}^n}\big[ \langle x,y \rangle \ge 0 \;\text{and}\; \langle f(x),f(y) \rangle \ge 0 \big] \;\;\ge\; \tfrac{1}{4} - O(1/\sqrt{n}), \] implying the same lower bound for the joint event under any two bijections. Our proof proceeds by applying the spectral decomposition of the Hamming association scheme, which allows us to reformulate the problem as a linear program over the Birkhoff polytope. This makes it possible to isolate the contribution of the nontrivial spectrum, which we show is asymptotically negligible, leaving the dominant contribution arising from the principal eigenvalue. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_00716 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sharp Inner Product Correlations for Hypercube Bijections Narang, Ijay Ju, Muchen Combinatorics We resolve a conjecture of Rob Morris concerning bijections on the hypercube. Specifically, we show that for any bijection $f : \{-1,1\}^n \to \{-1,1\}^n$, \[ \Pr_{x,y \in \{-1,1\}^n}\big[ \langle x,y \rangle \ge 0 \;\text{and}\; \langle f(x),f(y) \rangle \ge 0 \big] \;\;\ge\; \tfrac{1}{4} - O(1/\sqrt{n}), \] implying the same lower bound for the joint event under any two bijections. Our proof proceeds by applying the spectral decomposition of the Hamming association scheme, which allows us to reformulate the problem as a linear program over the Birkhoff polytope. This makes it possible to isolate the contribution of the nontrivial spectrum, which we show is asymptotically negligible, leaving the dominant contribution arising from the principal eigenvalue. |
| title | Sharp Inner Product Correlations for Hypercube Bijections |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2509.00716 |