On the structures of subset sums in higher dimension

2024/05/03 by Hegyvári, Norbert, Pálfy, Máté, Yue, Erfei
#11B75 #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2405.02269

Abstract

A given subset A of natural numbers is said to be complete if every element of \N is the sum of distinct terms taken from A. This topic is strongly connected to the knapsack problem which is known to be NP complete. The main goal of the paper is to study the structure of subset sums in a higher dimension. We show 'dense' sets and generalized arithmetic progrssions in subset sums of certain sets.

Related

• On the distribution of subset sums of certain sets in ℤ²_p
• Subset sums, completeness and colorings
• Strongly complete sets and a conjecture of Erdős
• New examples of complete sets, with connections to a Diophantine theorem of Furstenberg
• A novel and efficient algorithm to solve subset sum problem