Aperiodic Subshifts of Finite Type on Groups Emmanuel Jeandel LORIA, UMR 7503 - Campus Scientifique, BP 239 54506 VANDOEUVRE-LE`S-NANCY, FRANCE 5 [email protected] 1 0 7th July 2015 2 l u J Abstract 4 In thisnote we provethe following results: ] • IfafinitelypresentedgroupGadmitsastronglyaperiodicSFT,then R G has decidable word problem. More generally, for f.g. groups that G arenotrecursivelypresented,thereexistsacomputableobstruction . for them to admit strongly aperiodic SFTs. h t • On the positive side, we build strongly aperiodic SFTs on some a new classes of groups. We show in particular that some particular m monster groups admits strongly aperiodic SFTs for trivial reasons. [ Then, for a large class of group G, we show how to build strongly aperiodic SFTs over Z×G. In particular, this is true for the free 2 v groupwith2generators,Thompson’sgroupsT andV,PSL2(Z)and 1 any f.g. group of rational matrices which is bounded. 3 While Symbolic Dynamics [LM95] usually studies subshifts on Z, there has 8 been a lot of work generalizing these results to other groups,from dynamicians 6 0 and computer scientists working in higher dimensions (Zd [Lin04]) to group . theoristsinterestedincharacterizinggrouppropertiesinterms oftopologicalor 1 0 dynamical properties [CSC10]. 5 Inthisnote,weareinterestedintheexistenceofaperiodicSubshiftsofFinite 1 Type (SFT for short), or more generally of aperiodic effectively closed shifts. v: A subshift on a group G corresponds informally to a way of coloring the i elements of the group, subject to some local constraints. The constraints are X in finite number for a SFT, the constraints are given by an algorithm for an r effectively closed shift. a Ofgreatinterestis the existence ofaperiodicsubshifts, whichare nonempty subshifts for which no coloring has a translation vector, i.e. is invariant under translation by a nonzero element of G. An important example of a group with an aperiodic SFT is the group Z2, for which SFTs are sometimes called tilings of the plane and given by Wang tiles [Wan61], the most famous example being the Robinson tiling [Rob71]. NotallgroupadmitsanaperiodicSFTsthough,itisforexampleeasytosee thattherearenoaperiodicSFToverZ. However,all(countable)groupsadmits aperiodic shifts, this result is surprisingly nontrivial and quite recent [GJS09]. Therehasbeenalotofworkprovinghowto buildaperiodicSFTs inalarge class of groups, and more generally tilings on manifolds [Moz97, Coh14]. It 1 is an open question to characterizegroups that admit strongly aperiodic SFTs. Cohen[Coh14]provedthatthispropertyisaquasiisometryinvariant,andCarroll and Penland [CP] proved it is a commensurability invariant. In the first part of this article, we use computability theory to prove that groups admitting aperiodic SFTs must satisfy some computability obstruction. In particular, a finitely presented group with an aperiodic SFT has a decidable word problem. This is proven in section 2. Cohen[Coh14] showed that f.g. groups admitting strongly aperiodic SFTs are one ended and asked whether it is a sufficientcondition. Our first resultprovesinparticular that this condition is not sufficient. For f.g. groups that are not finitely presented, the computability condi- tion is harder to understand: Intuitively it means that the information about which products of generatorsare equal to the identity is enoughto know which productsaren’t,i.e. wecanobtainnegativeinformationaboutthewordproblem frompositive information. The exactcriterionis formulatedprecisely using the concept of enumeration reducibility. This generalization is presented in section 3,andmight be omitted by anyreadernotfamiliar orinterestedwith recursion theory. The more general result we obtain is as follows: Theorem. If a f.g. group G admits a normally aperiodic effectively closed subshift, then thecomplement ofthewordproblem of Gis enumerationreducible to the word problem of G. Forfinitelypresentedgroups, thisimplies thewordproblem ofGisdecidable. Normal aperiodicity is a weakening of the notion of aperiodicity, which is intermediatebetweenthenotionofweakaperiodicityandofstrongaperiodicity. Strongly aperiodic subshifts ask that the stabilizer of each point is finite. Here we ask that the stabilizer of each point does not contain a normal subgroup. The firstpart of the article is organizedas follows. Subshifts can be defined as shift-invariant topologically closed sets on AG, the sets of functions from G F to A. The first section introduces an effective notion of closed sets on A p and then on AG, and proves some link between the two. In the second section, we usethiseffectivenotiontoprovethemainresultforrecursivelypresentedgroups In the third section, we use concepts of computability theory to generalize the results to any f.g. group. In the second part of the article, we exhibit aperiodic subshifts of finite type for some groups G. We first show that some monster groups,which are infinite simple groups with some bad properties, admits strongly aperiodic SFTs The SFT we obtain are quite trivial and degenerate. In the last section, we will remark how a variation on a technique by Kari gives aperiodic SFTs on Z×G for a large class of group G. We do not know if there exists an easier proof of this statement. This class of groups contains the free group, f.g. subgroups of SO (Q), and Thompson’s group T and V. n 2 1 Effectively closed sets on Groups We first give definitions of effectively closed sets, which are some particular closed subsets of the Cantor Space AG and AFp. The reader fluent with sym- bolic dynamics should remark that the sets we consider are not supposed to be translation(shift)-invariant in this section. 1.1 Effectively closed sets on the free group Let F denote the free group on p generators, with generators x ...x . Unless p 1 p specified otherwise, the identity on F , and any other group will be denoted by p λ, and the symbol 1 will be used only for denoting a number. Let A be a finite alphabet. A word is a map w from a finite part of Fp to A. A configuration x ∈ AFp disagrees with a word w if there exists g so that x 6= w and both sides are g g well defined. Definition 1.1. Let L be a list of words. The closed set defined by L is the subset SFp of AFp of all configurations x that disagree with all words in L. L F Such a set is a closed set for the prodiscrete topology on A p. if S is a closed set of AFp, we denote by L(S) the set of all words of Fp that disagree with S. Note that S =S . L(S) Definition 1.2. A closed set S of AFp is effectively closed if S = SL for a recursively enumerable set of words L. Equivalently, L(S) is recursively enu- merable. Theequivalenceneedsaproof. Wegiveitintheformofthefollowingresult, which will be useful later on. Proposition 1.3. There exists an algorithm that, given an effective enumera- F tion L, halts iff S p is empty. L F Proof. For a finite set L, it is easy to test if S p is empty: just test all possible L words of AFp defined on the union of the supports of all words in L. F Furthermore,bycompactness,foraninfiniteL′,S p isemptyiffthereexists L′ F a finite L⊆L′ so that S p is empty. L Now, if L is effective, consider the following algorithm: enumerate all ele- F mentsw inL,andtestateachstepifS p isempty. Bythefirstremark, i {w1,...,wn} F it is indeed an algorithm. By the second remark, this algorithm halts iff S p is L empty. F Proof of the equivalence in the definition. Suppose that S = S p is effectively L closed. We will prove that L(S) is recursively enumerable. Let w be a finite word. Suppose that w is defined over I. Let W be the set of all words defined over I that are incompatible with w. Then w ∈L(S) iff S =∅. L∪W 3 1.2 Effectively closed sets on groups We will now look at closed sets of AG. From now on, a given finitely generated groupGwillalwaysbe givenasaquotientofafreegroup,thatisG=F /Rfor p R a normal subgroup of F . As long as G is finitely generated, it is routine to p showthatallsuchrepresentationsgivetheexactsamedefinitionofeffectiveness. Let φ be the natural map from F to G. For g,h∈F we will write g = h p p G for φ(g)=φ(h). Let w be a word on F . We say that w is a G-word if w = w whenever p g h g = h and both sides are defined. G A configuration x ∈ AG disagrees with a word w if there exists g ∈ F so p that x 6= w and both sides are defined. Note that a configuration in AG φ(g) g always disagrees with a word which is not a G-word. Definition 1.4. The closed set on G defined by L is the subset SG of AG of all L configurations x that disagree with all words in L. Such a set is a closed set for the prodiscrete topology on AG. If S is a closed set of AG, we denote by L(S) the set of all words of F that p disagree with S. Note that S =S . L(S) Note in particular that all words that are not G-words are always elements of L(S). Definition 1.5. A closed set S of AG is effectively closed if S = SG for a L recursively enumerable set of words L. Note thatthis is no longerequivalentto L(S) being recursivelyenumerable. Indeed, S = AG is effectively closed but L(AG) is recursively enumerable only if G is recursively presented (see below). In the following we will see closed sets of AG as closed sets of AFp. To do so, denote by PerG the set of all configurations of AFp which are G-consistent,thatisx =x wheneverg = h. ItisclearthatPer isaclosed g h G G set: In fact L(Per ) is exactly the set of words that are not G-words. G Furthermore Per is isomorphic to AG: There is a natural map ψ from G Per to AG defined by ψ(x)=y where y =x . ψ is invertible with inverse G φ(g) g defined by ψ−1(y)=x where x =y . g φ(g) This bijection preserves the closed sets in the following sense: Fact 1.6. ψ(SFp ∩Per )=SG L G L L(SFp ∩Per )=L(SG) L G L F While S p is always effective if L can be enumerated, it might be possible L F for S p ∩Per to not be effective. In fact: L G Proposition 1.7. Let A be an alphabet of size at least 2. Per is effective iff G has a recognizable word problem. G Arecognizablewordproblemmeansthatthere isanalgorithmthat, givena wordw inF ,haltsiffw= λ. ThisisequivalenttosayingthatGisrecursively p G presented. 4 Proof. IfGhasarecognizablewordproblem,wecanenumerateallpairs(g,h)∈F p s.t. g = h, and thus enumerate the set of words that are not G-words, that is R L(Per ). G Conversely, suppose that L(Per ) is enumerable. Let {a,b} be some fixed G letters from A, with a6=b. For g ∈G, consider the word w over {λ,g} defined by w =a,w =b. Then g = λ iff w ∈L(Per ). λ g G G Corollary 1.8. If G has a recognizable word problem and SG is effectively L F closed, then S p ∩Per is effectively closed. L G 2 Effective subshifts on Groups Ifx∈AG,denotebygxtheconfigurationofAG definedby(gx)h =xg−1h. This defines an action of G on AG. Definition 2.1. A closed set X of AG is said to be a subshift if x ∈ X,g ∈ G implies that gx∈X. X is an effectively closed subshift if X is effectively closed and is a subshift. X is a SFT if there exists a finite set L so that X = S{g−1w,g∈G,w∈L} = S{g−1w,g∈Fp,w∈L}. In particular a SFT is always effectively closed. Fact 2.2. If X is a subshift, ψ−1(X)⊆Per is a subshift. G Hence any subshift of AG lifts up to a subshift of AFp. As a warmup to the theorems, we consider X , the subset of {0,1}G of ≤1 configurationsthat containsat mostone symbol1. It is easyto see thatX is ≤1 closed, and a subshift. Proposition 2.3. Suppose that G has a recognizable word problem. If X is effectively closed then the word problem on G is decidable. ≤1 Proof. X liftsuptoasubshiftY onF withthepropertythat(a)Y iseffective ≤1 p (as G is recursively presented), hence L(Y) is enumerable (b) Y consists of all configurations so that x =x =1 =⇒ g = h. g h G Now let g ∈ F . Let w be the word defined by w = 1 and w = 1. Then p λ g w ∈L(Y) iff g 6= λ. G The complement of the word problem is recognizable, therefore decidable. In the following, we are now interested in aperiodic subshifts. Definition 2.4. For x∈AG denote by Stab(x)={g|gx=x}. A (nonempty) subshift X is strongly aperiodic iff for every x ∈ X, Stab(x) is finite. A(nonempty)subshiftX isnormallyaperiodiciffforeveryx∈X,∩ Stab(hx) h∈G is finite. Note that there are conflicting definitions in the literature for strong aperi- odicity: Some require that Stab(x)={λ} for all x∈X. The only result in this paper where this makes a difference is Prop 4.2. 5 Both properties are equivalent for commutative groups. ∩ Stab(hx) will h∈G be called the normal stabilizer of x. It is indeed a normal subgroup of G, and the union of all normal subgroups of Stab(x). Our first result states that a strongly aperiodic effectively closed subshift (andinparticularastronglyaperiodicSFT)forcesthegrouptohaveadecidable wordproblem in the class of torsion-freerecursively presentedgroup. The next proposition strengthens the result by deleting the torsion-freeness requirement. Proposition 2.5. Let G be a torsion-free recursively presented group. If G admits a strongly aperiodic effective subshift, then G has decidable word problem. Proof. LetX bethestronglyaperiodiceffectivesubshift. X liftsuptoasubshift Y on AFp. Let R={g|g= λ}. G Note that if ψ(y)=x, then Stab(y)=Stab(x)R=RStab(x). Furthermore, if G is torsion-free,then Stab(x)={λ}, hence for all y ∈Y, Stab(y)=R. Now let g ∈Fp. Let Z ={x|∀t,xgt =xt}={x∈AFp|g ∈Stab(x)}. It is easy to see that Z is effective. Furthermore Y ∩Z =∅ iff g 6= λ. G As there is a semialgorithm to test whether Y ∩Z = ∅, we get that the complement of the word problem is recognizable, hence decidable. Proposition 2.6. Let G be a recursively presented group. If G admits a normally aperiodic effectively closed subshift, then it ad- mits a normally aperiodic effectively closed subshift X where for all x ∈ X, ∩ Stab(hx)=λ. h∈G Proof. Let X be normally aperiodic. The proof is in two steps. In the first step, we will prove that there exists a finite normal subgroup H of G and a nonempty effective subshift Y so that for all x∈Y, ∩ Stab(gx)=H. g∈G LetH ={λ}. Supposethatthereexistsx∈X sothatH (∩ Stab(hx). 0 0 h∈G Then let’s denote H ⊃H the normal subgroup on the right. 1 0 We do the same for H , building progressively a chain of normal subgroups 1 H ...H .... 1 n It is impossible however to obtain an infinite chain this way. Indeed, as for all i, there exists x so that ∩ Stab(gx ) = H , a limit point x of x would i g∈G i i i verify ∩ Stab(gx)⊇∪ H , hence x would be a configurationwith an infinite g∈G i i normal stabilizer, impossible by definition. Hence this process will stop, and we obtain some finite normal subgroup H of G and a point x so that ∩ Stab(hx) = H and no point x has a larger 0 h∈G normal stabilizer. Now let Y = {x ∈ X|∀g ∈ G,h ∈ H,hgx = gx}. Y is nonempty, as it contains x . As H is finite, Y is clearly effectively closed. As H is normal, it is 0 a subshift. Furthermore, for all x∈Y, ∩ Stab(hx)=H. h∈G Nowthesecondstep. TakeZ ={x∈HG|∀g ∈G,h∈H\{λ},x 6=x }. Z hg g isclearlyeffectivelyclosed. AsH isnormal,itisasubshift1. Z isalsononempty: Write G = HI where I is a family of representatives of G/H. Then the point 1 Indeed, let z ∈ Z and t ∈ G. Let g ∈ G and h ∈ H \{λ}. Then (tz)hg = zt−1hg = zt−1htt−1g 6=zt−1g =(tz)g,hencetz∈Z 6 z defined by z = h if g ∈ hI is in Z, hence Z is nonempty2. Furthermore, if g z ∈ Z, then Stab(x)∩H = {λ} 3. As a consequence, Z ×Y is a nonempty subshift for which for all x∈Z×Y, ∩ Stab(hx)={λ}. h∈G Theorem 1. Let G be a recursively presented group. If G admits a normally aperiodic effectively closed subshift, G has decidable word problem. Proof. This is more or less the same proof as before, with one slight difference. LetX bethenormallyaperiodiceffectivelyclosedsubshift. Wemaysuppose by the previous proposition that for all x∈X, ∩ Stab(hx)={λ}. h∈G F X lifts up to a subshift Y on A p with the following property: If y ∈ Y, then ∩h∈FpStab(hy)=R. Now let g ∈ Fp. Let Z = {y|∀h ∈ Fp,ghy = hy} = {y|g ∈ ∩h∈FpStab(hy)}. Z is effective. Furthermore Y ∩Z =∅ iff g 6= λ. G Emptyness is recognizable, hence the complement of the word problem is recognizable, hence decidable. Corollary 2.7. Let G be a recursively presented group that admits a strongly aperiodic SFT. Then G has a decidable word problem. 3 Enumeration degrees In this section, we generalize the previous results to any finitely generated groups, whose presentation might be not recursive. Recall that the word problem of G is the set W(G)={g ∈F |g = λ} p G If G is any f.g. group, there are various ways that a subshift X =S could be L said to be computable in G: • We can enumerate a list of forbidden pseudo-words for S • We can enumerate a list of forbidden pseudo-words for S give an oracle for W(G) • We can enumerate a list of forbidden pseudo-words for S give a list of all elements of W(G) The last two are possibly different: In the last case,we are only given accessto positiveinformations,i.e. theelementsthatareinW(G),notthosethataren’t. Thedefinitionsandresultsbelowinvolvethe notionofenumeration reducib- ility [FR59, Odi99]. Enumeration degrees, and enumeration reducibility, is a notion from com- putability theory that is quite natural in the context of presented groups and subshifts, as it captures (in computable terms) the fact that the only inform- ation we have about these objects are positive (or negative) information: In a 2 Indeed, let g ∈ G and h ∈ H\{λ}. Then zg = k where g ∈ kI for some k ∈ H. But hg∈(hk)I hencezhg =hk6=k=zg. 3 Indeed,forh∈H\{λ},(hx)λ=xh−1 6=xλ,henceh6∈Stab(x). 7 subshift(effectiveornot),weusuallyhavewaystodescribepatternsthatdonot appear,butnoproceduretolistpatternsthatappear. Inapresentedgroup,we haveinformationaboutelements that correspondto the identity element ofthe group, but no easy way to prove that an element is different from the identity. Thisreductionhasbeenusedalreadyinthecontextofgroups[HS88,Chapter 6] or in symbolic dynamics [AS09]. 3.1 Definitions IfAandBaretwosetsofnumbers(orwordsinF ),wesaythatAisenumeration p reducible to B if there exists an algorithm that produces an enumeration of A from any enumeration of B. Formally: Definition 3.1. A is enumeration reducible to B, written A ≤ B, if there e exists a partial computable function f that associates to each (n,i) a finite set D s.t. n∈A ⇐⇒ ∃i,D ⊆B. n,i n,i We willfirstgivehere afew easyfacts,andthen examplesrelevanttogroup theory and symbolic dynamics. Fact 3.2. A is recursively enumerable iff A≤ ∅. e In particular, if A is recursively enumerable, then A≤ B for all B. e A≤ B⊕B iff A is enumerable given B as an oracle. e B⊕B denotes the set {(1,x)|x∈B}∪{(1,x)|x6∈B}. Here are some examples relevant to group theory: Fact 3.3. (Formal version) Let G = hX|Ri be a finitely generated group, with R⊆F and N be the normal subgroup of F generated by R. Then N ≤ R. In p p e particular, if R is finite, then N (hence the word problem over G) is recursively enumerable. (Informalversion)FromapresentationRofagroup,wecanlistallelements thatcorrespondtotheidentityelementofthegroup(butingeneralwecannotlist elements that are not identity of the group). In terms of reducibility, the set of all elements that correspond to the identity is the smallest possible presentation of a group. Indeed g ∈ N iff there exists g ...g ∈ F ,u ...u ∈ R∪ R−1 so that 1 k p 1 k g = g u g−1g u g−1...g u g−1. Given any enumeration of R (and as F is 1 1 1 2 2 2 k k k p enumerable), we can therefore enumerate N. Here are some examples relevant to symbolic dynamics or topology. Fact 3.4. (Formal version) Let S =S be any closed set. Then L(S)≤ L. L e In particular if L is enumerable then L(S) is recursively enumerable. (Informal version) From any description of a closed set in terms of some forbidden words, wemayobtainalistofallwordsthatdonotappear (butusually not of patterns that appear). In terms of reducibility, the set of all words that do not appear is the smallest possible description of a closed set. Subshifts are particular closed sets, so this is also true for subshifts. In particular the set of patterns that do not appear in a SFT (over Z, or F ) is p recursively enumerable. 8 Proof. This is a straightforwardgeneralizationofProp. 1.3 andthe subsequent proof. Letw beanyword,definedoverafinitesetB. LetW bethesetofallwords defined over B that are incompatible with w. Then w ∈L(S) iff S =∅. L∪W Now SL∪W =∅ iff there exists a finite set L′ ⊆L s.t. SL′∪W =∅. Thus, if (F(n,w))n∈N is the computable enumeration of all finite sets of words s.t that S =∅, then w ∈L(S) iff ∃n,F(n,w)⊆L. F(n,w)∪W 3.2 Generalizations Nowweexplainhowthisconceptgivesgeneralizationsoftheprevioustheorems. First, we look at subsets of AFp that are effective given an enumeration of B. This definition is nonstandard: Definition 3.5. A set S ⊆AFp is B-enumeration-effective if S =SL for some set of words L so that L≤ B. e Here are a few examples: • {x∈{0,1}Fp|∀h∈B,xh =1} is B-enumeration effective • {x∈{0,1}Fp|∀g ∈Fp,∀h∈B,xgh =xh} is B-enumeration effective • {x ∈ {0,1}Fp|∀h 6∈ B,xh = 1} is usually not B-enumeration effective. It is B-enumeration effective iff the complement of B is enumeration re- ducible to B. It happens for example whenever the complement of B is enumerable, regardless of the status of B. If we go back to the different ways to define a subshift from a group given at the introduction of this section, they correspond to three different notions of enumeration-effectiveness: • The first one corresponds to ∅-enumeration-effective • The second one corresponds to W(G)⊕W(G)-enumeration-effective • The third one corresponds to W(G)-enumeration-effective The second notion is what is called a G-effective subshift in the vocabulary of [ABS]. Definition3.6. Wewill saythatX ∈AFp isG-enumerationeffectivewhenever X is W(G)-enumeration effective. Proposition 3.7 (Analog of Prop1.7). Let A be an alphabet of size at least 2. Then Per is G-enumeration effective. More precisely, L(Per )≡ W(G). G G e Proposition3.8. IfX,Y aretwoclosedsetsinAF,thenL(X ∩Y)≤ L(X)∪L(Y) p e Proof. X ∩Y =S . L(X)∪L(Y) Corollary 3.9 (AnalogofCor.1.8). If X is an effectively closed set of AG,then L(X)≤ W(G). More generally, if X =SG then L(X)≤ L⊕W(G). e L e F Proof. L(X)=L(SG)=L(S p ∩Per )≤ L∪L(Per )≤ L⊕W(G). L L G e G e 9 Proposition 3.10 (Analog of Prop. 2.3). If X is effectively closed (in par- ≤1 ticular if it is an SFT) then W(G)≤ W(G) e Proof. X≤1 lifts up to a subshift Y of AFp which is G-enumeration effective. By the proof of Prop.2.3, there exists a uniform family w of words so that g g 6=λ iff w ∈L(X). This implies easily that W(G)≤ L(Y). g e Theorem 2 (Analog of Th. 1). If G admits a normally aperiodic effective subshift X, then W(G)≤ W(G). e Proof. From the proof of Th. 1, there exists a G-enumeration effective subshift Y onF ,anda(uniform)familyofeffectivelyclosedsetsX sothatY ∩X =∅ p g g iff g 6=λ. Let (F(n,g))n∈N be a computable enumeration of all finite sets F for which there exists G ⊆ L so that S = ∅ (this can indeed be enumerated as L g F∪G g can be enumerated). Then g 6= λ iff ∃nF(n,g)⊆L(Y), hence W(G)≤ L(Y) G e Hence the existence of a strongly aperiodic SFT implies that the comple- ment of the word problem can be enumerated from the word problem. This is not a vacuous hypothesis: If G is recursively presented (hence W(G) is recurs- ivelyenumerable),thisimplies thatW(G)is alsorecursivelyenumerable,hence recursive. Another way of stating the result is that, for a group having this property, the notion of G-enumeration effectiveness and G-effectiveness coincide. 4 Aperiodic SFTs on monster groups In this sectionwe exhibit examples of aperiodic SFTs on some monster groups. All our examples are trivial and somewhat degenerate. Nevertheless these are aperiodic SFT. Simple groups Our last section introduces a computability obstruction that mustsatisfyallgroupsGthatadmitsanaperiodicSFT:Thecomplementofthe word problem must be enumeration reducible to the word problem. There are a few well known algebraic classes of groups that satisfy this property: In particular, all f.g. simple groups have this property. Proposition 4.1. If G is a f.g. simple group, then G admits a normally aperi- odic SFT Proof. Fix some given nontrivial element a of G. And define X = x∈{0,1,2}G ∀g ∈G,(gx) 6=(gx) a λ (cid:8) (cid:12) (cid:9) Thus X is an SFT. It is easy to see th(cid:12)at X is nonempty. Now let x ∈ X. Then (a−1x) = x 6= x . Thus a−1x 6= x, which means λ a λ the stabilizer of x is not the whole group. A fortiori, the normal stabilizer of x is also not the whole group: ∩ Stab(hx) 6= G. As the left term is a normal h∈G subgroup of G and G is simple, this implies ∩ Stab(hx)={λ}. h∈G TheproofworksverbatimforanygroupGwithnoinfinitenormalsubgroups. 10