Philippe Schnoebelen

LMF Julien Veron

On arch factorization and subword universality for words and compressed words

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

Introduction

A subword of a given word is obtained by removing some letters at arbitrary places. For example, abba is a subword of abracadabra, as witnessed by the underlined letters. Subwords are a fundamental notion in formal language theory and in algorithmics but they are not as well-behaved as factors, a special case of subwords where the kept letters correspond to an interval inside the original word. 1 Words and languages can be characterised or compared via their subwords. For example, we can distinguish u 1 = nationalists from u 2 = antinationalists by the subword x = ino. Indeed, only u 2 has x as a subword. We say that x is a distinguisher (also, a separator ) between u 1 and u 2 . Observe that ino is a shortest distinguisher between the two words. 2 In applications one may want to distinguish between two similar DNA strings, or two traces of some program execution: in these situations where inputs can be huge, finding a short distinguishing subword requires efficient algorithms [START_REF] Simon | Words distinguished by their subwords[END_REF]. When considering the usual first-order logic of words (i.e., labelled linear orders), a distinguisher x can be seen as a Σ 1 formula separating the two words.

Definability by subwords. These considerations led Imre Simon to the introduction of piecewise-testable languages in his 1972 Phd thesis [START_REF] Simon | Hierarchies of Event with Dot-Depth One[END_REF][START_REF] Simon | Piecewise testable events[END_REF]: these languages can be defined entirely in terms of forbidden and required subwords.

In logical terms, this corresponds to BΣ 1 -definability, see [START_REF] Diekert | A survey on small fragments of first-order logic over finite words[END_REF]. Piecewise testability is an important and fundamental concept, and it has been extended to, among others, trees [START_REF] Bojańczyk | Piecewise testable tree languages[END_REF][START_REF] Goubault-Larrecq | Deciding piecewise testable separability for regular tree languages[END_REF], picture languages [START_REF] Matz | On piecewise testable, starfree, and recognizable picture languages[END_REF], or words over arbitrary scattered linear orderings [START_REF] Carton | Simon's theorem for scattered words[END_REF].

From a descriptive complexity point of view, a relevant measure is the length of subwords used in defining piecewise-testable languages, or in distinguishing between two individual words. Equivalently, the required length for these subwords is the required number of variables for the BΣ 1 formula. This measure was investigated in [START_REF] Karandikar | The height of piecewise-testable languages and the complexity of the logic of subwords[END_REF] where it is an important new tool for bounding the complexity of decidable logic fragments.

Subword universality. Barker, Day et al. introduced the notion of subword universality: a word u is k-universal if all words of length at most k are subwords of u [BFH + 20,DFK + 21]. They further define the subword universality index ι(u) as the largest k such that u is k-universal. Their motivations come, among others, from works in reconstructing words from subwords [START_REF] Day | k-spectra of weakly c-balanced words[END_REF] or computing edit distance [DFK + 21], see also the survey in [START_REF] Kosche | Combinatorial algorithms for subsequence matching: A survey[END_REF]. In [BFH + 20], the authors prove several properties of ι(u), e.g., when u is a palindrome, and further introduce the circular subword universality index ζ(u), which is defined as the largest ι(u ) for u a conjugate of u. Alternatively, ζ(u) can be seen as the subword universality index ι([u] ∼ ) for a circular word (also called necklace, or cyclic word), i.e., an equivalence class of words modulo conjugacy.

While it is easy to compute ι(u), computing ζ(u) is trickier but [BFH + 20] proves several bounds relating ζ(u) to the values of ι(u n ) for n ∈ N. This is leveraged in [START_REF] Fleischmann | Scattered factor universality -the power of the remainder[END_REF] where an O(|u| • |A|) algorithm computing ζ(u) is given. That algorithm is quite indirect, with a delicate and nontrivial correctness proof. Further related works are [START_REF] Kosche | Absent subsequences in words[END_REF] where, given that ι(u) = k, one is interested in all the words of length k + 1 that do not occur as subwords of u, [FHH + 22] where one considers words that are just a few subwords away from k-universality, and [START_REF] Kosche | Subsequences in bounded ranges: Matching and analysis problems[END_REF] where the question whether u has a k-universal factor of given length is shown to be NP-complete.

Our contribution. In this paper we introduce new tools for studying subword (circular) universality. First we focus on the arch factorizations (introduced by Hébrard [START_REF] Hébrard | An algorithm for distinguishing efficiently bit-strings by their subsequences[END_REF]) and show how arch jumping functions lead to simple proofs of combinatorial results on subword universality indexes, allowing a new and elegant algorithm for computing ζ(u). These arch-jumping functions are implicit in some published constructions and proofs (e.g., in [FK18,FGN21,KKMS21]) but studying them explicitly brings simplifications and improved clarity.

In a second part we give bilinear-time algorithms that compute the universality indexes ι and ζ for compressed words. This is done by introducing a compact subword universality signature that can be computed compositionally. These algorithms and the underlying ideas can be useful in the situations we mentioned earlier since long DNA strings or program execution traces are usually very repetitive, so that handling them in compressed form can entail huge savings in both memory and communication time.

More generally this is part of a research program on algorithms and logics for computing and reasoning about subwords [KS15,HSZ17,KS19,GLHK + 20]. In that area, handling words in compressed form raises additional difficulties. For example it is not known whether one can compute efficiently the length of a shortest distinguisher between two compressed words. Let us recall here that reasoning on subwords is usually harder than reasoning on factors, and this is indeed true for compressed words: While deciding whether a compressed X is a factor of a compressed Y is polynomial-time, deciding whether X is a subword of Y is intractable (in PSPACE and PP-hard, see [Loh12, Sect. 8]). However, in the special case where one among X or Y is a power word, i.e., a compressed word with restricted nesting of concatenation and exponentiation, the subword relation is polynomial-time, a result crucial for the algorithms in [START_REF] Ph | On flat lossy channel machines[END_REF] where one handles exponentially long program executions in compressed forms.

Outline of the paper. Section 2 recalls all the necessary definitions for subwords and universality indexes. Section 3 introduces the arch-jumping functions, relates them to universality indexes and proves some basic combinatorial results. Then Section 4 provides a simple algorithm for the circular universality index. In Section 5 we introduce the subword universality signature of words and show how they can be computed compositionally. Finally Section 6 considers SLPcompressed words and their subword universality indexes.

Basic notions

Words and subwords. Let A = {a, b, . . .} be a finite alphabet. We write u, v, w, s, t, x, y . . . for words in A * . Concatenation is denoted multiplicatively while ε denotes the empty word. When u = u 1 u 2 u 3 we say that u 1 is a prefix, u 2 is a factor, and u 3 is a suffix, of u. When u = vw we may write v -1 u to denote w, the suffix of u one obtains after removing its v prefix. When u = v 0 w 1 v 1 w 2 • • • w n v n , the concatenation w 1 w 2 • • • w n is a subword of u, i.e., a subsequence obtained from u by removing some of its letters (possibly none, possibly all). We write u v when u is a subword of v.

A word u = a 1 • • • a has length , written |u| = , and we let A(u) def = {a 1 , . . . , a } denote its alphabet, a subset of A. We let Cuts(u) = {0, 1, . . . , } ⊆ N denote the set of cutting positions inside u, i.e., positions between u's letters, where u can be split: for 0 ≤ i ≤ j ≤ , we let u(i, j) denote the factor a i+1 a i+2 • • • a j . With this notation, u(0, j) is u's prefix of length j, and u(i, ) is the suffix (u(0, i)) -1 u. Note also that u(i, i) = ε and u(i, j) = u(i, k) u(k, j) whenever the factors are defined. If u = u 1 u 2 , we say that u 2 u 1 is a conjugate of u. For i ∈ Cuts(u), the i-th conjugate of u is u(i, ) u(0, i) and is denoted by

u ∼i . Finally u R def = a • • • a 1 denotes the mirror of u.
Rich words and arch factorizations. A word u ∈ A * is rich if it contains at least one occurrence of each letter a ∈ A, otherwise we say that it is incomplete.

A rich word having no rich strict prefix is an arch. The mirror of an arch is called a co-arch (it is generally not an arch). Observe that an arch (or a co-arch) necessarily ends (respectively, starts) with a letter that occurs only once in it.

The arch factorization of u, introduced by Hebrard [Héb91], is a decomposition u = s 1 • • • s m • r of u into m + 1 factors given by the following: -if u is not rich then m = 0 and r = u, -otherwise let s 1 be the shortest prefix of u that is rich (it is an arch) and let s 2 , . . . , s m , r be the arch factorization of the suffix (s 1 ) -1 u.

We write r(u) for the last factor in u's factorization, called the rest of u. For example, with A = {a, b, c}, the arch factorization of u ex = baccabbcbaabacba is bac • cab • bcba • abac • ba, with m = 4 and r(u ex ) = ba. Thus the arch factorization is a leftmost decomposition of u into arches, with a final rest r(u).

There is a symmetric notion of co-arch factorization where one factors u as u = r • s 1 • • • s m such that r is incomplete and every s i is a co-arch, i.e., a rich factor whose first letter occurs only once.

All the above notions assume a given underlying alphabet A, and we should speak more precisely of "A-rich" words, "A-arches", or "rest r A (u)". When A is understood, we retain the simpler terminology and notation.

Subword universality. In [BFH + 20], Barker et al. define the subword universality index of a word u, denoted ι A (u), or just ι(u), as the largest m ∈ N such that any word of length m in A * is a subword of u.

It is clear that ι(u) = m iff the arch factorization of u has m arches. Hence one can compute ι(u) in linear time simply by scanning u from left to right, keeping track of letter appearances in consecutive arches, and counting the arches [BFH + 20, Prop. 10]. Using that scanning algorithm for ι, one sees that the following equalities hold for all words u, v:

ι(u v) = ι(u) + ι r(u)v , r(u v) = r r(u)v . (1)
Barker et al. further define the circular subword universality index of u, denoted ζ(u), as the largest ι(u ) for u a conjugate of u. Obviously, one always has ζ(u) ≥ ι(u). Note that ζ(u) can be strictly larger that ι(u), e.g., with A = {a, b} and u = aabb one has ι(u) = 1 and ζ(u) = 2. These descriptive complexity measures are invariant under mirroring of words, i.e., ι(u R ) = ι(u) and ζ(u R ) = ζ(u), and monotonic w.r.t. the subword ordering:

u v =⇒ ι(u) ≤ ι(v) ∧ ζ(u) ≤ ζ(v) .
(2)

The behaviour of ζ can be deceptive. For example, while ι is superadditive, i.e., ι(uv) ≥ ι(u) + ι(v) -just combine eqs. (1) and (2)-we observe that ζ(uv) < ζ(u) + ζ(v) can happen, e.g., with u = ab and v = bbaa.

Arch-jumping functions and universality indexes

Let us fix a word w = a 1 a 2 • • • a L of length L. We now introduce the α and β arch-jumping functions that describe the reading of an arch starting from some position inside w. For i ∈ Cuts(w), we let

α(i) = min{j | A w(i, j) = A}, β(j) = max{i | A w(i, j) = A}.
These are partial functions: α(i) and β(j) are undefined when w(i, L) or, respectively, w(0, j), does not contain all the letters from A. See Figure 1 for an illustration. The following properties are easily seen to hold for all i, j ∈ dom(α):

α(i) ≥ i + |A| , i ≤ j =⇒ α(i) ≤ α(j) , (3)
β(α(i)) ≥ i , α(β(α(i))) = α(i) . (4)
Since β is a mirror version of α, it enjoys similar properties that we won't spell out here.

