Mapping Uncharted Symmetries: Machine Discovery in Combinatorics

Motivation

• Known: 머신러닝을 활용해 수학적 대상(그래프, 대수적 불변량, Lyapunov function, bijection 후보 등)을 발견하거나 기존에 알려진 결과를 재발견하는 연구들이 존재하며, LLP(Learning from Label Proportions)와 program synthesis 역시 관련된 문제 설정을 다루어왔다.
• Gap: 기존 q,t-combinatorics 관련 ML 연구들은 이미 알려진 결과(zeta map 등)를 재도출하는 proof-of-concept 수준에 머물러 있었고, LLP나 program synthesis는 근사적 제약 만족이나 유한 도메인을 전제로 하여 무한 도메인에서 정확한 제약 만족과 검증 가능한 symbolic description을 요구하는 SLURP 설정과는 근본적으로 다르다.
• Why: 이 연구는 ML이 단순히 근사적 예측을 넘어 수학자가 실제로 활용할 수 있는 검증 가능한 새로운 수학적 발견(새로운 combinatorial statistic과 대칭성의 combinatorial proof)에 기여할 수 있음을 보여주며, 대수적 조합론에서 수십 년간 미해결이었던 exchanging bijection 구성 문제를 해결했다는 점에서 중요하다.
• Approach: 정확한 분포 제약 하에서 단순한 함수를 찾는 문제를 SLURP로 정식화하고, pseudo-labeling과 supervised training을 번갈아 수행하는 MapSeek-Functional과 population-based symbolic search를 수행하는 MapSeek-Symbolic 두 가지 방법을 제안하여 q,t-Narayana polynomials의 새로운 combinatorial interpretation을 탐색한다.

Achievement

Figure 6. A 12 × 7 polyomino with area 30 −18 = 12 (left) and its bounce path (right); the bounce statistic is equal to

1. SLURP 프레임워크 정식화: 대수적 조합론 문제에서 영감을 받아, 정확한 분포 제약(rigid proportion constraint) 하에서 단순한 함수를 찾는 문제를 새로운 학습 패러다임으로 형식화했다.
2. 두 가지 방법 제안: pseudo-labeling과 supervised training을 교대로 수행하는 MapSeek-Functional과, symbolic formula를 직접 탐색하는 population-based 방법인 MapSeek-Symbolic을 도입했다.
3. 새로운 combinatorial interpretation 발견: noncrossing partitions에 기반한 q,t-Narayana polynomials의 최초의 combinatorial interpretation을 발견했다 (Figure 1의 atlas).
4. 미해결 대칭성 문제 해결: skip과 leap statistic을 교환하는 explicit bijection을 구성하여 Nn,3(q,t)=Nn,3(t,q) 대칭성에 대한 combinatorial proof를 제시, Open Problem 4.1의 k=3 경우를 해결했다.
5. Lean 4 형식화 및 코드 공개: 발견한 모든 수학적 결과를 Lean 4로 형식화하고, MapSeek 코드, skip-pairing benchmark, Lean 4 formalization 전체를 공개하여 검증 및 재현성을 보장했다.

How

Figure 2. A SLURP instance: the domain X is partitioned into

• 도메인 X를 bag들로 분할하고 각 bag에 target distribution Di를 부여하는 SLURP 문제 설정을 정의 (rigid proportion constraint + simplicity requirement)
• MapSeek-Functional: 제약으로부터의 약한 지도(weak supervision)를 이용해 모델이 원하는 함수로 수렴하도록 pseudo-labeling 단계와 supervised update 단계를 반복 수행
• MapSeek-Symbolic: symbolic formula에 대한 population-based search를 수행하며, 후보를 반복적으로 생성·평가해 정확한 해를 탐색
• skip-pairing benchmark를 구축하여 q,t-Narayana polynomials Nn,3(q,t)의 interpretation 발견 문제에 두 방법을 적용
• 발견된 skip, leap 등의 statistic 쌍을 이용해 exchanging bijection을 구성하고 이를 Lean 4로 형식적으로 검증

Originality

• 기존 ML-for-math 연구가 대부분 이미 알려진 결과를 재발견하는 proof-of-concept에 그쳤던 것과 달리, 이 논문은 실제로 미지의 combinatorial statistic을 발견하고 이를 이용해 미해결 문제를 해결한 최초의 사례로 제시된다.
• SLURP이라는 새로운 학습 패러다임을 formalize하여 LLP, program synthesis와의 차별점을 명확히 제시했다.
• 서로 독립적인 두 방법(functional, symbolic)이 동일한 interpretation을 제안했다는 교차검증적 결과가 발견의 신뢰성을 높인다.

Limitation & Further Study

• 본 발췌문에는 MapSeek-Functional과 MapSeek-Symbolic의 구체적 알고리즘 세부사항, 성공률, 실패 사례에 대한 정량적 분석이 충분히 제시되지 않아 방법의 일반화 가능성을 판단하기 어렵다.
• 적용 사례가 q,t-Narayana polynomials의 k=3 경우 등 특정 조합론적 문제에 국한되어 있어, 다른 대수적 조합론 문제나 일반적인 SLURP 인스턴스에 대한 폭넓은 적용성이 추가로 검증될 필요가 있다.
• symbolic search나 pseudo-labeling 기반 방법이 더 복잡한 statistic이나 더 큰 k값에 대해서도 확장 가능한지에 대한 후속 연구가 필요하다.

Evaluation

총평: 머신러닝을 검증 가능한 순수 수학 발견의 도구로 사용한 인상적인 사례로, SLURP이라는 새로운 문제 정식화와 Lean 4를 통한 형식적 검증을 결합해 실제 미해결 문제를 해결했다는 점에서 학제간 연구의 모범적인 성과라 평가된다.