수 이론의 유효 결과
Effective results in number theory | 이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다.(2010년 9월)(이를 과 시기 |
역사적 이유와 디오판타인 방정식의 해법에 적용하기 위해, 수학의 다른 분야보다 숫자 이론의 결과가 더 면밀하게 조사되어 그 내용이 효과적으로 계산[citation needed] 가능한지를 살펴보았다.일부 정수 목록이 유한하다고 주장되는 경우, 문제는 원칙적으로 기계 계산 후 목록을 출력할 수 있는가 하는 것이다.
리틀우드의 결과
비효과적인 결과의 초기 예는 1914년의 J. E. 리틀우드의 정리인데,[1] 소수 정리에서는 점증적 추정이 있는 ψ(x)와 π(x)의 차이가 모두 부호를 무한히 자주 바꾼다.[2]1933년 스탠리 스큐스는 현재 스큐스의 번호로 알려진 첫 번째 간판 변경에 대한 효과적인 상한선을 획득했다.[3]
보다 세부적으로, 숫자 시퀀스 f(n)에 대한 쓰기, 무한히 변화하는 부호에 대한 효과적인 결과는, N의 모든 값에 대해, f(N)와 f(M)가 다른 부호를 갖는 값 M > N을 포함하는 정리일 것이고, M은 지정된 자원으로 계산될 수 있을 것이다.실용적으로 보면, M은 N 이상의 값을 취함으로써 계산될 것이며, 문제는 '얼마나 가야 하는가?'이다.특별한 경우는 첫 번째 표지판 변화를 찾는 것이다.질문의 관심사는 알려진 수치적 증거는 아무런 변화도 보이지 않는다는 점이었다: 리틀우드의 결과는 이 증거가 단지 작은 숫자 효과라는 것을 보장했지만, 여기서 '작은'은 n에서 최대 10억까지 값을 포함했다.
계산가능성의 요구사항은 결과를 증명하기 위해 분석적 숫자 이론에 사용된 접근법과 대조된다.예를 들어, 란도 표기법과 그 묵시 상수의 사용에 의문을 제기한다: 그러한 상수에 대한 주장은 순수한 존재론인가, 아니면 1000(say)이 암시 상수를 대신하는 버전을 복구할 수 있는가?즉, 기호의 변경과 같은 M > N이 있다는 것을 알았다면.
- M = O(G(N))
일부 명시적 함수 G에 대해, 파워, 로그 및 지수로부터 축적된 말로, 이는 단지
- M < A.G(N)
어떤 절대 상수 A에 대해서이른바 묵시 상수인 A의 값도 계산 목적으로 명시적으로 만들 필요가 있을 수 있다.란도 표기법이 유행했던 한 가지 이유는 A가 정확히 무엇인지 숨기기 때문이다.어떤 간접적인 형태의 증거에서는 암시된 상수가 명시적으로 만들어질 수 있다는 것이 전혀 명백하지 않을 수 있다.
'시겔 시대'
1900-1950년에 입증된 분석적 수 이론의 주요 결과들 중 많은 것들이 사실 효과적이지 않았다.주요 예는 다음과 같다.
- 투-시겔-로스 정리
- 1929년부터 적분점에 대한 시겔의 정리
- 1934년 1급 문제에 대한[4] 한스 헤이즐브론·에드워드 린풋의 정리
- 1935년 '시겔[5] 제로'에 대한 결과
- 시겔 제로에 기초한 시겔-왈피즈 정리.
이론적으로 불완전하게 남겨진 구체적인 정보에는 등급 번호에 대한 하한(일부 숫자 분야의 이상 등급 그룹 증가)과 분모 측면에서 대수적 숫자에 대한 최상의 합리적 근사치에 대한 한계가 포함되었다.이 후자는 악셀 투의 작업 후에 디오판틴 방정식에 대한 결과로 꽤 직접적으로 읽힐 수 있었다.증거에서 Louville 숫자에 사용된 결과는 평균값 정리를 적용하는 방식에 효과적이지만 개선(현재 Thue-Siegel-Roth 정리)은 그렇지 않았다.
나중일
나중에 나온 결과들, 특히 앨런 베이커는 그 위치를 바꾸었다.질적으로 말하면 베이커의 이론은 약해 보이지만, 명시적인 상수를 가지고 있고, 기계 계산과 함께 실제로 적용되어 (완료될 것으로 예상되는) 해결책 목록이 실제로 전체 솔루션 세트라는 것을 증명할 수 있다.
이론적 이슈
이곳의 어려움은 모순에 의한 증명에 훨씬 더 신경을 쓰면서 근본적으로 다른 증명 기법에 의해 충족되었다.관련된 논리는 계산가능성 이론과 계산 가능한 함수의 논리보다 증명 이론에 가깝다.어려움이 계산 복잡성 이론의 영역에 있을 수 있다는 것은 다소 느슨한 추측이다.A형이나 B형에서는 아직 실효성이 없는 결과가 증명되고 있는데, 어느 쪽인지 알 길이 없다.
참조
- ^ Littlewood, J. E. (1914). "Sur la distribution des nombres premiers". Comptes Rendus. 158: 1869–1872. JFM 45.0305.01.
- ^ Feferman, Solomon (1996). "Kreisel's "unwinding" program" (PDF). Kreiseliana. Wellesley, MA: A K Peters. pp. 247–273. MR 1435765. 사전 인쇄 버전의 9페이지를 참조하십시오.
- ^ Skewes, S. (1933). "On the difference π(x) − Li(x)". Journal of the London Mathematical Society. 8: 277–283. doi:10.1112/jlms/s1-8.4.277. JFM 59.0370.02. Zbl 0007.34003.
- ^ Heilbronn, H.; Linfoot, E. H. (1934). "On the imaginary quadratic corpora of class-number one". Quarterly Journal of Mathematics. Oxford Series. 5 (1): 293–301. doi:10.1093/qmath/os-5.1.293..
- ^ *Sprindzhuk, V.G. (2001) [1994], "Diophantine approximation, problems of effective", Encyclopedia of Mathematics, EMS Press – 바운드의 비효과적인 부분에 대한 코멘트.
외부 링크
- Sprindzhuk, V.G. (2001) [1994], "Diophantine approximations", Encyclopedia of Mathematics, EMS Press
