← All problems

Erdős Problem #340 — Growth of the greedy Sidon sequence

46 years old · traced to

Define a sequence recursively by a1=1a_1=1 and, for each n≥2n\ge 2, let ana_n be the least integer m>an−1m>a_{n-1} such that adjoining mm to the earlier terms preserves the Sidon property. Here a set BB of integers is Sidon if every equality x+y=u+vx+y=u+v with x,y,u,v∈Bx,y,u,v\in B has the same unordered pair of summands on both sides; repeated summands are allowed. Set A={an:n≥1}A=\{a_n:n\ge1\} and A(N)=∣A∩{1,…,N}∣A(N)=\lvert A\cap\{1,\ldots,N\}\rvert. What is the asymptotic order of growth of this greedy sequence? In particular, is it true that for every ϵ>0\epsilon>0 there are constants cϵ>0c_\epsilon>0 and N0(ϵ)N_0(\epsilon) such that

A(N)≥cϵN1/2−ϵ(N≥N0(ϵ))?A(N)\ge c_\epsilon N^{1/2-\epsilon}\qquad(N\ge N_0(\epsilon))?

Erdős Problems #340 O’Bryant (2004)

Background

This greedy Sidon sequence is also called the Mian–Chowla sequence; its first terms are 1,2,4,8,13,21,31,45,66,81,97,…1,2,4,8,13,21,31,45,66,81,97,\ldots. 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 A(N)=mA(N)=m, its m(m+1)/2m(m+1)/2 pair sums lie among the 2N−12N-1 integers from 22 through 2N2N. Thus the Sidon property forces A(N)=O(N1/2)A(N)=O(N^{1/2}), the natural scale against which the proposed near-square-root lower bound is measured. O’Bryant (2004)

References

Progress summary

Never refreshed

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.