# On Equivalence of Known Families of APN Functions in Small Dimensions

Bo Sun  University of Bergen
Bergen, Norway
<EMAIL_ADDRESS>

###### Abstract

In this extended abstract, we computationally check and list the CCZ-
inequivalent APN functions from infinite families on
$\operatorname{\mathbb{F}}_{2^{n}}$ for $n$ from $6$ to $11$. These functions
are selected with simplest coefficients from CCZ-inequivalent classes. This
work can simplify checking CCZ-equivalence between any APN function and
infinite APN families.

##  I Introduction

A cryptosystem is the system provides encryption and decryption. Algorithms,
protocols, keys are the fundamental components in any cryptosystem. Algorithms
impact how the encryption and decryption take place and they encompass
symmetric algorithms and asymmetric algorithms. Symmetric algorithms use same
keys for encryption and decryption, while asymetrric algorithms use different
keys. DES, AES, and blowfish are well known symmetric algorithms. Symmetric
algorithms are the oldest and most used algorithms among cryptosystems.
Symmetric algorithms have two main types, one is block cipher which encrypts
fixed-size blocks at a time and the other one is stream cipher which encrypts
one bit or byte at a time.

One critical component in symmetric block cipher is substitution-box (S-box).
Substitution substitutes some values to other values instead. The design of
S-boxes in symmetric block cipher is based on Claude Elwood Shannon’s theory
about designing secure cryptosystems. Shannon is called the father of
contemporary cryptography. In particular, he theoretically deduced that both
confusion and diffusion should be present in a computationally secure
cryptosystem. Confusion is for making the relation between ciphertext and keys
as complex as possible. Diffusion is for spreading the influence of any bit of
plaintext over ciphertext as much as possible.

S-boxes provide confusion for symmetric block cipher cryptosystems. They take
some number of bits of input from one finite field and transform them into
output from other finite field. The reasons that S-boxes are the most critical
components in symmetric block cipher are as following: 1) They are the only
nonlinear components in block cipher; 2) They provide confusion to block
cipher; 3) There is strong connection between cryptographic attacks and
certain properties of S-boxes.

##  II Preliminaries

For positive integers $n$ and $m$, a Boolean function $f$ is a function from
finite filed $\operatorname{\mathbb{F}}_{2^{n}}$ to finite filed
$\operatorname{\mathbb{F}}_{2}$. Likewise, a function $F$ is a vectorial
Boolean function if it is from finite filed
$\operatorname{\mathbb{F}}_{2^{n}}$ to another finite filed
$\operatorname{\mathbb{F}}_{2^{m}}$. Any vectorial boolean function
$F:\operatorname{\mathbb{F}}_{2^{n}}\rightarrow\operatorname{\mathbb{F}}_{2^{m}}$
can be represented by $m$ Boolean functions as
$F(x_{1},x_{2},...,x_{n})=\\{f_{1}(x_{1},x_{2},...,x_{n}),...,f_{m}(x_{1},x_{2},...,x_{n})\\}$.
$f_{1},f_{2}...f_{m}$ are called coordinate functions of $F$ and each of them
has $n$ variables. Any nonzero linear combination of the coordinate functions
is called a component function of $F$. The mathematical nature of S-boxes is
represented by vectorial Boolean functions.

As we mentioned, there is close connection between successfulness of many
attacks on symmetric block cipher and certain properties of S-boxes (or
vectorial Boolean functions). Two most well known and powerful attacks on
block cipher are linear attacks and differential attacks. Linear attacks try
to find the linear relationship between plaintext and ciphertext in order to
deduce keys. Nonlinearity of S-boxes (defined below) can measure the
resistance of block cipher to linear attacks. Differential attacks study how
the difference of input can impact the difference of output. The differential
uniformity of S-boxes (defined below) define the resistibility to differential
attacks. Correspondingly, algebraic degree of S-boxes matters with the
resistance to high order differential attacks. The low degree multivariate
equation of S-boxes influences the resistance to algebraic attacks. The
univariate polynomial degree of S-boxes measures the ability against
interpolation attacks. There are also other attacks, the resistance to those
attacks highly depend on one or more properties of S-boxes. In this extended
abstract, we will only focus on nonlinearity, differential uniformity and
algebraic degree of S-boxes.

The nonlinearity of any vectorial Boolean function
$F:\operatorname{\mathbb{F}}_{2^{n}}\rightarrow\operatorname{\mathbb{F}}_{2^{m}}$
is the minimum hamming distance between all nonzero linear Boolean functions
over $\operatorname{\mathbb{F}}_{2^{n}}$ and component functions of $F$. The
nonlinearity $N(F)$ can also be represented by Walsh transofrm. Walsh
transform $\lambda_{F}$ is defined as:

$\lambda_{F}(a,b)=\sum\limits_{x\in\operatorname{\mathbb{F}}_{2^{n}}}(-1)^{b\cdot
F(x)+a\cdot x},a\in\mathbb{F}_{2^{n}},b\in\mathbb{F}_{2^{m}}^{*},$

and corresponding Walsh spectrum is the set as following:

$\\{\lambda_{F}(a,b):a\in\mathbb{F}_{2^{n}},b\in\mathbb{F}_{2^{m}}^{*}\\}.$

TABLE I: Known APN power functions $x^{d}$ on $\operatorname{\mathbb{F}}_{2^{n}}$ Functions | Exponents $d$ | Conditions | Proven
---|---|---|---
Gold | $2^{i}+1$ | $\gcd(i,n)=1$ | [7, 8]
Kasami | $2^{2i}-2^{i}+1$ | $\gcd(i,n)=1$ | [9, 10]
Welch | $2^{t}+3$ | 3 | [11]
Niho |  $2^{t}+2^{\frac{t}{2}}-1$, $t$ even | $n=2t+1$ | [12]
|  $2^{t}+2^{\frac{3t+1}{2}}-1$, $t$ odd |  |
Inverse | $2^{2t}-1$ | $n=2t+1$ | [13, 8]
Dobbertin | $2^{4i}+2^{3i}+2^{2i}+2^{i}-1$ | $n=5i$ | [14]
TABLE II: Families of APN polynomial functions on $\operatorname{\mathbb{F}}_{2^{n}}$ $N^{\circ}$ | Functions | Conditions | References
---|---|---|---
|  |  $n=pk$, $\gcd(k,p)=\gcd(s,pk)=1,$ |
1-2 | $x^{2^{s}+1}+\alpha^{2^{k}-1}x^{2^{ik}+2^{mk+s}}$ |  $p\in\\{3,4\\}$, $i=sk$ mod $p$, $m=p-i,$ | [15]
|  |  $n\geq 12$, $\alpha$ primitive in $\operatorname{\mathbb{F}}_{2^{n}}^{*}$ |
|  |  $q=2^{m}$, $n=2m$, $\gcd(i,m)=1,$ |
3 | $x^{2^{2i}+2^{i}}+bx^{q+1}+cx^{q(2^{2i}+2^{i})}$ | $\gcd(2^{i}+1,q+1)\neq 1,cb^{q}+b\neq 0,$ | [16]
|  | $c\not\in\\{\lambda^{(2^{i}+1)(q-1)},\lambda\in\operatorname{\mathbb{F}}_{2^{n}}\\},c^{q+1}=1$ |
|  |  $q=2^{m},n=2m,\gcd(i,m)=1$, |
4 | $x(x^{2^{i}}+x^{q}+cx^{2^{i}q})$ | $c\in\operatorname{\mathbb{F}}_{2^{n}},s\in\operatorname{\mathbb{F}}_{2^{n}}\backslash\operatorname{\mathbb{F}}_{q},$ | [16]
| $+x^{2^{i}}(c^{q}x^{q}+sx^{2^{i}q})+x^{(2^{i}+1)q}$ | $X^{2^{i}+1}+cX^{2^{i}}+c^{q}X+1$ |
|  | is irreducible over $\operatorname{\mathbb{F}}_{2^{n}}$ |
5 | $x^{3}+a^{-1}{\rm{tr}}_{1}^{n}(a^{3}x^{9})$ | $a\neq 0$ | [17, 18]
6 | $x^{3}+a^{-1}{\rm{tr}}_{3}^{n}(a^{3}x^{9}+a^{6}x^{18})$ |  $3|n$, $a\neq 0$ | [17]
7 | $x^{3}+a^{-1}{\rm{tr}}_{3}^{n}(a^{6}x^{18}+a^{12}x^{36})$ |  $3|n$, $a\neq 0$ | [17]
|  |  $n=3k$, $\gcd(k,3)=\gcd(s,3k)=1,$ |
8-10 | $ux^{2^{s}+1}+u^{2^{k}}x^{2^{-k}+2^{k+s}}+$ | $v,w\in\operatorname{\mathbb{F}}_{2^{k}},vw\neq 1,$ | [19]
| $vx^{2^{-k}+1}+wu^{2^{k}+1}x^{2^{s}+2^{k+s}}$ |  $3|(k+s)$, $u$ primitive in $\operatorname{\mathbb{F}}_{2^{n}}^{*}$ |
|  |  $n=2k$, $\gcd(s,k)=1$, $s,k$ odd, |
11 | $\alpha x^{2^{s}+1}+\alpha^{2^{k}}x^{2^{k+s}+2^{k}}+$ | $\beta\notin\operatorname{\mathbb{F}}_{2^{k}},\gamma_{i}\in\operatorname{\mathbb{F}}_{2^{k}},$ | [19, 20]
| $\beta x^{2^{k}+1}+\sum_{i=1}^{k-1}\gamma_{i}x^{2^{k+i}+2^{i}}$ |  $\alpha$ not a cube |
TABLE III: CCZ-inequivalent APN functions over $\mathbb{F}_{2^{n}}$ from the known APN classes ($6\leq n\leq 11$ and $a$ primitive in $\mathbb{F}_{2^{n}}$) $n$ | $N^{\circ}$ | Functions | Families from Tables I,II | Relation to [22]
---|---|---|---|---
6 | 6.1 | $x^{3}$ | Gold | Table 5: $N^{\circ}$1.1
6.2 | $x^{6}+x^{9}+a^{7}x^{48}$ |  $N^{\circ}$3 | 5: $N^{\circ}$1.2
6.3 | $ax^{3}+a^{4}x^{24}+x^{17}$ |  $N^{\circ}$8-10 | 5: $N^{\circ}$2.3
7 | 7.1 | $x^{3}$ | Gold | Table 7 : $N^{\circ}$1.1
7.2 | $x^{5}$ | Gold | 7 : $N^{\circ}$3.1
7.3 | $x^{9}$ | Gold | 7 : $N^{\circ}$4.1
7.4 | $x^{13}$ | Kasami | 7 : $N^{\circ}$5.1
7.5 | $x^{57}$ | Kasami | 7 : $N^{\circ}$6.1
7.6 | $x^{63}$ | Inverse | 7 : $N^{\circ}$7.1
7.7 | $x^{3}+{\rm{tr}}_{1}^{7}(x^{9})$ |  $N^{\circ}$5 | 7 : $N^{\circ}$1.2
8 | 8.1 | $x^{3}$ | Gold | Table 9 : $N^{\circ}$1.1
8.2 | $x^{9}$ | Gold | 9 : $N^{\circ}$1.2
8.3 | $x^{57}$ | Kasami | 9 : $N^{\circ}$7.1
8.4 | $x^{3}+x^{17}+a^{48}x^{18}+a^{3}x^{33}+ax^{34}+x^{48}$ |  $N^{\circ}$4 | 9 : $N^{\circ}$2.1
8.5 | $x^{3}+{\rm{tr}}_{1}^{8}(x^{9})$ |  $N^{\circ}$5 | 9 : $N^{\circ}$1.3
8.6 | $x^{3}+a^{-1}{\rm{tr}}_{1}^{8}(a^{3}x^{9})$ |  $N^{\circ}$5 | 9 : $N^{\circ}$1.5
9 | 9.1 | $x^{3}$ | Gold |
9.2 | $x^{5}$ | Gold |
9.3 | $x^{17}$ | Gold |
9.4 | $x^{13}$ | Kasami |
9.5 | $x^{241}$ | Kasami |
9.6 | $x^{19}$ | Welch |
9.7 | $x^{255}$ | Inverse |
9.8 | $x^{3}+{\rm{tr}}_{1}^{9}(x^{9})$ |  $N^{\circ}$5 |
9.9 | $x^{3}+{\rm{tr}}_{3}^{9}(x^{9}+x^{18})$ |  $N^{\circ}$6 |
9.10 | $x^{3}+{\rm{tr}}_{3}^{9}(x^{18}+x^{36})$ |  $N^{\circ}$7 |
10 | 10.1 | $x^{3}$ | Gold |
10.2 | $x^{9}$ | Gold |
10.3 | $x^{57}$ | Kasami |
10.4 | $x^{339}$ | Dobbertin |
10.5 | $x^{6}+x^{33}+a^{31}x^{192}$ |  $N^{\circ}$3 |
10.6 | $x^{72}+x^{33}+a^{31}x^{258}$ |  $N^{\circ}$3 |
10.7 | $x^{3}+{\rm{tr}}_{1}^{10}(x^{9})$ |  $N^{\circ}$5 |
10.8 | $x^{3}+a^{-1}{\rm{tr}}_{1}^{10}(a^{3}x^{9})$ |  $N^{\circ}$5 |
11 | 11.1 | $x^{3}$ | Gold |
11.2 | $x^{5}$ | Gold |
11.3 | $x^{9}$ | Gold |
11.4 | $x^{17}$ | Gold |
11.5 | $x^{33}$ | Gold |
11.6 | $x^{13}$ | Kasami |
11.7 | $x^{57}$ | Kasami |
11.8 | $x^{241}$ | Kasami |
11.9 | $x^{993}$ | Kasami |
11.10 | $x^{35}$ | Welch |
11.11 | $x^{287}$ | Niho |
11.12 | $x^{1023}$ | Inverse |
11.13 | $x^{3}+{\rm{tr}}_{1}^{11}(x^{9})$ |  $N^{\circ}$5 |

Then the nonlinearity of $F$ equals:

$N(F)=2^{n-1}-\frac{1}{2}\max\limits_{a\in\operatorname{\mathbb{F}}_{2^{n}},b\in\operatorname{\mathbb{F}}_{2^{m}}^{*}}|\lambda_{F}(a,b)|.$

The higher is the nonlinearity $N(F)$, the better is the resistance of $F$ to
linear attacks. There is a universal upper bound of nonlinearity for any
vectorial Boolean function.

It means any vectorial Boolean function’s nonlinearity is lower or equal than
this uppper bound. The bound is $2^{n-1}-2^{\frac{n}{2}-1}$ for any vectorial
Boolean function
$F:\operatorname{\mathbb{F}}_{2^{n}}\rightarrow\operatorname{\mathbb{F}}_{2^{m}}$.
Functions which achieve this bound are called bent functions. Since bent
functions have the highest nonlinearity, so they are optimal against linear
attacks. Bent functions only exist when $n$ is even and $m\leq n/2$. When
$n=m$ and $n$ is odd, the upper bound is smaller and changes to $N(F)\leq
2^{n-1}-2^{\frac{n-1}{2}}$. Functions which achieve this bound when n is odd
are Almost Bent(AB) functions. When $n=m$ and $n$ is even, it is conjectured
that the bound is $N(F)\leq 2^{n-1}-2^{\frac{n}{2}}$.

A vectorial Boolean functions
$F:\operatorname{\mathbb{F}}_{2^{n}}\rightarrow\operatorname{\mathbb{F}}_{2^{m}}$
is differential $\delta$-uniform if the equations

$F(x+a)-F(x)=b,\hskip 28.45274pt\forall
a\in\operatorname{\mathbb{F}}_{2^{n}}^{*},\hskip 8.5359pt\forall
b\in\operatorname{\mathbb{F}}_{2^{m}},$

have at most $\delta$ solutions. The lower is the differential uniformity, the
better is the resistance to differential attacks. Differential uniformity
$\delta$ has lower bound if $n\neq m$ as $\delta\geq 2^{(n-m)}$. Functions
achieve this bound are Perfect Nonlinear(PN) functions. A function is PN if
and only if it is bent. Since bent functions have highest nonlinearity, thus
PN (or bent functions) have highest nonlinearity and lowest uniformity. When
$n=m$, the functions with lowest possible differential uniformity are Almost
Perfect Nonlinear (APN) functions which are $2$-uniform. Every AB function is
APN, but the converse is not true. Any vectorial Boolean function
$F:\operatorname{\mathbb{F}}_{2}^{n}\rightarrow\operatorname{\mathbb{F}}_{2}^{m}$
can be represented by its Algebraic Normal Form (ANF) as follow:

$F(x_{1},...,x_{n})=\sum_{u\in\operatorname{\mathbb{F}}_{2}^{n}}a_{u}\prod_{i=1}^{n}x_{i}^{u_{i}},\
\ a_{u}\in\operatorname{\mathbb{F}}_{2}^{m},\ \ u=(u_{1},...,u_{n}).$

The degree of $F$ \- $d^{\circ}(F)$ is the degree of its ANF. $F$ is affine if
$d^{\circ}(F)\leq 1$ and it is quadratic if $d^{\circ}(F)=2$. If $n=m$, $F$
can be represented as univariate polynomial over
$\operatorname{\mathbb{F}}_{2^{n}}$ :

$F(x)=\sum_{i=0}^{2^{n}-1}c_{i}x^{i},\quad c_{i}\in\mathbb{F}_{2^{n}}.$

We denote $tr_{m}^{n}$ as the trace functions from
$\operatorname{\mathbb{F}}_{2^{n}}\rightarrow\operatorname{\mathbb{F}}_{2^{m}}$:

${\rm{tr}}_{m}^{n}(x)=x+x^{2^{m}}+x^{2^{2m}}+\cdots+x^{2^{(n/m-1)m}},$

and we write $tr_{1}^{n}$ when $m=1$.

There are three equivalence relations of vectorial Boolean functions which
keep the uniformity (APN-ness) and nonlinearity (AB-ness) the same. They are
affine-equivalence, Extended Affine (EA)-equivalence and Carlet-Charpin-
Zinoview (CCZ)-equivalence. CCZ-equivalence is more general than EA-
equivalence and EA-equivalence is more general than affine-equivalence.

For example, if two vectorial Boolean functions are affine-equivalent, they
are also EA and CCZ-equivalent, however if two functions are CCZ-equivalent,
they may not be affine or EA-equivalent. In particular, CCZ-equivalence
doesn’t preserve the algebraic degree, but affine and EA-equivalence do. Two
vectorial Boolean functions $F$,$F^{\prime}$:
$\operatorname{\mathbb{F}}_{2^{n}}\rightarrow\operatorname{\mathbb{F}}_{2^{m}}$
are affine-equivalent if $F^{\prime}$ = $A_{1}\circ F\circ A_{2}$. Likewise,
they are EA-equivalent if $A_{1}\circ F\circ A_{2}$ \+ $A$, which $A_{1}$ is
affine permuation on $\operatorname{\mathbb{F}}_{2^{m}}$, $A_{2}$ is affine
permutation on $\operatorname{\mathbb{F}}_{2^{n}}$, $A$ is affine functions
from $\operatorname{\mathbb{F}}_{2^{n}}$ to
$\operatorname{\mathbb{F}}_{2^{m}}$.

$F$ and $F^{\prime}$ are called CCZ-equivalent if there exists affine
permutation $L$ on $\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{m}$, which makes
$\ {\cal L}(G_{F})=G_{F^{\prime}}\ $, where
$G_{F}=\\{(x,F(x)):x\in\mathbb{F}_{2}^{n}\\}\subset\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{m}$,
$G_{F}^{\prime}=\\{(x,F^{\prime}(x)):x\in\mathbb{F}_{2}^{n}\\}\subset\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{m}$.

As we mentioned, EA-equivalences are special cases of CCZ-equivalences. There
are some cases when they coincide:
1) Boolean functions [1];
2) Bent functions [2];
3) Two quadratic APN functions [3];
4) If a quadratic APN function is CCZ-equivalent to a power function then they
are EA-equivalent [4];
5) For $n$ $\geq$ $3$, two power APN functions are CCZ-equivalent if and only
if they are EA-equivalent or one of them is EA-equivalent to the inverse of
the other one [4].

In contrast, for functions from
$\operatorname{\mathbb{F}}_{2^{n}}\rightarrow\operatorname{\mathbb{F}}_{2^{m}}$,
$m\geq 2$, CCZ-equivalence is different from EA-equivalence [5],[6].

##  III Known Families of APN functions

Until now, there are $17$ known infinite families of APN functions. Among them
are $6$ families of power functions.

###  III-A Families of Power APN

Talbe I lists all the power APN functions on
$\operatorname{\mathbb{F}}_{2^{n}}$. Welch, Niho, Gold with n odd and Kasami
with n odd are AB functions. Their Walsh spectra are $\\{0,\pm
2^{(n+1)/2}\\}$. In contrast, Inverse, Dobbertin, Gold with n even and Kasami
with n even are not AB. When n is even, Gold and Kasami functions have the
Walsh spectra $\\{0,\pm 2^{n/2},\pm 2^{(n+2)/2}\\}$. For $n\leq 5$, all APN
functions are CCZ-equivalent to power functions.

###  III-B Families of APN Polynomials

Table II lists all the known families of APN polynomials. They are all
quadratic. When n is odd, all these polynomials are AB functions.

##  IV Simplification of known APN families

As we can see from Talbe I and Talbe II, there are many APN functions in each
APN family. In particular, there are many coefficients and many parameters in
the families of APN polynomials. For example, when $n=10$, only family NO.$3$
in Table II already has $45012$ APN functions. So it is very difficult to
check the equivalence of a given APN function to both monomial and polynomial
families.

Not only polynomial APN are complex to compare with, APN power functions are
the same. In [21], they alleged that they have found a new APN family, but it
was proved their result is affine equivalent to Gold family. These motivate us
to simplify the families and make a list that for given $n$, all functions are
CCZ-inequivalent. Taking family NO.$3$ for $n=10$ for example to explain what
we do. Firstly, we found all the value range for each parameter, then we found
$45012$ APN functions. Secondly, we compare all $45012$ APN functions with
each other, then we found two CCZ-inequivalent classes. Next, from each class,
we choose one representative APN function with simplest coefficients. Fianlly,
we check CCZ-equivalence between these two representatives with other families
for $n=10$. In the end, both two representatives are CCZ-inequivalent with
other families. Thus, we put them into our table.

Table III contains all APN functions from $n=6$ to $n=11$ and they are CCZ-
inequivalent between each other for given $n$. In the future, people can
compare with this table for $n=6$ to $n=11$ instead of comparing with each
function in every known APN family again. We also compare the result with the
known APN functions from [22].

In addition, we observe that when n is odd and not divisible by 3, there is
only one APN polynomial (up to CCZ-equivalence) provided by the known families
of APN polynomials $x^{3}+{\rm{tr}}_{1}^{n}(x^{9})$.

##  V Conclusion and future work

In this extended abstract, we check CCZ-equivalence for functions within known
families of APN functions and compare them with each other. We present a list
of CCZ-inequivalent APN functions for $n$ from $6$ to $11$ provided by the
known APN families. This work can facilitate to find new APN families for
constructing more secure cryptosystems or for enriching knowledge in
mathematics or other fields. In the future, we plan to extend the list for
bigger $n$ and try to find some rules behind the results.

## References

  * [1] L.Budaghyan, C.Carlet, "CCZ-equivalence of single and multi output Boolean functions", _Post-proceedings of the 9-th International Conference on Finite Fields and Their Applications Fq’09, Contemporary Math._ , AMS, vol. 518, 2010, pp. 43-54.
  * [2] L. Budaghyan, C. Carlet, "CCZ-equivalence of bent vectorial functions and related constructions",_Designs, Codes and Cryptography_ , vol 59(1), 2011, pp. 69-87.
  * [3] S. Yoshiara, "Equivalences of quadratic APN functions", _Journal of Algebraic Combinatorics_ , vol.35(3), 2012, pp. 461-475.
  * [4] S. Yoshiara, "Equivalences of power APN functions with power or quadratic APN functions", _Journal of Algebraic Combinatorics_ , vol.35(3), 2016, pp. 561-585.
  * [5] L. Budaghyan, C. Carlet, "CCZ-equivalence of single and multi-output Boolean functions", _Post-proceedings of the 9th International Conference on Finite Fields and Their Applications Fq’09, Contemporary Mathematics_ , vol. 518, 2010, pp. 43-54.
  * [6] L. Budaghyan, T. Helleseth, "Planar functions and commutative semifields", _Tatra. Mt. Math. Publ._ vol.45,2010, pp. 15-45.
  * [7] R. Gold, "Maximal recursive sequences with 3-valued recursive crosscorrelation functions", _IEEE Trans. Inform. Theory_ , vol.14, 1986, pp. 154-156.
  * [8] K. Nyberg, "Differentially uniform mappings for cryptography", _Advances in Cryptography, EUROCRYPT’93_ , LNCS, vol.765, 1994, pp. 55-64.
  * [9] H. Janwa, R. Wilson, "Hyperplane sections of Fermat varieties in $P^{3}$ in char. 2 and some applications to cyclic codes", _Proceedings of AAECC-10_ , LNCS, vol. 673, 1993, pp. 180-194. Berlin: Springer-Verlag.
  * [10] T. Kasami, "The weight enumerators for several classes of subcodes of the second order binary Reed-Muller codes", _Inform. and Control_ , vol.18, 1971, pp. 369-394.
  * [11] H. Dobbertin, "Almost perfect nonlinear power functions over $GF(2^{n})$ the Welch case", _IEEE Trans. Inform. Theory_ , vol.45, 1999, pp. 1271-1275.
  * [12] H. Dobbertin, "Almost perfect nonlinear power functions over $GF(2^{n})$: the Niho case", _Inform. and Comput._ , vol.151, 1999, pp. 57-72.
  * [13] T. Beth, C. Ding, "On almost perfect nonlinear permutations", _Advances in Cryptology-EUROCRYPT’93_ , LNCS, vol.765, 1993, pp. 65-76, New York: Springer-Verlag.
  * [14] H. Dobbertin, "Almost perfect nonlinear power functions over $GF(2^{n})$: a new case for $n$ divisible by 5", _Proceedings of Finite Fields and Applications Fq5_ , 2000, pp. 113-121.
  * [15] L. Budaghyan, C. Carlet, G. Leander, "Two classes of quadratic APN binomials inequivalent to power functions", _IEEE Trans. Inform. Theory_ , vol.54(9), 2008, pp. 4218-4229.
  * [16] L. Budaghyan, C. Carlet, "Classes of quadratic APN trinomials and hexanomials and related structures", _IEEE Trans. Inform. Theory_ , vol.54(5), 2008, pp. 2354-2357.
  * [17] L. Budaghyan, C. Carlet, G. Leander, "Constructing new APN functions from known ones", _Finite Fields and Their Applications_ , vol 15(2), 2009, pp. 150-159.
  * [18] L. Budaghyan, C. Carlet, G. Leander, "On a construction of quadratic APN functions", _IEEE Information Theory Workshop_ , 2009, pp. 374-378.
  * [19] C. Bracken, E. Byrne, N.Markin, G. McGuire, "A few more quadratic APN functions", _Cryptography and Communications_ , vol.3(1), 2011, pp. 43-53.
  * [20] C. Bracken, E. Byrne, N.Markin, G. McGuire, "New families of quadratic almost perfect nonlinear trinomials and multinomials", _Finite Fields and Their Applications_ , vol.14(3), 2008, pp. 703-714.
  * [21] F. Göloğlu, "Almost perfect nonlinear trinomials and hexanomials", _Finite Fields and Their Applications_ , vol.33, 2015, pp. 258-282.
  * [22] Y. Edel, A. Pott, "A new almost perfect nonlinear function which is not quadratic", _Advances in Mathematics of Communications_ , vol.3(1), 2009, pp. 59-81.


# The lowest two-sided cell of weighted Coxeter groups of rank 3

Jianwei Gao  Jianwei Gao
Beijing International Center for Mathematical Research
Peking University
No.5 Yiheyuan Road
Beijing, 100871
People’s Republic of China<EMAIL_ADDRESS>
###### Abstract.

In this paper, we give precise description for the lowest lowest two-sided
cell $c_{0}$ and the left cells in it for a weighted Coxeter group of rank 3.
Then we show conjectures $P1-P15$ and $\widetilde{P}$ hold for $c_{0}$ and do
some calculation for the based ring of $c_{0}$.

###### Key words and phrases:

Weighted Coxeter group, Hecke algebra, Two-sided cell, Left cell, Based ring

##  0\. Introduction

Let $(W,S,L)$ be a weighted Coxeter group. In [L3, 13.4], G.Lusztig
conjectured that the maximal weight value of the longest elements of the
finite parabolic subgroups of $W$ is a bound for $(W,S,L)$. This property is
referred as boundness of a weighted Coxeter group([L3, 13.2]). When the rank
of $W$ is 1 or 2, this conjecture is clear. In [Gao, 2.1], I proved this
conjecture when $rank(W)=3$. As a consequence, $W$ has a lowest two-sided cell
$c_{0}$, see [Gao, 7.1]. In this paper, we give precise description for
$c_{0}$ and the left cells in it. Then we can show conjectures $P1-P15$ and
$\widetilde{P}$ hold for $c_{0}$. At last, we do some calculation for the
based ring of $c_{0}$.

##  1\. Preliminaries

1.1. In this paper, for any Coxeter group $(W,S)$, we assume the generating
set $S$ is finite. We call $|S|$ the rank of $(W,S)$ and denote it by
$rank(W)$. We use $l$ for the length function and $\leq$ for the Bruhat order
of $W$. The neutral element of $W$ will be denoted by $e$. For $x\in W$, we
set

$\mathcal{L}(x)=\\{s\in S|sx<x\\},\ \mathcal{R}(x)=\\{s\in S|xs<x\\}.$

For $s,t\in W$, let $m_{st}\in\mathbb{Z}_{\geq 1}\bigcup\\{\infty\\}$ be the
order of $st$ in $W$.

For any $I\subseteq S$, let $W_{I}=\langle I\rangle$. Then $(W_{I},I)$ is also
a Coxeter group, called a parabolic subgroup of $(W,S)$. Denote the longest
element of $W_{I}$ by $w_{I}$ if $|W_{I}|<\infty$. For $s,t\in S$, $s\neq t$,
we use $W_{st}$ instead of $W_{\\{s,t\\}}$ and $w_{st}$ instead of
$w_{\\{s,t\\}}$.

For $w_{1},w_{2},\cdots,w_{n}\in W$, we often use the notation $w_{1}\cdot
w_{2}\cdot\ \cdots\ \cdot w_{n}$ instead of $w_{1}w_{2}\cdots w_{n}$ if
$l(w_{1}w_{2}\cdots w_{n})=l(w_{1})+l(w_{2})+\cdots+l(w_{n})$.

