# The structure and density of $k$-product-free sets in the free semigroup

Freddie Illingworth222Mathematical Institute, University of Oxford, United
Kingdom ({illingworth,michel,scott}@maths.ox.ac.uk). Research of FI and AS
supported by EPSRC grant EP/V007327/1. Lukas Michel222Mathematical Institute,
University of Oxford, United Kingdom
({illingworth,michel,scott}@maths.ox.ac.uk). Research of FI and AS supported
by EPSRC grant EP/V007327/1. Alex Scott222Mathematical Institute, University
of Oxford, United Kingdom ({illingworth,michel,scott}@maths.ox.ac.uk).
Research of FI and AS supported by EPSRC grant EP/V007327/1.

(7 July 2023)

###### Abstract

The free semigroup $\mathcal{F}$ over a finite alphabet $\mathcal{A}$ is the
set of all finite words with letters from $\mathcal{A}$ equipped with the
operation of concatenation. A subset $S$ of $\mathcal{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 $\mathcal{F}$ has upper Banach
density at most $1/\rho(k)$, where $\rho(k)=\min\\{\ell\colon\ell\nmid
k-1\\}$. We also determine the structure of the extremal $k$-product-free
subsets for all $k\notin\\{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/\rho(k)$, which confirms a conjecture of Ortega,
Rué, and Serra.

00footnotetext: _2020 MSC_ : 20M05 (free semigroups), 05D05 (extremal set
theory).

##  1 Introduction

A subset $S$ of a (semi)group $G$ is said to be _product-free_ if $x\cdot
y\notin S$ for all $x,y\in S$. Two very natural questions present themselves.

  1. Density: How dense can the largest product-free subset of $G$ be?

  2. Structure: What is the structure of the densest product-free subsets of $G$?

These problems have been extensively studied over the last fifty years. In the
finite abelian case, this culminated in a solution to the density problem by
Green and Ruzsa [GR05] and the structure problem by Balasubramian, Prakash,
and Ramana [BPR16]. The finite non-abelian case was first investigated by
Babai and Sós [BS85]. This case behaves very differently with the possibility
of the largest product-free subsets having vanishing density as shown by the
seminal work of Gowers [Gow08] on quasirandom groups. Recent breakthroughs
include the alternating group where Eberhard [Ebe16] solved the density
problem (up to logarithmic factors) and Keevash, Lifshitz, and Minzer [KLM22]
solved the structure problem. We refer the reader to [Ked09, TV17] for surveys
of the area.

In the infinite non-abelian setting, Leader, Letzter, Narayanan, and Walters
[LLNW20] solved the density problem for a _free semigroup_ 111The free
semigroup on alphabet $\mathcal{A}$ is the set of all finite words whose
letters are in $\mathcal{A}$ equipped with the associative operation of
concatenation and whose identity is the empty word. $\mathcal{F}$ on a finite
alphabet $\mathcal{A}$ with respect to the measure that assigns weight
$\lvert\mathcal{A}\rvert^{-n}$ to each word of length $n$. This is the natural
measure induced by sampling uniformly random words from $\mathcal{F}$ and
gives total weight 1 to the words of length $n$. As noted in [LLNW20], the
counting measure leads to degenerate results (in particular, intuitively small
product-free sets with density close to 1). Leader, Letzter, Narayanan, and
Walters solved the density problem proving the following where $d^{\ast}$ is
the _upper Banach density_ (see Section 2 for formal definitions).

######  Theorem 1.1 ([LLNW20]).

Let $\mathcal{A}$ be a finite set and $\mathcal{F}$ be the free semigroup with
alphabet $\mathcal{A}$. If $S\subset\mathcal{F}$ is product-free, then
$d^{\ast}(S)\leqslant 1/2$.

There is a simple class of examples of large product-free subsets of
$\mathcal{F}$ that show that $1/2$ in Theorem 1.1 is best possible. For a non-
empty subset $\Gamma\subset\mathcal{A}$ the _odd-occurrence set_
$\mathcal{O}_{\Gamma}\subset\mathcal{F}$ generated by $\Gamma$ is the set of
words in which the total number of occurrences of letters from $\Gamma$ is odd
(note that if $\Gamma=\mathcal{A}$, then $\mathcal{O}_{\Gamma}$ consists of
all words of odd length). It is easy to see that these are product-free with
density $1/2$. Leader, Letzter, Narayanan, and Walters conjectured that these
are the only examples.

######  Conjecture 1.2 ([LLNW20]).

Let $\mathcal{A}$ be a finite set and $\mathcal{F}$ be the free semigroup with
alphabet $\mathcal{A}$. If $S\subset\mathcal{F}$ is product-free and
$d^{\ast}(S)=1/2$, then $S\subset\mathcal{O}_{\Gamma}$ for some nonempty
subset $\Gamma\subset\mathcal{A}$.

We confirm Conjecture 1.2 and in fact prove a more general result (Theorem
1.4). Calkin and Erdős [CE96] and Łuczak and Schoen [ŁS97] defined a subset
$S$ of a (semi)group to be _$k$ -product-free_ ($k\geqslant 2$) if
$x_{1}\cdot\dotsc\cdot x_{k}\notin S$ for all $x_{1},\dotsc,x_{k}\in S$ and to
be _strongly $k$-product-free_ if it is $\ell$-product-free for every
$\ell=2,\dotsc,k$. Ortega, Rué, and Serra extended Theorem 1.1 to strongly
$k$-product-free sets as well as to the free group.

######  Theorem 1.3 ([ORS23]).

Let $k\geqslant 2$ be an integer, $\mathcal{A}$ be a finite set, and
$\mathcal{F}$ be the free (semi)group with alphabet $\mathcal{A}$. If
$S\subset\mathcal{F}$ is strongly $k$-product-free, then $d^{\ast}(S)\leqslant
1/k$.

Our first main theorem solves the structure problem for free semigroups,
describing the structure of strongly $k$-product-free sets
$S\subset\mathcal{F}$ with density $1/k$. This confirms Conjecture 1.2. An
alternative view of the odd-occurrence set $\mathcal{O}_{\Gamma}$ is as
follows: label each letter in $\Gamma$ with a $1$ and every other letter with
a $0$ and let the sum of a word be the sum of the labels of its letter;
$\mathcal{O}_{\Gamma}$ is the set of words with odd sum. The natural
generalisation of this to $k\geqslant 3$ provides strongly $k$-product-free
subsets of $\mathcal{F}$ with density $1/k$ (see Remark 1.5). We prove that
these are the only examples.

######  Theorem 1.4.

Let $k\geqslant 2$ be an integer, $\mathcal{A}$ be a finite set, and
$\mathcal{F}$ be the free semigroup with alphabet $\mathcal{A}$. If
$S\subset\mathcal{F}$ is strongly $k$-product-free and $d^{\ast}(S)=1/k$, then
the following holds. It is possible to label each letter of $\mathcal{A}$ with
a label in $\mathbb{Z}/k\mathbb{Z}$ such that $S$ is a subset of the strongly
$k$-product-free set

$T\coloneqq\\{w\in\mathcal{F}\colon\text{the sum of the labels of letters in
$w$ is }1\bmod{k}\\}.$

######  Remark 1.5.

If some prime divides $k$ and every label given to letters in $\mathcal{A}$,
then $T$ will be empty. If there is no such prime, then $T$ will be non-empty
by Bezout’s lemma. If $T$ is non-empty, then $d^{\ast}(T)=1/k$. Indeed, let
$\alpha_{1}\alpha_{2}\dotsb$ be an infinite random word where the $\alpha_{i}$
are independent uniformly random letters from $\mathcal{A}$ and let $X_{n}$ be
the sum of the labels of $\alpha_{1}$, $\alpha_{2}$, …, $\alpha_{n}$. Then
$(X_{n})$ is a Markov chain on $\mathbb{Z}/k\mathbb{Z}$ that is irreducible
(since $T\neq\varnothing$). The uniform distribution $\pi$ on
$\mathbb{Z}/k\mathbb{Z}$ is stationary for this chain. Let $d$ be the period
of $(X_{n})$: by the Markov convergence theorem, for each fixed
$r\in\\{1,\dotsc,k-1\\}$, the subsequence $(X_{nd+r})$ converges to $\pi$ in
distribution, and so the averages $\lvert I\rvert^{-1}\sum_{n\in I}X_{n}$ over
long intervals converge to $\pi$ in distribution. In particular,
$d^{\ast}(T)=\pi(1)=1/k$.

We now turn to $k$-product-free sets. In the special case
$\lvert\mathcal{A}\rvert=1$, the free semigroup $\mathcal{F}$ is isomorphic to
the non-negative integers under addition. In this case, the term ‘sum-free’ is
used in place of ‘product-free’. Calkin and Erdős [CE96] conjectured that a
$k$-sum-free subset of the non-negative integers has density at most
$1/\rho(k)$ where _$\rho(k)$_ is

$\rho(k)\coloneqq\min\\{\ell\in\mathbb{Z}^{+}\colon\ell\nmid k-1\\}.$

Note that the integers which are $1\bmod{\rho(k)}$ form a $k$-product-free set
and so $1/\rho(k)$ would be best possible. Łuczak and Schoen [ŁS97] confirmed
this conjecture and also solved the structure problem for non-negative
integers. We extend their results by solving both the density problem (for all
$k$) and the structure problem (provided $k\notin\\{3,5,7,13\\}$) for
$k$-product-free subsets of the free semigroup.

######  Theorem 1.6.

Let $k\geqslant 2$ be an integer, $\mathcal{A}$ be a finite set, and
$\mathcal{F}$ be the free semigroup with alphabet $\mathcal{A}$. If
$S\subset\mathcal{F}$ is $k$-product-free, then $d^{\ast}(S)\leqslant
1/\rho(k)$.

Theorem 1.7 shows that the structure of the extremal $k$-product-free sets is
very similar to that of strongly $k$-product-free sets except everything is
modulo $\rho(k)$. See Section 9 for further discussion of the cases when $k$
is 3, 5, 7, or 13.

######  Theorem 1.7.

Let $k\geqslant 2$ be an integer with $k\notin\\{3,5,7,13\\}$ and
$\rho=\rho(k)$. Let $\mathcal{A}$ be a finite set and $\mathcal{F}$ be the
free semigroup with alphabet $\mathcal{A}$. If $S\subset\mathcal{F}$ is
$k$-product-free and $d^{\ast}(S)=1/\rho$, then the following holds. It is
possible to label each letter of $\mathcal{A}$ with a label in
$\mathbb{Z}/\rho\mathbb{Z}$ such that $S$ is a subset of the $k$-product-free
set

$T\coloneqq\\{w\in\mathcal{F}\colon\text{the sum of the labels in $w$ is
}1\bmod{\rho}\\}.$

Note, just as in Remark 1.5, that if some prime divides $\rho$ and every label
given to a letter in $\mathcal{A}$, then $T$ is empty. Otherwise $T$ is non-
empty, $k$-product-free, and has density $1/\rho(k)$.

Finally, we consider the free group. Theorem 1.3 solves the density problem
for strongly $k$-product-free sets. Ortega, Rué, and Serra [ORS23] made a
conjecture corresponding to Calkin and Erdős’s for $k$-product-free sets. We
prove this conjecture.

######  Theorem 1.8.

Let $k\geqslant 2$ be an integer, $\mathcal{A}$ be a finite set, and $F$ be
the free group with alphabet $\mathcal{A}$. If $S\subset F$ is $k$-product-
free, then $d^{\ast}(S)\leqslant 1/\rho(k)$.

The rest of the paper is structured as follows. In Section 2 we provide the
formal definitions of density. In Section 3 we prove some important technical
lemmas and state our main density result, Theorem 3.5, from which Theorem 1.6
follows. Before proving Theorem 3.5 we obtain our structural results whose
proofs are simpler and already contain some of the key ideas. The proof of
Theorem 1.4 is given in Section 4 and the proof of Theorem 1.7 in Section 5.
In Section 6 we build the machinery that we use to prove Theorem 3.5 in
Section 7. In Section 8 we adapt our arguments to the free group. We finish,
in Section 9, with some open problems.

##  2 Density

Throughout this paper $\mathcal{F}$ will be the free semigroup on a finite
alphabet $\mathcal{A}$. To motivate and provide intuition for the notation we
view things from the perspective of a randomly generated word. Let
$\mathbf{W}=\alpha_{1}\alpha_{2}\dotsb$ be a random infinite word where each
$\alpha_{i}$ is an independent uniformly random letter in $\mathcal{A}$.
Taking $\mathbf{W}_{n}=\alpha_{1}\alpha_{2}\dotsb\alpha_{n}$, we may view
$(\mathbf{W}_{n})$ as a random walk on the infinite
$\lvert\mathcal{A}\rvert$-ary tree. We say $\mathbf{W}$ _hits_ a set
$B\subset\mathcal{F}$ if the random walks hits $B$ (equivalently if
$\mathbf{W}$ has a prefix in $B$) and $\mathbf{W}$ _avoids_ $B$ otherwise. We
equip $\mathcal{F}$ with a measure _$\mu$_ satisfying, for every word
$w\in\mathcal{F}$,

$\mu(w)=\mathbb{P}(\mathbf{W}\text{ hits }w)=\lvert\mathcal{A}\rvert^{-\lvert
w\rvert}.$

Note that, for $B\subset\mathcal{F}$, $\mu(B)=\sum_{w\in B}\mu(w)$ is the
expected number of times that $\mathbf{W}$ hits $B$. This has a useful
corollary. A set $C\subset\mathcal{F}$ is _prefix-free_ if there are not
distinct words $a,b\in C$ where $a$ is a prefix of $b$. $\mathbf{W}$ can hit a
prefix-free set at most once.

######  Observation 2.1.

If $C\subset\mathcal{F}$ is prefix-free, then $\mu(C)\leqslant 1$.

For a positive integer $n$ and a set $B\subset\mathcal{F}$ the _length $n$
layer of $B$_ is

$B(n)\coloneqq\\{w\in B\colon\lvert w\rvert=n\\},$

while, for an interval $I\subset\mathbb{Z}^{+}$,

$B(I)\coloneqq\\{w\in B\colon\lvert w\rvert\in I\\}.$

Note that the measure $\mu$ is defined so that $\mu(\mathcal{F}(n))=1$. The
density of $B$ on layer $n$ is $\lvert
B(n)\rvert/\lvert\mathcal{F}(n)\rvert=\mu(B(n))$, which is the probability
that $\mathbf{W}_{n}$ is in $B$. The _density of $B$ on interval $I$_ is

$d^{I}(B)\coloneqq\frac{\mu(B(I))}{\mu(\mathcal{F}(I))}=\lvert
I\rvert^{-1}\sum_{n\in I}\mu(B(n)).$

With these definitions in place, we may give standard notions of density. The
_upper asymptotic density_ of $B$ is

$\bar{d}(B)\coloneqq\limsup_{m\to\infty}d^{\\{1,2,\dotsc,m\\}}(B)=\limsup_{m\to\infty}\sum_{n=1}^{m}\mu(B(n))/m.$

The _upper Banach density_ of $B$ is

$d^{\ast}(B)\coloneqq\limsup_{I\to\infty}d^{I}(B)=\limsup_{I\to\infty}\ \lvert
I\rvert^{-1}\sum_{n\in I}\mu(B(n)),$

where $I$ is an interval and the notation $I\to\infty$ denotes that both
$\lvert I\rvert$ and $\min I$ tend to infinity222The condition $\min
I\to\infty$ is often omitted from the definition. However, some simple
analysis shows that, whether or not this condition is included, the resulting
density is the same.. Now $d^{\ast}(B)\geqslant\bar{d}(B)$ for any set $B$ and
so all of our results also hold for asymptotic density.

It should be noted that limit superiors are only subadditive (and not
additive). In particular, for disjoint sets $A,B\subset\mathcal{F}$ we have
$d^{\ast}(A\cup B)\leqslant d^{\ast}(A)+d^{\ast}(B)$ and equality may not
hold. As an example, the sets

$\displaystyle A$
$\displaystyle=\bigcup_{n\in\mathbb{Z}^{+}}\mathcal{F}(\\{(2n-1)!+1,(2n-1)!+2,\dotsc,(2n)!\\}),$
$\displaystyle B$
$\displaystyle=\bigcup_{n\in\mathbb{Z}^{+}}\mathcal{F}(\\{(2n)!+1,(2n)!+2,\dotsc,(2n+1)!\\})$

are disjoint and both have density 1.

Despite this, in the group of non-negative integers
$\mathcal{F}=\mathbb{Z}^{+}$, $d^{\ast}(B)$ satisfies some useful properties.
For example, it holds that $\lvert d^{I}(x+B)-d^{I}(B)\rvert\leqslant x/\lvert
I\rvert$. This implies that $d^{\ast}(x+B)=d^{\ast}(B)$. Even more
importantly, if $x_{1},\dots,x_{n}\in\mathbb{Z}^{+}$ are such that
$x_{1}+B,\dots,x_{n}+B$ are disjoint, then
$d^{I}(x_{1}+B)+\dots+d^{I}(x_{n}+B)\leqslant 1$, implying that

$n\cdot
d^{I}(B)\leqslant\sum_{i=1}^{n}\left(d^{I}(x_{i}+B)+\frac{x_{i}}{\lvert
I\rvert}\right)\leqslant 1+\sum_{i=1}^{n}\frac{x_{i}}{\lvert I\rvert}$

and so $n\cdot d^{\ast}(B)\leqslant 1$. Not only can this provide upper bounds
on the density of $B$, but if we knew that $d^{\ast}(B)>1/n$, we could
conclude that the sets $x_{1}+B,\dots,x_{n}+B$ cannot all be disjoint and
thereby deduce some structural information about $B$. Such arguments were used
by Łuczak and Schoen [Łuc95, ŁS97] for their results about sum-free subsets of
the non-negative integers.

If $\lvert\mathcal{A}\rvert>1$, these arguments no longer work. For example,
if $w\in\mathcal{F}$, it is easy to see that
$d^{\ast}(wB)=\lvert\mathcal{A}\rvert^{-\lvert w\rvert}\cdot d^{\ast}(B)$
where $wB\coloneqq\\{wb\colon b\in B\\}$. Also, the fact that
$w_{1}B,\dots,w_{n}B$ are disjoint gives no general upper bound on the density
of $B$. Even if we consider nested sets $B,wB,\dots,w^{n}B$, taking
$B\coloneqq\mathcal{F}\setminus(w\mathcal{F})$ provides an example where these
sets are pairwise disjoint, but
$d^{\ast}(B)=1-\lvert\mathcal{A}\rvert^{-\lvert w\rvert}$ which can be
arbitrarily close to $1$.

We address these issues in the next section. By modifying the density that we
consider, we can ensure that the density is additive. Importantly, the density
of the set $S\subset\mathcal{F}$ whose upper Banach density we want to bound
will not change. Moreover, in certain situations, we prove that $n$ disjoint
nested copies of $B$ imply that the density of $B$ is at most $1/n$. This will
be crucial for proving our structural results.

##  3 Diagonalisation and relative density

Throughout the paper $S\subset\mathcal{F}$ will be a fixed set whose upper
Banach density we wish to bound (for example, $S$ might be $k$-product-free).
There is a sequence of intervals $(I_{j})$ such that $I_{j}\to\infty$ and

$d^{I_{j}}(S)\to d^{\ast}(S),\quad\text{as }j\to\infty.$

Let $B\subset\mathcal{F}$ be another set. The sequence $(d^{I_{j}}(B))$ is
bounded (all terms are in $[0,1]$) and so, by the Bolzano-Weierstrass theorem,
has a convergent subsequence. In particular, by passing to a subsequence of
$(I_{j})$, we may assume that $d^{I_{j}}(S)\to d^{\ast}(S)$ and
$(d^{I_{j}}(B))$ converges to some limit that we will call
_$d^{I_{\infty}}(B)$_. Given a countable collection of subsets of
$\mathcal{F}$, we may, by a diagonalisation argument, assume there is a
subsequence $(I_{j})$ such that $d^{I_{j}}(B)\to d^{I_{\infty}}(B)$ for every
$B$ in the collection where $d^{I_{\infty}}(S)=d^{\ast}(S)$. Throughout this
paper we will only ever consider countably many sequences and so this
convergence occurs for all sets we consider. These limits, unlike the
corresponding upper Banach densities, are additive. Indeed, if sets $A$ and
$B$ are disjoint, then $d^{I_{j}}(A\cup B)=d^{I_{j}}(A)+d^{I_{j}}(B)$ and so
$d^{I_{\infty}}(A\cup B)=d^{I_{\infty}}(A)+d^{I_{\infty}}(B)$. It should be
noted that while $d^{I_{\infty}}(S)=d^{\ast}(S)$, we only have
$d^{I_{\infty}}(B)\leqslant d^{\ast}(B)$ for the other sets that we consider.

For our structural proofs we will need not only to bound the density of a
product-free set $S$ but also to bound the density of $S$ on subtrees. We now
begin to define this.

The product _AB_ of two sets $A,B\subset\mathcal{F}$ is

$AB\coloneqq\\{ab\colon a\in A,b\in B\\}$

and the set $B^{k}$ is the product of $k$ copies of $B$. Note that $B$ is
$k$-product-free exactly if $B\cap B^{k}=\varnothing$. A particular important
example of a product is $w\mathcal{F}$ for a word $w\in\mathcal{F}$: this is
exactly the subtree of $\mathcal{F}$ consisting of all words starting with
$w$. Similarly $B\mathcal{F}$ is exactly the set of words that have a prefix
in $B$.

For a finite set $B\subset\mathcal{F}$ we write _$\min B$_ and _$\max B$_ for
the length of the shortest and longest words in $B$, respectively. Note that
if $B$ is finite, then for $n\geqslant\max B$ the random infinite word
$\mathbf{W}$ hits $(B\mathcal{F})(n)$ if and only if it hits $B$.

######  Observation 3.1.

If $n\geqslant\lvert w\rvert$, then $\mu((w\mathcal{F})(n))=\mu(w)$. If
$C\subset\mathcal{F}$ is prefix-free and finite, then
$\mu((C\mathcal{F})(n))=\mu(C)$ for $n\geqslant\max C$.

######  Definition 3.2 (relative density).

Let $w\in\mathcal{F}$ and $B\subset\mathcal{F}$. For $n\geqslant\lvert
w\rvert$, the relative density of $B$ in $w\mathcal{F}$ on layer $n$ is

$\frac{\lvert B(n)\cap w\mathcal{F}\rvert}{\lvert\mathcal{F}(n)\cap
w\mathcal{F}\rvert}=\frac{\mu(B(n)\cap w\mathcal{F})}{\mu(\mathcal{F}(n)\cap
w\mathcal{F})}=\frac{\mu(B(n)\cap w\mathcal{F})}{\mu(w)}$

which is the probability that $\mathbf{W}_{n}$ is in $B$ conditioned on the
event that $\mathbf{W}$ hits $w$. If $n<\lvert w\rvert$, then we will take the
relative density to be $0$ by convention.

Furthermore, if $I$ is an interval with $\min I\geqslant\lvert w\rvert$, then
the _relative density of $B$ in $w\mathcal{F}$ on interval $I$_ is

$d_{w\mathcal{F}}^{I}(B)\coloneqq\frac{\mu(B(I)\cap
w\mathcal{F})}{\mu(\mathcal{F}(I)\cap w\mathcal{F})}=\lvert
I\rvert^{-1}\mu(w)^{-1}\sum_{n\in I}\mu(B(n)\cap
w\mathcal{F})=\mu(w)^{-1}\cdot d^{I}(B\cap w\mathcal{F}).$

If $\min I<\lvert w\rvert$, then we will take the relative density to be $0$
by convention.

Note that if $w$ is the empty word then this relative density is just
$d^{I}(B)$.

Consider the sequence of intervals $(I_{j})$ given above where
$d^{I_{j}}(B)\to d^{I_{\infty}}(B)$ for every set $B$ in a countable
collection. For each word $w\in\mathcal{F}$ and each set in the collection,
the sequence $(d_{w\mathcal{F}}^{I_{j}}(B))$ is bounded (all terms are in
$[0,1]$) and so, by the Bolzano-Weierstrass theorem, has a convergent
subsequence. Since $\mathcal{F}$ is countable (it consists of only finite
words) we may, via a diagonalisation argument, pass to a subsequence $(I_{j})$
such that, for every $w\in\mathcal{F}$ and every $B$ in the countable
collection, $(d_{w\mathcal{F}}^{I_{j}}(B))$ converges to some limit
_$d^{I_{\infty}}_{w\mathcal{F}}(B)$_. In conclusion, we may assume throughout
the paper that for any set $B$ we encounter and for all $w\in\mathcal{F}$ we
have

$d_{w\mathcal{F}}^{I_{j}}(B)\to d^{I_{\infty}}_{w\mathcal{F}}(B),$

where $d^{I_{\infty}}(B)\leqslant d^{\ast}(B)$ and
$d^{I_{\infty}}(S)=d^{\ast}(S)$ for one fixed set $S$. As before, these limits
are additive. They satisfy the useful property that we may strip away
prefixes.

######  Lemma 3.3.

If $w,v\in\mathcal{F}$, then
$d^{I_{\infty}}_{wv\mathcal{F}}(wB)=d^{I_{\infty}}_{v\mathcal{F}}(B)$.

###### Proof.

Let $I$ be any interval with $\min I>\lvert wv\rvert$. Now

$d^{I}_{wv\mathcal{F}}(wB)=\lvert I\rvert^{-1}\mu(wv)^{-1}\sum_{n\in
I}\mu((wB)(n)\cap wv\mathcal{F}).$

Removing the leading $w$ from each word in $(wB)(n)\cap wv\mathcal{F}$ shows
that $\mu((wB)(n)\cap wv\mathcal{F})=\mu(w)\cdot\mu(B(n-\lvert w\rvert)\cap
v\mathcal{F})$. Also $\mu(wv)=\mu(w)\mu(v)$ and so

$d^{I}_{wv\mathcal{F}}(wB)=\lvert I\rvert^{-1}\mu(v)^{-1}\sum_{n\in I-\lvert
w\rvert}\mu(B(n)\cap v\mathcal{F}),$

where $I-\lvert w\rvert$ is the interval obtained by subtracting $\lvert
w\rvert$ from each element of $I$. Thus

$\lvert d^{I}_{wv\mathcal{F}}(wB)-d^{I}_{v\mathcal{F}}(B)\rvert=\lvert
I\rvert^{-1}\mu(v)^{-1}\cdot\bigg{\lvert}\sum_{n\in I-\lvert
w\rvert}\mu(B(n)\cap v\mathcal{F})-\sum_{n\in I}\mu(B(n)\cap
v\mathcal{F})\bigg{\rvert}$

But, for each integer $n$, $\mu(B(n)\cap v\mathcal{F})\in[0,1]$ and so

$\lvert d^{I}_{wv\mathcal{F}}(wB)-d^{I}_{v\mathcal{F}}(B)\rvert\leqslant\lvert
I\rvert^{-1}\mu(v)^{-1}\cdot\lvert w\rvert$

Setting $I=I_{j}$ and taking $j$ to infinity gives the required result. ∎

We are now ready to make an important definition that captures the densest
that a set $B$ can be down a subtree.

######  Definition 3.4 (sup density).

For a set $B$ in the countable collection, the _sup density of $B$_ is

$d_{\sup}^{I_{\infty}}(B)\coloneqq\sup_{w\in\mathcal{F}}d^{I_{\infty}}_{w\mathcal{F}}(B).$

Of course, the sup density satisfies $d_{\sup}^{I_{\infty}}(B)\geqslant
d^{I_{\infty}}(B)$ (note that the empty word is in $\mathcal{F}$) and so
$d_{\sup}^{I_{\infty}}(S)\geqslant d^{\ast}(S)$.

We will prove the following strengthening of Theorems 1.3 and 1.6 in Section
7.

######  Theorem 3.5.

Let $k\geqslant 2$ be an integer, $\mathcal{A}$ be a finite set, and
$\mathcal{F}$ be the free semigroup with alphabet $\mathcal{A}$.

  1. (a)

If $S\subset\mathcal{F}$ is strongly $k$-product-free, then
$d^{\ast}(S)\leqslant 1/k$. Moreover, if $d^{\ast}(S)=1/k$, then
$d_{\sup}^{I_{\infty}}(S)=1/k$.

  2. (b)

If $S\subset\mathcal{F}$ is $k$-product-free, then $d^{\ast}(S)\leqslant
1/\rho(k)$. Moreover, if $d^{\ast}(S)=1/\rho(k)$, then
$d_{\sup}^{I_{\infty}}(S)=1/\rho(k)$.

This strengthening is needed for our structural results, Theorems 1.4 and 1.7.
For example, if $S\subset\mathcal{F}$ is strongly $k$-product-free with
$d^{\ast}(S)=1/k$, then by (a),
$d^{I_{\infty}}(S)=d^{\ast}(S)=d_{\sup}^{I_{\infty}}(S)$. This suggests that
$S$ is uniformly distributed down subtrees which is made precise by the
following lemma.

######  Lemma 3.6.

If $d^{I_{\infty}}(B)=d_{\sup}^{I_{\infty}}(B)$, then
$d^{I_{\infty}}_{w\mathcal{F}}(B)=d^{I_{\infty}}(B)$ for every word
$w\in\mathcal{F}$.

###### Proof.

Let $\ell$ be a non-negative integer and let $I$ be an interval with $\min
I>\ell$. Every word of length greater than $\ell$ is in exactly one
$w\mathcal{F}$ (where $w\in\mathcal{F}(\ell)$). Hence,

$d^{I}(B)=\sum_{w\in\mathcal{F}(\ell)}d^{I}(B\cap
w\mathcal{F})=\sum_{w\in\mathcal{F}(\ell)}\mu(w)\cdot
d^{I}_{w\mathcal{F}}(B).$

Setting $I=I_{j}$ and taking $j$ to infinity gives

$d^{I_{\infty}}(B)=\sum_{w\in\mathcal{F}(\ell)}\mu(w)\cdot
d^{I_{\infty}}_{w\mathcal{F}}(B).$

Now $\sum_{w\in\mathcal{F}(\ell)}\mu(w)=\mu(\mathcal{F}(\ell))=1$ and every
$w\in\mathcal{F}(\ell)$ satisfies $d^{I_{\infty}}_{w\mathcal{F}}(B)\leqslant
d_{\sup}^{I_{\infty}}(B)=d^{I_{\infty}}(B)$. Hence we must have
$d^{I_{\infty}}_{w\mathcal{F}}(B)=d^{I_{\infty}}(B)$ for every
$w\in\mathcal{F}(\ell)$. The integer $\ell$ was arbitrary and so we have the
required result. ∎

The next two lemmas are the key technical results for our structural proofs.
We remark that for the non-negative integers (that is, when
$\lvert\mathcal{A}\rvert=1$) they are much more obvious.

######  Lemma 3.7.

Let $S\subset\mathcal{F}$ be such that
$d^{I_{\infty}}(S)=d_{\sup}^{I_{\infty}}(S)>1/n$. Then, for any
$w_{1},\dotsc,w_{n}\in\mathcal{F}$, the sets

$w_{1}S,\quad w_{1}w_{2}S,\quad\dotsc,\quad w_{1}w_{2}\dotsb w_{n-1}S,\quad
w_{1}w_{2}\dotsb w_{n}S$

cannot be pairwise disjoint.

###### Proof.

Assume that these sets are pairwise disjoint. Then, for any word
$w\in\mathcal{F}$,

$d^{I_{\infty}}_{w\mathcal{F}}(w_{1}S)+\dots+d^{I_{\infty}}_{w\mathcal{F}}(w_{1}\dotsb
w_{n}S)=d^{I_{\infty}}_{w\mathcal{F}}((w_{1}S)\cup\dots\cup(w_{1}\dotsb
w_{n}S))\leqslant 1.$

Choose $w=w_{1}\dotsb w_{n}$. Applying Lemma 3.3 to each term gives

$d^{I_{\infty}}_{w_{2}\dotsb
w_{n}\mathcal{F}}(S)+\dotsb+d^{I_{\infty}}_{w_{n}\mathcal{F}}(S)+d^{I_{\infty}}_{\mathcal{F}}(S)\leqslant
1.$

By Lemma 3.6, each term is $d^{I_{\infty}}(S)$ which contradicts
$d^{I_{\infty}}(S)>1/n$, as required. ∎

######  Lemma 3.8.

Let $S\subset\mathcal{F}$ be such that
$d^{I_{\infty}}(S)=d_{\sup}^{I_{\infty}}(S)>2/(2n-1)$. Then, for any
$w_{1},\dotsc,w_{n},v_{1},\dotsc,v_{n}\in\mathcal{F}$ and $C\subset S$, either
the sets

$w_{1}S,\quad w_{1}w_{2}S,\quad\dotsc,\quad w_{1}\dotsb w_{n-1}S,\quad
w_{1}\dotsb w_{n}C$

or the sets

$v_{1}S,\quad v_{1}v_{2}S,\quad\dotsc,\quad v_{1}\dotsb v_{n-1}S,\quad
v_{1}\dotsb v_{n}(S\setminus C)$

are not pairwise disjoint.

###### Proof.

Assume that both collections of sets are pairwise disjoint. Then, as in the
proof of Lemma 3.7,

$d^{I_{\infty}}_{w_{2}\dotsb
w_{n}\mathcal{F}}(S)+\dots+d^{I_{\infty}}_{w_{n}\mathcal{F}}(S)+d^{I_{\infty}}_{\mathcal{F}}(C)\leqslant
1$

and

$d^{I_{\infty}}_{v_{2}\dotsb
v_{n}\mathcal{F}}(S)+\dots+d^{I_{\infty}}_{v_{n}\mathcal{F}}(S)+d^{I_{\infty}}_{\mathcal{F}}(S\setminus
C)\leqslant 1.$

Note that $d^{I_{\infty}}_{\mathcal{F}}(S\setminus
C)=d^{I_{\infty}}_{\mathcal{F}}(S)-d^{I_{\infty}}_{\mathcal{F}}(C)$. Applying
this and adding the two inequalities, we get

$\displaystyle d^{I_{\infty}}_{w_{2}\dotsb
w_{n}\mathcal{F}}(S)+\dots+d^{I_{\infty}}_{w_{n}\mathcal{F}}(S)+d^{I_{\infty}}_{v_{2}\dotsb
v_{n}\mathcal{F}}(S)+\dots+d^{I_{\infty}}_{\mathcal{F}}(S)\leqslant 2.$

However, by Lemma 3.6, each term is $d^{I_{\infty}}(S)$ which contradicts
$d^{I_{\infty}}(S)>2/(2n-1)$, as required. ∎

##  4 Structure of strongly $k$-product-free sets

In this section we prove Theorem 1.4 assuming Theorem 3.5. Therefore, let
$S\subset\mathcal{F}$ be strongly $k$-product-free satisfying
$d^{\ast}(S)=1/k$. Note, by Theorem 3.5, that
$d^{I_{\infty}}(S)=1/k=d_{\sup}^{I_{\infty}}(S)$ and so we may and will
frequently apply Lemmas 3.7 and 3.8 with $n=k+1$.

We want to show that we can label each letter of $\mathcal{A}$ with a label in
$\mathbb{Z}/k\mathbb{Z}$ such that $S$ is a subset of

$T\coloneqq\\{a\in\mathcal{F}\colon\text{the sum of the labels of letters in
$a$ is }1\bmod{k}\\}.$

Assume that each $a\in\mathcal{F}$ is labelled with this sum. To deduce the
structure of $S$, we would like to identify these labels for all words
$a\in\mathcal{F}$. Clearly, everything in $S$ should be labelled $1$. For any
other $a\in\mathcal{F}$, appending a word from $S$ should increase the label
by $1$. So, if $a$ has label $\ell$ and we append
$i=-\ell\in\mathbb{Z}/k\mathbb{Z}$ words from $S$ to $a$, we should get the
label $0$, and appending one more word from $S$ should give the label $1$,
which might itself be a word from $S$. On the other hand, for any other
$j\in\mathbb{Z}/k\mathbb{Z}$, appending $j+1$ words from $S$ to $a$ should
give a label different from $1$ and should therefore never yield a word from
$S$.

Based on this intuition, for $i=0,1,\dotsc,k-1$ define

$T_{i}\coloneqq\\{a\in\mathcal{F}\colon S\cap aS^{i+1}\neq\varnothing\\}.$

Then, everything in $T_{i}$ should have the label
$-i\in\mathbb{Z}/k\mathbb{Z}$. So, we expect that $S\subset T_{k-1}$ and that
$T_{i}T_{j}\subset T_{i+j}$. This is exactly what we will show and which
allows us to deduce the structure of $T_{k-1}$, which will be the set $T$ from
above.

######  Remark 4.1.

Throughout we will view the indices of the $T_{i}$ as elements of
$\mathbb{Z}/k\mathbb{Z}$ and, in particular, all addition of indices is modulo
$k$.

Note that our definition of $T_{i}$ is slightly arbitrary. Whether we append
or prepend words from $S$ to some $a\in\mathcal{F}$, the change in the label
of $a$ should always be the same. So, we could also have defined $T_{i}$ as
the set $\\{a\in\mathcal{F}\colon S\cap S^{i+1}a\neq\varnothing\\}$.
Fortunately, the following result tells us that these definitions are
equivalent.

######  Proposition 4.2.

For any positive integer $r$ and any $a\in\mathcal{F}$,

$S\cap S^{r}a\neq\varnothing\Leftrightarrow S\cap
S^{r-1}aS\neq\varnothing\Leftrightarrow\dotsb\Leftrightarrow S\cap
SaS^{r-1}\neq\varnothing\Leftrightarrow S\cap aS^{r}\neq\varnothing.$

###### Proof.

We first prove the case $r=1$. Suppose that $S\cap Sa\neq\varnothing$. Then
there is some $x$ such that $x,xa\in S$. Consider the sets
$S,xS,x^{2}S,\dotsc,x^{k-1}S,x^{k-1}aS=x^{k-2}(xa)S$. By Lemma 3.7, these
cannot all be pairwise disjoint. Since $S$ is strongly $k$-product-free and
$x\in S$, the sets $S,xS,\dotsc,x^{k-1}S$ are pairwise disjoint. Since $S$ is
strongly $k$-product-free and $xa\in S$, the sets
$S,xS,\dotsc,x^{k-2}S,x^{k-2}(xa)S$ are pairwise disjoint. Thus $x^{k-1}S$ and
$x^{k-1}aS$ are not disjoint and so $S\cap aS\neq\varnothing$.

Let $f\colon\mathcal{F}\to\mathcal{F}$ be the _reverse map_ that reverses each
word of $\mathcal{F}$ (that is, reads them from right to left). The function
$f$ is a measure-preserving involution. Let $\overline{S}=f(S)$. Now
$\overline{S}$ is a strongly $k$-product-free subset of $\mathcal{F}$ with
$d^{\ast}(\overline{S})=d^{\ast}(S)=1/k$. In particular, the previous
paragraph shows that
$\overline{S}\cap\overline{S}a\neq\varnothing\Rightarrow\overline{S}\cap
a\overline{S}\neq\varnothing$. Now, $\overline{S}\cap\overline{S}a=f(S\cap
aS)$ and $\overline{S}\cap a\overline{S}=f(S\cap Sa)$ and so $S\cap
aS\neq\varnothing\Rightarrow S\cap Sa\neq\varnothing$ concluding the case
$r=1$.

For the general case it suffices to prove that for all non-negative integers
$i,j$: $S\cap S^{i+1}aS^{j}\neq\varnothing\Leftrightarrow S\cap
S^{i}aS^{j+1}\neq\varnothing$. Suppose that $S\cap
S^{i+1}aS^{j}\neq\varnothing$. Then there is $x_{i}\in S^{i}$ and $x_{j}\in
S^{j}$ such that $S\cap Sx_{i}ax_{j}\neq\varnothing$. Applying the $r=1$ case
to the word $x_{i}ax_{j}$ shows that $S\cap x_{i}ax_{j}S\neq\varnothing$ and
so $S\cap S^{i}aS^{j+1}\neq\varnothing$. The other direction is analogous. ∎

If the sets $T_{1},\dots,T_{k-1}$ are supposed to correctly identify the
labels of all words $a\in\mathcal{F}$, then every $a$ should be in exactly one
of these sets, and $S$ should satisfy $S\subset T_{k-1}$. This is proved by
the following proposition.

######  Proposition 4.3.

The sets $T_{0}$, $T_{1}$, …, $T_{k-1}$ partition $\mathcal{F}$ and $S\subset
T_{k-1}$.

###### Proof.

Let $a\in\mathcal{F}$ and $x\in S$. Consider the sets $S$, $aS$, $axS$,
$ax^{2}S$, …, $ax^{k-1}S$. By Lemma 3.7, these cannot all be pairwise
disjoint. Since $S$ is strongly $k$-product-free and $x\in S$, the sets $aS$,
$axS$, …, $ax^{k-1}S$ are pairwise disjoint. Hence there is some
$r\in\\{0,1,\dotsc,k-1\\}$ such that $S\cap ax^{r}S\neq\varnothing$ and so
$S\cap aS^{r+1}\neq\varnothing$. That is, $\cup_{r=0}^{k-1}T_{r}=\mathcal{F}$.

We next show that the $T_{i}$ are pairwise disjoint (and so partition
$\mathcal{F}$). Suppose that $a\in T_{i}\cap T_{j}$ where $0\leqslant
i<j\leqslant k-1$. Since $a\in T_{i}$, $S\cap SaS^{i}\neq\varnothing$ and so
there is $x\in S$ and $y\in S^{i}$ such that $xay\in S$. Let

$C\coloneqq\\{s\in S\colon ays\in S\\}\subset S.$

Consider the $k+1$ sets

$S,\quad xS,\quad x^{2}S,\quad\dotsc,\quad x^{k-1}S,\quad x^{k-1}ay(S\setminus
C).$

As $S$ is strongly $k$-product-free and $x\in S$, the first $k$ of these sets
are pairwise disjoint. Similarly, noting that $x^{k-1}ay=x^{k-2}(xay)$ and
$xay\in S$, we have that the last set is disjoint from each of the first
$k-1$. Finally, the last two sets are disjoint by the definition of $C$.
Hence, all $k+1$ sets are pairwise disjoint.

Since $a\in T_{j}$ there are $z_{1},\dotsc,z_{j+1}\in S$ such that
$z_{1}\dotsb z_{j+1}a\in S$. Consider the $k+1$ sets

$S,\quad z_{1}S,\quad z_{1}^{2}S,\quad\dotsc,\quad z_{1}^{k-j}S,\quad
z_{1}^{k-j}z_{2}S,\quad\dotsc,\quad z_{1}^{k-j}z_{2}\dotsb z_{j}S,\quad
z_{1}^{k-j}z_{2}\dotsb z_{j+1}ayC.$

The first $k$ of these sets are pairwise disjoint as $S$ is strongly
$k$-product-free. Similarly, noting that $z_{1}z_{2}\dotsb z_{j+1}a\in S$, the
last set is disjoint from each of $S$, $z_{1}S$, …, $z_{1}^{k-j-1}S$. Now, by
the definition of $C$, $ayC\subset S$. Using this and product-freeness shows
that the last set is disjoint from each of $z_{1}^{k-j}S$,
$z_{1}^{k-j}z_{2}S$, …, $z_{1}^{k-j}z_{2}\dotsb z_{j}S$. Hence, all $k+1$ sets
are pairwise disjoint. This contradicts Lemma 3.8 and so the $T_{i}$ do
partition $\mathcal{F}$.

It remains to show that $S\subset T_{k-1}$. Since $S$ is strongly $k$-product-
free, for any $x\in S$, the set $S$ is disjoint from each of $xS$, $xS^{2}$,
…, $xS^{k-1}$ and so $x\notin T_{0}\cup\dotsb\cup T_{k-2}$. Since the $T_{i}$
partition $\mathcal{F}$, we must have $x\in T_{k-1}$, as required. ∎

Given these two results, we already know that $a\in T_{i}$ should be labelled
by $-i\in\mathbb{Z}/k\mathbb{Z}$. Next, we want to show that the label of a
product $ab$ should be the sum of the labels of $a$ and $b$. We begin by
proving that this is true whenever we append a word from $S$.

######  Proposition 4.4.

The following hold for all $j\in\mathbb{Z}/k\mathbb{Z}$.

  1. (a)

If $ax\in T_{j}$ and $x\in S$, then $a\in T_{j+1}$.

  2. (b)

$T_{j+1}S\subset T_{j}$.

###### Proof.

We first prove (a). Suppose that $0\leqslant j\leqslant k-2$. We have $S\cap
axS^{j+1}\neq\varnothing$ and $x\in S$, so $S\cap aS^{j+2}\neq\varnothing$ and
so $a\in T_{j+1}$.

Now suppose that $j=k-1$. Consider the sets $S$, $aS$, $axS$, $ax^{2}S$, …,
$ax^{k-1}S$. By Lemma 3.7, these cannot all be pairwise disjoint. Since $S$ is
strongly $k$-product-free and $x\in S$, the sets $aS$, $axS$, …, $ax^{k-1}S$
are pairwise disjoint. Also, as $ax\in T_{k-1}$ (and so $ax$ is not in
$T_{0}\cup T_{1}\cup\dotsb\cup T_{k-2}$ by Proposition 4.3), $S$ is disjoint
from each of $axS$, $ax^{2}S$, …, $ax^{k-1}S$. Thus $S$ and $aS$ are not
disjoint and so $a\in T_{0}$, as required.

We now prove (b). Let $a\in T_{j+1}$ and $x\in S$. Suppose that $ax\in T_{i}$
(such an $i$ exists by Proposition 4.3). By (a), $i+1=j+1\bmod{k}$ and so
$i=j\bmod{k}$, as required. ∎

It is now an easy consequence that the labels of all $T_{i}$ are very well-
behaved with respect to products.

######  Proposition 4.5.

For all $i,j\in\mathbb{Z}/k\mathbb{Z}$, $T_{i}T_{j}\subset T_{i+j}$.

###### Proof.

Let $a\in T_{i}$ and $b\in T_{j}$. As $b\in T_{j}$ there are
$x_{1},x_{2},\dotsc,x_{j+1}\in S$ such that $bx_{1}x_{2}\dotsb x_{j+1}\in S$.
By Proposition 4.4(b),

$abx_{1}\dotsb x_{j+1}=a(bx_{1}\dotsb x_{j+1})\in T_{i-1}.$

Applying Proposition 4.4(a) $j+1$ times, once to remove each $x_{\ell}$, gives
$ab\in T_{i-1+(j+1)}=T_{i+j}$, as required. ∎

Finally, this allows us to complete the proof of Theorem 1.4.

###### Proof of Theorem 1.4.

For each letter $\alpha\in\mathcal{A}$, there is, by Proposition 4.3, a unique
$i\in\mathbb{Z}/k\mathbb{Z}$ such that $\alpha\in T_{i}$. Label $\alpha$ with
$i$. By Proposition 4.5, for each $i$,

$T_{i}=\\{w\in\mathcal{F}\colon\text{the sum of the labels of letters in $w$
is }i\bmod{k}\\}.$

In particular, by Proposition 4.3,

$S\subset T_{k-1}=\\{w\in\mathcal{F}\colon\text{the sum of the labels of
letters in $w$ is }-1\bmod{k}\\}.$

Note that $T_{k-1}$ is strongly $k$-product-free: if $w$ is the concatenation
of $\ell$ words from $T_{k-1}$, then the sum of the labels of letters in $w$
is $-\ell\bmod{k}$.

To obtain the result given in the statement of Theorem 1.4 (i.e. with
$1\bmod{k}$ instead of $-1\bmod{k}$) simply multiply the label of each letter
by $-1$. ∎

##  5 Structure of $k$-product-free sets

In this section we prove Theorem 1.7 assuming Theorem 3.5. Let $k\geqslant 2$
be an integer with $k\notin\\{3,5,7,13\\}$, let $\rho=\rho(k)$, and let
$S\subset\mathcal{F}$ be $k$-product-free satisfying $d^{\ast}(S)=1/\rho$.
Note, by Theorem 3.5, that $d^{I_{\infty}}(S)=1/\rho=d_{\sup}^{I_{\infty}}(S)$
and so we may and will frequently apply Lemma 3.7 with $n=\rho+1$.

We will show that, in fact, $S$ is strongly $\rho$-product-free and so the
result follows from Theorem 1.4. To this end we make the following definition.

######  Definition 5.1.

For a set $A\subset\mathbb{Z}^{+}$, the set _$S_{A}$_ $\subset\mathcal{F}$ is

$S_{A}\coloneqq\bigcap_{i\in A}S^{i},$

where we will omit set parentheses so, for example, $S_{1}=S$ and
$S_{1,3}=S\cap S^{3}$.

Since $S$ is $k$-product-free, $S_{1,k}=\varnothing$. It is enough for us to
show that $S_{1,2}=S_{1,3}=\dotsb=S_{1,\rho}=\varnothing$ as then $S$ is
strongly $\rho$-product-free. Note that the case $k=2$ is immediate and so we
assume that $k\geqslant 3$ from now on.

We need a quick technical lemma about the size of $\rho$.

######  Lemma 5.2.

Let $k\geqslant 3$ be an integer with $k\notin\\{3,5,7,13\\}$ and let
$\rho=\rho(k)$. Then

$k-1\geqslant\max\\{(\rho-t)t(t+1)\colon t\in\\{1,2,\dotsc,\rho-1\\}\\}.$ (1)

###### Proof.

By the arithmetic mean-geometric mean inequality, for any $t\in[0,\rho]$,

$(\rho-t)t(t+1)=4(\rho-t)\tfrac{t}{2}\tfrac{t+1}{2}\leqslant
4\bigl{(}\tfrac{\rho+1/2}{3}\bigr{)}^{3}=4/27\cdot(\rho+1/2)^{3}.$

On the other hand, Lev [Lev03, Lem. 18] proved that, for all positive integers
$k\geqslant 2$,

$\rho(k)\leqslant 2\log_{2}k+2.$

Now, for all $k\geqslant 2400$,

$k-1\geqslant 4/27\cdot(2\log_{2}k+5/2)^{3},$

and so (1) holds. Now, if $\rho\geqslant 10$, then $k-1\geqslant 5\times
7\times 8\times 9=2520$ and so (1) holds. We are left to check the remaining
cases.

  * •

If $\rho=2$, then the right-hand side of (1) is 2. The smallest $k\geqslant 3$
with $\rho=2$ is 4.

  * •

If $\rho=3$, then the right-hand side of (1) is 6. The only $k\leqslant 6$
with $\rho=3$ are 3 and 5.

  * •

If $\rho=4$, then the right-hand side of (1) is 12. The only $k\leqslant 12$
with $\rho=4$ is 7.

  * •

If $\rho=5$, then the right-hand side of (1) is 24. The only $k\leqslant 24$
with $\rho=5$ is 13.

  * •

$\rho$ is always the power of a prime so there are no $k$ with $\rho=6$.

  * •

If $\rho=7$, then the right-hand side of (1) is 60. The smallest $k$ with
$\rho=7$ is $61$.

  * •

If $\rho=8$, then the right-hand side of (1) is 90. The smallest $k$ with
$\rho=8$ is $421$.

  * •

If $\rho=9$, then the right-hand side of (1) is 126. The smallest $k$ with
$\rho=9$ is 841.∎

We first show that $S_{1,\rho}$ is empty.

######  Proposition 5.3.

$S_{1,\rho}=\varnothing$.

###### Proof.

Suppose that $S_{1,\rho}\neq\varnothing$ and let $t\in\mathbb{Z}^{+}$ be
maximal with $S_{1,\rho,2\rho-1,\dotsc,t(\rho-1)+1}\neq\varnothing$ where the
indices form an arithmetic progression with common difference $\rho-1$. Such a
$t$ must exist as $k\equiv 1\bmod{\rho-1}$ and $S_{1,k}=\varnothing$. Let
$w\in S_{1,\rho,2\rho-1,\dotsc,t(\rho-1)+1}$.

Taking $t=\rho-1$ inside the maximum in (1), we have
$k-1\geqslant\rho(\rho-1)$. We split into two cases based on the size of $k$.

First suppose that $k-1>2\rho(\rho-1)$. Let $\alpha\in\mathbb{Z}^{+}$ be
minimal such that $(\alpha-1)\rho(\rho-1)\geqslant k-1$. Note that
$\alpha\geqslant 4$. Write $\rho=2a+b$ where $a=\lfloor\rho/2\rfloor$ and
$b\in\\{0,1\\}$. Consider the following sets

$\displaystyle S,\quad w^{\rho-1}S,\qquad w^{\alpha(\rho-1)}S,\quad
w^{(\alpha+1)(\rho-1)}S,\qquad w^{2\alpha(\rho-1)},\quad
w^{(2\alpha+1)(\rho-1)}S\quad\dotsc,$ $\displaystyle
w^{(a-1)\alpha(\rho-1)}S,\quad w^{((a-1)\alpha+1)(\rho-1)}S,\qquad
w^{a\alpha(\rho-1)}S,\quad w^{(a\alpha+b)(\rho-1)}S.$

We remark that these sets are formed by starting with $S$ and then alternating
between prepending $w^{\rho-1}$ and $w^{(\alpha-1)(\rho-1)}$. Two sets that
differ only be a prepending of $w^{\rho-1}$ are called a _pair_ : the pairs
are the first and second sets; the third and fourth sets; …. The number of
sets listed is $2a+b+1=\rho+1$ and so these cannot all be pairwise disjoint by
Lemma 3.7.

We first show that sets in different pairs are disjoint. If two such sets
meet, then $S\cap w^{\ell(\rho-1)}S\neq\varnothing$ for some integer $\ell$
satisfying $\alpha-1\leqslant\ell\leqslant a\alpha+b$. We will show that, for
such an $\ell$, $w^{\ell(\rho-1)}\in S^{k-1}$ which contradicts
$S_{1,k}=\varnothing$. Since $w\in S_{1,\rho,2\rho-1,\dotsc,t(\rho-1)+1}$, we
have $w^{\ell(\rho-1)}\in
S_{\ell(\rho-1),(\ell+1)(\rho-1),\dotsc,\ell(\rho-1)(t(\rho-1)+1)}$ where the
indices form an arithmetic progression with common difference $\rho-1$. It
suffices to show that $k-1$ is in this arithmetic progression. Since $k-1$ is
a multiple of $\rho-1$, it is enough to show that $\ell(\rho-1)\leqslant
k-1\leqslant\ell(\rho-1)(t(\rho-1)+1)$ for all integers $\ell$ satisfying
$\alpha-1\leqslant\ell\leqslant a\alpha+b$. Now,

$\ell(\rho-1)(t(\rho-1)+1)\geqslant\ell(\rho-1)\rho\geqslant(\alpha-1)\rho(\rho-1)\geqslant
k-1$

and

$\displaystyle\ell(\rho-1)$
$\displaystyle\leqslant(a\alpha+b)(\rho-1)=(a\alpha+\rho-2a)(\rho-1)$
$\displaystyle=a(\alpha-2)(\rho-1)+\rho(\rho-1)\leqslant\rho/2\cdot(\alpha-2)(\rho-1)+\rho(\rho-1)$
$\displaystyle=\alpha/2\cdot\rho(\rho-1)\leqslant(\alpha-2)\rho(\rho-1)<k-1,$

where we used the minimality of $\alpha$ and the fact that $\alpha\geqslant 4$
in the final and penultimate inequality respectively.

We second show that sets in the same pair are disjoint which gives the
contradiction required to conclude the case $k-1>2\rho(\rho-1)$. If two sets
in the same pair are not disjoint, then $S\cap w^{\rho-1}S\neq\varnothing$.
But $w^{\rho-1}\in S_{\rho-1,2(\rho-1),\dotsc,(t(\rho-1)+1)(\rho-1)}$ and so
if $S\cap w^{\rho-1}S\neq\varnothing$, then
$S_{1,\rho,2\rho-1,\dotsc,(t(\rho-1)+1)(\rho-1)+1}\neq\varnothing$ which
contradicts the maximality of $t$.

Second suppose that $2\rho(\rho-1)\geqslant k-1\geqslant\rho(\rho-1)$.
Consider the the following $\rho+1$ sets

$S,\quad w^{\rho-1}S,\quad w^{2(\rho-1)}S,\quad\dotsc,\quad
w^{\rho(\rho-1)}S.$

Since $t$ is maximal, consecutive sets are disjoint as in the previous case.
If non-consecutive sets are not disjoint, then $S\cap
w^{\ell(\rho-1)}S\neq\varnothing$ for some integer $\ell$ satisfying
$2\leqslant\ell\leqslant\rho$. As before, $w^{\ell(\rho-1)}\in
S_{\ell(\rho-1),(\ell+1)(\rho-1),\dotsc,\ell(\rho-1)(t(\rho-1)+1)}$ and so it
suffices to show that $\ell(\rho-1)\leqslant
k-1\leqslant\ell(\rho-1)(t(\rho-1)+1)$ for such $\ell$. This is the case as

$\ell(\rho-1)(t(\rho-1)+1)\geqslant\ell(\rho-1)\rho\geqslant
2\rho(\rho-1)\geqslant k-1$

and

$\ell(\rho-1)\leqslant\rho(\rho-1)\leqslant k-1.$

Thus all $\rho+1$ sets are disjoint contradicting Lemma 3.7 and so
$S_{1,\rho}$ is indeed empty. ∎

We now show that $S_{1,2}$, …, $S_{1,\rho-1}$ are all empty.

######  Proposition 5.4.

For all $1\leqslant d\leqslant\rho-1$, $S_{1,d+1}=\varnothing$.

###### Proof.

We argue via downwards induction on $d$ with the base case $d=\rho-1$ given by
Proposition 5.3. Let $1\leqslant d\leqslant\rho-2$ be largest with
$S_{1,d+1}\neq\varnothing$ and let $t\in\mathbb{Z}^{+}$ be maximal with
$S_{1,d+1,2d+1,\dotsc,td+1}\neq\varnothing$. Such a $t$ exists as $k\equiv
1\bmod{d}$. Let $w\in S_{1,d+1,2d+1,\dotsc,td+1}$.

By the definition of $\rho$, both $d$ and $d+1$ divide $k-1$. Since $d$ and
$d+1$ are coprime we may write $k-1=\alpha d(d+1)$ for some positive integer
$\alpha$. Let $s\in\mathbb{Z}^{+}$ be largest such that $ds\leqslant\rho-1$.
Write $\rho=a(s+1)+b$ where $a=\lfloor\rho/(s+1)\rfloor$ and
$b\in\\{0,1,\dotsc,s\\}$. Consider the following $\rho+1$ sets

$\displaystyle S,\quad w^{d}S,\quad\dotsc,\quad w^{sd}S,\qquad\qquad\qquad
w^{(\alpha+s)d}S,\quad w^{(\alpha+s)d+d}S,\quad\dotsc,\quad
w^{(\alpha+s)d+sd}S,$ $\displaystyle w^{2(\alpha+s)d}S,\quad\dotsc,\quad
w^{2(\alpha+s)d+sd}S,\qquad\dotsc,\qquad w^{a(\alpha+s)d}S,\quad\dotsc,\quad
w^{a(\alpha+s)d+bd}S.$

We remark that these sets are formed by starting with $S$, then prepending
$w^{d}$ $s$ times, prepending $w^{\alpha d}$, then prepending $w^{d}$ $s$
times, prepending $w^{\alpha d}$, and so on. We group up the sets: the
$1^{\text{st}}$ through $d^{\text{th}}$ sets are in the first group; the
$(d+1)^{\text{th}}$ through $(2d)^{\text{th}}$ sets are in the second group;
and so on.

We first show that sets in different groups are disjoint. If two such sets
meet, then $S\cap w^{\ell d}S\neq\varnothing$ for some integer $\ell$
satisfying $\alpha\leqslant\ell\leqslant a(\alpha+s)+b$. Now $w^{\ell d}\in
S_{\ell d,(\ell+1)d,\dotsc,\ell d(td+1)}$ and so, since $k-1$ is a multiple of
$d$, it suffices to show that $\ell d\leqslant k-1\leqslant\ell d(td+1)$ for
all such $\ell$. Firstly,

$\ell d(td+1)\geqslant\alpha d(d+1)=k-1.$

Now,

$\displaystyle\ell d$
$\displaystyle\leqslant(a(\alpha+s)+b)d=(a(\alpha+s)+\rho-a(s+1))d$
$\displaystyle=(a(\alpha-1)+\rho)d$

and we wish to show this is at most $k-1=\alpha d(d+1)$ and so it is enough to
show that $a(\alpha-1)+\rho\leqslant\alpha(d+1)$. By the maximality of $s$,
$d(s+1)\geqslant\rho$ and so $d\geqslant\rho/(s+1)\geqslant a$. Hence, it
suffices to show that $d(\alpha-1)+\rho\leqslant\alpha(d+1)$, or equivalently
$\rho\leqslant\alpha+d$. But, by Lemma 5.2,

$\displaystyle\alpha d(d+1)$
$\displaystyle=k-1\geqslant\max\\{(\rho-t)t(t+1)\colon
t\in\\{1,2,\dotsc,\rho-1\\}\\}$ $\displaystyle\geqslant(\rho-d)d(d+1),$

and so we do indeed have $\rho\leqslant\alpha+d$.

Next we show that sets in the same group are disjoint. If two consecutive sets
in the same group meet, then $S\cap w^{d}S\neq\varnothing$. But $w^{d}\in
S_{d,2d,\dotsc,(td+1)d}$ and so if $S\cap w^{d}S\neq\varnothing$, then
$S_{1,d+1,2d+1,\dotsc,(td+1)d+1}\neq\varnothing$ which contradicts the
maximality of $t$. If two non-consecutive sets in the same group meet, then
$S\cap w^{\ell d}S\neq\varnothing$ for some integer $\ell$ with
$2\leqslant\ell\leqslant s$. But $w^{\ell d}\in S_{\ell d}$ and so $S_{1,\ell
d+1}\neq\varnothing$. However, $d<2d\leqslant\ell d\leqslant
ds\leqslant\rho-1$ and so this contradicts the maximality of $d$.

Hence, all $\rho+1$ sets are pairwise disjoint which contradicts Lemma 3.7, as
required. ∎

Propositions 5.3 and 5.4 together show that $S$ is strongly $\rho$-product-
free. Theorem 1.7 then follows from Theorem 1.4.

##  6 Steeplechases

In this section, we develop some results which will be used in the next
section to bound the density of a (strongly) $k$-product-free set $S$ and so
prove Theorem 3.5. To motivate our approach, assume that $S$ is strongly
3-product-free. To bound the density of $S$, we might hope that
$d^{I_{\infty}}(S)=d^{I_{\infty}}(S^{2})=d^{I_{\infty}}(S^{3})$. Because all
of these sets are disjoint, this would imply that $d^{I_{\infty}}(S\cup
S^{2}\cup S^{3})=3\cdot d^{I_{\infty}}(S)$ and so $d^{I_{\infty}}(S)\leqslant
1/3$, as required.

If $S$ is evenly distributed, such an argument works. Indeed, note that for
all $w\in S$ we have $d^{I_{\infty}}_{w\mathcal{F}}(S^{2})\geqslant
d^{I_{\infty}}_{w\mathcal{F}}(wS)=d^{I_{\infty}}(S)$, so the relative density
of $S^{2}$ in $S\mathcal{F}$ is at least $d^{I_{\infty}}(S)$. If
$S\mathcal{F}$ covers all of $\mathcal{F}$, this implies that
$d^{I_{\infty}}(S^{2})\geqslant d^{I_{\infty}}(S)$, and so
$d^{I_{\infty}}(S\cup S^{2})\geqslant 2\cdot d^{I_{\infty}}(S)$. To include
$S^{3}$ in the union, we can just repeat the argument. For $w\in S$ we have
$d^{I_{\infty}}_{w\mathcal{F}}(S^{2}\cup S^{3})\geqslant
d^{I_{\infty}}_{w\mathcal{F}}(w(S\cup S^{2}))=d^{I_{\infty}}(S\cup
S^{2})\geqslant 2\cdot d^{I_{\infty}}(S)$, giving $d^{I_{\infty}}(S^{2}\cup
S^{3})\geqslant 2\cdot d^{I_{\infty}}(S)$ and thus $d^{I_{\infty}}(S\cup
S^{2}\cup S^{3})\geqslant 3\cdot d^{I_{\infty}}(S)$, as required.

If $S$ is not evenly distributed, we want to ignore the part of $\mathcal{F}$
where $S$ has a very low density. In the rest, the density of $S$ should be at
least $d^{I_{\infty}}(S)$ and $S$ should be somewhat evenly distributed.
Within this part, we then want to show that $S\cup S^{2}$ has density $2\cdot
d^{I_{\infty}}(S)$ and $S\cup S^{2}\cup S^{3}$ has density $3\cdot
d^{I_{\infty}}(S)$ to again obtain the sought result.

While the density of $S\cup S^{2}$ could be computed as before, this no longer
works for $S\cup S^{2}\cup S^{3}$. We only know that $S\cup S^{2}$ has a high
density within a part of $\mathcal{F}$, for example
$d^{I_{\infty}}_{v\mathcal{F}}(S\cup S^{2})\geqslant 2\cdot d^{I_{\infty}}(S)$
for some $v\in\mathcal{F}$. This does not suffice to get a lower bound on
$d^{I_{\infty}}_{w\mathcal{F}}(S^{2}\cup S^{3})$ in the calculation above.

Instead, note that $d^{I_{\infty}}_{wv\mathcal{F}}(S^{2}\cup S^{3})\geqslant
d^{I_{\infty}}_{wv\mathcal{F}}(w(S\cup
S^{2}))=d^{I_{\infty}}_{v\mathcal{F}}(S\cup S^{2})\geqslant 2\cdot
d^{I_{\infty}}(S)$ which tells us that the relative density of $S^{2}\cup
S^{3}$ in $Sv\mathcal{F}$ is at least $2\cdot d^{I_{\infty}}(S)$. If we could
now show that $Sv\mathcal{F}$ covers essentially all of $S\mathcal{F}$, this
would imply that $S^{2}\cup S^{3}$ has density at least $2\cdot
d^{I_{\infty}}(S)$ in $S\mathcal{F}$ which in turn would suffice to show that
$d^{I_{\infty}}(S)\leqslant 1/3$.

The technical arguments in this section are mostly devoted to showing that
this is true, at least up to some small error. The idea is that we partition
$S$ into prefix-free sets $(C_{k})$ such that $C_{k+1}\subset
C_{k}\mathcal{F}$. At some point, the measure of $C_{k}$ will no longer drop.
This means that $C_{k+1}\mathcal{F}$ covers almost all subtrees of
$C_{k}\mathcal{F}$.

Now, $C_{k}v\mathcal{F}$ will cover a fraction of size
$\lvert\mathcal{A}\rvert^{-\lvert v\rvert}$ of $C_{k}\mathcal{F}$. We also
know that all uncovered subtrees are covered by $C_{k+1}\mathcal{F}$. So,
$C_{k+1}v\mathcal{F}$ will cover a fraction of size
$\lvert\mathcal{A}\rvert^{-\lvert v\rvert}$ of the still uncovered subtrees of
$C_{k}\mathcal{F}$, and the remaining subtrees are covered by
$C_{k+2}\mathcal{F}$. By repeating this argument with
$C_{k+2}v\mathcal{F},C_{k+3}v\mathcal{F},\dots$, we can eventually cover
almost all of $C_{k}\mathcal{F}$ with $\bigcup_{\ell\geqslant
k}C_{\ell}v\mathcal{F}$. By deleting the first few layers of our partition of
$S$, we therefore get that $S\mathcal{F}$ is covered by $Sv\mathcal{F}$, which
is what we need.

This motivate the following definition.

######  Definition 6.1 (steeplechase).

An infinite sequence $(C_{k})$ of subsets of $\mathcal{F}$ is a _steeplechase_
if, for each positive integer $k$,

  * •

each $C_{k}$ is prefix-free and finite,

  * •

every word in $C_{k+1}$ has a proper prefix in $C_{k}$ (in particular,
$C_{k+1}\mathcal{F}\subset C_{k}\mathcal{F}$).

Steeplechase $(C_{k})$ is _spread_ if $\max C_{k}<\min C_{k+1}$ for all $k$
and is _$\varepsilon$ -tight_ if, for all $m,n$,
$\lvert\mu(C_{m})-\mu(C_{n})\rvert\leqslant\varepsilon$.

Every steeplechase contains a spread steeplechase. Indeed, note that $\min
C_{k}\geqslant k$, since every word in $C_{k}$ has a proper prefix in
$C_{k-1}$. Let $\ell_{1}=\max C_{1}$. Then $\min C_{\ell_{1}+1}>\ell_{1}=\max
C_{1}$. Let $\ell_{2}=\max C_{\ell_{1}+1}$. Then $\min C_{\ell_{2}+1}>\max
C_{\ell_{1}+1}$. Iteratively doing this gives a spread steeplechase
$C_{1},C_{\ell_{1}+1},C_{\ell_{2}+1},\dotsc$.

Since $C_{k}$ is prefix-free, $\mu(C_{k})\in[0,1]$. Also, for each $k$,
$C_{k+1}\mathcal{F}\subset C_{k}\mathcal{F}$ and so the sequence
$(\mu(C_{k}))$ is non-increasing. In particular, this sequence tends to a
limit. Hence the sequence is Cauchy: for any $\varepsilon>0$, there is a $K$
such that, for all $\ell,k\geqslant K$,
$\lvert\mu(C_{k})-\mu(C_{\ell})\rvert\leqslant\varepsilon$. Thus, ignoring the
first few $C_{k}$ gives an $\varepsilon$-tight steeplechase.

In particular, given any steeplechase $(C_{k})$ we may, by passing to a
subsequence, assume that $(C_{k})$ is both spread and $\varepsilon$-tight.

The following lemma shows that, for any set $B\subset\mathcal{F}$, there is a
steeplechase that captures almost all of $B$.

######  Lemma 6.2.

Let $\varepsilon>0$ and $B\subset\mathcal{F}$. There is an $\varepsilon$-tight
spread steeplechase $(C_{k})$ such that

  * •

$C_{1}\cup C_{2}\cup\dotsb\subset B$,

  * •

for all $k$ and all large $n$ (in terms of $k$), $\mu((B\setminus
C_{k}\mathcal{F})(n))\leqslant\varepsilon$,

  * •

for all $k$, $\mu(C_{k})\geqslant d^{I_{\infty}}(B)-\varepsilon$.

###### Proof.

For $x\in B$, let the _headcount_ of $x$ be

$h(x)=\lvert\\{b\in B\colon b\text{ is a prefix of }x\\}\rvert.$

For each positive integer $k$, let $D_{k}=\\{x\in B\colon h(x)=k\\}$. Note
that each $D_{k}$ is prefix-free and so $\mu(D_{k})\leqslant 1$ for all $k$.
Iteratively do the following procedure for each positive integer $k$.

  1. 1.

Let $\ell_{k}$ be such that
$\mu(D_{k}(\\{\ell_{k}+1,\ell_{k}+2,\dotsc\\}))\leqslant\varepsilon/2^{k}$.

  2. 2.

Let $C_{k}=D_{k}(\\{1,2,\dotsc,\ell_{k}\\})$.

  3. 3.

Remove $(D_{k}\setminus C_{k})\mathcal{F}$ from $B$ (including from all later
$D_{i}$).

Let $B^{\prime}$ be the set remaining at the end of this procedure. Note that
in step 3 the headcounts of words either remain the same or those words are
removed from $B$ entirely. In particular, every word in $C_{k}$ has a proper
prefix in $C_{k-1}$. Also, by construction, $C_{k}$ is a finite subset of $B$.
Thus $(C_{k})$ is a steeplechase and $C_{1}\cup C_{2}\cup\dotsb\subset B$.

Fix $k$ and let $n>\max\\{\ell_{1},\dotsc,\ell_{k}\\}$. Any word of length $n$
in $B^{\prime}$ is not in $C_{1}\cup\dotsb\cup C_{k}$ and so has headcount
greater than $k$ and so is in $C_{k}\mathcal{F}$. Thus, $B^{\prime}(n)\subset
C_{k}\mathcal{F}(n)$. Next note that $B^{\prime}$ is obtained from $B$ by
deleting all the $(D_{t}\setminus C_{t})\mathcal{F}$ and so,

$\mu((B\setminus C_{k}\mathcal{F})(n))\leqslant\mu((B\setminus
B^{\prime})(n))\leqslant\sum_{t}\mu((D_{t}\setminus
C_{t})(n))\leqslant\sum_{t}\mu(D_{t}\setminus C_{t})\leqslant\varepsilon.$

Finally, this implies that
$\mu(B(n))\leqslant\mu(C_{k}\mathcal{F}(n))+\varepsilon\leqslant\mu(C_{k})+\varepsilon$.
Averaging this over $n\in I_{j}$ and taking $j\to\infty$ gives
$d^{I_{\infty}}(B)\leqslant\mu(C_{k})+\varepsilon$.

Hence $(C_{k})$ is a steeplechase satisfying all three conditions. As noted
above, we may, by passing to a subsequence, assume that $(C_{k})$ is spread
and $\varepsilon$-tight. Passing to a subsequence does not affect the three
conditions. ∎

We call the steeplechase $(C_{k})$ given by Lemma 6.2 an _$\varepsilon$
-capturing steeplechase for $B$_.

######  Lemma 6.3.

Let $(C_{k})$ be an $\varepsilon$-tight spread steeplechase. For every
$w\in\mathcal{F}$ there is an $N$ such that the following holds. If
$C=C_{1}\cup C_{2}\cup\dotsb\cup C_{N}$ and $n\geqslant\max C_{N}+\lvert
w\rvert$, then

$\mu((C_{1}\mathcal{F}\setminus Cw\mathcal{F})(n))\leqslant 2\varepsilon.$

###### Proof.

Let $N$ sufficiently large in terms of $\lvert w\rvert$ and
$\lvert\mathcal{A}\rvert$ and let $n\geqslant\max C_{N}+\lvert w\rvert$. Now

$\mu((C_{1}\mathcal{F}\setminus
C_{N}\mathcal{F})(n))=\mu((C_{1}\mathcal{F})(n))-\mu((C_{N}\mathcal{F})(n))=\mu(C_{1})-\mu(C_{N})\leqslant\varepsilon,$

since $C_{N}\mathcal{F}\subset C_{1}\mathcal{F}$ and $(C_{k})$ is
$\varepsilon$-tight. Hence, it suffices to prove that

$\mu((C_{N}\mathcal{F}\setminus Cw\mathcal{F})(n))\leqslant\varepsilon.$

Let $X$ be the following finite prefix-free set

$X=\\{s\in C_{N}\colon s\text{ has no prefix in }Cw\\}.$

Note that $(C_{N}\mathcal{F}\setminus
Cw\mathcal{F})(n)\subset(X\mathcal{F})(n)$ and so

$\mu((C_{N}\mathcal{F}\setminus
Cw\mathcal{F})(n))\leqslant\mu((X\mathcal{F})(n))=\mu(X).$

Recall the random infinite word $\mathbf{W}=\alpha_{1}\alpha_{2}\dotsb$ and
corresponding random walk defined in Section 2. Since $X$ is prefix-free,
$\mu(X)=\mathbb{P}(\mathbf{W}\text{ hits }X)$ and it suffices to show this
probability is at most $\varepsilon$. Let $K$ be the largest integer with
$1+K\lvert w\rvert\leqslant N-\lvert w\rvert$. If $\mathbf{W}$ hits $X$, then
$\mathbf{W}$ hits $C_{N}$ and so, since $(C_{k})$ is a steeplechase,
$\mathbf{W}$ hits each of $C_{1}$, $C_{1+\lvert w\rvert}$, …, $C_{1+K\lvert
w\rvert}$. Also, $\mathbf{W}$ must avoid each of $C_{1}w$, $C_{1+\lvert
w\rvert}w$, …, $C_{1+K\lvert w\rvert}w$ in order to hit $X$.

We reveal the letters of $\mathbf{W}$ one-by-one. We wait until $\mathbf{W}$
hits/avoids $C_{1}$ (this will certainly be known by the time the length of
$\mathbf{W}$ is $\max C_{1}$). If $\mathbf{W}$ avoids $C_{1}$, then
$\mathbf{W}$ avoids $X$. If $\mathbf{W}$ hits $C_{1}$, then we reveal the next
$\lvert w\rvert$ letters of $\mathbf{W}$ and check if they spell $w$ (this has
probability $\lvert\mathcal{A}\rvert^{-\lvert w\rvert}$). If they do, then
$\mathbf{W}$ avoids $X$. If they do not, then we wait until $\mathbf{W}$
hits/avoids $C_{1+\lvert w\rvert}$: note that this has not already happened
since $(C_{k})$ is spread and so $\min C_{1+\lvert w\rvert}\geqslant\max
C_{1}+\lvert w\rvert$. If $\mathbf{W}$ avoids $C_{1+\lvert w\rvert}$, then
$\mathbf{W}$ avoids $X$. If $\mathbf{W}$ hits $C_{1+\lvert w\rvert}$, then we
reveal the next $\lvert w\rvert$ letters of $\mathbf{W}$ and check if they
spell $w$ (this has probability $\lvert A\rvert^{-\lvert w\rvert}$). We
continue this procedure with the final check being whether the next $\lvert
w\rvert$ letters of $\mathbf{W}$ after it hits $C_{1+K\lvert w\rvert}$ spell
$w$. Note that each check has probability $\lvert\mathcal{A}\rvert^{-\lvert
w\rvert}$ and is independent of the previous checks (new letters are involved
in each check). If $\mathbf{W}$ hits $X$, then $\mathbf{W}$ must fail each of
these spelling checks and so the probability that $\mathbf{W}$ hits $X$ is at
most

$(1-\lvert\mathcal{A}\rvert^{-\lvert w\rvert})^{K+1}.$

By taking $N$ (and so $K$) sufficiently large in terms of $\lvert w\rvert$ and
$\lvert\mathcal{A}\rvert$ we may ensure this is at most $\varepsilon$, as
required. ∎

Before proving our key technical result for our density proofs (Lemma 6.5) we
will need to define the relative density of $B$ on $C\mathcal{F}$. If
$C\subset\mathcal{F}$ is finite and interval $I$ satisfies $\min
I\geqslant\max C$, then the _relative density of $B$ in $C\mathcal{F}$ on
interval $I$_ is

$d^{I}_{C\mathcal{F}}(B)\coloneqq\frac{\mu(B(I)\cap
C\mathcal{F})}{\mu(\mathcal{F}(I)\cap C\mathcal{F})}.$

Suppose $C$ is also prefix-free. Then, by Observation 3.1,
$\mu(\mathcal{F}(I)\cap C\mathcal{F})=\lvert I\rvert\mu(C)$. Also
$(c\mathcal{F}\colon c\in C)$ partition $C\mathcal{F}$. In particular,

$\displaystyle d^{I}_{C\mathcal{F}}(B)$ $\displaystyle=\lvert
I\rvert^{-1}\mu(C)^{-1}\sum_{n\in I}\mu(B(n)\cap C\mathcal{F})$
$\displaystyle=\sum_{c\in C}\lvert I\rvert^{-1}\mu(C)^{-1}\sum_{n\in
I}\mu(B(n)\cap c\mathcal{F})$ $\displaystyle=\sum_{c\in
C}\frac{\mu(c)}{\mu(C)}\cdot d^{I}_{c\mathcal{F}}(B)$
$\displaystyle=\mu(C)^{-1}\sum_{c\in C}d^{I}(B\cap c\mathcal{F})$
$\displaystyle=\mu(C)^{-1}\cdot d^{I}(B\cap C\mathcal{F}).$

For every set $B$ that we consider in this paper and every word $c$, the
sequence $d^{I_{j}}_{c\mathcal{F}}(B)$ converges (to
$d^{I_{\infty}}_{c\mathcal{F}}(B)$). Thus the sequence
$d^{I_{j}}_{C\mathcal{F}}(B)$ converges to a limit
_$d^{I_{\infty}}_{C\mathcal{F}}(B)$_. Again, these limits are additive.

######  Observation 6.4.

Let $C\subset\mathcal{F}$ be finite and prefix-free. Then

$d^{I_{\infty}}_{C\mathcal{F}}(B)=\sum_{c\in C}\frac{\mu(c)}{\mu(C)}\cdot
d^{I_{\infty}}_{c\mathcal{F}}(B)=\mu(C)^{-1}\cdot d^{I_{\infty}}(B\cap
C\mathcal{F}).$

Now for the key technical lemma for our density results.

######  Lemma 6.5.

Let $\varepsilon>0$ and let $A,B\subset\mathcal{F}$. If $(C_{k})$ is an
$\varepsilon$-capturing steeplechase for $A$ with $\mu(C_{1})\geqslant
2\varepsilon+\varepsilon^{1/3}$, then

$d^{I_{\infty}}_{C_{1}\mathcal{F}}(AB)\geqslant
d_{\sup}^{I_{\infty}}(B)-3\varepsilon^{1/3}.$

###### Proof.

Let $w\in\mathcal{F}$ be such that

$d^{I_{\infty}}_{w\mathcal{F}}(B)\geqslant
d_{\sup}^{I_{\infty}}(B)-\varepsilon^{1/3}.$

Apply Lemma 6.3 to $(C_{k})$ and $w$ to give an $N$ such that letting
$C=C_{1}\cup\dotsb\cup C_{N}$, if $n\geqslant\max C_{N}+\lvert w\rvert$, then

$\mu((C_{1}\mathcal{F}\setminus Cw\mathcal{F})(n))\leqslant 2\varepsilon.$

We may greedily choose $\widetilde{C}\subset C$ (starting with shorter words
first) such that $\widetilde{C}w$ is prefix-free and
$\widetilde{C}w\mathcal{F}=Cw\mathcal{F}$. Note that

$\displaystyle 2\varepsilon$
$\displaystyle\geqslant\mu((C_{1}\mathcal{F}\setminus\widetilde{C}w\mathcal{F})(n))\geqslant\mu((C_{1}\mathcal{F})(n))-\mu((\widetilde{C}w\mathcal{F})(n))$
$\displaystyle=\mu(C_{1})-\mu(\widetilde{C}w)\geqslant
2\varepsilon+\varepsilon^{1/3}-\mu(\widetilde{C}w)$

and so $\mu(\widetilde{C}w)\geqslant\varepsilon^{1/3}$.

Let $I$ be an interval with $\min I\geqslant\max C_{N}+\lvert w\rvert$ and let
$X\subset\mathcal{F}$. Note that $\widetilde{C}w\mathcal{F}\subset
C_{1}\mathcal{F}$ and so

$\displaystyle d^{I}_{C_{1}\mathcal{F}}(X)$ $\displaystyle=\lvert
I\rvert^{-1}\mu(C_{1})^{-1}\sum_{n\in I}\mu(X(n)\cap C_{1}\mathcal{F})$
$\displaystyle\geqslant\lvert I\rvert^{-1}\mu(C_{1})^{-1}\sum_{n\in
I}\mu(X(n)\cap\widetilde{C}w\mathcal{F})$ $\displaystyle\geqslant\lvert
I\rvert^{-1}\sum_{n\in
I}\frac{\mu(X(n)\cap\widetilde{C}w\mathcal{F})}{\mu(\widetilde{C}w)+2\varepsilon}.$

Using the fact that $x/(y+2\varepsilon)\geqslant x/y-2\varepsilon
x/y^{2}\geqslant x/y-2\varepsilon^{1/3}$ for $\varepsilon>0$, $x\in[0,1]$, and
$y\geqslant\varepsilon^{1/3}$, we have

$d^{I}_{C_{1}\mathcal{F}}(X)\geqslant
d^{I}_{\widetilde{C}w\mathcal{F}}(X)-2\varepsilon^{1/3}.$

Setting $X=AB$, $I=I_{j}$, and taking $j$ to infinity gives

$d^{I_{\infty}}_{C_{1}\mathcal{F}}(AB)\geqslant
d^{I_{\infty}}_{\widetilde{C}w\mathcal{F}}(AB)-2\varepsilon^{1/3}.$ (2)

Now,

$\displaystyle d^{I_{\infty}}_{\widetilde{C}w\mathcal{F}}(AB)$
$\displaystyle=\sum_{c\in\widetilde{C}}\frac{\mu(c)}{\mu(\widetilde{C})}\cdot
d^{I_{\infty}}_{cw\mathcal{F}}(AB)$
$\displaystyle\geqslant\sum_{c\in\widetilde{C}}\frac{\mu(c)}{\mu(\widetilde{C})}\cdot
d^{I_{\infty}}_{cw\mathcal{F}}(cB)$
$\displaystyle=\sum_{c\in\widetilde{C}}\frac{\mu(c)}{\mu(\widetilde{C})}\cdot
d^{I_{\infty}}_{w\mathcal{F}}(B)$
$\displaystyle=d^{I_{\infty}}_{w\mathcal{F}}(B)\geqslant
d_{\sup}^{I_{\infty}}(B)-\varepsilon^{1/3},$

where the first equality used Observation 6.4, the first inequality used the
fact that $c\in\widetilde{C}\subset C\subset A$, the second equality used
Lemma 3.3, and the second inequality is due to the choice of $w$. Combining
this with (2) gives the required result. ∎

##  7 Density of (strongly) $k$-product-free sets

In this section we prove Theorem 3.5, making use of the machinery developed in
the previous section. Part (a) has a simple iterating proof which uses that a
strongly $k$-product-free $S$ is disjoint from each of $S^{2}$, $S^{3}$, …,
$S^{k}$.

###### Proof of Theorem 3.5(a).

Let $S\subset\mathcal{F}$ be strongly $k$-product-free and let $\varepsilon>0$
be sufficiently small. Let $(C_{k})$ be an $\varepsilon$-capturing
steeplechase for $S$, as given by Lemma 6.2. If
$\mu(C_{1})<2\varepsilon+\varepsilon^{1/3}$, then
$d^{\ast}(S)=d^{I_{\infty}}(S)\leqslant\mu(C_{1})+\varepsilon<3\varepsilon+\varepsilon^{1/3}$
which is less than $1/k$. Otherwise, by Lemma 6.5,
$d^{I_{\infty}}_{C_{1}\mathcal{F}}(S^{2})\geqslant
d_{\sup}^{I_{\infty}}(S)-3\varepsilon^{1/3}$. Since $S$ is strongly
$k$-product-free, $S$ and $S^{2}$ are disjoint and so

$d^{I_{\infty}}_{C_{1}\mathcal{F}}(S\cup S^{2})\geqslant
d^{I_{\infty}}_{C_{1}\mathcal{F}}(S)+d_{\sup}^{I_{\infty}}(S)-3\varepsilon^{1/3}.$

Now, by Observation 6.4,

$d_{\sup}^{I_{\infty}}(S\cup S^{2})\geqslant
d^{I_{\infty}}_{C_{1}\mathcal{F}}(S\cup S^{2})\geqslant
d^{I_{\infty}}_{C_{1}\mathcal{F}}(S)+d_{\sup}^{I_{\infty}}(S)-3\varepsilon^{1/3},$

and so, by Lemma 6.5,

$d^{I_{\infty}}_{C_{1}\mathcal{F}}(S^{2}\cup S^{3})\geqslant
d_{\sup}^{I_{\infty}}(S\cup S^{2})-3\varepsilon^{1/3}\geqslant
d^{I_{\infty}}_{C_{1}\mathcal{F}}(S)+d_{\sup}^{I_{\infty}}(S)-6\varepsilon^{1/3}.$

Hence,

$d_{\sup}^{I_{\infty}}(S\cup S^{2}\cup S^{3})\geqslant
d^{I_{\infty}}_{C_{1}\mathcal{F}}(S\cup S^{2}\cup S^{3})\geqslant
2d^{I_{\infty}}_{C_{1}\mathcal{F}}(S)+d_{\sup}^{I_{\infty}}(S)-6\varepsilon^{1/3}.$

Iterating this argument gives

$1\geqslant d_{\sup}^{I_{\infty}}(S\cup S^{2}\cup\dotsb\cup
S^{k})\geqslant(k-1)d^{I_{\infty}}_{C_{1}\mathcal{F}}(S)+d_{\sup}^{I_{\infty}}(S)-3(k-1)\varepsilon^{1/3}.$

But, since $(C_{k})$ is $\varepsilon$-capturing for $S$,
$d^{I_{\infty}}_{C_{1}\mathcal{F}}(S)=\mu(C_{1})^{-1}\cdot
d^{I_{\infty}}(S\cap C_{1}\mathcal{F})\geqslant d^{I_{\infty}}(S\cap
C_{1}\mathcal{F})\geqslant d^{I_{\infty}}(S)-\varepsilon$. Hence,
$(k-1)d^{I_{\infty}}(S)+d_{\sup}^{I_{\infty}}(S)\leqslant
1+(k-1)\varepsilon+3(k-1)\varepsilon^{1/3}$. As $\varepsilon$ is arbitrarily
small,

$1\geqslant(k-1)d^{I_{\infty}}(S)+d_{\sup}^{I_{\infty}}(S).$

But $d_{\sup}^{I_{\infty}}(S)\geqslant d^{I_{\infty}}(S)$ and so
$d^{\ast}(S)=d^{I_{\infty}}(S)\leqslant 1/k$. Furthermore, if
$d^{\ast}(S)=1/k$, then $d^{I_{\infty}}(S)=1/k$ and so
$d_{\sup}^{I_{\infty}}(S)\leqslant 1/k$, as required. ∎

The argument for part (b) ($k$-product-free sets) is more involved. It is not
necessary to keep track of the error term depending on $\varepsilon$ (as we
eventually take $\varepsilon$ to zero). We introduce some notation to simplify
the argument. Write _$x\lesssim y$_ to mean that $x\leqslant y+f(\varepsilon)$
where the error term $f(\varepsilon)$ depends only on $k$ and $\varepsilon$
and goes to zero as $\varepsilon$ goes to zero (in all cases $f(\varepsilon)$
will be a polynomial in $\varepsilon^{1/3}$).

To improve clarity and motivate the proof we first sketch a proof of Theorem
3.5(b) for $k=3$. For full details see the proof of Proposition 7.1 that
follows.

###### Proof of Theorem 3.5(b) for $k=3$.

Let $S\subset\mathcal{F}$ be 3-product-free and let $\varepsilon>0$ be
sufficiently small. Let $(C_{k})$ be an $\varepsilon$-capturing steeplechase
for $S_{1,2}=S\cap S^{2}$ (recall Definition 5.1), as given by Lemma 6.2.
Since $S$ is 3-product-free, $S_{1,2}$ is strongly 3-product-free.

We claim that $d^{I_{\infty}}(S\cap C_{1}\mathcal{F})\lesssim
1/3\cdot\mu(C_{1})$. If $\mu(C_{1})<2\varepsilon+\varepsilon^{1/3}$, then this
is immediate. Otherwise $\mu(C_{1})\geqslant 2\varepsilon+\varepsilon^{1/3}$
and so, by Lemma 6.5, $d^{I_{\infty}}_{C_{1}\mathcal{F}}(S_{1,2}S)\gtrsim
d_{\sup}^{I_{\infty}}(S)$. Since $S$ is 3-product-free, $S$ and $S_{1,2}S$ are
disjoint and so

$d_{\sup}^{I_{\infty}}(S\cup S_{1,2}S)\geqslant
d^{I_{\infty}}_{C_{1}\mathcal{F}}(S\cup S_{1,2}S)\gtrsim
d^{I_{\infty}}_{C_{1}\mathcal{F}}(S)+d_{\sup}^{I_{\infty}}(S).$

Then, by Lemma 6.5,

$d^{I_{\infty}}_{C_{1}\mathcal{F}}(S_{1,2}S\cup
S_{1,2}^{2}S)=d^{I_{\infty}}_{C_{1}\mathcal{F}}(S_{1,2}(S\cup
S_{1,2}S))\gtrsim
d^{I_{\infty}}_{C_{1}\mathcal{F}}(S)+d_{\sup}^{I_{\infty}}(S).$

Since $S$ is 3-product-free, $S$ is disjoint from $S_{1,2}S\cup S_{1,2}^{2}S$
and so

$1\geqslant d_{\sup}^{I_{\infty}}(S\cup S_{1,2}S\cup S_{1,2}^{2}S)\geqslant
d^{I_{\infty}}_{C_{1}\mathcal{F}}(S\cup S_{1,2}S\cup S_{1,2}^{2}S)\gtrsim
2d^{I_{\infty}}_{C_{1}\mathcal{F}}(S)+d_{\sup}^{I_{\infty}}(S).$

But $d_{\sup}^{I_{\infty}}(S)\geqslant d^{I_{\infty}}_{C_{1}\mathcal{F}}(S)$
and so $d^{I_{\infty}}_{C_{1}\mathcal{F}}(S)\lesssim 1/3$. Observation 6.4
then gives $d^{I_{\infty}}(S\cap C_{1}\mathcal{F})\lesssim
1/3\cdot\mu(C_{1})$, as claimed.

We have bounded the density of $S$ on the part of $\mathcal{F}$ where
$S_{1,2}$ is dense. We now bound the density of $S$ on the rest. Let
$S^{\prime}=S\setminus(S_{1,2}\cup C_{1}\mathcal{F})$ and $(D_{k})$ be an
$\varepsilon$-capturing steeplechase for $S^{\prime}$, as given by Lemma 6.2.
By passing to a subsequence we may and will assume that $\min D_{1}>\max
C_{1}$. Since $S$ is 3-product-free and $S^{\prime}\cap S^{2}=\varnothing$,
$S^{\prime}$ is strongly 3-product-free.

We claim that $d^{I_{\infty}}(S^{\prime}\cap D_{1}\mathcal{F})\lesssim
1/3\cdot\mu(D_{1})$. If $\mu(D_{1})<2\varepsilon+\varepsilon^{1/3}$, then this
is immediate. Otherwise, by Lemma 6.5,
$d^{I_{\infty}}_{D_{1}\mathcal{F}}(S^{\prime}S)\gtrsim
d_{\sup}^{I_{\infty}}(S)$. Now $S^{\prime}$ and $S^{\prime}S$ are disjoint
since $S^{\prime}\cap S^{2}=\varnothing$. Thus

$d_{\sup}^{I_{\infty}}(S^{\prime}\cup S^{\prime}S)\geqslant
d^{I_{\infty}}_{D_{1}\mathcal{F}}(S^{\prime}\cup S^{\prime}S)\gtrsim
d^{I_{\infty}}_{D_{1}\mathcal{F}}(S^{\prime})+d_{\sup}^{I_{\infty}}(S).$

Then, by Lemma 6.5,

$d^{I_{\infty}}_{D_{1}\mathcal{F}}((S^{\prime})^{2}\cup(S^{\prime})^{2}S)=d^{I_{\infty}}_{D_{1}\mathcal{F}}(S^{\prime}(S^{\prime}\cup
S^{\prime}S))\gtrsim
d^{I_{\infty}}_{D_{1}\mathcal{F}}(S^{\prime})+d_{\sup}^{I_{\infty}}(S).$

Since $S$ is 3-product-free and $S^{\prime}\cap S^{2}=\varnothing$,
$S^{\prime}$ is disjoint from $(S^{\prime})^{2}\cup(S^{\prime})^{2}S$ and so

$1\geqslant
d_{\sup}^{I_{\infty}}(S^{\prime}\cup(S^{\prime})^{2}\cup(S^{\prime})^{2}S)\geqslant
d^{I_{\infty}}_{D_{1}\mathcal{F}}(S^{\prime}\cup(S^{\prime})^{2}\cup(S^{\prime})^{2}S)\gtrsim
2d^{I_{\infty}}_{D_{1}\mathcal{F}}(S^{\prime})+d_{\sup}^{I_{\infty}}(S).$

But $d_{\sup}^{I_{\infty}}(S)\geqslant
d_{\sup}^{I_{\infty}}(S^{\prime})\geqslant
d^{I_{\infty}}_{D_{1}\mathcal{F}}(S^{\prime})$ and so
$d^{I_{\infty}}_{D_{1}\mathcal{F}}(S^{\prime})\lesssim 1/3$. Observation 6.4
then gives $d^{I_{\infty}}(S^{\prime}\cap D_{1}\mathcal{F})\lesssim
1/3\cdot\mu(D_{1})$, as claimed.

By the definition of $S^{\prime}$ and since $\min D_{1}>\max C_{1}$, it
follows that $C_{1}\mathcal{F}$ and $D_{1}\mathcal{F}$ are disjoint (see proof
of Proposition 7.1 for more details). In particular, $C_{1}$ and $D_{1}$ are
disjoint and their union is prefix-free. Hence $\mu(C_{1})+\mu(D_{1})\leqslant
1$. Thus,

$d^{I_{\infty}}(S\cap C_{1}\mathcal{F})+d^{I_{\infty}}(S^{\prime}\cap
D_{1}\mathcal{F})\lesssim 1/3\cdot(\mu(C_{1})+\mu(D_{1}))\leqslant 1/3.$

Since $(C_{k})$ and $(D_{k})$ are $\varepsilon$-capturing, it follows (see the
proof of Claim 7.1.2 below) that very little of $S$ lies outside $(S\cap
C_{1}\mathcal{F})\cup(S^{\prime}\cap D_{1}\mathcal{F})$. In particular,
$d^{I_{\infty}}(S)\lesssim 1/3$. Since $\varepsilon$ can be arbitrarily small,
we have $d^{\ast}(S)=d^{I_{\infty}}(S)\leqslant 1/3$. For the moreover part
see the proof of Proposition 7.1 below. ∎

For general $k$ the argument is a more involved version of the above. We first
consider some $S_{A_{1}}$, take some $\varepsilon$-capturing steeplechase,
$(C_{k}^{(1)})$ for $S_{A_{1}}$ and show the density of $S$ relative to
$C_{1}\mathcal{F}$ is at most $1/\rho$. We then repeat this step for some
$S_{A_{2}}$, $S_{A_{3}}$, …. In future steps we may use the fact that we have
dealt with previous $S_{A_{i}}$. Proposition 7.1 says that if we have chosen a
suitable sequence $A_{1},A_{2},\dotsc$, then we obtain the required bound on
$d^{\ast}(S)$, and Proposition 7.2 shows that for each $k$ there is a suitable
sequence of $A_{i}$. These combine to complete the proof of Theorem 3.5(b).

Note in the statement below that _$dA_{\ell}$_ is the sumset

$dA_{\ell}\coloneqq\\{a_{1}+\dotsb+a_{d}\colon a_{1},\dotsc,a_{d}\in
A_{\ell}\\}.$

######  Proposition 7.1.

Let $k\geqslant 2$ be an integer and $A_{1},\dots,A_{m}\subset\mathbb{N}$ be a
sequence of sets with $A_{m}=\\{1\\}$. Suppose that for all $\ell\in[m]$ there
exist positive integers $d_{1},\dotsc,d_{\rho-1}$ such that, for all
$1\leqslant i\leqslant j\leqslant\rho-1$, either

  * •

$k\in\\{1\\}\cup(1+(d_{i}+d_{i+1}+\dotsb+d_{j})A_{\ell})$ or

  * •

$A_{\ell^{\prime}}\subset\\{1\\}\cup(1+(d_{i}+d_{i+1}+\dotsb+d_{j})A_{\ell})$
for some $1\leqslant\ell^{\prime}<\ell$.

If $S\subset\mathcal{F}$ is $k$-product-free, then $d^{\ast}(S)\leqslant
1/\rho$. Moreover, if $d^{\ast}(S)=1/\rho$, then
$d_{\sup}^{I_{\infty}}(S)=1/\rho$.

###### Proof.

Let $\varepsilon>0$ be sufficiently small. We define the following sets and
steeplechases. Take $S^{(1)}\coloneqq S$, $R^{(1)}\coloneqq S_{A_{1}}\cap
S^{(1)}$, and let $(C_{k}^{(1)})$ be an $\varepsilon$-capturing steeplechase
for $R^{(1)}$, as given by Lemma 6.2. For $\ell=2,3,\dotsc,m$, iteratively do
the following:

  * •

Set $S^{(\ell)}\coloneqq S\setminus(S_{A_{1}}\cup\dotsb\cup
S_{A_{\ell-1}}\cup(C_{1}^{(1)}\cup\dotsb\cup C_{1}^{(\ell-1)})\mathcal{F})$
and $R^{(\ell)}\coloneqq S_{A_{\ell}}\cap S^{(\ell)}$.

  * •

Take $(C_{k}^{(\ell)})$ to be an $\varepsilon$-capturing steeplechase for
$R^{(\ell)}$. By passing to a subsequence of the steeplechase we may and will
assume that $\min C_{1}^{(\ell)}>\max C_{1}^{(\ell-1)}$.

######  Claim 7.1.1.

For each $\ell\in[m]$, $d^{I_{\infty}}(S^{(\ell)}\cap
C_{1}^{(\ell)}\mathcal{F})\lesssim 1/\rho\cdot\mu(C_{1}^{(\ell)})$.

###### Proof.

Firstly, if $\mu(C_{1}^{(\ell)})<2\varepsilon+\varepsilon^{1/3}$, then

$d^{I_{\infty}}(S^{(\ell)}\cap C_{1}^{(\ell)}\mathcal{F})\leqslant
d^{I_{\infty}}(C_{1}^{(\ell)}\mathcal{F})=\mu(C_{1}^{(\ell)})\lesssim
1/\rho\cdot\mu(C_{1}^{(\ell)}).$

Hence, we may assume from now on that $\mu(C_{1}^{(\ell)})\geqslant
2\varepsilon+\varepsilon^{1/3}$. Consider the sets $S^{(\ell)}$ and
$(R^{(\ell)})^{d_{\rho-1}}S$. Note that $(R^{(\ell)})^{d_{\rho-1}}\subset
S_{d_{\rho-1}A_{\ell}}$. Hence, if $S^{(\ell)}$ and
$(R^{(\ell)})^{d_{\rho-1}}S$ meet, then $S^{(\ell)}\cap
S_{1+d_{\rho-1}A_{\ell}}\neq\varnothing$. By the proposition statement, this
implies that $S^{(\ell)}\cap S_{k}\neq\varnothing$ or $S^{(\ell)}\cap
S_{A_{\ell^{\prime}}}\neq\varnothing$ (for $\ell^{\prime}<\ell$). $k$-product-
freeness rules out the former and the definition of $S^{(\ell)}$ the latter.
Therefore, $S^{(\ell)}$ and $(R^{(\ell)})^{d_{\rho-1}}S$ are disjoint and so,

$\displaystyle
d_{\sup}^{I_{\infty}}(S^{(\ell)}\cup(R^{(\ell)})^{d_{\rho-1}}S)$
$\displaystyle\geqslant
d^{I_{\infty}}_{C_{1}^{(\ell)}\mathcal{F}}(S^{(\ell)}\cup(R^{(\ell)})^{d_{\rho-1}}S)$
$\displaystyle=d^{I_{\infty}}_{C_{1}^{(\ell)}\mathcal{F}}(S^{(\ell)})+d^{I_{\infty}}_{C_{1}^{(\ell)}\mathcal{F}}((R^{(\ell)})^{d_{\rho-1}}S).$

Note that $(C_{k}^{(\ell)})$ is an $\varepsilon$-capturing steeplechase for
$R^{(\ell)}$ and so, by Lemma 6.5,

$d_{\sup}^{I_{\infty}}(S^{(\ell)}\cup(R^{(\ell)})^{d_{\rho-1}}S)\gtrsim
d^{I_{\infty}}_{C_{1}^{(\ell)}\mathcal{F}}(S^{(\ell)})+d_{\sup}^{I_{\infty}}(S).$

Iterating this procedure, exactly as in the proofs of Theorem 3.5(a) and the
$k=3$ case above, gives

$\begin{split}1\geqslant
d_{\sup}^{I_{\infty}}(S^{(\ell)}\cup(R^{(\ell)})^{d_{1}}S^{(\ell)}&\cup\dotsb\cup(R^{(\ell)})^{d_{1}+\dotsb+d_{\rho-2}}S^{(\ell)}\cup(R^{(\ell)})^{d_{1}+\dotsb+d_{\rho-1}}S)\\\
&\gtrsim(\rho-1)d^{I_{\infty}}_{C_{1}^{(\ell)}\mathcal{F}}(S^{(\ell)})+d_{\sup}^{I_{\infty}}(S).\end{split}$
(3)

Now, $d_{\sup}^{I_{\infty}}(S)\geqslant
d_{\sup}^{I_{\infty}}(S^{(\ell)})\geqslant
d^{I_{\infty}}_{C_{1}^{(\ell)}\mathcal{F}}(S^{(\ell)})$ and so
$d^{I_{\infty}}_{C_{1}^{(\ell)}\mathcal{F}}(S^{(\ell)})\lesssim 1/\rho$. The
claim follows from Observation 6.4. ∎

We next show that very little of $S$ has not been captured by the previous
claim.

######  Claim 7.1.2.

For all large $n$, $\mu(S(n)\setminus\bigcup_{\ell}(S^{(\ell)}\cap
C_{1}^{(\ell)}\mathcal{F}))\leqslant m\varepsilon$.

###### Proof.

For each $\ell$, $(C_{k}^{(\ell)})$ is an $\varepsilon$-capturing steeplechase
for $R^{(\ell)}$ and so, for all large $n$,

$\mu(R^{(\ell)}(n)\setminus C_{1}^{(\ell)}\mathcal{F})\leqslant\varepsilon.$

Hence, it is enough to show that $S\setminus\bigcup_{\ell}(S^{(\ell)}\cap
C_{1}^{(\ell)}\mathcal{F}))\subset\bigcup_{\ell}(R^{(\ell)}\setminus
C_{1}^{(\ell)}\mathcal{F})$. Fix $w\in S\setminus\bigcup_{\ell}(S^{(\ell)}\cap
C_{1}^{(\ell)}\mathcal{F}))$. Let $\ell$ be maximal with $w\in S^{(\ell)}$
(such an $\ell$ exists as $S^{(1)}=S$). Since $w\in
S\setminus\bigcup_{\ell}(S^{(\ell)}\cap C_{1}^{(\ell)}\mathcal{F}))$, we have
$w\notin C_{1}^{(\ell)}\mathcal{F}$. We claim that $w\in S_{A_{\ell}}$. If
$\ell=m$, then this is immediate ($S_{A_{m}}=S_{1}=S$). If $\ell<m$, then, by
the maximality of $\ell$, we must have $w\in S_{A_{\ell}}\cup
C_{1}^{(\ell)}\mathcal{F}$ and so $w\in S_{A_{\ell}}$. Thus,
$w\in(S_{A_{\ell}}\cap S^{(\ell)})\setminus
C_{1}^{(\ell)}\mathcal{F}=R^{(\ell)}\setminus C_{1}^{(\ell)}\mathcal{F}$, as
required. ∎

