PharmD Guillaume Monneret
email: guillaume.monneret@chu-lyon.fr

Brief Report

Marked elevation of human circulating CD4؉CD25؉ regulatory T cells in sepsis-induced immunoparalysis

Guillaume Monneret, PharmD, PhD; Anne-Lise Debard, PharmD; Fabienne Venet; Julien Bohe, MD; Olivier Hequet, MD; Jacques Bienvenu, PharmD, PhD; Alain Lepape, MD T he concept of immunoparalysis recently has been proposed to explain the failure of 20 yrs of clinical trials using antiinflammatory drugs in septic shock. In fact, the initial inflammatory stage of sepsis is rapidly counterbalanced by an antiinflammatory response, which may adversely affect immune functions [START_REF] Kox | Immunomodulatory therapies in sepsis[END_REF][START_REF] Munford | Normal responses to injury prevent systemic inflammation and can be immunosuppressive[END_REF]. This secondary immunoparalysis state is first characterized by a monocytic deactivation: Phagocytic function, proinflammatory cytokine release, and antigenpresenting capacity (likely due to a decreased expression of human leukocyte antigen [HLA]-DR) are severely depressed [START_REF] Kox | Immunomodulatory therapies in sepsis[END_REF][START_REF] Munford | Normal responses to injury prevent systemic inflammation and can be immunosuppressive[END_REF]. On the other hand, T cells become hyporesponsive in terms of proliferation and turn toward a type 2 profile: Interleukin (IL)-4, tumor growth factor-␤, and IL-10 productions are increased, whereas those of IL-12 and interferon-␥ are suppressed [START_REF] Kox | Immunomodulatory therapies in sepsis[END_REF][START_REF] Munford | Normal responses to injury prevent systemic inflammation and can be immunosuppressive[END_REF]. Importantly, the persistence of immunoparalysis, as monitored by measuring monocytic HLA-DR expression, correlates with an increased risk for fatal outcome [START_REF] Docke | Monocyte deactivation in septic patients: Restoration by IFN-gamma treatment[END_REF].

Recently, human peripheral blood CD4ϩCD25ϩ T cells have been characterized as suppressor T cells (4 -5). The mechanism by which these cells mediate their effects remains under debate as well as the definition of their cellular targets. It is reported they act on T cells by inducing their anergy through a cellcontact mechanism in which CTLA-4 would be involved [START_REF] Shevach | Certified professionals: CD4ϩCD25ϩ suppressor T cells[END_REF]. On the other hand, CD4ϩCD25ϩ T cells also are thought to produce IL-10 and tumor growth factor-␤ and to suppress interferon-␥ production [START_REF] Shevach | Certified professionals: CD4ϩCD25ϩ suppressor T cells[END_REF]. In line with these data, Suto et al. [START_REF] Suto | Role of CD4ϩCD25ϩ regulatory T cells in TH2 cell-mediated allergic inflammation in the airways[END_REF] suggested that regulatory T cells act by inhibiting the activation of Th1 T cells. Accordingly, Zelenika et al. [START_REF] Zelenika | Regulatory T cells overexpress a subset of TH2 gene transcripts[END_REF] showed that CD4ϩCD25ϩ T cells express a subset of Th2 gene transcripts, whereas Iellem et al. ( 9) described a specific expression of type 2 chemokines receptor on their surface.

Given these properties, we hypothesized that CD4ϩCD25ϩ might have a kind of type 2 role to play in sepsis induced-immunoparalysis. The present study was designed to determine whether CD4ϩCD25ϩ T cells are increased during the stage of immunoparalysis in patients with septic shock.

STUDY DESIGN

Patients. The study group consisted of 16 patients (mean age, 58 yrs; male/ female ratio, 14/2) with septic shock according to the diagnostic criteria for septic shock of the American College of Chest Physicians/Society of Critical Care Medicine [START_REF] Bone | Definitions for sepsis and organ failure and guidelines for the use of innovative therapies in sepsis. The ACCP/SCCM Consensus Conference Committee[END_REF]. Severity was assessed by the Simplified Acute Physiology Score II [START_REF] Gall | A new Simplified Acute Physiology Score (SAPS II) based on a European/North American multicenter study[END_REF]; mean admission score was 47 (range, 24 -70). Mortality was defined as death occurring within 28 days after diagnosis. Because we focused our interest on the secondary stage (immunoparalysis) of septic shock, we excluded patients who did not survive Ͼ48 hrs after being admitted to intensive care units. None of the patients received corticosteroids as therapy for septic shock. Most patients presented with no preexisting underlying disease, and only two patients (one survivor, one nonsurvivor) presented with metastatic cancer. To provide a panel of control values, we also included 36 healthy individuals from our laboratory (age 22-48). Cell phenotyping in whole blood was performed as regularly as possible during 10 days after the onset of shock when residual blood was available after completing routine follow-up performed in our intensive care units (details in sampling are given in Table 1), in accordance with the human experimentation guidelines for clinical research of our institute.

Flow Cytometry and Cell Isolation. Flow cytometric (EPICS XL, Beckman-Coulter, Hialeah, FL) expression of cellsurface markers was assessed on peripheral whole blood collected in EDTA anticoagulant tubes. Monocytes were characterized by expression of CD14 ( 12) and regulatory T cells by coexpression of CD3, CD4, and CD25 (4 -5). A number of monoclonal antibodies and their respective isotype controls were used according to the manufacturer's recommendations: PC5-labeled anti-CD45, fluorescein isothiocyanate-labeled anti-CD14, ECDlabeled anti-CD3, PE-labeled anti-CD25, ECD-labeled anti-CD45RO, PC5-labeled anti CD69 (Immunotech, Marseille, France), PE-labeled anti-HLA-DR, Cy-Chrome-labeled anti-CTLA-4, PE-labeled anti-CD25 (Becton Dickinson-Pharmingen, San Jose, CA). Results are expressed as mean Ϯ SEM as percentages of HLA-DR-positive monocytes out of total monocyte population, as percentages of CD25-positive cells out of total CD4-T cell population (CD3ϩCD4ϩ), and as percentages of CD69-, CD45RO-, or CTLA-4-positive cells out of total T regulatory population (CD3ϩCD4ϩCD25ϩ). The different thresholds for positivity were defined with the respective isotype controls. Plate-bound anti-CD3 and soluble anti-CD28 (Becton Dickinson-Pharmingen) were used for polyclonal activation of T cells. For CD4ϩCD25ϩ isolation, CD4ϩ T cells were first isolated from peripheral blood mononuclear cells with a negative CD4ϩ T cell isolation kit (Miltenyi Biotec, Bergisch Gladbach, Germany). Then, regulatory T lymphocytes were obtained after an additional purification by using CD25 microbeads (Mil-tenyi Biotec) as previously described (4). Purity was assessed by flow cytometry (Ͼ90%) by using the anti-CD25 monoclonal from Becton Dickinson.

Statistical Study. Due to the sample size and some missing data at certain time points in the follow-up, the comparison between groups was made with a nonparametric Mann Whitney test, whereas the Wilcoxon paired test was used to assess daily individual variation in CD4ϩCD25ϩ percentages. We considered p Ͻ .05 to be significant, without correction of the number of tests performed.

RESULTS AND DISCUSSION

In the first days following septic shock, the expression of HLA-DR on monocytes was severely reduced in septic patients (Table 1). This illustrated the rapid onset of immunoparalysis. Mortality defined as death occurring within 28 days after diagnosis was 56%. When survivors and nonsurvivors were compared, there was no difference in HLA-DR monocytic expression until day 5. However, at days 7-10, we found higher values in survivors, suggesting an ongoing recovery of their immunologic functions (Table 1). These data agree with several studies which have shown that lower expression of monocytic HLA-DR in the first days after diagnosis is associated with a poor prognosis (1-3). We extended these results by illustrating that the recovery observed at days 7-10 in survivors was not found in nonsurvivors.

Rapidly following the onset of septic shock, we observed a progressive and significant elevation of CD4ϩCD25ϩ T cells above control values (Table 1 and Fig. 1). The highest values were found at day 5 (30 Ϯ 2; median, 27; range, 23-42), which was significantly increased compared with control values (p Ͻ .001). Because CD25 is the IL-2 receptor ␣ chain, we verified that this increase in CD4ϩCD25ϩ cells was not due to a sepsis-induced up-regulation of CD25 (Fig. 2). As expected, the majority of CD4ϩCD25ϩ cells did not express a phenotype of recently activated T cells since they express low levels of CD69 (11 Ϯ 0.6%) and were CD45RO positive (86 Ϯ 3%), which is similar to the human CD4ϩCD25ϩ regulatory T-cell phenotype described by others [START_REF] Dieckmann | Human CD4(ϩ)CD25(ϩ) regulatory, contact-dependent T cells induce Interleukin1producing, contact-independent type 1-like regulatory T cells[END_REF][START_REF] Jonuleit | Infectious tolerance: Human CD25(ϩ) regulatory T cells convey suppressor activity to conventional CD4(ϩ) T helper cells[END_REF]. Moreover, after activation with plate-bound anti-CD3 plus soluble anti-CD28, most CD4ϩ cells became strongly CD25-CD69 double positive (Ͼ60%), and CD25 expression levels after activation were higher compared with those measured on CD4ϩCD25ϩ cells isolated in patients (Fig. 2B). When expressed as means of fluorescence, CD25 levels were at 11 Ϯ 1 and 43 Ϯ 4 in patients' cells and CD3-activated cells, respectively. Together, these data strongly indicated that we were identifying regulatory T cells (CD25low, CD69Ϫ) rather than recently activated T cells (CD25high, CD69ϩ). Besides, the hypothesis of an activated T population during immuno-paralysis as illustrated by the low level of monocytic HLA-DR expression seems to be very unlikely. That would suggest the coexistence at the same time of a two-cell population with phenotypes corresponding to totally opposite stages of immune responses. We confirmed this whole blood phenotyping after purifying CD4ϩCD25ϩ T cells by using a magnetic cell separation system. In three additional donors, we obtained purified cells that were mainly positive for CD45RO (Ͼ94%) and negative for CD69 (Ͻ10%) (Fig. 2C).

Interestingly, the elevation of CD4ϩCD25ϩ T cells was similar until day 5 in both survivors and nonsurvivors, suggesting a normal homeostatic mechanism. Afterward, however, a difference was observed (Table 1). At days 7-10, in survivors, the percentage of CD4ϩCD25ϩ T cells was 24%, whereas in sharp contrast, these cells still represented 38% of total CD4ϩ T lymphocytes in nonsurvivors.

Considering that regulatory T cell effects are believed to be mediated, for the most part, by CTLA-4, we also looked at its expression in ten donors and ten patients at days 7-10. We found that CTLA-4 levels were increased in cells from septic patients (15 Ϯ 4; median, 10; range, 5-50) compared with control values (5 Ϯ 1; median, 6; range, 2-8; p Ͻ .005). Due to the small number of patients, we could not demonstrate a difference between survivors and nonsurvivors regarding CTLA-4 expression. Even if we found higher values in nonsurvivors than in survivors (Table 1), this point remains to be investigated in a larger study to confirm the idea that elevated CTLA-4 expression is associated with patients who are not going to survive.

In total, the present study describes that circulating CD4ϩCD25ϩ T cells are increased during sepsis-induced immunoparalysis. Furthermore, the persistence of elevated percentages of these cells 10 days after the onset of septic shock was found in nonsurviving patients with low monocytic HLA-DR. To our knowledge, this is the first description of such an elevation of circulating CD4ϩCD25ϩ T cells in a human disease context. It provides an additional argument for rethinking the pathophysiology of septic shock. It seems likely that homeostatic modulatory mechanisms rap- idly occur after the onset of shock to counterbalance the initial inflammatory response. Nevertheless, in some patients, this may induce a prolonged and severe immunoparalysis that is associated with poor prognosis. A larger study is now needed to fully support this first description of elevated CD4ϩCD25ϩ in sepsisinduced paralysis and to investigate whether CD4ϩCD25ϩ may have a direct role in the different immunologic processes inducing immunoparalysis after a septic shock.

Objective:

  Immunoparalysis has recently emerged as a possible cause explaining the failure of clinical trials in septic shock. Because human peripheral blood CD4؉CD25؉ T cells have been characterized as suppressor T cells, we hypothesized they might be increased in sepsis-induced immunoparalysis. Design: Prospective, observational, clinical study. Setting: Adult intensive care units in a university hospital. Subjects: Patients with septic shock (n ؍ 16) and healthy individuals (n ؍ 36). Interventions:None. Measurements and Main Results: In patients with septic shock (mortality rate at 28 days, 56%; mean admission Simplified Acute Physiology Score II, 47), we first illustrated immunoparalysis by showing a severe diminished monocytic human leukocyte antigen (HLA)-DR expression. Afterward, compared with control values, we found in these patients a marked elevation of circulating CD4؉CD25؉ T cells that were also CD45RO؉ and CD69-and overexpressed CTLA-4. Importantly, nonsurvivors (n ؍ 9) presented prolonged lower monocytic HLA-DR expression and higher percentage of CD4؉CD25؉ T-suppressor T cells. Conclusions: These data support the concept that the persistence of a pronounced immunoparalysis after septic shock is associated with a poor outcome. Whether CD4؉CD25؉ T cells directly participate in sepsis-induced immunoparalysis remains to be investigated. (Crit Care Med 2003; 31:2068 -2071) KEY WORDS: human leukocyte antigen-DR; immunoparalysis; T lymphocytes; CD4؉CD25؉ T cells; septic shock

  Changes of human lymphocyte antigen-reaction of degeneration (HLA-DR) expression on monocytes (percent of monocytes expressing HLA-DR), changes of CD4ϩCD25ϩ suppressor T cells (percent of total CD4 positive T cell population), and expression of CTLA-4 on CD4ϩCD25ϩ T (percent of CD4ϩCD25ϩ cells expressing CTLA-4) are expressed as mean Ϯ SE, median, [range of values], and number of samples, in patients who survived (n ϭ 7) or died (n ϭ 9). a p Ͻ .05 (Mann Whitney test) between survivors and nonsurvivors.

