Amit Parag
email: aparag@laas.fr

Vaishak Belle
email: vaishak@ed.ac.uk

Tractable Generative Modelling of Cosmological Numerical Simulations

Keywords: Tractable Generative Modelling of Cosmological Numerical Simulations Probabilistic Modelling, Cosmological Simulations, Dark Matter, Tractable Graphical Model

whether they are published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Probabilistic representations, such as Bayesian and Markov networks, are fundamental to statistical machine learning. The attractiveness of such networks is that they can express probabilistic dependencies in a compact manner. However, owing to the intractability of inference, learning also becomes challenging, since learning typically uses inference as a subroutine [START_REF] Koller | Probabilistic graphical models: principles and techniques[END_REF], and moreover, even if such a representation is learned, prediction will suffer because inference has to be approximated. Tractable learning is a powerful new paradigm that attempts to learn representations that support efficient probabilistic querying. Much of the initial work focused on low tree-width models, [START_REF] Bach | Kernel independent component analysis[END_REF], but later, building on properties such as local structure [START_REF] Chavira | On probabilistic inference by weighted model counting[END_REF], numerous proposals based on arithmetic circuits (ACs) emerged. These circuit learners can also represent high tree-width models and enable exact inference for a range of queries in time polynomial in the circuit size. Sum-product networks (SPNs) [START_REF] Poon | Sum-product networks: A new deep architecture[END_REF], for example, are instances of ACs with an elegant recursive structure; essentially, an SPN is a weighted sum of products of SPNs, and the base case is a leaf node denoting a tractable probability distribution (e.g., a univariate Bernoulli distribution). In so much as deep learning models can be understood as graphical models with multiple hidden variables, SPNs can be seen as a tractable deep architecture. Of course, learning the architecture of standard deep models is very challenging [START_REF] Bengio | Learning deep architectures for ai[END_REF], and in contrast, SPNs, by their very design, offer a reliable structure learning paradigm. While it is possible to specify SPNs by hand, weight learning is additionally required to obtain a probability distribution, but also the specification of SPNs has to obey conditions of completeness and decomposability, all of which makes structure learning an obvious choice. Since SPNs were introduced, a number of structure learning frameworks have been developed for those and related data structures, e.g., [START_REF] Gens | Learning the structure of sum-product networks[END_REF][START_REF] Hsu | Online structure learning for sum-product networks with gaussian leaves[END_REF][START_REF] Liang | Learning the structure of probabilistic sentential decision diagrams[END_REF]. (Note that these related structures are not necessarily equivalent in terms of its features and properties; see works such as [START_REF] Liang | Learning the structure of probabilistic sentential decision diagrams[END_REF] for discussions. We will focus on SPNs here owing to their simple specification for generative modelling.)

In this work, we study how SPNs can be used to model a novel and challenging problem related to the evolution of galaxies; in particular, we consider the concordance cosmology in the backdrop of hydrodynamical simulations. In essence, in cosmology, there is no scope of actual experiments and therefore, the need to simulate universes to test various cosmological parameters, galactic properties and theories of universes require computationally efficient methods. One of the most effective tools to study astrophysical phenomena are numerical simulations. This is primarily due to the inability to arrive at analytic solutions for gravitationally interacting particles which immediately leads to an investigation of the computational methods. The mutual gravitational interactions between large sets of particles forms the basis of all simulations. This is easy to see: in simulations, dark matter is modelled as particles that can only interact with each other through gravity and since all matter must form in wells of dark matter, n-body simulations of billions of particles are of paramount importance. When juxtaposed with suitable numerical techniques that permit a realistic treatment of baryonic physics, this allows numerical simulations to be used as a tool for validating cosmological models and provide a general picture of structure formation in the universe.

Numerical simulations attempt to describe the cosmological picture by painting galaxies inside dark matter halos. This task, however, is extremely difficult: first, it involves making certain assumptions which cannot be substantiated, [START_REF] Somerville | Physical models of galaxy formation in a cosmological framework[END_REF] and second, the computation process is prohibitively expensive as indicated by the millions of hours of computation times on CPU for simulations such as the Eagle simulations or the Illustris simulations [START_REF] Schaye | The eagle project: simulating the evolution and assembly of galaxies and their environments[END_REF][START_REF] Llinares | The shrinking domain framework i: a new, faster, more efficient approach to cosmological simulations[END_REF]. Various algorithms have been proposed to reduce the exorbitant computations time and increase the accuracy of the process [START_REF] Llinares | The shrinking domain framework i: a new, faster, more efficient approach to cosmological simulations[END_REF][START_REF] Gheller | Numerical cosmology on the gpu with enzo and ramses[END_REF]. Scalable machine learning architectures are used in a variety of particle physics and cosmology experiments but their use has been restricted to particle tracing and classification [START_REF] Guest | Deep learning and its application to lhc physics[END_REF]. We believe the role of machine learning can be enhanced extensively in cosmological settings, and in this work, we take first steps towards that goal. In particular, given the recent advances in tractable probabilistic models, we study the question of how those advances could be leveraged in service of yielding a generative model. Thus, we reiterate that the thrust of this paper is purely on the applicability of tractable learning for the identified cosmological domain, and not about extending existing algorithms. As we demonstrate below, this requires a non-trivial understanding of the mathematical concepts surrounding concordance cosmology, and raises considerable challenges in feature selection and engineering. In the long term, we hope our results here will lead to more interdisciplinary research, and enable machine learning and probabilistic logical learning to tackle the deep, existing problems in cosmology.

Problem Statement

In this section, we will formulate the problem statement, first by giving a fairly informal picture of the cosmological model, before turning to the equations driving the computational task. (As we expect both physicists and machine learning practitioners to be readers of the article, our exposition will generally follow the style of introducing the overall background at an intuitive level, but then describing the core concepts using mathematical notation.)

Preliminaries. Of the many pictures that can be painted about origins of universe, the widely celebrated one is the Big Bang theory. The universe began with a bang, a hot big bang, so much so that the temperatures of the particles within 10 -33 s of Big Bang far surpasses the particles produced in current high energy physics experiments. Inflation soon took over and morphed space by a factor of 10 26 over time of the order 10 -32 s and so began epochs where the finest grains of the universe combined, decoupled and synthesized to establish the order that was to follow. The order that followed is usually described by one particular parametrization of the Big Bang theory, the ΛCDM model.

Concordance Cosmology.

The concordance cosmological model is the ΛCDM model of the universe, founded on the Copernican principles of isotropy and homogeneity [START_REF] Ryden | Introduction to cosmology[END_REF]. To build the concordance model of the universe, we start by assuming that observers in any location in the universe can never be the principle observers of the universe. This simple assumption immediately leads to the proposition that the universe is isotropic and homogeneous.

However a few things need to be kept in mind. Any theory is only as good as the initial assumptions made to form that theory. The properties of isotropicity and homogeneity are only apparent on the largest scales of the universe. As an example, consider the solar system. If we imagine a sphere engulfing the solar system, then the criteria of isotropicity and homogeneity are not met. The sun is located in a specific point in the sphere and on observing the sphere of solar system, we can immediately conclude that the sphere is not homogeneous. Planets in solar system are not alike and the sun outshines them all. Similarly, if we take into account the local group of galaxies -Andromeda, Milky Way, Large and Small Magellanic Clouds with the remaining fifty dwarf satellite galaxies -we observe that Andromeda and Milky Way are the two most pronounced galaxies in terms of mass, luminosity and size while the remaining can be classified as dwarf satellites. Only at largest scales of multiple superclusters of galaxies when differences between baryonic features like star formation rate, size, luminosity can be smoothed over, we assume the Copernican principle to hold.

Under the assumptions of isotropy and homogeneity, the currently accepted cosmological model describes a universe with rotational and translational symmetry, where the matter content is dominated by dark matter. In the energy context of the universe, dark energy accounts for the overwhelming majority of the energy in the universe while dark matter plays the second fiddle. Baryonic content, out of which structures like galaxies form, accounts for a very small portion of the universe. While the nature and the physical properties of dark energy and dark matter are not fully established, the prevalent theory of cosmological structure formation assumes that the central aspect of galaxy formation is the hierarchical assembly of dark matter halos with the properties of dark energy being not necessarily germane to galaxy formation [START_REF] Salcido | The impact of dark energy on galaxy formation. what does the future of our universe hold[END_REF]. This is the ΛCDM cosmological model [START_REF] Bertschinger | Cosmic structure formation[END_REF] of the universe where the curvature of spacetime is described by the Robertson-Walker metric. If we further hypothesize that the universe is filled with perfect fluid, then the evolution of the universe follows the Friedmann equations as outlined in [START_REF] Mörtsell | Cosmological histories from the friedmann equation: The universe as a particle[END_REF]:

ȧ a 2 = 8πG 3c 2 ε + Λ 3 - κc 2 a 2 R 2 (1) ä a = - 4πG 3c 2 (ε + 3P) + Λ 3 . ( 2
)
where G is the universal gravitational constant, c is the speed of light, ε and P are the energy density and pressure of the mass-energy in the universe. The scale factor a(t) models an expanding universe. Conventionally, a(t 0 ) = 1 where t 0 is present day. Λ represents the cosmological constant.

The concordance cosmology states that the present day large scale structure of baryonic matter can be traced back to its seeds embedded within dark matter halos in a very young universe, with the morphology of a galaxy, at any point in cosmic time, predominantly dependent on the properties of the surrounding halo, merger history of that galaxy and feedback effects. As is evident from Figures 1 and2, galaxies rarely evolve or are found in complete seclusion, but a necessary condition for formation of galaxies is the presence of a dark matter halo. Each dark matter halo typically contains a few subhalos inside which baryonic matter collapses to form galaxies. The most massive subhalo lies at the center of potential of the halo and contains the central galaxy of the halo. Therefore, modeling the universe for a better understanding is essentially painting a temporal picture of the cosmic web. 2: Dependence of baryonic features on dark matter. In fact, as we can see, the baryonic features of a galaxy are indeed dependent on the dark matter features of the galaxy. We provide a concise description of the features in Table 1 and present a more detailed analysis of the features in §4.2

There are broadly two flavors of simulations that model matter distribution in the universe [START_REF] Dolag | Simulation techniques for cosmological simulations[END_REF]: semi-analytic simulations and hydrodynamical simulations. There is, however, no reason for supposing the superiority of hydrodynamics over semi-analytic modeling. The predictive power of both of these approaches is in agreement with actual observations. We refer the reader to [START_REF] Benson | A comparison of semi-analytic and smoothed particle hydrodynamics galaxy formation[END_REF] for a comparison between semi-analytic methods and hydrodynamical modelling. In particular, physical processes critical to galaxy formation and evolution such as core collapse supernovae, accretion shocks, stellar winds, involve multiple sets of partial differential equations [START_REF] Somerville | Physical models of galaxy formation in a cosmological framework[END_REF] such that modeling structure formation through either approach becomes extremely difficult. The already intractable complexity of this problem is further compounded by the addition of approximations of physical phenomena which cannot be derived ab initio. Related Work. Using machine learning algorithms to model structure formation has inevitably resulted in a difference of efficacy. Algorithms like k-nearest neighbors and support vector machines used in [START_REF] Xu | A first look at creating mock catalogs with machine learning techniques[END_REF] have conclusively shown that machine learning galaxy-halo relation is not unsuccessful. The work was further extended in [START_REF] Kamdar | Machine learning and cosmological simulations[END_REF], [START_REF] Agarwal | Painting galaxies into dark matter haloes using machine learning[END_REF] and [START_REF] Cavuoti | Stellar formation rates in galaxies using machine learning models[END_REF] by including other discriminative or ensemble algorithms like decision trees and/or random forests. However, focusing on the algorithmic aspects of the task is equally important since the choice of algorithms usually involve some trade offs between scalability and accuracy while certain algorithms like decision trees are prone to overfitting. To our knowledge, tractable graphical models have never been applied to this problem. Our contribution in this paper is to apply a deep architecture with probabilistic semantics, sum product networks (SPNs) [START_REF] Poon | Sum-product networks: A new deep architecture[END_REF], to estimate a generative model for the data such that a mock catalog of galaxies can be build. The added advantage of using SPNs is that it guarantees that inference will always be in time linear in the size of the model [START_REF] Gens | Discriminative learning of sum-product networks[END_REF].

Method

Making machines learn to recognize halos and their corresponding baryonic content broadly involves two steps. The first step is finding features which are good representatives of a halo-galaxy system and indicate a strong correlation between the potential well of host dark matter halo and the galaxy inside it. This is usually followed up by providing a merger history of the galaxy-halo system to the machine. The choice of the depth of history to be provided is generally the prerogative of the machine learning practitioner. However, this choice comes with a few caveats. Since galaxy clusters generally formed in a very early universe, their merger histories usually cover billions of years and involve thousands of progenitors. Providing a description of all the progenitors of any galaxy is simply an impractical task. A good way to approach this choice is by constraining the number of progenitors of a galaxy (subhalo) and providing their corresponding properties only for a subset of the cosmic time. This is done keeping in mind that even though a subhalo may have thousands of progenitors and continuously morphs through multiple collisions and accretions, only a few of its progenitors play an overwhelming role in its overall shape and so only these few progenitors are sufficient to indicate the overall lineage of the subhalo. A partial merger history is choosing how far to travel along the main branch of a galaxy. As shown in Figure 3, the morphology of a galaxy at some redshift, is the result of evolution along many branches, but its protogalaxies along the main branch can adequately trace the history of a galaxy.

An alternate approach is to provide the algorithm with only a few random snapshots of the universe corresponding to different look-back times. In this approach, merger history need not be provided. The algorithm learns the underlying generative model which can be subsequently used to infer the morphology of galaxies at different redshifts. The motivation behind this is the drastic reduction in the dimensionality of the dataset. This then reduces the computation time.

In this paper, we find the set of progenitors of a galaxy along the main branch between redshift 0 and 0.5 sufficient for our purposes. We provide progenitor history in our first approach. In our second approach to model the relation between dark and baryonic matter, we do not provide progenitor history at all. The dataset construction is described in detail in §4.3. We compare and contrast the results of our approaches in §5.

The added advantage of using a graphical model is the greater interpretability. SPNs augment this by allowing probabilistic semantics even when there are no conditional dependencies present [START_REF] Butz | On learning the structure of sum-product networks[END_REF], while guaranteeing inference in time linear in tree width of the network. In the next section, we briefly review SPNs. We generate the dataset using the results of the Eagle suite of smoothed particle hydrodynamical simulations [START_REF] Schaye | The eagle project: simulating the evolution and assembly of galaxies and their environments[END_REF].

Tractable Probabilistic Graphical Models

Computing the modes and marginals of a probability distribution efficiently while learning the underlying distribution accurately is the main challenge of probabilistic modeling. This is more often than not done by exploiting the inherent relations present in the dataset to learn a joint distribution. However, inference remains the primary bottleneck in probabilistic modeling; in general, inference in Bayesian networks is intractable [START_REF] Darwiche | Complexity results and approximation strategies for map explanations[END_REF][START_REF] Chavira | On probabilistic inference by weighted model counting[END_REF].

Sum Product Networks

A graphical model represents a probability distribution over a d dimensional vector x, where x ∈ X, as a product of factors φ k such that P(X

= x) = 1 Z Π k φ k (x k )
, where Z is the partition function and φ k is a function over a subset x k : k = 1, 2, 3,. . . , d.

While the representation is expressive and compact, practical realizations of graphical models often fail to take advantage of their generative nature due to the computation cost of computing an intractable partition function, Z, which itself is made up of an exponential number of terms, Z = Σ x∈X Π k φ k (x k ). This immediately results in intractable inference queries.

Sum Product Networks ameliorate this problem by imposing certain restriction on the nodes in the graph. In its simplest description, SPNs are directed acylic graphs with alternate layers of sums and products. SPNs can be recursively defined as follows [START_REF] Poon | Sum-product networks: A new deep architecture[END_REF]:

• A (tractable) univariate distribution is an SPN • A product of SPNs over disjoint variables is a SPN
• A weighted sum of SPNs over the same set of variables is a SPN.

Formally: Let X = {X 1 , • • • X n } be a set of variables. A Sum-Product Network (SPN) defined over X is a rooted directed acyclic graph. The leaves are indicators [X p = •],
where the indicator function [.] has value 1 when its argument is true, 0 otherwise. The internal nodes are sum nodes and product nodes. Each edge (i, j) from sum node i has a non-negative weight w i j . The value of a sum node is j∈Ch(i) w i j v j , where Ch(i) is the children of i and v j is the value of its j th child. The value of a product node is the product of the values of its children. The value of an SPN is the value of its root.

We use S to denote an SPN as a function of the leaves. Let x be an instantiation of the indicator variables, that is, a full state. Let e be the evidence (partial instantiation). For a given node i, we use S i to denote the sub-SPN rooted at i. Also, we use x a p to mean [X p = a] is true, and use xa p to mean its negation. We are interested in learning SPNs with the following properties:

• Validity: A SPN is valid if and only if it always correctly computes the probability of evidence: S (e) = Φ S (e), where Φ S (e) is the unnormalized probability of e.

• Consistency: A SPN is consistent if and only if for every product node i, there is no variable X p that has indicator x a p as one leaf of the sub-SPN S i and indicator x b p with b a as another leaf.

• Completeness: A SPN is complete if and only if all children of the same sum node have the same scope. (The scope of an SPN is the set of variables in X that the indicators of an SPN are defined on)

• Decomposability: A SPN is decomposable if and only if the children of every product node have disjoint scopes.

To ensure the tractability at the root node, the descendant sum nodes are forced to have children nodes with identical scope, where the scope of a node is defined as the set of variables encoded in that node, while the descendant product nodes must have children with disjoint scopes. It is easy to see that a sum node is a symbolic mixture model made from the decomposable product nodes with leaf nodes at the bottom attached to univariate distributions. The parameters of the networks are the priors over the mixture components in the sum node. This allows the computation of the partition function to remain tractable, which in turn, allows exact inference.

Structure Learning

Typically, the network can be learned in two ways. The first method involves initializing a random SPN and then estimating the parameters (the weights) of the network from the data either discriminatively as shown in [START_REF] Gens | Discriminative learning of sum-product networks[END_REF], or generatively as described in [START_REF] Gens | Learning the structure of sum-product networks[END_REF]. For the former case, stochastic gradient descent is usually applied to estimate the parameters of the network. The pervasive gradient diffusion problem in layered networks [START_REF] Haykin | Neural networks and learning machines/Simon Haykin[END_REF] can be overcome by doing hard expectation-maximization (EM). For the generative case, expectation-maximization is generally employed to learn the weights. Once the weights have been learned, unnecessary edges and nodes can be pruned away.

