← All problems

Erdős Problem #201 — Progression-free subsets of arbitrary integer sets

57 years old · traced to

For integers k≥3k\ge 3 and N≥1N\ge 1, call a subset progression-free if it contains no kk distinct integers of the form a,a+d,…,a+(k−1)da,a+d,\ldots,a+(k-1)d, where a∈Za\in\mathbb Z and d∈Z∖{0}d\in\mathbb Z\setminus\{0\}. For each finite X⊆ZX\subseteq\mathbb Z, let Ak(X)A_k(X) be the largest cardinality of a progression-free subset of XX. Define

Gk(N)=min⁡X⊆Z∣X∣=NAk(X),Rk(N)=Ak({1,2,…,N}).G_k(N)=\min_{\substack{X\subseteq\mathbb Z\\|X|=N}} A_k(X), \qquad R_k(N)=A_k(\{1,2,\ldots,N\}).

Thus Gk(N)G_k(N) is the largest size guaranteed to be available in every NN-element set of integers. The questions are to determine Gk(N),G_k(N), understand its relation to Rk(N),R_k(N), and, for k=3k=3, decide whether

lim⁡N→∞R3(N)G3(N)=1.\lim_{N\to\infty}\frac{R_3(N)}{G_3(N)}=1.

Erdős Problem #201

Background

The comparison asks whether the interval {1,…,N}\{1,\ldots,N\} is asymptotically as difficult as the worst-positioned NN-element set of integers for finding a large progression-free subset. The inequality Gk(N)≤Rk(N)G_k(N)\le R_k(N) follows because the interval is one of the sets over which the minimum defining Gk(N)G_k(N) is taken. The problem was first investigated by Riddell; Erdős and Graham later recorded the comparison and asked whether the ratio for three-term progressions tends to 11. Erdős Problem #201 Erdős and Graham (1979)

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.