Jonathan Chappelon
email: jonathan.chappelon@lmpa.univ-littoral.fr

A universal sequence of integers generating balanced Steinhaus figures modulo an odd number

Keywords: 05B30, 11B50 Molluzzo problem, balanced Steinhaus figure, universal sequence, Steinhaus figure, Steinhaus triangle, Pascal triangle

In this paper, we partially solve an open problem, due to J.C. Molluzzo in 1976, on the existence of balanced Steinhaus triangles modulo a positive integer n, that are Steinhaus triangles containing all the elements of Z/nZ with the same multiplicity. For every odd number n, we build an orbit in Z/nZ, by the linear cellular automaton generating the Pascal triangle modulo n, which contains infinitely many balanced Steinhaus triangles. This orbit, in Z/nZ, is obtained from an integer sequence called the universal sequence. We show that there exist balanced Steinhaus triangles for at least 2/3 of the admissible sizes, in the case where n is an odd prime power. Other balanced Steinhaus figures, such as Steinhaus trapezoids, generalized Pascal triangles, Pascal trapezoids or lozenges, also appear in the orbit of the universal sequence modulo n odd. We prove the existence of balanced generalized Pascal triangles for at least 2/3 of the admissible sizes, in the case where n is an odd prime power, and the existence of balanced lozenges for all admissible sizes, in the case where n is a square-free odd number.

Introduction

Let n be a positive integer and let Z/nZ denote the finite cyclic group of order n. Let S = (a j ) j∈Z be a doubly infinite sequence of elements in Z/nZ. The derived sequence ∂S of S is the sequence obtained by pairwise adding consecutive terms of S, that is ∂S = (a j + a j+1 ) j∈Z . This operation of derivation can be repeated and then, the ith derived sequence ∂ i S is recursively defined by ∂ 0 S = S and ∂ i S = ∂∂ i-1 S for all integers i 1. The sequence of all the iterated derived sequences of S is called the orbit O S = (∂ i S) i∈N of S. For all i ∈ N and all j ∈ Z, we denote by a i,j the jth term of ∂ i S. Since a i+1,j = a i,j + a i,j+1 by the linear local rule of this cellular automaton, the orbit of S can be seen as the (N × Z)-indexed sequence of elements in Z/nZ defined by

O S = a i,j = i k=0 i k a j+k i ∈ N, j ∈ Z ,
where i k is the binomial coefficient i k = i! (i-k)!k! . For every i ∈ N, the ith row of O S is the sequence R i = ∂ i S = (a i,j ) j∈Z and, for every j ∈ Z, the jth diagonal and the jth anti-diagonal of O S are the sequences D j = (a i,j ) i∈N and AD j = (a i,j-i ) i∈N respectively. Orbits of integer sequences and the canonical projection map π n : Z -։ Z/nZ are also considered in this paper. Elementary figures appear in this linear cellular automaton. Examples of them in Z/5Z are depicted in Figure 1. 0 4 3 1 2 4 2 0 3 1 3 4 0 1 0 0 0 1 3 2 0 2 0 3 3 3 3 4 1 0 0 1 4 1 0 4 2 4 3 1 1 2 3 4 4 2 4 1 1 0 0 1 4 0 2 2 2 3 1 1 1 2 0 1 0 1 0 0 1 3 1 1 2 4 2 3 0 2 3 1 1 0 2 1 0 1 0 4 2 4 4 0 4 2 2 3 2 1 1 1 1 0 1 4 4 2 3 1 1 0 3 2 0 4 2 1 2 3 1 1 1 4 1 1 3 4 4 1 4 0 0 3 2 2 2 1 1 0 1 1 0 4 2 1 3 0 2 4 1 3 3 0 4 2 2 0 0 2 4 2 3 0 0 4 0 3 0 4 4 3 2 1 2 2 1 4 1 3 4 3 2 1 0 4 1 3 4 1 4 2 0 2 1 1 0 3 0 4 4 3 3 4 3 2 0 3 3 1 3 0 0 4 2 2 0 3 1 4 0 4 2 0 0 1 2 2 3 2 1 3 3 4 3 2 1 2 2 0 2 3 1 0 4 3 0 4 1 4 2 3 4 0 4 4 1 2 0 1 3 4 0 0 3 4 1 2 2 0 3 3 4 2 2 0 4 1 0 2 3 4 0 0 1 0 2 4 4 3 0 3 2 1 4 2 4 0 3 2 0 3 4 2 3 1 2 1 4 2 4 0 1 2 0 2 4 0 1 1 2 1 3 2 3 3 0 3 0 1 1 4 3 0 2 3 2 1 0 4 3 3 0 1 1 4 1 In this paper, Steinhaus figures are viewed as finite multisets in Z/nZ, that are sets in Z/nZ for which repeated elements are allowed. A finite multiset M in Z/nZ corresponds to a function m M : Z/nZ -→ N, the multiplicity function associated with M, which assigns its multiplicity in M to each element of Z/nZ. The cardinality of M, denoted by |M|, is the number of elements of M counted with multiplicity, that is the non-negative integer |M| = x∈Z/nZ m M (x). Now, let S m = (a 0 , . . . , a m-1 ) be a finite sequence of length m 1 in Z/nZ. The Steinhaus triangle ∇S m associated with S m is the collection of all the iterated derived sequences of S m , that is the finite orbit ∇S m = O Sm = {S m , ∂S m , . . . , ∂ m-1 S m }. Namely, it is the multiset in Z/nZ defined by

∇S m = i k=0 i k a j+k 0 i m -1, 0 j m -1 -i .
We shall say that the triangle ∇S m is of order m. A Steinhaus triangle of order m has cardinality m+1

proposed this construction, for the binary case Z/2Z, in his book on elementary mathematical problems [START_REF] Steinhaus | One hundred problems in elementary mathematics[END_REF]. The Steinhaus trapezoid ST(S m , h) of order m and of height h, with 1 h m, is the collection of the first h derived sequences of S m , that is,

ST(S m , h) = h-1 i=0 ∂ i S m = ∇S m \ ∇∂ h S m .
A Steinhaus trapezoid of order m and of height h has cardinality h(2m -h + 1)/2. Now, let S 2m-1 = (a 0 , . . . , a 2m-2 ) be a finite sequence of length 2m -1 1 in Z/nZ. The generalized Pascal triangle (or Pascal triangle for short) ∆S 2m-1 associated with S 2m-1 is the triangle of height m, built from the top to the base, appearing in the center of the Steinhaus triangle ∇S 2m-1 . Namely, it is the multiset in Z/nZ defined by

∆S 2m-1 = i k=0 i k a m-1-j-k 0 j i m -1 .
Obviously, the generalized Pascal triangle associated with the sequence of length 2m -1 with a 1 in the middle and 0 elsewhere corresponds to the first m rows of the standard Pascal triangle modulo n. A Pascal triangle of order 2m -1 has cardinality m+1

2

. The Pascal trapezoid PT(S 2m-1 , h) of order 2m -1 and of height h is the collection of the last h rows of the Pascal triangle ∆S 2m-1 , that is,

PT(S 2m-1 , h) = ∆S 2m-1 \ ∆(a j ) h j 2m-h-2 .
A Pascal trapezoid of order 2m -1 and of height h has cardinality h(2m -h + 1)/2. Finally, the lozenge ♦S 2m-1 associated with the sequence S 2m-1 is the multiset union of the Pascal triangle ∆S 2m-1 and of the Steinhaus triangle ∇∂ m S 2m-1 . The lozenge ♦S 2m-1 is then the multiset in Z/nZ defined by ♦S 2m-1 = ∆S 2m-1 ∇∂ m S 2m-1 = i+j k=0 i + j k a m-1-j-k 0 i, j m -1 .

A lozenge of order 2m -1 has cardinality m 2 .

In 1963 [START_REF] Steinhaus | One hundred problems in elementary mathematics[END_REF], H. Steinhaus posed the elementary problem of determining if there exists, for every m 1 such that (m + 1)m/2 is even, a binary Steinhaus triangle of order m containing as many 0's as 1's. This problem was solved, for the first time, by H. Harborth in 1972 [START_REF] Harborth | Solution of Steinhaus's problem with plus and minus signs[END_REF]. For every m ≡ 0 or 3 (mod 4), he explicitly built at least four such binary Steinhaus triangles of order m. Other solutions of the Steinhaus problem appear in the literature [START_REF] Eliahou | Zero-sum balanced binary sequences[END_REF][START_REF] Eliahou | On a problem of Steinhaus concerning binary sequences[END_REF][START_REF] Eliahou | On symmetric and antisymmetric balanced sequences[END_REF]. A generalization of this problem in any finite cyclic group was posed by J.C. Molluzzo in 1976 [START_REF] Molluzzo | Steinhaus graphs. Theory and applications of graphs[END_REF].

A finite multiset M in Z/nZ is said to be balanced if each element of Z/nZ appears in M with the same multiplicity. Thus, the multiset M is balanced if and only if m M is the constant function on Z/nZ equal to |M|/n.

Problem 1.1 (Molluzzo,1976). Let n be a positive integer. For every m 1 such that the binomial coefficient m+1 2 is divisible by n, does there exist a balanced Steinhaus triangle of order m in Z/nZ?

In this paper, for every odd number n, we explicitly build balanced Steinhaus triangles of order m in Z/nZ for every m ≡ 0 (mod n) or m ≡ -1 (mod 3n). This answers in the affirmative Problem 2 of [START_REF] Chappelon | On a problem of Molluzzo concerning Steinhaus triangles in finite cyclic groups[END_REF]. In [START_REF] Chappelon | On a problem of Molluzzo concerning Steinhaus triangles in finite cyclic groups[END_REF], the author completely and positively solved this Molluzzo problem in Z/3 k Z for all k 1. Moreover, for n odd, he showed that there exist at least ϕ(n)n balanced Steinhaus triangles of order m in Z/nZ for every m ≡ 0 or -1 (mod ϕ(rad(n))n), where ϕ is the Euler totient function and rad(n) is the radical of n, that is the product of the distinct prime factors of n. As observed in [START_REF] Chappelon | Regular Steinhaus graphs and Steinhaus triangles in finite cyclic groups[END_REF], this problem of Molluzzo does not always admit a positive solution. Indeed, it can be verified, by exhaustive search, that there is no balanced Steinhaus triangle of order m = 5 in Z/15Z or of order m = 6 in Z/21Z. Here, we are also interested in the generalization of the • for every m 1 and every h m such that h(2m -h + 1)/2 is divisible by n, does there exist a balanced Steinhaus trapezoid of order m and of height h?

• for every m 1 such that m+1 2 is divisible by n, does there exist a balanced Pascal triangle of order 2m -1?

• for every m 1 and every h m such that h(2m -h + 1)/2 is divisible by n, does there exist a balanced Pascal trapezoid of order 2m -1 and of height h?

• for every m 1 such that m 2 is divisible by n, does there exist a balanced lozenge of order 2m -1?

For all positive integers n and k and for all k-tuples of elements A = (a 0 , . . . , a k-1 ) and D = (d 0 , . . . , d k-1 ) in Z/nZ, or in Z, the k-interlaced arithmetic progression IAP(A, D) is the sequence with first terms (a 0 , . . . , a k-1 ) and with common differences (d 0 , . . . , d k-1 ), that is the doubly infinite sequence IAP(A, D) = (a j ) j∈Z defined by a j 0 +jk = a j 0 + jd j 0 , for all j ∈ Z and for every j 0 ∈ {0, 1, . . . , k -1}. For k = 1, we denote by AP(a 0 , d 0 ) the arithmetic progression with first element a 0 and with common difference d 0 .

