Sandra Weller

Claude-Agnès Reynaud
email: reynaud@necker.fr

Jean-Claude Weill
email: weill@necker.fr

C.-A R Or

Splenic marginal zone B cells in humans: where do they mutate their Ig receptor?

Human IgM + IgD + CD27 + B cells have mutated Ig genes and harbor a splenic marginal zone phenotype. The group of R. Küppers has studied the expression of the enzyme activation-induced cytidine deaminase (AID) in human spleen samples by immunocytochemistry and failed to detect a significant AID-expressing subset in the marginal zone region. The consequences on the possible origin of these cells are discussed.

Introduction: "Memory" B cell subsets in humans R. Küppers and colleagues made the seminal observation that blood B cells in humans were very different from mice's one because they contained 30-40% of memory B cells displaying the CD27 marker at their surface and a mutated Ig receptor [START_REF] Klein | Human immunoglobulin (Ig)M+IgD+ peripheral blood B cells expressing the CD27 cell surface antigen carry somatically mutated variable region genes: CD27 as a general marker for somatically mutated (memory) B cells[END_REF]. Among these memory B cells, about half of them are switched cells and surprisingly, the other half are IgM-positive cells, distributed in two subsets, IgM + IgD + and IgM-only (i.e. IgD-negative) B cells. In their discussion these authors proposed, among other hypothesis, that these CD27 + IgM-positive cells could in fact be the equivalent of the mutated IgM + cells made during the formation of the preimmune repertoire in sheep.

At first and without any clear explanation for the discrepancy with Küppers's initial observation, a clear CD27 + IgM-only subset has not been observed by two different groups in either blood or spleen, its distinct presence being mostly linked with pathological situations (immunodeficiency or auto-immunity) [START_REF] Weller | Human blood IgM "memory" B cells are circulating splenic marginal zone B cells harboring a prediversified immunoglobulin repertoire[END_REF][START_REF] Kruetzmann | Human IgM memory B cells controlling Streptococcus pneumoniae infections are generated in the spleen[END_REF]. In AIDdeficient patients for example, in which there is a molecular block within germinal centers (GC) that prevents hypermutation and isotype switch [START_REF] Revy | Activation-induced cytidine deaminase (AID) deficiency causes the autosomal recessive form of the Hyper-IgM syndrome (HIGM2)[END_REF], one can detect a clear IgM-only CD27 + B cell subset in blood, suggesting that these cells could be GC precursors of switched cells that would now accumulate and thus appear in the circulation [START_REF] Weller | Human blood IgM "memory" B cells are circulating splenic marginal zone B cells harboring a prediversified immunoglobulin repertoire[END_REF].

Asking the question of the origin of IgM + IgD + CD27 + B cells, it was observed that hyper-IgM patients who lack either a functional CD40 or CD40L protein and therefore have no GC and switched cells (similarly to the equivalent experimental K.O. mice) always display IgM + IgD + CD27 + B cells with a mutated Ig receptor in blood [START_REF] Weller | Human blood IgM "memory" B cells are circulating splenic marginal zone B cells harboring a prediversified immunoglobulin repertoire[END_REF][START_REF] Weller | CD40-CD40L independent Ig gene hypermutation suggests a second B cell diversification pathway in humans[END_REF]. The frequency of these cells was often lower than in normal individuals of the same age, while the frequency of somatic mutations was close to normal. Now comes the issue of the interpretation of these results. Where do these mutated IgM + IgD + B cells come from in hyper-IgM patients? Are they made in cryptic germinal centers, which have not been described but may still exist in these patients, or do they belong to a separate B cell diversification pathway? The first explanation would mean that these cryptic structures would allow the generation and the mutation of the IgM + IgD + cells specifically but not the formation of any IgM-only and switched cells. Not a totally satisfactory explanation.

No marginal zone (MZ) B cell lineage in humans?

It has been shown thereafter that blood and splenic IgM + IgD + CD27 + B cells, which represent 10 to 30% of total B cells in normal individuals, display a marginal zone phenotype (IgM high , IgD low , CD21 + , CD23 -, CD1 + ) and are involved in Tindependent responses [START_REF] Weller | Human blood IgM "memory" B cells are circulating splenic marginal zone B cells harboring a prediversified immunoglobulin repertoire[END_REF][START_REF] Kruetzmann | Human IgM memory B cells controlling Streptococcus pneumoniae infections are generated in the spleen[END_REF]. The marginal zone B cell sub-population was originally described as a separate lineage in rodents, bearing the CD21 high CD23 -IgM + IgD low/- CD1 + phenotype, but, in contrast to humans, carrying a germline non-mutated Ig receptor [START_REF] Kumararatne | Marginal zones: the major B cell compartment of rat spleens[END_REF][START_REF] Martin | Marginal-zone B cells[END_REF]. Differentiation of this subpopulation occurs in mice as a cell lineage choice at the transitional B cell stage, resulting in either a follicular or a marginal zone phenotype. This binary cell fate decision is, like many others in development, mediated by the Notch pathway, Notch2 acting via RBP-J, with its function being counteracted by MINT in this specific case [START_REF] Saito | Notch2 is preferentially expressed in mature B cells and indispensable for marginal zone B lineage development[END_REF][START_REF] Kuroda | Regulation of marginal zone B cell development by MINT, a suppressor of Notch/RBP-J signaling pathway[END_REF]. Many other factors, involved in particular in cell migration or in BCR signal transduction, have profound impact on the follicular versus marginal zone B cell development [START_REF] Martin | Marginal-zone B cells[END_REF][START_REF] Pillai | Marginal zone B cells[END_REF].

Apart from very young children, all marginal zone B cells in humans (more than 95%) carry a mutated Ig receptor, and there is clearly no individualized unmutated subset among them (the low frequency of germline receptors corresponding to what is expected from a heterogeneous distribution of mutation frequencies). In this issue of Eur. J. Immunol., Willenbrock et al. study the distribution of AID-positive cells in the human spleen [START_REF] Willenbrock | Human splenic marginal zone B cells lack expression of activation-induced cytidine deaminase (AID)[END_REF], since the expression of AID is an absolute requisite for the occurrence of Ig gene hypermutation [START_REF] Revy | Activation-induced cytidine deaminase (AID) deficiency causes the autosomal recessive form of the Hyper-IgM syndrome (HIGM2)[END_REF][START_REF] Muramatsu | Class switch recombination and hypermutation require activationinduced cytidine deaminase (AID), a potential RNA editing enzyme[END_REF]. They found the frequency of AID-positive cells to be very low in the splenic marginal zone, and thus favor the proposition that most marginal zone B cells are in fact derived in humans from a T-dependent response taking place in germinal centers.

One should emphasize that the obvious conclusion of this proposition is that, as opposed to rodents, a distinct marginal zone B cell sub-population does not exist as such in humans. Taking into account the clear anatomical differences between rodent and human spleen, it would suggest that, instead of being a separate B cell lineage, marginal zone B cells arise in humans as a branching point during germinal center differentiation, after some accumulation of somatic mutation but before the onset of isotype switch (fig. 1). We obviously do not favor this interpretation and think, along with others, that, although the splenic marginal zone is a complex lymphoid niche, humans have evolved like rodents a separate sub-population of B cells which reside in this splenic compartment, are pre-activated and respond rapidly to blood-born TI antigens [START_REF] Martin | Marginal-zone B cells[END_REF][START_REF] Carsetti | Peripheral development of B cells in mouse and man[END_REF][START_REF] Spencer | Human marginal-zone B cells[END_REF].

Other sites for diversification of IgM + IgD + CD27 + B cells?

Hypermutation being the hallmark of a T-dependent germinal center reaction, the confusion arise from the fact that marginal zone B cells in humans carry a mutated Ig receptor and that vaccination against polysaccharidic antigens raise mutated antibodies [START_REF] Lucas | Polysaccharide vaccines as probes of antibody repertoires in man[END_REF]. However evolution has taught us that hypermutation and gene conversion can be used in several species in a T-independent and external antigen-free mode in order to generate a B cell pre-immune repertoire [START_REF] Reynaud | Hypermutation generating the sheep immunoglobulin repertoire is an antigen-independent process[END_REF][START_REF] Weill | A bird's eye view on human B cells[END_REF].

Moreover these molecular mechanisms that introduce diversity in the three VH/VL complementarity-determining regions (CDRs) can provide these animals with a diversified antibody repertoire with all range of affinities against proteic and polysaccharidic determinants present at the surface of pathogens.

