정수 관계 알고리즘

Integer relation algorithm

실제 숫자 x1, x2, ..., xn 집합 사이의 정수 관계는 다음과 같은 정수 a1, a, ..., a, 모두2n 0이 아니다.

정수 관계 알고리즘은 정수 관계를 찾기 위한 알고리즘이다. 특히, 주어진 정밀도에 알려진 일련의 실수들을 주어진 정수 관계 알고리즘은 그들 사이에 정수 관계를 찾거나, 또는 크기가 특정 상한보다 작은 계수와 정수 관계가 존재하지 않는다고 판단한다.[1]

역사

사례 n = 2의 경우, 유클리드 알고리즘의 확장은 두 개의 실제 숫자 x와1 x2 사이에 존재하는 정수 관계를 찾을 수 있다. 알고리즘은 x1/x의2 지속적인 부분 팽창의 연속적인 항을 생성한다. 만약 숫자 사이에 정수 관계가 있다면, 그 비율은 합리적이고 알고리즘은 결국 종료된다.

  • 퍼거슨-포케이드 알고리즘은 1979년 헬라만 퍼거슨과 R.W.포케이드에 의해 출판되었다.[2] 논문은 n장군을 다루지만, 신뢰할 수 있는 구현에 결정적인 세부 단계와 증거, 정밀도 구속이 결여되어 있어 논문이 문제를 완전히 해결할 수 있는지는 명확하지 않다.
  • 완전한 증거를 가진 최초의 알고리즘은 1982년 아르옌 렌스트라, 헨드릭 렌스트라, 라슬로 로바스츠가 개발한 LLL 알고리즘이었다.[3]
  • HJLS 알고리즘은 1986년 요한 호스타드, 베티나 저스트, 제프리 라고리아스, 클로스-피터 슈노르가 개발했다.[4][5]
  • 1988년에 퍼거슨에 의해 개발된 PSOS 알고리즘.[6]
  • PSLQ 알고리즘은 1992년 퍼거슨과 베일리가 개발하고 1999년 퍼거슨, 베일리, 아르노가 실질적으로 단순화했다.[7][8] PSLQ 알고리즘은 본질적으로 HJLS와 동등한 것으로 여겨지지만, 2000년에 잭 동가라와 프란시스 설리번이[9] 선정한 "세기의 10대 알고리즘" 중 하나로 선정되었다.[10][11]
  • LLL 알고리즘은 수많은 저자들에 의해 개선되었다. 현대의 LLL 구현은 n이 500 이상일 때 정수 관계 문제를 해결할 수 있다.

적용들

정수 관계 알고리즘에는 수많은 응용 프로그램이 있다. 첫 번째 적용은 x {1, x, x, x2, ..., xn}의 검정력 집합 사이의 정수 관계를 검색하여 주어진 실수 x가 대수학일 가능성이 있는지 여부를 결정하는 것이다. 두 번째 적용은 실수 x와 e, π, ln(2)와 같은 수학 상수 집합 사이의 정수 관계를 검색하는 것으로, 이 상수의 선형 결합으로서 x에 대한 식을 이끌어 낼 것이다.

실험 수학의 전형적인 접근법은 숫자법과 임의의 정밀도 산술법을 사용하여 무한 시리즈, 무한 제품 또는 높은 정밀도의 적분(일반적으로 최소 100개의 유의한 수치)에 대한 근사값을 찾은 다음 정수 관계 알고리즘을 사용하여 정수 관계 betw를 검색하는 것이다.이 값과 일련의 수학 상수. 정수 관계가 발견될 경우, 이는 원본 영상 시리즈, 제품 또는 적분에 대해 가능한 폐쇄형 식을 제안한다. 이 추측은 공식 대수적 방법에 의해 검증될 수 있다. 알고리즘에 대한 입력을 알 수 있는 정밀도가 높을수록 발견된 정수 관계가 단순한 숫자 아티팩트가 아니라는 신뢰도 수준이 높아진다.

이 접근방식의 주목할 만한 성공은 π 값에 대한 베일리-보레인-플로프 공식으로 이어지는 정수 관계를 찾기 위해 PSLQ 알고리즘을 사용한 것이다. PSLQ는 또한 다중 제타 함수와 양자장 이론에서의 그들의 외관과 관련된 새로운 정체성을 찾는데 도움을 주었다. 또한 로지스틱 지도의 분기점을 식별하는데 있어 도움이 되었다. 예를 들어, 여기서 B는4 로지스틱 지도의 네 번째 분기점이며 상수 α = -B4(B4 - 2)는 가장 큰 계수가 257인30 120도 다항식의 루트다.[12][13] 정수 관계 알고리즘은 역심볼 계산기나 플로프의 인버터와 같은 응용 프로그램에서 고정밀 수학적 상수와 경험적 발견 방법의 표와 결합된다.

정수 관계 발견은 높은 수준의 다항식을 고려하는 데 사용될 수 있다.[14]

참조

  1. ^ 실수의 집합은 한정된 정밀도까지만 지정할 수 있기 때문에 계수 크기에 제한을 두지 않은 알고리즘은 항상 충분히 큰 계수에 대한 정수 관계를 찾을 것이다. 관심 결과는 정수 관계에서 계수의 크기가 실제 숫자가 지정된 정밀도에 비해 작을 때 발생한다.
  2. ^ Weisstein, Eric W. "Integer Relation". MathWorld.
  3. ^ Weisstein, Eric W. "LLL Algorithm". MathWorld.
  4. ^ Weisstein, Eric W. "HJLS Algorithm". MathWorld.
  5. ^ 요한 호스타드, 베티나 저스트, 제프리 라고리아스, 클로스-피터 슈노르: 실수의 정수 관계를 찾기 위한 다항 시간 알고리즘. 예비 버전: STACS 1986(심포시움 정리) 컴퓨터 과학의 측면) 강의 노트 컴퓨터 과학 210(1986), 페이지 105–118. SIAM J. 연산, 제18권(1989), 페이지 859–881
  6. ^ Weisstein, Eric W. "PSOS Algorithm". MathWorld.
  7. ^ Weisstein, Eric W. "PSLQ Algorithm". MathWorld.
  8. ^ Helman R. P. 퍼거슨과 David H. Bailey의 다항 시간, 수치적으로 안정된 정수 관계 알고리즘; RNR 기술 보고서 RNR-91-032; 1992년 7월 14일
  9. ^ Cipra, Barry Arthur. "The Best of the 20th Century: Editors Name Top 10 Algorithms" (PDF). SIAM News. 33 (4).
  10. ^ 징웨이 첸, 데미안 스틸레, 길레스 빌라드: HJLS와 PSLQ: Lattice의 합과 투영, ISSAC'13
  11. ^ Helaman R. P. 퍼거슨, David H. Bailey 및 Steve Arno, PSLQ 분석, 정수 관계 찾기 알고리즘: [1]
  12. ^ 데이비드 H. 베일리 및 데이비드 J. 브로드허스트 "병렬 정수 관계 감지: 기법과 응용" 계산의 수학, vol. 70, no. 236 (2000년 10월), 페이지 1719–1736; LBNL-44481.
  13. ^ I. S. 코티레아스와 K. 카라만오스, "로지스틱 지도와 베일리-브로드허스트 추측의 분기점 B4의 정확한 계산", I. J. 분기 및 혼돈 14(2004):2417–2423(2004)
  14. ^ M. van Hoij: 인수 다항식과 배낭 문제. J. of Number 이론, 95, 167–189, (2002)

외부 링크