Erdős Problem 198

Reference: erdosproblems.com/198

theorem baumgartner_strong (V : Type u_1) [AddCommGroup V] [Module ℚ V] (k : ℕ) : ∃ (X : Set V), (∀ (Y : Set V), Y.IsAPOfLength ⊤ → (X ∩ Y).Nonempty) ∧ ∀ (Y : Set V), Y.IsAPOfLength ↑k → (X ∩ Y).ncard ≤ 2

Let $V$ be a vector space over the rationals and let $k$ be a fixed positive integer. Then there is a set $X_k ⊆ Y$ such that $X_k$ meets every infinite arithmetic progression in $V$ but $X_k$ intersects every $k$-element arithmetic progression in at most two points.

At the end of:

• Baumgartner, James E., Partitioning vector spaces. J. Combinatorial Theory Ser. A (1975), 231-233. the author claims that by "slightly modifying the method of [his proof]", one can prove this.

theorem baumgartner_headline (V : Type u_1) [AddCommGroup V] [Module ℚ V] : ∃ (X : Set V), (∀ (Y : Set V), Y.IsAPOfLength ⊤ → (X ∩ Y).Nonempty) ∧ ∀ (Y : Set V), Y.IsAPOfLength 3 → (X ∩ Y).ncard ≤ 2

The statement for which Baumgartner actually writes a proof.

theorem erdos_198 : (∀ (A : ℕ →o ℕ), IsSidon A → ∃ (Y : Set ℕ), Y.IsAPOfLength ⊤ ∧ Y ⊆ (Set.range ⇑A)ᶜ) ↔ False

If $A ⊆ ℕ$ is a Sidon set then must the complement of $A$ contain an infinite arithmetic progression?

Answer "yes" according to remark on page 23 of:

• Erdös and Graham, "Old and new problems and results in combinatorial number theory", 1980.

"Baumgartner also proved the conjecture of Erdös that if $A$ is a sequence of positive integers with all sums $a + a'$ distinct for $a, a' ∈ A$ then the complement of $A$ contains an infinite A.P."

But this seems to be a misprint, since the opposite is true: There is a sequence of positive integers with all $a + a'$ distinct for $a, a' ∈ A$ such that the complement of $A$ contains no infinite A.P., i.e. there is a Sidon set $A$ which intersects all arithmetic progressions.

So the answer should be "no".

This can be seen, as pointed out by Thomas Bloom erdosproblems.com/198, by an elementary argument.

theorem erdos_198.variant_concrete : ∃ (A : ℕ →o ℕ), (∀ (n : ℕ), A n = n.factorial + n) ∧ IsSidon A ∧ ∀ (Y : Set ℕ), Y.IsAPOfLength ⊤ → (Set.range ⇑A ∩ Y).Nonempty

In fact one such sequence is $n! + n$. This was found by AlphaProof. It also found $(n + 1)! + n$.