Erdős Problem #340 — Growth of the greedy Sidon sequence
Define a sequence recursively by and, for each , let be the least integer such that adjoining to the earlier terms preserves the Sidon property. Here a set of integers is Sidon if every equality with has the same unordered pair of summands on both sides; repeated summands are allowed. Set and . What is the asymptotic order of growth of this greedy sequence? In particular, is it true that for every there are constants and such that
Erdős Problems #340 O’Bryant (2004)
Background
This greedy Sidon sequence is also called the Mian–Chowla sequence; its first terms are . The greedy construction is a particular way to produce a Sidon set, rather than a general extremal construction: at each step it chooses the smallest admissible next integer. Erdős and Graham posed the question about its growth in their 1980 work on combinatorial number theory. Erdős Problems #340 O’Bryant (2004) Erdős and Graham (1980)
The Sidon condition is equivalently expressed by requiring distinct unordered pair sums, including sums with equal summands. This makes the usual finite-set counting bound directly relevant: if , its pair sums lie among the integers from through . Thus the Sidon property forces , the natural scale against which the proposed near-square-root lower bound is measured. O’Bryant (2004)
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.