Theoretical computer science · fine-grained complexity

Modern 3SUM Hypothesis

Collaboration beta

Do cubic-universe integer 3SUM and reasonable-real 3SUM each resist every truly subquadratic algorithm in their stated machine models?

Modern 3SUM has distinct open integer and reasonable-real targets.

Known results and sources

Do integer word-RAM 3SUM and reasonable-real 3SUM each resist every truly subquadratic algorithm in their stated models?

Research problem

Exact mathematical statement

The current source keeps two targets separate. TARGET-I asks whether exact integer 3SUM on $A,B,C\subseteq[-n^3,n^3]$ , each of size at most $n$ , has no $O(n^{2-\varepsilon})$ -time algorithm for any fixed $\varepsilon>0$ on a $\Theta(\log n)$ -bit word RAM. TARGET-R4 separately asks the analogous question for three sets of immutable input reals when real-dependent queries are limited to the stated three-way 3-linear and 4-linear comparisons plus ordinary word-RAM bookkeeping. In each target's own machine model, the unresolved lower-bound hypothesis is

\text{no }O(n^{2-\varepsilon})\text{-time algorithm for any fixed }\varepsilon>0.

A truly subquadratic algorithm would refute only the target whose machine model it respects; an integer algorithm does not by itself settle TARGET-R4. Neither target is resolved.

Problem infographic

Problem at a glance

A text-free scientific explainer showing the objects, constraints, and unresolved route for Modern 3SUM Hypothesis. — The current route map ends at selected-witness recovery for integer 3SUM and random closed-lens reporting for reasonable-real 3SUM; double-cross slabs remain a secondary open route.

Current mathematical picture

Where work on Modern 3SUM Hypothesis stands

Open problem

V6 separates the integer word-RAM and reasonable-real targets, records source-reported proved front ends only to their exact first open nodes, and keeps all conditional interfaces, scoped barriers, and submitted checks non-authoritative. Neither target is solved.

Leading routePrimary integer route: certified core to restriction-stable witnesses

The source reports the compatible-affine certified front end as internally proved and makes WIT-AFFINE/WIT-RESTRICT the first open node. Affine universality and scoped witness-recovery barriers prevent treating this as a routine last lemma.

Route status · Active route

Useful failureTarget-contour cell delimitation

A cell can lie wholly below the target while remaining inside the sample-adjacent interval; predecessor and successor contours are the correct boundaries. Use both sample endpoint contours and preserve the global cap in every local reporter.

Route status · Eliminated route

Main reductionGcd/resultant normal forms remain exact but secondary

The source retains shifted-gcd and quadratic-extension resultant formulations as exact secondary normal forms, explicitly charges field size and coefficient-algebra work, and leaves fast selected subresultant or masked-product evaluation open.

Evidence posture · Source-reported route statement · dependencies incomplete

Priority open bridgeProve WIT-RESTRICT or a weaker certified-core reporter with output exponent below two.Task status · Ready to work on

Later mathematical updateV6 separates the integer and reasonable-real targets and repairs exact model scope

The source keeps TARGET-I and TARGET-R4 distinct, states their legal machines, and does not let an integer algorithm settle the reasonable-real target.

V6 source revision order; not mathematical occurrence time

Work mapped so far

Modern 3SUM Hypothesis in numbers

2kretained lines of mathematical investigation960 in the current working snapshot

Argument development: 1,511 · 74%
Explored or eliminated routes: 44 · 2%
Computational analysis: 135 · 7%
Open obligations: 275 · 14%
Definitions and setup: 72 · 4%

13selected mapped statements4routes investigated5open questions5contribution-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.

Status checkedAug 28, 2026

Source recordedAug 30, 2026

Recommended next task

Prove WIT-RESTRICT or a weaker certified-core reporter with output exponent below two.

Suggested move: Follow the exact V6 interface, model, distributional posture, output semantics, and falsification checklist without broadening a local result.

What would count as progress

