±1-sequence

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

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.

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[edit]

Main article: Barker code

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

for j = 1, 2, …, N

such that

for all .[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[edit]

Notes[edit]

  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.2184free to read. 
  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 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.05363free to read. 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. 

References[edit]

External links[edit]