Julien Couvidat

Vincent Chatain

Hassan Bouzahzah

Mostafa Benzaazoua

Julien Couvidat1

Vincent Chatain1

Hassan Bouzahzah3

Mostafa Benzaazoua1

Characterization of how

Keywords: Biogeochemical reactivity, Contaminated marine sediment, Sulfides, Leaching, oOxidation, Organic matter

come

Introduction

Careful management of the dredged sediment is necessary for the good operation of ports and navigable waterways. In 2010, about 18.6 million tons of sediment (dry weight) were dredged in mainland France and France''s overseas territories, 33.56 million tons in 2009, and 23.2 million tons in 2008[START_REF] Guyader | Enquête "Dragage 2009" -Synthèse des données[END_REF][START_REF] Guyader | Enquête "Dragage 2010" -Synthèse des données[END_REF]. According to European legislation, once the sediments are extracted from their natural environment, they are considered as waste and thus must be consequently managed according to the legislation in force (Commission Decision of 3 May 2000 Replacing Decision 94/3/EC Establishing a List of Wastes, 2002;JORF, 2007).

These marine sediments are mainly composed of mineral species (quartz, silicates, carbonates, iron and manganese oxyhydroxides and sulfides, etc.) and organic matter. As they accumulate by the deposit of solid and colloidal matter, marine sediments are also the final "reservoir" for numerous contaminants coming from industrial and port activities, urban effluent, nautical activities or deposited in the form of aerosols. In this way, they integrate and amplify the contaminant concentrations [START_REF] Delvalls | Determining contamination sources in marine sediments using multivariate analysis, TrAC Trends in Analytical ChemistryTrAC Trends Anal[END_REF]. Inorganic pollutants such as copper, zinc, lead, chromium, mercury, and arsenic, are a particular issue due to their ubiquity and persistence in the environment [START_REF] Frémion | Key parameters influencing metallic element mobility associated with sediments in a daily-managed reservoir[END_REF][START_REF] Jones | Distribution and speciation of heavy metals in surficial sediments from the Tees Estuary, north-east England, Marine Pollution BulletinMar[END_REF][START_REF] Caplat | Heavy metals mobility in harbour contaminated sediments: Tthe case of Port-en-Bessin, Marine Pollution BulletinMar[END_REF][START_REF] Eek | Diffusion of PAH and PCB from contaminated sediments with and without mineral capping; measurement and modelling[END_REF][START_REF] Lions | Metal availability in a highly contaminated, dredged-sediment disposal site: Ffield measurements and geochemical modeling[END_REF]Chatain et al., 2013a). A large number of organic pollutants also accumulate in the marine sediments such as PCBs, PAHs, residues of medicines and endocrine disruptors, as well as organometallic compounds e.g. organotin compounds principally coming from antifouling paints used to prevent aquatic organisms from attaching to boats. These compounds, frequently encountered at various concentrations in the dredged marine sediments, are considered dangerous for the environment as well as for human health [START_REF] Dıéz | Organotin contamination in sediments from the Wwestern Mediterranean enclosures following 10 years of TBT regulation[END_REF][START_REF] Mamindy-Pajany | Ex situ remediation of contaminated sediments using mineral additives: Aassessment of pollutant bioavailability with the microtox solid phase test[END_REF][START_REF] Casado-Martínez | A multivariate assessment of sediment contamination in dredged materials from Spanish ports[END_REF][START_REF] Ribecco | Biological effects of marine contaminated sediments on Sparus aurata juveniles, Aquatic ToxicologyAquat[END_REF][START_REF] Staniszewska | The relationship between the concentrations and distribution of organic pollutants and black carbon content in benthic sediments in the Gulf of Gdańsk, Baltic Sea, Marine Pollution BulletinMar[END_REF].

To set up a long-lasting management plan for the dredged sediment, it is necessary to have more precise knowledge and more than just the degree of contamination. Therefore, it is essential to determine how the contaminants are distributed in the sedimentary matrix. Furthermore, these sediments are renowned for being particularly reactive materials following their abrupt change in surroundings after dredging; for example, when the saturation in water greatly diminishes, the redox potential increases significantly due to an increased availability of molecular oxygen. Wind and rain also induce cycles of lixiviation and drying favoring the formation of secondary mineral phases likely to control the mobility of dissolved metallic elements (Tack et al., 2006). Following these changes, these metals can be released into the lixiviation water and thus contaminate the soil if the effluent is not controlled [START_REF] Caille | Solubility of metals in an anoxic sediment during prolonged aeration, Science of The Total EnvironmentSci[END_REF]Chatain et al., 2013b;[START_REF] Stephens | Changes in the leachability of metals from dredged canal sediments during drying and oxidation[END_REF]. Actually, the paper aim in characterizing the contaminant mineralogical speciation and their geochemical evolution during weathering under natural conditions. From this in-depth characterization, adapted management solutions could be proposed and evaluated.

Material and methods

Sampling, storage and treatment

The two sediments in this study come from the same sampling point, from a port in the south of France, submitted to an extensive anthropic activity during many centuries and contaminated by industrial activity. They were collected by dredging the 50--80 first centimeters of the harbor seabed with a mechanical shovel. The unweathered sediment was immediately put in 50 L opaque containers under a 10 cm layer of sea water to preserve the anoxic conditions and stored in a dark cold room at 4 °C. Underwater storage enables the physicochemical parameters of the environment before dredging to be conserved as much as possible. Indeed, this conditioning is to avoid any reactivity of the sediment that comes from an anoxic environment. Sulfides content and organic matter are very instable and may oxidize quickly if exposed to air (Couvidat et al., 2016b). The preservation method was inspired from what recommended during sulfides mine waste handling [START_REF] Benzaazoua | Cementitious backfill with high sulfur content Pphysical, chemical, and mineralogical characterization, Cement and Concrete ResearchCem[END_REF].

A part of this sediment was sieved (20 mm) and underwent bioremediation pretreatment lasting 5 months during which it was regularly watered and aerated by turning-off with a mechanical shovel, then stored for a further 5 years outdoors without any special protection. These samples are called the naturally-weathered sediment. Storage of the sample in the open air under weather condition without being covered, enables natural alteration to be simulated for long-term storage conditions. For the naturally-weathered sediments, the samples to be analyzed were taken from different parts of the stored sediment and then mixed to produce a more homogeneous sample, stored also in the dark at 4 °C.

Characterization of dredged sediments

Physicochemical parameters

Physicochemical parameters measurements were performed on both sediments. The natural pH, ORP (oxidation-reduction potential, which was afterward utilized to determine the Eh by using the standard reference electrode potential, SHE of 204 mV), and conductivity were measured on a sediment slurry with a water-sediment ratio of 1:2; after a contact time of 48 hoursh using an Accumet® combined glass electrode. The redox potential of the sediment (ORP) was measured using a portable multi-meter (VWR SympHony SB90M5) supplied with a pH Ag/AgCl electrode (Fischer AccupHast 13-620-114), and an Eh Ag/AgCl electrode (Cole Palmer EW-05990-55), while conductivity was determined according to Standard Method 4110 [START_REF] Apha | Standard mMethods for the eExamination of wWater and wWastewater[END_REF]. Water content was estimated by using the gravimetric method NF EN 12880 (X 33-005). Organic matter content was determined as TOC concentration through dry combustion in a furnace following the standard NF ISO 10694. Three current organotin compounds (monobutyltin, dibutyltin, and tributyltin) were analyzed into both sediments by low-resolution MS. Sixteen PAHs were also measured benzo[g,h,i]perylene, indeno[1,2,3-c,d]pyrene) with GC/MS quantitative analysis following hexane/acetone extraction, according to the XP X 33-012 method. PCBs content was calculated according a similar method as for the HAPs, represented by the sum of 7 regulated PCB species (PCB 28,52,101,118,138,153,and 180).

Sulfides within sediments are often not solely crystallized and other forms of reduced sulfur exist, which considerably induce microbiological activity and metals mobility (Chatain et al., 2013b;Couvidat et al., 2016b). The acid volatile sulfides (AVS) method consists of the generation of H 2 S from acid-sensitive sulfides by the addition of HCl while stirring for 60 min, with a solution-sediment ratio of 1:10 (5 g of sample in 500 mL of 1 N HCl), and to absorb the producing gas into 10 mL of a Sulfide Anti-Oxidant Buffer (SAOB) solution, to be towards analyzed for soluble sulfides [START_REF] Brouwer | Diffusion method for the determination of acid-volatile sulfides (AVS) in sediment, Environmental Toxicology and ChemistryEnviron[END_REF][START_REF] Leonard | Modified diffusion method for analysis of acid volatile sulfides and simultaneously extracted metals in freshwater sediment, Environmental Toxicology and ChemistryEnviron[END_REF][START_REF] Rickard | Acid volatile sulfide (AVS)[END_REF]. The SAOB solution was analyzed for dissolved sulfides by spectrophotometry (HACH DR-890 Colorimeter) using the methylene blue method (equivalent procedure to USEPA 376.2 or Standard Method 4500-S2-D for wastewater).

Analysis of major and trace inorganic compounds was carried out on 6 granulometric fractions (< 25 μm, 25--80 μm, 80--200 μm, 200--1000 μm, 1--2 mm, > 2 mm). Particle-size distribution (PSD) was conducted by wet sieving according to an adaptation of the XP P 94--041 standard. After mineralization by alkali fusion with LiBO 2 , and acid solubilization in HNO 3 •H 2 O 2 , total Inorganic species analysis was realized by ICP-MS (Inductively Coupled Plasma -Mass Spectroscopy) accordingly to the internal procedure of the SARM laboratory [START_REF] Carignan | Routine Aanalyses of Ttrace Eelements in Ggeological Ssamples using Fflow Iinjection and Llow Ppressure Oon-Lline Lliquid Cchromatography Ccoupled to ICP-MS: Aa Sstudy of Ggeochemical Rreference Mmaterials BR, DR-N, UB-N, AN-G and GH, Geostandards NewsletterGeostand[END_REF]. Specific gravity was determined with a helium gas pycnometer (Micromeritics Accupyc 1330). Total sulfur was determined by induction furnace analyzer (Eltra CS-2000). A modified Sobek method [START_REF] Sobek | Field and lLaboratory mMethods aApplicable to oOverburden and mMinesoils[END_REF] was carried out on both sediments for the sulfur characterization, while organic sulfur forms were considered as negligible. Then, just the HCl 40% extraction was used, to obtain the HCl-extractable sulfur forms, mostly amorphous sulfides and sulfates, as well as other sulfur forms, mostly sulfides, by difference with total sulfur. The acid-generating Potential (AP) was calculated by the Paktunc method using the sulfides content determined by the X-ray diffraction (Paktunc, 1999a;Paktunc, 1999b), and the neutralization potential (NP) was determined by the [START_REF] Sobek | Field and lLaboratory mMethods aApplicable to oOverburden and mMinesoils[END_REF] method modified by [START_REF] Lawrence | Determination of neutralization potential in the prediction of acid rock drainage[END_REF] [START_REF] Lawrence | Determination of neutralization potential in the prediction of acid rock drainage[END_REF]Wang, 1997, Sobek et al., 1978).

Mineralogical analysis

The mineralogy of both sediments was carefully analysedanalyzed using Optical Microscopy (OM), X-Ray Diffraction (XRD) and Scanning Electron Microscopy (SEM).

The XRD analysis was carried out using a Bruker apparatus (AXS D8 advance) equipped with a Cu anticathode, by scanning over a diffraction angle (2θ) range from 5° to 70°. Scan settings were 0.02° 2θ step size and 4 s counting time per step. The DiffracPlus EVA software (v.3.2) was used for mineral species identification, while the TOPAS software (v 4.1), with the implementation of the Rietveld refinement, was used to quantify the abundance of all identified mineral species (Young, 1993). The precision of the Rietveld quantification is in the order of ± 0.5 to 1 % [START_REF] Bouzahzah | Modal analysis of mineral blends using optical image analysis versus X ray diffraction[END_REF][START_REF] Raudsepp | Application of Rietveld Analysis to Environmental Mineralogy[END_REF]. The mineralogical identification was also achieved by microscopy observations on polished section prepared with bulk sediment samples impregnated in an Epoxy resin. The optical microscopy observations was performed by a reflected light microscope (Zeiss Axio Imager.M2m) and allowed to define selected area for further scanning electron microscope (SEM) examination. Thus, the chemical composition of the individual minerals (stoichiometry) was determined using an SEM (Hitachi S-3500 N) equipped with an Energy Dispersive Spectrometer (EDS, Silicon Drift Detector X-Max 20 mm 2 , Oxford) operated under the INCA software (450 Energy). The operating conditions were 20 keV, ~ 100 μA and 15 mm working distance.

Kinetic test: weathering cells

The weathering cells test, mostly used in mining environment to sulfide-rich materials, enables to accelerate the weathering processes within materials in order to assess their reactivity [START_REF] Bouzahzah | Prediction of acid mine drainage: importance of mineralogy and the test protocols for static and kinetic tests, Mine Water and the EnvironmentMine[END_REF][START_REF] Cruz | Cyclic voltammetry applied to evaluate reactivity in sulfide mining residues[END_REF]Villeneuve et al., 2009). About 70 g of both sediments were placed on a 0.45 μm paper filter positioned in a Büchner-type funnel, and twice a week leached by 50 mL of deionized water (pH is between 6.5 and 8.5). Each leaching was separated by consecutively two and three days of drying. The Eh, pH and conductivity of the leachates were instantaneously determined, before the analysis of inorganic compounds of interest by ICP-AES. These physicochemical parameters were realized over 18 cycles, until reaching a geochemical equilibrium of the leachates.

Results

Physicochemical characterization

The values for the principal physicochemical parameters measured for the unweathered and naturally-weathered sediments are given in Table 1. As the samples come from the same sampling point they have some common characteristics for certain parameters, notably the density of 2.5 g/cm 3 which is close to that of quartz (2.65 g/cm 3 ) or carbonates (2.6--2.8 g/cm 3 ) and a natural pH of 7.3 for both sediments. However, the bioremediation treatment and the method of conservation for the weathered sediment, lead to significant physicochemical differences. First, the electrical conductivity of the water extracted from the pores is 25 mS/cm for the unweathered sediment and decreases to 5 mS/cm for the weathered sediment, probably due to the natural lixiviation under open-air storage. Aeration leads to a much more oxidized state in the weathered sediment which thus induces a higher redox potential (ORP) (572 mV/SHE for the weathered sample compared to 331 for the unweathered sediment), and a change in speciation of the elements, notably those of sulfur. There is little variation in the total sulfur content, around 2 wt.%. The fraction which cannot be extracted in HCl and is mainly composed of crystallized sulfides, decreases between the unweathered and weathered samples from 1.6 to 1.0 wt.%. However, the fraction that can be extracted in HCl which includes the amorphous sulfides and almost all of the sulfate minerals, increases from 0.3 to 1.0 wt.%. In a similar way, the acid-generating potential (AP), associated to sulfide minerals, is higher in the unweathered sediment (50 kg CaCO 3 /t) than for the weathered one (32 kg CaCO 3 /t). However, the neutralization potential (NP) is about 7 to 10 times greater than the AP in both samples. The quantity of sulfides making up the AVS class, mainly the amorphous sulfides, polysulfides and clusters, decreases from 4.3 × 10 --3 g(S)/kg in the unweathered sample, to 9.4 × 10 --5 g(S)/kg in the weathered samples. Both sediments are rich in organic matter, with almost 6 wt.% of TOC.

However, a significant decrease in the loss on ignition is observed (12.5 and 7.9 wt.%, for the unweathered and weathered samples, respectively), as well as the quantity of PAH (62 and 22 mg/kg on average, for the unweathered and weathered samples, respectively) and organotin compounds (65.5 compared to 5.9 mg/kg, for the unweathered and weathered samples, respectively). Chemical analysis of the two sediments also highlights their significant contamination by trace metals, particularly by copper (1445 and 835 mg/kg), lead (760 and 1260 mg/kg) and zinc (2085 and 2550 mg/kg), for the unweathered and weathered samples, respectively. The concentrations of these three metals is above the N2 thresholds set by the French regulation in the decree of 09 August 2006 for the disposal of waste in the sea, which are 90, 200 and 552 mg/kg MS for Cu, Pb and Zn, respectively. These decree sets two threshold N1 and N2 for concerning trace metals in dredged sediments; when metals concentrations are below N1 threshold, the potential impact is considered as negligible and the sediment can be rejected to the sea, whereas one trace metal exceeds N2 threshold, the sediment is treated as "highly contaminated", cannot be rejected in the sea, and need to undergo proper management. The chemical form, and in particular the mineral phases containing these metals, will be discussed with the mineralogical results. Both sediments have a fine granulometry, with about 45 to 50 % v/v of the particles having a diameter less than < 20 μm (Fig. 1). In fact, the D 50 of the unweathered sediment is 22 μm, and that of the weathered samples 19 μm.

The fraction where the diameter of particles is greater than > 100 μm decreases in the weathered samples whereas the finest fractions increase. This results in a substantial decrease in the D 90 from 153 to 80 μm between the unweathered and weathered sediment.

In addition to the PSD studied by laser diffraction, based on a model working with the volume of particles, the size distribution or particles in both sediments was analyzed with a mechanical sieving. This analysis results in the particle mass distribution, in order to determine the distribution of trace metals in the different fractions of unweathered (Fig. 2a) and weathered (Fig. 2b) sediments.

Sieving revealed that both sediments are mainly composed of fine particles where the < 25 μm fraction represents 53 % and 48 % by mass of the unweathered and naturally-weathered sediments, respectively. The fine fraction of the sediment is known for concentrating the metallic pollutants due to the large specific surface area intrinsic to the substances it is composed of, such as clays [START_REF] Eggleton | A review of factors affecting the release and bioavailability of contaminants during sediment disturbance events[END_REF][START_REF] Isaure | Quantitative Zn speciation in a contaminated dredged sediment by μ-PIXE, μ-SXRF, EXAFS spectroscopy and principal component analysis[END_REF][START_REF] Maity | Trace metals distribution and their dependence on some physico-chemical parameters in creek sediment, Toxicological & Environmental ChemistryToxicol[END_REF]. As stated above, the three metals targeted in this study are Cu, Pb and Zn due to their high concentration. Figure . 2a and 2b show the distribution of these elements between the different granulometric fractions. The finest fraction (less than < 25 μm) of both sediments is the highest concentrated for those three elements. The > 2 mm fraction contains about 5 % of the total quantity of these elements in the unweathered sediment, but this percentage does not go above 0.3 % in the weathered sediment. Furthermore, these three metals are observed as more concentrated in the < 25 μm fraction in the weathered sediment, whereas they are distributed more homogeneously between the different granulometric fractions for the unweathered sediment. However, in order to estimate the distribution of these metals in the different fractions, it is necessary to take into account their mass proportion. Thus, in the < 25 μm fraction of the unweathered sediment, Cu is present at 41 %, Pb at 53 % and Zn at 49 %. This distribution increases to 82 %, 85 % and 78 % in the weathered sediment for the same three metals, respectively. This suggests a possible treatment by size separation to separate the contaminated fine fraction from the cleaner coarse fraction of sediments. In a second time, the coarser fraction could be used as a secondary unweathered material in an integrated valorization pathway.

Mineralogical characterization

The mineralogical data obtained by XRD is presented in tableTable 2. The two samples contain 45 and 35 wt.% silicates minerals (quartz, muscovite, chamosite, illite and kaolinite) respectively in the unweathered and naturallyweathered sediments. Carbonate minerals (calcite and dolomite) also represent a main content of both sediments with respectively 38 and 52 wt.%. Pyrite (FeS 2 ) is the main sulfide minerals with 3.4 and 2 wt.% in the unweathered and weathered samples, respectively. The quantity of pyrite decreased in the naturally-weathered sediments probably because of their oxidation after exposure to the atmosphere and natural weather changes. Chalcopyrite (CuFeS 2 ) occurs in trace level in the unweathered sediment (0.3 wt.%) whereas we observed halite (NaCl) in quantities of 3.7 wt.% which decreased to 0.8 wt.% in the naturally-weathered sediments. This decrease is connected to the significant alt-text: Fig. 2 decrease in the conductivity of the sediments linked to the natural lixiviation (washing) by rainwater of the sediments during storage (Table 1). Finally, we observed the appearance of gypsum and magnetite in the naturally-weathered sediments in quantities of 5 and 1 wt.%, respectively. The mineralogical characterization was completed by optical and scanning electron microscopy (SEM) observations. These confirmed the presence of quartz, calcite and framboïdal pyrite in both sediments (Fig. 3). The framboïdal pyrite is composed of micro-cubes of pyrite where the average size is about 1 μm (Fig. 3b andd). This form of pyrite is considered as the most common in anoxic media, as well as the most reactive one [START_REF] Pierret | Sur l'origine de la pyrite framboïdale dans les sédiments de la fosse Suakin (mer Rouge)[END_REF]. In the weathered sediment, an aluminosilicate-bonded agglomerate was observed containing aluminosilicates, copper and zinc components with pyrite, quartz and calcite (Fig. 3b andc). These agglomerates could explain the preservation of pyrite oxidation in oxic conditions. In fact, framboïdal pyrite in agglomerates is always present and does not show any sign of oxidation (Fig. 4). However, free pyrite shows signs of transformation into iron oxide as shown in fFigure.

4a and b. In the unweathered sediment, pyrrhotite (Fe 1 --x S) was observed and shows signs of transformation into hematite (Fe 2 O 3 ) and magnetite (Fe 3 O 4 ) (Fig. 4c andd). Chemical analysis has shown that the granulometric distribution of Pb, Zn and Cu in the two sediments is very different. It is probable that the speciation of these elements has changed with the natural weathering and bioremediation treatment. The SEM observations and element microanalyses were able to determine their distribution and identify the phases containing these metals (element speciation). The copper is in the form of chalcopyrite and covellite (Fig. 5a andb), copper (Fig. 5c) or mixed-metal sulfide complexes such as CuFe 4 S 5 (Fig. 5d). Cu and Zn can also be found in dispersed and concentrated forms in the aluminosilicate agglomerates (Figs. 3b and4a). Zn and Pb are not found in any crystallized mineral form. Figure . 6 illustrates the X-ray mapping of Zn showing its association to sulfur distribution, but not occurring as sulfide minerals.

to an augite (Aug) showing signs of transformation into magnetite (Mag) and hematite (Hém).

alt-text: Fig. 4

Leaching tests in weathering cells

The mineralogical study of the two sediments has shown that they contain sulfide minerals. The latter are particularly sensitive to oxidation by oxygen and water, as organic matter which is known for controlling the mobility of certain metal ions such as copper and lead (Chatain et al., 2013b;[START_REF] Couvidat | An innovative coupling between column leaching and oxygen consumption tests to assess behavior of contaminated marine dredged sediments, Environmental Science and Pollution ResearchEnviron[END_REF][START_REF] Morabito | Temporal evolution of cadmium, copper and lead concentration in the Venice Lagoon water in relation with the speciation and dissolved/particulate partition[END_REF]. The use of a leaching test in weathering cells has enabled to assess the reactivity of the sediments according to the protocol described previously.

The pH of the leachates varies very little, and globally oscillates around the « natural » pH of sediments, i.e. 7.5 to 7.7. This pH is related to the presence of carbonated minerals (calcite and dolomite, Table 2) which buffer the pH. The conductivity which is initially very high in the unweathered sediment (54 mS/cm) decreases very rapidly to finally reach a pseudo-stationary state after 5 leaching cycles. The initial conductivity of the weathered sediment is much less (9 mS/cm) but also decreases rapidly to reach values approaching those of the unweathered sediment. The redox potential oscillates throughout the test from 500to 600 mv/SHE, explained by the oxidizing conditions in the two sediments.

The release of Cu, Pb and Zn is low, even with the highly oxidizing redox potential in the two sediments (Fig. 7). In fact, the accumulated quantity of copper in the leachates does not go over 2.5 mg/kg for the weathered sediment, and 0.7 mg/kg for the unweathered sediment, whereas the accumulated quantities in lead and zinc do not exceed 0.5 mg/kg for the two sediments (Fig. 7a, 7b and 7c). The copper and lead were mainly released during the first 5 cycles. However, the Zn behaves differently for the two samples, in that the quantity released during the last 4 cycles is greater than that in the previous ones. Figure . 7d shows a linear relation between the charges accumulated in calcium and magnesium on the one hand, and sulfates on the other, which is linked to the oxidation-neutralization phenomenon which occurs in materials rich in sulfides and carbonates [START_REF] Benzaazoua | Kinetic tests comparison and interpretation for prediction of the Joutel tailings acid generation potential[END_REF]. The oxidationneutralization curve is almost linear for the weathered sediment, thus showing a strong correlation between the release of sulfur and calcium and magnesium ions. However, for the unweathered sediment, the curve shows an inflection during the first 4 cycles before becoming linear, which might mean that release of S, Ca and Mg into the lixiviates is probably partially disconnected. alt-text: Fig. 6

(

  naphthalene, acenaphthylene, acenaphthene, fluorene, phenanthrene, anthracene, fluoranthene, pyrene, benzo[a]anthracene, chrysene, benzo[b]fluoranthene, benzo[k]fluoranthene, benzo[a]pyrene, dibenzo[a,h]anthracene,

Fig. 1

 1 Fig. 1 Particles size distribution by laser diffraction of unweathered (a) and weathered (b) sediments (% in volume).alt-text: Fig.1

Fig. 2

 2 Fig. 2 Analysis of the repartition of the sediment particles, copper, lead and zinc in 6 granulometric fractions of unweathered (a) and weathered (b) sediments (uncertainties are < 5% for Cu and Pb, and < 10% for Zn and for the > 2mm fraction for Cu).

Fig. 3 Fig. 4

 34 Fig. 3 Optical and scanning electron microscope images: a,b) weathered sediment: framboïdal pyrite (PyFr) included into an aluminosilicate-bonded agglomerate rich of copper and zinc (L) and containing quartz (Qz) and calcite (Cal); c,d) unweathered sediment: framboïdal pyrites.alt-text: Fig.3

Fig. 5

 5 Fig. 5 Optical microscope images of unweathered sediment: a, b) chalcopyrite (Cpy) and covellite (Cov); c) native copper (Cu); d) iron and copper mixed sulfide CuFe4S5 included into Katophorite (Ka).alt-text: Fig.5

Fig. 6

 6 Fig. 6 a) Scanning electron microscope image of a grain in unweathered sediment; b, c, d) X-mapping images showing zinc, sulfur and oxygen distribution in the grain of unweathered sediment.

Table 1

 1 Physicochemical characteristics of the sediments.

	alt-text: Table 1
	Parameter	Unit	Unweathered	Weathered
	pH	--	7.4	7.3
	ORP	mV/SHE	331	572
	Conductivity	mS/cm	25	5
	Water content	wt.%	47	23
	Loss on ignition	wt.%	12.5	7.9
	TOC	wt.%	5.8	6.3
	∑ PAHs	mg/kg	62.18 < x < 62.4	21.93 < x < 22.35
	∑ PCBs	mg/kg	0.96 < x < 0.97	1.07 < x < 1.21
	∑ oOrganotins	mg/kg	65.5	5.9
	Sulfur	wt.%	1.89	2.02
	HCl-extractable Ssulfur	wt.%	0.29	1.04
	Other sulfur forms	wt.%	1.61	0.98
	AVS	g(S)/kg	4.3 × 10--3	9.4 × 10--5
	NP	kg(CaCO3)/t	384	536
	AP	kg(CaCO3)/t	50	31
	Iron	wt.%	3.7	3.4
	Copper	mg/kg	1445	835
	Lead	mg/kg	760	1260
	Zinc	mg/kg	2085	2550

Table 2

 2 XRD mineralogical analyses of unweathered and weathered sediments.

	alt-text: Table 2
	Mineral

Acknowledgments

The authors are grateful to the EEDEMS platform (French research network on waste and polluted materials management) for experimental support. The authors also acknowledge the Research and Service Unit in Mineral Technology (URSTM), University of Quebec in Abitibi-Temiscamingue (UQAT) for their experimental support.

Discussion

Although the two sediments studied come from the same sampling campaign, the conditions in which they were kept have significantly influenced their physicochemical characteristics. First of all, the impact of storage in the open air after bioremediation treatment influences their redox state which increases as the saturation in water decreases. In fact, oxygen diffuses into the sediment to reach the phases sensitive to oxidation, such as the sulfides and organic matter. In the presence of molecular oxygen, which is the main oxidant of reduced sulfur species in oxic environments, water is necessary as shown by the oxidation equation for pyrite (Eq. ( 1)) [START_REF] Lowson | Aqueous oxidation of pyrite by molecular oxygen[END_REF]:

The atmospheric oxygen combined to the meteoritic water enables oxidation at the same time as the leaching of most of the mobile elements such as chlorides and oxidation products such as sulfates.

The aging phenomenon, by weathering in open air, had the effect of modifying the distribution of the metallic elements in the different granulometric fractions of the sediments. In fact, we observed that the fractions less than < 80 μm were enriched in Cu, Pb and Zn when going from the unweathered to the naturally-weathered sediments (Fig. 2). These elements are concentrated in the < 80 μm fraction in the naturally-weathered sediments, whereas in the unweathered sediments, distribution is more likely to follow the mass distribution of the fractions. The redistribution of the metals, in particular in the sulfide phases towards the more accessible reactive phases (labile or acidsoluble), was also observed after aeration and drying of the sediment [START_REF] Claff | Effect of sample pretreatment on the fractionation of Fe, Cr, Ni, Cu, Mn, and Zn in acid sulfate soil materials[END_REF][START_REF] Calmano | Binding and mMobilization of hHeavy mMetals in cContaminated sSediments aAffected by pH and rRedox pPotential[END_REF].

The aging phenomenon also had the effect of varying the weight of the different unweathered and weathered sediment fractions, notably for the < 25 μm fraction which decreased in favor of the 200--1000 μm and 1--2 mm fractions, with an increase of 5.3 and 4.9 %, respectively. Particle agglomeration is probably the cause of this granulometric modification. In the naturally-weathered sediments, the SEM observations revealed the presence of aggregates composed of alumino-silicates (Fig. 3b and4b), maybe clay-humus complexes considering the high content in organic matter (Table 1). These are considered as being relatively stable, and come from a modification of the structure of the organic matter [START_REF] Puget | Dynamics of soil organic matter associated with particle-size fractions of water-stable aggregates[END_REF][START_REF] Capel | Elucidation of different forms of organic carbon in marine sediments from the Atlantic coast of Spain using thermal analysis coupled to isotope ratio and quadrupole mass spectrometry, Organic GeochemistryOrg[END_REF][START_REF] Sutton | Molecular Sstructure in Ssoil Hhumic Ssubstances: Tthe Nnew Vview[END_REF]. With weathering, the organic matter partially degrades, and recombines to produce acid humic complexes. In the weathered sediment, we also observe a significant degradation, or volatilization, in particular of the PAHs and the organo--tins, compared to the unweathered sediment, but not for the PCBs which are very persistent molecules (Table 1). Bioremediation and weathering act relatively efficiently on the degradation of the hydrocarbon-type organic or organo-metallic molecules [START_REF] Juhasz | Bioremediation of high molecular weight polycyclic aromatic hydrocarbons: a review of the microbial degradation of benzo[a]pyrene[END_REF][START_REF] Straube | Remediation of polyaromatic Hhydrocarbons (PAHs) through landfarming with Bbiostimulation and Bbioaugmentation[END_REF][START_REF] Beolchini | Degradation kinetics of butyltin compounds during the bioremediation of contaminated harbour sediments[END_REF][START_REF] Mulligan | An evaluation of technologies for the heavy metal remediation of dredged sediments[END_REF][START_REF] Rulkens | Introduction to the Ttreatment of Ppolluted Ssediments, Reviews in Environmental Science and BiotechnologyRev[END_REF][START_REF] Cruz | Microbial remediation of organometals and oil hydrocarbons in the marine environment[END_REF].

The speciation of sulfur also evolves but differently for the two sediments. We observed a decrease in the crystallized or amorphous sulfides after weathering and an increase in oxidized sulfur, mainly in the form of sulfates. This evolution can be noticed with the decrease of pyrite and chalcopyrite concentrations from unweathered to weathered sediments and the appearance of gypsum in unweathered sediments (Table 2), with the decrease in the quantity of AVS from unweathered to weathered, or also with the increase of soluble sulfur in HCl acid from unweathered to weathered (Table 1). XRD also revealed the appearance of secondary minerals in the naturally-weathered alt-text: Fig. 7 (1) sediments which are the products of sulfide oxidation, in particular gypsum and iron oxides. Those oxidation products derived mainly from the oxidation taking place within the sediments, because of the 5-years open air storage. In fact, sulfides are sensitive to oxidation in presence of water and oxygen [START_REF] Jerz | Pyrite oxidation in moist air[END_REF]. However, despite the aging conditions of the naturally-weathered sediments, sulfides are still present including the particularly reactive framboïdal form of pyrite. It''s more likely than minerals from inner layers of the sediment may have been protected from oxidation, either by surface precipitation of oxidation products and subsequent surface coating (Fig. 4b), or by aggregation into aluminosilicates binders as observed by SEM (Fig. 3b). Less surprisingly, sulfides can be observed in the unweathered sediments, their persistence being explained by the underwater conservation limiting the diffusion of oxygen in the sedimentary layers.

For the marine sediments, the release of metals is very sensitive to pH variation (Chatain et al., 2013b;[START_REF] Calmano | Binding and mMobilization of hHeavy mMetals in cContaminated sSediments aAffected by pH and rRedox pPotential[END_REF][START_REF] Frémion | Key parameters influencing metallic element mobility associated with sediments in a daily-managed reservoir[END_REF]. The leaching test in weathering cells showed that the pH of the leachates of the two sediments is neutral. It is buffered by the large quantity of carbonates, as foreseen by the very large NP value calculated for both sediments, much greater than the calculated AP (Table 1). These characteristics therefore prevent any acidity being generated in the sediment following oxidation of the sulfides. We also observed that in the same pH and ORP environmental conditions as those of the weathering cells, Cu and Zn are re-adsorbed rapidly after release by the organic matter, the organo-clay complexes or the Fe/Mn oxides [START_REF] Caille | Solubility of metals in an anoxic sediment during prolonged aeration, Science of The Total EnvironmentSci[END_REF][START_REF] Stephens | Changes in the leachability of metals from dredged canal sediments during drying and oxidation[END_REF][START_REF] Lions | Zinc and cadmium mobility in a 5-year-old dredged sediment deposit: Eexperiments and modelling[END_REF]Tack, 2016). In particular, Zn is known to be adsorbed in a reversible way between the iron oxihydroxides and the organic matter after oxidation of the metal sulfides [START_REF] Piou | Changes in the geochemistry and ecotoxicity of a Zn and Cd contaminated dredged sediment over time after land disposal[END_REF]. Therefore, even though the sediments are strongly buffered, it is necessary to prevent all risk of leaching of the pollutants they contain by other mechanisms such as ORP modification, or by percolation of a chelating agent [START_REF] Bäckström | Mobilisation of heavy metals by deicing salts in a roadside environment[END_REF][START_REF] Mayer | Geochemistry and toxicity of sediment porewater in a salt-impacted urban stormwater detention pond[END_REF]. A treatment could be envisaged, even valorization, for example in a road building material, or in civil engineering by treatment with hydraulic binders [START_REF] Paria | Solidification-stabilization of organic and inorganic contaminants using portland cement: a literature review[END_REF][START_REF] Pinto | Environmental impact of the use of contaminated sediments as partial replacement of the aggregate used in road construction[END_REF]Wang et al., 2012;Couvidat et al., 2016a;[START_REF] Bao | Changes in speciation and leaching behaviors of heavy metals in dredged sediment solidified/stabilized with various materials[END_REF][START_REF] Saussaye | Trace element mobility in a polluted marine sediment after stabilisation with hydraulic binders[END_REF].

Conclusion

The characterization of dredged sediment is essentially done in order to choose and ensure the right management strategy. Both sediments studied possess a mineralogical composition typical of marine sediments. They are essentially constituted of quartz, aluminosilicates, evaporites (halite) and carbonates (37 and 52 wt.% in the unweathered and naturally-weathered sediments, respectively). The two sediments contain framboïdal pyrite which shows significant signs of oxidation. In the weathered sediment, the pyrite seems to be preserved in the agglomerates composed of aluminosilicate minerals. The unweathered sediments contain organic matter, PAHs, organotin compounds and PCBs. the weathering of the unweathered sediment in the open air and bioremediation led to an evolution in the organic matter (degradation), a decrease in the PAHs and organotins, whereas the PCBs are preserved as they are more persistent.

The quantity of metals appears high, in particular for copper which reaches 1445 and 835 mg/kg, lead at 760 and 1260 mg/kg, and zinc at 2085 and 2550 mg/kg in the unweathered and naturally-weathered sediments, respectively. Only copper sulfides are detected as chalcopyrite and covellite, and zinc is found associated with sulfur but not in the form of sphalerite or sulfates. Cu is also present in its native form. However, lead is not found in any mineral form. Zn and Cu are also associated in aggregates composed of aluminosilicate minerals and refractory organic matter. The latter prevent pyrites from being oxidized, in particular in the weathered sediment.

The leaching test in weathering cells revealed the low potential for release of Cu, Pb and Zn. The presence of carbonates in large quantities in the two sediments enabled leachates to have a neutral pH during the whole lixiviation test, as indicated by the elevated NP. As the AP is lower than the NP, we can suppose that this sediment will not release acidic leachates. Even if this is the case, in order to prevent the dispersion of the contaminants by other possible mechanisms, a treatment and/or valorization could be envisaged, in civil engineering or the road-building domain, for example (Couvidat et al., 2016a;[START_REF] Saussaye | Trace element mobility in a polluted marine sediment after stabilisation with hydraulic binders[END_REF][START_REF] Bao | Changes in speciation and leaching behaviors of heavy metals in dredged sediment solidified/stabilized with various materials[END_REF].

Queries and Answers

Query:

Your article is registered as belonging to the Special Issue/Collection entitled "AquaConsoil 2017". If this is NOT correct and your article is a regular item or belongs to a different Special Issue please contact p.das@elsevier.com immediately prior to returning your corrections.

Answer: Yes

Query:

Please confirm that given names and surnames have been identified correctly and are presented in the desired order, and please carefully verify the spelling of all authors' names.

Highlights

• In-depth study of contaminated sediments is advised for accurate management.

• Reactive mineral species in particular framboïdal pyrite were observed in materials.

• The natural weathering has led to a significant decrease in PAHs and organotins.

• The leaching test revealed the low potential for release of Cu, Pb and Zn.

• Size separation and/or a valorization in civil engineering could be envisaged.

Graphical abstract

alt-text: Image 1

Answer: Yes

Query:

The author names have been tagged as given names and surnames (surnames are highlighted in teal color). Please confirm if they have been identified correctly.

Answer: Yes

Query:

Please check and confirm if the authors' affiliations are presented correctly and amend as necessary.

Answer: I confirm that it is correct.

Query:

One parenthesis has been deleted to balance the delimiters. Please check and confirm if this was done correctly.

Answer: Yes

Query:

The data "IRME" has been deleted to avoid redundancy. Please check if the deletion is appropriate and amend as necessary.

Answer: I confirm that it is correct.

Query:

Please check the hierarchy of the section headings and confirm if correct.

Answer: Yes

Query:

The citation "European Council, 2002" has been linked to reference "Commission decision of 3 may 2000 replacing Decision 94/3/EC establishing a list of wastes, consolidated version of 01 january 2002 (2000D0532)". Please check if appropriate and amend as necessary.

Answer: I confirm that it is correct.

Query:

The citation "French Official Journal, 2007" has been linked to reference "JORF n°240 du 16 octobre 2007 p.17002 texte n°1". Please check if appropriate and amend as necessary.

Answer: I confirm that it is correct.

Query:

The citation " [START_REF] Sobek | Field and lLaboratory mMethods aApplicable to oOverburden and mMinesoils[END_REF]" has been changed to [START_REF] Sobek | Field and lLaboratory mMethods aApplicable to oOverburden and mMinesoils[END_REF]" to match the author name/date in the reference list. Please check if the change is fine and amend if necessary.

Answer: I confirm that it is correct.

Query:

Please check if the insertion of "2008" in this reference item is correct and amend as necessary.

Answer: I confirm that it is correct.

Query:

Please check if the insertion of "1997" in this reference item is correct and amend as necessary.

Answer: I confirm that it is correct.

Query:

Please provide the volume number and page range for the bibliography in [START_REF] Morabito | Temporal evolution of cadmium, copper and lead concentration in the Venice Lagoon water in relation with the speciation and dissolved/particulate partition[END_REF] Answer: In press, https://doi.org/10.1016/j.marpolbul.2017.10.043


Mohab Safey

El Din

Zhi-Hong Yang

Lihong Zhi

On the complexity of computing real radicals of polynomial systems

Let f = (f 1 , . . . , f s ) be a sequence of polynomials in Q[X 1 , . . . , X n ] of maximal degree D and V ⊂ C n be the algebraic set defined by f and r be its dimension. The real radical re f associated to f is the largest ideal which defines the real trace of V . When V is smooth, we show that re f , has a finite set of generators with degrees bounded by deg V . Moreover, we present a probabilistic algorithm of complexity (snD n ) O(1) to compute the minimal primes of re f . When V is not smooth, we give a probabilistic algorithm of complexity s O(1) (nD) O(nr2 r ) to compute rational parametrizations for all irreducible components of the real algebraic set V ∩ R n . Experiments are given to show the efficiency of our approaches.

Introduction

Let Q, R and C be the fields of rational, real and complex numbers and X = (X 1 , . . . , X n ) be a sequence of variables.

For f = (f 1 , . . . , f s ) in Q[X] := Q[X 1 , . . . , X n ], we denote by f the ideal generated by f in Q[X]. For K = C or R, we let V K (f ) := {x ∈ K n | f 1 (x) = 0 . . . , f s (x) = 0}. The radical ideal of f is the vanishing ideal of the algebraic set V C (f ) ⊂ C n .

The real radical re f of f in Q[X] is defined as the set of polynomials g ∈ Q

[X] such that g 2m + l i=1 a 2 i ∈ f for m, l ∈ N, a i ∈ Q[X]. An ideal I ⊂ Q[X]
is said to be real if it equals its real radical, that is, I = re √ I. The Real Nullstellensatz (see e.g. [START_REF] Neuhaus | Computation of real radicals of polynomial ideals -II[END_REF]) states that re f is equal to the vanishing ideal of V R (f ). Hence, representing the real radical associated to f provides some insight on the geometry of V R (f ).

Computing real radicals has attracted much attention both on the symbolic and numerical side. Symbolic algorithms were developed at first in [START_REF] Becker | Computation of real radicals of polynomial ideals[END_REF].

Later [START_REF] Neuhaus | Computation of real radicals of polynomial ideals -II[END_REF] proposed a revised form of this algorithm and gave an upper bound D 2 O(n 2 ) for the degree of the generators of re f , where D = max{deg f 1 , . . . , deg f s }. [START_REF] Spang | On the computation of the real radical[END_REF][START_REF] Spang | A zero-dimensional approach to compute real radicals[END_REF] implemented this algorithm and improved its efficiency by avoiding some linear changes of coordinates. This algorithm is based on properties of isolated points of real algebraic sets and computation of real radicals of zero-dimensional ideals. Instead of computing real radicals, [START_REF] Chen | Triangular decomposition of semi-algebraic systems[END_REF][START_REF] Chen | Triangular decomposition of semi-algebraic systems[END_REF][START_REF] Chen | Computing with semi-algebraic sets represented by triangular decomposition[END_REF] give a method to decompose semi-algebraic systems into regular semi-algebraic systems.

On the numerical side, [START_REF] Lasserre | Semidefinite characterization and computation of zero-dimensional real radical ideals[END_REF][START_REF] Lasserre | Moment matrices, border bases and real radical computation[END_REF] presented an algorithm based on moment relaxations to compute zero-dimensional real radicals in R[X]. Subsequently, [START_REF] Ma | A certificate for semidefinite relaxations in computing positive-dimensional real radical ideals[END_REF] generalized this algorithm to positive dimensional cases. [START_REF] Brake | Validating the completeness of the real solution set of a system of polynomial equations[END_REF] gave a method based on numerical algebraic geometry and sums of squares programming to certify that a set of polynomials generates the real radical. We emphasize that these algorithms compute real radicals in R[X] and hence return approximate encodings of those radicals. To see this, consider a univariate polynomial f ∈ Q[X 1 ] with a single irrational real root ρ. The real radical of f is generated by X 1 -ρ. The aforementioned algorithms based on numerical computations use an approximation of ρ to encode the output. By contrast, symbolic algorithms return real radicals with base field Q and in the example we just considered would simply return f .

In this paper, we focus on symbolic algorithms for computing generators or lazy representations (see Definition 2) for real radicals in Q[X] with a focus on complexity issues.

Main results. All in all, we improve the complexity bound D 2 O(n 2 ) for computing real radicals. When V C (f ) is smooth, we use polynomial system solving techniques in [START_REF] Jeronimo | The computational complexity of the Chow form[END_REF][START_REF] Blanco | Computing generators of the ideal of a smooth affine algebraic variety[END_REF][START_REF] El Din | Finding sampling points on real hypersurfaces is easier in singular situations[END_REF] to obtain an algorithm running in time polynomial in snD n .

Theorem 1. Let f = (f 1 , . . . , f s ) ⊂ Q[X 1 , . . . , X n ] with D = max(deg(f i ), i = 1, . . . , s)
encoded by a straight-line program Γ. Assume that V C (f ) is smooth, of dimension r and of degree δ. There exists a probabilistic algorithm which takes as input Γ and returns generators of each minimal associated prime of re f with maximum degree δ. In case of success, the algorithm uses (snD n ) O(1) arithmetic operations in Q.

When V = V C (f ) is not smooth and has dimension r, we obtain an algorithm using s O(1) (nD) O(nr2 r ) arithmetic operations in Q to represent the irreducible components of re f . Hence for fixed r, it is singly exponential in n by contrast to previous results. The difficulty in the non-smooth case is that the real algebraic set V R (f ) might be embedded in the singular locus of V , or even worse, in the singular locus of the singular locus of V , etc. Using the Jacobian criterion and Gröbner bases to compute the vanishing ideal of the singular locus of V , would result in the complexity D 2 O(n 2 ) as in [START_REF] Neuhaus | Computation of real radicals of polynomial ideals -II[END_REF]. To bypass complexity issues, we use techniques developed in the last decades to represent algebraic sets. Such techniques, which are now standard in computer algebra, consist in representing an equidimensional algebraic set V ⊂ C n outside a Zariski closed set, hence often restricting to a subset of V which is a complete intersection. There are two main such representations, either triangular setsWu (1984); [START_REF] Wang | Decomposing polynomial systems into simple systems[END_REF] (also known as regular chainsKalkbrener (1991), tower of simple extensionsLazard (1991), regular setMoreno Maza (1997)) or rational parametrizations (also known as geometric resolutions)(see e.g. [START_REF] Giusti | A Gröbner free alternative for polynomial system solving[END_REF]; [START_REF] Lecerf | Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers[END_REF]; [START_REF] Schost | Computing parametric geometric resolutions[END_REF]; Safey El Din and [START_REF] El Din | A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets[END_REF]). The following definition is folkore. . . . , T r+1 ] such that the following holds: the variables T 1 , . . . , T r+1 are new and w is square-free and monic and of degree δ in each variable T 1 , . . . , T r+1 and, for 1

Definition 2. An r-dimensional rational parametrization Q = ((w, v 1 , . . . , v n ), ) in Q[T 1 , . . . , T r+1 ] of degree δ consists of the following: • a sequence of polynomials (w, v 1 , . . . , v n ) in Q[T 1 ,
≤ i ≤ n, deg(v i , T r+1 ) < deg(w, T r+1 ). • = (λ 1 , . . . , λ r+1 ) is a sequence of linear forms in variables X 1 , . . . , X n such that λ i (v 1 , . . . , v n ) = T i ∂w ∂T r+1 mod w. The corresponding algebraic set Z(Q) ⊂ C n is the Zariski closure of the locally closed set of points (x 1 , . . . , x n ) ∈ C n such that ∃ϑ ∈ C r+1 , w(ϑ) = 0, ∂w ∂T r+1 (ϑ) = 0, x i = v i ∂w/∂T r+1 (ϑ).
Observe that Z(Q) is equidimensional (using the Jacobian criterion) and that the Zariski closure of the image of Z(Q) by the map x → (λ 1 (x), . . . , λ r+1 (x)) is defined by w = 0. Furthermore, the polynomial w is called the eliminating polynomial of the parametrization. Besides, the degree of w coincides with the degree of Z(Q) (see [START_REF] Giusti | A Gröbner free alternative for polynomial system solving[END_REF]; [START_REF] Lecerf | Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers[END_REF]). Finally, observe also that the parametrization ((1)) encodes the empty set. Equidimensional decompositions of algebraic sets whose components are represented by such parametrizations can be efficiently computed using [START_REF] Lecerf | Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions[END_REF]. This is a key ingredient for the proof of the result below.

Theorem 3. Let f = (f 1 , . . . , f s ) ⊂ Q[X 1 , . . . , X n ]
of degrees bounded by D. Let r be the maximum of 1 and the dimension of the algebraic set V C (f ). Then, there exists a probabilistic algorithm LazyRealRadical which takes as input f and returns rational parametrizations of the minimal associated primes of re f using s O(1) (nD) O(nr2 r ) arithmetic operations in Q.

Plan of the paper. In Section 2, we introduce some basic notions that will be used throughout the paper. In Section 3, we present an algorithm for computing generators of real radicals under the smoothness assumption and show the correctness and the complexity of the algorithm. In Section 4, we give a probabilistic algorithm to compute rational parametrizations for all irreducible components of an arbitrarily given real algebraic set. The last section is devoted to practical experiments.

Preliminaries

Ideals and varieties

For basic notions related to affine and projective spaces, ideals and algebraic sets (and their irreducible components), as well as equidimensionality we refer to [START_REF] Cox | Ideals, varieties, and algorithms[END_REF]. For basic definitions on real algebraic sets and semi-algebraic sets, we refer to [START_REF] Bochnak | Real algebraic geometry[END_REF]. In the sequel, we use the following notations.

We denote by P n (C) the n-dimensional projective space over C. A subset of P n (C) is called a projective algebraic set if it is the set of common zeros of some homogeneous polynomials in Q[X 0 , X 1 , . . . , X n ].

Let S ⊂ C n , we denote by S the Zariski closure of S which is the smallest algebraic set containing S; we denote by I (S) the vanishing ideal of S which is the set of all polynomials in Q[X 1 , . . . , X n ] vanishing identically over S.

Let V ⊂ C n be an algebraic set. Let I (V ) = f 1 , . . . , f s ⊂ Q[X] and p be a point of V . The tangent space of V at p, denoted by T p (V ), is given by T p (V ) := s j=1 x ∈ C n n i=1 ∂f j ∂X i (p)x i = 0 . The dimension of V at p, denoted by dim p V , is the maximum dimension of an irreducible component of V containing p. The point p is said to be non-singular (or regular) at V if dim T p (V ) = dim p V . Otherwise, p is called a singular point of V . The singular locus of V is the set Sing(V ) := {p ∈ V | p is a singular point of V }. We say that V is smooth if V has no singular point, that is, Sing(V ) = ∅.

All the notions above can be similarly defined for real algebraic sets in R n and projective algebraic sets in P n (C).

Let W ⊂ C n be an irreducible algebraic set and r := dim W . The degree deg W of W is sup{#(H 1 ∩ . . . ∩ H r ∩ W )} where H 1 , . . . , H r are hyperplanes in C n meeting W at finitely many points. If W is not irreducible, then its degree is defined to be the sum of the degrees of all its irreducible components.

Chow forms

We recall the definition of Chow forms (Gelfand et al., 1994, Chapter 3). Let V ⊂ P n (C) be an irreducible projective set, where dim V = r. For i = 0, . . . , r, we denote by

U i = (U i0 , . . . , U in ) a group of n + 1 variables and U := (U 0 , . . . , U r ). Let L i = U i0 X 0 + . . . + U in X n , i = 0, . . . , r. The Chow form of the projective set V is the unique (up to a scalar factor) irreducible polynomial F V ∈ Q[U ] such that for any u 0 , . . . , u r ∈ C n+1 , F V (u 0 , . . . , u r ) = 0 ⇔ V ∩ {L 0 (u 0 , X) = 0, . . . , L r (u r , X) = 0} = ∅ where L i (u i , X) = u i0 X 0 + • • • + u in X n , i = 0, . . . , r.
Let W ⊂ P n (C) be an equidimensional projective set and W i be its irreducible components (1 ≤ i ≤ ). The Chow form of W is defined as

F W = i=1 F W i , where F W i is the Chow form of W i .
This definition can be extended to equidimensional affine algebraic sets in C n . Assume that we are given a finite sequence of polynomials f = (f 1 , . . . , f s ) in Q[X 1 , . . . , X n ] and let f h i be the homogenization of f i using the new variable X 0 . Denote Cox et al., 1992, Chapter 8 ). The Chow form of V is defined to be the Chow form of its projective closure in P n (C) (see [START_REF] Jeronimo | The computational complexity of the Chow form[END_REF], Section 1.1).

f h = (f h 1 , . . . , f h s ). Then the affine algebraic set V := V C (f ) can be identified with a subset of P n (C) which is V C (f h ) \ V C (X 0 ), and the projective closure of V is the smallest projective algebraic set containing V C (f h ) \ V C (X 0 ) (see
3 Algorithm for the smooth case

Preliminary results

Let V be a smooth and equidimensional algebraic set in C n defined by polynomials in Q[X] and let m := (n -dim V )(1 + dim V ). It has been shown in (Blanco et al., 2004, Theorem 10 and Corollary 17) that there exist polynomials g 1 , . . . , g m with deg g i ≤ deg V such that g 1 , . . . , g m generate the ideal I (V ). Moreover, the polynomials g 1 , . . . , g m can be obtained by specializing the Chow form of V at some generic linear forms with rational coefficients (see [START_REF] Blanco | Computing generators of the ideal of a smooth affine algebraic variety[END_REF], Section 4) for details). We slightly generalize this result.

Theorem 4. Let V be a smooth algebraic set in C n of degree δ. There exists a finite set of polynomials

G = (g 1 , . . . , g s ) ⊂ Q[X] with max(deg(g i ), i = 1, . . . , s) ≤ δ such that G = I (V ).
Proof. Set r = dim(V ) and V = r i=0 V i be the minimal equidimensional decomposition of V , where V i is either empty or i-equidimensional. Let m i := (n -i)(i + 1), for i = 0, . . . , r. By (Blanco et al., 2004, Theorem 10 and Corollary 17), there exist polynomials g

(i) 1 , . . . , g (i) m i with degrees bounded by deg V i such that I (V i ) = g (i) 1 , . . . , g (i)
m i , for i = 0, . . . , r. Since V is smooth, according to (Cox et al., 1992, §9.6, Theorem 8), we have V i ∩ V j = ∅ for any 0 ≤ i < j ≤ r. Then I (V i )+I (V j ) = 1 for all 0 ≤ i < j ≤ r and therefore

I (V ) = r i=0 I (V i ) which equals g (0) j 0 • • • g (r) jr | 1 ≤ j 0 ≤ m 0 , . . . , 1 ≤ j r ≤ m r . Moreover, deg g (0) j 0 • • • g (r) jr ≤ deg V 0 +• • •+deg V r = δ. Let G := g (0) j 0 • • • g (r) jr | 1 ≤ j 0 ≤ m 0 , . . . , 1 ≤ we have G = I (V ) = √ I and deg(g) ≤ δ for all g ∈ G.
We recall now a well-known criterion for testing whether a given prime ideal is real.

Proposition 5. (Marshall, 2008, Theorem 12.6.1) Let I be a prime ideal in Q[X], then I is real if and only if I has a non-singular real zero.

Theorem 6. Let f be a finite polynomial sequence of Q[X] and V := V C (f ) of degree δ. If V is smooth, then re f has a finite set of generators G ⊂ Q[X] with deg(g) ≤ δ for g ∈ G.
Proof. Let V = s i=1 V i be the minimal irreducible decomposition of V . Note that for i = 1, . . . , s, V i is smooth (because V is) and

I (V i ) is prime. W.l.o.g. we assume that V ∩ R n = ∅ since otherwise the conclusion is trivial. Let Ω := {V j | V j ∩ R n = ∅, 1 ≤ j ≤ s}. If V j ∈ Ω,
then the prime ideal I (V j ) has at least one non-singular real zero because V j is smooth and V j ∩ R n = ∅. Therefore, according to Proposition 5, I (V j ) is real for every

V j ∈ Ω. Now we have I V ∩ R n = I (V ∩ R n ) = I V j ∈Ω (V j ∩ R n ) which equals V j ∈Ω I (V j ∩ R n ) = V j ∈Ω I (V j ), where V ∩ R n is the Zariski closure of V ∩ R n in C n
, and the last equality follows from the fact that I (V j ) is real. Note that the first equality holds because for any subset S of C n , S and its Zariski closure S have the same vanishing ideal (see Cox et al., 1992, §4.4)

. It follows that I V ∩ R n and V j ∈Ω I (V j ) define the same algebraic set, that is, V ∩ R n = V j ∈Ω V j . Then, deg(V ∩ R n ) = V j ∈Ω deg V j ≤ s i=1 deg V i = deg V.
(1)

By the Real Nullstellensatz, re f = I (V ∩ R n ). We already observed that I V ∩ R n = I (V ∩ R n ). Hence, we have re f = I V ∩ R n . Moreover, V ∩ R n is smooth because V is smooth.
The conclusion follows from Theorem 4 and the inequality (1).

Algorithm description

Let f = (f 1 , . . . , f s ) ⊂ Q[X]
, and assume that V = V C (f ) is smooth of dimension r. Write the minimal equidimensional decomposition of V as V = r i=1 V i , where V i is either empty or is i-equidimensional. Denote by f h 1 , . . . , f h s the homogenizations of f 1 , . . . , f s using the new variable X 0 . Our algorithm uses several subroutines for computing generators of real radicals when V = V C (f ) is smooth.

• PointsPerComponents. It takes as input polynomials f 1 = 0, . . . , f s = 0 and returns a set of real points meeting every connected component of V R (f 1 , . . . , f s ) (see Safey El Din, 2005).

• Equidim. It takes as input homogeneous polynomials f h 1 , . . . , f h s , g ∈ Q[X 0 , . . . , X n ] and returns the Chow forms of all equidimensional components of [START_REF] Jeronimo | The computational complexity of the Chow form[END_REF]).

V C (f h 1 , . . . , f h s ) \ V C (g) (see
• Generators. It takes as input a Chow form F V i of some equidimensional algebraic set V i and returns a set of generators of the radical ideal I (V i ) (see [START_REF] Blanco | Computing generators of the ideal of a smooth affine algebraic variety[END_REF].

Let V i ⊂ C n be an equidimensional component of V and V h i ⊂ P n denote the projective closure of V i . Let V i = m i j=1 V ij be the minimal irreducible decomposition of V i . Then V h i = m i j=1 V h ij , where V h ij is the projective closure of V ij .
We can compute the Chow form F V i of V i by the subroutine Equidim. According to the definition of the Chow form,

F V i = m i j=1 F V ij .
Therefore we can compute the Chow forms of all the irreducible components of V i by factorizing F V i over Q. The following is the algorithm mentioned in Theorem 1.

RealRadicalSmooth(f ) 1. S = PointsPerComponents(f = 0); 2. if S = ∅, then return {1}; 3. {F V 0 , . . . , F Vr } = Equidim(f h , X 0 ); 4. for 0 ≤ i ≤ r do {F V i1 , . . . , F V im i } ← irreducible factors of F V i ; 5. Ω = {}; 6. for 0 ≤ i ≤ r and 1 ≤ j ≤ m i do G ij = Generators(F V ij ); if V C (G ij ) ∩ S = ∅ then Ω = Ω ∪ {G ij };
7. return Ω.

Proof of Theorem 1

Probabilistic aspects. The algorithms used in Step 1,3,4,6 are probabilistic. The probability of success of these algorithms depends on choices of points in Q n O(1) , and there exist a Zariski open set in Q n O(1) such that for all choices in this set yield correct answers for these algorithms in RealRadicalSmooth. In the following, we assume that all the probabilistic calls mentioned above perform correctly. Correctness of algorithm RealRadicalSmooth. Let V ij := V C (G ij ). Since V is smooth, by (Cox et al., 1992, §9.6, Theorem 8), its irreducible components V ij do not intersect each other. Hence for each nonempty real algebraic set

V ij ∩ R n , it contains at least one connected component of V R (f ), which implies that V ij ∩ R n = ∅ if and only if V ij ∩ S = ∅.
On the other hand, the prime ideal (Neuhaus, 1998, Lemma 2.2(a)). Finally, the ideals I (V ij ) are exactly the prime components of re f since V ij are irreducible components of V C (f ). The correctness of the algorithm is proved. Complexity analysis. The first step of RealRadicalSmooth computes a finite set S of real points meeting every connected component of the real algebraic set V R (f ). Many algorithms can be used (see Safey El Din and [START_REF] Schost | Computing parametric geometric resolutions[END_REF][START_REF] El Din | Properness defects of projections and computation of at least one point in each connected component of a real algebraic set[END_REF]; Safey El Din (2005, 2007b,a)). Using Safey El Din (2007a) and by the complexity analysis in Safey El Din (2005), Step 1 uses sL(nD n ) O(1) arithmetic operations in Q where L is the length of the straight-line program Γ.

I (V ij ) is real if and only if V ij ∩ R n = ∅ (see the proof of Theorem 6). Thus, I (V ij ) is real if and only if V ij ∩ S = ∅. Then we have re f = V ij ∩S =∅ I (V ij )
Next, by [START_REF] Jeronimo | The computational complexity of the Chow form[END_REF], Theorem 1), computing the Chow forms of all equidimensional components of

V C (f h 1 , . . . , f h s )\V C (X 0 ) requires at most sL(nD n ) O(1) arithmetic operations in Q. The Chow forms {F V 0 , . . . , F Vr } computed in
Step 3 are encoded by straight-line programs of length bounded by sL(nD n ) O(1) (Jeronimo et al., 2004, Section 3.5).

Suppose that the straight-line program encoding F V i has length L i , then the cost of factorizing F V i over Q is polynomial in L i and the total degree of F V i [START_REF] Kaltofen | Factorization of polynomials given by straight-line programs[END_REF][START_REF] Kaltofen | Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators[END_REF]. Note that the total degree of F V i is bounded by (i + 1)D n , so

Step 4 can be done using at most (sLn(r +1)D n ) O(1) arithmetic operations in Q. Observe that r ≤ n -1, we can bound (sLn(r + 1)D n ) O( 1) by (sLnD n ) O(1) .

The cost of computing generators G ij of I (V ij ) from the Chow form F V ij does not increase the order of the complexity of Step 4 (Blanco et al., 2004, Section 5.5). Deciding the emptiness of V C (G ij ) ∩ S is done by evaluating the polynomials of G ij at all points of S, and its cost is negligible. Observe that L is bounded by O(s(nD) n ) (see e.g. [START_REF] Krick | Straight-line programs in polynomial equation solving[END_REF]). Therefore, in case of success, the algorithm RealRadicalSmooth uses (snD n ) O(1) arithmetic operations in Q.

Lazy representations and non-smooth case 4.1 Preliminary results

The following result is folklore and extracted from [START_REF] Durvye | A concise proof of the Kronecker polynomial system solver from scratch[END_REF]; [START_REF] Lecerf | Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers[END_REF].

Lemma 7. Let V ⊂ C n be an equi-dimensional algebraic set defined over Q of dimension r. There exists a non-empty Zariski open set G (V ) ⊂ C n×(r+1) such that for ∈ G (V ) ∩ Q n×(r+1) the following holds. There exists a sequence of polynomials (w, v 1 , . .

. , v n ) in Q[T 1 , . . . , T r+1 ] such that Z(Q) = V with Q = ((w, v 1 , . . . , v n ), ).
Let Q = ((w, v 1 , . . . , v n ), = (λ 1 , . . . , λ r+1 )) be a rational parametrization. We define the polynomial σ Q as the one obtained by substituting the variables T 1 , . . . , T r+1 with the λ 1 , . . . , λ r+1 in ∂w ∂T r+1 . We denote by S(Q) the intersection of Z(Q) with V C (σ Q ). The following lemma is pointed out as a remark in the conclusion of [START_REF] Lecerf | Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions[END_REF].

Lemma 8. Under the above notations, the ideal associated to

Z(Q) in Q[X 1 , . . . , X n ] is prime if and only if w is irreducible over Q. Lemma 9. Assume that the vanishing ideal of Z(Q) in Q[X] is prime.
Then, it is real if and only if one of the following equivalent conditions are satisfied:

(i) Z(Q) contains a real regular point;

(ii) the semi-algebraic set defined by w = 0, ∂w ∂T r+1 = 0 is non-empty.

In particular, if the vanishing ideal of

Z(Q) is not real, then Z(Q) ∩ R n coincides with S(Q) ∩ R n .
Proof. We denote h = ∂w ∂T r+1 and I the vanishing ideal of Z(Q). By (Marshall, 2008, Theorem 12.6.1) I is real if and only if it has a regular real zero which is equivalent to the assertion that Z(Q) contains a regular real point. Now we prove that the condition (ii) holds if and only if I is real. Without loss of generality, we assume that the linear forms λ i = X i for i = 1, . . . , r + 1. Then T i = X i for i = 1, . . . , r + 1.

If the semi-algebraic set defined by w = 0, h = 0 is not empty, that is, there exists ϑ ∈ R r+1 such that w(ϑ) = 0 and h(ϑ) = 0, then we have a real point x = v 1 h (ϑ), . . . , vn h (ϑ) ∈ Z(Q). It follows from the definition of Z(Q) and the Hilbert Nullstellensatz that the polynomials w, hX r+2 -v r+2 , . . . , hX n -v n belong to I. Then x is a regular real zero of I because the Jacobian matrix of w, hX r+2 -v r+2 , . . . , hX n -v n has rank n -r at the point x. Thus the ideal I is real.

Conversely, if the set {ϑ ∈ R r+1 | w(ϑ) = 0, h(ϑ) = 0} is empty, then we have Z(Q) ∩ R n ⊂ Z(Q) ∩ V C (σ Q ). On the other hand, Z(Q) ∩ V C (σ Q ) has dimension less than dim(Z(Q)) (since Z(Q) is irreducible and Z(Q) ∩ V C (σ Q ) is strictly contained in Z(Q)). Hence Z(Q) ∩ R n has dimension less than dim(Z(Q)), which implies that the vanishing ideal of Z(Q) is not real.
From the proof of Lemma 9, we immediately have the following corollary:

Corollary 10. Under the above notations, assume that Z(Q) is irreducible, then S(Q) has dimension strictly less than dim(Z(Q)).

Subroutines

In this paragraph, we describe the subroutines used in the main algorithm. operations in a univariate power series ring Q[[T 1 -y 1 ]] (where y 1 is chosen randomly) by applying (Poteaux and Schost, 2013, Lemma 2). Doing this allows us to use the algorithm designed for the zero-dimensional case but performing operations in Q[[T 1 -y 1 ]] and truncate computations up to deg(Q) + 1. The extra cost of such a strategy is just the extra cost induced by the arithmetics in Q

[[T 1 -y 1 ]].
To tackle the r-dimensional case, we do the same but using power series ring Q[[T 1y 1 , . . . , T r -y r ]] where y 1 , . . . , y r are chosen randomly and truncating computations again up to the degree of Q. Again the extra cost comes from arithmetic operations in Q[[T 1y 1 , . . . , T r -y r ]] which is dominated by (nδ) O(r) since computations are truncated up to deg(Q) + 1. Now, changing r + 1 linear forms requires to perform the above operations r + 1 times.

Subroutine Intersect Let Q = ((w, v 1 , . . . , v n ), ) with = (λ 1 , . . . , λ r+1 ) be a rational parametrization in Q[T 1 , . . . T r+1 ] and g ∈ Q[T 1 , . . . T r+1 ]. We denote by g Q the polynomial g(λ 1 , . . . , λ r+1 ) ∈ Q[X]. A key step for our algorithm is to compute Z(Q) ∩ V C (g Q ) Lemma 14. Let Q = ((w, v 1 , . . . , v n ), ) be a rational parametrization in Q[T 1 , . . . , T r+1 ]
encoding an equidimensional algebraic set Z = Z(Q) ⊂ C n of dimension r ≥ 1 and degree δ and let g be a polynomial in Q[T 1 , . . . , T r+1 ] of degree δ . Assume that the intersection of Z with V C (g Q ) has dimension r -1. There exists an algorithm Intersect which on input (Q, g) outputs a list of rational parametrizations encoding the irreducible components of

Z ∩ V C (g Q ) in time (n max(δ, δ )) O(r) .
Proof. The algorithm starts by choosing randomly a sequence of r + 1 linear forms = (λ 1 , . . . , λ r+1 ) in X 1 , . . . , X n assuming that lies in the non-empty Zariski open set G (Z) (defined in Lemma 7).

Recall that Z is r-equidimensional. Observe that by Krull's theorem [START_REF] Eisenbud | Commutative Algebra: with a View Toward Algebraic Geometry[END_REF], Z ∩ V C (g Q ) is either empty or has dimension greater than or equal to r -1 and hence none of its irreducible components has dimension less than r -1. Since, by assumption, dim(Z ∩ V C (g Q )) = r -1, we deduce that it is equidimensional (of dimension r -1).

Hence, it makes sense to assume additionally that the first r linear forms of lie in the non-empty Zariski open set G (Z ∩V C (g Q )) (see again Lemma 7). Another assumption of the same nature will be done and stated precisely below.

Next, one computes a rational parametrization Q = ((w , v 1 , . . . , v n ), ) defining Z. For clarity, we denote by T 1 , . . . , T r+1 the variables involved in Q . Lemma 13 establishes that this step can be performed using (r + 1)(nδ) O(r) arithmetic operations in Q. Now, we want to compute a rational parametrization of the intersection of

Z = Z(Q ) with V C (g Q ).
The process we would like to mimic is as follows:

1. substitute in g the variables T 1 , . . . , T r+1 by the linear forms λ 1 , . . . , λ r+1 used in Q (hence yielding an explicit representation of g Q );

2. substitute the X i 's by their parametrizations in Q , hence obtaining a rational fraction g (it lies in Q(T 1 , . . . , T r+1 ));

3. compute a representation of the intersection of the vanishing sets of the numerator of g and w (through subresultant computations as in [START_REF] Giusti | A Gröbner free alternative for polynomial system solving[END_REF]) and deduce from that a rational representation of Z ∩ V C (g Q ).

Carrying out directly these steps without taking care of denominators does not allow us to obtain the announced complexity statement.

To achieve the announced complexity bound, we use a classical evaluation interpolation technique: that will allow us to obtain a better control on the monomial combinatorics and handle the presence of denominators.

Instead of computing an explicit representation of g Q , we will actually build a straightline program Γ evaluating it. Since g is a polynomial of degree δ involving r + 1 variables and since is composed of r+1 linear forms in X 1 , . . . , X n which are equal to T 1 , . . . , T r+1 , the length of such a straight-line program is bounded by (rδ ) O(r) + O(nr).

Evaluating the rational fraction g defined above is then obtained by stacking to Γ the parametrizations

X i = v i ∂w /∂T r+1
. Evaluating all parametrizations can be done using (nδ) O(r) operations in Q (because the polynomials in Q have degree ≤ δ and involve r +1 variables). In the end, one can evaluate g using (rδ ) O(r) + O(nr) + (nδ) O(r) arithmetic operations in Q.

Now take y = (y 1 , . . . , y r-1 ) in Q r-1 . Substituting the variables T 1 , . . . , T r-1 by y 1 , . . . , y r-1 in g is done thanks to the procedure described above in time (rδ ) O(r) + O(nr) + (nδ) O(r) .

For y as above, we denote by g y the obtained rational fraction. Similarly, Q y denotes the rational parametrization obtained by substituting the variables T 1 , . . . , T r-1 with y 1 , . . . , y r-1 in Q .

Using the intersection algorithm of [START_REF] Giusti | A Gröbner free alternative for polynomial system solving[END_REF] with input Q y and the numerator of g y , one computes a zero-dimensional rational parametrization encoding

Z ∩ V C (g Q ) ∩ V C ( y ).
Since, by Bézout's theorem, the intersection of Z with V C (g Q ) has degree bounded by δ δ, it is sufficient to repeat this process (δ δ) O(r) times to interpolate a rational parametrization for Z∩V C (g Q ). The last step consists in extracting from that parametrization the irreducible components of Z ∩ V C (g Q ) by factoring the eliminating polynomial of Q. The complexity statement follows easily.

Subroutine RemoveRedundantComponents Let L = (Q 1 , . . . , Q t ) be a list of rational parametrizations such that, for 1

≤ i ≤ t, Z(Q i ) is irreducible. The routine RemoveRedundantComponents returns a subset of L say, Q i 1 , . . . , Q i k such that, Z(Q i 1 ∪ • • • ∪ Z(Q i k ) = Z(Q 1 ) ∪ • • • ∪ Z(Q t ) and, for u = v, Z(Q iu ) ⊂ Z(Q iv ).
Lemma 15. Let L = (Q 1 , . . . , Q t ) be a list of rational parametrizations with δ i being the degree of Q i and δ be the maximum of δ 1 , . . . , δ t . Assume that for 1 ≤ i ≤ t, Z(Q i ) is irreducible of dimension r i ; let r be the maximum of 1 and r 1 , . . . , r t . There exists an algorithm RemoveRedundantComponents which on input L returns a subset Q i 1 , . . . , Q i k of L such that, the following holds:

• Z(Q i 1 ) ∪ • • • ∪ Z(Q i k ) = Z(Q 1 ) ∪ • • • ∪ Z(Q t ); • for u = v, Z(Q iu ) ⊂ Z(Q iv ).
It uses t(r + 1)(nδ) O(r) operations in Q.

Proof. The algorithm starts by sorting (in ascending order) the rational parametrizations according to their dimension. Up to renumbering, one may assume that Q 1 , . . . , Q t are already sorted by nondecreasing dimension (i.e. r i ≤ r i+1 ). The algorithm starts by choosing randomly r+1 linear forms = (λ 1 , . . . , λ r+1 ) and call the routine ChangeSeparatingElement with input Q i and (λ 1 , . . . , λ r i +1 ). According to Lemma 13, this step uses t(r+1)(nδ) O(r) operations in Q. To keep notations simple, we keep on naming Q 1 , . . . , Q t for the obtained rational parametrizations. Since, by assumption, the rational parametrizations define irreducible algebraic sets, one only needs to decide if Z(Q i ) ⊂ Z(Q j ) for i < j and r i < r j . Thanks to the change of separating element, it then suffices to pick a random rational point in Q r i -1 and specialize both in Q i and Q j the parameters corresponding to λ 1 , . . . , λ r i . Hence, we are led to decide the inclusion of a finite set of points in an algebraic set ; both are given by a rational parametrization. This boils down to standard Euclidean remainder computations (see [START_REF] Lecerf | Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers[END_REF]).

Description of main algorithm

The algorithm takes as input a sequence f = (f 1 , . . . , f s ) of polynomials in Q[X 1 , . . . , X n ] of degree bounded by D. It returns a list of rational parametrizations, each of which defining a prime component of the real radical ideal generated by f .

The algorithm starts by calling IrreducibleDecomposition to compute a finite sequence of rational parametrizations R 1 , . . . , R t encoding the irreducible components of V C (f ). Next, for 1 ≤ i ≤ t, one computes a list of rational parametrizations encoding the irreducible components of the real radical associated to Z(R i ). This is done by calling a routine called LazyRealRadicalRec which is described further. Finally, the routine RemoveRedundantComponents is called with input the list of all previously computed rational parametrizations to remove redundancies.

LazyRealRadical(f ) 1. (R 1 , . . . , R t ) = IrreducibleDecomposition(f ); 2. if t = 1 and R 1 = (1) then return ((1)); 3. res = {}; 4. for 1 ≤ j ≤ t do • res = res ∪ LazyRealRadicalRec(R i );

return RemoveRedundantComponents(res).

We describe now the routine LazyRealRadicalRec. It takes as input a rational parametrization Q and outputs a list of rational parametrizations encoding the irreducible algebraic sets defined by the prime components of the real radical associated to Z(Q).

It works as follows. First, it decides if Z(Q) contains real regular points using the routine IsReal. If this is the case, then it returns Q, else it computes rational parametrizations encoding the prime components of the set S(Q) and performs a recursive call with input these parametrizations.

LazyRealRadicalRec(Q) 1. if Q = (1) then return (1); 2. if IsReal(Q) then return (Q); 3. let w be the eliminating polynomial of Q in Q[T 1 , . . . , T r+1 ]; 4. (Q 1 , . . . , Q k ) = Intersect(Q, ∂w ∂T r+1 ); 5. for 1 ≤ ≤ k do • res = res ∪ LazyRealRadicalRec(Q );
6. return RemoveRedundantComponents(res).

Proof of Theorem 3

We start by proving correctness and termination.

Proof. On input f , LazyRealRadical starts by computing an irreducible decomposition of the algebraic set defined by f by means of rational parametrizations R 1 , . . . , R t . The next step consists in computing rational parametrizations encoding the prime components of the real radical associated to Z(R i ) for 1 ≤ i ≤ t. This is done through the call to the routine LazyRealRadicalRec. Hence, the main step for proving correctness of LazyRealRadical consists in proving the correctness of LazyRealRadicalRec. Recall that it takes as input a rational parametrization Q encoding an irreducible algebraic set. We prove its correctness by decreasing induction on the dimension of Z(Q). The case where the Z(Q) is finite is immediate; hence we assume below that Z(Q) has positive dimension, say r, and terminates and is correct on inputs encoding algebraic sets of dimension less than r.

The routine LazyRealRadicalRec decides if the prime ideal associated to Z(Q) is real by calling the routine IsReal. If this is the case, Q is returned as expected. Else, it computes a decomposition of S(Q) following Lemma 9. Besides, Corollary 10 establishes that S(Q) has dimension strictly less than dim(Z(Q)). Termination and correctness follow by the induction assumption.

We can now prove the complexity statement.

Proof. The first step of LazyRealRadical consists in calling the routing IrreducibleDecomposition which uses (snD nr ) O(1) arithmetic operations in Q (Lemma 11) where r is the the maximum of 1 and the dimension of the algebraic set defined by the input f . By Bézout's theorem, the sum of the degrees of the irreducible components encoded by the output is bounded by D n . Hence, we have t ≤ D n and for 1 ≤ i ≤ t, the degree of R i is bounded by D n .

Next, one enters in the loop and call t times LazyRealRadicalRec with R i as input (for 1 ≤ i ≤ t). Below, we prove that running LazyRealRadicalRec with input a rational parametrization, say Q, of degree δ encoding an irreducible algebraic set of dimension ρ takes (nδ) O(2 ρ ) arithmetic operations in Q and the sum of the degrees of the rational parametrizations it outputs lies in (nδ) O(2 ρ ) Hence, the whole cost of the "for loop" is (nD) O(n2 r ) .

The last step consists in calling the routine RemoveRedundantComponents. Lemma 15 allows to estimate the complexity of this step. All in all, the total cost is bounded by s O(1) (nD) O(nr2 r ) .

We prove now the claim on the complexity of LazyRealRadicalRec. The first step consists in calling subroutine IsReal on input Q. This call takes δ O(ρ) arithmetic operations in Q (Lemma 12). When it returns true, Q is returned else a call to Intersect is performed with input Q and ∂w ∂T ρ+1 where w is the eliminating polynomial of Q. By Lemma 14, this uses (nδ) O(ρ) arithmetic operations in Q.

The sum of the degrees of the output is bounded by δ 2 but the dimension of these output rational parametrizations is ρ-1. Hence, denoting by T (δ, ρ) the cost of LazyRealRadicalRec on input a rational parametrization of degree δ encoding an irreducible algebraic set of dimension ρ, the following recursive formula holds:

T (δ, ρ) ≤ (nδ) O(ρ) + T (δ 2 , ρ -1).

Solving this recurrence formula yields a complexity (nδ) O(2 ρ ) . The same formula occurs for the degree bounds on the output. Hence, we are done.

As for algorithm RealRadicalSmooth, most of subroutines which are used in LazyRealRadical are probabilistic: they rely on either generic specialization points or generic choices of linear changes of variables (or linear forms).

Experiments

We give several examples to show the efficiency of our approach. All the examples given below are beyond the reach of the Singular library realrad implemented by Spang [START_REF] Spang | On the computation of the real radical[END_REF] which is, up to our knowledge, the single available implementation of the algorithm given by [START_REF] Becker | Computation of real radicals of polynomial ideals[END_REF]; [START_REF] Neuhaus | Computation of real radicals of polynomial ideals -II[END_REF]. That implementation is based on Gröbner bases.

Observe that one can use Singular functionalities to compute equidimensional/prime decompositions and intersections of ideals as well as elimination ideals, by means of Gröbner bases. Hence, one can "simulate" LazyRealRadical using those functionalities combined with the HasRealSolutions function in the Maple library RAGlib Safey El Din (2007a).

In a word, taking a polynomial sequence f as input, we will obtain generators of the minimal associated primes of re f . The computations were performed on an Intel(R) Xeon(R) CPU E7-4809 v2 @ 1.90GHz and 756GB of RAM.

Example 16 (Vor1). The following polynomial comes from [START_REF] Everett | The Voronoi diagram of three lines[END_REF]:

Vor1 =(α 2 + β 2 +

Acknowledgment

We thank Yue Ren for his help with the implementation of our algorithms. We also thank Erich L. Kaltofen for his valuable suggestions on the complexity of factorizing multivariate polynomials.

Mohab Safey El Din is supported by the ANR grant ANR-17-CE40-0009 Galop and the PGMO grant Gamma. Zhi-Hong Yang and Lihong Zhi are supported in part by the National Key Research Project of China 2016YFB0200504 and the National Natural Science Foundation of China under Grants 11571350.

Subroutine IrreducibleDecomposition This subroutine aims at performing the following. Given a straight-line program of length L which evaluates a sequence of polynomials f = (f 1 , . . . , f s ) in Q[X], it outputs a list of rational parametrizations encoding the irreducible components of V C (f ). This computation simply consists of calling the equidimensional decomposition algorithm in [START_REF] Lecerf | Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions[END_REF] which uses (sLnD n ) O(1) operations in Q to return zero-dimensional parametrizations of generic points in V C (f ). Combined with the Hensel lifting technique in [START_REF] Giusti | A Gröbner free alternative for polynomial system solving[END_REF] (which are actually used in [START_REF] Lecerf | Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions[END_REF]), that algorithm allows to recover r-equidimensional parametrizations for the components of dimension r. The total cost becomes (snD n max(1,r) ) O(1) . Deducing from this the irreducible components is then easily done by factoring the eliminating polynomials of the parametrizations (the one which vanishes in the representation); the cost of this latter step is negligible [START_REF] Kaltofen | Factorization of polynomials given by straight-line programs[END_REF]; [START_REF] Kaltofen | Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators[END_REF].)

Lemma 11. Let f = (f 1 , . . . , f s ) be a sequence of polynomials in Q[X] of degree bounded by D and V be the algebraic set defined by f with r = dim(V ). There exists a probabilistic algorithm which computes a list of rational parametrizations encoding the irreducible components of V using (snD n max(1,r) ) O(1)

of degree δ such that Z(Q) is irreducible. There exists an algorithm IsReal which returns true if Z(Q) contains real regular points or false otherwise. It uses δ O(max(1,r)) arithmetic operations in Q.

Proof. By Lemma 9, it suffices to decide if the semi-algebraic system w = 0, ∂w ∂T r+1 = 0 has a real solution. Using (Basu et al., 2006, Chapter 14), this can be done using δ O(max(1,r)) arithmetic operations in Q.

Subroutine ChangeSeparatingElement We describe now a subroutine which takes as input a rational parametrization encoding an equidimensional algebraic set Z using linear forms and returns a new sequence of linear forms and which computes a new rational parametrization still encoding Z but using .

Lemma 13. Let Q = ((w, v 1 , . . . , v n ), ) be a rational parametrization of degree δ encoding a r-equidimensional algebraic set Z and in the non-empty Zariski open set G (Z) defined in Lemma 7.

Then, there exists a routine ChangeSeparatingElement which computes a rational parametrization Q = ((w , v 1 , . . . , v n ), ) using (r + 1)(nδ) O(max(1,r)) arithmetic operations in Q.

Proof. The algorithm for changing one linear form works as in the proof of (Safey El Din and Schost, 2017, Lemma J.8 of the electronic Appendix). It simply consists in using the algorithm underlying (Poteaux and Schost, 2013, Lemma 2) which performs this operation in the zero-dimensional case in time (nδ) O(1) .

Here, we deal with positive dimensional situations. In (Safey El Din and Schost, 2017, Lemma J.8 of the Appendix), the one dimensional situation is tackled by performing This polynomial is a sum of squares [START_REF] Kaltofen | Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars[END_REF], thus the ideal Vor1 is not real. Take Vor1 as input and we obtain in 9 sec. the minimal primes of the real radical re Vor1 :

Example 17. Consider the discriminant D of the characteristic polynomial of the following linear symmetric matrix:

It has been proved that D is a sum of squares [START_REF] Lax | On the discriminant of real symmetric matrices[END_REF]. On input D, our algorithm computed in 4 sec. the real radical re D . It has only one minimal prime which is y -z, g where g = -19y

12 + 228y 11 z -1254y 10 z 2 + 4180y 9 z 3 -9405y 8 z 4 + 15048y 7 z 5 -17556y

Example 18 (Homotopy-1). This example is taken from [START_REF] Chen | Triangular decomposition of semi-algebraic systems[END_REF]:

Take the sequence f = (f 1 , f 2 , f 3 ) as input and we obtain in a single second that re f has only one minimal prime which is the ideal f . This shows that the ideal f is prime and real.

Example 19 . This is also an example taken from [START_REF] Chen | Triangular decomposition of semi-algebraic systems[END_REF]:

We obtain in 47 sec. the minimal primes of re f for f = (f 1 , f 2 , f 3 ):

Example 20 (Essential Variety). This is an example taken from [START_REF] Fløystad | The Chow form of the essential variety in computer vision[END_REF]. Let E be the essential variety defined as:

where det(M ) is the determinant of M and tr(M M T ) is the trace of M M T .

If we write the matrix M as

then the 10 cubics defining E are: where g = (a 2 + b 2 + c 2 + u 2 + v 2 + w 2 + x 2 + y 2 + z 2 ). Let I denote the ideal generated by these 10 cubics. Take these 10 cubics as input and we obtain in 800 sec. only one minimal prime of re √ I, which is the ideal I itself. Thus I is a real ideal.