Algorithm classifying roots of star-shaped Kac-Moody rootsystems
Toshio Oshima
Abstract. There is a correspondence between the roots of a star-shaped KacMoody root system and the spectral types of irreducible Fuchsian ordinary
diﬀerential equations. The norm of the root corresponds to the index of rigidityof the equation and the action of the Weyl group corresponds to the middle
convolution of the equations. The Weyl group has ﬁnite orbits on the setof roots with a ﬁxed non-zero norm. The purpose of this paper is to give analgorithm realized in a computer algebra which eﬀectively gives representativesof the orbits. The representatives can be applied to the classiﬁcation andconstruction of higher dimensional Painlevé type equations.

1. Introduction
We ﬁrst review a star-shaped Kac-Moody root system. Let(1.1)

I := {0, (j, ν) ; j = 0, 1, . . . , ν = 1, 2, . . .}be a set of indices and let h be an inﬁnite dimensional real vector space with theset of basis Π, where(1.2)

Π = {αi ; i ∈ I} = {α0 , αj,ν ; j = 0, 1, 2, . . . , ν = 1, 2, . . .}.

Put
(1.3)
(1.4)

I ′ := I \ {0},Π′ := Π \ {α0 },X
XQ :=Zα ⊃ Q+ :=Z≥0 α, Q− := −Q+ .
α∈Π

α∈Π

Then α ∈ Q has an expression(1.5)

α = nα0 +p−1 nXj −1
Xnj,ν αj,ν

j=0 ν=1

with n, nj,ν ∈ Z, p ∈ Z≥0 , nj ∈ Z>0 , and α ∈ Q+ if and only if n, nj,ν ∈ Z≥0 .
Moreover α ∈ Q is indivisible means that k1 α 6∈ Q for k = 2, 3, . . ..
We deﬁne an indeﬁnite symmetric bilinear form on h by(α|α) = 2
(1.6)

(α ∈ Π),(α0 |αj,ν ) = −δν,1 ,(0(i 6= j or |µ − ν| > 1),(αi,µ |αj,ν ) =−1 (i = j and |µ − ν| = 1).

α0

α0,1

α0,2

α1,1

α1,2

α2,1

α2,2

α3,1

α3,2

···
···
···
···

We will consider a Dynkin diagram which is a graph with some elements of Π asvertices and two vertices corresponding to α, β ∈ Π are connected by a line if
1

2

TOSHIO OSHIMA(α|β) = −1. An element of Π is called a simple root of a Kac-Moody root systemand the Weyl group W of this Kac-Moody root system is generated by the simple
reﬂections
sα : h 3 x 7→ x − (x|α)α ∈ h(1.7)

with α ∈ Π. The group generated by linear transformations σi,j of h with
σi,ν (αi,ν ) = αj,ν , σi,j (αj,ν ) = αj,ν , σk,ν (αk,ν )(k 6= i, j), σi,j (α0 ) = α0

for 0 ≤ i < j is denoted by S∞ . Note that W and S∞ keep ( | ) invariant.
Remark 1.1 ([Kc]). The set ∆re of real roots equals the W -orbit of Π, which
also equals W α0 . Denoting
B := {γ ∈ Q+ ; supp β is connected and (γ, α) ≤ 0(1.8)(∀α ∈ Π)},the set of positive imaginary roots ∆im+ equals W B. HereX
(1.9)
supp γ := {α ∈ Π ; nα 6= 0} if γ =
nα α.
α∈Π

Then ∆ = (∆ ∩Q+ )t(∆ ∩Q− ) and W B ⊂ Q+ . The set ∆ of roots equals
im
im
im
= ∆im
∆re t ∆im by denoting ∆im+ t ∆− . The set of positive− = −∆+ and ∆reroots ∆+ equals ∆ ∩ Q+ = ∆+ t W B. A subset L ⊂ Π is called connected if thedecomposition L1 ∪ L2 = L with L1 6= ∅ and L2 6= ∅ always implies the existenceof vj ∈ Lj satisfying (v1 |v2 ) 6= 0. Note that α0 ∈ supp α for α ∈ ∆im .
For α, β ∈ B with α 6= β satisfy W α ∩ W β = ∅. Hence the set {α0 } t B t (−B)
gives the complete representatives of W -orbits in ∆.
There are 4 extended Dynkin diagrams D̃4 , Ẽ8 , Ẽ7 and Ẽ6 corresponding toconnected classical star-shaped Dynkin diagrams as follows. Here “classical” meansthat the corresponding Weyl group is a ﬁnite group.
re

re

re

1
1

3

2

1

4

2

6

5

4

3

2

1

33, 222, 111111
1
11, 11, 11, 11(1.10)

1
2

1

2

3

4

2
3

2

1

1

22, 1111, 1111

2

3

2

1

111, 111, 111

Here the circles correspond to simple roots and the numbers attached to simple
roots are the coeﬃcients n and nj,ν in the expression (1.5) of an element α ∈ Q+ .
Then the elements corresponding to the above 4 diagrams are in B with (α|α) = 0
and moreover it is known that any γ ∈ B with (γ|γ) = 0 is a positive integer
multiple of one of these 4 roots (cf. Remark 2.7 i)).
Remark 1.2. For an integer N , we put(1.11)

BN := {α ∈ B | (α|α) = N }.

Then BN 6= ∅ if and only if N ∈ −2Z≥0 . The elements of B0 are multiples of theabove 4 indivisible elements. Moreover it is proved by [O1, O2] that BN are ﬁnite
sets for N < 0 (cf. Remark 2.5).

ALGORITHM CLASSIFYING ROOTS OF STAR-SHAPED KAC-MOODY ROOT SYSTEMS 3

Lemma 1.3 ([O1, Lemma 7.2]). For the expression (1.5) of α ∈ ∆+ with{α0 } ⫋ supp α, we have
(1.12)n ≥ nj,1 ≥ nj,2 ≥ nj,3 ≥ · · ·(j = 0, 1, . . .),Xn≤nj,1 − max{nj,1 , nj,2 , . . .}.

Moreover α ∈ Q+ \ {0} is an element of B if and only if(1.13)(1.14)

