Alexander Rahn

Max Henkel
email: mlf.henkel@stud.fh-sm.de

Sourangshu Ghosh
email: sourangshu@iitkgp.ac.in

Eldar Sultanow
email: eldar.sultanow@wi.uni-potsdam.de

Idriss J Aberkane
email: idriss.aberkane@polytechnique.edu

AN ALGORITHM FOR LINEARIZING THE COLLATZ CONVERGENCE

Keywords: 2010 Mathematics Subject Classification. 14H52. Key words and phrases. Envelopes, Pedal Curves, Arithmetic dynamics, Ergodic Theory, Dynamical Systems, Number Theory, Diophantine Algebra, Caustics, Algebraic topology, Sums of cubes, symplectic geometry, non-archimedean dynamics

The Collatz dynamic is known to generate a complex quiver of sequences over natural numbers which inflation propensity remains so unpredictable it could be used to generate reliable proof of work algorithms for the cryptocurrency industry; it has so far resisted every attempt at linearizing its behavior. Here we establish an ad hoc equivalent of modular arithmetic for Collatz sequences, based on five arithmetic rules we prove apply on the entire Collatz dynamical system and which iteration exactly define the full basin of attraction leading to any odd number. We further simulate these rules to gain insight on their quiver geometry and computational properties, and observe they allow to linearize the proof of convergence of the full rows of the binary tree over odd numbers in their natural order, a result which, along with the full description of the basin of any odd number, has never been achieved before. We then provide two theoretical programs to explain why the five rules allow to linearize Collatz convergence, one in ZFC and one in Peano arithmetic.

Introduction

In 1937 Lothar Collatz established a conjecture known as the 3n + 1 problem, also known otherwise as Kakutani's problem, Syracuse algorithm, Hasse's algorithm, Thwaites conjecture, and Ulam's problem. The collatz problem involves the iterative sequence defined as (see OEIS [START_REF] Sloane | A006370: The collatz or 3x+1 map: a(n) = n/2 if n is even, 3n + 1 if n is odd[END_REF] for the definition of the Collatz Map):

(1)

a n = a n-1 /2, if a n-1 is even 3a n-1 + 1, if a n-1 is odd
Conway [START_REF] Conway | Unpredictable iterations[END_REF] conjectured that given any initial term a 0 , the sequence always terminates at 1. He also showed that there is no non-trivial cycle with a length lesser than 400 with Lagarias [START_REF] Lagarias | The 3x + 1 problem and its generalizations[END_REF] later increasing this lower bound to 275000. Conway [START_REF] Conway | Unpredictable iterations[END_REF], Kurtz and Simon [START_REF] Kurtz | The undecidability of the generalized collatz problem[END_REF] proved that the generalization of the Collatz problem is undecidable. The Collatz conjecture was first verified up to 5.6•10 13 by Leavens et.al. [START_REF] Leavens | 3x + 1 search programs[END_REF], 10 15 by Vardi [START_REF] Vardi | The 3x + 1 problem[END_REF], Oliveira [START_REF] Oliveira E Silva | Computational verification of the 3x + 1 conjecture[END_REF] further extended the results to 5.48 • 10 18 and as of 2020 it had been verified beyond 2 68 . The Collatz problem was stated differently by Terras [START_REF] Terras | A stopping time problem on the positive integers[END_REF] [START_REF] Terras | On the existence of a density[END_REF], to essentially compress the division by 2 [START_REF] Cloney | The 3x + 1 problem: A quasi cellular automaton[END_REF] [11]:

(2)

a n = a n-1 /2, if a n-1 is even 3a n-1 +1 /2, if a n-1 is odd
Researchers have also tried to model the Problem in various ways. Wolfram [START_REF] Wolfram | A new kind of science[END_REF] modelled it as an 8-register machine. Cloney et al. [START_REF] Cloney | The 3x + 1 problem: A quasi cellular automaton[END_REF], Bruschi [START_REF] Bruschi | Two cellular automata for the 3x + 1 map[END_REF] modeled it as a quasicellular automaton, Zeleny [START_REF] Zeleny | Collatz problem as a cellular automaton[END_REF] modeled it as an 6-color one-dimensional quasi-cellular automaton. There have been some more breakthroughs in this topic; for example Machado [START_REF] José | A clustering perspective of the collatz conjecture[END_REF] provided an interesting clustering perspective of the Collatz Conjecture.

The dynamical system generated by the 3n + 1 problem is known to create complex quivers over N, one of the most picturesque being the so-called "Collatz Feather" or "Collatz Seaweed", a name popularized by Clojure programmer Oliver Caldwell in 2017. The inflation propensity of Collatz orbits remains so unpredictable it can form the core of a reliable proof-of-work algorithm for Blockchain solutions [START_REF] Bocart | Inflation propensity of collatz orbits: a new proof-of-work for blockchain applications[END_REF], with groundbreaking applications to the field of number-theoretical cryptography as such algorithms are unrelated to primes yet, being based on the class of congruential graphs, still allow for a wide diversity of practical variants. If Bocart thus demonstrated that graph-theoretical approaches to the 3n+1 problem can be very fertile to applied mathematics, the authors have also endeavored to demonstrate its pure number-theoretical interest prior to this work [START_REF] Aberkane | On the syracuse conjecture over the binary tree[END_REF], [START_REF] Aberkane | Endomorphisms of the collatz quiver[END_REF], [START_REF] Koch | Divisions by two in collatz sequences: A data science approach[END_REF], [START_REF] Sultanow | Collatz sequences in the light of graph theory[END_REF].

Our methodology consists of using the complete binary tree and the complete ternary tree 1 over 2N + 1 as a general coordinate system for each node of the Feather. We owe this strategy to earlier discussions with Feferman [START_REF] Feferman | Is the continuum hypothesis a definite mathematical problem[END_REF] on his investigations on the continuum hypothesis, as it is known the complete binary tree over natural numbers is one way of generating real numbers. The last author's discussion with Feferman argued morphisms, sections and origamis of n-ary trees over N could be a promising strategy to define objects of intermediate cardinalities between ℵ n and ℵ n+1 , in a manner inspired from Conway's construction of the surreal numbers [START_REF] Knuth | Surreal Numbers: How Two Ex-students Turned on to Pure Mathematics and Found Total Happiness[END_REF], which itself began by investigating the branching factor of the game of Go.

Related Research

2.1. Goodstein Sequences and Hydra Games. The idea of attacking the Collatz conjecture from the angle of logic and set theory is not new. Hydra Games were first introduced by Kirby and Paris [START_REF] Kirby | Accessible independence results for peano arithmetic[END_REF] and Arzarello [START_REF] Artigue | Goodstein sequences: The power of a detour via infinity[END_REF] provided a rather wide outline of how their consideration could, in fact, lead to a set-theoretical solution of the Collatz conjecture. The convergence of Goodstein Sequences indeed, which form the core of Kirby and Paris' demonstration that no Hydra Game can be lost, cannot be proven in Peano Arithmetic alone. Their founding element however, which is the base-k hereditary representation of a number n, can be defined without the axiom of Choice.

Definition 1. Let us write any given number n as a sum of powers of a base k. Let us further write the exponents themselves as sums of powers of a base k, this process will continue until we reach 1 in the exponent. This representation is denoted as the base-k hereditary representation of n.

The Goodstein sequence is generated by repeatedly increasing or "bumping" the base k to k + 1 and then subtract by 1. Mathematically this can be defined by the recursive sequence

G 0 (n) = n and G k (n) = B[k + 1](G k-1 (n)) -1.
Here the operator B[b](n) takes base-k hereditary representation of n and then replaces the base with k + 1. An example of this as given by Klein [START_REF] Artigue | Goodstein sequences: The power of a detour via infinity[END_REF] starts with 266

u 0 = 2 2 2+1 + 2 2+1 + 2 1 = 266 u 1 = 3 3 3+1 + 3 3+1 + 3 1 -1 = 3 3 3+1 + 3 3+1 + 2 ≈ 10 38 u 2 = 4 4 4+1 + 4 4+1 + 2 -1 ≈ 10 616 u 3 = 5 5 5+1 + 5 5+1 ≈ 10 10921
Goodstein [START_REF] Goodstein | On the restricted ordinal theorem[END_REF] proved that this sequence shall always terminate at 0.Kirby and Paris [START_REF] Kirby | Accessible independence results for peano arithmetic[END_REF] showed that this theorem cannot be proven by Peano arithmetic alone. The idea of a Hydra game is similar to the Goodstein sequence, the name "Hydra" comes from Greek mythology describing the battle between Hercules and the Hydra of Lerna, with any of its multiple heads growing two more each time it is cut. In this game a tree is representing the Hydra, and the game consists of cutting a branch of the tree (or one of the multiple "heads") turn by turn. The Hydra then grows according to a set of rules, a finite number of new heads in response to the cutting. Kirby and Paris [START_REF] Kirby | Accessible independence results for peano arithmetic[END_REF] showed that Hydra will get killed by Hercules regardless of the strategy used to cut its heads. They also proved that similar to Goodstein Sequences this property cannot be proven by Peano arithmetic alone. They proved this by demonstrating that if the well-ordering hypothesis for integers (i.e., within Peano arithmetic) could be used to demonstrate the convergence, then the theorem regarding Goodstein sequences could be reduced to the famous result of Gentzen [START_REF] Gentzen | Die widerspruchsfreiheit der reinen zahlentheorie[END_REF] named "Gentzen's consistency proof", meaning that from solving the Hydra Game From one may prove the consistency of Peano arithmetic, which cannot be achieved within Peano arithmetic, as known from the Gödel incompleteness theorem [START_REF] Godel | Über formal unentscheidbare sätze der principia mathematica und verwandter systeme, i[END_REF]. Cichon [START_REF] Cichon | A short proof of two recently discovered independence results using recursion theoretic methods[END_REF] and Hodgson [START_REF] Hodgson | Herculean or sisyphean tasks[END_REF] discussed a similar sequence than that of Goodstein, which is called a "weak Goodstein Sequence", also used in the Arzarello argument. In this sequence one also writes a number as a sum of powers of a base k, but the exponents are not further written in this way. An example of this is given by Arzarello [START_REF] Artigue | Goodstein sequences: The power of a detour via infinity[END_REF] starts with 266 as earlier

