Dejemos que $n>1$ sea un número entero. Consideremos el conjunto $C_n := \{0,1, \dots , n-1\}$ .
Un Ordenación euleriana de $C_n$ es una ordenación $r_1, \dots, r_n$ de sus elementos tal que:
$$\forall i \le n \ \forall j<i \ \exists k < i \text{ with } \frac{n}{gcd(n,r_k-r_i)} \text{ prime and } \frac{gcd(n,r_k-r_i)}{gcd(n,r_j-r_i)} \text{ integer.}$$
Nota: : Dejemos que $p$ sea un número primo. Entonces, $0,1, \dots , p-1$ es una ordenación euleriana de $C_p$ .
De hecho, cualquier ordenación de $C_p$ es euleriano, por lo que $C_p$ tiene $p!$ Ordenaciones eulerianas.
Ejercicio : Si $n$ no es libre de cuadrados entonces $C_n$ no tiene un ordenamiento euleriano.
Ejemplo: la ordenación euleriana (lexicográficamente primera) para $C_n$ con $n \le 30$ no prima cuadrada:
$C_6 : 0,2,3,1,4,5$
$C_{10} : 0, 2, 4, 5, 1, 3, 6, 7, 8, 9$
$C_{14} : 0, 2, 4, 6, 7, 1, 3, 5, 8, 9, 10, 11, 12, 13$
$C_{15} : 0, 3, 5, 2, 6, 1, 4, 7, 8, 9, 10, 11, 12, 13, 14$
$C_{21} : 0, 3, 6, 7, 1, 4, 8, 2, 5, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20$
$C_{22} : 0, 2, 4, 6, 8, 10, 11, 1, 3, 5, 7, 9, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21$
$C_{26} : 0, 2, 4, 6, 8, 10, 12, 13, 1, 3, 5, 7, 9, 11, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25$
$C_{30} : 0, 6, 10, 4, 12, 2, 8, 14, 15, 16, 18, 3, 20, 5, 17, 21, 1, 7, 11, 13, 19, 9, 22, 23, 24, 25, 26, 27, 28, 29$
Pregunta principal : ¿Existe una ordenación euleriana de $C_n$ para cada $n>1$ ¿libre de cuadritos?
Sage comprueba que $n\le 500$ (véase más abajo).
En caso afirmativo, deje que $n>1$ sea un número entero libre de cuadrados:
Pregunta más fuerte : ¿Puede cualquier ordenación euleriana parcial de $C_n$ ( $r_1, \dots, r_s$ con $s<n$ ) se complete?
Preguntas extra : ¿Cuántas ordenaciones eulerianas de $C_n$ ¿están ahí? ¿Qué es lo primero lexicográficamente?
Nota: : $C_6$ tiene $6!/2$ ordenamientos eulerianos, y $C_{10}$ tiene $10!/3$ (véase el cálculo más abajo).
La motivación de la combinatoria algebraica
Dejemos que $G$ sea un grupo finito y $H$ un subgrupo. Sea $[H,G]$ sea el intervalo en la red de subgrupos de $G$ .
La ordenación euleriana tal y como se ha escrito anteriormente es una traducción teórica de la siguiente propiedad más general aplicada a $G=C_n$ (grupo cíclico) y $H = \{ e\}$ .
Dejemos que $\hat{C}(H,G)$ sea la red de cosetas, es decir, el conjunto $\{Kg \ | \ K \in [H,G] \text{, } g \in G\} \cup \{ \emptyset \}$ ordenado por $\subseteq$ con $K_1g_1 \wedge K_2g_2 = K_1g_1 \cap K_2g_2$ y $K_1g_1 \vee K_2g_2 = \langle K_1,K_2,g_1g_2^{-1}\rangle g_2$ .
Un Ordenación euleriana del conjunto de $H$ -cosetas $Hg$ es una ordenación $Hg_1, Hg_2, \dots, Hg_n$ tal que:
$$\forall i \le n \ \forall j<i \ \exists k < i \text{ with } \langle H,g_kg_i^{-1}\rangle \text{ atom of } [H,G] \text{ and } \langle H,g_kg_i^{-1}\rangle \subseteq \langle H,g_jg_i^{-1}\rangle.$$
Esta propiedad se inspira en la noción de descascarillado de un complejo simplicial, y el documento Desgranando el coset poset por Russ Woodroofe . De hecho, puedo demostrar que si el intervalo $[H,G]$ es el entramado de caras de un regular politopo convexo (que es un Entramado euleriano ), y si el $H$ -admiten un ordenamiento euleriano, entonces el coset poset $\hat{C}(H,G)$ es conchable, y su invariante de Möbius (que es igual a la característica reducida de Euler del complejo de orden de su parte propia) es distinto de cero. Se deduce que el totiente dual de Euler $\hat{\varphi}(H,G)$ como se define en este documento también es distinto de cero.
La motivación anterior implica las nociones habituales de retículo euleriano, característica de Euler y totiente de Euler, por eso la ordenación anterior se denota como un Euleriano ordenando.
Por último, para $G=C_n$ y $H = \{ e \}$ , tenga en cuenta que $\langle H,g_kg_i^{-1}\rangle$ es un átomo $[H,G]$ si $ord(g_kg_i^{-1})$ es primo, y $\langle H,g_kg_i^{-1}\rangle \subseteq \langle H,g_jg_i^{-1}\rangle$ si $\frac{ord(g_jg_i^{-1})}{ord(g_kg_i^{-1})}$ es un número entero; además, $ord(r) = \frac{n}{gcd(n,r)}$ .
Programa Sage
# %attach SAGE/IntegerOrder.spyx
from sage.all import *
cpdef IsEulerianOrdering(int n, list L): # It checks whether L is a (partial) Eulerian ordering.
cdef int i,j,k,s1,s2,s3,a,b,c,g1,g2,p
for s1 in range(1,len(L)):
i=L[s1]
for s2 in range(s1):
j=L[s2]
for s3 in range(s1):
c=0
k=L[s3]
g1=gcd(n,i-k)
g2=gcd(n,i-j)
p=n/g1
if is_prime(p) and g1 % g2 == 0:
c=1
break
if c==0:
print([i,j])
return False
return True
cpdef IntegerOrder(int n, list LL): # If LL is not a partial Eulerian ordering, then it return False. Else it try to complete LL lexicographically (possibly return a partial Eulerian ordering).
cdef int t,s,i,j,k,a,b,c,g1,g2,p,l
cdef list L,T
if IsEulerianOrdering(n,LL):
T=range(n)
l=len(LL)
L=LL
for t in LL:
T.remove(t)
for s in range(n-l):
c=0
for i in T:
a=0
for j in L:
b=0
for k in L:
g1=gcd(n,i-k)
g2=gcd(n,i-j)
p=n/g1
if is_prime(p) and g1 % g2 ==0:
b=1
break
if b==0:
a=1
break
if a==0:
L.append(i)
T.remove(i)
c=1
break
if c==0:
break
return L
return False
cpdef TestSquareFree(int r1, int r2):
cdef int n,l
cdef list L
for n in range(r1,r2+1):
if is_squarefree(n) and not is_prime(n):
L=IntegerOrder(n,[0])
l=len(L)
if l<n:
return n
return True
cpdef MixedBase(int n, list s):
cdef int l, m, i, c
cdef list b,
l=len(s)
b=[]
m=n
for i in range(l):
c=m//s[i]
b.append(m-s[i]*c)
m=c
return b
cpdef MixedBaseOrdering(list s):
cdef list b,o
cdef int p,l,i,n,m
n=prod(s)
o=[]
for r in range(n):
b=MixedBase(r,s)
l=len(s)
m=sum([b[i]*n/s[i] for i in range(l)]) % n
o.append(m)
return o
cpdef HowManyEulerianOrdering(int n):
cdef list L
cdef int r
L=Permutations(range(n)).list()
r=0
for l in L:
if IsEulerianOrdering(n,list(l)):
r+=1
return r Cómputo
sage: IntegerOrder(22,[0])
[0, 2, 4, 6, 8, 10, 11, 1, 3, 5, 7, 9, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21]
sage: IntegerOrder(210,[0])
[0, 30, 42, 12, 54, 24, 60, 18, 48, 6, 36, 66, 70, 72, 2, 78, 84, 90, 96, 100, 102, 32, 105, 108, 112, 82, 40, 114, 44, 14, 74, 120, 15, 124, 4, 88, 28, 58, 94, 10, 52, 98, 8, 38, 50, 20, 62, 80, 92, 22, 64, 104, 34, 76, 16, 46, 86, 26, 56, 68, 106, 110, 116, 118, 122, 126, 21, 111, 128, 130, 132, 27, 117, 134, 135, 9, 129, 3, 123, 136, 138, 33, 140, 35, 141, 1, 142, 144, 39, 146, 147, 148, 150, 45, 152, 153, 154, 155, 156, 51, 121, 158, 159, 160, 161, 41, 71, 125, 162, 57, 127, 7, 37, 91, 164, 165, 166, 167, 47, 5, 75, 77, 107, 65, 131, 61, 19, 49, 79, 109, 25, 55, 13, 43, 85, 97, 103, 113, 23, 53, 11, 81, 83, 93, 95, 115, 31, 73, 119, 29, 59, 17, 87, 89, 99, 101, 133, 63, 137, 67, 139, 69, 143, 145, 149, 151, 157, 163, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209]
sage: TestSquareFree(2,500)
True
sage: HowManyEulerianOrdering(6)
360
sage: HowManyEulerianOrdering(10)
1209600Comprobación de los ejemplos de @user44191
sage: L=MixedBaseOrdering([5,3,2])
sage: L
[0, 6, 12, 18, 24, 10, 16, 22, 28, 4, 20, 26, 2, 8, 14,15, 21, 27, 3, 9, 25, 1, 7, 13, 19, 5, 11, 17, 23, 29]
sage: IsEulerianOrdering(30,L)
True
sage: L=MixedBaseOrdering([7,3,2])
sage: LL=[11*i for i in L]
sage: A=[1,2,3,4,5,6]
sage: LL.extend(A)
sage: IsEulerianOrdering(462,LL) # It checks whether LL is a partial Eulerian ordering.
True
sage: CL=IntegerOrder(462,LL); len(CL)==462 # It checks whether CL is a completion of LL
True
sage: CL
[0, 66, 132, 198, 264, 330, 396, 154, 220, 286, 352, 418, 22, 88, 308, 374, 440, 44, 110, 176, 242, 231, 297, 363, 429, 33, 99, 165, 385, 451, 55, 121, 187, 253, 319, 77, 143, 209, 275, 341, 407, 11, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 155, 23, 89, 156, 24, 90, 157, 25, 91, 158, 26, 92, 159, 27, 93, 160, 28, 94, 161, 29, 95, 162, 30, 96, 163, 31, 97, 164, 32, 98, 177, 45, 111, 178, 46, 112, 179, 47, 113, 180, 48, 114, 181, 49, 115, 182, 50, 116, 183, 51, 117, 184, 52, 118, 185, 53, 119, 186, 54, 120, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 265, 34, 266, 35, 267, 36, 268, 37, 269, 38, 270, 39, 271, 40, 272, 41, 273, 42, 274, 43, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 309, 78, 12, 144, 166, 276, 310, 79, 13, 145, 167, 277, 311, 80, 14, 146, 168, 278, 312, 81, 15, 147, 169, 279, 313, 82, 16, 148, 170, 280, 314, 83, 17, 149, 171, 281, 315, 84, 18, 150, 172, 282, 316, 85, 19, 151, 173, 283, 317, 86, 20, 152, 174, 284, 318, 87, 21, 153, 175, 285, 320, 56, 122, 188, 210, 254, 100, 321, 57, 123, 189, 211, 255, 101, 322, 58, 124, 190, 212, 256, 102, 323, 59, 125, 191, 213, 257, 103, 324, 60, 126, 192, 214, 258, 104, 325, 61, 127, 193, 215, 259, 105, 326, 62, 128, 194, 216, 260, 106, 327, 63, 129, 195, 217, 261, 107, 328, 64, 130, 196, 218, 262, 108, 329, 65, 131, 197, 219, 263, 109, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 397, 398, 399, 400, 401, 402, 403, 404, 405, 406, 408, 409, 410, 411, 412, 413, 414, 415, 416, 417, 419, 420, 421, 422, 423, 424, 425, 426, 427, 428, 430, 431, 432, 433, 434, 435, 436, 437, 438, 439, 441, 442, 443, 444, 445, 446, 447, 448, 449, 450, 452, 453, 454, 455, 456, 457, 458, 459, 460, 461]
