# On the exponent of spinor groups

Sanghoon Baek  Department of Mathematics and Statistics, University of Ottawa,
Canada<EMAIL_ADDRESS>
##  1\. Introduction

Let $G$ be a split simple simply connected group of rank $n$ over a field $F$.
Fix a maximal split torus $T$ of $G$ and a Borel subgroup $B$ containing $T$.
We denote by $W$ the Weyl group of $G$ with respect to $T$. Let $\Lambda$ be
the weight lattice of $G$ (hence, $T^{*}=\Lambda$).

We denote by $\omega_{1},\cdots,\omega_{n}$ the fundamental weights of
$\Lambda$. We let
$I_{K}:=\operatorname{Ker}(\mathbb{Z}[\Lambda]\to\mathbb{Z})$ and
$I_{CH}:=\operatorname{Ker}(S^{*}(\Lambda)\to\mathbb{Z})$ be the augmentation
ideals, where $\mathbb{Z}[\Lambda]\to\mathbb{Z}$ (respectively,
$S^{*}(\Lambda)\to\mathbb{Z}$) is the map from the group ring
$\mathbb{Z}[\Lambda]$ (respectively, the symmetric algebra) of $\Lambda$ to
the ring of integers by sending $e^{\lambda}$ to $1$ (respectively, any
element of positive degree to $0$).

For any $i\geq 0$, we consider the ring homomorphism

$\phi^{(i)}:\mathbb{Z}[\Lambda]\to\mathbb{Z}[\Lambda]/I_{K}^{i+1}\to
S^{*}(\Lambda)/I_{CH}^{i+1}\to S^{i}(\Lambda),$

where the first and the last maps are projections and the middle map sends
$e^{\sum_{j=1}^{n}a_{j}\omega_{j}}$ to
$\prod_{j=1}^{n}(1-\omega_{j})^{-a_{j}}$. The _$i$ th-exponent of $G$_
(denoted by $\tau_{i}$), as introduced in [1], is the gcd of all nonnegative
integers $N_{i}$ satisfying

$N_{i}\cdot(I_{CH}^{W})^{(i)}\subseteq\phi^{(i)}(I_{K}^{W}),$

where $I_{K}^{W}:=\langle\mathbb{Z}[\Lambda]^{W}\cap I_{K}\rangle$
(respectively, $I_{CH}^{W}:=\langle S^{*}(\Lambda)^{W}\cap I_{CH}\rangle$)
denotes the $W$-invariant augmentation ideal of $\mathbb{Z}[\Lambda]$
(respectively, $S^{*}(\Lambda)$) and $(I_{CH}^{W})^{(i)}=I_{CH}^{W}\cap
S^{i}(\Lambda)$. Informally, these numbers $\tau_{i}$ measure how far is the
ring $S^{*}(\Lambda)^{W}$ from being a polynomial ring in basic invariants.

For any $i\leq 4$, it was shown that the $i$th-exponent of $G$ divides the
Dynkin index in [1] and this integer was used to estimate the torsion of the
Grothendieck gamma filtration and the Chow groups of $E/B$, where $E/B$
denotes the twisted form of the variety of Borel subgroups $G/B$ for a
$G$-torsor $E$.

In this paper, we show that all the remaining exponents of spinor groups
divide the Dynkin index $2$.

### Acknowledgments.

The work has been partially supported from the Fields Institute and from
Zainoulline’s NSERC Discovery grant 385795-2010.

##  2\. Exponent

Let $G$ be $\operatorname{\mathbf{Spin}}_{2n+1}$ ($n\geq 3$) or
$\operatorname{\mathbf{Spin}}_{2n}$ ($n\geq 4$). The fundamental weights are
defined by

$\displaystyle\omega_{1}$
$\displaystyle=e_{1},\omega_{2}=e_{1}+e_{2},\cdots,\omega_{n-1}=e_{1}+\cdots+e_{n-1},\omega_{n}=\frac{e_{1}+\cdots+e_{n}}{2},$
$\displaystyle\omega_{1}$
$\displaystyle=e_{1},\omega_{2}=e_{1}+e_{2},\cdots,\omega_{n-1}=\frac{e_{1}+\cdots+e_{n-1}-e_{n}}{2},\omega_{n}=\frac{e_{1}+\cdots+e_{n}}{2},$

respectively, where the canonical basis of $\mathbb{R}^{n}$ is denoted by
$e_{i}$ ($1\leq i\leq n$).

For $1\leq i\leq n$, let

(1) $q_{2i}:=e_{1}^{2i}+\cdots+e_{n}^{2i}$

be the basic invariants of the group $G$, i.e., be algebraically independent
homogeneous generators of $S^{*}(\Lambda)^{W}$ as a $\mathbb{Q}$-algebra (see
[2, §3.5 and §3.12]), together with

(2) $q^{\prime}_{n}:=e_{1}\cdots e_{n}$

if $G=\operatorname{\mathbf{Spin}}_{2n}$.

For any $\lambda\in\Lambda$, we denote by $W(\lambda)$ the $W$-orbit of
$\lambda$. For any finite set $A$ of weights, we denote $-A$ the set of
opposite weights.

The Weyl groups of $\operatorname{\mathbf{Spin}}_{2n+1}$ and
$\operatorname{\mathbf{Spin}}_{2n}$ are $(\mathbb{Z}/2\mathbb{Z})^{n}\rtimes
S_{n}$ and $(\mathbb{Z}/2\mathbb{Z})^{n-1}\rtimes S_{n}$, respectively. Hence,
by the action of these Weyl groups, one has the following decomposition of
$W$-orbits: if $G=\operatorname{\mathbf{Spin}}_{2n+1}$ (respectively,
$G=\operatorname{\mathbf{Spin}}_{2n}$), then for any $1\leq k\leq n-1$
(respectively, $1\leq k\leq n-2$)

(3) $W(\omega_{k})=W_{+}(\omega_{k})\cup-W_{+}(\omega_{k}),$

where $W_{+}(\omega_{k})=\\{e_{i_{1}}\pm\cdots\pm
e_{i_{k}}\\}_{i_{1}<\cdots<i_{k}}$. If $n$ is even, then the $W$-orbits of the
last two fundamental weights of $\operatorname{\mathbf{Spin}}_{2n}$ are given
by

(4) $W(\omega_{n-1})=W_{+}(\omega_{n-1})\cup-W_{+}(\omega_{n-1})\text{ and
}W(\omega_{n})=W_{+}(\omega_{n})\cup-W_{+}(\omega_{n}),$

where $W_{+}(\omega_{n-1})$ (respectively, $W_{+}(\omega_{n})$) is the subset
of $W(\omega_{n-1})$ (respectively, $W(\omega_{n})$) containing elements of
the positive sign of $e_{1}$.

For any $\lambda=\sum_{j=1}^{n}a_{j}\omega_{j}\in\Lambda$ and any integer
$m\geq 0$, we set $\lambda(m)=\sum_{j=1}^{n}a_{j}\omega_{j}^{m}$. For example,
$\lambda(0)=\sum_{j=1}^{n}a_{j}$ and $\lambda(1)=\lambda$. We shall need the
following lemma:

######  Lemma 2.1.

$(i)$ If $G$ is $\operatorname{\mathbf{Spin}}_{2n+1}$ $($respectively,
$\operatorname{\mathbf{Spin}}_{2n}$$)$, then for any odd integer $p$, any
nonnegative integers $m_{1},\cdots,m_{p}$ and, any $1\leq k\leq n-1$
$($respectively, any $1\leq k\leq n-2$$)$, we have

$\sum_{\lambda\in W(\omega_{k})}\lambda(m_{1})\cdots\lambda(m_{p})=0.$

$(ii)$ If $G$ is $\operatorname{\mathbf{Spin}}_{2n}$ with odd $n$, then for
any even integer $p$ and any nonnegative integers $m_{1},\cdots,m_{p}$, we
have

$\sum_{\lambda\in
W(\omega_{n})}\lambda(m_{1})\cdots\lambda(m_{p})=\sum_{\lambda\in
W(\omega_{n-1})}\lambda(m_{1})\cdots\lambda(m_{p}).$

$(iii)$ If $G$ is $\operatorname{\mathbf{Spin}}_{2n}$, then for any odd
integer $p<n$ and any nonnegative integers $m_{1},\cdots,m_{p}$, we have

$\sum_{\lambda\in
W(\omega_{n})}\lambda(m_{1})\cdots\lambda(m_{p})=\sum_{\lambda\in
W(\omega_{n-1})}\lambda(m_{1})\cdots\lambda(m_{p})=0.$

###### Proof.

$(i)$ It follows from (3) that

$\displaystyle\sum_{\lambda\in
W(\omega_{k})}\lambda(m_{1})\cdots\lambda(m_{p})$
$\displaystyle=\sum_{\lambda\in
W_{+}(\omega_{k})}\lambda(m_{1})\cdots\lambda(m_{p})+\sum_{\lambda\in-
W_{+}(\omega_{k})}\lambda(m_{1})\cdots\lambda(m_{p})$
$\displaystyle=\sum_{\lambda\in
W_{+}(\omega_{k})}\lambda(m_{1})\cdots\lambda(m_{p})-\sum_{\lambda\in
W_{+}(\omega_{k})}\lambda(m_{1})\cdots\lambda(m_{p})$ $\displaystyle=0.$

