Skip to content

Erdős Problem #817

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

Given k>=3, let g_k(n) be the LEAST N for which some set A subset {1,...,N} of size n has all its {0,1}-subset sums free of any NONTRIVIAL arithmetic progression of length k. The subset-sum family includes the empty sum 0. Is g_3(n)>>3^n with absolute constant? OPEN.

A small example

Take A={1,3,9}. Its eight subset sums {0,1,3,4,9,10,12,13} contain no nonconstant 3-term AP. Digitwise proof: if x,z and y have ternary digits 0/1 and x+z=2y, there is no carrying, so in each digit x_i+z_i=2y_i, which forces x_i=y_i=z_i. Therefore the progression is trivial. This exact proof applies to all n and establishes an upper bound, not the desired lower bound.

What is known

Maintained https://www.erdosproblems.com/latex/817, read 2026-10-14: Erdős–Sárközy obtained g_3(n)>>3^n/n^O(1), but the stronger constant-times-3^n lower bound remains unknown. Historical theorem original bibliography appears implicit and full source not verified. A simple upper construction A={1,3,...,3^(n-1)} has all subset sums represented by ternary digits 0 or1, so a nontrivial 3-term AP cannot occur; g_3(n)<=3^(n-1).

There is an explicit family proving the upper bound \(g_3(n)\leq3^{n-1}\): take \(A=\{1,3,\ldots,3^{n-1}\}\). Every subset sum has base-three digits only 0 and 1. If three such sums \(x,y,z\) satisfy \(x+z=2y\), adding digits makes no carries. At each digit, the equation \(x_i+z_i=2y_i\) with all digits 0 or 1 forces \(x_i=y_i=z_i\). Thus \(x=y=z\) and there is no nontrivial arithmetic progression. This elementary constructive lemma is a genuine finite/combinatorial derivation, but it establishes an UPPER bound, not the conjectured constant times \(3^n\) lower bound.

The relevant quantity is the LEAST possible maximum generator,

$$

g_k(n)=\min\left{\max A:\ |A|=n,\ \left{\sum_{a\in A}\epsilon_a a:\epsilon_a\in{0,1}\right} \text{ has no nontrivial }k\text{-term AP}\right}.

$$

The powers-of-three construction already proves \(g_3(n)\leq3^{n-1}\). This upper construction does not resolve the open conjecture that \(g_3(n)\gg3^n\) with a constant independent of \(n\).

GCL's current state

The original authenticated RESULT/1 source return records BOUNDED_TASK_DESIGNED and retains the original mathematical qualifications. This is an editorially reviewed explanatory article in the EC-BULK-005-R9 protected batch, effective only when that exact-hash transaction merges. The corresponding maintained Erdős statement and its bibliography were inspected. This editorial decision does not certify any full original theorem proof, independent external formalization, or Lean kernel check.

Preserved source-review qualifications: open ap free subset sum cube with ternary upper. See the immutable 128-case critical review record for the complete source-return caveats.

What remains

Implement no-nontrivial-3AP checker for ternary subset sum sets n<=7, and prove the digitwise carry-free argument in publication language. Source-lock original Erdős–Sárközy lower estimate, including polynomial exponent, and retain OPEN constant-times-3^n question.

Critical review must independently verify the original primary theorem, hypotheses, quantitative constants and simple examples. Passing source tests does not establish publication or mathematical proof certification.

Sources and claim boundaries

  • Erdős problem #817, maintained LaTeX and original authenticated source return, checked 14 October 2026.
  • Pinned teorth/erdosproblems revision 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, Git blob 4e60263a80af6207aca494d2e1388e44fa372889. The source comment contains original bibliography and limits of direct proof inspection.
  • Editorial acceptance: NONE. Protected merge: NONE. Real-browser MathJax: NOT VERIFIED. Lean/new theorem certification: NOT CLAIMED.

Editorial source decision: R9 critical review, REVIEWED as a source-grounded explanation only. All open mathematical questions, primary-proof fidelity obligations, and external formalization caveats remain separate.

Catalogue and evidence provenance

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