2nj,ν ≤ nj,ν−1 + nj,ν+1(nj,0 := n, j = 0, 1, . . . , ν = 1, 2, . . .),2n ≤ n0,1 + n1,1 + n2,1 + · · · + np−1,1 .

Note that these two conditions correspond to (α|αj,ν ) ≤ 0 and (α|α0 ) ≤ 0.
In this note we give an eﬀective algorithm to calculate BN for a given N ,which is implemented in a computer program. The root is transformed into atuple of partitions of an integer, which has direct applications to several ﬁelds ofmathematics and mathematical physics. We also explain an algorithm to get ∆ + .
Under the expression (1.5) of α ∈ ∆+ , put(1.15)

mj,ν = nj,ν−1 − nj,ν(j = 1, . . . , p − 1, ν = 1, . . . , np ).

Then(1.16)

nj,k = mj,k+1 + · · · + mj,nj(1.17)

n = mj,1 + · · · + mj,nj(k = 1, . . . , nj −1, j = 0, . . . , p−1),(j = 0, . . . , p − 1)with mj,ν ∈ Z≥0 and we have a tuple of p partitions (1.17) of n. Moreover we have
(1.18)(α|α) = 2n −
2

p−1
X
j=0

n −
2

nj
X


2
mj,ν
.

ν=1

The action of W on Q can be translated to that of tuples of integers :(1.19)(1.20)

sj,ν : mj,ν−1 ↔ mj,ν(j = 0, 1, . . . , ν = 1, 2, . . .),

p−1


X
s0 : mj,1 7→ mj,1 + 2n −(n − mj,1 )(j = 0, 1, . . .).

j=0Here we note that, for a ﬁxed j, reﬂections sj,ν (ν = 1, 2, . . .) generate permutationsof indices of mj,i with allowing j = p or ν = nj and in particular p changes into
p + 1 by sp,1 . Thus we will identify a tuple of partitions with an element of Q.
A relation between a star shaped Kac-Moody root system and Deligne-Simpson
problem of Fuchsian ordinary diﬀerential equations is ﬁrst clariﬁed by [CB]. For
a Fuchsian diﬀerential equation M on the Riemann sphere with p singular points,
the spectral type of M is a tuple of p partitions of n deﬁned by the multiplicities
of characteristic exponents at the singular points. Here n is the rank of M. Thereexists an irreducible Fuchsian diﬀerential equation with a given spectral type if
and only if the tuple corresponds to a positive root α of the star-shaped KacMoody root system with the condition that α0 ∈ supp α and moreover (α|α) 6= 0or α is indivisible (cf. [CB, O2]). Then (α|α) determines the number of accessory
parameters of the equation. The equation is called rigid if it has no accessory
parameter and it means the spectral type corresponds to a positive real root. To
get this result, transformations of the equations called middle convolutions andadditions are essential which induce transformations of spectral types corresponding
to the action of elements of W on the Kac-Moody root space.
A tuple of partitions m corresponds to an element α ∈ B if and only if (2.1),(2.2) and (2.8) are satisﬁed. Note that nj,1 = n − mj,1 and therefore these three
conditions correspond to (1.17), (1.13) and (1.14), respectively.

4

TOSHIO OSHIMA

2. Fundamental tuples of partitions
Let m be a tuple of p partitions of a positive integer n, namely,m = (m0 , m1 , . . . , mp−1 ),(j = 0, . . . , p − 1),

mj = (mj,1 , . . . , mj,nj )(2.1)

n = mj,1 + · · · + mj,nj(mj,ν ∈ Z>0 ).

For simplicity, we may assume mj are monotone, namely,
mj,1 ≥ mj,2 ≥ · · · ≥ mj,nj(2.2)
and non-trivial, namely,(2.3)

nj > 1for j = 0, . . . , p − 1. We write as follows.
mj = mj,1 mj,2 · · · mp−1,np−1 ,mjν = mj,ν ,m = m0 ; m1 ; · · · ; mp−1,np−1= m0,1 m0,2 · · · m0,n0 ; m1,1 · · · m1,n1 ; · · · : mp−1,1 · · · mp−1,np−1 ,

(2.4)

k

z }| {
m = m···m.
kDefinition 2.1. For a tuple m of p partitions of n, we deﬁne
(2.5)
(2.6)

ord m := n = mj,1 + · · · + mj,nj ,codim m := n −2njXm2j,ν ,

ν=1

(2.7)

idx m := 2n −
2

p−1
X

codim mj=0

and we call idx m the index of rigidity of m. The tuple m is basic when
(2.8)

2n −

p−1
X
j=0

n−

nj
X


mj,ν ≤ 0

ν=1

and m is indivisible, namely, there exists no integer k with k > 1 which satisﬁes
mj,ν ∈ kZ (j = 0, . . . , p − 1, ν = 1, . . . , nj ). The tuple m is fundamental if m isbasic or m = km′ with k ∈ Z>0 and a basic tuple m′ satisfying idx m′ 6= 0.
Since codim mj are even integers, so is idx m. Hence the relation
(2.9)
p−1
X
j=0

nj
p−1X


X
(ord m − mj,1 ) − 2 · ord m ·ord m +(mj,1 − mj,ν )mj,ν = −idx m
j=0 ν=1

means p ≥ 3 and − idx m is a nonnegative even integer for any fundamental tuplem.
Remark 2.2. The number codim mj is the codimension of a conjugacy classesof diagonalizable matrices in the space of matrices of size n whose multiplicities of
eigenvalues are given by mj,1 , . . . , mj,nj (cf. [O1, §3] for general matrices).
To obtain fundamental tuples m with a give index of rigidity, the following
theorem is essential.

ALGORITHM CLASSIFYING ROOTS OF STAR-SHAPED KAC-MOODY ROOT SYSTEMS 5

Theorem 2.3. [O2, Proposition 7.13] If m is fundamental, then
(2.10)

ord m ≤ 3 · idx m + 6,

(2.11)p ≥ 3 ⇒ ord m ≤ |idx m| + 2,
p ≤ 21 |idx m| + 4.

(2.12)

Corollary 2.4. If m is fundamental and ord m > |idx m| + 2, then p = 3 and(2.13)

m0,1 + m1,1 + m2,1 = ord m.

Here we may assume m is ordered, namely,(2.14)

If ∃N ∈ Z>0 with mj,ν = mj+1,ν

(0 ≤ ν < N ) and mj,N 6= mj+1,N⇒ mj,ν > mj,ν+1

for j = 0, . . . , p − 2.
Remark 2.5. It follows from Theorem 2.3 that for a given integer N , there
exist only ﬁnite fundamental tuples with a ﬁxed index of rigidity and the above
corollary follows from (2.9).
Example 2.6. i) [O2, Example 7.14] For m ∈ Z>0 , we deﬁne fundamental
tuples(2.15)(m): m2 , m2 , m2 , m(m − 1)1