u 0 = 2 8 + 2 3 + 2 1 = 266 u 1 = 3 8 + 3 3 + 3 1 -1 = 3 8 + 3 3 + 2 = 6590 u 2 = 4 8 + 4 3 + 2 -1 = 4 8 + 4 3 + 1 = 65601 u 3 = 5 8 + 5 3 + 1 -1 = 390750
Cichon [START_REF] Cichon | A short proof of two recently discovered independence results using recursion theoretic methods[END_REF] further proved the convergence of all weak Goodstein sequences by showing that one can assign the m-tuplet of the coefficients of the decomposition in base n + 2 to each term u n of any such sequence and then demonstrate that the m-tuplets are well-ordered in a purely decreasing lexicographic way. In contrast to the Goodstein sequences, the convergence of weak Goodstein sequence can be proven by Peano Arithmetic. The above mentioned results of Cichon [START_REF] Cichon | A short proof of two recently discovered independence results using recursion theoretic methods[END_REF] and Kirby and Paris [START_REF] Kirby | Accessible independence results for peano arithmetic[END_REF] were alternatively proved by Caicedo [START_REF] Caicedo | Goodstein's function[END_REF] using proof theoretic results of Lob-Wainer's fast growing hierarchy of functions. Other excellent literature discussing the independence of Goodstein Sequence and Peano Arithmetic Axioms are done by Kaplan [31] and Miller [START_REF] Miller | On the independence of goodstein's theorem[END_REF] in their thesis. Kaplan has further demonstrated a method for finding "nonstandard models" of Peano Arithmetic that satisfy Goodstein's theorem using indicator theory, but a more significant contribution is that of Stepien and Stepien 2017 [START_REF] Stępień | On the consistency of the arithmetic system[END_REF] with their groundbreaking approach to the demonstration of the consistency of arithmetic.

Barina [START_REF] Barina | Convergence verification of the collatz problem[END_REF] introduces a new algorithmic approach for a computational convergence verification of the Collatz problem. For this he used a single-threaded CPU implementation verifying 4.2 • 2 109 128-bit numbers per second on Intel Xeon Gold 5218 CPU computer. His parallel OpenCL implementation reached a speed of 2.2 • 10 11 128-bit numbers per second on NVIDIA GeForce RTX 2080. In conformity with the approach by Koch et al. [START_REF] Koch | Divisions by two in collatz sequences: A data science approach[END_REF] he used the advantage that is given by the binary representation of integers.

Kleinnijenhuis et al. [START_REF] Kleinnijenhuis | The collatz tree as a hilbert hotel: a proof of the 3x + 1 conjecture[END_REF] applied Hilbert's paradox of the Grand Hotel to the Collatz problem and used Wolfram Mathematica for computations that involve very large numbers. These large numbers (and beyond) have also been simulated by Christian Koch, for this see the Collatz Python Library hosted by his GitHub repository [START_REF] Koch | Collatz python library[END_REF].

2.2. L-systems and analogies with statistical physics. The fundamental concept of our approach is to identify inevitable collisions within the phase space of the Collatz dynamical system. To that end, we need to precisely define a coordinate system of this phase space, which will be the complete binary tree over 2N + 1 but also to describe the non-ergodicity of the system, which will be captured by the distribution of the intersections of the binary and ternary trees in Section 9. The most important contribution of this paper to the solving of the Collatz conjecture is the identification and demonstration of the five fundamental laws that characterize the basin of attraction of any odd number, which we can recursively apply to define an infinite L-system developing within the complete binary tree, and the characterization of some of their most essential emerging properties, in particular their comparative branching factor. From there, the objective is to demonstrate that the L-system starting from number 1 cannot fail to finitely collide with the L-system starting from any other number, a methodology that may rightly evoke ergodic theory and statistical physics. Indeed, demonstrating on the one side that the Collatz dynamical system tends to compress trajectories to certain bottlenecks of its phase space, and using this element of proof to further demonstrate that finite collisions between any two pairs of trajectories is therefore inevitable, is a proof program we borrowed from statistical physics. However, if the already existing representations of the "Collatz Feather" do already exhibit obvious bottlenecks and phase space confinements, the most essential contribution to their further understanding lies in establishing an ad-hoc coordinate system to characterize and demonstrate the nature of these confinements precisely.

Contributions to the state of the art

In acknowledgement of the intellectual influence of the study of quantum non ergodicity to the study of discrete dynamical systems (for a more precise example, see [START_REF] Clark | Non-ergodicity in open quantum systems through quantum feedback[END_REF]) we have meant to not reduce this article to its mathematical proofs, but rather to accompany them with novel 3D visualizations of the Collatz phase space, along with specific empirical measurements of its behavior. As we explained in the previous section, both the mathematics proofs and 3D visualizations are based on the ad-hoc algebraic foundations, and in particular the coordinate system consisting of studying the intersections of both the binary and ternary trees over odd numbers, that we have established to gain further insight on the chaoticity of the Collatz feather. In Figure 1 we outline the fundamental contributions we intend to make. Green charts indicate results obtained from a two-dimensional coordinate system, purple charts indicate those obtained from a 3D-analysis of the feather. The Blue chart indicates a result obtained from both. Fundamentally, our most essential theorems consist of the five rules that are exactly defining the basin of attraction of any odd number in the Collatz dynamical system. However, the emerging properties of those five rules are hard to predict and can be counter-intuitive. They require equally novel developments in mathematical visualization and beyond, a few novel concepts as well. This interplay between conceptual and visual progress is the reason we have here endeavored to develop many figures and many frameworks, both in 2D and in 3D, and from graph theory to cellular automata, transfinite set theory, space-filling L-systems and caustics. Though not intended ab initio, these many approaches practically complement each other in achieving what we believe is one of the finest understandings of the fundamental chaoticity of Collatz orbits ever achieved. For all intent and purpose we will define Syr(x) or the "Syracuse action" as "the next odd number in the forward Collatz orbit of x". Whenever two numbers a and b have a common number in their orbit, we will also note a ≡ b, a relation that is self-evidently transitive:

(a ≡ b) ∧ (b ≡ c) ⇒ a ≡ c
The choice of symbol "≡" is a deliberate one to acknowledge a kinship between our method and modular arithmetic.

Definition 2. Actions G, V and S For any natural number a are specified as follows:

(1) G(a) Type A, B andC (1) a number a is of type A if its base 3 representation ends with digit 2 (2) a number b is of type B if its base 3 representation ends with digit 0 (3) a number c is of type C if its base 3 representation ends with digit 1 To remember which is which one need only remember the order of ABC: a+1 is dividable by 3, and so is c -1, thus A is on the left of B and C is on the right. Quiver connecting all odd numbers from 1 to 31 with the arrows of actions S,V and G. The set 2N + 1 is thus endowed with three unary operations without a general inverse that are non commutative with G • S = V . Whenever we will mention the inverse of these operations, it will be assuming they exist on N. Type A numbers are circled in teal, B in gold and C in purple.

:= 2a -1 (2) S(a) := 2a + 1. The rank of a is its number of consecutive end digits 1 in base 2. (3) V (a) := 4a + 1 = G • S(a) Definition 3.
We intend to use the quiver of Figure 3 as a general coordinate system for each node of the Collatz Feather. Paramount to our investigation will be the comparative analysis of the branching factor of the feather compared to that of the binary tree. The Collatz feather depicted by Figure 3 visualises the Collatz-sequences of the numbers from 1 to 15000 in 3D. Each branch is generated from the complete sequence of each number. For an even number, the branch is rotated around one axis, for an odd number the branch rotates in the other direction. The colors are set by Type of the number which was mentioned in Definition 3. Teal ones represent type A, golden branches represent type B numbers and purple ones represent type C numbers.

The rotation of the branches is based on a point that is moved by a vector and then rotated around a predefined axis. Two points, pre and cur which contain the previous and the current point in the form [x, y, z], are handed over to the rotation function which executes the rotation of the current point. By rotating in different directions for even and odd numbers, the individual branches are generated, which together form the feather-like construct shown in Figure 3. [START_REF] Conway | Unpredictable iterations[END_REF] return [x,y,z] Listing 1. Code for rotating the branches of the Feather in Figure 3, see [START_REF] Sultanow | Sources for the exploration of collatz sequences: Tex, mathematica and python[END_REF] Although the Collatz feather has been often represented in the literature and in popular mathematics circle, its fundamental geometry remain poorly understood. In the next section, we define the five fundamental rules that define the complete basin of attraction of any point of the feather.

x = pre[0] + rotated_vec[0] y = pre[1] + rotated_vec[1] z = pre[2] + rotated_vec

Five essential rules of Collatz dynamics

Theorem 1. The following arithmetic rules apply anywhere over the system 2N + 1 endowed with the Collatz dynamic. Their iteration ad infinitum from any odd number precisely define the entirety of the basin of attraction leading to it.

• Rule One:

∀x odd, V (x) ≡ (x) • Rule Two: ∀x, k odd, S k V (x) ≡ S k+1 V (x) and ∀x, k even, S k V (x) ≡ S k+1 V (x) • Rule Three: ∀{n; y} ∈ N 2 , ∀x odd non B, 3 n x ≡ y ⇒ n i=1 (V (4 i 3 n-i x)) ∧ S(V (4 i 3 n-i x)) ≡ y • Rule Four: ∀{n; y} ∈ N 2 , ∀x odd non B, S(3 n x) ≡ y ⇒ n i=1 (S(4 i 3 n-i x)∧S 2 (4 i 3 n-i x)) ≡ y • Rule Five ∀n ∈ N, ∀y ∈ N, ∀x odd non B where 3 n x is of rank 1, a ≡ y, a = G(3 n x) ⇒ n i=0 (S i (G(3 n-i x)) ∧ S i+1 (G(3 n-i x))) ≡ y
In the following we will prove these five rules.

