Peter Beelen

Vincent Neiger

Faster List Decoding of AG Codes

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

Introduction

Context and main result. Algebraic geometry (AG) codes form a large class of error-correcting codes that became famous for providing asymptotically good families of codes surpassing the Gilbert-Varshamov bound. Such codes are constructed using algebraic curves defined over a finite field, say F q where q is the cardinality of the field. Instead of considering algebraic curves defined over F q , one can also use the language of function fields with full constant field F q ; we follow the latter viewpoint in this article. Section 2 gives some more background on AG codes and function fields; for a detailed introduction, the reader may refer to [START_REF] Stichtenoth | Algebraic Function Fields and Codes[END_REF].

Decoding algorithms for AG codes have been studied since the late 80's. One important such decoder is the well-known Guruswami-Sudan (GS) list-decoder, that can be used to decode any AG code.

Consider an AG code constructed from a function field F of genus g, with underlying finite field F q and code length n. The design of the GS decoder further asks that one chooses a list size ℓ and multiplicity parameter s, which are such that s ≤ ℓ. It was shown in [2] that such an AG code can be decoded using a particular instance of the GS decoder using Õ(sℓ ω µ ω-1 (n + g)) operations in F q , where µ is the smallest positive element in the Weierstrass semigroup at some chosen rational place P ∞ of F . Here, the "soft-O" notation Õ(•) is similar to the "big-O" notation O(•), but hides factors logarithmic in the parameters s, ℓ, µ, n, g. This complexity result is achieved under the mild assumption that one has already carried out some precomputations, yielding objects which depend on the code but not on the received word. These objects can therefore be reused as such, with no additional computation, in each subsequent call to the decoder (see [2, Section VI] for more details).

To the best of our knowledge, this complexity result is the best known one for this decoding task in general. More precisely, any other implementation of the GS decoder has a complexity bound which is similar or worse, with one exception in the specific context of Reed-Solomon (RS) codes. Indeed, in this case the above complexity from [2] becomes Õ(sℓ ω n), while there are known list decoders for these codes whose complexity is in Õ(s 2 ℓ ω-1 n) [4, Section IV] [9, Sections 2.4 to 2.6]; recall that s ≤ ℓ.

The main goal of this paper is to refine the exploitation of efficient univariate polynomial matrix computations in the algorithmic framework from [2]. We will show that this indeed is possible, leading to our main result: any AG code can be list decoded, using an instance of the GS list decoder, in complexity Õ(s 2 ℓ ω-1 µ ω-1 (n+g)+ℓ ω µ ω ). This complexity bound holds under mild assumptions about precomputations, similar to those of [2] mentioned above. Since µ ≤ g + 1, the term ℓ ω µ ω is in O(ℓ ω µ ω-1 g), and therefore this new complexity bound improves upon the best previously known bound Õ(sℓ ω µ ω-1 (n + g)).

Moreover, for Reed-Solomon codes one has µ = g+1 = 1 and also ℓ ≤ sn, so that the new complexity bound becomes Õ(s 2 ℓ ω-1 n), matching the best previously known bound in this specific case.

Overview of the approach. The GS list decoding algorithm consists of two main steps: the interpolation step, in which one seeks a polynomial Q(z) ∈ F [z] satisfying certain interpolation properties; and the root finding step, in which one computes roots of the polynomial Q(z). The second step is generally considered as computationally easier than the first step. In this paper, we keep the root finding algorithm described in [2, Algorithm 6], yet with a minor refinement of the complexity analysis to ensure that it does not become the dominant step after our improvement of the interpolation step. Specifically, Section 5.2 shows a simple modification of the analysis from [2] leading to the complexity estimate Õ(sℓµ ω-1 (n+g)), improving upon the one Õ(ℓ 2 µ ω-1 (n+g)) reported in [2].

We also keep the overall structure of the interpolation step [2, Algorithm 7, Steps 1 to 9], which performs two main tasks: first build a basis B of some F q [x]module of interpolant polynomials, and then find a small degree such interpolant Q(z) thanks to a suitable F q [x]-module basis reduction procedure. The main novel ideas for obtaining our result are the following:

• For applying basis reduction to B, we rely on the algorithm from [START_REF] Neiger | Computing Canonical Bases of Modules of Univariate Relations[END_REF] for computing so-called shifted Popov forms. The same choice was made in [2], where it was motivated by the fact that this algorithm supports any shift, whereas earlier similarly efficient algorithms [5,16,[START_REF] Gupta | Triangular x-basis decompositions and derandomization of linear algebra algorithms over[END_REF] focus on the unshifted case. Here, we have an additional motivation for this choice: a key towards our complexity improvement lies in the fact that the complexity of this basis reduction algorithm is sensitive to some type of average degree of the input polynomial matrix.

• We describe a new algorithm to build a polynomial matrix B whose average degree is small, and whose rows generate all possible interpolating polynomials Q(z). Our construction directly provides a matrix whose rows are F q [x]-linearly independent, whereas the matrix built in [2] has redundant rows and therefore requires additional computations to obtain a basis of its F q [x]-row space, which furthermore typically does not have small average degree. In our case, this small average degree is ensured through the combination of two ingredients. The first one is a new description of a generating set of the module of interpolants (see Sections 3.1 to 3.3) which leads to a matrix B with many zero entries in each row (like in [2]), and also such that the nonzero entries are restricted to the first µs columns (unlike in [2] where they can be found in all columns). The second ingredient is an iterative computation of blocks of rows of B, avoiding any degree growth at each stage via the computation of matrix remainders in polynomial matrix divisions by well-chosen matrix quotients (see Sections 3.4 and 4.2).

• A core tool in our construction of B is a generalization of [2, Algorithm 4] which, given some function a ∈ Я(A), finds a polynomial matrix representation of the multiplication map f ∈ Я(B) → af ∈ Я(A + B) (see Section 2 for definitions and notation). The version in [2] was for A = 0, and we show how to generalize it to any divisor A without impacting the asymptotic complexity.

Outline. Section 2 presents the main definitions and preliminary results used throughout the paper. Section 3 focuses on bases for the module of interpolant polynomials, starting with a versatile description of a family of such bases, then showing a polynomial matrix representation of an explicit choice of such a basis, and finally gathering some properties that constructively prove the existence a basis matrix B with small average degree. Section 4 describes the above-mentioned generalization of [2, Algorithm 4], and a complete algorithm for efficiently constructing B. Finally, Section 5 summarizes the resulting list decoder and proves the announced overall complexity bound.

Perspectives. After this work, the obvious perspective is to seek further complexity improvements beyond Õ(s 2 ℓ ω-1 µ ω-1 (n + g) + ℓ ω µ ω ). Remark that any improvement concerning the exponents of ℓ, s, or n would directly imply an improvement of the state-of-the-art complexity for the case of Reed-Solomon codes; a perhaps more accessible target would be to reduce the dependency on the genus g or on the quantity µ. Although our emphasis here is on the complexity of the decoder for a fixed code, allowing to perform some precomputations that depend only on this code, another natural direction for further work is to carry out a complexity analysis for these precomputations. This involves notably the computation of Apéry systems as introduced in [START_REF] Lee | Unique Decoding of General AG Codes[END_REF], which relates directly to active research topics such as the computation of bases of Riemann-Roch spaces (see for example [START_REF] Hess | Computing Riemann-Roch spaces in algebraic function fields and related topics[END_REF] and the literature overview in [START_REF] Berardini | A proof of the Brill-Noether method from scratch[END_REF]Section 7]).

Preliminaries

In this section we review some necessary concepts and notations about function fields, AG codes, the GS list decoder, and algorithms for polynomial matrices (i.e. matrices over F q [x]). We largely use the same notation as in [2] and definitions from [START_REF] Stichtenoth | Algebraic Function Fields and Codes[END_REF].

Function fields and AG codes

Let a function field F of genus g and full constant field F q be given. A divisor A = i n i A i of F is a formal Z-linear combination of places A i of F , such that finitely many of these places have a nonzero coefficient. Then the support of A, denoted by supp(A) is the set of all places A i of F such that n i ̸ = 0. A divisor A is called effective if for all i it holds n i ≥ 0. This is commonly denoted by A ≥ 0.

The degree of a place A i of F is defined as the dimension of the residue field F Ai of the place A i , viewed as an F q -vector space. If a place of F has degree one, it is called a rational place of F . The degree of a divisor A = i n i A i , is then simply defined as deg(A) = i n i deg(A i ), where deg(A i ) denotes the degree of the place A i . The Riemann-Roch space of a divisor A is given by

L(A) = {f ∈ F \ {0} | (f ) + A ≥ 0} ∪ {0},
where (f ) denotes the divisor of f . Divisors of nonzero functions are called principal divisors. The Riemann-Roch space L(A) is a finite dimensional vector space over F q , whose dimension will be denoted by l(A). The dimension of L(A) is the topic of the theorem of Riemann-Roch [START_REF] Stichtenoth | Algebraic Function Fields and Codes[END_REF]Theorem 1.5.15]. In particular, it implies that l(A) ≥ deg(A)+1-g and that equality holds whenever deg(A) ≥ 2g -1. Moreover l(A) = 0 if deg(A) < 0 since the degree of a principal divisor is zero. Now let P 1 , . . . , P n be distinct rational places of F and write

D = P 1 + • • • + P n . Given any divisor G such that supp(D) ∩ supp(G) = ∅, one defines the AG code C L (D, G) = {(f (P 1 ), . . . , f (P n )) | f ∈ L(G)},
where L(G) denotes the Riemann-Roch space of the divisor G. The dimension of the code equals l(G) -l(G -D), the functions in L(G -D) being precisely all function in L(G) that give rise to the zero codeword. In particular,

C L (D, G) is the zero code if deg(G) < 0. Moreover, the theorem of Riemann-Roch implies that dim(C L (D, G)) = n, i.e. C L (D, G) = F n q , whenever deg(G) ≥ n + 2g -1.
Because of this, we may assume 0 ≤ deg(G) ≤ n + 2g -1 and in particular deg(G) ∈ O(n + g).

Further we denote by P ∞ an additional rational place of F not occurring in the divisor D. (At first sight this seems to restrict the length of the AG code C L (D, G), since apparently not all rational places can occur in D, but as explained in [2, Section II.B] this is not the case: if needed, a small degree extension of the constant field will always produce "new" rational places from which P ∞ can be chosen; a similar observation about P ∞ was made independently in [START_REF] Lee | Base field extension of AG codes for decoding[END_REF].) We denote by µ ∈ Z >0 the smallest positive element in the Weierstrass semigroup of P ∞ and by x ∈ F a function that has pole order µ at P ∞ , but otherwise is without poles. Note that µ ≤ g +1, since the Weierstrass semigroup has g gaps; in fact µ ≤ g as soon as the set of these gaps is not {1, . . . , g}.

For any divisor A of F , let Я(A) = ∞ m=-∞ L(mP ∞ + A) and let Я = Я(0). As in [START_REF] Lee | Unique Decoding of General AG Codes[END_REF], for any nonzero a ∈ Я(A) we denote by δ A (a) the smallest integer m such that a ∈ L(mP ∞ + A), i.e. δ A (a) = -v P∞ (a) -v P∞ (A) and let δ(a) = δ 0 (a) = -v P∞ (a). We will take as convention that δ A (0) = -∞. Note that for any a ∈ Я(A) and b ∈ Я(B), one has δ A+B (ab) = δ A (a) + δ B (b). We will use the quantity δ A (a) to indicate the "size" of an element a ∈ Я(A); it generalizes the degree of a univariate polynomial. For example, the following known result, see for example [2, Lemma V.3] for a proof, indicates the size of interpolating functions in Я(A):

