← All problems

Erdős Problem #160 — Minimum colors for four-term progressions

37 years old · traced to

For a positive integer NN, write [N]={1,…,N}[N]=\{1,\ldots,N\}. A four-term arithmetic progression in [N][N] means a sequence a,a+d,a+2d,a+3da,a+d,a+2d,a+3d with integers a≥1a\ge 1, d≥1d\ge 1, and a+3d≤Na+3d\le N. For a coloring c:[N]→{1,…,k}c:[N]\to\{1,\ldots,k\}, require that each such progression use at least three distinct colors. The parameter in question is

h(N)=min⁡{k≥1:there is a coloring c:[N]→{1,…,k} such that ∣{c(a+id):0≤i≤3}∣≥3 for all a,d with a≥1, d≥1, a+3d≤N}.h(N)=\min\left\{k\ge 1: \text{there is a coloring }c:[N]\to\{1,\ldots,k\}\text{ such that }\left|\{c(a+id):0\le i\le 3\}\right|\ge 3\text{ for all }a,d\text{ with }a\ge1,\ d\ge1,\ a+3d\le N\right\}.

If N<4N<4, there are no such progressions and h(N)=1h(N)=1. The question is to estimate h(N)h(N) as NN grows. Bloom, Erdős Problem #160

Background

Erdős’s 1989 account describes an investigation with Freud of a closely related partition problem: find the largest number of parts for which every partition of [N][N] has two parts whose union contains a four-term arithmetic progression. For N≥4N\ge4, with partitions into nonempty parts, this threshold is one less than the present h(N)h(N). Indeed, for a partition into at least two color classes, having no progression in the union of any two classes is equivalent to every progression using at least three colors. The two formulations thus express the same obstruction from opposite sides of the threshold. Erdős (1989), Some Problems and Results on Combinatorial Number Theory Bloom, Erdős Problem #160

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.