Remark 2. In reference to Figure 1 we will call "vertical even" a number that can be written V (e) where e is even, and "vertical odd" if it can be written V (o) where o is odd. For example, 9 is the first vertical even number and 5 is the first vertical odd.

5.1. Proving Rule One. If a is written 4b + 1 then 3a + 1 = 12b + 4 = 4(3b + 1) therefore a ≡ b.

Proving Rule Two.

Lemma 1. Let a be a number of rank 1 thus with an odd number p so that a = G(p)

then Syr(S(a)) = G(3 • p). Let a be a number of rank n so that S -(n-1) (a) = G(p) then Syr n-1 (a) = G(3 n-1 • p) Proof. If a = 2p -1, p is odd, then it follows: S(a) = 4p -1 3 • S(a) + 1 2 = 12p -2 2 = 6p -1 = G(3 • p)
Syr(S(a)) = G(3 • p) Let's generalize to the n. If Syr(S(a)) can be written G(3 • p) it is also of rank 1, whereas S(a) was of rank 2, therefore, the Syracuse action has made it lose one rank. All we have to prove now is that Syr(S 2 (a)) = S(Syr(S(a))) under those conditions: Remark 3. The 3n + 1 action over an odd number, since it necessary yields an even one, is in fine equivalent to adding 1 to it, then the half of the result, then -1. How many times one can add an half to an odd number +1 directly depends on its base 2 representation, and in particular its number of consecutive end digits 1. Let us take Mersenne numbers for example, which are defined as 2 n -1. One can transform them consecutively in this way a number of time equal to their rank-1, indeed, 31, which is written 11111 in base 2 is of rank 5, because 32 = 2 5 so if one repeats the action "add to the number+1 the half of itself" this will yield an even result exactly four consecutive times. Thus, any strictly ascending Collatz orbit concerns only numbers a of rank n > 1, and is defined by

3 • (S 2 (a)) + 1 2 = 6a + 5 S(Syr(S(a))) = S(3a + 2) = 6a + 5 = Syr(S 2 (a)) If a is of rank n > 1, Syr(a) is of rank n -
(a + 1) • 3 2 n-1 - 1
Lemma 2. Let a be an odd number of rank 1 that is vertical even, then 3a is of rank 2 or more, and 9a is vertical even. Let a be an odd number of rank 1 that is vertical odd, then 3a is of rank 2 or more, and 9a is vertical odd.

Proof. If a is vertical even it can be written 8k + 1 ∀k : 3a = 24k + 3 and this number admits an S -1 that is 12k + 1, which is an odd number, therefore 3a is at least of rank 2.

Moreover, 9a = 72k + 9 and this number admits a V -1 that is 18k + 2, an even number. Now if a is vertical odd, it can be written 8k + 5 and ∀k : 3a = 24k + 15 and 9a = 72k + 45. It follows that 3a admits an S -1 and 9a admits a V -1 , respectively 12k + 7 and 18k + 11 and they are both odd. Lemma 3. Let a be a number that is vertical even, then (a) ≡ S(a) and S k (a) ≡ S k+1 (a) for any even k. Let a be a number that is vertical odd, then S(a) ≡ S 2 (a) and S k (a) ≡ S k+1 (a) for any odd k.

Proof. If a is vertical even then it can be written as G(p) where p is necessarily vertical (odd or even). We proved that 3p is then of rank 2 or more and also that we have Syr(S(a)) = G(p) so it is necessarily vertical odd (since 3d is of rank 2 or more) so Syr(a) = V -1 (Syr(S(a)) and therefore a ≡ S(a). This behavior we can now generalize to the n, because if a is vertical even with a = G(p), then the lemmas we used also provide that Syr n (S n (a)) = G(3 n • p) and therefore Syr n (S n (a)) will be vertical even for any even n because 3 n • p will be vertical something (even or odd, depending on p only) for any even n. Now if a is vertical odd it can be written G(p) and p is necessarily of rank 2 or more because G • S = V . Thus 3p is vertical (even or odd) and therefore Syr(S(a)) = G(3p) is vertical even. Remark 4. Observe that in the process of proving Rule Two we also demonstrated that any number of rank 2 or more is finitely turned into a rank 1 number of type A by the Collatz dynamic, and that any number x of rank 2 or more so that x ≡ S(x) under Rule Two is finitely mapped to a type A number that is vertical even, therefore proving the convergence of such numbers is enough to prove the Collatz Conjecture.

Proof. If a = G n+2 (S(b)) by definition a = 2 n+3 b+1. Then 3•a+1 = 3(2 n+3 b+1)+1) = 2 n+3 • (3b) + 4.
As this expression can be divided by 2 no more than twice, we have

Syr(a) = 2 n+1 3b + 1 = G n (S(3b)). Note that if n = 1 then V -1 (Syr(a)) = V -1 (2 2 • (3a) + 1) = 2 2 • 1 4 • (3b) = 3b
which is of course an odd number. Therefore Syr(a) is vertical odd and V -1 (Syr(a)) = 3b thus we have proven that a ≡ 3b.

If n = 0 then a = 2 3 • b + 1 so 3(a + 1) = 2 3 • 3b + 4 therefore Syr(a) = S(3b) and thus a ≡ S(3b). From this we can generalise the progression of numbers that can be written G n (x) where x is of rank 2 or more. Let b be any odd number:

• All "Variety S" numbers above b are written

V (b • 2 2k-1 ) or S(b • 2 2k ) = 2 2k+1 • b + 1 and • all "Variety V" numbers above b are written V (b • 4 k ) or equivalently S(b • 2 2k+1 ) = 4 k+1 • b + 1.
Any number g that can be written G n (V (x)) with x odd and n > 0 may thus be finitely reduced under the Collatz dynamic to a number that can be written either S(3 m x) or V (3 m x) by the repeated following transformation:

(g -1) • 3 4 k + 1
Therefore we have indeed that,

• for Variety S numbers: Figure 4 shows a few applications of Rules Three, Four and Five plotted in gold. Rules One and Two are plotted in black. Whenever a number is connected to 1 by a finite path of black and/or gold edges it is proven to converge to 1.

2 2k+1 • b • 3 4 k + 1 = 2b • 3 k + 1 = S(b • 3 k ), which proves Rule Four. • for Variety V numbers: 4 • 4 k • b • 3 4 k + 1 = 4b • 3 k + 1 = V (b • 3 k ) which proves Rule Three because Rule One already provides that V (b • 3 k ) ≡ b • 3 k .

The Golden Automaton

Definition 4. On {2N + 1; G, S} where Rules One and Two are considered precomputed (the black edges on Figure 4) the systematic computation of Rules Three, Four and Five from number 1 onward is called the "Golden Automaton".

6.1. "Golden Arithmetic". Our purpose is to develop an ad hoc multi-unary algebra that could found a congruence arithmetic specifically made to prove the Collatz conjecture, and which we intend as an epistemological extension of modular arithmetic, hence our use of the symbol ≡ in this article rather than the usual ∼ which is seen more frequently in the Collatz-related literature. This "Golden arithmetic" involves words taken in the alphabet {G; S; V ; 3}, which we will call in their order of application, just like in turtle graphics. For example VGS3 means 3 • S • G • V Rules 3, 4 and 5 may now be reformulated as such, without loss of generality as long as Rules One and Two are still assumed:

• Rule Three: Let b be of type B, then b ≡ V GS3 -1 from b. We will call this action R b (x) = 16 x 3 + 1 • Rule Four: Let c be of type C, then c ≡ GS3 -1 from c. We will call this action R c (x) = 4x-1 3

• Rule Five: Let a be of type A, then a ≡ G3 -1 from a. We will call this action R a (x) = 2x-1 3

As Rules One and Two ensure that the quiver generated by the Golden Automaton is branching, with each type B number that is vertical even providing both a new A and a new B to keep applying respectively rules 5 and 3, we may follow only the pathway of type A numbers to define a single non-branching series of arrows, forming a single infinite branch of the quiver. Starting with number 15, this leads straight to [START_REF] Kaplan | A classification of non-standard models of peano arithmetic by goodstein's theorem[END_REF] Again, it is in no way a problem, but rather a powerful property of the Golden Automaton that this particular quiver branch already cover 19 steps (and actually more) because each of them is branching into other solutions.

We may follow another interesting sequence to show that in the same way that Mersenne number 15 finitely solves Mersenne number 31, Mersenne number 7 solves Mersenne number 127, this time we will follow a B branch up to Syr 6 (127) which we know can be written G(3 6 ) because 127 is the Mersenne of rank 7.

By Rule 4 we have the first equivalence 7≡9 and 9≡25≡49.

So by Rule 2 we also have 25≡51.

Rule 3 gives 51≡273 and again 273≡1457=G(729)≡127.

The cases of 15 proving the convergence of 31 and 27 and of 7 proving the one of 127 naturally leads us to the following conjecture: Conjecture 1. Suppose all odd numbers up to 2 n are proven to converge to 1 under the Collatz dynamic, then the Golden Automaton finitely proves the convergence of those up to 2 n+1

And indeed we already have that the Golden Automaton starting with 1 proves 3 by Rule One, then 3 proves all numbers from 5 to 15 which in turn prove all numbers from 33 to 127. In the next subsection we render larger quivers generated by the Golden Automaton to provide a better understanding of their geometry and fundamental properties, and to demonstrate why it is so, and more generally, why it can be proven they can reach any number in 2N + 1 in ZFC.

The Golden Automaton linearizes Collatz convergence

In this cellular automaton, each cell is identified by a unique odd number and can only adopt three states:

