On the Frobenius Number and Genus of a Collection of Semigroups Generalizing Repunit Numerical Semigroups

1. 연구 문제 (Problem)

• 기본 정의: 자연수 집합 $N$ 의 부분집합 $S$ 가 $0$을 포함하고 덧셈에 대해 닫혀 있으며,$N \setminus S$가 유한할 때 이를 **수치 반군**이라고 합니다. 생성 집합$A = (a_1, a_2, \dots, a_n)$으로 생성된 반군을$\langle A \rangle$ 라고 합니다.
• 핵심 문제:
  • 프로베니우스 수 $F(A)$: $\langle A \rangle$ 에 속하지 않는 가장 큰 정수.
  • 종 (Genus) $g(A)$: $\langle A \rangle$ 에 속하지 않는 양의 정수의 개수.
  • 프로베니우스 문제: 주어진 생성 집합 $A$ 에 대해 $F(A)$ 와 $g(A)$ 를 구하는 것.
• 연구의 동기: 기존 연구들은 등차수열, 기하수열, 피보나치, 메르센, Repunit 등 특수한 수열에 국한되어 있었습니다. 본 논문은 Repunit 수치 반군을 일반화한 더 넓은 범위의 반군 집합을 정의하고, 이들에 대한 통일된 접근법을 제시하여 프로베니우스 수와 종을 구하는 것을 목표로 합니다. 특히 생성 항 중 하나인 $d$ 가 음수가 될 수 있는 경우를 포함하여 기존 연구의 제약을 확장했습니다.

2. 방법론 (Methodology)

저자들은 다음과 같은 단계적 방법론을 사용하여 문제를 해결했습니다.

1. 일반화된 반군 집합 정의 (Collection GCNS):

   • 생성 집합을 $A = (a, h_1a + db_1, h_2a + db_2, \dots, h_ka + db_k)$ 형태로 정의했습니다.
   • 여기서 $b_i$ 는 $b_1=1, b_{i+1} = s_i b_i + 1$ ($s_i \ge s_{i-1}$) 을 만족하는 순서열이며, $h_i = u b_i + 1$ 형태입니다.
   • 이 구조는 Repunit, Thabit, Proth 등 다양한 특수한 반군들을 포괄합니다.

2. Apéry 집합 (Apéry Set) 분석:

   • $a$ 에 대한 Apéry 집합 $Ape(A, a)$를 분석하여$F(A)$와$g(A)$ 를 구하는 표준적인 방법 (Brauer-Shockley, Selmer) 을 활용했습니다.
   • $N_r = \min \{ s \in \langle A \rangle \mid s \equiv r \pmod a \}$ 를 구하는 문제로 환원했습니다.

3. 최소화 문제와 탐욕 알고리즘 (Greedy Algorithm):

   • $N_r$ 을 구하는 과정은 $O_B^H(M) = \min \{ \sum h_i x_i \mid \sum b_i x_i = M \}$ 형태의 최소화 문제로 귀결됩니다.
   • 핵심 통찰: 정의된 $B = (b_1, \dots, b_k)$ 가 정렬된 순서열 (Orderly Sequence) 임을 증명했습니다. 이는 탐욕 알고리즘 (Greedy Algorithm) 이 항상 최적해를 제공함을 의미합니다.
   • 이를 통해 $M$ 을 $B$ 의 원소들로 표현하는 탐욕적 표현 (Greedy Presentation) $X(M)$ 을 유일하게 결정할 수 있게 되었습니다.

4. 점화식 및 부등식 유도:

   • $N_r(m)$ 이 $m$ 에 대해 증가하는지 여부를 판별하기 위해 조건 $ua + d + k - 2 \ge \sum s_i$ 등을 도출했습니다.
   • 탐욕적 표현의 순서 (Colexicographic order) 와 가중치 (Weight) 함수 $w(r)$ 의 성질을 분석하여 $F(A)$ 와 $g(A)$ 의 공식을 유도했습니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

A. 일반화된 공식 유도 (Theorem 2.12, 2.13)

• Collection GCNS에 속하는 임의의 반군에 대해, 특정 조건 하에서 $F(A)$ 와 $g(A)$ 의 닫힌 형식 (Closed-form) 공식을 제시했습니다.
• $F(A) = \sum x_i a + (a-1)(ua+d) - a$
• $g(A)$ 는 탐욕적 표현의 원소 합에 대한 합계로 표현됩니다.
• 혁신성: 생성 항의 계수 $d$ 가 음수일 수도 있음을 허용하여, 기존 연구에서 다루지 못했던 Proth 반군 등의 경우를 포함시켰습니다.

B. 특수한 반군에 대한 적용

이 일반화된 공식은 다음과 같은 기존 및 새로운 반군들에 대해 구체적인 공식을 제공합니다:

1. Repunit 수치 반군: $S(b, n)$ 에 대한 $F(A)$ 와 $g(A)$ 공식을 재도출하고 단순화했습니다.
2. 메르센 (Mersenne) 수치 반군: $b=2$ 인 Repunit 반군의 특수한 경우로, 기존 결과를 포함합니다.
3. Thabit 수치 반군: $d=1$ 인 경우와 일반화된 $d$ 에 대한 공식을 유도했습니다.
4. Proth 수치 반군 (Open Problem 해결):
   • Open Problem 1.3: 임의의 홀수 $m$ 에 대한 Proth 반군 $P_m(n)$ 의 프로베니우스 수와 불변량을 구하는 공식이 존재하는가?
   • 해결: $m = 2^r + q$ 형태일 때, $q$ 의 값에 따라 탐욕적 표현의 패턴을 분석하여 $F(P_m(n))$ 에 대한 명시적 공식을 유도했습니다 (Theorem 5.4, 5.5).
   • $q < 50$ 인 경우에 대한 구체적인 표 (Table 1) 를 제시하여 다양한 $m$ 에 대한 공식을 제공합니다.

C. 새로운 반군 클래스 제안

• $a = m(2^k - 1) + 2^{k-1} - 1$ 형태의 새로운 반군 클래스에 대해 프로베니우스 수와 종의 공식을 제시했습니다 (Theorem 6.1).

4. 의의 및 결론 (Significance & Conclusion)

• 통일된 프레임워크: Repunit, Mersenne, Thabit, Proth 등 이질적으로 보였던 다양한 수치 반군들을 하나의 일반화된 모델 (Collection GCNS) 로 통합하여 설명했습니다.
• 음수 계수의 허용: 생성 항의 계수 $d$ 가 음수일 수 있다는 점을 인정하고 이를 수학적으로 엄밀하게 처리함으로써, Proth 반군과 같은 중요한 클래스를 연구할 수 있는 길을 열었습니다.
• 계산적 효율성: 탐욕 알고리즘이 최적해를 보장하는 '정렬된 순서열' 구조를 활용함으로써, 복잡한 최소화 문제를 효율적으로 해결하고 명시적 공식을 도출할 수 있었습니다.
• 미해결 문제의 부분적 해결: Proth 반군의 프로베니우스 수에 대한 장기적인 미해결 문제 (Open Problem 1.3) 에 대해, $m$ 의 특정 조건 하에서 해결책을 제시했습니다.

요약하자면, 이 논문은 수치 반군의 프로베니우스 문제를 해결하기 위한 강력한 일반화된 도구를 개발하고, 이를 통해 기존에 알려진 특수한 반군들의 성질을 재해석함과 동시에 Proth 반군과 같은 새로운 영역에 대한 구체적인 해법을 제시한 중요한 연구입니다.