E6

(m)

: (2m)2 , m4 , m3 (m − 1)1

E8

D4
E7

(m)

: m3 , m3 , m2 (m − 1)1(m): (3m)2 , (2m)3 , m5 (m − 1)1

with orders 2m, 3m, 4m and 6m, respectively, and index of rigidity 2−2m. We note(m)(m)
that E8 , D4 and 11, 11, 11, · · · attain the equalities (2.10), (2.11) and (2.12),
respectively.
ii) [Ko, Corollary 6.3] There are 4 fundamental tuples m with idx m = 0 :(1)

D4 = 12 , 12 , 12 , 12

(1)

E6

= 13 , 13 , 13

(1)

E7

= 22 , 14 , 14

(1)

E8

= 32 , 23 , 16 .

iii) [O1, Proposition 8] There are 13 fundamental tuples m with idx m = −2:
12 , 12 , 12 , 12 , 12

21, 21, 13 , 13

22 , 22 , 22 , 212

31 , 22 , 22 , 14

212 , 14 , 14

32, 15 , 15

22 1, 22 1, 15

32 , 22 12 , 16

23 , 23 , 22 12

42 , 24 , 23 12

42 , 24 , 23 12

42 , 32 2, 18

62 , 43 , 25 12
Remark 2.7. i) Let m be a fundamental tuple with idx m = 0. Then (2.8)
m
m
ord m
and (2.9) show that mj,ν = ord
and ordnj
n0 + · · · + np−1 = (p − 1) · ord m. Then
it is not diﬃcult to conclude that (n0 , n2 , . . . , np−1 ) equals (2, 2, 2, 2) or (3, 3, 3) or(2, 2, 4) or (2, 3, 6) and ord m is the least common multiples of n0 , . . . , np−1 . The
tuple corresponds to the list in Example 2.6 ii).
ii) The fundamental tuples m with idx m = −4 or −6 are given in [O2, §13.1.2,§13.1.4]. But some fundamental tuples are missing. Namely, 32 2, 32 2, 24 should be
added in the case idx m = −4. Moreover 32 2, 32 2, 23 12 and 32 2, 32 12 , 24 should
be added in the case idx m = −6. The fundamental tuples m with idx m ≤ −4
are obtained by a program using the computer algebra Risa/Asir [O6] whosealgorithm will be explained in the next section.
iii) For an expression of a partition, the numbers larger than 9 sometimes
expressed by alphabets. For example, 10, 11, 12, . . . , 16, 17, . . . are expressed bya, b, c, . . . , f, g, . . ., respectively. 11 may be expressed by (11) and bb9 = (11)(11)9.

6

TOSHIO OSHIMA

3. An algorithm obtaining fundamental tuples with a ﬁxed index
We want to obtain all the fundamental tuples m with a given index of rigidity.
We assume (2.2) and (2.14). Owing to (2.10) and (2.12), there are ﬁnite tuples ofpartitions to be checked the conditions (2.7) and (2.8) which assure that they are
fundamental.
For example, consider the case idx m = −8. Then ord m ≤ 30 and p ≤ 8.
(8)
When ord m = 30, it follows from [O2] that m equals E8 . Suppose ord m = 29.
Then (2.12) assures p = 3. Since the number of divisions p(29) = 4569, we haveto check about 45693 /6 > 1010 cases of ordered triplets of partitions of 29. This isquite heavy. As a result, there is no tuple satisfying these condition. In this section
we will show and explain a computer program which gives the fundamental tuples
with a ﬁxed index of rigidity. It gives 116 fundamental tuples m with idx m = −8
within 0.05 second under Windows 11 with CPU i7-10700. In the same way, it takes
about 1 second (resp. 3 minutes) to get 884 (resp. 40617) fundamental tuples mwith idx m = −18 (resp. −50). Note that p(3 · 50 + 5) = 66493182097 ≒ 6.65 × 1010 .
We use a free computer algebra Risa/Asir [Risa] and a partition is expressedby a list of integers and a tuple is a list of lists of integers, namely, the tuple m isrepresented by a list of lists V :m = [m0,1 , . . . , m0,n0 ], [m1,1 , . . . , m0,n1 ], . . . , [mp,1 , . . . , mp,np ] ,(3.1)
V[j][ν − 1] = Vj,ν−1 = mj,ν (j = 0, 1, . . . , p − 1, ν = 1, 2, . . . , nj )under the notation in the previous section. We assume m is monotone and ordered.
In our program we also use symbols
D = ord m = n,
Idx = |idx|,
(3.2)

S :=

p
X

(ord m − mj,1 ) − 2 · ord m,

j=0

SS :=

nj
p X
X


(mj,1 − mj,ν )mj,ν .

j=0 ν=1

Then the the tuple m is fundamental if and only if(3.3)

S ≥ 0 and S + SS = Idx

together with the condition that m is indivisible when Idx = 0.
Now we explain the function spbasic( ) in a library os muldif.rr [O6].
spbasic(Idx,D|str=1,pt=[k,ℓ]):: Returns the list of fundamental tuples with rank D and index Idx.
If Idx equals 0, indivisible fundamental tuples are return.
If D equals 0, the list of all the fundamental tuples with index Idx are returned.
Here the fundamental tuples are given in the form of ordered tuples.
The option pt=[k,k] may be indicated by pt=k.
If the option pt=[k,ℓ] is indicated, then k ≤ #partitions (in a tuple) ≤ ℓ
If the option str=1 is indicated, tuples of partition are given by strings of
numbers as in Example 2.6. These two expressions of tuples of partition can betransformed to each other by s2sp( ) in os muldif.rr, which contains more than
460 functions.
A partition is expressed by a sequence of non-increasing positive integers. Putlarger partitions ﬁrst in the lexicographic order of sequences of numbers and put

