# ±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 (1, −1, 1, −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 ${\displaystyle \textstyle \langle x_{1},x_{2},..\rangle }$ and any integer C, there exist integers k and d such that:

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

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

In October 2010, this problem was taken up by the Polymath Project.[1]

In February 2014, Alexei Lisitsa and Boris Konev of the University of Liverpool, UK,[2] showed that every sequence of 1161 or more elements satisfies the conjecture in the special case C = 2, which proves the conjecture for C ≤ 2. This was the best such bound available at the time. Their proof relies on a SAT-solver computer algorithm whose output takes up 13 gigabytes of data, more than the entire text of Wikipedia at that time,[3] so it cannot be verified by human mathematicians. However, human checking may not be necessary: if an independent computer verification returns the same results, the proof is likely to be correct.[4]

In September 2015, Terence Tao announced a proof of the conjecture,[5] building on work done in 2010 during Polymath5 (a form of crowdsourcing applied to mathematics)[6] and a suggested link to the Elliott conjecture on pair correlations of multiplicative functions.[7] His proof was published in 2016, as the first paper in the new journal Discrete Analysis.[8]

## Barker codes

Main article: Barker code

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

${\displaystyle x_{j}}$ for j = 1, 2, …, N

such that

${\displaystyle \left|\sum _{j=1}^{N-v}x_{j}x_{j+v}\right|\leq 1\,}$

for all ${\displaystyle 1\leq v.[9]

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.

## Notes

1. ^
2. ^ Konev, Boris; Lisitsa, Alexei (17 Feb 2014). "A SAT Attack on the Erdos Discrepancy Conjecture". arXiv:1402.2184.
3. ^
4. ^ Aron, Jacob (February 17, 2014). "Wikipedia-size maths proof too big for humans to check". New Scientist. Retrieved February 18, 2014.
5. ^ Tao, Terence (2015-09-18). "The logarithmically averaged Chowla and Elliott conjectures for two-point correlations; the Erdos discrepancy problem". What's new.
6. ^ article, New Scientist 30 Sep 15 retrieved 21.10.2015
7. ^ article, New Scientist 25 Sep 15 retrieved 21.10.2015
8. ^ Tao, Terence (2016). "The Erdős discrepancy problem". Discrete Analysis: 1–29. arXiv:1509.05363. doi:10.19086/da.609. ISSN 2397-3129. MR 3533300.
9. ^ Barker, R. H. (1953). "Group Synchronizing of Binary Digital Sequences". Communication Theory. London: Butterworth. pp. 273–287.