Mohammad Reza Deylam Salehi

Derya Malak
email: malak@eurecom.fr

An Achievable Low Complexity Encoding Scheme for Coloring Cyclic Graphs

Keywords: Function compression, characteristic graph, graph coloring, graph entropy, eigenvalues, chromatic number

In this paper, we utilize graph coloring for functions captured by cycle graphs to achieve lossless function compression. For functional compression of characteristic graphs or cycles and their OR graphs, we present a feasible scheme for coloring the odd cycles and their OR power graphs. In addition, we calculate the chromatic number for coloring the n-th power of even cycles, which paves the way for calculating the minimum entropy coloring. Moreover, we determine the number of distinct eigenvalues in each OR power and the largest eigenvalue for each power, which allows us to derive a bound on the chromatic number of each OR power of a cycle. Our method provides a proxy for understanding the fundamental limits of compressing cyclic graphs, which has broad applications in various practical use cases of cryptography and computer algebra.

I. INTRODUCTION

The concept of data compression in information theory describes the process of encoding and decoding a source using fewer bits than its original size of the source, which is given by Shannon's entropy [START_REF] Shannon | A mathematical theory of communication[END_REF]. When the sources are distributed and the goal is to recover them jointly at a user, the Slepian-Wolf theorem gives the fundamental limits of compression [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF]. In the case of recovering or computing a deterministic function of distributed sources but not sources themselves, we can provide a further reduction in compression via accounting for the structure of the function [START_REF] Alon | Source coding and graph entropies[END_REF]. This is known as functional compression, where the function is an abstraction of a task.

A. Motivation and Literature Review

Let us begin with an example. Consider a student database with information including the rental records, and health, etc., of individuals. The Ministry of Science wants to offer housing aid to a particular group of students, by only requiring information on the rental contracts, and the payslips of the students, and without disclosing their personal data, due to privacy and redundancy constraints. This scenario is an example of functional compression, which aims to avoid compressing and transmitting large volumes of data, and is instead tailored to the specifics (i.e., the structure, distribution, sensing, or whatever) of the function.

This work is partially supported from a Huawei France-funded Chair towards Future Wireless Networks. Co-funded by the European Union (ERC, SENSIBILITÉ, 101077361). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. In Shannon's breakthrough work in [START_REF] Shannon | A mathematical theory of communication[END_REF], the function to be recovered at the user is the identity function of the source, i.e., the source itself. In [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF], the authors have generalized the noiseless coding of a discrete information source, given in [START_REF] Shannon | A mathematical theory of communication[END_REF], to distributed compression and joint decoding of two jointly distributed and finite alphabet sources. Slepian-Wolf theorem gives a theoretical bound for the lossless coding rate of distributed coding of such sources [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF]. As shown in their work, these two data sequences {X i } ∞ i=1 , and {Y i } ∞ i=1 are obtained by repeated independent drawings from a discrete bivariate distribution. The encoder of each source is constrained to operate without the knowledge of the other source, while the joint distribution is available to the decoder. Practical schemes for Slepian-Wolf compression have been proposed in [START_REF] Pawlak | Postfiltering versus prefiltering for signal recovery from noisy samples[END_REF]- [START_REF] Ahlswede | Network information flow[END_REF].

Different from distributed source compression, in functional compression, the goal is to separately compress the distributed sources such that a deterministic function f (X, Y ) of these sources can be calculated by a receiver. Prior attempts on functional compression can be categorized into works focusing on lossless compression of functions, [START_REF] Shannon | A mathematical theory of communication[END_REF]- [START_REF] Alon | Source coding and graph entropies[END_REF], [START_REF] Shannon | The zero error capacity of a noisy channel[END_REF]- [START_REF] Malak | Weighted graph coloring for quantized computing[END_REF], and those for which the compression schemes tolerate distortion for lossy reconstruction of functions [START_REF] Wyner | The rate-distortion function for source coding with side information at the decoder[END_REF]- [START_REF] Wagner | Rate region of the quadratic gaussian two-encoder source-coding problem[END_REF]. In [START_REF] Orlitsky | Coding for computing[END_REF], Orlitsky and Roche have provided a single letter characterization for general functions of two variables. The authors have used characteristic graphs, where each graph represents the outcomes of one source and the pairwise relationships between each source's outcomes while maintaining the function structure [START_REF] Orlitsky | Coding for computing[END_REF].

Applications of distributed compression problem include the two special cases studied by Ahlswede and Körner, i.e., when f (X 1 , X 2 ) = X 1 , and f (X 1 , X 2 ) = (X 1 +X 2 ) mod 2 [START_REF] Ahlswede | Source coding with side information and a converse for degraded broadcast channels[END_REF]. Körner and Marton, in [START_REF] Korner | How to encode the modulo-two sum of binary sources (corresp.)[END_REF], have derived the rate region for distributed encoding of two binary sources to compute their modulo-two sum at the receiver. In [START_REF] Yamamoto | Wyner-Ziv theory for a general function of the correlated sources (corresp.)[END_REF], Yamamato has considered a source coding problem for Wyner-Ziv systems, in which the receiver estimates the value of f (X, Y ) of the input X given side information Y . In [START_REF] Han | A dichotomy of functions F(X, Y) of correlated sources (X, Y)[END_REF], Han and Kobayashi have established an achievable functional reconstruction scheme, which depends on the structure of f (X 1 , X 2 ), but free of the joint distribution of (X 1 , X 2 ). Optimal coding schemes and achievable rate regions for lossless and lossy computation of f (X, Y ) with side information Y , and distributed compression of f (X, Y ) have been derived in [START_REF] Doshi | Functional compression through graph coloring[END_REF].

B. Overview and Contributions

In this paper, we propose a coding scheme for distributed functional compression problems; where the source character-istic graphs can be represented as cycles, i.e., each source outcome must be distinguished from the two neighboring (or adjacent) outcomes of the same source. We focus on asymptotically lossless compression and decoding of functions with such cyclic characteristic graphs.

Cycle graphs (or cyclic graphs) show up in many practical scenarios, such as periodic functions, and mod functions, which are widely used in cryptography, computer algebra, and science. More specifically, in cryptography, Caesar Ciphers, Rivest-Shamir-Adleman (RSA) algorithm [START_REF] Paar | Understanding cryptography: a textbook for students and practitioners[END_REF], Diffie-Hellman [START_REF] Diffie | Multiuser cryptographic techniques[END_REF], as well as Advanced Encryption Standard (AES) [START_REF] Selent | Advanced encryption standard[END_REF], International Data Encryption Algorithm (IDEA), are several practical examples [START_REF] Basu | International data encryption algorithm (idea)-a typical illustration[END_REF]. The calculation of checksums within serial numbers is another application of interest [START_REF] Knill | Applications: International standard book numbers[END_REF]. For example, ISBNs (International Standard Book Numbers) use mod 11 arithmetic for 10-digit ISBNs or mod 10 for 13digit ISBNs to detect errors. In addition, International Bank Account Numbers (IBANs) use mod 97 arithmetic to identify mistakes in bank account numbers entered by users.

Why cyclic graphs? There are several key advantages to having cycles as characteristic graphs and their coloring. When we color cyclic structures, we can reuse coloring much more efficiently than when coloring any other connected graph with a higher average degree, as we will discuss later in Sect. III-C. In particular, to model a length n source sequence, we use the n-th OR power1 of the characteristic graph [START_REF] Orlitsky | Coding for computing[END_REF] and its valid coloring to compress the source information for computing the desired function in a lossless manner as the blocklength n tends to infinity. The minimum entropy valid coloring gives a lower bound to the compression length required in bits for the lossless reconstruction of the desired function. Due to the features that cycles and their powers can capture, in this paper, we aim to find valid coloring for both even and odd cycles.

The main contributions of this paper can be listed as follows:

• We characterize the exact degree of a vertex of n-th OR power for both odd and even cycles. • We derive the exact chromatic number, denoted by χ C 2l , for even cycles C 2l and their OR powers, for l ∈ Z + . • We devise an achievable coloring scheme for odd cycles C 2l+1 for l ∈ Z + . • We compute the largest eigenvalue, λ 1 (C n i ), of the adjacency matrix A n f for the n-th OR power of cycle graphs. • We compute a valid coloring of a characteristic graph, which is in the form of a cycle, in polynomial time 2 , exploiting the structure of the graph and its OR powers. • We derive lower and upper bounds on the chromatic numbers of OR powers of cycle graphs, χ C j i , based on the relationship between the adjacency matrices of cycle graphs and the eigenvalues of these matrices.

C. Organization

The rest of this article is organized as follows. The second section, II, consists of a review of some technical literature on graphs, cycles, and their valid coloring. Main results section, III, contains theorems, and coloring schemes, drawing on the bounds of the degrees, eigenvalues, and the chromatic numbers of cycle graphs. In Sect. IV, we summarize our key results and outline avenues for exploration.

D. Notation

Capital letter X denotes a discrete random variable with distribution p(x) over the finite alphabet X , whereas x is a realization of X, and {X j } ∞ j=1 is an i.i.d. sequence where each element is distributed according to p(x). The joint distribution of the source variables X 1 and X 2 is denoted by p(x 1 , x 2 ). For a length n i.i.d. vector realization of X 1 , we use the boldface notation x n 1 = x 11 , . . . , x 1n to represent the length n source realization. We also let [n] = {1, . . . , n} for n ∈ Z + .

The distributed sources X 1 and X 2 build the characteristic graphs G X1 and G X2 , respectively, to compute function f (X 1 , X 2 ). We denote by χ G X the chromatic number of G X , by C i a cycle graph with i vertices, by C n i its n-th OR power, and by C j i (l) the set of distinct colors in sub-graph l ∈ V (detailed in Sect. III) of the j-th power of C i .

We denote by J V and I V an all-one and identity matrices of size V ×V each, by A f the adjacency matrix of

C i = G(V, E), where A f = (a xx ′ ) 1≤x, x ′ ≤V
is a symmetric (0, 1)-matrix with zeros on its diagonal, i.e., a xx = 0, and a xx ′ = 1 indicates that vertices x, x ′ ∈ V are adjacent, and a xx ′ = 0 when there is no edge between them. We denote by deg(x) the degree of x ∈ V. The largest and the smallest eigenvalues of A f are denoted by λ 1 , and λ V , respectively, and ϑ(C j i ) is the set of distinct eigenvalues of the adjacency matrix of C j i , i.e., A j f . II. TECHNICAL PRELIMINARY This section introduces the fundamental concepts related to graphs, such as degree, independent sets, and cycles [START_REF] Havel | A remark on the existence of finite graphs[END_REF]- [START_REF] Nagle | On ordering and identifying undirected linear graphs[END_REF]. Furthermore, it discusses some graph-theoretic concepts used in distributed functional compression, such as characteristic graphs, OR power graphs, and their coloring [START_REF] Nagle | On ordering and identifying undirected linear graphs[END_REF]- [START_REF] Alon | Graph powers[END_REF].

A. Regular Graphs, Characteristic Graphs, and OR Powers

Consider a graph G(V, E) on a set of vertices V = [V ] and set of edges E, with the number of vertices being |V| = V . Definition 1. (Degree of a vertex [START_REF] Havel | A remark on the existence of finite graphs[END_REF].) The degree of a vertex x ∈ V, represented by deg(x), of G(V, E) is the number of edges it is connected to, i.e., the number of its neighbors.

The number of edges in G is determined as

|E| = ( l∈[V ] deg(x l ))/2 . ( 1
)
Along with the notion of the degree of a vertex, we next introduce the concept of an independent set, which is critical for determining the valid coloring of a characteristic graph that we discuss later in Sect. II-B. Definition 2. (Independent set, and maximal independent set [START_REF] Beigel | Finding maximum independent sets in sparse and general graphs[END_REF].) An independent set, I(G), in G(V, E) is a subset of vertices of V, such that no two are adjacent. A maximal independent set, M IS(G), is an independent set that is not a subset of any other independent set I(G) of G(V, E).

In the distributed functional compression setting we focus on here, the function outputs at the receiver can be captured through source characteristic graphs. To that end, we next define characteristic graphs to help distinguish between function outcomes toward providing compression savings.

Definition 3. (Characteristic graph, G X [36].) Source X 1 builds a characteristic graph or confusion graph G X1 = G(V, E) to distinguish the outcomes of a function f (X 1 , X 2 )
of the distributed sources X 1 and X 2 with a joint distribution p(x 1 , x 2 ). This graph is constructed using source outcomes, where V = X 1 , and for

x 1 1 , x 2 1 ∈ V that are distinct vertices, ∃ an edge (x 1 1 , x 2 1 ) ∈ E if and only if there exists a x 1 2 ∈ X 2 such that p(x 1 1 , x 1 2 ) • p(x 2 1 , x 1 2 ) > 0 and f (x 1 1 , x 1 2 ) ̸ = f (x 2 1 , x 1
2 ), i.e., these two vertices of G X1 should be distinguished.

The type of characteristic graphs we use in the current paper falls into the category of cyclic graphs. We note that a characteristic graph can be either cyclic or non-cyclic based on the function which it represents. As our next step, we will define k-regular graphs that contain cycles. Definition 4. (k-regular graph, and cycles [START_REF] Chen | Graph theory and its engineering applications[END_REF], [START_REF] Nagle | On ordering and identifying undirected linear graphs[END_REF].) In a regular graph G(V, E), each vertex x ∈ V has the same number of neighbors. The term k-regular graph refers to a regular graph with a degree of k = deg(x) for all x ∈ V.

Cyclic graphs are members of k-regular graphs. More specifically, cyclic graphs are 2-regular graphs and their adjacency matrices are symmetric (0, 1) matrices.

To present the concept of characteristic graphs clearly, the following example is provided.

Example 1. Consider the problem of distributed functional compression of f (X 1 , X 2 ) = (X 1 + X 2 ) mod 2 with two sources X 1 and X 2 and one receiver. Source one X 1 is uniform over the alphabet X 1 = {0, 1, 2, 3, 4, 5}, and X 2 is uniform over X 2 = {0, 1}. Because for even X 1 , the function output is f (X 1 , X 2 ) = X 2 , and for the odd values of X 1 , we have f (X 1 , X 2 ) = X 2 + 1.
At source X 1 even outcomes do not need to be distinguished from each other and are assigned the color G, while odd outcomes of X 1 are assigned the color Y , and similarly for X 2 . We illustrate the coloring of G X1 and G X2 in Fig. 1. For decoding f , it is necessary and sufficient [START_REF] Feizi | On network functional compression[END_REF], if the receiver has the color pairs (Y, G) or (G, Y ), to determine the function outcome, which is 1, whereas, for the pairs (Y, Y ) and (G, G), to infer that the outcome is 0.

To determine the number of bits needed for multiple source instances, and realize the fundamental limits of functional compression of a source sequence [START_REF] Alon | Source coding and graph entropies[END_REF], we exploit the notion of OR powers of graphs, as introduced next.

G X = G(V, E) is represented as G n X = (V n , E n ) where V n = X n
, and for distinct vertices

x n 1 = x 1 11 , . . . , x 1 1n ∈ V n , and x n 2 = x 1 21 , . . . , x 1 2n ∈ V n it holds that (x n 1 , x n 2 ) ∈ E n , when ∃ at least one l ∈ [n] such that (x 1 1l , x 2 1l
) ∈ E, where recall that this condition is determined by the rule in Defn. 3 for building G X .

The total number of vertices in V n is represented by V n . The total number of edges in G n X , i.e., |E n |, can be determined evaluating deg(x n l ), l ∈ [V n ] and using (1).