$(ii)$ If $G$ is $\operatorname{\mathbf{Spin}}_{2n}$ with odd $n$, then we
have $W(\omega_{n})=-W(\omega_{n-1})$. Hence, the result immediately follows
from the assumption that $p$ is even.

$(iii)$ If $n$ is even, then the result follows from (4) by the same argument
as in the proof of $(i)$. In general, note that for any
$\lambda_{i_{1}},\cdots,\lambda_{i_{p}}\in W_{+}(\omega_{1})$ the term
$\lambda_{i_{1}}(m_{1})\cdots\lambda_{i_{p}}(m_{p})/2^{p}$ (respectively,
-$\lambda_{i_{1}}(m_{1})\cdots\lambda_{i_{p}}(m_{p})/2^{p}$) appears $2^{n-2}$
times (respectively, $2^{n-2}$) in both sums in $(iii)$. ∎

Let $p$ be an even integer and $q\geq 2$ an integer. For any nonnegative
integers $m_{1},\cdots,m_{p}$, we define

$\Lambda(p,q)(m_{1},\cdots,m_{p}):=\sum\lambda_{j_{1}}(m_{1})\cdots\lambda_{j_{p}}(m_{p}),$

where the sum ranges over all different
$\lambda_{i_{1}},\cdots,\lambda_{i_{q}}\in W_{+}(\omega_{1})$ and all
$\lambda_{i_{1}},\cdots,\lambda_{i_{p}}\\\
\in\\{\lambda_{i_{1}},\cdots,\lambda_{i_{q}}\\}$ such that the numbers of
$\lambda_{i_{1}},\cdots,\lambda_{i_{q}}$ appearing in
$\lambda_{i_{1}},\cdots,\lambda_{i_{p}}$ are all nonnegative even solutions of
$x_{1}+\cdots+x_{q}=p$. If $p<2q$, then we set
$\Lambda(p,q)(m_{1},\cdots,m_{p})=0$. Given $m_{1},\cdots,m_{p}$, we simply
write $\Lambda(p,q)$ for $\Lambda(p,q)(m_{1},\cdots,m_{p})$.

For instance, $\Lambda(4,2)$ is the sum of
$\lambda_{j_{1}}(m_{1})\lambda_{j_{2}}(m_{2})\lambda_{j_{3}}(m_{3})\lambda_{j_{4}}(m_{4})$
for all $j_{1},j_{2},j_{3},j_{4}\in\\{i,j\\}$ and all $1\leq i\neq j\leq n$
such that two $i$’s and two $j$’s appear in $j_{1},j_{2},j_{3},j_{4}$.

######  Example 2.2.

We observe that

(5)
$(x_{1}+x_{2})(x^{\prime}_{1}+x^{\prime}_{2})+(x_{1}-x_{2})(x^{\prime}_{1}-x^{\prime}_{2})=2(x_{1}x^{\prime}_{1}+x_{2}x^{\prime}_{2}).$

If $G$ is $\operatorname{\mathbf{Spin}}_{2n+1}$ or
$\operatorname{\mathbf{Spin}}_{2n}$, then by (3) and (5) we have

$\sum_{W_{+}(\omega_{2})}\lambda(m_{1})\lambda(m_{2})=2(n-1)\sum_{W_{+}(\omega_{1})}\lambda(m_{1})\lambda(m_{2})$

for any nonnegative integers $m_{1}$ and $m_{2}$ as we have $(n-1)$ choices of
such pairs in the left hand side of (5) from $W_{+}(\omega_{2})$, which
implies that

$\sum_{W(\omega_{2})}\lambda(m_{1})\lambda(m_{2})=2(n-1)\sum_{W(\omega_{1})}\lambda(m_{1})\cdots\lambda(m_{2}),$

(cf. [1, Lemma 5.1(ii)]). For any even $p\geq 4$, we apply the same argument
with the expansion of
$(x_{1}+x_{2})\cdots(x_{1}^{(p)}+x_{2}^{(p)})+(x_{1}-x_{2})\cdots(x_{1}^{(p)}-x_{2}^{(p)})$.
Then, we have

$\sum_{W_{+}(\omega_{2})}\lambda(m_{1})\cdots\lambda(m_{p})=2(n-1)\sum_{W_{+}(\omega_{1})}\lambda(m_{1})\cdots\lambda(m_{p})+2\Lambda(p,2),$

which implies that

$\sum_{W(\omega_{2})}\lambda(m_{1})\cdots\lambda(m_{p})=2(n-1)\sum_{W(\omega_{1})}\lambda(m_{1})\cdots\lambda(m_{p})+2^{2}\Lambda(p,2).$

We generalize Example 2.2 to any $\omega_{k}$ as follows.

######  Lemma 2.3.

If $G$ is $\operatorname{\mathbf{Spin}}_{2n+1}$ $($respectively,
$\operatorname{\mathbf{Spin}}_{2n}$$)$, then for any $1\leq k\leq n-1$
$($respectively, $1\leq k\leq n-2$$)$, any even $p$, and any nonnegative
integers $m_{1},\cdots m_{p}$ we have

$\sum_{W(\omega_{k})}\lambda(m_{1})\cdots\lambda(m_{p})=2^{k-1}{{n-1}\choose{k-1}}\sum_{W(\omega_{1})}\lambda(m_{1})\cdots\lambda(m_{p})+\sum_{j=2}^{k}2^{k}{{n-j}\choose{k-j}}\Lambda(p,j).$

###### Proof.

For any $\lambda\in W(\omega_{1})$, there are $2^{k}{{n-1}\choose{k-1}}$
choices of the element containing $\lambda$ in $W(\omega_{k})$, thus we have
the term
$2^{k-1}{{n-1}\choose{k-1}}\sum_{W(\omega_{1})}\lambda(m_{1})\cdots\lambda(m_{p})$
in $\sum_{W(\omega_{k})}\lambda(m_{1})\cdots\lambda(m_{p})$.

If an element $\lambda\in W(\omega_{1})$ appears odd times in a term
$\lambda_{i_{1}}(m_{1})\cdots\lambda_{i_{p}}(m_{p})$ of
$\sum_{W(\omega_{k})}\lambda(m_{1})\cdots\lambda(m_{p})$, where
$\lambda_{i_{1}},\cdots,\lambda_{i_{p}}\in W(\omega_{1})$, then by the action
of Weyl group this term vanishes in
$\sum_{W(\omega_{k})}\lambda(m_{1})\cdots\lambda(m_{p})$. Hence, the remaining
terms in $\sum_{W(\omega_{k})}\lambda(m_{1})\cdots\lambda(m_{p})$ are a linear
combination of $\Lambda(p,j)$ for all $2\leq j\leq k$ such that $p\geq 2k$. As
each term $\Lambda(p,j)$ appears $2^{k}{{n-j}\choose{k-j}}$ times in
$\sum_{W(\omega_{k})}\lambda(m_{1})\cdots\lambda(m_{p})$, the result follows.
∎

For any $\lambda\in\Lambda$, we denote by $\rho(\lambda)$ the sum of all
elements $e^{\mu}\in\mathbb{Z}[\Lambda]$ over all elements $\mu$ of
$W(\lambda)$. Let $i!\cdot\phi^{(i)}(e^{\lambda})=\lambda^{i}+S_{i}$ for any
$i\geq 1$, where $S_{i}$ is the sum of remaining terms in
$i!\cdot\phi^{(i)}(e^{\lambda})$ and $\lambda=\sum a_{j}\omega_{j}$,
$a_{j}\in\mathbb{Z}$. Hence, for any fundamental weight $\omega_{k}$ we have

(6)
$i!\cdot\phi^{(i)}(\rho(\omega_{k}))=\sum_{W(\omega_{k})}\lambda^{i}+\sum_{W(\omega_{k})}S_{i}.$

We view $i!\cdot\phi^{(i)}(e^{\lambda})$ as a polynomial in variables
$\lambda,\lambda(m_{1}),\cdots,\lambda(m_{j})$ for some nonnegative integers
$m_{1},\cdots,m_{j}$. Let $T_{i}$ be the sum of monomials in $S_{i}$ whose
degrees are even.

If $G$ is $\operatorname{\mathbf{Spin}}_{2n+1}$ $($respectively,
$\operatorname{\mathbf{Spin}}_{2n}$$)$, then by Lemma 2.1(i) the equation (6)
reduces to

(7)
$i!\cdot\phi^{(i)}(\rho(\omega_{k}))=\sum_{W(\omega_{k})}\lambda^{i}+\sum_{W(\omega_{k})}T_{i}.$

for any $1\leq k\leq n-1$ $($respectively $1\leq k\leq n-2$$)$.

Given $p$ and $q$, we define

$\Omega(p,q):=\sum\Lambda(p,q)(m_{1},\cdots,m_{p}),$

where the sum ranges over all $m_{1},\cdots,m_{p}$ which appear in all
monomials of $T_{i}$.

######  Example 2.4.

