# Eulerian ordering of the integers modulo n

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]

• I am finding it challenging to translate the condition into something I can mentally operate. Can you give some motivation for the name and for the need for their being a suitable index k? Gerhard "Usually Finds Coprimality Quite Intuitive" Paseman, 2018.03.26. – Gerhard Paseman Mar 27 '18 at 1:05
• @GerhardPaseman: I wanted to hide the motivation because I believed this question interesting for itself in number theory... I edited a last paragraph explaining that the motivation comes from algebraic combinatorics, and justifying in great detail the name of Eulerian ordering. – Sebastien Palcoux Mar 27 '18 at 8:41
• I think the following algorithm will generally produce an "Eulerian ordering": Choose an ordering of the prime factors of $n$, e.g. (5, 3, 2) for 30. For $0 \leq i < n$, write $i$ in mixed base (e.g. $23 = 1_2 1_3 3_5)$. Let $d_p(i)$ denote the digit corresponding to $i$. Then let $r_i = (\sum_{p \in P} d_p(i) \frac{n}{p}) (mod n)$. For example, for 30 (with $5, 3, 2$), this leads to the sequence $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$. Is this sequence Eulerian? – user44191 Mar 27 '18 at 9:59
• I should add: given $i, j$, let $k$ be $i$, except with the largest digit (in the mixed-base) where $j$ differs from $i$ changed. – user44191 Mar 27 '18 at 10:09
• @GerhardPaseman It may be useful to think of this as a sequence of unit boxes in a larger box. The side lengths are each of the prime factors. The condition is then: is there a sequence such that for $j < i$, there's some box in an axis direction from the $i$th box, and that axis direction has to be one where the $i$th and $j$th boxes have different coordinates. My algorithm below then just "fills out" the boxes "lexicographically". – user44191 Mar 28 '18 at 6:50

The basic idea is to separate out the action of each prime, to the maximal extent possible. In the example given in the above comments, the idea was to ignore (the remainder modulo) $2$ as long as possible, ignore (the remainder modulo) $3$ as long as possible given that $2$ was being ignored, etc. I was inspired by the examples you posted, since almost all of them started out with an arithmetic sequence by some prime fraction of $n$. My guess was that that could be extended until it would force a repeat.
For $0 \leq i < n$, write $i$ in mixed base (e.g. $23 = 1_2 1_3 3_5$). Let $d_p(i)$ denote the digit corresponding to $p$ (e.g. $d_3(23) = 1$). Then let $r_i = (\sum_{p \in P} d_p(i) \frac{n}{p}) (\text{mod n})$. Claim: this sequence is Eulerian.
Proof: Let $j < i$ (e.g. $14 = 0_2 2_3 4_5$). Then $j$ differs from $i$ in some digit for a prime $p$ in the mixed base (and, in the largest such digit, the digit for $j$ must be smaller than that for $i$). Then we can choose some $k$ that differs from $i$ only in that digit (e.g. for $i = 23, j = 14$, we can have $k = 0_2 1_3 3_5 = 8$).
We then have that $r_i - r_k$ will be a multiple of $\frac{n}{p}$, so the first part of your statement is satisfied. Further, as $j$ differs from $i$ in the digit for $p$, the coefficients for $\frac{n}{p}$ for $r_i, r_j$ are different (and their difference isn't divisible by $p$). All of the other $\frac{n}{p'}$ are divisible by $p$, so $r_i - r_j$ isn't divisible by $p$, which implies it satisfies the second part of your statement.
• Very nice! Can you prove the bijectivity of the map $i \mapsto r_i$? – Sebastien Palcoux Mar 28 '18 at 1:02
• @SebastienPalcoux Any $j < i$ will differ for some digit $p$; then $r_i \neq r_j \text{(mod p)}$ (as the $d_p$ are all less than $p$), and so will be different. – user44191 Mar 28 '18 at 1:05