Esta es la tercera entrada sobre el mismo tema de las dos anteriores. No se muy bien por qué, la publiqué en inglés y así la republico. La original se publicó e 12/3/2011 y he realizado algunas ediciones mínimas. El objetivo en ésta entrada es mostrar una imagen que ilustra lo que se ha desarrollado en las dos anteriores, con algunas explicaciones adicionales.
I have uploaded a one page slide Power Point presentation which sumarizes graphically the situation I expressed in words in a previous post regarding how I see the asymptotic limit of the distribution of all pairs of generators that generate n!, as n grows.
1. Before showing the graphic two comments:
–along the X axis the degree of all pairs of permutations that generates a given n!.
–Along the Y axis the number of pairs of a given degree that generates the given n!.
2. The graphic / PPT presentation.
Please click on the picture to enlarge.
Reader should note that the shape of the curve is irregular not because this is the way I think it is but due to my poor Power Point drawing ability. My apologies to the reader / viewer for this.
The Power Point presentation can be found here in the following link: Asymptotic shape and structure of the distribution of all pairs of generators that generates n!.
3. Some explanations about the image:
The all easy cases region includes all the smooth cases. As you move along the X axis to the right to get non-isomorphic cases of larger degree you need that at least one of the parameters of the case (order of the permutations, order of the IAS,…) to be of a size that can not be reached with permutations of lower degree and the structural properties of the cases change accordingly, from smooth, to entangled with one generator beeing an involution, then entangled, and finally cycle-entangled. As structural properties change the complexity of cases change accordingly.
The reader may need much more explanation to fully understand this scheme, and the writer would need more time to read all past posts and have a fully coherent description of the scheme (at present I have not fully clear the NP and P region).
To have a more clear view, reader must think as if when you move to the right along the X axis, the size or order of the IAS grow and since the order of the group/graph is always the same for all degrees, n!, there are less and less IAS per case until there is only one IAS of size n!; as there are less and less IASes, structural properties change.
Though I might include some comments more in the round shaped areas or changes, I think the shape and structure of the distribution is probably close to the definite one. However it is unclear what´s the asymptotic behavior of the range under each region: will the “hard part” shrink and the easy part be enlarged or grow asymptotically or not ?
Update 27/03/2011: In a previous post I showed the equation whose solution (in x) expresses the degree frontier between the easy and the hard region (the following equation is just an aproximation):