Sekvence znamení - Sign sequence - Wikipedia

V matematice, a posloupnost znakůnebo ± 1 – sekvence nebo bipolární sekvence, je sekvence čísel, z nichž každé je buď 1 nebo -1. Jedním příkladem je posloupnost (1, −1, 1, −1 ...).

Takové sekvence jsou běžně studovány v teorie nesrovnalostí.

Erdőův problém s nesrovnalostmi

Kolem roku 1932, matematik Paul Erdős domníval se, že pro jakoukoli nekonečnou ± 1 sekvenci ${ displaystyle textstyle langle x_ {1}, x_ {2}, ldots rangle}$ a jakékoli celé číslo C, existují celá čísla k a d takhle

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

Erdőův problém s nesrovnalostí vyžaduje důkaz nebo vyvrácení této domněnky.

V únoru 2014 Alexej Lisitsa a Boris Konev z University of Liverpool ukázal, že každá posloupnost 1161 nebo více prvků splňuje domněnku ve zvláštním případě C = 2, což dokazuje domněnku pro C ≤ 2.^[1] To byla v té době ta nejlepší vazba, která byla k dispozici. Jejich důkaz se opíral o a SAT-řešič počítačový algoritmus, jehož výstup zabírá 13 gigabajty dat, více než celý text Wikipedie v té době, takže to nelze nezávisle ověřit lidskými matematiky bez dalšího použití počítače.^[2]

V září 2015 Terence Tao oznámil důkaz domněnky, navazující na práci provedenou v roce 2010 během roku 2006 Polymath5 (forma crowdsourcing aplikovaný na matematiku) a návrh německého matematika Uwe Stroinského na Taově blogu.^[3][4] Jeho důkaz byl publikován v roce 2016 jako první příspěvek v novém časopise Diskrétní analýza.^[5]

Erdőův nesoulad konečných sekvencí byl navržen jako měřítko lokální náhodnosti v sekvencích DNA.^[6] To je založeno na skutečnosti, že v případě posloupností konečné délky je nesrovnalost omezená, a proto lze určit konečné posloupnosti s nesrovnalostí menší než určitá hodnota. Těmito sekvencemi budou také ty, které se „vyhýbají“ určitým periodicitám. Porovnáním očekávané a pozorované distribuce v DNA nebo použitím jiných korelačních opatření lze vyvodit závěry týkající se místního chování sekvencí DNA.

Barkerovy kódy

A Barkerův kód je posloupnost N hodnoty +1 a -1,

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

takhle

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

pro všechny ${ displaystyle 1 leq v$.^[7]

Kódy Barker o délkách 11 a 13 se používají v rozprostřené spektrum přímé sekvence a pulzní kompresní radar systémy kvůli jejich nízkému autokorelace vlastnosti.

Viz také

• Binární sekvence
• Nesrovnalosti hypergrafů
• Sekvence Rudin – Shapiro

Poznámky

Reference

• Chazelle, Bernard (2000-07-24). Metoda nesrovnalosti: náhodnost a složitost. Cambridge University Press. ISBN  0-521-77093-9.

externí odkazy

• Erdőův problém s nesrovnalostmi - Polymath Project
• Počítač rozluští Erdőovu hádanku - ale žádný lidský mozek nemůže ověřit odpověď —Nezávislý (Pátek 21. února 2014)