Misplaced Pages

Sign sequence

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Erdős discrepancy problem) Sequence of numbers consisting of 1 and -1 This article is about sign sequences in mathematics. For sequences of roadside signs, see Burma-Shave.

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 ( x 1 , x 2 , … ) {\displaystyle (x_{1},x_{2},\ldots )} and any integer C, there exist integers k and d such that

| ∑ i = 1 k x i ⋅ d | > C . {\displaystyle \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 February 2014, Alexei Lisitsa and Boris Konev of the University of Liverpool 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 relied on an SAT-solver computer algorithm whose output takes up 13 gigabytes of data, more than the entire text of Misplaced Pages at that time, so it cannot be independently verified by human mathematicians without further use of a computer.

In September 2015, Terence Tao announced a proof of the conjecture, building on work done in 2010 during Polymath5 (a form of crowdsourcing applied to mathematics) and a suggestion made by German mathematician Uwe Stroinski on Tao's blog. His proof was published in 2016, as the first paper in the new journal Discrete Analysis.

Erdős discrepancy of finite sequences has been proposed as a measure of local randomness in DNA sequences. This is based on the fact that in the case of finite-length sequences discrepancy is bounded. Therefore one can determine the finite sequences with discrepancy less than a certain value. Those sequences will also be those that "avoid" certain periodicities. By comparing the expected versus observed distribution in the DNA or using other correlation measures, one can make conclusions related to the local behavior of DNA sequences.

Barker codes

Main article: Barker code

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

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

such that

| ∑ j = 1 N − v x j x j + v | ≤ 1 {\displaystyle \left|\sum _{j=1}^{N-v}x_{j}x_{j+v}\right|\leq 1}

for all 1 ≤ v < N {\displaystyle 1\leq v<N} .

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.

See also

Notes

  1. Konev, Boris; Lisitsa, Alexei (2014). "A SAT attack on the Erdős discrepancy conjecture". In Sinz, Carsten; Egly, Uwe (eds.). Theory and Applications of Satisfiability Testing – SAT 2014 – 17th International Conference, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 14–17, 2014, Proceedings. Lecture Notes in Computer Science. Vol. 8561. Springer. pp. 219–226. arXiv:1402.2184. doi:10.1007/978-3-319-09284-3_17.
  2. Aron, Jacob (February 17, 2014). "Misplaced Pages-size maths proof too big for humans to check". New Scientist. Retrieved February 18, 2014.
  3. Famous math problem solved thanks to crowdsourcing. USA Today Sept. 28, 2015
  4. Jacob Aron, Crowds beat computers in answer to Misplaced Pages-sized maths problem, New Scientist, 30 Sep 15, retrieved 21.10.2015
  5. 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. S2CID 59361755.
  6. Li, Wentian; Thanos, Dimitrios; Provata, Astero (2019-01-14). "Quantifying local randomness in human DNA and RNA sequences using Erdös motifs". Journal of Theoretical Biology. 461: 41–50. arXiv:1805.10248. Bibcode:2019JThBi.461...41L. doi:10.1016/j.jtbi.2018.09.031. ISSN 0022-5193. PMID 30336158. S2CID 52901027.
  7. Barker, R. H. (1953). "Group Synchronizing of Binary Digital Sequences". Communication Theory. London: Butterworth. pp. 273–287.

References

External links

Categories: