La enumeración de Bianchi círculos

Question

Antecedentes: Katherine Stange describe Schmidt arreglos en "Visualizar la media aritmética de los imaginarios cuadrática campos", arXiv:1410.0417. Dado un imaginario cuadrática campo $K$, el estudio de la Bianchi grupo $\mathrm{PSL}_2(\mathcal{O}_K)$, que es el grupo de transformaciones de Möbius con coeficientes en el anillo de enteros de $K$. La imagen de $\mathbb R$ bajo un elemento de grupo que se llama un $K$-Bianchi círculo, y el conjunto de $K$-Bianchi círculos se llama Schmidt disposición.

He aquí un ejemplo de Stange la galería de imágenes, teniendo en $K=\mathbb Q(\sqrt{-7})$ y el dibujo de todos los círculos con la curvatura de hasta el $30\sqrt 7$ que cruzan el fundamental dominio de $\mathcal{O}_K$:

Mi pregunta: ¿Cómo puedo recrear imágenes arbitrarias $K$, a partir de racional aritmética de enteros? Lo que los algoritmos que tengo que escribir el código de C++ desde cero para enumerar un Schmidt acuerdo? (Prefiero que no me tire de un Sabio paquete fuera de la plataforma.)

Es una sencilla tarea para implementar las operaciones básicas de la aritmética de $K$, $\mathcal{O}_K$, y $\mathrm{GL}_2(\mathcal{O}_K)$. Entonces, un ataque de fuerza bruta enfoque es generar un montón de matrices en $\mathrm{GL}_2(\mathcal{O}_K)$, compruebe si cada uno tiene determinante $1$, y si es así, dibuje el círculo correspondiente. Hay muchos problemas con esta fuerza bruta enfoque:

• Se gasta la mayoría de su tiempo a la inspección de matrices sin determinante $1$, sobre todo a la búsqueda de grandes norma de coeficientes y de alta curvatura círculos.
• También se pierde tiempo en los círculos que están fuera de los límites de la ilustración.
• Se retoma muchos elementos de los grupos que generan el mismo círculo. Debemos cociente de la estabilizador de $\mathbb R$, es decir, el sistema modular de grupo $\mathrm{PSL}_2(\mathbb Z)$.
• No está claro cuántas de las matrices deben ser probados antes de que podamos decir que hemos enumerado todos los círculos en un diagrama como Stange.

Cada vez que me alcance para un mayor acercamiento inteligente, estoy frenada por el hecho de que $\mathcal{O}_K$ no es necesariamente una única factorización de dominio, e incluso cuando lo es, no es necesariamente Euclidiana. ¿Cómo podemos enumerar algo como $\mathrm{PSL}_2(\mathcal{O}_K)$ con una eficiencia razonable al $K$ es tan rebelde?

Edit: Para explicar mi último comentario, estamos en busca de matrices $\pmatrix{a&b\\c&d}$ con coeficientes en $\mathcal{O}_K$ donde $ad-bc=1$. Cada fila y columna de una matriz se compone de dos coprime números. ¿Cómo enumerar los pares de coprime números en un no-Euclidiana anillo? (O es que esta mal la sub-problema a resolver?)

Answer 1

Para el registro, he encontrado la manera de improvisar suficiente desigualdades para hacer que la fuerza bruta enfoque de trabajo. He aquí una muy rápida contorno. No voy a probar que funciona, pero lo hace. Yo todavía apreciar una solución más elegante!

Voy a seguir Stange la notación, por lo general un elemento de la Bianchi grupo es $\pmatrix{\alpha&\gamma\\\beta&\delta}$.

1. Fijar un máximo de curvatura $M$. Vamos a sacar todos Bianchi círculos tener curvatura acotada por $M$. Tenga en cuenta que la curvatura es $i(\beta\overline\delta-\delta\overline\beta)$, así que vamos a empezar la hebra externa mediante la enumeración de $\beta$$\delta$.
2. Enumerar $\beta\in\mathcal{O}_K$ delimitada por $N(\beta)\leq M^2$, y de tal manera que $\beta\geq0$ en el diccionario de la orden. (Por el proyectivas de simetría, podemos elegir el signo de $\beta$ sin pérdida de generalidad.)
3. Enumerar $\delta\in\mathcal{O}_K$ delimitada por $N(\beta)\leq N(\delta)\leq \frac{4M^2}{3N(\beta)}$, y de tal manera que $|\Re(\delta/\beta)|\leq1/2$. (Solo necesitamos para $\delta/\beta$ a cubrir uno de los fundamentos de dominio de la modulares grupo). Si la curvatura es, de hecho, en $M$, luego siguen el bucle más profundo:
4. Enumerar $\alpha\in\mathcal{O}_K$ delimitada por $N(\alpha)\leq\frac{(4+|\Delta|)N(\beta)}{16}$ donde $\Delta$ es el discriminante de $K$. (Esto elimina algunos, pero no todos, de la redundancia de la generación de círculos que se diferencian sólo por una traducción en $\mathcal{O}_K$.)
5. Solucionar $\alpha\delta-\beta\gamma=1$$\gamma$. Si $\gamma\in\mathcal{O}_K$, a continuación, dibuje el círculo correspondiente y de cualquiera de sus traduce por $\mathcal{O}_K$ en el área de visualización.

Los tres bucles anidados parecer como que iba a explotar $M$ se hace más grande, pero en la práctica sólo se tarda un par de segundos para llegar hasta el $M=600$, lo cual es suficiente para la mayoría de las ilustraciones, como este:

Answer 2

Acabando el tiempo. En general, los generadores de Bianchi grupos puede ser difícil de calcular, ya que este papel por Swan sugiere [1]

Sin embargo, el artículo 4 de Stange del papel se ve muy útil para el cómputo de las cosas.

• 4.1 $K$-bianchi círculos sólo se cruzan en $K$ puntos.

• 4.2 Dos $K$-bianchi círculos de mayo sólo se cruzan en ángulo de $\theta$ fib $e^{i\theta} \in \mathbb{O}_K$. Principalmente esto se aplica a $K = \mathbb{Q}(i), \mathbb{Q}(e^{2\pi i /3})$

• 4.3 Deje $a/b \in K$ ser una fracción con $a,b \in \mathcal{O}_K$ $(a)+(b)=(1)$ "coprime" como ideales. Luego tenemos a los vecinos de "fracciones de farey"

$$ \left[\begin{array}{c} a \\ b \end{array}\right] , u\left[\begin{array}{c} a \\ b \end{array}\right] + k\tau\left[\begin{array}{c} c \\ d \end{array}\right] \in \mathbb{P}^1_K $$

Aquí $u \in \mathcal{O}^\ast_K$ ser una unidad, que es $\{1,- 1\}$ si $K = \mathbb{Q}(\sqrt{-d})$$d > 3$. Aquí $k \in \mathbb{Z}$ $\tau$ es [no sé]. $\tau$ debe ser parte de el grupo de clase de $K$. es $\sqrt{-d}$ $d \not \equiv 3(4)$ o $\frac{1 + \sqrt{-d}}{2}$$d \equiv 3(4)$.

El documento original por Asmus Schmidt es una lectura interesante. Él no tiene equipo así que definitivamente tenemos una pierna para arriba en él. Véase también Stange más reciente del papel de La Appolonian Estructura de Bianchi Grupos. Ella incluye esto:

En este caso se reduce a la informática coprime pares de números de $(a)+(b)=1$ que puede o no puede ser más fácil de lo que acaba de encontrar soluciones a $ad-bc=1$.