Jaume Baixeries

Victor Codocedo
email: victor.codocedo@inf.utfsm.cl

Mehdi Kaytoue
email: mehdi.kaytoue@insa-lyon.fr

Amedeo Napoli
email: amedeo.napoli@loria.fr

Chapter 6 Computing Dependencies Using FCA

Introduction

The goal of this paper is to present and discuss some of our recent advances on the characterization and computation of different database constraints with Formal Concept Analysis [START_REF] Ganter | Formal Concept Analysis[END_REF] enriched with the formalism of pattern structures [START_REF] Ganter | Pattern Structures and Their Projections[END_REF].

Although the Relational Database Model (RDBM) [START_REF] Mannila | The Design of Relational Databases[END_REF] currently coexists with other non-SQL database models [START_REF] Floratou | Can the elephants handle the nosql onslaught?[END_REF], it still is one of the most popular database systems nowadays. In this model, one of the most important constraints is based on Functional Dependencies [START_REF] Maier | The Theory of Relational Databases[END_REF]. These dependencies are of key importance in the normalization of a database schema (the process of splitting an original dataset into smaller units in order to prevent redundancies and anomalies in the update process), and also in some accessory tasks, like data cleaning [START_REF] Bohannon | Conditional functional dependencies for data cleaning[END_REF].

However, the definition of FDs is too strict for several useful tasks that are not related to the design of a database. One prototypical example is when one should model datasets with imprecision. By this, we mean datasets that contain errors and uncertainty in real-world data. To overcome this problem, different generalizations of FDs have been defined. These generalizations can be classified according to the criteria by which they relax the equality condition of FDs [START_REF] Caruccio | Relaxed functional dependencies -A survey of approaches[END_REF]. According to this classification, two main strategies are presented: "extent relaxation" and "attribute relaxation" (in agreement with the terminology introduced in [START_REF] Caruccio | Relaxed functional dependencies -A survey of approaches[END_REF]).

The difference between these two strategies is that in the case of extent relaxation, a functional dependency may hold only in a (predefined) fraction of the datasets. In the attribute relaxation case, the equality that holds in the definition of a functional dependency may be relaxed, this is, it can be generalized by a more relaxed and general definition of an equality. The dependencies that follow this latter strategy have been named in different ways: fuzzy FDs [START_REF] Belohlávek | Data tables with similarity relations: Functional dependencies, complete rules and non-redundant bases[END_REF], matching dependencies [START_REF] Song | Efficient discovery of similarity constraints for matching dependencies[END_REF], constraint generating dependencies [START_REF] Baudinet | Constraint-generating dependencies[END_REF]. We name them Similarity Dependencies. These dependencies are still an active topic of research in the database community [START_REF] Bertossi | Data cleaning and query answering with matching dependencies and matching functions[END_REF][START_REF] Fan | Dynamic constraints for record matching[END_REF][START_REF] Song | Efficient discovery of similarity constraints for matching dependencies[END_REF][START_REF] Song | Comparable dependencies over heterogeneous data[END_REF].

Formal Concept Analysis (FCA) is a branch of applied lattice theory that dates back to the 1980s [START_REF] Ganter | Formal Concept Analysis[END_REF]. It is based on a binary relation between a set of objects and a set of attributes, and constructs a set of formal concepts with two operators between objects and attributes that form a Galois connection. Formal Concept Analysis has proved to be useful in many different fields: artificial intelligence, knowledge management, data-mining and machine learning, morphological mathematics, etc. [START_REF] Kuznetsov | Machine learning on the basis of formal concept analysis[END_REF].

Pattern structures [START_REF] Kuznetsov | Pattern Structures for Analyzing Complex Data[END_REF] are a generalization of FCA for dealing with complex data within the framework of FCA [START_REF] Kaytoue | Mining gene expression data with pattern structures in Formal Concept Analysis[END_REF][START_REF] Kuznetsov | Pattern Structures for Analyzing Complex Data[END_REF]. One of the interesting features of pattern structures is that they do not need to transform the original dataset before any treatment. As we will later see, this is one keypoint of the results presented here.

The characterization of FDs is a fruitful field in lattice theory [START_REF] Caspard | The lattices of closure systems, closure operators, and implicational systems on a finite set: A survey[END_REF][START_REF] Demetrovics | Normal form relation schemes: A new characterization[END_REF][START_REF] Lopes | Functional and approximate dependency mining: database and fca points of view[END_REF]. Since the characterization of FDs with Formal Concept Analysis (FCA) was originally presented in [START_REF] Ganter | Formal Concept Analysis[END_REF], many papers have continued this line of research. Although this list is not intended to be exhaustive, we name the following general lines of research:

• Characterization of Functional Dependencies [START_REF] Baixeries | A formal concept analysis framework to model functional dependencies[END_REF][START_REF] Lopes | Functional and approximate dependency mining: database and fca points of view[END_REF].

• Characterization of Similarity Dependencies [START_REF] Belohlávek | Data tables with similarity relations: Functional dependencies, complete rules and non-redundant bases[END_REF][START_REF] Lopes | Functional and approximate dependency mining: database and fca points of view[END_REF].

• Characterization of other Database Dependencies [4-6, 9, 32].

In this paper, we present some recent results that deal with the characterization of FDs and similarity dependencies in terms of FCA and Pattern Structures, which have already been published [START_REF] Baixeries | Characterizing approximate-matching dependencies in formal concept analysis with pattern structures[END_REF][START_REF] Baixeries | Computing functional dependencies with pattern structures[END_REF][START_REF] Baixeries | Computing similarity dependencies with pattern structures[END_REF][START_REF] Baixeries | Characterizing Functional Dependencies in Formal Concept Analysis with Pattern Structures[END_REF]. The aim of this paper is not only to offer a general overview of the results obtained by these authors, but to try to present a more general overview of this topic, as well as a discussion of the limitations and potential possibilities that this line of research offers to both researchers and practitioners.

This line of research is relevant to different fields of research, namely, the database dependencies computation in the relational model, since we provide the possibility that existing algorithms in FCA may be used in the relational database model, or complex database analysis, since the generalization of functional dependencies allows the modeling of more complex relations within a dataset.

We present first the basic notations in Sect. 6.2, and then, we present some previous results that link FCA with the characterization of FDs. We introduce the results in Sect. 6.4, which are later discussed in Sect. 6.5.

Notation

In this section, we present the notation that will be used in this paper. The main object that will be used is a dataset D (equivalently table, dataset, set of tuples), that is composed by a set of attributes U and a set of tuples T , this is: D = (U , T ).

Along the paper, we may refer to either a dataset D = (U , T ) or to the set of tuples T that it contains, in which case, we assume also the set of attributes U .

The domain of U is Dom, which is a set of values. In the forthcoming examples, we assume that Dom is a numerical set. A tuple t is a function t : U → Dom. Usually tables are presented as in Table 6.1, where the set of tuples (or objects) is

T = {t 1 ,t 2 ,t 3 ,t 4 }, U = { a, b, c, d }
is the set of attributes, and Dom = {1, 3, 4, 7, 8}. Given a tuple t ∈ T , we say that t(X) (for all X ⊆ U ) is a tuple with the values of t in the attributes x i ∈ X: t(X) = t(x 1 ),t(x 2 ), . . . ,t(x n )

For example, we have that t 2 ({ a, c }) = t 2 (a),t 2 (c) = 4, 4. We also drop the set notation: instead of { a, b } we use ab.

Equivalence Relation

An equivalence relation R on a set T can be seen as:

1. A set of pairs, since R ⊆ T × T . 2. A partition of the set T , this is, a set of subsets of P = {S 1 , S 2 , . . . , S n }, such that each pair S i ∩ S j = / 0 when i = j and

T = S 1 ∪ S 2 ∪ • • • ∪ S n . Each S i is a class of T .
For example, given P = {{1, 2, 3}, {4}}, one has the relation [START_REF] Baixeries | Lattice Characterization of Armstrong and Symmetric Dependencies[END_REF][START_REF] Baixeries | Lattice Characterization of Armstrong and Symmetric Dependencies[END_REF], (4, 4)} (omitting symmetry for the sake of readability). Equivalence relations contain also a partial order with the set inclusion operator when the equivalence relation is seen as a set of pairs, where the meet and join of two equivalence relations are the intersection and the union respectively. If this relation is seen as partitions of a set, the order if defined by the finer (coarser) relation: a partition P i is finer than a partition P j if every class of P i is a subset of a class of P j . The coarser relation is just the reverse.

R P = {(1, 2), (1, 3), (2, 3), (1, 1), (2, 2),
An equivalence relation also defines a relation of two tuples w.r.t. a set of attributes. Following the notation in Example 6.4, we say that two tuples t i ,t j are related w.r.t. the set of attributes X (this is: t i θ X t j ) if t i (X) = t j (X). Example 6.1 We take tuples t 1 ,t 2 in Table 6.1, we state that t 1 θ bc t 2 , but we do not have that t 1 θ ad t 2 .

In this case, a set of attributes X generates an equivalence class Π X . Example 6.2 Again in Table 6.1, we state that Π bc = {{t 1 ,t 2 }, {t 3 }, {t 4 }}, and that Π a = {{t 1 ,t 3 }, {t 2 ,t 4 }}.

Tolerance Relations

We introduce the concept of tolerance relation between values, which is a generalization of an equivalence relation. These two relations are extended to tuples and then used to characterize similarity and functional dependencies, respectively. Definition 6.1 A tolerance relation θ ⊆ T × T on a set T is a reflexive (i.e. ∀t ∈ T : tθt) and symmetric (i.e. ∀t i ,t j ∈ T : t i θt j ⇐⇒ t j θt i ) relation.

A tolerance relation is somehow equivalent to the concept of similarity between two values, and this is how it will be used in this article. Example 6.3 An often used tolerance relation is the similarity that can be defined within a set of integer values. Given two integer values v 1 , v 2 and a user-defined threshold ε:

v 1 θ v 2 ⇐⇒ |v 1 -v 2 | ≤ ε.
For instance, let's take a variable Month, defined over the months of a year. The function Δ Month (m 1 , m 2 ) defines the tolerance relation θ Month such as:

Δ Month (m 1 , m 2 ) = min(|m 1 -m 2 |, min(m 1 , m 2 ) + 12 -max(m 1 , m 2 )) m i θ Month m j ⇐⇒ Δ Month (m i , m j ) ≤ 4
Then θ Month is the tolerance relation that considers two values similar if they have values within 4 months of distance.

This tolerance relation on values can easily be extended to tuples. Example 6. [START_REF] Baixeries | A Formal Context for Symmetric Dependencies[END_REF] We now assume that the variable Month is, in fact, an attribute of a table dataset D = (U , T ). The function Δ Month (t i ,t j ), where t i ,t j ∈ T , defines the tolerance relation θ Month such as:

Δ Month (t i ,t j ) =min(|t i (Month) -t j (Month)|, min(t i (Month),t j (Month))+ 12 -max(t i (Month),t j (Month))) t i θ Month t j ⇐⇒ Δ Month (t i (Month),t j (Month)) ≤ 4
Then θ Month is the tolerance relation that considers two tuples similar if they have values within 4 months of distance, this is, their value in Month is similar.

A tolerance relation generates blocks of tolerance, among a set of tuples. A block of tolerance (w.r.t. an attribute a) is a group of tuples such that their values in attribute a are similar. Definition 6.2 Given a set T , a subset K ⊆ T and a tolerance relation

θ ⊆ T × T . K is a block of tolerance of θ if: 1. ∀t i ,t j ∈ K : t i θt j (pairwise correspondence) 2. ∀t i ∈ K, ∃t j ∈ K : ¬(t i θt j ) (maximality)
Given a set of tuples T and a set of attributes U , for each attribute x ∈ U , we define a tolerance relation θ x on the values of x. The set of tolerance blocks generated by θ x is denoted by T /θ x . Example 6.5 For example, when T = { 1, 2, 3, 4, 5 }, θ is defined as above, i.e.

v 1 θ v 2 ⇐⇒ |v 1 -v 2 | ≤ ε, and ε = 2, then T /θ = { { 1, 2, 3 }, { 2, 3, 4 }, { 3, 4, 5 } }.
We see that T /θ is not a partition, and this is because θ is not necessarily transitive. A partial ordering on the set of all possible tolerance relations in a set T can be defined as follows: Definition 6.3 Let θ 1 and θ 2 two tolerance relations in the set T . We say that θ 1 ≤ θ 2 if and only if

∀ K i ∈ T /θ 1 : ∃ K j ∈ T /θ 2 : K i ⊆ K j
This relation is a partial ordering and generates a lattice classifying tolerance relations, or, equivalently, blocks of tolerance. Given two tolerance relations, θ 1 and θ 2 , the meet and the join operations in this lattice are: Definition 6.4 Let θ 1 and θ 2 two tolerance relations in the set T .

θ 1 ∧ θ 2 = θ 1 ∩ θ 2 = max T ({ K i ∩ K j | K i ∈ T /θ 1 , K j ∈ T /θ 2 }) θ 1 ∨ θ 2 = θ 1 ∪ θ 2 = max T (T /θ 1 ∪ T /θ 2 )
where max T (.) returns the set of maximal subsets w.r.t. inclusion.

t i θ m t j ⇐⇒ |t i (m) -t j (m)| ≤ ε.
Then, assuming that ε = 1, we obtain:

T /θ a = { {t 1 ,t 3 }, {t 2 ,t 4 } } T /θ b = { {t 1 ,t 2 ,t 4 }, {t 3 } } T /θ c = { {t 1 ,t 2 ,t 3 }, {t 4 } } T /θ d = { {t 1 ,t 3 }, {t 2 ,t 4 } }
We can check the following meet and join operations:

θ a ∧ θ b = { {t 1 }, {t 2 ,t 4 }, {t 3 } } θ a ∨ θ b = { {t 1 ,t 2 ,t 3 ,t 4 } } θ a ∧ θ c = { {t 1 ,t 3 }, {t 2 }, {t 4 } } θ a ∨ θ c = { {t 1 ,t 2 ,t 3 ,t 4 } } θ b ∧ θ c = { {t 1 ,t 2 }, {t 3 }, {t 4 } } θ b ∨ θ c = { {t 1 ,t 2 ,t 3 ,t 4 } }
We can also extend the definition of a similarity relation on a single attribute to a similarity relation to sets of attributes. Given X ⊆ U , the similarity relation θ X is defined as follows:

(t i ,t j ) ∈ θ X ⇐⇒ ∀ x ∈ X : (t i ,t j ) ∈ θ x
Two tuples are similar w.r.t. a set of attributes X if and only if they are similar w.r.t. each attribute in X.

FCA and Database Dependencies

In this section we present the two kinds of dependencies that will be discussed here: functional dependencies and similarity dependencies. In fact, the latter are a generalization of the former. As we will see, in order to switch from functional to similarity dependencies, we just need to change the implicit equivalence relation that is behind the definition of functional dependencies by a tolerance relation.

We also present the basics of FCA that are needed in order to understand some previous results concerning the characterization of FDs using FCA. We finish this section by presenting pattern structures, which is a generalization of FCA. We will use this formalism in the following section in order to present the main results in this article.

Functional Dependencies Definition 6.5 ([35]) Let T be a set of tuples, and X,Y ⊆

U . A functional depen- dency (FD) X → Y holds in T if: ∀t,t ∈ T : t(X) = t (X) =⇒ t(Y ) = t (Y )
For instance, the functional dependencies a → d and d → a hold in Table 6.1, whereas the functional dependency a → c does not hold since t 2 (a) = t 4 (a) but t 2 (c) = t 4 (c).

Similarity Dependencies

Similarity Dependencies are a generalization or a relaxation of Functional Dependencies. The definition of similarity dependencies is the following: Definition 6.6 Let X,Y ⊆ U and let θ be a tolerance relation: This definition just replaces the equality relation (an equivalence relation) for functional dependencies with a tolerance relation, which means that transitivity is dropped. In the following sections we will see that this generalization is captured by FCA in order to characterize both kinds of dependencies.

X → Y is a similarity dependency if: ∀t i ,t j ∈ T : t i θ X t j =⇒ t i θ Y t j While a functional dependency X → Y is

Formal Concept Analysis

Formal Concept Analysis (FCA) is a mathematical framework allowing to build a concept lattice from a binary relation between objects and their attributes. The concept lattice can be represented as a diagram where classes of objects/attributes and ordering relations between classes can be drawn, interpreted and used for datamining, knowledge management and knowledge discovery [START_REF] Wille | Why can concept lattices support knowledge discovery in databases[END_REF].

We use standard definitions from [START_REF] Ganter | Formal Concept Analysis[END_REF]. Let G and M be arbitrary sets and I ⊆ G×M be an arbitrary binary relation between G and M. The triple (G, M, I) is called a formal context. Each g ∈ G is interpreted as an object, each m ∈ M is interpreted as an attribute. The statement (g, m) ∈ I is interpreted as "g has attribute m". The two following derivation operators (•) :

A = {m ∈ M | ∀ g ∈ A : gIm} f or A ⊆ G, B = {g ∈ G | ∀ m ∈ B : gIm} f or B ⊆ M
(A 1 , B 1 ) ≤ (A 2 , B 2 ) ⇔ A 1 ⊆ A 2 (⇔ B 2 ⊆ B 1 ). (A 1 , B 1 ) is a sub-concept of (A 2 , B 2 ),
while the latter is a super-concept of (A 1 , B 1 ). With respect to this partial order, the set of all formal concepts forms a complete lattice called the concept lattice of the formal context (G, M, I), i.e. any subset of concepts has both a supremum (join ∨) and an infimum (meet ∧) [START_REF] Ganter | Formal Concept Analysis[END_REF]. For a concept (A, B) the set A is called the extent and the set B the intent of the concept. The set of all concepts of a formal context (G, M, I) is denoted by B(G, M, I) while the concept lattice is denoted by B(G, M, I).

An implication of a formal context (G, M, I) is denoted by X → Y , X,Y ⊆ M and means that all objects from G having the attributes in X also have the attributes in Y , i.e. X ⊆ Y . Implications obey the Armstrong rules (reflexivity, augmentation, transitivity). The minimal subset of implications (in sense of its cardinality) from which all implications can be deduced with Armstrong rules is called the Duquenne-Guigues basis [START_REF] Guigues | Familles minimales d'implications informatives résultant d'un tableau de données binaires[END_REF].

Objects described by non binary attributes can be represented in FCA as a manyvalued context (G, M,W, I) with a set of objects G, a set of attributes M, a set of attribute values W and a ternary relation I ⊆ G × M ×W . The statement (g, m, w) ∈ I, also written g(m) = w, means that "the value of attribute m taken by object g is w". The relation I verifies that g(m) = w and g(m) = v always implies w = v. For applying the FCA machinery, a many-valued context can be transformed into a formal context with a conceptual scaling. The choice of a scale should be wisely done w.r.t. data and goals since it affects the size, the interpretation, and the computation of the resulting concept lattice.

Functional Dependencies as Implications

In this section we present how functional dependencies are characterized with FCA (see [START_REF] Baixeries | Lattice Characterization of Armstrong and Symmetric Dependencies[END_REF] and [START_REF] Ganter | Formal Concept Analysis[END_REF]). This is performed by transforming a table into a formal context. The implications that hold in that formal context will be equivalent to the set of functional dependencies that hold in the original table.

Again, with a table D with attributes U taking values in Dom, we build the formal context K = (B 2 (G), M, I), where G = T and M = U to respect the FCA notation from [START_REF] Ganter | Formal Concept Analysis[END_REF]. B 2 (G) = { (t i ,t j ) | i < j and t i ,t j ∈ T } is the set of all pairs of tuples from T (excluding symmetry and reflexivity to avoid redundancy) Then, the relation I is defined as

(t i ,t j ) I m ⇔ t i (m) = t j (m), for m ∈ M
while attributes remain the same. Figure 6.1 illustrates the transformation of the initial data to build a formal context and its concept lattice.

The number of objects of this newly built formal context is in the range of O(|T 2 |) (where |T | is the number of tuples), so it can be significantly larger than the original set of tuples T .

K a b c d (t 1 ,t 2 ) × × (t 1 ,t 3 ) × × × (t 1 ,t 4 ) × (t 2 ,t 3 ) × (t 2 ,t 4 ) × × × (t 3 ,t 4 )
Fig. 6.1: Characterizing functional dependencies with FCA: from a set of tuples to a formal context and its concept lattice We now explain how this concept lattice characterizes the set of all functional dependencies that hold in the table T with the following proposition:

Proposition 6.1 ([3, 24]) A functional dependency X → Y holds in a table T if and only if {X} = {X,Y } in the formal context K = (B 2 (G), M, I).

This proposition states how to test that a FD holds using the concept lattice that has been computed. For instance, let us suppose that we want to test whether a functional dependency a → b holds in the formal context of Fig. 6.1. We should test in the corresponding concept lattice if {a} = {a, b} . In this particular case, we observe that {a} = {a, d} and {a, b} = {a, b, d}, which means that this dependency does not hold in T . On the other hand, the dependency ac → d holds, since {a, c} = {a, c, d} and {a, c, d} = {a, c, d}.

An interesting consequence is that the set of implications that hold in the formal context K = (B 2 (G), M, I) is syntactically equivalent to the set of functional dependencies that hold in a table T [START_REF] Baixeries | Lattice Characterization of Armstrong and Symmetric Dependencies[END_REF][START_REF] Ganter | Formal Concept Analysis[END_REF]. By syntactically we mean that whenever an implication X → Y holds in K, then the functional dependency X → Y holds in T .

Pattern Structures

A pattern structure is defined as a generalization of a formal context describing complex data [START_REF] Ganter | Pattern Structures and Their Projections[END_REF]. Formally, let G be a set of objects, let (D, ) be a meet-semilattice of potential object descriptions and let δ : G -→ D be a mapping associating each object with its description. Then (G, (D, ), δ ) is a pattern structure. Elements of D are patterns and are ordered thanks to a subsumption relation : ∀ c,d ∈ D,c d ⇐⇒ c d = c.

A pattern structure (G, (D, ), δ ) is based on two derivation operators (•) � :

d � = {g ∈ G|d δ (g)} f or d ∈ (D, ).
These operators form a Galois connection between (℘(G), ⊆) and (D, ). Pattern concepts of (G, (D, ), δ ) are pairs of the form (A, d), A ⊆ G, d ∈ (D, ), such that A � = d and A = d � . For a pattern concept (A, d), d is a pattern intent and is the common description of all objects in A, the pattern extent. When partially ordered by

(A 1 , d 1 ) ≤ (A 2 , d 2 ) ⇔ A 1 ⊆ A 2 (⇔ d 2 d 1 )
, the set of all concepts forms a complete lattice called pattern concept lattice.

As for formal contexts, implications can be defined. For c, d ∈ D, the pattern implication c → d holds if c � ⊆ d � , i.e. the pattern d occurs in an object description if the pattern c does. Similarly, for A, B ⊆ G, the object implication A → B holds if A � B � , meaning that all patterns that occur in all objects from the set A also occur in all objects in the set B [START_REF] Ganter | Pattern Structures and Their Projections[END_REF].

Results

In this section we show some of the most relevant results regarding the characterization of functional and similarity Dependencies with pattern structures. These results have appeared in [START_REF] Baixeries | Computing functional dependencies with pattern structures[END_REF][START_REF] Baixeries | Characterizing Functional Dependencies in Formal Concept Analysis with Pattern Structures[END_REF] for functional dependencies and in [START_REF] Baixeries | Characterizing approximate-matching dependencies in formal concept analysis with pattern structures[END_REF][START_REF] Baixeries | Computing similarity dependencies with pattern structures[END_REF] for Similarity Dependencies. We will see now that pattern structures are able to characterize functional and similarity dependencies in quite an elegant manner, without incurring in any extra transformation process.

Characterization of Functional Dependencies with Pattern Structures

The main idea behind this approach is to avoid the creation of a formal context K = (B 2 (G), M, I) (defined in Sect. 6.3.4) that, as it has already been discussed, has a size of order O(|T 2 |). The strategy consists in using Pattern Structures that will be built on the dataset, without any sort of transformation. Consider a dataset D = (U , T ) as a many-valued context (G, M,W, J) where G = T corresponds to the set of objects ("rows"), M = U to the set of attributes ("columns"), W = Dom the data domain ("all distinct values of the table ") and J ⊆ G × M × W a relation such that (g, m, w) ∈ J also written m(g) = w means that attribute m takes the value w for the object g [START_REF] Ganter | Formal Concept Analysis[END_REF]. In the left table of Fig. 6.2, b(t 4 ) = 3.

We show how a partition pattern structure can be defined from a many-valued context (G, M,W, J) and show that its concept lattice is equivalent to the concept lattice of K = (B 2 (G), M, I) introduced above. Intuitively, formal objects of the pattern structure are the attributes of the many-valued context (G, M,W, J). Then, given an attribute m ∈ M, its description δ (m) is given by a partition over G such that any two elements g, h of the same class take the same values for the attribute m, i.e. m(g) = m(h). The result is given in Fig. 6.2 (middle). As such, descriptions obey the ordering of a partition lattice as described above. It follows that (G, M,W, J) can be represented as a pattern structure (M, (D, ), δ ) where M is the set of original attributes, and (D, ) is the set of partitions over G provided with the partition intersection operation . An example of concept formation is given as follows, starting from set {a, d} ⊆ M:

{a, d} � = δ (a) δ (d) = {{t 1 ,t 3 }, {t 2 ,t 4 }} {{t 1 ,t 3 }, {t 2 ,t 4 }} = {{t 1 ,t 3 }, {t 2 ,t 4 }} {{t 1 ,t 3 }, {t 2 ,t 4 }} � = {m ∈ M|{{t 1 ,t 3 }, {t 2 ,t 4 } δ (m)} = {a, d}
Hence, ({a, d}, {{t 1 ,t 3 }, {t 2 ,t 4 }}) is a pattern concept. The resulting pattern concept lattice is given in Fig. 6.2 (right).

id a b c d ((g, h), m) ∈ I means that m(g) = m(h). The resulting concept lattice is used to characterize the set of functional dependencies [START_REF] Ganter | Formal Concept Analysis[END_REF].

t 1 1 3 1 t 2 4 3 4 3 t 3 1 8 4 1 t 4 4 3 7 3 m (m) ∈ (D, ) a {{t 1 ,t 3 }, {t 2 ,t 4 }} b {{t 1 ,t 2 ,t 4 }, {t 3 }} c {{t 1 ,t 2 ,t 3 }, {t 4 }} d {{t 1 ,t 3 }, {t 2 ,t 4 }} d
We also show that the lattice of pattern concepts yielded by the many-valued context (G, M,W, J) is isomorphic to the lattice of formal concepts that is yielded by the formal context (B 2 (G), M, I):

Proposition 6.2 ([11]) (B, A) is a pattern concept of the partition pattern struc- ture (M, (D, ), δ ) if and only if (A, B) is a formal concept of the formal context (B 2 (G), M, I) for all B ⊆ M, A ⊆ B 2 (G) (equivalently A is a partition on G).
Following this equivalence, the following proposition shows that the functional dependencies that are computed in (B 2 (G), M, I) and in (G, M,W, J) are exactly the same:

Proposition 6.3 ([11]) A functional dependency X → Y holds in a table T if and only if:

{X} � = {XY } � in the partition pattern structure (M, (D, ), δ ).

Example. We consider a FD that holds in Table 6.1: a → d. It is characterized from (B 2 (G), M, I) as an attribute implication. It holds as well in (M, B 2 (G), I) and (M, (D, ), δ ) as an object implication.

Similarity Dependencies

In this section we present Proposition 6.4, the second main result of this article. As the reader will realize, the results in this section are very similar to those presented in the previous section. In fact, this is congruent with the fact that we are showing that the formalism of pattern structures is flexible enough to characterize not only dependencies that are based in an equivalence relation, but also with a softer relation, this is, a tolerance relation.

As in the previous case for functional dependencies, the dataset can be represented as a pattern structure (U , (D, ), δ ) where U is the set of original attributes. Here, (D, ) is the set of sets of tolerance blocks (differently from the previous section, where we had a partition or equivalence relation) over the set of tuples T provided with the meet operation introduced in Definition 6.4. The description of an attribute x ∈ U is given by δ (x) = T /θ x which is given by the set of tolerance blocks. Example 6.7 An example of concept formation in the pattern structure is given as follows. Consider the table in Example 6.1. Starting from the set { a, c } ⊆ U and assuming that t i θ x t j ⇐⇒ |t i (x) -t j (x)| ≤ 2 for all attributes:

{a, c} � = δ (a) δ (c) = {{t 1 ,t 3 }, {t 2 ,t 4 }} {{t 1 ,t 2 ,t 3 }, {t 4 }} = {{t 1 ,t 3 }, {t 2 }, {t 4 }} {{t 1 ,t 3 }, {t 2 }, {t 4 }} � = {x ∈ U |{{t 1 ,t 3 }, {t 2 }, {t 4 }} δ (x)} = {a, c}
Hence, ({a, c}, {{t 1 ,t 3 }, {t 2 }, {t 4 }}) is a pattern concept.

Then the pattern concept lattice allows us to characterize all similarity dependencies holding in the set of attributes U : Proposition 6.4 ([10]) An similarity dependency X → Y holds in a table T if and only if: {X} � = {X,Y } � in the pattern structure (U , (D, ), δ ).

This result is isomorphic to Proposition 6.3. That means that the softening of the relation between tuples (equality in the case of functional dependencies, similarity in this present case) does not prevent the pattern structure from characterizing these dependencies. This is due in part to the fact that a partial order can also be defined over tolerance blocks. We do not mean that this condition is sufficient, but it is evidently necessary.

Discussion

We have revisited some results that concern the characterization of two different kinds of dependencies with pattern structures. What is the interest of using this formalism for the computation of dependencies that have already been computed using different methods not related to lattice theory? The answer is many-fold:

1. A unified framework. We have seen that two different kinds of dependencies may be handled using the same formalism (pattern structures). Obviously, the parameters for this formalism (objects, attributes, domain, relation) depend on the kind of dependency that we are dealing with, but as we have seen in Propositions 6.3 and 6.4, the characterization of both kinds of dependencies are equivalent. This is also true for other different kinds of dependencies: order-like dependencies [START_REF] Baixeries | Computing functional dependencies with pattern structures[END_REF][START_REF] Codocedo | Characterization of Order-like Dependencies with Formal Concept Analysis[END_REF], acyclic join dependencies [START_REF] Baixeries | A formal context for acyclic join dependencies[END_REF], degenerate multivalued dependencies [START_REF] Baixeries | Characterization and armstrong relations for degenerate multivalued dependencies using formal concept analysis[END_REF], to name some of them. If we examine all these results, FCA offers an encapsulation of the semantics of each kind of dependency so that their syntax is handled by the pattern structures. 2. Common algorithms. As a consequence of the previous remark, we observe that potentially the same algorithms that have been used to compute formal concepts, implications, concept lattices, minimal (Duquenne-Guigues) bases can be used for all characterizations. One of the most remarkable examples is the computation of the implications that hold in a (transformed) context in Sect. 6.3.4, which are, in fact, the functional dependencies that hold in a dataset. 3. New semantics. Because we are using FCA and pattern structures in order to characterize dependencies, we also have structures that were unknown in database theory: formal concepts, concept lattices, etc. These objects have not been yet explored in the scenarios that we have described in this paper. Said otherwise: how can a concept lattice help a database practitioner? 4. Different classification. In [START_REF] Abiteboul | Foundations of Databases[END_REF][START_REF] Maier | The Theory of Relational Databases[END_REF] there are different criteria in order to classify dependencies in the relational database model (tuple or non-tuple generating, typed or non-types, etc). However, with FCA there is no difference between the characterization of tuple-generating dependencies like multivalued dependencies [START_REF] Baixeries | Lattice Characterization of Armstrong and Symmetric Dependencies[END_REF][START_REF] Baixeries | A lattice representation of relations, multivalued dependencies and armstrong relations[END_REF] and non tuple-generating dependencies like functional dependencies [START_REF] Baixeries | Characterizing Functional Dependencies in Formal Concept Analysis with Pattern Structures[END_REF]. In fact, the difference is encapsulated within the relation between objects and attributes, and the difference shows up the different kinds of attributes of the formal context: partitions of the attribute set in the former case, sets of attributes in the latter. Could we devise a different classification of dependencies w.r.t. FCA?

We suggest some items for discussion that may be of interest to our FCA community as well as the database community that, eventually, may become interested in our research:

1. Solve problems that are present in the database community. To name just a few of them: dependencies with complex data (graphs, sequences, etc. . . ), storage limitations, fast computation of queries. 2. Do not fight the standard. We need to admit that a standard in a long-time established community with a large number of users like that of the database community is a difficult thing to change. Even if that standard is too complex, obscure or anti-intuitive w.r.t. other formulations, the fact that this formalism has survived for such a long time in such a huge community means that it will stay there. For instance, if we take the definitions of a closure in basic texts of database theory [START_REF] Abiteboul | Foundations of Databases[END_REF][START_REF] Maier | The Theory of Relational Databases[END_REF], we see that the equivalent in FCA is much clearer and easy to understand (maybe, this is a biased point of view of someone who has been working with FCA for years). But even if this is the case, that community will not change their formalism by our new proposal. Therefore, instead of offering them a completely new formalism, our task should be to offer them different and more efficient solutions to their problems, not expecting that they would necessarily embrace FCA as a new paradigm. 3. Have the practitioner in mind. It is clear that some victories achieved by FCA outside our community have to do with applications rather than theory. Obviously, theory is the sine qua non condition for the practical solutions, but, again, what seems appealing to people outside our community is the potential use of FCA as a problem solving tool. In the case of the database community, we think that this is also true: they already have their formalisms, which are very unlikely to be changed. But they have a set of open problems that may be solved by FCA or some old problems which may be better solved using FCA.

Obviously, we just mention these points as a departure point for debate. We do not assume that all the previous points need to be an absolute truth, we just hope that they can be of interest for researchers in our community.

Conclusions

We have seen that FCA and pattern structures can characterize different kinds of dependencies in an elegant and compact way. These results are also present for different kinds of database dependencies. We have shown the advantages and some potential drawbacks that FCA offers to the database community.

We think that there has been an enormous amount of work in this fields that needs to be continued. The results presented in this paper show that there are still new lines of research that need to be explored, and that may be fruitful not only to the FCA community but, most importantly, to the database community.

Example 6 . 6

 66 Based on Example 6.1, let us define the tolerance relation θ m w.r.t. an attribute m ∈ { a, b, c, d } as follows:

  define a Galois connection between the powersets of G and M. The derivation operators {(•) , (•) } put in relation elements of the lattices (℘(G), ⊆) of objects and (℘(M), ⊆) of attributes and reciprocally. A Galois connection defines the closure operators (•) and realizes a one-to-one correspondence between all closed sets of objects and all closed sets of attributes. For A ⊆ G, B ⊆ M, a pair (A, B) such that A = B and B = A, is called a formal concept. Concepts are partially ordered by

Fig. 6 . 2 :

 62 Fig. 6.2: The original data (left), the resulting pattern structure (middle) and its pattern concept lattice (right)

Table 6 . 1 :

 61 An example of a table D, i.e. a set of tuples

  based on equality of values, a similarity dependency X → Y holds if each pair of tuples having similar values w.r.t. attributes in X has similar values w.r.t. attributes in Y .

Computing Dependencies Using FCA

Acknowledgements This research was supported by the recognition of 2017SGR-856 (MACDA) from AGAUR (Generalitat de Catalunya), and the grant TIN2017-89244-R from MINECO (Ministerio de Economía y Competitividad).


A Baraviera

Renaud Leplaideur
email: renaud.leplaideur@unc.nc

THE JACARANDA TREE IS STRONGLY APERIODIC AND HAS ZERO ENTROPY

We prove that the Jacaranda tree obtained as a fixed point for a substreetution in previous work of the authors is strongly aperiodic and that the number of patches increases linearly with respect to the size of the patch. As a consequence we get that the tree has zero entropy.

1. Introduction 1.1. The Jacaranda tree and the substreetutions. In the present paper, we put a step forward the ergodic study of the Jacaranda tree which is obtained from a special example of substreetution as defined by authors in [START_REF] Baraviera | Substreetutions and more on trees[END_REF].

Substreetutions are substitutions acting on the set of colored binary trees {0, 1} F + 2 , where F + 2 is the free semi-group with two generators a and b. They extend to {0, 1} F + 2 classical objects as the Thue-Morse and the Fibonacci substitutions on {0, 1} N .

In [START_REF] Baraviera | Substreetutions and more on trees[END_REF] it was proved that the closure of F + 2 -orbit of the fixed point for some special substreetution H, X := {T ω (J), ω ∈ F + 2 }, is minimal and non-periodic, in the sense that it is not reduced to a periodic orbit. In other words, and following the terminology, it was proved that X is weakly aperiodic. We remind that the natural action of F + 2 is given by the two maps T a and T b which respectively send a binary (colored) tree A on its a-follower or b-follower.

There are several motivations to study substitutions on {0, 1} F + 2 . The principal one is a long work in progress that aims to export the thermodynamic formalism via transfer operator to higher dimensional group (or semi-group) action. One reason for that is to continue to better understand similitudes and differences between Ergodic or Statistical Mechanics viewpoints for Thermodynamic formalism. Statistical Mechanics viewpoint usually deals with Z d -action or even F + 2 -actions (see [START_REF] Gallavotti | Statistical mechanics[END_REF][START_REF] Rozikov | Gibbs measures on Cayley Trees[END_REF]). Ergodic viewpoint deals with transfer operators. For Z-actions it links the thermodynamic quantities (such as pressure, Gibbs measures, etc) to the spectral properties of that operator. This has never be done for Z d -actions (with d ≥ 2) and, this is probably due to the existence of the "natural" orientation in Z which is the key point to define the transfer operator. This natural direction fails to exist in Z d . For that reason authors were naturally led to study F + 2 -actions. Other works related to phase transitions and quasi-periodic systems (see [START_REF] Baraviera | The potential point of view for Renormalization[END_REF][START_REF] Bruin | Renormalization, thermodynamic formalism for quasi-crystals in subshifts[END_REF][START_REF] Bruin | Renormalization, freezing phase transition and Fibonacci quasicrystals, Annales Scientifiques de l[END_REF]) also led authors to prospect for substitutions adapted to F + 2 -actions, since their attractor are example of quasi-periodic systems.

Along the way, many other interesting questions arose, as by-products of the initial goal. For instance, a notion of Sturmian trees has been introduced and studied (see e.g. [START_REF] Kim | Quasi-Sturmian colorings on regular trees[END_REF]). We remind that for the Fibonacci substitution the attractor is a Sturmian shift. It was thus quite natural to inquire to get example of such trees generated by substreetutions.

The question of entropy is also of prime importance. Entropy measures the complexity of the system. For trees, the first natural question is to define the right normalization, since the increase is expected to be super exponential. Several notions of entropies with different normalizations have been defined in the literature (see [START_REF] Bufetov | Topological entropy of free semigroup actions and skew-product transformations[END_REF][START_REF] Petersen | Entropy on regular trees[END_REF][START_REF] Ban | Tree-shifts: the entropy of tree-shifts of finite type[END_REF]). We also point out that for usual N-actions, entropy is also related to the number of preimages, and this quantity is crucial to properly define the transfer operator.

In the present paper we continue the work in progress, advancing in the study of topological properties of the free semi-group action on the Jacaranda tree. We prove that the stabilizer is reduced to the empty word , which means that X is strongly aperiodic. Concerning complexity, we prove that the number of patches essentially increases linearly with respect to the length. This is one path in the good direction to check if J is Sturmian. As a by-product, we get that X has zero entropy whatever the definition we take.

1.2. Main results.

1.2.1. Aperiodicity. We remind that for some group G acting on some space X , g ∈ G is a stabilizer for x ∈ X if g.x = x. Definition 1.1. We say that a F + 2 -invariant set is strongly periodic if it is finite. We say that a F + 2 -invariant set is weakly periodic if the set of stabilizers is non-empty. If a F + 2 -invariant set is not strongly periodic then it is said to be weakly aperiodic. If it is not weakly periodic then it is said to be strongly aperiodic.

In [START_REF] Baraviera | Substreetutions and more on trees[END_REF] it is proved that X is weakly aperiodic. We prove here a stronger result:

Theorem A. X is strongly aperiodic.

Remark 1. We emphasize that being minimal does not prohibits the existence of A ∈ X and ω ∈ F + 2 , |ω| ≥ 1 such that T ω (A) = A. Hence being minimal and weakly aperiodic does not imply that X is strongly aperiodic.

Complexity and topological entropy.

Definition 1.2. A patch of size n ≥ 1 is a finite binary tree with n lines that appears in J. We denote by K n the set of patches of length n in X. Its cardinal is κ n .

For C ∈ K n , [C] denotes the set of A ∈ X starting as C.

We emphasize (see below for technical results on X) that for any

C ∈ K n [C] = B(A, 2 -n ) for any A in [C]. Theorem B. There exists 1 < C < +∞ such that for every n, n + 2 ≤ κ n ≤ Cn + 4.
This result has to be compared to the one for "classical" substitutions (see [START_REF] Pansiot | Complexité des facteurs des mots infinis engendrés par morphismes itérés[END_REF]). It is known that the equivalent p(n)

for κ n is either in O(n 2 ), O(n log n), O(n log log n), O(n) or O(1)
. However, we point out that that proof does not seem to be easily adaptable to substreetutions. It is also interesting to connect this result with the concept of quasi-Sturmian trees introduced in [START_REF] Kim | Quasi-Sturmian colorings on regular trees[END_REF]; those are the colored trees where κ n = n + c (in the particular case where c = 1 the trees are called simply Sturmian) for n ≥ N 0 .

Hence, a natural question is to inquire if in our case an equality κ n = n + c holds, at least for large values of n.

As said above entropy measures the complexity of the system. It matters with how κ n increases. For trees, the main issue, at least for general set of trees, is to find the right normalization. Going in that direction, Petersen and Salama define the entropy for a colored binary tree (see [START_REF] Petersen | Entropy on regular trees[END_REF], ) as

h P S := lim sup n→+∞ 1 2 n log κ n .
This makes sense since the normalization factor 2 2 n is the cardinality of {0, 1} 2 n and is approximatively the number of patches of length n in {0, 1} F + 2 .

In another direction Ban and Chang define entropy as h BC := lim sup n→+∞ 1 n log log κ n (see [START_REF] Ban | Tree-shifts: the entropy of tree-shifts of finite type[END_REF]).

An immediate consequence of Theorem B is

Corollary C. The Petersen-Salama and Ban-Chang entropies for J are equal to zero.

1.2.3. Entropy for a skew-product extension of X. In order to define an entropy for a compact set X of trees, Bufetov introduced an idea whose details are in section 4; he also related this entropy to the usual topological entropy as follows (in our settings).

Let us set Y := {a, b} N × X and consider the skew-product F : Y → Y defined as

(ω, x) ∈ {a, b} N × X → F (ω, x) = (σ(ω), T ω0 (x)),
where σ is the usual unilateral shift on {a, b} N . Then, Bufetov showed equality

h B (T ) := h top (F) -log 2.
In our setting we set X = X. Then we get:

Theorem D. The map F has topological entropy equal to log 2.

Hence, Bufetov's entropy is zero for the action of the free semi-group on the Jacaranda tree.

We finish this subsection with an open question :

Question 1. Is (Y, F ) an expansive dynamical system ?

We remind that expansiveness is a sufficient condition to get upper semi-continuity for the metric entropy. Our next step will be to check how invariant measures for F may give better descriptions of X or J. For that purpose, studying thermodynamic formalism for F seems a good way. Hence proving upper semi-continuity would be helpful.

We remind that expansiveness means that for some ε > 0, if d Y (F n (ω, A), F n (ω , A )) < ε for every n ≥ 0, then (ω, A) = (ω , A ). It is immediate that d Y (F n (ω, A), F n (ω , A )) < 1 for every n implies ω = ω . On the other hand, d Y (F n (ω, A), F n (ω, A )) < ε for every n only means that A and A do coincide along the enlarged path ω. It is however not clear that this yields A = A .

Furthermore, for any A in X, sites along the path b ∞ are all equal to 0 except (may be) the root. This holds because any even line in J is a concatenation of 10 and any even line is a concatenation of 0010 and 0000. Similarly, for every even tree, the word along the path (ab) ∞ = ababab . . . is ⊗(10) ∞ , where ⊗ is the root of the considered tree. For odd tree it is ⊗(01) ∞ .

This shows that many trees do coincide along the two extremal paths but are different. Hence, some results go in the direction that (Y, F ) is expansive, some others go int eh opposite direction. This also shows that proving expansiveness is not immediate, nor non-expansiveness. 1.3. Plan of the paper. In Section 2 we remind some facts on substreetutions and the Jacaranda tree and we prove Theorem A. Section 3 is devoted to give estimates for κ n . This yields the proofs of Theorems B and D.

2. Reminders on Substreetutions and proof that J is strongly aperiodic . 2.1. Reminders on Substreetutions. The set of colored binary trees we consider is {0, 1} F +2 . All the trees we shal consider are these ones, and we will just refer to them as trees. If A is a tree and ω is in F + 2 , A ω is the digit at position ω. If A is a tree T a (A) is the new tree obtain when considering the new root at site a and thus forgetting the old root and the other part of the tree. Similarly T b (A) is the subtree with root at position b.

The distance between two trees A and B is 2 -N (A,B) where N (A, B) is the minimal integer n such that A ω = B ω and |ω| = n.

In other words, d(A, B) = 2 -n means that A and B have different root if n = 0, and A ω and B ω do coincide for every ω, such that |ω| ≤ n and for at least one ω with |ω| = n, one of the followers of A ω is different to the same follower for B ω .

Note that the space of trees A F + 2 is compact (for the metric we introduced) as a product of compact spaces. The subset of trees with root equal to 0 (or 1) is also compact as a closed set included into a compact set.

If A is a binary tree, and ω = ω 0 . . . ω n is in

F + 2 , we set T ω (A) = T ωn • . . . • T ω1 • T ω0 (A)
. This corresponds to consider the substree in A with root equal to the site ω in A.

Colored binary trees and substreetutions.

A substreetution1 on trees is a map H on the set of configurations defined by concatenation as follows:

(1) H maps each site to a truple (actually a root with two followers), the value depending only on the value of the digit at the site. See Figure 1 with the box with dashline. (2) H connects images of subtrees (followers) as indicated on Figure 1, with I, J, K, L ∈ {H(A), H(B)}. The order word IJKL is called the grammar of the substreetution.

The substreetution is said to be marked if

H(0) = i and H(1) = 1-i , i = 0, 1. ⊗ B A ⊗ L K ⊕ J I Figure 1. A market substreetution 2.1.3.
The Jacaranda tree. The substreetution H we consider here is the one given by 0 → 0 1 0 and 1 → 1 1 0 , equipped with the grammar BBAB.

There exists a unique fixed point J with root 0. It is called the Jacaranda tree. The closure of its orbit is a minimal dynamical system X and is not periodic. There also exists a unique fixed point J with root 1. It coincides with J except at the root.

More precisely we have for ⊗ = 0, 1: A line standing at an odd level (root is at line 0) in J is a concatenation of 10's. A line at level 2 n (2m + 1) is a concatenation of χ n [START_REF] Petersen | Entropy on regular trees[END_REF].

H         ⊗ A B         = ⊗ 1 H(B) H(B) 0 H(A) H(B) ,
If A belongs to

X := {T ω (J), ω ∈ F + 2 }, there exists ω k with |ω k | → +∞ as k → +∞ such that A = lim k→+∞ T ω k (J).
Then it turns out that there exists a unique n such that for any sufficiently big k,

|ω k | = 2 n (2m k + 1).
If n = 0 we say that A is odd (or of odd-type). If n ≥ 1 we that that A is even, and more precisely we say that A is of 2 n -type. Odd and even trees form a partition, and more generally trees of type 2 n with n ≥ 1 form a partition of even trees.

If A is of 2 n -type with n ≥ 1, there exists a unique B such that H(B) = A. Furthermore, B is of 2 n-1 -type. The map A → B is called the source map and we write B = s(A).

Note that the source can actually be defined on F + 2 , since for every ω ∈ F + 2 there exists a unique s(ω) with length |ω|/2 such that

T ω • H = H • T s(ω)
2.2. Proof of Theorem A. Assume that there exists A ∈ X and ω ∈ F + 2 , |ω| ≥ 1 such that A = T ω (A). Note that |ω| must be an even integer since T ω (A) must have the same parity than A (either odd or even).

Claim 1 (Claim Cutting). There exist

A ∈ X and ω ∈ F + 2 with |ω | = |ω| 2 such that T ω (A ) = A .
Proof of the claim. If A is even, then we set A := s(A) and there exists ω

∈ F + 2 with |ω | = |ω| 2 such that H(A ) = A = T ω (A) = T ω • H(A ) = H(T ω (A )). If A is odd, set ω = ω 0 . . . ω n , ω := ω 1 . . . ω n ω 0 . Then T ω0 (A) = T ω0 T ω (A) = T ω (T ω0 (A)).
Furthermore, T ω0 (A) is even. Hence we are sent to the previous point.

Applying the claim, we get that |ω | must be an even integer. There exists some k and m such that |ω| = 2 k (2m + 1). Hence, applying k times Claim 1 we arrive to a contradiction: there exists B ∈ X and ω with odd length such that B = T ω (B). Proof. By Lemma 3.1 the sequence is non-decreasing. If for some n 0 κ n0+1 = κ n0 , then the sequence is stationary (Lemma 3.2). This yields that for any C with length n 0 , there exists a unique element in X starting as C. Let us denote it by A(C). This yields that the graph with vertices all the A(C), C ∈ K n0 and arrows defined by images by T a and T b , is closed. Hence J is strongly pre-periodic, which is false.

An immediate corollary is:

Corollary 3.4. For any n, κ n ≥ n + 2. Hence lim inf n→+∞ κ n n ≥ 1.
3.2. Bound from above for κ n and end of the proof of Theorem B.

3.2.1.

An inequality sastified by (κ n ).

Proposition 3.5. For any n, κ 2n ≤ κ n + κ n+1 .

Proof. Inequality is obvious if n = 1. Let n ≥ 2 be in N. Let C be an element in K 2n and let A ∈ X be in [C]. We know first four lines for A, hence we can determine if it is even or odd. For simplicity we denote by K n,o , K n,e the set of patches coinciding with odd or even trees. Their cardinality is respectively denoted by κ n,o and κ n,e .

If A is even, then we set B := s(A). The first 2n-lines in A are entirely defined by the first n lines in B. Furthermore this definition is one-to-one. This means that the number of patches C in K 2n of even type is equal to κ n , hence κ 2n,e = κ n . 3.2.3. Bound from above for κ n . We remind that any even line in J is a concatenation of 0010 or 0000. Any odd line is a concatenation of 10. This yields that only the configurations Note that max(c, c ) ≤ is equivalent to c ≤ and c ≤ . Pick := 2 -p . We remind that k n denotes the cardinality of the set K n of patches of length n. Because (X, F + 2 ) is expanding, k n+p = #K n+p is the maximal cardinality for an (n, )-separated set in X. Similarly, (Σ 2 , σ) is expanding and 2 n+p is the maximal cardinality for a (n, )-separated set in Σ. This yields (for sufficiently large n) r(n, ) ≤ 2 n+p k n+p ≤ 2 n+p C(n + p) where we use the bound from above for κ n . This yields h top (F ) ≤ log 2.

2. 1 . 1 .

 11 Binay colored trees and F + 2 -action. F + 2 is the free monoid with two generators, a and b. It is the collection of finite words in a and b. The empty word is denoted by e. For ω ∈ F + 2 , |ω| is its length and denotes the number of letter that compose ω. By definition |e| = 0.

2. 1 . 4 .

 14 Types, source map. The map χ on words in {0, 2} 2 N is defined by χ(10) = 0010 and χ(CD) = χ(D)χ(D)χ(C)χ(D) if C and D are in {0, 1} 2 n (for any n but the same n).

3. Estimations for κ n 3 . 1 .Lemma 3 . 2 .

 3132 Bound from below for κ n and beginning of proof of Theorem B. First, we state two lemmas that extend known-results for classical substitutions.Lemma 3.1. κ n+1 ≥ κ n . Proof. Each element C in K n has a "continuation" ‹ C to be an element in K n+1 . Hence, two different C and C in K n yields two different ‹ C and ‹ C in K n+1. This yields κ n+1 ≥ κ n . Assume that κ n0+1 = κ n0 for some n 0 . Then, for every n ≥ n 0 , κ n = κ n0 .Proof. Each C ∈ K n0 admits a unique continuation (on the bottom) to define an element ‹ C in K n0 . This holds because otherwise, we would get κ n0+1 > k n0 . Set images T a ( ‹ C) and T b ( ‹ C) (see Fig.2) define two elements of K n , respectively denoted by C and C . C unique continuation for C 0 unique continuation for C 00

Figure 2 .Proposition 3 . 3 .

 233 Figure 2. Eventually stationarity for κ n

2 κsup n→+∞ 1 n 4 . 1 .

 2141 in J. Hence κ 2 = 4. Set α = 4 and β = κ 3 . Let us consider the sequences (u n ) = (κ n ) and (v n ) as above. Lemma 3.6 yields for all n ≥ 2n ≤ (β + 3)(n -1) + 4, κ 2n+1 ≤ κ 2n+2 -1 = (β + 3)n + 3.4. Bufetov entropyFirst, we recall Bufetov's definition of entropy in our settings. We write ψ ≤ ω when there exists some η such that ω = ηψ and define the dynamical distance d ω on X byd ω (A, B) = max ψ≤ω d(T ψ (A), T ψ (B)).For > 0, an (ω, , T a , T b )-separated set is a set K ⊂ X such that for any pair A, B ∈ K, with A = B, d ω (A, B) ≥ . The maximal cardinality of an (ω, , T a , T b )-separated set is then denoted by N (ω, , T a , T b ). Now takeN (n, , T a , T b ) = 1 2 n |ω|=n N (ω, , T a , T b )The Bufetov entropy of the action is defined ash B (T ) = lim →0 lim log(N (n, , T a , T b )).Setting Y := {a, b} N × X,F : (ω, A) ∈ {a, b} N × X → (σ(ω), T ω0 (A))where σ is the usual shift, andd Y ((ω, A); (ω , A )) = max(d Σ (ω, ω ); d(A, A )), Bufetov proved in [6] equality h top (F ) = h B (T ) + log 2.Proof of Theorem D. By definition (see[START_REF] Walters | An Introduction to Ergodic Theory[END_REF]), n, ) is the maximal cardinality for a (n, )-separated set of points (for the metric d Y ).

Actually this is a constant length

substitution.

If A is of odd type, we consider any preimage A of A. It belong to some (unique) [C ], with C ∈ K 2n+2 , and is even. Two different such A's belonging to different [C ]'s yield two different A 's. This yields that κ 2n,o is lower or equal to κ 2n+2,e = κ n+1 .

3.2.2. Special sequences satisfying that inequality. We consider two numerical sequences (u n ) and (v n ) satisfying [START_REF] Ban | Tree-shifts: the entropy of tree-shifts of finite type[END_REF]

Proof. The proof is done by induction. Inequality holds for n = 2 and n = 3. Let us assume it holds for every k ≤ n and let us prove it also holds for every k ≤ n + 1.

This yields

, where the last inequality uses the induction hypothesis.

We can thus apply he induction hypothesis to get

Lemma 3.7. The sequence v n satisfies for every n ≥ 2,

Proof. A simple computation shows that this holds up to v 22 -v 20 . We thus do the proof by induction. Assume n ≥ 4 is such that for any p ≤ n, v 2p+2 -v 2p is either equal to β or β + α -1.

Hence we have

If n is even, then 5 ≤ n + 1 ≤ n + 3 are odd and equalities

If n is odd, 5 ≤ n + 1 ≤ n + 3 are even and n + 1 ≤ 2n since n ≥ 4. This also yields that v 2(n+1)+2 -v 2(n+1) is either equal to β or to β + α -1. Lemma 3.8 yields that for every n, v 2n ≤ (β + α -1)(n -1) + α.

On the other hand, for any α 1 . . . α n ∈ {a, b} n any maximal (n, )-separated set in Y must contain a point (ω, A) with ω 0 . . . ω n-1 = α 1 . . . α n . Hence r(n, ) ≥ 2 n+p . This yields h top (F ) ≥ log 2. Hence, h top (F ) = log 2 and h B (T ) = 0 as claimed.


Ahmad Darwiche
email: ahmad.darwiche@univ-littoral.fr

Dominique Schneider
email: dominique.schneider@univ-littoral.fr

Lmpa

Refinement of Gál-Koksma's theorems and applications

Keywords:

In this paper, we investigate the strong laws of large numbers with general normalizing sequences for arbitrary dependent sequences whose partial sums satisfy certain conditions on the p-th moment. To do it, we adapt results due to Móricz concerning moment inequalities. We also give applications that were difficult to deal with previously. Our results extend and improve some well-known corresponding ones.

Introduction

Kolmogorov's strong law of large numbers [START_REF] Nikolaevitch | Sur la loi forte des grands nombres[END_REF] is one of the most important results in probability limit theorems. This result has been generalized by to obtain rates of convergence. Specifically, given a centered sequence of independent and identically distributed (i.i.d.) random variables {X k , k ≥ 1} and S n , the associated partial sum of rank n:

S n = X 1 + • • • + X n , for 1 ≤ p < 2, E|X 1 | p < ∞ if
and only if n -1/p S n -→ 0 almost surely (a.s.). It is worth noting that the last equivalence constitutes Kolmogorov's strong law of large numbers in the case p = 1 and that of Marcinkiewicz-Zygmund in the case 1 < p < 2. Many studies have been conducted concerning the rates of convergence in the Marcinkiewicz-Zygmund's strong law of large numbers, and there is a vast body of literature on this topic.

It is natural to extend the idea behind the Kolmogorov-Marcinkiewicz-Zygmund result to dependent random sequences. However, this extension imposes conditions on the p-th moment of S n . In this context, we refer to several studies such as [START_REF] Chobanyan | Strong law of large numbers under a general moment condition[END_REF][START_REF] Cohen | On strong laws of large numbers with rates[END_REF][START_REF] Cohen | Laws of large numbers with rates and the one-sided ergodic hilbert transform[END_REF][START_REF] Gál | Sur l'ordre de grandeur des fonctions sommables[END_REF][START_REF] Li | A characterization of a new type of strong law of large numbers[END_REF][START_REF] Nane | A strong law of large numbers with applications to self-similar stable processes[END_REF][START_REF] Nane | Strong laws of large numbers for arrays of random variables and stable random fields[END_REF][START_REF] Weber | Uniform Bounds under Increment Conditions[END_REF][START_REF] Weber | Dynamical systems and processes[END_REF].

Let p ≥ 1 be a constant and let {X k , k ≥ 1} ⊂ L p (X, A, µ) be a sequence of random variables. We say that {X k , k ≥ 1} satisfies the strong law of large numbers with respect 1 to a non-decreasing function ϕ : R + → R + such that ϕ(x) ↑ ∞ as x → ∞, if lim

N →∞ 1 ϕ(N ) N k=1
X k = 0 a.s.. [START_REF] Gál | Sur l'ordre de grandeur des fonctions sommables[END_REF] derived weak conditions of the form

Gál-Koksma

E n k=m+1 X k p ≤ d(m, n) for any m, n ∈ N with m < n, (1)
for some function d : N × N → R + , to ensure that the above limit holds. Weber [START_REF] Weber | Uniform Bounds under Increment Conditions[END_REF][START_REF] Weber | Dynamical systems and processes[END_REF] recently established a strong law of large numbers for random variables satisfying increment conditions of the type considered in Gál-Koksma theorems. In this paper, we aim to establish a more general strong law of large numbers by providing conditions of the type (1) that allow us to extend Gál-Koksma and Weber's results. Our approach is based on adapting results from Móricz's work, and it enables us to obtain new results in several cases. One of the strengths of our approach is that our proof is much simpler than the existing ones.

Before presenting our main result, let us first recall the following definition. A function d(m, n) is said to be super-additive if, for any j ∈ [m, n], we have d(m, j) + d(j, n) ≤ d(m, n). It is important to note that if d(m, n) is super-additive and η(m, n) is a nondecreasing function with respect to n and a non-increasing function with respect to m, then d(m, n)η(m, n) is also super-additive. Throughout this paper, the symbol C denotes a positive constant which may vary from one appearance to another. With this definition in mind, we can now proceed to state our main theorem. Theorem 1. Let p ≥ 1. Consider a sequence of random variables {X k , k ≥ 1} ⊂ L p (X, A, µ). Let Ψ : R + → R + be a non-decreasing function satisfying Ψ(2x) ≤ CΨ(x). Assume that, there exists a constant η ≥ 0 such that the function Ψ(x) x 1+η is non-decreasing and for any m, n ∈ N with m < n, we have

E n k=m+1 X k p ≤ Ψ(d(m, n)).
(2)

1. If one of the following cases holds:

(a) η > 0, d(m, n) is a super-additive function and τ > 1; (b) η = 0, there exists α > 1 such that d 1 α (m, n) is super-additive and τ > 1; (c) η = 0, d(m, n) is super-additive, there exists σ > 0 such that n σ = O (d(0, n))
and τ > p + 1,

then we have lim N →∞ 1 (Ψ(d(0, N )) log τ (d(0, N ))) 1/p N k=1 X k = 0 a.s. and sup N ≥1 N k=1 X k (Ψ(d(0,N )) log τ (d(0,N ))) 1/p ∈ L p (µ).
2. If one of the preceding cases, namely a, b, or c without the condition that there exists

σ > 0 such that n σ = O (d(0, n)), holds and if d(0, 2n) ≤ Cd(0, n), then lim N →∞ 1 (Ψ(d(0, N )) log τ (N )) 1/p N k=1 X k = 0 a.s. and sup N ≥1 N k=1 X k (Ψ(d(0,N )) log τ (N )) 1/p ∈ L p (µ).
Theorem 1 extends the results of Weber [START_REF] Weber | Uniform Bounds under Increment Conditions[END_REF][START_REF] Weber | Dynamical systems and processes[END_REF] and, as a result, extends the wellknown Gál-Koksma theorems [START_REF] Gál | Sur l'ordre de grandeur des fonctions sommables[END_REF]. More details on this will be provided in Section 2 below. Additionally, this theorem can be used to improve upon the ideas presented in Theorem 1.1. of [START_REF] Nane | Strong laws of large numbers for arrays of random variables and stable random fields[END_REF] in a one-dimensional setting (see also Theorem 1.1. in [START_REF] Nane | A strong law of large numbers with applications to self-similar stable processes[END_REF] and Theorem 1. in [START_REF] Chobanyan | Strong law of large numbers under a general moment condition[END_REF]). The paper by Nane et al. [START_REF] Nane | Strong laws of large numbers for arrays of random variables and stable random fields[END_REF] provides strong laws of large numbers with normalizations that satisfy more conditions than ours.

The next corollary considers the scenario where only d(m, n) is present. It is a direct application of the previous theorem with η = 0 and Ψ is the identity function. X k = 0 a.s..

Corollary 1. Let p ≥ 1. Consider a sequence of random variables {X k , k ≥ 1} ⊂ L p (X, A, µ) and suppose that E n k=m+1 X k p ≤ d(m, n), for any m, n ∈ N with m < n.

If one of the preceding cases, namely a or b without the condition that there exists

σ > 0 such that n σ = O (d(0, n)), holds and if d(0, 2n) ≤ Cd(0, n), then lim N →∞ 1 (d(0, N ) log τ (N )) 1/p N k=1 X k = 0 a.s..
As an application of Theorem 1, we are able to give an example of function ϕ such that the series k≥1 X k ϕ(k) converges. In particular, we establish the following corollary. Corollary 2. Suppose that

E n k=m+1 X k p ≤ (n -m) β for any m, n ∈ N with m < n. If β = 1 and τ > p + 1, then k>1 X k (k log τ (k)) 1/p converges a.s.. If 1 < β < p and τ > 1, then k>1 X k (k β log τ (k)) 1/p converges a.s..
This paper also provides strong laws of large numbers for sequences of non-negative random variables. Two notable strands of research in this literature are: (i) the works of Etemadi [START_REF] Etemadi | On the laws of large numbers for nonnegative random variables[END_REF] and Csörgő, Tandori, and Totik [START_REF] Csörgő | On the strong law of large numbers for pairwise independent random variables[END_REF], and (ii) the Petrov-type approach, inspired by Petrov [START_REF] Vladimirovich | On the strong law of large numbers[END_REF], which has been studied by several authors such as Korchevsky [START_REF] Korchevsky | A generalization of the petrov strong law of large numbers[END_REF], Kuczmaszewska [START_REF] Kuczmaszewska | Convergence rate in the petrov slln for dependent random variables[END_REF], and Petrov [START_REF] Vladimirovich | On the strong law of large numbers for nonnegative random variables[END_REF]. Chen and Sung [START_REF] Chen | A strong law of large numbers for nonnegative random variables and applications[END_REF] established a theorem that unifies both strands. Specifically, they demonstrated that if {Y k , k ≥ 1} ⊂ L p (X, A, µ), p ≥ 1, is a sequence of non-negative random variables and (b k ) k≥1 is a non-decreasing unbounded sequence of positive numbers such that

sup n≥1 n k=1 EY k b n < ∞, ∃ δ n ≥ 0 : E n k=1 (Y k -EY k ) p ≤ n k=1 δ k and k≥1 δ k b p k < ∞, then we have lim N →∞ 1 b N N k=1 (Y k -EY k ) = 0 a.s..
This paper aims to provide additional contributions to this topic. We can prove the following theorem.

Theorem 2. Let p ≥ 1. Let {Y k , k ≥ 1} ⊂ L p (X, A, µ) be a sequence of non-negative random variables. Suppose that, for any m < n,

E n k=m+1 (Y k -EY k ) p ≤ d(m, n) and EY n ≤ Cd 1 p (0, n)d(n -1, n),
where d(m, n) is a super-additive function. Then, for any τ > p + 1, we have

lim N →∞ 1 (d(0, N ) log τ (d(0, N ))) 1/p N k=1 (Y k -EY k ) = 0 a.s..
Notice that this theorem can also be used for some sequences of non-positive random variables. For example, consider a sequence of random variables {X k , k ≥ 1} taking values in {-1, 1} such that P(X n = 1) = p n and p n ≤ Cd

1 p (0, n)d(n -1, n). Then, we have E n k=m+1 (X k -EX k ) p = E n k=m+1 (Y k -EY k ) p , where Y k = X k + 1 for any k ≥ 1.
Moreover, note that the result of the theorem remains true even if the condition

EY n ≤ Cd 1 p (0, n)d(n -1, n) is replaced by the condition sup n≥1 n k=1 EY k d 1/p (0,n) < ∞.
The rest of this paper is organized as follows. In Section 2, we compare our results with those of Gál-Koksma and Weber. In Section 3, we recall some known results that will be used in the proofs of our main theorems and then proceed to prove them. One of the main analytical tools used in the proofs is Móricz's work. In the last section, we provide several examples illustrating our main results.

Extension of Gál-Koksma's and Weber's theorems

In this section, we will show how our theorem extends the results of Gál-Koksma [START_REF] Gál | Sur l'ordre de grandeur des fonctions sommables[END_REF] and Weber [START_REF] Weber | Uniform Bounds under Increment Conditions[END_REF][START_REF] Weber | Dynamical systems and processes[END_REF]. Let {X k , k ≥ 1} be a sequence of random variables with probability space (X, A, µ) and let Ψ : R + → R + be a non-decreasing function such that Ψ(2x) ≤ CΨ(x). Assume that there exists a constant η ≥ 0 such that Ψ(x) x 1+η is non-decreasing. Let (a k ) k∈N be a sequence of positive real numbers, and define A(n) = n k=1 a k . Now, assume that the condition (2) holds with:

d(m, n) = n k=m+1 a k .
Then several theorems of Gál-Koksma and Weber can be seen as particular cases of our Theorem 1. More precisely, let ϵ > 0, and depending on the value of a k , we have the following:

Case a k > C. Applying Theorem 1, we have :

If η > 0, lim N →∞ N k=1 X k Ψ(A(N )) log 1+ϵ A(N ))
1/p = 0 a.s. (Theorem 8.4.1 [START_REF] Weber | Dynamical systems and processes[END_REF]; η > 0).

If η = 0, lim N →∞ N k=1 X k Ψ(A(N )) log p+1+ϵ (A(N ))
1/p = 0 a.s. (Theorem 8.4.1 [START_REF] Weber | Dynamical systems and processes[END_REF]; η = 0).

Case a k = 1. This case covers two theorems of [START_REF] Gál | Sur l'ordre de grandeur des fonctions sommables[END_REF]. Indeed, when a k = 1, we have

A(n)=n. Then it is clear that if η = 0, lim N →∞ 1 Ψ(N ) log p+1+ϵ (N ) 1/p N k=1 X k = 0 a.s. (Theorem 3 [9]). If η > 0, lim N →∞ 1 Ψ(N ) log 1+ϵ (N ) 1/p N k=1 X k = 0 a.s. (Theorem 5 [9]). Moreover, let s > 0 be such that p -s > 1, then if Ψ(x) = x p-s , we obtain lim N →∞ 1 N p-s log 1+ϵ (N ) 1/p N k=1 X k = 0 a.s.
which improves Theorem 7 in [START_REF] Gál | Sur l'ordre de grandeur des fonctions sommables[END_REF] in the case where η(x) = 1

x s .

Case a k = 1 k . This case allows us to establish a new result which apparently cannot be obtained by applying Weber's work. Since we have

A(n) ∼ log(n), then if η > 0, lim N →∞ 1 Ψ(log(N )) log 1+ϵ (log(N )) 1/p N k=1 X k = 0 a.s. and, since log(2n) ≤ 2 log(n) for n > 1, then if η = 0, lim N →∞ 1 Ψ(log(N )) log p+1+ϵ (N ) 1/p N k=1 X k = 0 a.s..

Proofs of the main results

Additivity and maximal inequalities

To prove the main results, we need the following lemmas.

Lemma 1. Let Ψ : R + → R + be a non-decreasing function. Suppose there exists a constant η ≥ 0 such that Ψ(x) x 1+η is non-decreasing. Then there exists a constant λ ≥ 1 such that

Ψ 1 λ (x) + Ψ 1 λ (y) ≤ Ψ 1 λ (x + y)
for all x, y ∈ R + . In particularly, if η = 0 and if there exists α > 1 such that x

1 α +y 1 α ≤ z 1 α , z ∈ R + , then Ψ 1 α (x) + Ψ 1 α (y) ≤ Ψ 1 α (z).
Proof. For all x, y ∈ R + , we have

Ψ 1 λ (x) + Ψ 1 λ (y) ≤ (x 1+η ) 1 λ Ψ(x + y) (x + y) 1+η 1 λ + (y 1+η ) 1 λ Ψ(x + y) (x + y) 1+η 1 λ ≤ x 1+η λ + y 1+η λ Ψ(x + y) (x + y) 1+η 1 λ ≤ (x + y) 1+η λ Ψ(x + y) (x + y) 1+η 1 λ = Ψ 1 λ (x + y)
where the last inequality holds if we take 1 ≤ λ ≤ 1 + η. Moreover, if η = 0 and if there exists α > 1 such that x

1 α + y 1 α ≤ z 1 α , we have Ψ 1 α (x) + Ψ 1 α (y) ≤ x 1 α Ψ(z) z 1 α + (y) 1 α Ψ(z) z 1 α ≤ x 1 α + y 1 α Ψ(z) z 1 α ≤ z 1 α Ψ(z) z 1 α = Ψ 1 α (z).
The following results are provided by Móricz. A direct consequence of Theorems 1 in [START_REF] Móricz | Moment inequalities and the strong laws of large numbers[END_REF] is the following lemma. Lemma 2. Let p ≥ 1 and let {X k , k ≥ 1} be a sequence of random variables on a probability space (X, A, P). Assume that there exist λ > 1 and a non-negative function

g : N × N -→ R + , such that for any m, n ∈ N with m < n, E n k=m+1 X k p ≤ Cg λ (m, n), where g(m, n) is a super-additive function. Then E n sup j=m+1 j k=m+1 X k p ≤ C(λ)g λ (m, n),
where C(λ) is a constant only depending on λ.

We are now dealing with the case where λ = 1. By adapting the result of Theorem 3 in [START_REF] Móricz | Moment inequalities and the strong laws of large numbers[END_REF], we obtain the following lemma. Before presenting it, let us define the following sequences. Let (λ(n)) n∈N be a positive and non-decreasing sequence, and define (Λ(n)) n∈N as follows:

Λ(1) = 1 and Λ(n) = λ(m) + Λ(m -1), n ≥ 2,
where m denotes the integer part of n+2 2 . For instance

, if λ ≡ 1, then Λ(n) = log 2 (2n) because 1 + log 2 (2(m -1)) ≤ log 2 (2n). Lemma 3. Let {X k , k ≥ 1}
be a sequence of random variables on a probability space (X, A, P). Suppose that

E |X b+n -X b | p ≤ λ p (n)g(b, b + n)
where g(m, n) is a super-additive function. Then

E sup 1≤k≤n |X b+k -X b | p ≤ Λ p (n)g(b, b + n). Proof. Let n > 1. If m ≤ k ≤ n, we have |X b+k -X b | ≤ |X b+k -X b+m | + |X b+m -X b | ≤ sup m≤k≤n |X b+k -X b+m | + |X b+m -X b | . If k < m, we have |X b+k -X b | ≤ sup 1≤k≤m-1 |X b+k -X b | . By Minkowski's inequality E sup 1≤k≤n |X b+k -X b | p 1/p ≤ (E |X b+m -X b | p ) 1/p (3)
+ E sup 1≤k≤m-1 |X b+k -X b | p + E sup m≤k≤n |X b+k -X b+m | p 1/p .
Assuming that the conclusion of the lemma holds for k < n and for any b ≥ 0. Then, by the choice of m, we have

E sup 1≤k≤m-1 |X b+k -X b | p ≤ Λ p (m -1)g(b, b + m -1)
and thus

E sup m≤k≤n |X b+k -X b+m | p = E sup 1≤k≤n-m |X b+m+k -X b+m | p ≤ Λ p (n -m)g(b + m, b + n).
Since n -m ≤ m -1 and d(m, n) is super-additive, we have that the second term of the right-hand side of Equation ( 3) is

E sup 1≤k≤m-1 |X b+k -X b | p + E sup m≤k≤n |X b+k -X b+m | p ( 4
)
≤ Λ p (m -1) (g(b, b + m) + g(b + m, b + n)) ≤ Λ p (m -1)g(b, b + n).
Now by assumption, the first term is

E |X b+m -X b | p ≤ λ p (m)g(b, b + m). (5)
The proof follows directly by using ( 3), (4), and ( 5) and performing recurrence over n.

Proof of Theorem 1

Firstly, let's consider that 2 ψ(n) ≤ Cd(0, n) and

ψ(n) n ↑ ∞ as n → ∞. Since E N k=1 X k p ≤ Ψ(d(0, N )), we can derive that E N k=1 X k (Ψ(d(0, N )) log τ (d(0, N ))) 1/p p ≤ C 1 log τ (d(0, N )) ≤ C 1 n τ .
Summing over n with τ > 1, by Beppo Levi's theorem, we can clearly obtain the result of the first part of the theorem.

Secondly, we consider that d(0, n) ≤ C2 n . For any j ∈ N * , we have

{d(0, n); n ∈ N * } ∩ [2 j , 2 j+1 ] ̸ = ∅.
We denote by N j the smallest integer N such that d(0, N ) belongs to [2 j , 2 j+1 ]. In other words, we write

N j = inf{N ∈ N * : d(0, N ) ∈ [2 j , 2 j+1 ]}.
To provide proof, we write

N k=1 X k (Ψ(d(0, N )) log τ (d(0, N ))) 1/p ≤ Nj k=1 X k (Ψ(d(0, N j )) log τ (d(0, N j ))) 1/p (6) + sup Nj <N ≤Nj+1 N k=Nj +1 X k (Ψ(d(0, N j )) log τ (d(0, N j ))) 1/p .
The proof is divided into 6 steps. In Step 1, we show that the first term of the righthand side of Equation ( 6) converges to zero almost surely, which is a common step for all cases. From Step 2 to Step 4, we demonstrate that the second term converges to zero almost surely in all cases of the first part of the theorem. Step 5 is dedicated to the second part. Finally, Step 6 is performed to prove the maximal inequality.

Step 1. First, since

E n k=m+1 X k p ≤ Ψ(d(m, n)) for m < n, we observe that E Nj k=1 X k (Ψ(d(0, N j )) log τ (d(0, N j ))) 1/p p ≤ Ψ((d(0, N j )) Ψ(d(0, N j )) log τ (d(0, N j )) ≤ C 1 j τ .
With τ > 1 in all cases of the theorem, this implies that the last quantity is a term of a convergent series. By Beppo Levi's theorem

lim j→∞ Nj k=1 X k (Ψ(d(0, N j )) log τ (d(0, N j ))) 1/p = 0 a.s.. ( 7
)
Step 2. To control the second term on the right-hand side of ( 6), we can write for any

n, m ∈ [N j , N j+1 ] with m < n, E n k=m+1 X k p ≤ Ψ(d(m, n)). (8)
Moreover, if there exists η > 0 such that Ψ(x) x 1+η is non-decreasing, then, by Lemma 1, we have Ψ 1 λ (d(m, n)) is super-additive for some λ > 1. We can now apply Lemma 2 to obtain

E sup Nj <N ≤Nj+1 N k=Nj +1 X k (Ψ(d(0, N j )) log τ (d(0, N j ))) 1/p p ≤ Ψ(d(N j , N j+1 )) Ψ(d(0, N j )) log τ (d(0, N j )) ≤ Ψ(d(0, N j+1 )) Ψ(d(0, N j )) log τ (d(0, N j )) ≤ C 1 j τ .
The last line follows from the fact that d(0, N j ) belongs to [2 j , 2 j+1 ], d(0, N j+1 ) belongs to [2 j+1 , 2 j+2 ] and Ψ(2x) ≤ CΨ(x) for any x ∈ R + . Now, by summing over j and using the Beppo Levi's theorem, we obtain

lim j→∞ sup Nj <N ≤Nj+1 N k=Nj +1 X k (Ψ(d(0, N j )) log τ (d(0, N j ))) 1/p = 0 a.s.. (9)
This, together with [START_REF] Csörgő | On the strong law of large numbers for pairwise independent random variables[END_REF], concludes the proof the first part of the theorem in case a.

Step 3. By Lemma 1, if there exists α > 1 such that d

1 α (m, n) is super-additive then Ψ 1 α (d(m, n))
is also super-additive. Therefore, if we follow the same procedure as in Step 2, we can conclude that

lim j→∞ sup Nj <N ≤Nj+1 N k=Nj +1 X k (Ψ(d(0, N j )) log τ (d(0, N j )))
1/p = 0 a.s.. This, together with [START_REF] Csörgő | On the strong law of large numbers for pairwise independent random variables[END_REF], concludes the proof the first part of the theorem in case b.

Step 4. We will now begin the proof in case c. Since d(m, n) is assumed to be a super-additive function, then Ψ(d(m, n)) is also super-additive. Applying now Lemma 3 to equation (8) yields,

E sup Nj <N ≤Nj+1 N k=Nj +1 X k (Ψ(d(0, N j )) log τ (d(0, N j ))) 1/p p ≤ log p (2(N j+1 -N j )) Ψ(d(N j , N j+1 )) Ψ(d(0, N j )) log τ (d(0, N j )) ≤ C log p (2(N j+1 -N j )) j τ ,
where the last inequality follows from the fact that d(0, N j ) belongs to [2 j , 2 j+1 ], d(0, N j+1 ) belongs to [2 j+1 , 2 j+2 ] and Ψ(2x) ≤ CΨ(x) for any x ∈ R + . We recall that by assumption, n σ ≤ Cd(0, n) for some σ > 0. Now, from this fact and the definition of N j , we have

(N j+1 ) σ ≤ Cd(0, N j+1 ) ≤ C2 j . Then log p (2(N j+1 -N j )) ≤ Cj p .
And, therefore

E sup Nj <N ≤Nj+1 N k=Nj +1 X k (Ψ(d(0, N j )) log τ (d(0, N j ))) 1/p p ≤ C 1 j τ -p .
Summing over j and using Beppo Levi's theorem, this gives

lim j→∞ sup Nj <N ≤Nj+1 N k=Nj +1 X k (Ψ(d(0, N j )) log τ (d(0, N j )))
1/p = 0 a.s.. This together with [START_REF] Csörgő | On the strong law of large numbers for pairwise independent random variables[END_REF] concludes the proof of the first part of the theorem in case c.

Step 5. To prove the second part of the theorem, we follow the previous steps but with some modifications. Specifically, we set N j = 2 j and replace log τ (d(0, N )) in the denominator of the previous steps with log τ (N ). Moreover, we use the inequalities d(0, 2n) ≤ 2d(0, n) and Ψ(2x) ≤ CΨ(x) to show that

Ψ(d(0,Nj+1)) Ψ(d(0,Nj )) is bounded.
Step 6. Now, we prove the strong maximal inequality. To do it, we use ( 6), and we take the supremum over j. This gives sup

N ≥1 N k=1 X k (Ψ(d(0, N )) log τ (d(0, N ))) 1/p p ≤ C sup j≥1 sup Nj <N ≤Nj+1 N k=Nj +1 X k (Ψ(d(0, N j )) log τ (d(0, N j ))) 1/p p +C sup j≥1 Nj k=1 X k (Ψ(d(0, N j )) log τ (d(0, N j ))) 1/p p .
Choosing, for instance, the case c of the first part of the theorem and integrating over µ, we can obtain sup

N ≥1 N k=1 X k (Ψ(d(0, N )) log τ (d(0, N ))) 1/p p p,µ ≤ C j≥1 log p (2(N j+1 -N j ))Ψ(d(N j , N j+1 )) Ψ(d(0, N j )) log τ (d(0, N j )) +C j≥1 Ψ(d(0, N j )) Ψ(d(0, N j )) log τ (d(0, N j ))
.

The last term is finite, as we showed above in Steps 1 and 4. If we perform the same operation on all cases, this demonstrates the strong maximal inequality and completes the proof.

Proof of Theorem 2

Let (N k ) k∈N be such that

N k = inf{N ∈ N : d(0, N ) ≥ k}. Note that k ≤ d(0, N k ) < k + 1.
Therefore, for any m < n,

d(N m , N n ) ≤ d(0, N n ) -d(0, N m ) < 2(n -m).
To simplify the notation, we define X k = Y k -EY k . We will prove the theorem in two steps. In Step 1, we will demonstrate that the theorem holds for the sequence (N k ) k∈N .

In Step 2, we will generalize this result.

Step 1. As in the proof of Theorem 1, we write,

N k i=1 X i (d(0, N k ) log τ (d(0, N k ))) 1/p ≤ N 2 j k=1 X k (d(0, N 2 j ) log τ (d(0, N 2 j ))) 1/p (10) + sup 2 j <k≤2 j+1 N k k=N 2 j +1 X k (d(0, N 2 j ) log τ (d(0, N 2 j ))) 1/p . Know we have, E N 2 j k=1 X k (d(0, N 2 j ) log τ (d(0, N 2 j ))) 1/p p ≤ d(0, N 2 j ) d(0, N 2 j ) log τ (d(0, N 2 j )) ≤ 1 log τ (2 j ) ≤ C 1 j τ .
It follows from the assumptions of the theorem that j 1 j τ < ∞. Thus, according to Beppo Levi's theorem,

lim j→∞ N 2 j k=1 X k (d(0, N 2 j ) log τ (d(0, N 2 j )))
1/p = 0 a.s.. [START_REF] Korchevsky | A generalization of the petrov strong law of large numbers[END_REF] Now, we have to control the second term on the right-hand side of [START_REF] Nikolaevitch | Sur la loi forte des grands nombres[END_REF]. To do it, we write for any n, m ∈ [2 j + 1, 2 j+1 ] with m < n,

E |S Nn -S Nm | p ≤ Cd(N m , N n ) ≤ C(n -m).
We are now in a position to apply Lemma 3, then E sup

2 j <k≤2 j+1 N k i=N 2 j +1 X i (d(0, N 2 j ) log τ (d(0, N 2 j ))) 1/p p ≤ C log p 2(2 j+1 -2 j ) (2 j+1 -2 j ) d(0, N 2 j ) log τ (d(0, N 2 j )) ≤ C log p 2 j+1 2 j 2 j log τ (2 j ) ≤ C 1 j τ -p .
When τ > p + 1, the last quantity is a term of a convergent series. By Beppo Levi's theorem lim j→∞ sup

2 j <k≤2 j+1 N k i=N 2 j +1 X i (d(0, N 2 j ) log τ (d(0, N 2 j )))
1/p = 0 a.s..

According now [START_REF] Korchevsky | A generalization of the petrov strong law of large numbers[END_REF] and [START_REF] Kuczmaszewska | Convergence rate in the petrov slln for dependent random variables[END_REF], this concludes that, for τ > p + 1,

lim k→∞ N k k=1 X k (d(0, N k ) log τ (d(0, N k )))
1/p = 0 a.s., and yields the desired result of Step 1.

Step 2. In this step we treat the general case. For this, we let N and k two integers in such a way that

N k < N ≤ N k+1 . Then N i=1 X i = N i=1 (Y i -EY i ) ≤ N k+1 i=1 Y i - N k+1 i=1 EY i + N k+1 i=N +1 EY i (13) = N k+1 i=1 X i + N k+1 i=N +1 EY i .
And, therefore

N i=1 X i (d(0, N ) log τ (d(0, N ))) 1/p ≤ N k+1 i=1 X i (d(0, N k ) log τ (d(0, N k ))) 1/p + N k+1 i=N +1 EY i (d(0, N k ) log τ (d(0, N k ))) 1/p . By Step 1, for τ > p + 1, we have lim k→∞ N k+1 i=1 X i (d(0, N k+1 ) log τ (d(0, N k+1 )))
1/p = 0 a.s..

For large enough k, there exists a constant C > 0 such that

d(0, N k+1 ) log τ (d(0, N k+1 )) d(0, N k ) log τ (d(0, N k )) ≤ (k + 2) log τ (k + 2) k log τ (k) ≤ C. Thus lim k→∞ N k+1 i=1 X i (d(0, N k ) log τ (d(0, N k ))) 1/p = 0 a.s.. ( 14
)
Now, from the assumptions, EY i ≤ Cd andd(m, n) is super-additive, and from the definition of N k , we have

1 p (0, i)d(i -1, i)
N k+1 i=N +1 EY i (d(0, N k ) log τ (d(0, N k ))) 1/p ≤ C N k+1 i=N k +1 d 1 p (0, i)d(i -1, i) (d(0, N k ) log τ (d(0, N k ))) 1/p ≤ C d(0, N k+1 ) 1 p d(N k , N k+1 ) (d(0, N k ) log τ (d(0, N k ))) 1/p ≤ C 1 log τ p k .
This together with the equation ( 14) gives lim sup

k→∞ N i=1 X i (d(0, N ) log τ (d(0, N )))
1/p ≤ 0 a.s..

To conclude, we use the fact that N k < N ≤ N k+1 and we write

N i=1 X i ≥ N k i=1 X i - N i=N k +1 EY i
And, therefore

N i=1 X i (d(0, N ) log τ (d(0, N ))) 1/p ≥ N k i=1 X i (d(0, N k+1 ) log τ (d(0, N k+1 ))) 1/p - N i=N k +1 EY i (d(0, N k+1 ) log τ (d(0, N k+1 ))) 1/p .
Now we do as we did above to prove that lim inf

k→∞ N i=1 X i (d(0, N ) log τ (d(0, N ))) 1/p ≥ 0 a.s.. Consequently lim k→∞ N i=1 X i (d(0, N ) log τ (d(0, N )))
1/p = 0 a.s.

which proves our claim and finishes the proof of theorem.

Proof of Corollary 2

Using Abel's summation formula, we have

N k=1 X k (k β log τ (k)) 1/p = N -1 k=1 1 (k β log τ (k)) 1/p - 1 ((k + 1) β log τ (k + 1)) 1/p k j=1 X j + 1 (N β log τ (N )) 1/p N k=1 X k . ( 15
) If β > 1, then there exists α > 1 such that (n -m) β/α is super-additive. Applying Corollary 1 with d(m, n) = (m -n) β , we have lim N →∞ 1 (N β log τ (N )) 1/p N k=1 X k = 0.
This implies that the last term of the right-hand side of (15) converges to 0 almost surely. Moreover,

E N -1 k=1 1 (k β log τ (k)) 1/p - 1 ((k + 1) β log τ (k + 1)) 1/p k j=1 X j p ≤ C N -1 k=1 1 k β+1 log τ (k) E k j=1 X j p ≤ C N -1 k=1 k β k β+1 log τ (k)
.

Since we assume that τ > 1, the last term is finite, as desired. Then, by applying Beppo Levi's theorem, we can conclude the proof for β > 1. For the case where β = 1, we can follow the same steps as before and use Corollary 1 with d(m, n) = (n -m).

Discussion and applications

Let {X k , k ≥ 1} be a sequence of random variables. It is well-known that for p ≥ 1,

E n k=m+1 X i p ≤ (n -m) p-1 n k=m+1 E |X i | p . If {X k , k ≥ 1}
∈ R + . Then if 1 ≤ α ≤ 2, k≥1 log p (k)k α-1 E |X k | p ϕ p (k) < ∞ =⇒ lim N →∞ 1 ϕ(N ) N k=1 X k = 0 a.s.. ( 16
)
If α > 2, k≥1 k α-1 E |X k | p ϕ p (k) < ∞ =⇒ lim N →∞ 1 ϕ(N ) N k=1 X k = 0 a.s.. Notice that, if we take      E |X k | p = 1 k , d(m, n) = (n -m) α-1 n k=m+1 E |X k | p , ϕ(n) = (d(0, n) log τ (d(0, n))) 1/p ,
then by Corollary 1, the convergence of equation ( 16) is guaranteed as long as τ > 1 + p, since there exists a positive σ such that n σ ≤ Cn α-1 n k=1 E |X k | p , where 1 < α ≤ 2. In contrast, Theorem 3 only requires a value of τ greater than p to achieve convergence. Similarly, if α > 2, Corollary 1 necessitates τ > 1 for convergence, while the previous theorem only requires τ > 0.

Proof. The proof for the first part of the theorem will be presented, and the second part can be demonstrated using the same process. From the proof of Theorem 1, specifically equation ( 6), step 1 and step 4, to obtain [START_REF] Nane | A strong law of large numbers with applications to self-similar stable processes[END_REF], it remains to show that

j≥1 2 j(α-1) 2 j k=1 E |X k | p ϕ p (2 j ) < ∞ and j≥1 j p 2 j(α-1) 2 j+1 k=2 j +1 E |X k | p ϕ p (2 j ) < ∞. ( 17
) Since ϕ(2x) ≤ Cϕ(x), j≥1 j p 2 j(α-1) 2 j+1 k=2 j +1 E |X k | p ϕ p (2 j ) ≤ C j≥1 2 j+1 k=2 j +1 log p (k)k α-1 E |X k | p ϕ p (k) ≤ C k≥3 log p (k)k α-1 E |X k | p ϕ p (k) ,
which is finite by assumption. Now, we prove the first half of [START_REF] Nane | Strong laws of large numbers for arrays of random variables and stable random fields[END_REF]. Provided that

ϕ p (n) n α-1 log p (n) n∈N
is a strictly increasing sequence and approaches infinity as n approaches infinity, we have from the assumption of the theorem and from Kronecker's lemma that

lim n→∞ log p (n)n α-1 ϕ p (n) n k=1 E |X k | p = 0. Consequently n α-1 ϕ p (n) n k=1 E |X k | p ≤ C 1 log p (n) .
The proof ends with p > 1.

The following corollary is a direct application of the previous theorem using ϕ be defined on [A, ∞). The following result is a direct consequence of Theorem 1.5.12 and Proposition 1.5.15 in [START_REF] Nicholas H Bingham | Regular variation[END_REF] (see also Lemma p < ∞.

(n) = n α-1 log τ (n) n k=1 E |X k | p 1/p . Corollary 3. If 1 ≤ α ≤ 2, then k≥1 E |X k | p log τ -p (k) k i=1 E |X i | p < ∞ =⇒ lim N →∞ N k=1 X k N α-1 log τ (N ) N k=1 E |X k | p 1/p = 0 a.s.. If α > 2, then k≥1 E |X k | p log τ (k) k i=1 E |X i | p < ∞ =⇒ lim N →∞ N k=1 X k N α-1 log τ (N ) N k=1 E |X k | p 1/p = 0 a.s..

Application with slowly varying sequences

2.1 in [1]), lim x→∞ f (g(x)) x = lim x→∞ g(f (x)) x = 1. Let now, {X k , k ≥ 1} be an identically distributed sequence such that E (g(|X 1 | p )) < ∞.
To do it, we write

k≥2 log p (k)k α-1 E |Y k | p (k β log(k)L β (k)) p = k≥2 k α-1 E (|X k | I (|X k | p ≤ f (k))) p k βp L βp (k) = E   |X 1 | p k≥2 I (|X 1 | p ≤ f (k)) k βp-α+1 L βp (k)   .
Since β > α p , it follows from Theorem 8.7 in [START_REF] Zygmund | Trigonometric series[END_REF], that

k≥n 1 f (k) ≤ C n f (n) for any n ≥ g(A). Thus |X 1 | p k≥2 I (g(|X 1 | p ) ≤ k) k βp-α+1 L βp (k) ≤ C|X 1 | p g(|X 1 | p ) f (g(|X 1 | p ) ≤ Cg(|X 1 | p )
where the last inequality follows from the fact that f (g(x)) ∼ x. Since E [g(|X 1 | p )] < ∞, the proof is complete.

Sequence of quasi-stationary random variables.

The van der Corput lemma will come in handy later on. Let f : N → R + be a non-negative function. Let {X k , k ∈ N} be a sequence of random variables. We say that {X k , k ≥ 1} is f -quasi-stationary if for any h ∈ N, E(X k ) = 0, E(X 2 k ) < ∞ and E(X k X k+h ) ≤ f (h).

According to [START_REF] Vladimirovich | On the strong law of large numbers[END_REF] with

H = n -m -1, E n k=m+1 X k 2 ≤ C n k=m+1 E|X k | 2 + C n -m n-1 h=m+1 (n -h) n+m-h k=m+1 |E(X k X k+h )| ≤ C n k=m+1 E|X k | 2 + C n -m n-1 h=m+1 (n -h) 2 f (h) ≤ C n k=m+1 E|X k | 2 + C(n -m) n-1 h=m+1 f (h).
The following theorem is a direct consequence of Theorem 3.

E|X k | 2 + C n-1 h=m+1 f (h) n+m-h-1 k=m g(k)E|X k | 2 .
Theorem 3 can also be applied.

1 . 1 α

 11 If one of the following cases holds: (a) there exists α > 1 such that d (m, n) is super-additive and τ > 1; (b) d(m, n) is super-additive, there exists σ > 0 such that n σ = O (d(0, n)) and τ > p + 1, 0, N ) log τ (d(0, N )))

A

  slowly varying function L(•) is a positive and measurable function on [A, ∞) for some A > 0, such that for any λ > 0, conjugate of a slowly varying function L(•) is another slowly varying function L(•) that is unique up to asymptotic equivalence. The de Bruijn conjugate satisfies two conditions: lim x→∞ L(x) L(xL(x)) = 1 and lim x→∞ L(x)L(x L(x)) = 1. Let β > α p and let f (x) = x

Theorem 4 .→∞ 1 N

 41 It is known that for a non-negative random variableY , E(Y ) < ∞ if and only if k≥1 P (Y > k) < ∞. This gives k≥1 P(|X 1 | p > f (k)) = k≥1 P(g(|X 1 | p ) > k) < ∞. Let Y k = X k I (|X k | p ≤ f (k)), then lim N β log(N )L β (N ) N k=1 Y k a.s.. Proof. Based on Theorem 3, it is enough to demonstrate that k≥2 log p (k)k α-1 E |Y k | p (k β log(k)L β (k))

Lemma 4 .

 4 (Van der Corput) Let m and n be integers such that m < n. Let (u k ) k∈N be a finite sequence which takes values in C and H a integer such that H < n -m. Then k+h • ūk ) .

Theorem 5 .X

 5 Let {X k , k ≥ 1} be a f -quasi-stationary sequence and let ϕ be a nondecreasing function. Suppose thatk≥2 log 2 (k)k k i=1 f (i) ϕ 2 (k) k = 0 a.s..It is possible to push the analysis further. Specifically, suppose that for anyh > 0, |E(X k X k+h )| ≤ g(k)f (h)E|X k | 2 ,where g is a positive function. Using the Van der Corput lemma allows us to obtain E

  is a sequence of independent random variables with EX k = 0 and E|X k | p < ∞ for some 1 ≤ p ≤ 2, then E | Although Corollary 1 is applicable in this case, the following theorem proves to be more effective in certain special cases of E |X k |

			n k=1 X k | p ≤ C p	n k=1 E |X k |	p (see von Bahr and Esseen
	[20]). In what follows we consider that the sequence {X k , k ∈ N} satisfying
	n	p	n
	E	X i	≤ (n -m) α-1	E |X k |
	k=m+1		k=m+1

p , for some α ∈ [1, p]. p . Theorem 3. Let p > 1 and let ϕ : R → R + be a non-decreasing function such that ϕ(2x) ≤ Cϕ(x), for any x