J Ben Rejeb

I.-C Morȃrescu

Synchronization in networks of linear singularly perturbed systems Jihene Ben Rejeb, Irinel-Constantin Morȃrescu and Jamal Daafouz

Abstract-This work is motivated by the fact that many real systems are characterized by two features. The first one is that they are obtained by interconnecting a bunch of simpler subsystems that have to synchronize in order to reach a global goal. The second one is that each subsystem presents dynamics that evolves on different time-scales. Taking into account the two features leads to the problem of synchronization in networks of singularly perturbed systems. In this work we are providing a preliminary study that considers the problem where each subsystem is linear and the network topology is represented by a connected undirected graph that is fixed in time. We show that we can proceed to a time-scale separation of the overall network dynamics and design the controls that synchronize the slow dynamics and the fast ones. Applying the joint control actions to the network of singularly perturbed systems we obtain an approximation of the synchronization behavior imposed for each scale. The methodology requires a variable transformation to overcome the fact that we are dealing with non-standard singularly perturbed systems. One example illustrates the synchronization behavior of linear singularly perturbed systems.

Index Terms-Multiagent systems; consensus; singularly perturbed systems.

I. INTRODUCTION

Physical systems are often characterized by several dynamical processes evolving on different time scales and influencing each other [START_REF] Naidu | Singular perturbations and time scales in control theory and applications: an overview[END_REF]. When several orders of magnitude differentiate the various time scale the analysis of the overall systems becomes more difficult. In this case, standard control techniques lead to ill-conditioned problems. To overcome this, singular perturbation theory [START_REF] Kokotović | Singular perturbation methods in control: analysis and design[END_REF], [START_REF] Khalil | Nonlinear Systems[END_REF] propose to approximate the dynamics by decoupling the slow dynamical process of the faster ones. Consequently, the control design is also decoupled with respect to each time scale and then is proven that the joint actions performs well when applied to the overall system.

The analysis and control design for multiple time-scales systems attracted a lot of interest due to their various applications going from biological systems such as gene expression systems [START_REF] Chen | A model of periodic oscillation for genetic regulatory systems[END_REF], neurons behavior [START_REF] Hodgkin | A quantitative description of membrane current and its application to conduction and excitation in nerve[END_REF] to engineering problems [START_REF] Malloci | Two time scale switched systems: Application to steering control in hot strip mills[END_REF]. General stability and stabilization of linear and nonlinear singularly perturbed systems can be found in [START_REF] Kokotović | Singular perturbation methods in control: analysis and design[END_REF], [START_REF] Khalil | Nonlinear Systems[END_REF]. For linear singularly perturbed systems a linear quadratic optimal control design is proposed in [START_REF] Garcia | The infinite time near optimal decentralized regulator problem for singularly perturbed systems: a convex optimization approach[END_REF]. Stabilization and exponential stability of singularly perturbed linear switched systems is considered in [START_REF] Alwan | Exponential stability of singularly perturbed switched systems with time delay[END_REF], [START_REF] Malloci | Stabilization of continuous-time singularly perturbed switched systems[END_REF]. Various biological singularly perturbed systems are analyzed from a geometric perspective in [START_REF] Hek | Geometric singular perturbation theory in biological practice[END_REF].

The particularity of existing studies presented above is that they consider singularly perturbed systems as being stand alone systems. Motivated by the fact that biological as technological systems are often composed of several coupled singularly perturbed systems, we are considering, in this work, the problem of synchronization of singularly perturbed systems. When only one time-scale characterizes the systems dynamics, the problem of synchronization has been extensively studied [START_REF] Kuramoto | Chemical Oscillations, Waves and Turbulence[END_REF], [START_REF] Pecora | Master stability functions for synchronized coupled systems[END_REF], [START_REF] Strogatz | Sync: The Emerging Science of Spontaneous Order[END_REF], [START_REF] Michiels | Consensus problems with distributed delays, with application to traffic flow models[END_REF], [START_REF] Morȃrescu | Synchronization of coupled nonlinearoscillators with shifted gamma-distributed delays[END_REF]. However, the synchronization of singularly perturbed systems has not been treated. We point out that time-scale separation has been observed and analyzed in power networks [START_REF] Chow | Time scale modeling of sparse dynamic networks[END_REF], [START_REF] Bıyık | Area aggregation and time-scale modeling for sparse nonlinear networks[END_REF], [START_REF] Romeres | Novel results on slow coherency in consensus and power networks[END_REF] but the systems composing the grid evolve on only one time scale.

In this work we consider a network of singularly perturbed linear systems and we provide the methodology allowing at extending the stabilization control design to the synchronization one. Precisely, we show that we can proceed to a timescale separation of the overall network dynamics and design the controls that synchronize the slow dynamics and the fast ones. Next, applying the joint control actions to the network of singularly perturbed systems we obtain an approximation of the synchronization behavior imposed for each scale. The main difficulty that we have to overcome is that the matrix defining the fast dynamics in closed loop is not invertible.

In this preliminary study we consider that the coupling topology, between the systems composing the network, is fixed and undirected. Therefore, the control feedback necessary for synchronization will use only local information provided by this fixed coupling topology. Extensions to directed and time-varying topologies as well as generalization to nonlinear dynamics will be considered in our future works.

The rest of the paper is organized as follows. In Section II we introduce the basic concepts that are used throughout the paper and we formulate the problem under consideration. The main results, concerning the design of the controllers that synchronize the subsystems using only local information, are presented in Section III. One numerical example illustrating the results is provided in Section IV. The paper ends with some concluding remarks and perspectives.

Notation

The following standard symbols are used throughout the paper. R is the set of real numbers, |A| is the cardinality of a given finite set A, x is the Euclidean norm of the vector x and ⊗ denotes the Kronecker product of two matrices. We also denote by I n ∈ R n×n the identity matrix of size n and by 1 n , 0 n ∈ R n the column vector whose components are all 1 and 0, respectively. We also denote by 0 n×m ∈ R n×m the matrix whose all components are 0. The transpose of a given matrix A is denoted by A . We denote diag(A 1 , . . . , A n ) the block diagonal matrix having the matrices A 1 to A n on the diagonal and 0 everywhere else.

II. PRELIMINARIES AND PROBLEM FORMULATION

We consider a network of n identical singularly perturbed linear systems. For any i = 1, . . . , n, the i th system at time t is characterized by the state (x i (t), z i (t)) ∈ R nx+nz and there exists a small > 0 such that its dynamics is given by:

ẋi (t) = A 11 x i (t) + A 12 z i (t) + B 1 u i (t) żi (t) = A 21 x i (t) + A 22 z i (t) + B 2 u i (t), i = 1, . . . , n (1)
where u i ∈ R m is the control input and

A 11 ∈ R nx×nx , A 12 ∈ R nx×nz B 1 ∈ R nx×m , A 21 ∈ R nz×nx A 22 ∈ R nz×nz , B 2 ∈ R nz×m such that rank(B 1 ) = rank(B 2 ) = m.
A standard assumption, in singular perturbation theory, which aims at ensuring the well posedness of ( 1) is the following.

Assumption 1:

The matrix A 22 is invertible.

