💻 computer science

Witness-split + window-cardinality refinement for $r_3(N)$ : Architecture, empirical results, and a structural hard pocket

본 논문은 증인 분할(witness-splitting), 윈도우 기수 가지치기(window-cardinality pruning), 그리고 하이브리드 SAT/MIP 솔버를 결합한 재현 가능한 계산 프레임워크를 제시하여 $r_3(212)$ 의 상한을 엄밀하게 조사하며, 대부분의 후보 44-세트를 성공적으로 제거하는 동시에 광범위한 검증 노력에도 불구하고 여전히 미해결 상태로 남아 있는 두 개의 저항성 구조적 사례를 격리한다.

원저자: Mehmet Ergezer

게시일 2026-06-04

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Mehmet Ergezer

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

당신이 1부터 212까지의 숫자들로 구성된 여행 가방에 가능한 한 많은 아이템을 채우려 한다고 상상해 보세요. 하지만 단 하나의 엄격한 규칙이 있습니다: 절대로 완벽한 등차수열 패턴을 형성하는 세 개의 아이템을 고를 수 없습니다.

예를 들어, 당신이 숫자 2를 골랐다면, 4와 6도 함께 고를 수 없습니다. 왜냐하면 2, 4, 6은 각각의 숫자가 이전 숫자보다 2씩 큰 패턴을 이루기 때문입니다. 이것을 "3항 등차수열(3-term arithmetic progression)"이라고 부릅니다.

수학자들은 이 규칙을 어기지 않으면서 가방에 담을 수 있는 아이템의 절대적인 최대 개수를 알아내기 위해 노력해 왔습니다. 가방 크기가 211일 때, 정답은 43으로 알려져 있습니다. 이 논문의 핵심 질문은 이것입니다: 가방 크기가 212일 때 44개의 아이템을 담을 수 있을까요?

저자인 메흐메트 에르게제르(Mehmet Ergezer)는 단순히 추측만 한 것이 아니라, 44가 불가능하다는 것을 증명하기 위해 거대한 디지털 공장을 건설했습니다. 이 논문의 전개 방식은 다음과 같은 쉬운 비유를 사용하여 설명됩니다.

1. 전략: "위트니스 분할(Witness Split)" 공장

212개 중 44개의 숫자를 조합하는 모든 경우의 수를 확인하는 것은 지구상의 모든 해변에서 특정한 모래알 하나를 찾는 것과 같습니다. 이는 컴퓨터 한 대가 처리하기에는 너무나 방대한 양입니다.

그래서 저자는 영리한 트릭을 사용했습니다:

위트니스(Witness): 그는 이미 작동함이 증명된 '안전한' 43개의 숫자 리스트에서 시작했습니다.
분할(Split): 그는 그 안전한 리스트에서 가장 "중요한" 24개의 숫자를 뽑아낸 뒤, 컴퓨터에게 이 숫자들에 대한 모든 가능한 "예/아니오" 시나리오를 체크하도록 요청했습니다.
결과: 이 방식은 불가능할 정도로 거대한 데이터의 산을 **1,250만 개의 작고 관리 가능한 덩어리(chunk)**로 나누었습니다. 그런 다음 컴퓨터는 각 덩어리를 하나씩 해결하려고 시도했습니다.

2. 도구: "윈도우(Window)"와 "정교화(Refinement)"

컴퓨터를 더 빠르게 만들기 위해 저자는 두 가지 특별한 도구를 추가했습니다:

윈도우 카드 (가지치기 도구): 여행 가방의 작은 구역을 들여다보는 창문을 상상해 보세요. 우리는 이미 이전 수학적 지식을 통해 크기가 50인 작은 창문에는 최대 10개의 아이템만 들어갈 수 있다는 것을 알고 있습니다. 컴퓨터는 이 규칙을 사용하여, 해당 창문에 11개의 아이템을 넣으려는 모든 덩어리를 즉시 폐기합니다. 이것은 가장 강력한 도구였으며, 까다로운 덩어리의 수를 거의 30% 줄였습니다.
정교화 (심층 탐구): 만약 어떤 덩어리가 60초 안에 해결되지 않는다면, 컴퓨터는 포기하지 않았습니다. 그 특정 까다로운 덩어리에 더 많은 규칙을 추가하고, 더 긴 시간 제한을 두어 다시 시도했습니다. 이것은 마치 잠긴 상자를 가져와서 특정 자물쇠를 따고, 더 큰 열쇠를 사용하여 다시 시도하는 것과 같습니다.

