Additive bases

Sets whose h-fold sums cover the integers or a group: asymptotic, exact and restricted bases, Schnirelmann density, Rohrbach's theorem, representation counts and convolutions, sums of cubes covering vector spaces, knight-move bases of the plane, and sumsets of infinite sets of positive or zero density.

• Additive complements
• Additive representation functions
• Asymptotic additive bases
• Bounded-gap sumsets avoiding lacunary sequences
• Erdős sumset conjecture
• Knight and king distances on the integer lattice
• Restricted additive bases
• Schnirelmann density
• Shifted sumsets in sets of positive density
• Splitting sets with dense sumsets
• Sums of cubes in ternary vector spaces
• Sumsets of sets of density zero

TheoremRohrbach's symmetric basis theorem#✓fully proved

Let \(A\) be a finite set of natural numbers and \(a\) a natural number with \(\{a - x : x \in A\} = A\), where \(a - x\) denotes truncated subtraction (\(a - x = 0\) when \(x > a\)). If every natural number \(m \le a\) is a sum \(x + y\) of two elements \(x, y \in A\), then every natural number \(m \le 2a\) is such a sum.

The symmetry condition forces every element of \(A\) to be at most \(a\), so it says exactly that \(A\) is invariant under \(x \mapsto a - x\).

This is Rohrbach's theorem on symmetric restricted additive bases.

theorem exists_add_eq_of_image_sub_eq_self (A : Finset ℕ) (a : ℕ)
    (hsymm : A.image (fun x => a - x) = A)
    (hadmissible : ∀ m : ℕ, m ≤ a → ∃ x ∈ A, ∃ y ∈ A, x + y = m) :
    ∀ m : ℕ, m ≤ 2 * a → ∃ x ∈ A, ∃ y ∈ A, x + y = m

Sources

• Jukka Kohonen, "A Meet-in-the-Middle Algorithm for Finding Extremal Restricted Additive 2-Bases", Journal of Integer Sequences 17 (2014), Article 14.6.8, theorem theorem:symmrest, lines 274–288, with notation and basis definitions at lines 226–248, https://cs.uwaterloo.ca/journals/JIS/VOL17/Kohonen2/kohonen5.tex.

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.