Barisan tanda

Dalam matematika, sebuah barisan tanda, atau barisan–1± atau barisan bipolar, adalah sebuah barisan bilangan yang terdiri dari 1 {\displaystyle 1} $1$ atau − 1 {\displaystyle -1} $-1$ . Contohnya seperti barisan ( 1 , − 1 , 1 , − 1 , … ) {\displaystyle (1,-1,1,-1,\dots )} $(1,-1,1,-1,\dots )$ . Biasanya, barisan tersebut dipelajari dalam teori ketakcocokan.

Masalah ketakcocokan Erdős

Sekitar tahun 1932, matematikawan bernama Paul Erdős menduga bahwa untuk setiap barisan–1± ⟨ x 1 , x 2 , … ⟩ {\displaystyle \langle x_{1},x_{2},\dots \rangle } $\langle x_{1},x_{2},\dots \rangle$ dan setiap bilangan bulat C {\displaystyle C} $C$ , terdapat bilangan bulat k {\displaystyle k} $k$ dan d {\displaystyle d} $d$ sehingga

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

Masalah ketakcocokan Erdős meminta untuk membuktikan atau menyangkal konjektur tersebut.

Pada bulan Februari 2014, Alexei Lisitsa dan Boris Konev dari Universitas Liverpool memperlihatkan bahwa setiap barisan dari 1161 anggota atau lebih memenuhi konjektur dalam kasus khusus C = 2 {\displaystyle C=2} $C=2$ , yang membuktikan konjektur untuk C ≤ 2 {\displaystyle C\leq 2} $C\leq 2$ ,^[1] sebuah batas terbaik yang ditemukan pada saat itu. Bukti tersebut mengandalkan sebuah algoritme komputer SAT-solver, dengan output yang dibutuhkan adalah 13 gigabit data, lebih dari jumlah bit dari seluruh teks Wikipedia saat itu. Karena itu, banyak matematikawan tidak memvalidkan bukti tersebut tanpa ada pemakaian komputer lebih lanjut.^[2]

Pada bulan September 2015, Terence Tao mengumumkan sebuah bukti dari konjektur tersebut. Pembuktian tersebut dilakukan pada tahun 2010 dengan memakai Polymath5, sebuah bentuk urun daya yang berlaku untuk matematika, serta mengikuti saran dari seorang matematikawan berkebangsaan Jerman bernama Uwe Stroinski di sebuah blog milik Tao.^[3]^[4] Bukti Tao diterbitkan pada tahun 2016, sebagai makalah pertama dalam jurnal baru Discrete Analysis.^[5]

Ketakcocokan Erdős dari barisan terhingga diusulkan sebagai ukuran keacakan lokal dalam pengurutan DNA.^[6] Hal ini berdasarkan fakta bahwa barisan panjang terhingga dalam kasus ketakcocokan adalah terbatas, dan sebab itu seseorang dapat menentukan barisan terhingga dengan ketakcocokan lebih kecil dari sebuah nilai tertentu. Barisan tersebut akan "menghindari" periodisitas. Ketika membandingkan distribusi yang diduga dengan distribusi yang diamati di dalam DNA atau menggunakan ukuran korelasi yang lain, maka seseorang dapat menyimpulkan terkait dengan perilaku lokal pengurutan DNA.

Kode Barker

Kode Barker adalah sebuah barisan nilai N {\displaystyle N} $N$ dari + 1 {\displaystyle +1} $+1$ dan − 1 {\displaystyle -1} $-1$ ,

x j {\displaystyle x_{j}} $x_{j}$ untuk j = 1 , … , N {\displaystyle j=1,\dots ,N} $j=1,\dots ,N$

sehingga

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

untuk semua 1 ≤ v < N {\displaystyle 1\leq v<N} $1\leq v<N$ .^[7]

Kode Barker dari panjang 11 dan 13 digunakan dalam spektrum menyebar barisan langsung dan sistem radar pemampatan denyut, sebab mempunyai sifat autokorelasi yang lemah.

Lihat pula

Catatan

↑ Konev, Boris; Lisitsa, Alexei (17 Feb 2014). "A SAT Attack on the Erdos Discrepancy Conjecture". arXiv:1402.2184. Bibcode:2014arXiv1402.2184K.{{cite journal}}: Kutipan journal memerlukan |journal=Pemeliharaan CS1: Tanggal diterjemahkan otomatis (link)
↑ Aron, Jacob (Februari 17, 2014). "Wikipedia-size maths proof too big for humans to check". New Scientist. Diakses tanggal Februari 18, 2014.{{cite magazine}}: Pemeliharaan CS1: Tanggal diterjemahkan otomatis (link)
↑ Famous math problem solved thanks to crowdsourcing. USA Today Sept. 28, 2015
↑ Jacob Aron, Crowds beat computers in answer to Wikipedia-sized maths problem, New Scientist, 30 Sep 15, retrieved 21.10.2015
↑ Tao, Terence (2016). "The Erdős discrepancy problem". Discrete Analysis: 1–29. arXiv:1509.05363. doi:10.19086/da.609. ISSN 2397-3129. MR 3533300.
↑ Li, Wentian; Thanos, Dimitrios; Provata, Astero (2019-01-14). "Quantifying local randomness in human DNA and RNA sequences using Erdös motifs". Journal of Theoretical Biology. 461: 41–50. arXiv:1805.10248. doi:10.1016/j.jtbi.2018.09.031. ISSN 0022-5193. PMID 30336158.
↑ Barker, R. H. (1953). "Group Synchronizing of Binary Digital Sequences". Communication Theory. London: Butterworth. hlm. 273–287.