Sorting $X+Y$ (Pairwise Sums)

Research-attempt provenance

Definitions and mathematical statement

The input consists of two lists of real numbers $X=(x_1,\ldots,x_n)$ and $Y=(y_1,\ldots,y_n)$. Form the $n^2$ labelled pairwise sums $s_{ij}=x_i+y_j$. The required output orders all pairs $(i,j)$ so that their sums are nondecreasing; equal sums may be ordered arbitrarily. Keeping labels avoids ambiguity about whether repeated values disappear from the output.

Determine the smallest worst-case running time of a uniform algorithm for this task in the real-arithmetic comparison model. In particular, can the obvious $O(n^2\log n)$ sorting time be reduced to $O(n^2)$, which matches the size of the explicit output?

The special additive structure permits far fewer possible orderings than arbitrary unrelated lists of $n^2$ real numbers. However, a bound on the number of comparisons alone is insufficient: the time needed to choose each comparison and manage the partial order must also be charged. The source records quadratic-comparison methods, so a generic comparison-count lower bound does not settle the algorithmic question.

The inputs are unrestricted real numbers. Methods relying on small integer ranges must account for the range parameter separately. Reporting only distinct sums is a related output convention, rather than the labelled sorting task fixed here.

Short English statement

Can all pairwise sums of two real-number lists be explicitly sorted in quadratic total time, including the work needed to choose comparisons?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 5500041 (AMR-054-0041), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problems Project - Computational Geometry, Problem 41. Original source indexed by AMR-054-0041. https://topp.openproblem.net/p41.

Literature and context check

The consulted TOPP Problem 41 page explicitly distinguishes quadratic comparison bounds from the cost of choosing comparisons. Its stated elementary total-time bound retains a logarithmic factor. The supplied prior summary claiming a quadratic-time solution and then asking for subquadratic explicit output contradicts both this distinction and the labelled output convention; neither assertion is adopted here.

Research attempt: The frontier-selection cost remains after exploiting monotonicity

Sort $X,Y$ first, keeping their original labels. The matrix $M_{ij}=x_i+y_j$ is nondecreasing in both coordinates. Maintaining the first unreported item of every row in a binary heap gives a correct merge: every unreported item is at least its own row head, so the minimum head is globally minimum. Extract it and insert its row successor, if any. There are $n^2$ outputs, each with $O(\log(n+1))$ heap work, plus initial sorting. This proves $O(n^2\log(n+1))$ time and $O(n)$ auxiliary space in addition to output. Equal sums cause no difficulty if a deterministic label tie rule is used.

The attempted improvement was to sweep grid antidiagonals, replacing the heap by a known index order. It fails even for sorted nonnegative input. With \[ X=(0,1,100),\qquad Y=(0,2,3), \] using zero-based indices, $M_{20}=100$ lies on antidiagonal two, whereas $M_{12}=4$ lies on antidiagonal three. Emitting all of one antidiagonal before the next is not valid. Nor can the rows be permanently ordered by $x_i$: $M_{02}=3>M_{10}=1$. Monotonicity constrains predecessors in the partial order, but leaves a frontier of incomparable positions to be selected.

There is more information in additivity than in the grid alone: \[ x_i+y_j<x_k+y_\ell\quad\Longleftrightarrow\quad x_i-x_k<y_\ell-y_j. \] Thus one might sort all $n^2$ differences in each input to answer many later comparisons by ranks. But forming and conventionally sorting those differences already costs $O(n^2\log(n+1))$ time. The reduction has relocated the disputed cost, not removed it; ties also need consistent equality handling. Treating the precomputed difference order as free advice would violate uniformity.

For a genuine easy subcase, suppose $X$ is sorted and every consecutive gap $x_{i+1}-x_i$ is at least $y_n-y_1$. Then $x_i+y_n\le x_{i+1}+y_1$, so the sorted rows concatenate in order. After sorting the inputs, the output can be written in $\Theta(n^2)$ time. Checking the gap condition costs $O(n)$. This calculation identifies exactly the missing separation invariant in arbitrary inputs; the example above does not satisfy it. It supplies no uniform algorithm when rows interleave.

Verification and adversarial audit

The heap invariant was checked at initialization, extraction and row exhaustion. Both invalid sweeps have numerical counterexamples. Duplicate inputs, $n=1$, zero row gaps and equality in the row-separation condition are covered by arbitrary label order within ties. Explicit output alone requires $n^2$ label writes in the stated model.

Audit corrections.

Quadratic comparisons were separated from quadratic running time; the original explicit labelled-output target was not replaced by distinct-sum enumeration.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

The first gap is choosing and updating the minimum of the interleaving frontier with only constant amortized total work per labelled output, or another uniform method that pays for its comparison choices. A comparison-count theorem or a free ordering of all differences does not supply that work bound.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://topp.openproblem.net/p41 (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration and repository-format review; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved. This is a research attempt with an explicit failed route or restricted calculation, not a full solution, not a current-status certification, and not a claim that the elementary material is new. The catalogue's original source-status label is preserved independently of this attempt status.