1.2. Let $(W,S)$ be a Coxeter group. A map $L:W\longrightarrow\mathbb{Z}$ is
called a weight function if $L(ww^{\prime})=L(w)+L(w^{\prime})$ for any
$w,w^{\prime}\in W$ with $l(ww^{\prime})=l(w)+l(w^{\prime})$. Then we call
$(W,S,L)$ a weighted Coxeter group. In this paper, the weight function $L$ for
any weighted Coxeter group $(W,S,L)$ is assumed to be positive, that is,
$L(s)>0$ for any $s\in S$.

1.3. Let $(W,S,L)$ be a weighted Coxeter group and $\mathbb{Z}[v,v^{-1}]$ be
the ring of Laurent polynomials in an indeterminate $v$ with integer
coefficients. For
$f=\sum\limits_{n\in\mathbb{Z}}a_{n}v^{n}\in\mathbb{Z}[v,v^{-1}]\setminus\\{0\\}$,
we define $deg\ f=\max\limits_{n\in\mathbb{Z}\atop a_{n}\neq 0}n$.
Complementally, we define $deg\ 0=-\infty$.

For $w\in W$, set $v_{w}=v^{L(w)}\in\mathbb{Z}[v,v^{-1}]$. The Hecke algebra
$\mathcal{H}$ of $(W,S,L)$ is the unital associative
$\mathbb{Z}[v,v^{-1}]-$algebra defined by the generators $T_{s}(s\in S)$ and
the relations

$(T_{s}-v_{s})(T_{s}+v_{s}^{-1})=0,\ \forall s\in S.$
$\underbrace{T_{s}T_{t}T_{s}\cdots}_{m_{st}\ factors}\ =\
\underbrace{T_{t}T_{s}T_{t}\cdots}_{m_{st}\ factors},\ \forall s,t\in S,\
m_{st}<\infty.$

Obviously, $T_{e}$ is the multiplicative unit of $\mathcal{H}$. For any $w\in
W$, we define $T_{w}=T_{s_{1}}T_{s_{2}}\cdots T_{s_{n}}\in\mathcal{H}$, where
$w=s_{1}s_{2}\cdots s_{n}$ is a reduced expression of $w$ in $W$. Then $T_{w}$
is independent of the choice of reduced expression and $\\{T_{w}|w\in W\\}$ is
a $\mathbb{Z}[v,v^{-1}]-$basis of $\mathcal{H}$, called the standard basis. We
define $f_{x,y,z}\in\mathbb{Z}[v,v^{-1}]$ for any $x,y,z\in W$ by the identity

$T_{x}T_{y}=\sum\limits_{z\in W}f_{x,y,z}T_{z}.$

The following involutive automorphism of rings is useful, called the bar
involution:

$\bar{}:\mathcal{H}\longrightarrow\mathcal{H}\ \ \ \ \ $ $v^{n}\longrightarrow
v^{-n}.$ $T_{s}\longrightarrow T_{s}^{-1}.$

We have $\overline{T_{w}}=T_{w^{-1}}^{-1}$ for any $w\in W$. We set

$\mathcal{H}_{\leq 0}=\bigoplus\limits_{w\in W}\mathbb{Z}[v^{-1}]T_{w},\
\mathcal{H}_{<0}=\bigoplus\limits_{w\in W}v^{-1}\mathbb{Z}[v^{-1}]T_{w}.$

We can get the following facts by easy computation.

Lemma 1.4. (1) For any $x,y,\in W$, we have

$f_{x,y,e}=\delta_{x,y^{-1}}.$

(2) For any $x,y,z\in W$, we have

$deg\ f_{x,y,z}\leq min\\{L(x),L(y),L(z)\\}.$

(3) For any $x,y,z\in W$, we have

$f_{x,y,z^{-1}}=f_{y,z,x^{-1}}=f_{z,x,y^{-1}}.$

(4) For any finite parabolic subgroup $W_{I}$ of $W$, $x\in W_{I}$, we have

$deg\ f_{w_{I},w_{I},x}=L(x).$

Define the degree map

$deg:\ \mathcal{H}\longrightarrow\mathbb{Z}\cup\\{-\infty\\}\ \ \ \ \ \ \ \ \
$ $\ \ \ \ \sum_{w\in W}f_{w}T_{w}\longrightarrow Max\\{deg\ f_{w}|w\in W\\}.$

And we set $N=\max\limits_{I\subseteq S\atop|W_{I}|<\infty}L(w_{I})$.
G.Lusztig gave the following conjecture in [L3, 13.4].

Conjecture 1.5. Let $(W,S,L)$ be a weighted Coxeter group, $S$ is finite and
$L$ is positive, then $N$ is a bound for $(W,S,L)$. Namely, $deg\
(T_{x}T_{y})\leq N$ for all $x,y\in W$.

Remark 1.6. When $W$ is a finite Coxeter group, this conjecture can be proved
using Lemma 1.4(2). In [L1, 7.2], G.Lusztig proved this conjecture when $W$ is
an affine Weyl group. In [SY, 3.2], J.Shi and G.Yang proved this conjecture
when $W$ has complete Coxeter graph. In [Gao, 2.1], I proved this conjecture
when the rank of $W$ is 3.

1.7. For any $w\in W$, there exists a unique element
$C_{w}\in\mathcal{H}_{\leq 0}$ such that $\overline{C_{w}}=C_{w}$ and
$C_{w}-T_{w}\in\mathcal{H}_{<0}$. The elements $\\{C_{w}|w\in W\\}$ form a
$\mathbb{Z}[v,v^{-1}]-$basis of $\mathcal{H}$, called the Kazhdan-Lusztig
basis. We define $h_{x,y,z},p_{x,y}\in\mathbb{Z}[v,v^{-1}]$ for any $x,y,z\in
W$ such that

$C_{x}C_{y}=\sum\limits_{z\in W}h_{x,y,z}C_{z}.$ $C_{y}=\sum\limits_{x\in
W}p_{x,y}T_{x}.$

These polynomials $p_{x,y}$ are called Kazhdan-Lusztig polynomials. For $w\in
W$, $I=\mathcal{R}(w)$, $J=\mathcal{L}(w)$, we have the factorization
$w=x\cdot w_{I}=w_{J}\cdot y$ for some $x,y\in W$. Then we set

$E_{x}=\sum_{x^{\prime}\leq x\atop
l(x^{\prime}w_{I})=l(x^{\prime})+l(w_{I})}p_{x^{\prime}w_{I},w}T_{x^{\prime}}.$
$F_{y}=\sum_{y^{\prime}\leq y\atop
l(w_{J}y^{\prime})=l(w_{J})+l(y^{\prime})}p_{w_{J}y^{\prime},w}T_{y^{\prime}}.$

1.8. Using Kazhdan-Lusztig basis, we can define the preorders
$\underset{L}{\leq}$, $\underset{R}{\leq}$, $\underset{LR}{\leq}$ on $W$.
These preorders give rise to equivalence relations $\underset{L}{\sim}$,
$\underset{R}{\sim}$, $\underset{LR}{\sim}$ on $W$ respectively. The
equicalence classes are called left cells, right cells and two-sided cells of
$W$. Then we have partial orders $\underset{L}{\leq}$, $\underset{R}{\leq}$,
$\underset{LR}{\leq}$ on the sets of left cells, right cells and two-sided
cells of $W$ respectively. For $x,y\in W$, we have $x\underset{L}{\leq}y$ if
and only if $x^{-1}\underset{R}{\leq}y^{-1}$.

Now we assume Conjecture 1.5 holds and $W$ has a lowest two-sided cell
$c_{0}$. It is easy to see that $deg\ h_{x,y,z}\leq N$ for any $x,y,z\in W$,
so we can define the a-function

$a:W\longrightarrow\mathbb{N}\ \ \ \ \ \ \ \ \ \ \ $ $\ \ \ \ \ \ \ \ \ \ \
w\longrightarrow\max\limits_{x,y\in W}deg\ h_{x,y,w}.$

For any $x,y,z\in W$, we define $\beta_{x,y,z},\gamma_{x,y,z}\in\mathbb{Z}$
such that

$f_{x,y,z^{-1}}=\beta_{x,y,z}v^{N}+\mbox{lower degree terms}.$
$h_{x,y,z^{-1}}=\gamma_{x,y,z}v^{a(z)}+\mbox{lower degree terms}.$

Lemma 1.9. Let $x,y,z\in W$.
(1) We have $\beta_{x,y,z}=\beta_{y,z,x}=\beta_{z,x,y}$.
(2) We have $\gamma_{x,y,z}=\gamma_{y^{-1},x^{-1},z^{-1}}$.
(3) If $\beta_{x,y,z}\neq 0$, then $x\underset{L}{\sim}y^{-1}$,
$y\underset{L}{\sim}z^{-1}$, $z\underset{L}{\sim}x^{-1}$, $a(x)=a(y)=a(z)=N$,
and $\beta_{x,y,z}=\gamma_{x,y,z}=\gamma_{y,z,x}=\gamma_{z,x,y}$.
(4) If $\gamma_{x,y,z}\neq 0$ and $a(z)=N$, then
$\beta_{x,y,z}=\gamma_{x,y,z}\neq 0$.

1.10. In [L3, 14.2,14.3], G.Lusztig gave some conjectures about the Hecke
algebra, which are called $P1-P15$ and $\widetilde{P}$. When these conjectures
hold for $c_{0}$, we can study the based ring $J_{0}$ of $c_{0}$, which is an
associative ring with $\mathbb{Z}-$basis $\\{t_{w}|w\in c_{0}\\}$ and
multiplication

$t_{x}t_{y}=\sum_{z\in c_{0}}\gamma_{x,y,z^{-1}}t_{z}$

for any $x,y\in c_{0}$. In section 4 of this paper, we will do some
calculation for $J_{0}$ to study its structure when the rank of $W$ is 3.

##  2\. The boundness of $(W,S,L)$

From now on, we assume $(W,S,L)$ is a weighted Coxeter group of rank 3 and $L$
is positive. We set $N=\max\limits_{I\subseteq S\atop|W_{I}|<\infty}L(w_{I})$.
In [Gao, 2.1], I proved Conjecture 1.5 in this case.

Theorem 2.1. We have $deg\ (T_{x}T_{y})\leq N$ for all $x,y\in W$.