Definition 6. (Sub-graphs of G n X .) Given the n-th power graph G n X , the set of V graphs {G n-1 X (l)} l∈[V ] in G n X
, each corresponding to a replica of the (n -1)-th power of G X , is denoted as the sub-graphs of G n X . The use of OR powers in determining the rate regions in the asymptotic regime for distributed lossless compression of functions is explored in [START_REF] Feizi | On network functional compression[END_REF] and [START_REF] Malak | Fractional graph coloring for functional compression with side information[END_REF], where the authors have demonstrated that the lowest sum rate could be achieved by encoding the n-th OR power graphs built using X n 1 and X n 2 , p(x n 1 , x n 2 ), and f (x 1 , x 2 ) in the limit as n goes to infinity. Having defined these theoretical tools for our functional compression problem, we next focus on how to utilize them.

B. Coloring of Characteristic Graphs

In this paper, we envision a vertex coloring perspective for the encoding of characteristic graphs. A valid or proper coloring of G X1 is such that each vertex of G X1 is assigned a color, and adjacent vertices of G X1 receive distinct colors. In other words, a valid coloring in our distributed compression setting determines which source realizations should be assigned different codes (colors). Nonadjacent vertices can be assigned the same or different colors. The minimum number of colors required to achieve a valid coloring of G X1 is called the chromatic number, χ G X 1 . The problem of determining χ G X 1 is connected to finding the maximal independent sets of G X1 , and is in general NP-complete [START_REF] Cardinal | Tight results on minimum entropy set cover[END_REF]. A sufficient condition for achieving a minimum entropy coloring is as follows. Provided that p(x 1 , x 2 ) > 0, ∀ (x 1 , x 2 ) ∈ X 1 × X 2 , the maximal independent sets of G X1 and of its power G n X1 , for n > 1, are some non-overlapping fully-connected sets [START_REF] Feizi | On network functional compression[END_REF]. Under this condition, the minimum entropy coloring of G X1 can be achieved by assigning different colors to its different maximal independent sets (see e.g., Sect. III-A).

Next, in Sect. III, we detail our coloring approach devised specifically for cycle graphs.

III. MAIN RESULTS

Let C i be a cycle graph with i vertices that represents the characteristic graph source X 1 builds for computing f , where for an even cycle we have i = 2l, and for an odd cycle, we have i = 2l + 1, for some l ∈ Z + . We seek to achieve an asymptotically lossless functional compression of sources to recover the colors of C i . To that end, we need to determine the optimal coloring for the n-th power of C i , denoted by C n i . We start this section by determining the degree of each vertex of the j-th power of C i , i.e., C j i . Theorem 1. The degrees in the n-th OR power of a cycle graph, C n i for n ≥ 2, are calculated as follows:

deg(x n ) = 2 + j∈[n-1] 2(V j ) , ∀x n ∈ V n . ( 2
)
Proof. See Appendix A.

From Theorem 1, when

G X = C i is a cycle, G n X = C n i is a k-regular graph, i.e., deg(x n l ) = k, for some even number k ∈ Z + , ∀ l ∈ [V n ],
as given by ( 2). We will next calculate the chromatic number of χ C n i , n ≥ 1, for i = 2l, l ∈ Z + .

A. Coloring Cyclic Graphs

In this part, we first discuss even cycles and their j-th powers, and determine their chromatic numbers (see Theorem 2). Then, we analyze odd cycles, for which we introduce a valid coloring scheme (see Prop. 1 and App. B).

1) Even Cycles: We first consider even cycles, which are denoted by C 2l , l ∈ Z + . Vertices are sequentially numbered in a clockwise direction, e.g., see G X1 in Fig. 1, and alternately colored. Even vertices are represented by one color, while odd vertices are denoted with a different color.

Theorem 2. The chromatic number of C n 2l is given as

χ(C n 2l ) = 2 n , l ∈ Z + , n ≥ 1 (3)
Proof. In order to cover all vertices in C n 2l , l ∈ Z + , only two colors are required. Subsequently, for C 2 2l , the sub-graphs are {C 2l (1), C 2l (2), . . . , C 2l (2l)}. The reason for having 2l subgraphs in C 2 2l can be explained as follows. There are (2l) 2 vertices in C 2 2l such that each sub-graph C 2l (•), i.e., a 1-st power graph, has 2l vertices. Due to the fact that each subgraph is two colorable, and the vertices of adjacent sub-graphs are fully connected, the colors of the two sub-graphs should differ. For example, consider {C 2l (l 1 mod (V )), C 2l (l 1 + 1 mod (V ))}. Consequently, each of these sub-graphs requires two different colors disjoint across C 2l (l 1 mod (V )) and C 2l (l 1 +1 mod (V )), resulting in a total of 4 colors. However, due to the cyclic characteristic of power graphs, it is possible to alternate colors from C 2l (l 1 mod (V )) to cover the vertices of C 2l (l 1 + 2 mod (V )) for any l 1 ∈ [2l], and so on, and similarly for the sub-graphs of C 2 2l with even indices. Using induction, we can calculate the number of colors needed to reach a valid coloring from (n-1)-th to n-th powers. Finally, we can calculate χ C n 2l by the relation in [START_REF] Alon | Source coding and graph entropies[END_REF].

We show a valid coloring for the 3 -rd power graph C 3 4 of the even cycle C 4 in Fig. 2. 2) Odd Cycles: Our next consideration is odd cycles, namely C 2l+1 , l ∈ Z + . In the special case with 3 vertices, i.e., for C 3 , a valid coloring requires 3 distinct colors to successfully recover the coloring information of the vertices in decoding. In C 2 3 , each sub-graph of a power graph, i.e., C 3 (1), C 3 (2), and C 3 (3), requires 3 different colors since C 3 is a complete graph. Similarly, using induction we can show that for a valid coloring of C n 3 the minimum number of required colors is given as

χ C n 3 = 3 n , n ≥ 1.
In fact, because C 3 is complete, one cannot exploit color reuse.

Unlike C 3 , for coloring C 5 , which is not complete, one could reuse the colors. A valid coloring of C 5 has χ C5 = 3. We next present an achievable scheme for valid coloring of general odd cycles C 2l+1 and their powers, namely, C n 2l+1 . Proposition 1. (Chromatic number of odd cycles.) The chromatic number can be recursively computed as follows:

χ C n+1 i = 2χ C n i + χ C n i 2 , n ≥ 1 (4)
where χ C n i is the chromatic number of C n i , i.e., the n-th OR power of an odd cycle, where i = 2l + 1 for some l ∈ Z + .

Proof. See Appendix B.

The value of χ C n 2l in Theorem 2 for even cycles is exact, but for odd cycles, it is not. However, we note from Prop. 1 that, χ C n i for n ≥ 1 can be determined from χ Ci . It remains unclear whether, in general, we can lower and upper bound chromatic numbers χ G X of characteristic graphs. By exploiting the eigenvalues of the adjacency matrix, we will next bound χ G X .

B. Eigenvalues of An Adjacency Matrix of Cyclic Graphs

It is possible to bound χ Ci for a cycle graph C i = G(V, E) using the eigenvalues λ i (C i ) (where C i has V eigenvalues) of its adjacency matrix A f distinguishing the outcomes of a function f . We can calculate the largest eigenvalue λ V n (C n i ) of the adjacency matrix of n-th power of C i , i.e., A n f , exploiting the eigenvalues of the V × V all-ones matrix, denoted by J V . To begin with, let us describe the characteristics of J V .

Lemma 1. The eigenvalues of the all-ones matrix J V are 0 and V , with algebraic multiplicities V -1 and 1, respectively. The adjacency matrix of the n-th OR power, A n f , of a cycle C i = G(V, E) is presented as follows:

A n f =     A n-1 f J V n-1 0 V n-1 . . . 0 V n-1 J V n-1 J V n-1 A n-1 f J V n-1 0 V n-1 . . . 0 V n-1 . . . . . . . . . . . . . . . . . . J V n-1 0 V n-1 0 V n-1 . . . J V n-1 A n-1 f     , (5)
which has a block structure, with V row partitions of size V for each partition. In every block row of A n f , i.e., a sub-matrix of A n f that is obtained by selecting a set of consecutive rows from the matrix, with the number of rows equal to the number of rows in A n-1 f , and there are exactly two J V matrices. From Lemma 1, the largest eigenvalue of the J V matrix is equal to V , i.e., λ 1 (J V ) = V . In order to calculate the eigenvalues of A n f , one needs to solve

|A n f -λ(C n i )I V n | = 0. Let λ l (C i ), l ∈ [V ] be the eigenvalues of A f , and ν l (C 2 i ), l ∈ [V 2 ] be the eigenvalues of A 2 f which is a V 2 × V 2 matrix. Let u l , l ∈ [V ]
be the set of eigenvectors of A f . We also let v l , l ∈ [V 2 ] be the set of eigenvectors of A 2 f . We solve the equations A f u = λ(C i )u to determine the eigenvalues λ(C i ) of A f . Similarly, for the 2-nd power graph, we have

A 2 f v = ν(C 2 i )v for A 2 f . The eigenvalues ν(C 2 i ) of A 2
f can be determined by solving the following matrix:

    A f JV 0V . . . 0V JV JV A f JV . . . 0V 0V . . . . . . . . . . . . . . . . . . JV 0V 0V . . . JV A f     v = ν(C 2 i )v , (6)
where

v = [v ⊺ 1 , v ⊺ 2 , . . . , v ⊺ V ] ⊺ , and each v l , l ∈ [V ] is V × 1.
In other words, for each ν(C 2 i ), we have a set of V block row equations, each containing V scalar equations. More specifically, ν(C 2 i ) satisfy the following V block equations:

A f v l + J V v l+1 + J V v l-1 = ν(C 2 i )v l , l ∈ [V ] . (7
) Using [START_REF] Shannon | The zero error capacity of a noisy channel[END_REF], we next derive the eigenvalues of A n f . Theorem 3. The adjacency matrix A n f for the n-th OR power of cyclic graphs, where n ≥ 2, has the same distinct eigenvalues of A n-1 f as well as two new distinct eigenvalues.

Proof. See Appendix D.

Let us consider G to be a general characteristic graph with an adjacency matrix A f . The following section presents bounds on the eigenvalues of A n f for n-th OR powers of G.

C. Bounds on Chromatic Number Derived from Eigenvalues

The following inequality provides bounds on χ G , i.e., the chromatic number of graph G = (V, E):

1 - λ 1 (G) λ V (G) ≤ χ G ≤ ⌊λ 1 (G)⌋ + 1 , (8)
where λ 1 (G) is the largest eigenvalue, and λ V (G) is the smallest eigenvalue of G, respectively [START_REF] Aspvall | Graph coloring using eigenvalue decomposition[END_REF], and the lower and the upper bounds are derived from [START_REF] Hoffman | On eigenvalues and colorings of graphs, ii[END_REF] and [START_REF] Wilf | The eigenvalues of a graph and its chromatic number[END_REF], respectively. Our objective is next to refine the bound in (8) for χ

C j i derived from A j f , j ∈ [n].
To that end, we first consider the smallest eigenvalue of matrix A f , which is λ V (C i ).

In accordance with Brigham and Dutton [START_REF] Brigham | Bounds on graph spectra[END_REF], we have the following lower bound on the V -th eigenvalue in A f of C i :

λ V (C i ) ≥ -2|E|(V -1)/2 . ( 9
)
For the 2-nd power graph C 2 5 , (9) yields λ V 2 (C 2 5 ) ≥ -60. The set of distinct eigenvalues, ϑ, for A 2 f are calculated as ϑ(C 5 ) = {-1.618, 0.618, 2}, and similarly ϑ(C 2 5 ) = {-6.090, -1.61803, 0.61803, 5.09016, 12} for C 2 5 . Consider the set ϑ(C 2 5 ), where λ V 2 (C 2 5 ) = -6.09, which satisfies the bound presented in [START_REF] Doshi | Functional compression through graph coloring[END_REF]. Later, Hong [START_REF] Hong | Bounds of eigenvalues of a graph[END_REF] has derived the following lower bound for graph G:

λ V (G) ≥ -(V /2)[(V + 1)/2] , (10)
where we note that for C 2 5 , it holds that λ V 2 (C 2 5 ) ≥ -12.748. By observing the lower bounds on λ V 2 (C 2 5 ) from ( 9), and (10), for the 2-nd power, one can find that the bound by Hong in [START_REF] Hong | Bounds of eigenvalues of a graph[END_REF] is tighter. Hence, we can enhance the bounds on χ C j i in (8) using the bound for λ V (G) in [START_REF] Orlitsky | Coding for computing[END_REF] given by Hong [START_REF] Hong | Bounds of eigenvalues of a graph[END_REF].

For cyclic graphs, we recall from Theorem 1 that all vertices of C n i for n ≥ 2 have the same degree. Using this result, we next derive an exact characterization for λ 1 (C n i ), n ≥ 2. Theorem 4. The largest eigenvalue λ 1 (C n i ) of the n-th OR power of a cycle graph C n i is determined as follows:

λ 1 (C i ) = 2 , λ 1 (C n i ) = 2 + j∈[n-1] (2V j ) , n ≥ 2 . ( 11
)
Proof. See Appendix E.

The bounds in [START_REF] Doshi | Distributed functional compression through graph coloring[END_REF] are enhanced by utilizing the exact values for λ 1 (C n i ) given in Theorem 4. Ideally, we aim to sharpen these and extend them to include a wider range of characteristic graphs beyond cycles. Our method for constructing A n f results in a lower complexity versus methods that do not exploit the structure of a given function (e.g., [START_REF] Jensen | Graph coloring problems[END_REF] and [START_REF] Hajiabolhassan | On colorings of graph powers[END_REF]), hence, leading to a reduced functional compression rate.

By exploiting the bounds on the eigenvalues of A f given above, we next derive new lower and upper bounds on χ C n i .

Proposition 2. The following bound holds for χ C n i :

1 - 2 + n-1 j=1 (2V j ) -(V n /2)[(V n + 1)/2] ≤ χ C n i ≤ n-1 j=1 (2V j ) + 3 .
Proof. See Appendix G.

Remark 1. From Theorem 1, the total number of edges |E| given in [START_REF] Shannon | A mathematical theory of communication[END_REF], and the lower bound on λ V (C i ) given in ( 9), we derive the following new bound for χ C n i :

1 - 2 + n-1 j=1 (2V j ) -2|E|(V n -1)/2 ≤ χ C n i ≤ 1 + (2 + n-1 j=1 (2V j )) ,
where the term 2 + n-1 j=1 (2V j ) that appears both in the LHS and RHS is equal to the largest eigenvalue of A n f (see [START_REF]Coding for computing[END_REF]). We provide a more comprehensive overview of the largest and smallest eigenvalues and bounds on chromatic numbers in Appendix F. These bounds were utilized for deriving bounds on the chromatic number of a general graph and comparison purposes alongside the bounds presented in this section.

IV. CONCLUSIONS AND FUTURE DIRECTIONS