We now note that $C_{1}^{(1)}\mathcal{F}$, …, $C_{1}^{(m)}\mathcal{F}$ are
pairwise disjoint. If not then some $w_{i}\in C_{1}^{(i)}$ is a prefix of some
$w_{j}\in C_{1}^{(j)}$ (for $i\neq j$). Now, by construction, $\min
C_{1}^{(\ell)}>\max C_{1}^{(\ell-1)}$ for all $\ell$ and so $i<j$. On the
other hand, $w_{j}\in C_{1}^{(j)}\subset R^{(j)}\subset S^{(j)}$ and so
$w_{j}\notin C_{1}^{(i)}\mathcal{F}$, a contradiction. In particular,
$C_{1}^{(\ell)}$, …, $C_{1}^{(m)}$ are pairwise disjoint and their union is
prefix-free.

We can now show that $d^{\ast}(S)\leqslant 1/\rho$. Summing Claim 7.1.1 over
$\ell$ gives

$d^{I_{\infty}}(\bigcup_{\ell}(S^{(\ell)}\cap
C_{1}^{(\ell)}\mathcal{F}))\lesssim 1/\rho\cdot\mu(C_{1}^{(1)}\cup\dotsb\cup
C_{1}^{(m)})\leqslant 1/\rho.$ (4)

