# Product-free sets in the free group

Miquel Ortega  Juanjo Rué  Oriol Serra Departament de Matemàtiques and
Institut de Matemàtiques (IMTech) de la Universitat Politècnica de Catalunya
(UPC), and Centre de Recerca Matemàtica (CRM), Barcelona, Spain. E-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We prove that product-free sets of the free group over a finite alphabet have
maximum density $1/2$ with respect to the natural measure that assigns total
weight one to each set of irreducible words of a given size. This confirms a
conjecture of Leader, Letzter, Narayanan and Walters. In more general terms,
we actually prove that strongly $k$-product-free sets have maximum density
$1/k$ in terms of the said measure.

##  1 Introduction

A subset $S$ of a group is said to be _product-free_ if there do not exist
$x,y,z\in S$ (not necessarily distinct) such that $z=x\cdot y$. Much has been
studied about product-free subsets of finite groups, particularly so in the
abelian case, where they are usually called _sum-free subsets_ (see, for
example, the survey by Tao and Vu [7]). The study of product–free subsets in
nonabelian groups can be traced back to Babai and Sós [1], see the survey by
Kedlaya [3]. Interest on the problem was prompted by the seminal work of
Gowers on quasirandom groups [2].

The study of _product-free_ sets in discrete infinite structures is more
recent. As a first approach to the study of the infinite case, Leader,
Letzter, Narayanan, and Walters in [6] proved that product-free subsets of the
free _semigroup_ on the finite alphabet $\mathcal{A}$ have maximum density
$1/2$ with respect to the measure that assigns a weight of
$|\mathcal{A}|^{-n}$ to every word of length $n$. They conjectured that this
is also true for the analogous measure on the free group. The main purpose of
the present paper is to provide a proof of this conjecture.

More precisely, let us write $\mathcal{F}$ for the free group over a finite
alphabet $\mathcal{A}$. For $n\geq 1$ and $A\subseteq\mathcal{F}$, we write
$A(n)=\left\\{w\in A\colon|w|=n\right\\}$ for the set of elements of $A$ whose
reduced words have length $n$, and $A_{\leq n}$ for those that have length
smaller or equal than $n$. We define a measure $\mu$ on $\mathcal{F}$ such
that $\mu(\left\\{w\right\\})=1/|\mathcal{F}(|w|)|$ for all $w\in\mathcal{F}$,
so that every layer of words of a given length has the same total weight.
Finally, we write $\bar{d}(A)=\limsup_{n\to\infty}\frac{\mu(A_{\leq
n})}{\mu(\mathcal{F}_{\leq n})}$ for the upper density of $A$. Our main result
can be phrased as follows.

######  Theorem 1.

Let $S\subseteq\mathcal{F}$ be a product-free subset. Then

$\bar{d}(S)\leq\frac{1}{2}.$ (1)

We actually study a generalisation of this result. Following the notion by
Łuczak and Schoen [5] we call a subset $S$ of a semigroup _$k$ -product-free_
for $k\geq 2$ if there are no $x_{1},\dots,x_{k},y\in S$ such that $x_{1}\dots
x_{k}=y$ and, furthermore, we call $S$ _strongly_ $k$-product-free if it is
$l$-product-free for all $l$ with $2\leq l\leq k$. We are able to prove the
following.

######  Theorem 2.

Let $S\subseteq\mathcal{F}$ be a strongly $k$-product-free subset for $k\geq
2$. Then

$\bar{d}(S)\leq\frac{1}{k}.$ (2)

Fixing an arbitrary $x\in\mathcal{A}$, the natural example of the set
$S\subseteq\mathcal{F}$ consisting of words such that the number of $x$ minus
the number of $x^{-1}$ in its reduced form is congruent to $1$ modulo $k$,
which is strongly $k$–product–free and has upper density $\bar{d}(S)=1/k$,
shows that the upper bound in Theorem 2 is best possible.

The paper is organised as follows. In Section 2 we reduce the problem to
certain subsemigroups of the free group and state the key result, Proposition
1, which provides the proof of Theorem 2. Section 3 is devoted to the proof of
Proposition 1. For $2\leq k\leq 3$, the proof is inspired by the arguments
used in [6] for the case of semigroups, and we give a separate proof for this
case for clarity of exposition. The general case is somewhat more involved and
uses a density increment argument to first reach a pseudorandom subset of our
given set, in which the general argument carries over. The paper concludes
with final remarks in Section 4.

To conclude, we also want to remark that the statement of Theorem 2 also holds
in the free semigroup, which actually was the model where we first worked out
the proof, and it is a generalisation of the main theorem in [6].

######  Theorem 3.

For any finite alphabet $\mathcal{A}$, a strongly $k$-product-free of the free
semigroup over $\mathcal{A}$ has upper density at most $1/k$.

The straightforward translation of the arguments in the proof of Theorem 2 to
the case of semigroups is discussed in the final section.

##  2 Reduction to a semigroup

Throughout the proof, we identify every element of $\mathcal{F}$ with its
reduced word (for example, the length of $w\in\mathcal{F}$ is the length of
its reduced word) and assume that $|\mathcal{A}|\geq 2$. If $|\mathcal{A}|=1$,
the free group is isomorphic to the integers, where the result is
straightforward.

We write $\mathcal{F}^{xy}\subseteq\mathcal{F}$ for the subset of words that
begin with $x$ and end in $y$ (with $x,y\in\mathcal{A}\cup\mathcal{A}^{-1})$.
The first step of the proof consists in reducing the proof of Theorem 2 to an
analogous statement over $\mathcal{F}^{xy}$ with $x\neq y^{-1}$. This ambient
space has the advantage of having no cancellation when multiplying, so it is
much closer to the case of the free semigroup, and we will then be able to use
ideas similar in spirit to those of [6].

For a given family $\mathcal{H}\subseteq\mathcal{F}$ and a subset
$A\subseteq\mathcal{H}$, we define the _relative upper density_ of $A$ as

$\bar{d}_{\mathcal{H}}(A)=\limsup_{n\to\infty}\frac{\mu(A_{\leq
n})}{\mu(\mathcal{H}_{\leq n})}.$

The analogous result to Theorem 2 then reads as follows.

######  Proposition 1.

Let $S\subseteq\mathcal{F}^{xy}$ be a strongly $k$-product-free with $k\geq 2$
and $x\neq y^{-1}$. Then

$\bar{d}_{\mathcal{F}^{xy}}(S)\leq\frac{1}{k}.$

We will prove this result in the following sections. In this section, we
deduce Theorem 2 from it. First, though, we need the following straightforward
estimate on the size of each layer $\mathcal{F}^{xy}(n)$.

######  Lemma 1.

For any $x,y\in\mathcal{A}\cup\mathcal{A}^{-1}$ and $n\in\mathbb{N}$, it holds
that

$\left|\frac{|\mathcal{F}^{xy}(n)|}{|\mathcal{F}(n)|}-\frac{1}{4|\mathcal{A}|^{2}}\right|<\frac{1}{(2|\mathcal{A}|-1)^{n-1}}.$

###### Proof.

Define the sequences $a_{n}=|\mathcal{F}^{xx}(n)|$,
$b_{n}=|\mathcal{F}^{xx^{-1}}(n)|$ and $c_{n}=|\mathcal{F}^{xy}(n)|$ when
$x\neq y,y^{-1}$. These satisfy

$\begin{cases}a_{n}=a_{n-1}+(2|\mathcal{A}|-2)c_{n-1}\\\
b_{n}=b_{n-1}+(2|\mathcal{A}|-2)c_{n-1}\\\
c_{n}=a_{n-1}+b_{n-1}+(2|\mathcal{A}|-3)c_{n-1}\end{cases}$

for $n\geq 2$ and $a_{1}=1$, $b_{1}=c_{1}=0$.

By subtracting the first two equations, we see that
$a_{n}-b_{n}=a_{n-1}-b_{n-1}=1$. Furthermore, subtracting the remanining
equation we obtain that
$a_{n}-c_{n}=c_{n-1}-a_{n-1}+1=a_{n-2}-c_{n-2}=\frac{1+(-1)^{n+1}}{2}$. From
this we obtain that

$|\mathcal{F}^{xy}(n)|=\begin{cases}\frac{(2|\mathcal{A}|-1)^{n-1}+2+(-1)^{n-1}}{2|\mathcal{A}|}&\text{
for }x=y,\\\
\frac{(2|\mathcal{A}|-1)^{n-1}+2+(-1)^{n-1}}{2|\mathcal{A}|}-1&\text{ for
}x=y^{-1},\\\
\frac{(2|\mathcal{A}|-1)^{n-1}+(-1)^{n-2}}{2|\mathcal{A}|}&\text{ in other
cases.}\end{cases}$

Dividing by $|\mathcal{F}(n)|=2|\mathcal{A}|(2|\mathcal{A}|-1)^{n-1}$ gives
the result. ∎

With this estimate in hand and assuming the result over $\mathcal{F}^{xy}$, we
are ready to prove the main theorem.

###### Proof of Theorem 2 assuming Proposition 1.

Let $\mathcal{I}$ be the set of tuples $(w,x,y)$, with $w\in\mathcal{F}$ and
$x,y\in\mathcal{A}\cup\mathcal{A}^{-1}$ such that $wxyw^{-1}$ admits no
cancellation. For $w,x,y\in\mathcal{I}$ write $S^{w,x,y}\subseteq S$ for the
elements of $S$ that may be written as $wx\alpha yw^{-1}$. Note that, since we
imposed that $x\neq y^{-1}$, the elements of $S$ belong to a unique
$S^{w,x,y}$.

Let us define the map $\pi\colon S\to\mathcal{F}^{xy}$ that strips out $w$ and
$w^{-1}$ from the elements of $S^{w,x,y}$, meaning that

$\pi(wx\alpha yw^{-1})=x\alpha y$

for $wx\alpha yw^{-1}\in S^{w,x,y}$. In other words, the map $\pi$ sends an
element of $S$ to its cyclically reduced word.

Set a fixed $\varepsilon>0$. Since $S$ is strongly $k$-product-free, so is
$S^{w,x,y}$, and, because $\pi$ preserves products and is injective when
restricted to $S^{w,x,y}$, so is $\pi(S^{w,x,y})$. In that case, Proposition 1
tells us that $\pi(S^{w,x,y})\subseteq\mathcal{F}^{xy}$ has relative upper
density at most $1/k$. Hence, for each $w,x,y$, there exists
$n_{0}=n_{0}(w,x,y)$ such that

$\frac{\mu(\pi(S^{w,x,y}_{\leq n}))}{\mu(\mathcal{F}^{xy}_{\leq
n})}<\frac{1}{k}+\varepsilon.$ (3)

for all $n\geq n_{0}$.

Let $N_{0}$ be large enough so that (3) holds for all $w,x,y$ with $|w|\leq
l_{0}$ and $n\geq N_{0}$, with $l_{0}$ to be fixed later on. Our goal is to
bound

$\frac{\mu(S_{\leq n})}{n}=\sum_{\mathcal{I}}\frac{\mu(S^{w,x,y}_{\leq
n})}{n}=\sum_{\begin{subarray}{c}\mathcal{I},\\\ |w|\leq
l_{0}\end{subarray}}\frac{\mu(S^{w,x,y}_{\leq
n})}{n}+\sum_{\begin{subarray}{c}\mathcal{I},\\\
|w|>l_{0}\end{subarray}}\frac{\mu(S^{w,x,y}_{\leq n})}{n}$ (4)

for large $n$. Let us first bound the sum where $|w|>l_{0}$. In that case, we
may use the crude bound

$\sum_{\begin{subarray}{c}\mathcal{I},\\\
|w|>l_{0}\end{subarray}}\frac{\mu(S^{w,x,y}_{\leq
n})}{n}\leq\sum_{\begin{subarray}{c}\mathcal{I},\\\
|w|>l_{0}\end{subarray}}\frac{1}{n}\sum_{i>2|w|}^{n}\frac{|\mathcal{F}(i-2|w|)|}{|\mathcal{F}(i)|}\\\
\leq\sum_{l>l_{0}}|\mathcal{F}(l)|(2|\mathcal{A}|-1)^{-2l}\leq
2|\mathcal{A}|\sum_{l>l_{0}}(2|\mathcal{A}|-1)^{-l}<\varepsilon,$

if we take $l_{0}$ large enough in terms of $\varepsilon$. On the other hand,
using (3) we obtain

$\displaystyle\sum_{\begin{subarray}{c}\mathcal{I},\\\ |w|\leq
l_{0}\end{subarray}}\frac{\mu(S^{w,x,y}_{\leq n})}{n}$
$\displaystyle\leq\sum_{\begin{subarray}{c}\mathcal{I},\\\ |w|\leq
l_{0}\end{subarray}}\frac{1}{n}\sum_{i>2|w|}^{n}\frac{|\mathcal{F}(i-2|w|)|}{|\mathcal{F}(i)|}\mu(\pi(S^{w,x,y}_{\leq
n})(i-2|w|))$
$\displaystyle\leq\left(\frac{1}{k}+\varepsilon\right)\sum_{\begin{subarray}{c}\mathcal{I},\\\
|w|\leq l_{0}\end{subarray}}\mu(\mathcal{F}^{xy}_{\leq
n})(2|\mathcal{A}|-1)^{-2|w|}.$

Using Lemma 1 we may guarantee that for $n$ large enough
$\mu(\mathcal{F}^{xy}_{\leq n})\leq\frac{1}{4|\mathcal{A}|^{2}}+\varepsilon$.
Then, plugging the two previous estimates into (4) we obtain

$\bar{d}(S)\leq\left(\left(\frac{1}{4|\mathcal{A}|^{2}}+\varepsilon\right)\left(\frac{1}{k}+\varepsilon\right)\sum_{\mathcal{I}}(2|\mathcal{A}|-1)^{-2|w|}\right)+\varepsilon.$
(5)

By the way we constructed $S^{w,x,y}$, the sum
$\sum_{\mathcal{I}}(2|\mathcal{A}|-1)^{-2|w|}$ must be equal to
$4|\mathcal{A}|^{2}$, but we may as well prove it. The only restriction on $w$
is that its last letter, if it has any, does not coincide with $x^{-1}$ or
$y$, which are necessarily distinct. Hence, separating the case where $w$ is
empty, we have

$\sum_{\mathcal{I}}(2|\mathcal{A}|-1)^{-2|w|}=2|\mathcal{A}|(2|\mathcal{A}|-1)\left(1+\sum_{l\geq
1}(2|\mathcal{A}|-2)(2|\mathcal{A}|-1)^{-l-1}\right)=4|\mathcal{A}|^{2}.$

Since (5) is true for any $\varepsilon>0$, we conclude by taking
$\varepsilon\to 0$. ∎

##  3 Proof over a semigroup

Throughout this section we assume fixed
$x,y\in\mathcal{A}\cup\mathcal{A}^{-1}$ such that $x\neq y^{-1}$ and write
$\mathcal{G}=\mathcal{F}^{xy}\subseteq\mathcal{F}$ for the subsemigroup of
words beginning in $x$ and ending in $y$. We also write
$K=\frac{2|\mathcal{A}|}{2|\mathcal{A}|-1}$ for a constant that appears in
several arguments, due to the fact that
$|\mathcal{F}(i)||\mathcal{F}(j)|=\frac{|\mathcal{F}(i+j)|}{K}$.

We first prove a version of Proposition 1 that depends on the construction of
certain subsets of $S$ with appropriate properties. We say
$\mathcal{H}\subseteq\mathcal{F}$ is _dense_ if $\mu(\mathcal{H}_{\leq
n})>\delta\mu(\mathcal{F}_{\leq n})>0$ for a fixed $\delta$ and all large
enough $n$. Furthermore, it is a _subsemigroup_ if
$\mathcal{H}\cdot\mathcal{H}\subseteq\mathcal{H}$, i.e.
$\alpha\beta\in\mathcal{H}$ for all $\alpha,\beta\in\mathcal{H}$. Finally, a
subset $W\subseteq\mathcal{H}$ has _unique products_ in $\mathcal{H}$ if the
map

$\displaystyle(W,\mathcal{H})$ $\displaystyle\to\mathcal{H}$
$\displaystyle(w,h)$ $\displaystyle\mapsto w\cdot h$

