ManfredG¨obel TheOptimalLowerBoundforGeneratorsofInvariantRingswithoutFiniteSAGBIBaseswithRespecttoAnyAdmissibleOrder

(1)

The Optimal Lower Bound for Generators

of Invariant Rings without Finite SAGBI Bases with Respect to Any Admissible Order

Manfred G¨obel

DFD-AP, DLR Oberpfaffenhofen, 82234 Weßling, Germany [email protected]

received 23 April 1998, revised 23 November 1998, accepted 27 January 1999.

We prove the existence of an invariant ring generated by elements with a total degree of at most , which has no finite SAGBI basis with respect to any admissible order. Therefore, is the optimal lower bound for the total degree of generators of invariant rings with such a property.

Keywords: SAGBI basis, Invariant ring, Analysis of algorithms.

In [2], the structure of SAGBI (Subalgebra Analogue to Gr¨obner Basis for Ideals [5]) bases for invariant rings of permutation groups with respect to the lexicographical order with !"$#%#%#&!')(

was investigated. It turned out that only invariant rings of direct products of symmetric groups have a finite SAGBI basis, which is then, in addition, multilinear. Of course, it would be of interest to have such a strong characterization with respect to any other admissible order [4, 6]. To achieve this seems to be all but trivial. One step towards the understanding of the behavior of SAGBI bases for invariant rings with respect to any admissible order is the investigation of important special cases. Recently, the non-finiteness of SAGBI bases for^*,+ ^.- ^)/ ^- ^1032546 ^/7089 with respect to any admissible order was proven in [3]. In addition, it was shown that with respect to the number of variables,^*,+ ^:- ^)/ ^- ^)032546 ^/089 is the

“smallest” unique example for such a ring of polynomial invariants of a permutation group.

In this note, we show the existence of an invariant ring generated only by polynomial invariants with a total degree of at most^; , which has no finite SAGBI basis with respect to any admissible order. Hence,

; is the optimal lower bound, because any invariant ring generated by polynomial invariants with a total degree of at most^< has for trivial reasons a finite SAGBI basis. In addition, we can show that our example has with respect to this property the minimal number of variables⁼ , if we restrict ourself to polynomial invariants of permutation groups, and the minimal group order^; .

We briefly recall our notation, and then state and prove our result.

>

This work was supported by the German Science Foundation (DFG). The author would like to thank Prof. Cohen (Eindhoven) and the anonymous referees for their comments and remarks.

1365–8050 c

?

1999 Maison de l’Informatique et des Math´ematiques Discr`etes (MIMD), Paris, France

(2)

@ The natural and complex numbers are denoted by^A and^* ,

@CB

+ D- #%#%# - ( 2 is the commutative polynomial ring over^B in the indeterminates , . . . , ⁽ ,

@FE is the set of terms (= power-products of the^1G) in^B ⁺^H ^- ^#I#%# ^- ^)(J2,

@CK,LNMB

-7OQP denotes the general linear group over^B ,

@CK

K,LNMB

-ROQP a permutation group,

@ and^S ⁽ the symmetric group of^O symbols.

A polynomial^TVU ^B ⁺ ^- ^#I#%# ^- ^)(W2 is called^X -invariant, if

T'Y[Z MT

P]\

Y^T M (

_

G!`aab RG)G

-

#%#I#