Lemma 2.1 ([2, Lemma V.3]). Let A be a divisor and E = E 1 + • • • + E N for distinct rational places E 1 , . . . , E N of F different from P ∞ such that supp(A) ∩ supp(E) = ∅. For any (w 1 , . . . , w N ) ∈ F N q there exists an a ∈ Я(A) with δ A (a) ≤ deg(E) + 2g -1 -deg(A)
such that a(E j ) = w j for j = 1, . . . , N .

Since by definition, the function x only has a pole in P ∞ , we have x ∈ Я\F q . Hence, we can view Я(A) as a free F q [x]-module. Following [START_REF] Lee | Unique Decoding of General AG Codes[END_REF] and using the same notation as in [2], we consider a specific kind of basis of Я(A) as F q [x]module, called an Apéry system of Я(A). Definition 2.2. For a divisor A and an integer i = 0, . . . , µ-1, let y

(A) i ∈ Я(A) be a function satisfying: 1. δ A (y (A) i ) ≡ i mod µ, 2. if a ∈ Я(A) and δ A (a) ≡ i mod µ, then δ A (y (A) i ) ≤ δ A (a). Further we define y i = y (0) i .
Using the theorem of Riemann-Roch, it is not hard to show the following lemma, see for example [2, Lemma III.3] for details:

Lemma 2.3 ([2, Lemma III.3]). For any divisor A it holds that -deg(A) ≤ δ A (y (A) i ) ≤ 2g -1 -deg(A) + µ, for i = 0, . . . , µ -1.
As mentioned in [START_REF] Lee | Unique Decoding of General AG Codes[END_REF], y

(A) 0 , . . . , y (A) µ-1 is an F q [x]-basis of Я(A). Given a ∈ Я(A)
, it is therefore possible to write a as an F q [x]-linear combination of these basis elements, and in fact the F q [x]-coefficients of this combination are unique. As demonstrated in [2, Lemma III.4], there is a very explicit upper bound for the degree of these occurring coefficient polynomials:

Lemma 2.4 ([2, Lemma III.4]). If a = µ-1 i=0 a i y (A) i ∈ Я(A), where a i ∈ F q [x] and A is a divisor, then deg(a i ) ≤ 1 µ δ A (a) -δ A (y (A) i ) ≤ 1 µ δ A (a) + deg(A) .

The Guruswami-Sudan list decoder

The key idea in the Guruswami-Sudan list decoding algorithm for

C L (D, G) [7] is to find a polynomial Q(z) = ℓ t=0 z t Q t ∈ F [z],
nonzero of degree at most ℓ, that vanishes with multiplicity at least s at each point (P i , r i ), where r = (r 1 , . . . , r n ) ∈ F n q is the received word. The idea is that if the coefficients Q t ∈ F are chosen in suitable subspaces of F and r has small enough Hamming distance from the sent codeword (f (P 1 ), . . . , f Theorem 2.5). This can then be used to recover f from Q by finding the roots of Q in F .

