The Word-Search Constants C_2(ABBB) = 8/5 and C_3(ABB) = 6: On Two Questions of Schildkraut and of Halberstam and Schildkraut

Abstract

For a word w and a toroidal grid of letters in dimension d, an appearance of w is a cell together with one of the 3^d − 1 directions in {−1,0,1}^d ∖ {0} along which the letters spell w, and C_d(w) is the supremum, over all grids, of the number of appearances per cell. We prove that C_2(ABBB) = 8/5. This answers Question 9.3 of Halberstam and Schildkraut (Words with repeated letters in a grid, 2025) and the last part of Question 11 of Schildkraut in the problem session of the Oberwolfach workshop Combinatorics (Oberwolfach Rep. 23 (2026)). We also prove that C_3(ABB) = 6, which is the case d = 3 of the first part of that Question 11 and of their Question 9.2. Both values also hold for n × … × n arrays without wraparound, as in the report. The lower bounds are known constructions. The upper bounds are computer-assisted: averaging lemmas, proved in the text, reduce them to 65,536 and 2^27 integer inequalities, one for each pattern of a 4 × 4 or a 3 × 3 × 3 window; these are given by exact certificates and were checked in integer arithmetic by independent programs. In both cases we classify the extremal grids. For ABBB they are the two five-queens lattices, on tori with both sides divisible by 5; for ABB in dimension 3 they are the grids in which the letters A form a family of parallel planes modulo 3. Every window that is not of this kind costs at least 3/70, respectively 47137/294912. So for these two pairs (d, w), and only for these, we show that the supremum is attained by a periodic grid; Question 10 of the report (Question 2.5 of Halberstam and Schildkraut) asks this for all pairs. For ABBB we also determine the possible pairs (density of A, concentration): their closure is the quadrilateral with vertices (0,0), (1/5, 8/5), (3/8, 3/2), (1,0). It follows that Question 9.6 of Halberstam and Schildkraut, a stability statement with constant 1 for the letter distribution of near-extremal grids, has a negative answer for the pair (ABBB, 2) as stated; it holds with the optimal constant 14/5 for grids on two letters. Finally 18 ≤ C_4(ABB) ≤ 62/3, 54 ≤ C_5(ABB) ≤ 64 and 24/5 ≤ C_3(ABBB) ≤ 11/2. Question 10 in general and the values of C_d(ABB) for d ≥ 4 remain open. This is an unrefereed note. Unrefereed preprint released for independent mathematical scrutiny. Publication on Zenodo does not constitute peer review. AI-assisted tools supported research, computation, proof development, and manuscript preparation. The author remains responsible for all claims and the final text. Corpus identifier: OWR-14299905-036 (C. Schildkraut, Questions 10 and 11, problem session of "Combinatorics", Oberwolfach Reports 23 (2026), no. 1, pp. 72-73, doi:10.4171/OWR/2026/1).