E Bourgeois

N Jidenko

M Alonso

J P Borra

DBD as a post-discharge bipolar ions source and selective ioninduced nucleation versus ions polarity

DBD as a post-discharge bipolar ions source and selective ioninduced nucleation versus ions polarity

Introduction

An increasing number of on-line industrial processes and air-filtration devices are based on dielectric barrier discharge (DBD) [START_REF] Kogelschatz | Atmospheric-pressure plasma technology Plasma[END_REF]. Ions produced by DBD have to be taken into account in post-discharge since they lead to surface and aerosol charging that can induce powder coagulation and deposition with subsequent clogging as well as accidental arcing [START_REF] Cross | Electrostatics: Principles, Problems and Applications[END_REF].

Besides, gaseous ions sources such as flames, radioactive materials or more user-friendly atmospheric pressure electrical discharges are used in industrial processes, for instance to neutralize charged surfaces or powders. They are also required for unipolar or bipolar particles charging that constitutes the first step of many aerosols processes (charge distribution measurements, electrostatic precipitation, coating, Coulombian coagulation, etc.) since the kinematics of charged particles is controlled by electrostatic forces [START_REF] Cross | Electrostatics: Principles, Problems and Applications[END_REF], [START_REF] Borra | Charging of aerosol and nucleation in atmospheric pressure electrical discharges Plasma[END_REF]. Aerosols can be charged by ions collection when they are injected in the gap of an electrical discharge, where they undergo combined diffusion and field charging in high ions densities [START_REF] Biskos | Monte-Carlo simulation of unipolar diffusion charging for spherical and non-spherical particles[END_REF]. However many charged particles are lost by electro-collection. Once collected on electrodes, they can destabilize the discharge. Besides, the charge reached by a particle by field charging depends on its diameter and shape [START_REF] Unger | Unipolar field charging of particles by electrical discharge: effect of particle shape[END_REF]. Diffusion charging in post-discharge, for example in post-DBD, is interesting to avoid these drawbacks, all the more since field charging is not efficient for particles smaller than 100 nm.

Moreover, when a DBD is used to produce nanoparticles, either as a standard aerosol generator or as a nano-material production system, the apparent production rate may depend on post-discharge electrostatic collection of nano-particles charged by ion diffusion in post-discharge.

The charge reached by particles undergoing diffusion charging depends on both Ni. product (Ni:

ions density, : transit time of particles in this density) and ions electric mobility. The objective of this work is thus to characterize these parameters in post-DBD. DBD can be considered as a post-discharge bipolar ions source. It is obtained by applying an AC voltage between electrodes covered by dielectrics materials. In air at atmospheric pressure, discharge filaments are homogeneously distributed on dielectric surface. It has to be noticed that throughout this paper, the expression "discharge filament" includes all phases from Townsend pre-breakdown avalanches to streamer, surface discharge and quenching. During filaments development, positive ions settle on dielectric surface at one side of the filament and negative ions and electrons at the other. The total electric field in gas depends on the electric field created by charges deposited on surface, on applied voltage and on transient space charge during the development of filaments [START_REF] Gibalov | The development of dielectric barrier discharges in gas gaps and on surfaces[END_REF], [START_REF] Eliasson | Modeling and applications of silent discharge plasmas[END_REF]. After a filament and before the change of polarity, the electric field created by surface charges deposited by the filament decreases the total electric field. On the contrary, during the following half-period, these surface charges contribute to increase the total electric field, which explains why filaments repeat at the same places at a frequency that is twice the frequency of the applied voltage.

After the filament has reached the dielectric surface, surface electric field repels ions of same polarity as surface charges in the gap. Each filament can thus be considered as a source of ions [START_REF] Xu | Ion composition of expanding microdischarges in dielectric barrier discharges[END_REF]. Some remanent ions are maybe also produced in avalanches outside filaments [START_REF] Bernecker | Hexagonal and Honeycomb structures in Dielectric Barrier Discharges[END_REF]. These subcritical avalanches would not be detected electrically as independent current pulses because of a number of electrons smaller than 10 8 , inferior to Meek's criterion for the transition from pre-breakdown Townsend avalanches to streamer development [START_REF] Gibalov | The development of dielectric barrier discharges in gas gaps and on surfaces[END_REF], [START_REF] Meek | A theory of spark discharge[END_REF].

Then ions can undergo local collection just after production -within ns to µs. They may also be collected during their transit inside DBD or in post-discharge, that both last from ms to tens of ms. Ions losses inside DBD and in post-discharge happen by ions recombination, diffusion, thermophoresis and electro-collection. Electro-collection in DBD is due to both external field (Laplacian and surface fields) and to self-repulsion, while it is only due to electrostatic self-repulsion in post-discharge [START_REF] Alonso | A numerical study of the influence of ion-aerosol mixing on unipolar charging in a laminar flow tube[END_REF].

Contrary to ions, electrons produced in filaments or in avalanches outside filament are all collected on surfaces soon after their production, because of their about 400 times higher electric mobility. Ions currents in post-DBD (hereafter referred as post-discharge ions currents), resulting from ions production and losses, are controlled by electrical, hydraulic and thermal parameters as well as by the geometries of DBD reactor and post-discharge tube. The energy per filament and the related local ions flux from each filament are determined by gas composition and DBD reactor design (dielectric material and thickness, gap length) [START_REF] Gibalov | The development of dielectric barrier discharges in gas gaps and on surfaces[END_REF]. From 1 kHz to 60 kHz, it does not evolve markedly with voltage amplitude or frequency once filaments are homogeneously distributed on dielectric material surface [START_REF] Jidenko | Electrical characterisation of microdischarges produced by dielectric barrier discharge in dry air at atmospheric pressure[END_REF], [START_REF] Petit | Electrical characterization of gas discharges in relation with their properties using a numerical treatment: application to DBD[END_REF]. So voltage amplitude controls the number of identical ions sources per surface unit in a halfperiod, while frequency determines the number of ions sources per half-period and so per time unit. Losses inside DBD depend on transit time inside discharge, on applied voltage amplitude and frequency (controlling electro-collection, [START_REF] Jidenko | Kinematics of charged nanometric particles in silent discharge[END_REF]) and on dielectric material temperature and humidity (influencing surface polarization). Post-DBD losses depend on tube geometry, gas flow rate and ions density and mobility [START_REF] Alonso | A numerical study of the influence of ion-aerosol mixing on unipolar charging in a laminar flow tube[END_REF].

This study has been carried out in air, with fixed DBD reactor geometry, since it is representative of many particles chargers functioning conditions. At first, overpressure, frequency, gas flow rate and post-DBD tube material have been chosen by measuring ions post-discharge density and mobility for different functioning conditions. As ions electric mobility affects losses, positive and negative ions mobility spectra at different electrode temperatures are also presented. Then the influence of the number of filaments per surface unit during a half-period on ions production and losses is studied. A change in the number of filaments per time and surface unit modifies DBD reactor temperature. Hence, respective impacts of filaments numbers and temperature on production and losses are analysed in terms of polarization of dielectric surfaces to account for ions losses in DBD or potential ions production in avalanches outside filaments.

Experimental set-up

DBD reactor is made of two rectangular metal electrodes (width: 10 mm, length: 30 mm), covered by 0.55 mm thick alumina plates (figure 1(a)). Inter-dielectric gap is 1 mm and gas injection section is 13 mm wide and 1 mm high. It corresponds to gas velocity ranging from 1.3 to 14.7 m.s -1 and transit time inside DBD reactor from 22.4 to 2.0 ms when flow rate varies from 1 to 11.5 lpm. The gas injected in DBD is dry and filtered air. A sinusoidal voltage is applied between electrodes by a high voltage generator. The peak-to-peak amplitude (Vpp) and frequency (F) are determined using a high voltage probe and an oscilloscope. The current is measured through a 25  resistor. At frequencies higher than 1 kHz, discharge electrical power is calculated as the mean of the product between applied voltage and discharge current on an entire number of periods. At 50 Hz, Lissajous' method is used to determine power.