$(i)$ If $G$ is $\operatorname{\mathbf{Spin}}_{2n+1}$ or
$\operatorname{\mathbf{Spin}}_{2n}$ and $i=4$, then by (7) and Lemma 2.3 we
have

$\displaystyle 4!\phi^{(4)}(\rho(\omega_{1}))$
$\displaystyle=\sum_{W(\omega_{1})}\lambda^{4}+\sum_{W(\omega_{1})}T_{4},$
$\displaystyle 4!\phi^{(4)}(\rho(\omega_{2}))$
$\displaystyle=\sum_{W(\omega_{2})}\lambda^{4}+\sum_{W(\omega_{2})}T_{4}$
$\displaystyle=\sum_{W(\omega_{2})}\lambda^{4}+2(n-1)\sum_{W(\omega_{1})}T_{4},$

which implies that

$4!(\phi^{(4)}(\rho(\omega_{2}))-2(n-1)\phi^{(4)}(\rho(\omega_{1})))=\sum_{W(\omega_{2})}\lambda^{4}-2(n-1)\sum_{W(\omega_{1})}\lambda^{4}.$

By Lemma 2.3, the right-hand side of the above equation is equal to

$4\Lambda(4,2)=4\cdot\frac{4!}{2!2!}\sum_{i<j}e_{i}^{2}e_{j}^{2}.$

Hence, we have

$\phi^{(4)}(\rho(\omega_{2}))-2(n-1)\phi^{(4)}(\rho(\omega_{1}))=\sum_{i<j}e_{i}^{2}e_{j}^{2}.$

$(ii)$ If $G$ is $\operatorname{\mathbf{Spin}}_{2n+1}$ ($n\geq 4$) or
$\operatorname{\mathbf{Spin}}_{2n}$ ($n\geq 5$) and $i=6$, then by (7) and
Lemma 2.3 we have

$\displaystyle 6!\phi^{(6)}(\rho(\omega_{1}))$
$\displaystyle=\sum_{W(\omega_{1})}\lambda^{6}+\sum_{W(\omega_{1})}T_{6},$
$\displaystyle 6!\phi^{(6)}(\rho(\omega_{2}))$
$\displaystyle=\sum_{W(\omega_{2})}\lambda^{6}+2(n-1)\sum_{W(\omega_{1})}T_{6}+4\Omega(4,2),$
$\displaystyle 6!\phi^{(6)}(\rho(\omega_{3}))$
$\displaystyle=\sum_{W(\omega_{3})}\lambda^{6}+4{{n-1}\choose{2}}\sum_{W(\omega_{1})}T_{6}+8(n-2)\Omega(4,2),$

which implies that

$\phi^{(6)}(\rho(\omega_{3}))-2(n-2)\phi^{(6)}(\rho(\omega_{2}))+2(n-1)(n-2)\phi^{(6)}(\rho(\omega_{1}))=\sum_{i<j<k}e_{i}^{2}e_{j}^{2}e_{k}^{2}.$

######  Lemma 2.5.

$(i)$ If $G$ is $\operatorname{\mathbf{Spin}}_{2n}$, then we have

$\sum_{W(\omega_{n})}\lambda^{n}-\sum_{W(\omega_{n-1})}\lambda^{n}=n!e_{1}\cdots
e_{n}.$

$(ii)$ If $G$ is $\operatorname{\mathbf{Spin}}_{2n}$, then for any $1\leq
p\leq n-1$ and any nonnegative integers $m_{1},\cdots,m_{p}$ we have

$\sum_{W(\omega_{n})}\lambda(m_{1})\cdots\lambda(m_{p})=\sum_{W(\omega_{n-1})}\lambda(m_{1})\cdots\lambda(m_{p}).$

###### Proof.

$(i)$ First, assume that $n\geq 4$ is even. We show that

$\sum_{W_{+}(\omega_{n})}\lambda^{n}-\sum_{W_{+}(\omega_{n-1})}\lambda^{n}=(n!/2)e_{1}\cdots
e_{n}.$

As $|W_{+}(\omega_{n})|=|W_{+}(\omega_{n-1})|=2^{n-2}$, we have

$(n!/2^{n})2^{n-2}e_{1}\cdots e_{n}-(-(n!/2^{n})2^{n-2}e_{1}\cdots
e_{n})=(n!/2)e_{1}\cdots e_{n}$

in $\sum_{W(\omega_{n})}\lambda^{n}-\sum_{W(\omega_{n-1})}\lambda^{n}$. If one
of the exponents $i_{1},\cdots,i_{n}$ in $e_{1}^{i_{1}}\cdots e_{n}^{i_{n}}$
(except the case $i_{1}=\cdots=i_{n}=1$) is odd, then from the orbits
$W_{+}(\omega_{n})$ and $W_{+}(\omega_{n-1})$ this monomial vanishes in each
sum of
$\sum_{W_{+}(\omega_{n})}\lambda^{n}-\sum_{W_{+}(\omega_{n-1})}\lambda^{n}$.
Otherwise, the terms
$2^{n-2}\sum_{j=1}^{n}e_{j}^{n},\Lambda(n,2)\cdots,\Lambda(n,n/2)$ with
$m_{1}=\cdots=m_{n}=1$ are in both $\sum_{W_{+}(\omega_{n})}\lambda^{n}$ and
$\sum_{W_{+}(\omega_{n-1})}\lambda^{n}$.

Now, we assume that $n\geq 4$ is odd. As
$|W(\omega_{n})|=|W(\omega_{n-1})|=2^{n-1}$, we have

$(n!/2^{n})2^{n-1}e_{1}\cdots e_{n}-(-(n!/2^{n})2^{n-1}e_{1}\cdots
e_{n})=n!e_{1}\cdots e_{n}$

in $\sum_{W(\omega_{n})}\lambda^{n}-\sum_{W(\omega_{n-1})}\lambda^{n}$. By the
same argument, if one of the exponents $i_{1},\cdots,i_{n}$ in
$e_{1}^{i_{1}}\cdots e_{n}^{i_{n}}$ (except the case $i_{1}=\cdots=i_{n}=1$)
is odd, then this monomial vanishes in each sum of
$\sum_{W(\omega_{n})}\lambda^{n}-\sum_{W(\omega_{n-1})}\lambda^{n}$. This
completes the proof of $(i)$.

$(ii)$ By Lemma 2.1(ii)(iii), it is enough to consider the case where both $n$
and $p$ are even. For any $p$ and any $n\geq p+2$, we have
$2^{n-2}(\sum_{W_{+}(\omega_{1})}\lambda(m_{1})\cdots\lambda(m_{p}))$ in both
$\sum_{W_{+}(\omega_{n})}\lambda(m_{1})\cdots\lambda(m_{p})$ and
$\sum_{W_{+}(\omega_{n-1})}\lambda(m_{1})\cdots\lambda(m_{p})$. By the action
of Weyl group, any term $\lambda_{i_{1}}(m_{1})\cdots\lambda_{i_{p}}(m_{p})$,
where an element $\lambda\in W(\omega_{1})$ appears odd times in either
$\sum_{W_{+}(\omega_{n})}\lambda(m_{1})\cdots\lambda(m_{p})-2^{n-2}(\sum_{W_{+}(\omega_{1})}\lambda(m_{1})\\\
\cdots\lambda(m_{p}))$ or
$\sum_{W_{+}(\omega_{n-1})}\lambda(m_{1})\cdots\lambda(m_{p})-2^{n-2}(\sum_{W_{+}(\omega_{1})}\lambda(m_{1})\cdots\lambda(m_{p}))$,
vanishes. As each term of $\Lambda(p,2),\cdots,\Lambda(p,p/2)$ appears in both
$\sum_{W_{+}(\omega_{n})}\lambda(m_{1})\cdots\\\ \lambda(m_{p})$ and
$\sum_{W_{+}(\omega_{n-1})}\lambda(m_{1})\cdots\lambda(m_{p})$, this completes
the proof.

∎

######  Theorem 2.6.

If $G$ is $\operatorname{\mathbf{Spin}}_{2n+1}$ $($respectively,
$\operatorname{\mathbf{Spin}}_{2n}$$)$, then for any $i\geq 3$ and any
$n\geq[i/2]+1$ $($respectively, $n\geq[i/2]+2$$)$ the exponent $\tau_{i}$
divides the Dynkin index $\tau_{2}=2$.

###### Proof.

As $B_{2}=C_{2}$ and $D_{3}=A_{3}$, we have $1=\tau_{3}\mid 2$ by [1, Theorem
5.4]. If $G$ is $\operatorname{\mathbf{Spin}}_{2n}$ for any $n\geq 4$, then by
Lemma 2.5(i)(ii) we have

$q^{\prime}_{n}=\phi^{(n)}(\rho(\omega_{n}))-\phi^{(n)}(\rho(\omega_{n-1})),$

which implies that the invariant $q^{\prime}_{n}$ is in the ideal generated by
the image of $\phi^{(n)}$. As there are no invariants of odd degree except
$q^{\prime}_{n}$, we have

$\tau_{2i+1}\mid\tau_{2i}$

for all $i\geq 1$. Therefore, it suffices to show that $\tau_{2i}\mid\tau_{2}$
for any $i\geq 2$.

