Extremal densities for forbidden configurations in $S$-smooth numbers

제시된 논문 "S-스무스 수에서의 금지된 구성에 대한 극한 밀도 (EXTREMAL DENSITIES FOR FORBIDDEN CONFIGURATIONS IN S-SMOOTH NUMBERS)" 는 Nikola Veselinov 에 의해 작성된 것으로, 정수론과 조합론의 교차 영역인 S-스무스 수 (S-smooth numbers) 집합 내에서 특정 곱셈적 구성 (multiplicative configurations) 을 피하는 부분집합의 최대 크기와 밀도를 연구한 것입니다.

다음은 이 논문의 문제 설정, 방법론, 주요 기여, 결과 및 의의를 기술적으로 요약한 내용입니다.

---

1. 문제 설정 (Problem Statement)

• S-스무스 수: 유한한 소수 집합 $S = \{p_1, \dots, p_r\}$ ($r \ge 2$) 가 주어졌을 때, $S$ 의 소인수만으로 이루어진 양의 정수들의 집합을 $M(S)$ 라고 합니다. 즉, $M(S) = \{p_1^{a_1} \cdots p_r^{a_r} : a_i \ge 0\}$ 입니다.
• 금지된 구성 (Forbidden Configuration): 연구의 핵심은 $M(S)$ 의 부분집합 $A$ 가 다음 형태의 집합을 포함하지 않도록 하는 것입니다.
  $$\{n, p_1 n, p_2 n, \dots, p_r n\}$$
  이는 $n$ 과 $S$ 에 속하는 각 소수 $p_i$ 를 곱한 수들이 동시에 $A$ 에 존재하지 않도록 하는 조건입니다.
• 목표:
  1. $X$ 이하의 $S$-스무스 수 중 금지된 구성을 포함하지 않는 최대 부분집합의 크기 $F_S(X)$ 를 구하는 점근적 공식을 도출하는 것.
  2. 첫 $k$ 개의 $S$-스무스 수에 대한 극한 함수 $f_S(k)$ 의 거동을 분석하는 것.
  3. 전체 구간 $[1, N]$ 에서의 밀도 상수 $\alpha_S$ 를 표현하고 계산 가능한 경계를 제시하는 것.

2. 방법론 (Methodology)

논문은 다음과 같은 수학적 도구와 기법을 결합하여 문제를 해결했습니다.

• 가중 격자 심플렉스 (Weighted Lattice Simplex) 로의 매핑:

  • $S$-스무스 수 $n = p_1^{a_1} \cdots p_r^{a_r}$ 를 지수 벡터 $(a_1, \dots, a_r) \in \mathbb{Z}_{\ge 0}^r$ 로 변환합니다.
  • $X$ 이하의 조건은 $\sum a_i \log p_i \le \log X$ 라는 부등식으로 표현되며, 이는 가중 심플렉스 $\Sigma_S(u)$ 내의 격자점 문제로 귀결됩니다.
  • 금지된 구성 $\{n, p_1 n, \dots, p_r n\}$ 은 격자점에서의 단위 모서리 (unit corner) $\{a, a+e_1, \dots, a+e_r\}$ 에 해당합니다. 따라서 문제는 심플렉스 내에서 단위 모서리를 포함하지 않는 최대 부분집합을 찾는 문제로 변환됩니다.

• 하한 (Lower Bound) 증명 - 모듈러 색칠법:

  • $\chi(a_1, \dots, a_r) \equiv a_1 + 2a_2 + \dots + r a_r \pmod{r+1}$ 로 정의된 색칠 함수를 사용합니다.
  • 임의의 단위 모서리는 $r+1$ 개의 서로 다른 색을 가지는 점들을 포함하므로, 가장 작은 크기의 한 색 클래스를 제거하면 모든 모서리가 파괴됩니다. 이를 통해 $r/(r+1)$ 비율의 하한을 증명합니다.

• 상한 (Upper Bound) 증명 - 역방향 이동 (Backward Shift) 항등식:

  • 집합 $A$ 에 대해 $A^{(i)} = \{x : x+e_i \in A\}$ 와 같은 역방향 이동 연산을 정의합니다.
  • $A$ 가 모서리를 포함하지 않는다는 조건을 이용하여 $|A|$ 와 $|\Sigma_S(u)|$ 사이의 정확한 항등식을 유도하고, 오차 항을 추정하여 상한을 도출합니다.

• 전체 구간 $[1, N]$ 으로 확장:

  • 임의의 정수 $n$ 을 $n = m \cdot d$ ($d \in M(S), (m, P_S)=1$) 로 유일하게 분해합니다.
  • 이를 통해 전체 구간에서의 극한 문제를 $S$-스무스 수 부분집합 문제의 합으로 분해하여 밀도 상수 $\alpha_S$ 의 표현식을 유도합니다.

