OP-01087 Needs verification

Sorting X+Y

Needs verification: A solution is claimed (Mundhra, 2025); held until the record of the claim is listed here.

For sets $X$ and $Y$ of $n$ real numbers each, let $$X+Y = \{x+y \mid x \in X,\ y \in Y\}.$$

Sorting the $n^2$ sums directly takes $O(n^2\log n)$ time, and no faster algorithm is known. Fredman showed that $8n\log n + 2n^2$ comparisons suffice, but choosing them took exponential time; Kahn and Kim brought this overhead down to polynomial time, and Lambert and Steiger and Streinu to $O(n^2\log n)$, so no superquadratic lower bound holds in the linear decision tree model. Fredman, Dietzfelbinger and Erickson proved $\Omega(n^2)$ lower bounds in restricted forms of that model. For integers in $[-M, M]$, an algorithm of Seidel based on the fast Fourier transform runs in $O(n + M\log M)$ time.

Problem. How fast can $X+Y$ be sorted? In particular, can the logarithmic factor be removed, that is, can $X+Y$ be sorted in $O(n^2)$ time?

Source: Berlekamp, according to Fredman (1976); Problem 41 of The Open Problems Project (Demaine, Mitchell and O'Rourke).

Imported from topp.openproblem.net.

Classification

Primary: CO — Combinatorics
Keywords: pairwise sums, sorting X+Y, The Open Problems Project

References

@article{fredman1976,
  author  = {Fredman, M. L.},
  title   = {How good is the information theory bound in sorting?},
  journal = {Theoret. Comput. Sci.},
  volume  = {1},
  year    = {1976},
  pages   = {355--361}
}

@article{kahn1995,
  author  = {Kahn, Jeff and Kim, Jeong Han},
  title   = {Entropy and Sorting},
  journal = {J. Comput. Sys. Sci.},
  volume  = {51},
  year    = {1995},
  pages   = {390--399}
}

@article{lambert1992,
  author  = {Lambert, Jean-Luc},
  title   = {Sorting the sums $(x_i+y_j)$ in {$O(n^2)$} comparisons},
  journal = {Theoret. Comput. Sci.},
  volume  = {103},
  year    = {1992},
  pages   = {137--141}
}

@article{steiger1995,
  author  = {Steiger, W. and Streinu, Ileana},
  title   = {A pseudo-algorithmic separation of lines from pseudo-lines},
  journal = {Inform. Process. Lett.},
  volume  = {53},
  year    = {1995},
  pages   = {295--299}
}

@article{dietzfelbinger1989,
  author  = {Dietzfelbinger, M.},
  title   = {Lower Bounds for Sorting of Sums},
  journal = {Theoret. Comput. Sci.},
  volume  = {66},
  year    = {1989},
  pages   = {137--155}
}

@article{erickson1999,
  author  = {Erickson, Jeff},
  title   = {Lower Bounds for Linear Satisfiability Problems},
  journal = {Chicago J. Theoret. Comput. Sci.},
  volume  = {1999},
  number  = {8},
  year    = {1999},
  url     = {http://cjtcs.cs.uchicago.edu/articles/1999/8/contents.html}
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-01087, "Sorting X+Y", clopen.solutions.