# Sequences of +1 and -1 with constrained sums

I have to analyse sequences of +1 and -1 that meet specific constraints.

The first constraint is that at any point in a sequence the sum of the elements from the beginning up to that point is always between -1 and +1 inclusive.

So for a sequence of elements ($e_i$), where $e_i$ is either -1 or +1, the following expression holds $\forall n$ where $1 \le n \le length(sequence)$.

$$\left\lvert \sum_{i=1}^ne_i \right\rvert \le 1$$

It becomes apparent when deriving sequences that meet this condition, that when the sum so far is:

• zero, the next element can be -1 or +1
• -1, the next element must be +1
• +1, the next element must be -1

So when I was asked for all possible sequences of length 6, I came up with the following empirically:

-1, +1, -1, +1, -1, +1
-1, +1, -1, +1, +1, -1
-1, +1, +1, -1, -1, +1
-1, +1, +1, -1, +1, -1
+1, -1, -1, +1, -1, +1
+1, -1, -1, +1, +1, -1
+1, -1, +1, -1, -1, +1
+1, -1, +1, -1, +1, -1


All good so far. The problem then introduced the concept of an $m$-selection. An $m$-selection is defined as selecting the $m^{th}$ element, followed by the element at $2m$, $3m$ and so on. We note that the eight sequences above are $1$-selections.

I was asked to find the subset of the eight sequences above (of length 6) where the $2$-selection and the $3$-selection also met the same constraint regarding the sum of the elements.

This was a matter of selecting the sequences where the $2^{nd}$, $4^{th}$ and $6^{th}$ elements were appropriately constrained and the $3^{rd}$ and $6^{th}$ elements were appropriately constrained. By inspection these are the $4^{th}$ and $5^{th}$ sequences:

-1, +1, +1, -1, +1, -1
+1, -1, -1, +1, -1, +1


Again, all good so far. Then I got stuck with the next two parts of the analysis:

• Find all sequences of length 11 that meet the constraint no matter what $m$-selection is used. That is, how do I extend what I've learnt a larger combination?
• Show that it is impossible to find a sequence of length 12 where every $m$-selection meets the constraint.
• You're asking about a restricted case of the Erdos Discrepancy Problem, which deals with homogeneous discrepancy. Two points: 1. Only sequences of length $\leq 6$ which meet the constraints can be extended. 2. Obviously some constraints (if $gcd(m,m')\leq 11$) interact but others are independent. – kodlu Mar 6 '16 at 23:40
• Thanks for the tip. I haven't come across discrepancy theory before. A quick scan online suggests it is a bit beyond my abilities. Is there a simple explanation to my problem? – dave Mar 6 '16 at 23:48
• Well the question is only asking until a short length, say 11, and thus it is a matter of writing the relevant inequalities of the form $$|\sum_{k=1}^{\lfloor 11/m\rfloor} x_{mk}|\leq 1$$ and using what you already know as the two allowed sequence beginnings. – kodlu Mar 7 '16 at 0:06
• @dave : at first, the constraints you wrote reduce to $e_{2i}= - e_{2i-1}$ where the subsequence $e_{2i-1}$ can take any $\pm1$ value – reuns Mar 7 '16 at 0:35