Then, by Claim 7.1.2, we obtain $d^{I_{\infty}}(S)\lesssim 1/\rho$. Noting
that $\varepsilon$ can be arbitrarily small we have
$d^{\ast}(S)=d^{I_{\infty}}(S)\leqslant 1/\rho$.

Finally suppose that $d^{I_{\infty}}(S)=d^{\ast}(S)=1/\rho$. We must have
‘equality’ in Claim 7.1.1 and (4). That is, $\mu(C_{1}^{(1)}\cup\dotsb\cup
C_{1}^{(m)})\gtrsim 1$ and $d^{I_{\infty}}(S^{(\ell)}\cap
C_{1}^{(\ell)}\mathcal{F})\gtrsim 1/\rho\cdot\mu(C_{1}^{(\ell)})$ for all
$\ell\in[m]$. Take $\ell$ with $\mu(C_{1}^{(\ell)})\geqslant 1/(2m)$. Then, by
Observation 6.4,
$d^{I_{\infty}}_{C_{1}^{(\ell)}\mathcal{F}}(S^{(\ell)})\gtrsim 1/\rho$. But
then (3) gives $d_{\sup}^{I_{\infty}}(S)\lesssim 1/\rho$. Since $\varepsilon$
can be arbitrarily small, we have $d_{\sup}^{I_{\infty}}(S)\leqslant 1/\rho$,
as required. ∎

