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?

*Remark*: $C_6$ has $6!/2$ Eulerian orderings, and $C_{10}$ has $10!/3$ ones (see computation below).

**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 of a simplicial complex, and the paper Shelling the coset poset by Russ Woodroofe. In fact, I can prove that if the interval $[H,G]$ is the face lattice of a regular convex polytope (which is an Eulerian lattice), 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 of its proper part) is nonzero. It follows that the dual Euler totient $\hat{\varphi}(H,G)$, as defined in this paper, 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): # 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
```

**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
sage: HowManyEulerianOrdering(6)
360
sage: HowManyEulerianOrdering(10)
1209600
```

*Checking of @user44191's examples*

```
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]
```

Eulerian ordering. $\endgroup$ – Sebastien Palcoux Mar 27 '18 at 8:41