text:
# EARLY HIERARCHICAL FORMATION OF MASSIVE GALAXIES TRIGGERED BY INTERACTIONS

## 1. Introduction

Current hierarchical theories of galaxy formation envisage the build up of stars in galaxies as a gradual process driven by the continuous growth of the host dark matter (DM) galactic halos through repeated merging events. These progressively increase also the gas mass in the growing galaxies; its subsequent radiative cooling is partially counteracted by the heating due to the winds from Supernovae originated by parent massive stars. The net result of such a ”quiescent” star formation is a gradual increase of the stellar content of the galaxies.

But when the picture is quantitatively modeled through the semi-analytic models (SAMs, Kauffmann et al. 1993; Somerville & Primack 1999; Cole et al. 2000; Menci et al. 2002) the resulting amount of stars formed at high $`z`$ in the bright galaxy population is lower than indicated by several observational results.

Among these we mention first the excess of the cosmic density of bright galaxies observed to be in excess over the model predictions at $`z35`$. True that several groups (e.g., Cole et al. 2000; , Somerville Primack & Faber 2001; Fontana et al. 2003a) have shown the canonical SAMs (i.e., with no merging-induced starbursts) to provide a total star formation history (integrated over all luminosities) consistent with observations. But when one focuses on the UV luminosity density produced by the brightest galaxies only, these SAMs underpredict the luminosity densities observed at $`z4`$ (Fontana et al. 1999, 2003a). This traces back to the fact that the detailed shape of the luminosity functions (LFs) from SAMs are appreciably steeper than the observed ones at these redshifts. Actually, the SAMs overpredict the number of faint galaxies and, for the canonical SAMs with quiescent star formation only, they underpredict the bright ones, see Somerville, Primack & Faber (2001).

Second, and most important, the SAMs underpredict both the bright galaxies observed in the K-band luminosity functions at intermediate redshifts ($`z12`$, see Pozzetti et al. 2003) and the galaxies brighter than $`K=20`$ counted at $`z>1.5`$ (Cimatti et al. 2002). The emission in the K-band is largely contributed by old stellar populations, and so is a measure of the amount of stars already formed; thus the above observations imply that the star content of massive galaxies already in place at $`z2`$ is larger than that resulting from the gradual star formation typical of hierarchical models. Indeed, independent, direct observations at $`z2`$ of the stellar mass density of massive galaxies (in the range $`m_{}10^{10}10^{11}`$ $`M_{}`$) yield a fraction close to 0.3 of the present value, while the canonical (no-burst) SAMs yield a fraction around 0.1 (see Fontana et al. 2003b). The above results concur to indicate that the physics of hierarchical galaxy formation still lacks some basic process enhancing star formation in massive galaxies.

A candidate for such an enhancement is constituted by starbursts triggered by galaxy interactions, as proposed by Somerville, Primack & Faber (2001), see also Cavaliere & Menci (1993). The former authors assumed that satellite galaxies contained in the same host DM halo (i.e., in groups or clusters of galaxies) may undergo binary aggregations, which would not only affect their mass distribution but also brighten them by triggering starbursts. In such a model, only encounters leading to outright merging are considered; in addition, the fraction of galactic gas converted into stars during each burst is taken to be constant in time, with a parametrized dependence on the merger mass ratio which favors major mergers. The resulting starbursts, while improving the match with the observed UV LFs at $`z=3`$ and $`z=4`$, still do not provide enough high-$`z`$ star formation to account for the number of bright ($`K>20`$) galaxies at $`z>1.5`$ observed by Cimatti et al. (2002).

Thus one main problem with the current SAMs is their failure to form enough stars at high-$`z`$ in bright galaxies, so as to match the observed bright end of the $`K`$-band LFs at intermediate $`z`$.

Here we address the issue on the basis of a more complete description of the starbursts triggered by galaxy encounters. This is based on the physical model for the destabilization of cold galactic gas during galactic merging and fly-by developed by Cavaliere & Vittorini (2000, CV00). The destabilized gas is assumed to feed in part the accretion onto a central super-massive black hole (BH) so powering quasar-like emission, and in part a burst of star formation. The amount of destabilized gas, the duration of the bursts, and their rate set by the galaxy encounters are determined by the physical properties of the galaxies and of their host halos, groups or clusters. While CV00 adopted simplified derivations for the galactic properties in common DM halos, here such properties are self-consistently computed from the SAM presented in Menci et al. (2002).

In a previous paper (Menci et al. 2003) we have shown that the quasar (QSO) evolution resulting from such a model is in excellent agreement with a whole set of observables. Here we focus on the circumnuclear starbursts originating from the fraction of cold gas destabilized in galaxy encounters complementary to the gas accreted to the central supermassive BH; such starbursts mainly affect the massive galaxy population.

We recall in Sect. 2 the basic features of the SAM presented in Menci et al. (2002), while in Sect. 3 we present our treatment of the new processes included in our present model, i.e., the fly-by events and the associated destabilization of cold galactic gas. The results are presented in Sect. 4, while Sect. 5 is devoted to conclusions and discussion.

## 2. Modeling the Galaxy Evolution

To describe the galaxy evolution in the hierarchical scenario, we adopt the SAM described in detail in Menci et al. (2002); here we recall the basic points. We consider both the host DM halos containing the galaxies (i.e., groups and clusters of galaxies with mass $`M`$, virial radius $`R`$ and circular velocity $`V`$), and the DM clumps (with mass $`m`$, radius $`r`$ and circular velocity $`v`$) associated with the individual member galaxies. The former grow hierarchically to larger sizes through repeated merging events (at the rate given in Lacey & Cole 1993), while the latter may coalesce either with the central galaxy in the common halo due to dynamical friction, or with other satellite galaxies through binary aggregations. The timescale for the dynamical friction and the binary merging processes, and so the probability for such processes to occur in each timestep, are given by eq. (2) and (4) in Menci et al. (2002).

We assume initially (at $`z10`$) one galaxy in each host structure, with the latter following the Press & Schechter mass distribution. The probability for the merging processes (dynamical friction and binary aggregations) to occur during the hierarchical growth of the hosting structure yields the differential distribution function $`N(v,V,t)`$ of galaxies with given $`v`$ in hosts with circular velocity $`V`$ at the cosmic time $`t`$. From $`N(v,V,t)`$ we derive the number $`N_T(V,t)`$ of galaxies in a host halo (membership), and the overall distribution of galaxy circular velocity $`N(v,t)`$ irrespective of the host.

The properties of the baryons (gas and stars) contained in the galactic DM clumps are computed as follows. Starting from an initial amount $`m\mathrm{\Omega }_b/\mathrm{\Omega }`$ of gas at the virial temperature of the galactic halos, we compute the mass $`m_c`$ of cold baryons within the cooling radius. The disk associated to the cold baryons will have a radius $`r_d(v)`$, rotation velocity $`v_d(v)`$, and dynamical time $`t_d=r_d/v_d`$, all computed after Mo, Mao & White (1998). From such a cold phase, stars are allowed to form at the rate

$$\dot{m}_{}=\frac{m_c}{t_{dyn}}\left(\frac{v}{200\mathrm{km}\mathrm{s}^1}\right)^\alpha _{}$$
(1)
Finally, a mass $`\mathrm{\Delta }m_h=\beta m_{}`$ is returned from the cool to the hot gas phase due to the energy fed back by canonical type II Supernovae associated to $`m_{}`$; the feedback efficiency is taken to be $`\beta =(v/v_h)^{\alpha _h}`$. The values adopted for the parameters $`\alpha _{}=1.5`$, $`\alpha _h=2`$ and $`v_h=150`$ km/s fit both the local B-band galaxy LF and the Tully-Fisher relation, as illustrated by Menci et al. (2002).

At each merging event, the masses of the different baryonic phases are refueled by those in the merging partner. The further increments $`\mathrm{\Delta }m_c`$, $`\mathrm{\Delta }m_{}`$, $`\mathrm{\Delta }m_h`$ from cooling, star formation and feedback are recomputed on iterating the procedure described above.

Thus, for each galactic $`v`$, the star formation defined by eq. (1) is driven by the cooling rate of the hot gas and by the rate of refueling of cold gas, which in turn is related to the progressive growth of the total galactic mass along the merging tree. The related brightening of galaxies is a gradual process, and the associated star formation history is often referred to as ”quiescent” star formation.

The integrated stellar emission $`S_\lambda (v,t)`$ at the wavelength $`\lambda `$ is computed by convolving the SFR with the spectral energy distribution $`\varphi _\lambda `$ obtained from population synthesis models:

$$S_\lambda (v,t)=_0^t𝑑t^{}\varphi _\lambda (tt^{})\dot{m}_{}(v,t^{}).$$
(2)
In the following we adopt $`\varphi _\lambda `$ taken from Bruzual & Charlot (1993), with a Salpeter IMF. The dust extinction is computed as described in Menci et al. (2002).

All computations are made in a $`\mathrm{\Lambda }`$-CDM cosmology with $`\mathrm{\Omega }_0=0.3`$, $`\mathrm{\Omega }_\lambda =0.7`$, a baryon fraction $`\mathrm{\Omega }_b=0.03`$, and Hubble constant $`h=0.7`$ in units of 100 km s-1 Mpc-1.

## 3. Star Formation triggered by Galaxy Encounters

In the present work, we upgrade the above model by adding a treatment of fly-by events (i.e., encounters which do not lead to bound merging) and of the related bursts of star formation. Indeed, galaxy encounters are expected to destabilize part of the available cool gas by causing it to loose or transfer angular momentum (Barnes & Hernquist 1998; Mihos 1999); this triggers gas inflow. The gas funneled inward may end up in accretion onto a central supermassive BHs, but also in a nuclear starburst (see Sanders & Mirabel 1996). A quantitative model to derive the fraction $`f`$ of cold gas destabilized by the encounters has been worked out by CV00; here we recall the guidelines in terms suitable for direct implementation in our SAM.

