Последовательность знаков - Sign sequence - Wikipedia

Эта статья о знаковых последовательностях в математике. Последовательность придорожных знаков см. Бирма-Бритье.

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

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

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

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

${\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 году как первая статья в новом журнале. Дискретный анализ.^[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}$

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

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

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

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

Примечания

1. Конев, Борис; Лисица, Алексей (17 фев 2014). «Атака SAT на гипотезу несоответствия Эрдоша». arXiv:1402.2184. Bibcode:2014arXiv1402.2184K.
2. Арон, Джейкоб (17 февраля 2014 г.). «Математическое доказательство размером с Википедию слишком велико для проверки людьми». Новый ученый. Получено 18 февраля, 2014.
3. Знаменитая математическая задача решена благодаря краудсорсингу. USA Today 28 сентября 2015 г.
4. Джейкоб Арон, Толпа побеждает компьютеры в решении математической задачи размером с Википедию, Новый ученый, 30 сен 15, дата обращения 21.10.2015
5. Тао, Теренс (2016). «Проблема несоответствия Эрдеша». Дискретный анализ: 1–29. arXiv:1509.05363. Дои:10.19086 / da.609. ISSN  2397-3129. МИСТЕР  3533300.
6. Ли, Вентянь; Танос, Димитриос; Провата, Астеро (14 января 2019). «Количественная оценка локальной случайности в последовательностях ДНК и РНК человека с использованием мотивов Эрдеша». Журнал теоретической биологии. 461: 41–50. arXiv:1805.10248. Дои:10.1016 / j.jtbi.2018.09.031. ISSN  0022-5193. PMID  30336158.
7. Баркер, Р. Х. (1953). «Групповая синхронизация двоичных цифровых последовательностей». Теория коммуникации. Лондон: Баттерворт. С. 273–287.

Рекомендации

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

внешняя ссылка

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