text:
# A Hybrid Cosmological Hydrodynamic/N-body Code Based on the Weighted Essentially Non-Oscillatory Scheme

## 1 Introduction

Due to the highly non-linearity of gravitational clustering in the universe, one significant feature emerging in cosmological hydrodynamic flow is extremely supersonic motion around the density peaks developed by gravitational instability, which leads to strong shock discontinuities within complex smooth structures. It poses more challenge than the typical hydrodynamic simulation without self-gravity. To address this issue, two algorithms have been implemented for high resolution shock capturing in cosmology: total-variation diminishing (TVD) scheme and piecewise parabolic method (PPM).

An alternative hydrodynamic solver to discretize the convection terms in the Euler equations is the fifth order finite difference WENO (weighted essentially non-oscillatory) method, with a low storage nonlinearly stable third order Runge-Kutta time discretization. The WENO schemes, first constructed in third order finite volume version by Liu et al., are based on the essentially non-oscillatory scheme (ENO) developed by Harten et al. in the form of finite volume scheme for hyperbolic conservative laws. The ENO scheme generalizes the total variation diminishing (TVD) scheme of Harten. The TVD schemes typically degenerate to first-order accuracy at locations with smooth extrema while the ENO and WENO schemes maintain high order accuracy there even in multi-dimensions. The WENO method is very robust and stable for solutions containing strong shocks and complex solution structures,. It uses the idea of adaptive stencils in the reconstruction procedure based on the local smoothness of the numerical solution to automatically achieve high order accuracy and non-oscillatory property near discontinuities. This is achieved by using a convex combination of a few candidate stencils, each being assigned a nonlinear weight which depends on the local smoothness of the numerical solution based on that stencil. WENO schemes can simultaneously provide a high order resolution for the smooth part of the solution, and a sharp, monotone shock or contact discontinuity transition.

In the context of cosmological applications, we have developed a hybrid N-body/hydrodynamical code that incorporates a Lagrangian particle-mesh algorithm to evolve the collision-less matter with the fifth order WENO scheme to solve the equation of gas dynamics. This paper describes this code briefly.

## 2 Numerical Techniques

### 2.1 The Basic Equations

The hydrodynamic equations for baryons in the expanding universe, without any viscous and thermal conductivity terms, can be written as,

$$\dot{U}+_i𝐅^i[U]=f(t,U)$$
(1)
where the abbreviation $`_i/x^i`$ has been used, $`x^i`$ denote the proper coordinates. $`U`$ is a five-component column vector, $`U=(\rho ,\rho v_1,\rho v_2,\rho v_3,E)`$, $`\rho `$ is the comoving density, $`𝐯=\{v_i\}`$ is the proper peculiar velocity, E is the total energy per unit comoving volume including both kinetic and internal energy, P is comoving pressure, related to the total energy E by $`E=P/(\gamma 1)+\frac{1}{2}\rho 𝐯^2`$ where we assume an ideal gas equation of state, $`P=(\gamma 1)e`$, where $`e`$ is the internal energy density and $`\gamma `$ is the ratio of the specific heats of the baryon. The left hand side of Eq.(1) is written in the conservative form for mass, momentum and energy, the ”force” source term on right hand side includes the contributions from the expansion of the universe, the gravitation. $`\mathrm{\Lambda }_{net}`$ in the energy equation represents the net energy loss due to the radiative heating-cooling of the baryonic gas.

$$f(t,U)=(0,\frac{\dot{a}}{a}\rho 𝐯+\rho 𝐠,2\frac{\dot{a}}{a}E+\rho 𝐯𝐠\mathrm{\Lambda }_{cool})$$
(2)
where $`𝐠`$ is the peculiar acceleration in the gravitational field produced by both the dark matter and the baryonic matter, which is obtained by solving the Poisson equation using standard particle-mesh technique.

### 2.2 Hydrodynamic Solver: Finite Difference WENO Schemes

The fifth order WENO finite difference spatial discretization to a conservation law such as

$$u_t+f(u)_x+g(u)_y=0$$
(3)
approximates the derivatives, for example $`f(u)_x`$, by a conservative difference

$$f(u)_x|_{x=x_j}\frac{1}{\mathrm{\Delta }x}\left(\widehat{f}_{j+1/2}\widehat{f}_{j1/2}\right)$$

where $`\widehat{f}_{j+1/2}`$ is the numerical flux. $`g(u)_y`$ is approximated in the same way. Hence finite difference methods have the same format for one and several space dimensions, which is a major advantage. For the simplest case of a scalar equation (3) and if $`f^{}(u)0`$, the fifth order finite difference WENO scheme has the flux given by

$$\widehat{f}_{j+1/2}=w_1\widehat{f}_{j+1/2}^{(1)}+w_2\widehat{f}_{j+1/2}^{(2)}+w_3\widehat{f}_{j+1/2}^{(3)}$$

where $`\widehat{f}_{j+1/2}^{(i)}`$ are three third order accurate fluxes on three different stencils given by

$`\widehat{f}_{j+1/2}^{(1)}`$ $`=`$ $`{\displaystyle \frac{1}{3}}f(u_{j2}){\displaystyle \frac{7}{6}}f(u_{j1})+{\displaystyle \frac{11}{6}}f(u_j),`$
$`\widehat{f}_{j+1/2}^{(2)}`$ $`=`$ $`{\displaystyle \frac{1}{6}}f(u_{j1})+{\displaystyle \frac{5}{6}}f(u_j)+{\displaystyle \frac{1}{3}}f(u_{j+1}),`$
$`\widehat{f}_{j+1/2}^{(3)}`$ $`=`$ $`{\displaystyle \frac{1}{3}}f(u_j)+{\displaystyle \frac{5}{6}}f(u_{j+1}){\displaystyle \frac{1}{6}}f(u_{j+2}).`$
Notice that the combined stencil for the flux $`\widehat{f}_{j+1/2}`$ is biased to the left, which is upwinding for the positive wind direction due to the assumption $`f^{}(u)0`$. The key ingredient for the success of WENO scheme relies on the design of the nonlinear weights $`w_i`$, which are given by

$$w_i=\frac{\stackrel{~}{w}_i}{_{k=1}^3\stackrel{~}{w}_k},\stackrel{~}{w}_k=\frac{\gamma _k}{(\epsilon +\beta _k)^2},$$

where the linear weights $`\gamma _k`$ are chosen to yield fifth order accuracy when combining three third order accurate fluxes, and are given by

$$\gamma _1=\frac{1}{10},\gamma _2=\frac{3}{5},\gamma _3=\frac{3}{10};$$

the smoothness indicators $`\beta _k`$ are given by

$`\beta _1`$ $`=`$ $`{\displaystyle \frac{13}{12}}\left(f(u_{j2})2f(u_{j1})+f(u_j)\right)^2+{\displaystyle \frac{1}{4}}\left(f(u_{j2})4f(u_{j1})+3f(u_j)\right)^2`$
$`\beta _2`$ $`=`$ $`{\displaystyle \frac{13}{12}}\left(f(u_{j1})2f(u_j)+f(u_{j+1})\right)^2+{\displaystyle \frac{1}{4}}\left(f(u_{j1})f(u_{j+1})\right)^2`$
$`\beta _3`$ $`=`$ $`{\displaystyle \frac{13}{12}}\left(f(u_j)2f(u_{j+1})+f(u_{j+2})\right)^2+{\displaystyle \frac{1}{4}}\left(3f(u_j)4f(u_{j+1})+f(u_{j+2})\right)^2,`$
and they measure how smooth the approximation based on a specific stencil is in the target cell. Finally, $`\epsilon `$ is a parameter to avoid the denominator to become zero and is usually taken as $`\epsilon =10^6`$ in the computation.

This finishes the description of the fifth order finite difference WENO scheme in the simplest case. As we can see, the algorithm is actually quite simple and the user does not need to tune any parameters in the scheme.

The WENO finite difference scheme is characterized by the following properties. (1) The scheme is proven to be uniformly fifth order accurate including at smooth extrema, and this is verified numerically. (2) Near discontinuities the scheme produces sharp and non-oscillatory discontinuity transition. (3) The approximation is self-similar. That is, when fully discretized with the Runge-Kutta methods discussed in next section §2.3, the scheme is invariant when the spatial and time variables are scaled by the same factor. This is a major advantage for approximating conservation laws which are invariant under such scaling. For the details of how the scheme can be generalized in a more complex situation, eventually to 3D systems such as Euler equations, we refer to the reference .

### 2.3 Time Discretizations

To further discretize in time, we use a class of high order nonlinearly stable Runge-Kutta time discretizations. A distinctive feature of this class of time discretizations is that they are convex combinations of first order forward Euler steps, hence they maintain strong stability properties in any semi-norm (total variation norm, maximum norm, entropy condition, etc.) of the forward Euler step, with a time step restriction proportional to that for the forward Euler step to be stable, this proportion coefficient being termed CFL coefficient of the high order Runge-Kutta method. The most popular scheme in this class is the following third order Runge-Kutta method for solving $`u_t=L(u,t)`$, where $`L(u,t)`$ is a spatial discretization operator:

$`u^{(1)}`$ $`=`$ $`u^n+\mathrm{\Delta }tL(u^n,t^n)`$
$`u^{(2)}`$ $`=`$ $`{\displaystyle \frac{3}{4}}u^n+{\displaystyle \frac{1}{4}}u^{(1)}+{\displaystyle \frac{1}{4}}\mathrm{\Delta }tL(u^{(1)},t^n+\mathrm{\Delta }t)`$ (4)
$`u^{n+1}`$ $`=`$ $`{\displaystyle \frac{1}{3}}u^n+{\displaystyle \frac{2}{3}}u^{(2)}+{\displaystyle \frac{2}{3}}\mathrm{\Delta }tL(u^{(2)},t^n+{\displaystyle \frac{1}{2}}\mathrm{\Delta }t),`$
which is nonlinearly stable with a CFL coefficient 1.0. However, for our purpose of 3D calculations, storage is a paramount consideration. We thus use the third order low storage nonlinearly stable Runge-Kutta method which was proven to be nonlinearly stable in , with a CFL coefficient 0.32.

The timestep is chosen by the minimum value among three time scales. The first is from the Courant condition given by

$$\mathrm{\Delta }t\frac{CFL\times a(t)\mathrm{\Delta }x}{\text{max}(|u_x|+c_s,|u_y|+c_s,|u_z|+c_s)}$$
(5)
where $`\mathrm{\Delta }x`$ is the cell size, $`c_s`$ is the local sound speed, $`u_x`$, $`u_y`$ and $`u_z`$ are the local fluid velocities and $`CFL`$ is the Courant number, typically, we take $`CFL=0.3`$. The second constraint is imposed by cosmic expansion which requires that $`\mathrm{\Delta }a/a<0.02`$ within single time step. The last constraint comes from the requirement that a particle move no more than a fixed fraction of cell size in one time step.

## 3 Cosmological Application: IGM and Ly$`\alpha `$ Forest at High Redshift

We run our hybrid N-body/hydrodynamic code to compute the cosmic evolution of coupled system of both dark matter and baryonic matter in a flat low density CDM model ($`\mathrm{\Lambda }`$CDM), which is specified by the cosmological parameters $`(\mathrm{\Omega }_m,\mathrm{\Omega }_\mathrm{\Lambda },h,\sigma _8,\mathrm{\Omega }_b)=(0.3,0.7,0.65,0.9,0.035)`$. The simulations were performed in a periodic, cubical box of size 12h-1Mpc with a 1283 grid and an equal number of dark matter particles. Atomic processes including ionization, radiative cooling and heating are modeled as in Cen in a primeval plasma of hydrogen and helium of composition ($`X=0.76`$, $`Y=0.24`$). The uniform UV-background of ionizing photons is assumed to have a power-law spectrum of the form $`J(\nu )=J_{21}\times 10^{21}(\nu /\nu _{HI})^\alpha `$ergs-1cm-2sr-1Hz-1 parameterized by photoionizing flux $`J_{21}`$ at the Lyman limit frequency $`\nu _{HI}`$, and is suddenly switched on at $`z6`$ to heat the gas and reionize the universe.

