Small complete 3-term progression free sets in cyclic groups and vector spaces

기술 요약: 순환 군 및 벡터 공간에서의 작은 완전 3-항 등차수열 자유 집합

문제 정의
본 논문은 대수적 구조, 특히 순환 군($\mathbb{Z}_m$)과 유한 벡터 공간($\mathbb{F}_p^n$)에서 완전한 3-항 등차수열(3-AP) 자유 집합의 최소 크기를 결정하는 문제를 다룬다. 최대 크기의 3-AP 자유 집합을 찾는 것은 가법 조합론의 중심 주제이지만(예: Roth의 정리, Croot-Lev-Pach, Ellenberg-Gijswijt), 완전한 집합(더 이상 확장할 수 없는 집합)의 최소 크기를 구하는 것은 그 반대 방향의 문제이다. 단순한 계수 논증을 통해 이 최소 크기의 차수는 구조의 카디널리티의 제곱근보다 크거나 같다는 것을 알 수 있다. 저자들은 이러한 집합이 순환 군에서 $O(\sqrt{|G|})$의 크기를 갖는 존재 여부에 관한 미결 과제들을 다루며, 이 하한선이 타이트한지 조사한다.

방법론
저자들은 명시적인 조합론적 구성, 모듈로 축소 기법, 그리고 유한 체 위에서의 대수 기하학을 결과적으로 결합하여 사용한다.

1. 순환 군 ($\mathbb{Z}_m$):

   • 강한 성질: 저자들은 완전한 (2, -1)-회피(avoiding) 집합에 집중한다. 집합 $A$가 (2, -1)-회피적이라는 것은 $A \cap (2A \dot{-} A) = \emptyset$ (여기서 $2A \dot{-} A = \{2a - b : a, b \in A, a \neq b\}$)임을 의미한다. 이 성질은 완전한 3-AP-free 성질보다 더 강력한데, 이는 외부의 모든 점이 단순히 중점이 되는 것을 허용하는 대신, 반드시 $A$의 원소들을 양 끝점으로 하는 수열의 끝점이 되도록 강제하기 때문이다.
   • R-완전 집합: 이 구성은 정수 부분집합 $[0, R]$이 내부적으로 (2, -1)-회피적이며 구간 $[-R, 2R]$을 포화하는 "R-완전" 집합에 기초한다.
   • 이진 자릿수 구성: 일반화된 이진 자릿수 구성을 사용하여(보조정리 3.3), $S_n$-완전인 크기 $2^n$의 집합 $P$를 생성한다. 자릿수 수열 $d_i$를 신중하게 선택함으로써, 결과적인 집합이 넓은 범위의 법(moduli) $m$을 커버하도록 보장한다.
   • 모듈로 축소: 보조정리 3.2는 $R$-완전 집합이 $2R < m \leq 3R + 1$일 때 $\mathbb{Z}_m$에서 완전한 (2, -1)-회피 집합으로 내려온다는 것을 보여준다.
   • 유한 검증: 일반적인 구성이 적용되지 않거나 완전한 (2, -1)-회피 집합이 존재할 수 있는 작은 법 $m < 81$의 경우, 저자들은 정확한 최소 크기를 결정하기 위해 전수 조사를 수행한다.

