H Sellemi

Sandrine Coste
email: sandrine.coste@univ-lemans.fr

M Barre
email: maud.barre@univ-lemans.fr

R Retoux

A Ben Ali

Philippe Lacorre
email: philippe.lacorre@univ-lemans.fr

Synthesis by the polyol process and ionic conductivity of nanostructurated La 2 Mo 2 O 9 powders

Keywords: Nanostructured materials, La 2 Mo 2 O 9, polyol process, ionic conductivity

La 2 Mo 2 O 9 nanostructured powders were synthesized by the polyol process. The effects of the nature of the polyol, the refluxing time, the hydrolysis ratio, the metal concentration and the addition of hydroxyde ions, on the purity and morphology of the powders are determined. Two main morphologies are observed, the particles being in the shape of platelets or spheres, with respectively diethylene glycol or ethylene glycol as solvent. A specific surface area of 24 m².g -1 was reached by varying the metal concentration. The conductivity measurements were recorded on pellets that present in some cases a closed porosity, the relative density reaching 95% without any milling step.

According to the synthesis parameters, the grain conductivity can be slightly increased, the total conductivity remaining only slightly lower than that of pellets made of powders synthesized by solid state reaction.

Introduction

Recently, La 2 Mo 2 O 9 -based oxide-ion conductors have attracted special attention as they present high ionic conductivity at low temperatures (400-800 °C) under a wide oxygen partial pressure ranging from 0.21 to 10 -15 atm [START_REF] Lacorre | Designing fast oxide-ion conductors based on La 2 Mo 2 O 9[END_REF][START_REF] Goutenoire | Crystal structure of La 2 Mo 2 O 9 , a new fast oxide-ion conductor[END_REF][START_REF] Georges | Structural and transport properties of the fast oxide-ion conductors La 2-x R x Mo 2 O 9 (R=Nd, Gd, Y)[END_REF][START_REF] Yang | Preparation and characterization of solid electrolytes La 2-x A x Mo 2-y W y O 9 (A=Sm, Bi)[END_REF][START_REF] Vega-Castillo | Thermodynamic stability, structural and electrical characterization of mixed ionic and electronic conductor La 2 Mo 2 O 8.96[END_REF]. Pure La 2 Mo 2 O 9 presents a phase transition from a monoclinic low temperature α-form to a cubic high temperature β-form at about 580 °C [START_REF] Lacorre | Designing fast oxide-ion conductors based on La 2 Mo 2 O 9[END_REF][START_REF] Goutenoire | Crystal structure of La 2 Mo 2 O 9 , a new fast oxide-ion conductor[END_REF]. At this temperature, the ionic conductivity of La 2 Mo 2 O 9 increases by two orders of magnitude and, above it becomes higher than that of yttria-stabilized zirconia (YSZ), which is the reference material among solid electrolytes for oxygen ion conductors. La 2 Mo 2 O 9 is usually prepared by a conventional solid state reaction method [START_REF] Lacorre | Designing fast oxide-ion conductors based on La 2 Mo 2 O 9[END_REF][START_REF] Goutenoire | Crystal structure of La 2 Mo 2 O 9 , a new fast oxide-ion conductor[END_REF][START_REF] Georges | Structural and transport properties of the fast oxide-ion conductors La 2-x R x Mo 2 O 9 (R=Nd, Gd, Y)[END_REF][START_REF] Yang | Preparation and characterization of solid electrolytes La 2-x A x Mo 2-y W y O 9 (A=Sm, Bi)[END_REF][START_REF] Vega-Castillo | Thermodynamic stability, structural and electrical characterization of mixed ionic and electronic conductor La 2 Mo 2 O 8.96[END_REF][START_REF] Goutenoire | Structural and transport characteristics of the LAMOX family of fast oxide-ion conductors, based on lanthanum molybdenum oxide La 2 Mo 2 O 9[END_REF], but this method does not allow to obtain directly dense ceramic samples, since a milling step is necessary before sintering. Indeed, even if this step leads to the decrease of the grain size and thus to a higher sinterability, it also leads to the apparition of impurities, especially when the milling balls/jar are made of zirconia [7,[START_REF] Georges | Oxide ion diffusion in optimised LAMOX materials[END_REF]. These impurities are located in the grain boundaries after sintering and increase their resistance, leading to a drop of the total conductivity of the material. Therefore, in order to obtain a good La 2 Mo 2 O 9 conductor, we should synthesize a pure sample with high density. Nanocrystalline powders allow a good densification (when non aggregated), lower sintering temperatures, better mechanical properties of the electrolytes, and generally improve the electrical properties [START_REF] Rao | New directions in solid state chemistry[END_REF]. Recently, we successfully synthesized nanocrystalline La 2 Mo 2 O 9 powders by the polyol process [START_REF] Sellemi | Synthesis of La 2 Mo 2 O 9 powders with nanodomains using polyol procedure[END_REF], that presents the advantage of inducing various microstructures [START_REF] Larcher | Some insights on the use of polyols-based metal alkoxides powders as precursors for tailored metal-oxides particles[END_REF][START_REF] Škapin | Synthesis and characterization of calcite and aragonite in polyol liquids: control over structure and morphology[END_REF][START_REF] Joseyphus | Low temperature synthesis of ITO nanoparticles using polyol process[END_REF] and lowering the temperature of the heat treatment (generally necessary as a final step when soft chemistry is used, in order to reduce the size of the particles obtained [START_REF] Flores-Gonzalez | Preparing nanometer scaled Tb-doped Y 2 O 3 luminescent powders by the polyol method[END_REF]).

The first aim of this work was to optimize the synthesis parameters in order to extend the control of the morphology. The following parameters were modified in order to determine their effect on the structure and microstructure of the final powders: the refluxing time, the nature of polyol, the hydrolysis ratio (h), defined by the nominal molar ratio water/total divalent and trivalent metal ions, the metal concentration and the effect of addition of hydroxide ions. The second part of this work was devoted to the measurement of ionic conductivities and the determination of the impact of the morphology, by way of the synthesis process, on them. This part also included, at first, a study of the sinterability of the powders.

Experimental

Synthesis

Precursor salts, lanthanum acetate, La(CH 3 CO 2 ) 3 .1.5 H 2 O (Alfa Aesar, 99,99%), and ammonium molybdate, (NH 4 ) 2 Mo 2 O 7 (Alfa Aesar, Mo 56.5%), in a molar ratio (Mo:La: = 1:1), and, for a part of this work an appropriate volume of distilled water, were added to 30 mL of a given polyol (table 1). The total lanthanum and molybdenum concentration ([La+Mo]) was 0.2 mol.L -1 , except for the part concerning the effect of the concentration in which the total concentration was varied from 0.05 to 0.5 mol.L -1 . The resulting mixture was then heated up to the boiling point of the polyol, under reflux and mechanical stirring, for durations ranging from 1 to 3 hours. In order to modify the pH and thus try to modify the morphology or the purity of the obtained powders, urea (Jeulin, 99%) was added to the reaction mixture just before heating, for some syntheses. After cooling, the asprepared precipitates were separated from the supernatant by alternating centrifugation, washing in ethanol and ultrasonication. Finally, the precipitates were heat treated by placing them directly, for 5 min, in a muffle furnace preheated at 600°C and then quenched at room temperature. The aim of such a rapid heat treatment was to avoid an important grain growth. It's worth noting that a slightly higher temperature (600°C instead of 550°C) was used for this work, compared to that in our previous publication [START_REF] Sellemi | Synthesis of La 2 Mo 2 O 9 powders with nanodomains using polyol procedure[END_REF], in order to facilitate the observation of an eventual impurity.

Characterization techniques

The phase purity of the obtained powders was checked by recording X-Ray powder Diffraction (XRD) patterns at room temperature on a PANalytical θ/θ Bragg-Brentano X'pert MPD PRO diffractometer (CuKα 1+2 radiations) equipped with the X'Celerator detector. The diagrams were collected at room temperature in the [10-60°] scattering angle range, with a 0.01671° step for a total acquisition time of 11 min for the presented diagrams, and for a total acquisition time of 1h for the measurement of the full width at half maximum (FWHM) in order to determine the grain size according to the Scherrer equation. For clarity, only selected ranges of these diagrams are presented.

The morphology of the powders was investigated with a Carl Zeiss Supra 55 (Oberkochen,

Germany) high resolution scanning electron microscope (SEM) equipped with EDS. The transmission electron microscopy (TEM) study was performed using a 200kV JEOL 2100 LaB 6 transmission electron microscope fitted with a double tilt sample holders. Specimens for TEM observations were prepared by crushing powdered samples in ethanol. After dispersion of the crystallites, a drop of the suspension is deposited and dried onto a carbon coated copper grid. The specific surface area measurements were realized according to the BET method with a Micromeritics Tristar II apparatus. The sinterability of the obtained powders was determined from pellets obtained by pressing the powders unidirectionally under 5000 bars with a 5 mm diameter die, the thickness obtained being of about 2-2.5mm. Nonisothermal sintering behavior of the green pellets was measured on a dilatometer (Model: Netzsch, DIL 402C) from room temperature to 950 °C at a heating rate of 10 °C/min, followed by a cooling down at the same rate.

The electric conductivity was measured by complex impedance spectroscopy on pellets sintered by placing the green pellets directly, for 30 min, in a preheated muffle furnace and then quenching them down to room temperature [START_REF] Barré | The NASICON solid solution Li 1-x La x/3 Zr 2 (PO 4 ) 3 : optimization of the sintering process and ionic conductivity measurements[END_REF]. Such a heat treatment was called "rapid" and used in order to keep as much as possible the nonostructuration of the grains. Two probe electrical conductivity measurements were carried out using a Solartron 1260 frequency response analyser connected to a Solartron 1296 dielectric interface over the 10MHz-0.01Hz range (ac voltage of 175 mV, 40 points/decade from 10MHz to 1Hz and few points under 1Hz). Complex impedance diagrams were recorded under dry air flow every 25 °C, after a thermal equilibration of 35 min and over the temperature range 302-700°C. Impedance diagrams plotted in the Nyquist complex plane were least squares fitted, using the Z-view 2.8d software, with one or a series combination of two R//CPE elements, assigned to the bulk and -when two elements are used-to the grain boundaries contributions [16].

Results and discussion

Control of the microstructure of the particles

Effect of the refluxing time

In order to determine the effect of the refluxing time, t, reflux was maintained for 1, 2 or 3 hours, the DEG being used as solvent. After heat treatment of the precipitate, pure La 2 Mo 2 O 9 was obtained with a reflux time of 3 hours. However, impurity (La 2 Mo 3 O 12 ) was observed, by XRD, for shorter reflux times (figure. 1). The shorter the reflux time was, the larger the amount of impurity.

Afterwards, the reflux time was thus fixed to 3 hours.

Figure 1: XRD diagrams of precipitates synthesized with DEG with a reflux time of 1, 2 or 3 hours and heat treated at 600°C for 5 min.

Effect of the nature of the polyol

As the nature of the polyol solvent can have a major influence on the particle morphology [START_REF] Larcher | Some insights on the use of polyols-based metal alkoxides powders as precursors for tailored metal-oxides particles[END_REF],

different polyols were used in order to determine their effects on the microstructure and grain size.

Pure La 2 Mo 2 O 9 powders were obtained with DEG whereas La 2 Mo 3 O 12 impurity is observed by XRD when EG, PEG and TEG were used as solvent (figure 2). It can be noted that the amount of La 2 Mo 3 O 12 impurity is higher with TEG. In order to avoid the formation of the impurity, urea was added to the initial solution (before reflux) in order to promote the precipitation of the lanthanum acetate, as hydroxide or oxide, since the 3 b). These results seem to confirm that the addition of urea, and thus the progressive production of hydroxide groups, enhanced the precipitation of the lanthanum acetate. On another hand, an important release of hydroxide groups seems to stabilize the ammonium molybdate and thus leads to a decrease of its precipitation, leading to the formation of an impurity poor in molybdenum, La 2 MoO 6 . In order to also obtain pure La 2 Mo 2 O 9 powders with PEG and TEG as solvent, the addition of urea was tested with a ratio u = 3 as it leads to pure powders with EG as solvent (table 2). With these 2 polyols, the powders obtained after heat treatment were also pure, as determined by XRD (figure 4).

