Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be a sequence of distinct real numbers. Determine
where the maximum is taken over all monotonic subsequences.
Let be a sequence of distinct real numbers. Determine the largest constant such that, for all such sequences,
where the maximum is taken over all monotonic subsequences.
Source: erdosproblems.com/1026
An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.
The site labels the problem SOLVED (LEAN): . It credits the lower bound , the stronger finite form, to Tidor, Wang and Yang [TWY16] as its first proof, implicit in Wagner [Wa17], and names the Lean proof of the finite form that the AI system Aristotle produced, posted by Alexeev, together with Chan's second proof from the Erdős–Szekeres theorem; the upper bound is Cambie's construction in the thread.
The site's wording is ambiguous, as its commentary says: for one given sequence the maximum is a finite computation, and the wording names neither a normalization nor the extremal quantity to be found. The precise Statement replaces the object of "Determine", the maximum itself, with "the largest constant such that, for all such sequences," that maximum exceeds . The ambiguity is already in Erdős's text: [Er71, item 22], on the card Erdős 1971, asks only to determine over the monotonic subsequences of distinct numbers and calls the question unsettled, and Steele's survey [St95, Section 12] and Problem 3.4 of [TWY16] repeat that form. The inserted words are the site's: its commentary adopts this precise question, posed by Wouter van Doorn in the site's thread on 12 September 2025 after discussion with Desmond Weisenberg and Stijn Cambie, and the site's label SOLVED (LEAN), with the answer , describes it. The commentary states the question for all sequences of reals; the precise Statement keeps the site's distinct reals. The normalization agrees with a weighted question of Erdős that Steele reports in the same section, citing Chung (1980, p. 278): to determine , the least over nonnegative weights with sum of the largest sum of the weights along a monotone subsequence, which Steele expects to satisfy . No result about the wording before it was made precise is recorded.