Sign sequence: Difference between revisions

Content deleted Content added

Inline

Revision as of 15:39, 3 April 2014

In mathematics, a ±1–sequence is a sequence of numbers, each of which is either 1 or −1. One example is the sequence $(x 1, x 2, x 3, ...)$ , where $x i = (-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 $\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 Octobr 2010, this problem was taken up by the Polymath Project^[1]

A SAT-solver-based proof ^[2] has shown that every sequence of 1161 or more elements satisfies the conjecture in the special case C = 2: this constitutes a proof of the conjecture for C ≤ 2. As of February 2014^[update], this is the best such bound available.

Alexei Lisitsa and Boris Konev of the University of Liverpool, UK, used a computer to solve part of the discrepancy problem. In February 2014, the computer showed that an infinite sequence will always have a discrepancy larger than 2.^{[clarification needed]} The main issue with the proof is that it takes up 13 gigabytes of data, which larger than the size of all the text on Wikipedia as of 2014, and so cannot be verified by human mathematicians. However, it may not be necessary to have a human check the proof. If a different computer-based method is used and returns the same results then the proof is likely to be correct.^[3]

Barker codes

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

a_{j}

for j = 1, 2, …, N

such that

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

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

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

^ "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. {{cite journal}}: Cite journal requires |journal= (help)
^ Aron, Jacob (February 17, 2014). "Wikipedia-size maths proof too big for humans to check". New Scientist. Retrieved February 18, 2014.
^ 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)

[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. {{cite journal}}: Cite journal requires |journal= (help)

[3] Aron, Jacob (February 17, 2014). "Wikipedia-size maths proof too big for humans to check". New Scientist. Retrieved February 18, 2014.

[4] Barker, R. H. (1953). "Group Synchronizing of Binary Digital Sequences". Communication Theory. London: Butterworth. pp. 273–287.

[1]

[2]

[3]

[4]

@@ Line 12: / Line 12: @@
 The Erdős Discrepancy Problem asks for a proof or disproof of this conjecture.
-{{Asof|2010|October}}, this problem is currently being studied by the [[Polymath Project]] [http://michaelnielsen.org/polymath1/index.php?title=The_Erd%C5%91s_discrepancy_problem].
+In Octobr 2010, this problem was taken up by the [[Polymath Project]]<ref>{{cite web | url = http://michaelnielsen.org/polymath1/index.php?title=The_Erd%C5%91s_discrepancy_problem | title = The Erdős discrepancy problem | publisher = [[Polymath Project]] }}</ref>
-A SAT-solver-based proof <ref>[http://arxiv.org/pdf/1402.2184v2.pdf 2014 arXiv preprint], featured in [http://www.newscientist.com/article/dn25068-wikipediasize-maths-proof-too-big-for-humans-to-check.html NewScientist website]</ref> has shown that every sequence of 1161 or more elements satisfies the conjecture in the special case ''C''&nbsp;=&nbsp;2: this constitutes a proof of the conjecture for ''C''&nbsp;≤&nbsp;2. {{Asof|2014|February}}, this is the best such bound available.
+A SAT-solver-based proof <ref>{{cite paper | title = A SAT Attack on the Erdos Discrepancy Conjecture | arxiv = 1402.2184 | first1 = Boris | last1 = Konev | first2 = Alexei | last2 = Lisitsa | date = 17 Feb 2014 }}</ref> has shown that every sequence of 1161 or more elements satisfies the conjecture in the special case ''C''&nbsp;=&nbsp;2: this constitutes a proof of the conjecture for ''C''&nbsp;≤&nbsp;2. {{Asof|2014|February}}, this is the best such bound available.
-Alexei Lisitsa and Boris Konev of the [[University of Liverpool]], UK, used a computer to solve part of the discrepancy problem. In February 2014, the computer showed that an infinite sequence will always have a discrepancy larger than 2.{{clarify | reason = 'discrepancy' has not been defined. I could guess that this is saying that there always exist k and d such that absolute value of the sum is greater than 2, but it is by no means clearly stated|date=February 2014}} The main issue with the proof is that it takes up 13 [[gigabytes]] of data, which larger than the size of all the text on Wikipedia as of 2014, and so cannot be verified by human mathematicians. However, it may not be necessary to have a human check the proof. If a different computer-based method is used and returns the same results then the proof is likely to be correct.<ref>{{cite web|url=http://www.newscientist.com/article/dn25068-wikipediasize-maths-proof-too-big-for-humans-to-check.html#.UwQcNfldVv9|title=Wikipedia-size maths proof too big for humans to check|author=Jacob Aron|publisher=New Scientist|date=February 17, 2014|accessdate=February 18, 2014}}</ref>
+Alexei Lisitsa and Boris Konev of the [[University of Liverpool]], UK, used a computer to solve part of the discrepancy problem. In February 2014, the computer showed that an infinite sequence will always have a discrepancy larger than 2.{{clarify | reason = 'discrepancy' has not been defined. I could guess that this is saying that there always exist k and d such that absolute value of the sum is greater than 2, but it is by no means clearly stated|date=February 2014}} The main issue with the proof is that it takes up 13 [[gigabytes]] of data, which larger than the size of all the text on Wikipedia as of 2014, and so cannot be verified by human mathematicians. However, it may not be necessary to have a human check the proof. If a different computer-based method is used and returns the same results then the proof is likely to be correct.<ref>{{cite web|url=http://www.newscientist.com/article/dn25068-wikipediasize-maths-proof-too-big-for-humans-to-check.html|title=Wikipedia-size maths proof too big for humans to check|first = Jacob | last = Aron|publisher=[[New Scientist]]|date=February 17, 2014|accessdate=February 18, 2014}}</ref>
 ==Barker codes==