Kernel-Checked Exclusions for the Erdős-Selfridge Odd Covering Problem: Any Odd Covering of ℤ Has lcm Exceeding 10000

정수(1, 2, 3과 같은 자연수)를 양방향으로 끝없이 뻗어 있는 무한한 고속도로라고 상상해 보십시오. 수학의 세계에는 이 고속도로를 '덮는(covering)' 것에 관한 매혹적인 퍼즐이 있습니다. '커버링 시스템(covering system)'은 마치 특정 지점에 배치되어 특정 순찰 패턴을 부여받은 보안 요원들의 팀과 같습니다. 예를 들어, 어떤 요원은 매 2번째 집을 확인하고, 다른 요원은 매 3번째 집을, 또 다른 요원은 매 4번째 집을 확인합니다. 이들을 적절히 배치하면, 그들의 순찰 경로가 서로 겹치면서 무한한 고속도로 위의 모든 집을 적어도 한 번은 방문하게 됩니다. 수학자들은 수십 년 전부터 이것이 가능하다는 것을 알고 있었지만, 여기에는 함정이 하나 있습니다. 알려진 모든 사례에서 적어도 한 명의 보안 요원은 '짝수' 순찰 패턴(예를 들어 매 2번째 또는 4번째 집을 확인하는 것)을 가지고 있었습니다.

이는 70년 넘게 수학자들을 괴롭혀온 끈질긴 질문으로 이어집니다. 만약 서로 다른 순찰 패턴 크기를 가진 '홀수' 순찰 패턴(매 3번째, 5번째, 7번째 등)만을 사용하여 전체 고속도로를 덮는 것이 가능할까요? 이것은 에르되시-셀리시(Erdős–Selfridge)의 홀수 커버링 문제입니다. 이는 마치 홀수 모양의 타일만을 사용하여 바닥을 채울 수 있는지, 단 하나의 짝수 모양 타일도 사용하지 않고 가능한지를 묻는 것과 같습니다. 최종적인 답은 아직 알 수 없지만, 이 새로운 논문은 마치 매우 정밀하고 로봇에게 검증받은 조사관처럼 행동합니다. 이 논문이 문제 전체를 해결하는 것은 아니지만, 만약 그러한 기묘한 '전부 홀수인' 커서링 시스템이 존재한다면, 그 숫자들이 믿기 힘들 정도로 커야 한다는 것을 확실하게 증명해 냅니다. 이는 이전에 컴퓨터를 통해 배제할 수 있었던 범위보다 훨씬 더 큰 숫자입니다.

이 논문의 발견: 로봇이 검증한 제외 구역

이브라힘 미안(Ibrahim Mian)과 샤얀 시디크(Shayaan Siddique)가 작성한 이 논문은 홀수 커버링 문제에 대한 해답을 제시한다고 주장하는 것이 아닙니다. 대신, 이들은 어떤 잠재적인 해법이라도 10,000보다 훨씬 더 커야 함을 증명하기 위해 '디지털 요새'를 구축했습니다. 이 문제를 숫자로 이루어진 조합을 가진 거대한 자물쇠라고 생각해 보십시오. 저자들은 "조합이 945나 1,200처럼 작은 숫자일 수도 있을까?"라는 의문을 가졌습니다. 그들의 대답은 확고한 "아니오"였습니다. 하지만 아주 특별한 반전이 있었습니다. 그들은 단순히 계산기를 사용한 것이 아니라, 수학적 로봇(Lean 4라고 불리는 컴퓨터 프로그램)을 사용하여 논리의 모든 단계를 점검함으로써 인간의 오류나 숨겨진 가정이 끼어들 틈이 없도록 했습니다.

그들이 이 일을 수행한 방법은 다음과 같은 몇 가지 창의적인 비유를 통해 설명할 수 있습니다.

1. 밀도 함정 (군중 세기)
먼저, 저자들은 보안 요원들의 '밀도'를 살펴보았습니다. 서로 다른 홀수 순찰 크기를 가진 보안 요원 그룹이 있다면, 그들이 도로를 얼마나 덮는지 계산할 수 있습니다. 만약 그들이 '모든 곳'을 덮으려면, 그들의 결합된 커버리지는 100%가 되어야 합니다. 수학적으로 이것이 홀수로 이루어지려면, '최소공배수(LCM)'—즉, 패턴이 다시 시작되기 전까지의 전체 반복 길이—가 '과잉수(abundant number)'라는 매우 특별한 종류의 숫자여야 합니다. 과잉수란 자신의 약수들의 합이 자기 자신보다 큰 숫자를 말합니다. 이는 마치 어떤 숫자가 너무 인기가 많아서, 그 친구들의 합이 숫자 자체보다 더 큰 것과 같습니다.

2. 바닥 체크 (945의 장벽)
저자들은 가장 작은 홀수 과잉수가 945라는 것을 증명했습니다. 이는 만약 전부 홀수인 커버링 시스템이 존재한다면, 그 패턴의 길이는 반드시 945 이상이어야 함을 의미합니다. 이보다 작은 숫자는 수학적으로 불가능합니다. 이것은 그들이 사다리의 첫 번째 칸을 올린 것이며, 이 사실은 약 80초 동안 눈 한 번 깜빡이지 않고 수행된 순수한 계산 과정을 통해 검증되었습니다.

3. 용량 인증서 (중첩 테스트)
여기서 마법이 일어납니다. 숫자들이 '과잉수'라는 것을 아는 것만으로는 충분하지 않습니다. 보안 요원들이 틈 없이 실제로 잘 맞물리는지도 확인해야 합니다. 저자들은 '용량 인증서(capacity certificates)'를 만들었습니다. 퍼즐 조각들을 상자에 끼워 맞추는 것을 상상해 보십시오. 조각들이 이론적으로는 맞을 것 같아 보여도, 때로는 너무 많이 겹치거나 아주 작은 구멍을 남길 수도 있습니다. 저자들은 10,000 미만의 모든 홀수 과잉수에 대해 특정한 테스트를 작성했습니다. 그들은 이렇게 물었습니다: "만약 우리가 이 특정 홀수들을 사용하여 커버링 시스템을 만들려고 한다면, 보안 요원들 사이의 틈이 메우기엔 너무 커지지 않을까?"

10,000 미만의 모든 홀수 과잉수(정확히 23개)에 대해 테스트를 수행한 결과, 결과는 "아니오, 불가능합니다"였습니다. 틈이 너무 컸거나, 중첩이 너무 지저분했습니다. 컴퓨터는 이 23개의 숫자에 대해 모두 확인하여, 그 어떤 것도 비밀스러운 조합이 될 수 없음을 증명했습니다.

4. 최종 판결 (10,000의 한계)
이 단계들을 결합하여, 저자들은 핵심적인 정리(headline theorem)를 입증했습니다: 1보다 큰 서로 다른 홀수 모듈라이(moduli)를 사용하는 정수의 커버링 시스템은 반드시 10,000보다 큰 최소공배수(LCM)를 가져야 한다.

더 쉽게 말하면, 만약 누군가가 홀수 순찰 패턴만을 사용하여 무한한 고속도로를 덮는 방법을 찾아냈다고 주장한다면, 그 패턴이 10,000단계 이내에서 반복된다면 그 사람은 거짓말을 하고 있는 것입니다. 패턴은 반드시 10,000보다 길어야 합니다.

이것이 왜 중요한가 (최종 해답이 아닐지라도)

"그래서 뭐? 그냥 숫자가 10,000보다 커야 한다는 것을 증명했을 뿐인데. 이미 알고 있던 사실 아닌가?"라고 의문을 가질 수도 있습니다. 저자들은 매우 솔직합니다. 그들은 문제 전체를 해결한 것이 아닙니다. 실제 답은 100,000이나 10억 같은 숫자일 수도 있습니다. 그러나 그들이 이 일을 해낸 '방식'이 바로 진정한 돌파구입니다.

보통 수학자들이 컴퓨터를 사용하여 거대한 숫자 목록을 확인할 때, 그들은 버그나 숨겨진 가정이 있을 수 있는 '블랙박스' 소프트웨어에 의존합니다. 하지만 이 논문은 다릅니다. 그들은 자신의 모든 논증을 '증명 커널(proof kernel)'—즉, 모든 논리적 단계를 편집증적인 회계사처럼 점검하는 아주 작고 신뢰할 수 있는 컴퓨터 프로그램의 핵심부—안에 구축했습니다. 그들은 어떤 '마법 같은' 지름길이나 검증되지 않은 코드를 사용하지 않았습니다. 심지어 그들은 고전적인 12단계 커버링 시스템과 같은 알려진 사례를 통해 자신들의 컴퓨터 코드가 제대로 작동하는지 테스트함으로써, 코드가 실제로 가능한 상황에서 실수로 '불가능'하다고 말하지 않는다는 것까지 증명했습니다.

또한 그들은 무한한 정수의 세계와 유한한 컴퓨터 체크의 세계를 연결하는 가교를 만들었습니다. 이는 향로, 만약 누군가가 해법을 찾기 위해 슈퍼컴퓨터 탐색을 수행한다면, 이 논문이 컴퓨터를 맹목적으로 믿지 않고도 그 결과를 검증할 수 있는 방법을 제공한다는 것을 의미합니다.

결론

이 논문은 '작은' 홀수 커버링 시스템의 가능성을 배제합니다. 이 논문은 이렇게 말합니다. "만약 답이 존재한다면, 그것은 10,000 너머 어딘가에 숨어 있다." 답이 어디에 있는지는 알려주지 않지만, 10,000 미만의 숫자 구역을 그 누구도 혼자서는 결코 달성할 수 없는 확실한 수준으로 깨끗이 정리해 두었습니다. 이는 미래의 발견들을 검증할 수 있는 흔들림 없는 도구를 갖춘 채, 큰 숫자들을 향한 미스터리를 열어둔 채로, 작은 숫자들에 대한 엄격하고 로봇에 의해 검증된 "아니오"라는 답변입니다.