Lynda Ferez

Thierry Thami

Edefia Akpalo

Valérie Flaud

Lara Tauk

Jean-Marc Janot

Philippe Déjardin
email: philippe.dejardin@iemm.univ-montp2.fr

Interface of Covalently bonded phospholipids with a phosphorylcholine head: characterization, protein non adsorption and further functionalization

Keywords: biocompatibility, phosphorylcholine, biosensor, PMHS, silicone gel, hydrosilylation, phospholipid, antifouling

Surface anchored poly(methylhydrosiloxane) (PMHS) thin films on oxidized silicon wafers or glass substrates were functionalized via the SiH hydrosilylation reaction with the internal double bonds of 1,2-dilinoleoyl-sn-glycero-3-phosphorylcholine (18:2 Cis). The surface was characterized by X-ray photoelectron spectroscopy, contact angle measurements, atomic force microscopy and scanning electron microscopy. These studies showed that the PMHS top layer could be efficiently modified resulting in an interfacial high density of phospholipids. Grafted phospholipids made the initially hydrophobic surface ( = 106°) very hydrophilic and repellent towards avidin, bovine serum albumin, bovine fibrinogen, lysozyme and -chymotrypsin adsorption in phosphate saline buffer pH 7.4. The surface may constitute a new background-stable support with increased biocompatibility. Further possibilities of functionalization on the surface remain available owing to the formation of interfacial SiOH groups by Karstedt-catalyzed side reactions of SiH groups with water. The presence of interfacial SiOH groups was shown by zeta potential measurements. The reactivity and surface density of SiOH groups were checked by fluorescence after reaction of a monoethoxy silane coupling agent bearing alexa as fluorescent probe.

Introduction

The efficiency of sensors for biomedical analysis is dependent on the integrity and accessibility of the surface-fixed molecule designed for molecular recognition, on the one hand, and on the surroundings designed for neutral behavior, especially to avoid non specific adsorption, on the other hand. The last requirement leads in practice to diagnostic kits using blocking buffers containing typically albumin 1,2 .

Neutral behavior is also required for biomaterials where the biological functions of the fluid components have to be preserved. For instance, the proteins should present no conformational changes in solution, 3 possibly induced by adsorption at interfaces, as this could trigger cascades of biological reactions. 3 Even active biomaterials for cell culture, for instance, could be considered as surfaces with specific anchoring and functional points positioned on a neutral surface.

Several strategies were considered to create surfaces with neutral behavior. They can be roughly classified into two categories: 4 the first being based on poly(ethylene oxide) -PEO -, 3,[5][6][7][8][9][10][11][12][13][14][15][16] and the second on zwitterionic groups [17][18][19] , especially the phosphorylcholine head. The reason for their efficiency is that they are very hydrophilic. They can retain numerous molecules of water. The choice of a phosphorylcholine (PC) head is justified by the large number of phospholipids bearing that head on the external side of the bilayer membrane of cells. 20 Phospholipid polymers were developed many years ago. [21][22][23][24][25][26] Chemical transformation of the phospholipids was then necessary to obtain first the polymerizable functional group as was the case when individual surface grafting was carried out. 27 The availability of 2-methacryloyloxyethyl phosphorylcholine (MPC) monomer has resulted in several studies with polymers based on this monomer [28][29][30][31][32][33][34][35][36][37] in particular recently when the reaction of the monomer with triethoxysilane was investigated before covalent fixation on titanium alloy 38 .

Modification of existing polymers to obtain PC side chains was carried out for polyelectrolyte multilayer applications. 39 Grafting of PC on hydroxylated gold surfaces was also studied. 40 Instead of considering synthesis and adsorption of various (co)polymers containing PC or ethylene oxide (EO) chains, we looked at the possibility of creating soft structures aimed at covalent bonding of these groups in high density. In the present study PC grafting was considered preferable to EO where hydration layer stability decreases as the temperature increases. 41 Moreover, polymers based on EO can decompose in the presence of oxygen and transition metal ions. 42 We followed the strategy of hydrosilylation. Silicone gels such as polydimethylsiloxane (PDMS) have been previously considered as starting materials requiring surface modification to improve biocompatibity. The aim was to introduce Si-H functional groups for subsequent reactions. Several approaches have been developed to introduce SiH onto silicone gels such as plasma treatment, 43 acid catalyzed equilibration in the presence of polymethylhydrosiloxane (PMHS), 44,45 and 4 copolymerization. [46][START_REF] Thompson | Silicon Based Polymers: Advances in Synthesis and Supramolecular Organization[END_REF][START_REF] Guo | [END_REF] Indeed, hydrosilylation of an alkene C=C by addition of SiH is a very effective reaction in the bulk or in solution by using platinum catalysts. [49][50][51] The reaction is irreversible and the resulting Si-C bond is hydrolytically stable. In addition PMHS gels have been shown to be stable for several months 52,53 before subsequent functionalization. The functional SiH groups are used to add hydrophilic moieties like PEO [44][45][46][START_REF] Thompson | Silicon Based Polymers: Advances in Synthesis and Supramolecular Organization[END_REF][START_REF] Guo | [END_REF] or PC groups via the monomer MPC 54 thus increasing the protein repellent properties. These methods often result in incomplete surface coverage after hydrosilylation with the functional molecule, partly due to a low density of SiH groups.

We developed recently a new method that allows control of the accessibility of SiH groups by using solgel process of lightly crosslinked PMHS materials in order to increase the functionalization density of silicone layers by the molecule of interest 55,56 . The sol-gel process allowed a facile and rapid formation of a thin PMHS layer covalently grafted on the silica surface at room temperature. In addition, the process of film crosslinking and surface attachment on silica occurs in one step giving homogeneous and flat films in the nanometer range allowing further reaction with alkenes 56 . PMHS layers were prepared by acid-catalyzed hydrolytic polycondensation of a mixture of methyldiethoxysilane monomer and triethoxysilane as crosslinker. Moreover, it was shown that in a soft network (5% of crosslinker) complete platinum catalyzed addition of alkene molecules up to C 18 could occur 55 . We believe that this method has opened a new way to obtain very hydrophilic domains with high density of moieties like EO or PC.

The present work was therefore focussed on the functionalization of oxidized silicon wafers and glass substrates with PC via PMHS. Instead of synthesizing molecules with the PC functional group, we took advantage of the availability of phospholipids with long fatty chains which would also give a closer biomimetism of the cell bilayer membrane surface. The large molecular size should moreover lead to only limited functionalization inside the bulk of the layer but quantitative functionalization at the surface of the material. Contrary to the material obtained from photopolymerization of diacetylenic phospholipids, 25 the final layer should not be colored. Moreover additional stabilizing hydrophobic interactions between the fatty chains are expected in an aqueous environment. Such stabilization of the 5 assembly of non covalently bonded phospholipids has also been achieved by heating / cooling. 57 Previously 58 other studies concluded that for polymerized planar supported bilayers, to ensure quantitative lipid retention upon removal from water, all the lipids must be covalently anchored to the polymer network. Also important is the absence of defects. 59 The high density of SiH functional groups could also favor complete consumption of the unsaturated carbon-carbon bonds leading to a final product protected against self-oxidation. In summary we adopted the strategy, which we have previously applied in the development of a sensor for nitroaromatics 60 , of establishing first a soft thin threedimensional network scaffold where unsaturated phospholipids could be subsequently grafted in a second step.

With this aim, we first deposited by the sol-gel process an anchored layer of the PMHS network and functionalized it afterwards by reaction of the silane groups with the unsaturated phospholipid 1,2dilinoleoyl-sn-glycero-3-phosphorylcholine (18:2 Cis). The commercially available phospholipid molecule bearing four unsaturated double bonds which are all reactive toward hydrosilylation was chosen in order to be able to observe a significant infrared absorption signal of the C=C bond for the bulk starting material. A 1 µm thick PMHS layer allowed this common infrared analysis. The final product interface was characterized by photoelectron spectroscopy (XPS), captive bubble contact angle measurements in water, atomic force microscopy (AFM) and scanning electron microscopy (SEM). The adsorption of avidin, bovine serum albumin, bovine fibrinogen, lysozyme and -chymotrypsin were studied by means of normal scanning confocal fluorescence. We used a method for the quantitative determination of interfacial concentration. In addition, creation of new functional groups at such interfaces was shown to be easy and their interfacial density was determined by the same method.

Materials and Methods

Chemicals 6

Both precursors methyldiethoxysilane HSi(CH 3 )(OCH 2 CH 3 ) 2 (DH) and triethoxysilane HSi(OCH 2 CH 3 ) 3 (TH) were purchased from ABCR (Karlsruhe, Germany) and used as received. Water for substrate cleaning was obtained from a Milli-Q water purification apparatus (Millipore). Absolute ethanol for solgel synthesis was of synthesis grade purity. The sol-gel catalyst trifluoromethanesulfonic acid CF 3 SO 3 H was purchased from Aldrich. Toluene for thin film hydrosilylation was distilled before use. The platinum-divinyltetramethyldisiloxane complex in xylene (platinum concentration ca. 0.1 M assuming 2.4% (w) Pt in xylene), also known as Karstedt's catalyst, was purchased from ABCR (PC072). 1,2-dilinoleoyl-sn-glycero-3-phosphorylcholine (18:2 Cis) (PL, Fig. 1) was purchased from AvantiPolarLipids.

Other chemicals were used as received: 3-(ethoxydimethylsilyl)-propyl amine (Aldrich, 588857), Alexa Fluor® 594 succinimidyl ester (labelling kit A10239, InvitroGen), biotin-ethylenediamine hydrobromide (Sigma B9181).

Proteins and labeling

Bovine serum albumin (A-7638), bovine fibrinogen (F-8630), lysozyme (62971-Fluka), chymotrypsin (C-4129) and avidin (A9275) were purchased from Sigma-Aldrich; some avidin from Fluka (No. 11368). Labeling of proteins was performed with Alexa-fluor-594 succinimidyl ester (InvitroGen, A30008). Typically 500 µL of protein solution were added to dry fluorophore Alexa-594 in molar ratio 1:1 and allowed to react for 0.5 h at 20°C. Avidin was also labelled via the previous biotinethylenediamine hydrobromide reaction with alexa succinimidyl ester as described elsewhere 61 . The mixture was then put in an ad hoc microtube with filter (Biospin P6) and centrifuged at 16 000 g for 1 min according to the supplier of the kit. The labeling ratio [Alexa] / [protein] (0.3-0.5) was determined 7 from the UV absorbances at 280 nm where both the label ( 280 -Alexa = 50 400 M -1 cm -1 ) and the protein absorb and at 590 nm where only the label ( 590 = 90 000 M -1 cm -1 ) 62 absorbs. Protein solutions were prepared in 10mM sodium phosphate buffer pH 7.4 with 0.15M NaCl in de-ionized water (MilliQ system, Millipore) and stored at 4°C.

Substrate cleaning and activation