We now show that there is always a sequence of sets satisfying Proposition
7.1. The sequence chosen here is motivated by the proofs of Propositions 5.3
and 5.4.

######  Proposition 7.2.

For every integer $k\geqslant 2$ there is a sequence $A_{1},\dotsc,A_{m}$
satisfying the hypothesis of Proposition 7.1.

###### Proof.

We deal with the cases $k=2,3,5,7,13$ first.

  * •

$k=2$: take $A_{1}=\\{1\\}$ (with $d_{1}=1$),

  * •

$k=3$: take $A_{1}=\\{1,2\\}$ (with $d_{1}=d_{2}=1$) and $A_{2}=\\{1\\}$ (with
$d_{1}=d_{2}=1$),

  * •

$k=5$: take $A_{1}=\\{1,3\\}$ (with $d_{1}=d_{2}=2$) and $A_{2}=\\{1\\}$ (with
$d_{1}=d_{2}=2$),

  * •

$k=7$: take

$\displaystyle A_{1}=\\{1,3\\}$ $\displaystyle(\text{with
}d_{1}=d_{2}=d_{3}=2),$ $\displaystyle A_{2}=\\{1,2\\}$
$\displaystyle(\text{with }d_{1}=d_{2}=d_{3}=1),$ $\displaystyle
A_{3}=\\{1,4\\}$ $\displaystyle(\text{with }d_{1}=d_{2}=d_{3}=1),\text{ and}$
$\displaystyle A_{4}=\\{1\\}$ $\displaystyle(\text{with
}d_{1}=d_{2}=d_{3}=1),$

  * •

