Greedy Regular Convolutions

기술 요약: 탐욕적 정규 합성곱 (Greedy Regular Convolutions)

문제 정의
본 논문은 산술 함수($\Gamma$) 집합 위의 정규 합성곱(regular convolutions)의 분류 및 구축 문제를 다룬다. 자연수 $\mathbb{N}$을 0을 포함하는 산술 급수로 분해하는 일련의 분해 구조를 통해 정규 합성곱을 정의한 나르키예비치(Narkiewicz)의 분류를 바탕으로, 저자는 특히 '동차(homogeneous)' 및 '유계(bounded)' 정규 합성곱의 부류를 조사한다.

정규 합성곱이 동차하다는 것은 분해 구조가 모든 소수 $p$에 대해 동일함을 의미하며, 유계라는 것은 산술 급수 블록의 길이가 어떤 정수 $M$에 의해 균등하게 제한됨을 의미한다. 디리클레 합성곱(unbounded)과 유니터리 합성곱(bounded, 블록 길이 1)은 잘 알려져 있으며, 테르나리(ternary) 합성곱(bounded, 블록 길이 2)은 가벨(Gavell)에 의해 식별되었으나, 블록 길이 $d > 2$인 정규 합성곱에 대한 이해에는 공백이 존재한다. 가벨은 $d > 2$일 때, 모든 블록이 정확히 동일한 길이 $d$를 갖는 정규 동차 합성곱은 존재할 수 없음을 증명했다. 본 논문은 모든 블록을 최대한 균일하게 채움으로써 이 균일성을 근사하는 '탐욕적(greedy)' 합성곱의 개념을 도입하여, 임의의 $d$에 대한 정형적인 합성곱을 정의하고자 한다.

방법론
저자는 이러한 합성곱을 생성하기 위한 구성적 절차로서 탐욕적 합성곱(greedy convolutions) $d$를 도입한다. 방법론은 두 가지 주요 표현법에 의존한다:

1. 트리 구축: 주어진 $d$에 대하여, 정점 $\{0, 1, \dots, n\}$을 갖는 루트 트리의 수열 $T_d(n)$이 정의된다. 정수들은 순차적으로 추가된다. 정수 $n+1$은 $n+1 = (m+1)k$이고 $m+1 \le d$를 만족할 때 기존 브랜치 $0 \to k \to 2k \to \dots \to mk$에 리프로 부착된다. 만약 여러 브랜치가 존재한다면, 가장 작은 $k$를 갖는 브랜치가 선택된다("탐욕적" 규칙). 만약 적절한 브랜치가 없다면, 새로운 브랜치 $0 \to (n+1)$이 시작된다. 이 트리들의 극한은 $\mathbb{N}$의 분해 $\Pi(d)$를 정의한다.
2. 행렬 표현: 분해는 엔트리 $(i, j) = ij$를 갖는$d \times \mathbb{N}$행렬$A(d, N)$에 의해 동등하게 생성된다. 열(column)들이 처리되는 과정에서, 만약 값 $ar,c$가 이전 열에 나타나면 현재 열은 '가지치기(pruning)' 된다(행 $r$ 아래의 값을 0으로 설정). 0이 아닌 열들은 양의 정수 $\mathbb{P}$의 분할 $S(d)$의 부분들을 나타낸다.

본 논문은 분해의 각 블록 내에서 가장 작은 양의 원소를 나타내는 **원시 원소(primitive elements)**의 개념을 사용하여 대수적 구조를 특징짓는다. $d=2$와 $d=3$의 원시 원소 집합을 분석하기 위해, 저자는 **선택적 체질(selective sifting)**이라 명명된 $s(S)$라는 재귀적 체질 유사 절차를 도입한다. 이 절차는 정수 $n$이 $a \in S$이고 $b$가 이미 체질된 집합에 속하는 $ab$의 형태로 형성될 수 없는 한,$n$을 집합에 포함시키는 방식으로 반복 수행된다.

주요 기여 및 결과