• Black, meaning the odd number is not (yet) proven to converge under the iterated Collatz transformation or equivalently that it is only equivalent to another black number • Gold, meaning the odd number is proven to converge and the consequences of its convergence have not yet been computed, ie. it can have an offspring • Blue, meaning the number is proven to converge and the consequences of its convergence have been computed ie. its offspring has already been turned gold In this ad hoc yet simpler game of life each gold cell yields and offspring then turns blue, and whenever a cell is blue or gold its odd number is proven to converge. Starting with one cell colored in gold at the positions 1, it applies the following algorithm to each gold cell in the natural order of odd numbers:

(1) Rule 1: if a cell on x is gold color cell on V (x) gold (2) Rule 2: if a cell on x is gold, color cell on S(x) gold depending on the precise conditions of rule 2 (3) If a cell on a of type A is gold, then color that on R a (x) in gold (4) If a cell on c of type C is gold, then color that on R c (x) in gold (5) After applying the previous rules on a gold cell, turn it blue Note that applying R b on a type B number being equivalent to Rule 1 then R c the algorithm needs not implement a defined R b Whenever a complete series of odd numbers between 2 n + 1 and 2 n+1 -1 has been colored in gold, it ticks it and returns what we will call its computational "expense", namely all the numbers colored blue and gold that are higher than 2 n+1 -1, thus giving a clear measurement of the algorithmic time it takes the Golden Automaton to prove the convergence of each complete level of the binary tree over 2N + 1. We then plot the evolution of this expense on a linear and a logarithmic scale.

Figure 5 is illustrating of the game we defined for the case n = 6. On the middle image, row {5;7} has been solved , with an "expense" of 8 numbers also solved above it. On the right image, row {9; 11; 13; 15} with an expense of 6. As number 1 is the neutral element of operation R c we leave it in gold during all the simulation. In Figure 6 and Figure 7 we scaled up the simulation to n = 12. The charts shown in Figure 12 plot the amount of extra numbers proven to converge above any row n of the binary tree when the Golden Automaton has just finished proving its entire convergence. The chart on the right plots the result against a logarithmic scale, with progressions 2, 5 n (orange line), 3 n (green) and 3, 5 n (red) in comparison. The linelike shape indicates the linear behavior of the Golden Automaton, solving the rows of the binary tree in their natural order, and solving about 3 n additional odd numbers above any row 2 n it has just solved. We further investigated the behavior of the Golden Automaton when mapped on the ternary tree over odd numbers, that is, the set of odd numbers endowed with operations {•3; •3 + 2; •3 -2}. The automaton was still demonstrating the entire rows 3 n one after another, this time with about 5 n extra numbers solved above each row. These graphs are shown in Figure 13. From there we can thus provide two strategies to finalise a proof of the Collatz conjecture. The first would be to demonstrate the Golden Automaton defines a game that is strictly simpler than a Hydra Game over the graph of all unsolved numbers up to any arbitrary odd integer. The second would be to demonstrate the comparative branching factor of the Golden Automaton, as it is diagonal to the binary tree, is strictly above 2, and that thus the population of solved dots can only finitely take over the population of unsolved ones, or, put in another way, that the basin of attraction of any supposedly diverging odd number grows too fast not to collide the basin of number 1.

The Golden Automaton as a Hydra Game

As we mentioned in 2.1 the idea of attacking the Collatz conjecture from the angle of transfinite arithmetic and in particular the model of the Hydra Game is not new, as Arzarello and others considered it in 2015 [START_REF] Artigue | Goodstein sequences: The power of a detour via infinity[END_REF]. Both Goodstein sequences and Collatz sequences iterate base changes, but the Collatz sequences do so in a much less diverging manner, involving only bases 2, 3 and 4, with each critical step of their trajectory obeying the following rules:

(1) if a number is written x 1 . . . The purpose of this subsection is to identify provable fundamental properties of the Golden Automaton by computationally scaling it up on the full binary tree over 2N + 1.

To streamline its algorithmic scaling, we use the simplified rules we defined in the previous subsection, again, without loss of generality. Our precise purpose is to pave the way for a formal demonstration that proving the convergence of odd numbers up to n is always isomorphic to a Hydra Game. In Figure 14-17 we color all the elements of 24N -7 as for example {17, 41, 65, . . .} in red to as we demonstrate in the next section they precisely from the "heads" in the Hydra Game. Theorem 2. In ZFC, the Collatz conjecture is true. Definition 5. A hydra is a rooted tree with arbitrary many and arbitrary long finite branches. Leaf nodes are called heads. A head is short if the immediate parent of the head is the root; long if it is neither short nor the root. The object of the Hydra game is to cut down the hydra to its root. At each step, one can cut off one of the heads, after which the hydra grows new heads according to the following rules:

• if the head was long, grow n copies of the subtree of its parent node minus the cut head, rooted in the grandparent node. • if the head was short, grow nothing Lemma 5. The Golden Automaton reaching any natural number is a Hydra Game over a finite subtree of the complete binary tree over 24N -7.

Proof. The essential questions to answer in demonstrating either a homomorphism between a Hydra game and the Golden Automaton reaching any odd number, or that the Golden Automaton is playing at worst a Hydra Game are:

• What are the Hydra's heads? • How do they grow?

• Does the Golden Automaton cut them according to the rules (at worst)? Definition 6. A type A number that is vertical even is called an A g . The set of A g numbers is 24N -7. Type B numbers that verify b ≡ S(b) and type C numbers that verify c ≡ S(c) under Rule Two are called Bups and Cups respectively.

8.1.

What are the Hydra's heads? A g numbers are the heads of the Hydra. They are 12 points apart on 2N + 1 (24 in nominal value, e.g. 17 to 41) and any Bup or Cup of rank > 1 they represent under Rule Five is smaller than them since action R a is strictly decreasing so up to the n th A g there are 2n (Bups + Cups) of rank 2 or more and half of them are equivalent to these A g (e.g. between 17 and 41 Bup 27 is equivalent to A g 41, which is equivalent to Cup 31 by Rule Four 8.2. How do they grow? Between any two consecutive A g in 2N + 1 there are • 8 non-A numbers • 1 of them at most is mapped to the second A g • 3 at most are "ups" (Bup or Cup) of rank 2 or more Besides, we also have anywhere that:

• Let b be of type B, there are 2b 3 numbers of type A g that are smaller than V 2 (b) • Let c be of type C, there are S(c) 3 numbers of type A g that are smaller than V 2 (c) • Let 3c be a type B where c is of type C, there are S(c) 3 numbers of type A g up to R b (3c) included • Let 3a be a type B where a is of type A, there are G(a) 3 numbers of type A g smaller than R b (3a) Which is defining the growth of the heads. Indeed, any supposedly diverging A g is forming a Hydra, as we have proven 24N -7 contains an image of all undecided Collatz numbers and that any non-decreasing trajectory identifies a subtree within this set. 8.3. Does the Golden Automaton play a Hydra game? It could be demonstrated that the Golden Automaton is playing an even simpler game as it is branching and thus cutting heads several at a time and in particular cutting some long heads without them doubling 2 but as this is needless for the final proof we can now simply demonstrate that even under the worst possible assumptions it follows at least the rules of a regular Hydra game.

The computing of 15 ≡ . . . ≡ 27 that we detailed in Subsection 3.1 is one case of the playing of a Hydra Game by the Golden Automaton; we underlined each use of Rule 5 specifically so the reader can now report to it more easily, because each time this rule is used, a head (A g ) has just been cut.

The demonstration that 27 and 31 converge is the cutting of heads 41 and 161 respectively. This single branch of the Automaton having first cut head 17, reaches to the head 1025 via B-typed numbers 15 and 81. It is therefore playing a Hydra with 1025+7 24

= 43 heads of which one [START_REF] Aberkane | On the syracuse conjecture over the binary tree[END_REF] is already cut at this point and of which at least 8 are rooted (so cutting them does not multiply any number of heads). This process being independent of the targeted number, we now have that the reaching of any number by the Golden Automaton is at least equivalent to the playing of a Hydra with n heads of which 0 < m < n are rooted. Even without demonstrating more precise limit theorems for each factors n and m (which could still be a fascinating endeavor) the road is now open for a final resolution of the Collatz conjecture.

From there indeed, we know with Goodstein [START_REF] Goodstein | On the restricted ordinal theorem[END_REF] and Kirby and Paris [START_REF] Kirby | Accessible independence results for peano arithmetic[END_REF] that assuming 0 is well-ordered, no Hydra game can be lost. Since we have that the reaching of any number n is a Hydra Game for the Golden Automaton, we have that the Golden Automaton cannot fail to finitely reach any natural number.

The Golden Automaton as a winning cellular game

Beyond graph theory, we want to outline here a different strategy towards a resolution of the Collatz conjecture in Peano arithmetic, by studying the Golden Automaton as a cellular game invading the phase space defined by the complete binary tree over odd numbers. This is therefore essentially a 3D representation of the dynamic we studied in section 7, designed to specifically display potential collisions between the basins of attraction of number 1 and any supposedly diverging other number. We thus employ the same game, that is, a zero-player game which is significantly simpler than John Conway's Game of Life and played on the complete binary tree {2N + 1; G, S}, except that we now allow it to start from any point rather than 1, and study its development within the basin of 1. The purpose of this approach is both to identify possibly provable patterns in the way any sub-basin would be embedded in the 1-basin, but also to simply observe whether or not the five rules, for any point, finitely spawn a population of points between any starting number x and 2 n x that is bigger than 2 n , which would imply that finite collisions between any two basins are inevitable.

In Figure 20 an orthogonal view of the Golden Automaton starting from 1 (in blue) merged with one starting from 1457 (in green), which is the first A g in the trajectory of 127. We input the A g rather than 127 itself to specifically study the impact of divergence on the form of the basin. Figure 19 visualizes the Golden Automaton starting from 1 (blue) merged with the one starting from 1457 (green). Mersenne numbers like 511, on which six iterations of the Collatz sequence yields 1457, are particularly interesting to study with the Golden Automaton in that they form the benchmark of Collatz divergence. Indeed, at any height 2 n of the binary tree over odd numbers, no number can monotonously increase more than a Mersenne. As the Golden Automaton only accounts for the backward orbits of any number, precisely, defining the basin of attraction of any number, the interest of studying its expansion on the numbers generated by the monotonous increase of a Mersenne number specifically consists in observing, and further, measuring, to which extent the basin of attraction of any number will increase if we assume its divergence.