3. 주요 결과 (Key Results)

3.1. 점근적 공식 (Theorem 1.1)

$S$-스무스 수 $X$ 이하에서 금지된 구성을 피하는 최대 부분집합의 크기 $F_S(X)$ 와 첫 $k$ 개에 대한 $f_S(k)$ 는 다음과 같이 점근적으로 주어집니다.

$$F_S(X) = \frac{r}{r+1} \Psi_S(X) + O_S((\log X)^{r-1})$$
$$f_S(k) = \frac{r}{r+1} k + O_S(k^{(r-1)/r})$$

여기서 $\Psi_S(X)$ 는 $X$ 이하의 $S$-스무스 수의 개수이며, 주된 항은 $\frac{r}{r+1}$ 비율을 가집니다. 이는 $S$-스무스 수 집합 내에서 최적의 밀도가 $r/(r+1)$ 임을 의미합니다.

3.2. 밀도 상수 $\alpha_S$ 의 표현 및 계산 가능성 (Corollary 1.2, 1.3)

전체 구간 $[1, N]$ 에서의 밀도 상수 $\alpha_S$ 는 다음과 같이 표현됩니다.
$$\alpha_S = c_S \sum_{k \ge 1} \frac{\Delta f_S(k)}{d_k^{(S)}}$$
여기서 $c_S = \prod_{p \in S} (1 - 1/p)$ 이고, $d_k^{(S)}$ 는 $k$ 번째 $S$-스무스 수이며, $\Delta f_S(k) \in \{0, 1\}$ 는 최적 부분집합의 크기 증가분을 나타냅니다.

• 중요한 결과: 이 표현식을 통해 $\alpha_S$ 를 중첩된 계산 가능한 구간 (nested computable bounds) $[L_{S,N}, U_{S,N}]$ 으로 근사할 수 있으며, $N$ 을 증가시킴으로써 $\alpha_S$ 의 소수점 이하 임의의 자릿수를 계산할 수 있습니다.

3.3. 비주기적 유리수 역수합 (Proposition 1.4)

$S$-스무스 수 분모를 가진 유리수 역수합이 결국 주기적인 (eventually periodic) 이진 수열에서 비롯될 필요는 없음을 증명했습니다. 이는 유리수 역수합의 유리수성과 이진 수열의 주기성 사이의 관계에 대한 새로운 통찰을 제공합니다.

3.4. 고전적 경우 $S=\{2, 3\}$ (Section 6)

• $S=\{2, 3\}$ 인 경우 (3-스무스 수), Graham-Spencer-Witsenhausen 상수 $\alpha$ 에 대한 명시적인 꼬리 공식 (tail formula) 을 유도했습니다.
• 구조적 명제: 최적 부분집합들이 중첩된 (nested) 형태 ($A_1 \subseteq A_2 \subseteq \dots$) 로 존재하지 않음을 증명했습니다. 즉, $k$ 개의 원소로 구성된 최적 집합이 항상 $k-1$ 개의 원소로 구성된 최적 집합을 포함하는 것은 아닙니다. 이는 최적 해의 구조가 매우 복잡함을 보여줍니다.

4. 의의 및 기여 (Significance)

1. 일반화된 극한 밀도 문제 해결: 기존에 $S=\{2, 3\}$ 에 대해서만 연구되었던 금지된 구성 문제를 임의의 유한 소수 집합 $S$ 로 일반화하여, 밀도 상수가 $r/(r+1)$ 임을 증명했습니다.
2. 구체적인 계산 가능성: 밀도 상수 $\alpha_S$ 에 대한 이론적 존재성뿐만 아니라, 실제 값을 임의의 정밀도로 계산할 수 있는 알고리즘적 접근법 (중첩 구간) 을 제시했습니다.
3. 조합론적 구조에 대한 통찰: 최적 부분집합이 중첩되지 않을 수 있다는 사실은, 이러한 극한 문제에서 '그리디 (greedy)'한 접근이 항상 최적 해를 보장하지 않음을 시사하며, 문제의 구조적 복잡성을 강조합니다.
4. 수론적 연결: S-스무스 수의 분포, 가중 심플렉스 내 격자점 문제, 그리고 금지된 패턴 회피 문제를 통합하여 다학제적 관점에서 접근했습니다.

결론

이 논문은 S-스무스 수 집합 내에서의 극한 밀도 문제를 체계적으로 해결하고, 그 밀도 상수의 계산적 특성과 최적 집합의 구조적 성질을 규명했습니다. 특히, $r/(r+1)$ 이라는 깔끔한 점근적 비율과 밀도 상수의 계산 가능성은 조합론적 정수론 분야에서 중요한 진전을 이루었으며, 향후 유사한 금지된 구성 문제에 대한 연구의 기초를 제공합니다.