Positive and negative ions currents blown from DBD (referred as post-discharge ions currents) are separated by an electrostatic precipitator (ESP), made of two metal plates (380  26 mm) with a 10 mm gap polarised at 80 V. Indeed, preliminary measurements have shown that this voltage was sufficient to collect entirely on one of the two plates an unipolar ions current produced by corona discharge and corresponding to an ions density of 10 7 cm -3 , that is the maximal ions density observed for one polarity during post-DBD measurements. Ions currents collected on each plate are then measured by two electrometers, one of both being polarized at 80 V (figure 1(a)). Discharge effluents are transported to the ESP using a metal tube (inner diameter: 4 mm). To cool them down to 70 °C before ESP entrance, 15 lpm of dry filtered air is injected. Transit time of ions in post-discharge has the same order of magnitude as inside the DBD, from 7 to 69 ms for gas flow rates from 1 to 11.5 lpm, as depicted in captions.

Leakage currents are measured by electrometers between ESP metal plates when electrical discharge is off, due to surface electric conduction on PVC walls separating metal plates. For defined voltage, these conduction currents can be reduced by water desorption with hot gas. 1 to 15 pA leakage currents still existed during measurements of post-discharge ions currents. Hence, post-discharge ions currents were evaluated subtracting the leakage currents. Electric mobility spectra are determined using a mobilimeter, with 500 lpm sheath airflow. Ions transit time in metal tube between DBD reactor and mobilimeter is about 30 ms at 3 lpm. Mobility calculated from sheath airflow rate and voltage applied between mobilimeter electrodes is converted into reduced mobility at 20 °C and 1013 mbar using the following expression: Absolute values of electric mobilities cannot be used for chemical composition determination from mass calculation since the cross-sections of ions clusters are not known. However, the objective in this paper is to deal qualitatively with the evolution of ions clusters composition through the number of peaks and their relative positions and intensities. The influence of the electric field on the mobility for reduced field above 5 Td [START_REF] Buryakov | Coefficient of Ion Mobility Versus Electric Field Strength Dependence in Gases[END_REF] has thus been neglected here.

DBD reactor electrode temperature is displayed by a thermocouple, since variations of electrode temperature give an image of variations of dielectric surface temperature.

Conditions for ions extraction and post-discharge measurements

Results presented in this paper to deal with ions production and losses concern post-discharge ions currents. As a matter of fact, measured ions current corresponds to the difference between the current of ions produced by the dischargewhich is proportional to the number of ions produced by time unitand the currents of ions lost inside DBD and in post-discharge. Ions densities are derived from ions currents, gas flow rate and ions unit charge.

Overpressure in DBD reactor

Mobility measurements at 3 lpm induce a 300 mbar overpressure in DBD reactor due to mobilimeter inlet slit width.

Measurements of post-discharge ions currents have been performed at different overpressure between 0 and 90 mbar. As ions currents were higher at low overpressure (positive and negative currents decrease of about 25 % when overpressure in DBD reactor increases from 2 to 90 mbar), results presented here have been obtained at an overpressure in DBD reactor of 10 mbar, set independently of gas flow rate by placing a pump in air circuit after the ESP.

Frequency

Post-discharge ions currents have been measured at several frequencies from 50 Hz to 60 kHz (Vpp = 21 kV, Q = 1 lpm). At 50 Hz or 1 kHz, no ions current is detected (figure 1(b)), which means that ions densities are lower than 10 4 cm -3 , in consideration of the lowest current value that can be detected by electrometers. Ions currents start being detected at 25 kHz and increase between 25 and 60 kHz, up to corresponding ions densities in the order of 10 7 cm -3 .

Growth of ions currents with frequency can partly be explained by an increase in the number of ions sources per time and surface units. But this is not the only explanation since electrical discharge power, which is proportional to the number of identical discharge filaments per time and surface unit, is multiplied by about 2.5 between 25 and 60 kHz, while positive and negative ions currents are multiplied by 5 (at identical electrode temperatures).

The increase in ions currents also results from lower electro-collection at high frequency. Indeed, at low frequency ions have more time to derivate through one of the electrodes during a half-period. The frequency below which all ions are collected in DBD -on condition that their transit time is superior to one period of AC voltage -can be estimated to 30 kHz considering that ions electric mobility is 2 cm 2 V -1 s -1 and that electric field amplitude in the gap is 5 10 5 Vm -1 [START_REF] Jidenko | Kinematics of charged nanometric particles in silent discharge[END_REF]. The critical frequency calculated for ions collection in DBD is thus superior to the observed one. It can be due to the fact that electric field in gap differs from the value considered for calculation because of the electric field created by surface charges. Ions detected at frequencies lower than 30 kHz could also be produced by filaments located just before the DBD reactor outlet, with related reduced electro-collection probability.

Hence, post-discharge measurements have been performed at a frequency of 60 kHz. At this frequency, electrode temperature remains inferior to 260 °C and a reduction of gas temperature below 70 °C before ESP entrance by fast dilution is possible.

Gas flow rate

Post-discharge ions currents have been measured for flow rates from 1 to 11.5 lpm at voltages between 15 and 21 kV, for which filaments are homogeneously distributed on dielectric surface [START_REF] Chirokov | Self-Organization Of Microdischarges In DBD[END_REF]. Measurements have been performed at a constant electrode temperature of 40 °C (figure 2). Maximal positive and negative currents are reached at a given voltage by modifying flow rate between 1 and 11.5 lpm. They remain in the range 40 to 50 pA for positive currents and -30 to -40 pA for negative one. So low flow rate corresponds to minimal dilution and maximal ions densities. Moreover, it is favourable to post-discharge diffusion charging since the Ni. product is maximal. The influence of the number of filaments per time and surface unit on post-discharge ions currents has thus been studied at 1 lpm (cf. §5.). It can also be observed on figure 2 that below 4 lpm, post-discharge ions currents strongly increase with voltage while at higher flow rates, currents dependence on voltage is weaker.

This modification of post-discharge ions currents indicates that 4 lpm probably corresponds to the transition between laminar and turbulent flow regimes in at least some parts of the DBD reactor, (probably close to entrance and exhaust gas pipes), despite Reynolds number smaller than 2000. Indeed, shrinking in gas injection section at DBD reactor entrance and outlet as well as high temperature gradients between gas and dielectric surfaces are not taken into account in Reynolds calculation. Above 4 lpm, growing turbulences in DBD reactor facilitate ions collection on polarized surfaces by affecting ions densities profiles. Indeed, in case of turbulent flow regime, ions are permanently redistributed by turbulences in the volume of collection near dielectric surfaces instead of oscillating around a straight line in the gas. Total polarized surface and related field modifications are stronger at high voltage. Hence, the growth of the number of ions sources per time and surface unit with voltage is certainly compensated by a more efficient turbulent electro-collection, as supported by the quasi-constant ions currents observed in turbulent regime whatever the voltage is (for Q  4 lpm).

Outlet tubes material

Preliminary mobility measurements have been performed to choose outlet tubes material. With clean metal tubes, to prevent desorption from tubes wall, continuous spectra between 0.4 and 1.7 cm 2 V -1 s -1 are observed. On the contrary, when outlet tubes are made of polyethylene (PE), positive ions mobility spectra are composed of well-defined peaks situated at mobilities lower than 0.7 cm 2 V -1 s -1 (figure 3). Modifications of positive spectra, indicating that selective condensation on positive ions has occurred, are also observed when outlet tubes are made of polyvinyl chloride (PVC), polyamid or norprene  . However, no modification appears when polytetrafluoroethylene (PTFE) tubes are used. Negative ions mobility spectra are less dependent on tubes material: with polymer or metal tubes spectra are composed of well-resolved peaks, with the same modal values, only the relative intensities of peaks change with tube material.

This phenomenon is certainly due to the emission of vapours by heated polymer tubes that condensate preferentially on positive ions. Well-resolved peaks observed in positive spectra result from the existence of stable cluster sizes with particular number of adsorbed molecules. This selective ioninduced was first observed in [START_REF] Wilson | On the comparative Efficiency as condensation Nuclei of Positively and Negatively Charged Ions[END_REF] and selective ion-induced nucleation of organic vapours on positive ions has already been described in [START_REF] Adachi | Experimental studies of ion-induced nucleation[END_REF] and [START_REF] Seto | Size and sign effect on the ion induced nucleation[END_REF].

As the presence of polymer tubes in post-discharge affects ions chemical composition, the influence of filaments number per surface unit during a half-period and thermal effects on ions densities and mobilities have been studied using metal post-DBD tubes.

Ions electric mobility