is injective.

For $W$ and $\mathcal{H}\subseteq\mathcal{G}$ satisfying the above properties,
we prove a version of Proposition 1 conditional on $\mu(W)$ being close to
$K$.

######  Lemma 2.

Let $\mathcal{H}\subseteq\mathcal{G}$ be a dense subsemigroup. For any
strongly $k$-product free set $S\subseteq\mathcal{H}$ and finite subset
$W\subseteq S$ with unique products it holds that

$\bar{d}_{\mathcal{H}}(S)\leq\frac{1}{1+\frac{\mu(W)}{K}+\dots+\left(\frac{\mu(W)}{K}\right)^{k-1}}$

###### Proof.

For a given $n$, consider a random word $\alpha\in\mathcal{F}_{\leq n}$ chosen
in the following manner. We first choose its length $l\in[n]$ with uniform
probability, and then choose a random word belonging to $\mathcal{F}(l)$
uniformly, so that $\Pr(\alpha=w)=\mu(\\{w\\})/n$. By additivity, it holds
that

$\frac{\Pr(\alpha\in S)}{\Pr(\alpha\in\mathcal{H})}=\frac{\mu(S_{\leq
n})}{\mu(\mathcal{H}_{\leq n})}$ (6)

Since $S$ is strongly $k$-product-free, if $\alpha$ belongs to $W^{i}\cdot S$
for $1\leq i\leq k-1$ then $\alpha$ cannot belong to $S$. Since $W$ has unique
products, the set $W^{i}\cdot S$ intersects $W^{j}\cdot S$ with $i>j$ only
when $W^{i-j}\cdot S$ intersects $S$. Hence, the sets $W^{i}\cdot S$ for
$0\leq i\leq k-1$ are disjoint and

$\sum_{i=0}^{k-1}\Pr(\alpha\in W^{i}\cdot S)\leq\Pr(\alpha\in\mathcal{H}).$
(7)

Let us estimate the probability that $\alpha\in W\cdot A$ for an arbitrary
subset $A\subseteq\mathcal{H}$. Note that $\alpha$ factors in a unique way
because $W$ has unique products. In particular, $W(i)\cdot S$ and $W(j)\cdot
S$ are disjoint for $i\neq j$. Hence, writing $l_{0}$ for the maximum length
of a word in $W$, we have that

$\Pr(\alpha\in W\cdot A)=\sum_{i=1}^{l_{0}}\Pr(\alpha\in W(i)\cdot A).$

Conditioning on the length of $\alpha$, we obtain

$\begin{split}\Pr(\alpha\in W\cdot
A)&=\sum_{i=1}^{l_{0}}\sum_{l=i+1}^{n}Pr(|\alpha|=l)\Pr(\alpha\in W(i)\cdot
A\mid|\alpha|=l)\\\
&=\sum_{i=1}^{l_{0}}\sum_{l=i+1}^{n}\frac{1}{n}\Pr(\alpha\in W(i)\cdot
A(l-i)\mid|\alpha|=l)\\\
&=\sum_{i=1}^{l_{0}}\sum_{l=i+1}^{n}\frac{1}{n}\mu(W(i))\mu(A(l-i))\frac{|\mathcal{F}(i)||\mathcal{F}(l-i)|}{|\mathcal{F}(l)|}\\\
&=\frac{1}{K}\sum_{i=1}^{l_{0}}\mu(W(i))\left(\frac{1}{n}\sum_{t=1}^{n-i}\mu(A(t))\right)\\\
&=\frac{\mu(W)}{K}\frac{\mu(A_{\leq n})+O(1)}{n}\\\
&=\frac{\mu(W)\Pr(\alpha\in A)}{K}+o(1).\end{split}$ (8)

By induction, we have that $\Pr(W^{i}\cdot S)=(\mu(W)/K)^{i}\Pr(\alpha\in
S)+o(1)$. Plugging this estimate into (7) and noting that $\mathcal{H}$ is
dense gives

$\frac{Pr(\alpha\in
S)}{Pr(\alpha\in\mathcal{H})}\left(1+\frac{\mu(W)}{K}+\cdots+\left(\frac{\mu(W)}{K}\right)^{k-1}\right)+o(1)\leq
1$

Using (6) and taking the upper limit we reach the desired conclusion. ∎

It is now our task to build a subset $W$ large enough in order to apply the
previous lemma. We first present a proof for the case $2\leq k\leq 3$, where
we can use a similar argument to the one in [6]. In this case, we may exploit
the fact that $S$ is product-free to construct $W$ in a straightforward
manner. The reader interested only in the general case may choose to ignore
this proof.

###### Proof of Proposition 1 for $2\leq k\leq 3$.

Suppose there exists $S$ satisfying
$\bar{d}_{\mathcal{G}}(S)>\frac{1}{k}+\varepsilon$ for $\varepsilon>0$. We
will build a nested sequence of divisor-free subsets
$W_{i}\subset\mathcal{G}$, meaning there are no $u,v\in W_{i}$ and
$t\in\mathcal{G}$ such that $ut=v$. This condition implies that $W_{i}$ has
unique products in $\mathcal{G}$.

Choose $\alpha\in\mathcal{F}_{\leq n}$ randomly as in the proof of Lemma 2.
Since $S$ is strongly $k$-product-free and $W$ has unique products, we have
that

$\sum_{j=0}^{k-1}\Pr(\alpha\in W_{i}^{j}\cdot S)\leq\Pr(\alpha\in
W_{i}\cdot\mathcal{G})+\Pr(\alpha\in S,\alpha\not\in W_{i}\cdot\mathcal{G}).$

Applying the estimate (8) and reordering terms, we obtain that

$\Pr(\alpha\in S,\alpha\not\in W_{i}\cdot\mathcal{G})\geq\Pr(\alpha\in
S)\left(\sum_{j=0}^{k-1}\left(\frac{\mu(W_{i})}{K}\right)^{j}\right)-\Pr(\alpha\in\mathcal{G})\frac{\mu(W_{i})}{K}+o(1)$

Since we assumed that $S$ has relative upper density greater than
$1/k+\varepsilon$, we may find $l\in\mathbb{N}$ such that

$\mu(S(l)\setminus
W_{i}\cdot\mathcal{G})\geq\Pr(\alpha\in\mathcal{G})\left(\frac{1}{k}\left(\sum_{j=0}^{k-1}\left(\frac{\mu(W_{i})}{K}\right)^{j}\right)-\frac{\mu(W_{i})}{K}\right).$

Setting $W_{i+1}=W_{i}\cup(S(l)\setminus W_{i}\cdot\mathcal{G})$, we obtain a
sequence of subsets satisfying

$\mu(W_{i+1})-\mu(W_{i})\geq\frac{1}{k}\left(\sum_{j=0}^{k-1}\left(\frac{\mu(W_{i})}{K}\right)^{j}\right)-\frac{\mu(W_{i})}{K}$

with $K$ as in the proof of Proposition 1 . Repeating this process, we can
increase the size of $W_{i}$ until we reach the first zero of the polynomial

$\frac{1}{k}\left(\sum_{j=0}^{k-1}\left(\frac{x}{K}\right)^{j}\right)-\frac{x}{K}.$
(9)

If $2\leq k\leq 3$, this polynomial has $K$ as its first positive zero and it
is positive at zero. Hence, we obtain $\frac{\mu(W_{i})}{K}\to 1$. Applying
Lemma 2 with every $W_{i}$ and letting $i\to\infty$ we obtain
$\bar{d}_{\mathcal{G}}(S)\leq 1/k$, a contradiction with our original
assumption. ∎

The previous proof fails for $k>3$ because the polynomial in (9) has a zero in
the interval $(0,K)$. Thus, we must find another way of building the subset
$W\subseteq S$ necessary to apply Lemma 2. To do so, instead of finding such a
set directly in $\mathcal{G}$, we will find a subset of $\mathcal{G}$ where
$S$ is regularly distributed, where the existence of $W\subseteq S$ as we are
interested in is much easier to prove and does not depend on $S$ being
product-free.

Concretely, we are interested in studying $S$ when we restrict ourselves to
words which are divisible in $\mathcal{G}$ by a given factor. For a given
$w\in\mathcal{G}$, we write $w\mathcal{G}\subseteq\mathcal{G}$ for the set of
words belonging to $\mathcal{G}$ which may be written as $w\alpha$ for
$\alpha\in\mathcal{G}$. We then define the following pseudorandomness
condition, which measures whether $S$ is evenly distributed when restricted to
such sets.

######  Definition 1.

Given $w\in\mathcal{G}$, a subset $S\subset w\mathcal{G}$ is
$\varepsilon$-regular in $w\mathcal{G}$ if

$\bar{d}_{ww^{\prime}\mathcal{G}}((S\cap(ww^{\prime}\mathcal{G}))<\bar{d}_{w\mathcal{G}}(S)+\varepsilon$
(10)

for all words $w^{\prime}\in\mathcal{G}$.

We now prove the analogous statement to Theorem 2 under pseudorandomness
assumptions. In particular, the following Lemma will imply Theorem 2 when $S$
is $\varepsilon$-regular for all $\varepsilon>0$.

######  Lemma 3.

Let $S\subset w\mathcal{G}$ be a strongly $k$-product free set that is
$\varepsilon$-regular in $w\mathcal{G}$, with $w\in\mathcal{G}$, and let
$d=\bar{d}_{w\mathcal{G}}(S)$ be its relative upper density. Then

$d\left(1+\frac{d}{d+2\varepsilon}+\cdots+\left(\frac{d}{d+2\varepsilon}\right)^{k}\right)\leq
1,$ (11)

###### Proof.

Our goal is to build a subset $W\subset w\mathcal{G}$ with unique products and
$\mu(W)$ as large as possible so that we may apply Lemma 2 with
$\mathcal{H}=w\mathcal{G}$. We will construct a nested sequence of subsets
$W_{i}\subset w\mathcal{G}$ with the following properties:

  1. i)

Elements of $W_{i}$ have either the same length or lengths that differ by at
least $|w|$. That is, given $w_{1},w_{2}\in W_{i}$, either $|w_{1}|=|w_{2}|$
or $||w_{1}|-|w_{2}||>|w|$.

  2. ii)

The sets $W_{i}$ are divisor-free in $w\mathcal{G}$. By this we mean that
there are no $u,v\in W_{i}$ and $t\in w\mathcal{G}$ such that $ut=v$.

From these two properties, we may deduce that the sets $W_{i}$ have unique
products in $w\mathcal{G}$. Indeed, if $ux=u^{\prime}x^{\prime}$ for some
$u,u^{\prime}\in W_{i}$ and $x,x^{\prime}\in w\mathcal{G}$, then
$|u|=|u^{\prime}|$ implies $u=u^{\prime}$ and $x=x^{\prime}$, and if
$|u|<|u^{\prime}|-|w|$ the same conclusion following from $W_{i}$ being
divisor-free. Set $W_{1}=S(l)$ for some $l$ such that $S(l)\neq\varnothing$.
Given $W_{i}$, we will now build $W_{i+1}$. Choose $\alpha$ randomly as in the
proof of Lemma 2. We have that

$\Pr(\alpha\in S,\,\alpha\not\in W_{i}\cdot w\mathcal{G})\geq\Pr(\alpha\in
S)-\Pr(\alpha\in S,\alpha\in W_{i}\cdot w\mathcal{G}).$ (12)

Let us upper bound the rightmost term. Since $W_{i}$ has unique products,

$\displaystyle\Pr(\alpha\in S,\alpha\in W_{i}\cdot w\mathcal{G})$
$\displaystyle=\sum_{wu\in W_{i}}\Pr(\alpha\in S,\alpha\in wuw\mathcal{G})$
$\displaystyle=\sum_{wu\in W_{i}}\frac{\mu((wuw\mathcal{G})_{\leq
n})}{\mu(\mathcal{F}_{\leq n})}\frac{\mu((S\cap(wuw\mathcal{G}))_{\leq
n})}{\mu((wuw\mathcal{G})_{\leq n})}.$

Consider a fixed $\varepsilon>0$. By the $\varepsilon$-regularity of $S$,
using (10) we may guarantee for all large enough $n$ that
$\frac{\mu((S\cap(wuw\mathcal{G}))_{\leq n})}{\mu((wuw\mathcal{G})_{\leq
n})}<d+\varepsilon$, from which we conclude that

$\Pr(\alpha\in S,\alpha\in W_{i}\cdot w\mathcal{G})<\Pr(\alpha\in W_{i}\cdot
w\mathcal{G})(d+\varepsilon).$

Using the estimate (8) we obtain

$\Pr(\alpha\in S,\alpha\in W_{i}\cdot
w\mathcal{G})<\frac{\mu(W_{i})\Pr(\alpha\in
w\mathcal{G})}{K}(d+\varepsilon)+o(1)$

Plugging this into (12), for any $\xi>0$ we may obtain arbitrarily large $n$
such that

$\displaystyle\frac{\Pr(\alpha\in S,\,\alpha\not\in W_{i}\cdot
w\mathcal{G})}{\Pr(\alpha\in w\mathcal{G})}$ $\displaystyle\geq
d-\xi-\frac{\mu(W_{i})}{K}(d+\varepsilon).$

Setting $\xi=\varepsilon\mu(W_{i})/K$ we may obtain $l_{k+1}\in\mathbb{N}$ as
large as necessary such that

$\mu(S(l_{k+1})\setminus W_{i}\cdot w\mathcal{G})\geq\Pr(\alpha\in
w\mathcal{G})\left(d-\frac{\mu(W_{i})}{K}(d+2\varepsilon)\right)$

Taking $l_{k+1}$ larger than the maximum length of an element in $W_{i}$ plus
$|w|$ and setting $W_{i+1}=W_{i}\cup(S(l)\setminus W_{i}\cdot w\mathcal{G})$
we obtain a sequence $W_{i}$ with the desired properties that satisfies

$\mu(W_{i+1})\geq\mu(W_{i})+\Pr(\alpha\in
w\mathcal{G})\left(d-\frac{\mu(W_{i})}{K}(d+2\varepsilon)\right).$

Then $\mu(W_{i})$ is an increasing sequence whose limit is the fixed point of
the previous recurrence, namely

$\frac{\mu(W_{i})}{K}\to\frac{d}{d+2\varepsilon}$

Applying Lemma 2 with every $W_{i}$ and letting $i\to\infty$ gives the desired
conclusion. ∎

Finally, we use a density-increment strategy, where failure of
pseudorandomness implies an increase in density, to prove our main result.

###### Proof of Proposition 1.

Consider a fixed $\varepsilon>0$. If $S$ is not $\varepsilon$-regular in
$\mathcal{G}$, we may then find $w_{1}\in\mathcal{G}$ such that

$\bar{d}_{w_{1}\mathcal{G}}(S\cap w_{1}\mathcal{G})>\bar{d}(S)+\varepsilon.$

More generally, if $S\cap w_{k}\mathcal{G}$ is not $\varepsilon$-regular in
$w_{k}\mathcal{G}$, we may find $w_{k+1}\in w_{k}\mathcal{G}$ such that

$\bar{d}_{w_{k+1}\mathcal{G}}(S\cap
w_{k+1}\mathcal{G})>\bar{d}_{w_{k}\mathcal{G}}(S\cap
w_{k}\mathcal{G})+\varepsilon>\bar{d}_{\mathcal{G}}(S)+k\varepsilon.$

Since upper relative density is bounded above by $1$, this procedure must
terminate in less than $\varepsilon^{-1}$ steps, which means there exists $w$
such that $S\cap w\mathcal{G}$ is $\varepsilon$-regular in $w\mathcal{G}$ and
$\bar{d}_{w\mathcal{G}}(S\cap w\mathcal{G})\geq\bar{d}(S)$.

Applying Lemma 3 with $S\cap w\mathcal{G}$ and using that the left hand side
in (11) is increasing in $d$ we obtain that

$\bar{d}(S)\left(1+\frac{\bar{d}(S)}{\bar{d}(S)+2\varepsilon}+\cdots+\left(\frac{\bar{d}(S)}{\bar{d}(S)+2\varepsilon}\right)^{k}\right)\leq
1.$

Taking $\varepsilon\to 0$ finishes the proof. ∎

##  4 Final remarks

We devoted the previous section to proving Proposition 1, which is stated for
the semigroup $\mathcal{F}^{xy}$ for $x,y\in\mathcal{A}\cup\mathcal{A}^{-1}$
and $x\neq y^{-1}$. In fact, the proof of Theorem 3 is done following the
arguments from the previous section, by only replacing the role played by
$\mathcal{F}^{xy}$ for $\bm{F}_{\mathcal{A}}$, and by replacing $K$ by 1. It
is also worth noting that the results in [6] concern the upper Banach density
of sum-free subsets, which gives slightly stronger results, since the upper
Banach density is an upper bound for the upper density we consider. For the
sake of simplicity, we have not attempted to write down our results for this
case, although all arguments should hold.

Finally, it would also be interesting to consider the case of $k$-product-free
sets. To state the natural conjecture for this case, define $\rho$ as

$\rho(l)=\min\left(\left\\{l\in\mathbb{N}\colon l\nmid k-1\right\\}\right).$

Then we believe the following to be true.

######  Conjecture 1.

Let $S\subseteq\mathcal{F}$ be a $k$-product-free subset for $k\geq 2$. Then

$\bar{d}(S)\leq\frac{1}{\rho(k)}$ (13)

This is analogous to a result of Łuczak and Schoen [4], which proves the
corresponding statement over the integers. One might attempt to prove it using
ideas by the same authors in [5]. For example, for $k=3$, one would partition
$S$ into $S_{1}$ and $S_{2}$, with $w\in S_{2}$ if $w=uv$ for $u,v\in S$ and
$w\in S_{1}$ otherwise. Then one could use the following disjunctive for an
extremal $S$:

  * •

If $\bar{d}(S_{2})>0$, we would expect to find a large enough subset
$W\subseteq S_{2}$ with unique products. One could then directly use $W$ as
done in Lemma 2 because $(S_{2}\cdot S)\cap S=\varnothing$.

  * •

If $\bar{d}(S_{2})=0$, then $\bar{d}(S_{1})=\bar{d}(S)$ and $S_{1}$ is
strongly $3$-product-free.

This approach fails because of the claim in the first point. It is not clear
how to find such a $W$. If we try to use the same approach as we did in this
paper, the control implied by our definition of pseudorandomness only allows
for upper bounds and not lower bounds on the density of $S$, and this
complicates controlling the pseudorandomness of $S$ and $S_{2}$ at the same
time, which is what we would need to find a suitable $W$. For stronger notions
of pseudorandomness, the density increment strategy seems to break.

##  5 Acknowledgments

We acknowledge the support of the grants MTM2017-82166-P,
PID2020-113082GB-I00, and the Severo Ochoa and María de Maeztu Program for
Centers and Units of Excellence in R&D (CEX2020-001084-M). Miquel Ortega also
acknowlegdes the support of the FPI grant PRE2021-099120.

## References

  * [1] László Babai and Vera T. Sós, _Sidon sets in groups and induced subgraphs of Cayley graphs_ , European J. Combin. 6 (1985), no. 2, 101–114. MR 810691
  * [2] W. T. Gowers, _Quasirandom groups_ , Combin. Probab. Comput. 17 (2008), no. 3, 363–387. MR 2410393
  * [3] Kiran S. Kedlaya, _Product-free subsets of groups, then and now_ , 479 (2009), 169–177. MR 2513445
  * [4] Tomasz Ł uczak and Tomasz Schoen, _On infinite sum-free sets of natural numbers_ , J. Number Theory 66 (1997), no. 2, 211–224. MR 1473879
  * [5] , _Sum-free subsets of right cancellative semigroups_ , European J. Combin. 22 (2001), no. 7, 999–1002. MR 1857261
  * [6] Imre Leader, Shoham Letzter, Bhargav Narayanan, and Mark Walters, _Product-free sets in the free semigroup_ , European Journal of Combinatorics 83 (2020), 103003.
  * [7] Terence Tao and Van Vu, _Sum-free sets in groups: a survey_ , J. Comb. 8 (2017), no. 3, 541–552. MR 3668880


algebra $H(\mathord{\text{NB}})$ is the complement set of
$H(\mathord{\vphantom{\bot}\mathchoice{\ooalign{$\displaystyle\bot$\cr\kern
1.99997pt$\displaystyle\bot$}}{\ooalign{$\textstyle\bot$\cr\kern
1.99997pt$\textstyle\bot$}}{\ooalign{$\scriptstyle\bot$\cr\kern
1.99997pt$\scriptstyle\bot$}}{\ooalign{$\scriptscriptstyle\bot$\cr\kern
1.99997pt$\scriptscriptstyle\bot$}}})$, a similar argument proves the
statement.

  * •

Assume $\varphi=P_{i}$. For all $b\in B$ we have that $b\in
H({\mathcal{P}}_{i})$ if and only if $b\leq b_{i}$. Then by $e$ being an
embedding this holds if and only if $e(b)\leq e(b_{i})$, which is equivalent
to $e(b)\in H^{\prime}(P_{i})$.

  * •

Assume $\varphi=\mathord{{\sim}}P_{i}$. By Lemma 6.4
$H(\mathord{{\sim}}P_{i})$ is the principal ideal generated by $\lnot b_{i}$.
Similarly, $H^{\prime}(\mathord{{\sim}}P_{i})$ is the principal ideal
generated by $\lnot e(b_{i})$. Thus, a similar argument as for $\varphi=P_{i}$
suffices.

  * •

Assume $\varphi=\psi\land\chi$. Then $b\in H(\varphi)$ if and only if $b\in
H(\psi)$ and $b\in H(\chi)$. By induction we can conclude that this holds if
and only if $e(b)\in H^{\prime}(\psi)$ and $e(b)\in H^{\prime}(\chi)$ which
holds if and only if $e(b)\in H^{\prime}(\varphi)$.

  * •

Assume $\varphi=\psi\lor\chi$. The result follows in a similarly standard way
as the previous case.

  * •

Assume
$\varphi=\psi\mathrel{\vphantom{\lor}\mathchoice{\ooalign{\raisebox{0.6458pt}{\rotatebox[origin={c}]{-90.0}{$\displaystyle\geqslant$}}}}{\ooalign{\raisebox{0.6458pt}{\rotatebox[origin={c}]{-90.0}{$\textstyle\geqslant$}}}}{\ooalign{\raisebox{0.6458pt}{\rotatebox[origin={c}]{-90.0}{$\scriptstyle\geqslant$}}}}{\ooalign{\raisebox{0.6458pt}{\rotatebox[origin={c}]{-90.0}{$\scriptscriptstyle\geqslant$}}}}}\chi$.
If $b\in H(\varphi)$, then there exists $c\lor d=b$ such that $c\in H(\psi)$
and $d\in H(\chi)$. By induction hypothesis we directly see that
$e(b)=e(c)\lor e(d)\in H^{\prime}(\varphi)$. For the other direction, assume
$e(b)\in H^{\prime}(\varphi)$. Then there exists $c^{\prime}\lor
d^{\prime}=e(b)$ such that $c^{\prime}\in H^{\prime}(\psi)$ and $d^{\prime}\in
H^{\prime}(\chi)$. Now by the interval lemma above we can find
$b_{\psi},b_{\chi}\in B$ such that $[c^{\prime},e(b_{\psi})]\subseteq
H^{\prime}(\psi)$ and $[d^{\prime},e(b_{\chi})]\subseteq H^{\prime}(\chi)$.
Now, let $c=b\land b_{\psi}$ then

$e(c)=e(b)\land e(b_{\psi})=(c^{\prime}\lor d^{\prime})\land
e(b_{\psi})=c^{\prime}\lor(d^{\prime}\land e(b_{\psi}))$

so that clearly $e(c)\in[c^{\prime},e(b_{\psi})]\subseteq H^{\prime}(\psi)$,
and by induction hypothesis $c\in H(\psi)$. Similarly define $d=b\land
b_{\chi}$ and conclude that $d\in H(\chi)$. What is left to show is that
$b=c\lor d$. We see that

$c\lor d=(b\land b_{\psi})\lor(b\land b_{\chi})=(b\lor(b\land
b_{\chi}))\land(b_{\psi}\lor(b\land b_{\chi}))=\\\ b\land((b_{\psi}\lor
b)\land(b_{\psi}\lor b_{\chi}))=b,$

where the last equality comes from the observation that $e(b)=c^{\prime}\lor
d^{\prime}\leq e(b_{\psi})\lor e(b_{\chi})=e(b_{\psi}\lor b_{\chi})$, and by
$e$ being injective letting us conclude that $b\leq b_{\psi}\lor b_{\chi}$.

This concludes the proof of Lemma 6.8. ∎

###### Lemma 6.11

For every Boolean algebra of the form
$({\mathcal{P}}S,\emptyset,\cdot^{C},\cup,\cap)$ and every homomorphism
$H:\mathtt{Fm}_{\text{LT}}\to{\mathcal{P}}{\mathcal{P}}S$ with principal
variables there is a mapping $f_{H}:S\to 2^{\mathbb{N}}$ such that for all
formulas $\varphi\in\mathtt{Fm}_{\text{PT}^{+}}$ and all $X\in{\mathcal{P}}S$:

$X\in H(\varphi)\quad\text{iff}\quad f_{H}^{*}(X)\in H_{V}(\varphi),$

where $f_{H}^{*}:{\mathcal{P}}S\to{\mathcal{P}}2^{\mathbb{N}}$ is defined by
$f_{H}^{*}(X)=\set{f_{H}(x)}{x\in X}$, and
$H_{V}:\mathtt{Fm}_{\text{LT}}\to{\mathcal{P}}{\mathcal{P}}2^{\mathbb{N}}$
denotes the valuation homomorphism.

###### Proof.

Assume $H:\mathtt{Fm}_{\text{LT}}\to{\mathcal{P}}{\mathcal{P}}S$ has principal
variables. Let $f:S\to 2^{\mathbb{N}}$ be defined by

$f(s)(i)=\begin{cases}1&\text{ if }\\{s\\}\in H(P_{i})\\\ 0&\text{ if
}\\{s\\}\notin H(P_{i}).\end{cases}$

> Claim: For all $X,Y\in{\mathcal{P}}S$, $f^{*}(X\cup Y)=f^{*}(X)\cup
> f^{*}(Y)$. Furthermore, if $f^{*}(X)=U\cup V$, then there exist
> $Y,Z\in{\mathcal{P}}S$ such that $f^{*}(Y)=U$, $f^{*}(Z)=V$ and $Y\cup Z=X$.

The first part of the claim is self-evident by the definition of $f^{*}$ from
$f$. For the second part, let $Y=\set{s\in X}{f(s)\in U}$ and $Z=\set{s\in
X}{f(s)\in V}$.

We can now prove that the function $f$ is what we looked for in the lemma by
induction over formulas $\varphi\in\mathtt{Fm}_{\text{PT}^{+}}$.

We have four types of base cases:
$\mathord{\vphantom{\bot}\mathchoice{\ooalign{$\displaystyle\bot$\cr\kern
1.99997pt$\displaystyle\bot$}}{\ooalign{$\textstyle\bot$\cr\kern
1.99997pt$\textstyle\bot$}}{\ooalign{$\scriptstyle\bot$\cr\kern
1.99997pt$\scriptstyle\bot$}}{\ooalign{$\scriptscriptstyle\bot$\cr\kern
1.99997pt$\scriptscriptstyle\bot$}}},\mathord{\text{NB}},P_{i},\mathord{{\sim}}P_{i}$:

  * •

Assume
$\varphi=\mathord{\vphantom{\bot}\mathchoice{\ooalign{$\displaystyle\bot$\cr\kern
1.99997pt$\displaystyle\bot$}}{\ooalign{$\textstyle\bot$\cr\kern
1.99997pt$\textstyle\bot$}}{\ooalign{$\scriptstyle\bot$\cr\kern
1.99997pt$\scriptstyle\bot$}}{\ooalign{$\scriptscriptstyle\bot$\cr\kern
1.99997pt$\scriptscriptstyle\bot$}}}$. By definition $X\in
H(\mathord{\vphantom{\bot}\mathchoice{\ooalign{$\displaystyle\bot$\cr\kern
1.99997pt$\displaystyle\bot$}}{\ooalign{$\textstyle\bot$\cr\kern
1.99997pt$\textstyle\bot$}}{\ooalign{$\scriptstyle\bot$\cr\kern
1.99997pt$\scriptstyle\bot$}}{\ooalign{$\scriptscriptstyle\bot$\cr\kern
1.99997pt$\scriptscriptstyle\bot$}}})$ iff $X=\emptyset$, and since
$f^{*}(X)=\emptyset$ if and only if $X=\emptyset$ this case is evident.

  * •

Assume $\varphi=\mathord{\text{NB}}$. This case is proved by contraposition of
the previous case.

  * •

Assume $\varphi=P_{i}$. By assumption $H(P_{i})$ is a principal ideal in the
Boolean algebra ${\mathcal{P}}S$. Hence, for all $X\in H(P_{i})$, by downwards
closure we have for all $s\in X$ that $\\{s\\}\in H(P_{i})$. By construction
then $f^{*}(\\{s\\})\in H_{V}(P_{i})$ for all $s\in X$, and thus since $H_{V}$
has principal variables we find that $f^{*}(X)\in H_{V}(P_{i})$. The opposite
direction is proved with a similar chain of arguments.

  * •

Assume $\varphi=\mathord{{\sim}}P_{i}$. Then by Lemma 6.4 we assert that for
all $H\in\mathcal{H}_{PV}$ we have that $H(\mathord{{\sim}}P_{i})$ is a
principal ideal. The proof is then similar to the previous case.

For the induction step we have three cases for the main connectives:
$\land,\lor,\mathrel{\vphantom{\lor}\mathchoice{\ooalign{\raisebox{0.6458pt}{\rotatebox[origin={c}]{-90.0}{$\displaystyle\geqslant$}}}}{\ooalign{\raisebox{0.6458pt}{\rotatebox[origin={c}]{-90.0}{$\textstyle\geqslant$}}}}{\ooalign{\raisebox{0.6458pt}{\rotatebox[origin={c}]{-90.0}{$\scriptstyle\geqslant$}}}}{\ooalign{\raisebox{0.6458pt}{\rotatebox[origin={c}]{-90.0}{$\scriptscriptstyle\geqslant$}}}}}$

  * •

Assume $\varphi=\psi\land\chi$. $X\in H(\varphi)$ by definition if and only if
$X\in H(\psi)$ and $X\in H(\chi)$. By induction hypothesis, we can conclude
that is the case if and only if $f^{*}(X)\in H_{V}(\psi)$ and $f^{*}(X)\in
H_{V}(\chi)$, which is equivalent to stating that $f^{*}(X)\in
H_{V}(\varphi)$.

  * •

Assume $\varphi=\psi\lor\chi$. The proof is similarly standard as the previous
case.

  * •

Assume
$\varphi=\psi\mathrel{\vphantom{\lor}\mathchoice{\ooalign{\raisebox{0.6458pt}{\rotatebox[origin={c}]{-90.0}{$\displaystyle\geqslant$}}}}{\ooalign{\raisebox{0.6458pt}{\rotatebox[origin={c}]{-90.0}{$\textstyle\geqslant$}}}}{\ooalign{\raisebox{0.6458pt}{\rotatebox[origin={c}]{-90.0}{$\scriptstyle\geqslant$}}}}{\ooalign{\raisebox{0.6458pt}{\rotatebox[origin={c}]{-90.0}{$\scriptscriptstyle\geqslant$}}}}}\chi$.
For one direction, assume $X\in H(\varphi)$. Then there exist $Y\in H(\psi)$
and $Z\in H(\chi)$ such that $X=Y\cup Z$. By induction hypothesis $f^{*}(Y)\in
H_{V}(\psi)$ and $f^{*}(Z)\in H_{V}(\chi)$. By the first part of the Claim
about $f^{*}$ we see that $f^{*}(X)=f^{*}(Y)\cup f^{*}(Z)$ and thus
$f^{*}(X)\in H_{V}(\varphi)$.

For the other direction, assume $f^{*}(X)\in H_{V}(\varphi)$. Then there exist
$U\in H_{V}(\psi),V\in H_{V}(\chi)$ such that $f^{*}(X)=U\cup V$. Then by the
second part of the Claim about $f^{*}$, there exists $Z,Y$ such that
$f^{*}(Z)=U,f^{*}(Y)=V$ and $Z\cup Y=X$. By the induction hypothesis $Z\in
H(\psi)$ and $Y\in H(\chi)$. We conclude that $X\in H(\varphi)$.

This concludes the proof of the lemma. ∎

We are now ready to prove Theorem 6.6.

###### Proof of Theorem 6.6.

The theorem is equivalent to the statement that for all
$\Delta\cup\\{\varphi\\}\subseteq\mathtt{Fm}_{\text{PT}^{+}}$

$\text{PT}^{+}:\Delta\vDash\varphi\quad\text{iff}\quad\mathcal{H}_{\text{PV}}:\Delta\vDash\varphi.$

One direction follows directly from Theorem 6.2 and the fact that
$H_{V}\in\mathcal{H}_{\text{PV}}$.

The other direction is proved by contraposition. Assume
$\mathcal{H}_{\text{PV}}:\Delta\nvDash\varphi$ and thus
$\text{LT}:\text{PVA},\Delta\nvDash\varphi$. Then there is some Boolean
algebra $B$ and homomorphism $H:\mathtt{Fm}_{\text{LT}}\to{\mathcal{P}}B$ such
that $H:\text{PVA},\Delta\nvDash\varphi.$ In other words,
$H\in\mathcal{H}_{\text{PV}}$ and there exists an element $b\in B$ such that

$b\in\bigcap_{\delta\in\Delta}H(\delta),\text{ but }b\notin H(\varphi).$

By Theorem 6.7, we can then find an embedding
$e:B\hookrightarrow{\mathcal{P}}{S}$ of $B$ into a complete atomic Boolean
algebra of the form $({\mathcal{P}}S,\emptyset,\cdot^{C},\cup,\cap)$. Then by
lemma 6.8 and 6.11 we can find a homomorphism
$H^{\prime}:\mathtt{Fm}_{\text{LT}}\to{\mathcal{P}}{\mathcal{P}}S$, and a
mapping $f_{H^{\prime}}:S\to 2^{\mathbb{N}}$ such that

$f_{H^{\prime}}^{*}(e(b))\in\bigcap_{\delta\in\Delta}H_{V}(\delta),\text{ but
}f_{H^{\prime}}^{*}(e(b))\notin H_{V}(\varphi).$

Thus, $H_{V}:\Delta\nvDash\varphi$ and by Theorem 6.2:

$\text{PT}^{+}:\Delta\nvDash\varphi.$

This finalises the proof of Theorem 6.6. ∎

Observe that to evaluate $\text{PT}^{+}$ it is sufficient to consider the
valuational algebra ${\mathcal{P}}2^{\mathbb{N}}$ i.e. for all
$\Delta,\\{\varphi\\}\subseteq\mathtt{Fm}_{\text{PT}^{+}}$ we have

$\text{PT}^{+}:\Delta\vDash\varphi\quad\text{iff}\quad{\mathcal{P}}2^{\mathbb{N}}:\text{PVA},\Delta\vDash\varphi.$

In this sense ${\mathcal{P}}2^{\mathbb{N}}$ can be seen as canonical for
$\text{PT}^{+}$. It is however not canonical for the logic in LT axiomatized
by PVA, since the canonicity only holds when the formulas are restricted to
the language $\mathtt{Fm}_{\text{PT}^{+}}$.

##  7 Conclusion

In this paper, we have introduced a new substitutional logic of teams, LT,
with a natural semantics inspired by algebraic semantics together with a sound
and complete labelled natural deduction system. We have also given an
axiomatisation of different propositional team logics, such as propositional
dependence logic, in LT. From the initial choice of a more algebraic
perspective, we see that the constructions of the semantics, the natural
deduction system and the relative axiomatisation presented, seem fairly
straight-forward and sensible without significant arbitrary choices. This
indicates that an analysis of the structure of these constructions should be
informative for an over-arching view of team logics from an algebraic
perspective. By focusing on different parts of this construction we highlight
some research topics that are exposed by the work in this paper.

The logic LT is fully substitutional, so the full toolbox of algebraisation is
open to us. In the language of abstract algebraic logic [Font16], LT is a
semilattice-based logic; and by applying some general theory we can see that
LT is, in fact, not algebraisable in the strict meaning. However, its
assertional companion, $\text{LT}^{\top}$, defined by the designated element
$\top$, is an implicative logic and thus algebraisable. We suggest that both
these two logics should be analysed from the view of abstract algebraic logic
in future work.

To relate LT to other propositional team logics we have identified a set of
principle variable axioms (PVA). This set of axioms can be viewed as a
somewhat natural set of axioms that captures the denotational semantics of the
valuational team logic PT+ in the semantics of LT, bearing in mind how
classical propositional logic is captured in PT+. It is therefore expected
that similar algebraic constructions and axiomatisations are possible for
other types of team semantics such as modal team semantics [Vaeaenaenen2008].
Furthermore, this axiomatisation provides a way to construct proofs of the
entailment statements of these propositional team logics. It does however not
directly constitute a natural deduction system for the axiomatised logics per
se, since the terms of these proofs will in general not be confined to the
syntactical fragment of the logics. Our natural deduction system may however
motivate, and be seen as a guide in the construction of deduction systems for
these propositional team logics, and indicates the suitability of labelled
systems.

In the labelled natural deduction for LT, the rules $\mathtt{sub}$ and
$\mathtt{taut}$ establish a notion of equivalence of labels determined by
classical propositional logic. From this perspective these rules can be viewed
as structural rules of the deduction system. The rules for the formulas of LT
consist of introduction rules together with the elimination rules that are the
direct inverses of the introduction rules (up to equivalence of labels).666The
rule
$\mathord{\vphantom{\lnot}\mathchoice{\ooalign{\raisebox{0.86108pt}{$\displaystyle\neg$}\cr\raisebox{-0.86108pt}{$\displaystyle\neg$}}}{\ooalign{\raisebox{0.86108pt}{$\textstyle\neg$}\cr\raisebox{-0.86108pt}{$\textstyle\neg$}}}{\ooalign{\raisebox{0.86108pt}{$\scriptstyle\neg$}\cr\raisebox{-0.86108pt}{$\scriptstyle\neg$}}}{\ooalign{\raisebox{0.86108pt}{$\scriptscriptstyle\neg$}\cr\raisebox{-0.86108pt}{$\scriptscriptstyle\neg$}}}}\mathtt{E}$
is not directly the inverse of
$\mathord{\vphantom{\lnot}\mathchoice{\ooalign{\raisebox{0.86108pt}{$\displaystyle\neg$}\cr\raisebox{-0.86108pt}{$\displaystyle\neg$}}}{\ooalign{\raisebox{0.86108pt}{$\textstyle\neg$}\cr\raisebox{-0.86108pt}{$\textstyle\neg$}}}{\ooalign{\raisebox{0.86108pt}{$\scriptstyle\neg$}\cr\raisebox{-0.86108pt}{$\scriptstyle\neg$}}}{\ooalign{\raisebox{0.86108pt}{$\scriptscriptstyle\neg$}\cr\raisebox{-0.86108pt}{$\scriptscriptstyle\neg$}}}}\mathtt{I}$
but can be seen to be equivalent to a direct inverse rule.  In this sense, the
rules of LT harmonise, and it is possible to use more advanced proof-theoretic
methods to investigate LT. For example, it seems to be easy to turn the system
into a sequent system that could be analysed with respect to cut rules and cut
elimination. This analysis may lead up to a proof-theoretic explanation of the
internal connectives and so also of the connectives in other propositional
team logics through their axiomatisations.

By thinking of the $\mathtt{taut}$ rule as provability in an _inner logic_ we
can generalise the construction of the labelled natural deduction system into
a proof-theoretic teamification, or combination of two logics, an inner and an
outer logic. Of such constructions LT represents the special case for which
both are classical propositional logic. This opens the door for a purely
proof-theoretic approach to team logics, and more general relatives, and we
see this as an interesting future research topic. In particular this indicates
the possibility for similar constructions in a first-order setting that could
give new general insight into first-order team logics, which is an active
field of study with many applications.

