Long Arithmetic Progressions in Sparse Subset Sums: A Computational Perspective

Existence of long arithmetic progressions in sumsets and subset sums is an important topic in additive combinatorics, and has applications in the design of algorithms for classic combinatorial optimization problems, including Subset Sum and Knapsack. Motivated by these applications, Chen, Mao and Zhang [STOC, 2025] studied arithmetic progressions from a computational perspective: instead of merely knowing the existence of arithmetic progressions, they aim to construct it explicitly and find out how its terms can be represented using integers from the corresponding set. They show that both can be done in near-linear time for long arithmetic progressions in \(kA\), the \(k\)-fold sum of an integer set \(A\), and \(\mathcal{S}(A)\), the set of all subset sums of \(A\), where \(A\) is a set of nonnegative integers and \(|A|\) is relatively large comparing to \(\max(A)\) (the largest element in \(A\)). They left as an open problem whether the same thing can be achieved for long arithmetic progressions in the sumset of different sets, i.e., \(A_1 + A_2 + \cdots + A_k\).