By Lemma 2.3 together with the same argument as in Example 2.4 we have

(8)
$\phi^{(2i)}(\rho(\omega_{i}))+\sum_{j=1}^{i-1}a_{j}\phi^{(2i)}(\rho(\omega_{i-j}))=\sum_{j_{1}<\cdots<j_{i}}e_{j_{1}}^{2}\cdots
e_{j_{i}}^{2},$

where the integers $a_{1},\cdots,a_{i-1}$ satisfy

$\Big{(}\sum_{j=k}^{i-2}2^{j+1}{{n-1-k}\choose{j-k}}a_{j+1}\Big{)}+2^{i}{{n-1-k}\choose{i-1-k}}=0,$

for $0\leq k\leq i-2$. Let $p_{i}$ be the right-hand side of (8). Then this
equation implies that $p_{i}$ is in the image of $\phi^{(2i)}$.

We show that the invariant $q_{2i}$ is in the ideal $\phi^{(2i)}(I_{K}^{W})$
for any $i\geq 2$. We proceed by induction on $i$. As
$q_{2}=\phi^{(2)}(\rho(\omega_{1}))$, the case $i=2$ is obvious. By Newton’s
identities we have

(9) $(-1)^{i-1}q_{2i}=ip_{i}-\sum_{j=1}^{i-1}(-1)^{j-1}p_{i-1-j}q_{2j}$

with $p_{0}=1$. By the induction hypothesis, the sum of (9) is in
$\phi^{(2i)}(I_{K}^{W})$. Hence, $q_{2i}$ is in $\phi^{(2i)}(I_{K}^{W})$. ∎

For any nonnegative integer $n$, we denote by $v_{2}(n)$ the $2$-adic
valuation of $n$. For a smooth projective variety $X$ over $F$, we denote by
$\Gamma^{*}K(X)$ the gamma filtration on the Grothendieck ring $K(X)$. We let
$c_{CH}:S^{*}(\Lambda)\to CH(G/B)$ be the characteristic map.

######  Corollary 2.7.

Let $G$ be $\operatorname{\mathbf{Spin}}_{2n}$ $($respectively,
$\operatorname{\mathbf{Spin}}_{2n+1}$$)$. If $2^{m(i)}(\ker
c_{CH})^{(i)}\subseteq(I_{CH}^{W})^{(i)}$ for some nonnegative integer $m(i)$,
then for any $i\geq 3$ and any $n\geq[i/2]+2$ $($respectively,
$n\geq[i/2]+1$$)$ the torsion of $\Gamma^{i}K(G/B)/\Gamma^{i+1}K(G/B)$ is
annihilated by $2^{g(i)}$, where $g(i)=1+m(i)+v_{2}((i-1)!)$.

######  Remark 2.8.

It is shown that $m(3)=0$ and $m(4)=1$ in [1, Lemma 6.4].

###### Proof.

The proof of [1, Theorem 6.5] still works with Theorem 2.6. ∎

######  Corollary 2.9.

Let $G$ be $\operatorname{\mathbf{Spin}}_{2n}$ $($respectively,
$\operatorname{\mathbf{Spin}}_{2n+1}$$)$. If $2^{m(i)}(\ker
c_{CH})^{(i)}\subseteq(I_{CH}^{W})^{(i)}$ for some nonnegative integer $m(i)$,
then for any $G$-torsor $E$, any $i\geq 3$ and any $n\geq[i/2]+2$
$($respectively, $n\geq[i/2]+1$$)$ the torsion of $\operatorname{CH}^{i}(E/B)$
is annihilated by $2^{t(i)}$, where $t(i)=1+\sum_{j=3}^{i}g(j)+v_{2}((i-1)!)$.

###### Proof.

By [3, Theorem 2.2(2)], we have

$\Gamma^{i}K(G/B)/\Gamma^{i+1}K(G/B)\simeq\Gamma^{i}K(E/B)/\Gamma^{i+1}K(E/B).$

As the torsion of $\operatorname{CH}^{i}(E/B)$ is annihilated by

$(i-1)!\prod_{j=1}^{i}e(\Gamma^{i}K(E/B)/\Gamma^{i+1}K(E/B)),$

where $e(\Gamma^{i}K(E/B)/\Gamma^{i+1}K(E/B))$ denotes the finite exponent of
its torsion subgroup (see [1, p.149]), the result follows from Corollary 2.7.
∎

## References

  * [1] S. Baek, E. Neher, K. Zainoulline, _Basic polynomial invariants, fundamental representations and the Chern class map_ , Doc. Math. 17 (2012), 135–150.
  * [2] J. Humphreys, _Reflection groups and Coxeter groups_. Cambridge studies in Advanced Math. 29, Cambridge Univ. Press (1990).
  * [3] I. A. Panin, _On the algebraic K-theory of twisted flag varieties_ , K-Theory 8 (1994), no. 6, 541–585.


equalities and inequalities hold almost surely:

$\displaystyle M^{(q)}_{i}(t)$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\mathbf{1}\left(\sum^{t-1}_{\tau=\max\\{t-d_{\text{max}},1\\}}\hat{A}_{i}(\tau)\mathbf{1}(\hat{D}_{i}(\tau)\geq
t-\tau+1)>c_{i}-a_{\text{max}}\right)~{}\bigg{|}~{}{\cal
H}(\tau^{(q-1)})\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\mathbf{1}\left((1+\varepsilon)^{\sum^{t-1}_{\tau=\max\\{t-d_{\text{max}},1\\}}\frac{\hat{A}_{i}(\tau)}{a_{\text{max}}}\mathbf{1}(\hat{D}_{i}(\tau)\geq
t-\tau+1)}>(1+\varepsilon)^{\frac{c_{i}}{a_{\text{max}}}-1}\right)~{}\bigg{|}~{}{\cal
H}(\tau^{(q-1)})\right]$ $\displaystyle\leq$
$\displaystyle\frac{1}{(1+\varepsilon)^{\frac{c_{i}}{a_{\text{max}}}-1}}\cdot\mathbb{E}\left[(1+\varepsilon)^{\sum^{t-1}_{\tau=\max\\{t-d_{\text{max}},1\\}}\frac{\hat{A}_{i}(\tau)}{a_{\text{max}}}\mathbf{1}(\hat{D}_{i}(\tau)\geq
t-\tau+1)}~{}\bigg{|}~{}{\cal H}(\tau^{(q-1)})\right]$ (53) $\displaystyle=$
$\displaystyle\frac{1}{(1+\varepsilon)^{\frac{c_{i}}{a_{\text{max}}}-1}}\cdot\prod^{t-1}_{\tau=\max\\{t-d_{\text{max}},1\\}}\mathbb{E}\left[(1+\varepsilon)^{\frac{\hat{A}_{i}(\tau)}{a_{\text{max}}}\mathbf{1}(\hat{D}_{i}(\tau)\geq
t-\tau+1)}~{}\bigg{|}~{}{\cal H}(\tau^{(q-1)})\right]$ (54)
$\displaystyle\leq$
$\displaystyle\frac{1}{(1+\varepsilon)^{\frac{c_{i}}{a_{\text{max}}}-1}}\cdot\prod^{t-1}_{\tau=\max\\{t-d_{\text{max}},1\\}}\left(1+\varepsilon\cdot\mathbb{E}\left[\frac{\hat{A}_{i}(\tau)}{a_{\text{max}}}\mathbf{1}(\hat{D}_{i}(\tau)\geq
t-\tau+1)~{}\bigg{|}~{}{\cal H}(\tau^{(q-1)})\right]\right)$ (55)
$\displaystyle\leq$
$\displaystyle\frac{1}{(1+\varepsilon)^{\frac{c_{i}}{a_{\text{max}}}-1}}\cdot\prod^{t-1}_{\tau=\max\\{t-d_{\text{max}},1\\}}\left(1+\varepsilon\cdot\mathbb{E}[B(\tau)]\mathbb{E}\left[\frac{\tilde{A}_{i}(\tau)}{a_{\text{max}}}\mathbf{1}(\tilde{D}_{i}(\tau)\geq
t-\tau+1)~{}\bigg{|}~{}{\cal H}(\tau^{(q-1)})\right]\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{(1+\varepsilon)^{\frac{c_{i}}{a_{\text{max}}}-1}}\cdot\prod^{t-1}_{\tau=\max\\{t-d_{\text{max}},1\\}}\exp\left(\varepsilon\cdot\mathbb{E}[B(\tau)]\mathbb{E}\left[\frac{\tilde{A}_{i}(\tau)}{a_{\text{max}}}\mathbf{1}(\tilde{D}_{i}(\tau)\geq
t-\tau+1)~{}\bigg{|}~{}{\cal H}(\tau^{(q-1)})\right]\right)$ (56)
$\displaystyle=$
$\displaystyle\frac{1}{(1+\varepsilon)^{\frac{c_{i}}{a_{\text{max}}}-1}}\cdot\exp\left(\frac{\varepsilon}{a_{\text{max}}}\cdot\frac{1}{1+\bar{\epsilon}^{(q)}_{D}+\eta}\sum^{t-1}_{\tau=\max\\{t-d_{\text{max}},1\\}}\mathbb{E}\left[\tilde{A}_{i}(\tau)\mathbf{1}(\tilde{D}_{i}(\tau)\geq
t-\tau+1)~{}\bigg{|}~{}{\cal H}(\tau^{(q-1)})\right]\right)$ (57)
$\displaystyle\leq$
$\displaystyle\frac{1}{(1+\varepsilon)^{\frac{c_{i}}{a_{\text{max}}}-1}}\cdot\exp\left(\frac{\varepsilon}{a_{\text{max}}}\cdot\frac{1}{1+\bar{\epsilon}^{(q)}_{D}+\eta}\sum^{t}_{\tau=t-d_{\text{max}}+1}\sum^{d_{\max}}_{s=t-\tau+1}\mathbb{E}\left[\tilde{A}_{i}(\tau)\mathbf{1}(\tilde{D}_{i}(\tau)=s)~{}\bigg{|}~{}{\cal
H}(\tau^{(q-1)})\right]\right)$ $\displaystyle=$
$\displaystyle\frac{1}{(1+\varepsilon)^{\frac{c_{i}}{a_{\text{max}}}-1}}\cdot\exp\left(\frac{\varepsilon}{a_{\text{max}}}\cdot\frac{1}{1+\bar{\epsilon}^{(q)}_{D}+\eta}\sum^{d_{\max}}_{s=1}\sum^{t}_{\tau=t-s+1}\mathbb{E}\left[\tilde{A}_{i}(\tau)\mathbf{1}(\tilde{D}_{i}(\tau)=s)~{}\bigg{|}~{}{\cal
H}(\tau^{(q-1)})\right]\right)$ $\displaystyle=$
$\displaystyle\frac{1}{(1+\varepsilon)^{\frac{c_{i}}{a_{\text{max}}}-1}}\cdot\exp\left(\frac{\varepsilon}{a_{\text{max}}}\cdot\frac{1}{1+\bar{\epsilon}^{(q)}_{D}+\eta}\sum^{d_{\max}}_{s=1}\sum^{t}_{\tau=t-s+1}\mathbb{E}\left[\tilde{A}_{i}(t)\mathbf{1}(\tilde{D}_{i}(t)=s)~{}\bigg{|}~{}{\cal
H}(\tau^{(q-1)})\right]\right)$ (58) $\displaystyle=$
$\displaystyle\frac{1}{(1+\varepsilon)^{\frac{c_{i}}{a_{\text{max}}}-1}}\cdot\exp\left(\frac{\varepsilon}{a_{\text{max}}}\cdot\frac{1}{1+\bar{\epsilon}^{(q)}_{D}+\eta}\sum^{d_{\max}}_{s=1}\mathbb{E}\left[\tilde{A}_{i}(t)\cdot
s\cdot\mathbf{1}(\tilde{D}_{i}(t)=s)~{}\bigg{|}~{}{\cal
H}(\tau^{(q-1)})\right]\right)$ $\displaystyle=$
$\displaystyle\frac{1}{(1+\varepsilon)^{\frac{c_{i}}{a_{\text{max}}}-1}}\cdot\exp\left(\frac{\varepsilon}{a_{\text{max}}}\cdot\frac{1}{1+\bar{\epsilon}^{(q)}_{D}+\eta}\cdot\mathbb{E}\left[\tilde{A}_{i}(t)\tilde{D}_{i}(t)~{}\bigg{|}~{}{\cal
H}(\tau^{(q-1)})\right]\right)$ $\displaystyle=$
$\displaystyle\frac{1}{(1+\varepsilon)^{\frac{c_{i}}{a_{\text{max}}}-1}}\cdot\exp\left[\frac{\varepsilon}{a_{\text{max}}}\frac{1}{1+\bar{\epsilon}^{(q)}_{D}+\eta}\cdot\frac{2}{\tau^{(q-1)}}\sum^{\tau^{(q-1)}/2}_{s=1}v_{i,j(s),k^{(q)}(s)}\right].$
(59)

Step (53) is by the Markov inequality. Step (54) follows from the joint
independence of
$\\{\frac{\hat{A}_{i}(\tau)}{a_{\text{max}}}\mathbf{1}(\hat{D}_{i}(\tau)\geq
t-\tau+1)\\}^{t-1}_{\tau=\max\\{t-d_{\text{max}},1\\}}$ conditioned on ${\cal
H}(\tau^{(q-1)})$, thanks to the coupling argument. Step (55) is by the fact
that $(1+\varepsilon)^{a}\leq 1+\varepsilon\cdot a$ for all
$a\in[0,1],\varepsilon>0$. Step (56) is by the inequality $1+\varepsilon\leq
e^{\epsilon}$ which holds for all $\varepsilon>0$. In step (57), it is crucial
to that the range of summation, namely
$\\{\max\\{t-d_{\text{max}},1\\},\ldots,t-1\\}$, lies inside the time interval
of phase $q$, by our assumption that
$t\in\\{\tau^{(q-1)}+1+d_{\text{max}},\ldots,\tau^{(q)}\\}$. Now, recall
Algorithm 1 Line 12 that constructs $\tilde{k}(t)$ and the definition of
$(\tilde{W}(t),\tilde{A}(t),\tilde{D}(t))\sim{\cal O}_{j(t),\tilde{k}(t)}$ in
our coupling argument. These two facts imply that
$\\{(\tilde{A}_{i}(\tau),\tilde{D}_{i}(\tau))\\}^{t}_{\tau=\max\\{t-d_{\text{max}},1\\}}$
are iid conditioned on ${\cal H}(\tau^{(q-1)})$, which leads to step (58).
Finally, step (59) follows from taking the conditional expectation and
recalling the way $\tilde{k}(t)$ is constructed in Algorithm 1.

Inequality (51) follows from a direct application of Lemma 4.4. Inequality
(52) follows by routine calculations and the assumptions on
$\bar{\epsilon}^{(q)}_{D},\eta$. Now, we set
$\varepsilon=\frac{\eta}{1+\bar{\epsilon}^{(q)}_{D}}$. By Assumption 4 we know
$\eta\leq 1$, and therefore $\varepsilon\leq 1$. Recall that
$\bar{\epsilon}^{(q)}_{D}=\epsilon^{(q)}_{D}/c_{\text{min}}$, we have

$\displaystyle\frac{1}{(1+\varepsilon)^{\frac{c_{i}}{a_{\text{max}}}-1}}\cdot\exp\left[\frac{\varepsilon}{a_{\text{max}}}\frac{c_{i}+\epsilon^{(q)}_{D}}{1+\bar{\epsilon}^{(q)}_{D}+\eta}\right]$
$\displaystyle\leq(1+\varepsilon)\cdot\frac{1}{(1+\varepsilon)^{\frac{c_{i}}{a_{\text{max}}}}}\cdot\exp(\frac{\varepsilon}{1+\varepsilon}\cdot\frac{c_{i}}{a_{\text{max}}})$
(60)
$\displaystyle=(1+\varepsilon)\left[\frac{e^{\varepsilon}}{(1+\varepsilon)^{1+\varepsilon}}\right]^{\frac{c_{i}}{a_{\text{max}}}\cdot\frac{1}{1+\varepsilon}}$
$\displaystyle\leq(1+\varepsilon)\cdot\exp\left[-\frac{\varepsilon^{2}}{(1+\varepsilon)(2+\varepsilon)}\cdot\frac{c_{i}}{a_{\text{max}}}\right]$
$\displaystyle\leq(1+\varepsilon)\cdot\exp\left[-\frac{\varepsilon^{2}}{(1+\varepsilon)(2+\varepsilon)}\cdot\frac{1}{\xi}\right].$
(61)

Recall from (5) that

$\eta=\sqrt{\xi\log\frac{|\mathcal{I}_{c}|}{\xi}},\quad\bar{\epsilon}^{(q)}_{D}=\frac{\epsilon^{(q)}_{D}}{c_{\text{min}}}\text{,
where
}\epsilon^{(q)}_{D}=8\gamma\sqrt{\frac{\log((|\mathcal{I}_{r}|+|\mathcal{I}_{c}|)/\delta)}{\tau^{(q-1)}}}.$

Recalling our assumption that
$\tau^{(q-1)}\geq\frac{384\gamma^{2}}{c_{\text{min}}^{2}}\log\frac{|\mathcal{I}_{r}|+|\mathcal{I}_{c}|}{\delta}$,
(61) can be upper bounded as

$(\ref{eq:reject_bd_3_1})\leq
2\exp\left(-\frac{\eta^{2}}{6\xi(1+\bar{\epsilon}^{(q)}_{D})^{2}}\right)=2\exp\left(-\frac{\tau^{(q-1)}c_{\min}^{2}\log(|\mathcal{I}_{c}|/\xi)}{384\gamma^{2}\log((|\mathcal{I}_{r}|+|\mathcal{I}_{c}|)/\delta)}\right)\leq\frac{2}{|\mathcal{I}_{c}|}\sqrt{\xi}.$

Altogether, the Lemma is proved. $\square$

###  8.6 Proof of Lemma 4.7

We first remark that the Lemma does not follow directly from the conditional
Chernoff inequality in Lemma 4.8. Indeed, the random variables
$\\{L(t)\hat{W}_{i}(t)\\}^{\tau^{(q)}}_{t=\bar{\tau}^{(q-1)}+1}$ are
correlated even when we condition on ${\cal H}(\tau^{(q-1)})$. Instead, we
apply Lemma 4.8 on suitable subsets of
$\\{L(t)\hat{W}_{i}(t)\\}^{\tau^{(q)}}_{t=\bar{\tau}^{(q-1)}+1}$ that
partition $\\{L(t)\hat{W}_{i}(t)\\}^{\tau^{(q)}}_{t=\bar{\tau}^{(q-1)}+1}$. To
this end, we define
$N=\lceil\frac{\tau^{(q)}-\bar{\tau}^{(q-1)}}{d_{\text{max}}+1}\rceil$. For
$\ell\in\\{1,\ldots,d_{\text{max}}+1\\}$ and $n\in\\{1,\ldots,N\\}$, we define
the time index

$t(n;\ell)=\bar{\tau}^{(q-1)}+\ell+(n-1)\cdot(d_{\text{max}}+1).$

Clearly, we have
$\\{t(n;\ell)\\}_{n\in\\{1,\ldots,N\\},\ell\in\\{1,\ldots,d_{\text{max}}+1\\}}\supseteq\\{\bar{\tau}^{(q-1)}+1,\ldots,\tau^{(q)}\\}$.
Cruically, we observe that for any $\ell\in\\{1,\ldots,d_{\text{max}}+1\\}$,
the random variables in the collection

$\Psi(\ell)=\\{L(t(n;\ell))\cdot\hat{W}_{i}(t(n;\ell))\\}^{N}_{n=1}$

are independent and identically distributed conditioned on ${\cal
H}(\tau^{(q-1)})$.

We first show the conditional independence. For every $t$, the random variable
$L(t)\hat{W}_{i}(t)$ is
$\sigma(\\{(\hat{W}(\tau),\hat{A}(\tau),\hat{D}(\tau))\\}^{t}_{\tau=t-d_{\text{max}}})$-measurable.
More precisely, by the definition of $L(t),\hat{W}_{i}(t)$, we know that there
is a deterministic function $g_{i}$ such that
$L(t)\hat{W}_{i}(t)=g_{i}(\\{(\hat{W}(\tau),\hat{A}(\tau),\hat{D}(\tau))\\}^{t}_{\tau=t-d_{\text{max}}})$,
where $g_{i}$ does not vary with $t$ and only depends on $i$. Since the time
indexes in $\Psi(\ell)$ are at least $d_{\text{max}}+1$ time steps apart, we
know that for any two distinct $n,n^{\prime}\in\\{1,\ldots,N\\}$, the time
indexes sets $\\{t(n;\ell)-d_{\text{max}},\ldots,t(n,\ell)\\}$ and
$\\{t(n^{\prime};\ell)-d_{\text{max}},\ldots,t(n^{\prime},\ell)\\}$ are
disjoint. By observing that
$\\{(\hat{W}(\tau),\hat{A}(\tau),\hat{D}(\tau))\\}^{\tau^{(q)}}_{\tau=\bar{\tau}^{(q-1)}-d_{\text{max}}}$
are independent conditioned on ${\cal H}(\tau^{(q-1)})$, we know that the
random variables in $\Psi(\ell)$ are independent conditioned on ${\cal
H}(\tau^{(q-1)})$.

The identically distributed part follows from the fact that, for any
$t\in\\{\bar{\tau}^{(q-1)}+1,\ldots,\tau^{(q)}\\}$, we know that
$\\{t-d_{\text{max}},\ldots,t\\}\subset\\{\tau^{(q-1)}+1,\ldots,\tau^{(q)}\\}$.
In addition, by the coupling argument on the construction of
$\hat{W},\hat{A},\hat{D}$, we know that
$\\{(\hat{W}(t),\hat{A}(t),\hat{D}(t))\\}^{\tau^{(q)}}_{t=\tau^{(q-1)}+1}$ are
identically distributed conditioned on ${\cal H}(\tau^{(q-1)})$, since all the
time indexes in $\\{\tau^{(q-1)}+1,\ldots,\tau^{(q)}\\}$ belong to phase $q$.
Since
$L(t)\hat{W}_{i}(t)=g_{i}(\\{(\hat{W}(\tau),\hat{A}(\tau),\hat{D}(\tau))\\}^{t}_{\tau=t-d_{\text{max}}})$
and $g_{i}$ does not vary with $t$, we know that
$\\{L(t)\hat{W}_{i}(t)\\}^{\tau^{(q)}}_{t=\bar{\tau}^{(q-1)}+1}$ are
identically distributed conditioned on ${\cal H}(\tau^{(q-1)})$, which in
particular implies that the random variables in $\Psi(\ell)$ are identically
distributed conditioned on ${\cal H}(\tau^{(q-1)})$.

After establishing the claim that the random variables in $\Psi(\ell)$ are
conditionally iid for any $\ell$, we apply the conditional Chernoff inequality
(Lemma 4.8) on the random variables in $\Psi(\ell)$, along with ${\cal
F}={\cal H}(\tau^{(q-1)})$ and $B=w_{\text{max}}$. Summing (20) over
$t\in\\{t(n;\ell)\\}^{N}_{n=1}$ gives us that, with probability at least
$1-7\delta$, it holds that

$\displaystyle\sum^{N}_{n=1}\mathbb{E}[\hat{W}_{i}(t(n;\ell))L(t(n;\ell))~{}|~{}{\cal
H}(\tau^{(q-1)})]=\mu_{-}(\ell)$ $\displaystyle\geq$
$\displaystyle\left(1-{\color[rgb]{0,0,0}3\sqrt{\xi\log\frac{|\mathcal{I}_{c}|}{\xi}}}\right)N\lambda_{*}-N(\epsilon^{(q)}_{A}+\epsilon^{(q)}_{B}+\epsilon^{(q)}_{C}+{\color[rgb]{0,0,0}(1+\lambda^{*})}\epsilon^{(q)}_{D})$

for all $\ell\in\\{1,\ldots,d_{\text{max}}+1\\}$. Observe that
$\mu_{-}(\ell)\leq w_{\text{max}}N$ for all
$\ell\in\\{1,\ldots,d_{\text{max}}+1\\}$ almost surely. The conditional
Chernoff inequality shows us that with probability $\geq 1-8\delta$, we have

$\sum^{N}_{n=1}\hat{W}_{i}(t(n;\ell))L(t(n;\ell))\geq\mu_{-}(\ell)-w_{\text{max}}\sqrt{2N\log\frac{d_{\text{max}}+1}{\delta}}$
(62)

for all $\ell\in\\{1,\ldots,d_{\text{max}}+1\\}$. Summing (62) over $\ell$
gives

$\displaystyle\sum^{\tau^{(q)}}_{t=\bar{\tau}^{(q-1)}+1}\hat{W}_{i}(t)L(t)$
$\displaystyle\geq$
$\displaystyle\left(1-{\color[rgb]{0,0,0}3\sqrt{\xi\log\frac{|\mathcal{I}_{c}|}{\xi}}}\right)(\tau^{(q)}-\bar{\tau}^{(q-1)})\lambda_{*}-(\tau^{(q)}-\bar{\tau}^{(q-1)})(\epsilon^{(q)}_{A}+\epsilon^{(q)}_{B}+\epsilon^{(q)}_{C}+{\color[rgb]{0,0,0}(1+\lambda^{*})}\epsilon^{(q)}_{D})$
$\displaystyle\qquad-
w_{\text{max}}(d_{\text{max}}+1)\sqrt{2N\log\frac{d_{\text{max}}+1}{\delta}}\qquad\qquad\text{with
probability {\color[rgb]{0,0,0}$\geq 1-8\delta$}}$ $\displaystyle\geq$
$\displaystyle\left(1-{\color[rgb]{0,0,0}3\sqrt{\xi\log\frac{|\mathcal{I}_{c}|}{\xi}}}\right)(\tau^{(q)}-\tau^{(q-1)})\lambda_{*}-(\tau^{(q)}-\tau^{(q-1)})(\epsilon^{(q)}_{A}+\epsilon^{(q)}_{B}+\epsilon^{(q)}_{C}+{\color[rgb]{0,0,0}(1+\lambda^{*})}\epsilon^{(q)}_{D})$
$\displaystyle\qquad-
w_{\text{max}}(d_{\text{max}}+1)\sqrt{4\frac{\tau^{(q)}-\tau^{(q-1)}}{d_{\text{max}}+1}\log\frac{d_{\text{max}}+1}{\delta}}-2w_{\text{max}}d_{\text{max}}\qquad\qquad\text{a.s.}$
$\displaystyle=$
$\displaystyle\left(1-{\color[rgb]{0,0,0}3\sqrt{\xi\log\frac{|\mathcal{I}_{c}|}{\xi}}}\right)(\tau^{(q)}-\tau^{(q-1)})\lambda_{*}-\tilde{O}(\sqrt{\tau^{(q)}-\tau^{(q-1)}})\qquad\text{a.s.}.$
(63)

Step (63) is by the fact that
$\epsilon^{(q)}_{A}+\epsilon^{(q)}_{B}+\epsilon^{(q)}_{C}+{\color[rgb]{0,0,0}(1+\lambda^{*})}\epsilon^{(q)}_{D}=\tilde{O}(1/\sqrt{\tau^{(q)}-\tau^{(q-1)}})$.
Altogether, the Lemma is proved. $\square$

###  8.7 A Generalization of Lemma 4.8 and Proof

We demonstrate a generalized version of Lemma 4.8 that provides high
probability upper and lower bounds to a sum of conditionally independent
random variables in the following.

######  Lemma 8.1 (Multiplicative Chernoff inequality with both sides)

Suppose random variables $\\{X_{t}\\}^{N}_{t=1}$ satisfy the following
properties:

  1. 1.

$X_{1},\ldots,X_{N}$ are jointly independent conditional on a $\sigma$-algebra
${\cal F}$,

  2. 2.

$\Pr(X_{t}\in[0,B]\text{ for all $t\in\\{1,\ldots,N\\}$})=1$ for some
$B\in\mathbb{R}_{>0}$.

  3. 3.

There exists real numbers $\delta_{-},\delta_{+}\in[0,1]$ and
$\mu_{-},\mu_{+}\in\mathbb{R}_{>0}$ such that

$\Pr\left(\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]>\mu_{+}\right)\leq\delta_{+},\qquad\Pr\left(\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]<\mu_{-}\right)\leq\delta_{-}.$ (64)

