Последовательность знаков

В математике последовательность знаков , или ±1-последовательность или биполярная последовательность , представляет собой последовательность чисел, каждое из которых равно 1 или -1. Одним из примеров является последовательность (1, −1, 1, −1, ...).

Такие последовательности обычно изучаются в теории несоответствий .

Проблема несоответствия лесов

Примерно в 1932 году математик Пауль Эрдеш предположил , что для любой бесконечной ±1-последовательности $(x_{1},x_{2},\ldots )$ и любого целого числа C существуют целые числа k и d такие, что

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

Проблема несоответствия Эрдеша требует доказательства или опровержения этой гипотезы.

В феврале 2014 года Алексей Лисица и Борис Конев из Ливерпульского университета показали, что каждая последовательность из 1161 или более элементов удовлетворяет гипотезе в специальном случае C = 2, что доказывает гипотезу для C ≤ 2. ^{[ 1 ]} Это был лучший такой переплет, доступный на тот момент. Их доказательство основывалось на компьютерном алгоритме SAT-solver, выходные данные которого занимают 13 гигабайт данных, что больше, чем весь текст Википедии на тот момент, поэтому математики-люди не могут его независимо проверить без дальнейшего использования компьютера. ^{[ 2 ]}

В сентябре 2015 года Теренс Тао объявил о доказательстве гипотезы, основываясь на работе, проделанной в 2010 году во время Polymath5 (форма краудсорсинга в применении к математике), и на предложении, сделанном немецким математиком Уве Строински в блоге Тао. ^{[ 3 ]}^{[ 4 ]} Его доказательство было опубликовано в 2016 году как первая статья в новом журнале Discrete Analysis . ^{[ 5 ]}

Расхождение Эрдеша конечных последовательностей было предложено как мера локальной случайности в последовательностях ДНК . ^{[ 6 ]} Это основано на том, что в случае последовательностей конечной длины невязка ограничена, и поэтому можно определить конечные последовательности с невязкой меньше определенного значения. Эти последовательности также будут теми, которые «избегают» определенных периодичностей. Сравнивая ожидаемое и наблюдаемое распределение в ДНК или используя другие меры корреляции, можно сделать выводы, связанные с локальным поведением последовательностей ДНК.

Коды Баркера

Код Баркера представляет собой последовательность N значений +1 и -1,

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

такой, что

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

для всех $1\leq v<N$ . ^{[ 7 ]}

Коды Баркера длиной 11 и 13 используются в радиолокационных системах с расширением спектра прямой последовательностью и сжатием импульсов из-за их низких автокорреляционных свойств.

См. также

Примечания

^ Конев, Борис; Лисица, Алексей (2014). «Атака SAT на гипотезу о несоответствии Эрдеша». В Синце, Карстен; Эгли, Уве (ред.). Теория и приложения тестирования выполнимости – SAT 2014 – 17-я Международная конференция, проходившая в рамках Венского лета логики, VSL 2014, Вена, Австрия, 14–17 июля 2014 г., Труды . Конспекты лекций по информатике. Том. 8561. Спрингер. стр. 219–226. arXiv : 1402.2184 . дои : 10.1007/978-3-319-09284-3_17 .
^ Арон, Джейкоб (17 февраля 2014 г.). «Математические доказательства размером с Википедию слишком сложны, чтобы люди могли их проверить» . Новый учёный . Проверено 18 февраля 2014 г.
^ Знаменитая математическая задача решена благодаря краудсорсингу . USA Today , 28 сентября 2015 г.
↑ Джейкоб Арон, Толпы победили компьютеры в ответ на математическую задачу размером с Википедию , New Scientist , 30 сентября 15, дата обращения 21 октября 2015 г.
^ Тао, Теренс (2016). «Проблема несоответствия Эрдеша». Дискретный анализ : 1–29. arXiv : 1509.05363 . дои : 10.19086/da.609 . ISSN 2397-3129 . МР 3533300 . S2CID 59361755 .
^ Ли, Вэньтянь; Танос, Димитриос; Провата, Астеро (14 января 2019 г.). «Количественная оценка локальной случайности в последовательностях ДНК и РНК человека с использованием мотивов Эрдеша». Журнал теоретической биологии . 461 : 41–50. arXiv : 1805.10248 . Бибкод : 2019JThBi.461...41L . дои : 10.1016/j.jtbi.2018.09.031 . ISSN 0022-5193 . ПМИД 30336158 . S2CID 52901027 .
^ Баркер, Р.Х. (1953). «Групповая синхронизация двоичных цифровых последовательностей». Теория коммуникации . Лондон: Баттерворт. стр. 273–287.

Ссылки

Шазель, Бернар (24 июля 2000 г.). Метод несоответствия: случайность и сложность . Издательство Кембриджского университета. ISBN 0-521-77093-9 .

Внешние ссылки

Проблема несоответствия Эрдёша - Проект Polymath
Компьютер разгадал загадку Эрдеша, но ни один человеческий мозг не может проверить ответ — The Independent (пятница, 21 февраля 2014 г.)

[1] Конев, Борис; Лисица, Алексей (2014). «Атака SAT на гипотезу о несоответствии Эрдеша». В Синце, Карстен; Эгли, Уве (ред.). Теория и приложения тестирования выполнимости – SAT 2014 – 17-я Международная конференция, проходившая в рамках Венского лета логики, VSL 2014, Вена, Австрия, 14–17 июля 2014 г., Труды . Конспекты лекций по информатике. Том. 8561. Спрингер. стр. 219–226. arXiv : 1402.2184 . дои : 10.1007/978-3-319-09284-3_17 .

[2] Арон, Джейкоб (17 февраля 2014 г.). «Математические доказательства размером с Википедию слишком сложны, чтобы люди могли их проверить» . Новый учёный . Проверено 18 февраля 2014 г.

[3] Знаменитая математическая задача решена благодаря краудсорсингу . USA Today , 28 сентября 2015 г.

[4] Джейкоб Арон, Толпы победили компьютеры в ответ на математическую задачу размером с Википедию , New Scientist , 30 сентября 15, дата обращения 21 октября 2015 г.

[5] Тао, Теренс (2016). «Проблема несоответствия Эрдеша». Дискретный анализ : 1–29. arXiv : 1509.05363 . дои : 10.19086/da.609 . ISSN 2397-3129 . МР 3533300 . S2CID 59361755 .

[6] Ли, Вэньтянь; Танос, Димитриос; Провата, Астеро (14 января 2019 г.). «Количественная оценка локальной случайности в последовательностях ДНК и РНК человека с использованием мотивов Эрдеша». Журнал теоретической биологии . 461 : 41–50. arXiv : 1805.10248 . Бибкод : 2019JThBi.461...41L . дои : 10.1016/j.jtbi.2018.09.031 . ISSN 0022-5193 . ПМИД 30336158 . S2CID 52901027 .

[7] Баркер, Р.Х. (1953). «Групповая синхронизация двоичных цифровых последовательностей». Теория коммуникации . Лондон: Баттерворт. стр. 273–287.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]