text:
# An alternative to the cosmological ‘concordance model’

## 1 Introduction

Measurements of cosmological parameters with reasonable accuracy are essential both to establish a robust picture of the standard Big Bang cosmology, and to provide insights into the fundamental processes, far beyond the Standard Model of particle physics, which determined its initial conditions. Since the pioneering work of Hubble, it has been recognised that cosmological tests based on astrophysical arguments can suffer from large systematic biases. Clearly one should as far as possible use methods which do not depend explicitly on assumptions concerning complex astrophysical phenomena.

In this respect, measurements of anisotopies in the Cosmic Microwave Background (CMB) appear to offer the most promise for accurate determination of cosmological parameters, thanks to the high control possible on systematic errors. Since the epochal discovery of primordial fluctuations on large angular scales by COBE (Smoot et al. 1992), this field has witnessed a renaissance. The first detections of fluctuations on degree scales (Netterfield et al. 1995; Scott et al. 1996) provided tantalizing evidence for the flatness of the Universe (e.g. Lineweaver et al. 1997). The unambiguous detection of the first and second acoustic peaks in the angular power spectrum (de Bernardis et al. 2000; Hanany et al. 2000; Halverson et al. 2002) has confirmed this result. Taken together with studies of large-scale structure (LSS) in the universe, these observations have also confirmed the overall picture of structure formation through gravitational instability. The recent results obtained by WMAP represent a further major advance in the field. For the first time, measurements of cosmological parameters are being quoted with uncertainties of a few per cent, opening up the anticipated era of ‘precision cosmology’. Our intention here is to examine whether such determinations are in fact robust or depend crucially on underlying assumptions or ‘priors’. Specifically we wish to test whether a cosmological constant, $`\mathrm{\Lambda }`$, is really required by observations of the CMB and LSS, independently of the indications from the SN Ia Hubble diagram. We will do so by confronting Einstein-de Sitter (E-deS) models with the same observations. It turns out that with a different assumption concerning the spectrum of primordial fluctuations generated by inflation, such models can fit the data even better than models with non-zero $`\mathrm{\Lambda }`$.

## 2 What do the $`C_{\mathrm{}}`$ measurements imply?

The physics of passive linear perturbations in the early Universe is well understood and therefore their evolution can be computed accurately (see Hu & Dodelson 2002). This is the basic reason why precise measurements of the angular structure of the imprints left on the CMB by primordial fluctuations can provide accurate information on cosmological parameters. The ingredients necessary to compute the amplitudes of the multipole moments ($`C_{\mathrm{}}`$) specifying the angular power spectrum are both the nature and spectrum of the primordial fluctuations (presumably arising from inflation), as well as specification of the various contents of the universe which contribute to its density and pressure. The imprint of a specific parameter can be direct, through the influence on the dynamics of acoustic oscillations before the epoch of last scattering (as for the baryonic content $`\mathrm{\Omega }_\mathrm{b}`$ for instance), as well as indirect, through the effect on the angular distance to the last scattering surface. A non-zero $`\mathrm{\Lambda }`$ affects the $`C_{\mathrm{}}`$s primarily through the distance effect (Blanchard 1984). There are also more subtle effects, such as the integrated Sachs-Wolfe (ISW) effect which contributes at a much weaker level. However such effects are harder to identify, as they can easily be mimicked by a non-trivial primordial fluctuation spectrum.

The first studies of the generation of density perturbations during inflation established (see Linde 1990) that for the simplest models involving a single ‘inflaton’ field, the spectrum is close to the Harrison-Zel’dovich (H-Z) scale-invariant form, $`P(k)k^n`$ with $`n=1`$, which had been proposed earlier on grounds of simplicity. Thus the H-Z spectrum became a standard input for calculations of CMB anisotropies and the growth of LSS, e.g. in the standard cold dark matter (SCDM) model (Davis et al. 1985). In fact there are significant corrections to a H-Z spectrum even in single-field models, in particular the spectrum steepens logarithmically with increasing $`k`$ (decreasing scale) as the end of inflation is approached. This is usually accomodated by considering a ‘tilted’ spectrum with $`n<1`$, although it should be noted that the index $`n`$ is scale-dependent for any polynomial potential for the inflaton, and is constant only for an exponential potential (power-law inflation). Moreover $`n`$ can be close to, and even exceed, unity if inflation ends not through the steepening of the inflaton potential but, for example, due to the dynamics of a second scalar field (hybrid inflation). In such multi-field models, the spectrum may not even be scale-free since features can be imprinted onto the spectrum, e.g. when the slow-roll evolution of the inflaton is interrupted by other background fields undergoing symmetry-breaking phase transitions (Adams, Ross & Sarkar 1997b).

The expectations for the spectral index $`n(k)`$ in various inflationary models has been reviewed by Lyth & Riotto (1999). Even small departures from scale-invariance can be quite significant for LSS formation. For example after the SCDM model was found by Efstathiou et al. (1992) to be in conflict with the observed power spectrum of galaxy clustering (in being unable to simultaneously reproduce the abundance of rich clusters (quantified by the variance $`\sigma _8`$ in a top-hat sphere of radius $`8h^1`$ Mpc) and the COBE measurement of fluctuations on the scale of $`H_0^13000h^1`$ Mpc), it was noted by White et al. (1995) that invoking a tilted spectrum with $`n0.9`$ could save the model. Interestingly enough, such a spectrum arises from natural supergravity inflation,111Technically ‘natural’ means that the flatness of the potential is protected by a symmetry — here the shift symmetry of a Nambu-Goldstone mode (Freese, Freiman & Olinto 1990). where the leading term in the potential is cubic in the field (Ross & Sarkar 1996; Adams, Ross & Sarkar 1997a). This yields $`n=(N2)/(N+2)`$, where $`N<\mathrm{\hspace{0.33em}57}+\mathrm{ln}(k^1/H_0^1)`$ is the number of e-folds of expansion from the end of inflation, taking the inflationary energy scale to be $`<\mathrm{\hspace{0.33em}10}^{16}`$ GeV as required by the normalization to COBE, and the reheat temperature to be $`<\mathrm{\hspace{0.33em}10}^9`$ GeV to avoid the thermal gravitino problem (see Sarkar 1996). If the inflationary scale is significantly lower (German, Ross & Sarkar 2001) and/or if there was a late epoch of thermal inflation (Lyth & Stewart 1996), then our present Hubble radius may have exited the horizon only $`2030`$ e-folds from the end of inflation. This yields a spectral index as low as $`n0.8`$ on cosmologically observable scales since $`n14/N`$ in this model.

It is thus clear that the primordial spectrum may not have a trivial form and lacking a ‘standard model’ of inflation, it is necessary to consider a wide range of possibilities. Furthermore such complex spectra could potentially confuse cosmological parameter estimation from CMB data (e.g. Kinney 2001). This was explicitly demonstrated by Barriga et al. (2001) using the COBE and BOOMERanG data (de Bernardis et al. 2000) for the case of a primordial spectrum with a step-like feature at a scale $`k0.1h/`$Mpc, as in double inflation (Silk & Turner 1987). In this paper we investigate the flexibility in the determination of cosmological parameters using the much more precise WMAP data, when the usual hypothesis of a single power law spectrum is relaxed. Since the power-law index is related to the slope and curvature of the inflaton potential, it can change suddenly e.g. if the mass of the inflaton changes through its coupling to a background field which undergoes spontaneous symmetry breaking during inflation (Adams et al. 1997b)

The possible detection of a non-zero $`\mathrm{\Lambda }`$ through measurements of the Hubble diagram of distant Type Ia supernovae (Riess et al. 1998; Perlmutter et al. 1999) is among the most significant developments in modern cosmology (see Peebles and Ratra, 2003), and has led to the establishment of the ‘concordance model’ with $`\mathrm{\Omega }_\mathrm{\Lambda }0.7`$ and $`\mathrm{\Omega }_\mathrm{m}0.3`$ (Bahcall et al. 1999). This is quite consistent with the WMAP data for an assumed power-law primordial spectrum; for a spatially flat universe the cosmological parameters are determined to be: $`\mathrm{\Omega }_\mathrm{m}h^2=0.14\pm 0.02`$, $`\mathrm{\Omega }_\mathrm{b}h^2=0.024\pm 0.001`$, $`\mathrm{\Omega }_\nu h^2<0.0076`$, $`h=0.72\pm 0.05`$, $`n=0.99\pm 0.04`$ and $`\tau =0.166_{0.071}^{+0.076}`$ (Spergel et al. 2003). This agreement has led to to the widespread belief that the $`\mathrm{\Lambda }`$CDM concordance model is now established to high accuracy through CMB measurements. However we wish to illustrate that this agreement is crucially dependent on the underlying assumptions concerning the primordial power spectrum and that CMB data do not yet independently require a non-zero $`\mathrm{\Lambda }`$. Before addressing this issue, let us first assess the status of the concordance model.

## 3 Is the concordance model actually concordant?

### 3.1 Concordance with WMAP data

As mentioned already, SCDM with $`\mathrm{\Omega }_\mathrm{m}=1`$, $`h=0.5`$ and $`n=1`$ was found to disagree with the shape of the APM galaxy correlation function (Maddox et al. 1990), as well as the high baryon fraction measured in clusters, which together with the baryon fraction inferred from primordial nucleosynthesis arguments, implied a lower matter density of $`\mathrm{\Omega }_\mathrm{m}0.3`$ in agreement with local dynamical estimates (White et al. 1993). The subsequent measurements of CMB fluctuations on degree scales however required the universe to be spatially flat and ruled out such a low density matter-dominated universe (Lineweaver & Barbosa 1998). Thus the possible detection of cosmic acceleration in the Hubble expansion of distant supernovae, implying a cosmological constant with $`\mathrm{\Omega }_\mathrm{\Lambda }0.7`$, was eagerly seized on as a mean of reconciling the CMB and LSS data. However although this concordance model is consistent with most cosmological observations, its first precision test has come with the WMAP data. The agreement of the concordance model with data as summarised by the WMAP team appears impressive (Spergel et al. 2003). However, there are two facts to keep in mind. First the global $`\chi ^2`$ on the temperature autocorrelation (TT) power spectrum is rather poor — the probability that the model fits the data is only 3%, so strictly speaking the model is rejected at the $`2\sigma `$ confidence level! However given possible remaining systematics effects not yet accounted for, the WMAP team concluded that this should not be considered as a serious problem for the concordance model. Allowing for ‘running’ of the spectral index with scale improves the fit somewhat; the data suggest that $`n>\mathrm{\hspace{0.33em}1}`$ on the largest scales and $`n<\mathrm{\hspace{0.33em}1}`$ on small scales.

