← All problems

Erdős Problem #1185 — Dense progressions with differences from a prescribed difference set

46 years old · traced to

For an integer N≥1N\geq 1, let [N]={1,…,N}[N]=\{1,\ldots,N\}, and for B⊆[N]B\subseteq[N] let B−B={b−b′:b,b′∈B}B-B=\{b-b':b,b'\in B\}. Is the following assertion true: for every real δ>0\delta>0 and every integer k≥3k\geq3, there exist a positive integer m=m(δ,k)m=m(\delta,k) and an integer N0N_0 such that, for every N≥N0N\geq N_0 and all A,B⊆[N]A,B\subseteq[N] with ∣A∣≥δN|A|\geq\delta N and ∣B∣≥m|B|\geq m, there are an integer xx and a positive integer d∈B−Bd\in B-B such that

x+jd∈A(0≤j<k)?x+jd\in A\qquad(0\leq j<k)?

The positivity of dd makes the progression nonconstant; since B−BB-B is symmetric, it does not change the question. Erdős Problems #1185 Erdős (1980)

Background

Erdős attributed the problem to himself and Ralph Mauldin, saying it arose from a question in measure theory. His 1980 formulation asks whether every sufficiently dense finite set contains a three-term progression whose difference is the difference of two elements of an auxiliary set of fixed size; he suggests the analogous question for longer progressions. Thus the prescribed differences are constrained by the additive structure of BB, rather than chosen freely. Erdős (1980)

References

P. Erdős, A survey of problems in combinatorial number theory, Annals of Discrete Mathematics 6 (1980), 89–115.

Source: P. Erdős, A survey of problems in combinatorial number theory, Annals of Discrete Mathematics 6 (1980), 89–115.

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.