ProofAtlas

Signed complete graphs · discrepancy · covering radii · finite-temperature methods

Minimum Overlap Problem

Collaboration beta

Choose plus or minus signs on every edge of a complete graph to make every two-way vertex signing have small total interaction. The open question asks whether the best possible worst interaction, divided by n^(3/2), approaches a limit.

limn→∞Fnn3/2exists
Known results and sources
A complete signed graph and a cube of vertex signings feed a balance scale whose normalized discrepancy sequence stops before an open limit marker.
The minimum signed-graph discrepancy is known within asymptotic bounds, while convergence of its normalized value remains open.

Research problem

Exact mathematical statement

For a symmetric zero-diagonal sign matrix A=(aij)A=(a_{ij}), with aij=aji∈{±1}a_{ij}=a_{ji}\in\{\pm1\} for i≠ji\ne j, set

QA(x)=∑1≤i<j≤naijxixj,D(A)=maxx∈{±1}n|QA(x)|,Q_A(x)=\sum_{1\le i<j\le n}a_{ij}x_i x_j,\qquad \mathcal D(A)=\max_{x\in\{\pm1\}^n}|Q_A(x)|,

and let Fn=minAD(A)F_n=\min_A\mathcal D(A). The Minimum Overlap Problem asks whether

limn→∞Fnn3/2\lim_{n\to\infty}\frac{F_n}{n^{3/2}}

exists. The source records this target as open and requires that all factors of two be checked against the convention that QAQ_A counts each undirected edge once.

Problem infographic

Problem at a glance

Four-stage diagram from signed complete graphs through finite-temperature bridge and cross experiments to an unresolved reverse max-information inequality and the desired normalized limit.
Exact identities connect the discrepancy problem to matched information budgets; the linear-scale comparison between them is still open.

Current mathematical picture

Where work on Minimum Overlap Problem stands

Open problem

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

Useful failureOrdinary total-variation clustering as reverse max-information control

Near a minimizing output, additive coupling error can dominate the tiny output probability, so a multiplicative likelihood-ratio or localized one-point estimate is required. Pointwise BSC-output domination, a one-point likelihood-ratio test, or same-orbit allocation remains viable within the source's stated boundaries.

Route status · Narrowed route
Main reductionCurrent reduction

At each fixed temperature, exact bridge and cross reverse max-information identities reduce the desired two- and three-dilation bounds to one same-center inequality, MOP-DINF-CLOSURE; obtaining it for both dilation factors on one common unbounded temperature set would imply convergence of the zero-temperature sequence.

Evidence posture · Source-reported route statement · dependencies incomplete
Priority open bridgeCombine row and column one-point tests without double-counting their shared matrix entries and recover two bridge budgets up to sublinear logarithmic cost.Task status · Ready to work on

Work mapped so far

Minimum Overlap Problem in numbers

1.1kretained lines of mathematical investigation1,081 in the current working snapshot
Argument development
864 · 80%
Explored or eliminated routes
13 · 1%
Computational analysis
9 · 1%
Open obligations
157 · 15%
Definitions and setup
38 · 4%
8selected mapped statements1routes investigated4open questions4contribution-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 byPaata IvanisviliProposed2022Status checkedJan 16, 2022
Source recordedAug 30, 2026

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

13 selected steps

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

13 selected steps

Scroll horizontally to explore the route

Working route overview for Minimum Overlap ProblemA selected map of recorded claims, active routes, useful failures, open questions, and their explicit relationships. Search, filter, zoom, or pan within this page.Does the normalized minimum signed-complete-graph discrepancy have a limit? — Depends on missing premiseDoes the normalized minimumsigned-complete-graphdiscrepancy…Canonical signing and augmented cut code — Depends on missing premiseCanonical signing andaugmented cut codeCurrent reduction — Depends on missing premiseCurrent reductionFinite-temperature dilation reduction — Depends on missing premiseFinite-temperature dilationreductionMatched reverse max-information budgets — Depends on missing premiseMatched reversemax-information budgetsAudited asymptotic interval — Depends on missing premiseAudited asymptotic intervalClosing target — Depends on missing premiseClosing targetFinite-order values and witnesses — Depends on missing premiseFinite-order values andwitnessesOrdinary total-variation clustering as reverse max-information control — stoppedOrdinary total-variationclustering as reversemax-information…Combine row and column one-point tests without double-counting their shared matrix entries and recover two bridge budgets up to sublinear logarithmic cost. — OpenCombine row and columnone-point tests withoutdouble-counting…Turn projective or antipodal clustering into multiplicative control of the exponentially small minimizing BSC output, not merely additive or total-variation control. — OpenTurn projective or antipodalclustering intomultiplicative…Keep both dilation factors on one common unbounded temperature set while preserving same-center bridge/cross bindings and an exponent strictly below one after every accumulated error. — OpenKeep both dilation factorson one common unboundedtemperature…Reverse max-information closure — OpenReverse max-informationclosure
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

1 recorded
Narrowed routeOrdinary total-variation clustering as reverse max-information control

Near a minimizing output, additive coupling error can dominate the tiny output probability, so a multiplicative likelihood-ratio or localized one-point estimate is required. Pointwise BSC-output domination, a one-point likelihood-ratio test, or same-orbit allocation remains viable within the source's stated boundaries.

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