The size, shape and the weights of the network can also be learned from the data itself. To build a valid SPN such that the conditions of decomposability and completeness are satisfied, instances and variables are recursively split and partitioned. Sum nodes are assigned to the clusters of instances using any of the cluster estimation algorithms, whereas independence tests are usually employed to partition variables and assign them to product nodes. Leaf nodes are assigned to univariate distributions. We learn generatively with the leaf nodes of our SPN explicitly encoded to contain univariate Bernoulli distributions. This is however not a strict requirement: as shown in works such as [START_REF] Molina | Poisson sum-product networks: A deep architecture for tractable multivariate poisson distributions[END_REF][START_REF] Molina | Mixed sum-product networks: A deep architecture for hybrid domains[END_REF][START_REF] Rashwan | Online and distributed bayesian moment matching for parameter learning in sum-product networks[END_REF][START_REF] Hsu | Online structure learning for sum-product networks with gaussian leaves[END_REF][START_REF] Bueff | Tractable querying and learning in hybrid domains via sum-product networks[END_REF], SPNs can also be learned online with Gaussian, Poisson and other distributions.

Empirical Evaluations

Simulation overview

The suite of Eagle simulations [START_REF] Schaye | The eagle project: simulating the evolution and assembly of galaxies and their environments[END_REF] uses a modified version of Gadget3 hydrodynamical code, last described in [START_REF] Springel | The cosmological simulation code gadget-2[END_REF], to evolve resolution elements in boxes of size 12, 25, 50 and 100 comoving mega parsecs (cMpc) on a side. The cosmology employed in the simulations is consistent with the results of [START_REF] Planck | Planck 2013 results. xvi. cosmological parameters[END_REF], where Ω Λ = 0.693, Ω m = 0.307, Ω b = 0.04825, σ 8 = 0.8288, n s = 0.9611, h = 0.677, where, Ω Λ , Ω m , Ω b , σ 8 , n s , h stand for the contributions to matter/energy content of the universe from cosmological constant, matter, baryons respectively, h is the dimensionless Hubble parameter, n s is the spectral index of the primordial power spectrum while σ 8 is the rms amplitude of the linear mass fluctuations. High resolution simulations correspond to simulations with an initial baryonic particle mass of m g = 2.26 x 10 5 M while intermediate resolution simulations have a higher initial baryonic particle mass, m g = 1.81 * 10 6 M , where M is 1 solar mass.

The key run of the simulations, which we use in this paper, the Fiducial Ref-L0100N1504 simulation is an intermediate resolution simulation with periodic box with a volume of (100cMpc) 3 , initially containing 1504 3 gas particles, with an initial mass of 1.81 * 10 6 M and the same amount of dark matter particles with 9.70 * 10 6 M .

Substructures, like galaxies, in Eagle simulations were identified using the the standard SUBFIND algorithm (developed in [START_REF] Springel | Populating a cluster of galaxies-i. results at [formmu2] z= 0[END_REF]). Galaxies were defined as gravitationally bound subhalos and identified using three steps. First, halos were identified by running the Friends-of-Friends algorithm (FOF) [START_REF] More | The overdensity and masses of the friends-of-friends halos and universality of halo mass function[END_REF] on the dark matter particles with linking length 0.2 times the mean interparticle separation. Gas and star particles are assigned to the same, if any, halo as their nearest dark matter particles. Second, SUBFIND defines substructure candidates by identifying overdense regions within the halos bounded by saddle points in the density distribution. Finally, particles that are not gravitationally bound to the substructure are removed and the resulting substructures are referred to as galaxies.

The simulations themselves have a finite resolution and are generally not reliable on lower mass range of satellite galaxies and dwarf halos; the physics on lower scales is more influenced by feedback effects and stellar winds which are poorly understood and have no analytic solutions. The properties of low mass galaxies are not entirely reliable due to the finite resolution of the simulations. In general, many galaxy properties are unreliable below a stellar mass of 10 9 M . Due to this, we only select central galaxies with halo mass above 10 10 M . For a more comprehensive discussion on the parameters of the simulation, we refer the readers to [START_REF] Schaye | The eagle project: simulating the evolution and assembly of galaxies and their environments[END_REF].

Feature Engineering

Physical processes critical to galaxy formation and evolution such as core collapse supernovae, accretion shocks, stellar winds, involve multiple sets of partial differential equations [START_REF] Somerville | Physical models of galaxy formation in a cosmological framework[END_REF] such that modeling structure formation becomes extremely difficult. The already intractable complexity of this problem is further compounded by the addition of approximations of physical phenomena which cannot be derived ab initio. This is where the dependence between baryonic matter and dark matter can be exploited in a probabilistic machine learning setting to generate mock catalogs of galaxies. If baryonic matter and dark matter are modelled as random variables, then a joint distribution over these random variables can give a very good indication of the dynamical co-evolution of the universe. But this again is a complex task since the effectiveness of any machine learning algorithm dramatically increases with a good choice of features. This crucial aspect of probabilistic modeling plays a more pronounced role in rich, high dimensional datasets such as cosmological simulations since these simulations essentially take snapshots of the state of particles, the state of any particle itself is an aggregate of multiple non-linear couplings between various physical processes. The choice of features to make up the input space of machine learning algorithms rests solely on the domain knowledge. The domain here is the universe, a universe where majority of the energy content is completely dark and the properties of the overwhelming majority of matter is a mystery and the features of the remaining matter are only finitely resolvable.

To better illustrate the difficulty of the problem, let us consider a simple toy example: assume that a galaxy is a system with just four components: dark matter halo, stellar halo, central black hole and stellar bulge. Suppose we further fix the location of the central black hole of a galaxy as the starting point of a galaxy. In this simplistic scenario, the answer to the question: what is the size of a galaxy or equivalently, where does a galaxy end?, is reduced to heuristics. To answer this question, we normally assume that the galaxy with all its components are in a state of equilibrium. This leads to definition of a virialized state of that system such that the virial radius of the galaxy can act as a representative of the galaxy size. But, can virial radius, established under the assumptions of lack of perturbations, be a good indication of the size of a galaxy like Milky Way, which at the moment is undergoing tidal stress and is on a collision course with Andromeda Galaxy? It is obvious that making a generative model of dark and baryonic matter so as to understand the overall matter distribution in the universe and using it to learn the mapping between dark and baryonic matter is not a trivial task. To reiterate the point let us consider another example. If we take into account that star formation rate peaked at redshift 1∼2, see [START_REF] Madau | Cosmic star-formation history[END_REF] for stages of evolution in cosmology, while the first stars were born just 200 million years after the Big Bang, then an interesting formulation of the task is defining the word partial. If we are to predict the the baryonic content of a halo using at any redshift using the halo merger history, then modeling the dynamical evolution of the galaxy depends, in no small measure, on the kind of history provided.

Overall, the baryonic features we model as random variables are: mass of central super massive black hole, stellar mass, velocity dispersion and the maximum of circular velocity of the galaxy, which are described below, followed by a short description of dark matter features.

Black Hole Mass

The Eagle simulations implement a quasar mode active galactic nuclei feedback to model black hole with black hole seeds only planted in halos with masses more than 10 10 M h -1 , that do not already contain a black hole. The black hole grows through mergers and accretion.

Stellar Mass

The stellar mass of the central galaxies is chosen to be the mass contained within a 3 dimensional aperture centred on the minimum of potential of that galaxy. In this paper, we use stellar mass within an aperture of size 30 proper kiloparsecs to describe the stellar content of the galaxy. As shown in Figure 1, the galaxy stellar mass function produced in the simulations corresponds well with the observations from Galaxy And Mass Assembly [START_REF] Baldry | Galaxy and mass assembly (gama): the galaxy stellar mass function at z¡ 0.06[END_REF] and SDSS [START_REF] Li | Autocorrelations of stellar light and mass in the low-redshift universe[END_REF] surveys.

Velocity Dispersion

The Eagle simulations model the velocity dispersion of the stars as √ 2E k /3M, where the kinetic energy, E k and mass M, is calculated for all the stars within a spherical 30 physical kiloparsecs aperture centered on the galaxy's center of potential.

Maximum of Circular Velocity

The maximum value of the circular velocity (hereafter Vmax) is derived through v c (r) ≡ G N M(<r) r , where M(< r) is the mass enclosed within a sphere of radius r.

Mass Critical 200

The halo mass, M 200 , is defined as the total mass contained within the virial radius R 200 ,

Radius Critical 200

The corresponding radius term for Mass Critical 200 is Radius Critical 200 (R 200 ). Formally, it is the physical radius within which the mean density is 200 times the critical density of the universe.

Halo Group Mass

The halo features, Radius Critical 200 (R 200 ) and Mass Critical 200 (M 200 ), we use were derived by placing a sphere at the minimum of gravitational potential centered on the central galaxy. The halo group mass is the aggregate mass of all the dark matter subhalos within a group while the number of subhalos refers to the number of galaxies inside a halo. As previously noted in §4.1, the (sub)halos within a group were identified through SUBFIND and FOF algorithms. The halo group mass is the aggregate mass of all subhalos within any group.

Dataset Construction

Since our method involves two different approaches, we construct four datasets by querying both the fiducial and dark matter-only models in the database for the properties of sub-halos (galaxies) with their corresponding dark matter halos and halos only.

