Words with Repeated Letters in a Grid

Basic Information

• Paper ID: 2511.19678
• Title: Words with Repeated Letters in a Grid
• Authors: Zachary Halberstam, Carl Schildkraut
• Classification: math.CO (Combinatorics)
• Publication Date: November 24, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2511.19678

Abstract

This paper investigates the maximum number of occurrences of a given word w when read consecutively along "word search" directions (i.e., direction vectors in {-1,0,1}^d{0}) in a d-dimensional grid. The problem was first proposed by Patchell and Spiro, and completely resolved for words without repeated letters by Alon and Kravitz. This paper studies the general case containing repeated letters, revealing richer structure and complexity (even in d=1), and uncovering deep connections with classical combinatorial problems such as the n-queens problem.

Research Background and Motivation

1. Core Problem

Given a word w and dimension d, how can one arrange letters in an n₁×n₂×...×n_d d-dimensional toroidal grid (with each coordinate modulo n_i) to maximize the number of occurrences of w? Here "occurrence" refers to reading w consecutively along one of the 3^d-1 search directions.

2. Problem Significance

• Theoretical Importance: The problem connects multiple mathematical branches including additive combinatorics, Fourier analysis, and graph theory
• Combinatorial Optimization: Involves extremal configuration problems under constraints
• Classical Problem Connections: Deep connections with periodic tiling conjectures, n-queens problems, and other famous problems

3. Limitations of Existing Work

Alon and Kravitz 1 completely resolved the case of "well-behaved" words, including:

• Words without repeated letters
• Words satisfying specific constraints (e.g., letters appearing only at odd or even positions, without repeated two-letter blocks)

However, for general words with repeated letters, the problem remains unsolved and exhibits significantly more complex structure.

4. Research Motivation

• Explore extremal configurations for words with repeated letters
• Classify which words are "d-stackable" or "d-tileable"
• Establish connections with other combinatorial problems

Core Contributions

1. Complete Solution for One Dimension (Theorem 1.2): Provides a closed form for the concentration C₁(w) of any word in one dimension and classifies all extremal grids
2. Dimension Bounds (Proposition 1.3): Proves for any word w and dimension d: $3^{d-1}C_1(w) \leq C_d(w) \leq \frac{3^d-1}{2}C_1(w)$
3. Characterization of d-Stackability (Theorem 1.4):
   • Parity words (letters not appearing simultaneously at odd and even positions) are d-stackable in all dimensions
   • Letter repetition preserves d-stackability
   • Complete characterization of 2-stackability for 4-letter words
   • Proves AB^(ℓ-1) (ℓ>3) is not 2-stackable
4. Bounds on d-Tileability (Theorem 1.5):
   • Words of length ℓ cannot be d-tileable when d≥8log₂ℓ+47
   • When all prime factors of ℓ are ≥2^d, AB^(ℓ-1) is d-tileable
5. Methodological Contributions: Develops four major techniques
   • Additive reconstruction method
   • Combinatorial reduction techniques
   • Local linear programming analysis
   • Fourier analysis method

Methods in Detail

Problem Formulation

Core Concepts:

• Grid Γ: A function from G=∏ᵢ₌₁ᵈ Z/nᵢZ to alphabet Σ
• Occurrence: For (p,v)∈G×({-1,0,1}^d{0}), (p,v) is an occurrence of w if the letters at positions {p+iv}_^{len(w)-1} form w
• Concentration: cd(w,Γ) = ct(w,Γ)/|Γ|, the number of occurrences divided by grid size
• Maximal Concentration: Cd(w) = sup_Γ cd(w,Γ)

Core Problem: Given word w and dimension d, determine the value of Cd(w).

Core Technical Framework

1. Additive Reconstruction Method (Section 3)

Transforms the problem into a set addition problem. For direction v, define: $S_v = \{p \in G : (p,v) \text{ is an occurrence of } w\}$

Key observation: $(S_u - S_v) \cap I_{u,v} = \emptyset$ where $I_{u,v} = \{iv - ju : 0 \leq i,j < len(w), w_i \neq w_j\}$

This transforms the counting problem into maximizing $\sum_v |S_v|/|G|$ under additive constraints.

Complete Solution for One Dimension:

Define three parameters:

• c_left: length of longest palindromic prefix
• c_right: length of longest palindromic suffix
• c_repeat: length of longest substring that is both a proper prefix and proper suffix

Theorem 3.1: For a word w of length ℓ:

• If w is not palindromic: $C_1(w) = \max\left(\frac{1}{\ell-c_{repeat}}, \frac{1}{\ell-\frac{c_{left}+c_{right}}{2}}\right)$
• If w is palindromic: $C_1(w) = \frac{2}{\ell-c_{repeat}}$

Two Types of Extremal Constructions:

1. Construction 1 (overlapping same direction): When c_repeat is large, repeat w=vs (s is the c_repeat-length repeated substring) by overlapping the v part
2. Construction 2 (alternating directions): When c_left+c_right is large, alternate reading w forward and backward, overlapping palindromic parts

2. Combinatorial Reduction Technique (Section 4)

Projection Reduction Proposition 4.2: If there exists a mapping π:Σ→Σ' and a one-dimensional grid Γ₀ such that:

• Γ₀ is w-extremal
• π(Γ₀) is w'-extremal
• For any grid Γ: ct(w,Γ)/ct(w',π(Γ)) ≤ ct(w,Γ₀)/ct(w',π(Γ₀))

Then for any d: Cd(w)/C₁(w) ≤ Cd(w')/C₁(w')

Application Examples:

• Parity Words (Theorem 1.4a): Project letters to {odd, even}, reduce to the case of AB
• Letter Repetition Words (Theorem 1.4b): Use subsampling techniques to prove w^(k) preserves d-stackability
• Short Word Reduction: Reduce ABCA, ABBC, ABBA, BABB to ABB

3. Local Linear Programming Analysis (Section 5)

Core Idea: For fixed local region S⊂Z^d, optimize weight function F.

Proposition 5.2: If weight function F satisfies:

• (i) For each direction type, average weight is K
• (ii) For any infinite grid G: $\sum_{(p,v)\in A(w,G)} F(p,v) \leq M$

Then Cd(w) ≤ M/K

Linear Programming Construction:

1. Choose local region S (e.g., 3×3 or 5×5 grid)
2. Choose letter A, define feasible direction set F
3. Optimize: $\min M \text{ s.t. } \sum_{(p,v)\in A(w,G)} F(p,v) \leq M, \forall G\in\mathcal{G}$ where G is the set of grids with all A outside S

Key Optimizations:

• Exploit symmetry to reduce variables
• Iteratively add violated constraints
• Enumerate verification over 2^|S| grids

Successful Cases:

• Prove ABB is 2-stackable (C₂(ABB)≤2)
• Prove ABCC is 2-stackable (C₂(ABCC)≤6/5)
• Compute C₂(BABBB)=8/5 (neither 2-stackable nor 2-tileable)

4. Fourier Analysis Method (Section 7)

Application 1: ABB in (Z/3Z)^d grids

Lemma 7.1: For f:(Z/3Z)^d→0,1, α=𝔼f: $\mathbb{E}_{x,y} f(x)(1-f(x+y))(1-f(x+2y)) \leq \frac{3}{2}\alpha(1-\alpha)^2$

Proof technique:

• Expand expectation in terms of Fourier coefficients
• Use properties of ω=e^(2πi/3)
• Apply Lemma 7.2: If ℜ(z),ℜ(ωz),ℜ(ω²z)≤β, then ℜ(z³)≤β³

Application 2: Dimension bounds for d-tileability

Core Strategy (Theorem 1.5a proof):

1. Construct near-extremal grid Θ (Lemma 7.3)
2. Apply stability result (Theorem 3.2): Near-extremal search lines have nearly identical letter distributions
3. Fourier analysis contradiction (Lemma 7.4): In (Z/nZ)^d (n<2^d), impossible for all search lines to have identical letter distributions

Lemma 7.4: In grids of shape (Z/nZ)^d (n<2^d), if letter A occupies proportion α, then there exist two search lines whose A counts differ by at least: $\frac{\sqrt{\min(\alpha,1-\alpha)}}{3^{d/2}}n$

Proof uses second moment method and Fourier transform.

Technical Innovation Points

1. Unified Framework: First systematic study of words with repeated letters, revealing significantly greater complexity than the no-repetition case
2. Additive Perspective: Transforms grid problems into additive combinatorics problems, establishing connections with periodic tiling
3. Multi-level Reduction: Develops flexible combinatorial reduction techniques applicable to various word types
4. Local-Global Principle: Obtains global upper bounds through local linear programming constraints, achieving tight bounds in some cases
5. Fourier-Stability Combination: Innovatively combines one-dimensional stability results with high-dimensional Fourier analysis to obtain dimension bounds
6. n-Queens Connection: Reveals deep connections between AB^(ℓ-1) d-tileability and modular n-queens problems

Experimental Setup

This is a pure theoretical mathematics paper without traditional experiments, but includes extensive computational verification:

Computational Verification

1. One-Dimensional Case: Completely compute C₁(w) for all words of length ≤5
2. Two-Dimensional Short Words:
   • Completely determine 2-stackability for all 4-letter words (10 isomorphism classes)
   • Partially determine 5-letter words (16 out of 31 isomorphism classes)
3. Linear Programming Computation:
   • ABB: Verify 512 grid configurations on 3×3 region (Lemma A.1 hand-verified)
   • ABCC: Verify on 5×5 region (Lemma A.2 hand-verified)
   • BABBB: Computer verification on larger region
   • ABBB: Obtain upper bound C₂(ABBB)≤59526/35459≈1.679

Implementation Details

Linear Programming Optimization Strategy:

• Reduce variables using symmetry group (Z/2Z)^d⋊Sd
• Merge grids on Π-orbits into single constraints
• Iterative constraint sampling solver
• Symmetry reduces computation from 2^|S| to manageable scale

Experimental Results

Main Theoretical Results

1. Complete One-Dimensional Solution (Theorems 3.1, 3.3)

Result Showcase:

• SALSA: c_repeat=2, C₁(SALSA)=1/3 (construction: ...SALSALSALSAL...)
• ELEPHANT: c_left=1, c_right=1, c_repeat=0, C₁(ELEPHANT)=1/7 (construction: ...HPELEPHANTNAHPELEPH...)
• ABABAB: c_repeat=4, C₁(ABABAB)=1 (construction: ...ABABABABAB..., each letter used 6 times)

Structure Characterization (Proposition 3.3):

• If c_left+c_right<2c_repeat: only Construction 1 is extremal
• If c_left+c_right>2c_repeat: only Construction 2 is extremal
• If c_left+c_right=2c_repeat: both constructions are extremal, all extremal grids are combinations thereof

2. Complete Classification of Two-Dimensional Four-Letter Words (Theorem 1.4c)

Key Finding: ABBB (isomorphic to AAAB) is the unique non-2-stackable 4-letter word.

3. Partial Results for Five-Letter Words

d-Stackable (8 words): ABABA, ABABC, ABACA, ABACD, ABCBA, ABCBD, ABCDA, ABCDE (Theorem 1.4a) AABBA (reduction to AABB)

2-Stackable (additional 5 words): AABCC, AABAA (reduction to AAB) ABCAB (reduction to ABB) AABCB, ABBAC (reduction to ABCC)

Non-2-Stackable (2 words):

• ABBBB: C₂(ABBBB)=8/5>6/5=3C₁(ABBBB)
• BABBB: C₂(BABBB)=8/5>3/2=3C₁(BABBB) (Lemma 5.6)

Unresolved: 15 out of 31 isomorphism classes

4. Dimension Bounds Results

Theorem 1.5 Verification:

• Upper bound: For length ℓ words, d-tileability impossible when d≥8log₂ℓ+47
• Lower bound: When all prime factors of ℓ are ≥2^d, AB^(ℓ-1) is d-tileable
• Tightness: By Bertrand's postulate, upper bound is optimal up to constant factors

Concrete Examples:

• ℓ=5, gcd(5,6)=1: AB⁴ is 2-tileable (C₂(AB⁴)=8/5=4C₁(AB⁴))
• ℓ=7, gcd(7,6)=1: AB⁶ is 2-tileable (corresponds to 7-queens problem)

Ablation Studies

While not traditional ablations, the paper demonstrates necessity of each technique component:

1. Necessity of Additive Method: One-dimensional case cannot achieve closed form and structural characterization without additive reconstruction
2. Power of Combinatorial Reduction:
   • Without reduction: need separate analysis of 14 four-letter words
   • With reduction: only directly analyze few base cases like ABB, ABCC
3. Irreplaceability of Local Method:
   • ABB's 2-stackability: other methods cannot handle
   • Key advantage: obtains tight bounds (C₂(ABB)=2 exactly equals 3C₁(ABB))
4. Fourier Analysis Limitations and Advantages:
   • Limitations: only handles special structures (e.g., (Z/3Z)^d shapes)
   • Advantages: obtains general dimension bounds impossible for local methods

Case Studies

Case 1: Complexity of CROC (Note 3.8)

CROC satisfies c_left+c_right=2c_repeat, belonging to Theorem 3.3 case (c).

• v=CROC, v'=CORO
• Extremal grids can be Grid(v₁...vₘ) where vᵢ∈{v,v'}
• Number of extremal grids of size 3n grows exponentially in n
• Example: Grid(CROCROCOR) is extremal but inequivalent to Constructions 1 or 2

Case 2: Non-Monotonicity of BABBB (Lemma 5.6)

Grid Γ (5×5):
A B B B B
B B B A B
B A B B B
B B B B A
B B A B B

• c₂(BABBB,Γ)=8/5
• 3C₁(BABBB)=3×(1/2)=3/2<8/5
• 4C₁(BABBB)=2>8/5
• Conclusion: neither 2-stackable nor 2-tileable, exhibits intermediate behavior

Case 3: AB⁶ and 7-Queens Problem (Figures 6-7)

7 non-attacking queens configurations correspond to extremal grids for C₂(AB⁶)=4C₁(AB⁶):

A B B B B B B
B B A B B B B
B B B B A B B
B B B B B B A
B A B B B B B
B B B A B B B
B B B B B A B

Each A surrounded by 6 consecutive B's in all 8 directions, totaling 56 occurrences.

Experimental Findings

1. Complexity Jump: From no repeated letters to repeated letters, problem complexity increases significantly
   • No repetition: all words d-stackable
   • With repetition: three types emerge—d-stackable, d-tileable, intermediate
2. Dimension Effects:
   • Low dimensions (d=1,2): require detailed per-word analysis
   • High dimensions (d≥8log₂ℓ): general results show no word d-tileable
3. Method Complementarity:
   • Combinatorial methods: handle structured words
   • Linear programming: handle few critical hard cases
   • Fourier analysis: provide asymptotic bounds
4. Rich Open Problems:
   • 15 out of 31 five-letter words unresolved
   • ABB behavior for d≥3 unknown
   • Exact value C₂(ABBB) unknown

Related Work

1. Word Search in Grids

Patchell-Spiro 14 (2022):

• First systematic problem formulation
• Partial results and conjectures

Alon-Kravitz 1 (2024):

• Complete solution for words without repeated letters
• Main result: For "well-behaved" word w, Cd(w)=3^(d-1)/(len(w)-1)
• Extremal construction: alternating forward-backward reading, e.g., ...w₂w₁w₂...wℓwℓ...w₂w₁...
• Methods: Fourier analysis + combinatorial arguments

This Paper's Extension:

• Handles general words with repeated letters
• Reveals richer structure (three types: d-stackable, d-tileable, intermediate)
• Develops new methods (local linear programming)

2. Additive Combinatorics

Periodic Tiling Conjecture:

• Greenfeld-Tao 8 (2024) counterexample: non-periodic tilings exist
• Paper Problem 2.5: Do extremal grids exist? Similar to tiling conjecture
• Connection: Tiling requires S+T=Z^d, this paper requires (S-S)∩I=∅

Kravitz Set Density 11:

• Studies density of sets avoiding specific difference sets
• Related to this paper's additive constraints

3. Extremal Combinatorics

Flag Algebras 16:

• Razborov's semidefinite programming method
• Applied to subgraph density problems
• This paper's linear programming is simplified version of similar idea

Geometric Extremal Problems:

• Unit distance-free sets 2,17
• Orthogonal vector-free sets on spheres 3,7
• Common theme: global extrema under local constraints

4. n-Queens Problem

Classical n-Queens 4:

• Classic problem since 1848
• Bell-Stevens survey

Modular n-Queens:

• Pólya 15 (1921): n non-attacking queens exist when gcd(n,6)=1
• Klarner 9, Kunt 10: high-dimensional generalizations
• Nudelman 13: different attack conventions

This Paper's Contribution:

• Corollary 8.2: For gcd(n,(2d)!)=1, n^(d-1) non-attacking queens exist
• Proves one direction of Bell-Stevens conjecture 25
• Theorems 1.4d and 1.5b establish equivalence between AB^(ℓ-1) and ℓ-queens problem

5. Fourier Analysis Applications in Combinatorics

Arithmetic Progressions:

• Roth theorem (3-AP), Szemerédi theorem (k-AP)
• Higher-order Fourier analysis 18
• This paper's problem similar to restricted-difference AP problems but harder

Recent Progress 5:

• Effective bounds for restricted 3-AP
• This paper's problem for ℓ>3 may require higher-order Fourier analysis

Conclusions and Discussion

Main Conclusions

1. Complete One-Dimensional Solution: Provides closed form for C₁(w) of any word and complete classification of extremal grids
2. Two-Dimensional Short Words: Completely solves 4-letter words, partially solves 5-letter words
3. Dimension Bounds:
   • General bounds: 3^(d-1)C₁(w) ≤ Cd(w) ≤ (3^d-1)/2·C₁(w)
   • d-Tileability: length ℓ words cannot be d-tileable when d≥8log₂ℓ+47
4. Structure Theorems:
   • Parity words always d-stackable
   • Letter repetition preserves d-stackability
   • AB^(ℓ-1) (ℓ>3) not 2-stackable
5. Methodology: Establishes toolkit of four complementary techniques

Limitations

1. Computational Complexity:
   • Linear programming infeasible for |S|>25
   • Hand verification (ABB, ABCC) extremely tedious
   • Limits tractable word lengths
2. Coverage Gaps:
   • 48% of 5-letter words unresolved
   • 6-letter and longer almost completely untouched
   • ABB behavior for d≥3 unknown
3. Method Limitations:
   • Fourier analysis requires special structures (e.g., (Z/3Z)^d shapes)
   • Combinatorial reduction requires finding suitable "base words"
   • Local methods struggle with non-tight bounds
4. Theoretical Gaps:
   • Problem 2.5 (extremal grid existence) solved only for d=1
   • High-dimensional stability results (Problem 9.6) completely open
   • "Typical behavior" of general words unclear

Future Directions

Problems Explicitly Posed in Paper:

1. Extremal Grid Existence (Problem 2.5):
   • For each (w,d), does extremal w-grid exist?
   • Analogy: periodic tiling conjecture disproven; this problem likely also false in high dimensions
2. Short Word Complete Classification:
   • Problem 9.1: Which 5-letter words are 2-stackable?
   • Problem 9.2: Is ABB d-stackable for all d?
   • Problem 9.3: Is C₂(ABBB)=8/5?
3. High-Dimensional Structure (Problems 9.5-9.6):
   • Do all w-extremal grids have identical letter distributions?
   • Do stability results like Theorem 3.2 exist in high dimensions?
4. Asymptotic Behavior (Problem 9.4):
   • Proportion of d-stackable/d-tileable words among long words?
   • Behavior of "typical" words?

Potential Research Directions:

5. Higher-Order Fourier Analysis Application:
   • Can Gowers norms handle long words?
   • Precise connections with restricted-difference AP problems?
6. Computational Method Improvements:
   • More efficient linear programming solvers
   • Machine learning-assisted extremal configuration discovery
   • Symbolic computation verification
7. Connections with Other Combinatorial Problems:
   • Ramsey theory connections
   • Coding theory connections
   • Generalizations to non-grid structures (graphs, manifolds)
8. Algorithmic Questions:
   • Computational complexity of approximating Cd(w) given (w,d)?
   • Efficient algorithms for constructing near-extremal grids?

In-Depth Evaluation

Strengths

1. Excellent Problem Selection:
   • Natural and challenging
   • Connects multiple mathematical branches
   • Both theoretically deep and computationally tractable
2. Methodological Innovation:
   • Diversity: Four complementary techniques each with distinct strengths
   • Unity: Additive reconstruction provides unified perspective
   • Practicality: Linear programming achieves tight bounds in some cases
3. Result Depth:
   • Complete one-dimensional solution includes fine structural characterization (Theorem 3.3)
   • Stability results (Theorem 3.2) establish foundation for high-dimensional analysis
   • Connection with n-queens problem has independent value (Corollary 8.2)
4. Technical Rigor:
   • All main theorems have complete proofs
   • Computational verification transparent (Appendix A provides hand verification)
   • Honest about limitations and open problems
5. Writing Quality:
   • Clear structure organized by technical method
   • Abundant examples and illustrations (Figures 5-9)
   • Detailed motivation and intuitive explanations

Weaknesses

1. Computational Bottleneck:
   • Linear programming method's scalability limited
   • Hand verification of ABB (Lemma A.1) extremely tedious, hard to generalize
   • BABBB and similar cases rely on computers without elegant proofs
2. Incomplete Coverage:
   • 15/31 five-letter words unresolved
   • Almost no results for long words
   • Sparse results for high dimensions (d≥3)
3. Theoretical Gaps:
   • Problem 2.5 (extremal existence) completely open for d≥2
   • Lack of asymptotic results for general words
   • Missing high-dimensional stability theory
4. Method Limitations:
   • Fourier analysis only applies to special-shape grids
   • Combinatorial reduction requires identifying "base words" without systematic method
   • Local methods struggle with non-tight bounds
5. Proof Complexity in Places:
   • Theorem 3.3(c) proof extremely technical
   • Theorem 7.4 proof relies on multiple delicate estimates
   • Readability sometimes compromised

Impact

Theoretical Contributions:

• Initiates systematic study of words with repeated letters
• Techniques developed (especially local linear programming) potentially applicable to other extremal problems
• Connection with n-queens problem may inspire new research

Methodological Value:

• Demonstrates complementarity of multiple techniques
• Additive reconstruction perspective may inspire related problems
• Successful application of local-global principle

Open Problems:

• Numerous concrete, attackable problems posed
• Multiple difficulty levels suitable for different backgrounds
• Significant space for computer-assisted proofs

Limitations:

• Complete resolution unlikely in near term (e.g., general Cd(w))
• Requires new ideas to overcome computational bottlenecks
• No obvious practical applications (pure theory)

Applicable Scenarios

Direct Applications:

• Combinatorial optimization: maximizing configurations under constraints
• Coding theory: possibly related to codeword distributions
• Game design: extreme configurations for word search games

Theoretical Tools:

• Additive combinatorics researchers: new extremal problem type
• Fourier analysis: concrete application case
• Linear programming: demonstration of local method

Teaching Value:

• Shows synthesis of multiple techniques
• Clear progression from simple to complex
• Abundant concrete examples suitable for exposition

Future Research:

• Springboard for studying related extremal problems
• Platform for testing new computational methods
• Interface with other fields (higher-order Fourier analysis)

References

Core References:

1 N. Alon and N. Kravitz. Cats in cubes. Electron. J. Combin., 31(3):Paper No. 3.29, 2024.

• Direct predecessor of this paper, resolves non-repeated-letter case

14 G. Patchell and S. Spiro. The maximum number of appearances of a word in a grid. Amer. Math. Monthly, 129(5):415–434, 2022.

• Original problem formulation

8 R. Greenfeld and T. Tao. A counterexample to the periodic tiling conjecture. Ann. of Math., 200(1):301–363, 2024.

• Important counterexample related to Problem 2.5

4 J. Bell and B. Stevens. A survey of known results and research areas for n-queens. Discrete Math., 309(1):1–31, 2009.

• Comprehensive n-queens survey

16 A. A. Razborov. Flag algebras. J. Symbolic Logic, 72(4):1239–1282, 2007.

• Powerful tool in extremal combinatorics, related to this paper's linear programming method

18 T. Tao. Higher order Fourier analysis. Graduate Studies in Mathematics, vol. 142, AMS, 2012.

• Standard reference for higher-order Fourier analysis, discussed as potential application

Overall Assessment: This is an excellent combinatorics paper that systematically investigates a natural and profound problem. Through developing multiple complementary techniques, the authors achieve substantial progress, particularly completely solving the one-dimensional case and partially solving two-dimensional short words. The paper reveals unexpected connections with classical n-queens problems and poses rich open questions. Main limitations stem from computational complexity restricting method scalability and limited understanding of long words and high dimensions. Nevertheless, this paper establishes solid foundations for the field, with methods and results likely to inspire future research.