3. 결과: "하드 포켓(Hard Pocket)"

슈퍼컴퓨터 클러스터에서 수백만 번의 검사를 실행한 결과는 다음과 같습니다:

성공 사례 제로: 컴퓨터는 단 한 번도 44개의 아이템을 유효하게 담을 수 있는 방법을 찾아내지 못했습니다. 컴퓨터가 시도할 때마다 벽에 부딪히며 "불가능하다"라고 말했습니다.
증거: 이것은 44가 불가능하다는 강력한 증거이지만, 아직 공식적인 증명은 아닙니다. 왜냐하면 컴퓨터가 제시간에 끝내지 못한 몇몇 고집스러운 덩어리들이 남아 있기 때문입니다.

"하드 포켓" (저항하는 덩어리들):
수백만 개의 덩어리 중에서 저자는 추가 시간과 다른 도구들을 투입했음에도 불구하고 해결되지 않은 아주 작고 고집스러운 그룹인 45개의 덩어리를 발견했습니다.

LP 공격: 저자는 문제를 매끄러운 곡선처럼 바라보는 다른 유형의 수학 솔버(HiGHS라고 불리는)를 시도했습니다. 그러나 이 방법은 45개의 덩어리 중 어느 것도 해결하지 못했습니다.
CDCL 공격: 저자는 자신의 실수로부터 배우는 탐정처럼 작동하는 세 번째 솔버(CDCL)를 시도했습니다. 이 방식은 성공적이었습니다! 이 솔버는 45개 중 18개의 덩어리를 해결했습니다.
최종 2개: 하지만, 2개의 덩어리(T1c로 표시됨)가 여전히 미해결 상태로 남았습니다. 이들은 첫 번째 솔버, 두 번째 솔버, 그리고 세 번째 솔버 모두를 거부했습니다. 이들이 바로 이 문제의 "최종 보스"입니다.

4. 결론: "유닛 갭(Unit Gap)"

이 논문은 다음과 같이 결론짓습니다:

우리는 작동하는 43개의 숫자 리스트를 확보했습니다.
컴퓨터가 수백만 번 시도했음에도 실패했으므로, 44가 불가능하다는 강력한 증거가 있습니다.
하지만, 그 2개의 마지막 고집스러운 덩어리들 때문에 아직 100% 수학적 증명을 완성하지는 못했습니다. 정답은 거의 확실히 43이지만, 43과 44 사이의 "간극(gap)"은 기술적으로 여전히 열려 있습니다.

5. 커뮤니티를 향한 선물

저자는 단순히 "포기한다"라고 말하는 대신, 모든 데이터를 공개합니다. 그는 2개의 고집스러운 덩어리를 세상에 도전 과제로 던집니다.

그는 다른 수학자들이 오직 이 두 개의 덩어리만을 해결할 수 있도록 정확한 코드와 데이터를 제공합니다.
심지어 이 문제를 형식 증명 시스템(Lean)을 위한 언어로 번역하여, 컴퓨터 과학자들이 논리 엔진을 사용하여 이를 증명해 볼 수 있도록 초대했습니다.

요약하자면: 저자는 패턴 없이 숫자를 채우는 기록을 깨기 위해 거대한 디지털 기계를 만들었습니다. 그 기계는 기록을 깨는 방법을 찾는 데 실패했지만, 매우 어렵고 작은 두 개의 퍼즐에서 멈춰 섰습니다. 이 논문은 이렇게 말합니다. "우리는 정답이 43이라고 99.9% 확신하지만, 이를 증명하기 위해 풀어야 할 두 개의 최종 퍼즐을 여기 남겨둡니다."

기술 요약: $r_3(212)$ 에 대한 Witness-Split + Window-Cardinality 정밀화