$k=13$: take

$\displaystyle A_{1}=\\{1,4\\}$ $\displaystyle(\text{with
}d_{1}=d_{2}=d_{3}=d_{4}=3),$ $\displaystyle A_{2}=\\{1,2\\}$
$\displaystyle(\text{with }d_{1}=d_{2}=d_{3}=d_{4}=3),$ $\displaystyle
A_{3}=\\{1,3,5,7\\}$ $\displaystyle(\text{with }d_{1}=d_{2}=d_{3}=d_{4}=1),$
$\displaystyle A_{4}=\\{1,3\\}$ $\displaystyle(\text{with
}d_{1}=d_{2}=d_{3}=d_{4}=1),$ $\displaystyle A_{5}=\\{1,5\\}$
$\displaystyle(\text{with }d_{1}=d_{2}=d_{3}=d_{4}=1),\text{ and}$
$\displaystyle A_{6}=\\{1\\}$ $\displaystyle(\text{with
}d_{1}=d_{2}=d_{3}=d_{4}=1).$

We now turn to $k\notin\\{2,3,5,7,13\\}$. For positive integers $d$ and $t$,
let $B_{d,t}\coloneqq\\{1,d+1,2d+1,\dotsc,td+1\\}$. We construct
$A_{1},A_{2},\dotsc$ by taking all the sets $B_{d,t}$ for $1\leqslant
d\leqslant\rho-1$ and $1\leqslant t<(k-1)/d$ in the order of decreasing $d$
and then decreasing $t$, and add the set $\\{1\\}$ to the end.

