Symmetric ideals, Specht polynomials and solutions to symmetric systems of equations

(1)

Contents lists available atScienceDirect

Journal of Symbolic Computation

www.elsevier.com/locate/jsc

Symmetric ideals, Specht polynomials and solutions to symmetric systems of equations

Philippe Moustrou, Cordian Riener, Hugues Verdure

DepartmentofMathematicsandStatistics,UiT- theArcticUniversityofNorway,9037Tromsø,Norway

a r t i c l e i n f o a b s t ra c t

Articlehistory:

Received16December2019

Receivedinrevisedform11February2021 Accepted12February2021

Availableonline18February2021

Keywords:

Symmetricgroup Spechtpolynomials Polynomialequations

Anidealofpolynomialsissymmetricifitisclosedunderpermu- tationsofvariables.Werelategeneralsymmetricidealstothe so calledSpechtidealsgeneratedbyallSpechtpolynomialsofagiven shape.Weshow aconnectionbetweentheleadingmonomials of polynomials in the ideal and the Specht polynomials contained inthe ideal.Thisprovidesapplications inseveral contexts. Most notably,thisconnection givesinformation about thesolutions of the corresponding set ofequations. From anotherperspective, it restrictstheisotypicdecompositionoftheidealviewedasarepre- sentationofthesymmetricgroup.

©²⁰²¹^TheÂuthor(s).^Published^byÊlsevier^Ltd.^Thisîsânôpen accessarticleundertheCCBYlicense (http://creativecommons.org/licenses/by/4.0/).

1. Introduction

LetSn denotethesymmetricgrouponn-elements,andletKbeaﬁeld.Then Snactsnaturallyon ann-dimensionalspaceKⁿ bypermuting coordinates.Thislinearactionthengivesrisetoan action on the corresponding polynomial ring by permuting coordinates. In thisarticle we consider ideals I

⊂

K

[

^X1

, . . .

Xn

]

^whichâre^stableûnder^thisâction.^The^studyôf^such îdealsâppears^quite^naturally indifferentcontexts(see forexampleSteidel(2013);FaugèreandSvartz(2012);Krone(2016);Busé andKarasoulou(2016)).

Ourinterestinsuchidealsstemsfromalgorithmicpurposes:thesymmetryonasetofequations often can be used to simplify its resolution. In this ﬂavour,a fundamental resultby Timofte (see Timofte(2003);Riener(2012))yields thateverysymmetricvarietydeﬁnedbypolynomialsofdegree

E-mailaddresses:[email protected](P. Moustrou),[email protected](C. Riener),[email protected] (H. Verdure).

https://doi.org/10.1016/j.jsc.2021.02.002

0747-7171/©²⁰²¹^TheÂuthor(s).^Published^byÊlsevier^Ltd.^Thisîsânôpenâccessârticleûnder^the^CC^BY^license (http://creativecommons.org/licenses/by/4.0/).

(2)

disnon-emptyoverRifandonlyifitcontainsarealpointwithatmostddistinctcoordinates.Here we aimat generalisingthisaspect of Timofte’sresult invarious ways. We are able toshow that - undertheassumption that thenumber ofvariables issuﬃciently large- thevariety corresponding to the symmetric ideal will not contain any point with strictly more than d distinct coordinates.

Moreover,ourresultyieldsthatthesetofpossibleconﬁgurationsoftheseddistinctcoordinatescan befurtherrestrictedby theshapeofthe monomialsofhighestdegreeamongst thegenerators of I, seeSection5.1.Theargumentsputforwardtoestablishthisresultarepurelyalgebraicandworkwith norequirementsonK.Infact,thisresultwillfollowfromastudyofSpechtpolynomialscontainedin symmetricideals.Moreprecisely,weassignapartitionofntothesemonomialsandwe relatethese partitionstospeciﬁcSpechtpolynomialswhichbelongtotheideal,seeSection 4.

In characteristic 0, this property also has an applicationto the structure of the decomposition of I in termsof Sn-representations. Theaction of Sn on I turns I andK

[

^X1

, . . . ,

Xn

] /

I intoK

[

^Sn

]

modules.Overaﬁeldofcharacteristiczerothesemodules canbedecomposedintoirreducibleK

[

^Sn

]

modules, which are usually called Specht modules and we show in Section 5.2 that the possible Spechtmodulesappearinginthisdecompositionarealsoveryrestricted(seeBasuandRiener(2020) foraresultinasimilarspiritintherealsetting).One applicationofsuchadecompositionconcerns sums of squares representations of positive symmetric polynomials modulo symmetric ideals. The understandingof the irreduciblerepresentations in I givesa control on the complexity ofsums of squaresdecompositioninthissetup,seeSection5.3.

Thisarticleisstructuredasfollows.Section2collectsnecessarystandardnotationsanddeﬁnitions.

Then,Section3focusesonvarietiesdeﬁnedbySpechtpolynomialsandtheirproperties.Thisisused inSection 4to describethe Spechtpolynomialscontainedinsymmetric ideals.Finally,Section 5 is devotedtoapplications.

2. Preliminarynotationsanddeﬁnitions 2.1.PartitionsandYoungtableaux

Foranynaturalnumbern,onecanconsideritspartitions:

Deﬁnition1.Letn

∈

N.Apartition

λ

ofn,(denoted

λ

ⁿ⁾^is^a^sequence

λ = (λ

1

, · · · , λ

_l

)

ofpositive naturalnumbers orderedsuch that

λ

1

λ

2

· · · λ

l^{0 with} ^the^property

λ

1

+ . . . + λ

l

=

^n.^The lengthof

λ

is

len

(λ) =

^max

{

ⁱ

: λ

_i

=

⁰

} .

Wewillallowourselvestoidentifypartitionsthatonlydifferby0 terms.

Deﬁnition2.Foragivenpartition

λ

,itsdualpartition

λ

^⊥isdeﬁnedby

λ

^⊥

i

= {

^j

, λ

j

ⁱ

} .

PartitionsareverywellknownandarecloselyrelatedtoYoungtableaux(seee.g.Sagan(2013)).

Deﬁnition3.Given

λ

^n, ^a ^Young^{tableau T} ^of ^shape

λ

^n, ^or^a

λ

-tableauconsistsof len

(λ)

rows, with

λ

i entriesin the i-throw.Each entryisan element in

{

¹

, . . . ,

n

}

^, ândêach ôf^these^numbers occursexactlyonce.Furthermorewewritesh

(

T

) = λ

.

Deﬁnition4.Letn

∈

N.Let

λ = (λ

1

, · · · , λ

l

)

ⁿ^and

μ = ( μ

1

, · · · , μ

m

)

ⁿ^be^twopartitions.Wesay that

λ

dominates

μ

if

i j=1

λ

j

i

j=1

μ

j holds for all 1

ⁱ

^min

{

^len

(λ),

len

( μ )}.

(3)

Wewillwrite

λ μ

inthiscase.

Equippedwiththedominanceorder,thesetofallpartitionsofagivenn

∈

Nisapartiallyordered set.We will further use

λ ν

to denote the caseinwhich

λ

does not dominate

ν

. Notethat the orderisonlypartialandhencethisdoesnotentailthat

ν

dominates

λ

,sincetheyalsomightbenot comparable.Furthermore,notethat

λ

^⊥

1

=

^len

(λ)

,

λ

^⊥_⊥

= λ

,and

λ μ ⇔ μ

^⊥

λ

^⊥

.

2.2.Orbittypesandpartitions

TheactionofS_n onKⁿ naturallydecomposesthespaceintoorbits.

Deﬁnition5.Foreveryx

∈

Kⁿ,theassociatedstabilizersubgroupStab

(

x

) ⊆

^Sn isoftheform Stab

(

x

)

S₁

×

^S2

× · · · ×

^S_k

with

1

2

. . .

_k.Wehencedeﬁnetheorbittypeofxtobe

(

x

) := (

1

,

2

, · · · ,

_k

).

Then,foragiven

λ

ⁿ^we^can^deﬁne H_λ

:=

x

∈ K

ⁿ

: (

x

) = λ .

Remark1.Notethatwehave

K

ⁿ

= ·

λn

H_λ

.

2.3.Polynomials,varieties,andsymmetricideals

Let K be a ﬁeld, and consider the polynomial ring in n variables K

[

^X1

, · · · ,

X_n

]

^. ^For ^any P

∈

K

[

^X1

, · · · ,

Xn

]

^, ^we ^denote^by ^Mon

(

P

)

theset ofmonomialsappearing in P,andby P_h its ho- mogenouscomponentofdegreeh.

Givenamonomial m

=

n j=¹

X^k_j^j

,

itssupport is

Supp

(

m

) = {

^j

,

k_j

=

⁰

}

anditsweightwt

(

m

)

isthecardinalityofitssupport.Bytakingtheunionoverallthemonomialsin Mon

(

P

)

,wegeneralizethesenotionsto P todeﬁneSupp

(

P

)

andwt

(

P

)

.

ToeveryidealinK

[

^X1

, . . . ,

Xn

]

ône^canâssociateâ^variety:

Deﬁnition6.Let I be anidealinK

[

^X1

, . . . ,

X_n

]

^.^The ^{variety V}

(

I

)

associatedwith I isthesubset of Kⁿ madebythecommonzerosofallthepolynomialsinI,namely

V

(

I

) = {

^x

∈ K

ⁿ

,

P

(

x

) =

0 for everyP

∈

^I

} .

TheactionofSnonKⁿinducesanactiononK

[

^X1

, . . . ,

Xn

]

^by^permuting^the^variables.^We^denote by

σ

P theimageofapolynomial P undertheactionofapermutation

σ

.

(4)

Deﬁnition7.Anideal I

⊂

K

[

^X1

, . . . ,

Xn

]

îs^calledâ^symmetricîdeal îf^forêvery ^P ⁱⁿ Î ând^forêvery

σ ∈

Sn,

σ

P belongstoI.

Notethat ifI isasymmetricideal,thenthevariety V

(

I

)

isclosedundertheactionof Sn onthe coordinates.

2.4.Spechtpolynomials

The so-calledSpechtpolynomials will play a central role in ourproofs. Those polynomials were originallydesignedbySpecht(1935) toconstructthedifferentirreduciblerepresentationsof S_n. Deﬁnition8.Letn

∈

N.

(1) ForasetS

= {

ⁱ1

, . . . ,

ir

} ⊂ {

¹

, . . . ,

n

}

^,^we^deﬁne^theVandermondedeterminant

(

S

)

ofthevariables Xi,fori

∈

^S:

(

S

) :=

1^j<k^r

(

X_i_j

−

^Xik

).

(2) Let

λ

ⁿ^and^T ^be^a

λ

-tableau.ThentheSpechtpolynomialassociatedwithT isthepolynomial sp_T

:=

c

(

T_·_,_c

),

wherec runsthroughthecolumnsofT,andT_·,c denotestheentriesinthecthcolumn.Wewill saythatsp_T isaSpechtpolynomialofshape

λ

.

Example1.TheSpechtpolynomialassociatedwiththeYoungtableau 4 2 6 1

8 7 5 3

is

(

X₄

−

^X8

)(

X₄

−

^X3

)(

X₈

−

^X3

)(

X₂

−

^X7

)(

X₆

−

^X5

).

3. ZerosofSpechtpolynomials

Throughoutthepaper,wewillbeinterestedintheidealgeneratedby alltheSpechtpolynomials ofagivenshape,aswellasinthecorrespondingvariety.

Deﬁnition9.LetKbeaﬁeld,nbeaninteger,and

μ

^n.

•

^The

μ

-Spechtideal, denoted by I^spμ, is the ideal of K

[

^X1

, . . . ,

X_n

]

^generated ^by ^all ^the ^Specht polynomialsofshape

μ

.

•

^We^denote^by^VμthesetofcommonzerosofallSpechtpolynomialsofshape

μ

,thatis V_μ

:=

^V

(

I_μ^sp

) =

sh(T)=μ V

(

sp_T

).

Weaimatdescribingmorepreciselythosevarieties.Particularcasesofthesevarietieshavebeen studiedforexampleinYanagawa(2019);WatanabeandYanagawa(2019);FröbergandShapiro(2016).

Letusstart withafew remarks.Let T bea Youngtableau, ofshape

μ

^n.^A^point ^x

= (

x₁

, . . . ,

x_n

)

(5)

is a zeroof sp_T if andonly if there exists a column of T containing two indexes i

=

^j ^such ^that xi

=

^xj.Followingthiseasyobservation, we getacharacterizationof Vμ thatwillbe usefullater:a pointx

∈

Kⁿ doesnotbelongtoVμifandonlyifonecanﬁllinaYoungtableauofshape

μ

withthe coordinatesofxinsuchawaythatineverycolumn,allthevaluesaredistinct.

Thisremark alreadyimplies some properties aboutvarieties associated withSpecht ideals, that willbeusefulinthefollowing:

Proposition1.Letx beapointinKⁿ,and

(

x

)

itsorbittype.Then:

i) Thepointx isnotinthevarietyV₍x),

ii) If

μ

isapartitionofn suchthatx

∈ /

^Vμ,then

(

x

) μ

.

Proof. Let

λ = (

x

) = (λ

1

, . . . , λ

r

)

,andletu1

, . . . ,

ur bethedistinctcoordinatesofx,whereforeach 1ⁱ^r,^uiappears

λ

i times.

Letusﬁrstprovei).LetT beanyYoungtableauofshape

λ

such thattheindexesintheithrow aretheindexes jsuchthatxj

=

^ui.Thensp_T

(

x

) =

^0,ând^hence^xîsôutside^Vλ.

Nowletusproveii).SupposexnotinVμ.ThismeansthatthereexistsaYoungtableauU ofshape

μ

such that sp_U

(

x

) =

^0.^Thus ^we ^can^fill Û ^with û1

, . . . ,

u_r insuch a waythatfor every 1ⁱ^r, ui appears atmostonce per column, andwe mayassume without lossof generality that inevery column, if uj is below ui,then i

<

j. As a consequence, for every 1^k^r, ^the ûi for i^k âre containedinthefirstkrowsofT.Thismeansthat

λ

1

+ . . . + λ

k

μ

1

+ . . . + μ

k

,

whichimplies

λ μ

.

NowwewanttoprovethatVλcontainsexactlytheVμsuchthat

μ

λ

.Thisisaconsequenceof thecorrespondinginclusionofideals:

Theorem1.Let

λ

and

μ

betwopartitionsofn.Thenthefollowingassertionsareequivalent:

i) Thepartition

μ

dominates

λ

,i.e.

λ μ

, ii) TheidealI^spμ containsI_λ^sp,i.e.I_λ^sp

⊂

^I^spμ, iii) ThevarietyV_λcontainsVμ,i.e.Vμ

⊂

^Vλ.

Remark2.Notethatthe inclusionofidealswas notaprioriequivalent totheinclusion ofvarieties, sinceitisnotknownwhetherSpechtidealsareradical,seeYanagawa(2019).

Proof. Westartby provingi)impliesii). Let

λ = (λ

1

, . . . , λ

t

)

,and

μ

suchthat

λ μ

.We onlyneed toconsidertheparticularcasewhere

μ

isoftheform

μ = (λ

1

, . . . , λ

i−1

, λ

i

+

¹

, λ

i+1

, . . . , λ

j−1

, λ

j

−

¹

, λ

j+1

, . . . , λ

t

),

where

λ

i−¹

> λ

i and

λ

j

> λ

j+¹,inordertoensurethat

μ

isapartition.Indeed,itisknownthatwe cangofrom

λ

toany

μ λ

byaﬁnitenumberofsuchsteps,seee.g. (Brylawski,1973,Prop.2.3).

LetT bea Youngtableauofshape

λ

.Weneedto show thatsp_T belongstotheideal generated byallthepolynomialssp_U whereU runsthroughalltheYoungtableauxofshape

μ

.IfU isaYoung tableauofshape

μ

,then itscolumnshavethesamenumberofelements than T,exceptfortwo of them.Let U₁ and U₂ be thesecolumns, andlet T₁ and T₂ be the corresponding columns in T. If a

= |

^T1

|

^and^b

= |

^T2

|

^,^then

|

^U1

| =

^a

−

^1,

|

^U2

| =

^b

+

^{1 and}^a

−

^b^2.^Byrestrictingour attentionto thesetwocolumns,itisenoughtoprove,uptopermutation,thatthepolynomial

P

= ( {

¹

, . . . ,

a

} )( {

^a

+

¹

, . . . ,

a

+

^b

} )

(6)

isintheidealIofK

[

^X1

, . . . ,

Xa+^b

]

^generated^by^all^thepolynomialsoftheform

(

S₁

)(

S₂

),

with

|

^S1

| =

^a

−

¹

,|

^S2

| =

^b

+

¹

,

andS₁

∪

^S2

= {

¹

, . . . ,

a

+

^b

}.

Considerthepolynomial

Q

= ({

2

, . . . ,

a

})({

1

,

a

+

1

, . . . ,

a

+

b

})

X^a₁⁻^b⁻¹

,

andthepolynomial R

=

a i=¹

((

1

,

i

))(

1

,

i

)

Q

,

where

denotesthe signature. Byconstruction, R isinthe ideal I.We needtoprove that forany pair1

α < β

â ândâ

+

¹

α < β

^a

+

^b,^the ^polynomial

(

Xα

−

^Xβ

)

divides R,equivalently R vanisheswheneverX_β

=

^Xα.Inotherwords,wewanttoshow

R_α_,β

=

^R

(

X1

. . . ,

X_β−1

,

X_α

,

X_β+1

, . . . ,

Xn

) =

⁰

foreverypair1

α < β

âândâ

+

¹

α < β

^a

+

^b.

ThelattercaseisobviousbydeﬁnitionofQ andR.Suppose1

α < β

^a.^Then^for^everyⁱ

= α , β

wehave

((

1

,

i

)

Q

)

α,β

=

^0,^so^that

R_α,β

= ((

1

, α ))((

1

, α )

Q

)

_α,β

+ ((

1

, β))((

1

, β)

Q

)

_α,β

.

Now,wehavetodistinguishtwocases,namely

α =

^{1 and}

α =

^1.^In^the^ﬁrst^case,^we^have R₁_,β

=

^Q1,β

− ((

1

, β)

Q

)

₁_,β

=

⁰

while in the second case, the signatures are both negative, but the polynomials differ from each other by interchanging the variables X1 and Xα inplaces

α

and

β

, andby deﬁnitionof Q, these polynomialsareoppositeofeachother,thatis,

R_α_,β

=

⁰

.

Thisimpliesthat P

= ( {

¹

, . . . ,

a

} )( {

^a

+

¹

, . . . ,

a

+

^b

} )

divides R.SincethedegreeofR satisﬁes deg

(

R

)

^deg

(

Q

) = (

a

−

¹

)(

a

−

²

)

2

+ (

b

+

¹

)

b

2

+

^a

−

^b

−

¹

=

^a

(

a

−

¹

)

2

+

^b

(

b

−

¹

)

2

=

^deg

(

P

),

itimpliesthat R

=

^{c P}

with c

∈

K, and we need to check that c is not zero. The degree of Q in the variable X1 is b

+

^a

−

^b

−

¹

=

^a

−

^{1 while}îts^degreeⁱⁿ^the^variable ^Xifor2ⁱâîsâ

−

^2.^Thus,^the^degree^of^Rⁱⁿ thevariableX₁ isexactlya

−

^{1 and}^thecorrespondingcoeﬃcientis

({

²

, . . . ,

a

})({

^a

+

¹

, . . . ,

a

+

^b

})

^, whichisalsothecoeﬃcientof X^a₁⁻^b in P.Hence R

=

^P^.

Since ii) obviously implies iii), we only have to prove that iii) implies i). Assume then that Vμ

⊂

^Vλ.Consider xwithorbittype

(

x

) = λ

.Then,accordingtoi)ofProposition1,x

∈ /

^Vλ.Thenby assumption,x

∈ /

^Vμ,andii)ofProposition1yields

λ μ

.

Finally,asaconsequenceofthepreviousresults,wegetacharacterizationofVμintermsoforbit types:

(7)

Corollary1.ThesetofcommonzerosofSpechtpolynomialsassociatedwithYoungtableauxofgivenshape

μ

canbecharacterisedas

V_μ

=

⎛

⎝

λμ

H_λ

⎞

⎠

c

=

νμ H_ν

Proof. We want to show Vμ^c

=

λμH_λ. The direct inclusion is nothing but ii) inProposition 1.

Conversely,let x

∈

^Hλ,with

λ μ

.Accordingtoi) inProposition1,xisoutside Vλ.Since

λ μ

,it followsfromTheorem1that Vμ

⊂

^Vλ,sothatx

∈

^V_μ^c^.

4. Spechtpolynomialsinsymmetricideals

Inthissectionwe showthatifasymmetricidealcontainspolynomialswithsparse leadingcom- ponent,thenthisidealwillcontainmanySpechtpolynomials.Letusbemoreprecise: First,toevery monomialweassociateapartition:

Deﬁnition10.LetmbeamonomialofweightlanddegreedinK

[

^X1

, . . . ,

Xn

]

^.^The^partial^degrees^of minduceapartitionofdoflengthl,say

(λ

1

, . . . , λ

l

)

.

Ifmoreoverweassumethatl

+

^d^n,^we^can^deﬁne^a^partition

μ (

m

)

ofnby

μ (

m

) = (λ

1

+

1

, λ

2

+

1

, . . . , λ

l

+

1

,

1

, . . . ,

1

n−d−l

).

Example2.Letn

=

^12,^and m

=

^X2X⁴₄X₅²

.

Then

μ (

m

) = (

5

,

3

,

2

,

1

,

1

).

Thenwewillshow:

Theorem2.LetI

⊂

K

[

^X1

, . . . ,

Xn

]

^beâ^symmetricîdeal.Âssume^that^thereêxists ^P

∈

^{I of}^degree^d,^such thatd

+

wt

(

Pd

)

n.Then,foreverymonomialm

∈

Mon

(

Pd

)

,theideal I containseverysp_T forwhich sh

(

T

) μ (

m

)

^⊥.Inotherwords:

I^sp_λ

⊂

I forevery

