Algoritmica y complejidad computacional. Algunos resultados sobre permutaciones.

Disclaimer. Esta entrada se ha escrito en los días 13 y 14 de marzo de 2016. La parte dónde comentamos sobre resultados de otros autores, más  el día 13; la parte más de “investigación” propia o en la que comentamos sobre nuestra propia investigación más el día 14. Recordamos una vez, con una imagen más lo que dijo Donald Knuth, uno de los padres de la informática sobre el problema que hemos estudiado y algunos de cuyos resultados estamos intentando patentar en EEUU desde hace años, con grandes dificultades en la concesión, que se deben a motivos que desconocemos, pues incluso en un mundo post Alice Corp, se deberían de poder patentar.        

Ignacio Reneses. Knuth TAOCP.

Y recordamos lo que ha comentado un investigador recientemente al respecto, investigador que utilizando uno de los pasos que quiero patentar ha dado respuesta a uno de los problemas “abiertos” en digrafos de Cayley Bigenerados:

The Hamiltonicity of G(n) was first considered by Nijenhuis and Wilf (Exercise 6 in [5]). A general condition by Rankin [7] forbids Hamilton cycles in G(n) for even n ≥ 4 (see Swan for a simplified proof [11]). Determining if Hamilton cycles exist for odd n was given a difficulty rating of 48/50 by Knuth, making it one of the hardest in The Art of Computer Programming (Problem 71 in Section 7.2.1.2 [4]).

.  

Si mis resultados aportan tanta luz a todos los casos posibles (todos los pares posibles) del problema de recorridos hamiltonianos (ciclos y caminos) en Digrafos de Cayley bigenerados, siendo un problema con una de reputación de ser tan complicado, incluso si hablamos de un solo caso, de un solo par, ¿ por que no se ha concedido la patente para los pasos solicitados directamente y está costando 8 años de tramitaciones ?. ¿ Por qué tengo, a lo mejor (esta semana saldremos de dudas)  que volver a explicar esto una vez más oficialmente al examinador pagando, seguramente, otra importante cantidad a mi agente de patentes en EEUU (no me quejo por ello; hacen bien su trabajo) ?. ¿ Por qué un problema que es tan complicado para uno de los padres de la informática (y para cualquiera que intente abordarlo sin las técnicas de la patente) no lo es para la USPTO ? ¿ Sólo porque la solución es sencilla de programar ? 

Fin de disclaimer.

Quería reflejar en esta entrada, muy brevemente,

–en el primer punto algunos resultados sobre la teoría estadística de permutaciones (propiedades de una sola permutación elegida aleatoriamente en un grupo dado, en general Sn) y algunos problemas de la teoría estadística de permutaciones (propiedades de dos permutaciones, relacionados con la segunda patente, con nuestra propia investigación) que nos gustaría ver resueltos (en algunos puntos esbozamos soluciones). En esta parte seguramente nos repetimos, pues a medida que la voy escribiendo voy acordándome que igual hay una entrada anterior de contenido similar (en cuanto a algunas preguntas; la novedad de esta entrada serían las respuestas): 8 años, que es lo que están tardando en tramitar la USPTO mis solicitudes dan para olvidar.

–en el segundo punto, la importancia de la representación de grupos de permutaciones y en el tercero una simple curiosidad, la relación del problema del Sudoku generalizado con el problema de encontrar ciclos hamiltonianos en grafos generales.

1.Teoría estadística de permutaciones: propiedades de una sola permutación.

En general la teoría estadística de permutaciones se refiere a las propiedades que podemos esperar que tenga una sola permutaciónen general elegida de manera aleatoria.

Como el lector sabe, en el resultado de la patente nos hemos interesado más en identificar determinadas propiedades que puedan tener pares de permutaciones, y sus consecuencias de cara a la solución del problema de recorridos hamiltonianos. Como veremos ya se ha trabajado bastante también en problemas relativos a pares de permutaciones (por ejemplo el resultado de Dixon, sobre el que hablaremos más adelante).

Empezamos con el artículo relevante de wikipedia que

nos hace ver que es las estadísticas asociadas a una permutación aleatoria es un tema muy trabajado. El artículo es interesante pero parece poco sistemático. Me pregunto  si hay algún survey reciente sobre ello con una carácter más sistemático.

Hace unos meses vi este artículo en el que hablan de algunos resultados muy relevantes para el tema de la  patente.

Título. Identifying long cycles in finite alternating and symmetric groups acting on subsets

Extracto.

In a seminal collection of papers, Erdös and Turán initiated the study of asymptotic behaviour of the proportions of various kinds of elements in permutation groups. For example, they showed [4, 5] that for n large enough, most elements in the symmetric group Sn of degree n have order n^(1/2 +o(1)) log(n).

In the same vein Warlimont [13] proved that the conditional probability that a random element g in Sn is an n-cycle, given that g^n = 1, is 1 − O(n −1 ). Applied algorithmically, Warlimont’s result is used to conclude, from the fact that the nth power of a ‘hidden’ permutation g ∈ Sn is the identity, that g is almost certainly an n-cycle. 

Realmente no entiendo muy bien de momento el resultado de Warlimont. Con respecto al resultado de Erdos-Turan, (que tampoco entiendo bien de momento; la notación) que es el que más me ha llamado la atención, me interesa saber como crece esta función en relación a n! y a n!/2. Relevante para determinar si asintóticamente la mayoría de los Digrafos de Cayley Bigenerados son smooth.

Nota.

Los artículos citados son:

[4] P. Erdős, and P. Turán, ‘On some problems of a statistical group-theory. I’, Wahrscheinlichkeitstheorie Verw. Gebiete, 4 (1965), 175–186.

En este primer  artículo plantean el problema de la teoría estadística de grupos con toda generalidad, incluyendo las dos subteorías sobre las que hemos hablado: propiedades de una permutación y propiedades de dos permutaciones.

Comentan sobre la cota superior de Landau al orden de una permutación y comentan sobre cuantas permutaciones de orden n pueda haber en todo Sn concluyendo que hay (n-1) !, que son bastantes (ellos dicen “P´s of order as low as n are many“).

[5] P. Erdős, and P. Turán, ‘On some problems of a statistical group-theory. III’, Acta Math. Acad. Sci. Hungar. 18 (1967), 309–320.

Tras el trabajo pionero de Erdos-Turan su resultado se fue refinando:

THE EXPECTED ORDER OF A RANDOM PERMUTATION WILLIAM M. Y. GOH AND ERIC SCHMUTZ

Aquí expresan el orden de una permutación típica de una manera más clara:

If a is a permutation on n letters, let N subindice n {a) be the order of a as a group element. For a typical permutation, N subindice n {a} is about n^log n/2

Realmente ahora  mismo no sabría derivar esta fórmula de la dada en el artículo original, es decir de n^(1/2 +o(1)) log(n)

Y en este libro nos dan otra que no copiamos por  su complejidad.

En fin, luego hablan de la media, digamos de Un del orden de un elemento  de Sn. Si Erdos y Turan nos daban una fórmula de tipo Big O, es decir Erdos and Turan determined that log Un = O(Raiz cuadrada (n/ log n)),  estos autores dan una fórmula asintotica, es decir con una constante que incluso hacen expícita (la omitimos por su complejidad; tampoco el lector la comprendería seguramente).

THE AVERAGE ORDER OF A PERMUTATION. Richard Stong

Y este artículo hace un repaso de todos los avances:

Paul Erdős’s results and influence in the theory of integer partitions Mihály Szalay

Queda claro que la media del orden de una permutación de Sn es superior al orden de una permutación típica (es decir de aquella que se extraería al azar de manera uniforme), debido a que para todo Sn hay algunas (pocas) permutaciones que se aproximan a la cota de Landau. Esto eleva la  media. El último paper citado nos da una fórmula más ajustada.

