of Toulouse researchers and makes it freely available over the web where possible

Health status diagnosis of chestnut forest stands using Sentinel-2 images

Véronique Chéret 1 , Yousra Hamrouni 1 , Michel Goulard 1 , Jean-Philippe Denux 1 , Hervé Poilvé 2 , Michel Chartier 3 1 Dynafor, University of Toulouse, INRA, INPT, INPT-EI PURPAN, Chemin de Borde-Rouge, 31326 Castanet Tolosan, France; veronique.cheret@purpan.fr 2 AIRBUS Defense and Space, 5 rue des satellites, F-31400 Toulouse, France; herve.poilve@airbus.com 3 CNPF-IDF, 13 avenue des Droits de l'Homme, 45921 Orléans Cx 9, France; michel.chartier@cnpf.fr

Context -Objectives

Health status diagnosis of chestnut forest stands is a crucial concern for forest managers. These stands are made vulnerable by numerous diseases and sometimes unadapted forestry practices. Moreover, since last years, they were submitted to several droughts. In Dordogne province (France), the economic stakes are important. For example, about 2/3 of the chestnut forest area are below the optimal production level, and most of this area shows forest stands with a high proportion of dry branches. The actual extent of chestnut forest decline remains still unknown. Sentinel-2 time series show an interesting potential to map declining stands over a wide area and to monitor their evolutions. This study aim to propose a method to discriminate healthy chestnut forest stands from the declining ones with several levels of withering intensity over the whole Dordogne province.

Method

The proposed method is the development of a statistical model integrating in a parsimonious manner several vegetation indices and biophysical parameters.

The statistical approach is based on an ordered polytomous regression to which are applied various technics of models' selection (A. Agresti, 2003).

Data

In this study, Sentinel-2 images (10 bands at 10 and 20 m spatial resolution) acquired during the growing season of 2016 have been processed. Due to insufficient data quality related to atmospheric conditions, only 2 cloudfree images could be analyzed (one in July and one in September). -Vegetation Red Edge and NIR spectral bands : B8a, B7, B6, B8, -Vegetation indices : NDII (B8-B11/B8+B11), NDVIre2n (B8a-B6/B8a+B6), DVI (b7-b3), IRECI ((b6 -b3)*b5/b4), NBR (B8-B12/B8+B12)… -Biophysical parameters : GLAI and GLCV. 2-About 24 selected models using for 2 to 5 variables, and using single date images (July and Sept) or both combined 3-Maps from the 12 best models :

-Linear prediction maps, -Maps of probability of belonging to a class of decline value, -Expected classification maps.

In progress : In progress :

• Spatial analyses of the 24 selected models

  2 dates images➢ 30/07/2016 ➢ 28/09/2016 Remark : Image to image registration shows up to 1.5 pixel error 1-Remote sensing variables : About 36 vegetation indices were calculated from THEIA-MAJA L2A products and 5 biophysical parameters were processed from ESA level 1C product. These last parameters have been obtained with the Overland software (developed by Airbus DS Geo-Intelligence) by inverting a canopy reflectance model. This software couples the PROSPECT leaf model and the scattering by arbitrary inclined leaves (SAIL) canopy model. 2-Calibration and validation of the predictive models are based on health status data. About 50 plots have been surveyed by foresters describing the chestnut trees health status by using two protocols (ARCHI and expert knowledge). bands (resampled at 10m spatial resolution ) ▪ B2, B3, B4, B5, B6, B7, B8, B8a, B11 et B12  36 vegetation indices ▪ NDVI, EVI, NDII, NDVI RedEdge , MCARI, DVI, Clgreen, CRI2, NBR, PSRI ….  5 Biophysical parameters ▪ Blcv : Cover fraction of brown vegetation ▪ Glcv : Cover fraction of green vegetation ▪ Fapar : Fraction of Absorbed Photosynthetically Active Radiation ▪ Glai : Gren Leaf Area Index ▪ Wat : Leaf water content Results 1-The best remote sensing variables according to AIC and cross validation :

Remote sensing variables Decline value of forest plots

	SENTINEL-2 spectral bands (ESA)
	Example : linear
	prediction map
	• Validation of the
	selected models with
	additional plots of
	expert knowledge
	observations (spring
	2018)

This study is funded by the network "Adaptation des forêts au Changement climatique" (AFORCE) Software Overland

(Airbus DS)


Pierre Poulain
email: pierre.poulain@u-paris.fr

Jean-Michel Camadro

AutoClassWeb: a simple web interface for Bayesian clustering

Keywords: Clustering, Genomics, Proteomics, Bayesian, Autoclass, Machine learning

Objective: Data clustering is a common exploration step in the omics era, notably in genomics and proteomics where many genes or proteins can be quantified from one or more experiments. Bayesian clustering is a powerful algorithm that can classify several thousands of genes or proteins. AutoClass C, its original implementation, handles missing data, automatically determines the best number of clusters but is not user-friendly. Results: We developed an online tool called AutoClassWeb, which provides an easy-to-use web interface for Bayesian clustering with AutoClass. Input data are entered as TSV files. Results are provided in formats that ease further analyses with spreadsheet programs or with programming languages, such as Python or R. AutoClassWeb is implemented in Python and is published under the 3-Clauses BSD license.

Introduction

In biology, high-throughput technologies (notably in genomics and proteomics) enable identification and quantification of several thousands of genes or proteins in a single experiment. To analyze such a large amount of data, from one or more experiments, clustering algorithms are widely used unsupervised machine-learning methods to group genes or proteins with similar patterns. Bayesian clustering is such an algorithm and one of its implementation in the C programming language (AutoClass C) has been developed in 1996 at the Ames Research Center at NASA [START_REF] Cheeseman | Bayesian Classification(AutoClass):Theory and Results[END_REF][START_REF] Stutz | Autoclass -A Bayesian Approach to Classification[END_REF]. The idea behind Bayesian clustering and the AutoClass algorithm is to find a classification that fits the data with the highest probability. The AutoClass algorithm provides some additional and interesting features: it handles missing data and determines automatically the best number of clusters.

AutoClass C has been used in a wide variety of applications from clustering cells of the prefrontal cortex in rats and mice [START_REF] Elliott | Serotonin Differentially Regulates L5 Pyramidal Cell Classes of the Medial Prefrontal Cortex in Rats and Mice[END_REF] to detecting body patterns in the common cuttlefish [START_REF] Crook | Identifying the Structure in Cuttlefish Visual Signals[END_REF] (see also references [START_REF] Achcar | AutoClass@IJM: A Powerful Tool for Bayesian Classification of Heterogeneous Data in[END_REF] and [START_REF] Camadro | AutoClassWrapper: A Python Wrapper for AutoClass C Classification[END_REF] for a detailed list of applications). However, AutoClass C, originally developed by physicists, is not user-friendly: the program is solely accessible through the command line, only 32-bit binaries are available and results files are difficult to parse for subsequent analysis.

More than 10 years ago, Achcar et al. published AutoClass@IJM [START_REF] Achcar | AutoClass@IJM: A Powerful Tool for Bayesian Classification of Heterogeneous Data in[END_REF], a web interface for AutoClass C. This web service drastically simplified the use of AutoClass C and widen its adoption, especially in biology [START_REF] Elliott | Serotonin Differentially Regulates L5 Pyramidal Cell Classes of the Medial Prefrontal Cortex in Rats and Mice[END_REF][START_REF] Wu | The Control of Tomato Fruit Elongation Orchestrated by Sun, Ovate and Fs8.1 in a Wild Relative of Tomato[END_REF][START_REF] Léger | The Metacaspase (Mca1p) Has a Dual Role in Farnesol-induced Apoptosis in Candida[END_REF][START_REF] Franco | Cluster Analysis of Microarray Data[END_REF][START_REF] Duval | The Adaptive Response to Iron Involves Changes in Energetic Strategies in the Pathogen Candida Albicans[END_REF]. Unfortunately, this tool is not maintained anymore, and its source code is not publicly available.

To continue to offer this powerful Bayesian clustering method to the community, we developed AutoClassWeb, a new easy-to-use open-source web interface for AutoClass C.

Main text

Implementation AutoClassWeb utilizes AutoClassWrapper [START_REF] Camadro | AutoClassWrapper: A Python Wrapper for AutoClass C Classification[END_REF], a Python wrapper for the AutoClass C program. This wrapper facilitates the preparation and quality control of data, runs the actual classification, and eventually, prepare results in file formats that allow further analysis.

AutoClassWeb is written in Python [START_REF] Van Rossum | Python Tutorial[END_REF] and uses the Flask library to build the web interface users interact with. For better reproducibility and sustainability, Au-toClassWeb is packaged in a Docker image stored in the BioContainers [START_REF] Da Veiga Leprevost | BioContainers: An Open-Source and Community-Driven Framework for Software Standardization[END_REF] registry.

The web service itself has been designed to be user-friendly. There is no user authentication and by default, results are kept 30 days before being deleted. A comprehensive help page provides all the help and guidance the user might need.

