Adjacent comparison bounds and extremal sets for Ruzsa numbers

기술 요약: 인접 비교 경계 및 루자 수(Ruzsa Numbers)의 극단적 집합

문제 정의
양의 정수 $m$과 $\mathbb{Z}_m$을 법 $m$에 대한 잔여류 환(residue class ring)이라 하자. 부분집합 $A \subset \mathbb{Z}_m$에 대하여, $\sigma_A(n)$을 $a + a' \equiv n \pmod m$을 만족하는 순서쌍 $(a, a') \in A^2$의 개수라고 정의하자. 루자 수 $R_m$은 모든 $n \in \mathbb{Z}_m$에 대하여 $1 \le \sigma_A(n) \le r$을 만족하는 부분집합 $A \subset \mathbb{Z}_m$이 존재하는 최소 정수 $r$로 정의된다. 이 개념은 가법 기저(additive bases)에 관한 에르되시-투란 추측(Erdős-Turán conjecture)에서 유래하였다. 선행 연구들은 $R_m$이 절대 상수 $C$로 유계임을 입증하였으며, 상한값은 $C$ (Ruzsa)에서 $768$ (Tang and Chen), $5120$ (Tang and Chen)을 거쳐 최종적으로 $288$ (Chen)로 개선되어 왔다. 최근 Ding과 Zhao (2024)는 상한을 $R_m \le 192$로 개선하였으며, 모든 $m$에 대하여 $|R_{m+1} - R_m| \le 1$이라는 추측을 제시하였다.

방법론
저자들은 조합론적 비교 보조정리(comparison lemmas), 표현 함수(representation functions)를 이용한 해석적 부등식, 그리고 광범에 걸친 계산적 검증을 결합하여 사용한다.

1. 비교 보조정리 (Comparison Lemmas): 본 논문은 $R_m \le 4R_{m+1}$ 및 $R_{m+1} \le 4R_m$을 확립하는 새로운 비교 보조정리(Lemma 3.2)를 도입한다. 이는 집합의 평행 이동(translation)과 합집합을 사용하여 $\mathbb{Z}_m$의 가법 기저로부터 $\mathbb{Z}_{m+1}$의 가법 기저를(또는 그 반대로) 구성하고, 새로운 집합의 표현 횟수를 제한함으로써 달성된다.
2. 해석적 경계 (Analytic Bounds): 극단적 집합 $A$ (즉, $1 \le \sigma_A(n) \le R_m$을 만족하는 집합)의 크기를 추정하기 위해, 저자들은 Lev-Sárközy 부등식(Lemma 2.1)을 활용한다. $\sigma_A(n)$의 상수 $c$로부터의 평균 제곱 편차를 분석함으로써, 저자들은 $|A|$와 $m$ 및 $R_m$ 사이의 이차 부등식을 도출한다.
3. 계산적 검증 (Computational Verification): 저자들은 $m$이 100에 이르기까지 $R_m$의 정확한 값을 결정하기 위해 인증 기반 탐색(certificate-based search)을 수행한다.
   • $m \le 45$인 경우, 주장된 $R_m$보다 낮은 표현 경계를 갖는 집합의 부존재를 증명함으로써 정확성을 검증한다.
   • $m > 45$인 경우, 하한 증명($R_m \ge 6$)에 의존하며 $\max \sigma_A(n) \le 6$을 만족하는 집합을 탐색한다.
   • 탐색에는 집합 평행 이동, 원소 교체, 그리고 표현 결함(representation defect)을 최소화하기 위한 예산 할당 시도(budgeted attempts)를 포함하는 휴리스틱 최적화 절차가 사용된다.

주요 기여 및 결과

• 인접 비교 경계 (Adjacent Comparison Bound, 정리 1.1): 저자들은 임의의 양의 정수 $m$에 대하여 $|R_{m+1} - R_m| \le 144$임을 증명한다. 이는 새로운 비교 보료정리와 알려진 상한 $R_m \le 192$를 사용하여 자명한 경계인 $186$($192 - 6$에서 유도됨)을 개선한 것이다.
• 정확한 값 및 반례: 본 논문은 $2 \le m \le 100$인 모든 $m$에 대한 $R_m$의 정확한 값을 표로 제공한다.
  • 계산 결과 $R_{37} = 4$이고 $R_{39} = 5$임이 밝혀졌다.
  • 구체적으로, $R_{36} = 6$이고 $R_{37} = 4$이며, 이는 $m=36$일 때 원래의 Ding-Zhao 추측($|R_{m+1} - R_m| \le 1$)에 대한 반례가 된다.
  • 저자들은 수정된 추측을 제안한다: $|R_{m+1} - R_m| \le 1$은 충분히 큰 $m$에 대해 성립한다.
  • 또한, $m \ge 40$인 모든 $m$에 대하여 $R_m = 6$이라고 추측한다 (추측 2.3).
• 극단적 집합 크기에 대한 경계 (Extremal Set Size Bounds, 정리 1.2): 충분히 큰 $m$과 $R_m$을 달성하는 집합 $A$에 대하여, 저자들은 $|A|^2$에 대한 비자명한 경계를 도출한다. $s = \lfloor R_m/2 \rfloor$라 할 때, 크기는 다음을 만족한다:
  $$\left( s + \frac{1}{2} - \sqrt{\left(s+\frac{1}{2}\right)^2 - 4s - \epsilon} \right)m \le |A|^2 \le \left( s + \frac{1}{2} + \sqrt{\left(s+\frac{1}{2}\right)^2 - 4s + \epsilon} \right)m$$
  결과적으로, 만약 $R_m = 6$이라면, $|A| \le \sqrt{191m}$이다.
• 구조적 성질 (Structural Properties): 본 논문은 $A_m$ (집합 $A_m$을 달성하는 부분집합들)의 성질을 조사한다.
  • 패리티 (Parity): 명제 5.5는 $m$이 짝수일 때 $A$ 내 짝수 원소의 비율에 대한 경계를 제공한다. 만약 $R_m = 6$이라면, 짝수 원소의 비율은 $1/2$로부터 약 $0.14$ 범위 내로 제한된다.
  • 등차수열 (Arithmetic Progressions): 저자들은 $L_m$을 임의의 $A \in A_m$에 포함된 등차수열의 최대 길이로 정의한다. $L_m \le R_m$임이 언급된다.
  • $A_m$의 카디널리티 (Cardinality of $A_m$): 명제 5.6은 그러한 집합들의 개수인 $|A_m|$에 대한 점근적 경계를 설정하며, $\frac{1}{2}\log m - C \le \log |A_m| \le \sqrt{191m} \log(\dots)$임을 보여준다.

의의
본 논문은 루자 수의 거동, 특히 인접한 법(modulus) 변화에 따른 $R_m$의 안정성을 다룸으로써 루자 수에 대한 이해를 정교화한다. 작은 $m$에 대해 엄격한 $|R_{m+1} - R_m| \le 1$ 추측을 반박하는 동시에, 점근적으로는 그 타당성에 대한 강력한 근거를 제공함으로써, 저자들은 대수적 구조(법의 성질)와 조합론적 무작위성 사이의 상호작용을 명확히 한다. $m=100$까지의 정확한 값을 제공하는 것은 기존의 표를 실질적으로 확장하며, 극단적 집합의 크기에 대해 도출된 경계는 순환 군에서의 가법 기저에 관한 향후 연구에 새로운 제약을 제공한다. 본 연구는 표현 값의 분포, 극단적 집합의 구조, 그리고 그러한 집합들의 증가율에 관한 여러 미해결 과제들을 제기한다.