Erdős Problem #198

Erdős Problem #198

1. FORMAL RESTATEMENT

If $A\subset\mathbb N$ is Sidon, must its complement contain an infinite arithmetic progression? We use the strong Sidon convention: $a+b=c+d$, with all entries in $A$ and repetitions allowed, implies equality of the two unordered pairs.

2. LITERATURE AND CONSTRUCTION

The negative answer is attributed to Baumgartner. The current problem page credits AlphaProof with the explicit factorial example used here. We verify that construction, with no novelty claim: \[ a_n=(n+1)!+n\quad(n\ge0),\qquad A=\{a_n:n\ge0\}. \]

3. A SEPARATION LEMMA

For $n\ge0$, \[ a_{n+1}-2a_n=n(n+1)!+1-n>0. \] The inequality holds at $n=0$ directly; at $n\ge1$, $(n+1)!\ge2$ makes it immediate. Thus $a_{n+1}>2a_n$ and all entries are positive.

Any positive sequence with this property is Sidon. To prove it, suppose $a_i+a_j=a_r+a_s$. If the largest occurring index appears on both sides, cancel it and use strict increase. Otherwise let the largest index be $t$, occurring on just one side. Its side is at least $a_t$, whereas the other side is at most $2a_{t-1}<a_t$, a contradiction. This includes the case where the largest summand is repeated.

4. MEETING EVERY PROGRESSION

Fix integers $b\ge1,d\ge1$. For every sufficiently large index $n\equiv b\pmod d$, we have $d\mid(n+1)!$ and hence \[ a_n\equiv b\pmod d. \] Also $a_n\ge b$, so $a_n\in\{b+jd:j\ge0\}$. There are infinitely many such indices. Thus $A$ meets every infinite positive-integer arithmetic progression infinitely often, and no such progression lies in its complement.

An abstract version further explains why sparsity is no obstacle: enumerate all infinite progressions $P_1,P_2,\ldots$ and choose $b_j\in P_j$ with $b_j>2b_{j-1}$. The same separation lemma gives a Sidon transversal. Larger prescribed finite lower thresholds may be imposed at every step as well.

5. FINAL AND VERIFICATION

SOLVED: negative answer, by a fully verified known construction. Both the repeated-summand Sidon convention and the one-sided progression condition are addressed explicitly. There is no remaining gap or external theorem beyond elementary factorial divisibility.

6. SOURCES

https://www.erdosproblems.com/198, including its attribution of the factorial construction to AlphaProof and its discussion of J. E. Baumgartner, Partitioning vector spaces, J. Combinatorial Theory Ser. A 18 $1975$, 231--233. The proof here is independent of the unavailable full text of that paper.

COMPLETION ESTIMATE

COMPLETION: 100%