Zero-sum subsequences in bounded-sum $\{-1,1\}$-sequences

Abstract

The following result gives the flavor of this paper: Let $t$, $k$ and $q$ be integers such that $q\ge 0$, $0\le t<k$ and $t\equiv k(\mathrm{mod}2)$, and let $s\in [0,t+1]$ be the unique integer satisfying $s\equiv q+\frac{k-t-2}{2}(\mathrm{mod}(t+2))$. Then for any integer $n$ such that \[n \ge \max\left\{k,\frac{1}{2(t+2)}k^2 + \frac{q-s}{t+2}k - \frac{t}{2} + s\right\}\] and any function $f:[n]\to \{-1,1\}$ with $|{\sum }_{i=1}^{n}f(i)|\le q$, there is a set $B\subseteq [n]$ of $k$ consecutive integers with $|{\sum }_{y\in B}f(y)|\le t$. Moreover, this bound is sharp for all the parameters involved and a characterization of the extremal sequences is given. This and other similar results involving different subsequences are presented, including decompositions of sequences into subsequences of bounded weight.

29 pages