The Frobenius Formula for $A=(a,ha+d,ha+b_2d,...,ha+b_kd)$

논문 요약: 수열 $A = (a, ha + d, ha + b_2d, \dots, ha + b_kd)$에 대한 Frobenius 공식

1. 연구 배경 및 문제 정의 (Problem)

• Frobenius 수 ($g(A)$): 서로소인 양의 정수 집합 $A = (a_1, a_2, \dots, a_n)$가 주어졌을 때, $A$의 원소들의 비음수 정수 계수 선형 결합으로 표현할 수 없는 가장 큰 정수를 의미합니다.
• 기존 연구의 한계: $n=2$인 경우 Sylvester 가 공식을 제시했으나, $n \ge 3$인 일반적인 경우 폐쇄형 공식 (closed formula) 을 구하는 것은 알려져 있지 않습니다.
• 연구 대상: 본 논문은 다음과 같은 특수한 형태의 수열 $A$를 다룹니다.
  $$A = (a, ha + d, ha + b_2d, \dots, ha + b_kd)$$
  여기서 $a, h, d$는 양의 정수, $B = (1, b_2, \dots, b_k)$는 $b_1=1$인 정수 수열이며, $\gcd(a, d)=1$입니다.
• 핵심 질문: $a$가 충분히 클 때, $g(A)$를 $a$에 대한 함수로 어떻게 표현할 수 있으며, 특히 $a$가 $b_k$로 나눈 나머지 (congruence class) 에 따라 어떤 구조를 가지는가?

2. 방법론 (Methodology)

논문은 다음과 같은 수학적 도구와 전략을 사용하여 문제를 해결합니다.

• Apéry 집합 (Apéry Set):
  • $A = (a, B)$에 대한 Apéry 집합 $Ape(A, a) = \{N_0, N_1, \dots, N_{a-1}\}$를 정의합니다. 여기서 $N_r$은 $r \pmod a$를 만족하는 $A$의 원소들의 선형 결합 중 가장 작은 값입니다.
  • Brauer-Shockley 정리에 따라 $g(A) = \max(N_r) - a$로 계산됩니다.
• 최소 표현 문제 (Change-making Problem):
  • $N_{dr}$의 계산은 $OB(M) = \min \{ \sum x_i \mid \sum b_i x_i = M \}$를 최소화하는 문제로 환원됩니다. 이는 동전 교환 문제 (Change-making problem) 와 동일합니다.
  • 생성 함수 (Generating function) $F(t, q) = \prod \frac{1}{1 - tq^{b_i}}$를 도입하여 $OB(M)$을 분석합니다.
  • 최소 차수 연산자 $\oslash$를 사용하여 최적 해 (optimal representation) 만을 추출하는 생성 함수 $f(t, q)$를 구성합니다.
• "Stable" 성질 (Stable Property):
  • $OB(M)$이 일정 임계값 이상에서$OB(M + b_k) = OB(M) + 1$을 만족하는 "Stable" 성질을 가짐을 증명합니다.
  • 이는 $OB(M)$의 계산을 유한한 개수의 초기 값으로 줄여주며,$a$가 충분히 크면$g(A)$가$a \pmod {b_k}$에 따라 결정됨을 보여줍니다.
• Greedy Strategy 및 Orderly Sequence:
  • 탐욕 알고리즘 (Greedy strategy) 이 항상 최적해를 주는 수열을 "Orderly sequence"라고 정의합니다. 이 경우 $OB(M)$ 계산이 훨씬 간소화됩니다.

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

가. 일반적인 수열 $B$에 대한 Frobenius 공식 (Theorem 3.3)

• 결과: $a$가 충분히 크면 ($a \ge (u+c-1)b_k$), Frobenius 수 $g(A(a))$는 $b_k$개의 합동류 (congruence class) 로 나뉘며, 각 합동류 내에서 $a$에 대한 이차 다항식으로 표현됩니다.
• 공식 형태:
  $$g(A(a)) = (w_j h - 1)a + r_j d + (ha + b_k d) \left( \left\lfloor \frac{a}{b_k} \right\rfloor - u - c + 1 \right)$$
  여기서 $a \equiv j \pmod {b_k}$이며, $w_j, r_j$는 $B$에 의해 결정되는 상수 수열입니다.
• 의의: 이는 $g(A)$가 $a$에 대해 단순히 선형이 아니라, $a$의 크기에 따라 구간별로 다른 이차 다항식 형태를 띤다는 것을 보여줍니다.

나. Orderly Sequence 인 경우의 개선된 결과 (Section 4)

• 결과: $B$가 Orderly sequence 인 경우 (예: $B=(1, 2, b, b+1)$, $B=(1, b, 2b-1)$ 등), $a$에 대한 하한 (bound) 이 크게 개선됩니다.
• 구체적 공식:
  • $B = (1, 2, b, b+1, 2b)$, $B = (1, b, 2b-1)$, $B = (1, 2, \dots, k, K)$ 등 다양한 특수한 수열에 대해 명시적인 Frobenius 공식을 유도했습니다.
  • 예: $B=(1, 2, \dots, k)$인 경우 (Corollary 4.9), Selmer 의 기존 결과를 일반화하여 $g(A(a))$에 대한 정확한 공식을 제시했습니다.

다. $b_1 > 1$인 경우의 확장 (Section 5)

• 확장: $b_1=1$이라는 제약을 제거하고, $\gcd(B)=1$인 일반적인 수열 $B=(b_1, \dots, b_k)$ ($b_1 > 1$) 에 대해서도 "Stable" 성질이 성립함을 보였습니다.
• 방법: $g(B)$ (수열 $B$만의 Frobenius 수) 를 사용하여 $OB(M)$의 안정성 범위를 재정의했습니다.
• 결과: $b_1 > 1$인 경우에도 $a$가 충분히 크면 $g(A(a))$는 $b_k$를 법 (modulus) 으로 하는 합동류 함수이며, 각 구간에서 이차 다항식임을 증명했습니다 (Corollary 5.2).

4. 의의 및 결론 (Significance)

1. 알고리즘적 효율성:
   • 본 논문은 $b_k$에 대해 다항 시간 (polynomial time) 알고리즘을 제공하여 $g(A(a))$를 계산할 수 있음을 보였습니다. 이는 $n \ge 3$인 일반적인 Frobenius 문제가 NP-hard 임에도 불구하고, 특정 구조를 가진 수열에 대해서는 효율적으로 해결 가능함을 의미합니다.
2. 구조적 통찰:
   • Frobenius 수가 단순한 공식이 아니라, $a$의 크기와 나머지 클래스에 따라 변하는 "합동류 함수 (congruence class function)"이며, 각 구간에서 이차 다항식 형태를 가진다는 것을 체계적으로 규명했습니다.
3. 기존 연구의 일반화:
   • 제곱 수열 ($A=(a, a+1, a+4, \dots)$) 에 대한 기존 연구 (Einstein et al.) 를 일반화된 수열 $A=(a, ha+dB)$로 확장했습니다.
   • Selmer, Brauer, Roberts 등이 연구한 특수한 수열들의 결과를 포괄하는 일반적인 프레임워크를 제시했습니다.
4. 실용성:
   • 구체적인 수열 (예: $B=(1, 11, 14)$ 등) 에 대해 실제 Frobenius 수를 계산하는 예시를 제시하여 이론의 적용 가능성을 입증했습니다.

요약하자면, 이 논문은 Frobenius 수 계산 문제를 생성 함수와 Apéry 집합의 "Stable" 성질을 결합하여 해결하였으며, $a$가 큰 경우 $g(A)$가 $a \pmod {b_k}$에 따라 결정되는 이차 다항식 형태임을 증명하고, 다양한 특수 수열에 대한 명시적 공식을 도출했습니다.