Ions losses by electro-collection inside DBD and by electrostatic self-repulsion in post-DBD tubes depend on ions electric mobility. That is why the evolutions of positive and negative ions mobility spectra have been measured at Vpp = 20 kV and Q = 3 lpm, during the initial thermal evolution of DBD reactor (figure 3). Indeed, when the discharge is on, discharge filaments deposit energy on dielectric surfaces so electrode temperature increases from ambient temperature to a thermal equilibrium temperature depending on functioning conditions.

To deal with the evolution of ions chemical composition with temperature, reduced mobility spectra at 20 °C and 1013 mbar are presented.

Positive ions keep the same reduced mobility range (from 0.4 to 1.7 cm 2 V -1 s -1 ) between ambient and equilibrium temperatures. However the shape of positive spectra evolves: at low temperatures a broad massif is observed (width at half-height: about 0.6 cm 2 V -1 s -1 ), while at higher temperatures better resolved peaks appear at 0.85, 1.24 and 1.58 cm 2 V -1 s -1 (width at half-height of the peak at 0.85 cm 2 V -1 s -1 : 0.15 cm 2 V -1 s -1 ). On the contrary, negative ions reduced mobility spectra contain well-resolved peaks at any temperature. For electrode temperatures lower than about 100 °C, there is only one peak at 1.69 cm 2 V -1 s -1 . At higher temperatures this peak does not exist and several peaks are observed below 1.3 cm 2 V -1 s -1 . In different flow rate conditions, only one peak situated at about 1.7 cm 2 V -1 s -1 has been observed at electrode temperatures between 190 and 210 °C.

Ions electric mobility is determined by their composition and by clustered molecules composition and number. The drop in negative ions reduced mobility occurring around an electrode temperature of 100 °C could be related to the fact that at low temperatures discharge effluents are mainly composed of ozone, while at high temperatures Nitrogen oxides predominate. Indeed, the transition between O3 and NOx occurs for an electrode temperature around 90 °C [START_REF] Odic | 1999 Electrical discharges for environmental purposes: fundamentals and applications[END_REF]. Both chemical and mobility spectra transitions occur at similar electrode temperature. So the drop in mobility at higher temperatures is probably related to a change in the chemical composition of negative ions or of neutral species clustered on negative ions. The fact that at other flow rates a peak at about 1.7 cm 2 V -1 s -1 has been observed around 200 °C indicates that it is rather condensation on negative ions existing at low temperatures which is modified when electrode temperature exceeds 100 °C. Over 190 °C, conditions are probably not favourable to this condensation anymore, either because neutral species that condensate on negative ions are not produced over 190 °C or because they are not saturated anymore for ion-induced nucleation.

So mobility measurements have shown that modifications in negative ions reduced electric mobility could affect post-discharge losses and thus contribute to the evolution of post-discharge negative ions current with temperature (even if it is probably not the dominant effect, cf. 5.3.4). But changes in reduced electric mobility cannot explain positive ions current growth during DBD reactor thermal evolution (figure 5), since positive ions reduced mobility range and related post-DBD losses by self-repulsion are not affected by temperature.

To sum up, vapours emitted by hot polymer tubes preferentially condensate on positive ions (cf. 3.4), while discharge effluents seem to condensate preferentially on negative ions as suggested by the transitions of negative ions mobility spectra with temperature, which controls the chemical composition of discharge effluents.

Influence of the number of filaments per surface and time unit and of electrode temperature on post-discharge ions currents

Method

At fixed frequency, the number of filaments per time and surface unit mainly depends on applied voltage. That is why positive and negative post-discharge ions currents have been measured at constant flow rate (1 lpm) for different peak-to-peak voltages from 14 to 21 kV, and at related equilibrium electrode temperatures (figure 4). But a change in voltage also leads to an evolution of the electrode temperature reached at thermal equilibrium. When the number of filaments per surface and time unit is higher, the power flux received by dielectric materials increases and they become hotter. For instance, at 1 lpm, the electrode equilibrium temperature is 105 °C at 14 kV and 253 °C at 21 kV. As temperature is likely to influence ions production and losses, the impact of filaments number has first been studied at constant electrode temperature (figure 4). Then consequences of a temperature increase have been determined at constant number of filaments per time and surface unit (fixed frequency and voltage), during DBD reactor thermal evolution from ambient temperature to equilibrium temperature (figure 5).

Results

Influence of the number of filaments per time and surface unit at related equilibrium temperatures:

Both positive and negative currents increase with voltage amplitude (figure 4). The slope of the curves representing currents as a function of voltage increases more markedly above 15 kV to 16 kV (Telectrode from 132 to 153 °C). The increase in positive current between the initial plateau, from 14 to 16 kV, and 21 kV is stronger than the increase in negative current (e.g. with positive current multiplied by 3.

Influence of the number of filaments per time and surface unit at constant electrode temperature (Telectrode = 40 °C, whatever the number of filaments per time and surface unit is):

For peak-to-peak voltages between 14 and 21 kV, post-discharge ions currents have been measured at the beginning of reactor thermal evolution, for an electrode temperature of 40 °C. Positive and negative post-discharge currents increase with voltage at constant electrode temperature (figure 4). Hence, post-discharge currents are related to the number of filaments per time and surface unit, as detailed in 5.3.1. The slopes of the curves representing positive and negative currents as a function of peak-to-peak voltage increase around 16 kV, which can be related to the homogeneous distribution of discharge filaments on dielectric surface above this voltage.

Moreover, it appears that at a given voltage, post-discharge positive and negative currents measured at 40°C are systematically lower than currents measured at equilibrium temperature. This effect of electrode temperature on currents at fixed voltage is detailed below.

Influence of electrode temperature:

For any voltage and flow rate, an increase in positive postdischarge current happens during thermal evolution of DBD reactor between ambient temperature and thermal equilibrium temperature (figure 5). Positive current evolves from ambient temperature (for instance at Vpp = 17.3 kV and Q = 4.2 or 8.7 lpm) or remains constant until 110 °C and then increases (for instance at Vpp = 21.3 kV and Q = 4.2 lpm). Negative current evolution only starts over 110 °C. Moreover, positive ions current growth with temperature is stronger than negative ions current one. For instance, at Vpp = 26.6 kV and Q = 4.2 lpm, between 110 and 220 °C, positive current is multiplied by 4, and negative current by 1.8.

This thermal effect on post-discharge ions currents has been confirmed since similar currents evolutions are observed by injecting hot gas in DBD so as to provoke an increase in electrode temperature (figure 5).

It has to be stressed that concerning measurements performed for different voltages at related equilibrium temperatures, the increase in currents with voltage becomes stronger above 15 kV to 16 kV (Telectrode from 132 °C to 153 °C). Since in the case of measurements at equilibrium temperature the effect of temperature cumulates with the effect of filaments number per time and surface unit, it is consistent with the evolutions observed with electrode temperature at fixed voltage.

Discussion

Increases in post-discharge ions currents with the number of filaments by time and surface unit and electrode temperature could be related to an increased ions production, by filaments or by avalanches outside filaments. They also can be due to decreased losses, inside DBD or in post-discharge. These different hypotheses are examined below.

Ions production Ions production by filaments:

The increase in post-discharge currents observed between 14 and 21 kV at low flow rate and for an electrode temperature of 40 °C (figure 4) can in part be explained by the increase in the number of filaments, considered as ions sources, per time and surface unit. Electrical power is representative of the number of filaments insofar as the energy of each filament is almost independent of voltage. But from 14 to 21 kV, it is multiplied by 2.8 while positive and negative postdischarge currents are multiplied by about 7. So the increase in ions production by filaments only accounts for about 40 to 50 % of the growths of post-discharge ions currents with voltage. Another factor has to be considered to explain the totality of the evolution. Gas temperature increases during thermal evolution of the DBD reactor, which reduces gas density. Consequently, the threshold applied voltage to trigger the development of a filament diminishes (cf. following paragraph), which leads to a decrease in electrical power. However, temperature has no noticeable effect neither on the amount of charge per filament nor on the number of filaments per time and surface unit. Hence, the evolution of positive and negative post-discharge ions currents with temperature cannot be related to a variation of the amount of ions produced by discharge filaments.

So a modification in the number of ions produced by all the filaments only partly explains the increase in post-discharge ions currents with voltage. Besides, the increase in electrode temperature has no effect on the production of ions by all the filaments. But an evolution of voltage or electrode temperature affects dielectric surface polarization. On the one hand, it may increase the number of ions produced by avalanches outside filaments (cf. following paragraphs) and on the other hand it reduces losses inside DBD reactor (cf. 5.3.2). Surface polarization: When voltage or temperature increase, the reduced electric field created in the gap by charges deposited on surfaces at both sides of a filament (which repels ions from polarised surfaces) becomes higher, especially after the junction of the filament with the surface of the dielectric material. Indeed, as the number of filaments per surface unit increases with voltage, filaments get closer from one another and surface charges deposited by a filament can contribute to increase the reduced electric field on the axis of surrounding filaments. The influence of temperature on polarization is probably related to a decrease in alumina surface conductivity [START_REF] Caldararu | Electrical conductivity of -Al2O3 at atmpospheric pressure under dehydrating/hydrating conditions[END_REF] that leads to slowest radial spreading of surface charges from each filament on dielectric material and thus to a reinforcement of reduced electric field on its axis before the change of polarity.

The reinforcement of the reduced field on the axis of each filament with voltage or temperatureafter the junction of the filament with the dielectric material surface and before the change of polarityaffects post-discharge ions currents. Indeed, it potentially increases the production of ions by avalanches outside filaments (cf. following paragraph) or reduces losses inside DBD reactor (cf. 5.3.2). Ions production by avalanches outside filaments: Higher surface potential induced by increased voltage or temperaturecombined with higher maximal laplacian field in the gap in case of increased voltage enhances the probability of development of avalanches around filaments. They could contribute to ions production without being detected with electrical measurements as independent pulses, due to a number of electrons smaller than 10 8 , and thus inferior to Meek's criterion for the transition from prebreakdown Townsend avalanches to streamer development [START_REF] Meek | A theory of spark discharge[END_REF].

An evolution of the reduced electric field on the axis of each filament not only increases the probability of ions production by avalanches outside filaments, but also reduces losses inside DBD (cf. 5.3.2).

Losses by electro-collection inside DBD:

Ions electro-collection inside DBD -both around the filament just after their production and during their post-production transit in the DBD gap -is affected by the modifications of surface potential related to voltage or temperature increases.

Indeed, as the reduced electric field created in the gap by the polarization due to charges deposited on surface is reinforced, ions approaching dielectric surface after the junction of the filament with the surface of the dielectric material are more strongly repelled in the gap [START_REF] Xu | Ion composition of expanding microdischarges in dielectric barrier discharges[END_REF]. Recollection of ions around the filaments where they have been produced is thus reduced at high voltage or electrode temperature.

Moreover, the modification of reduced field on the axis of each filament affects electro-collection during ions transit inside DBD reactor. However, this analysis does not allow one to conclude about the sense of variations of these losses with dielectric surface polarization. Hence, the increase in post-discharge ions currents with voltage and temperature are partly related to a decrease in losses inside DBD, just after ions production by a discharge filament and maybe during their transit inside DBD reactor.

Post-discharge losses:

These losses are not affected by a change in voltage. Indeed, at constant electrode temperature, gas temperature slightly varies with voltage, but corresponding modifications in post-discharge losses do not exceed 5 %.

The evolution of ions currents with temperature cannot be explained by modifications of losses in post-discharge tubes either. The increase in electrode temperature during DBD reactor thermal evolution leads to an increase in gas temperature and thus in ions diffusion coefficients. So losses by diffusion increase with electrode temperature. Recombination between positive and negative ions diminishes with temperature but this phenomenon can be neglected here [START_REF] Kossyi | Kinetic scheme of the non-equilibrium discharge in nitrogen-oxygen mixtures Plasma Sources[END_REF]. At constant reduced electric mobility, losses by electrostatic repulsion do not depend on temperature [START_REF] Kasper | Electrostatic dispersion of homopolar charged aerosols[END_REF]. Moreover, the range of positive ions reduced electric mobility does not evolve with temperature (figure 3). A drop in negative ions reduced electric mobility is observed around 100 °C, which corresponds to the temperature after which negative current starts increasing. However, except around ambient temperature, net space charge in postdischarge is positive. So negative ions do not undergo electrostatic losses and the thermal evolution of negative ions current is probably not due to the modification of their electric mobility.

As a conclusion, evolutions of post-discharge losses cannot justify the increase in ions currents in post-discharge with voltage or electrode temperature.

To sum up, the increase in post-discharge ions currents with voltage is partly related to an increase in the number of discharge filaments by time and surface unit and thus in the quantity of ions produced by all the filaments. On the contrary, electrode temperature does not affect the number of ions produced by filaments. Evolutions of post-DBD losses cannot explain the increase in post-discharge ions currents with voltage or electrode temperature. So the observed evolutions of post-discharge currents are related to the reinforcement of the reduced electric field on the axis of each filament after the junction of the filament with the dielectric material surface and before the change of polarity with high voltage or temperature. On the one hand it may increase the number of ions produced in avalanches outside filaments and on the other hand it reduces losses inside DBD reactor.

Conclusions

Conditions for ions extraction from DBD and for post-discharge measurements were experimentally defined in this work. Ions are extracted from DBD at high frequency (25 kHz) both because of reduced electro-collection and increased number of discharge filaments per time unit. Moreover, highest ions densities are obtained at low gas flow rate (1 lpm).

Mobility measurements have shown that in the range of moderate saturation ratios experienced here selective nucleation of vapours emitted by heated polymer tubes occurs only on positive ions while discharge effluents seem to condensate preferentially on negative ions. Indeed, with clean metal tubes a drop in negative ions reduced mobility is observed around 100 °C, provoked by a change in the chemical composition of ions or of molecules condensed on ions. This phenomenon is probably related to a transition between O3 and NOx happening in electrical discharge effluents for an electrode temperature around 90 °C. Positive ions conserve the same range of mobility when DBD reactor temperature increases, but the distribution of population of positive clusters is modified, with the appearance of wellresolved peaks at high temperature.

The impact on post-discharge ions currents of dielectric surface polarization, influencing ions collection inside DBD or ions production outside filaments by small avalanches -not detected electrically as independent pulses -, has also been highlighted. As a matter of fact, at low flow rate (1 lpm), the increase in post-discharge ions currents with the number of filaments per surface and time unit is both due to the growing number of discharge filaments per time and surface unit and to the reinforcement of the reduced electric field on the axis of filaments before the change of polarity. A growth in temperature also provokes an increase in post-discharge ions currents, due to strengthen reduced electric field on filament axis after the junction of the filament with the surface of the dielectric material. At higher flow rates (Q  4 lpm), probably corresponding to the development of local turbulences in DBD reactor, the evolutions of post-discharge ions currents with voltage are not anymore monotonous. Finally, maximal ions densities are obtained at high frequency (60 kHz), high voltage (Vpp = 21 kV), low flow rate (1 lpm) and related thermal equilibrium electrode temperature (253 °C). In these conditions ions densities up to 3.3 10 7 cm -3 for positive ions and 2.4 10 7 cm -3 for negative ions are reached, leading to Ni. products over 10 6 cm -3 s, sufficient for aerosols bipolar diffusion charging in post-discharge [START_REF] Hinds | Aerosol Technology, Properties, Behaviour, and Measurement of Airborne Particles[END_REF].

Figure 1 :

 1 Figure 1: (a) Experimental set-up; (b) Influence of frequency on post-discharge ions currents (tpost-DBD = 55 ms, Vpp = 21 kV, Q = 1 lpm, Preactor = 10 mbar, at 50 Hz and 1 kHz, Telectrode = 20 °C, at 25 kHz and 60 kHz, Telectrode = 143 °C)

Figure 2 :

 2 Figure 2: Evolution of positive and negative post-discharge ions currents with gas flow rate, at constant electrode temperature (40 °C) (tpost-DBD from 7 to 55 ms, F = 60 kHz, Vpp from 15 to 21 kV, Preactor = 10 mbar)

Figure 3 :

 3 Figure 3: Influence of electrode temperature and post-DBD tubes material on ions electric mobility (tpost-DBD = 28 ms, F = 60 kHz, Vpp = 20 kHz, Q = 3 lpm, Preactor = 300 mbar, spectra obtained during DBD reactor thermal evolution from ambient temperature to equilibrium temperature)

  3 and negative one by 2.8 between 16 and 21 kV).

