울람 나선

201×201 크기의 울람 나선. 검은 점은 소수를 나타낸다. 소수 밀도가 높은 대각선, 수직선, 수평선이 뚜렷하게 보인다. 비교를 위해, 임의의 홀수를 검은색으로 칠한 나선 (200x200 나선에서 소수와 같은 밀도). **울람 나선**(Ulam spiral) 또는 **소수 나선**(prime spiral)은 소수 집합을 그래픽으로 묘사한 것으로, 1963년 수학자 스타니스와프 울람이 고안했으며 얼마 후 마틴 가드너의 사이언티픽 아메리칸의 수학 게임 칼럼에서 대중화되었다.p=122 이 나선은 양의 정수를 정사각형 나선으로 쓰고 소수를 특별히 표시하여 구성된다. 울람과 가드너는 나선에서 많은 수의 소수를 포함하는 눈에 띄는 대각선, 수평선, 수직선의 놀라운 출현을 강조했다. 울람과 가드너는 나선에서의 이러한 눈에 띄는 선의 존재가 예상치 못한 것이 아니라고 언급했는데, 나선에서의 선은 이차 다항식에 해당하고, 오일러의 소수 생성 다항식 x2 − x + 41과 같은 특정 다항식은 높은 소수 밀도를 생성한다고 믿어지기 때문이다.p=517p=124 그럼에도 불구하고 울람 나선은 란다우 문제와 같은 수론의 주요 미해결 문제와 연결되어 있다. 특히, 어떤 이차 다항식도 무한히 많은 소수를 생성하거나, 훨씬 더 나아가 점근적 밀도가 높다는 것이 증명된 적은 없지만, 그 점근적 밀도가 무엇이어야 하는지에 대한 잘 지지되는 추측이 있다. 1932년, 울람의 발견보다 31년 전에 로렌스 클라우버라는 파충류학자는 소수의 유사한 집중을 보이는 수직선 및 대각선을 포함하는 삼각형 모양의 비나선형 배열을 구성했다. 울람처럼 클라우버는 오일러의 것과 같은 소수 생성 다항식과의 연관성을 언급했다.p=373
# 구성
울람 나선은 양의 정수를 정사각형 격자 위에 나선 형태로 써서 구성된다. :1에서 49까지의 숫자를 나선형 순서로 배치 그리고 나서 소수를 표시한다. :작은 울람 나선 그림에서 소수는 특정 대각선을 따라 집중되는 것처럼 보인다. 위에서 보여준 201×201 울람 나선에서는 대각선이 뚜렷하게 보이며, 그 지점까지의 패턴을 확인시켜준다. 소수 밀도가 높은 수평선과 수직선도 덜 두드러지지만 분명히 나타난다. 가장 흔하게는 숫자 나선이 중앙의 1로 시작되지만, 어떤 숫자로든 시작할 수 있으며, 대각선, 수평선, 수직선을 따라 소수가 동일하게 집중되는 현상이 관찰된다. 중앙을 41로 시작하면 40개의 연속적인 소수로 이루어진 대각선이 나타나는데 (원점 남서쪽 1523에서 시작하여 원점의 41로 감소하고 원점 북동쪽 1601로 증가함), 이는 이 종류의 가장 긴 예이다.p=21
# 역사
가드너에 따르면, 울람은 1963년에 과학 회의에서 "길고 매우 지루한 논문" 발표 중에 낙서하다가 나선을 발견했다고 한다.p=122 이 손으로 한 계산은 "수백 점"에 달했다. 얼마 후, 울람은 동료인 마이런 스타인과 마크 웰스와 함께 로스앨러모스 과학 연구소의 MANIAC II를 사용하여 계산을 약 100,000점으로 확장했다. 이 그룹은 또한 소수가 많은 선과 소수가 적은 선을 따라 10,000,000까지의 숫자 중에서 소수의 밀도를 계산했다. 65,000점까지의 나선 이미지는 "기계에 연결된 스코프"에 표시된 다음 촬영되었다.p=520 울람 나선은 마틴 가드너의 1964년 3월호 사이언티픽 아메리칸 수학 게임 칼럼에 실렸으며 그 호의 표지를 장식했다. 스타인, 울람, 웰스의 일부 사진이 그 칼럼에 재현되었다. 사이언티픽 아메리칸 칼럼의 부록에서 가드너는 클라우버의 이전 논문을 언급했다.p=88. 클라우버는 그의 구성을 다음과 같이 설명한다. "정수는 1을 꼭대기로 하는 삼각형 형태로 배열되고, 두 번째 줄은 2에서 4까지의 숫자를, 세 번째 줄은 5에서 9까지의 숫자를 포함하며, 이러한 방식으로 계속된다. 소수를 표시하면 특정 수직선 및 대각선에 집중되어 있으며, 그 중 소수 집중도가 높은 소위 오일러 시퀀스가 발견된다."p=373
# 설명
숫자 나선에서의 대각선, 수평선, 수직선은 다음 형태의 다항식에 해당한다. : f(n) = 4 n^2 + b n + c 여기서 b와 c는 정수 상수이다. b가 짝수일 때, 선은 대각선이고, c 값에 따라 모든 숫자가 홀수이거나 모든 숫자가 짝수이다. 따라서 2를 제외한 모든 소수가 울람 나선의 다른 대각선에 놓이는 것은 놀라운 일이 아니다. 4 n^2 + 8 n + 3과 같은 일부 다항식은 홀수 값만 생성하지만, 정수 (4 n^2 + 8 n + 3)=(2n+1)(2n+3)로 인수분해되므로, 인수 중 하나가 1이 되는 경우를 제외하고는 소수가 될 수 없다. 이러한 예는 소수가 없거나 거의 없는 대각선에 해당한다. 나머지 홀수 대각선 중 일부가 다른 대각선보다 소수의 밀도가 더 높은 이유에 대한 통찰력을 얻기 위해 4 n^2 + 6 n + 1과 4 n^2 + 6 n + 5를 고려해보자. n이 0, 1, 2, ...와 같이 연속적인 값을 취할 때 3으로 나눈 나머지를 계산한다. 이 다항식 중 첫 번째 다항식의 경우 나머지 시퀀스는 1, 2, 2, 1, 2, 2, ...이고, 두 번째 다항식의 경우 2, 0, 0, 2, 0, 0, ...이다. 이는 두 번째 다항식이 취하는 값의 시퀀스에서 세 개 중 두 개가 3으로 나누어 떨어지므로 확실히 소수가 아니며, 첫 번째 다항식이 취하는 값의 시퀀스에서는 어떤 것도 3으로 나누어 떨어지지 않는다는 것을 의미한다. 따라서 첫 번째 다항식이 두 번째 다항식보다 소수의 밀도가 더 높은 값을 생성할 것이라고 가정하는 것이 타당해 보인다. 적어도 이 관찰은 해당 대각선이 소수로 동일하게 밀집되어 있을 것이라고 믿을 이유를 거의 제공하지 않는다. 물론 3 이외의 소수로 나누어 떨어지는지 여부를 고려해야 한다. 5로 나누어 떨어지는지 여부도 함께 조사하면, 첫 번째 다항식의 경우 15로 나눈 나머지는 1, 11, 14, 10, 14, 11, 1, 14, 5, 4, 11, 11, 4, 5, 14 패턴으로 반복되고, 두 번째 다항식의 경우 5, 0, 3, 14, 3, 0, 5, 3, 9, 8, 0, 0, 8, 9, 3 패턴으로 반복된다. 이는 두 번째 시퀀스에서 15개의 값 중 세 개만이 잠재적으로 소수(3으로도 5로도 나누어 떨어지지 않음)인 반면, 첫 번째 시퀀스에서 15개의 값 중 12개가 잠재적으로 소수(세 개만 5로 나누어 떨어지고 어떤 것도 3으로 나누어 떨어지지 않음)임을 의미한다. 이차 수열의 소수에 대한 엄밀하게 증명된 결과는 거의 없지만, 위와 같은 고려 사항들은 다음 섹션에 설명된 바와 같이 그러한 수열의 소수의 점근적 밀도에 대한 타당한 추측을 제시한다.
# 하디-리틀우드의 추측 F
골트바흐 추측에 대한 1923년 논문에서 하디와 리틀우드는 일련의 추측을 제시했는데, 그 중 하나가 사실이라면 울람 나선의 놀라운 특징 중 일부를 설명할 수 있을 것이다. 하디와 리틀우드가 "추측 F"라고 부른 이 추측은 베이트먼-혼 추측의 특별한 경우이며, ax2 \+ bx + c 형태의 소수 개수에 대한 점근적 공식을 주장한다. 울람 나선의 중앙 영역에서 수평 및 수직과 45° 각도를 이루며 방사되는 광선은 b가 짝수인 4x2 \+ bx + c 형태의 숫자에 해당한다. 수평 및 수직 광선은 b가 홀수인 동일한 형태의 숫자에 해당한다. 추측 F는 그러한 광선을 따라 소수의 밀도를 추정하는 데 사용할 수 있는 공식을 제공한다. 이는 다른 광선을 따라 밀도에 상당한 변동이 있을 것임을 시사한다. 특히, 밀도는 다항식의 판별식 b2 − 16c에 매우 민감하다. x = 0, 1, 2, ...인 4x2 − 2x + 41 형태의 소수가 보라색으로 강조되었다. 그림 하반부의 눈에 띄는 평행선은 4x2 \+ 2x + 41 또는 음수 x 값에 해당한다. 추측 F는 a, b, c가 정수이고 a가 양수인 ax2 \+ bx + c 형태의 다항식에 관한 것이다. 계수가 1보다 큰 공통 인수를 포함하거나 완전제곱인 판별식 Δ = b2 − 4ac를 가지면, 다항식은 인수분해되어 x가 0, 1, 2, ... 값을 취할 때 합성수를 생성한다 (인수 중 하나가 1과 같은 x의 한두 값은 제외). 더욱이, a + b와 c가 모두 짝수이면, 다항식은 짝수 값만 생성하므로, 2를 제외하고는 합성수이다. 하디와 리틀우드는 이러한 상황을 제외하고는 ax2 \+ bx + c가 x가 0, 1, 2, ... 값을 취할 때 무한히 자주 소수 값을 취한다고 주장한다. 이 진술은 이전 부냐콥스키 추측의 특별한 경우이며 여전히 미해결로 남아 있다. 하디와 리틀우드는 또한 점근적으로, ax2 \+ bx + c 형태의 소수 중 n보다 작은 P(n)의 개수는 다음과 같이 주어진다고 주장한다. : P(n)\sim A\frac{1}{\sqrt{a\frac{\sqrt{n{\log n} 여기서 A는 a, b, c에 의존하지만 n에는 의존하지 않는다. 소수 정리에 의해, A를 1로 설정한 이 공식은 ax2 \+ bx + c 형태의 숫자 집합과 같은 밀도를 가진 임의의 숫자 집합에서 예상되는 n 미만의 소수의 점근적 개수이다. 그러나 A는 1보다 크거나 작은 값을 취할 수 있으므로, 추측에 따르면 일부 다항식은 특히 소수가 많고, 다른 다항식은 특히 소수가 적을 것이다. 이례적으로 소수가 많은 다항식은 울람 나선에 눈에 보이는 선을 형성하는 4x2 − 2x + 41이다. 이 다항식의 상수 A는 약 6.6으로, 추측에 따르면 이 다항식이 생성하는 숫자는 비슷한 크기의 무작위 숫자보다 소수일 확률이 거의 7배 높다는 것을 의미한다. 이 특정 다항식은 x를 2x로 대체하거나, 동등하게 x를 짝수로 제한함으로써 오일러의 소수 생성 다항식 x2 − x + 41과 관련되어 있다. 상수 A는 모든 소수에 대한 곱으로 주어진다. : A = \prod\limits_{p} \frac{p-\omega(p)}{p-1}~, 여기서 \omega (p)는 이차 다항식 모듈로 p의 영점 개수이며, 따라서 0, 1, 2 중 하나의 값을 취한다. 하디와 리틀우드는 곱을 세 가지 인수로 나눈다. : A = \varepsilon\prod_p \biggl(\frac{p}{p-1}\biggr)\,\prod_{\varpi}\biggl(1-\frac{1}{\varpi-1}\Bigl(\frac{\Delta}{\varpi}\Bigr)\biggr). 여기서 소수 2에 해당하는 인자 ε은 a + b가 홀수이면 1이고, a + b가 짝수이면 2이다. 첫 번째 곱 인덱스 p는 a와 b를 모두 나누는 유한한 홀수 소수들을 따라간다. 이 소수들에 대해 \omega (p)=0인데, p가 c를 나눌 수 없기 때문이다. 두 번째 곱 인덱스 \varpi는 a를 나누지 않는 무한히 많은 홀수 소수들을 따라간다. 이 소수들에 대해 \omega (p)는 판별식이 모듈로 p에서 0인지, 0이 아닌 제곱수인지, 아니면 제곱수가 아닌지에 따라 1, 2, 0과 같다. 이것은 르장드르 기호 \left(\frac{\Delta}{\varpi}\right)를 사용하여 설명된다. 소수 p가 a를 나누지만 b를 나누지 않을 때, 모듈로 p에는 하나의 근이 있다. 결과적으로, 그러한 소수들은 곱에 기여하지 않는다. 현재까지 알려진 가장 높은 값인 A ≈ 11.3을 가진 이차 다항식이 Jacobson과 Williams에 의해 발견되었다.
# 변형
클라우버의 1932년 논문은 n번째 행이 (n − 1)2 \+ 1부터 n2까지의 숫자를 포함하는 삼각형을 설명한다. 울람 나선에서와 같이, 이차 다항식은 직선에 놓이는 숫자를 생성한다. 수직선은 k2 − k + M 형태의 숫자에 해당한다. 소수 밀도가 높은 수직선과 대각선이 그림에서 분명히 보인다. 로버트 삭스는 1994년에 울람 나선의 변형을 고안했다. 삭스 나선에서는 음이 아닌 정수가 울람이 사용한 정사각형 나선 대신 아르키메데스 와선에 그려지며, 각 완전 회전마다 하나의 정사각수가 나타나도록 간격을 둔다. (울람 나선에서는 각 회전마다 두 개의 제곱수가 나타난다.) 오일러의 소수 생성 다항식인 x2 − x + 41은 이제 x가 0, 1, 2, ... 값을 취할 때 단일 곡선으로 나타난다. 이 곡선은 그림의 왼쪽 절반에서 수평선에 점근적으로 접근한다. (울람 나선에서 오일러의 다항식은 두 개의 대각선을 형성하는데, 하나는 시퀀스에서 x의 짝수 값에 해당하는 그림의 위쪽 절반에, 다른 하나는 시퀀스에서 x의 홀수 값에 해당하는 그림의 아래쪽 절반에 있다.) 합성수도 울람 나선에 포함될 때 추가적인 구조가 나타날 수 있다. 숫자 1은 자신이라는 단 하나의 인수를 갖는다. 각 소수는 자신과 1이라는 두 인수를 갖는다. 합성수는 적어도 세 개 이상의 다른 인수로 나누어 떨어진다. 정수를 나타내는 점의 크기를 인수의 개수로 나타내고 소수를 빨간색으로, 합성수를 파란색으로 칠하면 그림과 같은 결과가 나온다. 평면의 다른 테셀레이션을 따르는 나선도 소수가 풍부한 선을 생성한다. 예를 들어 육각형 나선이 있다. 왼쪽 비우기 다항식 x2 − x + 41에 의해 생성된 소수가 강조된 클라우버 삼각형 Image:Sacks 나선 File:Spirale Ulam 합성수를 모두 보여주는 150×150 크기의 울람 나선 File:Hexgrid prime number 소수, 진한 파란색은 더 고차 합성수를 나타내는 육각형 숫자 나선 위에 7503개의 소수가 보이는 숫자 나선 File:Ulam Spiral of 10 Million 개의 소수를 포함하는 울람 나선