In this study, we present a new method for distributed compression of functions with characteristic graphs that are represented as cycles and multi-shot computing of functions through OR graph powers. Our approach can achieve the minimum entropy coloring (see e.g., Theorem 1 and Prop. 1) for cycle graphs, while it might not be possible to achieve such a coloring for other connected graph types. Our findings include the analysis of the degree of a vertex for the n-th OR power of cycles and the chromatic number required for coloring even cycles. Additionally, our contributions include a novel scheme for coloring odd cycles that reduces entropy, offering improved compression efficiency. Furthermore, we examine the properties of the adjacency matrices of power graphs, particularly for cycles, and establish bounds for the chromatic number based on the eigenvalues of the adjacency matrices of such graphs. Our approach introduces a new and efficient cyclic coloring technique, as outlined in Prop. 1 and App. B, for the purpose of function compression. Possible future directions include improving the bound in Prop. 2 for general graphs based on the properties in Theorem 2, Lemma 1, and Prop. 1. Specifically, we aim to determine the distribution of coloring, to derive bounds on the entropy of cycle graphs, which will be followed by achieving the entropy of fractional coloring for the n-th OR powers of such graphs (cf. [START_REF] Malak | Fractional graph coloring for functional compression with side information[END_REF]). These bounds can also be applied to characteristic graphs beyond cycles to realize the limits of functional compression for more general computation scenarios.

APPENDIX

A. Proof of Theorem 1

Consider a cycle C i = (V, E), with a total number of vertices V . It is known that each vertex in C i has a degree of two from Defn. 4. The second power can be represented by

C 2 i = (V 2 , E 2 ), and it has V sub-graphs {C i (1), C i (2), . . . , C i (V )}.
For a given sub-graph, say C i (l), l ∈ [V ], any x 1 (l) ∈ C i (l), where x 1 (l) denotes a vertex in the l-th replica of C i , is connected to any vertex of the adjacent sub-graphs, namely ∈ {C i ((l -1) mod (V )), C i ((l +1) mod (V ))}. Therefore, each vertex in C i (l) has V edges to C i ((l -1) mod (V )) and C i ((l + 1) mod (V )) each. For n = 2, taking the sum of the number of edges between adjacent sub-graphs, and each vertex's degree in the sub-graph itself, the degree of each vertex in C 2 i is deg(x 2 1 ) = 2 + 2V . When n = 3, the degree of vertex x 3 1 can be calculated by adding the number of edges connecting it to adjacent sub-graphs and the degree of the vertex in n = 2. This results in deg(x 3 1 ) = 2 + 2V + 2V 2 . For a given sub-graph C n-1 i (l), each vertex x n-1 1 (l) is connected to all vertices in the adjacent sub-graphs, C n-2 i ((l-1) mod (V )) and C n-2 i ((l + 1) mod (V )). Therefore, the degree for the (n -1)-th power, by considering the previous power's degree and using induction, is going to be deg(

x n-1 1 ) = 2+2V +2V 2 +• • •+2V n-2 = 2+ n-2 j=1 2(V j ).
Similarly, for building the n-th power graph of a cycle, using the same procedure, there are V sub-graphs

{C n-1 i (1), C n-1 i (2), . . . , C n-1 i (V )}. Like the second power graph, the sub-graph C n-1 i (l), l ∈ [V ]
, is fully connected to the adjacent sub-graphs {C n-1 i ((l-1) mod (V )), C n-1 i ((l+ 1) mod (V ))}. Therefore, for the n-th power, the degree for each vertex x n can be found using (2).

B. Proof of Proposition 1

The cycle characteristic graph C 5 is 3 colorable. The second power, C 2 5 , has a valid coloring using 8 colors, as shown in Fig. 3, which provides a saving from the greedy coloring algorithm with 9 colors. We use coloring sets for sub-graphs instead of coloring the entire structure at once and encountering difficulties finding optimal coloring. The coloring set, namely C i (l), is a set of colors that can be used for the valid coloring of sub-graph l. It is important to ensure that no two neighboring coloring sets share the same color.

To achieve a valid coloring, we divide the set of vertices into sub-graphs and assign to each a set of colors. The minimum number of colors required for coloring these sets is known.

The following example will help us understand it better.

As previously mentioned, coloring C 5 requires three distinct colors, e.g., {c 1 , c 2 , c 3 }. It is also evident that the cardinality of the color set for C n i changes based on χ C n-1 i that is, the set contains the number of distinct colors needed to color the subgraph. However, the number of coloring sets is always constant and equal to the number of vertices on C i , |V| = V . In the case of C 5 , there are 5 sets of coloring assigned to the subgraphs. To cover the sub-graphs assigned to the first two color sets, the adjacent coloring sets cannot share the same colors. Thus, {c 1 , c 2 , . . . , c 6 } are required in the first two coloring sets, namely C 2 5 (1) and C 2 5 [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF]. Consequently, we can reuse the colors from the first set, since there is no edge between the first C 2 5 (1) and third C 2 5 (3) sub-graphs. It is easy to note that by adding only 2 colors to the third color set and using them in a cyclic manner, all vertices are colored with only 8 colors, which allows us to express C 2 5 (l) for l ∈ [START_REF] Ho | A random linear network coding approach to multicast[END_REF] as:

C 2 5 (1) = {c 1 , c 2 , c 3 }, C 2 5 (2) = {c 4 , c 5 , c 6 }, C 2 5 (3) = {c 7 , c 8 , c 1 }, C 2 5 (4) = {c 2 , c 3 , c 4 }, C 2
5 (5) = {c 5 , c 6 , c 7 } . Based on the number of colors used on coloring sets, the size of five coloring sets for the next power will be adjusted. In this case, the set size for the next power is 8. For C 3 5 , we will follow the same method, which results in a chromatic number of 20. Hence, we can express C = 313, and so on. From this pattern, it is easy to note that, by induction, χ C n+1 i can be determined as (4).

C. Proof of Lemma 1

Let I V be the V × V identity matrix, and J V be the square V × V all-ones matrix, which can be represented as follows:

J V = (1 xx ′ ) 1≤x, x ′ ≤V . (12)
For computing the eigenvalues, first, we need to solve the characteristic equation of J V , which is J V u V = λ(J V )u V , or equivalently, |J V -λ(J V )I V | = 0, where u represents an eigenvector that satisfies the following relationship:

J V u V = λ(J V )u V =   u1 + u2 + • • • + uV . . . u1 + u2 + • • • + uV   =   λ(JV )u1 . . . λ(JV )uV   .
Hence, multiplying J V by the eigenvectors u V , clearly, the above relation implies that the eigenvalues λ(J V ) satisfy λ(J V ) =

V with multiplicity 1, 0 with multiplicity V -1 , which gives the final result.

D. Proof of Theorem 3

Assume that A f has V eigenvalues. To find the eigenvalues of A 2 f , one needs to solve the equation, [START_REF] Shannon | The zero error capacity of a noisy channel[END_REF], that comes from computing the eigenvalues of (6), which gives V equations for each block row, with V eigenvalues. Hence, there are V 2 equations, from which the remaining (V -1) × V equations are just replicas of the eigenvalues of any given block row, due to cyclic symmetry. In [START_REF] Shannon | The zero error capacity of a noisy channel[END_REF], due to the cyclic nature, the terms with indices l + 1 and l -1 are in modulo V . There are two additional equations necessary for calculating eigenvalues of the adjacency matrix as the power increases from n -1 to n.

Both A f and J V are diagonalizable due to symmetry and can be transformed into diagonal matrices H A f and H J V using a matrix P . The relationship between the matrices is expressed as A f = P -1 H A f P and J V = P -1 H J V P . Note 1. In symmetrical matrices, all eigenvalues are real [START_REF] Parlett | The symmetric eigenvalue problem[END_REF].

If we consider the sum of A f and J V , it holds that

A f + J V = P -1 H A f P + P -1 H J V P = P -1 (H A f + H J V )P .
The eigenvalues of A f + J V can now be computed using the diagonal of H A f + H J V , where λ(A f ) and λ(J V ) represent the eigenvalue of A f and J V matrices, respectively.

λ(A f + J V ) = λ(A f ) + λ(J V ) (13)
From Lemma 1, the number of distinct eigenvalues of A 2 f differs from the eigenvalues of A f at most by two, and similarly for the eigenvalues of A j f , j ∈ {Z +≥2 } derived from A j-1 f of the (j -1)-th power graph. From ( 5), the sub-graph A j-1 f in A j f will have the following form:

A j-1 f v l + J V j-1 v l+1 + J V j-1 v l-1 = νv l , l ∈ [V ] , (14)
where j ∈ {Z +≥2 }, and the dimension of the column vector v l is V j-1 × 1. The adjacency matrix for the n-th power, namely A n f , is constructed by combining A n-1 f , J V n-1 from the (n -1)-th power, and V n-1 × V n-1 zero matrices, as specified in [START_REF] Ho | A random linear network coding approach to multicast[END_REF]. The first block row of A n f contains the matrix A n-1 f , the two J V n-1 matrices representing full connections to adjacent two sub-graphs, and the remaining V n-1 ×V n-1 zero matrices indicating the absence of edges between sub-graphs, which impacts the calculation of eigenvalues. Accordingly, the n-th power of the cycle graph has two more distinct eigenvalues from the (n -1)-th power of the cycle graph. As a result, by using Lemma 1, we can prove Theorem 3.

E. Proof of Theorem 4

The eigenvalues of the adjacency matrix of C j i can be derived through generalizing [START_REF] Shannon | The zero error capacity of a noisy channel[END_REF], From [START_REF] Malak | Fractional graph coloring for functional compression with side information[END_REF] and ( 14) it can be observed that the largest eigenvalue for a power graph C n i is obtained by adding up the largest eigenvalue of A n-1 f corresponding to a sub-graph C n-1 i with 2 times the largest eigenvalue of J V n-1 , which is V n-1 (see Lemma 1). Hence, we can derive the final result given in Theorem 4.

F. Additional Bounds on the Largest and Smallest Eigenvalues of Graph Adjacency Matrices

In this section, we will explore several additional bounds on the largest λ 1 (G) and the smallest λ V (G) eigenvalues of adjacency matrices of a graph G(V, E), in addition to the ones in Sect. III-C. Barnes in [START_REF] Barnes | An algorithm for partitioning the nodes of a graph[END_REF] used the Hoffman-Wielandt inequality [START_REF] Hoffman | The variation of the spectrum of a normal matrix[END_REF], and the eigenvalues and the eigenvectors of an adjacency matrix to partition the vertex set of a graph such that the resulting partitions have fewer edges between them than any other possible subsets, which ensures a tight upper bound for the largest eigenvalue of the matrix.

For the largest eigenvalue λ 1 (G), there exist several bounds [START_REF] Hong | Bounds of eigenvalues of a graph[END_REF], [START_REF] Das | Some new bounds on the spectral radius of graphs[END_REF], [START_REF] Favaron | Some eigenvalue properties in graphs (conjectures of graffiti-ii)[END_REF]. For instance, Das and Kumar [START_REF] Das | Some new bounds on the spectral radius of graphs[END_REF] proved that

λ 1 (G) ≥ 2|E| -(V -1)d V + (d V -1)d 1 , (15)
where In [START_REF] Das | Some new bounds on the spectral radius of graphs[END_REF], the authors also bounded λ V (G):

λ V (G) ≥ -2|E| -(V -1)d V + (d V -1)d 1 . (16)
Hong obtained the following lower bound for λ V (G) [START_REF] Hong | Bounds of eigenvalues of a graph[END_REF]:

λ V (G) ≥ -V (V + 1)/2 , (17)
Similarly, Brigham and Dutton bounded λ V (G) as [START_REF] Brigham | Bounds on graph spectra[END_REF]:

λ V (G) ≥ -2|E|(V -1)/2 . (18)
G. Proof of Proposition 2

Combining equation ( 8), which bounds λ 1 (G) and λ V (G) of A f for G = C n i , with Theorem 4, as well as the Hong bound (10) for λ V (G) [START_REF] Hong | Bounds of eigenvalues of a graph[END_REF], we have

1 - 2 + n-1 j=1 (2V j ) -(n/2)[(n + 1)/2] ≤ χ G ≤ 2 + n-1 j=1 (2V j ) + 1 .
Further simplifying the floor function on the RHS by plugging a positive integer-valued λ 1 (C n i ) (see Theorem 4), we obtain the result in Prop. 2.

Fig. 1 .

 1 Fig.1. The problem of a distributed functional compression with two sources, with the characteristic graph for X 1 , i.e., G X 1 , being cyclic, and a receiver.

Fig. 2 .

 2 Fig. 2. A valid coloring of C 3 4 with 8 colors.

Fig. 3 .

 3 Fig. 3. The 2-nd power of C 5 and its valid coloring.

3 5 (

 5 l) for l ∈ [5] as C 3 5 (1) = {c 1 , c 2 , c 3 , c 4 , c 5 , c 6 , c 7 , c 8 }, C 3 5 (2) = {c 9 , c 10 , c 11 , c 12 , c 13 , c 14 , c 15 , c 16 }, C 3 5 (3) = {c 17 , c 18 , c 19 , c 20 , c 1 , c 2 , c 3 , c 4 }, C 3 5 (4) = {c 5 , c 6 , c 7 , c 8 , c 9 , c 10 , c 11 , c 12 }, C 3 5 (5) = {c 13 , c 14 , c 15 , c 16 , c 17 , c 18 , c 19 , c 20 }. Using induction, we can show that C 4 5 requires 50 colors. The followings are the chromatic numbers for the graph powers: χ C 1 5 = 3, χ C 2 5 = 8, χ C 3 5 = 20, χ C 4 5 = 50, χ C 5 5 = 125, and χ C 6 5

  d 1 = max x∈V (deg(x)) and d V = min x∈V (deg(x)).

In this paper, we exclusively focus on the OR graph powers for realizing lossless compression of multi-letter source realizations[START_REF] Körner | Zero-error information theory[END_REF].

Note that the problem of finding a minimum entropy coloring in general graphs (beyond cyclic graphs) is in general NP-hard[START_REF] Cardinal | Tight results on minimum entropy set cover[END_REF].


Matthieu Baumann

Thomas Boch

François-Xavier Pineau

Pierre Fernique

Caroline Bot

Mark Allen

Aladin Lite v3: Behind the Scenes of a Major Overhaul

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Aladin Lite v3: behind the scenes of a major overhaul Matthieu Baumann 1 and Thomas Boch 1 1 Université de Strasbourg, CNRS, Observatoire astronomique de Strasbourg, Strasbourg, France; matthieu.baumann@ astro.unistra.fr thomas.boch@ astro.unistra.fr Abstract. Since its first version in 2013, Aladin Lite has gained significant traction and usage as an HiPS viewer running in the browser. Designed to be easy to embed, it is now used in more than fifty websites and portals in the professional astronomy community. Aladin Lite has been adopted as the sky visualisation component of popular applications: ESA Sky, ESO Science Archive or ALMA Science Archive.

We present a major overhaul of Aladin Lite taking advantage of the GPU with WebGL, and which responds to requests of users, developers and integrators in a context where browser-based applications and science analysis platforms are increasingly important.

While keeping the strengths of the original code, Aladin version 3 will introduce several new features: support of multiple projections (Aitoff, Mollweide, Orthographic, Mercator), support of FITS tiles, display of FITS images, heatmaps visualisation of catalogue data, improved rendering pipeline and coordinates grids. We will give an overview on the architecture used to develop these new functionalities, based on existing Rust code transpiled to WebAssembly, a portable high-performance low-level bytecode for the web supported in all modern browsers. We will also outline the technical challenges and limitations we encountered. Short video footage sequences will demonstrate the existing prototype throughout the presentation.

These improvements have been partially supported by the ESCAPE project and will also benefit to ipyaladin, the widget enabling the usage of Aladin Lite in Jupyter notebooks.

Features details 1.Multiple Screen Projections

The support of multiple screen projections, especially all sky ones have been implemented. This includes Hammer-Aitoff, Arc, Gnomonic (i.e. TAN), Mercator and Mollweide projections. These projections are not rendered tile by tile as in many sky/map viewers, instead it uses a ray-tracing-like approach. Each pixel colour is computed independently from its surrounding neighbours. This condition of independence makes the use of GPUs very adapted. For each pixel of the screen, the algorithm follows:

1. Unproject the screen pixel coordinates to get its world position with respect to the projection chosen. P -1 (s x , s y ) = (w x , w y , w z ) T 2. Compute the HEALPix cell index h i where the world position is located. δ x δ y offset positions within the cell are also computed. 4. Within the tile texture, get the pixel colour located at δ x δ y inside the texture.

Blending of Multiple Image Surveys

Aladin Lite, like Aladin desktop, renders image surveys formatted by the HiPS (Hierarchical image Progressive Survey) standard [START_REF] Fernique | HiPS -Hierarchical Progressive Survey Version 1.0[END_REF]. The coming overhaul of Aladin Lite enables the rendering of FITS tile HiPSes thanks to a basic FITS parser implemented in Rust using the nom crate. The support of FITS tiles is a great improvement, allowing the user to see much more dynamic in those images than given in any compressed ones (JPG, PNG, ...). On top of that, thanks to WebGL and as the tile textures are available from the GPU, it is possible to change the screen pixels in real-time. Grayscale values mapped to a colormap. Left: Rainbow Center: Red Temperature Right: Constant green the performance of rendering a specific mesh at different locations. This is very adapted for rendering simple primitives a thousand times such as simple catalogue sources. The catalogue rendering implements the following features:

• Catalogue sources downloaded through an async JavaScript TAP query.

• HEALPix index array built from the position array, allowing fast and cacheresident retrievals of the sources lying in the field of view (Górski et al. 2005).

• Heat-map visualisation of the sources making visible high density spots.

Rust, WebAssembly and WebGL

The Rust system programming language has been chosen for this project. Rust is a compiled, garbage collector free language. In that sense, it is similar to C++ but relies heavily on the RAII principle which is part of the Rust compiler. Ownership and borrowing rules have been added to the Rust compiler, making Rust its very unique signature. The compilation phase will hence prevent you from e.g. returning a reference to a resource owned by the current function, ... On top of that, Rust can be compiled to Web-Assembly, a portable bytecode designed for high performance applications. Web-Assembly standard is part of the W3C making it reliable for developing applications for the long term support.

The wasm_bindgen crate makes the interfacing with the JavaScript sandbox possible. From Rust, one can export functions/classes to JavaScript, manipulate the DOM and access the WebGL API.

The WebGL API makes available your GPU from the browser. It offers an API similar to OpenGL and is supported by 98-99% of user's browsers.

Figure 1 .

 1 Figure 1.Aladin Lite with all its new coming features

Figure 2 .

 2 Figure 2. Effect of cutout parameters. Left: Too much background Center: Good balance Right: Higher details at the center of galaxy but less brightness

Figure 5 .

 5 Figure 5. APOGEE catalogue sources heat-map, 183232 sources

Acknowledgments. This work has been partly supported by the ESCAPE project (the European Science Cluster of Astronomy & Particle Physics ESFRI Research Infrastructures) that has received funding from the European Union's Horizon 2020 research and innovation programme under the Grant Agreement n. 824064.


Mark G Allen
email: mark.allen@astro.unistra.fr

Stefania Amodeo

François Bonnarel

Marco Molinaro

Françoise Genova

Martino Romaniello

Hendrik Heinl

André Schaaff

Soizick Lesteven

Amo

Franc ¸ois

Moli

Genova

Data stewardship of next-generation data products and services related to ESFRI and other astrophysics infrastructures

Keywords:

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

standards. The FAIR principles (Wilkinson et al. 2016) are guidelines for data resources to be findable, accessible, interoperable and re-usable. These principles are key to Open Science as described in the EOSC Association Strategic Research and Innovation Agenda 6 . In order to implement FAIR in practice it requires the scientists, software engineers and data experts to face the different 'data stewardship' challenges across the different facilities and data types. The work of the project is built around the requirements of the various ESFRI, in particular their needs for standardisation and interoperable tools. A recent Technology Forum event 7 was held to track the progress of the work. This poster paper presents a summary of the most important interoperability topics that have been identified in the different scientific domain areas, and the implications for data stewardship of the different types of data and services and how this is evolving with the development of EOSC. All the IVOA standards cited in the text can be found at https://www.ivoa.net/documents/.

RADIO AND MILLIMETRE ASTRONOMY

Radio and millimetre astronomy produce a wide range of data with special characteristics related to the interferometric nature of the observations. These data have typically been difficult to use by non-specialists, but the developments of current facilities (such as ALMA, JIVE, LOFAR) and new facilities (e.g. SKA) are putting much effort into making the data widely usable. The ESCAPE project contributed to a recent review, published as an IVOA Note 8 , of how the Virtual Observatory can be better adapted to work with radio data. The emphasis of the work, based on the ALMA, JIVE and SKA requirements, is on data discovery and visualisation. Firstly to "Make the data easy to find" -which requires standards for discovery of interferometric data, and definition of the necessary metadata for interoperability.

Secondly, a way to encode "What happened to these data?" -for which the IVOA Provenance Data model [START_REF] Servillat | [END_REF]) has been developed and then tested for radio astronomy (Servillat et al. 2021b). In terms of visualisation, there is a strong motivation to implement the all-sky zoomable interfaces that are enabled by the IVOA HiPS standard (Fernique et al. 2015) and also access to VO services for radio data from Python language programs and notebooks.

HIGH ENERGY ASTROPHYSICS

High energy astrophysics by the future Cherenkov Telescope Array (CTA) will be pursued with an observatory operational model, and many of the interoperability challenges involve the development of archiving and data access services for the complex CTA data. CTA will detect the Cherenkov radiation from particle showers triggered in the Earth atmosphere by high energy particles from astrophysical sources. The data processing chains require the capturing of the 'provenance' information at each step to describe what happened to the data using a common standard for the description. The CTA requirements have been used in the use-cases for the development of the IVOA Provenance Data Model [START_REF] Servillat | [END_REF]. The focus of this effort is to allow users to access quality and reliability information. This work for CTA has been used as an example of how the VO Provenance Scheme can be applied to a large complex project. Its applicability to ESFRI projects and scientific research, has been highlighted in a recent ESCAPE workshop 9 , and also in a review of practical provenance issues for implementation of the provenance standard (Servillat et al. 2021b), and this lead to a proposed management system for provenance information (Servillat et al. 2021a).

NEUTRINO ASTROPHYSICS

The KM3NeT neutrino telescope is involved in ESCAPE CEVO with the work focused on the improvement in the use of common IVOA standards for KM3NeT. Some of the first steps for making neutrino data available in the VO include the establishment of expertise within KM3NeT for the VO publication of tabular data and publication of events (e.g. VOEvents). This is strongly motivated by the need to integrate neutrino data services into multi-messenger astrophysics systems, and to set up complementarity with the services of the KM3NeT Open Data Center 10 . The ESCAPE project work has identified synergies between the requirements for CTA and KM3NeT in terms of provenance standards, as well as for the using of VO applications and tools (e.g. TOPCAT, Aladin).

OPTICAL/UV/IR ASTRONOMY

The use of VO standards is embedded in the operations of many archives and data centres of optical, ultraviolet and infrared astronomy. IVOA has taken an approach of engaging with the large astronomy projects to develop the necessary standards and tools (e.g. Allen et al. ( 2020) and Berriman et al. ( 2020)). The ESCAPE project supports the development of IVOA standards based on the needs, which have been updated recently to include standards for time-domain astrophysics and alerts for multi-messenger astronomy, as well as standards for handling and accessing multi-dimensional data (e.g. cut-outs and visualisation). This is in addition to the maintenance and evolution of the standards that are implemented in services such as the ESO archive [START_REF] Romaniello | [END_REF]. The relevant standards 11 are ADQL 2.0 [START_REF] Osuna | IVOA Astronomical Data Query Language Version 2.00[END_REF] The emphasis of the activities in the CEVO work is the application of IVOA standards for solar physics data, and setting up the basis for interoperability between the astronomy Virtual Observatory and the SOLARNET virtual observatory13 . This involves a first trial for installation of a IVOA standard TAP service at the Royal Observatory of Belgium, and a study on how to link a TAP service and a solar web browser: JHelioviewer14 . The ESCAPE supported participation of EST partners in the IVOA interoperability meetings has enabled extensions of the IVOA metadata (Unified Content Descriptors 'UCD') for the semantics of data content for solar data. This is being used to support cross-column, or even cross-catalog search in SOLARNET VO.

