Jonathan Chappelon

ON A PROBLEM OF MOLLUZZO CONCERNING STEINHAUS TRIANGLES IN FINITE CYCLIC GROUPS

Let X be a finite sequence of length m 1 in Z/nZ. The derived sequence ∂Xof X is the sequence of length m -1 obtained by pairwise adding consecutive terms of X. The collection of iterated derived sequences of X, until length 1 is reached, determines a triangle, the Steinhaus triangle ∆X generated by the sequence X. We say that X is balanced if its Steinhaus triangle ∆X contains each element of Z/nZ with the same multiplicity. An obvious necessary condition for m to be the length of a balanced sequence in Z/nZ is that n divides the binomial coefficient m+1 2 . It is an open problem to determine whether this condition on m is also sufficient. This problem was posed by Hugo Steinhaus in 1963 for n = 2 and generalized by John C. Molluzzo in 1976 for n 3. So far, only the case n = 2 has been solved, by Heiko Harborth in 1972.

In this paper, we answer positively Molluzzo's problem in the case n = 3 k for all k 1. Moreover, for every odd integer n 3, we construct infinitely many balanced sequences in Z/nZ. This is achieved by analysing the Steinhaus triangles generated by arithmetic progressions. In contrast, for any n even with n 4, it is not known whether there exist infinitely many balanced sequences in Z/nZ. As for arithmetic progressions, still for n even, we show that they are never balanced, except for exactly 8 cases occurring at n = 2 and n = 6.

Introduction

Let Z/nZ denote the finite cyclic group of order n 1. Let X = (x 1 , x 2 , . . . , x m ) be a sequence of length m 2 in Z/nZ. We define the derived sequence ∂X of X as ∂X = (x 1 + x 2 , x 2 + x 3 , . . . , x m-1 + x m ), where + is the sum in Z/nZ. This is a finite sequence of length m -1. Iterating the derivation process, we denote by ∂ i X the ith derived sequence of X, defined recursively as usual by ∂ 0 X = X and ∂ i X = ∂(∂ i-1 X) for all i 1. Then, the ith derived sequence of X can be expressed by means of the elements of X = (x 1 , x 2 , . . . , x m ) as follows

∂ i X = i k=0 i k x 1+k , i k=0 i k x 2+k , . . . , i k=0 i k x m-i+k ,
for every 0 i m -1, where i k = i! k!(i-k)! denotes the binomial coefficient for 0 k i.

The Steinhaus triangle ∆X generated by the sequence X = (x 1 , x 2 , . . . , x m ) is the multiset union, where all occurring multiplicities are added, of all iterated derived sequences of X, that is,

∆X = m-1 i=0 ∂ i X = i k=0 i k
x j+k 0 i m -1, 1 j m -i .

Note that the Steinhaus triangle generated by a sequence of length m 1 is composed by

m+1 2
elements of Z/nZ, counted with their multiplicity. For example, the Steinhaus triangle ∆X generated by the sequence X = (0, 1, 2, 2) in Z/3Z can be represented as Figure 1, where the ith row of the triangle is the (i -1)th derived sequence ∂ i-1 X of X. A finite sequence X in Z/nZ is said to be balanced if each element of Z/nZ occurs in the Steinhaus triangle ∆X with the same multiplicity. For instance, the sequence (2, 2, 3, 3) is balanced in Z/5Z. Indeed, as depicted in Figure 2, its Steinhaus triangle is composed by each element of Z/5Z occurring twice. Note that, for a sequence X of length m 1 in Z/nZ, a necessary condition to be balanced is that the integer n divides the binomial coefficient This concept was introduced by Hugo Steinhaus in 1963 [START_REF] Steinhaus | One Hundred Problems in Elementary Mathematics[END_REF], who asked whether there exists, for each integer m ≡ 0 or 3 (mod 4) (i.e. whenever the binomial coefficient m+1 2 is even), a balanced binary sequence of length m, i.e. a sequence of length m in Z/2Z whose Steinhaus triangle contains as many 0's as 1's. This problem was answered positively for the first time by Heiko Harborth in 1972 [START_REF] Harborth | Solution of Steinhaus's problem with plus and minus signs[END_REF] by showing that, for every m ≡ 0 or 3 (mod 4), there exist at least four balanced binary sequences of length m. New solutions of the Steinhaus's problem recently appeared in [START_REF] Eliahou | On symmetric and antisymmetric balanced binary sequences[END_REF], [START_REF] Eliahou | On a problem of Steinhaus concerning binary sequences[END_REF] and [START_REF] Eliahou | Zero-sum balanced binary sequences[END_REF]. The possible number of ones in a binary Steinhaus triangle was explored in [START_REF] Chang | Binary triangles[END_REF]. In 1976, John C. Molluzzo [START_REF] Molluzzo | Steinhaus graphs[END_REF] extended the definition of Steinhaus triangle to any finite cyclic group Z/nZ and he posed the generalization of the Steinhaus's original problem.

Problem [START_REF] Molluzzo | Steinhaus graphs[END_REF]. Let n be a positive integer. Given a positive integer m, is it true that there there exists a balanced sequence of length m in Z/nZ if and only if the binomial coefficient m+1 2 is divisible by n?

This generalization of the Steinhaus's original problem corresponds to Question 8 of [START_REF] Dymacek | A survey of Steinhaus graphs[END_REF]. So far this problem was completely open for n 3. In this paper, we solve in the affirmative the case n = 3 k for all k 1. Moreover, we show that there exist infinitely many balanced sequences in each finite cyclic group of odd order. This paper is organized as follows. In Section 2, we present generalities on balanced sequences in finite cyclic groups. In Section 3, we describe the structure of the Steinhaus triangle generated by an arithmetic progression in Z/nZ. This permits us to show, in Section 4, that there exists a positive integer α(n), for each odd number n, such that every arithmetic progression with invertible common difference and of length m ≡ 0 or -1 (mod α(n)n) is a balanced sequence in Z/nZ. This result is refined in Section 5, by considering antisymmetric sequences. Particularly, this refinement answers in the affirmative Molluzzo's Problem in Z/3 k Z for all k 1. In contrast with the results obtained in Sections 4 and 5, we show, in Section 6, that the arithmetic progressions in finite cyclic groups of even order n are never balanced, except for exactly 8 cases occurring at n = 2 and n = 6. Finally, in Section 7, we conclude with several remarks and open subproblems of Molluzzo's problem.

Generalities on balanced sequences

In this section, we will establish the admissible lengths of balanced sequences in Z/nZ and study the behaviour of balanced sequences under projection maps.

On the length of a balanced sequence

The set of all prime numbers is denoted by P. For every prime number p, we denote by v p (n) the p-adic valuation of n, i.e. the greatest exponent e 0 for which p e divides n. The prime factorization of n may then be written as

n = p∈P p vp(n) .
We denote by ω(n) the number of distinct prime factors of n, i.e. the number of primes p for which v p (n) 1.

As seen in Section 1, a necessary condition for a sequence of length m 1 in Z/nZ to be balanced is that n divides the binomial coefficient m+1 2 , the cardinality of the Steinhaus triangle ∆X. The set of all positive integers m satisfying this divisibility condition is described in the following theorem.

Theorem 2.1. Let n be a positive integer. The set of all positive integers m such that the binomial coefficient m+1 2 is a multiple of n is a disjoint union of 2 ω(n) distinct classes modulo 2n if n is even, and of the same number of distinct classes modulo n if n is odd. This set comprises the classes 2nN and (2n -1) + 2nN if n is even, and the classes nN and (n -1) + nN if n is odd.

Proof. Let n and m be two positive integers. Then,

m + 1 2 ≡ 0 (mod n) ⇐⇒ m(m + 1) ≡ 0 (mod 2n) ⇐⇒ m(m + 1) ≡ 0 (mod 2 v 2 (n)+1 ) m(m + 1) ≡ 0 (mod p vp(n) ), ∀p ∈ P \ {2} ⇐⇒ m ≡ a 2 (mod 2 v 2 (n)+1 ) m ≡ a p (mod p vp(n) ), ∀p ∈ P \ {2}
with a p ∈ {-1, 0} for every prime p. Each integer m of the set appears then as a solution of a system of congruences composed by ω(n) non-trivial equations. By the Chinese remainder theorem there exists a unique solution modulo n or modulo 2n according to the parity of n. This permits us to conclude that there exist 2 ω(n) such classes modulo 2n (resp. modulo n) for every even (resp. odd) number n. Particularly, if n is even (resp. odd) and a p = 0 for every prime p, then the positive integers m, such that the binomial m+1 2 is a multiple of n, constitute the class 2nN (resp. the class nN). By the same way, if n is even (resp. odd) and a p = -1 for every prime p, then such positive integers m constitute the class (2n -1) + 2nN (resp. the class (n -1) + nN).

Corollary 2.2. Let p be an odd prime number and k be a positive integer. For every positive integer m, we have

m + 1 2 ≡ 0 (mod p k ) ⇐⇒ m ≡ 0 or -1 (mod p k ).
Similarly, for every positive integer m, we have

m + 1 2 ≡ 0 (mod 2 k ) ⇐⇒ m ≡ 0 or -1 (mod 2 k+1 ).
For instance, for n = 825 = 3 • 5 2 • 11, the set of positive integers m such that the binomial coefficient m+1 2 is divisible by 825 is the disjoint union of the 8 classes a + 825N with a ∈ {0, 99, 275, 374, 450, 549, 725, 824}.