Silicon wafers Si(100) (ACM, France) cut into square strips of 2 × 2 cm 2 or thin microscope glass slides (see below) were used as substrates for spin-coating deposition. The square was cut into four pieces of 1 cm 2 area for phospholipid reaction with the PMHS layer. To bond covalently the PMHS thin films to native oxide silica (thickness  2 nm), the silicon wafers were first cleaned and activated using the previously described procedure with "piranha" solution H 2 SO 4 /H 2 O 2 -30%w (70/30 vol); 90°C; 30 min. 53 Caution: piranha solution must be handled extremely carefully. For fluorescence adsorption measurements, the substrates were wafers or thin microscope glass slides (Menzel-Glazer, Germany) of 2.5 × 6 cm 2 submitted to the same treatment to bond PMHS. However, for protein adsorption to glass (without subsequent PMHS bonding), the substrate was previously treated with sulfochromic acid and rinsed carefully just before adsorption experiment.

PMHS films

PMHS thin films were prepared at 22  1 °C by sol-gel polymerization of DH and TH as crosslinker. DH/TH 95/5 (mol%) sol mixtures were deposited by spin-coating on freshly activated substrates according to the procedure 55,56 summarized as follows. Trifluoromethanesulfonic acid CF 3 SO 3 H (1.0 M in absolute ethanol) was used as catalyst (0.5 mmol/mol of monomers). The mixture of monomers (4.0 M in EtOH; molar ratio [EtOH]/[Si] = 1) was polymerized with hydrolysis ratio h = [H 2 O]/[SiOEt] = 0.5. The content of trifluoromethanesulfonic acid was not higher than 0.05% to control the kinetics of gelation of the liquid mixture. The resulting clear sols were allowed to age for 30 8 minutes with magnetic stirring before spin-coating deposition. The freshly cleaned silicon wafer was purged (2 min) in the spin-coater (Spin150, SPS Europe) under a stream of nitrogen (2 L/min) to avoid air moisture. For all samples, the speed of rotation was 4000 rpm (spin acceleration 2000 rpm/s) and the rotation time 30 s. The samples were finally cured at 110°C in an oven for 15 minutes. This procedure gave layers of reproducible homogeneity and thickness as verified by electron microscopy and infrared analysis.

Grafting PMHS with phospholipid to afford PL-PMHS

After spin-coating a ca. 1µm thick PMHS layer onto pieces of oxidized silicon wafer, the hydrosilylation reaction between the dilinoleoyl phospholipid and the PMHS SiH functional group was performed in air by casting solutions of phospholipid in the presence of Karstedt's catalyst. The reaction was then allowed to proceed in air at two different temperatures, 20°C and 40°C, before the sample was rinsed to remove any physisorbed material, and finally dried under a stream of nitrogen.

The phospholipid solutions contained 20 mg in 1 mL of toluene (25.5 mM), with an additional 2µL of the xylene solution of the platinum divinyltetramethyldisiloxane complex. To functionalize the PMHS film (thickness ca. 1 µm or less, area 1 cm 2 ), droplets of the phospholipid solution were deposited on PMHS by casting. Typically, four coalescing droplets of 5 µL were enough to cover the PMHS area. The procedure was repeated over 15 -30 min until a final molar ratio of phospholipid in excess of 1.5 over the SiH groups present on the PMHS film was achieved. After total evaporation of the toluene (ca. 15 min) at room temperature, the samples were kept for 15h (A) at 20°C or (B) placed in a thermostated box at 40°C. The samples were then rinsed three times in 5 mL of dry toluene. To remove any noncovalently bonded molecules in both procedures A and B the samples were immersed successively in different toluene/chloroform mixtures ranging from 100% to 0% (vol.) toluene with in steps of 20%.

The samples were dried under a stream of nitrogen for 5 minutes, then immersed in water for two hours and finally re-dried. Transmission infrared (IR) absorption spectra of the thin films before and after 9 hydrosilylation were used to ascertain the reaction yield after solvent and water rinsing. The water drop or air captive bubble contact angle in water was finally measured in order to characterize the sample surface hydrophilicity.

Synthesis of monoethoxysilane bearing Alexa. Grafting on PL-PMHS

To a solution of Alexa Fluor® 594 succinimidyl ester (12.2 nmol) in dry ethanol (100 µL) under an argon atmosphere, was added 3-(ethoxydimethylsilyl)-propyl amine (12.2 nmol). The reaction mixture was vigorously stirred for two hours at room temperature. The resulted mixture was then divided into ten parts. The solvent was evaporated under reduced pressure and the product alexamonoethoxysilane thus obtained was used without further purification. HRMS (Q-Tof) : Calcd for

PL-PMHS passivation with hexamethyldisilazane (HMDS):

The substrate with a PL-PMHS layer was dried under a stream of argon and treated with a solution of 95-5 % (vol.) of dry toluene-HMDS for 30 min at room temperature. After rinsing with toluene, and drying under a stream of argon, the substrate was soaked in alexa-monoethoxysilane solution as described above.

X-ray photoelectron spectroscopy (XPS)

The surface elemental composition of the PMHS and PL-PMHS surfaces were analysed by XPS. The spectra were obtained by means of a spectrophotometer (ESCALAB 250, Thermo Electron, UK) equipped with a monochromatic Al Kα (1486.6 eV) radiation source. The acceleration tension and power of the X-ray source were 15 kV and 100 W, respectively. The samples were analysed in the 10 -9 mbar range of pressure. The photoelectrons were analyzed at normal incidence of the sample surface.

The spot size was approximately 400m 2 . The composition corresponds to depths of 5-10 nm. Survey scans (0-1350 eV) at low resolution were performed to identify the constitutive elements. High resolution C 1s , Si 2p , O 1s , N 1s and P 2p spectra were recorded to obtain more detailed information on the nature of the surface. The peaks were fitted with Gauss-Lorentz curves. They provided the various surface atomic ratios which were calculated from the ratio of the corresponding peak areas, assuming the total area corresponded to 100%, after correction with the theoretical sensitivity factors reported by Scofield. 63 The spectra of both pristine PMHS and PL-PMHS were calibrated using the hydrocarbon contaminant or alkane C 1s peak at 284.8 eV. In both cases, the peak of Si-CH 3 was found at a binding energy (BE) of 284.0 eV in agreement with PDMS polymer at 284.4 eV according to Beamson and Briggs. [START_REF] Beamson | High resolution XPS of organic polymers[END_REF]

Captive air bubble contact angle measurements in water

Air captive bubble contact angles in water were measured (GBX -Digidrop, Romans, France) by applying an air bubble of about 25 µL to the surface. Contact angles with water were measured by applying a water droplet of 7 µL to the surface. The contact angle was calculated using computerized image analysis.

Adsorption: Determination of interfacial concentration 11

The experiments were performed at T = 19°C in a slit flow cell of thickness 63 or 105 µm and flow rate corresponding to wall shear rate 1000 s -1 . Confocal measurements were performed at 3 cm from the slit entrance. Details were provided in a previous work. [START_REF] Balme | [END_REF] The entrance design was modified to provide a sharper transition between the flows of buffer and solution. The interfacial concentration was evaluated as follows: the fluorescence signal F sol from the solution at concentration C is relative to an effective volume V while the signal F surf at the surface concerns the interfacial concentration  over area A. F surf   A and F sol  C V therefore  = (V/A) (F surf / F sol ) C. In a previous paper 66 the order of magnitude of V/A was estimated from the focus radius for A and 1 µm 3 taken as the confocal volume V. We propose below the experimental determination of V/A according to the following argument. We consider the interfacial signal F i (y) obtained under the confocal mode by scanning normal to a fluorescent interface positioned at y = 0 in non fluorescent solution (Fig. 2). F i (y) is maximal at y = 0; F surf = F i (0) When focusing at position y ≠ 0, the emission signal which originates from fluorescent molecules at position y = 0 is smaller by some factor given by the normalized curve to its maximum f i (y) 12 = F i (y) / F i (0). Assuming random orientation of the fluorophores, whatever the beam polarization and surface concentration, the signal is proportional to the number of molecules on the emitting area A where the concentration is mass or mol per unit area). F surf   A. Let us consider now focusing with the same beam into a solution of uniform concentration C b (mass or mol per unit volume). F sol  C b V.

In that situation the emission signal when focusing at some distance y 0 originates from the same area A excited at position y 0 and from other molecules in the neighborhood of y 0 . The contribution to the signal at y 0 from a plane of thickness dy situated at distance y is dF sol  A dy C(y 0 + y) f i (y). The observed signal is the sum of those elementary contributions. Assuming the concentration to be constant and the space infinite, we have:

() sol b i F AC f y dy     (1)
The integral is the area under the curve f i (y) and has the dimension of length. Let us call it w D , subscript D reminding that its determination comes from the convolution of the laser beam with a fluorescent surface described as a Dirac function. Then the ratio V / A is the integral of the interfacial signal normalized to its maximum.  = w D (F surf / F sol ) C. The product w D F surf is anyway the area under the curve F i (y). The parameter w D was determined from the signal of the interface after replacing the solution by buffer, since adsorption was either irreversible or very slow desorption occurred. Several functions can be used to fit the data. We found that a linear combination of Lorentzian and Gaussian functions provided a satisfactory fit. Three examples are given in Fig. 3. The width w D was reproducible over one experiment and the variations were small from one experiment to another (relative variation of about 10%). The convolution of the solution profile (step function at both interfaces) with the beam shape leads to a sigmoid at the interfaces with half the bulk solution signal at the interface 66 . We used then as surface signal F surf the raw signal minus half the solution signal. This correction was negligible when a strong adsorption occurred at small solution concentrations.

AFM and SEM

Atomic Force Microscopy (AFM) experiments were performed using a Dimension 3100 microscope equipped with a Nanoscope IIIa controller system (Digital Instruments, Veeco Metrology Group). AFM images were obtained by scanning in tapping mode in water or under air ambient conditions using silicon SPM probes (stiffness k  2 N/m, resonance frequency of 67 kHz, pointeprobeplus, Nanosensors). The root mean square average roughness (R q ) was analyzed by the Nanoscope software (version 5.31r1). Scanning electron microscopy (SEM) pictures were obtained with a Hitachi S4800 instrument. The MeX software (version 5.1) was used for the construction of the 3D SEM image and zprofile (±10 nm) from differently tilted SEM images.

Results and Discussion

14

A previously-reported novel reactive polymethylhydrosiloxane polymer crosslinked by the sol-gel reaction of hydrogenosilane precursors was prepared allowing subsequent functionalization by hydrosilylation of the SiH groups 55,56 . The hydrosilylation reaction between the internal double bonds of the phospholipid molecule and the PMHS SiH functional group occurred in air under very mild conditions at only 20°C or 40°C in the presence of the platinum catalyst.

Chemical analysis of the Interfaces

The XPS composition of the pristine PMHS surface showed good agreement with the theoretical elemental composition (hydrogen excluded) of the bulk PMHS-network (SiCO 2/2 ) 0.95 (SiO 3/2 ) 0.05 .

