스콜렘-말러-레흐 정리

가법 및 대수적 수 이론에서, 스콜렘-마흘러-레흐 정리는 숫자의 시퀀스가 선형 차이 방정식을 만족하면, 그 시퀀스가 0인 위치가 규칙적으로 반복되는 패턴을 형성한다고 기술한다.이 결과는 Thoralf Scolem(합리적 숫자의 시퀀스에 대한 정리를 입증한 사람), Kurt Mahler(대수적 숫자의 시퀀스에 대해 증명된 사람), Christer Lech(특성 0의 어떤 영역에 원소가 속하는 시퀀스에 대해 증명된 사람)의 이름을 따서 명명되었다.그것의 알려진 증거는 p-adic 분석을 사용하며 비구축적이다.

정리명세서

Let ${\displaystyle s(n)_{n\geq 0}}$ be a sequence of complex numbers satisfying ${\displaystyle s(n)=c_{1}s(n-1)+c_{2}s(n-2)+\cdots +c_{d}s(n-d)}$ for all ${\displaystyle n\geq d}$, where ${\displaystyle c_{i}}$ are복잡한 숫자 상수(즉, 순서 $d{\displaystyle }$ ${\displaystyle d}$의 연속 반복 시퀀스).$$그러면 0의 ${\displaystyle 집합}$이 ${\displaystyle \mathrm{유한}}$집합의 대칭적 차이와 같으며$$$,$ 산술적으로 $완전$하게 많은 수의 진행과 같다$.$여기서 무한 산술 진행은 i와 b의 정수가 존재하여 진행은 b modulo a와 동일한 모든 양의 정수로 구성되면 가득 찬다.$c{\displaystyle {}_{}}$ ${\displaystyle d_{}}$≠ ${\displaystyle 0}$ ${\dplaystyle c_{d}\neq$ 0$}$을($$를) 추가로 포함할 경우(1, 0, 0, 0, ...와 같은 시퀀스는 제외) 대칭 차이를 유니언으로 대체할 수 있다.

예

순서를 고려하십시오.

0, 0, 1, 0, 1, 0, 2, 0, 3, 0, 5, 0, 8, 0, ...

0과 피보나치 숫자 사이에서 번갈아 나타나는 것.이 시퀀스는 선형 반복 관계에 의해 생성될 수 있다.

${\displaystyle F(i)=F(i-2)+F(i-4)}$

(피보나치 재발의 변형된 형태) 베이스 케이스 F(1) = F(2) = F(4) = 0, F(3) = 1. 이 시퀀스의 경우 F(i) = 0은 하나이거나 짝인 경우에만 0이다.따라서 시퀀스가 0인 위치는 유한 집합(싱글톤 집합 {1})과 완전 산술 연속(양수 짝수)으로 분할할 수 있다.

이 예에서는 하나의 산술 진행만 필요했지만, 다른 반복 시퀀스는 다중 산술 진행률을 형성하는 위치에서 0을 가질 수 있다.

관련결과

스콜렘 문제는 주어진 반복 시퀀스에 0이 있는지 여부를 판단하는 문제다.0이 무한히 많은지를 시험하는 알고리즘이 존재하며,^[1] 0이 무한히 많은지를 시험하는 알고리즘이 존재하며, 만일 그렇다면 스콜렘-말러-레흐 정리에 의해 존재한다고 보장된 주기적인 집합으로 분해되는 것을 찾아내는 알고리즘이 존재한다.그러나 반복 시퀀스에 비주기적 0이 있는지 여부를 판별하는 알고리즘이 존재하는지 여부는 알 수 없다(Ouaknine & Worrell 2012).

참조

• Skolem, Th. (1933), "Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf diophantische Gleichungen", Oslo Vid. akad. Skrifter, I (6), 1953년 레흐에서 인용했다.
• Mahler, K. (1935), "Eine arithmetisehe Eigenschaft der Taylor-koeffizienten ralionaler Funktionen", Akad. Wetensch. Amsterdam, Proc., 38: 50–60, 1953년 레흐에서 인용했다.
• Lech, C. (1953), "A Note on Recurring Series", Arkiv för Matematik, 2: 417–421, doi:10.1007/bf02590997.
• Mahler, K. (1956), "On the Taylor coefficients of rational functions", Proc. Cambridge Philos. Soc., 52: 39–48, doi:10.1017/s0305004100030966.
• Mahler, K. (1957), "Addendum to the paper "On the Taylor coefficients of rational functions"", Proc. Cambridge Philos. Soc., 53: 544, doi:10.1017/s0305004100032552.
• Ouaknine, Joël; Worrell, James (2012), "Decision problems for linear recurrence sequences", Reachability Problems: 6th International Workshop, RP 2012, Bordeaux, France, September 17-19, 2012, Proceedings, Lecture Notes in Computer Science, vol. 7550, Heidelberg: Springer-Verlag, pp. 21–28, doi:10.1007/978-3-642-33512-9_3, MR 3040104.

외부 링크

• Weisstein, Eric W. "Skolem-Mahler-Lech Theorem". MathWorld.