문제 정의
본 논문은 $N$ 에 대해 $[1, N]$ 내의 비자명한 3-항 등차수열(3-AP)을 포함하지 않는 부분집합의 최대 크기로 정의되는 $r_3(N)$ 의 정확한 계산을 다룬다. 점근적 거동(예: Roth의 정리, Kelley–Meka)은 잘 연구되어 있으나, 본 연구의 초점은 $N=212$ 라는 유한한 경계면에 있다. OEIS A003002에 따르면, $r_3(211) = 43$ 이다. 저자들은 결정 문제(decision problem)인 * $[1, 212]$ 내에 44개의 원소를 가진 3-AP-free 부분집합이 존재하는가?*를 조사한다.
저자들은 43개 원소의 witness를 독립적으로 검증하여 $r_3(212) \ge 43$ 임을 확립했다. 상한(upper-bound)에 대한 질문은 $r_3(212) \le 43$ 인지 여부이다. 가상의 44-set에 대한 필요조건은 해당 집합이 반드시 양 끝점인 1과 212를 포함해야 한다는 것이다. 그렇지 않으면 이는 $[1, 211]$ 내의 44-set으로 변환되어 알려진 값과 모순되기 때문이다. 따라서 문제는 $\{1, 212\}$ 를 포함하는 44-set의 불가능성을 증명하는 것으로 귀결된다.

방법론 및 아키텍처
저자들은 실행 가능한 44-set을 탐색하기 위해 다섯 가지 구성 요소를 결합한 재현 가능한 계산 프레임워크를 제안한다:

결정형 CP-SAT 모델: 문제는 $i \in [1, 212]$ 에 대한 불리언 변수 $x_i$ 를 사용하여 인코딩된다. 제약 조건에는 다음이 포함된다:
- 3-AP 부등식: 모든 3-AP를 형성하는 트리플 $(a, b, c)$ 에 대해 $x_a + x_b + x_c \le 2$ .
- Cardinality 등식: $\sum x_i = 44$ (부등식보다 전파(propagation)에 더 강력함).
- Endpoint forcing: $x_1 = x_{212} = 1$ .
- Symmetry breaking: 반사 대칭을 제거하기 위한 렉시코그래피 순서 지정.
Witness-Splitting: 탐색 공간을 관리하기 위해, 저자들은 검증된 43개 원소의 witness $A_{43}$ 를 사용한다. 이들은 $A_{43}$ 의 원소들을 AP-incidence degree(AP 출현 차수)에 따라 정렬하고 상위 24개를 선택한다. 탐색 공간은 이 24개 변수의 값을 고정함으로써 $2^{24}$ 개의 "청크(chunks)"로 분할된다. 고정된 접두사(prefix)가 3-AP를 강제하는 경우 많은 청크들이 즉시 가지치기(pruning)된다.
Window-Cardinality Pruning: 유효한 부등식을 추가하는 핵심적인 개입 단계로, OEIS A003002로부터 유도된 window-cardinality 부등식을 사용한다. 임의의 윈도우 $[a, a+L-1]$ 에 대해, 변수의 합은 $r_3(L)$ 에 의해 제한된다. $N=212$ 인 경우, 이는 22,154개의 부등식을 추가하며, 이는 가공되지 않은 raw 3-AP 제약 조건보다 모델을 크게 강화한다.
재귀적 정밀화 (Recursive Refinement): 광역 레이어(depth 24)에서 UNKNOWN을 반환하는 청크들은, 가장 높은 degree를 가진 witness 변수들로 고정 접두사를 확장함으로써(depth 40, 48, 56, 64) 정밀화되며, 더 긴 시간 제한(time cap)과 함께 재해결된다.
솔버 다양성 및 엔지니어링: 이 캠페인은 UMass Unity 클러스터에서 실행되는 SLURM 기반 파이프라인을 활용한다. 다음을 채택한다:
- CP-SAT (OR-Tools): 광역 패스 및 재귀적 정밀화를 위해 사용.
- HiGHS (MIP): 가장 어려운 "UNKNOWN" 청크들을 공격하기 위해 사용되는 LP-relaxation 기반 솔버.
- CDCL/SAT (CaDiCaL): LP 방식에 저항하는 청크들을 재공격하기 위해 사용되며, 불만족성(unsatisfiability)에 대한 DRAT 증명을 생성한다.

실험 결과
캠페인은 depth-24 스윕과 다양한 정밀화 단계에 걸쳐 수백만 개의 하위 문제를 처리했다.