However the ratio C/Si (0.80) was lower than the theoretical value (0.95). The content of methylhydrogenosiloxane difunctional subunits SiHCH 3 O 2/2 was then lower than expected probably due to partial evaporation of DH oligomers. 53 After hydrosilylation of PMHS with PL, the infrared sharp absorption C=C peak at 3009 cm -1 of the cis-double bond in the starting PL spectrum totally disappeared in the final PL-PMHS film. This suggested complete reaction has occurred of the unsaturated carboncarbon bonds of phospholipids. Nitrogen (N 1s ) and phosphorus (P 2p ) peaks, attributed to the ammonium N + (CH 3 ) and phosphate PO 4 -groups of the phosphorylcholine subunit 31,32,33 appeared at 402.7 and 133.5 eV, respectively. The O content was higher than expected because the SiH group in PMHS matrix underwent reaction with water (present from air moisture) catalyzed by Karstedt's catalyst. 56 However, it was not easy by XPS to differentiate the SiOH and SiOSi groups. The elemental surface composition can be thus calculated with the following structure without hydrogen and neglecting the TH crosslinker: To summarize, all SiH groups have reacted. The reaction of PL with silane was not complete due to the bulkiness of the phospholipid chains, on the one hand, and competitive reaction with water from air moisture, catalyzed by Karstedt's catalyst, on the other hand. In the 5-10 nm upper layer the SiH reaction yield with double bonds (ca 45%) was higher than in the bulk (mean value ca. 15% as obtained from transmission infrared absorption), showing the preferential reaction of PL at the top of the PMHS layer.

Physical characterization of PMHS and PL-PMHS films

The final PL-PMHS film was characterized by AFM and SEM microscopy (Figs. 5,6). The pristine PMHS was very flat with low AFM roughness of 0.4 nm typical of sol-gel PMHS thin-film preparation. 53 After hydrosilylation, the major change of the surface topography by comparison with the virgin PMHS was the formation of grooves ca.100 nm deep which represented less than 10% of the total film thickness. Both reactions of the surface SiH functional groups in pristine PMHS with water and the 16 double bonds of the phospholipids PL increased the degree of crosslinking of the polymer chain in the PMHS network. The increasing crosslinking of the material may influence the thickness and surface roughness of the film as a consequence of the ensuing constraint. From cross sectional SEM images of the film, we observed, however, that the top of the PL-PMHS material was relatively flat showing that there were no grooves descending to the silicon substrate and no delamination of the film. Surface analysis by SEM showed a skin-like topography with the same peculiarities as in the AFM pictures over some larger areas and without defects. This result confirmed the good coverage of the PL-PMHS layer on the silicon substrate and the presence of superficial grooves. The surface morphological images under dry and aqueous conditions were studied using AFM (not shown). Some influence of water was detected as the depth of the grooves increased by about 20%.

Fig. 5 shows the cross-sectional SEM images of PMHS and PL-PMHS. The thickness after reaction was 170% higher than before grafting. The swelling can be attributed to the reaction with water and phospholipids. Swelling has also been observed by ellipsometry for n-alkene grafting reactions in PMHS siloxane networks. 55 The water-wettability of the PL-PMHS surface was considerably greater than that of the untreated PMHS surface (Fig. 5). We preferred to examine hydrophilicity by the captive air bubble method as the material changed its interfacial character in response to the type of environment, air or aqueous medium.

Indeed, the phosphorylcholine head at the surface can reorient slowly in a few hours as shown by the contact angle of a sessile drop of water which decreased from about 75° after droplet deposition to less than 5° after 1h under RH 80% humidity before evaporation of the droplet (not shown). This change was drastic with respect to PMHS characterized by an angle of 106°. By dipping the sample in water the captive air bubble angle increased with time from 130-150° after a few minutes, to 180° after several hours. At equilibrium (typically 15h), at room temperature, the air bubble could not adhere to the surface with contact angles of ca. 180°. We could explain this behaviour by the embedding of the hydrophilic phosphorylcholine head under the surface when the material was kept in contact with air while the reverse process occurred in the presence of water. 67,68 In this case the phosphorylcholine heads migrated 17

to the uppermost surface. The water could also be trapped in the specific microstructured grooves leading to a superhydrophilic effect.

Adsorption of proteins

We examined the behavior of different proteins: avidin, bovine serum albumin (BSA), bovine fibrinogen, lysozyme and -chymotrypsin. Given their isoelectric point, at physiological pH 7.4 BSA (67 000 g mol -1 , pI 5.6) is negative as fibrinogen (340 000 g mol -1 , pI 5.5), -chymotrypsin (25 300 g mol -1 , pI 8.1) is slightly positive, avidin (66 000g mol -1 , pI 10) and lysozyme (14 300, pI 11) are strongly positive. Avidin is a model of a very stable hard protein. Conversely BSA, like fibrinogen, can be viewed as a model of a soft protein, able to be adsorbed and denatured on many materials whatever their charge. In addition, avidin is positive at neutral pH, thereby providing an electrostatic attractive component of interaction with negative substrates such as oxidized silicon wafers and glass. In the neutral pH range, avidin is largely positive, as its isoelectric point is 10.4, and was expected to have an electrostatic attraction component with the negative hydrophilic glass, despite the quite high ionic strength. Indeed, we observed such adsorption. In the presence of the PMHS layer, adsorption still occurred but was significantly reduced. Finally, the treatment of PMHS with 1,2dilinoleoyl-sn-glycero-3-phosphorylcholine (18:2 Cis) reduced still further the interfacial concentration of avidin. However, as we could expect some conformational changes in the PL-PMHS layer depending on the fluid at the interface, air or aqueous medium, the adsorption kinetics of avidin were studied after keeping the cell in buffer for different times: 0; 3 and 15 hours. Some tiny adsorption was still detectable after 3 hours but no adsorption at all after 15 hours (Fig. 10). The decreasing adsorption level observed after the successive treatments may be linked to the expected decreasing density of negative charges.

The final totally repellent character of PL-PMHS was interpreted as resulting from the highly hydrated layer generated by the phosphorylcholine groups.

The initial kinetics were analyzed to estimate the adsorption constants. On hydrophilic glass, a twostep process can be proposed with an initial fast adsorption of constant k  10 -4 cm s -1 of the same order of magnitude as the transport-controlled Lévêque model constant k Lev = 0.54 (D 2 /x) 1/3 = 2.9 × 10 -4 cm s - 1 with D  7 × 10 -7 cm 2 s -1 ,  = 1000 s -1 and x = 3 cm. The chemical constant k a was therefore of the same order of magnitude. Applying previously published accurate approximations 69,70 The transport contribution was thus small and the k values were very close to the constant relative to the chemical control of the process: k a = 1.2 × 10 -5 cm/s and 2.4 × 10 -6 cm/s for PMHS and PL-PMHS interfaces, respectively. The low adsorption level on PMHS seems not to be related to the hydrophobic character of the material. This behavior might be connected to the hard nature of avidin which prevents the protein to be denatured and expose its hydrophobic core to the PMHS surface. 

21

The protein-repellent character of the PL-PMHS surface previously immersed overnight in water was also checked in the configuration of flowing solutions of -chymotrypsin, lysozyme, BSA and fibrinogen (Fig. 8). Lysozyme is a hard protein positively charged like avidin at neutral pH. Conversely the negative BSA can be viewed as a model of soft protein, able to be adsorbed and denatured on many materials whatever their charge, thus a good candidate to check the possible hydrophobic interactions with surfaces. Indeed, this protein is often used in blocking buffers to prevent subsequent non specific adsorption 2 . BSA at 10, 50 and 100 µg/mL exhibited a final adsorption of 0.05, 0.2 and 0.3 ng cm -2 respectively, after relative significant desorption at the highest solution concentrations from about 1 and 2 ng cm -2 . Let us mention that there was a slight displacement in the plane of substrate between the normal scannings to avoid repetitive expositions to the laser beam which could induce a photobleaching effect. This procedure constituted then also an examination of the interface homogeneity. The repellent character of the PL-PMHS interface with respect to bovine serum albumin suggested that the phospholipid fatty chains were not able to protrude towards the protein for hydrophobic interactions.

The other proteins exhibited also low adsorption (± SD). -chymotrypsin: 0.15 ± 0.05; 0.50 ± 0.16; 0.73 ± 0.14 ng cm -2 ; Lyosozme: 0.08 ± 0.07; 0.3 ± 0.3; 0.46 ± 0.11 ng cm -2 ; Fibrinogen: 0.5 ± 0.3; 0.3 ± 0.1; 7 ± 2 ng cm -2 , from solutions at 10, 50 and 100 µg/mL respectively. The relatively high adsorption from the fibrinogen solution at 100 µg/mL might correspond to a domain with some surface defect. 

Further functionalization

Infrared and XPS analysis after PMHS hydrosilylation with PL indicated the side reaction with water giving silanol groups, which may also evolve to siloxane crosslinks. In that case, such interfacial groups could be available for subsequent reaction. The presence of interfacial SiOH groups was checked by reaction of a monoethoxy silane coupling agent bearing alexa as fluorescent probe (Scheme 1). We water plays a major role in the formation of interfacial silanol on the PL-PMHS surface. After coupling the alexa probe, the silanol concentration can be thus estimated by assuming that the coupling reaction is total. According to the method developed above for determination of interfacial concentration, which 24 may be an alternative to the removal of the fluorescent probe from surface to solution for analysis, 71 the mean degree of functionalization of the PL-PMHS layer was found to be 3.0× 10 -2 nm -2 . Assuming that all molecules were grafted at the interface the mean distance between the sites was 5.7 nm. This order of magnitude is acceptable for a quite dense packing of bigger molecules on a neutral background and can be probably modulated by experimental conditions. The interfacial crosslinking density might also be decreased by using phospholipids with fewer unsaturated carbon-carbon bonds which would lead to interfaces of different softness. However a better control of the side reaction with water would be needed.

Conclusion

Polymethylhydrosiloxane anchored on an oxidized silicon wafer or activated glass could be functionalized with phosphorylcholine heads by means of 1,2-dilinoleoyl-sn-glycero-3phosphorylcholine (18:2 Cis). The functionality of the surface was checked by infrared absorbance and the correlated wettability change measured via contact angle measurements, with water drop or captive air bubble. Infrared absorption analysis demonstrated that all four double bonds of the phospholipids reacted with silane groups. XPS analysis showed a higher PL functionality at the interface than in the bulk. Side reaction with water provided the formation of silanol groups inducing probable swelling of the film and further possibilities of functionalization at the interface. The latter point was illustrated by grafting a fluorescent monoethoxy silane. Extension to the creation of amino functionalized interfaces should present no specific difficulties. The new interface was observed to be repellent towards avidin, bovine serum albumin, fibrinogen, lysozyme and -chymotrypsin adsorption at neutral pH in phosphate saline buffer. Therefore, this work opens the way to the constitution of stable protein repellent interfaces which could be useful in several fields such as biomaterials, diagnostic kits, microfluidics and cell cultures. Compared to phospholipid polymerization 26 at 70°C, the present method avoided the tedious 25 preliminary preparation of the specific phospholipid with the needed polymerizable group in the fatty chains. In addition, in the present work, the reaction still occurred at room temperature and the final layer was anchored at the surface with a very hydrophilic character measured by captive air bubble contact angle. Such preliminary chemistry was also required for monolayer anchoring of phospholipids on surfaces 27 . With respect to those works and others 40 involving monolayers at interfaces, the present method was much simpler and could be extended easily to other phospholipids. Moreover, the initial PMHS layer provided a much higher density of reaction sites compared to other similar materials 54 thus providing its very hydrophilic character.

