Sharp Inner Product Correlations for Hypercube Bijections

Ijay Narang; Muchen Ju

arxiv: 2509.00716 · v2 · submitted 2025-08-31 · 🧮 math.CO

Sharp Inner Product Correlations for Hypercube Bijections

Ijay Narang , Muchen Ju This is my paper

Pith reviewed 2026-05-18 20:16 UTC · model grok-4.3

classification 🧮 math.CO

keywords hypercube bijectionsinner product correlationsHamming association schemeBirkhoff polytopeRob Morris conjecturespectral decompositionpermutation correlations

0 comments

The pith

Any bijection on the hypercube preserves the probability that two random points and their images both have nonnegative inner product, up to an additive error of order 1 over square root n.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that for any rearrangement f of the vertices of the n-dimensional hypercube, the fraction of pairs x and y where both the original pair and the image pair have inner product at least zero is at least one quarter minus a vanishing term of size roughly one over square root n. This bound also holds when the inner-product condition is applied to any two independent bijections instead of one. The result quantifies how much any permutation must preserve the natural correlation structure of the hypercube. A reader cares because the hypercube encodes all binary strings of length n, so the statement limits how freely one can relabel them without destroying pairwise sign correlations.

Core claim

For any bijection f from {-1,1}^n to itself, the probability that a random pair x,y satisfies both <x,y> >= 0 and <f(x),f(y)> >= 0 is at least 1/4 minus O(1/sqrt(n)). The same lower bound holds for the joint event under any two bijections. The argument proceeds by applying the spectral decomposition of the Hamming association scheme to rewrite the probability as the value of a linear program over the Birkhoff polytope; the contribution of all nontrivial eigenvalues is shown to be asymptotically negligible, so the bound is controlled by the principal eigenvalue.

What carries the argument

Spectral decomposition of the Hamming association scheme, which converts the correlation probability into a linear program over the Birkhoff polytope whose optimum is dominated by the principal eigenvalue once the nontrivial spectrum is shown to be negligible.

If this is right

The same quantitative lower bound holds when the inner-product condition is replaced by the corresponding condition for any pair of independent bijections.
No hypercube bijection can make the positive-correlation event occur with probability noticeably smaller than one quarter.
The Hamming association scheme and Birkhoff-polytope formulation isolate the geometric contribution of the all-ones vector as the only non-vanishing term in the large-n limit.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same spectral-reduction technique may apply directly to other association schemes on vertex-transitive graphs where one seeks correlation-preservation bounds for permutations.
If the O(1/sqrt(n)) error can be replaced by an exact finite-n expression, the result would give a sharp combinatorial inequality without asymptotics.
The argument suggests that the hypercube's correlation geometry is rigid enough that approximate isometries in the Hamming metric must approximately preserve sign patterns of inner products.

Load-bearing premise

The contribution of the nontrivial spectrum is asymptotically negligible, allowing the entire lower bound to be read off from the principal eigenvalue after the reformulation as an LP over the Birkhoff polytope.

What would settle it

An explicit bijection f for some large n such that the measured probability falls below 1/4 minus C/sqrt(n) for a constant C larger than the paper's implicit constant would disprove the claim.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives the first proof of Morris's conjecture with a 1/4 - O(1/sqrt(n)) correlation lower bound via Hamming scheme spectral methods and Birkhoff LP reformulation.

read the letter

The main takeaway is that the paper resolves Rob Morris's conjecture by proving any bijection f on the hypercube satisfies Pr[ >=0 and >=0] >= 1/4 - O(1/sqrt(n)), and the same holds for any pair of bijections. The argument uses the spectral decomposition of the Hamming association scheme to express the relevant quadratic form in terms of a permutation matrix, then relaxes to a linear program over the Birkhoff polytope so the principal eigenvalue can be isolated and the rest shown to vanish at the claimed rate. This is genuinely new: the quantitative bound and its proof were not in the prior literature. The reformulation is clean and draws on standard tools from association schemes and polytope theory without circularity or invented parameters. The strategy is a reasonable way to handle these correlation questions on the hypercube. The soft spot is the claim that the sum over nontrivial idempotents is O(1/sqrt(n)). The stress-test note correctly flags that the relevant eigenspaces have dimension roughly 2^n / sqrt(n), so even with Krawtchouk decay the worst-case alignment over doubly stochastic matrices could introduce an extra factor that cancels the decay and leaves a larger error. If the full proof supplies a uniform bound that controls this, the result holds; otherwise the error analysis is the part that would need tightening. This is for combinatorialists and discrete analysts working on hypercube mappings, correlation inequalities, or coding-theoretic questions. A reader comfortable with association schemes would extract value from the LP reduction and the conjecture resolution. It deserves a serious referee because settling an open conjecture with an explicit rate is worth verifying the spectral estimates in detail. I would recommend sending it to peer review.

Referee Report

1 major / 2 minor

Summary. The paper resolves a conjecture of Rob Morris by showing that for any bijection f : {-1,1}^n → {-1,1}^n, Pr_{x,y} [<x,y> ≥ 0 and <f(x),f(y)> ≥ 0] ≥ 1/4 - O(1/sqrt(n)). The proof applies the spectral decomposition of the Hamming association scheme, reformulates the quadratic form as a linear program over the Birkhoff polytope, and argues that the contribution of the nontrivial idempotents is asymptotically negligible, leaving the principal eigenvalue to dominate.

