Teckensekvens

I matematik är en teckensekvens , eller ±1–sekvens eller bipolär sekvens , en sekvens av tal, som var och en är antingen 1 eller −1. Ett exempel är sekvensen (1, −1, 1, −1, ...).

Sådana sekvenser studeras vanligen inom diskrepansteorin .

Erdős diskrepansproblem

antog matematikern Paul Erdős att för alla oändliga ±1-sekvenser $(x_{1},x_{2},\ldots )$ och vilket heltal C som helst , det finns heltal k och d så att

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

Problemet med Erdős diskrepans kräver ett bevis eller motbevis för denna gissning.

I februari 2014 visade Alexei Lisitsa och Boris Konev från University of Liverpool att varje sekvens av 1161 eller fler element uppfyller gissningarna i specialfallet C = 2, vilket bevisar gissningen för C ≤ 2. Detta var den bästa sådan bunden som fanns tillgänglig just då. Deras bevis förlitade sig på en SAT-lösare datoralgoritm vars utdata tar upp 13 gigabyte data, mer än hela Wikipedias text vid den tiden, så det kan inte verifieras oberoende av mänskliga matematiker utan ytterligare användning av en dator.

I september 2015 tillkännagav Terence Tao ett bevis på gissningen, baserad på arbete som utfördes 2010 under Polymath5 (en form av crowdsourcing tillämpad på matematik) och ett förslag från den tyske matematikern Uwe Stroinski på Taos blogg. Hans bevis publicerades 2016, som den första artikeln i den nya tidskriften Discrete Analysis .

Erdős diskrepans av ändliga sekvenser har föreslagits som ett mått på lokal slumpmässighet i DNA- sekvenser. Detta är baserat på det faktum att i fallet med ändliga sekvenser är diskrepansen begränsad, och därför kan man bestämma de finita sekvenserna med en diskrepans som är mindre än ett visst värde. Dessa sekvenser kommer också att vara de som "undviker" vissa periodiciteter. Genom att jämföra den förväntade kontra observerade fördelningen i DNA eller använda andra korrelationsmått kan man dra slutsatser relaterade till DNA-sekvensernas lokala beteende.