On sums and permutations

Jakub Konieczny

Published 2015-04-27Version 1

We study the number of distinct sums $\sum_{i=u}^v a_i$, where the sequence $a_1,a_2,\dots,a_n$ is a permutation of $1,2,\dots,n$, and $u \leq v$ vary from $1$ to $n$. In particular, we show that generically there are at least $c n^2$ such sums, for a absolute constant $c$. This answers an old question of Erd\H{o}s and Harheim. We also obtain non-trivial bounds on the maximal possible number of distinct sums, where $n$ is fixed and $a$ is allowed to vary.