Given the different possibilities of varying the preparation conditions and in view of the perspectives, possible control of the structure, density and depth of the grooves, and softness of the interface could be achieved, both properties potentially useful in cell culture and tissue engineering. If, however, very flat surfaces are desired for AFM analysis, for instance, the regular network of 100 nm deep grooves should be avoided in principle.

Figure 1

 1 Figure 1 Structure of 1,2-dilinoleoyl-sn-glycero-3-phosphorylcholine (18:2 Cis).

C 35 H

 35 35 N 3 O 10 S 2 721.1745 (M --C 4 H 11 SiO); found: 721.1764. PL-PMHS functionalization: Each part of the divided alexa-monoethoxysilane (~ 1 nmol) was dissolved in a mixture of toluene/dry ethanol (700µL/300µL). The PL-PMHS coated surfaces were then soaked in the solution for one hour. The substrates were further rinsed with ethanol, dried under a stream of argon, then kept overnight in Milli-Q water in order to remove any trace of physically adsorbed alexa before characterisation by confocal microscopy.

Figure 2 (

 2 Figure 2 (top) Scheme of focused laser beam at some distance from an interface occupied by fluorescent

Figure 3

 3 Figure 3 Peak width w D at interface, determined from adsorbed avidin, as a function of time in the

[(C 44 NO 8 P) 1 / 4 (

 44814 SiCO 2/2 )] z [SiCO 3/2 ] 1-z where z is the fraction of SiH having reacted with the double bonds of PL; the complement 1-z having reacted with water to form SiOH and new Si-O-Si links. Experimental atomic percentages agree well with z  0.45. The presence of superficial SiOH was sustained by streaming potential measurements (Fig. 4) in the presence of 10 -3 M KCl. The negative  15 potential (-65 mV) cannot be explained by the phosphorylcholine head and the isoelectric point is clearly in the acidic domain of silica.

Figure 4 .

 4 Figure 4.  potential in the presence of 10 -3 M KCl as a function of pH for PMHS functionalized with

Figure 5

 5 Figure 5 Surface analysis of PMHS (left) and PL-PMHS (right). From top to bottom: AFM images (5 × 5 µm 2 ) by tapping mode in air with corresponding Z-profile (black line) -PMHS with 0.4 nm roughness

Figure 6

 6 Figure 6 (top) SEM images of PL-PMHS over 25 × 20 µm 2 showing the same peculiarities as the AFM

  Avidin and BSA have about the same molecular mass. The two smaller other proteins should present a strong (lysozyme) or weak (-chymotrypsin) electrostatic attractive component with a negative surface. 19 In Fig. 7 the adsorption kinetics of avidin from 10.5 µg / mL (150 nM) solutions in phosphate buffer 10 mM, 150 mM NaCl on the three surfaces, hydrophilic glass, 1µm thick PMHS coating, and a layer of PMHS functionalized with 1,2-dilinoleoyl-sn-glycero-3-phosphorylcholine (18:2 Cis) are depicted.

Figure 7 .

 7 Figure 7. (top) Adsorption kinetics of avidin (10.5 µg /mL) in phosphate buffer saline at pH 7.4 on (o)

  (k a = k (b 1 u + 1) (b 2 u + 1)/((u-1) (a 1 u-1)) where u = k/k Lev and numerical coefficients a 1 = 0.556, b 1 = -0.681, b 2 = -0.0484) led indeed to k a = 1.3 × 10 -4 cm s -1 . For the other interfaces, the constants were much smaller.

Figure 8

 8 Figure 8 Interfacial concentration of proteins on PL-PMHS interface in the presence of flowing PBS buffer after flowing solutions at wall shear rate 1000 s -1 . C b = 10; 50; 100 µg/mL (top to bottom). (a) -

Scheme 1

 1 Scheme 1 Grafting reaction (b) of Alexa to surface silanols via (a) previous formation of amide links

TOC Graphic

Acknowledgments This work was supported by FP7 European grant NMP-214538 (BISNES project) and French Carnot structure. We are grateful to M. Ramonda (LMCP, UM2) for the AFM pictures, to Didier Cot (IEM) for the SEM pictures. Special thanks to Anton-Paar company for giving access to the SurPass apparatus for  potential measurements and to M. Leman for assistance in its use. JMJ is grateful to PI-France for discussions about the components of the optical device.


Nathanaël Fijalkow

Pierre Ohlmann

Joël Ouaknine

Amaury Pouly

James Worrell

Complete Semialgebraic Invariant Synthesis for the Kannan-Lipton Orbit Problem

Keywords: Verification, algebraic computation, Skolem Problem, Orbit Problem, invariants

come   L'archive ouverte pluridisciplinaire

Introduction

The Orbit Problem was introduced by Kannan and Lipton in the seminal papers [START_REF] Kannan | The Orbit Problem is decidable[END_REF][START_REF] Kannan | Polynomial-time algorithm for the Orbit Problem[END_REF], and shown there to be decidable in polynomial time, answering in the process a decade-old open problem of Harrison on accessibility for linear sequential machines [START_REF] Harrison | Lectures on linear sequential machines[END_REF]. The Orbit Problem can be stated as follows:

Given a square matrix A ∈ Q d×d together with vectors x, y ∈ Q d , decide whether there exists a non-negative integer n such that A n x = y.

In other words, if one considers the discrete 'orbit' of the vector x under repeated applications of the linear transformation A, does the orbit ever hit the target y? Although it is not a priori obvious that this problem is even decidable, Kannan and Lipton showed that it can in fact be solved in polynomial time, by making use of spectral techniques as well as some sophisticated results from algebraic number theory.

In instances of non-reachability, an interesting and natural question is whether one can produce a suitable invariant as certificate, i.e., a set P ⊆ R d that is stable under A (in the sense that AP ⊆ P) and such that x ∈ P and y / ∈ P. The existence of such an invariant then immediately entails by induction that the orbit of x does indeed avoid y.

Invariants appear in a wide range of contexts, from gauge theory, dynamical systems, and control theory in physics, mathematics, and engineering to program verification, static analysis, abstract interpretation, and programming language semantics (among others) in computer science. Automated invariant synthesis is a topic of active current research, particularly in the fields of theorem proving and program verification; in the latter, for example, one might imagine that y corresponds to a faulty or undesirable program state, and an invariant P as described above amounts to a succinct 'safety' certificate (here the program or procedure in question corresponds to a simple while loop with linear updates). In the context of imperative programs there has been work on synthesizing affine and algebraic invariants [START_REF] Müller | A note on Karr's algorithm[END_REF][START_REF] Müller | Precise interprocedural analysis through linear algebra[END_REF][START_REF] Colón | Polynomial approximations of the relational semantics of imperative programs[END_REF], as well as polyhedral invariants [START_REF] Cousot | Automatic discovery of linear restraints among variables of a program[END_REF], but as far we know no work on the more general class of semialgebraic invariants.

The widespread use of invariants should not come as a surprise. In addition to their obvious advantage in constituting easily understandable safety certificates, their inductive nature makes them ideally suited to modular reasoning, often allowing one to analyse complex systems by breaking them down into simpler parts, each of which can then be handled in isolation. Invariants, viewed as safety certificates, also enable one to reason over large sets of program states rather than individual instances: in the context of the Orbit Problem, for example, an invariant P ⊆ R d such that x ∈ P and y / ∈ P doesn't merely certify that y is not reachable from x, but in fact guarantees that from any starting point x ∈ P, it is impossible to reach any of the points y / ∈ P. In general, when searching for invariants, one almost always fixes ahead of time a class of suitable potential candidates. Indeed, absent such a restriction, one would point out that the orbit O(x) = {A n x : n ≥ 0} is always by definition stable under A, and in instances of non-reachability will therefore always constitute a safety invariant. Such an invariant will however often not be of much use, as it will usually lack good algorithmic properties; for example, as observed in [START_REF] Kannan | Polynomial-time algorithm for the Orbit Problem[END_REF], in dimension d = 5 and higher, the question of whether the orbit O(x) reaches a given (d -1)-dimensional hyperplane corresponds precisely to the famous Skolem Problem (of whether an order-d linear recurrence sequence over the integers has a zero), whose decidability has been open for over 80 years [START_REF] Tao | Structure and Randomness[END_REF].

Thus let us assume that we are given a domain D ⊆ 2 R d of suitable potential invariants. At a minimum, one would require that the relevant stability and safety conditions (i.e., for any P ∈ D, whether AP ⊆ P, x ∈ P, and y / ∈ P) be algorithmically checkable (with reasonable complexity). The following natural questions then arise:

-Completeness: in instances of non-reachability, does a suitable invariant in D always exist? -Effectiveness: if not, can we algorithmically determine whether a suitable invariant in D exists, and when this is the case can we moreover synthesise such an invariant?

The completeness question can be further refined when considering topologically closed invariants for the Euclidian topology. Indeed, if y is in the topological closure of the orbit, then there cannot exist a closed invariant. The converse is a completeness property:

-Closure-Completeness: if the target vector is not in the topological closure of the orbit, does there exist a closed invariant in D?

Main results. The main results of this paper concern the synthesis of semialgebraic invariants for non-reachability instances of the Kannan-Lipton Orbit Problem, where the input is provided as a triple (A, x, y) with all entries rational, and can be summarised as follows:

-We show that whether a suitable semialgebraic invariant exists or not is decidable in polynomial space, and moreover in positive instances we show how to synthesise a suitable invariant of polynomial size. Further, checking whether a semialgebraic set is an invariant can be done in polynomial space. Both results hold for both semialgebraic and closed semialgebraic invariants.

-We provide a simple characterisation of instances of non-reachability for which there does not exist a suitable semialgebraic invariant, -We obtain that the class of closed semialgebraic invariants is closurecomplete, i.e., there exists a closed semialgebraic invariant if and only if the target vector is not in the topological closure of the orbit.

Since the existence of suitable semialgebraic invariants for the Orbit Problem does not coincide precisely with non-reachability, our proof necessarily departs substantially from that given by Kannan and Lipton in [START_REF] Kannan | The Orbit Problem is decidable[END_REF][START_REF] Kannan | Polynomial-time algorithm for the Orbit Problem[END_REF]. In particular, handling negative instances relies upon certain topological and geometrical insights into the structure of semialgebraic sets, and positive instances require the explicit construction of suitable semialgebraic invariants of polynomial size. We achieve this by making use of techniques from algebraic number theory such as Kronecker's Theorem on inhomogeneous simultaneous Diophantine approximation, and Masser's deep results on multiplicative relations among algebraic numbers.

The following three examples illustrate a range of phenomena that arise in searching for semialgebraic invariants.

Example 1 Consider the matrix

A = 1 5 4 -3 3 4 .
The matrix A defines a counterclockwise rotation around the origin by angle arctan(3/5), which is an irrational multiple of π. Thus the topological closure

O of the orbit O = {x, Ax, A 2 x, . . .} is a circle in R 2 . If y ∈ O then O itself is clearly a suitable semialgebraic invariant.
On other hand, it can be shown that if y ∈ O \ O then there does not exist a suitable semialgebraic invariant. (In passing, it is also not difficult to see that the only polygons P that are invariant under A are ∅, {(0, 0)}, and R 2 , see the remark following the examples.) More general orthogonal matrices can be handled along similar lines, but the analysis becomes substantially more involved. In general, the only cases in which y ∈ O but there is no semialgebraic invariant are when the matrix A is diagonalisable and all eigenvalues have modulus one, as in the case at hand.

Example 2 Consider the matrix

A = 4 25      4 -3 4 -3 3 4 3 4 0 0 4 -3 0 0 3 4     
The matrix A has spectral radius 4 5 and so A n x converges to 0 for any initial vector x ∈ Q 4 . Given a non-zero target y ∈ Q 4 that does not lie in the orbit x, Ax, A 2 x, . . ., a natural candidate for an invariant is an initial segment of the orbit, together with some neighbourhood N of the origin in R 4 that excludes y and is invariant under A. Note however that A is not contractive with respect to either the 1-norm or the 2-norm, so we cannot simply take N to be a ball of suitably small radius with respect to either of these norms. However, for ε > 0, the set

N ε = u ∈ R 4 : u 2 1 + u 2 2 ≤ ε 2 ∧ u 2 3 + u 2 4 ≤ 1 16 ε 2 is invariant under A.
Thus we obtain a semialgebraic invariant as the union of N ε , where ε is chosen sufficiently small such that y ∈ N ε , together with an (easily computable) initial segment of the orbit x, Ax, A 2 x, . . . comprising all points in the orbit that lie outside N ε .

Example 3 Consider the following scaled version of the matrix from the previous example:

A = 1 5      4 -3 4 -3 3 4 3 4 0 0 4 -3 0 0 3 4      .
Note that A is a non-diagonalisable matrix with spectral radius 1. Example 1 concerned an orthogonal matrix, while the matrix in Example 2 was (morally speaking, if not literally) length-decreasing. Here, by contrast, the idea is to identify a subset Q ⊆ R 4 that is invariant under A, together with a "length measure" f : Q → R that increases under application of A. Fixing a constant c > 0, such a set is

Q = u ∈ R 4 : u 2 1 + u 2 2 ≥ c ∧ u 1 u 3 + u 2 u 4 ≥ 0 with length measure f (u) = u 2 1 +u 2 2 .
A key property of Q is that for any vector x ∈ R 4 such that x 3 = 0 or x 4 = 0, the orbit x, Ax, A 2 x, . . . eventually enters Q. By choosing c suitably large, we can exclude y from Q. Thus we obtain an invariant as the union of Q and an appropriate finite initial segment of the orbit x, Ax, A 2 x, . . .. We would like to draw the reader's attention to the critical role played by the underlying domain D of potential invariants. In the examples above as well as the rest of this paper, we focus exclusively on the domain of semialgebraic sets. However one might naturally consider instead the domain of semilinear sets, i.e., sets defined by Boolean combinations of linear inequalities with integer coefficients, or equivalently consisting of finite unions of (bounded or unbounded) rational polytopes. As pointed out above, in Example 1 no nontrivial instance admits a semilinear invariant, whereas one can show that in Example 2 semilinear invariants can always be found. Interestingly, determining in general whether or not a suitable semilinear invariant exists in non-reachability instances is not known to be decidable, and appears to be a challenging problem.

Preliminaries

Semialgebraic sets

Identifying C d with R 2d , a set P is semialgebraic if it is the set of real solutions of some Boolean combination of polynomial inequalities with integer coefficients.

It is convenient in this paper to work over the field of (complex) algebraic numbers, denoted A. All standard algebraic operations, such as sums, products, root-finding of polynomials and computing Jordan normal forms of matrices with algebraic entries can be performed effectively; we refer the reader to [START_REF] Bochnak | Real Algebraic Geometry[END_REF] for more details on the matter.

A central result about semialgebraic sets is the Tarski-Seidenberg Theorem: if S ⊆ R n+1 is semialgebraic then the image π(S) under the projection π : R n+1 → R n , where π(x 1 , . . . , x n+1 ) = (x 1 , . . . , x n ), is also semialgebraic. Among the consequences of this result is the fact that the topological closure of a semialgebraic set (in either R n or C n ) is again semialgebraic.

Succinct semialgebraic sets

The standard representation of semialgebraic sets involves representing polynomials as an array of coefficients, or equivalently with exponents written in unary. By contrast, we will need to represent polynomials with few terms but large exponents, such as f (x) = x 2 100 . Therefore we cannot use the standard representation of semialgebraic set and maintain good complexity bounds. Furthermore, it will be important to allow for composition without an exponential blowup: for example f (x + y) = (x + y) 2 100 has 2 100 + 1 monomials over x and y. This rules out the usual sparse representation where polynomials are given by a list of coefficients. We introduce a succinct representation where polynomials are represented as terms generated by the following grammar:

p ::= x | v | p + p | p • p
where x denotes a variable and v ∈ A a (real) algebraic number. The size of such a term is the number of subterms (in other words we see a term as a DAG), noting that we use the standard representation of algebraic numbers (in particular, integers coefficients are written in binary). For example, f above has size approximately 100 since f can be defined by taking x and squaring it 100 times. Composing two such polynomials amounts to a substitution of variables and only increases the size linearly, so f (x + y) also has size roughly 100. We can also have a small representation for the real and imaginary parts of f (x + iy). As an example, consider r n the real part of (x + iy) 2 n and i n its imaginary part. Then r n+1 = r 2 n -i 2 n and i n+1 = 2r n i n . This yields a representation for r n+1 and i n+1 of size 6 plus the sizes of r n and i n , thus linear in n. More generally, the size of the representation of the real and imaginary parts of f (x + iy) is linear in the size of the representation of f . We extend this succinct representation to formulas by

ϕ ::= (p = 0) | (p > 0) | ϕ ∧ ϕ | ϕ ∨ ϕ
and we define the size of a formula in the usual way, with the size of atoms using the succinct representation above. The other comparisons , <, and = can be rewritten using = and > only with a linear blowup in size: for example (p = 0) ⇐⇒ (p < 0)∨(p > 0). Similarly, negation is not included because it can always be pushed down to the comparisons operators; this will be important for the following lemma.

A succinct representation for a semialgebraic set S ⊆ R n is a succinct formula ϕ such that S = {x ∈ R n : ϕ(x)}. The size of this representation is the size of ϕ.

The usual complexity results on semialgebraic sets and the existential theory of reals assume the standard encoding. It is therefore important to point out that we can translate our succinct encoding into a standard one by introducing existential quantifiers. This translation shows that some decision problems on succinct semialgebraic sets are decidable.

Lemma 1 Let S ⊆ R n be a semialgebraic set with succinct representation ϕ. Then there exists k ∈ N and a formula φ, using the standard representation, such that

S = x ∈ R n : ∃y ∈ R k , φ(x, y)
and the size of (the standard representation of ) φ is polynomial in the size of (the succinct representation of ) ϕ. Furthermore, there is a PTIME algorithm to compute k and φ from ϕ.

Proof It is sufficient to show the result for ϕ ≡ (p = 0) or ϕ ≡ (p > 0). We introduce one variable for each subterm of p, and mimic the construction of p. For instance, if p = p 1 • p 2 , then we add y = y 1 • y 2 in the formula φ, where the variables y, y 1 , y 2 correspond to the terms p, p 1 , p 2 .

In particular, membership and semialgebraic set inclusion (with a twist), remain decidable in polynomial space:

Lemma 2 The following problems can be solved in polynomial space, where S is a semialgebraic set given by a succinct representation:

compute a succinct representation for S c , the complement of S, compute a succinct representation for AS where A is an invertible matrix, decide if x ∈ S, decide if AS ⊆ T where A is a matrix and S is a semialgebraic sets, compute a succinct representation for A k x where A is a matrix and k is given in binary.

In all problems, the coefficients of A and or/ x are algebraic numbers.

Proof The first item is clear: the complement of S is define by the negation of its succinct formula. By pushing the negation to the polynomials, we can obtain a new succinct formula with a linear blowup in size.

The second item is also clear: first compute B = A -1 , which has algebraic coefficients and can be computed in polynomial time. Write S = {x : ϕ(x)}, then AS = {x : ϕ(Bx)} = {x : ϕ (x)} where ϕ = ϕ[x ← Bx] is a substitution and thus only incurs a polynomial blowup in size.

The third item follows from Lemma 1: compute a formula φ such that S = {x : ∃y, φ(x, y)}. Then we have

x ∈ S ⇐⇒ ∃y.φ(x, y)
which is a first order formula in the existential theory of the reals, and is thus decidable in polynomial space. Note that it is crucial that the formula φ uses the standard representation.

The fourth item is a bit more involved since we cannot easily compute a succinct representation for AS in the case where A is not invertible. By the first item and Lemma 1, we can compute a formula ψ such that T c = {x : ∃y.ψ(x, y)}. By Lemma 1 we can compute a formula φ such that S = {x : ∃y, φ(x, y)}. But then

AS ⊆ T ⇐⇒ AS ∩ T c = ∅ ⇐⇒ {z : ∃x ∈ S.z = Ax} ∩ T c = ∅ ⇐⇒ {z : ∃x, y.φ(x, y) ∧ z = Ax} ∩ T c = ∅ ⇐⇒ {z : ∃x, y.φ(x, y) ∧ z = Ax ∧ ∃y.ψ(z, y)} = ∅ ⇐⇒ ¬∃z. (∃x, y.φ(x, y) ∧ z = Ax ∧ ∃y.ψ(z, y))
which is decidable in polynomial space by the existential theory of the reals.

To show the fifth item, one can compute a Jordan normal form P JP -1 for A in polynomial time, then observe that A k x = P J k P -1 x, thus it is enough to compute a succinct representation for the entries of J k . This is done blockwise, using the following formula for a Jordan block of size d:

     λ 1 . . . . . . λ 1 λ      =      λ k k 1 λ k-1 • • • k d λ k-1 λ k k 1 λ k-1 . . . λ k k 1 λ k-1 λ k      .
Indeed, λ k can be written succinctly by repeatedly squaring λ. Similarly, k i is an integer so it can obtained by repeatedly squaring 2 since it has polynomial size (in the size of k) when written in binary (since i is bounded by the dimension of the matrix).

The Orbit Problem

An instance of the Orbit Problem, or Orbit instance for short, is given by a square matrix A ∈ Q d×d and two vectors x, y ∈ Q d . The triple (A, x, y) is a reachability instance if there is n ∈ N such that A n x = y, and otherwise is a non-reachability instance. It was shown by Kannan and Lipton [KL80,[START_REF] Kannan | Polynomial-time algorithm for the Orbit Problem[END_REF] that the Orbit problem is decidable. We are interested in non-reachability certificates given as invariants. Formally, given an Orbit instance (A, x, y) in dimension d, a set P ⊆ C d is a (non-reachability) invariant if AP ⊆ P, x ∈ P, and y / ∈ P. For the remainder of this paper, we focus on semialgebraic invariants.

Representation of semialgebraic invariants

As it is the case in Examples 2 and Examples 3, many of the invariants we synthesise are comprised of an initial segment of the orbit x, Ax, . . . , A k-1 x together with a semialgebraic invariant Q for the instance (A, A k x, y). Since the smallest such k may be exponential and polynomials describing Q might involve large exponents we choose to represent such an invariant by the pair (k, ϕ) where k is written in binary and ϕ is a succinct formula. More precisely, (k, ϕ) represents the semialgebraic set x, Ax, . . . , A k-1 x ∪ {x : x satisfies ϕ} .

By abuse of notation, we will sometimes write (k, ϕ) to denote the above set. This representation is more succinct than a more classical representation given by a single boolean combination of polynomial inequalities using a standard representation. However, this does not affect complexity as stated in the following lemma.

We say that (k, Q) is an eventual invariant if y / ∈ x, Ax, . . . , A k-1 x and Q is an invariant for the instance (A, A k x, y). Or equivalently if

-A k x ∈ Q := {z : ϕ(z)}, -AQ ⊆ Q, -y / ∈ x, Ax, . . . , A k-1 x ∪ Q.
One checks that any eventual invariant is invariant but the converse is not true. Indeed, one can build an invariant (k, Q) such that AQ Q. However, if (k, Q) is invariant, then (0, x, . . . , A k x ∪Q) is trivially an eventual invariant, but its description can be exponential bigger, even using the succinct representation for semialgebraic sets.

Lemma 3 For the representation defined above, the following two problems can be decided in polynomial space:

-decide if (k, Q) is an eventual invariant, -assume (k, Q) is an eventual invariant, decide if z ∈ (k, Q),
Proof To check that (k, Q) is an eventual invariant, we need to check that:

-A k x ∈ Q: we cannot write down A k x since k could be exponential but thanks to Lemma 2 we can express A k x succinctly and check if

A k x ⊆ Q. -AQ ⊆ Q: this is an instance of Lemma 2.
y / ∈ P := x, Ax, . . . , A k-1 x ∪ Q: since A k x ∈ Q, it follows that the entire orbit of x is contained in P. Thus y / ∈ P if and only if y is not in the orbit of x and y / ∈ Q. The former is decidable in polynomial time [START_REF] Kannan | The Orbit Problem is decidable[END_REF] and the latter in polynomial space using Lemma 2. Now given (k, Q) an eventual invariant, and using the same remark as above,

checking if z ∈ (k, Q) is equivalent to checking if z is in the orbit of x and if z ∈ Q.
Note that these two complexity bounds match the complexity for the more classical representation. However, it is unclear if the same lemma holds for succinct invariants that are not eventual invariants. Indeed, checking that AQ ⊆ (k, Q) (as opposed to AQ ⊆ Q) appears nontrivial. A consequence of our main result is that whenever an invariant exists, a succinct eventual invariant of small size always exists.

Throughout this paper we assume that semialgebraic sets are given by the representation (k, Q), above, and the size of a semialgebraic set refers to the number of bits required for its representation.

Semialgebraic Invariants

Our main result is the following.

Theorem 1 There exist PSPACE algorithms for the following two problems: given an Orbit instance, does it admit a semialgebraic invariant? does it admit a closed semialgebraic invariant? Furthermore, both algorithms construct such an invariant when it exists, and the invariant produced has polynomial-size description, the invariants produced by the algorithms are always eventual invariants, there exists a closed semialgebraic invariant if and only if the target vector is not in the topological closure of the orbit.

Kannan and Lipton showed the decidability of reachability for Orbit instances over rational numbers; their proof carries over to instances with algebraic entries, however without the polynomial-time complexity.

The remainder of the paper is devoted to proving Theorem 1. To this end, let = (A, x, y) be a non-reachability Orbit instance in dimension d.

As a first step, recall that every matrix A can be written in the form A = Q -1 JQ, where Q is invertible and J is in Jordan normal form. The following lemma transfers semialgebraic invariants through the change-of-basis matrix Q.

Lemma 4 Let = (A, x, y) be an Orbit instance, and Q an invertible matrix in A d×d . Construct the Orbit instance Q = (QAQ -1 , Qx, Qy). Then P is a semialgebraic invariant for Q if and only if Q -1 P is a semialgebraic invariant for . Moreover, the size of Q -1 P is at most the sum of the size of Q and of P. Finally, if P is an eventual invariant then Q -1 P is also an eventual invariant.

Proof First of all, Q -1 P is semialgebraic if and only if P is semialgebraic and we can build a succinct representation of Q -1 P from that of P using Lemma 2 since Q -1 is invertible. We have:

-QAQ -1 P ⊆ P if and only if AQ -1 P ⊆ Q -1 P, -Qx ∈ P if and only if x ∈ Q -1 P, -Qy / ∈ P, if and only if y / ∈ Q -1 P.

This concludes the proof, the last point being clear. One easily checks that this transformation also preserves eventual invariants.

Thanks to Lemma 4, we can reduce the problem of the existence of semialgebraic invariants for Orbit instances to cases in which the matrix is in Jordan normal form, i.e., is a diagonal block matrix, where the blocks (called Jordan blocks) are of the form:

      λ 1 λ . . . . . . 1 λ      
Note that this transformation can be achieved in polynomial time [START_REF] Cai | Computing Jordan normal forms exactly for commuting matrices in polynomial time[END_REF][START_REF] Cai | The complexity of the A B C problem[END_REF]. Formally, a Jordan block is a matrix λI + N with λ ∈ A, I the identity matrix and N the matrix with 1's on the upper diagonal, and 0's everywhere else. The number λ is an eigenvalue of A. A Jordan block of dimension one is called diagonal, and A is diagonalisable if and only if all Jordan blocks are diagonal.

The d dimensions of the matrix A are indexed by pairs (J, k), where J ranges over the Jordan blocks and k ∈ {1, . . . , d(J)} where d(J) is the dimension of the Jordan block J. For instance, if the matrix A has two Jordan blocks, J 1 of dimension 1 and J 2 of dimension 2, then the three dimensions of A are (J 1 , 1) (corresponding to the Jordan block J 1 ) and (J 2 , 1), (J 2 , 2) (corresponding to the Jordan block J 2 ).

For a vector v and a subset S of {1, . . . , d}, we let v S denote the projected vector on C S . We extend it to matrices: for A ∈ C d × C d , we define A S ∈ C S × C S . The notation v J,>k is for the projection on the coordinates of the Jordan block J whose indices are greater than k. We let S c denote the complement of S in {1, . . . , d}.

There are a few degenerate cases that we handle now. We say that an Orbit instance = (A, x, y) in Jordan normal form is non-trivial if:

-There is no Jordan block associated with the value 0, or equivalently A is invertible; -For each Jordan block J, x J is not the zero vector; -For each non-diagonal Jordan block J, the vector x J has at least a non-zero coordinate other than the first one, i.e., x J,>1 is not the zero vector.

Lemma 5 The existence of (closed) semialgebraic eventual invariants for Orbit instances reduces in polynomial time to the same problem for non-trivial Orbit instances in Jordan normal form.

Proof Let = (A, x, y) be an Orbit instance in Jordan normal form.

-If A is not invertible, we distinguish two cases.

-If for some Jordan block J associated with the eigenvalue 0 we have that y J = 0, then consider P = (k, Q) where z ∈ C d : z J = 0 is semialgebraic, which we claim is an eventual invariant. Indeed, the Jordan block J is nilpotent, so for any vector u and n ≥ d, we have that J n u = 0, so in particular (A n x) J = 0, i.e. A n x ∈ P. If z J = 0 then (Az) J = 0, i.e. AQ ⊆ Q. Moreover, since by assumption y is not reachable, it is not one of A n x for n < d, and y J = 0, so y / ∈ P. -Otherwise, let J be the dimensions corresponding to Jordan blocks associated with the eigenvalue 0, we have that y J = 0. Consider the Orbit instance J c = (A J c , (A d x) J c , y J c ). We claim that admits a semialgebraic eventual invariant if and only if J c does. Let P = (k, Q) be an eventual semialgebraic invariant for and construct Q = z ∈ C J c : (z, 0) ∈ Q ). We argue that P J c = (d, Q ) is an eventual invariant for J c . Indeed,

A J c Q ⊆ Q since AQ ⊆ Q and A(z, 0) = (A J c z, 0) for any z. Then A k J c (A d x) J c = (A k+d x) J c ∈ Q since A k ∈ Q, Q
is stable under A and (A k+d x) J = 0. Finally y J c / ∈ P J c because y J = 0, so y J c ∈ P J c would imply y ∈ P. Conversely, let P J c = (k, Q) be a semialgebraic invariant for J c , construct P = (k, Q ) where Q = (z, 0) ∈ C J c × C J : z ∈ Q . One easily checks that it is an eventual invariant for using a similar reasoning. We reduced the existence of semialgebraic invariants from to J c , with the additional property that the matrix is invertible.

-If A contains a Jordan block J such that x J = 0, we distinguish two cases.

-If for some Jordan block J we have x J = 0 and y J = 0, then P = (0, z ∈ C d : z J = 0 ) is a semialgebraic eventual invariant for . -Otherwise, let J be the dimensions corresponding to Jordan blocks for which x J = y J = 0. Consider the Orbit instance J c = (A J c , x J c , y J c ), we claim that admits an eventual invariant if and only if J c does.

Let P = (k, Q) be a semialgebraic eventual invariant for , construct

P J c = (k, Q ) where Q = z ∈ C J c : (z, 0) ∈ Q .
We easily see that P J c is a semialgebraic eventual invariant for J c . Conversely, let P J c = (k, Q) be a semialgebraic eventual invariant for

J c , construct P = (k, Q ) where Q = (z, 0) ∈ C J c × C J : z ∈ Q .
We easily see that P is a semialgebraic invariant for . We reduced the existence of semialgebraic eventual invariants from to J c , with the additional property that for each Jordan block J, x J = 0.

-If A contains a non-diagonal Jordan block J such that x J,>1 = 0, we distinguish two cases.

-If for some non-diagonal Jordan block J we have that x J,>1 = 0 and y J,>1 = 0, then P = (0, z ∈ C d : z J,>1 = 0 ) is a semialgebraic eventual invariant for . -Otherwise, let J be the dimensions corresponding to non-diagonal Jordan blocks for which x J,>1 = y J,>1 = 0. Let S = J c ∪ J (J, 1), i.e., the dimensions outside J plus the first dimension of each block in J.

Consider the Orbit instance S = (A S , x S , y S ), we claim that admits a semialgebraic eventual invariant if and only if S does. Let P = (k, Q) be a semialgebraic invariant for , construct P S = (k, Q ) where Q = z ∈ C S : (z, 0) ∈ P . We easily see that P S is a semialgebraic eventual invariant for S . Conversely, let P S = (k, Q) be a semialgebraic invariant for S , construct P = (k, Q ) where Q = (z, 0) ∈ C S × C S c : z ∈ P S . We easily see that P is a semialgebraic eventual invariant for . We reduced the existence of semialgebraic invariants from to S , with the additional property that for each non-diagonal Jordan block J, x J,>1 = 0.

This concludes the proof. Note that in all constructions closed invariants were constructed, hence the proof also yields a reduction for the existence of closed invariants.

A useful lemma

We give a number theoretic lemma which we will need on several occasions. It concerns eigenvalues of A of modulus different than 1 and is an easy consequence of a separation bound by Mignotte [START_REF] Mignotte | Some useful bounds[END_REF] asserting that for two roots α = β of a polynomial P ∈ Z[x], we have

|α -β| > √ 6 d (d+1)/2 H d-1 ,
where d and H are respectively the degree and height of the polynomial P . Proof (Sketch) Let p be the minimal polynomial of A, then p has degree at most d, the dimension, and height H exponential in the size of A. Let q be an integer polynomial such that the roots of q are the products of the roots of p. There are standards constructions using the resultant, one can build such a q in a way that only increases the degree and height by a polynomial factor. Since A is a real matrix, λ and λ are eigenvalues of A, thus roots of p, thus |λ| 2 = λ λ is a root of q. Without loss of generality, we can assume that 1 is a root of q, by considering r(x) = q(x)(x -1), which incurs only a polynomial blowup in the degree and height. Finally, 1 and |λ| 2 are roots of r, thus by the Mignotte bound, and since 1 = |λ| 2 , ||λ| 2 -1| > √ 6/M where M = e (e+1)/2 G d-1 where e is polynomial in d and G is polynomial in H and d. If |λ| > 1, we then have, using log(1 + x)

x x+1 , that (log(|λ| 2 )) -1 |λ| 2 |λ| 2 -1 (eG) 2 6e (e+1)/2 G d-1
which is exponential in G and e and thus exponential in the size of A at most.

Some eigenvalue has modulus greater than one

Lemma 7 Let = (J, x, y) be a non-reachability instance, where J is a Jordan block whose modulus is greater than 1 and x = 0, then there exists a closed semialgebraic eventual invariant for with size polynomial in the size of . This invariant can be computed in polynomial time.

Proof Some coordinate of (J n x) n∈N diverges to infinity, so eventually gets larger in modulus than the corresponding coordinate in y. This allows us to construct a semialgebraic invariant for by taking the first points and then all points having a large coordinate in the diverging dimension. This case is illustrated in Figure 1.

By assumption x = 0, let k such that x k = 0 and x >k = 0. For all n ∈ N, we have (J n x) k = λ n x k , so |(J n x) k | diverges to infinity. It follows that there

exists n 0 ∈ N such that |(J n0 x)| k > |y k |. Let P = (n 0 , Q) where Q = z ∈ C d : |z k | ≥ |(J n0 x) k | and z >k = 0 .
We argue that P is a semialgebraic eventual invariant for . The non-trivial point is that Q is stable under J. Note that (J n0 x) >k = 0, so

J n0 x ∈ Q. Let z ∈ C d such that |z k | ≥ |(J n0 x) k | and z >k = 0. Then (Jz) k = λz k and (Jz) >k = 0, so Jz ∈ Q. Clearly y /
∈ P, thus P is an invariant for . To finish the proof we argue that P indeed has polynomial size. Indeed one can choose

n 0 = log(|y k |)-log(|x k |) log(|λ|)
, and using Lemma 6, we see that n 0 is bounded by an exponential in the size of and we can use Lemma 2 to write (J n0 x) k succintly.

O x λx λ 2 x λ 3 x λ 4 x λ 5 x λ 6 x λ 7 x P y J,k
Fig. 1 Case |λ| > 1. This figure represents the complex plane, which is the projection on the coordinate k.

Some eigenvalue has modulus smaller than one

Lemma 8 Let = (J, x, y) be a non-reachability instance, where J is a Jordan block whose modulus is smaller than 1 and x = 0, then there exists a semialgebraic eventual invariant for . Further, if y = 0 then there exists a closed semialgebraic eventual invariant for . Moreover, these invariants have size polynomial in the size of and can be computed in polynomial time.

Proof If y = 0 then P = (0, z ∈ C d : z = 0 ) is clearly a semialgebraic eventual invariant, but it is not closed.

For the remainder of the proof we assume that y = 0 and construct a closed semialgebraic eventual invariant. The situation is similar to Lemma 7, except that the convergence is towards the origin. The construction of the semialgebraic invariant is much more subtle though, for the following reason: for k such that x k = 0 and x >k = 0, we may have that y k = 0, implying that ((J n x) k ) n∈N does not become smaller than y k . Working on another dimension entails giving up the following diagonal behaviour: (J n x) k = λ n x k , making it hard to find a stable set under J. To overcome this problem, the invariant we define depends upon all the coordinates of J.

We let d denote the dimension of J. We have that (J n x) n∈N converges to 0. It follows that there exists n 0 ∈ N such that for each dimension k of J, i.e., for k ∈ {1, . . . , d}, we have

|(J n0 x) k | ≤ (1 -|λ|) k • ||y|| ∞ . Let P = (n 0 , Q) where Q = z ∈ C d : ∀k ∈ {1, . . . , d} , |z k | ≤ (1 -|λ|) k • ||y|| ∞ .
We argue that P is a semialgebraic invariant for . Note that y / ∈ P since for k such that ||y|| ∞ = |y k |, this would imply ||y|| ∞ ≤ (1 -|λ|) k • ||y|| ∞ , which cannot be since k ≥ 1, y = 0 and |λ| < 1. We examine the stability of Q under J. Let z ∈ C d such that for each dimension k ∈ {1, . . . , d}, we have

|z k | ≤ (1 -|λ|) k • ||y|| ∞ . Let k < d, then |(Jz) k | = |λz k + z k+1 | ≤ |λ||z k | + |z k+1 | ≤ |λ|(1 -|λ|) k • ||y|| ∞ + (1 -|λ|) k+1 • ||y|| ∞ = (|λ| + (1 -|λ|))(1 -|λ|) k • ||y|| ∞ = (1 -|λ|) k • ||y|| ∞ .
The case k = d is similar but easier. It remains to see that P has a polynomial representation. We show that n 0 can be chosen exponential in the size of . We will consider the case where J is not diagonal, which is a bit harder and easily adapted to the diagonal case. Note that

|(J n x) k | = |λ n x k + nλ n-1 x k+1 + . . . + n d -k λ n-d+k x d | ≤ d|λ| n-d n d ||x|| ∞ .
It follows that n 0 can be chosen to be

log(||y|| ∞ ) -log(d) -log(||x|| ∞ ) log(|λ|) + d
which is exponential in the size of thanks to Lemma 6.

Some eigenvalue has modulus one and corresponds to a non-diagonal Jordan block

Lemma 9 Let = (J, x, y) be a non-reachability instance, where J is a nondiagonal Jordan block whose modulus is equal to 1 and x >1 = 0, then there exists a closed semialgebraic eventual invariant for of size polynomial in the size of . This invariant can be computed in polynomial time.

We illustrate the construction of the semialgebraic invariant in an example following the proof. (See also Example 3 from the Introduction.)

Proof Let k such that x k = 0 and x >k = 0, we have k ≥ 1 and

(J n x) k-1 = λ n x k-1 + nλ n-1 x k , so (|(J n x) k-1 |) n∈N diverges to infinity since |λ| = 1. It follows that there exists n 0 ∈ N such that |(J n0 x) k-1 | > |y k-1 |. Without loss of generality we assume n 0 ≥ -λx k-1 ,x k |x k | 2
. The notation u, v designates the scalar product of the complex numbers u and v viewed as vectors in R 2 , defined by Re (uv). This quantity will appear later; note that it only depends on x and J. Let P = (n 0 , Q) where

Q = z ∈ C d : |z k-1 | ≥ |(J n0 x) k-1 |,
and λz k-1 , z k ≥ 0, and z >k = 0 .

We argue that P is a semialgebraic eventual invariant for . It is a semialgebraic set: the condition λz k-1 , z k ≥ 0 is of the form P (z) ≥ 0 for a polynomial P with algebraic coefficients, where z is seen as a vector in R 2d . The part to be looked at closely is the stability of Q under J.

First, J n0 x ∈ Q. Indeed, using |λ| = 1 and the assumption on n 0 ,

λ(J n0 x) k-1 , (J n0 x) k = λ • λ n0 x k-1 + n 0 λ n0-1 x k , λ n0 x k = |λ n0 | 2 λx k-1 , x k + n 0 |λ n0 x k | 2 = λx k-1 , x k + n 0 |x k | 2 ≥ 0. Now, let z ∈ C d such that |z k-1 | ≥ |(J n0 x) k-1 |, λz k-1 , z k ≥ 0 and z >k = 0. We have (Jz) k-1 = λz k-1 + z k , (Jz) k = λz k and (Jz) >k = 0. It follows that |(Jz) k-1 | 2 = |λz k-1 + z k | 2 = |z k-1 | 2 + 2 λz k-1 , z k + |z k | 2 ≥ |z k-1 | 2 ≥ |(J n0 x) k-1 | 2 , and λ(Jz) k-1 , (Jz) k = λ(λz k-1 + z k ), λz k = |λ| 2 λz k-1 + z k , z k = λz k-1 , z k + |z k | 2 ≥ 0.
Hence Jz ∈ Q, and P is a semialgebraic eventual invariant for .

To conclude we show that P has size polynomial in the size of . Indeed, it is enough to have n 0

|y k-1 |-|x k-1 | |x k |
and we can use Lemma 2.

Example 4 Consider the following matrix:

A = e iθ 1 0 e iθ ,
where θ ∈ R is an angle such that θ π / ∈ Q. We start from the vector x = [1, 1] T . We have

A n x = e inθ + ne i(n-1)θ , e inθ , so the projection on the second coordinate is a dense subset of the unit circle, and the projection on the first coordinate describes a growing spiral (similar to that shown in Figure 1). A tentative invariant for excluding some vector y is the complement of a circle on the first coordinate, large enough not to include y. However, this set is not a priori invariant. Geometrically, the action of A on a vector [z 1 , z 2 ] is to rotate both z 1 and z 2 by an angle of θ, and to push the first coordinate in the direction of z 2 :

A [z 1 , z 2 ] = e iθ z 1 + z 2 , e iθ z 2 .

A natural way to restrict the above set to make it invariant is to ensure that z 2 pushes away from the origin, i.e., that the norm of (Az) 1 increases. This is achieved by requiring that e iθ z 1 , z 2 ≥ 0.

All eigenvalues have modulus one and the matrix is diagonalisable

This case is the most involved and is the only one in which it might hold that y is not reachable and yet no closed semialgebraic invariant exists. (Recall Example 1 from the Introduction.) Write O = {A n x : n ∈ N} for the orbit of x under A, and O for its topological closure. Using results from Diophantine approximation and algebraic number theory, we show that O is (effectively) semialgebraic. Furthermore, using topological properties of semialgebraic sets we show that any semialgebraic invariant must contain the closure of the orbit. It follows that there exists a semialgebraic invariant just in case y / ∈ O. We start with the following topological fact about semialgebraic sets.

Lemma 10 Let E, F ⊆ R n be two sets such that E = F and F is semialgebraic. Then E ∩ F = ∅.

Proof The proof uses the notion of the dimension of a semialgebraic set. The formal definition of dimension uses the cell-decomposition theorem (see, e.g., [START_REF] Petrus | Tame Topology and O-minimal Structures[END_REF]Chapter 4]). However to establish the lemma it suffices to note the following two properties of the dimension. First, for any semialgebraic set X ⊆ R n we have dim(X) = dim(X) [Dri98, Chapter 4, Theorem 1.8]. Secondly, if X ⊆ Y are semialgebraic subsets of R n that have the same dimension, then X has non-empty interior in Y [Dri98, Chapter 4, Corollary 1.9].