Balanced sequences under projection maps

For every finite multiset M of Z/nZ, we define and denote by m M the multiplicity function of M as the function m M : Z/nZ -→ N which assigns to each element x in Z/nZ the number of occurrence m M (x) of x in the multiset M. We agree that the multiplicity function m M vanishes at every x not in M.

As usual, the cardinality |M| of a finite multiset M is the total number of elements in M, counted with multiplicity, that is,

|M| = x∈Z/nZ m M (x).
Let X be a sequence of length m 1 in Z/nZ. Since the Steinhaus triangle ∆X is a multiset of cardinality m+1 2 , it follows that the sequence X is balanced if, and only if, the multiset ∆X has a constant multiplicity function m ∆X equal to 1 n m+1 2

.

For every factor q of the positive integer n, we denote by π q the canonical surjective morphism π q : Z/nZ -։ Z/qZ. For a finite sequence X = (x 1 , x 2 , . . . , x m ) of length m 1 in Z/nZ, we define, and denote by π q (X) = (π q (x 1 ), π q (x 2 ), . . . , π q (x m )) , its projected sequence in Z/qZ. We now study the behaviour of balanced sequences in Z/nZ under the projection morphism π q : Z/nZ -։ Z/qZ. Theorem 2.3. Let q be a divisor of n and X be a sequence of length m 1 in Z/nZ. Then, the sequence X is balanced if, and only if, its projected sequence π q (X) is also balanced and the multiplicity function m ∆X : Z/nZ -→ N is constant on each coset of the subgroup qZ/nZ. Proof. For every x in Z/nZ, it is clear that the multiplicity of π q (x) in ∆π q (X) is the sum of the multiplicities in ∆X of all the elements of the coset x + qZ/nZ, that is,

m ∆πq(X) (π q (x)) = n q -1 k=0 m ∆X (x + kq), ∀x ∈ Z/nZ.
This completes the proof.

Steinhaus triangles of arithmetic progressions

In this section we will describe the structure of the Steinhaus triangle associated to an arithmetic progression of Z/nZ. We denote by AP (a, d, m) = (a, a + d, a + 2d, . . . , a + (m -1)d) the arithmetic progression beginning with a ∈ Z/nZ, with common difference d ∈ Z/nZ and of length m 1. We begin by analysing the iterated derived sequences of an arithmetic progression in Z/nZ. First, its derived sequence is also an arithmetic progression in Z/nZ. More precisely, we have Proposition 3.1. Let n be a positive integer and let a and d be in Z/nZ. Then, the ith derived sequence of the arithmetic progression AP (a, d, m) is the arithmetic progression

∂ i AP (a, d, m) = AP 2 i a + 2 i-1 id, 2 i d, m -i ,
for every 0 i m -1.

Proof. If we set X = AP (a, d, m) = (x 1 , x 2 , . . . , x m ) and ∂ i X = (y 1 , y 2 , . . . , y m-i ), then we have

y j = i k=0 i k x j+k = i k=0 i k (a + (j + k -1)d) = i k=0 i k (a + (j -1)d) + i k=0 i k kd = 2 i (a + (j -1)d) + 2 i-1 id = (2 i a + 2 i-1 id) + (j -1)2 i d,
for all 1 j m -i.

For every sequence X of length m 1 in Z/nZ, we denote by ∆X(i, j) the jth element of the ith row of the Steinhaus triangle ∆X, i.e. the jth element of the (i -1)th derived sequence ∂ i-1 X of X, for all 1 i m and all 1 j m -i + 1. For example, in this notation, the jth element of the sequence X is ∆X(1, j).

We now describe the coefficients of the Steinhaus triangle generated by an arithmetic progression in Z/nZ. Proposition 3.2. Let n be a positive integer. Let a and d be in Z/nZ and X = AP (a, d, m) be an arithmetic progression in Z/nZ. Then, we have

∆X(1, j) = a + (j -1)d , ∀1 j m, ∆X(i, j) = 2 i-1 a + 2 i-2 (2j + i -3)d , ∀2 i m, ∀1 j m -i + 1.
Proof. This is merely a reformulation of Proposition 3.1 using the notation ∆X(i, j) introduced above.

Let X be a finite sequence in Z/nZ. Every finite sequence Y such that ∂Y = X is called primitive sequence of X. By definition of the derivation process, each finite sequence admits exactly n primitives. However, for n odd, if X is an arithmetic progression in Z/nZ, then there is exactly one primitive of X which is itself an arithmetic progression. Proposition 3.3. Let n be an odd number and let a and d be in Z/nZ. Then, the sequence AP (2 -1 a -2 -2 d, 2 -1 d, m + 1) is the only arithmetic progression whose derived sequence is the arithmetic progression AP (a, d, m).

Proof. By Proposition 3.1, the derived sequence of AP (2

-1 a -2 -2 d, 2 -1 d, m + 1) is the arithmetic progression AP (a, d, m), that is, ∂AP (2 -1 a -2 -2 d, 2 -1 d, m + 1) = AP (a, d, m).
Suppose now that the arithmetic progressions AP (a 1 , d 1 , m + 1) and AP (a 2 , d 2 , m + 1) have the same derived sequence, that is,

∂AP (a 1 , d 1 , m + 1) = ∂AP (a 2 , d 2 , m + 1).
Then, by Proposition 3.1, we have

AP (2a 1 + d 1 , 2d 1 , m) = AP (2a 2 + d 2 , 2d 2 , m). It follows that 2a 1 + d 1 = 2a 2 + d 2 and 2d 1 = 2d 2 .
Since 2 is invertible in Z/nZ, this leads to the equalities a 1 = a 2 and d 1 = d 2 and so the unicity of the statement is proved.

In contrast, for n even, there is no such unicity statement. For example, in Z/8Z, the arithmetic progressions [START_REF] Eliahou | Zero-sum balanced binary sequences[END_REF][START_REF] Molluzzo | Steinhaus graphs[END_REF][START_REF] Eliahou | Zero-sum balanced binary sequences[END_REF][START_REF] Molluzzo | Steinhaus graphs[END_REF][START_REF] Eliahou | Zero-sum balanced binary sequences[END_REF] and (1, 1, 1, 1, 1) are distinct but have the same derived sequence (2, 2, 2, 2).

Balanced arithmetic progressions in Z/nZ for n odd

The integer n is assumed to be odd throughout this section. We begin by showing that the common difference of a balanced arithmetic progression in Z/nZ must be invertible. Proof. Ab absurdo, suppose that there exists a balanced arithmetic progression

X = AP (a, d, m) with non-invertible common difference d in Z/nZ. We set q = gcd(n, d 0 ) = 1
where d 0 is any integer whose residue class modulo n is d. We consider the canonical surjective morphism π q : Z/nZ -։ Z/qZ and the arithmetic progression

π q (X) = AP (π q (a), π q (d), m) = AP (π q (a), 0, m),
which is a constant sequence in Z/qZ. Theorem 2.3 implies that the sequence π q (X) is balanced. Therefore there exists at least one coefficient in the Steinhaus triangle ∆π q (X) which is zero, say ∆π q (X)(i, j) = 0, and then we obtain 2 i-1 π q (a) = 0 by Proposition 3.2. Since 2 is invertible in Z/qZ, it follows that π q (a) = 0 and hence that π q (X) is the zerosequence of length m in Z/qZ, in contradiction with the fact that π q (X) is balanced.

We continue by studying arithmetic progressions with invertible common differences.

For every odd number n, we denote by α(n) the multiplicative order of 2 n modulo n, i.e. the smallest positive integer e such that 2 en ≡ 1 (mod n), namely

α(n) = min {e ∈ N * | 2 en ≡ 1 (mod n)} .
For every positive integer n, we denote by ϕ(n) the totient of n, i.e. the number of positive integers less than or equal to n that are coprime to n. Note that, for n odd, the integer α(n) divides ϕ(n).

In contrast with Theorem 4.1, the following result states that, for each a and d in Z/nZ with d invertible, there are infinitely many lengths m for which the arithmetic progression AP (a, d, m) is balanced. Theorem 4.2. Let n be an odd number. Let a and d be in Z/nZ with d invertible. Then, the arithmetic progression AP (a, d, m) is balanced for every positive integer m ≡ 0 or -1

(mod α(n)n).
This theorem will be proved at the end of this section.

The positive integer α(n) seems to be difficult to determine. Indeed, there is no general formula known to compute the multiplicative order of an integer modulo n but, however, we get the following helpful propositions.

For every positive integer n, the radical of n, denoted by rad(n), is the product of the distinct prime factors of n, that is,

rad(n) = p∈P p|n p.
The radical of n is also the largest square-free divisor of n. Proposition 4.3. Let n be an odd number. Then α(n) divides α(rad(n)).

Proof. Let p be a prime factor of n such that p 2 divides n. We shall show that α(n) divides α( n p ). There exists a positive integer u such that

2 α( n p ) n p = 1 + u n p .
It follows from the binomial theorem that

2 α( n p )n = 2 α( n p ) n p p = 1 + u n p p = 1 + p-1 k=1 p k u k n p k + u p n p p ≡ 1 (mod n),
and so α(n) divides α( n p ). We conclude by induction that α(n) divides α(rad(n)).

Proposition 4.4. Let p be an odd prime number. Then,

α(p k ) = α(p),
for every positive integer k.

Proof. By Proposition 4.3, the integer α(p k ) divides α(p). It remains to prove that α(p) divides α(p k ). The congruence

2 α(p k )p k ≡ 1 (mod p k ) implies that 2 α(p k )p k ≡ 1 (mod p),
and hence, by Fermat's little theorem, it follows that

2 α(p k )p ≡ 2 α(p k )p k ≡ 1 (mod p).
Therefore α(p) divides α(p k ). This completes the proof.

Proposition 4.5. Let n 1 and n 2 be two relatively prime odd numbers. Then, α(n

1 n 2 ) divides lcm(α(n 1 ), α(n 2 )). Proof. Let i ∈ {1, 2}. The congruences 2 α(n i )n i ≡ 1 (mod n i )
imply that 2 lcm(α(n 1 ),α(n 2 ))n 1 n 2 ≡ 1 (mod n i ).

The result follows by the Chinese remainder theorem.

For example, for n 1 = 5 and n 2 = 3, we have the equality α(15) = 4 = lcm(4, 2) = lcm(α(5), α(3)). However, α(n 1 n 2 ) may be a strict factor of lcm(α(n 1 ), α(n 2 )), e.g. for n = 21: α(21) = 2 and lcm(α(7), α(3)) = lcm(3, 2) = 6. The table in Figure 3 shows the first values of α(n) for n odd.

We end this section by proving Theorem 4.2, using the following two lemmas. Lemma 4.6. Let n be a positive integer. Let AP (a, d, m) = (x 1 , x 2 , . . . , x m ) be an arithmetic progression beginning with a ∈ Z/nZ and with invertible common difference d ∈ Z/nZ. Then, every n consecutive terms of AP (a, d, m) are distinct. In other words, for every

1 i m -n + 1, we have {x i , x i+1 , . . . , x i+n-1 } = Z/nZ. n rad(n) α(n) 1 1
x i 1 = x i 2 ⇐⇒ a+(i 1 -1)d = a+(i 2 -1)d ⇐⇒ (i 1 -1)d = (i 2 -1)d ⇐⇒ i 1 ≡ i 2 (mod n).
This completes the proof. Proof. We shall show that there exists a relationship between the multiplicity function of the Steinhaus triangle ∆AP (a, d, kα(n)n) and that of ∆AP (a, d, α(n)n). We set

X = AP (a, d, kα(n)n).
We now consider the structure of the Steinhaus triangle ∆X depicted in Figure 4. Recall that ∆X(i, j) denotes the jth element of the ith row of ∆X, for every integer 1 i kα(n)n and every integer 1 j kα(n)n -i + 1. The subtriangle A is defined by

A = {∆X(i, j) | 1 i α(n)n , 1 j α(n)n -i + 1} .
Then A is the Steinhaus triangle generated by the initial segment

AP (a, d, α(n)n) of the sequence X, that is, A = ∆AP (a, d, α(n)n).
The subtriangle B is defined by

B = {∆X(i, j) | α(n)n + 1 i kα(n)n , 1 j kα(n)n -i + 1} . α(n)n (k -1)α(n)n α(n)n (k -1)α(n)n A C B Figure 4: Structure of ∆X
Then B is the Steinhaus triangle generated by the derived sequence ∂ α(n)n X, that is,

B = ∆∂ α(n)n X.
Applying Proposition 3.1, we obtain that

∂ α(n)n AP (a, d, kα(n)n) = AP 2 α(n)n a + 2 α(n)n-1 α(n)nd, 2 α(n)n d, (k -1)α(n)n . Since 2 α(n)n = 1, it immediately follows that B = ∆AP (a, d, (k -1)α(n)n).
Finally, the multiset C is defined by

C = {∆X(i, j) | 1 i α(n)n , α(n)n -i + 2 j kα(n)n -i + 1} .
Then each row of C is composed of (k -1)α(n)n consecutive terms of a derived sequence of X. Since, for every 0 i kα(n)n -1, the derived sequence ∂ i X of X is an arithmetic progression with invertible common difference 2 i d by Proposition 3.1, it follows from Lemma 4.6 that each element of Z/nZ occurs (k -1)α(n) times in each row of C. Therefore, the multiplicity function of C is the constant function defined by

m C (x) = (k -1)α(n) 2 n, ∀x ∈ Z/nZ.
Combining these results on the multisets A, B and C, we have

m ∆AP (a,d,kα(n)n) (x) = m A (x) + m B (x) + m C (x) = m ∆AP (a,d,α(n)n) (x) + m ∆AP (a,d,(k-1)αnn) (x) + (k -1)α(n) 2 n,
for every x in Z/nZ. Thus, by induction on k, we obtain

m ∆AP (a,d,kα(n)n) (x) = k • m ∆AP (a,d,α(n)n) (x) + k 2 α(n) 2 n, ∀x ∈ Z/nZ.
This completes the proof.

We are now ready to prove our main theorem.

Proof of Theorem 4.2.

1st Case: m ≡ -1 (mod α(n)n). We first derive the case m ≡ -1 (mod α(n)n) from the case m ≡ 0 (mod α(n)n). Let k be a positive integer and X = AP (a, d, kα(n)n -1) .

By Proposition 3.3, the arithmetic progression

Y = AP 2 -1 a -2 -2 d, 2 -1 d, kα(n)n
is a primitive sequence of X. Since Y is an arithmetic progression with invertible common difference 2 -1 d and of length kα(n)n, it follows from Lemma 4.6 that each element of Z/nZ occurs kα(n) times in the sequence Y . Since X is the derived sequence of Y , we have

m ∆X (x) = m ∆∂Y (x) = m ∆Y (x) -m Y (x) = m ∆Y (x) -kα(n),
for all x in Z/nZ. Therefore, X is balanced if and only if the sequence Y is balanced. This completes the proof of the case m ≡ -1

(mod α(n)n) from the case m ≡ 0 (mod α(n)n).
2nd Case: m ≡ 0 (mod α(n)n). We shall prove this case by induction on n. For n = 1, it is clear that all finite sequences in Z/nZ = {0} are balanced and so, the assertion is true for n = 1. Let now n > 1 be a positive integer and p be the greatest prime factor of n. Suppose that the statement is true for q = n p , i.e. every arithmetic progression with invertible common difference and of length m ≡ 0 (mod α(q)q) in Z/qZ is balanced. Let a and d be in Z/nZ with d invertible. We will show that AP (a, d, m) is balanced for every positive integer m ≡ 0 (mod α(n)n). By Lemma 4.7, it is sufficient to prove that AP (a, d, m) is balanced for one length m multiple of α(n)n.

We set

λ = ϕ rad(n) p .
Then the integer λα(p) is a multiple of α(n). Indeed, the integer α(n) divides α(rad We will prove that the sequence X = AP (a, d, λα(p)n) is balanced. We begin by showing that the multiplicity function of ∆X is constant on each coset of the subgroup qZ/nZ. We consider the structure of the Steinhaus triangle ∆X depicted in Figure 5 where ∆X is constituted by the multisets A r , B (s,t) and C u . We shall show that (1) the multiplicity function m Cu is constant for each C u , (2) the multiplicity function of the union of the B (s,t) is constant, and (3) the multiplicity function of the union of the A r is constant on each coset of the subgroup qZ/nZ.

Step (1): The multiplicity function m Cu is constant for every 1 u α(p) -1.

C 1 C 2 C α(p)-1 B (1,1) B (1,2) ←-B (1,p-1) A 1 -→ A 2 -→ A p-1 -→ Ap -→ B (2,1) B (2,2) ←-B (2,p-1) A p+1 -→ A p+2 -→ A 2p-1 -→ A 2p -→ B (α(p)-1,1) B (α(p)-1,2)
←-B (α(p)-1,p-1)

A (α(p)-2)p+1 -→ A (α(p)-2)p+2 -→ A (α(p)-1)p-1 -→ A (α(p)-1)p -→ B (α(p),1) B (α(p),2)
←-B (α(p),p-1)

A (α(p)-1)p+1 -→ A (α(p)-1)p+2 -→ A α(p)p-1 -→ A α(p)p -→
C u = {∆X(i, j) | (u -1)λn + 1 i uλn , uλn -i + 2 j λα(p)n -i + 1} ,
where ∆X(i, j) denotes the jth element in the ith row of ∆X, for every integer 1 i λα(p)n and every integer 1 j λα(p)n -i + 1. As depicted in Figure 6, each multiset C u is a parallelogram of λn rows and (α(p) -u)λn columns.

(α(p) -u)λn λn C u

m Cu (x) = (α(p) -u)λ 2 n, ∀x ∈ Z/nZ.
Step (2): The multiplicity function of the union of all the multisets B (s,t) is constant. We will construct a fixed-point-free involution Ψ on the set of pairs (s, t) such that the multiplicity function of the multiset union B (s,t) ∪ B Ψ(s,t) is constant for every pair (s, t). Let

Ψ : 1, α(p) × 1, p -1 -→ 1, α(p) × 1, p -1 (s, t) -→ (ψ(s, t), p -t) ,
We will show that the sequence

B (v) (s,t) • B (v)
Ψ(s,t) , the concatenation of the sequences B (v ) (s,t) and B (v ) Ψ (s,t) , is an arithmetic progression with invertible common difference and of length λn. The congruence p ≡ 1 (mod α(p)) implies that (s -1)p + t -1 ≡ s + t -2 (mod α(p)), and (ψ(s, t) -1)p + (p -t) -1 ≡ ψ(s, t) -1 -t ≡ s + t -2 (mod α(p)).

Since α(n) divides λα(p), it follows that 2 ((ψ(s,t)-1)p+(p-t)-1)λ ≡ 2 ((s-1)p+t-1)λ ≡ 2 (s+t-2)λ (mod n), and hence, 2 ((ψ(s,t)-1)p+(p-t)-1)λ n p +v-1 d = 2 ((s-1)p+t-1)λ n p +v-1 d = 2 (s+t-2)λ n p +v-1 d.

(v) (s,t) . Since b (v) Ψ(s,t) = ∆X ((Ψ(s, t) -1)p + (p -t) -1)λ n p + v, λ n p -v + 2 = 2 ((ψ(s,t)-1)p+(p-t)-1)λ n p +v-2 2a + 2 λ n p -v + 2 + + ((ψ(s, t) -1)p + (p -t) -1)λ n p + v -3 d = 2 (s+t-2)λ n p +v-2 2a + ((p -t) + 1)λ n p -v + 1 d = 2 (s+t-2)λ n p +v-2 2a + (t + 1)λ n p -v + 1 d + (p -2t)λ n p 2 (s+t-2)λ n p +v-2 d = b (v) (s,t) + (p -t)λ n p 2 (s+t-2)λ n p +v-2 d , it follows that B (v) (s,t) • B (v) Ψ(s,t) = AP b (v) (s,t) , 2 (s+t-2)λ n p +v-1 d , λn ,
and so, each element of Z/nZ occurs λ times in

B (v) (s,t) • B (v)
Ψ(s,t) for every 1 v λ n p . Then the multiplicity function of the multiset union B (s,t) ∪ B Ψ(s,t) is the constant function defined by

m B (s,t) ∪B Ψ(s,t) (x) = λ 2 n p , ∀x ∈ Z/nZ.
If we denote by B the union of all the multisets B (s,t) , then

m B (x) = α(p) s=1 p-1 t=1 m B (s,t) (x) = 1 2 α(p) s=1 p-1 t=1 m B (s,t) ∪B Ψ(s,t) (x) = 1 2 α(p) s=1 p-1 t=1 λ 2 n p = α(p)λ 2 (p -1)n 2p ,
for every x in Z/nZ, since Ψ is a fixed-point-free involution on 1, α(p) × 1, p -1 .

Step (3): The multiplicity function of the union of all the multisets A r is constant on each coset of the subgroup n p Z/nZ.

For every integer 1 r α(p)p, the multiset A r is defined by

A r = ∆X(i, j) (r -1)λ n p + 1 i rλ n p , 1 j rλ n p -i + 1 .
As depicted in Figure 8, each multiset A r is a triangle associated to a sequence of length If we denote by X r the sequence of the first λ n p terms of the derived sequence ∂ (r-1)λ n p X, then A r is the Steinhaus triangle generated by X r , for every 1 r α(p)p. It is clear that there exists a correspondence between A r and the whole Steinhaus triangle ∆X. Indeed, for every integer 1 i λ n p and every integer 1 j λ n p -i + 1, we have ∆X r (i, j) = ∆X (r -1)λ n p + i, j .

λ n p . λ n p λ n p A r
Let 1 l α(p), 1 i λ n p and 1 j λ n p -i + 1. We will prove that each element of the coset ∆X l (i, j) + n p Z/nZ occurs once in the multiset

∆X l+kα(p) (i, j) k ∈ 0, p -1 .
First, the equality

λn -λ n p = λ(p -1) n p = ϕ rad(n) p (p -1) n p = ϕ(rad(n)) n p = ϕ(n) rad(n) p implies that 2 λn ≡ 2 λ n p (mod n),
and so, 2 α(p)λ n p ≡ 2 α(p)λn ≡ 1 (mod n), since α(n) divides λα(p). This leads to

∆X l+kα(p) (i, j) = ∆X (kα(p) + l -1)λ n p + i, j = 2 (kα(p)+l-1)λ n p +i-1 2a + 2j + (kα(p) + l -1)λ n p + i -3 d = 2 kα(p)λ n p 2 (l-1)λ n p +i-1 2a + 2j + (kα(p) + l -1)λ n p + i -3 d = 2 (l-1)λ n p +i-1 2a + 2j + (l -1)λ n p + i -3 d + k 2 (l-1)λ n p +i-1 λα(p)d n p = ∆X (l -1)λ n p + i, j + k 2 (l-1)λ n p +i-1 λα(p)d n p = ∆X l (i, j) + k 2 (l-1)λ n p +i-1 λα(p)d n p ,
for every integer 0 k p -1. The congruence p ≡ 1 (mod α(p)) implies that α(p) is not divisible by p. Moreover, since p is the greatest prime factor of n, it follows that λ = ϕ rad(n) p is relatively prime to p and hence, the integer λα(p) is not divisible by p. Therefore, we obtain the following multiset equality

∆X l+kα(p) (i, j) k ∈ 0, p -1 = ∆X l (i, j), ∆X l (i, j) + n p , . . . , ∆X l (i, j) + (p -1)n p ,
for every 1 l α(p), 1 i λ n p and 1 j λ n p -i + 1. If we denote by A the union of all the multisets A r , then the multiplicity function of A is constant on each coset of the subgroup n p Z/nZ. We now combine the results obtained above. By Steps 1 and 2, we have

m ∆X (x) = m A (x) + m B (x) + α(p)-1 u=1 m Cu (x) = m A (x) + α(p)λ 2 (p-1)n 2p + α(p)-1 u=1 (α(p) -u)λ 2 n = m A (x) + α(p)λ 2 (p-1)n 2p + α(p) 2 λ 2 n,
for every x in Z/nZ and so, by Step 3, the multiplicity function m ∆X is constant on each coset of the subgroup n p Z/nZ = qZ/nZ.

We now end the proof by showing that π q (X), the image of the sequence X under the surjective morphism π q : Z/nZ -։ Z/qZ with q = n p , is balanced. First, the sequence π q (X) is the arithmetic progression beginning with π q (a) ∈ Z/qZ, with common difference π q (d) ∈ Z/qZ and of length λα(p)n, that is,

π q (X) = π q (AP (a, d, λα(p)n)) = AP (π q (a), π q (d), λα(p)n) .
Moreover, the integer λα(p) is divisible by α(q). Indeed, if v p (n) 2, then rad(q) = rad(n) and so α(q) divides α(rad(q)) = α(rad(n)) by Proposition 4.3. As seen before, λα(p) is divisible by α(rad(n)) and then, α(q) divides λα(p). Otherwise, if v p (n) = 1, then rad(q) = rad(n) p and so α(q) divides α(rad(q)) = α rad(n) p by Proposition 4.3. Since λ = ϕ rad(n) p is divisible by α rad(n) p , it follows that α(q) divides λ. In all cases, we have λα(p) ≡ 0 (mod α(q)).

Therefore, the induction hypothesis implies that the sequence π q (X) is balanced, since it is an arithmetic progression with invertible common difference π q (d) and of length λα(p)n divisible by α(q)q.

We conclude that the sequence X is balanced by Theorem 2.3. This completes the proof of Theorem 4.2.

For example, in Z/7Z, the arithmetic progression AP (1, 3, 20) is balanced since α(7) = 3 and 3 is an invertible element in Z/7Z. Indeed, each element of Z/7Z occurs 30 times in this Steinhaus triangle. Since there are n distinct elements a in Z/nZ and ϕ(n) distinct invertible elements d in Z/nZ, it follows that, for each positive integer m, there exist exactly nϕ(n) distinct arithmetic progressions AP (a, d, m) with invertible common difference in Z/nZ and of length m. Therefore, for n odd, Theorem 4.2 implies that there exist at least nϕ(n) balanced sequences of length m for every positive integer m ≡ 0 (mod α(n)n) or m ≡ -1 (mod α(n)n). However, this is not sufficient to completely settle Molluzzo's Problem, as shown by the following proposition. This shortcoming will be partly overcome in the next section.

⇐= By induction, we can prove that

x i = (-1) j-i x j + j-1 k=i (-1) k-i y k , x j = (-1) j-i x i + j-1 k=i (-1) j-k-1 y k ,
for all integers 1 i < j m. It follows that

x m-i+1 + x i = (-1) ⌈ m 2 ⌉-i x m-⌈ m 2 ⌉+1 + m-i k=m-⌈ m 2 ⌉+1 (-1) m-k-i y k + (-1) ⌈ m 2 ⌉-i x ⌈ m 2 ⌉ + ⌈ m 2 ⌉-1 k=i (-1) k-i y k = (-1) ⌈ m 2 ⌉-i x ⌈ m 2 ⌉ + x m-⌈ m 2 ⌉+1 =0 + ⌈ m 2 ⌉-1 k=i (-1) k-i (y k + y m-k =0 ) = 0, for every integer 1 i ⌈ m 2 ⌉ -1.
This completes the proof.

Proposition 5.2. Let n be an odd number. Let a and d be in Z/nZ. Then, the arithmetic progression AP (a, d, m) of length m 2 is antisymmetric if, and only if, its derived sequence AP (2a + d, 2d, m -1) is also antisymmetric.

Proof. We set X = AP (a, d, m) = (x 1 , x 2 , . . . , x m ) and ∂X = AP (2a + d, 2d, m -1) = (y 1 , y 2 , . . . , y m-1 ). It follows that

y m-i + y i = (2a + d) + (m -i -1)2d + (2a + d) + (i -1)2d = 2(2a + (m -1)d) = 2(a + (m -j)d + a + (j -1)d) = 2(x m-j+1 + x j ),
for all integers 1 i < m and all integers 1 j m.

In contrast, for n even, this proposition is not true. For instance, for n = 8, the arithmetic progression X = (0, 1, 2, 3, 4) is not antisymmetric in Z/8Z but its derived sequence ∂X = (1, 3, 5, 7) is.

We now determine arithmetic progressions which are antisymmetric in Z/nZ for n odd. Proof. We set X = AP (a, d, m) = (x 1 , x 2 , . . . , x m ). If the sequence X is antisymmetric, then

x m-i+1 + x i = 0 for all integers 1 i m. Since x m-i+1 + x i = a + (m -i)d + a + (i -1)d = 2a + (m -1)d
for each 1 i m, it follows that the arithmetic progression X is antisymmetric if, and only if, a, d and the integer m are such that 2a + (m -1)d = 0. Therefore, the sequence

AP 2 -1 (1 -m)d, d, m
is the only arithmetic progression of length m 1 and with common difference d ∈ Z/nZ which is antisymmetric. This completes the proof.

If n is even, the above unicity does not hold in general. For example, in Z/8Z, the antisymmetric sequences (0, 2, 4, 6, 0) and (4, 6, 0, 2, 4) are both arithmetic progressions of length m = 5 and of common difference d = 2.

For every odd number n, we denote by β(n) the projective multiplicative order of 2 n modulo n, i.e. the smallest positive integer e such that 2 en ≡ ±1 (mod n), namely

β(n) = min {e ∈ N * | 2 en ≡ ±1 (mod n)} .
Observe that we have the alternative α(n) = β(n) or α(n) = 2β(n). Moreover, α(n) = 2β(n) if and only if there exists a power e of 2 n such that 2 en ≡ -1 (mod n). If n is a prime power, then β(n) = β(rad(n)), in analogy with Proposition 4.4 for α(n). Indeed, if α(p k ) = 2β(p k ), then we have 2 β(p k )p k ≡ -1 (mod p k ). This implies that 2 β(p k )p k ≡ -1 (mod p) and so 2 β(p k )p ≡ -1 (mod p) by Fermat's little theorem. It follows that α(p) = 2β(p) and β(p) divides β(p k ).

Conversely, if α(p) = 2β(p), then 2 β(p)p ≡ -1 (mod p). By induction on k, it follows from the binomial theorem that there exists a positive integer u k such that 2 β(p)p k = -1 + u k p k . This leads to the congruence 2 β(p)p k ≡ -1 (mod p k ) and so we have α(p k ) = 2β(p k ) and β(p k ) divides β(p).

In either of the two cases α(p k ) = 2β(p k ) or α(p k ) = β(p k ), the result follows from Proposition 4.4.

We now improve Theorem 4.2 by considering the antisymmetric arithmetic progressions with invertible common difference. There are exactly ϕ(n) such sequences, for every length, by Proposition 5.3. Theorem 5.5. Let n be an odd number and d be an invertible element in Z/nZ. Then

• for every m ≡ 0 (mod β(n)n), the arithmetic progression AP (2 -1 d, d, m) is balanced,

• for every m ≡ -1 (mod β(n)n), the arithmetic progression AP (d, d, m) is balanced.

The proof is based on Theorem 4.2 and on the following lemma.

Lemma 5.6. Let n be a positive integer and X be an antisymmetric sequence of length m 1 in Z/nZ. Then we have

m ∆X (x) = m ∆X (-x), ∀x ∈ Z/nZ.
Proof. By Proposition 5.2, all the iterated derived sequences of X are antisymmetric. This leads to

m ∆X (x) = m-1 i=0 m ∂ i X (x) = m-1 i=0 m ∂ i X (-x) = m ∆X (-x), ∀x ∈ Z/nZ.
We are now ready to prove our refinement of Theorem 4.2.

Proof of Theorem 5.5. As in the proof of Theorem 4.2, we derive the case m ≡ -1 (mod β(n)n) from the case m ≡ 0 (mod β(n)n). Let k be a positive integer. We set m = kβ(n)n -1 and X = AP (d, d, m). From Proposition 3.3, the arithmetic progression

Y = AP (2 -2 d, 2 -1 d, kβ(n)n)
is a primitive of the sequence X. Since Y is an arithmetic progression with invertible common difference 2 -1 d and of length kβ(n)n, it follows from Lemma 4.6 that each element of Z/nZ occurs kβ(n) times in the sequence Y . Since X is the derived sequence of Y , we have

m ∆X (x) = m ∆∂Y (x) = m ∆Y (x) -m Y (x) = m ∆Y (x) -kβ(n),
for all x in Z/nZ. Therefore, X is balanced if and only if the sequence Y is balanced. This completes the proof of the case m ≡ -1 (mod β(n)n) from the case m ≡ 0 (mod β(n)n).

We now settle the case m ≡ 0 (mod β(n)n). If α(n) = β(n), then this statement is a particular case of Theorem 4.2. Suppose now that α(n) = 2β(n). Then 2 β(n)n ≡ -1 (mod n). Let k be a positive integer. We shall show that the sequence

AP 2 -1 d, d, kβ(n)n is balanced. We first set X = AP (2 -1 d, d, 2kβ(n)n).
We now consider the structure of the Steinhaus triangle ∆X depicted in Figure 10. Recall that ∆X(i, j) denotes the jth element of the ith row of ∆X, for every integer 1 i 2kβ(n)n and every integer 1 j 2kβ(n)n -i + 1.

kβ(n)n kβ(n)n kβ(n)n kβ(n)n A C B Figure 10: Structure of ∆X
The subtriangle A is defined by

A = {∆X(i, j) | 1 i kβ(n)n , 1 j kβ(n)n -i + 1} .
Then A is the Steinhaus triangle generated by the kβ(n)n first elements of X, that is,

A = ∆AP 2 -1 d, d, kβ(n)n .
The subtriangle B is defined by

B = {∆X(i, j) | kβ(n)n + 1 i 2kβ(n)n , 1 j 2kβ(n)n -i + 1} .
Then B is the Steinhaus triangle generated by the derived sequence ∂ kβ(n)n X, that is,

B = ∆∂ kβ(n)n X.
Proposition 3.1 leads to

∂ kβ(n)n X = ∂ kβ(n)n AP (2 -1 d, d, 2kβ(n)n) = AP 2 kβ(n)n-1 d + 2 kβ(n)n-1 kβ(n)nd, 2 kβ(n)n d, kβ(n)n . Since 2 β(n)n ≡ -1 (mod n), it follows that ∂ kβ(n)n X = AP (-1) k 2 -1 d, (-1) k d, kβ(n)n . If k is even, then ∂ kβ(n)n X = AP (2 -1 d, d, kβ(n)n) and thus A = B. If k is odd, then ∂ kβ(n)n X = AP (-2 -1 d, -d, kβ(n)n).
Since it is an antisymmetric arithmetic progression by Proposition 5.3, it follows from Lemma 5.6 that m B (x) = m B (-x) for all x in Z/nZ. Therefore, we have

m B (x) = m B (-x) = m ∆AP (-2 -1 d,-d,kβ(n)n) (-x) = m ∆AP (2 -1 d,d,kβ(n)n) (x) = m A (x)
for all x ∈ Z/nZ. In all cases, we obtain

m B (x) = m A (x), ∀x ∈ Z/nZ.
Finally, the multiset C is defined by

C = {∆X(i, j) | 1 i kβ(n)n , kβ(n)n -i + 2 j 2kβ(n)n -i + 1} .
Then each row of C is composed of kβ(n)n consecutive terms of a derived sequence of X. Since, for every 0 i 2kβ(n)n -1, the derived sequence ∂ i X of X is an arithmetic progression with invertible common difference 2 i d by Proposition 3.1, it follows from Lemma 4.6 that each element of Z/nZ occurs kβ(n) times in each row of C. Therefore, the multiplicity function of C is the constant function defined by

m C (x) = k 2 β(n) 2 n, ∀x ∈ Z/nZ.
Combining the results above, we have

m ∆X (x) = m A (x) + m B (x) + m C (x) = 2m A (x) + k 2 β(n) 2 n
for all x in Z/nZ.

We conclude that the sequence AP

(2 -1 d, d, kβ(n)n) is balanced if and only if the sequence X = AP (2 -1 d, d, 2kβ(n)n) = AP (2 -1 d, d, kα(n)n
) is also balanced. This completes the proof of Theorem 5.5.

We shall now see that this theorem answers in the affirmative Molluzzo's problem in Z/3 k Z for all positive integers k and gives a partial answer in the general odd case. Finally, from Corollary 2.2, we know that 3 k divides the binomial coefficient m+1 2 if, and only if, the positive integer m is congruent to 0 or -1 modulo 3 k . Therefore, we have constructed balanced sequences for all admissible lengths in Z/3 k Z.

For every odd number n, the results above, namely Theorem 2.1 and Theorem 5.5, partly solve Molluzzo's problem in Z/nZ in the exact proportion of 1 2 ω(n)-1 β(n) , where ω(n) is the number of distinct prime factors of n. Indeed, if we consider the sets It follows from Theorem 2.1 and Theorem 5.5 that

N(n) = m ∈ N m + 1 2 ≡ 0 (mod n) ,
|B(n) ∩ 0, k | |N(n) ∩ 0, k | 1 2 ω(n)-1 β(n) , for all k β(n)n. Since 2 ω(n)-1 β(n)
2 for every odd number n = 3 k , it follows that our method gives a complete solution to Molluzzo's Problem for the powers of three only. For example, for n = 5 k , we have 2 ω(n)-1 β(n) = 2, whence our results in this case produce balanced sequences for half of the admissible lengths.

6 Balanced arithmetic progressions in Z/nZ for n even

In preceding sections we have seen that, for any odd number n and any invertible element d in Z/nZ, the arithmetic progressions AP (a, d, m), for m ≡ 0 or -1 (mod α(n)n), constitute an infinite family of balanced sequences. Here we study the case where n is even and show that, in contrast, arithmetic progressions are almost never balanced. Theorem 6.1. Let n be an even number and a and d be in Z/nZ. Then the arithmetic progression X = AP (a, d, m) is balanced if, and only if, we have    n = 2 and X ∈ {(0, 1, 0), (1, 1, 1), (0, 1, 0, 1), (1, 0, 1, 0)} , or n = 6 and X ∈ {(1, 3, 5), [START_REF] Dymacek | A survey of Steinhaus graphs[END_REF][START_REF] Eliahou | Zero-sum balanced binary sequences[END_REF][START_REF] Eliahou | On a problem of Steinhaus concerning binary sequences[END_REF], (4, 3, 2), (5, 3, 1)} .

Proof. Suppose that the arithmetic progression X = AP (a, d, m) is balanced. We first consider the canonical surjective morphism π 2 : Z/nZ -։ Z/2Z and the projected sequence π 2 (X) = AP (π 2 (a), π 2 (d), m) in Z/2Z which is also balanced by Theorem 2.3. If we denote by ∆π 2 (X) (i, j) the jth element of the ith row of ∆π 2 (X), then Proposition 3.2 implies that ∆π 2 (X) (i, j) = 2 i-2 (2π 2 (a) + (2j + i -3)π 2 (d)) = 0 ∈ Z/2Z, for all i 3. Therefore, for every i 3, the derived sequence ∂ i X only contains zeros. Since the sequence π 2 (X) is balanced, it follows that its triangle ∆π 2 (X) contains at least twice as many elements as π 2 (X) and its derived sequence ∂π 2 (X) and hence, the positive integer m is solution of the inequality 2 m -1 2 m + 1 2 .

Therefore m ∈ 1, 6 . Moreover, the necessary condition that the binomial coefficient m+1 2 , the cardinality of the Steinhaus triangle ∆π 2 (X), is even implies that m = 3 or m = 4. We now distinguish the different cases. Since the equality ∆X (i, j) = 0 implies ∆X(i, j -1) = ∆X(i + 1, j -1) or ∆X(i, j + 1) = ∆X(i + 1, j), it follows that ∆X(4, 1) = 0 and hence, we have 0 = ∆X(4, 1) = 4(2a + 3d) = 4∆X(2, 2).

Therefore, ∆X(2, 2) = 5. Moreover, if 2a + 3d = 5, then d = 3 -1 (5 -2a) = 7(5 -2a) = 5 -4a.

Thus, we look for balanced arithmetic progressions X = (a, 5 -3a, 3a, 5 -a)

with a ∈ {1, 2, 3, 4, 6, 7, 8, 9}. Finally, there is no balanced arithmetic progression in Z/10Z.

Concluding remarks and open subproblems

We have seen, throughout Sections 4 and 5, that in Z/nZ, for n odd, arithmetic progressions with invertible common difference give infinitely many balanced sequences. Particularly, in every Z/3 k Z, they yield a full solution to Molluzzo's problem. In Section 6, we have proved that arithmetic progressions are almost never balanced in Z/nZ for n even. The following particular cases of Molluzzo's problem remain open and are of particular interest.

Problem 1. Do there exist infinitely many balanced sequences in Z/nZ for every even n 4?

Problem 2. Let n be an odd number. Does there exist a balanced sequence of length m for every multiple m of n?

There are some indications that Problem 2 may be more tractable than the full Molluzzo's problem.

Figure 1 :

 1 Figure 1: A Steinhaus triangle in Z/3Z

m+1 2 ,Figure 2 :

 22 Figure 2: The Steinhaus triangle of a balanced sequence in Z/5Z

Theorem 4 . 1 .

 41 Let n be an odd number and let a and d be in Z/nZ. If d is non-invertible, then the arithmetic progression AP (a, d, m) is not balanced for every positive integer m.

Lemma 4 . 7 .

 47 Let n be an odd number and k a positive integer. Let a and d be in Z/nZ with d invertible. Then, the arithmetic progression AP (a, d, kα(n)n) is balanced if, and only if, its initial segment AP (a, d, α(n)n) is also balanced.

  (n)) by Proposition 4.3, which divides α rad(n) p α(p) by Proposition 4.5, which divides ϕ rad(n) p α(p) by definition of the function α.

