Sign sequence: Difference between revisions

Content deleted Content added

Inline

Revision as of 07:15, 18 February 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_{id}\right|>C

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

A SAT-solver-based proof ^[1] has shown that every sequence S 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.

As of October 2010^[update], this problem is currently being studied by the Polymath Project [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$ .^[2]

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], featured in [2]
^ 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

[1] [1], featured in [2]

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

[1]

[2]

@@ Line 6: / Line 6: @@
 <!--{{Further|[[Erdős discrepancy problem]]}}-->
-Around 1932 mathematician [[Paul_Erdős]] conjectured that for any infinite ±1-sequence <math> \langle x_1, x_2, ..\rangle </math> and any integer ''C'' there exist integers ''k'' and ''d'' such that:
+Around 1932 mathematician [[Paul_Erdős]] conjectured that for any infinite ±1-sequence <math>\textstyle\langle x_1, x_2, ..\rangle </math> and any integer ''C'' there exist integers ''k'' and ''d'' such that:
 : <math> \left| \sum_{i=1}^k x_{id} \right| > C </math>
@@ Line 12: / Line 12: @@
 The Erdős Discrepancy Problem asks for a proof or disproof of this conjecture.
-A computer search<ref>[http://arxiv.org/abs/1402.2184], featured in [http://www.newscientist.com/article/dn25068-wikipediasize-maths-proof-too-big-for-humans-to-check.html]</ref> has shown that there could be no such sequence ''S'' achieving the above property for ''C''=2 (and neither, therefore, for ''C'' < 2). {{asof|2014|February}}, this is the best such bound available.
+A SAT-solver-based proof <ref>[http://arxiv.org/pdf/1402.2184v2.pdf], featured in [http://www.newscientist.com/article/dn25068-wikipediasize-maths-proof-too-big-for-humans-to-check.html]</ref> has shown that every sequence ''S'' of 1161 or more elements satisfies the conjecture in the special case ''C''=2: this constitutes a proof of the conjecture for ''C''≤2. {{Asof|2014|February}}, this is the best such bound available.
 {{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].