Figure 4 :

 4 Figure 4: Influence of voltage on positive and negative ions currents in post-discharge, at Telectrode = 40 °C and at equilibrium temperature corresponding to each voltage (tpost-DBD = 69 ms, F = 60 kHz, Q = 1 lpm, Preactor = 10 mbar)

Figure 5 :

 5 Figure 5: Influence of electrode temperature on positive and negative post-discharge ions currents during DBD reactor thermal evolution from ambient temperature to equilibrium temperature (tpost-DBD from 9 to 55 ms, F = 60 kHz, Vpp from 17.3 to 26.6 kV, Q from 1 to 8.3 lpm, Preactor = 10 mbar)

Aknowledgements

The authors thank RAMEM company for providing calibrated mobilimeter and financial support of a part of this study.


René Schott
email: schott@loria.fr

G Stacey Staples
email: sstaple@siue.edu

Reductions in Computational Complexity Using Clifford Algebras

Keywords: AMS subject classification: 68Q15, 05C38, 60B99, 81P68, 05C50 Hamiltonian cycles, traveling salesman problem, longest path, NP-hard, NP-complete, cycle cover, set packing problem, set covering problem, matrix permanent, quantum computing

A number of combinatorial problems are treated using properties of abelian nilpotent-and idempotent-generated subalgebras of Clifford algebras. For example, the problem of deciding whether or not a graph contains a Hamiltonian cycle is known to be NP-complete. By considering entries of Λ k , where Λ is an appropriate nilpotent adjacency matrix, the k-cycles in any finite graph are recovered. Within the algebra context (i.e., considering the number of multiplications performed within the algebra), these problems are reduced to matrix multiplication, which is in complexity class P. The Hamiltonian cycle problem is one of many problems moved from classes NP-complete and ♯P-complete to class P in this context. Other problems considered include the set covering problem, counting the edge-disjoint cycle decompositions of a finite graph, computing the permanent of an arbitrary matrix, computing the girth and circumference of a graph, and finding the longest path in a graph.

Introduction

Clifford methods have already been applied to problems in computer vision [START_REF] Lasenby | New geometric methods for computer vision[END_REF] and automated geometry theorem proving [START_REF] Li | Clifford algebra approaches to automated geometry theorem proving, Mathematics Mechanization and Applications[END_REF]. In work having applications to computer vision, Clifford algebra methods have been employed to estimate points, lines, circles, and spheres from uncertain data while keeping track of the uncertainty [START_REF] Perwass | Estimation of geometric entities and operators from uncertain data[END_REF].

Extending Clifford-algebraic methods to graph theory (cf. [START_REF] Schott | Nilpotent adjacency matrices, random graphs, and quantum random variables[END_REF], [START_REF] Staples | Clifford-algebraic random walks on the hypercube[END_REF], [START_REF] Schott | Nilpotent adjacency matrices and random graphs[END_REF]) opens the door to applications in theoretical computer science, symbolic dynamics, and coding theory. The methods can be applied to a graph-theoretic construction of multiple stochastic integrals from which stochastic integrals are recovered from the limit in mean of a sequence of Berezin integrals in an ascending chain of Clifford algebras [START_REF] Staples | Graph-theoretic approach to stochastic integrals with Clifford algebras[END_REF].

Clifford algebras have well-known connections with quantum physics and quantum probability [START_REF] Applebaum | Fermion stochastic calculus in Dirac-Fock space[END_REF], [START_REF] Applebaum | Fermion Itô's formula and stochastic evolutions[END_REF], [START_REF] Barnett | The Itô-Clifford integral I[END_REF]. However, Aerts and Czachor have shown that quantum-like computations can be performed within Clifford algebras without the associated problem of noise and need for error-correction [START_REF] Aerts | Cartoon computation: quantum-like computing without quantum mechanics[END_REF].

While Clifford algebra computations can be performed on general purpose processors through the use of software libraries like CLU [START_REF] Perwass | The CLU Project web page[END_REF], GluCat [START_REF] Leopardi | The GluCat Home Page[END_REF], GAIGEN [START_REF] Fontijne | GAIGEN: a geometric algebra implementation generator[END_REF], and the Maple package CLIFFORD [START_REF] Ab Lamowicz | CLIFFORD -A Maple Package for Clifford Algebra Computations[END_REF], direct hardware implementations of data types and operators is the best way to exploit the computational power of Clifford algebras. To this end, a number of hardware implementations have been developed.

Perhaps the first such hardware implementation was a Clifford co-processor design developed by Perwass, Gebken, and Sommer [START_REF] Perwass | Implementation of a Clifford algebra coprocessor design on a field programmable gate array[END_REF]. Implemented on a Field Programmable Gate Array, the design is scalable in both the dimension of the Clifford algebra and the bit width of the numerical factors.

To our knowledge, the second hardware design was the color edge detection hardware developed by Mishra and Wilson [START_REF] Mishra | Color edge detection hardware based on geometric algebra[END_REF], [START_REF] Mishra | Hardware implementation of a geometric algebra processor core[END_REF]. This focus of their work was the introduction of a hardware architecture for applications involving image processing.

More recently, Gentile, Segreto, Sorbello, Vassallo, Vitabile, and Vullo have developed a parallel embedded coprocessing core that directly supports Clifford algebra operators (cf. [START_REF] Franchini | A sliced coprocessor for native Clifford algebra operations[END_REF], [START_REF] Gentile | Clif-foSor, an innovative FPGA-based architecture for geometric algebra[END_REF], [START_REF] Gentile | CliffoSor: a parallel embedded architecture for geometric algebra and computer graphics[END_REF]). The prototype was implemented on a Field Programmable Gate Array and initial tests showed a 4× speedup for Clifford products over the analogous operations in GAIGEN.

Given a computing architecture based on Clifford algebras, the natural context for determining an algorithm's time complexity is in terms of the number of geometric (Clifford) operations required. This paper assumes the existence of such a processor and examines a number of combinatorial problems known to be of NP time complexity.

For example, the problem of determining whether or not a graph contains a Hamiltonian cycle is known to be NP-complete. By considering entries of Λ k , where Λ is an appropriate nilpotent adjacency matrix associated with a finite graph on n vertices, the k-cycles in the graph are recovered.

The nilpotent adjacency matrix of a graph on n vertices is defined using elements of an abelian algebra generated by the collection

{ζ i }, 1 ≤ i ≤ n satisfying ζ i 2 = 0.
In terms of the number of multiplications performed within the algebra, the cycle enumeration problem is reduced to matrix multiplication. While the algebras used here are not Clifford algebras themselves, they are constructed within Clifford algebras of appropriate signature.

Notational Preliminaries

Definition 1.1 (Clifford algebra of signature (p, q)). For fixed n ≥ 1, the 2 n -dimensional algebra Cℓ p,q (p + q = n) is defined as the associative algebra 2 generated by the collection {e i } (1 ≤ i ≤ n) along with the unit scalar e 0 = e ∅ = 1 ∈ R, subject to the following multiplication rules:

e i e j = -e j e i for i = j, (1.1)

e i 2 = 1 1 ≤ i ≤ p, and -1 p + 1 ≤ i ≤ n. (1.2)
Products are multi-indexed by subsets of [n] = {1, . . . , n} according to

e i = ι∈i e ι , (1.3)
where i is an element of the power set 2 [n] . By defining ζ i = (e i + e n+i ) ∈ Cℓ n,n for each 1 ≤ i ≤ n, the following useful algebra is obtained. Definition 1.2. Let Cℓ n nil denote the real abelian algebra generated by the collection {ζ i } (1 ≤ i ≤ n) along with the scalar 1 = ζ 0 subject to the following multiplication rules:

ζ i ζ j = ζ j ζ i for i = j, and (1.4)
ζ i 2 = 0 for 1 ≤ i ≤ n. (1.5)
It is evident that a general element u ∈ Cℓ n nil can be expanded as

u = i∈2 [n] u i ζ i , (1.6)
where i ∈ 2 [n] is a subset of [n] = {1, 2, . . . , n} used as a multi-index, u i ∈ R, and

ζ i = ι∈i ζ ι .
Letting