The evolution of the IGM temperature relies on the reionization history of hydrogen and helium, and plays important role in our understanding the Ly$`\alpha `$ absorption spectrum. It is expected that a power-law relation between IGM temperature and density $`T=T_0(\rho /<\rho >)^{\gamma 1}`$ could be established due to the ionizing photon heating the gas. We test T versus $`\rho `$ relation using the simulation samples. Fig.(1) shows the scatter plot of temperature-density relation drawn from the simulation at the output of redshift z=3. Apparently, the T-$`\rho `$ relation approximates roughly a power law with a best-fitting value of $`\gamma =0.56`$. The dispersions in temperature at a fixed density mainly arise from the shock-heating.

Mock Ly$`\alpha `$ spectra are produced along random lines of sight in the simulation box, and meanwhile, the corresponding one-dimension distributions of IGM density and peculiar velocity are also extracted from the sample. The results are demonstrated in Fig.(2). To compare with the observation, e.g. the Keck spectrum of QSO q0014+8118, we Gaussian smooth the spectra to match with the spectral resolutions of observation and normalize the spectra by the observed mean flux decrement. For q0014+8118, we have $`D=1<e^\tau >0.31`$. It could be shown that there are good agreements of flux power spectrum and some higher-order statistical behaviors (e.g. intermittency) between the observation and simulations.


format: text

text:
# Heavy Quarkonium Inclusive Decays: Theoretical Status and Perspectives

## 1 Introduction

In recent years, the study of heavy quarkonia ($`b\overline{b}`$, $`c\overline{c}`$, …) has gone through several theoretical and experimental advances.

From the theoretical side the introduction of non-relativistic effective field theories (EFTs) of QCD has put our description of these systems on the solid ground of QCD. It has made it possible, in the case of several observables, to factorize the high-energy dynamics into matching coefficients calculable in perturbation theory and the non-perturbative QCD dynamics into few well-defined matrix elements to be fitted on the data or calculated on the lattice. Systematic improvements are possible, either calculating higher-order corrections in the coupling constant or adding higher-order operators.

Heavy quarkonium, being a non-relativistic bound state, is characterized by a hierarchy of energy scales $`m`$, $`mv`$ and $`mv^2`$, where $`m`$ is the heavy-quark mass and $`v1`$ the relative heavy-quark velocity. A hierarchy of EFTs may be constructed by systematically integrating out modes associated to these energy scales. Integrating out degrees of freedom of energy $`m`$, which for heavy quarks can be done perturbatively, leads to non-relativistic QCD (NRQCD). This EFT still contains the lower energy scales as dynamical degrees of freedom. In the last years, the problem of integrating out the remaining dynamical scales of NRQCD has been addressed by several groups and has now reached a solid level of conceptual understanding (an extended list of references can be found in). The ultimate EFT obtained by subsequent matchings from QCD, where only the lightest degrees of freedom of energy $`mv^2`$ are left dynamical, is called potential NRQCD, pNRQCD. This EFT is close to a quantum-mechanical description of the bound system and, therefore, as simple. It has been systematically explored in the dynamical regime ΛQCD<

mv2subscriptΛQCD<

𝑚superscript𝑣2\Lambda_{\rm QCD}{\ \lower-1.2pt\vbox{\hbox{\hbox to0.0pt{$<$\hss}\lower 6.0pt\vbox{\hbox{$\sim$}}}}\ }mv^{2} in and in the regime mv2ΛQCD<

mvmuch-less-than𝑚superscript𝑣2subscriptΛQCD<

𝑚𝑣mv^{2}\ll\Lambda_{\rm QCD}{\ \lower-1.2pt\vbox{\hbox{\hbox to0.0pt{$<$\hss}\lower 6.0pt\vbox{\hbox{$\sim$}}}}\ }mv in. The quantity $`\mathrm{\Lambda }_{\mathrm{QCD}}`$ stands for the generic scale of non-perturbative physics.

From the experimental side new data have recently been produced for heavy-quarkonium observables. Measurements relevant to the determination of heavy-quarkonium inclusive decay widths have come from Fermilab (E835), BES, CLEO and Belle.

In the following I will review recent progress in our theoretical understanding of inclusive and electromagnetic heavy-quarkonium decays. I will recall the NRQCD factorization formulas in Sec. 2 and the pNRQCD factorization in Sec. 3. The presented pNRQCD formulas apply to quarkonia that fulfil mv>

ΛQCDmv2much-greater-than𝑚𝑣>

subscriptΛQCD𝑚superscript𝑣2mv{\ \lower-1.2pt\vbox{\hbox{\hbox to0.0pt{$>$\hss}\lower 6.0pt\vbox{\hbox{$\sim$}}}}\ }\Lambda_{\rm QCD}\gg mv^{2}. In Sec. 4, I will discuss the main difficulties that still prevent us from obtaining precise predictions from the above formulas and indicate what progress has been made towards an eventual solution of these difficulties.

## 2 NRQCD factorization

The NRQCD factorization formulas are obtained by separating contributions coming from degrees of freedom of energy $`m`$ from those coming from degrees of freedom of lower energy. In the case of heavy-quarkonium decay widths, the first are encoded in the imaginary parts of the four-fermion matching coefficients, $`f,g_{1,8,ee,\gamma \gamma }(^{2S+1}L_J)`$ and are ordered in powers of $`\alpha _\mathrm{s}(m)`$. The second are encoded into the matrix elements of the four-fermion operators on the heavy-quarkonium states $`|H`$ ($`\mathrm{}_HH|\mathrm{}|H`$). These are non-perturbative objects, which are counted, at least, in powers of $`mv`$. Matrix elements of higher dimensionality are suppressed in $`v`$. Including up to the NRQCD four-fermion operators of dimension 8, the NRQCD factorization formulas for inclusive decay widths of heavy quarkonia into light hadrons ($`LH`$) read:

$`\mathrm{\Gamma }(V_Q(nS)LH)={\displaystyle \frac{2}{m^2}}(\mathrm{Im}f_1(^3S_1)O_1(^3S_1)_{V_Q(nS)}`$
$`+\mathrm{Im}f_8(^3S_1)O_8(^3S_1)_{V_Q(nS)}+\mathrm{Im}f_8(^1S_0)O_8(^1S_0)_{V_Q(nS)}`$
$`+\mathrm{Im}g_1(^3S_1){\displaystyle \frac{𝒫_1(^3S_1)_{V_Q(nS)}}{m^2}}+\mathrm{Im}f_8(^3P_0){\displaystyle \frac{O_8(^3P_0)_{V_Q(nS)}}{m^2}}`$
$`+\mathrm{Im}f_8(^3P_1){\displaystyle \frac{O_8(^3P_1)_{V_Q(nS)}}{m^2}}+\mathrm{Im}f_8(^3P_2){\displaystyle \frac{O_8(^3P_2)_{V_Q(nS)}}{m^2}}),`$ (1)
$`\mathrm{\Gamma }(P_Q(nS)LH)={\displaystyle \frac{2}{m^2}}(\mathrm{Im}f_1(^1S_0)O_1(^1S_0)_{P_Q(nS)}`$
$`+\mathrm{Im}f_8(^1S_0)O_8(^1S_0)_{P_Q(nS)}+\mathrm{Im}f_8(^3S_1)O_8(^3S_1)_{P_Q(nS)}`$
$`+\mathrm{Im}g_1(^1S_0){\displaystyle \frac{𝒫_1(^1S_0)_{P_Q(nS)}}{m^2}}+\mathrm{Im}f_8(^1P_1){\displaystyle \frac{O_8(^1P_1)_{P_Q(nS)}}{m^2}}),`$ (2)
$`\mathrm{\Gamma }(\chi _Q(nJS)LH)={\displaystyle \frac{2}{m^2}}(\mathrm{Im}f_1(^{2S+1}P_J){\displaystyle \frac{O_1(^{2S+1}P_J)_{\chi _Q(nJS)}}{m^2}}`$
$`+f_8(^{2S+1}S_S)O_8(^1S_0)_{\chi _Q(nJS)}).`$ (3)
At the same order the electromagnetic decay widths are given by:

$`\mathrm{\Gamma }(V_Q(nS)e^+e^{})={\displaystyle \frac{2}{m^2}}(\mathrm{Im}f_{ee}(^3S_1)O_{\mathrm{EM}}(^3S_1)_{V_Q(nS)}`$
$`+\mathrm{Im}g_{ee}(^3S_1){\displaystyle \frac{𝒫_{\mathrm{EM}}(^3S_1)_{V_Q(nS)}}{m^2}}),`$ (4)
$`\mathrm{\Gamma }(P_Q(nS)\gamma \gamma )={\displaystyle \frac{2}{m^2}}(\mathrm{Im}f_{\gamma \gamma }(^1S_0)O_{\mathrm{EM}}(^1S_0)_{P_Q(nS)}`$
$`+\mathrm{Im}g_{\gamma \gamma }(^1S_0){\displaystyle \frac{𝒫_{\mathrm{EM}}(^1S_0)_{P_Q(nS)}}{m^2}}),`$ (5)
$`\mathrm{\Gamma }(\chi _Q(nJ1)\gamma \gamma )=2\mathrm{Im}f_{\gamma \gamma }(^3P_J){\displaystyle \frac{O_{\mathrm{EM}}(^3P_J)_{\chi _Q(nJ1)}}{m^4}},J=0,2.`$ (6)
The symbols $`V_Q`$ and $`P_Q`$ indicate respectively the vector and pseudoscalar $`S`$-wave heavy quarkonium and the symbol $`\chi _Q`$ the generic $`P`$-wave quarkonium (the states $`\chi _Q(n10)`$ and $`\chi _Q(nJ1)`$ are usually called $`h_Q((n1)P)`$ and $`\chi _{QJ}((n1)P)`$, respectively).

The operators $`O,𝒫_{1,8,\mathrm{EM}}(^{2S+1}L_J)`$ are the dimension $`6`$ and $`8`$ four-fermion operators of the NRQCD Lagrangian. They are classified in dependence of their transformation properties under colour as singlets ($`1`$) and octets ($`8`$) and under spin ($`S`$), orbital ($`L`$) and total angular momentum ($`J`$). The operators with the subscript EM are the singlet operators projected on the QCD vacuum. The explicit expressions of the operators may be found in.

The imaginary parts of the four-fermion matching coefficients have been calculated over the last twenty years to different levels of precision. In the following I will indicate, to the best of my knowledge, some recent literature where their updated value may be found. If the case arises, references to the original literature may also be found there. The imaginary parts of $`f_8(^3S_1)`$, $`f_8(^1S_0)`$, $`f_8(^3P_J)`$, $`f_1(^{2S+1}P_J)`$, and $`f_1(^1S_0)`$ (this originally calculated in) have been calculated up to order $`\alpha _\mathrm{s}^3`$ in. A different result for $`f_1(^3P_0)`$ and $`f_1(^3P_2)`$ is in. The imaginary part of $`f_1(^3S_1)`$ has been calculated up to order $`\alpha _\mathrm{s}^4`$ in, the imaginary part of $`g_1(^3S_1)`$ at order $`\alpha _\mathrm{s}^3`$ may be found in, the imaginary part of $`g_1(^1S_0)`$ at order $`\alpha _\mathrm{s}^2`$ in and the imaginary part of $`f_8(^1P_1)`$ at order $`\alpha _\mathrm{s}^2`$ in. Where the electromagnetic coefficients are concerned, the imaginary part of $`f_{ee}(^3S_1)`$ has been calculated up to order $`\alpha ^2\alpha _\mathrm{s}^2`$ in, the imaginary parts of $`f_{\gamma \gamma }(^1S_0)`$ and $`f_{\gamma \gamma }(^3P_{0,2})`$ up to order $`\alpha ^2\alpha _\mathrm{s}`$ (originally calculated in) and $`g_{ee}(^3S_1)`$ and $`g_{\gamma \gamma }(^1S_0)`$ up to order $`\alpha ^2`$ may be found in.

The NRQCD matrix elements are poorly known. They may be fitted on the experimental decay data, as in, or calculated on the lattice. The matrix elements of singlet operators may be linked at leading order to the Schrödinger wave functions in the origin and are often evaluated by means of potential models.

## 3 pNRQCD factorization

The pNRQCD expressions of the NRQCD matrix elements are obtained by integrating out degrees of freedom of energy larger than $`mv^2`$. Four different situations are possible: $`\mathrm{\Lambda }_{\mathrm{QCD}}mv^2`$, $`\mathrm{\Lambda }_{\mathrm{QCD}}mv^2`$, $`mv\mathrm{\Lambda }_{\mathrm{QCD}}mv^2`$ and $`\mathrm{\Lambda }_{\mathrm{QCD}}mv`$. In the first situation the NRQCD matrix elements may be calculated perturbatively up to non-perturbative corrections of the form of local condensates. This situation may apply to the ground state of bottomonium. Explicit formulas have been worked out for the electromagnetic decay of the $`\mathrm{{\rm Y}}(1S)`$ in. In the situation $`\mathrm{\Lambda }_{\mathrm{QCD}}mv^2`$ the NRQCD matrix elements turn out to be convolutions of non-local condensates and perturbative Green functions. In this situation, which may apply to the ground states of bottomonium and charmonium, only the real part of the spectrum has been studied. Calculations of decay widths have not been done so far. In this situation, however, the state and flavour-dependent part will not factor out from the integrals. The situations $`mv\mathrm{\Lambda }_{\mathrm{QCD}}mv^2`$ and $`\mathrm{\Lambda }_{\mathrm{QCD}}mv`$ have been studied in. In principle they may apply to all heavy quarkonium states below threshold and above the ground state. Both situations give the same physical results and will be summarized in the following.111 Possible threshold effects have been neglected. As suggested in they may be large for the $`\psi (2S)`$. The main point here is that, since $`\mathrm{\Lambda }_{\mathrm{QCD}}`$ is well separated from the energy scale of the bound state, $`mv^2`$, the state dependence of the NRQCD matrix elements factorizes in the quarkonium wave function, while contributions coming from excitations of order $`\mathrm{\Lambda }_{\mathrm{QCD}}`$ are encoded into a few universal constants.

### 3.1 pNRQCD factorization in the case mv>

ΛQCDmv2much-greater-than𝑚𝑣>

subscriptΛQCD𝑚superscript𝑣2mv\!{\ \lower-1.2pt\vbox{\hbox{\hbox to0.0pt{$>$\hss}\lower 6.0pt\vbox{\hbox{$\sim$}}}}\ }\!\Lambda_{\rm QCD}\!\gg\!mv^{2}

The matrix element of the NRQCD operator $`O`$ on the heavy-quarkonium state $`|H`$ at rest, $`𝐏=0`$, with quantum numbers $`n`$, $`j`$, $`l`$ and $`s`$, may be written in terms of the eigenstates $`|\underset{¯}{k};𝐱_1𝐱_2`$ of the NRQCD Hamiltonian as

$`O_H={\displaystyle \frac{1}{𝐏=0|𝐏=0}}{\displaystyle d^3rd^3r^{}d^3Rd^3R^{}𝐏=0|𝐑njls|𝐫}`$
$`\times \left[\underset{¯}{0};𝐱_1𝐱_2|{\displaystyle d^3\xi O(𝝃)}|\underset{¯}{0};𝐱_1^{}𝐱_2^{}\right]𝐑^{}|𝐏=0𝐫^{}|njls,`$
where $`𝐫=𝐱_1𝐱_2`$, $`𝐫^{}=𝐱_1^{}𝐱_2^{}`$, $`𝐑=(𝐱_1+𝐱_2)/2`$ and $`𝐑^{}=(𝐱_1^{}+𝐱_2^{})/2`$.

In the situation mv>

ΛQCDmv2much-greater-than𝑚𝑣>

subscriptΛQCD𝑚superscript𝑣2mv{\ \lower-1.2pt\vbox{\hbox{\hbox to0.0pt{$>$\hss}\lower 6.0pt\vbox{\hbox{$\sim$}}}}\ }\Lambda_{\rm QCD}\gg mv^{2} and assuming that all the higher gluonic excitations of the two heavy quarks develop a mass gap of order $`\mathrm{\Lambda }_{\mathrm{QCD}}`$, the matrix element $`\underset{¯}{0};𝐱_1𝐱_2|O(𝝃)|\underset{¯}{0};𝐱_1^{}𝐱_2^{}`$ has been calculated order by order in $`1/m`$ in. Once normalized to $`m`$, we get up to $`𝒪(v^3\times (\mathrm{\Lambda }_{\mathrm{QCD}}^2/m^2,E/m))`$ for the NRQCD $`S`$-wave matrix elements and up to $`𝒪(v^5)`$ for the NRQCD $`P`$-wave matrix elements:

$`O_1(^3S_1)_{V_Q(nS)}=C_A{\displaystyle \frac{|R_{n0}^V(0)|^2}{2\pi }}(1{\displaystyle \frac{E_{n0}^{(0)}}{m}}{\displaystyle \frac{2_3}{9}}+{\displaystyle \frac{2_3^{(2,t)}}{3m^2}}+{\displaystyle \frac{c_F^2_1}{3m^2}}),`$ (7)
$`O_1(^1S_0)_{P_Q(nS)}=C_A{\displaystyle \frac{|R_{n0}^P(0)|^2}{2\pi }}(1{\displaystyle \frac{E_{n0}^{(0)}}{m}}{\displaystyle \frac{2_3}{9}}+{\displaystyle \frac{2_3^{(2,t)}}{3m^2}}+{\displaystyle \frac{c_F^2_1}{m^2}}),`$ (8)
$`O_{\mathrm{EM}}(^3S_1)_{V_Q(nS)}=C_A{\displaystyle \frac{|R_{n0}^V(0)|^2}{2\pi }}(1{\displaystyle \frac{E_{n0}^{(0)}}{m}}{\displaystyle \frac{2_3}{9}}+{\displaystyle \frac{2_3^{(2,\mathrm{EM})}}{3m^2}}+{\displaystyle \frac{c_F^2_1}{3m^2}}),`$
(9)
$`O_{\mathrm{EM}}(^1S_0)_{P_Q(nS)}=C_A{\displaystyle \frac{|R_{n0}^P(0)|^2}{2\pi }}(1{\displaystyle \frac{E_{n0}^{(0)}}{m}}{\displaystyle \frac{2_3}{9}}+{\displaystyle \frac{2_3^{(2,\mathrm{EM})}}{3m^2}}+{\displaystyle \frac{c_F^2_1}{m^2}}),`$
(10)
$`O_1(^{2S+1}P_J)_{\chi _Q(nJS)}=O_{\mathrm{EM}}(^{2S+1}P_J)_{\chi _Q(nJS)}={\displaystyle \frac{3}{2}}{\displaystyle \frac{C_A}{\pi }}|R_{n1}^{(0)}(0)|^2,`$ (11)
$`𝒫_1(^3S_1)_{V_Q(nS)}=𝒫_1(^1S_0)_{P_Q(nS)}=𝒫_{\mathrm{EM}}(^3S_1)_{V_Q(nS)}`$
$`=𝒫_{\mathrm{EM}}(^1S_0)_{P_Q(nS)}=C_A{\displaystyle \frac{|R_{n0}^{(0)}(0)|^2}{2\pi }}(mE_{n0}^{(0)}_1),`$ (12)
$`O_8(^3S_1)_{V_Q(nS)}=O_8(^1S_0)_{P_Q(nS)}`$
$`=C_A{\displaystyle \frac{|R_{n0}^{(0)}(0)|^2}{2\pi }}\left({\displaystyle \frac{2(C_A/2C_f)_3^{(2)}}{3m^2}}\right),`$ (13)
$`O_8(^1S_0)_{V_Q(nS)}={\displaystyle \frac{O_8(^3S_1)_{P_Q(nS)}}{3}}`$
$`=C_A{\displaystyle \frac{|R_{n0}^{(0)}(0)|^2}{2\pi }}\left({\displaystyle \frac{(C_A/2C_f)c_F^2_1}{3m^2}}\right),`$ (14)
$`O_8(^3P_J)_{V_Q(nS)}={\displaystyle \frac{O_8(^1P_1)_{P_Q(nS)}}{3}}`$
$`=(2J+1)C_A{\displaystyle \frac{|R_{n0}^{(0)}(0)|^2}{2\pi }}\left({\displaystyle \frac{(C_A/2C_f)_1}{9}}\right),`$ (15)
$`O_8(^1S_0)_{\chi _Q(nJS)}={\displaystyle \frac{T_F}{3}}{\displaystyle \frac{|R_{n1}^{(0)}(0)|^2}{\pi m^2}}_3,`$ (16)
where $`R_{n0}^V=R_{n0}^{(0)}(1+𝒪(v))`$ is the radial part of the vector $`S`$-wave function, $`R_{n0}^P=R_{n0}^{(0)}(1+𝒪(v))`$ the radial part of the pseudoscalar $`S`$-wave function, $`R_{n1}^{(0)}`$ the derivative of the LO $`P`$-wave function and $`E_{n0}^{(0)}M_H2mmv^2`$ the LO binding energy. A consistent way to calculate the wave functions is from the real part of the pNRQCD Hamiltonian obtained up to order $`1/m^2`$ in. Any other $`S`$-wave dimension-6 matrix element is 0 at NNLO and any other $`S`$-wave dimension-8 matrix element is 0 at LO. The symbol $`c_F`$ indicates the NRQCD chromomagnetic matching coefficient, which is known at NLO from. All the non-perturbative dynamics is encoded into the wave functions and the six chromoelectric and chromomagnetic correlators $`_1`$, $`_3`$, $`_3^{(2)}`$, $`_3^{(2,t)}`$, $`_3^{(2,\mathrm{EM})}`$ and $`_1`$. The exact definition of the correlators may be found in. It is important to note that, owing to the factorization of the state and flavour dependence into the wave function, on the whole set of heavy-quarkonium states below threshold the number of non-perturbative parameters needed to describe inclusive decays has diminished with respect to NRQCD, so that definite new predictions are possible. In practice, one may consider ratios where the wave-function dependence drops out and fix the correlators either through lattice calculations or through specific models of the QCD vacuum or on some set of experimental data. In particular, new predictions for $`P`$-wave bottomonium inclusive decay-width ratios were made in this way in before the CLEO-III data were made available.

## 4 How to use the above formulas

Here I would like to point out that there are two potential problems that may still prevent us from getting precise determinations of heavy-quarkonium decay widths from the above formulas. These problems seem to be often underestimated in the existing literature. Eventually, they may lead to an underestimate of the errors associated to the calculated values of the decay widths or to the extracted values of the matrix elements and $`\alpha _\mathrm{s}(m)`$.

$`i)`$ It has been discussed, in particular in (but see also), that higher-order operators, not considered in the above formulas, can be numerically quite relevant. This may be the case particularly for charmonium, where $`v_c^20.3`$, so that relativistic corrections are large, and for $`P`$-wave decays where the above formulas provide, indeed, only the leading-order contribution in the velocity expansion. In order to be specific, in the case of the $`\chi _c`$ decay width into two photons the corrections of relative $`𝒪(\mathrm{\Lambda }_{\mathrm{QCD}}^2/m^2,E/m)`$ to the formulas (6) are given by:

$`{\displaystyle \frac{\delta \mathrm{\Gamma }(\chi _{c0}\gamma \gamma )}{\mathrm{\Gamma }^{(0)}(\chi _{c0}\gamma \gamma )}}`$ $``$ $`2.3{\displaystyle \frac{E_{\chi _c}}{m_c}}3𝒜\left({\displaystyle \frac{\mathrm{\Lambda }_{\mathrm{QCD}}^2}{m_c^2}}\right),`$
$`{\displaystyle \frac{\delta \mathrm{\Gamma }(\chi _{c2}\gamma \gamma )}{\mathrm{\Gamma }^{(0)}(\chi _{c2}\gamma \gamma )}}`$ $``$ $`1.0{\displaystyle \frac{E_{\chi _c}}{m_c}}4\left({\displaystyle \frac{\mathrm{\Lambda }_{\mathrm{QCD}}^2}{m_c^2}}\right),`$
where $`𝒜\left(\mathrm{\Lambda }_{\mathrm{QCD}}^2/m_c^2\right)`$ and $`\left(\mathrm{\Lambda }_{\mathrm{QCD}}^2/m_c^2\right)`$ are some specific combinations of matrix elements of order $`\mathrm{\Lambda }_{\mathrm{QCD}}^2/m_c^2`$. Choosing $`E_{\chi _c}/m_c0.3`$ and $`|𝒜,(\mathrm{\Lambda }_{\mathrm{QCD}}^2/m_c^2)|0.1`$ (or $`0.3`$)222The first choice corresponds to a hierarchy of the type $`\mathrm{\Lambda }_{\mathrm{QCD}}mv^2`$, the second of the type $`\mathrm{\Lambda }_{\mathrm{QCD}}mv`$. the relative corrections may be $`(0.7\pm 0.3)`$ (or $`(0.7\pm 0.9)`$) for $`\mathrm{\Gamma }(\chi _{c0}\gamma \gamma )`$ and $`(0.3\pm 0.4)`$ (or $`(0.3\pm 1.2)`$) for $`\mathrm{\Gamma }(\chi _{c2}\gamma \gamma )`$ and, therefore, potentially as large as the leading one. The two $`\pm `$ values refer to the two possible choices of sign for $`𝒜`$ and $``$. Note that for some specific choice of sign, large cancellations may also occur.

The introduction of higher-order matrix elements may spoil the predictive power of the NRQCD factorization. A way out is provided by pNRQCD, which can be used to reduce also these new matrix elements to a few universal correlators.

$`ii)`$ The convergence of the perturbative series of the four-fermion matching coefficients is often bad. Let us consider, for instance, the following matching coefficients ($`n_f=3`$):

$`\mathrm{Im}f_1(^1S_0)=(\mathrm{})\times (1+11.1{\displaystyle \frac{\alpha _\mathrm{s}}{\pi }}),`$
$`\mathrm{Im}f_8(^1S_0)=(\mathrm{})\times (1+13.7{\displaystyle \frac{\alpha _\mathrm{s}}{\pi }}),`$
$`\mathrm{Im}f_8(^3S_1)=(\mathrm{})\times (1+10.3{\displaystyle \frac{\alpha _\mathrm{s}}{\pi }}),`$
$`\mathrm{Im}f_1(^3P_0)=(\mathrm{})\times (1+(13.60.44\mathrm{log}{\displaystyle \frac{\mu }{2m}}){\displaystyle \frac{\alpha _\mathrm{s}}{\pi }}),`$
$`\mathrm{Im}f_1(^3P_2)=(\mathrm{})\times (1(0.73+1.67\mathrm{log}{\displaystyle \frac{\mu }{2m}}){\displaystyle \frac{\alpha _\mathrm{s}}{\pi }}).`$
Apart from the case of $`\mathrm{Im}f_1(^3P_2)`$, the series in $`\alpha _\mathrm{s}`$ of the other coefficients does not seem to converge. This behaviour may not be adjusted by a suitable choice of the factorization scale $`\mu `$, which enters only in $`\mathrm{Im}f_1(^3P_0)`$; in this case lowering the factorization scale below $`2m`$ would make the convergence worse.333In the case of the coefficient $`\mathrm{Im}f_{ee}(^3S_1)`$, which presents a similar problem, it has been noted by Beneke et al. in that in the bottomonium case a suitable choice of the factorization scale may adjust the convergence of the series up to order $`\alpha ^2\alpha _\mathrm{s}^2`$. A solution may be provided by the resummation of the large contributions in the perturbative series coming from bubble-chain diagrams. This analysis has been successfully carried out in some specific cases in. A general treatment is still missing, in particular in the case of $`P`$-wave decays.

Finally, I would like to note that neither contributions coming from higher-order matrix elements of the type described in $`(i)`$ nor resummations of large contributions in the perturbative series of the matching coefficients discussed in $`(ii)`$ have been considered in recent determinations of $`\alpha _\mathrm{s}`$ (e.g. in) and of the NRQCD matrix elements (e.g. in) from the charmonium $`P`$-wave decay data.

## 5 Conclusions

The progress in our understanding of non-relativistic effective field theories makes it possible to move beyond ad hoc phenomenological models and have a unified description of the different heavy-quarkonium observables, so that the same quantities determined from a set of data may be used in order to describe other sets. Moreover, predictions based on non-relativistic EFTs are conceptually solid, and systematically improvable. Therefore, the recent progress in the measurement of several heavy-quarkonium observables makes it meaningful to ask whether their precise theoretical determination is feasible.

Here, I have focused on inclusive and electromagnetic heavy-quarkonium decays. In the framework of NRQCD, heavy-quarkonium decay widths may be expressed in terms of matrix elements, which, in the case of matrix elements of singlet operators, may be linked to the wave function in the origin. This is also the case of some matrix elements entering in the description of production processes. In the framework of pNRQCD also some octet matrix elements may be expressed in terms of the wave function in the origin and some universal non-local gluon-field correlators. These correlators enter also in the expression of the masses of some heavy-quarkonium states. Specific predictions have been discussed in. There are, however, still some difficulties that hinder in several cases precise predictions of heavy-quarkonium decay observables. These are essentially related to the control of higher-order corrections in the velocity and $`\alpha _\mathrm{s}`$ expansion and have been addressed in the last section. In principle, the tools to overcome these difficulties already exist, so that progress in the field is expected from the coordinated effort of the heavy-quarkonium community in the near future.

## Acknowledgements

I acknowledge the support of the European Community through a Marie-Curie fellowship, contract No. HPMF-CT-2000-00733.


text:
# Actions for Vacuum Einstein’s Equation with a Killing Symmetry

## 1 Introduction

Dimensional reduction is a crucial step in any high dimensional theory of physics such as, Kaluza-Klein theory  and string theory , in order to make contact with the 4-dimensional sensational world. It is also a useful approach to study 4-dimensional space-time with symmetries in general relativity.

In the appendix of , Geroch introduced a Killing reduction formalism of 4-dimensional space-time. Let $`(M,g_{ab})`$ be a space-time with a Killing vector field $`\xi ^a`$, and $`\xi ^a`$ is either everywhere timelike or everywhere spacelike. The collection of all trajectories of $`\xi ^a`$ gives a 3-dimensional space $`S`$. Geroch’s discussion shows that there is a one-to-one correspondence between tensor fields and tensor operations on $`S`$ and certain tensor fields and tensor operations on $`M`$. Thus, the differential geometry of $`S`$ will be mirrored in $`M`$. Geroch gives the curvature tensor and geometric properties of $`S`$ and finally the field equations on $`S`$, which is equivalent to the vacuum Einstein equation on $`M`$. If the Killing vector field $`\xi ^a`$ is hypersurface orthogonal, there is a well-known conclusion that $`3+1`$ gravity is equivalent to $`2+1`$ gravity coupled to a massless scalar field.

Geroch’s work concerned only the reduction of the equation of motion. In this paper, we will study the Killing reduction from the viewpoint of variation principle. It turns out that, if one starts with the symmetry-reduced Hilbert action, the 4-metric components rather than the variables of Geroch have to be regarded as the arguments in order to get the correct reduced fields equations. An alternative action in the arguments of Geroch’s 3-dimensional fields is also obtained, which gives the same field equations as Geroch’s on $`S`$. If we confined the configuration to static space-time, both actions are reduced to that of 3-dimensional Euclidean gravity coupled to a massless Klein-Gordon field, which is consistent with the reduced action in .

## 2 Killing reduction of space-time

Let $`(M,g_{ab})`$ be a space-time with Killing vector field $`\xi ^a`$, which is either everywhere timelike or everywhere spacelike. Let $`S`$ denote the collection of all trajectories of $`\xi ^a`$. An element of $`S`$ is an inextendible curve in $`M`$ which is everywhere tangent to $`\xi ^a`$.

A mapping $`\psi `$ from $`M`$ to $`S`$ can be defined as follows: For each point $`p`$ of $`M`$, $`\psi (p)`$ is the trajectory of $`\xi ^a`$ passing through $`p`$. Assume $`S`$ is given the structure of a differentiable 3-manifold such that $`\psi `$ is a smooth mapping.

If the Killing field $`\xi ^a`$ were hypersurface orthogonal, it would be possible to represent $`S`$ as one of the hypersurfaces in $`M`$ which is everywhere orthogonal to $`\xi ^a`$. Each trajectory of $`\xi ^a`$ would intersect this hypersurface in exactly one point.

In the non-hypersurface-orthogonal case. It is most natural to regard $`S`$ as a quotient space of $`M`$ rather than a subspace. Geroch shows that there is a one-to-one correspondence between tensor fields $`T_{a\mathrm{}c}^{b\mathrm{}d}`$ on $`S`$ and tensor fields $`T_{a\mathrm{}c}^{b\mathrm{}d}`$ on $`M`$ which satisfy

$$\xi ^aT_{a\mathrm{}c}^{b\mathrm{}d}=0,\mathrm{},\xi _dT_{a\mathrm{}c}^{b\mathrm{}d}=0,$$

$$_\xi T_{a\mathrm{}c}^{b\mathrm{}d}=0.$$
(1)
The entire tensor algebra on $`S`$ is completely and uniquely mirrored by tensors on $`M`$ subject to (1). So the primes will be dropped hereafter: Speaking of tensor fields being on $`S`$ is merely as a shorthand way of saying that the field on $`M`$ satisfies (1).

The metric and inverse metric on $`S`$ are defined as

$$h_{ab}=g_{ab}\lambda ^1\xi _a\xi _b,$$
(2)
$$h^{ab}=g^{ab}\lambda ^1\xi ^a\xi ^b,$$
(3)
$$h_a^b=\delta _a^b\lambda ^1\xi _a\xi ^b,$$
(4)
where $`\lambda `$ is the norm of Killing field $`\xi ^a`$, i.e.,

$$\lambda =\xi ^m\xi _m.$$
(5)
Note that the indices of any tensor on $`S`$ can be raised or lowered with either $`h`$ or $`g`$ with the same result.

The covariant derivative operator on $`S`$ is defined as

$$D_eT_{a\mathrm{}c}^{b\mathrm{}d}=h_a^m\mathrm{}h_c^nh_r^b\mathrm{}h_s^dh_e^p_pT_{m\mathrm{}n}^{r\mathrm{}s},$$
(6)
which satisfies all the conditions of derivative operator and

$$D_ch_{ab}=0.$$
(7)
The twist of $`\xi ^a`$ is defined by

$$\omega _a=ϵ_{abcd}\xi ^b^c\xi ^d.$$
(8)
The Ricci tensor $`_{ab}`$ of $`h_{ab}`$ on $`S`$ is related to that of $`g_{ab}`$ on $`M`$ by

$`_{ab}`$ $`=`$ $`{\displaystyle \frac{1}{2}}\lambda ^2(\omega _a\omega _bh_{ab}\omega ^c\omega _c)+{\displaystyle \frac{1}{2}}\lambda ^1D_aD_b\lambda `$ (9)
$`{\displaystyle \frac{1}{4}}\lambda ^2(D_a\lambda )(D_b\lambda )+h_a^ch_b^dR_{cd}.`$
Contracting Eq. (9) we get the relation between the scalar curvatures $``$ of $`h_{ab}`$ and $`R`$ of $`g_{ab}`$ as