Figure 1 .

 1 Figure 1. Elevation of CD4ϩCD25ϩ T cells in patients after septic shock. Individual values were taken into account when paired samples were available at the two time points considered: day 1 to day 3 (n ϭ 11) and day 3 to day 5 (n ϭ 9). Horizontal lines represent medians. The Wilcoxon paired test was used to assess significance between days.

Figure 2 .

 2 Figure 2. Human circulating CD4ϩCD25ϩ T cells in sepsis-induced immunoparalysis express low levels of CD25 and do not express CD69. A, identification of CD4ϩCD25ϩ T cells in whole blood in a representative patient during immunoparalysis (upper panel, patient ϩ PE-isotype control; lower panel, patient ϩ PE-anti-CD25). Cells were previously gated on their scatter characteristics and CD3 positive expression. B, CD4 T cells before (upper panel) and after (lower panel) activation with plate-bound anti-CD3 and anti-CD28 during 24 hrs (one representative experiment of four). Cells were previously gated on their CD3-CD4 characteristics. C, after purification, CD4ϩCD25ϩ T cells (ungated) express CD45RO (upper panel) and do not express CD69 (lower panel), one representative experiment of three.

Table 1 .

 1 Immunomonitoring of patients with septic shock

		Day 1	Day 3	Day 5	Days 7-10	Control Values
	HLA-DRϩ (% of monocytes)
	Survivors	29 Ϯ 5	30Ϯ 5	42 Ϯ 6	67Ϯ 2 a
		27	30	38	70
		[16-45]	[11-54]	[27-70]	[51-71]	89 Ϯ 1
		n ϭ 6	nϭ 7	nϭ 7	nϭ 7	9 0
	Nonsurvivors	23 Ϯ 4	17Ϯ 3	27 Ϯ 4	2 9Ϯ 3	(from Ref. 12)
		24	18	27	25
		[8-38]	[4-33]	[10-43]	[21-48]
		n ϭ 5	nϭ 8	nϭ 7	nϭ 9
	CD4ϩCD25ϩ (% of CD4ϩ)
	Survivors	23 Ϯ 3	24Ϯ 3	30 Ϯ 3	24Ϯ 3 a
		21	24	30	24
		[15-32]	[16-35]	[24-41]	[12-32]	20 Ϯ 1
		n ϭ 6	nϭ 7	nϭ 6	nϭ 7	1 8
	Nonsurvivors	23 Ϯ 4	25Ϯ 5	29 Ϯ 3	3 8Ϯ 5	[12-26]
		18	22	26	37	n ϭ 36
		[15-39]	[10-57]	[23-42]	[19-55]
		n ϭ 6	nϭ 8	nϭ 5	nϭ 9
	CTLA-4 (% of CD4ϩCD25ϩ)
	Survivors				8 Ϯ 1
		-	-	-	8
					[6-10]	5 Ϯ 1
					n ϭ 4	6
	Nonsurvivors				19 Ϯ 7	[ 2 -8]
		-	-	-	11	n ϭ 10
					[5-50]
					n ϭ 6

Downloaded from http://journals.lww.com/ccmjournal by BhDMf5ePHKav1zEoum1tQfN4a+kJLhEZgbsIHo4XMi0hCy wCX1AWnYQp/IlQrHD3i3D0OdRyi7TvSFl4Cf3VC4/OAVpDDa8K2+Ya6H515kE= on 04/12/2023

Crit Care Med 2003 Vol. 31, No. 7 Downloaded from http://journals.lww.com/ccmjournal by BhDMf5ePHKav1zEoum1tQfN4a+kJLhEZgbsIHo4XMi0hCy wCX1AWnYQp/IlQrHD3i3D0OdRyi7TvSFl4Cf3VC4/OAVpDDa8K2+Ya6H515kE= on 04/12/2023

ACKNOWLEDGMENTS

This study was conducted thanks to the logistic and methodological support from the Centre d'Investigation Clinique (Clinical Research Centre) of INSERM and Hospices Civils de Lyon. We also thank J. Kingsley for his great help in preparing the manuscript and C. Fernandez, M. A. Guinand, and M. C. Gutowski for technical assistance in flow cytometric measurement.


Edouard Feingesicht

DEHORNOY'S CLASS AND SYLOWS FOR SET-THEORETICAL SOLUTIONS OF THE YANG-BAXTER EQUATION

Keywords: 2020 Mathematics Subject Classification. 16T25, 20N02, 20C10 Yang-Baxter equation, Garside monoid, Cycle set, Monomial representation, Sylow, Zappa-Szép

We explain how the germ of the structure group of a cycle set decomposes as a product of its Sylow-subgroups, and how this process can be reversed to construct cycle sets from ones with coprime classes. We study the Dehornoy's class associated to a cycle set, and conjecture a bound that we prove in a specific case. The main tool used is a monomial representation, which allows for intuitive, short and self-contained proofs, in particular to easily re-obtain previously known results (Garsideness, I-structure, Dehornoy's class and germ, non-degeneracy of finite cycle sets).

Introduction

In 1992 Drinfeld ([11]) posed the question of classifying set-theoretical solutions of the (quantum) Yang-Baxter equation, given by pairs (X, r) where X is a set, r : X × X → X × X a bijection satisfying r 1 r 2 r 1 = r 2 r 1 r 2 where r i acts on the i and i + 1 component of X × X × X. In [START_REF] Etingof | Set-Theoretical Solutions to the Quantum Yang-Baxter Equation[END_REF], the authors propose to study solutions which are involutive (r 2 = id X×X ) and non-degenerate (if r(x, y) = (λ x (y), ρ y (x)) then for any x ∈ X, λ x and ρ x are bijective). Since then, many advances have been made on this question and objects introduced: structure group ( [START_REF] Etingof | Set-Theoretical Solutions to the Quantum Yang-Baxter Equation[END_REF]), I-structure ( [START_REF] Gateva-Ivanova | Semigroups of I-Type[END_REF]), etc. Many equivalent objects are known, but in particular here we are interested in cycle sets, introduced by Rump ( [START_REF] Rump | A Decomposition Theorem for Square-Free Unitary Solutions of the Quantum Yang-Baxter Equation[END_REF]). Dehornoy ([7]) then studied the structure group (from cycle sets) seen from a Garside perspective (divisibility, word problem, ...), he then concludes with a faithful representation, which will be the base of this article. Starting from this representation, we retrieve most of Dehornoy's results in simpler, shorter and self-contained proofs, and other well known results (I-structure, non-degeneracy of finite left-non-degenerate involutive solutions of [START_REF] Rump | A Decomposition Theorem for Square-Free Unitary Solutions of the Quantum Yang-Baxter Equation[END_REF]). Then we study finite quotient defined through an integer called the Dehornoy's class of the solution, those quotients are called germs because they come with a natural way to recover the structure monoid and its Garside structure. We state the following conjecture on Dehornoy's class (Conjecture 3.6):

Conjecture. Let S be a cycle set of size n. The Dehornoy's class d of S is bounded above by the "maximum of different products of partitions of n into distinct parts" and the bound is minimal, i.e.

d ≤ max k i=1 n i k ∈ N, 1 ≤ n 1 < • • • < n k , n 1 + • • • + n k = n .
We then focuses on the germ and its Sylows, with the main result on cycle sets being constructed from the Zappa-Szép product of germs (Theorem 4.12), this product being a sort of generalized semi-direct products where each term acts on the others :

Theorem. Any cycle set can be obtained as the Zappa-Szép product of cycle sets with class a prime power.

Taking decomposability ( [START_REF] Bhandari | On the Extraordinary Construction of Cycle Sets by Wolfgang Rump[END_REF]) into account, one can consider that the "basic" cycle sets are of class and size powers of the same prime.

The first two sections are mostly a new approach to well-known theorems which allows simpler and more intuitive proofs, while the last two contain new results obtained by using the new approach developed in the two first sections. More precisely:

Section 1 is a brief introduction to monomial matrices and the main properties that we will use for our proofs. Section 2 consists in recovering most results of [START_REF] Dehornoy | Set-Theoretic Solutions of the Yang-Baxter Equation, RC-calculus, and Garside Germs[END_REF] with a monomial representation, allowing shorter, simpler and self-contained proofs. Including the study of right-divisibility without Rump's theorem on the non-degeneracy of finite cycle sets (while also easily re-obtaining this theorem). Section 3 focuses on Dehornoy's class and germ, in particular we state a conjecture on the bound of the classes and prove it in a particular case. Section 4 explains how to construct all cycle sets from ones with coprime classes through the Zappa-Szép product of germs, with a precise condition and an explicit algorithm/formula to do so.

Acknowledgements The author wishes to thank Leandro Vendramin for his insightful remarks on the content and readability of this article.

Monomial matrices

The basic tool to work on the representation are monomial matrices. We recall the definition and some basic properties: A matrix is said to be monomial if each row and each column has a unique non-zero coefficient. We denote by Monom n (R) the set of monomial matrices over a ring R. To a permutation σ ∈ S n we associate the permutation matrix P σ where the i-th row contains a 1 on the σ(i)-th column, for instance

P (123) =    0 1 0 0 0 1 1 0 0   .
We then have [START_REF] Bachiller | Extensions, Matched Products, and Simple Braces[END_REF] . . .

P σ     v 1 . . . v n     =     v σ
v σ(n)   
 and thus, if e i is the i-th canonical basis vector, P σ (e i ) = e σ -1 (i) . Moreover, for σ, τ ∈ S n we find P σ P τ = P τ σ . It is well known that a monomial matrix admits a unique (left) decomposition as a diagonal matrix right-multiplied by a permutation matrix. Thus, if m is monomial, D m will denote the associated diagonal matrix, and P m the associated permutation matrix, i.e. m = D m P m , and by ψ(m) we will denote the permutation associated with the matrix P m . Let D be a diagonal matrix and P a permutation matrix. We denote the conjugate matrix P DP -1 as P D, and if σ is the permutation associated with P we will also write σ D. The following statements are well-known. As they will be essential throughout this paper, we state them explicitly:

Lemma 1.1. Let D be a diagonal matrix and P a permutation matrix. Then P D is diagonal. Moreover, the i-th row of D is sent by conjugation to the σ -1 (i)-th row.

In particular, this implies that, P σ D = σ DP σ giving a way to alternate between left and right (unique) decomposition of monomial matrices. D m = diag(a, b, c) (123) diag(x, y, z) = diag(a, b, c)diag(y, z, x) = diag(ay, bz, cx)

and indeed mm =    0 ay 0 bz 0 0 0 0 cx    = diag(ay, bz, cx)P [START_REF] Etingof | Set-Theoretical Solutions to the Quantum Yang-Baxter Equation[END_REF] .

Cycle sets and monomial matrices

In this section, we retrieve the results of [START_REF] Dehornoy | Set-Theoretic Solutions of the Yang-Baxter Equation, RC-calculus, and Garside Germs[END_REF] using monomial matrices. In particular, our proofs don't rely on Rump's theorem on the bijectivity of finite cycle sets ( [START_REF] Rump | A Decomposition Theorem for Square-Free Unitary Solutions of the Quantum Yang-Baxter Equation[END_REF]), and use simpler arguments compared with the technicality of [START_REF] Dehornoy | Set-Theoretic Solutions of the Yang-Baxter Equation, RC-calculus, and Garside Germs[END_REF]. Moreover, although we don't need it in this section, we provide a short and simple proof of Rump's theorem.

Cycle sets Definition 2.1 ([19]).

A cycle set is a set S endowed with a binary operation * such that for all s in S the map ψ(s) : t → s * t is bijective and for all s, t, u in S:

(s * t) * (s * u) = (t * s) * (t * u). ( 1
)
When S is finite, ψ(s) can be identified with a permutation in S n .

When the diagonal map is the identity (i.e. for all s ∈ S, s * s = s), S is called square-free.

From now, we fix a cycle set (S, * ) .

Definition 2.2 ([19]

). The group G S associated with S is defined by the presentation:

G S := S | s(s * t) = t(t * s), ∀s = t ∈ S .
(2)

Similarly, we define the associated monoid M S by the presentation:

M S := S | s(s * t) = t(t * s), ∀s = t ∈ S + .
It will be called the structure group (resp. monoid) of S.

Example 2.3. Let S = {s 1 , . . . , s n }, σ = (12 . . . n) ∈ S n . The operation s i * s j = s σ(j) makes S into a cycle set, as for all s, t in S we have (s * t) * (s * s j ) = s σ 2 (j) = (t * s) * (t * s j ).

The structure group of S then has generators s 1 , . . . , s n and relations s i s σ(j) = s j s σ(i) (which is trivial for i = j).

In particular, for n = 2 we find

G = s, t | s 2 = t 2 .
When the context is clear, we will write G (resp. M ) for G S (resp. M S ). We also assume S to be finite and fix an enumeration S = {s 1 , . . . , s n }.

Remark 2.4. By the definition of ψ : S → S n we have that s i * s j = s ψ(s i )(j) , which we will also write ψ(s i )(s j ) for simplicity.

Dehornoy's calculus

Recall that we fixed (S, * ) a finite cycle set of size n with structure monoid (resp. group) M (resp. G).

In the following, we introduce the basics of Dehornoy's Calculus, which will be easily understood by directly looking at the representation introduced in the same paper [START_REF] Dehornoy | Set-Theoretic Solutions of the Yang-Baxter Equation, RC-calculus, and Garside Germs[END_REF], and we use those to retrieve the well-known I-structure of the structure monoid ( [START_REF] Gateva-Ivanova | Semigroups of I-Type[END_REF]).

Although all these results are already stated in [START_REF] Dehornoy | Set-Theoretic Solutions of the Yang-Baxter Equation, RC-calculus, and Garside Germs[END_REF], their provided proofs are very technical, whereas using monomial matrices greatly simplifies proofs and allows for more intuition.

Definition 2.5 ([7]). For a positive integer k, we define inductively the formal expression

Ω k by Ω 1 (x 1 ) = x 1 and Ω k (x 1 , . . . , x k ) = Ω k-1 (x 1 , . . . , x k-1 ) * Ω k-1 (x 1 , . . . , x k-2 , x k ). ( 3
)
We then define another formal expression Π k by:

Π k (x 1 , . . . , x k ) = Ω 1 (x 1 ) • Ω 2 (x 1 , x 2 ) • . . . • Ω k (x 1 , . . . , x k ). ( 4
)
For a cycle set S, Ω k (t 1 , . . . , t k ) will be the evaluation in S of Ω k (x 1 , . . . , x k ) at (t 1 , . . . , t k ) in S k . Similarly, Π k (t 1 , . . . , t k ) will be the evaluation in M S of Π k (t 1 , . . . , t k ) with the symbol • identified with the product of elements in M S .

Lemma 2.6 ([7]

). The element Ω k (t 1 , . . . , t k ) of S is invariant by permutation of the first k -1 entries.

Proof. For k = 1 and k = 2 there is only the identity permutation and for k = 3 this is precisely the condition the cycle set equation [START_REF] Bachiller | Extensions, Matched Products, and Simple Braces[END_REF]:

Ω 3 (s, t, u) = Ω 2 (s, t) * Ω 2 (s, u) = (s * t) * (s * u) = (t * s) * (t * u) = Ω 3 (t, s, u).
Assume k ≥ 4 and proceed by induction. Since the transpositions σ i = i i + 1 generate S k , we only have to look at σ i with i ≤ k -2. We have, by definition,

Ω k (t 1 , . . . , t k ) = Ω k-1 (t 1 , . . . , t k-1 ) * Ω k-1 (t 1 , . . . , t k-2 , t k ). If i = k -2,
By the induction hypothesis, both Ω k-1 occurring here are invariant by σ i as it doesn't affect the last term. Remains the case i = k -2, for which we have:

Ω k (t 1 , . . . , t σ k-2 (r-2) , t σ k-2 (r-1) , t k ) = Ω k (t 1 , . . . , t k-3 , t k-1 , t k-2 , t k ) = Ω k-1 (t 1 , . . . , t k-3 , t k-1 , t k-2 ) * Ω k-1 (t 1 , . . . , t k-3 , t k-1 , t k ) (Expanding) = (Ω k-2 (t 1 , . . . , t k-3 , t k-1 ) * Ω k-2 (t 1 , . . . , t k-3 , t k-2 )) (Expanding) * (Ω k-2 (t 1 , . . . , t k-3 , t k-1 ) * Ω k-2 (t 1 , . . . , t k-3 , t k )) = (Ω k-2 (t 1 , . . . , t k-3 , t k-2 ) * Ω k-2 (t 1 , . . . , t k-3 , t k-1 )) (cycle set Equation) * (Ω k-2 (t 1 , . . . , t k-3 , t k-2 ) * Ω k-2 (t 1 , . . . , t k-3 , t k )) = Ω k-1 (t 1 , . . . , t k-3 , t k-2 , t k-1 ) * Ω k-1 (t 1 , . . . , t k-3 , t k-2 , t k ) (Collapsing) = Ω k (t 1 , . . . , t k-2 , t k-1 , t k ).
(Collapsing) Which concludes the proof.

Proposition 2.7. The element Π k (t 1 , . . . , t k ) of M S is invariant by permutation of the entries.

Proof. For k = 1 there is nothing to prove. For k = 2 we find Π

2 (t 1 , t 2 ) = t 1 (t 1 * t 2 ) which is identified with t 2 (t 2 * t 1 ) = Π 2 (t 2 , t 1 ) by the defining relations of M in 2.
Now assume k ≥ 3 and, as in the proof of the previous lemma; restrict to the transpositions

σ i = i i + 1 with 1 ≤ i < k. Recall that, by definition Π k (t 1 , . . . , t k ) = Ω 1 (t 1 ) • Ω 2 (t 1 , t 2 ) • . . . • Ω k (t 1 , . . . , t k ).
Clearly, the first i -1 terms remain unchanged by σ i . And by the previous Lemma 2.6, for k > i + 1 the terms Ω k are invariant by σ i . Thus we only have to look at the product:

Ω i (t 1 , . . . , t i-1 , t i+1 ) • Ω i+1 (t 1 , . . . , t i-1 , t i+1 , t i ) = Ω i (t 1 , . . . , t i-1 , t i+1 ) • (Ω i (t 1 , . . . , t i-1 , t i+1 ) * Ω i (t 1 , . . . , t i-1 , t i )) (Expanding) = Ω i (t 1 , . . . , t i-1 , t i ) • (Ω i (t 1 , . . . , t i-1 , t 1 ) * Ω i (t 1 , . . . , t i-1 , t i+1 )) (Relations of M ) = Ω i (t 1 , . . . , t i-1 , t i ) • Ω i+1 (t 1 , . . . , t i-1 , t i , t i+1 ).
(Collapsing) Which concludes the proof. Lemma 2.8. For any s, t 1 , . . . , t k in S, the map s → Ω k+1 (t 1 , . . . , t k , s) is bijective.

Proof. We proceed by induction: for k = 1 there is nothing to prove, for k = 2 this is part of the definition of a cycle set. So consider k ≥ 2 and suppose that the property holds for k -1. We have

Ω k+1 (t 1 , . . . , t k , s) = Ω k (t 1 , . . . , t k ) * Ω k (t 1 , . . . , t k-1 , s),
by induction hypothesis s → Ω t 1 ,...,t k-1 ,s is bijective, and as Ω k t 1 , . . . , t k is an element of S, its left action is bijective, which concludes the proof. Proposition 2.9. Let f be in M . Then there exists (t 1 , . . .

, t k ) k in S k such that f = Π k (t 1 , . . . , t k ).
In the sequel, for any f ∈ M , by a "Π-expression of f " we mean choosing any (t

1 , . . . , t k ) in S k such that f = Π k (t 1 , . . . , t k ).
Proof. Take a decomposition of f as a product of elements of S:

f = t 1 t 2 . . . t k . Let t 1 = t 1 , because S is a cycle set, the map t → t 1 * t is bijective, so there exists t 2 such that t 2 = t 1 * t 2 (explicitly t 2 = ψ(t 1 ) -1 (t 2 )), i.e.: f = t 1 (t 1 * t 2 )t 3 . . . t k = Ω 1 (t 1 )Ω 2 (t 1 , t 2 )t 3 . . . t k = Π 2 (t 1 , t 2 )t 3 . . . t k .
We proceed by induction on k: suppose that we have t

1 , . . . , t k-1 such that t 1 . . . t k-1 = Π k-1 (t 1 , . . . , t k-1 ), i.e. t i = Ω k (t 1 , . . . , t i ) for i < k. By the previous lemma the map s → Ω k (t 1 , . . . , t k-1 , s) is bijective, so there exists t k such that t k = Ω k (t 1 , . . . , t k ).
By induction, this gives the existence of t 1 , . . . , t k such that

f = Ω 1 (t 1 ) . . . Ω k (t 1 , . . . , t k ) = Π k (t 1 , . . . , t k ).
Example 2.10. Take S = {s 1 , s 2 , s 3 , s 4 } with ψ(s 1 ) = (1234) ψ(s 3 ) = (24) ψ(s 2 ) = (1432) ψ(s 4 ) = [START_REF] Etingof | Indecomposable Set-Theoretical Solutions to the Quantum Yang-Baxter Equation on a Set with a Prime Number of Elements[END_REF].

And consider the element f = s 1 s 2 s 3 s 4 . We have

ψ(s 1 ) -1 (s 2 ) = s 1 , so f = s 1 (s 1 * s 1 )s 3 s 4 = Π 2 (s 1 , s 1 )s 3 s 4 . Similarly, ψ(s 2 ) -1 (s 3 ) = s 4 , so s 3 = s 2 * s 3 = (s 1 * s 1 ) * s 4 , as ψ(s 1 ) -1 (s 4 ) = s 3 , we have s 3 = (s 1 * s 1 ) * (s 1 * s 3 ) = Ω 3 (s 1 , s 1 , s 3 ). So f = Π 3 (s 1 , s 1 , s 3 )s 4 .
Finally, for s 4 , we first write s 4 = s 3 * a, then a = s 2 * b and b = s 1 * c (going through the letters of f = s 1 s 2 s 3 s 4 from right to left), so that s 4 = s 3 * (s 2 * (s 1 * c))). Replacing s 3 , s 2 and s 1 by their previously found expressions gives

s 4 = ((s 1 * s 1 ) * (s 1 * s 3 )) * ((s 1 * s 1 ) * (s 1 * c)) = Ω 4 (s 1 , s 1 , s 3 , c).
Here we find c = s 2 so

f = Π 4 (s 1 , s 1 , s 3 , s 2 ).
One can also check for instance that s 4 = Ω 4 (s 1 , s 1 , s 3 , s 2 ) also equals Ω 4 (s 3 , s 1 , s 1 , s 2 ) and so f = Π 4 (s 3 , s 1 , s 1 , s 2 ).

The monomial representation

Recall that we fix (S, * ) a finite cycle set of size n with S = {s 1 , . . . , s n } and with structure monoid (resp. group) M (resp. G). Proposition 2.11 ([7]). Let q be an indeterminate and consider Monom n (Q[q, q -1 ]), denote D s i the matrix diag(1, . . . , q, . . . , 1) the n × n diagonal matrix with a q on the i-th row.

The map Θ defined on S by Θ(s i ) := D s i P ψ(s i ) (5) extends to a representation G → Monom n (Q[q, q -1 ]) and similarly to a morphism M → Monom n (Q[q]).

Proof. We have to show that Θ respects the defining relations of G (and M ). Let s i , s j be in S and define g = Θ(s i )Θ(s i * s j ) and g = Θ(s j )Θ(s j * s i ). By Corollary 1.2 we have

D g = D s i ψ(s i ) D s i * s j = D s i ψ(s i ) D ψ(s i )(s j )
and the latter is equal to D s i D s j by Lemma 1.1. By symmetry and commutativity of diagonal matrices, we deduce D g = D g .

On the other hand, again by Corollary 1.2, we have ψ(g

)(t) = ψ(s i * s j ) • ψ(s i )(t) = (s i * s j ) * (s i * t)
for all t ∈ S. By symmetry and as S is a cycle set we deduce that ψ(g) = ψ(g ) and so g = g .

For simplicity, we will write Θ(g) = D g P g to mean Θ(g) = D Θ(g) P Θ(g) .

Remark 2.12. The image of G by Θ lies in the subgroup of Monom n (Q[q, q -1 ]) consisting of matrices such that the non-zero coefficients (i.e. the diagonal part of the decomposition) consists only of powers of q (including q 0 = 1). We denote this subgroup by Σ n . By Σ + n we denote the submonoid of Monom n (Q[q]) consisting of non-matrices whose non-zero coefficients are non-negative powers of q only, and by D i the matrix diag(1, . . . , q, . . . , 1) with a q in the i-th place. Remark 2.13. Let G + be the submonoid of M of positive words. As M and G + have the same generators, their images in their respective representations Θ coincide. Thus, when working in Monom n (Q[q, q -1 ]), we will not distinguish between Θ(M ) and Θ(G + ). Later, we will see that in fact G is the group of fractions of M and M = G + .

Example 2.14. Set S = {s 1 , s 2 , s 3 } and ψ(s i ) = (123) for all i.

Θ(s 1 ) =    q 0 0 0 1 0 0 0 1       0 1 0 0 0 1 1 0 0    =    0 q 0 0 0 1 1 0 0    and similarly Θ(s 2 ) =    0 1 0 0 0 q 1 0 0    Θ(s 3 ) =    0 1 0 0 0 1 q 0 0    .
Proposition 2.15. For all s, t ∈ S:

P s D t = ψ(s) D t P s = D ψ(s) -1 (t) P s .
In particular, P s D s * t = D t P s .

Proof. This is a direct consequence of Lemma 1.1. Definition 2.16. For an element g ∈ Σ n , we define its "coefficient-powers tuple" cp(g) to be the unique n-tuple of integers (c 1 , . . . , c n ) such that D g = diag(q c 1 , . . . , q cn ).

We set λ(g

) := n i=0 | c i |. For σ ∈ S n , by σ (c 1 , . . . , c n ) we denote (c σ(1) , . . . , c σ(n) ). Example 2.17. If g =      q 2 0 0 0 0 0 1 0 0 0 0 q -1 0 q 0 0     
, then cp(g) = (2, 0, -1, 1) and λ(g) = 2 + 0 + 1 + 1 = 4. Proposition 2.18. For all g, h ∈ Σ n we have:

cp(gh) = cp(g) + ψ(g) cp(h). ( 6
)
Moreover λ(gh) = λ(g) + λ(h).

Proof. The first equality is a direct consequence of Corollary 1.2 applied to the representation. The second follows from the fact that the defining relations of the structure monoid respects the length of words.

Set Ω = Θ

P Ω k-1 (t 1 ,...t k-1 ) D Ω k (t 1 ,...,t k ) = P Ω k-1 (t 1 ,...t k-1 ) D Ω k-1 (t 1 ,...,t k-1 ) * Ω k-1 (t 1 ,...,t k-2 ,t k ) = D Ω k-1 (t 1 ,...,t k-2 ,t k ) P Ω k-1 (t 1 ,...t k-1 ) .
We can then repeat this process for all the permutation matrices

P Ω k-2 (t 1 ,...t k-2 ) , . . . , P Ω 1 (t 1 )
and get

P Ω 1 (t 1 ) . . . P Ω k-1 (t 1 ,...t k-1 ) D Ω k (t 1 ,...,t k ) = D t k P Ω 1 (t 1 ) . . . P Ω k-1 (t 1 ,...t k-1 ) .
Thus we find

Π k (t 1 , . . . , t k ) = (D t 1 . . . D t k ) P Ω 1 (t 1 ) . . . P Ω k (t 1 ,...,t k ) .
As

P σ P τ = P τ σ , we have ψ(Π k (t 1 , . . . , t k ))(s) = ψ(Ω k (t 1 , . . . , t k )) • • • • • ψ(Ω 1 (t 1 ))(s). Then ψ(Ω 1 (t 1 ))(s) = t 1 * s = Ω 2 (t 1 , s), which in turns gives ψ(Ω 2 (t 1 , t 2 )) • ψ(Ω 1 (t 1 ))(s) = ψ(Ω 2 (t 1 , t 2 ))(Ω 2 (t 1 , s)) = Ω 2 (t 1 , t 2 ) * Ω 2 (t 1 , s) = Ω 3 (t 1 , t 2 , s).
ψ(s 1 ) = (1234) ψ(s 3 ) = (24) ψ(s 2 ) = (1432) ψ(s 4 ) = (13).
The tuple (2, 1, 1, 0) can be obtained from Π 4 (s 1 , s 1 , s 3 , s 2 ) = s 1 s 2 s 3 s 4 = f as, in the induction of the proof we did:

P s 1 P s 2 P s 3 D s 4 = P s 1 P s 2 D ψ(s 3 ) -1 (s 4 ) P s 3 = P s 1 D ψ(s 2 ) -1 •ψ(s 3 ) -1 (s 4 ) P s 2 P s 3 = D ψ(s 1 ) -1 •ψ(s 2 ) -1 •ψ(s 3 ) -1 (s 4 ) P s 1 P s 2 P s 3 Computing ψ(s 1 ) -1 • ψ(s 2 ) -1 • ψ(s 3 ) -1 (s 4 ) = s 2 precisely retrieves the Example 2.10.
Those reasonings are inverse to one another: to construct an element with given coefficient-powers we use permutations step by step and letter by letter (this is the construction of Π), and to get a Π-expression we use all the inverse of those permutations.

Corollary 2.22. Any f ∈ M is uniquely determined by D Θ(f ) .
Moreover, this diagonal part can be read as the entries when taking a Π-expression of f .

In particular, this means that the representation is injective on the monoid, as the diagonal part is determined by the entries of a Π-expression, which is invariant by permutations of those entries.

Proof. This follows from the previous proposition and Proposition 2.9. Take Θ(f ) =

D f P f ∈ M with D f = D a 1 s 1 . . . D a k s k . By Proposition 2.9 there exist t 1 , . . . , t k ∈ S such that f = Π k (t 1 , . . . , t k ). By Proposition 2.19, we have D Θ(f ) = D t 1 . . . D t k ,
this gives the second statement. By the unicity of the monomial decomposition, we must have a i times s i in the tuple (t 1 , . . . , t k ) and by Proposition 2.7 the orders of the t i 's doesn't matter.

Thus if g ∈ M is such that D Θ(g) = D Θ(f ) , by the same argument we must have

g = Π k (t 1 , . . . , t k ) = f . Denote D n (resp. D + n ) the subset of diagonal matrices of M n (resp. M + n ).
We have an obvious inclusion D + n → D n , and a faithful representation

N n ∼ → D + n . Corollary 2.23. The natural morphism M → G sending each generator s i ∈ M to s i ∈ G is injective.
Proof. We have shown that there is a (set) bijection Π : N n ∼ → M . Then we have the following commutative diagram:

N n M G D + n D n ∼ Π ∼ Because the composition N n → D + n → D n is injective, and as Π : N n → M is bijective, the composition M → G → D n must be injective, so necessarily M injects in G.
A word t 1 . . . t k over S representing an element g is said to be reduced if its length k is minimal among the representative words of g.

Proposition 2.24. Any element g ∈ G can be decomposed as a reduced left-fraction in

M , that is: ∃f, h ∈ M, g = f h -1 with λ(g) = λ(f ) + λ(h)
where λ denotes the length as a S ∪ S -1 -word.

Proof. Let g ∈ G, and write a reduced decomposition of g as product of elements in S ∪ S -1 . If this expression is of length 1, this is trivial. If the length is 2, we have 4 cases with s, t ∈ S: st, s -1 t -1 , st -1 and s -1 t. The first 3 cases are of the desired form. For the last one, the defining relations of G give

s(s * t) = t(t * s) ⇐⇒ s -1 t = (s * t)(t * s) -1 .
For arbitrary length, we can inductively use the same relation s -1 t = (s * t)(t * s) -1 to "move" all inverses of the generators to the right in a decomposition of g, which gives the desired form.

We will later state a similar result for right-fractions (Proposition 2.71).

Corollary 2.25. Any element in G can be decomposed as a left-fraction f g -1 in M such that D g commutes with all permutation matrices (more precisely that D g is a power of

D s 1 . . . D sn ).
Proof. Take a Π-expression Π k (t 1 , . . . , t k ) of g. up to permuting the entries, we can assume that g = Π k (s 1 , . . . , s 1 , . . . , s n , . . . , s n ), where for 1 ≤ i ≤ n each s i occurs a i times and

a 1 + • • • + a n = k.
Let j be such that a j is (one of) the biggest of the a i 's, then if for some i we have a i < a j we can consider a new element Π k+1 (s 1 , . . . , s 1 , . . . , s n , . . . , s n , s i ) = g • Ω k+1 (s 1 , . . . , s 1 , . . . , s n , . . . , s n , s i ), where s i occurs a i + 1 times and that is obtained from g by right-multiplying by an element in S. Doing so, until all s i occurs a j times, provides an element g which is obtained from g by right-multiplication by some g ∈ M and such that D g = (D s 1 . . . D sn ) a j . Let P σ be a permutation matrix, then P σ D g = σ D g P σ = D g P σ where the last equality is because all the diagonal terms in D g are equal so are invariant by σ.

Finally f g (g) -1 = f g -1 , so replacing (f, g) by (f g , gg ) gives us the result.

Example 2.26. Take S = {s 1 , s 2 , s 3 } and ψ(s i ) = (123) for all i.

Consider h = s -1 3 s -1 2 s 3 , the relation s 2 s 1 = s 3 s 3 (i.e. s 1 s -1 3 = s -1 2 s 3 ) gives h = s -1 3 s 1 s -1 3 ; similarly s 3 s 2 = s 1 s 1 (i.e. s 2 s -1 1 = s -1 3 s 1 ) yields h = s 2 s -1 1 s -1 1 . Let f = s 2 and g = s 1 s 1 so that h = f g -1 , we have g = s 1 (s 1 * s 3 ) = Π 2 (s 1 , s 3 ), thus D g = D Θ(g) = D s 1 D s 3 ,
which is not stable under permutation (as we have (123)

D g = D s (123) -1 (1) D s (123) -1 (2) = D s 3 D s 2 = D g ).
To complete g so that it commutes, we must add D s 3 , so we take

g = Π 3 (s 1 , s 2 , s 3 ) = gs 1 and f = f s 1 . Now D g = D s 1 D s 2 D s 3 commutes with permutation matrices, and f g -1 = f s 1 s -1 1 g -1 = f g -1 = h. Theorem 2.27. Let S be a finite cycle set of cardinal n. Then Θ is a faithful represen- tation of G. Proof. Let g ∈ G, from Proposition 2.24 we know that there exist f, h ∈ M such that g = f h -1 . Thus as Θ is a representation: Θ(g) = Id n ⇐⇒ Θ(f ) = Θ(h) By Corollary 2.23, Θ(f ) = Θ(h) ⇐⇒ f = h, thus Θ is faithful.
From now on, we assume that S is a finite cycle set with S = {s 1 , . . . , s n }. We identify G with its image by the (faithful) representation Θ. We can as well identify Ω (resp. Π) with its image Ω (resp. Π ) by Θ.

Definition 2.28. A subgroup of Σ n is called permutation-free if the only permutation matrix it contains is the identity.

Proposition 2.29. G is permutation-free.

Proof. Suppose P σ is a permutation matrix (associated with σ ∈ S n ) that is in G. Then by Proposition 2.24, there exists f, g ∈ M such that P σ = f g -1 , i.e. D f P f = P σ D g P g . By Corollary 2.25 we can assume that P σ D g = D g P σ , so D f P f = D g P σ P g . By the unicity of the monomial decomposition, we must have D f = D g and P f = P σ P g , so by Proposition 2.22 f = g and thus P σ =Id (and σ =id).

Corollary 2.30. An element g ∈ G is uniquely determined by D g .

Proof. Suppose for g, h ∈ G we have D g = D h . Then

g -1 h = (D g P g ) -1 (D h P h ) = P -1 g D -1 g D g P h = P -1 g P h ∈ G
We have a permutation matrix in G, so it must be the identity, so P g = P h and thus g = h.

Proposition 2.31. For any tuple a = (a 1 , . . . , a k ) in Z k , there exists a unique g ∈ G with cp(g) = (a 1 , . . . , a k ).

Moreover, if all a i ≥ 0 then g ∈ M has a Π-expression g = Π λ(a) which is of length of λ(a) and is minimal by additivity of λ.

Similarly, if g ∈ G, writing it as a fraction of two minimal-length elements of M also gives that the length of g over S ∪ S -1 is λ(g).

Proof. For the first part, the existence follows from Corollary 2.20 and the unicity from the previous Corollary.

The second statement is just Proposition 2.18 applied to the generators of the monoid, and, similarly, the third is a consequence of considering irreducible left-fractions in Proposition 2.24.

Remark 2.32. This is precisely a matricial formulation of the I-structure of [START_REF] Gateva-Ivanova | Semigroups of I-Type[END_REF].

We've seen that the structure group of a cycle set is permutation-free, we now state a reciprocal under a condition on the atom set of the submonoid:

Theorem 2.33. Let G be a subgroup of Σ n , denote G + = G ∩ Σ +
n (the submonoid of positive elements). Suppose that the set of atoms S = {s 1 , . . . , s n } of G + has cardinal n, generates G and there exists a positive integer k such that D s i = D k i . Let the operation * be defined on S by s i * s j = ψ(s i )(s j ), then the following assertions are equivalent:

(i) G is permutation-free (ii) s(s * t) = t(t * s) for all s, t in S (iii) G is the structure group of S Proof. First notice that q → q p provides an injective morphism Σ n → Σ n , so we can assume p = 1. (i) ⇒ (ii): For 1 ≤ i, j ≤ n, we have from Proposition 2.15:

s i s ψ(i)(j) = D i P s i D s i * s j P s i * s j = D i D j P s i P s i * s j
By symmetry, s j (s j * s i ) will have the same diagonal part. Then

(s i (s i * s j )) -1 (s j (s j * s i )) = P -1 s i (s i * s j ) D -1 s i (s i * s j ) D s j (s j * s i ) P s j (s j * s i ) = P -1 s i (s i * s j ) P s j (s j * s i ) ∈ G.
So by the assumption that G is permutation-free we deduce s i (s i * s j ) = s j (s j * s i ).

(ii) ⇒ (iii): Recall that

P s i (s i * s j ) = P s i P s i * s j = P ψ(s i * s j )•ψ(s i ) , so we find ψ(s i * s j )•ψ(s i ) = ψ(s j * s i ) • ψ(s j ). For t ∈ S, this means that ψ(s i * s j ) • ψ(s i )(t) = ψ(s j * s i ) • ψ(s j )(t), i.e. (s i * s j ) * (s i * t) = (s j * s i ) * (s j * t),
so precisely that S is a cycle set. Then the generators of M correspond to the generators of M S and both are submonoids of Σ n , so M = M S . Similarly, as S generates G we have G S = G.

(iii)⇒ (i): This is Proposition 2.29.

Garsideness

In a 2017 talk ( [START_REF] Dehornoy | Garside Germs for YBE Structure Groups, and an Extension of Ore's Theorem[END_REF]), Dehornoy addressed the question of whether his results on the construction of the Garside structure and the I-structure can be derived without using Rump's result on the non-degeneracy of finite cycle set ( [START_REF] Etingof | Indecomposable Set-Theoretical Solutions to the Quantum Yang-Baxter Equation on a Set with a Prime Number of Elements[END_REF]). In this section, we answer his question positively.

Although equivalent to working in the I-structure [START_REF] Gateva-Ivanova | Semigroups of I-Type[END_REF] Z n S n by decomposing elements (c, σ) = (c, 1)(1, σ) = (1, σ)( σ c, 1), working with monomial matrices and their decomposition has the advantage of giving more intuition, and allows for looking at both left and right structure at the same time. For instance, this is efficient when looking at divisibility, that we study in this section.

Recall that we fix (S, * ) a finite cycle set of size n with structure monoid (resp. group) M (resp. G). Definition 2.34. Let g 1 , g 2 be elements of M . We say that g 1 left-divides (resp. rightdivides) g 2 , that we note g 1 g 2 (resp. g 1 r g 2 ) if there exists some h ∈ M such that g 2 = g 1 h (resp. g 2 = hg 1 ) and λ(g 2 ) = λ(g 1 ) + λ(h).

An element g ∈ M is called balanced if the set of its left-divisors Div(g) and rightdivisors Div r (g) coincide.

We equip Z n with the partial ordering given by (a 1 , . . . ,

a n ) ≤ (b 1 , . . . , b n ) iff a i ≤ b i for all 1 ≤ i ≤ n.
In particular, this means that given g 1 , g 2 ∈ G, cp(g 1 ) ≤ cp(g 2 ) iff the power of q on the i-th row of g 1 is less than the one of g 2 for 1 ≤ i ≤ n. Moreover, note that, as

g 1 = P g 1 g 1 D g 1 and g t 1 = P t g 1 D g 1 = P -1 g 1 D g 1 = g 1 D g 1 P -1 g 1 , the coefficient on the i-th column of g 1 is the coefficient on the i-th row of g t 1 . Proposition 2.35. g 1 left-divides g 2 if and only if cp(g 1 ) ≤ cp(g 2 ),
Similarly, g 1 right-divides g 2 if and only if cp(g t 1 ) ≤ cp(g t 2 ). This means that, to check if g 1 is a left-(resp. right-) divisor of g 2 , we only have to check if the power of q is smaller on each row (resp. column).

Proof. Write g

i = D g i P g i = P g i g i D g i . For left-divisibility, consider in G the element h = g -1 1 g 2 = P -1 g 1 D -1 g 1 D g 2 P g 2 . By Proposition 2.31 h ∈ M iff D -1 g 1 D g 2 )
contains only non-negative powers of q, precisely meaning that the power on each row of g 1 is less than the one of g 2 .

Similarly, for right divisibility, let h = g 2 g -1

1 = P g 2 g 2 D g 2 g 1 D g 1 -1 P -1 g 1 , which is in M iff g 2 D g 2 g 1 D g 1 -1
contains only non-negative powers of q, which is the same criterion on the columns.

Example 2.36. 12), we can see that: 0 q 3 1 0 left-divides q 4 0 0 1 (as 3 ≤ 4 on the first line and 0 ≤ 0 on the second since 1 = q 0 ), but doesn't right divide it (as 3 > 0 on the second column)

Taking S = {s 1 , s 2 } with ψ(s 1 ) = ψ(s 2 ) = (
Corollary 2.37. Let g = Π k (t 1 , . . . , t k ), then the left-divisors of g are precisely the Π's of subtuples of (t 1 , . . . , t k ).

Reciprocally, the right multiples of g are the elements h such that, when writing h = Π l (u 1 , . . . , u l ), the tuple (u 1 , . . . , u l ) contains the tuple (t 1 , . . . , t k ).

Corollary 2.38. Let g 1 , g 2 be in M . The left-gcd (resp. left-lcm) of g 1 and g 2 , denoted g 1 ∧ g 2 (resp. g 1 ∨ g 2 ) is given by the unique element such that the coefficient-power on each row is the maximum (resp. minimum) of those of g 1 and g 2 .

For right-gcd (resp. right-lcm) it is the same but for each column.

Explicitly, if cp(g 1 ) = (a 1 , . . . , a n ) and cp(g 2 ) = (b 1 , . . . , b n ), then cp(g 1 ∧ g 2 ) = (max(a 1 , b 1 ), . . . , max(a n , b n )) and cp(g 1 ∨ g 2 ) = (min(a 1 , b 1 ), . . . , min(a n , b n )).
Example 2.39. As in 2.10 take S = {s 1 , s 2 , s 3 , s 4 } with ψ(s 1 ) = (1234) ψ(s 3 ) = (24)

ψ(s 2 ) = (1432) ψ(s 4 ) = (13)
We have

     0 q 0 0 1 0 0 0 0 0 0 q 0 0 1 0      ∧      0 0 0 q 0 0 q 0 0 1 0 0 1 0 0 0      =      0 q 0 0 0 0 1 0 0 0 0 1 1 0 0 0     
Which can be understood in two ways:

• gcd (Π 2 (s 1 , s 3 ), Π 2 (s 1 , s 2 )) = Π 1 (s 1 )
as s 1 the only term appearing in both Π 2 .

• The gcd of the two given matrices must have cp-tuple (1, 0, 0, 0) (taking the minimal coefficient-power row by row), which uniquely exists by the I-structure. Similarly:

     0 q 0 0 1 0 0 0 0 0 0 q 0 0 1 0      ∨      0 1 0 0 q 0 0 0 0 0 0 1 0 0 q 0      =      q 0 0 0 0 q 0 0 0 0 q 0 0 0 0 q     
can be understood as both:

• lcm (Π 2 (s 1 , s 3 ), Π 2 (s 2 , s 4 )) = Π 4 (s 1 , s 2 , s 3 , s 4 ) (we took the maximum number of each occurences of each s i , here always 1) • The lcm of the two given matrices must have cp-tuple (1, 1, 1, 1) (taking the maximal coefficient-power row by row), which uniquely exists by the I-structure. The second description however does not provide an explicit description of the element, as we don't have the permutation part.

For the right gcd and lcm, we do the same on the columns, which has the disadvantage and not having something as explicit as the first-description of the left versions (see the Π of [START_REF] Dehornoy | Set-Theoretic Solutions of the Yang-Baxter Equation, RC-calculus, and Garside Germs[END_REF] for a more detailled approach). Corollary 2.40. An element such that the non-zero terms of its i-th row and i-th column are equal for all 1 ≤ i ≤ n is balanced. Definition 2.41. An element of M is called a Garside element if it is balanced, Div(g) is finite and generates M . Proposition 2.42 ([7]). The unique element ∆ such that D ∆ = diag(q, . . . , q) is a Garside element of M .

Equivalently, ∆ = Π n (s 1 , . . . , s n ) or cp(∆) = (1, . . . , 1).
Proof. Because all the non-zero coefficients of ∆ are equal, the latter is balanced.

Its set of divisors is the set of elements with non-zero coefficients 1 or q and so is finite and has cardinal 2 n , and it contains all the generators s i so also generates M.

Remark 2.43. The powers of ∆, which are the unique elements with cp-tuple (k, . . . , k) for k ≥ 1, are also Garside elements by the same reasoning.

More generally, Garside elements are precisely the balanced elements with no 1's.

Definition 2.44 ([9]

). A monoid is said to be a Garside monoid if: (i) It is cancellative, i.e. if for every element g 1 , g 2 , h, k, hg

1 k = hg 2 k ⇒ f = g.
(ii) There exists a map Λ to the integers such that λ(g 1 g 2 ) ≥ λ(g 1 ) + λ(g 2 ) and λ(g) = 0 ⇒ g = 1. (iii) Any two elements have a gcd and lcm relative to both and r . (iv) It possesses a Garside element ∆.

Proposition 2.45 ([7]

). M is a Garside monoid.

Proof. The map λ previously defined satisfies point (ii) (and in fact as an equality).

For (iii) we have Corollary 2.38 and for (iv) Proposition 2.42. We are left to prove (i), which is a direct consequence of Corollary 2.23 (alternatively, we can see this is that our elements are monomial matrices, such inject into the linear group GL n (Q[q, q -1 ]) from which we deduce the cancellative property).

Germs

In [START_REF] Dehornoy | Set-Theoretic Solutions of the Yang-Baxter Equation, RC-calculus, and Garside Germs[END_REF] Dehornoy associates a germ to structure groups of cycle sets, in the construction he uses the non-degeneracy of finite cycle sets. Here we provide proofs that do not rely on this property. In particular the direct existence of Dehornoy's class is obtained along with a better bound (again improved in the next section). Moreover, we state an exchange lemma and a solution to the word problem, as is known in the context of Coxeter groups.

Recall that we fix (S, * ) a finite cycle set of size n with structure monoid (resp. group) M (resp. G). For s ∈ S and k ∈ N denote by s [k] the unique element in M such that

D s [k] = D k s , i.e. s [k] = Π k (s, . . . , s) = sT (s) . . . T k-1 (s)
where T is the diagonal map s → s * s.

Proposition 2.46. There exists a positive integer d such that for all

s i ∈ S, s [d] i is diagonal, i.e. P s [d] i = Id.
The smallest integer satisfying this condition is called the Dehornoy's class of S, and all the others will be multiples of this class. Our results will be stated for the class, but most would work for any multiples.

Proof. First fix s ∈ S. The map sending s [k] to ψ(s [k] ) is a map from an infinite (countable) set to a finite one (S n ), therefore it is not injective. So there exists

k 1 , k 2 ∈ N such that P s [k 1 ] = P s [k 2 ]
. We can assume k 1 > k 2 without loss of generality. We have s

[k 1 ] (s [k 2 ] ) -1 = D k 1 -k 2 s which is in G, and as k 1 -k 2 > 0 is also in M (it is Π k 1 -k 2 (s, . . . , s)), so it is necessarily equal to s [k 1 -k 2 ]
which is thus diagonal. Doing this for all s i ∈ S, we get the existence of d i ∈ N such that s

[d i ] i
is diagonal. Notice that again, by the same argument, we must have for all k ∈ N (s

[d i ] i ) k = D kd i s i = s [kd i ] i . Taking d = lcm(d 1 , . . . , d n ) we have for all i the existence of d i > 0 such that d = d i d i , we find that for all i, s [d] i = (s [d i ] i ) d i is diagonal.
Remark 2.47. In [START_REF] Dehornoy | Set-Theoretic Solutions of the Yang-Baxter Equation, RC-calculus, and Garside Germs[END_REF], the author gives a bound on the class of a cycle set as d ≤ (n 2 )!.

Here, we obtain a first better bound d ≤ (n!) n given by the previous proof (as d = lcm(d 1 , . . . , d n ) with d i ≤ n!). This bound will be improved in Propositions 3.10 and 3.11.

Proposition 2.48. Let d be the class of S and denote by G [d] the subgroup of G generated by all the s [d] . Then G [d] is a normal subgroup of G.

Proof. The generators of G [d] are diagonal, thus this subgroup consists of diagonal matrices only. Conjugating a diagonal matrix D by a permutation matrix is diagonal, thus for all g in G, (D g P g )D(P -1 g D -1 g ) = ψ(g) D. Because the subgroup contains all possible diagonal matrix with coefficients powers of q d , it is stable by the action of S n by permutation, so ∀h ∈ G [d] , ghg -1 ∈ G [d] .

We define the quotient group G by G = G/G [d] .

Proposition 2.49 ([7]). The projection π : G → G amounts to adding to the presentation of G the relations s [d] = 1, more precisely quotienting is the same as specializing at q = exp( 2iπ d ) noted ev q . Moreover, the map π • Π : Z S → G induces a (set) bijection Π : (Z/dZ) S → G.

Proof. The first part comes from the fact that G [d] is generated by the s [d] which are diagonal, and as each element containing a coefficient-power greater than d is a multiple of some s i by Proposition 2.35, we see that quotienting is just specializing at q = exp( 2iπ d ). The second part then follows as (canonical representative of) elements of G have nonzero coefficients in {1, q, . . . , q d-1 }.

Remark 2.50. If d = 1 then G [d] = G so G is trivial. However, d = 1 means that all the generators s are diagonal, i.e. s * t = t for all s, t in S: this is just the special case of the trivial cycle set. So we will assume d ≥ 2, but this unique trivial case can still be included as all our results work for any multiples of the class (thus any positive integer for the trivial cycle set).

From now on, assume d ≥ 2.

Example 2.51. Let S = {s 1 , . . . , s n } with ψ(s i ) = (12 . . . n) = σ for all i. Then for any s ∈ S, k ∈ Z: s

[k] i = D k s P σ k . Thus Dehornoy's class of S is equal to n. Let ζ n = exp( 2iπ n ), then G is generated by the s i = diag(1, . . . , ζ n , . . . , 1)P σ . Denote by ζ d = exp( 2iπ d ) a primitive d-th root of unity and µ d = {ζ i d | 0 ≤ i < d}. Let Σ d n be the subgroup of Monom n (C) with non-zero coefficients in {0} ∪ µ d . Given k ≥ 1, there is natural embedding ι dk d : Σ d n → Σ dk n sending ζ d to ζ k dk (as ζ k dk = exp( 2ikπ dk ) = ζ d ).
From the previous proposition, we deduce the following result: Lemma 2.52. The quotient group G is a subgroup of Σ d n . Recall that if S has Dehornoy's class d, then for any positive integer k we have that s [kd] = (s [d] ) k is diagonal, thus we could also consider the germ G/ s [kd] s∈S . The embedding ι dk d (G) can then be seen as embedding the germ G is this bigger quotient group. Definition 2.53. [START_REF] Dehornoy | Set-Theoretic Solutions of the Yang-Baxter Equation, RC-calculus, and Garside Germs[END_REF] If (M, ∆) be a Garside monoid and G the group of fractions of M , a group G with a surjective morphism π : G → G is said to provide a Garside germ for (G, M, ∆) if there exists a map χ :

G → M such that π • χ = Id G , χ(G) = Div(∆) and M admits the presentation χ(G) | χ(f g) = χ(f )χ(g) when ||f g|| S = ||f || S + ||g|| S
where || • || S denote the length of an element over S = π(S).

Proposition 2.54 ([7]

). The specialization ev q that imposes q = exp( 2iπ d ) provides a Garside germ of (G, M, ∆ d-1 ).

Proof. Consider the map χ

: G → M defined by sending exp( 2iπ•k d ) to q k ∈ Q[q] for 1 ≤ k < d. It trivially satisfies ev q • χ = Id G .
Its image is the elements of M such that each coefficient-power (the power of q) is strictly less than d, and thus identifies with Div(∆ d-1 ) by the characterization of divisibility. And the presentation amounts to forgetting that q is a root of unity, thus generating M as required.

To work over G, we will use the following corollary to restrict to classes of equivalence over the structure monoid.

Corollary 2.55. The projection ev

q : M → G is surjective.
Proof. G is generated by the s i (positive generators) and their inverses s -1 i (negative generators), so the same holds for G. Moreover, as G is finite, inverses can be obtained from only positive generators. Finally, because M → G as the submonoid generated by positive generators, we obtain the statement.

Example 2.56. Let S = {s 1 , . . . , s n } with ψ(s i ) = (12 . . . n) = σ for all i. Then for any s ∈ S, k ∈ Z: s To recover G from G, one simply takes all the elements of G and forget that q is a root of unity in the following sense: when computing the product of two elements and finding a coefficient q a with a > d, we do not use that q d = 1 and just consider it as a new element. So for instance in χ(G) with n = 4:

χ s [3] 1 χ s [2] 4 = χ(s 1 [3] )χ(s 4 [2] ) =      0 0 0 q 3 1 0 0 0 0 1 0 0 0 0 1 0           0 0 1 0 0 0 0 1 1 0 0 0 0 q 2 0 0      =      0 q 5 0 0 0 0 1 0 0 0 0 1 0 0 0 0      = s [5]
1 .

Because 5 > 4, we obtain a new element different from χ s

[5] 1 = χ (s 1 ).
The quotient group G defined above is called a Coxeter-like group, it was first studied by Chouraqui and Godelle in [START_REF] Chouraqui | Folding of Set-Theoretical Solutions of the Yang-Baxter Equation[END_REF] for d = 2 and generalized by Dehornoy in [START_REF] Dehornoy | Set-Theoretic Solutions of the Yang-Baxter Equation, RC-calculus, and Garside Germs[END_REF].

Fix G a Coxeter-like group obtained from a cycle set S of cardinal n and class d ≥ 2 (so that G is not trivial).

Proposition 2.57. G is permutation-free.

Proof. From Proposition 2.29, we know that G is permutation-free. As G is the image of G by the evaluation at q = ζ d , a matrix g ∈ G is a permutation matrix if it comes from an equivalence class of g ∈ M such that cp(g) = (da 1 , . . . , da n ) (with a 1 , . . . , a n ∈ N), i.e. g = (s

[d]
1 ) a 1 . . . (s [d] n ) an = D da 1 s 1 . . . D dan sn which is diagonal, thus g is diagonal. Definition 2.58. For c = (c 1 , . . . , c n ) ∈ (Z/dZ) n , define cp(diag(q c 1 , . . . , q cn )) to be the unique representative of c as (c 1 , . . . , c n ) ∈ {0, . . . , d -1} n . If g ∈ G, we define cp(g)) = cp(D g ).

We define a function l d by:

∀k ∈ {0, 1, . . . , d -1}, l d (k) =    k, if k ≤ d 2 k -d, if k > d 2 .
(

) 7
And we define λ(c)