The first approach, where we provide a merger history, corresponds to Dataset 1 and Dataset 3.

With Dataset 1, we provide SPNs with a selection of properties of the central galaxy at zero redshift in each halo along with a description of their corresponding central subhalo merger history from redshift 0 to redshift 0.50. This is equivalent to providing the halo history for approximately the last 5 billion years. The merger tree was traversed only along the main branch, see Fig. 3, of every galaxy. [START_REF] Mcalpine | The eagle simulations of galaxy formation: Public release of halo and galaxy catalogues[END_REF]. As described before, a galaxy at the present time, is the result of mergers of multiple galaxies over the course of billions of years. Redshift 0 corresponds to the present day, while redshift 10 corresponds to a lookback time of 12 Gigayears. The merger history of a galaxy usually follows a main progenitor branch. The Eagle simulations model the merger history as shown in the figure, where the Descendant ID represent a galaxy at a specific point in time, while the TopLeafID represents the first progenitor of that galaxy along the main branch. The main progenitor branch is indicated with a thick black line, all other branches with a thin line. To get the merger history, we only traverse along the main progenitor branch.

The galactic properties we model are the mass of its central black hole, stellar mass, velocity dispersion of the stars and the maximum of the circular velocity rotation curve of the galaxy.

Dataset 3 was generated in a similar way through the Dark Matter-Only snapshots in the Eagle simulations. In Dataset 3, we only use halo properties and halo merger histories, from redshift 0 to redshift 0.50, as inputs and query for properties redshift 0. The common factors in Dataset 1 and Dataset 3 are the halo properties and merger histories.

Through the second approach, corresponding to Dataset 2 and Dataset 4 where halo history was not provided at all, SPN builds generative models of matter distribution out of snapshots.

Dataset 2 and Dataset 4 were generated again from the fiducial and the dark matter-only run. These datasets contain the same properties of galaxy-halo systems and only halos as in the first approach, but between redshifts 3.5 to 1.7 respectively. We chose this particular redshift range so that our dataset can better model the universe since the peak of star formation rate is generally supposed to have occurred within this regime [START_REF] Madau | Cosmic star-formation history[END_REF]. The generative model created by training the machine on the values between these particular redshifts were tested by querying for the values of the corresponding properties at redshift 0. We wanted to see how well the SPN picks up on the underlying matter distribution of the simulated universe, when given only the state of cosmic web at different redshifts. The ulterior motive for using the dark matter-only runs was to see how well the algorithm approximates the N-body calculations. The dark matter-only simulations use gravity as the governing law for evolution of billions of particles. Since there is no analytic solution for this case and convergence is usually established through the use of energy or momentum conservation laws, so we can, to some extent, see how well SPNs can approximate the convergence.

Analysis

In this section, we present and discuss the results that were obtained when we applied the algorithm to the Eagle data. Using the dark matter internal halo properties as our inputs, the following baryonic features were are predicted: black hole mass, stellar mass of the galaxies, velocity dispersion and Vmax. These attributes are the result of evolution over billions of years through dissipative, nonlinear baryonic processes. As discussed earlier, the overall picture of large scale structure formation is the ΛCDM model; but, on smaller scales, the details are incredibly rich and vastly more complicated.

In Fig 4 we first show the performance of SPNs in reproducing the simulated properties of the galaxies in Eagle and subsequently follow it up by discussing the implications of our results for the halo-galaxy connection. We use the following statistics to quantify the effectiveness of SPNs in predicting the galaxy properties.

• First, we use the standard mean squared error (MSE) metric, which is defined as:

MS E = 1 N test i=N test -1 i=1 X i test -X i predicted 2 (3)
Here, X i test is the i th value of the test set, X i predicted is the i th value of the predicted set and N test is the size of the test set.

• The Pearson correlation coefficient is perhaps the most widely used measure for linear relationships between two normal distributed variables and thus often just called "correlation coefficient". The Pearson correlation coefficient measures the linear relationship between two variables. Usually, the Pearson coefficient is obtained via a Least-Squares fit and a value of 1 represents a perfect positive relationship, -1 a perfect negative relationship, and 0 indicates the absence of a relationship between variables.

For two variables X and Y:

ρ = cov(X, Y) σ x σ y (4)
with cov(X, Y) as the covariance between X and Y and σ x and σ y the standard deviations of X and Y respectively.

The estimate:

r = n i=1 (x i -x)(y i -y) n i=1 (x i -x) 2 (y i -y) 2 (5)
where x i , y i , denote the i th element of the vector X and Y.

x, y are the respective means of X and Y.

• The Coefficient of Determination is defined as: Once the SPN has captured the joint distribution over all the variables in the dataset at its root node, it can be easily queried for conditional and marginal likelihoods for any random variable like stellar mass or mass of central black hole. The root node in SPN can also be sampled to generate synthetic datasets that follow the learned joint distribution.

R 2 = 1 - i (X i test -X i predicted ) 2 i (X i test -X mean,train ) 2 (6)
Tables 2 and3 clearly show that there is not much difference in the errors between the two approaches. The computation time taken to learn the joint distribution however, is much less when just snapshots are provided. So merger histories of halos do not really play much role in building richer models. Tables 4 and5 are analogous, but for dark matter properties only.

The results shown in Tables 2, 3, 4, 5 demonstrate that SPNs are able to recreate mock catalogs with properties strikingly similar to those produced by extensive hydrodynamic codes. The baryonic properties which are heavily A striking feature is the inability of progenitor history to increase the accuracy of the predictions, even at the cost of increased computation time. As we can see from Tables 2 and3, the mean squared errors for stellar mass of a galaxy when the progenitor history is provided is 0.019964, while the mean squared error when no progenitor history is provided is 0.019542. The contrast becomes more pronounced when we compare the computation time taken by our algorithm. For Dataset 1 and Dataset 2, the time taken for the same computation is 846 seconds and 144 seconds. This clearly shows that even though large scale structure can only grow hierarchically through mergers over cosmic time, progenitor history does not play any significant role in predictions.

The same is true for dark matter-only runs. Table 4 gives the result for dark matter-only simulation with progenitor history of halos provided to SPNs, while Table 5 delineates the result when halo history is not provided. As we can see in the mean squared errors for number of subhalos and halo group mass, there is not even an appreciable difference in errors, while learning the structure of SPN to model the joint distribution takes drastically more time with Dataset 3, relatively to the computation time taken by Dataset 4.

Overall, we get somewhat surprising results. Numerical simulations evolve many gaseous interactions on an ad hoc basis and the baryonic physics is vastly complicated. We did not really expect the algorithm to pick up so well on the galaxy halo relation. However it is important to note that our model is purely a phenomenological one. Unlike hydrodynamics, machine learning does not presume a relation between dark matter halos and the galaxies in it. This implies that machine learning can never be used as a replacement for numerical simulations, instead it can be used as a tool to study galaxy-halo connection and explore the influence of different simulation physics, like the one employed in semi-analytic modelling, to explore structure formation in the universe.

Conclusions

We performed an empirical study of the relation between dark matter halo and the corresponding galaxies it encloses through the use of a tractable probabilistic graphical model, sum product network, in the backdrop of one of the largest hydrodynamic simulations of cosmology.

The core underlying physics is the dependence of baryonic matter like stars and galaxies on dark matter. Dark matter itself cannot be seen by any form of instruments. We only infer the presence of dark matter. Dark matter itself must be modelled through simulations and the properties of dark matter must be defined through heuristics. This is where simulations are necessary to generate the dataset. Without the simulation, we will not have any dataset to begin with. But on the other hand, a full simulation will take hours to complete. To this end, we showed that given the data from a partial simulation, SPNs can provide a generative model for full simulation. So, one possible idea for future work is to let a simulation run for a small amount of time and then train SPNs to generate newer data.

The goal of this project was not to construct a numerically identical population of galaxies, but to explore how much information can be extracted from dark matter properties about the eventual evolutionary properties of galaxies. The conclusion seems to indicate that SPNs can clearly mimic the evolution of galaxies in a hydrodynamic setting. Furthermore, the runtime of SPN is of the order of minutes, in sharp contrast to millions of hours spend by numerical simulations. Challenges for the future include using more advanced algorithms to fully explore the extent to which machine learning can be assimilated in cosmology. Potential applications of such an extended framework include a new approach to obtaining a halo mass function, which can be directly tested against existing fitting formulae adopted by analytic approaches. A second interesting avenue is the use of machine learning to compare and contrast different cosmologies. If we train machines to learn galaxy-halo connection based on the concordance model, then the trained model can be tested to see how well it can explain baryonic features generated by other parametrizations of the Big Bang theory. A further ambitious project lies in using machine learning to constrain cosmological parameters using weak lensing data or deep sky surveys. In this regard, tractable probabilistic models such as probabilistic sentential decision diagrams (e.g [START_REF] Kisa | Probabilistic sentential decision diagrams[END_REF]) that permit the structure learning process to incorporate symbolic constraints may be particularly useful.

Figure 1 :

 1 Figure 1: The galaxy stellar mass function (GSMF). The evolution of the stellar mass density of the universe provides a good overview of the growth of stellar mass in the simulation. The GSMF can generally be described approximately by a Schechter function [37], i.e. a power law and an exponential break which starts at a characteristic mass. The figure describes the relation between galaxy stellar mass density and redshift based on data taken from Eagle simulations. The Eagle simulation is described in §4.1