λ μ (

m

)

^⊥.

Accordingto Theorem 1,it isenough to prove that I contains the Spechtpolynomials ofshape

μ (

m

)

^⊥.Henceweonlyneedtoprove:

Proposition2.Let I

⊂

K

[

^X1

, . . . ,

Xn

]

^beâ ^symmetricîdeal.Âssume^that^thereêxists ^P

∈

^{I of}^degree^d, suchthatd

+

^wt

(

Pd

)

^n.^Then,^for^every^monomial^m

∈

^Mon

(

Pd

)

,theidealI containseverysp_T forwhich sh

(

T

) = μ (

m

)

^⊥.InotherwordsI^sp

μ(m)^⊥

⊂

^I.

Inthefollowingproof, wewillassume that thecharacteristicofKiszero.Thisallows formore conceptualproof.Thisassumption onthecharacteristicensuresthat thefactorialsinthe endofthe proofdonotvanish.WeprovideageneralproofintheAppendix.

(8)

Proof. LetKbeaﬁeldofcharacteristic0.SincetheidealIissymmetric,wemayassumethat m

=

^X^k₁¹^X^k₂²

· · ·

^X_l^k^l

,

andthatSupp

(

P_d

) = {

¹

, . . . ,

wt

(

P_d

) }

^.Îtsâssociated^partitionîs

μ := μ (

m

) = (

k₁

+

¹

,

k₂

+

¹

, . . . ,

k_l

+

¹

,

1

, . . . ,

1

n−^d−^l

).

ThestatementsaysthattheidealI containsanySpechtpolynomialoftheform

1

2

· · ·

l

,

wherethe

i are Vandermonde polynomialsin disjointsets of variables, each ofsize ki

+

¹

= μ

i. Thankstoitssymmetry,itisenoughtoshowthat Icontainsonesuchpolynomial.

OurstrategyconsistsinusingX_i^kⁱ tobuildaVandermondepolynomialinvolvingX_iandk_ivariables thatdonot appearin Pd.Ourassumption on Pd guaranteesthat thereareenough freevariablesto doso.

More precisely, we can take I1

, . . . ,

I_l,disjoint subsets of

{

¹

, . . . ,

n

}

^such ^that ^for ^any¹ⁱ^l, thereareki elementsinIi,andnoneofthemappearsin Pd.Let,for1ⁱ^l,

J_i

= {

ⁱ

} ∪

^Ii

.

WewillshowthatthereexistpolynomialsRσ

∈

K

[

^X1

, . . . ,

Xn

]

^,^for

σ ∈

^Snsuchthat:

(

J₁

) · · ·(

^Jl

) =

σ∈Sn

R_σ

σ

P

.

Here, applying the strategy used to prove Theorem 1 we give explicit polynomials Rσ when the characteristicofKis0.Inthegeneralcase,wecangivearecursiveconstructionofthesepolynomials;

wepostponethisconstructiontoAppendixA.Considerthepolynomials Q

= (

I₁

) · · ·(

^Il

)

P

and

R

=

σ∈^SJ1×···×^S_Jl

( σ ) σ

Q

,

whereS_J₁

× · · · ×

^SJl isseenasasubgroupof S_n.Byconstruction,forevery

ρ ∈

^SJ1

× · · · ×

^SJl,

ρ

R

= ( ρ )

R

sothat

(

J1

) · · · (

Jl

)

dividesR.Furthermore,since

deg

(

Q

) =

^d

+

l

i=¹

k_i

(

k_i

−

¹

)

2

=

l i=¹

ki

(

ki

−

1

)

2

+

^ki

=

l i=1

ki

(

ki

+

1

)

2

=

^deg

((

J₁

) · · · (

J_l

)),

weget

(9)

R

=

^c

(

J₁

) · · ·(

^Jl

)

withc

∈

K. In order to check that c is not 0, we look at the coeﬃcient of R corresponding with m

=

^X^k₁¹

· · ·

^X^k_l^l^,^seenâsânêlementôf

(K [

^Xl+1

, . . . ,

Xn

])[

^X1

, . . . ,

X_l

]

^.

In Q,thiscoeﬃcient is

(

I1

) · · · (

Il

)

.If, for1ⁱ^l,^thepermutation

σ _∈

SJ1

× · · · ×

^SJ_l does notletiinvariant,theassumptiononP_densuresthatthecoeﬃcientofmin

σ

Q willbe0.Therefore, thecoeﬃcientofR correspondingwithm is

σ∈SI1×···×S_Il

( σ ) σ (

I1

) · · · (

I_l

) =

^k1

! · · ·

^kl

! (

I1

) · · · (

I_l

)

andhenceR

=

^k1

! · · ·

^kl

! (

J1

) · · · (

Jl

)

. 5. Applications

5.1.Computingpointsinsymmetricvarieties

Letn be an integer and I be a symmetric ideal in K

[

^X1

, . . . ,

Xn

]

^. ^What ^can ^we ^say ^about^the variety V

(

I

)

? For instance, can we algorithmically decide if V

(

I

)

is empty in an eﬃcient manner makinguseofthestructureofI?

Over any real closed ﬁeld R the so-called half-degreeprinciple Timofte (2003) can be used to simplifythealgorithmicaltaskofrootﬁnding.Thisstatementsays(Riener,2012,Corollary1.3):

Theorem3.LetKbearealclosedﬁeld,andletP beasymmetricpolynomialinK

[

^X1

, . . . ,

X_n

]

^of^degree^d, andletk

=

^max

(

2

,

^d₂

)

.Thenthereexistsx

∈

KⁿsuchthatP

(

x

) =

⁰îfândônlyîf^thereêxists^y

∈

