Sign sequence

In mathematics, a sign sequence, or ±1–sequence or bipolar 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},\ldots \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

Main article: Barker code

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

x_{j}{\text{ for }}j=1,\ldots ,N

such that

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

for all $1\leq v<N$ .^[9]

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

Notes

↑ "The Erdős discrepancy problem". Polymath Project.
↑ Konev, Boris; Lisitsa, Alexei (17 Feb 2014). "A SAT Attack on the Erdos Discrepancy Conjecture". arXiv:1402.2184.
↑ see Wikipedia:Size of Wikipedia
↑ Aron, Jacob (February 17, 2014). "Wikipedia-size maths proof too big for humans to check". New Scientist. Retrieved February 18, 2014.
↑ Tao, Terence (2015-09-18). "The logarithmically averaged Chowla and Elliott conjectures for two-point correlations; the Erdos discrepancy problem". What's new.
↑ article, New Scientist 30 Sep 15 retrieved 21.10.2015
↑ article, New Scientist 25 Sep 15 retrieved 21.10.2015
↑ 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.
↑ 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)

This article is issued from Wikipedia - version of the 11/14/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.