Erdős problem 43 · problems.science

If Sidon sets $A, B \subseteq \{1, \dots, N\}$ satisfy $(A-A) \cap (B-B) = \{0\}$ , must $\binom{|A|}{2} + \binom{|B|}{2} \le \binom{f(N)}{2} + O(1)$ , where $f(N)$ is the largest Sidon-set size in $[N]$ - and can the bound be improved by a fixed proportion when $|A| = |B|$ ?

Sources

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

3 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

43.lean

Retained formal statement2 of 2

If $A$ and $B$ are equal-sized Sidon sets in $\{1,\ldots,N\}$ with $(A-A)\cap(B-B)=\{0\}$ , can the bound be improved to $\binom{\lvert A\rvert}{2}+\binom{\lvert B\rvert}{2} \leq (1-c+o(1))\binom{f(N)}{2}$ for some constant $c>0$ ?

The answer is no; the Erdős Problems page records a negative answer due to Barreto.

FormalConjectures/ErdosProblems/43.leanErdos43.erdos_43.parts.ii13 linesExact file

1False ↔2  ∃ c > 0,3    ∃ o,4      o =o[Filter.atTop] 1 ∧5        ∀ᶠ (N : ℕ) in Filter.atTop,6          ∀ (A B : Finset ℕ),7            A ⊆ Finset.Icc 1 N →8              B ⊆ Finset.Icc 1 N →9                IsSidon ↑A →10                  IsSidon ↑B →11                    A.card = B.card →12                      (A - A) ∩ (B - B) = {0} →13                        ↑(A.card.choose 2 + B.card.choose 2) ≤ (1 - c + o N) * ↑((Erdos43.f N).choose 2)

SolvedStatement only, no proof

Sources

Search problems.science