$``$ $`=`$ $`{\displaystyle \frac{1}{2}}\lambda ^2\omega _a\omega _bh^{ab}+\lambda ^1h^{ab}D_aD_b\lambda `$ (10)
$`{\displaystyle \frac{1}{2}}\lambda ^2h^{ab}(D_a\lambda )(D_b\lambda )+R.`$
As shown in , in the source-free case (the 4-dimensional Ricci tensor $`R_{ab}=0`$), $`\omega _a`$ is a gradient:

$$\omega _a=D_a\omega .$$
(11)
The Ricci tensor $`_{ab}`$ on $`S`$ then takes the form

$`_{ab}`$ $`=`$ $`{\displaystyle \frac{1}{2}}\lambda ^2[(D_a\omega )(D_b\omega )h_{ab}(D^m\omega )(D_m\omega )]`$ (12)
$`+{\displaystyle \frac{1}{2}}\lambda ^1D_aD_b\lambda {\displaystyle \frac{1}{4}}\lambda ^2(D_a\lambda )(D_b\lambda ).`$
and the scalar fields on $`S`$ satisfy

$$D^2\lambda =\frac{1}{2}\lambda ^1(D^m\lambda )(D_m\lambda )\lambda ^1(D^m\omega )(D_m\omega ),$$
(13)
$$D^2\omega =\frac{3}{2}\lambda ^1(D^m\lambda )(D_m\omega ).$$
(14)
Eqs. (12), (13) and (14) are equivalent to the vaccum Einstein’s equation of $`g_{ab}`$.

## 3 Alternative actions on $`S`$

### 3.1 The symmetry-reduced Hilbert action

The Einstein-Hilbert action on $`M`$ is defined by

$$S_{EH}[g^{ab}]=_M_G=_M\sqrt{g}R,$$
(15)
where g is the determinant of 4-metric components $`g_{\mu \nu }`$ in some basis on $`M`$.

Suppose the Killing vector field is everywhere timelike. For practical calculations, it is convenient to take a coordinate system adapted to the congruence:

$$t^a=\left(\frac{}{t}\right)^a=\xi ^a.$$
(16)
Then the line element of $`g_{ab}`$ on $`M`$ can be written as

$$\mathrm{d}s^2=h_{\mu \nu }\mathrm{d}x^\mu \mathrm{d}x^\nu +\lambda (\mathrm{d}t+B_\mu \mathrm{d}x^\mu )^2.$$
(17)
The components of metric are

$$g_{\mu \nu }=h_{\mu \nu }+\lambda ^1\xi _\mu \xi _\nu ,g_{\mu 4}=\xi _\mu =\lambda B_\mu ,g_{44}=\xi _4=\lambda .$$
(18)
We also have

$$2B_{[\mu ,\nu ]}=|\lambda |^{3/2}ϵ_{\mu \nu \rho }\omega ^\rho ,ϵ_{\mu \nu \rho }=|\lambda |^{1/2}ϵ_{\mu \nu \rho \sigma }\xi ^\sigma .$$
(19)
Let $`h`$ denote the determinant of $`h_{\mu \nu }`$ on $`S`$. Straightforward calculations give

$`g=\lambda h.`$ (20)
This formula is still valid in the case where $`\xi ^a`$ is everywhere spacelike.

Since the principle of symmetric criticality is valid in the one Killing vector model of general relativity , one expects that the 3-dimensional fields Eqs. (12), (13) and (14) could be obtained by the variations of the action from symmetric reduction of (15), which can be read from Eq. (10) as

$`S_{EH}={\displaystyle _S}|\lambda |^{1/2}\sqrt{|h|}(+{\displaystyle \frac{1}{2}}\lambda ^2\omega _a\omega _bh^{ab}),`$ (21)
where a 3-dimensional total divergence term has been neglected. This reduced action cannot lead to the correct reduced fields equations by variations with respect to the Geroch’s variables $`(h^{ab},\lambda ,\omega _a)`$. For instance, the variation of (21) with respect to $`\omega _a`$ leads to $`\omega _a=0`$, which is not the case in general. This is not a very surprising result since the relation of $`\omega _a`$ and the 4-metric components is rather nontrivial, as one can see from Eq. (19). Although the variation of Hilbert action with respect to the 4-metric gives certainly the Einstein equation, there is no guarantee to get the same equation if one varies it with respect to other variables arbitrarily concocted such as $`\omega _a`$. Eq. (19) suggests a one-form $`A_a`$ at least locally on $`S`$ such that

$$(dA)_{ab}=|\lambda |^{3/2}ϵ_{bac}\omega ^c.$$
(22)
Substituting $`A_a`$ for $`\omega _a`$ in Eq. (21), we get the familiar form of the symmetry-reduced action

$`S_{EH}[h^{ab},A_c,\lambda ]={\displaystyle _S}|\lambda |^{1/2}\sqrt{|h|}[{\displaystyle \frac{1}{4}}\lambda h^{ab}h^{cd}(dA)_{ac}(dA)_{bd}].`$ (23)
The variations of this action with respect to $`(h^{ab},A_c,\lambda )`$ will give the correct reduced fields equations on $`S`$, that can be checked directly by substituting $`\omega _a`$ back for $`A_a`$ after variations.

### 3.2 Hypersurface orthogonal case

We now consider a special case where the Killing field $`\xi ^a`$ is hypersurface orthogonal. It is then possible to represent $`S`$ as one of the hypersurfaces in $`M`$ which is everywhere orthogonal to $`\xi ^a`$. The symmetry-reduced Einstein-Hilbert action on $`S`$ reads

$`S_{EH}[h^{ab}]={\displaystyle _S}_G={\displaystyle _S}|\lambda |^{1/2}\sqrt{|h|}.`$ (24)
To obtain regular form of action on $`S`$, we now conformally transform $`h_{ab}`$ as $`\stackrel{~}{h}_{ab}`$:

$$\stackrel{~}{h}_{ab}=\mathrm{\Omega }^2h_{ab}.$$
(25)
Let $`\stackrel{~}{D}_a`$ be the covariant derivative operator determined by metric $`\stackrel{~}{h}_{ab}`$, i.e.,

$$\stackrel{~}{D}_a\stackrel{~}{h}_{bc}=0.$$
(26)
$`\stackrel{~}{D}_a`$ is related to $`D_a`$ by

$$D_av_b=\stackrel{~}{D}_av_bC_{ab}^cv_c,$$
(27)
where

$`C_{ab}^c`$ $`=`$ $`{\displaystyle \frac{1}{2}}h^{cd}(\stackrel{~}{D}_ah_{bd}+\stackrel{~}{D}_bh_{ad}\stackrel{~}{D}_dh_{ab})`$ (28)
$`=`$ $`\stackrel{~}{h}_b^c\stackrel{~}{D}_a\mathrm{ln}\mathrm{\Omega }+\stackrel{~}{h}_a^c\stackrel{~}{D}_b\mathrm{ln}\mathrm{\Omega }\stackrel{~}{h}_{ab}\stackrel{~}{h}^{cd}\stackrel{~}{D}_d\mathrm{ln}\mathrm{\Omega }.`$
After the conformal transform, the form of action (24) becomes

$`S_{EH}[\stackrel{~}{h}^{ab}]`$ $`=`$ $`{\displaystyle _S}|\lambda |^{1/2}\sqrt{\mathrm{\Omega }^6|\stackrel{~}{h}|}\mathrm{\Omega }^2[\stackrel{~}{}4\stackrel{~}{h}^{ab}\stackrel{~}{D}_a\stackrel{~}{D}_b\mathrm{ln}\mathrm{\Omega }`$ (29)
$`2\stackrel{~}{h}^{ab}(\stackrel{~}{D}_a\mathrm{ln}\mathrm{\Omega })(\stackrel{~}{D}_b\mathrm{ln}\mathrm{\Omega })].`$
Let

$$\mathrm{\Omega }=|\lambda |^{1/2},$$
(30)
then (29) becomes

$`S_{EH}[\stackrel{~}{h}^{ab}]={\displaystyle _S}\sqrt{|\stackrel{~}{h}|}\left[\stackrel{~}{}4\stackrel{~}{h}^{ab}\stackrel{~}{D}_a\stackrel{~}{D}_b\mathrm{ln}\mathrm{\Omega }2\stackrel{~}{h}^{ab}(\stackrel{~}{D}_a\mathrm{ln}\mathrm{\Omega })(\stackrel{~}{D}_b\mathrm{ln}\mathrm{\Omega })\right].`$ (31)
Note that the second term in (31) is a total divergence term that can be ignored for variations. Let

$$\mathrm{\Lambda }\sqrt{2}\mathrm{ln}\mathrm{\Omega },$$
(32)
straightforward calculations of variations show that the action (31) gives the same equations of motion as those of 3-gravity $`\stackrel{~}{h}^{ab}`$ coupled to a massless Klein-Gordon field $`\mathrm{\Lambda }`$, which is defined by the coupled action:

$$S_E+S_{KG}=_S\sqrt{|\stackrel{~}{h}|}[\stackrel{~}{R}\stackrel{~}{h}^{ab}(_a\mathrm{\Lambda })(_b\mathrm{\Lambda })].$$
(33)
Therefore, a 4-dimensional space-time with a hypersurface orthogonal Killing vector field which is either everywhere timelike or everywhere spacelike, is “conformally” equivalent to 3-dimensional gravity coupled to a massless scalar field. Static space-time is of course a typical case .

### 3.3 An alternative action

In Geroch’s reduction, the 4-dimensional Einstein vacuum $`(M,g_{ab})`$ reduces in general to a 3-dimensional gravity coupled to two scalar fields on $`S`$ satisfying Eqs. (12), (13) and (14). One may ask if there is an action in the arguments of Geroch’s variables $`\omega `$ and $`\lambda `$ on $`S`$, whose variations give the above Geroch’s equations. Note that in hypersurface orthogonal case, besides $`\stackrel{~}{h}_{ab}`$ only one scalar field $`\lambda `$ exists on $`S`$. Up to a boundary term the action (31) can be written as

$`S_{EH}[\stackrel{~}{h}^{ab}]={\displaystyle _S}\sqrt{|\stackrel{~}{h}|}\left[\stackrel{~}{}{\displaystyle \frac{1}{2}}\lambda ^2\stackrel{~}{h}^{ab}(\stackrel{~}{D}_a\lambda )(\stackrel{~}{D}_b\lambda )\right].`$ (34)
While in general case, another scalar field $`\omega `$ exists on $`S`$. By carefully observing Geroch’s equations and the special action (34), we propose an action for the reduced fields equations on $`S`$ as

$`S[\stackrel{~}{h}^{ab}]={\displaystyle _S}\sqrt{|\stackrel{~}{h}|}\left[\stackrel{~}{}{\displaystyle \frac{1}{2}}\lambda ^2\stackrel{~}{h}^{ab}(\stackrel{~}{D}_a\lambda )(\stackrel{~}{D}_b\lambda ){\displaystyle \frac{1}{2}}\lambda ^2\stackrel{~}{h}^{ab}(\stackrel{~}{D}_a\omega )(\stackrel{~}{D}_b\omega )\right].`$ (35)
We now show that the variations of (35) give exactly the same field equations as those of Geroch’s work.

The variation of (35) with respect to $`\stackrel{~}{h}^{ab}`$ gives

$`\delta S`$ $`=`$ $`{\displaystyle _S}\sqrt{|\stackrel{~}{h}|}[\stackrel{~}{}_{ab}{\displaystyle \frac{1}{2}}\stackrel{~}{}\stackrel{~}{h}_{ab}+{\displaystyle \frac{1}{4}}\lambda ^2\stackrel{~}{h}_{ab}\stackrel{~}{h}^{cd}(\stackrel{~}{D}_c\lambda )(\stackrel{~}{D}_d\lambda ){\displaystyle \frac{1}{2}}\lambda ^2(\stackrel{~}{D}_a\lambda )(\stackrel{~}{D}_b\lambda )`$ (36)
$`+{\displaystyle \frac{1}{4}}\lambda ^2\stackrel{~}{h}_{ab}\stackrel{~}{h}^{cd}(\stackrel{~}{D}_c\omega )(\stackrel{~}{D}_d\omega ){\displaystyle \frac{1}{2}}\lambda ^2(\stackrel{~}{D}_a\omega )(\stackrel{~}{D}_b\omega )]\delta \stackrel{~}{h}^{ab}.`$
The vanishing of (36) gives the Einstein field equation of gravity with sources on $`S`$ as:

$`\stackrel{~}{}_{ab}{\displaystyle \frac{1}{2}}\stackrel{~}{}\stackrel{~}{h}_{ab}`$ $`=`$ $`{\displaystyle \frac{1}{2}}\lambda ^2(\stackrel{~}{D}_a\lambda )(\stackrel{~}{D}_b\lambda ){\displaystyle \frac{1}{4}}\lambda ^2\stackrel{~}{h}_{ab}\stackrel{~}{h}^{cd}(\stackrel{~}{D}_c\lambda )(\stackrel{~}{D}_d\lambda )`$ (37)
$`+{\displaystyle \frac{1}{2}}\lambda ^2(\stackrel{~}{D}_a\omega )(\stackrel{~}{D}_b\omega ){\displaystyle \frac{1}{4}}\lambda ^2\stackrel{~}{h}_{ab}\stackrel{~}{h}^{cd}(\stackrel{~}{D}_c\omega )(\stackrel{~}{D}_d\omega ),`$
or

$$\stackrel{~}{}_{ab}=\frac{1}{2}\lambda ^2(\stackrel{~}{D}_a\lambda )(\stackrel{~}{D}_b\lambda )+\frac{1}{2}\lambda ^2(\stackrel{~}{D}_a\omega )(\stackrel{~}{D}_b\omega ).$$
(38)
Likewise the variation principle gives the equations of motion of the matter fields $`\lambda `$ and $`\omega `$ determined by action (35) respectively as:

$$\stackrel{~}{h}^{ab}\stackrel{~}{D}_a\stackrel{~}{D}_b\lambda =\lambda ^1\stackrel{~}{h}^{ab}(\stackrel{~}{D}_a\lambda )(\stackrel{~}{D}_b\lambda )\lambda ^1\stackrel{~}{h}^{ab}(\stackrel{~}{D}_a\omega )(\stackrel{~}{D}_b\omega ),$$
(39)
and

$$\stackrel{~}{h}^{ab}\stackrel{~}{D}_a\stackrel{~}{D}_b\omega =2\lambda ^1\stackrel{~}{h}^{ab}(\stackrel{~}{D}_a\lambda )(\stackrel{~}{D}_b\omega ).$$
(40)
To compare with Geroch’s work , we make the conformal transformation (25) inversely. From (27), (28) and (30), we have

$`\stackrel{~}{h}^{ab}\stackrel{~}{D}_a\stackrel{~}{D}_b\lambda `$ $`=`$ $`\mathrm{\Omega }^2\left[h^{ab}D_aD_b\lambda h^{ab}(D_a\lambda )(D_b\mathrm{ln}\mathrm{\Omega })\right]`$ (41)
$`=`$ $`\mathrm{\Omega }^2\left[D^2\lambda +{\displaystyle \frac{1}{2}}\lambda ^1h^{ab}(D_a\lambda )(D_b\lambda )\right],`$
and

$`\stackrel{~}{h}^{ab}\stackrel{~}{D}_a\stackrel{~}{D}_b\omega `$ $`=`$ $`\mathrm{\Omega }^2\left[h^{ab}D_aD_b\omega h^{ab}(D_a\omega )(D_b\mathrm{ln}\mathrm{\Omega })\right]`$ (42)
$`=`$ $`\mathrm{\Omega }^2\left[D^2\omega +{\displaystyle \frac{1}{2}}\lambda ^1h^{ab}(D_a\omega )(D_b\lambda )\right].`$
Substituting (41) into (39), one gets equation (13). Substituting (42) into (40), one gets equation (14).

The relation between $`_{ab}`$ and $`\stackrel{~}{}_{ab}`$ reads (see the appendix D of )

$`_{ab}`$ $`=`$ $`\stackrel{~}{}_{ab}D_aD_b\mathrm{ln}\mathrm{\Omega }h_{ab}h^{cd}D_cD_d\mathrm{ln}\mathrm{\Omega }`$ (43)
$`(D_a\mathrm{ln}\mathrm{\Omega })(D_b\mathrm{ln}\mathrm{\Omega })+h_{ab}h^{cd}(D_c\mathrm{ln}\mathrm{\Omega })(D_d\mathrm{ln}\mathrm{\Omega }).`$
Substituting (43) into (38), we obtain

$`_{ab}`$ $`=`$ $`{\displaystyle \frac{1}{4}}\lambda ^2(D_a\lambda )(D_b\lambda )+{\displaystyle \frac{1}{2}}\lambda ^2(D_a\omega )(D_b\omega )`$ (44)
$`+{\displaystyle \frac{1}{2}}\lambda ^1D_aD_b\lambda {\displaystyle \frac{1}{4}}\lambda ^2h_{ab}(D^m\lambda )(D_m\lambda )+{\displaystyle \frac{1}{2}}\lambda ^1h_{ab}D^2\lambda .`$
Using (13), one gets equation (12).

In conclusion, the variations of the symmetry-reduced Hilbert action (21) with respect to Geroch’s variables on $`S`$ cannot lead to the correct reduced field equations. While, the variations of action (35) defined on $`S`$ give the field equations for 3-dimensional gravity coupled to two scalar fields, which are “conformally” equivalent to Geroch’s equations reduced from the vacuum Einstein equation on $`M`$. In this sense, we may regard the action (35) as an alternative action for vacuum Einstein’s equation with a Killing symmetry. Geroch’s equations can thus be obtained from the variation principle.

The above discussion could be generalized to higher dimensional case , and hence might lead some new sight on the mechanism of dimensional reduction.

## Acknowledgments

This work is supported in part by NSFC No. 10205002. H. He and X. Yang would like to acknowledge support from NSFC(10073002). Y. Ma would also like to acknowledge support from Young Teachers Foundation of BNU and YSRF for ROCS, SEM.


text:
# Classical and Quantum Polynomial Reconstruction via Legendre Symbol Evaluation

## 1 Introduction

Let $`p3`$ be a prime number and let $`𝔽_p`$ denote a finite field of $`p`$ elements. We let $`\chi `$ denote the quadratic character of $`𝔽_p`$, or the Legendre symbol modulo $`p`$; see .

Wim van Dam, Sean Hallgren and Lawrence Ip, in the series of papers  have considered the shifted Legendre symbol problem of finding an unknown shift $`s𝔽_p`$ given an oracle $`𝒪`$ which for each $`x𝔽_p`$ computes $`\chi (x+s)`$. They have designed efficient quantum algorithms for the above problem and its generalisation to characters in residue rings.

The problem is of intrinsic interest and also has strong cryptographic motivation; sequences of values of quadratic characters have been considered as sources of cryptographically strong pseudorandom bits .

Here we consider a generalisation of the above problem to polynomials.

For an integer $`d`$ we let $`_d`$ denote the set of square-free monic polynomials $`f(X)𝔽_p[X]`$ of degree $`d`$,

$$_d\stackrel{\mathrm{\Delta }}{=}\{f(X)=X^d+s_{d1}X^{d1}+\mathrm{}+s_1X+s_0s_i𝔽_p\}.$$

We study the problem of finding $`f_d`$, given an oracle $`𝒪_f`$ which returns $`\chi (f(x))`$ for any $`x𝔽_p`$:

$$𝒪_f:x\chi (f(x)).$$

It is obvious that the square-freeness condition is essential because polynomials of the form $`f_1(X)=F(X)G_1(X)^2`$ and $`f_1(X)=F(X)G_2(X)^2`$ with $`F(X),G_1(X),G_2(X)𝔽_p[X]`$ cannot be distinguished by this oracle.

We remark that for the approach of  the orthogonality condition

