Julien Lavauzelle
email: julien.lavauzelle@inria.fr

Lifted Projective Reed-Solomon Codes

Lifted Reed-Solomon codes, introduced by Guo, Kopparty and Sudan in 2013, are known as one of the few families of high-rate locally correctable codes. They are built through the evaluation over the affine space of multivariate polynomials whose restriction along any affine line can be interpolated as a low degree univariate polynomial.

In this work, we give a formal definition of their analogues over projective spaces, and we study some of their parameters and features. Local correcting algorithms are first derived from the very nature of these codes, generalizing the well-known local correcting algorithms for Reed-Muller codes. We also prove that the lifting of both Reed-Solomon and projective Reed-Solomon codes are deeply linked through shortening and puncturing operations. It leads to recursive formulae on their dimension and their monomial bases. We finally emphasize the practicality of lifted projective Reed-Solomon codes by computing their information sets and by providing an implementation of the codes and their local correcting algorithms.

Introduction

Motivation and previous works. Locally decodable codes (LDC) and locally correctable codes (LCC) are codes equipped with a probabilistic algorithm which can efficiently decode or correct a single symbol of a noisy codeword, by querying only a few of its symbols. Low degree Reed-Muller codes define a well-known family of LDCs/LCCs with reasonable rate. Indeed, when restricted to an affine line, a sufficiently low-degree multivariate polynomial can be interpolated by a low-degree univariate polynomial. However, the rate R of such Reed-Muller codes stays stuck below 1/2. Multiplicity codes [START_REF] Kopparty | High-rate codes with sublinear-time decoding[END_REF] were the first family of codes breaking the R = 1/2 barrier for correcting a constant fraction of errors. The construction was based on a generalization of Reed-Muller codes which introduce multiplicities in the evaluation map. Shortly after the multiplicity codes breakthrough, Guo, Kopparty and Sudan [START_REF] Guo | New affine-invariant codes from lifting[END_REF] proposed another generalization of Reed-Muller codes and considered all the multivariate polynomials (i.e. not only the low-degree ones) which can be interpolated as lowdegree univariate polynomials when restricted to a line. Surprisingly, it sometimes appears that much more polynomials satisfy this property than the low-degree ones lying in Reed-Muller codes. Resulting codes are named lifted Reed-Solomon codes, and in this work, more shortly referred to as affine lifted codes.

Organisation. In this work, we show how to build analogues of these codes in projective spaces, that we call projective lifted codes. Our construction relies on the notion of degree sets which also appears in [START_REF] Guo | New affine-invariant codes from lifting[END_REF] and helps us to exhibit relations between affine and projective lifted codes. Section 2 introduce tools necessary to our construction. Affine and projective lifted codes are built in Section 3, where we also prove main properties of projective lifted codes, notably their monomiality and the structure of their degree set. In Section 4 we present a family of local correcting algorithms for projective lifted codes, whose locality depends on the number of admissible errors on the queried line. Section 5 is devoted to the links between affine and projective lifted codes, through puncturing and shortening. Finally, we show miscellaneous properties of projective lifted codes in Section 6 which emphasize their explicitness and practicality: we present explicit information sets, we bound on their minimum distance and we prove their (quasi-)cyclicity under certain conditions.

We emphasize the practicality of our construction by presenting tables of parameters of projective lifted codes in Appendix C. A basic implementation of affine and projective lifted codes in the open-source software SageMath [S + 17] is also made available1 .

Notation and preliminaries

This section is devoted to introducing the algebraic background for the definition of affine and projective lifted codes.

Geometry, polynomials and evaluation maps

We denote by F q the finite field with q elements, and by F × q its non-zero elements. For m ≥ 1, the affine space of dimension m is the set of m-tuples with coordinates in F q , and is denoted A m . We also define the projective space of dimension m as P m := (A m+1 \ {0})/ ∼ , where for a, b ∈ A m+1 \ {0}, the relation ∼ is given by a ∼ b ⇐⇒ ∃λ ∈ F × q , a = λb .

A projective point will be denoted a = (a 0 : • • • : a m ) ∈ P m . It has (q -1) different representatives, and we call standard representative the only one such that ∀j < i, a j = 0 and a i = 1. The projective space P m contains θ m,q := q m+1 -1 q-1 distinct points. The hyperplane at infinity Π ∞ := {a ∈ P m , a 0 = 0} is isomorphic to P m-1 , and the bijective map (a 1 , . . . , a m ) → (1 : a 1 : • • • : a m ) embeds A m into P m . A projective line is a (q + 1)-subset of P m of the form L a,b := {xa + yb, (x : y) ∈ P 1 } for some distinct points a, b ∈ P m . The line L a,b is the only one containing both a and b, and there are exactly θ m-1,q = |P m-1 | = q m -1 q-1 projective lines on which a given point a ∈ P m lies.

Polynomials and degrees. We denote by F q [X] := F q [X 1 , . . . , X m ] the ring of m-variate polynomials over F q . Following the terminology given in [START_REF] Guo | New affine-invariant codes from lifting[END_REF], for f = ∑ d f d X d ∈ F q [X], the set {d ∈ N m , f d = 0} is called the set of degrees of f and is denoted Deg( f ). For a subset D ⊆ N m , we denote by Poly(D) the vector space of polynomials generated by monomials X d for d ∈ D:

Poly(D) := X d , d ∈ D ⊆ F q [X] .
Some subsets D are of particular interest. For instance, for v ∈ N,

• the 1-norm ball B m 1 (v) := {d ∈ N m , ∑ m i=1 d i ≤ v} generates the space F q [X] v of multivariate polynomials of total degree bounded by v,

• the ∞-norm ball B m ∞ (v) := {d ∈ N m , d i ≤ v, ∀i = 1, . . . , m} generates the space of multivariate polynomials of partial degree bounded by v,

• the 1-norm sphere S m+1 (v) := {d ∈ N m+1 , ∑ m i=0 d i = v} generates the space F q [X] H v of homogeneous polynomials of degree v (plus the zero polynomial).

We write |d| := ∑ i d i the weight of a tuple of integers d.

Evaluation of homogeneous polynomials on a projective point. For any homogeneous polynomial f ∈ F q [X] H v , it is well-known that

f (λX) = λ v f (X) , ∀λ ∈ F × q .
It means that different representatives of a fixed projective point may result to different evaluations by f . In order to remove any ambiguity, we adopt the following definition. Let (a 0 : • • • : a m ) be the standard representation of a projective point P ∈ P m . Then we define the evaluation of f at P as: ev P ( f ) := f (a 0 , . . . , a m ) .

In other words, every projective point must be written in the unique standard representation when evaluated by homogeneous polynomials. Denote by (P 1 , . . . , P θ m,q ) (resp. (Q 1 , . . . , Q q m )) an ordered list of all the projective (resp. affine) points. Thanks to the previous definition, the following evaluation map can be defined without ambiguity for all v ≥ 0:

ev P m : F q [X] H v → F θ m,q q f → (ev P 1 ( f ), . . . , ev P θm,q ( f ))
Its affine analogue is:

ev A m : F q [X] → F q m q f → ( f (Q 1 ), . . . , f (Q q m ))
Clearly, ev P m and ev A m are F q -linear maps. Since x q = x for all x ∈ F q , we have ker(ev A m ) = X q i -X i , ∀i = 1, . . . , m . Moreover, since ev P m evaluates homogeneous polynomials, for a fixed v ∈ N ker(ev

P m ) = X q i X j -X i X q j , ∀i = j ∈ {0, . . . , m} ∩ F q [X] H v .
These properties are formally proved in [START_REF] Renterìa | Reed-Muller codes: an ideal theory approach[END_REF].

Evaluation codes

A common way to build linear codes is to evaluate polynomials over a list of points. In this subsection, we formally define the family of evaluation codes we are studying. We also recall well-known examples of such codes, namely the Reed-Solomon and Reed-Muller codes, as well as their projective analogues.

Definition 1 (affine evaluation code). Let F be a linear subspace of F q [X]. The affine evaluation code associated to F is the F q -linear code of length n = |A m | = q m composed by the evaluation vectors of polynomials in F :

ev A m (F ) = {ev A m ( f ), f ∈ F } ⊆ F q m
q .

The n-tuple (Q 1 , . . . , Q n ) of evaluation points is called the support of the code.

Definition 2 (projective evaluation code). Let F be a linear subspace of F q [X] H v . The projective evaluation code associated to F is the F q -linear code of length n = |P m | = θ m,q composed by the evaluation vectors of polynomials in F :

ev P m (F ) = {ev P m ( f ), f ∈ F } ⊆ F θ m,q q .
Once again, the n-tuple (P 1 , . . . , P n ) of evaluation points is called the support of the code.

We point out a specific class of evaluation codes which is generated by evaluation vectors of monomials.

Definition 3 (monomial code). An affine evaluation code

C = ev A m (F ) (resp. a projective evaluation code C = ev P m (F )) is said monomial if F = Poly(D) for some D ⊆ N m (resp. D ⊆ S m+1 (v)).
As we will see later, monomial codes turn out to be very convenient to describe with their set of degrees D.

Reed-Solomon and Reed-Muller codes.

Definition 4 (Reed-Solomon code). Let 0 ≤ k ≤ q -1. The vector space of evaluation vectors of polynomials of degree ≤ k over F q is called the (full-length) Reed-Solomon code:

RS q (k) := {ev A 1 ( f ), f ∈ F q [X] k } . and has dimension k + 1 over F q .
Definition 5 (Reed-Muller code). Let 0 ≤ d ≤ m(q -1). The (generalized) Reed-Muller code of order m and degree d over F q is the subspace of F q m q consisting in evaluation vectors of m-variate polynomials over F q of total degree ≤ d:

RM q (m, d) := {ev A m ( f ), f ∈ F q [X] d } . For d > 0, the dimension of RM q (m, d) is given by [AK92]: dim RM q (m, d) = d ∑ i=0 m ∑ j=0 (-1) j m j i -jq + m -1 i -jq ,
and simplifies to ( m+d m ) for d ≤ q -1. Reed-Muller codes generalize Reed-Solomon codes, in the sense that RM q (1, k) = RS q (k).

Projective Reed-Solomon and Reed-Muller codes. Previous codes can be naturally adapted to the context of projective spaces.

Definition 6 (Projective Reed-Solomon code). Let 0 ≤ k ≤ q. The projective Reed-Solomon code of dimension k + 1 over F q is the linear code of length q + 1 = |P 1 | consisting of the evaluation of bivariate homogeneous polynomials of degree k over F q : PRS q (k)

:= {ev P 1 ( f ), f ∈ F q [X, Y] H k } .
Projective Reed-Solomon codes are also called extended, or doubly-extended Reed-Solomon codes. Similarly, Reed-Muller codes have a projective analogue, defined as follows [Lac86, Lac90, Sør91]: Definition 7 (Projective Reed-Muller code). Let 1 ≤ v ≤ m(q -1). The projective Reed-Muller code of order m and degree v over F q is the linear code of length |P m | = (q m+1 -1)/(q -1) consisting of the evaluation of (m + 1)-variate homogeneous polynomials over F q of degree v:

PRM q (m, v) := {ev P m ( f ), f ∈ F q [X] H v } . The dimension of PRM q (m, v) is (see [Sør91]): dim PRM q (m, v) = ∑ t∈I v m+1 ∑ j=0 (-1) j m + 1 j t -jq + m t -jq ,
where

I v = {t ∈ [1, v], t ≡ v mod q -1}. For v ≤ q -1, it simplifies to dim PRM q (m, v) = ( m+v v ).
Once again, by definition we have PRS q (k) = PRM q (1, k) for every 1 ≤ k ≤ q -1.

Reduced degree sets

In the previous subsection, we have seen that well-known families of linear codes are defined as the image of subspaces of polynomials by evaluation maps. For coding theoretic reasons (e.g. giving the dimension of the code, or computing a basis), it is interesting to find sets

D ⊆ S m+1 (v) (resp. D ⊆ B m 1 (v)
) such that the map ev P m (resp. ev A m ) is injective over Poly(D). So let us define such sets.

First of all, we introduce specific tuples.

Definition 8 (A and P-reduced tuples).

1. A tuple d ∈ N m is A-reduced if d lies in B m ∞ (q -1). 2. A tuple d = (d 0 , . . . , d m ) ∈ N m+1 is P-reduced if, for all 0 ≤ i ≤ m: d i ≥ q ⇒ d j = 0 ∀j < i , d j ≤ q -1 ∀j > i .
We see that any A-reduced tuple is also P-reduced. We also say that a set D of tuples is A-reduced (resp. P-reduced) if every tuple it contains is A-reduced (resp. P-reduced).

Denote by (e 1 , . . . , e m ) the canonical basis of N m . Let d ∈ N m , 1 ≤ i < j ≤ m, and assume that d j ≥ q and d i ≥ 1. For such d (and only for such d), we define ρ j (d) := d -(q -1)e j and τ ij (d

) := d + (q -1)(e i -e j ). Remark that |τ ij (d)| = |d|.
Remark 9. Let d ∈ N m or N m+1 depending on the context (affine or projective). Then,

• we have ev A m (X ρ j (d) ) = ev A m (X d ) and ev P m (X τ ij (d) ) = ev P m (X d );
• as long as they are defined,

ρ j • ρ = ρ • ρ j and τ ij • τ k = τ k • τ ij ;
• if no τ ij can be applied to d, then d is P-reduced;

• if no ρ j can be applied to d, then d is A-reduced;

• if we keep applying to some tuple d the maps τ ij , for 0 ≤ i < j ≤ m, until we cannot apply any of them, then we obtain a P-reduced tuple;

• if we keep applying to some tuple d the maps ρ j , for 1 ≤ j ≤ m, until we cannot apply any of them, then we obtain an A-reduced tuple.

Definition 10. Let d ∈ N m . The A-reduction of d is the tuple d ∈ N m which is obtained by applying iteratively ρ j (for 1 ≤ j ≤ m) until the result lies in B m ∞ (q -1). It satisfies ev A m (X d ) = ev A m (X d ). The A-reduction of D ⊆ N m+1 , denoted D, consists in the A-reduction of the tuples in D.

Definition 11. Let d ∈ S m+1 (v) for some v > 0. The P-reduction of d is the tuple d ∈ S m+1 (v) which is obtained by applying iteratively τ ij (for 0 ≤ i < j ≤ m) until the result is P-reduced. It satisfies ev P m (X d ) = ev P m (X d ). The P-reduction of D ⊆ S m+1 (v), denoted D, consists in the P-reduction of the tuples in D.

Aand P-reduction are defined in order to make the evaluation maps ev A m and ev P m injective over polynomial spaces of the form Poly(D), where D is Aor P-reduced. Next lemma details these properties.

Lemma 12. Let m ≥ 1 and v ∈ N. The following properties hold:

1. If D ⊆ N m is A-reduced, then the map ev A m is injective over Poly(D).

2. If D ⊆ S m+1 (v) is P-reduced, then the map ev P m is injective over Poly(D).

3. For every D ⊆ N m , the A-reduction D of D is the unique A-reduced subset of N m satisfying

ev A m (Poly(D)) = ev A m (Poly(D)) .
4. For every D ⊆ S m+1 (v), the P-reduction D of D is the unique P-reduced subset of S m+1 (v) satisfying ev P m (Poly(D)) = ev P m (Poly(D)) .

Proof.

1. By definition, if D is A-reduced, then D is a subset of B m ∞ (q -1). Since ker(ev A m ) = X q i -X i 1≤i≤m , we can see that Poly(D) ∩ ker(ev A m ) = {0}. 2. We proceed by induction on m. Recall that ker(ev

P m ) = X q i X j -X i X q j 0≤i<j≤m ∩ F q [X] H v .
• For m = 1 and v ∈ N, let D be a P-reduced subset of S 2 (v). If v ≤ q, it is clear that ker(ev P 1 ) ∩ Poly(D) = {0}. So assume v > q and let f (X, Y) ∈ Poly(D) ∩ ker(ev P 1 ). Since D is P-reduced, we can write

f (X, Y) := f v Y v + q-1 ∑ i=0 f i X v-i Y i ∈ Poly(D) .
Then, we see that

f v = f (0, 1) = 0, hence g(Y) := f (1, Y) = ∑ q-1 i=0 f i Y i lies in Poly(D ), for some set D ⊆ B 1
∞ (q -1). Moreover f ∈ ker(ev P 1 ) implies g ∈ ker(ev A 1 ). Hence, the first point of this Lemma (applied to D which is A-reduced) shows that g = 0, and f = 0 follows.

• Let m > 1 and v ∈ N. The proof works similarly. Let D be a P-reduced subset of S m+1 (v), and let

f (X) := f 0 (X 1 , . . . , X m ) + X 0 f 1 (X 0 , X 1 , . . . , X m ) ∈ Poly(D) ∩ ker(ev P m ) .
Since f 0 does not depend on X 0 , we can see that f 0 ∈ ker(ev P m-1 ) and f 0 ∈ Poly(D 0 ) where D 0 ⊂ S m (v). Besides, D 0 is P-reduced as a subset of D. Therefore, by induction f 0 = 0, and f = X 0 f 1 (X 0 , X 1 , . . . , X m ) follows. Let us define g := f (1, X 1 , . . . , X m ); we see that g ∈ ker(ev A m ) and g ∈ Poly(D ) where D ⊆ B m ∞ (q -1) since D is P-reduced and every degree tuple in D comes from a tuple d ∈ D such that d 0 = 0. Thanks to the first point of the lemma, it follows that g = 0. Therefore, f = αX v 0 with α ∈ F q , which necessarily implies f = 0 (evaluate it at (1 : 0 : • • • : 0)).

Since ev

A m (X d ) = ev A m (X d ) for every d ∈ N m ,
C = |Deg(C)| .
Example 14. Reed-Solomon and Reed-Muller codes, as well as their projective analogues, are monomial codes. Table 1 presents their degree sets.

Code Degree set

Reed-Solomon code RS q (k)

B 1 1 (k) = {0, 1, . . . , k} Reed-Muller code RM q (m, k) B m 1 (k) = {e | e ∈ N m , |e| ≤ k} projective Reed-Solomon code PRS q (k) S 2 1 (k) = {(k, 0), (k -1, 1), . . . , (0, k)} projective Reed-Muller code PRM q (m, k) S m+1 1 (k) = {d | d ∈ N m+1 , |d| = k}

Permutations, automorphisms

Generally, a linear code C is a linear subspace of F X q for some finite set X. Any permutation σ of X induces a permutation of the coordinates of vectors c ∈ F X q given by:

σ(c) = (c σ -1 (x) ) x∈X ∈ F X q
Denote by S(X) the group of permutations of X. The subset of permutations of X which let C invariant is a subgroup of S(X), called the permutation group of C, and denoted by Perm(C). Let Iso(X) be the semi-direct product F × q X S(X). Any (w, σ) ∈ Iso(X) acts on c ∈ F X q by: (w, σ)

• c = w σ(c) ,
where denotes the component-wise product between tuples: a b = (a 1 b 1 , . . . , a m b m ). If w = (1, . . . , 1), we simply write σ ∈ Iso(X). The subgroup of Iso(X) letting C invariant is called the automorphism group of C, and is denoted by Aut(C). Of course, Perm(C) ⊆ Aut(C).

Let us finally denote by GL m (F q ) the group of m × m invertible matrices over F q . Using the canonical basis, these matrices represent linear automorphisms A m → A m . Affine evaluation codes. In the case X = A m , let us define the affine transformations T M,b :

A m → A m by x → Mx + b, for every M ∈ GL m (F q ) and b ∈ F m q . Each T M,b is a permutation of A m . Denote by Aff(F q , m) the group of such transformations: Aff(F q , m) = {T M,b | (M, b) ∈ GL m (F q ) × F m q } . In Appendix A.3 we prove that Aff(F q , m) ⊆ Perm(RM q (m, k)) for every 0 ≤ k ≤ m(q -1).
Projective evaluation codes. In the case X = P m , let M ∈ GL m+1 (F q ). Then x → Mx induces a permutation of P m , but does not necessarily preserve the standard representation of projective points. Still, there exists λ M,x ∈ F × q such that the standard representative of Mx is λ M,x Mx. For every f ∈ F q [X] H v , we then have:

ev Mx ( f ) = f (λ M,x Mx) = (λ M,x ) v f (Mx) = (λ M,x ) v ev x ( f • M) ,
and we see that (λ M,x ) v does not depend on f (only on its total degree). Let us denote by w v M := ((λ M,x ) v : x ∈ P m ), and by σ M the permutation of P m induced by M. Then, we have:

ev P m ( f • M) = w v M σ M -1 (ev P m ( f )) . Denote by Proj(F q , m) := {(w v M , σ M -1 ) ∈ Iso(P m ), M ∈ GL m+1 (F q )
} in the context of evaluating homogeneous polynomials of degree v. In Appendix A.3 we prove that Proj(F q , m) ⊆ Aut(PRM q (m, v)) for every 1 ≤ v ≤ m(q -1).

Embedding maps

Here we define maps embedding lines into higher dimensional spaces. For U, V two F q -linear spaces, we denote by Hom(U, V) the set of linear maps U → V. Let Emb P (m) be the set of full-rank (i.e. injective) linear maps from F 2 q to F m+1 q :

Emb P (m

) := {L ∈ Hom(F 2 q , F m+1 q ), rank L = 2} .
Each L ∈ Emb P (m) induces a projective embedding P 1 → P m sending (x : y) → L(x, y).

One can easily check that this map is well defined over projective spaces. Moreover, the set {L(P 1 ), L ∈ Emb P (m)} describes all the projective lines of P m , though a projective line is obviously associated to many maps L in Emb P (m).

Similarly, the set

Emb A (m) := {L * = (L 1 , . . . , L m ) ∈ Hom(F 2 q , F m q ) | L = (L 0 , . . . , L m ) ∈ Emb P (m)} defines affine embeddings A 1 → A m by t → L * (1, t). The set {L * (1, A 1 ), L * ∈ Emb A (m)} defines the set of affine lines of A m .
Remark 15. Elements of Emb P (m) and Emb A (m) will sometimes be seen as (m + 1) × 2 or m × 2 matrices over F q . Besides, for convenience and when the context is clear, we will improperly write L * (t) instead of L * (1, t). By using this notation, we want to emphasize that, for every f ∈ F q [X] and every

