Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. Coppersmith and Phillips's Theorem 3.7 (printed p. 177) states: "A sequence of integers in [1,n][1,n] satisfying S2S_2, S3S_3, and S4S_4 contains at most 2n/3−⌊n/512⌋+3log⁡4n−1/22n/3-\lfloor n/512\rfloor+3\log_4n-1/2 elements", where property SkS_k says that no sum of kk adjacent elements of the increasing sequence is an element. The paper is Coppersmith, D. and Phillips, S., On a question of Erdös on subsequence sums, SIAM J. Discrete Math. 9 (1996), no. 2, 173--177; the theorem is recorded on the result page Theorem 3.7. An increasing sequence counted by the function f(n)f(n) of Problem 357 has these properties: if a block of two or more consecutive terms summed to a term, that block and the single term would be two equal sums of consecutive terms. Hence f(n)≤(2/3−1/512)n+O(log⁡n)f(n)\le(2/3-1/512)n+O(\log n), as a thread comment of 9 December 2025 and Lenthall-Cleary's eq. (1.2) observe. The site's commentary credits the bound, through Problem 867, to the unrestricted function g(n)g(n), for sequences that need not increase; a thread comment of 9 April 2026 disputes that application, and this page claims the bound only for f(n)f(n).

Covers. The upper bound f(n)≤(2/3−1/512)n+O(log⁡n)f(n)\le(2/3-1/512)n+O(\log n). The result does not answer whether f(n)=o(n)f(n)=o(n), the problem's question.

Acceptance. The refereed evidence is the journal publication cited above, in the SIAM Journal on Discrete Mathematics. The site labels the problem OPEN, so its commentary credits the paper without settling the problem and no reviewed evidence is listed. The publication record dates the issue to May 1996 and gives no finer date, so the page is dated to the first day of that month.

Depends on. The result page Coppersmith and Phillips's Theorem 3.7.