Figure 19. The Golden Automaton starting from 1 (blue). All its intersections with the one independently starting from 1457 are shown in green: it is fully overlapping it.

The following Figure 20 provides an orthogonal view of the Golden Automaton starting from 1 (blue) merged with one starting from 161 (green), which is the first A g of number 31. As 31 is both lower than 127 in the binary tree and is displaying a higher orbit inflation propensity its overlap ends up much larger than that of 127, meaning its basin of attraction inflates along with its orbit. In Figure 22 we can see the Golden Automaton starting from 161 overlapping the one starting from 1. 161 is marking the end of the first monotonous increase of Mersenne number 31. This number however is more diverging than the next Mersenne 127 (1457), and therefore, as its orbit inflates, so does its basin of attraction. Another important property of Mersenne 31 is that, as defined by OEIS [START_REF] Sloane | A005184: Self-contained numbers: odd numbers n whose collatz sequence contains a higher multiple of n[END_REF], it is "self-contained", meaning its orbits contains multiples of itself (ie. the number 155). The convexoid that is structuring the center of the basin of attraction of number 1 appears to be the truncated caustic generated by the multiplication by 3 on the binary tree projected on the unit circle. In the next figure we thus implement the fundamental operations of the ternary tree, {•3; •3 -2; •3 + 2}.

Figure 23 visualizes the ternary tree over the binary tree projected on the unit circle. Operation •3 is figured in yellow, •3 -2 in purple and •3 + 2 in teal. Number 1 is at exactly π, number 3 at 2π, number 7 at π 2 and number 5 at 3π 2 .

Figure 23. The ternary tree over the binary tree projected on the unit circle.

And then, with the purpose of better studying the impact of the multiplication by 3 on the non-ergodicity of the Collatz orbits, we implement a version with a better outline of the departure and arrival point of operation •3.

Figure 24 shows the truncated caustic of operation •3 alone, this time the color gradient indicates departure (red) and arrival (yellow), thus further outlining the nonergodicity of the implied trajectories. The following graphs provide some measurements of the non-ergodicity generated by the truncated caustic (Figure 25). Clockwise, from the upper left: number of points on each side of the unit circle (Side 7 is "top", side 5 is "bottom") after iterations of the multiplication by 3 on number 1. The Top/Bottom ratio, on the next figure, converges to approximately 0,7. The next two figures display respectively the cosine and sine of the multiplication by 3 of each point of the unit circle. The apparent growth rate of all the Mersenne numbers from 31 to 8191 is now calculated as the solution for x to n k=1 x k = N where N is the number of dots in the basin of the number that are found between itself and its first A g (for example: 161 is the first A g of 31) and n is the number of multiplications by 2 from the initial number that are needed to reach the row of this first A g in the binary tree (for example, n=3 to go from 31 to 161). All the growth rates are larger than 2 (orange line)(Figure 28). We have already demonstrated in section 4 that any A g can be written G(x3 n ) and it is precisely the catching of A g numbers with a large factor n by the Golden Automaton that increases the quantity of dots in its offspring per given finite series of rows of the binary tree. Specifically, those A g numbers, which are by definition the ones that can be iterated the most upon by the Golden Automaton are not evenly distributed on the unit circle, and we postulate that this is the most fundamental reason behind the apparent branching factor of the Golden Automaton being strictly greater than 2 in any point we calculated. And if indeed the branching factor of the Golden automaton tends to always be greater than two, it is impossible for two separate basins of attraction to cohabitate on the binary tree.

Conclusion

Whenever the Collatz conjecture is being studied, one cannot fail to quote Paul Erdős' famous claim that "mathematics may not be ready for such problems"; depending on one's epistemological attitude, the quote may either seem discouraging or the incentive to achieve a novel theoretical breakthrough. This is what we have attempted in this article, primarily by establishing an ad hoc equivalent of modular arithmetic for Collatz sequences to automatically demonstrate the convergence of infinite quivers of numbers, based on five arithmetic rules we proved apply on the entire dynamical system and which we further simulated to gain insight on their graph geometry and computational properties. This endeavor has led us to focus on the origins of the non-ergodicity of the Collatz dynamical system, which we found in the geometric properties of the multiplication by 3 on the complete binary tree over odd numbers. These symmetry-breaking properties, indeed, could be further studied in other contexts such as cryptography, harmonic analysis, or the study of L-functions. In particular, following Bocart 2018 [START_REF] Bocart | Inflation propensity of collatz orbits: a new proof-of-work for blockchain applications[END_REF] one can now gain a better insight at the geometric properties of the pseudorandomness generated by Collatz series, and even more, by the Collatz basins.

11. Attribution I. Aberkane created the framework of studying the Collatz dynamical system in the coordinates defined by the intersection of the binary and ternary trees over 2N + 1, identified and demonstrated the five rules and predicted they would be isomorphic to a Hydra game over the set of undecided Collatz numbers, which he defined as well. He directed the 3D visualization of the Golden Automaton and its 2D projection on the unit circle, and the search for its comparative growth rate. Contributing equally, A. Rahn and E. Sultanow designed and coded an optimised, highly scalable 2D graphical implementation of the five rules and ran all the simulations, confirming the Hydra game isomorphism and computing the first ever dot plot of the Golden Automaton over odd numbers, which they optimised as well. They were also the first team to ever simulate the five rules to the level achieved in this article, and to confirm their emerging geometric properties on such a scale, including the linearity of their logarithmic scaling and the limit reproductive rates of single dots of the golden automaton. A. Rahn also designed, coded and optimized the 3D generated feather (Figure 3). Max Henkel was in charge of generating the other 3D figures and related simulations and was the first to outline the convexoid at the center of the Golden Automaton's basin of attraction. Sourangshu Ghosh was in charge of giving an overview of the topic described and also provided editorial guidance for the organization of the results' communication.

Funding

This work was supported by a personal grant to I. Aberkane from Mohammed VI University, Morocco and by a collaboration between Capgemini, Potsdam University, The Nuremberg Institute of Technology, and Strasbourg University. Even though the last author began the initial works leading to this article at Stanford University, 42 School of Code Fremont and the Complex Systems Digital Campus Unesco-Unitwin the funding that financed the discovery of his most important theorems is fully attributable to Mohammed VI University.

Figure 1 . 4 .

 14 Figure 1. Structure of the original contributions of this paper.

Figure 2 .

 2 Figure2. Quiver connecting all odd numbers from 1 to 31 with the arrows of actions S,V and G. The set 2N + 1 is thus endowed with three unary operations without a general inverse that are non commutative with G • S = V . Whenever we will mention the inverse of these operations, it will be assuming they exist on N. Type A numbers are circled in teal, B in gold and C in purple.

Figure 3 .

 3 Figure 3. The Collatz feather rendered in Blender, this time using the same ternary typology as defined in 3.

  def oddRotation(pre, cur, rot, counter): vec = [cur[0]-pre[0],cur[START_REF] Sloane | A006370: The collatz or 3x+1 map: a(n) = n/2 if n is even, 3n + 1 if n is odd[END_REF]-pre[START_REF] Sloane | A006370: The collatz or 3x+1 map: a(n) = n/2 if n is even, 3n + 1 if n is odd[END_REF],cur[START_REF] Conway | Unpredictable iterations[END_REF]-pre[START_REF] Conway | Unpredictable iterations[END_REF]] rotation_degrees = -rot/30 rotation_radians = np.radians(rotation_degrees) axis = [1,0,1] rotation_axis = np.array(axis) rotation_vector = rotation_radians * rotation_axis rotation = R.from_rotvec(rotation_vector) rotated_vec = rotation.apply(vec)

1 ,

 1 and Syr(S(a)) = S(Syr(a))

5. 3 .Lemma 4 . 3 m 2

 3432 Proving Rules Three and Four. Let a be a vertical even number with a = G n+2 (S(b)) where n and b are odd, then a ≡ 3 n+1 2 (b). Let a be a vertical even number with a = G m+2 (S(b)) where m is even (zero included) and b is odd, then a ≡ S((b))

5. 4 .

 4 Proving Rule Five. Any type A number of rank 1 can be written a = G(b) where b is of type B. In proving Rule Two we showed that any number of rank n > 1 is finitely mapped by the Collatz dynamics to G(3 n-1 • G -1 (S -(n-1) (a))), which combined with Rule Two itself gives Rule Five.

Figure 4 .

 4 Figure 4. Application of the five rules starting from 1 ≡ 3 ≡ 5.

Figure 5 .

 5 Figure 5. The five rules completing row by row.

Figure 6 .

 6 Figure 6. case 12, state of the tree when seventh row has just been completed.

Figure 7 .

 7 Figure 7. case 12, state of the tree when eighth row has just been completed.

Figure 8 .

 8 Figure 8. State of row 8 (129 to 255) when it has just been finished.

Figure 9 .

 9 Figure 9. State of Row 9 (257 to 511) when Row 8 has just been finished.

Figure 10 .

 10 Figure 10. State of Row 10 (513 to 1023) when row 8 has just been finished

Figure 11 .

 11 Figure 11. State of row 11 (going from 1025 to 2047: each line has about 100 dots)

Figure 12 .

 12 Figure 12. Amount of extra numbers proven to converge in a binary tree above row n and its logarithmic graph.

Figure 13 .

 13 Figure[START_REF] Bruschi | Two cellular automata for the 3x + 1 map[END_REF]. Amount of extra numbers proven to converge in a ternary tree above row n and its logarithmic graph.

1 n in base 2 , 1 n

 121 then it is finitely mapped to the result of operation G on the number written y 1 . . . in base 3 with y = (x-1)/2. Note that this is the one and only way an orbit can grow in the Collatz dynamics.