= n i=1 |l d (c i )|.
Note that cp corresponds to cp with the projection Z → Z/dZ) and taking representatives in the interval [0, d -1[∩Z, while λ corresponds to λ with the same projection but with representatives in ] -d 2 , d 2 ] ∩ Z. The latter is chosen because, if we have q 6 = 1, the shortest way to write q 2 is q • q but to write q 4 we should use q -1 • q -1 .

Proposition 2.59. The followings hold:

(i) For any c = (c 1 , . . . , c n ) ∈ (Z/dZ) n , there exists a unique element g ∈ G such that cp(g) = c. (ii) The length of an element g ∈ G over S = π(S) is given by λ Proof. (i) follows from Proposition 2.57. Point (ii) is obtained by realizing that the shortest way to write q k for k ∈ {0, . . . , d-1} is using q • ... • q is k ≤ d 2 and otherwise we use the fact that q d = 1 to write it as q -1 • ... • q -1 . Corollary 2.60. Because G is finite, the generators have finite order, so any element has a decomposition as a product of generators (we don't have to include inverses). Thus, any element in G has a Π-expression (in the same sense as in M ).

Corollary 2.61. Defining similarly to Σ n the group Σ n with non-zero coefficients powers of exp( 2iπ d ), we get that a subgroup of Σ n respecting the conditions of Proposition 2.33 is a Coxeter-like group.

Remark 2.62. We say that a word in S = π(S) is reduced in G if it has length λ(w) when seen as an element of G.

For instance, if d > 2 then w = s(s * s) is reduced as it represents Π 2 (s, s) which has λ = 2 but the word corresponding to Π d (s, . . . , s) is not as it has λ = 0. More generally, the word associated to Π r ((t 1 ), . . . , (t r )) is reduced in G if each s i occurs strictly less than d times in the family (t i ).

For Coxeter groups, we have the so-called exchanging lemma (see [START_REF] Michel | Lectures on Coxeter Groups[END_REF]). We provide a similar result for Coxeter-like groups: Lemma 2.63 (Exchange Lemma). Let g ∈ G be written as a reduced expression given by Π k (t 1 , . . . , t k ). For s ∈ S, if Π k+1 (s, t 1 , . . . , t k ) is not reduced, then there exists some i such that g = Π k (s, t 1 , . . . , ti , . . . , t k ), where ti means we omit t i .

Proof. As Π k (t 1 , . . . , t k ) is reduced, s occurs strictly less than d times in (t j ) 1≤j≤k .

Thus, if Π k+1 (s, t 1 , . . . , t k ) is not reduced as word, then s must occur exactly d times in s ∪ (t j ) 1≤j≤k , in particular as d > 1, s occurs at least once in (t j ) 1≤j≤k , say t i = s. Because Π is invariant by permutation of the entries (as Π is), we can move this t i at the beginning and thus g = Π k (s, t 1 , . . . , ti , . . . , t k ).

Another part of interest of the study of Garside groups is that they provide a solution to the word problem:

Proposition 2.64. Two words t = t 1 . . . t k and u = u 1 . . . u l ∈ S * represent the same element in M (resp. G) if,

when taking a Π-expression (resp. Π-expression) of both, they have the same number of occurrences of each s

i , 1 ≤ i ≤ n (resp. modulo d).
Proof. • In M , the elements corresponding to t and u have respectively a Π-expression of length k and l, and because Π is a bijection from N n to M , they represent the same element iff they have the same number of occurrences of each of the atoms in N n . In particular, k = l.

• In G, the same reasoning applies: take a Π-expression of both elements, they represent the same equivalence class iff the number of occurrences of each atom is the same modulo d in N n , as the map Π : (Z/dZ) n → G is a bijection.

We summarize all the previous results in the following diagram, where black arrows are morphism and blue arrows are just maps of sets, and the middle line is a short exact sequence.

M 1 G [d] G G 1 Z S Z S (Z/dZ) S ∼ Π π=evq ∼ Π χ ∼ Π ×d
Note that the left Π is a group morphism because all elements of G [d] have trivial permutation, so this group is abelian and thus Π is the morphism sending (a 1 , . . . , a n ) to diag(q da 1 , . . . , q dan ).

Non-degeneracy

Here we give a new proof of Rump's result on the non-degeneracy of finite cycle sets [START_REF] Rump | A Decomposition Theorem for Square-Free Unitary Solutions of the Quantum Yang-Baxter Equation[END_REF], that is the fact that s → s * s is bijective; in Dehornoy's paper it is used to obtain the bijectivity of (s, t) → (s * t, t * s). Here we prove both of those results using the previous section, the first proof has the advantage of being a simple direct consequence of the I-structure compared to the proof in [START_REF] Rump | A Decomposition Theorem for Square-Free Unitary Solutions of the Quantum Yang-Baxter Equation[END_REF] which involves several steps and constructions.

Recall that we fix (S, * ) a finite cycle set of size n with structure monoid (resp. group) M (resp. G). We have g = ss -1 = D s P s P -1 s D -1 s , using that P σ D = σ DP σ and P -1

σ = P σ -1 twice we find g = D s P s D -1 s * s P -1 s = D s D -1 ψ -1 (s)(s * s ) P s P -1 s . By assumption s * s = s * s thus g = D s D -1 ψ -1 (s)(s * s) P s P -1 s = D s D -1 s P s P -1 s = P s P -1 s .
As G S is permutation-free, we deduce g = 1.

Proposition 2.66.

(i) The diagonal map T : s → s * s is a bijection of S. (ii) The order o of T divides d. In particular, for any integer k, we have s [kd] = (sT (s) . . . T o-1 (s)) k . (iii) More generally s [k] = sT (s) . . . T o-1 (s)sT (s) . . . with exactly k terms Proof. As S is finite and T is injective by the previous lemma, it is bijective and so has finite order. The third point follows directly from the equalities s [k] = Π k (s, . . . , s) = sT (s) . . . T k-1 (s) and, as T o (s) = s, we regroup as many words sT (s) . . . T o-1 (s) as possible. For the second point, if s [k] is diagonal, then s [k]

s = D k s D s P s which has diagonal part D k+1 s so must be s [k+1] . As s [d+1] = s [d] T d (s), we deduce T d (s) = s, thus o = o(T ) divides d.
Corollary 2.67. Let G t be the set of transposes of the elements of G. Then G t is the structure group of a cycle set structure on S t .

Proof. First note that, because G is generated by S, G t is generated by S t . As T is a bijection, for each i the set S t contains exactly one element s t such that D s t = D i , that is s = T -1 (s i ). Moreover, as G is permutation-free, so is G t . So by Theorem 2.33 it is the structure group of the cycle set S t .

In particular, this can be used to work on the columns in G: if we want an element of G with coefficient powers tuple (a 1 , . . . , a n ) on the columns, we can work in G t , use the Π of Dehornoy's calculus to obtain an elements g t in G t with cp(g t ) = (a 1 , . . . , a n ) and transpose it to get g in G with q a i on the i-th column. Proposition 2.68. For any k ∈ N, ψ(s [k] )(s) = T k (s). In particular, the map s → ψ(s [k] )(s) is a bijection of S.

Proof. For k = 0, s [0] = 1 so both sides of the equality are s. For k = 1, this is just the definitions ψ(s)(s) = s * s = T (s). Now proceed by induction:

Recall that, by Proposition 2.19,

ψ(s [k+1] )(s) = ψ(T k (s)) • ψ(T k-1 (s)) • • • • • ψ(s) (s) = ψ(T k (s))(ψ(s [k] )(s)).
So by the induction hypothesis ψ(s

[k+1] )(s) = ψ(T k (s))(T k (s)) = T k (s) * T k (s) = T k+1 (s).
As T is a bijection, so is T k .

Corollary 2.69. For k in N and s in S,

let t = (T k ) -1 (s) then s [-k] = Π k (t, . . . , t) -1 .
Proof. Let t ∈ S, we have

(t [k] ) -1 = (D k t P t [k] ) -1 = P -1 t [k] D -k t = ψ(t [k] ) -1 D -k t P -1 t [k] = D -k ψ(t [k] )(t) P -1 t [k] = D -k T k (t) P -1 t [k] .
Thus, if t = (T k ) -1 (s), we find

D (t [k] ) -1 = D -k s .
Proposition 2.70 ([7]). The map (s, t) → (s * t, t * s) is bijective.

Proof. As S is finite, so is S×S, so we only have to show injectivity, i.e. assume s * t = s * t and t * s = t * s for some s, t, s , t ∈ S.

Since Π 2 (s, t) = s(s * t) = t(t * s) = Π 2 (t, s), we get Π 2 (s, t)Π 2 (s , t ) -1 = s(s * t)(s * t ) -1 s -1 = ss -1

by hypothesis and then as previously ss

-1 = D s D -1 ψ -1 (s)(s * s ) P s P -1 s . We also have Π 2 (s, t)Π 2 (s , t ) -1 = Π 2 (t, s)Π 2 (t , s ) -1 = tt -1 = D t D -1
ψ -1 (t)(t * t ) P t P -1 t . By unicity of the diagonal part, we must have

D s D -1 ψ -1 (s)(s * s ) = D t D -1 ψ -1 (t)(t * t ) , i.e. D s D ψ -1 (t)(t * t ) = D t D ψ -1 (s)(s * s ) .
Because each term on each side corresponds to a diagonal matrix with only one q, we have either D s = D t and so t = s by the previous lemma, or s = ψ -1 (s)(s * s ), thus s * s = s * s and again by the previous lemma s = s , so ss -1 = 1 = tt -1 and finally t = t . In both cases, we are done. Proposition 2.71. Any element g ∈ G can be decomposed as a reduced right-fraction in M , that is:

∃f, h ∈ M, g = f -1 h. with λ(g) = λ(f ) + λ(h).
Proof. The proof is essentially the same as in Proposition 2.24. Take a reduced decomposition of g as product of elements in S ∪ S -1 , the defining relations of G give

s(s * t) = t(t * s) ⇐⇒ s -1 t = (s * t)(t * s) -1 .
From the previous proposition, for any couple (s , t ) ∈ S 2 there exists (s, t) such that (s * t, t * s) = (s , t ), thus we can inductively use the relations s t -1 = (s * t)(t * s) -1 = s -1 t to "move" all inverses of the generators to the left in a decomposition of g, which gives the desired form.

From Propositions 2.24 and 2.71 we deduce:

Corollary 2.72 ([7]). G is the group of fractions of M .

This also implies that G is a Garside group.

Bounding of the Dehornoy's class

We fix a finite cycle set (S, * ) of size n with structure monoid (resp. group) M (resp. G), of Dehornoy's class d > 1 and associated germ G.

Definition 3.1. The permutation group G S associated to a cycle set S is the subgroup of

S n generated by ψ(s i ), 1 ≤ i ≤ n.
When the context is clear we will simply write G.

G is precisely the image of the map sending g in G to P g . Note that, as P σ P τ = P τ σ , we have that ψ(gh) = ψ(h)ψ(h), thus an antimorphism. This won't pose problem here, as we'll only use ψ(

s n ) = ψ(s) n . Definition 3.2 ([2]). A subset X of S is said to be G-invariant if for every s ∈ S, ψ(s)(X) ⊂ X. S is called decomposable if there exists a proper partition S = X Y such that X, Y are G S -invariant.
In this case (X, * | X ) and (Y, * | Y ) are also cycle sets.

A cycle set that is not decomposable is called indecomposable.

Example 3.3. For S = {s 1 , s 2 , s 3 , s 4 } and ψ(s 1 ) = ψ(s 2 ) = (2143), ψ(s 3 ) = ψ(s 4 ) = (2134), we have G = (2143), (2134) < S n . We see that X = {s 1 , s 2 } and Y = {s 3 , s 4 } are both G-invariant and their respective cycle set structure are given by ψ X (s 1 ) = ψ X (s 2 ) = ( 12) and ψ Y (s 3 ) = ψ Y (s 4 ) = (34).

In personal communications [START_REF] Sastriques-Guardiola | Personnal Communications[END_REF], the following conjecture was mentionned:

Conjecture 3.4 ([20]). If S is indecomposable then d ≤ n.
Note that, taking S = {s 1 , . . . , s n } with ψ(s) = (12 . . . n) for all s provides an indecomposable cycle set that attains this bound.

Using a python program based on the proof of Proposition 2.46, we find the following maximum values of the class of cycle sets of size n: n 3 4 5 6 7 8 9 10 d max 3 4 6 8 12 15 24 30 This corresponds to the OEIS sequence A034893 "Maximum of different products of partitions of n into distinct parts", studied in [START_REF] Došlić | Maximum Product over Partitions into Distinct Parts[END_REF] where the following is proved: Lemma 3.5 ([10]). Let n ≥ 2 be written as n = T m + l where T m is the biggest triangular number (T m = 1 + 2 + • • • + m) with T m ≤ n (and so l ≤ m). Then the maximum value

a n = max k i=1 n i k ∈ N, 1 ≤ n 1 < • • • < n k , n 1 + • • • + n k = n is given by a n = a Tm+l =        (m+1)! m-l , 0 ≤ l ≤ m -2 m+2 2 m!, l = m -1 (m + 1)!, l = m.
This leads to the following conjecture: Conjecture 3.6. The class d of S is bounded above by a n and the bound is minimal.

Note that the set map Π : Z n → G allows us to transport the abelian group structure of Z n to G as follows: Proposition 3.7. There exists a commutative group structure on G denoted (G, +) such that for all g, h in G, g + h is the unique element such that

D g+h = D g D h .
Proof. This is a direct consequence of Theorem 2.29. This structure corresponds to the structure of left braces, see for instance [START_REF] Cedó | Left Braces: Solutions of the Yang-Baxter Equation[END_REF].

Proposition 3.8. There exist g , h in

G such that g + h = gh = hg with D h = g -1 D h and D g = h -1 D g . Moreover, if g, h are in M with g = Π k (t 1 , . . . , t k ) and h = Π l (u 1 , . . . , u l ) then g + h = Π k+l (t 1 , . . . , t k , u 1 , . . . , u l ), and g , h are in M . Proof. By definition g + h = D g D h P g+h . Let h = g -1 (g + h) then h = P -1 g D h P g+h = g -1 D h P -1 g P g+h , thus D h = g -1 D
h by the unicity of monomial left-decomposition. And similarly for g using g + h = h + g.

For the second part, the Π-expression is a consequence of Proposition 2.9. Then, by the first statement g (resp. h ) only has non-negative coefficient-powers iff g (resp. h) does, which is equivalent to being in M . Proposition 3.9. The additive commutative structure (M, +) induces an abelian group structure on G compatible with the map ψ : M → G.

Proof. Let σ, τ be in G and g, h in M such that ψ(g) = σ and ψ(h) = τ (i.e. P g = P σ , P h = P τ ). We will show that P g+h does not depend on g and h but only on σ and τ , so that σ + τ is well-defined as ψ(g + h).

By the commutativity of (M, +), it suffices to show that σ + τ does not depend on the choice of the representative g of σ. From Proposition 3.8 we have the existence of h in M such that g + h = gh and D h = g -1 D h which only depends on h and P g = P σ . As h is uniquely determined by D h , it does not depend on the choice of g, so neither does P h . Finally, we have that P g+h = P g P h is the product of terms only depending on σ = ψ(g).

As a consequence we obtain the following result: Proposition 3.10 ( [START_REF] Cedó | Left Braces: Solutions of the Yang-Baxter Equation[END_REF]). The class d divides the order of G. In particular d divides n!. Proof. For s ∈ S, the set {s [k] | k ∈ Z} is a subgroup of (G, +), and the smallest integer d s such that s [ds] is diagonal corresponds to the order of ψ(s) in (G, +), which thus divides |G|.

As d is the lcm of all the d s , s ∈ S, it also divides |G|.

The landau function g : N * → N * ( [START_REF] Landau | Über Die Maximalordnung Der Permutationen Gegebenen Grades[END_REF]) is defined as the largest order of a permutation in S n .

Proposition 3.11. If S is square-free and G abelian then d ≤ a n

That is, under these conditions the bound part of Conjecture 3.6 holds.

Proof. If S is square-free, then for all s ∈ S we have by definition T (s) = s, so for any k ∈ Z, s [k] = sT (s) . . . T k-1 (s) = s k so {s [k] | k ∈ Z} is a subgroup of (G, •) and the smallest integer d s such that s [ds] is diagonal corresponds to the order of ψ(s) in (G, •), which thus divides e(G) the exponent of G (the lcm of the orders of every element). So d will also divide e(G).

As G is abelian and finite, there exists an element with order equal to its exponent, so the exponent is bounded by the maximal order of an element, i.e. d | e(G) ≤ g (n).

By the decomposition in disjoint cycles, g(n) is equal to the maximum of the lcm of partitions of n:

g(n) = max ({lcm(n 1 , . . . , n k )|k ∈ N, 1 ≤ n 1 ≤ • • • ≤ n k , n 1 + • • • + n k = n})
Moreover, by properties of the lcm, if 1 ≤ n i = n j , as lcm(n i , n j ) = n i , the max is unchanged by replacing n j by only 1's. And as the lcm of a set is bounded above by the product of the elements, we have g(n) ≤ a n . Thus d ≤ g(n) ≤ a n . Proposition 3.12. The followings hold:

(i) ψ : G → G factorizes through the projection G → G (ii) We have the following divisibilities:

• o(T ) | d • d | #G • #G | d n
where o(T ) is the order of the diagonal permutation T , #G denotes its order |G| (to avoid confusion with | for divisibility).

Proof. (i) follows from the definition of d as ψ(s [d] ) = id.

For (ii), the first divisibility is Proposition 2.66, the second is Proposition 3.10 and the third is (i).

For a positive integer k, denote by π(k) the set of divisors of k.

Corollary 3.13. We have π(d) = π(#G).

In particular, d is a prime power iff #G is a prime power.

This means that our later results, which will involve the condition "d is a prime power" can also be restated for #G. In particular, π(n) ⊆ π(#G) = π(d), and thus if d is a prime power then n is also a power of the same prime. Proof. By [START_REF] Etingof | Set-Theoretical Solutions to the Quantum Yang-Baxter Equation[END_REF] S is indecomposable iff G acts transitively on S. By the orbit stabilizer theorem, for any s in S we have #Orb(x) = #G #Stab(x) . So if S is indecomposable there is a unique orbit of size n so n divides #G. The last statements are a direct consequence of this divisibility and the previous corollary. Lemma 3.15. If S is indecomposable and G is abelian, then n = |G| Proof. a Again by [START_REF] Etingof | Set-Theoretical Solutions to the Quantum Yang-Baxter Equation[END_REF] S is indecomposable iff G acts transitively on S. Let x 0 ∈ S, by transitivity for all x ∈ S, there exists σ ∈ G such that x = σ(x 0 ). Let τ ∈ G be such that we also have x = τ (x 0 ), we will show that τ = σ. For all y ∈ S, there exists ν ∈ G such that y = ν(x), thus σ(y) = σ(ν(x)) = σ(ν(τ (x 0 )) = τ (ν(σ(x 0 )) = τ (y). So an element of G is uniquely determined by its image of x 0 , thus |S| ≥ |G|, and the other inequality follows by transitivity.

• Let k ≥ 1 and G [k] be the subgroup of G generated by S [k] = {s [k] | s ∈ S}. The following result was simultaneously introduced in [START_REF] Lebed | Involutive Yang-Baxter: Cabling, Decomposability[END_REF]: Proposition 3.16. For ≥ 1, G [k] induces a cycle set structure on S [k] .

Proof. Recall that ψ(s [k] )(t) = Ω k+1 (s, . . . , s, t) for all s, t ∈ S, and note that

s [k] t [k] = D k s P s [k] D k t P t [k] = D k s s [k] D k t P s [k] P t [k] = D k s D k ψ(s [k] ) -1 (t) P s [k] P t [k] .
a https://math.stackexchange.com/a/1316138 For all s [k] , t [k] ∈ S [k] , define s [k] t [k] as Ω k+1 (s, . . . , s, t) [k] . Then we have

s [k] (s [k] t [k] ) = D k s D k ψ(s [k] ) -1 (s [k] t [k] ) P s [k] P t [k] = D k s D k t P s [k] P t [k] . By symmetry, we have that D s [k] (s [k] t [k] ) = D t [k] (t [k] s [k]
) . Thus as G is permutation-free we conclude that s [k] (s [k] t [k] ) = t [k] (t [k] s [k] ).

All generators satisfy the conditions of Theorem 2.33 with

D s i = D k i so (S [k] ,
) is a cycle set. Remark 3.17. Alternatively, one can directly show that satisfies Equation (1): let s, t, u ∈ S, then we have (s [k] t [k] ) (s [k] u [k] ) = Ω k+1 (s, . . . , s, t) [k] Ω k+1 (s, . . . , s, u) [k] = Ω k+1 (Ω k+1 (s, . . . , s, t), . . . , Ω k+1 (s, . . . , s, t), Ω k+1 (s, . . . , s, u)) [k] .

By definition of Ω (see [START_REF] Dehornoy | Set-Theoretic Solutions of the Yang-Baxter Equation, RC-calculus, and Garside Germs[END_REF] eq 4.8), the two expressions Ω p+q (x 1 , . . . , x p , y 1 , . . . , y q ) and Ω q (Ω p+1 (x 1 , . . . , x p , y 1 ), . . . , Ω p+1 (x 1 , . . . , x p , y q )) coincide. Thus (s [k] t [k] ) (s [k] u [k] ) = Ω 2k+1 (s, . . . , s, t . . . , t, u). As Ω is invariant by permutation all but the last coordinate, we have Ω 2k+1 (s, . . . , s, t, . . . , t, u) = Ω 2k+1 (t, . . . , t, s, . . . , s, u). Thus, we conclude that: This means that this construction provides, at most, d different cycle sets.

s [k] t [k] ) (s [k] u [k] ) = (t [k] s [k] ) (t [k] u [k] ).
Proof. Recall that (s [k] ) [j] = s [kj] . Thus (s [k] ) [a] is diagonal when ka is a multiple of d, so we deduce that S [k] is of class lcm(d,k)

k = d gcd(d,k)
. By definition of d, we have that (S [d] , ) is the trivial cycle set (ψ(s) = id), thus ψ(s [d+1] ) = ψ(s).

Sylow subgroups and decomposition

Recall that for k > 1, Σ k n denotes the group of monomial matrices with non-zero coefficients powers of ζ k , and ι kl k is the embedding Σ k n → Σ kl n sending ζ k to ζ l kl . Given two subgroups H, K < G, their internal product subset is defined by HK = {hk | h ∈ H, k ∈ K}. If H and K have trivial intersection and HK = KH, the set product HK has a natural group structure called the Zappa-Szép product of H and K. We apply this to the Sylow-subgroups of the germs to obtain that any cycle set can be obtained as a Zappa-Szép product of cycle sets with coprime classes.

. Given two subgroups G < Σ k n , H < Σ l n by G m H we denote the subset ι m k (G)ι m l (H) of Σ m n .
Identifying G and H with their image in Σ m n , we say that they commute ( [START_REF] Ledermann | Introduction to Group Theory[END_REF]) if GH = HG as sets, i.e. for any (g, h) in G × H, there exists a unique (g , h ) in (G × H) such that gh = h g . We now construct a candidate S 1 d S 2 for which G could be the germ. This candidate is not, in general a cycle set, but if it is, its class is a divisor of d. Then we will state the condition for it to be a cycle set.

For clarity, we will put a subscript to distinguish between the respective structures of S 1 and S 2 : ψ 1 (s) will denote the permutation given by * 1 , and s [k] Compute

g 1 = s [u] 1 i ∈ G 1 5: Let σ = ψ 1 (s [u] i ) 6: Compute g 2 = s [v] 2 σ(i) ∈ G 2 7: Let ψ(s i ) be the permutation part of ι d d 1 (g 1 )ι d d 2 (g 2 ) 8: return S 1 d S 2 = (S, * ) with s i * s j = s ψ(s i )(j) .
Remark 4.4. The heart of the algorithm is lign 6 which relies on the following

D k i P σ D l j P τ = D k i D l σ -1 (j) P τ σ .
To obtain an element with coefficient-powers 1 on the i-th coordinate and zero elsewhere, we have to take j = σ(i) with here σ = ψ(s

[k] 1 i
) and as we apply ι d on the elements (in S 1 this does q → q d 2 and in S 2 q → q d 1 ), we obtain

D s i = D d 2 u+d 1 v i = D i from lign 1.
Example 4.5. Take two cycle sets of size n = 5 and class respectively 2 and 3, and apply Algorithm 1 providing a candidate for a cycle set of class 6:

Let S 1 = {s 1 , . . . , s 5 } and S 2 = {s 1 , . . . , s 5 }, with (S 1 , ψ 1 ), (S 2 , ψ 2 ) given by:

ψ 1 (s 1 ) = ψ 1 (s 3 ) = (1234) ψ 1 (s 2 ) = ψ 1 (s 4 ) = (1432) ψ(s 5 ) = id ψ 2 (s 1 ) = ψ 2 (s 2 ) = (354) ψ 2 (s 3 ) = ψ 2 (s 4 ) = ψ 2 (s 5 ) = (345)
Where S 1 is of class d 1 = 2 and S 2 of class d 2 = 3.

Consider their respective germs G 1 and G 2 of order 2 5 and 3 5 . Then define G = G 1 6 G 2 over the basis S = {s 1 , . . . , s 5 }. For instance:

ι 6 2 (s 1 ) = ι 6 2               0 ζ 2 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1               =        0 ζ 3 6 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1        0 1 0 0 0 0 0 0 0 1 0 0 ζ 6 0 0 1 0 0 0 0 0 0 0 1 0       
This will be our candidate for s 3 . Doing this for all the generators we find: ψ(s 1 ) = (124)(35), ψ(s 2 ) = (1532), ψ(s 3 ) = (1254), ψ(s 4 ) = (132)(45), ψ(s 5 ) = (354).

Unfortunately, this isn't a cycle set: (s 1 * s 2 ) * (s 1 * s 1 ) = s 4 * s 2 = s 1 whereas (s 2 * s 1 ) * (s 2 * s 1 ) = s 5 * s 5 = s 4 . This also means that, G is not permutation-free or in Dehornoy's Calculus terms: with our candidates s 1 , s 2 we have that Π 2 (s 1 , s 2 ) and Π 2 (s 2 , s 1 ) both have coefficient-powers (1, 1, 0, 0, 0) but different permutations. Proposition 4.6. If G 1 and G 2 commute, then S 1 and S 2 are -compatible.

In this case, G

= G 1 d G 2 is the Zappa-Szép product of G 1 and G 2 . Proof. As d 1 and d 2 are coprime, it is clear that G 1 ∩ G 2 = {1}. By ([17], Product Theorem), G is a subgroup of Σ k n if and only if G 1 and G 2 commute, i.e. G = G 1 d G 2 = G 2 d G 1 . As G 1 and G 2 have different (non-zero) coefficient- powers, a product g 1 g 2 of two non-trivial elements from ι d d 1 (G 1 ) and ι d d 2 (G 2
) cannot be a permutation matrix.

With Algorithm 1, we know that G respects condition (ii) for Theorem 2.33, and we've seen it also satisfies condition (i), finishing the proof. Remark 4.7. To check whether G 1 and G 2 commute, we can restrict to the generators and check that:

∀s ∈ S 1 , t ∈ S 2 , ∃s ∈ S 1 ,
i ) = ψ 2 s [v] 2 ψ 1 (s [u] i )(i) • ψ 1 s [u] 1 i with u, v such that d 2 u + d 1 v = 1[d 1 d 2 ].
Proof. We will use the previous proposition and show how Equation 8 naturally arises from considering the commutativity of the germs.For clarity, although our two cycle sets have the same underlying set S = {s 1 , . . . , s n }, we will distinguish where we see those elements by writing s for (S, * 1 ) and s for (S, * 2 ). Let s i ∈ S 1 , s j ∈ S 2 , then in G:

s i s j = D d 2 i P s i D d 1 j P s j = D d 2 i D d 1 ψ 1 (s i ) -1 (j) P s i P s j . We want some s k ∈ S 1 , s l ∈ S 2 such that s i s j = s l s k , i.e: D d 2 i D d 1 ψ 1 (s i ) -1 (j) P s i P s j = D d 1 l D d 2 ψ 2 (s l ) -1 (k) P s l P s k .
As d 1 and d 2 are coprime, they're in particular different, so we must have:

         D d 2 i = D d 2 ψ 2 (s l ) -1 (k) D d 1 ψ 1 (s i ) -1 (j) = D d 1 l P s i P s j = P s l P s k .
From which we first deduce: k = ψ 2 (s l )(i) and j = ψ 1 (s i )(l), or equivalently s k = s l * 2 s i and s j = s i * 1 s l . So taking this k and l we get D s i s j = D s l s k . We are left with last of the three conditions, which then becomes:

P s i P s i * 1 s l = P s l P s l * 2 s i .
As P σ P τ = P τ σ , the last condition is equivalent to

ψ 2 (s i * 1 s l ) • ψ 1 (s i ) = ψ 1 (s l * 2 s i ) • ψ 2 (s l ).
As s l ∈ S 2 , ψ 2 (s i * 1 s l ) is seen as the action of an element of S 2 , so all this becomes equivalent to: ∀s, t, u ∈ S, (s

* 1 t) * 2 (s * 1 u) = (t * 2 s) * 2 (t * 2 u).
Remark 4.9. The condition that the classes are coprime is used, with Bézout's identity, to have generators of the group G (elements with diagonal part D i ). Otherwise, say for instance that the classes are powers of the same prime, d 1 = p a and d 2 = p b with b ≤ a. Then ι d d 2 is the identity and ι d d 1 will add elements with higher coefficient powers (or equal), thus we do not get any new generators (or too many in the case a = b).