L * ∈ Emb A (m), the map t → f (L * (1, t)) can be interpolated as a univariate polynomial denoted f • L * ∈ F q [T].
Remark 16. For local correction purposes (see section 4), it is important to notice the following points.

1. In the affine setting, for every

L * ∈ Emb A (m) and f ∈ F q [X], the word ev A 1 ( f • L * ) is a subword of ev A m ( f )
, and can be read at indices L * (t) for t ∈ A 1 .

2. In the projective setting, ev P 1 ( f • L) is not necessary a subword of ev P m ( f ), since nothing asserts that L preserves the standard representation of projective points, similarly to the discussion in Subsection 2.4. We solve this issue in a very similar manner. Let x ∈ P 1 and L ∈ Emb P (m). We know there exists λ L,x ∈ F × q such that the standard representative P of L(x) is λ L,x L(x) ∈ P m . Then it holds:

∀ f ∈ F q [X] H v , ev P ( f ) = f (λ L,x L(x)) = (λ L,x ) v ( f • L)(x) .
Therefore, let us define w v L = ((λ L,x ) v : x ∈ P 1 ). Then w v L ev P 1 ( f • L) is a subword of ev P m ( f ), and can be read at indices L(x) ∈ P m for x ∈ P 1 .

Example 17. Let us fix an ordered list of points in P 1 (F 3 ) and P 2 (F 3 ): P 1 (F 3 ) = (1 : 1), (1 : 2), (1 : 0), (0 : 1) P 2 (F 3 ) = (1 : 1 : 1), (1 : 1 : 2), (1 : 1 : 0), (1 : 2 : 1), (1 : 2 : 2), (1 : 2 : 0),

(1 : 0 : 1), (1 : 0 : 2), (1 : 0 : 0), (0 : 1 : 1), (0 : 1 : 2), (0 : 1 : 0), (0 : 0 : 1)

Let f = X 1 ∈ F 3 [X 0 , X 1 , X 2 ] H
1 and L ∈ Emb P (2) represented by the matrix:

L =   1 1 0 1 1 0   Denote by c = ev P 2 ( f ) = (1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 0) ∈ F 13 3 .
On the one hand we have L(P 1 ) = ((2 : 1 : 1), (0 : 2 : 1), (1 : 0 : 1), (1 : 1 : 0)) = ((1 : 2 : 2), (0 : 1 : 2), (1 : 0 : 1), (1

: 1 : 0)) , (1)
hence ev P 2 ( f ) |L(P 1 ) = (c 5 , c 11 , c 7 , c 3 ) = (2, 1, 0, 1). On the other hand ( f • L)(S, T) = T ∈ F 3 [S, T] H
1 , and we get ev

P 1 ( f • L) = (1, 2, 0, 1). Clearly ev P 2 ( f ) |L(P 1 ) = ev P 1 ( f • L). Nevertheless, w 1
L can be obtained through the homogenizing made in (1):

w 1 L = (2 1 , 2 1 , 1 1 , 1 1 ) .
Therefore it gives:

w 1 L ev P 1 ( f • L) = (2, 1, 0, 1) = ev P 2 ( f ) |L(P 1 ) .

Affine and projective lifted Reed-Solomon codes

Before introducing our construction, we recall the definition of affine lifted codes given by Guo, Kopparty and Sudan [START_REF] Guo | New affine-invariant codes from lifting[END_REF]. Notice that we restrict our study to the lifting of (projective) Reed-Solomon codes, but we believe that our construction can be extrapolated to the lifting of (projective) Reed-Muller codes. Besides, our formalism is slightly different from the paper of [START_REF] Guo | New affine-invariant codes from lifting[END_REF], since their notion of restriction f |L of a polynomial f along a line L is somewhat ambiguous.

Affine lifted codes

We first need to introduce a few notation.

• Let a = ∑ a (i) p i be the p-adic decomposition of a non-negative integer a. We define a partial order ≤ p on integers by:

a ≤ p b ⇐⇒ a (i) ≤ b (i) , ∀i . (2)
The relation ≤ p can be naturally extended to m-tuples by a ≤ p b ⇐⇒ ∀j, a j ≤ p b j .

• We also extend binomial coefficients to m-tuples of integers by ( a b ) := ∏ m i=1 ( a i b i ).

We also recall that, for f ∈ F q [X] and L ∈ Emb A (m), the notation f • L represents the univariate polynomial f (L(1, T)).

Definition 18 (Affine lifting of Reed-Solomon codes [START_REF] Guo | New affine-invariant codes from lifting[END_REF]). Let 0 ≤ k ≤ q -2 and m ≥ 1. The affine lifting of order m of the Reed-Solomon code RS q (k) is

Lift q (m, k) := {ev A m ( f ) | f ∈ F q [X], ∀L ∈ Emb A (m), ev A 1 ( f • L) ∈ RS q (k)} .
The codes Lift q (m, k) will shortly be called affine lifted codes. In [START_REF] Guo | New affine-invariant codes from lifting[END_REF] it is also proved that every affine lifted code Lift q (m, k) is monomial and satisfies

Lift q (m, k) = ev A m (X d ) | d ∈ B m ∞ (q -1), ∀e ≤ p d, |e| ≤ k , (3)
where p = char(F q ) and |e| = ∑ i e i . Note that monomiality of affine lifted code follows from their affine-invariance, by using a result of Kaufman and Sudan [START_REF] Kaufman | Algebraic property testing: the role of invariance[END_REF].

A careful observation of their degree sets shows that Lift q (m, k) fits between two projective Reed-Muller codes:

RM q (m, k) ⊆ Lift q (m, k) ⊆ RM q (m, k + (m -1)(q -1)) . ( 4
)
The main interest of affine lifted codes appears for some values of q and k (essentially q non-prime and k close to q), for which the first inclusion is proper. Indeed, Kaufman and Ron give in [START_REF] Kaufman | Testing polynomials over general fields[END_REF] arguments that shows that affine lifted codes are Reed-Muller codes as long as k < q -q p (where p is the characteristic of the field). In the k ≥ q -q p setting, some families of affine lifted codes give rise to a family of highrate locally decodable and correctable codes, while Reed-Muller codes have rate bounded by 1/m!. More specifically, the following theorem is proved in [START_REF] Guo | New affine-invariant codes from lifting[END_REF] (we report the formal definition of locally correctable codes to Section 4):

Theorem 19 (High rate lifted codes, [START_REF] Guo | New affine-invariant codes from lifting[END_REF]). Let 0 < ρ, γ < 1 and n 0 ≥ 1. Define m := 1/δ , q := 2 s ≥ n γ 0 , b := 1 + log m and c := b2 bm log(1/ρ) . Finally, let k := (1 -2 -c )q. Then the code Lift q (m, k) has length n ≥ n 0 , rate R ≥ 1ρ, and is locally correctable with locality = n γ for a δ = 2 -c /6 fraction of errors.

However, for generic parameters m, k, q, exact formulae for the dimension of affine lifted codes are hard to produce. We give some concrete values in Appendix C.

Projective lifted codes

In this section, we aim at defining the projective analogues of the lifted Reed-Solomon codes introduced by Guo et al. [START_REF] Guo | New affine-invariant codes from lifting[END_REF]. A way to build an evaluation code over a projective space is to evaluate homogeneous polynomials of fixed degree v, as it is done for projective Reed-Muller codes. It raises the problem of determining a meaningful value of v we could use to define projective lifted codes. Equation (4) suggests to set v = v m,k := k + (m -1)(q -1).

Definition 20. Let 1 ≤ k ≤ q -1, m ≥ 1 and v = v m,k = k + (m -1)(q -1). The projective lifting of order m of the projective Reed-Solomon code PRS q (k) is PLift q (m, k) = {ev P m ( f ) | f ∈ F q [X] H v , ∀L ∈ Emb P (m), ev P 1 ( f • L) ∈ PRS q (k)} .
Such a code will shortly be called a projective lifted code, and its length is θ m,q = |P m | = (q m+1 -1)/(q -1).

Monomiality of projective lifted codes

Similarly to the affine setting, a main issue remains to give a basis of PLift q (m, k). In this subsection, we show that projective lifted codes are monomial, and then we compute their degree set. For this purpose, we first prove Theorem 21 which can be seen as a projective analogue of the monomial extraction lemma of Kaufman and Sudan [START_REF] Kaufman | Algebraic property testing: the role of invariance[END_REF].

Theorem 21. Let C = ev P m (F ) be a projective evaluation code, where F is a subspace of F q [X] H v for some m, v ≥ 1. Assume that Proj(F q , m) ⊆ Aut(C). Then C is monomial.

Before diving straight into the proof, we first observe that lie in Proj(F q , m) elements (w v M , σ M -1 ) where M is:

• a diagonal isomorphism Diag a for any a ∈ (F × q ) m+1 , where Diag a : P m → P m (P 0 : . . . : P m ) → (a 0 P 0 : . . . : a m P m )

• an elementary switch of coordinates s i,j for any 0 ≤ i, j ≤ m, i = j, where s i,j : P m → P m (P 0 : . . . : P i : . . . : P j : . . . : P m ) → (P 0 : . . . : P j : . . . : P i : . . . : P m )

• an elementary transvection t i,j,β for any 0 ≤ i, j ≤ m, i = j, and β ∈ F q , where t i,j,β : P m → P m (P 0 : . . . : P i : . . . : P m ) → (P 0 : . . . : P i + βP j : . . . :

P m ) Proof of Theorem 21. Let c = ev P m ( f ) ∈ C, where f = ∑ d f d X d , and denote by D = Deg( f ) = {d, f d = 0}.
Our goal is to prove that every j ∈ D satisfies ev P m (X j ) ∈ C. The proof will consist in three main parts:

(i) we prove that ev P m (Q j (X)) ∈ C for some polynomial Q j (X) such that j ∈ Deg(Q j ) and Deg(Q j ) is much smaller than Deg(C);

(ii) we analyse and rephrase Deg(Q j ), allowing us to write

Q j as X j 1 1 . . . X j a
a R(X 0 , X a+1 , . . . , X m ) for some multivariate polynomial R;

(iii) we prove that, if there exists an (ma + 1)-variate polynomial R satisfying some prescribed properties and such that ev P m (X

j 1 1 . . . X j a
a R(X 0 , X a+1 , . . . , X m )) ∈ C, then we can compute an (ma)-variate polynomial R satisfying the same prescribed properties, and such that the vector ev P m (X

j 1 1 . . . X j a+1 a+1 R (X 0 , X a+2 , . . . , X m )) ∈ C.
Reasoning inductively on the last part will conclude the proof.

Proof of part (i). Let j ∈ D, and define

Q j (X) := (-1) m+1 ∑ a∈(F × q ) m+1 m ∏ i=0 a -j i i ( f • Diag a )(X) .
Since C is linear and Diag a ∈ Aut(C) for every a ∈ (F × q ) m+1 , we see that ev P m (Q j (X)) ∈ C. We also have:

Q j (X) = (-1) m+1 ∑ a∈(F × q ) m+1 m ∏ i=0 a -j i i ∑ d f d a d 0 0 . . . a d m m X d = (-1) m+1 ∑ d f d ∑ a∈(F × q ) m+1 m ∏ i=0 a d i -j i i X d = (-1) m+1 ∑ d f d m ∏ i=0 ∑ a i ∈F × q a d i -j i i =0 if d i ≡j i mod (q-1), -1 otherwise X d = ∑ d∈E j f d X d ,
where E j = {d ∈ D, d ≡ j mod (q -1)}.

Proof of part (ii). The code C is invariant under the action of elementary switches of coordinates. Therefore one can assume w.l.o.g. that, if exists, the j i 's satisfying j i ∈ (q -1)N lie at the end of the tuple j. Besides, by P-reduction and by definition of E j , we can assume that j i / ∈ {0, q -1} implies that j i = d i , except maybe for the leftmost non-zero coordinate of d and j. Therefore, w.l.o.g. there exists a ∈ [1, m] such that every d ∈ E j satisfies the following three properties

   ∀1 ≤ i ≤ a, we have d i = j i < q -1 ∀a < i ≤ m, we have d i ∈ {0, q -1} and j i ∈ {0, q -1} d 0 = v -∑ m i=1 d i .
Therefore, Q j (X) can be written as

X j 1 1 . . . X j a
a R(X 0 , X a+1 , . . . , X m ), where R is an homogeneous polynomial of degree v -∑ a i=1 j i , whose monomials have partial degree either 0 or q -1, for every coordinate X i , i > a.

Proof of part (iii). Recall that we aim to prove that ev P m (X

j 0 0 X j 1 1 . . . X j m
m ) ∈ C, and we know that ev P m (Q j (X)) ∈ C. Our strategy is to proceed inductively, from i = a to m, by proving there exists an (mi + 1)-variate polynomial R i such that j ∈ Deg(X

j 1 1 . . . X j i i R i (X 0 , X i+1 , . . . , X m )) and ev P m (X j 1 1 . . . X j i i R i (X 0 , X i+1 , . . . , X m )) ∈ C.
Notice that step i = a has been proved in part (ii), and that step i = m concudes the proof. Hence there remains to prove the induction step.

Write

R i = R i + X q-1 i+1 R i
, where polynomials R i and R i do not depend on X i+1 . Also denote by S i = X j 1 1 . . . X j i i R i (X 0 , X i+1 , . . . , X m ), and assume that ev P m (S i ) ∈ C and j ∈ Deg(S i ).

If R i = 0, then the induction step is proved. Otherwise:

• 1st case: j i+1 = 0. Since ∑ β∈F q (X i+1 + βX 0 ) q-1 = -X q-1 0 (see Lemma 62 in the appendix), we get

∑ β∈F q S i (X 0 , . . . , X i+1 + βX 0 , . . . , X m ) = X j 1 1 . . . X j i i ∑ β∈F q R i (X 0 , X i+2 , . . . , X m ) + (X i+1 + βX 0 ) q-1 R i (X 0 , X i+2 , . . . , X m ) = ∑ β∈F q X j 1 1 . . . X j i i R i (X 0 , X i+2 , . . . , X m ) -X j 1 1 . . . X j i i X q-1 0 R i (X 0 , X i+2 , . . . , X m ) = -X j 1 1 . . . X j i i X q-1 0 R i (X 0 , X i+2 , . . . , X m ) .
By linearity and stability of C under elementary transvections, ev P m (S i ) ∈ C ensures that the word ev P m (X

j 1 1 . . . X j i i X q-1 0 R i (X 0 , X i+2 , . . . , X m )) ∈ C. We conclude by defining R i+1 = X q-1 0 R i . • 2nd case: j i+1 = q -1. Since ∑ β∈F q (βX i+1 + X 0 ) q-1 = -X q-1 i+1 , we get ∑ β∈F q S i (X 0 , . . . , X i+1 + βX 0 , . . . , X m ) = X j 1 1 . . . X j i i ∑ β∈F q R i (X 0 , X i+2 , . . . , X m ) + (βX i+1 + X 0 ) q-1 R i (X 0 , X i+2 , . . . , X m ) = -X j 1 1 . . . X j i i X q-1 i+1 R i (X 0 , X i+2 , . . . , X m ) .
Similarly to the first case, we can conclude by defining R i+1 = R i .

Projective lifted codes can be proved invariant under Proj(F q , m).

Lemma 22. Let k ≤ q -1, m ≥ 1 and C = PLift q (m, k). Then Proj(F q , m) ⊆ Aut(C). Said differently, ∀c = ev P m ( f ) ∈ C, ∀M ∈ GL m+1 (F q ), ev P m ( f • M) ∈ C .
Proof. It is sufficient to notice that, for every L ∈ Emb P (m) and every M ∈ GL m+1 (F q ), the map M • L also lies in Emb P (m).

As a corollary, Corollary 23. Every projective lifted code is monomial.

Degree sets of lifted codes

A natural question is now to determine the degree set of PLift q (m, k). Let us first recall that affine lifted codes have the following degree sets (see equation (3)):

ADeg q (m, k) := Deg(Lift q (m, k)) = {d ∈ B m ∞ (k), ∀e ≤ p d, |e| ≤ k} .
Similarly, we define PDeg q (m, k) := Deg(PLift q (m, k)).

In this subsection, we state a few links between degree sets of affine and projective lifted codes. Propositions 24 and 25 show that d ∈ PDeg(m, k) can be sent either to ADeg(m, k -1) or to PDeg(m -1, k), according to the value of d 0 . Then, in Theorem 26 we derive a recursive formula on the degree sets of affine/projective lifted codes, which translates into another recursive formula on the dimension of these codes (Corollary 27).

Proposition 24. Let v = k + (m -1)(q -1) for 1 ≤ k ≤ q -1 and m ≥ 2. Let also d = (d 0 , d * ) ∈ S m+1 (v) such that d 0 = 0. Then: ev P m (X d 0 0 X d * ) ∈ PLift q (m, k) ⇐⇒ ev A m (X d * ) ∈ Lift q (m, k -1) ,
or, equivalently,

d = (d 0 , d * ) ∈ PDeg q (m, k) ⇐⇒ d * ∈ ADeg q (m, k -1) .
Proof. (⇒). Let ev P m (X d 0 0 X d * ) ∈ PLift q (m, k) with d 0 = 0. Let also L * ∈ Emb A (m); we need to prove that ev A 1 (X d * • L * ) ∈ RS q (k -1). Let us define L = (L 0 , . . . , L m ) ∈ Hom(F2 q , F m+1 q ) as follows: the m last coordinates (L 1 , . . . , L m ) = L * , and the first coordinate L 0 is chosen between L 0 (S, T) = S and L 0 (S, T) = T, in order to have rank(L) = 2. Now assume w.l.o.g. that L 0 (S, T) = S. 2 Then,

ev P 1 (X d 0 0 X d * • L) = ev P 1 (X 0 X d * • L) = ev P 1 (S . (X d * • L * )(S, T)) ∈ PRS q (k) (5)
since X d 0 0 X d * and X 0 X d * evaluate identically. Besides, for any homogeneous polynomial P(S, T), we know that ev P 1 (S . P(S, T)) ∈ PRS q (k) ⇐⇒ ev A 1 (P(1, T)) ∈ RS q (k -1) .

(6)

Applying this to P(S, T) = (X d * • L * )(S, T), we get our result. (⇐). Let ev A m (X d * ) ∈ Lift q (m, k) and L ∈ Emb P (m). Let also d 0 = 0 such that (d 0 , d * ) ∈ S m+1 (v). We need to prove that ev P 1 (X d 0 X d * • L) ∈ PRS q (k). If L 0 = 0, then the result holds since 0 ∈ PRS q (k). Otherwise, it is worthwhile to notice that, since PRS q (k) is invariant under Proj(F q , 1), we can assume w.l.o.g. that L 0 (S, T) = S. Define L * = (L 1 , . . . , L m ), which lies in Emb A (m) by definition. Therefore ev A 1 (X d * • L * ) ∈ RS q (k -1), and using (5) and (6), we get our claim.

Proposition 25. Let v = k + (m -1)(q -1) for 1 ≤ k ≤ q -1 and m ≥ 2. Let also d = (d 0 , d * ) ∈ S m+1 (v), ans assume that d 0 = 0. Then:

ev P m (X d ) ∈ PLift q (m, k) ⇐⇒ ev P m-1 (X d * ) ∈ PLift q (m -1, k) , or equivalently, d = (0, d * ) ∈ PDeg q (m, k) ⇐⇒ d * ∈ PDeg q (m -1, k) .
Proof. (⇒). Let ev P m (X d ) ∈ PLift q (m, k) where d = (d 0 , d * ) and d 0 = 0. Let also L ∈ Emb P (m -1); we need to prove that ev P 1 (X d * • L ) ∈ PRS q (k). Any L 0 ∈ Hom(F 2 q , F q ) extends L to L = (L 0 , L ) ∈ Emb P (m). Therefore,

ev P 1 (X d * • L ) = ev P 1 (X 0 0 X d * • L) = ev P 1 (X d • L) (7) lies in PRS q (k) since ev P m (X d ) ∈ PLift q (m, k). (⇐). Let d = (d 0 , d * ) ∈ S m+1 (
v) with d 0 = 0, and assume that ev P m-1 (X d * ) ∈ PLift q (m -1, k). Let also L ∈ Emb P (m); we need to prove that ev P 1 (X d • L) ∈ PRS q (k). Write L = (L 0 , L ). If L ∈ Emb P (m -1), then the result follows using (7). The case rank L = 1 is a bit trickiest. Since Proj(F q , 1) let the code PRS q (k) invariant, we can assume w.l.o.g. that, seen as a 2 × m matrix, the second row of L is zero. In other words, L (S, T) can be written ( 1 S, . . . , m S) with some non-zero ( 1 , . . . , m ) ∈ F m q . Therefore, (X d • L)(S, T) = αS |d * | with α ∈ F q , and ev P 1 (X d • L) = α ev P 1 (S |d * | ) ∈ PRS q (k) since the P-reduction of (|d * |, 0) is (k, 0) which lies in Deg(PRS q (k)).

Theorem 26. For every m ≥ 2 and 1 ≤ k ≤ q -1, there is a bijection between PDeg(m, k) and

PDeg(m -1, k) ∪ ADeg(m, k -1).
Proof. According to Propositions 24 and 25, this bijection is given by:

d = (d 0 , d * ) → d * ∈ ADeg(m, k -1) if d 0 = 0 d * ∈ PDeg(m -1, k) otherwise.
A recursive formula on the dimension of lifted codes follows.

Corollary 27. Let m ≥ 2 and 1 ≤ k ≤ q -1. Then,

dim PLift q (m, k) = dim PLift q (m -1, k) + dim Lift q (m, k -1) .
One can also check that PLift q (1, k) = PRS q (k) and Lift q (1, k -1) = RS q (k -1). Therefore we also get:

Corollary 28. Let m ≥ 1 and 1 ≤ k ≤ q -1. Then, dim PLift q (m, k) = m ∑ j=1 dim Lift q (j, k -1) + 1 .
Finally, if one would like to explicit PDeg q (m, k), one could use iteratively the bijective map given in Theorem 26 and the characterisation of ADeg q (j, k -1), 1 ≤ j ≤ m, given previously. For d = (d 0 , . . . , d m ) ∈ S m+1 (v), define ι(d) the minimum i such that d i = 0, and η(d) = (d ι(d)+1 , . . . , d m ) ∈ S m-ι(d) . We then obtain Corollary 29. Let m ≥ 2 and 1 ≤ k ≤ q -1. Denote by v = k + (m -1)(q -1). Then,

PDeg q (m, k) = {d ∈ S m+1 (v), ∀e ≤ p η(d), |e| ≤ k -1} .
One also can see that any d ∈ S m+1 (k) can be lifted in Deg(PLift q (m, k)) by adding (q -1)(m -1) to the leftmost non-zero coordinate of d. Hence a corollary is the projective analogue of equation (4).

Corollary 30. Let 1 ≤ k ≤ q -1 and v = k + (m -1)(q -1). Then we have:

PRM q (m, k) ⊆ PLift q (m, k) ⊆ PRM q (m, v) ,
where the inclusion are taken up to diagonal isomorphisms of codes.

Example 31. We give here the smallest example of projective lifted code that is not isomorphic to any projective Reed-Muller code. Let q = 4, m = 2 and k = 3, giving v = k + (m -1)(q -1) = 6. The corresponding projective Reed-Muller code has length q 2 + q + 1 = 21, dimension ( m+d+1 d ) = 10, and admits D = {(3, 0, 0), (2, 1, 0), (2, 0, 1), (1, 2, 0), (1, 1, 1), (1, 0, 2), (0, 3, 0), (0, 2, 1), (0, 1, 2), (0, 0, 3)} as a degree set. A computation shows that PLift q (m, k) is given by the following degree set: D L = {(6, 0, 0), (5, 1, 0), (5, 0, 1), (4, 2, 0), (4, 1, 1), (4, 0, 2), (0, 6, 0), (0, 5, 1), (0, 4, 2), (0, 0, 6), (2, 2, 2)} .

One observes that D L = D ∪ {(2, 2, 2)}, where D is obtained by adding q -1 = 3 to the leftmost non-zero coordinate of every d ∈ D. Besides, the affine lifted code Lift q (m, k -1) has the following degree set:

D A = {(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (2, 2)} .
We see that D A corresponds to elements d ∈ D L such that d 0 = 0, then punctured on their first coordinate. We also remark that the remaining elements {(0, 6, 0), (0, 5, 1), (0, 4, 2), (0, 0, 6)}, being at first punctured on their first coordinate and then P-reduced, give the degree set {(3, 0), (2, 1), (1, 2), (0, 3)} of PRS q (k).

Finally, notice that the extra degree (2, 2, 2) which makes PLift q (m, k) non-isomorphic to PRM q (m, k) corresponds to the codeword c = ev P 2 (X 2 Y 2 Z 2 ). A tedious computation can then confirm that any embedding (S, T) → (a 0 S + b 0 T, a 1 S + b 1 T, a 2 S + b 2 T) sends c to a projective Reed-Solomon codeword.

Local correction

Definitions

This section is devoted to local correcting properties of projective lifted codes. After Guo et al.'s work [START_REF] Guo | New affine-invariant codes from lifting[END_REF], we know that affine lifted codes are (perfectly smooth) locally correctable codes. We first recall this notion.

Definition 32 (locally correctable code). Let Σ be a finite set, 2 ≤ ≤ k ≤ n be integers, and

δ, ∈ [0, 1]. A code C : Σ k → F n
q is ( , δ, )-locally correctable if and only if there exists a randomized algorithm D such that, for every input i ∈ [1, n] we have:

• for all c ∈ C and all y ∈ F n q , if |{j ∈ [1, n], y j = c j }| ≤ δn, then

P(D (y) (i) = c i ) ≥ 1 -,
where the probability is taken over the internal randomness of D;

• D reads at most symbols y q 1 , . . . , y q of y.

Notation D (y) refers to the fact that D has oracle access to single symbols y q j of the word y ∈ F n q . The parameter is called the locality of the code. Moreover, the code C is said perfectly smooth if on arbitrary input i, each individual query of the probabilistic algorithm D is uniformly distributed over the coordinates of the word y.

By definition of projective lifted codes, if c = ev P m ( f ) ∈ PLift q (m, k), then ev P 1 ( f • L) ∈ PRS q (k) for all L ∈ Emb P (m). In Remark 16 we noticed that ev P 1 ( f • L) is not a subword of ev P m ( f ). Nevertheless, denoting v = k + (m -1)(q -1), there still exists w v L ∈ (F × q ) q+1 such that w v L ev P 1 ( f • L) is such a subword. Moreover, given L and the standard representation of points in P 1 , each coordinate of w v L is expressed as a v-th power of a linear combination of O(m) F q -symbols (hence, it is also a k-th power since every x ∈ F q satisfies x q = x). Therefore,

w v L ∈ F q+1 q
can be computed in O(mq log k) operations over F q . To sum up we get: Lemma 33. Let c = ev P m ( f ) ∈ PLift q (m, k) and L ∈ Emb P (m). There exists a deterministic algorithm which computes ev P 1 ( f • L) from c and L, with q + 1 queries to c and O(mq log k) operations in F q .

Local correcting algorithms

For convenience, we fix a projective lifted code PLift q (m, k), and we denote by n = θ m,q its length. We also denote by ∞ the point (0 : 1) ∈ P 1 , and for a given P ∈ P m , Emb P (m, P) := {L ∈ Emb P (m), ev ∞ (L) = P} is the set of embeddings having P as image of the point at infinity. We denote by L(P 1 ) the set {ev Q (L), Q ∈ P 1 }.

In this subsection, we present a generic local correcting algorithm for projective lifted codes. This algorithm depends on a parameter s ∈ [k + 1, q], and it informally works as follows: (i) pick at random s points on a random projective line of P m , (ii) correct the associated noisy PRS q (k) codeword, and (iii) output the desired corrected symbol. This is somewhat a projective analogue of a generalization of the two well-known Reed-Muller local correcting algorithms (see Yekhanin's survey [Yek12, Section 2.2]), since we do not restrict s ∈ {k + 1, q}.

Let us assume we have access to a query generator R s , for k + 1 ≤ s ≤ q, with parameters P ∈ P m and L ∈ Emb P (m, P), such that for all P we have:

• for all L ∈ Emb P (m, P), if S ← R s (P, L), then S ⊆ L(P 1 ) and |S| = s,

• ∀Q ∈ P m , Pr L←Emb P (m,P)

S←R s (P,L) [Q ∈ S] = s/n.
Such a query generator can be implemented, as we show in Appendix B.

We also assume to have at our disposal an error-and-erasure correcting algorithm for PRS q (k), which corrects q + 1s erasures and up to t = s-k-1 2 errors (we recall that PRS q (k) is an MDS code and dim PRS q (k) = k + 1). Call Corr PRS s this correcting algorithm, and see [START_REF] Reed | Simplified algorithm for correcting both errors and erasures of Reed-Solomon codes[END_REF] for a simple example.

Theorem 34. Let k + 1 ≤ s ≤ q and t = s-k-1 2 . For every δ ≤ t+1 2s , the code PLift q (m, k) is a perfectly smooth (s, δ, δs t+1 )-locally correctable code using Algorithm 1. Proof. Let us analyse Algorithm 1. Concerning the locality, the algorithm indeed makes = s queries to y. Besides, it is smooth due to our assumption on R s . Now let us focus on the correctness.

Algorithm 1: A generic local correcting algorithm Corr PLift s for C := PLift q (m, k) Data: a noisy word y ∈ F P m q such that d(c, y) ≤ δn for some codeword c ∈ C, and a point P ∈ P m where to correct y P Result: the symbol c P 1 Pick uniformly at random L ← Emb P (m, P), and pick S = {Q 1 , . . . , Q s } ← R s (P, L). 2 Denote by R j = ev Q j (L). Collect y R 1 , . . . , y R s and define y ∈ F P 1 q by:

y Q := w v L,Q j • y R j if Q = Q j for some j ⊥ otherwise.
where w v L,Q j is the symbol indexed by Q j in the tuple w v L given in Remark 16 3 Use Corr PRS s to correct y as a noisy codeword of PRS q (k). 4 If this succeeds, return y (∞). Otherwise return ⊥.

Let y ∈ F P m q such that d(y, c) ≤ δn for some c ∈ PLift q (m, k). Denoting E = {Q ∈ P m , c Q = y Q }, we have |E| ≤ δn. By definition of the correcting algorithm of PRS q (k), the output value is correct as long as |E ∩ S| ≤ t. Let us bound this probability. Using Markov's inequality,

Pr L,S [|E ∩ S| ≤ t] = 1 -Pr L,S [|E ∩ S| ≥ t + 1] ≥ 1 -E L,S [|E ∩ S|]/(t + 1) .
By linearity, we get:

E L,S [|E ∩ S|] = ∑ e∈E Pr L,S [e ∈ S] = ∑ e∈E s n = δn s n = δs . Hence, Pr L,S [ algorithm succeeds ] ≥ 1 - δs t + 1 .
We exhibit the two extreme instances which correspond to the well-known correcting algorithms of Reed-Muller codes presented in [START_REF] Yekhanin | Locally decodable codes[END_REF] for instance. The first one picks the least possible number of symbols, but assumes few errors on the corrupted codeword. Corollary 35 (s = k + 1). For every δ ≤ 1 2(k+1) , the code PLift q (m, k) is a perfectly smooth (k + 1, δ, δ(k + 1))-locally correctable code.

Proof. s = k + 1 implies t = 0.

The second one achieves local correction under a constant fraction of errors on the corrupted codeword.

Corollary 36 (s = q). Let τ = k+1 q . For every δ ≤ 1 4 (1 -τ), the code PLift q (m, k) is a perfectly smooth (q, δ, 2δ 1-τ )-locally correctable code. Proof. s = q implies t = q(1-τ) 2 , hence t + 1 ≥ q(1-τ) 2 .
Remark 37. In Algorithm 1, we can avoid to compute the tuple w v L . Indeed, it can be proved that for every projective line S ⊂ P m and every point P ∈ S, there exists an L ∈ Emb P (m) such that L(P 1 ) = S, P ∈ {ev (1:0) (L), ev ∞ (L)} and w v L = (1, . . . , 1). Remark 38. Local testability of affine lifted codes was also proved by Guo et al. [START_REF] Guo | New affine-invariant codes from lifting[END_REF]. Once again, their results rely on the work of Kaufman and Sudan [START_REF] Kaufman | Algebraic property testing: the role of invariance[END_REF] regarding the testability of some families of affine-invariant codes. Though, projective lifted codes cannot be proved locally testable the same manner, since their automorphism group is slightly different. Though, this issue is worth addressing in a future work.

Puncturing and shortening relations between affine and projective lifted codes

In this section we aim at showing links between affine and projective lifted codes through shortening and puncturing operations on codes.

Motivation and similar results

The embedding of both P m-1 and A m into P m issues the relation between affine and projective Reed-Muller codes. Indeed, the hyperplane at infinity Π ∞ := {P ∈ P m , P 0 = 0} defines a restriction map π :

F P m q → F Π ∞ q c → c |Π ∞ .
Map π induces a surjective map PRM q (m, k) PRM q (m -1, k) by seeing Π ∞ as the projective space P m-1 . Indeed, every m-variate homogeneous polynomial of degree k can be also considered as an (m + 1)-variate homogeneous polynomial of same degree (in which the new variable, denoted X 0 , does not appear).

Besides, the vector space K := ker PRM q (m, k) PRM q (m -1, k) consists in evaluation vectors of homogeneous polynomials P ∈ F q [X 0 , . . . , X m ] H k such that X 0 divides P. That is,

K = {ev P m (X 0 Q), Q ∈ F q [X 0 , . . . , X m ] H k-1 } . Now, restricting K to coordinates in (P m \ Π ∞ )
A m leads to a vector space isomorphic to RM q (m, k -1), since X 0 evaluates to 1 on every affine point of P m .

To sum up, we have the following short exact sequence:

0 → RM q (m, k -1) → PRM q (m, k) π -→ PRM q (m -1, k) → 0 .
From a coding theory point of view, it may be more convenient to see this sequence in the terminology of puncturing and shortening. Indeed, up to isomorphism, the surjective map π corresponds to the puncturing of PRM q (m, k) on coordinates lying in A m ⊂ P m , while the injection RM q (m, k -1) -→ PRM q (m, k) corresponds to its shortening on P m-1 ⊂ P m .

A very similar exact sequence holds for the codes coming from the block designs of incidences between points and hyperplanes. Let us denote by C(D) the code whose dual code is generated by the incidence matrix of a block design D (we refer to [START_REF] Douglas | Combinatorial Designs -Constructions and Analysis[END_REF][START_REF] Assmus | Designs and Their Codes[END_REF] for details on block designs and their associated codes). Let also AG t (m, q) and PG t (m, q) be respectively the designs of points and t-flats in affine and projective spaces of dimension m > t over F q . Then it holds that

0 → C(AG 1 (m, q)) → C(PG 1 (m, q)) π -→ C(PG 1 (m -1, q)) → 0 .
This result is presented by Assmus and Key in [AK92, Theorem 5.7.2] for the dual of these codes, but it remains true for the codes we consider, since duality of codes preserves such short sequences.

In this section, our goal is to prove similar results for lifted codes.

Shortening and puncturing projective lifted codes

We recall that Π ∞ denotes the hyperplane of P m defined by X 0 = 0.

Theorem 39. Let m ≥ 1, 1 ≤ k ≤ q -1, and v = k + (m -1)(q -1). Let also

S := {c |A m | c ∈ PLift q (m, k) and c P = 0, ∀P ∈ Π ∞ }
be the shortening of PLift q (m, k) at the coordinates indexed by points in Π ∞ , and

P := {c |Π ∞ | c ∈ PLift q (m, k)}
be the puncturing of PLift q (m, k) at the coordinates indexed by points in P m \ Π ∞ . Then

S = Lift q (m, k -1) and P = PLift q (m -1, k) . Proof. (i) Proof of S = Lift q (m, k -1). Let c = ev A m (X d ) ∈ Lift q (m, k -1) and extend it to c = ev P m (X d 0 0 X d ) ∈ PLift q (m, k), with d 0 = v -|d| > 0.
We notice that c vanishes on the coordinates corresponding to points in Π ∞ , and that c = c elsewhere, hence c ∈ S.

Conversely, let c ∈ S. There exists f ∈ F q [X] H v such that c = ev P m ( f ) satisfies c = 0 over all coordinates of Π ∞ , and c = c elsewhere. It means that the polynomial f vanishes on the whole projective hyperplane Π ∞ given by X 0 = 0. Therefore f vanishes over the hyperplane Π ∞ of the affine space A m+1 given by X 0 = 0.

The previous remark makes sense since we can apply the Combinatorial Nullstellensatz proved by Alon in [START_REF] Alon | Combinatorial nullstellensatz[END_REF] (see Theorem 61 in the appendix). This result asserts that, if

W = ∏ m i=0 W i ⊆ F m+1 q and deg f = ∑ m i=0 t i with each t i < |W i |, then f (W) = {0} implies f t = 0,
where f t denotes the coefficient of the monomial X t in f . In our context, let W = {0} × F m q and t satisfy t 0 = 0 and t i ≤ q -1 for all i > 0. The Combinatorial Nullstellensatz then shows that Coeff( f , X t ) = 0. Therefore every monomial in f must be divisible by X 0 . Said differently, f is a sum of monomials X d with d such that d 0 = 0, and Proposition 24 then shows that ev

A m ( f ) ∈ Lift q (m, k -1). (ii) Proof of P = PLift q (m -1, k). First, PLift q (m -1, k) ⊆ P, since c = ev P m-1 (X d ) ∈ PLift q (m -1, k) can be extended to c = ev P m (X d ) ∈ PLift q (m, k)
, where we define d by adding q -1 to the leftmost non-zero coordinate of d.

Conversely, let c = ev P m ( f ) ∈ PLift q (m, k) such that c |Π ∞ ∈ P \ {0}. Let X d be a monomial in f . If d 0 = 0, then ev P m (X d ) |Π ∞ = 0, hence one can assume that every monomial X d composing f satisfies d 0 = 0. Using Proposition 25 and by linearity, it means that c |Π ∞ ∈ PLift q (m -1, k).

Remark 40. For m = 1, we know that by definition, Lift q (1, k) = RS q (k) and PLift q (1, k) = PRS q (k). Therefore, Theorem 39 rewrites the well-known result stating that the shortening at the infinity of the projective Reed-Solomon code is a (classical) Reed-Solomon code.

Theorem 39 also translates in terms of exact sequences: Corollary 41. The following exact sequence holds for every 1 ≤ k ≤ q -1 and m ≥ 1:

0 → Lift q (m, k -1) → PLift q (m, k) π -→ PLift q (m -1, k) → 0 ,
where π is the restriction map to points at infinity.

On the practicality of projective lifted codes

We here present miscellaneous results emphasizing the practicality of projective lifted codes. At first, we present tables and figures demonstrating the gain in terms of information rate, compared to projective Reed-Muller codes. In Subsection 6.2, we prove that the storage cost of projective lifted codes can be reduced since they admit (quasi-)cyclic automorphisms. Explicit information sets are then computed in Subsection 6.3. We conclude this section by estimating the minimum distance (Subsection 6.4) and connecting our construction to a well-known family of design-based codes (Subsection 6.5).

Proof. We can check that ψ d (U) = U, hence ψ d ∈ S(U). Since ψ d ∈ GL m+1 (F q ), the polynomial space Poly(D) is invariant under ψ d , where D = Deg(C). Besides, C = ev U (Poly(D)) thanks to Lemma 45. Therefore ψ d ∈ Perm(C ).

Let us now prove that ψ d is an (n/d)-cycle. For φ(ω i β jd ) ∈ U i , we have

ψ d (φ(ω i β jd )) = φ(ω i β jd β d ) = φ(ω i β (j+1)d ) ∈ U i .
It remains to show that the order of ψ d is n/d. Since φ is bijective and U represents P m , for every 0 ≤ s ≤ t < n/d we have:

∀u ∈ U i , (ψ d ) s (u) = (ψ d ) t (u) ⇐⇒ ω (t-s)d(q-1) = 1 ⇐⇒ n | (t -s)d(q -1) .
Our assumption on n/d and (q -1) implies that t = s; hence ψ d has order n/d.

As an easy corollary, when d = 1 we obtain Corollary 47. If n and q -1 are coprime, then for all 1 ≤ k ≤ q -1 the code w v PLift q (m, k) is cyclic.

Remark 48. A very similar approach was used by Berger and de Maximy in [START_REF] Thierry | Cyclic Projective Reed-Muller Codes[END_REF], in order to prove the quasi-cyclicity of codes isomorphic to our definition of projective Reed-Muller codes.

Explicit information sets

In this section, we aim at giving explicit information sets for projective lifted codes. Such sets are useful in order to extend the local correctability of lifted codes to a local decodability property (see [START_REF] Yekhanin | Locally decodable codes[END_REF]). Our techniques are highly inspired by the work of Guo and Kopparty [GK16, Appendix A]. We also prove a quite stronger result, being that a quite large family of affine evaluation codes presents the same information sets as affine lifted codes.

Monomiality of bounded degree affine evaluation codes. Similarly to the previous section, let φ : F q m → F m q be an F q -isomorphism. We denote by F q [X] ∞ q-1 := Poly(B m ∞ (q -1)) the space of m-variate polynomials of partial degree bounded by q -1. If f ∈ F q [X] ∞ q-1 is seen as a function, then the map f • φ : F q m → F q m can be interpolated uniquely as a univariate polynomial in F q m [X] q m -1 . We denote by φ * this process, which also appears to be an F qisomorphism:

φ * : F q [X] ∞ q-1 → F q m [X] q m -1 f (X) → ( f • φ)(X)
We know that Ω ∈ GL m (F q ) acts on m-variate polynomials by (Ω, f (X)) → f (Ω(X)). For some subspace F of polynomials, we say that

Ω ∈ Aut(F ) if { f • Ω, f ∈ F } ⊆ F .
For a nonzero a ∈ F × q m , we denote by µ a : F q m → F q m , x → ax. It is well-known that GL 1 (F q m ) = {µ a , a ∈ F × q m }. Every map µ a being F q -linear, we have M a := φ • µ a • φ -1 ∈ GL m (F q ). Map M a is known as the F q -homomorphism of the multiplication by a ∈ F q m . Lemma 49. Let F be a subspace of

F q [X] ∞ q-1 . If GL m (F q ) ⊆ Aut(F ), then GL 1 (F q m ) ⊆ Aut(φ * (F )). Proof. Let f • φ ∈ φ * (F ). For every µ a ∈ GL 1 (F q m ), we have f • φ • µ a = f • M a • φ by definition of the matrix of the multiplication by a. But M a ∈ GL m (F q ), hence f • M a ∈ F and we get f • φ • µ a ∈ φ * (F ).
Let us define the subgroup of diagonal isomorphisms Diag(F q , m) := {Diag a : P → (a 1 P 1 , . . . , a m P m ), a ∈ (F × q ) m } ⊆ GL m (F q ) . Proposition 50. Let F be a subspace of m-variate polynomials of partial degree bounded by q -2, that is F ⊆ Poly(B m ∞ (q -2)). If Diag(F q , m) ⊆ Aut(F ), then F is generated by monomials.

Proof. Let f ∈ F , such that f (X) = ∑ d∈D f d X d with D = {d ∈ N m , f d = 0}. It is sufficient to prove that for all d ∈ D, X d lies in F . Let d ∈ D.
Similarly to the proof of Theorem 21, we define

Q d (X) := (-1) m ∑ a∈(F × q ) m m ∏ i=1 a -d i i ( f • Diag a )(X)
Since F is a vector space and Diag(F q , m) ⊆ Aut(F ), we see that

Q d (X) ∈ F . Q d (X) = ∑ a∈(F × q ) m m ∏ i=1 -a -d i i ∑ j f j a j 1 1 . . . a j m m X j = ∑ j f j ∑ a∈(F × q ) m m ∏ i=1 -a j i -d i i X j = ∑ j f j m ∏ i=1 -∑ a i ∈F × q a j i -d i i =0 if d i =j i , 1 otherwise X j = f d X d .
We know that d ∈ D, hence f d = 0 and by linearity we obtain

X d = 1 f d Q d (X) ∈ F .
Information sets of some affine evaluation codes. We first recall the definition of an information set of a linear code.

Definition 51 (information set). Let C ⊆ F X q be a linear code of dimension k and support X, where |X| = n. An information set for C is a subset S ⊆ X, |S| = k such that the restriction of C to coordinates in X is F k q . In other words, S is such that the projection of C on F S q is injective.

Lemma 52. Let F ⊆ Poly(B m ∞ (q -1)) and assume that S ⊂ A 1 (F q m ) is an information set for ev A 1 (φ * (F )). Then φ(S) is an information set for ev A m (F ).

Proof. This follows from the fact that φ * (F ) = { f • φ, f ∈ F } and φ is an F q -isomorphism.

In the next proposition, we give a result that improves the theorem given by Guo and Kopparty in [GK16, Appendix A], in the specific case of codes evaluating polynomials with partial degree bounded by q -2 (which is the case for many interesting codes). Indeed, their result holds for affine-invariant codes while we only need codes invariant under GL m (F q ). Proposition 53. Let C = ev A m (F ) be an affine evaluation code of dimension k over F q , and assume that F ⊆ Poly(B m ∞ (q -2)) and GL m (F q ) ⊆ Aut(F ). Then, for every primitive element ω of F q m , and every isomorphism φ : F q m → F m q , the set {φ(ω), . . . , φ(ω k )} is an information set for C.

Proof. The proof is highly inspired by [GK16, Appendix A]. Thanks to Lemma 52, it is sufficient to prove that S = {ω, . . . , ω k } is an information set for C = ev A 1 (φ * (F )). Moreover, since Diag(F q , m) ⊆ GL m (F q ), the conjunction of Proposition 50 and Lemma 49 ensures that C is monomial. Denote by I = Deg(C ) = {i 1 , . . . , i k }, and let g(X) = ∑ i∈I a i X i ∈ F . We need to prove:

g = 0 =⇒ ev S (g) = 0 .
For this sake, we remark that

     ω i 1 ω i 2 . . . ω i k ω 2i 1 ω 2i 2 . . . ω 2i k . . . . . . . . . . . . ω ki 1 ω ki 2 . . . ω ki k           a 1 a 2 . . . a k      =      g(ω) g(ω 2 ) . . . g(ω k )      = ev S (g) .
Since the left-hand square matrix is a Vandermonde matrix and ω is primitive, it is invertible and the result is proved.

As a corollary we recover Guo and Kopparty's result, since GL m (F q ) is a subgroup of the group of affine transformations.

Corollary 54 (given in [START_REF] Guo | List-decoding algorithms for lifted codes[END_REF]). Let C = Lift q (m, k) for k ≤ q -2. Then, for every ω primitive element of F q m , and every φ isomorphism F q m → F m q , the set {φ(ω), . . . , φ(ω dim C )} is an information set for C.

The case of projective evaluation codes. We would like to prove a similar result for projective lifted codes. Unfortunately, one cannot define an isomorphism between P 1 (F q m ) and P m (F q ) since they do not have same cardinality. To solve this issue, our idea is to decompose P m (F q ) into affine parts, and to use recursively the links between projective and affine lifted codes we stated in previous sections.

Let

P m (F q ) = m i=0 A m,i (F q ), where A m,i (F q ) := {(0 : • • • : 0 : 1 : x 1 : • • • : x i ), (x 1 , . . . , x i ) ∈ A i (F q )} .
Informally, A m,i is the affine part of the i-dimensional projective subspace at infinity of P m .

Theorem 55. Let C = PLift q (m, k) for k ≤ q -1. Then, for every ω i primitive element of F q i , and every isomorphism φ i :

F q i → A m,i (F q ), the set S = m i=0 {φ i (ω i ), . . . , φ i (ω dim C i i )}
is an information set for C, where C i = Lift q (i, k -1) for i > 0, and by convention, dim C 0 = 1 and φ 0 (F q 0 ) := {(0 : • • • : 0 : 1)}.

Proof. We proceed by induction on m.

• Case m = 1. Then C = PRS q (k) which is an MDS code of dimension k + 1, hence any (k + 1)-subset of P 1 is an information set for C. In particular, S = {(0 : 1)} ∪ {φ 1 (ω 1 ), . . . , φ 1 (ω k 1 )} is one of them.

• Induction step. Assume the result holds for step m -1. A basis of PLift q (m, k) consists in evaluating monomials with exponents in PDeg q (m, k). Thanks to Theorem 26, we know that PDeg q (m, k) is in bijection with ADeg q (m, k -1) PDeg q (m -1, k), where the bijection is given in the proof of the theorem. Hence, there exists a generator matrix of PLift q (m, k) defined as follows:

                      G 0 0 * G 1 • • • (1 : x 1 : • • • : x m ) • • • (0 : . . . )                              A m (F q )            P m-1 (F q )          evaluation of monomials with degrees in ADeg(m, k -1)    evaluation of monomials with degrees in PDeg(m -1, k)
where G 0 and G 1 are generator matrices of Lift q (m, k -1) and PLift q (m -1, k) respectively.

Since G 1 and G 0 are full-rank, we know that the union of an information set S 0 of Lift q (m, k -1) and an information set S 1 of PLift q (m -1, k) gives an information set S of PLift q (m, k). Information sets of affine lifted codes are described in Corollary 54 (we just need to take care about the way we represent affine points in the projective space, whence the definition of the A m,i , 1 ≤ i ≤ m). Therefore we have S 0 = {φ m (ω m ), . . . , φ m (ω dim C m m )} with φ m , ω m defined as in the statement of the theorem. Besides, the inductive step gives the information set of PLift

q (m -1, k): S 1 = m-1 i=0 {φ i (ω i ), . . . , φ i (ω dim C i i
)}. Therefore S = S 0 S 1 leads to the result at step m.

Estimation of the minimum distance

We give bounds on the minimum distance of a projective lifted code, depending on the minimum distance of the underlying projective Reed-Solomon code. In this section, wt(c) denotes the Hamming weight of a vector c, and nz S ( f ) denotes the number of zeroes of f ∈ F q [X 0 , . . . , X m ] H v over the set S ⊆ P m .

Proposition 56 (upper bound). Let 1 ≤ k ≤ q -1 and PRS q (k) be the projective Reed-Solomon code of dimension k + 1 and distance d = q + 1k. Then the distance D of PLift q (m, k) satisfies: D ≤ θ m,qq m-1 (q + 1d)

where θ m,q = q m+1 -1 q-1 . As a corollary, the relative distance δ of PRS q (k) and ∆ of PLift q (m, k) satisfy:

∆ ≤ (1b)δ + b, where 0 ≤ b ≤ q -2 .

Proof. Let c = ev P 1 (g) ∈ PRS q (k) be a minimum-weight codeword, i.e. wt(c) = d. Assume that g(X 0 , X 1 ) = ∑ k i=0 g i X i 0 X k-i 1 , and let f (X 0 , . . . , X m ) := g 0 X (q-1)(m-1)+k 1

+ k ∑ i=1 g i X (q-1)(m-1)+i 0 X k-i 1 ∈ F q [X 0 , . . . , X m ] H v
where v = (q -1)(m -1) + k. By studying the degrees of f , one can check that c := ev P m ( f ) ∈ PLift q (m, k). Moreover, for every (x 0 : x 1 ) ∈ P 1 , we have:

f (x 0 , x 1 , x 2 , . . . , x m ) = g(x 0 , x 1 ), ∀x = (x 2 , . . . , x m ) ∈ F m-1 q .

Hence c is non-zero, and:

D ≤ wt(c ) = θ m,qnz P m ( f ) ≤ θ m,qnz P 1 (g) q m-1 = θ m,qq m-1 (q + 1d) .

For the bound on the relative distance, we divide both sides of the previous equation by θ m,q and we use that d = (q + 1)δ by definition. Then we get:

∆ ≤ 1 + (δ -1)a ,
where a = (q+1)q m-1 θ m,q = 1 -q m-1 -1 q m+1 -1 satisfies 1q -2 ≤ a ≤ 1. Denoting b = 1a concludes the proof.

Proposition 57 (lower bound). Let 1 ≤ k ≤ q -1 and PRS q (k) be a projective Reed-Solomon code of dimension k + 1 and distance d = q + 1k. Then the distance D of PLift q (m, k) satisfies: D ≥ (d -1)θ m-1,q + 1 where θ m,q = q m+1 -1 q-1 . As a corollary, the respective relative distance δ of PRS q (k) and ∆ of PLift q (m, k) satisfy:

∆ ≥ (1b )δb , where 0 ≤ b ≤ q -1 .

Proof. Let c = ev P m ( f ) ∈ PLift q (m, k) be a minimum-weight codeword, meaning that D = wt(c) = 0. Let also a ∈ P m such that c a = ev a ( f ) = 0. We denote by Λ a the set of projective lines of P m passing through a. It is clear that ( L∈Λ a (L \ {a})) ∪ {a} is a partition of P m , and |Λ a | = θ m-1,q = q m -1 q-1 . Besides we have: Since c |L 0 ∈ PRS q (k) and c |L 0 = 0, its weight is greater than d and we get:

D ≥ (d -1)θ m-1,q + 1 .

Dividing both sides by θ m,q and using θ m,q = qθ m-1,q + 1 finally leads to:

∆ ≥ (q + 1)θ m-1,q θ m,q δ -θ m-1,q -1 θ m,q ≥ (1b )δb , where b = θ m-1,q -1 θ m,q = qb and b is defined in the previous proposition.

Connection with codes based on projective geometry designs

In this section, we simply point out a link between the construction of lifted codes and the codes coming from design theory -we refer to [START_REF] Assmus | Designs and Their Codes[END_REF] as a good reference for links between codes and designs. We focus on projective lifted codes since they are the core of our work, but the upcoming facts also hold for affine lifted codes. Let us consider the highest value of k for which PLift q (m, k) is non-trivial, that is k = q -1. It is well-known that dual codes of projective Reed-Solomon codes are also projective Reed-Solomon codes, and in the setting k = q -1 we have: Lemma 58. The dual code of PRS q (q -1) is the repetition code (1, . . . , 1) = PRS q (0) of length q + 1 over F q .

Hence, a (non full-rank) parity-check matrix H for PLift q (m, k) can be written by listing in rows the incidence vectors of lines and points of the projective space P m . More formally,

H =    1 L 1 . . . 1 L N   
where {L 1 , . . . , L N } denotes the set of all the projective lines of P m , and 1 X is the {0, 1}-vector of length θ m,q = |P m | which is 1 at coordinate i if and only if i ∈ X (for any X ⊂ P m ).

In fact, matrix H is exactly the incidence matrix of the projective geometry design PG 1 (m, q), the block design of points and lines in the projective space P m . Moreover, the vector space over F q spanned by this matrix gives rise to a linear code, which has been thoroughly studied and whose significant properties are given in [START_REF] Assmus | Designs and Their Codes[END_REF]. This code is known as the code spanned by the design PG 1 (m, q), and is denoted by C(PG 1 (m, q)). To sum up we have: Lemma 59. For every prime power q and every m ≥ 2, the projective lifted code PLift q (m, q -1) and the code C(PG 1 (m, q)) spanned by the projective geometry design PG 1 (m, q) are dual codes.

This characterisation allows us to obtain the dimension of projective lifted codes, for which the rank of matrices H has been computed. For instance, it is proved (e.g. in [START_REF] Smith | On the p-rank of the incidence matrix of points and hyperplanes in a finite projective geometry[END_REF]) that the rank over F p t of the design of points and lines in P 2 (F

Conclusion

In this work we introduced lifted projective Reed-Solomon codes as an analogue of the lifting of Reed-Solomon codes studied by Guo, Kopparty and Sudan in [START_REF] Guo | New affine-invariant codes from lifting[END_REF]. We presented local correcting algorithms for these codes, and proved their practicality through explicit bases, information sets and automorphisms. However, similarly to the affine setting, we still lack closed formulae for the dimension of the codes. Future works may then consist in keeping studying the lifting process, for a better understanding of the structure of lifted codes. A generalisation of our work to the lifting of projective Reed-Muller codes or other codes invariant under Proj(F q , t) would also be of interest.

  |L ) = |θ m-1,q | + ∑ L∈Λ a wt(c |L\{a} ) = θ m-1,q + wt(c |P m \{a} ) = θ m-1,q + (D -1) .Therefore, there must exist a line L 0 such thatwt(c |L 0 ) ≤ 1 |Λ a | ∑ L∈Λ a wt(c |L ) = 1 + D -1 θ m-1,q .

  we have ev A m (Poly(D)) = ev A m (Poly(D)).

	Uniqueness comes from the injectivity of ev A m .
	4. Same argument.
	Definition 13 (Degree set). Let C = ev A m (Poly(D)) be an affine (resp. let C = ev P m (Poly(D))
	be a projective) monomial code. Its degree set is the unique A-reduction (resp. P-reduction) of
	D, and is denoted Deg(C).
	By definition, if C is monomial, then we have C = ev(Poly(Deg(C))) where ev ∈ {ev A m , ev P m }
	depending on the context. Moreover, since ev is injective over Poly(Deg(C)), it also holds that:
	dim

Table 1 :

 1 Degree sets of classical monomial codes.

  p t ) is ( 1+p 2 ) For any t ≥ 1 and any prime p, we have:dim PLift p t (2, p t -1) = p 2t + p t -

t + 1. Therefore, Corollary 60. p(p + 1) 2 t .

see https://bitbucket.org/jlavauzelle/lifted_codes

Two points could be clarified here. First, if the linear map (S, L * (S, T)) as rank 1, by definition of Emb A (m) the linear map (T, L * (S, T)) has rank 2. Second, the choice L 0 (S, T) = S can be done since PRS q (k) is invariant under Proj(F q , 1).

Acknowledgements

This work is partially funded by French ANR-15-CE39-0013-01 "Manta". The author would like to thank Françoise Levy-dit-Vehel and Daniel Augot for their valuable comments and advice concerning the presentation of the results.

This work is partially funded by French ANR-15-CE39-0013-01 "Manta".

Information rate

In this section, we emphasize how projective lifted codes surpasses projective Reed-Muller codes in terms of code rate (the local correcting capability being fixed). In Figure 1, we present the rate of PRM q (m, k) and PLift q (m, k) for increasing values of q = 2 e . These codes are comparable since they have same length n = q m+1 -1 q-1 , and same local correction features (locality and error tolerance). In each subfigure of Figure 1, four curves are plotted: blue ones represent projective lifted codes and red ones projective Reed-Muller codes. Plain curves correspond to the minimum error tolerance setting, for which local correction admits no error on the line being picked (see Section 4). To compare, dotted curves correspond to a constant fraction of errors tolerated by the local correcting algorithm. Here, the constant has been arbitrarily fixed to 1/32. PLift q (m = 2, k = q -1) PRM q (m = 2, k = q -1) PLift q (m = 2, k = 15q/16) PRM q (m = 2, k = 15q/16) PLift q (m = 3, k = q -1) PRM q (m = 3, k = q -1) PLift q (m = 3, k = 15q/16) PRM q (m = 3, k = 15q/16) PLift q (m = 4, k = q -1) PRM q (m = 4, k = q -1) PLift q (m = 4, k = 15q/16) PRM q (m = 4, k = 15q/16)

Figure 1: Rate of projective Reed-Muller codes (red) and projective lifted codes (blue).

Automorphisms and (quasi-)cyclicity

In this section, we address the question of the (quasi-)cyclicity of projective lifted codes. More precisely, we prove in Proposition 46 that, under arithmetic constraints between q and m, the code PLift q (m, k) is a quasi-cyclic code up to diagonal isomorphims. This result relies deeply on the fact that PLift q (m, k) is invariant under the action of Proj(F q , m), that has been proved in Lemma 22.

In coding theory, automorphism groups of codes, and a fortiori their permutation groups, are interesting for many reasons. For instance, they can be used for reducing the practical storage cost of the codes (through the storage of their generator or parity-check matrix). Cyclic or quasi-cyclic codes are known to be specifically efficient in that sense.

Definition 42 (Cyclicity, quasi-cyclicity). A code C ⊆ F X q , |X| = n, is said cyclic if Perm(C) contains a cyclic permutation of order n (that is, an n-cycle). It is said quasi-cyclic of index c if Perm(C) contains a permutation which is the product of c different (n/c)-cycles with disjoint orbits. In particular, a cyclic code is a quasi-cyclic code of index 1.

In all what follows, we fix a finite field F q and an integer m ≥ 1, and we define n = |P m | and d = gcd(n, q -1).

Definition 43 (representation of P m ). A tuple u = (u 1 , . . . , u n ) ∈ (F m+1 q ) n represents P m if {u 1 , . . . , u n } = P m , when the u i are taken up to projective equivalence.

Let now φ : F q m+1 → F m+1 q be an isomorphism of F q -vector spaces, and ω be a primitive element of F q m+1 . We define β := ω q-1 . It is clear that β has order n in the multiplicative group F × q m+1 since (q -1)n = q m+1 -1. For every 0 ≤ i < d, we define:

We also define its concatenation

Lemma 44. If n/d and q -1 are coprime, then U represents P m .

Proof. We need to prove that all φ(ω i β dj ) define distinct projective points for 0

Of course, every u = φ(ω i β dj ) ∈ U i is not necessarily represented in a standard form. Denote by P u ∈ F m+1 q its standard form. We have u = w u P u and we can define w = (w u ) u∈U ∈ F n q . Up to a reordering, if n/d and q -1 are coprime, then we have

where P ∈ (F m+1 q

) n denotes the standard evaluation points of P m . Similarly to the definition of ev P m given in the introduction, we can define a map ev Let us now introduce σ : F q m+1 → F q m+1 given by x → βx. We also denote by ψ := φ • σ • φ -1 the associated map over the vector space F m+1 q . It is clear that ψ ∈ Hom(F m+1 q , F m+1 q ), and since σ and φ are bijective, ψ ∈ GL m+1 (F q ). We finally denote by ψ i the i-fold composition of ψ. We then have ψ i (P) = φ(ω i(q-1) φ -1 (P)) for any point P ∈ P m . Proposition 46. If n/d and (q -1) are coprime, then C = w v PLift q (m, k) is quasi-cyclic of index d, through the permutation ψ d ∈ S(U). The orbits of ψ d are given by the subsets U i .

A Useful results

A.1 Combinatorial Nullstellensatz

We recall the Combinatorial Nullstellensatz proved by Alon in [START_REF] Alon | Combinatorial nullstellensatz[END_REF].

Theorem 61 (Combinatorial Nullstellensatz [START_REF] Alon | Combinatorial nullstellensatz[END_REF]). Let F be a field and f ∈ F[X 1 , . . . , X r ]. Assume that deg( f ) = ∑ r i=1 t i and the coefficient of the monomial X t = ∏ r i=1 X t i i in f is non-zero (in other words, assume that t = (t 1 , . . . , t r ) is a degree of f ). Let finally W 1 , . . . , W r ⊆ F such that |W i | > t i for every 1 ≤ i ≤ r.

Then, there exists

A.2 Technical results

Lemma 62. The following equality over bivariate polynomials holds:

Proof. Let α be a primitive element of F q .

∑ β∈F q

A.3 Automorphism groups of (projective) Reed-Muller codes

The automorphism group of affine Reed-Muller codes has been thoroughly studied by Berger and Charpin in [START_REF] Thierry | The automorphism group of Generalized Reed-Muller codes[END_REF] with group algebra techniques. For our needs, we recall below that this group contains the subgroup of affine transformations.

Proposition 63 (Reed-Muller code). Let 0 ≤ k ≤ m(q -1). The automorphism group of the Reed-Muller code C = RM q (m, k) contains the affine permutations Aff(F q , m).

and the total degree of f • T -1

M,b is the same that the total degree of f . Hence ev

) and the proof is completed.

A few years later, Berger also studied the automorphism group of projective Reed-Muller codes [START_REF] Thierry | Automorphism groups of homogeneous and projective Reed-Muller codes[END_REF].

Proposition 64 (projective Reed-Muller code). Let 0 ≤ v ≤ m(q -1). The automorphism group of the projective Reed-Muller code C = PRM q (m, v) contains the projective automorphisms Proj(F q , m).

Proof. Using that ev

), the proof is very similar to the previous one.

B Building the query generator R s

We recall that in our local correction algorithm (Section 4.2) we need a randomized query generator R s which, given a point P ∈ P m and an embedding L ∈ Emb P (m, P), returns s random points of L(P 1 ) such that:

∀Q ∈ P m , Pr L←Emb P (m,P)

The tricky point is that, for a fixed L ∈ Emb P (m, P), we cannot pick the s points uniformly at random on L(P 1 ), otherwise the point P will have a larger probability to be chosen than the other points. We provide a solution to this issue in Algorithm 2. Pick uniformly at U random an (s -1)-subset of L(P 1 ) \ {P}.

C Computation of the dimension of lifted codes

In the following tables are presented some parameters of affine lifted codes, projective lifted codes and projective Reed-Muller codes. We denote respectively by n A , dim(A) and R A the length, dimension and rate of A = Lift q (m, k -1) the value of k given in the first row (q and m being fixed in each table). Similarly, n P , dim(P) and R P represent the length, dimension and rate of P = PLift q (m, k), while dim(PRM) and R PRM denote the dimension and the rate of PRM q (m, k) (its length being n P ).

We choose to compare these codes because, in the local correcting algorithm, they admit approximately the same error-correction capability and locality. Our goal is to show how lifting leads to higher rates, and that projective and affine lifted codes behave similarly.

C.1 Parameters of the kind