Erdős problem 862 · problems.science

Let $A_1(N)$ be the number of maximal Sidon subsets of $\{1,\ldots,N\}$ . Is it true that $A_1(N) > 2^{N^c}$ for some constant $c>0$ ?

Sources

Browse retained paths and inspect the exact material available for this Problem.

3 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

862.lean

Retained formal statement3 of 3

This is resolved as a consequence of results of Saxton and Thomason [SaTh15] - they prove that the number of Sidon sets in $\{1,\ldots,N\}$ is at least $2^{(1.16+o(1))N^{1/2}}$ . Since each Sidon set is contained in a maximal Sidon set, and each maximal Sidon set contains at most $2^{(1+o(1))N^{1/2}}$ Sidon sets, it follows that $A_1(N) \geq 2^{(0.16+o(1))N^{1/2}}.$

FormalConjectures/ErdosProblems/862.leanErdos862.erdos_862.variants.lower_bound1 lineExact file

1∀ (ε : ℝ), 0 < ε → ∀ᶠ (N : ℕ) in Filter.atTop, 2 ^ ((0.16 - ε) * ↑N ^ (1 / 2)) ≤ ↑(Erdos862.numMaximalSidonSets N)

SolvedStatement only, no proof

Sources

Search problems.science