arXiv:1509.01568v2 [] 8 Apr 2018

A CONSTRUCTIVE WAY TO COMPUTE THE TARSKI
NUMBER OF A GROUP
AKRAM YOUSOFZADEH

Abstract. The Tarski number of a group G is the minimal number of the
pieces of paradoxical decompositions of that group. Using configurations along
with a matrix combinatorial property we construct paradoxical decompositions. We also compute an upper bound for the Tarski number of a given
non-amenable group by counting the number of paths in a diagram associated
to the group.

1. Introduction
Rosenblatt and Willis introduced a concept for groups to show that for an infinite
discrete amenable group or a non-discrete amenable group G a net of positive,
normalized functions in L1 (G) can be constructed such that this net converges
weak* to invariance but does not converge strongly to invariance [8]. This concept
which is called configuration is also used to classify some group theoretical properties
(see for example [1, 2]).
Configurations are strongly linked to the amenability of groups and by Tarski’s
alternative, a discrete group is non-amenable if and only if it admits a paradoxical
decomposition. Therefore it is valuable to construct the paradoxical decomposition
for such a group, using configurations. This problem which was originally asked
by Willis is answered partially in [7]. In that paper the paradoxical decomposition
was constructed under a paradoxical condition.
In the present paper we define a general matrix combinatorial property under
which the paradoxical decomposition is completely constructed. We also find a new
upper bound for the Tarski number of a given non-amenable group.

Notations. The following notations are used throughout this paper
•
•
•
•
•
•

N,
F Z and R are the sets of natural, integer and real numbers, respectively,
is the disjoint union of sets,
gA = {ga; a ∈ A}, for a group G, A ⊆ G and g ∈ G,
P(X) is the power set of the set X,
|X| is the the cardinal number of the set X,
A (0, 1)-matrix is a matrix with entries in {0, 1}.

If v is a vector of real numbers and n ∈ Z, by v ≥ n we mean that v has entries
equal to or greater than n.
1

2

AKRAM YOUSOFZADEH

2. Preliminaries
2.1. Matrix theory. We use Gordan’s theorem to find nontrivial nonnegative
solutions to a homogenous system of linear equations with real coefficients. This
theorem has also applications in linear programming [4].
Theorem 2.1. (Gordan 1873) Either a linear homogenous system of equations
AX = 0 possesses a nontrivial solution in nonnegative variables or there exists an
equation, formed by taking some linear combination of equations, that all positive
coefficients. That is, either there exists an x such that
Ax = 0,

0 6= x ≥ 0

t

or there exists a vector m such that m A > 0 (has positive entries).
Remark 2.2. In Theorem 2.1, if A is a matrix with rational entries, then the
entries of m can be chosen in Z.
The main theorem of this paper is proved under a certain condition. To clarify
this condition, we need some definitions.
Let π : {1, . . . , n} → {1, . . . , n} be a permutation for the set {1, . . . , n}. Then


eπ(1)
 eπ(2) 


Pπ =  . 
 .. 
eπ(n)

is called the permutation matrix associated to π, where ei denotes the row vector
of length n with 1 in the i-th position and 0 otherwise. When the permutation
matrix Pπ is multiplied with a matrix M from left, Pπ M will permute the rows of
M by π. 

P1
 P2 


If P =  .  is a permutation matrix, by P + we mean the matrix with
 .. 
Pn
shifted rows, i.e.


P2
 P3 




P + = Pρ P =  ...  ,


 Pn 
P1
in which ρ is the cyclic permutation (1 2 . . . n). Throughout we use the notation


1 0 0 ... 0
 1 1 0 ... 0 
X


T = .
=
Eij ,

 ..

1≤j≤i≤n
1 1 1 ... 1

where Eij is the matrix with 1 in ij position and 0 otherwise. When the matrix T
is multiplied with a matrix M from left, j-th row of T M will be the sum of j first
rows of M .

A CONSTRUCTIVE WAY TO COMPUTE THE TARSKI NUMBER OF A GROUP





Definition 2.3. Let ℓ ∈ N and 


A1
A2
..
.









 and 



B1
B2
..
.

3





 be two (0, 1)-matrices with


A
Bn
Pn n
rows Ai , Bi . Let also the vector i=1 (Bi − Ai ) has strictly positive entries. If there
exists a permutation matrix Pπ such that the matrix
(1)

T Pπ (B − A) − Pπ+ A

has integer entries equal or greater than −1, we say that the homogenous system
of equations (B − A)X = 0 is normal.
Pn
It is apparent that if i=1 (Bi − Ai ) has strictly positive entries, then the system
has no non-zero non-negative solution. Conversely, if (B − A)X = 0 is a system
of equations with no non-zero non-negative solution, then by Gordan’s theorem
there exists a vector m = (m1 , . . . , mn ) such that mt (B − A) has strictly positive
entries. If we permit B − A to have repeated rows and we insert the opposite of a
row (exchanging the corresponding rows of A and B) if necessary, then mi can be
chosen in {0, 1}. Omit Bi − Ai , whereP
mi = 0 and denote the modified matrix by
n
B − A again. So, we can assume that i=1 (Bi − Ai ) has strictly positive entries.
It is to be noted that there exist examples of both normal and non-normal
systems of equations with no nonzero non-negative solution. We will explain the
relation between normality and paradoxical decompositions in section 3.
2.2. Non-amenable discrete groups. Let G be a discrete group. Then G is
called amenable if it admits a finitely additive probability measure µ on the σ−algebra
P(G) such that
µ(gA) = µ(A),

(A ⊆ G, g ∈ G).

Definition 2.4. [10] Let G be a group acting on a set X and suppose E ⊆ X.
E is G-paradoxical (or, paradoxical with respect to G) if for some positive integers m, n there are pairwise disjoint subsets A1 , . . . , An , B1 , . . . , Bm of E and
g1 . . . , gn , h1 . . . , hm ∈ G such that
(2)

E=

n
G

i=1

gi Ai =

m
G

h j Bi .

j=1

A group G is called paradoxical if it is G-paradoxical, where G acts on itself
by left multiplication. Clearly if G is a paradoxical group satisfying the above
definition, then it cannot be amenable. Indeed if µ is a G−invariant probability
measure, then
X
X
1 = µ(G) =
µ(Ai ) +
µ(Bj )
X
X
=
µ(gi Ai ) +
µ(hj Bj ) = µ(G) + µ(G) = 2.
In fact there is the following remarkable alternative due to Alfred Tarski.

Theorem 2.5. Let G be a discrete group. Exactly one of the following happens
1) G is paradoxical,
2) G is amenable.

AKRAM YOUSOFZADEH

4

The number τ = n + m for n and m in (2) is called the Tarski number of that
paradoxical decomposition; the minimum of all such numbers over all the possible
paradoxical decompositions of G, is called the Tarski number of G and denoted by
τ (G). In the case that there is no paradoxical decomposition, we set τ (G) = ∞.
The Tarski number of a group is of real interest and has been estimated for some
classes of groups. But it is not so easy to compute in many cases. For more details
see [9] and [3].
We draw the reader’s attention to the next proposition for different types of
paradoxical decompositions.
Proposition 2.6. [7, Proposition 1.2] Let G be a group. Then the following statements are equivalent
1) There exist a partition {A1 , . . . , An , B1 , . . . , Bm } of G and g1 , . . . , gn and
h1 , . . . , hm in G such that {gi Ai }ni=1 and {hj Bj }m
j=1 form partitions of G.
2) There exist pairwise disjoint subsets A1 , . . . , An , B1 , . . . , Bm of G and elements g1 , . . . , gn and h1 , . . . , hm in G such that {gi Ai }ni=1 and {hj Bj }m
j=1 form
partitions of G.
3) There exist pairwise disjoint subsets A1 , . . . , AnS, B1 , . . . , BmSof G and elen
m
ments g1 , . . . , gn and h1 , . . . , hm in G such that G = i=1 gi Ai = j=1 hj Bj (not
necessarily pairwise disjoint).