Using Docker technology, AutoClassWeb can be quickly deployed on a local machine or on a public web server. To this end and to reduce the installation burden, we provide two companion GitHub repositories with detailed instructions, for local (https://github.com/pierrepo/autoclassweb-app) and server installation (https://github.com/pierrepo/autoclassweb-server).

Data submission

The input data must be formatted as tab-separated values (TSV) files. The first line is a header containing the names of the columns which must be unique. The first column contains the names of the objects studied (i.e. protein or gene identifiers).

Missing data is supported and should be coded with an empty value (i.e. nothing).. AutoClass supports three categories of data: real location: negative and positive values such as position, elevation, microarray log ratio... real scalar : singly bounded real values, typically bounded below at zero (i.e.: length, weight, age). discrete: qualitative data. For instance, color, phenotype, name... If the initial input dataset contains several data types (real scalar, real location, discrete), it is recommended to split the initial dataset into several datasets of homogeneous type and submit them in the input form (Figure 1 (A)).

For the data types real scalar and real location, the user can optionally specify an absolute and relative error, respectively.

Clustering

Upon submission, input data is quality checked and formatted to be usable by AutoClass C. The web interface provides a unique job name, a link to the status page and a quick summary of input data (toggled with the text Hide/show logs), as illustrated in Figure 1 (B).

The status page lists running, failed and completed runs with their respective identifier (Job name), creation date, status and running time (Figure 1 (C)).

Results

Once a job is completed, a green button allows the user to download results of the clustering. Results are bundled in a zip archive with the following files (where xxx stands for the unique identifier of the job):

xxx autoclass out.cdt and xxx autoclass out withproba.cdt can be viewed with Java TreeView [START_REF] Saldanha | Java Treeview-extensible Visualization of[END_REF], a versatile viewer initially developed for microarray data. The file xxx autoclass out withproba.cdt contains the probability for each object (gene or protein) to belong to each class. xxx autoclass out stats.tsv contains means and standard deviations of distance between all classes. xxx autoclass out.tsv contains all the data with the class assignment and membership probabilities for all classes. This file is in the TSV format and can be easily parsed with spreadsheet programs such as Microsoft Excel or LibreOffice Calc, or programming languages such as R or Python.

Performance

The AutoClass C algorithm has been designed to run on a single CPU. The running time depends exponentially on the size of the input dataset. Figure 2 illustrates the running time as a function of the input dataset sizes. Dataset size is expressed as the number of rows (usually genes or proteins) times the number of columns (features or properties of interest).

Conclusion

Data clustering is an essential step in most modern omics analyses. The AutoClass algorithm, while very powerful, is not widely used, mainly because its original Au-toClass C implementation is difficult to use. AutoClassWeb provides an easy-to-use web interface for AutoClass C. The project is open-source, packaged in a Docker image available in BioContainers for better reproducibility and sustainability.

Limitations

AutoClassWeb provides a convenient online service to cluster results from highthroughput experiments such as RNA-seq or mass spectrometry based proteomics. However, we would like to point out that the processing time required to cluster data with AutoClass is proportional to the number of genes or proteins to be clustered. A parallel version of AutoClass C that potentially reduces the processing time has been published [START_REF] Pizzuti | P-Autoclass: Scalable Parallel Clustering for Mining Large Data Sets[END_REF]. Unfortunately, the source code is not available, and the project has been discontinued. Another limitation of AutoClassWeb requires users to split input data by type (real location, real scalar or discrete) with a special attention to real location and real scalar which may sometimes be confused.

FiguresFigure 1

 1 Figures

Figure 2

 2 Figure 2 Running time (in hour) as a function of the input dataset sizes. Dataset size is expressed as the number of rows (genes or proteins) times the number of columns (features or studied properties).

Acknowledgements

Authors thank Denis Mestivier for fruitful discussions on AutoClass@IJM.

The source code is available at https://github.com/pierrepo/autoclassweb along with a

Availability of data and materials

The source code of AutoClassWeb is open-source, released under the BSD-3-Clause license, and available on the GitHub development platform https://github.com/pierrepo/autoclassweb. AutoClassWeb source code in its current version 2.2.1 is archived in Software Heritage with the following reference: swh:1:dir:173e846a5137a4b498ca7da9eca980790631bc1a

Abbreviations CPU: Central Processing Unit TSV: tab-separated values

Competing interests

The authors declare that they have no competing interests.


Laetitia Boitaud

Sandrine Salmon

Celine Bourlette

Jean-François F Ponge
email: jean-francois.ponge@wanadoo.fr

Type of contribution: Short communication Avoidance of low doses of naphthalene by Collembola

Keywords: Soil pollution, Collembola, Behaviour, Avoidance, Polycyclic Aromatic Hydrocarbon (PAH)

Capsule

PAH avoidance by soil springtails is species-specific and differs among populations of the same species

Introduction

Polycyclic aromatic hydrocarbons (PAHs) are important compounds to be considered in environmental risk assessment [START_REF] Riser-Roberts | Remediation of petroleum contaminated soils[END_REF]. Naphthalene, one of the smallest (in molecular size) and most common PAHs, is a neurotoxicant [START_REF] Ritchie | A review of the neurotoxicity risk of selected hydrocarbon fuels[END_REF] and its carcinogenic effects are now fully recognized [START_REF] Preuss | Naphthalene. An environmental and occupational toxicant[END_REF]. This pollutant has been used for decades in homes for deterring insects from clothing and to reduce densities of microarthopods in soils [START_REF] Best | Response of microarthropod populations to naphthalene in three contrasting habitats[END_REF].

Although still not fully recognized in ecological risk assessment, the avoidance of contaminants by soil animals has proven to be of ecological value at the micro-site level, by allowing sensitive species to move away from the pollution source (Tranvik and Eijsackers, 1989;[START_REF] Filser | Experimental studies on the reactions of Collembola to copper contamination[END_REF]. Recent studies in ecotoxicology showed that avoidance tests using Collembola compare well in their outcome with tests of toxicity [START_REF] Greenslade | A comparison of Collembola species for toxicity testing of Australian soils[END_REF][START_REF] Da Luz | Avoidance tests with Collembola and earthworms as early screening tools for site-specific assessment of polluted soils[END_REF].

We may wonder whether naphthalene, known to affect arthropod populations at high concentration [START_REF] Best | Response of microarthropod populations to naphthalene in three contrasting habitats[END_REF]Sverdrup et al., 2002), can be perceived and avoided at low doses, whether avoidance depends on the species and whether several populations of the same species avoid it to the same extent.

Materials and methods

Different species collected from several sites in France were compared (Table 1). Soil from four sites was used for starting cultures. NS Brunoy was a neutral soil (pH 7.5) in an oak/hornbeam woodlot at Brunoy (Ile-de-France). AS Brunoy was an acid soil (pH 4.5) in an oak/pine woodland at Brunoy. NS Pechelbronn was a neutral soil (pH 7) in an abandoned oil refinery at Pechelbronn (Alsace). AS Pfaffenbronn was an acid soil (pH 4.5) in an oak/beech woodland at Pfaffenbronn (Alsace).

Previous to each experimental run all specimens used had never been into contact with any kind of pollutant. They stemmed from batch cultures performed from 1 to 3 years (according to species) on a standard substrate made of fine quartz sand moistened with tap water, powdered cow dung being added ad libitum. The test specimens were selected among fully developed (adult) animals from the same rearing box.

Avoidance experiments were performed in sterile polystyrene Petri dishes. The diameter of the dish was 35 mm (Mesaphorura macrochaeta, M. florae, M. yosii, Proisotoma minima), 52 mm (Folsomia candida, Isotomiella minor, Parisotoma notabilis) or 85 mm (Arrhopalites caecus, Heteromurus nitidus), depending on the size and activity of the species. Previous observations showed that tiny, short-legged springtails such as Mesaphorura spp. could not perform a choice within the duration of the experiment if they were not allowed to explore the whole dish in a first step.

Conversely, bigger, very motile species such as Heteromurus nitidus were unable to make a choice if they lacked space for their movements. Two half-disks of glass fiber paper were moistened with deionised water then deposited at the the bottom of the Petri dish. The entire surface of each half-disk was covered with a thin layer (1 mm) of Fontainebleau sand saturated with different concentrations of the test solution (test half disk) or deionised water (control half disk). The two half-disks were separated by a 2 mm space, at the centre of which one naive specimen was deposited. The position of the animal was recorded every 20 minutes for 100 minutes. This time interval was selected on the base of similar experiments where the position of animals was recorded every 10' [START_REF] Salmon | Earthworm excreta attract soil springtails: laboratory experiments on Heteromurus nitidus (Collembola: Enromobryidae)[END_REF]. During the first 20' the animals wandered continuously, then when a difference between both sides of the Petri dish was perceived, most of them shifted to one or the other side. Twenty replicates were used for each treatment, in two successive batches of ten. During the experiment, Petri dishes were placed under a fluorescent illuminator in a temperature-controlled chamber at 20°C. Care was taken that the animals were not disturbed during observations, done by transparency through the cover lid. Blank experiments checked for the absence of effects of any light gradient which could bias the results [START_REF] Salmon | Responses to light in a soil-dwelling springtail[END_REF].

For each of the four concentrations of naphthalene, differences between test and control sides of Petri dishes were tested by paired t test after check for the normal distribution of count data [START_REF] Sokal | Biometry. The Principles and Practice of Statistics in Biological Research[END_REF]. Statistical tests were done on the number of times (from 0 to 5) an animal was counted on each side of the Petri dish.

Results are presented as mean percent presence of animals on the test side (total of 5x20 counts divided by 100).

The test pollutant was naphthalene (C 10 H 8 ). Its water solubility is 30 mg.L -1 at 20°C (Verschueren, 2001). A new solution of naphthalene was prepared before each test run to prevent the appearance of degradation products. Before use, the solution was put on a magnetic blender for one night at 20°C. Three dilution rates (0.3, 0.03, 0.003 mg.L -1 ) and the mother solution (30 mg.L -1 ) were tested.

Results and discussion

Table 2 shows the results of all behavioural tests. For H. nitidus, only the saturated concentration (30 mg.L -1 ) was tested because of a lack of individuals in the rearing box. At the highest concentration of naphthalene (30 mg.L -1 ), specimens from all but three strains avoided the polluted side (mean percent presence ≤32% on the test side) but no mortality was found. Avoidance was still displayed by most strains at 0.3 mg.L -1 . Naphthalene was not avoided by F. candida (AS Pfaffenbronn), H. nitidus (NS Pechelbronn) and P. minima (AS Brunoy). Only M. yosii (AS Brunoy) and P. notabilis (NS Pechelbronn) avoided the naphthalene at 0.03 mg.L -1 . No species was sensitive at 0.003 mg.L -1 .

The absence of mortality within the duration of the experiment can be explained by the low concentration of the contaminant in aqueous solution, even when saturated (30 mg.L -1 ). One-month test cultures on the same substrate (pure fine quartz sand moistened with naphthalene solution, powdered cow dung added ad libitum) did not show any mortality of the introduced specimens, nor any definite trend of cessation of reproduction. Other studies showing the toxicity of naphthalene to soil Collembola used naphthalene as a powder [START_REF] Best | Response of microarthropod populations to naphthalene in three contrasting habitats[END_REF] or diluted in lipophilic solvents (Sverdrup et al., 2002), which added a vapour phase in the soil atmosphere. In our experiment, the odour of naphthalene was nil after the introduction of fine quartz sand. Previous assays without the addition of sand revealed a definite odour at the highest concentration, which did not allow the animals to perceive a difference between both sides of petri dishes. The presence of highly diffusible olfactory compounds should be considered as a severe limitation to the use of Petri dishes for testing avoidance, olfactometers, being recommended, although they are unfortunately not commercially available [START_REF] Bengtsson | Fungal odour attracts soil Collembola[END_REF].

The avoidance test discriminated between species and strains and no attraction was shown even at the lowest concentration. Most species avoided naphthalene at the highest concentration (30 mg.L -1 ) but still avoided it at 0.3 mg.L -1 . Only three species were not sensitive at all to the tested PAH, including F. candida. This species does not seem to be representative of the Isotomidae family, if not of the Collembola group, despite its standard use in ecotoxicology (ISO 11267). Mesaphorura macrochaeta, Mesaphorura yosii, Parisotoma notabilis and Arrhopalites caecus seem to be more sensitive indicators of soil toxicity.

Differences in the sensitivity of collembola to the studied PAH cannot be explained by ecological requirements of the species. Soil acidity (Senart, Pfaffenbronn) and PAH pollution (Pechelbronn) did not seem to select for more tolerant species and different strains of the same species did not avoid naphthalene at the same concentration threshold (Table 2). To the present state of our studies, acidophilic collembola do not seem to be more resistant to pollution by PAHs or heavy metals. [START_REF] Garnier | Acid-tolerant Collembola cannot colonize metal-polluted soils at neutral pH[END_REF] showed that despite similarities between the chemical environment of acid soils and that of metal-polluted soils, differences in pH and microbial communities prevented acid-tolerant populations from surviving and reproducing when introduced in a polluted site. In the present experiments, we demonstrated that, when placed in the same environmental conditions (for culture and experiment), acid-tolerant animals were not less sensitive to naphthalene than acidintolerant species. Two hypotheses can be proposed, i) an acclimatization time is required to reveal the tolerance of a given population, ii) populations which withstand low pHs and associated chemicals such as heavy metals, terpenes and phenolics are not necessarily tolerant to every contaminant.

