Problem 34

For any permutation $\pi\in S_n$ of $\{1,\ldots,n\}$ let $S(\pi)$ count the number of distinct consecutive sums, that is, sums of the shape $\sum_{u\leq i\leq v}\pi(i)$ . Is it true that

S(\pi) = o(n^2)

for all $\pi\in S_n$ ?

Source: erdosproblems.com/34

Number theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

The site labels the problem DISPROVED (LEAN), a catalog label explained under Formalization. Konieczny's Proposition 1.1 (J. Combinatorics 12 (2021), 413--477, refereed; arXiv:1504.07156v5) gives for every $n\ge1$ the permutation $1,n,2,n-1,3,n-2,\ldots$ with $S(\pi)\ge n^2/4$ , so $S(\pi)=o(n^2)$ fails along these permutations. Hegyvári's 1986 Theorem 1 (claims checked) gives $(1/3+o(1))n$ distinct integers in $[1,n]$ with all consecutive sums distinct, and Konieczny (Section 1.5) and the site deduce from it a permutation with $S(\pi)\ge(1/18+o(1))n^2$ , the first refutation; the paper itself states nothing about permutations. The extremal behavior is known to constants: $(3/2-2/\sqrt e+o(1))n^2\le\max_\pi S(\pi)\le(1/4+\pi/16+o(1))n^2$ (Konieczny's Theorem 1.2), a uniformly random permutation has $S(\pi)=((1+e^{-2})/4+o(1))n^2$ in probability (Theorem 1.3), and $\min_\pi S(\pi)\ge n^{3/2}/(4\sqrt2)$ (Proposition 6.1), while $S(\iota)=n^{2-o(1)}$ for the identity $\iota$ . The two refutations are recorded as the accepted claim pages Hegyvári 1986 and Konieczny 2015. The proof claim of 15 September 2026 on the minimum $g(n)$ has no claim page: it concerns a question of the site's commentary, not the page's question, and settles no instance of the problem.

Ko15: Konieczny, J., On consecutive sums in permutations. arXiv:1504.07156 (2015); v5 of 27 August 2021 (46 pp.) and J. Combinatorics 12 (2021), no. 3, 413--477, DOI 10.4310/joc.2021.v12.n3.a3 (the statements cited agree word for word in the two versions). Proposition 1.1 (p. 2; journal pp. 414--415), Theorem 1.2 and Question 2 (pp. 2--3; journal pp. 415--416), Theorem 1.3 (p. 3; journal p. 416), Section 1.5 (p. 3; journal pp. 416--417), Proposition 6.1 and Questions 3--4 (pp. 42--44; journal pp. 471--474). Library home: Konieczny 2015.
He86: Hegyvári, N., On consecutive sums in sequences. Acta Math. Hungar. 48 (1986), no. 1--2, 193--200, DOI 10.1007/BF01949064. The introduction and Theorem 1 (printed p. 193), the proof (pp. 193--194, followed for structure): $(1/3+o(1))n\le f(n)\le(2/3+o(1))n$ for the maximum number of integers in $[1,n]$ , not required to be increasing, with all consecutive sums distinct, Konieczny's $k_{\max}(n)$ . Library home: Hegyvári 1986; result page Hegyvári 1986, Theorem 1.
Er77c: Erdős, P., Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43--72. Printed p. 71: the passage below. Library home: Erdos 1977.
ErGr80: Erdős, P. and Graham, R. L., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique 28, Université de Genève (1980). Printed p. 58: the passage below. Library home: Erdős and Graham 1980.
Be24: Beker, A., On a problem of Erdős and Graham about consecutive sums in strictly increasing sequences. Bull. Lond. Math. Soc. (2024), DOI 10.1112/blms.13098; arXiv:2311.10087 (16 November 2023). Not held; the monotone variant of the monograph's paragraph (Problem 356), context only.
OEIS: The entries A389241 (the maximum, 2025), A390187 (the minimum, 2025) and A234813 (the identity permutation, 2014) of The On-Line Encyclopedia of Integer Sequences, read as ordinary web sources; their terms were not verified here.

Problem 34

Status

Proof claims

Discussion