A problem on sumset sizes of sets of lattice points

Technical Summary: A Problem on Sumset Sizes of Sets of Lattice Points

Problem Statement
The central problem addressed in this work concerns the "range of sumset sizes" for finite subsets within additive abelian semigroups. Specifically, for a semigroup $X$ and positive integers $h$ and $k$, the paper investigates the set of possible cardinalities of $h$-fold sumsets ($hA$) and restricted $h$-fold sumsets ($\widehat{hA}$) where $A$ is a subset of $X$ with cardinality $k$.

The author defines two primary sets of interest:

1. $R_X(h, k) = \{ |hA| : A \subseteq X, |A| = k \}$
2. $\widehat{R}_X(h, k) = \{ |\widehat{hA}| : A \subseteq X, |A| = k \}$

The paper focuses on comparing these ranges when $X$ is the additive group of integers ($\mathbb{Z}$) versus when $X$ is the group of $n$-dimensional lattice points ($\mathbb{Z}^n$). Since $\mathbb{Z}$ is isomorphic to a subgroup of $\mathbb{Z}^n$, it is trivially true that $R_{\mathbb{Z}}(h, k) \subseteq R_{\mathbb{Z}^n}(h, k)$. The core question is whether the reverse inclusion holds, thereby establishing equality between the ranges of sumset sizes for integers and for $n$-dimensional lattice points.

Furthermore, the paper poses a computational efficiency problem. It asks whether the set of sumset sizes can be computed more efficiently using lattice points than integers. This is framed as a geometric question: does the freedom of working in $n$ dimensions allow for the determination of these ranges by examining sets with significantly smaller diameters (specifically, sets contained in $[0, N_n]^n$) compared to the one-dimensional case (sets contained in $[0, N]$)?

Methodology
The primary methodology employed is the construction of a specific linear mapping to establish an isomorphism between subsets of lattice points and subsets of integers that preserves sumset cardinalities.

1. Linear Mapping Construction: The author defines a linear function $\phi_g: \mathbb{R}^n \to \mathbb{R}$ given by:
   $$\phi_g(x_1, \dots, x_n) = \sum_{i=1}^n x_i g^{i-1}$$
   where $g$ is a positive integer chosen such that $g > h\ell$, and $\ell$ is a bound on the coordinates of the lattice points in the set $A$.

2. Uniqueness of Representation: By selecting $g > h\ell$, the function $\phi_g$ becomes injective (one-to-one) on the lattice point cube $[0, h\ell]^n \cap \mathbb{Z}^n$. This relies on the uniqueness of the $g$-adic representation of integers.

3. Preservation of Sumset Structure: Because $\phi_g$ is linear and injective on the relevant domain, it satisfies the following identities for any set $A$ within the domain:

   • $\phi_g(hA) = h\phi_g(A)$
   • $\phi_g(\widehat{hA}) = \widehat{h\phi_g(A)}$
     These identities ensure that the cardinality of the sumset is preserved: $|hA| = |h\phi_g(A)|$.

Key Results
The paper establishes the following main theorem:

Theorem 1: For all positive integers $h$ and $k$,
$$R_{\mathbb{Z}}(h, k) = R_{\mathbb{Z}^n}(h, k)$$
and
$$\widehat{R}_{\mathbb{Z}}(h, k) = \widehat{R}_{\mathbb{Z}^n}(h, k)$$

Proof Outline:

• Inclusion $R_{\mathbb{Z}} \subseteq R_{\mathbb{Z}^n}$: This is immediate because $\mathbb{Z}$ embeds into $\mathbb{Z}^n$.
• Inclusion $R_{\mathbb{Z}^n} \subseteq R_{\mathbb{Z}}$: Let $t \in R_{\mathbb{Z}^n}(h, k)$. There exists a set $A \subset \mathbb{Z}^n$ with $|A|=k$ and $|hA|=t$. By translation invariance, $A$ can be assumed to have non-negative coordinates, contained in $[0, \ell]^n$. Choosing $g > h\ell$, the map $\phi_g$ transforms $A$ into a set of integers $\phi_g(A) \subset \mathbb{N}_0$ with $|\phi_g(A)| = k$. Due to the linearity and injectivity of $\phi_g$, $|h\phi_g(A)| = |hA| = t$. Thus, $t \in R_{\mathbb{Z}}(h, k)$.
• The same logic applies to restricted sumsets using the second identity, proving $\widehat{R}_{\mathbb{Z}^n}(h, k) = \widehat{R}_{\mathbb{Z}}(h, k)$.

The function $\phi_g$ is identified as a classical example of a Freiman isomorphism.

Open Problems and Geometric Questions
While the paper proves that the sets of possible sumset sizes are identical, it does not claim that the computational effort to find them is identical. The paper highlights the following open problems (referencing Nathanson [4] and Gowers [1]):

1. Problem 1 & 2 (Bounding the Search Space): Determine the smallest integers $N(h, k)$ and $\widehat{N}(h, k)$ such that the ranges $R_{\mathbb{Z}}(h, k)$ and $\widehat{R}_{\mathbb{Z}}(h, k)$ can be fully computed by considering only subsets of the interval $[0, N]$ (or $[0, \widehat{N}]$).
2. Problem 3 (Dimensional Efficiency): Define $N_n(h, k)$ as the smallest integer such that $R_{\mathbb{Z}}(h, k)$ can be computed using subsets of the $n$-dimensional cube $[0, N_n]^n$. The paper poses the inequality:
   $$N_n(h, k) \leq N(h, k)^{1/n}$$
   The paper asks whether this inequality holds, which would imply that working in $n$ dimensions allows for the computation of sumset sizes using sets with a significantly smaller diameter (and thus fewer candidate sets) than in the one-dimensional case.

Significance and Claims
The paper claims to resolve the structural question of whether the "range of sumset sizes" differs between integers and lattice points. The result confirms that the range is invariant under the dimension of the lattice; the set of possible sumset sizes for $k$ elements is exactly the same whether the elements are chosen from $\mathbb{Z}$ or $\mathbb{Z}^n$.

The significance of this result lies in the reduction of the problem: one can theoretically compute the range of sumset sizes for integers by constructing sets of lattice points. However, the paper explicitly frames the remaining challenge as a geometric optimization problem. It does not claim that lattice points provide a faster algorithm for computing these ranges, but rather poses the question of whether the geometric freedom of higher dimensions allows for a reduction in the "diameter" of the sets required to exhaustively determine the range. The paper concludes by leaving the estimation of these bounds and the verification of the dimensional inequality as open problems.