Figure

  Figure2: Dependence of baryonic features on dark matter. In fact, as we can see, the baryonic features of a galaxy are indeed dependent on the dark matter features of the galaxy. We provide a concise description of the features in Table1and present a more detailed analysis of the features in §4.2

Figure 3 :

 3 Figure 3: Merger history of a galaxy with stellar mass, M star > 10 5 M . Figure taken from the Eagle Database[START_REF] Mcalpine | The eagle simulations of galaxy formation: Public release of halo and galaxy catalogues[END_REF]. As described before, a galaxy at the present time, is the result of mergers of multiple galaxies over the course of billions of years. Redshift 0 corresponds to the present day, while redshift 10 corresponds to a lookback time of 12 Gigayears. The merger history of a galaxy usually follows a main progenitor branch. The Eagle simulations model the merger history as shown in the figure, where the Descendant ID represent a galaxy at a specific point in time, while the TopLeafID represents the first progenitor of that galaxy along the main branch. The main progenitor branch is indicated with a thick black line, all other branches with a thin line. To get the merger history, we only traverse along the main progenitor branch.

Figure 4 :

 4 Figure 4: The structure of the SPN for Dataset 1. The SPN has 143 edges with 144 nodes in 20 layers. The network has 19 sum nodes, 40 product nodes and 85 leaf nodes. Each leaf node contains a univariate Bernoulli distribution. The single node at the top is the root sum node. The structure took 149 seconds to be learned

Table 1 :

 1 A concise description of the features of dark and baryonic matter.

	Dark Matter Features
	Feature	Description
	Halo Group Mass	Aggregate Group Mass of all subhalos within a
		larger halo
	Mass Critical 200, M 200	Defines the mass of a halo
	Radius Critical 200, R 200	The Radius that bounds Mass Critical 200
	Number of Subhalos	Representative of the number of smaller subhalos
		that make up a larger halo
	Baryonic Matter Features
	Feature	Description
	Black Hole Mass	The mass of the central black hole in a halo
	Stellar Mass	Representative of the stellar content of a galaxy
	Velocity Dispersion	Provides a measure of velocity of a galaxy
	Maximum of Circular Velocity, Vmax	Maxima of the circular velocity curve of a galaxy

Table 2 :

 2 Dataset 1: The structure of SPN for this dataset was learned in 847.6 seconds. Progenitor history was provided.

	Feature	MSE	R 2	Accuracy Score PearsonR
	Central Black Hole Mass 0.041714 0.464182	0.958286	0.743506
	Stellar Mass	0.019964 0.732150	0.980036	0.870518
	Velocity Dispersion	0.118812 0.464540	0.881188	0.727086
	Vmax	0.065533 0.680239	0.934467	0.837789

Table 3 :

 3 Dataset 2: The structure of SPN for this dataset was learned in 144.7 seconds. Only random snapshots were provided.

	Feature	MSE	R 2	Accuracy Score PearsonR
	Central Black Hole Mass 0.039717 0.469593	0.960283	0.735701
	Stellar Mass	0.019542 0.727792	0.980458	0.867607
	Velocity Dispersion	0.107178 0.512861	0.892822	0.751796
	Vmax	0.055159 0.728921	0.944841	0.863211

Table 4 :

 4 Dataset 3: The structure of SPN for this dataset was learned in 1890.15 seconds. Dark Matter Only run with halo history. are predicted extremely well. This is the direct consequence of gravity being the most dominant force at large scale. The mass of the central black hole and the stellar content of a galaxy, given by stellar mass, is linearly dependent on the mass of the halo, M 200 around it. Velocity Dispersion and Vmax are implicitly governed by kinetic and potential energies which are in turn, dependent on mass and radius. The predicted and true distributions are almost identical in the case of stellar mass and mass of central black hole.

	Feature	MSE	R 2	Accuracy Score PearsonR
	Number of Subhalos 0.053304 0.442150	0.946696	0.701084
	Halo group Mass	0.014672 0.799276	0.985328	0.905383
	M 200	0.005449 0.929433	0.994551	0.965560
	R 200	0.012702 0.938336	0.987298	0.969134

Table 5 :

 5 Dataset 4: The structure of SPN for this dataset was learned in 149.5 seconds. Dark Matter Only run with just snapshots.

	Feature	MSE	R 2	Accuracy Score PearsonR
	Number of Subhalos 0.051744 0.464274	0.948256	0.714493
	Halo group Mass	0.015195 0.793547	0.974805	0.914319
	M 200	0.004964 0.933783	0.994036	0.963175
	R 200	0.010756 0.947684	0.989244	0.973857


Yoann Dieudonné

Franck Petit

Deterministic Leader Election in Anonymous Sensor Networks Without Common Coordinated System

Keywords: Election de leader distribué, Sense d'orientation, Latéralité, Réseaux de capteurs

Dans ce papier, nous nous focalisons sur le problème qui consiste à élire un leader dans un réseau de n capteurs anonymes ne partageant aucun système commun de coordonnées. En supposant que lorsque les robots disposent de la propriété de latéralité, nous donnons une caractérisation complète sur les positions des capteurs permettant de distinguer un leader, et ce quelque soit n. Lorsqu'ils ne disposent pas de la propriété de latéralité, nous montrons que cette caractérisation reste vraie si et seulement si n est impair. Ces résultats sont vrais même si les capteurs possèdent une mémoire et une visibilité infinie, sont mobiles et peuvent communiquer entre eux.

Introduction

In distributed settings, many problems that are hard to solve otherwise become easier to solve with a leader to coordinate the system. Due to its importance, the problem of electing a leader is covered in depth in many books related to distributed systems, e.g., [San07]. The Leader Election (LE) Problem consists in moving the system from an initial configuration were all entities are in the same state into a final configuration were all entities are in the same state, except one, the leader.

