[#P3120] Matrix Spencer discrepancy conjecture

Neutral schematic of several symmetric matrices stacked with plus-minus signs and an operator-norm gauge. — The objects and operations appearing in Matrix Spencer discrepancy conjecture.

Problem. Does there exist an absolute constant \(C>0\) such that, for every positive integer \(n\) and all real self-adjoint matrices \(A_1,\ldots,A_n\in\mathbb R^{n\times n}\) with operator norm \(\|A_i\|_{\mathrm{op}}\le1\), there are signs \(\varepsilon_i\in\{-1,1\}\) satisfying \(\|\sum_{i=1}^n\varepsilon_iA_i\|_{\mathrm{op}}\le C\sqrt n\)?

1Context

Known frontier: The conjectured bound holds for commuting matrices and for matrices of rank at most \(n/\log^3 n\); general concentration gives an extra \(\sqrt{\log n}\) factor. Open boundary: Remove the logarithmic loss without rank or commutativity hypotheses.

2Problem setup

Definition 1 (Self-adjoint matrix). Here this means a real symmetric square matrix.

Definition 2 (Operator norm). \(\|A\|_{\mathrm{op}}=\sup_{\|x\|_2=1}\|Ax\|_2\).

Remark 1. This is a noncommutative analogue of Spencer vector discrepancy.

3What counts as a solution

Prove the bound with one universal \(C\), or give a family for which the minimum signed-sum norm divided by \(\sqrt n\) is unbounded.

1Status

Current status (Current status and exact unresolved remainder). OPEN as checked on 2026-08-01. Strongest checked neighboring result: The conjectured bound holds for commuting matrices and for matrices of rank at most \(n/\log^3 n\); general concentration gives an extra \(\sqrt{\log n}\) factor. Exact unresolved remainder: Remove the logarithmic loss without rank or commutativity hypotheses.^[1][2]

1Records

Record	Kind	Assessment
	Result	Supported
claim · Claim 1 OPEN as checked on 2026-08-01. Strongest checked neighboring result: The conjectured bound holds for commuting matrices and for matrices of rank at most \(n/\log^3 n\); general concentration gives an extra \(\sqrt{\log n}\) factor. Exact unresolved remainder: Remove the logarithmic loss without rank or commutativity hypotheses.^[1][2] Relevance to this problem This is the dated publication status for the canonical target Matrix Spencer discrepancy conjecture. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details The problem was checked as open on 2026-08-01. The strongest neighboring result found in the cited sources is: The conjectured bound holds for commuting matrices and for matrices of rank at most \(n/\log^3 n\); general concentration gives an extra \(\sqrt{\log n}\) factor. The exact unresolved remainder is: Remove the logarithmic loss without rank or commutativity hypotheses. A complete resolution must meet the following acceptance conditions: - Prove the bound with one universal \(C\), or give a family for which the minimum signed-sum norm divided by \(\sqrt n\) is unbounded. Open full record →
	Result	Supported
claim · Claim 2 The conjectured bound holds for commuting matrices and for matrices of rank at most \(n/\log^3 n\); general concentration gives an extra \(\sqrt{\log n}\) factor.^[1][2] Relevance to this problem Locates the present research frontier immediately below Matrix Spencer discrepancy conjecture. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details The conjectured bound holds for commuting matrices and for matrices of rank at most \(n/\log^3 n\); general concentration gives an extra \(\sqrt{\log n}\) factor. This leaves the following boundary unresolved: Remove the logarithmic loss without rank or commutativity hypotheses. The distinction is retained here so a restricted theorem, finite computation, or neighboring case is not presented as a solution of the full target. Related: Claim 1 Open full record →
	Trace	Supported
attempt · Route 1 The exact formulation, named variants, 2025–2026 updates, and repository-wide semantic duplicates were checked on 2026-08-01. The source collection still marks the stated remainder open. Living-database status remains subject to later literature not indexed there.^[1][2] Relevance to this problem Documents why Matrix Spencer discrepancy conjecture was treated as a distinct open target on 2026-08-01. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state completed Scope No narrower scope recorded Sources Reference 1, Reference 2 What happened The audit ran on 2026-08-01 across source collection and its cited primary literature, Crossref/arXiv or MathSciNet stable records, TheoremDB published, prospecting, formal-conjecture, packet, and retired corpus. It checked the exact statement, its named or normalized variants, recent status evidence, and the controlled TheoremDB corpus. Queries included: - "Matrix Spencer" conjecture 2026 - "Resolving Matrix Spencer" rank - matrix discrepancy operator norm C sqrt n The exact formulation, named variants, 2025–2026 updates, and repository-wide semantic duplicates were checked on 2026-08-01. The source collection still marks the stated remainder open. Living-database status remains subject to later literature not indexed there. Related: Claim 1 Open full record →
	Trace	Reported
attempt · Route 2 Remove the logarithmic loss without rank or commutativity hypotheses. Relevance to this problem Turns the remaining uncertainty in Matrix Spencer discrepancy conjecture into a checkable research target. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded What happened Research should address this boundary directly: Remove the logarithmic loss without rank or commutativity hypotheses. A claimed resolution should satisfy every item below and preserve the statement's exact quantifiers and normalizations: - Prove the bound with one universal \(C\), or give a family for which the minimum signed-sum norm divided by \(\sqrt n\) is unbounded. Related: Claim 1 Open full record →
No records match these filters.

Notes and companion materialContext, examples, and computations

Original intake status. OPEN as checked on 2026-08-01. Strongest checked neighboring result: The conjectured bound holds for commuting matrices and for matrices of rank at most \(n/\log^3 n\); general concentration gives an extra \(\sqrt{\log n}\) factor. Exact unresolved remainder: Remove the logarithmic loss without rank or commutativity hypotheses.

Equivalent-formulation queries: "Matrix Spencer" conjecture 2026; "Resolving Matrix Spencer" rank; matrix discrepancy operator norm C sqrt n
Strongest checked neighboring result: The conjectured bound holds for commuting matrices and for matrices of rank at most \(n/\log^3 n\); general concentration gives an extra \(\sqrt{\log n}\) factor.
Exact unresolved remainder: Remove the logarithmic loss without rank or commutativity hypotheses.

How the 4 records connectTyped relations and evidence flow

ProblemMatrix Spencer discrepancy conjecture

Claim 1Current status and exact unresolved remainderin this packetSupported
Route 1Dated source and duplicate auditchecksSupported
Claim 2Strongest checked neighboring resultinformsSupported
Route 2Work at the unresolved boundaryaddressesReported

2See also

Cycle Double Cover Conjecturecombinatorics
The Total Coloring Conjecturecombinatorics
Sabidussi's Compatibility Conjecturecombinatorics

How to cite

TheoremDB contributors, “Matrix Spencer discrepancy conjecture,” TheoremDB research memory, snapshot of August 1, 2026. https://theoremdb.org/statements/matrix-spencer-discrepancy

This page as plain text: matrix-spencer-discrepancy.md

This problem includes 4 records joined by 3 typed links, sourced from doi.org^[1], current as of August 1, 2026.

1References

Packet source. Afonso S. Bandeira, Anastasia Kireeva, Antoine Maillard, and Almut Rödder, “Randomstrasse101: Open Problems of 2024,” arXiv:2504.20539, version dated 22 March 2026. Conjecture 1 and 2026 update record. ↗ open copy ↗preprint · primary source · arXiv:2504.20539, checked 2026-08-01 · checked 2026-08-01Source use: original summary.Gives the problem statement, definitions, status discussion, and the authors’ update record.Also cited at Afonso S. Bandeira, Anastasia Kireeva, Antoine Maillard, and Almut Rödder, “Randomstrasse101: Open Problems of 2024,” arXiv:2504.20539, version dated 22 March 2026. Conjecture 1 and 2026 update record.Source used to assess the problem's recorded status.For Matrix Spencer discrepancy conjecture: This is the dated publication status for the canonical target Matrix Spencer discrepancy conjecture.Source named by the research packet.
Bansal, Nikhil, Jiang, Haotian, and Meka, Raghu, “Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank”. arXiv (2022). DOI 10.48550/arXiv.2208.11286. Abstract and main theorem. ↗ open copy ↗preprint · primary source · arXiv:2208.11286, checked 2026-08-01 · checked 2026-08-01Source use: original summary.Proves the full conjectured order for matrices of rank at most n/log^3 n.Source used to assess the problem's recorded status.For Matrix Spencer discrepancy conjecture: Proves the full conjectured order for matrices of rank at most n/log^3 n.

Original TheoremDB statement and summary based on citation-only scholarly sources; no source prose, proof, table, code, or figure is reproduced.

[#P3120] Matrix Spencer discrepancy conjecture

1Context

2Problem setup

3What counts as a solution

1Status

1Records

2See also

1Lean verification

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Records

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance