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

Последовательность чисел, состоящая из 1 и -1

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

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

Проблема расхождения Эрдёша

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

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

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

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

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

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

Коды Баркера

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

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

такой что

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

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

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

Смотрите также

• Двоичная последовательность
• Несоответствие гиперграфов
• Последовательность Рудина–Шапиро

Примечания

1. Конев, Борис; Лисица, Алексей (2014). «Атака SAT на гипотезу о расхождении Эрдёша». В Sinz, Карстен; Эгли, Уве (ред.). Теория и применение тестирования выполнимости – SAT 2014 – 17-я международная конференция, проходившая в рамках Венского лета логики, VSL 2014, Вена, Австрия, 14–17 июля 2014 г., Труды . Конспект лекций по информатике. Том 8561. Springer. стр. 219–226. arXiv : 1402.2184 . doi :10.1007/978-3-319-09284-3_17.
2. Арон, Джейкоб (17 февраля 2014 г.). «Математическое доказательство размером с Википедию слишком велико для проверки людьми». New Scientist . Получено 18 февраля 2014 г.
3. Известная математическая задача решена благодаря краудсорсингу. USA Today 28 сентября 2015 г.
4. Джейкоб Арон, Толпы победили компьютеры в решении математической задачи размером с Википедию, New Scientist , 30 сентября 2015 г., получено 21.10.2015 г.
5. Тао, Теренс (2016). «Проблема несоответствия Эрдеша». Дискретный анализ : 1–29. arXiv : 1509.05363 . дои : 10.19086/da.609. ISSN  2397-3129. МР  3533300. S2CID  59361755.
6. Ли, Вэньтянь; Танос, Димитриос; Провата, Астеро (14.01.2019). «Количественная оценка локальной случайности в последовательностях ДНК и РНК человека с использованием мотивов Эрдёша». Журнал теоретической биологии . 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. Баркер, Р. Х. (1953). «Групповая синхронизация двоичных цифровых последовательностей». Теория связи . Лондон: Баттерворт. С. 273–287.

Ссылки

• Шазелл, Бернард (2000-07-24). Метод расхождения: случайность и сложность . Cambridge University Press. ISBN 0-521-77093-9.

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

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