ε i = 1 2
(1 + e i e n+i ) ∈ Cℓ n,n for each 1 ≤ i ≤ n gives the following algebra.

Definition 1.3. Let Cℓ n idem denote the real abelian algebra generated by the collection {ε i } (1 ≤ i ≤ n) along with the scalar 1 = ε 0 subject to the following multiplication rules:

ε i ε j = ε j ε i for i = j, and (1.7)
ε i 2 = ε i for 1 ≤ i ≤ n. (1.8)
An element β ∈ Cℓ n idem can also be expanded as in (1.6); that is,

β = i∈2 [n] β i ε i . (1.9)
Both algebras admit an inner product of the form

i∈2 [n] u i ζ i , j∈2 [n] v j ζ j = ℓ∈2 [n]
u ℓ v ℓ .

(1.10)

The degree-k part of u ∈ Cℓ n nil will be defined by

u k = i∈2 [n] |i|=k u i ζ i . (1.11)
Letting u denote an arbitrary element of Cℓ n nil , the scalar sum of coefficients will be denoted by

u = i∈2 [n] u, ζ i = i∈2 [n] u i . (1.
12)

The definitions of scalar sum and degree-k part extend naturally to Cℓ n idem . A number of norms can be defined on Cℓ n nil . One that will be used later is the infinity norm, defined by

i∈2 [n] u i ζ i ∞ = max i∈2 [n] u i . (1.13)
Remark 1.4. The algebra Cℓ n,n is canonically isomorphic to the fermion algebra of quantum physics [START_REF] Applebaum | Fermion stochastic calculus in Dirac-Fock space[END_REF].

An algorithm's time complexity is typically determined by counting the number of operations required to process a data set of size n in worst-, average-, and best-case scenarios. The operation of multiplying two integers is typical. Multiplying a pair of integers in classical computing is assumed to require a constant interval of time, independent of the integers. The architecture of a classical computer makes this assumption natural.

The existence of a processor whose registers accommodate storage and manipulation of elements of Cℓ n ♦ is assumed through the remainder of this paper. The Cℓ complexity of an algorithm will be determined by the required number of Cℓ n ♦ operations, or Clops required by the algorithm. In other words, multiplying (or adding) a pair of elements u, v ∈ Cℓ n ♦ will require one Clop, where ♦ can be replaced by either "nil" or "idem."

Evaluation of the infinity norm is another matter. In one possible model of such an evaluation, the scalar coefficients in the expansion of u ∈ Cℓ n ♦ are first paired off and all pairs are then compared in parallel. In this way, evaluation of the infinity norm has complexity O(log

2 n ) = O(n).
Let u ∈ Cℓ p,q where p + q = n, and consider the following set of operations.

u † := i∈2 [n] u i e [n]\i (1.14) ι   i∈2 [n] u i e i   := ui>0 e i , (1.15)
u • v := i∈2 [n] u i v i e i , (1.16
)

u + := u • ι(u) (1.17) π k   i∈2 [n] u i e i   := i∈2 [k]
u i e i .

(1.18) Also, define the element

1 [n] := i∈2 [n] e i . (1.19)
Using these operations, an algorithm of Cℓ complexity O(n) can now be written for computing the infinity norm.

procedure InfNorm(u: u ∈ Cℓ p,q ) {Replace all scalar coefficients of u with their absolute values.} u := u + + -u + for j := 1 to n begin {Get multi-vectors e i corresponding to

u i ≥ u [n]\i } x := 1 [n-j+1] -ι u † -u + u := u • x
{Now u has only half as many nonzero coefficients. Project down onto subalgebra of dimension 2 n-j .} u := π n-j (u) + π n-j u † {Note that in each case, either e i or e [n]\i is in the subalgebra, exclusively. Hence, u i ≥ u [n]\i implies u i is assigned as the coefficient of the appropriate multivector in the subalgebra.} end return [u] Given a processor capable of natively performing the operations defined in (1.14)-(1.18), construction of this algorithm establishes the following results.

Lemma 1.5. The Cℓ complexity of evaluating the infinity norm in Cℓ

n ♦ is O(n).
Lemma 1.6. The Cℓ complexity of finding the maximum or minimum real number in a list of size k is O(log k).

Proof. Using the algorithm, the complexity of finding the maximum or minimum value in a list of size 2 n is O(n).

Corollary 1.7. The Cℓ complexity of sorting a list of size k is O((log k) 2 ).

Proof. In light of the lemma, the complexity of sorting a list of size 2 n is

O n k=1 k = O n 2 + n 2 = O(n 2 ). (1.20)
Hence, the result.

Graph Problems

A graph G = (V, E) is a collection of vertices V and a set E of unordered pairs of vertices called edges. Two vertices v i , v j ∈ V are adjacent if there exists an edge {v i , v j } ∈ E. A k-walk {v 0 , . . . , v k } in a graph G is a sequence of vertices in G with initial vertex v 0 and terminal vertex v k such that there exists an edge {v j , v j+1 } ∈ E for each 0 ≤ j ≤ k -1. Note that a k-walk contains k edges. A k-path is a k-walk in which no vertex appears more than once. A closed k-walk is a k-walk whose initial vertex is also its terminal vertex. A k-cycle (k ≥ 3) is a closed k-path with v 0 = v k . A Hamiltonian cycle is an n-cycle in a graph on n vertices; i.e., it contains V.
When working with a graph G on n vertices, one often utilizes the adjacency matrix A associated with G. If the vertices are labeled {1, . . . , n}, one defines A by

A ij = 1 if v i , v j are adjacent 0 otherwise. ( 2.1)
A simple but useful result of this definition, which can also be generalized to directed graphs, is given here without proof.

Proposition 2.1. Let G be a graph on n vertices with associated adjacency matrix A. Then for any positive integer k, the (i, j) th entry of A k is the number of k-walks i → j. In particular, the entries along the main diagonal of A k are the numbers of closed k-walks in G.

What the adjacency matrix fails to provide, however, is a method of counting paths and cycles in G. For that, a "new" type of adjacency matrix is needed.

Nilpotent Adjacency Matrices

Definition 2.2. Let G be a graph on n vertices, either simple or directed with no multiple edges, and let {ζ i }, 1 ≤ i ≤ n denote the nilpotent generators of Cℓ n nil . Define the nilpotent adjacency matrix associated with G by

Λ ij = ζ j , if {v i , v j } ∈ E(G) 0, otherwise. (2.
2)

It should be clear that Λ defined over Cℓ n nil implies Λ k is the n × n zero matrix for all k > n. Therefore (I -tΛ) -1 = n k=0 t k Λ k exists as a finite sum, and one can recover

tr Λ k = tr (I -tΛ) -1 t k . (2.3)
In other words, the trace of the coefficient of t k in the power series expansion of (I -tΛ) -1 is the trace of Λ k .

Theorem 2.3. Let Λ be the nilpotent adjacency matrix of an n-vertex graph G. For any m ≥ 3 and 1 ≤ i ≤ n, summing the coefficients of (Λ m ) ii yields the number of m-cycles based at v i occurring in G.

Proof. The proof is by induction on m. First it will be shown that matrix entry (Λ m ) ij corresponds to a sum of blades indexed by vertex sets on which there exist m-step walks from v i to v j that revisit no vertex except possibly v i itself. When m = 1, this is true by definition of Λ. Now assuming the proposition holds for m and considering the case m + 1,

Λ m+1 ij = (Λ m × Λ) ij = n ℓ=1 (Λ m ) iℓ Λ ℓj . (2.4)
Considering a general term of the sum,

(Λ m ) iℓ = m-paths wm:vi→v ℓ w m , and (2.5)
Λ ℓi = 1-paths w1:v ℓ →vj w 1 . (2.6)
Because the vertices are labeled with the null-square generators of Cℓ n nil , any repeated vertex yields 0.

It should then be clear that terms of the product

(Λ m ) iℓ Λ ℓj (2.7)
are nonzero if and only if they correspond to (m + 1)-paths v i → v ℓ → v j , with the possible exception that if i = j, then v i could be revisited once. Summing over all vertices v ℓ gives the sum of all (m + 1)-walks based at v i that revisit no vertex with only the specified exception possible. Finally, when i = j, the null-square generator associated with v i appears as the last factor in each product over the (m + 1)-walks. As a result, any walks that revisit v i in an intermediate step are removed from (Λ m+1 ) ii , leaving only the (m + 1)-cycles based at v i .

