Andrei Romashchenko

Clustering with Respect to the Information Distance

We discuss the notion of a dense cluster with respect to the information distance and prove that all such clusters have an extractable core that represents the mutual information shared by the objects in the cluster.

Introduction

In the seminal paper [START_REF] Charles H Bennett | Information distance[END_REF], Bennett et al. introduced the notion of information distance based on Kolmogorov complexity. Loosely speaking, the distance between two individual finite objects is defined as the length of the shortest program that can translate these objects to each other. A surprising result proven in [START_REF] Charles H Bennett | Information distance[END_REF] claims that the length of such a program (that performs the translation of the given objects to each other, in both directions) is substantially equal to the maximum of the lengths of two separate programs translating the objects to each other. The optimal lengths of the programs depend, of course, on the choice of the programming language. Such a choice may look arbitrary. However, the framework of Kolmogorov complexity (see [START_REF] Kolmogorov | Three approaches to the quantitative definition of information[END_REF]) provides us with an optimal programming language where the required programs have the minimum (up to an additive constant) possible length.

The notion of information distance attracted the attention of theoretical computer scientists and also inspired many experimental works, where various practical approximations of the information distance were computed for realworld data. This technique was typically used to reveal clusters and classify data of some specific type (texts, music recordings, genetic codes, and so on). In such experiments, the revealed clusters (groups of objects with small pairwise information distances) consist of the data having something in common: texts written in the same language, music pieces of the same genre, genetic information of closely related species, and so on (see, e.g, [START_REF] Li | The similarity metric[END_REF][START_REF] Cilibrasi | Algorithmic clustering of music based on string compression[END_REF][START_REF] Cilibrasi | Clustering by compression[END_REF]). In the studied practical examples, it can be usually observed that the revealed dense clusters have some core (e.g., the common language vocabulary, specific characteristics of a particular music genre, the genetic information of the common predecessor of several biological species), even if providing an explicit description of such a core is not immediate.

In this paper, we study a similar phenomenon in a purely theoretical setting. We show that the only reason why a large set of objects may form a dense cluster with respect to the information distance is that these objects share some common information in the sense of Gács and Körner [START_REF] Gács | Common information is far less than mutual information[END_REF]. In other words, there must exist a core that is simple conditional on each object of the cluster and that represents in some sense the mutual information shared by all these objects. Such results were used (more or less explicitly) as technical tools in [START_REF] Romashchenko | Extracting the mutual information for a triple of binary strings[END_REF][START_REF] Romashchenko | A criterion for extractability of mutual information for a triple of strings[END_REF][START_REF] Muchnik | Stability of properties of kolmogorov complexity under relativization[END_REF]. We believe that the observed phenomenon is interesting in its own right, and we want to draw more attention to this issue. In this paper, we propose a selfcontained explanation of the mentioned result using a simplified definition of a cluster proposed by Alexander Shen (personal communication, June 10, 2021), see Definition 1 below. The proofs of the main results follow the arguments suggested in [START_REF] Romashchenko | Extracting the mutual information for a triple of binary strings[END_REF][START_REF] Romashchenko | A criterion for extractability of mutual information for a triple of strings[END_REF].

Notation and standard properties of Kolmogorov complexity

In what follows we use the standard notation C(x) for the plain Kolmogorov complexity of a string x and C(x|y) for the plain Kolmogorov complexity of a string x conditional on a string y (see, e.g., [START_REF] Li | An introduction to Kolmogorov complexity and its applications[END_REF] or [START_REF] Shen | Kolmogorov complexity and algorithmic randomness[END_REF]). In this paper we do not discuss prefix-free complexity, monotone complexity, or any other subtler versions of algorithmic complexity, so we may use for C(x) and C(x|y) the term Kolmogorov complexity without risk of ambiguity.

As usual, we assume to be fixed an encoding of tuples, i.e., a computable bijection between binary strings and tuples (finite ordered lists) of strings. Thus, every tuple of strings is associated with its code, which is an individual binary string. Keeping this in mind, we assume that C(x, y) denotes Kolmogorov complexity of the code of the pair x, y ; C(x, y, z) denotes Kolmogorov complexity of the code of the triple x, y, z , and so on.

Observe that any two encodings of this type (computable bijections between tuples and individual strings) are equivalent: there are translation algorithms converting a code of a tuple in one encoding system into the code of the same tuple in the other encoding systems, and the other way around. This means that the choice of the encoding is quite arbitrary and affects the value of Kolmogorov complexity by at most an additive constant, see [START_REF] Shen | Kolmogorov complexity and algorithmic randomness[END_REF]Section 2.1].

The classical Kolmogorov-Levin theorem (the chain rule), [START_REF] Kolmogorov | Logical basis for information theory and probability theory[END_REF][START_REF] Alexander | The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms[END_REF], establishes the relation between Kolmogorov complexity of a pair and conditional Kolmogorov complexity,

C(x, y) = C(x) + C(y |x) + O(log(C(x) + C(y))).
The mutual information of two strings and the conditional mutual information are defined as I(x : y)

Clusters with respect to the information distance

The information distance between x and y can be defined as dist(x, y) = max{C(x|y), C(y |x)}.

(It is not a distance in the proper sense since the triangle inequality is true only up to an additive logarithmic term.) Information distance measures the amount of information needed to obtain one of the strings given another one. Speaking informally, this value can be understood as a measure of "similarity" (or rather "non-similarity") between strings: if x, y, z are three strings of the same length, and dist(x, y) is much less than dist(x, z), we can say that x is more "similar" to y than to z. We can consider clusters defined in the sense of this information distance, i.e., large sets of strings with small diameters. Roughly speaking, a cluster is a set of strings of cardinality at least 2 m and diameter at most m. As is usual in the theory of Kolmogorov complexity, we should admit a minor imprecision (say, logarithmic in m) of the parameters. The formal definition of a cluster involves two parameters, the diameter and the logsize (logarithm of the cardinality): Definition 1. We say that a set of strings S is an (m, ℓ)-cluster if for all x 1 , x 2 ∈ S we have dist(x 1 , x 2 ) ≤ m and #S ≥ 2 ℓ . An equivalent wording: we can say that this S is a cluster with parameters (m, ℓ). The minimal suitable value of m is called the cluster's diameter and the maximal suitable integer number ℓ is called the cluster's logsize.

The "density" of a cluster can be measured by the difference between the diameter and the logsize: the closer they are to each other, the denser is the cluster. We usually deal with clusters where this difference is bounded by O(log m).

First of all, do the dense clusters exist? The answer to this question is yes, we can find (m, ℓ)-clusters with only a logarithmic gap between m and ℓ. Indeed, for every string z we may consider a "canonical" cluster or a daisy that consists of strings x such that C(z |x) ≈ 0 and C(x|z) m. To make these approximate equality and inequality more specific, we fix a parameter d and define a daisy with imprecision d as follows. Observe that the definition of a daisy involves two integer parameters, but they do not play the same role as the parameters in the general definition of an (m, ℓ)-cluster.

Every (m, d)-daisy with d = O(log m) is a cluster, i.e., it satisfies Definition 1 with a logarithmic gap between the diameter and the logsize. Indeed, from the definition of an (m, d)-daisy it follows that for all x 1 , x 2 in this set we have

C(x 1 |x 2 ) ≤ C(z |x 2 ) + C(x 1 |z) + O(log m).
A similar bound applies to C(x 2 |x 1 ). Therefore,

dist(x 1 , x 2 ) ≤ m + O(d + log m) = m + O(log m).
The cardinality of this set is at least 2 m since it contains all pairs z, w where w is an m-bit string. Thus, this set is an (m + O(log m), m)-cluster.

A daisy is by definition a cluster with an explicitly given core. A daisy of strings intuitively resembles a flower with a core and many petals. We can draw it on the plane as a family of 2 m pairwise intersecting sets (so that the mutual information of every two strings corresponds to the size of the intersection between two sets) such that all these sets have a common part (the core), as shown in Fig. 1a, and the size of each "petal" (outside the core) is at most m. However, a naive parallelism between the mutual information and intersections of sets can be deceiving. Indeed, Gács and Körner showed that the mutual information of two strings may not correspond to any material object (see [START_REF] Gács | Common information is far less than mutual information[END_REF]). Moreover, even if the mutual information of each pair of objects can be "materialized," it seems possible that pairwise intersecting objects do not share any common core, as in the example in Fig. 1b.

So a natural question arises: do there exist clusters substantially different from a daisy? Rather surprisingly, it turns out that there are no other clusters besides the daisies and their subsets. We can say informally that all clusters (in the sense of Definition 1) resemble Fig. 1a and not Fig. 1b. This is the main result of this paper.

Main Result (informal version). Every cluster in the sense of information distance is a sufficiently large subset of some daisy.

Observe that every large enough subset of a cluster is still a cluster (of high enough density). Thus, this theorem may be interpreted as a description of all dense enough clusters as sufficiently large parts of daisies. Now we proceed with a more formal statement.

Theorem 1 (main result, the formal version). Let S be a set of strings such that C(x|x ′ ) ≤ m for every two strings x, x ′ ∈ S. Assume that log #S ≥ m -d for some d. Then there exists a string z such that

C(z |x) ≤ O(d + log m) and C(x|z) ≤ m + O(d + log m)
for all x ∈ S.

Theorem 1 can be naturally rephrased in terms of clusters and daisies: it claims that for every (m, m -d)-cluster S there exists a string z such that S is included in an (m + O(d + log m), O(d + log m))-daisy with the core z. Notice that the found core z possibly does not belong to S. In fact, a cluster may even not contain any element close to its core.

Proof. We start the proof with the following lemma.

Lemma 1 (Many paths x -y -z imply one shorter path x -z). Assume that for given strings x, z and for given numbers u, v, w there are at least 2 u strings y such that C(y |x) < v and C(z |y) < w.

Then C(z |x) ≤ v + w -u + O(log(v + w)).
Proof of Lemma 1. Given x, v, w, we can enumerate all z for which there exists y with the required properties. There are at most 2 v+w paths of length 2 and at least 2 u of these paths should lead to such a z. So there are at most 2 v+w-u different z, and this implies the bound for C(z |x).

The previous lemma can be used to merge clusters, as the following remark shows.

Remark. (Merging two clusters). If S and S ′ are two clusters of diameter m that have at least 2 m-d common elements, then their union is a cluster of diameter at most m + d + O(log m). Indeed, if x and x ′ are elements from S and S ′ respectively, then there are at least 2 m-d paths x-x ′′ -x ′ such that x ′′ ∈ S ∩S ′ . Therefore, from Lemma 1 it follows that dist(x,

x ′ ) ≤ 2m-(m-d)+O(log m) = m + d + O(log m).
More specifically, we will need the following version of cluster merging:

Lemma 2 (Merging a cluster with a daisy). Assume that an (m + d 1 , m -d 2 )cluster S has at least 2 m-d3 common elements with an (m, d 4 )-daisy S ′ with a core z. Then S is contained in the daisy S ′′ with the same core z with the parameters

m + O i d i + log m , O i d i + log m . (1)
Proof. For every x ∈ S there are at least 2 m-d3 chains z -x ′ -x such that x ′ ∈ S ∩ S ′ . From Lemma 1 it follows that

C(z |x) ≤ m + d 1 + d 4 -(m -d 3 ) + O(log m) = O i d i + log m and C(x|z) ≤ m + d 4 + m + d 1 -(m -d 3 ) + O(log m) = m + O i d i + log m .
Therefore, x belongs to the daisy S ′′ with parameters (1) and the base z.

To prove the theorem, it is enough (thanks to Lemma 2) to find a daisy parameters

m + O d + log m , O d + log m
that has a large (of cardinality at least 2 m-O d+log m ) intersection with the given cluster S. We do it as follows. The property of being a cluster with given parameters is enumerable. So we can run a process enumerating all (m, m -d)clusters. We do not restrict the length or complexity of strings in the clusters, so the enumeration will be infinite. As any other cluster with the same parameters, our cluster S will be enumerated at some stage of this process. Let us fix some threshold d ′ (that will be slightly greater than d, see below). We say that two clusters S 1 , S 2 have a large intersection if #(S 1 ∩ S 2 ) > 2 m-d ′ . To make the enumeration procedure defined above more economic, we will drop some clusters from this enumeration. We will keep only the ones that do not have large intersections with one of the clusters enumerated (and not dropped) earlier. We call the clusters that are not dropped referential clusters. We assign to the referential clusters their ordinal numbers in the order they appear in the enumeration. (Observe again that there can be infinitely many referential clusters.) We will see that either S itself or some cluster that has a large intersection with S will become a referential cluster, and we plan to take its ordinal number in the enumeration as the core z of the daisy that we are looking for.