Supply a complete source-independent argument or a precisely scoped counterexample.
Survive independent review of model legality, dependency closure, and every charged setup term.

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

22 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.

Active routePrimary integer route: certified core to restriction-stable witnesses

Route status · Active route

Active routePrimary reasonable-real route: occurrence sampling to random closed lenses

The source reports occurrence sampling, expectation transfer, endpoint geometry, one-sided reporting, and outer-frame closure before the open RANDOM-CLOSED-LENS reporter; DOUBLE-CROSS-SLAB remains secondary.

Route status · Active route

Explored alternatives

Other routes

2 recorded

Eliminated routeTarget-contour cell delimitation

Route status · Eliminated route

Eliminated routeGeneric sparse selected dominance product

Aggregation, occurrence sampling, and cap corrections narrow the object to a coupled difference of two ordered threshold frontiers. Exploit ordered frontier coupling rather than treating the requests as unrelated sparse products.

Route status · Eliminated route

Route statements and reductions

Statements the next route can inspect and build on

Route statementTie-aware occurrence sampling gives the expected real candidate bound

The source reports that uniform pair-occurrence sampling, equality-block handling, and target-gap collapse yield E[K] <= n+2n^3/R, including arbitrary sum multiplicities.

Source-reported route statement · dependencies incomplete

Route statementCompatible-affine dyadic reduction reaches a certified sparse core

The source reports an exact compatible-affine map, collision peeling with exact bad-endpoint scans, zero-degree pruning, a constant-expected-round wrapper, and the resulting certified sparse convolution core. This is a source-reported proved front end, not an independently checked ProofAtlas result.

Source-reported route statement · dependencies incomplete

Route statementRestriction-stable selected-witness recovery is the first integer open node

WIT-AFFINE and the sufficient WIT-RESTRICT interface ask for shared recovery after output-specific exclusions; any certified-core reporter with output exponent below two yields a truly subquadratic exact Las Vegas TARGET-I algorithm.

Source-reported route statement · dependencies incomplete

Route statementRANDOM-CLOSED-LENS is the first reasonable-real open node

For every fixed input under the actual outer-frame-augmented sample law, the open target is an exact MODEL-R4 reporter with expected O~(n+E[K]) cost; the source does not claim a pointwise theorem for arbitrary lenses.

Source-reported route statement · dependencies incomplete

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

5 featured tasks

Prove WIT-RESTRICT or a weaker certified-core reporter with output exponent below two.Suggested move: Follow the exact V6 interface, model, distributional posture, output semantics, and falsification checklist without broadening a local result.

Ready to work on

Prove RANDOM-CLOSED-LENS under the actual outer-frame-augmented sample law.Suggested move: Follow the exact V6 interface, model, distributional posture, output semantics, and falsification checklist without broadening a local result.

Ready to work on

Build target-specific prefix reuse or shared laminar restricted counts after output-specific exclusions.Suggested move: Follow the exact V6 interface, model, distributional posture, output semantics, and falsification checklist without broadening a local result.

Ready to work on

Build an implicit frontier longest-common-extension operation shared across occupied gaps.Suggested move: Follow the exact V6 interface, model, distributional posture, output semantics, and falsification checklist without broadening a local result.

Ready to work on

Prove DOUBLE-CROSS-SLAB(theta,eta) with a fixed saving in both non-output terms.Suggested move: Follow the exact V6 interface, model, distributional posture, output semantics, and falsification checklist without broadening a local result.

Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 28, 2026

Current statusOpen problem

Known algorithms beat n^2 by logarithmic factors, so the older exact-quadratic conjecture is false. The model-specific assertion that no O(n^(2-epsilon)) algorithm exists for any fixed epsilon remains an open fine-grained hypothesis in the cited sources.

[1][2]

External progress

What the literature has established

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

2018
Peer reviewedChan improved logarithmic factors while explicitly retaining the no-O(n^(2-epsilon)) conjecture as the modern fine-grained hypothesis.[2]
2014
PreprintGrønlund and Pettie gave logarithmically subquadratic algorithms, refuting an older exact-quadratic formulation but not an n^(2-epsilon) lower-bound hypothesis.[1]

Mathematical neighborhood

What changed after the initial research map

Later recorded revisions that changed the mathematics, without inventing a date or an AI attribution.

V6 separates the integer and reasonable-real targets and repairs exact model scopeThe source keeps TARGET-I and TARGET-R4 distinct, states their legal machines, and does not let an integer algorithm settle the reasonable-real target.

Changed the research frontierLater mathematical revision

V6 source revision order; not mathematical occurrence time

V6 replaces the route portfolio with audited conditional chains and scoped barriersThe update preserves source-reported proved-front-end boundaries, expectation and gcd/resultant repairs, failed architectures, work orders, and inert artifact evidence without claiming resolution.

Changed the research frontierLater mathematical revision

V6 source revision order; not mathematical occurrence time

V6 isolates one first open interface on each active branchThe integer branch stops at restriction-stable selected-witness recovery, while the real branch stops at RANDOM-CLOSED-LENS or the weaker double-cross interface.

Changed the research frontierLater mathematical revision

V6 source revision order; not mathematical occurrence time

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.

8 standing statements5 proposed statements5 open questions

Statements by mathematical role13 selected mapped statements

theorem candidate3 of 133
reduction3 of 133
lemma4 of 134
equivalence1 of 131
negative result2 of 132

Selected mathematical clusters1 mathematical clusters

V6 two-target research mapThe recorded V6 overview keeps TARGET-I and TARGET-R4 separate, preserves exact source-reported proved-front-end boundaries, exposes the first open interface on each branch, retains expectation and gcd/resultant repairs, and scopes all negative route evidence without claiming a solution.30 displayed rows · 2 routes included

retained route statementModern 3SUM has distinct integer and reasonable-real targets
retained route statementTwo source-reported conditional front ends stop at separate first open interfacesintermediate
retained route statementImmediate next action is WIT-RESTRICT or RANDOM-CLOSED-LENSintermediate
retained route statementMODEL-R4 permits only exact three-way 3-linear and 4-linear sign queriesintermediate
retained route statementTie-aware occurrence sampling gives the expected real candidate boundintermediate
retained route statementEndpoint contours and the outer frame replace target-contour delimitationintermediate
retained route statementOne-sided cells have an output-sensitive extreme-corner heap reporterintermediate
retained route statementCompatible-affine dyadic reduction reaches a certified sparse coreintermediate
retained route statementRestriction-stable selected-witness recovery is the first integer open nodeintermediate
retained route statementExpectation transfer distinguishes all-input reporters from promise-only capped reportersintermediate
retained route statementGcd/resultant normal forms remain exact but secondaryintermediate
retained route statementRANDOM-CLOSED-LENS is the first reasonable-real open nodeintermediate
retained route statementSecond-audit repairs narrow earlier overclaims and restore missing chargesintermediate
Recorded relationshipThe source isolates restriction-stable witness recovery as the common unresolved search problem after the two front ends; the reduction remains conditional and does not prove either 3SUM target.supports · reported by source
Recorded relationshipThe exact wrapper's positive-degree selected outputs, exact degrees, fine targets, provenance, and load bound form the certified integer core consumed by the selected-witness interface.supports · reported by source
Recorded relationshipWIT-AFFINE asks for exact selected-predicate recovery, and the source proves only the conditional exponent transfer from any reporter with exponent below two; the reporter itself remains open.supports · reported by source
Recorded relationshipTie-aware pair-occurrence sampling gives the expected candidate bound that supplies the real route's output term, including arbitrary sum multiplicities.supports · reported by source
Recorded relationshipOuter-frame sampling converts remaining gap regions into closed lenses, after which the distributional RANDOM-CLOSED-LENS reporter is the explicit unresolved step.supports · reported by source
DerivationThe source gives conditional exponent transfers from each named open reporter to its corresponding target. Because both reporters remain open and the targets use different models, this is only a conditional route map.active reported
Useful failureGeneric pointwise sparse interval coverreported failure
Useful failureSecondary modulus as an independent exponent leverreported failure
Useful failureTwenty-two compact no-revisit architecturesreported failure
Research targetProve WIT-RESTRICT or a weaker certified-core reporter with output exponent below two.open
Research targetProve RANDOM-CLOSED-LENS under the actual outer-frame-augmented sample law.open
Research targetProve DOUBLE-CROSS-SLAB(theta,eta) with a fixed saving in both non-output terms.open
Research targetBuild target-specific prefix reuse or shared laminar restricted counts after output-specific exclusions.open
Research targetBuild an implicit frontier longest-common-extension operation shared across occupied gaps.open
ComputationThe V6 packet reports scripts, logs, manifests, and active-proof files for identities, small cases, barriers, and packet consistency.The governing source says its scripts test finite carry, modular, masked-product, and geometric cases and explicitly classifies them as regression tests rather than proofs. ProofAtlas did not execute or independently reproduce them during intake. · reported unreproduced
Active routePrimary integer route: certified core to restriction-stable witnessesThe source reports the compatible-affine certified front end as internally proved and makes WIT-AFFINE/WIT-RESTRICT the first open node. Affine universality and scoped witness-recovery barriers prevent treating this as a routine last lemma.
Active routePrimary reasonable-real route: occurrence sampling to random closed lensesThe source reports occurrence sampling, expectation transfer, endpoint geometry, one-sided reporting, and outer-frame closure before the open RANDOM-CLOSED-LENS reporter; DOUBLE-CROSS-SLAB remains secondary.

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 bridgeProve WIT-RESTRICT or a weaker certified-core reporter with output exponent below two.

