← All problems

Simonovits–Sós conjecture for 3-AP-intersecting families

For every n∈Nn\in\mathbb{N}, if F⊆2[n]\mathcal{F}\subseteq 2^{[n]} satisfies that for all F1,F2∈FF_1,F_2\in\mathcal{F}, the intersection F1∩F2F_1\cap F_2 contains a nonconstant three-term arithmetic progression, i.e. there exist integers a∈Za\in\mathbb{Z} and d∈Nd\in\mathbb{N} such that {a,a+d,a+2d}⊆F1∩F2\{a,a+d,a+2d\}\subseteq F_1\cap F_2, then ∣F∣≤2n−3|\mathcal{F}|\le 2^{n-3}.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

A new preprint sharply improves the known upper bound, but the conjectured exact answer remains unproved.

The Simonovits–Sós conjecture predicts that a family of subsets whose every pair shares a non-trivial three-term arithmetic progression has size at most 2n−32^{n-3}. Simonovits and Sós communicated the conjecture; the analogous graph problem was later solved, but this 33-AP version remains open.

Known results

  • The conjectured bound 2n−32^{n-3} is attained by all subsets containing a fixed three-term arithmetic progression.
  • Ellis, Filmus, and Friedgut proved the analogous triangle-intersecting graph conjecture; their methods do not directly settle the 33-AP problem.
  • In 2010, the set-system version was described as widely open.

September–October 2026 progress

On September 16, 2026, Kupavskii, Noskov, Sokolov, and Terekhov proved the first non-trivial bound: ∣F∣≤(1/2−c)2n|\mathcal F|\le (1/2-c)2^n for an absolute constant c>0c>0. A later reported result reaches the correct exponential scale for every k≥3k\ge 3, but does not determine the exact k=3k=3 value. These are preprint results and remain unrefereed.

Current status (as of October 2026): The conjectured exact bound 2n−32^{n-3} remains open; substantial unrefereed progress gives exponential-scale upper bounds but does not settle the 33-AP case.

Sources

Solutions 0

No solutions have been posted yet.