가용 해(Feasible Solution) 제로: 테스트된 모든 하위 문제(광역 패스, 정밀화, HiGHS, CDCL) 전반에 걸쳐, 0개의 가용 44-set이 발견되었다. 이는 $r_3(212) = 43$ 이라는 추측에 대한 강력한 경험적 지지를 제공하지만, 공식적인 증명은 아니다.
Window-Cardinality의 영향: Window-cardinality 부등식을 활성화하면 광역 패스에서의 UNKNOWN 비율이 약 28 퍼센트 포인트 감소하였다(예: 제어된 배치에서 ~30%에서 ~1.65%로 감소). 이는 가장 효과적인 가지치기 레이어임을 보여준다.
구조적 난관 영역 (The Structural Hard Pocket):
- 100,000개 청크 확장 배치 중 6,071개 청크가 UNKNOWN을 반환했다.
- 이들 중 무작위 샘플에 대한 300초 재캡(recap) 결과, 45개의 저항적인 청크(Tier T1)가 남았다.
- HiGHS 공격: 1시간 동안의 HiGHS 실행은 0/45를 해결했다. 8시간의 감사(audit)는 25/45를 해결하여, 20개의 청크(Tier T1b)를 남겼으며, 이들의 dual bound가 0.0에 고정되어 LP relaxation이 불만족성의 증명을 제공하지 못함을 나타냈다.
- CDCL 공격: 20개의 T1b 청크에 대한 순수 CDCL/SAT 공격은 18/20을 해결하였고, 독립적으로 검증된 DRAT 증명을 생성했다.
- 잔여물 (T1c): 두 개의 청크(ID 40959 및 48895)는 관대한 시간 제한을 둔 12시간의 순수 CDCL 실행과 4시간의 windowed CDCL 진단 후에도 UNKNOWN 상태로 남았다. 이 두 청크는 CP-SAT, HiGHS (LP-MIP), 그리고 CDCL 패러다임 모두에 저항한다.

주요 기여
본 논문은 자신의 기여를 $r_3(212)$ 의 새로운 정확한 값이 아니라 방법론적인 것으로 명시적으로 규정한다. 구체적인 기여는 다음과 같다:

아키텍처: Witness-splitting, window-cardinality pruning, 그리고 재귀적 정밀화를 결합한 재현 가능한 exact upper-bound 탐색 프레임워크.
경험적 기록: 솔버 간의 트레이드오프와 탐색 공간의 비균질성(예: 특정 pin assignment를 가진 "middle-out" 청크가 훨씬 더 어렵다는 점)을 포함한 $N=212, K=44$ 캠페인에 대한 상세한 분석.
난관 영역의 특성화: 관대한 시간 제한 하에서도 CP-SAT, HiGHS, CDCD 패러다임 전반에 걸쳐 불변하는 구조적 장애물(T1c)의 식별.
벤치마크 릴리스: 계층화된 인스턴스 릴리스:
- T1a: HiGHS에 의해 해결된 25개 청크.
- T1b \ T1c: DRAT 증명과 함께 CDCL로 해결된 18개 청크.
- T1c: 마지막으로 남은 2개의 저항적인 청크로, 가장 날카로운 미해결 문제로 제시됨.
- T2/T3: 6,071개의 광역 UNKNOWN들과 향후 시도를 위한 전체 12.5M 청크 생성기.
정형화: 공식 증명 시스템을 위한 T1c 타겟의 Lean 4 인코딩.

의의 및 주장
저자들은 캠페인이 $r_3(212) = 43$ 이라는 추측을 강력하게 뒷받침하지만, 해결되지 않은 T1c 잔여물 때문에 공식적인 증명은 되지 못한다고 겸허히 주장한다. 그 의의는 구체적인 계산적 장벽을 격리하는 데 있다:

인증된 경계 사이의 간격은 정확히 1이다 ( $43 \le r_3(212) \le 44$ ).
LP 기반 방법(HiGHS)의 실패와 CDCL의 부분적 성공은, 이 어려움이 단순히 전파(propagation)의 산물이 아니라, LP relaxation gap이 타이트하고 정수 불만족성 증명이 조합론적으로 확산되어 있는 구조적 특성임을 시사한다.
본 논문은 이 간극을 메우기 위해서는 더 강력한 가법 조합론적 경계(예: 푸리에 해석적 또는 다중 윈도우 분할 경계)나, 일반 목적의 솔버가 포착하지 못하는 문제 특유의 대칭성을 활용하는 커스텀 branch-and-bound 시스템이 필요하다고 상정한다.

본 연구는 일반 목적의 조합 최적화 솔버가 이 부류의 문제에서 도달할 수 있는 현재의 한계를 나타내는 벤치마크로서 커뮤니티에 기여한다.