In the situation at hand, since dim(F ) = dim(F ) it follows that F has non-empty interior (with respect to the subspace topology) in F = E. But then E is dense in E while F has non-empty interior in E, and thus E and F meet.

Lemma 11 Let = (A, x, y) be an Orbit instance, where A = diag(λ 1 , . . . , λ d ) is a diagonal d × d matrix with entries λ 1 , . . . , λ d ∈ C all having modulus one. Then -The set O is a semialgebraic set that is computable from in polynomial space and has polynomial size using the succinct representation. -Any semialgebraic invariant for contains O.

Proof We start by proving the first item. Write T for the unit circle in C. Let

L A = v ∈ Z d : λ v1 1 • • • λ v d d = 1
be the set of all multiplicative relations holding among λ 1 , . . . , λ d . Notice that L A is an additive subgroup of Z d . Consider the set of diagonal d × d matrices

T A = diag(µ 1 , . . . , µ d ) : µ ∈ T d and ∀v ∈ L A , (µ v1 1 • • • µ v d d = 1)
whose diagonal entries satisfy the multiplicative relations in L A . Notice that T A forms a group under matrix multiplication that is also a closed subset of C d×d . Using Kronecker's Theorem on inhomogeneous simultaneous Diophantine approximation [START_REF] John | An introduction to Diophantine approximation[END_REF], it is shown in [OW14, Proposition 3.5] that