Naphthalene is the commonest agent of soil and water pollution by hydrocarbons [START_REF] Riser-Roberts | Remediation of petroleum contaminated soils[END_REF][START_REF] Preuss | Naphthalene. An environmental and occupational toxicant[END_REF]. Among PAHs, its higher solubility in water and higher diffusibility in the air make it mostly responsible for the immediate sensitivity of organisms to hydrocarbons [START_REF] Ritchie | A review of the neurotoxicity risk of selected hydrocarbon fuels[END_REF]Sverdrup et al., 2002). Measuring the avoidance of naphthalene by soil animals can thus be considered as a relevant tool to assess the immediate sensitivity of these organisms to hydrocarbon pollution.

Table 1 .

 1 List of collembolan species used in eco-ethological tests, and their origin and 1 taxonomic affiliation. NS = neutral soil (pH water 7 or 7.5), AS = acid soil (pH water 4.5)

	2
	3
	Species	Family	Acidity Humus form Origin	Code
	Arrhopalites caecus	Arrhopalitidae	Neutral	Mull	Brunoy	NS Brunoy
	Folsomia candida	Isotomidae	Acid	Moder	Pfaffenbronn	AS Pfaffenbronn
	Isotomiella minor	Isotomidae	Acid	Moder	Brunoy	AS Brunoy
	Isotomiella minor	Isotomidae	Acid	Moder	Pfaffenbronn	AS Pfaffenbronn
	Mesaphorura florae	Onychiuridae	Neutral	Mull	Pechelbronn	NS Pechelbronn
	Mesaphorura macrochaeta	Onychiuridae	Acid	Moder	Pfaffenbronn	AS Pfaffenbronn
	Mesaphorura yosii	Onychiuridae	Acid	Moder	Brunoy	AS Brunoy
	Mesaphorura yosii	Onychiuridae	Acid	Moder	Pfaffenbronn	AS Pfaffenbronn
	Parisotoma notabilis	Isotomidae	Neutral	Mull	Pechelbronn	NS Pechelbronn
	Parisotoma nitabilis	Isotomidae	Acid	Moder	Pfaffenbronn	AS Pfaffenbronn
	Proisotoma minima	Isotomidae	Acid	Moder	Brunoy	AS Brunoy
	Proisotoma minima	Isotomidae	Acid	Moder	Pfaffenbronn	AS Pfaffenbronn
	4

Table 2 .

 2 Avoidance tests. Mean (± standard error) percent presence of collembola on 1 test side of Petri dishes (5 counts at 20 minute intervals, 20 replicates) at 4 dilution 2 rates of the naphthalene solution. Differences between control and test side were 3 tested by t test. Significant departure from no effect values (50% presence on test side) 4 is indicated in bold underlined type (P < 0.05).

	5
	6
	Species	Strain origin	0.003 mg.L -1	0.03 mg.L -1	0.3 mg.L -1	30 mg.L -1
	H. nitidus	NS Pechelbronn				48.00±10.60
	F. candida	AS Pfaffenbronn 49.00±8.64	40.00±7.68	44.00±8.16	52.00±7.73
	I. minor	AS Pfaffenbronn 42.00±8.07	44.00±9.47	31.00±7.88	32.00±7.46
	P. notabilis	AS Pfaffenbronn 49.00±7.88	46.00±9.30	40.00±7.11	30.00±8.27
	P. notabilis	NS Pechelbronn 37.00±9.87	30.00±7.33	26.00±8.96	28.00±8.00
	P. minima	AS Brunoy	49.00±7.47	48.00±8.75	32.00±8.13	33.00±7.15
	P. minima	AS Pfaffenbronn 58.00±7.80	53.00±8.86	51.00±8.88	37.00±8.62
	M. florae	NS Pechelbronn 50.00±7.75	42.00±7.66	20.00±6.96	31.00±7.18
	M. macrochaeta AS Pfaffenbronn 51.00±7.61	51.00±9.78	31.00±6.72	29.00±5.52
	M. yosii	AS Brunoy	52.00±8.51	18.00±5.96	28.00±8.87	24.00±8.16
	M. yosii	AS Pfaffenbronn 36.00±8.03	43.00±9.21	32.00±8.00	13.00±5.48
	A. caecus	NS Brunoy	53.00±8.62	41.25±8.37	25.56±7.64	22.00±6.94

Acknowledgements

The present study has been undertaken with a financial support from the Agence de l'Environnement et de la Maitrise de l'Énergie (ADEME), which is greatly acknowledged. Sverdrup, L.E., Nielsen, T., Krogh, P.H., 2002. Soil ecotoxicity of polycyclic aromatic hydrocarbons in relation to soil sorption, lipophilicity, and water solubility.

Environmental Science and Technology 36, 2429-2435. Tranvik, L., Eijsackers, H., 1989. On the advantage of Folsomia fimetarioides over Isotomiella minor (Collembola) in a metal polluted soil. Oecologia 80, 195-200. Verschueren, K., 2001. Handbook of Environmental Data on Organic Chemicals. Wiley, New York, NY.


Teresa Krick

AND Bernard Mourrain
email: bernard.mourrain@inria.fr

Agnes Szanto
email: aszanto@ncsu.edu

Aromath

Univariate Rational Sums of Squares

Keywords: Positive polynomials, Sum of Squares, Semi-Definite Matrix, Convex cone, Real roots, Exact computation, Certificate

come   L'archive ouverte pluridisciplinaire

Introduction

It is a classical result that a real univariate polynomial is nonnegative on all R if and only if it is a sum of squares of real polynomials (and in fact, 2 polynomials are enough). It was then proved by Landau in 1905, see [START_REF] Landau | Über die Darstellung definiter Funktionen durch Quadrate[END_REF], that every univariate polynomial with rational coefficients which is non-negative on all R is a sum of 8 squares of rational polynomials (this result was improved in [START_REF] Pourchet | Sur la représentation en somme de carrés des polynômes à une indéterminée sur un corps de nombres algébriques[END_REF], lowering the bound of 8 to the optimal value of 5).

We call this the global case, when we consider non-negativity on all R. The local case is when we consider analogous questions for a polynomial which is non-negative at the real roots of another non-zero polynomial. More explicitly, the corresponding statement is: Given a non-zero polynomial f ∈ R[x], is it true that a polynomial g ∈ R[x] is non-negative at all the real roots of f if and only if it is congruent modulo f to a sum of squares of polynomials in R[x]? That is, if there exist polynomials

h i ∈ R[x], 1 ≤ i ≤ N for some N ∈ N, such that h := N i=1 h 2 i satisfies h ≡ g mod f.
In [START_REF] Parrilo | An explicit construction of distinguished representations of polynomials nonnegative over finite sets[END_REF], P. Parrilo gives a very simple construction that shows that this is indeed the case in a zero-dimensional radical setting of multivariate polynomials. In our specific setting his result shows that every g ∈ R[x] which is non-negative at all the real roots of a squarefree polynomial f ∈ R[x] is congruent modulo f to a sum of squares of real polynomials. In this paper, we consider the corresponding rational question: Given polynomials f, g ∈ Q[x] such that g is non-negative at all the real roots of f , is it true that g is congruent modulo f to a sum of squares of polynomials h i ∈ Q[x]? Note that this is equivalent to say that g is congruent modulo f to a rational positive weighted sum of squares of polynomials in Q[x], that is, that there exist ω i ∈ Q + and

h i ∈ Q[x], 1 ≤ i ≤ N , such that (1) h := N i=1 ω i h 2 i satisfies h ≡ g mod f,
since for ω i = m/n ∈ Q with m, n ∈ N, ω i h 2 i = mn(h i /n) 2 . The positive weighted sum of squares h is commonly called a sum of squares (SOS) decomposition of g modulo f , and such a decomposition, together with the polynomial q ∈ Q[x] such that g = h + q f is a certificate of the non-negativity of g at the real roots of f . The existence and computation of rational SOS decompositions of positive polynomials has been investigated in the univariate global case for instance in [START_REF] Chevillard | Efficient and accurate computation of upper bounds of approximation errors[END_REF], [START_REF] Victor Magron | Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials[END_REF], or in the multivariate case in [START_REF] Peyrl | Computing sum of squares decompositions with rational coefficients[END_REF], [START_REF] Kaltofen | Exact certification of global optimality of approximate factorizations via rationalizing sums-ofsquares with floating point scalars[END_REF]. A counter-example in [START_REF] Scheiderer | Sums of squares of polynomials with rational coefficients[END_REF] shows that, in the multivariate case, a rational polynomial which is a sum of squares of real polynomials cannot always be decomposed as a rational sum of squares. In [START_REF] Kaltofen | Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients[END_REF], [START_REF] Guo | Certificates of impossibility of hilbert-artin representations of a given degree for definite polynomials and functions[END_REF], rational Artin's type certificates of positivity, that is, fractions of two rational weighted sums of squares polynomials are considered. In [START_REF] Magron | On exact Reznick, Hilbert-Artin and Putinar's representations[END_REF], algorithms to compute positivity certificates and bounds on their bit complexity and the size of their output are presented, including Artin's type certificates and rational weighted sums of squares certificates for positive polynomials on compact basic semi-algebraic sets. The algorithms work under some strictly positivity assumptions. They involve numeric-symbolic tools such as the perturbation algorithm of [START_REF] Chevillard | Efficient and accurate computation of upper bounds of approximation errors[END_REF], the rounding-projection algorithm of [START_REF] Peyrl | Computing sum of squares decompositions with rational coefficients[END_REF] or Semi-Definite Programming solvers. More recently, [START_REF] Victor Magron | Exact Optimization via Sums of Nonnegative Circuits and Arithmetic-geometric-mean-exponentials[END_REF] provides a numeric-symbolic algorithm based on rounding-projection techniques for computing exact representations of polynomials lying in the interior of the cone of nonnegative circuits (SONC) or of the cone of arithmetic-geometric-exponentials (SAGE). In [START_REF] Victor Magron | Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients[END_REF], an algorithm is proposed to compute the representation of a non-negative polynomial f as a rational sum of squares and an element in the gradient ideal of f with rational coefficients, under the hypothesis that the gradient ideal is zero-dimensional and radical, reducing to the univariate case by elimination techniques. Numeric-symbolic approaches similar to [START_REF] Magron | On exact Reznick, Hilbert-Artin and Putinar's representations[END_REF] are applied to trigonometric polynomials in [START_REF] Victor Magron | Exact SOHS decompositions of trigonometric univariate polynomials with Gaussian coefficients[END_REF].

In this paper, we first show, by a direct method, that a rational univariate polynomial g strictly positive at the real roots of a rational squarefree polynomial f always admits a rational SOS decomposition modulo f . This can be seen as a very very special case of Putinar's Theorem [START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF] over rational numbers. We then extend the result to rational univariate polynomials g that are non-negative at the real roots of f , under an assumption specified in our main result:

Theorem. Let f ∈ Q[x]
be a non-zero polynomial of degree n and g ∈ Q[x] be such that gcd(f, g) and f / gcd(f, g) are relatively prime. Assume that g is non-negative at all the real roots of f . Then there exist rational positive weights ω i ∈ Q + and rational polynomials

h i ∈ Q[x] of degree < n, 1 ≤ i ≤ N for some N ∈ N, such that h := N i=1 ω i h 2 i satisfies h ≡ g mod f.
Note that when f is squarefree, our assumption on gcd(f, g) and f / gcd(f, g) being relatively prime is automatically satisfied. Furthermore, this assumption seems to be optimal in order for such an SOS decomposition to exist, as the following example demonstrates [12, Remark 1]: For f = x 2 and g = x, g is non-negative on all the (real) roots of f but there is no such SOS decomposition. Note that in this case gcd(f, g) = x = f / gcd(f, g) and the polynomials f and g do not satisfy the assumption of our theorem.

Certifying the non-negativity of a polynomial g at the real roots of another polynomial f is a problem of particular importance in Computer Algebra, for instance, for the localisation of real roots [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF], or in Automatic Theorem Proving for the certification of sign conditions over the real numbers. It is also useful for checking the sign of polynomials in R n or more generally in Polynomial Optimization Problems, since one can generically add polynomial constraints like the gradient equations and reduce to a univariate polynomial sign certification problem by elimination of variables (see e.g. [START_REF] Victor Magron | Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients[END_REF]).

The proof of our theorem is developed in Section 2. It proceeds by first tackling in Subsection 2.1 the case when g is strictly positive at all the real roots of a squarefree polynomial f of degree n: by modifying the construction in [START_REF] Parrilo | An explicit construction of distinguished representations of polynomials nonnegative over finite sets[END_REF], we first show there always exists a real SOS decomposition h of g modulo f ,

h = [1, x, . . . , x n-1 ] Q [1, x, . . . , x n-1 ] T
with Q ∈ R n×n symmetric and positive definite. This enables us to perturb the real coefficients in matrix Q in order to turn them rational, while keeping the condition of remaining an SOS decomposition for g modulo f , as done in [START_REF] Peyrl | Computing sum of squares decompositions with rational coefficients[END_REF] for the global case (with the difference that here we know there always exists such a positive definite real matrix). In a second step, Subsection 2.2 deals with the case of a non squarefree polynomial f , by applying Hensel lifting and Chinese Remainder Theorem recombination. We finally relax the strictly positive condition to non-negative under our assumption.

In this paper, we also address the following algorithmic question: Can we produce an algorithm that computes a rational SOS certificate, which size is related to the geometry of the input polynomials?

Several algorithms can be used to certify that a polynomial g is nonnegative at the real roots of f . We refer to [START_REF] Basu | Algorithms in Real Algebraic Geometry[END_REF] for a general presentation of these algorithms, based for instance on Sturm-Habicth sequences or isolation of real roots. The algorithm that we describe in Section 3 does not require to isolate or approximate the real roots of f . It computes a certificate of non-negativity by computing an SOS decomposition of g modulo f using two main ingredients. The first ingredient is an adaptation of the rounding-projection algorithm of [START_REF] Peyrl | Computing sum of squares decompositions with rational coefficients[END_REF] to the case of a rational polynomial g strictly positive at the real roots of a squarefree polynomial f , following the proof of Proposition 2.8. The second ingredient is a reduction of the general case when gcd(f, g) and f / gcd(f, g) are relatively prime, to the strictly positive case, then lifting the rational SOS decompositions via Hensel lifting and Chinese Remainder Theorem, following the proof of our main theorem.

Acknowledgment. This collaboration and research project started because Agnes contacted the two other authors after an invitation by the organizers of the MCA 2021 session "Symbolic computation: theory, algorithms and applications", Alicia Dickenstein, Alexey Ovchinnikov and Veronika Pillwein, to submit a publication related to her talk to the Revista de la Unión Matemática Argentina. We all worked together during 2021 and, as usual when working with her, Agnes' input was crucial to produce the output. Agnes sadly passed away on March 21, 2022. We miss her dearly.

Existence of a rational SOS decomposition

2.1. The squarefree and strictly positive case. In this section we assume that f ∈ R[x] is a squarefree polynomial and that g ∈ R[x] is strictly positive at the real roots of f . We fix the following notation. Notation 2.1. We denote

f = n i=0 f i x i = f n (x -ξ 1 ) • • • (x -ξ n ) with ξ i = ξ j ∈ C for i = j,
where ξ 1 , . . . , ξ k are the real roots of f (for some 0 ≤ k ≤ n) while the complex non-real roots are labeled as

ξ k+2i-1 , ξ k+2i with ξ k+2i-1 = ξ k+2i for 1 ≤ i ≤ n-k 2 .
The Lagrange basis for ξ 1 , . . . , ξ n is denoted by u 1 , ..., u n ∈ C[x], i.e.

(2)

u i = j =i x -ξ j ξ i -ξ j = f f (ξ i )(x -ξ i ) for 1 ≤ i ≤ n.
It satisfies that for any polynomial p ∈ C[x] one has

(3) p(x) ≡ n i=1 p(ξ i ) u i (x) mod f.
The basis u 1 , . . . , u n is also defined by the conditions deg [START_REF] Parrilo | An explicit construction of distinguished representations of polynomials nonnegative over finite sets[END_REF] the following real polynomial