Let S = IAP((0, -1, 1), (1, -2, 1)). We shall show that this sequence has the remarkable property that the orbit of its projection π n (S) contains infinitely many balanced Steinhaus figures for every odd n. For this reason, we shall call this sequence the universal sequence and denote it by US. The first few terms of US, where 0 is the term of index 0, are given below: US = (. . . . . . , -3, -3, 5, -2, -2, 3, -1, -1, 1, 0, 0, -1, 1, 1, -3, 2, 2, -5, 3, 3, -7, . . . . . .) .

The following theorem is the main goal of this article.

Theorem 1.3. Let n ∈ N be odd. Then, the orbit of the projection π n (US) of the universal sequence in Z/nZ contains:

• balanced Steinhaus triangles of order m for every m ≡ 0 (mod n) or m ≡ -1 (mod 3n). This partially solves the Molluzzo problem for 2/3 of the admissible orders m, in the case where n is an odd prime power.

• balanced Steinhaus trapezoids of order m and of height h for every m ≡ 0 (mod n) or m ≡ -1 (mod 3n) and for every h ≡ m (mod n) or h ≡ m + 1 (mod 3n).

• balanced Pascal triangles of order 2m -1 for every m ≡ -1 (mod n) or m ≡ 0 (mod 3n). This also gives a partial solution of Problem 1.2 for 2/3 of the admissible orders 2m -1, in the case where n is an odd prime power.

• balanced Pascal trapezoids of order 2m -1 and of height h for every m ≡ -1 (mod n) or m ≡ 0 (mod 3n) and for every h ≡ m+1 (mod n) or h ≡ m (mod 3n).

• balanced lozenges of order 2m -1 for every m ≡ 0 (mod n). This completely solves Problem 1.2, for lozenges, in the case where n is a square-free odd number.

It would be highly desirable to have a similar result for n even, but this is widely open.

Here are a few results on Steinhaus figures in the binary case Z/2Z. The five smallest and the three greatest possible numbers of 1's in a binary Steinhaus triangle of fixed size was determined by G.J. Chang [START_REF] Chang | Binary triangles[END_REF]. H. Harborth and G. Hurlbert [START_REF] Harborth | On the number of ones in general binary Pascal triangles[END_REF] proved that every positive integer is realizable as the number of 1's in a generalized binary Pascal triangle, that is, for every natural k, there exists a binary sequence S of length 2m k -1 such that ∆S contains exactly k elements equal to 1. They also determined the minimum value for m k . The maximum number of 1's in binary Steinhaus figures (like Steinhaus triangles, generalized Pascal triangles, parallelograms or trapezoids) was studied by M. Bartsch in her Dissertation [START_REF] Bartsch | Steinhaus figures modulo 2 and generalized Steinhaus triangles (Steinhaus-Figuren modulo 2 und verallgemeinerte Steinhaus-Dreiecke), Dissertation[END_REF]. Symmetries in binary Steinhaus triangles and in binary generalized Pascal triangles were explored in [START_REF] Barbé | Symmetric patterns in the cellular automaton that generates Pascal's triangle modulo 2[END_REF][START_REF] Brunat | Symmetries in Steinhaus triangles and in Pascal generalized triangles[END_REF].

This paper is organized as follows. In Section 2, we study doubly arithmetic triangles (DAT for short) in Z/nZ. These are triangles where all the rows are arithmetic progressions with the same common difference and where all the diagonals are also arithmetic progressions with the same common difference. We show that these triangles constitute a source of balanced multisets in Z/nZ, for n odd, while they are never balanced in Z/nZ, for n even. Moreover, we prove that the orbit associated with the sequence of zeros is the only doubly arithmetic orbit in Z/nZ. In Section 3, interlaced doubly arithmetic orbits, i.e., orbits that are an interlacing of doubly arithmetic structures, are considered. We determine all the interlaced doubly arithmetic orbits in Z and, in Section 4, we show that the projection of these particular orbits in Z/nZ, for n odd, contains infinitely many balanced Steinhaus figures. This result is refined in Section 5, by considering antisymmetric sequences. In Section 6, a particular case of this antisymmetric refinement leads to the universal sequence US and we prove Theorem 1. We distinguish different cases according to the value of the greatest common divisor of δ 1 , δ 2 and n. Case 1. If q = gcd(δ 1 , δ 2 , n) = 1, then we consider the projection map π q : Z/nZ -։ Z/qZ. All elements of the triangle π q (DAT(a, d 1 , d 2 , m)) = DAT(π q (a), 0, 0, m) are equal to π q (a). Therefore, the triangle DAT(a, d 1 , d 2 , m) is not balanced in Z/nZ since its projection in Z/qZ is not. Case 2. If gcd(δ 1 , δ 2 , n) = 1, then we set q = gcd(δ 2 , n) = 1 and we consider the projection ∇ = π q (DAT(a, d 1 , d 2 , m)) = DAT(π q (a), π q (d 1 ), 0, m) in Z/qZ, where π q (d 1 ) is invertible in Z/qZ. Since the (kq + l)th row of ∇ is the constant sequence, of length m -kq -l + 1, equal to π q (a) + lπ q (d 1 ), for all l ∈ {0, 1, . . . , q -1} and for all k ∈ N such that kq + l m -1, it follows that we have m ∇ (π q (a)) > m ∇ (π q (a)+π q (d 1 )) > m ∇ (π q (a)+2π q (d 1 )) . . . . . . m ∇ (π q (a)+(q-1)π q (d 1 )).

Therefore ∇ is not balanced in Z/qZ and thus DAT(a,

d 1 , d 2 , m) is not in Z/nZ.
Remark. For n even, there is no balanced DAT in Z/nZ since at least one element of {d 1 , d 2 , d 1 -d 2 } is not invertible in Z/nZ, by the parity of n.

Remark. Another necessary condition for a DAT of order m to be balanced in Z/nZ is that its cardinality, that is the binomial coefficient m+1

2

, must be divisible by n. But these two necessary conditions are not sufficient: as depicted in Figure 2, the triangle DAT(0, 8, 1, 5) is not balanced in Z/15Z, although its cardinality 6 2 = 15 is divisible by n = 15 and its common differences 8, 1 and 7 are invertible in Z/15Z. The following theorem is the main result of this section.

Theorem 2.2. Let n ∈ N be odd and let d 1 , d 2 ∈ Z/nZ be invertible such that d 1 -d 2 is also invertible. Then, the doubly arithmetic triangle DAT(a,

d 1 , d 2 , m) is balanced in Z/nZ for all m ≡ 0 or -1 (mod n).
Proof. Let m be a multiple of n. We denote by R i the ith row of DAT(a, d 1 , d 2 , m), that is R i = (a + id 1 + jd 2 ) 0 j m-1-i . We prove that, for 0 λ m/n -2, the consecutive n rows {R λn , R λn+1 , . . . , R (λ+1)n-1 } are balanced. Consider the permutation σ of the set {0, 1, . . . , n -1} defined by

σ(i) ≡ i(d 1 -d 2 )d 1 -1 (mod n)
for all i ∈ {0, 1, . . . , n -1}. Denote by k i the cardinality of the orbit of i under σ. Let ∇(i, j) = a + id 1 + jd 2 denote the jth term in the ith row of DAT(a, d 1 , d 2 , m). Now, we show that, for every i ∈ {0, 1, . . . , n -1}, the concatenation

∪ k i -1 l=0 R λn+σ l (i) is balanced in Z/nZ. Since ∇ λn + σ l (i), m -1 -λn -σ l (i) + d 2 = a + (λn + σ l (i))d 1 + (m -λn -σ l (i))d 2 = a + σ l (i)(d 1 -d 2 ) = a + σ l+1 (i)d 1 = ∇ λn + σ l+1 (i), 0 , for all l ∈ {0, 1, . . . , k i -1}, it follows that the concatenation ∪ k i -1 l=0 R λn+σ l (i)
is an arithmetic progression with invertible common difference d 2 and of length a multiple of n. Therefore, its multiplicity function is constant on Z/nZ. Finally, since {0, 1, . . . , n -1} is a disjoint union of orbits under σ, the multiplicity function of ∪ n-1 i=0 R λn+i is constant on Z/nZ and thus the triangle DAT(a,

d 1 , d 2 , m) is balanced in Z/nZ.
For m ≡ -1 (mod n), the doubly arithmetic triangle DAT(a, d 1 , d 2 , m) is obtained from the balanced triangle DAT(a, d 1 , d 2 , m + 1) by rejecting its right side. Since it is an arithmetic progression with invertible common difference d 1 -d 2 and of length m + 1 ≡ 0 (mod n), it follows that this right side contains all the elements of Z/nZ with the same multiplicity. This completes the proof.

Remark. For n odd and for every d ∈ Z/nZ invertible, the doubly arithmetic triangles DAT(a, d, -d, m), DAT(a, d, 2d, m) and DAT(a, 2d, d, m) are balanced in Z/nZ, for all m ≡ 0 or -1 (mod n).

Let n be a positive integer and let d 1 and d 2 be two elements of Z/nZ. The orbit O S , associated with a doubly infinite sequence S in Z/nZ, is said to be (d 1 , d 2 )-doubly arithmetic if each subtriangle appearing in it is a DAT with common differences (d 1 , d 2 ), that is if O S is an orbit where all the diagonals are arithmetic progressions with the same common difference d 1 and where all the rows are arithmetic progressions with the same common difference d 2 . Now, we prove that, for every positive integer n, there does not exist a doubly arithmetic orbit in Z/nZ, except the trivial orbit generated by the sequence of zeros in Z/nZ. Proposition 2.3. Let n be a positive integer. The orbit associated with the sequence of zeros is the only doubly arithmetic orbit in Z/nZ.

Proof. It is clear that if O S is (d 1 , d 2 )
-doubly arithmetic, then S is an arithmetic progression with common difference d 2 . We set S = AP(a, d 2 ). It is known [START_REF] Chappelon | On a problem of Molluzzo concerning Steinhaus triangles in finite cyclic groups[END_REF], and easy to retrieve, that the derived sequence ∂S of S is an arithmetic progression with common difference 2d 2 . Moreover, it is also d 2 , by the doubly arithmetic structure of the orbit O S and thus, the common difference d 2 vanishes. By the local rule in O S , we obtain that a + d 1 = 2a and a + 2d 1 = 4a. Therefore, we have a = d 1 = 0 and S is the sequence of zeros. This completes the proof.

Even if there does not exist a non-trivial doubly arithmetic orbit, the results of this section will be useful in next sections, where orbits with an interlaced doubly arithmetic structure are studied.

Interlaced doubly arithmetic orbits of integers

For all positive integers n, k 1 and k 2 and for every doubly infinite sequence S in Z/nZ, or in Z, the orbit

O S = (a i,j |a i+1,j = a i,j + a i,j+1 , i ∈ N, j ∈ Z) is said to be (k 1 , k 2 )-interlaced doubly arithmetic if, for every i 0 ∈ {0, 1, . . . , k 1 -1} and every j 0 ∈ {0, 1, . . . , k 2 -1}, the subsequence (a i 0 +ik 1 ,j 0 +jk 2 |i ∈ N, j ∈ Z) is doubly arithmetic, i.e., if we have a i 0 +ik 1 ,j 0 +jk 2 = a i 0 ,j 0 + i(a i 0 +k 1 ,j 0 -a i 0 ,j 0 ) + j(a i 0 ,j 0 +k 2 -a i 0 ,j 0 ),
for all i ∈ N and all j ∈ Z.

Determining all interlaced doubly arithmetic orbits (IDAO for short) in Z/nZ seems to be very difficult. Nevertheless, IDAO in Z are determined in this section and their projection in Z/nZ will be considered in subsequent sections. First, it is clear that the sequence S associated with a (k 1 , k 2 )-interlaced doubly arithmetic orbit O S is a k 2interlaced arithmetic progression. We begin by showing that the interlaced arithmetic structure of a sequence is preserved under the derivation process. Proposition 3.1. Let n be a positive integer. Let (a 0 , . . . , a k-1 ) and (d 0 , . . . , d k-1 ) be two k-tuples of elements in Z/nZ, or in Z. Then, we have

∂IAP ((a 0 , . . . , a k-1 ), (d 0 , . . . , d k-1 )) = IAP ((a 0 + a 1 , . . . , a k-2 + a k-1 , a k-1 + a 0 + d 0 ), (d 0 + d 1 , . . . , d k-2 + d k-1 , d k-1 + d 0 )) .
Proof. Consider S = IAP ((a 0 , . . . , a k-1 ), (d 0 , . . . , d k-1 )) = (x j ) j∈N and ∂S = (y j ) j∈N .

Then, for all l ∈ Z, we have

y j 0 +lk = x j 0 +lk + x j 0 +lk+1 = (a j 0 + ld j 0 ) + (a j 0 +1 + ld j 0 +1 ) = (a j 0 + a j 0 +1 ) + l(d j 0 + d j 0 +1 ),
for all j 0 ∈ {0, 1, . . . , k -2}, and

y (k-1)+lk = x (k-1)+lk +x (l+1)k = (a k-1 +ld k-1 )+(a 0 +(l+1)d 0 ) = (a k-1 +a 0 +d 0 )+l(d k-1 +d 0 ), for j 0 = k -1.
This completes the proof.

We can now explicitly determine all the iterated derived sequences of an interlaced arithmetic progression.

Proposition 3.2. Let n be a positive integer. Let A and D be two k-tuples of elements in Z/nZ, or in Z. Then, for every integer i 0, we have

∂ i IAP (A, D) = IAP (AC i + DT i , DC i ) ,
where C i is the circulant matrix of size k defined by

C i = Circ l 0 i lk , l 0 i lk -1 , . . . , l 0 i lk + 1 ,
and where T i is the Toeplitz matrix of size k where the (r, s)-entry of T i is, for 1 r, s k,

(T i ) r,s = l 0 l i r -s + lk .
Proof. By iteration on i. Trivial for i = 0. For i = 1, Proposition 3.1 leads to

C 1 = Circ(1, 0, . . . , 0, 1) =        1 0 • • • 0 1 1 1 0 0 . . . . . . . . . . . . . . . . . . 0 0 • • • 0 1 1        and T 1 =         0 • • • • • • 0 1 . . . 0 . . . 0 . . . . . . . . . 0 • • • • • • • • • 0         .
We proceed by induction. Suppose that the result is true for some i 1. First, the (i + 1)th derived sequence of S = IAP (A, D) is equal to

∂ i+1 S = ∂∂ i S = ∂IAP (AC i + DT i , DC i ) = IAP (AC i C 1 + D (T i C 1 + C i T 1 ) , DC i C 1 ) .
Since the product of two circulant matrices is also a circulant matrix, it follows that

C i C 1 = Circ l 0 i lk , l 0 i lk -1 , . . . , l 0 i lk + 1 Circ (1, 0, . . . , 0, 1) = Circ l 0 i lk + l 0 i lk -1 , l 0 i lk -1 + l 0 i lk -2 , . . . . . . . . . . . . , l 0 i lk + l 0 i lk + 1 = Circ l 0 i + 1 lk , l 0 i + 1 lk -1 , . . . , l 0 i + 1 lk + 1 = C i+1 .
Moreover, let

T i C 1 + C i T 1 = (β r,s ) for 1 r, s k. Note that β r,s = (T i C 1 ) r,s + (C i T 1 ) r,s = k u=1 (T i ) r,u (C 1 ) u,s + k v=1 (C i ) r,v (T 1 ) v,s .
Hence for s < k,

β r,s = (T i ) r,s + (T i ) r,s+1 = l 0 l i r -s + lk + l 0 l i r -s + lk -1 = l 0 l i + 1 r -s + lk = (T i+1 ) r,s . For s = k, β r,s = (T i ) r,1 +(T i ) r,k +(C i ) r,1 = l 0 l i r -1 + lk + l 0 l i r -k + lk + l 0 i r -1 + lk = l 0 (l + 1) i r -1 + lk + l 0 l i r -k + lk = l 0 l i r -1 + (l -1)k + l 0 l i r + (l -1)k = l 0 l i + 1 r -k + lk = (T i+1 ) r,k .
This completes the proof.

The main result of this section is the complete characterization of IDAO in Z.

Theorem 3.3. Every interlaced doubly arithmetic orbit O S in Z is generated by an interlaced arithmetic progression of the form S = IAP((a 0 , a 1 , a 2 ), (d, -2d -3Σ, d + 3Σ)), where a 0 , a 1 , a 2 and d are integers, and Σ := a 0 + a 1 + a 2 .

We begin by showing that the interlaced arithmetic progressions listed in Theorem 3.3 will generate interlaced doubly arithmetic orbits of integers.

Proposition 3.4. Let a 0 , a 1 , a 2 , d ∈ Z and let Σ = a 0 +a 1 +a 2 . Then, the orbit O S associated with S = IAP((a 0 , a 1 , a 2 )(d, -2d -3Σ, d + 3Σ)) is (6, 3)-interlaced doubly arithmetic.

Proof. Let O S = (a i,j |a i+1,j = a i,j + a i,j+1 , i ∈ N, j ∈ Z) be the orbit associated with S and let S i 0 ,j 0 be the subsequence S i 0 ,j 0 = (a i 0 +6i,j 0 +3j |i ∈ N, j ∈ Z), for all i 0 ∈ {0, 1, 2, 3, 4, 5} and all j 0 ∈ {0, 1, 2}. We can prove, by induction on i, that, for all j ∈ Z, we have

a 6i,3j = a 0 -2i(d + 3Σ) + jd, a 6i,3j+1 = a 1 -2id -j(2d + 3Σ), a 6i,3j+2 = a 2 + 2i(2d + 3Σ) + j(d + 3Σ), a 6i+1,3j = (a 0 + a 1 ) -2i(2d + 3Σ) -j(d + 3Σ), a 6i+1,3j+1 = (a 1 + a 2 ) + 2i(d + 3Σ) -jd, a 6i+1,3j+2 = (a 0 + a 2 + d) + 2id + j(2d + 3Σ), a 6i+2,3j = (a 1 + Σ) -2id -j(2d + 3Σ), a 6i+2,3j+1 = (a 2 + Σ + d) + 2i(2d + 3Σ) + j(d + 3Σ), a 6i+2,3j+2 = (a 0 -2Σ) -2i(d + 3Σ) + jd, a 6i+3,3j = (a 1 + a 2 + 2Σ + d) + 2i(d + 3Σ) -jd, a 6i+3,3j+1 = (a 0 + a 2 -Σ + d) + 2id + j(2d + 3Σ), a 6i+3,3j+2 = (a 0 + a 1 -4Σ -2d) -2i(2d + 3Σ) -j(d + 3Σ), a 6i+4,3j = (a 2 + 2Σ + 2d) + 2i(2d + 3Σ) + j(d + 3Σ), a 6i+4,3j+1 = (a 0 -4Σ -d) -2i(d + 3Σ) + jd, a 6i+4,3j+2 = (a 1 -Σ -2d) -2id -j(2d + 3Σ), a 6i+5,3j = (a 0 + a 2 -2Σ + d) + 2id + j(2d + 3Σ), a 6i+5,3j+1 = (a 0 + a 1 -5Σ -3d) -2i(2d + 3Σ) -j(d + 3Σ), a 6i+5,3j+2 = (a 1 + a 2 + 4Σ + d) + 2i(d + 3Σ) -jd.
Thus, these 18 subsequences S i 0 ,j 0 are doubly arithmetic. This completes the proof. Now, we show that there is no other sequence generating IDAO in Z. Since any (k 1 , k 2 )-IDAO is also a (k 1 k 2 , k 1 k 2 )-IDAO, we suppose that we have k 1 = k 2 = k in the sequel. The problem of determining all (k, k)-IDAO can then be converted into a system of linear equations.

Proposition 3.5. Let n be a positive integer. Let A and D be two k-tuples of elements in Z/nZ, or in Z, and let S = IAP(A, D) be a k-interlaced arithmetic progression. Then, the orbit O S is (k, k)-interlaced doubly arithmetic if and only if A and D satisfy

W k 2 W k T k T 0 k W k A T D T = 0,
where

W k = C k -I k = Circ k 0 , k 1 , . . . , k k-1 , that is the Wendt matrix of size k.
The proof of this proposition is based on the following two lemmas.

Lemma 3.6. Let n be a positive integer. Let S be a k-interlaced arithmetic progression in Z/nZ, or in Z. Then, the orbit O S = (a i,j |a i+1,j = a i,j + a i,j+1 , i ∈ N, j ∈ Z) is (k, k)interlaced doubly arithmetic if and only if we have (1): for every i 0 ∈ {0, 1, . . . , k -1} and for every i ∈ N, the row R ik+i 0 is of the same common differences as R i 0 , and (2): for every j 0 ∈ {0, 1, . . . , k -1}, the sequence (a ik,j 0 ) i∈N is an arithmetic progression.

Proof. If the orbit O S is (k, k)-interlaced doubly arithmetic, then it is clear that the assertions (1) and ( 2) are verified. Suppose now that (1) and ( 2) hold. We begin by showing (3): for every j 0 ∈ {0, 1, . . . , k-1} and for every j ∈ Z, the sequence (a ik,j 0 +jk ) i∈N is an arithmetic progression. Indeed, for every i ∈ N, we have

a ik,j 0 +jk (1)
= a ik,j 0 + j(a 0,j 0 +k -a 0,j 0 )

= a 0,j 0 + i(a k,j 0 -a 0,j 0 ) + j(a 0,j 0 +k -a 0,j 0 ) = a 0,j 0 +jk + i(a k,j 0 -a 0,j 0 ).

Moreover, since a i 0 +ik,j 0 = i 0 l=0 i 0 l a ik,j 0 +l by the local rule of the automaton, it follows that we have