4 featured tasks
01
Combine row and column one-point tests without double-counting their shared matrix entries and recover two bridge budgets up to sublinear logarithmic cost.Suggested move: Test checkerboard, fractional-product, deepest-output Markov-kernel, and synchronization-corrected constructions on the exact product and antipodal calibrations.
Ready to work on
02
Turn projective or antipodal clustering into multiplicative control of the exponentially small minimizing BSC output, not merely additive or total-variation control.Suggested move: Develop a likelihood-ratio truncation, hypercontractive smoothing estimate, exact component cancellation, or localized one-point test that is uniform over outputs in the required tail regime.
Ready to work on
03
Reverse max-information closure

The source identifies MOP-DINF-CLOSURE as the first genuinely open theorem: the cross reverse max-information must dominate k bridge budgets with sublinear error for both dilation factors on one common unbounded temperature set.

Suggested move: Resolve the exact source-reported obligation without treating it as an established negative result.
Ready to work on
04
Keep both dilation factors on one common unbounded temperature set while preserving same-center bridge/cross bindings and an exponent strictly below one after every accumulated error.Suggested move: Audit every proposed inequality for its temperature set, first-argument D-infinity orientation, native-minimizer identity, small-beta range, and final summed exponent.
Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 30, 2026
Current statusOpen problem

Historical source posture only: the 2022 original post asks whether the normalized min-max quadratic-form sequence has a limit and does not present a proof of existence or nonexistence. This field does not independently establish the problem's status after 2022-01-16.

[1]
External progress

What the literature has established

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

  1. Historical sourceIvanisvili posed the exact limit-existence question for the minimum, over upper-triangular sign choices, of the maximum absolute quadratic form on the Boolean cube.[1]
1 cited sources0 related results or reductionsReferences

Mathematical neighborhood

Related results and reusable starting points

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

  • Formalization targetA formal statement must fix the upper-triangular or symmetric zero-diagonal normalization so each undirected pair contributes exactly once.
  • Formalization targetA formal asymptotic treatment needs the finite sign-matrix minimization, Boolean-cube maximum, n^(3/2) normalization, and convergence of the resulting real sequence.
  • Formalization targetAny finite computation or asymptotic bound must remain separate from proof that the normalized sequence converges.

Detailed research inventory

Claims, milestones, and routes in the current map

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

6 standing statements2 proposed statements4 open questions1 narrowed routes
Statements by mathematical role8 selected mapped statements
  • theorem candidate1 of 81
  • reduction2 of 82
  • lemma2 of 82
  • equivalence2 of 82
  • computational claim1 of 81
Selected mathematical clusters1 mathematical clusters
Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.21 displayed rows · 1 route included
  • retained route statementDoes the normalized minimum signed-complete-graph discrepancy have a limit?
  • retained route statementCurrent reductionintermediate
  • retained route statementClosing targetintermediate
  • retained route statementCanonical signing and augmented cut codeintermediate
  • retained route statementAudited asymptotic intervalintermediate
  • retained route statementFinite-temperature dilation reductionintermediate
  • retained route statementMatched reverse max-information budgetsintermediate
  • retained route statementFinite-order values and witnessesintermediate
  • 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 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
  • 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 failureOrdinary total-variation clustering as reverse max-information controlreported failure
  • Research targetCombine row and column one-point tests without double-counting their shared matrix entries and recover two bridge budgets up to sublinear logarithmic cost.open
  • Research targetTurn projective or antipodal clustering into multiplicative control of the exponentially small minimizing BSC output, not merely additive or total-variation control.open
  • Research targetKeep both dilation factors on one common unbounded temperature set while preserving same-center bridge/cross bindings and an exponent strictly below one after every accumulated error.open
  • Research targetReverse max-information closureopen
  • Narrowed routeOrdinary total-variation clustering as reverse max-information controlNear a minimizing output, additive coupling error can dominate the tiny output probability, so a multiplicative likelihood-ratio or localized one-point estimate is required. Pointwise BSC-output domination, a one-point likelihood-ratio test, or same-orbit allocation remains viable within the source's stated boundaries.
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 bridgeCombine row and column one-point tests without double-counting their shared matrix entries and recover two bridge budgets up to sublinear logarithmic cost.

1 approach has 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
Prepared starting pointCombine row and column one-point tests without double-counting their shared matrix entries and recover two bridge budgets up to sublinear logarithmic cost.

Minimum Overlap Problem · 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

Choose plus or minus signs on every edge of a complete graph to make every two-way vertex signing have small total interaction. The open question asks whether the best possible worst interaction, divided by n^(3/2), approaches a limit.

  • 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 references1 cited works · next context review by Nov 30, 2026

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

  1. 1
    Min max of a quadratic form of plus-minus onesoriginal source · Paata Ivanisvili · MathOverflow · 2022-01-16 · accessed Aug 30, 2026

Important qualifications

  • This was a bounded exact-statement search, not an exhaustive literature, priority, rights, authorship, or citation review.
  • The source title is Min max of a quadratic form of plus-minus ones; Minimum Overlap Problem remains in the current research map only as the current work-defined local workspace title and must not be confused with Erdős's distinct minimum overlap problem in additive combinatorics.
  • The status field records only the 2022 source posture: the original MathOverflow post asks whether the limit exists. It does not independently establish the problem's status after 2022-01-16.
  • A bounded search found no statement-aligned primary paper resolving the limit, but a scoped negative search does not prove that no later result or claim exists.
  • No packet attachment was opened, and no URL was discovered or selected from packet contents; every public source was located through an independent search.
  • The bounded search did not establish a statement-aligned formalization, certificate, dataset, or independently reproduced computation. Empty readiness lists do not prove that none exists.

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

Expanded visual

Open original image