The fraction of cold gas which is destabilized in each interaction event and feeds the starbursts is derived from eq. A3 of CV00 in terms of the variation $`\mathrm{\Delta }j`$ of the specific angular momentum $`jGm/v_d`$ of the gas; in slow, grazing encounters between galaxies with relative velocity $`V_r`$ one obtains:

$$f(v,V)\frac{3}{8}\left|\frac{\mathrm{\Delta }j}{j}\right|=\frac{3}{8}\frac{m^{}}{m}\frac{r_d}{b}\frac{v_d}{V_r}.$$
(3)
The effective impact parameter $`b=max[r_d,\overline{d}(V)]`$ is the maximum between the radius $`r_d`$ and the average distance $`\overline{d}(V)=R/N_T^{1/3}`$ of the galaxies in the halo; we take $`V_r`$ to be twice the one-dimensional velocity dispersion $`\sigma _V=V/\sqrt{2}`$ of the host halo. The first approximate equality is derived by considering the amount of gas which is in centrifugal equilibrium outside a circumnuclear region of fixed size; since the extension $`\mathrm{\Delta }r`$ of the outer region is proportional to $`j`$ (see, e.g., Mo, Mao & White 1998), a loss of angular momentum implies a negative $`\mathrm{\Delta }r`$ and hence a mass flow toward the circumnuclear region. As for the prefactor, it accounts for the probability 1/2 of inflow rather than outflow related to the sign of $`\mathrm{\Delta }j`$. We assume that $`1/4`$ of the inflow feeds the central BH, while the remaining fraction is assumed to kindle circumnuclear starbursts, see Sanders & Mirabel (1996); thus, the starbursts efficiency $`f`$ in eq. (3) is three times larger than the complementary BH accretion efficiency shown in fig. 1 of Menci et al. (2003).

The last equality in eq. (3) has been derived by CV00 by computing the variation $`\mathrm{\Delta }j=Gm^{}r_d/Vb`$ of the angular momentum in the galaxy from the gravitational torque (proportional to the disk size $`r_d`$) exerted by the partner galaxy with mass $`m^{}`$; this is time-integrated along the partner orbit. Note that the dependence of $`\mathrm{\Delta }j`$ on $`r_d`$ causes the the amount of destabilized gas to be larger in more massive systems. The average runs over the probability of finding a galaxy with mass $`m^{}`$ in the same halo $`V`$ where the galaxy $`m`$ is located.

When inserted into our SAM and applied to the BH accretion and to the related QSO emission (Menci et al. 2003), the above model has proven to be very successful in reproducing the observed properties of the QSO population from $`z=6`$ to the present, including the rapid decline of their densities from $`z2.5`$ to $`z=0`$ and even the detailed changes of their LF from $`z5`$ to $`z=0`$. In the present picture, the interaction-driven starbursts constitute the ”counterpart” of the BH accretion powering the QSOs.

To compute the average effects of the cold gas destabilization on the star formation rate and hence on the galactic emission, we derive the probability for a given galaxy to be in a burst phase. This is defined as the ratio $`\tau _e/\tau _r`$ of the duration of the burst to the average time interval between bursts.

In turn, such quantities can be derived from a detailed analysis of the orbital parameters (see Saslaw 1985); following CV00, here we just recall that tides effective for angular momentum transfer (as considered in eq. 3) require two conditions: the interaction time is to be comparable with the internal oscillation time in the galaxies involved (resonance); the orbital specific energy of the partners is not to exceed the sum of the specific internal gravitational energies of the partners. The rate of such encounters $`\tau _r^1`$ is then given by Saslaw (1985) in terms of the distance $`r_t2r`$; for a galaxy with given $`v`$ inside a host halo with circular velocity $`V`$ the result reads

$$\tau _r^1=n_T(V)\mathrm{\Sigma }(v,V)V_r(V),$$
(4)
where $`n_T=3N_T/4\pi `$$`R^3`$, and the cross section is averaged over all partners with effective tidal radius $`r_t^{}`$ in the same halo $`V`$. The membership $`N_T`$, and the distributions of $`v^{}`$, $`r_t^{}`$ and $`V_r`$ are computed from the SAM described in §2.

The condition for a grazing encounter defines the encounter duration $`\tau _e=(r_t+r_t^{^{}})/V_r`$ (with the upper limit given by $`\tau _r`$ in eq. 4) where the average is again over all partners with tidal radius $`r_t^{}`$ in the same host halo $`V`$. It must be noted that the cross section in eq. (4) determines the probability for any grazing encounter including the fly-by events, which are in fact more frequent than major mergers and dominate the statistics of galaxy encounters. We also stress that in our model the eq. (4) determines only the probability $`\tau _e/\tau _r`$ of finding a galaxy in the burst phase, but does not affect the evolution of the galaxy mass function. This is instead determined by the processes of dynamical friction and binary aggregation proper, for which we retain the cross sections given in Menci et al. (2002), and recalled in Sect. 3.

The average SFR associated to the destabilized cold gas during an encounter lasting a time $`\tau _e`$ reads,

$$\mathrm{\Delta }\dot{m}_{}(v,z)=\frac{f(v,V)m_c(v)}{\tau _e(v,V)}_{\tau _e/\tau _r}.$$
(5)
The average is here over all host halos with circular velocity $`V`$, and is weighted with the probability $`\tau _e/\tau _r`$ of finding the galaxy in the burst phase.

We remark that our model includes the effects of both fly-by events and bound mergings. Although the former induce starbursts with a lower efficiency ($`f0.10.4`$ at $`z3`$) they contribute appreciably to the average star formation rate in bursts (eq. 5). In fact, the fly-by events are more probable than major mergers, and hence provide larger values for the probability $`\tau _e/\tau _r`$ entering the average in eq. 5. This holds even though for major merging events (requiring small relative velocities and hence small values of $`V_r`$ in eq. 3) the efficiency may attain values $`f0.7`$, consistent with the values 0.65-0.8 obtained in the hydrodynamical simulations by Mihos & Hernquist (1996), and close to the values observed in SCUBA sources and in the local Ultra Luminous Infrared Galaxies (see Blain et al. 2002 and references therein; Sanders & Mirabel 1996). At $`z3`$, the contributions to eq. (5) from merging and from fly-by events are comparable.

The average contribution to the stellar emission $`S(v,t)`$ from bursts in a galaxy with circular velocity $`v`$ at the time $`t`$ is given by eq. (2), with the quiescent star formation rate $`\dot{m}_{}`$ replaced by the starbursts rate $`\mathrm{\Delta }\dot{m}_{}(v,t)`$ given by eq. (5). From $`S(v,t)`$ we compute the LF given by $`N(v,t)dv/dS`$.

## 4. Results

In fig. 1 (bottom panel) we show the effect of bursts on the B-band LF of galaxies at $`z=0`$, and on the UV LFs $`z=3`$ and at $`z=4`$.

Fig. 1. - The predicted LFs of galaxies in the quiescent (blue dashed lines) and starburst modes (red solid lines) at $`z0`$ (in the B-band, top panel), and at $`z3`$ and $`z4`$ (at 1400 Å, middle and bottom panels, respectively). In the top panel, the shaded area corresponds to the LF measured by the Sloan Digital Sky Survey (Blanton et al. 2000), and the circles to the data from the 2dFGRS survey (Madgwick et al. 2002). In the middle and bottom panels, the two red solid lines refer to the burst model and bracket the uncertain due to different dust extinction curves (represented by the shaded regions) for given dust-to-gas ratio, see text. Similarly for the blue dashed curves (and the comprised shaded areas) referring to the quiescent model. The spectroscopic (solid squares) and the photometric (open squares) data are from Steidel et al. (1999).

As the emission in the UV (and, to a minor extent, that in the B-band) is contributed by massive, short-living stars, the LFs in fig. 1 show the effect of bursts on the instantaneous star formation at low and high redshifts. At low $`z`$ (top panel) the LFs are little affected by starbursts whose effect, if anything, is to make the model LF closer to that measured by in Sloan survey (Blanton et al. 2000).

At high $`z`$, the predictions for the UV LFs are shown in the bottom panels, and compared with data uncorrected for extinction, since the dust absorption is included in the model. In particular, we implemented in our SAM the Milky Way, the Small Magellanic Cloud (SMC) and the Calzetti extinction curves, with the dust optical depth fixed by the fit to the local LF. The related uncertainties in the model predictions are illustrated by showing (for both the quiescent and the starburst modes) the brightest and the faintest LFs (corresponding to the SMC and to the Calzetti curves, respectively). Note that at high $`z`$ the interactions are more effective in stimulating starbursts; at $`z=4`$, compared with the quiescent mode, they brighten the galaxy LF by an amount which grows with the luminosity to reach about $`0.7`$ mag in the brightest magnitude bin. Note also that the inclusion of bursts does not appreciably affect the LFs for galaxies fainter than $`M_B20`$.

Indeed, burst are more efficient in high mass than in low mass systems, since the former have larger cross section for encounters (see eq. 4). In addition, in each encounter the amount of destabilized gas is larger in more massive galaxies, since the loss of angular momentum is larger for larger disks as discussed below eq. 3.

As a function of time, fig. 1 shows that galactic encounters are increasingly effective in stimulating starbursts for increasing $`z`$. In fact, the interaction rate $`\tau _r^1`$ and the accreted fraction $`f`$ decrease with increasing $`t`$, since in the growing host halos the growing membership $`N_T(V)`$ is offset by $`R`$, $`V`$ and $`V_r`$ increasing (see eqs. 3, 4). In a group, the average values for $`f`$ drop from from a few $`10^1`$ to several $`10^3`$ on going from $`z3`$ to $`z=0`$, as shown in fig. 1 of Menci et al. (2003) (the latter paper shows the efficiency for BH accretion which is three times lower than the efficiency for starbursts, as discussed below eq. 3); higher values up to $`f0.4`$ are instead attained at $`z3`$.