(u i ) ≤ n -1, 1 ≤ i ≤ n and u i (ξ j ) = δ i,j for 1 ≤ i, j ≤ n. This implies by (3) that (4) u 2 i ≡ u i mod f for 1 ≤ i ≤ n and u i u j ≡ 0 mod f for i = j. Given g ∈ R[x], Parrilo constructed in
k i=1 g(ξ i ) u 2 i + (n-k)/2 i=1 g(ξ k+2i )u k+2i + g(ξ k+2i )u k+2i 2 (5) = n i=1 g(ξ i ) u 2 i + 2 (n-k)/2 i=1 |g(ξ k+2i )| u k+2i-1 u k+2i ,
where the identity follows from the fact that the interpolation polynomials associated to the complex non-real roots of f are pairwise conjugate, i.e. u k+2i = u k+2i-1 . This polynomial is a sum of squares in R[x] whenever g is nonnegative at the real roots of f , as shown by identity (5), since for

1 ≤ i ≤ n-k 2 , g(ξ k+2i )u k+2i + g(ξ k+2i )u k+2i = 2 ( g(ξ k+2i )u k+2i ),
where denotes the real part. Furthermore, it is congruent to g modulo f since by ( 4) and (3) we have

n i=1 g(ξ i ) u 2 i +2 (n-k)/2 i=1 |g(ξ k+2i )| u k+2i-1 u k+2i ≡ n i=1 g(ξ i ) u i ≡ g mod f.
Inspired by this construction, we define for fixed

λ i ∈ R, 1 ≤ i ≤ n-k 2 , the polynomial (6) h = n i=1 g(ξ i ) u 2 i + 2 (n-k)/2 i=1 λ i u k+2i-1 u k+2i
which is also congruent to g modulo f for any choice of

λ i , 1 ≤ i ≤ n-k 2 .
Next proposition shows that for a range of values of λ i , this polynomial h is a sum of n linearly independent squares.

Proposition 2.2. Let f ∈ R[x] be a squarefree polynomial as in Nota- tion 2.1 and let g ∈ R[x] be such that g(ξ i ) > 0 for 1 ≤ i ≤ k. Fix λ i > |g(ξ k+2i )|, 1 ≤ i ≤ n-k
2 , and let

h = n i=1 g(ξ i ) u 2 i + 2 (n-k)/2 i=1 λ i u k+2i-1 u k+2i
be the polynomial h defined in [START_REF] Landau | Über die Darstellung definiter Funktionen durch Quadrate[END_REF], which is congruent to g modulo f . Then h is a positive weighted sum of n squares of linearly independent real polynomials of degree strictly bounded by n. More precisely,

h = n i=1 ω i h 2 i ( 7
)
where

• h i = u i and ω i = g(ξ i ) for 1 ≤ i ≤ k, • h k+2i-1 = (u k+2i ) - (g(ξ k+2i )) λ i + (g(ξ k+2i )) (u k+2i ), h k+2i = λ 2 i -|g(ξ k+2i )| 2 λ i + (g(ξ k+2i )) (u k+2i ),
and

ω k+2i-1 = ω k+2i = 2 (λ i + (g(ξ k+2i ))) for 1 ≤ i ≤ n-k 2 .
(Here and denote real and imaginary part respectively.) Proof. We first show that the expressions in ( 6) and (7) coincide.

Set

γ i := g(ξ k+2i ) for 1 ≤ i ≤ n-k 2 . Applying the identity (a + i b)(u + i v) 2 + (a -i b)(u -i v) 2 + 2 λ|u + i v| 2 = 2 (λ + a) u 2 -2 b u v + (λ -a) v 2 = 2(λ + a) (u - b λ + a v) 2 + (λ 2 -a 2 -b 2 ) ( v λ + a ) 2
for λ + a = 0, we get from Identity (6):

h = k i=1 g(ξ i ) u 2 i + (n-k)/2 i=1 γ i u 2 k+2i + γ i u k+2i 2 + 2 λ i |u k+2i | 2 = k i=1 g(ξ i ) u 2 i + (n-k)/2 i=1 2 (λ i + (γ i )) (u k+2i ) - (γ i ) λ i + (γ i ) (u k+2i ) 2 + (n-k)/2 i=1 2 (λ i + (γ i )) λ 2 i -|γ i | 2 λ i + (γ i ) (u k+2i ) 2 since λ i > |γ i | implies λ i + (γ i ) = 0 and λ 2 i -|γ i | 2 > 0. Now, observe that ω i > 0 since for 1 ≤ i ≤ k, ω i := g(ξ i ) > 0 by assumption, and for 1 ≤ i ≤ n-k 2 , ω k+2i-1 = ω k+2i := 2(λ i + (γ i )) > 0.
Therefore h is a positive weighted sum of n squares of polynomials of degree < n with real coefficients.

Finally, as the polynomials u i are linearly independent over C and u k+2i-1 = u k+2i , the real polynomials u 1 , . . . , u k , (u k+2 ), (u k+2 ), . . . , (u n ), (u n ) are also linearly independent. This implies that the real polynomials h 1 , . . . , h n are also linearly independent over R (and in particular nonzero).

We fix the following notation for the rest of the paper: Notation 2.3. We set S n (R) for the set of symmetric matrices in R n×n and S n + (R) for its cone of symmetric positive semidefinite matrices. We equip S n (R) with the Frobenius inner product A, B = trace(A B), ∀A, B ∈ S n (R), which induces the Frobenius norm • . The 2-norm on the coefficients of polynomials in R[x] is also denoted by • . For m ∈ N 0 we set R[x] m for the set of polynomials of degree bounded by m. Finally, x = [1, x, . . . , x n-1 ] T is the column vector of monomials of degree < n.

Note that for any polynomial p = d i=0 p i x i , one has

p f ≤ d i=0 p i x i f ≤ d i=0 |p i | x i f (8) ≤ d i=0 p f ≤ (d + 1) p f .
As a first corollary of Proposition 2.2, we have:

Corollary 2.4. Let f, g ∈ R[x]
with f of degree n with simple roots ξ i , 1 ≤ i ≤ n, and g of degree < n that is strictly positive at the real roots ξ 1 , . . . , ξ k of f . Then, there exists a pair

(Q, q) ∈ S n (R) × R[x] n-2 with Q positive definite such that g = x T Qx + q f . In particular Q ∈ Int(S n + (R))
, where Int denotes interior. Proof. For fixed

λ i > |g(ξ i )|, 1 ≤ i ≤ n-k
2 , let H be the coefficient matrix of the polynomials h 1 , . . . , h n of Proposition 2.2 in the monomial basis 1, x, . . . , x n-1 , so that [START_REF] Magron | On exact Reznick, Hilbert-Artin and Putinar's representations[END_REF] [h 1 , . . . , h n ] = x T H.

The matrix H is invertible since h 1 , . . . , h n are linearly independent. Let ∆ be the diagonal matrix

(10) ∆ = diag(ω 1 , . . . , ω n ).
Then [START_REF] Victor Magron | Exact SOHS decompositions of trigonometric univariate polynomials with Gaussian coefficients[END_REF] rewrites as

(11) h = x T H∆H T x = x T Q x
where Q := H∆H T is positive definite since H is invertible and ω i > 0 for 1 ≤ i ≤ n. Also, as h ≡ g mod f and deg(h) ≤ 2n -2, there exists

q ∈ R[x] n-2 such that g = h + q f . Finally Q ∈ Int(S n + (R)) since det(Q) > 0. Remark 2.5. The passage from h = n i=1 ω i h 2 i with ω i ∈ R >0 , 1 ≤ i ≤ n, to h = x T Qx where Q ∈ S n
+ (R) is a positive definite matrix, and vice-versa, is quite standard:

As shown in the proof of Corollary 2.4, Q = H∆H T where H and ∆ are defined in ( 9) and [START_REF] Victor Magron | Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials[END_REF].

Conversely, an exact square-root-free Cholesky decomposition of a positive definite matrix

Q ∈ S n + (R) yields Q = LDL T ,
where L is a lower unitriangular matrix and D is a diagonal matrix with positive entries. For instance, this decomposition can be computed exactly over Q through LU decomposition via Gaussian elimination of matrix Q.

Then ω 1 , . . . , ω n are the diagonal entries of D and

[h 1 , . . . , h n ] := x T L.
Note that when λ i = |g(ξ k+2i )|, which is the case in Parrilo's polynomial [START_REF] Kaltofen | Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients[END_REF], h k+2i = 0 and therefore these polynomials h i , 1 ≤ i ≤ n, are not linearly independent. This means that Parrilo's polynomial [START_REF] Kaltofen | Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients[END_REF] lies in the border of the cone S n + (R). What we were able to do in Proposition 2.2 is to modify Parrilo's construction in order to obtain a polynomial h in the interior of this cone. This gives room to perturb it a little in order to get a rational polynomial with the same characteristics, and yields the particular version of our main theorem when g is strictly positive at all the real roots of a squarefree polynomial f . To describe this construction, we introduce the following ingredients.

Notation 2.6. Let p = p 0 + p 1 x + • • • + p 2n-2 x 2n-2 ∈ R[x].
We define the affine space

Q p = {Q ∈ S n (R) : x T Q x = p},
and the symmetric matrix ( 12) . . . . . .

Q p =        p 0 p 1 2 . . . p n-2 n-1 p n-1 n p 1 2 . . . . . .
p 2n-3 2 p n-1 n pn n-1 . . . p 2n-3 2 p 2n-2        , which satisfies (13) x T Q p x = 2n-2 k=0 p k x k = p,
and therefore

Q p ∈ Q p .
We note for further use that we have ( 14)

Q p = 2n-2 k=0 s k p k s k 2 1/2 ≤ 2n-2 k=0 p 2 k 1/2 = p , where (15)
s k = s 2n-2-k = k + 1, 0 ≤ k ≤ n -1,
denotes the number of entries in each of the 2n -1 antidiagonals of Q p . We now describe the orthogonal projection from S n (R) on Q p for the Frobenius norm, in a more convenient matrix formulation for the univariate case than in [START_REF] Peyrl | Computing sum of squares decompositions with rational coefficients[END_REF]Prop.7], and prove it for sake of completeness.

Lemma 2.7. The map

