기술 요약: 수론적 변환(Number Theoretic Transform)에 대한 불확실성 원리

1. 문제 정의 및 동기

본 논문은 지수 함수를 포함하는 식에 대한 다항식 항등식 검사(Polynomial Identity Testing, PIT) 문제를 다루며, 이는 최근 Li와 Wu [LW26]에 의해 공식화된 영역이다. 이 설정에서, $P(x) = \sum_{j=1}^k f_j(x) \exp(g_j(x)/h_j(x))$ 형태의 식이 항등적으로 0인지 여부를 판별해야 한다.

이러한 형태의 식을 유한체 위에서 테스트할 때의 핵심 과제는 건전한 평가 모델(evaluation model)을 정의하는 것이다. Li와 Wu는 두 소수 $p$와 $q$ (여기서 $p \equiv 1 \pmod q$)를 사용하여, $\mathbb{F}_p^*$ 내의 유일한 $q$ 차 부분군을 통해 지수 함수를 해석하는 모델을 제안했다. 그러나 이들의 건전성 오차(soundness error, 0이 아닌 다항식을 수락할 확률)에 대한 분석은 $q^{-1/(k-1)} + O(dk^2/q)$라는 경계값을 산출했다. $q = k^{O(1)}$인 실용적인 영역에서 이 오차는 1에 근접하게 되어, 테스트를 무효하게 만든다.

Li와 Wu는 이러한 낮은 건전성이 유한체 상의 수론적 변환(NTT)에 대한 **불확실성 원리(uncertainty principles)**의 부재와 관련이 있다고 추측했다. 구체적으로, 그들은 희소한(sparse) 다항식이 부분군 $G$ 내에서 너무 많은 근을 가질 수 없다고 추측했다. 본 논문의 저자들은 항등식 검사의 건전성을 개선하기 위해 이러한 불확실성 원리를 증명하는 것을 목표로 한다.

2. 방법론 및 기술적 접근

저자들은 벡터 $f$의 희소성과 그 NTT인 $\hat{f}$의 희소성 사이의 관계를 조사한다. 이들은 서포트 크기 $|\text{Supp}(f)|$를 0이 아닌 좌표의 개수로 정의한다. 목표는 $|\text{Supp}(f)| + |\text{Supp}(\hat{f})|$의 하한을 설정하는 것이다.

2.1 하이퍼 역변환성(Hyperinvertibility)을 통한 가법적 불확실성

첫 번째 접근 방식은 복소 이산 푸리에 변환(DFT)에 대한 Tao [Tao05]의 전략을 응용한다. 복소수 설정에서 DFT 행렬은 "하이퍼 역변환 가능(hyperinvertible)"하며(모든 정사각 부분 행렬이 가역적임), 이는 강한 가법적 불확실성 $|\text{Supp}(f)| + |\text{Supp}(\hat{f})| \ge q + 1$을 함의한다.

저자들은 이 성질이 일반적인 유한체에서는 실패한다는 점에 주목한다(Zhang [Zha19]에 의해 입증됨). 그러나 그들은 고정된 소수 $q$에 대하여, NTT 행렬의 하이퍼 역변환 가능성이 $p \equiv 1 \pmod q$를 만족하는 거의 모든 소수 $p$에 대해 성립함을 증명한다.

• 증명 기법: 저자들은 다항식의 **결과식(resultant)**을 활용한다. 푸리에 행렬의 임의의 정사각 부분 행렬에 대해, 그 행렬식(determinant)이 원시 $q$제곱근에서 0이 아닌 $D_{R,C}(z)$라는 다항식을 구성한다(복소수 결과에 의해). 만약 어떤 부분 행렬이 모듈로 $p$에서 특이(singular)해진다면, $p$는 $D_{R,C}(z)$와 원분 다항식 $\Phi_q(z)$의 결과식의 약수여야 함을 보인다. 결과식은 0이 아닌 정수이므로 유한한 수의 소수 약수만을 가지며, 이를 통해 "나쁜" 소수 $p$를 제한한다.

2.2 다항식 영역을 위한 근사적 불확실성

위의 가법적 불확실성 결과는 $p$가 매우 커야 한다는 조건($p \approx q^{q^2}$)이 있어, $p = q^{O(1)}$인 실제 응용 분야에서는 비실용적이다. 이를 해결하기 위해 저자들은 확률적(근사적) 불확실성 원리를 증명한다.