Remark 3.1. As will be seen in the rest of this section, the arch jumping functions are a natural and convenient tool for reasoning about arch factorizations. Similar concepts can certainly be found in the literature. Already in [START_REF] Hébrard | An algorithm for distinguishing efficiently bit-strings by their subsequences[END_REF], Hébrard writes p(n) for what we write α n (0), i.e., the n-times iteration α(α(

• • • (α(0)) • • • ))
of α on 0: the starting point for the p(n)'s is fixed, not variable. In [START_REF] Fleischer | Testing Simon's congruence[END_REF], Fleischer and Kufleitner use rankers like X a and Y b to jump from a current position in a word to the next (or previous) occurrence of a given letter, here a and b: this can specialise to our α and β if one knows what is the last letter of the upcoming arch. In [START_REF] Kosche | Absent subsequences in words[END_REF] minArch corresponds exactly to our α, but there minArch is a data structure used to store information, not a notational tool for reasoning algebraically about arches.

Subword universality index via jumping functions

The connection between the jumping function α and the subword universality index ι(w) is clear:

ι(w) = max n α n (0) is defined . ( 5
)
For example, w in Figure 1 has α 3 (0) = 10 = |w| so ι(w) = 3. We can generalise Equation (5): ι(w) = n implies α p (0) ≤ β n-p (|w|) for all p = 0, . . . , n, and the reciprocal holds. We can use this to prove the following:

Proposition 3.2. ι(u v) ≤ ι(u) + ι(v) + 1.
Proof. Write n and n for ι(u) and ι(v). Thus, on w = u v with L = |u| + |v|, one has α n+1 (0) > |u| and β n +1 (L) < |u|. See Fig. 2. Hence ι(w) < n + n + 2. u v

0 |u| L α(0) α 2 (0) α 3 (0) α n (0) • • • β(L) β 2 (L) β n (L) • • • α β ? ? Fig. 2. Comparing ι(u v) with ι(u) + ι(v).
We can also reprove a result from [BFH + 20]:

Proposition 3.3. ι(u u R ) = 2ι(u). Proof. Write n for ι(u). When w = u u R and L = |w|, the factor w α n (0), β n (L) is r(u) • r(u) R hence is not rich. Thus α n+1 (0) > |u| + |r(u) R | = β n (L), entailing ι(u u R ) < 2n + 1.

Subword circular universality index via jumping functions

The jumping functions can be used to study the circular universality index ζ(u). For this we consider the word w = u u obtained by concatenating two copies of u, so that L = 2 . Now, instead of considering the conjugates of u, we can consider the factors w(i, i + ) of w: see Figure 3.

s1 s2 s3 • • • sm r s1 s2 s3 • • • sm r 0 λ 1 λ 2 λ m-1 λm λ 1 + λ 2 + 2 i i + u u α Fig. 3. Computing ι(u ∼i ) on w = u 2 .
This leads to a characterisation of ζ(u) in terms of α on w = u u:

ζ(u) = max 0≤i< max n α n (i) ≤ i + (6) or, using u ∼ = u ∼0 , = max 0<i≤ max n α n (i) ≤ i + . (7
(u) -1 ≤ ι(u ) ≤ ι(u) + 1. (b) If furthermore r(u) = ε then ι(u ) ≤ ι(u). Proof. Let s 1 • • • s m •
r be the arch factorization of u and assume that u = u ∼i as depicted in Figure 3. (a) If the position i falls inside some arch s p of u (or inside the rest r) we see that

s p+1 • • • s m • s 1 • • • s p-1 is a subword of u hence ι(u ) ≥ m -1. This gives ι(u) -1 ≤ ι(u ),
and the other inequality is obtained by exchanging the roles of u and u . (b) If furthermore r = ε, then λ p-1 ≤ i < λ p for some p. Looking at u as a factor of w = u 2 (and assuming that α m+1 (i) is defined) we deduce α m+1 (i) ≥ α m+1 (λ p-1 ) = λ p + > i + . This proves ι(u ∼i ) < m + 1.

Corollary 3.5. (a) ι(u) ≤ ζ(u) ≤ ι(u) + 1. (b) Furthermore, if r(u) = ε, then ζ(u) = ι(u).

An O(|u| • |A|) algorithm for ζ(u)

The following crucial lemma shows that computing ζ(u) does not require checking all the conjugates u ∼i for 0 ≤ i < . By Equation (7) there exists some 0 < i 0 ≤ such that α n (i 0 ) ≤ i 0 + . We consider the sequence i

0 < i 1 < • • • < i n given by i k+1 = α(i k ). If i n ≤ then taking d = 1 works: monotonicity of α entails α n (d) ≤ α n (i 0 ) ≤ and we deduce ι(u ∼d ) ≥ n. Clearly d = 1 fulfils (b).
So assume i n > and let k be the largest index such that i k ≤ (hence

k < n). Since α( ) = + λ 1 (recall λ 1 def = |s 1 |), monotonicity of α entails i k+1 = α(i k ) ≤ + λ 1 , i.
e., i k+1 lands inside the first arch of the second copy of u in w.

Let now

d def = i k+1 -so that u ∼d = w(d, d + ) = w(d, i k+1 ). Since α n-k-1 (i k+1 ) = i n ≤ i 0 + , one has α n-k-1 (d) ≤ i 0 hence ι w(d, i 0 ) ≥ n-k-1.
We also have ι w(i 0 , i k+1 ) = k + 1 since i k+1 = α k+1 (i 0 ). This yields

ι(u ∼d ) = ι w(d, d + ) ≥ (n -k -1) + (k + 1) = n ,
entailing (a). For (b) observe that w(i k+1 -1, i k+1 ) is the last letter of an arch across the end of the first u in w to the beginning of the second u in w. Since it is the first occurrence of this letter in this arch, it is also in u. Since d is i k+1 shifted to the first copy of u, (b) is fulfilled. Observe that the above algorithm does not have to explicitly build u ∼d . It is easy to adapt any naive algorithm for ι(u) so that it starts at some position d and wraps around when reaching the end of u.

Subword universality signatures

In this section, we write ι * (u), r * (u), etc., to denote the values of ι(u), r(u), etc., when one assumes that A(u) is the underlying alphabet. This notation is less heavy than writing, e.g., ι A(u) (u), but it is needed since we shall consider simultaneously ι * (u) and ι * (v) when A(u) = A(v), i.e., when the two universality indexes have been obtained in different contexts.

When u is a word, we define a function S u on words via:

S u (x) = ι * (x u), A r * (x u) for all x such that A(u) ⊆ A(x). (8)
In other words, S u (x) is a summary of the arch factorization of x u: it records the number of arches in x u and the letters of the rest r * (x u), assuming that the alphabet is A(x u).

Note that S u (x) is only defined when A(u) ⊆ A(x), i.e., when at least one letter from u does not appear in x. With this restriction, S u (x) and S u (x ) coincide (or are both undefined) whenever A(x) = A(x ). For this reason, we sometimes write S u (B), where B is a set of letters, to denote any S u (x) with A(x) = B.

We are now almost ready to introduce the main new object: a compact data structure with enough information for computing S u on arbitrary arguments.

With a word u we associate e(u), a word listing the letters of u in the order of their first appearance in u. For example, by underlining the first occurrence of each letter in u = ccacabcbba we show e(u) = cab. We also write f (u) for the word listing the letters of u in order of their last occurrence: in the previous example f (u) = cba.

Definition 5.1. The subword universality signature of a word u is the pair Σ(u) = e(u), s u where s u is S u restricted to the strict suffixes of e(u).

Example 5.2. With u = aabac we have:

Σ(u) =        e(u) = abc s u =    ε → 1, ∅ c → 1, {a, c} bc → 2, ∅ in view of: ε • u = aabac • ε c • u = caab • ac bc • u = bca • abac • ε
NB: the strict suffixes of e(u) are ε, c and bc.

While finite (and quite small) Σ(u) contains enough information for computing S u on any argument x on any alphabet. One can use the following algorithm: Algorithm 5.3 (Computing S u (x) from Σ(u)). Given inputs x and Σ(u) = e(u), s u we proceed as follows: (a) Retrieve A(u) from e(u). Check that A(u) ⊆ A(x), since otherwise S u (x) is undefined. (b) Now with x ∈ dom(S u ), let y be the longest suffix of e(u) with A(y) ⊆ A(x) -necessarily y is a strict suffix of e(u)-and extract n y , B y from s u (y).

(c.1) If A(x) ⊆ A(u), return S u (x) = n y , B y . (c.2) Similarly, if n y = 1 return S u (x) = n y , B y . (c.3) Otherwise return S u (x) = 1, A(u) .
Proof (of correctness). Assume x ∈ dom(S u ). Since u contains a letter not appearing in x, the first arch of x u ends inside u, so let us consider the factorization u = u 1 u 2 such that x u 1 is the first arch of x u (see picture below, where e(u) is underlined).

• • • c • • • d • • • a • • • e • • • b • • • x u u 1 u 2 α * ? ?
Now u 1 has a last letter, say a, that appears only once in u 1 and not at all in x.

Observe that a letter b appears after a in e(u) iff it does not appear in u 1 , and thus must appear in x. Hence the y computed in step (b) is the suffix of e(u) after a (in the above picture y would be eb).

If A(x) ⊆ A(u) then y u 1 is rich, and is in fact an arch since its last letter, a, appears only once. So S u (x) and S u (y) coincide and step (c.1) is correct.

In case A(x) ⊆ A(u), both x and u contain some letters that are absent from the other word, so necessarily ι * (x u) = 1 and r * (x u) = u 2 . There only remains to compute A(u 2 ) from Σ(u). We know that s u (y) = n y , B y . If n y > 1 this means that u 2 contains at least another A(u)-arch, so A(u 2 ) = A(u) and step (c.3) is correct. If n y = 1 this means that y u only has one arch, namely y u 1 , and B y provides A(u 2 ): step (c.2) is correct in this case.

Remark 5.4 (Space and time complexity for Algorithm 5.3). For simplifying our complexity evaluation, we assume that there is a fixed maximum size for alphabets so that storing a letter a ∈ A uses space O(1), e.g., 64 bits. When storing Σ(u), the e(u) part uses space O(|A|). Now s u can be represented in space O(|A| log |u|) when e(u) and f (u) are known: it contains at most |A| pairs n x , B x where x is a suffix of e(u) and B x is always the alphabet of a strict suffix of f (u): x and B x can thus be represented by a position (or a letter) in e(u) and f (u). The n x values each need at most log |u| bits.

Regarding time, the algorithm runs in time O |x| + |Σ(u)| + |A(u)| .

Universality indexes from signatures

Obviously the signature Σ(u) contains enough information for retrieving ι * (u): this is found in s u (ε). More interestingly, one can also retrieve ζ * (u): Factor u as u = u 1 u 2 r such that x u 1 is the first arch of x u and such that r = r * (x u) is its rest. Then u 2 contains m arches and B x = A(r). Let now u def = r u 1 u 2 . We claim that ι * (u ) = m + 1. Indeed r u 1 is rich since x u 1 is rich and A(x) ⊆ A(r), so ι * (r u 1 u 2 ) ≥ m + 1. Since u and u are conjugates, we deduce ζ * (u) = ι * (u ) = m + 1 from Corollary 3.5.(a). (⇒): assume ζ * (u) = m + 1. By Lemma 4.1 we know that ι * u ∼i = m + 1 for some position 0 < i ≤ λ 1 falling just after a first occurrence of a letter in u. Looking at factors of w = u u as we did before, we have α m+1 (i) ≤ i + , leading to

j def = α m (i) ≤ (see picture below). b • • • a • • • d • • • b • • • a • • • d • • • 0 λ 1 λ 2 λm λ 1 + 2 i j i + u u
α Define now x as the suffix of e(u) that contains all letters in u(i, λ 1 ), that is, all underlined letters to the right of i. This is a strict suffix since i > 0. Now x u(0, i) is rich, and u(i, j) is made of exactly m arches, so ι * (x u) = n x = m + 1 and r * (x u) = u(j, ).

Then B x = A u(j, ) and w(j, i+ ) is rich, so w(j, ) contains all letters missing from w(i, i + ) = u(0, i). In other words B x ⊇ A(x), concluding the proof.

Combining signatures

Subword universality signatures can be computed compositionally.

Algorithm 5.7 (Combining signatures). The following algorithm takes as input the signatures Σ(u) and Σ(v) of any two words and computes Σ(u v):

(a) Retrieve A(u) and A(v) from e(u) and e(v), then compute e(u v) as e(u) e where e is the subword of e(v) that only retains the letters from A(v) A(u).

(b) Consider now any strict suffix x of e(u v) and compute s u v (x) as follows:

(b.1) If A(v) ⊆ A(x) ∪ A(u) then let s u v (x) def = S v x e(u) , using Algorithm 5.3. (b.2) If A(v) ⊆ A(x) ∪ A(u), then A(u) ⊆ A(x). Write n, B for s u (x): (b.2.1) If now A(v) ∪ B = A(x) ∪ A(u) then let s u v (x) def = n, A(v) ∪ B . (b.2.2) Otherwise retrieve s v (B) = n , B and let s u v (x) def = n + n , B .

Proof (of correctness).

Step (a) for e(u v) is correct. In step (b) we want to compute S u v (x). Now x (u v) = (x u) v so S u v (x) coincides with S v (x u) when the latter is defined . This is the case in step (b.1) where one computes S v (x u) by replacing x u with x e(u), an argument with same alphabet (recall that the algorithm does not have access to u itself). In step (b.2) where S v (x u) is not defined, computing S u (x) provides n and B = A(r) for the arch factorization

x u = s 1 • • • s n • r of x u.
We can continue with the arch factorization of r v and combine the two sets of arches if these factorizations rely on the same alphabet: this is step (b.2.2). Otherwise, r v only uses a subset of the letters of x u. There won't be a new arch, only a longer rest:

r * (x u v) = r v. Step (b.2.1) is correct. Note that Algorithm 5.7 runs in time O |A(u v)| + |Σ(u)| + |Σ(v)| and that the result has linear size |Σ(u v)| = O(|Σ(u)| + |Σ(v)|).

Universality indexes for SLP-compressed words

We are now ready to compute the universality indexes of SLP-compressed words. Recall that an SLP X is an acyclic context-free grammar in Chomsky normal form where furthermore each non-terminal has only one production rule, i.e., the grammar is deterministic (see survey [START_REF] Lohrey | Algorithmics on SLP-compressed strings: A survey[END_REF]). SLPs are the standard mathematical model for compression of texts and files and, modulo polynomial-time encodings, it encompasses most compression schemes used in practice.

Formally, an SLP X with m rules is a list N 1 → ρ 1 ; • • • ; N m → ρ m of production rules where each right-hand side ρ i is either a letter a from A or a concatenation N j N j of two nonterminals with j, j < i. It has size |X| = O(m log m) when A is fixed.

Each nonterminal N i encodes a word, its expansion, given inductively via:

exp(N i ) def = a if ρ i = a, exp(N j ) exp(N j ) if ρ i = N j N j .
Finally, the expansion exp(X) of the SLP itself is the expansion exp(N m ) of its last nonterminal. This is a word (or file) of length 2 O(|X|) and one of the main goals in the area of compressed data science is to develop efficient methods for computing relevant information about exp(X) directly from X, i.e., without actually decompressing the word or file.

In this spirit we can state:

Theorem 6.1. The universality indexes ι exp(X) and ζ exp(X) can be computed from an SLP X in bilinear time O |A| • |X| .

Proof. One just computes Σ exp(N 1 ) , . . . , Σ exp(N k ) for the non-terminals N 1 , . . . , N k of X. If N i is associated with a production rule N i → N i1 N i2 , we compute Σ exp(N i ) by combining Σ exp(N i1 ) and Σ exp(N i2 ) via Algorithm 5.7 (recall that i 1 , i 2 < i since the grammar is acyclic). If N i is associated with a production N i → a for some a ∈ A, then Σ exp(N i ) = Σ(a) is trivial. In the end we can extract the universality indexes of exp(X), defined as exp(N k ), from Σ exp(N k ) using Corollary 5.6. Note that all signatures have size O(|A| • |X|) since for any u = exp(N i ), log |u| is in O(|X|). With the analysis of Algorithm 5.7 and Corollary 5.6, this justifies the claim about complexity.

Conclusion

We introduced arch-jumping functions and used them to describe and analyse the subword universality and circular universality indexes ι(u) and ζ(u). In particular, this leads to a simple and elegant algorithm for computing ζ(u).

In a second part we defined the subword universality signatures of words, a compact data structure with enough information for extracting ι(u) and ζ(u). Since one can efficiently compute the signature of u v by composing the signatures of u and v, we obtain a polynomial-time algorithm for computing ι(X) and ζ(X) when X is a SLP-compressed word. This raises our hopes that one can compute some subword-based descriptive complexity measures on compressed words, despite the known difficulties encountered when reasoning about subwords.

Fig. 1 .

 1 Fig. 1. Arch-jumping functions α, β for A = {a, b, c} and w = aabcbcaabc.

)

  Bounding ζ(u). For k = 0, . . . , m, we write λ k for the cumulative length |s 1 • • • s k | of the k first arches of u, i.e., we let λ k def = α k (0). The following Lemma and its corollary are a version of Lemma 20 from [BFH + 20] but we give a different proof. Lemma 3.4. Let u and u be two conjugate words. (a) ι