π p : S n (R) -→ Q p , Q -→ Q -Q x T Qx-p
is the orthogonal projection onto the affine space Q p for the norm • .

Proof. Let Q ∈ S n (R). By (13), we have:

x T π p (Q) x = x T Qx -(x T Qx -p) = p,
and thus π p (Q) ∈ Q p . To prove that π p (Q) is the orthogonal projection of Q on Q p , we show that Q -π p (Q) is orthogonal to Q p :
We first observe that for any Q ∈ S n (R),

x T Qx = 2n-2 k=0 i+j=k+2 Q i,j x k = 2n-2 k=0 Q, H k x k , where for 0 ≤ k ≤ 2n -2, H k ∈ S n (R) is the Hankel matrix such that (H k ) i,j = 1 if i + j = k + 2 and 0 otherwise, 1 ≤ i, j ≤ n.
This shows that the affine space Q p is defined by the equations

Q, H k -p k = 0, k = 0, . . . , 2n -2,
which implies that the vector space

Q ⊥ p orthogonal to Q p is spanned by (H k ) 0≤k≤2n-2 .
On another hand we can easily verify from its definition that

Q p = 2n-2 k=0 p k s k H k ,
where s k is defined in [START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF]. Therefore,

Q -π p (Q) = Q x T Qx-p = 2n-2 k=0 Q, H k - p k s k H k , which shows that Q -π p (Q) is a linear combination of (H k ) 0≤k≤2n-2 ,
and thus orthogonal to Q p .

We are going to use this projection to compute a rational sum of squares modulo f for a polynomial g strictly positive at the real roots of f . Proposition 2.8. Let f ∈ Q[x] be a non-zero squarefree polynomial and g ∈ Q[x] be such that g is strictly positive at all the real roots of f . Then there exist polynomials h i ∈ Q[x] of degree < n and positive weights

ω i ∈ Q + , 1 ≤ i ≤ n, such that h := n i=1 ω i h 2 i satisfies h ≡ g mod f.
Proof. There is a natural proof of this proposition which makes use of the fact that the set

{(A, b) ∈ S n (R) × R[x] n-2 : g = x T Ax + b f }
is a real affine space which in the case that f, g ∈ Q[x] is defined by a rational basis and a rational particular point. This approach follows the proof of the analogous result for the global case mentioned as image representation in [START_REF] Peyrl | Computing sum of squares decompositions with rational coefficients[END_REF]Section 3.2].

Here, we give the proof that uses the orthogonal projection π p defined in Definition 2.6, as done for the global case in the kernel representation in [START_REF] Peyrl | Computing sum of squares decompositions with rational coefficients[END_REF]Section 3.1].

Without loss of generality we can assume that deg(g) < n by replacing it by its remainder modulo f . Let (Q * , q * ) be given by Corollary 2.4, i.e. g = x T Q * x + q * f and

Q * ∈ Int(S n + (R))
, and let σ > 0 be the smallest eigenvalue of Q * , which is the distance of Q * to the set of singular matrices, so that the open ball centered at Q * and of radius σ is contained in

S n + (R). Take a rational approximation (Q, q) ∈ S n (Q) × Q[x] n-2 such that Q -Q * < σ 2 and q -q * < σ 2(n -1) f . ( 16
)
The problem is that most surely, x T Qx + q f = g. Let e := x T Qx + qf -g be the error polynomial, and define

Q := π g-qf (Q) = Q -Q e ∈ S n (Q), which is the orthogonal projection of Q on Q g-qf according to Lemma 2.7. Then Q ∈ Q g-qf , i.e. x T Qx + qf = g. Next we prove that Q ∈ Int(S + (Q)) by proving that Q -Q * < σ. We have Q -Q * ≤ π g-q f (Q) -π g-q f (Q * ) + π g-q f (Q * ) -Q * ≤ π g-q f (Q) -π g-q f (Q * ) + π g-q f (Q * ) -π g-q * f (Q * ) ≤ Q -Q * + Q * -Q x T Q * x-(g-q f ) -Q * -Q x T Q * x-(g-q * f ) ≤ Q -Q * + Q (q * -q) f , since x T Q * x + q * g = g implies Q * = π g-q * f (Q * ).
By ( 14) and ( 8) we have

Q (q * -q) f ≤ (q * -q) f ≤ (n -1) q * -q f
since deg(q * -q) ≤ 2n -2. Finally, by ( 16), we conclude

Q -Q * < σ 2 + (n -1) σ 2(n -1) f f = σ.
This implies that Q ∈ Int(S n + (R)), i.e. h = x T Q x is a rational positive weighted sum of squares.

Example 2.9. We now consider a toy example to illustrate our construction. This is a toy example because in this case we know the roots of f and use that knowledge, as in the proof or our existential theorem. Let f = x 3 -2 = (x -2 1/3 )(x -2 1/3 ω)(x -2 1/3 ω), where ω = e 2πi /3 , and g = x, which is strictly positive at 2 1/3 . Set ξ 1 = 2 1/3 , ξ 2 = 2 1/3 ω and ξ 3 = ξ 2 .

Parrilo's construction [START_REF] Kaltofen | Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients[END_REF] gives in this case the following real polynomial, which is congruent to g modulo f and a sum of 2 squares:

g(ξ 1 )u 1 (x) ∈R[x] 2 + g(ξ 2 )u 2 (x) + g(ξ 3 )u 3 (x) ∈R[x] 2 = x T Q * x
where

Q * =     2 3 √ 2 9 2 9 - 3 √ 4 18 2 9 3 √ 4 18 - 3 √ 2 18 - 3 √ 4 18 - 3 √ 2 18 5 18     .
Note that Q * is a rank 2 positive semidefinite matrix, which therefore lies in the border of the cone of positive semidefinite matrices. Now, if we take λ := 2|g(ξ 2 )| = 2 • 2 1/3 in our construction (6), we get h * = x T Q * x where

Q * =     4 3 √ 2 9 1 9 - 3 √ 4 9 1 9 2 3 √ 4 9 - 3 √ 2 9 - 3 √ 4 9 - 3 √ 2 9 7 18    
is a (rank 3) definite positive matrix with smallest eigenvalue σ ∼ 0.2239, and

g = x T Q * x + q * f for q * = - 7 18 x + 2 3 √ 2 9
.

Here, if we take the following rational approximations of Q * and q * (rounding to two significant digits)

Q =   0.6 0.1 -0.2 0.1 0.4 -0.1 -0.2 -0.1 0.4   and q = -0.4x + 0.3
we get that Q * -Q ∼ = 0.0923 and q * -q ∼ = 0.0229. Thus, we have

Q * -Q < σ 2 ∼ = 0.112 and q * -q < σ 2(n-1) f ∼ = 0.025 respectively,
satisfying both of the bounds given in ( 16) required in the proof of Proposition 2.8. We have x T Q x + q f = 0.1x 3 + x = g, with error e = x T Q x + q f -g = 0.1x 3 .

Compute the orthogonal projection of

Q on Q g-qf : Q = π g-qf (Q) = Q -Q e =   0.6 0.1 -0.2 0.1 0.4 -0.15 -0.2 -0.15 0.4   so that x Q x -x T Q x = e and Q is still a definite positive matrix. Then matrix Q ∈ S 3 (Q) satisfies h := x T Q x = x T Q x -e = g -q f ≡ g mod f,
and h is a sum of squares of rational polynomials, which we can obtain applying the square-root-free Cholesky decomposition of Q (Remark 2.5) as follows:

h = 3 5 1 + 1 6 x - 1 3 x 2 2 + 23 60 x - 7 23 x 2 2 + 137 460 x 4 .

The general case.

In this subsection we generalize the results of the previous section to the case when f is non-necessarily squarefree and g is non-negative at all the real roots of f (but might vanish on some of them), as long as gcd(f, g) and f / gcd(f, g) are relatively prime, in order to obtain our main theorem. We will need the following auxiliary results, namely Hensel lemma and Chinese remainder theorem.

Lemma 2.10. Let p, g ∈ Q[x] with p irreducible in Q[x] which does not divide g. Assume that there exists h 1 , . . . , h N ∈ Q[x] and ω 1 . . . , ω N ∈ Q + for some N ∈ N with deg(h i ) < deg(p) such that g ≡ N i=1 ω i h 2 i mod p.
Then for any fixed e ∈ N, e ≥ 1, there exist h

1 , . . . , h N ∈ Q[x] with deg(h i ) < e • deg(p) such that g ≡ N i=1 ω i h 2 i mod p e .
Proof. We show that it suffices to perform Hensel lifting on one of the polynomials h i . Since p ∈ Q[x] is irreducible and does not divide g, one of the h i at least is not divisible by p, and w.l.o.g. we assume that it is h 1 . Define

g = g ω 1 for N = 1 and g := g - i=2 ω i h 2 i ω 1 ∈ Q[x] for N > 1.
Then g ≡ h 2 1 mod p, and we define the following Newton iteration starting from h (0)

1 := h 1 : (17) h (k+1) 1 ≡ 1 2 h (k) 1 + g h (k) 1 ≡ 1 2 h (k) 1 + s (k) 1 g mod p 2 k+1 for k ≥ 0,
where s

(k) 1 ∈ Q[x] is defined by s (k) 1 h (k) 1 ≡ 1 mod p 2 k+1 . First note that this sequence is well defined in Q[x] since by induc- tion, h (k) 1 ≡ 1 2 h (0) 1 + h (0) 1 2 h (0) 1 ≡ h (0) 1 mod p,
and therefore h

(k)
1 is prime to the irreducible polynomial p since h (0)

1 is, and hence invertible modulo p 2 k+1 .

We now prove by induction that h (k) 1 ) 2 ≡ g mod p 2 k : First, from [START_REF] Von | Modern computer algebra[END_REF] we derive ( 18)

