Barisan tanda

Dalam matematika, sebuah barisan tanda, atau barisan–1± atau barisan bipolar, adalah sebuah barisan bilangan yang terdiri dari $1$ atau $-1$. Contohnya seperti barisan $(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,\dots ⟩$ dan setiap bilangan bulat $C$, terdapat bilangan bulat $k$ dan $d$ sehingga

$\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$, yang membuktikan konjektur untuk $C\le 2$, 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.

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. Bukti Tao diterbitkan pada tahun 2016, sebagai makalah pertama dalam jurnal baru Discrete Analysis.

Ketakcocokan Erdős dari barisan terhingga diusulkan sebagai ukuran keacakan lokal dalam pengurutan DNA. 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$ dari $+1$ dan $-1$,

$x_j$ untuk $j=1,\dots ,N$

sehingga

$\left|\sum _{j=1}^{N-v}{x}_j{x}_{j+v}\right|\le 1$

untuk semua $1\le v<N$.

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

• Barisan biner
• Ketakcocokan hipergraf
• Barisan Rudin–Shapiro

Referensi

• Templat:Cite book

Pranala luar

• The Erdős discrepancy problem – Polymath Project
• Computer cracks Erdős puzzle – but no human brain can check the answer—The Independent (Jumat, 21 Februari 2014)