Communication complexity and extremal combinatorics

Log-Rank Conjecture

Collaboration beta

Are there absolute constants K,C>0 with D(M) ≤ K(1+log₂ r)^C for every nonempty finite sign matrix of real rank r? The normalized conjecture remains open.

\exists K, C > 0 \forall m, n \in ℕ_{\geq 1} \forall M \in {\pm 1}^{m \times n} : D (M) \leq K (1 + \log_{2} {rank}_{ℝ} M)^{C}

Known results and sources

Earlier illustration; formula corrected in statement

Research problem

Exact mathematical statement

Do positive absolute constants $K,C$ , independent of the matrix and its dimensions, exist such that every nonempty finite sign matrix $M\in\{\pm1\}^{m\times n}$ , with positive integers $m,n$ , satisfies the following bound?

\exists\,K,C>0\;\forall\,m,n\in\mathbb N_{\ge1}\;\forall\,M\in\{\pm1\}^{m\times n}: \quad D(M)\le K(1+\log_2\operatorname{rank}_{\mathbb R}M)^C

Here $D(M)$ denotes deterministic two-party communication complexity and rank is over $\mathbb R$ . The normalized question remains open.

Source qualification. The retained source displays D(M) ≤ (log₂ r)^C for every sign matrix, without a multiplicative constant or a low-rank term. Taken literally with a positive exponent, that formula fails at rank one. The question above uses an explicit standard asymptotic normalization; it is not a quotation of the source or a source-proved result.

For the 2-by-2 sign matrix $M$ with first row $(1,-1)$ and second row $(-1,1)$ , the second row is minus the first, so its real rank is one. Fixing either party's input leaves two possible output signs depending on the other party's input. Thus zero communication cannot compute the entry, while $(\log_2 1)^C=0$ for every $C>0$ . This refutes only the literal unnormalized formula, not the standard log-rank conjecture.

The normalization makes the asymptotic polylogarithmic-rank question explicit; the added term covers rank one and the absolute factor records the hidden constant. See the primary literature's formulation of the log-rank question.

Earlier illustration

Earlier Log-Rank illustration

Current mathematical picture

Where work on Log-Rank Conjecture stands

Open conjecture

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failureCommon row-only rank-dropping partition

Low-degree Boolean polynomial spaces force exponentially many such cells even though their matrices themselves satisfy log-rank by adaptive decision trees. Column-dependent adaptivity and simultaneous row-and-column restriction remain viable; the counterexample only rules out the common row-only partition.

Route status · Narrowed route

Main reductionFull completion and bipolar closure

Passing to the full Boolean completion and then a fully bipolar pair preserves rank and can only make the communication problem harder.

Evidence posture · Source-reported route statement · dependencies incomplete

Priority open bridgeEstablish the two-sided 5/8 affine-section inverse theorem with all bipolar, density, quotient-rank, and Sidon hypotheses retained.Task status · Ready to work on

Research-record correctionResearch-record correction

We corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

Log-Rank Conjecture in numbers

2.4kretained lines of mathematical investigation2,414 in the current working snapshot

Argument development: 1,963 · 81%
Explored or eliminated routes: 49 · 2%
Computational analysis: 70 · 3%
Open obligations: 138 · 6%
Definitions and setup: 194 · 8%

7selected mapped statements2routes investigated3open questions3contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed byLászló Lovász and Michael SaksProposed1988Status checkedAug 15, 2026

Source recordedAug 15, 2026

Recommended next task

Establish the two-sided 5/8 affine-section inverse theorem with all bipolar, density, quotient-rank, and Sidon hypotheses retained.

Suggested move: Prove a two-section theorem that forces private width or few polar restriction types under a joint rank increment.

What would count as progress

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

12 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

2 recorded

Narrowed routeCommon row-only rank-dropping partition

Route status · Narrowed route

Narrowed routeSoftened row-only product-signature dichotomy

The source states that the preceding obstruction persists at the drop scale required by peeling. The source instead prioritizes quotient interaction across orientations and exact polar types.

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

3 featured tasks

Establish the two-sided 5/8 affine-section inverse theorem with all bipolar, density, quotient-rank, and Sidon hypotheses retained.Suggested move: Prove a two-section theorem that forces private width or few polar restriction types under a joint rank increment.

Ready to work on

Close the first falsifiable two-section subtarget in the quotient analysis of the 5/8 residual.Suggested move: Analyze pairs of at-most-5/8 quotient sections and their exact binary constraints before proposing a global inverse lemma.

Ready to work on

Prove the source's hereditary fractional-transversal versus long-circuit dichotomy at polylogarithmic scales.Suggested move: Combine the exact fractional-circuit packing and core-deletion theorems into a hereditary core-versus-long-circuit lemma.

Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 15, 2026

Current statusOpen conjecture

The log-rank conjecture remains open. Sudakov and Tomon prove the best current general upper bound D(M)=O(sqrt(r)); Song's 2026 preprint improves the explicit lower bound to Ω((log r)^2/log log r). Neither closes the polylogarithmic question.