ALGORITHM CLASSIFYING ROOTS OF STAR-SHAPED KAC-MOODY ROOT SYSTEMS 7

larger tuples of partitions ﬁrst in the lexicographic order. For example,
aa431 > a99 > a981 and 541,3331 > 532,433.
The function spbasic(Idx,D) checks whether each tuple of partitions satisﬁes(3.3) according to the above order and returns all the required tuples. Note that
Theorem 2.3 assures that there is no required tuple if D > 3 · |Idx| + 6 or Idx > 0
or Idx is odd and moreover that the number p of partitions of the tuple equals 3
if D > |Idx| + 2 and 3 ≤ p ≤ 12 |Idx| + 4 in general. Hence the number of tuples tobe checked is ﬁnite but it is quite large when |Idx| and D are large. For a practicaland eﬀective program to perform this, it is quite important to avoid unnecessary
checks as much as possible. Note that most fundamental tuples m in this region
satisfy | idx m| > |Idx|.
The code of spbasic( ) is divided into two parts:
1. Introduction
1.1, 1.2, 1.3. Check the arguments and the options of the function and return
the answer when it is clear, for example, in the case D ≥ 3 · |Idx| + 6.
1.4. Determine an upper limit L such that p ≤ L according to Theorem 2.3.
1.5, 1.6. Determine an upper limit T such that m0,1 ≤ T by using the condition
SS ≥ 0. Then mj,ν ≤ T. Set the ﬁrst tuple to be checked with m0,1 = T.
2. Loop of Main routine
2.1. If D > |Idx| + 2, check (2.13) and skip tuples without (2.13).
2.2. Examine the minimal integer IL such that S ≥ 0 with p = IL < L.
If IL does not exist, skip some unsuitable tuples and go to the top of the loop
2.3. If there exists K ≤ IL such that SS > |Idx| with p = K, skip some
unsuitable tuples and go to the top of Loop.
2.4. Examine the minimal p = J such that Ix := Idx − S − SS ≤ 0 withIL ≤ J < L.
2.5. If J is found and Ix = 0, a required tuple is obtained and the tuple issaved in R.
2.6. Skip some unsuitable tuples according to Ix and go to the top of Loop.
We show the code of spbasic( ) with explanations inserted.
def spbasic(Idx,D){
1. Initialization
Idx 7→ -Idx
Set options str (output by strings)
Handle the option pt=
Idx=-Idx;
if((Str=getopt(str))!=1) Str=0;
Tu0=Tu1=0;
if(type(Tu=getopt(pt))==4&&length(Tu)==2&&isint(car(Tu))){Tu0=Tu[0];Tu1=Tu[1];}else if(isint(Tu)) Tu0=Tu1=Tu;
if(Tu1<3) Tu1=0;
1.1. If D > 3 · Idx + 6, there is no solution. Hence we assume D ≤ 3 · Idx + 6.
if(!isint(Idx)||!isint(Idx/2)||Idx<0||!isint(D)||D<0||D==1||D>3*Idx+6) return [];1.2. D = 0 ⇒ Handle arbitrary order

8

TOSHIO OSHIMA

if(D==0){
for(R=[],D=3*Idx+6;D>=2;D--)
R=append(spbasic(-Idx,D|str=Str,pt=[Tu0,Tu1]),R);
return R;}
1.3. Return the answer when Idx = 0
if(!Idx){
R=0;
if(D==2&&Tu0<5&&Tu1>3) R="11,11,11,11";if(Tu0<4&&Tu1>2){
if(D==3) R="111,111,111";
if(D==4) R="22,1111,1111";
if(D==6) R="33,222,111111";}
if(!R) return [];return [(Str==1)?R:s2sp(R)];}
1.4. Set L an upper bound of the number of partitions of a tuple
D > Idx + 2⇒ # partitions of a tuple = 3 (L = 2)
D = 3 · Idx + 6 ⇒ Returns the answer
D=2⇒ p = Idx/2 + 4
Check the option pt=.
if(D>Idx+2){
L=3;
if(D==3*Idx+6){
R=[[D/2,D/2],[D/3,D/3,D/3],[D/6,D/6,D/6,D/6,D/6,D/6-1,1]];
return [(Str==1)?s2sp(R):R];}}else L=Idx/2+4;
if(L>Tu1) L=Tu1;
1.5. Find a positive number T satisfying V00 ≤ T (⇒ Vj,ν ≤ T).
Note that V00 < D and K · (V00 − K) ≤ Idx with K = D%V00
Here D%V00 is a minimal non-negative integer in D + V00 Z.
for(T=D-1;T>1;T--){
K=D%T;
if((T-K)*K<=Idx) break;}1.6. Deﬁne the initial V by the top tuple with V00 = T.
NP[m] : the top partition of the integer D by positive integers ≤ m.
NP[m]=[m, . . . , m, m′ ] with length(NP)= D and m ≥ m′ > 0.
FS: check (2.13) ?
V=newvect(L);NP=newvect(T+1);
for(I=1;I<=T;I++) NP[I]=nextpart(D|max=I);
for(I=0;I<L;I++) V[I]=NP[T];S1=NP[1];FS=(D>Idx+2 ||(L==3&&D>Idx))?1:0;
2. Loop of Main routine
Idx (index) , D (order), L (maximal number of partitions of a tuple) are given.
V (initial tuple) is also given. The required tuples ≤ V.

ALGORITHM CLASSIFYING ROOTS OF STAR-SHAPED KAC-MOODY ROOT SYSTEMS 9for(R=[];;){
2.1. Case D > Idx + 2 etc. : examine V00 , V10 , V20
Check the condition V00 + V10 + V20 = D
3V00 < D ⇒ no more required tuples(V00 ≥ V10 ≥ V20 )if(FS){
if(3*car(V[0])<D) break;2.1.1. V00 + V10 ≥ D ⇒ change V10 7→ D − V00 − 1 if possible
if(car(V[0])+car(V[1]) >= D && (T=D-car(V[0])-1) > 0)
V[1]=V[2]=NP[T];2.1.2. Want to have the equality S := D − V00 − V10 − V20 = 0
S=D-car(V[0])-car(V[1])-car(V[2]);2.1.3. V00 + 2 · V10 < D or (S 6= 0, V10 = 1) ⇒ change V0 , . . . ⇒ Top of Loopif(car(V[0])+2*car(V[1])<D || (car(V[1])==1 && S) ){if(car(V[0])==1) break;V[0]=V[1]=V[2]=nextpart(V[0]);continue;}else if(S<0) V[2]=NP[car(V[2])+S];
2.1.4. S > 0 or V20 ≤ S2 ⇒ change V[1] with V[2] ⇒ Top of Loopif(S>0||var(V[2])+S<1){
V[1]=V[2]=nextpart(V[1]);continue;
2.1.5. V20 can be changed so that V00 + V10 + V20 = D}else if(S<0) V[2]=NP[car(V[2])+S];}
2.2. Find minimal IL satisfying (D − V00 ) + · · · + (D − VIL0 ) − 2D ≥ 0 with IL < L.
for(S=-2*D,IL=0;IL<L;IL++){
S+=D-car(V[IL]);
if(S>=0) break;}2.2.1. S = (D − V00 ) + · · · + (D − VL−1,0 ) − 2D < 0⇒ Get minimal k so that Vk0 can be reduced to attain (2.8) ⇒ Top of Loopif(S<0){ /* reducible i.e. IL=L && S<0 */for(LL=L-1;LL>=0;LL--){
if((K=car(V[LL]))+S>0){
V[LL]=NP[K+S];
break;}else{
S+=K-1;
V[LL]=S1;}}
if(LL<0) break;for(I=LL;I<L;I++) V[I]=V[LL];
continue;}
2.3. We have S := (D − V00 ) + · · · + (D − Vk,0 ) − 2D ≥ 0 with IL ≤ k < L
Check the second term SS of LHS of (2.9) which should be ≤ Idx.

10

TOSHIO OSHIMA

for(SS=K=0;K<=IL;K++){
ST=car(V[K]);SS0=SS;
for(I=length(V[K])-1;I>0;I--) SS+=(ST-V[K][I])*V[K][I];if(SS>Idx) break;}2.3.1. SS > Idx for V[0], . . . , V[K] with K ≤ IL ⇒ change V[K] ⇒ Top of Loop
if(SS>Idx && car(V[K])!=1){
if((W=nextcod(V[K],SS-Idx))==[]){
for(T=car(V[K])-1;T>0;T--){
J=D%T;
if(SS0+J*(T-J)<=Idx) break;
W=NP[T];}
for(J=K;J<L;J++) V[J]=W;
continue;}
2.4. Check the tuples V[0], . . . , V[J] whether they attain Idx.
Ix: Idx − (LHS of (2.9) with p = J), which strictly decreases when J increases.
IxF: the value of Ix in the case J − 1
Get smallest J with Ix ≤ 0for(Ix=2*D^2+Idx,J=0;J<L;J++){
IxF=Ix;for(Ix-=D^2,TV=V[J];TV!=[];TV=cdr(TV)) Ix+=car(TV)^2;
if(Ix<=0) break;}
2.5. Ix = 0 ⇒ we have a required tuple ⇒ save it in R
if(!Ix&&J>=IL&&J>Tu0-2){
for(TR=[],K=J;K>=0;K--) TR=cons(V[K],TR);
R=cons((Str==1)?s2sp(TR):TR,R);}
2.6. Prepare the next search
2.6.1. Ix < 0 ⇒ check the case that V[J-1] should be changedif(Ix<0 && IxF-mincod(D,car(V[J]))<0) J--;
2.6.2. Cannot ﬁnd J ⇒ change V[L-1] in 2.6.3.
else if(J>=L) J=L-1;
2.6.3. Change V[J] to the next one
for(I=J;I>=0&&car(V[I])==1;I--);
if(I<0) break;V[I]=nextpart(V[I]);for(J=I+1;J<L;J++) V[J]=V[I];}return R;}
3. Functions used in spbasic()
3.1. Get the next partition
nextpart(V|max=N):: get the partition that comes after V in descending lexicographical order.
If V is the last partition, 0 is returned.

ALGORITHM CLASSIFYING ROOTS OF STAR-SHAPED KAC-MOODY ROOT SYSTEMS 11

If V is a positive integer, the top partition of the integer V is given. In thiscase, the option max=N means the top partition of V by integers ≤ N, which equals[N,. . .,N,M] with 0 < M ≤ N.
Note that any partition m of V in the position after nextpart(V|max=N )satisﬁes codim m > codim nextpart(V|max=N).
S=os_md.nextpart(5);[5]while((S = os_md.nextpart(S)) != 0) print(S);
[4,1]
[3,2]
[3,1,1][2,2,1][2,1,1,1][1,1,1,1,1]0
os_md.nextpart(5|max=3);[3,2]
def nextpart(V){if(isint(V)){
if(V<1) return [0];I=V;
if(!isint(K=getopt(max))|| K<1) K=I;
K++;V=[];}else{
if(car(V) <= 1)
return 0;for(I = 0, V = reverse(V); car(V) == 1; V=cdr(V))
I++;
I += (K = car(V));
V=cdr(V);}R = irem(I,--K);
R = (R==0)?[]:[R];for(J = idiv(I,K); J > 0; J--)
R = cons(K,R);
while(V!=[]){
R = cons(car(V), R);
V = cdr(V);}return R;}
3.2. Get the next partition with a required property
nextcod(V,D):: get the partition after V whose square sum of elements ≥ (that of V) + D.
If the required partition does not exists, [] is returned.
def nextcod(V,D){
if(D<=0){if(car(V)==1) return [];for(D=0,TV=V;TV!=[];TV=cdr(TV)) D+=car(TV)^2;

12

TOSHIO OSHIMA

V=nextpart(V);
for(TV=V;TV!=[];TV=cdr(TV)) D-=car(TV)^2;}
K=length(V)-1;
for(S=T=0;K>=0; K--){
T+=(W=V[K]);S+=W^2;
if(W>2&&T^2-mincod(T,W-1)>=S+D){
R=nextpart(T|max=W-1);
for(--K;K>=0;K--) R=cons(V[K],R);
return R;}}
return [];}3.3. Get the minimal codimension of certain conjugacy classes of matrices
minicod(D,T):: returns codim nextpart(D,T)
def mincod(D,T){
K=D%T;
return D^2-T*(D-K)-K^2;}
We examine the eﬀects of codes in spbasic( ) eliminating unnecessary checks
and the runtime of spbasic(Idx,0) is given under Windows 11 with CPU i7-10700.
Eﬀect of codes eliminating unnecessary checks
Code
1.5
2.1
2.31
2.31∗
2.61
check
SS > |Idx| S 6= 0 SS > |Idx| SS > |Idx| Ix < 0Index of rigidity
−16
−26
−12
−12
−26
# fundamental tuples
647 2889
291
291
2889
original runtime (sec)
0.58
4.92
0.16
0.16
4.92
runtime without Code26.31 24.47
323.5
1.20
24.67
Ix < 0 ⇔ S + SS > |Idx|
The term “runtime without Code” in the above column 2.31∗ means the runtime
with using nextpart( ) in place of nextcod( ) in 2.31.
Idx
all
3
4
5
Idx
all
3
4
5
Idx
all
3
4
5

Number of fundamental tuples of 3, 4, 5 partitions with given Idx
0
−2
−4
−6
−8
−10
−12
−14
−16
−18
4
13
37
69
112
198
291
415
647
884
3
9
25
46
72
127
182
249
395
522
1
3
9
17
29
50
76
115
172
243
0
1
2
4
8
15
24
36
55
83
−20
−22
−24
−26
−28
−30
−32
−34
−36
−38
1186
1682 2183 2889
3841 4831 6203
8012 9789 12290
680
963
1230 1577
2105 2570 3257
4187 5009 6144
345
478
625
861
1126 1430 1890
2411 2982 3832
111
164
229
310
416
570
716
940
1214 1546
−40
−42
−44
−46
−48
−50
−52
−54
−56
−58
15379 18683 22910 28096 33387 40617 48703 57481 68622 81728
7731
9153 11072 13493 15768 18878 22594 26040 30819 36495
4721
5785 7227 8763 10484 12953 15392 18259 22056 26041
1939
2491 3046 3805
4675 5700 6916
8521 10114 12203

ALGORITHM CLASSIFYING ROOTS OF STAR-SHAPED KAC-MOODY ROOT SYSTEMS 13

4. Related results
For a given α ∈ ∆, it is easy to get the orbit W α ⊂ ∆. Namely, the function
spgen( ) in os muldif.rr gives the ﬁnite set {γ ∈ W α | ord γ ≤ D} for D ∈ Z>0 .
Since the set is stable under the transformation by sj,ν ∈ W , it is better to give therepresentatives of the elements of the set as monotone tuples of partitions. For atuple of partitions m, deﬁne sm the unique monotone tuple obtained by successive
applications of sj,ν , and for an integer r ≥ p − 1 and (j0 , . . . , jr ) ∈ Zr+1
>0 , put
r


X
(4.1)
Tν0 ,ν1 ,...,νr : mj,νj 7→ mj,νj − 2n −(n − mj,νj )(j = 0, . . . , r).
j=0

We note that Tν0 ,ν1 ,...,νr is an involutive transformation of monotone tuples and(4.2)

ord Tν0 ,ν1 ,...,νr m − ord m =rX(ord m − mj,νj ) − 2 ord m.

j=0

Owing to (1.12), the right hand side of (4.2) is positive if r ≥ p. It is known thatfor a fundamental tuple m, any monotone element m′ ∈ W m has an expression(4.3)

m = m(0) , m′ = sm(N ) , m(k) = Tj (k) ,...,j (k) m(k−1) ,
0

ord m

(k)

> ord m(k−1)

rk

(k = 1, . . . , N ).

Let γ ∈ ∆+ with supp γ 3 α0 . Then we may assume the corresponding tuple m′of partitions is monotone and m′ is similarly obtained by (4.3) with putting m thetrivial tuple of partition 1 (or 1, 1, 1). Thus we have the following function.
spgen(n|eq=1,str=1,std=f ,pt=[k, ℓ],sp=m,basic=1):: Get tuples m of partitions corresponding to the elements ∆+ with supp α 3 α0 .
• If n ∈ Z>0 , rigid tuples m with ord m ≤ n are obtained and– eq=1: ord m = D– str=1: returns in string form
– pt=[k, ℓ] : the number of the partition is in [k, ℓ]. pt=k means k = ℓ– std=f: the multiplicities are arranged from larger ones at eachpartition and the partitions are arranged from smaller (resp. larger)
tuples if f = 1 (resp. f = −1).
• If n ∈ Z>0 , the fundamental tuples m with idx m = n are obtained.
Options str=1 and pt= are valid.
• The option sp=m returns tuples in W m obtained by the direction withhigher rank. If basic=1 is indicated, the direction is not speciﬁed. Options
st=1, std= and pt= are valid.
[0] os_md.spgen(4|eq=1,pt=4);[[[2,2],[2,2],[2,2],[3,1]],[[2,2],[3,1],[3,1],[2,1,1]]][1] ltov(os_md.spgen(4|eq=1,pt=4,str=1));[ 22,22,22,31 22,31,31,211 ][2] ltov(os_md.spgen(4|eq=1,pt=4,str=1,std=-1));[ 31,22,22,22 31,31,22,211 ][3] ltov(os_md.msort(os_md.spgen(4|eq=1,pt=4,str=1,std=-1),[-1,0]));[ 31,31,22,211 31,22,22,22 ][4] ltov(os_md.spgen(-2|pt=4,str=1));[ 21,21,111,111 22,22,22,211 31,22,22,1111 ][5] ltov(os_md.spgen(4|eq=1,sp="11,11,11,11",str=1,std=-1));[ 31,31,22,1111 31,22,22,211 31,31,211,211 31,31,31,31,22 ]Here the header os md. is required for a function in os muldif.rr.
[0] list of rigid tuples m with p = 4 and ord m = 4

14

TOSHIO OSHIMA[1] the same list as above in the string form[2] the same list as above in the string form with the inverse lexicographic order[3] the same list as above further arranged by tuples[4] list of fundamental tuples m with idx m = −2 and p = 4[5] list of tuples m with ord m = 4 in the orbit containing 11,11,11,11Let α ∈ ∆+ with supp α 63 α0 . Then α correspond to a classical root of typeA, namely, there exist j0 ∈ Z≥0 and non-negative integers ν0 < ν1 such that(0(j, ν) 6= (j0 , ν0 ), (j0 , ν1 ),(4.4)
mj,ν =
ϵ(−1) (j = j0 , ν = νϵ , ϵ = 0, 1).
This tuple m has a special meaning for reducibility of rigid Fuchsian diﬀerential
equations (cf. [O3, Type 3 in Deﬁnition 2.4]).
Fundamental tuples whose index of rigidity ≥ −10 are listed in [O4] and rigid
tuples of order at most 8 are listed in [O2, 13.2.3].
We can consider similar problem in the case of a general symmetrizable KacMoody root system which includes the star-shaped Kac-Moody root system. The
imaginary fundamental root α is characterized by (α|γ) ≤ 0 for γ ∈ Π, where Π isthe set of simple roots deﬁning the root system. It is proved by [HO] that for agiven integer N , there exist only ﬁnite fundamental roots α with a given index ofrigidity (α|α) = N under a simple equivalence relation and classiﬁed them whenN ≥ −2. Note that the imaginary fundamental root is called a basic root in [HO].
It is desirable to have a computer program to get the fundamental roots α with agiven index of rigidity. The ﬁniteness theorem in [HO, Theorem 2.2] shows that
there are ﬁnite cases to be checked as in the case in this paper.
The fundamental roots of the symmetrizable Kac-Moody root system corresponds to the spectral types of ordinary diﬀerential equations which allow unramiﬁed irregular singularities together with regular singularities. The number of accessory parameters of the equation equals 2 − (α|α). Thedeformation preserving themonodromy of solutions of the equation gives 2−(α|α) -dimensional Painlevé-type
equation. Hence the classiﬁcation of fundamental roots are closely related to theclassiﬁcation of higher dimensional Painlevé-type equations. The classiﬁcation of
fundamental roots α with (α|α) = −2 in [O1, O2, HO] induces the classiﬁcationof 4-dimensional Painlevé-type equations in [HKNS] and that with (α|α) = −4
induces 8 new 6-dimensional Painlevé-type equations constructed by [Su].
We show a function chksp( ) in os muldif.rr which analyzes a tuple of partitions of a positive integer. Here the tuple may not be monotone nor ordered. It
also analyzes generalized Riemann schemes but here we do not explain it (cf. [O6,os muldifeg.pdf]).
chkspt(m|opt=t):: Check a tuple m of partitions (spectral type)
Return : [pts, ord, idx, f uchs, rod, redsp, f spt]
−1 means the tuple is not correct
0 means that the tuple is not in ∆+pts : number p of partitions
ord : ord m
idx : idx mf uchs : Fuchs relation (no meaning if m is a tuple of partitions)rod : the diﬀerence of the value ord m under one-step reduction
(N )
(N )
redsp : the positions (j0 , . . . , jp−1 ) in (4.3) speciﬁed by one-step reduction
f spt : corresponding fundamental tuple

ALGORITHM CLASSIFYING ROOTS OF STAR-SHAPED KAC-MOODY ROOT SYSTEMS 15

In place of the tuple m, the corresponding element α ∈ Q+ in the Kac-Moody root
space may be indicated by(4.5) m = [n,[n0,1 ,. . .,n0,n0 −1 ],. . .,[np−1,1 ,. . ., np−1,np−1 −1 ]] (cf. (1.15)).
• opt="sp" : return spectral type• opt="basic" : return f spt (return 0 if m 6∈ ∆+ )• opt="construct" : return the construction from a fundamental tuple(return 0 if m 6∈ ∆+ (not realizable))• opt="strip" : delete the exponents 0 from the tuple• opt="sort" : return the tuple with sorted partitions• opt="root" : return the construction by Kac-Moody Weyl group
The returned list has 3 elements which are base spectral type, given
spectral type and the list of reﬂections. The reﬂection has 3 elements,
namely, the value of inner product, the branch and the position in the starshaped Dynkin diagram which speciﬁed the root in the Dynkin diagram.
• opt="idx" : return index of rigidity• opt="kac" : return the corresponding element in Q+ (cf. (4.5)).
[0] os_md.chkspt([[1,2,1],[2,2],[1,1,1,1]]);2 α1,1[3,4,2,0,1,[ 1 0 0 ],[[1],[1],[1]]]][1] os_md.chkspt("121,22,1111");
1
3
4
3
2
1
[3,4,2,0,1,[ 1 0 0 ],[[1],[1],[1]]]]
α0,2 α0,1 α0 α2,1 α2,2 α2,3[2] os_md.chkspt("121,22,1^4");[3,4,2,0,1,[ 1 0 0 ],[[1],[1],[1]]]][3] os_md.chkspt([[1,2,1],[2,2],[1,1,1,1]]|opt="kac");[4,[3,1],[2],[3,2,1]][4] os_md.chkspt([4,[3,1],[2],[3,2,1]]);[3,4,2,0,1,[ 1 0 0 ],[[1],[1],[1]]]][5] os_md.chkspt([4,[3,1],[2],[3,2,1]]|opt="sp");[[1,2,1],[2,2],[1,1,1,1]][6] os_md.chkspt([[1,2,1],[2,2],[1,1,1,1]]|opt="sort");[[2,1,1],[2,2],[1,1,1,1]][7] os_md.chkspt([[1,2,1],[2,2],[1,1,1,1]]|opt="basic");[[1],[1],[1]][8] os_md.chkspt([[1,2,1],[2,2],[1,1,1,1]]|opt="construct");[[[1],[1],[1]],[[1,1],[1,1],[1,1]],[[1,1,1],[2,1],[1,1,1]],[[2,1,1],[2,2],[1,1,1,1]]][9] os_md.chkspt([[0,1,2,1],[2,0,2,0],[1,1,1,1]]|opt="strip");[[2,1,1],[2,2],[1,1,1,1]][10] os_md.chkspt("21,21,21,21"|opt="root");[[[1],[1],[1],[1]],[[2,1],[2,1],[2,1],[2,1]],[[1,3,1],[1,2,1],[1,1,1],[1,0,1],[2,0,0]]][11] os_md.chkspt("21,21,21,111");[4,3,0,0,1,[ 0 0 0 0 ],[[1,1],[1,1],[1,1],[1,1]]][12] os_md.chkspt([[3,2],[2,2,1],[1,1,1,1]]);
illegal partitions-1[13] os_md.chkspt("31,31,31,22");
not realizable

