±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 $\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_{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

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

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

such that

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

for all $1 \le v < N$.^[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.

See also

• Binary sequence
• Discrepancy of hypergraphs

Notes

1. "The Erdős discrepancy problem". Polymath Project.
2. Konev, Boris; Lisitsa, Alexei (17 Feb 2014). "A SAT Attack on the Erdos Discrepancy Conjecture". arXiv:1402.2184.
3. see Wikipedia:Size of Wikipedia
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 Statesman 30 Sep 15 retrieved 21.10.2015
7. article, New Statesman 25 Sep 15 retrieved 21.10.2015
8. Tao, Terence (2016-02-27). "The Erdős discrepancy problem". Discrete Analysis. 2016:1: 29pp. arXiv:1509.05363. doi:10.19086/da.609.
9. Barker, R. H. (1953). "Group Synchronizing of Binary Digital Sequences". Communication Theory. London: Butterworth. pp. 273–287.

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
• Computer cracks Erdős puzzle – but no human brain can check the answer—The Independent (Friday, 21 February 2014)