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 (x1, x2, x3, ...), where xi = (−1)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 and any integer C there exist integers k and d such that:
The Erdős Discrepancy Problem asks for a proof or disproof of this conjecture.
A computer search[1] has shown that there could be no such sequence S achieving the above property for C=2 (and neither, therefore, for C < 2). As of February 2014[update], this is the best such bound available.
As of October 2010[update], this problem is currently being studied by the Polymath Project [3].
Barker codes
A Barker code is a sequence of N values of +1 and −1,
- for j = 1, 2, …, N
such that
for all .[2]
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
Notes
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