サインシーケンス

数学において、符号列、または±1-列、双極性列とは、各要素が1または-1である数列のことです。例として、数列(1, -1, 1, -1, ...)が挙げられます。

このような数列は、不一致理論において一般的に研究されている。

1932年頃、数学者のポール・エルデシュは、任意の無限±1列に対して、${\displaystyle (x_{1},x_{2},\ldots )}$また、任意の整数Cに対して、整数kとdが存在し、

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

エルデシュの矛盾問題は、この予想の証明または反証を求めるものである。

2014年2月、リバプール大学のアレクセイ・リシツァとボリス・コネフは、1161個以上の要素からなる任意の数列が、 C  = 2 の特殊な場合において予想を満たすことを示し、 C ≤ 2 の場合の予想を証明した。^{[ 1 ]}これは当時入手可能な最良の境界であった。彼らの証明は、出力が13ギガバイトのデータを占めるSATソルバーのコンピュータアルゴリズムに依存しており、これは当時のウィキペディアの全テキストよりも大きいため、コンピュータをさらに使用せずに人間の数学者が独立して検証することはできない。^{[ 2 ]}  

2015 年 9 月、テレンス・タオは、2010 年にPolymath5 (数学に適用されたクラウドソーシングの一種) で行われた作業と、タオのブログでドイツの数学者ウーヴェ・ストロインスキーが提案したことを基に、予想の証明を発表した。^{[ 3 ] [ 4 ]}彼の証明は、新しいジャーナルDiscrete Analysisの最初の論文として 2016 年に発表された。^{[ 5 ]}

有限配列のエルデシュ不一致は、 DNA配列の局所的なランダム性の尺度として提案されている。^{[ 6 ]}これは、有限長の配列の場合、不一致は有界であり、したがって、ある値よりも不一致が小さい有限配列を決定できるという事実に基づいている。これらの配列は、特定の周期性を「回避」するものでもある。DNAにおける期待分布と観測分布を比較したり、他の相関尺度を使用したりすることで、DNA配列の局所的な挙動に関する結論を導き出すことができる。

バーカーコードは、 +1 と −1 の N 個の値のシーケンスです。

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

そのため

$\left|\sum _{j=1}^{Nv}x_{j}x_{j+v}\right|\leq 1}$

すべての人々のために${\displaystyle 1\leq v<N}$[ ^{7 ]​}

自己相関が低いという特性から、長さ11および13のバーカー符号は、直接拡散スペクトラムレーダー およびパルス圧縮レーダーシステムで使用される。

• 二進数列
• ハイパーグラフの不一致
• ルディン-シャピロシーケンス

• シャゼル、バーナード（2000年7月24日）。『不一致法：ランダム性と複雑性』ケンブリッジ大学出版局。ISBN 0-521-77093-9。

• エルデシュの不一致問題– Polymath プロジェクト
• コンピューターがエルデシュのパズルを解いたが、人間の脳ではその答えを検証できない―インディペンデント紙（2014年2月21日金曜日）