±1-sequence

In mathematics, a ±1–sequence is a sequence of numbers, each of which is either 1 or −1. One example is the sequence (x₁, x₂, x₃, ...), where x_i = (−1)ⁱ⁺¹.

Such sequences are commonly studied in discrepancy theory.

Erdős discrepancy problem

Let S=(x₁, x₂, x₃,...) be a ±1–sequence, where x_j denotes the j^th term. The Erdős discrepancy problem asks whether there exists a sequence S and an integer C_S, such that for any two positive integers d and k,

$\left| \sum_{i=1}^k x_{id} \right| \leq C_S.$

As of October 2010, this problem is currently being studied by the Polymath Project.

Barker Codes

Main article: Barker code

A Barker code is a sequence of N values of +1 and −1,

$a_j$ for j = 1, 2, …, N

such that

$\left|\sum_{j=1}^{N-v} a_j a_{j+v}\right| \le 1\,$

for all $1 \le v < N$.

Barker codes of length 11 and 13 are used in direct-sequence spread spectrum and pulse compression radar systems because of their low autocorrelation properties.

See also

• Barker code
• Binary sequence
• Discrepancy of hypergraphs

References

• Chazelle, Bernard. The Discrepancy Method: Randomness and Complexity. Cambridge University Press. ISBN 0-521-77093-9. 

External links

• The Erdős discrepancy problem – Polymath Project