There is another aspect of the WMAP data that is even more puzzling, viz. the amplitudes of the low $`C_{\mathrm{}}`$s, particularly the quadrupole, is rather small compared to the expectation in the concordance model where the large cosmological constant should boost the anisotropy on large angles. It is well known that the cosmic variance is high on such large angular scales and that Galactic foreground subtraction introduces further uncertainties. Spergel et al. (2003) concluded, from Monte Carlo realisations following two different methods, that the low signal on large scales cannot be obtained in over 99% of the cases.

However, statistical inferences from the quadrupole amplitude have to be handled with caution. The measured value of $`Q_{\mathrm{rms}}=\sqrt{(5/4\pi )C_2}=8\pm 2\mu \mathrm{K}`$ corresponds to a variance ($`\mathrm{\Delta }T_{\mathrm{}}^2=\mathrm{}(\mathrm{}+1)C_{\mathrm{}}/2\pi `$) of $`\mathrm{\Delta }T_2^2=154\pm 70\mu \mathrm{K}^2`$ (Bennett et al. 2003), so one might conclude that e.g. an expected $`\mathrm{\Delta }T_2^2=350\mu \mathrm{K}^2`$ is discrepant by about $`2\sigma `$, which would be at the 95% c.l. for a gaussian distribution. In properly evaluating this probability however one should take into account the foreground removal technique and its uncertainty, in order to determine the likelihood distribution. Such a distribution is likely to be non-Gaussian and it is therefore possible that the estimation of the goodness-of-fit for the concordance model might be significantly improved in this outlying region. If one instead considers the best-fit concordance model derived by Spergel et al. (2003) to be the true description of the CMB sky, the probability of observing a low quadrupole can be directly estimated. The log–likelihood of $`C_{\mathrm{}}^{\mathrm{theo}}`$ can be well approximated by (Bartlett et al. 2000):

$$2\mathrm{ln}(C_{\mathrm{}}^{\mathrm{theo}})=5\times f_{\mathrm{sky}}\times \left[\mathrm{ln}\left(\frac{C_{\mathrm{}}+\mathrm{}}{C_{\mathrm{}}^{\mathrm{theo}}+\mathrm{}}\right)\frac{C_{\mathrm{}}+\mathrm{}}{C_{\mathrm{}}^{\mathrm{theo}}+\mathrm{}}\right]$$