With the network of n systems we associate a graph G which is a couple (V, E) where V = {1, . . . , n} represents the vertex set and E ⊂ V × V is the edge set. In the sequel we suppose that the graph is undirected meaning that (i, j) ∈ E ⇔ (j, i) ∈ E. We also assume that G has no self-loop (i.e.

∀ i = 1, . . . , n one has (i, i) / ∈ E). A weighted adjacency matrix associated with G is G = [g i,j ] ∈ R n×n such that g ij > 0 if (i, j) ∈ E g ij = 0 otherwise . The corresponding Laplacian matrix is L = [l ij ] ∈ R n×n defined by      l ii = n j=1 g i,j , ∀i = 1, . . . , n l ij = -g i,j if i = j .
By definition L is symmetric and all of its rows sum are zero.

Definition 1: A path of length p in the graph G = (V, E) is a union of edges p k=1 (i k , j k ) such that i k+1 = j k , ∀k ∈ {1, . . . , p -1}. The node j is connected with node i in G = (V, E) if there exists at least a path in G from i to j (i.e. i 1 = i and j p = j). A connected graph is such that any of its two distinct elements are connected.

Assumption 2:

The undirected graph G is connected.

Remark 1 (Basic properties of the Laplacian matrix [START_REF] Godsil | Algebraic Graph Theory[END_REF]): Let λ 1 ≤ λ 2 ≤ . . . ≤ λ n be the eigenvalues of L. Then

• λ 1 = 0 is a simple eigenvalue of L associated with the eigenvector 1 n . • λ 2 > 0 as far as G is connected. In other words, L is positive semi-definite. • λ 1 = 0 is an eigenvalue with multiplicity r of L⊗I r and it has r different eigenvectors defined by 1 n ⊗ e i , i = 1, . . . , r where e i ∈ R r is the column vector whose i th components equals 1 and all the others are 0. • there exists an orthonormal matrix T ∈ R n×n (i.e.

T T = T T = I n ) such that

T LT = D = diag(λ 1 , λ 2 , . . . , λ n ) Definition 2:
The n singularly perturbed systems defined by (1) achieve asymptotic synchronization using local information if there exists a state feedback controller of the form

u i (t) = K 1 n j=1 g i,j (x i (t) -x j (t))+ K 2 n j=1 g i,j (z i (t) -z j (t)) K 1 ∈ R m×nx , K 2 ∈ R m×nz (2) such that lim t→∞ x i (t) -x j (t) = 0 and lim t→∞ z i (t) -z j (t) = 0.
The main goal of this paper is the characterization of the feedback controllers that use local information and asymptotically synchronize the singularly perturbed systems defined by [START_REF] Naidu | Singular perturbations and time scales in control theory and applications: an overview[END_REF]. In order to do that we firstly define the collective dynamics describing the behavior of the overall network of n feedback coupled systems.

Let us denote by x(t) ∈ R n•nx and z(t) ∈ R n•nz the vectors collecting the states x i (t) and z i (t), i = 1, . . . , n, respectively (i.e. x(t) = (x 1 (t) , . . . , x n (t) ) and z(t) = (z 1 (t) , . . . , z n (t) ) ).

lim t→∞ D ⊗ I nz T ⊗ I nz z(t) = 0 (3)
Replacing ( 2) in (1) one obtains the following collective closed-loop dynamics:

ẋ(t) = Ā11 x(t) + Ā12 z(t) ż(t) = Ā21 x(t) + Ā22 z(t) (4)
where

Ā11 = I n ⊗ A 11 -(I n ⊗ B 1 K 1 )(L ⊗ I nx ), Ā12 = I n ⊗ A 12 -(I n ⊗ B 1 K 2 )(L ⊗ I nz ) Ā21 = I n ⊗ A 21 -(I n ⊗ B 2 K 1 )(L ⊗ I nx ), Ā22 = I n ⊗ A 22 -(I n ⊗ B 2 K 2 )(L ⊗ I nz )
We note that one has no guaranty that the matrix Ā22 is invertible. Therefore, the well posedness of the closedloop system(4) has also to be ensured by the choice of the controller gains. A final change of variable

x(t) = T ⊗ I nx x(t), z(t) = T ⊗ I nz z(t)
allows at rewriting the collective dynamics (4) as

ẋ(t) = Ã11 x(t) + Ã12 z(t) ż(t) = Ã21 x(t) + Ã22 z(t) (5)
where

Ã11 = I n ⊗ A 11 -(I n ⊗ B 1 K 1 )(D ⊗ I nx ), Ã12 = I n ⊗ A 12 -(I n ⊗ B 1 K 2 )(D ⊗ I nz ) Ã21 = I n ⊗ A 21 -(I n ⊗ B 2 K 1 )(D ⊗ I nx ), Ã22 = I n ⊗ A 22 -(I n ⊗ B 2 K 2 )(D ⊗ I nz ) Discussion 1)
Using the properties of Kronecker product, the closedloop system (5) can be decoupled in n independent singularly perturbed systems. Precisely, one uses that for any matrices M, N of appropriate dimension we have

I n ⊗ M -(I n ⊗ N )(D ⊗ I m ) = I n ⊗ M -D ⊗ N = diag M, . . . , M -diag λ 1 N, . . . , λ n N = diag M -λ 1 N, . . . , M -λ n N yielding Ã11 = diag A 11 -λ 1 B 1 K 1 , . . . , A 11 -λ n B 1 K 1 , Ã12 = diag A 12 -λ 1 B 1 K 2 , . . . , A 12 -λ n B 1 K 2 Ã21 = diag A 21 -λ 1 B 2 K 1 , . . . , A 21 -λ n B 2 K 1 , Ã22 = diag A 22 -λ 1 B 2 K 2 , . . . , A 22 -λ n B 2 K 2
Therefore, the closed-loop system (5) is equivalent with

     ẋi (t) = (A 11 -λ i B 1 K 1 )x i (t) + (A 12 -λ i B 1 K 2 )z i (t) żi (t) = (A 21 -λ i B 2 K 1 )x i (t) + (A 22 -λ i B 2 K 2 )z i (t) i = 1, . . . , n (6)
2) The asymptotic synchronization problem with local information becomes a problem of simultaneous stabilization of systems in (6) for i = 2, . . . , n. Indeed (3) can be seen as lim t→∞ D ⊗ I nx x(t) = 0 and lim t→∞ D ⊗ I nz z(t) = 0 but since D = diag(λ 1 , . . . , λ n ) with λ 1 = 0 the condition is transformed as lim t→∞ xi (t) = 0 and lim t→∞ zi (t) = 0, i = 2, . . . n 3) We emphasize that from the definition of T , the following also hold x(t) = T ⊗I nx x(t) and z(t) = T ⊗ I nz z(t). Thus, the synchronization manifold depends on the dynamics of (x(t), z(t)). Precisely, if the system

     ẋ1 (t) = A 11 x1 (t) + A 12 z1 (t) ż1 (t) = A 21 x1 (t) + A 22 z1 (t) i = 1, . . . , n (7)
has a stable equilibrium point (x * , z * ), then systems (1) will asymptotically reach a finite consensus. If [START_REF] Garcia | The infinite time near optimal decentralized regulator problem for singularly perturbed systems: a convex optimization approach[END_REF] is unstable then all the systems in (1) will synchronize on divergent trajectories. 4) The well posedness of system ( 4) is equivalent with the one of system (5) which in turn is ensured if all systems in (6) are well posed. Let us notice that for i = 1 the system is well posed due to Assumption 1. The rest of the systems in (5) are well posed if K 2 is chosen such that A 22 -λ i B 2 K 2 is invertible for i = 2, . . . , n.

III. CONTROL DESIGN

Before giving our main result let us introduce some notation that allows at completely decouple the slow and fast dynamics that occur in the overall system. This is done by following the classical singular perturbation design (see [START_REF] Kokotović | Singular perturbation methods in control: analysis and design[END_REF] for instance). Let us consider the slow systems

     ẋi,s (t) = A 0 -λ i B 0 K 0 xi,s (t), xi,s (0) = xi (0) zi,s (t) = -A -1 22 A 21 -λ i B 2 K 0 xi,s (t) i = 1, . .

. , n

where

A 0 = A 11 -A 12 A -1 22 A 21 , B 0 = B 1 -A 12 A -1 22 B 2 .
Consequently, the corresponding fast systems are

żi,f (t) = A 22 -λ i B 2 K 2 zi,f (t), zi,f (0) = zi (0)-z i,s (0)
Using the notation above the following result holds.

Theorem 3: Let K 2 and K 0 be designed such that for i = 2, . . . , n the matrices A 22 -λ i B 2 K 2 and A 0 -λ i B 0 K 0 are all Hurwitz. Then, there exists * > 0 such that the controllers (2) with

K 1 = (I m -K 2 A -1 22 B 2 )K 0 + K 2 A -1 22 A 21 .
asymptotically synchronize with local information the systems [START_REF] Naidu | Singular perturbations and time scales in control theory and applications: an overview[END_REF].

Proof: Following [START_REF] Kokotović | Singular perturbation methods in control: analysis and design[END_REF], the choice of K 1 and K 2 as in the statement above ensures that for i = 2, . . . , n the systems in ( 6) are asymptotically stable. Moreover, for all ∈ (0, * ] and all t ≥ 0 one has

xi (t) = xi,s (t) + O( ), zi (t) = -A -1 22 A 21 -λ i B 2 K 0 xi,s (t) + zi,f (t) + O( ).
We recall here that the asymptotic synchronization is equivalent with

lim t→∞ L ⊗ I nx x(t) = 0 and lim t→∞ L ⊗ I nz z(t) = 0 which hold true since L ⊗ I nx x(t) = D ⊗ I nx x(t) =      0 λ 2 x2
. . .

λ n xn      and L ⊗ I nz z(t) = D ⊗ I nz z(t) =      0 λ 2 z2
. . .

λ n zn     
Remark 3: Theorem 3 basically says that in order to asymptotically synchronize systems in [START_REF] Naidu | Singular perturbations and time scales in control theory and applications: an overview[END_REF] we have to separately synchronize the fast and slow dynamics by stabilizing the dynamics of the error between the different systems.

Corollary 1: Let K 0 be designed such that for i = 2, . . . , n the matrices A 0 -λ i B 0 K 0 are Hurwitz. If the matrix A 22 is Hurwitz the controllers u i in (2) with K 1 = K 0 and K 2 = 0 m×nz , asymptotically synchronize the systems (1).

Remark 4: We note that A 22 is Hurwitz corresponds to the case in which the fast dynamics is stable. In this case, the control design can be directly realized by approximating the dynamics (1) with the corresponding decoupled slow and fast dynamics. Thus, we have to synchronize only the slow linear dynamics representing the reduced systems in [START_REF] Naidu | Singular perturbations and time scales in control theory and applications: an overview[END_REF].

We also note that, when A 22 is Hurwitz the dynamics (7) can be approximated by its decoupled version in fast and slow dynamics.

Using Theorem 3 we reduce the synchronization problem to the one of state feedback simultaneous stabilization (SFSS) of linear systems [START_REF] Luke | A survey of state feedback simultaneous stabilization techniques[END_REF], [START_REF] Saadatjoo | Simultaneous control of linear systems by state feedback[END_REF]. Simultaneous stabilization is in general a difficult undecidable problem that received a lot of attention [START_REF] Blondel | Simultaneous stabilization of linear systems[END_REF], [START_REF] Henrion | Rank-one lmi approach to simultaneous stabilization of linear systems[END_REF]. Nevertheless, we are facing a very particular SFSS problem that can be formulated as follows. Problem 1: For A ∈ R p×p , B ∈ R p×m and 0 < λ 2 ≤ λ 3 ≤ . . . ≤ λ n find K ∈ R m×p such that for i = 2, . . . , n the matrices A -λ i BK are Hurwitz.

It is obvious that the problem is feasible as far as the states x i (t) and z i (t) are scalar since depending on the sign of B we have to render negative only the scalar A -λ 2 BK or A -λ n BK. When x i (t) and z i (t) are not scalars we have to simultaneously render the n -1 matrices A -λ i BK Hurwitz.

Proposition 4: If the pair (A, B) is controllable then there exists K solving Problem 1. Before giving the proof of this result let us state the following.

Lemma 5:

The matrix M ∈ R n×n is Hurwitz if ∀x ∈ R n \ {0 n } one has x M x < 0.
Proof: Let ν be an eigenvalue of M . It means (see [START_REF] Wielandt | On the eigenvalues of a+b and ab[END_REF]) that there exists x ∈ C n \ {0 n } such that ν = x M x where x stands for the complex conjugate of x. Let us consider r, q ∈ R n the real and imaginary part of x ∈ C n . Since M is a matrix with real components, the following computation is straightforward

2 (ν) = ν + ν = x M x + x M x = 2(r M r + q M q)
which leads to (ν) < 0 since r, q ∈ R n and at least one of them is not 0 n .

Proof of Proposition 4: In order to prove the existence of K solving Problem 1 we show that there exists K such that ∀x ∈ R p \ {0 p }, ∀i = 2, . . . , n one has

x (A + λ i BK)x < 0. (8)
If (A, B) is controllable then (A, λ 2 B) is controllable too. Let us notice that 0 < λ 2 ≤ λ 3 ≤ . . . ≤ λ n . Therefore, the following makes sense for i = 2, . . . , n

A + λ i BK = λ i λ 2 A + λ 2 BK + λ 2 λ i -1 A . (9)
Considering

µ = max i=2,...,n λ 2 λ i -1 A one has x λ 2 λ i -1 Ax ≤ µ x = x µI p x
Therefore,

x (A + λ i BK)x ≤ λ i λ 2 x (A + λ 2 BK + µI p ) x (10)
Since (A, λ 2 B) is controllable we can choose K such that all the eigenvalues η j , j = 1, . . . , p of A + λ 2 BK are real, different one from another and smaller than -µ. Doing so, there exists a nonsingular matrix T ∈ R p such that

T -1 (A + λ 2 BK)T = diag(η 1 , . . . , η p ) meaning that T -1 (A + λ 2 BK + µI p )T = diag(η 1 + µ, . . . η p + µ) < 0.
Using [START_REF] Hek | Geometric singular perturbation theory in biological practice[END_REF] and the previous inequality we conclude that (8) holds.

