2025-11-26T05:13:18.966584

Words with Repeated Letters in a Grid

Halberstam, Schildkraut
Given a word $w$, what is the maximum possible number of appearances of $w$ reading contiguously along any of the directions in $\{-1, 0, 1\}^d \setminus \{\mathbf{0}\}$ in a large $d$-dimensional grid (as in a word search)? Patchell and Spiro first posed a version of this question, which Alon and Kravitz completely answered for a large class of ``well-behaved" words, including those with no repeated letters. We study the general case, which exhibits greater variety and is often more complicated (even for $d=1$). We also discuss some connections to other problems in combinatorics, including the storied $n$-queens problem.
academic

격자 내 반복 문자가 있는 단어

기본 정보

  • 논문 ID: 2511.19678
  • 제목: 격자 내 반복 문자가 있는 단어
  • 저자: Zachary Halberstam, Carl Schildkraut
  • 분류: math.CO (조합론)
  • 발표 시간: 2025년 11월 24일 (arXiv 사전 인쇄본)
  • 논문 링크: https://arxiv.org/abs/2511.19678

요약

본 논문은 d차원 격자에서 "단어 검색" 방향(즉, 방향 벡터가 {-1,0,1}^d{0} 내)으로 연속 읽을 때 주어진 단어 w의 최대 출현 횟수 문제를 연구합니다. Patchell과 Spiro가 처음 이 문제를 제안했으며, Alon과 Kravitz는 중복되지 않는 문자의 경우를 완전히 해결했습니다. 본 논문은 반복 문자를 포함하는 일반적인 경우를 연구하여 더 풍부한 구조와 복잡성을 보여주며(d=1인 경우에도 마찬가지), n-퀀 문제와 같은 고전적 조합 문제와의 깊은 연관성을 밝혀냅습니다.

연구 배경 및 동기

1. 핵심 문제

단어 w와 차원 d가 주어졌을 때, n₁×n₂×...×n_d 크기의 d차원 원형 격자(각 좌표는 n_i로 모듈로)에서 문자를 어떻 배치하여 w의 출현 횟수를 최대화할 수 있을까요? 여기서 "출현"은 3^d-1개의 검색 방향 중 하나를 따라 연속 읽어서 w를 얻는 것을 의미합니다.

2. 문제의 중요성

  • 이론적 의의: 이 문제는 가법 조합론, 푸리에 해석 및 그래프 이론 등 여러 수학 분야를 연결합니다
  • 조합 최적화: 제약 조건 하에서의 극값 배치 문제를 포함합니다
  • 고전적 문제와의 연관성: 주기적 타일링 추측, n-퀀 문제 등 유명한 문제와 깊은 연관성이 있습니다

3. 기존 연구의 한계

Alon과 Kravitz 1은 "잘 행동하는" 단어의 경우를 완전히 해결했습니다. 여기에는 다음이 포함됩니다:

  • 중복되지 않는 문자의 단어
  • 특정 제약 조건을 만족하는 단어(예: 문자가 홀수 또는 짝수 위치에만 나타나고, 중복되지 않는 두 문자 블록)

그러나 일반적으로 반복 문자를 포함하는 단어의 경우 문제는 여전히 해결되지 않았으며, 더 복잡한 구조를 나타냅니다.

4. 연구 동기

  • 반복 문자 단어의 극값 배치 탐색
  • 어떤 단어가 "d-허용 가능" 또는 "d-기울 가능"인지 분류
  • 다른 조합 문제와의 연관성 구축

