OP-00983 Open

Three-term progressions in F_3^n with common difference in {0,1}^n

Let $A \subset \mathbb{F}_3^n$ have density $\alpha$. By the density Hales–Jewett theorem, $A$ contains a three-term progression with nonzero common difference in $\{0, 1\}^n$ if $\alpha \to 0$ slowly enough as $n \to \infty$; Bhangale, Khot, Liu and Minzer showed that $\alpha \ge (\log\log\log n)^{-c}$ suffices, and Green does not rule out $\alpha = (1 - c)^n$ for some $c > 0$. For sets invariant under permutations of the coordinates the counting question below has a positive answer (Hązła). Both questions may be asked with $3$ replaced by any prime.

Problem. Under what conditions on $\alpha$ is $A$ forced to contain $x, x + d, x + 2d$ with $d \in \{0, 1\}^n \setminus \{0\}$? For fixed $\alpha$, must there be $\gg_\alpha 6^n$ such triples?

Source: B. Green, 100 open problems (version of January 2026), Problem 17; Green thanks V. Lev for reminding him of the first question.

Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.

Classification

Primary: CO — Combinatorics
Keywords: arithmetic progressions, density Hales–Jewett theorem, finite field model, restricted differences
Literature checked: Oct. 26, 2026 by clemens-admin

References

@article{bhangale2024effective,
  author = {Bhangale, Amey and Khot, Subhash and Minzer, Dor},
  title = {Effective bounds for restricted 3-arithmetic progressions in $\mathbb{F}_p^n$},
  journal = {Discrete Analysis},
  pages = {Paper No. 16},
  year = {2024},
  url = {https://discreteanalysisjournal.com/article/125858},
  eprint = {2308.06600},
  archivePrefix = {arXiv}
}

@misc{bhangale2024csps,
  author = {Bhangale, Amey and Khot, Subhash and Liu, Yang P. and Minzer, Dor},
  title = {On approximability of satisfiable $k$-{CSP}s: {VI}},
  year = {2024},
  eprint = {2411.15133},
  archivePrefix = {arXiv}
}

@article{hazla2020,
  author = {H{\k{a}}z{\l}a, Jan},
  title = {On arithmetic progressions in symmetric sets in finite field model},
  journal = {Electronic Journal of Combinatorics},
  volume = {27},
  number = {3},
  pages = {Paper No. P3.61},
  year = {2020},
  doi = {10.37236/9242}
}

@misc{conlon2026restricted,
  author = {Conlon, David and Fox, Jacob and Pham, Huy Tuan},
  title = {A note on arithmetic progressions with restricted differences},
  year = {2026},
  eprint = {2605.13628},
  archivePrefix = {arXiv}
}

@techreport{bhangale2026counting,
  author = {Bhangale, Amey and Khot, Subhash and Liu, Yang P. and Minzer, Dor},
  title = {A counting lemma for somewhat restricted 3-{AP}s},
  institution = {Electronic Colloquium on Computational Complexity},
  number = {TR26-149},
  year = {2026}
}

@misc{green100open,
  author = {Green, Ben},
  title = {100 open problems},
  howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
  note = {Problem 17; version of January 2026, most recent update December 2025},
  year = {2026}
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00983, "Three-term progressions in F_3^n with common difference in {0,1}^n", clopen.solutions.