{A n : n ∈ N} is a dense subset of T A . This immediately gives O = {A n x : n ∈ N} = {M x : M ∈ T A } . (1)
We now show that O is semialgebraic. Observe that L A is finitely generated, being a subgroup of the free finitely generated abelian group Z d . Moreover, if B ⊆ L A is a basis of L A then we can write

T A = diag(µ 1 , . . . , µ d ) : µ ∈ T d and ∀v ∈ B, (µ v1 1 • • • µ v d d = 1) .
It follows that T A is a semialgebraic subset of C d×d and thus from (1) that O is a semialgebraic set.

From an upper bound on the length of B due to Masser [START_REF] Masser | Linear relations on algebraic groups[END_REF], it can be shown that one can compute a basis for L A of polynomial size, in polynomial space in the description of A (see [OW14, Corollary 3.3]) and thereby compute a description of T A as a semialgebraic set, also in polynomial space in the description of A. More precisely, the resulting basis B has at most d elements and each vector in it has polynomial size (when writing integers in binary). Using the succinct representation, we can thus write µ v1 1 • • • µ v d d using polynomial size only by repeated squaring. Doing so for each of the (at most d) vectors of the basis yields a polynomial size formula. Now we move to the second item in the statement of the lemma. Let P be a semialgebraic invariant for . Our goal is to show that O ⊆ P. To show this we can, without loss of generality, replace P by P ∩ O, since the latter is also a semialgebraic invariant. Moreover, since any invariant necessarily contains the orbit O, we may suppose that O ⊆ P ⊆ O, and hence P = O.