Figure 5 :

 5 Figure 5: Structure of ∆X

Figure 6 :

 6 Figure 6: Structure of C u Let 1 u α(p) -1. Each row of C u is composed of (α(p) -u)λn consecutive terms of a derived sequence of X. For every 0 i λα(p)n -1, the derived sequence ∂ i X of X is an arithmetic progression with invertible common difference 2 i d by Proposition 3.1. It follows from Lemma 4.6 that each element of Z/nZ occurs (α(p) -u)λ times in each row of C u . Therefore, the multiplicity function of C u is the constant function defined by

Figure 7 :

 7 Figure 7: Structure of B (s,t)

Figure 8 :

 8 Figure 8: Structure of A r

Figure 9 :

 9 Figure9: The Steinhaus triangle ∆AP[START_REF] Chang | Binary triangles[END_REF][START_REF] Eliahou | Zero-sum balanced binary sequences[END_REF] 20)

Proposition 5 . 3 .

 53 Let n be an odd number. Let d be in Z/nZ and m be a positive integer. Then, there exists a unique antisymmetric arithmetic progression of length m and with common difference d. Moreover, if m is a multiple of n, then the unique antisymmetric arithmetic progression with common difference d and of length m is the sequence AP (2 -1 d, d, m). If m ≡ -1 (mod n), then the unique antisymmetric arithmetic progression with common difference d and of length m is the sequence AP (d, d, m).