Kⁿwith atmostk distinctcoordinatessuchthatP

(

y

) =

^0.

Thisimpliesthefollowingresultonsymmetricideals:

Corollary2.LetKbea realclosedﬁeld,andlet I beasymmetricideal ofK

[

^X1

, . . . ,

Xn

]

^,^generated^by P1

, . . . ,

P_l.Letd

=

^max

(

deg

(

P1

), . . . ,

deg

(

P_l

))

.ThenV

(

I

)

isnonemptyifandonlyifitcontainsapoint x

∈

Kⁿwithatmostd distinctcoordinates.

Proof. Overarealclosedﬁeldthevariety V

(

I

)

isexactlythevarietydeﬁnedby

Q

=

l

i=¹

σ∈^Sn

σ (

P_i

)

²

andwecanapplyTheorem3.

The algorithmic implications of this resultare the following. Take

μ

ⁿ ^of ^length ^d. ^For^every polynomial P

∈

K

[

^X1

, . . . ,

X_n

]

^we^consider

P^μ

:=

^P

(

Z₁

, . . . ,

Z₁

μ1

,

Z₂

, . . . ,

Z₂

μ2

, . . . ,

Z_d

, . . . ,

Z_d

μd

)

anddenotebyIμ

⊂

K

[

^Z1

, . . . ,

Z_d

]

^the^resulting^idealⁱⁿ^d^variables.^Moreover^consider^thetopological closureHμof Hμandthemap

_μ

:

^V

(

I^μ

) −→ (

V

(

I

) ∩

^Hμ

)/

Sn

whichassociatestoapointx

= (

x1

, . . . ,

xd

) ∈

^V

(

Iμ

)

theSn-orbitofthepoint x

= (

x

1

, . . . ,

x1

μ1

,

x

2

, . . . ,

x2 μ2

, . . . ,

x

d

, . . . ,

xd μd

).

(10)

Thismapisclearlysurjective,andfromthenaturaldecomposition V

(

I

) =

μⁿ

(

V

(

I

) ∩

H_μ

) =

νⁿ

(

V

(

I

) ∩

H_ν

)

wethusget

V

(

I

)/

Sn

=

νⁿ

_ν

(

V

(

I^ν

)).

ThenCorollary 2sayspreciselythat V

(

I

)

isemptyifandonlyif V

(

Iμ

)

is emptyforeverypartition

μ

ofn withlen

( μ )

^d. ^Since^the ^number^ofd-partitionsofn is boundedby

(

n

+

¹

)

^d theoriginal probleminnvariablesreducestoapolynomialnumberofproblemsindvariables.

Ourresultsyieldastrongerversion ofthisprinciple,underadditionalassumptiononthesupport ofthepolynomials:Ontheonehandourresultsare validforanyﬁeld, andon theotherhand,not onlyourvarietiescontainpointswithfewdistinctcoordinates,buttheycontainonlypointswithfew distinctcoordinates.Moreprecisely,Theorem2gives,inthiscontext:

Theorem4.LetI

⊂

K

[

^X1

, . . .

Xn

]

^beâ^symmetricîdeal.Âssume^that^thereêxists^P

∈

^{I of}^degree^{d such}^that wt

(

Pd

) +

^d^{n and}^let^m

∈

^Mon

(

Pd

)

.Then

V

(

I

) ∩

^Hλ

= ∅

^{for all}

λ μ (

m

)

^⊥

.

Inotherwords,

V

(

I

)/

Sn

=

νμ(m)^⊥

_ν

(

V

(

I^ν

)).

Proof. Accordingto Proposition2,thevariety V

(

I

)

iscontainedinthevariety Vμ^⊥ associatedwith theSpechtidealI^sp

μ^⊥.Corollary1thenyields V

(

I

) ⊂

λμ(m)^⊥ Hλ

.

Since Kⁿ is the disjoint union of the subsets Hλ, it follows that for all

λ

with

λ μ (

m

)

^⊥, V

(

I

) ∩

^Hλ

= ∅

^.Furthermore,wecanwrite

V

(

I

) =

λμ(m)^⊥

(

V

(

I

) ∩

^Hλ

).

Thus,toprovethesecondpartofthestatement,itisenoughtoprovethat

λμ(m)^⊥

(

V

(

I

) ∩

^Hλ

) =

νμ(m)^⊥

(

V

(

I

) ∩

^Hν

).

Oneinclusionistrivial,wefocusontheother one.Assumethat x

∈

Hν.Thennaturally,

ν (

x

)

.So if

ν μ (

m

)

^⊥,wealsohave

(

x

) μ (

m

)

^⊥.

Hence,ifoneisabletocompute thepointsinthevariety V

(

Iν

)

,one getsallthepoints of V

(

I

)

. Alsonotethatthelengthofthepartitions

ν

isatmostd,thiscomesfromthefollowingobservation:

Proposition3.Letn beaninteger,andm beamonomialofdegreed,withd

+

^wt

(

m

)

^n.^Then^for^every partition

λ

ofn suchthatlen

(λ) >

d,

μ (

m

)

^⊥

λ.

(11)

Proof. Theproofconsistsintwosteps.Firstweprovethat

μ (

m

)

^⊥

(

n

−

^d

,

1

, . . . ,

1

d

).

Indeed,ifm

=

^X^k₁¹

· · ·

^X_l^k^l^,

μ (

m

) = (

k1

+

1

,

k2

+

1

, . . . ,

k_l

+

1

,

1

, . . . ,

1

n−d−l

)

haslengthn

−

^d,^so^that

μ (

m

)

^⊥

= (

n

−

^d

, . . .) (

n

−

^d

,

1

, . . . ,

1

d

).

Second,iflen

(λ) >

d,then