where the noise is $`\mathrm{}`$ ($`=3.4\mu \mathrm{K}^2`$ for $`\mathrm{}=2`$ as quoted in the WMAP data release222http://lambda.gsfc.nasa.gov), the sky coverage is $`f_{\mathrm{sky}}=85\%`$, $`C_{\mathrm{}}`$ is the measured amplitude and $`C_{\mathrm{}}^{\mathrm{theo}}`$ is the value of the best-fit $`\mathrm{\Lambda }`$CDM model ($`1204\mu \mathrm{K}^2`$ for $`\mathrm{}=2`$). Given this approximation, one can retrieve the probability distribution of $`C_2`$ and thus estimate the chance of observing a low value, following Douspis et al. (2003). For $`Q_{\mathrm{rms}}=8\mu \mathrm{K}`$ this is 4.6%, in agreement with the estimate of Tegmark, de Oliveira-Costa & Hamilton (2003) by a different method (varying the cut CMB sky and considering the best running spectral index model). This indicates that the quadrupole is an outlier at most at the 2$`\sigma `$ level (see also Gaztañaga et al. 2003, Efstathiou 2003b).

### 3.2 Concordance with astronomical data

As discussed already, the concordance model has been built up over time in order to match observations, thus its a posteriori agreement with much of the LSS data is not a test. Of course as the quality of data improves the model will be further tested, although the number of free parameters provides some room for adjustment.

Interestingly enough, WMAP has thrown new light on the masses of galaxy clusters and therefore on the inferred baryon fraction which, it had been argued (White et al. 1993), indicates a low matter density universe. There has been some controversy in recent years concerning the actual masses of X-ray emitting clusters, which are determined by two different methods. One is the application of hydrostatic equilibrium, while the second uses mass-temperature relationships derived from numerical simulations. Systematic differences between the two methods are significant (Markevitch 1998; Roussel, Sadat & Blanchard 2000) and this translates into an appreciable difference in the derived value of $`\sigma _8`$ (Reiprich & Böhringer 2002; Seljak 2002). Furthermore similar differences arise from the use of different theoretical mass functions. The Sheth & Tormen (1999) expression is recognised as providing a satisfactory fit to the mass function obtained from numerical simulations. Using this for an $`\mathrm{\Omega }_\mathrm{m}=0.3`$ universe, one finds $`\sigma _8=0.86`$ corresponding to the high mass estimates from numerical simulations, and $`\sigma _8=0.68`$ for the low mass estimates from hydrostatic equilibrium (Vauclair et al. 2003). Clearly the WMAP measurement of $`\sigma _8=0.9\pm 0.1`$ (Spergel et al. 2003) favours the high mass estimates. The implied baryon fraction (including stars) in clusters is then rather low, slightly below 9% (for $`h=0.7`$). This conflicts with the universal baryon fraction of 15% required for the best concordance model fit to the acoustic peaks! We note that this discrepancy disappears for $`\sigma _80.7`$, which is about a $`2\sigma `$ deviation from the WMAP determination.

## 4 Acceptable Einstein-de Sitter models

Let us now examine whether it is possible to obtain an acceptable CMB power spectrum in an E-deS universe. Clearly to do this we have to deviate from the assumptions of the $`\mathrm{\Lambda }`$CDM concordance model regarding the primordial power spectrum. Indeed the WMAP team (Peiris et al. 2003) have already noted that the model fit can be significantly improved (particularly to the outliers at $`\mathrm{}=`$ 22, 40 and 200) by allowing for oscillations in the primordial spectrum (Adams, Cresswell & Easther 2001) such as might be induced by phase transitions occuring during inflation (Adams, Ross & Sarkar 1987b). However if we are not to introduce too many new parameters, the simplest modification that can be introduced is perhaps to consider a change in the slope of the spectrum at a particular scale. It is important in this respect to notice that the first and second acoustic peaks span a rather limited range of scales, $`\mathrm{}150600`$, while the rising part of the first peak covers a much bigger range, $`\mathrm{}2200`$. Without advocating any specific scenario, it is interesting to examine how a model with different power law indices for the primordial fluctuations in these two regions compares to the observational data. We therefore focus on models with

$$P(k)=\{\begin{array}{cc}A_1k^{n_1}\hfill & \mathrm{for}k<k_1,\hfill \\ A_2k^{n_2}\hfill & \mathrm{for}kk_1,\hfill \end{array}$$

with a continuity condition ($`A_1k_1^{n_1}=A_2k_1^{n_2}`$). We calculate the CMB power spectrum using the CAMB code (Lewis et al. 2000) and use the WMAP likelihood code (Verde et al. 2003) to determine the quality of the fit.

As we are primarily interested in examining the possible constraints on the cosmological constant, we have restricted our search to models with $`\mathrm{\Omega }_\mathrm{\Lambda }=0`$ but allow a reasonable range for other cosmological parameters (including the optical depth $`\tau `$ to last scattering). The best model we find has $`h=0.46`$, $`\omega _\mathrm{b}=\mathrm{\Omega }_\mathrm{b}h^2=0.019`$, $`\tau =0.16`$, $`k_1=0.0096`$ Mpc-1, $`n_1=1.015`$, $`n_2=0.806`$. As seen in Fig. 1 the calculated power spectrum does very well in fitting the WMAP data and other observations at high $`\mathrm{}`$. Interestingly enough a preferred scale of $`k0.01`$ Mpc-1 was also found by Mukherjee & Wang (2003) in attempting to reconstruct the primordial spectrum in the context of a $`\mathrm{\Lambda }`$CDM model (although Bridle et al. (2003) did not detect this using a different method). We wish to emphasise that inspite of having one additional parameter, our model has a better $`\chi ^2`$ (on the scalar $`C_{\mathrm{}}`$) than the best concordance model, because of its lower amplitude at low $`l`$ (the $`\chi ^2`$ of the TE spectrum being identical). In particular, the mean quadrupole $`C_2`$ has an amplitude of $`844\mu \mathrm{K}^2`$, which has a 13% probability of yielding $`Q_{\mathrm{rms}}=8\mu \mathrm{K}`$. The reason of course is that E-deS models do not produce ISW effects as high as in flat models with low matter density and a large cosmological constant. This is arguably a simpler way to accomodate the observed low signal at $`l<\mathrm{\hspace{0.33em}20}`$, than to invoke new physics (e.g. Spergel et al. 2003; Uzan, Kirchner & Ellis 2003a; Efstathiou 2003a, Contaldi et al. 2003, Cline, Crotty & Lesgourgues 2003).

### 4.1 Why this E-deS model is in difficulty

It might appear that our E-deS model with $`\mathrm{\Omega }_\mathrm{m}=1`$, $`\mathrm{\Omega }_\mathrm{\Lambda }=0`$ and $`h=0.46`$ must be in conflict with a number of astronomical observations. However, several of these observations which in fact support the $`\mathrm{\Lambda }`$CDM concordance model have been questioned. For example, the observed mass-to-light function from galaxies to superclusters yields $`\mathrm{\Omega }_\mathrm{m}=0.16\pm 0.05`$ (Bahcall et al. 2000) but such observations are mostly local and possibly untypical. The abundance of high redshift X-ray selected clusters, a global test rather than a local one, systematically leads to high values of $`\mathrm{\Omega }_\mathrm{m}`$, well above the best WMAP value (Henry 1997; Sadat, Blanchard & Oukbir 1998; Viana & Liddle 1999; Borgani et al. 1999; Reichart et al. 1999; Blanchard et al. 2000). This points in the same direction as the observed absence of any large-scale correlations between the COBE map of the CMB and the HEAO-1 map of the 2–8 keV X-ray background which provides an interesting upper limit of $`\mathrm{\Omega }_\mathrm{\Lambda }<0.6`$ at 95% c.l. (Boughn, Crittenden & Koehrsen 2002).333Very recently, Boughn & Crittenden (2003) claim to have detected a large-scale correlation between the WMAP and HEAO-1 maps at the $`2.42.8\sigma `$ level, which is surprising since the WMAP and COBE maps are quite consistent. They also find a correlation between WMAP and the NVSS survey of radio galaxies at the $`1.82.3\sigma `$ level. Nolta et al. (2003) confirm the latter finding and reject a $`\mathrm{\Lambda }=0`$ universe at 95% c.l. However Myers et al. (2003) have found significant contamination of the WMAP data by NVSS sources which can account for the observed correlation. Fosalba & Gaztañaga (2003) also find a correlation, twice as strong as the expected signal, between WMAP and the APM galaxy survey.

The only direct evidence so far for a cosmological constant comes from the Hubble diagram of distant Type Ia supernovae, a method which relies on the standard candle hypothesis and on empirical corrections to the observed peak magnitudes on the basis of the observed decay times. Such corrections are essential for reducing the scatter in the data sufficiently so as to allow significant cosmological deductions. However there are systematic differences in the corrections made for the same objects by the two groups (Leibundgut 2000) which raises legitimate concerns about their validity. Moreover, the distant SN Ia appear to be significantly bluer than the nearby sample, suggesting that the derived reddening may have been underestimated (Leibundgut 2001). Rowan-Robinson (2002) has argued that when extinction and the luminosity–decay time relation are treated in a self-consistent way, the significance of the evidence for positive $`\mathrm{\Lambda }`$ is much reduced.

A Hubble constant of $`H_0=46`$ km/s/Mpc would seem to be completely inconsistent with the Hubble Key Project (HKP) determination of $`72\pm 8`$ km/s/Mpc (Freedman et al. 2001). However there are some details of this work which might merit reexamination:

1. Rowan-Robinson (2003) finds that if a more sophisticated local flow model is used than that of Mould et al. (2000), there is a reduction of about 2 km/s/Mpc in $`H_0`$.
2. The method of combining the data used by Freedman et al. (2001), viz. estimating $`H_0`$ by different methods and then combining the results, does make the outcome somewhat vulnerable to Malmquist bias. Rowan-Robinson (2003) finds that this can also result in overestimation of $`H_0`$ by about 2 km/s/Mpc.
3. Between the summary paper of Mould et al. (2000) and that of Freedman et al. (2001), a change in the assumed I-band period-luminosity relation resulted in an increase of the extinction values in the Cepheid program galaxies, and hence in an average reduction in the distance scale of 4%. This was almost exactly cancelled out by correction for the effects of metallicity on Cepheid distances, of about the same magnitude in the opposite direction. However it is possible that these effects do not quite cancel, e.g. if the extinction in the program galaxies has been overestimated and/or the correction for the effects of metallicity have been underestimated. It would be highly desirable to extend observations of the Key Project Cepheids into the infrared to assess these effects.
4. The assumed extinction in the LMC may be slightly on the low side compared with estimates for hot stars in the LMC by Zaritsky (1999).
5. Finally, it would be highly desirable to confirm the assumed distance to the LMC, preferably by direct geometric methods.

All these effects are likely to be small, but it is possible that they may combine in the same direction to significantly reduce $`H_0`$.

It is interesting that methods which are largely independent of the LMC and Cepheid distance scales, do tend to give significantly lower values for $`H_0`$. For instance, Sunyaev-Zeldovitch (S-Z) distances to 41 clusters give a value of $`54_3^{+4}`$ km/s/Mpc in an E-deS universe (Reese et al. 2002); furthermore any clumping of the X-ray emitting gas would lower the actual value by up to $`20\%`$. The 4 simple gravitational lens systems (PG1115+080, SBS1520+530, B1600+434, HE2149-2745) for which time delays have been reliably measured yield $`H_0=48\pm 3`$ km/s/Mpc if the lenses are assumed to have isothermal halos of dark matter, while it would be $`71\pm 3`$ km/s/Mpc if the lenses instead had constant $`M/L`$ (Kochanek & Schechter (2003). However Koopmans et al. (2003) have recently obtained $`H_0=75_6^{+7}`$ km/s/Mpc from a detailed reanalysis of the system B1608+656, significantly higher than their previous estimate of $`59\pm 2`$ km/s/Mpc for this system (Fassnacht et al. 2002). We note that Parodi et al. (2000) find $`H_0=59\pm 4`$ km/s/Mpc using SN Ia (see also Branch 2000).

Fig 2 shows a compilation of distances to Type Ia supernovae, S-Z clusters and gravitationally lensed systems with $`z>0.05`$. The best-fit flat model (not shown) has $`\mathrm{\Omega }_0=0.9\pm 0.5`$ and $`H_0=60\pm 11`$ km/s/Mpc. Models with $`\mathrm{\Omega }_\mathrm{m}=1`$, $`H_0=60`$ km/s/Mpc and $`\mathrm{\Omega }_\mathrm{m}=0.3`$, $`\mathrm{\Omega }_\mathrm{\Lambda }=0.7`$, $`H_0=72`$ km/s/Mpc are shown (solid lines); both fit the data well. The model with $`\mathrm{\Omega }_\mathrm{m}=1`$, $`H_0=46`$ km/s/Mpc (broken line) is clearly a less good fit to the data.

In conclusion a Hubble constant in the range 55-65 km/s/Mpc seems entirely plausible at the present time. The value we require, 46 km/s/Mpc, is still below this range, but perhaps only by $`12\sigma `$. We believe the present paper provides a powerful stimulus for further work on the cosmological distance scale.

There is however one observational constraint that our E-deS model fails to reproduce quite badly, viz. the amplitude of matter fluctuations on cluster scales ($`8h^1`$ Mpc). This model has an amplitude of $`\sigma _81.1`$, which is much higher than required to match the local abundance of clusters and weak lensing measurements. The discrepancy is at least at the 5 $`\sigma `$ level, even taking into account the scatter in the determinations from different analyses: current estimates for $`\sigma _8`$ from clusters and from weak lensing range from $`0.45`$ to $`0.6`$ (for $`\mathrm{\Omega }_\mathrm{m}=1`$). This is consistent with measurements of peculiar velocity fields, e.g. the redshift-space distortion seen in 2dFGRS on scales $`<10h^1`$ Mpc yields $`\beta \mathrm{\Omega }_\mathrm{m}^{0.6}/b=0.55\pm 0.1`$ for an E-deS universe, where $`b1/\sigma _8`$ is the linear bias parameter (Hawkins et al. 2002). 444Their best-fit is $`\beta =0.49\pm 0.09`$ at the mean redshift of the survey: $`z0.17`$. Combined with the estimate of $`b=1.04\pm 0.11`$ from analysis of the bispectrum of 2dFGRS on scales $`k(0.10.5)h/`$Mpc (Verde et al. 2002), this yields $`\mathrm{\Omega }_\mathrm{m}(z=0)=0.23\pm 0.09`$. However, this constraint on the bias, obtained by an elaborate statistical analysis, may not be reliable if the biasing process is more complicated than envisaged in this work. As WMAP cannot probe very small scales, one might imagine that further modification of the primordial spectrum could remove this discrepancy. For example Barriga et al. (2001) invoked a ‘step’ in the spectrum at $`k0.1`$/h Mpc to decrease $`\sigma _8`$ significantly below the corresponding value for a H-Z spectrum, and thus accounted for the observed slow evolution of the number density of rich clusters with redshift. However, an examination of the CMB power spectrum normalized to $`\sigma _8=1`$ for various power law indices (see Fig. 3) reveals that the implied amplitude on the scale $`l900`$ is essentially constant. Thus the recent measurements on this scale by ground-based CMB experiments (Pearson et al. (2002); Kuo et al. (2002); Ruhl et al. (2002); Grainge et al. (2003)), if taken to be reliable, cannot be matched if $`\sigma _8`$ is made significantly smaller than unity by modifying the primordial spectrum. We conclude therefore that an E-deS model with CDM alone cannot accommodate both data sets, independently of the shape of the primordial spectrum.

### 4.2 Modifying the matter content

In this last section, we examine whether the above discrepancy can be avoided if we do not restrict ourselves to pure CDM models but modify the matter content. Specifically, we now have evidence that all the known neutrinos have masses which are rather close to each other, with $`\mathrm{\Delta }m^27\times 10^5\mathrm{eV}^2`$ for the electron and muon neutrinos and $`\mathrm{\Delta }m^23\times 10^3\mathrm{eV}^2`$ for the muon and tau neutrinos, indicated respectively by the oscillation interpretation of the Solar and atmospheric neutrino anomalies (see Gonzalez-Garcia & Nir 2003). Moreover the direct kinematic limit on the neutrino mass from the Mainz and Troitsk tritium $`\beta `$-decay experiments is 2.2 eV (see Weinheimer 2002). The addition of massive neutrinos is known to damp the power spectrum on scales smaller than their free-streaming length $`d_\nu =1230(m_\nu /\mathrm{eV})^1`$ Mpc, and thus to lower $`\sigma _8`$ (see Primack & Gross 2000). We have therefore introduced 3 quasi-degenerate neutrinos of mass 0.8 eV each and find the following model provides an acceptable fit: $`h=0.46`$, $`\omega _\mathrm{b}=\mathrm{\Omega }_\mathrm{b}h^2=0.021`$, $`\tau =0.10`$, $`k_1=0.009`$ Mpc-1, $`n_1=0.98`$, $`n_2=0.87`$, $`\mathrm{\Omega }_\nu =0.12`$. The amplitude on clusters scales is perhaps still too high at $`\sigma _8=0.64`$, but it is certainly premature to rule out this model for this reason alone.

In a second model we introduce a small amount of ‘quintessence’ with $`w_\mathrm{Q}=0`$. Such possibility arises naturally as an attractor solution of a simple exponential potential: $`V=M_p^4\mathrm{exp}(\lambda \mathrm{\Phi }/Mp)`$ which is well motivated theoretically (Ratra & Peebles 1988; Wetterich 1988) and has been argued to give good agreement with observations with $`\mathrm{\Omega }_\mathrm{Q}0.1`$ (Ferreira & Joyce 1997; 1998). Indeed, we find that the power at small scales is suppressed in this model compared to pure cold dark matter, yielding an acceptable fit to the CMB and LSS data (with $`\sigma _8=0.5`$) for the following parameters: $`h=0.45`$, $`\omega _b=\mathrm{\Omega }_bh^2=0.019`$, $`\tau =0.10`$, $`k_1=0.012`$ Mpc-1, $`n_1=1.00`$, $`n_2=0.90`$, $`\mathrm{\Omega }_\mathrm{Q}=0.12`$.

For both cases, the best-fit optical depth to last scattering $`\tau 0.1`$ is significantly smaller than the value of $`\tau =0.17`$ obtained in the WMAP team’s fit to the temperature-polarization cross-correlation (TE) spectrum (Kogut et al. 2003). Nevertheless the predicted TE spectra for our E-deS models are in reasonable agreement with the WMAP data, although the predicted polarization autocorrelation (EE) spectra differ (see Fig. 5). The baryonic content $`\omega _\mathrm{b}=\mathrm{\Omega }_\mathrm{b}h^2=0.019`$ is at the upper end of the range suggested by considerations of primordial nucleosynthesis (Fields & Sarkar 2002). The cluster baryon fraction expected in these two models is $`f_\mathrm{b}1012\%`$ (keeping in mind that the ‘dark energy’ component does not cluster on these scales); although low this is consistent with recent estimates (Sadat & Blanchard 2001). It is also necessary to examine the agreement of these models with LSS data, in particular the power spectrum obtained from studies of galaxy clustering and the Lyman-$`\alpha `$ forest. For this purpose we adopt a bias parameter given by $`b=1/\sigma _8`$. As seen in Fig. 6, both models are then in agreement with the APM power spectrum (Baugh & Efstathiou 1993; Peacock 1997), the 2dFGRS power spectrum (Percival et al. 2001; Tegmark, Hamilton & Xu 2002) and the Ly$`\alpha `$ forest (matter) power spectrum (Croft et al. 2002) which has been used recently to set interesting constraints on models of large scale structure (Douspis, Blanchard & Silk 2001). The model with massive neutrinos provides a particularly good description of LSS data. Such a model has already been considered by Elgarøy & Lahav (2003) as providing a good fit to the 2dFGRS data, but maintaining a constant power law index on large scales as they do, then gives a very poor fit to the WMAP data. We emphasise that although our model is apparently in conflict with the upper bound of $`\mathrm{\Omega }_\nu h^2<0.0076`$ quoted by Spergel et al. (2003), this latter bound was obtained under more restrictive asumptions (in particular adopting ‘priors’ on the bias parameter, matter density and Hubble parameter), hence is not sufficiently conservative.

## 5 Further tests

It is important to devise means of breaking the ‘$`\mathrm{\Omega }_\mathrm{m}\sigma _8`$ degeneracy’ and establish reliably whether we do live in an low matter density universe, and also to devise further tests for $`\mathrm{\Lambda }`$ independently of the SN Ia Hubble diagram.

Attempts to determine $`\mathrm{\Omega }_\mathrm{m}`$ from measurements of peculiar velocity fields have relied on constraining the bias parameter by examination of the statistical properties of the galaxy distribution (e.g. Verde et al. 2002). More detailed examination of the clustering properties of different galaxy populations in the ongoing Sloan digital sky survey will sharpen this test further (Szapudi et al. 2002).

Another approach is based on measurement of the mean relative peculiar velocity of galaxy pairs as a function of their separation (Juskiewicz et al. 2000); a recent application of this method yields $`\mathrm{\Omega }_\mathrm{m}=0.29_{0.09}^{+0.15}`$, $`\sigma _8=0.95_{0.11}^{+0.20}`$ without any prior assumptions concerning the primordial fluctuations or cosmological parameters (Feldman et al. 2003). However the inclusion of a component of hot dark matter, as in our model, will affect peculiar velocities on the relevant small scales, so simulations incorporating non-linear effects are necessary to assess the robustness of this test (J. Silk, private communication).

Measurements of ‘cosmic shear’ induced through gravitational lensing offer yet another possible way to determine the matter density and bias separately (see Van Waerbeke et al. 2002). Again several ongoing and proposed large area surveys should allow adequate control of systematic uncertainties and enable cosmological parameters to be obtained without prior assumptions.

A complementary approach is to seek direct evidence in the CMB for the presence of a cosmological constant. As mentioned earlier, the absence of the expected ISW effect at large angular scales in the WMAP data has been disappointing in this respect, but might be regarded as a statistical fluctuation. The expected ISW correlations with other tracers of large-scale structure are being sought but results are not definitive as yet. The power spectrum of the E-mode polarization offers an additional way to distinguish among models. As seen in Fig. 5, the nominal EE spectra for our E-deS models differ significantly from that of the concordance model since the best-fit value of $`\tau `$ is smaller. However the value of $`\tau `$ for our E-deS models can be raised to be closer to the WMAP value of 0.17 (thin lines in Fig. 5) without significantly affecting the $`C_l`$ or $`P(k)`$ fits. Hopefully analysis of further data from WMAP, as well as other CMB experiments, can distinguish between these possibilities. The most stable difference between our E-deS models and the $`\mathrm{\Lambda }`$CDM concordance model is in fact the matter power spectrum shape in the range $`k(0.010.03)h`$/Mpc, which galaxy surveys may be able to investigate, provided the possible biasing is reliably understood on these scales (Durrer et al. 2003).

## 6 Discussion

We have shown that when the assumption of a single power law for the primordial fluctuation spectrum is relaxed, an Einstein-de Sitter model with zero $`\mathrm{\Lambda }`$ can fit the CMB data as well as if not better than the best $`\mathrm{\Lambda }`$CDM concordance model. This is a clear and direct indication that the CMB data alone does not require the introduction of a non-zero cosmological constant. However a model with only cold dark matter cannot simultaneously match both the CMB data and the amplitude of matter fluctuations as indicated by clusters, peculiar velocity fields and weak lensing measurements. We have shown further that acceptable Einstein-de Sitter models are indeed possible provided they comprise a small amount of a ‘dark energy’ component which does not cluster on small scales, such as relic neutrinos with masses of order eV or a pressureless quintessence field. These models have a low, but as we have argued, not unimaginable, Hubble constant. Moreover this provides further motivation for laboratory experiments sensitive to eV-scale neutrino masses, since a detection would provide crucial input for cosmology.

Given the need to suppress the amplitude of fluctuations on cluster scales in any model, we conclude that extant CMB and LSS data actually imply the existence of a dark component beyond cold dark matter, with a density contribution of about 10% of the critical density and an equation of state corresponding to conventional pressureless matter. Such models reproduce quite well the observed properties of the large scale structure of of universe without further adjustment.

The essential conclusion is that an Einstein-de Sitter universe is not yet ruled out, as seems to be generally believed. Although there is indeed conflict with some astronomical observations, we have argued that these data are not established beyond reasonable doubt. Given the severe coincidence problem associated with a classical cosmological constant as well as the profound implications of de Sitter space-time for fundamental physics (e.g. Witten 2001, Banks & Dine 2001, Dyson, Kleban & Susskind 2002), it is surely worth investigating these issues further.

###### Acknowledgements.

We thank the Referee for her critical and helpful comments. We also acknowledge useful discussions with David Spergel, Alain Riazuelo, Joe Silk and Ludovic Van Waerbeke. M.D. is supported by a CMBNet fellowship.


format: text

text:
# Quasi-Optimal Arithmetic for Quaternion Polynomials

## 1 Motivation

Nearly 40 years after Cooley and Tukey , their Fast Fourier Transform (FFT) has provided numerous applications, among them

* fast multiplication of polynomials

> Given the coefficients of $`p,q[X]`$, $`n:=\mathrm{deg}(p)+\mathrm{deg}(q)`$;
> determine the coefficients of $`pq`$.

which, based on FFT, can be performed in $`𝒪(n\mathrm{log}n)`$ and
* their multi-evaluation

> Given the coefficients of $`p[X]`$, $`\mathrm{deg}(p)<n`$, and $`x_1,\mathrm{},x_n`$;
> determine the values $`p(x_1),\mathrm{},p(x_n)`$.

allowing algorithmic solution within $`𝒪(n\mathrm{log}^2n)`$.

Observe in both cases the significant improvement over naive $`𝒪(n^2)`$ approaches. These two examples illustrate a larger class of operations called *Fast Polynomial Arithmetic*  with, again, a vast number of applications . For instance, Gerasoulis employed fast polynomial arithmetic to drastically accelerate $`N`$-Body Simulations in 2D , and Pan, Reif, and Tate did so in 3D . Since systems with up to $`N=10^5`$ objects arise quite frequently when simulating biochemical processes, the theoretical benefit of asymptotic growth $`𝒪(N\mathrm{polylog}N)`$ over $`𝒪(N^2)`$ pays off in practice as well.

Technically speaking in order to calculate, for each of the $`N`$ particles, the total force it experiences due to the $`N1`$ others, Gerasoulis identifies the plane $`^2`$ with $``$; he thus turns Coulomb’s potential into a rational complex function which, by means of fast polynomial multiplication and multi-evaluation, can be handled efficiently.  on the other hand exploit fast multi-evaluation of polynomials to *approximate* the total forces in $`^3`$. Whether 3D forces can be obtained *exactly* within subquadratic time is still an open question. One promising approach proceeds by identifying, similarly to , $`^3`$ with (a subspace of) Hamilton’s four-dimensional algebra of Quaternions $``$ and there applying fast polynomial arithmetic of some kind or another. In fact the mere notion of a polynomial becomes ambiguous when passing from fields $`𝕂=`$ and $`𝕂=`$ to the skew-field $`𝕂=`$. We consider three common approaches to define polynomials (Section 2) and, for each induced kind of quaternion polynomials, present quasi-optimal algorithms supporting according arithmetic operations (Section 3).

## 2 Quaternions

The algebra $``$ of quaternions was discovered in 1843 by W.R. Hamilton in an attempt to extend multiplication of ’vectors’ from $`^2`$ to $`^3`$. In fact, $``$ is a *four*-dimensional real vector space whose canonical basis $`1,i,j,k`$ satisfies the non-commutative multiplicative rule

$$i^2=j^2=k^2=ijk=1,ij=ji=k\text{+ cyclic interchange}$$
(1)
which, by means of associative and distribute laws, is extended to arbitrary quaternions. $``$ is easily verified to form a *skew-field*, that is, any non-zero element $`a`$ possesses a unique two-sided multiplicative inverse $`a^1`$. In fact it holds $`a^1=\overline{a}/|a|^2`$ where $`\overline{a}:=\mathrm{Re}(a)i\mathrm{Im}_i(a)j\mathrm{Im}_j(a)k\mathrm{Im}_k(a)`$ is the analogue of complex conjugation and $`|a|:=\sqrt{a\overline{a}}=\sqrt{\overline{a}a}_+`$ the *norm* satisfying $`|ab|=|a||b|`$. The *center* of $``$ is $``$; in other words: real numbers and only they multiplicatively commute with any quaternion. For further details, please refer to the excellent111wrongly condemned in Chapter XXI, p.245 of  Chapter 7 of . Theorem 17.32 in  determines the (multiplicative algebraic) complexity of quaternion multiplication;  does so similarly for quaternion inversion and division. However rather than on single quaternions, our focus shall lie on asymptotics w.r.t. $`n`$, the quaternion polynomials’ degree, tending to infinity.

It is well-known that commutativity *has* to be abandoned in order to turn $`^4`$ into some sort of a field; in fact, Frobenius’ Theorem states that $``$ is the *only* associative division algebra beyond $`^2`$. On the other hand to the author’s best knowledge, all notions of polynomials either require the ground ring $``$ to satisfy commutativity or — such as *skew polynomial rings*, see p.262, Chapter 16 of  — they lack evaluation homomorphisms. The latter means that any polynomial $`p=p(X)[X]`$ should naturally induce a mapping $`\widehat{p}:`$, $`x\widehat{p}(x)`$ such that for all $`a,x`$:

$$\widehat{X}(x)=x,\widehat{a}(x)=a,\widehat{pq}(x)=\widehat{p}(x)\widehat{q}(x),\text{and }\widehat{p+q}(x)=\widehat{p}(x)+\widehat{q}(x).$$

The distant goal is to find a notion of quaternion polynomials which naturally generalizes from real or complex ones *and* supports efficient arithmetic by means of, say, quasi-linear time algorithms. Our contribution considers three such definitions for $`𝕂[X]`$ which, in case $`𝕂`$ is an infinite field, are equivalent to the usual notion. In case $`𝕂=`$ however they disagree and give rise to different arithmetic operations. We focus on Multiplication and Multi-Evaluation and present in Section 3, for each of the three notions, according quasi-optimal algorithms.

### 2.1 Polynomials as Ring of Mappings

The idea pursued in this subsection is that the following objects should be considered polynomials:

* the identity mapping $`X:=\mathrm{id}:𝕂𝕂`$, $`xx`$,
* any constant mapping $`\widehat{a}:𝕂𝕂`$, $`xa`$ for $`a𝕂`$
* the sum of two polynomials and
* the product of two polynomials.

Formally, let the set $`𝕂^𝕂`$ of mappings $`f:𝕂𝕂`$ inherit the ring structure of $`𝕂`$ by defining pointwise $`f+g:xf(x)+g(x)`$, $`fg:xf(x)g(x)`$. Then embed $`𝕂`$ into this ring by identifying $`a𝕂`$ with the constant mapping $`𝕂xa𝕂`$.

###### Definition 1

$`𝕂_1[X]`$ is the smallest subring of $`𝕂^𝕂`$ containing $`X`$ and the constant mappings $`𝕂`$. For instance,

$$a_1+Xa_2XXa_3+a_4XXXa_5𝕂_1[X],a_1,\mathrm{},a_5𝕂\text{ fixed.}$$
(2)
$`𝕂_1[X]`$ is closed not only under addition and multiplication but also under composition, i.e., $`f+g,fg,fg𝕂_1[X]`$ for $`f,g𝕂_1[X]`$. Since, in the commutative case, any such polynomial can be brought to the form

$$_{\mathrm{}=0}^{n1}a_{\mathrm{}}X^{\mathrm{}},n,a_{\mathrm{}}𝕂,$$
(3)
Definition 1 there obviously coincides with the classical notion of polynomial rings $`[X]`$ and $`[X]`$. For the skew-field $`𝕂=`$ of quaternions, the structure of $`_1[X]`$ is not so clear at first sight:

* $`aXXa`$ unless $`a`$ i.e., the form (3) in general cannot be attained any more.
* Uniqueness becomes an issue, since

$$XXiXi+iXXiXiXiXXXiXXi$$
(4)
vanishes identically \[5, top of p.201\];
in particular, a polynomial can have many more roots than its ’degree’ suggests.
* The fundamental theorem of algebra is violated as well: $`iXXi+1`$ has no root in $``$ \[5, p.205\].
* Lagrange-style polynomials $`P_m`$ to pairwise distinct points $`x_0,\mathrm{},x_{n1}`$, e.g.,

$$\left(\underset{\begin{array}{c}\mathrm{}=0\\ \mathrm{}m\end{array}}{\overset{n1}{}}(Xx_{\mathrm{}})\right)\left(\underset{\begin{array}{c}\mathrm{}=0\\ \mathrm{}m\end{array}}{\overset{n1}{}}(x_mx_{\mathrm{}})\right)^1\text{or}\underset{\begin{array}{c}\mathrm{}=0\\ \mathrm{}m\end{array}}{\overset{n1}{}}\left((x_mx_{\mathrm{}})^1(Xx_{\mathrm{}})\right)$$

both interpolate $`P_m(x_m)=1`$, $`P_m(x_{\mathrm{}})=0`$, $`m\mathrm{}`$ but obviously lack uniqueness.
* There is no polynomial division with remainder; e.g. $`XiXmodX^2=\mathrm{?}\mathrm{?}\mathrm{?}`$

On the other hand we present in Subsection 3.2 algorithms for addition, multiplication, and multi-evaluation of this kind of quaternion polynomials of degree $`n`$ in time $`𝒪(n^4\mathrm{polylog}n)`$. Since it turns out that generic $`p_1[X]`$ have roughly $`n^4`$ free coefficients, the running time is thus quasi-optimal. Finally, a fast randomized zero-tester for expressions like (2) and (4) comes out easily.

### 2.2 Polynomials as Sequence of Coefficients

Since the above Definition 1 thus does not *allow* for quaternion polynomial arithmetic as fast as quasi-linear time, the present subsection proposes another approach. The idea is to identify polynomials with their coefficients. Recall that for $`p=_{\mathrm{}=0}^{n1}a_{\mathrm{}}X^{\mathrm{}}`$ and $`q=_{\mathrm{}=0}^{m1}b_{\mathrm{}}X^{\mathrm{}}`$ over a commutative field $`𝕂`$, the finite sequence of coefficients $`\stackrel{}{c}=(c_{\mathrm{}})𝕂^{}`$ of $`pq`$ is given in terms of $`\stackrel{}{a}=(a_{\mathrm{}})𝕂^{}`$ and $`\stackrel{}{b}=(b_{\mathrm{}})𝕂^{}`$ by the convolution product

$$\stackrel{}{c}=\stackrel{}{a}\stackrel{}{b},c_{\mathrm{}}=_{t=0}^{\mathrm{}}a_tb_\mathrm{}t,\mathrm{}=0,\mathrm{},n+m1$$
(5)
with the implicit agreement that $`a_{\mathrm{}}=0`$ for $`\mathrm{}n`$ and $`b_{\mathrm{}}=0`$ for $`\mathrm{}m`$.

###### Definition 2

$`𝕂_2[X]`$ is the set $`𝕂^{}`$ of finite sequences of quaternions, equipped with componentwise addition and convolution product according to (5). Let $`X`$ denote the special sequence $`(0,1,0,\mathrm{},0)𝕂^{}`$.

It is easy to see that this turns $`𝕂_2[X]`$ into a ring which, in case of fields $`𝕂`$ of characteristic zero, again coincides with the usual ring of polynomials $`𝕂[X]`$. Here the classical results assert that arithmetic operations `+` and `*` can be performed within time $`𝒪(n)`$ and $`𝒪(n\mathrm{log}n)`$, respectively. In Subsection 3.1, we show that the same is possible in the non-commutative ring $`_2[X]`$. Dealing with $`n`$ coefficients, this is trivially quasi-optimal.

Unfortunately fast arithmetic for $`_2[X]`$ does not include multi-evaluation, simply because evaluation (substituting $`X`$ for some $`x`$) makes no sense here: One might be tempted to identify $`\stackrel{}{a}^{}`$ with the formal expression $`_{\mathrm{}}a_{\mathrm{}}X^{\mathrm{}}`$ and $`\stackrel{}{b}`$ with $`_{\mathrm{}}b_{\mathrm{}}X^{\mathrm{}}`$, but then $`\stackrel{}{c}:=\stackrel{}{a}\stackrel{}{b}`$ does not agree with

$$\left(a_{\mathrm{}}X^{\mathrm{}}\right)\left(b_{\mathrm{}}X^{\mathrm{}}\right)=_{\mathrm{}}_{t=0}^{\mathrm{}}a_t\underset{b_\mathrm{}tX^t}{\underset{}{X^tb_\mathrm{}t}}X^\mathrm{}t_{\mathrm{}}c_{\mathrm{}}X^{\mathrm{}}$$

because of non-commutativity.

The next subsection considers expressions of the form $`a_{\mathrm{}}X^{\mathrm{}}`$ as further notion of quaternion polynomials. These lack closure under multiplication; on the other hand, there, multi-evaluation does make sense and turns out to have classical complexity $`𝒪(n\mathrm{log}^2n)`$.

### 2.3 One-sided Polynomials

Roughly speaking, one aims at a subclass of $`_1[X]`$ where polynomials have only $`𝒪(n)`$ rather than $`\mathrm{\Theta }(n^4)`$ coefficients and thus give a chance for operations with quasi-linear complexity.

###### Definition 3

Let $`X:𝕂𝕂`$ denote the identity mapping and consider this class of mappings on $`𝕂`$: $`𝕂_3[X]:=\{_{\mathrm{}=0}^na_{\mathrm{}}X^{\mathrm{}}:n_0,a_{\mathrm{}}𝕂\}𝕂^𝕂`$.
The degree of $`p𝕂_3[X]`$ is $`\mathrm{deg}(p)=\underset{a_{\mathrm{}}0}{\mathrm{max}}\mathrm{}`$, $`\mathrm{deg}(0):=1`$.

Again this coincides for fields $`𝕂`$ of characteristic zero with the usual notions. For the skew-field of quaternions, the restriction compared to (2) applies that all coefficients $`a_{\mathrm{}}`$ must be on the *left* of powers $`X^{\mathrm{}}`$. Unfortunately, this prevents $`_3[X]`$ from being closed under multiplication; fortunately, $`_3[X]`$ has the following other nice properties:
being a real vector space;    supports interpolation;        allows fast multi-evaluation;    a fundamental theorem of algebra holds;    polynomials satisfy uniqueness. Formally:

###### Lemma 1

Consider $`p:=_{\mathrm{}=0}^{n1}a_{\mathrm{}}X^{\mathrm{}}`$, $`a_{\mathrm{}}`$.

1. Suppose $`p(x)=0`$ for all $`x`$. Then $`a_{\mathrm{}}=0`$ for all $`\mathrm{}`$.
2. Nevertheless even $`p0`$ may have an infinite (and in particular unbounded in terms of $`p`$’s degree) number of roots.
3. If $`a_{\mathrm{}}0`$ for some $`\mathrm{}1`$, then $`p`$ has at least one root.

###### Proof

1. Follows from Lemma 2b) by choosing $`n\mathrm{deg}(p)`$ and pairwise distinct $`x_0,\mathrm{},x_{n1}`$ since then, no three are automorphically equivalent.
2. All quaternions $`x=i\beta +j\gamma +k\delta `$ with $`\beta ,\gamma ,\delta `$ and $`\beta ^2+\gamma ^2+\delta ^2=1`$ are easily verified zeros of $`p:=X^2+1`$.
3. Cf. p.205 in  or see, e.g., .

Interpolation is the question of existence and uniqueness, given $`x_0,\mathrm{},x_{n1}`$ and $`y_0,\mathrm{},y_{n1}𝕂`$, of a polynomial $`p𝕂[X]`$ with degree at most $`n1`$ satisfying $`p(x_{\mathrm{}})=y_{\mathrm{}}`$ for all $`\mathrm{}=0,\mathrm{},n1`$. In the commutative case, both is asserted for pairwise distinct $`x_{\mathrm{}}`$. Over quaternions, this condition does not suffice neither for uniqueness (Lemma 1b) nor for existence:

###### Example 1

No $`p=aX^2+bX+c_3[X]`$ satisfies $`p(i)=0=p(j)`$, $`p(k)=1`$.

It turns out that here an additional condition has to be imposed which, in the commutative case, holds trivially for distinct $`x_{\mathrm{}}`$, namely being automorphically inequivalent.

###### Definition 4

Call $`a,b`$ automorphically equivalent iff $`a=ubu^1`$ for some non-zero $`u`$, that is, iff $`\mathrm{Re}(a)=\mathrm{Re}(b)|\mathrm{Im}(a)|=|\mathrm{Im}(b)|`$ where $`\mathrm{Im}(a):=i\mathrm{Im}_i(a)+j\mathrm{Im}_j(a)+k\mathrm{Im}_k(a)`$.

This obviously *is* an equivalence relation (reflexivity, symmetry, transitivity). The name comes from the fact that mappings $`xuxu^1`$ are exactly the $``$-algebra automorphisms of $``$; cf. \[5, bottom of p.215\]. The central result of  now says:

###### Lemma 2

For $`x_0,\mathrm{},x_{n1}`$, the following are equivalent

1. To any $`y_0,\mathrm{},y_{n1}`$, there exists $`p_3[X]`$ of $`\mathrm{deg}(p)<n`$ such that $`p(x_{\mathrm{}})=y_{\mathrm{}}`$, $`\mathrm{}=0,\mathrm{},n1`$.
2. Whenever $`p=_{\mathrm{}=0}^{n1}a_{\mathrm{}}X^{\mathrm{}}`$ and $`q=_{\mathrm{}=0}^{n1}b_{\mathrm{}}X^{\mathrm{}}`$ satisfy $`p(x_{\mathrm{}})=q(x_{\mathrm{}})`$ for $`\mathrm{}=0,\mathrm{},n1`$, it follows $`a_{\mathrm{}}=b_{\mathrm{}}`$.
3. The Quaternion Vandermonde Matrix $`V:=(x_{\mathrm{}}^m)_{\mathrm{},m=0,..,n1}`$ is invertible.
4. Its Double Determinant $`V`$ does not vanish.
5. The $`x_{\mathrm{}}`$ are pairwise distinct and no three of them are automorphically equivalent.

Concluding this subsection, $`_3[X]`$ has (unfortunately apart from closure under multiplication) several nice structural properties. In 3.3 we will furthermore show that it supports multi-evaluation in time $`𝒪(n\mathrm{log}^2n)`$. More generally, our algorithm applies to polynomials $`_3^1[X]:=\{_{\mathrm{}=0}^{n1}a_{\mathrm{}}X^{\mathrm{}}b_{\mathrm{}}:n_0,a_{\mathrm{}},b_{\mathrm{}}\}`$ with coefficients to *both* sides of each monomial $`X^{\mathrm{}}`$. This generalized notion has the advantage of yielding not only an $``$-vector space but a two-sided $``$-vector space.

## 3 Algorithms

### 3.1 Convolution of Quaternion Sequences

Beginning with the simplest case of $`_2[X]`$:
Let $`n`$. Given $`\stackrel{}{a}=(a_0,a_1,\mathrm{},a_{n1})^n`$ and $`\stackrel{}{b}=(b_0,b_1,\mathrm{},b_{m1})^m`$, one can compute their convolution according to (5) from 16 real convolutions222In fact, 4 complex convolutions suffice; but asymptotically, that gains nothing. and 12 additions of real sequences within time $`𝒪(n\mathrm{log}n)`$. Indeed write componentwise

$$\stackrel{}{a}=\mathrm{Re}(\stackrel{}{a})+i\mathrm{Im}_i(\stackrel{}{a})+j\mathrm{Im}_j(\stackrel{}{a})+k\mathrm{Im}_k(\stackrel{}{a}),\stackrel{}{b}=\mathrm{Re}(\stackrel{}{b})+i\mathrm{Im}_i(\stackrel{}{b})+j\mathrm{Im}_j(\stackrel{}{b})+k\mathrm{Im}_k(\stackrel{}{b})$$

and exploit $``$-bilinearity of quaternion convolution.

### 3.2 Ring of Quaternion Mappings

The central point of this subsection is the identification of $`_1[X]`$ with the four-fold Cartesian product of four-variate real polynomials $`^4[X_0,X_1,X_2,X_3]`$. Formally consider, for $`f:`$, the quadruple $`\stackrel{~}{f}`$ of four-variate real functions defined by

$$\begin{array}{cccc}\hfill \stackrel{~}{f}_0(X_0,..,X_3):=& \mathrm{Re}\left(p\left(X_0+iX_1+jX_2+kX_3\right)\right)\hfill & \hfill \stackrel{~}{f}_1(X_0,..,X_3):=& \mathrm{Im}_i\left(p\left(X_0+iX_1+jX_2+kX_3\right)\right)\hfill \\ \hfill \stackrel{~}{f}_2(X_0,..,X_3):=& \mathrm{Im}_j\left(p\left(X_0+iX_1+jX_2+kX_3\right)\right)\hfill & \hfill \stackrel{~}{f}_3(X_0,..,X_3):=& \mathrm{Im}_k\left(p\left(X_0+iX_1+jX_2+kX_3\right)\right)\hfill \end{array}$$
(6)
and multiplication among such mappings $`\stackrel{~}{f},\stackrel{~}{g}:^4^4`$ given pointwise by

$$\begin{array}{c}(\stackrel{~}{f}_0,\stackrel{~}{f}_1,\stackrel{~}{f}_2,\stackrel{~}{f}_3)(\stackrel{~}{g}_0,\stackrel{~}{g}_1,\stackrel{~}{g}_2,\stackrel{~}{g}_3):=\text{(}\text{6}\frac{1}{2}\text{)}\hfill \\ \hfill (\stackrel{~}{f}_0\stackrel{~}{g}_0\stackrel{~}{f}_1\stackrel{~}{g}_1\stackrel{~}{f}_2\stackrel{~}{g}_2\stackrel{~}{f}_3\stackrel{~}{g}_3,\stackrel{~}{f}_0\stackrel{~}{g}_1+\stackrel{~}{f}_1\stackrel{~}{g}_0+\stackrel{~}{f}_2\stackrel{~}{g}_3\stackrel{~}{f}_3\stackrel{~}{g}_2,\stackrel{~}{f}_0\stackrel{~}{g}_2+\stackrel{~}{f}_2\stackrel{~}{g}_0+\stackrel{~}{f}_3\stackrel{~}{g}_1\stackrel{~}{f}_1\stackrel{~}{g}_3,\stackrel{~}{f}_0\stackrel{~}{g}_3+\stackrel{~}{f}_3\stackrel{~}{g}_0+\stackrel{~}{f}_1\stackrel{~}{g}_2\stackrel{~}{f}_2\stackrel{~}{g}_1)\end{array}$$
(7)
In that way, calculations in $`_1[X]`$ can obviously be as well performed in $`\stackrel{4}{}[X_0,..,X_3]`$. This allows for application of classical algorithms for multivariate polynomials over commutative fields. But before, we need a notion of *degree* on $`_1[X]`$:

###### Definition 5

For a commutative multi-variate polynomial, let $`\mathrm{deg}`$ denotes its *total* degree; e.g., $`\mathrm{deg}(x^2y^3)=5`$, $`\mathrm{deg}(0)=\mathrm{}`$. The degree $`\mathrm{deg}(q)`$ of a quaternion polynomial $`q_1[X]`$ is half the total degree of the real four-variate polynomial $`\stackrel{~}{f}_0^2+\mathrm{}+\stackrel{~}{f}_3^2`$ with $`\stackrel{~}{f}_0,\mathrm{},\stackrel{~}{f}_3`$ according to (6).

Rather than the total degree, one might as well have considered the maximum one $`\mathrm{deg}(x^2y^3):=3`$ since, for 4 variables, they differ by at most a constant factor. However we shall later exploit the equality $`\mathrm{deg}(pq)\mathbf{=}\mathrm{deg}(p)+\mathrm{deg}(q)`$ valid for the first whereas for the latter in general only the *in*equality $`\mathrm{deg}(pq)\mathbf{}\mathrm{deg}(p)+\mathrm{deg}(q)`$ holds. In fact, this nice property carries over to the degree of quaternion polynomials:

###### Lemma 3

The degree $`\mathrm{deg}(p)`$ of $`p_1[X]`$ is always integral. Furthermore it holds $`\mathrm{deg}(pq)=\mathrm{deg}(p)+\mathrm{deg}(q)`$.

Now recall the following classical results on four-variate polynomials:

###### Lemma 4

1. Given (the coefficients of) $`p,q[X_0,\mathrm{},X_3]`$, the (coefficients of the) product $`pq`$ can be computed in time $`𝒪(n^4\mathrm{log}n)`$ where $`n:=\mathrm{deg}(pq)=\mathrm{deg}(p)+\mathrm{deg}(q)`$.
2. Given $`p[X_0,\mathrm{},X_3]`$ of degree $`n`$, one can compute within $`𝒪(n^4\mathrm{log}n)`$ steps the coefficients of $`p\left(T(X_0,\mathrm{},X_3)^{}+\stackrel{}{y}\right)[X_0,\mathrm{},X_3]`$, that is, perform on $`p`$ an affine variable substitution given by $`T^{4\times 4}`$ and $`\stackrel{}{y}^4`$.
3. A given polynomial $`p[X_0,\mathrm{},X_3]`$ of degree $`n:=\mathrm{deg}(p)`$ can be evaluated on all $`n^4`$ points of a 4-dimensional complex grid $`G:=A_0\times A_1\times A_2\times A_3`$ such that $`A_{\mathrm{}}`$, $`|A_{\mathrm{}}|=n`$, within time $`𝒪(n^4\mathrm{log}^2n)`$.
4. The same holds for the regular affine image $`G^{}=TG+\stackrel{}{y}`$ of such a grid, i.e.,

$$G^{}=\{T\stackrel{}{x}+\stackrel{}{y}:\stackrel{}{x}=(x_0,\mathrm{},x_3)^{}G\},T^{4\times 4}\text{ regular},\stackrel{}{y}^4.$$
5. Let $`p[X_0,\mathrm{},X_3]`$ be non-zero, $`n\mathrm{deg}(p)`$. Fix arbitrary $`A`$ of size $`|A|2n`$. Then, for $`(x_0,\mathrm{},x_3)A^4`$ chosen uniformly at random, the probability of $`p(x_0,\mathrm{},x_3)=0`$ is strictly less than $`\frac{1}{2}`$.

###### Proof

1. Reduction to the univariate case by means of Kronecker’s embedding: cf. Equation (8.3) on p.62 of  for $`m:=4`$; dealing with the complex field $``$ rather than an arbitrary ring $``$ of coefficients, the $`\mathrm{log}\mathrm{log}`$-factor may be omitted.
2. Folklore. A proof had to be removed from the final version due to space limitations.
3. Cf. Equation (8.5) and the one below on p.63 of  for $`m:=4`$, $`c:=n`$.
4. follows from b). It is not known whether multi-evaluation is feasible on *arbitrarily* placed $`n^4`$ points within time $`𝒪(n^4\mathrm{polylog}n)`$.
5. Cf. Subsection 12.1 in .

One could of course identify in a similar way complex univariate polynomials $`p[Z]`$ with tuples $`p_0,p_1[X,Y]`$ of real bivariate polynomials. However the thus obtained running times of $`𝒪(n^2\mathrm{polylog}n)`$ thus obtained for $`[Z]`$ are strikingly suboptimal, basically because *not every* tuple of real bivariate polynomials corresponds to a complex univariate polynomial. For instance, $`z\mathrm{Re}(z)`$ is well-known not only to be no complex polynomial but to even violate Riemann-Jacoby’s equations of complex differentiability. Surprisingly for quaternion polynomials, the situation is very different:

###### Lemma 5

$`\mathrm{Re}(X)=\frac{1}{4}(XiXijXjkXk)_1[X]`$. More generally, every quadruple of real four-variate polynomials corresponds to a quaternion polynomial.

The generic quaternion polynomial of degree $`n`$ thus has $`\mathrm{\Theta }(n^4)`$ free coefficients. Lemmas 4 and 5 together yield

###### Theorem 3.1

1. Multiplication of two quaternion polynomials $`p,q_1[X]`$ is possible in time $`𝒪(n^4\mathrm{log}n)`$ where $`n:=\mathrm{deg}(pq)=\mathrm{deg}(p)+\mathrm{deg}(q)`$.
2. Multi-evaluation of $`p`$ at $`x_0,\mathrm{},x_{n1}`$ can be done within $`𝒪(n^4\mathrm{log}^2n)`$, $`n:=\mathrm{deg}(p)`$.
3. Within the same time, multi-evaluation is even feasible at as many as $`n^4`$ points $`x`$, provided they lie on a (possibly affinely transformed) $`n^4`$-grid $`G`$.

The above complexities are optimal up to the (poly-)logarithmic factor.

Theorem 3.1 presumes the polynomial(s) to be given as (coefficients of four) real four-variate polynomials. But how fast can one convert input in more practical format like (2) or (4) to that form? By means of fast multiplication of *several* polynomials, this can be done efficiently as well:

###### Theorem 3.2

1. The (ordered!) product $`_{\mathrm{}=1}^mp_{\mathrm{}}`$ of $`m`$ quaternion polynomials $`p_{\mathrm{}}_1[X]`$, each given as quadruple of real four-variate polynomials, can be computed within $`𝒪(n^4\mathrm{log}n\mathrm{log}m)`$ where $`n=_{\mathrm{}}\mathrm{deg}(p_{\mathrm{}})`$ denotes the result’s degree.
2. An algebraic expression $`E`$ over quaternions, i.e., composed from $`+`$, $``$, $``$, constants $`a`$, and the quaternion variable $`X`$ — but *without* powers like $`X^{99}`$ nor brackets! — can be converted into the quadruple of real four-variate polynomials according to (6) within time $`𝒪(N^4\mathrm{log}^2N)`$ where $`N=|E|`$ denotes the input string’s length.

The above conversion yields a deterministic $`𝒪(N^4\mathrm{log}^2N)`$-test for deciding whether a given quaternion expression like (4) represents the zero polynomial. When satisfied with a *randomized* test, the same can be achieved much faster:
Theorem 3.2 (continued)

1. Given $`\epsilon >0`$ and an expression $`E`$ of length $`N=|E|`$, composed from ”`+`”, ”`-`”, ” $``$”, constants $`a`$, the quaternion variable $`X`$, and possibly brackets ”`(`”, ”`)`”; then one can test with one-sided error probability at most $`\epsilon `$ whether $`E`$ represents the zero-polynomial within time $`𝒪(N\mathrm{log}\frac{1}{\epsilon })`$.

###### Proof

1. Standard divide-and-conquer w.r.t. $`m`$ similar to Corollary 2.15 in .
2. Lacking brackets, the input string $`E`$ necessarily has the form

$`E=E_1\pm E_2\pm \mathrm{}\pm E_M`$

where $`E_{\mathrm{}}`$ describes a product $`P_{\mathrm{}}`$ of quaternion constants (degree 0) and the indeterminate $`X`$ (degree 1). Since obviously $`\mathrm{deg}(P_{\mathrm{}})N_{\mathrm{}}:=|E_{\mathrm{}}|`$, its real four-variate representation is obtainable within $`𝒪(N_{\mathrm{}}^4\mathrm{log}^2N_{\mathrm{}})`$ steps. Doing so for all $`\mathrm{}=1,\mathrm{},M`$ leads to running time $`𝒪(N^4\mathrm{log}^2N)`$ as $`_{\mathrm{}}N_{\mathrm{}}N`$.
W.l.o.g. let $`\mathrm{deg}(P_1)\mathrm{deg}(P_2)\mathrm{}\mathrm{deg}(P_M)`$. Adding up the just obtained four-variate representations in this increasing order takes additional time $`𝒪(N_1^4+N_2^4+\mathrm{}+N_M^4)𝒪(N^4)`$.
3. By virtue of standard amplification it suffices to deal with the case $`\epsilon =\frac{1}{2}`$. The algorithm considers any set $`A`$ of size $`|A|2N`$. It chooses $`x_0,x_1,x_2,x_3A`$ uniformly and independently at random; and then evaluates the input expression $`E`$ by substituting $`X:=x_0+ix_1+jx_2+kx_3`$. If the result is zero, the algorithm reports zero, otherwise non-zero.
The running time for evaluation is obviously linear in $`|E|=N`$. Moreover, only one-sided errors occur. So suppose $`E`$ represents non-zero $`p_1[X]`$. Then obviously $`\mathrm{deg}(p)N`$ and at least one of the four real four-variate polynomials $`\stackrel{~}{p}_0,\mathrm{},\stackrel{~}{p}_3`$ according to (6) is non-zero as well. By virtue of Lemma 4e), this will be witnessed by $`(x_0,\mathrm{},x_3)`$ — i.e., $`p(x_0+ix_1+jx_2+kx_3)0`$ — with probability at least $`\frac{1}{2}`$. ∎