Remark 2.2. In the proof of [Gao, 2.1], I set $S=\\{r,s,t\\}$, $m_{rt}=2$,
$m_{sr}\geq m_{st}$, $W$ is infinite and $W$ is not an affine Weyl group,
otherwise this conjecture has been proved. When $m_{sr}=\infty$ and
$m_{st}=2$, or $m_{sr}=m_{st}=\infty$, the conjecture is easy to check, so I
only need to consider the following three cases in [Gao].
Case 1: $m_{sr}=\infty>m_{st}\geq 3$.
$r$$s$$t$$\infty$$m_{st}$

Case 2: $\infty>m_{sr}\geq m_{st}\geq 4$, $m_{sr}\geq 5$.
$r$$s$$t$$m_{sr}$$m_{st}$

Case 3: $\infty>m_{sr}\geq 7$, $m_{st}=3$.
$r$$s$$t$$m_{sr}$$3$

Now we set

$M=\\{w_{J}|J\subseteq S,\ |W_{J}|<\infty,\ L(w_{J})=N\\}.$ $\Lambda=\\{x\cdot
u\cdot y|x,y\in W,\ u\in M\\}.$

For any $w_{J}\in M$, we set

$B_{J}=\\{x\in W|\mathcal{R}(x)\subseteq S\setminus J\\}.$ $U_{J}=\\{y\in
W|\mathcal{L}(y)\subseteq S\setminus J\ \mbox{and}\ sw_{J}y\notin\Lambda\
\mbox{for all}\ s\in J\\}.$

Then Theorem 2.1 has the following corollaries.

Corollary 2.3. (1) If $x,y\in W$ satisfy $deg\ (T_{x}T_{y})=N$, then both
$x\in\Lambda$ and $y\in\Lambda$.
(2) For any $w_{J}\in M$, $q\leq w_{J}$, $x,y\in W$,
$\mathcal{R}(x),\mathcal{L}(y)\subseteq S\setminus J$, we have $deg\
(T_{xq}T_{y})\leq N-L(q)$. In particular, $T_{xw_{J}}T_{y}=T_{xw_{J}y}$.
(3) For any $w_{J}\in M$, the left cell of $W$ containing $w_{J}$ is
$\\{x\cdot w_{J}|x\in W\\}=\\{y\in W|\mathcal{R}(y)=J\\}$, the right cell of
$W$ containing $w_{J}$ is $\\{w_{J}\cdot x|x\in W\\}=\\{y\in
W|\mathcal{L}(y)=J\\}$.

Proof. See [Gao, Section 6]. $\square$

Corollary 2.4. Let $w_{J}\in M$, $x\in B_{J}$, $q<w_{J}$.
(1) If $y\in B_{J}^{-1}$, $l(q)\geq 2$, then $deg\ (T_{xq}T_{y})<N-L(q)$ for
the three cases listed in Remark 2.2.
(2) If $y\in U_{J}$, then $deg\ (T_{xq}T_{y})<N-L(q)$ for any weighted Coxeter
group of rank 3.

Proof. (1) By the proofs in [Gao, 3.3, 4.7, 5.9], we have the following
tables.
Case 1
$w_{J}$ $q$ $deg\ (T_{xq}T_{y})$ $w_{st}$ $q<w_{st}$, $l(q)\geq 2$ 0

Case 2
$w_{J}$ $q$ $deg\ (T_{xq}T_{y})$ $w_{sr}$ $sr$ $\leq Max\\{L(st),L(sr)\\}$
$w_{sr}$ $rs$ $\leq Max\\{L(st),L(sr)\\}$ $w_{sr}$ $rsr$ $\leq L(s)$ $w_{sr}$
$srs$ $\leq Max\\{L(t),L(r)\\}$ $w_{sr}$ $q<w_{sr}$, $l(q)\geq 4$ 0 $w_{st}$
$st$ $\leq L(sr)$ $w_{st}$ $ts$ $\leq L(sr)$ $w_{st}$ $tst$ 0 $w_{st}$ $sts$
$\leq L(r)$ $w_{st}$ $q<w_{st}$, $l(q)\geq 4$ 0

Case 3
$w_{J}$ $q$ $deg\ (T_{xq}T_{y})$ $w_{sr}$ $sr$ $\leq L(srsr)$ $w_{sr}$ $rs$
$\leq L(srsr)$ $w_{sr}$ $srs$ $\leq L(srs)$ $w_{sr}$ $rsr$ $\leq L(srs)$
$w_{sr}$ $srsr$ $\leq L(sr)$ $w_{sr}$ $rsrs$ $\leq L(sr)$ $w_{sr}$ $rsrsr$
$\leq L(s)$ $w_{sr}$ $srsrs$ $0$ $w_{sr}$ $q<w_{sr}$, $l(q)\geq 6$ 0

We have $deg\ (T_{xq}T_{y})<N-L(q)$ in all these three cases.
(2) It is obvious when $W$ is a finite Coxeter group. We can get this
inequality by [Xie1, 3.1] when $W$ is an affine Weyl group and by [Xie2, 3.5]
when $W$ has complete Coxeter graph. Now we only consider other case.

If $l(q)=0$, by Corollary 2.3(1), we get $deg\ (T_{x}T_{y})<N$ since
$y\notin\Lambda$. If $l(q)=1$, by Corollary 2.3(1), we get $deg\
(T_{xq}T_{qy})<N$ since $qy\notin\Lambda$, so $deg\ (T_{xq}T_{y})<N-L(q)$. If
$l(q)\geq 2$, then we must in the three cases listed in Remark 2.2, we get
$deg\ (T_{xq}T_{y})<N-L(q)$ by (1). $\square$

##  3\. The lowest two-side cell $c_{0}$

Now we fix an element $w_{J}\in M$ and let $c_{0}$ be the two-sided cell of
$W$ containing $w_{J}$. In [Gao, 7.1], I proved the following consequence.

Proposition 3.1. (1) The two-sided cell $c_{0}$ is the lowest two-sided cell
of $W$.
(2) We have $\Lambda=\\{w\in W|a(w)=N\\}\subseteq c_{0}$.

By Corollary 2.3 and Corollary 2.4, we can prove the following proposition
using the same method used in [Xie2, 3.6,3.7].

Proposition 3.2. (1) For $w_{J}\in M$, $x\in B_{J}$, $y\in U_{J}$, we have
$C_{xw_{J}y}=E_{x}C_{w_{J}}F_{y}$.
(2) For $w_{J}\in M$, $y\in U_{J}$, $x\in U_{J}^{-1}$, the set
$\Gamma_{J,y}=B_{J}w_{J}y$ is a left cell of $W$ and
$\Phi_{x,J}=xw_{J}B_{J}^{-1}$ is a right cell of $W$.

Now we can give precise description for $c_{0}$ and the left cells in it.

Theorem 3.3. (1) We have $c_{0}=\Lambda=\\{w\in W|a(w)=N\\}$.
(2) The lowest two-sided cell $c_{0}$ can be decomposed into left cells as

$c_{0}=\coprod_{w_{J}\in M,y\in U_{J}}\ \Gamma_{J,y}\ .$

Proof. (1) It is clear that $\Lambda=\bigcup\limits_{w_{J}\in
M}B_{J}w_{J}U_{J}=\bigcup\limits_{w_{J}\in
M}U_{J}^{-1}w_{J}B_{J}^{-1}\subseteq c_{0}$.

We claim that for any $x\in W$, $y\in\Lambda$, if $x\underset{L}{\leftarrow}y$
or $x\underset{R}{\leftarrow}y$, then $x\in\Lambda$. We only prove the
$x\underset{L}{\leftarrow}y$ case. First, we assume $y=z_{1}w_{J}z_{2}$ for
some $w_{J}\in M$, $z_{1}\in B_{J}$, $z_{2}\in U_{J}$, $h_{s,y,x}\neq 0$ for
some $s\in S$. By Proposition 3.2(1), we have

$\displaystyle\ C_{s}C_{z_{1}w_{J}z_{2}}$ $\displaystyle=$ $\displaystyle\
C_{s}C_{z_{2}w_{J}}F_{z_{2}}$ $\displaystyle=$ $\displaystyle\ \sum_{z_{3}\in
B_{J}}h_{s,z_{1}w_{J},z_{3}w_{J}}C_{z_{3}w_{J}}F_{z_{2}}$ $\displaystyle=$
$\displaystyle\ \sum_{z_{3}\in
B_{J}}h_{s,z_{1}w_{J},z_{3}w_{J}}C_{z_{3}w_{J}z_{2}}.$

We get $x=z_{3}w_{J}z_{2}\subseteq\Lambda$ for some $z_{3}\in B_{J}$ and
$z_{2}\in U_{J}$, the claim is proved.

For $w\in c_{0}$, we have $w\underset{LR}{\leq}w_{J}$ and $w_{J}\in\Lambda$,
so $w\in\Lambda$ by the claim. On the other hand, we have $\Lambda=\\{w\in
W|a(w)=N\\}\subseteq c_{0}$ by Proposition 3.1(2). This conclusion follows.
(2) It is clear that $c_{0}=\bigcup\limits_{w_{J}\in M,y\in U_{J}}\
\Gamma_{J,y}\ .$ If $w_{J},w_{J^{\prime}}\in M$, $y\in U_{J}$, $y^{\prime}\in
U_{J^{\prime}}$ such that $\Gamma_{J,y}=\Gamma_{J^{\prime},y^{\prime}}$, then
there exists $x\in B_{J}$ such that $xw_{J}y=w_{J^{\prime}}y^{\prime}$. If
$x\neq e$, we take $s\in\mathcal{L}(x)$, then
$s\in\mathcal{L}(xw_{J}y)=\mathcal{L}(w_{J^{\prime}}y^{\prime})=J^{\prime}$
and $sw_{J^{\prime}}y^{\prime}=sxw_{J}y\in\Lambda$, contradict to
$y^{\prime}\in U_{J^{\prime}}$. So we have $x=e$. Thus,
$J=\mathcal{L}(w_{J}y)=\mathcal{L}(w_{J^{\prime}}y^{\prime})=J^{\prime}$,
$y=y^{\prime}$. Therefore, it is a disjoint union. $\square$

Proposition 3.4. We have the following table for weighted Coxeter groups of
rank 3.

$W$ the number of left cells in $c_{0}$ finite Coxeter group 1 affine Weyl
group $|W_{0}|$ $m_{sr}=\infty$, $m_{st}=m_{rt}=2$ 2 $m_{sr}=m_{st}=\infty$,
$\infty>m_{rt}\geq 2$ $\infty$ or $2m_{rt}$ $m_{sr}=m_{st}=m_{rt}=\infty$
$\infty$ or 3 or 4 other cases $\infty$

