Erdős Problem #272 — Families with arithmetic progression intersections
For an integer , write . An arithmetic progression in means a set of the form
where are integers, , , and every term belongs to ; in particular, a singleton is an arithmetic progression. Let be the largest integer for which there is a family of distinct subsets such that
The question is to determine . Distinctness is required by the family formulation of the problem; without it, repeating one admissible set would make the maximum unbounded. Erdős Problems #272 Szabó, Intersection properties of subsets of integers
Background
This problem belongs to extremal set theory, but unlike classical intersection questions that constrain only the size of pairwise intersections, it imposes structure on the intersection itself: it must be an arithmetic progression. Graham, Simonovits and Sós studied the related version in which empty intersections are allowed. They determined its exact maximum, . Requiring intersections to be non-empty changes the extremal behavior and leads to the present problem. Erdős Problems #272 Szabó, Intersection properties of subsets of integers Graham, Simonovits and Sós (1980)
A natural construction takes all arithmetic progressions containing one fixed integer, while another takes all subsets of size at most three containing a fixed integer. The latter construction already gives sets, and Szabó’s later improvement shows that this simple common-point construction is not always extremal. Thus the problem is not merely to count progressions through a point; it also asks how non-progression sets can be incorporated while preserving the required pairwise intersections. Erdős Problems #272 Szabó, Intersection properties of subsets of integers
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
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.