Proposition 5 . 4 .

 54 Let p be an odd prime number. Then,β p k = β (p) ,for every positive integer k.Proof. The result follows from the claim that α(p k ) = 2β(p k ) if and only if α(p) = 2β(p).

Corollary 5 . 7 .

 57 Molluzzo's problem is completely solved in Z/3 k Z for all positive integers k. In other words, there exists a balanced sequence of length m in Z/3 k Z if and only if m+1 2 is divisible by 3 k .Proof. Let k be a positive integer. By Proposition 5.4, we haveβ(3 k ) = β(3) = 1.Let d be an invertible element in Z/3 k Z. Then, Theorem 5.5 implies that• AP (2 -1 d,d, m) is balanced for every positive integer m ≡ 0 (mod 3 k ),• AP (d, d, m) is balanced for every positive integer m ≡ -1 (mod 3 k ).

  and B(n) = {m ∈ N | ∃ a balanced sequence in Z/nZ of length m} , then clearly B(n) ⊂ N(n) as pointed out in Sections 1 and 2. Moreover, Molluzzo's problem can be reformulated as the question whether B(n) = N(n) for all n > 1.

m = 3 : 2 = 6 , 2 n = 6 : 6 m = 4 : Since n divides the binomial coefficient m+1 2 =n = 2 : 8 n

 3262664228 Since n divides the binomial coefficient m+1 it follows that n = 2 or n = 6. n = 2 : There exist four arithmetic progressions of length m = 3 in Z/2Z including two that are balanced, the sequences X 1 = (0, 1, 0) and X 2 = (1We look for a Steinhaus triangle ∆X containing each element of Z/6Z once. Since the equality ∆X (i, j) = 0 implies ∆X(i, j -1) = ∆X(i + 1, j -1) or ∆X(i, j + 1) = ∆X(i + 1, j), it follows that ∆X(3, 1) = 0 and hence, we have0 = ∆X(3, 1) = 4(a + d) = 4∆X(1, 2).Therefore, ∆X(1, 2) = 3 and we look for balanced arithmetic progressions X = (a, 3, -a), with a ∈ {1, 2, 4, 5}. Finally, the four arithmetic progressions X 3 = (1, 3, 5), X 4 = (2, 3, 4), X 5 = (4, 3, 2) and X 6 = (5, 3, 1) are balanced. 10, it follows that n = 2 or n = 10. There exist four arithmetic progressions of length m = 4 in Z/2Z including two that are balanced, the sequences X 7 = (0, 1, 0, 1) and X 8 = (1= 10 : We look for a Steinhaus triangle ∆X containing each element of Z/10Z once.

Acknowledgments

The author would like to thank Prof. Shalom Eliahou for introducing him to the subject and for his help in preparing this paper.

where ψ : 1, α(p) × 1, p -1 -→ 1, α(p) is the function which assigns to each pair (s, t) the positive integer ψ(s, t) in 1, α(p) which is equivalent to s + 2t -1 modulo α(p), that is, ψ(s, t) ≡ s + 2t -1 (mod α(p)), ∀1 s α(p), ∀1 t p -1.

Since α(p) divides ϕ(p) = p -1, it follows that

and hence, we obtain that

for every (s, t) in 1, α(p) × 1, p -1 . Moreover, this involution has no fixed point. Indeed, if (s, t) were a fixed point of Ψ, then (s, t) = Ψ(s, t) = (ψ(s, t), p -t), implying p = 2t, in contradiction with the parity of p. We have proved that Ψ is a fixedpoint-free involution on the set 1, α(p) × 1, p -1 .

Let 1 s α(p) and let 1 t p -1. If we denote by

for all 1 v λ n p , then

which is an arithmetic progression with common difference 2 ((s-1)p+t-1)λ n p +v-1 d by Proposition 3.1. It follows that

Proposition 4.8. Let n > 1 be an odd number. Then

be the prime factorization of the odd number n > 1. If α(n) = 1, then

Let p j be the least prime factor of n. Since

it follows that O p j (2) divides n, in contradiction with the fact that O p j (2) divides p j -1 which is relatively prime to n.

The antisymmetric case

In Section 4, we have seen that there exist infinitely many balanced sequences in Z/nZ for n odd. More precisely, Theorem 4.2 states that all the arithmetic progressions with invertible common difference and of length m ≡ 0 or -1 (mod α(n)n) are balanced. In this section we refine this result by considering the antisymmetric sequences in Z/nZ. This will be sufficient to settle Molluzzo's problem for any n = 3 k .

Let X = (x 1 , x 2 , . . . , x m ) be a finite sequence of length m 1 in Z/nZ. The sequence X is said to be antisymmetric if x m-i+1 = -x i , for every integer 1 i m.

We first show that the antisymmetry is preserved by the derivation process and we study the condition to have an antisymmetric primitive sequence of an antisymmetric sequence. Proposition 5.1. Let X = (x 1 , x 2 , . . . , x m ) be a finite sequence of length m 1 in Z/nZ. Then the sequence X is antisymmetric if, and only if, its derived sequence ∂X is also antisymmetric and

Proof. We set X = (x 1 , x 2 , . . . , x m ) and ∂X = Y = (y 1 , y 2 , . . . , y m-1 ) its derived sequence. =⇒ For every integer 1 i m -1, we have y m-i + y i = (x m-i + x m-i+1 ) + (x i + x i+1 ) = (x m-i+1 + x i ) + (x m-i + x i+1 ) = 0.


Jimmy Durand Wesolowsk

Aymen Boudguiga

Anup Patel

Julien Viard De Galbert

Matthieu Donain
email: matthieu.donain@mpsa.com

Witold Klaudel
email: witold.klaudel@renault.com

Guillaume Scigala

Jimmy Durand Wesolowski

Xvisor VirtIO-CAN: Fast Virtualized CAN

Keywords: Embedded Systems, Controller Area Network, Virtualization, VirtIO, Xvisor

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

By the end of the last century, transportation systems and especially vehicles replaced some of their mechanical functions by electronically controlled applications. Such applications include automatic control of windows, fuel injection supervision and automatic activation of car headlights. By the end of 2010, cars relied on software containing millions lines of code on 70 to 100 microcontrollers, namely Electronic Control Units (ECUs) [START_REF] Robert | This car runs on code[END_REF], [START_REF] Motavalli | The dozens of computers that make modern cars go (and stop)[END_REF]. Nowadays, the customers needs for new Advanced Driver Assistance Systems (ADAS) services are increasing and so is the total number of embedded ECUs in the vehicles [START_REF] Pitcher | Growing number of ecus forces new approach to cars electrical architecture[END_REF]. In fact, proposing new services for drivers on the road implies embedding more electronic boards, more communication buses, more cables and more software, ending up by increasing vehicle complexity. Consequently, car price is rising with respect to the number of its embedded ECU while it has to stay competitive on the market in order to attract more customers.

One interesting solution to reduce the number of vehicle embedded ECUs consists in using virtualization via a hypervisor. Virtualization allows to run different virtual automotive Operating Systems (OSes), called guest OSes or guest systems, simultaneously over one single physical board. Virtualization defines the hypervisor as a software layer (called host) between the guest OSes and the real hardware. The hypervisor emulates the hardware board for each guest system (Figure 1). In addition, it manages resources sharing between all the guests. However, virtualization comes with a major drawback which is computation overhead. As virtualization introduces the hypervisor layer between running guests and the board, it naturally induces a delay for accessing the hardware. That is, a virtual guest takes more time to access the memory, the network interfaces and the CPU than a classical OS running directly on the hardware. In fact, every time a virtual guest needs to access a resource, it has to pass through the hypervisor which introduces some overhead. Reducing this computation overhead is really important especially for communication scenarios. In practice, vehicle ECU exchange real time data frames through the Controller Area Network (CAN) bus [START_REF][END_REF]. When virtualization is used, CAN bus virtualization overhead must stay as low as possible.

Hypervisor (host)

Guest system 1

Guest System 2 In this paper, we introduce an optimized virtualized CAN device. We use VirtIO API [START_REF] Edge | An api for virtual i/o: virtio[END_REF] [START_REF] Laor | [END_REF] to implement it for our hypervisor namely Xvisor [START_REF] Patel | Xvisor: eXtensible Versatile hypervISOR[END_REF].

Real hardware

The remainder of this paper is organized as follows. Section II reviews the CAN specification and introduces VirtIO and Xvisor. Section III depicts our solution. Section IV concludes the paper.

II. STATE OF THE ART

In this section, we give a brief description of the CAN protocol. Then, we introduce VirtIO and Xvisor.

A. Controller Area Network

The Controller Area Network (CAN) connects Electronic Control Units (ECUs) via a broadcast bus [START_REF][END_REF]. Each ECU is in charge of controlling multiple actuators or sensors. In midrange cars, ECUs are used for Adaptive Cruise Control (ACC), fuel injection supervision, anti-lock braking system and comfort services management. ECUs communicate by exchanging CAN frames. These frames have one of the following types:

• Data frames exchange data between ECUs.

• Remote frames request the transmission of a specific Data frame.

• Error frames indicate the presence of an error over the CAN bus.

• Overload frames add an extra delay before the next frame transmission.

CAN frames do not contain information about their sender (i.e. source) or receiver (i.e. destination). They do not rely on interfaces addressing. In practice, each ECU manages a limited set of unique and distinct frame identifiers. A frame identifier defines an action that must be taken by the frame receivers. CAN bits are encoded using a Non-Return to Zero (NRZ) code where 0-bits and 1-bits are encoded with different nonnull voltage. The value of each transmitted bit is sampled at the end of a nominal bit time i.e. a bit time slot. In practice, CAN 0-bits are generally referenced as dominant bits and 1bits as recessive bits.

CAN relies on Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) with a bitwise arbitration as bus access method. The bitwise arbitration concerns the value of frame identifiers. When two ECUs start the delivery of two different frames at the same time, the ECU sending the frame with the greatest identifier value stops its transmission at the reception of a dominant bit while it is transmitting a recessive bit.

B. Virtual Input Output

Virtual Input Output (VirtIO), is a virtualization abstraction API. It was created by Paul "Rusty" Russel to create a common layer for most virtual devices. As such, it avoids the proliferation of virtualization techniques in drivers, whose code and execution is similar to each others [START_REF] Edge | An api for virtual i/o: virtio[END_REF].

We choose to use VirtIO for CAN interface virtualization for three reasons. On the one side, VirtIO defines a clear and flexible API with well defined and optimized transport abstractions, that fit our needs. On the other side, VirtIO API is becoming the virtualization standard for host-guest communication interfaces [START_REF] Russel | virtio: Towards a de-facto standard for virtual i/o devices[END_REF]. Finally, it is recommended and supported by the LINUX community.

C. eXtensible Versatile hypervISOR

The eXtensible Versatile hypervISOR (Xvisor) is a type-1 monolithic embedded open-source hypervisor. A type-1 hypervisor, also known as bare metal hypervisor, is a virtualization layer that runs directly on the hardware. Meanwhile type-2 hypervisor is executed on top of an operating system. Xvisor is said to be Monolithic, as it has a common software for host hardware access, CPU virtualization, and guest IO emulation. Meanwhile, micro-kernelized software kernels contain basic hardware access and CPU virtualization, but they relies on a management guest to handle the other services (e.g. drivers, file systems, . . . ) [START_REF] Patel | Xvisor: eXtensible Versatile hypervISOR[END_REF].

By design, it has a fast interruption management. Benchmarks demonstrated a low overhead on both guest instruction execution and guest memory operations [START_REF] Patel | Embedded hypervisor xvisor: A comparitive analysis[END_REF]. For example, a Xvisor guest yields an average of 2.550.336 Dhrystone Millions of Instruction Per Second (DMIPS), compared to 2.558.851 DMIPS for a native system. In addition, the Read-Modify-Write throughput on a guest is about 556,13 MB/s compared to 564,58 MB/s on a native system.

Xvisor allows having an emulated interface if needed, a paravirtualized one, or even a direct access to hardware when the resource is not shared.

To conclude, Xvisor flexibility suits well our need to use the already existing VirtIO interfaces, and to adapt it to create a new one for the CAN bus VirtIO-CAN.

III. THE CAN VIRTIO

In the following section, we first list the industrial contraints that must be fulfilled by our proposed solution, VirtIO-CAN. Then, we describe it in details.

A. VirtIO-CAN Prerequisites

The following list depicts the requirements regarding CAN virtual software:

1) The guest high level (userland) certified softwares must remain the same. Thus, the interface for the CAN must not change, i.e. it has to present a SocketCAN compatible driver for LINUX guests.

