En matemáticas, una secuencia de signos , o una secuencia ± 1 o una 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
Alrededor de 1932, el matemático Paul Erdős conjeturó que para cualquier secuencia ± 1 infinitay cualquier número entero C , existen enteros k y d tal que
El problema de la discrepancia de Erd 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 cada secuencia de 1161 o más elementos satisface la conjetura en el caso especial C = 2, lo que demuestra la conjetura para C ≤ 2. [1] Esta fue la mejor tal encuadernado disponible en ese momento. Su prueba se basó en un algoritmo informático de resolución SAT cuya salida 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 adicional 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 aplicado 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 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á acotada y, por lo tanto, se pueden determinar las secuencias finitas con una discrepancia menor que cierto valor. Esas secuencias también serán las que "eviten" determinadas periodicidades. Al comparar la distribución esperada con la observada en el ADN o al utilizar 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 de Barker es una secuencia de N valores de +1 y -1,
tal que
para todos . [7]
Los códigos de Barker de longitudes 11 y 13 se utilizan en sistemas de radar de compresión de impulsos y espectro ensanchado de secuencia directa debido a sus bajas propiedades de autocorrelación .
Ver también
Notas
- ^ Konev, Boris; Lisitsa, Alexei (17 de febrero de 2014). "Un ataque del SAT a la conjetura de la discrepancia de Erdos". arXiv : 1402.2184 . Código Bibliográfico : 2014arXiv1402.2184K . Cite journal requiere
|journal=
( ayuda ) - ^ Aron, Jacob (17 de febrero de 2014). "Prueba matemática del tamaño de Wikipedia demasiado grande para que los humanos la revisen" . Nuevo científico . Consultado el 18 de febrero de 2014 .
- ^ Famoso problema matemático resuelto gracias al crowdsourcing . USA Today 28 de septiembre de 2015
- ^ Jacob Aron, Las multitudes vencieron a las computadoras en 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
- ^ Tao, Terence (2016). "El problema de la discrepancia de Erd". Análisis discreto : 1–29. arXiv : 1509.05363 . doi : 10.19086 / da.609 . ISSN 2397-3129 . Señor 3533300 .
- ^ Li, Wentian; Thanos, Dimitrios; Provata, Astero (14 de enero de 2019). "Cuantificación de la aleatoriedad local en secuencias de ADN y ARN humano utilizando motivos Erdös". Revista de Biología Teórica . 461 : 41–50. arXiv : 1805.10248 . doi : 10.1016 / j.jtbi.2018.09.031 . ISSN 0022-5193 . PMID 30336158 .
- ^ 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 . Prensa de la Universidad de Cambridge. ISBN 0-521-77093-9.
enlaces externos
- El problema de la discrepancia de Erd - Polymath Project
- La computadora resuelve el rompecabezas de Erd, pero ningún cerebro humano puede verificar la respuesta - The Independent (viernes 21 de febrero de 2014)