Algorithmic aspects of Newman polynomials and their divisors

M. Idris 와 J.-M. Sac-Epée 의 논문 "Algorithmic aspects of Newman polynomials and their divisors"에 대한 상세한 기술적 요약입니다.

1. 문제 제기

이 논문은 대수적 수론에서 뉴먼 다항식(계수가 $\{0, 1\}$에 속하고 상수항이 1 인 다항식) 과 관련된 근본적인 질문에 답합니다. 구체적으로, 정수 계수 다항식 $p(x)$가 뉴먼 다항식을 나누는 조건을 조사합니다.

핵심 질문은 다음과 같습니다: 모든 정수 다항식 $p(x)$가 다음 두 조건을 만족할 때, 보편적 상수 $\sigma$가 존재하여 $p(x)$가 반드시 어떤 뉴먼 다항식을 나누게 되는가?

1. 음이 아닌 실근을 갖지 않으며,
2. 마호러 측정 (Mahler measure) $M(p) < \sigma$인 경우.

이전 연구에 따르면, 만약 $M(p) < 2$라면 $p(x)$는 계수가 $\{-1, 0, 1\}$인 다항식을 나눕니다. 그러나 계수를 $\{0, 1\}$로 제한하는 것은 훨씬 더 엄격한 조건입니다. 황금비 ($g \approx 1.618$) 가 자연스러운 상한선으로 여겨졌으나, 마호러 측정이 약 1.556 인 반례들이 발견되었습니다. 이 논문은 이러한 상한선을 정교화하고 작은 마호러 측정을 갖는 다항식의 나눗셈 성질을 규명하는 것을 목표로 합니다.

2. 방법론

저자들은 뉴먼 배수를 찾는 것과 그러한 배수의 부재를 인증하는 두 가지 서로 다른 문제를 해결하기 위해 **혼합 정수 선형 계획법 (MILP)**과 알고리즘적 인증을 결합하여 사용합니다.

A. 뉴먼 배수 탐색 (MILP 접근법)

주어진 다항식 $p(x)$가 뉴먼 다항식을 나누는지 판단하기 위해, 저자들은 이를 선형 부등식 체계로 공식화합니다.

• 공식화: 차수가 $2d$인 모닉 (monic) 다항식 $p(x)$가 주어졌을 때, 곱 $N(x) = p(x)q(x)$의 계수가 $\{0, 1\}$에 속하도록 하는 다항식 $q(x)$를 찾습니다.
• 제약 조건: $p$와 $q$의 상수항이 1 이므로 $N$의 상수항도 1 입니다. $N(x)$의 계수들은 $q(x)$의 미지 계수들의 선형 결합입니다. $N(x)$의 모든 계수가 0 또는 1 이어야 한다는 조건은 정수 미지수를 갖는 선형 부등식 체계를 생성합니다.
• 구현: 저자들은 Julia 언어와 JuMP 모델링 언어, 그리고 Gurobi 최적화 도구를 사용하여 이를 구현했습니다. 결과적으로 생성된 뉴먼 다항식의 차수가 1000 을 초과하지 않는 해를 탐색했습니다.

B. 비나눗셈 인증 (Reachability 접근법)

어떤 다항식이 뉴먼 다항식을 나누지 않음을 증명하기 위해, 저자들은 Hare 와 Mossinghoff 가 제안한 알고리즘적 방법을 활용합니다.

• 원리: 후보 다항식의 근을 $\beta$라고 합시다. 이들은 특정 원판 $I'(\beta)$로 제한된, 차수가 $\le d$인 모든 뉴먼 다항식 $F$에 대한 $F(\beta)$의 값을 나타내는 집합 $N'(\beta, d)$를 정의합니다.
• 알고리즘: 이 집합은 재귀적으로 구축됩니다. 만약 집합이 수렴하여 (즉, $N'(\beta, d+1) = N'(\beta, d)$) 이 집합 내에서 0 에 도달하지 않는다면, $\beta$가 어떤 뉴먼 다항식의 근이 아님이 증명됩니다. 결과적으로 $\beta$의 최소 다항식은 어떤 뉴먼 다항식도 나누지 않습니다.
• 구현: 교차 검증을 위해 이를 Julia(Polynomials.jl 및 Nemo.jl 사용) 와 GP/PARI에서 독립적으로 구현했습니다.

C. 중복근을 갖는 배수 구성

저자들은 MILP 접근법을 $l(x)^2$로 나누어지는 뉴먼 다항식을 찾기 위해 적용했는데, 여기서 $l(x)$는 $x \to -x$로 변환된 Lehmer 다항식입니다.

• 방법: 부등식 대신, 유클리드 나눗셈의 나머지 $N(x) = g(x)H(x) + R(x)$에서 유도된 선형 방정식 체계를 풀었습니다. $g(x) | N(x)$가 성립하려면 $R(x) = 0$이어야 합니다.
• 최적화: 소멸하는 나머지 조건을 만족시키기 위해 이진 계수 $a_i \in \{0, 1\}$에 대해 해를 구했습니다.