16

TOSHIO OSHIMA

0[14] os_md.chkspt("43,322,1^7");[3,7,0,0,1,[ 0 0 0 ],[[3,3],[2,2,2],[1,1,1,1,1,1]]][15] os_md.chkspt("21,21,21,111");[4,3,0,0,1,[ 0 0 0 0 ],[[1,1],[1,1],[1,1],[1,1]]][16] os_md.chkspt([[2*m,2*m],[m,m,m,m],[m,m,m,m-1,1]]|opt="idx");-2*m+2[17] os_md.chkspt([[2*m,2*m],[m,m,m,m],[m,m,m,m-1,1]]);[3,4*m,-2*m+2,0,-1,[ 0 0 3 ],[[2*m,2*m],[m,m,m,m],[m-1,m,m,m,1]]]
Remark 4.1. For a tuple m of partitions, we get a fundamental tuple m′ withm ∈ W m′ as follows. We choose (j0 , . . . , jp−1 ) so that the right hand side of (4.2)
is negative. Then we have succesively get m(k) = T(j (k) ,...,j (k) ) m(k−1) as in (4.3)
′

0

p−1

with the condition m(k) < m(k−1) . Then three cases happen.
(1) The right hand side of (4.2) is non-negative for any (j0 , . . . , jp−1 ) withputting m = m(N ) . Then sm(N ) is a fundamental tuple.
(2) sm′ = kα0 with k ∈ Z>0 . Then m′ ∈ W kα0 .
(3) When we deﬁne m(N +1) according to (4.1), there appear a negative integer
and a positive integer. Then m does not correspond to an element of ∆+ .
We note that the sequence m(0) = m, m(1) , . . . , m(N ) corresponds to Katz’ reduction of Fuchsian diﬀerential equations with the spectral type m (cf. [Kz, CB, O2]).
Acknowledgements
In 2007–2008, a program okubo [O5] was written by the author using the computer language C. It has several functions handling the tuples of partitions related
to the spectral types of Fuchsian diﬀerential equations. It has a function which generates fundamental tuples with a given index. In 2019, H. Kawakami pointed out
a fundamental tuple of index −4 which is not generated by the function and thenthe author rewrote the function spbasic( ) using the computer algebra Risa/Asir(cf. Remark 2.7 ii)). In 2024, L. Yongchao showed the author a missing fundamental tuple of index −18 and pointed out a connection to a problem in mathematicalphysics (cf. [MOTZ]). It is the only one missing fundamental tuple when the index
of rigidity ≥ −24 and there exists another one in 2889 fundamental tuples of index−26. The author has rewritten spbasic( ) and writes this paper explaining thealgorithm used by spbasic( ). The author greatly thanks to H. Kawakami and
L. Yongchao for pointing out missing fundamental tuples caused by the original
programs.
References[CB]