In this paper, we address the leader election problem in sensor networks under very weak assumptions e.g., uniformity (or, homogeneity -all the sensors follow the same program -, anonymity -the sensors are a priori indistinguishable -, disorientation -the sensors share no kind of coordinate system nor common sense of direction nor unit measure. In weak distributed environments, many tasks have no solution. In particular, in uniform anonymous general networks, the impossibility of breaking a possibly symmetry in the initial configuration makes the leader election unsolvable deterministically [Ang80]. We come up with the following question : "Given a set of such weak sensors scattered on the plane, what are the (minimal) geometric conditions to be able to deterministically agree on a single sensor ?"

Preliminaries

In this section, we define the distributed system considered in this paper. Next, we review some formal definitions and basic results on words and Lyndon words.

Model

Consider a set of n sensors (or agents, robots) arbitrarily scattered on the plane such that no two sensors are located at the same position. The sensors are uniform and anonymous, i.e, they all execute the same program using no local parameter (such that an identity) allowing to differentiate any of them. However, we assume that each sensor is a computational unit having the ability to determine the positions of the n sensors within an infinite decimal precision. We assume no kind of communication medium. Each sensor has its own local x-y Cartesian coordinate system defined by two coordinate axes (x and y), together with their orientations, identified as the positive and negative sides of the axes.

In this paper, we discuss the influence of Sense of Direction and Chirality in a sensor network.

Definition 2.1 (Sense of Direction) A set of n sensors has sense of direction if the n sensors agree on a common direction of one axis (x or y) and its orientation. The sense of direction is said to be partial if the agreement relates to the direction only -i.e., they are not required to agree on the orientation.

In Figure 1, the sensors have sense of direction in the cases (a) and (b), whereas they have no sense of direction in the cases (c) and (d).

Given an x-y Cartesian coordinate system, the handedness is the way in which the orientation of the y axis (respectively, the x axis) is inferred according to the orientation of the x axis (resp., the y axis).

Definition 2.2 (Chirality)

A set of n sensors has chirality if the n sensors share the same handedness. In Figure 1, the sensors have chirality in the cases (a) and (c), whereas they have no chirality in the cases (b) and (d).

Lyndon Words

Let k and j be two positive integers. The k th power of a word w is the word denoted s k such that s 0 = ε, and s k = s k-1 s. A word u is said to be primitive if and only if u = v k ⇒ k = 1. Otherwise (u = v k and k > 1), u is said to be strictly periodic. The j th rotation of a word w, notation R j (w), is defined by : R j (w)

def = ε if w = ε a j , . . . , a l , a 1 , . . . , a j-1 otherwise (w = a 1 , . . . , a l , l ≥ 1) Note that R 1 (w) = w.
A word w is said to be minimal if and only if ∀ j ∈ 1, . . . , l, w R j (w).

Definition 2.3 (Lyndon Word)

A word w (|w| > 0) is a Lyndon word if and only if w is nonempty, primitive and minimal, i.e., w = ε and ∀ j ∈ 2, . . . , |w|, w ≺ R j (w).

Leader Election

The leader election problem considered in this paper is stated as follows : Given the positions of n sensors in the plane, the n sensors are able to deterministically agree on the same position L called the leader.

Leader Election with Chirality

In this subsection, we assume a sensor networks having the property of chirality. A configuration π of the sensor network is a set of positions p 1 , . . . , p n (n > 1) occupied by the sensors. Given a configuration π, SEC denotes the smallest enclosing circle of the positions in π. Note that SEC is unique and can be computed in linear time [Wel91]. The center of SEC is denoted O. SEC passes either through two of the positions that are on the same diameter (opposite positions), or through at least three of the postions in π. Note that if n = 2, then SEC passes both sensors and no sensor can be located inside SEC, in particular at O. Since the sensors have the ability of chirality, they are able to agree on a common orientation of SEC, denoted .

Given a smallest enclosing circle SEC, we can associate a word W (r) for each radius r with at least one robot on it and not at the center. Let R be the finite set of radii such that at least one sensor is located on r Deterministic Leader Election in Anonymous Sensor Networks Without Common Coordinated System but O. Let p 1 , . . . , p k be the respective positions of k robots (k ≥ 1) located on the same radius r ∈ R . Let w r be the word such that w r def = 0 if there exists one sensor at O a 1 , . . . , a k with a 1 = d(O, p 1 ) and ∀i ∈

[2, k], a i = d(p i-1 , p i ) , otherwise
Let r be a radius in R . The successor of r, denoted by Succ(r, ), is the next radius in R , according to . The i th successor of r, denoted by Succ i (r, ), is the radius such that Succ 0 (r, ) = r, and Succ i (r, ) = Succ(Succ i-1 (r, ), ). Given r and its successor r = Succ(r, ), (rOr ) denotes the angle between r and r . Given an orientation , let CW be the set of configuration words, computed by any sensor s, build over R such that for each radius r ∈ R , the associated configuration word W (r) is equal to (0, 0) if Let A CW be the set of letters over CW . Let (u, x) and (v, y) be any two letters in A CW . Define the order over A CW as follows : (u, x) (v, y) ⇔ (u v or (u = v and x < y)). The lexicographic order over CW is naturally built over .

w r = 0, otherwise W (r) is equal to the word a 1 , . . . , a k such that k = R and ∀i ∈ [1, k], a i = (Succ i-1 (r, ), (Succ i-1 (r, )OSucc i (r, ))).
Theorem 3.1 Given a configuration π of any number n ≥ 2 sensors with chirality scattered on the plane, the n sensors are able to deterministically agree on the same sensor L if and only if there exists a radius r ∈ R such that W (r) is a Lyndon Word.

Sketch of proof.

If there exists a radius r such that W (r) is a Lyndon Word then r is unique. So, the leader is the robot on r which is the nearest from the center of SEC. If there exists no radius r ∈ R such that W (r) is a Lyndon Word, then for each r, W (r) is strictly periodic. So, for each sensor there exists at least another sensor which can have the same view of the world (see Figure 3). In that case, we cannot determiniscally distinguish an unique sensor L. 2

Leader Election without Chirality

Without chirality, the sensors are not able to agree on a common orientation of SEC. No chirality implies that for each radius r there are two possible word according to the clockwise or counterclockwise orientation. The main difficult is, with respect to their handedness, some of the n sensors choose to orient SEC according to , whereas some other to .

In spite of this constraint, we can build the same set A CW as for the case assuming chirality in both direction of SEC. Over this set, assuming that n is odd, we can provide a deterministic algorithm following a similar method as in the previous section. So, the statement of Theorem 3.1 also holds assuming no chirality if n is odd. However, the equivalence does not work with an even number of sensors. A counter example is shown in Figure 4. For any orientation in { , }, there exists one Lyndon word equal to (d, α)(d, β)(d, γ)(d, β). However, the symetry of the configuration does not allow to choose any sensor as a leader. Theorem 3.2 Given a configuration π of any number n ≥ 2 sensors without chirality scattered on the plane, the n sensors are able to determiniscally agree on the same sensor L if and only if n is odd and there exists a radius r such that W (r) is a Lyndon Word.

Conclusion

We studied the leader election problem in networks of anonymous sensors sharing no kind of common coordinate system. Assuming anonymous sensors with chirality, we gave a complete characterization on the sensors positions to deterministically elect a leader for any number n > 1 of sensors. We also showed that our characterization still holds with sensors without chirality if and only if the number of sensors is odd. [Wel91] E Welzl. Smallest enclosing disks (balls and ellipsoids). In LNCS 555, editor, New Results and New Trends in Computer Science, pages 359-370, 1991.

R éf érences

  FIG. 1: Four examples showing the relationship between Sense of Direction and Chirality

FIG. 2 :

 2 FIG. 2: Computation of Configuration words -the sensors are the black bullets. In Figure 2, if is the clockwise orientation, then : W (r 1 ) = (abc, β)(c 2 , γ) 2 (c, γ)(d, β)(e, α) and W (r 2 ) = (c 2 , γ) 2 (c, γ)(d, β)(e, α)(abc, β). If is the counterclockwise orientation, then : W (r 1 ) = (abc, α)(e, β)(d, γ)(c, γ)(c 2 , γ)(c 2 , β) and W (r 2 ) = (c 2 , β)(abc, α)(e, β)(d, γ)(c, γ)(c 2 , γ).

  FIG. 4:A counter example showing that the statement of Theorem 3.2 does not hold if n is even.

[

  Ang80] D. Angluin. Local and global properties in networks of processors. In Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC '80), pages 82-93, 1980.[San07] N Santoro. Design and Analysis of DistributedAlgorithms. John Wiley & Sons, Inc., 2007.


Dr Martin Vuagnat

Prof. Dr Vincent Tognetti

Dr Philippe Jubault

Tatiana Besset
email: tatiana.besset@insa-rouen.fr

Ru(II)-Catalyzed Hydroarylation of in situ generated 3,3,3-Trifluoro-1-propyne by C-H Bond Activation: A Facile and Practical Access to β-trifluoromethylstyrenes

In this study, a practical and straightforward synthesis of β-(E)-trifluoromethylstyrenes by ruthenium-catalyzed C-H bond activation was developed. The readily available and inexpensive 2bromo-3,3,3-trifluoropropene (BTP), a non-ozone depleting reagent, was used as a reservoir of 3,3,3-trifluoropropyne. With this approach, the monofunctionalization of a panel of heteroarenes was possible in a safe and scalable manner (23 examples, up to 87% yield). Mechanistic investigations and density functional theory (DFT) calculations were also conducted to get a better understanding of the mechanism of this transformation. These studies suggested that 1) a cyclometallated ruthenium complex enabled the transformation, 2) this latter exhibited high efficiency in this transformation compared to the commercially available [RuCl2(p-cymene)]2 and 3) the mechanism proceeded through a bis-cyclometallated ruthenium intermediate for the carboruthenation step. Scheme 1. Context of the work. [a] from Apollo Scientific. TM = Transition Metal.

Introduction

Due to the prevalence of fluorinated molecules in material sciences, drug discovery, pharmaceutical and agrochemical industries, [1] there is an increasing demand for innovation in this important and fast-growing research area. Therefore, the design and the development of new technologies to access fluorinated scaffolds aroused the interest of the scientific community and major advances significantly have reshaped this field of research. [START_REF] Kirk | For a selection[END_REF] Indeed, the molecules embedded with a fluorine atom or a fluorinated moiety showed unique behaviors and properties thanks to the features of the fluorine atom. [3] Among them, trifluoromethylated derivatives are major compounds with the Fluoxetine (Prozac®) as a flagship. [1], [START_REF] Kirk | For a selection[END_REF] In particular, the vinyltrifluoromethylated residue is found in several compounds of interest: Trifluridine, Bifenthrin and Panomifene, being typical examples. In comparison with the synthesis of trifluoromethylated arenes, the access to b-trifluoromethylstyrene derivatives was less studied. Synthetic pathways generally used for the preparation of these molecules include 1) cross coupling reactions of (hetero)arenes with suitable trifluoromethylated coupling partners (Scheme 1a), [4] 2) olefination reactions (Scheme 1b), [5] 3) the trifluoromethylation of (pre-functionalized) styrene derivatives (Scheme 1c), [6] and 4) the hydrotrifluoromethylation of terminal alkynes (Scheme 1d). [7] Although efficient, the lack of selectivity observed in some cases (E/Z mixture) combined with the need to use either prefunctionalized substrates or expensive trifluoromethylating reagents as coupling partners seriously hampered their widespread applications to the synthesis of b-trifluoromethylated alkenes.