Figure 4: XRD diagrams of precipitates synthesized with PEG (u = 3) or TEG (u = 3) and heat treated at 600°C for 5min.

It can be thus expected that, except in the case of the use of DEG as solvent which leads to pure powders with or without the addition of urea, it is necessary to provide hydroxide groups, through the decomposition of urea during heating of the starting solution, to enhance the precipitation of lanthanum acetate. However, the ratio of urea, u, has to be controlled since a too important value of u leads to a lack of the precipitation of the ammonium molybdate.

The microstructure of the pure La 2 Mo 2 O 9 powders obtained with the different polyols was investigated in order to determine if the nature of the polyol and, for DEG, if the addition of urea impact the morphology of the obtained powders.

The crystallite size was estimated, from XRD patterns, according to the Scherrer equation (the contribution of the apparatus on the FWHM being deducted). From the thinnest diffraction peak at about 2q =24.9° when we use DEG, the crystallite size is around 29, 43 and 35 nm for u = 1, u = 2 and u = 3 respectively. With EG and u = 3, the crystallite size is about 50 nm.

In order to determine the microstructure of the powders obtained and to estimate if the crystallite size determined by XRD corresponds to monocristallized grains or to particles composed of different crystalline domains, the powders have been observed by SEM (figure 5). After a rapid heat treatment of 5 min at 600°C, the powder synthesized with DEG is composed of platelets of few hundred nanometers long and around twenty nanometers thick. It can also be observed that the addition of urea has no effect on the morphology of samples synthesized in DEG (figure 5 A TEM micrograph of a sample prepared with EG (u = 3) and heat treated at 600°C for 5min, is given in figure 6. It shows that all the particles are roughly spherical, mostly agglomerated. We measured the specific surface area, according to the BET method, of the powders obtained with all polyols after rapid heat treatment at 600 °C for 5min, these compounds being pure according to XRD. The specific surface area depends on the morphology of the powders. For particles as platelets, the specific surface area is of 16 and 10 m 2 .g -1 respectively for powders synthesized with DEG (u = 0) or PEG (u = 3) as solvent, which is higher than the surface areas of spherical particles synthesized with EG or TEG as solvent with addition of urea (u = 3) (6 and 4 m 2 .g -1 respectively) (table 2). These low values result from the agglomeration of the formed particles, especially in the case of spherical ones. The platelets are formed of a plurality of crystallites, but this configuration, in the form of plates, keeps a much larger contact surface.

The contribution of the hydroxide ion seems to lead to a slight decrease in surface area. This slight decrease may be related to an organization of platelets as desert roses during the addition of urea.

For comparison, the specific surface areas presented by Kuang et al. [START_REF] Kuang | Synthesis, characterization and optical properties of ZnO nanoparticles with controlled size and morphology[END_REF] for La 2 Mo 2 O 9 powders obtained from citrates reaches 4.8 m².g -1 with a heat treatment at 650°C for 4h.

Effect of the hydrolysis ratio h

Here we studied the effect of the hydrolysis ratio h by adding an appropriate amount of distilled water in DEG (u = 0) or EG (u = 3) with a concentration of metal [La 3+ + Mo 6+ ] of 0.2 mol.L -1 . The hydrolysis ratio was varied between 2 and 50 (table 3). The duration of heating under reflux was 3h and the precipitates were heat treated for 5 min at 600 °C. When DEG is used as solvent, the formation of pure La 2 Mo 2 O 9 after a heat treatment at 600 °C for 5 min is observed only with h ≤ 2, the samples with higher values of h (h >2) containing the La 2 Mo 3 O 12 as impurity (figure 8). With EG, La 2 Mo 2 O 9 compound is pure after a heat treatment at 600 °C for 5 min with only h ≤ 10 (figure 9), according to XRD diagrams. The increase in hydrolysis rate leads, on the other hand, to an increase of crystallite size.

The addition of water seems to promote the precipitation of molybdenum and / or the stabilization of lanthanum acetate, an impurity rich in molybdenum (La 2 Mo 3 O 12 ) being formed. It is possible that the decrease in boiling point due to the presence of water can explain the formation of this impurity.

Indeed, we tried to promote germination at lower temperature by performing a first step at 150 °C for 3 h before increasing the temperature to the boiling point, but we observed the formation of the same impurity (La 2 Mo 3 O 12 ). The presence of water may also makes the environment less reducing as the supernatant is colorless after reflux and the precipitate white, whereas they are brown and beige respectively in all the other cases.

Figure 8: XRD diagrams of the precipitate synthesized with DEG and hydrolysis ratio h equal 0, 2, 10, 20 and 50 and heat treated at 600°C for 5min

Figure 9: XRD diagrams of the precipitate synthesized with EG and hydrolysis ratio h equal 0, 2, 10, 20 and 50 and heat treated at 600°C for 5min SEM observations show that the addition of water has no effect on the morphology with DEG (agglomerated platelets) and EG (agglomerated spherical particles) (figure 10). However, we can see that for values of h ≥ 2, the particles are more agglomerated. Such an increase in agglomeration was also observed previously, for the synthesis of ZnO, with an increase in the hydrolysis rate [START_REF] Dakhlaoui | Synthesis, characterization and optical properties of ZnO nanoparticles with controlled size and morphology[END_REF].

It could be due to an increase of hydrolysis and condensation kinetics which lead to more dense particles. The addition of water results in a decrease of the specific surface area, as with both EG (4 and 1 m 2 .g -1 for h equal 2 and 10 respectively) and DEG (8 m 2 .g -1 for h = 2). The decrease of the specific surface area with EG, despite a decrease in crystallite size, shows that the particles are agglomerated and made of several crystallites.

Effect of the concentration of metal

In the literature, the concentration of dissolved salts is used to control the particle size, the size of particles increasing with concentration [START_REF] Poul | Layered Hydroxide Metal Acetates (Metal = Zinc, Cobalt, and Nickel): Elaboration via Hydrolysis in Polyol Medium and Comparative Study[END_REF]. Therefore, we varied the metal concentration [La + Mo] from 0.05 to 0.5 mol L -1 (table 4). The different concentrations were tested with DEG (u=0)

and EG (u = 3), no water being added. The refluxing time was fixed to 3 hours. The precipitates were heat treated for 5 min at 600 °C. Particles synthesized with concentration of 0.05mol.L -1 have the smallest average size, as observed directly on XRD diagrams, but for other concentrations, larger average size remains constant. A synthesis with concentration of metal [La+Mo] of 0.025 mol. L -1 in DEG was carried out to see if it is possible to reduce the particle size. However, it was impossible to separate particles even by increasing speed centrifugation at 14,000 rpm -1 . This is probably due to the very fine particle size or even to a too low concentration, which is then below the critical concentration for nucleus formation or insufficient for their growth [START_REF] Brinker | Sol-Gel Science: The Physics and Chemistry of Sol-Gel Processing[END_REF]. When the concentration is lowered to [La + Mo] = 0.05 mol.L -1 , the crystallite sizes and the agglomerates formed are smaller. This suggests that the decrease in concentration [La + Mo] below a value of 0.1 mol.L -1 leads to a decrease in size of the particles formed, as well as their agglomeration.

We measured the specific surface area according to the BET method for all the powders heat treated at 600 °C for 5min (table 4). As expected, in the case of DEG, its evolution is inverse of that of the crystallite size. Indeed, platelets formed by crystallites with smaller sizes have the highest specific surface area. Thus, the surface area of the powder synthesized with a metal concentration [La + Mo] = 0.05 mol.L -1 is 24 m 2 .g -1 when the crystallite size is 21 nm. For higher [La + Mo] concentrations, the specific surface is lower (between 7 and 16 m 2 .g -1 ), with a crystallite size of about 40 nm. When EG is used as a solvent, the surface area remains substantially the same (between 3 and 6 m².g -1 ), although the crystallite size is significantly smaller than the others (30 nm instead of about 50 nm)

with a [La + Mo] concentration of 0.05 mol.L -1 . Lowering the [La + Mo] concentration to 0.05 mol.L -1 therefore allowed us to obtain, using DEG as solvent, the largest surface area using the conventional polyol method and heat treating the precipitate 5 min at 600 °C.

Conduction properties

In order to measure the ionic conductivity of our samples and thus estimate the impact of the microstructure, with optimal conditions, it was necessary to determine the sintering parameters that allow to increase the density (in order to decrease grain boundary contribution) while maintaining the grain size as small as possible. The determination of the sintering conditions of powders is thus described before presenting the conductivity properties.

Sinterability and pellets microstructure

In order to estimate the more suitable sintering conditions, we studied the sinterability of the powders. It was first investigated by dilatometry on pellets made of powders obtained by polyol process after a heat treatment at 600 °C for 5 min of the precipitates obtained with DEG (h and u = 0) and EG (h = 0, u = 3), these powders being constituted respectively of platelets and agglomerated spheres. Comparison was made with the sinterability of powder synthesized by conventional solid state reaction (SSR). The powders were compacted in the shape of pellets of 5 mm diameter, by uniaxial pressing under 5000 bar and then isostatic pressing also under 5000 bar. The linear shrinkage of these three samples, under air, from room temperature up to 950 °C with a speed of 5 °C.min -1 is presented in figure 14. Comparison of curves evidences a difference of behavior between the two powders synthesized by polyol process.

For the powder obtained with DEG as solvent, a significant linear shrinkage of about 13% is observed beyond 550 °C. This shrinkage is related to the removal of much of the porosity initially present in the pellets. Two mechanisms of shrinkage seem to proceed, as a slight change of the slope can be observed around 650 °C (figure 14). This could be due to a preferential welding of platelets stuck together, in the first step. For the powders obtained with EG, a significant linear shrinkage, of about 11%, proceeds above 620 °C. In this case, two very different regimes of sintering are observable, with an important lowering of the speed about 720 °C. This is probably due to a differential sintering. First, agglomerates, which consist in spherical particles, sinter. This leads to large grains with a large porosity between them. In the second step, the porosity interagglomerate decreases with time but far more slowly, leading to a lower densification.

Figure 14: Linear shrinkage as a function of temperature, with a heating and cooling rate of 5°C.min -1 , under air, of powders synthesized with DEG (u = 0) or EG (u = 3) and a heat treatment at 600 °C for 5 min, and by solid state reaction (SSR).

According to these results, short sintering times and sintering temperatures of 650 and 750 °C, for the pellets prepared with powders obtained with DEG or EG, respectively, were chosen.

Additionally, the pellets were directly placed in a muffle furnace preheated at the desired temperature and, after a heat treatment of 30 min, quenched at room temperature, such a sintering being qualified as rapid sintering in this paper. These conditions seem to be the more appropriate to avoid an important grain growth while obtaining a density as satisfactory as possible for ionic conductivity measurements. In order to favor the electric measurements by increasing the density, rapid heat treatments at 925°C were also done.

The microstructures of the pellets obtained with such rapid heat treatments are then presented.

-Pellets made of powders obtained with DEG (platelets).

Pellets made of the powders obtained with DEG were densified by a rapid sintering at 650 or 925 °C for 30 min, under air. The relative densities reached are of 79 and 95% respectively. A high relative density is thus obtained with these powders after a rapid sintering at 925 °C, the porosity being then closed. -Pellets made of powders obtained with EG (spheres).

Pellets made of powders obtained after heat treatment at 600 °C for 5 min of the precipitate synthesized with EG were densified by a quick sintering at 750 or 925 °C for 30 min, under air.

Their relative densities are of 78 and 82% respectively. The relative density increases with the sintering temperature, but is still substantially lower than the one reached with the powders prepared with DEG, with a sintering temperature of 925°C. This is in agreement with the dilatometric curves which highlight a lower sinterability of the powders obtained with EG.

SEM images of the pellets sintered at 750 or 925°C for 30 min and then fractured are presented in figure 16. The slight decrease of the relative porosity of pellets with increasing sintering temperature is evidenced. The porosity is highly connected after a sintering at 750 °C and still remains connected after a sintering at 925 °C, even if the grains are more weld together. The size of the grains, that are relatively spherical, remains slightly the same and is in the order of few hundred nanometers.

1µm 1µm

Figure 16: SEM images of pellets, made of a powder synthesized with EG and heat treated at 600 °C for 5 min, then sintered at a) 750 °C and b) 925 °C for 30 min.

-Pellets made of powders obtained by solid state reaction.

In order to determine the impact of the powder synthesis process, a reference pellet was prepared with a powder synthesized by solid state reaction [START_REF] Goutenoire | Crystal structure of La 2 Mo 2 O 9 , a new fast oxide-ion conductor[END_REF]. As evidenced by dilatometry (figure 14), the sinterability of these powders is significantly lower than that of the powders obtained by the polyol process. It was thus necessary to treat these powders by high energy ball milling to increase the relative density as it strongly influences the conductivity [START_REF] Georges | Structural and transport properties of the fast oxide-ion conductors La 2-x R x Mo 2 O 9 (R=Nd, Gd, Y)[END_REF]. This step allowed to reach a relative density of 98% after a rapid sintering at 925°C. As in the case of pellets made of powders prepared by the polyol process, the relative density of the pellets made from powder synthesized by solid state reaction is higher after a rapid sintering at 925°C than after dilatometry, the relative density being in the last case of 94%. This may be due to the fact that rapid sintering allows to reduce grain growth during the increase in temperature before reaching the sintering temperature.

-

Conclusion on sintering of the powders

In conclusion, according to the dilatometric study and the microstructural characterization, a strong difference is observed between the sinterings of spherical particles (obtained with EG) and of platelets (obtained with DEG). Indeed, after a rapid sintering at 925°C, the relative density is markedly higher for the pellets made of platelets, the closure of the porosity being even reached.

The lower relative density of the pellets made of spherical particles may be due to a strong agglomeration of the particles that lead to a differential sintering. However, it has to be pointed out that a relative density of about 80%, reached after a rapid sintering at 650 or 750°C for the platelets or spherical particles respectively, is already satisfactory to realize conductivity measurements by impedance spectroscopy in suitable conditions when the grain growth has to be limited as much as possible.

Moreover, it has to be noted that, when sintered pellets are prepared from the powders obtained by the polyol process, a very high relative density (95%) can be reached, without any milling step that would lead to the introduction of impurities, contrarily to the powders obtained by solid state reaction. This is thus an important advantage offered by the powders prepared by the polyol process with DEG, that can be very useful in many applications.

Conductivity measurements

Our aim was to determinate if the grain size and the morphology of the starting powders impact the ionic conduction properties of the La The resistance of all the samples decreases with increasing temperature. Up to three contributions can be distinguished. The first contribution (at high frequencies), that is represented as a semicircle and modeled by a parallel circuit R-CPE, can be assigned to the grain contribution. The phenomena observed at intermediate frequencies, called as grain boundaries contributions, correspond to all the phenomena that happen at the grain interfaces. At low frequency, the electrode polarization is observed in some cases, in the form of a straight line or sometimes of an arc of circle. The presence of several relaxations, which can be assigned to the grain and grain boundaries contributions, was already observed for the La 2 Mo 2 O 9 compound synthesized by freeze-drying [START_REF] Marrero-Lopez | Synthesis and characterization of La 2 Mo 2 O 9 obtained from freeze-dried precursors[END_REF][START_REF] Marrero-López | Synthesis, sinterability and ionic conductivity of nanocrystalline La 2 Mo 2 O 9 powders[END_REF] or spray pyrolysis [START_REF] Baqué | Microstructural and electrical characterizations of tungsten-doped La 2 Mo 2 O 9 prepared by spray pyrolysis[END_REF]. In the case of the La 2 Mo 2 O 9 powders obtained by solid state reaction and then ball milled and sintering at 925°C, the grain boundaries contribution is very low and cannot generally be distinguished from grain contribution. It is the same for our reference pellet (figure 17 e)).

A significant difference is observed in the case of the pellet made of powder synthesized in DEG and sintered at 650 °C (figure 17 a)). Indeed, the contribution of the grain is characterized by a far lower resistance and therefore a significantly greater conductivity than for the other pellets.

However, despite the high conductivity of the grain, the resistance at grain interfaces is very important, leading to a lower total conductivity (σ = 6.8 10 -7 S.cm -1 ) than for other pellets made of powders synthesized by polyol process (σ closed to 2 10 -6 S.cm -1 ) at 377 °C, despite a higher compactness than for the pellets made of powders obtained with EG.

We also observed, for all the pellets, a decrease of the resistance of grains and grain boundaries and a shift of the characteristic frequencies to the high frequencies with increasing temperature, until the second semicircle relative to the grain boundaries contribution completely disappears at higher temperature.

Figure 17: Complex impedance diagram recorded at 327, 352 and 377 °C for pellets made of powders synthesized with DEG and sintered at 650 (a) or 925 °C (b), and with EG (u = 3) and The modeling of diagram (Z-view software) was thus realized by using several theoretical models that accounted for the evolution of the aspect of the diagram according to the temperature and the sample. Refinements were realized by modeling either with two parallel equivalent circuits R-CPE for the grain and grain boundaries contribution and a CPE for the polarization at electrodes, or with only one parallel equivalent circuit R-CPE (and a CPE) when there is an overlapping of the grain and grain boundaries contributions. In the last case, this is thus the total resistance and conductivity which are determined globally. At high temperature, for all the pellets, no more semicircle corresponding to the migration phenomena is observable and positive values of the imaginary part are even measured. The resistance of the material is then assimilated to the abscissa of the first point for which Z" becomes negative.

0 5,0e6 1,0e7 1,5e7 2,0e7 -2,0e7 -1,5e7 -1,0e7 -5,0e6 0 Z
The values of the grain, grain boundaries and total conductivities are listed in table 5. For the powder synthesized with DEG and sintered at 650 °C, the grain conductivity is slightly higher but the grain boundaries conductivity is lower, resulting in a total conductivity slightly lower than that of the others pellets. For the same powder but sintered at 925 °C, the ratio between the conductivities of the grains and grain boundaries, σ g / σ gb at 327 °C is significantly lower (1.6 instead of 16.4) and the total conductivity is very closed to that measured in the case of the powder synthesized with EG and sintered at 925 °C. However, the ratio σ g / σ gb remains higher than in the case of the powders obtained with EG, for which it is of 0.6 and 0.5 respectively after sintering at 750 or 925 °C.

The expected decrease of the contribution of the grain boundaries, with the increase of the sintering temperature, has also been observed for powders of La 2 Mo 2 O 9 synthesized by freeze drying [START_REF] Marrero-López | Synthesis, sinterability and ionic conductivity of nanocrystalline La 2 Mo 2 O 9 powders[END_REF].

Table 5 : Grains (σ g ), grain boundaries (σ gb ) and total (σ t ) conductivities at 327, 352 and 377°C, determined by using the software ZView, of pellets made from powders synthesized with DEG and sintered at 650 or 925 °C or with EG (u = 3) and sintered at 750 or 925 °C or of a pellet made from the powder obtained by solid state reaction and sintered at 925°C. The Arrhenius plots ( ) of all the samples are reported in figure 18. For all curves, an abrupt break is observed around of 600 °C. This abrupt change in the anionic conductivity is due to the first order phase transition α / β, the β-form presenting the higher conductivity. On both sides of this break, Arrhenius law is followed. It is interesting to note that the jump in conduction occurs at a slightly lower temperature (between 25 and 50 °C lower) in the case of the pellet made of the powder synthesized with DEG and sintered at 650 °C. Its total conductivity, is always the lowest, except at 602 °C. It can be also observed that the jump in conductivity seems to be less important in the case of powders sintered at 650 °C (prepared from DEG) or 750 °C (prepared with EG). As sintering of the powders was carried out at temperatures as low as possible and for relatively short times (30 min) in order to limit grain growth, the densification of the pellets still proceed at high measurement temperatures. The relative density increased from 79% to 93% and from 78% to 81% for pellets made of the powders synthesized with DEG and EG respectively. However, the evolution of the sample dimensions does not affect significantly the shape factors and the conductivities that are deduced from it. For example, at 702 °C, total conductivities calculated with the new shape factor, are only slightly higher (5.98 10 -3 instead of 5.58 10 -3 S.cm -1 or 7.57 10 -3 instead of 7.45 10 -3 S.cm -1 with respectively DEG or EG).