• 영역: 저자들은 $P(q) = \{p \le q^4 : p \text{는 소수}, p \equiv 1 \pmod q\}$ 구간에서 균등하게 샘플링된 $p$를 고려한다.
• 증명 기법: 희소한 정수 다항식 $f$를 고정하고, 무작위 소수 $p$에 대해 $f$가 원시 $q$제곱근에서 0이 될 확률을 분석한다.
  • 만약 $f$가 그러한 근에서 0이 된다면, $p$는 $\text{Res}(f, \Phi_q)$를 나누어야 한다.
  • Poisson의 곱 공식을 사용하여, 이 결과식의 크기를 $\|f\|_1^{q-1}$로 제한한다.
  • 이는 불확실성 원리가 실패하는 "나쁜" 소수 $p$의 개수가 최대 $(q-1)\log_2 \|f\|_1$개임을 의미한다.
  • Bombieri–Vinogradov 정리를 인용하여, 무수히 많은 $q$에 대해 집합 $P(q)$가 충분히 커서($|P(q)| \ge q^3 / (32 \log q)$) 나쁜 소수의 밀도가 무시할 수 있는 수준임을 보인다.

3. 주요 기여 및 결과

3.1 강한 가법적 불확실성 (Theorem 1.1 / Theorem 3.1)

모든 고정된 소수 $q$와 $p \equiv 1 \pmod q$를 만족하는 거의 모든 소수 $p$에 대하여, 모든 0이 아닌 $f \in \mathbb{F}_p^{\mathbb{Z}_q}$는 다음을 만족한다:
$$|\text{Supp}(f)| + |\text{Supp}(\hat{f})| \ge q + 1$$
이는 $k$-희소 함수가 최소 $q - k + 1$의 변환 서포트를 가짐을 의미한다. 이 결과는 $p$가 $q$에 비해 충분히 빠르게 성장할 때 유효한, Li-Wu 추측의 비균등 버전(non-uniform version)을 제공한다.

3.2 근사적 불확실성 (Theorem 1.2 / Theorem 3.6)

무수히 많은 소수 $q$에 대하여, $|\text{Supp}(c)| < q$이고 $\ell_1$-노름이 $W$인 임의의 0이 아닌 정수 벡터 $c$에 대해, 무작위 소수 $p \in P(q)$에 대한 역 NTT의 기대 서포트 크기는 다음과 같다:
$$\mathbb{E}_p [|\text{Supp}(\hat{c})|] \ge q - 1 - \frac{32(q-1)\log q}{q^2} \log_2 W$$
이 결과는 $p$가 $q$에 대해 다항식적으로 제한되는 실용적인 영역에서도 성립한다.

3.3 개선된 항등식 검사 (Theorem 1.3 / Theorem 4.3)

저자들은 이러한 원리들을 적용하여 $k$-희소 지수 다항식(계수의 높이 $w$ 포함)을 위한 수정된 블랙박스 항등식 검사를 구축한다.

• 수정 사항: 표준적인 무작위 평가 지점들과 더불어, 구간 $P(q)$에서 소수 $p$를 무작위로 샘플링한다.
• 건전성 경계: 만약 $P \not\equiv 0$라면, 수락 확률은 다음과 같이 제한된다:
  $$O\left(\frac{dk^2}{q}\right) + O\left(\frac{1}{q}\right) + O\left(\frac{\log(kw)\log q}{q^2}\right)$$
• 의의: 만약 $q = k^C$ ($C > 2$)이고 $kw$가 다항식적으로 제한된다면, 건전성 오차는$o(1)$이 된다(구체적으로$q$가 커짐에 따라 0으로 수렴한다). 이는 동일한 파라미터 설정에서 오차가 1에 가까워졌던 Li-Wu의 경계보다 직접적인 개선이다.

4. 의의 및 주장

본 논문은 주요 기여가 항등식 검사의 건전성을 증명하는 데 필요한 가법적 불확실성 원리를 확립하는 것임을 주장한다. 저자들은 표준적인 곱셈적 불확실성 원리(Donoho–Stark)가 이 목적에는 불충분하다고 명시적으로 밝힌다.

본 연구의 의의는 다음과 같다:

1. 추측의 해결: NTT에 대한 강한 불확실성 원리를 특정 영역에서 공식적으로 증명함으로써, Li와 Wu의 추측에 대한 직관을 검증하였다.
2. 알고리즘적 개선: 소수 모듈러스 $p$의 선택을 무작위화함으로써, 지수 다항식의 항등식 검사에서 상수 건전성 오차를 달성할 수 있음을 보여주었다. 이는 기존에 실용적인 파라미터 설정에서 높은 오차율을 가질 것으로 생각되었던 작업이다.
3. 이론적 가교: 결과식(resultant)과 원분 다항식의 대수적 성질을 유한체 상의 변환의 희소성 속성과 연결하였다.

저자들은 자신들의 가장 강력한 결과(Theorem 3.1)가 "거의 모든" 소수에 적용되는 "비균등적" 성격을 띠고 있음을 인정하며 겸손한 태도를 유지하며, 실질적인 응용을 위해 확률적 결과(Theorem 3.6)에 의존한다. 그들은 모든 지수 표현에 대한 일반적인 PIT 문제를 해결하려는 것이 아니라, 응용 섹션에서 정의된 특정 희소하고 압축된 경우에 집중하고 있다.