### 3.3 Multi-Evaluating Two-Sided Polynomials

Consider an expression of the form $`p(X)=_{\mathrm{}=0}^{n1}a_{\mathrm{}}X^{\mathrm{}}b_{\mathrm{}}`$, $`a_{\mathrm{}},b_{\mathrm{}}`$. Expanding $`a_{\mathrm{}}=\mathrm{Re}(a_{\mathrm{}})+i\mathrm{Im}_i(a_{\mathrm{}})+j\mathrm{Im}_j(a_{\mathrm{}})+k\mathrm{Im}_k(a_{\mathrm{}})`$ and similarly for $`b_{\mathrm{}}`$, one obtains, by virtue of distributive laws and since whole $``$ commutes with $`X^{\mathrm{}}`$, that it suffices to multi-evaluate expressions of the form

$$q(X)=_{\mathrm{}=0}^{n1}\alpha _{\mathrm{}}X^{\mathrm{}},\alpha _{\mathrm{}}(!)$$
(8)
since $`p(X)`$ can be obtained from 16 of them, each multiplied both from left and right with some basis element $`1,i,j,k`$. Now with real $`\alpha _{\mathrm{}}`$, multi-evaluation of (8) is of course trivial on $`x_0,\mathrm{},x_{n1}`$; but we want $`x_{\mathrm{}}`$ to be arbitrary quaternions! Fortunately, the latter can efficiently be reduced to the first.