3. 주요 결과

A. 작은 마호러 측정을 갖는 다항식의 나눗셈

저자들은 마호러 측정 $< 1.3$이고 차수 $\le 180$인 8,438 개의 알려진 다항식(Known180으로 명명됨) 데이터 세트를 분석했습니다.

• 발견: 양의 실근을 갖는 다항식을 제외하고, 이 목록의 3 개를 제외한 모든 다항식이 차수 $\le 1000$인 뉴먼 다항식을 나누는 것으로 확인되었습니다.
• 정리: 마호러 측정 $M(p) < 1.3$을 가지며, 음이 아닌 실근이 없고, 원분 인자가 없는 차수 $\le 44$의 모든 정수 계수 다항식은 뉴먼 다항식을 나눕니다. 이는 Known180이 차수 44 까지 완전하다는 사실에 기반합니다.
• 미해결 사례: 세 가지 특정 다항식은 여전히 미해결 상태입니다 (차수 1000 까지 뉴먼 배수가 발견되지 않음). 이들이 더 높은 차수의 뉴먼 다항식을 나누는지 여부는 여전히 열려 있는 질문입니다.

B. 보편적 상수 $\sigma$의 개선

인증 방법을 사용하여 저자들은 어떤 뉴먼 다항식도 나누지 않는 새로운 다항식들을 식별함으로써, 가상의 상수 $\sigma$에 대한 상한선을 낮췄습니다.

• 새로운 상한선: 그들은 마호러 측정이 약 1.419404632인 10 차 다항식을 발견했습니다:
  $$x^{10} - x^8 - x^5 + x + 1$$
• 의의: 이는 Drungilas 등 (2023) 의 이전 최상위 상한선인 $\approx 1.4366$과 Hare & Mossinghoff 의 초기 상한선인 $\approx 1.556$을 개선한 것입니다. 만약 상수 $\sigma$가 존재한다면, 그것은 $\le 1.419404632$여야 합니다.
• 데이터 세트: 이 논문은 마호러 측정 $\le 1.556$이며 어떤 뉴먼 다항식도 나누지 않는 33 개의 인증된 예시 (차수 8–12) 의 표를 제공합니다.

C. 중복근을 갖는 뉴먼 다항식

저자들은 $l(x)^2$로 나누어지는 뉴먼 다항식 ($l(x)$는 변환된 Lehmer 다항식) 을 조사했습니다.

• 결과: 그들은 차수가 150까지인 $l(x)^2$로 나누어지는 뉴먼 다항식을 명시적으로 구성했습니다.
• 부정적 결과: 그들은 차수 $\le 160$인 뉴먼 다항식 중 $l(x)^3$으로 나누어지는 것은 없음을 증명했습니다. 이는 Mossinghoff 의 이전 검증 (차수 120 에서 중단됨) 을 확장한 것입니다.
• 데이터: 이 논문은 16 진수 형식으로 인코딩된 이러한 다항식에 대한 포괄적인 표를 제공합니다.

4. 의의와 기여

1. 상한선 정교화: 이 논문은 뉴먼 배수의 존재와 관련된 이론적 상한선을 크게 강화하여, 알려진 "금지된" 마호러 측정 임계값을 $\approx 1.436$에서 $\approx 1.419$로 낮췄습니다.
2. 알고리즘적 프레임워크: 제한된 계수를 갖는 다항식과 관련된 수론적 문제를 해결하는 데 **혼합 정수 선형 계획법 (MILP)**의 효율성을 입증했습니다. 이 방법은 배수를 찾는 부등식 제약과 나머지를 소거하는 등식 제약 모두를 처리할 만큼 유연한 것으로 나타났습니다.
3. 포괄적 데이터: 저자들은 추가 연구를 위해 사용할 수 있는 완전한 데이터 세트를 제공합니다 (Known180 분석, 인증된 비나눗셈자, 구성된 배수 포함) 하며, 여기에는 GP/PARI 검증 스크립트가 포함되어 있습니다.
4. 미해결 질문의 해결: 이 연구는 작은 마호러 측정을 갖는 저차수 다항식 ($\le 44$) 의 경우, 뉴먼 다항식을 나누지 못하게 하는 장애물이 양의 실근의 존재에 거의 전적으로 기인함을 확인시켜 주었으며, 오직 세 가지 소수의 예외만이 더 높은 차수 탐색을 기다리고 있습니다.

5. 결론

이 논문은 보편적 상수 $\sigma$의 존재 여부는 여전히 미해결 질문이지만, 반례에 대한 탐색 공간이 극적으로 축소되었다고 결론지었습니다. 저자들은 MILP 기반 프레임워크가 Borwein, Littlewood, Newman 다항식에 대한 향후 조사를 위한 강력한 도구이며, 제한된 계수를 갖는 다항식의 상한선 개선과 새로운 구조적 성질 발견을 가능하게 할 수 있다고 제안합니다.