Consider a set $A_{\ell}=B_{d,t}$. We need to show that $A_{\ell}$ satisfies
Proposition 7.1. Let $s\in\mathbb{Z}^{+}$ be maximal such that
$ds\leqslant\rho-1$, and $\alpha\in\mathbb{Z}^{+}$ be minimal such that
$\alpha d(d+1)\geqslant k-1$. For $1\leqslant i\leqslant\rho-1$, define

$d_{i}=\begin{cases}\alpha d&\text{if }i\equiv 0\bmod{s+1}\text{ and
}\alpha\neq 2,\\\ d&\text{otherwise}.\end{cases}$

For any $1\leqslant i\leqslant j\leqslant\rho-1$, we have that
$d_{i}+d_{i+1}+\dots+d_{j}=\beta d$ for some integer $\beta$ satisfying
$1\leqslant\beta\leqslant\rho-1+(\alpha-1)(\rho-1)/(s+1)$. Moreover, by
definition of the $d_{i}$, either $\beta\geqslant\alpha$ or $\beta\leqslant
s$. Note that

$1+(d_{i}+d_{i+1}+\dots+d_{j})A_{\ell}=\\{1+\beta d,1+(\beta+1)d,\dots,1+\beta
d(td+1)\\}.$

If $\beta=1$, then
$B_{d,t+1}\subset\\{1\\}\cup(1+(d_{i}+d_{i+1}+\dots+d_{j})A_{\ell})$. Now,
either $k\in B_{d,t+1}$ or $B_{d,t+1}=A_{\ell^{\prime}}$ for some
$\ell^{\prime}<\ell$ and so $A_{\ell}$ satisfies Proposition 7.1.