Crawley-Boevey W., On matrices in prescribed conjugacy classes with no common invariant
subspaces, and sum zero, Duke Math. J. 118(2003), 339-352.
[HKNS] Hiroe, H. Kawakami, A. Nakamura and H. Sakai, 4-dimensional Painlevé-type equations,
MSJ Memoirs 37, Mathematical Society of Japan, 2018.
[HO] Hiroe K. and Oshima T., Classiﬁcation of roots of symmetric Kac-Moody root systems andits application, Symmetries, Integrable Systems and Representations, Springer Proceedingsin Mathematics and Statistics 40 (2012), 195–241.
[Kc]
Kac V. C., Inﬁnite dimensional Lie algebras, Third Edition, Cambridge Univ. Press 1990.
[Kz]
Katz, N. M., Rigid Local Systems, Annals of Mathematics Studies 139, Princeton University Press 1995.
[Ko] Kostov, V. P., The Deligne-Simpson problem for zero index of rigidity, Perspective inComplex Analysis, Diﬀerential Geometry and Mathematical Physics, World Scientiﬁc 2001,
1–35.
[MOTZ] Mekareeya1 N., Ohmori K., Tachikawa Y. and Zafrir G., E8 instantons on type-A ALE
spaces and supersymmetric ﬁeld theories, J. High Energ. Phys. 144 (2017).