To this end, consider mappings $`\phi _u:`$, $`xuxu^1`$ with $`u`$ of norm $`|u|=1`$. It is well-known \[5, pp.214-216\] that, identifying $``$ with $`^4`$, $`\phi _u`$ describes a rotation, i.e., $`\phi _u\mathrm{SO}(^4)`$. Furthermore, restricted to the set

$$\mathrm{Im}:=\{x:\mathrm{Re}(x)=0\}^3$$

of *purely imaginary* quaternions, $`\phi _u`$ exhausts whole $`\mathrm{SO}(^3)`$ as $`u`$ runs through all unit quaternions; this is called Hamilton’s Theorem. Finally, $`\phi _u`$ is an (and in fact, again, the most general) $``$-algebra automorphism, i.e., satisfies for $`\alpha `$ and $`x,y`$:

$$\phi _u(\alpha )=\alpha ,\phi _u(x+y)=\phi _u(x)+\phi _u(y),\phi _u(xy)=\phi _u(x)\phi _u(y).$$

###### Lemma 6

For $`v,w\mathrm{Im}`$, $`|v|=1=|w|`$, let $`u:=(v+w)/|v+w|`$; then $`\phi _u(v)=w`$. In particular for $`x`$, $`v:=\mathrm{Im}(x)/|\mathrm{Im}(x)|`$, $`w:=i`$, it holds $`q(x)=u^1q(y)u`$ where $`y:=uxu^1+i`$.

