On the Monotonicity of Higher-Fold Representation Functions

기술 요약: 고차 표현 함수의 단조성에 관하여

문제 정의
본 논문은 집합 $A \subseteq \mathbb{N}$에 대하여, $n = a_1 + \dots + a_h$ ($a_i \in A$)를 만족하는 순서쌍 $(a_1, \dots, a_h)$의 개수로 정의되는 순서형 $h$-중 표현 함수(ordered $h$-fold representation function) $R_{A,h}(n)$의 단조성 성질을 조사한다. 핵심 질문은 여집합 $\mathbb{N} \setminus A$가 무한집합(즉, co-infinite set)인 집합 $A$에 대해 $R_{A,h}(n)$이 엄격히 증가할 수 있는지 여부이다.

역사적으로, Erdős, Sárközy, Sós는 $h=2$인 경우, 엄격한 단조성은 $A$가 cofinite(즉, 여집합이 유한함)임을 의미한다는 것을 증명했다. $h \ge 3$인 경우, Dombi는 만약 $\mathbb{N} \setminus A$가 무한하다면 $R_{A,h}(n)$이 결국(eventually) 엄격히 증가할 수 없다는 추측을 내놓았다. 이 추 conjecture는 Shallit에 의해 반박되었는데, 그는 오토마타 이론을 사용하여 $R_{B,3}(n)$이 엄격히 증가하는 co-infinite 집합 $A$를 구성하였다. 구체적으로, Shallit는 집합 $B = \{0\} \cup \{m \ge 1 : m$의 4진법 전개가 1 또는 2로 시작하는 $m\}$을 활용하였다. Shallit는 고정된 $h \ge 3$에 대해 $R_{B,h}(n)$의 엄격한 단조성을 확립하였으나, 차이 함수 $R_{B,h}(n+1) - R_{B,h}(n)$의 정확한 성장률은 미해결된 정량적 문제로 남아 있었다. 또한, Dombi는 점근적 밀도 $\alpha \neq 1/2$ (또는 구체적으로 $\alpha \neq 1$)를 갖는 그러한 집합의 존재성에 관한 문제를 제기하였다.

연구 방법론
저자들은 생성 함수, 집합 $B$의 자기 유사 구조에서 유도된 재귀 관계, 그리고 합성(convolution) 논법을 결합하여 차이 함수 $\Delta_h(n) = R_{B,h}(n+1) - R_{B,h}(n)$에 대한 경계값을 설정한다.

1. 집합 $B$에 대한 재귀 분석:
   집합 $B$는 지시 수열(indicator sequence) $c_n$에 의해 정의되며, 이는 생성 함수 $C(x) = \sum c_n x^n$에 대한 함수 방정식을 만족한다:
   $$C(x) = (1+x+x^2+x^3)C(x^4) - x^3$$
   이 방정식을 제곱하고 세제곱함으로써, 저자들은 2-중($\beta_n$) 및 3-중($\alpha_n$) 표현 함수의 차이에 대한 재귀 관계를 유도한다.

• 보조정리 2.1 및 2.2: 이 보조정리들은 인덱스 $n/4$에서의 값들을 기반으로 $\beta_n$과 $\alpha_n$에 대한 재귀 공식을 확립한다.
• $\beta_n$에 대한 경계: 보조정리 3.1은 2-중 함수의 차이가 $-1 \le \beta_n \le 2$ 범위 내에 있음을 증명한다.
• $\alpha_n$에 대한 경계: $\beta_n$의 경계와 재귀 관계를 사용하여, 보 auxiliary 정리 3.2는 $n \ge 78$일 때 $\alpha_n \ge n/5 + 4$라는 선형 하한을 확립하며, 보조정리 3.3은 $\alpha_n \le 3n + 2$라는 선형 상한을 제공한다.

2. 합성 리프트(Convolution Lift):
   $h=3$에서 임의의 $h \ge 3$로 결과를 확장하기 위해, 저자들은 다음의 합성 항등식을 활용한다:
   $$R_{p+q}(n) = \sum_{u=0}^n R_p(n-u)R_q(u)$$
   이는 차이 함수에 대한 관계로 이어진다:
   $$\Delta_{p+q}(n) = \sum_{u=0}^n \Delta_p(n-u)R_q(u) + R_p(0)R_q(n+1)$$
   $p=3$ 및 $q=h-3$으로 설정함으로써, $\Delta_h(n)$의 거동은 알려진 $\Delta_3(n)$ (즉, $\alpha_n$)의 거동과 $R_{h-3}(n)$의 성장량에 의해 제어된다.

