Zero-Sum Ascending Waves

Abstract

A sequence of positive integers $a_1\le a_2\le \dots \le a_n$ is called an ascending monotone wave of length $n$, if $a_{i+1}–a_i\ge a_i–a_{i-1}$ for $i=2,\dots ,n-1$. If $a_{i+1}–a_i>a_i–a_{i-1}$ for all $i=2,\dots ,n-1$ the sequence is called an ascending strong monotone wave of length $n$. Let $Z_k$ denote the cyclic group of order $k$. If $k|n$, then we define $MW(n,Z_k)$ as the least integer $m$ such that for any coloring $f:\{1,\dots ,m\}\to Z_k$, there exists an ascending monotone wave of length $n$, where $a_n\le m$, such that $\sum _{i=1}^{n}f(a_i)=0\mathrm{mod}k$. Similarly, define $SMW(n,Z_k)$, where the ascending monotone wave in $MW(n,Z_k)$ is replaced by an ascending strong monotone wave. The main results of this paper are:

1. $\frac{\sqrt{k}}{2}n\le MW(n,Z_k)\le c_1(k)n$. Hence, this result is tight up to a constant factor which depends only on $k$.
2. $(\genfrac{}{}{0ex}{}{n}{2})<SMW(n,Z_k)\le c_2(k)n^2$. Hence, this result is tight up to a constant factor which depends only on $k$.
3. $MW(n,Z_2)=3n/2$.
4. $\frac{23}{12}n–7/6\le MW(n,Z_3)\le 2n+3$.

These results are the zero-sum analogs of theorems proved in [1] and [5].