Bounded-gap sumsets avoiding lacunary sequences

DefinitionLacunary threshold for bounded-gap sumsets#✓fully proved

For natural numbers \(d_1\), \(d_2\) and \(k\), the threshold \(r_k(d_1, d_2)\) of Erdős Problem 1112 exists when there is a natural number \(r\) such that for every strictly increasing sequence \(b_0 < b_1 < \cdots\) of positive integers with \(b_{i+1} \ge r b_i\) for all \(i\), there is a sequence \(a_0, a_1, \dots\) of positive integers with \(a_i + d_1 \le a_{i+1} \le a_i + d_2\) for all \(i\) such that no \(b_i\) lies in the \(k\)-fold sumset of \(A = \{a_0, a_1, \dots\}\), the set of all sums of \(k\) elements of \(A\) with repetition allowed (for \(k = 0\) this set is \(\{0\}\)).

def HasLacunaryThreshold (d₁ d₂ k : ℕ) : Prop :=
  ∃ r : ℕ, ∀ b : ℕ → ℕ, 0 < b 0 → StrictMono b → (∀ i, r * b i ≤ b (i + 1)) →
    ∃ a : ℕ → ℕ, 0 < a 0 ∧ (∀ i, a i + d₁ ≤ a (i + 1) ∧ a (i + 1) ≤ a i + d₂) ∧
      Disjoint (k • Set.range a) (Set.range b)

Used by 1

Used byStatement of Erdős Problem 1112 for gaps in \((2, 3)\) and triple sums

DefinitionStatement of Erdős Problem 1112 for gaps in \((2, 3)\) and triple sums#✓fully proved

The threshold \(r_3(2, 3)\) exists: there is a natural number \(r\) such that for every strictly increasing sequence \(b_0 < b_1 < \cdots\) of positive integers with \(b_{i+1} \ge r b_i\) for all \(i\), there is a sequence \(a_0, a_1, \dots\) of positive integers with \(a_i + 2 \le a_{i+1} \le a_i + 3\) for all \(i\) such that no \(b_i\) is a sum \(x + y + z\) of three, not necessarily distinct, terms \(x, y, z\) of the sequence \(a\).

def lacunaryThresholdGapsTwoThreeThreeFold : Prop :=
  HasLacunaryThreshold 2 3 3

Uses 1 · Used by 1

Statement usesLacunary threshold for bounded-gap sumsets

Used byBollobás–Hegyvári–Jin theorem on Erdős Problem 1112

TheoremBollobás–Hegyvári–Jin theorem on Erdős Problem 1112#●ready to prove

There is no natural number \(r\) such that for every strictly increasing sequence \(b_0 < b_1 < \cdots\) of positive integers with \(b_{i+1} \ge r b_i\) for all \(i\), there is a sequence \(a_0, a_1, \dots\) of positive integers with \(a_i + 2 \le a_{i+1} \le a_i + 3\) for all \(i\) such that no \(b_i\) is a sum of three, not necessarily distinct, terms of the sequence \(a\). In other words, the threshold \(r_3(2, 3)\) of Erdős Problem 1112 (gaps between \(2\) and \(3\), triple sums) does not exist.

public theorem_wanted lacunaryThresholdGapsTwoThreeThreeFold_refuted :
    ¬ lacunaryThresholdGapsTwoThreeThreeFold

Sources

• T. F. Bloom, Erdős Problems, Problem #1112, https://www.erdosproblems.com/1112 (status OPEN (LEAN)); resolution: B. Bollobás, N. Hegyvári and G. Jin, On a problem of Erdős and Graham, Discrete Math. 175 (1997), 253-257, main result (Theorem 3 of the paper), as recorded on erdosproblems.com/1112: for any integers 1 ≤ r₁ < r₂ < ⋯ there is a B with b_{i+1} ≥ r_i b_i such that (A + A + A) ∩ B ≠ ∅ for every A with 2 ≤ a_{i+1} - a_i ≤ 3; erdosproblems.com/1112: 'It follows from the above results that r₂(2, 3) = 2 and that r₃(2, 3) does not exist', https://doi.org/10.1016/S0012-365X(96)00122-7.

Uses 1

Statement usesStatement of Erdős Problem 1112 for gaps in \((2, 3)\) and triple sums

2 fully proved1 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.