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 IntegerOrder(int n):
cdef int s,i,j,k,a,b,c,g1,g2,p
cdef list L,T
T=range(n)
L=[0]
T.remove(0)
for s in range(n-1):
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
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)
l=len(L)
if l<n:
return n
return True
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,n):
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:
return [i,j]
return True
_____
**Computation**
sage: IntegerOrder(22)
[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, 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 example*
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
[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