Because of the above equivalence, G admits a paradoxical decomposition, if any
condition of Proposition 2.6 holds. The decomposition in condition 1 is called a
complete paradoxical decomposition. By [5, Theorem A.1] if the conditions 2 or 3
are satisfied for a group G, then τ (G) ≤ m + n.
2.3. Configuration of groups. Let G be a discrete group. The configurations
of G are defined in terms of finite generating sets and finite partitions of G. If
g = (g1 , . . . , gn ) is a string of elements of G and E = {E1 , . . . , Em } is a partition
of G, a configuration corresponding to (g, E) is an (n + 1)−tuple C = (c0 , . . . , cn ),
where 1 ≤ ci ≤ m for each i, such that there is x in G with x ∈ Ec0 and gi x ∈ Eci for
each 1 ≤ i ≤ n. The set of all configurations corresponding to the pair (g, E) will be
denoted by Con(g, E). It is shown that groups with the same set of configurations
have some common properties. For example they obey the same semigroup laws
and have the same Tarski numbers (see [1] and [11]).
In the case that g = {g1 , . . . , gn } is a generating set for G, the configuration
C = (c0 , . . . , cn ) may be described as a labelled tree which is a subgraph of the
Cayley graph of the finitely generated group G and configuration set Con(g, E) is
a set of rooted trees having height 1. In last section of the paper we assign a new
graph to G that depends on the pair (g, E).
If (g, E) is as above and for each C ∈ Con(g, E)
x0 (C) = Ec0 ∩ (∩nj=1 gj−1 Ecj )

and

xj (C) = gj x0 (C),

then it is seen that for any 0 ≤ j ≤ n, {xj (C); C ∈PCon(g, E)} is a partition for
G. Let C ∈ Con(g, E) and f ∈ ℓ1 (G). Define fC = x∈x0 (C) f (x). Then we have
(see [8])
(1 ≤ j ≤ n, 1 ≤ i ≤ m)
hf −gj f, χEi i = 0,
if and only if
X
X
fC
(1 ≤ j ≤ n, 1 ≤ i ≤ m).
fC =
x0 (C)⊆Ei

xj (C)⊆Ei

A CONSTRUCTIVE WAY TO COMPUTE THE TARSKI NUMBER OF A GROUP

5

For each pair (g, E) for G, the system of equations
X
X
fC ,
(1 ≤ i ≤ m, 0 ≤ j, k ≤ n)
fC =
xj (C)⊆Ei

xk (C)⊆Ei

with variables fC , C ∈ Con(g, E) is called the system of configuration equations
corresponding to (g, E) and is denoted by Eq(g, E). By a normalized solution
P to this
system, we mean a solution (fC )C such that for each C, fC ≥ 0 and C fC = 1.
A group G isR amenable if and only if there is a net (fα )α of positive functions in
L1 (G) with fα = 1 which is weak* convergence to invariance, that is for any
F ∈ L∞ (G) and any g ∈ G
limhfα −g fα , F i = 0
α

(see [6]). Using this fact, Rosenblatt and Willis proved the following theorem
Theorem 2.7. [8, Proposition 2.4] There is a normalized solution of every possible
instance of the configuration equations if and only if G is amenable.
We will apply this theorem to find paradoxical decompositions.
3. Main Theorem
Throughout this section by G, g = (g1 , . . . , gn ) and E = {E1 , . . . , Em } we mean
a group, a finite string of elements of G and a finite partition for G, respectively.
If D is a subset of Con(g, E), we use the following notation
G
D̃ :=
x0 (C).
C∈D