- (

_

G!`aQb (Gc1G

Ped ZVY

Mb

Ggf

P

hiGkjf3hi( U'X$

K,LlMB

-ROQP

# (1)

The ring^B ⁺ ^.- ^#%#I# ^- ⁽ ^2nm denotes the^B -algebra of^X -invariant polynomials in^B ⁺ ^:- ^#%#I# ^- ⁽ ², and

o:pqrts

m MT P Y _

u:vWw7x

6ny 8Rz

x{v

mW|

} (2)

the^X -invariant orbit of^T . An admissible order on the set of terms^E is such that

s

~< d <Y s U E

and ^s ^N[ ^s ^/ ^d ^-^s ^- ^s ^/ ^U ^E with ^s^N ^s ^/ ⁺4^- 6^25# (3)

EM

T P is the leading term of^TU ^B ⁺ ^- ^#%#I# ^- ⁾⁽² with respect to a given admissible order , and ^M ^T ^P denotes its coefficient. A term^s ^Y ⁷

#%#%#7

( is called multilinear iff^D ^- ^#%#%# ^- :(^: - <J . Lemma 1 Let^K ^Y ^M ^<:; ^P ^Mc ⁼ ^PR. Then^*,+^H ^- ^/ ^- ⁰ ^-^1%2n is generated by

YQ 1/ - )/ - 10 - )0% - )/3)0.W# (4)

Proof A close look at the^K -invariant orbits of^*,+^H ^- ^/ ^- ⁰ ^- ^1%2 via the reduction technique described in [1] shows that we only have to find a representation of^o:pqrts

M /

0 P,^o:pqrts

M

/

0 P ,^o:pqrts

M /

1

P, and^o:pqrts

M

/

P in terms of the elements of . We have

o:p.qr5s

M /

10

P Y M

)/

P M 10

)/3

:P

M

)/

P M )0

:P-

o:p.qr5s

M /

0 P Y M

)0 :P

M 10 )/3 :P

M

)03 DP

M 1/ P-

o:p.qr5s

M /

:P Y M )/ P M ] )/3)0 P

M )/ P M

)0 :P- and

o:p.qr5s

M /

P Y M

)0 :P

M 10 )/3 :P

M

)03 DP

M 1/ P-

with

0 /

1Y

M

/ P M 0 1 P

M

/ 0 P #

For any other non-multilinear special^o:p.qr5s

M R

/

0 t

P not listed so far, we have ^- ^/ or

0 - D,¡ , i.e. we can rewrite these orbits as

M )/ P

o:pqrts M ¢

3¢

/

0

P (5)

(3)

or

M 0 1 P o:pqrts

M

/ %¢

0 3¢

P # (6)

This completes the proof of the lemma. ^£¤

Lemma 2 Let^K ^Y ^M ^<:; ^P ^Mc ⁼ ^PR. Then^*,+ ^.- ^#I#%# ^- ⁽ ² has no finite SAGBI basis with respect to ^! . Proof The permutation group^K is not a direct product of symmetric groups. So, following [2],

*,+ - / - 0 -132 can not have a finite SAGBI basis with respect to^! .^£¤

Theorem 3 Let^K ^Y¥ ^M ^<:; ^P ^M ⁼ ^PR. Then^*,+ ^- ^/ ^- ⁰ ^- ¹³² has no finite SAGBI basis with respect to any admissible order .

Proof Assume that ^*,+ ^- ^/ ^- ⁰ ^- ¹³² has a finite SAGBI basis with respect to , and assume further w.l.o.g. that^{H ¦} ^/ , ⁰ ^¦1 , and^§ ⁰ . Then we have either ^/ ^¦ ⁰ , or ⁰ ^¦ ^/ . And further, the basis contains the multilinear^K -invariant orbits

Q / - H / - 1 / 0 - 0 1 - 0 1J (7)

and a finite number of non-multilinear^K -invariant orbits of the form

¨

RjlY[

R

"

R

/

0 (8)

with^Y§ ^/© ^< . Note that the leading term of

¨

Y1 / 0 is with respect to not determined so far. Our goal is now to construct an infinite sequence of leading terms^sª ^-^s ^- ^s ^/ ^- ^#%#I# of^K -invariant orbits such that almost all of these terms are not generated by products of leading terms of the polynomials in . Let

sª

Y¬«

EMo:pqrts

M H

/

P7P-if ^EM^¨ ^P ^{Y^H1}

EMo:pqrts

M / / 0

P7P-otherwise,

and let ^ª ^Y1 , if ^sª ^Y® ^/ , ^ª ^Y¯ ^/ ⁰ , if^sª ^Y® ^/ 0^/ , ^ª ^Y® ^/ , if ^sª ^Y /^/ 0 , and ^ª ^Y

H1 otherwise. Furthermore, for ^r ^© ^< , define ^s^GY ^{E Mo:pqrts}

Mks

G¢ IDG¢ PRP, and let ^IGY¥DG^¢ , if

s

GaY

s G¢ IDG¢ , and let

G Y «

7

- if^s^G^¢ ^{Y^} ^R/

0

7

/

0 - otherwise.

For all^r ^U°A , we have^s ^G is ^R

"

or ^R/

0 with <F±¯.$¯ / , if ^EM^¨ ^P ^Y1 , and with

~D/ © < , otherwise (see Figure 1 on the following page for an example sequence). The total degree of^s ^G is always smaller than the total degree of^s^G for^r ^r^/HUCA , and ^G is never a leading term of a

K -invariant orbit for all^r ^U'A .

Our selection of the ^G,^r ^U'A ensures that the sequence of leading terms^s ^ª ^- ^s ^.- ^s^/ ^- ^#%#I# in^*,+ ^:- ^1/ ^- ⁾⁰ ^- ² has by construction the following properties: First,^s ^G is never a product of terms in

² G¢ Y~D .- )/ -

EM

¨

P3- )0 - )0% &³

sª - #%#%# - s G¢ d r

U'A# (9)

Each product of terms in^² ^G^¢ matching the exponent of (⁾⁰ ) is unable to match simultaneously the exponent of (^)/ ), if^s ^G ^Y

( /

0 ). Second, all other leading terms in^*,+ ^:- ^)/ ^- ⁾⁰ ^- ² have an expression as a product of terms in^² ^YI ^:- ^)/ ^- ^EM

¨

P- 10 -)03 &³

s ª - s

.- s / - #%#I#´W#

(4)

Altogether, this implies that any^s ^G with a sufficiently large total degree has no expression as a product of leading terms of the polynomials in the finite set

. Hence, there exists no finite SAGBI basis of

*,+ - / - 0 -132 with respect to (contradiction).^£¤

Figure 1 illustrates the way of the sequence^sª ,^s ,^s ^/ , . . . thru the terms in question with respect to a given admissible order . The upper (lower) half of the figure shows the first couple of ^R

( ⁷/

0 )

terms denoted by ^:## ^/ (^# ^/ ^#) with ^µ[¶ ^/ . We can see in this example that ^sª ^Y· ^/

( ^ª ^Y¶1 ), ^s ^FY¶ ^/ 0⁰ (^:FY¶ ^/ 0^/ ), ^s ^/ ^Y¶ /^/

¸

0 ( ^/ ^Y¶ ^/ ^/0 ), ^s ⁰ ^Y¶ ⁰

¹

( ⁰ ^Yº ^/

¸

),

s Y¦¸

/

( ^Y¦ ^/

¸

), and so on. The set^² ^Y»I ^D- ^)/ ^- ^J-⁾⁰ ^- ⁾⁰³ ^]³¼ ^s^ª ^- ^s^.- ^s ^/ ^- ^#I#%#´

... ... ... ... ... ... ... ... ... ...

... ... ...

1..4

1..8 1..9 1..10 1..11 1..12 1..13

2..3

7..10 2..4

2..5 2..6 2..7 2..8 2..9 2..10

2..13 2..14

...

7..13 7..14

...

.3 4.

.4 5.

.5 6.

.6 7.

.7 8.

.8 9.

.9 10.

.10 11.

.11 12.

.12 13.

.13 14.

.5 7.

.6 8.

.7 9.

.8 10.

.9 11.

.10 12.

.11 13.

.12 14.

... ...

3..5 4..6 3..6 3..7 3..8 3..9 3..10 3..11 3..12 3..13

...

4..7 4..8 4..9 4..10 4..11 4..12 4..13 4..14

...

5..8 5..9 5..10 5..11 5..12 5..13 5..14

...

6..9 6..10 6..11 6..12 6..13 6..14

...

8..12 8..13 8..14

... ^9..14... ...

.8 11.

.9 12.

.10 13.

...

.11 14.

...

9..13

.10 14.

...

3..4 4..5

5..7 6..7 6..8 7..8

7..9 8..10 8..11 9..11

9..12 10..11 10..12

10..14 11..12 11..13 11..14

12..13 12..14 13..14

...

.1 2.

.2 3.

.1 3.

.1 4. .2 4.

.1 5. .2 5. .3 5.

.1 6. .2 6. .3 6. .4 6.

.1 7.

.1 8.

.1 9.

.1 10.

.1 11.

.1 12.

.1 13.

.1 14. .2 14. .3 14. .4 14. .5 14. .6 14. .7 14. .8 14. .9 14.

.9 13.

.8 12.

.8 13.

.7 13.

.7 12.

.7 11.

.7 10.

.6 9.

.6 10.

.6 11.

.6 12.

.6 13.

.5 12.

.5 11.

.5 10.

.5 9.

.5 8.

.4 7.

.3 7.

.2 7.

.2 8. .3 8. .4 8.

.2 9.

.2 10.

.2 11.

.2 12.

.2 13.

.3 9. .4 9.

.3 10. .4 10.

.3 11.

.3 12. .4 12.

.4 11.

.3 13. .4 13. .5 13.

1..2

1..5 1..6 1..7

1..14 2..11 2..12

3..14

7..12 8..9

9..10

10..13 7..11

...

5..6 1..3

Fig. 1: The leading term pattern for a given admissible order^½ . separates the terms in the set^D

-

/

0¿¾

1À ¡:/ into leading terms (font: times-bold) and

other terms (font: times-roman) such that either

or /

0 is a leading term, and such that any other leading term in^*,+ ^:- ^)/ ^-⁾⁰ ^- ^2Á is a product of terms in^² .

The invariant ring^*,+ ^- ^#%#I# ^- ^1(W2nm is generated by polynomials with a total degree of at most^< implies that^X is the trivial group, and that the generators are, . . . , ¹⁽ . Hence,^; is the smallest possible and therefore optimal lower bound for the generators of an invariant ring without a finite SAGBI with respect to any admissible order. Furthermore, we must have¾X ¾ © ; for any^*,+ ^- ^#%#I# ^- ^)(W2nm with this property, i.e. our example is minimal with respect to the group order, because¾K ¾

Y^; .

(5)

Lemma 4 Let^O ^¡= , and let^*,+ ^- ^#%#%# ^-⁾⁽² be generated by elements with a total degree of at most^; .

Then^*,+^H ^- ^#I#%# ^- ^1(W2 has a finite SAGBI basis.

Proof ^K is either^SQ ,^{SQÃÂ SQ},^S ^/ ,^SQÂÄS ^/ ,^S ^/ ^ÂÄSQ, orSaÃÂÄSQÂÄSQ , i.e.^*,+^H ^- ^#I#%# ^- ^1(W2 has a finite SAGBI basis (Cf. [2]).^£¤

Hence,^*,+ ^- ^/ ^- ⁰ ^-¹³² with^K ^YÅ ^M ^<D; ^P ^M ⁼ ^PR is, in addition, minimal with respect to the number of variables, if we restrict ourself to polynomial invariants of permutation groups. Note that these results hold not only for the field^* but for any ring^Æ , because our arguments are based on^K -invariant orbits.

References

[1] M. G¨obel, Computing Bases for Permutation-Invariant Polynomials, Journal of Symbolic Computa- tion, 19, 285–291, 1995.

[2] M. G¨obel, A Constructive Description of SAGBI Bases for Polynomial Invariants of Permutation Groups. Journal of Symbolic Computation, 26, 261–272, 1998.

[3] M. G¨obel, The “Smallest” Ring of Polynomial Invariants of a Permutation Group which has No Finite SAGBI Bases w.r.t. Any Admissible Order, Theoretical Computer Science, to appear, 1998.

[4] L. Robbiano, Term Orderings on the Polynomial Ring, in: B. Caviness (ed.), European Conference on Computer Algebra, EUROCAL’85, Proceedings Vol. 2: Research Contributions, volume 204 of LNCS, Springer, Linz, Austria, 513–517, 1985.

[5] L. Robbiano and M. Sweedler, Subalgebra Bases, In: W. Bruns and A. Simis (eds.), Commutative Algebra, Lect. Notes Math. 1430, Springer, 61–87, 1990.

[6] V. Weispfenning, Admissible Orders and Linear Forms, ACM SIGSAM Bulletin, 21:2, 16–18, 1987.

(6)