2. 벡터 공간 ($\mathbb{F}_p^n$):

   • 이차 곡선 그래프: 핵심 구성은 동차 이차 사상 $Q: U \to W$의 그래프를 활용한다. 구체적으로, $A_Q = \{(u, Q(u)) : u \in U\}$ 형태의 집합을 구성한다.
   • 끝점-중점 완전성: 저자들은 "끝점-중점 완전(endpoint-midpoint complete)" 집합을 정의하는데, 이는 외부의 모든 점이 $A$의 원소들로 형성된 수열의 끝점($x = 2a - b$)과 중점($2x = c + d$)으로 모두 표현될 수 있음을 의미한다. 이 성질은 곱 구성(product construction)에 있어 매우 중요하다.
   • 부분체 구성: 확장체 $E = \mathbb{F}_{p^{kL}}$와 부분체 $T = \mathbb{F}_{p^k}$ 위에서 이차 사상 $Q(x, s) = x^2 - \delta s^2$ (여기서 $\delta$는 비잉여원)를 구성한다. 캐릭터 합(character sums)과 Weil 부등식을 사용하여, 이 사상이 전사적이고 자명한 핵(trivial kernel)을 가짐을 증명함으로써 특정 차원 $n_0 = k(2L+1)$에서 완전한 (2, -1)-회피 집합을 도출한다.
   • 곱 보조정리: 모든 차원 $n$으로 결과를 확장하기 위해 곱 보조정리(보조정리 4.2)를 사용한다. 만약 $A$가 특정 부분 공간에서 끝점-중점 완전하고 $B$가 나머지 좌표에서 완전한 3-AP-free라면, 이들의 곱 $A \times B$는 전체 공간에서 완전한 3-AP-free가 된다. 이를 통해 특수 차원의 집합을 더 작은 집합으로 패딩(padding)하여 임의의 $n$을 커버할 수 있다.

주요 기여 및 결과

1. 순환 군:

   • 정리 1.2: 모든 정수 $m \geq 1$에 대하여, $|A| < 2\sqrt{m}$인 완전한 3-AP-free 집합 $A \subseteq \mathbb{Z}_m$가 존재한다.
   • 큰 $m$에 대한 더 강한 결과: $m \geq 81$인 경우, 구성된 집합은 더 강력한 완전 (2, -1)-회피 성질을 만족한다.
   • 작은 법: 논문은 $m \leq 80$인 경우 $a(3\text{-AP}, \mathbb{Z}_m)$와 $a(2, -1)(\mathbb{Z}_m)$의 정확한 값을 표로 제공하며, 특정 작은 법(예: $m \in \{2, 5, 6, 8, 17, 18, 19, 20\}$)에서는 완전한 (2, -1)-회피 집합이 존재하지 않음을 명시한다.

2. 벡터 공간:

   • 정리 1.3: 모든 고정된 홀수 소수 $p$와 $\epsilon > 0$에 대하여, 모든 $n \geq 1$에 대해 다음을 만족하는 상수 $C_{p,\epsilon}$가 존재한다:
     $$a(3\text{-AP}, \mathbb{F}_p^n) \leq C_{p,\epsilon} n^{1+\epsilon} p^{n/2} = p^{n/2 + o(n)}$$
   • 이 결과는 지수(exponent) 측면에서 $p^{n/2}$를 달성함으로써, 단순 계수 상한선까지의 부차적인 요인을 제외하고는 벡터 공간 변형 문제를 해결한다.

의의 및 주장
본 논문은 완전한 진행-자유 집합에 대한 제곱근 하한선의 타이트함성에 관한 두 가지 미결 과제를 해결했다고 주장한다:

• 순환 군: 모든 순환 군에 대해 하한선이 절대 상수(구체적으로 2) 내에서 타이트함을 입증하였으며, $m \geq 81$인 경우 더 강력한 (2, -1)-회피 성질에 대한 명시적인 구성을 제공한다.
• 벡터 공간: 고정된 홀수 소수 체에 대한 지수 버전을 해결하여, 최소 크기가 $p^{n/2 + o(n)}$임을 보여준다. 이는 단순 계수 상한이 지수적 성장률 측면에서 본질적으로 날카롭다는 것을 확인해 준다.

저자들은 순환 군 결과의 상수 인자(2)가 이전 연구에서 제안된 3/2보다 높지만, 이는 구성이 의도적으로 더 강력한 (2, -1)-회피 성질에 제한되었기 때문이라고 언급한다. 표준 3-AP-완전성(외부 점이 중점이 되는 것을 허용함)의 추가적인 자유도를 활용한다면 더 작은 구성을 얻을 수 있을 것이라고 시사한다. 마찬가지로 벡터 공간의 경우, $n$과 독립적인 균일한 절대 상수의 존재 여부와 모든 차원에서 완전한 (2, -1)-회피 집합의 경계가 존재하는지에 대한 문제는 여전히 열려 있다. 이 연구는 이러한 가법 조합론 문제를 완전 캡(complete caps) 및 포화 집합(saturating sets)과 같은 유한 기하학에 연결한다.