Nevertheless, for the pellet made of the powder synthesized with EG and sintered at 750 °C, the carrying out of sintering during the measurements (at the highest temperatures), can explain the slight breaking of the conductivity beyond 652 °C. In the case of the pellet made of the powder synthesized with DEG and sintered at 650 °C, we probably do not observe this small breaking of the conductivity as the sintering temperature of the powder is lower (beginning between 550 and 600 °C) and coincides with the one of the αβ phase transition, this transition leading to an increase of the conductivity.

It can be noted that, except at 602 °C, the conductivity of the pellet made of the powder synthesized by solid state reaction is always slightly higher than the ones of the pellets made of the powders synthesized by the polyol process. This can be explained by the amount of grain boundaries which is lower in the samples prepared from powders synthesized by solid state reaction. In this case, the total conductivity is quite not affected by the grain boundaries resistance as their contribution is weaker. The activation energies, estimated from the slope of the segments between 300 and 600 °C and between 625 °C and 725 °C of the Arrhenius plot, are presented in table 6. All the samples present very similar activation energies, around 1.3 eV, for the first segment. However, this value is slightly higher in the case of the pellet made of the powder synthesized with DEG and sintered at 650 °C. For the second segment, the value of the activation energy is lower, between 0.61 and 1.03 eV. However, this variation is not really representative, as some shape factors evolved during measurements at the highest temperatures (above 600 °C). According to all these results, we can establish that the evolution of the conductivity of the samples synthesized by polyol process is similar to that of the samples synthesized by solid state reaction.

However, the values are slightly lower. This can be attributed to the high amount of grain boundaries that create an effect of "blocking" in our case, leading to their higher contribution in the resistance to ion migration. Therefore, the measured total conductivity is lower than that determined when the initial powder is synthesized by solid state reaction as the ratio of grain boundaries is very low in this case.

The same behavior was observed for the La 2 Mo 2 O 9 compound synthesized by freeze drying and sintered at temperatures lowers than 925°C, the relative density being less than 92% [START_REF] Marrero-López | Synthesis, sinterability and ionic conductivity of nanocrystalline La 2 Mo 2 O 9 powders[END_REF]. As in many cases, it is difficult to completely benefit of conduction properties probably improved by nanometric particles.

Conclusion

Nanostructured La 2 Mo 2 O 9 powders were synthesized by the polyol process, with two different morphologies (platelets or spheres) according to the nature of the solvent. Obtaining crystallized nanodomains can be achieved by the polyol process as it presents the advantage of a relatively low temperature thermal treatment (around 550-600°C). In order to determine the effect of the main synthesis parameters on the powder microstructure and purity, we varied also the refluxing time, the hydrolysis ratio, the metal concentration and we had hydroxide ions by the means of urea.

The ionic conduction properties were determined. First of all, the sinterability of the powders was evaluated in order to determine the more appropriate sintering temperature that allows obtaining relatively dense pellets while preserving as much as possible the grain size. It was established that the powders synthesized with DEG as solvent present a very high sinterability, relative densities of 95% being reached without any intermediate step as milling, contrarily to the solid state reaction for example. The values of the ionic conductivity are close to the ones of the powders synthesized by solid state reaction but always lower, except at 602°C, for the powder synthesized with DEG and rapidly sintered at 600°C. The lower values of the total conductivity can be explained by the high amount of grain boundaries in the pellets made from the powders synthesized by the polyol process.

In our case, they lead to a contribution of grain boundaries to the total resistance of the pellets that can be very important. However, despite slightly lower conduction properties, the efficient sintering of such nanoparticles, with no milling step could be of great interest for further applications (better long term stability and performances of the material). with DEG and 2 or 5 mmol.L -1 with EG, then heat treated for 5 min at 600 °C.

Figure 2 :

 2 Figure 2: XRD diagrams of precipitates synthesized with different polyols : EG, PEG and TEG and heat treated at 600°C for 5 min.

Figure 3 :

 3 Figure 3: XRD diagrams of precipitates synthesized a) with DEG (u = 1, 2 or 3) and b) with EG (u = 2, 3 or 4) and heat treated at 600°C for 5 min.

  .a) but the powder synthesis in EG is composed of almost spherical particles (figure 5.b).

Figure 5 :

 5 Figure 5: SEM images of precipitates synthesized with DEG (u = 3) (a) or with EG (u = 3) (b) and heat treated at 600°C for 5min.

Figure 6 :

 6 Figure 6: TEM images of the precipitate synthesized with EG (u=3) and heat treated at 600°C for 5min.

Figure 10 :

 10 Figure 10: SEM images of the precipitate synthesized with DEG or EG (u = 3) and hydrolysis ratio h = 2, then heat treated at 600°C for 5min.

Figure 11 :Figure 12 :Figure 13 :

 111213 Figure 11: XRD diagrams of precipitates synthesized with DEG, with metal concentrations of 0.05, 0.1, 0.2, 0.3, 0.4 or 0.5 mol.L -1 (u = 0) and heat treated at 600°C for 5min

  SEM images of pellets sintered at 650 or 925°C and then fractured are presented in figure15. They evidence the transition from open to closed porosity when increasing the sintering temperature from 650°C (figure15 a) to 925°C (figure15 b) as well as the increase in density. For pellet sintered at 650 °C, we can observe the presence of relatively large, interconnected pores (few hundred nanometers) located at grain boundaries, the grain size being in the order of microns. For pellet , the porosity is greatly decreased and closed. Therefore, its relative density is very high.

Figure 15 :

 15 Figure 15: SEM images of pellets, made of a powder obtained after heat treatment for 5 min at 600 °C of the precipitate synthesized in DEG, then sintered at a) 650 °C and b) 925 °C for 30 min.

2

 2 Mo 2 O 9 compound. This part of the work is thus dedicated to the determination of the transport properties of the pellets made of pure La 2 Mo 2 O 9 powders prepared by the polyol process with DEG and sintered at 650 or 925°C or with EG and sintered at 750 or 925°C. The results are compared with those of a reference pellet made of powder prepared by the solid state reaction. The relative densities of the different pellets are of 79, 95, 78, 82 and 98% respectively. The data were collected in the temperature range 302 -700°C. The impedance diagram acquired at 327, 352 and 377 °C are presented in figure 17 for the pellets made of powders prepared by polyol process with DEG (u=0) and sintered at 650 (a) or 925 °C (b), and with EG (u = 3) and sintered at 750 (c) or 925 °C (d), and of powder prepared by solid state reaction and sintered at 925°C (e).

  (c) or 925 °C (d), and of the powder synthesized by solid state reaction and sintered at 925°C (e).

Figure 18 :

 18 Figure 18 : Arrhenius plot of the ionic conductivity of the pellets made of powders synthesized with DEG and sintered at 650 °C or 925 °C or with EG (u = 3) and sintered at 750 or 925 °C or prepared by solid state reaction and sintered at 925 °C.

Figure 1 :

 1 Figure 1: XRD diagrams of precipitates synthesized with DEG with a reflux time of 1, 2 or 3 hours and heat treated at 600°C for 5 min.

Figure 2 :

 2 Figure 2: XRD diagrams of precipitates synthesized with different polyols : EG, PEG and TEG and heat treated at 600°C for 5 min.

Figure 3 :

 3 Figure 3: XRD diagrams of precipitates synthesized a) with DEG (u = 1, 2 or 3) and b) with EG (u = 2, 3 or 4) and heat treated at 600°C for 5 min.

Figure 4 :

 4 Figure 4: XRD diagrams of precipitates synthesized with PEG (u = 3) or TEG (u = 3) and heat treated at 600°C for 5min.

Figure 5 :

 5 Figure 5: SEM images of precipitates synthesized with DEG (u = 3) (a) or with EG (u = 3) (b) and heat treated at 600°C for 5min.

Figure 6 :

 6 Figure 6: TEM images of the precipitate synthesized with EG (u=3) and heat treated at 600°C for 5min.

Figure 7 :

 7 Figure 7: SEM images of precipitates synthesized with PEG (u = 3) or TEG (u = 3) and heat treated at 600°C for 5min.

Figure 8 :Figure 9 :Figure 10 :

 8910 Figure 8: XRD diagrams of the precipitate synthesized with DEG and hydrolysis ratio h equal 0, 2, 10, 20 and 50 and heat treated at 600°C for 5min

Figure 11 :Figure 12 :

 1112 Figure 11: XRD diagrams of precipitates synthesized with DEG, with metal concentrations of 0.05, 0.1, 0.2, 0.3, 0.4 or 0.5 mol.L -1 (u = 0) and heat treated at 600°C for 5min

Figure 13 :

 13 Figure 13: SEM images of precipitates synthesized with metal concentrations [La + Mo] of 0.05 and 0.5 mol.L -1 with DEG (u = 0) and EG (u = 3), then heat treated for 5 min at 600 °C.

Figure 14 :

 14 Figure 14 : XRD diagrams of precipitates synthesized with DEG, and DDAB concentrations of 0.5, 1, 2, 3, 4 and 5 mmol.L -1 and heat treated at 600°C for 5min.

Figure 15 :

 15 Figure 15: XRD diagrams of precipitates synthesized with EG, and DDAB concentrations of 0.5, 1, 2, 3, 4 and 5 mmol.L -1 and heat treated at 600°C for 5min.

Figure 16 :

 16 Figure 16: SEM images of precipitates synthesized with concentrations of DDAB of 0.5 mmol.L -1

Figure 17 :

 17 Figure 17: TEM image of a) the precipitate synthesized with DEG with a concentration of DDAB of 0.5 mmol.L -1 and b) the precipitate synthesized with EG with a concentration of DDAB of 5 mmol.L -1 , and heat treated at 600 °C for 5 min.

Figure 18 :

 18 Figure 18: XRD diagrams of precipitates synthesized with DEG, and PVP concentrations of 2 or 4 mmol.L -1 and heat treated at 600°C for 5min.

Figure 19 :

 19 Figure 19: XRD diagrams of the precipitates synthesized with EG, and PVP concentrations of 2 or 4 mmol.L -1 and heat treated at 600°C for 5min.

Figure 20 :

 20 Figure 20: Linear shrinkage as a function of temperature, with a heating and cooling rate of 5°C.min -1 , under air, of powders synthesized with DEG (u = 0) or EG (u = 3) and a heat treatment at 600 °C for 5 min, and by solid state reaction (SSR).

Figure 21 :

 21 Figure 21: SEM images of pellets, made of a powder obtained after heat treatment for 5 min at 600 °C of the precipitate synthesized in DEG, then sintered at a) 650 °C and b) 925 °C for 30 min.

Figure 22 :

 22 Figure 22: SEM images of pellets, made of a powder synthesized with EG and heat treated at 600 °C for 5 min, then sintered at a) 750 °C and b) 925 °C for 30 min.