$$\underset{x𝔽_p}{}\chi \left((x+a)(x+b)\right)=\{\begin{array}{cc}p1,\hfill & \text{if}a=b,\hfill \\ 1,\hfill & \text{if}ab,\hfill \end{array}a,b𝔽_p,$$

appears to be crucial, however, this condition fails for nonlinear polynomials. On the other hand, the Weil bound, see , provides a certain approximate analogue of the above identity:

$$\underset{x𝔽_p}{}\chi \left(g(x)h(x)\right)=\{\begin{array}{cc}p+O(d),\hfill & \text{if}g=h,\hfill \\ O(p^{1/2}),\hfill & \text{if}gh,\hfill \end{array}g,h_d.$$
(1)
Hereafter the implied constants in symbols ‘$`O`$’ may depend on $`d`$ and also, where obvious, on the small positive parameter $`\epsilon `$.

Using this property we demonstrate that the quantum query complexity of recovering $`f`$, given the oracle $`𝒪_f`$, is $`O(d)`$. In contrast, we observe that the classical query complexity is $`\mathrm{\Omega }(d\mathrm{log}p)`$. Furthermore, we give a classical algorithm for reconstructing $`f`$ from $`𝒪_f`$, which appears to be new even in the case of linear polynomials. In fact this algorithm is also based on the Weil bound.

It is clear that the brute force approach leads to a (classical) algorithm of complexity $`O(p^{d+1+\epsilon })`$ which is based on computation and comparison of the $`p`$-dimensional vectors of the values of $`\chi (f(x))`$ and $`\chi (g(x))`$ for all $`x𝔽_p`$ and all $`g_d`$. A naive use of the Weil bound shows that it is enough to compute and compare $`\chi (f(x))`$ and $`\chi (g(x))`$ only for $`1xdp^{1/2}\mathrm{log}^2p`$ which leads to an algorithm of complexity $`O(p^{d+1/2+\epsilon })`$. We show that using the Weil bound in a less obvious way one can obtain an $`O(p^{d+\epsilon })`$ algorithm.

It could be relevant to recall the work of Dima Grigoriev  where a somewhat related question is considered for multivariate polynomials (although the field characteristic is assumed to be small).

It is easy to see that our method applies to multiplicative characters of other orders and to multivariate polynomials as well.

Finally, it is also easy to see that we can allow oracles which return the right value of $`\chi (f(x))`$ only with some fixed probability $`\gamma >1/2`$. We do not pursue this issue in this work, though.

Acknowledgement. We thank Asma Harcharras for several useful discussions.

## 2 Preparation

First of all we recall the Weil bound in its classical form given in Example 12 of Appendix 5 of ; see also Theorem 3 of Chapter 6 in  and Theorem 5.41 and comments to Chapter 5 of .

###### Lemma 1.

For any $`F_d`$ which is not a perfect square of another polynomial, the bound

$$\left|\underset{x𝔽_p}{}\chi \left(F(x)\right)\right|dp^{1/2}$$

holds.

The following statement is also implied by the Weil bound and is essentially Theorem 2 of .

###### Lemma 2.

For any integers $`M<p`$ and any $`F_d`$ which is not a perfect square of another polynomial, the bound

$$\left|\underset{x=1}{\overset{M}{}}\chi (F(x))\right|=O\left(dp^{1/2}\mathrm{log}p\right)$$

holds.

We also need a similar statement for multivariate polynomials.

###### Lemma 3.

For any collection of $`\mathrm{}`$ pairwise distinct linear forms

$$L_\nu (S_0,\mathrm{},S_{d1})=S_0+S_1c_{1\nu }+\mathrm{}+S_{d1}c_{d1,\nu }+c_{d,\nu },\nu =1,\mathrm{},\mathrm{},$$

over $`𝔽_p`$ the bound

$$\left|\underset{s_0,\mathrm{},s_{d1}𝔽_p}{}\chi \left(\underset{\nu =1}{\overset{\mathrm{}}{}}L_\nu (s_0,\mathrm{},s_{d1})\right)\right|2\mathrm{}p^{d1/2}$$

holds.

###### Proof.

We have

$`\left|{\displaystyle \underset{s_0,\mathrm{},s_{d1}𝔽_p}{}}\chi \left({\displaystyle \underset{\nu =1}{\overset{\mathrm{}}{}}}L_\nu (s_0,\mathrm{},s_{d1})\right)\right|`$
$`{\displaystyle \underset{s_1,\mathrm{},s_{d1}𝔽_p}{}}\left|{\displaystyle \underset{s_0𝔽_p}{}}\chi \left({\displaystyle \underset{\nu =1}{\overset{\mathrm{}}{}}}L_\nu (s_0,\mathrm{},s_{d1})\right)\right|.`$
Clearly, there are at most

$$\frac{(\mathrm{}1)(\mathrm{}2)}{2}p^{d2}\mathrm{}2p^{d2}$$

$`d1`$-tuples $`(s_1\mathrm{},s_{d1})𝔽_p`$ for which the values of

$$s_1c_{1\nu }+\mathrm{}+s_{d1}c_{d1,\nu }+c_{d,\nu },\nu =1,\mathrm{},\mathrm{},$$

are pairwise distinct. In this case we estimate the sum over $`s_0`$ by $`p`$. Otherwise we see from Lemma 1 that the sum over $`s_0`$ does not exceed $`\mathrm{}p^{1/2}`$. Therefore

$$\left|\underset{s_0,\mathrm{},s_{d1}𝔽_p}{}\chi \left(\underset{\nu =1}{\overset{\mathrm{}}{}}L_\nu (s_0,\mathrm{},s_{d1})\right)\right|\mathrm{}p^{d1/2}+\mathrm{}2p^{d1}.$$

The claimed bound is trivial for $`\mathrm{}p^{1/2}`$, otherwise we have $`\mathrm{}p^{d1/2}\mathrm{}2p^{d1}`$ and the result follows. ∎

We remark that one can also use stronger bounds based on the famous results of Pierre Deligne , however they do improve our final results.

Our next statement gives an upper bound “on average” for weighted character sums with polynomials.

###### Lemma 4.

For any integers $`Np`$, $`r1`$ and any sequence of real numbers $`\alpha _x`$ with $`|\alpha _x|1`$, $`x=1,\mathrm{},N`$, the bound

$$\underset{g_d}{}\left|\underset{x𝔽_p}{}\alpha _x\chi \left(g(x)\right)\right|^{2r}4rN^{2r}p^{d1/2}+\frac{(2r)!}{r!}N^rp^d$$

holds.

###### Proof.

We have

$`{\displaystyle \underset{g_d}{}}\left|{\displaystyle \underset{x𝔽_p}{}}\alpha _x\chi \left(g(x)\right)\right|^{2r}`$ $`=`$ $`{\displaystyle \underset{g_d}{}}{\displaystyle \underset{x_1,\mathrm{},x_{2r}𝔽_p}{}}{\displaystyle \underset{i=1}{\overset{2r}{}}}\alpha _{x_i}\chi \left(g(x_i)\right)`$
$`=`$ $`{\displaystyle \underset{x_1,\mathrm{},x_{2r}𝔽_p}{}}{\displaystyle \underset{i=1}{\overset{2r}{}}}\alpha _{x_i}{\displaystyle \underset{g_d}{}}\chi \left({\displaystyle \underset{i=1}{\overset{2r}{}}}g(x_i)\right)`$
$`=`$ $`{\displaystyle \underset{x_1,\mathrm{},x_{2r}𝔽_p}{}}\left|{\displaystyle \underset{g_d}{}}\chi \left({\displaystyle \underset{i=1}{\overset{2r}{}}}g(x_i)\right)\right|.`$
Assume that $`x_1,\mathrm{},x_{2r}[1,N]`$ contains $`m`$ pairs of equal elements

$$x_{i_\nu }=x_{j_\nu },\nu =1,\mathrm{},m,$$

and $`l=2r2m`$ pairwise distinct elements $`y_\nu =x_{k_\nu }`$, $`\nu =1,\mathrm{},m`$. Then

$$\underset{g_d}{}\chi \left(\underset{i=1}{\overset{2r}{}}g(x_i)\right)=\underset{g_d}{}\chi \left(\underset{\nu =1}{\overset{l}{}}g(y_\nu )\right).$$

If $`l=0`$, which happens for at most

$$r!\left(\genfrac{}{}{0pt}{}{2r}{r}\right)N^r=\frac{(2r)!}{r!}N^r$$

$`2r`$-tuples $`(x_1,\mathrm{},x_{2r})[1,N]^{2r}`$, then the sum over $`g`$ is obviously equal to $`\left|_d\right|=p^d`$. For $`l>0`$ we derive

$$\underset{g_d}{}\chi \left(\underset{\nu =1}{\overset{l}{}}g(y_\nu )\right)=\underset{s_0,\mathrm{},s_{d1}}{}\chi \left(\underset{\nu =1}{\overset{l}{}}\left(s_0+s_1y_\nu +\mathrm{}+s_{d1}y_\nu ^{d1}+y_\nu ^d\right)\right).$$

It is easy to verify that because $`y_1,\mathrm{},y_l`$ are pairwise distinct elements of $`𝔽_p`$ the linear forms

$$S_0+S_1y_\nu +\mathrm{}+S_{d1}y_\nu ^{d1}+y_\nu ^d,\nu =1,\mathrm{},m,$$

satisfy the conditions of Lemma 3. Thus for at most $`N^{2r}`$ remaining $`2r`$-tuples $`(x_1,\mathrm{},x_{2r})[1,N]^{2r}`$ the sum over $`g`$ is at most $`2lp^{d1/2}4rp^{d1/2}`$

We recall that, using the Horner scheme, for any $`g_d`$ the value of $`g(x)`$ can be computed with $`O(d)`$ arithmetic operations modulo $`p`$. We also recall that polynomial evaluation and computing the quadratic character can be done in polynomial time in the standard RAM model of computation. Explicit and efficient versions of these statements can be found in .

## 3 Classical Algorithm

Here we design an algorithm for the classical model of computation on a RAM computer. The complexity of our algorithm can be improved slightly if one uses fast algorithms for finite field arithmetic and polynomial evaluation, see . In particular, one can replace $`p^\epsilon `$ by a reasonably small power of $`\mathrm{log}p`$ and also improve the term $`d^2`$ in our estimate.

###### Theorem 5.

For any fixed $`\epsilon >0`$ and $`d1`$, given an oracle $`𝒪_f`$ one can find $`f_d`$ in $`O\left(d^2p^{d+\epsilon }\right)`$ binary operations.

###### Proof.

Obviously we can assume that $`p`$ is sufficiently large. Put $`M=dp^{1/2}\mathrm{log}^2p`$ and $`N=d\mathrm{log}^2p`$.

Using the square-freeness condition we conclude that for any $`g_d`$ with $`gf`$ the polynomial $`gf`$ is not a prefect square. Thus from Lemma 2 we see that in this case

$$\underset{x=1}{\overset{M}{}}\chi (g(x)f(x))=O(M/\mathrm{log}p)$$

while for $`g=f`$ this sum is at least $`Md`$. Using the Horner scheme, for any any $`g_d`$ the value of $`g(x)`$ can be computed with $`O(d)`$ arithmetic operations modulo $`p`$. Thus for any polynomial $`g_d`$ the above sum can be evaluated and the identity $`g=f`$ can be verified in $`O(d^2p^{1/2+\epsilon })`$ binary operations. We now show that in fact for all, except at most $`O(p^{d1/2}\mathrm{log}p)`$ polynomials $`g_d`$ one can verify the identity $`g=f`$ in $`O(dN\mathrm{log}^2p)`$ binary operations. It is enough to show that that the inequality

$$\left|\underset{x=1}{\overset{N}{}}\chi (g(x)f(x))\right|Nd$$
(2)
is possible for at most $`O(p^{d1/2}\mathrm{log}p)`$ polynomials $`g_d`$. Using Lemma 4 with $`\alpha _x=\chi (f(x))`$, we see that the number $`T`$ of polynomials $`g_d`$ with (2), for any integer $`r1`$, satisfies the inequality

$$T(Nd)^{2r}4rN^{2r}p^{d1/2}+\frac{(2r)!}{r!}N^rp^d.$$

Let $`r=\mathrm{log}p`$. We have

$$(Nd)^{2r}N^{2r}(1d/N)^{2r}N^{2r}/2$$

for sufficiently large $`p`$. Therefore

$$T8rp^{d1/2}+2\frac{(2r)!}{r!}N^rp^d8rp^{d1/2}+2(2r)^rN^rp^d.$$

Taking into account that $`(2r)^rN^r=(2r/N)^rp^{1/2}`$ for our choice of $`N`$ and $`r`$, and sufficiently large $`p`$, we obtain the desired statement. ∎

## 4 Quantum Query Complexity

As above, we consider the problem of recovering a polynomial $`f`$ from an oracle $`𝒪_f:x\chi (f(x))`$. An easy counting argument shows that the classical query complexity is $`\mathrm{\Omega }(d\mathrm{log}p)`$ (it is in fact $`\mathrm{\Theta }(d\mathrm{log}p)`$): see, for example, van Dam’s article , for an analogous argument. We begin by showing that the quantum query complexity of this problem is at most $`O(d)`$. We refer the reader to accounts by Nielson and Chuang  and Kitaev  for a discussion of quantum computation and quantum algorithms. In particular, we need the notion of positive operator valued measurement (POVM) (see, e.g., , for a discussion which matches our notation below).

Recall that a POVM $`P`$ on Hilbert space $``$ is a set $`𝒜`$ and a family $`\{\vartheta _aa𝒜\}`$ of positive semidefinite operators on $``$ with the property that

$$\underset{a𝒜}{}\vartheta _a=\iota ,$$

where $`\iota `$ denotes the identity operator. The result of the measurement $`P`$ on the state $`\mathrm{\Psi }`$ is the probability distribution on $`𝒜`$ where $`a𝒜`$ is observed with probability $`\vartheta _a\mathrm{\Psi },\mathrm{\Psi }`$. Note that $`\vartheta _a\mathrm{\Psi },\mathrm{\Psi }0`$, as $`\vartheta _\alpha `$ is positive semidefinite, and that

$$\underset{a𝒜}{}\vartheta _a\mathrm{\Psi },\mathrm{\Psi }=\underset{a𝒜}{}\vartheta _a\mathrm{\Psi },\mathrm{\Psi }=\iota \mathrm{\Psi },\mathrm{\Psi }=\mathrm{\Psi }^2=1.$$

Note, also, that in the special case when $`\vartheta _a=\gamma \pi `$ for a projection $`\pi `$ and a scalar $`\gamma [0,1]`$, $`\vartheta _a\mathrm{\Psi },\mathrm{\Psi }=\gamma \pi \mathrm{\Psi }^2`$.

###### Theorem 6.

Let $`f`$ be a polynomial in $`_d`$. If $`dp^{1/2\epsilon }`$ for some fixed $`\epsilon >0`$ then there exists a quantum algorithm which, after $`O(d)`$ quantum queries to $`𝒪_f`$, produces a state for which there is a POVM that determines $`f`$ with probability at least $`1+O(p^1)`$.

###### Proof.

Let us put $`k=2(d+1)\epsilon ^1`$. For a prime $`p`$, let $`𝒢`$ denote a $`p`$-dimensional Hilbert space with an orthonormal basis $`\{|zz_p\}`$. Initially, by applying the Fourier transform to a delta state, we arrive at the uniform superposition

$$\mathrm{{\rm Y}}\stackrel{\mathrm{\Delta }}{=}\frac{1}{\sqrt{p}}\underset{x𝔽_p}{}|x𝒢$$

which is used to query the oracle $`O_f`$. Let $`\stackrel{~}{\chi }:𝔽_p\{\pm 1\}`$ be the function

$$\stackrel{~}{\chi }(x)=\{\begin{array}{cc}\chi (x)\hfill & \text{if}x0,\hfill \\ 1\hfill & \text{if}x=0.\hfill \end{array}$$

We can certainly assume that in fact we are given an oracle $`\stackrel{~}{𝒪_f}`$ with $`\stackrel{~}{𝒪_f}(x)=\stackrel{~}{\chi }(f(x))`$. Then the result of the query may be computed into the phases by controlled phase shift yielding the state

$$\mathrm{\Psi }_f\stackrel{\mathrm{\Delta }}{=}\frac{1}{\sqrt{p}}\underset{x𝔽_p}{}\stackrel{~}{\chi }(f(x))|x.$$

Repeating the process independently $`k1`$ times yields the tensor product state

$$\mathrm{\Psi }_{f,k}\stackrel{\mathrm{\Delta }}{=}\frac{1}{p^{k/2}}\underset{𝐱𝔽_p^k}{}\left(\underset{i=1}{\overset{k}{}}\stackrel{~}{\chi }(f(x_i))\right)|𝐱𝒢^k$$

where $`𝐱=(x_1,\mathrm{},x_k)`$,

$$𝒢^k\stackrel{\mathrm{\Delta }}{=}\underset{k}{\underset{}{𝒢\mathrm{}𝒢}},$$

and $`|𝐱\stackrel{\mathrm{\Delta }}{=}|x_1\mathrm{}|x_k`$. In general, we let $`\mathrm{\Psi }_{g,k}`$ denote the state that would have arisen at this point had we started with the polynomial $`g_d`$. Observe that for $`g_d`$, $`\mathrm{\Psi }_{g,k},\mathrm{\Psi }_{g,k}=1`$ and, furthermore, that for distinct $`g,h_d`$,

$`\left|\mathrm{\Psi }_{g,k},\mathrm{\Psi }_{h,k}\right|`$ $`=`$ $`{\displaystyle \frac{1}{p^k}}\left|{\displaystyle \underset{𝐱𝔽_p^k}{}}{\displaystyle \underset{i=1}{\overset{k}{}}}\stackrel{~}{\chi }(g(x_i))\stackrel{~}{\chi }(h(x_i))\right|`$
$`=`$ $`{\displaystyle \frac{1}{p^k}}{\displaystyle \underset{i=1}{\overset{k}{}}}\left|{\displaystyle \underset{z𝔽_p}{}}\stackrel{~}{\chi }(g(z))\stackrel{~}{\chi }(h(z))\right|.`$
To bound this, we focus on the inner quantity

$$\sigma _{2d}\stackrel{\mathrm{\Delta }}{=}\underset{\begin{array}{c}g,h_d\\ gh\end{array}}{\mathrm{max}}\left|\underset{z𝔽_p}{}\stackrel{~}{\chi }(g(z))\stackrel{~}{\chi }(h(z))\right|.$$

For a polynomial $`g𝔽_p[X]`$, let $`𝒱(g)=\{x𝔽_pg(x)=0\}`$. Recall that $`𝒱(gh)=𝒱(g)𝒱(h)`$ and that for a nonzero univariate polynomial $`g`$, $`\left|𝒱(g)\right|\mathrm{deg}(g)`$. Considering that $`\stackrel{~}{\chi }(f(x))=\chi (f(x))`$ for $`x𝒱(f)`$, we bound $`\sigma _{2d}`$ as follows:

$`\sigma _{2d}`$ $`=`$ $`\underset{\begin{array}{c}g,h_d\\ gh\end{array}}{\mathrm{max}}\left|{\displaystyle \underset{z𝔽_p\backslash 𝒱(gh)}{}}\chi (g(z))\chi (h(z))+{\displaystyle \underset{z𝒱(gh)}{}}\stackrel{~}{\chi }(g(z))\stackrel{~}{\chi }(h(z))\right|`$
$``$ $`\underset{\begin{array}{c}g,h_d\\ gh\end{array}}{\mathrm{max}}\left(\left|{\displaystyle \underset{z𝔽_p\backslash 𝒱(gh)}{}}\chi (gh(z))\right|+\left|𝒱(gh)\right|\right)`$
$``$ $`\underset{\begin{array}{c}g,h_d\\ gh\end{array}}{\mathrm{max}}\left|{\displaystyle \underset{z𝔽_p}{}}\chi (gh(z))\right|+2d.`$
Note now that for two distinct elements $`g,h_d`$, the product $`gh`$ cannot be a perfect square and from Lemma 1 we conclude that

$$\sigma _{2d}\underset{g_{2d}}{\mathrm{max}}\left|\underset{z𝔽_p}{}\chi (g(z))\right|+2ddp^{1/2}+2d2dp^{1/2}$$
(3)
provided that $`p>3`$ (otherwise the result is trivial). Hence for distinct $`g,h_d`$ we have

$$\left|\mathrm{\Psi }_{g,k},\mathrm{\Psi }_{h,k}\right|\sigma _{2d}^kp^k.$$
(4)
Now we show that there is a POVM that identifies the polynomial $`f`$ with probability $`1+O(p^1)`$. For each $`g_d`$, let $`\pi _{g,k}`$ be the projection operator onto the subspace spanned by $`\mathrm{\Psi }_{g,k}`$. As each $`\pi _{g,k}`$ is a projection operator, it is positive semidefinite, and we now show that for some $`0<\alpha <1`$ with $`\alpha =1+O(p^1)`$, there is a decomposition of the identity operator $`\iota `$ of the form

$$\iota =\rho +\underset{g_d}{}\alpha \pi _{g,k}$$

where $`\rho `$ and all $`\pi _{g,k}`$ are positive semidefinite operators on $`𝒢^k`$. Note that if $`\mathrm{\Psi }_{f,k}`$ is measured according to this POVM, the “correct” index $`f,k`$ is observed with probability $`\alpha `$.

So define $`\rho =\iota _{g_d}\alpha \pi _{g,k}`$; we wish to select $`\alpha =1+O(p^1)`$ to insure that $`\rho `$ is positive semidefinite. It suffices to see that for our choice of $`\alpha `$

$$\underset{g_d}{}\alpha \pi _{g,k}<1,$$
(5)
where $`M`$ denotes the operator norm of $`M`$, given by

$$M\stackrel{\mathrm{\Delta }}{=}\underset{\mathrm{\Phi }\mathrm{𝟎}}{sup}\frac{M\mathrm{\Phi }}{\mathrm{\Phi }},$$

this supremum taken over all nonzero vectors $`\mathrm{\Phi }`$. Note that for a unit vector $`\mathrm{\Phi }𝒢^k`$,

$$\underset{g_d}{}\pi _{g,k}\mathrm{\Phi }=\underset{g_d}{}\mathrm{\Phi },\mathrm{\Psi }_{g,k}\mathrm{\Psi }_{g,k}.$$

Let $`_d`$ be a Hilbert space of dimension $`\left|_d\right|`$ with orthonormal basis $`\{\text{B}_gg_d\}`$ and let $`\tau :𝒢^k_d`$ be the linear operator

$$\tau \stackrel{\mathrm{\Delta }}{=}\underset{g_d}{}\mathrm{\Psi }_g\text{B}_g^{};$$

here $`\text{B}_g^{}:_d`$ is the linear functional $`\text{B}_g^{}:\mathrm{\Phi }\mathrm{\Phi },\text{B}_g`$. Then

$$\tau \tau ^{}(\mathrm{\Phi })=\underset{g,h_d}{}\mathrm{\Psi }_g\text{B}_g^{}\left(\text{B}_h\mathrm{\Psi }_h^{}(\mathrm{\Phi })\right)=\underset{g_d}{}\mathrm{\Psi }_g\mathrm{\Psi }_g^{}(\mathrm{\Phi })=\underset{g_d}{}\pi _{g,k}\mathrm{\Phi },$$

so that $`_g\pi _{g,k}=\tau \tau ^{}`$; recalling that $`\tau ^{}^2=\tau \tau ^{}`$, it suffices to suitably upper bound $`\tau ^{}`$. So let $`\mathrm{\Phi }𝒢^k`$ be an element in the span of $`\{\mathrm{\Psi }_{g,k}g_d\}`$ and let $`\mathrm{\Gamma }=_g\gamma _g\text{B}_g_d`$ satisfy $`\tau (\mathrm{\Gamma })=\mathrm{\Phi }`$, which is to say that

$$\mathrm{\Phi }=\underset{g_d}{}\gamma _g\mathrm{\Psi }_{g,k}.$$

Observe that

$$\begin{array}{cc}\hfill \mathrm{\Phi }^2=& \underset{g_d}{}\gamma _g\mathrm{\Psi }_{g,k}^2=\underset{g,h_d}{}\gamma _g\gamma _h^{}\mathrm{\Psi }_{g,k},\mathrm{\Psi }_{h,k}\hfill \\ \hfill =& \underset{g_d}{}\left|\gamma _g\right|^2+O\left(\frac{\sigma _{2d}^k}{p^k}\left(\underset{g_d}{}|\gamma _g|\right)^2\right)\hfill \\ \hfill =& \mathrm{\Gamma }^2+O\left(\frac{\sigma _{2d}^k}{p^k}\left(p^d\mathrm{\Gamma }^2\right)\right)=\left(1+O\left(p^{dk}\sigma _{2d}^k\right)\right)\mathrm{\Gamma }^2,\hfill \end{array}$$
(6)
by the Cauchy–Schwarz inequality. With $`\mathrm{\Phi }`$ expressed in this way, we expand $`\tau ^{}\mathrm{\Phi }`$ as follows:

$$\begin{array}{cc}\hfill \tau ^{}\mathrm{\Phi }^2=& \underset{g_d}{}\left|\mathrm{\Phi },\mathrm{\Psi }_{g,k}\right|^2=\underset{g_d}{}\left|\underset{h_d}{}\gamma _h\mathrm{\Psi }_{h,k},\mathrm{\Psi }_{g,k}\right|^2\hfill \\ \hfill =& \underset{g_d}{}\left|\gamma _g+\underset{hg}{}\gamma _h\mathrm{\Psi }_{h,k},\mathrm{\Psi }_{g,k}\right|^2.\hfill \end{array}$$
(7)
Recalling the inner product bounds of (4), for any $`g_d`$ we must have

$$\left|\underset{\begin{array}{c}h_d\\ gh\end{array}}{}\gamma _h\mathrm{\Psi }_{h,k},\mathrm{\Psi }_{g,k}\right|\sigma _{2d}^kp^k\underset{h_d}{}\left|\gamma _h\right|\sigma _{2d}^kp^k\sqrt{p^d}\mathrm{\Gamma },$$
(8)
again by the Cauchy–Schwarz inequality. Finally, considering that $`\alpha +\beta \alpha +\beta `$, we conclude from (7) and (8) that

$`\tau ^{}\mathrm{\Phi }\mathrm{\Gamma }+p^{dk}\sigma _{2d}^k\mathrm{\Gamma }=\left(1+p^{dk}\sigma _{2d}^k\right)\mathrm{\Gamma }`$
and, from (6), that

$$\tau ^{}\mathrm{\Phi }\left(1+O\left(p^{dk}\sigma _{2d}^k\right)\right)\mathrm{\Phi }.$$

Hence

$$\underset{g_d}{}\pi _{g,k}1+O\left(p^{dk}\sigma _{2d}^k\right).$$

We can assume that $`p>2^{2/\epsilon }`$ and hence that $`2p^{\epsilon /2}`$, because otherwise the result is trivial. Then by (3) we have

$$p^{dk}\sigma _{2d}^kp^{dk}\left(2dp^{1/2}\right)^kp^{dk}p^{(1\epsilon /2)k}=p^{dk\epsilon /2}p^1,$$

because of our choice of $`k`$. We obtain

$$\underset{g_d}{}\pi _{g,k}1+O\left(p^1\right),$$

and are guaranteed that (5) holds (provided that $`p`$ is large enough) for some $`\alpha =1+O(p^1)`$ (recall that $`(1+\delta )^1=1+O(\delta )`$). Thus the above POVM determines $`f`$ with probability $`\alpha =1+O(p^1)`$. ∎