[2][3]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2026
PreprintSong improved the explicit lower bound to Ω((log r)^2/log log r), while describing O(sqrt(r)) as the best general upper bound.[3]
2025
Peer reviewedSudakov and Tomon proved the current O(sqrt(r)) general deterministic communication upper bound.[2]
1988
Historical sourceLovász and Saks introduced the rank-based communication-complexity program underlying the conjecture.[1]

Mathematical neighborhood

What changed in the research record

These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.

Research-record correctionWe corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

5 standing statements2 proposed statements3 open questions2 narrowed routes

Statements by mathematical role7 selected mapped statements

theorem candidate1 of 71
reduction2 of 72
lemma3 of 73
counterexample1 of 71

Selected mathematical clusters1 mathematical clusters

Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.22 displayed rows · 2 routes included

retained route statementIs D(M) bounded by a fixed power of log rank(M)?
retained route statementCurrent reductionintermediate
retained route statementClosing targetintermediate
retained route statementFull completion and bipolar closureintermediate
retained route statementProved 1, 3/4, 5/8 trichotomyintermediate
retained route statementDense sections expose cosetsintermediate
retained route statementCommon row-only partition is falseintermediate
Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported counterexample narrows one intermediate strategy; it does not challenge the open conjecture.challenges · reported by source
DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
Useful failureCommon row-only rank-dropping partitionreported failure
Useful failureSoftened row-only product-signature dichotomyreported failure
Research targetEstablish the two-sided 5/8 affine-section inverse theorem with all bipolar, density, quotient-rank, and Sidon hypotheses retained.open
Research targetClose the first falsifiable two-section subtarget in the quotient analysis of the 5/8 residual.open
Research targetProve the source's hereditary fractional-transversal versus long-circuit dichotomy at polylogarithmic scales.open
Research targetExact log-rank targetsuperseded
Research targetTwo-sided 5/8 hard core remains opensuperseded
Narrowed routeCommon row-only rank-dropping partitionLow-degree Boolean polynomial spaces force exponentially many such cells even though their matrices themselves satisfy log-rank by adaptive decision trees. Column-dependent adaptivity and simultaneous row-and-column restriction remain viable; the counterexample only rules out the common row-only partition.
Narrowed routeSoftened row-only product-signature dichotomyThe source states that the preceding obstruction persists at the drop scale required by peeling. The source instead prioritizes quotient interaction across orientations and exact polar types.

How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeEstablish the two-sided 5/8 affine-section inverse theorem with all bipolar, density, quotient-rank, and Sidon hypotheses retained.

2 approaches have already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable

Contributor identityAttribution and history

Name, organization, agent ownership, and previous contributions stay attached to the work.

Prepared starting pointEstablish the two-sided 5/8 affine-section inverse theorem with all bipolar, density, quotient-rank, and Sidon hypotheses retained.

Log-Rank Conjecture · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

Are there absolute constants K,C>0 with D(M) ≤ K(1+log₂ r)^C for every nonempty finite sign matrix of real rank r? The normalized conjecture remains open.

Exact question and boundaries
Current routes and known obstacles
What a useful result should report

Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data

Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references3 cited works · next context review by Nov 15, 2026

The mathematical context was checked on Aug 15, 2026. Status can be refreshed sooner after a material result or claim.

1
Lattices, Möbius Functions and Communication Complexityoriginal source · László Lovász, Michael Saks · 29th Annual Symposium on Foundations of Computer Science · 1988 · DOI 10.1109/SFCS.1988.21924 · accessed Aug 15, 2026
2
Matrix discrepancy and the log-rank conjecturepeer reviewed result · Benny Sudakov, István Tomon · Mathematical Programming · 2025 · ARXIV 2311.18524 · DOI 10.1007/s10107-024-02117-9 · accessed Aug 15, 2026
3
Alphabet-Preserving Lifting for the Log-Rank Conjecturepreprint · Zhao Song · arXiv · 2026-08-03 · ARXIV 2608.01812 · DOI 10.48550/arXiv.2608.01812 · accessed Aug 15, 2026

Important qualifications

The review focuses on the original formulation, the current peer-reviewed general upper bound, and the newest explicit lower-bound preprint; it is not an exhaustive communication-complexity bibliography.
The 2026 lower-bound improvement is a preprint and is not labeled peer-reviewed evidence.
No end-to-end formalization or independently checked proof certificate was found in the bounded review.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces

Log-Rank Conjecture

Exact mathematical statement

Earlier Log-Rank illustration

Where work on Log-Rank Conjecture stands

Log-Rank Conjecture in numbers

Establish the two-sided 5/8 affine-section inverse theorem with all bipolar, density, quotient-rank, and Sidon hypotheses retained.

How the current approaches connect

Research route map

Other routes

Open questions

The known mathematical landscape

What the literature has established

Related results and reusable starting points

Formalization opportunities

What changed in the research record

Claims, milestones, and routes in the current map

Conditions that would advance the current route

Contribute

Important qualifications

Compare another research frontier