Then the following concentration inequalities hold for any fixed but arbitrary
$\delta\in(0,1)$:

$\displaystyle\Pr\left(\sum^{N}_{t=1}X_{t}>\mu_{+}+2\sqrt{B\mu_{+}\log\frac{1}{\delta}}+2B\log\frac{1}{\delta}\right)$
$\displaystyle\leq\delta+\delta_{+},$ (65)
$\displaystyle\Pr\left(\sum^{N}_{t=1}X_{t}<\mu_{-}-\sqrt{2B\mu_{-}\log\frac{1}{\delta}}\right)$
$\displaystyle\leq\delta+\delta_{-}.$ (66)

###### Proof 8.2

Proof of Lemma 8.1 We first proof the inequality (65). To ease the discussion,
we denote

$\epsilon_{+}=2\sqrt{\frac{B}{\mu_{+}}\log\frac{1}{\delta}}+\frac{2B}{\mu_{+}}\log\frac{1}{\delta}.$
(67)

To begin, we have

$\displaystyle\Pr\left(\sum^{N}_{t=1}X_{t}>(1+\epsilon_{+})\mu_{+}\right)$
$\displaystyle\leq$
$\displaystyle\Pr\left(\sum^{N}_{t=1}X_{t}>(1+\epsilon_{+})\mu_{+}\text{, and
}\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]\leq\mu_{+}\right)+\delta_{+},$ (68)

