Gaps of Binary Numerical Semigroups and of Binary Inclusion-Exclusion Polynomials

기술적 요약: 이진 수치 반군과 이진 포함-배제 다항식의 공집합

문제 제기
본 연구는 $Q_{\{p,q\}}(x)$로 표기되는 이진 포함 - 배제 다항식의 "공집합 (gapsets)" 구조적 성질과 연관된 이진 수치 반군 $\langle p, q \rangle$에서 연속된 원소들 사이의 거리를 다룹니다. 해당 다항식은 다음과 같이 정의됩니다:
$$Q_{\{p,q\}}(x) := \frac{(1-x^{pq})(1-x)}{(1-x^p)(1-x^q)}$$
여기서 $p$와 $q$는 $q \ge p \ge 3$을 만족하는 서로소인 정수입니다. $p$와 $q$가 소수일 때, $Q_{\{p,q\}}$는 원분 다항식 $\Phi_{pq}$로 축소됩니다.

다항식 $f$의 공집합 $G(f)$는 연속된 0 이 아닌 계수의 지수들 사이의 차이의 집합으로 정의됩니다. 이전 연구 (예: Hong 등, Zhang, Cafure 및 Cesaratto) 는 특정 조건 (예: $q \equiv \pm 1 \pmod p$) 하에서 $\Phi_{pq}$의 최대 공집합에 대한 구체적인 결과를 확립했으나, 일반적인 이진 경우에 대한 전체 공집합의 완전한 설명은 여전히 미해결 문제였습니다. 본 논문은 또한 반군 $\langle p, q \rangle = \{ iq + jp \mid i, j \ge 0 \}$에서 연속된 원소들 사이의 가능한 모든 거리의 집합을 특징짓는 것을 목표로 합니다.

방법론
본 논문의 핵심 기술적 기여는 잉여계 (residue systems) 의 선형 치환에 대한 특정 성질의 분석입니다. $p$를 법 (modulus) 으로 하고 $u$를 $p$와 서로소인 정수라 합시다. 해당 치환은 $n \mapsto \langle un \rangle_p$로 주어지며, 여기서 $\langle x \rangle_p$는 $x$를 $p$로 나눈 최소 음이 아닌 잉여를 나타냅니다.

저자는 $a < b$인 쌍 $(a, b)$를 다음 두 가지 부등식 중 하나를 만족하는 경우 "우세 쌍 (dominant pair)"으로 정의합니다:

1. $\max(\langle ua \rangle_p, \langle ub \rangle_p) < \min_{a < n < b} \langle un \rangle_p$
2. $\min(\langle ua \rangle_p, \langle ub \rangle_p) > \max_{a < n < b} \langle un \rangle_p$

이러한 쌍을 분석하기 위해, 논문은 $p$와 $u$의 곱셈적 역수 (기호: $r_1$) 에 적용된 유클리드 알고리즘에서 유도된 법 $p$에 대한 잉여계의 표현을 도입합니다. 유클리드 알고리즘은 $r_{i-1} = Z_i r_i + r_{i+1}$을 통해 $(r_i)$와 $(Z_i)$ 시퀀스를 생성합니다.

저자는 $n = R(z) = \sum z_i (-1)^{i-1} r_i$ 형태의 임의의 정수 $n \in [0, p)$에 대한 특정 표현을 구성하며, 여기서 $z$는 유클리드 알고리즘 매개변수에 의해 제약받는 계수의 튜플입니다. 이 표현을 통해 $z_i$ 계수들에 대한 $\langle un \rangle_p$의 명시적 평가가 가능해집니다.

주요 기여 및 결과

1. 우세 쌍의 특징화:
   논문은 우세 쌍에 대한 차이들의 집합 $\{b-a\}$가 정확히 다음 집합임을 증명합니다:
   $$D_\Delta(p, u) = \{ r_{i-1} - z r_i \mid 0 \le z \le Z_i - 1, \ 1 \le i \le t \}$$
   여기서 $t$는 유클리드 알고리즘의 단계 수입니다. 이 결과는 유클리드 시퀀스의 인덱스 $i$에 기반하여 가능한 차이들을 집합 $D_i$로 분할합니다.