Thus, at low redshifts the lower densities and larger relative velocities of the galaxies contained in the same host environment suppress the effectiveness of the interactions and hence of the associated starbursts.

Fig. 2. - The predicted UV luminosity densities (at 1400 Å) compared with data. Solid squares refer to the data for galaxies with $`m_Z<25`$ (Fontana et al. 2003a), while the shaded areas (heavy and red for the model with bursts, light and blue for the pure quiescent model) represent the model predictions – at the same limiting magnitude – adopting different extinction curves in the models (see text). In addition we plot the UV luminosity density obtained by Giavalisco et al. (2003, empty circles) by integrating the observed UV LFs down to $`0.2L_3`$ (where $`L_3`$ is the characteristic luminosity of observed Ly-break galaxies at $`z=3`$), compared with the prediction of our model for the same luminosity cut (red heavy solid line) averaged over the three extinction curves we considered in the text. We also show the total UV luminosity density in the burst (red dotted line) and quiescent (blue dashed line) models, averaged over the dust extinction as above.

Such a picture is borne out by fig. 2, where we show the effect of bursts on the cosmic UV luminosity density produced by galaxies, and compare it with existing observations. These are based on HST and VLT imaging surveys aimed at identifying high-$`z`$ galaxies. The data concerning the UV luminosity density contributed by the bright ($`m_Z<25`$) galaxy population are compared with the model predictions; for these we also show the uncertainties due to the different extinction curves, represented as shaded areas. In addition, we compare with the recent data from Giavalisco et al. (2003) concerning the density contributed also by fainter galaxies, with the lower limit in luminosity provided in the caption.

We note that when the UV luminosity density contributed only by bright ($`m_Z<25`$) galaxies is considered, the canonical SAMs (with no bursts) underpredict the observed values. This is because such models fail to provide enough star formation to match (once dust is included) the bright end of the UV LFs at $`z4`$ (see fig. 1). However, when one considers the total UV luminosity density (obtained by integrating the LFs over all luminosities) the same models provide a sustained luminosity density (the dashed line) up to large $`z`$. This is because the shape of the LFs from such SAMs are appreciably steeper than the observed ones at high $`z`$; while such models underpredict the density of bright sources, they overpredict the number of faint galaxies. The two effects balance as to yield a sustained total UV luminosity density at high $`z`$, as shown in fig. 2.

On the other hand, the burst model naturally provides more star formation in massive galaxies and so matches in detail the observed UV luminosity density from bright galaxies with $`m_Z<25`$. We also compare our burst model with the observed UV luminosity density contributed by fainter galaxies. Following the discussion above, any such comparison depends critically on the lower luminosity limit for the integration of the UV LFs. So in comparing our prediction (heavy solid line in fig. 2) with the data from Giavalisco et al. (2003) we adopt the same luminosity cut used by such authors (see caption), finding a good agreement with observations.

As a result, in the starburst scenario the fraction of stars predicted to be already formed in massive galaxies by $`z2`$ is significantly larger then in the quiescent models. This, in turn affects the galaxy LFs and the corresponding redshift distributions in the $`K`$ band; here the emission is largely contributed by evolved stellar populations, so probing the total amount of stars which have been assembled in galaxies by a given cosmic time. In the following, we shall focus on such issues since, as we recalled in Sect. 1, matching the K-band observables and the stellar mass density at intermediate redshifts constitutes one main problem for canonical SAMs.

In fig. 3 we compare the results with observations obtained from the K20 survey (Cimatti et al. 2002; Pozzetti et al. 2003). The starbursts brighten the LF by $`0.5`$ mag at $`z1.5`$, so matching the observed shape of the LFs (top panel). Meanwhile the faint end of the LFs is left almost unchanged. This is again a consequence of the larger effectiveness of the bursts in more massive galaxies, which is due to the physics of interaction-driven bursts combining with the statistics of encounters. On the one hand, in each bursts galaxies with larger disk sizes undergo larger losses of angular momentum as a consequence of larger gravitational torques, as explained below eq. (3); on the other hand, larger galactic sizes favor the encounters, as described in detail below eq. (4). Correspondingly, the burst model matches the observed number of luminous ($`m_K<20`$) galaxies at $`z1.5`$, while the quiescent model underpredicts the number by a factor $`34`$ (see bottom panel in fig. 3).

Fig. 3. - Upper panel: the K-band galaxy LFs at $`z=1.5`$ in the quiescent (blue dashed line) and in the starburst model (red solid line) are compared with the data from the K20 survey (Pozzetti et al. 2003). Bottom panel: the corresponding cumulative $`z`$-distribution of $`m_K<20`$ galaxies are compared with observations from the K20 survey (Cimatti et al. 2002). The inset shows in detail the cumulative distribution in the range $`1<z<3`$ with the $`3\sigma `$ Poissonian confidence region (shaded area); the dotted line reproduces from Cimatti et al. (2002) the prediction of the SAM by Somerville, Primack, & Faber (2001).

Inspection of fig. 3 shows that our burst model provides a better fit to the observed $`z`$-distribution of galaxies with $`m_K<20`$ than the SAM by Somerville, Primack e Faber (2001), which also included starbursts. The reason is that our model provides a higher star formation rate at high redshift. This is shown by the dotted line in fig. 2; when the total UV luminosity density of our model is converted to a total density of star formation, the resulting star formation rate is larger than the Somerville, Primack & Faber (2001) rate at $`z>4`$ for any reasonable dust extinction adopted in the conversion. The improvement is achieved despite of an average value of the burst efficiency $`f`$ somewhat lower than adopted by Somerville, Primack e Faber (2001).

Our improvement is due to two circumstances. First, the above authors associate starbursts only to bound mergers; for such events (requiring very slow encounters with small $`V_r`$) we obtain from eq. (3) values $`f0.7`$ comparable to theirs, as these particular interactions are maximally effective in inducing loss of gas angular momentum. However, in our model we also consider the effect of the more frequent fly-by events not leading to outright merging of the involved galaxies. These produce starbursts with a lower efficiency $`f0.10.4`$ (at $`z3`$), but dominate the encounter statistics. While they yield a low average $`f`$, the key quantity for $`\mathrm{\Delta }m_{}`$ is instead the product $`f\tau _r^1`$ (i.e., the efficiency weighted with the interaction rate) which is enhanced by the fly-by events, see eq. (5) and the discussion below it. Second, the dynamics of sub-halo mergers in our model slightly favors the formation of massive galaxies at high-$`z`$ compared to SPF. This is because the cross section we adopt for bound mergers (taken from Menci et al. 2002, eq. 4) is somewhat larger than that used by Somerville, Primack & Faber (2001), especially at high $`z`$. In fact, the above authors adopt the cross section derived by Makino & Hut (1997) from N- body simulations, strictly valid for encounters between equal galaxies in the limit of large relative velocities. Our cross section, although reducing to the Makino & Hut’s (1997) in the proper limit of merging between equal galaxies with large $`V_r`$ (as shown in Menci et al. 2002), also holds for lower relative velocities. This is particularly relevant at high $`z4`$, when galaxies reside in environments with low velocity dispersions.

Fig. 4. - The evolution of the stellar mass density (normalized to the present) for galaxies with stellar mass in the range $`10^{10}M_{}<m_{}<10^{11}M_{}`$ in the starburst mode (red solid line) and in the quiescent mode (blue dashed line) is compared with data from Dickinson et al. (2003, open squares) and from Fontana et al. (2003, solid squares). The triangles show the upper limit obtained on adopting the ”maximal mass” algorithm of Fontana et al. (2003b).

The enhancement in the fraction of stars formed in massive galaxies at high redshift $`z>3`$ due to our treatment of the bursts is illustrated by fig. (4). There we show for both the burst and the quiescent modes the evolution of the stellar mass density in massive ($`10^{10}M_{}<m_{}<10^{11}M_{}`$) systems, and compare it with various observations. Although the present data are not sufficient by themselves to discriminate between the two models, the plot clearly shows that at $`z2`$ the model with bursts predicts a fraction of stars formed in massive systems which is 2.5 times larger than predicted in the quiescent models.

## 5. Conclusions

We have presented the results of a SAM which includes a physical model for starbursts. The latter originate from the destabilization of cold galactic gas occurring in galaxy encounters as described by Cavaliere & Vittorini (2000). In this picture, part of the destabilized gas feeds the accretion onto BHs powering the QSOs (see Menci et al. 2003), while the complementary, larger fraction produces circumnuclear starsbursts at redshifts $`z24`$, preferentially in massive objects. This speeds up the star formation in massive galaxies (favored by their larger cross sections for encounters) at high redshifts (when the higher densities and the slower relative velocities of galaxies in common halos favor strong interactions). The LFs resulting in our model match those of luminous ($`M_B<21`$) Lyman-break galaxies observed at $`z=3`$ and 4, while leaving almost unchanged the model predictions for fainter objects. Thus, at $`z2`$, a larger fraction of the stellar content of the massive galaxies is already in place, at variance with the predictions of previous hierarchical models; the resulting K-band LFs and $`z`$\- distributions match the existing data.

Compared to Somerville, Primack, & Faber (2001) our model gives qualitatively similar results, but a better fit (see fig. 3) to the observed $`z`$-distribution of bright $`K>20`$ galaxies at $`z1.5`$. Such a larger rate is mainly due to the novel inclusion of fly-by events which, although producing starbursts with lower efficiency ($`f0.10.2`$ at $`z3`$), are more frequent than the bound merging events. In our picture, the UV luminosity, and hence the star formation rate, of massive galaxies at high redshift is in part contributed by the few powerful starbursts occurring in major merging events, and in part by a more widespread, though less powerful, brightening of galaxies almost continuously stimulated by the frequent encounters. In this regime, a considerable fraction close to $`0.25`$ of the present stellar content of massive ($`10^{10}M_{}<m_{}<10^{11}M_{}`$) galaxies is formed by $`z=2`$, see fig. 4. As a result, at lower redshifts $`z1.5`$ a considerable fraction of massive galaxies contains a stellar population evolved enough to provide the bright $`K`$-band luminosities required to match the observed LFs and counts.

