The largest number of affine copies of {0, 1, 3} in a set of n integers
An affine copy of $\{0, 1, 3\}$ is a set $\{x, x + d, x + 3d\}$ with $d \ne 0$. Green expects the answer below to be $(\frac13 + o(1))n^2$, the value for an interval, but this is not known.
Problem. If $A$ is a set of $n$ integers, what is the largest number of affine copies of $\{0, 1, 3\}$ that $A$ can contain?
Source: Raised by Ganguly, as Green heard from R. Pemantle; see J. Aaronson, Maximising the number of solutions to a linear equation in a set of integers (2019). Listed as Problem 24 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
- NT
- Keywords
- affine copies, extremal combinatorics, linear equations in sets
References
@article{aaronson2019maximising,
author = {Aaronson, James},
title = {Maximising the number of solutions to a linear equation in a set of integers},
journal = {Bulletin of the London Mathematical Society},
volume = {51},
number = {4},
pages = {577--594},
year = {2019},
doi = {10.1112/blms.12253}
}
@article{abrego2016similar,
author = {{\'A}brego, Bernardo M. and Fern{\'a}ndez-Merchant, Silvia and Katz, Daniel J. and Kolesnikov, Levon},
title = {On the number of similar instances of a pattern in a finite set},
journal = {Electronic Journal of Combinatorics},
volume = {23},
number = {4},
pages = {Paper 4.39},
year = {2016},
doi = {10.37236/4972}
}
@misc{korsky2026affine,
author = {Korsky, Samuel},
title = {Affine copies of three-point patterns in sets of integers},
year = {2026},
eprint = {2609.02308},
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 24; version of January 2026, most recent update December 2025},
year = {2026}
}
Resolution claims
Let $P=\{0,a,b\}$, where $0<a<b$ and $\gcd(a,b)=1$. For a finite set $A\subset\mathbb Z$, let $M_P^+(A)$ count the copies $x,x+ad,x+bd\in A$ with $d>0$, and let $M_P(A)$ count the copies with any $d\ne0$. We prove that every such three-point pattern other than the arithmetic progression $\{0,1,2\}$ satisfies \[ M_P^+(A)\le \frac{99}{400}|A|^2+O(|A|), \qquad M_P(A)\le \frac{13}{28}|A|^2+O_P(|A|). \] For the particular pattern $P=\{0,1,3\}$ -- the subject of …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-29 | Open → Partially resolved | The registry's curators | Affine Copies of Three-Point Patterns in Sets of Integers v1 recorded from arXiv:2609.02308v1. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01033, "The largest number of affine copies of {0, 1, 3} in a set of n integers", clopen.solutions.