(

n

−

^d

,

1

, . . . ,

1

d

) λ.

Indeed,ifnot,thereexists j suchthat

j i=1

λ

i

> (

n

−

^d

) + (

j

−

¹

).

Inthiscase,sincelen

(λ)

^d

+

^1,

n

=

len

(λ) i=¹

λ

_i

j i=¹

λ

_i

+

^len

(λ) −

^j

>

n

−

^d

+

^j

−

¹

+

^len

(λ) −

^j

>

n

.

Remark3.The propositionabove showsthat we can always ensure that every pointof thevariety V

(

I

)

hasatmostddistinctcoordinates.Ifthemonomialmis X₁^dthen

μ (

m

)

^⊥

= (

n

−

^d

,

1

, . . . ,

1

)

and thisistheonlycasewhereweneedtoconsideralld-partitionsofn.

Already for the monomial m

=

^X^d₁⁻¹^X2, we have

μ (

m

) = (

d

,

2

,

1

, . . . ,

1

)

, and

μ (

m

)

^⊥

= (

n

−

^d

,

2

,

1

, . . . ,

1

)

. Then for every 2^k

(

n

−

^d

−

²

)/

2,the partition

(

n

−

^d

− (

k

−

²

),

k

,

1

, . . . ,

1

)

haslength d and is dominatedby

μ (

m

)

^⊥: they are among the partitions that we do not need to consider.

Themostfavourablecasewillbem

=

^X1X₂

· · ·

^Xd,where

μ (

m

)

^⊥

= (

n

−

^d

,

d

)

.Inthiscase,theonly partitions

λ = (λ

1

, . . . , λ

t

)

thatarenotdominatedby

μ (

m

)

^⊥aretheoneswith

λ

1

>

n

−

^d.

Therefore,aﬁneanalysisontheactualmonomialsofhighestdegreeinthegeneratorsofI allows to reduce the number of partitions that need to be considered, which can be seen as a stronger versionofthedegreeprinciple.

Onefurthernaturalconsequenceisthatourvarietyiscontainedinaﬁniteunionofd-dimensional subspaces,hence:

Corollary3.LetI

⊂

K

[

^X1

, . . . ,

Xn

]

^beâ^symmetricîdeal.Âssume^that^thereêxists^P

∈

^{I of}^degree^d,^such^that d

+

wt

(

Pd

)

n.ThenthedimensionofthevarietyV

(

I

)

isatmostd.

Inamoregeneralsetup,NagelandRömerNagelandRömer(2017) studysequencesofsymmetric ideals.Theyshow inparticularthat thedimensionoftheideals theystudyisalinearfunctioninn.

Inourmorerestrictedframework,wethusobtainastabilizationofthedimensionofsuchsequences.

(12)

5.2.Isotypiccomponentsofsymmetricideals

Theactionofthesymmetricgroup Sn onK

[

^X1

, . . . ,

Xn

]

^is^linear,^giving^the^polynomial^ring ^the structureofaK

[

^Sn

]

^-module.^If^we^assume^that^thecharacteristicofKis0,theneveryK

[

^Sn

]

^-module canbedecomposedasadirectsumofirreduciblesubmodules.Itiswellknown(seee.g.Sagan(2013)) thattheirreducibleK

[

^Sn

]

^-modules^areⁱⁿcorrespondencewiththepartitionsofn.Thesemodulesare calledSpechtmodules,denotedbyS^λ.ItfollowsthateveryK

[

^Sn

]

^-module^U ^can^be^uniquely^written as

U

λn

U_λ

,

whereforeverypartition

λ

ofn,Uλisadirectsumofirreduciblesubmodulesisomorphicto S^λ.The submoduleU_λiscalledthe

λ

-isotypiccomponentofU.

NowletI

⊂

K

[

^X1

, . . . ,

Xn

]

^beâ^symmetricîdeal.ÎtîsâlsoâK

[

^Sn

]

^-module,^and^we^have,^for^every partition

λ

ofn,

I_λ

= K [

^X1

, . . . ,

Xn

]

λ

∩

^I

.

Let

λ

be a partition of n, then the linear subspace Wλ of K

[

^X1

, . . . ,

Xn

]

^generated ^by ^all ^the Spechtpolynomialsofshape

λ

isanirreduciblesubmodule ofK

[

X1

, . . . ,

Xn

]

λ isomorphicto S^λ.For anyotherirreduciblesubmoduleW_λinK

[

^X1

, . . . ,

Xn

]

λ,wehaveanisomorphism

ϕ

betweenW_λand Wλ.Let T beaYoungtableauofshape

λ

.Since

ϕ

respectstheactionof Sn,forany

τ

transposition oftwoelementsinasamecolumnofT,

τ ϕ (

sp_T

) = − ϕ (

sp_T

),

sothat

ϕ (

sp_T

)

hasto be divisible by sp_T.It follows that K

[

^X1

, . . . ,

Xn

]

λ is includedin theSpecht idealI^sp_λ,andthereforeTheorem2gives:

Theorem5.LetKbeaﬁeldofcharacteristic0andI

⊂

K

[

^X1

, . . . ,

Xn

]

^beâ^symmetricîdeal.Âssume^that thereexistsP

∈

^{I of}^degree^d,^such^that^d

+

^wt

(

P_d

)

^n.^Then^for^every^m

∈

^Mon

(

P_d

)

,forevery

λ μ (

m

)

^⊥, theidealI containstheisotypiccomponentK

[

^X1

, . . . ,

Xn

]

λ.Inotherwords

I_λ

= K [

^X1

, . . . ,

X_n

]

λ

,

orequivalently

(K [

^X1

, . . . ,

Xn

] /

I

)

_λ

