🔢 mathematics

A counterexample to a subadditivity conjecture of Cohen for Sophie Germain cyclic numbers

이 논문은 $m=31$ 및 $n=3928$ 에서의 특정 반례를 제시함으로써 소피 제르맹 순환 수(Sophie Germain cyclic numbers)에 대한 코언의 부가성 추측(Cohen's subadditivity conjecture)이 틀렸음을 입증하며, 이 결과는 Lean 4 커널에 의해 공식적으로 검증되었다.

원저자: Josué Alexander Ibarra

게시일 2026-07-14

📖 2 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Josué Alexander Ibarra

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 '순환수(cyclic numbers)'라고 불리는 특별한 숫자들로 구성된 거대한 파티를 기획하고 있다고 상상해 보세요. 이들은 숫자의 세계에서 VIP입니다. 이들에게는 그 크기만큼의 모든 그룹을 혼란 없이 완벽한 원형으로 배치할 수 있는 독특한 초능력이 있습니다. 더 멋진 클럽인 '소피 제르맹 순환수(Sophie Germain cyclic numbers)' 모임도 있습니다. 이 클럽에 들어가려면 본인이 먼저 VIP여야 하고, 그의 '플러스 원' 쌍둥이(구체적으로 $2n + 1$ ) 또한 VIP여야 합니다.

오랫동안 수학자 코헨(Cohen)은 이 VIP들이 어떻게 퍼져 있는지에 대한 직관을 가지고 있었습니다. 그는 이들이 **부가성(subadditivity)**이라는 규칙을 따른다고 생각했습니다. 이것은 '중복 계산 금지' 규칙과 같습니다. 이 규칙은 $m$ 명의 사람들로 이루어진 작은 그룹에 있는 VIP의 수를 세고, 여기에 $n$ 명의 사람들로 이루어진 더 큰 그룹에 있는 VIP의 수를 더하면, 그 합계는 단순히 $m + n$ 명의 결합된 그룹에서 발견되는 VIP의 수보다 항상 크거나 같아야 한다는 규칙입니다. 즉, 시작부터 이어지는 첫 번째 슬라이스보다 무작위로 뽑은 슬라이스에서 더 밀집된 VIP 군단을 발견할 수는 없다는 뜻입니다.

코헨은 백만( $10^6$ )까지의 숫자들을 대상으로 이 규칙을 확인했고, 단 하나의 틈도 발견하지 못했습니다. 그는 매우 확신한 나머지 이를 **추측 66(Conjecture 66)**이라고 기록했습니다.

하지만 여기서 반전이 일어납니다. 그 규칙은 깨졌습니다.

수학자 호수에 알렉산더 이바라(Josué Alexander Ibarra)는 파티가 놀라울 정도로 붐비는 특정 지점을 찾아내어 '중복 계산 금지' 규칙을 무너뜨렸습니다. 그는 31과 3928이라는 두 특정 숫자를 살펴보았습니다.

처음 31개의 숫자 중에서 VIP를 세면 정확히 10명이 나옵니다.
처음 3928개의 숫자 중에서 VIP를 세면 어떤 큰 숫자(편의상 $X$ 라고 부릅시다)가 나옵니다.
기존의 규칙에 따르면, 처음 3959개( $31 + 3928$ )의 숫자 안에 있는 VIP의 총합은 $10 + X$ 보다 작거나 같아야 합니다.

하지만 이바라가 계산했을 때, 그는 처음 3959개의 숫자 중에서 697명의 VIP를 찾아냈습니다.
그가 처음 31명($10 $)과 처음 **3928**명($ X$)의 VIP를 더했을 때, 그 값은 696이었습니다.

697은 696보다 큽니다.

파티의 중간 부분(구체적으로 3929에서 3959 사이의 구간)에 있는 VIP들이 너무나 밀집되어 있어서, 무려 11명의 새로운 손님을 채워 넣은 것입니다. 반면 파티의 첫 번째 구간(1에서 31까지)에는 10명뿐이었습니다. 이는 마치 입구 홀보다 파티룸 중간에 있는 비밀 VIP 라운지가 더 붐비는 것을 발견한 것과 같습니다.

이것은 단순한 추측이나 시뮬레이션이 아닙니다. 이 논문은 절대적인 확실성을 가지고 이를 증명합니다. 저자는 단순히 프로그램을 실행하고 요행을 바란 것이 아니라, 모든 논리적 단계를 점검하여 실수가 없도록 보장하는 매우 엄격한 심판 역할을 하는 Lean 4라는 형식 증명 시스템을 사용했습니다. 심판은 이 반례가 실재하며, 기존의 규칙이 확실히 틀렸음을 확인해주었습니다.

흥미롭게도, 코헨 자신은 나중에 자신의 컴퓨터 코드에 아주 작은 오류가 있었기 때문에 이 부분을 놓쳤음을 인정했습니다. 이제 코드가 수정되고 반례가 검증됨에 따라, 우리는 이 특별한 숫자들에 대한 '중복 계산 금지' 규칙이 성립하지 않는다는 것을 확실히 알게 되었습니다. 때로는 파티의 시작보다 중간이 훨씬 더 흥미진진할 수도 있다는 사실이 드러난 것입니다.

기술적 요약: 소피 제르맹 순환 수에 대한 코헨의 부가성 추측에 대한 반례

문제 정의
본 논문은 J. E. 코헨(J. E. Cohen)이 제안한 "소피 제르맹 순환(Sophie Germain cyclic)" 정수의 분포에 관한 추측을 다룬다. 정수 $n \ge 1$ 은 $\gcd(n, \phi(n)) = 1$ 일 때(즉, 모든 차수가 $n$ 인 군이 순환군일 때) **순환(cyclic)**적이라고 정의된다. $n$ 과 $2n+1$ 이 모두 순환적이면 $n$ 을 소피 제르맹 순환적이라고 한다. $C_\sigma(N)$ 을 구간 $[1, N]$ 내의 이러한 정수들에 대한 계수 함수(counting function)라고 하자.

코헨은 $C_\sigma$ 가 부가적(subadditive)이라고 추측했다. 구체적으로 모든 정수 $1 \le m \le n$ 에 대하여 다음이 성립한다는 것이다:
$C_\sigma(m + n) \le C_\sigma(m) + C_\sigma(n)$
이는 소수 계수 함수 $\pi$ 에 관한 두 번째 하디-리틀우드(Hardy–Littlewood) 추측의 순환적 유사 형태이다. 코헨은 반례를 찾지 못한 채 $m, n \le 10^6$ 범위에서 이 부등식을 검증했으나, 일반적인 타당성 여부는 미결로 남겨두었다.

방법론
저자는 다음과 같은 직접적인 계산 및 논리적 접근 방식을 사용하여 추측을 반증한다:

표적 탐색 (Targeted Search): 광범위한 탐색 대신, 저자는 초기 구간 $[1, m]$ 에서의 밀도보다 밀도가 높은 특정 창(window) $(m, m+n]$ 을 식별한다.
명시적 열거 (Explicit Enumeration): 증명은 특정 범위 내의 소피 제르맹 순환 정수의 유한한 열거에 의존한다. 저자는 $m=31$ 에 대한 정확한 개수를 계산하고, $n=3928$ 에서 시작하는 길이 31의 창(즉, 구간 $(3928, 3959]$ )을 식별한다.
형식적 검증 (Formal Verification): 결과는 mathlib 라이브러리를 사용하는 Lean 4 증명 보조기를 통해 검증된다. 형식화 과정에서는 Nat.Coprime n (Nat.totient n)을 통해 순환수를 정의하고 $C_\sigma$ 를 검증한다. 결정적으로, 이 증명은 native_decide와 같은 네이티브 결정 절차를 피하고 오직 표준 공리(propext, Classical.choice, Quot.sound)만을 사용하여 Lean 커널 자체에 의해 체크되므로, 결과가 계산적 산물이 아닌 정리(theorem)임을 보장한다.

주요 결과
본 논문은 코헨의 추측 66에 대한 구체적인 반례를 제공한다:

매개변수: $m = 31$ , $n = 3928$ .
계수:
- $C_\sigma(31) = 10$ (정수들: 1, 2, 3, 5, 7, 11, 15, 17, 23, 29).
- 구간 $(3928, 3959]$ 에는 11개의 소피 제르맹 순환 정수가 포함되어 있다: 3929, 3931, 3935, 3941, 3943, 3945, 3947, 3949, 3953, 3957, 3959.
- 따라서, $C_\sigma(3959) = C_\sigma(3928) + 11$ 이다.
부등식 위배:
$C_\sigma(3959) = C_\sigma(3928) + 11 > C_\sigma(3928) + 10 = C_\sigma(3928) + C_\sigma(31)$
따라서, $C_\sigma(31 + 3928) > C_\sigma(31) + C_\sigma(3928)$ 이 되어, 부가성 주장이 거짓임을 입증한다.

저자는 $C_\sigma(3928)$ 의 구체적인 값은 증명에 중요하지 않음을 언급한다. 증명은 오직 구간 $(3928, 3959]$ 가 $[1, 31]$ 보다 밀도가 높다는 사실에 기초한다.

의의 및 주장
논문은 다음과 같은 의의를 주장한다:

미해결 문제의 해결: 본 논문은 코헨의 추측 66이 거짓임을 확정적으로 증명하여, $10^6$ 까지의 탐색 후에도 열려 있었던 질문을 종결시킨다.
이전 연구의 수정: 저자는 코헨이 원래의 탐색에서 반례를 찾지 못한 이유가 그의 컴퓨터 코드 오류 때문이었음을 지적하며, 이는 본 논문의 결과에 따라 코헨 자신에 의해 확인되었다.
이론적 일관성: 소피 제르맹 순환 수에 대한 부가성 추측의 거짓은 소수(primes)에 관한 유사한 추측(하디-리틀우드) 또한 거짓일 것이며, 소수 $k$ -튜플 추측(prime $k$ -tuples conjecture)과 양립할 수 없다는 일반적인 믿음과 궤를 같이한다.
형식적 엄밀성: 결과는 Lean 4를 통한 형식적 검증으로 차별화되며, 반례가 코헨의 기존(오류가 있는) 탐색 범위( $m, n \le 10^6$ ) 내에 있음을 보여주는 커널 체크된 증명을 제공한다.

본 논문은 이러한 성격의 반례가 드문 것이 아니라고 결론짓지만, 이 특정 사례는 코헨의 원래(오류가 있는) 탐색 범위 내에 위치한다는 점에서 주목할 만하다.

유사한 논문