When $W$ is an affine Weyl group, $W_{0}$ denotes the finite Weyl group
corresponding to $W$. When the number of left cells in $c_{0}$ has various
possibilities, it depends on the weight function $L$.

Proof. It is clear when $W$ is a finite Coxeter group. See [Xie1, 3.7] when
$W$ is an affine Weyl group. Then we assume $\infty\geq m_{sr}\geq m_{st}\geq
m_{rt}\geq 2$ and consider the following 11 cases.
(1) $m_{sr}=m_{st}=m_{rt}=\infty$. We have $N=Max\\{L(r),L(s),L(t)\\}$. We may
assume $L(r)\geq L(s)\geq L(t)$. If $L(r)=L(s)=L(t)$, then
$\Gamma_{\\{r\\},e}$,$\Gamma_{\\{s\\},e}$ and $\Gamma_{\\{t\\},e}$ are all the
3 left cells in $c_{0}$. If $L(r)=L(s)>L(t)$, then
$\Gamma_{\\{r\\},e}$,$\Gamma_{\\{s\\},e}$,$\Gamma_{\\{r\\},t}$ and
$\Gamma_{\\{s\\},t}$ are all the 4 left cells in $c_{0}$. If $L(r)>L(s)\geq
L(t)$, then for different $k\in\mathbb{N}$, $\Gamma_{\\{r\\},(st)^{k}}$ are
different left cells in $c_{0}$.
(2) $m_{sr}=m_{st}=\infty$, $\infty>m_{rt}\geq 2$. We have
$N=Max\\{L(w_{rt}),L(s)\\}$. If $L(w_{rt})>L(s)$, then for different
$k\in\mathbb{N}$, $\Gamma_{\\{r,t\\},(sr)^{k}}$ are different left cells in
$c_{0}$. If $L(w_{rt})=L(s)$, then $\Gamma_{\\{r,t\\},e}$ and
$\Gamma_{\\{s\\},w},w\in W_{rt}\setminus\\{w_{rt}\\}$ are all the $2m_{rt}$
left cells in $c_{0}$. If $L(s)>L(w_{rt})$, then $\Gamma_{\\{s\\},w},w\in
W_{rt}$ are all the $2m_{rt}$ left cells in $c_{0}$.
(3) $m_{sr}=\infty$, $m_{st}=m_{rt}=2$. Now we have $N=Max\\{L(st),L(rt)\\}$.
If $L(s)>L(r)$, then $\Gamma_{\\{s,t\\},e}$ and $\Gamma_{\\{s,t\\},r}$ are all
the 2 left cells in $c_{0}$. If $L(s)=L(r)$, then $\Gamma_{\\{s,t\\},e}$ and
$\Gamma_{\\{r,t\\},e}$ are all the 2 left cells in $c_{0}$. If $L(r)>L(s)$,
then $\Gamma_{\\{r,t\\},e}$ and $\Gamma_{\\{r,t\\},s}$ are all the 2 left
cells in $c_{0}$.
(4) $m_{sr}=\infty$, $\infty>m_{st}\geq 3$, $m_{rt}=2$. We have
$N=Max\\{L(w_{st}),L(rt)\\}$. If $L(w_{st})>L(rt)$, then for different
$k\in\mathbb{N}$, $\Gamma_{\\{s,t\\},(rs)^{k}}$ are different left cells in
$c_{0}$. If $L(rt)\geq L(w_{st})$, then for different $k\in\mathbb{N}$,
$\Gamma_{\\{r,t\\},(sr)^{k}}$ are different left cells in $c_{0}$.
(5) $m_{sr}=\infty$, $\infty>m_{st},m_{rt}\geq 3$. We have
$N=Max\\{L(w_{st}),L(w_{rt})\\}$. We may assume $N=L(w_{st})$, then for
different $k\in\mathbb{N}$, $\Gamma_{\\{s,t\\},(rst)^{k}}$ are different left
cells in $c_{0}$.
(6) $\infty>m_{sr}\geq m_{st}\geq 4$, $m_{sr}\geq 5$, $m_{rt}=2$. We have
$N=Max\\{L(w_{sr}),L(w_{st})\\}>L(rt)$. If $L(w_{sr})\geq L(w_{st})$, then for
different $k\in\mathbb{N}$, $\Gamma_{\\{s,r\\},(tsrs)^{k}}$ are different left
cells in $c_{0}$. If $L(w_{st})>L(w_{sr})$, then for different
$k\in\mathbb{N}$, $\Gamma_{\\{s,t\\},(rst)^{k}}$ are different left cells in
$c_{0}$.
(7) $\infty>m_{sr}\geq 7$, $m_{st}=3$, $m_{rt}=2$. We have
$N=L(w_{sr})>Max\\{L(w_{st}),L(rt)\\}$. For different $k\in\mathbb{N}$,
$\Gamma_{\\{s,r\\},(tsrsrs)^{k}}$ are different left cells in $c_{0}$.
(8) $\infty>m_{sr}\geq m_{st}\geq m_{rt}\geq 4$. If $L(w_{sr})=N$, then for
different $k\in\mathbb{N}$, $\Gamma_{\\{s,r\\},(tsr)^{k}}$ are different left
cells in $c_{0}$. $L(w_{st})=N$ and $L(w_{rt})=N$ are similar.
(9) $\infty>m_{sr}\geq m_{st}\geq 4$, $m_{rt}=3$, $L(w_{rt})=N$. For different
$k\in\mathbb{N}$, $\Gamma_{\\{r,t\\},(srt)^{k}}$ are different left cells in
$c_{0}$.
(10) $\infty>m_{sr}\geq m_{st}\geq 4$, $m_{rt}=3$, $L(w_{sr})=N$. For
different $k\in\mathbb{N}$, $\Gamma_{\\{s,r\\},(tsr)^{k}}$ are different left
cells in $c_{0}$.
(11) $\infty>m_{sr}\geq 4$, $m_{st}=m_{rt}=3$. Now we have
$N=L(w_{sr})>L(w_{st})=L(w_{rt})$. For different $k\in\mathbb{N}$,
$\Gamma_{\\{s,r\\},(tsr)^{k}}$ are different left cells in $c_{0}$. $\square$

For $n\in\mathbb{Z}$, define

$\pi_{n}:\mathbb{Z}[v,v^{-1}]\longrightarrow\mathbb{Z}\ \ \ \ \ \ \ \ $
$\sum_{k\in\mathbb{Z}}a_{k}v^{k}\longrightarrow a_{n}.$

For $z\in W$, define $\Delta(z)\in\mathbb{N}$ and
$n_{z}\in\mathbb{Z}\setminus\\{0\\}$, such that

$p_{e,z}=n_{z}v^{-\Delta(z)}+\mbox{lower degree terms}.$

Let

$\mathcal{D}=\\{z\in W|a(z)=\Delta(z)\\}.$

Proposition 3.5. We have the following propositions $P1^{\prime}-P15^{\prime}$
and $\widetilde{P}^{\prime}$. In particular, Conjectures $P1-P15$ and
$\widetilde{P}$ hold for $c_{0}$.
$P1^{\prime}$ For $z\in c_{0}$, we have $a(z)\leq\Delta(z)$.
$P2^{\prime}$ For $d\in\mathcal{D}\cap c_{0}$, $x,y\in c_{0}$, if
$\gamma_{x,y,d}\neq 0$, then $x=y^{-1}$.
$P3^{\prime}$ For $y\in c_{0}$, there exists unique $d\in\mathcal{D}\cap
c_{0}$ such that $\gamma_{y^{-1},y,d}\neq 0$.
$P4^{\prime}$ For $z,z^{\prime}\in W$, if $z\in c_{0}$ or $z^{\prime}\in
c_{0}$, and $z^{\prime}\underset{LR}{\leq}z$, then $a(z^{\prime})\geq a(z)$.
$P5^{\prime}$ For $d\in\mathcal{D}\cap c_{0}$, $y\in c_{0}$, if
$\gamma_{y^{-1},y,d}\neq 0$, then $\gamma_{y^{-1},y,d}=n_{d}=1$.
$P6^{\prime}$ For $d\in\mathcal{D}\cap c_{0}$, we have $d^{2}=e$.
$P7^{\prime}$ For $x,y,z\in W$, if $x\in c_{0}$ or $z\in c_{0}$, then
$\gamma_{x,y,z}=\gamma_{y,z,x}$.
$P8^{\prime}$ For $x,y\in W$, $z\in c_{0}$, if $\gamma_{x,y,z}\neq 0$, then
$x\underset{L}{\sim}y^{-1}$, $y\underset{L}{\sim}z^{-1}$,
$z\underset{L}{\sim}x^{-1}$.
$P9^{\prime}$ For $z,z^{\prime}\in W$, if $z\in c_{0}$ or $z^{\prime}\in
c_{0}$, $z^{\prime}\underset{L}{\leq}z$, and $a(z^{\prime})=a(z)$, then
$z^{\prime}\underset{L}{\sim}z$.
$P10^{\prime}$ For $z,z^{\prime}\in W$, if $z\in c_{0}$ or $z^{\prime}\in
c_{0}$, $z^{\prime}\underset{R}{\leq}z$, and $a(z^{\prime})=a(z)$, then
$z^{\prime}\underset{R}{\sim}z$.
$P11^{\prime}$ For $z,z^{\prime}\in W$, if $z\in c_{0}$ or $z^{\prime}\in
c_{0}$, $z^{\prime}\underset{LR}{\leq}z$, and $a(z^{\prime})=a(z)$, then
$z^{\prime}\underset{LR}{\sim}z$.
$P12^{\prime}$ If $y\in c_{0}\cap W_{I}$ for some $I\subseteq S$, then $a(y)$
computed in terms of $W_{I}$ is equal to $a(y)$ computed in terms of $W$.
$P13^{\prime}$ For any left cell $\Gamma$ in $c_{0}$, we have
$|\Gamma\cap\mathcal{D}|=1$. Assume $\Gamma\cap\mathcal{D}=\\{d\\}$, then
$\gamma_{x^{-1},x,d}\neq 0$ for all $x\in\Gamma$.
$P14^{\prime}$ For any $z\in c_{0}$, we have $z\underset{LR}{\sim}z^{-1}$.
$P15^{\prime}$ For $x,x^{\prime}\in W$, $y,w\in c_{0}$, we have the equality
$\mathop{\sum}\limits_{y^{\prime}\in c_{0}}h_{x,y^{\prime},y}\otimes
h_{w,x^{\prime},y^{\prime}}=\mathop{\sum}\limits_{y^{\prime}\in
c_{0}}h_{x,w,y^{\prime}}\otimes h_{y^{\prime},x^{\prime},y}$ in
$\mathbb{Z}[v,v^{-1}]\mathop{\otimes}\limits_{\mathbb{Z}}\mathbb{Z}[v,v^{-1}]$.
$\widetilde{P}^{\prime}$ For $x,y,z^{\prime}\in W$, $z\in c_{0}$, if
$\gamma_{x,y,z^{-1}}\neq 0$, $z^{\prime}\underset{L}{\leftarrow}z$, then there
exists $x^{\prime}\in c_{0}$, such that
$\pi_{a(z)}(h_{x^{\prime},y,z^{\prime}})\neq 0$.