3. 집합 $C$의 구성:
   밀도에 관한 Dombi의 문제를 해결하기 위해, 저자들은 집합 $C = \mathbb{N} \setminus \{2^j : j \ge 10\}$를 구성한다. 제거된 집합 $D(x)$에 대응하는 생성 함수 $G_C(x) = (1-x)^{-1} - D(x)$를 분석한다. 제거된 집합의 희소성(sparsity)은 차이 $R_{C,h}(n+1) - R_{C,h}(n)$의 명시적 추정을 가능하게 한다.

주요 기여 및 결과

1. 다항식 차수의 성장 (정리 1.1):
   본 논문은 집합 $B$에 대하여, 차이 $R_{B,h}(n+1) - R_{B,h}(n)$이 $n^{h-2}$의 차수로 다항식 성장을 함을 증명한다. 구체적으로, 모든 정수 $h \ge 3$에 대하여, 모든 $n \ge 1$에 대해 다음을 만족하는 상수 $c_h, C_h > 0$가 존재한다:
   $$c_h n^{h-2} \le R_{B,h}(n+1) - R_{B,h}(n) \le C_h n^{h-2}$$
   이 결과는 $B$가 거대한 간격을 가진 무한한 여집합을 가짐에도 불구하고, 그 표현 함수의 거동이 전체 정수의 집합 $\mathbb{N}$ (여기서 차이는 $\binom{n+h-1}{h-2} \asymp n^{h-2}$)과 점근적으로 유사함을 확인시켜 준다.

2. 임의의 $h \ge 3$에 대한 엄격한 단조성:
   저자들은 $R_{B,h}(n+1) > R_{B,h}(n)$이 모든 $n \ge 0$ 및 모든 $h \ge 3$에 대해 성립함을 엄격하게 증명하였으며, 이는 모든 $h$에 대한 성장률을 정량화하지 않고 존재성만을 다루었던 Shallit의 결과를 개선한 것이다.

3. Dombi의 밀도 문제 해결 (정리 1.2):
   본 논문은 다음과 같은 성질을 갖는 co-infinite 집합 $C = \mathbb{N} \setminus \{2^j : j \ge 10\}$를 구성한다:

• 점근적 밀도가 존재하며 1이다: $\lim_{n \to \infty} C(n)/n = 1$.
• 표현 함수 $R_{C,h}(n)$은 모든 정수 $h \ge 3$에 대해 엄격히 증가한다.
  이는 기존에 알려진 밀도 1/2의 예시들과 구별되는, 밀도 1을 갖는 집합을 제시함으로써 Dombi의 문제를 해결한다.

의의
본 논문은 가법적 표현 함수(additive representation functions)에 대한 이해를 정교화한다. $h=2$인 경우에서 발견되는 단조성의 장애물이 $h \ge 3$에서는 지속되지 않음을 보여주며, 이는 집합이 매우 큰 무한 여집합을 가질 때도 마찬가지이다. 차이 함수의 정확한 다항식 차수를 확립함으로써, 저자들은 집합 $B$가 정수의 전체 집합이 가지는 "매끄러움(smoothness)"을 표현 성장 측면에서 유지하고 있음을 보여준다. 또한, 집합 $C$의 구성은 이러한 집합들의 지형을 확장하여, 엄격한 단조성이 점근적 밀도 1과 양립 가능함을 보여줌으로써 cofinite와 co-infinite 거동 사이의 간극을 좁힌다.

저자들은 임의의 주어진 밀도 $d \in [0, 1)$를 갖는 집합 및 특정 liminf와 limsup 밀도를 갖는 집합의 존재성에 관한 미해결 과제들을 제시하며, 표현 함수의 단조성 조건에 대한 완전한 규명이 여전히 활발한 연구 분야임을 시사하며 결론을 맺는다.