We now prove that O ⊆ P, that is, we pick an arbitrary element z ∈ O and show that z ∈ P. To this end, consider the orbit of z under the matrix

A -1 . Now A -1 = diag(λ -1 1 , . . . , λ -d d )
and we may define groups L A -1 and T A -1 analogously with L A and T A . In fact it is clear that L A and L A -1 coincide (i.e., λ 1 , . . . , λ d satisfy exactly the same multiplicative relations as λ -1 1 , . . . , λ -1 d ), and hence also T A = T A -1 .

2. Or some eigenvalue of A has modulus smaller than 1. 3. Or some eigenvalue of A has modulus 1 and a non-diagonal Jordan block. 4. Otherwise, all eigenvalues have modulus 1 and the matrix is diagonalisable, so thanks to Corollary 1 there exists a semialgebraic invariant if and only if the topological closure of the orbit O is such an invariant, which holds if and only if the closure does not contain y.

In the first three cases, let J be the corresponding Jordan block. Thanks to Lemma 12, we can see that (J, J n0 x J , y J ) is a non-reachability Orbit instance. Now thanks to either Lemma 7, Lemma 8, or Lemma 9, we obtain a semialgebraic invariant, which then easily induces a semialgebraic invariant for . In all cases, when an invariant exists we can compute an eventual invariant of polynomial size, and do so in polynomial space (and in fact polynomial time, except for the last case).