## Funding

This paper was written as part of the project: Foundations for team semantics:
Meaning in an enriched framework, a research project supported by grant
2022-01685 of the Swedish Research Council, Vetenskapsrådet.

## References

  * [1] Bezhanishvili2021 N.NickBezhanishvili, G.GianlucaGrilletti, and D. E.Davide EmilioQuadrellaro 20220 Nick Bezhanishvili, Gianluca Grilletti, Davide Emilio Quadrellaro An algebraic approach to inquisitive and DNA-logics, The Review of Symbolic Logic, vol.15(2022), no.4, pp.950–990. bezhanishvili nick grilletti gianluca quadrellaro davide emilio 2022 algebraic approach to inquisitive and textttdna logics
  * [2] Bolzano1837 B.BernardBolzano 18370 Bernard Bolzano Wissenschaftlehre: Versuch einer ausführlichen und größtentheils neuen darstellung der logik mit steter rücksicht auf deren bisherige berabeiter, vol. 1, Seidel,1837. bolzano bernard 1837 wissenschaftlehre versuch einer ausfuhrlichen und grosstentheils neuen darstellung der logik mit steter rucksicht auf deren bisherige berabeiter
  * [3] Brink1984 C.ChrisBrink 19840 Chris Brink Second-order boolean algebras, Quaestiones Mathematicae, vol.7(1984), no.2, pp.93–100. brink chris 1984 second order boolean algebras
  * [4] Brink1986 C.ChrisBrink 19860 Power structures and logic, Quaestiones Mathematicae, vol.9(1986), no.1-4, pp.69–94. brink chris 1986 power structures and logic
  * [5] Brink1993 C.ChrisBrink 19930 Power structures, Algebra Universalis, vol.30(1993), pp.177–216. brink chris 1993 power structures
  * [6] Bull1984 R.RobertBull and K.KristerSegerberg 19840 Robert Bull Krister Segerberg Basic modal logic, Handbook of philosophical logic: Volume ii: Extensions of classical logic, Springer,1984, pp.1–88. bull robert segerberg krister 1984 basic modal logic
  * [7] Font16 J. M.Josep MariaFont 20160 Josep Maria Font Abstract algebraic logic: An introductory textbook, College Publications,2016. font josep maria 2016 abstract algebraic logic an introductory textbook
  * [8] Goldblatt1989 R.RobertGoldblatt 19890 Robert Goldblatt Varieties of complex algebras, Annals of pure and applied logic, vol.44(1989), no.3, pp.173–242. goldblatt robert 1989 varieties of complex algebras
  * [9] Goranko99 V.ValentinGoranko and D.DimiterVakarelov 19990 Valentin Goranko Dimiter Vakarelov Hyperboolean algebras and hyperboolean modal logic, Journal of Applied Non-classical Logics, vol.9(1999), no.2-3, pp.345–368. goranko valentin vakarelov dimiter 1999 hyperboolean algebras and hyperboolean modal logic
  * [10] Halmos2009 P.PaulHalmos and S.StevenGivant 20090 Paul Halmos Steven Givant Introduction to boolean algebras, Springer,2009. halmos paul givant steven 2009 introduction to boolean algebras
  * [11] Hella2023 L.LauriHella, K.KerkkoLuosto, and J.JoukoVäänänen 20230 Lauri Hella, Kerkko Luosto, Jouko Väänänen Dimension in team semantics, arXiv preprint arXiv:2304.03354,(2023). hella lauri luosto kerkko vaananen jouko 2023 dimension in team semantics
  * [12] Hintikka1989 J.JaakkoHintikka and G.GabrielSandu 19890 Jaakko Hintikka Gabriel Sandu Informational independence as a semantical phenomenon, Logic, methodology and philosophy of science, VIII (Moscow, 1987), Stud. Logic Found. Math., vol. 126, North-Holland, Amsterdam,1989, pp.571–589. hintikka jaakko sandu gabriel 1989 informational independence as a semantical phenomenon
  * [13] Hodges1997 W.WilfridHodges 19970 Wilfrid Hodges Compositional semantics for a language of imperfect information, Logic Journal of the IGPL, vol.5(1997), no.4, pp.539–563. hodges wilfrid 1997 compositional semantics for a language of imperfect information
  * [14] Humberstone2014 L.LloydHumberstone 20140 Lloyd Humberstone Power matrices and dunn–belnap semantics: Reflections on a remark of graham priest, The Australasian Journal of Logic, vol.11(2014), no.1. humberstone lloyd 2014 power matrices and dunn belnap semantics reflections on a remark of graham priest
  * [15] Jonsson1993 B.BjarniJónsson 19930 Bjarni Jónsson A survey of boolean algebras with operators, Algebras and orders, Springer,1993, pp.239–286. jonsson bjarni 1993 survey of boolean algebras with operators
  * [16] Kontinen2013 J.JuhaKontinen and J.JoukoVäänänen 20130 Juha Kontinen Jouko Väänänen Axiomatizing first-order consequences in dependence logic, Annals of Pure and Applied logic, vol.164(2013), no.11, pp.1101–1117. kontinen juha vaananen jouko 2013 axiomatizing first order consequences in dependence logic
  * [17] LorimerOlsson2022 O.OrvarLorimer Olsson 20220 Orvar Lorimer Olsson Monadic semantics, team logics and substitution, Master’s thesis, University of Gothenburg,2022. lorimer olsson orvar 2022 monadic semantics team logics and substitution
  * [18] Lueck2020 M.MartinLück 20200 Martin Lück Team logic: axioms, expressiveness, complexity, Ph.D. thesis, Hannover: Institutionelles Repositorium der Leibniz Universität Hannover,2020. luck martin 2020 team logic axioms expressiveness complexity
  * [19] Priest2017 G.GrahamPriest 20170 Graham Priest Plurivalent logics, The logical legacy of Nikolai Vasiliev and modern logic,(2017), pp.169–179. priest graham 2017 plurivalent logics
  * [20] Quadrellaro2020 D. E.Davide EmilioQuadrellaro 20200 Davide Emilio Quadrellaro Algebraic semantics of intuitionistic inquisitive and dependence logic, Short Papers Advances in Modal Logic AiML 2020,(2020), p.75. quadrellaro davide emilio 2020 algebraic semantics of intuitionistic inquisitive and dependence logic
  * [21] Quadrellaro2021 D. E.Davide EmilioQuadrellaro 20220 On intermediate inquisitive and dependence logics: An algebraic study, Annals of Pure and Applied Logic, vol.173(2022), no.10, p.103143. quadrellaro davide emilio 2022 on intermediate inquisitive and dependence logics an algebraic study
  * [22] Vaeaenaenen2007 J.JoukoVäänänen 20070 Jouko Väänänen Dependence logic: A new approach to independence friendly logic, vol. 70, Cambridge University Press,2007. vaananen jouko 2007 dependence logic a new approach to independence friendly logic
  * [23] Vaeaenaenen2008 J.JoukoVäänänen 20080 Modal dependence logic, New perspectives on games and interaction, vol.4(2008), pp.237–254. vaananen jouko 2008 modal dependence logic
  * [24] Venema2007 Y.YdeVenema 20070 Yde Venema 6 algebras and coalgebras, Studies in logic and practical reasoning, vol. 3: Handbook of Modal Logic, Elsevier,2007, pp.331–426. venema yde 2007 6 algebras and coalgebras
  * [25] Yang2022 F.FanYang 20220 Fan Yang Propositional union closed team logics, Annals of Pure and Applied Logic, vol.173(2022), no.6, p.103102. yang fan 2022 propositional union closed team logics
  * [26] Yang2016 F.FanYang and J.JoukoVäänänen 20160 Fan Yang Jouko Väänänen Propositional logics of dependence, Annals of Pure and Applied Logic, vol.167(2016), no.7, pp.557–589. yang fan vaananen jouko 2016 propositional logics of dependence
  * [27] Yang2017 F.FanYang and J.JoukoVäänänen 20170 Propositional team logics, Annals of Pure and Applied Logic, vol.168(2017), no.7, pp.1406–1441. yang fan vaananen jouko 2017 propositional team logics
  * [28]