In sum, we have shown that making early massive galaxies takes not only the early collapse of large DM halos favored in the $`\mathrm{\Lambda }`$-CDM cosmology, but also baryons forced to shine starlight by galaxy interactions.

We stress that our results are achieved on the basis of a physical – rather than phenomenological – model to derive the burst rate and the amount of cold gas converted into stars during the bursts. Moreover, our model naturally connects with the accretion onto BHs and with the corresponding QSOs emission. Such a unified description is thus able to link the independent observations concerning the luminosity distributions of QSOs and of the galaxies.

For $`z<2`$ the merging and the encounter rates decline, and no longer affect the evolution of the cold gas reservoirs of massive galaxies. So, these galaxies specifically enter a phase of nearly passive evolution, with redder colors which in some cases – whose probability we shall give in detail elsewhere – correspond to those of many observed extremely red objects (EROs see, e.g., Daddi et al. 2002 and references therein). In our model, the beginning and the development of such a phase is naturally matched to the dramatic drop of the QSO luminosities; these are entirely triggered by the gas destabilized in the encounters, and so are particularly sensitive to the current merging and interaction rates of their host galaxies.

We thank the referee for useful comments which helped to improve our presentation.


format: text

text:
# Principal moduli and Class Fields

## 1. Introduction

The Fricke group $`\mathrm{\Gamma }_0(n)^{}`$ of level $`n>1`$ is the subgroup of $`\mathrm{PSL}_2()`$ generated by the congruence subgroup $`\mathrm{\Gamma }_0(n)\mathrm{PSL}_2()`$ and the Fricke involution $`w_n=\sqrt{n}\left(\begin{array}{cc}0& \frac{1}{n}\\ 1& 0\end{array}\right),`$ which acts on the upper half plane $`𝔥`$ by $`w_n(\tau )=\frac{1}{n\tau }`$. As explained in \[2, Section 4\], $`\mathrm{\Gamma }_0(n)^{}`$ is a subgroup of finite index of the full normalizer $`\mathrm{\Gamma }_0(n)^+`$ of $`\mathrm{\Gamma }_0(n)`$ in $`\mathrm{PSL}_2()`$, and equal to it if $`n`$ is prime. The subgroup $`\mathrm{\Gamma }_0(n)`$ has index $`2`$ in $`\mathrm{\Gamma }_0(n)^{}`$, and the elements of the coset $`\mathrm{\Gamma }_0(n)^{}\mathrm{\Gamma }_0(n)`$ are the matrices $`\sqrt{n}\left(\begin{array}{cc}A& \frac{B}{n}\\ C& D\end{array}\right)(\mathrm{mod}\pm 1)`$ with $`A,B,C,D`$ satisfying $`nADBC=1`$. Such a matrix is elliptic of order 2 if and only if it has trace $`0`$, i.e., if it is represented by

(1.1)
$$\alpha =\sqrt{n}\left(\begin{array}{cc}A& \frac{B}{n}\\ C& A\end{array}\right)\mathrm{SL}_2()$$

with $`nA^2+BC=1`$. We always pick $`\alpha `$ in (1.1) in such a way that we have $`B<0`$ and $`C>0`$. Then the fixed point of $`\alpha `$ in $`𝔥`$ is the element

(1.2)
$$\tau _\alpha =\frac{nA+\sqrt{n}}{nC}𝔥,$$

which is a zero of the polynomial

(1.3)
$$f_\alpha =nCX^22nAXB[X]$$

of discriminant $`4n(nA^2+BC)=4n`$. As $`B`$ is coprime to $`nA`$, the polynomial $`f_\alpha `$ is irreducible in $`[X]`$ unless $`B`$ and $`C`$ are both even. In the latter case we have $`n=(1BC)\frac{1}{A^2}3mod4`$, and $`\frac{1}{2}f_\alpha `$ is irreducible in $`[X]`$ of discriminant $`n`$. It follows (cf. \[3, Thm. 7.7 and Prop. 7.4\]) that the complex lattice

(1.4)
$$I_\alpha =[\tau _\alpha ,1]=\frac{1}{nC}[nA+\sqrt{n},nC]$$

corresponding to the fixed point of $`\alpha `$ is an invertible ideal for the quadratic order $`𝒪_\alpha =\{\lambda :\lambda I_\alpha I_\alpha \}`$, which has discriminant $`n`$ if $`B`$ and $`C`$ are both even, and discriminant $`4n`$ otherwise. More explicitly, we have

(1.5)
$$𝒪_\alpha =\{\begin{array}{cc}[\frac{n+\sqrt{n}}{2}]\hfill & \text{for }n3mod4,B\text{and}C\text{even}\hfill \\ [\sqrt{n}]\hfill & \text{otherwise.}\hfill \end{array}$$

The goal of this paper is to study the Galois theoretic properties of the values $`f(\tau _\alpha )`$ over $`(\tau _\alpha )`$ when $`f`$ is a $`\mathrm{\Gamma }_0(n)`$-modular function and $`\alpha `$ is an elliptic element of order 2 in $`\mathrm{\Gamma }_0(n)^{}\mathrm{\Gamma }_0(n)`$. If $`f`$ is modular for the full modular group $`\mathrm{PSL}_2()`$ and has rational $`q`$-expansion, i.e., if $`f`$ is an element of the field $`(j)`$ of modular functions of level 1, then the classical theory of complex multiplication tells us that if $`f(\tau _\alpha )`$ is finite, then it is contained in the ring class field of the order $`𝒪_\alpha `$. This class field is an abelian extension of $`(\tau _\alpha )=(\sqrt{n})`$, and its Galois group over $`(\tau _\alpha )`$ is canonically isomorphic under the Artin isomorphism to the ideal class group $`C(𝒪_\alpha )`$ of the order $`𝒪_\alpha `$. We will write $`\sigma _\alpha `$ for the automorphism corresponding to the ideal class $`[I_\alpha ]C(𝒪_\alpha )`$.

For $`f(j)`$ of level 1 as above, a classical result \[3, Cor. 11.37\] on the Galois theoretic properties of the values of $`j`$ at imaginary quadratic arguments implies that we have $`\sigma _\beta \left(f(\tau _\alpha )\right)=f(\tau _\gamma )`$ when $`\alpha ,\beta `$ and $`\gamma `$ are elliptic elements as in (1.1) satisfying $`𝒪_\alpha =𝒪_\beta =𝒪_\gamma `$ and $`[I_\alpha I_\beta ^1]=[I_\gamma ]C(𝒪_\alpha )`$.

Our main result below shows that $`\mathrm{\Gamma }_0(n)`$-modular functions behave like level 1 functions when evaluated at the elliptic points of order 2 of the Fricke group $`\mathrm{\Gamma }_0(n)^{}`$ that lie outside $`\mathrm{\Gamma }_0(n)`$. The proof given in Section 3 uses the Shimura reciprocity law \[12, Thm. 6.31\] as explained in .

###### Theorem 1.1.

Fix $`n>1`$ and let $`f`$ be a $`\mathrm{\Gamma }_0(n)`$-modular function with rational $`q`$-expansion at $`\mathrm{}`$. Also let $`\alpha `$ be an elliptic element of order $`2`$ in $`\mathrm{\Gamma }_0(n)^{}\mathrm{\Gamma }_0(n)`$ as in (1.1), and assume that $`f`$ is defined at $`\tau _\alpha `$. Then:

1. $`f(\tau _\alpha )`$ lies in the ring class field of $`𝒪_\alpha `$.
2. Let $`\beta ,\gamma `$ be elliptic elements as in (1.1) with $`𝒪_\alpha =𝒪_\beta =𝒪_\gamma `$, and suppose $`[I_\alpha I_\beta ^1]=[I_\gamma ]C(𝒪_\alpha )`$. Then we have

$$\sigma _\beta \left(f(\tau _\alpha )\right)=f(\tau _\gamma ).$$

Our motivation for proving Theorem 1.1 goes back to the special case where $`f`$ is a principal modulus (‘Hauptmodul’) of the kind that arises in the moonshine conjectures for the monster group  and its generalizations to replicable functions . These principal moduli are known to correspond to genus zero subgroups of $`\mathrm{PSL}_2()`$ that lie between $`\mathrm{\Gamma }_0(n)`$ and its normalizer $`\mathrm{\Gamma }_0(n)^+`$ for some $`n`$. In Section 4 we apply Theorem 1.1 to this situation, and explain how our results relate to those of Chen and Yui . The main corollary, which is proved in Section 4, is the following.

###### Corollary 1.2.

Fix $`n>0`$ and let $`f`$ be a principal modulus with rational $`q`$-expansion at $`\mathrm{}`$ for either $`\mathrm{\Gamma }_0(n)`$ or $`\mathrm{\Gamma }_0(n)^{}`$. Suppose that $`f`$ is defined at the fixed point $`\tau _\alpha `$ from (1.2). Then $`(\tau _\alpha ,f(\tau _\alpha ))`$ is the ring class field of the order $`𝒪_\alpha `$.

## 2. Ideals, Quadratic Forms, and Conjugacy Classes

This section collects what we need about the ideals $`I_\alpha `$ arising in (1.4) and their classes in $`C(𝒪_\alpha )`$. While part of this material is well known (see ), we include the details for the convenience of the reader.

In (1.3), we denoted by $`f_\alpha `$ the quadratic polynomial in $`[X]`$ having the fixed point $`\tau _\alpha `$ of the elliptic element $`\alpha `$ as one of its zeroes. Its homogeneous form

(2.1)
$$F_\alpha (x,y)=nCx^22nAxyBy^2[x,y]$$

is a binary quadratic form of discriminant $`4n`$. Since we take $`B<0`$ and $`C>0`$, the form $`F_\alpha `$ is positive definite. Depending on the case we are in in (1.5), either $`F_\alpha `$ or $`\frac{1}{2}F_\alpha `$ is primitive of discriminant $`\mathrm{disc}(𝒪_\alpha )\{n,4n\}`$. Under the standard bijection \[3, Thm. 7.7\] between the set of $`\mathrm{SL}_2()`$-orbits of primitive positive definite binary quadratic forms of discriminant $`\mathrm{disc}(𝒪_\alpha )`$ and the class group $`C(𝒪_\alpha )`$, this primitive form corresponds to the ideal class $`[I_\alpha ]C(𝒪_\alpha )`$.

###### Lemma 2.1.

Let $`\alpha `$ and $`\alpha ^{}`$ be as in (1.1). Then the quadratic forms $`F_\alpha `$ and $`F_\alpha ^{}`$ are $`\mathrm{SL}_2()`$-equivalent if and only if $`\alpha `$ and $`\alpha ^{}`$ are conjugate in $`\mathrm{\Gamma }_0(n)^{}`$. If $`\alpha `$ and $`\alpha ^{}`$ are conjugate in $`\mathrm{\Gamma }_0(n)^{}`$, there exists $`\delta \mathrm{\Gamma }_0(n)`$ with $`\delta ^1\alpha \delta =\alpha ^{}`$.

###### Proof.

Let $`M_\alpha `$ denote the matrix representing the form $`\alpha `$ from (2.1):

$$M_\alpha =\left(\begin{array}{cc}nC& nA\\ nA& B\end{array}\right)=\sqrt{n}\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)\alpha .$$