Lemma 4. 1 .

 1 Let u = a 1 • • • a be a rich word with arch factorization s 1 • • • s m •r. (a) There exists some 0 < d ≤ λ 1 def = |s 1 | such that ζ(u) = ι(u ∼d ). (b) Furthermore, there exists a ∈ A such that d = min{i | a i = a}, i.e., d can be chosen as a position right after a first occurrence of a letter in u. Proof. Let n = ζ(u). For (a) it is enough to show that ι(u ∼d ) ≥ n for some d ∈ (0, λ 1 ].

  Algorithm 4.2 (Computing ζ(u)). For each position d such that u(d -1, d) is the first occurrence of a letter in u, one computes ι(u ∼d ) (in time O(|u|) for each d), and returns the maximum value found. The correctness of this algorithm is given by Lemma 4.1 (if u is not rich, ζ(u) = 0 and this will be found out during the computation of ι(u ∼1 )). It runs in time O(|A| • |u|) since there are at most |A| values for d, starting with d = 1. There are two heuristic improvements that can speed up the algorithm 3 : -As soon as we have encountered two different values ι(u ∼d ) = ι(u ∼d ), we can stop the search for a maximum in view of corollary 3.5.(a). For example, for u = aabaccb, the first occurrences of a, b, and c, are with d = 1, 3 and 5. So one starts with computing ι(u ∼1 ) = ι(abaccb a) = 2. Then one computes ι(u ∼3 ) = ι(accb aab) = 1. Now, and since we have encountered two different values, we may conclude immediately that ζ(u) = 2 without the need to compute ι(u ∼5 ). -When computing some ι(u ∼d ) leads us to notice r(u ∼d ) = ε, we can stop the search in view of corollary 3.5.(b). For example, and again with u = aabaccb, the computation of ι(u ∼1 ) led us to the arch-factorization u ∼1 = abac • cba • ε, with 2 arches and with r(u ∼1 ) = ε. We may conclude immediately that ζ(u) = ι(u ∼1 ) = 2 without trying the remaining conjugates.

Proposition 5. 5 .

 5 Let u be a word with ι * (u) = m. Then ζ * (u) = m + 1 iff there exists a strict suffix x of e(u) with s u (x) = n x , B x such that n x = m + 1 and A(x) ⊆ B x . Otherwise ζ * (u) = m. Proof. (⇐): assume s u (x) = m + 1, B x with A(x) ⊆ B x . Thus ι * (x u) = m + 1.

Corollary 5. 6 (

 6 Computing universality indexes from signatures). One can compute ι * (u) and ζ * (u) from Σ(u) in time (|A| + log |u|) O(1) . Actual implementations can use heuristics based on Lemma 3.4.(b): if s u (ε) = m, ∅ then ζ * (u) = m.

This is a very rare situation with the English lexicon, where different words almost always admit a length-2 distinguisher. To begin with, two words can already admit a length-1 distinguisher unless they use exactly the same set of letters.

Work partially supported by Labex DigiCosme (project ANR-11-LABEX-0045-DIGICOSME) operated by ANR as part of the program « Investissement d'Avenir » Idex Paris-Saclay (ANR-11-IDEX-0003-02).


Pablo Algarra
email: palgarra@comet-ingenieria.es@https

Iñigo Domínguez

José Nieto

Juan Fayos

Josh Wilkinson

Toby Cornwall

Jean-Michel Leger

Thomas Jager

Nanomagsat Deployable

Amagnetic Boom

la diffusion de documents scientifiques de niveau

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

Two of the payloads of the satellite, the Miniaturised Absolute Magnetometer (MAM) and the High Frequency Magnetometer (HFM) need to be kept away from any source of magnetic perturbance, such as the body of the satellite platform. To do that, a 3-meter deployable boom carries the MAM at its tip, and the HFM at mid-length. This boom must accomplish a set of really challenging requirements: it must be stowed, together with its payloads and harness, in a rather small 16 U platform filled with other equipment; it must be able to also deploy the harness connecting the payloads with the platform; it must be stiff enough (with a mass at is tip and another at mid-length) to allow the ADCS to operate… and it must be completely made of amagnetic, non-conductive materials. This paper presents the innovative solution developed by COMET and PROSIX, a modular deployable boom, passively motorised with amagnetic springs. An engineering model has been manufactured and successfully tested to deploy in TVAC conditions after surviving to vibrations tests, and its magnetic signature has been measured and found satisfactory.

Topic: Innovative Structures (damping, deployable, stable, active). Theme: Amagnetic, modular, deployable boom development. Preference for presentation: ORAL

Currently, this project is under a Risk Retirement Activity funded by ESA and led by OPEN COSMOS in a consortium with CEA-Leti, IPGP, PROSIX and COMET.


This paper's copyright is held by the author(s). It is published in these proceedings and included in any archive such as IEEE Xplore under the license granted by the "Agreement Granting URSI

On the future NanoMagSat LEO nanosatellite constellation observations of space environment

Gauthier Hulot* (1) , Pierdavide Coïsson (1) , Robin Duchêne (1) , Jean-Michel Léger (2) , Thomas Jager (2) , Lasse B. N. Clausen (3) , John L. Jørgensen (4) and Florian Deconinck (5) (1) Université Paris Cité, Institut de physique du globe de Paris, CNRS, Paris, France; e-mail: gh@ipgp.fr; coisson@ipgp.fr; duchene@ipgp.fr (2) CEA-Leti, Université Grenoble Alpes, MINATEC, Grenoble, France; e-mail: jean-michel.leger@cea.fr; thomas.jager@cea.fr (3) Department of Physics, University of Oslo, Oslo, Norway; e-mail: lasse.clausen@fys.uio.no (4) DTU Space, Technical University of Denmark, Kongens Lyngby, Denmark; e-mail: jlj@space.dtu.dk

(5) Open Cosmos Ltd., Didcot, United Kingdom; e-mail: flo@open-cosmos.com

The NanoMagSat project aims to deploy and operate a new constellation concept of three identical 16U gravitygradient stabilized nanosatellites with no propulsion but stable enough attitude control, using two inclined (~ 60°) and one polar LEO, for investigating both the Earth's magnetic field and the ionospheric environment. Drawing from the lessons learnt from the ESA Swarm mission, which it is designed to complement and succeed, it will also provide new science opportunities thanks to its innovative constellation design and miniaturized payload.