( 2 ) 2 n 1 1 2n+1 in base 2 ( 3 )

 221123 if a number is written z 2 . . . in base 4 then it is immediately mapped to a number written x 1 . . . if a number is written s 0 . . . 0 2n+1 1 in base 2 then it is equivalent to the result of operation S on r 0 . . . 0 n in base 3 with r the base 3 representation of s (4) if a number is written v 0 . . . 0 2n 1 in base 2 then it is equivalent to w 0 . . . 0 n in base 3 with w the base 3 representation of v

Figure 14 .

 14 Figure 14. Golden Automaton confined to numbers smaller than 32.

Figure 15 .

 15 Figure 15. Golden Automaton confined to numbers smaller than 64.

Figure 16 .

 16 Figure 16. Golden Automaton confined to numbers smaller than 128.

Figure 17 .

 17 Figure 17. Golden Automaton confined to numbers smaller than 256.

Figure 18 .

 18 Figure 18. Orthogonal view of the Golden Automaton starting from 1 (in blue). All its intersections with the automaton starting independently from 1457 are shown in green. As expected from our 2D works in section 7 the Golden automaton starting from 1 covers all numbers.

Figure 20 .

 20 Figure 20. Orthogonal view of the Golden Automaton starting from 1 (blue), which is overlapping the one starting from 161 (green).

Figure 21 .

 21 Figure 21. Close-up of the top of the Golden Automaton starting from 1, overlapping the one starting from 161.

Figure 22 .

 22 Figure 22. The Golden Automaton starting from 161 overlapping the one starting from 1.

Figure 24 .

 24 Figure 24. Truncated caustic of operation •3, with a color gradient from preimage (orange) to image (yellow).

Figure 25 .

 25 Figure 25. Non-ergodic measurements generated by the truncated caustic.

Figure 26 .

 26 Figure 26. Amount of numbers proven by applying the five rules, starting from (clockwise, from the upper left corner) numbers 31, 511, 13121 and 161 respectively, by row of the binary tree. Function 2 n , implemented from the starting point, is shown in comparison.

Figure 27 .

 27 Figure 27. Starting point: 118097, First row of graph: 12, Last row of graph: 29

Figure 28 .

 28 Figure 28. Growth rate of Mersenne numbers

In fact, the reason the Golden Automaton dominates 24N -7 so fast is that it is playing a much simpler game one could call "Hecatonchire v. Hydra game" namely a Hydra game where Herakles' number of arms is also multiplying at each step

Acknowledgments

I. Aberkane wishes to thank the late Prof. Solomon Feferman and Prof. Alan T. Waterman Jr, along with Prof. Paul Bourgine, Prof. Yves Burnod, Prof. Pierre Collet, Dr. Françoise Cerquetti and Dr. Oleksandra Desiateryk. The authors dedicate this work to the memory of John Horton Conway (1937-2020), Solomon Feferman (1928-2016) and Alan T. Waterman Jr (1918-2008).


Nejat Arınık

Rosa Figueiredo

Vincent Labatut

Multiple Partitioning of Multiplex Signed Networks

Keywords: Signed Graph, European Parliament, Graph Partitioning, Correlation Clustering, Structural Balance

Introduction

In a signed graph, each link is associated to a sign, which can be either positive (+) or negative (-). This type of graph can be used to model any system containing two types of antithetical relationships (like/dislike, for/against, similar/different...). A signed graph is considered structurally balanced if it can be partitioned into two [START_REF] Cartwright | Structural balance : A generalization of heider's theory[END_REF] or more [START_REF] Davis | Clustering and structural balance in graphs[END_REF] clusters, such that positive links are located inside the clusters, and negatives ones are in-between them.

However, it is very rare for a real-world network to have a perfectly balanced structure : the question is how to quantify its imbalance. Various measures have been defined for this purpose, the simplest consisting in counting the numbers of misplaced links, i.e. negative ones located inside the groups, and positive ones located between them [START_REF] Cartwright | Structural balance : A generalization of heider's theory[END_REF]. Such measures are expressed relatively to a graph partition, so processing the graph balance amounts to identifying the partition corresponding to the lowest imbalance measure. In other words, calculating the graph balance can be formulated as an graph optimization problem.

Our goal is to use this paradigm to study the roll-call voting activity of the Members of the European Parliament (MEPs) by bringing together three different disciplines : Operations Research, Social Science and Data Science. In this work, we want not only to detect groups of MEPs which would be cohesive in terms of votes, but also to identify the different characteristic voting patterns of the European Parliament (EP), i.e. the characteristic ways in which the MEP set is partitioned by these votes. In literature the standard approach to study this type of system is to extract a vote similarity network, in which nodes represent MEPs and weighted (possibly signed) links represent the similarity between two MEPs, averaged over the series of roll-calls (e.g. [START_REF] Waugh | Party polarization in congress : A network science approach[END_REF][START_REF] Traag | Significant scales in community structure[END_REF]). However, this averaging leads to some information loss due to the temporal integration performed on the raw data [START_REF] Arinik | Signed graph analysis for the interpretation of voting behavior[END_REF].

In the current work, we propose to adopt an approach based on a multiplex signed vote similarity networks, in which each layer models a single roll-call as a signed unweighted graph. All approaches proposed in the literature are based on the assumption that one is looking for a single partition in the end. However, this single-partition assumption is not compatible with all our objectives. Indeed, we look for the different characteristic polarizations of the EP, so we want our method to be able to identify several partitions. To this aim, we propose a new partitioning process for multiplex signed graphs. We apply our method to a dataset representing the voting activity during the 7 th term of the EP. As desired, it allows identifying groups of cohesive voters, but also their different characteristic voting configurations, as well as the context (i.e. legislative propositions voted through roll-calls) to which they apply. In particular, we focus on certain case studies previously analyzed and discussed by Arinik et al. [START_REF] Arinik | Signed graph analysis for the interpretation of voting behavior[END_REF] using a standard approach. Not only does our method confirm certain of their assumptions, such as the fact that Socialists and Liberals alternatively align with the left-and right-wing blocks, but it also identifies the contexts that happen. In addition, it uncovers previously overlooked properties, for instance the emergence of a strong antagonism for a proportionally small number of roll-calls, that was invisible to the traditional approach. We invite reader to see the extended work of this summarized paper for further details [START_REF] Arinik | Multiple partit. of multiplex signed networks[END_REF].

The rest of the article is organized as follows. First, in Section 2, we give the formal definition of the Correlation clustering (CC) problem. We turn to the methods in Section 3, and describe the approach we propose for the analysis of multiplex signed networks. In Section 4, we present our results on a few specific cases selected from the dataset, and discuss them. Finally, in Section 5 we summarize our findings, comment the limitations of our work and describe how they can be overcome, and how our work can be extended.

Correlation clustering problem

In this section, we give the mathematical formulation of the CC problem. Let us introduce our notations before defining the problem itself. Let G = (V, E) be an undirected graph, where V and E are the sets of vertices and edges, respectively. We note n = |V | and m = |E| the numbers of vertices and edges, respectively. Consider a function s : E → {+, -} that assigns a sign to each edge in E. An undirected graph G together with a function s is called a signed graph, denoted by G = (V, E, s). An edge e ∈ E is called negative if s(e) = -and positive if s(e) = +. We note E -and E + the sets of negative and positive edges, respectively.

Let P = {F 1 , ..., F } (1 ≤ ≤ n) be an -partition of V , i.e. a division of V into nonoverlapping and non-empty subsets F i (1 ≤ i ≤ ) that we call factions in the context of this work. For σ ∈ {+, -}, the set of positive or negative edges (depending on σ) connecting two factions

F i , F j ∈ P (1 ≤ i, j ≤ ) is E σ [F i : F j ] = {{u, v} ∈ E σ | u ∈ F i , v ∈ F j or v ∈ F i , u ∈ F j },
and its cardinality, i.e. its total number of links, is expressed as Ω σ (F i , F j ).

The Imbalance I(P ) of a partition P is defined as the total number of positive edges located between factions, and negative edges located inside them, i.e.

I(P ) = 1≤i≤ Ω -(F i , F i ) + 1≤i =j≤ Ω + (F i , F j ). (1)
The CC problem is formally described as follows.

Problem 1 (CC problem). For a signed graph G = (V, E, s), the Correlation Clustering problem consists in finding a partition P of V such that the imbalance I(P ) is minimized.

This N P -hard minimization problem appears under this name for the first time in Bansal's paper [START_REF] Bansal | Correlation clustering[END_REF], although it was addressed before in the literature, e.g. [START_REF] Doreian | A partitioning approach to structural balance[END_REF].

Methods

In this section, we describe the method that we propose to analyze our multiplex signed networks. We will handle various types of partitions, so we need to clarify our terminology first. We call voting behavior pattern of the EP (or pattern, for short) a partition of the set of all MEPs obtained for a given roll-call. The subsets of MEPs constituting this partition are called factions. A pattern represents the way the parliament is split at the occasion of a roll-call concerning a specific subject. We reserve the term clustering to refer to a partition of the set of all patterns (i.e. the patterns corresponding to all considered roll-calls). Since each pattern describes the EP behavior for a given roll-call, a clustering can also be interpreted as a partition of the set of all roll-calls. The subsets of roll-calls constituting a clustering are simply called clusters. For instance, if roll-calls #1, 2 and 3 form a cluster, this means the pattern was similar for all three corresponding roll-calls.

The goal of our method is to identify the main types of patterns occurring at the EP, and to characterize them in terms of political groups, individual MEPs and topics of the concerned legislative documents. To this aim, we propose a three-stepped method, summarized in Figure 1, and detailed in the rest of this section. The first step is to separately partition the p roll-calls, in order to get as many patterns (Section 3.1). The second step consists in applying a clustering method onto those patterns (Section 3.2). This leads to a set of k clusters, each one gathering similar patterns. The third step is to process what we call the characteristic pattern of each cluster, which is supposed to consensually represent all the patterns belonging to the cluster (Section 3.3). This results in a set of characteristic patterns, each one associated with a cluster of roll-calls, which can be used as the basis of the interpretation work.