If $1<\beta\leqslant s$, then $B_{\beta
d,1}\subset\\{1\\}\cup(1+(d_{i}+d_{i+1}+\dots+d_{j})A_{\ell})$. Since $d<\beta
d\leqslant ds\leqslant\rho-1$, it holds that $B_{\beta d,1}=A_{\ell^{\prime}}$
for some $\ell^{\prime}<\ell$ and so $A_{\ell}$ satisfies Proposition 7.1.

If $\beta\geqslant\alpha$, we claim that $k\in
1+(d_{i}+d_{i+1}+\dots+d_{j})A_{\ell}$. Since $k-1$ is a multiple of $d$, it
suffices to show that $\beta d\leqslant k-1\leqslant\beta d(td+1)$. Firstly,

$\beta d(td+1)\geqslant\alpha d(d+1)\geqslant k-1.$

For the second inequality, if $d\leqslant\rho-2$, it holds that $\alpha
d(d+1)=k-1$ as observed in the proof of Proposition 5.4. Furthermore, we have

$\beta d\leqslant(\rho+(\alpha-1)\rho/(s+1))d\leqslant(\rho+(\alpha-1)d)d.$

where the second inequality follows from $d(s+1)\geqslant\rho$. This is less
than $k-1=\alpha d(d+1)$ if $d(\alpha-1)+\rho\leqslant\alpha(d+1)$, which is
true for $k\notin\\{2,3,5,7,13\\}$ as shown in the proof of Proposition 5.4.
On the other hand, if $d=\rho-1$, we have

$\beta
d\leqslant(d+(\alpha-1)d/(s+1))d\leqslant((\alpha+1)/2)d^{2}\leqslant((\alpha+1)/2)d(d+1).$

If $\alpha\geqslant 3$, this is at most $(\alpha-1)d(d+1)<k-1$ as required. If
$\alpha\leqslant 2$, we can observe that $\beta\leqslant\rho-1$ to obtain
$\beta d\leqslant\rho(\rho-1)\leqslant k-1$ where the last inequality was
shown in the proof of Proposition 5.3. In all cases, we have $\beta d\leqslant
k-1$ as required. Hence, $k\in 1+(d_{i}+d_{i+1}+\dots+d_{j})A_{\ell}$, and so
$A_{\ell}$ satisfies Proposition 7.1.

Finally, for $A_{\ell}=\\{1\\}$, we can simply pick
$d_{1}=\dots=d_{\rho-1}=1$. We then get that
$B_{j-i+1,1}\subset\\{1\\}\cup(1+(d_{i}+d_{i+1}+\dots+d_{j})A_{\ell})$. Since
$1\leqslant j-i+1\leqslant\rho-1$, it holds that
$B_{j-i+1,1}=A_{\ell^{\prime}}$ for some $\ell^{\prime}<\ell$ and so
$A_{\ell}$ satisfies Proposition 7.1. ∎

Propositions 7.1 and 7.2 combine to give Theorem 3.5(b) and so we have indeed
proved Theorem 3.5 in this section, as promised.

##  8 Product-free sets in the free group

We now adapt our methods to the free group and prove Theorem 1.8. Throughout,
$F$ denotes the free group on a finite alphabet $\mathcal{A}$, and $S\subset
F$ is a $k$-product-free set whose density we want to bound. We always assume
that all words are in reduced form. Moreover, _$AB$_ denotes the product of
two sets $A,B\subset F$ without cancellation, that is

$AB\coloneqq\\{w\in F:\text{ there is a substring decomposition }w=ab\text{
with }a\in A\text{ and }b\in B\\}.$

In particular, $CF$ consists of all words with a prefix in $C$. We equip $F$
with the measure _$\mu$_ defined as $\mu(w)=1/\lvert F(\lvert w\rvert)\rvert$.
If $\mathbf{W}=\alpha_{1}\alpha_{2}\dotsb$ is a random infinite word where
each $\alpha_{i+1}$ is an independent uniformly random letter other than
$\alpha_{i}^{-1}$, then

$\mu(w)=\mathbb{P}(\mathbf{W}\text{ hits
}w)=\begin{cases}(2\lvert\mathcal{A}\rvert)^{-1}(2\lvert\mathcal{A}\rvert-1)^{-(\lvert
w\rvert-1)}&\text{if $w$ is not the empty word},\\\
1&\text{otherwise}.\end{cases}$

As before, for $B\subset F$, $\mu(B)=\sum_{w\in B}\mu(w)$ is the expected
number of times that $\mathbf{W}$ hits $B$. So, we can make the following
observations corresponding to Observations 2.1 and 3.1.

######  Observation 8.1.

If $C\subset F$ is prefix-free, then $\mu(C)\leqslant 1$,
$\mu(CF(n))\leqslant\mu(C)$ for all $n$, and $\mu(CF(n))=\mu(C)$ if $C$ is
finite and $n\geqslant\max C$.

We now define the relative density of subsets of $F$ as follows.

######  Definition 8.2 (relative density).

Let $B\subset F$, and $G$ be a subsemigroup of $F$ with $G(n)\neq\varnothing$
for all sufficiently large $n$. If $I$ is an interval, then the _relative
density of $B$ in $G$ on interval $I$_ is

$d_{G}^{I}(B)\coloneqq\frac{\mu(B(I)\cap
G)}{\mu(G(I))}=\mu(G(I))^{-1}\sum_{n\in I}\mu(B(n)\cap G).$

If $G(I)=\varnothing$, we will take the relative density to be $0$ by
convention, and $d^{I}(B)\coloneqq d_{F}^{I}(B)$.

The upper Banach density of $B$ is then
$d^{\ast}(B)=\limsup_{I\to\infty}d^{I}(B)$. At this point, we can again
diagonalise to obtain a sequence $(I_{j})$ is such that, for every $G$ and $B$
that we consider in our proofs, $(d_{G}^{I_{j}}(B))$ converges to some limit
_$d^{I_{\infty}}_{G}(B)$_ , and $d^{I_{\infty}}(S)=d^{\ast}(S)$. These limits
are again additive. Also note that $d_{G}^{I}(B)=d^{I}(B\cap G)/d^{I}(G)$ and
so $d^{I_{\infty}}_{G}(B)=d^{I_{\infty}}(B\cap G)/d^{I_{\infty}}(G)$ if
$d^{I_{\infty}}(G)>0$. We define sup density as follows.

######  Definition 8.3 (sup density).

For a set $B$, the _sup density of $B$ in $G$_ is

$d_{\sup G}^{I_{\infty}}(B)\coloneqq\sup_{w\in G}d^{I_{\infty}}_{wF\cap
G}(B).$

From now on, let $G=F^{\alpha\beta}\subset F$ be the subsemigroup of $F$
consisting of all words starting with $\alpha$ and ending in $\beta$ where
$\alpha,\beta\in\mathcal{A}\cup\mathcal{A}^{-1}$ and $\alpha\neq\beta^{-1}$. A
random sequence argument shows the following.

######  Observation 8.4.

Let $C\subset G$ be finite and prefix-free. Then, for all $n\geqslant\max
C+2$,

$\mu((CF\cap G)(n))\geqslant\frac{\mu(C)}{(2\lvert\mathcal{A}\rvert-1)^{2}}.$

In particular, $d^{I_{\infty}}(wF\cap G)>0$ for all $w\in G$. As in Lemma 3.3,
subtree densities of $G$ satisfy the property that we may strip away prefixes.

######  Lemma 8.5.

If $w,v\in G$, then $d^{I_{\infty}}_{wvF\cap G}(wB)=d^{I_{\infty}}_{vF\cap
G}(B)$.

###### Proof.

For $u\in G$, note that $\mu(wu)=a\cdot\mu(u)$ where $a=(2\lvert
A\rvert-1)^{-\lvert w\rvert}$. So, if $X\subset G$ is finite, then
$\mu(wX)=a\cdot\mu(X)$. Let $I$ be any interval with $\min I>\lvert wv\rvert$.
Then

$d^{I}_{wvF\cap G}(wB)=\frac{\mu((wB)(I)\cap wvF)}{\mu((wvF\cap
G)(I))}=\frac{\mu(B(I-\lvert w\rvert)\cap vF)}{\mu((vF\cap G)(I-\lvert
w\rvert))}.$

where we used that $wvF\cap G=w(vF\cap G)$. For any $X\subset G$, the fact
that $\mu(X(n))\in[0,1]$ implies that

$\lvert\mu(X(I))-\mu(X(I-\lvert w\rvert))\rvert=\bigg{\lvert}\sum_{n\in
I}\mu(X(n))-\sum_{n\in I-\lvert w\rvert}\mu(X(n))\bigg{\rvert}\leqslant\lvert
w\rvert.$

Therefore,

$\frac{\mu(B(I)\cap vF)-\lvert w\rvert}{\mu((vF\cap G)(I))+\lvert
w\rvert}\leqslant d^{I}_{wvF\cap G}(wB)\leqslant\frac{\mu(B(I)\cap vF)+\lvert
w\rvert}{\mu((vF\cap G)(I))-\lvert w\rvert}.$

Set $I=I_{j}$ and take $j$ to infinity. From $d^{I_{\infty}}(vF\cap G)>0$ it
follows $\mu((vF\cap G)(I_{j}))\to\infty$. Hence, both bounds above tend to
$d^{I_{\infty}}_{vF\cap G}(B)$ and so $d^{I_{\infty}}_{wvF\cap
G}(wB)=d^{I_{\infty}}_{vF\cap G}(B)$. ∎

We can also obtain the following analogue to Observation 6.4.

######  Observation 8.6.

Let $C\subset G$ be finite and prefix-free. Then

$d^{I_{\infty}}_{CF\cap G}(B)=\sum_{c\in C}\frac{d^{I_{\infty}}(cF\cap
G)}{d^{I_{\infty}}(CF\cap G)}\cdot d^{I_{\infty}}_{cF\cap
G}(B)=\frac{d^{I_{\infty}}(B\cap CF)}{d^{I_{\infty}}(CF\cap G)}.$

###### Proof.

Because $d^{I_{\infty}}(cF\cap G)>0$ for all $c\in C$, and therefore also
$d^{I_{\infty}}(CF\cap G)>0$, it holds that

$d^{I_{\infty}}_{cF\cap G}(B)=\frac{d^{I_{\infty}}(B\cap
cF)}{d^{I_{\infty}}(cF\cap G)}\quad\text{ and }\quad d^{I_{\infty}}_{CF\cap
G}(B)=\frac{d^{I_{\infty}}(B\cap CF)}{d^{I_{\infty}}(CF\cap G)}.$

Since $d^{I_{\infty}}$ is additive, this implies that

$d^{I_{\infty}}_{CF\cap G}(B)=\frac{d^{I_{\infty}}(B\cap
CF)}{d^{I_{\infty}}(CF\cap G)}=\sum_{c\in C}\frac{d^{I_{\infty}}(B\cap
cF)}{d^{I_{\infty}}(CF\cap G)}=\sum_{c\in C}\frac{d^{I_{\infty}}(cF\cap
G)}{d^{I_{\infty}}(CF\cap G)}\cdot d^{I_{\infty}}_{cF\cap G}(B).\qed$

Steeplechases in the free group can be defined exactly as for the free
semigroup.

######  Definition 8.7 (steeplechase).

An infinite sequence $(C_{k})$ of subsets of $G$ is a _steeplechase_ if, for
each positive integer $k$,

  * •

each $C_{k}$ is prefix-free and finite,

  * •

every word in $C_{k+1}$ has a proper prefix in $C_{k}$ (in particular,
$C_{k+1}F\subset C_{k}F$).

Steeplechase $(C_{k})$ is _spread_ if $\max C_{k}<\min C_{k+1}$ for all $k$
and is _$\varepsilon$ -tight_ if, for all $m,n$,
$\lvert\mu(C_{m})-\mu(C_{n})\rvert\leqslant\varepsilon$.

The following lemma is an analogue to Lemma 6.2.

######  Lemma 8.8.

Let $\varepsilon>0$ and $B\subset G$. There is an $\varepsilon$-tight spread
steeplechase $(C_{k})$ such that

  * •

$C_{1}\cup C_{2}\cup\dotsb\subset B$,

  * •

for all $k$ and all large $n$ (in terms of $k$), $\mu((B\setminus
C_{k}F)(n))\leqslant\varepsilon$,

  * •

for all $k$, $\mu(C_{k})/d^{I_{\infty}}(G)\geqslant
d^{I_{\infty}}_{G}(B)-\varepsilon$.

###### Proof.