Since every $`\delta \mathrm{SL}_2()`$ satisfies

$$\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)\delta ^t\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)=\delta ^1,$$

we have

$$\delta ^tM_\alpha \delta =M_\alpha ^{}\delta ^1\alpha \delta =\alpha ^{}.$$

When $`F_\alpha `$ and $`F_\alpha ^{}`$ are equivalent via $`\delta \mathrm{SL}_2()`$, reduction modulo $`n`$ gives

$$\delta ^t\left(\begin{array}{cc}0& 0\\ 0& B\end{array}\right)\delta \left(\begin{array}{cc}0& 0\\ 0& B^{}\end{array}\right)modn.$$

If $`\delta =\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)`$, this easily implies

$$Bc^2Bcd0modn.$$

Since $`\mathrm{gcd}(B,n)=\mathrm{gcd}(c,d)=1`$ (because $`det(\alpha )=det(\delta )=1`$), we see that $`c0modn`$, so that $`\delta \mathrm{\Gamma }_0(n)`$. Then the above equivalence implies that $`\alpha `$ and $`\alpha ^{}`$ represent conjugate elements in $`\mathrm{\Gamma }_0(n)^{}`$.

Conversely, suppose we have $`\alpha ^{}=\pm \delta ^1\alpha \delta `$ (remember that conjugacy classes are computed in $`\mathrm{\Gamma }_0(n)^{}\mathrm{PSL}_2()`$). If $`\delta `$ represents an element of $`\mathrm{\Gamma }_0(n)`$, then the above equivalence shows that $`F_\alpha `$ and $`\pm F_\alpha ^{}`$ are properly equivalent, and the sign must be $`+`$ since $`F_\alpha `$ and $`F_\alpha ^{}`$ are positive definite. The final statement of the lemma says that this is the only case we need to consider. Indeed, if $`\delta `$ represents an element of $`\mathrm{\Gamma }_0(n)^{}\mathrm{\Gamma }_0(n)`$, then $`\alpha ^1\delta `$ represents an element of $`\mathrm{\Gamma }_0(n)`$ since $`\mathrm{\Gamma }_0(n)`$ has index $`2`$ in $`\mathrm{\Gamma }_0(n)^{}`$, and we may replace $`\delta `$ by $`\alpha ^1\delta `$:

$$\alpha ^{}=\pm \delta ^1\alpha \delta =\pm (\alpha ^1\delta )^1\alpha (\alpha ^1\delta ).$$

This completes the proof of the lemma. ∎

It follows from Lemma 2.1 that $`\mathrm{\Gamma }_0(n)`$-modular functions have a well-defined value on the $`\mathrm{\Gamma }_0(n)^{}`$-orbits of the fixed points in (1.2), and that elliptic elements $`\alpha ,\beta `$ in (1.1) with $`𝒪_\alpha =𝒪_\beta `$ are conjugate in $`\mathrm{\Gamma }_0(n)^{}`$ if and only if $`\sigma _\alpha `$ and $`\sigma _\beta `$ coincide on the ring class field of $`𝒪_\alpha `$.

Our main result (Theorem 1.1) gives a Galois action in terms of Artin automorphisms $`\sigma _\alpha `$ corresponding to the ideal classes $`[I_\alpha ]`$. It is therefore useful to know that every ideal class in $`C(𝒪_\alpha )`$ is of this form.

###### Lemma 2.2.

Let $`n`$ be a positive integer and fix $`𝒪`$ to be either $`[\sqrt{n}]`$ or $`[\frac{n+\sqrt{n}}{2}]`$, where in the latter case we assume $`n3mod4`$. Then the ideals $`I_\alpha =\frac{1}{nC}[nA+\sqrt{n},nC]`$ from(1.4) with $`𝒪_\alpha =𝒪`$ represent all ideal classes in the ideal class group $`C(𝒪)`$.

###### Proof.

It suffices to show that a primitive positive definite quadratic form $`G`$ of discriminant $`D=4n`$, or $`D=n`$ with $`n3mod4`$, is properly equivalent to $`F_\alpha `$ or $`\frac{1}{2}F_\alpha `$ respectively. By \[3, Lemmas 2.3 and 2.25\], we may assume that $`G(x,y)=ax^2+bxy+cy^2`$ has $`\mathrm{gcd}(c,D)=1`$.

First suppose that $`D=4n`$. Since $`b`$ is even in this case, we can find an integer $`k`$ such that

$$ckb/2modn.$$

Using this $`k`$ to replace $`G(x,y)`$ with the equivalent form

(2.2)
$$G(x,y+kx)=(a+bk+ck^2)x^2+(b+2kc)xy+cy^2,$$

we may assume that $`b`$ is divisible by $`2n`$. Then $`4n=b^24ac`$ and $`\mathrm{gcd}(c,4n)=1`$ imply that $`a`$ is divisible by $`n`$. It follows that $`G`$ is of the form $`F_\alpha `$, as desired.

Next assume $`D=n`$ and $`n3mod4`$. Then we can find $`k`$ such that

$$2ckbmodn.$$

Using this $`k`$ and (2.2), we may assume that $`b`$ is divisible by $`n`$. Since $`n`$ is odd, $`n=b^24ac`$ and $`\mathrm{gcd}(c,n)=1`$ imply that $`a`$ is divisible by $`n`$. Then $`G=\frac{1}{2}F_\alpha `$ follows easily. ∎

For $`𝒪=[\sqrt{n}]`$, the form $`F_\alpha =nx^2+y^2`$ corresponding to the principal ideal generated by $`\tau =\frac{1}{\sqrt{n}}`$ is in the unit class in $`C(𝒪)`$. For $`𝒪=[\frac{n+\sqrt{n}}{2}]`$, we can start from $`G(x,y)=\frac{n+1}{4}x^2+xy+y^2`$ in the unit class and apply the proof of (2.2) (with $`k=\frac{n1}{2}`$) to obtain the element $`F_\alpha (x,y)=\frac{n(n+1)}{4}x^2+nxy+y^2`$ in the unit class. It corresponds to the principal ideal generated by $`\tau =\frac{2n+2\sqrt{n}}{n(n+1)}`$. Note that in both cases, $`\tau 𝒪`$ is the lattice $`[\tau ,1]`$.

## 3. Proof of the Main Theorem

We now prove Theorem 1.1 using the method explained in .

Let $`f`$ be a modular function for $`\mathrm{\Gamma }_0(n)`$ with rational $`q`$-expansion and assume that $`f`$ is defined at the fixed point $`\tau _\alpha `$ from (1.2). Our first task is to show that $`f(\tau _\alpha )`$ lies in the ring class field of $`𝒪_\alpha `$. We first do this when the corresponding ideal $`I_\alpha `$ is in the unit class in $`C(𝒪_\alpha )`$. This leads to the following special choice for $`\tau =\tau _\alpha `$ and in each of the two cases for $`𝒪=𝒪_\alpha `$ provided by (1.5).

|  | $`n`$ | $`\alpha `$ | $`\tau `$ | $`𝒪`$ |
| --- | --- | --- | --- | --- |
| Case 1 | arbitrary | $`\sqrt{n}\left(\begin{array}{cc}0& \frac{1}{n}\\ 1& 0\end{array}\right)`$ | $`\frac{1}{\sqrt{n}}`$ | $`[n\tau ]`$ |
| Case 2 | $`n3mod4`$ | $`\sqrt{n}\left(\begin{array}{cc}1& \frac{2}{n}\\ \frac{n+1}{2}& 1\end{array}\right)`$ | $`\frac{2n+2\sqrt{n}}{n(n+1)}`$ | $`[\frac{n(n+1)}{4}\tau ]`$ |

Standard results in complex multiplication imply that $`f(\tau )`$ lies in the maximal Abelian extension $`K^{\mathrm{ab}}`$ of $`K=(\tau )=(\sqrt{n})`$. Class field theory describes the absolute abelian Galois group $`\mathrm{Gal}(K^{\mathrm{ab}}/K)`$ as the surjective image under the Artin map of the group $`\widehat{K}^{}=(K_{}\widehat{})^{}`$ of finite $`K`$-ideles. (We generally write $`\widehat{A}`$ to denote the tensor product over $``$ of a ring $`A`$ with the profinite completion $`\widehat{}=_p\widehat{}_p`$ of $``$.) In order to show that $`f(\tau )`$ lies in the ring class field $`H_𝒪`$ of $`𝒪`$, it suffices to show that every automorphism of $`K^{\mathrm{ab}}`$ over $`H_𝒪`$ leaves $`f(\tau )`$ invariant. As $`\mathrm{Gal}(K^{\mathrm{ab}}/H_𝒪)`$ is the image under the Artin map of the subgroup $`\widehat{𝒪}^{}=(𝒪_{}\widehat{})^{}\widehat{K}^{}`$, we need to show that the Artin symbol of any idele $`x\widehat{𝒪}^{}`$ leaves $`f(\tau )`$ invariant.