First of all, we argue that every referential cluster is a part of a daisy with parameters m + O(d + log m), O(d + log m) .

Let S i be the referential cluster with ordinal number i. We start with the observation that every element x ∈ S i can be determined if we know i and the ordinal number of x in some standard ordering of S i . To organize the process x ∈ S i . We want to show that i is a part of a daisy with a core i. To this end, we show that C(i|x) ≈ 0 for all x ∈ S i . We use the following lemma saying that (under some conditions on the parameters) the multiplicity of the family S i is small, i.e., every x is covered by only a small number of S i . Then, to reconstruct i given x, we need only the ordinal number of S i in the list of referential clusters containing x (and also the number m, as before).

Lemma 3 (Multiplicity bound). Assume that d ′ > 2d + 1. Then every string x can be covered by at most 2 d+1 referential (m, m -d)-clusters.

Proof of Lemma 3. Assume that some string x is covered by N referential clusters. Each cluster S i has size at least 2 m-d , and the intersection of every two clusters is at most 2 m-d ′ (otherwise the second cluster could not be selected as a referential one). Note also that all elements of all clusters that contain x have conditional complexity at most m conditional on x. Therefore, the union of all these clusters has a size at most 2 m+1 (all clusters covering x are included in a rather small neighborhood of x, see Fig. 2). We use the following probabilistic claim:

Claim. Let ε be the inverse of a positive integer number1 . If there are N events of probability greater than ε, and all pairwise intersections have probability less than ε 2 /2, then N < 2/ε.

(The bounds in the claim are pretty tight: 1/ε events of probability ε could be disjoint, and any number of independent events of probability ε have intersection ε 2 .)

Proof. Assume that we have N = 2/ε events (we decrease N if needed). By the principle of inclusion and exclusion, the probability of the union of these events is strictly greater than

N • ε - N 2 2 • ε 2 2 = 2 - 4 2ε 2 • ε 2 2 = 1, a contradiction.
We consider the union of all (m, m -d)-clusters covering x as the probability space with equiprobable points, where each cluster is an event. To apply this claim, we note that each cluster has a probability of at least ε := 2 -d , and the intersections are of at most 2 -d ′ . Since d ′ > 2d + 1, we can apply the Claim and obtain the bound 2 d+1 for the number of clusters covering x. Therefore, we have

C(x|i) ≤ m + O(log m) and C(i|x) ≤ d + O(log m)
for every element x of every referential cluster S i . Thus, each referential cluster is a part of an m + O(d + log m), O(d + log m) -daisy. Now we bind together all parts of the argument. Assume that we have an (m -d, m)-cluster S. We let d ′ = 2d + 2 (so the condition of Lemma 3 is true) and start the process of enumeration of referential clusters using d ′ as the "large intersection" threshold. The construction guarantees that S is one of the referential clusters or at least it has a large intersection with some referential cluster S i . Every referential cluster S i is a part of an m + O(d + log m), O(d + log m) -daisy. Therefore, we can apply Lemma 2 and conclude that S is a part of a slightly bigger m + O(d + log m), O(d + log m) -daisy, and the theorem is proven.

Clusters and the mutual information of a triple

In this section, we discuss an application of Theorem 1 that motivated the definition of "bunches" proposed in [START_REF] Romashchenko | Extracting the mutual information for a triple of binary strings[END_REF] (similar to the definition of clusters discussed in the previous section). Theorem 2 ([7,[START_REF] Romashchenko | A criterion for extractability of mutual information for a triple of strings[END_REF]). For every triple of strings x, y, z there exists a string w such that C(w) = I(x : In particular, if the three values of conditional mutual information I(x : y |z), I(x : z |y), I(y : z |x) are negligibly small (say, logarithmic in C(x, y, z)) as shown in Fig. 3, then the mutual information shared by x, y, z can be materialized in the sense of common information by Gács and Körner, [START_REF] Gács | Common information is far less than mutual information[END_REF]. Proof. For each triple of strings (x, y, z) we call by its complexity profile the tuple of seven complexity quantities C(x), C(y), C(z), C(x, y), C(x, z), C(y, z), C(x, y, z) .

y : z) + O(ε + log C(x,
For every precision parameter (an integer number) δ we define the set C δ of δ-clones of z conditional on (x, y) as the set of all z ′ such that the complexity profile of (x, y, z ′ ) differs in each component from the complexity profile of (x, y, z) by at most δ.

A simple counting argument implies (see, e.g., [START_REF] Ae Romashchenko | Pairs of words with nonmaterializable mutual information[END_REF]) that there exists a constant D (independent of x, y, z) such that for all x, y, z the set of δ-clones of z conditional on (x, y) with δ = D log C(x, y, z) consists of 2 C(z |x,y)-O(δ) strings z ′ . In what follows we fix such a δ.

We claim that C δ is a cluster. To prove this fact we need the following inequality, where z ′ and z ′′ are two arbitrary elements from This inequality2 is valid for all strings x, y, z, z ′ , z ′′ , see [START_REF] Makarychev | A new class of non-Shannon-type inequalities for entropies[END_REF]. Since z ′ and z ′′ are clones of z conditional on x, y, the inequality rewrites to I(x : y) ≤ I(z ′ : z ′′ ) + O(ε + log C(x, y, z)).

It follows that (it is enough to count the number of chains x -ẑ -w and y -ẑ -w with ẑ ∈ C δ ).

C(z ′′ |z ′ ) = C(z ′′ ) -I(z ′ : z ′′ ) ≤ C(z) -I(x : y) + O(ε + log C(x, y, z)) = C(z |x, y) + O(ε + log C(x, y, z)).

Discussion

The questions addressed in this paper seem to be related to the density properties studied in [1, Section IX], where the authors estimated the rate of growth of the number of elements in balls of radius r in the metric spaces induced by the information distance. We should stress, however, that a ball (the set of strings x ′ at the distance at most r from a given center x) is not a cluster in the sense of Definition 1.

The main result of this theorem is formulated and proven with a "logarithmic precision," which is quite typical for the theory of Kolmogorov complexity. In many applications the logarithmic precision is enough. At the same time, it seems that the residue terms in Theorem 1 can be made somewhat tighter. In this vein, an anonymous referee of the Theoretical Computer Science journal suggested the following stronger version of Theorem 1: (Compared with Theorem 1, the conclusion of this statement contains no additive terms O(log m); on the other hand, the number m is included into the conditions of two expressions with Kolmogorov complexity.) This version of the theorem can be proven by an argument very similar to the proof of Theorem 1 presented in Section 2; we only need to relativize to m the expressions with Kolmogorov complexity that appear in the proof. However, if we want to rephrase Theorem 1 ′ in terms of clusters and daisies (cf. the paragraph after Theorem 1 on p. 5), we would need to revise the definition of a daisy. This observation suggests that the definitions of clusters and daisies might need to be refined.

Let us mention also that slightly different variants of the definition of a cluster may be helpful in some applications, see [START_REF] Muchnik | Stability of properties of kolmogorov complexity under relativization[END_REF]. An interesting variant of the definition was proposed by S. Epstein in [START_REF] Epstein | On the conditional complexity of sets of strings[END_REF], where the principal parameter was not the maximum but the average distance between elements of a cluster. Epstein argued that the density of a cluster is connected with the mutual information between this cluster and the halting sequence (characterizing the stopping Turing machine in the universal enumeration). Thus, the formulation of the most natural and practical definition of a dense cluster (in the sense of information distance) remains an open question.

  def = C(y) -C(y |x) and I(x : y |z) def = C(y |z) -C(y |x, z) respectively. From the Kolmogorov-Levin theorem it follows that mutual information is symmetric up to a logarithmic additive term: I(x : y) = C(x) + C(y) -C(x, y) + O(log n) = I(y : x) + O(log n) and I(x : y |z) = C(x, z)+C(y, z)-C(x, y, z)-C(z)+O(log m) = I(y : x|z)+O(log m), where n = C(x) + C(y) and m = C(x) + C(y) + C(z).

Definition 2 .

 2 An (m, d)-daisy with a core z is the set of all x such that C(z |x) ≤ d and C(x|z) ≤ m + d.

  (a) A bunch of intersecting sets having a common core.(b) A bunch of pairwise intersecting sets with no common core.

Figure 1 :

 1 Figure 1: Geometric representation of clusters.

xFigure 2 :

 2 Figure 2: An element x (shown as a dot) is covered by a family of sets (shown in different colors) all of which lie in a neighborhood of this element (shown as an area with a dashed borderline).

  y, z)) and max{C(w|x), C(w|y), C(w|z)} = O(ε + log C(x, y, z)), where ε := max I(x : y |z), I(x : z |y), I(y : z |x) and I(x : y : z) := C(x) + C(y) + C(z) -C(x, y) -C(x, z) -C(y, z) + C(x, y, z).

Figure 3 :

 3 Figure 3: A Venn-like diagram representing information quantities for a triplet (x, y, z). The area of each circle represents the value of Kolmogorov complexity of x, y, and z respectively. The areas of the unions of any two circles represent Kolmogorov complexity of pairs, and the area of the union of all three circles represents Kolmogorov complexity of the triple. Accordingly, the intersections of every two circles represent the mutual information of pairs, and the intersection of all three circles represents the value I(x : y : z). The areas shown in light gray represent the values of the three conditional mutual information I(x : y |z), I(x : z |y), I(y : z |x). Theorem 2 claims that if the three values of conditional mutual information are negligibly small, then the mutual information of the triple I(x : y : z) (which is in this case ε-close to each of the values I(x : y), I(x : z), and I(y : z)) can be materialized.

  C δ : I(x : y) ≤ I(x : y |z ′ ) + I(x : y |z ′′ ) + I(z ′ : z ′′ ) + I(x : y |z) + I(x : z |y) + I(y : z |x) + O(log C(x, y, z)).

  Therefore, C δ is a cluster with the parametersC(z |x, y) + O(δ + log C(x, y, z)), C(z |x, y) -O(δ + log C(x, y, z)) .Theorem 1 implies that there exists a string w (the core of the cluster) such that C(w| ẑ) = O(ε + log C(x, y, z)) and C(ẑ |w) = C(z |x, y)+ O(ε + log C(x, y, z)) for all ẑ ∈ C δ (including the original string z). It is easy to compute Kolmogorov complexity of w: C(w) = I(z : x, y ) + O(ε + log C(x, y, z)) = I(x : y : z) + O(ε + log C(x, y, z)). It remains to observe that due to Lemma 1 C(w|x) = O(ε + log C(x, y, z)) and C(w|y) = O(ε + log C(x, y, z))

Theorem 1 ′

 1 . Let S be a set of strings such that C(x|x ′ ) ≤ m for every two strings x, x ′ ∈ S. Assume that log #S ≥ m -d for some d. Then there exists a string z such that C(z|x, m) < O(d) and C(x|z, m) < m + O(d).

A similar claim is true for all real numbers ε > 0. The assumption that 1/ε is an integer number slightly simplifies the calculations since we can ignore rounding.

This inequality is a non-Shannon type one, i.e., it cannot be represented as a linear combination of several instances of inequalities representing non negativity of conditional Kolmogorov complexity, or mutual information, or conditional mutual information. The very first example of a non-Shannon type linear inequality for Shannon's entropy was proven by Zhang and Yeung in[START_REF] Zhang | On characterization of entropy function via information inequalities[END_REF]. It is known, see[START_REF] Hammer | Inequalities for Shannon entropy and Kolmogorov complexity[END_REF], that the same linear inequalities are true for Shannon's entropy and Kolmogorov complexity. The inequality used in our proof is a little generalization of the inequality discovered by Zhang and Yeung, see[START_REF] Makarychev | A new class of non-Shannon-type inequalities for entropies[END_REF] for details.

Acknowledgments. The author is grateful to Alexander Shen and Marius Zimand for fruitful discussions, especially for the elegant form of the probabilistic claim (see the Claim on p. 7) suggested by Alexander Shen. The author also thanks the anonymous referees of the Theoretical Computer Science journal for the careful review of the paper and valuable comments and suggestions.


S Bessy

D Rautenbach
email: dieter.rautenbach@uni-ulm.de

Algorithmic aspects of broadcast independence

Keywords:

An independent broadcast on a connected graph G is a function f : V (G) → N 0 such that, for every vertex x of G, the value f (x) is at most the eccentricity of x in G, and

We describe an efficient algorithm that determines the broadcast independence number of a given tree. Furthermore, we show NP-hardness of the broadcast independence number for planar graphs of maximum degree four, and hardness of approximation for general graphs. Our results solve problems posed by Dunbar, Erwin, Haynes, Hedetniemi, and

Introduction

In his PhD thesis [START_REF] Erwin | Cost domination in graphs[END_REF] Erwin introduced the notions of broadcast domination and broadcast independence in graphs. While broadcast domination was studied in detail, only little research has been done on broadcast independence [START_REF] Ahmane | On the broadcast independence number of caterpillars[END_REF][START_REF] Bouchemakh | On the broadcast independence number of grid graph[END_REF][START_REF] Dunbar | Broadcasts in graphs[END_REF][START_REF] Hedetniemi | Unsolved algorithmic problems on trees[END_REF], and several fundamental problems related to this notion remained open. After efficient algorithms for optimal broadcast domination were developed for restricted graph classes [START_REF] Blair | Broadcast domination algorithms for interval graphs, series-parallel graphs and trees[END_REF][START_REF] Dabney | A linear-time algorithm for broadcast domination in a tree[END_REF], Heggernes and Lokshtanov [START_REF] Heggernes | Optimal broadcast domination in polynomial time[END_REF] showed the beautiful and surprising result that broadcast domination can be solved optimally in polynomial time for every graph. In contrast to that, Dunbar et al. [START_REF] Dunbar | Broadcasts in graphs[END_REF] and Hedetniemi [START_REF] Hedetniemi | Unsolved algorithmic problems on trees[END_REF] explicitly ask about the complexity of broadcast independence and about efficient algorithms for trees. As pointed out recently by Ahmane et al. [START_REF] Ahmane | On the broadcast independence number of caterpillars[END_REF], the complexity of broadcast independence was unknown even for trees.

In the present paper we describe an efficient algorithm for optimal broadcast independence in trees. Furthermore, we show hardness of approximation for general graphs and NPcompleteness for planar graphs of maximum degree four. Before stating our results precisely, we collect the necessary definitions. We consider finite, simple, and undirected graphs, and use standard terminology and notation. Let N 0 be the set of nonnegative integers, and let Z be the set of integers. For a connected graph G, a function f : V (G) → N 0 is an independent broadcast on G if (B1) f (x) ≤ ecc G (x) for every vertex x of G, where ecc G (x) is the eccentricity of x in G, and (B2) dist G (x, y) > max{f (x), f (y)} for every two distinct vertices x and y of G with f (x), f (y) > 0, where dist G (x, y) is the distance of x and y in G.

The weight of f is

x∈V (G)
f (x). The broadcast independence number α b (G) of G is the maximum weight of an independent broadcast on G, and an independent broadcast on G of weight α b (G) is optimal. Let α(G) be the usual independence number of G defined as the maximum cardinality of an independent set in G, which is a set of pairwise nonadjacent vertices of G. For an integer k, let [k] be the set of all positive integers at most k, and let

[k] 0 = {0} ∪ [k].
Note that adding a universal vertex to a non-empty graph does not change its independence number but reduces its diameter to two, and that α b (G) = α(G) for a graph G with diameter two and α(G) ≥ 3. These observations imply that Zuckerman's [START_REF] Zuckerman | Linear degree extractors and the inapproximability of max clique and chromatic number[END_REF] hardness of approximation result for maximum clique immediately yields the following. Proposition 1.1. For every positive real number ǫ, it is NP-hard to approximate the broadcast independence number of a given connected graph of order n to within n 1-ǫ .

As already stated, we show that computing the broadcast independence number remains hard even when restricted to instances with bounded maximum degree. In fact, we believe that it is hard even when restricted to cubic graphs.

Theorem 1.1. For a given connected planar graph G of maximum degree 4 and a given positive integer k, it is NP-complete to decide whether α b (G) ≥ k.

Clearly, α b (G) ≥ α(G) for every connected graph G. In [START_REF] Bessy | Relating broadcast independence and independence[END_REF] we show α b (G) ≤ 4α(G) for every connected graph G, which yields efficient constant factor approximation algorithms for the broadcast independence number on every class of connected graphs on which the independence number can efficiently be approximated within a constant factor; in particular, on graphs of bounded maximum degree.

In the next section, we prove Theorem 1.1, and, in Section 3, we present the polynomial time algorithm to compute the broadcast independence number of a given tree, more precisely, we prove the following.

Theorem 1.2. The broadcast independence number α b (T ) of a given tree T of order n can be determined in O(n 9 ) time.

2 NP-completeness of broadcast independence on planar graphs with maximum degree 5

In this section, we prove Theorem 1.1.

Since an independent broadcast can be encoded using polynomially many bits, and (B1) and (B2) can be checked in polynomial time, the considered decision problem is in NP. We show its NP-completeness by reducing to it the NP-complete problem [START_REF] Garey | The rectilinear Steiner tree problem is NP-complete[END_REF] Independent Set restricted to connected planar cubic graphs. Therefore, let (H, k) be an instance of Independent Set, where H is a connected planar cubic graph. Recall that Independent Set is the problem to decide whether α(H) ≥ k. In order to complete the proof, we describe a polynomial time construction of a planar graph G of maximum degree 4 such that

α b (G) = α(H) + 45 2 n(H),
where n(H) is the order of H. First, let the graph H ′ arise by subdividing each edge of H exactly twice. It is well known and easy to see that α(

H ′ ) = α(H) + m(H) = α(H) + 3 2 n(H)
, where m(H) is the number of edges of H. Now, the graph G arises from H ′ by • adding, for every vertex x in V (H), one copy K(x) of the star K 1,4 of order 4 and connecting its center with x, and

• adding, for every vertex x in V (H ′ ) \ V (H), two disjoint copies K 1 (x) and K 2 (x) of the star K 1,4 of order 4 and connecting their two centers with x.

See Figure 1 for an illustration. Note that G is connected and planar, has order 32n(H) and maximum degree 4, and contains 21n(H) endvertices. Since some maximum independent set in G contains all 21n(H) endvertices of G, and removing the closed neighborhoods of all these endvertices yields H ′ , we have

✉ ✉ s s r r r r r r r r r r r r r r r r r r ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ u v ❅ ❅ ❅ ❅ r r r r r r
α(G) = α(H ′ ) + 21n(H) = α(H) + 3 2 n(H) + 21n(H) = α(H) + 45 2 n(H), that is, it remains to show that α b (G) = α(G).
Let f : V (G) → N 0 be an optimal independent broadcast on G. For every vertex x of H ′ , let L(x) be the set of endvertices of G that are at distance 2 from x, and let L =

x∈V (H ′ ) L(x). Note that |L(x)| = 3 if x ∈ V (H), and that |L(x)| = 6 if x ∈ V (H ′ ) \ V (H).
If there is some vertex

x in V (G) \ L with f (x) = k for some k ≥ 2,
and y is a vertex in L that is closest to x, then changing the value of f (y) to k, and the value of f (x) to 0 yields an independent broadcast on G of the same weight as f . Applying this operation iteratively, we may assume that

f (x) ≥ 2 only if x ∈ L.
If there is some vertex y in V (H ′ ) such that f (x) ∈ {2, 3} for some vertex x in L(y), then changing the value of f for the at least three vertices in L(y) to 1 yields an independent broadcast on G whose weight is at least the weight of f . Applying this operation iteratively, we may assume that

f (x) ∈ {2, 3} for every x ∈ V (G).
If there is some vertex

y in V (H ′ ) \ V (H) such that f (x) ∈ {4, 5, 6} for some vertex x in L(y),
then changing the value of f for the six vertices in L(y) to 1 yields an independent broadcast on G whose weight is at least the weight of f . Applying this operation iteratively, we may assume that f (x) ∈ {4, 5, 6} for every y ∈ V (H ′ ) \ V (H) and every x ∈ L(y).

(1)

Let X = {x ∈ V (G) : f (x) > 0}.
To every vertex x in X, we assign an independent set I(x) as follows:

• If f (x) = 1, then let I(x) = {x}.
• If f (x) = 4, then, by [START_REF] Ahmane | On the broadcast independence number of caterpillars[END_REF], there is some vertex y of H such that x ∈ L(y). Let I(x) = {y} ∪ L(y).

• If f (x) = 5, then, by [START_REF] Ahmane | On the broadcast independence number of caterpillars[END_REF], there is some vertex y of H such that x ∈ L(y). Let y ′ be some neighbor of y in H ′ , and let I(x) = L(y) ∪ L(y ′ ).

• If f (x) ≥ 6, then there is some vertex y of H ′ such that x ∈ L(y). By (B1), there is a shortest path P :

x 0 . . . x ⌊ f (x) 2 ⌋ in G such that x 0 = x and x 2 = y. Let I(x) = ⌊ f (x) 2 ⌋ i=2 L(x i ).
By construction, I(x) is an independent set for every x in X. Furthermore, if f (x) ≤ 5 for some x in X, then |I(x)| ≥ f (x) is easily verified. Now, if f (x) ≥ 6 for some x in X, and P is as above, then f (x) 2 ≥ 3, at least one of the two sets L(x 2 ) and L(x 3 ) contains six vertices, and, hence,

|I(x)| ≥ 3 f (x) 2 -1 + 3 ≥ f (x)
. Altogether, I(x) is an independent set of order at least f (x) for every x in X.

Suppose, for a contradiction, that there are two distinct vertices x and x ′ in X such that I(x) and

I(x ′ ) intersect. If f (x) = 1, then, necessarily, f (x ′ ) = 4, and dist G (x, x ′ ) ≤ 2, contradicting (B2). If f (x), f (x ′ ) ∈ {4, 5}, then, by (1), dist G (x, x ′ ) = 2, and if f (x) ∈ {4, 5} and f (x ′ ) ≥ 6, then dist G (x, x ′ ) ≤ f (x ′ ) 2 + 2 < f (x ′ ), contradicting (B2). Finally, if f (x), f (x ′ ) ≥ 6, then dist G (x, x ′ ) ≤ f (x) 2 + f (x ′ ) 2
≤ max{f (x), f (x ′ )}, again contradicting (B2). Hence, the sets

I(x) for x in X are all disjoint.
Suppose, for a contradiction, that there are two distinct vertices x and x ′ in X such that G contains an edge between I(x) and I(x ′ ). Since no two endvertices in G are adjacent, and I(x) ⊆ L for x in X with f (x) ≥ 5, this implies f (x), f (x ′ ) ∈ {1, 4}, which easily implies a contradiction to (B2). Altogether, it follows that

I = x∈X I(x) is an independent set of order at least α b (G), which implies α(G) ≥ α b (G). Since α b (G ′ ) ≥ α(G ′ ) holds for every graph G ′ ,
this complete the proof.

A polynomial time algorithm for trees

Throughout this section, let T be a fixed tree of order n.

Before we explain the details of our approach, which is based on dynamic programming, we collect some key observations. We will consider certain subtrees T (u, i) of T that contain a vertex u such that all edges of T between V (T (u, i)) and V (T ) \ V (T (u, i)) are incident with u, that is, V (T (u, i)) contains u and some connected components of Tu. For every independent broadcast f on T , the restriction of f to V (T (u, i)) clearly satisfies (C1) f (x) ≤ ecc T (x) for every vertex x of T (u, i).

(C2) dist T (x, y) > max{f (x), f (y)} for every two distinct vertices x and y of T (u, i) with f (x), f (y) > 0.

Furthermore, if y is a vertex in V (T ) \ V (T (u, i)) with f (y) > 0, then y imposes upper bounds on the possible values of f inside V (T (u, i)). More precisely, f (x) must be 0 for all vertices

x of T (u, i) with dist T (x, y) ≤ f (y), and f (x) can be at most dist T (x, y) -1 for all vertices

x of T (u, i) with dist T (x, y) > f (y). So, in short we have f (x) = 0 if dist T (x, y) ≤ f (y) and f (x) ≤ dist T (x, y) -1 otherwise. Expressed as a function of dist T (u, x) instead of dist T (x, y), and using the equality dist T (u, x) = dist T (x, y) -dist T (u, y), we obtain the condition

f (x) ≤ g (p,q) (dist T (u, x)) for every vertex x of T (u, i),
where the function g (p,q) (d) : Z → N 0 is such that

g (p,q) (d) =    0 , if d ≤ p, and
d -p + q -1 , if d ≥ p + 1, (2)
p = f (y) -dist T (u, y), and q = f (y).

Note that q is positive, p may be negative, and that |p| and q are both at most the diameter of T , which is at most n.

One key observation is the following simple lemma.

Lemma 3.1. If (p 1 , q 1 ), . . . , (p k , q k ) are pairs of integers such that -n ≤ p i ≤ n and 1 ≤ q i ≤ n for every i in [k], then there is a pair (p in , q in ) of integers such that -n ≤ p in ≤ n, 1 ≤ q in ≤ n, and

g (p in ,q in ) (d) = min g (p 1 ,q 1 ) (d), . . . , g (p k ,q k ) (d) for every nonnegative integer d.
Proof. The statement follows for p in = max{p 1 , . . . , p k } and q in = min g (p 1 ,q 1 ) (p in + 1), . . . , g (p k ,q k ) (p in + 1) .

Clearly, we have -n ≤ p in ≤ n and min{g (p 1 ,q 1 ) (d), . . . , g

(p k ,q k ) (d)} = 0 = g (p in ,q in ) (d) for d ≤ p in . Since g (p i ,q i ) (p in + 1) ≥ g (p i ,q i ) (p i + 1) = q i ≥ 1 for every i in [k], we have q in ≥ 1. Furthermore, if i in [k] is such that p in = p i , then q in ≤ g (p i ,q i ) (p in + 1) = g (p i ,q i ) (p i + 1) = (p i + 1) -p i + q i -1 = q i ,
which implies q in ≤ q i ≤ n. Finally, notice that for every p, q, p ′ , and d such that d ≥ p + 1 and p ′ ≥ p, we have g (p,q) (d) = d -(p ′ + 1) + g (p,q) (p ′ + 1). So, for every d ≥ p in + 1, we have

min{g (p 1 ,q 1 ) (d), . . . , g (p k ,q k ) (d)} = d -(p in + 1) + min{g (p 1 ,q 1 ) (p in + 1), . . . , g (p k ,q k ) (p in + 1)} = d -(p in + 1) + q in = g (p in ,q in ) (d).
Lemma 3.1 implies that the upper bounds on the possible values of f inside V (T (u, i)) that are imposed by positive values of f in V (T ) \ V (T (u, i)) can be encoded by just two integers p in and q in with -n ≤ p in ≤ n and 1 ≤ q in ≤ n. Symmetrically, the upper bounds on the possible values of

f inside V (T ) \ V (T (u, i)) that are imposed by positive values of f in V (T (u, i)),
again expressed as a function of the distance from u in T , can be encoded by just two integers p out and q out with -n ≤ p out ≤ n and 1 ≤ q out ≤ n. For all O(n 4 ) possible choices for ((p in , q in ), (p out , q out )), the algorithm determines the maximum contribution

x∈V (T (u,i))
f (x) to the weight of an independent broadcast f on T such that the following conditions hold:

(C3) f (x) ≤ g (p in ,q in ) (dist T (u, x)) for every vertex x of T (u, i). (C4) If f (x) > 0 for some vertex x of T (u, i), then g (pout,qout) (d) ≤ g (f (x),f (x)) (d + dist T (u, x)) for every positive integer d.
Intuitively speaking, (C3) means that every value of f assigned to some vertex of T (u, i) respects the upper bound encoded by g (p in ,q in ) , and (C4) means that every positive value of f assigned to some vertex of T (u, i) imposes an upper bound on the values of f outside V (T (u, i)) that is at least the upper bound encoded by g (pout,qout) . The next lemma shows how to check condition (C4) in constant time for an individual vertex x. Lemma 3.2. If p, q, f , and dist are integers such that -n ≤ p ≤ n and q, f, dist ∈ [n], then

g (p,q) (d) ≤ g (f,f ) (d + dist) for every positive integer d (3)
if and only if max f -max p, 0 , qp ≤ dist.

Proof. We consider two cases. First, let p ≤ 0. In this case, g (p,q) (d) is positive for every positive d, and (3) holds if and only if

(i) g (f,f ) (1 + dist) is positive, and (ii) g (f,f ) (1 + dist) is at least g (p,q) (1).
(i) is equivalent to 1 + dist ≥ f + 1, and, by (i), (ii) is equivalent to

(1 + dist) -f + f -1 ≥ 1 -p + q -1
, that is, (i) and (ii) together are equivalent to max{f, q -p} ≤ dist. Next, let p ≥ 1. In this case, g (p,q) (d) is positive if and only if d ≥ p + 1, and (3) holds if and only if

(i) g (f,f ) (p + 1 + dist) is positive, and (ii) g (f,f ) (p + 1 + dist) is at least g (p,q) (p + 1). (i) is equivalent to p + 1 + dist ≥ f + 1, and, by (i), (ii) is equivalent to p + 1 + dist -f + f -1 ≥ p + 1 -p + q -1 = q, that
is, (i) and (ii) together are equivalent to max{fp, q -p} ≤ dist.

The statement of the lemma summarizes both cases. Now, we explain which subtrees T (u, i) we consider. We select a vertex r of T , and consider T as rooted in r. For every vertex u of T that is not a leaf, we fix an arbitrary linear order on the set of children of u. If v 1 , . . . , v k are the children of u in their linear order, then for every i ∈ [k] 0 , let T (u, i) be the subtree of T that contains u, v 1 , . . . , v i as well as all descendants of the vertices v 1 , . . . , v i in T . Note that T (u, 0) contains only u, and that u is the only vertex of T (u, i) that may have neighbors in T outside of V (T (u, i)). Altogether, there are at most (d T (r) + 1) +

x∈V (T )\{r} d T (x) = O(n) many choices for (u, i). For brevity, let V (u, i) denote V (T (u, i)).
Let u be a vertex with k children, and let i ∈ [k] 0 . Let p in , p out , q in , and q out be integers with -n ≤ p in , p out ≤ n and 1 ≤ q in , q out ≤ n. A function f : V (u, i) → N 0 is ((p in , q in ), (p out , q out ))-compatible if conditions (C1), (C2), (C3), and (C4) hold. Let β((u, i), (p in , q in ), (p out , q out ))

be the maximum weight

x∈V (u,i) f (x) of a function f : V (u, i) → N 0 that is ((p in , q in ), (p out , q out ))- compatible.
Our next lemma shows that the broadcast independence number can be extracted from these values. The following lemmas explain how to determine β((u, i), (p in , q in ), (p out , q out )) recursively for all O(n 5 ) possible choices for ((u, i), (p in , q in ), (p out , q out )). The next lemma specifies in particular the values for leaves. Lemma 3.4. β((u, 0), (p in , q in ), (p out , q out )) =    0 , if q out > p out , and min ecc T (x), g (p in ,q in ) (0), p out , if q out ≤ p out .

Proof. This follows immediately from (C1), (C3), and (C4) using Lemma 3.2, V (u, 0) = {u}, and dist T (u, u) = 0.

The next lemma is the technical key lemma. Recall that v 1 , . . . , v k denote the children of u in the chosen linear order. See Figure 2. If f is ((p in , q in ), (p out , q out ))-compatible, then there are integers

s u s s . . . v 1 v i-1 ✂ ✂ ✂ s v i V (u, i -1) V (v i , k i )
p (0) in , p (0)
out , p

in , p

out , q

in , q

out , q

in , q

, with -n ≤ p (0) in , p (1) out
out , p

in , p

out ≤ n and 1 ≤ q

(0) in , q (0)
out , q

in , q

out ≤ n such that:

(i) The restriction of f to V (u, i -1) is p (0) in , q (0) in , p (0)
out , q

0) out -compatible. (ii) The restriction of f to V (v i , k i ) is p (1) in , q (
, p

out , q

1) out -compatible. (iii) g p (0) in ,q (0) in (d) = min g (p in ,q in ) (d), g p (1) out ,q (
(d + 1) for every nonnegative integer d.

(iv) g p (1) in ,q

(1) in

(d) = min g (p in ,q in ) (d + 1), g p (0) out ,q (0
) out (d + 1) for every nonnegative integer d.

(v) g (pout,qout) (d) ≤ min g p (0) out ,q (0) out (d), g p (1) out ,q (1) out
(d + 1) for every positive integer d.

which implies dist T (x, y) > f (y), because f (x) is positive. Symmetrically, we obtain f (y)

(ii),(C3)

≤ g p (1)
in ,q

(1) in (dist T (v i , y))

(iv) ≤ g p (0) out ,q (0) out (dist T (v i , y) + 1)

(i),(C4) ≤ g (f (x),f (x)) (dist T (v i , y) + 1 + dist T (u, x))

= g (f (x),f (x)) (dist T (x, y)), which implies dist T (x, y) > f (x), because f (y) is positive. Altogether, it follows that f satisfies (C2).

Since, by (iii), g p (0) in ,q (0) in (d) ≤ g (p in ,q in ) (d), and, by (iv), g p (1) in ,q

(1) in (d) ≤ g (p in ,q in ) (d + 1) for every nonnegative integer d, we have f satisfies (C3).

If x ∈ V (u, i -1) is such that f (x) > 0, then, β((u, i), (p in , q in ), (p out , q out )) equals the maximum of β (u, i -1), p

g (pout,qout) (d) (v) ≤ g p (0) out ,q (0) out (d)
in , q (0) in , p

out , q (0) out

+ β (v i , k i ), p (1)
in , q

(1) in , p

out , q

, where the maximum extends over all choices of p (0) in , p

out , p

in , p

out , q

in , q (0) out , q

in , and q

(1) out , with

Figure 1 :

 1 Figure 1: An edge uv of H after two subdivisions and the attachment of the disjoint stars. The vertices of H are shown largest and the vertices of the attached stars are shown smallest.

Lemma 3 . 3 .

 33 α b (T ) = β((r, d T (r)), (-1, n), (n, 1)). Proof. By definition, T (r, d T (r)) equals T . Since g (-1,n) (d) ≥ n for every d in N 0 , condition (C3) is void in view of condition (C1). Similarly, condition (C4) is void by Lemma 3.2 and condition (C1). This clearly implies the statement.

Figure 2 : 5 . 3 . 5 .

 2535 Figure 2: The situation considered in Lemma 3.5.

5 . 3 . 6 .

 536 x),f (x)) (d + dist T (u, x)) for every positive integer d.Similarly, if x ∈ V (v i , k i ) is such that f (x) > 0, then, g (pout,qout) (d) (x),f (x)) (d + 1 + dist T (v i , x)) = g (f (x),f (x)) (d + dist T (u, x))for every positive integer d.Altogether,f satisfies (C4),which completes the proof.The next lemma is a consequence of Lemma 3.Lemma Let i ∈ [k], and let v i have k i children.

Conversely, if the integers p (0) in , p (0) out , p [START_REF] Ahmane | On the broadcast independence number of caterpillars[END_REF] in , p [START_REF] Ahmane | On the broadcast independence number of caterpillars[END_REF] out , q (0) in , q (0) out , q [START_REF] Ahmane | On the broadcast independence number of caterpillars[END_REF] in , q

(1) out , with -n ≤ p (0) in , p (0) out , p [START_REF] Ahmane | On the broadcast independence number of caterpillars[END_REF] in , p [START_REF] Ahmane | On the broadcast independence number of caterpillars[END_REF] out ≤ n and 1 ≤ q (0) in , q (0) out , q [START_REF] Ahmane | On the broadcast independence number of caterpillars[END_REF] in , q

(1) out ≤ n are such that conditions (i) to (v) hold, then f is ((p in , q in ), (p out , q out ))-compatible.

Proof. First, let f : V (u, i) → N 0 be ((p in , q in ), (p out , q out ))-compatible.

By Lemma 3.1, there is a pair p (0) out , q (0) out such that the function g p (0) out ,q (0) out encodes the upper bounds on the possible values of f outside of V (u, i -1) that are imposed by the positive values of f in V (u, i -1) as a function of the distance to u. Similarly, there is a pair p

out , q