Processing the Patterns

Detecting the pattern associated with the i th roll-call amounts to partitioning the i th layer of our multiplex signed network. This layer is an unweighted signed graph G i whose nodes are connected depending on how the MEPs they represent voted during this roll-call. MEPs who voted similarly are connected together by positive links, and are connected by negative links to MEPs that voted differently from them. MEPs who did not vote at all are isolated (nodes without any neighbor). We consider that absent MEPs should not affect the pattern, since they did not express any opinion regarding the matter at hand during this roll-call, so we simply ignore them at this stage. For those who abstained, we keep them in the graph, since abstaining is a way of expressing some middle ground position.

Next, we need to identify the factions of similarly voting MEPs remaining in the graph, which can be done by solving the Correlation Clustering problem (CC). In its original version [START_REF] Bansal | Correlation clustering[END_REF], and consistently with the definition of structural balance given earlier in the introduction, it consists in finding a partition of the set of vertices which maximizes both the number of positive links located inside the subgroups, and that of negative links located between them. In order to identify this partition, we coded Ex-CC (Exact Correlation Clustering), which is a mixed integer programming (MIP) based method able to solve the CC problem exactly [START_REF] Ales | An extended edge-representative formulation for the kpartitioning problem[END_REF]. It is well known that exact approaches of any clustering problem do not scale much due to its NP-hard nature. Moreover, the process can be very time-consuming even for medium-sized networks (e.g. 100 nodes). One way to deal with this issue is to strengthen the underlying MIP model through the cutting plane approach with the following valid inequalities whose efficiency is empirically proved by Ales et al. [START_REF] Ales | Polyhedral combinatorics of the k-partitioning problem with representative variables[END_REF] for another graph clustering problem : The 2-partition and the 2-chorded cycle inequalities.

Performing the Clustering

At this stage, we have identified the pattern associated with each roll-call. We now want to gather similar patterns together. For this purpose, we use a classic cluster analysis approach.

We first compute a similarity value based on the Purity [START_REF] Manning | Introduction to Information Retrieval[END_REF] for each pair of patterns. We then build a dissimilarity matrix summarizing these comparisons. Next, we apply the k-medoids clustering method to the previously obtained similarity matrix [START_REF] Kaufman | Partitioning around medoids[END_REF]. It is similar to the well-known k-means algorithm in the sense that it tries to partition the dataset in k clusters, while minimizing the distance between the members of each cluster and some center of the cluster. The difference is that in k-means, this center is an average value, whereas in k-medoids it is one of the actual data points from the dataset. It is generally used in place of k-means when one cannot perform the required average operation, which is true in our case (we cannot straightforwardly process an average pattern).

Computing the Characteristic Patterns

We now have k clusters, each one containing a certain number of patterns. The patterns constituting a cluster may differ slightly, but overall they are supposed to be very similar. The next step is to compute a characteristic pattern representing the whole cluster, such that these small differences are smoothed.

For this purpose, we use a similarity network-based approach, inspired by the work of Lancichinetti & Fortunato [START_REF] Lancichinetti | Consensus clustering in complex networks[END_REF]. Based on a collection of n partitions of the same set, we derive a consensual partition by first extracting a weighted signed similarity network, and then applying Ex-CC to this network, in order to identify a partition corresponding to the characteristic pattern of the cluster. The network is built as follows : each node represents a MEP, and the weight of the link connecting two MEPs is the difference between the proportion of patterns putting both MEPs in the same faction, and the proportion of patterns putting them in different ones.

Like any pattern, a characteristic pattern can take one of three forms : a single faction in case of unanimity, 2 antagonistic factions if some MEPs agreed on the concerned roll-calls whereas others opposed them, and 3 in case of an additional faction of abstentionists.

Results

As mentioned in the introduction, our goal is to compare our proposed method with the standard approach traditionally used when studying vote networks. For this purpose, we analyze the same data as Arinik et al. [START_REF] Arinik | Signed graph analysis for the interpretation of voting behavior[END_REF], and more particularly the votes of French and Italian MEPs related to agricultural questions during the 2012-13 legislative year. We expect our method to be able to answer some of the questions left open by their analysis. We take their discussion as a reference when commenting our own results, highlighting both differences and similarities between these approaches. Our source code is publicly available 1 .

Conventions and General Remarks

To denote the clusters, we use a notation indicating first the concerned country (F r for France), then the value of k used when detecting the considered clustering through k-medoids, and finally the number of the cluster in this clustering. For instance : F r-k3-clu2 is the name of the second cluster of the clustering obtained with k = 3 for the French MEPs.

We represent all networks and voting patterns using a circular layout (Figures 2) generated through Circos 2 . We describe them generically here, for matters of convenience. They shall be read from the center to the periphery. The negative and positive links are drawn at the center, in red and green, respectively. Next, the inner colored ring represents the nodes (MEPs), and these colors correspond to the factions constituting the detected pattern (i.e. partition of the MEPs). If a MEP was often absent, he is ignored and appears in white. The names of the MEPs are not included due to lack of space. Finally, the outer ring shows the European political groups to which the MEPs belong. They are ordered according to the political spectrum, from left to right : GUE-NGL (red), G-EFA (green), S&D (pink), ALDE (orange), EPP (light blue), ECR (dark blue), EFD (purple) and NI (brown).

Baseline

Arinik et al. [START_REF] Arinik | Signed graph analysis for the interpretation of voting behavior[END_REF] have applied a classic method, and extracted a vote similarity network by integrating their data over the whole considered legislative year (2012-13). Moreover, they have filtered the weakest links to sparsify the network. Figure 2a and Figure 2d show the best partition that Arinik et al. obtained by solving the CC problem, and a variant called RCC problem, respectively. They state that the network is highly polarized, as it contains many negative links and results in good partitions in terms of structural balance. They identify two antagonistic factions respectively led by the environmentalists (G-EFA) and the right conservatives (EPP), joined by some other groups or individual MEPs. The position of S&D and ALDE is interesting, because they belong to the right-wing faction according to CC, whereas they hold an intermediate position with RCC. Arinik et al. were not able to give a solid explanation for this. But they assumed that these groups were sometimes voting like the left-wing faction, and sometimes like the right-wing one.

Characteristic Patterns

As mentioned in Section 3.3, k-medoids requires us to specify the number of clusters. In theory, there exist several internal criteria to do it automatically. However, in practice, one possibly has to consider other factors to make a choice. Therefore, we identify k = 5 as our best trade-off (which is also consistent with the internal criteria), and discuss each cluster obtained for k = 5 and its corresponding pattern in the following.

Unanimity

Cluster F r-k5-clu1 corresponds to a unanimity situation, so for space considerations is not included in Figure 2. Indeed, it contains a single faction, and only one negative link, between P. Le Hyaric (GUE-NGL) and M. Le Pen (NI). The emergence of such a high level of agreement was completely hidden when considering only a temporal integrated network (i.e. averaged over the series of roll-calls), and therefore could not be detected by Arinik et al. It is the largest cluster with 100/232 roll-calls (43%), so we can assume it represents the regular voting behavior in the considered context. All the other clusters correspond to patterns containing varying antagonistic factions. This is consistent with the fact that our clusters are supposed to correspond, by construction, to distinct voting patterns.

Conservatives vs. All

The characteristic pattern associated with F r-k5-clu2, shown in Figure 2b, finds the rightwing conservative group (EPP) opposing the rest of the MEPs, while both Euroskeptic groups (EFD and NI) abstain. This cluster contains 34/232 (15%) roll-calls. An examination of the content of the corresponding legislative documents voted through those roll-calls reveals that this voting behavior corresponds to EPP trying to block radical changes related to the CAP. These changes, as well as their blocking by the right-wing conservatives, are confirmed in a positioning paper published by S&D about the 2013 CAP reform [START_REF] S&d) | CAP Reform -a good deal despite resistance from some Governments[END_REF].

Environmentalists vs. All

Cluster F r-k5-clu3, shown in Figure 2c, contains 74/232 roll-calls (32%). Its characteristic pattern finds the environmentalist group (G-EFA) opposing a large faction constituted of the rest. The far-left group (GUE-NGL) is apart, as one MEP agrees with the environmentalists whereas the rest of his group abstains. This is very similar to the pattern obtained by Arinik et al. when solving CC on their integrated network, except for the NI group and a few MEPs. In particular, Corinne Lepage, which was described by Arinik et al. as an environmentalist member of ALDE, is placed in the G-EFA faction by our method. The relevance of this faction is confirmed by her activity at the EP, where she is very active on issues such as food safety.

G U E -N G L G -E F A S & D ALDE EP P E F D N I C. Lepage (a) CC (Arinik et al.) G U E -N G L G -E F A S & D ALDE EP P E F D N I (b) F r-k5-clu2 G U E -N G L G -E F A S & D ALDE EP P E F D N I C. Lepage (c) F r-k5-clu3 G U E -N G L G -E F A S &

S&D/EPP vs. the Rest

Cluster F r-k5-clu4, shown in Figure 2e, represents 18/232 (8%) roll-calls. Its characteristic pattern contains a faction formed by the far-left, environmentalist and liberal groups (GUE-NGL, G-EFA, ALDE), vs. another faction containing the socialists and conservatives (S&D, EPP), while both Euroskeptical groups form an abstentionist faction. This constitutes a new type of pattern, different from all the others met until now, including in the baseline. In particular, it is is worth noticing that S&D and ALDE do not belong to the same faction. Thus, if these groups alternatively side with left-and right-wing groups, as already assumed by Arinik et al., our method shows that they do not always do so simultaneously.

Unholy Alliance