Our algorithm evaluates $`q[X]`$ simultaneously at $`x_1,..,x_n`$ as follows:

* For all $`x_{\mathrm{}}+i`$, let $`u_{\mathrm{}}:=1`$;
* for each $`x_{\mathrm{}}`$, compute (in constant time) $`u_{\mathrm{}}`$ according to Lemma 6.
* Perform in linear time the transformation $`y_{\mathrm{}}:=u_{\mathrm{}}x_{\mathrm{}}u_{\mathrm{}}^1`$.
* Use classical techniques to multi-evaluate $`q`$ at $`y_1,\mathrm{},y_n`$ within $`𝒪(n\mathrm{log}^2n)`$.
* Re-transform the values $`q(y_{\mathrm{}})`$ to $`q(x_{\mathrm{}})=u_{\mathrm{}}^1q(y_{\mathrm{}})u_{\mathrm{}}`$.

This proves the claimed running time of $`𝒪(n\mathrm{log}^2n)`$. ∎

## 4 Conclusion

We proposed three generalizations for the notion ’*polynomial*’ from fields $``$ and $``$ to the skew-field $``$ of quaternions and analyzed their respective properties. For each notion, we then investigated (where applicable) on the algebraic complexity of operations multiplication and multi-evaluation on polynomials in terms of their degree. The upper bounds attained by our respective algorithms match (usually trivial) lower bounds up to polylogarithmic factors.

