Skip to content

Erdős Problem #43

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: number theory, sidon sets, additive combinatorics.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

Suppose \(A\) and \(B\) are Sidon sets of integers from 1 to \(N\) whose sets of differences have no common nonzero element. Let \(f(N)\) be the largest possible cardinality of a Sidon set in that interval. Erdős Problem #43 contains two separate questions.

First, must the numbers of unordered pairs of different elements satisfy

\[ \binom{|A|}{2}+\binom{|B|}{2} \le \binom{f(N)}{2}+O(1)? \]

Second, when \(|A|=|B|\), can this bound be improved by a fixed positive fractional saving asymptotically? The maintained registry reports negative answers to both questions, but they have different proof routes.

A small example

For the Sidon set \(A=\{1,2,4\}\), there are three unordered pairs of distinct elements and three positive differences. A singleton \(B=\{3\}\) has no nonzero differences, so it is automatically compatible with \(A\). The two pair counts add to \(3+0=3\).

This finite example cannot disprove a bound with an unspecified universal additive constant. The first conjecture fails only if its excess can become arbitrarily large.

What is known

The negative answer to the first question follows from the general statement for any fixed \(M\) reported for Problem #42. Choose \(A\) with the maximal possible size \(f(N)\). For each fixed \(M\), #42 supplies, at sufficiently large \(N\), a compatible \(B\) with \(M\) elements. If the first inequality held with one fixed constant \(C\), it would require

\[ \binom M2\le C \]

for every \(M\), a contradiction. This implication is elementary given the deep #42 theorem; it is not an independent verification of that theorem.

The public registry attributes a negative answer to the equal-cardinality question to Kevin Barreto. A related upper bound was discussed by Terence Tao. The first-question contradiction by itself does not resolve the second question, so their mathematical evidence must remain separate.

GCL's current state

Source audit #1312 reconstructed the precise conditional contradiction, source-status drift and two-part formal boundary. The frozen Formal Conjectures file has distinct research theorem statements annotated with negative answers, but their bodies are unfilled. No current external formal proof has been independently replayed by GCL.

What remains

Both original bounds are reported disproved. GCL's separate work is to source-check the general #42 proof for the first part and independently inspect Barreto's equal-size construction for the second, preserving external attribution and exact quantifiers.

Sources and claim boundaries

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1312 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction