come

Comparison and relationship between functional changes of macroinvertebrates and microbial communities in response to resuspension of contaminated sediment

Fanny Colas, Simon Devin, Virginie Archaimbault

Comparison and relationship between functional changes of macroinvertebrates and microbial communities in response to resuspension of contaminated sediment

Fanny Colas1,*, Simon Devin1, & Virginie Archaimbault2 In the European water Framework directive context, long term management and prevention of damages on aquatic ecosystems is needed. Among pressures, historical contamination of sediments from surrounding industry and urbanization pose a serious ecological threat. Therefore, water storages within dams represent a critical system, retaining runoff and particulate-bound contaminants and thereby exposes organisms to elevated concentrations of contaminants. Moreover, when sediment is disturbed ( i.e. sewages or remedial measures), contaminants can be released into the water column and sweep away in downstream systems. Ecological impacts of resuspension of contaminated sediment are low documented, most studies focusing on clogging or breaking up effects on halieutic resources. We determined functional changes in microbial and macroinvertebrates communities in response to resuspension of contaminated sediment (heavy metals and PAH) subsequent to dam's sewage.

We assessed this ecological threat by sampling macroinvertebrates and microbial communities within sediment on five sites presenting different contamination levels. Functional diversity was evaluated through bioecological profiles of macroinvertebrates and with biolog ECOPLATES for microbial communities. Expected results should identify the sensibility of both communities to sediment resuspension. We hypothesize that microbial communities should respond faster than macroinvertebrates assemblages, and could be helpful to explain modifications of ecosystem processes.


R G Novikov
email: novikov@cmap.polytechnique.fr

Absence of exponentially localized solitons for the Novikov-Veselov equation at positive energy

Absence of exponentially localized solitons for the

Novikov-Veselov equation at positive energy

Abstract. In this note we show that the Novikov-Veselov equation (NV-equation) at positive energy (an analog of KdV in 2+1 dimensions) has no exponentially localized solitons in the two-dimensional sense.

1.Introduction and Theorem 1. We consider the following 2+1 -dimensional analog of the KdV equaion ( Novikov-Veselov equation):

∂ t v = 4Re (4∂ 3 z v + ∂ z (vw) -E∂ z w), ∂ z w = -3∂ z v, v = v, E ∈ R, v = v(x, t), w = w(x, t), x = (x 1 , x 2 ) ∈ R 2 , t ∈ R, (1)
where

∂ t = ∂ ∂t , ∂ z = 1 2 ∂ ∂x 1 -i ∂ ∂x 2 , ∂ z = 1 2 ∂ ∂x 1 + i ∂ ∂x 2 . (2)
We assume that v is sufficiently regular and has sufficient decay as |x| → ∞, w is decaying as |x| → ∞.

(3)

Equation ( 1) is contained implicitly in the paper of S.V.Manakov [M] as an equation possessing the following representation , where higher analogs of (1) were also constructed. Note also that the both Kadomtsev-Petviashvili (KP) equations can be obtained from (1) by considering an appropriate limit E → ±∞, see [ZS], [G2].

∂(L -E) ∂t = [L -E, A] + B(L -E) (4) (Manakov L-A-B-triple), where L = -∆ + v(x, t), ∆ = 4∂ z ∂ z , A
For the case when

v(x 1 , x 2 , t), w(x 1 , x 2 , t) are independent of x 2 (5)
equation ( 1) is reduced to

∂ t v = 2∂ 3 x v -12v∂ x v + 6E∂ x v, x ∈ R, t ∈ R. (6)
In terms of u(x, t) such that

v(x, t) = u(-2t, x + 6Et), x ∈ R, t ∈ R, (7)
equation ( 6) takes the standard form of the KdV equation (see [NMPZ]):

∂ t u -6u∂ x u + ∂ 3 x u = 0, x ∈ R, t ∈ R. (8)
It is well-known (see [NMPZ]) that (8) has the soliton solutions

u(x, t) = u κ,ϕ (x -4κ 2 t) = - 2κ 2 ch 2 (κ(x -4κ 2 t -ϕ)) , x ∈ R, t ∈ R, κ ∈]0, +∞[, ϕ ∈ R.
(9) In addition, one can see that

u κ,ϕ ∈ C ∞ (R), ∂ j x u κ,ϕ (x) = O(e -2κ|x| ) as x → ∞, j = 0, 1, 2, 3, . . . (10)
Properties (10) show, in particular, that the solitons of ( 9) are exponentially localized in x.

In the present note we obtain, in particular, the following result:

Theorem 1. Let v, w satisfy (1) for E = E f ix > 0, where v(x, t) = V (x -ct), x ∈ R 2 , c = (c 1 , c 2 ) ∈ R 2 , V ∈ C 3 (R 2 ), ∂ j x V (x) = O(e -α|x| ) f or|x| → ∞, |j| ≤ 3 and some α > 0, (11a)
(where j = (j 1 , j 2 )

∈ (0 ∪ N) 2 , |j| = |j 1 | + |j 2 |, ∂ j x = ∂ j 1 +j 2 ∂x j 1 1 ∂x j 2 2 ), w(•, t) ∈ C(R 2 ), w(x, t) → 0 as |x| → ∞, t ∈ R. ( 11b
)
Then V ≡ 0, v ≡ 0, w ≡ 0.
Theorem 1 shows that equation ( 1) for E > 0 has no nonzero solitons (travel wave solutions) exponentially localized in x in the two-dimensional sense. For E < 0 this result will be given in [KN]. Note also that some other integrable systems in 2+1 dimensions admit exponentially decaying solitons in all directions on the plane, see [BLMP], [FS].

The proof of Theorem 1 is based on Proposition 1 and Proposition 2, see Section 4. In turn, Proposition 2 is based, in particular, on Lemma 1 and Lemma 2.

Lemma 1, Lemma 2 and Proposition 1 are recalled in Section 2. Proposition 2 is given in Section 3. It seems that the result of Proposition 2 (that sufficiently localized travel wave solutions for the NV-equation ( 1) for E = E f ix > 0 have zero scattering amplitude for the two-dimensional Schrödinger equation ( 12)) was not yet formulated in the literature.

2. Lemma 1, Lemma 2 and Proposition 1. Consider the equation

-∆ψ + v(x)ψ = Eψ, x ∈ R 2 , E = E f ix > 0, ( 12
)
where

v(x) = v(x), x ∈ R 2 , (1 + |x|) 2+ε v(x) ∈ L ∞ (R 2 ) (as a function of x ∈ R 2 ) for some ε > 0. ( 13
)
It is known that for any k ∈ R 2 , such that k 2 = E, there exists an unique continuous solution ψ + (x, k) of equation ( 12) with the following asymptotics:

ψ + (x, k) = e ikx -iπ √ 2πe -iπ/4 f (k, |k| x |x| ) e i|k||x| |k||x| + o( 1
|x| ) as |x| → ∞. ( 14
)
This solution describes scattering of incident plane wave e ikx on the potential v. The function f on

M E = {k ∈ R 2 , l ∈ R 2 : k 2 = l 2 = E} (15)
arising in ( 14) is the scattering amplitude for v in the framework of equation ( 12). Under assumptions (13), it is known, in particular, that

f ∈ C(M E ). ( 16
)
Lemma 1. Let v satisfy (13) and v y , y ∈ R 2 , be defined by

v y (x) = v(x -y), x ∈ R 2 . ( 17
)
Then the scattering amplitude f for v and the scattering amplitude f y for v y are related by the formula

f y (k, l) = f (k, l)e iy(k-l) , (k, l) ∈ M E , y = (y 1 , y 2 ) ∈ R 2 . ( 18
)
Lemma 1 follows, for example, from the definition of the scattering amplitude by means of ( 14) and the fact that ψ + (xy, k) solves (12) for v replaced by v y , where k 2 = E.

Lemma 1 was given, for example, in [N3].

Lemma 2. Let v, w satisfy (1), ( 3), where

E = E f ix > 0. Then the scattering amplitude f (•, •, t) for v(•, t) and the scattering amplitude f (•, •, 0) for v(•, 0) are related by f (k, l, t) = f (k, l, 0) exp[2it(k 3 1 -3k 1 k 2 2 -l 3 1 + 3l 1 l 2 2 )], (k, l) ∈ M E , t ∈ R. ( 19
)
Lemma 2 was given for the first time in [N1]. Note that in the framework of Lemma 2 properties (3) can be specified as follows:

v, w ∈ C(R 2 × R) and for each t ∈ R the following properties are fulfiled :

v(•, t) ∈ C 3 (R 2 ), ∂ j x v(x, t) = O(|x| -2-ε ) for |x| → ∞, |j| ≤ 3 and some ε > 0, w(x, t) → 0 for |x| → ∞. (20) Proosition 1. Let v(x) = v(x), e α|x| v(x) ∈ L ∞ (R 2 ) (as a function of x) for some α > 0 (21)
and the scattering amplitude f ≡ 0 on M E for this potential for some

E = E f ix > 0. Then v ≡ 0 in L ∞ (R 2 ).
In the general case the result of Proposition 1 was given for the first time in [GN]. Under the additional assumption that v is sufficiently small (in comparison with E) the result of Proposition 1 was given for the first time in [N2]-[N4].

Transparency of solitons.

In this section we show that sufficiently localized solitons (travel wave solutions) for the NV-equation ( 1) for E = E f ix > 0 have zero scattering amplitude for the two-dimensional Schrödinger equation ( 12).

Proposition 2. Let v, w satisfy (1) for E = E f ix > 0, where v(x, t) = V (x -ct), x ∈ R 2 , c = (c 1 , c 2 ) ∈ R 2 , V ∈ C 3 (R 2 ), ∂ j x V (x) = O(|x| -2-ε ) f or|x| → ∞, |j| ≤ 3 and some ε > 0, (22a) w(•, t) ∈ C(R 2 ), w(x, t) → 0 as |x| → ∞, t ∈ R. ( 22b
)
Then f ≡ 0 on M E , ( 23
)
where f is the scattering amplitude for v(x) = V (x) in the framework of the Schrödinger equation ( 12).

The proof of Proposition 2 consists in the following. We consider

T = {λ ∈ C : |λ| = 1}. ( 24
)
We use that

M E ≈ T × T, E = E f ix > 0, ( 25
)
where diffeomorphism ( 25) is given by the formulas:

λ = k 1 + ik 2 √ E , λ ′ = l 1 + il 2 √ E , (k, l) ∈ M E , (26)
k 1 = √ E 2 λ + 1 λ , k 2 = i √ E 2 1 λ -λ , l 1 = √ E 2 λ ′ + 1 λ ′ , l 2 = i √ E 2 1 λ ′ -λ ′ , (λ, λ ′ ) ∈ T × T. (27)
We use that in the variables λ, λ ′ formulas (18), ( 19) take the form

f y (λ, λ ′ , E) = f (λ, λ ′ , E) exp i 2 √ E λȳ + y λ -λ ′ ȳ - y λ ′ , (28)
where (λ, λ ′ ) ∈ T × T , y is considered as

y = y 1 + iy 2 , f (λ, λ ′ , E, t) = f (λ, λ ′ , E, 0) exp iE 3/2 t λ 3 + 1 λ 3 -(λ ′ ) 3 - 1 λ ′ 3 , (29)
where (λ, λ ′ ) ∈ T × T , t ∈ R.

The assumptions of Proposition 2 and Lemmas 1 and 2 (with ( 18), ( 19) written as ( 28), ( 29)) imply that

f (λ, λ ′ , E) exp i 2 √ Et λc + c λ -λ ′ c - c λ ′ = f (λ, λ ′ , E) exp iE 3/2 t λ 3 + 1 λ 3 -(λ ′ ) 3 - 1 λ ′ 3 (30) for (λ, λ ′ ) ∈ T × T , t ∈ R, where f is the scattering amplitude for v(x, 0) = V (x), c is considered as c = c 1 + ic 2 .
Property ( 16), identity (30) and the fact that λ 3 , λ -3 , λ, λ -1 , 1 are linear independent on each nonempty open subset of T imply (23).

4. Proof of Theorem 1 and final remark. Theorem 1 follows from Proposition 1 and Proposition 2.

Finally, note that the result of Theorem 1 does not hold, in general, without the assumption that V (x) = O(e -α|x| ) as |x| → ∞ for some α > 0: "counter examples" to Theorem 1 with rational bounded V decaying at infinity as O(|x| -2 ) are contained (in fact) in [G1], [G2]. As regards prototypical algebraically decaying solitons for KP1 equation, see [FA].

[ KN] A.V.Kazeykina, R.G.Novikov, Absence of exponentially localized solitons for the Novikov-Veselov equation at negative energy, (in preparation) [ M] S.V.Manakov, The inverse scattering method and two-dimensional evolution equations, Uspekhi Mat.Nauk 31(5), 245-246 (1976) Dokl. 30, 705-708 (1984).

[ ZS] V.E.Zakharov, E.I.Shulman, Integrability of nonlinear systems and perturbation theory / / What is integrability? Berlin: Springer-Verlag, 185-250 (1991)

  and B are suitable differential operators of the third and zero order respectively, [•, •] denotes the commutator. Equation (1) was written in an explicit form by S.P.Novikov and A.P.Veselov in [NV1], [NV2]

  The inverse scattering problem on a fixed energy level for the twodimensional Schrödinger operator, J.Funct.Anal. 103, 409-463 (1992). [NMPZ] S.Novikov, S.V.Manakov, L.P.Pitaevskii, V.Z.Zakharov, Theory of solitons: the inverse scattering method, Springer, 1984. [ NV1] S.P.Novikov, A.P.Veselov, Finite-zone, two-dimensional, potential Schrödinger operators. Explicit formula and evolution equations. Dokl.Akad.Nauk. SSSR 279, 20-24 (1984) (in Russian); English translation: Sov.Math.Dokl. 30, 588-591 (1984). [ NV2] S.P.Novikov, A.P.Veselov, Finite-zone, two-dimensional Schrödinger operators. Potential operators. Dokl.Akad.Nauk. SSSR 279, 784-788 (1984) (in Russian); English translation: Sov.Math.

	(in Russian)
	[ N1] R.G.Novikov, Construction of a two-dimensional Schrödinger operator with a given
	scattering amplitude at fixed energy, Teoret. i Mat Fiz 66(2), 234-240 (1986) (in
	Russian); English translation: Theoret. and Math.Phys. 66, 154-158 (1986).
	[ N2] R.G.Novikov, Reconstruction of a two-dimensional Schrödinger operator from the
	scattering amplitude at fixed energy, Funkt.Anal. i Pril. 20(3), 90-91 (1986) (in
	Russian); English translation: Funct.Anal. and Appl. 20, 246-248 (1986).
	[ N3] R.G.Novikov, Inverse scattering problem for the two-dimensional Schrödinger equation
	at fixed energy and nonlinear equations, PhD Thesis, Moscow State University 1989
	(in Russian)
	[ N4] R.G.Novikov,


Alain Couvreur

INCIDENCE STRUCTURES FROM THE BLOWN-UP PLANE AND LDPC CODES

Keywords: Incidence structures, LDPC codes, algebraic geometry, finite geometry, conics, linear systems of curves, blowing up

In this article, new regular incidence structures are presented. They arise from sets of conics in the affine plane blown-up at its rational points. The LDPC codes given by these incidence matrices are studied. These sparse incidence matrices turn out to be redundant, which means that their number of rows exceeds their rank. Such a feature is absent from random LDPC codes and is in general interesting for the efficiency of iterative decoding. The performance of some codes under iterative decoding is tested. Some of them turn out to perform better than regular Gallager codes having similar rate and row weight.

Introduction

LDPC codes were first discovered by Gallager in [START_REF] Gallager | Low-density parity-check codes[END_REF] in the beginning of the sixties. They regained popularity in the mid-nineties and became a fascinating and highly dynamic research area providing numerous applications. The main reason of this success is that, thanks to iterative decoding, these codes perform very close to the theoretical Shannon limit. For instance, see [START_REF] Richardson | Design of capacity-approaching irregular low-density parity-check codes[END_REF].

Constructions. In the literature, one can distinguish two general approaches to construct LDPC codes. The first one is based on random constructions (for instance see [START_REF] Mackay | Near shannon limit performance of low-density parity-check codes[END_REF]). The second one is based on combinatorial and algebraic methods involving finite fields, block designs, incidence structures and so on. The present article focuses on the second approach.

A well-known construction of LDPC codes from incidence structures is due to Kou, Lin and Fossorier in [START_REF] Kou | Low-density parity-check codes based on finite geometries: a rediscovery and new results[END_REF] who proposed to use the points-lines incidence in affine and projective spaces. Kou et al's approach motivated several other works about the study of LDPC codes arising from incidence structures. Among them (and the list is far from being exhaustive), other codes from points and lines incidence structures in affine or projective spaces are studied in [START_REF] Kamiya | High-rate quasi-cyclic low-density parity-check codes derived from finite affine planes[END_REF] and [START_REF] Xu | Construction of regular and irregular LDPC codes: geometry decomposition and masking[END_REF]. Codes from partial and semi-partial geometries are considered in [START_REF] Johnson | Codes for iterative decoding from partial geometries[END_REF] and [START_REF] Li | Regular LDPC codes from semipartial geometries[END_REF]. Several other well-known incidence structures have also been used to produce good LDPC codes, among them: generalised quadrangles [START_REF] Kim | Small weight codewords in LDPC codes defined by (dual) classical generalized quadrangles[END_REF], generalised polygons [START_REF] Liu | LDPC codes from generalized polygons[END_REF], unital designs [START_REF] Johnson | High-rate LDPC codes from unital designs[END_REF], incidence structures from Hermitian curves [START_REF] Pepe | LDPC codes from the Hermitian curve[END_REF], oval designs [START_REF] Weller | Regular low-density parity-check codes from oval designs[END_REF], flats [START_REF] Tang | Codes on finite geometries[END_REF] and so on.

Redundant matrices. An interesting property of LDPC codes from incidence structures is that they are frequently defined by parity-check matrices whose number of rows exceeds their rank. Such matrices are said to be redundant. Even if it has no influence on the code, a redundant matrix may improve the efficiency of the iterative decoding.

It is worth noting that sparse matrices obtained by random constructions are generically full rank. Of course, it is always possible to add new rows by linear combinations. However, a linear combination of a large number of rows is in general non-sparse. On the other hand, adding linear combinations of a small number of rows does not improve the performance of iterative decoding.

In the case of the codes described in the above-cited references, the parity-check matrix is highly redundant and no row is a linear combination of a small number of other rows. This is particularly interesting for iterative decoding.

New incidence structures. In this article, we introduce new incidence structures obtained from the incidence relations between points and strict transforms of conics on the affine plane blown-up at all of its rational points. Three incidence structures are presented corresponding to three different sets of conics. These three incidence structures are regular (each point is incident to a constant number of blocks and each block is incident to a constant number of points) and any two points of them have at most one block in common. Moreover, the girth of their incidence graph is proved to be either 6 or 8. LDPC Codes. Using these incidence structures, we construct binary LDPC codes and study their parameters. A formula giving their minimum distance is proved and their dimension is discussed. Two conjectures are stated on the dimensions of some of these codes. Using the computer algebra software Magma, the actual dimension of some codes is computed. The information rates of these codes turn out to be close to 1/2 and their parity-check matrices are highly redundant since they are almost square and hence contain twice more parity checks than necessary. Finally, simulations of these codes on the Gaussian channel are done and some codes turn out to perform better than regular Gallager codes having the same rates and row weight.

Outline of the article. The aims of the article are described in Section 1. Some necessary background in algebraic geometry (namely, blow-ups and linear systems of curves) are recalled in Section 2. Section 3 is devoted to plane conics. Some well-known basic results on conics are recalled and some lemmas used in what follows are proved. The context and some conventions are stated in Section 4. In Section 5, three sets of conics are introduced and studied. These three sets are the respective first stones of the constructions of the three new incidence structures presented in the following sections. In Section 6, we introduce the surface B obtained by blowing up all the rational points of the affine plane. We derive three interesting sets of curves on this surface arising from the three sets of conics introduced in the previous section. This yields three new incidence structures defined in Section 7. They are proved to be regular. Explicit formulas for the number of points per block and the number of blocks incident to a point are given. The girth of the incidence graph of these structures is computed and proved to be either 6 or 8. Moreover, the number of minimal cycles is estimated. In Section 8, the LDPC codes from these incidence structures are studied. Some computer aided calculations to get the exact information rate of such codes are presented. Finally, simulations on the Additive White Gaussian Noise channel are presented at the end of the article.

Notations and terminology. In this article, lots of notations and terminologies are introduced and maintained throughout the paper. To help the reader, an index of notations and terminologies is given in Appendix C.

Aims of the present article

The aim of the article is to construct binary LDPC codes which could be efficiently decoded by iterative algorithms. To seek good candidates, we are looking for binary matrices which [START_REF] Fulton | Algebraic curves. Advanced Book Classics[END_REF] are sparse;

(2) have a Tanner graph with few small cycles and in particular no cycles of length 4;

(3) are highly redundant, i.e. whose number of rows exceeds the rank.

In order to construct such matrices, we seek incidence structures having some particular properties. First recall the definition of incidence structure. Definition 1.1 (Incidence structure). An incidence structure I := (P, B, R) consists in three finite nonempty sets. A set of points P, a set of blocks B and a set of relations R ⊆ P × B called incidence relations. A point P ∈ P and a block B ∈ B are said to be incident if and only if (P, B) ∈ R.

An incidence relation can be described by an incidence matrix M , which is a ♯P × ♯B binary matrix such that

M i,j = 1 if (P i , B j ) ∈ R 0 otherwise .
Thus, if we want to use incidence structures to construct codes satisfying the above conditions (1), ( 2), (3), we have to look for incidence structures (1) have few incidence relations, i.e. ♯R ≪ ♯P × ♯B;

(2) have few small cycles in their incidence graph, in particular no cycles of length 4

(which means no pairs of points P, Q being both incident with at least two distinct blocks); (3) whose number of blocks exceeds the rank of the incidence matrix with entries in F 2 .

Some algebraic-geometric tools

The aim of this section is to give the minimal background in algebraic geometry to read this article. Hopefully, the contents of this section are enough to understand what follows. Most of the proofs are omitted since the presented results are well-known. We refer the readers to [START_REF] Fulton | Algebraic curves. Advanced Book Classics[END_REF] and [START_REF] Shafarevich | Basic algebraic geometry[END_REF] for more details.

Most of the results stated in the present section hold for arbitrary fields. However, we chose to state the definitions and the results in the context of the article. Thus, from now on, F q denotes some finite field and F q its algebraic closure.

2.1. Points, curves, tangent lines and intersections.

2.1.1. Affine and projective planes. We denote respectively by A 2 and P 2 the affine and projective plane over F q . Given a system of homogeneous coordinates (X, Y, Z) on P 2 , the projective plane can be obtained as a union of three copies of A 2 corresponding to the subsets {X = 0}, {Y = 0} and {Z = 0}. Such subsets are called affine charts of P 2 .

Points.

A geometric point of A 2 (resp. P 2 ) is a point whose coordinates are in F q . An F q -rational point (or a rational point, when no confusion is possible) is a point whose coordinates are in F q .

2.1.3. Curves. Definition 2.1 (Curve). A plane affine curve C defined over F q (resp. a plane projective curve defined over F q ) is the vanishing locus in A 2 (resp. P 2 ) of a squarefree polynomial f (x, y) ∈ F q [x, y] (resp. a squarefree homogeneous polynomial f ∈ F q [X, Y, Z]). Equivalently, it is the set of geometric points P ∈ A 2 (resp P 2 ) with coordinates (a, b) (resp. (a : b : c)) such that f (a, b) = 0 (resp. f (a, b, c) = 0). The polynomial f is a defining polynomial of the curve. The degree of C is defined as deg(C) := deg(f ).

Remark 2.2. A defining polynomial of a curve over F q is unique up to multiplication by a nonzero element of F q . In what follows we authorise ourselves to say "the defining polynomial of C" even if it is a misuse of language. Definition 2.3 (Reducible and irreducible curves). A curve C is said to be irreducible if its defining polynomial is irreducible. Else it is said to be reducible. Definition 2.4 (Smooth and singular points). Let C be an affine curve, f be its defining polynomial and P be a geometric point of C. The curve is said to be singular at P if the partial derivatives ∂f ∂x and ∂f ∂y vanish at P . Else, the curve C is said to be smooth at P . A curve is said to be singular if it is singular at at least one geometric point. Else it is said to be smooth.

Remark 2.5. The notion of being smooth or singular at a point P is extended to projective curves by reasoning on an affine chart of P 2 containing P . Definition 2.6 (Projective closure). Let C be a plane affine curve defined by the squarefree polynomial f ∈ F q [x, y]. Let f ♯ be the unique homogeneous polynomial in F q [X, Y, Z] such that f ♯ (x, y, 1) = f (x, y) and deg(f ♯ ) = deg(f ). The projective curve of equation f ♯ = 0 is called the projective closure of C. It is obtained by adding to C some points at infinity (see Definition 4.1 further). If P is a geometric point of A 2 (resp. P 2 ) and C, D are two curves which have no common irreducible component (i.e. their defining polynomials are prime to each other), then one can define a nonnegative integer denoted by m P (C, D) and called the intersection multiplicity of C and D at P which satisfies the following properties.

(1) m P (C, D) = 0 if and only if one of the curves C, D does not contain P ;

(2) m P (C, D) = 1 if and only if both curves contain P , are smooth at it and have distinct tangent lines at this point; (3) else, m P (C, D) ≥ 2. In particular, a curve has always intersection multiplicity > 1 at P with one of its tangent lines at this point.

To conclude this subsection let us recall the well-known Bézout's Theorem.

Theorem 2.10 (Bézout's Theorem). Let C, D be two plane projective curves having no common irreducible components. Then the set of geometric points of intersection of C and D is finite and

P ∈C∩D m P (C, D) = deg(C). deg(D).
2.2. Blow-up of a surface at a point. Blowing up a point of a surface is a classical operation in algebraic geometry. It is often used to "desingularise" a curve embedded in a surface or to "regularise" a non regular map at a point. In this section, we briefly present the notion of blow-up and summarise its most useful properties for the following sections. We refer the reader to [START_REF] Fulton | Algebraic curves. Advanced Book Classics[END_REF] Chapter 7 or [START_REF] Shafarevich | Basic algebraic geometry[END_REF] Chapter II.4 for further details.

Definition 2.11 (Blow-up of a surface at one point). Let S be an algebraic surface and P be a smooth point of S. The blow-up of S at P is a surface S together with a surjective map π : S → S satisfying the following properties. (i) The set π -1 ({P }) of pre-images of P by π is a curve E isomorphic to the projective line and called the exceptional divisor. (ii) The restriction π : S \ E → S \ {P } is an isomorphism of varieties.

Proposition 2.12. The blow-up of a surface at a point is unique up to isomorphism. Example 2.13 (Blow-up of the affine plane). Consider the affine plane A 2 with coordinates (x, y) and let P be the origin. Then, the blow-up of A 2 at P is the surface

A 2 := {(x, y, (u : v)) ∈ A 2 × P 1 | xu = yv}.
together with the projection map π :

A 2 → A 2 (x, y, (u : v)) → (x, y) .

One sees easily that the set of pre-images of the origin is isomorphic to P 1 and that any point of A 2 \ {P } has a unique pre-image by π.

Definition 2.14 (Strict transform of a curve). Let S be a smooth surface and P be a point of S. Let π : S → S be the blow-up of S at P and denote by E the corresponding exceptional divisor. Let C be a curve embedded in S and containing P . The decomposition into irreducible components of the algebraic set π -1 (C) is of the form π -1 (C) = E ∪ C, where C does not contain E. The curve C is called the strict transform of C by π. If C does not contain P , its strict transform is defined as C := π -1 (C).

Remark 2.15. The above definition extends naturally to a map obtained by the composition of a finite number of blow-ups.

In the proposition below, we summarise most of the properties of blow-ups needed in what follows.

Proposition 2.16. Let π : S → S be the blow-up of a surface S at a smooth point P .

Denote by E the exceptional divisor.

(i) There is a one-to-one correspondence between tangent lines to S at P and points of the exceptional divisor. In particular, given a tangent line L to S at P , there exists a unique point Q ∈ E such that for all curve C ⊂ S smooth at P and tangent to L at this point, the strict transform C meets E at Q and only at this point. (ii) If two curves C, D meet at P , are smooth at it but have no common tangent line at P , then their strict transforms do not meet in a neighbourhood of the exceptional divisor. (iii) If two curves C, D meet at P , are smooth at it and have a common tangent L (i.e.

their intersection multiplicity at P is greater than or equal to 2), then, their strict transforms meet at the point Q ∈ E corresponding to L. Moreover,

m P (C, D) > m Q ( C, D) ≥ 1,
where m P (. , .) denotes the intersection multiplicity at P .

We conclude this sub-section with the following lemma.

Lemma 2.17. In the context of Proposition 2.16, if C ⊂ S is a curve which is smooth at P or avoids P , then C is isomorphic to C. In particular, C and C have the same number of rational points.

2.3.

Linear automorphisms of the projective plane. Some proofs in this article involve the action of the group PGL(3, F q ) of linear automorphisms of P 2 . It is wellknown that this group acts simply transitively on 4-tuples of rational points of P 2 such that no 3 of them are collinear. More generally we have the following lemma.

Lemma 2.18. The group PGL(3, F q ) acts transitively on 4-tuples of the form:

(1) (P, P , P 3 , P 4 ) where P 3 , P 4 are rational points and P, P are non rational points conjugated under the action of the Frobenius and no 3 of these points are collinear; (2) (P 1 , P 2 , L 1 , L 2 ), where P 1 , P 2 are rational points and L 1 , L 2 are lines defined over F q such that P 1 ∈ L 1 , P 2 ∈ L 2 , P 1 / ∈ L 2 and P 2 / ∈ L 1 ; (3) (P 1 , P 2 , P 3 , L) such that P 1 , P 2 , P 3 are non-collinear rational points and L is a line defined over F q containing P 3 and avoiding P 1 , P 2 ; (4) (P, P , P 3 , L) where P 3 is a rational point and P, P are conjugated under the action of the Frobenius map, the three points are non collinear and L is a line defined over F q containing P 3 and avoiding P, P . In case (1), the action is also free.

The proof of Lemma 2.18 is given in Appendix A.

2.4. Linear Systems of plane projective curves. Linear systems of curves is a central object in this article. Let us recall their definition and some of their properties. For reference, see [START_REF] Fulton | Algebraic curves. Advanced Book Classics[END_REF] Chapter 5 §2. Definition 2.19 (Linear System of curves). A linear system Γ of curves in the affine (resp. projective) plane is a set of (possibly non-reduced) curves linearly parametrised by some projective space P n . That is, there exists a family of linearly independent polynomials F 0 , . . . , F s ∈ F q [x, y] (resp. linearly independent homogeneous polynomials in F q [x, y, z] of the same degree), such that for each element C ∈ Γ, there exists a unique point P = (p 0 : . . . : p s ) ∈ P s such that

p 0 F 0 + • • • + p s F s = 0 is an equation of C.
Remark 2.20 (Non-reduced curves). In §2.1.3, a curve is defined as the vanishing locus of a squarefree polynomial. In the above definition, some elements of the linear set of polynomials may have square factors. The good formalism to take care of this difficulty is that of Grothendieck's schemes (see for instance [START_REF] Hartshorne | Algebraic geometry[END_REF] Chapter II). However, this theory requires a huge background which is useless for what follows.

In the present article, the linear systems are always linear systems of curves of degree 2. The only degenerate cases are polynomial of the form l(x, y) 2 , where l has degree 1. In this case, the corresponding "curve" C is called the double line supported by L (where L is the line of equation l(x, y) = 0). The points of C are those of L. In addition, C is singular at all of its points and any line containing a point P ∈ C is tangent to C at P . Considering l(x, y) 2 as the defining polynomial of C, this property is actually coherent with Definition 2.7 and Proposition 2.9.

Definition 2.21. In the context of Definition 2.19, if P = (p 0 : . . . : p s ) is a geometric point of P s , the curve of equation

p 0 F 0 + • • • + p s F s = 0 is called a geometric element of Γ.
If P is a rational point of P s , then this curve is said to be a rational element of Γ. The rational elements of Γ are the curves of Γ which are defined over F q .

Definition 2.22. The dimension of a linear system is the dimension of its projective space of parameters.

The example of the linear system of conics is studied in the following section.

The linear system of plane conics

This section is devoted to the linear system of plane projective conics and the properties of some of its subsystems. The family of polynomials X 2 , Y 2 , Z 2 , XY, XZ, Y Z generates a linear system of dimension 5 on P 2 called the linear system of plane conics. Its elements are classified in the following proposition. Proposition 3.1 (Classification of plane projective conics). An element of the linear system of conics can be (1) either a smooth irreducible curve, in this situation, it has q + 1 rational points;

(2) or a union of two lines defined over F q ;

(3) or a union of two lines defined over F q 2 and conjugated under the Frobenius map; (4) or a "doubled" line defined over F q (see Remark 2.20).

The two following lemmas are frequently useful in what follows. To state them, the following notation is convenient. Notation 3.2. Let P, Q be two points of the affine (resp. projective) plane. We denote by (P Q) the unique affine (resp. projective) line joining P to Q. Lemma 3.3. Let P 1 , P 2 , P 3 be three non-collinear geometric points of P 2 . Let L be a line containing P 3 and avoiding P 1 and P 2 . The linear system Λ 1 (P 1 , P 2 , P 3 , L) of conics containing P 1 , P 2 , P 3 and tangent to L at P 3 has dimension 1. Moreover its only singular geometric elements are C := (P 1 P 2 ) ∪ L and C ′ := (P 1 P 3 ) ∪ (P 2 P 3 ). Remark 3.4. In the above statement, the curve C ′ := (P 1 P 3 ) ∪ (P 2 P 3 ) is singular at P 3 . Therefore, from Proposition 2.9, any line containing P 3 is tangent to C ′ at P 3 .

Proof of Lemma 3.3. Applying a suitable automorphism in PGL(3, F q ) (use Lemma 2.18 (3) replacing PGL(3, F q ) by PGL(3, F q )), one can assume that P 1 , P 2 , P 3 have respective coordinates (1 : 0 : 0), (0 : 1 : 0), (0 : 0 : 1) and the line L has equation Y = X. Take an equation aX 2 + bXY + cY 2 + dXZ + eY Z + f Z 2 = 0 of a conic.

The vanishing conditions at P 1 , P 2 , P 3 yield respectively a = 0, c = 0 and f = 0. The tangency condition entails d = e. Thus, the resulting linear system is parametrised by P 1 and generated by the polynomials XY and XZ + Y Z. Now, let D be a singular element of Λ 1 (P 1 , P 2 , P 3 , L). From Proposition 3.1, D is a union of two lines. We conclude by noticing that the only pairs of lines satisfying the conditions of the linear system are (P 1 P 2 ) ∪ L and (P 1 P 3 ) ∪ (P 2 P 3 ). Lemma 3.5. Let P 1 , P 2 be two geometric points of P 2 . Let L 1 , L 2 be two lines such that

L 1 ∋ P 1 , L 2 ∋ P 2 , P 1 /
∈ L 2 and P 2 / ∈ L 1 . Then the linear system Λ 2 (P 1 , P 2 , L 1 , L 2 ) of conics containing P 1 , P 2 and being respectively tangent to L 1 , L 2 at these points has dimension 1. Moreover its only singular geometric elements are L 1 ∪ L 2 and the doubled line supported by (P 1 P 2 ) (see Remark 2.20).

Proof. It is almost the same approach as that of the proof of Lemma 3.3 Remark 3.6. In Lemmas 3.3 and 3.5, the linear systems have exactly q -1 smooth F q -rational elements.

Context, notations and terminology

In what follows, the cardinal q of the base field F q is assumed to be greater than or equal to 4. The characteristic of the base field may be odd. We fix a system of coordinates (x, y) for A 2 and a system of homogeneous coordinates (X : Y : Z) on P 2 . Moreover, we identify A 2 as an affine chart of P 2 by the map (x, y) → (x : y : 1).

Caution. In this whole article, we deal with error correcting codes and with algebraic geometry over finite fields. It is worth noting that, although the geometric objects we deal with are defined over finite fields F q with q ≥ 4 and possibly odd, all the codes we construct are binary codes (i.e. defined over F 2 ).

Notation 4.1. The line {Z = 0}, is called "the line at infinity" and denoted by L ∞ . We fix an element α ∈ F q 2 \ F q and denote respectively by P ∞ , Q ∞ , R ∞ and R ∞ the points of respective coordinates:

P ∞ := (0 : 1 : 0) Q ∞ := (1 : 0 : 0) R ∞ := (α : 1 : 0) R ∞ := (α q : 1 : 0).
The points R ∞ and R ∞ are non rational but conjugated under the Frobenius action.

Definition 4.2 (Vertical and horizontal lines). We call vertical (resp. horizontal) lines the affine lines having an equation of the form x = a (resp. y = a), where a ∈ F q . Equivalently, vertical (resp. horizontal) lines are affine lines whose projective closure contain the point P ∞ (resp. Q ∞ ).

We keep Notation 3.2: given two points P, Q we denote by (P Q) the line joining these points. Moreover, we introduce the following notation. Notation 4.3. Let C be a plane curve and P be a smooth point of it, we denote by T P C the tangent line of C at P .

Incidence structures of conics of the affine plane

In the present section, we introduce the sets of conics C 1 (q), C 2 (q) and C 3 (q) which are further used to construct the block set of the incidence structures introduced in §5.5.

5.1.

The problem of small cycles. As said in §1, one of our objectives is to construct incidence structures in which two points are both incident with at most one block. If one considers a set of points of the affine or projective plane together with a set of conics, the corresponding incidence structure does in general not satisfy such expectations. Indeed, from Bézout's Theorem (2.10), two projective conics with no common irreducible components may meet at up to 4 distinct points.

Therefore, in order to construct a "good" incidence structure from conics, i.e. a set of points and a set of blocks such that two points have at most one block in common, we use two ideas.

(1) First, we consider particular sets of affine conics such that the projective closures of any two of them intersect twice at infinity. Such curves meet at most twice in the affine plane. This is the point of the present section. (2) Second, we blow-up the rational points of the affine plane and consider the strict transforms of conics on this blown-up plane. From Proposition 2.16 these strict transforms meet less frequently and provide an incidence structure which turns out satisfy our expectations. This is the point of Section 6.

5.2. Three sets of affine conics. We describe three sets of affine conics respectively denoted by C 1 (q), C 2 (q) and C 3 (q). They are constructed from 3-dimensional linear system of conics having prescribed points or tangents at infinity.

Definition 5.1 (The set C 1 (q)). Let Γ 1 be the linear system of conics containing P ∞ and tangent to L ∞ at P ∞ (see Notation 4.1). We define the set C 1 (q) to be the set affine conics defined over F q whose projective closure is a smooth element of Γ 1 . In affine geometry over the reals, such conics would be a family of parabolas.

Definition 5.2 (The set C 2 (q)). Let Γ 2 be the linear system of projective conics containing the points P ∞ and Q ∞ (see Notation 4.1). We define the set C 2 (q) to be the set of affine conics defined over F q whose projective closure is a smooth element of Γ 2 . In affine geometry over the reals, such conics would be a family of hyperbolas.

Definition 5.3 (The set C 3 (q)). Let Γ 3 be the linear system of projective conics containing the pair (R ∞ , R ∞ ) (see Notation 4.1). We define C 3 (q) to be the set of affine conics defined over F q whose projective closure is a smooth element of Γ 3 . In affine geometry over the reals, such conics would be a family of ellipses.

Remark 5.4. Even if the set of curves C 3 (q) depends on the choice of α, given two choices α, α ′ of elements of F q 2 \ F q , Lemma 2.18 (1) asserts the existence of σ ∈ PGL(3, F q ) sending {(α : 1 : 0), (α q : 1 : 0)} onto {(α ′ : 1 : 0), (α ′ q : 1 : 0)}. Thus, C 3 (q) is unique up to isomorphism and changing the choice of α does not change the isomorphism class of the incidence structure or that of the LDPC code.

Remark 5.5. In the linear systems Γ 1 , Γ 2 and Γ 3 , one finds some reducible conics obtained by the union of the line at infinity together with any other line. The trace of such curves in A 2 is a line and hence a smooth irreducible curve but is not an affine conic. Such elements are not elements of the sets C 1 (q), C 2 (q) or C 3 (q).

Explicit equations.

The following Lemmas give an explicit descriptions of the elements of C 1 (q), C 2 (q) and C 3 (q). Proposition 5.6 (Equation of an element of C 1 (q)). An affine curve is in C 1 (q) if and only if it has an equation of the form

y = ax 2 + bx + c, with a ∈ F q \ {0} and b, c ∈ F q . L ∞ P ∞ Q ∞ P ∞ L ∞ Figure 1.
The linear systems Γ 1 (on the left) and Γ 2 (on the right)

P ∞ P ∞ Q ∞ Figure 2.
The sets C 1 (q) (on the left) and C 2 (q) (on the right)

Proof. Let C ∈ C 1 (q), let C be its projective closure and F (X, Y, Z) = λ 1 X 2 + λ 2 XY + λ 3 XZ +λ 4 Y 2 +λ 5 Y Z +λ 6 Z 2 be a defining polynomial of C. The condition P ∞ = (0 : 1 : 0) ∈ C entails λ 4 = 0. For the tangency condition, consider the affine chart {Y = 0}. In this chart, we get a non homogeneous equation g(x, z) = λ 1 x 2 +λ 2 x+λ 3 xz+λ 5 z+λ 6 z 2 = 0. The point P ∞ has coordinates (0, 0) in this chart. From Definition 2.7, being tangent at P ∞ to L ∞ (which has equation z = 0 in this chart), means that ∂g ∂x (0, 0) = 0 and hence λ 2 = 0. In addition, if λ 5 was zero, then ∂g ∂z would also vanish at P ∞ and C would be singular. Thus, λ 5 = 0 and can be set to -1 without loss of generality

In the affine chart {Z = 0}, the conic has an affine equation of the form f (x, y) = λ 1 x 2 + λ 3 x + λ 6y = 0. Moreover, λ 1 must be nonzero or the corresponding affine curve would be a line and not a conic. There remains to show that under these conditions C is always smooth. It is obviously smooth at P ∞ (that was the reason why we set λ 5 = 0). It is also smooth in the affine chart {Z = 0} since the partial derivative ∂f ∂y ≡ 1 and hence never vanishes in this chart. Proposition 5.7 (Equation of an element of C 2 (q)). An affine curve is in C 2 (q) if and only if it has an equation of the form xy = ax + by + c, with (a, b, c) ∈ F 3 q and c = -ab.

Proof of Proposition 5.7. Let C ∈ C 2 (q) and C and F (X, Y, Z) be as in the proof of Proposition 5.6. The conditions at P ∞ and Q ∞ ∈ C entail respectively λ 4 = 0 and λ 1 = 0. This yields an affine equation for C of the form f (x, y) = λ 2 xy + λ 3 x + λ 5 y + λ 6 = 0. Since C is a conic and not a line, λ 2 = 0 and can bet set to -1 without loss of generality. Then ∂f ∂x = λ 3y and ∂f ∂y = λ 5x. Thus, C is singular if and only if the point (λ 5 , λ 3 ) is in C. One checks easily that this situation happens if and only if λ 6 = -λ 3 λ 5 . Therefore if λ 6 = -λ 3 λ 5 then C is smooth. There remains to check that C is also smooth at P ∞ and Q ∞ . Since C has degree 2 and meets L ∞ at P ∞ and Q ∞ , from Bézout's Theorem, the intersection multiplicities m P∞ (C, L ∞ ) and m Q∞ (C, L ∞ ) are both equal to 1 and hence C cannot be singular at these points (see §2.1.5).

The equation of the elements of C 3 (q) depend on the choice of α. From Remark 5.4, there is no loss of generality to consider an arbitrary choice of α, which is what we do in the two following lemmas.

Proposition 5.8 (Equation of an element of C 3 (q) in odd characteristic). Assume that q is odd. Let β be a non-square element of F q \ {0} and α ∈ F q 2 \ F q such that α 2 = β. For this choice of α, an affine curve is in C 3 (q) if and only if it has an equation of the form

x 2 -βy 2 = ax + by + c, with c = b 2 4β - a 2 4 • Proof. Let C ∈ C 3 (q)
and C and F (X, Y, Z) be as in the proof of Proposition 5.6. The vanishing conditions at R ∞ and R ∞ ∈ C entail λ 1 α 2 + λ 2 α + λ 4 = 0. Since T 2β is the minimal polynomial of α, we have λ 2 = 0 and λ 4 = -βλ 1 . If λ 1 = 0, then C would have an affine equation of the form λ 3 x + λ 5 y + λ 6 = 0 and hence would not be a conic. Therefore, λ 1 is nonzero and can be set to -1 without loss of generality. As in the proof of Lemma 5.7, an argument based on Bézout's Theorem asserts that on these conditions C is smooth at R ∞ and R ∞ . There remains to find under which additional conditions it is smooth in the affine chart {Z = 0}. In this chart, the curve has an equation of the form f (x, y) = λ 3 x + λ 5 y + λ 6 -(x 2βy 2 ). A computation of the partial derivatives of f entails that C is singular if and only if f ( λ 3 2 , -λ 5 2β ) = 0. This leads to the assertion that C is smooth provided

λ 2 3 4 - λ 2 5
4β + λ 6 = 0. Proposition 5.9 (Equation of an element of C 3 (q) in even characteristic). Assume that q is even. Let β be an element of F q \ {0} such that Tr F q 2 /Fq (β) = 0 and α ∈ F q 2 \ F q such that α 2 + α + β = 0. For this choice of α, an affine curve is in C 3 (q) if and only if it has an equation of the form

x 2 + xy + βy 2 = ax + by + c, with c = a 2 + b 2 + ab.
Proof. The proof is similar as that of Proposition 5.8, the conditions R ∞ and R ∞ entail λ 1 = λ 2 and λ 3 = βλ 1 . Moreover, λ 1 = 0 and can be set to 1 without loss of generality. Using Bézout's Theorem, one asserts that C is smooth at the points at infinity.

In the affine chart {Z = 0}, the curve C has an equation of the form f (x, y) = λ 3 x + λ 5 y + λ 6 + (x 2 + x + βy 2 ) and computations on the partial derivatives entail that this curve is smooth provided λ 2 3 + λ 2 5 + λ 3 λ 5 + λ 6 = 0. 5.4. Counting number of elements. Proposition 5.10 (Cardinal of the C i (q)'s). The sets C 1 (q), C 2 (q) and C 3 (q) have q 3 -q 2 elements.

Proof. It is a straightforward consequence of Lemmas 5.6 to 5.9.

Proposition 5.11 (Number of points of an element of C i (q)). Any element of C 1 (q) (resp. C 2 (q), resp. C 3 (q)) has exactly q (resp. q -1, resp q + 1) rational points in A 2 . Proof. By definition, for all C ∈ C 1 (q) (resp. C 2 (q), C 3 (q)) the projective closure C is smooth. Thus, from Proposition 3.1 (1), C has q + 1 rational points. Moreover, it has one (resp. two, resp. zero) prescribed rational point at infinity, this yields the result. 5.5. Incidence relations. Lemma 5.12 (Incidence structures given by the C i (q)'s). Let C, D be a pair of distinct elements of C 1 (q) (resp. of C 2 (q), resp. of C 3 (q)). Then, these two curves meet at 0 or 1 or 2 rational points of A 2 . Moreover, if they have a common tangent at a rational point P of A 2 , then they do not meet at another point of A 2 .

Proof. By definition, any two conics of C 1 (q) (resp. C 2 (q), resp. C 3 (q)) meet at least twice (counted with multiplicities) at infinity. This claim together with Bézout's Theorem yield the result. 5.6. Affine automorphisms. To conclude the present section, we focus on automorphisms of A 2 preserving C 1 (q) (resp. C 2 (q), resp. C 3 (q)). Basically they are the projective automorphisms preserving the pair

(P ∞ , L ∞ ) (resp. (P ∞ , Q ∞ ), resp. R ∞ , R ∞ ).
We have the following lemma.

Lemma 5.13. The group of automorphisms of A 2 preserving C 1 (q) (resp. C 2 (q), resp. C 3 (q)) acts transitively on the pairs (P, L) such that P is a rational point of A 2 and L is a non vertical line containing P (resp. a neither vertical nor horizontal line containing P , resp. a line containing P ).

Proof. It is a consequence of Lemma 2.18.

The blown-up plane

As said in Lemma 5.12, two conics of C i (q) may meet at two distinct points, therefore the incidence structure given by the rational points of A 2 together with the elements of C 1 (q) (resp. C 2 , C 3 (q)) does not satisfies the conditions expected in §1. This is the reason why, we introduce the surface B. Definition 6.1 (The surface B). Let P 1 , . . . , P q 2 be the rational points of the affine plane. The surface B is the surface obtained from A 2 by blowing up all the points P 1 , . . . , P q 2 . The corresponding exceptional divisors are denoted by E P 1 , . . . , E P q 2 and we denote by E the set E := {E P 1 , . . . , E P q 2 }. Remark 6.2. Two distinct exceptional divisors on B are disjoint.

The rational points of B can be interpreted in terms of flags. This is the purpose of the following definition. Definition 6.3 (Flags). We call a flag on A 2 a pair (P, L), where P is a rational point of A 2 , L is a line defined over F q and P ∈ L. Definition 6.4 (Incidence flag/curve). A plane curve C and a flag (P, L) are said to be incident if P ∈ C and L is a tangent to C at P . Lemma 6.5. The rational points of B are in one-to-one correspondence with the flags of A 2 . In particular, B has q 2 (q + 1) rational points.

Proof. It is a straightforward consequence of Proposition 2.16 (i).

The following theorem summaries most of the basic elements needed in the study of the further described incidence structures. Theorem 6.6. Let (P, L) be a flag in the affine plane, then (i) (P, L) is incident with q -1 elements of C 1 (q) if L is not a vertical (see Definition 4.2), else it is tangent to none of them; (ii) (P, L) is incident with q -1 elements of C 2 (q) if L is neither vertical nor horizontal (see Definition 4.2), else it is tangent to none of them; (iii) (P, L) is always incident with q -1 elements of C 3 (q). Proof. Step 1. First suppose that L is vertical, i.e. equal to (P P ∞ ) (see Notation 3.2) and assume that there exists C ∈ C 1 (q) which is tangent to L = (P P ∞ ) at P . Let C be the projective closure of C. By definition, C contains P ∞ . Then, m P (C, L) ≥ 2 and m P∞ (C, L) ≥ 1, which contradicts Bézout's Theorem since deg(C). deg(L) = 2.

Step 2. Suppose that L is non-vertical. Then, the set of conics containing P ∞ and P and which are respectively tangent to L ∞ and L at these points is the linear system Λ 2 (P, P ∞ , L, L ∞ ) (see Lemma 3.5 and Remark 3.6). It has dimension 1, thus has q + 1 elements defined over F q and from Lemma 3.5, they are all smooth but two of them.

One proves (ii) and (iii), by the very same manner using Lemma 3.3 instead of 3.5.

The new incidence structures

In this section we describe three incidence structures obtained from the surface B and the C i (q)'s.

7.1. Description. Definition 7.1. The sets C 1 (q), C 2 (q) and C 3 (q) are the respective sets of strict transforms of the elements of C 1 (q), C 2 (q) and C 3 (q) on B.

Recall that E denotes the set of all exceptional divisors on B. Definition 7.2 (Incidence structure I 1 (q)). We denote by I 1 (q) the incidence structure whose set of points P 1 (q) is the set of rational points of B corresponding to the flags (P, L) of A 2 such that L is not a vertical and whose set of blocks B 1 (q) is C 1 (q) ∪ E. Definition 7.3 (Incidence structure I 2 (q)). We denote by I 2 (q) the incidence structure whose set of points P 2 (q) is the set of rational points of B corresponding to the flags (P, L) of A 2 such that L is neither vertical nor horizontal and whose set of blocks B 2 (q) is C 2 (q) ∪ E. Definition 7.4 (Incidence structure I 3 (q)). We denote by I 3 (q) the incidence structure whose set of points P 3 (q) is the set of all rational points of B and whose set of blocks B 3 (q) is C 3 (q) ∪ E. Remark 7.5 (Why adding the exceptional divisors?). In the above-described incidence structures, one can wonder why we chose to add the exceptional divisors in the block sets. Actually the incidence structures would have been regular without these blocks. However, by adding a negligible number of blocks (q 2 additional blocks in a set containing already q 3 -q 2 blocks), one gets codes with a twice larger minimum distance, see Remark 8.6. (2) Using Lemma 6.5, any rational point of B is represented as a flag (P, L) on A 2 . We allow ourselves the notation "(P, L) ∈ B". In particular, we have (P, L) ∈ E P . (3) From now on, an element of C i (q) is denoted by C, where C is the affine conic whose strict transform is C.

Theorem 7.7. The incidence structures I 1 (q), I 2 (q) and I 3 (q) satisfy (i) ♯B 1 (q) = q 3 and ♯P 1 (q) = q 3 ; (ii) ♯B 2 (q) = q 3 and ♯P 2 (q) = q 2 (q -1);

(iii) ♯B 3 (q) = q 3 and ♯P 3 (q) = q 2 (q + 1).

(iv) any point of I 1 (q) (resp. I 2 (q), resp. I 3 (q)) is incident with exactly q blocks; (v) any block of B 1 (q) (resp. B 2 (q), resp. B 3 (q)) is incident with exactly q (resp. q -1, resp. q + 1) points. (vi) any two distinct points of I 1 (q) (resp. I 2 (q), resp. I 3 (q)) are incident with at most 1 common block.

Proof. From Proposition 5.10, the sets C 1 (q), C 2 (q), C 3 (q) and hence the sets C 1 (q), C 2 (q), C 3 (q) have cardinal q 3q 2 . Since E has cardinal q 2 , this proves that the block sets B i (q) ′ s have cardinal q 3 . From Lemma 6.5, the surface B has q 2 (q + 1) rational points.

To construct P 1 (q) (resp. P 2 (q)) we remove 1 (resp. 2) rational point(s) per exceptional divisor, corresponding to the vertical direction (resp. vertical and horizontal directions).

Consequently, these sets have respectively q 3 and q 2 (q -1) elements. To construct P 3 (q) we take all the rational points of B, thus this set has cardinal q 2 (q + 1). This proves (i), (ii) and (iii).

A point of I 1 (q) (resp. I 2 (q), resp. I 3 (q)) corresponds to a flag (P, L) of A 2 such that L is a non-vertical line (resp. is a neither vertical nor horizontal line, resp. is a line) of A 2 . From Theorem 6.6(i) (resp. (ii), resp. (iii)), such a flag is incident with exactly q -1 conics of C i (q) and hence the corresponding point of B is in q -1 elements of C i (q). In addition, this point also lies in the exceptional divisor E P . Therefore, the point (P, L) ∈ B is incident with q blocks in B 1 (q) (resp. B 2 (q), resp. B 3 (q)). This proves (iv).

The number of points incident to a block of the form C i (q) is a straightforward consequence of Proposition 5.11 together with Lemma 2.17. For the blocks in E, first recall that an exceptional divisor is isomorphic to a projective line and hence has q + 1 rational points. Moreover, to construct P 1 (q) (resp. P 2 (q)) we take all the flags but those of the form (P, L) where L is vertical (resp. either vertical or horizontal). Thus, we remove 1 (resp. 2) rational point to each exceptional divisor. Consequently, any block in B 1 (q) (resp. B 2 (q), resp. B 3 (q)) from E is incident with q (resp. q -1, resp. q + 1) points in P 1 (q) (resp. P 2 (q), resp. P 3 (q)). This proves (v).

Let i ∈ {1, 2, 3}. Let (P, L), (P ′ , L ′ ) be two distinct points of P i (q). First, assume that they both lie in the same exceptional divisor E P of B, i.e. P = P ′ . Then, E P is the only block containing both of them. Indeed, no other exceptional divisor contains them from Remark 6.2. Moreover, by definition, elements of C i (q) are smooth. Therefore, from Proposition 2.16 (i), a curve C ∈ C i (q) meets E at at most one point and hence cannot contain both points (P, L) and (P, L ′ ). Now, suppose that the points (P, L), (P ′ , L ′ ) lie in distinct exceptional divisors (i.e. P = P ′ ). Then, there is at most one element of C i (q) containing both of them. Indeed, assume that there exists two distinct such curves C, D ⊂ C i (q) both containing the points (P, L) and (P ′ , L ′ ). Then, from Proposition 2.16 (iii), the curves C, D both contain the points P, P ′ and meet with multiplicity B a = C a and B b = C b are both incident with (P ab , L ab ), from Proposition 2.16 (iii), the plane curves C a and C b meet at least "twice" at P ab (i.e. have a common tangent line L ab at this point). They also meet at P bc = P ac , which contradicts Lemma 5.12.

Therefore, B a , B b , B c are curves of the form C a , C b and C c and C a , C b (resp. C a , C c , resp. C b , C c ) meet "twice" at P ab (resp. P ac , resp. P bc ) i.e. have a common tangent line L ab (resp L ac , resp. L bc ) at this point. This means that the affine conics C a , C b , C c are in (C3) configuration. Lemma 7.12 (Criterion for the non-existence of (C3) configurations). Let i ∈ {1, 2, 3}. Let (P, L) be an element of P i (q) (i.e. a flag such that L is a non-vertical line, resp. a neither vertical nor horizontal line, resp. a line). If for all C ∈ C i (q) such that P / ∈ C, there exists at most one conic D ∈ C i (q) incident with (P, L) and such that C, D are incident with a common flag (P ′ , L ′ ) ∈ P i (q), then no three elements of C i (q) are in (C3) configuration.

Proof. Assume that there exists a triple C a , C b , C c ∈ C i (q) of conics in (C3) configuration. Let (P ab , L ab ) be the flag such that P ∈ C a ∩ C b and L ab = T P ab C a = T P ab C b . Applying a suitable automorphism of the plane (see Lemma 5.13), one can assume that (P ab , L ab ) = (P, L). By definition of (C3) configurations, P / ∈ C c and there are two distinct curves (namely C a and C b ) incident with (P, L) and having a common flag with C c . This contradicts the assumption of the statement. Proposition 7.13. Let (P, L) be a flag in P i (q) and C be an element of C i (q) such that P / ∈ C. Denote by κ i (q, P, L, C) the maximum number of elements C ′ ∈ C i (q) such that C ′ is incident with (P, L) and C, C ′ are incident with a common flag (P ′ , L ′ ) ∈ P i (q). If q is even, κ 1 (q, P, L, C) = q -2 κ 2 (q, P, L, C) = 1 κ 3 (q, P, L, C) = 1 If q is odd, κ 1 (q, P, L, C) = 1 κ 2 (q, P, L, C) ≤ 2 κ 3 (q, P, L, C) ≤ 4.

Remark 7.14. From Lemma 7.12, if κ(q, P, L, C) ≤ 1 for all P, L, C such that P / ∈ C, then no 3 elements of C i (q) are in (C3) configuration. From Lemma 7.11, such a condition also entails that the incidence graph of I i (q) has no cycles of length 6.

Proof of Proposition 7.13. Step 1. For i = 1. From Lemma 5.13, without loss of generality, one can choose (P, L) such that P = (0, 0) and L = {y = 0}. A curve C ∈ C 1 (q) avoiding P has an equation of the form (see Proposition 5.6):

(C) : y = ax 2 + bx + c, with a = 0 and c = 0.

A curve C t ∈ C 1 (q) incident with (P, L) has an equation of the form (C t ) : y = tx 2 , where t = 0.

A point P of intersection of C and C t has coordinates satisfying both equations. Thus, its x-coordinate satisfies

(1) (a -t)x 2 + bx + c = 0
The curves C and C t have a common tangent at P if they meet with multiplicity 2 at this point. It happens if equation ( 1) has a double root.

• If q is even then (1) has a double root if and only if a = t and b = 0. Therefore, if b = 0, then C shares a common flag with any curve C t , with t = 0 and t = a. Else it does not share a common flag with any of the C t . This yields κ 1 (q, P, L, C) = q -2. • If q is odd then (1) has a double root if and only if a = t and its discriminant vanishes. Since c = 0, it discriminant ∆(t) = b 2 -4(at)c is a polynomial of degree 1 in t which vanishes for one value of t. This entails κ 1 (q, P, L, C) = 1.

Step 2. For i = 2. We choose (P, L) with P = (0, 0) and L = {y = x}. A curve C ∈ C 2 (q) avoiding P has an equation of the form (see Proposition 5.7):

(C) : xy = ax + by + c where c = ab and c = 0.

A curve C t ∈ C 2 (q) incident with (P, L) has an equation of the form (C t ) : xy = t(x + y) where t = 0.

Notice that no point of C t has its x-coordinate equal to t. Thus, from now on one can assume that x = t. The equation of C t can then be re-written as y = xt x-t . Using this substitution in the equation of C, a quick computation gives

(2) (t -a)x 2 + (t(a -b) -c)x + ct = 0
• If q is even then (2) has a double root if and only if a = t and t(a + b) + c = 0. It happens for one value of t if a = b and does not happens if a = b. This yields κ 2 (q, P, L, C) = 1. • If q is odd then (2) has a double root if and only if a = t and if its discriminant vanishes. Its discriminant ∆(t) = (t(ab)c) 2 -4ct(ta) is a polynomial of degree ≤ 2 in t and hence vanishes for at most 2 values of t. This yields κ 2 (q, P, L, C) ≤ 2.

Step 3.a. For i = 3 and q even. We choose (P, L) as in Step 1. Using the same notations as in the previous steps we get If a = t, then after substitutions, one sees that C t meets C at a point of A 2 with multiplicity 2 if and only if the polynomial

(b 2 + (b + β(a + t))(a + t))y 2 + (a + t)(c + bt)y + c 2 + ct(a + t)
has a double root. Since a = t, it happens only if c = bt.

Finally C t and C meet with multiplicity 2 if and only if c = bt. Since c = 0, this is possible for one value of t when b = 0. This yields κ 3 (q, P, L, C) = 1.

Step 3.b. For i = 3 and q odd. We choose (P, L) as in Step The coordinates of a point at the intersection of C c and C t satisfy (at)x + by + c = 0 which can be rewritten as x = c a-t -by a-t . Substituting this relation in the equation of C t and after a quick computation, we get

(b 2 -β 2 )y 2 + (tb(a -t) -2bc)y + c 2 -c(a -t) = 0
The discriminant of this polynomial has degree ≤ 4 in t. Thus, κ 3 (q, P, L, C) ≤ 4.

Remark 7.15. In the above proof, Step 1 for q even entails that for a fixed flag (P, L), there are exactly (q -1) 2 curves C ∈ C 1 (q) avoiding P and for which there exists curves C t ∈ C 1 (q) incident with (P, L) and tangent to C at some point P ∈ A 2 . Moreover, for such a curve C there are exactly q -2 curves C t tangent to C at some P ∈ A 2 . Lemma 7.16 (The structure of 8-cycles). Given a 4-tuple of blocks of B i (q) yielding a cycle of length 8 in the incidence graph of I i (q), the corresponding curves satisfy one of the following configuration.

(i) Two of the blocks are exceptional divisors E P and E Q , with P, Q ∈ A 2 (F q ) and the two other ones are curves C, D ∈ C i (q) such that the corresponding affine plane conics C, D both contain P and Q. (ii) One of the blocks is an exceptional divisor E P and the three other ones are curves C 1 , C 2 and C 3 such that C 1 , C 2 ∋ P and C 3 is incident with a common flag (P 13 , L 13 ) ∈ P i (q) with C 1 and to another common one (P 23 , L 23 ) ∈ P i (q) with C 2 . (iii) None of the blocks are exceptional divisors, they are curves C 1 , . . . , C 4 . Moreover, there are 4 flags (P 13 , L 13 ), (P 14 , L 14 ), (P 23 , L 23 ), (P 24 , L 24 ) ∈ P i (q) such that the P ij 's are distinct and C i , C j are both incident with (P ij , L ij ).

These three possible configurations are represented in figure 4.

Proof. Since two distinct exceptional divisors on B have no common point (see Remark 6.2), a 4-tuple of blocks yielding an 8-cycle involves at most two exceptional divisors. The remaining curves are strict transforms of conics in C i (q). Verifications are left to the reader that these conics should satisfy these conditions. Now, using Lemmas 7.11, 7.12, 7.16 and Proposition 7.13, we can proceed to the proof of Theorem 7.8. of Theorem 7.8. Step 1. Theorem 7.7 (vi) entails the non-existence of cycles of length 4 in the incidence graph. From Remark 7.9, the girth is even and hence γ(i, q) ≥ 6 for all pairs (i, q).

Step 2. Cycles of length 8 always exist in the incidence graph: obviously, the case (i) of Lemma 7.16 always happens. Thus, γ(i, q) ≤ 8 for all i and all q.

Step 3. Proposition 7.13 together with Remark 7.14 entail that the incidence graph of I i (q) has no 6-cycles if q odd and i = 1 and if q even and i = 2 or 3. Therefore, in these situations, γ(i, q) = 8.

Step 4. For the remaining situations, the girth of the incidence graph is actually 6. To prove it, we explicit triples of elements of C i which are in (C3) configuration. In these three examples, the curves are denoted by C a , C b , C c and the flags by (P ab , L ab ), (P ac , L ac ) and (P bc , L bc ). Verifications are left to the reader.

Step 4.1. A triple of elements of C 1 (q) with q even in (C3) configuration. Let q be even. By assumption, q ≥ 4 (see §4). Then, there exists η ∈ F q such that η = 0 and η = 1. A (C3) configuration is given by Step 4.2. A triple of elements of C 2 (q) with q odd in (C3) configuration. Step 4.3. A triple of elements of C 3 (q) with q odd in (C3) configuration.

(C a ) : y = x 2 (C b ) : y = ηx 2 (C c ) : y = (η + 1)x 2 + 1 ; P ab = (0, 0) P ac = (η -1/2 , η -1 ) P bc = (1, η) ; L ab : y = 0 L ac : y = η -1 L bc : y = η. C D Q P E Q D C E P π P C 1 C 2 C 3 E P C 1 C 2 C 3 π C 1 C 2 C 3 C 4 C 1 C 4 C 3 C 2 π
(C a ) : x 2 -βy 2 = x (C b ) : x 2 -βy 2 = -x (C c ) : x 2 -βy 2 = 1, ; P ab = (0, 0) P ac = (1, 0) P bc = (-1, 0) ; L ab : y = 0 L ac : y = 1 L bc : y = -1.
7.4. Number of small cycles. In the previous sub-section it is proved that the incidence graph of I i (q) has either girth 6 or girth 8. In both cases we compute or bound above the number of cycles of minimum length.

Theorem 7.17 (Number of cycles of length 6). For incidence structures I i (q) whose incidence graph has girth 6, let N 6 (i, q) be the number of 6-cycles. We have

N 6 (i, q)    = q 3 (q -1) 3 (q -2)/6
if i = 1 and q is even ≤ q 2 (q -1)(q 3q 2q)/3 if i = 2 and q is odd ≤ 2q 4 (q + 1)(q -2) if i = 3 and q is odd .

In particular we always have N 6 (i, q) = O(q 6 ).

Proof. From Lemma 7.11, the number of 6-cycles equals the number of non-ordered triples of conics in (C3) configuration. For that, we compute the number of ordered such triples and divide this number by 6.

Step 1. For C 1 (q), with q even. We choose a flag (P, L) and look for the number of ordered triples C a , C b , C c in (C3) configuration and such that C a , C b are both incident with (P, L). Remark 7.15 entails that there are (q -1) 2 choices for C c for which one can find C a , C b both incident with (P, L) and such that C a , C b , C c are in (C3) configuration. We have:

• (q -1) 2 choices for C c ;

• (q -1) choices for C a ;

• (q -2) choices for C b . Since we also have ♯I 1 (q) = q 3 choices for (P, L), this yields q 3 (q -1) 3 (q -2) ordered triples of conics in (C3) configuration. Thus, there are q 3 (q -1) 3 (q -2)/6 non-ordered triples.

Step 2. For C 2 (q) with q odd. As in the previous step, we choose a flag (P, L) and look for triples C a , C b , C c in (C3) configuration such that C a , C b are both incident with (P, L). We choose an arbitrary curve C c ∈ C 2 (q) avoiding P . Without loss of generality, one can assume that P = (0, 0) and hence C c has an equation of the form xy = ax + by + c with c = ab and c = 0. This yields q 3q 2q possible choices for C c . Moreover, from Proposition 7.13, there are at most 2 curves in C 2 (q) which are incident with (P, L) and have a common flag with C c . Thus, we have

• ♯P 2 (q) = q 2 (q -1) choices for (P, L); • q 3q 2q choices for C c ;

• at most 2 choices for C a ;

• at most 1 choice for C b . This yields at most 2q 2 (q -1)(q 2q 2q) ordered triples and hence at most q 2 (q -1)(q 3q 2q)/3 non-ordered triples.

Step 3. For C 3 (q) with q odd. The approach is almost the same as that of the previous step. Choose (P, L) and C c avoiding P . Without loss of generality, one can assume that P = (0, 0) and C c has an equation of the form x 2βy 2 = ax + by + c with c = 0 and

c = b 2 4β -a 2 4 .
Since β is a non-square in F q , the expression b 2 4β -a 2 4 is nonzero of all (a, b). This entails that there are exactly q 2 (q -2) possible choices for C c .

As previously, one applies Proposition 7.13. We have • ♯P 3 (q) = q 2 (q + 1) choices for (P, L);

• q 2 (q -2) choices for C c ;

• at most 4 choices for C a ;

• at most 3 choices for C b . This yields at most 12q 4 (q + 1)(q -2) ordered triples and hence at most 2q 4 (q + 1)(q -2) non-ordered triples.

To conclude the present section we state a result on the number of 8-cycles. Such a result can be obtained by counting the number of configurations describes in Lemma 7. [START_REF] Weller | Regular low-density parity-check codes from oval designs[END_REF]. By counting one can obtain upper bounds on the number of these cycles. However the obtained formulas are pretty rough. We thus chose to give only the asymptotic behaviour of this number of 8-cycles. Notice that the following theorem holds for even when the incidence graph has girth 6.

Theorem 7.18 (Number of cycles of length 8). The number N 8 (i, q) of 8-cycles of I i (q) satisfies N 8 (i, q) = O(q 8 ).

Proof. We have to count the number of configurations described in Lemma 7.16 (see also Figure 4).

Configurations (i).

There are q 2 rational points in A 2 . Thus, there are O(q 4 ) choices for P, Q. There are O(q) conics in C i (q) containing P and Q. This yields O(q 2 ) choices for C, D. Finally, we have O(q 6 ) configurations (i).

Configurations (ii).

There are O(q 3 ) choices for P and O(q 3 ) choices for C 3 (basically, "almost all" elements of C i (q) avoid P ). Thus, we have O(q 6 ) choices for the pair (P, C 3 ). Choose two lines L 1 , L 2 containing P (O(q 2 ) choices), from Proposition 7.13 there is at most 1 element in C i (q) incident with (P, L 1 ) (resp. (P, L 2 )) and sharing a common flag with C 3 . Thus, we have O(q 2 ) choices for C 1 , C 2 and hence O(q 8 ) configurations (ii).

Configurations (iii). We have O(q 6 ) choices for C 1 , C 3 . Choose two points P, Q of C 1 (O(q 2 ) choices). From Proposition 7.13, there is at most one curve in C i (q) which is incident with (P, T P C 1 ) (resp. (Q, T Q C 1 )). Thus there are O(q 8 ) configurations (iii).

LDPC codes from the incidence structures

In this section, we construct and study LDPC codes from the previously defined incidence structures. Recall that, even if the incidence structures are constructed using geometry over an arbitrary finite field, the LDPC codes we construct are binary.

Codes are defined in §8.1. The weights and minimum distance of these codes are studied in §8.2. The dimension of such codes is discussed in §8.3.

8.1. The codes. Definition 8.1. Let i ∈ {1, 2, 3}. The code C(i, q) is the null space of the incidence matrix of I i (q) having coefficients in F 2 .

Theorem 8.2. The codes C(1, q) (resp. C(2, q), resp. C(3, q)) have a parity-check matrix of size q 3 × q 3 (resp. q 3 × q 2 (q -1) resp. q 3 × q 2 (q + 1)). Moreover, these matrices are sparse and regular: each row has weight q (resp. q -1, resp. q + 1) and each column has weight q.

Proof. It is a straightforward consequence of Theorem 7.7.

As a straightforward consequence of this Theorem, we obtain the length of these codes.

Corollary 8.3 (Length of C(i, q)). The length n(i, q) of the code C(i, q) is n(i, q) =    q 3 if i = 1; q 2 (q -1) if i = 2; q 2 (q + 1) if i = 3. 8.2. Weights and minimum distances. Lemma 8.4. For all pair (i, q), the codewords of C(i, q) have even weight.

Proof. Consider the incidence matrix H(i, q) of I i (q). A row of this matrix, is a parity check given by some block in B i (q). Consider the q 2 rows corresponding to the exceptional divisors. Any two of these rows have disjoint supports (Remark 6.2) and their sum is the vector (1, . . . , 1). It is an elementary exercise to prove that in a code whose parity-check matrix has a set of rows satisfying this property, the codewords always have even weight.

Theorem 8.5 (Minimum distance of C(i, q)). minimum distance d of C(i, q) is d = 2q.

Caution.

In what follows, we deal with codewords of C(i, q). Since we deal with binary codes (even if they arise from geometries over odd characteristic fields), a codeword of C(i, q) can be regarded as a set of flags {(P 1 , L 1 ), . . . , (P s , L s )} in P i (q) such that the number of such flags incident with any block in B i (q) is even. From now on, we frequently use the representation of codewords as sets of flags in P i (q). Therefore, we allow ourselves to write (P, L) ∈ c when c is a codeword in C(i, q) and its coordinate corresponding to (P, L) equals 1.

Proof of d ≥ 2q. Let c ∈ C(i, q) be a nonzero codeword. Let (P, L) ∈ P i (q) be a flag such that (P, L) ∈ c (regarding c as a subset of P i (q), see Caution above). Because of the block corresponding to the exceptional divisor E P above P , there is another line L ′ such that (P, L ′ ) ∈ P i (q) and (P, L ′ ) ∈ c.

Let C 1 , . . . , C q-1 (resp. C ′ 1 , . . . , C ′ q-1 ) be the conics in C i (q) which are incident with (P, L) (resp. (P, L ′ )). An example is represented in Figure 5 L Using Lemma 5.12, one sees that any two of these 2q-2 curves cannot share a common flag distinct from (P, L) or (P, L ′ ). Indeed, two curves of the form C i , C j (resp.

P L ′ C q-1 C ′ 1 C ′ q-1 C 1 . . . . . .
C ′ i , C ′ j )
have a common flag (P, L) (resp. (P, L ′ )) and therefore do not meet at another point in A 2 . Two curves C i , C ′ j meet with multiplicity 1 at P and hence cannot meet with multiplicity > 1 at another point of A 2 .

Consequently, to satisfy all the parity checks, for all i there is at least one flag (P i , L i ) (resp. P ′ i , L ′ i ) incident with C i (resp. C ′ i ), distinct from (P, L) and (P ′ , L ′ ) and contained in c. Moreover, the previous claim on the non incidence relations between the C i 's and C ′ i 's entails that the flags (P 1 , L 1 ), . . . , (P q-1 , L q-1 ), (P ′ 1 , L ′ 1 ), . . . , (P ′ q-1 , L ′ q-1 ) are distinct to each other. This yields w(c) ≥ ♯ (P, L), (P, L ′ ), (P 1 , L 1 ), . . . , (P q-1 , L q-1 ), (P ′ 1 , L ′ 1 ), . . . , (P ′ q-1 , L ′ q-1 ) = 2q, where w(c) denotes the Hamming weight of c.

There remains to prove the existence of codewords of weight 2q. Their existence and the construction of some of them is given in Appendix B.

Remark 8.6. As noticed in Remark 7.5, if the exceptional divisors were not in the block sets of the incidence structure, then the minimum distance would be only ≥ q. It can be proved be reproducing the reasoning of the above proof. Using the end of the proof in Appendix B, one can prove that the minimum distance would be actually q in that case. 8.3. Dimension. Unfortunately, we did not find formulas giving the dimension of the code C(i, q) as a function of q. The dimension of the C(i, q)'s have been computed using Magma for all prime power q ≤ 32 (see tables 1 to 6 pages 24 to 26). It turns out that the behaviour of these dimensions as a function of q depends on the parity of q. This claim is not surprising, we see for instance in Theorem 7.8, that the girth of their Tanner graph already depends on the parity of q. Therefore the parity of q has important consequences on the incidence structures.

Remark 8.7. It is worth noting that the length of C(i, q) is of the form q 3 + O(q 2 ). Therefore, if the dimension of the code for q odd (resp. for q even) is a polynomial in q, then this polynomial has degree at most 3 and leading coefficient between 0 and 1.

Using the tables in §8.5 and Lagrange's interpolation, we get the following conjectures.

1. If q is odd, then dim C(1, q) = 1 2 q 3 -q 2 + 3 2 q -1 dim C(2, q) = 1 2 q 3 - 5 2 q 2 + 9 2 q - 7 2 •
The conjecture is satisfied for all odd prime power 5 ≤ q ≤ 31.

A more surprising fact on these dimensions is the following one.

Lemma 8.8. The dimension of C(3, q) for q odd is not a polynomial in q.

Proof. From remark 8.7, if the dimension is a polynomial, this polynomial has degree at most 3. Using Table 5 page 25 and interpolating the values for q = 5, 7, 9, 11, we obtain the polynomial 23 48 q 3 -15 16 q 2 -215 48 q + 239 16 . It is easy to check that this polynomial does not give the other computed values of the dimension.

Looking at the calculations presented in §8.5, the codes C(i, q) seem have asymptotic information rate 1/2 when q is odd. This rate seems to be higher when q is even. Since the constructed parity-check matrices are almost square, they are redundant. Mostly, they have about twice more rows than necessary. 8.4. Cycles of the Tanner graph. An important criterion for the efficiency of LDPC codes is the girth of their Tanner graph and the number of small cycles. It is proved in Theorem 7.8 that the girth of their Tanner graphs are 6 or 8. Moreover, Theorem 7.17 asserts that if the girth is 6, then the number of small cycles is O(q 6 ) and hence O(n 2 ), where n denotes the length of the code. Theorem 7.18 asserts that the number of cycles of length 8 is O(q 8 ) and hence O(n 8/3 ). 8.5. Calculations. We developed Magma programs producing the codes C(i, q). These programs are available on http://www.lix.polytechnique.fr/Labo/Alain.Couvreur/ doc_rech/LDPC_codes.tar.gz. Thanks to them we are able to calculate by computer the dimensions of the C(i, q)'s for q ≤ 32. As seen in §7.3, the parity of q has an important influence on the incidence structure, and hence on the codes. Therefore, we present in distinct tables the cases q even and q odd. All the bit error rates above 10 -4 have been obtained after between 10 4 and 10 5 random tests. For Bit error rates under 10 -4 , between 10 6 and 10 7 random tests are done. The number of iterations of the iterative decoding algorithm is set to 50 for the simulations presented in Figure 6 and to 500 for the simulations in Lemma B.1. For all u ∈ F 2 q , all P ∈ A 2 (F q ) and all a ∈ F q \ {0}, the sets C i (q) are globally preserved by the translation of vector u and by the homotecy centred at P with ratio a. These affine automorphisms induce therefore automorphisms of I i (q). Proof. It is sufficient to prove that these automorphisms of A 2 prolongated and regarded as automorphisms of P 2 leave invariant any point at infinity. Since translations and homothecies send a line onto a parallel one, they fix any point at infinity. Proposition B.3. Let i ∈ {1, 2, 3}. Let L 0 , L be two lines in A 2 meeting at P ∈ A 2 (F q ). If i = 1, then L, L 0 are assumed to be non vertical; if i = 2, then they are assumed to be neither vertical nor horizontal. Let C ∈ C i (q) be a curve incident with (P, L) and Q be the other point of intersection of C with L 0 . Finally, denote by M the line M := T Q C. Proof. First, notice that C is the unique element of C i (q) incident with (P, L) and containing Q. Indeed, the existence of two such distinct curves C, D would yield a contradiction with Lemma 5.12, since C, D would meet at least once at Q and twice at P . Let C ′ ∈ C i (q) be another curve incident with (P, L) and Q ′ be the other point of intersection of C ′ with L 0 . By the same way C ′ is the unique element of C i (q) incident with (P, L) and containing Q ′ . Let h be the homotecy of centre P sending Q on Q ′ . By uniqueness, h sends C onto C ′ and T Q ′ C ′ = h(T Q C) = M , thus T Q C ′ ∼ M . Therefore [M ] does not depend on the choice of C. Afterwards, let P ′ ∈ L 0 be another point and L ′ ∼ L be a line containing P ′ . Let t be the translation sending P on P ′ , this map sends C onto a curve incident with (P ′ , L ′ ). The curve t(C) meets L 0 at t(Q) and its tangent at this point is parallel to M . This shows that [M ] does not depend on P .

Finally, to prove that this correspondence is an involution, it is sufficient to show that [M ] is sent onto [L], which is obvious since C is incident with (Q, M ), meets L 0 at another point P and has L a tangent at this point, thus ψ See figure 10 for an illustration. The line L 0 has q rational points in A2 and the above word is given by 2 flags per point in L 0 . Thus, it has weight 2q. There remain to show that it is a codeword of C(i, q), which means that any block of B i (q) is always incident with an even number of flags in c.

(1) Let E P be an exceptional divisor. If P / ∈ L 0 then none flag in C is incident with E P . Else, exactly two of them are, namely (P, L P ) and (P, M P ).

(2) Let C ∈ C i (q), if C is incident with a flag (P, L P ) in c, then C meets L 0 at another point Q. If the involution ψ [L 0 ] is constant, then T Q C ∼ L P and hence

T Q C = L Q , else T Q C = M Q . In

7. 2 .

 2 Basic properties of the incidence structures. Notation 7.6. (1) In what follows, any element of E, (i.e. any exceptional divisor on B) is denoted by E P , where P is the corresponding blown-up point (i.e. the image of E P by the canonical map B → A 2 ).

(C) : x 2 +

 2 xy + βy 2 = ax + by + c, where, c = 0 and c = a 2 + b 2 + ab. and (C t ) : x 2 + xy + βy 2 = tx, where t = 0. If a = t and b = 0, then the polynomial system has no solution since c = 0. Else if a = t and b = 0, then after substitution we see that C t is tangent to C at some point if and only if the polynomial b 2 x 2 + b(c + bt)x + βc 2 has a double root. It happens only if c = bt.

  1, and get (C) : x 2βy 2 = ax + by + c, with c = 0 and c = ) : x 2βy 2 = tx where t = 0.

Figure 4 .

 4 Figure 4. The three possible configurations of curves yielding 8-cycles. Left hand pictures represent the curves in A 2 and right hand ones the corresponding curves in B (π denotes the Blow-up map).

(

  C a ) : xy = x + y (C b ) : xy = -xy (C c ) : xy = 4 ; P ab = (0, 0) P ac = (2, 2) P bc = (-2, -2) ; L ab : y = -x L ac : y = -x + 4 L bc : y = -x -4.

Figure 5 .

 5 Figure 5. The curves C 1 , . . . , C q-1 and C ′ 1 , . . . , C ′ q-1

Figures 7 and 8

 8

  .

Figure 7 .

 7 Figure 7. Decoding performances of the code C(1, 13) (with parameters [2197, 948]) and three Gallager codes, with respective row weights 12, 13 and 14 and parameters [2196, 921], [2197, 1020] and [2198, 949].

Figure 8 .

 8 Figure 8. Decoding performances of the code C(2, 16) (with parameters [3840, 2001]) and two Gallager codes, with respective row weights 15 and 16 and parameters [3840, 2041] and [3840, 1927].

Notation B. 2 (

 2 Parallel lines). If two lines L, L ′ ∈ A 2 are parallel (i.e. they do not meet in A 2 ) we write L ∼ L ′ . Moreover the class of a line L modulo ∼ is denoted by [L]. The set of such classes is isomorphic to P 1 . The class of vertical lines is denoted by [V ] and that of horizontal lines by [H].

  Then, (i) the class [M ] modulo ∼ (see Notation B.2) depends only on [L] and [L 0 ] and neither on P , nor on C.(ii) the map [L] → [M ] is an involution ψ [L 0 ] of P 1 \ {[V ], [L 0 ]} if i = 1, of P 1 \ {[V ], [H], [L 0 ]} if i = 2 and of P 1 \ {[L 0 ]} if i = 3. See figure9for an illustration.

Figure 9 .

 9 Figure 9. The involution ψ [L 0 ] . In this picture, L ∼ L ′ and ψ [L 0 ] ([L]) = [M ] = [M ′ ].

Figure 10 .

 10 Figure 10. The codeword c.

  [L 0 ] ([L]) = [M ].Construction of minimum weight codewords. Using Proposition B.3, one can prove the existence of codewords of weight 2q in C(i, q) and construct them explicitly. Choose a line L 0 whose class inP 1 is distinct from [V ] if i = 1 and distinct from [V ], [H] if i = 2. The involution ψ [L 0 ] introduced in Proposition B.3 is either constant 1 or permutes at least two distinct classes [L], [M ]. If it is constant, then choose an arbitrary pair of classes [L], [M ], else choose [L] = [M ] such that ψ [L 0 ] ([L]) = [M ]. Recall that words in F n 2 can be represented by sets of flags (see Caution page 22). Consider the word in F n 2 defined by c := {(P, L P ) : P ∈ L 0 , L P ∋ P and L P ∼ L}∪ {(P, M P ) : P ∈ L 0 , M P ∋ P and M P ∼ M }.

  Definition 2.7 (Tangent line). Let C be a plane affine curve. Let P be a geometric point of C and L be a line of A 2 containing P . The line L is said to be a tangent to C Intersection multiplicity. The notion of intersection multiplicity is pretty easy to feel but heavy to define properly. Therefore, we do not state its definition for which we refer the reader to[START_REF] Fulton | Algebraic curves. Advanced Book Classics[END_REF] Chapter 3 §3. However, let us give some basic properties of this mathematical function which are enough for what follows.

	at P if	a	∂f ∂x	(P ) + b	∂f ∂y	(P ) = 0

2.1.4. Tangent lines. for all director vectors (a, b) of L. Remark 2.8. As in Remark 2.5, the notion of tangent line can be extent to projective curves by considering affine charts. Proposition 2.9. A plane curve is smooth at a point P if and only if it has a unique tangent line at this point. A plane curve C is singular at P if and only if any line containing P is a tangent to C at P . 2.1.5.

Table 1 .

 1 The codes C(1, q) for q odd.

	q Length Number of Minimum Girth Dimension	Rate
			Parity checks distance			(approx.)
	5	125	125	10	8	44	0,35
	7	343	343	14	8	132	0,38
	9	729	729	18	8	296	0,41
	11 1331	1331	22	8	560	0,42
	13 2197	2197	26	8	948	0,43
	25 15625	15625	50	8	7224	0,46
	31 29791	29791	62	8	13980	0,47
	q Length Number of Minimum Girth Dimension	Rate
			Parity checks distance			(approx.)
	4	64	64	8	6	23	0,36
	8	512	512	16	6	259	0,51
	16 4096	4096	32	6	2615	0,63
	32 32768	32768	64	6	24151	0,74

Table 2 .

 2 The codes C(1, q) for q even.

	q Length Number of Minimum Girth Dimension	Rate
			Parity checks distance			(approx.)
	5	100	125	10	6	19	0,19
	7	294	343	14	6	77	0,22
	9	648	729	18	6	199	0,31
	11 1210	1331	22	6	409	0,34
	13 2028	2197	26	6	731	0,36
	25 15000	15625	50	6	6359	0,42
	31 28830	29791	62	6	12629	0,44

Table 3 .

 3 The codes C(2, q) for q odd.

	q Length Number of Minimum Girth Dimension	Rate
			Parity checks distance			(approx.)
	4	48	64	8	8	11	0,23
	8	448	512	16	8	176	0,39
	16 3840	4096	32	8	2001	0,52
	32 31744	32768	64	8	19594	0,62

Table 4 .

 4 The codes C(2, q) for q even.

	q Length Number of Minimum Girth Dimension	Rate
			Parity checks distance			(approx.)
	5	150	125	10	6	29	0,19
	7	392	343		6	102	0,26
	9	810	729	18	6	248	0,31
	11 1452	1331	22	6	490	0,34
	13 2366	2197	26	6	852	0,36
	17 5202	4913	34	6	2032	0,39
	25 16250	15625	50	6	7513	0,46
	31 30752	29791	62	6	14431	0,47

Table 5 .

 5 The codes C(3, q) for q odd.

		0 10						BPSK
								Gal(576,9,6)
		-1 10						Gal(580,10,6) C(3,8)
	Bit Error Rate	10 -4 10 -3 -2 10
		10 -5
		-6 10	0	1	2	3	4	5	6	7
						E b /N 0 (dB)

Figure 6. Decoding performances of the code C(3, 8) (with parameters [576, 233]) and two Gallager codes, with respective row weights 9 and 10 and parameters [576, 197] and [580, 237].

Table 6 .

 6 The codes C(3, q) for q even. 8.6. Simulations on the Gaussian Channel. Using the function LDPCSimulate of Magma, we have simulated the performances of some codes C(i, q) on the Additive White Gaussian Noise Channel. We compare these results with the performances of regular Gallager codes having nearly the same rate and row weight. These results are presented in Figures6, 7 and 8. The performances of our codes turn out to beat those of Gallager codes having similar length, rate and row weight.

8.6.1. Details of the simulations.

  both cases, if C is incident with an element of c, then it is always incident with a second one. This concludes the proof.Appendix C. Index of notations and terminologies m P (C, D) §2.1.5 The line (P Q) Nota 3.2 Λ 1 (P 1 , P 2 , P 3 , L)Lem 3.3 Λ 2 (P 1 , P 2 , L 1 , L 2 ) Lem 3.5 L ∞ , α, P ∞ , Q ∞ , R ∞ , R ∞ , Γ 2 , Γ 3Defs 5.1, 5.2, 5.3 C 1 (q), C 2 (q), C 3 (q)

		Nota 4.1
	Vertical/Horizontal Lines	Def 4.2
	T P (C)	Nota 4.3
	Γ 1 Defs 5.1, 5.2, 5.3
	B	Def 6.1
	E	Def 6.1
	C i (q)	Def 7.1
	B i (q)	Defs 7.2, 7.3 and 7.4
	I i (q)	Defs 7.2, 7.3 and 7.4
	P i (q)	Defs 7.2, 7.3 and 7.4
	E P	Nota 7.6
	(C3) configuration	Def 7.10
	κ i (q, P, L, C)	Prop 7.13
	∼	Nota B.2
	[L]	Nota B.2

One can prove that the involution is constant when i = 1 and q is even. In even characteristic, the tangents of a curve of equation y = ax

+ bx + c are all parallel!

Acknowledgements

The author expresses a deep gratitude to Daniel Augot and Gilles Zémor for many inspiring discussions. Computations and simulations have been made using Magma.

This work was partially supported by the French ANR Defis program under contract ANR-08-EMER-003 (COCQ project).

≥ 2 at both them. Therefore, these curves meet at 4 points of A 2 counted with their multiplicities, which contradicts Lemma 5.12. This proves (vi). 7.3. Girths. Theorem 7.8 (Girth of the incidence graph). Let γ(i, q) be the girth of the incidence graph of the incidence structure I i (q). We have

Remark 7.9. The incidence graph of an incidence structure is a bipartite graph. Therefore, its cycles have even length. Thus, the girth of such graphs is even.

To prove Theorem 7.8, we need Lemma 7.11, Lemma 7.12, Proposition 7.13 and Lemma 7.16. Lemma 7.11 (The geometric structure of 6-cycles). The incidence graph of I 1 (q) (resp. I 2 (q), 3 (q)) has cycles of length 6 if and only if three elements of C 1 (q) (resp. C 2 (q), C 3 (q)) are in (C3) configuration.

Proof. Obviously, a triple of conics in (C3) configuration yields a cycle of length 6 in the incidence graph.

Conversely, assume there is a cycle of length 6 in the incidence graph of I i (q). Then, there are three blocks B a , B b , B c ∈ B i (q) together with three points (P bc , L bc ), (P ac , L ac ), (P ab , L ab ) ∈ P i (q) such that (P bc , L bc ) (resp. (P ac , L ac ), resp. (P ab , L ab )) is incident with B b and B c (resp. B a and B c , resp. B a and B b ). From Remark 6.2, two exceptional divisors (blocks in E) have no common point in P i (q). Therefore, at least two of the B i 's, say B a , B b are not in E and hence are of the form C a , C b with C a , C b ∈ C i (q). Let us prove that B c cannot be an exceptional divisor. If it was, since points (P bc , L bc ) and (P ac , L ac ) are both incident with B c , we would have P bc = P ac . In addition, since Proof of Lemma 2.18 (1). Let (P, P , P 3 , P 4 ) and (Q, Q, Q 3 , Q 4 ) be two such 4-tuples. Obviously, there exists a unique σ ∈ PGL(3, F q 2 ) sending (P, P , P 3 , P 4 ) onto (Q, Q, Q 3 , Q 4 ). Let us prove that σ is actually defined over F q , i.e. that σ = σ, where σ denotes the conjugate of σ under the Frobenius action. Since Q 3 is rational, we have Q 3 = Q 3 and hence Q 3 = σP 3 = σP 3 = σP 3 . In the same way, we obtain σP 4 = Q 4 . Moreover σP = Q = σP . By the same manner, we prove that σP = Q. By uniqueness of σ, we get σ = σ and hence σ ∈ PGL(3, F q ). Proof of Lemma 2.18 [START_REF] Gallager | Low-density parity-check codes[END_REF]. let (P 1 , P 2 , L 1 , L 2 ) and (Q 1 , Q 2 , M 1 , M 2 ) be two such 4-tuples. Choose two rational points

. The proofs of Lemma 2.18 (3) and (4) are obtained using the same techniques as in the above proofs.

Appendix B. Minimum weight codewords

In §8.2, it is proved that the codes C(i, q) have minimum distance at least 2q. In this appendix, we give an explicit construction of some codewords of weight 2q which concludes the proof of Theorem 8.5. To construct such codewords, we have to introduce additional mathematical tools.