With a view to develop an efficient, practical, and selective methodology as a sustainable alternative of the existing routes to b-trifluoromethylstyrenes, an ideal scenario would be the selective C-H vinyltrifluoromethylation of arenes with a readily and inexpensive fluorinated source. Worth mentioning that the direct and formal introduction of a vinyltrifluoromethylated residue by transition metal catalyzed C-H bond activation to afford btrifluoromethylstyrenes remains an unmet goal, probably due to the challenges related to the use of the corresponding coupling partners (e.g. low boiling points of the 3,3,3-trifluoropropene (-18 °C) and the 3,3,3-trifluoropropyne (-48 °C)). This strongly contrasts with the numerous reports dealing with the synthesis of non-fluorinated styrene derivatives via olefination [8] and hydroarylation [9] reactions of arenes by transition metal catalyzed C-H bond activation. Indeed, over the years, transition metal catalyzed C-H bond activation became an indisputable synthetic tool in organic chemistry for building molecular complexity with wide applications in academia and industry. [10] Therefore the quest for more efficient catalytic systems is of prime importance and recently, the use of cyclometallated metal complexes as catalytically active species (especially derived from rutheniumbased precursors) has emerged as an appealing new trend. [11,[START_REF] Korvorapun | C-H bond activation reactions[END_REF] Hence, we aim at designing the first synthetic route to btrifluoromethylstyrenes from non-prefunctionalized arenes by transition metal-catalyzed C-H bond activation taking benefit from the unique feature of ruthenium catalysts. With these considerations in mind, we questioned whether we could reach that synthetic goal by the in situ generation of 3,3,3trifluoropropyne, which would then undergo a directed ruthenium -catalyzed hydroarylation reaction in a one-pot process. [13] The cost and the limited availability of gaseous reagents such as the 3,3,3-trifluoropropene and the hazardous 3,3,3-trifluoropropyne have prompted our interest in finding a synthetic appealing reagent as a formal source of the trifluoromethylvinyl moiety. Therefore, we turned our attention to the inexpensive, readily available and non-ozone depleting 2-bromo-3,3,3trifluoropropene (BTP), well known to be an efficient coupling partner in cross-coupling reactions and more recently in palladium catalyzed C-H bond activation. [14] Moreover, BTP has been already used for the in situ generation of the 3,3,3-trifluoropropyne upon basic conditions, making this reagent an ideal candidate for the targeted transformation. [15] Herein, we report a robust and original methodology for the synthesis of btrifluoromethylstyrenes by a directed ruthenium-catalyzed hydroarylation of the in situ generated 3,3,3-trifluoropropyne from BTP upon basic conditions. A fully detailed mechanistic studies along with DFT calculations were conducted to get a better understanding of the reaction.

Results and Discussion

We embarked in this study with the 2-phenylpyridine as the model substrate (Table 1). Using 5 mol% of [RuCl2(p-cymene)]2 in the presence of BTP and sodium tert-butoxide, the functionalization of the 2-phenylpyridine was achieved at 100 °C for 24 h. A mixture of mono-and di-functionalized products was observed in 37% and 4% 19 F NMR yields, respectively, with a total control of the selectivity towards the E isomer (Table 1, entry 1). To circumvent the difunctionalization side reaction, we hypothesized that using a more sterically hindered directing group might prevent the second ortho ruthenation step to occur. [12j,16] With these considerations in mind, the reaction was carried out on the 3trifluoromethyl-2-phenylpyridine and the 3-methyl-2phenylpyridine (Table 1, entries 2 and 3). Pleasingly, in both cases, the mono-functionalized product was exclusively obtained, the 3-methylpyridine being the most efficient directing group in this transformation (Table 1, entry 3). The reaction was robust since when the reaction was conducted under air or in the presence of 5 equivalents of water, the expected product was observed in only a slightly lower yield (Table 1, entries 4 and5). Yield (%) [a] 1 H 100 24 37 + 4 [b] 2 CF3 100 24 49 3 CH3 100 24 66 (42) [c] 4 [d] CH3 100 24 61

5 [e] CH3 100 24 59

6 [f] CH3 100 24 NR 7 [g] CH3 62) [c] Reaction conditions: (Hetero)arene (0.3 mmol, 1.0 equiv.), BTP (5.0 equiv.), [RuCl2(p-cymene)]2 (5 mol%), tBuONa (2.0 equiv.), DMF (0.1 M), T (°C), time (h), Ar.

[a] Yields determined by 19 F NMR using α,α,α-trifluoroacetophenone as an internal standard. [b] Difunctionalized compound. [c] Isolated yield. [d] Under an air atmosphere. [e] The reaction was carried out in the presence of 5 equivalent of H2O. [f] No catalyst. [g] No base. NR: No Reaction.

Control experiments revealed that the presence of a catalyst or a base was crucial for the success of the reaction (Table 1, entries 6 and7). Finally, it turned out that the temperature and the reaction time were key parameters (Table 1, entries 8-11), and when the reaction was conducted at 90 °C for 16 h, the desired product was isolated in 62% yield (Table 1,entry 11).

With these optimized reaction conditions in hand, we explored the substrate scope and a panel of 3-methyl-2-phenylpyridine derivatives diversely substituted on the aryl part was functionalized (22 examples, Scheme 2). Worth mentioning that for less reactive substrates, a slight increase of the reaction temperature and time (100 °C, 24 h) improved the yield of the desired products. [16] When the 3-methyl-2-phenylpyridine 1a and the 3-methyl-2-naphthylpyridine 1b were used as substrates, the expected products 2a and 2b were isolated in 62% and 55% yields, respectively. Several derivatives substituted at the para position were then studied. Compounds bearing electrondonating groups and halogens (2c-2i) were isolated in good yields (up to 78% yield), except in case of the N-Boc protected amine 2d. Gratifyingly, a X-ray analysis of 2h was collected (CCDC 2085147), which ascertained the selective formation of the E isomer at the ortho position of the directing group. [16] Other parasubstituted arenes with electron-withdrawing groups (1j-1m) were also investigated and the corresponding compounds were obtained in high yields (2j-2m). In case of the trifluoromethylated derivative 1m, the reaction was easily scaled up to a one-gram scale, yielding 2m in 67% yield. In the same vein, derivatives bearing arenes substituted at the meta position with electrondonating groups (1n, 1o), halogen (1p) and electron-withdrawing ones (1q, 1r) were functionalized on the less sterically hindered position, except in case of 1n for which both positions were functionalized leading to a mixture of 2n/2n' with 53% isolated yield in a 3.3:1 ratio. In addition, the reaction was tolerant with difunctionalized compound 1s and went smoothly with the ortho substituted derivative 1t. In general, the transformation turned out to be functional group tolerant (cyano, ketone, nitro, carbamate), which demonstrated further its synthetic potential. Pleasingly, heteroarene derivatives (thiophene and furan) were suitable substrates and 2u and 2v were isolated in 72% and 66%, respectively. The reaction was not restricted to the 3-methyl-2-phenylpyridine derivatives as the phenylpyrazole (1w) was successfully functionalized in 54% yield. However, 2w was obtained as a 10:1 mixture of mono-and di-functionalized products. Note that no reaction occurred when replacing the BTP by the 2-bromopropene, the a-bromostyrene, the benzyl 2-bromo-2-propenoate and the phenylmethyl 2-propynoate, showing the unique behavior of the in situ generated 3,3,3-trifluoropropyne as a coupling partner in this reaction. In addition, when other directing groups were investigated, no expected product was obtained. [16] Scheme 2. Scope of the reaction. Reaction conditions: 1 (0.3 mmol, 1.0 equiv.), BTP (5.0 equiv.), [RuCl2(p-cymene)]2 (5 mol%), tBuONa (2.0 equiv.), DMF (0.1 M), 90-100 °C, 16-24 h, Ar. Isolated yields were given. For more details, see the Supporting Information.