˜ E) = G. Clearly D1 , D2 ⊆ Con(g, E) are disjoint if and only
In particular Con(g,
P
P
if D̃1 and D̃2 are. The configuration equation xj (C)⊆Ei fC = xk (C)⊆Ei fC is
written in the form aX = bX, where Con(g, E) = {C1 , . . . , Cℓ },


fC1
 fC2 


X =  . ,
 .. 
fCℓ
a is the coefficient vector of the left hand side and b is the coefficient vector of the
right hand side of the equation.

Theorem 3.1. If a subsystem of Eq(g, E) is normal, then G is non-amenable and
a paradoxical decomposition of G can be written in terms of g and E.




V1
W1
 V2 
 W2 




Proof. Let V =  .  and W =  .  be (0, 1)-matrices in Mp×ℓ (R) such
 .. 
 .. 
Vp
Wp
that (W − V )X = 0 is the normal subsystem of Eq(g, E) satisfying (1)for a permutation matrix Pπ . Write
Vt = (Vt (C))C∈Con(g,E)

and

Wt = (Wt (C))C∈Con(g,E) ,

(1 ≤ t ≤ p).

AKRAM YOUSOFZADEH

6

Then by the normality of (W − V )X = 0, for each C ∈ Con(g, E)
(3)

αC :=

p
X

Wt (C) −

t=1

p
X

Vt (C) > 0.

t=1

We consider only the case that Pπ = I, the identity matrix. Otherwise defining
Vt∗ = Vπ(t) and Wt∗ = Wπ(t) we see that
T Pπ (W − V ) − Pπ+ V = T (W ∗ − V ∗ ) − V ∗ +
and the proof is carried out in a similar way. Therefore throughout the proof we
assume
W1 (C) − (V1 (C) + V2 (C)) ≥ − 1,
(W1 (C) + W2 (C)) − (V1 (C) + V2 (C) + V3 (C)) ≥ − 1,
..
.
p
p−1
X
X
Vt (C)) ≥ − 1.
Wt (C)) −
(
t=1

t=1

Suppose that (i1 , i2 , . . . , ip ), (ji1 , ji2 , . . . , jip ) and (ki1 , ki2 , . . . , kip ) are strings such
that is ∈ {1, . . . , m} and jis , kis ∈ {0, 1, . . . , n} and the modified system is
X
X
fC ,
(1 ≤ t ≤ p).
fC =
xki (C)⊆Eit

xji (C)⊆Eit
t

t

Note that the strings are used instead of subsets since the repetition is not excluded
for the equations. For convenience we use the following notations for 1 ≤ t ≤ p
At = {C; xkit (C) ⊆ Eit } and Bt = {C; xjit (C) ⊆ Eit },
In other words, the system can be written as
X
X
fC ,
fC =
(4)

(1 ≤ t ≤ p).

(1 ≤ t ≤ p).

C∈Bt

C∈At

It is not difficult to see that for 1 ≤ t ≤ p
G
G
(5)
ġt
x0 (C ∗ ) =
x0 (C),
C ∗ ∈At

C∈Bt

gjit . For C ∈ Bt and C ∗ ∈ At put
where ġt = gk−1
i
t

Et (C ∗ , C) = x0 (C ∗ ) ∩ ġt−1 x0 (C).
Then we have by (5)
(6)

x0 (C) =

G

ġt Et (C ∗ , C),

(C ∈ Bt ).

C ∗ ∈At

Case 1. The Fsets At are pairwise disjoint. According to (3) and (4), for
p
C
each C ∈ A := t=1 At there exist at least two numbers 1 ≤ tC
1 , t2 ≤ p such that

A CONSTRUCTIVE WAY TO COMPUTE THE TARSKI NUMBER OF A GROUP

7

C ∈ BtC1 and C ∈ BtC2 . Also for each C ∈ B := Con(g, E) \ A there exists at least
one 1 ≤ tC ≤ p such that C ∈ BtC . This fact together with (6) implies that
G
G
ġtC1 EtC1 (C ∗ , C) =
ġtC2 EtC2 (C ∗ , C),
(C ∈ A)
x0 (C) =
C ∗ ∈AtC

C ∗ ∈AtC
1

2

and
x0 (C) =

G

C ∗ ∈A

Consequently the fact that
G=

"

ġtC EtC (C ∗ , C),

(C ∈ B).

tC

G

#

x0 (C)

C∈A

G

"

G

#

x0 (C)

C∈B

necessitates the following two equations


"
#
G
G

G G
∗
G=
ġtC1 EtC1 (C , C)
(7)
x0 (C)
C∈A C ∗ ∈AtC

C∈B

1

and
(8)



G
G=

G



C∈A C ∗ ∈AtC
2


G
G

ġtC2 EtC2 (C ∗ , C) 

G

C∈B C ∗ ∈AtC



ġtC EtC (C ∗ , C) .

We emphasize that all the sets in the following families are pairwise disjoint
(1) x0 (C), with C ∈ B,
(2) EtC (C ∗ , C), with C ∈ B, C ∗ ∈ AtC ,
(3) EtC1 (C ∗ , C), with C ∈ A, C ∗ ∈ AtC1 ,
(4) EtC2 (C ∗ , C), with C ∈ A, C ∗ ∈ AtC2 .
We know that A ∩ B = ∅ and Ai ∩ Aj = ∅ for i 6= j. On the other hand for
C ∗ ∈ At , Et (C ∗ , C) ⊆ x0 (C ∗ ) ⊆ Ãt ⊆ Ã. Therefore the sets of types (2), (3) and
C
(4) are all disjoint from the sets of type (1). Since tC
(C ∗ , C) ⊆ AtC1
1 6= t2 , EtC
1
∗
∗
and EtC2 (C , C) ⊆ AtC2 and AtC1 ∩ AtC2 = ∅, we have EtC1 (C , C) ∩ EtC2 (C ∗ , C) = ∅.
′

Now let i ∈ {1, 2} and tC
= tC , for C ∈ B and C ′ ∈ A. Let C ∗ ∈ AtC and
i
−1
′∗
′
C ∈ AtC ′ . Applying A ∩ B = ∅ once again, we see gt−1
C x0 (C) ∩ g C ′ x0 (C ) = ∅.
t
i

i

Thus EtC ′ (C ′∗ , C ′ ) ∩ EtC (C ∗ , C) = ∅. Therefore all the sets of types (3) and (4) are
i
disjoint from the sets of type (2). It remains to show that for distinct configurations
C, D ∈ A, i, j ∈ {1, 2}, C ∗ ∈ AtCi and D∗ ∈ AtD
one has EtCi (C ∗ , C)∩EtD
(D∗ , D) =
j
j
D
∅. But it is clear since if tC
i 6= tj , then

EtCi (C ∗ , C) ∩ EtD
(D∗ , D) ⊆ x0 (C ∗ ) ∩ x0 (D∗ ) ⊆ ÃtCi ∩ ÃtD
=∅
j
j
D
and if tC
i = tj , then
−1
EtCi (C ∗ , C) ∩ EtD
(D∗ , D) ⊆ ġt−1
C (x0 (C) ∩ x0 (D)) = ġtC (∅) = ∅.
j
i

i

Consequently the equations (7) and (8) form a paradoxical decomposition of G.
Case 2. The sets At are not pairwise disjoint. The procedure in case 1 does
not work here because the sets in a paradoxical decomposition must be disjoint.

AKRAM YOUSOFZADEH

8

In the sequel we shall replace the sets A1 , . . . , Ap with new sets P1 , . . . , Pp , which
are
Fp disjoint and then a paradoxical decomposition with respect to a partition of
i=1 P̃i will be given.
For C ∈ Con(g, E) if t0 is the least number in {1, . . . , p} such that Vt0 (C) 6= 0,
define Vt′0 (C) = 1 and for t 6= t0 put Vt′ (C) = 0. Then
(
Pp
p
X
1, if
′
t=1 Vt (C) > 0
Vt (C) =
(9)
0, otherwise.
t=1

We need a counter to compute the number of appearance of a configuration in
V1 , . . . , Vp and W1 , . . . , Wp . To achieve this purpose define
(P
Pp
p
( t=1 Vt (C)) − 1, if
0
t=1 Vt (C) > 0
(10)
mC =
0,
otherwise
and for 1 ≤ t ≤ p
mtC

(11)

=

(

t−1
mt−1
>0
C − 1, if Wt (C) = 1, mC
t−1
mC ,
otherwise.

Consequently by (10) we have for C ∈ Con(g, E)
p
X

(12)

Vt (C) −

p
X

Vt′ (C) = m0C .

t=1

t=1

Consider the vectors (Wt′ (C))Con(g,E) , 1 ≤ t ≤ p with the following definition
(
Wt (C) − 1, if Wt (C) = 1, mt−1
>0
′
C
Wt (C) =
Wt (C),
otherwise.
It is seen by (11) that for every C ∈ Con(g, E)
p
X

Wt (C) −

t=1

p
X

Wt′ (C) =

p
X

[Wt (C) − Wt′ (C)]

t=1

t=1

=
=
=

p
X

t
[mt−1
C − mC ]

t=1
m0C −
m0C .

mpC

Thus by (12) and (3)
(13)

p
X
t=1

Put

Wt′ (C) −

p
X

Vt′ (C) =

p
X
t=1

t=1

Wt (C) −

p
X

Vt (C) = αC .

t=1

Pt := {C : Vt′ (C) 6= 0} and Qt := {C : Wt′ (C) 6= 0}.
Then by (9) it is evident that P1 , . . . , Pp are pairwise disjoint. It is also clear for
S
1 ≤ t ≤ p that Pt ⊆ At , Qt ⊆ Bt and At \ Pt = t−1
j=1 (At ∩ Aj ). Let 1 ≤ t < j ≤ p
and define
# t−1
"
j−1
G
G j
j
Dts ) ∩ (Aj \ Pj ) \
Dk ,
(14)
Dt = (Bt \
s=t+1

k=1

A CONSTRUCTIVE WAY TO COMPUTE THE TARSKI NUMBER OF A GROUP

using the conventions
′

Sl2

l=l1

9

El = ∅, when 0 ≤ l2 < l1 . Obviously

Dtj ∩ Dtj = ∅

Dtj ∩ Dtj′ = ∅,

and

(t 6= t′ , j 6= j ′ ).

Next for 1 ≤ t ≤ p − 1 we prove that
Q t = Bt \ (

(15)

p
G

Dtj ).

j=t+1

To see this, let C ∈ Qt . Then C ∈ Bt and Wt′ (C) = 1, which means that mt−1
= 0.
C
If m0C = 0, then for each 2 ≤ j ≤ p, C ∈
/ Aj \ Pj . In particular C ∈
/ Dtj , for every
t + 1 ≤ j ≤ p. Assume that mt−1
= k > 0. Then by (10) there are exactly k + 1
C
numbers j0 < j1 < · · · < jk such that C ∈ ∩ki=0 Aji or equivalently
(1 ≤ i ≤ k).
C ∈ Aji \ Pji ,
Pt−1
Pt
This along with the normality condition ( j=1 Wj − j=1 Vj ≥ −1) implies that
there exist natural numbers t1 < t2 < · · · < tk < t such that C ∈ Bti , (1 ≤ i ≤ k),
where t1 is the smallest number with this property. Therefore by (14) and the
F
T
/ pj=t+1 Dtj . The converse is
sentence after that C ∈ ki=1 Dtjii . So, we have C ∈
obtained by a similar argument. We continue the proof of the theorem in the following four steps.
P
Pt
Step 1. By the normality condition if 1 ≤ t ≤ p, then t−1
j=1 Wj −
j=1 Vj ≥ −1.
This means (At \ Pt ) ⊆ ∪t−1
B
.
We
shall
prove
that
for
1
≤
t
≤
p
j
j=1
At \ Pt =

(16)

t−1
G

Dst .

s=1

Firstly we show that
At \ Pt ⊆

t−1
[

s=1

"

(Bs \

j
∪t−1
j=s+1 Ds )

\

s−1
G

Dkt

k=1

#

.

Let C ∈ At \ Pt and pick the smallest natural number t0 < t such that C ∈ Bt0
(it is possible by the normality condition). If for each t0 < j < t and 1 ≤ k < t0 ,
Ft0 −1 t
Ft−1
/ Dkj , we are done. If C ∈ k=1
Dk , then C ∈ k=1 Dkt because
C∈
/ Dtj0 and C ∈
t0 < t. Assume that for some t0 < j < t, C ∈ Dtj0 . Then by (14) C ∈ Aj \ Pj . By the
definition of Pj , this means that there exists at least one natural number s < j such
that C ∈ Aj ∩ As but on the other side C ∈ At . Consequently C ∈ Aj ∩ As ∩ At .
Pt−1
Pt
Since by the normality condition j=1 Wj − j=1 Vj ≥ −1, there are at least two
sets of the form Bi containing C. Accordingly there exists the smallest positive
integer t′0 < t such that C ∈ Bt′0 . This process is obviously finite and therefore we
achieve the purpose. Hence
"
# t−1
s−1
t−1
G
G
[
t−1
j
t
(Bs \ ∪j=s+1 Ds ) \
Dk =
Dst .
At \ Pt = (At \ Pt ) ∩
s=1

k=1

s=1

Step 2. We show by induction that for all j ≥ 1 there exists a family {Aσj , σj ∈
Fj−1
Λj } with cardinality 2j−1 −1 of disjoint subsets (possibly the empty sets) of t=1 P̃t

AKRAM YOUSOFZADEH

10

σj ∈ Λj } of G such that
G
Ãj \ P̃j =
gσj Aσj .

and the members {gσj ,

σj ∈Λj

Since Ã1 \ P̃1 = ∅, it is natural to set Aσ1 = ∅ and gσ1 = e, the identity element of
G. For j = 2, we have Ã2 \ P̃2 = Ã1 ∩ Ã2 ⊆ B̃1 = ġ1 Ã1 . Hence Ã2 \ P̃2 = ġ1 (ġ1−1 D̃12 ).
Set σ2 = 1, Λ2 = {σ2 } and gσ2 = ġ1 . Note that |Λ2 | = 1 = 22−1 − 1. Now let for
1≤t≤j
G
and |Λt | = 2t−1 − 1.
Ãt \ P̃t =
gσt Aσt
σt ∈Λt

By (16)

Ãj+1 \ P̃j+1 =

j
G

D̃tj+1

t=1

=

j
G

ġt (ġt−1 D̃tj+1 )

t=1

=

j
G

t=1

=

j
G



G
ġt [ġt−1 D̃tj+1 ∩ P̃t ] [ġt−1 D̃tj+1 ∩ (Ãt \ P̃t )]
ġt

t=1

=

j
G

[ġt−1 D̃tj+1

G
G
∩ P̃t ] [ġt−1 D̃tj+1 ∩ (
gσt Aσt )]
σt ∈Λt

!

ġt (ġt−1 D̃tj+1 ∩ P̃t )

t=1

Dtj+1

G

j
G
G

!
!

ġt−1 D̃tj+1 ∩ Aσt ] .
ġt gσt [gσ−1
t

t=2 σt ∈Λt

We have used the fact that
⊆ Pt . Recall for the last equation that Aσ1 = ∅.
Pj
Note that the number of pieces in the decomposition above is j + t=2 |Λt |, so by
the induction hypothesis
|Λj+1 | = j +

j
X

(2t−1 − 1) = 2j − 1.

t=2

Hence it is done for j + 1. This completes the Step 2. Before proceeding to the rest
of the proof, we draw the reader’s attention to the next two remarks.
Remark 3.2. In step 2 we explained how the sets Aσj+1 are obtained from the sets
Pt and Aσt , where 1 ≤ t < j + 1. In fact each Aσj+1 is in one of the following two
types:
ġt−1 D̃tj+1 ∩ P̃t
(I)
(II)
ġt−1 D̃tj+1 ∩ Aσt ,
gσ−1
t
for suitable t < j + 1 and σt ∈ Λt . So, one can easily see that Aσj+1 ∩ Aσt 6= ∅ if
and only if Aσj+1 ⊆ Aσt . In this case for every σt′ 6= σt , Aσj+1 ∩ Aσt′ = ∅.
Remark 3.3. For 1 ≤ r < t ≤ p and σt ∈ Λt , either Aσt and P̃r are disjoint or
Aσt ⊆ P̃r . To see this we apply Remark 3.2. Let Aσt ∩ P̃r 6= ∅. If Aσt is of type
(I), then Aσt ⊆ P̃k , for some k < t. In this case P̃r ∩ P̃k 6= ∅, which is impossible
unless k = r. Therefore Aσt ⊆ P̃r . Now suppose that Aσt is of type (II) and l be
the smallest natural number such that for some σl ∈ Λl , Aσt ⊆ Aσl and Aσl is of

A CONSTRUCTIVE WAY TO COMPUTE THE TARSKI NUMBER OF A GROUP

11

l
type (II). Then Aσl = P̃m ∩ ġ −1 D̃m
⊆ P̃m , for some m < l, which is not possible
unless m = r. This implies that Aσt ⊆ P̃r .

Step 3. We show that for 1 ≤ t ≤ p and C ∈ Qt there exists a family {MC
δt ∈
δt ,
F
Γt } with cardinality 2t−1 of disjoint subsets of tj=1 P̃j and the members {hC
,
δt ∈
δt
Γt } of G such that
G
C
hC
(17)
x0 (C) =
δt Mδt .
δt ∈Γt

Since Qt ⊆ Bt , by Step 1 we have

Q̃t ⊆ B̃t = ġt Ãt
G
= ġt P̃t ġt (Ãt \ P̃t )
G
G
= ġt P̃t ġt (
gσt Aσt )
σt ∈Λt

G G
ġt gσt Aσt ).
= ġt P̃t (
σt ∈Λt

Clearly by Step 1 the number of pieces in this decomposition is 1 + |Λt | = 2t−1 .
Therefore for C ∈ Qt , one has
G G
x0 (C) = ġt (P̃t ∩ ġt−1 x0 (C)) (
ġt−1 x0 (C))).
ġt gσt (Aσt ∩ gσ−1
t
σt ∈Λt

Now set MδC0 = P̃t ∩ ġt−1 x0 (C) and MδCt = Aσt ∩ gσ−1
ġt−1 x0 (C)), where σt ∈ Λt .
t
C
Note that these sets are pairwise disjoint; Mδ0 is a subset of P̃t whereas the sets
Ft−1
Ft−1
MδCt , δt ∈ Λt are disjoint subsets of j=1 P̃j and besides ( j=1 P̃j ) ∩ P̃t = ∅. Define
C
C
Γt = {δ0 } ∪ Λt , hC
δt = ġt gσt , where δt = σt ∈ Λt and hδt0 = ġt . Thus {Mδt , δt ∈ Γt }
is a family of pairwise disjoint subsets of G and
G
C
x0 (C) =
hC
δt Mδt .
δt ∈Γt

′

It is noticeable that for 1 ≤ t 6= s ≤ p, MδCt ∩ MδCs = ∅, where C ∈ Qt and C ′ ∈ Qs .
We show this below. Without loss of generality assume that t < s. Letting C ∈ Qt
and C ′ ∈ Qs , we need to prove that the following four equalities are satisfied
′

MδC0 ∩ MδC0 = ∅,
′

MδCt ∩ MδC0 = ∅,
′

MδC0 ∩ MδCs = ∅,
′

MδCt ∩ MδCs = ∅.
But it is equivalent to show that
(18)

[P̃t ∩ ġt−1 Q̃t ] ∩ [P̃s ∩ ġs−1 Q̃s ] = ∅,

(19)

ġt−1 Q̃t )] = ∅,
[P̃s ∩ ġs−1 Q̃s ] ∩ [Aσt ∩ gσ−1
t

(20)

ġs−1 Q̃s )] = ∅,
[P̃t ∩ ġt−1 Q̃t ] ∩ [Aσs ∩ gσ−1
s

(21)

ġs−1 Q̃s )] = ∅.
ġt−1 Q̃t )] ∩ [Aσs ∩ gσ−1
[Aσt ∩ gσ−1
s
t

AKRAM YOUSOFZADEH

12

The first
two equalities are trivial, since for each r 6= s, Pr ∩ Ps = ∅ and besides,
Ft−1
Aσt ⊆ r=1 P̃r and t < s. We now prove (20). If Aσs is of type (I), then there
exists l < s such that As = ġl−1 D̃ls ∩ P̃l . So
ġs−1 Q̃s )] ⊆ P̃l ∩ P̃t .
[P̃t ∩ ġt−1 Q̃t ] ∩ [Aσs ∩ gσ−1
s
The set P̃l ∩ P̃t is clearly empty if l 6= t. If l = t,
ġs−1 Q̃s ] ⊆ P̃l ∩ ġl−1 Q̃l ∩ ġl−1 D̃ls
[P̃t ∩ ġt−1 Q̃t ] ∩ [Aσs ∩ gσ−1
s
and P̃l ∩ ġl−1 Q̃l ∩ ġl−1 D̃ls is also empty since Q̃l ∩ D̃ls , by (15). Now let Aσs be of
type (II) and k be the smallest natural number such that Aσs ⊆ Aσk and Aσk is
of type (II). This implies that Aσk ⊆ P̃l ∩ ġl−1 D̃lk , for some l < k. If (20) does
not satisfy, then by Remark 3.3, Aσs ⊆ P̃t and this is impossible unless t = l. So
Aσs ⊆ Aσk ⊆ ġt−1 D̃tk ∩ P̃t . Taking into account that Dtk ∩ Q̃t = ∅, we have
[P̃t ∩ ġt−1 Q̃t ] ∩ Aσs ⊆ ġt−1 Q̃t ∩ ġt−1 D̃tk = ∅.
This contradicts our assumption.
To prove (21) let Aσs ∩ Aσt 6= ∅. By Remark 3.2 Aσs ⊆ Aσt . In fact Aσs =
ġt−1 D̃ts . Thus we have
Aσt ∩ gσ−1
t
ġt−1 D̃ts = ∅,
ġt−1 Q̃t ∩ gσ−1
ġs−1 Q̃s ] ⊆ Aσt ∩ gσ−1
ġt−1 Q̃t ] ∩ [Aσs ∩ gσ−1
[Aσt ∩ gσ−1
t
t
s
t
because Q̃t ∩ D̃ts = ∅.
Step 4. P1 , P2 , . . . , Pp are pairwise disjoint and for each C ∈ Con(g, E)
p
X

Vt′ (C) ∈ {0, 1}.

t=1

P
P
For C ∈ Con(g, E) we put zC = αC + pt=1 Vt′ (C). This way, if pt=1 Vt′ (C) = 1,
C
then zc ≥ 2. So, by (13) there are at least two numbers 1 ≤ tC
1 , t2 ≤ p such that
C ∈ QtC1 and C ∈ QtC2 . Therefore by Step 2,
G
G
C
C
hC
hC
x0 (C) =
δ C Mδ C .
δ C Mδ C =
1

t
1

t
1

δtC ∈ΓtC

δtC ∈ΓtC
2

1

t
2

t
2

2

Pp
On the other hand, if t=1 Vt′ (C) = 0, then zc ≥ 1, so by (13) there is at least one
number 1 ≤ tC ≤ p such that C ∈ QtC . Therefore by Step 2,
G
C
hC
x0 (C) =
δtC MδtC .
δtC ∈ΓtC

Thus



G⊇

P

G

(

G

MC
δ C)
t
1

Vi′ (C)=1 δtC ∈ΓtC
1

1

G




G

P

(

G

δtC ∈ΓtC

G

2

2




MC
δ C )

G

t
2

Vi′ (C)=0 δtC ∈ΓtC




MC
δtC

G




P

G

Vi′ (C)=0



x0 (C) .

A CONSTRUCTIVE WAY TO COMPUTE THE TARSKI NUMBER OF A GROUP

13

Observe that the sets in the right hand side of above inclusion are pairwise disjoint
because
p
G
X
Pi ,
{C ∈ Con(g, E),
Vi′ (C) = 0} ⊆ Con(g, E) \
i=1

i.e.,




P

G

Vi′ (C)=0



x0 (C)

p
G

\

P̃i

i=1

!

=∅

F
and the sets MδCt , δt ∈ Γt are pairwise disjoint subsets of pi=1 P̃i (take into account
C
that tC
1 , and t2 are distinct numbers). Based on our choice of sets

 

G
G
G
G
G


C
C 

G=
(
hC
(
hC
δtC MδtC )
δtC MδtC )
P




G=

P

Vi′ (C)=1 δtC ∈ΓtC

P

1

1

1

G

(

G

Vi′ (C)=1 δtC ∈ΓtC
2

2




G
C 

hC
δtC MδtC )
2

2

P

Vi′ (C)=0 δtC ∈ΓtC

G

Vi′ (C)=0



x0 (C) ,

which is a paradoxical decomposition of G after omitting the empty sets from this
decomposition. This decomposition is complete if for each C ∈ Con(g, E),
n
X

Vi′ (C) = aC = 1.

i=1

Otherwise the decomposition is not complete but by a process described in the
proof of [7, Proposition 1.2] it can be changed into a complete one.

Corollary 3.4. Using the notations of the proof of Theorem 3.1, if for every C ∈
Con(g, E), aC = 1, then τ (G) ≤ (ℓ − 1)(2p − 1).
Proof. By the definition of configuration the cardinality of each Bt cannot be more
than ℓ − 1, where |Con(g, E)| = ℓ. The Step 3 in the proof of Theorem 3.1 and the
explanation following Proposition 2.6 yields
τ (G) ≤
≤

p
X

t=1
p
X

|Λt ||Qt |
2t−1 |Bt |

t=1

≤

p
X

2t−1 (ℓ − 1)

t=1

≤ (ℓ − 1)(2p − 1).

Remark 3.5. In [7] the authors constructed the paradoxical decomposition under
the paradoxical condition. That is, a subsystem of Eq(g, E) is equivalent to BX = 0,

AKRAM YOUSOFZADEH

14

Pm
where each row of B has nonnegative entries and is of the form i=1 (Lji i − Lki i ),
for some ji , ki ∈ {0, . . . , n}, where Lji is the coefficient vector of the equation
X
X
fC = 0
fC −
x0 (C)⊆Ei

xj (C)⊆Ei

Pm
ks
js
and in addition B has no zero column. Let Rs = i=1 (Li i − Li i ) be s-th row of
B. Then
m
X
X
X
X
fC ) =
Rs (C)fC ,
fC −
(
i=1 xjs (C)⊆Ei

so

m
X

(

i

X

fC ) =

X

fC ) =

m
X

(

X

fC ) +

i=1 xks (C)⊆Ei

i=1 xjs (C)⊆Ei
i

C

xks (C)⊆Ei

i

i

X

Rs (C)fC

C

therefore we have
m
X

(

But Con(g, E) =
where

i=1





W = (


x0 (C)⊆Ei

1, 1, . . . , 1
1, 1, . . . , 1
..
.
1, 1, . . . , 1

X

(

i=1 x0 (C)⊆Ei

i=1 x0 (C)⊆Ei

Fm F

m
X



fC ) +

X

Rs (C)fC .

C

x0 (C). Consequently we can replace B by W − V,


 
 
+
 

R1
R2
..
.
Rp









) and V = 



1, 1, . . . , 1
1, 1, . . . , 1
..
.
1, 1, . . . , 1





.


Since by assumption each Rs has nonnegative
Pentries, Ws − Vs − Vs+1 has entries
≥ −1. Finally B has no zero column, so if s (Ws − Vs ) = (αC )C , then αC > 0.
This shows that the new system satisfies the normality condition in the statement
of Theorem 3.1.
4. Graph interpretation
In the current section we assign a graph to a group which helps us construct the
paradoxical decompositions and compute the Tarski numbers.
Definition 4.1. Let G be a group and g = (g1 , . . . , gn ) and E = {E1 , . . . , Em } be a
finite string of elements of G and a finite partition for G, respectively. Γ = Γ(G, g, E)
is a graph constructed as follows
 The vertex set of Γ is identified with ℓ-tuples of nonnegative integers, where
|Con(g, E)| = ℓ:

V (Γ) := (aC )C∈Con(g,E) ; aC ∈ N ∪ {0} .
 There exists a directed edge from the vertex A = (aC ) to B = (bC ) only if
aC ∈ {0, 1} and there are disjoint subfamilies
C
AC
1 , . . . , AbC

(C ∈ Con(g, E))

A CONSTRUCTIVE WAY TO COMPUTE THE TARSKI NUMBER OF A GROUP

of a partition of

F

aC 6=0

15

x0 (C) such that for all C ∈ Con(g, E)
G
x0 (C) =
gA A, 1 ≤ j ≤ bC ,
A∈AC
j

for suitable subsets {gA , A ∈ AC
j }, 1 ≤ j ≤ bC , of G.
Proposition 4.2. If Γ contains adjacent vertices A = (aC )C∈Con(g,E) and B =
(bC )C∈Con(g,E) with aC ∈ {0, 1} and αC := bC −aC > 0, then G admits a paradoxical
decomposition in terms of g and E.
Proof. By the assumption for each C, bC ≥ aC + 1. In other words
(
1, if aC = 0
bC ≥
2, if aC =
6 0.
F
Hence by Definition 4.1 there exists a partition P of aC 6=0 x0 (C) with the following
properties:
C
C
C
• If aC 6= 0, there are AC
1 , A2 ⊆ P and {gA , A ∈ A1 }, {gB , B ∈ A2 } ⊆ G
such that
G
G
gB .B.
gA .A =
x0 (C) =
B∈AC
2

A∈AC
1

• If aC = 0, there are AC ⊆ P and {gD , D ∈ AC } ⊆ G such that
G
gD .D.
x0 (C) =
D∈AC

• All the above subfamilies of P are pairwise disjoint.
F
F
For convenience denote the set aC =0 x0 (C) by E. We know that G = C∈Con(g,E) x0 (C).
Then we have


G=E

G

and
G=

G

G

aC =0 D∈AC



G

G

aC 6=0

A∈AC
1

!



gD .D

G



gA .A

G

G

aC 6=0 B∈AC
2



gB .B 

which give a (not necessarily complete) paradoxical decomposition for G. To make
it complete, one can apply the proof of [7, Proposition 1.2] as usual.

Theorem 4.3. Let G be a group and g = (g1 , . . . , gn ) and E = {E1 , . . . , Em } be a
finite string of elements of G and a finite partition for G, respectively. If Eq(g, E)
has no nonnegative nonzero solution with a normal subsystem, then Γ = Γ(G, g, E)
includes vertices A = (aC )C∈Con(g,E) and B = (bC )C∈Con(g,E) with aC ∈ {0, 1} and
αC := bC − aC > 0.
P
P
Proof. Using the notations of the proof of Theorem
A = Vi′ and B = Wi′ ,
P 3.1,
are desired vertices because first, B − A > 0 and
V ′ (C) ∈ {0, 1}, and second, by
(17) they satisfy the second condition of the definition of Γ(G, g, E).


AKRAM YOUSOFZADEH

16

4.1. Diagrams associated with configuration equations. Here we present a
kind of diagram associated with configuration equations. It could be of great importance in order to reduce the complexity of the proofs in the previous section.
• Let A, B1 , . . . , Bt be subsets of Con(g, E). If there is g ∈ G and there is a
F
partition {A1 , . . . , At } for Ã = C∈A x0 (C) such that
B̃j = gAj ,

1 ≤ j ≤ t,

we use the following tree diagram
A

B1

B2

...

Bt

Clearly if D ⊆ A, and Ej = B̃j ∩ g D̃, we also have a similar diagram with
directed paths from D to E1 , . . . , Et−1 , Et .
• By the diagram
B1

B2

...

Bt

A
F
we mean A = ti=1 Bi .
• Let A, B ⊆ Con(g, E). In the sequel we denote a directed path of any kind
of above two types from A to B by [A, B]. Inductively [A, B1 , B2 , . . . , Bn ]
is a path which connects the sets A, B1 , B2 , . . . , Bn through the sequence
of n single paths [A, B1 ], [B1 , B2 ], . . . , [Bn−1 , Bn ].
In the proof of Theorem 3.1 according to the normality condition we have the
possibility to borrow the configurations in At \ Pt from B1 , . . . , Bt−1 so that the
(not necessarily disjoint) subsets A1 , . . . , Ap turn into disjoint subsets P1 , . . . , Pp
and it is enough for us to construct a paradoxical decomposition of G and to get
an upper bound for τ (G). We Apply the above diagrams to make the proof of
that theorem more clear to the reader. Using the same notations, by (15) we
F
F
F
have P̃1 = Ã1 = ġ1−1 B̃1 = ġ1−1 Q̃1 ġ1−1 D̃12 · · · ġ1−1 D̃1p . So, there are p directed
F
paths from P1 = A1 to D12 , . . . , D1p and Q1 . Also D̃12 P̃2 = Ã2 = ġ2−1 B̃2 =
F
F
F
ġ2−1 Q̃2 ġ2−1 D̃23 · · · ġ2−1 D̃2p . So, there are p − 1 directed paths from D12 to
D23 , . . . , D2p and Q2 and the same number of paths from P2 to D23 , . . . , D2p and
Q2 .

A CONSTRUCTIVE WAY TO COMPUTE THE TARSKI NUMBER OF A GROUP

P1

Q1

p

D1

...

2
D1

A2

2
D1

Q2

p

D2

···

3
D2

17

P2

A2

Gluing these diagrams we obtain two paths from D12 and P2 to Q2 and so on.
P1

Q1

p

D1 ...

3
D1

P2

2
D1

A2

Q2

D2

P3

p

···

3
D2

A3

..
.
Ap

Qp



Pp

AKRAM YOUSOFZADEH

18

Our diagram contains the following 2p − 1 paths

[P1 , Q1 ],
[P1 , D12 , A2 , Q2 ], [P2 , A2 , Q2 ],
[P1 , D13 , A3 , Q3 ], [P1 , D12 , A2 , D23 , A3 , Q3 ], [P2 , A2 , D23 , A3 , Q3 ], [P3 , A3 , Q3 ],
..
.
[P1 , D1p , Ap , Qp ], . . . , [P1 , D12 , A2 , D2p , Ap , Qp ], . . . , [Pp , Ap , Qp ].

Depending onFthe members of Q1 , . . . , Qp , these paths can be continued one more
p
step. In fact t=1 Pt admits a partitionFwith at most 2p − 1 pieces such that with
suitable coefficients construct the sets C∈Qt x0 (C), 1 ≤ t ≤ p, separately (see
proof of Theorem 3.1). 2t−1 pieces in the partition are used to make Q̃t . These
pieces are divided into 2t−1 |Qt | new pieces to construct all the sets x0 (C), C ∈ Qt .
To have a paradoxical P
decomposition each x0 (C),
Pp C ∈ Con(g, E) must be obtained
p
at least two times. If t=1 Vt′ (C) = 1, then t=1 Wt′ (C) ≥ 2. In other words, C
belongs to at least two Qt s and it is done. Otherwise, C may appear in only one
Pp
′
Qt and we have to add the single set {C,
= 0˜} to the pieces of our
t=1
PpVt (C)
t−1
paradoxical
decomposition. Therefore τ (G) ≤ t=1 2 |Qt |+1. It is to be noted
Pp
that t=1 2t−1 |Qt | is the maximum possible number of mentioned paths.
Naturally to make this observation more accurate, we have to choose a procedure
in which the number of pieces in the paradoxical decomposition is as small as
possible. This process depends directly on the set of configurations given in the
statement of problem. We explain it in the next subsection.

4.2. Examples. We end the paper with some examples. Our examples will be
based on the sets of configurations instead of the elements of the group. As the
paradoxical decomposition of a group is not unique, different diagrams also exist.
One can find a more precise Tarski number’s upper bound by counting the paths
from the top to the bottom in a minimal diagram (a diagram with minimum number
of paths). It is noticeable that a minimal diagram is not necessarily a connected
one.

Example 4.4. Let C1 = (1, 2, 3, 2), C2 = (1, 3, 1, 3), C3 = (2, 1, 2, 2), C4 =
(3, 3, 1, 2) and C5 = (3, 3, 2, 1) be configurations corresponding to the configuration

A CONSTRUCTIVE WAY TO COMPUTE THE TARSKI NUMBER OF A GROUP

19

pair (g, E) of a group G. Consider the following equations
X

X

fC =

fC

x0 (C)⊆E1

X

fC =

fC ,

x2 (C)⊆E2

X

fC =

fC

x2 (C)⊆E2

x1 (C)⊆E2

X

fC ,

x0 (C)⊆E1

x0 (C)⊆E2

X

X

fC =

x3 (C)⊆E1

X

fC

x0 (C)⊆E1

x3 (C)⊆E1

X

X

fC =

x1 (C)⊆E1

X

fC ,

x0 (C)⊆E1

x1 (C)⊆E1

X

X

fC =

fC =

x3 (C)⊆E3

X

fC

x0 (C)⊆E3

which are the next equations, respectively
fC3 =fC1 + fC2 ,
fC3 =fC1 + fC2 ,
fC5 =fC3 ,
fC5 =fC3 ,
fC3 =fC3 + fC5 ,
fC1 =fC3 + fC5 ,
fC2 =fC4 + fC5 .


0 0
 0 0

 0 0

Then A = 
 0 0
 0 0

 1 0
0 1
sponding coefficient

1 0 0
1 0 0
0 0 1
0 0 1
1 0 0
0 0 0
0 0 0
matrices.





1 1 0 0 0

 1 1 0 0 0



 0 0 1 0 0


 and B =  0 0 1 0 0



 0 0 1 0 1



 0 0 1 0 1
0 0 0 1 1
Setting π = (2 7)(4 6), one has


1 0 −1 0 0
 1 0 −1 1 0 


 0 0 0 1 0 



T Pπ (B − A) − Pπ+ A = 
 0 0 0 1 1 .
 0 0 1 1 1 


 0 0 1 1 1 
1 1 0 1 1







 are the corre




AKRAM YOUSOFZADEH

20

Therefore this system is normal. The equations corresponding to T Pπ (B − A)
are
fC3 =fC1 + fC2 ,
fC2 =fC4 + fC5 ,
fC5 =fC3 ,
fC1 =fC3 + fC5 ,
fC3 =fC3 + fC5 ,
fC5 =fC3 ,
fC3 =fC1 + fC2 .
We use the notations of the proof of Theorem 3.1. In this example p = 7, A1 =
{C3 }, A2 = {C2 }, A3 = {C5 }, A4 = {C1 }, A5 = {C3 }, A6 = {C5 }, A7 = {C3 },
B1 = {C1 , C2 }, B2 = {C4 , C5 }, B3 = {C3 }, B4 = {C3 , C5 }, B5 = {C3 , C5 }, B6 =
{C3 }, B7 = {C1 , C2 }. The initial diagram is
C3

C2

C1

C5

C2

C1

C3

C4

C5

C3

C3

C5

C5

C3

C5

C3

C3

C1

C2

Applying the process in the proof of Theorem, we have P1 = {C3 }, P2 = {C2 }, P3 =
{C5 }, P4 = {C1 }, P5 = ∅, P6 = ∅, P7 = ∅, Q1 = {C1 , C2 }, Q2 = {C4 }, Q3 = ∅, Q4 =
{C3 , C5 }, Q5 = {C5 }, Q6 = {C3 }, Q7 = {C1 , C2 }. The associated diagram is
C3

C1

C2

C2

C4

C5

C1

C5

C3

C3

C3

C3

C5

C1

C2

C5

A CONSTRUCTIVE WAY TO COMPUTE THE TARSKI NUMBER OF A GROUP

21

The condition of normality enables us to have disjoint subsets P1 , . . . , Pp which
produce Con(g, E) two times (see proof of Theorem 3.1). By Corollary 3.4, τ (G) ≤
(ℓ − 1)(2p − 1) = 508 (ℓ = 5 and p = 7). This is not a very accurate upper bound.
Changing the diagram to a minimal one, helps us compute the most precise bound
τ (G). Look at the following diagram
C3

C2

C5

C1

C4

C3

C3

C5

C3 , C5

C3

C1 , C2

F
F
According to (5) we haveFg1 x0 (C3 ) = x0 (C1 ) x0 (C2 ), g3 F
x0 (C2 ) = x0 (C4 ) x0 (C5 ),
g2−1 g1 x0 (C1 ) = x0 (C3 ) x0 (C5 ), g2−1 x0 (C3 ) = x0 (C3 ) x0 (C5 ) and g3 x0 (C5 ) =
x0 (C3 ).
F
F
F
Then x0 (C3 ) = ∆1 ∆2 ∆3 ∆4 , where
∆1 = g1−1 g3−2 x0 (C3 )

∆2 = g1−1 g3−1 x0 (C4 )


[
∆3 = g1−2 g22 x0 (C3 ) x0 (C5 )


[
∆4 = g1−2 g2 g3−1 g1−1 x0 (C1 ) x0 (C2 ) .

Therefore it is obvious that

and besides

G

(G \ x0 (C3 ))
G
= g3 g1 ∆2 (G \ x0 (C3 ))

G = x0 (C3 )

G = g32 g1 ∆1

G

g2−2 g12 ∆3

G

g1 g3 g2−1 g12 ∆4 .

In other words, we have a paradoxical decomposition consisting of 5 pieces. Thus
τ (G) ≤ 5. This number can be obtained from the above diagram by counting the
paths from the beginning points to the end points and adding the result by 1. The

AKRAM YOUSOFZADEH

22

suitable part of Γ(G, g, E) corresponding to this example is
(0, 0, 1, 0, 0)

(1, 1, 2, 1, 1)
We have a very special case of Theorem 3.1 which eventuates a result for computing the Tarski number. We use the notations of section 3.
Pp
Theorem 4.5. Suppose that i=1 (Wi − Vi ) = (1, 1, . . . , 1) and there exists a permutation matrix Pπ such that the first p − 1 rows of Pπ B − Pπ+ A have nonnegative
entries. Then τ (G) ≤ 1 + |Aπ(1) | + ℓ.
Proof. The assumption says that for 1 ≤ i ≤ n, Aπ(i+1) ⊆ Bπ(i) . Set Aπ(n+1) = ∅,
−1
−1
−1
hi = ġπ(1)
.ġπ(2)
. . . . .ġπ(i)
and Ri = hi (B̃π(i) \ Ãπ(i+1) ), for 1 ≤ i ≤ p. By induction
on p we see
Ãπ(1) =

p
G

Ri .

i=1

Since by assumption
F

Pp

i=1 (Wi

− Vi ) = (1, 1, . . . , 1), the equations

C∈(Bπ(i−1) \Aπ(i) )

x0 (C) = h−1
i Ri ,

(1 ≤ i ≤ p)

define a paradoxical decomposition. On the other hand we have
n
X
|Bπ(i−1) \ Aπ(i) |) + 1
τ (G) ≤|Bπ(p) | + (
i=2

n
X
|Bπ(i) − Aπ(i) |) + |Aπ(1) | + 1
=(
i=1

=ℓ + |Aπ(1) | + 1.


In the special case where G does not contain the free group on two generators
and ℓ = 3 and |Aπ (1)| = 1 we have τ (G) = 5.
Example 4.6. Let Con(g, E) = {(1, 2, 2, 2), (2, 1, 2, 1), (2, 2, 1, 1)}. Then τ (G) ≤ 5.
A minimal diagram associated with Eq(g, E) is

A CONSTRUCTIVE WAY TO COMPUTE THE TARSKI NUMBER OF A GROUP

23

C1

C2

C3

C1

C2

C3

C1

C1

C2

C3

C1

The number of paths from the top to the bottom is 4. These paths are [C1 , C3 ],[C1 , C2 , C1 , C2 , C1 ],
[C1 , C2 , C1 , C3 , C1 , C2 ] and [C1 , C2 , C1 , C3 , C1 , C3 , C1 ]. Therefore τ (G) ≤ 4 + 1 = 5.
Indeed according to (5) we have
x0 (C1 ) =g3 x0 (C2 ) ∪ g3 x0 (C3 )
x0 (C2 ) =g1−1 x0 (C1 )
x0 (C3 ) =g2 x0 (C1 ).
Define
∆1 =g3 g1−1 g3 g1−1 g3 x0 (C2 ),
∆2 =g3 g1−1 g3 g1−1 g3 g2 x0 (C1 , )
∆3 =g3 g1−1 g3 g2 x0 (C1 ),
∆4 =g3 x0 (C3 ),
∆5 =x0 (C2 ) ∪ x0 (C3 ).

AKRAM YOUSOFZADEH

24

Then x0 (C1 ) =

F4

∆i . So, G =

F5

∆i and finally we have
G
G =g2−1 g3−1 g1 g3−1 ∆3 g3−1 g1 g3−1 g1 g3−1 ∆1 g3−1 ∆4
G
G =g2−1 g3−1 g1 g3−1 g1 g3−1 ∆2
e∆5 ,
i=1

i=1

G

where e is the identity element of G. We have a complete paradoxical decomposition
with five pieces. So, τ (G) ≤ 5.
Example 4.7. [8] Let F2 = ha, bi be the free group with generators a and b and
identity element e. Suppose that g = (a, b) and E = {E1 , E2 , E3 }, where
E1 = {x, x is a reduced word starting with a},
E2 = {x, x is a reduced word starting with b} and
F
E3 = {x, x is a reduced word starting with a−1 or b−1 } {e}.

Then Con(g, E) = {C1 , . . . , C7 }, where C1 = (1, 1, 2), C2 = (2, 1, 2), C3 = (3, 1, 2), C4 =
(3, 2, 2), C5 = (3, 3, 2), C6 = (3, 1, 3) and C7 = (3, 1, 1). One can see that this example satisfies that condition of the pervious theorem. Consider the following
configuration equations
X
X
X
X
fC
fC =
fC and
fC =
x0 (C)⊆E2

x1 (C)⊆E1

x0 (C)⊆E1

x2 (C)⊆E2

i.e.

fC1 = fC1 + fC2 + fC3 + fC6 + fC7 and fC2 = fC1 + fC2 + fC3 + fC4 + fC5 ,
which imply that each fC is zero. The corresponding diagram is
C1

C7

C6

C3

C2

C1

C1

C2

C3

C4

C5

Put A = a−1 x0 (C1 ), B = b−1 a−1 [∪5i=1 x0 (Ci )], C = a−1 (x0 (C6 ) ∪ x0 (C7 )) and
M = F2 \ x0 (C1 ). Then we have the non-complete paradoxical decomposition
F2 = A ⊔ B ⊔ C ⊔ M ⊔ a−1 x0 (C3 ) = eM ⊔ aA = abB ⊔ aC.
Hence τ (F2 ) = 4.
We now summarize what we have done for estimating the upper bound of the
Tarski number of a group.
(1) Change the order of the configuration equations based on the permutation
matrix in the definition of the normality condition.

A CONSTRUCTIVE WAY TO COMPUTE THE TARSKI NUMBER OF A GROUP

25

(2) Define the initial diagrams consisting of p connected components.
(3) Make each set in the top of the above diagrams disjoint from the previous
ones by borrowing their intersection from the sets in the bottom of the
former diagrams.
(4) Glue these diagrams as it is explained in subsection 4.1.
(5) Find the configurations of the top sets of the initial diagrams in the bottom
of the last gluing diagram.
(6) Count all the directed pats from top to the bottom. This number plus one
is an upper bound for τ (G).
To get the best bound for τ (G) using this procedure, we borrow the maximum
number of configurations that we can get from the former bottom sets (not only
the intersections). It is applied in the examples.
Definition 4.8. Let m, n ∈ N. A set of (n+1)-tuples C = {(ci0 , . . . , cin ), 1 ≤ i ≤ ℓ}
with 1 ≤ cij ≤ m and
∪nj=1 {cij } = {1, . . . , m},

(i = 1, . . . , ℓ)

is called a pre-configuration set if there exist a group G, a string g of elements of
G and a partition E of G such that Con(g, E) = C.
In [5] the authors give examples of groups with Tasrki numbers 5 and 6. Now
the question is whether we can construct such groups using configurations. Responding to this question depends on knowing that given well-behaved sets are
pre-configuration ones. In particular
Question 4.9. Is C = {(1, 2, 3, 2), (1, 3, 1, 3), (2, 1, 2, 2), (3, 3, 1, 2), (3, 3, 2, 1)} a preconfiguration set (see Example 4.4)?
References
[1] A. Abdollahi, A. Rejali and G. A. Willis, Group properties characterized by configuration,
Illinois J. Mathematics, 48 (2004) No. 3, 861–873.
[2] A. Abdollahi, A. Rejali and A. Yousofzadeh, Configuration of nilpotent groups and isomorphism, J. Algebra Appl, 8, No. 3 (2009) 339–350.
[3] T. G. Ceccherini-Silberstein, R. I. Grigorchuk and P. de la Harpe, Amenability and paradoxical decompositions for pseudogroups and for discrete metric spaces, Proc. Steklov. Inst.
Math. 224 (1999), 57–97.
[4] G. B. Dantzig and M. N. Thapa, Linear Programming 2: Theory and Extensions. SpringerVerlag, New York, 2003.
[5] M. Ershov, G. Golan and M. Sapir, The Tarski numbers of groups, Adv. Math. 284 (2015)
21–53.
[6] A. l. T. Paterson, Amenability Mathematical Surveyes and Monographs., 29, American Mathematical Society, Providence, RI, 1988.
[7] A. Rejali and A. Yousofzadeh, Configuration of groups and paradoxical decompositions, Bull.
Belg. Math. Soc. Simon Stevin 18 (2011) 157–172.
[8] J. M. Rosenblatt and G. A. Willis, Weak convergence is not strong for amenable groups,
Canad. math. Bull, 44 (2001) No 2, 231–241.
[9] M. Sapir, Combinatorial algebra: Syntax and Semantics. Springer International Publishing,
Suitzerland, 2014.
[10] S. Wagon, The Banach-Tarski Paradox., vol. 24 of Encyclopedia of Mathematics and its
Applications, Cambridge University Press, Cambridge-New York, 1985.
[11] A. Yousofzadeh, A. Tavakoli and A. Rejali, On configuration graph and paradoxical decomposition,J. Algebra. Appl, 13, No. 2 (2014), 1350086 (11 pages).
E-mail address: ayousofzade@yahoo.com

