On the size of $h$-fold sumsets

기술 요약: $h$-중 합집합의 크기에 관하여

문제 정의
본 논문은 유한 정수 집합 $A$의 $h$-중 합집합(h-fold sumset)의 정확한 카디널리티 $|hA|$를 결정하는 가법 정수론(additive number theory)의 근본적인 문제를 다룬다. 고전적인 극단적 하한(등차수열에 의해 달성됨)과 상한(고유한 표현을 가진 집합에 의해 달성됨)은 존재하지만, 중간 사례들에 대한 $|hA|$의 정확한 구조는 여전히 복잡하다. 저자들은 특히$1 \le s < a < b$인 형태의 집합$A = {0, 1, \dots, s, a, b}$에 초점을 맞춘다. 이 연구는 4-원소 집합의 합집합 구조와 합집합 크기의 집합$R(h, 4)$의 계산에 관한 Nathanson(2025)이 제기한 최근의 미해결 문제들에 의해 동기 부여되었다.

방법론
저자들은 최단 표현 함수(shortest representation function)의 구조적 분석과 생성 함수(generating functions)의 결합을 활용한다.

1. 최단 표현 함수 ($\ell_A$): 핵심 도구는 정수 $n$을 만들기 위해 필요한 $A$의 원소의 최소 개수를 정의하는 함수 $\ell_A(n)$이다. 정수 $n$은 $n \in hA$일 필요충분조건은 $\ell_A(n) \le h$인 것이다.
2. 모듈러 분해 (Modular Decomposition): 집합 $A$는 $\gcd(a_1, \dots, a_k) = 1$을 만족하도록 $A = \{0 = a_0 < a_1 < \dots < a_k = m\}$로 정규화된다. 저자들은 $n = tm + v$($0 \le v < m$)로 정수$n$을 분해하여$\ell_A$를 분석한다. 이들은$m$에 대한 선형 결합의 최솟값을 기반으로 하는 보조 함수$M_t(v)$를 정의하며, 이를 통해 표현 길이의 "기록(records)"을 특징지을 수 있다.
3. 생성 함수: $A = \{0, 1, \dots, s, a, b\}$인 특정 경우를 위해, 저자들은 표현 가능한 정수의 개수를 세기 위해 생성 함수를 활용한다. 이들은 $\lceil x/s \rceil$과 관련된 다항식 $P_{s,N}(z)$를 유도하고, 이를 사용하여 합집합 크기에 대한 생성 함수를 표현한다.
4. 절단된 이항 계수 (Truncated Binomial Coefficients): 최종 공식은 $x \ge j$이면 $\binom{x}{j}$, 그렇지 않으면 $0$으로 정의되는 절단된 이항 계수$\binom{x}{j}$를 사용하여 표현된다.

주요 기여 및 결과

• 일반 정확 공식 (정리 1): 본 논문은 임의의 유한 정규화된 집합 $A$에 대해 $|hA|$에 대한 정확한 공식을 확립한다. 이 공식은 함수$M_t(v)$의 유한한 엄격한 기록(strict records)들에 의해 결정되는, 잔여값 $v \in [0, m-1]$에 대한 차수 1의 절단된 이항 계수의 합으로 표현된다. 구체적으로, 이는 $M_t(v)$의 기록 값들을 포함하는 합으로 $|hA|$를 나타낸다.
• $\{0, 1, \dots, s, a, b\}$에 대한 명시적 공식 (정리 2): 저자들은 $A = \{0, 1, \dots, s, a, b\}$일 때 $|hA|$에 대한 결정적인 명시적 공식을 유도한다.$b = qa + r$($0 \le r < a$)라고 할 때, 크기는 다음과 같이 주어진다:
  $$|hA| = \sum_e p_{a,e} \left[ \binom{h-e+3}{3} - \binom{h-q-e+3}{3} \right] + \sum_e p_{r,e} \binom{h-q-e+2}{2}$$
  여기서 $p_{N,e}$는 다항식 $P_{s,N}(z)$로부터 유도된 계수들이다.
• 필요충분조건: 위 명시적 공식이 모든 양의 정수 $h$에 대해 성립하기 위한 필요충분조건은 $r = 0$ 또는 $qs + r \ge a$라는 사실을 증명하는 것이 중요한 기여이다.
  • 이러한 조건들이 충족되면, 합집합의 구조가 충분히 규칙적이어서 모든 $h$에 대해 다항식 공식으로 포착될 수 있다.
  • 만약 이 조건들이 실패하면 (즉, $r > 0$ 이고 $qs + r < a$인 경우), 공식은 특정$h$값(특히$h = q+1$)에 대해 실패한다. 이는 공식이 고려하지 못하는 원소들이 표현 가능한 정수 집합에 포함되기 때문이다.
• 4-원소 집합에 대한 따름정리: $s=1$로 설정함으로써, 저자들은 $r=0$ 또는 $q+r \ge a$일 때만 유효한 $|h\{0, 1, a, b\}|$에 대한 6개 항의 명시적 공식을 제공한다.

의의 및 주장
본 논문은 Nathanson의 결과를 일반화한다고 주장한다. Nathanson는 이전에 특정 패턴을 따르는 4-원소 집합의 가족을 식별한 바 있다. 본 연구는 다음을 통해 그 이해를 확장한다:

1. 임의의 유한 정규화된 집합에 적용 가능한 일반적인 프레임워크(정리 1)를 제공함으로써, Nathanson의 문제 1과 문제 2에서 제기된 구조적 질문에 대한 이론적 해결책을 제시한다.
2. 특정 "거의 등차수열적(almost arithmetic)" 구조를 가진 집합의 합집합 크기에 대해 (절단된 이항 계수 형태의) 단순한 폐쇄형 표현(closed-form expression)이 존재하는 경계 조건을 정확하게 규정한다.
3. "규칙 범위(regular range)"($r=0$ 또는 $qs + r \ge a$)를 벗어나면, 합집합의 산술적 구조가 불규칙해지며 단순한 공식이 실패함을 입증하고, 대신 정리 1의 더 복잡한 일반 공식을 사용해야 함을 보여준다.

저자들은 $R(h, 4)$(4-원소 집합의 가능한 모든 합집합 크기의 집합)를 완전히 계산하는 일반적인 문제를 해결한다고 주장하지 않으며, 대신 특정 부류의 집합들에 대해 언제 단순한 공식이 적용 가능한지, 그리고 언제 그렇지 않은지를 명확히 하며 필요한 도구와 구체적인 정확한 공식들을 제공한다.