Proof. By Proposition 3.2 and Theorem 3.3, we can prove
$P1^{\prime}-P15^{\prime}$ using the same method used in [Xie1, 4.1]. Here we
only give the proof of $\widetilde{P}^{\prime}$.

Since $\gamma_{x,y,z^{-1}}\neq 0$, $z\in c_{0}$, by $P8^{\prime}$, we have
$y\underset{L}{\sim}z$. Since $z^{\prime}\underset{L}{\leftarrow}z$, $z\in
c_{0}$, we get $z^{\prime}\underset{L}{\sim}z$ by $P9^{\prime}$. So
$y,z,z^{\prime}$ are in the same left cell in $c_{0}$. By Theorem 3.3(2), we
assume $y=aw_{J}b$, $z=a^{\prime}w_{J}b$, $z^{\prime}=a^{\prime\prime}w_{J}b$
for some $w_{J}\in M$, $b\in U_{J}$, $a,a^{\prime},a^{\prime\prime}\in B_{J}$.
Then we have $deg\ (T_{y}T_{z^{\prime-1}})=deg\
(T_{aw_{J}b}T_{b^{-1}w_{J}a^{\prime\prime-1}})=N$. Thus there exists
$x^{\prime}\in W$, such that $deg\ f_{y,z^{\prime-1},x^{\prime-1}}=N$, By
Lemma 1.9(3) and Theorem 3.3(1), we get $x^{\prime}\in c_{0}$. We have $deg\
f_{x^{\prime},y,z^{\prime}}=deg\ f_{y,z^{\prime-1},x^{\prime-1}}=N$, so $deg\
h_{x^{\prime},y,z^{\prime}}=N$, that is,
$\pi_{a(z)}(h_{x^{\prime},y,z^{\prime}})\neq 0$. $\square$

##  4\. The based ring of $c_{0}$

In this section, for a weighted Coxeter group of rank 3, we study the based
ring $J_{0}$ of its lowest two-sided cell $c_{0}$. We want to calculate
$t_{x}t_{y}$ for any $x,y\in c_{0}$, but it is quite a difficult problem. For
$w_{J},w_{J^{\prime}}\in M$, we set

$P_{J,J^{\prime}}=\\{x\in W|\mathcal{L}(x)=J,\ \mathcal{R}(x)=J^{\prime}\\}.$

Let

$P=\bigcup_{w_{J},w_{J^{\prime}}\in M}P_{J,J^{\prime}}.$

By [Xie2, 3.10,3.12], we have the following lemma.

Lemma 4.1. (1) For any $w\in c_{0}$, there exists unique
$w_{J},w_{J^{\prime}}\in M$, $p_{w}\in P_{J,J^{\prime}}$, $x\in U_{J}^{-1}$,
$y\in U_{J^{\prime}}$, such that $w=x\cdot p_{w}\cdot y$. Moreover, we have
$C_{w}=E_{x}C_{p_{w}}F_{y}$.
(2) Let $w_{1},w_{2},w_{3}\in c_{0}$. We have the following decomposition as
in (1).

$w_{1}=x_{1}\cdot p_{1}\cdot y_{1},\ w_{2}=x_{2}\cdot p_{2}\cdot y_{2},\
w_{3}=x_{3}\cdot p_{3}\cdot y_{3}.$

If $y_{1}=x_{2}^{-1}$, $y_{2}=x_{3}^{-1}$, $y_{3}=x_{1}^{-1}$,
$\mathcal{R}(p_{1})=\mathcal{L}(p_{2})$,
$\mathcal{R}(p_{2})=\mathcal{L}(p_{3})$,
$\mathcal{R}(p_{3})=\mathcal{L}(p_{1})$, then
$\gamma_{w_{1},w_{2},w_{3}}=\gamma_{p_{1},p_{2},p_{3}}$. Otherwise,
$\gamma_{w_{1},w_{2},w_{3}}=0$.

The lemma above simplify our work to calculate $t_{x}t_{y}$ for $x\in
P_{J,J^{\prime}}$, $y\in P_{J^{\prime},J^{\prime\prime}}$, but it is still not
easy. So we assume $x$ indecomposable at first. For $x\in
P_{J,J^{\prime}}\subseteq P$, we call $x$ indecomposable, if $x\notin M$, and
there doesn’t exist $w_{J^{\prime\prime}}\in M$, $x_{1}\in
P_{J,J^{\prime\prime}}\setminus M$, $x_{2}\in
P_{J^{\prime\prime},J^{\prime}}\setminus M$ such that
$x=x_{1}w_{J^{\prime\prime}}x_{2}$. Then we have the following proposition.

Proposition 4.2. Let $(W,S,L)$ be a weight Coxeter group of rank 3 but not an
affine Weyl group. Assume $w_{J},w_{J^{\prime}},w_{J^{\prime\prime}}\in M$,
$x\in P_{J,J^{\prime}}$ and indecomposable, $y\in
P_{J^{\prime},J^{\prime\prime}}$, then $t_{x}t_{y}=t_{xw_{J^{\prime}}y}+\delta
t_{w_{J}xy}$. If there exists $y_{1}\in W$ such that $y=x^{-1}\cdot y_{1}$,
then $\delta=1$, otherwise $\delta=0$.

To prove this proposition, we need two lemmas.

Lemma 4.3. Let $x=x_{1}\cdot w_{J^{\prime}}\in P_{J,J^{\prime}}$ and
indecomposable, $r\in J^{\prime}$. Then we have $x_{1}\cdot r\notin c_{0}$ or
$x_{1}\cdot r\in w_{J}U_{J}$.

Proof. We assume $x_{1}\cdot r\in c_{0}$. Since $x_{1}\cdot
w_{J^{\prime}}\underset{R}{\leq}x_{1}\cdot r$, we get $x_{1}\cdot
w_{J^{\prime}}\underset{R}{\sim}x_{1}\cdot r$ by $P10^{\prime}$, so
$\mathcal{L}(x_{1}\cdot r)=\mathcal{L}(x_{1}\cdot w_{J^{\prime}})=J$. Assume
$x_{1}\cdot r=w_{J}\cdot x_{2}$ for some $x_{2}\in B_{J}^{-1}$. We claim that
$x_{2}\in U_{J}$. Otherwise, there exists $r^{\prime}\in J$ such that
$r^{\prime}w_{J}\cdot x_{2}\in c_{0}$. By Theorem 3.3, we may assume
$r^{\prime}w_{J}\cdot x_{2}=x_{3}\cdot w_{J^{\prime\prime}}\cdot x_{4}$ for
some $w_{J^{\prime\prime}}\in M$, $x_{3}\in B_{J^{\prime\prime}}$, $x_{4}\in
B_{J^{\prime\prime}}^{-1}$. Then we have

$\displaystyle x=x_{1}\cdot w_{J^{\prime}}$ $\displaystyle=x_{1}\cdot r\cdot
rw_{J^{\prime}}$ $\displaystyle=r^{\prime}\cdot r^{\prime}w_{J}\cdot
x_{2}\cdot rw_{J^{\prime}}$ $\displaystyle=r^{\prime}\cdot x_{3}\cdot
w_{J^{\prime\prime}}\cdot x_{4}\cdot rw_{J^{\prime}}$
$\displaystyle=(r^{\prime}\cdot w_{3}\cdot
w_{J^{\prime\prime}})w_{J^{\prime\prime}}(w_{J^{\prime\prime}}\cdot x_{4}\cdot
rw_{J^{\prime}}).$

Since $x_{1}\cdot r\underset{R}{\leq}r^{\prime}\cdot x_{3}\cdot
w_{J^{\prime\prime}}$, we get $x_{1}\cdot r\underset{R}{\sim}r^{\prime}\cdot
x_{3}\cdot w_{J^{\prime\prime}}$ by $P10^{\prime}$, so
$\mathcal{L}(r^{\prime}\cdot x_{3}\cdot
w_{J^{\prime\prime}})=\mathcal{L}(x_{1}\cdot r)=J$. Thus, we get
$r^{\prime}\cdot x_{3}\cdot w_{J^{\prime\prime}}\in P_{J,J^{\prime\prime}}$.

On the other hand, since $x_{1}\cdot
r\underset{L}{\leq}w_{J^{\prime\prime}}\cdot x_{4}$, by $P9^{\prime}$, we get
$r\in\mathcal{R}(w_{J^{\prime\prime}}\cdot x_{4})=\mathcal{R}(x_{1}\cdot r)$,
so $\mathcal{R}(w_{J^{\prime\prime}}\cdot x_{4}\cdot
rw_{J^{\prime}})=J^{\prime}$. Thus, $w_{J^{\prime\prime}}\cdot x_{4}\cdot
rw_{J^{\prime}}\in P_{J^{\prime\prime},J^{\prime}}$, contradict to the
indecomposability of $x$. $\square$

Lemma 4.4. Let $x\in P_{J,J^{\prime}}$ with $J^{\prime}=\\{r_{1},r_{2}\\}$ and
$r_{1}\neq r_{2}$. Assume $x=x_{1}\cdot w_{J^{\prime}}$ for some $x_{1}\in
B_{J^{\prime}}$. If $\mathcal{L}(x_{1})\neq J$, then we have
$\mathcal{L}(x_{1}r_{1})\neq J$ or $\mathcal{L}(x_{1}r_{2})\neq J$.

Proof. If $\mathcal{L}(x_{1}r_{1})=\mathcal{L}(x_{1}r_{2})=J$, we assume