For F r-k5-clu5, as illustrated in Figure 2f, the characteristic pattern finds a faction gathering environmentalists and right-wing liberals and conservatives (G-EFA, ALDE, EPP), opposing a faction composed of the far-left and socialist groups (GUE-NGL and S&D), while the Euroskeptics abstain once again. These factions are surprising from a political standpoint, as they exhibit a somewhat unholy alliance between environmentalists and conservatives, whose views generally clash for AGRI matters. But the pattern is also surprising when considering Arinik et al.'s results, as they do not detect this alliance at all. The cluster contains only 6 roll-calls (2%), which shows that this situation does not happen often. A careful examination of the texts voted at these roll-calls reveals that the interests of these two groups happen to match, very punctually, and for completely different reasons.

Comparison with the Baseline

Our results confirm in a more objective way the assumption of Arinik et al., based on the RCC pattern from Figure 2, and according to which S&D and ALDE sometimes vote like the left-wing groups (as in F r-k5-clu2) and sometimes like the right-wing ones (F r-k5-clu3). Our method additionally identifies the context (i.e. roll-calls) for which the EP adopts these two patterns. But our method also shows that these two groups vote differently on a number of occasions (F r-k5-clu4 and F r-k5-clu5), a fact overlooked when using the traditional approach.

In addition, our results uncover the fact that the Euroskeptics systematically abstain on most roll-calls, and only vote for a specific subset corresponding to the Green vs. All pattern. This specific behavior put them apart from the rest of the groups, and maybe this is why they had been categorized by Arinik et al. as an intermediate group, like S&D and ALDE. However, our results show that this is an artifact of the Euroskeptics' abstentionist behavior, and that they hold a completely different position than S&D and ALDE.

Finally, our method allows identifying the Unholy Alliance pattern, which had completely been overlooked by Arinik et al. It corresponds to a very surprising coalition, politically speaking, which emerged when voting for a very specific set of roll-calls.

Conclusion

In this work, we introduce a method to the partition of multiplex signed networks. We show the interest of our approach by applying it to a subset of the 7 th term European Parliament dataset presented by Arinik et al for France and Italy. By comparison to existing approaches, our method has the following advantages. First, it undergoes much less of the information loss appearing when integrating the raw voting data to extract the voting similarity networks, since it treats separately each roll-call vote in the partitioning process. Second, in addition to antagonistic groups of voters, it allows identifying sets of legislative propositions causing the same polarization among these groups. This additional information can be leveraged by the end-user to better explain the observed outcomes. Third, unlike other methods, it does not require to filter out (quasi-)unanimous propositions, or to discard week links appearing in the model for interpretation or computational purposes. Fourth, it explicitly represents abstention in each roll-call vote layer, which allows detecting relevant groups of abstentionists.

Our method is generic and can be applied to any system with similar properties. For example, in the context of document/artwork classification, the opinion expressed by a selection of specialists can produce a set of polarizations, each one representing a variety of opinions regarding an item [START_REF] Bansal | Correlation clustering[END_REF]. Our method could allow identifying clusters of items leading to similar expert polarization. It can also be used to group specialists sharing the same point of view on certain issues. In the near future, we will apply our method more systematically to the whole EP dataset. Also, we will perform a textual content analysis of the voted documents, in order to provide the information required to properly interpret the identified characteristic voting patterns.

1

 1 Roll-calls 1,5,6, .. Roll-calls 2,4,8, .. Roll-calls 3,7,9, ..

FIG. 1 -

 1 FIG.1-General workflow of the proposed analysis method.

FIG. 2 -

 2 FIG. 2 -Voting behavior patterns of the French MEPs on AGRI questions in 2012-13. Red and green lines at the center represent negative and positive links, respectively. Around the links, each MEP is represented by a colored tile, whose color corresponds to the MEP's faction in the displayed pattern. The green factions in plots (b), (c), (e) and (f) correspond to abstentionists. The outer ring represents the political groups at the EP. The left plots show the patterns obtained by Arinik et al. [3] on the temporal integrated network when solving (a) CC and (d) RCC. The right plots show the second to fifth clusters obtained with our proposed method for k = 5 : (b) F r-k5-clu2 (%15 of roll-calls), (c) F r-k5-clu3 (%32 of roll-calls), (e) F r-k5-clu4 (%8 of roll-calls), and (f) F r-k5-clu2 (%3 of roll-calls). The first cluster, F r-k5-clu1, corresponding to a unanimity situation, is not included to lack of space.


ANALYSIS OF ROLL-CALLS IN THE EUROPEAN PARLIAMENT BY MULTIPLE PARTITIONING OF MULTIPLEX SIGNED NETWORKS

NEJAT ARINIK, ROSA FIGUEIREDO, AND VINCENT LABATUT

In a signed graph, each link is associated to a sign, which can be either positive (+) or negative (-). This type of graph can be used to model any system containing two types of antithetical relationships (like/dislike, for/against, similar/different...). A signed graph is considered structurally balanced if it can be partitioned into two [START_REF] Cartwright | Structural balance: A generalization of heider's theory[END_REF] or more [START_REF] Davis | Clustering and structural balance in graphs[END_REF] clusters, such that positive links are located inside the clusters, and negatives ones are in-between them. However, it is very rare for a real-world network to have a perfectly balanced structure: the question is how to quantify its imbalance. Various measures have been defined for this purpose, the simplest consisting in counting the numbers of misplaced links, i.e. positive ones located inside the groups, and negative ones located between them [START_REF] Cartwright | Structural balance: A generalization of heider's theory[END_REF]. Such measures are expressed relatively to a graph partition, so processing the graph balance amounts to identifying the partition corresponding to the lowest imbalance measure. In other words, calculating the graph balance can be formulated as an optimization problem.

Our goal is to use this paradigm to study the roll-call voting activity of the Members of the European Parliament (MEPs). We want not only to detect groups of MEPs which would be cohesive in terms of votes, but also to identify the different characteristic polarizations of the European Parliament (EP), i.e. the characteristic ways in which the MEP set is partitioned by these votes. The standard approach to study this type of system is to extract a vote similarity network, in which nodes represent MEPs and weighted (possibly signed) links represent the similarity between two MEPs, averaged over the series of roll-calls (e.g. [START_REF] Waugh | Party polarization in congress: A network science approach[END_REF][START_REF] Traag | Significant scales in community structure[END_REF]). However, this averaging leads to some information loss due to the temporal integration performed on the raw data [START_REF] Arinik | Signed graph analysis for the interpretation of voting behavior[END_REF].

In this work, we propose to adopt an approach based on a multiplex signed vote similarity network, in which each layer models a single roll-call as a signed unweighted graph. The literature contains 3 main approaches to partition multiplex graphs in general: 1) merge the Laboratoire Informatique d'Avignon LIA EA 4128, Avignon France E-mail addresses: {nejat.arinik, rosa.figueiredo, vincent.labatut}@univ-avignon.fr . layers and apply a traditional partitioning method to the resulting aggregated graph; 2) apply a traditional method separately to each layer and merge the resulting partitions; and 3) use a method specifically designed for multilayer graphs, which partitions the set of all nodes (over all layers). All 3 approaches are based on the assumption that one is looking for a single partition.

However, this single-partition assumption is not compatible with all our objectives. Indeed, we look for the different characteristic polarizations of the EP, so we want our method to be able to identify several partitions. To this aim, we propose a new partitioning process for multiplex signed graphs, which is three-stepped. First, we separately partition each layer, through a standard signed graph partitioning method. Second, we compute the similarity between all pairs of the resulting partitions, and perform a standard cluster analysis in order to identify clusters of similar partitions. Third, we process a characteristic partition for each cluster by solving a signed graph optimization problem.

We show the interest of our approach by applying it to a subset of the 7 th term European Parliament dataset presented in our previous work [START_REF] Arinik | Signed graph analysis for the interpretation of voting behavior[END_REF] for France and Italy. It allows identifying groups of cohesive voters, but also their different characteristic voting polarizations, as well as the legislative propositions to which they apply. There is a limited number of voting polarizations for a given roll-call: either unanimity (all MEPs vote similarly) or antagonism (two opposed groups), with the possibility of an additional abstention group. Based on our results, we show that antagonistic situations are not stable and depend on the topic at hand. We also uncovered some points overlooked by [START_REF] Arinik | Signed graph analysis for the interpretation of voting behavior[END_REF]. For instance, it is noticeable that the presence of a relatively significant French G-EFA group (environmentalists) causes a strong polarization when voting agriculture-related documents including environmental aspects, whereas this is not the case for Italy, due to the complete absence of any G-EFA MEPs. However, we find that the apparent unanimity observed in the previous case is not always true, and that a strong polarization appears for a certain small subset of rollcalls. We also identify roll-calls or subtopics treated differently by the French and Italian MEPs. For instance, general questions related to the Agricultural Structural Fund generally lead to unanimous votes for both countries, whereas all texts related to the Processing and Marketing of Agricultural Products are treated unanimously by Italian MEPs, but not by French MEPs.

By comparison to existing approaches, our method has the following advantages. First, it undergoes much less of the information loss appearing when integrating the raw voting data to extract the voting similarity networks, since it treats separately each roll-call vote in the partitioning process. Second, in addition to antagonistic groups of voters, it allows identifying sets of legislative propositions causing the same polarization among these groups. This additional information can be leveraged by the end-user to better explain the observed outcomes. Third, unlike other methods, it does not require to filter out (quasi-)unanimous propositions, or to discard week links appearing in the model for interpretation or computational purposes. Fourth, it explicitly represents abstention in each roll-call vote layer, which allows detecting relevant groups of abstentionists.

Our method is generic and can be applied to any system with similar properties. For example, in the context of document/artwork classification, the opinion expressed by a selection of specialists can produce a set of polarizations, each one representing a variety of opinions regarding an item [START_REF] Bansal | Correlation clustering[END_REF]. Our method could allow identifying clusters of items leading to similar expert polarization. It can also be used to group specialists sharing the same point of view on certain issues. In the near future, we will apply our method more systematically to the whole EP dataset. Also, we will perform a textual content analysis of the voted documents, in order to provide the information required to properly interpret the identified characteristic polarizations.