핵심 기여

  1. 1차원 경우의 완전 해결(정리 1.2): 임의의 단어에 대해 1차원 경우의 밀도 C₁(w)의 닫힌 형식을 제시하고 모든 극값 격자를 분류합니다
  2. 차원 경계 설정(명제 1.3): 임의의 단어 w와 차원 d에 대해 다음을 증명합니다: 3d−1C1(w)≤Cd(w)≤3d−12C1(w)3^{d-1}C_1(w) \leq C_d(w) \leq \frac{3^d-1}{2}C_1(w)
  3. d-허용 가능성 특성화(정리 1.4):
    • 홀짝 단어(문자가 다를 때 홀짝 위치에 나타남)는 모든 차원에서 d-허용 가능합니다
    • 문자 반복 단어는 d-허용 가능성을 유지합니다
    • 4문자 단어의 2-허용 가능성을 완전히 특성화합니다
    • AB^(ℓ-1)(ℓ>3)은 2-허용 가능하지 않음을 증명합니다
  4. d-기울 가능성 경계(정리 1.5):
    • 길이 ℓ의 단어는 d≥8log₂ℓ+47일 때 d-기울 가능하지 않습니다
    • ℓ의 모든 소인수가 ≥2^d일 때 AB^(ℓ-1)은 d-기울 가능합니다
  5. 방법론적 기여: 네 가지 주요 기술을 개발했습니다
    • 가법 재구성 방법
    • 조합 귀약 기술
    • 국소 선형 계획 분석
    • 푸리에 해석 방법

방법 상세

과제 정의

핵심 개념:

  • 격자 Γ: G=∏ᵢⱼ₁ᵈ Z/nᵢZ에서 문자표 Σ로의 함수
  • 출현: (p,v)∈G×({-1,0,1}^d{0})에 대해, Γ가 위치 {p+iv}_^{len(w)-1}에서 문자가 순서대로 w의 문자일 때, (p,v)를 w의 출현이라고 합니다
  • 밀도: cd(w,Γ) = ct(w,Γ)/|Γ|, 즉 출현 횟수를 격자 크기로 나눈 값
  • 최대 밀도: Cd(w) = sup_Γ cd(w,Γ)

핵심 문제: 단어 w와 차원 d가 주어졌을 때, Cd(w)의 값을 결정합니다.

핵심 기술 프레임워크

1. 가법 재구성 방법(절 3)

문제를 집합 가법 문제로 변환합니다. 방향 v에 대해 다음을 정의합니다: Sv={p∈G:(p,v)는 w의 출현}S_v = \{p \in G : (p,v) \text{는 w의 출현}\}

핵심 관찰: (Su−Sv)∩Iu,v=∅(S_u - S_v) \cap I_{u,v} = \emptyset 여기서 Iu,v={iv−ju:0≤i,j<len(w),wi≠wj}I_{u,v} = \{iv - ju : 0 \leq i,j < len(w), w_i \neq w_j\}

이는 계수 문제를 가법 제약 하에서 ∑v∣Sv∣/∣G∣\sum_v |S_v|/|G|를 최대화하는 문제로 변환합니다.

1차원 경우의 완전 해결:

세 가지 매개변수를 정의합니다:

  • c_left: 가장 긴 회문 접두사 길이
  • c_right: 가장 긴 회문 접미사 길이
  • c_repeat: 진짜 접두사이자 진짜 접미사인 가장 긴 부분 문자열 길이

정리 3.1: 길이 ℓ의 단어 w에 대해:

  • w가 회문이 아닐 경우: C1(w)=max⁡(1ℓ−crepeat,1ℓ−cleft+cright2)C_1(w) = \max\left(\frac{1}{\ell-c_{repeat}}, \frac{1}{\ell-\frac{c_{left}+c_{right}}{2}}\right)
  • w가 회문인 경우: C1(w)=2ℓ−crepeatC_1(w) = \frac{2}{\ell-c_{repeat}}

두 가지 극값 구성:

  1. 구성 1(동일 방향 반복): c_repeat가 클 때, w=vs(s는 길이 c_repeat의 반복 부분 문자열)의 v 부분을 반복합니다
  2. 구성 2(교대 방향): c_left+c_right가 클 때, w를 정방향과 역방향으로 교대로 읽고 회문 부분을 반복합니다

...

(이하 생략: 원문의 나머 절과 부분들을 한국어로 계속 번역할 수 있습니다. 필요한 경우 추가 번역을 요청해 주세요.)