(1) out such that the function g p (1) out ,q

(1) out encodes the upper bounds on the possible values of f outside of V (v i , k i ) that are imposed by the positive values of f in V (v i , k i ) as a function of the distance to v i . Since the distance of a vertex outside of V (u, i) to v i is one more than its distance to u, condition (C4) implies (v). By Lemma 3.1, the minimum in (iii) equals g p (0) in ,q

in , where we use g (p,q) (d + 1) = g (p-1,q) (d) for all integers p, d with q ≥ 1. Similarly, the minimum in (iv) equals g p (1) in ,q

(1) in for a suitable choice of p

in , that is, (iii) and (iv) hold. Since f is ((p in , q in ), (p out , q out ))-compatible, the value of f assigned to a vertex x in V (u, i-1) is at most g (p in ,q in ) (dist T (u, x)). Furthermore, by (C2) for f , the value of f assigned to any vertex

(dist T (u, x) + 1). Altogether, (i) holds for g p (0) in ,q (0) in as in (iii). By a completely symmetric argument, it follows that (ii) holds for g p [START_REF] Ahmane | On the broadcast independence number of caterpillars[END_REF] in ,q

(1) in as in (iv). This completes of the proof of the first part of the statement.

Next, let

in , p

out , q

in , p

out ≤ n and 1 ≤ q

in , q

(1) out ≤ n be such that conditions (i) to (v) hold.

By (i) and (ii), f satisfies (C1).

By (i) and (ii), the restriction of f to V (u, i -1) satisfies (C2), and the restriction of f to

out ,q

(1) out

out , p

in , p

out ≤ n and 1 ≤ q

in , q

out ≤ n that satisfy the conditions (iii), (iv), and (v) from Lemma 3.5. Proof. This follows from Lemma 3.5 and the fact that V (u, i) is the disjoint union of V (u, i -1) and V (v i , k i ). Notice that when considering the values β (u, i -1), p

out , q

(1) out , we know, by definition, that the corresponding restricted independent broadcasts T (u, i -1) and

in , q

out , q

(1) out -compatible, respectively. As the choice of the parameters satisfies the conditions (iii), (iv), and (v) from Lemma 3.5, we have seen in the proof of that lemma that the common extension of the two restricted independent broadcasts is a restricted independent broadcast on T (u, i).

We are now ready for the following.

Proof of Theorem 1.2. By Lemmas 3.4 and 3.6, each of the O(n 5 ) values β((u, i), (p in , q in ), (p out , q out )) can be determined in time O(n 4 ), by

• processing the vertices u of T in an order of nonincreasing depth within T ,

• considering the O(n) possible values for each of the four integers p

out , q (0) out , and q

(1) out ,

• checking condition (v) from Lemma 3.5 in constant time,

• determining the four integers p It may be possible -yet tedious -to extend Theorem 1.2 to graphs of bounded treewidth.


Antoine Domenech
email: antoine.domenech@ens-lyon.fr

Pascal Ochem
email: ochem@lirmm.fr

Doubled patterns with reversal and square-free doubled patterns

In combinatorics on words, a word w over an alphabet Σ is said to avoid a pattern p over an alphabet ∆ if there is no factor f of w such that f = h(p) where h : ∆ * → Σ * is a non-erasing morphism. A pattern p is said to be k-avoidable if there exists an infinite word over a k-letter alphabet that avoids p. A pattern is doubled if every variable occurs at least twice. Doubled patterns are known to be 3-avoidable. Currie, Mol, and Rampersad have considered a generalized notion which allows variable occurrences to be reversed. That is, h(V R ) is the mirror image of h(V ) for every V ∈ ∆. We show that doubled patterns with reversal are 3-avoidable. We also conjecture that (classical) doubled patterns that do not contain a square are 2-avoidable. We confirm this conjecture for patterns with at most 4 variables. This implies that for every doubled pattern p, the growth rate of ternary words avoiding p is at least the growth rate of ternary square-free words.

Introduction

The mirror image of the word w = w 1 w 2 . . . w n is the word w R = w n w n-1 . . . w 1 . A pattern with reversal p is a non-empty word over an alphabet ∆ = A, A R , B, B R , C, C R . . . such that {A, B, C, . . .} are the variables of p. An occurrence of p in a word w is a non-erasing morphism h : ∆ * → Σ * satisfying h(X R ) = (h(X)) R for every variable X and such that h(p) is a factor of w. The avoidability index λ(p) of a pattern with reversal p is the size of the smallest alphabet Σ such that there exists an infinite word w over Σ containing no occurrence of p. A pattern p such that λ(p) k is said to be k-avoidable. To emphasive that a pattern is without reversal (i.e., it contains no X R ), it is said to be classical. A pattern is doubled if every variable occurs at least twice.

Our aim is to strengthen the following result.

Theorem 1. [START_REF] Bell | Exponential lower bounds for the number of words of uniform length avoiding a pattern[END_REF][START_REF] Ochem | A generator of morphisms for infinite words[END_REF][START_REF] Ochem | Doubled patterns are 3-avoidable[END_REF] Every doubled pattern is 3-avoidable.

First, we extend it to patterns with reversal.

Theorem 2. Every doubled pattern with reversal is 3-avoidable.

Then, we notice that all the known classical doubled patterns that are 2-unavoidable contain a square, such as AABB, ABAB, or ABCCBADD. Conjecture 3. Every square-free doubled pattern is 2-avoidable.

Notice that Conjecture 3 is related to but independent of the following conjecture.

Conjecture 4. [START_REF] Ochem | Doubled patterns are 3-avoidable[END_REF][START_REF] Ochem | Application of entropy compression in pattern avoidance[END_REF] There exist only finitely many 2-unavoidable doubled patterns.

The proof of Conjecture 3 for patterns up to 3 variables follows from the 2-avoidability of ABACBC, ABCBABC, ABCACB and ABCBAC. We were able to verify it for patterns up to 4 variables. Theorem 5. Every square-free doubled pattern with at most 4 variables is 2-avoidable.

Finally, we obtain a lower bound on the number of ternary words avoiding a doubled pattern. The factor complexity of a factorial language L over Σ is

f (n) = |L ∩ Σ n |. The growth rate of L over Σ is lim n→∞ f (n) 1 n
. We denote by GR 3 (p) the growth rate of ternary words avoiding the doubled pattern p. Theorem 6. For every doubled pattern p, GR 3 (p) GR 3 (AA).

Let v(p) be the number of distinct variables of the pattern p. In the proof of Theorem 1, the set of doubled patterns is partitioned as follows:

1. Patterns with v(p) 3: the avoidability index of every ternary pattern has been determined [START_REF] Ochem | A generator of morphisms for infinite words[END_REF].

2. Patterns shown to be 3-avoidable with the so-called power series method:

• Patterns with v(p) 6 [1]
• Patterns with v(p) = 5 and prefix ABC or length at least 11 [START_REF] Ochem | Doubled patterns are 3-avoidable[END_REF] • Patterns with v(p) = 4 and prefix ABCD or length at least 9 [START_REF] Ochem | Doubled patterns are 3-avoidable[END_REF] 3. Ten sporadic patterns with 4 v(p) 5 whose 3-avoidability cannot be deduced from the previous results: they have been shown to be 2-avoidable [START_REF] Ochem | Doubled patterns are 3-avoidable[END_REF] using the method in [START_REF] Ochem | A generator of morphisms for infinite words[END_REF].

The proof of Theorems 2 and 6 use the same partition. Sections 3 to 5 are each is devoted to one type of doubled pattern with reversal. Theorem 5 is proved in Section 6 Theorem 6 is proved in Section 7

Preliminaries

A word w is d-directed if for every factor f of w of length d, the word f R is not a factor of w.

Remark 7. If a d-directed word contains an occurrence h of X.X R for some variable X, then |h(X)| d -1.

A variable that appears only once in a pattern is said to be isolated. The formula f associated to a pattern p is obtained by replacing every isolated variable in p by a dot. The factors between the dots are called fragments. An occurrence of a formula f in a word w is a non-erasing morphism h such that the h-image of every fragment of f is a factor of w. As for patterns, the avoidability index λ(f ) of a formula f is the size of the smallest alphabet allowing the existence of an infinite word containing no occurrence of f . Recently, the avoidability of formulas with reversal has been considered by Currie, Mol, and Rampersad [START_REF] Currie | A family of formulas with reversal of high avoidability index[END_REF][START_REF] Currie | Avoidance bases for formulas with reversal[END_REF] and Ochem [START_REF] Ochem | A family of formulas with reversal of arbitrarily high avoidability index[END_REF].

Recall that a formula is nice if every variable occurs at least twice in the same fragment. In particular, a doubled pattern is a nice formula with exactly one fragment.

The avoidability exponent AE(f ) of a formula f is the largest real x such that every x-free word avoids f . Every nice formula f with v(f ) 3 variables is such that AE(f ) 1 + 1 2v(f )-3 [START_REF] Ochem | Avoidability of palindrome patterns[END_REF]. Let ≃ be the equivalence relation on words defined by w ≃ w ′ if w ′ ∈ w, w R . Avoiding a pattern up to ≃ has been investigated for every binary formulas [START_REF] Currie | The undirected repetition threshold and undirected pattern avoidance[END_REF]. Remark that for a given classical pattern or formula p, avoiding p up to ≃ implies avoiding simultaneously all the variants of p with reversal.

Recall that a word is (β + , n)-free if it contains no repetition with exponent strictly greater than β and period at least n.

Formulas with at most variables

For classical doubled patterns with at most 3 variables, all the avoidability indices are known. There are many such patterns, so it would be tedious to consider all their variants with reversal.

However, we are only interested in their 3-avoidability, which follows from the 3-avoidability of nice formulas with at most 3 variables [START_REF] Ochem | On some interesting ternary formulas[END_REF].

Thus, to obtain the 3-avoidability of doubled patterns with reversal with at most 3 variables, we show that every minimally nice formula with at most 3 variables is 3-avoidable up to ≃.

The minimally nice formulas with at most 3 variables, up to symmetries, are determined in [START_REF] Ochem | On some interesting ternary formulas[END_REF] and listed in the following table. Every such formula f is avoided by the image by a q-uniform morphism of either any infinite 5 4 +free word w 5 over Σ 5 or any infinite 7 5 + -free word w 4 over Σ 4 , depending on whether the avoidability exponent of f is smaller than 7 5 .

Formula f + , 25

= f R AE(f ) Word q d freeness ABA.
In the table above, the columns indicate respectively, the considered minimally nice formula f , whether f is equivalent to its reversed formula, the avoidability exponent of f , the infinite ternary word avoiding f , the value q such that the corresponding morphism is q-uniform, the value such that the avoiding word is d-directed, the suitable property of (β + , n)-freeness used in the proof that f is avoided. We list below the corresponding morphisms. As an example, we show that ABCBA.CAC is avoided by g k (w 5 ). First, we check that g k (w 5 ) is 4 3 + , 25 -free using the main lemma in [START_REF] Ochem | A generator of morphisms for infinite words[END_REF], that is, we check the 4 Similarly, the factors h(BCB) and h(CAC) imply b max 1 2 c, 24 and c max 1 2 a, 24 . Solving these inequalities gives a 36, b 24, and c 24. Now we can check exhaustively that g k (w 5 ) contains no occurrence up to ≃ satisfying these bounds.

g
Except for ABCBA.CBABC, the avoidability index of the nice formulas in the above table is 3. So the results in this section extend their 3avoidability up to ≃.

The power series method

The so-called power series method has been used [START_REF] Bell | Exponential lower bounds for the number of words of uniform length avoiding a pattern[END_REF][START_REF] Ochem | Doubled patterns are 3-avoidable[END_REF] to prove the 3avoidability of many classical doubled patterns with at least 4 variables and every doubled pattern with at least 6 variables, as mentioned in the introduction.

Let p be such a classical doubled pattern and let p ′ be a doubled pattern with reversal obtained by adding some -R to p. Witout loss of generality, the leftmost appearance of every variable X of p remains free of -R in p ′ . Then we will see that p ′ is also 3-avoidable. The power series method is a counting argument that relies on the following observation. If the h-image of the leftmost appearance of the variable X of p is fixed, say h(X) = w X , then there is exactly one possibility for the h-image of the other appearances of X, namely h(X) = w X . This observation can be extended to p ′ , since there is also exactly one possibility for h(X R ), namely h(X R ) = w R X . Notice that this straightforward generalization of the power series method from classical doubled patterns to doubled patterns with reversal cannot be extended to avoiding a doubled pattern up to ≃. Indeed, if h(X) = w X for the leftmost appearance of the variable X and w X is not a palindrome, then there exist two possibilities for the other appearances of X, namely w X and w R X .

Sporadic patterns

Up to symmetries, there are ten doubled patterns whose 3-avoidability cannot be deduced by the previous results. They have been identified in [START_REF] Ochem | Doubled patterns are 3-avoidable[END_REF] and are listed in the following table.

Let w 5 be any infinite 5 4 + -free word over Σ 5 and let h be the following 9-uniform morphism. First, we check that h(w 5 ) is 7-directed and 139 108 + , 46 -free. Then, using the same method as in Section 3, we show that h(w 5 ) avoids up to ≃ these ten sporadic patterns simultaneously.

h(0) = 020022221 h(1) = 011111221 h(2) = 010202110 h(3) = 010022112 h(4) = 000022121

Square-free doubled patterns with at most 4 variables

Here we show Theorem 5, that is, every square-free doubled pattern with at most 4 variables is 2-avoidable. We list them as follows:

• Among patterns that are equal up to letter permutation, we only list the lexicographically least.

• If a pattern is distinct from its mirror image, we only list the lexicographically least among the pattern and its mirror image.

• We do not list patterns that contain a square-free doubled pattern as a strict factor.

• We do not list patterns that contain an occurrence of ABACBC, ABCACB, ABCBABC, ABCDBDABC, ABCDBDAC, ABACDCBD, or their mirror image.

• We do not include the seven sporadic patterns on 4 variables from Table 1, which are 2-avoidable. • We denote by w k any infinite RT (k) + -free word over Σ k .

• If the avoiding word is a pure morphic word m ω (0), then m is given.

• If the avoiding word is a morphic word f (m ω (0)), then we write m; f .

• If the avoiding word is of the form f (w k ), then we write w k ; f . The proofs that a (pure) morphic word avoids a pattern use Cassaigne's algorithm [START_REF] Cassaigne | An Algorithm to Test if a Given Circular HD0L-Language Avoids a Pattern[END_REF] and the proofs that a morphic image word a Dejean word avoids a pattern use the technique described in Section 3.

Growth rate of ternary words avoiding a doubled pattern

Theorem 6 obviously holds for p = AA. Without loss of generality, we do not need to consider a doubled pattern p that contains an occurrence of another doubled pattern. In particular, p is square-free. So we need to show that GR 3 (p) is at least GR 3 (AA), which is close to 1.30176 [START_REF] Shur | Growth rates of complexity of power-free languages[END_REF].

If p is 2-avoidable, then p is avoided by sufficiently many ternary words.

By Lemma 4.1 in [7], λ(p) = 2 implies that GR 3 (p) 2 1
2 > GR 3 (AA). Thus, Conjecture 3 implies Theorem 6. By Theorem 5, we can assume that v(p)

5. We can also rule out the three sporadic patterns on 5 variables from Table 1, which are 2-avoidable.

According to the partition of the set of doubled patterns mentioned in the introduction, there remains to consider the doubled patterns p whose 3-avoidability has been obtained via the power series method. In that case, we even get GR 3 (p) > 2 > GR 3 (AA).

Conclusion

Unlike classical formulas, we know that there exist avoidable formulas with reversal of arbitrarily high avoidability index [START_REF] Ochem | A family of formulas with reversal of arbitrarily high avoidability index[END_REF]. Maybe doubled patterns and nice formulas are easier to avoid. We propose the following open problems.

• Are there infinitely many doubled patterns up to ≃ that are not 2avoidable?

• Is there a nice formula up to ≃ that is not 3-avoidable?

A first step would be to improve Theorem 2 by generalizing the 3-avoidability of doubled patterns with reversal to doubled patterns up to ≃. Notice that the results in Sections 3 and 5 already consider avoidability up to ≃. However, the power series method gives weaker results. Classical doubled patterns with at least 6 variables are 3-avoidable because 1 -3x + 3x 2 1 -3x 2 v has a positive real root for v 6. The (basic) power series for doubled patterns up to ≃ with v variables would be

1 -3x + 6x 2 1 -3x 2 - 3x 2 + 3x 4 1 -3x 4 v .
The term 6x 2 1-3x 2 counts for twice the term 3x 2 1-3x 2 in the classical setting, for h(V ) and h(V ) R . The term 3x 2 +3x 4 1-3x 4 corrects for the case of palindromic h(V ), which should not be counted twice. This power series has a positive real root only for v 10. This leaves many doubled patterns up to ≃ whose 3-avoidability must be proved with morphisms.

Looking at the proof of Theorem 2, we may wonder if a doubled pattern with reversal is always easier to avoid than the corresponding classical pattern. This is not the case: backtracking shows that λ(ABCA R C R B) = 3, whereas λ(ABCACB) = 2 [START_REF] Ochem | A generator of morphisms for infinite words[END_REF].

To get a more precise version of both conjectures 3 and 4, we plan to obtain the (conjectured) list of all 2-unavoidable doubled patterns, which should be a finite list containing no square-free pattern.

3 + 4 += 3 + 4 3

 3434 , 25 -freeness of the g k -image of every5 -free word of length at most 32. Then we check that g k (w 5 ) is 13-directed by inspecting the factors of g k (w 5 ) of length 13. For contradiction, suppose that g k (w 5 ) contains an occurrence h of ABCBA.CAC up to ≃. Let us write a= |h(A)|, b = |h(B)|, c = |h(C)|.Suppose that a 25. Since g k (w 5 ) is 13-directed, all occurrences of h(A) are identical. Then h(ABCBA) is a repetition with period |h(ABCB)| 25. So the 4 , 25 -freeness implies the bound 2a+2b+c a+2b+c , that is, a b + 1 2 c. In every case, we have a max b + 1 2 c, 24 .

Table 1

 1

	: The seven sporadic patterns on 4 variables and the three sporadic
	patterns on 5 variables
	Doubled pattern	Avoidability exponent
	ABACBDCD	1.381966011
	ABACDBDC	1.333333333
	ABACDCBD	1.340090632
	ABCADBDC	1.292893219
	ABCADCBD	1.295597743
	ABCADCDB	1.327621756
	ABCBDADC	1.302775638
	ABACBDCEDE 1.366025404
	ABACDBCEDE 1.302775638
	ABACDBDECE 1.320416579

Table 2

 2 contains every pattern p in this list with an infinite binary word avoiding p. Let us detail how to read

Table 2 :

 2 • A morphism is m given in the format m(0)/m(1)/... • We denote by b 2 , b 4 , b 5 the famous morphisms 01/10, 01/21/03/23, 01/23/4/21/0, respectively.

Table 2 :

 2 Binary words avoiding doubled patterns

	Doubled pattern	Avoiding word
	ABCABDCBD	w 5 ; 0010101110/0010011000/0001111110/0001110101/0000011001
	ABCACDCBD	w 5 ; 000101010111/000100110111/000011001111/000001011111/000000111111
	ABCBABDBCBD	b 4 ; 01/00/10/11
	ABCBADCBCD	b 4 ; 0000/0011/1111/1010
	ABCBDACBCD	b 4 ; 01/00/10/11
	ABCBDBCACBCD	b 2
	ABCBDCBACBCD	b 4 ; 1000/0111/0110/0010
	ABCDACBD	w 5 ; 00100110111111000/00100110111011000/
		00011110110101010/00001111111011010/00001010101011111
	ABCDBACBD	w 6 ; 010101111100/010010100000/001001110111/000111111101/000101010111/000100011011
	ABCDBADC	w 5 ; 10001000101111101010110/00000110110101000111111/
		00000101011100100111111/00000011101010010011111/00000011011000101011111
	ABCDBCBACBD	001/011
	ABCDCACBD	b 5 ; 0011110110000/0011010100110/0001111100111/0001110001000/0001101101111
	ABCDCBABCD	avoided by every 3 2	+ , 4 -free binary word [6]
	ABCDCBCACBD	b 5 ; 00/01/10/110/111
	ABACDCBCD	w 5 ; 10011011000/01011111000/00111010100/00100100111/00001111111
	ABCABDBCD	w 5 ; 0010111111/0010011110/0010011100/0000010101/0000001101
	ABCADBCBD	w 5 ; 001011010000/001001111000/000110011001/000011101010/000010111111
	ABCADCBCD	w 5 ; 001101111000/001101101000/001001111111/000101110101/000001100101
	ABCBADBDC	w 5 ; 0011111110110/0001010111100/0000101101110/0000011010111/0000001011111
	ABCBDABCD	w 4 ; 1111/1101/0010/0000
	ABCBDABDC	w 5 ; 101110000001/101100100001/011111110100/010001111110/010001101110
	ABCBDACBD	b 5 ; 00/01/10/110/111
	ABCBDADBC	w 5 ; 00110111010010/00110000000010/00011111111011/00011110101000/00010101100011
	ABCBDADBDC	b 5 ; 111/101/000/011/001
	ABCBDBABDBC	b 5 ; 00/01/10/110/111
	ABCBDBABDC	b 5 ; 000/011/001/111/101
	ABCBDBACBCD	b 4 ; 01/00/10/11
	ABCBDBACD	w 5 ; 0001111101010/0001110111000/0001011111111/0000111001111/0000011011001
	ABCBDBADBDC	011/100
	ABCBDBADC	00111101110000/00111011000010/00111010100000/00011001001111/00010101111111
	ABCBDBCABCD	b 5 ; 00/01/10/110/111
	ABCBDBCACBD	b 5 ; 00/01/10/110/111
	ABCBDBCAD	w 5 ; 00011110110011/00011101101001/00011011010100/00010111111110/00000011111010
	ABCBDBCBABCD	b 4 ; 000/111/10/01
	ABCBDBCBACBCD	b 2
	ABCBDBCBACBD	b 4 ; 00/01/10/11
	ABCBDBCBACD	001/110
	ABCBDCABCD	b 5 ; 00/10/111/01/011
	ABCBDCABD	w 5 ; 10000000011/01111010010/01101100010/01011111110/00001010101
	ABCBDCACBD	b 5 ; 111/101/000/100/110
	ABCBDCBABCD	b 5 ; 00/01/10/110/111
	ABCBDCBACBD	b 5 ; 00/01/10/110/111
	ABCBDCBACD	b 5 ; 00/01/10/1100/111
	ABCBDCBAD	w 5 ; 001101101100/001011111111/001001111100/000110010100/000001110100
	ABCBDCBCABD	b 4 ; 000/111/10/01
	ABCBDCBCAD	w 5 ; 1111100/1100110/0110101/0010010/0000101
	ABCDADCB	w 5 ; 0000010001111110101000100111110111/0000010001111100100001100101101111/
		0000001001111111010000110101111011/0000001001111110110100010101111011/
		0000000101110010000111111010010111
	ABCDBABDC	w 5 ; 0011111110101/0010110111010/0010101110000/0000111111001/0000110110001
	ABCDBADBC	w 5 ; 01011111111/01001000111/00101000011/00011110101/00000001011
	ABCDBCACBD	b 5 ; 101/000/110/111/100
	ABCDBCBACD	w 5 ; 0110101/0100000/0011110/0001111/0000111
	ABCDBCBAD	w 5 ; 00010111001010/00001111010101/00001110001010/00001100111111/00001100010110
	ABCDBDAC	w 5 ; 00000011011011001110001111011010110000101111010100100101110111/
		00000011011011000010011110110101000010101111010100100101110111/
		00000010110011110101010011000111000010101111010100100101110111/
		00000010101101101000100011111101000010101111010100100101110111/
		00000010101011001110001111010011000010101111010100100101110111
	ABCDBDADBC	w 5 ; 01111101/00111100/00111001/00110110/00000101
	ABCDCACDB	w 5 ; 00110001000110/00101011111110/00011111010011/00010101011111/00000001010011

The formula ABA.BCB.CAC seems also avoided up to ≃ by the Hall-Thue word, i.e., the fixed point of 0 → 012; 1 → 02;

→ 1.[START_REF] Cassaigne | An Algorithm to Test if a Given Circular HD0L-Language Avoids a Pattern[END_REF] We mistakenly said in[START_REF] Ochem | On some interesting ternary formulas[END_REF] that ABCA.BCAB.CBAC is different from its reverse.


M Manceau

T E Wall

H Philip

A N Baranov

M R Tarbutt

R Teissier

B Darquié

Demonstration and frequency noise characterization of a 17 µm quantum cascade laser

We describe the properties of a continuous-wave room-temperature quantum cascade laser operating at the long wavelength of 17 µm. Long wavelength mid-infrared quantum cascade lasers offer new opportunities for chemical detection, vibrational spectroscopy and metrological measurements using molecular species. In particular, probing low energy vibrational transitions would be beneficial to the spectroscopy of large and complex molecules, reducing intramolecular vibrational energy redistribution which acts as a decoherence channel. By performing linear absorption spectroscopy of the v 2 fundamental vibrational mode of N 2 O molecules, we have demonstrated the spectral range and spectroscopic potential of this laser, and characterized its free-running frequency noise properties. Finally, we also discuss the potential application of this specific laser in an experiment to test fundamental physics with ultra-cold molecules.

Stimulated by the invention of the quantum cascade laser (QCL) [1], applications relying on midinfrared (MIR) radiations have progressed at a very rapid pace in recent years. These range from free-space optical communications [2][START_REF] Liu | SPIE Conference Proceedings[END_REF][START_REF] Corrias | [END_REF], gas sensing [5][6][7][8] and trace detection [9], and highresolution spectroscopy [10][11][12][13], to metrology and frequency referencing [14][15][16][17][18][19], as well as fundamental physics measurements [20][21][22]. Unlike MIR gas lasers, such as CO and CO 2 lasers, QCLs can provide broad and continuous frequency tuning over several hundreds of gigahertz. QCLs are also compact, robust and low-power devices compared to other more complex MIR sources based on frequency down conversion [23,24], such as optical parametric generators (OPG), oscillators (OPO) [25], or difference frequency generators (DFG) [26,27], less suited for field deployment. Moreover, QCLs can be easily interchanged and available wavelengths cover large parts of the MIR region from 2.6 [START_REF] Cathabard | Applied Physics Letters[END_REF] to 28 µm [START_REF] Ohtani | [END_REF], which is not the * benoit.darquié@univ-paris13.fr case of most of the other MIR sources, fiber [30] or crystalline (Cr:ZnSe, Tb:KPb 2 Cl 5 ) MIR lasers [31]are for example limited to the 2 to 5µm spectral region.

Distributed feedback (DFB) QCLs [32], which have a grating embedded in the laser cavity, are single longitudinal mode narrow-band lasers, and thus a solution of choice for molecular spectroscopy. However, until recently continuous wave (CW) DFB QCLs operating at room temperature were only available in the 4 to 11 µm window. Extending such technologies to longer wavelengths is important for a range of applications: (i) strong vibrational signatures of small hydrocarbons (such as ethene, ethane, acetylene, propane), of larger aromatics (such as BTEX -benzene, toluene, ethylbenzene, and xylenes), of nitrous oxide or uranium hexafluoride are found in the 12-18 µm spectral window [27,[33][34][35][36][START_REF] Elkhazraji | Proceedings of the Combustion Institute[END_REF]; in particular, it hosts the strongest absorption lines of C 2 H 2 , BTEX and UF 6 ; (ii) long wavelength (N and Q astronomical bands) QCLs would be valuable in radio-astronomy as local oscillators in heterodyne detectors [START_REF] Bourdarot | [END_REF]39]; (iii) MIR frequency standards and quantum simulators based on trapped ultra-cold diatomic molecules' vibrations are promising but the vibration wavelength of the few recently laser-cooled and/or trapped species such as SrF, CaF, YbF, BaF, YO all lie above 15 µm [40]; (iv) large polyatomic molecules suffer from non-radiative internal vibrational relaxation [41] (IVR) processes which greatly broadens rovibrational transitions ; bringing increasingly complex molecular systems within reach of precise spectroscopic measurements offer promising perspectives in astrophysics, earth sciences, quantum technologies, metrology and fundamental physics, but necessitates to work at increasingly lower transition energies at which IVR is correspondingly reduced [42,43]. In this paper, we report the characterization and operation of the longest wavelength room temperature CW DFB QCL technology [44]. Our source has been designed to operate at a wavelength of 17.2 µm, in coincidence with the vibration of calcium monofluoride, as it could constitute an enabling technology for a MIR frequency standard based on ultracold CaF samples [40].

The article is structured as follows: we describe the spectroscopy of the v 2 mode of N 2 O using the QCL, the first absorption spectroscopy reported at 17 µm wavelength using a QCL. We then present the measurement of the QCL frequency noise, using an N 2 O absorption line as a frequency discriminator. Finally, applications of the QCL are described, in particular the precise spectroscopy of ultra-cold molecules.

The active region of the QCL is formed from InAs/AlSb [44,50]. The laser chip is mounted on a Peltier-cooled module. The laser spectra and output power are shown on Fig. 1. Several milliwatts of optical power can be generated, over a frequency range of ∼ 3 cm -1 (∼ 100 GHz) by tuning the temperature and drive current. The QCL beam is collimated by a parabolic mirror mounted a few millimeters away from the laser chip.

We realized N 2 O absorption spectroscopy over the full tuning range of the QCL. There has hardly been any previous laser spectroscopy of N 2 O in this spectral region. The first laser spectroscopy of N 2 O around 17 µm was performed in 1978 by Reisfeld and Flicker [51] using a lead salt laser followed later on by the references [52,53]. However, these works were hampered by the poor laser performance, such as a broad emission bandwidth and mode hopping. Lead salt lasers present the user with other significant problems, including spectral properties that vary after temperature cycling. QCLs offer a much more reliable and precise alternative as we demonstrate in this article.

In order to explore the full frequency range of the QCL, seven spectral measurements were made, each recorded with different laser operating conditions. For these measurements, the laser temperature set-point was varied from -28.5°C to -2.6°C; for each temperature the unmodulated laser drive current was set around 525 mA. For each measurement the output frequency was scanned by applying a current ramp of amplitude ∼ ±0.5 mA and period 100 ms. In this way, N 2 O absorption data were recorded in the range from 580 cm -1 to 582.5 cm -1 . The absorption spectra were recorded with N 2 O pressure of 500 Pa in a 24 cm long gas cell using a liquid nitrogen-cooled photoconductive HgCdTe (MCT) detector. For each measurement, reference measurements were made in order to allow transmission spectra to be calculated. The first reference measurement was performed with the laser blocked, which allowed the MCT dark signal to be recorded. The second reference measurement was performed with the laser unblocked, but with the gas cell evacuated, which allowed the transmission of the gas cell itself to be measured (including the effects of etalon fringing). With these given by the N 14 N 14 O 16 isotopologue (abundance 99%). The blue sticks [45][46][47] are characterized by a better accuracy than the black sticks [47][START_REF] Maki | Wavenumber Calibration Tables From Heterodyne Frequency Measurements[END_REF][START_REF] Maki | Wavenumbers for calibration of IR spectrometers[END_REF]. The three main absorption lines belong to the P branch of the fundamental transitions of the v 2 bending mode (P8, P9 and P10 at 582.07, 581.24 and 580.4 cm -1 respectively), while other transitions correspond to hot bands of the same v 2 mode.

reference measurements, transmission spectra were generated, with fringing effects largely removed.

The frequency scale of each spectrum was calibrated using the NIST database Wavenumbers for Calibration of IR Spectrometers [47][START_REF] Maki | Wavenumber Calibration Tables From Heterodyne Frequency Measurements[END_REF][START_REF] Maki | Wavenumbers for calibration of IR spectrometers[END_REF]. For each spectrum around eight strong absorption features, covering the full frequency range of the spectrum, were selected for the calibration procedure. A Gaussian function was fitted to each of the selected features, in order to find the line centre in units of the scan data-point number. The known line centres from the NIST database (units of cm -1 ) were then plotted against the uncalibrated line centres, and a third order polynomial function was fitted to the line centre data. The polynomial function was then used to calibrate the spectrum frequency scale. The spectra were recorded with sufficient overlap to allow them to be combined into one spectrum, shown in Fig. 2, where the three large amplitude features in this spectrum correspond to the lines in the P branch of the v 2 fundamental mode (the bending mode), and all other features correspond to hot bands of the same mode.

We also characterized the frequency noise prop-erties of this 17 µm QCL. As illustrated in Fig. 3, the P9 absorption feature of the v 2 mode (581.24 cm -1 ) was used as a frequency-to-amplitude converter [15,54]. The P9 line is measured for a N 2 O pressure of 100 Pa, resulting in a large absorption signal and limited collision-induced broadening. The lineshape is fitted to a Voigt profile. The frequency scale is calibrated using the Doppler width as a reference. A FWHM of 63 MHz is obtained for the fitted Voigt profile. This is much larger than the linewidth at any time scale of the QCL, as will be shown after. This implies that the laser frequency noise is well within the linear response range of our molecular frequency-to-amplitude converter [55]. Once the line profile measured, the laser frequency is locked to the side of the P9 feature. The lock bandwidth was 1 Hz, chosen to stop slow drift of the laser frequency, but without suppressing higher frequency components. The amplitude noise generated by the molecular line frequency discriminator is measured with the MCT detector and processed by a Fast Fourier Transform (FFT) spectrum analyzer. The frequency-to-amplitude conversion coefficient is the derivative of the measured P9 rovibrational line profile shown in Fig. 3 at the position where the laser line is parked [15,54,56]. For the following frequency noise measurements, the 17 µm QCL is operated at a temperature of 258 K and a current of 570 mA.

The frequency noise PSD of the QCL is shown in Fig. 4, red curve. We also measured the contribution from the laser intensity noise (blue line in Fig. 4), obtained with the laser tuned far from any molecular resonance, as well as the contribution from a home-made low-noise current source (black line in Fig. 4) obtained by multiplying the driver's current noise spectrum by the laser DC current-to-frequency response of 240 MHz/mA [15]. This value is the local slope at 260 K and 570 mA of the measured QCL frequency shift versus driving current, obtained from the FTIR spectrum measurements (fig. 1b). The intensity and driver's contribution are negligibly small compared to the frequency noise, except at low frequencies (< 10 Hz) at which the laser driver current noise will contribute to the laser frequency noise.

At low frequencies ( 100 kHz) the QCL frequency noise (Fig. 4 red) is dominated by usual 1/ f noise .

However, for frequencies greater than 100 kHz, a noise plateau appears, as has been reported for other QCLs at shorter wavelengths [54,56]. This white noise level N w = 30.4 × 10 3 Hz 2 /Hz corresponds to an intrinsic Lorentzian FWHM linewidth of ∆ν l = πN w = 96 kHz. For frequencies greater than 500 kHz, the frequency noise PSD falls of rapidly due to the limited bandwidth of our photoconductive MCT detector. Following the theoretical work for a 3 level QCL described in reference [57], we calculated the expected FWHM intrinsic lorentzian linewidth of the 17 µm laser ∆ν l,th . The details of this calculation including a comparison with other QCLs are presented in the Supplementary Material. We find for this laser at the given operated conditions ∆ν l,th 400 Hz. The measured noise plateau gives therefore an intrinsic linewidth two orders of magnitude larger than the theoretical calculation. We do not have an explanation for this discrepancy. Measured or inferred intrinsic linewidth for QCLs at 4.3 and 10.6 µm [15,54,56] tend to agree with theoretical calculations, with reported values of the order of 100 Hz.