Figure 23 :

 23 Figure 23: Complex impedance diagram recorded at 327, 352 and 377 °C for pellets made of powders synthesized with DEG and sintered at 650 (a) or 925 °C (b), and with EG (u = 3) and sintered at 750 (c) or 925 °C (d), and of the powder synthesized by solid state reaction and sintered at 925°C (e).

Table 1 :

 1 Nature of the different polyols and reflux temperatures.

	Solvent	Purity (%)	Theoretical T bp (°C)	T reflux (experimental
				boiling point )
	Ethyleneglycol (EG)	99.9%, Alfa Aesar	197	192
	1,2-Propanediol (PEG)	97%, Acros organics	188	182
	Diethyleneglycol (DEG)	99.9%, Aldrich	245	227
	Tetraethyleneglycol (TEG)	99.5%, Acros organics	327	312

La 2 Mo 3 O 12 EG PEG TEG + +: La 2 Mo 2 O 9 + + + + + + + + + + + Intensity(a.u.) impurity

  , La 2 Mo 3 O 12 , presents a lack of lanthanum. Urea was also added to synthesis with DEG, even if pure La 2 Mo 2 O 9 powders were obtained, in order to determine if its addition can have an impact on the morphology of the powders.

	The addition of urea, to the synthesis realized with DEG and EG as solvent, was performed
	according to the ratios u (u = [urea]/[La+Mo]) presented in table 2. All the powders obtained with
	DEG as solvent, after heat treatment, are identified to be pure La 2 Mo 2 O 9 (figure 3 a). In the case of
	EG as solvent, pure La 2 Mo 2 O 9 is obtained with u = 3 whereas La 2 Mo 3 O 12 and La 2 MoO 6 impurities
	are observed by XRD for u = 2 and u = 4 respectively (figure
	17	20	30	40

*:

Table 2 :

 2 Ratios of urea, u, added to the starting solution and characterization of the powders.

	solvent	[urea]/[La+Mo]	impurity	Size(nm)	S BET (m².g -1 )
	DEG	1	none	29	15
	DEG	2	none	43	9
	DEG	3	none	35	11
	EG	2	La 2 MoO 6	---
	EG	3	none	50	6
	EG	4	La 2 Mo 3 O 12	---
	PEG	3	none	46	10
	TEG	3	none	52	4

Table 3 :

 3 Hydrolysis ratio h, added to the starting solution and characterization of the powders.

	Solvent	hydrolysis ratio h	T reflux (experimental boiling point )	Size(nm)	S BET (m².g -1 )
	DEG	0	227	41	16
	DEG	2	220	56	8
	DEG	10	203	---	---
	DEG	20	193	---	---
	DEG	50	172	---	---
	EG	0	192	50	6
	EG	2	189	52	4
	EG	10	179	57	1
	EG	20	168	---	---
	EG	50	154	---	---

Table 4 :

 4 Precipitates synthesized with different concentrations of metal [La + Mb] with DEG or EG and heat treated for 5 min at 600 °C.

	Solvent	[La + Mo](mol .L -1 )	u= [urea]/[La+Mo] Size(nm) S BET (m².g -1 )
	DEG	0.05	0	24
	DEG	0.1	0	11
	DEG	0.2	0	16
	DEG	0.3	0	12
	DEG	0.4	0	7
	DEG	0.5	0	16
	EG	0.05	3	6
	EG	0.1	3	3
	EG	0.2	3	6
	EG	0.3	3	5
	EG	0.4	3	3
	EG	0.5	3	5

All the powders synthesized with DEG or EG, after a heat treatment at 600°C for 5 min are identified to be pure La 2 Mo 2 O 9 by XRD. The crystallite size was estimated, from XRD patterns (figure

11 and 12

), according to the Scherrer equation. From the thinnest diffraction peak at about 2q=24.9 °, the crystallite size is between 21-48nm with DEG and 29-57nm with EG.

Table 6 :

 6 Activation energies between 300 and 600 °C and between 625 and 725 °C for the pellets made of powders synthesized with DEG and sintered at 650 or 925 °C or with EG (u = 3) and sintered at 750 or 925 °C or synthesized by solid state reaction (SSR) and sintered at 925 °C.

	Synthesis method	Sintering temperature (•C)	Ea (eV) between 300°C and 600°C	Ea (eV) between 625°C and 725°C
	SSR	925	1.26	1.01
	DEG	650	1.42	1.03
	DEG	925	1.27	0.73
	EG	750	1.33	0.61
	EG	925	1.31	0.81

Acknowledgements

We would like to acknowledge the Ministère de l'Enseignement Supérieur et de la Recherche Scientifique of the Tunisian Republic and the Ecole Doctorale Matière, Molécules et Matériaux en Pays de la Loire (3MPL)(ED500) for their financial support. The authors also express their thanks to Melanie Joly and Cyrille Bruneau, from the IUT of Le Mans, for their help with BET measurements.


Andrei Romashchenko
email: andrei.romashchenko@lirmm.fr

Marius Zimand

An Operational Characterization of Mutual Information in Algorithmic Information Theory

Keywords: 2012 ACM Subject Classification Mathematics of computing → Information theory, Theory of computation → Communication complexity, Theory of computation → Probabilistic computation Kolmogorov complexity, mutual information, communication complexity, secret key agreement

Introduction

Mutual information is a concept of central importance in both information theory (IT) and algorithmic information theory (AIT), also known as Kolmogorov complexity. We show an interpretation of mutual information in AIT, which links it to a basic concept from cryptography. Even though a similar interpretation was known in the IT framework, an operational characterization of mutual information in AIT has been elusive till now.

To present our result, let us consider two strings x and y. It is common to draw a Venn-like diagram such as the one in Figure 1 to visualize the information relations between Figure 1 Two strings x and y, and their information. There are six regions that we distinguish: [START_REF] Ahlswede | Common randomness in information theory and cryptography -I: secret sharing[END_REF] The left solid circle represents the information in x, as given by its Kolmogorov complexity, denoted C(x); [START_REF] Antunes | Cryptographic security of individual instances[END_REF] The right dotted circle represents the information in y, denoted C(y); [START_REF] Bennett | Privacy amplification by public discussion[END_REF] The entire grey region (the two circles taken together) represents the information in x and y, denoted C(x, y); [START_REF] Gregory J Chaitin | A theory of program size formally identical to information theory[END_REF] The light-grey region in the first circle represents the information in x conditioned by y, denoted C(x | y); [START_REF] Chan | Multivariate mutual information inspired by secret-key agreement[END_REF] The light-grey region in the second circle represents the information of y conditioned by x, denoted C(y | x); and (6) the dark-grey region in the middle represents the mutual information of x and y, denoted I(x : y).

(5) have a clear operational meaning. For instance, C(x) is the length of a shortest program that prints x, C(x | y) is the length of a shortest program that prints x when y is given to it, and so on. On the other hand, the mutual information I(x : y) from region [START_REF] Alexey | Upper semi-lattice of binary strings with the relation "x is simple conditional to[END_REF] is defined by a formula: I(x : y) = C(x) + C(y) -C(x, y). Intuitively, it is the information shared by x and y. But is there an operational interpretation of the mutual information? As mentioned above, we give a positive answer: The mutual information of x and y is essentially equal to the length of a longest shared secret key that two parties, one having x and the other one having y, and both parties also possessing the complexity profile of the two strings, can establish via a probabilistic protocol.

The following simple example illustrates the above concepts. Suppose that Alice and Bob want to agree on a common secret key. If they could meet face-to-face, they could just generate such a key by, say, flipping a coin. Unfortunately, they cannot meet in person and what makes the situation really troublesome is that they can only communicate through a public channel. There is however a gleam of hope because Alice knows a random line x in the affine plane over the finite field with 2 n elements, and Bob knows a random point y on this line. The line x is specified by the slope a and the intercept b and the point y by its two coordinates c and d. Therefore each of x and y has 2n bits of information, but, because of the geometrical correlation, together they have 3n bits of information. Thus, in principle, Alice and Bob share n bits. Can they use them to obtain a common secret key? The answer is yes: Alice sends a to Bob, Bob, knowing that his point is on the line, finds x, and now they can use b as the secret key, because the adversary has only seen a, and a and b are independent.

It may appear that the geometrical relation between x and y is crucial for the above solution. In fact it is just a red herring and Alice and Bob can agree on a common secret key in a very general setting. To describe it, we consider the scenario in which Alice has a random string x and Bob has a random string y. If x = y, then Alice and Bob can use their common string as a secret key in an encryption scheme (such as the one-time pad) and achieve perfect information-theoretical security. What happens if x and y are not equal, but only correlated? Somewhat surprisingly, for many interpretations of "correlated," they can still agree on a shared secret key via interaction on a public channel (for instances of this assertion, see [START_REF] Sik | Multi-user and wiretap channels including feedback[END_REF][START_REF] Bennett | Privacy amplification by public discussion[END_REF][START_REF] Ueli | Secret key agreement by public discussion from common information[END_REF][START_REF] Ahlswede | Common randomness in information theory and cryptography -I: secret sharing[END_REF]). In this paper, we look at this phenomenon using the very general framework of algorithmic information theory to measure the correlation of strings.

Our contributions

Characterization of mutual information. In a secret key agreement protocol, Alice and Bob, on input x and respectively y, exchange messages and compute a common string that is random conditioned by the transcript of the protocol. Such a string is said to be a shared secret key. Unless specified otherwise, we use protocols having the following features:

(1) We assume that Alice and Bob also know how their x and y are correlated. In our setting this means that Alice and Bob know the complexity profile of x and y, which, by definition, is the tuple (C(x), C(y), C(x, y)). (2) The protocols are effective and randomized, meaning that Alice and Bob use probabilistic algorithms to compute their messages.

Theorem 1 (Main Result, informal statement). 1. There is a secret key agreement protocol that, for every n-bit strings x and y, allows Alice and Bob to compute with high probability a shared secret key of length equal to the mutual information of x and y (up to an O(log n) additive term).

No protocol can produce a longer shared secret key (up to an O(log n) additive term).

Secret key agreement for three or more parties. Mutual information is only defined for two strings, but secret key agreement can be explored for the case of more strings. Let us consider again an example. Suppose that each of Alice, Bob, and Charles have a point in the affine plane over the finite field with 2 n elements, and that the three points, which we call A, B, C, are collinear. Thus each party has 2n bits of information, but together they have 5n bits of information, because given two points, the third one can be described with n bits. The parties want to establish a common secret key, but they can only communicate by broadcasting messages over a public channel. They can proceed as follows. Alice will broadcast a string p A , Bob a string p B , and Charles a string p C , such that each party using his/her point and the received information will reconstruct the three collinear points A, B, C. A protocol that achieves this is called an omniscience protocol because it spreads to everyone the information possessed at the beginning individually by each party. In the next step, each party will compress the 5n bits, comprising the three points, to a string that is random given p A , p B , p C . The compressed string is the common secret key. We will see that up to logarithmic precision it has length 5n -

(|p A | + |p B | + |p C |).
Assuming we know how to do the omniscience protocol and the compression step, this protocol produces a common secret key of length 5n -CO(A, B, C), where CO(A, B, C) is the minimum communication for the omniscience task for the points A, B, C. In our example, it is clear that each one of p A , p B , p C must be at least n bits long, and that any two of these strings must contain together at least 3n bits. Using some recent results from the reference [START_REF] Zimand | Kolmogorov complexity version of Slepian-Wolf coding[END_REF], it can be shown that any numbers satisfying these constraints can be used for the omniscience task. It follows that the smallest communication for omniscience is achieved when

|p A | = |p B | = |p C | = 1.
5n, and thus the key has 5n -4.5n = 0.5n bits (Warning: we have ignored in the entire discussion some O(log n) terms). We show that this holds in general. If parties have, respectively, one component of a tuple (x 1 , . . . , x ) of n-bit strings, then up to O(log n) precision, they can produce a common secret key of length C(x 1 , . . . , x ) -CO(x 1 , . . . , x ), where CO(x 1 , . . . , x ) is the I C A L P 2 0 1 8

95:4

An Operational Characterization of Mutual Information in AIT minimum communication for the omniscience task. The protocol that produces such a key is probabilistic, and, as was the case for two strings, assumes that each party i has at the beginning of the protocol besides its input string x i also the complexity profile of the entire tuple (x 1 , . . . , x ). We also show a matching (up to O(log n)) upper bound: no probabilistic protocol can produce a longer secret key.

Remark. The value CO(A, B, C) is understood as the communication complexity of the omniscience problem. However, it can be computed as a function of the Kolmogorov complexities of the involved strings, see Definition 4 below. This fact (the communication complexity of the optimal omniscience protocol depends only on the complexity profile of the inputs) is not trivial and requires a proof.

Communication complexity for secret key agreement. In the protocol in Theorem 1, Alice and Bob exchange min(C(x | y), C(y | x)) + O(log n) bits and obtain with high probability a shared secret key of length I(x : y) -O(log n). In this protocol we can assume that Alice and Bob use either private random bits, or public random bits. We show that for the model with public random bits, the communication complexity of the protocol is optimal, in the sense that in any protocol with public random bits there are input strings x and y, on which Alice and Bob have to exchange at least min(C(x | y), C(y | x)) bits. In fact our lower bound is stronger: we show that, for any constants δ 1 , δ 2 > 0, if Alice and Bob use a protocol with communication complexity (1 -δ 1 ) min(C(x | y), C(y | x)) for every input pair x, y, then there are inputs for which the shared secret key that they obtain has length at most δ 2 I(x : y). That is, if the communication complexity sinks below the threshold min(C(x | y), C(y | x)), then the size of the common secret key drops to virtually zero. To determine the optimal communication complexity for the model with private random bits remains an open problem.

Related previous work.

IT vs. AIT. Before reviewing existing related results in the IT and the AIT frameworks, it is useful to understand the distinction between the two theories. In computer science the attribute random is mainly used in two (fairly different) contexts: random processes and random objects. In short, IT, which we also call Shannon's framework, focuses on the former, whereas AIT, which we also call Kolmogorov's framework, focuses on the latter. On the one hand, we may think of an uncertain physical process with unpredictable outcomes, and employ the framework of the classic probability theory (distributions, random variables, etc.). The notion of a random variable formalizes the idea of a process like coin tossing. In this context we can measure the uncertainty of a random variable as a whole (by its Shannon's entropy, its min-entropy, etc.), but we can not ask whether one specific outcome is random or not. On the other hand, people use tables of random numbers, which are available as specific sequences of digits, written on a disc or printed on a paper. The usefulness of such a table depends on its individual properties: frequencies of digits, presence or absence of hidden regularities, compressibility, etc. The usual way to measure the uncertainty of an individual string of digits is Kolmogorov complexity. In both contexts the formal measures of randomness may or may not involve computational complexity (see, e.g., different versions of pseudoentropy for distributions and the resource bounded variants of Kolmogorov complexity for individual strings). These two formalizations of randomness are connected but not interchangeable.

Both notions of randomness appear in cryptography. For example, in the one-time pad scheme, two parties share a "random" key that remains "secret" for the attacker. It is common to use Shannon's framework, and therefore the notions of randomness and secrecy are defined in terms of random processes. In the ideal situation both parties should have access to a common source of randomness, e.g., to the results of tossing an unbiased coin (hidden from the adversary). By tossing this coin n times we get a random variable with maximal possible entropy, and thus, in Shannon's framework, the quality of randomness is perfect. But if by chance we obtain a sequence of n zeros, then this specific one-time pad looks pretty useless in any practical application. However, Shannon's information theory provides no vocabulary to complain about this apparently non-random individual key. Antunes et al. [START_REF] Antunes | Cryptographic security of individual instances[END_REF] suggested to use Kolmogorov complexity to measure the "secrecy" of individual instances of a one-time pad or a secret sharing schemes. We have in mind a similar motivation, and in this work a "secret key" is an individual string that is random in the sense of Kolmogorov complexity.

Related work.

We start with a brief account of works on secret key agreement in the IT setting. The secret key agreement is a relatively well-studied problem in information theory, motivated, as the name suggests, by applications in information-theoretically secure cryptography. Wyner [START_REF] Wyner | The wire-tap channel[END_REF] and Csiszár and Körner [START_REF] Csiszár | Broadcast channels with confidential messages[END_REF] have analyzed the possibility of obtaining a shared secret key in the case when one party sends to the other party a single message on a channel from which the eavesdropper can obtain partial information. Maurer [START_REF] Ueli | Conditionally-perfect secrecy and a provably-secure randomized cipher[END_REF][START_REF] Ueli | Secret key agreement by public discussion from common information[END_REF] considered the case of protocols with several rounds of communication and showed that interaction can be more powerful than one-way transmission. Ahlswede and Csiszár [START_REF] Ahlswede | Common randomness in information theory and cryptography -I: secret sharing[END_REF] and Maurer [START_REF] Ueli | Secret key agreement by public discussion from common information[END_REF] have established the tight relation between interactive secret key agreement and mutual information for memoryless sources. In the memoryless model, the input data is given by two random variables (X 1 , X 2 ) obtained by n independent draws from a joint distribution, where Alice observes X 1 and Bob observes X 2 . Informally stated, the references [START_REF] Ueli | Secret key agreement by public discussion from common information[END_REF][START_REF] Ahlswede | Common randomness in information theory and cryptography -I: secret sharing[END_REF] show that the longest shared secret key that Alice and Bob can establish via an interactive protocol with an arbitrary number of rounds is equal to the mutual information of X 1 and X 2 . Csiszár and Narayan [START_REF] Csiszár | Secrecy capacities for multiple terminals[END_REF] go beyond the scenario with two parties, and consider the case of an -memoryless source (X 1 , . . . , X ) and parties, each one observing one component of the tuple. They show that the longest shared secret key the parties can establish via an interactive protocol with an arbitrary number of rounds is equal to the entropy H(X 1 , . . . , X ) of the -memoryless source from which one subtracts the minimum communication for omniscience. Their result holds also for stationary ergodic sources, which generalize memoryless sources. As one can see, our results are very similar. They have been inspired by the papers [START_REF] Ahlswede | Common randomness in information theory and cryptography -I: secret sharing[END_REF][START_REF] Ueli | Secret key agreement by public discussion from common information[END_REF][START_REF] Csiszár | Secrecy capacities for multiple terminals[END_REF] and represent the AIT analogue of the results presented above. Our results imply their IT analogues, and can be viewed as more general because they do not require the memoryless or ergodicity properties of sources (in fact they do not require any generative model at all). Regarding the communication complexity of secret key agreement protocols, we only note here that Tiyagi [START_REF] Tyagi | Common information and secret key capacity[END_REF] has shown that for memoryless sources it is equal to the difference between interactive common information in Wyner's sense and mutual information. In the full version of this paper we explain how Tyagi's result compares to our results on communication complexity in the AIT framework.

Let us now say a few words about related results from the AIT world. To the best of our knowledge, in AIT there has been no previous works on secret key agreement. However, the general idea of "materialization" of mutual information was studied extensively. Motivated by the intuition that mutual information represents the amount of shared information in two strings, researchers have explored the extent to which mutual information can be materialized more or less effectively. The relevant concept is that of common information. Informally, a I C A L P 2 0 1 8

95:6 An Operational Characterization of Mutual Information in AIT

string z is a common information string extracted from strings x and y, if z can be "computed" from x, and also from y, where "computed" is taken in a more liberal sense that allows the utilization of a few help bits. In the most common setting of parameters, we require that

C(z | x) = O(log n) and C(z | y) = O(log n),
where n is the length of x and y and the constant hidden in the O(•) notation depends only on the universal machine. Informally, the common information of x and y is the length of a longest common information string that can be extracted from x and y. It can be shown that up to logarithmic precision common information is upper bounded by mutual information. In an influential paper, Gács and Körner [START_REF] Gács | Common information is far less than mutual information[END_REF] have constructed strings x and y for which the common information is much smaller than the mutual information. Moreover, the property of a pair (x, y) of having common information equal to mutual information does not depend solely on the complexity profile of x and y: There exist pairs (x 1 , y 1 ) and (x 2 , y 2 ) having the same complexity profile, and for (x 1 , y 1 ) the common information and mutual information are equal, whereas for (x 2 , y 2 ) they are not. Muchnik [START_REF] Muchnik | On common information[END_REF] and Romashchenko [START_REF] Romashchenko | Pairs of words with nonmaterializable mutual information[END_REF] have strengthened the Gács-Körner theorem in significant ways, by allowing a larger amount of help bits, parameterizing the mutual information of the constructed pair (x, y), and other ways. Chernov et al. [START_REF] Alexey | Upper semi-lattice of binary strings with the relation "x is simple conditional to[END_REF] presents alternative constructions of strings for which the common information is smaller than mutual information for several regimes of parameters. A nice, self-contained and accessible exposition of this research line can be found in the book of Shen, Vereshchagin and Uspensky [23, Chapter 11].

Thus, previous works have shown negative results regarding the "materialization" of mutual information in AIT. As far as we know, ours is the first positive result. In summary, we now know that computation without communication, even enhanced with help bits, fails to extract the mutual information of two strings, while interactive computation succeeds.

The basics of algorithmic information theory

Given a Turing machine M , a string p is said to be a program (or a description) of a string x, if M on input p prints x. We denote the length of a binary string x by |x|. The Kolmogorov complexity of x relative to the Turing machine M is

C M (x) = min{|p| | p is a program for x relative to M }.
If U is universal Turing machine, then for every other Turing machine M there exists a string m such that U (m, p) = M (p) for all p, and therefore for every string x, C U (x) ≤ C M (x)+|m|. Thus, if we ignore the additive constant |m|, the Kolmogorov complexity of x relative to U is minimal. We fix a universal Turing machine U , drop the subscript The chain rule (a.k.a. the Kolmogorov-Levin theorem) claims that for all sufficiently long strings x and y, C(x, y) -

U in C U (•),
(C(x) + C(y | x)) ≤ 3(log C(x) + log C(y)).
The mutual information of two strings x and y is denoted I(x : y), and is defined as

I(x : y) = C(x) + C(y) -C(x, y).
The complexity profile of a tuple of strings (x 1 , . . . , x ) is given by the tuple consisting of the complexities of all non-empty subsets of the strings in the tuple, i.e., it is the tuple (

C(x V ) | V ⊆ [ ], V = ∅).
Here x V denotes the subtuple obtained by taking the components with indices in V (for example if V = {1, 2, 7} then x V = (x 1 , x 2 , x 7 )).

Shared secret keys and protocols for secret key agreement

Let k be a positive integer. A k-rounds two-party protocol for secret key agreement uses two computable functions A and B and runs as follows. The first party has as input a string x A and uses private randomness r A , the second party has as input a string x B and uses private randomness r B . We assume that the length of r A (r B ) is determined by x A (respectively, x B ). The protocol consists of the following calculations:

x 1 = A(x A , r A ), y 1 = B(x B , r B , x 1 ) x 2 = A(x A , r A , y 1 ), y 2 = B(x B , r B , x 1 , x 2 ) . . . x k = A(x A , r A , y 1 , . . . , y k-1 ), y k = B(x B , r B , x 1 , . . . , x k ).
The algorithms A and B can handle inputs of different lengths. We also allow them to be partial (i.e., it is possible that the protocol does not converge for some pairs of inputs). Let us fix parameters and δ(n). (We assume is a positive constant and δ(n) is a constant or a slow growing function, e.g., O(log n)). A protocol succeeds with error probability and randomness deficiency δ(n) on a pair (x A , x B ) of n-bit strings if with probability (1 -) over r A , r B ,

A(x A , r A , t) = B(x B , r B , t) def. = z, (1)
and

C(z | t) ≥ |z| -δ(n), (2)
where t = (x 1 , y 1 , . . . , x k , y k ) is the transcript of the protocol. The string z satisfying equation (1) and inequality ( 2) is called a shared secret key output by the protocol on input (x A , x B ). Note that the shared secret key z is a random variable since it depends not only on the inputs x A and x B , but also on the randomness r A and r B .

In words, Alice and Bob start with input strings x A and respectively x B , use private randomness r A , and respectively r B and execute a protocol in which at round i, first Alice sends to Bob the string x i , and next Bob sends to Alice the string y i , and at the end Alice and Bob separately compute with high probability a common string z (equation ( 1)) such that z is random even conditioned by the transcript of the protocol (inequality (2)). Thus, z is secret to an adversary that has observed the protocol and consequently knows the transcript.

The number of rounds in a protocol (parameter k) may depend on the length of the inputs.

I C

Main results

We present here our main results. We first show that there exists a secret key agreement protocol which produces a shared secret key of length equal (up to logarithmic precision) to the mutual information of the inputs, provided the two parties know the complexity profile.

Next we show that no protocol can produce a longer shared secret key. The formal statements are as follows.

Theorem 2 (Lower bound). There exists a secret key agreement protocol with the following property: For every n-bit strings x and y, for every constant > 0, if Alice's input x A consists of x, the complexity profile of (x, y) and , and Bob's input x B consists of y, the complexity profile of (x, y) and , then, with probability 1 -, the shared secret key is a string

z such that, C(z | t) ≥ |z| -O(

Theorem 3 (Upper bound). Let us consider a protocol for secret key agreement, let x A and x B be input strings of length n on which the protocol succeeds with error probability and randomness deficiency δ(n), and let z be the random string that is the shared secret key output by the protocol, i.e., a string satisfying relations (1) and (2). Then with probability at least 1 -O( ), if n is sufficiently large, |z| ≤ I(x

A : x B ) + δ(n) + O(log(n/ ))
, where the constants in the O(•) notation depend on the universal machine, but not on x A and x B .

Theorem 3 establishes the upper bound claimed in the Introduction. Indeed, for any pair of n-bit strings (x, y), suppose that Alice's input x A consists of x and the complexity profile of (x, y) and Bob's input x B consists of y and the complexity profile of (x, y). Note that I(x A : x B ) = + I(x : y), because the length of the complexity profile is bounded by O(log n). Hence, Theorem 3 implies that secret key agreement protocols in which the two parties, besides x and respectively y, are additionally given the complexity profile of their inputs can not produce a secret key that is longer than I(x : y) + O(log n) (provided the randomness deficiency of the key satisfies δ(n) = O(log n)).

Remark. In our secret key agreement protocols, the inputs x A and x B have two components: x A = (x, h A ) and x B = (y, h B ), where the strings x and y are the main components, while h A and h B are short helping strings (for example, containing information about how x and y are correlated). The protocols designed in this paper succeed for all input pairs x A and x B in which h A = h B = (the complexity profile of x and y). In case one or both of h A and h B are not equal to the complexity profile, the protocols still halt on every input, but the outputs may be meaningless. However, the proof of Theorem 2 can be adapted to the situation where Alice and Bob are not given the exact value of the complexity profile of (x, y) but only an approximation of this profile. If Alice and Bob are given upper and lower bounds for each component of the complexity profile of (x, y) with precision ≤ σ, for some integer σ, then with probability 1 -O( ) Alice and Bob agree on a common secret z that is incompressible (i.e., C(z | t) ≥ |z| -O(log(1/ )) where t is the transcript of the protocol), and the length of z is greater than I(x : y) -σ -O(log(n/ )).

3

Secret key agreement for three or more parties

In this section we analyze secret key agreement for 3 parties, which we call Alice, Bob, and Charles. Alice has a string x A , Bob has a string x B , and Charles has a string x C . They also have private random bits r A , respectively r B and r C . They run a k-round protocol. In each of the k rounds, each party broadcasts a message to the other two parties, where the message is a string computed from the party's input string and private random bits, and the messages from the previous rounds. After the completion of the k rounds, each party computes a string. The requirement is that with probability at least 1 -, they compute the same string, and that this string is random conditioned by the transcript of the protocol. Formally, a k-round 3-party protocol for secret key agreement uses three computable functions A, B, C, and runs as follows. The first party has as input an n-bit string x A and uses private randomness r A , the second party has as input an n-bit string x B and uses private randomness r B , and the third party has as input an n-bit string x C and uses private randomness r C . The protocol consists of the following calculations:

t 1 = A(x A , r A ), t 2 = B(x B , r B ), t 3 = C(x C , r C ), t 4 = A(x A , r A , t[1 : 3]), t 5 = B(x B , r B , t[1 : 3]), t 6 = C(x C , r C , t[1 : 3]), t 7 = A(x A , r A , t[1 : 6]), t 8 = B(x B , r B , t[1 : 6]), t 9 = C(x C , r C , t[1 : 6]), . . .          k rounds
Each row corresponds to one round and shows the messages that are broadcast in that round, and we use the notation t[i : j] to denote the tuple of messages (t i , . . . , t j ). We also denote t = t[1 : 3k], the entire transcript of the protocol. The protocol succeeds with probability error and randomness deficiency δ(n) on the 3-tuple input (

x A , x B , x C ) if with probability (1 -) over r A , r B , r C , A(x A , r A , t) = B(x B , r B , t) = C(x C , r C , t) def. = z, (3)
and

C(z | t) ≥ |z| -δ(n).

Definition 4. (1)

For each triple of strings (x 1 , x 2 , x 3 ), we denote by S(x 1 , x 2 , x 3 ) the set of all triples of integers (n 1 , n 2 , n 3 ) that satisfy the following inequalities:

n 1 ≥ C(x 1 | x 2 , x 3 ), n 2 ≥ C(x 2 | x 1 , x 3 ), n 3 ≥ C(x 3 | x 1 , x 2 ), n 1 + n 2 ≥ C(x 1 , x 2 | x 3 ), n 1 + n 3 ≥ C(x 1 , x 3 | x 2 ), n 2 + n 3 ≥ C(x 2 , x 3 | x 1 ).
The constraints defining S(x 1 , x 2 , x 3 ) will be referred as the Slepian-Wolf constraints.

(2) We define CO(x 1 , x 2 , x 3 ) to be the minimal value of n 1 + n 2 + n 3 subject to n 1 , n 2 , n 3 satisfying the Slepian-Wolf constraints. (CO stands for communication for omniscience.)

We show that there exists a protocol that on every input tuple (x A , x B , x C ) produces with high probability a secret key of length

C(x A , x B , x C ) -CO(x A , x B , x C ) -O(log n) (
provided the parties have the complexity profile of the input tuple), and that no protocol can produce a secret key of length larger than

C(x A , x B , x C ) -CO(x A , x B , x C ) + O(log n).
Theorem 5 (Upper bound). Let us consider a 3-party protocol for secret key agreement with error probability , where the number of random bits is bounded polynomially in the input length. Let (x A , x B , x C ) be a 3-tuple of n-bit strings on which the protocol succeeds. Let z be the random variable which represents the secret key computed from the input (x A , x B , x C ) and let t be the transcript of the protocol that produces z. Then, for sufficiently large n, with probability

1 -O( ) we have C(z | t) ≤ C(x A , x B , x C ) -CO(x A , x B , x C ) + O(log(n/ )).

Theorem 6 (Lower bound).

There exists a 3-party protocol for secret key agreement with the following characteristics. For every n, for every tuple (x 1 , x 2 , x 3 ) of n-bit strings, for I C A L P 2 0 1 8

95:10

An Operational Characterization of Mutual Information in AIT every > 0, if Alice's input x A consists of x 1 , the complexity profile of the tuple and , Bob's input x B consists x 2 , the complexity profile of the tuple and , and Charles's input x C consists of x 3 , the complexity profile of the tuple and , then at the end the three parties compute with probability 1 -O( ) a common string z such that

C(z | t) ≥ |z| -O(log(1/ )) and |z| ≥ C(x 1 , x 2 , x 3 ) -CO(x 1 , x 2 , x 3 ) -O(log(n/ )),
where t is the transcript of the protocol.

Remark. Theorem 5 and Theorem 6 remain valid for any constant number ≥ 3 of parties, with a suitable generalization of the omniscience CO(x 1 , . . . , x ), see the full version of the paper.

Communication complexity of secret key agreement

It is of interest to find the communication complexity for the task of finding a shared secret key having the optimal length of I(x : y). We solve this problem in the model of randomized protocols with public random bits, visible to Alice, Bob, and the adversary. This model is obtained by modifying slightly the definition from Section 1.4 (in which the random bits are private): we require that r A = r B = r and we change equation (2

) to C(z | t, r) ≥ |z| -δ(n).
The protocol presented in the proof of Theorem 2 solves the task with communication min(C(x | y), C(y | x)) + O(log n). This protocol can be easily modified to work in the model with public randomness. We argue that within the model with public randomness the communication complexity of this protocol is optimal, up to the O(log n) term. In what follows we assume as usual that Alice is given a string x and Bob is given a string y, and both parties know the complexity profile of (x, y). Theorem 7. Let , δ 1 , δ 2 be arbitrary positive real constants. There is no secret key agreement protocol with public random bits such that for all inputs x and y, 1. the communication complexity of the protocol (the total number of all bits sent by Alice and Bob) is less than (1 -δ 1 ) min{C(x | y), C(y | x)}, 2. Alice and Bob agree with probability > on a common key z such that C(z | t, r) > δ 2 I(x : y), where r is the public randomness and t = t(x, y, r) is the transcript of the protocol.

Our techniques.

It is common for statements in IT (in the Shannon's entropy framework) to have an analogue version in AIT (in the Kolmogorov complexity framework). However, there is no canonical way to translate a result from one setting to the other, and proofs of homologous results in these two frameworks can be drastically different. A textbook example of this phenomenon is the chain rule: it is valid for Shannon's entropy and for Kolmogorov complexity, and the formal expressions of this rule in both frameworks look very similar. However, in Shannon's case this fact is an easy corollary of the definition, while in Kolmogorov's version it requires a nontrivial argument (which is known as the Kolmogorov-Levin theorem). There are more advanced examples of parallel properties (from IT and AIT respectively), where the discrepancy between their proofs is even more striking. This phenomenon manifests itself in this work as well. Our main results are motivated by similar ones in IT, and there is a close resemblance of statements. As discussed above, this is not surprising. In what follows we explain the relation between our proofs and the proofs of similar statements in Shannon's framework.

The positive results (the existence of communication protocols) use constructions that at the high level are akin to those from their IT counterparts [START_REF] Ueli | Secret key agreement by public discussion from common information[END_REF][START_REF] Ahlswede | Common randomness in information theory and cryptography -I: secret sharing[END_REF][START_REF] Csiszár | Secrecy capacities for multiple terminals[END_REF]. We employ a similar intuitive idea -manipulations with "fingerprints" of inputs of appropriate lengths 2 . However, the technical machinery is different. In the AIT framework, for communication-efficient protocols, we need quite explicit constructions, while homologous results in IT are usually proven by choosing random encodings. Our constructions are based on a combination of extractors and universal hashing. Our general protocols are not time-efficient and this is to be expected given the high generality of the type of data correlation in the AIT setting. However, for some particular types of correlation (e.g., for a pair of inputs with a bounded Hamming distance), our protocols can be modified to run in polynomial-time. In this case we use the reconciliation technique from [START_REF] Smith | Scrambling adversarial errors using few random bits, optimal information reconciliation, and better private codes[END_REF][START_REF] Guruswami | Codes for computationally simple channels: Explicit constructions with optimal rate[END_REF][START_REF] Guruswami | Optimal rate code constructions for computationally simple channels[END_REF].

In the negative results (upper bounds for the size of the common secret key, Theorems 2 and 5) the ideas from IT do not help. The reason is that in the AIT framework, the mutual information of various strings is not exactly zero, but only close to zero within some slack terms. The slack terms are small, but during the rounds of a protocol, the errors can accumulate and grow beyond control (for more detail see the discussion of the limits of the "weak" upper bound int he full version of the paper). To overcome this obstacle we come up with a new type of inequalities for Kolmogorov complexity. These inequalities are substantially different from the classic information inequalities used in the analogous results in IT. This technique is based on ideas similar to the conditional information inequalities in [START_REF] Kaced | Conditional information inequalities for entropic and almost entropic points[END_REF][START_REF] Kaced | Conditional information inequalities and combinatorial applications[END_REF]. We believe that this technique can be helpful in other cases, including applications in IT (see the discussion in the full version of the paper).

In the proof of a lower bound for communication complexity (Theorem 7), we use methods specific for AIT, with no apparent parallel in IT. We adapt the technique of bounds for the size of common information that goes back to An. Muchnik and use deep results regarding stochastic strings [START_REF] Kh | The concept of (α, β)-stochasticity in the Kolmogorov sense, and its properties[END_REF][START_REF] Muchnik | Stability of properties of Kolmogorov complexity under relativization[END_REF][START_REF] Razenshteyn | Common information revisited[END_REF], which have not been previously employed in information theory and communication complexity.

Final comments

On time-efficient secret key agreement protocols. The secret key agreement protocol in the proof of Theorem 2 is computable but highly non-efficient. The only slow stage is when Bob reconstructs x given his input string y and the fingerprint of x obtained from Alice. At this stage Bob has to simulate all programs of size C(x | y) until he obtains a string matching the fingerprint. All other stages of the protocol can be implemented in polynomial time (to this end we need to use an effective version of an extractor in the definition of fingerprints; this increases the overhead in communication complexity from O(log n) to poly(log n), but this is still negligible compared to the size of the fingerprint, which is the dominating term in the communication complexity of the protocol; for details see [START_REF] Zimand | Kolmogorov complexity version of Slepian-Wolf coding[END_REF]). We cannot make Bob's computation effective in general, but we can do it for some specific pairs of inputs (x, y). Actually we can make the entire communication protocol fast, if there is a way to communicate x from Alice to Bob so that (i) communication complexity of this stage (and therefore the information revealed to the adversary) remains about C(x | y), and (ii) all computations are performed by Alice and Bob in time poly(n).

2 On the high level this protocol consists of three stages: (i) Alice sends to Bob a suitable "fingerprint" of her input p1(x); (ii) Bob uses y and p1(x) to recover x; (iii) then both Alice and Bob independently compute another fingerprint p2(x), which is used as a common secret key. The construction of the fingerprints guarantees that the adversary (who eavesdrops p1) obtains virtually no information about p2. ) Let Alice get a random line x in the affine plane over the finite field with 2 n elements, and Bob get a random point y on this line. For most inputs of this type we have C(x | y) = n ± O(log n), and there exists a simple way to transfer x from Alice to Bob with communication complexity n (Alice just sends to Bob the slope of her affine line, and Bob draws a line with this slope incident to his point). Thus, we see once again that for this simple example there exists an effective (polynomial-time) communication protocol to agree on common secret key of size ≈ n bits.

Example 2. Let Alice and Bob get n-bits strings x and y respectively, and the Hamming distance between these strings is at most δn for some constant δ < 1/2. For most inputs of this type we have C(x | y) = h(δ)n ± O(log n) and I(x : y) = (1 -h(δ))n ± O(log n), where h(δ) = δ log 1 δ + (1 -δ) log 1 1-δ . Can we transfer x from Alice to Bob with communication complexity h(δ)n + o(n) ? It turns out that such a protocol exists; moreover, there exists a communication protocol with asymptotically optimal communication complexity and polynomial time computations, see [START_REF] Smith | Scrambling adversarial errors using few random bits, optimal information reconciliation, and better private codes[END_REF][START_REF] Guruswami | Codes for computationally simple channels: Explicit constructions with optimal rate[END_REF][START_REF] Guruswami | Optimal rate code constructions for computationally simple channels[END_REF]. Plugging this protocol in our proof of Theorem 3 we conclude that on most pairs of inputs (x, y) of this type Alice and Bob can agree on a common secret key of size (1 -h(δ))n -o(n), with poly-time computations for both parties.

On using our approach for "one-shot" sources. Most known results for secret key agreement in Shannon's framework are proven under the assumption that the input data available to Alice and Bob is generated by i.i.d. or at least stationary ergodic sources. These results can be derived from Theorem 2 and Theorem 3, using the well-known relation between Shannon entropy and Kolmogorov complexity for the above type of sources [START_REF] Ming | Kolmogorov complexity and its applications[END_REF][START_REF] Horibe | A note on Kolmogorov complexity and entropy[END_REF]. But actually Theorem 2 and Theorem 3 apply in more general settings. We can prove similar bounds for random inputs obtained in one shot, without the property of ergodicity. This is useful because in many natural instances of the secret key agreement problem the input data are far from being ergodic, and therefore the classic technique does not apply. For instance, Example 1 and Example 2 discussed above illustrate this situation if we reformulate them in the probabilistic setting (i.e., we introduce the uniform distribution on the set of all valid pairs of inputs). For the probabilistic versions of these examples the matching upper and lower bounds on the size of the common secret key can be easily deduced from Theorem 2 and Theorem 3.

On the error probability. The standard results on secret key agreement deal with the paradigm that the protocol works properly for most randomly chosen inputs (which is typical for the information theory), while in our approach we prove a somewhat stronger statement: for each valid pair of input data the protocol works properly with high probability (which is typical for the theory of communication complexity).

Open problems and acknowledgements

Open Question 1. In Theorem 7 we establish a lower bound on how many bits Alice and Bob must communicate to agree on a common secret key. Our proof is valid only for communication protocols with public randomness. Is the same bound true for protocols with private sources of random bits? Open Question 2. Our communication protocols are randomized. On the other hand they use unusually few random bits, only O(log n). It is natural to ask whether we can get rid of external randomness. We conjecture that for (O(log n), O(log n))-stochastic tuples of inputs the protocol can be made purely deterministic (though it would require very high computational complexity), but this cannot be done in the general case. The proof of this fact likely requires a better understanding of the nature of non-stochastic objects (such as Chaitin's Omega number, [START_REF] Gregory J Chaitin | A theory of program size formally identical to information theory[END_REF], see also [START_REF] Kh | The concept of (α, β)-stochasticity in the Kolmogorov sense, and its properties[END_REF] and [23]).

  and denote the complexity of x by C(x). Similarly to the complexity of x, we define the complexity of x conditioned by y as C(x | y) = min{|p| | U on input p and y prints x}. We list below a few basic facts about Kolmogorov complexity and introduce some notation: For every string x, C(x) ≤ |x| + O(1), because a string x is trivially described by itself. (Formally, there is a Turing machine M that, for every x, on input x prints x.) Using some standard computable pairing function •, • that maps pairs of strings into single strings, we define the complexity of a pair of strings by C(x, y) = C( x, y ). Then we can extend this notation to tuples of larger arity. We use the convenient shorthand notation a ≤ + b to mean that a ≤ b + O(log n), where n is a parameter that is clear from the context and the constant hidden in the O(•) notation only depends on the universal machine U . Similarly, a ≥ + b means a ≥ b -O(log n), and a = + b means (a ≤ + b and a ≥ + b).

  log(1/ )) and |z| ≥ I(x : y) -O(log(n/ )), where t is the transcript of the protocol. Moreover, the communication consists of a single message sent by Alice to Bob of length C(x | y) + O(log(n/ )), Alice uses O(log(n/ )) random bits, and Bob does not use any random bits.

Example 1 .

 1 (Discussed in Introduction, p. 2.

Acknowledgements

We are grateful to Bruno Bauwens for his insightful comments. We thank Tarik Kaced for attracting our attention to [5].

by ANR-15-CE40-0016-01 RaCAF grant.