[a] 2c was isolated with an inseparable impurity. [b] Reaction performed on a 4.2 mmol scale (1 g of 1m). [c] A 3.7/1 ratio for the products 2n/2n' was determined by 19 F NMR on the crude mixture and the products 2n/2n' were isolated as an inseparable mixture in a 3.3/1 ratio (o/o') as determined by 19 F NMR. [d] A 10/1 ratio (mono/di) for the product 2w was determined by 19 F NMR on the crude mixture and 2w was isolated as a mixture with the product resulting from the difunctionalization in a 10/1 ratio (mono/di) as determined by 19 F NMR. [e] The reaction was carried out on a 0.2 mmol scale.

10.1002/chem.202201928

Accepted Manuscript

Chemistry -A European Journal

This article is protected by copyright. All rights reserved.

To get better insights on the reaction mechanism, we carried out several experiments. At first, an intermolecular competition experiment between 1e and 1m was conducted under standard reaction conditions (Scheme 3a), and a mixture of products 2e and 2m was observed after 5 h with 28% 19 F NMR yield in a 1/3 ratio. These results suggested that electron-deficient substrates reacted slightly preferentially, probably due to an enhance acidity of the proton. [16] Then, based on the recent works from Ackermann, [12a,b,h,i] Larrosa, [12d,e,f] and others who independently reported cyclometallated ruthenium(II) metallacycles as key species, we wondered if it will be also the case in this transformation. Therefore, the complex A and the arene-free ruthenacycle B were synthetized and used as catalysts in the reaction (Scheme 3b). [12f,16,17] Pleasingly, in both cases, 2a was successfully obtained, the cyclometallated catalyst A being the most efficient one. In addition to these findings, under standard reaction conditions, the decoordination of p-cymene from the complex A was also observed by 1 H NMR and free p-cymene was also detected by GC-FID along with the consumption of 1a and the generation of 2a. [12i,12j,16] Scheme 3. Mechanistic studies. For more details, see the Supporting Information.

[a] Yields were determined by 19 F NMR using the α,α,α-trifluoroacetophenone as the internal standard. [b] Ratio was determined by 19 F NMR using the α,α,α-trifluoroacetophenone as the internal standard. [c] Reaction carried out using the complex B instead of the complex A.

10.1002/chem.202201928

Accepted Manuscript

Chemistry -A European Journal

This article is protected by copyright. All rights reserved.

All these results strongly supported that a p-cymene-free cyclometallated ruthenium (II) complex was the catalytically active species in the process. Besides, a scrambling experiment was carried out using the cyclometallated ruthenium complex A, showing no proton-deuterium exchange. [16] Then, a kinetic isotopic effect (KIE) of 1.74 was determined with parallel experiments starting either from 1a or [D]-1a (Scheme 3c). [16] These experiments suggested that the C-H bond activation step was irreversible and probably the rate determining step. [16,18] Based on recent contributions by key players in the field, [START_REF] Korvorapun | C-H bond activation reactions[END_REF] we hypothesized the in situ generation of a bis-cyclometallated ruthenium species. Therefore, stoichiometric experiments using the cyclometallated ruthenium complex A were conducted. When this latter was reacted with BTP and tBuONa (Scheme 3d), traces of 2a were observed, which excluded the involvement of the ruthenacycle A as a key intermediate in the hydroarylation reaction. Pleasingly, the addition of 3-methyl-2-phenylpyridine 1a

(1 equivalent) afforded the expected product 2a in 87% 19 F NMR yield. Similarly, 2a was observed in 60% 19 F NMR yield with a stoichiometric amount of the complex B. [16] These observations suggested the formation of a bis-cyclometallated rutheniumintermediate in the course of the process. Then, experiments with pyridine or bipyridine were conducted. In both cases, 2a was observed in low yields (22% and 25% 19 F NMR yields, respectively), which suggested that the reactivity did not stemmed from a L-type ligand effect from the pyridine part of 1a but rather from the involvement of a second metallacycle intermediate in agreement with the observations from the group of Larrosa. [12d,e,f] To further ascertain the formation of this bis-ruthenacycle complex, we performed an additional experiment. In the presence tBuONa, the complex A was first treated with BTP for two hours at 90°C and no reaction occurred (Scheme 3e). Then, 1a was added and the reaction was carried out for additional three hours. Pleasingly, the formation of the product 2a was observed reaching 97% 19 F NMR yield. Finally, when we studied the reaction by GC-FID (Scheme 3f), an interesting phenomenon was observed. Indeed, during the first 40 minutes, while 1a was consumed and free p-cymene was generated, 2a was not detected. This incubation time might support the formation of a bis-ruthenacycle intermediate, necessary for the hydroarylation reaction to proceed. All these results suggested that a bis-cyclometallated ruthenium complex was a plausible key intermediate in this process, probably involved in the carboruthenation step with the 3,3,3trifluoropropyne as supported by the DFT studies (see Figure 2, vide infra).

Next, we became interested in the use of the air-stable cyclometallated ruthenacycle A as catalyst in order to evaluate its efficiency in this hydroarylation reaction compared to our standard reaction conditions (8 examples, up to 87% yield, Scheme 4). Gratifyingly, the complex A generally exhibited a superior reactivity compared to the [RuCl2(p-cymene)]2 precursor as the desired products were either obtained with higher yields (e.g. 2a, 2p, 2q and 2u) or similar ones (eg. 2k and 2m). For instance, 2q was isolated in 78% yield with these modified reaction conditions (vs 44%, see Scheme 2), illustrating further the unique reactivity of this cyclometallated ruthenium(II)-complex as catalyst. Worth mentioning that the product 2a, which would result from the direct functionalization of the catalyst, has never been detected, confirming the role of the complex A as catalyst.

Scheme 4. Scope using the complex A as catalyst. On 0.3 mmol scale.

[a] Under standard reaction conditions.

To further demonstrate the synthetic value of our methodology, the E to Z isomerization of the compound 2m was achieved and the corresponding product 3 with 2m were isolated as a separable mixture of diastereoisomers in a 98% total yield (Scheme 5). [19] Scheme 5. Post-functionalization reaction. Reaction on 0.3 mmol scale.

[a] The Z/E ratio was determined by 19 F NMR on the crude mixture.

Then, DFT calculations [20] for the in situ generation of the 3,3,3trifluoropropyne from BTP under basic conditions were performed at the wB97X-D/6-31++G(d,p)-SDD IEF-PCM level of theory. They first gave evidence that the involvement of an alkyne intermediate was a reasonable assumption in agreement with literature data. [15] Indeed, as displayed in Figure 1, its formation is highly exergonic (from more than 10 kcal.mol -1 in terms of standard Gibbs energy) and is associated to a moderate overall activation barrier (about 14 kcal.mol -1 ), while occurring through a standard E1cB mechanism (first step: proton abstraction, second step: bromine elimination [21] ). Extensive DFT calculations (using the dispersion-corrected range-separated hybrid wB97X-D functional) were then carried out [20] to investigate the catalytic process of this redox-neutral transformation. To this aim, a particular care has been paid to solvation states, to the competition between various ligand coordinations, and to the different conformations each of them can adopt. This study resulted in identifying 46 relevant stationary points on the energy surface, as represented in Figures S1-S4. [16] They are thoroughly discussed in the supporting information, and unraveled the following key salient features: 1) the formation of the bis-ruthenacycle is energetically favored in comparison with the monocyclometallated ruthenacycle, 2) the bis-ruthenacycle complex is an important intermediate in the catalytic cycle, and 3) the hydroarylation step likely occurs after the formation of the bisruthenacycle.

The figure 2 depicts the lowest Gibbs energy profile that we have identified, where only key-intermediates are represented for the sake of simplicity. [16] After the formation of the monocyclometallated ruthenium complex A by C-H bond activation, a fast ligand exchange between Cl and OtBu occurred (the activation barrier equals 4.3 kcal.mol -1 ) providing D (Figure 2). Then, after decoordination of p-cymene, the arene-free ruthenacycle I2trans' was formed in the presence of 1a and the in situ generated 3,3,3-trifluoropropyne. Assisted by the presence of OtBu in the coordination sphere of the metal, the C-H ruthenation on the second substrate occurred, which was the rate determining step with an activation barrier of 17.5 kcal.mol -1 in term of standard Gibbs energy. Hence, the bis-cyclometallated ruthenium(II) complex K2trans was obtained along with the elimination of tBuOH. Coordination of the DMF further stabilized the complex K2trans by about 3.7 kcal.mol -1 to afford the intermediate L2trans. Then, the insertion of alkyne proceeded, leading preferentially to M2trans1 with an activation barrier equal to 13.8 kcal.mol -1 .

In agreement with the literature data, [START_REF] Korvorapun | C-H bond activation reactions[END_REF] and consistently supported by the above experiments and the DFT studies, we suggested the following mechanism for this redox-neutral process, as depicted in the Scheme 6. At first, formation of the monocyclometallated ruthenium complex A occurs by C-H bond activation. Then, in the presence of 1a, the in situ generated 3,3,3trifluoropropyne from BTP and tBuONa in DMF, the arene-free ruthenacycle I2trans' is generated after decoordination of the pcymene. [16] The latter leads to the irreversible formation of the biscyclometallated Ru(II) complex K2trans as a key intermediate after a second C-H activation event by means of an inner sphere base-assisted CMD mechanism. After coordination of DMF (L2trans) and subsequent carboruthenation the species M2trans1 is afforded, which selectively provides, after protonation and ligand exchange, the expected b-(E)trifluoromethylstyrene 2a and regenerates the monocyclometallated species I2trans'.

Conclusion

In summary, we have developed an unprecedented approach for the synthesis of b-trifluoromethylstyrene derivatives via a directed ruthenium-catalyzed hydroarylation process by C-H bond activation. Using the BTP as a readily available, inexpensive and practical precursor of 3,3,3-trifluoropropyne under basic reaction conditions, a broad range of b-trifluoromethylstyrene derivatives was selectively obtained as E isomers from non-prefunctionalized substrates (23 examples, up to 87% yield). The reaction was selective for mono-vs bis-functionalized products thanks to the astute choice of the 3-methylpyridine as a directing group. Pleasingly, the protocol turned out to be robust (air and moisture tolerant) and functional group tolerant (carbamate, nitro, cyano and ketone), a real asset for late-stage functionalization of complex molecules. This method provides a straightforward synthetic route to original molecular scaffolds, expanding the portfolio of tools to build up these important trifluoromethylated molecules. Detailed mechanistic studies, supported by DFT calculations, provided a better understanding of the reaction mechanism. A metallacycle ruthenium(II)-complex was identified as the catalytically active species and a bis-ruthenacycle was involved as the reactive species in the carboruthenation step. The use of cyclometallated complex as catalytically active species in C-H activation reactions offers new perspectives and further investigations are currently ongoing in our group. Finally, this study also demonstrates how we can use a cost-effective and non-ozone depleting reagent to access high value-added fluorinated scaffolds by means of a sustainable strategy.

  This article is protected by copyright. All rights reserved.

Figure 1 .

 1 Figure 1. Calculated pathway for the creation of the alkyne intermediate.

Figure 2 .

 2 Figure 2. Proposed synthetic pathway from DFT calculations. Standard Gibbs energies in kcal mol -1 . Colour code: H in white, C in grey, N in soft blue, O in red, Cl in green, Na in dark blue, Ru and F in pink.

  This article is protected by copyright. All rights reserved.

Scheme 6 .

 6 Scheme 6. Proposed catalytic cycle.

Table 1 .

 1 Optimization studies.

	Entry	R	T(°C)	t (h)

Acknowledgements

This work has been partially supported by University of Rouen Normandy, INSA Rouen Normandy, the Centre National de la Recherche Scientifique (CNRS), European Regional Development Fund (ERDF), Labex SynOrg (ANR-11-LABX-0029), Carnot Institute I2C, the graduate school for research XL-Chem (ANR-18-EURE-0020 XL CHEM), and by Region Normandie. M.V. and T.B. thank the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no. 758710). The authors would like also to gratefully acknowledge the Centre Régional Informatique et d'Applications Numériques de Normandie (CRIANN) for computing resources. Keywords: C-H activation • Synthetic Methodology • Homogeneous catalysis • β-Trifluoromethylstyrenes • Cyclometallated ruthenium(II)-complex