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.
  • $\begingroup$ 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. $\endgroup$ – kodlu Mar 6 '16 at 23:40
  • $\begingroup$ 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? $\endgroup$ – dave Mar 6 '16 at 23:48
  • $\begingroup$ 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. $\endgroup$ – kodlu Mar 7 '16 at 0:06
  • $\begingroup$ @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 $\endgroup$ – reuns Mar 7 '16 at 0:35

Originally I was after a generic (or algebraic) solution as I thought that drawing all the possible sequences would take too long for sequences of length 11 and 12.

However, I realised that any valid sequence of length 11 must start with one of the two sequences of length 6 that I found for the second part of my question. Combining this insight with the the way the 2-selection reduces the number of sequences, I was able to quickly draw up the possible sequences of length 11. It was then a quick task to reduce these to those that were also 2-, 3-, 4-, ..., 11-selections.

For the sequences of length 12, I took my set of sequences of length 11 and extended them by one. I then worked through the 2-, 3-, 4- and 6-selections (focusing on the factors of 12) and found that no valid sequences existed.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.