Compression and complexity for sumset sizes in additive number theory

2025/05/27 by Melvyn B. Nathanson, Nathanson, Melvyn B. · 2 citations
Computer Science · Mathematics · #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Analytic Number Theory Research

paper · pdf · doi:10.1016/j.jnt.2025.09.025

Abstract

The study of sums of finite sets of integers has mostly concentrated on sets with small sumsets (Freiman's theorem and related work) and on sets with large sumsets (Sidon sets and B_h-sets). This paper considers the sets \mathcal R_{\mathbf Z}(h,k) and \mathcal R_\mathbf Zⁿ(h,k) of all sizes of h-fold sums of sets of k integers or of k lattice points, and the geometric and computational complexity of the sets \mathcal R_{\mathbf Z}(h,k) and \mathcal R_\mathbf Zⁿ(h,k). For sumsets hA with large diameter, there is a compression algorithm to construct sets A' with |hA'| = |hA| and small diameter.

Citations

• INTERSECTIONS OF SUMSETS IN ADDITIVE NUMBER THEORY

Cited by

• INTERSECTIONS OF SUMSETS IN ADDITIVE NUMBER THEORY
• Possible Sizes of Sumsets
• Diversity, equity, and inclusion for problems in additive number theory

Related

• Explicit sumset sizes in additive number theory
• A problem on sumset sizes of sets of lattice points
• Improved stability for the size and structure of sumsets
• Triangular and tetrahedral number differences of sumset sizes in additive number theory
• On the Sumset of Sets of Size k