• 탐욕적 합성곱의 정의: 본 논문은 임의의 양의 정수 $d$에 대한 탐욕적 합성곱 $G(d)$를 공식적으로 정의한다. $G(1)$은 유니터리 합성곱에, $G(2)$는 테르나리 합성곱에 대응함을 확립한다.
• 균등 블록 길이의 유일성: 본 논문은 (가벨의 연구를 인용하여) $d > 2$일 때 모든 블록이 정확히 동일한 길이 $d$를 갖는 정규 동차 합성곱은 존재할 수 없음을 증명한다. 탐욕적 구축은 블록 길이가 $d$ 이하이지만 반드시 같지는 않은 자연스러운 대안으로 제시된다.
• $d=3$에 대한 상세 분석:
  • $G(3)$의 블록 길이는 3 또는 1임이 밝혀졌다.
  • 원시 원소 집합은 풀 랭크(full rank, 3)인 것과 랭크 1인 것으로 구분된다.
  • 풀 랭크 원시 원소의 집합 $M$은 $m = 4^i 9^j k$ (단, $\gcd(k, 6)=1$) 형태의 정수 집합으로 식별된다 (OEIS A339690).
  • 랭크-1 원시 원소 집합은 $6M$으로 식별된다.
  • $d=3$일 때 전체 원시 원소의 자연 밀도(natural density)는 $7/12$로 계산되었다.
  • 저자는 $d=3$의 원시 원소 집합이 $S = \{2, 3, 6\}$을 이용한 선택적 체질로 기술될 수 있음을 입증한다.
• 선택적 체질 프레임워크: 본 논문은 체질 방법을 일반화하여 $s(\{p\})$, $s(\{p, q, pq\})$ 및 기타 특정 집합들에 대한 폐쇄형(closed-form) 설명을 제공한다. 또한 $d=2$와 $d=3$에서 원시 집합들이 특정 $S$에 대한 $s(S)$와 정확히 일치함을 확립한다.
• $d=4$ 분석:
  • $G(4)$에 대한 데이터를 제시하며, 랭크 1, 2, 4의 원시 원소는 존재하지만 랭크 3 원시 원소는 부재함을 언급한다.
  • $d=4$의 원시 원소 집합은 유한한 선택적 체질 집합 $S$에 의해 정확히 표현될 수 없다는 점이 관찰되었다.
  • $2^a 3^b$ 형태의 수들로 구성된 무한한 $S$에 의해 생성되는 선택적 체질 집합에 랭크-4 원시 원소 집합이 "가깝다"는 추측을 제안한다.
• 통계적 특성: 본 논문은 다양한 경우에 대한 자연 밀도를 계산하고, 블록 길이의 분포와 연속적인 원시 원소 사이의 거리를 도식화한다. 이때 원시 원소 사이의 평균 거리는 그들의 자연 밀도의 역수이다.

의의 및 주장
본 논문은 유니터리/테르나리 사례와 더 높은 차수의 균등 블록 길이 사이의 간극을 메우는 새로운 정규 합성곱 부류를 위한 체계적인 구축 방법을 제공한다고 주장한다. 주요 의의는 다음과 같다:

1. 구조적 특징 규명: 균등 블록 길이는 $d > 2$일 때 불가능함을 증명하고, 탐욕적 구축을 가장 자연스러운 해결책으로 제시한다.
2. 복잡한 원시 구조: 탐욕적 합성곱의 정의 자체는 단순하지만, 그 원시 원소의 구조는 $d \ge 3$에서 놀라울 정도로 복잡해진다는 점을 밝힌다. 본 논문은 $d=3$의 경우 구조가 규칙적이며 선택적 체질로 기술 가능하지만, $d=4$의 경우 구조가 "놀라울 정도로 복잡해지며" 단순한 체질 기술에 저항한다는 점을 강조한다.
3. 미해결 문제: 본 논문은 일반적인 $d$에 대한 원시 원소의 랭크, 자연 밀도, 그리고 고차수 탐욕적 합성곱에서의 "스포라딕(sporadic)" 원소의 정확한 구조에 관한 몇 가지 미해결 과제를 제시하며 마무리된다.

저자는 모든 결과가 정의와 계산 실험(SageMath 사용)으로부터 도출되었음을 명시하며, 본 논문이 산술 함수 및 정규 합성곱의 이론적 틀 이외의 응용을 주장하지 않음을 밝힌다. 이 연구는 이러한 특정 대수적 구조의 분류와 탐색을 목적으로 한다.