부호순서

수학에서, 부호 수열 또는 ±1-수열 또는 쌍극 수열은 각각 1 또는 -1인 수열이다.예를 들어 시퀀스(1, -1, 1, -1 ...)가 있습니다.

그러한 순서는 불일치 이론에서 흔히 연구된다.

Erd의 불일치 문제

1932년경 수학자 Paul Erd's는 무한 ±${\displaystyle {}_{}}{\displaystyle {}_{}{}_{}{x\mathrm{}}_{}}$1, x 2,${\displaystyle }$…$$δ (\$displaystyle \textstyle \langle x_{1},x_{$2},\ldots \$rangle }$ 및$$ 정수 C에 대해 k와 d가 존재한다고 추측했다.

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

Erd의 불일치 문제는 이 추측의 증명 또는 반증을 요구합니다.

2014년 2월, 리버풀 대학의 알렉세이 리시사와 보리스 코네브는 1161개 이상의 원소의 모든 시퀀스가 특수 케이스 C = 2의 추측을 충족한다는 것을 보여주었고, 이는 C 2 ^[1]2에 대한 추측을 증명한다.이것은 그 당시 이용 가능한 가장 좋은 제본이었다.그들의 증명은 당시 위키피디아 전체 텍스트보다 많은 13기가바이트의 데이터를 차지하는 SAT 해결사 컴퓨터 알고리즘에 의존했다. 그래서 컴퓨터를 ^[2]더 사용하지 않고는 인간 수학자들에 의해 독립적으로 검증될 수 없다.

2015년 9월 Terence Tao는 2010년 Polymath5(수학에 적용되는 크라우드 소싱의 일종) 기간 동안 수행된 작업과 독일 수학자 Uwe Stroinski가 ^[3][4]Tao의 블로그에서 제안한 내용을 바탕으로 추측의 증거를 발표했습니다.그의 증거는 2016년에 새로운 저널 Discrete ^[5]Analysis에 첫 번째 논문으로 발표되었습니다.

Erd의 유한 시퀀스의 불일치는 DNA ^[6]시퀀스의 로컬 랜덤성 측정으로 제안되었습니다.이는 유한 길이 시퀀스의 불일치가 경계가 되어 있기 때문에 일정 값 미만의 불일치를 갖는 유한 시퀀스를 결정할 수 있다는 사실에 기초한다.이러한 시퀀스들은 또한 특정 주기성을 "회피"하는 시퀀스들이 될 것이다.DNA에서 예상되는 분포와 관찰된 분포를 비교하거나 다른 상관측정을 사용함으로써 DNA 배열의 국소적 거동에 관한 결론을 내릴 수 있다.

바커 코드

바커 코드는 +1과 -1의 N개 값의 시퀀스입니다.

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

그렇게 해서

${\displaystyle \left \sum _{j=1}^{N-v}x_{j}x_{j+v}\right \leq 1}$

모든 <N \ $display 1$\ $leq v$ < N^[7]>에 대해 지정합니다.

길이 11과 13의 바커 코드는 자기 상관 특성이 낮기 때문에 직접 시퀀스 확산 스펙트럼 및 펄스 압축 레이더 시스템에 사용된다.

「 」를 참조해 주세요.

• 이진수열
• 하이퍼그래프의 불일치
• 루딘-샤피로 수열

메모들

레퍼런스

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

외부 링크

• Erd의 불일치 문제– Polymath 프로젝트
• 컴퓨터가 Erd의 퍼즐을 풀지만 인간의 두뇌는 답을 확인할 수 없다.: 인디펜던트 (2014년 2월 21일 금요일)