a i 0 +ik,j 0 +jk (1) = a i 0 +ik,j 0 + j(a i 0 ,j 0 +k -a i 0 ,j 0 ) = i 0 l=0 i 0 l a ik,j 0 +l + j(a i 0 ,j 0 +k -a i 0 ,j 0 ) (3)
= i 0 l=0 i 0 l (a 0,j 0 +l + i(a k,j 0 +l -a 0,j 0 +l )) + j(a i 0 ,j 0 +k -a i 0 ,j 0 ) = i 0 l=0 i 0 l a 0,j 0 +l + i i 0 l=0 i 0 l a k,j 0 +l - i 0 l=0
i 0 l a 0,j 0 +l + j(a i 0 ,j 0 +k -a i 0 ,j 0 ) = a i 0 ,j 0 + i(a i 0 +k,j 0 -a i 0 ,j 0 ) + j(a i 0 ,j 0 +k -a i 0 ,j 0 ), for all i 0 , j 0 ∈ {0, 1, . . . , k -1} and for all i, j ∈ Z.

Lemma 3.7. For all i, j ∈ N such that 0 j i, we have

1. C i = C 1 i and so C ik = C k i , 2. T i = T j C i-j + C j T i-j .
Proof. The first assertion follows from the recursive definition of C i . For the second assertion, we proceed by induction on i. The result is trivial for i = 0 and for i = 1. Suppose it is true until i and prove it for i+1. It is clear for j = 0 and for j = i+1. Let j be an integer such that 1 j i. By the induction hypothesis and the recursive definition of T i+1 found in the proof of Proposition 3.2, we obtain

T i+1 = T i C 1 +C i T 1 = (T j C i-j + C j T i-j )C 1 + C i T 1 = T j C i-j+1 + C j (T i-j C 1 + C i-j T 1 ) = T j C i-j+1 + C j T i-j+1 .
We are now ready to prove Proposition 3.5.

Proof of Proposition 3.5. Let S = IAP(A, D) be a k-interlaced arithmetic progression of elements in Z/nZ, or in Z. We know that the orbit O S is (k, k)-interlaced doubly arithmetic if and only if the assertions (1) and ( 2) are satisfied by Lemma 3.6. We consider the equations (1 ′ ) and (2 ′ ):

(1 ′ ) : DW k = 0, ( 2
′ ) : AW k 2 + DT k W k = 0.
First, by Proposition 3.2, the assertions (1) and (1 ′ ) are equivalent:

(1)

P rop.3.2 ⇐⇒ DC i 0 +ik = DC i 0 , for all i ∈ N and i 0 ∈ {0, 1, . . . , k -1}, ⇐⇒ D(C ik -I k )C i 0 = 0, for all i ∈ N and i 0 ∈ {0, 1, . . . , k -1}, Lem.3.7 ⇐⇒ D(C k -I k ) i-1 l=0 C k l C i 0 = 0, for all i ∈ N and i 0 ∈ {0, 1, . . . , k -1}, ⇐⇒ DW k = 0 (1 ′ ).
Proposition 3.2 also permits to put assertion (2) in equation as follows:

(2) ⇐⇒ (a ik,0 , a ik,1 , . . . , a ik,k-1 ) i∈N is arithmetic,

P rop.3.2 ⇐⇒ (AC ik + DT ik ) i∈N is arithmetic, ⇐⇒ A(C (i+2)k -2C (i+1)k + C ik ) + D(T (i+2)k -2T (i+1)k + T ik ) = 0, for all i ∈ N.
Moreover, Lemma 3.7 leads to

C (i+2)k -2C (i+1)k + C ik = (C k 2 -2C k + I k )C ik = W k 2 C ik , and
T (i+2)k -2T (i+1)k + T ik = (T 2k C ik + C 2k T ik ) -2(T k C ik + C k T ik ) + T ik .
Finally, since DC k = D by assertion (1 ′ ), it follows that

D T (i+2)k -2T (i+1)k + T ik = D(T 2k -2T k )C ik = D(T k C k +C k T k -2T k )C ik = DT k W k C ik . Hence AW k 2 C ik + DT k W k C ik = 0
, for all i ∈ N and so we have (2 ′ ). This completes the proof.

In [START_REF] Wendt | Arithmetic studies on Fermat's "Last" Theorem which says that the equation a n = b n + c n for n > 2 does not have a solution in integers (Arithmetische Studien über den "letzten" Fermat'schen Satz, welcher aussagt, dass die Gleichung a n = b n + c n für n > 2 in ganzen Zahlen nicht auflösbar ist)[END_REF], E. Wendt investigated the resultant of X k -1 and (X +1) k -1, which corresponds to the determinant of W k . E. Lehmer was the first to prove that the determinant of W k vanishes if and only if k is divisible by 6 [START_REF] Lehmer | On a resultant connected with Fermat's last theorem[END_REF]. It is also easy to deduce from her proof that the Wendt matrix W k is of rank k if k is not divisible by 6 and of rank k -2 otherwise. Proposition 3.8.

rank(W k ) = k if k ≡ 0 (mod 6), k -2 if k ≡ 0 (mod 6).
We are now able to prove the main theorem of this section.

Proof of Theorem 3.3. If k is not divisible by 6, then the Wendt matrix W k is of rank k by Proposition 3.8. This implies that A = D = (0, . . . , 0) and thus S is the sequence of zeros. Otherwise, if k is divisible by 6, then Proposition 3.4 implies that the vector space of (k, k)-interlaced doubly arithmetic orbits is of dimension greater than or equal to 4. Moreover, since rank(W k

2 ) = rank(W k ) = k -2 by Proposition 3.8, it follows that the matrix

W k 2 W k T k T 0 k W k
is of rank greater than or equal to 2k -4. Therefore, there is no other (k, k)-IDAO than those listed in Theorem 3.3. This completes the proof.

Balanced Steinhaus figures modulo an odd number

In this section, we show that, for n odd, the projection in Z/nZ of an IDAO in Z, obtained in the previous section, contains infinitely many balanced Steinhaus figures. • every Steinhaus triangle of order m in O S , for every m ≡ 0 or -1 (mod 6n),

• every Steinhaus trapezoid of order m and of height h in O S , for every m ≡ 0 or -1 (mod 6n) and for every h ≡ m or m + 1 (mod 6n),

• every Pascal triangle of order 2m -1 in O S , for every m ≡ 0 or -1 (mod 6n),

• every Pascal trapezoid of order 2m -1 and of height h in O S , for every m ≡ 0 or -1 (mod 6n) and for every h ≡ m or m + 1 (mod 6n),

• every lozenge of order 2m -1 in O S , for every m ≡ 0 (mod 6n).

Proof. Let O S = (a i,j |a i+1,j = a i,j + a i,j+1 , i ∈ N, j ∈ Z) be the orbit associated with S.

Consider the subsequences S i 0 ,j 0 = (a i 0 +6i,j 0 +6j |i ∈ N, j ∈ Z), for i 0 and j 0 in {0, 1, 2, 3, 4, 5}. Each of these 36 subsequences is doubly arithmetic since the orbit O S is (6, 3)-interlaced doubly arithmetic by Proposition 3.4. The following -h) -1). Therefore, these trapezoids are balanced, for all m ≡ 0 or -1 (mod 6n) and for all h ≡ m or m + 1 (mod 6n). Finally, a lozenge of order 2m -1 in O S is balanced, for all m ≡ 0 (mod 6n), since it is the multiset union of a Pascal triangle of order 2m -1 and of a Steinhaus triangle of order m -1, which are both balanced in Z/nZ.

The case where a 0 = 0, a 1 = 1, a 2 = 2 and d = 1 in Z/3Z, i.e., the orbit associated with the sequence IAP((0, 1, 2), (1, 1, 1)), is illustrated in Figure 3. In this example, balanced Steinhaus figures are depicted in gray: there are a balanced Steinhaus triangle of order 18, a balanced Pascal triangle of order 35 and a balanced lozenge of order 35.

The antisymmetric case

In this section, we refine Theorem 4.1 by considering antisymmetric sequences in Z/nZ.

A finite sequence S = (a 0 , . . . , a m-1 ) of length m 1 in Z/nZ, or in Z, is said to be antisymmetric if a m-1-j = -a j for all j ∈ {0, 1, . . . , m -1}.

For examples, the sequences (1, 4, 0, 3, 6) and (2, 6, 1, 5) are antisymmetric in Z/7Z. It is known, see [START_REF] Chappelon | On a problem of Molluzzo concerning Steinhaus triangles in finite cyclic groups[END_REF], that the antisymmetry of finite sequences is preserved by the derivation process.

Proposition 5.1. Let n be a positive integer and let S = (a 0 , . . . , a m-1 ) be a finite sequence in Z/nZ, or in Z. Then, the sequence S is antisymmetric if and only if its derived sequence ∂S is also antisymmetric and a ⌊m/2⌋ + a m-⌊m/2⌋ = 0, where ⌊m/2⌋ is the floor of m/2.

Proof. We set ∂S = (b 0 , . . . , b m-2 ) = (a 0 + a 1 , . . . , a m-2 + a m-1 ). If S is antisymmetric, then ∂S is also antisymmetric since, for all j ∈ {0, 1, . . . , m -2}, we have b m-2-j = a m-2-j + a m-1-j = -a j+1 -a j = -b j . Conversely, if ∂S is antisymmetric and a ⌊m/2⌋ + a m-⌊m/2⌋ = 0, we proceed by decreasing induction on j. Since

0 0 0 0 0 1 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2 0 0 0 0 2 2 2 2 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2 0 0 0 0 2 2 2 2 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2 0 0 0 0 2 2 2 2 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2 0 0 0 0 2 2 2 2 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2 0 0 0 0 2 2 2 2 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2 0 0 0 0 2 2 2 2 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2 0 0 0 0 2 2 2 2 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2 0 0 0 0 2 2 2 2 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2 0 0 0 0 2 2 2 2 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 2 2 2 2 2 1 1 1 1 1 0 0 0 0 0 0 0 0 2 2 2 2 1 1 1 1 1 1 1 1 0 0 0 0 2 2 2 2 2 2 2 2 2 1 1 1 1 1 0 0 0 0 0 0 0 0 2 2 2 2 1 1 1 1 1 1 1 1 0 0 0 0 2 2 2 2 2 2 2 2 2 1 1 1 1 1 0 0 0 0 0 0 0 0 2 2 2 2 1 1 1 1 1 1 1 1 0 0 0 0 2 2 2 2 2 2 2 2 2 1 1 1 1 1 0 0 0 0 0 0 0 0 2 2 2 2 1 1 1 1 1 1 1 1 0 0 0 0 2 2 2 2 2 2 2 2 2 1 1 1 1 1 0 0 0 0 0 0 0 0 2 2 2 2 1 1 1 1 1 1 1 1 0 0 0 0 2 2 2 2 2 2 2 2 2 1 1 1 1 1 0 0 0 0 0 0 0 0 2 2 2 2 1 1 1 1 1 1 1 1 0 0 0 0 2 2 2 2 2 2 2 2 2 1 1 1 1 1 0 0 0 0 0 0 0 0 2 2 2 2 1 1 1 1 1 1 1 1 0 0 0 0 2 2 2 2 2 2 2 2 2 1 1 1 1 1 0 0 0 0 0 0 0 0 2 2 2 2 1 1 1 1 1 1 1 1 0 0 0 0 2 2 2 2 0 0 0 0 0 1 1 1 1 0 0 0 0 2 2 2 2 0 0 0 0 2 2 2 2 1 1 1 1 2 2 2 2 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 2 2 2 2 0 0 0 0 2 2 2 2 1 1 1 1 2 2 2 2 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 2 2 2 2 0 0 0 0 2 2 2 2 1 1 1 1 2 2 2 2 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 2 2 2 2 0 0 0 0 2 2 2 2 1 1 1 1 2 2 2 2 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 2 2 2 2 0 0 0 0 2 2 2 2 1 1 1 1 2 2 2 2 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 2 2 2 2 0 0 0 0 2 2 2 2 1 1 1 1 2 2 2 2 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 2 2 2 2 0 0 0 0 2 2 2 2 1 1 1 1 2 2 2 2 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 2 2 2 2 0 0 0 0 2 2 2 2 1 1 1 1 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 0 0 0 0 0 0 0 0 1 1 1 1 2 2 2 2 2 2 2 2 2 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 0 0 0 0 0 0 0 0 1 1 1 1 2 2 2 2 2 2 2 2 2 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 0 0 0 0 0 0 0 0 1 1 1 1 2 2 2 2 2 2 2 2 2 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 0 0 0 0 0 0 0 0 1 1 1 1 2 2 2 2 2 2 2 2 2 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 0 0 0 0 0 0 0 0 1 1 1 1 2 2 2 2 2 2 2 2 2 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 0 0 0 0 0 0 0 0 1 1 1 1 2 2 2 2 2 2 2 2 2 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 0 0 0 0 0 0 0 0 1 1 1 1 2 2 2 2 2 2 2 2 2 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 0 0 0 0 0 0 0 0 1 1 1 1
m-2-j k=j b k = m-2-j k=j (a k + a k+1 ) = a j + 2 m-2-j k=j+1 a k + a m-1-j ,
it follows that

