Open Collections

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

Banff International Research Station for Mathematical Innovation and Discovery

In this talk, we consider problems and results that go in the opposite direction of the classical theorems in the discrepancy theory. The following statement gives a flavor of our approach. Let $t$, $k$ and $q$ be integers such that $q \ge 0$, $0 \le t < k$, and $t \equiv k \,({\rm mod}\, 2)$, and take $s \in [0,t+1]$ as the unique integer satisfying $s \equiv q + \frac{k-t-2}{2} \,({\rm mod} \, (t+2))$. Then, for any integer $$n \ge \frac{1}{2(t+2)}k^2 + \frac{q-s}{t+2}k - \frac{t}{2} + s$$ and any function $f:[n]\to \{-1,1\}$ with $|\sum_{i=1}^nf(i)|\leq q$, there is a block of $k$ consecutive terms ($k$-block) $B\subset [n]$ with $|\sum_{x\in B}^nf(x)|\leq t$. Moreover, this bound is sharp for all the parameters involved and a characterization of the extremal sequences is given. This is a joint work with Yair Caro and Adriana Hansberg.

Mathematics; Combinatorics; Number theory; Discrete mathematics

video/mp4

Author affiliation: Universidad Nacional Autónoma de México

2020-05-13

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/74419

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/