2. 수치 반군의 공집합:
   $u$를 $p$에 대한 $q$의 곱셈적 역수로 설정함으로써, 저자는 우세 쌍을 수치 반군 $\langle p, q \rangle$와 연결합니다.

   • $S(p, q)$를 $[0, (p-1)(q-1)]$ 내의 표현 가능한 정수들의 집합으로, $N(p, q)$를 표현 불가능한 정수들의 집합으로 둡니다.
   • 연속된 표현 가능한 정수들 사이의 거리 집합 $S_\Delta(p, q) = \{ \ell_{j+1} - \ell_j \}$와 연속된 표현 불가능한 정수들 사이의 거리 집합 $N_\Delta(p, q) = \{ n_{j+1} - n_j \}$가 완전히 설명됩니다.
   • 정리 1: $q = p+1$인 경우를 제외하고는 $S_\Delta(p, q) = N_\Delta(p, q)$이며, $q = p+1$인 경우 $S_\Delta(p, q) = N_\Delta(p, q) \cup \{2\}$입니다. 두 집합 모두 $x_1 \equiv q^{-1} \pmod p$인 $D_\Delta(p, x_1)$과 같습니다.

3. 이진 포함 - 배제 다항식의 공집합:
   논문은 다항식 $Q_{\{p,q\}}$의 공집합이 연속된 표현 가능 또는 표현 불가능 정수들의 블록 길이에 해당함을 확립합니다. 구체적으로, 공집합 $G(p, q)$는 다음과 같이 주어집니다:
   $$G(p, q) = \{ \ell_{j+1} - \ell_j - 1 \mid \ell_{j+1} > \ell_j + 1 \}$$
   정리 2: 공집합은 집합 $G_i$들의 합집합입니다:
   $$G(p, q) = \bigcup_{i=1}^t G_i, \quad \text{where } G_i = \{ r_{i-1} - z r_i - 1 \mid 0 \le z \le Z_i - 1 \}$$
   (최종 집합 $G_t$에 대해서는 약간의 수정이 가해집니다.) 이는 모든 가능한 공집합에 대한 완전하고 구성적인 설명을 제공합니다.

4. 공집합 개수에 대한 상한:
   정리 3: 논문은 공집합의 크기 $\#G(p, q)$에 대한 엄밀한 상한을 제공합니다.

   • 상한: $\#G(p, q) \le p - 1$.
   • 하한: $\#G(p, q) \ge k$이며, 여기서 $k$는 $F_k < p \le F_{k+1}$ ($F_k$는 피보나치 수) 로 정의됩니다.
     저자는 이것이 어떤 상수 $c$에 대해 $\#G(p, q) > c \log p$를 의미한다고 지적합니다.

의의 및 주장
본 논문은 이진 포함 - 배제 다항식 클래스에 대한 공집합의 "완전한 설명"을 제공한다고 주장하며, 이는 $q \equiv \pm 1 \pmod p$와 같은 특정 경우나 최대 또는 차등 최대 공집합과 같은 특정 공집합에 국한되었던 이전 결과들을 일반화합니다.

주요 의의는 다항식 공집합 문제를 잉여계의 선형 치환 분석으로 환원시키는 데 있습니다. 저자는 유클리드 알고리즘에 기반한 잉여계의 표현을 도입하여 우세 쌍의 조건을 "매우 투명하게" 만듭니다. 논문은 이 표현이 독립적인 관심을 가질 수 있으며 다른 분야에서의 미래 응용 가능성이 있음을 시사하지만, 구체적인 응용 분야는 명시하지 않습니다.

이 결과는 이진 원분 다항식과 이진 수치 반군에서의 공집합에 대한 이해를 통합하여, 반군 내 연속된 원소들 사이의 거리 집합이 연관된 선형 치환의 우세 쌍에 대한 차이 집합과 동일함을 보여줍니다. 또한 이 연구는 이러한 공집합의 복잡성을 정량화하여, 최악의 경우 (피보나치 입력) 에서는 모듈로 $p$에 대해 로그적으로 증가하는 공집합의 수를 보이고, 최선의 경우에서는 $p$에 의해 선형적으로 제한됨을 보여줍니다.