We now consider closed semialgebraic invariants. Lemma 7, Lemma 9, and Corollary 1 construct closed semialgebraic invariants, but Lemma 8 applies only if the Jordan block J whose eigenvalue is smaller than 1 satisfies y J = 0. Hence we have to change the case distinction above. The first three cases are identical, the last case becomes: for all Jordan blocks J, the associated eigenvalue is either of modulus 1 and the block is diagonalisable, of modulus smaller than 1 and y J = 0.

In the last case, we conclude thanks to the following lemma.

Lemma 13 Let = (A, x, y) be a non-trivial Orbit instance in Jordan normal form. Assume that for each Jordan block J, either the eigenvalue has modulus 1 and J is diagonalisable, or the eigenvalue has modulus smaller than 1 and y J = 0. Then there exists a closed semialgebraic invariant for if and only if y / ∈ O.

Proof Let U denote the dimensions corresponding to eigenvalues of modulus 1.

Observe that y is in the closure of the orbit of A under x if and only if y U is in the closure of the orbit of A U under x U , because the action of A U is to converge towards y U = 0 since the associated eigenvalues have modulus smaller than 1. Thanks to Corollary 1, this implies the claim.

Again, in all cases, when a closed invariant exists we can compute a closed eventual invariant of polynomial size, and do so in polynomial space.

Thus we obtain an effective characterisation of the class of Orbit instances for which there exists a semialgebraic invariant, and similarly for a closed semialgebraic invariant. Note that non-reachability Orbit instances for which there do not exist semialgebraic invariants are extremely sparse. In those cases in which there exists an invariant we have shown how to compute such an invariant of polynomial size in polynomial space. Moreover, we obtain the completeness of the class of closed semialgebraic invariants: there exists a closed semialgebraic invariant if and only if the target vector is not in the topological closure of the orbit.

Conclusions

This paper is a first step towards the study of invariants for discrete linear dynamical systems. At present, the question of the existence and of the algorithmic synthesis of suitable invariants for higher-dimensional versions of the Orbit Problem (i.e., when the 'target' y to be avoided consists of either a vector space, a polytope, or some other higher-dimensional object) is completely open. Given, as pointed out earlier, that reachability questions with high-dimensional targets appear themselves to be very difficult, one does not expect the corresponding invariant synthesis problems to be easy, yet this approach might prove a tractable alternative well worth exploring.

Our main result is a polynomial-space procedure for deciding existence and computing semialgebraic invariants in instances of the Orbit Problem. The only obstacle to obtaining a polynomial-time algorithm is the problem of computing a basis of the group of all multiplicative relations among a given collection of algebraic numbers α 1 , . . . , α d , which is not known to be solvable in polynomial time. Less ambitiously one can ask for a polynomial-time procedure to verify a putative relation α n1 1 . . . α n d d ?

= 1. Assuming that α 1 , . . . , α d are represented as elements of an explicitly given finite-dimensional algebra K over Q, Ge [START_REF] Ge | Testing equalities of multiplicative representations in polynomial time[END_REF] gave a polynomial-time algorithm for verifying multiplicative relations. In our setting, however, where α 1 , . . . , α d are roots of the characteristic polynomial of matrix A, the dimension of K may be exponential in d. Note that in order to obtain an invariant of polynomial size, we had to introduce a succinct representation and the notion of eventual invariant. This representation is succinct in two orthogonal ways: we need to encode a prefix of the orbit succinctly because it can be exponentially long, and we need succinct representation of the semialgebraic "eventual" part. succinctly encoding the prefix of the orbit seems necessary in virtually all cases, whereas succinctly encoding the semialgebraic part is necessary because encoding the relations among the eigenvalues can involve very high exponents.

Lemma 6

 6 Let λ be a nonzero eigenvalue of a rational matrix A. If |λ| = 1, then 1 | log(|λ|)| is bounded by an exponential in the size of A.

Acknowledgements We would like to thank the reviewers for their very detailed and helpful comments, in particular pointing out a flaw in the complexity analysis in the first version of the paper.

Nathanaël Fijalkow was supported by the Alan Turing Institute under EPSRC grant EP/N510129/1, Nathanaël Fijalkow, Pierre Ohlmann, and Amaury Pouly were supported by the CODYS project ANR-18-CE40-0007, Joël Ouaknine was supported by ERC grant AVS-ISS (648701) and by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) -Projektnummer 389792660 -TRR 248, and James Worrell was supported by EPSRC Fellowship EP/N008197/1.

Now we claim that the following chain of equalities holds:

= O = P .

Indeed, Equation ( 2) is an instance of (1), but with A -1 and z in place of A and x. Equation (3) follows from the fact that T A = T A -1 . To see Equation (4), observe from (1) that z has the form M 0 x for some

Then by Lemma 10 we have that A -n z lies in P for some n ∈ N. But since P is invariant under A we have z ∈ P.

Corollary 1 Let the Orbit instance be as described in Lemma 11. Then admits a semialgebraic eventual invariant if and only if y / ∈ O. Furthermore, when it exists, such an eventual can be computed in polynomial space and has size polynomial in the size of .

Proof If y /

∈ O, then O is a semialgebraic invariant for by the first item in Lemma 11 and thus (0, O) is an eventual invariant. Conversely, if there exists a semialgebraic invariant P for , then O ⊆ P by the second item in Lemma 11, implying that y / ∈ O.

Proof of Theorem 1

We now draw together the results of the previous sections to prove our main result, Theorem 1, giving an effective characterisation of the existence of semialgebraic invariants and a procedure to compute such an invariant when it exists. Let = (A, x, y) be a non-reachability Orbit instance. First we put A in Jordan normal form and simplify to obtain a non-trivial Orbit instance.

Lemma 12 Let = (A, x, y) be a non-trivial Orbit instance in Jordan normal form. Assume that there exists a Jordan block J such that either the eigenvalue has modulus different from 1, or J is a non-diagonal Jordan block. Then there exists n 0 at most exponential such that if A n x = y, then n < n 0 .

Proof Clear by looking at the modulus of A n x.

We first consider the case of (non necessarily closed) semialgebraic invariants, and divide into four cases.

1. Either some eigenvalue of A has modulus greater than 1.