Remark 5: It is noteworthy that the controller design can be done in a decentralized manner since each agent needs to compute only norm of A 22 and A 0 in order to get K 2 and K 0 respectively.

Another practical way of finding the gain K is by solving the following n -1 linear matrix inequalities (LMIs):

(A -λ i BK) P + P (A -λ i BK) < 0, i = 2, . . . , n where P = P > 0 is a matrix to be found if it exists. More exactly, one has P = S -1 and K = RS -1 if S = S > 0, R ∈ R m×p solve the following standard LMIs [START_REF] Boyd | Linear Matrix Inequalities in system and control theory[END_REF]:

SA + AS -λ i (R B + BR) < 0, i = 2, . . . , n
Note that the previous LMIs are used to numerically find the value of K that simultaneously renders A -λ i BK Hurwitz for i = 2, . . . , n.

IV. ILLUSTRATIVE EXAMPLES

In this section, we consider the synchronisation of three agents described by an undirected graph G. One representative example is given for illustration.

The system is given by (1) where :

A 11 = 2, 5 -6 -2 2 , A 12 = 2 3 0 -2 A 21 = 0, 5 2 -1 1 , A 22 = -2 1 0 -1 B 1 = 2 1 , B 2 = 1 1
To each agent we assign a vector state having 4 components characterized by slow and fast dynamics. For any agent i ∈ {1, . . . , n}, let us denote by [x i,1 , x i,2 ] and [z i,1 , z i,2 ] its slow and fast state' components, respectively. The Laplacian matrix describing the undirected topology of the graph G is defined by:

L =   2 -1 -1 -1 2 -1 -1 -1 2   (11)
In simulation we fix = 0.001 and all the components of the initial condition are chosen within [-4, 5]. Since A 22 is Hurwitz we have to solve numerically 2 LMIs to stabilize the dynamics (6) such that K 1 = K 0 . Figure 1 highlights the synchronization of the slow dynamics for an sufficiently small. Fig. 1. Trajectories of the x components of system (4). The red bullet is the stable equilibrium x * of (7).

To highlight the fast transient dynamics, we represent the evolution of the fast states function of the slow ones. To emphasize the fast dynamics we also plot in Figure 7 the fast part of z variables. The synchronization of the two-time scale model (1) ensures the stabilization of the errors between the slow states as shown in figure 6. The standard singular perturbation analysis and design are adapted to synchronization purposes. The controller design is computationally oriented since it is obtained by solving some LMIs. We also show that under mild assumptions the LMIs are always feasible. One numerical example illustrates the method implementation. Stabilization of linear and nonlinear singularly perturbed systems for directed graphs and timevarying topologies are is our future focus.

Remark 2 :

 2 Let us observe that the asymptotic synchronization is equivalent with lim t→∞ L ⊗ I nx x(t) = 0, and lim t→∞ L ⊗ I nz z(t) = 0 and since T L = DT , the synchronization is also characterized by lim t→∞ D ⊗ I nx T ⊗ I nx x(t) = 0, and

Fig. 2 .

 2 Fig. 2. Slow and fast manifolds

Fig. 3 .Fig. 4 .

 34 Fig. 3. The trajectories of x (solid) and xs (dotted)

Fig. 5 .

 5 Fig. 5. The fast part of z components zf i ∀i ∈ {1, . . . , n}

2 Fig. 6 .

 26 Fig.6. The differences x i -x j , ∀i = j ∈ {1, . . . , n}

Fig. 7 .

 7 Fig. 7. The trajectories of system

This work was funded by the ANR project COMPACS -"Computation Aware Control Systems", ANR-13-BS03-004.


Jonathan Chappelon
email: jonathan.chappelon@math.univ-montp2.fr

Shalom Eliahou
email: shalom.eliahou@lmpa.univ-littoral.fr

ON THE PROBLEM OF MOLLUZZO FOR THE MODULUS 4

Keywords: Molluzzo's problem, Steinhaus triangles, balanced triangles, multisets, Pascal's rule. MSC2010: 05A05, 05A15, 05B30, 05E15, 11B50, 11B75

We solve the currently smallest open case in the 1976 problem of Molluzzo on Z/mZ, namely the case m = 4. This amounts to constructing, for all positive integer n congruent to 0 or 7 mod 8, a sequence of integers modulo 4 of length n generating, by Pascal's rule, a Steinhaus triangle containing 0,1,2,3 with equal multiplicities.

Introduction

The problem of Molluzzo in combinatorial number theory is about the existence of certain triangular arrays in Z/mZ. It was first formulated by Steinhaus in 1958 for m = 2 [START_REF] Steinhaus | One Hundred Problems in Elementary Mathematics[END_REF], and then generalized by Molluzzo in 1976 for m ≥ 3 [START_REF] Molluzzo | Theory and applications of graphs[END_REF]. It is still widely open for most moduli m. The problem reads as follows. Given m ≥ 2, for which n ≥ 1 does there exist a triangle

x 1,1 x 1,2
x 2,1

x 1,n x 1,n-1

x 2,n-1

x n,1 ∇ = with entries x i,j in Z/mZ, of side length n, satisfying the following two conditions:

(C1) Pascal's rule: every element of ∇ outside the first row is the sum of the two elements above it. That is, x i,j = x i-1,j + x i-1,j-1 for all 2 ≤ i ≤ n and 1 ≤ j ≤ n -i.

(C2) The elements of Z/mZ all occur with the same multiplicity in ∇.

Definition 1. A triangle ∇ in Z/mZ satisfying condition (C1) is called a Steinhaus triangle. It is said to be balanced if it satisfies condition (C2).

By (C1), a Steinhaus triangle is completely determined by its first row S, and may thus be denoted by ∇S. For instance, the sequence S = 0100203 in Z/4Z generates the following Steinhaus triangle ∇S: 0 1 0 0 2 0 3 1 1 0 2 2 3 2 1 2 0 1 3 3 2 1 2 1 3 3 0 3

Observe that ∇S is balanced, since each element of Z/4Z appears with the same multiplicity, namely 7.

An obvious necessary condition for the existence of a balanced Steinhaus triangle ∇ in Z/mZ of side length n is given by

n + 1 2 ≡ 0 mod m. (1)
Indeed, it follows from (C2) that m divides the multiset cardinality of ∇, which is n+1 2 . Is this necessary condition also sufficient? This is the more detailed content of Molluzzo's problem. While it seems reasonable to conjecture a positive answer in most cases, two counterexamples are known: in Z/15Z and in Z/21Z, there is no balanced Steinhaus triangle of side length 5 and 6, respectively, even though the pairs (m, n) = (15, 5) and (21, 6) both satisfy condition [START_REF] Chappelon | Regular Steinhaus graphs and Steinhaus triangles in finite cyclic groups[END_REF]. (See [1, p. 75] and [3, p. 293].)

Note that, given m ≥ 2, the condition for n ∈ N to satisfy (1) only depends on the class of n mod m if m is odd, or mod 2m if m is even.

Known results

Despite its apparent simplicity, the problem of Molluzzo is very challenging, as testified by the scarcity of available results. The only moduli m for which it has been completely solved so far are [START_REF] Harborth | Solution of Steinhaus's problem with plus and minus signs[END_REF][START_REF] Eliahou | On a problem of Steinhaus concerning binary sequences[END_REF][START_REF] Eliahou | Zero-sum balanced binary sequences[END_REF],

• m = 2 in
• m = 3 i for all i ≥ 1 in [1, 2],
• m = 5, 7 in [START_REF] Chappelon | Regular Steinhaus graphs and Steinhaus triangles in finite cyclic groups[END_REF][START_REF] Chappelon | Balanced Steinhaus triangles in Z/5Z and Z/7Z[END_REF].

In each case, the necessary existence condition (1) turns out to be sufficient.

Contents

In this paper, we solve the currently smallest open case of the problem, namely the case m = 4. Our solution is presented in Section 2 and proved valid in Section 3. Here again, the necessary existence condition (1) is found to be sufficient. The construction method, which consists in attempting to lift to Z/4Z specific known solutions in Z/2Z, is explained in Section 4. It will probably take some time before complete solutions emerge for more moduli. For this reason we propose, in a short concluding section, a hopefully more tractable version of the problem.

A solution for m = 4

Here we solve Molluzzo's problem in the group Z/4Z. For m = 4, it is easy to see that the necessary condition (1) amounts to the following: for all n ∈ N, we have n + 1 2 ≡ 0 mod 4 ⇐⇒ n ≡ 0 or 7 mod 8.

As in [START_REF] Eliahou | On a problem of Steinhaus concerning binary sequences[END_REF] for the case m = 2, our solution involves the concept of strongly balanced triangles. We first introduce a notation for initial segments of sequences. Notation 1. Let S = (x i ) i≥1 be a finite or infinite sequence, and let l ≥ 0 be an integer not exceeding the length of S. We denote by S[l] = (x 1 , . . . , x l ) the initial segment of length l of S. Definition 2. Let S be a finite sequence of length n ≥ 0 in Z/4Z. The Steinhaus triangle ∇S is said to be strongly balanced if, for every 0 ≤ t ≤ n/8, the Steinhaus triangle ∇S[n -8t] is balanced.

Here is our main result in this paper.

Theorem 1. There exists a balanced Steinhaus triangle of length n in Z/4Z if and only if n+1 2 ≡ 0 mod 4. More precisely, consider the following infinite, eventually periodic sequences in Z/4Z:

S 1 = 01220232(212113220030232311200232) ∞ , S 2 = 21210130(200132022112002110220130) ∞ , T 1 = 0120021(212202102023032200322021) ∞ , T 2 = 1000212(312223301210312003103232) ∞ , T 3 = 1200210(220101222032222103000210) ∞ , T 4 = 2102203(232002102021230022302203) ∞ .
Then, for all integers i, j, k such that 1 ≤ i ≤ 2, 1 ≤ j ≤ 4 and k ≥ 0, the Steinhaus triangles of the initial segments S i [8k] and T j [8k + 7] are strongly balanced.

Proof of Theorem 1

We now prove the above theorem. Actually, only the statements concerning S 1 are treated in detail. The proof method for the other sequences S 2 , T 1 , T 2 , T 3 , T 4 is similar and only briefly commented. Notation 2. Let A, B be two blocks, either triangles or lozenges. We denote by A * B the unique parallelogram they would determine by Pascal's rule (C1) if they were adjacent in a large Steinhaus triangle (as may be freely assumed to be the case). See Figure 1. Note that A * B only depends on the right lower side of A and the left lower side of B, and is a lozenge if A, B have the same side length. For example:

• if A = 0 1 1 and B = 2 3 1 , then A * B = 3 0 0 0 since 0 1 2 3 1 3 1 0 0 0 ; • if A = 2 2 3 1 and B = 3 0 2 2 , then A * B = 3 0 1 1 since 2 2 3 1 3 0 2 2 3 0 1 1 .
Consider now the four triangular blocks A 0 , A 1 , A 2 , A 3 depicted in Figure 3. Taking the * product of selected pairs, we define

B i = A i * A i+1 for i = 0, 1, 2 and B 3 = A 3 * A 1 . (2)
Similarly, we set

C i = B i * B i+1 for i = 0, 1, 2 and C 3 = B 3 * B 1 . (3)
Finally, we also need to set

D 0 = C 0 * C 1 and E 0 = D 0 * C 3 . (4)
The blocks A i , B i , C i , D 0 , E 0 (i = 1, 2, 3) are displayed in Figure 3. In view of the following lemma, we shall refer to them as the building blocks of ∇S 1 [8k].

Lemma 1. For every integer k ≥ 0, the Steinhaus triangle ∇S 1 [8k] has the structure depicted in Figure 2, where A i , B i , C i and D 0 , E 0 are the blocks defined above.

Proof. Recall that S 1 = 01220232(212113220030232311200232) ∞ . Thus, S 1 is made of an initial block I = 01220232 of length 8, and a period P 1 P 2 P 3 of length 24 = 3 × 8, where

P 1 = 21211322, P 2 = 00302323, P 3 = 11200232. A 0 A 1 A 2 A 3 A 1 A 2 A 3 A 1 B 0 B 1 B 2 B 3 B 1 B 2 B 3 C 0 C 1 C 2 C 3 C 1 C 2 D 0 C 3 C 1 C 2 C 3 E 0 C 2 C 3 C 1 C 0 C 1 C 2 D 0 C 3 E 0 Figure 2: Structure of ∇S 1 [8k]
Observe that A 0 = ∇I and A i = ∇P i for i = 1, 2, 3. This accounts for the top structure of ∇S 1 [8k]. Now, by definition we have

B 0 = A 0 * A 1 , B 1 = A 1 * A 2 , B 2 = A 2 * A 3 , B 3 = A 3 * A 1 , C 0 = B 0 * B 1 , C 1 = B 1 * B 2 , C 2 = B 2 * B 3 , C 3 = B 3 * B 1 , D 0 = C 0 * C 1 , E 0 = D 0 * C 3 .

It remains to show that

C 1 * C 2 = C 3 , C 2 * C 3 = C 1 , C 3 * C 1 = C 2 and E 0 * C 2 = C 0 .
To do this, recall that the * product of two blocks only depends on their lower sides, and observe on Figure 3 that -the lower sides of C 1 coincide with those of B 3 ;

-the lower sides of C 2 coincide with those of B 1 ;

-the lower sides of C 3 coincide with those of B 2 ;

-the lower sides of E 0 coincide with those of B 0 .

It follows that

C 1 * C 2 = B 3 * B 1 = C 3 , C 2 * C 3 = B 1 * B 2 = C 1 , C 3 * C 1 = B 2 * B 3 = C 2 , E 0 * C 2 = B 0 * B 1 = C 0 , (5)
as desired. This completes the proof of the lemma.

We are now in a position to prove our main result.

Proof of Theorem 1 for S 1 . We shall prove, by induction on k, that the Steinhaus triangle ∇S 1 [8k] is strongly balanced. This is true for k = 0. For k ≥ 1, it suffices to show that 0 1 2 2 0 2 3 2 1 3 0 2 2 1 1 0 3 2 0 3 2