a j + a m-1-j = m-2-j k=j b k -2 m-2-j k=j+1 a k = 0,
by the decreasing induction hypothesis. This completes the proof.

The main interest of the antisymmetric sequences in Z/nZ is that their multiplicity function admits a certain symmetry. Indeed, it is clear that, if S is an antisymmetric sequence in Z/nZ, then its multiplicity function m S satisfies m S (x) = m S (-x), for all x in Z/nZ. The same equality appears for the multiplicity function of Steinhaus or Pascal triangles generated by antisymmetric sequences.

Proposition 5.2. Let n be a positive integer and let S be an antisymmetric sequence of length m 1 in Z/nZ. Then, we have m ∇S (x) = m ∇S (-x) for all x ∈ Z/nZ.

Proof. Since each derived sequence

∂ i S, for i ∈ {0, 1, . . . , m -1}, is antisymmetric by Proposition 5.1, it follows that m ∇S (x) = m-1 i=0 m ∂ i S (x) = m-1 i=0 m ∂ i S (-x) = m ∇S (-x) for all x ∈ Z/nZ. Proposition 5.3.
Let n be a positive integer and let S be an antisymmetric sequence of length 2m -1 1 in Z/nZ. Then, we have m ∆S (x) = m ∆S (-x) for all x ∈ Z/nZ. Now, for n odd, we determine all the sequences generating IDAO in Z and such that the first 3n terms of their projection in Z/nZ are antisymmetric.

