Skip to content

Erdős problem 340

Let A={1,2,4,8,13,21,31,45,66,81,97,…}A = \{1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, \ldots\} be the greedy Sidon sequence: we begin with 11 and iteratively include the next smallest integer that preserves the Sidon property (i.e. there are no non-trivial solutions to a+b=c+da + b = c + d). What is the order of growth of AA? Is it true that ∣A∩{1,…,N}∣≫N1/2−ε|A \cap \{1, \ldots, N\}| \gg N^{1/2 - \varepsilon} for all ε>0\varepsilon > 0 and large NN?

Sources

The source's own material, retained exactly.

15 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

340.lean

Retained formal statement5 of 15

Erdős and Graham [ErGr80] also asked about the difference set A−AA - A and whether this has positive density.

[ErGr80] Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980).

FormalConjectures/ErdosProblems/340.leanErdos340.erdos_340.variants.sub_hasPosDensity1 lineExact file
(Set.range Finset.greedySidon - Set.range Finset.greedySidon).HasPosDensity
OpenStatement only, no proof