DATA STEWARDSHIP

The ESCAPE project brings the Astronomy and Particle Physics ESFRI infrastructures together to address their common challenges. In doing so, we find that there is a strong motivation to support Open Science via the use of the FAIR principles. One of the concepts reinforced by the project is that it is essential to have disciplinary level standards, and that these standards need to include or allow interfaces with wider interdisciplinary standards and frameworks.

Disciplinary level standards are necessary because there are specific data and information characteristics within a given domain, that must be managed by experts in order to maintain scientific integrity of the data and services. In astrophysics, this includes the disciplinary level metadata for semantic content (IVOA standard UCDs), and also the systems for sky coordinates and indexing (e.g. World Coordinate Systems (Greisen & Calabretta 2002), and the IVOA HiPS/MOC standards), as well as for characterising astronomical observations (such as the IVOA Observational Core Data Model) to name just a few examples. In practice, it is critical for the bodies that will implement the standards to be involved in their definition and maintenance, which has implications for the data stewardship roles that are needed to support open science in astronomy infrastructures.

With the creation of Open Science frameworks such as EOSC in Europe, and in particular the inclusion of existing infrastructures into these, the astrophysics standards and data services can be seen as part of the systems that have a wider scope of data sharing across all areas of science. This requires that the astronomy standards be compatible at some level with more generic standards. This is already the case with the IVOA Resource Registry which uses the Dublin Core metadata and OAI-PMH (Open Archives Initiative Protocol for Metadata Harvesting), and enables the harvesting of records by EUDAT/B2FIND 15 in readiness for inclusion in EOSC catalogues. Also, the IVOA standards definitions themselves which are included in the FAIRSharing database of standards 16 . Detailed interdisciplinary science will demand higher levels of cross-discipline data compatibility, but this is already a big step forward in terms of findability, access and interoperability of resource descriptions. In terms of the EOSC architecture, the astronomy standards would contribute to the "interoperability layer" and VO services can be considered as "thematic services" alongside of those from other domains (e.g. Environmental Science, Life Science, Social Sciences, Photon and Nuclear Sciences). CEVO is also following the efforts to define the cross-disciplinary semantic standard layer in EOSC, so that we will be ready to interface the IVOA semantic standards. Various services, such as authentication and authorisation may be provided generically via shared systems (e.g. the EOSC Core).

In terms of data stewardship, it requires that scientists, software engineers, data publication experts and librarians be aware of the wider context of their work. For example, in these various roles, it will be important to use interoperable metadata and to benefit from systems/tools/services that can be made common across domains. This is challenging because it requires a level of participation in activities that extend beyond the traditional boundaries of a discipline.

The EOSC initiative is promoting widespread uptake of Open Science, and projects such as FAIRsFAIR 17 are fostering FAIR data practices, so there is a rapidily growing set of resources for training which can be of great value. The work on the interoperability topics in the different areas of astrophysics described above is building up data stewardship expertise in the various ESFRI projects in order for common standards to be implemented for data sharing. A longer term aspiration is that the data stewardship skills become more widely recognised and rewarded in career paths, and that it stimulates new levels of innovation to enable new kinds of science.

ESCAPE -The European

  (European Science Cluster of Astronomy & Particle physics ESFRI research infrastructures 1 ) is addressing the Open Science challenges shared by the astrophysics and accelerator particle physics facilities that are labelled as ESFRI 2 by the European Strategy Forum for Research Infrastructures. The astrophysics ESFRI infrastructures are the CTA (Cherenkov Telescope Array), ELT (ESO Extremely Large Telescope), EST (European Solar Telescope), KM3NeT (Kilometre Cube Neutrino Telescope), and SKA (Square Kilometre Array). The other pan-European research infrastructures involved are ESO (European Southern Observatory), JIVE (Joint Institute for VLBI in ERIC) and EGO/Virgo (European Gravitational Observatory Virgo collaboration). The project is being done in the context of the European Open Science Cloud (EOSC 3 ) which is a major European initiative for Open Science. The CEVO 4 Work Package of the ESCAPE project (Allen et al. 2020) addresses the implementation of FAIR principles for Astronomy and Astroparticle ESFRI by using IVOA 5 (International Virtual Observatory Alliance)

  Science Cluster of Astronomy & Particle Physics ESFRI Research Infrastructures has received funding from the European Union's Horizon 2020 research and innovation programme under Grant Agreement no. 824064.

  , DataLink v1.0(Dowler et al. 2015), ObsCore v1.1[START_REF] Louys | Observation Data Model Core Components, its Implementation in the Table Access Protocol Version 1.1[END_REF], SSAP v1.1 8 https://ivoa.net/documents/Notes/RadioVOImp/index.html 9 https://indico.in2p3.fr/event/21913/ 10 https://www.km3net.org/km3net-infradev/open-access-to-km3net-data/ 11 ADQL -Astronomical Data Query Language, ObsCore -Observational Core Data Model, SSAP -Simple Spectral Access Protocol, TAP -Table Access Protocol (Tody et al. 2012), TAP v1.1 (Dowler et al. 2019). A major improvement to the Aladin Lite web visualiser is also underway for use in multiple astronomy services, making use of the HiPS 1.0 standard (Fernique et al. 2019). The progress toward all these standards are recorded in Milestone reports of CEVO, which are available in the public library of ESCAPE Milestones and Reports 12 . One of the innovative activities being pursued in ESCAPE is the prototyping of services for value-added data in astronomy archives. A highlight of this work is the application of Deep Learning techniques to enable searches for 'similar data' within the ESO archive of HARPS instrument spectra -see Sedaghat et al. (2021). Various prototypes have been tested to explore how these types of services can go beyond the traditional data archive interfaces, and offer ways to "let the data speak" in the sense of enabling new views of the data based on characteristics identified by machine learning or other techniques.6. GRAVITATIONAL WAVE ASTRONOMY The detection of gravitational waves and in particular the example where an electromagnetic counterpart was found by follow-up obervations, has marked the beginning a new era of multi-messenger astrophysics (Abbott et al. 2017). Interoperability of multi-wavelength data is essential for these studies which involve measurements from a wide range of instruments. The EGO/Virgo partner in ESCAPE identified the need for tools for visualising and managing the sky regions covered by the credible region probability maps and by the complex footprints of sky survey coverages. The key development supported in the ESCAPE project is the addition of the time-dimension to the IVOA standardised Multi-Order Coverage (MOC) maps. By including the temporal coverage to the spatial sky coverage maps, it enables searches of data for observations that overlap in both space and time. This builds on the work done in the ASTERICS project (Greco et al. 2019), and the new functions have been implemented into Python libraries for the use of the space-time MOCs (Baumann et al. 2020).

7. SOLAR PHYSICS

The European Solar Telescope (EST) is included in the astrophysics ESFRI participating in the ESCAPE project.

https://projectescape.eu

https://www.esfri.eu

https://www.eosc.eu

CEVO -Connecting ESFRI to EOSC using the Virtual Observatory framework

https://ivoa.net

https://www.eosc.eu/sites/default/files/EOSC-SRIA-V1.0 15Feb2021.pdf

https://indico.in2p3.fr/event/23481/

https://projectescape.eu/deliverables-and-reports

http://solarnet.oma.be/

https://www.jhelioviewer.org/