For every doubly infinite sequence S = (a j ) j∈Z in Z/nZ, or in Z, and for all integers j 0 and j 1 such that j 0 j 1 , we let S[j 0 , j 1 ] denote the subsequence of S indexed between j 0 and j 1 , that is S[j 0 , j 1 ] = (a j 0 , a j 0 +1 , . . . , a j 1 ). Proposition 5.4. Let n ∈ N be odd. Let a 0 , a 1 , a 2 , d ∈ Z/nZ and let Σ = a 0 + a 1 + a 2 . Then, the subsequence ((a,(d,d)

S m = IAP((a 0 , a 1 , a 2 ), (d, -2d -3Σ, d + 3Σ))[0, m -1], of length m ≡ 0 (mod 3n) in Z/nZ, is antisymmetric if and only if Σ = 0 and a 1 = -d, i.e., if we have S m = IAP
)[0, m -1]. Proof. Set m = 3λn and S m = IAP((a 0 , a 1 , a 2 ), (d, -2d -3Σ, d + 3Σ))[0, m -1] = (a 0 , . . . , a m-1 ) in Z/nZ. If S m is antisymmetric, then its terms a j must satisfy    a 3j + a 3(λn-j-1)+2 = 0 a 3j+1 + a 3(λn-j-1)+1 = 0 a 3j+2 + a 3(λn-j-1) = 0 ⇐⇒    a 0 + a 2 -d -3(j + 1)Σ = 0 2a 1 + 2d + 3Σ = 0 a 0 + a 2 -d + 3jΣ = 0
, for all 0 j n-1.

This leads to a 1 = -d, a 2 = d -a 0 and Σ = 0, since n is odd, and thus S m = IAP((a 0 , -d, d -a 0 ), (d,d))[0, m -1], as announced.

Let n be an odd number and let a and d be two elements in Z/nZ with d invertible. We refine Theorem 4.1 by considering the orbit O S of the sequence S = IAP (( a,da),(d,d)). Let ∇ 0 be the Steinhaus triangle, of order 3n, generated by the first 3n terms of S and let ∆ 0 be the Pascal triangle, of order 6n-3, adjacent with ∇ 0 as depicted in Figure 4, that are ∇ 0 = ∇S[0, 3n -1] and ∆ 0 = ∆∂S [1, 6n -3].

∇ 0 ∆ 0 Figure 4: ∇ 0 = ∇S[0, 3n -1] and ∆ 0 = ∆∂S[1, 6n -3].
We begin by showing that these triangles are balanced in Z/nZ.

∂ 3i S = (-1) i IAP((a -id, -(i + 1)d, (2i + 1)d -a), (d, -2d, d)), ∂ 3i+1 S = (-1) i IAP((a -(2i + 1)d, id -a, (i + 2)d), (-d, -d, 2d)), ∂ 3i+2 S = (-1) i IAP((-(i + 1)d, (2i + 2)d -a, a -id), (-2d, d, d)),
for all i ∈ N, it follows that ∂ 3n S = -S. Moreover, the orbit O S is (6, 3)-interlaced doubly arithmetic and thus each row (resp. each diagonal) of O S is periodic of period 3n (resp. of period 6n). This leads to the following periodic decomposition of the orbit O S into triangles ∇ 0 and ∆ 0 :

∇ 0 ∇ 0 ∇ 0 ∇ 0 ∇ 0 ∇ 0 ∇ 0 ∇ 0 ∇ 0 -∇ 0 -∇ 0 -∇ 0 -∇ 0 -∇ 0 -∇ 0 -∇ 0 -∇ 0 ∇ 0 ∇ 0 ∇ 0 ∇ 0 ∇ 0 ∇ 0 ∇ 0 ∇ 0 ∇ 0 ∆ 0 ∆ 0 ∆ 0 ∆ 0 ∆ 0 ∆ 0 ∆ 0 ∆ 0 -∆ 0 -∆ 0 -∆ 0 -∆ 0 -∆ 0 -∆ 0 -∆ 0 -∆ 0 -∆ 0 ∆ 0 ∆ 0 ∆ 0 ∆ 0 ∆ 0 ∆ 0 ∆ 0 ∆ 0
Particularly, the Steinhaus triangle ∇S[0, 6n -1], of order 6n, and the Pascal triangle ∆∂S[1, 12n -3], of order 12n -3, which are balanced by Theorem 4.1, admit the decomposition:

∇S[0, 6n -1] = ∇ 0 ∇ 0 -∇ 0 ∆ 0 and ∆∂S[1, 12n -3] = ∆ 0 -∇ 0 -∆ 0 -∆ 0 .
The sequences S[0, 3n -1] and ∂S[1, 6n -3] are antisymmetric in Z/nZ, by Propositions 5.4 and 5.1, and thus we deduce, from Propositions 5.2 and 5.3, that the multiplicity functions m -∇ 0 and m -∆ 0 correspond to m ∇ 0 and m ∆ 0 , since

m ∇ 0 (x) = m ∇ 0 (-x) = m -∇ 0 (x) and m ∆ 0 (x) = m ∆ 0 (-x) = m -∆ 0 (x)
, for all x ∈ Z/nZ. Finally, the multiplicity functions m ∇ 0 and m ∆ 0 are constant because they are solutions of the following system of equations

3m ∇ 0 + m ∆ 0 = m ∇S[0,3n-1] = 1 n 3n + 1 2 , m ∇ 0 + 3m ∆ 0 = m ∆∂S[1,6n-3] = 1 n 3n 2 .
Therefore, the elementary triangles ∇ 0 and ∆ 0 are balanced in Z/nZ.

Finally, we obtain the refinement of Theorem 4.1 announced above. • the Steinhaus triangles ∇S[0, 3λn -1] of order 3λn, and ∇∂S[0, 3λn -2] of order 3λn -1, for every integer λ 1,

• the Steinhaus trapezoid ST(S[0, 3λn -1], h) of order 3λn and of height h, for every integer λ 1 and for every h ≡ 0 or 1 (mod 3n); the Steinhaus trapezoid ST(∂S[0, 3λn -2], h) of order 3λn -1 and of height h, for every integer λ 1 and for every h ≡ -1 or 0 (mod 3n),

• the Pascal triangle ∆∂S[-m, m -2] of order 2m -1, for every m ≡ 0 or -1 (mod 3n),

• the Pascal trapezoid PT(∂S[-m, m -2], h) of order 2m -1 and of height h, for every m ≡ 0 or -1 (mod 3n) and for every h ≡ m or m + 1 (mod 3n),

• the lozenge ♦∂S[-m, m -2] of order 2m -1, for every m ≡ 0 (mod 3n).

Proof. For every integer λ 1, the Steinhaus triangle ∇S[0, 3λn-1] and the Pascal triangle ∆∂S[-3λn, 3λn -2] are balanced because they are multiset unions of the elementary triangles ∇ 0 , -∇ 0 , ∆ 0 and -∆ 0 , which are balanced in Z/nZ by Proposition 5.5. The Steinhaus triangle ∇∂S[0, 3λn -2] is balanced, since it is obtained from ∇S[0, 3λn -1] by rejecting the first row, which is a 3-interlaced arithmetic progression with invertible common differences and of length 3λn and thus contains 3λ times each element of Z/nZ. Similarly, the Pascal triangle ∆∂S[-3λn + 1, 3λn -3] is balanced, since it is obtained from ∆∂S[-3λn, 3λn-2] by rejecting the last row, which is also balanced. The Steinhaus trapezoids (resp. the Pascal trapezoids) listed in this theorem can be seen as multiset differences of Steinhaus triangles (resp. Pascal triangles). Namely, we have

ST(S[0, 3λn -1], h) = ∇S[0, 3λn -1] \ ∇∂ h S[0, 3λn -1 -h], ST(∂S[0, 3λn -2], h) = ∇∂S[0, 3λn -2] \ ∇∂ h+1 S[0, 3λn -2 -h], PT(∂S[-m, m -2], h) = ∆∂S[-m, m -2] \ ∆∂S[-m + h, m -2 -h].
We have shown that these triangles are balanced. Therefore the trapezoids of this theorem also are balanced. Finally, the lozenge ♦∂S[-3λn, 3λn -2] is the multiset union of the Pascal triangle ∆∂S[-3λn, 3λn -2] and the Steinhaus triangle ∇(-1) λ ∂S[-3λn, -2] = ∇(-1) λ ∂S[0, 3λn -2], which are balanced, for all integers λ 1.

6 The universal sequence modulo an odd number

Let US = IAP((0, -1, 1), (1, -2, 1)) be the universal sequence of integers introduced in Section 1. In this section, we refine Theorem 5.6 by studying this universal sequence modulo an odd number n, namely the sequence

S = dπ n (US) = IAP((0, -d, d), (d, -2d, d)),
where d is invertible in Z/nZ. It corresponds to the sequence S of Theorem 5.6 with a = 0. First, each element of its orbit O S = (a i,j |a i+1,j = a i,j + a i,j+1 , i ∈ N, j ∈ Z) can be expressed as a function of d.

Proposition 6.1. Let n ∈ N be odd and let d ∈ Z/nZ be invertible. Consider the orbit

O S = (a i,j |a i+1,j = a i,j + a i,j+1 , i ∈ N, j ∈ Z) of the sequence S = IAP((0, -d, d), (d, -2d, d))
in Z/nZ. Then, for all i, j ∈ N, we have

a i,j = (-1) i k>0 k j + 2i -k (-1) k (k -i)d.
Proof. We begin by proving this equality for i = 0. Let (u j ) j∈N and (v j ) j∈N be the sequences, in Z/nZ, defined by u j = k>0 k j-k (-1) k kd and v j = k>0 k j-k (-1) k d, for all j ∈ N. Then, for every integer j 2, we have

u j = k>0 k -1 j -k -1 + k -1 j -k (-1) k (k-1)d+ k>0 k j -k (-1) k d = -u j-2 -u j-1 +v j .
In the same way, we can prove that the sequence (v j ) j∈N satisfies the relation v j + v j-1 + v j-2 = 0, for all integers j 2. It follows that v 3j = d, v 3j+1 = -d and v 3j+2 = 0, for all j ∈ N. We complete the proof by induction on j. If we suppose that u 3j = jd, u 3j+1 = -(1 + 2j)d and u 3j+2 = (1 + j)d, then we obtain that u 3j+3 = -u 3j+2 -u 3j+1 + v 3j+3 = (j +1)d, u 3j+4 = -u 3j+3 -u 3j+2 +v 3j+4 = -(3+2j)d and u 3j+5 = -u 3j+4 -u 3j+3 +v 3j+5 = (2 + j)d. Therefore, we have a 0,j = u j = k>0 k j-k (-1) k kd, for all j ∈ N, and this completes the proof for i = 0. Finally, for all integers i, j 1, we obtain

a i,j = i l=0 i l a 0,j+l = i l=0 i l k>0 k j + l -k (-1) k kd = k>0 i l=0 i k k j + l -k (-1) k kd = k>0 i + k j + i -k (-1) k kd = (-1) i k>i k j + 2i -k (-1) k (k -i)d = (-1) i k>0 k j + 2i -k (-1) k (k -i)d.
In the sequel of this section, we suppose that n is an odd number and that S is the universal sequence modulo n, that is S = IAP((0, -d, d), (d, -2d, d)), where d is an invertible element in Z/nZ. Let ∇ 1 , ∇ 2 and ∇ 3 be the Steinhaus triangles of order n associated with the sequences S[0, n -1], S[n, 2n -1] and S[2n, 3n -1] respectively and let ∆ 1 , ∆ 2 and ∆ 3 be their adjacent Pascal triangles of order 2n -3, as depicted in Figure 5, that are:

∇ 1 = ∇S[0, n -1], ∇ 2 = ∇S[n, 2n -1], ∇ 3 = ∇S[2n, 3n -1], ∆ 1 = ∆∂S[1, 2n -3], ∆ 2 = ∆∂S[n + 1, 3n -3] and ∆ 3 = ∆∂S[2n + 1, 4n -3]. ∇ 1 ∇ 2 ∇ 3 ∆ 1 ∆ 2 ∆ 3
∇ 1 = ∇S[0, n -1], ∇ 2 = ∇S[n, 2n -1], ∇ 3 = ∇S[2n, 3n -1], ∆ 1 = ∆∂S[1, 2n -3], ∆ 2 = ∆∂S[n+1, 3n-3] and ∆ 3 = ∆∂S[2n+1, 4n-3]. Then, the multisets ∇ 2 , ∇ 1 ∇ 3 , ∆ 3 and ∆ 1 ∆ 2 are balanced in Z/nZ.
The proof of this proposition is based on the following lemma.

A finite sequence S = (a 0 , . . . , a m-1 ) of length m 1 in Z/nZ is said to be symmetric if a j = a m-1-j for all j ∈ {0, 1, . . . , m -1}.

Lemma 6.3. Let n ∈ N be odd and let ∇ = {a i,j |0 i m -1, 0 j m -1 -i} be a Steinhaus triangle of order m 1 in Z/nZ. Then, the anti-diagonals AD 2j and AD 2j+1 of ∇ are respectively antisymmetric and symmetric for all integers j such that 0 2j 2j + 1 m -1 if, and only if, we have a i,i = 0 for all i ∈ {0, 1, . . . , (m -1)/2}.

Proof. For every i ∈ {0, 1, . . . , (m -1)/2}, if the sequence AD 2i = (a 0,2i , . . . , a 2i,0 ) is antisymmetric, then it follows that we have 2a i,i = 0 and thus a i,i = 0, since n is odd. Conversely, suppose now that a i,i = 0 for all i ∈ {0, 1, . . . , (m -1)/2}. We proceed by induction on j. For j = 0, it is clear that AD 0 = (a 0,0 ) = (0) is antisymmetric and that AD 1 = (a 0,1 , a 1,0 ) = (a 1 , a 1 ) is symmetric. Suppose that the result is true for j -1, i.e., that the sequences AD 2j-2 and AD 2j-1 are respectively antisymmetric and symmetric, and prove it for j. We begin by showing that a j-k,j+k = -a j+k,j-k for all k ∈ {0, 1, . . . , j}. For k = 0, it comes from hypothesis a j,j = 0. Suppose it is true for all integers in {0, . . . , k-1}. Since a j-k,j+k-1 = a j+k-1,j-k by symmetry of AD 2j-1 , we obtain that a j-k,j+k = a j-(k-1),j+k-1 -a j-k,j+k-1 = -a j+k-1,j-(k-1) -a j+k-1,j-k = -a j+k,j-k and thus AD 2j is antisymmetric. We now prove that a j-k,j+1+k = a j+1+k,j-k for all k ∈ {0, 1, . . . , j}. For k = 0, it follows from the equality a j+1,j = a j,j +a j,j+1 = a j,j+1 . Suppose it is true for all integers in {0, . . . , k -1}. Since a j-k,j+k = -a j+k,j-k by antisymmetry of AD 2j , we have a j-k,j+k+1 = a j-k+1,j+k -a j-k,j+k = a j+k,j-(k-1) + a j+k,j-k = a j+k+1,j-k and thus AD 2j+1 is symmetric. This concludes the proof.

Proof of Proposition 6.2. First, we consider the Steinhaus triangle ∇ 0 = ∇S[0, 3n -1] of order 3n and the Pascal triangle ∆ 0 = ∆∂S [1, 6n-3] of order 6n-3, which are balanced by Proposition 5.5. If we denote by O S = (a i,j |a i+1,j = a i,j + a i,j+1 , i ∈ N, j ∈ Z) the orbit associated with the universal sequence S = IAP((0, -d, d), (d, -2d, d)) in Z/nZ, then Proposition 6.1 implies that we have a n,j = -a 0,2n+j , a 2n,j = a 0,n+j and a 3n,j = -a 0,j for all j ∈ Z. Moreover, we have a 0,3n+j = a 0,j for all j ∈ Z, since the sequence S is periodic of period 3n. This leads to the following decomposition of ∇ 0 and ∆ 0 into elementary triangles ∇ 1 , ∇ 2 , ∇ 3 , ∆ 1 , ∆ 2 and ∆ 3 :

∇ 0 = ∇ 1 ∇ 2 ∇ 3 ∆ 1 ∆ 2 -∇ 3 -∇ 1 -∆ 3 ∇ 2 and ∆ 0 = ∆ 3 -∆ 1 -∆ 2 -∇ 2 ∆ 2 ∆ 3 ∆ 1 ∇ 3 ∇ 1 .
For every k ∈ {0, 1, 2, 3}, we denote by D j (∇ k ) and AD j (∇ k ) the jth diagonal and the jth anti-diagonal of ∇ k , for every j ∈ {0, 1, . . . , n -1}, and by D j (∆ k ) and AD j (∆ k ) the jth diagonal and the jth anti-diagonal of ∆ k , for every j ∈ {0, 1, . . . , n -2}. Since we have a i,i = 0 for all i ∈ N, from the general expression of a i,j appearing in the proof of Proposition 3.4, it follows, from Lemma 6.3, that the sequences AD 2j (∇ 0 ) and AD 2j+1 (∇ 0 ) are respectively antisymmetric and symmetric, for all integers j such that 0 2j 2j + 1 3n -1. This implies the following equalities on the multiplicity functions of the anti-diagonals of ∇ 2 and ∇ 3 :

m AD 2j (∇ 3 ) (x) = m AD 2j (∇ 2 ) (-x) and m AD 2j+1 (∇ 3 ) (x) = m AD 2j+1 (∇ 2 ) (x),
for all x ∈ Z/nZ and for all integers j such that 0 2j 2j + 1 n -1. Moreover, we know, from Proposition 5.4, that the sequence S[0, 3n -1] is antisymmetric and, thus, all the rows of ∇ 0 are also antisymmetric by Proposition 5.1. Therefore, we have

m AD j (∇ 3 ) (x) = m D n-1-j (∇ 1 ) (-x) and m AD j (∇ 2 ) (x) = m D n-1-j (∇ 2 ) (-x),
for all x ∈ Z/nZ and for all j ∈ {0, 1, . . . , n -1}. This leads to the equality for all x ∈ Z/nZ. Similarly, if we consider the diagonals and the anti-diagonals of the triangles ∆ 1 , ∆ 2 and -∆ 3 , as depicted in Figure 6, then we obtain that m ∆ 1 + m ∆ 2 = 2m -∆ 3 . The antisymmetry in ∇ 0 also implies the following equalities:

m ∇ 1 (x)+m ∇ 3 (x) = n-1 j=0 m D j (∇ 1 ) (x) + n-1 j=0 m AD j (∇ 3 ) (x) = n-1 j=0 m AD n-1-j (∇ 3 ) (-x) + n-1 j=0 m AD j (∇ 3 ) (x) = n-1 j=0 m AD j (∇ 3 ) (-x) + m AD j (∇ 3 ) (x) = n-1 j=0 m AD j (∇ 2 ) (-x) + m AD j (∇ 2 ) (x) = n-1 j=0 m AD j (∇ 2 ) (x) + n-1 j=0 m AD n-1-j (∇ 2 ) (-x) = 2m ∇ 2 (x), + + + + + + + ± ± ± ± ± ± ± ± ∓ ∓ ∓ ∓ ∓ ∓ ∓ - - - - - - - + + + + + ± ± ± ± ± ± ∓ ∓ ∓ ∓ ∓ - - - - - 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ∇ 1 ∇ 2 ∇ 3 ∆ 1 ∆ 2 -∇ 3 -∇ 1 -∆ 3 ∇ 2
m ∇ 1 = m -∇ 3 , m ∇ 3 = m -∇ 1 , m ∇ 2 = m -∇ 2 , m ∆ 1 = m -∆ 2 , m ∆ 2 = m -∆ 1 and m ∆ 3 = m -∆ 3 .
Therefore, the multiplicity functions of these elementary triangles verify the following equations:

m ∇ 1 + m ∇ 3 = 2m ∇ 2 , m ∆ 1 + m ∆ 2 = 2m ∆ 3 .
Finally, since the triangles ∇ 0 and ∆ 0 are balanced in Z/nZ, it follows that the multiplicity functions m ∇ 2 and m ∆ 3 are solutions of the following system of equations

6m ∇ 2 + 3m ∆ 3 = m ∇ 0 = 1 n 3n + 1 2 , 3m ∇ 2 + 6m ∆ 3 = m ∆ 0 = 1 n 3n 2 .
We conclude that the triangles ∇ 2 , ∆ 3 and the multisets ∇ 1 ∇ 3 and ∆ 1 ∆ 2 are balanced.

We are now ready to prove Theorem 1.3, the main result of this paper. for every m ≡ -1 (mod 3n),

• the Steinhaus trapezoids ST(S[m, 2m -1], h), for every m ≡ 0 (mod n) and for every h ≡ 0 (mod n) or h ≡ m + 1 (mod 3n), and ST(∂S[0, m -1], h), for every m ≡ -1 (mod 3n) and for every h ≡ -1 (mod n) or h ≡ 0 (mod 3n),

• the Pascal triangle ∆∂S[-m, m -2], for every m ≡ -1 (mod n) or m ≡ 0 (mod 3n),

• the Pascal trapezoid PT(∂S[-m, m -2], h), for every m ≡ -1 (mod n) or m ≡ 0 (mod 3n) and for every h ≡ m (mod n) or h ≡ m + 1 (mod 3n),

• the lozenge ♦∂S[-m, m -2], for every m ≡ 0 (mod n).

Proof.

m ∇S[(3λ+2)n,(6λ+4)n-1] = (3λ + 2)m ∇ 2 + (3λ + 1)m ∆ 3 + m ∇S[(3λ+1)n,(6λ+2)n-1] .
This completes the proof that the Steinhaus triangle ∇S[m, 2m -1] is balanced for all m ≡ 0 (mod n). A similar decomposition shows that the Pascal triangle ∆∂S[-m, m-2] is balanced for all m ≡ -1 (mod n). First, we know, from Theorem 5.6, that the Pascal triangles ∆∂S[-3λn, 3λn -2], of order 6λn -1, and ∆∂S[-3λn + 1, 3λn -3], of order 6λn -3, are balanced in Z/nZ. The other cases come from the decomposition into elementary triangles, as depicted in Figure 8, which implies the following equalities:

m ∆∂S[-(3λ+1)n+1,(3λ+1)n-3] = 3λm ∇ 2 + (3λ + 1)m ∆ 3 + m ∆∂S[-3λn+1,3λn-3] , m ∆∂S[-(3λ+2)n+1,(3λ+2)n-3] = (3λ + 1)m ∇ 2 + (3λ + 2)m ∆ 3 + m ∆∂S[-(3λ+1)n+1,(3λ+1)n-3] .
The Steinhaus trapezoids (resp. the Pascal trapezoids) listed in this theorem can be seen as multiset differences of Steinhaus triangles (resp. Pascal triangles). Namely, we have

ST(S[m, 2m -1], h) = ∇S[m, 2m -1] \ ∇∂ h S[m, 2m -1 -h], ST(∂S[0, m -1], h) = ∇∂S[0, m -1] \ ∇∂ h+1 S[0, m -1 -h], PT(∂S[-m, m -2], h) = ∆∂S[-m, m -2] \ ∆∂S[-m + h, m -2 -h].
We have shown that these triangles are balanced. Therefore the trapezoids of this theorem also are balanced.

Conclusions and open problems

In this section, we analyse the results about the generalized Molluzzo problem obtained in this paper and two possible extensions of this work are proposed.

Conclusions on the generalized Molluzzo problem

As listed in Theorem 1. and since the set of all the integers m such that the binomial coefficient m+1 2 is divisible by n is an union of 2 ω(n) classes of integers modulo n, where ω(n) is the number of distinct prime factors of n, including the classes of 0 and -1, we have proved, in this paper, that there exist balanced Steinhaus triangles for at least 2/(3.2 ω(n)-1 ) of the admissible orders. Particularly, in the case where n is an odd prime power, this proportion becomes 2/3. In [START_REF] Chappelon | On a problem of Molluzzo concerning Steinhaus triangles in finite cyclic groups[END_REF], the author proved that arithmetic progressions with invertible common difference generate balanced Steinhaus triangles for 1/(2 ω(n)-1 β(n)) of the admissible orders, where β(n) is the order of 2 n in the multiplicative quotient group (Z/nZ) * /{-1, 1}. This completely solved the Molluzzo problem in Z/3 k Z for all k 1. A new proof of this result, shorter and based on doubly arithmetic triangles, will appear in a forthcoming paper. For Pascal triangles, the proportion of balanced Pascal triangles that we have highlighted is the same: 2/(3.2 ω(n)-1 ) for every odd number n and, thus, 2/3 if n is an odd prime power. Finally, for lozenges, since a lozenge of order 2m -1 has cardinality m 2 , the orbit of the universal sequence contains balanced lozenges for all admissible orders in Z/nZ, in the case where n is a square-free odd number. This completely solves Problem 1.2 for lozenges in the squarefree odd case.

∇ 2 ∇ 2 ∇ 2 ∇ 2 ∇ 3 ∇ 3 ∇ 3 ∇ 1 ∇ 1 ∇ 1 ∆ 2 ∆ 2 ∆ 2 ∆ 3 ∆ 3 ∆ 3 ∆ 1 ∆ 1 ∆ 1 -∇ 1 -∇ 1 -∇ 1 -∇ 2 -∇ 2 -∇ 2 -∇ 3 -∇ 3 -∇ 3 -∆ 1 -∆ 1 -∆ 1 -∆ 2 -∆ 2 -∆ 2 -∆ 3 -∆ 3 ∇ 3 ∇ 3 ∇ 3 ∇ 1 ∇ 1 ∇ 1 ∇ 2 ∇ 2 ∆ 3 ∆ 3 ∆ 3 ∆ 1 ∆ 1 ∆ 2 ∆ 2 -∇ 2 -∇ 2 -∇ 2 -∇ 3 -∇ 3 -∇ 1 -∇ 1 -∆ 2 -∆ 2 -∆ 3 -∆ 3 -∆ 1 -∆ 1 ∇S[3λn, 6λn -1]
∇ 1 ∇ 1 ∇ 2 ∇ 2 ∇ 3 ∇ 3 ∆ 3 ∆ 3 ∆ 3 ∆ 1 ∆ 1 ∆ 2 ∆ 2 -∇ 2 -∇ 2 -∇ 2 -∇ 3 -∇ 3 -∇ 1 -∇ 1 -∆ 1 -∆ 1 -∆ 1 -∆ 2 -∆ 2 -∆ 2 -∆ 3 -∆ 3 ∇ 3 ∇ 3 ∇ 3 ∇ 1 ∇ 1 ∇ 1 ∇ 2 ∇ 2 ∆ 2 ∆ 2 ∆ 2 ∆ 3 ∆ 3 ∆ 3 ∆ 1 ∆ 1 ∆ 1 -∇ 1 -∇ 1 -∇ 1 -∇ 2 -∇ 2 -∇ 2 -∇ 3 -∇ 3 -∇ 3 -∆ 3 -∆ 3 -∆ 3 -∆ 3 -∆ 1 -∆ 1 -∆ 1 -∆ 2 -∆ 2 -∆ 2 ∆∂S[-3λn + 1, 3λn -3]

Additive cellular automata

Other derivation maps can be considered. For all positive integers n and r and for every (2r + 1)-tuple of integers W = (ω -r , . . . , ω 0 , . . . , ω r ), we define the derivation map ∂ W by ∂ W (a j ) j∈Z = Finally, since there exist balanced (0, 1, 1)-Steinhaus triangles of order m for every m ≡ 0 (mod n) or m ≡ -1 (mod 3n), in Z/nZ with n odd, then there exist balanced (0, -1, 1) and (0, 1, -1)-Steinhaus triangles of the same orders in Z/nZ. For an odd prime power n, this corresponds to 2/3 of the admissible orders. Similarly, there exist balanced (0, -1, 1) and (0, 1, -1)-Pascal triangles of order 2m -1 for every m ≡ -1 (mod n) or m ≡ 0 (mod 3n), in Z/nZ with n odd. This also corresponds to 2/3 of the admissible orders, in the case where n is an odd prime power.

Figure 1 :

 1 Figure 1: Examples of Steinhaus figures in Z/5Z: the Steinhaus triangle ∇(2, 4, 3, 1, 1), the Pascal triangle ∆(4, 2, 1, 3, 0, 2, 4, 1, 3), the lozenge ♦(4, 4, 2, 4, 1, 1, 0), the Steinhaus trapezoid ST((1, 1, 4, 1, 1, 3, 4), 4) and the Pascal trapezoid PT((2, 0, 3, 3, 3, 3, 4, 1, 0, 0, 1, 4, 1), 4).

2 Figure 2 :

 22 Figure 2: The doubly arithmetic triangle DAT(0, 8, 1, 5) in Z/15Z.

Theorem 4 . 1 .

 41 Let n ∈ N be odd and let a 0 , a 1 , a 2 , d ∈ Z/nZ. Define Σ := a 0 + a 1 + a 2 . If d, d + 3Σ, and 2d + 3Σ are invertible, then, the following Steinhaus figures, contained in the orbit of S = IAP((a 0 , a 1 , a 2 ), (d, -2d -3Σ, d + 3Σ)), are balanced:

Figure 3 :

 3 Figure 3: Balanced Steinhaus figures in the orbit of IAP((0, 1, 2), (1, 1, 1)) in Z/3Z.

Proposition 5 . 5 .

 55 Let n ∈ N be odd and let a, d ∈ Z/nZ with d invertible. Consider the 3-interlaced arithmetic progression S = IAP((a, -d, d -a)(d, -2d, d)). Then, the triangles ∇ 0 = ∇S[0, 3n -1] and ∆ 0 = ∆∂S[1, 6n -3] are balanced in Z/nZ. Proof. First, since the derived sequences of S = IAP((a, -d, d -a), (d, -2d, d)) are:

Theorem 5 . 6 .

 56 Let n ∈ N be odd and let a, d ∈ Z/nZ with d invertible. Then, the following Steinhaus figures, contained in the orbit of S = IAP((a, -d, d -a), (d, -2d, d)), are balanced:

Figure 5 :

 5 Figure 5: The elementary triangles ∇ 1 , ∇ 2 , ∇ 3 , ∆ 1 , ∆ 2 and ∆ 3 .We begin by showing that these triangles, or unions of them, are balanced in Z/nZ. Proposition 6.2. Let n ∈ N be odd and let d ∈ Z/nZ be invertible. Consider the universal sequence S = IAP((0, -d, d), (d, -2d, d)) modulo n and the elementary triangles∇ 1 = ∇S[0, n -1], ∇ 2 = ∇S[n, 2n -1], ∇ 3 = ∇S[2n, 3n -1], ∆ 1 = ∆∂S[1, 2n -3], ∆ 2 = ∆∂S[n+1, 3n-3] and ∆ 3 = ∆∂S[2n+1, 4n-3]. Then, the multisets ∇ 2 , ∇ 1 ∇ 3 , ∆ 3 and ∆ 1 ∆ 2 are balanced in Z/nZ.

Figure 6 :

 6 Figure 6: The Steinhaus triangle ∇ 0 .

Theorem 6 . 4 .

 64 Let n ∈ N be odd and let d ∈ Z/nZ be invertible. Then, the following Steinhaus figures, contained in the orbit associated with the universal sequence S = IAP((0, -d, d), (d, -2d, d)) in Z/nZ, are balanced:• the Steinhaus triangles ∇S[m, 2m-1], for every m ≡ 0 (mod n), and ∇∂S[0, m-1],

  Finally, the lozenge ♦∂S[-m + 1, m -2] is the multiset union of the Pascal triangle ∆∂S[-m + 1, m -3] and of the Steinhaus triangle (-1) m ∇S[m, 2m -1], which are balanced in Z/nZ for all m ≡ 0 (mod n).

  3 and detailed in Theorem 6.4, there exist, for every odd number n, infinitely many balanced figures in Z/nZ, for each kind of figure. These results partially solve Problem 1.2, the generalized Molluzzo problem. For Steinhaus triangles, since a Steinhaus triangle of order m has cardinality m+1 2

Figure 7 :

 7 Figure 7: The Steinhaus triangle ∇S[m, 2m -1] for m ≡ 0 (mod n).

Figure 8 :

 8 Figure 8: The Pascal triangle ∆∂S[-m, m -2] for m ≡ -1 (mod n).

Problem 7 . 1 . 1 , 1 ,

 7111 infinite sequence (a j ) j∈Z in Z/nZ. Then, the derivation map ∂ of previous sections corresponds to ∂ (0,1,1) . Now, we naturally wonder, for every (2r + 1)-tuple of integers W , if there exist balanced Steinhaus figures in the additive cellular automaton associated with the derivation map ∂ W in Z/nZ. Let n and r be two positive integers and let W be a (2r+1)-tuple of integers. Do balanced Steinhaus figures exist in the additive cellular automaton associated with the derivation map ∂ W in Z/nZ? Consider the simpler case W = (0, ω 0 , ω 1 ) in the sequel and denote by ∇ W S the W -Steinhaus triangle and by ∆ W S the W -Pascal triangle associated with a finite sequence S in Z/nZ. Then, for every odd number n and for every invertible d ∈ Z/nZ, the universal sequence S = IAP((0, -d, d), (d, -2d, d)), in Z/nZ, has a (0, 1, 1)-orbit which contains infinitely many balanced (0, 1, -1)-Steinhaus and Pascal triangles and infinitely many balanced (0, -1, 1)-Steinhaus and Pascal triangles. Indeed, as illustrated in Figure9, the rotation of 120 degrees defined on the set of finite sequences of length m 1 in Z/nZ by rot 120 ((a j ) 0 j m-1 ) = induces an isomorphism between (0, 1, 1)-Steinhaus triangles (resp. (0, 1, 1)-Pascal triangles) and (0, -1, 1)-Steinhaus triangles (resp. (0, -1, 1)-Pascal triangles), which conserves multiplicity. Similarly, the rotation of 240 degrees, which assigns to a sequence (a j ) 0 j m-1 of length m in Z/nZ the sequence rot 240 ((a j ) 0 j m-1 ) = induces an isomorphism between (0, 1, 1)-Steinhaus triangles (resp. (0, 1, 1)-Pascal triangles) and (0, 1, -1)-Steinhaus triangles (resp. (0, 1, -1)-Pascal triangles), which conserves multiplicity. These sequences can be seen as the right side, for rot 120 (S), and the left side, for rot 240 (S), of the (0, 1, 1)-Steinhaus triangle ∇ (0,1,1) S associated with S.

  Molluzzo problem on each kind of Steinhaus figure defined above, not only on Steinhaus triangles. Problem 1.2. Let n be a positive integer. For each kind of Steinhaus figure, do there exist balanced Steinhaus figures in Z/nZ for all admissible sizes, i.e., for all Steinhaus figures whose cardinality is divisible by n? In other words,

	• for every m	1 such that m+1

2

is divisible by n, does there exist a balanced Steinhaus triangle of order m?

  For all positive integers n and m and for all elements a, d 1 and d 2 in Z/nZ, the doubly arithmetic triangle DAT(a, d 1 , d 2 , m) is the triangle of order m in Z/nZ, with first element a and where each diagonal and each row are arithmetic progressions with respective common differences d 1 and d 2 , that is the multiset in Z/nZ defined byDAT(a, d 1 , d 2 , m) = {a + id 1 + jd 2 | 0 i m -1 , 0 j m -1 -i} .Let n be a positive integer and let a, d 1 , d 2 ∈ Z/nZ. If the doubly arithmetic triangle DAT(a, d 1 , d 2 , m) of order m 1 is balanced, then its common differences d 1 , d 2 and d 1 -d 2 are invertible in Z/nZ. , -d 2 , d 1 -d 2 , m) of DAT(a, d 1 , d 2 , m). Let δ 1 and δ 2 be two integers whose respective residue classes modulo n are d 1 and d 2 .

	cellular automata of dimension 1 and in the cellular automaton of dimension 2 where the
	standard Pascal tetrahedron appears.
	2 DAT: a source of balanced multisets
	In this section, we show that doubly arithmetic triangles constitute a source of balanced
	multisets in Z/nZ, for n odd. Obviously, we can see that the anti-diagonals of a DAT
	are arithmetic progressions with common difference d 1 -d 2 . We begin by determining a
	necessary condition, on the common differences d 1 and d 2 , to obtain a balanced DAT in
	Z/nZ.
	Proposition 2.1. Proof. For n = 1 or m = 1, it is clear. Suppose now that n > 1 and m > 1. Let
	DAT(a, d 1 , d 2 , m) be a doubly arithmetic triangle in Z/nZ where at least one of the
	common differences d 1 , d 2 and d 1 -d 2 is not invertible. Without loss of generality, suppose
	that it is d 2 . If not, we can consider the rotations DAT(a, d 2 , d 1 , m) or DAT(a + (m -
	1)d 2
	3. Finally, in Section 7, we analyse
	the results on the generalized Molluzzo problem that we have obtained in this paper and
	we pose new open problems on the existence of balanced Steinhaus figures in additive

  table gives their common differences d 1 , d 2 , d 1 -d 2 . Thus, each subsequence S i 0 ,j 0 is doubly arithmetic, with invertible common differences d 1 , d 2 and d 1 -d 2 . Let λ 1 and let ∇ be a Steinhaus triangle of order m = 6λn or m = 6λn -1, that appears in O S . Since ∇ ∩ S i 0 ,j 0 , for i 0 and j 0 in {0, 1, 2, 3, 4, 5}, is a doubly arithmetic triangle of order λn or λn -1 and with invertible common differences dS i 0 ,j 0 d 1 d 2 d 1 -d 2 S 1,2, S 1,5 , S 3,1 , S 3,4 , S 5,0 , S 5,3 , S 0,4 , S 2,0 , S 2,3 , S 4,2 , S 4,5 , S 1,4 , S 3,0 , S 3,3 , S 5,2 , S 5,5 , S 0,3 , S 2,2 , S 2,5 , S 4,1 , S 4,4 -2(d Pascal trapezoid) of order m (resp. 2m -1) and of height h in O S can be seen as the multiset difference between a Steinhaus triangle of order m and a Steinhaus triangle of order m -h (resp. between a Pascal triangle of order 2m -1 and a Pascal triangle of order 2(m

	2d	2(2d + 3Σ)	-2(d + 3Σ)
	S 0,1 -2d	-2(2d + 3Σ)	2(d + 3Σ)
	S 1,1 2(d + 3Σ)	-2d	2(2d + 3Σ)
	S 0,0 + 3Σ)	2d	-2(2d + 3Σ)
	S 0,2 , S 0,5 , S 2,1 , S 2,4 , S 4,0 , S 4,3 2(2d + 3Σ)	2(d + 3Σ)	2d
	S 1,0 , S 1,3 , S 3,2 , S 3,5 , S 5,1 , S 5,4 -2(2d + 3Σ) -2(d + 3Σ)	-2d
	or -1 (mod 6n), since it can be decomposed into 36 subtriangles, which are balanced
	doubly arithmetic triangles by Theorem 2.2 again. For trapezoids, a Steinhaus trapezoid
	(resp.

1 , d 2 and d 1 -d 2 , it follows from Theorem 2.2 that the 36 subtriangles are balanced. Therefore their union, the Steinhaus triangle ∇, is also balanced in Z/nZ. Similarly, every Pascal triangle of order 2m -1 in O S is balanced, for all m ≡ 0

  The Steinhaus figures of this theorem are unions of the multisets ±∇ 2 , ±(∇ 1 ∇ 3 ), ±∆

[START_REF] Brunat | Symmetries in Steinhaus triangles and in Pascal generalized triangles[END_REF]

and ±(∆ 1 ∆ 2 ), which are balanced in Z/nZ by Proposition 6.2. More precisely, let λ be a positive integer. We know, from Theorem 5.6, that the Steinhaus triangles ∇S[3λn, 6λn -1], of order 3λn, and ∇∂S[0, 3λn -2], of order 3λn -1, are balanced. As depicted in Figure

7

, the Steinhaus triangle ∇S[(3λ+1)n, (6λ+2)n-1], of order (3λ+1)n, is the union of λ+1 triangles ∇ 2 , λ multisets ∇ 1 ∇ 3 , λ triangles ∆ 3 , λ multisets ∆ 1 ∆ 2 and the Steinhaus triangle ∇∂ n S[(3λ + 1)n, (6λ + 2)n -1] = -∇S[3λn, 6λn -1]. This leads to the equality

m ∇S[(3λ+1)n,(6λ+2)n-1] = (3λ + 1)m ∇ 2 + 3λm ∆ 3 + m ∇S[3λn,6λn-1] .

Similarly, the Steinhaus triangle ∇S[(3λ + 2)n, (6λ + 4)n -1], of order (3λ + 2)n, is the union of λ triangles ∇ 2 , λ + 1 multisets ∇ 1 ∇ 3 , λ + 1 triangles ∆ 3 , λ multisets ∆ 1 ∆ 2 and the Steinhaus triangle ∇∂ n S[(3λ+2)n, (6λ+4)n-1] = -∇S[(3λ+1)n, (6λ+2)n-1]. Therefore, we obtain

Acknowledgments

I would like to thank Shalom Eliahou for his unfailing support and his enthusiasm for this work. I also thank the anonymous referees for their helpful comments.

Steinhaus and Pascal tetrahedra

In this paper, we have studied balanced Steinhaus figures appearing in the cellular automaton of dimension 1 that generates the standard Pascal triangle. We may also consider similar figures in higher dimension, in the cellular automaton of dimension 2 generating the standard Pascal tetrahedron, for instance. Let n be a positive integer and let S = (a i,j ) i,j∈Z be a doubly infinite double sequence of terms in Z/nZ. The derived sequence ∂S of S is the sequence defined by ∂S = (a i,j + a i,j+1 + a i+1,j ) i,j∈Z and the orbit of S is the sequence of iterated derived sequences O S = ∂ k S k∈N . This orbit can also be seen as the (N × Z 2 )-indexed sequence of elements in Z/nZ, defined by