M Hochlaf
email: hochlaf@univ-mlv.fr

H Ndome

D Hammoutène

M Vervloet

Valence-Rydberg electronic states of N 2 : Spectroscopy and Spin-orbit couplings

Using an ab initio methodology, we compute the potential energy curves and the spinorbit coupling integrals of the N 2 electronic states located in the 0-120000 cm -1 energy domaine.

In our analysis, we focus mostly on those located outside the Franck-Condon regio n accessible from the ground state of N 2 i.e. the two strongly bound states 1 3 Σ g -and 1 1 Γ g , and the weakly bound state 2 3 Σ g -, in addition to several repulsive states. We characterize them spectroscopically and we compute their spin-orbit couplings to the close lying singlets, triplets and quintets. This work completes our knowledge on the electronic states of N 2 that may be important intermediates during N + N collisions and for the dynamics of the N 2 singlets and triplets and quintets VUV photodissociation.

I.

Introduction

For energies above 85000 cm -1 with respect to N 2 (X 1 Σ g + , v=0), three groups of N 2 electronic states are known and widely studied both experimentally and theoretically : namely the 1 Σ u + , the 1 Π u and the 3 Π u states. Their spectroscopy, their dynamics, their mutual interaction and their perturbation by the close lying electronic states of N 2 are nicely discussed and reviewed in Refs. [1][2][3][4][5]. Briefly, these electronic states are accessible (favorable Franck-Condon factors) by optical transitions from the ground state (GS) of N 2 either by spin-allowed (singlet-singlet) or spin-forbidden (singlet-triplet) absorptions [START_REF] Bernath | DiRef, a database of references associated with the spectra of diatomic molecules[END_REF][START_REF] Huber | Molecular spectra and molecular structure Constants of diatomic molecules[END_REF][START_REF] Lofthus | [END_REF]. Some triplet-triplet transitions were also well analyzed [START_REF] Bernath | DiRef, a database of references associated with the spectra of diatomic molecules[END_REF][START_REF] Huber | Molecular spectra and molecular structure Constants of diatomic molecules[END_REF][START_REF] Lofthus | [END_REF]. Outside the Franck-Condon region of GS, a quintet-quintet emitting system was detected and assigned later, by the help of theoretical calculations, to the C" 5 Π u ß A' 5 Σ g + transition, which is responsible for the Herman (HIR) bands of N 2 [9][10][11][12][13][14][15]. Very recently, some of us have predicted a second quintet-quintet system at higher energies [16]. It was shown there that some of these quintets couple to their close lying electronic states of triplet spin-multiplicities and participate into their perturbation as noticed experimentally [16][17][18][19][20][21][22][23].

Presently, we use state-of-the-art ab initio methodology for the investigation of electronic states of N 2 . In light of these calculations, we reanalyze the singlets and the triplets located outside the Franck-Condon region, which are not accessible directly from N 2 GS. Using these highly correlated wavefunctions we compute the spin-orbit couplings integrals between the electronic states of N 2 lying in the 75000-120000 cm -1 energy domain. Then, we deduce their spectroscopic parameters. Finally, we discuss the possible perturbations of the 1 Σ u + , the 1 Π u and the 3 Π u systems by these electronic states and their role on the formation of N atoms after N 2 VUV photodissociation.

II. Methodology

The calculations were done using the Complete Active Space Self Consistent Field (CASSCF) [24] technique followed by the internally contracted Multi Reference Configuration Interaction (MRCI) [25][26] approach. We described the nitrogen atom by a large basis set of aug-cc-pVQZ quality, which is augmented by 3 s and 2 p diffuse Gaussian type orbitals (GTOs) [27]. In CASSCF, the active space was composed by the valence molecular orbitals (MOs) of N 2 to which we added one σ g and one π g MOs for better relaxation of the wavefunctions of the N 2 electronic states whose configurations differ in their σ π orbital occupations. We used an active space larger than the valence and a diffuse basis set in order to well describe any possible Rydberg character of the electronic states treated presently. It is worth noting that such treatment does not disturb the MOs, whic h possess strictly a valence character as discussed previously [1,2,16]. A state-averaged procedure was used where the electronic states having the same spin and space irreducible representation in the D 2h point group were averaged together.

In MRCI, all CASSCF CSFs were taken as reference. All electrons were correlated. We carried out our ab initio electronic calculations using the MOLPRO program suite [28] in the D 2h point group. The B 3u and B 2u and the B 2g and B 3g representations were equivalently treated. We considered hence more than 2.6 x 10 8 uncontracted CSFs per symmetry. See Refs. [1,2,16] for further details.

The nuclear motion problem was solved using the method of Cooley [29]. The spectroscopic constants discussed below were obtained using the derivatives at the minimum energy distances and standard perturbation theory.

III. Potential energy curves and spectroscopy

We depict in Figure 1 the full set of our CASSCF/MRCI potential energy curves vs. the internuclear distance. These potentials are given in energy with respect to the GS minimum. This figure shows the high density of electronic states located for energies greater than 85000 cm -1 . This high density should favor their mutual interactions and the mixings of their wavefunctions by vibronic , spin-orbit and rotational couplings. For better clarity, we present in Figure 2 the electronic states correlating to each dissociation limit separately together with their assignments. We considered electronic states that converge adiabatically to the N( 4 S u ) + N( 4 S u ), N( 4 S u ) + N( 2 D u ), N( 4 S u ) + N( 2 P u ), and N( 2 D u ) + N( 2 D u ) asymptotes. Generally, the pattern of the electronic states located in the domain of interest is in good accord with the previously ones. For instance, this is the case for the majority of the electronic states located in the Franck-Condon region so that we will not discuss them in detail. In addition, our calculations allow better description of some singlet and triplet states lying at high energies. These states are either strongly or weakly bound or repulsive in nature. In the following, we focus on the spectroscopy of the bound states and their spin-orbit interactions with the close-lying electronic states of N 2 . The repulsive states are mostly of quintet spin multiplicity. They were widely discussed and commented in Ref. [16]. It is worth noting that the literature on the N 2 electronic states is wide and it is not the scope of the present paper to enumerate it. Instead we present our results and their comparison to the earlier VCI treatment of Michels [START_REF] Michels | Electronic structure of excited states of selected atmospheric systems[END_REF] and to the multi configuration interaction study of Mulliken and co-workers [31]. These two theoretical works represent the most complete treatments of the N 2 electronic states. The analysis of the electron configurations of these electronic states coincides with its performed by Mulliken and co-workers in Ref. [31]. Especially, the valence or Rydberg or mixed character of these electronic states is confirmed by the present calculations.

In the 90 x 10 3 -120 x 10 3 cm -1 energy range, we calculate three bound states located outside the Franck-Condon region from GS:

(i) At ~ 97800 cm -1 , we locate a relatively strongly bound electronic state of 3 Σ g symmetry (Figure 2C, Table 1). It possesses a potential well of ~8700 cm -1 . Its electronic wavefunction is mainly described by the (2σ g ) 2 (3σ g ) 2 (1π u ) 2 (2σ u ) 2 (1π g ) 2 similar to the N 2 (G 3 ∆ g ) state and to the outer part of the N 2 (a" 1 Σ g + ) state. Formally , we add an electron into the vacant 1π g molecular orbital to the ionic core N 2

+ (b 4 Π g ) [32]. The equilibrium distance of N 2 (1 3 Σ g -) is calculated 1.614 Å, which is close enough to the equilibrium value in N 2 + (b 4 Π g ) (1.46 Å [32]).
This electronic state was previously predicted by Michels [START_REF] Michels | Electronic structure of excited states of selected atmospheric systems[END_REF] in 1979. However, this prediction was strongly criticized two years later by Mulliken and co-workers [31] because of the small active space used in Michels's work. Nevertheless, our large calculations confirm the earlier predictions of Michels. At the MRCI level, we calculate ω e (1 3 Σ g -) = 761 cm -1 which is 31 cm -1 smaller than the value given by Michels (Table1).

(ii) We find a 1 Γ g state that correlates adiabatically to the N( 2 D u ) + N( 2 D u ) dissociation limit (Figure 2 D). The existence of this electronic state was already noticed by Ermler et al. [31]. These authors calculated the potential curve for the 1 1 Γ g state up to R=3.2 bohr (= 1.693 Å) and found in their best SD calculation a pronounced minimum at 13.14 eV (= 106000 cm -1 ).

The VCI treatment of Michels led also to a strongly bound state. Our calculations confirm definitely that this electronic state is well bound with a deep potential well of ~13750 cm -1 . Its electronic wavefunction is dominantly described by the N 2 + (b 4 Π g ) + 1π g electron configuration.

At the MRCI level of theory, we compute the following spectroscopic parameters for this electronic state: R e = 1.608 Å, B e = 0.9305 cm -1 , α e = 0.0123 cm -1 , ω e = 816.5 cm -1 , ω e x e = 9.35 cm -1 and ω e y e = -0.14 cm -1 (Table 1). Our R e , B e , α e and ω e x e agree with those of Michels [START_REF] Michels | Electronic structure of excited states of selected atmospheric systems[END_REF],

whereas our ω e is ~40 cm -1 smaller than his value.

(iii) In Michels's work, a 3 Σ g -state was found for energies ~ 114000 cm -1 . Nevertheless, the shape of the potential of this electronic state was not definitely established there because of the reduced size of his calculations. This author predicted a double well potential for this electronic state. Our calculations confirm the presence of such electronic state but a unique shallow potential well is found. It corresponds to the 2 3 Σ g -state at ~ 114500 cm -1 . The depth of the potential is ~ 2200 cm -1 . The 2 3 Σ g -equilibrium distance is 1.817 Å. The formation of such shallow potential well is most likely due to competition between electrostatic interactions and the chemical bonding between two N( 2 D u ) atoms (Figure 2D). This electronic state is multi configurational in nature: its wavefunction is dominantly described by the (2σ g ) 2 (3σ g ) 2 (1π u ) 2 (2σ u ) 2 (1π g ) 2 and (2σ g ) 2 (3σ g ) 0 (1π u ) 4 (2σ u ) 2 (1π g ) 2 electron configurations.

Table 1 presents the spectroscopic properties of these three electronic states. We list also the data for the a' 1 Σ u -, a 1 Π g , w 1 ∆ u , G 3 ∆ g , a" 1 Σ g + and E 3 Σ g + states, where a close comparison with the reference data of [START_REF] Huber | Molecular spectra and molecular structure Constants of diatomic molecules[END_REF][33][34][35] is given. For the later states, one can clearly see the good accord between our calcula ted harmonic and anharmonic terms and rotational constants and those determined experimentally. Indeed, the calculated and measured equilibrium distances differ by less than 0.01 Å, which is connected also to the noticeable good agreement for the rotationa l constants at equilibrium, B e . For the harmonic wavenumbers (? e ), the differences are less than 10 cm -1 , except for the E state where we compute a value larger than Refs. [34,35] by 29 cm -1 . Such good agreement asserts on the good quality of the predicted spectroscopic data for the of N 2 (1 3 Σ g -, 1 1 Γ g and 2 3 Σ g -) ele ctronic states.

IV. Spin-orbit couplings

We evaluated the spin-orbit coupling terms between the electronic states of interest over the CASSCF wavefunctions and using the Breit-Pauli Hamiltonian as implemented in MOLPRO. These integrals are calculated in Cartesian coordinates. Figure 3 displays the non-vanishing non-diagonal spin-orbit integrals between the singlet, triplet and quintet N 2 electronic states. In this figure, we use the following notation: A-B denotes the <A|H SO |B> integral. For instance, the

E 3 Σ g + -2 3 Σ g -term corresponds to the < E 3 Σ g + |H SO |2 3 Σ g -> integral.
In the following, we discuss solely the spin-orbit evolutions. In particular, we do not consider their consequences on the spectroscopic parameters of the N 2 electronic states since spin-orbit corrections to the spin-orbit free PECs of Figures 1 and2 are too small for N 2 .

Figure 3 shows that the spin-orbit integrals present two different behaviours: For R < 3-3.5 bohr, they exhibit a non-monotonic evolution along the internuclear distance, whereas they are mostly monotonic or quasi constant for R > 3.5 bohr. These brusque changes coincide with the change of the nature of the corresponding electronic wavefunctions. For instance, the E 3 Σ g + , a" 1 Σ g + , and 3 Π u electronic states present potential barriers separating their potential wells at short and large internuclear separations (within the adiabatic representation). This is accompanied by strong variations of the composition of their wavefunctions, resulting in drastic changes in the spin-orbit integrals evolving these three electronic states.

Recently, we calculated the spin-orbit constants at equilibrium (A SO,e ) for the quintet and the 3 Π u states using similar methodology. An excellent accord is found with experimental determinations [2,16]. The present data allow deducing A SO,e (G 3 ∆ g ) = ½ <G 3 ∆ g |H SO | G 3 ∆ g > = -0.04 cm -1 . We confirm hence the close to zero spin-orbit constants (A 0 = -0.21 and A 1 = -0.25 cm -1 ) measured earlier for this electronic state [36].

V. Discussion

In this section, we detail the implications of the presence of the 1 3 Σ g -, 1 1 Γ g and 2 3 Σ g -electronic states in the radiative transitions and perturbations of the well-known electronic states of N 2 . Then we use our PECs and spin-orbit coupling integral evolutions to treat the interactions of these electronic states with the other electronic states.

Implications for the radiative transitions in N 2

In despite that the 1 3 Σ g -state is located relatively high in energy, this state cannot emit to the lowest electronic states of N 2 due to selection rules for optical transitions. This confers a relative stability to this triplet. In contrast, it can undergo radiative transitions to the 3 Π u states. For instance, it may interact with the neighboring C 3 Π u , C' 3 Π u , and III 3 Π u states. For R = 3.06 bohr (~ R e of 1 3 Σ g -), we compute the following transition moments: <1 3 Σ g -|µ|C 3 Π u > = -0.221, <1 3 Σ g -|µ|C' 3 Π u > = -0.123 and <1 3 Σ g -|µ|III 3 Π u > = -0.430, in Debye. As shown in Figure 4, transitions in the IR between the low vibrational levels of both sets of trip let states are most likely occurring.

At ~ 96 x 10 3 cm -1 above GS, the E state was first located through the analysis of the E 3 Σ g + ?

A 3 Σ u + emissions (Herman-Kaplan system) [37]. This assignment was definitely confirmed later theoretically and experimentally [34,35,[38][39][40][41]. Our calculations show that the 1 3 Σ g -is lying closely to the E state. The E 3 Σ g + à A 3 Σ u + emission is allowed, whereas the 1 3 Σ g -à A 3 Σ u + radiative transition is not. Accordingly, the emission spectra of N 2 near to the Herman-Kaplan bands should be perturbed by the existence of the 1 3 Σ g -state: several observations relative to this band system remain still unexplained. For instance, Beiting and Feldman [42] found that the intensity of the (0, 2) band of the Herman-Kaplan (E ? A) system was ~5 times stronger than the previously predicted theoretical value. Moreover, the relatively long radiative lifetime for the E state of 270 ± 100 µs measured by

Freund [35] is probably because of the p opulation of the E rovibrational levels by spin-orbit conversions from the 1 3 Σ g -acting as a reservoir for the emitting E state (see below).

The 1 1 Γ g state can decay radiativel y to the lower W 3 ∆ u . However, this transition should be very weak because it is spin-forbidden and because |??| > 1. Hence, the rovibrational level s of 1 1 Γ g should have long lifetimes. Alternatively, it can be populated by optical emissions from the upper bound 1 ∆ u or 1 Γ u Rydberg states of N 2 or via spin-forbidden transitions from the upper 3 ∆ u and 3 F u (e.g. H 3 F u ).

Finally, the 2 3 Σ g -state should play a central role during the cascading optical transitions involving the Valence-Rydberg and Rydberg states of N 2 . For instance, Figure 4 shows that this triplet is embedded into a set of 3 Π u states to which it can either emit (e.g. to the C 3 Π u and C' 3 Π u state s) or couple (e. g. with the III 3 Π u state) and vice versa. The 3 Π u states lying above III 3 Π u , which present a non-zero

Franck-Condon overlap with the 2 3 Σ g -may be invoked in that context.

On the role of N

2 (1 3 Σ g -, 1 1 Γ g , 2 3 Σ g -)

in the dynamics of the neighboring electronic states and in N 2 VUV photodissociation

For a diatomic homonuclear molecular system, the spin-orbit interaction selection rules are [43,[START_REF] Lefebvre-Brion | The Spectra and Dynamics of Diatomic Molecules[END_REF]: ∆Ω = 0; g ?/? u; g ? g; u ? u;

Σ + ? Σ - ∆S = 0 or ∆S = ± 1; ∆Λ = ∆Σ = 0 or ∆Λ = -∆Σ = ± 1
Therefore, ungerade states couple together and gerade states couple together. We have already treated in Ref. [16] the possible interactions between the ungerade states of N 2 , where we have enlightened the role of the bound and repulsive quintet states. These quintets connect the singlets and the triplets located in the Franck Condon region of GS to the corresponding photodissociation products. Presently, we consider the interactions between the gerade states. We focus mostly on the role of 1 3 Σ g -, 1 1 Γ g and 2 3 Σ g -. We display in Figure 5 the PECs of these electronic states together with those of the other gerade states crossing them.

For N 2 (1 3 Σ g -), the situation is rather complicated since this triplet is embedded into a set of potentials of electronic states to which a priori it can couple. Indeed, Figure 5 reveals that 5 ∆ g and a 1 Π g . Among them, only the

1 3 Σ g -is crossed by the 2 5 Σ g + , E 3 Σ g + , a" 1 Σ g + , 1 5 Π g ,
1 3 Σ g -? E 3 Σ g + , 1 3 Σ g -?
1 5 Π g and 1 3 Σ g -? a 1 Π g spin-orbit conversions are allowed. The <1 3 Σ g -|H SO |a 1 Π g > integral (not shown) is close to zero along the NN distance. Whereas, the <1 3 Σ g -|H SO |E 3 Σ g + > and <1 3 Σ g -|H SO |1 5 Π g > integrals amount to ~ 5.9 and ~ 25.5 (in cm -1 ) at their crossings (i.e. R = 2.48 bohr and R = 3.93 bohr), respectively. Such integrals are large enough to allow such conversion. The 1 5 Π g is repulsive in nature.

It correlates adiabatically to the N( 2 D u ) + N( 4 S u ) asymptote. It leads hence directly to the N( 2 D u ) + N( 4 S u ) products. For the E vibrational levels located above the E 3 Σ g + -1 3 Σ g -crossing, we expect the following successive transitions: E 3 Σ g + à 1 3 Σ g -à 1 5 Π g à N( 2 D u ) + N( 4 S u ). This reduces their lifetimes.

For the lower rovibrational states, they should have, instead, long lifetimes.

The 1 1 Γ g state presents a large orbital angula r momentum, Λ. It should be free from any interactions or better saying weakly coupled to the N 2 states in despite that it is crossed by the E 3 Σ g + , 2 5 Σ g + , 1 5 Π g , 5 ∆ g , 2 3 Π g , a 1 Π g , 1 5 Π g 1 5 Σ g -and 2 5 Π g states. According to the selection rules given above, it cannot couple to any of these states by spin-orbit. For the formation of N 2 molecules in the 1 1 Γ g state , we can propose either reactive collisions between N*( 2 D u ) and N*( 2 D u ) atoms or by radiative transitions from the upper 3 ∆ u states of N 2 .

Similar to the 1 3 Σ g -state, the N 2 (2 3 Σ g -) is crossed by a multitude of gerade states. Spin-orbit conversions may occur only with the E 3 Σ g + , 2 3 Π g , 1 5 Π g and 2 5 Π g states (Figure 5). The spin-orbit integrals are non-zero at their crossings (Figure 3). Close to and beyond the region of the crossings, the E 3 Σ g + , 2 3 Π g , 1 5 Π g and 2 5 Π g states present dissociative behaviors and lead to the lower asymptotes.

The dynamics of the rovibrational levels supported by the 2 3 Σ g -weak potential should be complex.

This should affect the lifetimes of such levels. In addition, we expect that the 2 3 Σ g -state plays crucial roles during cold collisions between two N( 2 D u ) atoms and in the dynamics of the Valence-Rydberg states lying in energy close to the N( 2 D u ) + N( 2 D u ) asymptote via couplings to the triplet and quintet states.

VI. Conclusion

Using a full ab initio treatment, we investigated the electronic states of N 2 . In addition to the well-known electronic states, we confirm the existence of three bound gerade states. These states possess potentia l wells located outside the Franck-Condon region accessible from N 2 (X 1 Σ g + ) or from the metastable (A 3 Σ u + ) state. Experimental evidences of their existence and their interactions and perturbations of t he singlet, triplet and quintet manifolds of states are discussed. Therefore, we strongly recommend the consideration of these electronic states in the analysis of the N 2 spectra at these energies even those located in the FC region. In the near future, we will be computing the nonadiabatic couplings between these electronic excited states.

This work should motivate new experimental investigations dealing with N 2 , especially the gerade states using, for instance, multiphoton absorption techniques. We could also suggest the study of the emission spectra of electric discharges established in supersonic jets, where one may observe simultaneously N 2 emitting systems of any spin multiplicity, rotationally cold, similar to those allowed the identification of Herman's quintet system.

Table1: Excitation energy (T e , in cm -1 ), equilibrium distance (R e , in Å), rotational constants (B e , α e ; in cm -1 ), harmonic wavenumbers (ω e , in cm -1 ) and anharmonic terms (ω e x e , ω e y e , in cm -1 ) of the valence-

  are calculated at 1637.9, 4727.1 and 8116.86 (in cm -1 ), respectively.

Figure captions:Figure 1 :

 1 Figure captions:

Figure 2 :

 2 Figure 2: Potentials of the electronic states correlating to the N( 4 S u ) + N( 4 S u ) (in A), N( 4 S u ) + N( 2 D u ) (in B), N( 4 S u ) + N( 2 P u ) (in C) and N( 2 D u ) + N( 2 D u ) (in D). These PECs can be sent upon request.

Figure 3 :Figure 4 :

 34 Figure 3: Evolution of the spin-orbit integrals. These curves can be sent upon request

Figure 5 :

 5 Figure 5: Interactions of the 1 3 Σ g -, 1 1 Γ g and 2 3 Σ g -states with the close lying states.

Figure 1 14 Figure 2 Figure 5

 1425 Figure 1

  Rydberg states of N 2 . Second entry corresponds to the data from[33]. For the quintets located at these energies, readers are referred to Ref.[16].

		State	T e	R e	B e	α e	ω e	ω e x e	ω e y e
		a' 1 Σ u	-	68152.66 69032	1.2755 1.278	1.4799 1.4725	0.0166 0.0166	1530.25 1523.6	12.0747 11.91	0.028
		a 1 Π g	69283.06 69971	1.2203 1.225	1.6169 1.6034	0.0179 0.0178	1694.20 1687.5	13.949 13.91	0.0183
		w 1 ∆ u	72097.4 73494	1.268 1.271	1.498 1.4910	0.0166 0.0160	1559.26 1559.1	11.63 12.39	0.154
		G 3 ∆ g	87900 89721	1.6107 1.615	0.9280 0.9224	0.0161 0.0167	742.49 749.6	11.85 11.74	-0.17
		Inner well a)	95914	1.105 1.9704 0.100
	a'' 1 Σ g	+
		Outer well	90521	1.558 0.9915 0.010	933.9	-2.16


L Malegat

H Bachau

A Hamido

B Piraux

Analysing a two-electron wavepacket by semiclassically propagating its Fourier components in space

Keywords: numbers: 32.80 RM, 32.80.Fb, 42.65Ky

In the last few years, the development of high order harmonic generation sources and free electron lasers delivering ultra-intense and ultra-short VUV-XUV pulses has made it possible to study non linear processes in atoms and molecules on the electronic time scale. The theoretical support required by the ongoing experiments comes notably in the form of numerical tools intended to solve the timedependent Schrödinger equation. The wavepacket produced in these approaches has a multichannel character and its analysis in terms of the observed physical channels is a problem in itself. Various solutions have been proposed so far, which all suffer from one or another inconvenience, ranging from very heavy computational costs to the unability to characterize differential cross sections. The purpose of this paper is to propose a new, low-cost and complete method of analysis. It consists in propagating the Fourier components of the wavepacket with respect to the hyperradius all the way to the genuine asymptotic region where the various channels disentangle from each other based on their kinematics. We demonstrate the feasibility and versatility of this proposal by applying it to two different time-propagation codes in the case of one-photon double ionisation of helium using short pulses.

Introduction

The description of the dielectronic continuum is a long-lasting challenge in computational atomic and molecular physics. This is so because the standard method of collision theory, which would mean selecting the double continuum component of a short range multichannel wavefunction by imposing the asymptotic condition pertaining to this specific channel, has remained untractable until now. Indeed, although an accurate asymptotic representation has become available with the acknowledged BBK [1] function also referred to as the 3C function, it has not been possible so far to match it to an accurate finite range representation at an appropriate distance. By-passing strategies have therefore been proposed which proceed in two stages. First, an accurate multichannel wavefunction or wavepacket including double continuum contributions is generated over an extended spatial region without introducing explicit asymptotic conditions; second, it is analyzed in terms of the various contributing channels, in order to extract the double continuum one.

Two of these strategies use stationary perturbative approaches to provide stationary wavefunctions located in the double continuum. The external complex scaling (ECS) method (see [2] for a review) maps an outgoing wave boundary condition into a vanishing wave one beyond a finite distance; then, the transition amplitude to the double continuum is computed following a standard method of collision theory in terms of the computed multichannel wavefunction and a pair of well chosen distorted waves. The hyperspherical R-matrix with semiclassical outgoing wave (HRM-SOW) method [3] propagates the wavefunction hyperradially from a hyperradius of the order of a few tens a.u. to very large ones modelling the hyperradial motion by a semiclassical outgoing wave; in this case, the very large distances reached allow one to identify the various channels directly from their kinematics exactly as in an experimental situation. On the other side, the time-dependent close coupling (TDCC) method [4] uses a time-dependent non-perturbative approach to generate a wavepacket that includes stationary components located in the double continuum; then, the wavepacket at the final propagation time is projected onto a pair of uncorrelated Coulomb functions taken as an asymptotic representation of the double continuum.

The merit of these approaches has been to provide accurate estimations of the various cross sections attached to the fundamental processes of electron-impact ionization (e, 2e) and one photon double ionization (γ, 2e) right at the turn of this century [5,6,7]. Their comparable successes have not allowed to establish any definite advantage of any of them over the others -except that the HRM-SOW method is best suited to the very low energy range [8]. In recent years however, the double continuum problem has experienced a revival in connection with the development of new XUV sources, notably high order harmonic generation (HOHG) sources [9,10] or free electron lasers (FEL) built against accelerators [11,12]. The high intensity of the pulses delivered has opened the new domain of few-photon processes in the XUV. In addition, their short duration makes it now possible to follow the electronic dynamic in real time. Pioneering measurements of the cross section for the (2γ,2e) process in He have already appeared [13,14,15,16] calling for theoretical support. Owing to the interest in short pulses, this support comes mainly in the form of time-propagators of dielectronic wavepackets. This in turns renews the interest into methods devoted to the analysis of such multichannel wavepackets. We do not pretend here to give an exhaustive review of what has been attempted in this domain. Instead we focus on the proposals which looks the most promising to us, since they all attempt, although in very different ways, to account for the asymptotic behaviour of the double continuum which is the specific property that definetely distinguishes it from the single continua it is degenerate with.

The most popular of these methods is the one used in the TDCC approach cited above but also in many other recent works (see for instance [17]), which consists in projecting the wavepacket on a pair of Coulomb waves also referred to as a 2C function. We will refer to this method in the following as the projection method. It should first be noted that the asymptotic behaviour of the double continuum is given by the 3C function, not by the uncorrelated 2C one, and that these different representations may result in different predictions as shown in [18] in the context of lowest order timedependent perturbation theory applied to very short pulses. Moreover, this use of Coulomb functions to extract information for single and double ionization has been recently discussed in [19]. There it was pointed out that the projection should be made at a time late enough for the wavepacket to have reached the region where these Coulomb functions are assumed to be reasonable approximations of the physical asymptotic condition. It should finally be noted also that the multichannel wavepacket includes fast electrons in single ionization channels in addition to the slow electrons in the double ionization channel. Therefore care must be exercized to avoid contamination of the wavepacket by unphysical reflections of the fast electrons on the box boundaries before the slow doubly ionized electrons reach the relevant asymptotic zone. This can be fixed by implementing some absorbing potential at the boundaries, checking that the results are independent of the absorbing potential parameters. Yet there remains that this method requires a large propagation time hence a large spatial domain of propagation which makes it very demanding in terms of computationnal ressources [20,21]. This makes alternative methods desirable.

One such alternative is provided by a generalization of the stationary ECS method. Here, the Laplace transform of the wavepacket for the energy E, defined from the end of the pulse, is shown to satisfy the driven stationary Schrödinger equation having as a source term the wavepacket right at the end of the pulse [22]. Then, one is back to the standard ECS method, and a transition amplitude can be computed from the solution of the driven equation for the energy of interest. The distorted waves involved in this transition amplitude are Coulomb waves with Z=2 the orthogonality of which to all single ionization channels being essential to the success of the method. Yet for this orthogonality property to hold, the spatial region used has to be large enough to accomodate all excited ionic states that could be significantly populated in the process, compared to the double ionization channel. Otherwise, the double ionization channel might well be contaminated by those ill-represented single ionization channels. This in turn is likely to result in high computational requirements.

Another alternative is provided by the J matrix method [23,24,25,26], in which an exact projector on the single continua is set up, which allows to subtract these channels from the time-evolved wavepacket. An essentially exact double ionization probability follows. The only drawback of this method being that it does not provide differential cross sections so far.

The purpose of the present paper is to propose yet another alternative to the well known projection method. It consists in adapting the stationary HRM-SOW package to the wavepacket analysis problem using a specific Fourier transformation in the same spirit as in the ECS work discussed above. The resulting method is very cheap computationnaly, it provides total as well as differential cross sections, and it is particularly well adapted to the very low energy domain. This is why we believe it is timely in the present context. Here, for a start, we demonstrate its feasibility and accuracy in the textbook case of single photon double ionization (SPDI) of helium. The paper is organized as follows. Section 2 is devoted to a short reminder of the elements contained in the stationary HRM-SOW package. In section 3, we present the Fourier transformation which must be applied to the wavepacket in order to define stationary components eligible for a treatment based on the tools presented in section 2. Section 4 is intended to make things more concrete to any reader interested in implementing this technique: it describes the tasks one has to perform to match a time-dependent treatment to the stationary methods defined above, the details of which are given in the appendix. Illustrative results are given in section 5. The concluding section 6 summarizes the advantages of this method and indicates directions for further work. Atomic units are used unless otherwise stated.

Stationary package for the analysis of multichannel wavefunctions

Before we present the contents of our stationary package, let us define, for clarity, the notations we use for the two-electron systems considered: r 1,2 are the radial coordinates of the two electrons and R = r 2 1 + r 2 2 is the hyperradius; as to the angles, Ω 1,2 = (θ 1,2 , ϕ 1,2 ) denote the spherical angles of the two electrons, α = tan -1 (r 1 /r 2 ) is the radial correlation angle, and Ω 5 is a collective notation for the five angles (α, Ω 1 , Ω 2 ). Accordingly, Ψ(R, Ω 5 ; t) denotes a 6D wavepacket, and Ψ(R, Ω 5 ; E) a 6D wavefunction. The field-free atomic Hamiltonian is written H at .

There are three items in the stationary package we use. Each of them applies to the restriction of the stationary wavefunction to some specific hypersphere. The adiabatic partial wave analyzer and the semiclassical hyperradial propagator are both applied at the same distance R 0 , of the order of a few tens. The projector on the n th ionic state applies at a larger distance R n 10 2 r n , where r n is the range of the n th hydrogenic orbital of He + . We give below a short description of these tools, refering the reader to published work when possible.

The adiabatic partial wave analyzer is used to strip the lowest single ionization (SI) channels from the wavefunction taken at R 0 . To do that, it suffices to expand Ψ(R 0 , Ω 5 ; E) in the particular 5D angular basis formed by the eigenfunctions Φ λ (R 0 ; Ω 5 ) of the fixed R atomic hamiltonian H at (R 0 , Ω 5 ), which we refer to as adiabatic partial waves. The reason behind is that for large enough R 0 , the lowest eigenfunctions of H at (R 0 , Ω 5 ) can be identified with the lowest SI channels. This is easily understood from the structure of the atomic hamiltonian

H at (R 0 ; Ω 5 ) = 1 2R 2 0 T (Ω 5 ) - Z(α, θ 12 ) R 0 , where (1)
Z(α, θ 12 ) = Z cos α + Z sin α - 1 √ 1 -sin 2α cos θ 12 ,
which is the sum of two terms. The first involves an angular kinetic energy operator T (Ω 5 ). The second is the 3-body Coulomb potential expressed in terms of the charge Z(α, θ 12 ) that depends on the shape of the e-core-e triangle characterized by α and the angle θ 12 between the ejection directions of the two electrons, Z being the nuclear charge. This charge has the well known shape of a saddle consisting in a wide plateau around the so called saddle point at α = π/4 and θ 12 = π, with two repulsive singularities around α = π/4 and θ 12 = 0 or 2π, and two attractive wells around α = 0 or π/2. The eigenfunctions associated to the lowest eigenvalues are obviously located deep into these attractive wells and accordingly, they can be viewed as eigenfunctions of the Hamiltonian's expansion around α = 0 which, for large enough R 0 , reduces to a sum of three terms:

H at (R 0 ; Ω 5 )------→ R 0 → ∞ α → 0   - 1 2
∂ 2 ∂r 2 2 + 2 2 2r 2 2 - Z r 2   + r 2 cos θ 12 R 2 0 - (Z -1) R 0 , (2)
where 2 is the orbital angular momentum of the bound electron 2. The first of these terms is the Hamiltonian of the He + ion, the second is the interaction between the dipole of the ion and the electric field created by the outer electron sitting a distance R 0 apart, and the last one is the energy of the outer electron in the electric field of the ion -it being noted that the resulting hamiltonian (2) is exactly solvable in parabolic coordinates. This short discussion makes the physical meaning of the lowest eigenfunctions appear: they can indeed be identified with the lowest SI channels as announced above. To check this interpretation, we compare in table 1 the lowest adiabatic eigenvalues E λ (R 0 ) obtained by numerically diagonalizing the hamiltonian (1) and those obtained from

E n n 1 n 2 (R 0 ) = - Z 2 2n 2 + 3 2 n Z (n 1 -n 2 ) 1 R 2 0 - (Z -1) R 0 ,
which gives the exact eigenenergies of the approximate hamiltonian (2) as a function of the parabolic quantum numbers n 1 and n 2 and the principal quantum number n. The good agreement observed between the two approaches for the four lowest eigenvalues shows that, even for the small hyperradius selected R 0 = 25, expanding Ψ(R 0 , Ω 5 ; E) on the adiabatic angular basis and deleting the contributions of the four lowest partial waves is a practical way to get rid of the two lowest SI channels.

Table 1. Lowest adiabatic eigenvalues E λ (R 0 ), compared with the Stark sublevels E n n1 n2 (R 0 ) of the He + n states perturbed by an electron a distance R 0 apart, for n=1 to 3 and R 0 =25. The origin of energies is taken at the DI threshold Note in addition that the adiabatic analyzis applied to a stationary function at energy E allows to distinguish open channels (E λ (R 0 ) < E) from closed ones (E λ (R 0 ) > E), which will be neglected in the further hyperradial propagation.

n n 1 n 2 E n n1 n2 (R 0 ) E λ (R 0 ) λ 1 0 0 -2.0400 -2.
The semi classical hyperradial propagator P E (R 0 , R 1 ) has been described in [27] and we refer the reader to this paper for details. For the present purpose, we only need to know what this propagator does, and under which conditions it can be used safely.

So let us first mention the task it performs: as input, it takes an eigenfunction Ψ(R 0 , Ω 5 ; E) of H at for the energy E on some inner hypersurface R = R 0 ; as output it delivers this same eigenfunction on some outer hypersurface of increased hyperradius R 1 > R 0 . The point is that while R 0 is usually of the order of a few tens, R 1 can reach values as high as 10 6 or even 10 7 if needed, whereas the norm is conserved to an excellent precision. That is to say, the stationary solution can be propagated up to the genuine asymptotic region. Now the key issue for this propagator to work is the following: it should be possible to describe the bulk of the hyperradial motion by a unique semi classical outgoing wave. For the multichannel continuum states of interest here, this implies that the escape speed of the emitted electrons does not vary a lot from one open break-up channel to another, a condition that is not satisfied in general. In the case of helium, in particular, the thresholds I + n for single ionisation leaving He + in the n th state (SI n ) form a Rydberg series that converges to the DI threshold I 2+ at 2.9. The lowest term of the series, at 0.9, is well below I 2+ , and accordingly, it seems unrealistic to describe the fast electrons in the SI 1 channel and the slow electrons in the DI channel by a common semi classical outgoing wave. On the other side, the SI n≥3 and DI form a bunch of closely-spaced channels for which the definition of an averaged electronic speed makes sense. As a result, projecting the SI n<3 channels out of the stationary wavefunction Ψ(R 0 , Ω 5 ; E) is a pre-requisite for applying the semi classical hyperradial propagator. To perform this task, it suffices to project this wavefunction on the basis of adiabatic angular partial waves at R = R 0 , as explained above.

The semiclassical outgoing wave is then defined in terms of a local momentum p(R) = 2(E + Z ef f (R)/R) where the effective charge Z ef f (R) is interpolated between Z ef f (∞), which is is taken equal to the saddle point charge Z S = Z(π/4, π) = 4.95, and Z ef f (R 0 ) = Z 0 , which is obtained from the mean value of p(R) within the solution at R 0 . In the present calculations, with R 0 = 25 and the SI n<3 channels subtracted, Z 0 turns out to be very close to -yet slightly larger than Z S , which is physically satisfying.

The projector on the n th ionic state, noted P n , projects the wavefunction on the subspace in which one electron is in the n th hydrogenic state of He + -this being done at fixed R = R n . It thus determines the SI n channel. It is used to strip the higher SI channels, which have not been eliminated by the adiabatic analyzis at R 0 , from the wavefunction in the course of its hyperradial propagation. Again we refer the reader to [27] for more details.

Finally, the DI channel is obtained by applying the three tools described above to the wavefunction at R 0 according to the following sequence

Ψ 2+ (R nmax , Ω 5 ; E) = nmax n=1 (1 -P n ) P E (R n-1 , R n ) 1 - 4 λ=1 |Φ λ Φ λ | Ψ(R 0 , Ω 5 ; E)
In other words, the adiabatic analyzis applied at R 0 eliminates the two lowest SI channels, making the resulting wavefunction eligible for propagation. Then, the propagator takes the wavefunction to R 1 , where every trace of the SI 1 channel is eliminated by the projector 1 -P 1 before moving to R 2 etc...up to the point where we are left with an essentially pure DI channel.

Note that in this approach, each channel is extracted at a distance where it decouples from the rest of the wavefunction, so that its outgoing flux is converged. Then, the latter provides the most direct and accurate estimate of the corresponding ionization yield.

The local Fourier transformation

Now consider a two-electron wavepacket excited at time -T by a pulse of duration T and time-propagated on a finite 2D radial region r 1 , r 2 < r max up to a time T max such that no reflection has occurred yet. The question is: is it possible to apply the above reviewed stationary formalism to this wavepacket? The answer is: yes, provided we can define, within the r 1 , r 2 < r max box, a hypersphere R = R 0 satisfying the two following conditions: (i) it is reached by the wavepacket only after the end of the pulse; and (ii) it is entirely crossed over by the wavepacket before the end of the propagation. This we can summarize by

Ψ(R 0 , Ω 5 ; t) = 0 only for 0 ≤ t i < t < t f ≤ T max . (3)
In other words, the evolution of the wavepacket on the hypersphere is governed by the field free Hamiltonian H at :

ı ∂ ∂t Ψ(R 0 , Ω 5 ; t) = H at (R 0 ; Ω 5 ) Ψ(R 0 , Ω 5 ; t). (4)
We then define the Fourier transform of this wavepacket on the hypersphere by

Ψ(R 0 , Ω 5 ; E) = 1 √ 2π +∞ -∞ dt Ψ(R 0 , Ω 5 ; t) exp ıEt = 1 √ 2π t f t i dt Ψ(R 0 , Ω 5 ; t) exp ıEt . (5)
The action of H at on this Fourier transform is established through the sequence of elementary operations below:

H at (R 0 ; Ω 5 ) Ψ(R 0 , Ω 5 ; E) = 1 √ 2π t f t i dt [H at (R 0 ; Ω 5 ) Ψ(R 0 , Ω 5 ; t)] exp ıEt = 1 √ 2π t f t i dt ı ∂ ∂t Ψ(R 0 , Ω 5 ; t) exp ıEt = 1 √ 2π ı Ψ(R 0 , Ω 5 ; t) exp ıEt t f t i -ıE t f t i dt Ψ(R 0 , Ω 5 ; t) exp ıEt = EΨ(R 0 , Ω 5 ; E)
which takes advantage of the time-independence of H at , the time-evolution equation ( 4), and the conditions (3) which define the hypersphere. It demonstrates that the local Fourier transform (5) for the energy E is a solution of the stationary field-free Schrödinger equation for this particular energy. As such, it is eligible for a treatment based on the stationary tools described in the previous section. Note that the present approach, like that used in [22], applies a stationary method to a Fourier transform of the wavepacket. The stationary methods used in each case both circumvent the need for explicit DI asymptotic boundary conditions, yet in very different ways: as a result, the external complex scaling method used in [22] yields a fully quantum solution over a finite box, whereas the present approach provides a mixed semiclassical × quantum solution up to quasi macroscopic distances.

Implementation

We have investigated the feasibility of this proposal in the framework of two different time-propagation schemes of the spectral type using either B-splines [28] or Sturmian [25] radial basis functions. In both cases, the characteristics of the pulse are the following

E(t) = E 0 sin πt T 2 sin ωt for -T < t < 0, I = 10 13 Wcm -2 (E 0 = 0.053), N cycles = 6 , ω = 3.2,
resulting in the temporal and spectral profiles shown in figure 1. In addition, we take as a test case the one-photon processes exciting a 1 P o wave from the ground 1 S state of helium as announced in the introduction. The first task is to determine some tentative value of the critical hyperradius R 0 in view of the conditions (i) and (ii) established in the previous section. The lower bound for R 0 is given by the distance reached by the fast SI 1 electrons by the end of the pulse, i.e. R min = 2(ω -I + 1 ) × T . The upper bound is given by the distance reached by the slow DI electrons by the end of the propagation. As these DI electrons share the excess energy above threshold continuously, their speeds vary from 0 to 2(ω -I 2+ ). Yet it should be recalled that they are emitted as pairs, every zero energy electron being accompanied by another one carrying the maximum energy, yielding a symmetric energy distribution. As theory accounts for this symmetry, we can restrict ourselves to the upper half range of speeds from

√ ω -I 2+ to 2(ω -I 2+
). The best evaluation of the upper bound to R 0 would then be R max = √ ω -I 2+ × (T + T max ), and a cruder one R max = 2(ω -I 2+ ) × (T + T max ). The characteristics of the pulse used here were chosen to ensure that R min ≤ R max , which is the weakest condition for the existence of an appropriate hypersurface. This was done considering the maximum possible size 50 × 50 of the 2D radial box used in the B-spline calculation and the need to avoid contamination of the wavepacket by early reflections of the fast SI 1 electrons. For the time being, let us just mention that with the pulse defined above and the propagation time T max =20 reached in the B-spline calculation, we get R min R max 25 which forces the choice of the matching hypersurface and lets us expect that some DI electrons will be lost. However, we'll see in the following that their contribution does not seem to be significant.

Having identified a possible matching hypersurface, we must express the wavepacket on this hypersphere in terms of the 5D angular representation that emerges from the initial 6D representation by setting R = R 0 . Next, we have to monitor the flux of the wavepacket throughout this hypersphere as a function of time to check that it vanishes at t i ≥ 0 and t f ≤ T max as required. Having satisfied this condition, we may define the local Fourier transform on this hypersphere -for any energy in the spectral bandwidth of the pulse. To finish, we express this Fourier transform in the adiabatic partial wave representation provided by a previous diagonalization of H at (R 0 ; Ω 5 ) within the 5D angular representation used in HRM-SOW calculations [7,29]. To monitor the accuracy of the various changes of basis involved in this operation, we define a norm on the hypersurface and control its conservation. Although trivial in principle, these tasks must be performed with special care: accordingly, details are given in the appendix A in the B-spline case chosen for the sake of illustration.

Illustrative results

Feasibility

The feasibility of our proposal is entirely dependent on the existence of a hypersphere satisfying the conditions (3). We have investigated it, as announced before, using two different time-propagation methods. In both cases, the wavepacket is expanded on bipolar harmonics

Y L0 1 2 (Ω 1 , Ω 2 ) with L, 1 , 2 ≤ 3.
The 2D radial dependence is expanded either on a 2D Sturmian basis including up to 100 functions sharing the same non linear parameter κ = 2, or on a 2D B-spline basis comprising 60 functions of order 8 defined on a linear sequence of knots spanning a 2D radial box of dimension r max =50. In the Sturmian case, propagation is performed directly in the basis presented, whereas in the B-spline one, it takes place in the basis of eigenfunctions of the atomic hamiltonian.

Figures 2 and3 display the flux per unit time F (R 0 , t) and per unit energy F (R 0 , E) (A.4) as well as the time-accumulated G(t) and energy-accumulated flux G(E) (A.5). The first two of these quantities, which are homogeneous to an inverse time and an inverse energy respectively, are obtained in a.u., the last two are dimensionless probabilities. However, for the sake of comparison with other data, we have chosen to divide all these flux by the time-integrated photon flux 3IT /(8hω) expressed in (kb) -1 , where the factor 3/8 accounts for the temporal profile of the pulse. This way, the timeand energy-integrated flux will converge to quantities having the dimension of cross sections expressed in kb, the conversion factor N P →σ satisfying

σ tot (kb) = N P →σ × G(t f ) = N P →σ × G(E f ) where N P →σ = 7.65 10 19 × ω 2 N cycles I W cm -2 .( 6
)
In fact, our pulse does not include enough cycles to simulate the quasi stationary limit with accuracy. The results below will provide a proof of this statement. Therefore, the use of cross section units should be taken as a shortcut to facilitate qualitative comparisons with long pulse results and thereby check that there are no systematic errors in our method. Figure 2(a) thus shows the instantaneous flux F (R 0 , t) of the wavepacket through the hypersphere R 0 = 25 computed from both the B-spline and the Sturmian approaches. The corresponding two curves on figure 2(a) are almost undistinguishable up to t = 12. There, reflections occur in the Sturmian basis, leading to the abrupt decrease of the flux shown in the inset. The reason is that Sturmians are not well adapted to the description of the fastest electrons oscillating rapidly at large distances. By contrast, the more versatile B-spline basis, which provides a uniform description of the finite box considered, leads to a regular decrease of the flux. The latter goes down to zero before reflections occur. So in that case, we can state that the conditions required (see (3)) are satisfied for the hypersphere considered: namely the flux is zero at t i = 0, right after the end of the pulse, as well as at t f = 20, before the start of reflections. Accordingly, we restrict the discussion to the B-spline approach in what follows.

The main peak at short times in figure 2(a) corresponds to the arrival of the fastest and most numerous electrons delivered by the SI 1 process. The support of this peak is of the order of the pulse duration that is equal to 11.78. But this peak is markedly asymmetric: its long tail at large times is formed by the less numerous and slower electrons delivered by the SI n>1 and DI processes. The renormalized time-integrated flux G(t) in figure 2(b) converges to a cross section of 594 kb.

To complete our demonstration of feasibility, we now compute the local Fourier transform of the wavepacket according to (5), as well as the associated flux F (R 0 , E). This we do for each energy in the spectral bandwidth of the pulse. Figure 3(a) shows that the ionization probability per unit energy and the spectral profile of the pulse are very similar in shape. This results from the relatively slow variation of the ionization cross section within the pulse bandwidth [30]. The renormalized energy-accumulated flux G(E) on figure 3

Evaluation

First of all, we wish to recall that the aim of this paper is not to get more SPDI cross sections for He, since a very large amount of accurate theoretical and experimental data is available on this subject in the literature, as recalled in the introduction. It is instead to test the accuracy of the new method we propose for analyzing a wavepacket as carefully as possible. In this regard, it should be noted that the literature data regarding SPDI of He consider the interaction with the very long pulses delivered by synchrotron facilities, which can be treated in the quasi stationary approximation. In the present case, by contrast, the pulse used includes only 6 cycles, whereas it is generally agreed that the infinite pulse limit is not reached before N cycles = 10. As a result, we do not expect a perfect agreement between the present results and the well known literature on the subject. This is why we will restrict the comparisons made below to methods which differ from ours only by their analysis of the wavepacket.

More precisely, we will compare our approach, denoted by FT, with the usual one, denoted by WP, which implies the projection of the wavepacket at large times on either the product of an hydrogenic orbital of the ion and a Coulomb function of effective charge Z=1 (SI channels), or the product of two Coulomb functions of effective charge Z=2 (DI channel), that is to say on uncorrelated asymptotic representations. In practice, in the B-spline approach considered here, the functions one projects upon are calculated in the same B-spline basis as used for the time-propagation of the two-electron wavepacket, and the projection is made at t = 20. This time is the one at which unphysical backward reflected contributions enter the R 0 = 25 inner hypersphere, while the wavepacket is located outside this hypersphere. In other words, the wavepacket is likely to be slightly altered by these reflections. Moreover, it is not perfectly clear that it has reached the region where the uncorrelated asymptotic representations of the outgoing channels is assumed to become valid. By contrast, the FT approach uses the Fourier transform of the wavepacket on the hypersphere R 0 = 25, which is not affected by unphysical reflections. In addition, the stationary tools applied to this Fourier transform account for electronic correlation at all ranges. In this regard, it should be noted that polarisation and correlation effects might be significant in the present case, although the peak energy of the pulse profile, at 0.3 above the DI threshold or 3.2 above the He ground state, could be considered as high enough to make them negligible. This is because, due to the short duration of the pulse, the thresholds I + n≥2 to I 2+ are located well within the bandwidth of the pulse, thus giving rise to near threshold contributions very sensitive to polarisation and correlation effects. From this analysis, we conclude that we cannot expect a precise quantitative agreement between WP and FT, and that in case of disagreement, FT should be considered more reliable. Now remember from sections 2 and 4 that implementing the FT approach requires the previous knowledge of the adiabatic eigenvalues and eigenvectors produced at R 0 by a companion HRM-SOW calculation using the same number of electron angular momenta. We refer to this auxilliary calculation as ST. Instead of restricting it to the production of the above mentionned pre-requisites, we have carried it through to its end. Then, FT and ST differ only by the initial condition they use on the hypersurface R = R 0 : the Fourier transform of the wavepacket in FT, the solution of the 1 st order perturbation equation for ST. But from R 0 outwards, the same stationary tools are used in both cases to disentangle the various outgoing channels in the course of the hyperradial propagation. This is the reason why we compare below ST with the results noted EXP of experiments performed with synchrotron radiation: the purpose of this comparison is to assess the accuracy of the stationary tools used in ST and FT. (Note however that the level of agreement between ST and EXP may be less that what could be achieved if the constraints regarding R 0 and the maximum electron angular momentum were relaxed).

Partial integrated SI and DI cross sections

Before comparing the WP and FT cross sections, it is worth to consider dimension issues. In the WP case indeed, the wavepacket is normalized to 1 on the box, and so are the various representations of the exit channels it is projected on. Accordingly, its squared projections on these representations are dimensionless probabilities that can be turned into cross sections by multiplying by the factor N P →σ given in (6). In the FT case, by contrast, all predictions are based on the flux of the Fourier transform which has the dimension of an inverse energy, so that some energy integration has to be performed to recover a probability. This can be done either approximately, using as multiplicative factor N F E →P = 1.44 × ω/N cycles to account for the spectral bandwidth of the pulse, or exactly, using as multiplicative factor the ratio N F E →P between the WP probability and the FT probability per unit energy. In the following, we choose the second option. This way, the total ionization cross sections are the same in both cases, and we may focus on more significant sources of discrepancy between the two methods. We present in table 2 the total integrated ionization cross section as well as partial integrated cross sections for the SI 1,2 and DI channels at the peak of the spectral distribution of the pulse. The agreement between the ST and EXP results is satisfying enough to give us confidence into the performance of the stationary package we apply here to the wavepacket analyzis. Comparing now FT and WP, we note that the distribution of the outgoing flux among the different SI channels is a bit different, yet this does not seem to affect the DI channel. The disagreement between the two methods is maximum for the SI 2 channel where it amounts to 23%. This is considered as consistent with the different representations of the outgoing channels used in both approaches, as anticipated in 5.2. However, we expect that these discrepancies would disappear were the WP wavepacket free of spurious reflections and located within the alleged validity region of the uncorrelated asymptotic approximation of the double continuum. Note also the change in magnitude of the DI channel when passing from the short pulse case (WP and FT) to the infinite pulse limit (ST and EXP): this is an effect of the short duration of the pulse. Indeed, the DI threshold being located well within the spectral bandwidth of the pulse (see figure 1), a significant number of incoming photons is lost for this channel. This confirms that comparison with the infinite pulse literature on SPDI of He cannot be very accurate.

Energy differential DI cross sections

Figure 4 shows the DI energy differential cross section, also called the singly differential cross section (SDCS), as a function of the energy ratio E 2 /E of the energy of one electron to the total excess energy E above the DI threshold, for a photon energy of 87 eV. The surface below each curve, multiplied by E, is expected to be twice the integrated DI cross section given in table 2. This is so for the ST and FT treatments, but not exactly for the WP one. In this case indeed, the quantities emerging from the calculation are the probabilities P 1 2 (E 1 , E 2 ) for emitting one electron with energy E 1 and angular momentum 1 and the other with energy E 2 and angular momentum 2 , the energies sweeping across the set of values determined by the box description of the He + continuum. The total 2D energy distribution

P (E 1 , E 2 ) = 1 2 {P 1 2 (E 1 , E 2 ) + P 1 2 (E 2 , E 1 )} , (7)
summed over E 1 and E 2 and multiplied by the factor N P →σ , gives the cross section of table 2 back. But here, we proceed another way: we interpolate the 2D probability distributions P 1 2 (E 1 , E 2 ) on a common 2D grid of energies before we perform the summations in (7); then, we take P (E 2 , E -E 2 ) × N F E →P as a representation of the SDCS for excess energy E and electron energy E 2 . Using this approximate energy integration, we neglect the fact that part of the incoming photons are lost for the DI process, thus overestimating the DI signal. This being established, the most striking feature in figure 4 is the contrast between the oscillating ST and FT results and the essentially flat WP one: it seems that the oscillations appearing in FT are somehow smeared out in WP -which would appear as the perfect average of FT were it not for the slight overestimation discussed above. These oscillations indeed are an artefact produced by the semiclassical hyperradial propagation when the inner region is too small, which is the case here, due to the constraints inherent in the time-propagation calculations. They become negligible in magnitude as soon as all significant SI channels are accounted for by the fully quantum inner region treatment. This point was considered earlier [29], at least indirectly, in a convergence study of triply differential cross sections (TDCS) with the size of the inner region. It will be discussed in more detail in a forthcoming publication.

Energy and angle differential DI cross sections

In this section, we consider the kinematical situation studied in [31], which involves a photon energy very close to the central frequency of our pulse. In this experiment, the photon beam at 88 eV, which propagates along OZ, is polarized elliptically, either with a positive helicity and the main axis of the ellipse along OX, or with a negative helicity and the main axis of the ellipse along OY. One electron is detected along the diagonal of OX and OY, and the other at a varying angle in the XOY plane. We present in figure 5 the TDCS obtained for positive helicity. It of course depends only on the angle θ 12 between the two electrons. The right panel corresponds to a very assymetric sharing of the energy between the two electrons, while the left one corresponds to equal sharing. The focus in this figure is on the shape of the TDCS, not on its magnitude, for the following obvious reasons: the measurements are relative, the infinite pulse limit results ST and EXP yield significantly larger DI cross sections compared to the short pulse calculations FT and WP (see table 2), and the FT and WP results may differ in magnitude due to the unphysical oscillations noted in the FT SDCS (see figure 4). This is why all TDCS have been normalized to the ST result at the maximum of the peak. The striking feature is that the different approaches represented, be it ST, FT or WP, can hardly be distinguished from each other. Their agreement with experiment is very good and would certainly become perfect if the finite angular and energy resolutions of experiment were taken into account. It therefore seems that in this case, angular correlations are well accounted for by all methods studied.

Conclusion

We have presented a new technique to disentangle the various outgoing channels from a multichannel wavepacket and to compute the associated ionization yields, we have demonstrated its feasibility and compared its results with those provided by the popular projection method in the test case of SPDI of He. Trial calculations based upon a Bspline approach to the time-dependent problem have produced a variety of results in reasonable agreement with the data available for comparison, whereas calculations based on a Sturmian approach were shown to require untractably large basis sets to avoid early reflections of the wavepacket. Implementing this approach in conjunction with a gridbased time-dependent method should be feasible as well, the most cumbersome task being in this case the flux computation involving derivatives with respect to R. The advantage of the method is that it is much less demanding computationnally than the widespread projection method. The latter indeed requires to propagate the 6D wavepacket untill it reaches the asymptotic zone where its overlap with asymptotic uncorrelated representations of the DI channel makes sense. Recent calculations therefore consider increasingly large 2D boxes, up to 700 × 700 [20,21] for instance. In addition, spurious reflections of the fastest electrons in the SI 1 channel on the box boundaries must be avoided, a point that is not considered explicitly in the above publications. By contrast, the FT method only requires that a hypersphere be identified which satisfies the conditions (3). This being done, a 5D wavefunction is propagated with respect to R, a task that is orders of magnitude lighter than propagating a 6D wavepacket in time. For this reason, the asymptotic zone where the outgoing channels disentangle from each other geometrically can be reached to a low computational cost: note that propagating to 10 6 takes a quarter of an hour at 0.1 eV and less than one minute at 60 eV on a single NEC-SX8 vector processor. In addition, no reflection can occur since there is no underlying finite box involved, R being the propagation variable.

Further work will explore the following issues. First of all, different possibilities are already being explored to overcome the reflection problems met when using a Sturmian basis set in the time-propagation: (i) discarding the fastest electrons in the SI 1 channel right after the end of the pulse using the J-matrix technique; (ii) defining generalized Sturmian functions according to [32]. Meanwhile, we are developping the stationary package used here in the 1 S and 1 D e symmetries required by two-photon processes, in an effort to remedy the puzzling situation that prevails regarding the value of the two-photon double ionisation cross section in He [14]. Note also, as a side result of this study, that computing the outgoing flux of the wavepacket appears as a stringent test of possible unphysical reflections that could spoil the results extracted using whatever method one wishes. Note that the representation defined above, to be referred to as the initial representation on the hypersurface, has the dimension N ini = ( max + 1) × (n 0 + n 1 ), which is already much lower than that, ( max + 1) × n 2 , of the 6D representation it is extracted from according to (A.1).

Appendix A.2. Norm and flux

The norm of the wavepacket/Fourier transform on the hypersphere and its flux through this hypersphere are defined by

N (R 0 , x) = R=R 0 dS Ψ * Ψ F (R 0 , x) = -ı R=R 0 dS Ψ * ∂Ψ ∂R (A.4)
where the surface element dS = R 5 0 (sin α cos α) 2 dαdΩ 1 dΩ 2 . To obtain working expressions of these crucial quantities let us introduce the x-dependent complex vector d, that collects the coefficients d, along with its real and imaginary parts a and b, as well as the R 0 -dependent real matrices O, C and C, the elements of which are defined as which due to flux conservation does no longer depend on R 0 , will also be of interest in the following.

O II = dΣ f * I f I = 2δ δ R 0

Appendix A.3. Passage to the adiabatic representation

The last task is to express the local Fourier transform of the wavepacket in the adiabatic angular basis. Despite the sorting out of the basis vectors which contribute effectively on the hypersurface, the dimension N ini of the initial representation is by nature much larger than that, N ad = ( max + 1) × 2 × n α , of the adiabatic representation involving the same number of partial waves. This is due to the fact that the α basis is constructed directly as a 1D basis in the HRM-SOW approach whereas it appears as a subset of a 2D r 1 × r 2 basis in the context of time-propagation. The direct transformation between these two representations, involving a rectangular matrix that is far from being unitary, does not conserve the norm nor the flux. This is why an intermediate step is required.

It consists in diagonalizing and renormalizing the overlap matrix O thus defining a transformation matrix T such that T † O T = I. The coefficients vector e of the Fourier transform in the resulting orthonormal representation is then obtained by solving the linear system d = T e and the norm is given by N (R 0 , E) = e † e. The important point is that the norm turns out to be conserved to more digits than significant if the eigenvectors associated to the lowest eigenvalues of O are suppressed from the representation up to the point where the dimension is reduced to that of the adiabatic one. Let us then note

g k (R 0 ; Ω 5 ) = 1 R 2 0 sin α cos α k (R 0 ; α)Y (Ω 1 , Ω 2 ) ( A . 6 )
= 0 : max = 0 : 1 k = 1 : n α the basis vectors of this reduced orthogonal representation and ẽ the corresponding representative vector of the Fourier transform. Note that this representation and the adiabatic one are orthogonal representations of the same dimension. Accordingly, they are related by a unitary, hence norm and flux conserving transformation noted U .

For the sake of completeness, let us establish the expression of this transformation explicitly. To this end, we have to recall that the basis used in the HRM-SOW calculation reads [7,29] where I now stands for the set of indices { k}. Besides, the transformation matrix from this initial non-orthogonal basis to its orthogonal counterpart is T , and the rotation matrix from this orthogonal basis to the adiabatic basis is R. To complete our task, we still need the overlap matrix P between the non-orthogonal HRM-SOW basis (A.7) and the orthogonal time-propagation basis of the same dimension (A.6), the elements of which are

G I (R 0 , Ω 5 ) = 1 R 5/2 0 sin α cos α Ṽ k (α) Y (Ω 1 , Ω 2 ) ( A . 7 ) Ṽ 0 k (α) = 1 2 2 +2 (1 -z 2 ) +1 T 2(k-1) (z) k = 1 : n α (A.8) Ṽ 1 k (α) =
P JI = 2δ δ R 0 π 4 0 dα ṽ k Ṽ k
The vector F , which represents the Fourier transform in the adiabatic representation and provides the initial condition for the stationary treatments presented in section 2, is then given by:

F = R † T † P † ẽ

Figure 1 .

 1 Figure 1. (a): Temporal profile E(t) of the pulse, t being measured with respect to the end of the pulse. (b): Spectral profile of the pulse F(E) = ∞ -T E(t)e ıEt dt 2 , E being measured with respect to the He ground state; the arrows indicate, from left to right, the positions of the ionization thresholds I + 2 , I + 3 , I 2+ .

Figure 2 .

 2 Figure 2. Flux per unit time (a) and time-accumulated flux (b) through the hypersurface R = R 0 as a function of time from the B-splines wavepacket. These quantities are renormalized by the factor (6) yielding the accumulated flux in units of cross sections (kb). The origin of times is at the end of the pulse. The results from the Sturmian wavepacket are plotted in red in (a), where the inset enlightens the sudden change of slope of the Sturmian flux revealing the occurence of a reflected flux.

Figure 3 .

 3 Figure 3. Flux per unit energy (a) and energy-accumulated flux (b) through the hypersurface R = R 0 as a function of energy from the B-splines wavepacket (continuous black). These quantities are renormalized by the factor (6) yielding the accumulated flux in units of cross sections (kb). The origin of energies is at the DI threshold, marked by a vertical line. The dashed black line on (a) is the spectral profile of the pulse, renormalized to the maximum of the flux.

Figure 4 .

 4 Figure 4. Energy differential DI cross section in kb/eV as a function of the ratio of the energy of one electron and the total excess energy available, for a photon energy of 87 eV. Full line = FT; dashed line = WP; dotted line = ST.

Figure 5 .

 5 Figure 5. Energy and angle differential DI cross section (TDCS) in b/(eV sr 2 ) as a function of the inter-electronic angle in degrees for the geometry recalled in the text and for positive helicity. Left panel: E 1 /E 2 = 1; right panel: E 1 /E 2 = 8. Full line: FT; dashed line: WP; dotted line: ST; circles with error bars: EXP [31].

π 4 0

 4 dα ũ k ũ k , C II = dΣ f * where I is a shortened notation for ( , , k ) and the f I are the basis vectors (A.3) of the initial representation. The norm and flux then reads N (R 0 ; x) = a † Oa + b † Ob and F (R 0 ; x) = a † Cb -b † Ca The accumulated flux G(x) = x xstart F (R 0 ; x )dx (A.5)

1 2 2

 2 +1 (1 -z 2 ) +1 U 2k-1 (z) k = 1 : n α (

Table 2 .

 2 Total and partial integrated cross sections (in kb) at 87 eV photon energy.

		WP FT ST	EXP [30]
	σ tot 594 594 589 570 ± 9
	σ + 1	530 520 520 510 ± 10
	σ + 2	41	53	43.7 41.5 ± 2
	σ 2+ 5.7	6	7.42 7.1 ± 0.5

Acknowledgments

This work was granted access to the HPC resources of IDRIS under the allocation 2010-082147 made by GENCI (Grand Equipement National de Calcul Intensif). It is also partially supported by the european COST Action CM0702.

Appendix A. Detailed implementation

Appendix A.1. 5D angular representation on the hypersphere In the B-spline approach, the wavepacket is expanded on the eigenstates of the atomic Hamiltonian provided by a previous diagonalization of H at within a mixed B-splines × bipolar harmonics basis set. Accordingly, the 1 P o component of the wavepacket/Fourier transform at R 0 is provided by

where the variable x denotes either t or E, respectively. Y (Ω 1 , Ω 2 ) is the shorthand notation for the gerade ( = 0) and ungerade ( = 1) bipolar harmonics

and the α-depending functions are given by

where r 1 = R 0 cos α and r 2 = R 0 sin α, the B i being B-spline basis functions. The coefficients appearing in (A.1), which read

involve the expansion coefficients γ n ij of the wavepacket at the end of the pulse on the ij components of the n th eigenstate of H at , and the time -or energy-oscillating phase factors Γ n (x) attached to this eigenstate,

e +ı(E-En)t dt.

These cumbersome but mandatory notations being defined, we reorganize the summations in (A.1) in view of the passage to the adiabatic representation to be performed next for x = E. To this end we note that (i) u 1 jj ≡ 0; (ii) u ji (R 0 ; α) = (-1) u ij (R 0 ; α); and (iii) that each B i has a finite local support. Point (iii) implies that for most pairs of indices (i, j), ũ ij (R 0 ; α) is identically zero on the useful α interval [0, π 4 ]. After sorting out, the effectively contributing basis vectors ũ ij (R 0 ; α) are labelled by k = 1 : n , and to each of them, the arrays i (k ) and j (k ) associate the proper pair of B-spline indices (i, j). These tasks being performed, one can rewrite the wavepacket/Fourier transform as

the coefficients d k (x) being given by

δ n 0k 0 = γ n jj with i 0 (k 0 ) = j = j 0 (k 0 )

δ n 0k 0 = γ n ij + γ n ji with i 0 (k 0 ) = i = j = j 0 (k 0 )


Scalable Distributed Schur Complement Methods for CFD Simulation on

Many-Core Architectures

List of authors:

A. Basermann1

H.-P. Kersken2

At the German Aerospace Center (DLR), the parallel simulation systems TAU [1] and TRACE [2] have been developed for the aerodynamic design of aircrafts or turbines for jet engines. Largescale computing resources allow more detailed numerical investigations with bigger numerical configurations. Up to 50 million grid points in a single simulation are becoming a standard configuration in the industrial design. Both CFD solvers, TAU and TRACE, require the parallel solution of large, sparse real or complex systems of linear equations.

For the parallel iterative solution of sparse equation systems to be solved within the TAU or TRACE solvers, FGMRes [START_REF] Saad | A flexible inner-outer preconditioned GMRES algorithm[END_REF] with Distributed Schur Complement (DSC) preconditioning [START_REF] Saad | Distributed Schur complement techniques for general sparse linear systems[END_REF] for real or complex matrix problems has been investigated.

The DSC method requires adaquate partitioning of the matrix problem since the order of the approximate Schur complement system to be solved depends on the number of couplings between the sub-domains. Graph partitioning with ParMETIS [START_REF] Karypis | ParMETIS: Parallel graph partitioning and sparse matrix ordering library[END_REF] from the University of Minnesota is suitable since a minimization of the number of edges cut in the adjacency graph of the matrix corresponds to a minimization of the number of the coupling variables between the subdomains. The latter determine the order of the approximate Schur complement system used for preconditioning.

Matrix permutations like Reverse Cuthill-McKee (RCM), Minimum Degree (MD) or Nested Dissection are employed per sub-domain in order to reduce fill-in in incomplete factorizations which are part of the DSC preconditioner. These reordering methods together with a threshold strategy for incomplete factorizations decrease the costs of local approximate LU decompositions within the DSC method (ILUT).

For the solution of TAU or TRACE linear equation systems, we developed a parallel iterative FGMRes algorithm with DSC preconditioning. In [START_REF] Basermann | Parallel solution techniques for sparse linear systems in circuit simulation[END_REF] and [START_REF] Alrutz | HICFD -Hocheffiziente Implementierung von CFD-Codes für HPC-Many-Core-Architekturen[END_REF], we demonstrated the superiority of the DSC preconditionier over (approximate) block-Jacobi preconditioning. Block-local preconditioning methods like block-Jacobi are the standard preconditioners in TRACE. In [START_REF] Basermann | Parallel iterative solvers for sparse linear systems in circuit simulation[END_REF], we described and demonstrated the effect of matrix (re-)partitioning and reordering on the DSC algorithm in detail.

In the following, we particularly discuss numerical and performance results of DSC methods for typical complex TRACE CFD problems on many-core architectures. both for preconditioner preparation and for the total DSC solver. This is caused by the lower problem order and a more advantageous matrix structure in the complex case opposite to the real case. In addition, the complex formulation results in higher data locality (storage of real and imaginary part in adjacent memory cells) and a better ratio of computation to memory access due to complex arithmetics in comparison with the real formulation. Fig. 1 also shows an advantageous strong scaling behavior of the DSC method on the many-core cluster, even for this small matrix problem.

Fig. 2, left, illustrates the strong scaling behavior of the total complex DSC method on 4 to 192 processor cores of the AeroGrid cluster for a medium size complex TRACE matrix problem of order 378,400 and with 45,456,500 non-zeros.

Fig. 2, right, shows execution times of the total complex DSC method on 32 to 192 processor cores of the AeroGrid cluster for a large complex TRACE matrix problem of order 4,497,520 and with 552,324,700 non-zeros. In order to achieve the required accuracy in each component of the solution vector the FGMRes iteration was here stopped when the current residual norm divided by the initial residual was smaller than 10 -10 .

Figs. 1 and 2 demonstrate that the complex DSC algorithm scales very well on many-core clusters for differnt CFD matrix problems of varying size.

In addition to the TRACE results shown above, numerical and performance experiments will Figure 2: Execution times of the total complex DSC solver for a complex medium size TRACE matrix problem of order 378,400 (left) and for a complex large TRACE matrix problem of order 4,497,520 (right) on a many-core cluster.

be presented with the real version of the DSC method developed for typical real TAU CFD problems on many-core architectures.

Fig. 1

 1 Fig.1displays execution times of the real and complex DSC solver software developed on 4 to 32 processor cores of DLRs AeroGrid cluster (45 Dual-processor nodes; Quad-Core Intel Harpertown; 2.83 GHz; 16 GB main memory per node; InfiniBand interconnection network between the nodes) for a complex and the corresponding real small TRACE matrix problem of order 28,120 or 56,240. METIS Nested Dissection was used for reordering of the local diagonal blocks. ILUT with threshold 10 -3 was applied for factoring the local blocks. The FGMRes iteration was stopped when the current residual norm divided by the initial residual was smaller than 10 -5 . The complex DSC solver version distinctly outperforms the real version

German Aerospace Center (DLR), Simulation and Software Technology, Porz-Wahnheide, Linder Höhe, Cologne, Germany

German Aerospace Center (DLR), Simulation and Software Technology, Porz-Wahnheide, Linder Höhe, Cologne, Germany


♦ ✉✐

= {p

Bivariate system solving algorithm

♦❢ t❤❡ ❞❡❝♦♠♣♦s✐t✐♦♥ ✭❙❡❝t✐♦♥s ✶✳✸✮✳ ❲❡ s❤♦✇ ❤♦✇ t❤❡ s♣❡❝✐✜❝ ❢♦r♠ ♦❢ t❤❡ ✐♥♣✉t tr✐❛♥❣✉•❛r s②st❡♠s ♣❡r✲ ♠✐ts t♦ tr✐✈✐❛••② ❝♦♠♣✉t❡ ❛ •rö❜♥❡r ❜❛s✐s✱ ❛♥❞ ②✐❡•❞s ✐♠♣r♦✈❡♠❡♥ts t♦ t❤❡ ❛•❣♦r✐t❤♠ ♦❢ ❬✹( ❢♦r ❝♦♠♣✉t✐♥❣ ❛ |❯|✳ ❚❤❡ |❯| ✐s t❤❡♥ ✉s❡❞ ✐♥ ❛ st❛♥❞❛r❞ ✇❛② t♦ s♦•✈❡ t❤❡s❡ s②st❡♠s✳ ❲❡ s❤♦✇ ✐♥ ❙❡❝t✐♦♥ ✶✳✹ ❤♦✇ t❤❡s❡ t✇♦ st❡♣s ❝❛♥ ❜❡ ♣❡r❢♦r♠❡❞ ✇✐t❤ ♠♦❞✉•❛r ❛r✐t❤♠❡t✐❝ ✐♥ ❛ ❞❡t❡r♠✐♥✐st✐❝ ✇❛②✱ ②✐❡•❞✐♥❣ ❛ ✈❡r② ❡✣❝✐❡♥t ❛•❣♦r✐t❤♠✳ ■t s❤♦✉•❞ ❜❡ str❡ss❡❞ t❤❛t ✇❡ ❞♦ ♥♦t ❝♦♠♣✉t❡ t❤❡ ♠✉•t✐♣•✐❝✐t② ♦❢ t❤❡ r♦♦ts ✐♥ t❤❡ ✐♥♣✉t s②st❡♠✳ ❍♦✇❡✈❡r✱ ❢♦r ❡✈❡r② r♦♦t (α, β) ♦❢ ❛ s②st❡♠ {F, ∂F ∂y }✱ ✇❡ ♦❜t❛✐♥ t❤❡ ♠✉•t✐♣•✐❝✐t② ♦❢ β ❛s ❛ r♦♦t ♦❢ F (α, y) ✭❙❡❝t✐♦♥ ✷✮✳ ❚❤❡s❡ ♠✉•t✐♣•✐❝✐t✐❡s ❛r❡ ♥❡❡❞❡❞ ✐♥ ♦✉r ❛•❣♦r✐t❤♠ ❢♦r ❝♦♠♣✉t✐♥❣ t❤❡ t♦♣♦•♦❣② ♦❢ ♣•❛♥❡ ❝✉r✈❡s✱ ❛♥❞ t❤✐s ✐s ❛ ❦❡② ❢❡❛t✉r❡ ♦❢ ♦✉r s♦•✈✐♥❣ ❛•❣♦r✐t❤♠✳ 1.1 Preliminaries : sub-resultant sequences |❡❝❛•• t❤❛t P ❛♥❞ Q ❛r❡ t✇♦ ♣♦•②♥♦♠✐❛•s ✐♥ Q[x, y]✳ ❈♦♥s✐❞❡r✐♥❣ P ❛♥❞ Q ❛s ♣♦•②♥♦♠✐❛•s ✐♥ y✱ •❡t P = p i=0 a i y i ✱ ❛♥❞ Q = q i=0 b i y i ✇✐t❤ a i ✱ b i ✐♥ Q[x]
. ❆ss✉♠❡ ✇✐t❤♦✉t •♦ss ♦❢ ❣❡♥❡r❛•✐t② t❤❛t p q✳ ❚❤❡ ❙②•✈❡st❡r ♠❛tr✐① ♦❢ P ❛♥❞ Q ✐s t❤❡ (p + q) × (p + q) ♠❛tr✐① ✇❤❡r❡ t❤❡ k✲t❤ r♦✇ ❝♦♥s✐sts✱ ❢♦r 1 k q✱ ♦❢ k -1 ③❡r♦s✱ ❢♦••♦✇❡❞ ❜② t❤❡ ❝♦❡✣❝✐❡♥ts ♦❢ P ✱ a p , . . . , a 0 ✱ ❛♥❞ ❝♦♠♣•❡t❡❞ ❜② q -k ③❡r♦s✱ ❛♥❞✱ ❢♦r q + 1 k p

+ q✱ ♦❢ k -q -1 ③❡r♦s✱ ❢♦••♦✇❡❞ ❜② t❤❡ ❝♦❡✣❝✐❡♥ts ♦❢ Q✱ b q , . . . , b 0 ✱ ❛♥❞ ❝♦♠♣•❡t❡❞ ❜② p + q -k ③❡r♦s✳ ❖♥❡ ❞❡♥♦t❡s ❜② Sylv i ✱ i q✱ t❤❡ (p + q -2i) × (p + q -i) ♠❛tr✐① ♦❜t❛✐♥❡❞ ❢r♦♠ t❤❡ ❙②•✈❡st❡r ♠❛tr✐① ♦❢ P ❛♥❞ Q ❜② ❞❡•❡t✐♥❣ t❤❡ i •❛st r♦✇s ♦❢ t❤❡ ❝♦❡✣❝✐❡♥ts ♦❢ P ✱ t❤❡ i •❛st r♦✇s ♦❢ t❤❡ ❝♦❡✣❝✐❡♥ts ♦❢ Q✱ ❛♥❞ t❤❡ i •❛st ❝♦•✉♠♥s✳ ❉❡✜♥✐t✐♦♥ ✶ ✭❬✶(✮ ❚❤❡ i✲t❤ ♣♦•②♥♦♠✐❛• s✉❜✲ r❡s✉•t❛♥t ♦❢ P ❛♥❞ Q✱ ❞❡♥♦t❡❞ ❜② Sres i (P, Q)✱ ✐s t❤❡ ♣♦•②♥♦♠✐❛• det(Mp+q-2i)y i +det(Mp+q-2i+1)y i-1 +• • •+det(Mp+q-i) ✇❤❡r❡ M j ✐s t❤❡ sq✉❛r❡ s✉❜✲♠❛tr✐① ♦❢ Sylv i ♦❢ s✐③❡ p + q -2i ❛♥❞ ❝♦♥s✐st✐♥❣ ♦❢ t❤❡ p + q -2i -1 ✜rst ❝♦•✉♠♥s ❛♥❞ t❤❡ j✲t❤ ❝♦•✉♠♥ ♦❢ Sylv i ✱ j ∈ {p + q - 2i, . . . , p+q -i}. ❚❤❡ s✉❜✲r❡s✉•t❛♥t s❡q✉❡♥❝❡ ♦❢ P ❛♥❞ Q ✐s t❤❡ s❡q✉❡♥❝❡ Sres i (P, Q) ❢♦r i ❢r♦♠ 0 t♦ q✳ Sres i (P, Q) ✐s ❛ ♣♦•②♥♦♠✐❛• ♦❢ ❞❡❣r❡❡ ❛t ♠♦st i ✐♥ y✱ ❛♥❞ t❤❡ ❝♦❡✣❝✐❡♥t ♦❢ t❤❡ ♠♦♥♦♠✐❛• ♦❢ ❞❡❣r❡❡ i✱ ❞❡♥♦t❡❞ ❜② sres i (P, Q)✱ ✐s ❝❛••❡❞ t❤❡ i✲t❤ ♣r✐♥❝✐♣❛• s✉❜✲r❡s✉•t❛♥t ❝♦❡✣❝✐❡♥t✳ ◆♦t❡ t❤❛t Sres 0 (P, Q) = ✷✼t❤ ❊✉r♦♣❡❛♥ ❲♦r❦s❤♦♣ ♦♥ ❈♦♠♣✉t❛t✐♦♥❛• •❡♦♠❡tr②✱ ✷✵✶✶ sres 0 (P, Q) ✐s t❤❡ r❡s✉•t❛♥t ♦❢ P ❛♥❞ Q✳ ❲❡ t❤✉s ❤❛✈❡ Sres i (P, Q) = sres i (P, Q)y i + R i (x, y) ✭✶✮ ✇❤❡r❡ t❤❡ ❞❡❣r❡❡ ✐♥ y ♦❢ R i ✐s ❛t ♠♦st i -1✱ ❛♥❞ ✐ts ❞❡❣r❡❡ ✐♥ x ✐s ❛t ♠♦st t❤❡ ♣r♦❞✉❝t ♦❢ t❤❡ t♦t❛• ❞❡❣r❡❡s ♦❢ P ❛♥❞ Q ✭t❤❡ ❞❡❣r❡❡ ✐♥ x ✐s ❣❡♥❡r✐❝❛••② ♠❛①✐♠❛• ❢♦r i = 0 ✇❤✐❝❤ ✐s t❤❛t ♦❢ t❤❡ r❡s✉•t❛♥t✮✳ ❚❤❡ ♣♦•②♥♦♠✐❛• s✉❜✲r❡s✉•t❛♥ts ♦❢ P ❛♥❞ Q ❛r❡ ❡q✉❛• t♦ ❡✐t❤❡r 0 ♦r t♦ ✭✉♣ t♦ ❛ ❝♦♥st❛♥t✮ ♣♦•②♥♦♠✐❛•s ✐♥ t❤❡ r❡♠❛✐♥❞❡r s❡q✉❡♥❝❡ ♦❢ P ❛♥❞ Q ❬✶✱ ♣✳✸✵✽(✳ ❋♦r ❡✣✲ ❝✐❡♥❝②✱ t❤❡ ❝♦♠♣✉t❛t✐♦♥s ♦❢ s✉❜✲r❡s✉•t❛♥t s❡q✉❡♥❝❡s ❛r❡ ✉s✉❛••② ♣❡r❢♦r♠❡❞ ❜② ❝♦♠♣✉t✐♥❣ ♣♦•②♥♦♠✐❛• r❡✲ ♠❛✐♥❞❡r s❡q✉❡♥❝❡s ✉s✐♥❣ s♦♠❡ ✈❛r✐❛♥ts ♦❢ ❊✉❝•✐❞ ❛•✲ ❣♦r✐t❤♠✳ 1.2 Triangular decomposition ❋✐rst✱ ✇❡ ♣r♦•❡❝t t❤❡ s♦•✉t✐♦♥s ♦❢ S ♦♥ t❤❡ x✲❛①✐s❀ ❛•✲ ❣❡❜r❛✐❝❛••②✱ t❤✐s ❛♠♦✉♥ts t♦ ❝♦♠♣✉t✐♥❣ t❤❡ r❡s✉•t❛♥t ♦❢ P ❛♥❞ Q ✇✐t❤ r❡s♣❡❝t t♦ t❤❡ ✈❛r✐❛❜•❡ y✳ ❚❤❡ r♦♦ts ♦❢ t❤❛t r❡s✉•t❛♥t✱ ❞❡♥♦t❡❞ Res y (P, Q) ∈ Q[x]✱ ❛r❡ t❤❡ x✲❝♦♦r❞✐♥❛t❡s ♦❢ t❤❡ s♦•✉t✐♦♥s ♦❢ S✱ ❛♥❞ t❤❡ ❝♦♠♠♦♥ r♦♦ts ♦❢ t❤❡✐r •❡❛❞✐♥❣ ❝♦❡✣❝✐❡♥ts a p ❛♥❞ b q ∈ Q[x]✳ ❍❡♥❝❡✱ t❤❡ r❡s✉•t❛♥t ♦❢ P ❛♥❞ Q ♣r♦✈✐❞❡s t❤❡ x✲ ❝♦♦r❞✐♥❛t❡s ♦❢ t❤❡ ♣♦✐♥ts ✇❤❡r❡ t❤❡ ❝♦rr❡s♣♦♥❞✐♥❣ ❝✉r✈❡s ✐♥t❡rs❡❝t ♦r ❤❛✈❡ ❛ ❝♦♠♠♦♥ ✈❡rt✐❝❛• ❛s②♠♣t♦t❡✳ ❋♦r ❡❛❝❤ s✉❝❤ x✲❝♦♦r❞✐♥❛t❡✱ t❤❡ ❞✐✣❝✉•t② ✐s t♦ ❝♦♠✲ ♣✉t❡ t❤❡ y✲❝♦♦r❞✐♥❛t❡s ♦❢ t❤❡ ❝♦rr❡s♣♦♥❞✐♥❣ ✐♥t❡rs❡❝✲ t✐♦♥ ♣♦✐♥ts✳ ❚❤✐s ❝❛♥ ❜❡ ❞♦♥❡ ✇✐t❤ t❤❡ s✉❜✲r❡s✉•t❛♥t s❡q✉❡♥❝❡ ❜❛s❡❞ ♦♥ t❤❡ ❢♦••♦✇✐♥❣ ❢✉♥❞❛♠❡♥t❛• ♣r♦♣♦✲ s✐t✐♦♥✳ Pr♦♣♦s✐t✐♦♥ ✶ ✭❬✸(✮ ▲❡t P, Q ∈ Q[x, y] ❜❡ t✇♦ sq✉❛r❡✲❢r❡❡ ♣♦•②♥♦♠✐❛•s ❛♥❞ ❝♦♥s✐❞❡r t❤❡✐r s✉❜✲ r❡s✉•t❛♥t s❡q✉❡♥❝❡ ✇✐t❤ r❡s♣❡❝t t♦ t❤❡ ✈❛r✐❛❜•❡ y✳ ▲❡t α ∈ R ❜❡ ❛ r♦♦t ♦❢ Res y (P, Q) s✉❝❤ t❤❛t a p (α) = 0 ❛♥❞ b q (α) = 0✳ ❚❤❡♥ sres 0 (α) = 0, • • • , sres k-1 (α) = 0 sres k (α) = 0 ⇔ Gcd(P (α, y), Q(α, y)) = Sres k (α, y). ❲❡ ❞❡❝♦♠♣♦s❡ t❤❡ ✐♥♣✉t s②st❡♠ S ✐♥t♦ ❛ s❡t ♦❢ tr✐❛♥❣✉•❛r s②st❡♠s ✇✐t❤ r❡s♣❡❝t t♦ t❤❡ ❞❡❣r❡❡ ♦❢ Gcd(P (α, y), Q(α, y)) ❛❝❝♦r❞✐♥❣ t♦ Pr♦♣✳ ✶✳ ❚❤r♦✉❣❤✲ ♦✉t t❤❡ ❞❡❝♦♠♣♦s✐t✐♦♥ ✇❡ ❝♦♥s✐❞❡r t❤❡ sq✉❛r❡✲❢r❡❡ ♣❛rt ♦❢ t❤❡ r❡s✉•t❛♥t ♦❢ P ❛♥❞ Q✱ Res y (P, Q) = Sres 0 (P, Q)✱ ❛♥❞ ✇❡ ❞❡♥♦t❡ ✐t ❜② sqrf ree(Sres 0 (x))✳ ❚❛❦✐♥❣ t❤❡ sq✉❛r❡✲❢r❡❡ ♣❛rt s✐♠♣•✐✜❡s t❤❡ ❝♦♠♣✉t❛✲ t✐♦♥ ❜✉t ✐t ❞♦❡s ♥♦t ♣r❡s❡r✈❡ t❤❡ ♠✉•t✐♣•✐❝✐t✐❡s ♦❢ t❤❡ r♦♦ts✳ ❍♦✇❡✈❡r✱ t❤✐s ✐s ❛❝t✉❛••② ❝r✐t✐❝❛• ✐♥ ♦✉r ❛•❣♦✲ r✐t❤♠ ❢♦r ❝♦♠♣✉t✐♥❣ t❤❡ ♠✉•t✐♣•✐❝✐t✐❡s ✐♥ t❤❡ ✜❜❡rs ♥❡❡❞❡❞ ❢♦r t❤❡ t♦♣♦•♦❣② ❝♦♠♣✉t❛t✐♦♥✱ ❛s ♠❡♥t✐♦♥❡❞ ❡❛r•✐❡r ✭❙❡❝t✐♦♥ ✷✮✳ ❆❝❝♦r❞✐♥❣ t♦ Pr♦♣✳ ✶✱ ✇❡ ✜rst ❝♦♥s✐❞❡r ♦♥•② x✲ ❝♦♦r❞✐♥❛t❡s ♦♥ ✇❤✐❝❤ a p ❛♥❞ b q ❞♦ ♥♦t ✈❛♥✐s❤✳ •❡✲ ♦♠❡tr✐❝❛••②✱ t❤❡ r♦♦ts ♦❢ a p ❝♦rr❡s♣♦♥❞ t♦ ✈❡rt✐❝❛• ❛s②♠♣t♦t❡s ♦❢ t❤❡ ❝✉r✈❡ C P ❞❡✜♥❡❞ ❜② P = 0❀ s✐♠✐•❛r•② ❢♦r b q ❛♥❞ t❤❡ ❝✉r✈❡ C Q ✳ ❲❡ ❞❡♥♦t❡ ❜② F res(x) t❤❡ ♣♦•②♥♦♠✐❛• sqrf ree(Sres 0 (x)) ✏✇✐t❤♦✉t t❤❡s❡ r♦♦ts✑✿ F res(x) = sqrf ree(Sres0(x)) Gcd(sqrf ree(Sres0(x)), ap(x)bq(x)) . ✭✷✮ ❙♦•✉t✐♦♥s ♦✉ts✐❞❡ t❤❡ ✈❡rt✐❝❛• ❛s②♠♣t♦t❡s✳ ❚❤❡ s♦•✉t✐♦♥s ♦❢ S t❤❛t ❞♦ ♥♦t •✐❡ ♦♥ ❛ ✈❡rt✐❝❛• ❛s②♠♣✲ t♦t❡ ♦❢ C P ♦r C Q ❤❛✈❡ t❤❡✐r x✲❝♦♦r❞✐♥❛t❡s s♦•✉t✐♦♥s ♦❢ F res(x)✳ ❚❤❡ ✐❞❡❛ ✐s t♦ ❢❛❝t♦r✐③❡ F res(x) ✇✐t❤ r❡✲ s♣❡❝t t♦ t❤❡ ❞❡❣r❡❡ ♦❢ t❤❡ Gcd(P (α, y), Q(α, y)) ❢♦r α r♦♦t ♦❢ F res(x)✳ ▲❡t G 1 (x) = Gcd(F res(x), sres 1 (x))✳ ❲❡ s♣•✐t F res(x) ✐♥ t✇♦ ❢❛❝t♦rs G 1 ❛♥❞ F 1 (x) = F res(x) G1(x) ✱ ❛♥❞ ✇❡ ❝♦♥s✐❞❡r t❤❡ s②st❡♠ S 1 = F 1 (x) Sres 1 (x, y) = sres 1 (x)y + R(x) ✳ ❚❤❡ r♦♦ts ♦❢ S 1 ❛r❡ ❡①❛❝t•② t❤❡ r♦♦ts (α, β) ♦❢ S s✉❝❤ t❤❛t t❤❡ ❞❡❣r❡❡ ♦❢ t❤❡ Gcd(P (α, y), Q(α, y)) ✐s ✶✳ ■♥ ♦t❤❡r ✇♦r❞s✱ α ✐s ❛ r♦♦t ♦❢ F res(x) s✉❝❤ t❤❛t S ❛❞♠✐ts ❛ ✉♥✐q✉❡ r♦♦t (α, y) ❝♦✉♥t❡❞ ✇✐t❤ ♠✉•t✐♣•✐❝✐t②✳ ❆❝❝♦r❞✐♥❣ t♦ Pr♦♣✳ ✶✱ ✇❡ s♣•✐t ❛❣❛✐♥ G 1 ✇✐t❤ r❡✲ s♣❡❝t✱ t❤✐s t✐♠❡✱ t♦ t❤❡ ♣♦•②♥♦♠✐❛• sres 2 (x)✳ ▲❡t G 2 = Gcd(G 1 , sres 2 )✱ F 2 = G 1 /G 2 ✱ t❤❡ s②st❡♠ S 2 = {F 2 (x), Sres 2 (x, y)} ❡♥❝♦❞❡s t❤❡ s♦•✉t✐♦♥s (α, β) ♦❢ S s✉❝❤ t❤❛t t❤❡ ❞❡❣r❡❡ ♦❢ t❤❡ Gcd(P (α, y), Q(α, y)) ✐s ✷✳ ■♥ ♦t❤❡r ✇♦r❞s✱ α ✐s ❛ r♦♦t ♦❢ F res(x) s✉❝❤ t❤❛t S ❛❞♠✐ts t✇♦ r♦♦ts (α, y) ❝♦✉♥t❡❞ ✇✐t❤ ♠✉•t✐♣•✐❝✐t②✳ ❲❡ ❣♦ ❛❤❡❛❞ r❡❝✉rs✐✈❡•② ✉♥t✐• ✇❡ ❞❡❝♦♠♣♦s❡ ❝♦♠✲ ♣•❡t❡•② F res(x) ✇✐t❤ r❡s♣❡❝t t♦ t❤❡ ♣♦•②♥♦♠✐❛•s sres 1 (x), . . . , sres q (x)✳ ❆t t❤❡ k✲t❤ st❡♣ t❤❡ r♦♦ts ♦❢ F k (x) ❛r❡ ❡①❛❝t•② t❤❡ r♦♦ts ♦❢ F res(x) ✈❡r✐❢②✐♥❣ sres 1 (x) = 0, . . . , sres k-1 (x) = 0✱ ❛♥❞ sres k (x) = 0✳ ❚❤❡ r❡s✉•t ✐s ❛ s❡t ♦❢ tr✐❛♥❣✉•❛r s②s✲ t❡♠s S k = {F k (x), Sres k (x, y)} s✉❝❤ t❤❛t Gcd(F k (x), sres k (x)) = 1✳ ❙♦•✉t✐♦♥s ♦♥ ✈❡rt✐❝❛• ❛s②♠♣t♦t❡s✳ ❲❡ ♥♦✇ ❝♦♥✲ s✐❞❡r t❤❡ s♦•✉t✐♦♥s ♦❢ S ♦♥ ❛♥ ❛s②♠♣t♦t❡ x = α✱ ✇✐t❤ α ❛ r♦♦t ♦❢ a p ♦r b q ✳ ❖✉r ❛•❣♦r✐t❤♠ ❞✐✛❡rs ❤❡r❡ ❢r♦♠ t❤❛t ♦❢ ❬✸( ✐♥ ✇❤✐❝❤ t❤❡② ❞❡t❡❝t ✇❤❡♥ s✉❝❤ ❛ s✐t✉❛t✐♦♥ ♦❝❝✉rs ❛♥❞ s❤❡❛r t❤❡ ❝♦♦r❞✐♥❛t❡ s②st❡♠✳ ❋♦r s❛❦❡ ♦❢ ❜r❡✈✐t②✱ ✇❡ ♦♥•② ❞❡t❛✐• t❤❡ ❝❛s❡ ♦❢ s♦•✉t✐♦♥s ♦♥ ❛ ❝♦♠✲ ♠♦♥ ❛s②♠♣t♦t❡✱ t❤❛t ✐s x = α ✇✐t❤ α ❛ r♦♦t ♦❢ D(x) t❤❡ sq✉❛r❡✲❢r❡❡ ♣❛rt ♦❢ Gcd(a p , b q )✳ ▲❡t P 1 ✱ Q 1 ❜❡ ❞❡✜♥❡❞ ❛s ❢♦••♦✇s✿ P 1 = p i=1 (a i modD(x))y i ✱ Q 1 = q i=1 (b i modD(x))y i ✱ ✇❤❡r❡ U (x) mod D(x) ✐s t❤❡ r❡♠❛✐♥❞❡r ♦❢ t❤❡ ❊✉✲ ❝•✐❞❡❛♥ ❞✐✈✐s✐♦♥ ♦❢ U (x) ❜② D(x) ✐♥ Q[x]✳ ■t ✐s ❝•❡❛r t❤❛t P 1 , Q 1 ❝♦✐♥❝✐❞❡ ✇✐t❤ P ❛♥❞ Q ❛❜♦✈❡ t❤❡ r♦♦ts ♦❢ D(x)✱ ✐✳❡✳✱ ∀α ∈ R : D(α) = 0 =⇒ P 1 (α, y) = P (α, y) ❛♥❞ Q 1 (α, y) = Q(α, y). ❲❡ ❞❡❝♦♠♣♦s❡ t❤❡ s②st❡♠ {P 1 , Q 1 } ❛s ❞❡s❝r✐❜❡❞ ❛❜♦✈❡ ❜✉t ❦❡❡♣✐♥❣ ✐♥ t❤❡ r❡s✉•t❛♥t ♦♥•② t❤❡ r♦♦ts ♦❢ D(x)✿ F res(x) = sqrf ree(Gcd(Sres 0 (P 1 , Q 1 ), D(x)))✳ ❲❡ t❤✉s r❡❝♦✈❡r ✐♥ t❤❡ r❡s✉•t✐♥❣ s②st❡♠s✱ s♦•✉t✐♦♥s •♦❝❛t❡❞ ♦♥ t❤❡ ❝♦♠✲ ♠♦♥ ❛s②♠♣t♦t❡s✳ ❊✉r♦❈• ✷✵✶✶✱ ▼♦rs❝❤❛❝❤✱ ❙✇✐t③❡r•❛♥❞✱ ▼❛r❝❤ ✷✽✕✸✵✱ ✷✵✶✶ ❖✉t♣✉t✳ ❚❤❡ ♦✉t♣✉t ✐s ❛ s❡t ♦❢ tr✐❛♥❣✉✲ •❛r s②st❡♠s S k = F k (x) = 0 Sres k (x, y) = 0 s✉❝❤ t❤❛t Gcd(F k (x), sres k (x)) = 1 ❛♥❞ ❛•• F k ❛r❡ sq✉❛r❡✲❢r❡❡✳ ❋♦r ❡✈❡r② k t❤❡r❡ ♠✐❣❤t ❜❡ s❡✈❡r❛• s②st❡♠s S k ✿ ❞❡✲ ♣❡♥❞✐♥❣ ♦♥ ✇❤❡t❤❡r t❤❡ s♦•✉t✐♦♥ ♦❢ S k •✐❡s ♦♥ ❛ ✈❡r✲ t✐❝❛• ❛s②♠♣t♦t❡ ♦r ♥♦t✱ Sres k ❞❡♥♦t❡s t❤❡ k✲t❤ s✉❜✲ r❡s✉•t❛♥t ♦❢ P ❛♥❞ Q✱ ♦r ♦❢ s♦♠❡ r❡❞✉❝t✐♦♥s ♦❢ P ❛♥❞ Q ♠♦❞✉•♦ s♦♠❡ ❢❛❝t♦rs ♦❢ t❤❡✐r •❡❛❞✐♥❣ ❝♦❡✣❝✐❡♥ts a p ❛♥❞ b q ✐♥ Q[x]✳ 1.3 Groebner basis and RUR computation ❆ s♣❡❝✐✜❝ ♣r♦♣❡rt② ♦❢ t❤❡ ❞❡❝♦♠♣♦s✐t✐♦♥ ♦❜t❛✐♥❡❞ ❛❜♦✈❡ ✐s t❤❛t Gcd(F k (x), sres k (x)) = 1✳ ❇② ❇é✲ ③♦✉t ✐❞❡♥t✐t②✱ t❤❡r❡ ❡①✐sts U, V ∈ Q[x] s✉❝❤ t❤❛t U F k + V sres k = 1✳ ❚❤✉s✱ s✐♥❝❡ Sres k (x, y) = sres k (P, Q)y k + R k (x, y) ✭❊q✳ ✭✶✮✮✱ t❤❡ s②st❡♠ S k ✐s ❡q✉✐✈❛•❡♥t t♦ Sk : F k (x) = 0 y k + Rk (x, y) = 0 ✇❤❡r❡ Rk ✐s t❤❡ r❡❞✉❝t✐♦♥ ♦❢ V R k ♠♦❞✉•♦ F k ✭t❤❛t ✐s ❡❛❝❤ ❝♦❡✣✲ ❝✐❡♥t ✐s r❡❞✉❝❡❞ ♠♦❞✉•♦ F k (x)✮❀ ❤❡♥❝❡ Rk ❤❛s ❞❡❣r❡❡ ✐♥ y str✐❝t•② •❡ss t❤❛♥ k ❛♥❞ str✐❝t•② •❡ss t❤❛♥ t❤❛t ♦❢ F k ✐♥ x✳ ❚❤❡ r❡s✉•t✐♥❣ s②st❡♠ t❤✉s ✐s ❛ ✭r❡❞✉❝❡❞✮ •❡①✐❝♦❣r❛♣❤✐❝ •rö❜♥❡r ❜❛s✐s ❬✶(✳ ❆t t❤✐s st❛❣❡✱ ✇❡ ❝❛♥ ✉s❡ ❛ st❛♥❞❛r❞ |❯| ❛•❣♦✲ r✐t❤♠ ❢♦r s♦•✈✐♥❣ ❡❛❝❤ ♦❢ t❤❡s❡ s②st❡♠s ❬✹(✳ |❡❝❛•• t❤❛t ❣✐✈❡♥ ❛ ❜✐✈❛r✐❛t❡ s②st❡♠✱ ❛ |❯| ❞❡✜♥❡s ❛ ♣❛✲ r❛♠❡t❡r✐③❛t✐♦♥ ♦❢ ✐ts s♦•✉t✐♦♥s ✇✐t❤ ❢♦✉r ♣♦•②♥♦♠✐❛•s f, g x , g y , g ∈ Q[t] s✉❝❤ t❤❛t t❤❡ s♦•✉t✐♦♥s ♦❢ t❤❡ s②st❡♠ ❛r❡ ( gx(ti) g(ti) , gy(ti) g(ti) ) ❢♦r t❤❡ r♦♦ts t i ♦❢ f ✳ ■t s❤♦✉•❞ ❜❡ str❡ss❡❞ t❤❛t ❛ |❯| ♣r❡s❡r✈❡s t❤❡ ♠✉•t✐♣•✐❝✐t② ♦❢ t❤❡ r♦♦ts ♦❢ t❤❡ s②st❡♠✱ ✐s✱ t❤❡ ♠✉•t✐♣•✐❝✐t② ♦❢ ❛ r♦♦t t i ♦❢ f ✐s t❤❡ ♠✉•t✐♣•✐❝✐t② ♦❢ t❤❡ r♦♦t ( gx(ti) g(ti) , gy(ti) g(ti) ) ✐♥ Sk ✱ ❛♥❞ t❤✉s ✐♥ S k ✳ ❚❤❡ ❢❛❝t t❤❛t F k ✐s sq✉❛r❡✲❢r❡❡ ②✐❡•❞s ❛ ❣❡♦♠❡tr✐❝ ✐♥t❡r♣r❡t❛t✐♦♥ ♦❢ t❤❡ ♠✉•t✐♣•✐❝✐t✐❡s ✐s t❤❡ s②st❡♠ S k t❤❛t ✇✐•• ❜❡ ❡①♣•♦✐t❡❞ ✐♥ ♦✉r ❛♣♣•✐✲ ❝❛t✐♦♥ ♦♥ t❤❡ t♦♣♦•♦❣② ♦❢ ❝✉r✈❡s✳ ❚❤❡ ♣❛rt✐❝✉•❛r str✉❝t✉r❡ ♦❢ t❤❡ s②st❡♠s ✇❡ ♦❜t❛✐♥ ②✐❡•❞s ✐♠♣r♦✈❡♠❡♥ts t♦ t❤❡ ❛•❣♦r✐t❤♠ ♦❢ |♦✉✐••✐❡r ❬✹( ❢♦r ❝♦♠♣✉t✐♥❣ ❛ |❯|✳ ❚❤❡ ❝r✐t✐❝❛• ♣r♦♣❡rt✐❡s ♦❢ ♦✉r ✐♥♣✉t s②st❡♠s S k ✐s t❤❛t ✭✐✮ t❤❡② ❛r❡ •rö❜♥❡r ❜❛s✐s ❢♦r t❤❡ •❡①✐❝♦❣r❛♣❤✐❝ ♦r❞❡r✱ ✇❤✐❝❤ ✐♠♣•✐❡s t❤❛t ♦♥❡ ♦❢ t❤❡ ♣♦•②♥♦♠✐❛•s ✐s ✉♥✐✈❛r✐❛t❡✱ ❛♥❞ ✭✐✐✮ t❤❡r❡ ❛r❡ ♦♥•② t✇♦ ♣♦•②♥♦♠✐❛•s ✐♥ t❤❡ ❜❛s✐s✳ ▼♦st ♦❢ t❤❡ |❯| ❝♦♠✲ ♣✉t❛t✐♦♥s ❛r❡ ♣❡r❢♦r♠❡❞ ✉s✐♥❣ •✐♥❡❛r ❛•❣❡❜r❛ ✐♥ t❤❡ q✉♦t✐❡♥t ❛•❣❡❜r❛ Q[x, y]/S k ✭✇❤❡r❡ S k ❞❡♥♦t❡ ❤❡r❡ t❤❡ ✐❞❡❛• ❛ss♦❝✐❛t❡❞ t♦ t❤❡ s②st❡♠✮✳ Pr♦♣❡rt② ✭✐✐✮ ✐♠✲ ♣•✐❡s t❤❛t ❛ ❜❛s✐s ♦❢ t❤✐s ❛•❣❡❜r❛ ✐s s✐♠♣•② {x i y j }✱ ❢♦r 0 i < ❞❡❣r❡❡(F k ) ❛♥❞ 0 j < k✳ ❖♥❡ ✐♠♣♦rt❛♥t st❡♣ ♦❢ t❤❡ ❛•❣♦r✐t❤♠ ✐s t♦ ❝♦♠♣✉t❡ t❤❡ ♣r♦❞✉❝t ♦❢ ❛•• ♣❛✐rs ♦❢ ❡•❡♠❡♥ts ♦❢ t❤❛t ❜❛s✐s✱ r❡❞✉❝❡❞ ♠♦❞✉•♦ t❤❡ s②st❡♠ S k ❀ t❤✐s st❡♣ ✐s s✉❜st❛♥t✐❛••② s✐♠♣•✐✜❡❞ ❜② t❤❡ str✉❝t✉r❡ ♦❢ t❤❡ ❜❛s✐s ❛♥❞ ❜② ✉s✐♥❣ Pr♦♣❡rt② ✭✐✮✳ ❚❤❡ ❝♦♠♣•❡①✐t② ♦❢ t❤✐s st❡♣✱ ❛♥❞ ❛❝t✉❛••② ♦❢ t❤❡ ✇❤♦•❡ |❯| ❝♦♠♣✉t❛t✐♦♥✱ ✐s t❤✐s ✇❛② r❡❞✉❝❡❞ ❢r♦♠ O(D 3 ) t♦ O(D 2 ) ✇❤❡r❡ D ✐s t❤❡ s✐③❡ ♦❢ t❤❡ ❛•❣❡❜r❛ ❜❛s✐s✳ 1.4 Deterministic modular method ❚❤❡ ❜✐ts✐③❡ ♦❢ t❤❡ ❝♦❡✣❝✐❡♥ts ✐♥ t❤❡ |❯| ✐s r❡❛s♦♥❛❜•❡ ✐♥ t❤❡ s❡♥s❡ t❤❛t t❤❡s❡ ❝♦❡✣❝✐❡♥ts ❤❛✈❡ ♠♦r❡ ♦r •❡ss t❤❡ s❛♠❡ s✐③❡ ❛s t❤♦s❡ ✐♥ t❤❡ r❡s✉•t❛♥t ❬✷✱ ➓✹✳✷(✳ ❍♦✇✲ ❡✈❡r✱ t❤❡ s✐③❡ ♦❢ t❤❡ ❝♦❡✣❝✐❡♥ts ♦❢ t❤❡ •❡①✐❝♦❣r❛♣❤✐❝ •rö❜♥❡r ❜❛s✐s ✐♥ t❤❡ ✐♥t❡r♠❡❞✐❛t❡ ❝♦♠♣✉t❛t✐♦♥s ♠❛② ❜❡ q✉✐t❡ •❛r❣❡✳ ❆ st❛♥❞❛r❞ ❛♣♣r♦❛❝❤ ❢♦r ❛✈♦✐❞✐♥❣ s✉❝❤ ✐♥t❡r♠❡❞✐❛t❡ ❣r♦✇t❤ ✐s t♦ ✉s❡ ♠♦❞✉•❛r ❝♦♠♣✉t❛t✐♦♥s ❛♥❞ t❤❡ ❈❤✐♥❡s❡ |❡♠❛✐♥❞❡r ❚❤❡♦r❡♠ ❬✶(✳ ❚❤❡ ❞✐❢✲ ✜❝✉•t② ❜❡✐♥❣ t❤❡ ❞❡s✐❣♥ ♦❢ ❛ ❞❡t❡r♠✐♥✐st✐❝ ❛•❣♦r✐t❤♠ ✭r❛t❤❡r t❤❛♥ ❛ ▼♦♥t❡✲❈❛r•♦ ❛•❣♦r✐t❤♠✮✳ ❲❡ s❤♦✇ ❤♦✇ t❤✐s ❛♣♣r♦❛❝❤ ❝❛♥ ❜❡ ❛♣♣•✐❡❞ ❤❡r❡✳ ❲✐t❤♦✉t •♦ss ♦❢ ❣❡♥❡r❛•✐t②✱ ✇❡ ❝❛♥ ❛ss✉♠❡ t❤❛t t❤❡ t✇♦ ✐♥♣✉t ♣♦•②♥♦♠✐❛•s P ❛♥❞ Q ❤❛✈❡ ✐♥t❡❣❡r ❝♦❡✣✲ ❝✐❡♥ts ✭r❛t❤❡r t❤❛♥ r❛t✐♦♥❛•✮✳ ❋♦r ❜r❡✈✐t②✱ ✇❡ ♦♥•② ❞❡✲ s❝r✐❜❡ ❤♦✇ t♦ ❝♦♠♣✉t❡ t❤❡ r♦♦ts ♦✉ts✐❞❡ t❤❡ ✈❡rt✐❝❛• ❛s②♠♣t♦t❡s❀ t❤❡ r♦♦ts ♦♥ t❤❡ ✈❡rt✐❝❛• ❛s②♠♣t♦t❡s ❛r❡ tr❡❛t❡❞ s✐♠✐•❛r•②✳ ▲❡t µ ❜❡ ❛ ♣r✐♠❡ ♥✉♠❜❡r •❛r❣❡r t❤❛♥ pq✱ Z µ = Z µZ ✱ ❛♥❞ •❡t φ µ ❜❡ t❤❡ ❝❛♥♦♥✐❝❛• s✉r•❡❝t✐♦♥ Z[x, y] → Z µ [x, y] t❤❛t tr❛♥s❢♦r♠s t❤❡ ♣♦•②♥♦♠✐❛• ❝♦✲ ❡✣❝✐❡♥ts ♠♦❞✉•♦ µ✳ ❲❡ ✜rst ❝❤❡❝❦ t❤❛t ✭✐✮ φ µ (a p ) = 0 ❛♥❞ φ µ (b q ) = 0✱ t❤❡♥ ✇❡ ❝♦♠♣✉t❡ F res(P, Q) ❛♥❞ F res(φ µ (P ), φ µ (Q)) ✭❊q✳ ✭✷✮✮ ❛♥❞ t❡st ✇❤❡t❤❡r ✭✐✐✮ φ µ (F res(P, Q)) = F res(φ µ (P ), φ µ (Q)) ❛♥❞ ✭✐✐✐✮ degree(φ µ (F res(P, Q))) = degree(F res(P, Q))✳ ❲❡ ❝♦♥s✐❞❡r ♣r✐♠❡ ♥✉♠❜❡rs ✐♥ t✉r♥ ✉♥t✐• ❛•• t❤❡s❡ ♣r♦♣✲ ❡rt✐❡s ❛r❡ s❛t✐s✜❡❞✳ ❚❤❡♥✱ ❝♦♥s✐❞❡r✐♥❣ ♣♦•②♥♦♠✐❛•s ✐♥ Z µ [x, y]✱ ✇❡ s♦•✈❡ t❤❡ s②st❡♠ {φ µ (P ), φ µ (Q)} ❛s ❞❡✲ s❝r✐❜❡❞ ✐♥ ❙❡❝t✐♦♥s ✶✳✷ ❛♥❞ ✶✳✸✳ ▲❡♠♠❛ ✷ ❚❤❡ s✉♠ ♦❢ t❤❡ ❞❡❣r❡❡s ♦❢ t❤❡ s②st❡♠s ✭t❤❡ ❞❡❣r❡❡ ♦❢ ❛ s②st❡♠ ❜❡✐♥❣ t❤❡ ♥✉♠❜❡r ♦❢ ✐ts ❝♦♠♣•❡① r♦♦ts ❝♦✉♥t❡❞ ✇✐t❤ ♠✉•t✐♣•✐❝✐t②✮ ✐♥ t❤❡ ❞❡❝♦♠♣♦s✐t✐♦♥ ❛♣♣•✐❡❞ t♦ φ µ (P ) ❛♥❞ φ µ (Q) ❛♥❞ ♣❡r❢♦r♠❡❞ ✐♥ Z µ [x, y] ✐s ❣r❡❛t❡r t❤❛♥ ♦r ❡q✉❛• t♦ t❤❡ s✉♠ ♦❢ t❤❡ ❞❡❣r❡❡s ♦❢ t❤❡ s②st❡♠s ✐♥ t❤❡ ❞❡❝♦♠♣♦s✐t✐♦♥ ♦❢ P ❛♥❞ Q ♣❡r✲ ❢♦r♠❡❞ ♦✈❡r t❤❡ r❛t✐♦♥❛•s✳ ❆♥ ✐♠♣♦rt❛♥t r❡♠❛r❦ ✐s t❤❛t s✐♥❝❡ t❤❡ |❯| ♣r❡✲ s❡r✈❡s ♠✉•t✐♣•✐❝✐t✐❡s✱ t❤❡ ❞❡❣r❡❡ ♦❢ ❛ s②st❡♠ ✐s t❤❡ ❞❡✲ ❣r❡❡ ♦❢ t❤❡ ✜rst ♣♦•②♥♦♠✐❛• ♦❢ ✐ts |❯|✱ ❡✈❡♥ ✇❤❡♥ ❝♦♥s✐❞❡r❡❞ ♦✈❡r Z µ [x, y]✱ ❛s s♦♦♥ ❛s µ > pq ❬✹(✳ ■❢ t❤❡ s✉♠ ♦❢ t❤❡ ❞❡❣r❡❡s ♦❢ t❤❡ s②st❡♠s ♦❜t❛✐♥❡❞ ❜② ❛ ❝♦♠✲ ♣✉t❛t✐♦♥ ♠♦❞✉•♦ µ ✐s str✐❝t•② ❣r❡❛t❡r t❤❛♥ t❤❡ s✉♠ ♦❢ t❤❡ ❞❡❣r❡❡s ♦❢ t❤❡ s②st❡♠s ♦❜t❛✐♥❡❞ ❜② t❤❡ ❝♦♠♣✉t❛✲ t✐♦♥ ♦✈❡r t❤❡ r❛t✐♦♥❛•s✱ ✇❡ s❛② t❤❛t µ ✐s ❛♥ ✉♥•✉❝❦② ♣r✐♠❡✳ ❚❤❡ ❞✐✣❝✉•t② ✐s ♦❢ ❝♦✉rs❡ t♦ ❞❡t❡❝t ✉♥•✉❝❦② ♣r✐♠❡s✳ ❖✉r ❛•❣♦r✐t❤♠ s❡•❡❝ts ❛ s❡t ♦❢ ♣r✐♠❡s µ ✭❛s ❞❡s❝r✐❜❡❞ ❛❜♦✈❡✮✱ ❞❡❝♦♠♣♦s❡s t❤❡ s②st❡♠ {φ µ (P ), φ µ (Q)}✱ ❛♥❞ ❞❡t❡r♠✐♥❡s ❛ |❯| ❢♦r ❡❛❝❤ S k ♦✈❡r Z µ [x, y]✳ ■❢ t❤❡ s✉♠s ♦❢ t❤❡ ❞❡❣r❡❡s ♦❢ S k ❛r❡ ♥♦t t❤❡ s❛♠❡ ❢♦r ❛•• ❝♦♥s✐❞❡r❡❞ ♣r✐♠❡s✱ t❤❡ ♣r✐♠❡s ❢♦r ✇❤✐❝❤ t❤✐s s✉♠ ✐s ♥♦t ♠✐♥✐♠❛• ❛r❡ ✉♥•✉❝❦②✱ ❛♥❞ ✇❡ ❞✐s❝❛r❞ t❤❡s❡ ♣r✐♠❡s✳ ❖t❤❡r✇✐s❡✱ ❡✐t❤❡r ❛•• ♣r✐♠❡s ❛r❡ •✉❝❦② ♦r t❤❡② ❛r❡ ❛•• ✉♥•✉❝❦②✳ ❲❡ t❤❡♥ ✉s❡ t❤❡ ❈❤✐♥❡s❡ |❡♠❛✐♥❞❡r ❚❤❡♦✲ r❡♠ t♦ •✐❢t t❤❡ |❯|s ♦❢ t❤❡ s②st❡♠s S k ✳ ✷✼t❤ ❊✉r♦♣❡❛♥ ❲♦r❦s❤♦♣ ♦♥ ❈♦♠♣✉t❛t✐♦♥❛• •❡♦♠❡tr②✱ ✷✵✶✶ ❲❡ t❤❡♥ ❝❤❡❝❦ ✇❤❡t❤❡r t❤❡ r♦♦ts ♦❢ t❤❡ s❡t ♦❢ r❡✲ s✉•t✐♥❣ |❯|s (f, g x , g y , g) ♦❢ ❡❛❝❤ S k ❛r❡ ✐♥❞❡❡❞ r♦♦ts ♦❢ t❤❡ s②st❡♠ {P, Q} ✇✐t❤ t❤❡ ❝♦rr❡❝t ♠✉•t✐♣•✐❝✐t✐❡s✳ ❈❤❡❝❦✐♥❣ ✇❤❡t❤❡r t❤❡ r♦♦ts ❛r❡ ❝♦rr❡❝t ✐s ❞♦♥❡ ❜② s✉❜st✐t✉t✐♥❣ t❤❡ r❛t✐♦♥❛• ❝♦♦r❞✐♥❛t❡s x = gx(t) g(t) ❛♥❞ y = gy(t) g(t) ✐♥ P ❛♥❞ Q ❛♥❞ ❝❤❡❝❦✐♥❣ t❤❛t f ❞✐✈✐❞❡s ✐ts ♥✉♠❡r❛t♦r✳ ❆ r♦♦t ♦❢ ♠✉•t✐♣•✐❝✐t② m ❝♦rr❡s♣♦♥❞✐♥❣ t♦ ❛ r♦♦t t ♦❢ f ❝❛♥ ❜❡ ✈❡r✐✜❡❞ s✐♠✐•❛r•② ❜② s✉❜st✐t✉t✲ ✐♥❣ t❤❡ |❯| ❝♦♦r❞✐♥❛t❡s ✐♥ t❤❡ i✲t❤ ❞❡r✐✈❛t✐✈❡s ♦❢ P ❛♥❞ Q ✇✐t❤ r❡s♣❡❝t t♦ y ✭❢♦r i ❢r♦♠ 1 t♦ m -1✮✱ ❛♥❞ ❝❤❡❝❦✐♥❣ t❤❛t t ✐s ❛ r♦♦t ♦❢ t❤❡✐r ❣❝❞ ✇✐t❤ f ✭♠♦r❡ ♣r❡✲ ❝✐s❡•②✱ •❡t f = Π i f i i ❜❡ t❤❡ ❞❡❝♦♠♣♦s✐t✐♦♥ ✇✐t❤ r❡s♣❡❝t t♦ ♠✉•t✐♣•✐❝✐t✐❡s ♦❢ t❤❡ ✜rst ♣♦•② ♦❢ t❤❡ |❯| t❤❡♥ t ✐s ❛ r♦♦t ♦❢ f m ✱ ❛♥❞ ♦♥❡ ♠✉st ❝❤❡❝❦ t❤❛t f m ❞✐✈✐❞❡s t❤❡ ♥✉♠❡r❛t♦rs ♦❢ t❤❡ ❞❡r✐✈❛t✐✈❡s ♦❢ P ❛♥❞ Q ❛❢t❡r s✉❜st✐t✉t✐♦♥✮✳ ❙✐♠✐•❛r•②✱ t❤❡ ♠✉•t✐♣•✐❝✐t② m ♦❢ ❛ r♦♦t (α, β) ♦❢ t❤❡ s②st❡♠ ✭❝♦rr❡s♣♦♥❞✐♥❣ t♦ ❛ r♦♦t t ♦❢ f ✮ ❝❛♥ ❜❡ ❝❤❡❝❦❡❞ t♦ ❜❡ ❝♦rr❡❝t ❜② s✉❜st✐t✉t✐♥❣ t❤❡ |❯| ❝♦♦r❞✐♥❛t❡s ✐♥ t❤❡ i✲t❤ ❞❡r✐✈❛t✐✈❡s ♦❢ P ❛♥❞ Q ✇✐t❤ r❡s♣❡❝t t♦ y ✭❢♦r i ❢r♦♠ 1 t♦ m -1✮✱ ❛♥❞ ❝❤❡❝❦✐♥❣ t❤❛t t ✐s ❛ r♦♦t ♦❢ t❤❡✐r ❣❝❞ ✇✐t❤ f ✳ ❈❤❡❝❦✐♥❣ t❤❛t t ✐s ♥♦t ❛ r♦♦t ♦❢ t❤❡ m✲ t❤ ❞❡r✐✈❛t✐✈❡ ✐s ✉♥♥❡❝❡ss❛r② ❜❡❝❛✉s❡ m ✐s ♥❡❝❡ss❛r✐•② •❛r❣❡r t❤❛♥ ♦r ❡q✉❛• t♦ t❤❡ ❝♦rr❡❝t ♠✉•t✐♣•✐❝✐t② ♦❢ t❤❡ r♦♦t ✭❜② t❤❡ ♣r♦♦❢ ♦❢ ▲❡♠♠❛ ✷✮✳ ■❢✱ ❢♦r ❛•• S k ✱ ❛•• t❤❡ r♦♦ts ♦❢ t❤❡ |❯|s ❛r❡ ✐♥❞❡❡❞ r♦♦ts ♦❢ {P, Q}✱ ❛♥❞ ✐❢ t❤❡✐r ♠✉•t✐♣•✐❝✐t✐❡s ❛r❡ ❝♦rr❡❝t✱ t❤❡ s❡t ♦❢ r♦♦ts ✭✇✐t❤ ♠✉•t✐♣•✐❝✐t✐❡s✮ ✐s ♥❡❝❡ss❛r✐•② ❝♦r✲ r❡❝t ❜② ▲❡♠♠❛ ✷✳ ❖t❤❡r✇✐s❡ ✇❡ ❛❞❞ s♦♠❡ ♥❡✇ ♣r✐♠❡s ❛♥❞ •✐❢t ❛❣❛✐♥ t❤❡ r❡s✉•t✳ ✭❲❡ ♦♠✐t ❤❡r❡ s♦♠❡ ❞❡t❛✐•s✱ ✐♥❝•✉❞✐♥❣ t❤❛t ❛ ♣r✐♠❡ ♠❛② ❛•s♦ ❜❡ ✉♥•✉❝❦② ❢♦r t❤❡ ❝♦♠♣✉t❛t✐♦♥ ♦❢ t❤❡ |❯|s✳✮
2 Application to the topology of plane curves

❲❡ ♥♦✇ ❝♦♥s✐❞❡r t❤❡ ♣r♦❜•❡♠ ♦❢ ❝♦♠♣✉t✐♥❣ ❡✣❝✐❡♥t•② t❤❡ t♦♣♦•♦❣② ♦❢ ❛ r❡❛• ♣•❛♥❡ ❛•❣❡❜r❛✐❝ ❝✉r✈❡ C f ❞❡✲ ✜♥❡❞ ❜② ❛ ❜✐✈❛r✐❛t❡ ♣♦•②♥♦♠✐❛• f ✐♥ Q[x, y]✳ ■s♦t♦♣ ❬✷( ✐s ❛♥ ❛•❣♦r✐t❤♠ t❤❛t ✉s❡s •rö❜♥❡r ❜❛s✐s ❛♥❞ |❯| ❝♦♠♣✉t❛t✐♦♥ ❛s ❛ ❜•❛❝❦ ❜♦① ❢♦r ✐s♦•❛t✐♥❣ t❤❡ ❝r✐t✐❝❛• ♣♦✐♥ts ♦❢ C f ✱ t❤❛t ✐s t❤❡ ♣♦✐♥ts t❤❛t ❛r❡ s♦•✉t✐♦♥s ♦❢ {f, f y } ✇✐t❤ f y = ∂f ∂y ✳ ❈♦♠♣❛r❡❞ t♦ ♦t❤❡r ❛•❣♦r✐t❤♠s✱ ■s♦t♦♣ ✐s ♣❛rt✐❝✉•❛r•② ❡✣❝✐❡♥t ♦♥ ♥♦♥✲❣❡♥❡r✐❝ ❝✉r✈❡s ✭✐✳❡✳✱ ❝✉r✈❡s ✇✐t❤ s❡✈❡r❛• ❝r✐t✐❝❛• ♣♦✐♥ts ♦♥ s♦♠❡ ✈❡r✲ t✐❝❛• •✐♥❡✮ ❜❡❝❛✉s❡ t❤❡② ❛r❡ tr❡❛t❡❞ ✐♥ t❤❡ ♦r✐❣✐♥❛• ❝♦✲ ♦r❞✐♥❛t❡ s②st❡♠ ✇✐t❤♦✉t s❤❡❛r✐♥❣✳ ❍♦✇❡✈❡r✱ ■s♦t♦♣ ✐s •❡ss ❡✣❝✐❡♥t ♦♥ s♦♠❡ t②♣❡s ♦❢ ❣❡♥❡r✐❝ ❝✉r✈❡s✱ ✐♥ ♣❛rt✐❝✉•❛r ❢♦r ✭✐✮ ✏r❛♥❞♦♠✑ ❝✉r✈❡s ❢♦r ✇❤✐❝❤ t❤❡ ♠✉•✲ t✐♣•✐❝✐t② ♦❢ ❛•• ❝r✐t✐❝❛• ♣♦✐♥ts ✐♥ t❤❡✐r ✜❜❡r ✐s ✷✱ ❛♥❞ ✭✐✐✮ ❣❡♥❡r✐❝ ❝✉r✈❡s s✉❝❤ t❤❛t t❤❡ ♠✉•t✐♣•✐❝✐t② ✭✐♥ t❤❡ ✜❜❡r✮ ♦❢ s♦♠❡ ❝r✐t✐❝❛• ♣♦✐♥ts ✐s ❤✐❣❤✳ ■♥ ❝❛s❡ ✭✐✮✱ t❤❡ •rö❜✲ ♥❡r ❜❛s✐s ❝♦♠♣✉t❛t✐♦♥ ✐s ❡①♣❡♥s✐✈❡ ❝♦♠♣❛r❡❞ t♦ t❤❡ s✉❜✲r❡s✉•t❛♥t s❡q✉❡♥❝❡ ❞❡❝♦♠♣♦s✐t✐♦♥ ❛♣♣r♦❛❝❤ ♦❢ ❬✸( ❜❡❝❛✉s❡ t❤❡ ❞❡❝♦♠♣♦s✐t✐♦♥ •❡❛❞s t♦ ❛ ✉♥✐q✉❡ s②st❡♠ S 1 ✳ ■♥ ❝❛s❡ ✭✐✐✮✱ t❤❡ |❯| ❝♦♠♣✉t❛t✐♦♥ ✭♣❡r❢♦r♠❡❞ ❛s ❛ ❜•❛❝❦ ❜♦① ♦♥ ❛ •rö❜♥❡r ❜❛s✐s ♦❢ {f, f y }✮ t✉r♥s ♦✉t t♦ ❛•s♦ ❜❡ ❡①♣❡♥s✐✈❡ ❝♦♠♣❛r❡❞ t♦ t❤❡ ❞❡❝♦♠♣♦s✐t✐♦♥ ❛♣♣r♦❛❝❤ ❜❡❝❛✉s❡ ♠✉•t✐♣•✐❝✐t✐❡s ✐♥ t❤❡ ✐♥✐t✐❛• s②st❡♠ ❛r❡ ❦❡♣t ✭r❡❢❡r t♦ ❬✷( ❢♦r ❞❡t❛✐•s✮✳ ❖✉r ❝♦♥tr✐❜✉t✐♦♥ ✐s t♦ ❝❤❛♥❣❡ t❤❡ •rö❜♥❡r ❜❛s✐s ❛♥❞ |❯| ❜•❛❝❦ ❜♦① ❜② t❤❡ s♦•✈❡r ♣r❡s❡♥t❡❞ ✐♥ s❡❝t✐♦♥ ✶✳ ❚❤❡ ✐❞❡❛ ❜❡✐♥❣ t♦ ❞❡❝♦♠♣♦s❡ t❤❡ ✐♥♣✉t s②st❡♠ ✇❤❡♥ ♣♦ss✐❜•❡ ✇❤✐•❡ ❦❡❡♣✐♥❣ |❯| ❛♣♣r♦❛❝❤ ❢♦r s♦•✈✐♥❣ t❤❡s❡ s②st❡♠s✳ ❚❤✐s ②✐❡•❞s t✇♦ ♠❛✐♥ ❝❤❛♥❣❡s t♦ t❤❡ ■s♦t♦♣ ❛•❣♦r✐t❤♠✿ t❤❡ ✇❛② t♦ ❝♦♠♣

  ✉t❡ ❝r✐t✐❝❛• ♣♦✐♥ts✱ ❛♥❞ t♦ ❞❡t❡r♠✐♥❡ ♠✉•t✐♣•✐❝✐t✐❡s ✐♥ ✜❜❡rs✳ ❈♦♠♣✉t✐♥❣ ❝r✐t✐❝❛• ♣♦✐♥ts ♦❢ t❤❡ ❝✉r✈❡ C f ✳ ❈r✐t✲ ✐❝❛• ♣♦✐♥ts ♦❢ C f ❛r❡ t❤❡ s♦•✉t✐♦♥s ♦❢ t❤❡ s②st❡♠ S = {f, f y }✳ ❲❡ ✐s♦•❛t❡ t❤❡s❡ s♦•✉t✐♦♥s ❜② ❞❡❝♦♠✲ ♣♦s✐♥❣ S ✐♥ tr✐❛♥❣✉•❛r s②st❡♠s S i ❛♥❞ ❝♦♠♣✉t✐♥❣ t❤❡✐r |❯|s ❛❝❝♦r❞✐♥❣ t♦ t❤❡ ❛•❣♦r✐t❤♠ ♣r❡s❡♥t❡❞ ✐♥ ❙❡❝t✳ ✶✳ ❈♦♠♣✉t✐♥❣ t❤❡ ♠✉•t✐♣•✐❝✐t✐❡s ♦❢ ❝r✐t✐❝❛• ♣♦✐♥ts ✐♥ t❤❡✐r ✜❜❡rs✳ ❋♦r ❛ ♣♦✐♥t ♣ = (α, β) ♦♥ t❤❡ ❝✉r✈❡ C f ✱ t❤❡ ♠✉•t✐♣•✐❝✐t② ♦❢ ♣ ✐♥ ✐ts ✜❜❡r ❞❡♥♦t❡❞ ❜② mult(f (α, y), β) ✐s ❞❡✜♥❡❞ ❛s t❤❡ ♠✉•t✐♣•✐❝✐t② ♦❢ β ✐♥ t❤❡ ✉♥✐✈❛r✐❛t❡ ♣♦•②♥♦♠✐❛• f (α, y)✳ ❙♦•✈✐♥❣ t❤❡ s②s✲ t❡♠s S i ✇✐t❤ |❯|s ❡♥❛❜•❡s t♦ ♣r❡s❡r✈❡ t❤❡ ♠✉•t✐♣•✐❝✲ ✐t✐❡s ❛♥❞✱ ❤❡♥❝❡✱ t♦ ❝♦♠♣✉t❡ t❤❡ ♠✉•t✐♣•✐❝✐t✐❡s ✐♥ t❤❡ ✜❜❡rs ❡✈❡♥ ✐❢ t❤❡r❡ ❛r❡ s❡✈❡r❛• ❝r✐t✐❝❛• ♣♦✐♥ts ✇✐t❤ t❤❡ s❛♠❡ x✲❝♦♦r❞✐♥❛t❡✿ Pr♦♣♦s✐t✐♦♥ ✸ ■❢ ♣ ✐s ❛ ❝r✐t✐❝❛• ♣♦✐♥t ♦❢ C f t❤❡♥ ✐t ✐s ❛ s♦•✉t✐♦♥ ♦❢ s♦♠❡ s②st❡♠ S i ✱ ❛♥❞ ✐ts ♠✉•t✐♣•✐❝✐t② ✐♥ ✐ts ✜❜❡r ✐s ✐ts ♠✉•t✐♣•✐❝✐t② ✐s S i ♣•✉s ♦♥❡✳ Pr❡•✐♠✐♥❛r② ❡①♣❡r✐♠❡♥ts✳ ❲❡ ❤❛✈❡ ❝♦♠♣✉t❡❞ t❤❡ r❛t✐♦ ♦❢ r✉♥♥✐♥❣ t✐♠❡s ♦❢ t❤❡ ♦r✐❣✐♥❛• ■s♦t♦♣ ❛•❣♦r✐t❤♠ ✇✐t❤ ✐ts ♥❡✇ ✈❡rs✐♦♥✱ ■s♦t♦♣✷✱ ✉s✐♥❣ ♦✉r s♦•✈❡r ❛s ❡①✲ ♣•❛✐♥❡❞ ✐♥ ❙❡❝t✐♦♥ ✷✳ ❆s ❡①♣❡❝t❡❞ t❤❡ r❛t✐♦ ✐s •❛r❣❡ ❢♦r ❣❡♥❡r✐❝ ❝✉r✈❡s ✭❛ r❛t✐♦ ❜❡t✇❡❡♥ ✺ ❛♥❞ ✶✹ ♦♥ ❝✉r✈❡s ♦❢ ❞❡❣r❡❡ ❜❡t✇❡❡♥ ✶✵ ❛♥❞ ✷✵✮ ❛♥❞ ✇❡ ❛•s♦ ❤❛✈❡ ❛ s✐❣♥✐❢✲ ✐❝❛♥t ❣❛✐♥ ❢♦r ♥♦♥✲❣❡♥❡r✐❝ ❝✉r✈❡s ✭❛ r❛t✐♦ ❜❡t✇❡❡♥ ✶✳✺ ❛♥❞ ✶✺ ❢♦r ❞❡❣r❡❡s ❜❡t✇❡❡♥ ✶✷ ❛♥❞ ✷✽✮✳ ❚❤❡s❡ ♣r❡•✐♠✲ ✐♥❛r② t❡sts ❤❡♥❝❡ ❝♦♥✜r♠ t❤❡ t❤❡♦r❡t✐❝❛• ❛♥❛•②s✐s t❤❛t ♦✉r ❛♣♣r♦❛❝❤ ❛✉t♦♠❛t✐❝❛••② s❡•❡❝ts t❤❡ ❜❡st str❛t❡❣② ✐♥ ❛♥② ❝❛s❡✳