However since each of the above notions lacks one (e.g., closure under multiplication) or another (e.g., quasi-linear complexity) desirable property, a satisfactory definition for quaternion polynomials is still missing. Here comes another one, generalizing the representation of complex polynomials in terms of their roots:

$$𝕂_4[X]:=\{a_0(Xa_1)(Xa_2)\mathrm{}(Xa_n):n_0,a_{\mathrm{}}\}$$
(9)
So what is the complexity for multi-evaluation in $`_4[X]`$?

In view of the planar $`N`$-body problem, Gerasoulis’ major break-through was fast multi-evaluation of complex rational functions

$$\underset{\mathrm{}=1}{\overset{N}{}}(Xa_{\mathrm{}})^1$$
(10)
for given $`a_1,\mathrm{},a_N`$ at given $`x_1,\mathrm{},x_N`$; cf. also Corollary 7 in . Our techniques from Subsection 3.3 yield the same for $`x_{\mathrm{}}`$ and $`a_{\mathrm{}}`$. Thus the crucial question remains whether (10) also allows multi-evaluation in sub-quadratic time for both $`a_{\mathrm{}}`$ and $`x_{\mathrm{}}`$ being quaternions. But what is a rational quaternion function, anyway? We do not even know what a quaternion polynomial is! Observe that, lacking commutativity,