Strikingly in humans this circulating and splenic marginal zone B cell population is already well expanded and mutated at a stage at which T-independent responses against encapsulated bacteria cannot take place (before 2 years), which led us to suggest that these cells could in fact mutate their IgM receptor "à la sheep" while they are generated, before responding to external antigens [START_REF] Weller | Human blood IgM "memory" B cells are circulating splenic marginal zone B cells harboring a prediversified immunoglobulin repertoire[END_REF]. The place where this pre-diversification would take place was obviously left open at that time, and if the splenic marginal zone appears as an obvious candidate, marginal zone-like regions in secondary lymphoid organs or gut-associated lymphoid tissues are among the many other possible sites of diversification. Results on the selection of specific clones belonging to this circulating and splenic marginal zone compartment after a Tindependent immunization showed by CDR3 spectratyping that the B cells clones involved, that carried an already mutated V gene, seemed to undergo a second round of diversification during the few days of the response, a process which would add one to three mutations on the selected B cell clone [START_REF] Weller | Human blood IgM "memory" B cells are circulating splenic marginal zone B cells harboring a prediversified immunoglobulin repertoire[END_REF]. What the results of the paper of Willenbrock et al. [START_REF] Willenbrock | Human splenic marginal zone B cells lack expression of activation-induced cytidine deaminase (AID)[END_REF] tell us is that the short round of hypermutation taking place in marginal zone B cells after a T-independent challenge may only concern a very small number of cells, or that they would emigrate rapidly after stimulation, or even possibly, that the intra-clonal diversification observed represent independent activation of clonally related cells and not reactivation of the hypermutation process during the T-independent immune response.

How much AID does it take to perform hypermutation?

A last point of discussion concerns the sensitivity of AID detection assay. The IgM + IgD + CD27 + shows an Ig gene mutation frequency significantly lower than switched B cells (by a factor of 2, approximately [START_REF] Weller | Human blood IgM "memory" B cells are circulating splenic marginal zone B cells harboring a prediversified immunoglobulin repertoire[END_REF]). Moreover, the actual accumulation of mutation could be a much slower process than the one occurring in a few weeks in germinal centers. The obvious question then is: what is the amount of AID necessary to induce somatic mutation? Most AID proteins are present in the cytoplasm of mutating B cells, as a result of a constant nucleo-cytoplasmic shuttling in which the nuclear export dominates [START_REF] Nagaoka | Activation-induced cytidine deaminase shuttles between nucleus and cytoplasm like apolipoprotein B mRNA editing catalytic polypeptide 1[END_REF]. Only a few AID molecules have the opportunity to assemble in a nuclear mutasome at any time point and reach their Ig gene target. It is moreover totally unknown whether the quantitative requirements for AID to perform hypermutation versus isotype switch differ, and to what specific processes the widely different intensities in AID staining of germinal center B cells correspond. It seems therefore somewhat premature to conclude that marginal zone B cells are devoid of any AID activity. Accordingly, semi-quantitative PCR of RNA extracted from various B cell subsets show a 20-fold lower expression in splenic IgM + IgD + CD27 + B cells compared to switched cells (after a double cell sorting), whereas splenic naive B cells were negative, thus arguing against a trivial contamination in the purification procedure (our unpublished data). As AID is also required to induce class switching, these data raise only the question of the sensitivity of the in situ detection, but cannot lead to the formal conclusion that hypermutation is occurring in marginal zone B cells.

In conclusion, if one assumes that, in spite of the lack of detection of AID expression in the splenic marginal zone reported here by Willenbrock et al., a separate marginal zone B cell subset with mutated Ig genes do exist in humans, the question is now to unravel how and where this population is constantly renewed, pre-activated and pre-diversified. Self and commensal bacterial antigens may be necessary to develop these cells but also CD40L triggering by accessory cells such as NKT that can recognize self-lipids presented by CD1 on MZ B cells [START_REF] Mattner | Exogenous and endogenous glycolipid antigens activate NKT cells during microbial infections[END_REF][START_REF] De Libero | Bacterial infections promote T cell recognition of self-glycolipids[END_REF]. In such a scheme pre-activation could not occur correctly in hyper-IgM patients lacking the

Figure legend

Fig.1. What origin for marginal zone B cells in humans?

Transitional B cells in the mouse have been described as undergoing a binary cell fate, depending upon Notch2 activation, to become either follicular B cells (than can later be activated in germinal centers, leading again to either memory B cells or plasmocytes) or marginal zone B cells, that can be engaged in rapid plasmocytic differentiation in the response to blood-born antigens [START_REF] Pillai | Marginal zone B cells[END_REF]. Marginal zone B cells in humans have been proposed to undergo diversification of their Ig genes outside of an immune response [START_REF] Weller | Human blood IgM "memory" B cells are circulating splenic marginal zone B cells harboring a prediversified immunoglobulin repertoire[END_REF]. An alternate proposition (marked by the dotted arrow) is that splenic marginal zone B cells in humans are a subset arising during germinal center differentiation, after the onset of somatic mutation and before isotype switch [START_REF] Willenbrock | Human splenic marginal zone B cells lack expression of activation-induced cytidine deaminase (AID)[END_REF].

Immature

  figure1

CD40-CD40L interactions, thus explaining the lower development of these cells. At the effector stage, when marginal zone B cells respond to TI antigens in the spleen, switch and differentiate into plasma cells here again they would need non cognate Tcell mediated CD40L signaling (explaining why no switching occurs in Tindependent responses in hyper-IgM patients), together with strong Ig cross-linking and TLR signaling, that would drive them rapidly out of the MZ microenvironment.


Thomas Le Jan

Myriam Servières

Thomas Leduc

Vincent Tourre

Isovist computation of outdoor environment with semi-dense line SLAM and monocular camera

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

Isovist computation of outdoor environment with semi-dense line SLAM and monocular camera

Thomas Le Jan 1 , Myriam Servières 1 , Thomas Leduc 2 , Vincent Tourre 1 1. AAU, Ecole Centrale de Nantes, Nantes thomas.le-jan@eleves.ec-nantes.fr,prenom.nom@ec-nantes.fr 2. AAU, CNRS, ENSA Nantes, Nantes thomas.leduc@crenau.archi.fr ABSTRACT. Isovists are powerful tools for the morphological analysis of urban spaces, allowing us to account for the characteristics of the visible space from a given point of view. However, computing isovist field from digital model is limited by the quality of the model, and computing isovist field of the real environment with LiDaR sensors is limited by its cost and the setup of cumbersome equipment (eg. on a car). To allow the use of lightweight devices, we propose a method to compute isovists from a single monocular camera, catching a path in an urban environment. This method uses SLAM (Simultaneous Localization and Mapping) and ray casting algorithms. Our results are compared against digital model's isovists.

RÉSUMÉ. Les isovists sont des outils performants d'analyse morphologique des espaces urbains permettant de rendre compte des caractéristiques de l'espace visible à partir d'un point de vue donné. Cependant, le calcul des champs d'isovists à partir d'un modèle numérique est limité par la qualité de ce modèle, et le calcul des champs d'isovists d'environnement réel à l'aide de capteurs LiDaR reste limité par son coût et la mise en place d'un équipement encombrant (par exemple, sur un véhicule). Pour permettre l'utilisation d'équipement portable, nous proposons d'établir une méthode d'obtention d'isovists à partir d'une caméra monoculaire captant un parcours dans un environnement urbain. Cette méthode est basée sur les algorithmes de SLAM (Simultaneous Localization And Mapping) et de lancer de rayons. Les résultats obtenus par notre méthode sont comparés à ceux obtenus sur un ensemble d'isovists calculés sur un modèle numérique 3D simplifié de la ville.

KEYWORDS: Isovists, camera, space reconstruction MOTS-CLÉS : Isovists, caméra, reconstruction de l'espace SAGEO'2021 -La Rochelle, 5-7 mai 2021

Introduction

Isovists and isovist fields are conceptual tools used to carry out morphological analyses of architectural and urban spaces. They were developed and theorized in the 70s [START_REF] Benedikt | To take hold of space: isovists and isovist fields[END_REF]). An isovist determines the available space in a direct line of sight from a given position in an architectural or urban environment. As the visibility of the urban space is part of the urban design qualities identified by urban planners [START_REF] Ewing | Measuring the unmeasurable: Urban design qualities related to walkability[END_REF], isovists are particularly relevant to evaluate the quality of an urban space. Depending on the dimension of the space, these isovists have a polygonal (2D) or polyhedral (3D) shape.

They're usually computed from a digital urban model extracted from a GIS, which is a simplified representation of the urban environment. Some methods can calculate isovists along a route caught with sensors, such as LiDaR [START_REF] Schmid | Quantifying local spatial properties through lidar-based isovists for an evaluation of opinion-based vgi in a vr setup[END_REF], but the use of these powerful sensors is not accessible to as many people as possible and this may be very inconvenient because of the cumbersome equipment that requires additional transport (e.g. on a car). Although there is more consumer LiDaR equipment available, here we focus on sensors that are embedded in everyone's smartphones. It is possible to reconstruct a map of the environment with lightweight sensors, for example monocular cameras, using SLAM algorithms (Simultaneous Localization And Mapping). SLAM addresses the computational issue of constructing or updating a map of an unknown environment while simultaneously keeping track of the observer's location. Time-of-flight camera are also available on several smartphones, but their actual depth performances and sensitivity to lighting conditions, among others drawbacks, prevent us to use them to reconstruct outdoor environments.

In this article, we propose a method to delineate an isovist field from a video caught on a simple monocular camera (video-based isovists), using SLAM algorithms. To check the consistency of our results, we will confront them to the isovists generated from a digital urban model (mockup-based isovists).

Previous Works

SLAM algorithms provide a fairly accurate estimation of the trajectory of a camera while reconstructing the environment in which the camera evolves. Usually, SLAM algorithms return a point cloud mapping the environment, socalled reconstructed map. Depending on the SLAM method, the point cloud can be sparse (e.g. ORB-SLAM2 (Mur-Artal, Tardos, 2017), PTAM [START_REF] Klein | Parallel Tracking and Mapping for Small AR Workspaces[END_REF]), dense (e.g. DTAM [START_REF] Newcombe | DTAM: Dense tracking and mapping in real-time[END_REF]) or semi-dense (e.g. [START_REF] Engel | LSD-SLAM: Large-Scale Direct Monocular SLAM[END_REF]). The sparse methods detect feature points on keyframes and they are assigned 3D coordinates in the reconstructed map. The dense methods rather give depth to almost every pixel of a keyframe. The map is then reconstructed by overlapping the different depth maps. Finally, semidense methods fall midway between sparse and dense methods. They detect areas of interest in keyframes and assign a depth to every pixel of these areas. Unfortunately, these methods each present some weaknesses. Indeed, a sparse point cloud may be fairly accurate but, due to its lack of density, it does not permit to reconstruct real obstacles (there are not enough feature points detected). Dense and semi-dense methods can return much denser point clouds but the returned maps will be very noisy. Some recent methods [START_REF] He | Incremental 3D Line Segment Extraction from Semi-dense SLAM[END_REF] can reconstruct a map of the environment with lines instead of points, which makes it easier to reconstruct accurate surfaces using Delaunay triangulation. The method implemented in this paper uses a semi-dense version of ORB-SLAM2 [START_REF] Mur-Artal | Probabilistic Semi-Dense Mapping from Highly Accurate Feature-Based Monocular SLAM[END_REF] to generate a semi-dense point cloud and extract lines from it.

SLAM methods often include loop closure which improves tracking and mapping by recognizing places already visited by the user. Then the associated map points and camera poses are adjusted according to their previous values.

There are some methods that allow isovist computation from point clouds [START_REF] Díaz-Vilariño | From point clouds to 3D isovists in indoor environments[END_REF]. These methods are based on space discretization. Once space is subdivided into voxels, we determine if the voxels are occupied or empty by the number of points they contain. Then by ray-casting, we determine if the voxels are visible or obstructed which gives us our isovist. There are limits to these kinds of methods. The first is that the returned isovists won't be a vector object, as it is computed in a discretized space. The second is that the method expects a dense and accurate point cloud to clearly model the environment, which is not the case of the previous common visual SLAM methods.

The other simple way to compute isovists as vector objects is to apply raycasting on surfaces, instead of points. That is possible with semi-dense-line SLAM [START_REF] He | Incremental 3D Line Segment Extraction from Semi-dense SLAM[END_REF] and its surface reconstruction method.

Proposal -LIghtweight Real Isovist: LIRI

Our method's workflow is shown in Fig. 1. It is based on semi-dense-line SLAM algorithm [START_REF] He | Incremental 3D Line Segment Extraction from Semi-dense SLAM[END_REF], which can reconstruct surfaces from semidense point cloud obtained by video processing (Fig. 2). We use a smartphone monocular camera but this method is standard enough to be applied to any type of monocular camera provided that we know its intrinsic parameters, which can be computed by camera calibration. So we have a 3D model of the environment made of triangles and an estimation of the sensor trajectory in the reconstructed map. The different poses returned by the algorithm are located in the coordinate system of the first detected keyframe. The global orientation of the reconstructed map then depends on the orientation of the camera lens during the detection of the first keyframe. In order to ease the comparison between video-based isovists and mockup-based isovists and to stabilize the skyline, we use an additional phone stabilizer, minimizing the camera orientation error. The phone stabilizer doesn't impact the standard and lightweight setup hypothesis. The resulting model has some outlier triangles that don't represent real assets so we apply a filter upon the area and the perimeter of the triangles to eliminate the outliers. This filter was set up experimentally.

We use a ray-tracing based method to compute isovists from the reconstructed map of the environment and estimated trajectory. We scan the environment using a panoptic approach in the horizontal plane of vision. To compute ray-tracing, we use the Möller-Trumbore intersection algorithm [START_REF] Möller | Fast, minimum storage ray/triangle intersection[END_REF] that can quickly calculate the intersection point between a triangle and a ray in 3D space, without using plane equations. For each ray, we look at every triangle and determine the intersection point, if it exists, and we only keep the nearest intersection point from the ray origin. By connecting the intersection points obtained in the different directions we can reconstruct the isovist for a given position. Finally, if we aggregate the different isovists obtained by the positions along a trajectory, we have the isovists field related to that trajectory.

To compare our method to the topographic-based model, we have to transform our data in a geographical context. So we have to apply scaling, translation, and homothety (dilation) but also extract geographical coordinates of one of the points of the trajectory. In our case we focus on the first point which corresponds to the first moment a keyframe is detected. The position of the camera associated with this first keyframe is predominant; we determine it empirically with the help of orthophotographs. We use a similar method to get the scale factor: we determine manually the geographical location of two points of the trajectory, using a GIS and orthophotographs, and we calculate the distance between them in the reconstructed map and in the topographic-based model. By applying this factor to our data, it is now possible to implement the estimation of the trajectory in the digital model to compute mockup-based isovists 1 . We can also compare the isovists obtained by both models.

1. To calculate the mockup-based isovists, we use standard topographic data sets such as the ones provided by the IGN BD TOPO® database (June 2020 edition) and the t4gpd Python plugin [START_REF] Leduc | Minimum-area ellipse bounding an isovist: towards a 2D GIS-based efficient implementation[END_REF].

SAGEO'2021

Results

We present here the results on one dataset collected in the city of Nantes. We suppose that the user made a single one-way journey. We also implement an arbitrary limit distance for the ray-casting, based on the size of the reconstructed map. The computation has been conducted on a PC with 8GB RAM, 4x2.60 GHz Intel Core i7 CPU, using Ubuntu 16.04 64 bits. With these characteristics, semi-dense-line SLAM ran for half an hour to fully map the environment from a one minute video. Then our method takes about two minutes to generate the 164 isovists related to the video. A quick comparison (Fig. 3) of the video-based and mockup-based isovists shows the similarities and the differences between the two models. Thus, the video-based isovists from the first poses of the trajectory are very circular, because of the limited field of view of the camera that doesn't allow the SLAM method to reconstruct the environment behind the observer. As seen in Fig. 3 left, as the scene behind the observer is not reconstructed, there is no mask (i.e. no building facades) to stop the rays. This lack of mask casts the rays to the limits of the artificial horizon (which is here of very limited range) which explains the circularity of the resulting shape. The video-based and mockupbased isovists attached to the following poses seem pretty similar. Finally, the last poses show again some differences. This is caused by the fact that videobased isovists take into account walls delineating private plots while mockupbased isovists only consider buildings surfaces. The fences detected in the video are not present in the 3D model derived from standard datasets.

To go beyond visual comparison of the different isovists, we used four morphological indicators:

-Perimeter : P -Area : A -Ellipticity factor : = π × L 2 /4A -Convexity defect : e conv = A/A hull With L, the largest distance between two vertices of the polygon and A hull the area of the convex hull of the polygon.

The ellipticity factor reflects the compression of a circle to form an ellipsoid and the flattening of the isovist. The convexity defect reflects the convex aspects of an isovist, especially the presence of concavity.

All these four parameters give information upon the global form of an isovist. We then compute these parameters for one in ten of the isovists.

By observing the Fig. 4, 5 and 6 we can separate the isovists into three main groups whose limits are indicated by green dashed lines in the figures. The first group may contain the isovists corresponding to the first poses of the trajectory. In this group, the video-based and mockup-based isovists show some differences. Indeed the first video-based isovists of the trajectory are almost circular, because of the lack of information of the reconstructed map in the first poses of the trajectory. This lack of information is due to the camera's limited field of view. This period during which the SLAM algorithm has not reconstructed the environment with enough information yet could be considered as an initialization phase.

The second group contains the next isovists. Here, the video-based and mockup-based isovists show much more similarities than in the first group. This is because there is enough information in the video to fully map the environment and the digital model is similar to what we can see in the video.

Finally, the third group contains the isovists of the last poses of the trajectory. Here the video-based and mockup-based isovists show differences. This may be explained by the fact that the video shows the reality of the environment, with additional occlusions such as walls or fences delineating private plots, while the digital model only considers buildings as polygons. The environment around the latter part of the trajectory contains a lot of these additional occlusions.

It can also be seen from Fig. 7 that the convexity defect graph of videobased isovist is less constant and overall higher than the mockup-based isovist convexity defect graph. This indicates the presence of more occlusion leading to more concavity, which corresponds to the less smooth real environment.

SAGEO'2021

In this way, video-based isovists generated by our method more accurately reflects the reality of the environment, as long as there are enough data provided by the video.

Conclusion, Discussion and Perspectives

In this paper, we presented a process to generate isovists from a video recorded with a monocular camera, in an urban street. If the video shows enough information, the video-based isovists are pretty similar to the ones generated using standard topographic datasets, provided the viewing distance. There is even evidence to suggest that our method gives additional details upon the real environment, compared to the digital urban model, by taking into account some obstacles that are not houses or buildings.

Our method can be used to further improve the digital model by taking into account real assets obstructing the user's view represented by video-based isovists; thus tackling the well known updating problem in GIS. Moreover, the video-based reconstruction of the shape of the immediate surroundings could help several applications, eg. the display of geolocalised information in augmented reality.

Our method cannot run in real-time due to the important amount of calculation during the mapping of the environment in the semi-dense-line SLAM algorithm. This forced us to use short videos to test our method and thus to work on small environments, and this is why we limited the range of the isovists. This issue could be solved using a more powerful computer and longer videos of the environment. We could also use the loop closure of the SLAM algorithm to optimize the reconstructed map by recognizing places already visited by the user.

Another axis of improvement would be to automatize the acquisition of world coordinates and scale factor of the reconstructed map of the environment and the estimated trajectory. This may be done by getting the camera's metadata giving GPS coordinates and orientation of the sensor. This would also allow an automatic correspondence of video-based and mockup-based isovists.

Our method is not dependant on any kind of device, and any monocular video -if we know the intrinsic parameters of the camera -can be taken as an entry. Considering that a limit of the video-based isovists is the limited field of view of a simple monocular camera, we may wonder about the possibility to extend this method to omnidirectional cameras. Indeed omnidirectional cameras can catch videos with a very large field of view and adapting this method to this kind of camera only demands to adapt the mathematical model of the SLAM algorithm from pinhole model to unified model [START_REF] Caruso | Large-scale direct SLAM for omnidirectional cameras[END_REF]. Using omnidirectional cameras implies processing more pixels which may make the calculations heavier but we would have complete video-based isovists rather than half video-based isovists for the first poses of the trajectory.

Furthermore, it would be interesting to add semantic treatment to our video in order to optimize the surface reconstruction. It's an approach which is already used by MIT-SPARK [START_REF] Rosinol | Kimera: an Open-Source Library for Real-Time Metric-Semantic Localization and Mapping[END_REF] but with stereo cameras. This approach may soon be extended to monocular cameras which could also be inserted in our method.

Another very recent method [START_REF] Yang | Mobile3Drecon: Real-time monocular 3D reconstruction on a mobile phone[END_REF] allows user to reconstruct in real-time a dense surface mesh of the environment with a mobile device equipped with an embedded monocular camera. This method has given interesting results in indoor environments. We could imagine applying it to outdoor environments to replace the semidense-line SLAM.

As future work, we could directly compare isovist field extracted from LiDaR point cloud with mock-up based isovist. Such a comparison could validate our method, taking the point cloud as a reference.

Figure 1 .

 1 Figure 1. Workflow of our method.

Figure 2 .

 2 Figure 2. Surfaces reconstructed with semidense-line SLAM method. The red line represents the trajectory of the sensor.

Figure 3 .

 3 Figure 3. Comparison of isovists field. Left: video-based isovists. Right: mockup-based isovists.

Figure 4 .)Figure 5 .Figure 6 .Figure 7 .

 4567 Figure 4. Perimeters (m) of video-based (blue) and mockup-based (red) isovists.


Minjia Shi

Ferruh Özbudak
email: ozbudak@metu.edu.tr

Sol Patrick

Li I Xu

Patrick Solé
email: sole@enst.fr.

LCD CODES FROM TRIDIAGONAL TOEPLITZ MATRICES

Keywords: LCD codes, Toeplitz matrices, Dickson polynomials AMS(2020) Math Sc. Cl. 94B05, 15B05, 12E10

Double Toeplitz (DT) codes are codes with a generator matrix of the form (I, T ) with T a Toeplitz matrix, that is to say constant on the diagonals parallel to the main. When T is tridiagonal and symmetric we determine its spectrum explicitly by using Dickson polynomials, and deduce from there conditions for the code to be LCD. Using a special concatenation process, we construct optimal or quasi-optimal examples of binary and ternary LCD codes from DT codes over extension fields.

Introduction

Linear Complementary Dual (LCD) codes are linear codes which intersect their dual trivially. They were introduced by Massey in 1992 to solve a problem in Information Theory [START_REF] Massey | Linear codes with complementary duals[END_REF]. They were proved to be asymptotically good by Sendrier [START_REF] Sendrier | On the dimension of the hull[END_REF], who used them in relation with equivalence testing of linear codes [START_REF] Sendrier | Finding the permutation between equivalent codes: the support splitting algorithm[END_REF]. They enjoyed a renewal of interest in 2016, with an application to side-channel attacks on embarked cryptosystems [START_REF] Carlet | Complementary dual codes for counter-measures to side-channel attacks[END_REF]. Recently LCD double circulant codes or double negacirculant codes were constructed over various alphabets [START_REF] Huang | Double Circulant Self-Dual and LCD Codes Over Z p 2[END_REF][START_REF] Shi | Double circulant LCD codes over Z 4[END_REF][START_REF] Shi | Double circulant self-dual and LCD codes over Galois rings[END_REF][START_REF] Shi | On the self-dual negacirculant codes of index two and four[END_REF][START_REF] Shi | On self-dual and LCD double circulant and double negacirculant codes over F q + uF q , Cryptography and Communications[END_REF]. A far reaching generalization of both double circulant and double negacirculant codes is that of double Toeplitz codes [START_REF] Shi | On isodual double Toeplitz codes[END_REF]. In the present paper, we introduce a class of double Toeplitz codes which can be effectively tested for being LCD.

A code is double Toeplitz (DT) if its generator matrix is of the form (I, T ) with I an identity matrix, and T a Toeplitz matrix of the same order. Recall that a matrix is Toeplitz if it has constant entries on all diagonals parallel to the main diagonal. Thus circulant matrices and negacirculant matrices are Toeplitz.

It is easy to check that such a code is LCD iff -1 is not an eigenvalue of T T t . To make that condition easy to check we will make two hypotheses on T :

• T = T t implying T T t = T 2 ; • T is tridiagonal, in the sense that T ij = 0 if |i -j| > 1.

In the next section, we show that the characteristic polynomial of a tridiagonal symmetric Toeplitz matrix satisfies a three-term recurrence that can be identified, up to an easy change of variable to that of the Dickson polynomials [START_REF] Lidl | Dickson Polynomials, Pitman Monographs and Surveys in Pure and Applied Math[END_REF]. The roots of these polynomials can be determined explicitly [START_REF] Bhargava | Factoring Dickson Polynomials over Finite Fields[END_REF]. Hence we obtain an exact and explicit characterization on whether a given DT code (I, T ) is LCD or not, when T is tridiagonal and symmetric (see Theorems 2.9 and 2.10 below). It seems very difficult to obtain such a characterization for arbitrary Toeplitz T . Moreover this is the first paper in the literature using factorization of Dickson polynomials for the characterization of some LCD codes as far as we know.

Under some mild arithmetic conditions we can show that this spectrum does not intersect the base field, and in particular does not contain -1. Some sufficient conditions for the DT code to be LCD follow. Since the DT codes so constructed have minimum distance at most three, a rather sophisticated concatenation process, namely isometry (see Definition 3.1 below) can be used to construct an LCD code over a small field. Note that because of the fundamental result that any linear code over F q with q > 3 is equivalent to an LCD code [START_REF] Carlet | Linear codes over F q are equivalent to LCD codes for q > 3[END_REF], the theory of LCD codes is focusing on the cases of F 2 and F 3 . Using the said concatenation process optimal or quasi-optimal LCD codes over these two fields are explicitly constructed.

The material is organized as follows. The next section studies the spectrum of Toeplitz matrices. Section 3 describes a concatenation process that allow for LCD codes over small fields. Numerical examples are given there. The last section concludes the paper.

Toeplitz matrices

2.1. A Spectral lemma. Throughout this paper, let p be a prime, q = p s for a positive integer s. Let F q denote the finite field of q elements. Let F q denote an agebraic closure of F q . Lemma 2.1. For n ≥ 1 let A be an n × n matrix over F q . We have the following cases:

• char F q is even: -1 is an eigenvalue of A 2 if and only if -1 is an eigenvalue of A.

• char F q is odd: -1 is an eigenvalue of A 2 if and only if -µ or µ is an eigenvalue of A, where µ ∈ F q 2 with µ 2 = -1.

Proof. If char F q is even, then

(A + I n ) 2 = A 2 + I 2 n = A 2 + I n ,
which completes the proof in this case.

If char F q is odd, then

(A + µI n )(A -µI n ) = A 2 -µ 2 I n = A 2 + I n ,
which completes the proof.

2.2. Characteristic polynomial. For a ∈ F q and n ≥ 3, let T n (a) be the n × n tridiagonal Toeplitz matrix depending on a defined as

T n (a) =       a 1 0 • • • 1 a 1 • • • . . . 0 • • • 1 a       .
Namely, for example, we have

T 3 (a) =    a 1 0 1 a 1 0 1 a    and T 4 (a) =      a 1 0 0 1 a 1 0 0 1 a 1 0 0 1 a      .
We also define the cases for n = 1, 2 as

T 1 (a) = a and T 2 (a) = a 1 1 a .
For n ≥ 1 let

φ n (λ) = det (T n (a) -λI n ) .
Lemma 2.2. Under notation as above, we have

φ n (λ) = (a -λ)φ n-1 (λ) -φ n-2 (λ)
for n ≥ 2 with φ 1 (λ) = a -λ and φ 0 (λ) = 1.

Proof. For n = 2 we have

T 2 (a) -λI 2 = a -λ 1 1
a -λ and hence

φ 2 (λ) = det (T 2 (a) -λI 2 ) = (a -λ) 2 -1 = (a -λ)φ 1 (λ) -φ 0 (λ).
This completes the proof for n = 2.

For n = 3 we have

T 3 (a) -λI 3 =    a -λ 1 0 1 a -λ 1 0 1 a -λ    .
Considering the expansion of det (T 3 (a) -λI 3 ) using the last row we obtain

φ 3 (λ) = (a -λ) a -λ 1 1 a -λ - a -λ 0 1 1 = (a -λ)φ 2 (λ) -φ 1 (λ).
This completes the proof for n = 3.

For n ≥ 3 we will show that the lemma holds for n + 1. Note that this will complete the proof. Assume that n ≥ 3. For the (n + 1) × (n + 1) tridiagonal Toeplitz matrix T n+1 (a) depending on a we have

T n+1 (a) =    T n-1 (a) C n-1 0 (n-1)×1 R n-1 a 1 0 1×(n-1) 1 a    .
Here T n-1 (a) is the (n -1) × (n -1) triagonal Toeplitz matrix depending on a, 0 1×(n-1) is the 1 × (n -1) matrix whose all entries are 0 and 0 (n-1)×1 is the (n -1) × 1 matrix whose all entries are 0. Moreover, R n-1 is an 1 × (n -1) row matrix and C n-1 is an (n -1) × 1 column matrix.

Considering the expansion of det (T n+1 (a) -λI n+1 ) using the last row we obtain

φ n+1 (λ) = T n-1 (a) -λI n-1 C n-1 0 (n-1)×1 R n-1 a -λ 1 0 1×(n-1) 1 a -λ = (a -λ) T n-1 (a) -λI n-1 C n-1 R n-1 a -λ - T n-1 (a) -λI n-1 0 (n-1)×1 R n-1 1 = (a -λ) T n-1 (a) -λI n-1 C n-1 R n-1 a -λ -φ n-1 (a).
In the last equality we use the expansion of T n-1 (a) -λI n-1 0 (n-1)×1 R n-1 1 using the last column. Note that

T n-1 (a) -λI n-1 C n-1 R n-1 a -λ = T n (a) -λI n .
Hence we conclude that

φ n+1 (λ) = (a -λ)φ n (λ) -φ n-1 (λ)
for n ≥ 3, which completes the proof.

For n ≥ 0, a ∈ F q and x ∈ F q , let ψ n be the function on F q defined as

ψ n : F q → F q x → φ n (a -x).
Lemma 2.3. Under notation as above we have

ψ n (x) = xψ n-1 (x) -ψ n-2 (x)
for n ≥ 2 with ψ 1 (x) = x and ψ 0 (x) = 1.

Proof. For n = 1 and n = 0 we have

ψ 1 (x) = φ 1 (a -x) = a -(a -x) = x, and ψ 0 (x) = φ 0 (a -x) = 1.
For n ≥ 2 we have

ψ n (x) = φ n (a -x) = (a -(a -x)) φ n-1 (a -x) -φ n-2 (a -x), using Lemma 2.2, = xφ n-1 (a -x) -φ n-2 (a -x) = xψ n-1 (x) -ψ n-2 (x)
, by definitions of ψ n-1 (x) and ψ n-2 (x).

This completes the proof.

Recall that (see, for example, [START_REF] Lidl | Dickson Polynomials, Pitman Monographs and Surveys in Pure and Applied Math[END_REF]) for α ∈ F q and n ≥ 0, the Dickson polynomial of the second kind

E n (x, α) ∈ F q [x]
is defined recursively

E n (x, α) = xE n-1 (x, α) -αE n-2 (x, α)
with the initial conditions E 1 (x, α) = x and E 0 (x) = 1.

We put α = 1 and denote E n (x) = E n (x, 1) throughout the paper. We obtain that E n (x) ∈ F q [x] is the polynomial defined resursively

E n (x) = xE n-1 (x) -E n-2 (x) (1)
with the initial conditions E 1 (x) = x and E 0 (x) = 1.

Combining Lemma 2.2, Lemma 2.3 and (1) we prove the following proposition immediately.

Proposition 2.1. Under notation as above we have

det (T n (a) -xI n ) = φ n (x) = E n (a -x),
for all n ≥ 1 and x ∈ F q .

We recall the following result due to Bhargava and Zieve [3, Theorem 4].

Theorem 2.1. Let n ≥ 1 be an integer. Assume that gcd(n + 1, q) = 1. We have the following cases

• char F q is odd:

E n (x) = n i=1 x -θ i + θ -i ,
where θ is a primitive 2(n + 1)-th root of 1.

• char F q is even: then n is even and

E n (x) = n/2 i=1 x -θ i + θ -i 2 ,
where θ is a primitive (n + 1)-th root of 1.

Definition 2.2. For a ∈ F q and an integer n ≥ 1, let C n (a) be the F q -linear code of length 2n and dimension n whose generator polynomial is the n × 2n matrix given by Theorem 2.3. For a ∈ F q and an integer n ≥ 1, consider the [2n, n] q code C n (a) given in Definition 2.2. Assume that gcd(n + 1, q) = 1 and char F q is even. Then n is even and C n (a) is LCD if and only if

[I n | T n (a)] .
a ∈ -1 + θ i + θ -i : 1 ≤ i ≤ n 2 ,
where θ is a primitive (n + 1)-th root of 1.

Proof. It is well known that C n (a) is LCD (see, for example, [11]) if and only if GG T is invertible, where G = [I n | T n (a)]. Note that GG T = [I n | T n (a)] I n T n (a) = I n + T n (a) 2 ,
where we use the fact that T n (a) is symmetric. Hence C n (a) is LCD iff -1 is not an eigenvalue of T 2 n (a). Using Lemma 2.1 we conclude that C n (a) is LCD iff -1 is not an eigenvalue of T n (a). It follows from the definition of φ n (x) that -1 is an eigenvalue of T n (a) iff φ n (-1) = 0. Using Proposition 2.1 we have that φ n (-1) = E n (a + 1). Finally using Theorem 2.1 we complete the proof.

In odd characteristic we have the following result.

Theorem 2.4. For a ∈ F q and an integer n ≥ 1, consider the [2n, n] q code C n (a) given in Definition 2.2. Assume that gcd(n + 1, q) = 1 and char F q is odd. Then C n (a) is LCD if and only if

a ∈ -µ + θ i + θ -i : 1 ≤ i ≤ n ∪ µ + θ i + θ -i : 1 ≤ i ≤ n ,
where µ 2 = -1 and θ is a primitive 2(n + 1)-th root of 1.

Proof. The proof is similar to that of Theorem 2.3. We only indicate the different steps in this proof. Note that -1 is an eigenvalue of

T 2 n (a) iff -µ or µ is an eigenvalue of T n (a) by Lemma 2.1. Hence C n (a) is not LCD iff E n (a + µ) = 0 or E n (a -µ) = 0.
We complete the proof using the similar steps as in the proof of Theorem 2.3.

The following corollaries are immediate.

Corollary 2.1. Assume that gcd(n + 1, q) = 1 and char F q is even. If q > n 2 , then there exists a ∈ F q such that C n (a) is LCD.

Proof. Let S = {-1 + θ i + θ -i : 1 ≤ i ≤ n/2}
, where θ is a primitive (n + 1)-th roof of 1. Note that |S| ≤ n/2 and hence |S ∩ F q | ≤ n/2. As q > n/2, there exists a ∈ F q \ S. Using such a and Theorem 2.3 we complete the proof.

Corollary 2.2. Assume that gcd(n + 1, q) = 1 and char F q is odd. If q > 2n, then there exists a ∈ F q such that C n (a) is LCD.

Proof. Let S = {-µ + θ i + θ -i : 1 ≤ i ≤ n} ∪ {µ + θ i + θ -i : 1 ≤ i ≤ n}, where µ 2 = -1
and θ is a primitive 2(n + 1)-th root of 1. Note that |S| ≤ 2n and hence |S ∩ F q | ≤ 2n. As q > 2n, there exists a ∈ F q \ S. Using such a and Theorem 2.4 we complete the proof.

Corollary 2.1 and Corollary 2.2 give that there exist a ∈ F q so that C n (a) is LCD for infinitely many C n (a), namely if q is large compared to n. The corresponding conditions are not necessary for the existence. Under arithmetic conditions, the following two corollaries give simple existence results for even and odd characteristics.

Corollary 2.3. Assume that q is even and gcd(n + 1, q(q 2 -1)) = 1. We have that C n (a) is LCD for all a ∈ F q .

Proof. Note that gcd(n + 1, q) = 1 and gcd(n + 1, q 2 -1) = 1. Let θ be a primitive (n + 1)-th root of 1. Let 1 ≤ i ≤ n/2 be an arbitrary integer. Put t = θ i . We have 1 + t + 1/t ∈ F q iff (1 + t + 1/t) q = 1 + t + 1/t iff u q = u with u = t + 1/t. Thus u is in F q and t is in F q 2 . Since t n+1 = 1, with t = 1, this is impossible for gcd(n + 1, q 2 -1) = 1. The result follows by Theorem 2.3.

The analog of Corollary 2.3 for the odd characteristic is slightly more complicated.

Corollary 2.4. Assume that q is odd. Moreover, we assume the following:

• If q ≡ 1 mod 4, then gcd(n + 1, q(q 2 -1)/2) = 1.

• If q ≡ 3 mod 4, then gcd(n + 1, q) = 1 and gcd(n + 1, (q 4 -1)/2) divides (q -1)/2.

Let µ ∈ F q 2 such that µ 2 = -1. We have the following:

• If q ≡ 1 mod 4, then C n (a) is LCD for all a ∈ F q \{µ+2, -µ+2, µ-2, -µ-2}. • If q ≡ 3 mod 4, then C n (a) is LCD for all a ∈ F q .
Proof. Note that gcd(n + 1, q) = 1. Let θ be a primitive 2(n + 1)-th root of 1. Let 1 ≤ i ≤ n be an arbitrary integer. Put t = θ i . Also put w = ±µ + t + 1/t. Assume that w ∈ F q . Next we consider the cases separately:

• q ≡ 1 mod 4: Here µ ∈ F q and hence t + 1/t ∈ F q . This implies that t ∈ F q 2 and t q 2 -1 = 1. As gcd(q 2 -1, 2(n + 1)) = 2 by assumption, we obtain that t ∈ {-1, 1}. Hence we have {µ+t+1/t, -µ+t+1/t}={µ+2, µ-2, -µ+2, -µ-2}.

We complete the proof using Theorem 2.4.

• q ≡ 3 mod 4: Here µ ∈ F q 2 \ F q and hence t + 1/t ∈ F q 2 . This implies that t ∈ F q 4 and t q 4 -1 = 1. As gcd(q 4 -1, 2(n + 1)) divides q -1 by assumption, we obtain that t ∈ F q . Hence we have ±µ + t + 1/t ∈ F q 2 \ F q . We complete the proof using Theorem 2.4.

This completes the proof.

We also give simple examples that are not covered by these corollaries.

Example 2.1. Let q = 3 and n = 3 so that the condition q > 2n of Corollary 2.2 does not hold. Also the conditions of Corollary 2.4 do not hold. Let θ be a primitive

2(n + 1) = 8-th root of 1. Let µ = θ 2 so that µ 2 = -1. Let S = {-µ + θ i + θ -i : 1 ≤ i ≤ n} ∪ {µ + θ i + θ -i : 1 ≤ i ≤ n}.
Using Magma [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF] we obtain that S = {0, θ 2 , θ 6 }. By Theorem 2.4 we conclude that C n (a) is LCD for a ∈ F q iff a ∈ {1, 2}.

Example 2.2. Let q = 3 and n = 4 so that the condition q > 2n of Corollary 2.2 does not hold. Also the conditions of Corollary 2.4 do not hold. Let θ be a primitive 2(n + 1) = 10-th root of 1. Let µ = θ 5 so that

µ 2 = -1. Let S = {-µ + θ i + θ -i : 1 ≤ i ≤ n} ∪ {µ + θ i + θ -i : 1 ≤ i ≤ n}.
Let w be a primitive element of F 3 4 such that w 4 + 2w 3 + 2 = 0. Using Magma [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF] we obtain that S = {w 10 , w 20 , w 30 , w 50 , w 60 , w 70 }.

Note that F q = {0, w 40 , w 80 }. By Theorem 2.4 we conclude that C n (a) is LCD for any a ∈ F q .

2.4. Extension of the results for T (a, b). For a, b ∈ F q and n ≥ 3, let Tn (a, b) be the n × n triagonal Topelitz matrix depending on a and b defined as

Tn (a, b) =       a b 0 • • • b a b • • • . . . 0 • • • b a       .
Namely, for example, we have

T3 (a, b) =    a b 0 b a b 0 b a    and T4 (a, b) =      a b 0 0 b a b 0 0 b a b 0 0 b a     
.

We also define the cases for n = 2 as

T2 (a, b) = a b b a .
It is easy to observe that if b = 0, then

1 b Tn (a, b) = T n (a/b), (2)
for n ≥ 2 and a ∈ F q . This observation leads to the following. Proof. For λ ∈ F q we have that det Tn (a, b)

λI n = 0 ⇐⇒ det 1 b Tn (a, b) -λI n = 0 ⇐⇒ det (T n (a/b) -λ/bI n ) = 0,
where we use (2). This completes the proof.

Combining Theorem 2.3 and Lemma 2.4 we immediately obtain the following generalization.

Definition 2.5. For a, b ∈ F q and an integer n ≥ 2, let Ĉn (a, b) be the F q -linear code of length 2n and dimension n whose generator polynomial is the n × 2n matrix given by

I n | Tn (a, b) .
Theorem 2.6. For a, b ∈ F q with b = 0 and an integer n ≥ 2, consider the [2n, n] q code Ĉn (a, b) given in Definition 2.5. Assume that gcd(n + 1, q) = 1 and char F q is even. Then n is even and Ĉn (a, b) is LCD if and only if

a/b ∈ -1/b + θ i + θ -i : 1 ≤ i ≤ n 2 ,
where θ is a primitive (n + 1)-th root of 1.

Proof. Note that -1 is an eigenvalue of Tn (a, b) iff -1/b is an eigenvalue of T n (a/b) by Lemma 2.4. This holds iff E n ((a + 1)/b) = 0 by Proposition 2.1. We complete the proof using Theorem 2.1 as in the proof of Theorem 2.3.

Theorem 2.7. For a, b ∈ F q with b = 0 and an integer n ≥ 2, consider the [2n, n] q code Ĉn (a, b) given in Definition 2.5. Assume that gcd(n + 1, q) = 1 and char F q is odd. Then Ĉn (a, b) is LCD if and only if

a/b ∈ -µ/b + θ i + θ -i : 1 ≤ i ≤ n ∪ µ/b + θ i + θ -i : 1 ≤ i ≤ n ,
where µ 2 = -1 and θ is a primitive 2(n + 1)-th root of 1.

Proof. The proof is similar to those of Theorem 2.6 and Theorem 2. In the following theorem we recall the result in [3, Theorem 4] for the arbitrary case including gcd(n + 1, q) = 1.

Theorem 2.8. Let n ≥ 1 be an integer. For the characteristic p of F q , let r be the nonnegative integer such that p r || (n + 1). Let m be the nonnegative integer such that n + 1 = p r (m + 1). We have the following:

• p is odd:

E n (x) = E m (x) p r (x -2) (p r -1)/2 (x + 2) (p r +1)/2 and E m (x) = m i=1 x -θ i + θ -i ,
where θ is a primitive 2(m + 1)-th root of 1. • p = 2: then m is even and

E n (x) = E m (x) 2 r x 2 r -1 and E m (x) = m/2 i=1 x -θ i + θ -i 2 ,
where θ is a primitive (m + 1)-th root of 1.

We extend Theorem 2.6 (and hence Theorem 2.3) for gcd(n + 1, q) = 1.

Theorem 2.9. For a, b ∈ F q with b = 0 and an integer n ≥ 2, consider the [2n, n] q code Ĉn (a, b) given in Definition 2.5. Assume that char F q is even. Let r be the nonnegative integer such that 2 r || (n + 1). Let m be the nonnegative integer such that n + 1 = 2 r (m + 1). Assume that r ≥ 1 (see Theorem 2.6 for the remaining case that r = 0). We have that m is even. If m > 0, then Ĉn (a, b) is LCD if and only if

a/b ∈ {-1/b} ∪ -1/b + θ i + θ -i : 1 ≤ i ≤ m 2 ,
where θ is a primitive (m + 1)-th root of 1.

If m = 0, then Ĉn (a, b) is LCD if and only if a = 1.
Proof. The proof is similar to that of Theorem 2.6. The main difference is that we use Theorem 2.8 instead of Theorem 2.1. Now we extend Theorem 2.7 (and hence Theorem 2.4) for gcd(n + 1, q) = 1.

Theorem 2.10. For a, b ∈ F q with b = 0 and an integer n ≥ 2, consider the [2n, n] q code Ĉn (a, b) given in Definition 2.5. Assume that char F q is odd, which is p. Let r be the nonnegative integer such that p r || (n + 1). Let m be the nonnegative integer such that n + 1 = p r (m + 1). Assume that r ≥ 1 (see Theorem 2.7 for the remaining case that r = 0).

If m > 0, then Ĉn (a, b) is LCD if and only if a/b ∈ {-µ/b + 2, -µ/b -2, µ/b + 2, µ/b -2} ∪ {-µ/b + θ i + θ -i : 1 ≤ i ≤ m} ∪ {µ/b + θ i + θ -i : 1 ≤ i ≤ m} ,
where µ 2 = -1 and θ is a primitive 2(m + 1)-th root of 1.

If m = 0, then Ĉn (a, b) is LCD if and only if a/b ∈ {-µ/b + 2, -µ/b -2, µ/b + 2, µ/b -2}.
Proof. The proof is similar to that of Theorem 2.7. The main difference is that we use Theorem 2.8 instead of Theorem 2.1.

Next we extend Corollaries 2.1, 2.2, 2.3 and 2.4.

Corollary 2.5. Let b ∈ F q with b = 0 and n ≥ 2 an integer. Assume that char F q is even. Let r be the nonnegative integer such that 2 r || (n + 1). Let m be the nonnegative integer such that n + 1 = 2 r (m + 1). Assume that r ≥ 1 (see Corollary 2.1 for the remaining case that r = 0). If q > m/2 + 1, then there exists a ∈ F q such that Ĉn (a, b) is LCD.

Proof. The proof is similar to that of Corollary 2.1. We have q > m/2 + 1 instead of q > m/2 in the hypothesis as x = 0 is a root of E n (x) for r ≥ 1.

Corollary 2.6. Let b ∈ F q with b = 0 and n ≥ 2 an integer. Assume that char F q is odd. Let r be the nonnegative integer such that 2 r || (n + 1). Let m be the nonnegative integer such that n + 1 = 2 r (m + 1). Assume that r ≥ 1 (see Corollary 2.2 for the remaining case that r = 0). If q > 2m + 4, then there exists a ∈ F q such that Ĉn (a, b) is LCD.

Proof. The proof is similar to that of Corollary 2.2. We have q > 2m + 4 instead of q > 2m in the hypothesis as x = 2 and x = -2 are roots of E n (x) for r ≥ 1.

Corollary 2.7. Let b ∈ F q with b = 0 and n ≥ 2 an integer. Assume that char F q is even. Let r be the nonnegative integer such that 2 r || (n + 1). Let m be the nonnegative integer such that n + 1 = 2 r (m + 1). Assume that r ≥ 1 (see Corollary 2.3 for the remaining case that r = 0). Furthermore, assume that gcd(m + 1, q 2 -1) = 1. We have that Ĉn (a, b) is LCD for all a ∈ F q \ {1}.

Proof. The proof is similar to that of Corollary 2.3. We have Ĉn (a, b) is LCD for all a ∈ F q \ {1} instead of for all a ∈ F q in the conclusion as Ĉn (1, b) is not LCD by Theorem 2.9 when r ≥ 1.

In the following corollary there are no differences in the conclusion for the cases q ≡ 1 mod 4 and q ≡ 3 mod 4, which is not the situation in Corollary 2.4.

Corollary 2.8. Let b ∈ F q with b = 0 and n ≥ 2 an integer. Assume that char F q is odd, which is p. Let r be the nonnegative integer such that p r || (n + 1). Let m be the nonnegative integer such that n + 1 = p r (m + 1). Assume that r ≥ 1 (see Corollary 2.4 for the remaining case that r = 0). Furthermore, assume that • If q ≡ 1 mod 4, then gcd(m + 1, (q 2 -1)/2) = 1.

• If q ≡ 3 mod 4, then gcd(m + 1, (q 4 -1)/2) divides (q -1)/2.

Let µ ∈ F q 2 such that µ 2 = -1. We have that Ĉn (a, b) is LCD for all a ∈ F q \ {µ + 2b, µ -2b, -µ + 2b, µ -2b}.
Proof. The proof is similar to the proof of Corollary 2.4. We have Ĉn (a, b)

is not LCD for a ∈ {µ + 2b, µ -2b, -µ + 2b, µ -2b} as Ĉn (a, b) is not LCD if a/b ∈ {µ/b + 2, µ/b - 2, -µ/b + 2, -µ/b -2} by Theorem 2.10 when r ≥ 1.

Concatenation

In this section we construct LCD codes over F q with prescribed large minimum distance using DT that we characterize in Theorems 2.9 and 2.10 over an extension field F q s and a kind of concatenation. It is not difficult to observe that most of the concatenation maps do not work as they would not respect LCD property over the base and the extension fields. Hence we use an isometry map, which is introduced in [START_REF] Carlet | A new concatenated type construction for LCD codes and isometry codes[END_REF] as a special concatenation respecting LCD property. The minimum distance of the DT codes in Theorems 2.9 and 2.10 have minimum distance at most 3. However, the minimum distance of the isometry code can be arbitrarily large, provided the length of the isometry code is increased if necessary.

First we recall some results and notations from [START_REF] Carlet | A new concatenated type construction for LCD codes and isometry codes[END_REF].

Definition 3.1. Let n ≥ s ≥ 2 be integers. An F q -linear map π : F q s → F n q is called an isometry if there exists a basis (e 1 , . . . , e s ) of F q s over F q such that π(e i ) • π(e j ) = δ i,j for all 1 ≤ i, j ≤ s. Here • is the Euclidean inner product on F n q , (e 1 , . . . , e s ) is the dual basis of (e 1 , . . . , e s ), and δ i,j is the Kronecker delta.

The image π(F q s ) is an [n, s] q code, which we call an isometry code. Let d max-isometry (q; [n, s]) be the largest nonnegative integer d such that there exists an isometry π : F q s → F n q and π(F q s ) has minimum distance d.

Note that d max-isometry (q; [n, s]) coincides with the largest maximum distance of [n, s] q codes for many parameters. For example d max-isometry (2; [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF][START_REF] Araya | On the minimum weights of binary LCD codes and ternary LCD codes[END_REF]) = 2, d max-isometry (2; [START_REF] Carlet | Complementary dual codes for counter-measures to side-channel attacks[END_REF][START_REF] Bhargava | Factoring Dickson Polynomials over Finite Fields[END_REF]) = 2 and d max-isometry (3; [START_REF] Carlet | Complementary dual codes for counter-measures to side-channel attacks[END_REF][START_REF] Araya | On the minimum weights of binary LCD codes and ternary LCD codes[END_REF]) = 3 (see [START_REF] Carlet | A new concatenated type construction for LCD codes and isometry codes[END_REF]).

Let s ≥ 2 be an integer. Let n ≥ s be an integer such that d max-isometry (q, [n, s]) ≥ 1. Let π : F q s → F n q be an isometry such that π(F q s ) is an [n, s, d] q code, where d = d max-isometry (q, [n, s]).

For a, b ∈ F q s with b = 0 and an integer N ≥ 2, let ĈN (a, b) be the [2N, N ] q s code given in Definition 2.5.

Let π ⊗2N : F 2N q s → F 2N n q be the F q -linear map given by π ⊗2N (c 1 , . . . , c 2N ) = (π(c 1 ), . . . , π(c 2N )) .

We use these notations in the following two theorems. Now we are ready to construct LCD codes of arbitrary minimum distance using tridiagonal Toeplitz matrices over extension fields and isometry. First we present the even characteristic case. Theorem 3.2. Under notations as above assume that char F q is even. Let r be the nonnegative integer such that 2 r || (N + 1). Let m be the nonnegative integer such that N + 1 = 2 r (m + 1). Let θ be a primitive (m + 1)-th root of 1. Moreover we assume the following in the corresponding cases:

• If r = 0, then a/b ∈ {1/b + θ i + θ -i : 1 ≤ i ≤ m/2}.
• If r ≥ 1 and m = 0, then a = 1. Proof. Using Theorem 2.9 we obtain that ĈN (a, b) is an LCD code over the extension field F q s with minimum distance D. As π(F q s ) is an [n, s, d] q isometry code, we complete the proof by [START_REF] Carlet | A new concatenated type construction for LCD codes and isometry codes[END_REF]Theorem 3.1].

• If r ≥ 1 and m ≥ 1, then a/b ∈ {1/b} ∪ {1/b + θ i + θ -i : 1 ≤ i ≤ m/2}.
Next we consider the odd characteristic case.

Theorem 3.3. Under notation as above assume that char F q is odd, which is p. Let r be the nonnegative integer such that p r || (N + 1). Let m be the nonnegative integer such that N + 1 = p r (m + 1). Let θ be a primitive 2(m + 1)-th root of 1. Let µ 2 = -1. Moreover, we assume the following in the corresponding cases: Proof. The proof is similar to that of Theorem 3.2. The difference is that we use Theorem 2.10 instead of Theorem 2.9.

• If r = 0, then a/b ∈ {-µ/b + θ i + θ -i : 1 ≤ i ≤ m} ∪ {µ/b + θ i + θ -i : 1 ≤ i ≤ m} . • If r ≥ 1 and m = 0, then a/b ∈ {-µ/b + 2, -µ/b -2, µ/b + 2, µ/b -2}. • If r ≥ 1 and m ≥ 1, then a/b ∈ {-µ/b + 2, -µ/b -2, µ/b + 2, µ/b -2} ∪ {-µ/b + θ i + θ -i : 1 ≤ i ≤ m} ∪ {µ/b + θ i + θ -i : 1 ≤ i ≤ m} , .
In the following examples, we illustrate how to construct LCD codes with a prescribed lower bound on the minimum distance over small fields, in particular F 2 and F 3 , using the methods of this paper. In fact, we obtain good codes having optimal and almost optimal parameters and the actual minimum distances of our constructed codes are even better than the prescribed lower bounds in these examples.

Example 3.1. Let s = 2, q = 2 and N = 4. Let w be a primitive element of F q s satisfying w 2 + w + 1= 0. For a = w and b = 1, the [2N, N ] q s code ĈN (a, b) given in Definition 2.5 is an LCD code having parameters [4, 2, 3] 4 (see Theorem 2.9). Put n = 4. For a 1 = w, a 2 = w 2 , a 3 = 1 and a 4 = 1, the F q -linear map π : F q s → F n q x → (Tr(a 1 x), Tr(a 2 x), Tr(a 3 x), Tr(a 4 x)) is an isometry map such that the corresponding isometry code π(F q s ) is an [4, 2, 2] 2 code. Here Tr is the trace map from F q s onto F q . Using Theorem 3.2 we obtain that π ⊗2N

ĈN (a, b) is an LCD code with parameters [16, 4, D * ] 2 with the prescribed lower bound on the minimum distance D * given by D * ≥ 6. In fact using Magma [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF] it is easy to verify that D * = 7. This is an optimal LCD code, namely the largest minimum distance D of LCD code with parameters [16, 4, D] 2 is 7 (see [START_REF] Araya | On the minimum weights of binary linear complementary dual codes[END_REF]).

Example 3.2. Let s = 3, q = 2 and N = 4. Let w be a primitive element of F q s satisfying w 3 + w + 1= 0. For a = w and b = w 6 , the [2N, N ] q s code ĈN (a, b) given in Definition 2.5 is an LCD code having parameters [4, 2, 3] 4 (see Theorem 2.9). Put n = 5. For a 1 = w 3 , a 2 = w 5 , a 3 = w 6 , a 4 = 1 and a 5 = 1, the F q -linear map π : F q s → F n q

x → (Tr(a 1 x), Tr(a 2 x), Tr(a 3 x), Tr(a 4 x), Tr(a 5 x))

is an isometry map such that the corresponding isometry code π(F q s ) is an [5, 3, 2] 2 code. Here Tr is the trace map from F q s onto F q . Using Theorem 3.2 we obtain that π ⊗2N ĈN (a, b) is an LCD code with parameters [20, 6, D * ] 2 with the prescribed lower bound on the minimum distance D * given by D * ≥ 6. In fact using Magma [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF] it is easy to verify that in fact D * = 7. This is an almost optimal LCD code, namely the largest minimum distance D of and LCD code with parameters [20, 6, D] 2 is 8 (see [START_REF] Araya | On the minimum weights of binary linear complementary dual codes[END_REF]).

Example 3.3. Let s = 2, q = 3 and N = 4. Let w be a primitive element of F q s satisfying w 2 + 2w + 2= 0. For a = 2 and b = w, the [2N, N ] q s code ĈN (a, b) given in Definition 2.5 is an LCD code having parameters [4, 2, 3] 9 (see Theorem 2.10). Put n = 5. For a 1 = w, a 2 = w, a 3 = w 3 , a 4 = w 3 and a 5 = 2, the F q -linear map π : F q s → F n q

x → (Tr(a 1 x), Tr(a 2 x), Tr(a 3 x), Tr(a 4 x), Tr(a 5 x))

is an isometry map such that the corresponding isometry code π(F q s ) is an [5, 2, 3] 3 code. Here Tr is the trace map from F q s onto F q . Using Theorem 3.2 we obtain that 7].

Conclusion

In this paper we have constructed LCD double Toeplitz codes from tridiagonal symmetric Toeplitz matrices. It would be worthwhile to extend these results to symmetric Toeplitz matrices with more than three nontrivial diagonals. We conjecture that this might require multivariate Dickson polynomials [START_REF] Lidl | Dickson Polynomials, Pitman Monographs and Surveys in Pure and Applied Math[END_REF]. This might help to construct DT codes over small fields without recourse to the concatenation process of the previous section.

2. 3 .

 3 LCD double Toeplitz codes. Now we present our first characterization result on whether C n (a) is LCD or not.

Lemma 2 . 4 .

 24 For n ≥ 2, a, b ∈ F q and b = 0 we have that λ is an eigenvalue of Tn (a, b) if and only if λ/b is an eigenvalue of T n (a/b).

4 . 4 . 2 . 5 .

 4425 Note that -µ or µ is an eigenvalue of Tn (a, b) iff -µ/b or µ/b is an eigenvalue of T n (a/b) by Lemma 2.4. This holds iff E n ((a + µ)/b) = 0 or E n ((a -µ)/b) = 0 by Proposition 2.1. We complete the proof using Theorem 2.1 as in the proof of Theorem 2.Extension of the results for gcd(n + 1, q) = 1. First we introduce further notation: For positive integers a, b and a nonnegative integer u, b u || a denotes that b u |a and b u+1 a.

  Then π ⊗2N ĈN (a, b) is an LCD code with parameters [2nN, sN, D * ] q such that D * ≥ dD, where D is the minimum distance of ĈN (a, b).

  Then π ⊗2N ĈN (a, b) is an LCD code with parameters [2nN, sN, D * ] q such that D * ≥ dD, where D is the minimum distance of ĈN (a, b).

  π ⊗2N ĈN (a, b) is an LCD code with parameters [20, 4, D * ] 3 with the prescribed lower bound on the minimum distance D * given by D * ≥ 9. Using Magma [4] it is easy to verify that in fact D * = 10. The largest minimum distance D of an LCD code with parameters [20, 4, D] 3 is 12 by [2, Table

Acknowledgement

This research is supported by the National Natural Science Foundation of China (Grants no. 12071001 and 61672036), the Excellent Youth Foundation of Natural Science Foundation of Anhui Province (1808085J20), the Academic Fund for Outstanding Talents in Universities (gxbjZD03).