This result was sharpened by Schmutz [6], and later by Goh and Schmutz [4] to show that log µn ∼ C * (Raiz cuadrada [n/ log n]), for an explicit constant C. The purpose of this note is to show that log µn = C* (Raiz cuadrada[n / log n] + O (n(√n log log n) / log n), where C = 2.99047 … is an explicit constant defined below. 

[13] Richard Warlimont, Über die Anzahl der Lösungen von x n = 1 in der symmetrischen Gruppe Sn’, Arch. Math. 30 (1978), 591–594.

Realmente la teoría estadística de una permutación está muy relacionada con la teoría estadística de particiones.

En definitiva el orden típico (Erdos-Turan) es inferior al orden medio (Goh-Schmutz) y obviamente éste es inferior al orden máximo (cota de Landau). A nuestros efectos nos interesa sobre todo el orden típico.

Por otra parte el resultado de Dixon sobre pares de permutaciones de Sn elegidas al azar que generan Sn, casi todas, resultado sobre el que tanto hemos hablado en el blog, puede considerarse un resultado de la teoría estadística de grupos, la parte sobre pares de permutaciones.

En esta línea no está de más recordar que no importa lo grande que sea n, está demostrado  que pares de permutaciones en las que uno de las dos permutaciones es de orden 2 y el otro de orden n generan Sn (ignoro quien obtuvo este resultado y en el artículo no lo citan; igual es folk). Entiendo que es lo mínimo que podemos esperar. Es decir, no creo que pares de permutaciones en las que las dos sean de orden 2, o las una sea de orden 2 y la otra de orden 3 puedan generar Sn para todo n. Entiendo pero no lo sé 100% seguro (podría ser que el tamaño del IAS, cercano a la cota de Landau compensase para todo n en estos casos).

Fin de nota.

Algunas de las preguntas sobre la teoría estadística de pares de permutaciones que creo que tienen interés son, dado un par de permutaciones elegidas al azar dentro del grupo simétrico o alternado (u otros grupos), cual es la probabilidad de que el par sea:

regular o irregular. Aunque recordamos que la distinción regular / irregular  no es equivalente a abeliano / no abeliano, esta no parece excesivamente complicada.

¿ que orden podemos esperar que tenga el IAS en dos permutaciones  ?. A primera vista parece evidente que el IAS típico tendrá el mismo orden que la permutación típica (es decir el señalado por el resultado de Erdos-Turan), pero quizás la primera vista sea engañosa….

Nota 14 de marzo.

Ya me parece más claro que tiene que ser así. Daremos un esbozo de una demostración en breve.

Recordamos en este contexto el teorema de Dixon que afirma que dos permutaciones de Sn elegidas al azar generarán Sn o An con muy elevada probabilidad. La probabilidad de elegir dos permutaciones pares y que por lo tanto generarán An es 1/4 (según acabode leer). Realmente esto complica algo la idea que teníamos pero no creo que la complicación la cambie sustancialmente. Y aprovechamos para recordar que, según he leído, los  pares que no generen Sn lo  más probable generarán S(n-1). Nosotros en una gráfico hicimos una distribución en la que,  fijado un orden del grupo n!, relacionábamos el grado de los pares de permutaciones que generaban este  orden con el número de casos y nos salía una función del tipo ley potencial.

Mi planteamiento es el  siguiente. Si  para un n suficientemente grande hacemos una tabla en la que cruzamos la identidad con el resto de permutaciones de Sn y en cada casilla ponemos el orden de la permutación resultante, y si este orden es aproximadamente el señalado por Erdos-Turan coloreamos la casilla de un color (por ejemplo rojo) y si es muy diferente,  la coloreamos de otro color (por ejemplo azul), entonces obtenemos una tabla coloreada, que según el resultado de Erdos-Turán será de color prácticamente roja, con algunas casillas azules (los extremos de la distribución).  Esto no es más que una manera de expresar gráficamente el resultado de Erdos-Turan para una permutación.

Realmente, el hecho de hacer esta tabla con la identidad es puramente convencional y no cambiaría nada el color si eligiésemos cualquier otra permutación. Por lo tanto si en una tabla cruzamos todas las permutaciones por todas las permutaciones, cada fila será en su mayoría de color rojo.

Recordamos que el orden del IAS se obtiene comparando las dos permutaciones que son los generadores que hemos elegido. Por ejemplo,  los generadores 1342 y 2413 de S4, tienen un IAS de orden 4 dado  que la permutación que se obtiene comparando 1342 con 2413 es de orden 4. No se debe de confundir el orden del IAS con el número de permutaciones que éste contiene (es el doble). Queda claro que con una tabla como la que hemos construido anteriormente ya obtenemos todos los ordenes de todos los  IASes posibles.

Un proceso de selección aleatoria uniforme entre todos los pares de permutaciones se puede realizar de la siguiente manera: elegimos primero  al azar una permutación de la columna de permutaciones (y anotamos su orden comparando esta permutación con la  columna de identidad; será rojo de  manera típica) y luego de manera independiente otra permutación de la fila de permutaciones (y anotamos su orden, comparando con la fila de la  identidad; también será también rojo de manera típica). Finalmente vamos a la casilla dónde se cruzan (que también será rojo, de manera típica).   De manera equivalente aunque quizás más clara, convertimos cada casilla de la tabla en una bola en la cual anotamos el par de permutaciones que se cruzan en la casilla, su orden y mantenemos su color, rojo o azul y hacemos extracciones aleatorias. Claramente la mayoría  de las bolas de la urna serán de color rojo. El  lector se preguntará si no estamos repitiendo  pares de permutaciones y yo me pregunto si no deberíamos repetirlas pues, como hemos visto en el primer proceso, hay dos maneras de obtener el mismo par en una extracción uniforme. Lo de que me pregunto no es retórica, sino pregunta real, pero casi no dudo de la respuesta.

Diría que esto demuestra que el caso típico en Sn o An es el de un par de generadores de orden en torno al dado por Erdos-Turan, con un IAS también en el entorno de este valor. Admito que es una demostración un poco pedestre, troglodita, pero en fin. Quede como esbozo que hay que pulir para que sea demostración. Quede como presentación de los elementos, de los materiales que se utilizarían en una demostración. El caso es que para mi es suficientemente convincente. Y de hecho, ya en S6, se pone de manifiesto experimentalmente.

Fin de nota 14 de marzo. 

–¿ Cual es la probabilidad de que el IAS de la identidad tenga m vértices finales posibles o más ?. Si la intuición el esbozo de la demostración anterior es correcta, ya tenemos más o menos la respuesta, ya que conociendo el orden del IAS conocemos el número de vértices finales posibles. Por lo tanto el caso típico tendrá los vértices finales posibles que nos indica el valor de Erdos-Turan.

¿ cual es la circunferencia del caso típico ?. En entradas anteriores hemos definido el concepto de circunferencia de un Digrafo de Cayley bigenerado y una manera rápida de obtenerla, que no obstante implica la construcción de parte de dos IASes. Realmente ahora mismo no tengo ni idea sobre como abordar esta pregunta.

smooth o twisted. Esta es la pregunta cuya respuesta es más interesante. Se puede reformular de la siguiente manera: ¿ dados un par de permutaciones elegidas al azar en Sn y que por lo tanto serán, en general, de orden similar al valor de Erdos-Turan y cuyo IAS tendrá este valor, en general también, serán smooth o twisted ?.  La propiedad twisted no es tan cerrada como entangled o cycle-entangled, lo que hace que la respuesta a esta pregunta sea más complicada que la respuesta a otras que estamos planteando. Tenemos una investigación pendiente sobre este tema y ahora me oriento a pensar en que (en una definición amplia de Twisted), habrá más casos de este tipo de lo que pensaba, pero puedo cambiar de opinión. Es decir el caso está abierto y lo dejamos como pregunta son respuesta.

entangled o no entangled. (excluyendo aquellos que sólo sean entangled por el hecho de que uno de los dos generadores o los dos sean de orden 2. Recordamos que por definición si uno de los generadores es de orden 2, entonces el caso es entangled). Aquí creo que no me equivoco  si afirmo que estos casos serán asíntoticamente poco frecuentes. Aquí la idea de demostración, que llevo madurando un cierto tiempo y acabo  de aterrizar según escribo estas líneas, es que dados un IAS y DAS de un mismo orden no hay tantas maneras diferentes de construir un caso entangled: si el orden del IAS y DAS es n, puede estar entangled en 2n permutaciones y aunque es posible que para cada uno de ellos pueda haber variaciones, digamos m, no tendremos más que unos 2nm casos diferentes. que no es mucho comparado con n!, salvo que m pueda ser más grande de lo que pienso.   

Nota. De interés desde el punto de vista algorítmico y peligroso para el proyecto, si finalmente conceden la patente es encontrar la forma más eficientes de determinar si un par de generadores es entangled. Fin de nota.

entangled y que la circunferencia sea de orden dos. En otras entradas ya hemos definido el concepto de circunferencia. También hemos comentado, con pruebas bastante definitivas, su relevancia para el problema de recorridos hamiltonianos cuando la circunferencia es de orden 2.  Que la circunferencia sea de orden 2 se puede expresar de la siguiente manera alternativa: el caso es tal que se dé la propiedad (la multiplicación expresa composición) de que la permutación que comparten el IAS  y el DAS sea

(((x^-1) * y)^n) * (x^-1) = (((y^-1) * x)^n) * (y^-1), en el IAS si el IAS es de orden impar y ((x*y^-1)^n)*x = ((y*x^-1)^n)*y, en el DAS (siendo este de orden impar también pues orden IAS=orden DAS).

o

((x^-1) * y)^n = ((y^-1) * x)^n en el IAS si el IAS es de orden par y ((x*y^-1)^n)=((y*x^-1)^n) en el DAS.

(como hemos visto en anteriores entradas los casos que tienen estas propiedades son unas de las familias infinitas de casos que con mayor propabilidad serán altamente problemáticos (no tendrán recorridos hamiltonianos  en ninguno de los vértices finales posibles). Idem anterior, nos interesa encontrar una forma eficiente de determinar sin necesidad de construir el IAS y DAS, si un caso es entangled con circunferencia 2 o no. Por el mismo argumento utilizado anteriormente, pensamos que estos casos serán bastante escasos, más escasos que los puramente entangled.

cycle-entangled. Estos son los casos más restringidos y seguramente también los más improbables. Ya nos preguntamos en una entrada anterior si todo caso cycle-entangled es necesariamente de circunferencia 2.

2. Formas de representar grupos y sus consecuencias con respecto a la complejidad computacional y práctica informática.

Aunque en abstracto un grupo representado por permutaciones o por matrices es exactamente lo  mismo no lo es si lo que nos interesan son aspectos prácticos. En el blog de Cameron hay una entrada muy interesante en la que comenta sobre el simposio Discrete Mathematics and Big Data.

Me ha interesado el siguiente comentario pues ejemplifica lo sorprendentes que son algunas de las afirmaciones del examinador en su último rechazo final (que como el lector conoce, hemos recurrido), cuando dice que los pasos de mi  algoritmo se pueden hacer mentalmente. ¿ Por ejemplo cuando lo aplicamos al grupo Monster (ver parte en rojo) ?

¡¡ Nótese que ya solo almacenar un generador de este grupo en memoria ocupa 800 exabytes !! En wikipedia nos indican que el tamaño de Internet (entendido como almacenamiento digital global) se estima en cerca de 500 exabytes (la fuente es un artículo de The Guardian de 2009; hoy posiblemente esta cantidad ya sea al menos el doble y por lo tanto por primera vez Internet ocupa más espacio que un generador del Monster).

Nota.

Prometo que si me conceden la segunda patente, y ya hemos comentado que si el examinador actúa de manera legítima no le queda otra, no actuaré en contra de nadie que sea capaz de trabajar con los generadores este grupo u otros de tamaño superior mentalmente🙂. Ahora bien, si utiliza lápiz y papel, la cosa puede cambiar🙂.

Sí, es una coña: ya se que no se puede actuar en contra de nadie que utilice un resultado patentado mentalmente. Ni siquiera contra nadie que lo utilice sin ánimo de lucro, aunque utilice computadores.  El caso es que ya para casos pequeños es imposible ejecutar mentalmente los pasos que quiero patentar. No hace falta llegar al extremo del Monster. Y lo mismo para el que quiera utilizar lápiz y papel; lo digo por experiencia…

Fin de nota.

Extracto.

The Classification of Finite Simple Groups was probably the major achievement of 20th century mathematics. One of the groups is the Monster, a “sporadic” simple group of order about 1054 whose smallest permutation representation is on about 1020 points. A single generator for the group would take about 800 exabytes of storage! Matrices are better, since there is a representation by matrices of order 196882 over the field of two elements; one of these only takes about 5 gigabytes.

But these matrices are highly structured, and using the structure and group properties it was possible in the 1990s to fit the generators (and a program) onto a 1.44MB floppy disc.

More recent work has focussed on the idea that, for example, we can study permutation groups without using actual permutations: only a small amount of data in each permutation is actually required. In this way, the computer algebra system GAP can handle groups with big permutation representations (up to about 1018 points, so not quite large enough for the Monster yet).

Rob concluded by referring to the Atlas of Finite Group Representations, which I mentioned in my introduction. The Atlas is designed to be useful by ordinary algebraists with no special knowledge of how it was constructed.

Unfortunately, like all public services these days, its continued existence is under threat …

3. El Sudoku generalizado (que como es conocido es un problema NP-completo) se reduce al problema de encontrar ciclos hamiltonianos en grafos generales. 

Que el problema del Sudoku generalizado es NP-completo era de sobra conocido. Hace poco se ha publicado un artículo que relaciona este problema con el también NP-completo problema de encontrar ciclos hamiltonianos en en dígrafos / grafos.

Título. Reducing the generalised Sudoku problem to the Hamiltonian cycle problem

The generalised Sudoku problem with N symbols is known to be NP-complete, and hence is equivalent to any other NP-complete problem, even for the standard restricted version where N is a perfect square. In particular, generalised Sudoku is equivalent to the, classical, Hamiltonian cycle problem. A constructive algorithm is given that reduces generalised Sudoku to the Hamiltonian cycle problem, where the resultant instance of Hamiltonian cycle problem is sparse, and has O(N^3 ) vertices. The Hamiltonian cycle problem instance so constructed is a directed graph, and so a (known) conversion to undirected Hamiltonian cycle problem is also provided so that it can be submitted to the best heuristics. A simple algorithm for obtaining the valid Sudoku solution from the Hamiltonian cycle is provided. Techniques to reduce the size of the resultant graph are also discussed.

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 WordPress.com

Estás comentando usando tu cuenta de WordPress.com. 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 )

Google+ photo

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

Conectando a %s


A %d blogueros les gusta esto: