An approach to the moments subset sum problem through systems of diagonal equations over finite fields

Abstract

Let Fq be the finite field of q elements, for a given subset D ⊂ Fq, m ∈ N, an integer k ≤ |D| and b ∈ F m q we are interested in determining the existence of a subset S ⊂ D of cardinality k such that P a∈S a i = bi for i = 1, . . . , m. This problem is known as the moment subset sum problem and it is NP-complete for a general D. We make a novel approach of this problem trough algebraic geometry tools analyzing the underlying variety and employing combinatorial techniques to estimate the number of Fq-rational points on certain varieties. We managed to give estimates on the number of Fq-rational points on certain diagonal equations and use this results to give estimations and existence results for the subset sum problem.