This is very similar to the proof of Lemma 6.2. For each positive integer $k$,
let $D_{k}=\\{x\in B\colon h(x)=k\\}$. Iteratively do the following for each
positive integer $k$.

  1. 1.

Let $\ell_{k}$ be such that
$\mu(D_{k}(\\{\ell_{k}+1,\ell_{k}+2,\dotsc\\}))\leqslant\varepsilon\cdot
d^{I_{\infty}}(G)/2^{k}$.

  2. 2.

Let $C_{k}=D_{k}(\\{1,2,\dotsc,\ell_{k}\\})$.

  3. 3.

Remove $(D_{k}\setminus C_{k})F$ from $B$ (including from all later $D_{i}$).

Then $(C_{k})$ is a steeplechase and $C_{1}\cup C_{2}\cup\dotsb\subset B$. Fix
$k$ and let $n>\max\\{\ell_{1},\dotsc,\ell_{k}\\}$. Then,

$\mu((B\setminus C_{k}F)(n))\leqslant\sum_{t}\mu(((D_{t}\setminus
C_{t})F)(n))\leqslant\sum_{t}\mu(D_{t}\setminus
C_{t})\leqslant\varepsilon\cdot d^{I_{\infty}}(G)\leqslant\varepsilon.$

Finally, this implies that $\mu(B(n))\leqslant\mu(C_{k}F(n))+\varepsilon\cdot
d^{I_{\infty}}(G)=\mu(C_{k})+\varepsilon\cdot d^{I_{\infty}}(G)$. Averaging
this over $n\in I_{j}$ and taking $j\to\infty$ gives
$d^{I_{\infty}}(B)\leqslant\mu(C_{k})+\varepsilon\cdot d^{I_{\infty}}(G)$ and
therefore
$d^{I_{\infty}}_{G}(B)=d^{I_{\infty}}(B)/d^{I_{\infty}}(G)\leqslant\mu(C_{k})/d^{I_{\infty}}(G)+\varepsilon$.
By passing to a subsequence, we may assume that $(C_{k})$ is spread and
$\varepsilon$-tight. ∎

We call the steeplechase $(C_{k})$ given by Lemma 8.8 an _$\varepsilon$
-capturing steeplechase for $B$_. There is also an analogue to Lemma 6.3.

######  Lemma 8.9.

Let $(C_{k})$ be an $\varepsilon$-tight spread steeplechase. For every $w\in
G$ there is an $N$ such that the following holds. If $C=C_{1}\cup
C_{2}\cup\dotsb\cup C_{N}$ and $n\geqslant\max C_{N}+\lvert w\rvert$, then

$\mu(((C_{1}F\cap G)\setminus(CwF\cap G))(n))\leqslant 2\varepsilon.$

###### Proof.

Note that $(C_{1}F\cap G)\setminus(CwF\cap G)=(C_{1}F\setminus CwF)\cap
G\subset C_{1}F\setminus CwF$, and so it suffices to show that
$\mu((C_{1}F\setminus CwF)(n))\leqslant 2\varepsilon$.

We can show this exactly as in the proof of Lemma 6.3, we only need
$\mathbf{W}$ to be the random walk from the beginning of this section. As a
consequence, if $\mathbf{W}$ hits $C_{i}$, the probability that the next
$\lvert w\rvert$ letters of $\mathbf{W}$ spell $w$ is
$(2\lvert\mathcal{A}\rvert-1)^{-\lvert w\rvert}$. Importantly, this uses the
fact that the last letter of a word in $C_{i}$ is $\beta$ and the first letter
of $w$ is $\alpha$, and $\alpha\neq\beta^{-1}$. ∎

Now we can prove the key technical lemma for our density results,
corresponding to Lemma 6.5.

######  Lemma 8.10.

Let $\varepsilon>0$ and let $A,B\subset G$. If $(C_{k})$ is an
$\varepsilon$-capturing steeplechase for $A$ with
$\mu(C_{1})\geqslant(2\lvert\mathcal{A}\rvert-1)^{2}(2\varepsilon+\varepsilon^{1/3})$,
then

$d^{I_{\infty}}_{C_{1}F\cap G}(AB)\geqslant d_{\sup
G}^{I_{\infty}}(B)-3\varepsilon^{1/3}.$

###### Proof.

Observation 8.4 implies that $\mu((C_{1}F\cap
G)(n))\geqslant\mu(C_{1})/(2\lvert\mathcal{A}\rvert-1)^{2}\geqslant
2\varepsilon+\varepsilon^{1/3}$ for $n\geqslant\max C_{1}+2$. We proceed as in
the proof of Lemma 6.5. Let $w\in G$ be such that

$d^{I_{\infty}}_{wF\cap G}(B)\geqslant d_{\sup
G}^{I_{\infty}}(B)-\varepsilon^{1/3}.$

Apply Lemma 8.9 to $(C_{k})$ and $w$ to give an $N$ such that letting
$C=C_{1}\cup\dotsb\cup C_{N}$, if $n\geqslant\max C_{N}+\lvert w\rvert$, then
$\mu(((C_{1}F\cap G)\setminus(CwF\cap G))(n))\leqslant 2\varepsilon$. We may
greedily choose $\widetilde{C}\subset C$ such that $\widetilde{C}w$ is prefix-
free and $\widetilde{C}wF=CwF$. Note that

$\displaystyle 2\varepsilon$ $\displaystyle\geqslant\mu(((C_{1}F\cap
G)\setminus(\widetilde{C}wF\cap G))(n))$
$\displaystyle\geqslant\mu((C_{1}F\cap G)(n))-\mu((\widetilde{C}wF\cap G)(n))$
$\displaystyle\geqslant
2\varepsilon+\varepsilon^{1/3}-\mu((\widetilde{C}wF\cap G)(n))$

and so $\mu((\widetilde{C}wF\cap G)(n))\geqslant\varepsilon^{1/3}$ as well as
$\mu((C_{1}F\cap G)(n))\leqslant\mu((\widetilde{C}wF\cap G)(n))+2\varepsilon$.

Let $I$ be an interval with $\min I\geqslant\max C_{N}+\lvert w\rvert$, so
$\mu((\widetilde{C}wF\cap G)(I))\geqslant\lvert I\rvert\varepsilon^{1/3}$ and
$\mu((C_{1}F\cap G)(I))\leqslant\mu((\widetilde{C}wF\cap G)(I))+\lvert I\rvert
2\varepsilon$. Let $X\subset G$. Note that $\widetilde{C}wF\subset C_{1}F$ and
so

$\displaystyle d^{I}_{C_{1}F\cap G}(X)$ $\displaystyle=\frac{\mu(X(I)\cap
C_{1}F)}{\mu((C_{1}F\cap
G)(I))}\geqslant\frac{\mu(X(I)\cap\widetilde{C}wF)}{\mu((C_{1}F\cap
G)(I))}\geqslant\frac{\mu(X(I)\cap\widetilde{C}wF)}{\mu((\widetilde{C}wF\cap
G)(I))+\lvert I\rvert 2\varepsilon}.$

Using the fact that $x/(y+\lvert I\rvert 2\varepsilon)\geqslant x/y-\lvert
I\rvert 2\varepsilon x/y^{2}\geqslant x/y-2\varepsilon^{1/3}$ for
$\varepsilon>0$, $0\leqslant x\leqslant\lvert I\rvert$, and $y\geqslant\lvert
I\rvert\varepsilon^{1/3}$, we have

$d^{I}_{C_{1}F\cap G}(X)\geqslant d^{I}_{\widetilde{C}wF\cap
G}(X)-2\varepsilon^{1/3}.$

Setting $X=AB$, $I=I_{j}$, and taking $j$ to infinity gives

$d^{I_{\infty}}_{C_{1}F\cap G}(AB)\geqslant
d^{I_{\infty}}_{\widetilde{C}wF\cap G}(AB)-2\varepsilon^{1/3}.$ (5)

Now,

$\displaystyle d^{I_{\infty}}_{\widetilde{C}wF\cap G}(AB)$
$\displaystyle=\sum_{c\in\widetilde{C}}\frac{d^{I_{\infty}}(cwF\cap
G)}{d^{I_{\infty}}(\widetilde{C}wF\cap G)}\cdot d^{I_{\infty}}_{cwF\cap
G}(AB)$
$\displaystyle\geqslant\sum_{c\in\widetilde{C}}\frac{d^{I_{\infty}}(cwF\cap
G)}{d^{I_{\infty}}(\widetilde{C}wF\cap G)}\cdot d^{I_{\infty}}_{cwF\cap
G}(cB)$ $\displaystyle=\sum_{c\in\widetilde{C}}\frac{d^{I_{\infty}}(cwF\cap
G)}{d^{I_{\infty}}(\widetilde{C}wF\cap G)}\cdot d^{I_{\infty}}_{wF\cap G}(B)$
$\displaystyle=d^{I_{\infty}}_{wF\cap G}(B)\geqslant d_{\sup
G}^{I_{\infty}}(B)-\varepsilon^{1/3},$

where the first equality used Observation 8.6, the first inequality used the
fact that $c\in\widetilde{C}\subset C\subset A$, the second equality used
Lemma 8.5, and the second inequality is due to the choice of $w$. Combining
this with (5) gives the required result. ∎

At this point, we have recovered all important technical results that we
needed to bound the density of (strongly) $k$-product-free sets in the free
semigroup. We can now simply use exactly the same arguments as in Section 7.
We only need to replace $C_{i}\mathcal{F}$ by $C_{i}F\cap G$, $\mu(C_{i})$ by
$d^{I_{\infty}}(C_{i}F\cap G)$, $d_{\sup}^{I_{\infty}}$ by $d_{\sup
G}^{I_{\infty}}$, and all references by references to the corresponding
results in this section to prove the following analogue of Theorem 3.5.

######  Theorem 8.11.

Let $k\geqslant 2$ be an integer, $\mathcal{A}$ be a finite set, $F$ be the
free group with alphabet $\mathcal{A}$, and $G=F^{\alpha\beta}$ be the
subsemigroup of $F$ consisting of all words starting with $\alpha$ and ending
with $\beta$ where $\alpha,\beta\in\mathcal{A}\cup\mathcal{A}^{-1}$ and
$\alpha\neq\beta^{-1}$.

  1. (a)

If $S\subset G$ is strongly $k$-product-free, then
$d^{I_{\infty}}_{G}(S)\leqslant 1/k$. Moreover, if
$d^{I_{\infty}}_{G}(S)=1/k$, then $d_{\sup G}^{I_{\infty}}(S)=1/k$.

  2. (b)

If $S\subset G$ is $k$-product-free, then $d^{I_{\infty}}_{G}(S)\leqslant
1/\rho(k)$. Moreover, if $d^{I_{\infty}}_{G}(S)=1/\rho(k)$, then $d_{\sup
G}^{I_{\infty}}(S)=1/\rho(k)$.

The arguments from Ortega, Rué, and Serra [ORS23] show that a density bound on
(strongly) $k$-product-free sets in $F^{\alpha\beta}$ immediately translates
to a density bound in $F$. Therefore, Theorems 1.3 and 1.8 are immediate
corollaries of Theorem 8.11.

##  9 Open problems

A first natural problem left open is to determine the structure of the
extremal $k$-product-free sets for $k\in\\{3,5,7,13\\}$. For $k=5,7,13$, we
conjecture that the extremal sets are exactly as in Theorem 1.7. The extremal
sets for $k=3$ will be slightly more complicated. Indeed, while
$1+3\mathbb{Z}_{\geqslant 0}$ and $2+3\mathbb{Z}_{\geqslant 0}$ are both
maximal 3-sum-free subsets of the non-negative integers of density $1/3$, so
are both $\\{1,2\\}+6\mathbb{Z}_{\geqslant 0}$ and
$\\{5,6\\}+6\mathbb{Z}_{\geqslant 0}$ (Łuczak and Schoen [ŁS97] showed that
there are no others). We conjecture the corresponding result holds for the
free semigroup.

######  Conjecture 9.1.

Let $\mathcal{A}$ be a finite set and $\mathcal{F}$ be the free semigroup with
alphabet $\mathcal{A}$. If $S\subset\mathcal{F}$ is 3-product-free and
$d^{\ast}(S)=1/3$, then one of the following hold. Either it is possible to
label each letter of $\mathcal{A}$ with a label in $\mathbb{Z}/3\mathbb{Z}$
such that $S$ is a subset of

$\\{w\in\mathcal{F}\colon\text{the sum of the labels of letters in $w$ is
$1\bmod{3}$}\\},$

or it is possible to label each letter of $\mathcal{A}$ with a label in
$\mathbb{Z}/6\mathbb{Z}$ such that $S$ is a subset of

$\\{w\in\mathcal{F}\colon\text{the sum of the labels of letters in $w$ is
$1,2\bmod{6}$}\\}.$

Łuczak [Łuc95] proved that every sum-free subset of the non-negative integers
with density greater than $2/5$ is a subset of the odd integers (Łuczak and
Schoen proved similar results for (strongly) $k$-sum-free sets). Such
strengthenings for subsets of the free semigroup are false as the constants
$1/k$ in Theorem 1.4 and $1/\rho(k)$ in Theorem 1.7 cannot be replaced by
anything smaller. For example, let $k=2$, $T$ be the set of words of odd
length, and $x$ be any word of even length. Let

$\begin{split}T^{\prime}\coloneqq&\\{w\in T\colon\text{neither $x$ nor $w$ is
a prefix or suffix of the other}\\}\\\ &\cup\\{xwx\colon\text{$xwx$ has length
$1\bmod{3}$}\\}.\end{split}$

Then $T^{\prime}$ is product-free, has density at least
$1/2-2\lvert\mathcal{A}\rvert^{-\lvert x\rvert}$, and is not a subset of an
odd-occurrence set (in fact, a set of positive density would need to be
removed before this happens). Nonetheless, $T^{\prime}$ is a small
perturbation from the odd-occurrence set $T$. Hence, it is natural to ask
whether there is some form of stability.

######  Conjecture 9.2.

For each $\delta>0$, is there some $\varepsilon>0$ such that if
$S\subset\mathcal{F}$ is product-free and $d^{\ast}(S)>1/2-\varepsilon$, then
there exists an odd-occurrence set $\mathcal{O}_{\Gamma}$ such that
$d^{\ast}(S\setminus\mathcal{O}_{\Gamma})<\delta$?

Theorems 1.4 and 1.7 give the structure of extremal (strongly) $k$-product-
free sets in the free semigroup. The free group case remains. The simplest
open case is the following

######  Conjecture 9.3.

Let $\mathcal{A}$ be a finite set and $F$ be the free group with alphabet
$\mathcal{A}$. If $S\subset F$ is product-free and $d^{\ast}(S)=1/2$, then the
following holds. It is possible to label each letter of
$\mathcal{A}\cup\mathcal{A}^{-1}$ with a label in $\mathbb{Z}/2\mathbb{Z}$
such that the label of $\alpha^{-1}$ is the negation of the label of $\alpha$
for all $\alpha\in\mathcal{A}$ and $S$ is a subset of

$T\coloneqq\\{w\in F\colon\text{the sum of the labels of letters in $w$ is
$1\bmod{2}$}\\}.$

For strongly $k$-product-free we expect the above conjecture to hold with 2
replaced by $k$. For $k$-product-free we expect the behaviour to be the same
as for the free semigroup.

We remark that our methods do give some structure. Similar arguments to
Section 4 show there is a labelling of all words in the subsemigroup
$F^{\alpha\beta}$ (defined in Section 8) such that the label of a
concatenation is the sum of the individual labels and all words in $S\cap
F^{\alpha\beta}$ have label 1. What is missing is an understanding of how the
labellings interact when letters cancel during concatenation.

## References

  * [BPR16] R. Balasubramanian, Gyan Prakash, and D. S. Ramana (Nov. 2016).  Sum-free subsets of finite abelian groups of type III.  _European Journal of Combinatorics_ 58, 181–202.
  * [BS85] László Babai and Vera T. Sós (Jun. 1985).  Sidon sets in groups and induced subgraphs of Cayley graphs.  _European Journal of Combinatorics_ 6(2), 101–114.
  * [CE96] Neil J. Calkin and Paul Erdős (Jul. 1996).  On a class of aperiodic sum-free sets.  _Mathematical Proceedings of the Cambridge Philosophical Society_ 120(1), 1–5.
  * [Ebe16] Sean Eberhard (Feb. 2016).  Product mixing in the alternating group.  _Discrete Analysis_ Paper No. 2, 19.
  * [Gow08] W. T. Gowers (May 2008).  Quasirandom groups.  _Combinatorics, Probability and Computing_ 17(3), 363–387.
  * [GR05] Ben Green and Imre Z. Ruzsa (Dec. 2005).  Sum-free sets in abelian groups.  _Israel Journal of Mathematics_ 147, 157–188.
  * [Ked09] Kiran S. Kedlaya (2009).  Product-free subsets of groups, then and now.  _Communicating mathematics_ , _Contemporary Mathematics_ , vol. 479, 169–177.
  * [KLM22] Peter Keevash, Noam Lifshitz, and Dor Minzer (May 2022).  On the largest product-free subsets of the alternating groups.  arXiv:2205.15191.
  * [Lev03] Vsevolod F. Lev (Feb. 2003).  Sharp estimates for the number of sum-free sets.  _Journal für die Reine und Angewandte Mathematik_ 555, 1–25.
  * [LLNW20] Imre Leader, Shoham Letzter, Bhargav Narayanan, and Mark Walters (Jan. 2020).  Product-free sets in the free semigroup.  _European Journal of Combinatorics_ 83, 103003.
  * [ŁS97] Tomasz Łuczak and Tomasz Schoen (Oct. 1997).  On infinite sum-free sets of natural numbers.  _Journal of Number Theory_ 66(2), 211–224.
  * [Łuc95] Tomasz Łuczak (May 1995).  A note on the density of sum-free sets.  _Journal of Combinatorial Theory. Series A_ 70(2), 334–336.
  * [ORS23] Miquel Ortega, Juanjo Rué, and Oriol Serra (Feb. 2023).  Product-free sets in the free group.  arXiv:2302.03748.
  * [TV17] Terence Tao and Van Vu (Jun. 2017).  Sum-free sets in groups: a survey.  _Journal of Combinatorics_ 8(3), 541–552.