Counterexample to Majority Optimality in NICD with Erasures

Motivation

• Known: Boolean function analysis에서 NICD(Non-Interactive Correlation Distillation) with erasures 문제는 p<1/2일 때 unbiased Boolean function 중 majority function이 Φp(f)=E|f(z)|를 최대화한다고 추측되어온 오래된 open question이며, p≥1/2에서는 dictator function이 최적임이 알려져 있다. 유사한 "Majority is Least Stable" conjecture(L2 norm 버전)는 이미 Gopi, Jain, Biswas-Sarkar 등에 의해 linear threshold function 반례가 발견되어 반증되었다.
• Gap: 기존의 L2 norm(noise stability) 기반 반례들이 NICD의 L1 norm(Φp) 버전에서도 성립하는지는 검증되지 않았으며, L1 norm 비교는 orthogonality가 없어 L2보다 훨씬 다루기 어려워 지금까지 아무도 이 조합을 시도하지 않았다. 즉 p<1/2에서 majority optimality가 실제로 성립하는지는 미해결 상태였다.
• Why: 이 연구는 LLM(GPT-5 Pro)이 수십 년 된 이론computer science 공개문제에 실질적인 finite counterexample을 제시한 최초의 공개 보고 사례로 제시되며, AI가 단순 문헌 탐색이나 수치 실험을 넘어 구체적 반증에 기여할 수 있음을 보여주는 사례 연구로서 의미가 있다.
• Approach: GPT-5 Pro에게 Simons Institute의 공개문제 목록에서 반례를 찾도록 요청하여 수치 실험을 통해 5비트 linear threshold function 반례를 발견했고, 저자들은 이를 명시적 multilinear expansion과 손계산으로 엄밀히 검증했다.

Achievement

1. 반례 발견 및 검증: n=5, p=0.40에서 f(x)=sgn(x1-3x2+x3-x4+3x5)가 Φ0.40(f)=2689/6250=0.43024 > Φ0.40(Maj5)=5363/12500=0.42904를 만족함을 손으로 단계별로 증명, majority function이 p<1/2에서 항상 최적이라는 추측을 반증했다.
2. 함수의 구조 분석: 반례 f가 Maj3(-x2, x5, Maj3(x1,x3,-x4)) 형태로 분해되며, "Majority is Least Stable" 문제에서 알려진 Gopi/Jain의 반례와 순열·부호반전을 제외하면 동일한 "two heavy + three light" LTF 구조임을 밝혔다.
3. 국소 최적성 증명: 고정된 홀수 n에 대해 p=0 근방에서는 majority function이 unbiased Boolean function 중 유일한 최대화자임을 Fourier 계수 부등식(Lemma 5, 6)을 이용해 엄밀히 증명, 반례가 p=0 근방에서는 존재할 수 없음을 보였다.

How

• GPT-5 Pro에게 공개문제 리스트(Simons "Real Analysis in Computer Science" collection)를 대상으로 반례를 찾도록 요청, 여러 차례의 수치 실험(brute-force search 포함)을 거쳐 후보 함수를 도출
• 후보 함수 f와 Maj5의 multilinear polynomial extension을 명시적으로 전개 (Fourier-Walsh 계수 이용)
• erasure model 하에서 K=#{i:zi≠0}~Bin(n,p)로 조건화하여 각 K값에 대한 조건부 기댓값 E[|f(z)||K=k]를 계산, 이를 합산해 Φp(f)와 Φp(Maj5)를 다항식으로 명시적 도출 및 p=0.40 대입 비교
• p=0 근방 최적성 증명을 위해 Φp(f)를 p·Σ|f̂(i)| 항과 O(p²) 오차항으로 전개하는 부등식(Lemma 5)을 유도하고, 홀수 n에서 majority가 Σf̂(i)를 유일하게 최대화한다는 기존 정리(Lemma 6, O'Donnell 2021)를 결합해 국소 유일 최적성(Theorem 7)을 증명

Originality

• 오래된 이론computer science 공개문제(NICD with erasures majority optimality)에 대한 최초의 명시적 finite counterexample 제시
• L2 norm 기반 "Majority is Least Stable" 반례(Gopi, Jain)와 L1 norm 기반 NICD 문제 사이의 구조적 연결(동일한 LTF 패턴)을 처음으로 지적
• AI(LLM)가 수치 실험을 통해 구체적이고 검증 가능한 반례를 finite computer-science open problem에서 제시한 사례를 공개 문서화하여, AI-for-Math 워크숍 맥락에서 "AI 기여의 스파크"라는 메타적 관찰을 제공

Limitation & Further Study

• 반례는 n=5, p=0.40의 특정 경우에 국한되며, 일반적인 n과 p 범위에 대해 majority optimality가 어디까지 성립/붕괴하는지에 대한 전반적 구조는 밝혀지지 않음
• p0(n)의 명시적 크기나 최적 함수가 majority에서 다른 함수로 전이되는 정확한 임계 p값에 대한 분석이 부재
• GPT-5 Pro의 반례 발견 과정 자체가 brute-force 수치 탐색에 의존했다는 점에서, 진정한 "이론적 통찰"이라기보다는 계산 능력의 활용에 가까울 수 있어 AI 기여의 성격에 대한 평가가 제한적
• 후속 연구로 다른 p 값 및 더 큰 n에 대한 체계적 탐색, majority에서 전이되는 최적 함수 family의 분류가 필요

Evaluation

총평: 짧지만 명확한 노트로, 오래된 공개문제에 대한 구체적 반례를 손으로 검증 가능하게 제시한 점과 AI가 finite counterexample 발견에 기여한 사례를 투명하게 기록한 점이 인상적이나, 결과의 범위가 매우 국한적(n=5, p=0.40)이어서 이론적 기여의 폭은 제한적이다.