Secuencia de signos

Secuencia de números que consta de 1 y -1

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, ...).

Estas secuencias se estudian comúnmente en la teoría de la discrepancia .

Problema de discrepancia de Erdős

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

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

El problema de discrepancia de Erdős pide una prueba 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] Este era el mejor límite de este tipo disponible en ese momento. Su prueba se basó en un algoritmo informático de resolución SAT cuyo resultado ocupa 13 gigabytes de datos, más que todo el texto de Wikipedia en ese momento, por lo que no puede ser verificado independientemente por matemáticos humanos sin el uso posterior de una computadora. ^[2]

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

La discrepancia de Erdős de 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á limitada y, por lo tanto, se pueden determinar las secuencias finitas con discrepancia menor a un cierto valor. Esas secuencias también serán aquellas que "eviten" ciertas periodicidades. Al comparar la distribución esperada con la observada en el ADN o utilizando otras medidas de correlación, se pueden sacar conclusiones relacionadas con el comportamiento local de las secuencias de ADN.

Códigos de Barker

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

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

de tal manera que

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

para todos . ^[7] ${\displaystyle 1\leq v<N}$

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

Véase también

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

Notas

1. Konev, Boris; Lisitsa, Alexei (2014). "Un ataque SAT a la conjetura de discrepancia de Erdős". En Sinz, Carsten; Egly, Uwe (eds.). Teoría y aplicaciones de las pruebas de satisfacibilidad – SAT 2014 – 17.ª conferencia internacional, celebrada como parte del Vienna Summer of Logic, VSL 2014, Viena, Austria, del 14 al 17 de julio de 2014, Actas . Apuntes de clase en informática. Vol. 8561. Springer. págs. 219–226. arXiv : 1402.2184 . doi :10.1007/978-3-319-09284-3_17.
2. Aron, Jacob (17 de febrero de 2014). «La prueba matemática del tamaño de Wikipedia es demasiado grande para que los humanos la comprueben». New Scientist . Consultado el 18 de febrero de 2014 .
3. Famoso problema matemático resuelto gracias al crowdsourcing. USA Today , 28 de septiembre de 2015
4. Jacob Aron, Las multitudes superan a las computadoras en la respuesta a un problema matemático del tamaño de Wikipedia, New Scientist , 30 de septiembre de 2015, consultado el 21 de octubre de 2015
5. Tao, Terence (2016). "El problema de la discrepancia de Erdős". Análisis discreto : 1–29. arXiv : 1509.05363 . doi :10.19086/da.609. ISSN  2397-3129. SEÑOR  3533300. S2CID  59361755.
6. Li, Wentian; Thanos, Dimitrios; Provata, Astero (14 de enero de 2019). "Cuantificación de la aleatoriedad local en secuencias de ADN y ARN humanas utilizando motivos de Erdös". Journal of Theoretical Biology . 461 : 41–50. arXiv : 1805.10248 . Código Bibliográfico :2019JThBi.461...41L. doi :10.1016/j.jtbi.2018.09.031. ISSN  0022-5193. PMID  30336158. S2CID  52901027.
7. Barker, RH (1953). "Sincronización grupal de secuencias digitales binarias". Teoría de la comunicación . Londres: Butterworth. págs. 273–287.

Referencias

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

Enlaces externos

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