secuencia de signos

En matemáticas , una secuencia de signos , o secuencia ±1 o secuencia bipolar , es una secuencia de números, cada uno de los cuales es 1 o −1. Un ejemplo es la secuencia (1, −1, 1, −1, ...).

Este tipo de secuencias se estudian habitualmente en la teoría de la discrepancia .

Alrededor de 1932, el matemático Paul Erdős conjeturó que para cualquier secuencia infinita de ±1${\displaystyle (x_{1},x_{2},\ldots )}$y cualquier entero C , existen enteros k y d tales que

${\displaystyle \left|\sum _{i=1}^{k}x_{i\cdot d}\right|>C.}$

El problema de la discrepancia de Erdős exige una demostración o refutación de esta conjetura.

En febrero de 2014, Alexei Lisitsa y Boris Konev, de la Universidad de Liverpool, demostraron que toda secuencia de 1161 o más elementos satisface la conjetura en el caso especial C  =  2, lo que prueba la conjetura para C  ≤  2. ^{[ 1 ]} Esta fue la mejor cota disponible hasta el momento. Su prueba se basó en un algoritmo informático de resolución SAT cuya salida ocupa 13 gigabytes de datos, más que el texto completo de Wikipedia en ese momento, por lo que no puede ser verificada de forma independiente por matemáticos humanos sin el uso adicional de una computadora. ^{[ 2 ]}

En septiembre de 2015, Terence Tao anunció una demostración de la conjetura, basándose en el trabajo realizado en 2010 durante Polymath5 (una forma de colaboración colectiva aplicada a las matemáticas) y en una sugerencia del matemático alemán Uwe Stroinski en el blog de Tao. ^{[ 3 ] [ 4 ]} Su demostración se publicó en 2016 como el primer artículo de la nueva revista Discrete Analysis . ^{[ 5 ]}

La discrepancia de Erdős en secuencias finitas se ha propuesto como una medida de aleatoriedad local en secuencias de ADN . ^{[ 6 ]} Esto se basa en el hecho de que, en el caso de secuencias de longitud finita, la discrepancia está acotada y, por lo tanto, se pueden determinar las secuencias finitas con una discrepancia menor que un cierto valor. Dichas secuencias también serán aquellas que "evitan" ciertas periodicidades. Al comparar la distribución esperada con la observada en el ADN o al utilizar otras medidas de correlación, se pueden extraer conclusiones relacionadas con el comportamiento local de las secuencias de ADN.

Un código Barker es una secuencia de N valores de +1 y − 1,

${\displaystyle x_{j}{\text{ para }}j=1,\ldots ,N,}$

de tal manera que

${\displaystyle \left|\sum _{j=1}^{Nv}x_{j}x_{j+v}\right|\leq 1}$

a pesar de${\displaystyle 1\leq v<N}$. ^{[ 7 ]}

Los códigos Barker de longitudes 11 y 13 se utilizan en sistemas de radar de espectro ensanchado de secuencia directa y de compresión de pulsos debido a sus bajas propiedades de autocorrelación .

• Secuencia binaria
• Discrepancia de hipergrafos
• Secuencia de Rudin-Shapiro

• Chazelle, Bernard (24 de julio de 2000). El método de la discrepancia: aleatoriedad y complejidad . Cambridge University Press. ISBN 0-521-77093-9.

• El problema de la discrepancia de Erdős – Polymath Project
• Un ordenador resuelve el enigma de Erdős, pero ningún cerebro humano puede comprobar la respuesta — The Independent (viernes, 21 de febrero de 2014)