2023/05/09 by Freddie Illingworth, Illingworth, Freddie, Lukas Michel +3
Computer Science · Mathematics · #05D05 #20M05 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Group Theory (math.GR) #Limits and Structures in Graph Theory #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2305.05304
openalex publication_date 2023/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The free semigroup F over a finite alphabet A is the set of all finite words with letters from A equipped with the operation of concatenation. A subset S of F is k-product-free if no element of S can be obtained by concatenating k words from S, and strongly k-product-free if no element of S is a (non-trivial) concatenation of at most k words from S. We prove that a k-product-free subset of F has upper Banach density at most 1/ρ(k), where ρ(k) = min\ℓ \colon ℓ \nmid k - 1\. We also determine the structure of the extremal k-product-free subsets for all k ∉ \3, 5, 7, 13\; a special case of this proves a conjecture of Leader, Letzter, Narayanan, and Walters. We further determine the structure of all strongly k-product-free sets with maximum density. Finally, we prove that k-product-free subsets of the free group have upper Banach density at most 1/ρ(k), which confirms a conjecture of Ortega, Rué, and Serra.