$$\frac{1}{Xa}+\frac{1}{Xb}=\frac{1}{Xa}\frac{1}{Xb}(Xb)+(Xa)\frac{1}{Xa}\frac{1}{Xb}$$

cannot be collected into one single fraction, in spite of the common denominator.

#### Acknowledgments:

The idea to use quaternions for $`N`$-Body Simulation was suggested by Peter Bürgisser. The author wishes to thank his student, Tomas Brajkovic, for having chosen him as supervisor. In fact, Sections 2.1 and 3.2 constitute the core of Tomas*Staatsexamensarbeit* (high school teacher’s thesis).

## Appendix 0.A Postponed Proofs

Here, we collect some proofs which, in the printed version, had to be quelled due to page constraints.

###### Lemma 7

Let $`f,g[X_1,\mathrm{},X_d]`$ denote $`d`$-variate real polynomials. Then,

$$\mathrm{deg}(f^2+g^2)=\mathrm{max}\{\mathrm{deg}(f^2),\mathrm{deg}(g^2)\}=2\mathrm{max}\{\mathrm{deg}f,\mathrm{deg}g\}.$$

In particular, the total degree of $`f^2+g^2`$ is even.

###### Proof

The second equation is trivial, regarding that the total degree satisfies $`\mathrm{deg}(f^2)=2\mathrm{deg}(f)`$; similarly for the *in*equality $`\mathrm{deg}(f^2+g^2)\mathrm{max}\{\mathrm{deg}(f^2),\mathrm{deg}(g^2)\}`$. One thus has to show that, although in $`f^2+g^2`$ certain terms of coinciding maximum total degree might indeed cancel, the above inequality is in fact an equality. This is where the real ground field comes into play: choose in $`f`$ and $`g`$ respective terms $`M`$ and $`N`$ of coinciding maximum total degree, that is, $`M=aX_1^{m_1}\mathrm{}X_d^{m_d}`$ and $`N=bX_1^{n_1}\mathrm{}X_d^{n_d}`$ with $`m_{\mathrm{}}=\mathrm{deg}f=\mathrm{deg}g=n_{\mathrm{}}`$ and $`a,b0`$. Then both $`M^2=a^2X_1^{2m_1}\mathrm{}X_d^{2m_d}`$ and $`N^2=b^2X_1^{2n_1}\mathrm{}X_d^{2n_d}`$ have total degree equal to $`\mathrm{deg}(f^2)=\mathrm{deg}(g^2)`$. Furthermore, their respective occurrences in $`f^2+g^2`$ cannot cancel because $`a^2`$ and $`b^2`$ are strictly positive; hence $`\mathrm{deg}(f^2+g^2)\mathrm{deg}(M^2)=\mathrm{deg}(N^2)`$. ∎

Proof of Lemma 3. Integrality of the degree is covered by applying Lemma 7 above inductively to $`(\stackrel{~}{f}_0^2,\stackrel{~}{f}_1^2)`$, $`(\stackrel{~}{f}_0^2+\stackrel{~}{f}_1^2,\stackrel{~}{f}_2^2)`$, and $`(\stackrel{~}{f}_0^2+\stackrel{~}{f}_1^2+\stackrel{~}{f}_2^2,\stackrel{~}{f}_3^2)`$.
For the second claim, straight-forward calculation confirms the *Four Squares Theorem*333discovered by Euler in 1748 for real numbers, here applied to the case of real polynomials $`\stackrel{~}{f}_0,\mathrm{},\stackrel{~}{f}_3,\stackrel{~}{g}_0,\mathrm{},\stackrel{~}{g}_3`$:

$`\left(\stackrel{~}{f}_0^2+\stackrel{~}{f}_1^2+\stackrel{~}{f}_2^2+\stackrel{~}{f}_3^2\right)\left(\stackrel{~}{g}_0^2+\stackrel{~}{g}_1^2+\stackrel{~}{g}_2^2+\stackrel{~}{g}_3^2\right)=`$
$`=`$ $`(\stackrel{~}{f}_0\stackrel{~}{g}_0\stackrel{~}{f}_1\stackrel{~}{g}_1\stackrel{~}{f}_2\stackrel{~}{g}_2\stackrel{~}{f}_3\stackrel{~}{g}_3)^2+(\stackrel{~}{f}_0\stackrel{~}{g}_1+\stackrel{~}{f}_1\stackrel{~}{g}_0+\stackrel{~}{f}_2\stackrel{~}{g}_3\stackrel{~}{f}_3\stackrel{~}{g}_2)^2`$
$`+`$ $`(\stackrel{~}{f}_0\stackrel{~}{g}_2+\stackrel{~}{f}_2\stackrel{~}{g}_0+\stackrel{~}{f}_3\stackrel{~}{g}_1\stackrel{~}{f}_1\stackrel{~}{g}_3)^2+(\stackrel{~}{f}_0\stackrel{~}{g}_3+\stackrel{~}{f}_3\stackrel{~}{g}_0+\stackrel{~}{f}_1\stackrel{~}{g}_2\stackrel{~}{f}_2\stackrel{~}{g}_1)^2`$
Now observe that the total degree of the left hand side of (0.A) is

$$\begin{array}{c}\mathrm{deg}((\stackrel{~}{f}_0^2+\stackrel{~}{f}_1^2+\stackrel{~}{f}_2^2+\stackrel{~}{f}_3^2)((\stackrel{~}{g}_0^2+\stackrel{~}{g}_1^2+\stackrel{~}{g}_2^2+\stackrel{~}{g}_3^2))\hfill \\ \hfill =\mathrm{deg}(\stackrel{~}{f}_0^2+\stackrel{~}{f}_1^2+\stackrel{~}{f}_2^2+\stackrel{~}{f}_3^2)+\mathrm{deg}(\stackrel{~}{g}_0^2+\stackrel{~}{g}_1^2+\stackrel{~}{g}_2^2+\stackrel{~}{g}_3^2)\end{array}$$

which, by Definition 5, agrees with $`2\mathrm{deg}(p)+2\mathrm{deg}(q)`$ for $`p,q_1[X]`$ according to (6). At the same time, in view of Equation (6$`\frac{1}{2}`$), the total degree of (0.A)’s right hand side is nothing but $`2\mathrm{deg}(pq)`$. ∎

Proof of Lemma 5.

* Straight forward calculation verifies $`\mathrm{Re}(X)=\frac{1}{4}(XiXijXjkXk)`$ which obviously belongs to $`_1[X]`$. Thus, the quadruple of four-variate real polynomials $`(X_0,0,0,0)^4[X_0,\mathrm{},X_3]`$ does correspond to a quaternion polynomial.
* Similarly, $`(X_1,0,0,0)^4[X_0,\mathrm{},X_3]`$ corresponds to $`\mathrm{Im}_i(X)=\mathrm{Re}(iX)_1[X]`$; same for $`(X_2,0,0,0)`$ and $`(X_3,0,0,0)`$.
* For any real constant $`\alpha `$, $`(\alpha ,0,0,0)^4[X_0,\mathrm{},X_3]`$ corresponds to $`\alpha _1[X]`$.
* Let $`(\stackrel{~}{f},0,0,0)`$ and $`(\stackrel{~}{g},0,0,0)`$ correspond to quaternion polynomials $`p,q_1[X]`$, respectively. Then $`(\stackrel{~}{f}+\stackrel{~}{g},0,0,0)`$ corresponds to $`p+q_1[X]`$; and,

$$(\stackrel{~}{f}\stackrel{~}{g},0,0,0)\stackrel{(\text{6}\frac{1}{2})}{=}(\stackrel{~}{f},0,0,0)(\stackrel{~}{g},0,0,0)$$

corresponds to $`pq_1[X]`$.

Since $`[X_0,\mathrm{},X_3]`$ is the *smallest* set containing real constants, the generators $`X_0`$, $`X_1`$, $`\mathrm{}`$, $`X_3`$, and being closed under addition and multiplication, the above considerations imply that, for any $`\stackrel{~}{f}[X_0,\mathrm{},X_3]`$, $`(\stackrel{~}{f},0,0,0)`$ corresponds to some $`p_1[X]`$.

* Suppose $`(\stackrel{~}{f},0,0,0)`$ corresponds to $`p_1[X]`$. Then $`(0,\stackrel{~}{f},0,0)`$ corresponds to $`ip_1[X]`$; analogously for $`(0,0,\stackrel{~}{f},0)`$ and $`(0,0,0,\stackrel{~}{f})`$.
* Let $`(\stackrel{~}{f}_0,0,0,0)`$ correspond to $`p_0_1[X]`$, $`(0,\stackrel{~}{f}_1,0,0)`$ to $`p_1`$, $`(0,0,\stackrel{~}{f}_2,0)`$ to $`p_2`$, and $`(0,0,0,\stackrel{~}{f}_3)`$ to $`p_3`$. Then $`(\stackrel{~}{f}_0,\stackrel{~}{f}_1,\stackrel{~}{f}_2,\stackrel{~}{f}_3)`$ corresponds to $`p_0+\mathrm{}+p_3_1[X]`$. ∎

Proof of Lemma 6. Observe that $`u^1=\overline{u}/|u|^2=u`$ since $`u\mathrm{Im}`$ and $`|u|=1`$. Thus

$`\phi _u(v)`$ $`=`$ $`{\displaystyle \frac{(v+w)v(v+w)}{|v+w|^2}}={\displaystyle \frac{v^3+v^2w+wv^2+wvw}{2+2v,w}}`$
because $`|v|=1=|w|`$ by presumption. As $`v,w\mathrm{Im}`$, furthermore $`v^2=1=w^2`$ and thus

$`\phi _u(v)`$ $`=`$ $`{\displaystyle \frac{v2w+(2v,ww+v)}{2+2v,w}}=w.`$
The $``$-algebra homomorphism property ensures that $`q\left(\phi _u(x)\right)=\phi _u\left(q(x)\right)`$ for any polynomial $`q`$ with real coefficients and $`x`$. In particular, $``$-linearity yields

$$y=\phi _u(x)=\phi _u(\mathrm{Re}(x)+|\mathrm{Im}(x)|v)=\mathrm{Re}(x)+|\mathrm{Im}(x)|i+i$$