Erdős Problem #781
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (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
Choose the least integer \(f(k)\) so that every red/blue colouring of the integers from 1 to \(f(k)\) contains a monochromatic descending wave of length \(k\): an increasing sequence whose consecutive gaps never increase.
Brown, Erdős and Freedman proposed the \quadratic formula \(f(k)=k^2-k+1\). This exact conjecture is false. Alon and Spencer proved in 1989 that the correct growth rate has cubic rather than \quadratic order.
A small example
The increasing sequence \(1,3,4\) has gaps 2 and 1, so it is a descending wave. Reflect the surrounding interval \([5]\) by the map \(x\mapsto 6-x\) and then write the transformed entries in increasing order. The image is \(2,3,5\), whose gaps are 1 and 2: an ascending wave.
The reflection preserves the two colours, although it reverses the sequence order. Consequently, every descending wave in one colouring corresponds to an ascending wave in the reflected colouring of the same interval, and conversely. This simple reversible mapping matters because the original 1989 paper is about ascending, not descending, waves.
What is known
A sequence
is descending when
Equivalently, \(2x_j\geq x_{j-1}+x_{j+1}\). The conjectured exact formula was \(k^2-k+1\), and Brown, Erdős and Freedman established a lower bound of that order together with a cubic upper bound in Quasi-progressions and descending waves, JCTA (1990), 81–95.
N. Alon and J. Spencer, Ascending waves, Journal of Combinatorial Theory, Series A 52 (1989), 275–287, prove for their ascending-wave threshold positive constants \(c_1,c_2\) with
This is the article's original published abstract theorem, not merely a later catalogue paraphrase. Reflection of the interval proves that the ascending and descending 2-colouring thresholds are identical. Thus the cubic growth carries over without adjusting asymptotic constants, even though the direction of the gap inequalities changes.
The lower cubic bound for arbitrarily large \(k\) contradicts the proposed universal \quadratic identity. It does not assert any exact value of \(f(k)\) for a particular fixed \(k\) without additional calculation.
GCL's current state
The authenticated original RESULT/1 source return records SOURCE_LOCK_READY and preserves its issue-bound mathematical source observations. This explanatory article is REVIEWED under the exact-hash EC-BULK-005-R6 editorial transaction, subject to the protected merge of PR #2676. Its original source-audit status is retained. Editorial acceptance and public MathJax validation do not certify any original research theorem, external Lean file, or complete historical proof.
Unclosed mathematical proof/source qualifications: BROWN_ERDOS_FREEDMAN_1990_PROOF_UNINSPECTED; ASYMPTOTIC_PROOF_NOT_INDEPENDENTLY_REPLAYED.
What remains
Check the ascending/descending reflection for every increasing triple in small intervals using executable tests and verify that the transformation is an involution. Source-lock the full Brown–Erdős–Freedman 1990 proof for its exact lower and upper constants, and compare the original 1989 theorem hypotheses with the maintained catalogue. Optionally calculate finite \(f(3)\) and \(f(4)\) by exhaustive two-colouring, without extrapolating to all \(k\). The primary theorem proof replay remains outstanding; a separate editorial source review and public MathJax gate support this batch.
For mathematical proof certification, the complete primary argument and any external formalization must undergo separate independent replay. The bounded finite calculation is recorded in the governed R6 fixture; editorial approval does not discharge the outstanding research obligations.
Sources and claim boundaries
- Erdős problem #781 and authenticated source return.
- N. Alon, J. Spencer, Ascending waves, JCTA 52(2) (1989), 275–287, DOI.
- Editorial decision: exact-hash reviewed explanatory article, protected R6 transaction. Mathematical theorem proof / external Lean certification: NOT CLAIMED. The original SOURCE_LOCK_READY return, primary-source attribution, and proof-review holds remain.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2052 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- 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.