Sign 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

Around 1932 mathematician Paul_Erdős conjectured that for any infinite ±1-sequence $\textstyle \langle x_{1},x_{2},..\rangle$ and any integer C there exist integers k and d such that:

$\left|\sum _{i=1}^{k}x_{id}\right|>C$

The Erdős Discrepancy Problem asks for a proof or disproof of this conjecture.

A SAT-solver-based proof has shown that every sequence of 1161 or more elements satisfies the conjecture in the special case C=2: this constitutes a proof of the conjecture for C≤2. As of February 2014, this is the best such bound available.

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

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|\leq 1\,$

for all $1\leq 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

• 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