3 1 2 3 1 0 3 1 0 3 0 1 3 1 0 2 1 2 1 1 3 2 2 3 3 3 2 0 1 0 2 2 1 2 1 1 0 3 3 3 2 3 2 2 1 1 0 3 1 3 0 0 0 3 0 2 3 2 3 0 3 3 2 1 1 1 3 2 1 3 2 2 1 3 0 1 0 0 3 1 1 3 0 2 3 2 1 1 1 2 0 0 2 3 2 2 3 2 0 2 1 1 1 1 2 2 3 2 2 3 0 1 1 1 3 1 2 0 0 3 0 3 3 A 0 A 1 A 2 A 3 0 1 3 3 0 1 0 3 1 1 0 3 0 2 0 1 3 3 2 2 1 2 0 2 1 0 3 2 2 2 2 3 1 3 1 2 0 0 1 0 0 0 3 0 1 1 0 0 3 1 2 1 0 3 3 3 1 3 2 0 0 2 0 2 2 2 2 3 0 1 1 3 1 2 2 0 0 3 2 1 2 0 3 1 1 0 3 2 3 0 2 0 0 3 1 1 3 2 2 1 3 0 2 0 1 0 3 3 2 2 1 1 3 1 0 3 2 0 1 3 1 2 0 0 3 0 3 3 0 1 2 3 3 3 3 2 2 1 0 1 0 3 2 2 1 1 3 1 2 0 3 2 0 0 3 2 1 3 1 2 0 3 1 1 0 0 3 2 3 0 2 0 3 1 1 3 2 3 0 2 0 1 3 2 2 1 1 0 3 1 3 0 0 1 3 3 0 1 0 3 1 1 2 3 0 2 0 1 1 3 2 2 1 0 2 0 1 0 3 2 3 2 2 1 1 3 1 2 1 0 3 2 0 0 3 1 3 1 2 0 3 0 0 3 2 3 0 3 1 1 3 0 2 3 2 1 B 0 B 1 B 2 B 3 2 1 1 0 2 0 3 2 2 1 2 1 0 3 2 2 3 1 3 1 2 2 1 0 0 0 3 2 0 3 1 0 0 3 1 1 3 0 1 0 3 0 2 3 1 1 3 3 2 0 2 0 2 1 2 2 2 3 0 0 1 0 1 1 2 1 2 0 3 2 0 3 1 1 2 3 0 2 0 1 1 3 2 2 1 0 2 0 1 0 3 2 3 2 2 1 1 3 1 2 1 0 3 2 0 0 3 1 3 1 2 0 3 0 0 3 2 3 0 3 1 1 3 0 2 3 2 1 0 2 1 0 3 2 1 3 1 2 2 0 0 3 2 1 2 0 3 1 1 0 3 2 3 0 2 0 0 3 1 1 3 2 2 1 3 0 2 0 1 0 3 3 2 2 1 1 3 1 0 3 2 0 1 3 1 2 0 0 3 0 3 3 2 1 1 0 2 0 3 2 2 1 0 1 0 3 2 2 1 1 3 1 2 0 3 2 0 0 3 2 1 3 1 2 0 3 1 1 0 0 3 2 3 0 2 0 3 1 1 3 2 3 0 2 0 1 3 2 2 1 1 0 3 1 3 0 C 0 C 1 C 2 C 3 Figure 3: The building blocks of ∇S 1 [8k] 0 2 1 0 3 2 1 3 1 2 0 0 0 3 2 1 0 0 3 1 1 2 1 0 3 0 2 0 3 3 1 3 3 2 2 1 2 0 0 2 1 0 3 2 0 2 3 1 3 2 2 1 0 0 0 3 1 0 3 0 1 3 1 0 2 1 2 0 3 2 0 3 1 1 0 3 0 2 0 1 3 3 2 2 1 2 0 2 1 0 3 2 2 2 2 3 1 3 1 2 0 0 1 0 0 0 3 0 1 1 0 0 3 1 2 1 0 3 3 3 1 3 2 0 0 2 0 2 D 0 E 0 Figure 3: The building blocks of ∇S 1 [8k] (continued)
∇S 1 [8k] is balanced. It will then automatically be strongly balanced since ∇S 1 [8k -8] is, by the induction hypothesis. Thus, we are assuming that 0, 1, 2, 3 occur with the same multiplicity in ∇S 1 [8k -8], and we must show that this remains true in

∇S 1 [8k].
Consider the multiset difference

T = ∇S 1 [8k] \ ∇S 1 [8k -8],
a band of width 8 bordering the eastern side of ∇S 1 [8k]. To conclude the proof, we need only show that 0, 1, 2, 3 occur with the same multiplicity in T . For any finite multiset X on Z/4Z, and for all j ∈ Z/4Z, let us denote by m X (j) the occurrence multiplicity of j in X.

In order to determine the function m T on Z/4Z, we need to determine m X for the building blocks X = A i , B i , C i , D 0 , E 0 . This is done in Table 1. Let now C denote the

A 0 A 1 A 2 A 3 B 0 B 1 B 2 B 3 C 0 C 1 C 2 C 3 D 0 E 0 0 9 5 8
m C (j) = m C 1 (j) + m C 2 (j) + m C 3 (j)
for all j ∈ Z/4Z. Looking at the columns below C 1 , C 2 , C 3 in Table 1, we see that m C (j) = 15 + 16 + 17 = 48 [START_REF] Eliahou | Zero-sum balanced binary sequences[END_REF] for all j ∈ Z/4Z. We are now ready to show that m T is constant on Z/4Z. For this, we need to distinguish 3 cases, according to the class of k mod 3.

• Case 1: k = 3q. Figure 2 shows that the building blocks making up T are A 2 , B 1 and C 0 occurring once each, and C 1 , C 2 , C 3 occurring q -1 times each. Therefore, using Table 1 and ( 6), we get

m T (j) = m A 2 (j) + m B 1 (j) + m C 0 (j) + (q -1)m C (j)
= 41 + 48(q -1), for all j ∈ Z/4Z.

• Case 2: k = 3q + 1. In this case, the building blocks making up T are A 3 , B 2 , C 1 and D 0 occurring once each, and C 1 , C 2 , C 3 occurring q -1 times each. Thus

m T (j) = m A 3 (j) + m B 2 (j) + m C 1 (j) + m D 0 (j) + (q -1)m C (j)
= 57 + 48(q -1), for all j ∈ Z/4Z.

• Case 3: k = 3q + 2. Now, the building blocks making up T are A 1 , B 3 , C 2 , C 3 and E 0 occurring once each, and C 1 , C 2 , C 3 occurring q -1 times each. Thus

m T (j) = m A 1 (j) + m B 3 (j) + m C 2 (j) + m C 3 (j) + m E 0 (j) + (q -1)m C (j)
= 73 + 48(q -1), for all j ∈ Z/4Z.

Hence m T is constant on Z/4Z in each case, as desired. This completes the proof of Theorem 1 for the sequence S 1 .

The proof for the sequences S 2 , T 1 , T 2 , T 3 , T 4 follows similar lines. To start with, the structure of each derived triangle is the same as in Figure 2. Indeed, let A 0 , A 1 , A 2 , A 3 be the triangles constructed from the finite subsequences given in Table 2 for each sequence