2) The different guest systems can communicate not only together, but also indistinguishably with the external physical bus.

3) The access must be controlled. Some systems must not have access to or read from the virtual and physical buses. 4) The message priority must be supported. 5) Even guest-to-guest messages must go through the physical bus, as those frames can be used for monitoring or debugging, for example, during a diagnosis with an On-Board Board Diagnostics plug. 6) Xvisor interface for the CAN management must be simple. 7) The overall performance must be comparable, if not indistinguishable, from a non-virtualized (or native) systems.

B. VirtIO-CAN

In order to reach good performances, the CAN communication cannot be fully emulated, i.e. a fully virtualized. Full virtualization implies trapping and handling every operation on the device from the virtualized system, in a complex manner, to simulate the hardware expected behavior.

As CAN resources are shared, direct hardware access, namely passthrough, cannot be used. This would give all guests the complete access to the same hardware and registers in particular. A guest could then overwrite the controller configuration or the data set by another guest. In addition, it may perform conflicting operations that cause errors. In the worst case, it may render the whole controller or system unsusable. Thus, direct hardware access can only be used for exclusive hardware access from one system, either the host or one guest.

Our considered solution, referred to by paravirtualization, uses a compromise between full virtualization and passthrough approaches. The guest driver provides only an interface on the host, with no knowledge of the underlying hardware. This results in a better overall performance and a lower complexity than emulation. Meanwhile, paravirtualization keeps the latter advantages of controlling the resource access.

