Small sets with a k-term progression of every difference up to N
Let $F_k(N)$ be the size of the smallest set of positive integers containing, for each $d = 1, \dots, N$, a $k$-term arithmetic progression with common difference $d$. It is conjectured that $F_k(N) \gg_k N^{1 - c_k}$ with $c_k \to 0$ as $k \to \infty$. Green and Ruzsa showed that this is equivalent to the arithmetic Kakeya conjecture of Katz and Tao, which would give the Minkowski-dimension form of the Kakeya conjecture in every dimension.
Problem. Determine $F_k(N)$.
Source: I. Z. Ruzsa, Sumsets, European Congress of Mathematics (Stockholm 2004), Conjecture 4.2; equivalent, by Green and Ruzsa (2019), to the arithmetic Kakeya conjecture of N. Katz and T. Tao. Listed as Problem 37 in B. Green, 100 open problems (version of January 2026).
Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.
Classification
- Primary
- CO — Combinatorics
- Secondary
- CA, NT
- Keywords
- arithmetic Kakeya conjecture, arithmetic progressions, Kakeya problem
- Literature checked
- Oct. 26, 2026 by clemens-admin
References
@incollection{ruzsa2005sumsets,
author = {Ruzsa, Imre Z.},
title = {Sumsets},
booktitle = {European Congress of Mathematics (Stockholm, 2004)},
pages = {381--390},
publisher = {European Mathematical Society},
year = {2005},
doi = {10.4171/009-1/24},
note = {Conjecture 4.2}
}
@article{katz2002tao,
author = {Katz, Nets Hawk and Tao, Terence},
title = {New bounds for {K}akeya problems},
journal = {Journal d'Analyse Math{\'e}matique},
volume = {87},
pages = {231--263},
year = {2002},
doi = {10.1007/BF02868476}
}
@article{green2019ruzsa,
author = {Green, Ben and Ruzsa, Imre Z.},
title = {On the arithmetic {K}akeya conjecture of {K}atz and {T}ao},
journal = {Periodica Mathematica Hungarica},
volume = {78},
number = {2},
pages = {135--151},
year = {2019},
doi = {10.1007/s10998-018-0270-z},
eprint = {1712.02108},
archivePrefix = {arXiv}
}
@misc{green100open,
author = {Green, Ben},
title = {100 open problems},
howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
note = {Problem 37; 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-00986, "Small sets with a k-term progression of every difference up to N", clopen.solutions.