h (k) 1 h (k+1) 1 ≡ 1 2 h (k) 1 ) 2 + g mod p 2 k+1 .
Now, by the inductive hypothesis, h

(k) 1 2 ≡ g mod p 2 k implies that h (k+1) 1 ≡ 1 2 h (k) 1 + s (k) 1 h (k) 1 2 mod p 2 k ≡ 1 2 h (k) 1 + h (k) 1 ≡ h (k) 1 mod p 2 k . Therefore, h (k) 1 = h (k+1) 1 + t p 2 k for some t ∈ Q[x]
and from (18),

h (k+1) 1 + t p 2 k h (k+1) 1 ≡ 1 2 h (k+1) 1 + t p 2 k 2 + g mod p 2 k+1 ≡ 1 2 h (k+1) 1 2 + 2t p 2 k h (k+1) 1 + g mod p 2 k+1
and we can cancel t p 2 k h (k+1) 1 from both sides. We conclude

h (k+1) 1 ) 2 ≡ 1 2 h (k+1) 1 2 + g mod p 2 k+1
which implies

h (k+1) 1 2 ≡ g mod p 2 k+1 .
Going back to the definition of g,

g = ω 1 g + N i=2 ω i h 2 i ≡ ω 1 h (k) 1 2 + N i=2 ω i h 2 i mod p 2 k .
Finally, if we choose k such that 2 k-1 < e ≤ 2 k and define

h 1 := h (k) 1
mod p e , h i := h i for 2 ≤ i ≤ N and ω 1 , . . . , ω N unchanged then we get the sum of squares decomposition of g modulo p e with the desired degree bounds.

Lemma 2.11. Let f 1 , . . . , f r ∈ Q[x] with gcd(f i , f j ) = 1 for 1 ≤ i < j ≤ r. Assume that g ∈ Q[x] satisfies g ≡ N i j=1 ω i,j h 2 i,j mod f i , 1 ≤ i ≤ r, for some N i ∈ N, h i,j ∈ Q[x] with deg(h i,j ) < deg f i and ω i,j ∈ Q + , for 1 ≤ j ≤ N i . Then there exist N ∈ N, h 1 , . . . , h N ∈ Q[x] and ω 1 , . . . , ω N ∈ Q + such that g ≡ N i=1 ω i h 2 i mod r i=1 f i . Furthermore, deg(h i ) < r i=1 deg(f i ) for 1 ≤ i ≤ N . Proof.
The usual Chinese remainder theorem for a system

g ≡ g i mod f i , 1 ≤ i ≤ r, admits the solution (c.f. [17, Algorithm 5.4]) g ≡ s 1 f (1) g 1 + • • • + s r f (r) g r mod f where f := r i=1 f i , f (i) := j =i f j and s i is defined by s i f (i) + t i f i = 1 for 1 ≤ i ≤ r.
On another side, notice that

s i f (i) ≡ (s i f (i) ) 2 mod f, 1 ≤ i ≤ r, since s i f (i) ≡ 1 mod f i and s i f (i) ≡ 0 mod f j for j = i. Then g ≡ (s 1 f (1) ) 2 g 1 + • • • + (s r f (r) ) 2 g r mod f.
In our setting, since g i := N i j=1 ω i,j h 2 i,j we get

g ≡ r i=1 (s i f (i) ) 2 N i j=1 ω i,j h 2 i,j mod f ≡ r i=1 N i j=1 ω i,j (s i f (i) h i,j ) 2 mod f.
We get N := r i=1 N i and reduce s i f (i) h i,j modulo f to achieve the desired degree bounds in the SOS decomposition.

We are now able to prove the full version of our theorem. We repeat the statement here for the reader's convenience. Theorem. Let f ∈ Q[x] be a non-zero polynomial of degree n and g ∈ Q[x] be such that gcd(f, g) and f / gcd(f, g) are relatively prime. Assume that g is non-negative at all the real roots of f . Then there exist polynomials h i ∈ Q[x] of degree < n and positive weights

ω i ∈ Q + , 1 ≤ i ≤ N for some N ∈ N, such that h := N i=1 ω i h 2 i satisfies h ≡ g mod f.
Proof. First assume that gcd(f, g) = 1. Note that therefore, the assumption that g is non-negative at the real roots of f implies that g is strictly positive at the real roots of f . W.l.o.g. we can assume that f is monic. Suppose f has the following decomposition over Q into powers of irreducible factors in Q

[x] f = p e 1 1 • • • p er r
where p i are distinct monic irreducible polynomials in Q[x], e i ∈ N for 1 ≤ i ≤ r, and r i=1 e i deg(p i ) = n. Fix i ∈ {1, . . . , r}. Since g is strictly positive at the real roots of the irreducible polynomial p i , we can apply Proposition 2.8 to p i and g, which shows the existence of

h i,j ∈ Q[x] of degree < N i := deg(p i ) and ω i,j ∈ Q + for 1 ≤ i ≤ N i , such that g ≡ N i j=1 ω i,j h 2 i,j mod p i .
Next we apply Lemma 2.10 with p = p i and e = e i to show the existence of

h i,j ∈ Q[x] of degree < e i deg(p i ), 1 ≤ i ≤ N i , such that (19) g ≡ N i j=1 ω i,j h 2 i,j
mod p e i i .

Finally we apply Lemma 2.11 with f i = p e i i for 1 ≤ i ≤ r to combine the congruences in (19) and obtain

N ∈ N, h, h 1 , . . . , h N ∈ Q[x] and ω 1 , . . . , ω N ∈ Q + such that h := N i=1 ω i h 2 i satisfies h ≡ g mod f. Furthermore, deg(h i ) < r i=1 e i deg(p i ) = n for 1 ≤ i ≤ N .
This proves the claim for an arbitrary polynomial f with gcd(f, g) = 1.

Assume now that d := gcd(f, g) = 1. We show that under our assumption gcd(f /d, d) = 1, there is a polynomial b ∈ Q[x] relatively prime to f /d which satisfies that b d 2 ≡ g mod f and therefore b is strictly positive at the real roots of f /d:

The assumption implies that gcd(f /d, g) = 1, and therefore g is strictly positive at the real roots of f /d. Since gcd(f /d, d 2 ) = 1 as well, there exist s, t

∈ Q[x] s.t. 1 = s • f d + t • d 2 .
This implies in particular gcd(f /d, t) = 1 and that

(20) g = s • g d • f + (tg) • d 2 .
We We then apply our previous construction to b and f /d: There exist

h i ∈ Q[x] of degree < n -deg(d) and ω i ∈ Q + , 1 ≤ i ≤ N , such that h := N i=1 ω i h 2 i satisfies h ≡ b mod f d .
Therefore,

d 2 h = N i=1 ω i (d h i ) 2 and d 2 h ≡ b d 2 mod f. Since b d 2 ≡ g mod f we conclude that d 2 h ≡ g mod f.
We note that deg(d h i ) < n, thus h := d 2 h, h i := d h i and ω i , 1 ≤ i ≤ N , satisfy the claim of the theorem.

Example 2.12. Let us again consider a toy example to show how it works when gcd(f, g) = 1 and f is not squarefree.

Consider f = x(x 3 -2) 2 and g = x 3 . Here d = gcd(f, g) = x and f /d = (x 3 -2) 2 are relatively prime, so we are in the assumptions of our theorem.

In this case, as g/d 2 = x is already a polynomial, we can take tg = g/d 2 = x.

(1) Find rational SOS for g/d 2 = x modulo (x 3 -2) (see Example 2.9):

x ≡ 3 5 1 + 1 6 x - 1 3 x 2 2 + 23 60 x - 7 23 x 2 2 + 137 460 x 4 mod (x 3 -2).
(2) Apply Hensel lifting to find rational SOS for g/d 2 = x modulo (x 3 -2) 2 (note that we lift only the last term): i.e. x ≡ ω 1 h

x ≡ 3 5 1 + 1 6 x - 1
2 1 + ω 2 h 2 2 + ω 3 h 2 3 mod f /d = (x 3 -2) 2 . (3) Multiply both sides by d 2 = x 2 : g ≡ ω 1 (xh 1 ) 2 + ω 2 (xh 2 ) 2 + ω 3 (xh 3 ) 2 mod f = x(x 3 -2) 2 .

The algorithm

In this section, we describe the algorithm announced in the introduction, that computes a certificate of non-negativity of a polynomial g ∈ Q[x] at the real roots of another polynomial f ∈ Q[x].

3.1.

Certificate for a strictly positive polynomial. Here we assume that f ∈ Q[x] is a squarefree polynomial of degree n, and that g is strictly positive at all the real roots of f . We consider the following optimization problem

(21) max λ s.t. Q -λ I 0 q ∈ R[x] n-2 g = x T Q x + q f
where x = [1, . . . , x n-1 ] T is the vector of monomials of degree < n and Q ∈ S n (R). (Here 0 denotes positive semidefinite.) It is finding the maximal λ, which is bounded from above by all the eigenvalues of symmetric matrices Q satisfying g = x T Q x + q f . The set

C = {(Q, q) ∈ S n (R) × R[x] n-2 : Q 0, g = x T Q x + q f }
is convex, as the intersection of the linear space

{(Q, q) ∈ S n (R) × R[x] n-2 , g -x T Q x -q f = 0} with the convex cone S n + (R) × R[x] n-2 .
If the optimal value λ * of (21) is strictly positive, then the relative interior of C is non-empty.

By solving the convex optimization problem (21) using a numerical interior point solver, working at a given precision µ, we obtain an approximation of an interior point of C where the objective function reaches its maximum λ * > 0. This yields a rational approximation of an interior point (Q * , q * ) of the convex set C. That is, the numerical solver computes a (rational) approximate solution (Q * , q * ) of the optimization problem (21), where if the precision µ is good enough and λ * > 0, Q * ∈ S n + (Q) is a positive definite matrix but there will be an error polynomial x T Q * x + q * f -g = 0, although close to 0.

Since (Q * , q * ) may have a lot of decimals, in order to obtain a rational decomposition of g modulo f of small size, we start by rounding, at a convenient precision δ > 0, Q * ∈ S n + (R) to a nearby Q ∈ S n (Q) and q * ∈ R[x] ≤n-2 to a nearby rational polynomial q ∈ Q[x] ≤n-2 . We then compute the projection Q := π g-q f (Q) ∈ Q g-q f which satisfies g = x T Q x + q f . As in the proof of Proposition 2.8, if Q -Q * is smaller than the smallest eigenvalue σ of Q * , then Q ∈ S n + (Q) is a rational positive definite matrix and g = x T Qx + qf gives a rational SOS decomposition of g modulo f , that is (x T Qx, q) is a rational certificate of positivity of g at the real roots of f . Given the approximate solution (Q * , q * ) output by the numerical solver, we detail in the following proposition a bound on the rounding precision δ chosen to define (Q, q) needed to guarantee that Q = π g-qf (Q) is a positive definite matrix. We assume here that the matrix Q * output by the solver is positive definite. Proposition 3.1. Let σ > 0 be the smallest eigenvalue of Q * and assume that ρ :

= x T Q * x + q * f -g < σ. Set 0 < δ < 1 n + (n -1) √ n f (σ -ρ).
Then, for any rational approximations

(Q, q) ∈ S n (Q) × Q[x] n-2 of (Q * , q * ) such that |Q i,j -Q * i,j | ≤ δ, 1 ≤ i, j ≤ n and |q i -q * i | ≤ δ, 0 ≤ i ≤ n -2, the symmetric matrix Q = π g-qf (Q) ∈ S n (Q), which satisfies g = x T Q x + q f , is positive definite. Proof. We have Q -Q * ≤ n δ and q -q * ≤ √ n δ.
Then, the distance between Q = π g-q f (Q) and Q * can be bounded, as in the proof of Proposition 2.8 but with the difference that Q * = π g-q * f (Q * ), as follows:

Q -Q * ≤ π g-q f (Q) -π g-q f (Q * ) + π g-q f (Q * ) -π g-q * f (Q * ) + π g-q * f (Q * ) -Q * ≤ Q -Q * + Q * -Q x T Q * x-(g-qf ) -(Q * -Q x T Q * x-(g-q * f ) + Q x T Q * x-(g-q * f ) ≤ Q -Q * + Q (q * -q)f + Q x T Q * x-(g-q * f ) .
Using ( 14) and ( 8), as in the proof of Proposition 2.8 we have

Q (q * -q) f ≤ (n -1) q * -q f ≤ (n -1) √ n δ f and Q x T Q * x-(g-q * f ) ≤ x T Q * x + q * f -g = ρ. As Q -Q * ≤ n δ, we deduce that Q -Q * ≤ (n + (n -1) √ n f ) δ + ρ < (σ -ρ) + ρ = σ Therefore Q is positive definite.
The approximation of σ and the norm ρ of the error polynomial x T Q * x + q * f -g, which is approximately 0, depend on the precision µ of the solver. If ρ > σ, we need to increase the precision µ of the numerical solver and compute a new solution (Q * , q * ).

We can now summarize the certification algorithm for a strictly positive polynomial, in Algorithm 3.1, which is implemented in the function exact decompose of Julia package MomentTools.jl 1 .

3.2.

Certificate for a non-negative polynomial. We consider now the case where f arbitrary and g non-negative at the real roots of f satisfy the assumption that gcd(f, g) and f / gcd(f, g) are relatively prime. We set d := gcd(f, g).

We closely follow the proof of our main Theorem in Section 2. We first compute b ∈ Q[x] relatively prime to f /d such that b is strictly positive at the real roots of f /d and b d 2 ≡ g mod f .

We then compute the irreducible factorization of f /d = r i=1 p e i i where the polynomials p i ∈ Q[x] are irreducible, thus with simple roots, and pairwise relatively prime. We observe that b and p i are relatively prime, and that b is strictly positive on the real roots of p i , 1 ≤ i ≤ r.

We set b i to be the remainder of b modulo p i , 1 ≤ i ≤ r, and we apply Algorithm 3.1 to p i and b i . We get the rational SOS certificate b i = x T Q i x + q i p i 1 https://gitlab.inria.fr/AlgebraicGeometricModeling/MomentTools.jl and we finally compute q

∈ Q[x] s.t. g = N i=1 ω i (dh i ) 2 + q f.
This computation is summarized in Algorithm 3.2. Algorithm 3.2: Rational SOS certificate for a non-negative polynomial

Input: f ∈ Q[x] n , g ∈ Q[x]
such that g ≥ 0 at the real roots of f and gcd(f, g) and f / gcd(f, g) are relatively prime.

(

h i ← d h i ; (7) Compute q ∈ Q[x] s.t. g = i ω i h 2 i + q f ; Output: ω i ∈ Q + , h i ∈ Q[x], q ∈ Q[x] satisfying g = i ω i h 2 i + q f.

3.3.

Example. We now revisit Example 2.9 to illustrate the symbolicnumeric approach based on Semi-Definite-Programming. The norm of the error polynomial is ρ ≈ 1.16e -15 so that δ ≈ 0.0227 and rounding with t = 2 decimal digits yields a positivity certificate.

In fact, in this case, rounding with one decimal digit is enough: It is a positive definite matrix (its eigenvalues are approximately 0.24507, 0.505399, 0.816198) which induces a rational SOS decomposition of g modulo f .

Q =   0.

Conclusion

In this work,

(1) we showed that a univariate rational polynomial g is strictly positive at all the real roots of a univariate rational squarefree polynomial f if and only if it is a sum of squares of rational univariate polynomials modulo f . To our knowledge, this fact was known for univariate polynomials in the global setting but not in the local setting; (2) we showed that the usual assumption of g being strictly positive at the real roots of a squarefree polynomial f can be relaxed to non-negative when gcd(f, g) and f / gcd(f, g) relatively prime, which we believe is the best assumption one can obtain;

(3) we produced an algorithm for the local setting, which is the counterpart of known algorithms for the global setting in the strictly positive case, and involves Hensel lifting and Chinese Remainder Theorem in the non squarefree and non-negative case. Our projects are to derive bit complexity estimates for the proposed algorithms and also to try to extend our results to the multivariate local setting of polynomials being non-negative at the real zero set of a zerodimensional ideal. Some of them can be extended mutatis-mutandis but there is still work to be done on the relaxation of the assumptions.

  . . . . . . . . . . . . p n-2 n+1

  set b := tg. Then b and f /d are relatively prime since t and f /d, and g and f /d are. Therefore b is striclty positive at the real roots of f /d because for any such root ξ, d(ξ) = 0, b(ξ) = 0 and b(ξ)d 2 (ξ) = g(ξ) ≥ 0.Finally, (20) implies that b d 2 ≡ g mod f .

Example 3 . 2 .

 32 Let f = x 3 -2 = (x-2 1/3 )(x-2 1/3 ω)(x-2 1/3 ω), where ω = e 2πi /3 , and g = x.Solving the convex optimization program:max λ s.t. Q ∈ S 3 (R), Q -λ I 0 q ∈ R[x] 1 g = x t Qx + qfwe obtain the matrix Q * of maximal rank and the polynomial q * : -0.5167531 x + 0.3161031.The eigenvalues of Q * are approximately: 0.246693, 0.5292293, 0.8321596.

5 

 5 and q = -0.5 x + 0.3, with error e = x T Qx + q f -g = -0.1x 3 + 0.1x 2 yieldQ = π g-qf (Q) = Q -Q e =

  1) d ← gcd(f, g); (2) Compute b ∈ Q[x] s.t. b is prime to f /d, strictly positive at the real roots of f /d and b d 2 ≡ g mod f . (3) Compute the factorization f /d = r i=1 p e i i into irreducible factors in Q[x]; (4) For each irreducible factor p i , b i ← the remainder of b modulo pi ; (Q i , q i ) ← output of Algorithm 3.1 applied to b i and p i ; Compute ω i,j ∈ Q + , h i,j ∈ Q[x] such that Compute ω i ∈ Q + , h i ∈ Q[x] such that

	b i ≡
		i,j	mod p e i i
	using Hensel lifting in Lemma 2.10;
	(5) b ≡	ω i h 2 i	mod f /d
	i
	using Chinese Remainder construction in Lemma 2.11;
	(6)

j ω i,j h 2 i,j mod p i ; Compute h i,j ∈ Q[x] such that b i ≡ j ω i,j h 2

The research of Teresa Krick was partly supported by CONICET PIP-11220130100073CO and BID-PICT 2018-02315. The work of Bernard Mourrain was partly supported by the European Unions Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie Actions, grant agreement 813211 (POEMA). The research of Agnes Szanto was partly supported by NSF grant CCF-1813340.

Algorithm 3.1: Rational SOS certificate modulo a squarefree polynomial for a strictly positive polynomial

n-1 such that g > 0 at the real roots of f .

(1) µ ← µ 0 default precision of the interior point solver.

(2) (Q * , q * ) ← solution of the SDP problem (21) by the numerical interior point solver working at precision µ;

rational coefficients, with log 10 (δ -1 ) exact digits after decimal point; (7) q ← round q * to rational coefficients, with log 10 (δ -1 ) exact digits after decimal point;

where, setting

We deduce from the square-root-free Cholesky factorisation of Q i (cf. Remark 2.5) an SOS decomposition

By Hensel lifting (Lemma 2.10), we deduce an SOS decomposition of b modulo p e i i , and by the Chinese Remainder Theorem (Lemma 2.11), we deduce an SOS decomposition of b modulo f /d: b

Using that b d 2 ≡ g mod f , this gives the following SOS decomposition of g modulo f :