Using the frequency noise PSD, one can also estimate the lineshape and FWHM linewidth of the QCL including the dominant 1/ f noise below 100 kHz. The FWHM linewidth can be calculated with a good approximation using the β -separation line method as described in reference [58]. The β -separation line is shown in Fig. 4 as a green line. Noise components at frequencies greater than the cutoff defined by the crossing point between the β -separation line and the frequency noise PSD ( f c = 60 kHz) are discarded in the estimation of the laser linewidth. The estimated FWHM linewidth evolution with the integration time is shown in Fig. 5, solid red line. We find ∆ν = 240 kHz at 1 s integration time. The β -separation linewidth is not reported for small integration time (< 100 µs) approaching the cutoff (1/ f c = 16 µs) as the approximation discards high frequency noise components and therefore fails in estimating correctly the linewidth in this case [58]. To overcome the limitations of the β -separation line method we calculated the 17 µm laser lineshape (Fig. 5 inset) at various integration time from the frequency noise PSD following reference [59] and accounting for the integration time [15,60]. For integration times larger than 1 ms, the lineshape is approaching a Gaussian distribution due to the 1/ f noise contribution (Fig. 5 inset, blue and green lines). The corresponding FWHM linewidth are reported as square points on Fig. 5, agreeing reasonably well with the β -separation line method. The former method under-estimates the linewidth by 10% for pure 1/f noise [58]. A larger disagreement (20%) between the β -separation line method and the laser lineshape calculation is observed in our case owing to the contribution of the white noise plateau. The calculated FWHM linewidth decreases with decreasing integration time, reaches a minimum of 30 kHz at 33 µs integration. For smaller integration, the linewidth is limited by the measurement time and therefore increases. This new, narrow-linewidth laser offers new spectroscopic opportunities in the MIR, e.g. as the local oscillator of a heterodyne detector for astrophysical molecular detection at 17 µm [START_REF] Bourdarot | [END_REF]39], or the manipulation of bismuth spin states in silicon for solid-state quantum technology and atomic clock applications [START_REF] Saeedi | Thewalt[END_REF]. One of our goal is to extend to longer wavelengths, at which IVR is reduced, the frequency metrology methods for frequency stabilisation recently demonstrated for QCLs at 10 µm and below [14][15][16][17][18][19]. This opens perspectives for using increasingly complex polyatomic molecules to FIG. 5. FWHM linewidth as a function of integration time calculated from the frequency noise PSD presented in Fig. 4. Red line: β -separation line method, square points: FWHM linewidth inferred from a lineshape reconstruction. The inset shows the calculated QCL line shape for three integration times: 1 s (blue), 1 ms (green) and 33 µs (red).

perform tests of fundamental physics, e.g. to measure the energy difference between enantiomers of a chiral molecule, a signature of weak-interactionsinduced parity violation [21,[START_REF] Fiechter | Towards detection of the molecular parity violation in chiral Ru(acac)$_3$ and Os(acac)[END_REF], and a sensitive probe dark matter [START_REF] Gaul | [END_REF]. Longer wavelength QCLs are also necessary to develop frequency standards in the mid-infrared based on ultra-cold diatomic molecules and the QCL used for the present study has been designed to coincide with the vibration at 17.2 µm of CaF [64], one of the few molecules that can be laser cooled down to the microkelvin range [65]. A clock based on the fundamental vibrational transition of ultra-cold CaF molecules confined in an optical trap is currently under construction [40]. It is expected to have a linewidth below 10 Hz, a stability of 2 × 10 -15 at 1 s, and the potential to measure the stability of the electron-to-proton mass ratio to a fractional precision better than 10 -17 per year.

In conclusion, we have performed absorption spectroscopy of N 2 O to demonstrate the spectroscopic capabilities of a new QCL operating at 17 µm . This laser operates in a spectral region that is poorly covered by existing lasers, and its development opens new opportunities in atmospheric sensing and chemical detection, as well as in precise spectroscopic tests of fundamental physics. We have used this spectroscopy to probe the frequency characteristics of the laser, measuring the laser linewidth, the value of which disagrees with theoretical understanding of the noise associated with QCLs. This characterization of the frequency noise is a first step towards a frequency stabilization of this source for subsequent precise spectroscopy in this long wavelength region.

See the supplementary material for details on the intrinsic linewidth calculation as well as a comparison with reported data for other QCLs. TEW acknowledges funding from the Royal Society International Exchanges Scheme (grant IES\R3\183175), the Imperial College European Partners Fund and the Université Sorbonne Paris Nord Visiting Fellow Fund.

Appendix A: Supplementary material FIG. 6. Schematics of the quantum levels of a given potential well for a 3 level QCL. The radiative relaxation between level 3 and 2 producing photons is represented in red and characterized by a relaxation time τ r . The other relaxation paths described are non-radiative. The total relaxation time of level 3 is τ t = (1/τ r + 1/τ 32 + 1/τ 31 ) -1 .

In this supplementary material we describe the calculation of the theoretical intrinsic linewidth of the 17 µm laser, following the work by Yamanishi et al. [57] for a 3 level QCL as depicted on Fig. 6. The theoretical FWHM intrinsic linewidth ∆ν l,th of the 17 µm laser is given by

∆ν l,th = γβ e f f 4π(1 -ε) 1 I/Ith -1 + ε (1 + α 2 e ), (A1)
corresponding to equation (2) in reference [54], which is equivalent to eq. (16a) in reference [57]. ε = τ 21 τ 31 ητ t (τ 21 +τ 31 ) is a parameter depending on the relaxation times of the various levels and on the injection efficiency η of the charges in level The Henry linewidth enhancement factor α e is close to 0 for QCLs [1,66,67]. I and I th correspond to the injected and lasing threshold current. γ is the photon decay rate, β f f = β τ r /τ t effective coupling of the spontaneous emission, the ratio of spontaneous emission rate coupled into the lasing mode β τ r to the total relaxation rate of the upper level τ t . This number is typically small for QCLs due to very efficient nonradiative processes (τ r τ t ). This in terms explains the narrow intrinsic linewidth of QCLs due to a reduction of the noise associated to spontaneous emission. The order of magnitude of ∆ν l,th is mainly determined by the product γβ e f f . The values of the various parameters in eq.A1 are reported in table I for the 17 µm laser as well as for the QCLs of references [54,56] for comparison. Reference [54] and [56] used DFB QCLs, a 4.33 µm QCL cooled at liquid-nitrogen temperatures and a 4.36 µm QCL working at room-temperature respectively.

Following notations from Yamanishi et al [57], we give below the various physical quantities characterizing the 17 µm QCL necessary to derive its intrinsic linewidth and parameters presented in table I. The cavity of the 17 µm QCL is single mode (TM 00 ). The waveguide core thickness is t g = 5.2 µm, the core width w g = 14 µm and the cavity length L c = 3 mm. The cavity mode effective refractive index is n e f f = 3.34, the refractive index of the waveguide active material n g = 3.38, while the cladding and group indices are n c = 3 and n gr = 3.77 respectively. The optical confinement of the mode is such that Γ Con f ,y = 1 and Γ Con f ,z = 0.64. We find a z-oriented dipole moment of | φ 3 |z|φ 2 of 6.2 nm. The overall cavity losses are expected to be α tot = 3500 m -1 , which gives a photon decay rate of γ = 0.3 THz. The guided spontaneous relaxation is calculated to be τ rg = 790 ns (eq. (A10a) in [57]), while the spontaneous relaxation partly coupled to the free-space continuum mode is τ r f p = 92 ns (eq. (A6b) in [57]) and thus a total radiative lifetime τ r = 82 ns (eq. (A11) in [57]). With this, we calculate a coupling efficiency of spontaneous emission to the guide of β guide = 0.11 (eq. (A12) in [57]), and a coupling efficiency of spontaneous emission to a single longitudinal mode of β l = 0.007 (eq. (A13a) in [57]), wich gives a coupling efficiency of spontaneous emission into a single lasing mode β = β l × β guide = 7 × 10 -4 . The effective coupling efficiency is then β e f f = 1.9 × 10 -9 . The injection efficiency η of the charges in level 3 is measured to be 0.9. As for the experimental parameters, a current I = 570 mA was fed to the 17 µm QCL operating at a temperature T = 258 K, with a corresponding lasing threshold of I th = 480 mA. Finally, a theoretical intrinsic linewidth ∆ν l,th of 380 Hz is calculated, comparable to the two cases reported in the literature.

Reference [54] Reference [56] [54,56]. Reference [54] and [56] used DFB QCLs, a 4.33 µm QCL cooled at liquid-nitrogen temperatures and a 4.36 µm QCL working at room-temperature respectively.

FIG. 1

 1 FIG. 1. a) Optical output power and voltage versus drive current recorded for various QCL temperatures. b): Emission spectra, measured by a FTIR spectrometer for various QCL temperatures and drive currents.

5 FIG. 2 .

 52 FIG.2. Measured linear absorption spectrum of N 2 O (red curve) realised at a pressure of 500 Pa. The stick spectrum is taken from the NIST database and corresponds to transitions of various N 2 O isotopologues, the main contributions are given by the N 14 N 14 O 16 isotopologue (abundance 99%). The blue sticks[45][46][47] are characterized by a better accuracy than the black sticks[47][START_REF] Maki | Wavenumber Calibration Tables From Heterodyne Frequency Measurements[END_REF][START_REF] Maki | Wavenumbers for calibration of IR spectrometers[END_REF]. The three main absorption lines belong to the P branch of the fundamental transitions of the v 2 bending mode (P8, P9 and P10 at 582.07, 581.24 and 580.4 cm -1 respectively), while other transitions correspond to hot bands of the same v 2 mode.

  FIG. 3. QCL frequency noise measurement setup. A 24cm long cell filled at a N 2 O pressure P = 100 Pa is used as a frequency-to-intensity converter. The QCL frequency is locked to the side of the N 2 O P9 line (581.24 cm -1 ) of the v 2 vibrational bending mode. The lock bandwidth was 1 Hz to correct for slow frequency drifts without suppressing higher frequency components. Intensity fluctuations proportional to the laser frequency noise are measured with a liquid nitrogen-cooled photoconductive HgCdTe detector and processed by a Fast Fourier Transform (FFT) spectrum analyzer.

FWHMFIG. 4 .

 4 FIG. 4. Frequency noise power spectral density (PSD) of the 17 µm QCL (red line) and β -separation line (green line) to estimate the linewidth. The contributions of the laser intensity noise (blue line) and laser driver current noise (black line) are also shown for comparison. The laser intensity contribution has been recorded with the same QCL parameters (temperature, current) as in the frequency noise measurement. The optical power hitting the detector was attenuated to be equivalent to the case with molecular absorption.

FWHM

TABLE I .

 I 17 µm QCL τ 21 (s) 0.25 × 10 -12 0.15 × 10 -12 0.073 × 10 -12 τ 31 (s) 2 × 10 -12 1.79 × 10 -12 0.29 × 10 -12 Values of the parameters to calculate the intrinsic QCL linewidth given by eq.A1, comparison between the 17 µm QCLs and QCLs presented in references

	τ 32 (s)	3.4 × 10 -12	unknown	0.92 × 10 -12
	τ r (s)	7.5 × 10 -9	10 × 10 -9	52 × 10 -9
	τ t (s)	1.26 × 10 -12	1 × 10 -12	0.2 × 10 -12
	η	0.7	0.7	0.9
	β	9.5 × 10 -5	5 × 10 -5	7.2 × 10 -4
	γ (Hz)	1.2 × 10 11	1.2 × 10 11	3.1 × 10 11
	β e f f	1.6 × 10 -8	5 × 10 -9	1.9 × 10 -9
	ε	0.25	0.2	0.3
	I/I th	1.54	1.15	1.2
	∆ ∆ ∆ν ν ν l,th (Hz)	510	340	380