Shape and structure of the distribution of all pairs of generators of any degree that generates n!.

This is a research post tha interrupts the market oriented posts of last months. Also this is posibly the last in some time, at least the last research one.

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.

Before showing the graphic several 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!. 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. 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 cases, 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 extend asymptotically or not ?

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!.

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):


I could reduce this equation to 

Solve[n*Log[n]*n*Log[n]-(n+x)*Log[n+x]==0, x] (not completely sure if the reduction is correct),

but couldn´t go any further in finding the value for x, so I have solved it numerically for some values in order to check how this easy/hard frontier degree (let´s call it EHD) grows with the degree of the generators of n!. From the numerical results, if my calculations are not wrong, it is clear that the difference within succesive EHDs, that is is much smaller and grows more slowly than the difference between [(n+1)!- n], at least for degrees lower than 1000. That means that possibly, as n grows, there will be a larger and larger range of hard degrees, though possibly for each possible degree very few cases. There still remain to be prooved that the cases in the hard region scale (exist for every n), and the density question.

Update 15/04/2011:

For every distribution corresponding to groups of order n!, n!/2…the abelian cases (direct product of 2 cycles and the so called 2-circulants) of this order are in a region in the most right part of the distribution. As we know abelian cases are the easier and the less abundant since commutativity is quite restrictive as property. For those cases linear algorithms are known for the normal representation (graph given as input).   






Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de

Estás comentando usando tu cuenta de Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )


Conectando a %s

A %d blogueros les gusta esto: