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 statement1 of 2

If $A$ and $B$ are Sidon sets in $\{1,\ldots,N\}$ with $(A-A)\cap(B-B)=\{0\}$ , is it true that $\binom{\lvert A\rvert}{2}+\binom{\lvert B\rvert}{2}\leq\binom{f(N)}{2}+O(1)?$

The answer is no; the Erdős Problems page notes that this follows from the solution to Erdős Problem 42.

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

1False ↔2  ∃ C,3    ∀ᶠ (N : ℕ) in Filter.atTop,4      ∀ (A B : Finset ℕ),5        A ⊆ Finset.Icc 1 N →6          B ⊆ Finset.Icc 1 N →7            IsSidon ↑A →8              IsSidon ↑B →9                (A - A) ∩ (B - B) = {0} → ↑(A.card.choose 2 + B.card.choose 2) ≤ ↑((Erdos43.f N).choose 2) + C

SolvedStatement only, no proof

Sources

Search problems.science