Positive Lower Density for Hofstadter's $ab-1$ Problem

무한한 숫자 만들기 게임

숫자들이 장난감인 거대하고 끝없는 놀이터를 상상해 보세요. 수학, 특히 정수론이라는 분야에서 연구자들은 기존의 숫자로 새로운 숫자를 만들어내는 규칙을 가지고 노는 것을 좋아합니다. 이와 유사한 가장 유명한 유형의 게임 중 하나는 '재귀(recurrence)' 또는 '갱신(renewal)'과 관련이 있습니다. 이것은 사람 대신 숫자가 있고, 의자 대신 수직선 위의 특정 지점이 있는 의자 뺏기 게임과 같습니다. 수학자들이 수십 년 동안 던져온 핵심 질문은 이렇습니다: 만약 이 게임을 영원히 계속한다면, 생성된 숫자들은 놀이터 전체에 고르게 퍼질까요, 아니면 한쪽 구석에 뭉쳐서 거대한 빈 공간을 남길까요?

이 논문은 단순한 규칙에서 시작된 퍼즐을 다룹니다: 2와 3이라는 숫자로 시작합니다. 그런 다음, 이미 가지고 있는 서로 다른 두 숫자를 골라 곱한 뒤 1을 뺍니다. 만약 그 결과가 정수라면, 그 숫자를 당신의 컬렉션에 추가합니다. 이 과정을 영원히 반복합니다. 전설적인 수학자 폴 에르되시(Paul Erdős)가 (유명한 '호프스태터의 형상-형상' 수열의 저자로부터 들은) 이 문제를 제기했는데, 이 질문의 핵심은 이 숫자 집합이 충분히 '두꺼운가' 하는 것입니다. 즉, '양의 하한 밀도(positive lower density)'를 갖는가 하는 점입니다. 쉬운 말로 설명하자면, 숫자를 생성하는 이 집합이 아무리 멀리 나아가더라도 수직선의 상당한, 즉 0이 아닌 비율을 차지할 만큼 결국 채워지게 될까요? 오랫동안 아무도 이 답이 예인지 아니면 아니오인지 알지 못했습니다.

해결책: 숫자를 위한 교통 체계

이 논문에서 사무엘 코스키(Samuel Korsky)는 그 답이 **'예'**라고 증명합니다. 이 규칙에 의해 생성된 숫자의 집합은 실제로 양의 하한 밀도를 가집니다. 이는 더 큰 범위의 숫자들을 살펴볼 때마다, 당신은 항상 이 특별한 집합에 속하는 보장된, 0이 아닌 덩어리를 발견하게 될 것임을 의미합니다. 그것은 단지 흩어진 몇 개의 숫자가 아니라 풍부한 존재입니다.

저자가 이 문제를 어떻게 해결했는지 이해하기 위해, 숫자 집합을 하나의 도시로, 그리고 '곱하고 1을 빼기'라는 규칙을 일방통행 도로로 상상해 보세요. 저자의 목표는 이 도시를 통과해 운전할 수 있는 방법이 너무나 많아서 목적지에 도달하는 것을 피할 수 없음을 보여주는 것이었습니다. 하지만 함정이 있습니다. 규칙에 따르면 반드시 서로 다른 숫자를 곱해야 합니다. 만약 어떤 숫자를 자기 자신과 곱하려고 하면 규칙이 깨집니다. 이것은 마치 당신이 이미 같은 경로를 지나왔다면 그 도로 구간을 더 이상 달릴 수 없다고 규정하는 교통 법규와 같습니다.

저자의 전략은 20개의 특정 구역(구간)으로 나뉜 지도를 사용하여 '교통 제어 시스템'을 구축하는 것입니다. 그는 각 구역에 서로 다른 '곱해지는 수(multipliers)'(예: 2, 3, 5, 9, 14)를 할당합니다. 숫자가 특정 구역에 들어오면, 시스템은 다음에 사용할 곱해지는 수를 알려줍니다. 이 증명의 천재성은 이 곱해지는 수들이 선택되는 방식에 있습니다. 저자는 네 가지 서로 다른 '교통 패턴'(할당)을 설정합니다. 현재 시스템의 상태에 따라 이 패턴들 사이를 전환함으로써, 숫자들이 갇히거나 '서로 다름(distinctness)' 규칙 위반에 부딪히지 않도록 보장합니다.

이것을 리더를 따라가는 '따라하기 게임'이라고 생각해보세요. 여기서 리더는 완벽한 균형을 유지하려고 노력합니다. 저자는 숫자의 '성분'(구체적으로는 소수 2, 3, 5, 7의 거듭제곱)을 추적합니다. 그는 레시피가 균형을 유지하여 숫자가 매우 구체적이고 예측 가능한 방식으로 성장하기를 원합니다. 그는 피드백 루프를 사용합니다: 만약 레시피가 숫자 2 쪽으로 너무 무거워지면, 시스템은 3이나 5를 더 추가하여 균형을 맞추는 패턴으로 전환합니다. 이를 통해 성장의 '기울기'(숫자가 커지는 속도)를 특정 목표치에 고정시킵니다.

논문은 이러한 전환들을 세심하게 관리함으로써, 시스템이 동일한 '기울기'에 도달하는 엄청나게 많은 고유한 경로들을 만들어낸다는 것을 보여줍니다. 경로들이 고유하고 시스템이 시작점으로 계속 돌아오도록 설계되었기 때문에(이를 '양의 재귀성'이라 부릅니다), 수학적으로 무수히 많은 서로 다른 숫자가 생성됨을 증명합니다.

결정적으로, 저자는 밑바탕이 되는 수학적 구조가 일부 겹침을 허용함에도 불구하고(시스템이 엄밀한 의미에서 '자유로운' 것은 아닙니다), 이 경로들이 서로 구별된다는 것을 증명합니다. 그는 20개 구역 지도를 따라 경로를 역추적하면, 마지막 지점에 도달하기 전까지는 절대 서로 교차하지 않는다는 것을 보여줌으로써 이를 입증합니다. 이는 모든 경로가 고유한 최종 숫자를 생성한다는 것을 보장합니다.

최종 결론은 계수 논증(counting argument)입니다. 저자는 이 과정의 매 '단계'마다 유효한 경로의 수가 숫자 자체의 성장률과 일치하는 속도로 증가함을 계산합니다. 그는 특정 큰 수 $x$에 대하여, 1부터 $x$까지의 범위 내에서 발견되는 그의 특별한 집합의 양이 적어도 $c \times x$ (여기서 $c$는 0보다 큰 상수) 이상임을 증명합니다. 즉, 숫자를 세는 과정이 어디까지 진행되든, 당신은 항상 이 숫자들의 꾸준한 흐름을 발견하게 될 것입니다.

이 논문은 단순히 이것이 가능할 것이라고 암시하는 데 그치지 않고, 엄격하고 단계적인 수학적 증명을 제공합니다. 확률(시스템이 시작점으로 계속 돌아온다는 것을 보여주기 위해), 기하학(구간을 지도화하기 위해), 그리고 정수론(소인수를 세기 위해)을 결방합하여 사용합니다. 결과는 수십 년 된 질문에 대한 확정적인 답변입니다: 이 집합은 희박하지 않습니다. 그것은 밀도가 높으며, 수직선을 신뢰할 수 있는 양의 존재감으로 채우고 있습니다.