A chain-deficit theorem and exact multidimensional constructions for restricted sums

Definitions and mathematical statement

Let $A\subset\mathbb Z$ have cardinality $n\geq1$, and let $\Gamma\subseteq A\times A$ be an arbitrary set of ordered pairs. Its restricted sum and difference sets are \[ S_\Gamma=\{a+b:(a,b)\in\Gamma\},\qquad D_\Gamma=\{a-b:(a,b)\in\Gamma\}. \] Pairs with equal coordinates are allowed, and $\Gamma$ need not be invariant under exchanging its coordinates. Cardinalities count distinct integers, rather than the number of representations or selected pairs.

For each feasible pair of integers $n,m\geq1$, define \[ F(n,m)=\max\{|D_\Gamma|: A\subset\mathbb Z, |A|=n, \Gamma\subseteq A\times A, |S_\Gamma|=m\}. \] Determine sharp upper bounds for $F(n,m)$ and describe the integer sets and pair selections attaining, or asymptotically approaching, them. In particular, identify the structure of $A$ when the number of distinct differences is maximal for a prescribed small number of sums. The trivial estimates $|D_\Gamma|\leq n(n-1)+1$ and $|D_\Gamma|\leq mn$ only use the number of pairs and the fact that each fixed sum pairs a chosen element with at most one partner. The question seeks the stronger restrictions coming from simultaneously realizing these pairs within one integer set. The source's illustrative geometric examples are motivation; they are not imposed as hypotheses or asserted here as exact formulas with unspecified constants.

Short English statement

For a prescribed number of sums on selected pairs of an integer set, maximize the number of differences and describe extremal configurations.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20001135 (AIM-COMBINATORICS-0260), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 American Institute of Mathematics, Recent trends in additive combinatorics, item 4.4. Original workshop question underlying AIM-COMBINATORICS-0260. https://aimath.org/WWN/additivecomb/additivecomb.pdf.