S 2 , T 1 , T 2 , T 3 , T 4 . Let now B 0 , B 1 , B 2 , B 3 , C 0 , C 1 , C 2 , C 3 ,
D 0 , E 0 be the blocks defined by the same formulae (2), ( 3) and ( 4) as in the proof for S 1 . Then, as easily verified, the equalities (5) still hold. Finally, as for S 1 , the conclusion of the proof follows from the knowledge of the multiplicities of 0, 1, 2, 3 ∈ Z/4Z for each block. For convenience, these multiplicities are made explicit in Table 3.

A 0 A 1 A 2 A 3 S 2 ∇(21210130) ∇(20013202) ∇(21120021) ∇(10220130) T 1 ∇(0120021) ∇(21220210) ∇(20230322) ∇(00322021) T 2 ∇(1000212) ∇(31222330) ∇(12103120) ∇(03103232) T 3 ∇(1200210) ∇(22010122) ∇(20322221) ∇(03000210) T 4 ∇(2102203) ∇(23200210) ∇(20212300) ∇(22302203) Table 2: Definition of blocks A 0 , A 1 , A 2 , A 3 for the sequences S 2 , T 1 , T 2 , T 3 , T 4 . S 2 : A 0 A 1 A 2 A 3 B 0 B 1 B 2 B 3 C 0 C 1 C 2 C 3 D 0 E 0 0 9
A 0 A 1 A 2 A 3 B 0 B 1 B 2 B 3 C 0 C 1 C 2 C 3 D 0 E 0 0 7
T 2 : A 0 A 1 A 2 A 3 B 0 B 1 B 2 B 3 C 0 C 1 C 2 C 3 D 0 E 0 0 7
T 3 : A 0 A 1 A 2 A 3 B 0 B 1 B 2 B 3 C 0 C 1 C 2 C 3 D 0 E 0 0 7
A 0 A 1 A 2 A 3 B 0 B 1 B 2 B 3 C 0 C 1 C 2 C 3 D 0 E 0 0 7 8

The construction method

We now explain how our solution was constructed. Let m 1 , m 2 ≥ 2 be integers, with m 2 a multiple of m 1 . Consider the canonical quotient map

π : Z/m 2 Z -→ Z/m 1 Z. If ∇ is a Steinhaus triangle in Z/m 2 Z, then π(∇) is a Steinhaus triangle in Z/m 1 Z.
Moreover, if ∇ is balanced, then so is π(∇), as all fibers of π have the same cardinality. Thus, an obvious strategy for constructing balanced Steinhaus triangles in Z/m 2 Z consists in trying to lift to Z/m 2 Z known balanced Steinhaus triangles in Z/m 1 Z. This route is tricky, as illustrated by Theorems 3 and 4 below. It allowed us to solve the case m = 4 of Molluzzo's problem, but neither the case m = 6 nor the case m = 8 so far.

We shall restrict our attention to strongly balanced Steinhaus triangles. These were defined earlier in Z/4Z only. We now generalize them to Z/mZ for all even moduli. Definition 3. Let m ≥ 2 be an even modulus. Let S be a finite sequence of length n ≥ 0 in Z/mZ. The Steinhaus triangle ∇S is said to be strongly balanced if, for every 0 ≤ t ≤ n/(2m), the Steinhaus triangle ∇S[n -2mt] is balanced.

Note that this definition coincides with Definition 2 for m = 4. From now on, we assume that m 1 = m is an even number, and that m 2 = 2m 1 . The following notation helps to measure, roughly speaking, to what extent strong solutions in Z/mZ can be lifted to strong solutions in Z/2mZ. Notation 3. Let S be an infinite sequence in Z/mZ. For n ≥ 0, let a n (S) denote the number of sequences T in Z/2mZ, of length n, such that • ∇T is a strongly balanced Steinhaus triangle in Z/2mZ;

• π(T ) = S[n], the initial segment of length n in S.

We denote by G S (t) = ∞ n=0 a n (S)t n the generating function of the numbers a n (S).

We shall use this notation as a convenient device for exhibiting the value of the a n (S) for all n at once. For our present purposes, the favorable case occurs when G S (t) is an infinite series, not just a polynomial. Indeed, G S (t) is an infinite series if and only if there exists infinitely many strongly balanced Steinhaus triangles in Z/2mZ, which lift those in Z/mZ generated by initial segments of S.

From Z/2Z to Z/4Z

Here we set m = 2. Several types of balanced Steinhaus triangles of length 4k or 4k + 3 in Z/2Z are known. See [START_REF] Harborth | Solution of Steinhaus's problem with plus and minus signs[END_REF][START_REF] Eliahou | On a problem of Steinhaus concerning binary sequences[END_REF][START_REF] Eliahou | Zero-sum balanced binary sequences[END_REF]. We focus here on the ones given in [START_REF] Eliahou | On a problem of Steinhaus concerning binary sequences[END_REF], which have the added property of being strongly balanced.

Theorem 2 ([5]

). Let Q 1 , . . . , Q 4 and R 1 , . . . , R 12 be the following eventually periodic sequences of Z/2Z:

Q 1 = 0100(001001011100) ∞ , Q 2 = (010010000111) ∞ , Q 3 = 0101(011000011000) ∞ , Q 4 = 0101(101000101000) ∞ , R 1 = 001(010000100001) ∞ , R 2 = 0011110(001101010110) ∞ , R 3 = 010(000101000010) ∞ , R 4 = 0100001(010010111100001010111111) ∞ , R 5 = 0100001(100100001001) ∞ , R 6 = 0101011(010101100011) ∞ , R 7 = 0101011(010111111101011010011101) ∞ , R 8 = 010(101110110010) ∞ , R 9 = 100(001000010100) ∞ , R 10 = 1000010(110001101010) ∞ , R 11 = 1111101(011000110101) ∞ , R 12 = 111(110110000111) ∞ .
For all integers i, j, k such that 1 ≤ i ≤ 4, 1 ≤ j ≤ 12 and k ≥ 0, the Steinhaus triangles ∇Q i [4k] and ∇R j [4k + 3] are strongly balanced in Z/2Z.

Can we lift some initial segments of these sequences to sequences in Z/4Z which generate strongly balanced Steinhaus triangles? To answer this question, we have determined by computer the numbers a n (S) for all 16 sequences S in Theorem 2 and all n ≥ 1. In 11 out of the 16 cases, the numbers a n (S) turn out to vanish for all sufficiently large n, i.e. the series G S (t) is just a polynomial. But remarkably, in the remaining 5 cases, the a n (S) turn out to be ultimately periodic and non-vanishing, so that the infinite series G S (t) is actually a rational function. These 16 series are displayed below; the 5 infinite ones occur for the sequences Q The origin of our sequences S 1 , S 2 , T 1 , T 2 , T 3 , T 4 , solving the problem of Molluzzo in Z/4Z, is now clear. Indeed, they are lifts to Z/4Z of the 5 sequences Q 1 , Q 3 , R 3 , R 9 , R 10 in Z/2Z with G S (t) infinite. More precisely, we have π(S 1 ) = Q 1 , π(S 2 ) = Q 3 , π(T 1 ) = π(T 4 ) = R 3 , π(T 2 ) = R 10 , π(T 3 ) = R 9 , as the reader may readily check.