= {

⁰

} .

Given polynomials P₁

, . . . ,

P_l

∈

K

[

^X1

, . . . ,

X_n₀

]

^, ^they ^naturally înduce â ^symmetric îdeal ⁱⁿ K

[

^X1

, . . . ,

Xn

]

^for^anyⁿⁿ0.Wegetanincreasingsequenceofsymmetricideals

(

I

)

nⁿ0,andonecan studystabilizationpropertiesintermsofrepresentations(seeforinstanceSamandSnowden(2015);

Churchetal.(2015)).

Weremarkthat whennislargeenough,theconditiononthesupportoftheleading component ofP isautomaticallyfulﬁlledandwecanimmediatelydeduce:

Theorem6.LetKbeofcharacteristic0andn0beaninteger.GivenQ1

, . . . ,

QlinK

[

^X1

, . . . ,

Xn0

]

^,^consider foranynⁿ0theideal

In

= σ (

Qi

), σ ∈

Sn

,

1

i

l

.

Thenifn islargeenough,forevery1ⁱ^l,^every^monomial^{m of}^Qiofmaximaldegree,andany

λ

partition ofn suchthat

λ μ (

m

)

^⊥,

(K [

^X1

, . . . ,

Xn

] /

In

)

_λ

= {

⁰

} .

(13)

5.3.Symmetricsumsofsquaresonsymmetricvarieties

As a ﬁnal application we consider sums of squares of real polynomials. Let P

∈

K

[

^X1

, . . . ,

Xn

]

^. Then P iscalledasumofsquares,ifthereexistpolynomialsP1

, . . . ,

Pk with

P

=

^P1²

+ . . . +

^P_k²

.

Sumsofsquaresare the cornerstoneinthe socalledmomentapproach topolynomial optimization Lasserre (2001): in general, it can be decided by semideﬁniteprogramming if a given polynomial affords adecomposition asa sumof squares.The caseofsymmetric sums ofsquares hasreceived someinterestbydifferentauthorsBlekhermanandRiener(2021);Goeletal.(2016);Raymondetal.

(2018);Rieneretal.(2013);Kurpiszetal.(2016).

InBlekhermanandRiener(2021),Blekhermanandthesecondauthordescribedhowtocharacter- izesymmetricsumsofsquaresthroughrepresentationtheory.Moreprecisely,they usethetheoryof higherSpechtpolynomialsTerasomaandHigher(1993) toconstruct,forevery

λ

^n,^a^square^matrix polynomial Q^λ ofsize s_λ

=

^dim

(

S^λ

)

, whoseentries aresymmetric polynomials. Furthermore,these entriesare products andsums ofelements in R

[

^X1

, . . . ,

Xn

]

λ. Soeven though they are symmetric, theybelongtotheidealgeneratedbytheSpechtpolynomialsofshape

λ

.Thesematricescanbeused toshowthateverysymmetricpolynomial P thatisasumofsquarescanbewrittenintheform

P

=

λⁿ

Tr

(

P^λ

·

Q^λ

),

whereeach P^λ

∈

R

[

^X1

, . . . ,

Xn

]

^s^λ^×^s^λ îsâ^sumôf^symmetric^squares^matrixpolynomial,i.e.

P^λ

=

^L^t^L

forsomematrixLwhoseentriesaresymmetricpolynomials.

Sincethe

λ

-Spechtidealcontainsallthecoeﬃcientsof Q^λwecanapplyTheorem5toobtainthe followingresultonrepresentationsofasymmetricpolynomialmoduloasymmetricideal.

Theorem7.LetP

∈

R

[

^X1

, . . . ,

Xn

]

^Sⁿ^beâ^symmetric^sumôf^squares^polynomialând^{I be}â^symmetricîdeal inR

[

^X1

, . . . ,

Xn

]

^.^Further,^we^assume^that^there^exists^F

∈

^{I of}^degree^d,^such^that^d

+

^wt

(

F_d

)

^n.^Then^P canbewrittenas

P

=

νμ(m)^⊥

Tr

(

P^λ

·

^Q^λ

)

modI

,

whereagaineachP^λ

=

^L^t^{L for}^some^matrix^polynomial^{L whose}^entries^are^symmetricpolynomials.

AcaseofspecialinterestisthecasewhenI isthegradientidealI_grad

(

P

)

ofagivenpolynomial P ofevendegree2d.Nieetal.(2006) showedthatapolynomialthatispositiveonitsgradientvariety V

(

Igrad

)

canalwaysbewrittenasasumofsquaresmoduloitsgradientideal.WhenP isasymmetric polynomialourresultscanbeappliedtoreducetheproblemsize.

Itisworthremarkingthatperturbationscanbeusedtotransferapolynomialintothesituationof ﬁnitelymanycriticalpointsinasymmetricway:Forexample,HanzonandJibetean(2003),aswellas JibeteanandLaurent(2005) consideredthefollowingperturbationofapolynomial:

P_ε

:= ε · (

X^2d₁⁺²

+ . . . +

^X_n^2d⁺²

) +

^P

.

Sincetheperturbationtermispositivedeﬁniteandofhigherdegree,theperturbedpolynomial P has aglobalminimumandtheminimalvalueconvergestotheinﬁmumofP with

ε →

^0.^Moreover,^if ^P infacthasglobalminimizers,eachconnectedcomponentofthesetofglobalminimizersofP contains apointwhich islimitofabranchoflocalminimizersof Pε (seeJibeteanandLaurent(2005)).Fur- thermore,observethatthequotient I_grad

(

Pε

)

isgeneratedbythepolynomials2

(

d

+

¹

) ε

X_i^2d⁺¹

+

_∂^∂_X^P_i^,