We choose to achieve this communication through the VirtIO mechanism (presented in Section II-B). VirtIO defines a communication standard for the virtualization of multiple devices (console, network, disk, and soon graphical devices) over a variety of tranport medium (memory-mapped or PCI bus). It allows an identification of the device type, with the available features on the host and the guest side, and the configuration desired by the guest. High throughput data can be passed through VirtIO queues called virtqueues, and smaller specific data through the VirtIO configuration read/write functions.

VirtIO queues are designed for large data transfers. Their data footprint is at least 4 KB of memory with a queuing mechanism. CAN data frame has 29-bit long identifier and 64-bit long payload. Consequently, using VirtIO queues is inadequate because it introduces a large footprint and a cumbersome overhead. So, we decide to use the alternative data transmission mechanism: read/write configuration functions. That is, the guest access are done at specific offset on the host interface through VirtIO.

IV. VIRTIO-CAN IMPLEMENTATION

In this section, we describe the implementation and mechanisms of the virtual CAN. First, we describe the initialization of the different layers. Then, we not only depict a frame transmission from a virtual system to the physical bus, but we also detail the reception process in the opposite direction. Finally, we present an internal frame transmission between guests on the same board.

A. Initialization Phase 1) Initializing the hypervisor driver: In order to avoid mixing the virtualization mechanism and the hardware management, the hardware controller driver is initialized and operates the same way without virtualization. Depending on the underlying material, CAN mailbox number varies. Note that a mailbox is a buffer designed to filter CAN frames with an identification mask. Each mailbox contains only one CAN frame. It is used as reception and emission buffer with a priority management. Mailboxes can be grouped to be used as First In First Out (FIFO) queues. Due to the design of the CAN bus, mailboxes assignment and setup is known and set in advance. We can define the priority of mailboxes and FIFOs. That is a FIFO contains a group of mailboxes with a defined set of priority.

FIFOs are set if the number of virtual-mailboxes is greater than the one available in the hardware controller. If the hardware does not allow setting FIFOs, the service will not be initialized to prevent misuse. 2) Initializing the hypervisor service: We denote by VirtCAN the hypervisor service for the CAN framework. As such we avoid the ambiguity with the VCAN [START_REF] Thuermann | The virtual CAN driver[END_REF]. VirtCAN creates virtual-mailboxes with FIFO support to separate the hardware support from virtual system needs. It also provides a communication layer through the VirtIO framework to the guest system.

The host configuration sets the number of mailboxes and FIFOs to be created (Figure 3). The virtual-mailboxes are buffer slots of four 32-bit words each. The three first slots correspond to the CAN frame itself, and the last one serves for control and status storage (Figure 4). Sending a frame on a particular mailbox returns an error to the guest if the latter already stores one that was not sent. A mailbox read twice without new matching frame also returns an error. However, by design a CAN messaging system avoids that.

The virtual FIFOs use the same buffer format (Figure 4), but frames are queued. A guest system can read or write a defined number of frames before an error is reported. In general, FIFOs are used for lower priority frame reception.

However, the VirtCAN also permits the creation of transmission queues. The hypervisor also has a configuration file for each guest to describe which and how a virtual-mailbox is used by this virtual system. Two guests cannot share the same virtualmailbox to transmit or to receive a frame. However, they can have access to the same FIFOs. Each guest mailbox is a memory pointer to a virtual-mailbox. 3) Initializing the guest driver: The guest driver uses the VirtIO API to detect the VirtIO device and configure the required mailboxes and FIFOs. The hypervisor checks every guest setup to ensure its consistency.

B. Guest CAN Frame Transmission

Guests start transmitting at the end of the initialization phase. The VirtIO driver receives the frame from the higher layers (application, library, runnable, task,. . . ). Then, it sends it to the hypervisor VirtCAN framework. The guest side VirtIO writes the frame at the offset formed by the addition of the mailbox or FIFO offset and an initial base offset for mailboxes. The latter is set by the VirtIO-CAN API.

The CAN frame identifier (ID) is written on a 32-bit word while the frame data are written on 8 bytes. Finally, the 32bit control word is set. Note the frame payload can be less than the reserved 8 bytes. If a guest try to write a CAN frame with an unauthorized identifier, it is discarded and a warning is returned by the framework.

For example, to write a frame in its mailbox n , a guest has to write the 4 words of 32-bit in the VirtIO device at the offset: mailbox offset + VirtCAN buffer size × n When the control word is written, the hypervisor VirtCAN service writes the frame to the CAN hardware controller. If virtual-mailboxes number exceeds the physical-mailboxes one, the excedent content is written in the highest priority transmit FIFO. The system integrator knows the number of excedent mailboxes as he knows the total number of the mailboxes of the guest, the VirtCAN and the hardware.

Fig. 1 .

 1 Fig. 1. Bare metal hypervisor

Fig. 3 .

 3 Fig. 3. VirtCAN system

Fig. 4 .

 4 Fig. 4. VirtCAN framework buffer format

Mailboxes

C. Guest CAN Frame Reception

The frame reception process adapts the same idea of frame transmission of Section IV-B. When a frame is received by the hardware controller, it is copied in the virtual-mailbox matching the frame identifier. The number of physical-mailboxes can be lower than the total number of virtual-mailboxes. Then, the host must be able to receive all the frames. If no mailbox matches a frame identifier, it is queued in the highest priority FIFO. Note that the physical-mailboxes must be principally used for the higher priority frames. If all the reception FIFOs are full, or if there is no FIFO at all, the frame is discarded. In addition, an error message is returned.

Once a message is received in the VirtCAN layer, the service checks which guest is associated to this mailbox, write a flag corresponding to the guest mailbox number in the VirtIO configuration memory at a specified offset, and triggers a CAN interrupt to the guest.

When the guest driver receives the interrupt, it reads the VirtIO device for the mailbox flags. Then, the driver can submit the frame content to the upper layers. The reception flags synchronization between VirtCAN and the guest is not necessary. In fact, all VirtIO write operations done by the guest are trapped by the hypervisor. Then they are used by VirtCAN which updates itself the real flag status.

D. Guest-to-Guest CAN Frame Transmission

The Guest-to-Guest CAN frame transmission matches the aforementioned CAN frame transmission. The different layers operates as described in Section IV-B. In addition, we create a special association between a guest reception mailbox and a transmitting virtual-mailbox. When a frame is sent by a guest, these association sets are checked to notify the destination guest(s). Then, VirtCAN sends the frame to the hardware controller.

Mailboxes

V. CONCLUSIONS

In this work, we propose a framework, VirtCAN, to manage internal and external CAN bus virtualization with error management. The virtualization scheme is also preserved, as the hardware and the virtualization layers are clearly separated as seen in Figure 9.

As presented in the Xvisor memory benchmarks [START_REF] Patel | Embedded hypervisor xvisor: A comparitive analysis[END_REF], the memory throughput of emulated operating systems is as good as a native one (up to 98%). There are only two memory copies for both frame direction: one from the guest to VirtCAN, and one from VirtCAN to the hardware for a frame emission or reception. Moreover, no specific scheduling is required to implement this mechanism.

Our future work consists in implementing VirtCAN. As the higher CAN transmission speed is up to 1 MB/s, and the memory throughput between guests and host is superior to 100 MB/s, we expect a low virtualization overhead, and a very close bus occupation and behavior between the native system and the virtualized one.