Subsequence sums in permutations

Abstract

A sequence of positive integers $(a_1,a_2,\dots ,a_k)$ is called $\ell$-additive if $a_1+a_2+\cdots +a_k=\ell a_1$ or $\ell a_k$. In this paper, we prove that for all $k\ge 3$, if $n$ is sufficiently large, then every permutation of $\{1,2,\dots ,n\}$ has a 2-additive subsequence of length $k$. We also provide polynomial bounds for the smallest $n$ such that every permutation of $\{1,2,\dots ,n\}$ has a 2-additive subsequence of length $k$. When only monotone subsequences are considered, we show that $18$ is the smallest $n$ such that every permutation of $\{1,2,\dots ,n\}$ has a monotone 2-additive subsequence of length three. Strong bounds are obtained for the minimum number of $\ell$-additive subsequences of any length, as well as monotone $2$-additive subsequences of length three. Using techniques in arithmetic Ramsey theory, we also show similar results for products and inverse sums.

16 pages, fixed a Latex package issue