Erdős Problem #34 — Permutations of $[n]$ with $cn^2$ distinct interval sums

Erdős

Let $a_1 < \ldots < a_k \leqslant n$ be a sequence of integers and form all sums $\sum_{i=u}^{v} a_i$ . Can one have $cn^2$ distinct numbers in this set for some $c > 0$ ? This does not happen for the choice $a_i = i$ . What happens if we drop the monotonicity restriction but just insist that the $a_i$ be distinct? Perhaps some permutation of $\{1, 2, \ldots, n\}$ has $cn^2$ such "interval" sums.

Progress summary

Solved

A 2015 result shows that some permutations have a fixed positive share of all possible consecutive sums, so the proposed vanishing bound is false.

The problem asks whether every permutation of $1,\ldots,n$ has only $o(n^2)$ distinct sums of consecutive terms. It is an old question of Erdős and Harzheim, and the universal claim is false.

Known results

Konieczny, 2015: a uniformly random permutation has, with high probability, $|S(a)|\sim\left(\frac{1+e^{-2}}{4}\right)n^2$ , giving permutations with a positive quadratic number of distinct sums.

2015 probabilistic counterexample

Konieczny’s paper establishes the quadratic lower bound through random permutations, directly disproving the proposed $o(n^2)$ estimate. The same work also studies the maximum possible value of $|S(a)|$ .

Current status (as of March 2026): The original assertion is settled negatively; permutations with $\Theta(n^2)$ distinct consecutive sums are known, while sharper extremal constants remain a separate question.

Sources

Sources & referencesView supporting material

Primary source

Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique 28 (1980).

erdos-problem number-theory

3 weeks ago