Skip to content

Erdős Problem #36

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, 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

Divide the first \(2n\) positive integers into two disjoint sets \(A\) and \(B\), each with \(n\) elements. For any integer shift \(k\), count the ordered pairs \((a,b)\in A\times B\) satisfying \(a-b=k\). The maximum overlap is the largest such count over all shifts; let \(M(n)\) be the smallest possible maximum overlap among all balanced partitions. Erdős Problem #36 asks for the precise limiting constant of \(M(n)/n\), with related refinements.

This minimizes a maximum over shifts, so the average alone cannot determine the optimum.

A small example

Every cross-pair contributes to exactly one difference \(k=a-b\), hence

\[ \sum_k\#\{(a,b)\in A\times B:a-b=k\}=n^2. \]

Because \(A\) and \(B\) are disjoint, zero never occurs as a difference, and all differences lie among the \(4n-2\) nonzero integers between \(-(2n-1)\) and \(2n-1\). Pigeonhole therefore implies

\[ M(n)\ge\left\lceil\frac{n^2}{4n-2}\right\rceil. \]

For \(n=2\), the lower bound is one. The GCL audit's finite search reports \(M(2)=1\). Such small cases and this weak bound do not settle the limiting constant.

What is known

The maintained registry lists several stronger literature bounds but still marks the exact asymptotic value as OPEN. The audited source packet did not verify all historical paper hypotheses, so those constants should not be treated as newly certified here.

GCL's current state

Source audit #1305 checks the balanced-partition normalization, ordered-pair convention and frozen formal definitions. It reports an exact enumeration for \(n=1,\ldots,6\), obtaining \(M(n)=1,1,2,2,3,3\), and derives the elementary cross-pair mass identity. The formal target is not proved by this arithmetic.

What remains

Sharper structural control on the overlap profiles of balanced partitions is needed to identify the exact asymptotic optimum. Counting the total number of pairs alone cannot fix the best distribution of their differences.

Sources and claim boundaries

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1305 — 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