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

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

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

• 1 Проблема несоответствия Эрдеша
• 2 Коды Баркера
• 3 См. Также
• 4 Примечания
• 5 Ссылки
• 6 Внешние ссылки

Примерно в 1932 году математик Пол Эрдёш предположил, что для любой бесконечной ± 1-последовательности $⟨x\; 1,\; x\; 2,\dots \; ⟩\; \{\backslash \; Displaystyle\; \backslash \; textstyle\; \backslash \; langle\; x\_\; \{1\},\; x\_\; \{2\},\; \backslash \; ldots\; \backslash \; rangle\}$и любое целое число C, существуют целые числа k и d такие, что

$|\; \sum \; я\; знак\; равно\; 1\; К\; Икс\; я\; \cdot \; г\; |>С.\; \{\backslash \; displaystyle\; \backslash \; left\; |\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{k\}\; x\_\; \{i\; \backslash \; cdot\; d\}\; \backslash \; right\; |>C.\}$

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

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

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

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

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

$xj\; для\; j\; =\; 1,\dots ,\; N\; \{\backslash \; displaystyle\; x\_\; \{j\}\; \{\backslash \; текст\; \{for\}\}\; j\; =\; 1,\; \backslash \; ldots,\; N\}$

такой, что

$|\; \sum \; j\; =\; 1\; N\; -\; v\; x\; j\; x\; j\; +\; v\; |\; \le \; 1\; \{\backslash \; displaystyle\; \backslash \; left\; |\; \backslash \; sum\; \_\; \{j\; =\; 1\}\; ^\; \{Nv\}\; x\_\; \{j\}\; x\_\; \{j\; +\; v\}\; \backslash \; right\; |\; \backslash \; leq\; 1\}$

для всех .

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

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

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

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