(P n )), then Q(f ) is the zero element in F (see
For the remainder of this paper fix s, ℓ ∈ Z >0 with s ≤ ℓ, where s is the multiplicity parameter and ℓ the designed list size of the Guruswami-Sudan list decoder. The corresponding list decoding radius will be denoted by τ .

More specifically, as in [2], we restrict ourselves to the setting where

Q = ℓ t=0 z t Q t with Q t ∈ Я(-tG) and define δ G (Q) = max t δ -tG (Q t ).
Further, given a received word r = (r 1 , . . . , r n ) ∈ F n q , we define

M s,ℓ,r = Q = ℓ t=0 z t Q t ∈ F [z] Q t ∈ Я(-tG),
Q has a root of multiplicity at least s at (P j , r j ) for all j .

(2.1)

In this setting, one has the following result, which is the crux of the correctness of the Guruswami-Sudan list decoder [START_REF] Guruswami | Improved Decoding of Reed-Solomon Codes and Algebraic-Geometric Codes[END_REF]:

Theorem 2.5 (Instance of Guruswami-Sudan). Let r ∈ F n q be a received word and Q ∈ M s,ℓ,r with δ G (Q) < s(n -τ ). If f ∈ L(G) is such that the Hamming distance between r and (f (P 1 ), . . . , f (P n )) is at most τ , then Q(f ) = 0.
For algorithmic purposes, it is convenient to give a description of M s,ℓ,r that is as explicit as possible. For the remainder of this article let G t = (t -s)D -tG for 0 ≤ t < s and G t = -tG for s ≤ t ≤ ℓ. From [2] we quote the following:

Theorem 2.6 ([2, Theorem IV.4 and Remark IV.7]). Let R ∈ Я(G) be such that R(P j ) = r j for 1 ≤ j ≤ n. Then M s,ℓ,r = ℓ t=0 (z -R) t Я(G t ) (2.2) = s-1 t=0 (z -R) t Я(G t ) ⊕ ℓ t=s z t-s (z -R) s Я(G t ). (2.3)
In [2], the first description (Equation (2.2)) was used to obtain a decoding algorithm for C L (D, G) with complexity Õ(ℓ ω+1 µ ω-1 (n + g)), while the second description (Equation (2.3)) improved this to Õ(sℓ ω µ ω-1 (n + g)). We will see in Section 3 that one ingredient in our improvement is to use yet another description of M s,ℓ,r .

Reminders on univariate polynomial matrices

In this paper, we will make use of a few classical notions on univariate polynomial matrices. For brevity, since only the univariate case will be encountered, we will just write "polynomial matrix".

For a polynomial matrix A = [a i,j ] i,j ∈ F q [x] m×ν , its degree is defined as max i,j deg(a i,j ) and denoted by deg(A); its column degrees is the tuple formed by the degrees of each of its columns. In the square case m = ν, the matrix A is said to be nonsingular if det(A) ̸ = 0, and unimodular if det(A) ∈ F q \ {0}.

We refer to [10,[START_REF] Beckermann | Normal forms for general polynomial matrices[END_REF] for the classical notions of Popov forms and reduced forms, row degrees and pivot indices, as well as their shifted generalizations.

We will use the following result on the feasibility of polynomial matrix division with remainder, and on the complexity of performing such divisions using a Newton iteration-based approach.

Lemma 2.7. Let A and B be matrices in F q [x] m×m with B nonsingular. Then there exists a matrix R ∈ F q [x] m×m such that A -R is a left multiple of B and deg(R) < deg(B). There is an algorithm PM-Rem which, on input A and B, returns such a matrix R using Õ(m ω (deg 3 The interpolant module M s,ℓ,r and polynomial matrix representations of it

(A) + deg(B))) operations in F q . Proof. The existence of R such that A -R is a left multiple of B is proved in [10,
We now study the module M s,ℓ,r more in depth. First we generalize Theorem 2.6 to get more flexibility on the choice of generators for M s,ℓ,r , and we make such an explicit choice (Section 3.1). Then we introduce several maps and the corresponding F q [x]-matrices (Section 3.2). This allows us to describe a basis of M s,ℓ,r as an F q [x]-module, and to represent this module as the F q [x]-row space of an explicit polynomial matrix B s,ℓ,r in F q [x] m×m , for m = µ(ℓ+1) (Section 3.3). Finally, in Section 3.4, we deduce another basis matrix P s,ℓ,r which is less explicit than B s,ℓ,r , but computationally easier to construct and manipulate. Throughout, it is assumed that the received vector is r = (r 1 , . . . , r n ) ∈ F n q and that R ∈ Я(G) is a function satisfying R(P j ) = r j for 1 ≤ j ≤ n as well as the bound from Lemma 2.1,

δ G (R) ≤ n + 2g -1 -deg(G).
3.1 A more flexible description of M s,ℓ,r

In Theorem 2.6, two ways to describe the module M s,ℓ,r were given. We now indicate a more general shape for alternative descriptions for M s,ℓ,r .

Theorem 3.1. For s ≤ t ≤ ℓ, let f t (z) = t-s i=0 f ti z t-s-i ∈ F [z], where f ti ∈ Я(iG) and deg z (f t ) = t -s, hence in particular f t0 ∈ F q \ {0}. Then M s,ℓ,r = s-1 t=0 (z -R) t Я(G t ) ⊕ ℓ t=s f t (z)(z -R) s Я(G t ).
Proof. Using Equation (2.2) in Theorem 2.6, and since by definition G t = -tG for t ≥ s, it is sufficient to show that

M s,ℓ,r = s-1 t=0 (z -R) t Я(G t ) ⊕ ℓ t=s (z -R) t Я(-tG) is equal to M := s-1 t=0 (z -R) t Я(G t ) ⊕ ℓ t=s f t (z)(z -R) s Я(-tG).
We first prove the inclusion "M s,ℓ,r ⊇ M". For this we show, for t = s, . . . , ℓ, the inclusion

f t (z)(z -R) s Я(-tG) ⊆ t k=s (z -R) k Я(-kG). This follows from f t (z) ∈ t k=s (z -R) k-s Я((t -k)G), which itself comes from using the binomial formula on f t (z) = t-s j=0 (z -R + R) t-s-j f tj . Indeed, this yields f t (z) = t k=s (z -R) k-s ftk where, for s ≤ k ≤ t, ftk = t-k j=0 t-s-j k-s R t-k-j f tj is in Я((t -k)G).
Now we prove the inclusion "M s,ℓ,r ⊆ M". For this we show, for each t = s, . . . , ℓ, the inclusion

(z -R) t Я(-tG) ⊆ t k=s f k (z)(z -R) s Я(-kG). Similarly to the above, it is enough to prove (z -R) t-s ∈ t k=s f k (z)Я((t -k)G).
We proceed by induction on t ∈ {s, . . . , ℓ}, showing that (z-R) t-s = t k=s f k (z)α tk for certain α tk ∈ Я((t -k)G). The property is obvious for t = s, since f s (z) = f s0 ∈ F q \ {0}. Let t ∈ {s + 1, . . . , ℓ} and assume the property holds from s to t -1. Then

(z -R) t-s = 1 ftt   f t (z) - t-1 j=s (z -R) j-s ftj   = 1 ftt f t (z) + t-1 k=s f k (z)   -1 ftt t-1 j=k α jk ftj  
which proves the property for t, since ftt ∈ F q \{0} and α jk ftj ∈ Я((t-k)G).

As a first observation, the second description in Theorem 2.6 is now an easy consequence of Theorem 3.1 (which we proved using only the first description in Theorem 2.6). To obtain a faster decoder, we will start from the following description of the interpolant module.

Corollary 3.2. For s ≤ t ≤ ℓ, let g t (z) = t-s i=0 i+s-1 i R i z t-s-i ∈ F [z]. Then M s,ℓ,r = s-1 t=0 (z -R) t Я(G t ) ⊕ ℓ t=s g t (z)(z -R) s Я(G t ). Proof. We only need to check that f t (z) = g t (z) is a valid choice in Theorem 3.1. The first condition i+s-1 i R i ∈ Я(iG) follows from R ∈ Я(G). The second condition deg z (g t (z)) = t -s is obvious.
In this description, the polynomial g t (z)(z -R) s has at most s + 1 nonzero coefficients, as we will see in the next lemma (Lemma 3.3) which gives an explicit formula for these coefficients. In fact, looking back at the description in Equation (2.3), the polynomial z t-s (z -R) s also has at most s + 1 nonzero coefficients. Yet, the advantage of g t (z)(z -R) s over z t-s (z -R) s is the range of monomials that may appear with nonzero coefficients. Apart from the common leading term z t , for the latter these monomials are z t-s , z t-s+1 , . . . , z t-1 , whereas for the former they are 1, z, . . . , z s-1 independently of t. As we will see in Sections 3.3 and 3.4, this particular location of nonzero coefficients is instrumental in our approach for building an F q [x]-basis of M s,ℓ,r which has small average column degree.

Lemma 3.3. For s ≤ t ≤ ℓ, let g t (z) = t-s i=0 i+s-1 i R i z t-s-i . Then z t - g t (z)(z -R) s has degree at most s -1. Moreover, for 0 ≤ j < s, the coefficient of z j in g t (z)(z -R) s equals γ t,j R t-j , where γ t,j = s i=s-j s i t -j -i + s -1 s -1 (-1) i . (3.1)
Proof. Using a classical power series expansion formula in z -1 , we obtain that

z t = (z -R) s z t-s 1 - R z -s = (z -R) s i≥0 i + s -1 i R i z t-s-i .
This shows that

z t -g t (z)(z -R) s = z t -(z -R) s i≥t-s+1 i + s -1 i R i z t-s-i ,
Hence the polynomial z t -g t (z)(z -R) s has degree at most s -1. To prove the second part of the lemma, one can simply expand the product g t (z)(z -R) s , yielding that for 0 ≤ j < s the coefficient of z j in g t (z)(z -R) s equals γ t,j R t-j , just as indicated.

Inclusion and multiplication maps, and their matrices

In this subsection we study two types of F q [x]-module homomorphisms: the first type are inclusion maps of submodules in a module, while the second type are maps of multiplication by some R ∈ Я(G). We will also consider matrices over F q [x] which represent these maps, as this will help us describe and compute bases of M s,ℓ,r as an F q [x]-module. Note that, if the ranks as F q [x]-modules of the domain and codomain of the considered map are the same, then this map can, after choosing bases, be represented by a square F q [x]-matrix.

We start with the maps derived from the inclusions Я(G t ) ⊆ Я(-tG) for 0 ≤ t < s; these inclusions follow from G t = (t -s)D -tG ≤ -tG. Definition 3.4. For 0 ≤ t < s, the map ı t : Я(G t ) → Я(-tG) is defined as the natural inclusion map of Я(G t ) in Я(-tG). We denote by D t ∈ F q [x] µ×µ the matrix of ı t with respect to the ordered F q [x]-bases (y (Gt) 0 , . . . , y (Gt) µ-1 ) for Я(G t ) and (y (-tG) 0 , . . . , y (-tG) µ-1 ) for Я(-tG). Remark 3.5. In this paper, such matrices of maps are considered in a row-wise manner. For example, in this definition, the ith row of D t yields the expression of ı t (y (Gt) i

) as an F q [x]-linear combination of the mentioned basis of Я(-tG).

For deriving complexity estimates, we will use the following bound on the degree of any single entry of D t . Lemma 3.6. The matrix D t is nonsingular and deg (D t ) is in O(s(n + g)/µ).

Proof. Since ı t is an injection, D t is nonsingular. Let [p ij ] 0≤i,j<µ be the entries of D t , so that y

(Gt) i = µ-1 j=0 p ij y (-tG) j for 0 ≤ i < µ and deg(D t ) = max ij deg(p ij ).
Using Lemmas 2.3 and 2.4 we see that

deg(p ij ) ≤ 1 µ (δ -tG (y (Gt) i ) -t deg(G)) ≤ 1 µ (δ Gt (y (Gt) i ) -t deg(G)) ≤ 1 µ (2g -1 + µ -deg(G t ) -t deg(G)) = 1 µ (2g -1 + µ + (s -t)n) ∈ O(s(n + g)/µ).
We will also use the following, similarly defined inclusion maps and matrices, where we have defined H t = -sD -tG for 0 ≤ t < s. Definition 3.7. For 0 ≤ t < s, the map ȷ t : Я(H t ) → Я(-tG) is defined as the natural inclusion map of Я(H t ) in Я(-tG). We denote by E t ∈ F q [x] µ×µ the matrix of ȷ t with respect to the F q [x]-bases (y (Ht) 0 , . . . , y (Ht) µ-1 ) for Я(H t ) and (y (-tG) 0 , . . . , y (-tG) µ-1 ) for Я(-tG). This matrix E t satisfies properties similar to those of D t .

Lemma 3.8. The matrix E t is nonsingular and deg(E t ) is in O(s(n + g)/µ).

Proof. The proof can be directly adapted from that of Lemma 3.6.

We now turn our attention to the maps of multiplication by some R ∈ Я(G). Definition 3.9. For 1 ≤ t ≤ ℓ, we let the multiplication map R t : Я(-tG) → Я(-(t-1)G) be defined by R t : f → Rf . We denote by R t ∈ F q [x] µ×µ the matrix of R t with respect to the ordered F q [x]-bases (y ) for Я(-(t -1)G).

Although this definition is valid for any R ∈ Я(G), recall that here we consider specifically R such that δ G (R) ≤ n + 2g -1 -deg(G). This allows us to bound the degree of any single entry of R t , as follows.

Lemma 3.10. The matrix degree of R t is in O((n + g)/µ).

Proof. Using Lemma 2.3, we see that for any 0 ≤ i, t < µ, δ -(t-1)G (Ry

(-tG) i ) = δ G (R) + δ -tG (y (-tG) i ) ≤ δ G (R) + 2g -1 + t deg(G) + µ. Let [p ij ] 0≤i,j<µ be the entries of R t , so that Ry (-tG) i = µ-1 j=0 p ij y (-(t-1)G) j for 0 ≤ i < µ and deg(R t ) = max ij deg(p ij ). Then from Lemma 2.4 and the fact that δ G (R) ≤ n + 2g -1 -deg(G), we obtain deg(p ij ) ≤ 1 µ δ -(t-1)G (Ry (-tG) i ) + deg(-(t -1)G) ≤ 1 µ (δ G (R) + 2g -1 + t deg(G) + µ -(t -1) deg(G)) = 1 + 1 µ (δ G (R) + 2g -1 + deg(G)) ≤ 1 + 1 µ (n + 4g -2) .
In what follows we will also use this notation: Definition 3.11. For 0 ≤ t ≤ ℓ and 0 ≤ j ≤ ℓ, the matrix R (t,j) ∈ F q [x] µ×µ is defined as

R (t,j) =    R t R t-1 • • • R j+1 for 0 ≤ j < t;
the µ × µ identity matrix I for j = t; the µ × µ zero matrix 0 for t < j ≤ ℓ.

The definition of the R t 's implies that, for 0 ≤ j ≤ t, R (t,j) is the matrix of the following map of multiplication by R t-j : for Я(-jG). Similarly if j ≤ t < s, then D t R (t,j) is the matrix of the map

R j+1 • R j+2 • • • • • R t : Я(-tG) → Я(-jG), f → R t-j f,
R j+1 • R j+2 • • • • • R t • ı t : Я(G t ) → Я(-jG), f → R t-j f,

A first polynomial matrix basis of M s,ℓ,r

From Theorem 3.1, one may deduce a basis of M s,ℓ,r as an F q [x]-module. Lemma 3.12. M s,ℓ,r is an F q [x]-module of rank m := µ(ℓ + 1), and admits the following basis:

(z -R) t y (Gt) i | 0 ≤ t < s, 0 ≤ i < µ f t (z)(z -R) s y (Gt) i | s ≤ t ≤ ℓ, 0 ≤ i < µ , for any family of polynomials {f t (z) ∈ F [z] | s ≤ t ≤ ℓ} as in Theorem 3.1.
Proof. Let B be the claimed basis of M s,ℓ,r . Since ⟨y

(Gt) 0 , . . . , y (Gt) µ-1 ⟩ Fq[x] = Я(G t ) for 0 ≤ t ≤ ℓ,
from Theorem 3.1 it follows both that B ⊆ M s,ℓ,r and that any element of M s,ℓ,r is an F q [x]-linear combination of polynomials in B; whence ⟨B⟩ Fq[x] = M s,ℓ,r . To prove that B is a basis, it remains to show that its elements are

F q [x]-linearly independent. Let (α t,i ) 0≤i<µ,0≤t<k ∈ F q [x] m be a tuple such that 0≤t<s,0≤i<µ α t,i (z -R) t y (Gt) i + s≤t≤ℓ,0≤i<µ α t,i f t (z)(z -R) s y (Gt) i = 0. Since f t (z)(z -R) s has degree t, the polynomials {(z -R) t | 0 ≤ t < s} ∪ {f t (z)(z -R) s | s ≤ t ≤ ℓ}
form a basis of the F -vector space F [z] deg z ≤ℓ . Thus, from the above identity we deduce that 0≤i<µ α t,i y

(Gt) i = 0 for 0 ≤ t ≤ ℓ.

By definition of the y (Gt) i

To represent such a basis of M s,ℓ,r as a matrix B s,ℓ,r over F q [x], we see M s,ℓ,r as a submodule of the free F q [x]-module 0≤t≤ℓ z t Я(-tG) of rank m, with basis z j y

(-tG) k , 0 ≤ t ≤ ℓ, 0 ≤ k < µ.
The following F q [x]-module isomorphism will be useful for describing B s,ℓ,r :

φ ℓ : F q [x] 1×m → ℓ t=0 z t Я(-tG) [p 0,0 • • • p 0,µ-1 | • • • | p ℓ,0 • • • p ℓ,µ-1 ] → ℓ t=0 µ-1 k=0 p t,k y (-tG) k z t . (3.2)
Then, the rows of B s,ℓ,r are the preimages by φ ℓ of the elements of the basis of M s,ℓ,r described in Lemma 3.12. Choosing specifically for f t (z) the polynomial g t (z) described in Section 3.1, and using the maps and matrices defined in Section 3.2, we obtain the following explicit description of B s,ℓ,r .

Definition 3.13. Let m = µ(ℓ + 1). The matrix B s,ℓ,r ∈ F q [x] m×m is defined by blocks as B s,ℓ,r = [ D 0 R I ] where • I is the (m -µs) × (m -µs) identity matrix;

• 0 is the (µs) × (m -µs) zero matrix; µs) is defined by blocks as

• D ∈ F q [x] (µs)×(
D = γ t,j D t R (t,j) 0≤t<s,0≤j<s =      D 0 -D 1 R 1 D 1 D 2 R 2 R 1 -2D 2 R 2 D 2 . . . . . .     
where γ t,j = (-1) t-j t j for 0 ≤ t < s, 0 ≤ j < s;

• R ∈ F q [x] (m-µs)×(µs) is defined by blocks as

R = γ t,j R (t,j) s≤t≤ℓ,0≤j<s =    γ s,0 R (s,0) • • • γ s,s-1 R (s,s-1) . . . . . . γ ℓ,0 R (ℓ,0) • • • γ ℓ,s-1 R (ℓ,s-1)   
where γ t,j for s ≤ t ≤ ℓ, 0 ≤ j < s is defined in Equation (3.1).

Theorem 3.14. The matrix B s,ℓ,r from Definition 3.13 is a basis of M s,ℓ,r , seen as an F q [x]-submodule of 0≤t≤ℓ z t Я(-tG). More precisely, indexing the rows of B s,ℓ,r from 0 to m -1, for 0 ≤ t ≤ ℓ and 0 ≤ i < µ its row at index

tµ + i is φ -1 ℓ ((z -R) t y (Gt) i ) if t < s, and φ -1 ℓ (g t (z)(z -R) s y (Gt) i ) if s ≤ t ≤ ℓ.
Proof. This follows directly from the construction of B s,ℓ,r and from the definition of D t and R (t,j) in Section 3.2. Indeed, for 0 ≤ t ≤ ℓ and 0 ≤ i < µ, the image by φ ℓ of the row tµ + i of B s,ℓ,r as built in Definition 3.13 is

t j=0 (-1) t-j t j R t-j y (Gt) i z j = (z -R) t y (Gt) i if t < s,
and z t y

(-tG) i + s-1 j=0 γ t,j R t-j y (-tG) i z j = g t (z)(z -R) s y (-tG) i if s ≤ t ≤ ℓ,
where the last identity comes from Lemma 3.3.

Observe in particular the effect of our choice of polynomials g t (z) from Section 3.1: only the left µs columns [ D R ] of B s,ℓ,r are nontrivial, while the remaining columns [ 0 I ] are standard basis vectors. A parallel can be drawn with the remark on the monomials appearing in g t (z)(z -R) s , in Section 3.1. In contrast, the two descriptions from [2] recalled in Theorem 2.6 lead to matrices which are block-triangular as well, but with a lower triangular part which is either dense (if using Equation (2.2)) or is a band matrix (if using Equation (2.3)). Although in the latter case the number of nonzero blocks is the same as in B s,ℓ,r , the fact that these nonzero blocks are confined to the leftmost columns brings us closer to knowing an F q [x]-basis of M s,ℓ,r with small average column degree, as we are going to see in the next subsection.

A small-degree polynomial matrix basis of M s,ℓ,r

Keeping the same notation as in the previous subsection, we deduce from the matrix B s,ℓ,r a whole collection of suitable matrices for representing bases of M s,ℓ,r as an F q [x]-module, which all share the property that their rightmost m -µs columns are the standard basis vectors [ 0 I ]. It is within this collection that we will find a F q [x]-basis of M s,ℓ,r with small average column degree, which means that its shifted Popov form can be computed efficiently.

Theorem 3.15. For any matrix R ∈ F q [x] (m-µs)×(µs) such that R -R is a left multiple of D, the matrix M s,ℓ,r := [ D 0 R I ] ∈ F q [x] m×m is a basis of M s,ℓ,r , seen as an F q [x]-submodule of 0≤t≤ℓ z t Я(-tG).
In particular, if R has degree in O(s(n + g)/µ), then the sum of column degrees of M s,ℓ,r is in O(s 2 (n + g)), and the d-Popov form of M s,ℓ,r can be computed in Õ(s 2 ℓ ω-1 µ ω-1 (n + g) + ℓ ω µ ω ) operations in F q for any shift d ∈ 1 µ Z (ℓ+1)µ . Proof. The matrices B s,ℓ,r and M s,ℓ,r are left-unimodularly equivalent, since

I 0 -Q I D 0 R I = D 0 R I where Q ∈ F q [x] (m-µs)×(µs) is the quotient matrix such that R = QD + R.
Hence the rows of M s,ℓ,r form a basis of M s,ℓ,r .

The degree bounds in Section 3.2 and the construction of R (t,j) show that, for 0 ≤ t < s and 0 ≤ j < s, both deg(D t ) and deg(R (t,j) ) are in O(s(n + g)/µ). Therefore the degree of D = [γ t,j D t R (t,j) ] 0≤t<s,0≤j<s is also in O(s(n + g)/µ). Then, under the assumption on deg( R) stated in the theorem, the first µs columns of M s,ℓ,r have degree in O(s(n+g)/µ), whereas its last m-µs columns have degree 0. The claimed bound on the column degrees of M s,ℓ,r follows.

Computing the shifted Popov form of M s,ℓ,r , for any integer shift d ∈ Z (ℓ+1)µ , can then be performed in Õ(ℓ ω µ ω ⌈ s 2 (n+g) ℓµ ⌉) operations in F q [14, Theorem 1.3]. It has been showed that the case of a shift d with fractional entries in 1 µ Z (ℓ+1)µ directly reduces to the case of an integer shift by both permuting the matrix columns appropriately and rounding down the entries of d to integers; see [15, Section III.A] [2, Theorem V.9] for the present case, and [START_REF] Neiger | Bases of relations in one or several variables: fast algorithms and applications[END_REF]Section 1.3.4] for transforming more generally any module monomial ordering on F q [x] (ℓ+1)s into a corresponding shift in Z (ℓ+1)µ . The inequality ⌈ s 2 (n+g) ℓµ ⌉ < s 2 (n+g) ℓµ + 1 leads to the cost bound stated in the theorem.

Finally, in Theorem 3.17 we will make the above result more effective by describing an explicit construction of such a small-degree matrix R, using remainders in the matrix division of R modulo the matrices E 0 , . . . , E s-1 defined in Section 3.2. Here are some explanations why such a degree reduction is needed, and not straightforward. Remark 3.16. Observe that the matrix R, as defined in Section 3.3, may have degrees too large for our purpose; that is, simply taking R = R in the above theorem is not interesting as deg(R) is most likely not in O(s(n + g)/µ). In fact, by definition R has ℓ + 1 -s blocks of µ rows each with sµ columns, and the degree of the ith block of rows is in O((s + i) n+g µ ). In total, the dense representation of R therefore uses

O   1≤i≤ℓ+1-s µ(µs)(s + i) n + g µ   ⊆ O ℓ 2 sµ(n + g)
coefficients from F q , and this asymptotic bound can be reached. Indeed, it is reached already in the case of Reed-Solomon codes, where R (t,j) is a polynomial in F q [x], which is the power R t-j of some polynomial R ∈ F q [x] whose degree is n -1 generically. Thus, simply the size of the storage of R can already be in conflict with our target complexity. This also implies that we must aim to compute a smaller degree R without computing all of R.

Theorem 3.17. For each s ≤ t ≤ ℓ and 0 ≤ j < s, there exists a matrix R(t,j) such that R (t,j) -R(t,j) is a left multiple of E j and deg( R(t,j) ) < deg(E j ).

Then, the matrix R = [γ t,j R(t,j) ] s≤t≤ℓ,0≤j<s ∈ F q [x] (m-µs)×(µs) has degree in O(s(n + g)/µ) and is such that R -R is a left multiple of D.

Proof. The existence of R(t,j) with the specified properties follows directly from Lemma 2.7. The bound on deg( R) follows from deg(E j ) ∈ O(s(n+g)/µ), proved in Lemma 3.8. By construction, R -R = [γ t,j (R (t,j) -R(t,j) )] s≤t≤ℓ,0≤j<s is a left multiple of

E =      E 0 E 1 . . . E s-1      ∈ F q [x] (µs)×(µs) ,
hence it remains to prove that E is itself a left multiple of D.

We now show that each row of E is a left multiple of D. Let 0 ≤ i < µ and 0 ≤ t < s. Similarly to the considerations in Section 3.3, we observe that the row tµ + i of E corresponds to the polynomial z t y (Ht) i ∈ z t Я(H t ), which is in M s,ℓ,r since any function in Я(H t ) = Я(-sD -tG) has valuation at least s at each of the places P 1 , . . . , P n . Since z t y (Ht) i has z-degree less than s, by Theorem 2.6 it is in 0≤j<s (z -R) j Я(G j ), which means that the row tµ + i of E is a left multiple of D. . In order to do this, we generalize [2, Algorithm 4]. We follow the same approach as in [2] for showing the correctness and complexity of this generalization. Definition 4.1. For any Q(z) ∈ F [z], for any rational place P ∈ P F that is not a pole of any of the coefficients of Q(z), and for α ∈ F q , we denote by Q(P, α) the evaluation of Q(α) ∈ F at P . Definition 4.2. Let A, B be divisors and let

E = E 1 +• • •+E N for distinct ratio- nal places E 1 , . . . , E N of F different from P ∞ such that supp(A) ∩ supp(E) = ∅ and supp(B) ∩ supp(E) = ∅. For a ∈ Я(A), we define the F q [x]-module N A,B,E (a) = {Q = Q 0 + Q 1 z ∈ Я(A + B) ⊕ zЯ(B)
such that Q(P, a(P )) = 0 for all P ∈ supp(E)}.

In the following lemmas, we use the same notation A, B, E as in Definition 4.2.

Lemma 4.3. Let a ∈ Я(A). If Q = Q 0 + zQ 1 ∈ N A,B,E (a) with max{δ A+B (Q 0 ), δ B (Q 1 ) + δ A (a)} < deg(E) -deg(A + B), then Q(a) = 0, i.e. Q ∈ (z -a)Я(B). and -deg(A) ≤ δ A (a) ≤ δ B (y (B) i ) + δ A (a) + deg(B) ≤ 2g -1 + µ + δ A (a) ≤ -1 + deg(E) -deg(A) < N -deg(A).
Since deg(u k ) ≤ N/µ for k = 0, . . . , µ -1, then the total complexity of the algorithm is given by [2, Cor. V.10] as

Õ µ ω-1 max{| deg(E)|, | deg(E) -deg(A)|, | deg(A)|} ⊆ Õ(µ ω-1 (N + | deg(A)|)) operations in F q .
4.2 Computing a small-degree F q [x]-basis of M s,ℓ,r Theorem 4.9. Algorithm 2 is correct and costs Õ(ℓµ ω-1 N + s 2 ℓµ ω-1 (n + g)) operations in F q .

Proof. The correctness follows from the correctness of the called algorithms and from the results in Section 3.4.

For complexity, let us first consider the total cost of the calls to BasisProducts; for completeness we also give at the same time the detailed verification that the constraint on deg(E) required in the input of this algorithm is satisfied.

• For t = 0, . . . , s -1, the call at Line 3 is for the divisor A = (s -t)D and the function a = 1, and therefore costs Õ(µ ω-1 (N + | deg((s -t)D)|)) = Õ(µ ω-1 (N + (s -t)n)) according to Theorem 4.8. Over the s iterations, this cost is in Õ(sµ ω-1 N +s 2 µ ω-1 n). Furthermore the input requirements of BasisProducts impose deg(E) ≥ deg((s -t)D) + δ (s-t)D (1) + 2g + µ for all t = 0, . . . , s -1, hence we must ensure deg(E) ≥ sn + 2g + µ; this is implied by the input requirements of InterpolantPolMatBasis.

• The calls at Line 4 are for the divisor A = (s-t)D and the function a = 1.

Thus their total complexity fits within the one in the previous item, and these calls do not bring any additional restriction on deg(E).

• Finally, the calls to BasisProducts at Line 9 are for the divisor A = G and the function a = R, for each of the ℓ iterations. In total, this costs Algorithm 2 InterpolantPolMatBasis(r, D, G, E, x, y (-tG) , y (Gt) , y (Ht) )

Õ(ℓµ ω-1 (N +| deg(G)|)) = Õ(ℓµ ω-1 N +ℓµ ω-1 (n+g)). These calls all add the same constraint on deg(E), namely deg(E) ≥ deg(G)+δ G (R)+2g +µ. Since δ G (R) ≤ n + 2g -1 -deg(G)
Input:

• received word r ∈ F n q , • the code divisors D and G, • a divisor E = E 1 +• • •+E N , where E 1 , . . . , E N are pairwise distinct rational places not in {P ∞ } ∪ supp(G), with deg(E) ≥ sn + 4g + µ -1, • evaluations x = (x j ) j=1,...,N , where x j = x(E j ) ∈ F q ,
• evaluations y (-tG) = (y

(-tG) i,j
) i=0,...,µ-1 j=1,...,N for t = -1, 0, . . . , ℓ, where y

(-tG) i,j = y (-tG) i (E j ) ∈ F q ,
• evaluations y (Gt) = (y (Gt) i,j ) i=0,...,µ-1 j=1,...,N for t = 0, . . . , s -1, where G t = (t -s)D -tG and y

(Gt) i,j = y (Gt) i (E j ) ∈ F q ,
• evaluations y (Ht) = (y (Ht) i,j ) i=0,...,µ-1 j=1,...,N for t = 0, . . . , s -1, where H t = -sD -tG and y

(Ht) i,j = y (Ht) i (E j ) ∈ F q . Output: a matrix M s,ℓ,r := [ D 0 R I ] ∈ F q [x
] m×m as in Theorem 3.15: M s,ℓ,r is a basis of M s,ℓ,r seen as an F q [x]-submodule of 0≤t≤ℓ z t Я(-tG) and deg ( R) has degree in O(s(n + g)/µ). D t ← BasisProducts((s -t)D, G t , E, (1, . . . , 1), x, y (-tG) , y (Gt) )

4:

E t ← BasisProducts(sD, H t , E, (1, . . . , 1), x, y (-tG) , y (Ht) ) R t ← BasisProducts(G, -tG, E, r, x, y (-(t-1)G) , y (-tG) )

The interpolation at Line 6 costs Õ(µ ω-1 (N + g)), by [2,Lemma V.12]. The evaluation at Line 7 costs Õ(µN + δ G (R) + deg(G)), by [2, Lemma V.2]; our assumption on deg(E) implies that this is in Õ(µN ).

The costly part of the computation of D at Lines 10 to 14 is the matrix products at Line 13. For each t = 1, . . . , s -1, we start from D t which has degree in O(s(n + g)/µ) (see Lemma 3.6), and then we multiply iteratively for j = t -1, . . . , 0 by R j whose degree is in O((n + g)/µ) (see Lemma 3.10). Thus, altogether we perform about s 2 2 multiplications of two µ × µ matrices of degree in O(s(n + g)/µ), for a total cost of Õ(s 3 µ ω-1 (n + g)).

The costly part of the computation of R at Lines 15 to 20 is the matrix products and matrix remainders at both Lines 18 and 19. Consider a fixed iteration j, for some j ∈ {0, . . . , s-1}. The above recalled bound on deg(R t ) ensures that the product R s R s-1 • • • R j+1 at Line 18 can be computed in Õ(s 2 µ ω-1 (n + g)), and has degree in O(s(n + g)/µ). Then, since deg(E j ) is in O(s(n + g)/µ) as well (see Lemma 3.8), the matrix division with remainder at the same line costs Õ(sµ ω-1 (n + g)) and returns a matrix whose degree is in O(s(n + g)/µ) (see Lemma 2.7). At Line 19 there are ≤ ℓ iterations, and similarly to Line 18, each of them performs a matrix product and then a matrix division with remainder which both cost Õ(sµ ω-1 (n + g)), for a total of Õ(sℓµ ω-1 (n + g)). Note that degrees remain controlled since each of these iterations produces a matrix remainder whose degree is less than deg(E j ), which is in O(s(n+g)/µ). Summing over the iterations for j = 0, . . . , s -1, and using s ≤ ℓ, we get a cost bound of Õ(s 2 ℓµ ω-1 (n + g)) operations in F q for Lines 15 to 20.

Finally, summing the costs of each analyzed part above yields the result.

5 Decoder with better complexity

The decoding algorithm

The overall decoding algorithm is the one in [2, Algorithm 7] with the first three lines replaced by a call to InterpolantPolMatBasis, which provides P s,ℓ,r in complexity Õ(s 2 ℓµ ω-1 (n+g)) according to Theorem 4.9; indeed one can take N ∈ O(sn + g + µ) ⊂ O(s(n + g)). After that, two expensive computations remain. The first one asks to find the shifted Popov form of P s,ℓ,r [2, Algorithm 7, Line 5], which costs Õ(s 2 ℓ ω-1 µ ω-1 (n + g) + ℓ ω µ ω ) operations in F q according to Theorem 3.15. The second one is the root finding step [2, Algorithm 7, Line 10], whose complexity is in Õ(sℓµ ω-1 (n + g)) as detailed in Section 5.2. Hence the overall cost bound Õ(s 2 ℓ ω-1 µ ω-1 (n + g) + ℓ ω µ ω ) for the list decoder. Due to the modification of the first steps, the precomputed data slightly differs from the one listed in [2, Section VI]. Here, we do not need to know the evaluations of Я-module generators for Я(G t ), t = 0, . . . , ℓ, denoted by "g" in the above reference. As a kind of replacement, we need the evaluations y (Gt) and y (Ht) for t = 0, . . . , s -1 and y (-tG) for t = 0, . . . , ℓ, as defined in the input of InterpolantPolMatBasis. Observe that this algorithm also requires y (-tG) for t = -1; but y (G) is already part of the precomputation in [2,Section VI]

  Theorem 6.3-15, page 389]. This reference also ensures that B -1 R is a so-called strictly proper matrix fraction, which implies deg(R) < deg(B) as showed for example in [10, Lemma 6.3-10, page 383]. To find R, one may start with computing a Popov form P ∈ F q [x] m×m of B, which costs Õ(m ω deg(B)) [16, Theorem 21]. In particular, B and P are left-unimodularly equivalent, so that left multiples of B are the same as left multiples of P . Thus R can be found as a remainder in the division of A by P , since deg(P ) ≤ deg(B). Since P is column reduced, to find this remainder we can apply [14, Algorithm 1]: this boils down to one truncated expansion at order O(deg(A)) of the inverse of an m × m matrix (whose constant term is invertible), and two multiplications of two m×m matrices of degree in O(deg(A)+deg(P )). Hence the total cost Õ(m ω (deg(A)+ deg(P ))), which concludes the proof since deg(P ) ≤ deg(B).

  in the ordered bases (y (-tG) 0 , . . . , y (-tG) µ-1 ) for Я(-tG) and (y (-jG) 0 , . . . , y (-jG) µ-1 )

  in the ordered bases (y (Gt) 0 , . . . , y (Gt) µ-1 ) for Я(G t ) and (y (-jG) 0 , . . . , y (-jG) µ-1 ) for Я(-jG).

4

  Efficient construction of a polynomial matrix basis of M s,ℓ,r4.1 Computing multiplication mapsConsider the following problem: given two divisors A and B and a function a ∈ Я(A), compute the products y a ∈ Я(A + B), expressed in the basis y

1 :

 1 ▷ Compute matrices Dt and Et in Fq[x] µ×µ , see Definitions 3.4 and 3.7 2: for t = 0, . . . , s -1 do 3:

5 :

 5 ▷ Compute matrices R1, . . . , R ℓ in Fq[x] µ×µ , see Definition 3.96: R ∈ Я(G) ← Interpolate(r, D, G, x, y (G) ) ▷ [2, Algorithm 2] 7: r ∈ F N q ← Evaluate(R, E, G, x, y (G) ) ▷ [2,Algorithm 1] 8: for t = 1, . . . , ℓ do 9:

Acknowledgments

The first author would like to acknowledge the support from The Danish Council for Independent Research (DFF-FNU) for the project Correcting on a Curve, Grant No. 8021-00030B. The second author would like to acknowledge the support from Sorbonne Université's Faculty of Science and Engineering through the project Tremplin 2022: Fast reconstruction of multivariate algebraic relations; from the Agence nationale de la recherche (ANR), grant agreement ANR-19-CE40-0018 De Rerum Natura; from the ANR&Austrian Science Fund FWF, grant agreements ANR-22-CE91-0007 EAGLES and ANR-19-CE48-0015 ECARP; and from the EOARD-AFOSR, grant agreement FA8665-20-1-7029.

Proof. Since Q ∈ N A,B,E (a), we have Q(a) ∈ Я(A + B). Hence by definition of δ A+B , we have Q(a) ∈ L(δ A+B (Q(a))P ∞ + A + B). Since for all E j ∈ supp(E), we have Q(a)(E j ) = 0 and supp(E) ∩ (supp(A) ∪ supp(B) ∪ {P ∞ }) = ∅, we conclude that Q(a) ∈ L(δ A+B (Q(a))P ∞ + A + B -E). Moreover,

which ensures that the aforementioned Riemann-Roch space is trivial.

Like in [2], our generalization will use the notion of an x-partition of E. We recall the definition, see also [2,Definition V.4]; the existence of an x-partition of E was shown in [2,Lemma V.6]. Definition 4.4.

where E 1 , . . . , E N are distinct rational places different from P ∞ , and U 0 , . . . , U µ-1 are effective divisors satisfying

then we will say that U 0 , . . . , U µ-1 is an x-partition of E. Definition 4.5. For a polynomial matrix A ∈ F q [x] 2µ×µ and nonzero polynomials u 0 , . . . , u µ-1 ∈ F q [x] \ {0}, we define

where A * ,k is the column k of A.

Note that we have the following inclusion of F q [x]-submodules:

In particular, H u (A) is a free F q [x]-module of rank 2µ, and each of its bases can be represented as a nonsingular 2µ × 2µ matrix over F q [x]. Lemma 4.6. Let a ∈ Я(A). Let U 0 , . . . , U µ-1 be an x-partition of E, and let

, therefore it suffices to show that for any

This is true since for every E j ∈ U k the following identity holds, where α = x(E j ):

Lemma 4.7. In the context of Lemma 4.6, if

then exactly µ rows of P have d-degree less than 1 µ (deg(E) -deg(A)). Furthermore, if P ∈ F q [x] µ×(2µ) is the submatrix of P consisting of these rows, then for k = 0, . . . , µ -1 the row k of P is ψ(Y k ), where

Consequently, if P = [P 1 P 2 ], where P 1 and P 2 are in F q [x] µ×µ , then ay

, where (p k,0 , . . . , p k,µ-1 ) is the row k of -P 1 .

Proof. We start with some observations on the matrix whose rows are ψ(Y k ) for k = 0, . . . , µ -1. This is a µ × (2µ) matrix over F q [x], whose rank is µ since Y 0 , . . . , Y µ-1 are F q [x]-linearly independent. By construction, its µ×µ rightmost submatrix is the identity matrix. Writing

k , where

, and this d-degree is reached at index µ + k. This shows that µ + k is the d-pivot index of the row ψ(Y k ). This property combined with the special shape (with an identity submatrix) of the matrix formed by the ψ(Y k )'s ensure that this matrix is in d-Popov form.

Furthermore, since for k = 0, . . . , µ -

where the strict inequality is due to Lemma 2.3, then at least µ rows of P have d-degree less than

It then follows from Lemma 4.3 that

which means that at most µ rows of P can have d-degree less than 1 µ (deg(E)deg(A)), because (z -a)Я(B) has rank µ as an F q [x]-module.

Thus, exactly µ rows of P have d-degree less than 1 µ (deg(E) -deg(A)), which proves the first claim of the lemma. For the second claim, the above observations show that the matrix formed by the ψ(Y k )'s is a left multiple U P by a nonsingular µ × µ matrix U . Yet, since both P and the matrix whose rows are the ψ(Y k )'s are in d-Popov form, and since the rightmost µ × µ submatrix of the latter is the identity matrix, the only possibility is U = I µ , proving the second claim. The last claim is obvious.

Proof. Correctness is given by Lemma 4.7. For complexity, simply note that the computational bottleneck lies in Step 8, in which case δ A (a) ≥ -deg(A) because a is nonzero and a ∈ L(δ A (a)P ∞ + A). By assumption, we have that

Algorithm 1 BasisProducts(A, B, E, a, x, y (A+B) , y (B) ) Input:

, where E 1 , . . . , E N are pairwise distinct rational places such that supp(E) ∩ (supp(A) ∪ supp(B) ∪ {P ∞ }) = ∅ • evaluations a = (a j ) j=1,...,N , where a j = a(E j ) for a function a ∈ Я(A) with known δ A (a) and such that deg(E) ≥ deg(A) + δ A (a) + 2g + µ, • evaluations x = (x j ) j=1,...,N , where x j = x(E j ) ∈ F q ,

• evaluations y (A+B) = (y (A+B) i,j ) i=0,...,µ-1 j=1,...,N , where y

• evaluations y (B) = (y (B) i,j ) i=0,...,µ-1 j=1,...,N , where y for all k ∈ {0, . . . , µ -1}. 1: if a = 0 then return matrix 0 ∈ F q [x] µ×µ 2: U 0 , . . . , U µ-1 ← an x-partition of E 3: S = [S i,k ] ∈ F q [x] µ×µ ← matrix with S i,k (x j ) = y (A+B) i,j for E j ∈ U k 4: T = [T i,k ] ∈ F q [x] µ×µ ← matrix with T i,k (x j ) = a j y (B) i,j for E j ∈ U k 5: u = [u 0 , . . . , u µ-1 ] ∈ F q [x] µ ← vector with u k = Ej ∈U k (x -x j )


Laurent Cosnefroy

From Disorganized Study Methods to Disorganisation: New Perspectives on a Neglected Study Strategy 1

Introduction

Dropout and failure in higher education are key issues in many countries. In Europe, for instance, too many students fail to finish diploma or degree courses (European Commission 2015). This is why it is paramount to gain a better understanding of the factors that have an impact on persistence and academic achievement. There has been a great deal of research on success and failure in higher education over the years. Numerous variables may be associated with achievement in higher education. In their systematic review, Schneider and Preckel (2017) identified 105 such variables, which they broke down into two categories, depending on whether they concerned the learning environment or students' characteristics.

The latter category included cognitive and metacognitive strategies, namely strategies used to process information or to steer learning activities. Results showed that effort regulation and time or study management had a large-or medium-sized positive effect on students' success.

. However, research on disorganisation has been largely overlooked up to

now. The twofold aim of the present study was thus to undertake an overview of research on disorganisation, and explore new avenues for such research.

Referring to Entwistle's work on approaches to study [START_REF] Entwistle | Motivational factors in students' approaches to learning[END_REF]), [START_REF] Elliot | Achievement goals, study strategies, and exam performance: A mediational analysis[END_REF] defined disorganisation as "learners' difficulty in establishing or maintaining a structured, organized approach to study" (p. 549). Instead of disorganisation, Entwistle had used the term disorganized study methods, the title of a four-item subscale of the Approaches to Study Inventory (ASI; [START_REF] Entwistle | Dropout and completion in higher education in Europe[END_REF]. This subscale stresses the lack of time management, mainly addressing dilatory processes such as postponing academic work. Scores on this subscale are negatively correlated with academic performance [START_REF] Entwistle | Motivation and approaches to learning: Motivation and conceptions of teaching[END_REF][START_REF] Entwistle | Dropout and completion in higher education in Europe[END_REF]. [START_REF] Elliot | Achievement goals, study strategies, and exam performance: A mediational analysis[END_REF] devised a five-item disorganisation scale with a broader scope than Entwistle's scale. Lack of time management is only one of the components of the construct, the other two being uncertainty about goals (the what of study) and which study skills to use (the how of study). Elliot, McGregor, and Gable's disorganisation scale is actually closer to Vermunt (1998)'s lack of regulation scale than to Entwistle's disorganized study methods scale. Vermunt's scale also emphasizes the difficulty of clearly defining study goals and knowing how to study the learning material. As a consequence, disorganisation and lack of regulation are two constructs that largely overlap. [START_REF] Elliot | Achievement goals, study strategies, and exam performance: A mediational analysis[END_REF] conducted two studies showing that disorganisation mediates the relationship between performance-avoidance goals and exam performance. Performanceavoidance goals are positive predictors of disorganisation, which has a significant negative impact on exam performance. Performance-avoidance goals may trigger threat and apprehension, thereby undermining an organized study method. In turn, disorganisation "is likely to cause students to be ill prepared come evaluation time, thus leading to anxiety and worry during the examination process" (Elliot et al. 1999, p. 560).

State of research on disorganisation

Despite these challenging results, disorganisation has received little attention to date, such that only a handful of studies have focused on it. These studies referred to different theoretical frameworks, mostly achievement goals, but also self-determination theory [START_REF] Boiché | Motivational profiles and achievement: A prospective study testing potential mediators[END_REF][START_REF] Cheon | Expanding autonomy psychological need states from two (satisfaction, frustration) to three (dissatisfaction): A classroom-based intervention study[END_REF][START_REF] Jang | Why students become more engaged or more disengaged during the semester: A self-determination dual-process model[END_REF]. Achievement goals refer to the pursuit of competence in achievement contexts. Performance goals are focused on the demonstration of competence relative to others, while mastery goals highlight the development of competence and task mastery. Moreover, an achievement goal may be focused on either attaining a desirable possibility (approach goal) or avoiding an undesirable possibility (avoidance goal) (Elliot and Trash 2001). Regarding the antecedents of disorganisation, most studies have looked at how achievement goals affect disorganisation.

When disorganisation was regressed over achievement goals, performance-avoidance goals emerged as significant positive predictors of disorganisation (Al-Emadi 2000;[START_REF] Corker | Setting lower limits high: The role of boundary goals in achievement motivation[END_REF][START_REF] Cosnefroy | On the relationship between the forethought phase of self-regulated learning and self-regulation failure[END_REF][START_REF] Elliot | A 2x2 achievement goal framework[END_REF][START_REF] Senko | Pursuing their own learning agenda: how mastery-oriented students jeopardize their class performance[END_REF]. Mastery-avoidance goals were also found to be significant positive predictors in all the studies that included this goal [START_REF] Corker | Setting lower limits high: The role of boundary goals in achievement motivation[END_REF][START_REF] Cosnefroy | On the relationship between the forethought phase of self-regulated learning and self-regulation failure[END_REF][START_REF] Darnon | Buts d'accomplissement, stratégies d'étude, et motivation intrinsèque : présentation d'un domaine de recherche et validation de l'échelle d'Elliot et McGregor[END_REF][START_REF] Elliot | A 2x2 achievement goal framework[END_REF]. All results consistently showed that avoidance goals (either performance or mastery, when included in the study) are positive predictors of disorganisation.

Most studies investigating the relationship between disorganisation and performance have shown that disorganisation has a negative impact on academic performance or is negatively correlated with performance [START_REF] Bandalos | A model of statistics performance based on achievement goals theory[END_REF][START_REF] Corker | Setting lower limits high: The role of boundary goals in achievement motivation[END_REF][START_REF] Cosnefroy | On the relationship between the forethought phase of self-regulated learning and self-regulation failure[END_REF][START_REF] Elliot | Achievement goals, study strategies, and exam performance: A mediational analysis[END_REF][START_REF] Grant | Clarifying achievement goals and their impact[END_REF][START_REF] Harackiewicz | Short-term and longterm consequences of achievement goals: Predicting interest and performances over time[END_REF][START_REF] Senko | Pursuing their own learning agenda: how mastery-oriented students jeopardize their class performance[END_REF], although neither Berger and Freud (2012) nor [START_REF] Phan | Reflective thinking, effort persistence, disorganisation and academic performance: A mediational approach[END_REF] observed a significant effect on performance. It should be noted that control of potential confounding variables differed quite considerably across studies. No control variables were used in the studies by [START_REF] Cosnefroy | On the relationship between the forethought phase of self-regulated learning and self-regulation failure[END_REF], [START_REF] Grant | Clarifying achievement goals and their impact[END_REF], and [START_REF] Senko | Pursuing their own learning agenda: how mastery-oriented students jeopardize their class performance[END_REF]. [START_REF] Harackiewicz | Short-term and longterm consequences of achievement goals: Predicting interest and performances over time[END_REF] controlled for sex, while Berger and Freud (2012), Corker and Donellan (2012) and [START_REF] Elliot | Achievement goals, study strategies, and exam performance: A mediational analysis[END_REF] controlled for both sex and prior achievement.

Finally, three studies were grounded in self-determination theory. They viewed disorganisation as an indicator of students' cognitive disengagement. First, Boiché and Stephan (2014) investigated how cognitive strategies are a mediator between motivational profiles and achievement. The level of disorganisation varied significantly between the five motivational profiles these authors identified. Mean disorganisation scores were higher for the non-self-determined profile, in which external motivation and amotivation are salient. This profile also leads to weaker academic achievement. Time spent studying tends to decrease when mean disorganisation scores increase. Second, recent developments in selfdetermination theory have highlighted the distinction between need dissatisfaction (lack of need satisfaction) and need frustration (or need thwarting), that is "perceptions that psychological needs are actively undermined by others" (Costa, Ntoumanis, and Bartholomew 2015, p. 12). Two studies showed that autonomy need dissatisfaction and autonomy need frustration positively predict disengagement, whereas autonomy satisfaction negatively predict it. Autonomy dissatisfaction is fueled by the indifference of the teacher, who pays no attention to students' needs, whereas autonomy frustration is fueled by the control of the teacher, who tries to gain control over students' behavior through pressure-inducing tactics [START_REF] Cheon | Expanding autonomy psychological need states from two (satisfaction, frustration) to three (dissatisfaction): A classroom-based intervention study[END_REF][START_REF] Jang | Why students become more engaged or more disengaged during the semester: A self-determination dual-process model[END_REF]. Unlike studies within the achievement goal framework, these two highlight the potential impact of teacher's behavior on disorganisation.

In conclusion, research on disorganisation has tended to corroborate the seminal work by [START_REF] Elliot | Achievement goals, study strategies, and exam performance: A mediational analysis[END_REF] on the antecedents and consequences of disorganisation. All studies have confirmed that avoidance goals are positive predictors of disorganisation, and most of them that disorganisation is a negative predictor of academic performance. However, other variables besides achievement goals may also be significant predictors of disorganisation, such as teacher support. Furthermore, the very few studies controlling for both sex and prior achievement to assess the impact of disorganisation on academic performance have yielded mixed results: no impact for Berger and Freud (2012), and a negative impact for Corker and Donellan (2012) and [START_REF] Elliot | Achievement goals, study strategies, and exam performance: A mediational analysis[END_REF]. Thus, further investigations are needed to gain a better understanding of the predictors of disorganisation and to confirm the impact of disorganisation on academic performance. Lastly, some studies have suggested that disorganisation is closely linked to student disengagement [START_REF] Boiché | Motivational profiles and achievement: A prospective study testing potential mediators[END_REF][START_REF] Cheon | Expanding autonomy psychological need states from two (satisfaction, frustration) to three (dissatisfaction): A classroom-based intervention study[END_REF][START_REF] Jang | Why students become more engaged or more disengaged during the semester: A self-determination dual-process model[END_REF]. Student engagement refers to a student's active involvement in a learning activity [START_REF] Reschly | Jingle, jangle, and conceptual haziness: evolutions and future directions of the engagement construct[END_REF]. It is viewed as a multidimensional construct, often with four components: behavioral engagement pertains to effort and persistence; emotional engagement relates to being interested in learning activities, as well as having a sense of belonging to a university; cognitive engagement refers to allocation of varying amounts and types of cognitive resources; and agentic engagement pertains to proactive behavior during instruction [START_REF] Sinatra | The challenges of defining and measuring student engagement in science[END_REF].

Disorganisation can be viewed as student disengagement, when linked to low study time.

Although disorganisation was negatively associated with time spent studying in prior studies [START_REF] Boiché | Motivational profiles and achievement: A prospective study testing potential mediators[END_REF], it may also be associated with high study time. Uncertainty about study goals and study methods, which is the main feature of disorganisation, is likely to increase when learners are facing new learning tasks, as they can no longer rely on routine forms of studying. First-year undergraduate students must handle the transition from secondary to higher education. Compared with secondary students, higher education students are expected to learn more independently. They are confronted with new teaching and studying methods, as well as new content, trying to perform new academic tasks with familiar, tried-and-trusted learning strategies [START_REF] Kyndt | The development of students' motivation in the transition from secondary to higher education: A longitudinal study[END_REF][START_REF] Vermunt | A learning patterns perspective on student learning in higher education: State of the art and moving forward[END_REF].

Sometimes teaching strategies and learning strategies are not compatible. Some students experience what [START_REF] Vermunt | Congruence and friction between learning and teaching[END_REF] call destructive frictions when the contrast between the teacher-dependent way of learning they experienced in secondary school and the highly self-regulated form of learning that is expected at university is too great. We can assume that such changes potentially trigger disorganized study methods, even though students are eager to learn and make an effort. In such cases, disorganisation corresponds not to disengagement, but to engagement, insofar as students are trying hard to study the academic material.

The Present Study

The purpose of the present study was threefold. First, we investigated the relationship between disorganisation and academic success, controlling for sex and prior academic achievement, in order to gain a more accurate assessment of the impact of disorganisation on academic achievement.

Second, we expanded the study of potential determinants of disorganisation by encompassing context-related variables and students' prior achievement-related variables. 2019)'s and Jang, Kim, and Reeve (2016)'s results suggested that teachers' behavior helps students to handle disorganisation. Likewise, learners are liable to experience lack of regulationwhich is similar to disorganisation -when the external regulation provided by teachers and peers is not sufficient [START_REF] Ferla | Student models of learning and their impact on study strategies[END_REF][START_REF] Vermunt | Patterns in student learning: Relationships between learning strategies, conceptions of learning, and learning orientations[END_REF]). Thus, one can assume that falling back on external help is paramount to reduce uncertainty about the what and how of study, which characterizes disorganisation and lack of regulation. This external help may come from two sources: teachers and peers. As they convey teachers' concern for students' needs, supportive teaching practices, such as a student-centered teaching, may help students reduce their disorganisation. Regarding peers, social integration should also help students to find resources to cope with disorganisation, insofar as "a student's sense of loneliness is likely to isolate the student from peers who might be able to offer assistance on academic tasks" (Credé and Niehorster 2012, p. 140). With respect to students' prior achievement, we can assume that two distinct mechanisms may impact disorganisation: work habits (distal impact), and lack of knowledge acquired during the academic year (proximal impact). Rather than laying emphasis on time spent studying, [START_REF] Corno | Work habits and work styles: volition in education[END_REF] chose to define good work habits as "strategies and tactics for completing academic tasks that become honed through experience" (p. 1671). Having developed good work habits, high achievers in high school may be better able than low achievers to handle the new academic tasks they have to undertake at university, without becoming anxious and experiencing disorganisation. With regard to lack of knowledge, [START_REF] Entwistle | Motivational factors in students' approaches to learning[END_REF] pointed out that disorganized study methods are correlated with comprehension difficulties. Similarly, [START_REF] Phan | Reflective thinking, effort persistence, disorganisation and academic performance: A mediational approach[END_REF] claimed that a lack of relevant knowledge may manifest itself in the form of disorganisation. Comprehension difficulties and lack of relevant knowledge make it harder to thoroughly identify what is crucial to study. Thus, poor results over the current academic year (e.g., over the first semester) may foster the development of disorganisation later on (e.g., over the second semester).

Cheon et al. (

Third, we hypothesized that disorganisation may be consistent with either student engagement or student disengagement. Learners' disorganisation scores may mean different things, depending on their links to other learning dimensions, especially time spent studying.

Thus, it would be worthwhile showing that students with a high level of disorganisation may be characterized by either high or low study time. In line with this goal, we adopted a person-centered approach, with disorganisation and time spent studying as cluster variables. In a second step, we assessed whether this clustering was predictive of student engagement, using two target variables: procrastination and mastery approach goals. Procrastination is defined as delaying the initiation or completion of a goal to the point of discomfort [START_REF] Howell | Procrastination: Associations with achievement goal orientations and learning strategies[END_REF]. As such, it is a form of cognitive and behavioral disengagement. Masteryapproach goals are focused on the development of competence through task mastery. They may help students develop an interest-based engagement in learning activities [START_REF] Sommet | Achievement goals, reasons for goal pursuit, and achievement goal complexes as predictors of beneficial outcomes: Is the influence of goals reducible to reasons[END_REF]).

Method

Participants and Procedure

Participants were 177 (155 men, 22 women; M age = 18.94 years, SD = 1.46) students in their first year of a 2-year STEM course at a French university institute of technology. The study was conducted in April 2016. Data collection was carried out during regular courses by the author of the article. Students were informed of the purpose of the study and completed a consent form before answering the questionnaire. Overall scores for the first (S1) and second (S2) semesters were obtained from the course instructors at the end of the academic year.

Instruments

Students completed a self-report questionnaire that measured different facets of their motivation and study strategies, as well as their perception of the learning environment and their integration into student life. They responded on a 7-point scale ranging from 1 (Strongly disagree) to 7 (Strongly agree) with intermediate anchor points, having descriptive labels as well for all the scales included into the questionnaire except for the time spent studying scale.

Achievement goals.

We used [START_REF] Elliot | A 2x2 achievement goal framework[END_REF]'s French validation of the 12-item Achievement Goal Questionnaire [START_REF] Darnon | Buts d'accomplissement, stratégies d'étude, et motivation intrinsèque : présentation d'un domaine de recherche et validation de l'échelle d'Elliot et McGregor[END_REF] to assess achievement goals. Each type of achievement goal (i.e., performance-approach goal, mastery-approach goal, performanceavoidance goal, and mastery-avoidance goal) was measured with three items. We did not include the mastery-avoidance goal construct, as items assessing this goal are not always frequently endorsed or well understood by respondents [START_REF] Linnenbrink-Garcia | Multiple pathways to success: An examination of integrative motivational profiles among upper-elementary and college students[END_REF].

Social integration.

Social integration was assessed using a short version of [START_REF] Neuville | Persévérer et réussir à l'université[END_REF]'s 10item scale. Drawing on the French adaptation [START_REF] Larose | Exploration des qualités psychométriques de la version française du Student Adaptation to College Questionnaire[END_REF] of the Student Adaptation to College Questionnaire [START_REF] Baker | Measuring adjustment to college[END_REF], this scale explores both the quality of relationships between peers and engagement in extracurricular activities. Given the research question, we were more interested in the peers' social support dimension. Thus, we only kept the five items focusing on the quality of relationships between peers. These items reflect judgments about existing friends or the social skills needed to make new friends (e.g., "I have good friends with whom I can talk about any problem I might have" or the reverse item "I have a sense of loneliness in this institute").

Teachers' concern for students' development.

A short 6-item version of the French validation [START_REF] Neuville | Persévérer et réussir à l'université[END_REF]) of Mannan (2001)'s scale was used to assess students' perception of teachers' concern for students' needs, that is, their ability to adopt student-centered teaching. Items included "Teachers take our suggestions into account", and "Teachers strive to really understand the learning difficulty students have to cope with". Disorganisation. [START_REF] Elliot | Achievement goals, study strategies, and exam performance: A mediational analysis[END_REF]'s five-item disorganisation scale was adapted to the French language and validated by [START_REF] Darnon | Buts d'accomplissement, stratégies d'étude, et motivation intrinsèque : présentation d'un domaine de recherche et validation de l'échelle d'Elliot et McGregor[END_REF]. We used a slightly different form containing only four items, as preliminary studies (Author et al., 2018) had shown that one of the initial scale's items had insufficient psychometric qualities.

Procrastination.

Author et al. ( 2018)'s French six-item procrastination scale was used to assess procrastination. Three items explored difficulty initiating an action (e.g., "It takes a lot of effort for me to start working"), whereas the other three focused on difficulty pursuing an action until its completion (e.g., "If I take a break when I'm studying, I have a lot of trouble getting back to work").

Time spent studying.

Participants were asked to report the number of hours they spent studying each weekday and across the weekend on a 4-point Likert scale (1 = None, 2 = < 1 hr, 3 = 1-2 hr, 4 = > 2 hr per day for weekdays, and 1 = none, 2 = < 2 hr, 3 = 2-4 hr, 4 = > 4 hr for the weekend). Both measures were then averaged to obtain an index of time spent studying.

High-school achievement.

Students self-reported the grade they received for the French baccalaureate: pass (n = 51), quite good (n = 77), good (n = 38), or very good (n = 11).

Higher education achievement.

Grades in France's higher education system range between 0 and 20, and students need a mean grade equal to or above 10 to obtain a credit for the semester. The overall mean for the semester was used as an indicator of achievement in both S1 and S2. To calculate this overall mean, we averaged the grades awarded in continuous assessments and final exams, weighted with coefficients according to their relative importance in the program.

Results

Data were analyzed using SPSS Version 21.

Missing Data

As the percentage of missing data for this study was below 5% (1.33% of data points), we used the expectation maximization algorithm to handle missing data, as it is regarded as an appropriate missing data method [START_REF] Graham | Multiple imputation in multivariate research[END_REF].

Reliability and Validity of Self-Report Measures

All the scales we used had previously been validated in the above-mentioned studies. However, we chose to use abridged versions of three of them, namely disorganisation, teachers' concern, and social integration. To ensure the validity of these abridged versions, we ran a confirmatory factor analysis with Amos 21. The disorganisation items, teachers' concern items and social integration items all loaded onto their hypothesized factors. The standardized loadings were above .57 for social integration, above .67 for teachers' concern, and above .68 for disorganisation. This three-factor model fitted the data well: χ 2 /df = 1.54, CFI = .955, RMSEA = .055, 90% CI [.036, .073], RMR = .10.

Descriptive Statistics

We first examined the descriptive statistics, reliability (cf. Table 1) and intercorrelations of the variables used in the study. Note. MAP = mastery-approach goals; PAP = performance-approach goals; PAV = performance-avoidance goals.

Table 2 sets out the zero-order correlations for all of the observed variables. Consistent with predictions, the correlation matrix revealed that disorganisation was associated with poorer academic performance, for both S1 (r = -.24, p < .01) and S2 (r = -.29, p < .01).

Consistent with prior research, performance-avoidance goals were positively associated with disorganisation (r = .23, p < .01). Disorganisation was associated with less time spent studying, but the correlation was weak, albeit significant (r = -.18, p < .05). Note. MAP = mastery-approach goals; PAP = performance-approach goals; PAV = performance-avoidance goals.

Preliminary Analyses

We first performed t tests to assess the differences in mean disorganisation scores and S2 overall performance according to sex. Differences on S2 academic performance between male and female students were not significant (M = 11.57 vs. M = 11.87; t = -.60, ddf = 175, ns). Likewise, no differences between male and female students were observed regarding disorganisation (M = 3.67 vs. M = 3.16; t = 1.56, ddf = 175, ns). Given these results, sex was not included in subsequent regression analyses.

Hierarchical Regression Predicting S2 Academic Performance

A three-step hierarchical regression was used to predict S2 performance. In the first step, final performance at high school was entered as a predictor. In the second step, S1 academic performance was entered as a predictor. In the third step, disorganisation and time spent studying were added as predictors. Results are set out in Table 3. First, high-school performance predicted a significant amount of variance in S2 academic performance, F( 1

Hierarchical Regression Predicting Disorganisation

We ran a four-step hierarchical regression to predict disorganisation. In the first step, high-school achievement was entered as predictor of disorganisation, followed in the second step by S2 academic performance. In the third step, mastery-approach goals, performanceapproach goals, and performance-avoidance goals were included in the analysis. In the fourth step, social integration and teachers' concern were added as predictors. The results of the equations predicting disorganisation are set out in Table 4. Performance-avoidance goals were positive predictors of disorganisation (β = .24, p < .01). With regard to students' prior achievement-related variables, high-school performance was not a significant predictor of disorganisation, whereas S1 overall mean was (β = -.17, p < .05). Likewise, results were mixed for context-related variables. Teachers' concern was not a significant predictor of disorganisation, whereas social integration was (β = -.18, p < .05) * p < .05. ** p < .01.

Cluster Analysis

The SPSS TwoStep clustering method was performed with disorganisation and time spent studying as cluster variables. The TwoStep procedure automatically determines the appropriate number of clusters after z-standardizing the cluster variables. The cluster analysis yielded a mean silhouette measure of cluster cohesion and separation of 0.50, suggesting fair to good overall result quality (index range from -1 to +1). The first cluster (n = 48, 27.1% of the sample), was characterized by a high mean score (4.60) on disorganisation and the second highest mean score on time spent studying (2.84). The second cluster (n = 51, 28.8%) was characterized by the lowest mean score on disorganisation (2.26) and the highest mean score on time spent studying (2.87). The third cluster (n = 41, 23.2%) was characterized by the second lowest mean score on disorganisation (2.73) and the lowest mean score on time spent studying (1.87). The fourth cluster (n = 37, 20.9%), was characterized by the highest mean score on disorganisation (5.14) and the second lowest mean score on time spent studying (1.88). Clusters 1 and 4 showed that the highest scores on disorganisation could be associated with either weak study time (Cluster 4) or high study time (Cluster 1).

Clusters were then compared on mastery-approach goals and procrastination. A multivariate analysis of variance (MANOVA) with cluster membership as the independent variable showed a significant effect of cluster membership, with Wilks' λ = .50, F(6, 344) = 23.79, p < .01, η 2 = .29. Follow-up ANOVAs revealed significant effects of cluster membership on procrastination, F(3, 173) = 52.54, p < .001, η 2 = .48, and mastery-approach goals, F(3, 173) = 5.68, p < .01, η 2 = .09. A Tukey post hoc test revealed that Clusters 1 and 4 differed significantly from one another on both variables. Cluster 1 had a lower score on procrastination than Cluster 4 (M = 4.68 vs. M = 5.62, p < .01), while Cluster 1 had a higher score on mastery-approach goals than Cluster 1 (M = 5.16 vs. M = 4.33, p < .05).

To verify the stability of the extracted cluster solution, we ran a four-class cluster analysis, using a K-means clustering method. Square Euclidean distance was used as a measure of proximity between two observations. Results also revealed two contrasting groups regarding high scores on disorganisation. MANOVA with cluster membership as the independent variable revealed a significant effect of cluster membership on procrastination and mastery-approach goals, with Wilks' λ = .58, F(6, 344) = 18.22, p < .01, η 2 = .24. Follow-up ANOVAs revealed a significant effect of cluster membership on both procrastination, F(3, 173) = 40.63, p < .001, η 2 = .41, and mastery-approach goals, F(3, 173) = 2.67, p < .05, η 2 = .04. A Tukey post hoc test showed that Clusters 1 and 4 differed significantly on procrastination. Cluster 1 had a lower mean procrastination score than Cluster 4 (M = 4.70 vs. M = 5.75; p < .01), but they did not differ significantly on mastery-approach goals (M = 4.96 vs. M = 4.46).

Discussion

The first goal of the present study was to provide stronger evidence of the impact of disorganisation on academic performance, by simultaneously controlling for two variables, namely sex and prior achievement. After verifying in a preliminary analysis that sex had no effect, the hierarchical regression analysis showed that adding disorganisation at the last step while controlling for mean S1 scores significantly increased the percentage of explained variance, albeit only slightly. Thus, disorganisation makes a unique contribution to academic achievement beyond prior achievement. The effect of disorganisation may have been underestimated, as it may already have impacted mean S1 scores. For some students, disorganized study methods were probably present from the start of the academic year, rather than emerging during the second semester, leading to damaging consequences for overall performance in the first semester.

The second goal of the study was to gain a better understanding of the determinants of disorganisation, by adding two categories of variables that had never previously been taken into account (i.e., prior achievement and social support) to achievement goals. Each of these categories was broken down into two subcategories: proximal prior achievement (i.e., S1 mean scores) and distal prior achievement (i.e., high-school achievement), and teacher's concern for student needs and student's social integration. With regard to prior achievement, results showed that S1 mean scores were a significant negative predictor of disorganisation.

This finding is in line with prior research indicating that disorganized methods or disorganisation are fueled by misunderstanding and lack of knowledge [START_REF] Entwistle | Motivational factors in students' approaches to learning[END_REF][START_REF] Phan | Reflective thinking, effort persistence, disorganisation and academic performance: A mediational approach[END_REF]. By contrast, we did not find that high-school achievement was a significant negative predictor of disorganisation. Although high achievers may have been able to develop powerful study habits at high school, they may not have allocated enough time to studying because they had a high belief in their ability, as suggested by [START_REF] Vancouver | When self-efficacy negatively relates to motivation and performance in a learning context[END_REF].

Hence, good study habits may be counterbalanced by insufficient time spent studying. As for social support variables, results showed that teachers' concern had no effect on disorganisation, whereas social integration had a significant effect. The scale items probing teachers' concern mainly depict teachers who are open to discussion, striving for a better understanding of their students' needs and difficulties. Teachers who are receptive to their students' thoughts and feelings adopt an autonomy-supportive style [START_REF] Reeve | Why teachers adopt a controlling motivating style towards students and how they can become more autonomy supportive[END_REF]. However, providing autonomy support is probably not enough to help students self-regulate. They also need structure. In other words, they require teachers to communicate clear expectations and frame their learning activity with explicit direction and guidance [START_REF] Jang | Engaging students in learning activities: It is not autonomy support or structure, but autonomy support and structure[END_REF]. Teacher-provided structure increases students' perceived competence and perceived control over outcomes, which is paramount to combat disorganisation. The absence of an effect of the teacher's concern variable on disorganisation is probably due to the fact that this variable was measured with a scale that mainly focused on the autonomy-supportive dimension of the teacher's activity, rather than on the structure dimension. Overall, the present findings make a substantial contribution to our knowledge of the determinants of disorganisation. They pave the way for a multidimensional approach to the determinants of disorganisation that involves not only motivational factors (performance-avoidance goals), but also cognitive (lack of knowledge) and social (lack of social support) factors.

The third goal of the study was to ascertain whether disorganisation can be associated with student engagement. Both clustering methods highlighted two disorganisation groups, which differed according to the amount of time spent studying. Results clearly showed that disorganisation can be associated with time spent studying. Most important, these two contrasting groups differed on their impact on engagement-related variables. The disorganisation with high study time cluster had significantly weaker procrastination scores and higher mastery-approach goals (but only for the TwoStep clustering method) than the disorganisation with low study time cluster. These findings support the view that disorganisation and engagement are not mutually exclusive. Disorganisation is liable to increase during the first year in higher education because of changes in what is expected of students. The transition experience involves the loss of a secure learner identity (Christie, Tett, Cree, Hounsell, and McCune 2016). Thus, disorganisation does not necessarily mean that students are disengaged. Rather, it means that they try to learn the new rules and move toward a new learner identity. However, our results did not completely support our assumption, for although each of these two groups had a mean disorganisation score above the overall one, this score was lower when it was associated with high time spent studying than when it was associated with low time spent studying. This pattern may indicate that above a certain threshold, disorganisation becomes so highly developed that it triggers discouragement which, in turn, undermines behavioral and motivational engagement.

Limitations and Implications for Research and Practice

The present study had two limitations. First, the sample was relatively small and the students were all studying the same academic subject. It would therefore be useful to extend the study of the antecedents and consequences of disorganisation to a wider range of academic subjects. A second limitation was the unequal sex ratio, which prevented us from accurately measuring the impact of sex on disorganisation, even though previous research has failed to find an effect of sex. Future research should replicate the results reported here with larger samples that are more representative of students entering higher education.

Despite the aforementioned limitations, the present study makes two important contributions to the literature. First, it shows that disorganisation is a multidimensional process combining motivational, cognitive and social dimensions. Second, it provides evidence that disorganisation may sometimes be associated with student engagement, especially when students experience a transition. Hence, equating disorganisation with disengagement is too restrictive a view. These findings have both theoretical and practical implications. First, a transition can be defined as any major shift in students' role requirements or study context that involves changes and having to cope with these changes [START_REF] Coertjens | Students' transition into higher education from an international perspective[END_REF]. For example, when international students attend foreign universities, they undergo a transition. They have to learn the rules of a new game that are not made explicit [START_REF] Carroll | Support and guidance for learning from an international perspective[END_REF][START_REF] Heng | Voices of international students in USA colleges. "I want to tell them that …[END_REF]).

Accordingly, we can assume that international students are likely to experience disorganisation while trying to adapt to their new learning environment. Additional research is needed to evaluate this hypothesis. When considering implications for practice, supporting students' social integration would help to preclude, or at least curtail, disorganisation. As the classroom is an interface between the social and the academic [START_REF] Tinto | Classroom as communities: Exploring the educational character of student persistence[END_REF], social integration could be promoted in the classroom through group learning activities. However, it is crucial to ensure that the configuration of the groups often changes, in order to support social interactions with as many peers as possible. Finally, the results indicate that, in terms of helping students who are experiencing disorganisation, any support that teachers might offer to encourage students' autonomy is insufficient. A teaching style that combines the promotion of autonomous learning with more direct instruction (above all, giving clear instructions when introducing new tasks) would probably more helpful for such students.

  , 164) = 6.85 p < .01. Results from Step 2 indicated that adding S1 academic performance increased the amount of variance explained by 61%, F(1, 163) = 253.5, p < .01. High-school performance ceased to be a significant predictor. Adding disorganisation increased the amount of variance explained by 1%, F(2, 161) = 3,33, p < .01. Even when we controlled for students' prior achievement, disorganisation was a negative significant predictor of students' S2 academic achievement (β = -.10, p < 05).

Table 1

 1 Means, Standard Deviations, Skewness and Reliability for Study Variables

	Variables	Range	M	SD	Skewness α
	Disorganisation	1.00-6.50 3.60 1.44 -.16	.85
	Teachers' concern	1.83-6.83 5.12 0.90 -.91	.86
	Social integration	1.60-7.00 5.77 0.91 -.91	.79
	MAP	1.00-7.00 4.86 1.28 -.61	.82
	PAP	1.00-7.00 3.63 1.76 .17	.92
	PAV	1.00-7.00 4.32 1.42 -.39	.61
	Procrastination	1.00-7.00 4,34 1,41 -.23	.82
	Time spent studying 1.00-4.00 2,42 .59 .15	.60

Table 2

 2 Zero-Order Correlations Among Variables

	Variables	1	2	3	4	5	6	7	8	9	10
	1. Disorganisation 1
	2. Teachers'	-.04	1
	concern
	3. Social	-.17*	.25**	1
	integration
	4. MAP	-.16*	.42**	.14* 1
	5. PAP	-.09	.10	-.04	.40**	1
	6. PAV	.23**	-.09	.03	-.05	.22**	1
	7. Time spent	-.18*	.17*	-.10	.40**	.27**	.26**	1
	8. Procrastination .68**	-.14	-.12	-.28** -.05	.15*	-.47** 1
	9. S2 overall	-.29** .22**	.20*	.24**	.31**	-.18*	-.01	-.22** 1
	mean			*
	10. S1 overall	-.24** .14	.14	.14	.24**	-.16*	-.04	-.18*	.81**	1
	mean

Table 3

 3 Summary of Hierarchical Regression Analysis Predicting S2 Academic Performance

	Variable	B	SE B β	R 2	Δ R 2
	Step 1				.05**
	High-school achievement .52 .17	.23**
	Step 2				.66	.61**
	High-school achievement .18 .10	.08
	S1 academic performance .97 .06	.80**
	Step 3				.67	.01*
	High-school performance .18 .10	.08
	S1 academic performance .94 .06	.77**
	Disorganisation	-.15 .07	-.10

* Note. * p < .05. ** p < .01.

Table 4

 4 Summary of Hierarchical Regression Analysis Predicting Disorganisation

	Variable	B	SE B	β	R 2	Δ R 2
	Step 1				.00	ns
	High-school achievement	-.08	.11	-.05
	Step 2				.06	.06**
	High-school achievement	-.01	.11	-.01
	S1 academic performance	-.19	.06	-.24**
	Step 3				.11	.05*
	High-school performance	.04	.11	.03
	S1 academic performance	-.15	.06	-.18*
	MAP	-.11	.09	-.10
	PAP	-.04	.07	-.05
	PAV	.22	.08	.22**
	Step 4				.14	.03*
	High-school performance	.09	.12	.06
	S1 academic performance	-.14	.06	-.17*
	MAP	-.13	.10	-.11
	PAP	-.06	.07	-.07