We've seen how to construct cycle sets from ones of the same size and coprime classes. Now we show that this is enough to get all cycle sets from just ones of prime-power class:

Let d = p a 1 1 . . . p ar r be the prime decomposition of p (a i > 0 and p i = p j ), and write α i = p a i i for simplicity. We use techniques inspired by [START_REF] Cedó | Primitive Set-Theoretic Solutions of the Yang-Baxter Equation[END_REF] to construct new cycle sets from two with coprime Dehornoy's class.

Fix again a cycle set S of size n and class d > 1, with germ G. By Proposition 3.16, given k > 0 diving d, the subgroup G [k] generated by S [k] = {s [k] | s ∈ S} is the germ of a structure group, and has for elements the matrices whose coefficient-powers are multiples of k. (ii) Two such subgroups commute (i.e.

G [β i ] G [β j ] = G [β j ] G [β i ] ).
(iii) G is the product of all those subgroups. Proof. Fix 1 ≤ i ≤ r, as β divides d, the group G [β i ] corresponds to the subgroup of G of matrices with coefficient-powers in {0, β i , 2β i , . . . , β i (α i -1)} and thus has cardinal α n i = p a i n i , so it is a p i -Sylow subgroup of G. For s, t ∈ S we have that s [β i ] t [β j ] has a q β j on some row, thus is left-divisible by t [β j ] for some t ∈ S, i.e. s [β i ] t [β j ] = t [β j ] s [β i ] for some s ∈ S.

We've seen that the G [β i ] are p i -Sylow subgroups of the abelian group (G, +), so by cardinality it is the direct sum of those subgroups. By Proposition 3.8 for any g, h ∈ G, there exists h ∈ G such that g + h = gh , where D h = g -1 D h , so if h is in some G [k] , so is h . Projecting onto G, we have that any element g can be expressed as a sum of g i ∈ G

[β i ]
and thus a product of g i ∈ G Here, G decomposes as the Zappa-Szép product G [START_REF] Catino | The Matched Product of Set-Theoretical Solutions of the Yang-Baxter Equation[END_REF] 6 G [2] of its 2-and 3-Sylow. If we denote by (S 2 , ψ 2 ) and (S 3 , ψ 3 ) their respective cycle set structure then we find: [βr] . As the germ can be used to reconstruct the structure group and thus the cycle set, the following theorem summarizes these results from an enumeration perspective, that is constructing all solutions of a given size. Theorem 4.12. Any cycle set can be obtained as the Zappa-Szép product of cycle sets of class a prime power. Proof. Any cycle set is determined by its structure monoid, which can be recovered from the germ. By Lemma 4.10 and the above construction, the germ can be decomposed and reconstructed from its Sylows, which also determine cycle set by Proposition 3.16.

Remark 4.13. The class of the cycle set constructed will Algorithm 1 will, in general, only be a divisor of the product of the prime-powers. This happens because nothing ensures that, for instance, the cycle set obtained is not trivial: we only know that s [d 1 d 2 ] is diagonal, but it is not necessarily minimal. Remark 4.14. This construction is similar to the matched product of braces B 1 B 2 appearing in [START_REF] Bachiller | Extensions, Matched Products, and Simple Braces[END_REF][START_REF] Catino | The Matched Product of Set-Theoretical Solutions of the Yang-Baxter Equation[END_REF]. Key differences are that we directly construct a cycle set with permutation group B 1 B 2 (whereas the authors of [START_REF] Catino | The Matched Product of Set-Theoretical Solutions of the Yang-Baxter Equation[END_REF] construct one over the set B 1 B 2 ) and that our construction doesn't rely on groups of automorphisms thanks to the natural embedding ι kl k . Moreover, instead of classifying all braces, the existence of the germs suggests it is enough to classify braces with abelian group (Z/dZ) n for all d and n to recover all cycle-sets. Corollary 4.15. Any cycle set is induced (in the sense of using the decomposability and Zappa-Szép product) by indecomposable cycle sets of smaller size and class, both powers of the same prime.

Proof. Let S be obtained from the germ as an internal product of S 1 , . . . , S r of classes respectively p a 1 1 , . . . , p ar r with distinct primes. Then, consider a decomposition of each S i as indecomposable cycle sets: so up to a change of enumeration, the matrices in the structure group of S i are diagonal-by-block with each block corresponding to a cycle set, so with class dividing the class p a i i of S i , thus also a power of p i . By Lemma 3.14, the size of those indecomposable cycle sets must also be powers of p i . However, as far as the author knows, there is no "nice" way, given two cycle sets, to construct all cycle sets that decompose on those two, thus the above result is an existence result but not a constructive one, unlike the Zappa-Szép product previously used. Remark 4.16. Starting from a cycle set, we first write it as a Zappa-Szép product of its Sylows and then decompose each Sylow-subgroup if the associated cycle set is decomposable. If one proceeds the other way, first decomposing and then looking at the Sylows of each cycle set of the decomposition, we obtain less information. For instance, if S = {s 1 , . . . , s 6 } with ψ(s i ) = (1 . . . 6) for all i, then S is not decomposable, but the cycle sets obtained from its Sylows S [2] and S [3] are decomposable (ψ 2 (s i ) = ( 14)(25)(36) and ψ 3 (s i ) = (135)(246) for all i, having respectively 3 and 2 orbits).

Example 4.17. In Example 4.11, 3 does not divide 8 so S 3 has to be decomposable, and indeed it decomposes as S 3 = {s 1 , s 3 , s 5 } {s 2 , s 4 , s 6 } {s 7 , s 8 }. For n = 10, we find that there is approximately 67% of cycle sets that have class a prime-power (∼ 3.3 out of ∼ 4.9 millions). We hope that this number greatly reduces as n increases (as hinted by the previous values, for n = 4 it is 99%), as more values of d are possible (Conjecture 3.6).

Corollary 1 . 2 .

 12 Let m, m be monomial matrices. Then we have D mm = D m ψ(m) D m and ψ(mm ) = ψ(m ) • ψ(m). To simplify notations we will sometimes only write m D m for ψ(m) D m . As a final example, let m = which decomposes with D m = diag(a, b, c), D m = diag(x, y, z) and ψ(m) = (123), ψ(m ) = (13). We find ψ(m ) • ψ(m) = (13) • (123) = (12) and D m ψ(m)

  By induction, this gives the last statement.Corollary 2.20. Any tuple of non-negative integers (c 1 . . . , c n ) ∈ N n can be realized as the coefficient-powers tuple of a matrix in Θ(M S ).Proof. Let l =i c i and take the l-tuple containing c i times the element s i . By the previous proposition, Π l applied to this tuple gives the expected result.

Example 2 .

 2 21. As in 2.10 take S = {s 1 , s 2 , s 3 , s 4 } with

  k s P σ k . The Dehornoy's class of S is n and G is generated by the s i = diag(1, . . . , ζ n , . . . , 1)P σ where ζ n = exp( 2iπ n ).

Lemma 2 .

 2 65 ([19]). ∀s, s ∈ S, s * s = s * s ⇐⇒ s = s . Proof. If s = s * s then trivially s * s = s * s . Suppose s * s = s * s , and consider g = ss -1 , we want to show g = 1.

Proof.Lemma 3 . 14 .

 314 As d divide #G any divisor of d is a divisor of #G. Conversely, if p is a prime divisor of #G then it divides d n and thus divides d. If S is indecomposable then n divides #G.

Proposition 3 . 18 .

 318 Let k be a positive integer smaller than d, then (S[k] , ) is of class d gcd(d,k) .Moreover, (S [d+1] , ) is the same, as a cycle set, as (S, * ).

Definition 4 . 1 .

 41 Let k, l be integers such that k, l > 1. Let m be a common multiple of k and l, with m = ka = lb for some a, b ≥ 1

Remark 4 . 2 .

 42 This operation can be thought of as taking elements of G and H, changing appropriately the roots of unity (with ζ k = ζ a m and ζ l = ζ b m) and taking every product of such elements (we embed G and H in Σ m n and take their product as subsets). When k and l are coprime, G and H can be seen as subgroups of Σ

Lemma 4 . 10 .

 410 Let β i = d α i then (i) For each i, G [β i ] is a p i -Sylow subgroup of G.

[β i ] . Example 4 . 11 .

 411 The first example where S is indecomposable but has class product of different primes is n = 8, d = 6 given by: ψ(s 1 ) = (12)(36)(47)(58), ψ(s 2 ) = (1658)(2347), ψ(s 3 ) = (1834)(2765), ψ(s 4 ) = (12)(38)(45)(67), ψ(s 5 ) = (1438)(2567), ψ(s 6 ) = (1856)(2743), ψ(s 7 ) = (16)(23)(45)(78), ψ(s 8 ) = (14)(25)(36)(78)

ψ 2 (

 2 s 1 ) = ψ 2 (s 2 ) = (1476)(2583), ψ 2 (s 3 ) = ψ 2 (s 6 ) = (18)(27)(36)(45), ψ 2 (s 4 ) = ψ 2 (s 5 ) = (1674)(2385), ψ 2 (s 7 ) = ψ 2 (s 8 ) = (12)(34)(56)(78)andψ 3 (s 1 ) = ψ 3 (s 3 ) = ψ 3 (s 5 ) = ψ 3 (s 7 ) = (135)(264), ψ 3 (s 2 ) = ψ 3 (s 4 ) = ψ 3 (s 6 ) = ψ 3 (s 8 ) = (153)(246).Lemma 4.10 can be rephrased as G = G [β 1 ] d . . . d G

Corollary 4 . 18 .

 418 Let N (n, d) be the number of cycle sets of size n and of class a divisor of d = p a 1 1 . . . p ar r . Then we have: N (n, d) ≤ i N (n, p a i i ).

Proposition 2.19. Let

  • Ω and Π = Θ • Π the evaluation in the representation of the constructions from Section 2.2, that is Π k (t 1 , . . . , t k ) = Θ(Π(t 1 , . . . , t k )). t 1 , . . . , t k be in S, then D Π k (t 1 ,...,t k ) = D t 1 . . . D t k and P Π k (t 1 ,...,t k ) = P Ω 1 (t 1 ) . . . P Ω k (t 1 ,...,t k ) .

	Or equivalently for all s in S, ψ(Π k (t 1 , . . . , t k ))(s) = Ω k+1 (t 1 , . . . , t k , s).
	Proof. We proceed by induction: for r = 1, Π 1 (t 1 ) = t 1 and there is nothing to prove.
	Assume r ≥ 1 and the property true for r -1. Then, by definition we have Π(t 1 , . . . , t k ) =
	Π k-1 (t 1 , . . . , t k-1 ) • Ω k (t 1 , . . . , t k ), so by the induction hypothesis
	Π k (t 1 , . . . , t k ) = D t 1 . . . D t k-1 P Ω 1 (t 1 ) . . . P Ω k-1 (t 1 ,...t k-1 ) D Ω k (t 1 ,...,t k ) P Ω k (t 1 ,...,t k )
	Note that Ω k (t 1 , . . . , t k ) = Ω k-1 (t 1 , . . . , t k-1 ) * Ω k-1 (t 1 , . . . , t k-2 , t k ). So by Proposition
	2.15 we get

  m n with trivial intersection, and so if they commute we have that G m H is a group called the Zappa-Szép product of G and H ([17], Product Theorem). Let (S, * 1 ), (S, * 2 ) be two cycle sets, over the same set S, of coprime respective classes d 1 , d 2 and germs G 1 , G 2 . Let d = d 1 d 2 and G = G 1 d G 2 (which, in general, is only a subset of Σ d n ), and we identify each G i with its image in G. Definition 4.3. S 1 and S 2 are said to be -compatible if G is the structure group of some cycle set S 1 S 2 , called the Zappa-Szép product of S 1 and S 2 .

  2 will denote an element of M 2 . Constructing S 1 d S 2 Input: A set S with two cycle sets structure * 1 , * 2 on S of coprime classes d 1 , d 2 Output: A couple (S, * ) with * a binary operation

	Algorithm 1

1: Compute (u, v) the solution to Bézout's identity d 2 u + d 1 v = 1[d] 2: Set a 3: for i = 1 to n do 4:

  t ∈ S 2 such that st = t s .

Proposition 4.8. If S 1 and S 2 satisfy the following "mixed" cycle set equation

∀s, t, u ∈ S, (s * 1 t) * 2 (s * 1 u) = (t * 2 s) * 2 (t * 2 u) (8)

then S 1 and S 2 are -compatible and (S = S 1 d S 2 , * ) is a cycle set.

Explicitly, from Algorithm 1, we have ψ(s

Normandie Univ, UNICAEN, CNRS, LMNO, 14000 Caen, France Email address: edouard.feingesicht@unicaen.fr