Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Integer Linear Arithmetic

In the last three decades, the $k$-SUM hypothesis has emerged as a satisfying explanation of long-standing time barriers for a variety of algorithmic problems. Yet to this day, the literature knows of only few proven consequences of a refutation of this hypothesis. Taking a descriptive complexity viewpoint, we ask: What is the largest logically defined class of problems \emph{captured} by the $k$-SUM problem? To this end, we introduce a class ${\mathsf{F}\mathsf{O}\mathsf{P}}_{\mathbb{Z}}$ of problems corresponding to deciding sentences in Presburger arithmetic/linear integer arithmetic over finite subsets of integers. We establish two large fragments for which the $k$-SUM problem is complete under fine-grained reductions: 1. The $k$-SUM problem is complete for deciding the sentences with $k$ existential quantifiers. 2. The $3$-SUM problem is complete for all $3$-quantifier sentences of ${\mathsf{F}\mathsf{O}\mathsf{P}}_{\mathbb{Z}}$ expressible using at most $3$ linear inequalities. Specifically, a faster-than-$n^{\lceil k\mathrm{/}2\rceil \pm o(1)}$ algorithm for $k$-SUM (or faster-than-$n^{2\pm o(1)}$ algorithm for $3$-SUM, respectively) directly translate to polynomial speedups of a general algorithm for \emph{all} sentences in the respective fragment. Observing a barrier for proving completeness of $3$-SUM for the entire class ${\mathsf{F}\mathsf{O}\mathsf{P}}_{\mathbb{Z}}$, we turn to the question which other – seemingly more general – problems are complete for ${\mathsf{F}\mathsf{O}\mathsf{P}}_{\mathbb{Z}}$. In this direction, we establish ${\mathsf{F}\mathsf{O}\mathsf{P}}_{\mathbb{Z}}$-completeness of the \emph{problem pair} of Pareto Sum Verification and Hausdorff Distance under $n$ Translations under the $L_{\mathrm{\infty }}$/$L_1$ norm in ${\mathbb{Z}}^d$. In particular, our results invite to investigate Pareto Sum Verification as a high-dimensional generalization of 3-SUM.