The current research map records this as an open mathematical step.

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 source-independent argument or a precisely scoped counterexample.
Survive independent review of model legality, dependency closure, and every charged setup term.

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 pointProve WIT-RESTRICT or a weaker certified-core reporter with output exponent below two.

Modern 3SUM Hypothesis · 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

Do cubic-universe integer 3SUM and reasonable-real 3SUM each resist every truly subquadratic algorithm in their stated machine models?

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 references2 cited works · next context review by Nov 28, 2026

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

1
Threesomes, Degenerates, and Love Trianglespreprint · Allan Grønlund, Seth Pettie · arXiv · 2014-04-03 · ARXIV 1404.0799 · accessed Aug 28, 2026
2
More Logarithmic-Factor Speedups for 3SUM, (median,+)-Convolution, and Some Geometric 3SUM-Hard Problemspeer reviewed result · Timothy M. Chan · ACM Transactions on Algorithms · 2018 · DOI 10.1145/3180484 · accessed Aug 28, 2026

Important qualifications

This was a bounded primary-source and publisher-record search, not an exhaustive literature, priority, citation, rights, or authorship review.
Open status means that the cited source states or studies the problem as a conjecture or open problem and the bounded search found no statement-aligned primary resolution; it does not prove that no later claim exists.
Recent preprints are recorded only with their stated preprint posture and are not treated as peer-reviewed or independently verified.
No submitted attachment, submitted URL, packet-reported computation, or model output was treated as independent external authority.
No statement-aligned formalization, certificate, or independently reproduced computation was established by this search.

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

Modern 3SUM Hypothesis

Exact mathematical statement

Problem at a glance

Where work on Modern 3SUM Hypothesis stands

Modern 3SUM Hypothesis in numbers

Prove WIT-RESTRICT or a weaker certified-core reporter with output exponent below two.

How the current approaches connect

Research route map

Other routes

Statements the next route can inspect and build on

Open questions

The known mathematical landscape

What the literature has established

Related results and reusable starting points

Formalization opportunities

What changed after the initial research map

Claims, milestones, and routes in the current map

Conditions that would advance the current route

Contribute

Important qualifications

Compare another research frontier