Significance. If the central error bound holds, the result gives a sharp quantitative correlation inequality for arbitrary bijections of the hypercube and extends immediately to pairs of bijections. The combination of association-scheme spectral theory with an LP formulation over the Birkhoff polytope is technically clean and supplies a reusable template for similar permutation problems on highly symmetric spaces.

major comments (1)

The claim that the sum of contributions from nontrivial idempotents E_j (j ≥ 1) is o(1) (and in fact O(1/sqrt(n))) is load-bearing for the main theorem. The Krawtchouk eigenvalues of the cumulative distance matrix decay roughly as (1-2p)^k at p=1/2, yet the eigenspaces have dimension ~ binom(n,k) ≈ 2^n / sqrt(n). When the quadratic form is rewritten as a linear functional over doubly stochastic matrices X, the worst-case alignment of X with a high-dimensional eigenspace can introduce an extra sqrt(n) factor in the operator-norm or trace bound on the cross terms. The manuscript must supply the explicit uniform estimate (or lemma) that rules out this cancellation and keeps the total error O(1/sqrt(n)).

minor comments (2)

In the abstract, the sentence claiming the same bound for any two bijections should be accompanied by a one-sentence indication of how the single-bijection argument extends.
Notation for the Bose-Mesner algebra elements, the idempotents E_j, and the normalization of the quadratic form E[g(x,y)h(f(x),f(y))] should be introduced once and used consistently throughout the spectral section.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and for the detailed comment on the error bound. We respond to the major comment below and will update the manuscript accordingly.

read point-by-point responses

Referee: The claim that the sum of contributions from nontrivial idempotents E_j (j ≥ 1) is o(1) (and in fact O(1/sqrt(n))) is load-bearing for the main theorem. The Krawtchouk eigenvalues of the cumulative distance matrix decay roughly as (1-2p)^k at p=1/2, yet the eigenspaces have dimension ~ binom(n,k) ≈ 2^n / sqrt(n). When the quadratic form is rewritten as a linear functional over doubly stochastic matrices X, the worst-case alignment of X with a high-dimensional eigenspace can introduce an extra sqrt(n) factor in the operator-norm or trace bound on the cross terms. The manuscript must supply the explicit uniform estimate (or lemma) that rules out this cancellation and keeps the total error O(1/sqrt(n)).

Authors: We agree with the referee that an explicit uniform estimate is necessary to confirm the O(1/sqrt(n)) error term. In the manuscript, the negligibility follows from the rapid decay of the Krawtchouk eigenvalues for the relevant matrices, which outpaces the binomial growth in dimension. However, to address the potential alignment issue with high-dimensional eigenspaces, we will include a new lemma that provides a uniform bound over all doubly stochastic matrices X. This lemma will use the entrywise bounds and orthogonality of the idempotents to show that the total contribution remains O(1/sqrt(n)) without an additional sqrt(n) factor. We will revise the paper to state this lemma explicitly. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation uses external spectral theory and polytope reformulation

full rationale

The paper decomposes the indicator of nonnegative inner products via the Bose-Mesner algebra of the Hamming scheme, projects onto the principal idempotent, and bounds the remainder over the Birkhoff polytope using decay of Krawtchouk eigenvalues. These eigenvalue bounds and the association-scheme algebra are standard external facts independent of the target inequality; the negligibility argument does not reduce to a fitted parameter, self-definition, or self-citation chain. The central claim therefore remains non-tautological.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof relies on standard tools from algebraic combinatorics without introducing new free parameters or postulated entities.

axioms (1)

standard math The Hamming association scheme admits a spectral decomposition applicable to analyzing sign correlations of inner products under bijections.
Invoked to reformulate the probability expression as a linear program over the Birkhoff polytope.

pith-pipeline@v0.9.0 · 5693 in / 1310 out tokens · 56781 ms · 2026-05-18T20:16:52.396097+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

reformulate the problem as a linear program over the Birkhoff polytope... isolate the contribution of the nontrivial spectrum, which we show is asymptotically negligible
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

λS = sum_{d=0}^{⌊n/2⌋} K_d(|S|)... closed formula involving the Beta function

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages

[1]

Upper bounds for multicolour ramsey numbers, 2024

Paul Balister, Béla Bollobás, Marcelo Campos, Simon Griffiths, Eoin Hurley, Robert Morris, Julian Sahasrabudhe, and Marius Tiba. Upper bounds for multicolour ramsey numbers, 2024

work page 2024
[2]

In Erd o s--Ko--Rado Theorems: Algebraic Approaches

Chris Godsil and Karen Meagher. In Erd o s--Ko--Rado Theorems: Algebraic Approaches . Cambridge University Press, Cambridge, 2016

work page 2016

[1] [1]

Upper bounds for multicolour ramsey numbers, 2024

Paul Balister, Béla Bollobás, Marcelo Campos, Simon Griffiths, Eoin Hurley, Robert Morris, Julian Sahasrabudhe, and Marius Tiba. Upper bounds for multicolour ramsey numbers, 2024

work page 2024

[2] [2]

In Erd o s--Ko--Rado Theorems: Algebraic Approaches

Chris Godsil and Karen Meagher. In Erd o s--Ko--Rado Theorems: Algebraic Approaches . Cambridge University Press, Cambridge, 2016

work page 2016