Skip to content

Erdős Problem #1109

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory.

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.

UNACCEPTED DRAFT — mathematical editorial review pending

This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.

Review the underlying draft on GitHub.

The question in plain language

Choose some integers between \(1\) and \(N\). Can we arrange that every sum of two chosen numbers is squarefree, meaning no prime square divides it?

Erdős Problem #1109 asks how large such a set \(A\) can be. Writing the maximum size as \(f(N)\), the conjecture is that it grows extraordinarily slowly, perhaps no faster than a fixed power of \(\log N\).

The condition applies to \(a+a\) as well as to sums of different elements. In particular, each \(2a\) must be squarefree.

A small example

For \(N=16\), exact exhaustive search shows

\[ f(16)=2. \]

One optimal set is \(A=\{11,15\}\), whose distinct two-term sums are

\[ A+A=\{22,26,30\}. \]

All three are squarefree. The computation first filters the seven numbers with squarefree self-sums, then checks every subset for all pairwise sums. No three-element subset qualifies.

This is an exact result for \(N=16\), not an estimate of the growth of \(f(N)\) for arbitrarily large \(N\).

What is known

Erdős and Sárközy (1987) studied the problem and established the rough bounds

\[ \log N\ll f(N)\ll N^{3/4}\log N. \]

The maintained catalogue reports Konyagin's (2004) improvements:

\[ (\log\log N)(\log N)^2 \ll f(N)\ll N^{11/15+o(1)}. \]

The conjectured \(f(N)\le N^{o(1)}\), let alone polylogarithmic growth, is still open.

The infinite analogue is Problem #1103: construct an infinite increasing sequence with squarefree pair sums while making its terms grow slowly. Bounds on \(f(N)\) yield restrictions on the growth of such an infinite sequence, but the two problems must retain their different quantifiers.

GCL's current state

Authenticated source audit #2380 reproduces the complete bounded \(N=16\) search and maintains the diagonal \(a=a\) constraint.

The current catalogue indicates a formalized statement, but the older pinned formal-conjectures snapshot used by GCL has no corresponding #1109 file. That requires version reconciliation, not an inference that there is no current formalization.

What remains

Independently inspect the 1987 and 2004 extremal arguments, confirm all exponent losses and squarefree-sum conventions, and compare the finite and infinite versions without conflating them. An independent modular formulation could verify finite maxima for larger \(N\).

Sources and claim boundaries

Erdős Problem #1109; Erdős–Sárközy (1987); Konyagin (2004), externally reported bounds; GCL source return #2380. Exact \(f(16)=2\) is independently verified. The general growth conjecture remains open. This is an unaccepted draft.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2380 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: FORMAL_SOURCE_REFRESH_REQUIRED.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider 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