Barisan tanda

Dalam matematika, sebuah barisan tanda, atau barisan–1± atau barisan bipolar, adalah sebuah barisan bilangan, setiap yang baik $1$ atau $-1$. Salah satu contohnya adalah barisan $(1,-1,1-,1,\dots )$.

Seperti barisan biasanya dipelajari dalam teori ketakcocokan..

Masalah ketakcocokan Erdős

Sekitar tahun 1932, matematikawan bernama Paul Erdős menduga bahwa untuk suatu barisan–1± $\langle x_{1},x_{2},\dots \rangle$ dan suatu 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 menanyakn untuk sebuah pembuktian atau penyangkalan mengenai konjektur/dugaan ini.

Pada bulan Februari 2014, Alexei Lisitsa dan Boris Konev dari Universitas Liverpool menunjukkan bahwa setiap barisan dari 1161 unsur atau lebih memenuhi konjektur dalam kasus khusus $C=2$, yang membuktikan konjektur/dugaan untuk $C\leq 2$. Ini adalah batas terbaik yang tersedia pada saat itu. Buktinya diandalkan sebuah algoritme komputer SAT-solver yang keluarannya dibutuhkan 13 gigabit data, lebih dari seluruh teks Wikipedia pada waktu tertentu, jadi ini tidak dapat menjadi sah secara independen oleh para matematikawan tanpa penggunaan lebih lanjut mengenai sebuah komputer.

Pada bulan September 2015, Terence Tao mengumumkan sebuah bukti dari konjektur/dugaan, membangun pada pekerjaan yang dilakukan pada tahun 2010 dikarenakan Polymath5 (sebuah bentuk urun daya berlaku dengan matematika) dan sebuah saran dibuat oleh matematikawan Jerman bernama Uwe Stroinski pada blog Tao. Buktinya diterbitkan pada tahun 2016, sebagai makalah dalam jurnal baru Discrete Analysis.

Ketakcocokan Erdős mengenai barisan hingga telah diusulkan sebagai sebuah ukuran keacakan lokal dalam pengurutan DNA. Ini berdasarkan fakta dalam kasus mengenai ketakcocokan barisan panjang-hingga adalah terbatas, dan oleh karena itu salah satunya dapat menentukan barisan hingga dengan ketakcocokan lebih kecil dari sebuah nilai tertentu. Barisan itu akan menjadi itu yang "menghindari" keberkalaan tertentu. Dengan membandingkan yang terduga melawan sebaran teramati dalam DNA atau menggunakan ukuran korelas lainnya, salah satunya membuat kesimpulan berkaitan dengan perilaku lokal mengenai pengurutan DNA.

Kode Barker

Sebuah 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|\leq 1$

untuk semua $1\leq v<N$.

Kode Barker mengenai panjang 11 dan 13 digunakan dalam spektrum menyebar barisan langsung dan sistem radar pemampatan denyut karena sifat autokorelasinya yang lemah.

Lihat pula

• Barisan biner
• Ketakcocokan hipergrafik
• Barisan Rudin–Shapiro

Referensi

• Chazelle, Bernard (2000-07-24). The Discrepancy Method: Randomness and Complexity. Cambridge University Press. ISBN 0-521-77093-9. 

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)