Sidon sets meeting every infinite progression

DefinitionErdős Problem 198#✓fully proved

The proposition that the complement of every Sidon set \(A \subseteq \mathbb{N}\) contains an infinite arithmetic progression: for every Sidon set \(A \subseteq \mathbb{N}\) there are natural numbers \(a\) and \(d \ge 1\) such that \(a + kd \notin A\) for every natural number \(k\).

def sidonComplementContainsProgression : Prop :=
  ∀ A : Set ℕ, A.IsSidon → ∃ a d : ℕ, 0 < d ∧ ∀ k : ℕ, a + k * d ∉ A

Uses 1 · Used by 1

Statement usesSidon set

Used byErdős Problem 198 is false

TheoremErdős Problem 198 is false#●ready to prove

It is not the case that the complement of every Sidon set \(A \subseteq \mathbb{N}\) contains an infinite arithmetic progression: there is a Sidon set \(A \subseteq \mathbb{N}\) such that for all natural numbers \(a\) and \(d \ge 1\) some term \(a + kd\), \(k \in \mathbb{N}\), lies in \(A\). Here \(A\) is Sidon when \(w + x = y + z\) with \(w, x, y, z \in A\) forces \(\{w, x\} = \{y, z\}\).

To construct such a set, enumerate the infinite progressions \(P_1, P_2, \ldots\) and pick \(a_n \in P_n\) with \(a_n > 2 a_{n-1}\); the resulting lacunary set is Sidon and meets every infinite progression. erdosproblems.com/198 records this construction (implicit in Baumgartner's paper) and the explicit example \(\{(n + 1)! + n : n \ge 0\}\).

public theorem_wanted sidonComplementContainsProgression_refuted :
    ¬ sidonComplementContainsProgression

Sources

• T. F. Bloom, Erdős Problems, Problem #198, https://www.erdosproblems.com/198 (status DISPROVED (LEAN)); resolution: J. E. Baumgartner, Partitioning vector spaces, J. Combin. Theory Ser. A 18 (1975), 231-233; construction recorded on erdosproblems.com/198, erdosproblems.com/198: answered no; a lacunary set with one element in each infinite progression (implicit in [Ba75]), or explicitly A = {(n + 1)! + n : n ≥ 0}, https://www.erdosproblems.com/198.

Uses 1

Statement usesErdős Problem 198

1 fully proved1 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.