In an undirected graph, two orientations are possible for each cycle. As a result, each m-cycle is represented with multiplicity two along the diagonal of Λ m . Throughout the remainder of this paper, two cycles in an undirected graph will be considered the "same" if they differ only by orientation or choice of base point. Remark 2.4. The nilpotent adjacency matrix associated with a finite graph can be considered a quantum random variable whose m th moment corresponds to the number of m-cycles occurring in the graph [START_REF] Schott | Clifford algebras, random graphs, and quantum random variables[END_REF], [START_REF] Schott | Nilpotent adjacency matrices, random graphs, and quantum random variables[END_REF]. ) time [START_REF] Coppersmith | Matrix multiplication via arithmetic progressions[END_REF]. It is not clear that the same asymptotic speedup can be accomplished for the Cℓ case. However, in the remainder of the paper, β will represent the exponent associated with matrix multiplication. In the worst case, multiplication of n × n matrices with entries in Cℓ n nil has Cℓ complexity O(n 3 ), so that β ≤ 3. Proof. Cycles of length k must be counted for 3 Consider a directed, edge-weighted graph G on n vertices. When {v i , v j } is an edge of G, let w ij denote the weight or "cost" of the edge. The goal is to compute the total additive weight of all k-cycles in G.

≤ k ≤ n, requiring O n β log k for each 3 ≤ k ≤ n. Then, n k=3 n β log k = n β log(n!/2) ≤ n β log(n n ) = n β+1 log n. ( 2
The infinity norm in the following theorem is the natural extension of that found in (1.13).

Theorem 2.17 (Minimum cost of all k-cycles). Let G be a finite graph on n vertices with m edges of weights w 1 , w 2 , . . . , w m . Let f :

V (G) × V (G) → N
W min = -ln 1 2k τ k ∞ . (2.15)
Proof. Analogous to the proof of Theorem 2.3, the trace of Λ k consists of elements of the form

n i=1 k-cycles ξ based at vi exp   - v ℓ ∈ξ w ℓ   ζ i(ξ) γ j(ξ) . (2.16)
Here, i(ξ) denotes the subset of the n-set that corresponds to the vertices in cycle ξ. Similarly, j(ξ) is a subset of {1, 2, . . . , |E(G)|} representing the edges contained in cycle ξ. As seen previously, each cycle is represented with multiplicity 2k in the trace of Λ k . Clearly the maximum coefficient in the expansion of the trace corresponds to the minimum sum of weights in the argument of the exponential function.

Edge-disjoint Cycle Decompositions of Graphs

ϑ α ζ j γ i s j1 1 • • • s jn n = α γ i s j1 1 • • • s jn n , (2.17)
and define the evaluation

• : Cℓ m nil [s 1 , . . . , s n ] → R[s 1 , . . . , s n ] by linear extension of α γ i s j1 1 • • • s jn n = α s j1 1 • • • s jn n , (2.18)
where α ∈ R.

The projection ϑ and the evaluation • will be assumed to have Cℓ complexity O(1). Definition 2.20. A finite graph G on n vertices will be said to have a cycle decomposition if for some positive integer m there exists a collection of cycles

{C i } 1≤i≤m such that V (G) = m i=1 V (C i ) (2.19) E(G) = m i=1 E(C i ) (2.20) E(C i ) ∩ E(C j ) = ∅ if i = j. ( 2
G = C j1 ∪ • • • ∪ C jm , i j i = |E| if and only if the degree-m monomial α s j1 • • • s jm is a term in the expansion of ϑ n k=3 s k τ k 2k m |E| (2.22)
where α m! ∈ N indicates the multiplicity of the decomposition.

Proof. Begin by letting Λ be the edge-labeled nilpotent adjacency matrix of an n-vertex graph G = (V, E). From Theorem 2.3, it follows that for any k ≥ 3 and 1 ≤ i ≤ n, summing the coefficients of (Λ k ) ii yields the number of k-cycles based at v i occurring in G.

Hence, τ k 2k corresponds to the collection of k-cycles in G in one-to-one correspondence. Proof. As in the proof of Corollary 2.12, computing

It is now clear that

n k=3 s k τ k 2k has Cℓ com- plexity O(n β+1 log n). Then computing ϑ n k=3 s k τ k 2k m has Cℓ complexity O(n β+1 log n + log m) = O(n β+1 log n).
Example 2.23. The cycle decompositions of the complete graph K 5 are recovered. The nilpotent adjacency matrix is The results are now interpreted: K 5 itself is not a cycle, so the first expression yields zero. The only decompositions of K 5 into pairs of cycles are 6 = 12/(2!) decompositions into pairs of five-cycles. That is, K 5 = C 5 ∪ C 5 with multiplicity six.

• ζ 1 • ζ 2 • ζ 3 • ζ 4 • ζ 5 . . .
Λ =       0 ζ 2 γ 1 ζ 3 γ 2 ζ 4 γ 3 ζ 5 γ 4 ζ 1 γ 1 0 ζ 3 γ 5 ζ 4 γ 6 ζ 5 γ 7 ζ 1 γ 2 ζ 2 γ 5 0 ζ 4 γ 8 ζ 5 γ 9 ζ 1 γ 3 ζ 2 γ 6 ζ 3 γ 8 0 ζ 5 γ 10 ζ 1 γ 4 ζ 2 γ 7 ζ 3 γ 9 ζ 4 γ 10 0       . ( 2
The only decompositions into triples of cycles are 15 = 90/(3!) decompositions of the form K 5 = C 3 ∪ C 3 ∪ C 4 , i.e., a pair of three-cycles and a four-cycle.

There are no decompositions of K 5 into four or more disjoint cycles.

Definition 2.24. A cycle cover of a graph G is defined as a pairwise disjoint collection of cycles {C j } such that each vertex of G is contained in exactly one of the cycles. 3 Other Problems

In addition to graph problems, properties of Cℓ n nil and Cℓ n idem make them useful for other types of combinatorial problems.

Computing the Permanent

The problem of computing the permanent of a matrix is known to be ♯Pcomplete [START_REF] Valiant | The complexity of computing the permanent[END_REF], [START_REF] Ben-Dor | Zero-one permanent is ♯P-complete, a simpler proof[END_REF]. Methods of approximating the permanent using Clifford algebras have also been discussed [START_REF] Chien | Clifford algebras and approximating the permanent[END_REF].

The current authors' methods allow one to directly compute the permanent of a matrix with Cℓ computational complexity O(n).

Let M = (m ij ) n×n be an arbitrary matrix. Let {γ i } 1≤i≤n and {ζ i } 1≤i≤n denote commutative nilpotent generators of

The Set Packing and Set Covering Problems

The following two problems are among the original 21 NP-complete problems of Karp [START_REF] Karp | Reducibility among combinatorial problems, Complexity of Computer Computations[END_REF]. They are moved to class P in the Cℓ context.

Corollary 2 . 5 .Corollary 2 . 6 .

 2526 Let Λ be the nilpotent adjacency matrix of an n-vertex graph G. Let X m (m ≥ 3), denote the number of m-cycles appearing in the graph G. Then tr (Λ m ) = 2m X m . (2.8) Notation. To simplify notation, tr (Λ m ) is replaced by τ m in the remainder of the paper. Let Λ be the nilpotent adjacency matrix of an n-vertex graph G. Let H n denote the number of Hamiltonian cycles appearing in the graph G. Then τ n = 2n H n . (2.9) Recall the stated assumption that addition of two arbitrary elements of Cℓ n nil requires 1 Clop. It follows that computing tr(A), where A is an n × n matrix having entries in Cℓ n nil , has Cℓ complexity O(n). Using the Coppersmith-Winograd algorithm, multiplying two n × n matrices can be done in O(n 2.376

Corollary 2 . 7 .Corollary 2 . 8 .

 2728 Enumerating the k-cycles in a finite graph on n vertices requires O(n β log k) Clops. Enumerating the Hamiltonian cycles in a finite graph on n vertices requires O(n β log n) Clops.Corollary 2.9. Let Λ be the nilpotent adjacency matrix of an n-vertex graph G. Let X m,ℓ denote the number of ℓ-tuples of pairwise disjoint m-cycles appearing in the graph G, where m ≥ 3 and 1 ≤ ℓ ≤ ⌊n/m⌋. Then(τ m ) ℓ = (2m) ℓ ℓ!X m,ℓ . (2.10) Proof. Note that τ m 2m is a sum of nilpotent multivectors associated with m-cycles in the graph. By nilpotency, the nonzero terms of τ m 2m ℓ represent pairwise disjoint m-cycles, and each term occurs ℓ! times. Corollary 2.10. Counting the ℓ-tuples of pairwise disjoint m-cycles in a finite graph on n vertices requires O(n β log m) Clops. Proof. As already seen, computing τ m requires O(n β log m) Clops. Computing τ m ℓ then requires O(log ℓ) additional Clops. Hence, counting ℓ-tuples of mcycles requires O(max{log ℓ, n β log m}), where ℓ is never larger than n/m.The following proposition is an immediate corollary of Theorem 2.3. Proposition 2.11 (Graph circumference). Let G be a graph on n vertices with nilpotent adjacency matrix Λ. The length of the longest cycle in G is the largest integer k such that τ k = 0. (2.11) Corollary 2.12. Computing the circumference of a graph on n vertices requires O(n β+1 log n) Clops.

Corollary 2 . 18 .

 218 The problem of determining the minimum cost associated with a k-cycle in G has Cℓ complexity O(n β log k).

Corollary 2 . 19 (

 219 Minimum cost Hamiltonian cycle). The problem of determining the minimum cost associated with a Hamiltonian cycle in G has Cℓ complexity O(n β log n).

  sum of all the cycles contained in G. Projecting down onto Cℓ |E| nil leaves each k-cycle represented by a degree-k multivector γ i , corresponding to the edges comprising the cycle. By nilpotency, the nonzero terms of ϑ of all m-ensembles of pairwise edge-disjoint cycles, and each term occurs m! times in the expansion. By considering only those terms of degree |E| in Cℓ |E| nil , one ensures that only cycle decompositions of G are obtained since all edges are represented. Corollary 2.22. Let G be a simple graph on n vertices and |E| edges with nilpotent adjacency matrix over Cℓ nil n ⊗Cℓ nil |E| . Then, for any fixed m ≥ 1, determining the decomposition of G into m edge-disjoint cycles requires O(n β+1 log n) Clops.

γ 2 . 3 .

 23 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . γ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

γ 4 . 5 . 6 .

 456 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . γ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . γ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  γ

Theorem 2 . 25 .

 225 Let Λ be the nilpotent adjacency matrix of a finite graph G on n vertices. Then, letting C denote the number of cycle covers of G, [|E|] = C.(2.28)Proof. For each 3 ≤ m ≤ n, τm 2 m denotes the algebraic sum of multivectors representing m-cycles in G. Computing the ℓ th power of the sum of these reveals pairwise disjoint ℓ-tuples of cycles of all lengths, each appearing with multiplicity ℓ!. Because G has n edges, the maximum number of ℓ-tuples of disjoint cycles in G is ⌊n/3⌋. Summing over all admissible values of ℓ and considering the coefficient of γ[|E|] to ensure that all edges of G are covered, the number of cycle covers of G is recovered.For each m = 3, . . . , n, computing τ m requires O(n β log m) Clops. Hence, n β+1 log n) Clops. For each ℓ = 1, . . . , ⌊n/3⌋, O(n β+1 log n log ℓ) Clops. Finally, summing over ℓ, n β+2 log n log n) Clops. It therefore follows from the results obtained thus far that counting the disjoint cycle covers of a graph on n vertices requires O(n β+2 log n log n) Clops. In the next section, this result is improved by another method.

m. 1 ) 3 . 1 .mCorollary 3 . 3 .

 13133 ij γ i ζ j ∈ Cℓ n nil ⊗ Cℓ n nil . (3Proposition Let M , n, and a be defined as above. Then,a n , γ [n] ζ [n] = n! Perm(M ). (3.2)Proof. Let M be an n × n matrix and consider the following definition of the permanent:i π(i) γ i ζ π(i) = n! Perm(M ) γ [n] ζ [n] . (3.4) Corollary 3.2. Computing the permanent of an n×n matrix is of Cℓ complexity O(n). Counting the perfect matchings of a bipartite graph is of Cℓ complexity O(n).

Corollary 3 . 4 (

 34 Complexity of cycle covers).Counting the cycle covers of a finite graph on n vertices is of Cℓ complexity O(n).

Theorem 3 . 5 (ζTheorem 3 . 6 (ε

 3536 Set packing problem). Let S = {S 1 , . . . , S m } be a collection of subsets of the n set {1, 2, . . . , n}. In the Cℓ context, the problem of determining whether there exists a pairwise disjoint collection {S j1 , . . . , S j k } ⊆ S has Cℓ complexity O(log k). Proof. Let α = m j=1 Sj ∈ Cℓ n nil . Then there exists a pairwise disjoint collection {S j1 , . . . , S j k } ⊆ S if and only if α k = 0. Set covering problem). Let S = {S 1 , . . . , S m } be a collection of subsets of the n-set {1, 2, . . . , n}. In the Cℓ context, the problem of determining the minimum value of k for which there exists a collection {S j1 , . . . , S j k } ⊆ S satisfying k ℓ=1 S j ℓ = {1, 2, . . . , n} has Cℓ complexity O(m log k). Proof. Let α = m j=1 Sj ∈ Cℓ n idem . Then there exists a collection {S j1 , . . . , S j k } ⊆ S such that k ℓ=1 S j ℓ = {1, 2, . . . , n} if and only if α k , ε [n] = 0. Checking each k = 1, 2, . . . , m requires at most m iterations.

  In the next proposition, C denotes the diagonal matrix Diag(ζ 1 , . . . , ζ n ). It is used to account for the initial vertices of paths in G.Proposition 2.15 (Longest path). Let G be a graph on n vertices with nilpotent adjacency matrix Λ. The length of the longest path in G is the largest integer k This is a corollary of Theorem 2.3. Cycles are disregarded by removing the diagonal entries of CΛ k . Left multiplication by the matrix C is used to "sieve" out k-walks that revisit their initial vertices. Corollary 2.16. Computing the length of the longest path in a graph on n vertices requires O(n β log n log n) Clops. Proof. The maximum possible path length is n. For each 1 ≤ k ≤ n, computing CΛ k requires O(n β log k + n 2 ) = O(n β log n) Clops. Using binary search then requires testing O(log n) values of k in Proposition 2.15.

	Proof.
	such that
	CΛ k = 0.	(2.14)
	Here, 0 denotes the n × n zero matrix.

.12) Corollary 2.13 (Graph girth). Let G be a graph on n vertices with nilpotent adjacency matrix Λ. The length of the shortest cycle in G is the smallest integer k such that τ k = 0. (2.13) Corollary 2.14. Computing the girth of a graph on n vertices requires O(n β+1 log n) Clops.

Proof. Proof follows that of Corollary 2.12.

  be a labeling of the edges of G with natural numbers. Label the vertices of G with the nilpotent generators of Cℓ n

nil and let edges of G be labeled with exp(-w ij )γ f (i,j) , where {γ i } is the collection of nilpotent generators of Cℓ |E(G)| nil . The nilpotent adjacency matrix then has entries in Cℓ n nil ⊗ Cℓ |E(G)| nil . The minimum cost k-cycle in G has cost

  Consider the algebra R[s 1 , . . . , s n ] of polynomials in commutative variables s 1 , . . . , s n . Allowing these polynomials to have coefficients in Cℓ n nil ⊗ Cℓ m nil generates the abelian algebra Cℓ n nil ⊗ Cℓ m nil [s 1 , . . . , s n ]. Define the projection ϑ : Cℓ n nil ⊗ Cℓ m nil [s 1 , . . . , s n ] → Cℓ m nil [s 1 , . . . , s n ] by linear extension of

  7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	γ 9	γ 10
	γ 8

.

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . γ 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Acknowledgment. The second author thanks Philip Feinsilver for useful discussion about the matrix permanent.


Lydie Staron

Farhang

published or not. The documents may come

Friction versus texture at the approach of a granular avalanche


Glen M Hocky

Ludovic Berthier

Walter Kob

David R Reichman

Crossovers in the dynamics of supercooled liquids probed by an amorphous wall

published or not. The documents may come   L'archive ouverte pluridisciplinaire