$x_{1}\cdot r_{1}=w_{J}\cdot x_{2}\mbox{ for some }x_{2}\in B_{J}^{-1}.$
$x_{1}\cdot r_{2}=w_{J}\cdot x_{3}\mbox{ for some }x_{3}\in B_{J}^{-1}.$

Then we have

$x=w_{J}\cdot x_{2}\cdot r_{1}w_{J^{\prime}}=w_{J}\cdot x_{3}\cdot
r_{2}w_{J^{\prime}}.$

So

$x_{2}\cdot r_{1}w_{J^{\prime}}=x_{3}\cdot r_{2}w_{J^{\prime}}.$

Since $\mathcal{L}(x_{1})\neq J$, we get $x_{2},x_{3}\in B_{J^{\prime}}$.
Thus, $r_{1}w_{J^{\prime}}=r_{2}w_{J^{\prime}}$ and then $r_{1}=r_{2}$, a
contradiction. $\square$

4.5. Now we prove Proposition 4.2. Finite Coxeter groups don’t have any
indecomposable elements. If $W$ has complete Coxeter graph, see [Xie2, 4.2].
For $x,y,z\in c_{0}$, we have $\gamma_{x,y,z}=\beta_{x,y,z}$, so we may
compute $T_{x}T_{y}$. It is much easier than computing $C_{x}C_{y}$.
If $m_{sr}=\infty$ and $m_{st}=m_{rt}=2$, we can list all the indecomposable
elements and check this proposition directly.

weight function indecomposable elements $L(s)>L(r)$ $srst$ $L(s)=L(r)$
$srt,rst$ $L(r)>L(s)$ $rsrt$

The case of $m_{sr}=m_{st}=\infty$, $m_{rt}=2$ is also easy.

weight function indecomposable elements $L(rt)>L(s)$ $rtsrt$ $L(rt)=L(s)$
$rts,srt,srs,sts$ $L(s)>L(rt)$ $srs,sts,srts$

From now on, we only consider the three cases listed in Remark 2.2. We assume
$x=x^{\prime}\cdot w_{J^{\prime}}$ for some $x^{\prime}\in B_{J^{\prime}}$,
$y=w_{J^{\prime}}\cdot y^{\prime}$ for some $y^{\prime}\in
B_{J^{\prime}}^{-1}$. Then we have

$T_{x}T_{y}=\sum_{q\leq
w_{J^{\prime}}}f_{w_{J^{\prime}},w_{J^{\prime}},q}T_{x^{\prime}q}T_{y^{\prime}}.$

When $q=w_{J^{\prime}}$, by Lemma 1.4(4) and Corollary 2.3(2), we have

$deg\
f_{w_{J^{\prime}},w_{J^{\prime}},w_{J^{\prime}}}=L(w_{J^{\prime}})=N\mbox{ and
}T_{x^{\prime}q}T_{y^{\prime}}=T_{xw_{J^{\prime}}y}.$

Since $f_{w_{J^{\prime}},w_{J^{\prime}},w_{J^{\prime}}}$ is a monic
polynomial, we know

$f_{w_{J^{\prime}},w_{J^{\prime}},w_{J^{\prime}}}T_{x^{\prime}w_{J^{\prime}}}T_{y^{\prime}}$

contributes $t_{xw_{J^{\prime}}y}$ for $t_{x}t_{y}$.
When $q<w_{J^{\prime}}$ and $l(q)\geq 2$, by Corollary 2.4(1), we have

$deg\ (f_{w_{J^{\prime}},w_{J^{\prime}},q}T_{x^{\prime}q}T_{y^{\prime}})<N.$

So

$\sum_{q<w_{J^{\prime}},\ l(q)\geq
2}f_{w_{J^{\prime}},w_{J^{\prime}},q}T_{x^{\prime}q}T_{y^{\prime}}$

has no contribution for $t_{x}t_{y}$.
Now we assume $J^{\prime}=\\{r_{1},r_{2}\\}\subseteq S$ with $r_{1}\neq
r_{2}$. Then we have

$\displaystyle\ \ \ \ \sum_{l(q)\leq
1}f_{w_{J^{\prime}},w_{J^{\prime}},q}T_{x^{\prime}q}T_{y^{\prime}}$
$\displaystyle=(v_{r_{1}}-v_{r_{1}}^{-1})T_{x^{\prime}r_{1}}T_{y^{\prime}}+(v_{r_{2}}-v_{r_{2}}^{-1})T_{x^{\prime}r_{2}}T_{y^{\prime}}+T_{x^{\prime}}T_{y^{\prime}}.$

If $deg\ ((v_{r_{1}}-v_{r_{1}}^{-1})T_{x^{\prime}r_{1}}T_{y^{\prime}})=N$ or
$deg\ (T_{x^{\prime}}T_{y^{\prime}})=N$, then we have $deg\
(T_{x^{\prime}r_{1}}T_{r_{1}y^{\prime}})=N$, so $x^{\prime}r_{1}\in c_{0}$ by
Corollary 2.3(1). Moreover, we have $x^{\prime}r_{1}\in w_{J}U_{J}$ by Lemma
4.3. Assume $f_{x^{\prime}r_{1},r_{1}y^{\prime},z}=N$ for some $z\in W$, then
$\gamma_{x^{\prime}r_{1},r_{1}y^{\prime},z}=\beta_{x^{\prime}r_{1},r_{1}y^{\prime},z}\neq
0$. By Lemma 4.1, there exists $y^{\prime\prime}\in W$, such that
$y^{\prime}=x^{\prime-1}y^{\prime\prime}$. In this case, we have
$z=(w_{J}y^{\prime\prime})^{-1}$ and
$\beta_{x^{\prime}r_{1},r_{1}y^{\prime},(w_{J}y^{\prime\prime})^{-1}}=\gamma_{x^{\prime}r_{1},r_{1}y^{\prime},(w_{J}y^{\prime\prime})^{-1}}=1$,
so precisely one of $deg\
((v_{r_{1}}-v_{r_{1}}^{-1})T_{x^{\prime}r_{1}}T_{y^{\prime}})$ and $deg\
(T_{x^{\prime}}T_{y^{\prime}})$ is $N$. Similarly, we know precisely one of
$deg\ ((v_{r_{2}}-v_{r_{2}}^{-1})T_{x^{\prime}r_{2}}T_{y^{\prime}})$ and $deg\
(T_{x^{\prime}}T_{y^{\prime}})$ is $N$.

Now we claim that precisely one of $deg\
((v_{r_{1}}-v_{r_{1}}^{-1})T_{x^{\prime}r_{1}}T_{y^{\prime}})$, $deg\
((v_{r_{2}}-v_{r_{2}}^{-1})T_{x^{\prime}r_{2}}T_{y^{\prime}})$ and $deg\
(T_{x^{\prime}}T_{y^{\prime}})$ is $N$. Otherwise, we must have $deg\
((v_{r_{1}}-v_{r_{1}}^{-1})T_{x^{\prime}r_{1}}T_{y^{\prime}})=deg\
((v_{r_{2}}-v_{r_{2}}^{-1})T_{x^{\prime}r_{2}}T_{y^{\prime}})=N$ and $deg\
(T_{x^{\prime}}T_{y^{\prime}})<N$. Thus $\mathcal{L}(x^{\prime})\neq J$. By
Lemma 4.4, we have $\mathcal{L}(x^{\prime}r_{1})\neq J$ or
$\mathcal{L}(x^{\prime}r_{2})\neq J$. Since
$x^{\prime}w_{J^{\prime}}\underset{R}{\leq}x^{\prime}r_{1}$,
$x^{\prime}w_{J^{\prime}}\underset{R}{\leq}x^{\prime}r_{2}$, we get
$x^{\prime}r_{1}\notin c_{0}$ or $x^{\prime}r_{2}\notin c_{0}$ by
$P10^{\prime}$, contradict to Corollary 2.3(1).

Summarizing the arguments above, we know

$\sum_{l(q)\leq
1}f_{w_{J^{\prime}},w_{J^{\prime}},q}T_{x^{\prime}q}T_{y^{\prime}}$

contributes $\delta t_{w_{J}xy}$ for $t_{x}t_{y}$. If there exists $y_{1}\in
W$ such that $y=x^{-1}\cdot y_{1}$, then $\delta=1$, otherwise $\delta=0$.

We have completed the proof of Proposition 4.2. $\square$

## References

  * [AF] A.Bjorner, F.Brenti: _Combinatorics of Coxeter groups_ , Springer (2005).
  * [Bre] K.Bremke: _On generalized cells in affine Weyl groups_ , J.Algebra 191 (1997) 149–173.
  * [Gao] J.Gao: _The boundness of weighted Coxeter groups of rank 3_ , arXiv:1607.02286v10, 2019.
  * [H] J.E.Humphreys: _Reflection groups and Coxeter groups_ , Cambridge Studies in Advanced Mathematics 29 (1992).
  * [KL] D.Kazhdan, G.Lusztig: _Representations of Coxeter groups and Hecke algebras_ , Invent. Math. 53 (1979) 165–184.
  * [L1] G.Lusztig: _Cells in affine Weyl groups_ , Algebraic groups and related topics, Adv. Stud. Pure Math. 6 (1985) 255–287.
  * [L2] G.Lusztig: _Cells in affine Weyl groups, II_ , J.Algebra 109 (1987) 536–548.
  * [L3] G.Lusztig: _Hecke algebras with unequal parameters_ , CRM monograph series 18 (2003).
  * [SY] J.Shi, G.Yang: _The boundness of the weighted Coxeter group with complete graph_ , Proc. Amer. Math. Soc. 144 (2016) 4573–4581.
  * [Xi1] N.Xi: _Representations of affine Hecke algebras_ , Lect. Notes Math., Springer 1587 (1994).
  * [Xi2] N.Xi: _Lusztig’s a-function for Coxeter groups with complete graphs_ , Bull. Inst. Math. Acad. Sinica 7 (1) (2012) 71–90.
  * [Xie1] X.Xie: _The based ring of the lowest generalized two-sided cell of an extended affine Weyl group_ , J.Algebra 477 (2017) 1–28.
  * [Xie2] X.Xie: _The lowest two-sided cell of a Coxeter group with complete graph_ , J.Algebra 489 (2017) 38–58.
  * [Zhou] P.Zhou: _Lusztig’s a-function for Coxeter groups of rank 3_ , J.Algebra 384 (2013) 169–193.