The 3-satellite constellation will cover all locations/local times (LT) and will further ensure that all LT at all locations between 60°N and 60°S will be covered in a little more than one month, much faster than Swarm, which NanoMagSat is also designed to complement for even better coverage, should Swarm still be in operation at the time of launch. Each satellite will carry the same innovative payload suite. This will first include an advanced Miniaturized Absolute scalar and self-calibrated vector Magnetometer (MAM) using the same principle as the ASM instrument successfully operated on the Swarm mission [START_REF] Léger | In-flight performance of the Absolute Scalar Magnetometer vector mode on board the Swarm satellites[END_REF], collocated (on an ultra-stable optical bench, at the tip of a deployable boom) with a set of star trackers (STR) also based on Swarm space heritage, to provide very accurate attitude restitution. It will further include a new compact High Frequency Magnetometer (HFM) [START_REF] Bertrand | A 4 He vector zero-field optically pumped magnetometer operated in the Earth-Field[END_REF] (at mid-boom), as well as a multi-Needle Langmuir Probe (m-NLP) with space heritage [START_REF] Hoang | The Multi-Needle Langmuir Probe System on Board NorSat-1[END_REF] and dual frequency GNSS receivers (all on the satellite body). This payload suite will acquire high-precision/resolution oriented absolute vector magnetic data at 1 Hz sampling rate (for global magnetic field modelling purposes), very low noise scalar and vector magnetic field data at 2 kHz (for ELF signal detection and down to decameter-scale local electrical currents monitoring), electron density data at 2 kHz (for very small-scale plasma density investigations), as well as electron temperature data at 1 Hz. GNSS receivers will also allow top-side TEC and ionospheric radiooccultation profiles to be recovered. Possibility of using the STRs to further recover the energetic proton omnidirectional flux (above 100 MeV), as recently demonstrated on Swarm [START_REF] Toldbo | Mapping high energy particles using augmented Star Trackers On-Board Swarm[END_REF] is also considered.

In this presentation, we will provide an overview of the current status and science objectives of the NanoMagSat project, with special emphasis on the possibility it will provide to investigate the ionospheric dynamics and environment, using both in-situ measurements and its ability to remotely sense the ionosphere using e.g., ELF whistlers, TEC and ionospheric radio-occultation profiles.

This project was proposed to ESA within the context of its SCOUT program, and is currently undergoing a 18 months Risk Retirement Activity phase funded by ESA and due to end in July 2023, aiming at implementation for a launch possibly as early as 2026.


Stephanie Evan
email: stephanie.evan@univ-reunion.fr

Jerome Brioude

Karen H Rosenlof

Ru-Shan Gao

Robert W Portmann

Rainer Volkamer

Christopher F Lee

Jean-Marc Metzger

Kevin Lamy

Paul Walter

Sergio L Alvarez

James H Flynn

Elizabeth Asher

Michael Todt

Sean M Davis

Troy Thornberry

Holger Vömel

Frank G Wienhold

Ryan M Stauffer

Luis Millán

Michelle L Santee

Lucien Froidevaux

William G Read

Rapid ozone loss following humidification of the stratosphere by the Hunga Tonga Eruption

The massive January 2022 Hunga Tonga-Hunga Ha'apai eruption produced major perturbations in atmospheric composition, increasing the stratospheric water burden by 10%. Fresh stratospheric volcanic plume measurements are rare, but unique circumstances allowed in-situ tropical profiles of H2O, aerosols, and O3 at the Maïdo Observatory within a week of the eruption. Analysis including remote sensing observations of O3, HCl, ClO and NO2 radicals shows chemical O3 loss (-0.5 ppmv between 25-30 km in a week) in the volcanic plume under unusually warm temperatures (T ~ 220 K at 28 km). This rapid loss indicates that heterogeneous chlorine activation is efficient on humidified volcanic aerosols. Although a rare occurrence, better understanding of these processes provide insight on ozone perturbations possible in a world with changing climate.

One-Sentence Summary:

The 2022 Hunga Tonga-Hunga Ha'apai eruption majorly perturbed tropical stratospheric water and aerosols producing rapid ozone loss in the plume.

Main Text:

Large explosive volcanic eruptions can impact the climate by injecting gases (sulfur dioxide (SO2), water vapor (H2O), carbon dioxide (CO2), and halogen compounds such as hydrochloric acid (HCl) into the stratosphere. Typically, sulfate aerosols form from SO2 on a timescale of weeks; these aerosols cool the surface by reflecting some incoming solar radiation and warm the stratosphere via absorption of longwave radiation. Sulfate aerosol heating can alter stratospheric transport affecting the distribution of stratospheric species [START_REF] Aquila | Dispersion of the volcanic sulfate cloud from a Mount Pinatubo-like eruption: dispersion of a Mount Pinatubo cloud[END_REF]. The increase in the aerosol burden also enhances aerosol surface area density, increasing the chances for heterogeneous chemical reactions that play a role in stratospheric ozone chemistry.

Previous volcanic eruptions had a noticeable impact on stratospheric ozone (e.g., El Chichón in 1982 [START_REF] Hofmann | Ozone destruction through heterogeneous chemistry following the eruption of El Chichón[END_REF][START_REF] Adriani | Correlated behavior of the aerosol and ozone contents of the stratosphere after the El Chichon eruption[END_REF], Mt. Pinatubo in 1991 [START_REF] Randel | Ozone and temperature changes in the stratosphere following the eruption of Mount Pinatubo[END_REF][START_REF] Brasseur | Mount Pinatubo Aerosols, Chlorofluorocarbons, and Ozone Depletion[END_REF]. Following the eruption of Mt. Pinatubo, the total ozone column was reduced by ~6% in north polar and midlatitude regions [START_REF] Angell | Estimated impact of Agung, El Chichon and Pinatubo volcanic eruptions on global and regional total ozone after adjustment for the QBO[END_REF]. The ozone was destroyed by chemical reactions on volcanic aerosols transported to high latitudes, which provided additional reactive surface area for the same heterogeneous chemical reactions that cause polar ozone loss each year. In the tropics, a 6% decrease in total ozone was observed in satellite and ozonesonde data [START_REF] Schoeberl | Tropical ozone loss following the eruption of Mt. Pinatubo[END_REF]. It was confined between 24 and 28 km in altitude and started a month after the eruption, consistent with the time needed for SO2 to be converted to sulfate aerosols (8).

To quantify the ozone loss on volcanic aerosols, we need information on aerosol size/concentration, trace gases (e.g., ozone, chlorinated species) and meteorological conditions (temperature, humidity) following the eruptions. Major eruptions that cause large perturbations to the aerosol loading and ozone chemistry of the stratosphere occur sporadically, so the opportunity to make measurements in these plumes is rare.

The Hunga Tonga-Hunga Haʻapai submarine volcano (hereafter HT) in the South Pacific (20.55°S, 175.38°W) was the largest volcanic eruption in the past 30 years. Its massive eruption on 15 January 2022 sent material as high as 50-55 km, the greatest height ever reported for a volcanic plume [START_REF] Carr | Stereo Plume Height and Motion Retrievals for the Record-Setting Hunga Tonga-Hunga Ha'apai Eruption of 15 January 2022[END_REF][START_REF] Millán | The Hunga Tonga-Hunga Ha'apai Hydration of the Stratosphere[END_REF]. Satellite measurements indicated that the HT volcano injected into the stratosphere a relatively small amount of SO2 (0.4 Tg [START_REF] Millán | The Hunga Tonga-Hunga Ha'apai Hydration of the Stratosphere[END_REF] as compared to an amount of 10-20 Tg from Mt.. Pinatubo [START_REF] Read | Microwave limb sounder measurement of stratospheric SO 2 from the Mt. Pinatubo Volcano[END_REF][START_REF] Bluth | Global tracking of the SO2 clouds from the June, 1991 Mount Pinatubo eruptions[END_REF], but a massive amount of H2O (~150 Tg, or 10% of the stratospheric burden [START_REF] Millán | The Hunga Tonga-Hunga Ha'apai Hydration of the Stratosphere[END_REF] unlike past eruptions. The large amount of H2O injected was also confirmed by radiosonde in situ measurements [START_REF] Vömel | Water vapor injection into the stratosphere by Hunga Tonga-Hunga Ha'apai[END_REF].

Less than a week after the eruption, a rapid response balloon campaign took place at the Maïdo Observatory (MO) in Réunion Island, 21°S, 55°E) [START_REF] Baray | Maïdo observatory: a new high-altitude station facility at Reunion Island (21° S, 55° E) for long-term atmospheric remote sensing and in situ measurements[END_REF]. Due to zonal easterly winds in the stratosphere (20-50 km), Réunion Island was ideally located downwind of the plume. From 20 to 24 January 2022, multiple meteorological balloons carrying aerosol, H2O, SO2 and ozone instruments were launched each night to provide key measurements of the volcanic plume composition (see Methods). A field campaign resulting in volcanic plume measurements in the stratosphere by in situ instruments has never occurred this quickly post-eruption. In comparison, a rapid response balloon campaign was deployed to Hawaii within 15 days of the 2018 Kilauea eruption [START_REF] Vernier | VolKilau: Volcano Rapid Response Balloon Campaign during the 2018 Kilauea Eruption[END_REF]. In this paper, we present unique observations that corroborate the occurrence of fast chemical ozone loss inside the volcanic plume in the week following the eruption. The extremely high water vapor values accelerated the oxidation of SO2 to sulfate aerosols, with much of the conversion in the densest parts of the plume occurring within a few days after the eruption [START_REF] Asher | Unexpectedly rapid aerosol formation in the Hunga Tonga plume[END_REF], facilitating heterogeneous chemical ozone loss. Additionally, as noted by [START_REF] Anderson | UV Dosage Levels in Summer: Increased Risk of Ozone Loss from Convectively Injected Water Vapor[END_REF] [START_REF] Anderson | UV Dosage Levels in Summer: Increased Risk of Ozone Loss from Convectively Injected Water Vapor[END_REF], high stratospheric water vapor can change the catalytic chlorine free radical chemistry by shifting total available inorganic chlorine ClO, potentially increasing ozone loss. Both rapid aerosol conversion and additional ozone loss appeared very rapidly for the HT eruption. The high vertical resolution in situ measurements were critical for seeing this loss which is not easily apparent in the satellite ozone observations that smear features in the vertical.

Results:

Fig. 1 shows balloon-borne measurements of ozone and H2O profiles at MO for the period 20-24 January 2022. It took 6 days for the volcanic plume to reach Réunion at ~30 km altitude. Balloon measurements five days after the eruption indicate typical stratospheric background values of H2O (4.5 ppmv) and a peak in ozone partial pressure of 15 mPa at 25 km. At Reunion, the highest H2O mixing ratio of 356 ppmv at 27 km was reported on 22 January, 21 UTC. Larger values of near 1000 ppmv were indicated in radiosonde measurements closer to the eruption by [START_REF] Vömel | Water vapor injection into the stratosphere by Hunga Tonga-Hunga Ha'apai[END_REF] [START_REF] Vömel | Water vapor injection into the stratosphere by Hunga Tonga-Hunga Ha'apai[END_REF]. The observed progression of descending altitude with time in the peak of the H2O plume in Fig. 1 can be explained by the vertical sheer in easterly zonal winds that linearly decreased from 30 m s -1 at 30 km to 20 m s -1 at 20 km; causing the plume to travel ~18° in longitude per day [START_REF] Millán | The Hunga Tonga-Hunga Ha'apai Hydration of the Stratosphere[END_REF][START_REF] Vömel | Water vapor injection into the stratosphere by Hunga Tonga-Hunga Ha'apai[END_REF].

The largest ozone decrease was observed on 21 and 22 January at 25-29 km. The decrease amounts to a loss of 10-45% of the 1998-present ozone climatology (see Methods in Supplemental Material). The presence of SO2 inside the volcanic plume could affect the performance of ECC ozonesondes by decreasing the sensor signal, resulting in artificially low ozone measurements. During the experiment, SO2 instruments [START_REF] Yoon | Development and testing of a novel sulfur dioxide sonde[END_REF] were launched in tandem with ECC ozonesondes on three flights (see Methods). Overall, SO2 data indicate that SO2 interference accounts for only 3-4% of the ozone decrease observed above 25 km the week after the eruption (see Methods). Satellite measurements of stratospheric gas profiles from the Aura Microwave Limb Sounder (MLS), in operation since 2004 [START_REF] Waters | The Earth observing system microwave limb sounder (EOS MLS) on the aura Satellite[END_REF] were also used to diagnose possible mechanisms of ozone decrease following the eruption. As MLS measures microwave thermal emission from the Earth's limb, its retrievals are largely unaffected by the presence of volcanic aerosols that strongly impair visible, ultraviolet, and infrared measurements. MLS observed the massive H2O perturbation as well as anomalous values of several trace gases injected into the stratosphere by HT, such as SO2 and HCl [START_REF] Millán | The Hunga Tonga-Hunga Ha'apai Hydration of the Stratosphere[END_REF]. Large H2O values more than 100 standard deviations (σ) above background levels were observed in the week following the eruption between 20 and 30 km, with a maximum value as high as 350 ppmv at 30 km on 16 January. In Fig. 2, MLS measurements of ozone, HCl and ClO radicals inside the volcanic plume are identified by selecting data points which have water vapor mixing ratios above 10 ppmv between 100 and 10 hPa (see Methods). Then for each data point, the climatological January 2005-2021 average profile is computed by using MLS profiles in a 5°x5° box region around the point (see Methods). MLS ozone mixing ratios inside the volcanic plume decreased at 18-21 hPa (~27-28 km) in the week following the HT eruption, from an average value of 6.3 ppmv on 16 January to a minimum value of 4.6 ppmv on 20 January (near 18°S, 88°E) at 21 hPa, 27% below climatological values. Anomalies are computed for MLS measurements inside the plume using a water vapor threshold of 10 ppmv. (e) Same as (d) for but H2O mixing ratios exceeding 100 ppmv. The red shaded area in panels (d) and (e) indicates the ± 1 standard deviation of the ozone climatology. On panel (e), the average ozone anomaly profile measured by the balloon sondes in Réunion Island is shown in magenta (ozonesonde data degraded to MLS vertical resolution, see Methods). On panels (d) and (e), the dashed orange lines correspond to the ± 1 standard deviation of the HCl climatology, and the dashed blue lines correspond to ± 1 standard deviation of the ClO climatology. The numbers on panels (d) and (e) indicate how many profiles were used to compute the average anomaly. For ClO the averaged anomaly profiles are computed for daytime (in blue) and nighttime (in purple) ClO measurements.

We compute average ozone anomaly and standard error profiles inside the plume for the period 16-24 January for two H2O thresholds (10 and 100 ppmv) to assess the sensitivity of stratospheric ozone decrease to H2O conditions (Fig. 2c). The decrease in MLS ozone is more pronounced for higher H2O mixing ratios, and the largest average ozone drop of 0.4 ppmv (standard error of 0.04 ppmv) at 28 km is observed for profiles with H2O mixing ratios larger than 100 ppmv. 30% of all 190 ozone profiles selected using the 100 ppmv H2O mixing ratio threshold show ozone dropping below 0.5 ppmv. This change is larger than the typical range of variability established by MLS ozone measurements for the January 2005-2021 period (standard deviation of 0.25 ppmv) or the 2-σ uncertainty of individual MLS ozone data points (0.1 ppmv) [START_REF] Livesey | EOS MLS Version 4.2x Level 2 data quality and description document[END_REF].

The average ozone decrease in the ozonesonde profiles is 0.6 ppmv (standard error of 0.25 ppmv) near 27-29 km, and the strongest decrease is observed during the night of 22 January, when water vapor mixing ratios were highest. Thus, the large quantity of water vapor injected by the HT volcano appears to have played a key role in the stratospheric ozone decrease observed by both ozonesondes and MLS.

Discussion:

The Mt. Pinatubo eruption in June 1991 decreased the tropical ozone column substantially, by 13-20 Dobson Units (DU) [START_REF] Schoeberl | Tropical ozone loss following the eruption of Mt. Pinatubo[END_REF][START_REF] Grant | Observations of reduced ozone concentrations in the tropical stratosphere after the eruption of Mt. Pinatubo[END_REF] 3 to 6 months after the eruption. This is of similar magnitude to the 18.3 DU loss noted in the January 22 ozone profile (Fig. 3b), but less than a week after the HT eruption. This rapidity of the tropical stratospheric ozone decrease is thus unprecedented. This indicates different mechanisms at play. The low ozone observed in the tropics after the Mt. Pinatubo eruption is likely the result of "lofting" in the tropics [START_REF] Brasseur | Mount Pinatubo Aerosols, Chlorofluorocarbons, and Ozone Depletion[END_REF] where the tropical upwelling was accelerated by heating of the volcanic aerosols that ultimately enhanced vertical transport of ozone-poor air from the troposphere to the stratosphere. In the case of the HT eruption, the radiative heating by volcanic aerosols was offset by radiative cooling of the stratosphere from the massive amount of H2O injected into the stratosphere [START_REF] Vömel | Water vapor injection into the stratosphere by Hunga Tonga-Hunga Ha'apai[END_REF], and hence lofting could not have produced that magnitude of ozone loss. Additionally, upward transport at the time of eruption is also not an adequate explanation. A rising volcanic plume can entrain ozone-poor tropospheric air and produce a local column ozone decrease, but this would have resulted in a maximum decrease in the earliest plume observation from MLS on 16 January, as dilution of the volcanic plume would have decreased this apparent loss over time. Minimum ozone values at 27-28 km were observed 5 days after the eruption, therefore, chemical ozone destruction caused by heterogeneous reactions on particles must be considered.

Stratospheric ozone loss inside the HT volcanic plume occurred at rates exceeding those observed in the tropical stratosphere for previous major eruptions such as El Chichòn and Mt. Pinatubo. A drop of 0.5 ppmv for the altitude range 25-29 km was observed less than a week after the HT eruption. For comparison, during the formation of the Antarctic ozone hole, stratospheric ozone at 20 km is destroyed at a rate of about 0.05 ppmv per day [START_REF] Solomon | Progress towards a quantitative understanding of Antarctic ozone depletion[END_REF], or about 0.35 ppmv over a comparable period as the HT loss.

Heterogeneous reactions on the particles of polar stratospheric clouds (PSCs) play a key role in polar ozone loss. PSCs, forming at temperatures below ~195 K, provide the surfaces necessary to convert inorganic chlorine (primarily chlorine nitrate, ClONO2 and HCl) to chemically active forms of chlorine (e.g., chlorine monoxide, ClO) [START_REF] Solomon | Stratospheric ozone depletion: A review of concepts and history[END_REF]. ClO can then lead to catalytic ozone loss. Experimental studies have shown that these reactions can also occur at higher temperatures (~210 K) on other particle types, including sulfuric acid droplets [START_REF] Tolbert | Reaction of Chlorine Nitrate with Hydrogen Chloride and Water at Antarctic Stratospheric Temperatures[END_REF]. Activation of ClONO2 and HCl via heterogeneous reactions becomes more efficient as temperature decreases, or increased H2O dilutes the sulfuric acid concentration [START_REF] Tolbert | Heterogeneous interactions of chlorine nitrate, hydrogen chloride, and nitric acid with sulfuric acid surfaces at stratospheric temperatures[END_REF].

Modeling studies have indicated that enhanced H2O in the stratosphere could lead to chemical ozone loss through heterogeneous chlorine activation and subsequent ozone destruction [START_REF] Anderson | UV Dosage Levels in Summer: Increased Risk of Ozone Loss from Convectively Injected Water Vapor[END_REF][START_REF] Robrecht | Mechanism of ozone loss under enhanced water vapour conditions in the mid-latitude lower stratosphere in summer[END_REF]. Low temperatures (below 203 K) and elevated H2O mixing ratios (> 20 ppmv) must be maintained for heterogeneous chlorine activation on sulfate aerosols to occur [START_REF] Robrecht | Mechanism of ozone loss under enhanced water vapour conditions in the mid-latitude lower stratosphere in summer[END_REF].

The largest ozone loss observed above Réunion Island on 22 January 2022 coincides with H2O mixing ratios exceeding 100 ppmv at ~25 and 27 km (Fig. 3). Above 25 km, temperature values are 2 to 4 K below the climatological mean temperature profile for January computed using 1998-2021 SHADOZ data for Réunion Island (see Methods). Radiosoundings in the tropics have indicated an average temperature decrease of 2 K due to the large increase of water vapor after the HT eruption [START_REF] Vömel | Water vapor injection into the stratosphere by Hunga Tonga-Hunga Ha'apai[END_REF]. In Fig. 3, ozone decreases also coincide with the presence of aerosols as indicated by peaks in the COBALD backscatter measurements. Measurements from an optical particle counter instrument flown on that night provide additional information on the aerosol size and concentration, from which aerosol surface area density can be estimated (see Methods). In Fig. 3, the aerosol measurements indicate a peak ambient surface area density of 286.9 μm 2 cm -3 at 26.4 km. This is 4 to 6 times higher than what was reported after the Mt. Pinatubo eruption [START_REF] Deshler | Balloonborne measurements of the Pinatubo aerosol size distribution and volatility at Laramie, Wyoming during the summer of 1991[END_REF], and ~600 times higher than the background stratospheric value of 0.5 μm 2 cm -3 . The large humidification of the stratosphere by the HT eruption resulted in rapid aerosol formation in the volcanic plume and the corresponding large aerosol surface area [START_REF] Asher | Unexpectedly rapid aerosol formation in the Hunga Tonga plume[END_REF][START_REF] Zhu | Perturbations in stratospheric aerosol evolution due to the water-rich plume of the 2022 Hunga-Tonga eruption[END_REF]. The large stratospheric humidification, subsequent radiative cooling and the added surface area likely accelerated heterogeneous chemistry on sulfate aerosols and catalytic ozone loss. MLS measurements at 27 km inside the volcanic plume indicate ozone decreases (average ozone anomaly of -0.4 ppmv with decreases as large as -1.5 ppmv) correlated with higher water vapor (29)mixing ratios (mean H2O of 102 ppmv) and temperatures on average 2 K below the climatology (see Methods; Fig. S1). Above 25 km, where most of the ozone loss is observed, temperatures are usually far too warm (> 220 K) for heterogeneous activation of HCl to ClO to occur (see Methods). However, when water vapor mixing ratios exceed 100 ppmv, the probability of the HCl + ClONO2 reaction increases by 4 orders of magnitude at warm temperatures (see Methods; Fig. S2). The radiative cooling induced by the large amount of water vapor (-4 K from Fig. 3) can further increase this probability by another factor of 10 (see Methods; Fig. S2). An increase in water vapor and corresponding decrease in temperature results in more dilute sulfate aerosols and higher HCl solubility; hence the reaction probability for the conversion of HCl to ClO increases dramatically and catalytic ozone loss becomes possible at relatively warm temperatures.

Although the HCl injection into the stratosphere by the HT eruption was comparable to that from previous moderate eruptions observed during the MLS record [START_REF] Millán | The Hunga Tonga-Hunga Ha'apai Hydration of the Stratosphere[END_REF], it reached an altitude near 31.6 hPa (~24 km) on 16-17 January, well above levels previously observed by MLS [START_REF] Millán | The Hunga Tonga-Hunga Ha'apai Hydration of the Stratosphere[END_REF]. In Fig. 2, two main negative HCl anomalies are observed at 24 and 29 km for measurements with large water vapor mixing ratios (> 100 ppmv) inside the volcanic plume. The first HCl anomaly value of -0.25 ppbv at 24 km may be due to scavenging by ice or ash particles [START_REF] Tabazadeh | Stratospheric Chlorine Injection by Volcanic Eruptions: HCl Scavenging and Implications for Ozone[END_REF], which were injected up to ~23 km but rapidly washed out within the first day following the eruption [START_REF] Legras | The evolution and dynamics of the Hunga Tonga plume in the stratosphere[END_REF]. Moreover, experimental studies have indicated that a quasi-liquid layer (QLL) can form rapidly on ice particles at temperatures below the bulk melting point for ice exposed to high HCl and H2O content [START_REF] Mcneill | Hydrogen chlorideinduced surface disordering on ice[END_REF]. QLL surfaces mediate chemical reactions at the vapor-ice interface and could have enhanced the chlorine activation reaction of HCl with ClONO2 (29) on ice particles inside the volcanic plume. The second, larger HCl anomaly of -0.4 ppbv at 29 km may indicate HCl heterogeneous activation on sulfate aerosols. Indeed, this negative HCl anomaly coincides with a positive peak of 0.41 ppbv in ClO radicals that is much more pronounced for daytime measurements (Fig. 2). Such high ClO radical observations provide direct observational evidence for chlorine activation, consistent with efficient Cl2 production by the HCl + ClONO2 heterogeneous reac tion on sulfate aerosols at unusually warm temperatures.

The observed catalytic ozone loss is primarily due to an invigorated ClOx (Cl/ClO) ozone loss catalytic cycle, possibly assisted by other halogens. The chain length in stratospheric ozone depletion cycles can be considered as an estimate of ozone decline via the catalytic cycles [START_REF] Lary | Catalytic destruction of stratospheric ozone[END_REF]. For the ClOx cycle, a chain length greater than 10 is found in most of the stratosphere (i.e., each ClO molecule produced can lead to the destruction of 10 ozone molecules), which would imply a ratio of 10 or more for ozone to ClO anomaly. Between 20 and 15 hPa, where warmer temperatures make chlorine activation unlikely under baseline conditions, the chain length can range from 50 to 500 [START_REF] Morgenstern | Ozone sensitivity to varying greenhouse gases and ozonedepleting substances in CCMI-1 simulations[END_REF]. Inside the HT plume the ratio of peak ozone to ClO anomalies is about 870 (29) (0.41 ppmv/0.47 ppbv) in Fig. 2, not inconsistent with the upper range estimate, but 2 to 20 times higher (these values represent a first-order plausibility argument; a large range of ozone and ClO anomalies is observed in the MLS data set). Indeed, this estimate of chain length is a lower limit, since a decrease in NO2 radical observations indicate slowing of the NOx cycle, presumably due to N2O5 hydrolysis (see Methods; Fig. S3). At sunset NO2 is higher than in the morning, and better approximates baseline conditions, suggesting that NOx may at least partially be sustained in the daytime plume. An initial examination of groundbased DOAS observations of BrO radicals in the plume are indistinguishable from clear-sky values before the plume arrival (see Materials), but there is large uncertainty. An invigorated BrOx cycle at elevated ClO concentrations (i.e., BrO + ClO reaction) could contribute to some ozone loss. No significant impact on ozone by HOx gas-phase chemistry was seen in a global climate model simulation with enhanced water vapor following the HT eruption [START_REF] Zhu | Perturbations in stratospheric aerosol evolution due to the water-rich plume of the 2022 Hunga-Tonga eruption[END_REF]. Similarly, an increase of water vapor in the lower stratosphere did not have an impact on the HOx cycle expected from humidification and added surface area density [START_REF] Anderson | Stratospheric ozone over the United States in summer linked to observations of convection and temperature via chlorine and bromine catalysis[END_REF]. A full chemical box-model study with Lagrangian modeling ( 26) is needed to better examine the very rapid observed ozone loss in the volcanic plume; such model development is in part limited by uncertainty surrounding chlorine activation [START_REF] Mcneill | Hydrogen chlorideinduced surface disordering on ice[END_REF][START_REF] Bogdan | Formation of mixed-phase particles during the freezing of polar stratospheric ice clouds[END_REF] associated with supercooled aerosol proxy solutions and ice surfaces under the conditions of the HT plume.

The large amount of seawater vaporized during the eruption contains sea salt that may have been transported to the stratosphere, providing a source of reactive chlorine, bromine, and iodine for ozone destruction. However, it is unclear whether all components of sea salt aerosols would survive wet scavenging in the volcanic plume and be efficiently transported to the stratosphere. Inorganic chlorine (HCl, Cl -) and bromine (HBr, Br -) are easily removed by wet scavenging, while iodine is not [START_REF] Koenig | Quantitative detection of iodine in the stratosphere[END_REF]. Even a small injection of iodine into the stratosphere could have accelerated ozone loss in the volcanic plume due to its much larger ozone-depleting efficiency [START_REF] Koenig | Quantitative detection of iodine in the stratosphere[END_REF][START_REF] Carpenter | Update on ozone-depleting substances (ODSs) and other gases of interest to the Montreal protocol[END_REF][START_REF]World Meteorological Organization (WMO). Executive Summary. Scientific Assessment of Ozone Depletion: 2022[END_REF] Anderson et al. (2012) [START_REF] Anderson | UV Dosage Levels in Summer: Increased Risk of Ozone Loss from Convectively Injected Water Vapor[END_REF] hypothesized that excess mid latitude stratosphere water associated with convection changes due to global warming could destroy lower stratospheric ozone. This HT event appears to be an extreme example of that mechanism. The quantity of water from HT is significantly larger than expected from overshooting monsoon convection but provides observational evidence that this process occurs (see supplement). The rapid chemical ozone loss inside the HT volcanic plume was primarily triggered by the synergistic effects of large humidification, radiative cooling and added aerosol surface area. All effects act in concert to accelerate HCl heterogeneous activation on sulfate aerosols at warmer temperatures than previously studied. The fact that stratospheric ozone loss was so rapid after the HT eruption calls for additional experimental studies of heterogeneous chemistry on hydrated aerosols (especially halogen chemistry) to better assess the kinetics of these reactions. It also identifies the need to develop atmospheric modeling tools at finer scales to better understand stratospheric ozone chemistry in the tropics after extreme events. The increased stratospheric H2O may linger for 4-5 years, potentially altering ozone chemistry. As noted in Solomon et al. (2022) [START_REF] Solomon | On the stratospheric chemistry of midlatitude wildfire smoke[END_REF] in regards to the Australian New Year bush fires from 2019/2020, which injected 0.9 Tg of smoke into the stratosphere, there were chemical shifts associated with heterogeneous reactions that alter nitrogen, chlorine and reactive hydrogen species with the potential to cause mid latitude ozone loss. For the next few years, continued monitoring is needed of ozone, water vapor, aerosols, and halogens to assess the extended impacts of this unprecedented HT eruption.

Tables S1

(GPS) altitude, relative humidity (RH), wind speed and direction. Some of the balloon payloads included a SO2 sonde, an ECC ozonesonde, and a Portable Optical Particle Counter (POPS): a light-weight particle counter designed for aerosol particle size distribution measurements. Table S1 below provides a summary of the measurements schedule.

The CFH was developed to provide highly accurate water vapor measurements in the tropopause region and stratosphere where the water vapor mixing ratios are extremely low (~2 ppmv). CFH mixing ratio measurement uncertainty ranges from 5% in the tropical lower troposphere to less than 10% in the stratosphere (40); a recent study shows that the uncertainty in the stratosphere can be as low as 2%-3% [START_REF] Vömel | An update on the uncertainties of water vapor measurements using cryogenicfrost point hygrometers[END_REF].

The COBALD backscatter instrument, developed at ETH (Swiss Federal Institute of Technology, Zurich), uses two light-emitting diodes at two wavelengths (455 and 940 nm) to detect and characterize cloud and aerosol particles in the atmosphere [START_REF] Brabec | Particle backscatter and relative humidity measured across cirrus clouds and comparison with microphysical cirrus modelling[END_REF] , [START_REF] Brunamonti | Balloon-borne measurements of temperature, water vapor, ozone and aerosol backscatter on the southern slopes of the Himalayas during StratoClim 2016-2017[END_REF]. The optical detector has a field of view of ±6°, and the signal detected typically originates from a 0.5-10 m distance from the sonde. Beyond 10 m, the signal contribution becomes negligible. For each of the two COBALD wavelengths, the COBALD raw signal is converted to backscatter ratio (BSR), which is defined as: BSR = βtot/ βmol = (βmol+ βpart)/ βmol = 1 + PBSR, where PBSR is the particle BSR; βtot is the measured backscatter coefficient, expressed as the sum of the molecular (βmol) and particle (βpart) contributions. The particle backscatter coefficient includes scattering of aerosols or ice crystals in the atmosphere. The molecular backscatter coefficient βmol is computed according to ref. [START_REF] Bucholtz | Rayleigh-scattering calculations for the terrestrial atmosphere[END_REF] based on the concurrent radiosonde readings of temperature and pressure. The COBALD sonde has been used to detect and characterize aerosol layers in the upper troposphere-lower stratosphere [START_REF] Vernier | Increase in upper tropospheric and lower stratospheric aerosol levels and its potential connection with Asian pollution[END_REF].

The POPS instrument [START_REF] Gao | A light-weight, high-sensitivity particle spectrometer for PM2.5 aerosol measurements[END_REF], developed at the National Oceanic and Atmospheric Administration (NOAA) and the Cooperative Institute for Research in Environmental Sciences (CIRES) is an optical particle counter made from a three-dimensional printer to reduce weight (~900 g). It uses a laser at 405nm to measure the backscattering of aerosols crossing the laser path. Based on the backscattering Mie theory, and an assumption on the aerosol particle index of 1.45 valid for sulfate aerosols, POPS can resolve the size of aerosols from 140 nm to 2.5µm with a resolution of 5%. The particle size represents the aerosol dry diameter, since the enclosure temperature is much larger than the ambient air. The surface area of aerosols measured by POPS is calculated using the kappa-Köhler theory that is based on the aerosol dry diameter and ambient relative humidity.

The ECC ozonesonde is often used worldwide to provide accurate measurements of ozone profiles. The ECC ozonesonde generates an electrical current through the reaction of ozone in a potassium iodide sensing solution, which produces approximately two electrons per molecule of ozone [START_REF] Komhyr | Electrochemical concentration cells for gas analysis[END_REF]. The ozone partial pressure (𝑃 ! ! ) is then calculated using the measured cell current 𝐼 " .

𝑃 ! ! = # $ * & * ' " ( # * ( $ * ( % * ) " & * (𝐼 " -𝐼 * ) (ref.(48))
where 𝑃 ! ! is in millipascals, 𝑅 is the universal gas constant (=8.314 J K -1 mole -1 ), 𝐹 is Faraday's constant (= 9.6487´10 4 C mole -1 ), 𝐼 " is the cell current in microamperes attributed to the reaction of ozone with iodide, 𝐼 * is the cell background current in microamperes, T + is the air temperature entering the cell in kelvin, approximated by the temperature of the pump, 𝜂 , is the pump flow efficiency as a function of pressure, 𝜂 -is the absorption efficiency for the transfer of the sampled gaseous ozone into the liquid phase, 𝜂 . is the conversion efficiency of the absorbed ozone in the cathode sensing solution into iodine and Φ + & (in cm 3 s -1 ) is the gas volume flow rate of the air sampling pump.

We follow the guidelines from the Southern Hemisphere ADditional OZonesondes (SHADOZ, [START_REF] Witte | First reprocessing of Southern Hemisphere ADditional OZonesondes (SHADOZ) profile records (1998-2015): 1. Methodology and evaluation: SHADOZ Reprocessed Ozonesonde Profiles[END_REF][START_REF] Witte | First Reprocessing of Southern Hemisphere ADditional OZonesondes Profile Records: 3. Uncertainty in Ozone Profile and Total Column[END_REF][START_REF] Thompson | First Reprocessing of Southern Hemisphere Additional Ozonesondes (SHADOZ) Ozone Profiles (1998-2016): 2. Comparisons with Satellites and Ground-Based Instruments[END_REF]) network to process the ozonesonde data obtained at the Maïdo Observatory. Witte et al.

(2017) [START_REF] Witte | First reprocessing of Southern Hemisphere ADditional OZonesondes (SHADOZ) profile records (1998-2015): 1. Methodology and evaluation: SHADOZ Reprocessed Ozonesonde Profiles[END_REF] describe corrections of 𝑃 ! ! which includes a conversion efficiency term, a correction for pump flow rate term dependent on the relative humidity and temperature of the laboratory during pre-flight preparation and a pump flow efficiency term which is pressure dependent. [START_REF] Witte | First Reprocessing of Southern Hemisphere ADditional OZonesondes Profile Records: 3. Uncertainty in Ozone Profile and Total Column[END_REF] [START_REF] Witte | First Reprocessing of Southern Hemisphere ADditional OZonesondes Profile Records: 3. Uncertainty in Ozone Profile and Total Column[END_REF] estimate that the ECC ozonesonde has an uncertainty of 10% in the tropical stratosphere for austral summer conditions (December to February). SHADOZ ozonesondes are launched from the airport (Roland Garros; 21.06°S, 55.48°E), located on the north side of the island since 1998. The flying distance between the Maïdo Observatory and the airport is ∼20 km. The climatological 𝑃 ! ! mean profile for January used the SHADOZ ozonesonde data from the airport.

At the one per second telemetry data rate, the CFH, COBALD, and ECC ozonesonde data have a high vertical resolution of 5 m with a mean balloon ascent rate of 5 m s -1 on most flights. We use the GPS altitude measured by Intermet iMet-4-RSB radiosondes as the main vertical coordinate for all instruments. All variables are binned in altitude intervals of 100 m to reduce measurement noise.

MLS observations and comparison to high-resolution ozonesonde measurements.

The Aura Microwave Limb Sounder (MLS) is a satellite instrument launched by NASA on 15 July 2004. Aura is in a sun-synchronous orbit at an altitude of ~705 km with an inclination angle of 98.2° to the equator, performing approximately 14.5 orbits per day [START_REF] Waters | The Earth observing system microwave limb sounder (EOS MLS) on the aura Satellite[END_REF]. MLS observes thermal emission from the atmosphere day and night over a latitude range of 82°S to 82°N. From the measured radiances, profiles of temperature, various trace gases, and cloud ice are retrieved [START_REF] Waters | The Earth observing system microwave limb sounder (EOS MLS) on the aura Satellite[END_REF]. As recommended by ref. [START_REF] Millán | The Hunga Tonga-Hunga Ha'apai Hydration of the Stratosphere[END_REF], MLS version 4 data are used instead of the most recent version 5. This is because in version 4, pointing information is obtained solely from O2 signals, while version 5 also uses the H2O line, affecting the pointing information inside the HT plume. As a result, substantial discrepancies in pointing degrade the accuracy of some version 5 MLS products. The vertical resolution is typically 3 km in the stratosphere up to 10 hPa. We use measurements of H2O, O3, HCl, and ClO. MLS measurements inside the volcanic plume are identified by selecting data points which have water vapor mixing ratios above 10 ppmv between 100 and 10 hPa. Then for each data point, the climatological January 2005-2021 average profile is computed by using MLS profiles in a 5°x5° box region around the point.

The estimated accuracy for MLS version 4 O3 is 5% at 21 hPa. In Fig. 2a, all O3 data points meet the screening criteria described in the MLS data quality document [START_REF] Livesey | EOS MLS Version 4.2x Level 2 data quality and description document[END_REF]. These criteria are indicative of how well the retrieved profiles fit the observed atmospheric microwave spectra. Most of the O3 data points did pass the MLS quality screening, indicating that the low O3 values retrieved after the eruption are valid measurements. In Fig. 2b-c, MLS HCl and ClO profiles in the HT volcanic plume have passed the quality screening criteria described in ref. [START_REF] Livesey | EOS MLS Version 4.2x Level 2 data quality and description document[END_REF]. MLS O3, HCl and ClO averaged anomaly profiles for the period 16-24 January shown in Fig. 2d) and e) are anomalies from the MLS January 2005-2021 climatological profile computed at each data point. We select data points inside the plume corresponding to different water vapor mixing ratio conditions between 100 and 10 hPa (i.e., above 10 and 100 ppmv) to compute the anomaly profiles. This is to assess whether O3, HCl and ClO anomalies are more pronounced for larger stratospheric water vapor amounts. For ClO, we further examine separately the day and night retrievals. MLS ClO retrievals may be affected by SO2 interference [START_REF] Millán | The Hunga Tonga-Hunga Ha'apai Hydration of the Stratosphere[END_REF]. However, that SO2 contamination is more important at lower levels (i.e., higher pressures), where spectral lines are broader; at the altitudes where the ozone loss is occurring (above ~27 km or 21 hPa), the lines are much narrower, so the SO2 signal impinges less on the ClO line. Also, if the ClO enhancements in the volcanic plume occur mostly for the daytime MLS measurements (and they do), this indicates that contamination by SO2 is minimal (as contamination should impact the nighttime data as well as the daytime data).

MLS version 4 O3 mixing ratio values are reported on pressure levels spaced at 12 levels per pressure decade, a spacing of about 2.7 km in altitude. To compare the high-resolution ozonesonde mixing ratio profile to the MLS satellite data, we smooth the high-resolution sonde measurements to match the resolution of the satellite profiles. First, we compute a least squares fit of the ozonesonde balloon data to the lower-resolution MLS retrieval grid [START_REF] Livesey | EOS MLS Version 4.2x Level 2 data quality and description document[END_REF]. Then we apply the MLS vertical averaging kernels, following the procedure described in ref. (52) and ref. [START_REF] Davis | The Stratospheric Water and Ozone Satellite Homogenized (SWOOSH) database:a long-term database for climate studies[END_REF]. The procedure for applying the MLS averaging kernels to an ozonesonde profile requires an a priori profile as input; for this, we used the climatological January-February 1998-2021 average of SHADOZ ozone mixing ratio profiles for Réunion Island.

Ozonesonde and SO2 interference

The presence of SO2 in the air can lead to significant negative interferences in the measurements of ECC ozonesondes. In the ECC ozonesonde, ambient air with ozone is pumped into a cathode chamber that contains a platinum electrode immersed in a low concentration potassium iodide (KI) solution. O3 molecules react with the KI molecules to produce iodine (I2). The iodine in contact with the platinum electrode is converted to iodide (I -) through the uptake of two electrons per molecule of iodine. To rebalance the cathode chamber, the anode chamber with higher concentration KI solution provides electrons via an ion bridge to the cathode. The electrical cell current generated and measured by the ozonesonde is thus directly related to the uptake rate of ozone in the cathode chamber [START_REF] Komhyr | Electrochemical concentration cells for gas analysis[END_REF]. The cathode chamber chemistry is altered if SO2 is present in the air. As a reducing agent, SO2 converts the produced iodide (I -) from the ozone/KI reaction back to iodine. This results in a lower cell current measured by the ECC ozonesonde, which reports O3 concentration minus SO2 concentration [START_REF] Morris | A Balloon Sounding Technique for Measuring SO2 Plumes[END_REF]. Therefore, O3 values reported by the ECC ozonesondes after the HT eruption can be lower than actual values in the atmosphere if significant SO2 is present. To account for this SO2 interference, we need to subtract from the reported depleted O3 column the actual SO2 column. During the rapid response experiment, SO2 instruments [START_REF] Yoon | Development and testing of a novel sulfur dioxide sonde[END_REF] were launched in tandem with ECC ozonesondes and sampled SO2 in the stratospheric volcanic plume during four flights. The flight on 21 January 2022, 19:15 UTC, reported a column SO2 of 0.21 DU between the GPS altitudes of 27.5 and 30.1 km, where the reported O3 column decrease is 6 DU. An estimated 3-4% (upper limit < 9%) of the ozone partial pressure decrease between 28 and 30 km in the ozonesonde ozone profile on 21 January is thus accounted for by SO2 interference.

Zenith-Sky DOAS measurements of stratospheric NO2

Measurements of stratospheric NO2 during the plume period (21 Jan to 1 Feb 2022) are compared with the clear-sky interannual NO2 variability for three years (January 2020, 2021, 1-20 Jan 2022) above Maido Observatory (see Fig. S3) to assess whether the NOx-cycle of stratospheric O3 destruction was significantly impacted by N2O5 hydrolysis in the humidified plume. The University of Colorado Differential Optical Absorption Spectroscopy instrument [START_REF] Coburn | The CU ground MAX-DOAS instrument: characterization of RMS noise limitations and first measurements near Pensacola, FL of BrO, IO, and CHOCHO[END_REF] has been operational at Maido Observatory since March 2018. Here, we present twilight (solar zenith angle, SZA > 74 degrees) zenith-sky NO2 differential Slant Column Densities (dSCDs) retrieved from a 425-465 nm spectral fit window, with fit settings otherwise adapted from the Network for the Detection of Atmospheric Composition Change (NDACC). These measurements present qualitative evidence for a reduction in stratospheric NO2 during sunrise and sunset, consistent with N2O5 hydrolysis; both geometries overlap with the plume. During sunset, NO2 dSCDs are higher than during sunrise also in the plume, and the delta NO2 dSCDs (bottom panel) are closer to the clear sky interannual mean. The NO2 decrease compared to the interannual mean cannot be explained by volcanic aerosols, which would increase the NO2 dSCDs for SZA < 90 deg [START_REF] Bassford | Zenith-sky observations of stratospheric gases: the sensitivity of air mass factors to geophysical parameters and the influence of tropospheric clouds[END_REF]. The largest NO2 decrease is observed at SZA > 88 deg, consistent with the plume height. Some decrease in the NO2 dSCD at lower SZA is expected due to the broad vertical sensitivity of zenith-sky DOAS measurements (averaging kernel full-width-half-maximum at 28 km is ~10 km). BrO radicals were also detected by the DOAS before and after the HT plume arrival. No significant difference in the SZA dependence of BrO dSCDs was observed comparing sunrise and sunset data before and after the HT plume arrival (not shown). No evidence for enhanced BrO due to the volcanic plume injection was detectable in the DOAS data.

Heterogeneous chemistry under enhanced water vapor conditions.

The added aerosol surface area and large humidification of the stratosphere after the HT eruption may have affected heterogeneous chemistry on sulfate aerosols. In addition, the increase in water vapor resulted in radiative cooling of the stratosphere [START_REF] Vömel | Water vapor injection into the stratosphere by Hunga Tonga-Hunga Ha'apai[END_REF]. Fig. S1 displays MLS ozone anomalies at 27 km inside the volcanic plume as a function of temperature and water vapor for the 16-24 January period. The ozone anomalies are relative to the January 2005-2021 MLS ozone climatology computed at each MLS measurement inside the volcanic plume (shown on Figure 2a and selected using the 10 ppmv water vapor mixing ratio threshold). For each ozone anomaly, we keep the coincident MLS measurements of water vapor mixing ratio and temperature (the temperature profiles passed the MLS quality screening criteria), which results in the distribution of ozone anomalies as a function of water vapor and temperature shown in Fig. S1. In Fig. S1, negative ozone anomalies are more pronounced for higher water vapor mixing ratios and lower temperatures. 40% of MLS measurements inside the volcanic plume have negative ozone anomalies, with values as low as -1.5 ppmv. Negative ozone anomalies at 27 km are associated with a mean water vapor of 102 ppmv and temperature of 219 K (2K below the January 2005-2021 temperature climatology for 0-30°S). Thus, ozone decreases inside the volcanic plume are correlated with higher water vapor mixing ratios and lower temperatures (due in part to radiative cooling).

To further assess the effects of humidification and radiative cooling on heterogeneous chemistry, we look at changes in reactive uptake coefficient g (the probability that a molecule impacting the aerosol surface undergoes reaction) of the HCl + ClONO2 ® HNO3 + Cl2 chemical reaction. Computed g values for HCl + ClONO2 are based on a parameterization of heterogeneous reactions and uptake coefficients implemented in the Community Earth System Model (CESM) Whole Atmosphere Community Climate Model (WACCM). The parameterization of g values is based on ref. [START_REF] Shi | Kinetic model for reaction of ClONO 2 with H 2 O and HCl and HOCl with HCl in sulfuric acid solutions[END_REF] and is valid for uptake of HCl on sulfate aerosols (binary H2SO4/H2O solution) from 185 to 260 K. The formulation of g developed in ref. [START_REF] Shi | Kinetic model for reaction of ClONO 2 with H 2 O and HCl and HOCl with HCl in sulfuric acid solutions[END_REF] builds on initial work by ref. [START_REF] Hanson | Reaction of ClONO2 with H2O and HCl in sulfuric acid and HNO3/H2SO4/H2O mixtures[END_REF] to include the effects of temperature and partial pressure of water vapor on acid concentration and Henry's law solubilities of HCl and ClONO2. Further details and information on the formulation of uptake coefficients for HCl + ClONO2 are provided in Table A3 of ref. [START_REF] Shi | Kinetic model for reaction of ClONO 2 with H 2 O and HCl and HOCl with HCl in sulfuric acid solutions[END_REF]. Fig. S2 displays computed g values for HCl + ClONO2 as a function of temperature between 210 and 230 K at 20 hPa (27 km) for an aerosol radius of 0.3 µm (mean size reported by the POPS instrument on 22 January); 5, 100 and 350 ppmv of water vapor; 1 and 2 ppbv of HCl (range observed on Figure 2b); and 0.5 ppbv of ClONO2. The lower range of water vapor corresponds to background stratospheric water vapor conditions, while 350 ppmv corresponds to the maximum water vapor mixing ratio observed at 27 km inside the volcanic plume on 22 January (Fig. 3). At this altitude, the climatological temperature for January 1998-2021 is 222 K, while the temperature observed on that night is 218 K (Fig. 3).

Under usual background stratospheric water vapor conditions (5 ppmv), the probability of the HCl + ClONO2 heterogeneous reaction at 20 hPa is quite low (g ~ 1.9×10 -9 ) at 222 K. This is far too warm for heterogeneous processing to occur under typical stratospheric conditions. Under vastly perturbed conditions in stratospheric water vapor as observed after the HT eruption, g values for HCl + ClONO2 increase by 4 orders of magnitude to reach 7.2 ×10 -5 when water vapor reaches 350 ppmv at 222 K. Thus, water vapor injection into the stratosphere by the HT volcano increases the probability of heterogeneous processing of HCl to occur, even at warm stratospheric temperatures. The radiative cooling induced by the large amount of water vapor (-4 K in Figure 3) can further increase g values by a factor of 10 to reach 5.7×10 -4 . Increasing the amount of HCl has a relatively smaller effect as g values are doubled when HCl increases from 1 to 2 ppbv. At lower pressure (15 hPa), g values are smaller but still in the 10 -5 to 10 -4 range (g = 1.7×10 -4 for H2O = 350 ppmv, HCl = 1 ppbv, T = 218 K). Overall, the probability of the HCl + ClONO2 heterogeneous reaction on sulfate aerosols increases under the unusual stratospheric water vapor/temperature conditions encountered after the HT eruption. An increase in water vapor and corresponding decrease in temperature due to radiative cooling results in more dilute sulfate within the aerosol, and as a result the solubility of HCl increases. With shifts to higher water vapor mixing ratios and lower temperatures, the reaction probability for the conversion of HCl to ClO increases significantly and catalytic ozone loss becomes possible at relatively warm temperatures.

We can compute the time for removal of HCl via heterogeneous chemistry on sulfate aerosols according to ref. [START_REF] Hofmann | Ozone destruction through heterogeneous chemistry following the eruption of El Chichón[END_REF]. The characteristic time 𝜏 /01 (in seconds) for the deposition of HCl on sulfate aerosols can be expressed as 𝜏 /01 23 = 𝛾𝜐𝐴/4, where 𝛾 is the uptake coefficient, 𝜐 is the average molecular velocity (cm s -1 ) and 𝐴 is the aerosol surface area density (cm 2 cm -3 ). The maximum surface area density of 2.9 ×10 -6 cm 2 cm -3 was observed at 27 km on 22 January. In Extended Figure 2, the g value for HCl + ClONO2 is about 5.7×10 -4 at 20 hPa for conditions inside the volcanic plume (H2O = 350 ppmv, T = 218 K, HCl = 1ppbv). This corresponds to a removal time of HCl (via this heterogeneous reaction) of 19 hours (and 3 days for g = 1.7×10 -4 at 15 hPa). Thus, we estimate that conversion of HCl to Cl2 occurs rather quickly inside the volcanic plume, in about 1 to 3 days. This reaction converts inorganic chlorine (HCl and ClONO2) to the free radical form ClO (via photodissociation of Cl2). Elevated ClO concentrations observed by MLS in the week following the HT eruption are most likely the result of heterogeneous conversion of HCl to ClO on sulfate aerosols due to a combination of water vapor enhancements and radiative cooling in the stratosphere.

Fig. 1 .

 1 Fig. 1. Soundings of ozone and water vapor a week after the eruption. Profiles of ozone partial pressure (black) and water vapor mixing ratio (blue) measured at Maïdo Observatory on Réunion Island over 20-24 January 2022. SHADOZ climatological ozone partial pressure for January for Réunion Island is indicated by the red dashed line. The red shaded area shows values of 2 standard deviations above and below the mean.

Fig. 2 :

 2 Fig. 2: MLS satellite measurements inside the volcanic plume. Maps of MLS (a) ozone, (b) HCl and (c) ClO at 27 km for the period 16-24 January 2022. The locations of the Hunga Tonga volcano (HT) and the Maïdo Observatory (MO) are indicated by green stars. Colored circles correspond to individual satellite profiles. MLS anomaly profiles (see Methods) of (d) ozone (ppmv, red), HCl (ppbv, orange) and ClO (ppbv, blue and purple) inside the volcanic plume averaged over the period 16-24 January.

Fig. 3 :

 3 Fig. 3: Soundings at Maïdo Observatory on 22 January. a) Profiles of water vapor mixing ratio (blue), aerosol backscatter ratios at 940 nm (red) and 455 nm (blue), aerosol ambient surface area density (brown, in μm 2 cm -3 ); and b) ozone partial pressure (magenta) and temperature (green) measured at Maïdo Observatory on 22 January 2022. The location of the tropopause is indicated by the horizontal green dashed line and the ozone climatology for Réunion Island corresponds to the red dashed line. The red shaded area illustrates the observed ozone loss estimated for that night. The climatological temperature profile for January 1998-2021 for Réunion Island is in black on panels (a) and (b) as well as the temperature anomaly from the climatology on panel (b). The gray shaded area illustrates the ± 1 standard deviation of the temperature climatology.

Fig. S1 .

 S1 Fig. S1. Scatter plots of ozone anomalies at 27 km versus temperature and water vapor inside the volcanic plume. The ozone anomalies are relative to the January 2005-2021 climatology for MLS data points shown on Figure 2a (i.e., MLS ozone profiles for the period 16-24 January 2022 which are associated with water vapor exceeding 10 ppmv between 10 and 100 hPa).

Fig. S2 .

 S2 Fig. S2. g values for HCl+ClONO2 in the stratosphere as a function of temperature between 210 and 230 K at 20 hPa, aerosol radius 0.3 µm, and H2O of 5 ppmv (green), 100 ppmv (blue) and 350 ppmv (red), HCl of 1 ppbv (solid line) and 2 ppbv (dashed line) and 0.5 ppbv of C1ONO2. The red arrow indicates the shift in g values from humidification from 5 to 350 ppmv and the blue arrow indicates the shift in g values from a -4 K radiative cooling.

Table S1 . Summary of balloon flights from 20 to 24 January 2022 for the rapid response experiment at Maïdo Observatory.

 S1

	Date of balloon flight	Burst altitude (km)	ECC	CFH	COBALD	POPS	SO2
	Jan, 17UTC	28.8	x	x	x
	Jan, 19UTC	30.3	x			x	x
	Jan, 21UTC	20.0	x	x	x
	Jan, 18UTC	31.6	x			x	x
	Jan, 21UTC	31.5	x	x	x
	Jan, 00UTC	26.4	x			x	x
	Jan, 18UTC	30.6	x	x	x
	Jan, 15UTC	31.2	x			x	x
	Jan, 17UTC	31.0	x	x	x

Acknowledgments:

The authors acknowledge the European Communities, the Région Réunion, CNRS and Université de la Réunion for their support and contributions in the construction phase of the research infrastructure OPAR (Observatoire de Physique de l'Atmosphère de La Réunion, including Maïdo Observatory). OPAR is presently funded by CNRS (INSU), Météo France, and Université de La Réunion and managed by OSU-R (Observatoire des Sciences de l'Univers de La Réunion, UAR 3365). We thank Gary Morris, Daniel Murphy, Maya Abou-Ghane and Jim Burkholder for their discussions. We also thank Alex Wong and SilverLining for their support.

Funding :

Agence Nationale de la Recherche (ANR) CONCIRTO award ANR-17-CEO1-0005-01.

National Science Foundation (NSF) awards AGS-1620530 and AGS-2027252.

National Aeronautics and Space Administration (NASA) contract 80NM0018D0004.

Data and materials availability:

The processed CFH, ECC ozonesonde and COBALD data used in this study are available at https://lacy.univ-reunion.fr/activites/programmes-de-recherche/anr-concirto/donnees. Raw MLS H2O, O3, HCl and ClO data may be found at: https://disc.gsfc.nasa.gov/datasets/ML2H2O_004/summary?keywords=aura https://disc.gsfc.nasa.gov/datasets/ML2O3_004/summary?keywords=aura https://disc.gsfc.nasa.gov/datasets/ML2HCL_004/summary?keywords=aura https://disc.gsfc.nasa.gov/datasets/ML2CLO_004/summary?keywords=aura

Author contributions:

Conceptualization: SE Methodology: SE, JB, Data curation: SE, JB, RV, CFL, JMM, KL, PW, SLA, JHF, EA, MT, LA, MT, PW, SA, HV, FGW, LM, MLS, LF, WGR Writing -original draft: SE, JB, KHR, RG, RWP, RV, CFL, JMM, KL, PW, SLA, JHF, EA, MT, SMD, TT, HV, FGW, RMS, LM, MLS, LF, WGR

Competing interests:

The authors declare no competing interests.

Supplementary Materials:

Data and Methods

Figs. S1 to S3

Supplementary Materials for

Rapid ozone loss following humidification of the stratosphere by the Hunga Tonga Eruption

Stephanie Evan

Materials and Methods

In situ balloon-borne measurements

We have performed balloon-borne measurements of water vapor, ozone, and aerosols for 5 consecutive nights at the Maïdo Observatory (21.08°S, 55.38°E) on Réunion Island during the period 20-25 January 2022 following the eruption of the Hunga Tonga volcano on 15 January. Réunion Island is in the Southwest Indian Ocean and holds one of the very few atmospheric observatories in the subtropical Southern Hemisphere.

On some of the balloon payloads, a cryogenic frost-point hygrometer (CFH), a Compact Optical Backscatter and AerosoL Detector (COBALD) and an electrochemical concentration cell (ECC) ozonesonde were flown together. Data from the COBALD, CFH and ozone sondes were telemetered to the ground by an Intermet iMet-4-RSB meteorological radiosonde, which additionally provided measurements of ambient pressure, temperature, Global Positioning System