Skip to content

Erdős Problem #66

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

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

Choose a set \(A\) of positive integers. For each \(n\), count how many ordered pairs of elements of \(A\) add up to \(n\). Erdős asked whether one can choose \(A\) so that this count approaches a fixed positive multiple of \(\log n\) for every sufficiently large \(n\), with the ratio tending to a positive constant.

Write

\[ r_A(n)=\#\{(a,b)\in A^2:a+b=n\}. \]

The question is whether \(r_A(n)/\log n\) can have a finite, nonzero limit. The maintained catalogue records this as open.

A small example

For \(A=\{1,2,3\}\), the number \(4\) has three ordered representations: \((1,3)\), \((2,2)\), and \((3,1)\). Thus \(r_A(4)=3\). The distinction between ordered and unordered representations matters when translating source statements.

A useful general identity is

\[ \sum_{n\le x}r_A(n) =\#\{(a,b)\in A^2:a+b\le x\}. \]

Let \(A(x)=|A\cap[1,x]|\). Every pair with \(a,b\le x/2\) contributes to this sum, while every contributing pair has \(a,b\le x\). Consequently,

\[ A(x/2)^2\le\sum_{n\le x}r_A(n)\le A(x)^2. \]

What is known

If the desired limit existed and equaled \(c>0\), then summing \(r_A(n)\sim c\log n\) would give

\[ \sum_{n\le x}r_A(n)\sim c\,x\log x. \]

The elementary pair-counting bounds would then force

\[ (c+o(1))x\log x\le A(x)^2 \le(2c+o(1))x\log x. \]

So such a set would necessarily have about \(\sqrt{x\log x}\) elements up to \(x\), within constant factors. This is a necessary density constraint, not an existence construction.

The 2007 primary abstract of Gábor Horváth, An improvement of a theorem of Erdős and Sárközy, confirms a more general obstruction. If \(g(n)\) is eventually nondecreasing, tends to infinity and obeys \(g(n)=o(n/(\log n)^2)\), then for any fixed \(\varepsilon>0\) the estimate \(|R_2(n)-g(n)|\le(1-\varepsilon)\sqrt{g(n)}\) cannot hold for every sufficiently large \(n\). The abstract also attributes to Erdős–Sárközy the exclusion of an error \(o(\sqrt{g(n)})\) under those hypotheses. Setting \(g(n)=\log n\) satisfies the growth conditions. However, the paper's \(R_2\) representation-count convention has not been independently matched to this article's ordered-pair \(r_A\); no numerical constant should be transported across that convention without checking the full primary text. Even for the matching convention, these square-root error obstructions are weaker than excluding an error \(o(\log n)\), so the original ratio-limit question remains open. The maintained catalogue also describes random constructions with exceptional integers; they do not give the required full limit.

GCL's current state

The pinned catalogue and maintained Erdős #66 classify the problem as OPEN. The present GCL work derives the necessary counting-scale lemma from the exact ordered-pair convention. The original assignment is #1335.

This is an unaccepted local draft. The primary Horváth abstract and its growth hypotheses have been checked; the full proof, original Erdős–Sárközy paper and the distinction between \(R_2\) and ordered \(r_A\) still require source-level reconciliation.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

A bounded task is to formalize the ordered additive convolution and the pair-counting inequalities, then prove the necessary \(\Theta(\sqrt{x\log x})\) scale under the assumed limit. The real open difficulty is obtaining or excluding such precise representation counts without exceptional integers. A necessary counting scale alone does not settle existence.

Sources and claim boundaries

No solution, new impossibility theorem, primary-source certification or editorial acceptance is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1335 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: PROTECTED_READY_BACKLOG.
  • 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