Shimura’s reciprocity law tells us how (the Artin symbol of) the idele $`x\widehat{𝒪}^{}`$ acts on $`f(\tau )`$: we have

(3.1)
$$f(\tau )^x=f^{g_\tau (x^1)}(\tau ),$$

where $`g_\tau :\widehat{𝒪}^{}\mathrm{GL}_2(\widehat{})`$ is the map that sends $`x\widehat{𝒪}^{}`$ to the transpose of the matrix of multiplication by $`x`$ on the free $`\widehat{}`$-module $`\widehat{}\tau +\widehat{}`$ with respect to the basis $`\{\tau ,1\}`$. One often writes $`g_\tau (x)\left(\genfrac{}{}{0.0pt}{}{\tau }{1}\right)=\left(\genfrac{}{}{0.0pt}{}{x\tau }{x}\right)`$. Note that $`\mathrm{GL}_2(\widehat{})`$ acts in a natural way on the field of modular functions over $``$ (see \[8, §2 of Ch. 7\]). For modular functions of level $`N`$, the action factors via the quotient $`GL_2(/N)`$ (see \[8, §3 of Ch. 6\]).

From the irreducible polynomial of $`\tau `$ in $`[X]`$ one easily computes $`g_\tau `$ as in \[13, (3.3)\] to be

(3.2)
$$g_\tau (x)=g_\tau (a+bn\tau )=\left(\begin{array}{cc}a& b\\ nb& a\end{array}\right)$$

for the order $`𝒪=[n\tau ]`$ in Case 1, and

(3.3)
$$g_\tau \left(a+b\frac{n(n+1)}{4}\tau \right)=\left(\begin{array}{cc}anb& b\\ \frac{n(n+1)}{4}b& a\end{array}\right)$$

for the order $`𝒪=[\frac{n(n+1)}{4}\tau ]`$ in Case 2. In both cases, the matrix $`g_\tau (x)`$ is upper triangular modulo $`n`$ for every choice of $`x\widehat{𝒪}^{}`$. This means that modulo $`n`$, it is a product

$$M_1M_2=\left(\begin{array}{cc}1& 0\\ 0& d\end{array}\right)M_2\mathrm{GL}_2(/n),$$

where $`M_2`$ is the reduction modulo $`n`$ of a matrix from $`\mathrm{\Gamma }_0(n)`$. But $`M_2`$ acts trivially on $`f`$ since $`f`$ is a modular function for $`\mathrm{\Gamma }_0(n)`$, and $`M_1`$, which acts on $`f`$ via its Fourier coefficients, also acts trivially since the $`q`$-expansion is rational. It follows that $`f`$ is invariant under $`\widehat{𝒪}^{}`$, so that $`f(\tau )`$ lies in the desired ring class field $`H_𝒪`$. In particular, the class group $`C(𝒪)`$, which is naturally isomorphic to the Galois group $`\mathrm{Gal}(H_𝒪/K)`$ under the Artin map, now acts on $`f(\tau )`$.

Our next task is to show that for elliptic elements $`\beta `$ and $`\gamma `$ satisfying $`𝒪_\beta =𝒪_\gamma =𝒪`$ and $`[I_\beta ^1]=[I_\gamma ]C(𝒪)`$, the Galois action of $`\sigma _\beta `$ on $`f(\tau )`$ is in each of the two cases given by

(3.4)
$$\sigma _\beta (f(\tau ))=f(\tau _\gamma ).$$

This shows that we have $`\sigma _\gamma (f(\tau _\gamma ))=f(\tau )`$ for all $`f(\tau _\gamma )`$ with $`\gamma `$ as in (1.1) having $`𝒪_\gamma =𝒪`$. In particular, all these values $`f(\tau _\gamma )`$ are conjugate over $`K`$ as soon as one of them is known to be finite, and one easily derives the second statement in (1.1) from (3.4). We may therefore finish the proof of (1.1) by proving (3.4).

To prove (3.4), we apply (3.1) once more, with $`x\widehat{K}^{}`$ an $`\widehat{𝒪}`$-generator of $`\widehat{I_\gamma }=I_\gamma _{}\widehat{}`$ and $`g_\tau :\widehat{K}^{}\mathrm{GL}_2(\widehat{})`$ the natural $``$-linear extension of the map $`g_\tau :\widehat{𝒪}^{}\mathrm{GL}_2(\widehat{})`$ we had before. As in \[13, Section 6\], we let $`M\mathrm{GL}_2^+()`$ be the transpose of a matrix mapping the lattice $`[\tau ,1]=\tau 𝒪`$ to the lattice $`\tau I_\gamma `$. Write $`I_\gamma =\frac{1}{nC}[nA+\sqrt{n},nC]`$ as in (1.4). In Case 1 we have $`\tau \sqrt{n}=1`$, so

$$\tau I_\gamma =\tau [\frac{nA+\sqrt{n}}{nC},1]=[\frac{nA\tau 1}{nC},\tau ],$$

and we can take $`M\mathrm{GL}_2^+()`$ to be

$$M=\left(\begin{array}{cc}A/C& 1/nC\\ 1& 0\end{array}\right)=\left(\begin{array}{cc}1/C& A/C\\ 0& 1\end{array}\right)\left(\begin{array}{cc}0& 1/n\\ 1& 0\end{array}\right).$$

In Case 2 our element $`\tau `$ satisfies $`\tau (n+\sqrt{n})=2`$, so we have

$$\tau I_\gamma =\tau [\frac{nA+\sqrt{n}}{nC},1]=[\frac{n(A1)\tau 2}{nC},\tau ]$$

and we can take the matrix $`M\mathrm{GL}_2^+()`$ to be

$$M=\left(\begin{array}{cc}(A1)/C& 2/nC\\ 1& 0\end{array}\right)=\left(\begin{array}{cc}2/C& (A1)/C\\ 0& 1\end{array}\right)\left(\begin{array}{cc}0& 1/n\\ 1& 0\end{array}\right).$$

By construction, we have $`M(\tau )=\tau _\gamma `$ in both cases. Note that at this point we use the fact that the lattice $`[\tau ,1]`$ is a principal $`𝒪`$-ideal. Further $`M`$ and $`g_\tau (x)`$ are transposes of matrices mapping the $`\widehat{}`$-module $`\widehat{}\tau +\widehat{}\widehat{K}`$ onto $`\widehat{I_\gamma }`$, so the matrix $`g_\tau (x)M^1`$ is in $`\mathrm{GL}_2(\widehat{})`$ as its transpose fixes $`\widehat{}\tau +\widehat{}`$. We can now compute

(3.5)
$$\sigma _\beta (f(\tau ))=f^{g_\tau (x)}(\tau )=f^{g_\tau (x)M^1}(M(\tau ))=f^{g_\tau (x)M^1}(\tau _\gamma )$$

by evaluating $`g_\tau (x)M^1\mathrm{GL}_2(\widehat{})`$ modulo the level $`n`$ of $`f`$. All we need to know for this are the $`p`$-components $`x_p`$ of a generator $`x\widehat{K}^{}`$ of $`\widehat{I_\gamma }`$ for the primes $`p`$ dividing $`n`$. Finding a generator $`x_p`$ of the $`(𝒪_{}_p)`$-ideal $`I_\gamma _{}_p`$ is easy at primes $`p|n`$, since for these $`p`$ the identity $`BC=1nA^2`$ implies that $`C`$ is a unit in $`_p`$. This yields

(3.6) $`I_\gamma _{}_p`$ $`=\frac{nA+\sqrt{n}}{nC}_p+_p=(A\frac{1}{\sqrt{n}})_p+_p`$
$`=\frac{1}{\sqrt{n}}_p+_p=\frac{1}{\sqrt{n}}_p[\sqrt{n}].`$
In Case 1 we have $`𝒪_{}_p=_p[\sqrt{n}]`$ and we can choose $`x_p=\frac{1}{\sqrt{n}}=\tau `$ for all $`p|n`$. Applying (3.2) then yields

$$g_\tau (x_p)=\left(\begin{array}{cc}0& 1/n\\ 1& 0\end{array}\right)\mathrm{GL}_2(_p)$$

at all $`p|n`$, so $`g_\tau (x)M^1`$ has upper triangular reduction

$$\left(\begin{array}{cc}1/C& A/C\\ 0& 1\end{array}\right)^1=\left(\begin{array}{cc}C& A\\ 0& 1\end{array}\right)$$

modulo $`n`$. It therefore leaves $`f`$ invariant, and (3.5) reduces to (3.4).

In Case 2 only odd primes can divide $`n`$, so again we have $`𝒪_{}_p=_p[\sqrt{n}]`$ for $`p`$ dividing $`n`$, and we may take $`x_p=\frac{n+1}{4}\tau =\frac{1+\sqrt{n}}{2}\frac{1}{\sqrt{n}}`$ since $`\frac{1+\sqrt{n}}{2}`$ is a $`p`$-adic unit if $`p`$ divides $`n`$. Applying (3.3) now yields

$$g_\tau (x_p)=\left(\begin{array}{cc}1& 1/n\\ \frac{n+1}{4}& 0\end{array}\right)=\left(\begin{array}{cc}1& 1\\ 0& \frac{n+1}{4}\end{array}\right)\left(\begin{array}{cc}0& 1/n\\ 1& 0\end{array}\right)\mathrm{GL}_2(_p)$$

at all $`p|n`$, so $`g_\tau (x)M^1`$ has upper triangular reduction

$$\left(\begin{array}{cc}1& 1\\ 0& \frac{n+1}{4}\end{array}\right)\left(\begin{array}{cc}2/C& (A1)/C\\ 0& 1\end{array}\right)^1$$

modulo $`n`$. As in Case 1, we find that $`g_\tau (x)M^1`$ leaves $`f`$ invariant. This finishes the proof of Theorem (1.1).

By Lemma 2.2, Theorem 1.1 furnishes a complete description of the Galois theoretic properties of $`f(\tau _\alpha )`$ over $`(\tau _\alpha )`$. This will be particularly useful in the cases in the next section, where we know exactly which elements in $`\mathrm{PSL}_2()`$ fix $`f`$.

## 4. Principal moduli

A modular function $`f`$ for a discrete group $`G\mathrm{PSL}_2()`$ commensurable with $`\mathrm{PSL}_2()`$ is a *principal modulus* (in German: *Hauptmodul*) if it generates the field of all modular functions for $`G`$. This implies $`G\backslash 𝔥^{}^1`$ via $`f`$. In particular, $`G`$ has genus $`0`$.

Corollary 1.2, which we will prove now, states that if the modular function $`f`$ in Theorem 1.1 is a principal modulus for $`\mathrm{\Gamma }_0(n)`$ or $`\mathrm{\Gamma }_0(n)^{}`$, then we get a primitive element of the ring class field.

###### Proof of Corollary 1.2.

The case $`n=1`$ is obvious, so we may assume $`n>1`$. Lemma 2.2 shows that the ideals $`I_\alpha `$ represent all ideal classes in $`C(𝒪_\alpha )`$. Then Lemma 2.1 and the correspondence between ideals and quadratic forms imply that we get $`|C(𝒪_\alpha )|`$ different $`\mathrm{\Gamma }_0(n)^{}`$-inequivalent points of the form $`\tau _\alpha `$. If $`f`$ is a principal modulus for $`\mathrm{\Gamma }_0(n)^{}`$, it follows that the complex numbers $`f(\tau _\alpha )`$ have $`|C(𝒪_\alpha )|`$ distinct values as we vary $`\alpha `$, and the same is true if $`f`$ is a principal modulus for $`\mathrm{\Gamma }_0(n)`$ since $`\mathrm{\Gamma }_0(n)^{}`$-inequivalent points are automatically $`\mathrm{\Gamma }_0(n)`$-inequivalent. Thus the minimal polynomial of $`f(\tau _\alpha )`$ over $`(\tau _\alpha )`$ has degree $`|C(𝒪_\alpha )|`$ by Theorem 1.1. The theorem follows since this is the degree of the ring class field over $`(\tau _\alpha )`$. ∎

It is well known that $`\mathrm{\Gamma }_0(n)`$ has genus $`0`$ for the $`15`$ numbers

(4.1)
$$n=1\text{}10,12,13,16,18,25.$$

Turning to $`\mathrm{\Gamma }_0(n)^{}`$, Ogg  showed that $`\mathrm{\Gamma }_0(n)^{}`$ has genus $`0`$ for the following $`37`$ values of $`n>1`$ (we exclude $`n=1`$ since $`\mathrm{\Gamma }_0(1)^{}=\mathrm{\Gamma }_0(1)`$):

(4.2)
$$n=2\text{}21,23\text{}27,29,31,32,35,36,39,41,47,49,50,59,71.$$

However, in order to use Corollary 1.2 for either $`\mathrm{\Gamma }_0(n)`$ or $`\mathrm{\Gamma }_0(n)^{}`$, we also need to know that the group has a principal modulus with a rational $`q`$-expansion. As we are dealing with a finite list of groups, one can simply check the tables in , which give explicit formulas for principal moduli in all cases when $`\mathrm{\Gamma }_0(n)`$ or $`\mathrm{\Gamma }_0(n)^{}`$ has genus $`0`$. These all have rational $`q`$-expansions. Alternatively, as S. Norton pointed out to us, Theorem 1 of  easily implies the existence of a principal modulus with rational $`q`$-expansion whenever $`\mathrm{\Gamma }_0(n)`$ or $`\mathrm{\Gamma }_0(n)^{}`$ has genus $`0`$. It follows that Corollary 1.2 applies to all values of $`n`$ in (4.1) for $`\mathrm{\Gamma }_0(n)`$ and (4.2) for $`\mathrm{\Gamma }_0(n)^{}`$.

The primitive elements for the ring class fields obtained from principal moduli are often much smaller than those provided by the $`j`$-function. For example, take $`f`$ to be the function listed as 71A in \[2, p. 337\], which is a principal modulus for the Fricke group $`\mathrm{\Gamma }_0(71)^{}`$. There are 14 elliptic fixed points of order 2 for $`\mathrm{\Gamma }_0(71)^{}`$, of which seven are of discriminant $`71`$ and seven are of discriminant $`471=284`$. This is in accordance with the fact that the two quadratic orders having these discriminants have class number 7. In both cases the corresponding ring class field is the Hilbert class field $`H`$ of $`(\sqrt{71})`$.

When $`n=71`$, the two special elliptic points of order 2 used in the proof of Theorem 1.1 are

$$\tau _{284}=\frac{1}{\sqrt{71}}\text{and}\tau _{71}=\frac{71+\sqrt{71}}{7136}.$$

corresponding to the orders of discriminant $`284`$ and $`71`$ respectively. One can compute that the minimal polynomial of $`f(\tau _{284})`$ is

$$h_{284}=x^77x^511x^4+5x^3+18x^2+4x11,$$

while the minimal polynomial of $`f(\tau _{71})`$ is

$$h_{71}=x^7+4x^6+5x^5+x^43x^32x^2+1.$$

Each of these polynomials is a small generating polynomial for $`H`$ over $`(\sqrt{71})`$ and compares favorably with the polynomial

$$w_{71}=x^72x^6x^5+x^4+x^3+x^2x1$$

found by Weber \[14, Vol. III, p. 723\] (this is the minimal polynomial of $`𝔣(\sqrt{71})/\sqrt{2}`$, where $`𝔣`$ is the Weber function defined on page 114 of \[14, Vol. III\]). If $`\beta `$ is a root of $`w_{71}`$, then an easy calculation shows that

$`\beta ^21\beta ^1`$ $`\text{is a root of}h_{284}`$
$`\beta ^6+3\beta ^52\beta ^4+1`$ $`\text{is a root of}h_{71}.`$
Note that the values $`f(\tau _{71})`$ and $`f(\tau _{284})`$ are in this case *integral*, a general phenomenon for which we currently do not have a proof. For the importance of $`h_{284}`$ and $`h_{71}`$ for the Schwarzian differential equation satisfied by $`f`$, see .

As we mentioned in the introduction, the moonshine conjectures for the monster group provide us with principal moduli for genus zero subgroups of $`\mathrm{PSL}_2()`$ in the form of so-called McKay-Thompson series. Their singular values have been studied by Chen and Yui in . They restrict to fundamental McKay-Thompson series, i.e., the series $`T_g`$ associated to a conjugacy class $`g`$ of the monster group that is the principal modulus for a subgroup of $`\mathrm{PSL}_2()`$ whose level $`n`$ equals the order of $`g`$. If $`T_g`$ is fundamental, $`\tau 𝔥`$ is a CM-point and $`𝒪=[a\tau ]`$ is the multiplier ring of $`[\tau ,1]`$, they prove the following in \[1, Theorem 3.7.5\]:

1. If $`T_g`$ is a principal modulus for $`\mathrm{\Gamma }_0(n)`$, then $`(\tau ,T_g(\tau ))`$ is the ring class field of the order of index $`\frac{n}{\mathrm{gcd}(a,n)}`$ in $`𝒪`$.
2. If $`T_g`$ is a principal modulus for $`\mathrm{\Gamma }_0(n)^{}`$ with $`n`$ prime and coprime to $`a`$, then $`(\tau ,T_g(\tau ))`$ is the ring class field of the order of index $`n`$ in $`𝒪`$.

Applying the first part of this theorem to $`T_g(\tau _\alpha )`$, one can prove Corollary 1.2 when $`T_g`$ is a principal modulus for $`\mathrm{\Gamma }_0(n)`$. So for $`T_g(\tau _\alpha )`$, the Chen-Yui result covers all numbers in (4.1). On the other hand, if $`T_g`$ is a principal modulus for $`\mathrm{\Gamma }_0(n)^{}`$, then the hypothesis $`\mathrm{gcd}(a,n)=1`$ means that the second part of Theorem 3.7.5 doesn’t apply to $`T_g(\tau _\alpha )`$. So for $`T_g(\tau _\alpha )`$, the Chen-Yui result covers none of the numbers in (4.2). The integrality results in  for the numbers $`T_g(\tau )`$, although interesting in their own right, do not apply to the fixed points $`\tau =\tau _\alpha `$ in this paper. Numerical computations do however suggest that $`T_g(\tau _\alpha )`$ is an algebraic integer, so this question deserves further study.

## Acknowledgements

The research of the second author is partially supported by NSERC. The first author is grateful to Heng Huat Chan for bringing  to his attention, and the second author would like to thank Simon Norton for suggesting the relevance of .


text:
# 1 Introduction

## 1 Introduction

Entangled quantum states are interesting both from theoretical and practical points of view. Theoretically, entanglement is connected with the confounding issue of nonlocality. Practically, entangled states are useful in quantum cryptography and other quantum information processing tasks (for example, see  and references therein). The problem of determining whether a state is entangled or separable is thus important and comes in two flavors – one mathematical, and the other experimental.

The mathematical problem of separability (for bipartite systems) is defined as follows. Let $`_{M,N}`$ denote the set of all Hermitian operators mapping $`^M^N`$ to $`^M^N`$. The set of bipartite separable quantum states $`S_{M,N}`$ in $`_{M,N}`$ is defined as the convex hull of the separable pure states $`\{|\alpha \alpha ||\beta \beta |_{M,N}\}`$, where $`|\alpha `$ is a norm-1 vector in $`^M`$ and $`|\beta `$ is a norm-1 vector in $`^N`$. The set of separable states $`S_{M,N}`$ may be viewed as a compact, convex subset of $`^{M^2N^2}`$ by expressing each density operator as a real linear combination of the canonical Hermitian generators of $`SU(M)`$ and $`SU(N)`$ . The quantum separability problem is now easily defined as an instance of the Weak Membership problem : Given a convex set $`K^n`$, a point $`p^n`$, and an accuracy parameter $`\delta >0`$, assert either that (i) $`pS(K,\delta )`$ (i.e. $`p`$ is “almost in” $`K`$) or that (ii) $`pS(K,\delta )`$ (i.e. $`p`$ is “not $`\delta `$-deep within” $`K`$), where $`S(K,\delta )`$ denotes the union of all $`\delta `$-balls with centers belonging to $`K`$, and $`S(K,\delta )`$ denotes the union of all centers of all $`\delta `$-balls contained in $`K`$ (in the standard Euclidean norm). The separability problem has been shown to be NP-hard , thus any devised test for separability is likely to require a number of computing resources that scales exponentially with $`M`$ and $`N`$. There exist efficient “one-sided” tests for separability, where the output of some polynomial-time computable function of the matrix for $`\rho `$ can indicate that $`\rho `$ is certainly entangled  or certainly separable , but not both. The algorithm in  is in principle a one-sided test because it requires an infinite amount of computational resources to detect some entangled states.

The experimental flavor of the separability problem can be defined as follows: Given many physical copies of a completely unknown quantum state $`\rho _{M,N}`$, determine whether $`\rho `$ is separable. One way to solve this problem is to perform a full state tomography in order to construct the density matrix for $`\rho `$ to some precision $`\delta >0`$, and then solve the mathematical separability problem. If rather there is some partial knowledge of $`\rho `$, then there are certainly more options, such as testing for a violation of a specific Bell-type inequality  or invoking entanglement witnesses . As well, in the case where $`MN6`$, the positive partial transpose (PPT) test  can be implemented physically , though currently this approach is not experimentally viable.

In section 2 we describe a method to tackle the mathematical separability problem in general. The idea is to invoke the following characterization  of entangled states: A state $`\rho `$ is entangled if and only if there exists an entanglement witness  that detects it. The method is basically a search for an entanglement witness that detects the given state. In section 3 we describe how to use this method as a novel tool for solving the experimental separability problem. We conclude with a brief discussion, and point to some future directions of research in section 4.

## 2 Solving Quantum Separability

In this note we use the following definition of “entanglement witness”, which differs slightly from the definition used in the literature.

###### Definition 1.

An *entanglement witness* is any operator $`A_{M,N}`$ for which there exists a state $`\rho _{M,N}`$ such that

$$tr(A\sigma )<tr(A\rho )\sigma S_{M,N}.$$

Recalling that $`_{M,N}`$ is isomorphic to $`^{M^2N^2},`$ the above definition implies that for entangled $`\rho `$ there exists a hyperplane in $`^{M^2N^2}`$ which separates $`\rho `$ from the set of all separable states $`S_{M,N}`$. If we define the function

$`b_A:=\underset{\sigma S_{M,N}}{\mathrm{max}}tr(A\sigma ),`$ (1)
then the set $`\{x_{M,N}:tr(Ax)=b_A\}`$ is one such hyperplane. The function $`b_A`$ is implicitly at the heart of the definition of “entanglement witness” as it pins down which, if any, of the hyperplanes, with normal A, separate the state $`\rho `$ from $`S_{M,N}`$. The hyperplane defined by $`A`$ and $`b_A`$ is tangent to $`S_{M,N}`$ and is thus the optimal hyperplane with normal vector $`A`$ that separates $`\rho `$ from $`S_{M,N}`$.

The function $`b_A`$ leads naturally to an algorithm for quantum separability as follows. For $`A`$ such that $`tr(A^2)=1`$, define the function $`d_{A,\rho }`$ as

$`d_{A,\rho }:=b_Atr(A\rho ).`$ (2)
Geometrically, $`d_{A,\rho }`$ is the signed distance from the state $`\rho `$ to the hyperplane defined by $`b_A`$. By using equations 1 and 2, and the definition of “entanglement witness”, it follows that $`\rho `$ is entangled if and only if

$`A:d_{A,\rho }<0.`$ (3)
Thus we have reduced quantum separability to the task of finding an $`A`$ such that $`d_{A,\rho }`$ is negative. By observing that the ability to calculate $`b_A`$ gives an oracle for the Weak Optimization problem, Theorem 4.4.7 from  shows that it is possible to solve quantum separability with only polynomially many evaluations of the function $`b_A`$. Thus, the “hardness” of quantum separability is contained in the “hardness” of evaluating $`b_A`$. In practice, and for low-dimensional applications, well-known sophisticated techniques (such as simulated annealing or interval analysis) for finding global extrema would likely be sufficient to calculate $`b_A`$. Unfortunately the algorithm derived in  is not implementable on fixed precision computers, and it uses many more evaluations of $`b_A`$ than is strictly necessary. In a later paper, we hope to demonstrate a better algorithm which uses far fewer evaluations of $`b_A`$ and thus, hopefully, is of practical use for low-dimensional problems.

## 3 Solving Separability with Partial Information

In this section, we briefly show how the above approach may be used when only partial information about the state $`\rho _{M,N}`$ is available. This is of particular use in an experimental setting.

The state $`\rho `$ can be written

$`\rho ={\displaystyle \underset{i=0}{\overset{M^21}{}}}{\displaystyle \underset{j=0}{\overset{N^21}{}}}\rho _{ij}\lambda _i^M\lambda _j^N,`$ (4)
where $`\rho _{ij}`$ and the $`\lambda _i^M`$ and $`\lambda _j^N`$ (as defined in ) respectively generate the special unitary groups $`SU(M)`$ and $`SU(N)`$. In this case, the coefficients $`\rho _{ij}`$ are simply related to the expected values of $`\lambda _i^M\lambda _j^N`$:

$`\rho _{ij}=\lambda _i^M\lambda _j^N/4:=tr(\lambda _i^M\lambda _j^N\rho )/4.`$ (5)
Let $`\mathrm{\Lambda }:=\{\lambda _i^M\lambda _j^N\}_{i=0,1,\mathrm{},M^21;j=0,1,\mathrm{},N^21}`$. The expected values of all elements of $`\mathrm{\Lambda }`$ constitute complete information about $`\rho `$. Suppose only partial information about $`\rho `$ has been obtained by an experimental procedure, that is, only the expected values of the elements of a proper subset $`T`$ of $`\mathrm{\Lambda }`$ are known.

It helps to think of each density operator as a real vector of its expected values. With only $`|T|`$ expected values known, we now effectively project all the density operators onto $`\text{span}(T)`$ by ignoring the components of the real vectors that correspond to the unknown expected values of $`\rho `$. Now each density operator, including our unknown $`\rho `$, is represented by a point in a $`|T|`$-dimensional “expectation space”. Note that the set of points in this projective space representing all separable density operators is still a convex set. Call this convex set $`\overline{S}_T`$ and denote its elements by $`\overline{\sigma }^{|T|}`$. Similarly, let $`\overline{\rho }`$ be the $`|T|`$-dimensional real vector of known expected values of $`\rho `$. To represent the Hermitian operator $`A=_{XT}a_XX`$ in this space, we can use the real vector $`\overline{A}`$ of the coefficients $`a_X`$ in order to have the correspondence $`tr(A\rho )=\overline{A}\overline{\rho }`$, where “$``$” denotes the standard dot-product of two real vectors.

It is clear that the functions $`b_A`$ and $`d_{A,\rho }`$ in the previous section can be redefined for the $`|T|`$-dimensional space:

$`\overline{b}_{\overline{A}}:=\underset{\overline{\sigma }\overline{S}_T}{\mathrm{max}}\overline{A}\overline{\sigma }`$ (6)
and

$`\overline{d}_{\overline{A},\overline{\rho }}:=\overline{b}_{\overline{A}}\overline{A}\overline{\rho }.`$ (7)
If there exists $`\overline{A}`$ such that $`\overline{d}_{\overline{A},\overline{\rho }}<0`$, then $`\rho `$ is entangled; otherwise, more information is needed to determine the separability of $`\rho `$. As expected values are being gathered through experimental observation, they may be input to a computer program that searches for $`\overline{d}_{\overline{A},\overline{\rho }}<0`$. Finally, we point out that the idea of searching for an entanglement witness in the span of operators whose expected values are known was discovered independently and applied, in a special case, to quantum cryptographic protocols in .

## 4 Discussion

By looking at quantum separability as a mathematical problem in the real Euclidean space $`^{M^2N^2}`$ and slightly altering the definition of entanglement witness, we have show that quantum separability can be solved in oracle-polynomial time, for a rather natural looking oracle. This allows us to highlight the fact that the “hard” part of quantum separability is contained in the function $`b_A`$. The method we describe for solving quantum separability also gives experimentalists a tool for potentially determining if an unknown state is entangled by measuring only a subset of the expected values which completely describe the state. This method effectively trades quantum resources (additional copies of $`\rho `$) for classical resources (a computer able to calculate $`\overline{b}_{\overline{A}}`$). As well as providing a practical, implementable algorithm for low-dimensional quantum separability, some open questions which we hope to address in the future include getting a tight (exponential) bound on the complexity of calculating $`b_A`$, and determining the average number of expected values required to detect a random unknown quantum state.

## 5 Acknowledgements

We would like to thank Carolina Moura Alves, Coralia Cartis, Donny Cheung, Artur Ekert, and Tom Stace for useful discussions. We acknowledge support from the EU under project RESQ (IST-2001-37559). LMI also acknowledges support from CESG (UK) and NSERC (Canada). BCT also acknowledges support from CMI.