# P3120: Matrix Spencer discrepancy conjecture

- ID: `P3120`
- Reference: `matrix-spencer-discrepancy`
- Page: https://theoremdb.org/statements/P3120
- Record maturity: Reviewed problem with recorded work

## 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\)?

### Context

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.

### Problem setup

- **Definition (Self-adjoint matrix).** Here this means a real symmetric square matrix.
- **Definition (Operator norm).** \(\|A\|_{\mathrm{op}}=\sup_{\|x\|_2=1}\|Ax\|_2\).
- **Remark.** This is a noncommutative analogue of Spencer vector discrepancy.

### What 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.

## 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. [1](#reference-1) [2](#reference-2)

## Work

### Evidence for the current status

**Claim 1 (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.

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.

### Background and intake notes

- 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.
- The release review checked 2 structured sources on 2026-08-01.
- 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.

### Other known results

- **Claim 2** (supported): 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](#reference-1) [2](#reference-2)

### Prior approaches

- **Route 1** (supported): 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](#reference-1) [2](#reference-2)

### Open directions

- **Route 2** (reported): Remove the logarithmic loss without rank or commutativity hypotheses.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `matrix-spencer-discrepancy`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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 https://doi.org/10.48550/arXiv.2504.20539
   - 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
   - preprint; primary source; arXiv:2504.20539, checked 2026-08-01; checked 2026-08-01
   - Open copy: https://arxiv.org/abs/2504.20539
   - Source use: original_summary
   - Gives the problem statement, definitions, status discussion, and the authors’ 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.
2. <a id="reference-2"></a>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 https://doi.org/10.48550/arXiv.2208.11286
   - preprint; primary source; arXiv:2208.11286, checked 2026-08-01; checked 2026-08-01
   - Open copy: https://arxiv.org/abs/2208.11286
   - Source 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.