Let $n>1$ be an integer. Consider the set $C_n := \{0,1, \dots , n-1\}$.
An *Eulerian ordering* of $C_n$ is an ordering $r_1, \dots, r_n$ of its elements such that:
$$\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.}$$
*Remark*: Let $p$ be a prime number. Then, $0,1, \dots , p-1$ is an Eulerian ordering of $C_p$.
In fact, any ordering of $C_p$ is Eulerian, so that $C_p$ has $p!$ Eulerian orderings.
*Exercice*: If $n$ is not square-free then $C_n$ has no Eulerian ordering.
Example: the (lexicographically first) Eulerian ordering for $C_n$ with $n \le 30$ square-free non-prime:
$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$
**Main question**: Is there an Eulerian ordering of $C_n$, for every $n>1$ square-free?
It is checked by Sage for $n\le 500$ (see below).
If yes, let $n>1$ be a square-free integer:
*Stronger question*: Can any partial Eulerian ordering of $C_n$ ($r_1, \dots, r_s$ with $s<n$) be completed?
*Bonus questions*: How many Eulerian orderings of $C_n$ are there? What is the lexicographically first?
______
**The motivation from algebraic combinatorics**
Let $G$ be a finite group and $H$ a subgroup. Let $[H,G]$ be the interval in the subgroup lattice of $G$.
The Eulerian ordering as written above is a number-theoretic translation of the following more general property applied to $G=C_n$ (cyclic group) and $H = \{ e\}$.
Let $\hat{C}(H,G)$ be the coset lattice, i.e. the set $\{Kg \ | \ K \in [H,G] \text{, } g \in G\} \cup \{ \emptyset \}$, ordered by $\subseteq$, with $K_1g_1 \wedge K_2g_2 = K_1g_1 \cap K_2g_2$ and $K_1g_1 \vee K_2g_2 = \langle K_1,K_2,g_1g_2^{-1}\rangle g_2$.
An *Eulerian ordering* of the set of $H$-cosets $Hg$ is an ordering $Hg_1, Hg_2, \dots, Hg_n$ such that:
$$\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.$$
This property is inspired from the notion of [shelling][1] of a simplicial complex, and the paper [Shelling the coset poset][2] by [Russ Woodroofe][3]. In fact, I can prove that if the interval $[H,G]$ is the face lattice of a regular [convex polytope][5] (which is an [Eulerian lattice][4]), and if the $H$-cosets admit an Eulerian ordering, then the coset poset $\hat{C}(H,G)$ is shellable, and its Möbius invariant (which is equal to the reduced Euler characteristic of the order complex $\Delta(C(H,G))$ of its proper part $C(H,G)$) is nonzero. It follows that the dual Euler totient $\hat{\varphi}(H,G)$, as defined in [this paper][6], is also nonzero.
The above motivation involves the usual notions of Eulerian lattice, Euler characteristic and Euler totient, that is why the above ordering is denoted as an *Eulerian* ordering.
Finally, for $G=C_n$ and $H = \{ e \}$, note that $\langle H,g_kg_i^{-1}\rangle$ is an atom $[H,G]$ iff $ord(g_kg_i^{-1})$ is prime, and $\langle H,g_kg_i^{-1}\rangle \subseteq \langle H,g_jg_i^{-1}\rangle$ iff $\frac{ord(g_jg_i^{-1})}{ord(g_kg_i^{-1})}$ is an integer; moreover, $ord(r) = \frac{n}{gcd(n,r)}$.
___
**Sage program**
# %attach SAGE/IntegerOrder.spyx
from sage.all import *
cpdef IsEulerianOrdering(int n, list L):
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):
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
#print(len(L)==n)
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
_____
**Computation**
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
*Checking of @user44191's examples*
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)
True
sage: IntegerOrder(462,LL)
[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]
[1]: https://en.wikipedia.org/wiki/Shelling_(topology)
[2]: https://doi.org/10.1016/j.jcta.2006.08.010
[3]: https://mathoverflow.net/users/19729/russ-woodroofe
[4]: https://en.wikipedia.org/wiki/Eulerian_poset
[5]: https://en.wikipedia.org/wiki/Convex_polytope
[6]: https://doi.org/10.1016/j.jcta.2018.02.004