Signed Low-Entropy Reweightings to Rank One on the Sphere
Statement: AI-written, not yet formalized. Proof: AI draft, not yet independently reviewed, not yet formalized.
A probability distribution over unit vectors in \(\mathbb{R}^n\) has a second moment — the average outer product of a random vector with itself — that in general looks nothing like a rank-one matrix. Reweighting the distribution before averaging can buy closeness to rank one, at an entropy price; the question is how much cheaper that price gets once the reweighting is allowed to go negative, not just condition on an event. It is the sharpest gap the paper’s own techniques leave behind: the same machinery that yields its \(2^{\tilde O(\sqrt n)}\) algorithm for Best Separable State also proves the nonnegative case of this question tight, and the authors flag the signed case as the one lever left that could improve both that algorithm and the best known bound on the log rank conjecture. This site now has an AI-produced, AI-verified (not yet human-reviewed) affirmative resolution — see the Proof tab.
View PDF · LaTeX source · Formal statement — not yet formalized
Let \(\mathbb{S}^{n-1}\) be the real unit sphere. A signed reweighting of a Borel probability measure \(\mu\) on \(\mathbb{S}^{n-1}\) with entropy cost at most \(K\) is a Borel measurable, \(\mu\)-integrable function \(r : \mathbb{S}^{n-1} \to \mathbb{R}\) (not required to be nonnegative) with \[ \mathbb{E}_{v \sim \mu}\big|r(v)\big| = 1, \qquad \mathbb{E}_{v \sim \mu}\Big[\big|r(v)\big|\log\big|r(v)\big|\Big] \le K. \]
Conjecture. For every \(\varepsilon > 0\) and every \(\delta > 0\) there is a finite constant \(C = C(\varepsilon,\delta)\) such that, for every \(n \in \mathbb{N}\) and every Borel probability measure \(\mu\) on \(\mathbb{S}^{n-1}\), there exist a signed reweighting \(r\) of \(\mu\) with entropy cost at most \(C \cdot n^{\delta}\) and a nonzero rank-one matrix \(L \in \mathbb{R}^{n \times n}\) such that \[ \Big\|\mathbb{E}_{v \sim \mu}\big[r(v)\, vv^{\top}\big] - L\Big\|_F \le \varepsilon\, \|L\|_F . \]
This is the paper’s Question 8.1. A positive answer for any \(\delta < 1/2\) is the content of the question — the nonnegative case is already known, tightly, at \(\delta = 1/2\) — and the paper states outright that the answer is No if negative weights are disallowed, so any progress on the signed case must use genuine cancellation.
A caveat worth carrying forward (from the harvester’s own review, confirmed against the PDF): the paper’s \(O(n^{\delta})\) leaves the hidden constant’s dependence on \(\varepsilon\) implicit, and footnote 8 of the paper warns that the log-rank application specifically needs better control of that dependence than the paper’s own setting requires. A solver aiming at the log-rank corollary should track \(C(\varepsilon,\delta)\)’s dependence on \(\varepsilon\) rather than treat the constant as free.
Sources
- Barak, Kothari, and Steurer. Quantum entanglement, sum of squares, and the log rank conjecture. STOC 2017; arXiv:1701.06321v2, 9 July 2017. Question 8.1 and its discussion are on p. 21 (printed p. 19); the nonnegative case is Theorem 2.3 (p. 7); footnotes 7–8 on the log-rank corollary’s caveats are on pp. 6, 8.
View PDF · LaTeX source · Formal proof — not yet formalized
AI: a “conjecture-harness” proof-campaign harness (Anthropic Claude models) · Reviewed by: AI referees only, nobody human yet · 25 August 2026.
Resolved, affirmatively, and more strongly than the question asks. Every Borel probability measure \(\mu\) on \(\mathbb{S}^{n-1}\) admits a signed reweighting \(r\) reaching an exact (not merely \(\varepsilon\)-close) nonzero rank-one second moment, at entropy cost only \[ \log\!\big(n(n+1)/2\big) = O(\log n), \] which is below every \(n^{\delta}\) for every \(\delta > 0\). Packaged against the Contract’s own quantifiers this gives \(C(\varepsilon,\delta) = \tfrac{2}{e\delta}\) — a constant with no dependence on \(\varepsilon\) at all, stronger than footnote 8’s warning asks for. The construction is a reproducing-kernel argument on the finite-dimensional space of quadratic forms restricted to the sphere: evaluate at a well-chosen support point \(v_0\), use the kernel itself as the (possibly signed) reweighting function, and bound its entropy by the trace identity \(\int K(v,v)\,d\mu = \dim\). A companion corollary (Corollary B) transports the same construction to distributions over unit-Frobenius-norm rank-one matrices — the normalization the source paper’s own Theorem 2.3 uses — and the write-up gives, for both the sphere case and this generalization, an explicit reconciliation showing the construction never conflicts with the source’s own tightness claim for nonnegative reweightings (p. 6): whenever this construction happens to return a nonnegative \(r\), that \(\mu\) is independently shown not to be a hard instance for the nonnegative question either.
How this was verified. This proof was produced and checked by an AI-driven proof harness (this site’s “conjecture-harness” campaign framework), not a single AI pass: six revision rounds, twenty independent blind adversarial referee passes spread over four audited rounds, and four independent handling-editor triage rulings that re-derived every disputed claim from scratch rather than taking a referee’s word for it. Across all of that, no upheld finding has ever touched the load-bearing chain — Lemmas 1–4, the Theorem, the Corollary, or Corollary B; every real defect found lived in a scope/commentary remark, and the current revision closes the last one. The full round-by-round audit trail is campaign/LEDGER.md; the artifact frozen there is 0048-RKHS-1-r6. No human has reviewed the mathematics, and nothing here is formalized in Lean.
An open editorial fork, disclosed for transparency. A separate, concurrent AI session forked this same campaign at round 3 (before the round-3 triage ruling that this branch used was finalized) and closed the identical scope-commentary gap by deleting the problematic clause rather than by adding the reconciling argument this branch adds. Both branches share byte-identical load-bearing mathematics; the difference is purely editorial. Both are recorded in the ledger, and reconciling which becomes the citable page content is a pending human decision, not a mathematical one.
What the source paper itself established (background, unchanged). Theorem 2.3 proves the \(\delta = 1/2\) case with a nonnegative reweighting, tight as stated in that formulation — “we do know that the answer to this question is No if one does not allow negative reweighting functions” (p. 21) — which is exactly why the signed case above required genuine cancellation rather than a sharper analysis of the known nonnegative technique.
What this resolution means for the log-rank connection. The source paper flags the signed case as its most promising lever on the log rank conjecture, hedged by footnotes 7–8 on which notion of “approximate” is needed and how the bound depends on \(\varepsilon\). This resolution sidesteps the \(\varepsilon\)-dependence caveat entirely (its constant has none) but does not by itself resolve footnote 7’s caveat on which “approximate” notion the log-rank application needs (Gavinsky–Lovett’s equivalence uses a specific combinatorial closeness measure, not directly the Frobenius-norm closeness proved here), nor does it address the extension to sum-of-squares pseudo-distributions the paper’s Best Separable State application would need. Both remain open obligations below.
Why it matters. The paper is explicit that a positive answer below the square-root threshold may improve the best known bound on the log rank conjecture to \(\tilde O(n^{\delta})\) — hedged, in its own words, by footnotes 7 and 8 on which notion of “approximate” is needed and how the bound depends on \(\varepsilon\) — and, if extended to sum-of-squares pseudo-distributions, would improve the paper’s own Best Separable State algorithm’s running time to \(\exp(\tilde O(n^{\delta}))\) from \(\exp(\tilde O(\sqrt n))\). Two problems that have resisted independently would move together. A negative answer is almost as informative: it would say cancellation buys nothing over conditioning at this task, and that a fundamentally different notion of “closeness to rank one” is needed to make further progress.
Relation to the paper’s dual, combinatorial formulation. The paper’s Theorem 2.4 restates Theorem 2.3 as a purely combinatorial statement about large near-rank-one submatrices of low-rank real matrices, and that combinatorial form is what connects the whole circle of ideas to Lovett’s \(\tilde O(\sqrt n)\) bound on the log rank conjecture. Question 8.1 is the geometric (sphere / second-moment) formulation; a signed analogue of the combinatorial dual form is not stated by the paper as a separate question, so this page tracks only the geometric version actually posed.
Checked against the literature, 2026-08-19. Searched for post-2017 progress on Question 8.1 specifically and on the log rank conjecture’s best known bound generally. Lovett’s \(\tilde O(\sqrt n)\) bound (2014) appears to remain the best known general bound; a 2025 paper (“Around the log-rank conjecture,” Israel J. Math.) and a 2025 preprint on matrix discrepancy and the log-rank conjecture engage with the same circle of ideas but were not read in enough depth here to say whether either bears on the signed reweighting formulation specifically, as opposed to the combinatorial dual or other equivalent forms. A distinct October 2025 preprint introduces “signed rectangle rank,” a combinatorial notion for Boolean matrices that is not obviously the same object as this page’s signed reweighting on the sphere, and does not appear to cite Barak–Kothari–Steurer directly. No claimed resolution of Question 8.1 was found. This is a partial check, not an exhaustive one — a reviewer with more time should read those 2025 papers in full before treating this as settled current as of today, rather than relying on this page’s search.