where step (68) is by the assumption 3 in the statement of the Lemma. Next,

$\displaystyle\Pr\left(\sum^{N}_{t=1}X_{t}>(1+\epsilon_{+})\mu_{+}\text{, and
}\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal F}\right]\leq\mu_{+}\right)$
$\displaystyle=$
$\displaystyle\Pr\left((1+\epsilon_{+})^{\sum^{N}_{t=1}\frac{X_{t}}{B}}>(1+\epsilon_{+})^{\frac{(1+\epsilon_{+})\mu_{+}}{B}}\text{,
and }\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal F}\right]\leq\mu_{+}\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{(1+\epsilon_{+})^{\frac{(1+\epsilon_{+})\mu_{+}}{B}}}\cdot\mathbb{E}\left[(1+\epsilon_{+})^{\sum^{N}_{t=1}\frac{X_{t}}{B}}\cdot\mathbf{1}\left(\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]\leq\mu_{+}\right)\right]$ (69) $\displaystyle\leq$
$\displaystyle\frac{1}{(1+\epsilon_{+})^{\frac{(1+\epsilon_{+})\mu_{+}}{B}}}\cdot\mathbb{E}\left[\prod^{N}_{t=1}\left(1+\epsilon_{+}\frac{X_{t}}{B}\right)\cdot\mathbf{1}\left(\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]\leq\mu_{+}\right)\right].$ (70)

Step (69) is by the Markov inequality. More precisely, it is by taking
expectation over the inequality

$\displaystyle(1+\epsilon_{+})^{\frac{(1+\epsilon_{+})\mu_{+}}{B}}\cdot\mathbf{1}\left((1+\epsilon_{+})^{\sum^{N}_{t=1}\frac{X_{t}}{B}}>(1+\epsilon_{+})^{\frac{(1+\epsilon_{+})\mu_{+}}{B}}\text{,
and }\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal F}\right]\leq\mu_{+}\right)$
$\displaystyle\leq$
$\displaystyle(1+\epsilon_{+})^{\sum^{N}_{t=1}\frac{X_{t}}{B}}\cdot\mathbf{1}\left(\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]\leq\mu_{+}\right),$

which holds with certainty. Step (70) is by the fact that
$(1+\epsilon)^{a}\leq(1+\epsilon\cdot a)$ for any $\epsilon>0$ and
$a\in(0,1)$, and the fact that $X_{t}/B\in(0,1)$ almost surely (by Assumption
2).

To continue with (70), we have

$\displaystyle\mathbb{E}\left[\prod^{N}_{t=1}\left(1+\epsilon_{+}\frac{X_{t}}{B}\right)\cdot\mathbf{1}\left(\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]\leq\mu_{+}\right)\right]$
$\displaystyle\mathbb{E}\left[\mathbb{E}\left[\prod^{N}_{t=1}\left(1+\epsilon_{+}\frac{X_{t}}{B}\right)\cdot\mathbf{1}\left(\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]\leq\mu_{+}\right)\mid{\cal F}\right]\right]$
$\displaystyle=\mathbb{E}\left[\mathbf{1}\left(\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]\leq\mu_{+}\right)\cdot\prod^{N}_{t=1}\left(1+\mathbb{E}\left[\epsilon_{+}\frac{X_{t}}{B}\mid{\cal
F}\right]\right)\right]$ (71)
$\displaystyle\leq\mathbb{E}\left[\mathbf{1}\left(\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]\leq\mu_{+}\right)\cdot\exp\left(\epsilon_{+}\sum^{N}_{t=1}\mathbb{E}\left[\frac{X_{t}}{B}\mid{\cal
F}\right]\right)\right]$ (72)
$\displaystyle\leq\exp\left(\frac{\epsilon_{+}\mu_{+}}{B}\right).$ (73)

Step (71) is by the independence of $X_{1},\ldots,X_{N}$ conditioned on ${\cal
F}$ in Assumption 1, as well as the fact that the indicator random variable
$\mathbf{1}\left(\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]\leq\mu_{+}\right)$ is ${\cal F}$-measurable. Step (72) is by the
fact that $1+\epsilon\leq e^{\epsilon}$ for all $\epsilon\in\mathbb{R}$.

After that, applying the bound (73) to (70) gives

$\displaystyle\Pr\left(\sum^{N}_{t=1}X_{t}>(1+\epsilon_{+})\mu_{+}\text{, and
}\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]\leq\mu_{+}\right)\leq\left(\frac{e^{\epsilon_{+}}}{(1+\epsilon_{+})^{1+\epsilon_{+}}}\right)^{\frac{\mu_{+}}{B}}$
$\displaystyle\leq\exp\left(-\frac{\epsilon_{+}^{2}}{2+\epsilon_{+}}\cdot\frac{\mu_{+}}{B}\right),$
(74)

where step (74) follows from the following technical calculations:

$\displaystyle\log\left(\left(\frac{e^{\epsilon_{+}}}{(1+\epsilon_{+})^{(1+\epsilon_{+})}}\right)^{\frac{\mu_{+}}{B}}\right)$
$\displaystyle=\frac{\mu_{+}}{B}[\epsilon_{+}-(1+\epsilon_{+})\log(1+\epsilon_{+})]$
$\displaystyle\leq\frac{\mu_{+}}{B}\left[\epsilon_{+}-(1+\epsilon_{+})\frac{\epsilon_{+}}{1+(\epsilon_{+}/2)}\right]\leq-\frac{\epsilon_{+}^{2}}{2+\epsilon_{+}}\cdot\frac{\mu_{+}}{B}.$

To complete the proof of inequality (65), it remains to show that
$\exp\left(-\frac{\epsilon_{+}^{2}}{2+\epsilon_{+}}\cdot\frac{\mu_{+}}{B}\right)\leq\delta_{+}$,
or equivalently
$\frac{\epsilon_{+}^{2}}{2+\epsilon_{+}}\cdot\frac{\mu_{+}}{B}\geq\log\frac{1}{\delta_{+}}.$
The inequality is evident from the definition of $\epsilon_{+}$. In the case
of $\epsilon_{+}\leq 2$, we have

$\frac{\epsilon_{+}^{2}}{2+\epsilon_{+}}\cdot\frac{\mu_{+}}{B}\geq\frac{\epsilon_{+}^{2}}{4}\cdot\frac{\mu_{+}}{B}\geq\frac{1}{4}\left[\frac{1}{\mu_{+}}\left(2\sqrt{B\mu_{+}\log\frac{1}{\delta}}\right)\right]^{2}\cdot\frac{\mu_{+}}{B}=\log\frac{1}{\delta_{+}}.$

In the case of $\epsilon_{+}>2$, we have

$\frac{\epsilon_{+}^{2}}{2+\epsilon_{+}}\cdot\frac{\mu_{+}}{B}\geq\frac{\epsilon_{+}^{2}}{2\epsilon_{+}}\cdot\frac{\mu_{+}}{B}\geq\frac{1}{2}\cdot\frac{2B}{\mu_{+}}\log\frac{1}{\delta_{+}}\cdot\frac{\mu_{+}}{B}=\log\frac{1}{\delta_{+}},$

and altogether (65) is proved.

The proof of (66) is analogous to the previous proof of (65), but we include
the former for completeness sake. To ease the discussion, we denote

$\epsilon_{-}=\sqrt{\frac{2B}{\mu_{-}}\log\frac{1}{\delta_{-}}}.$ (75)

If $\epsilon_{-}\geq 1$, then (66) is clearly true since then
$\mu_{-}-\sqrt{2B\mu_{-}\log\frac{1}{\delta}}\leq 0$. Thus, wlog we assume
$\epsilon_{-}\in(0,1)$ in the following calculations. To begin, we have

$\displaystyle\Pr\left(\sum^{N}_{t=1}X_{t}<(1-\epsilon_{-})\mu_{-}\right)$
$\displaystyle\leq$
$\displaystyle\Pr\left(\sum^{N}_{t=1}X_{t}<(1-\epsilon_{-})\mu_{-}\text{, and
}\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]\geq\mu_{-}\right)+\delta_{-},$ (76)

where step (76) is by the assumption 3 in the statement of the Lemma. Next,

$\displaystyle\Pr\left(\sum^{N}_{t=1}X_{t}<(1-\epsilon_{-})\mu_{-}\text{, and
}\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal F}\right]\geq\mu_{-}\right)$
$\displaystyle=$
$\displaystyle\Pr\left((1-\epsilon_{-})^{\sum^{N}_{t=1}\frac{X_{t}}{B}}>(1-\epsilon_{-})^{\frac{(1-\epsilon_{-})\mu_{-}}{B}}\text{,
and }\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal F}\right]\geq\mu_{-}\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{(1-\epsilon_{-})^{\frac{(1-\epsilon_{-})\mu_{-}}{B}}}\cdot\mathbb{E}\left[(1-\epsilon_{-})^{\sum^{N}_{t=1}\frac{X_{t}}{B}}\cdot\mathbf{1}\left(\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]\geq\mu_{-}\right)\right]$ (77) $\displaystyle\leq$
$\displaystyle\frac{1}{(1-\epsilon_{-})^{\frac{(1-\epsilon_{-})\mu_{-}}{B}}}\cdot\mathbb{E}\left[\prod^{N}_{t=1}\left(1-\epsilon_{-}\frac{X_{t}}{B}\right)\cdot\mathbf{1}\left(\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]\geq\mu_{-}\right)\right].$ (78)

Step (77) is by the Markov inequality, similar to that in (69). Step (78) is
by the fact that $(1-\epsilon)^{a}\leq(1-\epsilon\cdot a)$ for any
$\epsilon,a\in(0,1)$, and the fact that $X_{t}/B\in(0,1)$ almost surely (by
Assumption 2).

To continue with (78), we have

$\displaystyle\mathbb{E}\left[\prod^{N}_{t=1}\left(1-\epsilon_{-}\frac{X_{t}}{B}\right)\cdot\mathbf{1}\left(\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]\geq\mu_{-}\right)\right]$
$\displaystyle\mathbb{E}\left[\mathbb{E}\left[\prod^{N}_{t=1}\left(1-\epsilon_{-}\frac{X_{t}}{B}\right)\cdot\mathbf{1}\left(\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]\geq\mu_{-}\right)\mid{\cal F}\right]\right]$
$\displaystyle=\mathbb{E}\left[\mathbf{1}\left(\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]\geq\mu_{-}\right)\cdot\prod^{N}_{t=1}\left(1-\mathbb{E}\left[\epsilon_{-}\frac{X_{t}}{B}\mid{\cal
F}\right]\right)\right]$ (79)
$\displaystyle\leq\mathbb{E}\left[\mathbf{1}\left(\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]\leq\mu_{-}\right)\cdot\exp\left(-\epsilon_{-}\sum^{N}_{t=1}\mathbb{E}\left[\frac{X_{t}}{B}\mid{\cal
F}\right]\right)\right]$ (80)
$\displaystyle\leq\exp\left(\frac{-\epsilon_{-}\mu_{+}}{B}\right).$ (81)

Step (79) is by the independence of $X_{1},\ldots,X_{N}$ conditioned on ${\cal
F}$ in Assumption 1, as well as the fact that the indicator random variable
$\mathbf{1}\left(\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]\geq\mu_{-}\right)$ is ${\cal F}$-measurable. Step (80) is by the
fact that $1-\epsilon\leq e^{-\epsilon}$ for all $\epsilon\in\mathbb{R}$.

After that, applying the bound (81) to (78) gives

$\displaystyle\Pr\left(\sum^{N}_{t=1}X_{t}<(1-\epsilon_{-})\mu_{-}\text{, and
}\mathbb{E}\left[\sum^{N}_{t=1}X_{t}\mid{\cal
F}\right]\geq\mu_{-}\right)\leq\left(\frac{e^{-\epsilon_{-}}}{(1-\epsilon_{-})^{1-\epsilon_{-}}}\right)^{\frac{\mu_{-}}{B}}$
$\displaystyle\leq\exp\left(-\frac{\epsilon_{-}^{2}}{2}\cdot\frac{\mu_{-}}{B}\right),$
(82)

where step (82) follows from the following technical calculations:

$\displaystyle\log\left(\left(\frac{e^{-\epsilon_{-}}}{(1-\epsilon_{-})^{(1-\epsilon_{-})}}\right)^{\frac{\mu_{-}}{B}}\right)$
$\displaystyle=\frac{\mu_{-}}{B}[-\epsilon_{-}-(1-\epsilon_{-})\log(1-\epsilon_{-})]$
$\displaystyle\leq\frac{\mu_{-}}{B}\left[-\epsilon_{-}+\left(\epsilon_{-}-\frac{\epsilon_{-}^{2}}{2}\right)\right]=-\frac{\epsilon_{-}^{2}}{2}\cdot\frac{\mu_{-}}{B}.$

To complete the proof of inequality (66), it remains to observe that
$\exp\left(-\frac{\epsilon_{-}^{2}}{2}\cdot\frac{\mu_{+}}{B}\right)\leq\delta_{-}$,
which in fact holds with equality by the definition of $\epsilon_{-}$.
Altogether (66) is proved. $\square$

###  8.8 Table of notation

Notation | Usage
---|---
$w_{ijk}$ | mean reward under $i\in\mathcal{I}_{r}$, $j\in\mathcal{J}$ and $k\in\mathcal{K}$; $w_{\max}=\max_{i,j,k}\\{w_{ijk}\\}$
$v_{ijk}$ | mean resource volume $\mathbb{E}[A_{ijk}D_{ijk}]$ under $i\in\mathcal{I}_{c}$, $j\in\mathcal{J}$, $k\in\mathcal{K}$; $v_{\max}=\max_{i,j,k}\\{v_{ijk}\\}$
$\bar{\epsilon}^{(q)}_{D}$ | Error parameter describing loss caused by model uncertainty, used to slim the customer flow
$\eta$ | Discount parameter describing loss caused by parameter stochasticity, used to slim the customer flow
$\hat{\lambda}^{(q)}_{*}$ | Estimate to benchmark $\lambda_{*}$ based on observations in time steps $(\tau^{(q-1)}/2)+1,\ldots,\tau^{(q-1)}$
$\Theta^{(q)}$ | Weight vector set generated by iMWU over observations in time steps $1,\ldots,\tau^{(q-1)}/2$
$\eta(s)$ | Leaning rate of iMWU at time $s$
$\epsilon^{(q)}_{C}$ | Error parameter describing loss caused by model uncertainty, $\hat{\lambda}^{(q)}_{*}-\epsilon^{(q)}_{C}$ used as a lower bound for $\lambda_{*}$
$\phi^{(q)}_{i}(s)$ | Weight vector regarding reward $i\in\mathcal{I}_{r}$, generated by iMWU in phase $q$ time step $s$
$\psi^{(q)}_{i}(s)$ | Weight vector regarding resource and usage duration $i\in\mathcal{I}_{c}$, generated by iMWU in phase $q$ time step $s$
$\Gamma^{(q)}_{i}(s)$ | Exponent parameter regarding reward $i\in\mathcal{I}_{r}$, used to update $\phi^{(q)}_{i}(s)$
$\Xi^{(q)}_{i}(s)$ | Exponent parameter regarding resource $i\in\mathcal{I}_{c}$, used to update $\psi^{(q)}_{i}(s)$