ALGORITHM CLASSIFYING ROOTS OF STAR-SHAPED KAC-MOODY ROOT SYSTEMS 17[O1]

Oshima T., Classiﬁcation of Fuchsian systems and their connection problem, RIMS
Kôkyûroku Bessatsu B37 (2013), 163–192.
[O2] Oshima T., Fractional calculus of Weyl algebra and Fuchsian diﬀerential equations, MSJ
Memoirs 28, Mathematical Society of Japan, Tokyo, 2012.
[O3] Oshima T., Reducibility of hypergeometric equations, Analytic, Algebraic and Geometric
Aspects of Diﬀerential Equations, Trends in Mathematics, Springer, 429–453, 2017,[O4] Oshima T., List of fundamental spectral types with index of the rigidity ≥ −10, 2024,
https://www.ms.u-tokyo.ac.jp/~oshima/paper/spect10.pdf[O5] Oshima T., okubo, a computer program for Katz/Yokoya/Oshima algorithm, 2007–2008,
http://www.ms.u-tokyo.ac.jp/~oshima/[O6] Oshima T., os muldif.rr, a library of computer algebra Risa/Asir, 2008–2024,
http://www.ms.u-tokyo.ac.jp/~oshima/[Risa] Noro M., etc., Risa/Asir, Computer algebra,
http://www.math.kobe-u.ac.jp/Asir/asir.html[Su]Suzuki T., Six-dimensional Painlevé systems and their particular solutions in terms of rigid
systems, J. Math. Phyics 55 (2014), 57–69.
Center for Mathematics and Data Science, Josai University, 2-3-20 Hirakawacho,
Chiyodaku, Tokyo 102-0093, Japan
Email address: oshima@ms.u-tokyo.ac.jp