1 , Q 3 , R 3 , R 9 , R 10 . Theorem 3. The generating functions G S (t) of Q 1 , . . . , Q 4 and R 1 , . . . , R 12 are: G Q 1 (t) = 1 + 8t
, G R 1 (t) = 0, G R 2 (t) = 0, G R 3 (t) = 10t

From Z/4Z to Z/8Z

Having solved the problem in Z/4Z with Theorem 2, can we lift our solutions S 1 , S 2 , T 1 , T 2 , T 3 , T 4 to sequences in Z/8Z giving rise to infinitely many strongly balanced Steinhaus triangles? Unfortunately, the answer is no, as shown by the following computational result.

Figure 1 :

 1 Figure 1: Defining A * B.

Theorem 4 .

 4 The generating functions G S (t) of S 1 , S 2 , T 1 , T 2 , T 3 , T 4 are polynomials only:G S 1 (t) = 1 + 16t

Table 1 :

 1 Multiplicities of 0, 1, 2, 3 in each building block of ∇S 1 [8k] multiset union of C 1 , C 2 , C 3 . That is, by definition we have

	7 20 16 15 16 17 15 17 16 20 19
	1 9 10 9 10 15 15 16 17 17 16 15 17 15 14
	2 9 11 8 11 14 16 15 14 17 17 15 16 14 17
	3 9 10 11 8 15 17 18 17 13 16 17 15 15 14

Table 3 :

 3 Multiplicities of 0, 1, 2, 3 in each building block of ∇S 2 [8k] and ∇T i [8k + 7] for i ∈ {1, 2, 3, 4}.

			12 7 15 13 19 18 14 16 15 17 13 13
	1 7	9	7	8 14 17 19 13 15 15 14 19 13 16
	2 7 10 8 12 13 19 13 15 12 16 18 14 14 14
	3 7	9	9	9 14 15 13 18 15 17 17 14 16 13

  8 + 34t 16 + 58t 24 + 84t 32 + 88t 40 + 86t 48 + 82t 56 + 60t 64 + 36t 72 + +34t 80 + 28t 88 + 16t 96 + 2t 104 1 -t 8 , G Q 2 (t) = 1 + 4t 8 + 14t 16 + 32t 24 + 36t 32 + 48t 40 + 44t 48 + 26t 56 + 22t 64 + 8t 72 + +6t 80 + 4t 88 + 2t 96 , G Q 3 (t) = 1 + 8t 8 + 28t 16 + 46t 24 + 78t 32 + 124t 40 + 118t 48 + 96t 56 + 78t 64 + 60t 72 + 28t 80 + 20t 88 + 14t 96 + 10t 104 + 4t 112 + 6t 120 + 4t 128 + 6t 136 + 4t 144 + 2t 152 + +2t 160 + 2t 168 + 2t 176 + 2t 184 + 2t 192 + 2t 200 + 4t 208 + 2t 216 1 -t 8 , G Q 4 (t) = 1 + 8t 8 + 26t 16 + 42t 24 + 66t 32 + 62t 40 + 52t 48 + 36t 56 + 26t 64 + 12t 72 + 6t 80

  7 + 38t 15 + 70t 23 + 88t 31 + 76t 39 + 54t 47 + 44t 55 + 28t 63 + 16t 71 + 8t 79 + +4t 87 + 4t 95 + 4t 103 + 4t 111 + 4t 119 + 6t 127 + 4t 135 + 6t 143 + 4t 151 1 -t 8 , G R 4 (t) = 10t 7 + 52t 15 + 102t 23 + 136t 31 + 152t 39 + 118t 47 + 108t 55 + 80t 63 + 60t 71 + +32t 79 + 20t 87 + 8t 95 + 2t 103 , G R 5 (t) = 10t 7 , G R 6 (t) = 10t 7 + 30t 15 + 66t 23 + 96t 31 + 96t 39 + 94t 47 + 66t 55 + 42t 63 + 24t 71 + 8t 79 + +2t 87 + 2t 95 , G R 7 (t) = 10t 7 + 60t 15 + 138t 23 + 204t 31 + 304t 39 + 266t 47 + 246t 55 + 148t 63 + 64t 71 + +36t 79 + 14t 87 + 10t 95 + 8t 103 , G R 8 (t) = 10t 7 , G R 9 (t) = 10t 7 + 42t 15 + 80t 23 + 130t 31 + 164t 39 + 174t 47 + 126t 55 + 68t 63 + 38t 71 + +20t 79 + 22t 87 + 12t 95 + 2t 103 + 2t 111 + 2t 119 + 2t 127 + 2t 135 + 2t 143 + 2t 151 + +2t 159 + 2t 167 + 2t 175 + 2t 183 + 2t 191 + 2t 199 + 4t 207 + 2t 215 1 -t 8 , G R 10 (t) = 10t 7 + 58t 15 + 98t 23 + 130t 31 + 160t 39 + 138t 47 + 132t 55 + 84t 63 + 64t 71 + +34t 79 + 14t 87 + 8t 95 + 6t 103 + 2t 111 + 2t 119 + 4t 127 + 2t 135 1 -t 8 , G R 11 (t) = 4t 7 + 16t 15 + 26t 23 + 32t 31 + 30t 39 + 30t 47 + 26t 55 + 12t 63 + 8t 71 + 2t 79 , G R 12 (t) = 4t 7 .

  16 + 46t 32 + 32t 48 + 14t 64 , G S 2 (t) = 1 + 22t 16 + 60t 32 + 56t 48 + 28t 64 + 6t 80 , G T 1 (t) = 14t 15 + 40t 31 + 40t 47 + 24t 63 + 8t 79 + 2t 95 + 2t 111 , G T 2 (t) = 30t 15 + 66t 31 + 76t 47 + 32t 63 + 12t 79 , G T 3 (t) = 14t 15 + 54t 31 + 42t 47 + 34t 63 + 12t 79 + 2t 95 , G T 4 (t) = 14t 15 + 54t 31 + 64t 47 + 40t 63 + 10t 79 + 2t 95 .

Summarizing, at this stage, it is not even known whether there exist infinitely many balanced Steinhaus triangles in Z/8Z. The picture is brighter here. Indeed, the first author has shown in [START_REF] Chappelon | Regular Steinhaus graphs and Steinhaus triangles in finite cyclic groups[END_REF][START_REF] Chappelon | On a problem of Molluzzo concerning Steinhaus triangles in finite cyclic groups[END_REF][START_REF] Chappelon | A universal sequence of integers generating balanced Steinhaus figures modulo an odd number[END_REF] that, for each odd modulus m, there are infinitely many balanced Steinhaus triangles in Z/mZ. Thus, the weak Molluzzo problem is affirmatively solved for all odd m, for m = 2 and here for m = 4. On the other hand, it is widely open for all even moduli m ≥ 6.

A weaker version of the problem

Somewhat similarly to the conjecture on the existence of Hadamard matrices of every order divisible by 4, the nature of the problem seems to lie less in the rarity of the solutions than in the difficulty of pinpointing easy-to-describe ones. For instance, in Z/6Z, there are exactly 94648 sequences of length 12 yielding a balanced Steinhaus triangle; up to automorphisms, they still total 23662 classes.

We note, finally, that all known solutions so far are by explicit constructions. However, the possibility of future nonconstructive existence results cannot be ruled out, for instance with the polynomial method of Alon-Tarsi.