Towards Efficient Normalizers of Primitive Groups
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Siccha, Sergio
We present the ideas behind an algorithm to compute normalizers of primitive groups with non-regular socle in polynomial time. We highlight a concept we developed called permutation morphisms and present timings for a partial implementation of our algorithm. The corresponding article is a collection of results from the author’s PhD thesis.
 Hello. Welcome to my talk, Towards Efficient Normalizers for Primitive Groups. This is essentially a collection of results from my PhD thesis. And I'm going to introduce quickly what normalizers and primitive groups are, and then I'll talk about the strategy that I use to obtain my results. So for two groups G and M, which are contained in a common over group K, we call the normalizer of G in the group M. The group consisting of all elements of M, which leave G invariant under conjugation. And I denoted conjugation by G to the M. In practice, the algorithm to solve the normalizer problem is partition backtrack, which in the worst case has to iterate over the whole group M. Partition backtrack is implemented in Gap and Magma, for example. The best known theoretical algorithm is by Daniel Wiebking, and it computes for a permutation group G on a set omega. It computes the normalizer of G in the full symmetry group on omega in a simply exponential time that is in time 2 to a linear polynomial in the number of points that omega contains. A group is called primitive, or the other way around. A group is a transitive group is called imprimitive. If we have a non-trivial G invariant partition of omega, by a G invariant non-trivial partition, we mean that if you take a block of the partition, and if you apply G to all elements in the block, then you have to arrive at another block of the partition. If such a partition exists and it is non-trivial, then we call the group imprimitive. If no such partition exists, we call it primitive. Here's a small example. On the right hand side you see a square, and the symmetry group of the square is the dihedral group with eight elements. If you look at rotations or at a rotation 90 degrees, then you notice that the opposing edges always will be mapped to opposing edges. If you rotate this to the left counterclockwise, then 1 and 3 are mapped to 2 and 4 and vice versa. This partition into the sets into the blocks 1, 3 and the blocks 2, 4, block 2, 4 is invariant under this group, so this group is not primitive. Essentially, if you have an imprimitive group, then this means that you can decompose your group into an action on the single blocks, and an action, sorry, moving the blocks around. What did I do? The normalizer problem is hard in general, but for primitive groups it can be solved efficiently. For many primitive groups it can be solved efficiently. Namely, if we have a primitive group given by a generating set X, which has a so-called non-regular socle, I will explain later what that is exactly, then we can compute the normalizer of g in the full symmetric group, or rather a generating set of it, in time linear in the number of generators and polynomial in the number of points that we operate on. This is in contrast to the general algorithm. The best that we know there is, as I already said at the beginning, a simply exponential time. In my PhD thesis, I first designed a theoretical algorithm to do this, and I'm currently working on implementing a practical version of this theoretical algorithm for as many cases as I have. Most parts of this calculation I have shown that they can be done in nearly linear time. I do some analysis of how the group looks like, and then a transformation into a nicer form, and all of this can be done in nearly linear time. It's only the actual normalizer calculation in the end that I reduced to that can only be done in polynomial time. I have restricted myself to the problem of only computing the normalizer in the symmetric group, because, well, if you look for the normalizer of g in another group, m, then you simply take the normalizer in the symmetric group and intersect it with the group m. Intersecting is a completely different problem for primitive groups than the normalizer, than finding normalizing elements. So I did not consider that. There are algorithms that can do that. As I already said, I'm trying to implement as much as possible, and code is available at this repository here, and currently I have implemented my algorithms for the so-called PA type case. I will talk more about that later, say more about that later. One moderate example is I was able to compute with a group of PA type, acting on 527, that is 78,125 points, and I was able to compute the normalizer in the symmetric group for this group, or a random conjugate of this group in roughly 67 seconds. So how did I arrive at that part, at that result? So we heavily use the O'Neill-Scott theorem, which classifies how primitive groups look like, and we use the classification of finite simple groups extensively. So before I can tell you what the O'Neill-Scott theorem is, we quickly need to discuss when two permutation groups are essentially equivalent, or we say permutation isomorphic, namely if for two permutation groups you find both a map, an isomorphism, between the sets that we act on, and an isomorphism between the groups, that are basically compatible with the action of the groups, then we say that this is a permutation isomorphism from G to H, or that the groups G and H are permutation isomorphic. And the compatibility means essentially that you take an element from omega, apply a group element G, and then use F to translate this to a delta, and by this I simply mean the permutation G applied to the element omega, or you first take the element omega, translate it to delta, and then apply the corresponding permutation in H. So if all of this exists and the maps are isomorphisms, then we say that G and H are permutation isomorphic, because we can simply relabel the points and find a group isomorphism which is compatible with the action. Okay, so the classification of primitive groups says the following. First we need to introduce a small tool, namely the Socle of a group, and the Socle of a group is a characteristic subgroup, namely the group generated by all minimal normal subgroups, and we noted Socle of G, Sock G, and it turns out it's actually quite easy to show for primitive groups that Socle must always be characteristically simple. So there exists a simple group T, such that the Socle is isomorphic to T to the L for some integer L, as groups. So what the Oren and Scott theorem tells us, that we, based on what the group theoretic structure looks like, we can actually know explicitly how this Socle, this characteristically simple Socle has to act on the set omega that we're given. And not only that, we also know how the normalizer of the Socle in the symmetric group looks like, and of course since the Socle is characteristic in G, this tells us that G has to live in this group. And the Oren and Scott theorem is a very powerful tool. Many people have used it to answer questions about primitive groups, and one of the reasons why it's so powerful is because, well, essentially you have a characteristically simple Socle, and you can use the Oren and Scott theorem to reduce questions about primitive groups to the simple question that appears in the Socle here. Okay, so the main steps of the algorithm are, let me repeat quickly, we have a primitive group G, and we want to compute the normalizer of the group G in the symmetric group omega, in the full symmetric group. And the main steps now are, well, first we compute this group that the Oren and Scott theorem tells us what it looks like. Why do we do this? Well, the Socle is characteristic in G, and thus the Socle is also normal in the normalizer of G, but this means that the normalizer of G must be contained in the normalizer of the Socle. So we only need to look for elements normalizing G in this group M. And once we have done that, we can look at, well, what the Oren and Scott theorem tells us how that M must look like, and from there we will essentially always see that, well, M can be represented a lot smaller, and we can compute a group of homomorphism from M into a group which acts on a lot lesser points. Yeah, and the reason why we can actually do this step number two is that the non-nibelian Socle, M, if the Socle is non-nibelian, then this M is very closely related to product action-reth products, and I'm going to explain what that is in a second, but the intuition is that these product action-reth products are, well, not very huge groups, but they act on the huge number of points. So in comparison to the number of points, the groups are actually very small, and if you only need to look in this group, well, then looking for the normalizer of G and M is a lot easier than looking for the normalizer of G in the full symmetric group. Okay, so let's recall quickly what a reth product is. We take a group H and a group K acting on L points, and then K acts on H to the L by simply permuting the components, and if we take the semi-direct product, then HvK is simply H to the L with K acting by permuting the components. So if H is itself a permutation group, then we can let the reth product act faithfully in two ways, namely first by the so-called imprimative action, where we act on delta times 1 to L, or by the so-called product action, where we act on tuples, namely of the form delta 2L, and both of these actions are very related because in both cases we take the group H which acts on delta, and we always let the i-th copy of H act on the i-th copy of delta, and we let K permute these copies. So here, for example, in the imprimative action, the i-th copy of H acts on the set delta times i, and in the product action the i-th copy of H acts on the i-th component of delta to the L. Okay, so let us talk, so there are several a lot of Onenscott cases. The version of Onenscott that I use has eight different types of primitive groups, and the simplest non-trivial one, or the easiest non-trivial one, is the PA type, because it is directly related to reth products, to reth products of product action, and the other ones are a little bit more complicated, but essentially the same ideas work there too, with some adaption to the cases themselves. Okay, so the type PA type, or the name PA type stands for Product Action Type, we say that a group G is of the product action type, or of type PA, if there exists an Orbilian Simple Group T, and a permutation isomorphism which maps the set omega to the set delta to the L, and G to some group H, which is not further specified, but the important thing is that the Soccal of G has to be mapped under the isomorphism phi to T to the L, which acts component-wise on the set delta to the L. So this is really important, we know that the Soccal is characteristically simple, which means that it is isomorphic to T to the L as a group, but here in the PA case, PA type, we really know that T to the L acts component-wise on delta to the L. And essentially what the Ornans-Cott theorem then says, tells us, is that if we are given a primitive group where the Soccal is actually equal to T to the L, not only is it a permutation isomorphic, but equal, then we can compute the normalizer of that Soccal, we call it M as usual, simply by taking the normalizer of the simple group T, and taking the product action with S to the L. So this again acts on delta to the L, and this is the normalizer of the Soccal. And now one thing that happens, which makes this this normalizer calculation even easier for primitive groups, is that, well we know that the Soccal of G always is a subgroup of G, and we can look at this fact factor group here, the normalizer of the Soccal, module of the Soccal, and if we look at this here, then this breathe product contains T to the L, or actually the normalizer of T to the L, with the SL permuting the components around, and if you factor out the T, well then you get something that only induces outer automorphisms on T, and that's breathed with the symmetric group on L points. And as we know, A, this group SL only acts on well on the components of which are a lot less than are there actually points in delta to the L, and this here is the auto-automobile group of a simple group about which we know from the classification that these are always very small. So actually we're talking about looking, searching in this group here, and yeah, so the normalizer for primitive groups, the normalizer problem for primitive groups starts to look easier and easier by the second. So what we can actually do, what also follows from the classification, is that we can compute if we are, this is important, if we are given the Soccal in this form that is T to the L, acting component-wise, then we can read off T, and then we can use the classification to compute the normalizer of T in polynomial time, and then we can simply write down this group in polynomial time. So that we can do this does not follow directly from the classification, rather this is work by Kantor, who showed that in polynomial time you can recognize finite simple groups, and if you can recognize them you can also simply write down the automorphisms, all of their outer automorphisms, and you can use these to compute the normalizer here. And what I do in step two is that I take this product action with product and simply transform it into the imprimative action of the read product, that already makes the set that we work on a lot smaller, and thus also makes the normalizer calculation itself a lot quicker. So for the result that I showed you earlier, the theoretical one, where I said that I can compute the normalizer in polynomial time, for that I can go a little bit further, but in the practical algorithm it's actually not necessary to go this far, because this is already more than enough. In the theoretical version I can make this a little bit better, namely I can say, okay I take d to be the number of elements in delta, and then by result by Goudalnyk, Marrota and Piber, I get that the outer automorphism group is less than three times the logarithm of d. And what we get directly is that l is the logarithm of n to the base d, where n is the number of points that we act on. And if you put this together, well if we compute the, essentially I compute the regular action of this thing on itself, this group on itself, and then compute the imprimative read product, and if you put all of this together, I get this. At first I take my group m, my normalizer of the Soco, I factor out the Soco and arrive at a subgroup of this group, outer automorphism of t, read SL. I compute the right regular action of this and transform this back into an imprimative read product, and then I get to 3 log d times log d of n points, and then this log d and this d in the index here, cancels each other out, essentially, and I arrive at 3 times log n points. And here I can apply the algorithm by Daniel Wiebking that I mentioned in the beginning, and if I take a simply exponential time algorithm and apply it to a logarithmic number of points, then I get a polynomial time algorithm. But again, a, this is more than enough, and b, passing to this and then using Wiebking's algorithm is an entirely theoretical argument, because Daniel Wiebking's algorithm is a theoretical algorithm. Okay, so the main problem there is that if we're given an arbitrary group g, then the Soco can have any form. It can be essentially a completely random conjugate of this nice component-wise action, so that we cannot simply read off the component-wise action. So what we need to do is we make, we need to somehow figure out how the Socle of our arbitrary group g corresponds to this nice component-wise acting t to the l. And essentially what I've done for that is I have found projections, or I compute projections from the Socle to the group t, such that, well, if I take the product of these projections, then I arrive exactly at t to the l. But now of course the problem is, I can, it's not enough to simply take a group homomorphism, because you already know that the Socle of g is isomorphic to t to the l as a group. We somehow need to make a permutation isomorphism out of that. And what I did for that is I came up with the notion of permutation morphisms, so I can say that these projections are permutation morphisms, and the direct product of this permutation morphisms will then yield a permutation isomorphism in the original sense of the permutation isomorphism definition. Okay, so I'm quickly going to tell you what permutation morphisms are about. So the definition is exactly the same as with permutation isomorphisms, but I simply drop the conditions that the maps f and phi need to be isomorphisms. There can be any maps now. And this compatibility relation stays exactly the same. And what I've shown is that if I take the permutation groups together with this permutation morphisms, and I say that the composition of permutation morphisms is by simply composing the domain maps and the group maps, then this forms a category. And what I've also shown is that since we want to talk about direct products or about products of permutation groups, that this category admits finite products. Okay, and these permutation morphisms turn out to have a few nice properties, I would say. And one of them is the following. If you take a map, a group g, and a map, an epimorphism, a surjective map f from omega to delta, then there exists at most one group H acting on delta, permuting delta, and at most one group epimorphism from g to 8, such that this pair is a permutation isomorphism. And there actually exists such a group and a group epimorphism, if and only if, well, this set of fibers of delta under the map f is g invariant. So think again of the definition of imprimative groups. If such a if such a group g is transitive, then this says, for example, that such a permutation epimorphism can only exist if this here is a block system of g and if the group g is imprimative. Unless, of course, this is an isomorphism and this is, for example, unless, for example, this is an isomorphism and this is then a trivial partition. Okay, and what this tells us is that it should be enough to figure out what the product structure of omega itself is, and once you have figured out what the product structure of omega is in our PA type example, then the product structure of the circle should essentially reveal itself without any further work. That's the idea here. So I've brought a small example. We take a billion group with four elements generated by these, by A and B, the permutations A and B. We act on four points and now we can look at the following map. We map, essentially imagine that you're mapping to the left, your projection to the left. So one and two both get mapped to the point one and three and four both get mapped to the point three and we call this map P1. Now by the argument from before, by the lemma from before, the fibers are one and two and three and four and these are invariant under the group V. This is essentially a block system for the group V. So we know that the romastics is a unique group epimorphism from G to a group H, which turns all of this in permutation into a permutation epimorphism. Namely, well how does A act? It acts by permuting one and two and three and four, but if you're projecting to the left, then permuting one and two doesn't do anything anymore, neither does this, so we get the identity on one and three. And with B it is the other way around, actually, because we are permuting one and three and permuting two and four and if we map this to the left, then we get the permutation one and three. So essentially, pi1 is this map and P1 and pi1 together form a permutation epimorphism of V. We can do the same game by just projecting to the top and then we get an analogous map, an analogous permutation epimorphism P2 and if we take the direct product of these two permutation epimorphisms, then we actually get an isomorphism from V into the permutation group on one three, permuting one three and the permutation group on the set one two generated by this transposition. Okay, and this is already basically everything that I wanted to tell you about permutation morphisms. The idea how to compute these product decompositions for general PA type groups is essentially the following. If we have such a group that acts by permuting, by acts essentially on the components of this thing here, then you do not, you can reconstruct this maps essentially, the projections to one three or the projection to one two by taking orbits of normal subgroups. So A is a normal subgroup of V, V is a billion or A generates a normal subgroup of V and if we take orbits under this normal subgroup, then this will yield a block system for V and the block system is a G invariant partition or in this case a V invariant partition. And so if we take the map P1 prime and simply map each element to its orbit under this normal subgroup generated by A, then we get the same map as before or the same map as essentially the same map as P1 because well one and two are mapped to the same point and three and four are mapped to the same point or the same value. And you can do all of this for PA type groups and this is how you construct the, this is how you figure out how you reconstruct the product structure of the Sockle of a PA type group and if you can do this to recap, you can use the Oren Scott theorem and the classification of finite simple groups to compute the normalizer of the Sockle and then we have essentially done the hardest part of the work because after that we only need to translate the product action with product into an primitive free product and then calculating the normalizer is almost trivial. That's it from me. Thank you.
 Hello. Welcome to my talk, Towards Efficient Normalizers for Primitive Groups.  This is essentially a collection of results from my PhD thesis.  And I'm going to introduce quickly what normalizers and primitive groups are,  and then I'll talk about the strategy that I use to obtain my results.  So for two groups G and M,  which are contained in a common over group K, we call the normalizer of  G in the group M. The group consisting of all elements of M,  which leave G invariant under conjugation.  And I denoted conjugation by G to the M.  In practice, the algorithm to solve the normalizer problem is partition backtrack,  which in the worst case has to iterate over the whole group M.  Partition backtrack is implemented in Gap and Magma, for example.  The best known theoretical algorithm is by Daniel Wiebking,  and it computes for a permutation group G on a set omega.  It computes the normalizer of G in the full symmetry group on omega  in a simply exponential time that is in time 2 to a linear polynomial  in the number of points that omega contains.  A group is called primitive, or the other way around.  A group is a transitive group is called imprimitive.  If we have a non-trivial G invariant partition of omega,  by a G invariant non-trivial partition, we mean that if you take a block of the partition,  and if you apply G to all elements in the block,  then you have to arrive at another block of the partition.  If such a partition exists and it is non-trivial,  then we call the group imprimitive.  If no such partition exists, we call it primitive.  Here's a small example.  On the right hand side you see a square,  and the symmetry group of the square is the dihedral group with eight elements.  If you look at rotations or at a rotation 90 degrees,  then you notice that the opposing edges always will be mapped to opposing edges.  If you rotate this to the left counterclockwise,  then 1 and 3 are mapped to 2 and 4 and vice versa.  This partition into the sets into the blocks 1, 3 and the blocks 2, 4, block 2, 4  is invariant under this group, so this group is not primitive.  Essentially, if you have an imprimitive group,  then this means that you can decompose your group into an action on the single blocks,  and an action, sorry, moving the blocks around.  What did I do?  The normalizer problem is hard in general,  but for primitive groups it can be solved efficiently.  For many primitive groups it can be solved efficiently.  Namely, if we have a primitive group given by a generating set X,  which has a so-called non-regular socle, I will explain later what that is exactly,  then we can compute the normalizer of g in the full symmetric group,  or rather a generating set of it, in time linear in the number of generators  and polynomial in the number of points that we operate on.  This is in contrast to the general algorithm.  The best that we know there is, as I already said at the beginning,  a simply exponential time.  In my PhD thesis, I first designed a theoretical algorithm to do this,  and I'm currently working on implementing a practical version of this  theoretical algorithm for as many cases as I have.  Most parts of this calculation I have shown that they can be done  in nearly linear time. I do some analysis of how the group looks  like, and then a transformation into a nicer form,  and all of this can be done in nearly linear time.  It's only the actual normalizer calculation in the end that I  reduced to that can only be done in polynomial time.  I have restricted myself to the problem of only computing the normalizer  in the symmetric group, because, well, if you look for the  normalizer of g in another group, m, then you simply take the normalizer  in the symmetric group and intersect it with the group m.  Intersecting is a completely different problem for primitive groups  than the normalizer, than finding normalizing elements.  So I did not consider that. There are algorithms that can do that.  As I already said, I'm trying to implement as much as possible,  and code is available at this repository here,  and currently I have implemented my algorithms for the so-called  PA type case. I will talk more about that later,  say more about that later.  One moderate example is I was able to compute with a group of PA type,  acting on 527, that is 78,125 points, and I was able to compute the  normalizer in the symmetric group for this group, or a random  conjugate of this group in roughly 67 seconds.  So how did I arrive at that part, at that result?  So we heavily use the O'Neill-Scott theorem, which  classifies how primitive groups look like,  and we use the classification of finite simple groups extensively.  So before I can tell you what the O'Neill-Scott theorem is,  we quickly need to discuss when two permutation groups  are essentially equivalent, or we say permutation isomorphic,  namely if for two permutation groups you find both a map, an isomorphism,  between the sets that we act on, and an isomorphism between the groups,  that are basically compatible with the action  of the groups, then we say that this is a permutation isomorphism from G to H,  or that the groups G and H are permutation isomorphic.  And the compatibility means essentially that you take an element  from omega, apply a group element G, and then use F to translate this to a  delta, and by this I simply mean the permutation G  applied to the element omega, or you first take the element omega,  translate it to delta, and then apply the corresponding permutation in H.  So if all of this exists and the maps are isomorphisms,  then we say that G and H are permutation isomorphic,  because we can simply relabel the points and  find a group isomorphism which is compatible with the action.  Okay, so the classification of primitive groups says the following.  First we need to introduce a small tool, namely the Socle of a group,  and the Socle of a group is a characteristic subgroup, namely the  group generated by all minimal normal subgroups,  and we noted Socle of G, Sock G, and it turns out it's actually quite easy to  show for primitive groups that Socle must always be  characteristically simple. So there exists a simple group T,  such that the Socle is isomorphic to T to the L for some integer L,  as groups. So what the Oren and Scott theorem tells us,  that we, based on what the group theoretic structure looks like,  we can actually know explicitly how this  Socle, this characteristically simple Socle has to act on the set omega  that we're given. And not only that, we also know  how the normalizer of the Socle in the symmetric group looks like,  and of course since the Socle is characteristic in G,  this tells us that G has to live in this group.  And the Oren and Scott theorem is a very powerful tool. Many people have used it  to answer questions about primitive groups, and  one of the reasons why it's so powerful is because,  well, essentially you have a characteristically simple Socle,  and you can use the Oren and Scott theorem to  reduce questions about primitive groups to  the simple question that appears in the Socle here.  Okay, so the main steps of the algorithm are,  let me repeat quickly, we have a primitive group G, and we want to compute  the normalizer of the group G in the symmetric group omega,  in the full symmetric group. And the main steps now are, well,  first we compute this group that the Oren and Scott theorem tells us what it  looks like. Why do we do this? Well, the Socle is  characteristic in G, and thus the Socle is also normal in the normalizer of G,  but this means that the normalizer of G must be contained in the  normalizer of the Socle. So we only need to look for  elements normalizing G in this group M. And once we have done that,  we can look at, well, what the Oren and Scott theorem tells us  how that M must look like, and from there we will essentially always see that,  well, M can be represented a lot smaller, and we can compute a group of  homomorphism from M into a group which acts on a lot  lesser points.  Yeah, and the reason why we can actually do this step number two  is that the non-nibelian Socle, M, if the Socle is non-nibelian,  then this M is very closely related to product action-reth products,  and I'm going to explain what that is in a second, but the intuition is that  these product action-reth products are, well, not very huge groups, but they act  on the huge number of points. So in comparison to the number of points,  the groups are actually very small, and if you only need to look in this group,  well, then looking for the normalizer of G and M is a lot easier than looking for  the normalizer of G in the full symmetric group.  Okay, so let's recall quickly what a reth product is.  We take a group H and a group K acting on L points,  and then K acts on H to the L by simply permuting the components,  and if we take the semi-direct product, then HvK is simply H to the L  with K acting by permuting the components.  So if H is itself a permutation group, then we can let the reth product act  faithfully in two ways, namely first by the so-called imprimative action,  where we act on delta times 1 to L, or by the so-called product action,  where we act on tuples, namely of the form delta 2L,  and both of these actions are very related because  in both cases we take the group H which acts on delta, and we always let  the i-th copy of H act on the i-th copy of delta,  and we let K permute these copies.  So here, for example, in the imprimative action,  the i-th copy of H acts on the set delta times  i, and in the product action the i-th copy of H acts on the i-th component  of delta to the L.  Okay, so let us talk, so there are several  a lot of Onenscott cases. The version of Onenscott that I use has  eight different types of primitive groups, and  the simplest non-trivial one, or the easiest non-trivial one, is the PA  type, because it is directly related to reth products, to reth products of  product action, and the other ones are a little bit more complicated, but  essentially the same ideas work there too,  with some adaption to the cases themselves.  Okay, so the type PA type, or the name PA type stands for Product Action  Type, we say that a group G is of the product action type, or of  type PA, if there exists an Orbilian Simple Group T,  and a permutation isomorphism which maps the set omega  to the set delta to the L, and G to some group H,  which is not further specified, but the important thing is that  the Soccal of G has to be mapped under the isomorphism  phi to T to the L, which acts  component-wise on the set delta to the L. So this is really important,  we know that the Soccal is characteristically simple,  which means that it is isomorphic to T to the L as a group,  but here in the PA case, PA type, we really know  that T to the L acts component-wise on delta to the L.  And essentially what the Ornans-Cott theorem then says, tells us,  is that if we are given a primitive group where the Soccal is actually equal  to T to the L, not only is it a permutation isomorphic, but equal,  then we can compute the normalizer of that Soccal,  we call it M as usual, simply by taking the normalizer of the  simple group T, and  taking the product action with S to the L. So this again  acts on delta to the L, and this is the normalizer  of the Soccal. And now one thing that happens, which makes this  this normalizer calculation even easier for primitive groups,  is that, well we know that the Soccal of G always is a subgroup of G,  and we can look at this fact factor group here,  the normalizer of the Soccal, module of the Soccal,  and if we look at this here, then this breathe product contains T to the L,  or actually the normalizer of T to the L,  with the SL permuting the components around,  and if you factor out the T, well then you get something that  only induces outer automorphisms on T,  and that's breathed with the symmetric group on L points.  And as we know, A, this group SL only acts on  well on the components of which are a lot less than  are there actually points in delta to the L, and this here is the auto-automobile  group of a simple group about which we know from the  classification that these are always very small.  So actually we're talking about looking, searching in this group here,  and yeah, so the normalizer for primitive groups,  the normalizer problem for primitive groups starts to look easier and easier  by the second.  So what we can actually do, what also follows  from the classification, is that we can compute if we are,  this is important, if we are given the Soccal in this form that is T to the L,  acting component-wise, then we can read off T,  and then we can use the classification to compute the normalizer of T  in polynomial time, and then we can simply write down this group in polynomial  time. So that we can do this does not follow  directly from the classification, rather this is work by Kantor,  who showed that in polynomial time you can recognize  finite simple groups, and if you can recognize them you can also simply  write down the automorphisms, all of their outer automorphisms, and you can  use these to compute the normalizer here. And what I do in step two is that I take  this product action with product and simply transform it into the  imprimative action of the read product,  that already makes the set that we work on a lot smaller, and thus also  makes the normalizer calculation itself a lot quicker.  So for the result that I showed you earlier, the theoretical one, where I said  that I can compute the normalizer in polynomial time,  for that I can go a little bit further, but in the practical algorithm it's  actually not necessary to go this far, because this is already  more than enough. In the theoretical version I can make  this a little bit better, namely I can say, okay I take d to be the number of  elements in delta, and then by result by Goudalnyk,  Marrota and Piber, I get that the outer  automorphism group is less than three times the logarithm of d.  And what we get directly is that l is the logarithm of n  to the base d, where n is the number of points that we act on.  And if you put this together, well if we compute the, essentially I compute  the regular action of this thing on itself, this group on itself,  and then compute the imprimative read product, and if you put all of this  together, I get this. At first I take my group m, my normalizer  of the Soco, I factor out the Soco and arrive  at a subgroup of this group, outer automorphism of t,  read SL. I compute the right regular action of this  and transform this back into an imprimative read product,  and then I get to 3 log d times log d of n points, and then this log d  and this d in the index here, cancels each other out, essentially,  and I arrive at 3 times log n points.  And here I can apply the algorithm by Daniel Wiebking that I mentioned in the  beginning, and if I take a simply exponential time  algorithm and apply it to a logarithmic number of points,  then I get a polynomial time algorithm. But again,  a, this is more than enough, and b, passing to this and then using  Wiebking's algorithm is an entirely theoretical  argument, because Daniel Wiebking's algorithm is a theoretical algorithm.  Okay, so the main problem there is that if we're given an arbitrary group g,  then the Soco can have any form. It can be essentially a completely  random conjugate of this nice component-wise action,  so that we cannot simply read off the component-wise action.  So what we need to do is we make, we need to somehow figure out how  the Socle of our arbitrary group g corresponds to this nice  component-wise acting t to the l. And essentially what I've done  for that is I have found projections, or I compute  projections from the Socle to the group t, such that, well, if I  take the product of these projections, then I arrive exactly at t to the l.  But now of course the problem is, I can, it's not enough to simply take a  group homomorphism, because you already know that the Socle of g  is isomorphic to t to the l as a group. We somehow need to  make a permutation isomorphism out of that. And what I did for that is I  came up with the notion of permutation morphisms, so I can say  that these projections are permutation morphisms,  and the direct product of this permutation morphisms will then  yield a permutation isomorphism in the original sense of the permutation  isomorphism definition. Okay, so I'm quickly going to tell you  what permutation morphisms are about.  So the definition is exactly the same as with permutation isomorphisms,  but I simply drop the conditions that the maps f and phi  need to be isomorphisms. There can be any maps now.  And this compatibility relation stays exactly the same.  And what I've shown is that if I take the permutation groups  together with this permutation morphisms, and I say that the  composition of permutation morphisms is by simply composing the  domain maps and the group maps, then this forms a category.  And what I've also shown is that since we want to talk about direct  products or about products of permutation groups,  that this category admits finite products.  Okay, and these permutation morphisms turn out to have  a few nice properties, I would say. And one of them is the following.  If you take a map, a group g, and a map, an epimorphism, a  surjective map f from omega to delta, then there exists at most one  group H acting on delta, permuting delta, and at most one group epimorphism  from g to 8, such that this pair is a permutation isomorphism.  And there actually exists such a group and a group epimorphism,  if and only if, well, this set of fibers of  delta under the map f is g invariant. So think again of the  definition of imprimative groups. If such a  if such a group g is transitive, then this says, for example, that such  a permutation epimorphism can only exist if this here is a block system of g  and if the group g is imprimative. Unless, of course, this is an isomorphism  and this is, for example, unless, for example, this is an isomorphism and this  is then a trivial partition.  Okay, and what this tells us is that it should be enough  to figure out what the product structure of omega itself is,  and once you have figured out what the product structure of  omega is in our PA type example, then the product structure of  the circle should essentially reveal itself without any further  work. That's the idea here.  So I've brought a small example. We take  a billion group with four elements generated by these,  by A and B, the permutations A and B. We act on four points  and now we can look at the following map.  We map, essentially imagine that you're mapping to the left,  your projection to the left. So one and two both get mapped to the  point one and three and four both get mapped to the point three and we call  this map P1.  Now by the argument from before, by the lemma from before,  the fibers are one and two and three and four and these are  invariant under the group V. This is essentially a block system for the group V.  So we know that the romastics is a unique group  epimorphism from G to a group H, which turns all of this  in permutation into a permutation epimorphism. Namely, well how does A act?  It acts by permuting one and two and three and four, but if you're projecting  to the left, then permuting one and two doesn't do  anything anymore, neither does this, so we get the identity on one and three.  And with B it is the other way around, actually, because we are  permuting one and three and permuting two and four and if we map this to the  left, then we get the permutation one and three.  So essentially, pi1 is this map and P1 and pi1 together form a  permutation epimorphism of V. We can do the same game by just  projecting to the top and then we get an analogous map, an analogous  permutation epimorphism P2 and if we take the direct product of  these two permutation epimorphisms, then we actually get an isomorphism from  V into the permutation group on one three,  permuting one three and the permutation group on the set one two  generated by this transposition.  Okay, and this is already  basically everything that I wanted to tell you about permutation morphisms.  The idea how to compute these product decompositions for  general PA type groups is essentially the following.  If we have such a group that acts  by permuting, by acts essentially on the components of this thing here,  then you do not, you can reconstruct this maps  essentially, the projections to one three or the projection to one two  by taking orbits of normal subgroups. So A is a normal subgroup of V,  V is a billion or A generates a normal subgroup of V  and if we take orbits under this normal subgroup, then this will yield a block  system for V and the block system is a G invariant partition  or in this case a V invariant partition.  And so if we take the map P1 prime and simply map each element  to its orbit under this normal subgroup generated by A,  then we get the same map as before or the same map as  essentially the same map as P1 because well one and two are mapped to the same  point and three and four are mapped to the  same point or the same value.  And you can do all of this for PA type groups  and this is how you construct the,  this is how you figure out how you reconstruct the product structure  of the Sockle of a PA type group and if you can do this  to recap, you can use the Oren Scott theorem  and the classification of finite simple groups to compute the normalizer of the  Sockle and then we have  essentially done the hardest part of the work because after that we only need to  translate the product action with product into an primitive  free product and then calculating the normalizer is almost trivial.  That's it from me. Thank you.
2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_0_287.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_288_503.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_504_1511.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_1512_1559.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_1560_2075.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_2076_4499.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_4500_4547.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_4548_4679.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_4680_7367.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_7368_8423.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_8424_8855.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_8856_9059.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_9060_9251.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_9252_9323.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_9324_9455.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_9456_9839.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_9840_12731.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_12732_13907.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_13908_18815.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_18816_19679.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_19680_24191.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_24192_27695.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_27696_33359.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_33360_34991.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_34992_35135.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_35136_35267.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_35268_35387.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_35388_35555.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_35556_35735.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_35736_35783.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_35784_35831.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_35832_35951.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_35952_36371.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_36372_37223.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_37224_39635.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_39636_39695.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_39696_40271.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_40272_47543.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_47544_47651.png 2020-ICMS-Siccha-Towards-efficient-normalizers-for-primitive-groups_47652_47675.png