format: text

text:
# In-medium properties of the D₁₃(1520) nucleon resonance

## Abstract

The in-medium properties of the D$`{}_{13}{}^{}(1520)`$ nucleon resonance were studied via photoproduction of $`\pi ^o`$-mesons from nuclei (C, Ca, Nb, Pb) with the TAPS-detector at the Mainz MAMI accelerator. The inclusive (single and multiple pion production) data disagree with model predictions which explain the disappearance of the second resonance bump in total photoabsorption via a medium modification of the D$`{}_{13}{}^{}\text{N}\rho `$ decay. The exclusive single $`\pi ^o`$ production data show no broadening of the resonance structure beyond Fermi smearing. Although due to final state interaction effects pion production tests the nucleus at densities less than the average nuclear density, both results together cast doubt on attempts to explain the vanishing of the second resonance bump for heavy nuclei by a broadening of the D13-resonance in nuclear matter.

preprint: HEP/123-qed

The low lying $`\text{N}^{}`$ resonances, excited states of the nucleon with isospin $`I=1/2`$, comprise the states P$`{}_{11}{}^{}(1440)`$, D$`{}_{13}{}^{}(1520)`$ and S$`{}_{11}{}^{}(1535)`$ in the well known nomenclature . They are for example excited by photons with energies between 600 and 900 MeV. Since their decay widths are large compared to their spacing they overlap and form one single enhancement usually called the second resonance region. Due to their different couplings to the initial photon - nucleon and the final meson - nucleon states they can nevertheless be separated to a large extent: The production of $`\eta `$-mesons proceeds almost exclusively via the excitation of the S11 resonance, while the largest resonance contributions to single and double pion production come from the D13 resonance. Using this selectivity, the properties of the resonances, when excited on the free proton or quasifree neutron, have been studied in much detail during the last few years via $`\eta `$-photoproduction  and single and double pion photoproduction reactions . The excellent quality of the recent data sets allowed precise determinations of the resonance properties, e.g. the extraction of a 0.05% - 0.08% branching ratio for the D$`{}_{13}{}^{}\text{N}\eta `$ decay .

However, much less is yet known about the behavior of the isobars inside the nuclear medium, where a number of modifications may arise. The most trivial is the broadening of the excitation functions due to Fermi motion. The decay of the resonances is modified by Pauli-blocking of final states, which reduces the resonance widths, and by additional decay channels like $`\text{N}^{}\text{N}\text{NN}`$ which cause the so-called collisional broadening. Both effects cancel to some extent and it is a priori not clear which one will dominate. A very exciting possibility is that the resonance widths could be sensitive to in-medium mass modifications of mesons arising from chiral restoration effects . The D13-resonance for example has a 15 - 25% decay branch to the $`\text{N}\rho `$-channel , which is only fed from the low energy tail of the $`\rho `$ mass distribution.

This means that a broadening or a downward shift of the $`\rho `$-mass distribution inside the nuclear medium could have significant effects on the D13 width.

The first experimental investigation of the second resonance region for nuclei was done with total photoabsorption. The surprising results showed an almost complete absence of the resonance bump for 4He and heavier nuclei , which up to now has not been understood.

The problem is illustrated in Fig. 1 where the total inclusive $`\pi ^o`$-production cross section from Ca from the present experiment is compared to the reaction on the deuteron and to model predictions. The deuteron data show a clear bump around 800 MeV, but the calcium data are rather flat. However, the predictions for Ca from the BUU model , which takes into account Fermi smearing, Pauli-blocking and collisional broadening still exhibit the bump structure. Not even the modification of the D13 decay by medium effects of the $`\rho `$-meson (solid curve) improves the situation. Only an arbitrary and probably unrealistic broadening  of the D13-resonance by 300 MeV produces a significant suppression. Note that the underestimation of the cross section at low incident photon energies is attributed in  to many-body absorption processes of the photon which are not included in the model.

Total photoabsorption has the advantage, that no final state interaction effects (FSI) must be accounted for so that the entire nuclear volume is tested. However, many different reaction channels do contribute to this reaction so that it is impossible to test the behavior of individual resonances. Even worse, some of the reaction channels responsible for the structure are not strongly related to the excitation of states from the second resonance region.

Part of the problem is that most of the rise of the cross section towards the resonance bump stems from the opening of the double pion production channels . The largest contribution is due to the $`\pi ^+\pi ^{}`$ final state. It is well known  that this reaction is dominated by $`\mathrm{\Delta }`$-Kroll-Rudermann and $`\mathrm{\Delta }`$-pion-pole terms, i.e. it mainly involves the excitation of the P$`{}_{33}{}^{}(1232)`$ $`\mathrm{\Delta }`$-resonance rather than the states from the second resonance region.

It is therefore desirable to study this region with exclusive reactions which allow the investigation of individual resonances, even at the expense that FSI effects complicate the interpretation. In a recent study  we used $`\eta `$-photoproduction for an investigation of the in-medium properties of the S$`{}_{11}{}^{}(1535)`$. In this case we did not find any unexplained depletion of the in-medium resonance strength. The data were in excellent agreement with predictions from the BUU-model  and other models (e.g. ), taking into account Fermi smearing, Pauli-blocking, collisional broadening and FSI effects. Since the energy range extended just up to the resonance maximum, it was not possible to deduce the in-medium width of the resonance. In the meantime Yorita et al.  have studied quasifree $`\eta `$-photoproduction from carbon over a larger energy range and also found no significant broadening of the S11 resonance. Again the data are in fairly good agreement with model expectations.

The above results do not preclude broadening as the explanation for the absence of the second resonance bump because the total contribution of the S11-resonance to the bump structure is quite small. Furthermore due to the location of the $`\eta `$-production threshold in the low energy tail of the resonance, the effects of nuclear Fermi motion have a drastic influence on the excitation curve so that any extraction of the in-medium width requires a lot of modelling. In the present work we have therefore investigated the dominant D$`{}_{13}{}^{}(1520)`$ resonance in the nuclear medium via quasifree single $`\pi ^o`$-photoproduction.

The experiments using C-, Ca-, Nb- and Pb-targets were carried out at the Glasgow tagged photon facility installed at the Mainz Microton (MAMI) with the TAPS-detector. Details of the experimental setup and the data analysis are summarised in . The neutral pions were identified via an invariant mass analysis and quasifree single $`\pi ^o`$-production was selected by a missing energy analysis as in . The stronger broadening of the structures in the missing energy spectra for nuclei heavier than deuterium was compensated by more restrictive cuts, so that contamination from multiple meson production was excluded.

The total single $`\pi ^o`$ production cross section for the proton and the deuteron  are shown in Fig. 2. The insert shows for the deuteron the separation of quasifree single $`\pi ^o`$-production in missing energy from multiple pion production processes ($`\pi ^o\pi ^o`$, $`\pi ^\pm \pi ^o`$, $`\eta 3\pi ^o`$, $`\eta \pi ^o\pi ^+\pi ^{}`$), which contribute to the inclusive cross section. In the main part of the figure the proton and deuteron cross sections are compared to the expectation from a unitary isobar analysis of pion photoproduction (MAID) . The data for the proton are very well reproduced. For the deuteron, we have taken the sum of the proton and neutron cross sections from MAID (full curve in Fig. 2) and folded this cross section with the momentum distribution of the nucleons bound in the deuteron (dashed curve). The momentum distribution was derived from a parametrization of the deuteron wave function . The prediction for the deuteron cross section agrees very well with the data in the tail of the $`\mathrm{\Delta }`$-resonance, but it significantly overestimates the cross section in the D13 region. This result is very surprising since we are dealing with quasifree pion production, for which the large momentum mismatch between participant and spectator nucleon is expected to suppress any interference terms between the two nucleons. At present it is not clear if this problem is related to the input used for the elementary cross section of the $`n(\gamma ,\pi ^o)n`$ reaction or if the incoherent addition of the Fermi smeared elementary cross sections, which in the same energy region works excellently e.g. for $`\eta `$-photoproduction , is not a good approximation. Precise measurements of $`\pi ^o`$-photoproduction from the deuteron with coincident detection of the recoil nucleons and more refined model calculations are necessary to solve this problem. However, no matter what the nature of the problem is, we like to stress that this finding has important consequences for the extraction of resonance in-medium properties from a comparison to model predictions. Models like the BUU  must rely on the assumption that the total cross section from nuclei before taking into account in-medium and FSI effects is the incoherent sum of the known proton and neutron cross sections, which in this case is not even true for the deuteron.

For a more quantitative analysis of the D13-excitation in nuclei we have decomposed the cross sections into a resonance and a background part. In principle such a decomposition requires a multipole analysis wich takes into account resonance - background interference terms. However, interference terms are small in this case as demonstrated in Fig. 3, which shows the proton and neutron cross sections calculated with MAID .

The single $`\pi ^o`$ production cross sections taking into account all resonances and background terms ($`\sigma _{\pi ^o}`$) are very similar to the sum of the separate cross sections $`\sigma _r`$ (excitation of the S11 and D13 resonances only) and $`\sigma _{nr}`$ (everything except S11 and D13 excitation). In the following we do not attempt to separate the contribution from the two resonances but one should keep in mind that the resonance part is dominated by the excitation of the D13 (see Fig. 3). The decomposition of the measured cross sections is shown in Fig. 4. The background part coming from the tail of the $`\mathrm{\Delta }`$-resonance, the contribution of the P11-resonance, nucleon Born terms and vector meson exchange was fitted with a function of the type:

$$\sigma e^{(aE_\gamma ^2+bE_\gamma )}$$
(1)
with $`a`$ and $`b`$ as free parameters. It is obvious from the figure that the resonance contribution for the data for heavier nuclei is not qualitatively different from the deuteron case.

The differences between measured cross sections and fits are shown in Fig. 5. In the main figure the resonance contributions for the proton, the deuteron and the average for the heavier nuclei are compared to the MAID predictions for the D13 and S11 contributions. For the deuteron and the heavier nuclei the MAID average of proton and neutron cross sections folded with the proper momentum distributions is scaled to the data. Obviously no broadening of the resonance structure beyond Fermi smearing is observed. A D13 resonance broadened to 300 MeV as used in the BUU calculations  for the inclusive data (see Fig. 1) is clearly ruled out, the data correspond rather to BW-curves with a width around 100 MeV.

Finally, we have investigated if the strength of the resonance signal for the nuclei is consistent with the deuteron case. For this purpose we have folded the MAID proton cross section for resonance excitation with the deuteron Fermi motion and compared the result to the measured deuteron cross section. Agreement is obtained for $`\sigma _n(\text{D}_{13})/\sigma _p(\text{D}_{13})1/3`$, while the ratio obtained from a direct comparison of MAID proton and neutron cross sections is 2/3. We have then adopted the 1/3 ratio, folded $`(1+1/3)\sigma _p/2`$ with a typical nuclear momentum distribution and compared the result to the nuclear data scaled to $`A^{2/3}`$, which in the simplest approximation accounts for the FSI effects (see Fig. 5, insert). The agreement of this approximation with the data is quite good.

At this point we must clarify a crucial aspect of our results. The approximate scaling of the cross sections with $`A^{2/3}`$ indicates FSI effects. This means that in contrast to total photoabsorption not the entire nuclear volume is probed. BUU-model calculations  indicate that e.g. for 208Pb in the $`\mathrm{\Delta }`$-resonance region observed pions are predominantly produced in a surface region where the nuclear density drops from 0.8$`\rho _o`$ to 0.4$`\rho _o`$ ($`\rho _o`$: normal nuclear density). However, suppression of the resonance bump in total photoabsorption reactions occurs already for 4He  and does not change from very light nuclei like lithium and beryllium up to very heavy ones like uranium. This excludes a strong density dependence of the effect.

Furthermore, it is clear that the models without a strong broadening of the D13 resonance overestimate our inclusive pion data (see Fig. 1). However, these data are subject to FSI in the same way as the exclusive data. This can be shown by fitting the mass dependence of the cross section from carbon to lead with a simple $`A^\alpha `$ law. The results in the energy range 720 - 790 MeV are: $`\alpha =0.791\pm 0.005`$ (inclusive pion data), $`\alpha =0.74\pm 0.01`$ (exclusive pion data, Fig. 4), and $`\alpha =0.81\pm 0.05`$ (D13 part only, Fig. 5, insert). This means that the inclusive and exclusive data probe the nuclei at comparable densities and consequently a broadening of the D13 resonance is ruled out as an explanation for the overestimation. It is thus evident that the models miss some other effect which must be understood before the results from total photoabsorption can be used as evidence for an in-medium resonance broadening.

In summary, investigating quasifree $`\pi ^o`$ photoproduction we have found a strong quenching but no broadening of the D13-resonance structure for the deuteron with respect to the proton. However, for heavy nuclei we found no indication of a broadening or a suppression of the D13 structure with respect to the deuteron. Since so far model predictions agree with the pion photoproduction data only under the assumption of a strong broadening of the resonance, other effects seem to be missing in the models. This casts also doubt on the interpretation of the total photoabsorption data via resonance broadening in the framework of the same models.

###### Acknowledgements.

We wish to acknowledge the outstanding support of the accelerator group of MAMI, as well as many other scientists and technicians of the Institute für Kernphysik at the University of Mainz. This work was supported by Deutsche Forschungsgemeinschaft (SFB 201) and the UK Science and Engineering Research Council.


text:
# Spectral and temporal behavior of the black hole candidate XTE J1118+480 as observed with BeppoSAX

## 1 Introduction

The high Galactic latitude transient source XTE J1118+480 was discovered with the All-Sky Monitor (ASM) aboard the Rossi X-Ray Time Explorer (RXTE) satellite Remillard et al.  (2000) during a low state mini–outburst in X–rays (see Fig. 1). The source has attracted the interest of many investigators, who have performed observational and theoretical studies. The radio, near-infrared, optical and EUV counterparts of XTE J1118+480 were discovered soon after the ASM announcement (Pooley & Waldram 2000, Chaty et al. 2000, Uemura et al. 2000a, Uemura et al. 2000c, Mauche et al. 2000) and their temporal and spectral properties reported (Cook et al. 2000, Garcia et al. 2000, Haswell, Hynes & King 2000a, McClintock et al. 2000, Uemura et al. 2000c, Wagner et al. 2000). The Low Mass X–ray Binary (LXMB) nature of the system was soon established Uemura et al. 2000c , even though a surprisingly low X–ray–to–optical flux ratio of $`5`$, against a typical value of $`500`$ van Paradijs & McClintock  (1995), was noticed Garcia et al.  (2000). The binary period of the system ($`P=0.1703`$ days) and its mass function were also determined McClintock et al.  (2000); McClintock et al. 2001a ; Wagner et al.  (2000). The estimate of a large value of the mass funtion ($`6M_{}`$, McClintock et al. 2000, 2001a; Wagner et al. 2000) provided evidence of the black hole nature of XTE J1118+480. Wagner et al. (2001) provided the following values of the sytem parameters: inclination $`i=81\pm 2`$ degrees, black hole mass $`M_\mathrm{X}/\mathrm{M}_{\mathrm{}}=`$6.0–7.7, distance $`d=1.9\pm 0.4`$ kpc. We also derived the parameters of the system (Frontera et al. 2001b, hereafter F01), finding values which are consistent with those derived by McClintock et al. (2001a) and Wagner et al. (2001).

The multiwavelength spectrum of XTE J1118+480, from radio to X–rays, has been investigated by various authors (Hynes et al. 2000, McClintock et al. 2001b, Markoff et al. 2001). The spectrum reported by McClintock et al. (2001b) was obtained from source observations centered on 2000 April 18 (April 18 in radio, NIR, optical and X–rays up to 200 keV; April 16–19 in EUV), while that reported by Hynes et al. (2000) is averaged over observations that took place on 2000 April 2–3 (radio), April 4, 18 (NIR), and April 8 (optical, EUV, X–rays up to 200 keV). The BeppoSAX 0.1–200 keV spectrum of the source performed on 2000 April 14–15 was also reported (F01). From these spectral investigations some relevant properties of the emission processes at the source site can be derived. In the radio–submillimiter–near-infrared band, the spectrum shows a broken power–law shape with energy index $`\alpha `$ of $`+0.5`$ below an inferred cut–off frequency of $`10^{13}`$ Hz and $`0.6`$ above it Fender et al. 2001a . Similar shapes are typical of hard/low spectral states of BHCs and are believed to be due to synchrotron emission from self-absorbed jets Fender 2001b . Another relevant spectral property is the presence of a thermal component consistent with a blackbody at $`40`$ eV. This component is apparent in the first observation of XTE J1118+480 with BeppoSAX (F01) and it is also detected in the multiwavelength spectrum of the source derived by McClintock et al. (2001b) . BeppoSAX has also allowed to study the source spectrum up to 200 keV (F01). In the BeppoSAX observation, the high energy tail is well fit with a thermal Comptonization in a plasma with a temperature of $`60`$ keV and an optical depth of the order of unity. A weak Compton reflection ($`\mathrm{\Omega }/2\pi =0.16_{0.06}^{+0.11}`$) along with a low metallicity ($`Z/Z_{}=0.10_{0.06}^{+0.11}`$) of the reflecting material appears the best description of the broad BeppoSAX spectrum. Miller et al. (2002), using 0.4–5 keV data obtained with a Chandra X–ray Observatory (Chandra) observation performed on 2000 April 18 and 2.8–100 keV data obtained summing together 18 short RXTE observations performed between 2000 April 13 and May 13, report a reflection ($`0.01_{0.01}^{+0.06}`$) consistent with zero. This result, obtained with standard metal abundances ($`Z/Z_{}=1`$), is also found with BeppoSAX (F01), when the metal abundances are constrained to be the solar ones. Markoff et al. (2001) find the multiwavelength spectrum from radio to X–rays reported by Hynes et al. (2000) also consistent with nonthermal synchrotron emission from a jet-like matter outflow.

The erratic time variability of the source has also been investigated. As in several other BHCs in their low/hard state, a low frequency QPO feature was discovered (Revnivtsev et al. 2000, Yamaoka et al. 2000). The centroid frequency is observed to continuously drift from $`0.07`$ Hz to $`0.17`$ Hz from 2000 April 10 to June 11 Wood et al.  (2000). It is interesting that a similar QPO feature as well as a non–Poissonian time variability is found in the optical/UV band: the power spectral density estimate (PSD) has a power–law shape ($`f^\beta `$ with index $`\beta `$ of $`1`$ above 0.02 Hz Haswell et al. 2000b . Simultaneous high-time resolution X–ray and optical observations of the source show a strong correlation between these emissions Kanbach et al.  (2001): the optical emission suddenly (within 30 ms) rises following an increase in the X–rays, but with a dip in the optical/X–ray cross–correlation at 2–5 s before zero lag, as though the optical emission knows something about the X–ray emission that comes later. Kanbach et al. (2001) interpret these features assuming a cyclo-synchrotron radiation emission mechanism Merloni et al.  (2000) and the photoshere of a magnetically dominated outflow from the black hole as the emission region. Another peculiar fact is that the 0.01–50 Hz fractional variation of the source flux is found to be highest in the soft X–ray range (62% rms in the 0.1–2 keV energy range versus 42% rms in the 2–10 keV range) (F01).

After the first Target of Opportunity (TOO) (F01), we performed with BeppoSAX three additional long observations of XTE J1118+480 (see Fig. 1), sampling the source outburst and its quiescence status. In this paper we report results of these observations and compare them with those, mentioned above, obtained in the first TOO.

## 2 Observations and data analysis

All the observations were performed with the BeppoSAX Narrow Field Instruments (NFIs). The NFIs embody a Low Energy Concentrator Spectrometer (LECS, 0.1–10 keV, Parmar et al. 1997), 2 Medium Energy Concentrators Spectrometers (MECS, 1.3–10 keV, Boella et al. 1997), a High Pressure Gas Scintillator Proportional Counter (HPGSPC, 3–100 keV, Manzo et al. 1997), and a Phoswich Detection System (PDS, 15–300 keV, Frontera et al. 1997). The LECS and MECS have imaging capabilities, while the HPGSPC and PDS are collimated detectors with a Field of View (FOV) of $`1^{}`$ and $`1.3^{}`$, respectively. The PDS instrument makes use of rocking collimators for background monitoring.

The first three observations (see log in Table 1) were performed in April, May and June 2000, at time intervals of about one month. During the second observation, the LECS was switched off. From 2000 June 30 to October 10, the source was outside the visibility window for BeppoSAX, thus the last BeppoSAX observation was performed in December 2000, long after the ASM outburst was over.

Useful data were selected from time intervals in which the satellite was outside the South Atlantic Geomagnetic Anomaly, the elevation angle was above the Earth limb by $`5\mathrm{°}`$, the Earth was dark (only for LECS), and the high voltage supplies were stabilized. The LECS and MECS source spectra were extracted from a region with a radius of $`8^{}`$ around the centroid of the source image. As background spectra we used standard files obtained from the observation of blank fields. For each observation the spectra of the two MECS were normalized to the same gain and co-added. We used background spectra accumulated from dark Earth data for the HPGSPC (note that the instrument’s collimator was kept on the source for the entire observation). The background level of the PDS was estimated by swapping its collimators off source every 96 s. The energy bands used for spectral fitting were limited to those where the response functions were best known, i.e, 0.12–4 keV, 1.7–10 keV, 7–29 keV, and 15–200 keV, for the LECS, MECS, HPGSPC and PDS, respectively. The count rate spectra were analyzed using the xspec software package Arnaud  (1996). A systematic error of 1% was added in quadrature to the statistical uncertainties of the spectral data, on the basis of the calibration results obtained with the Crab Nebula, that was observed on 10 April 2000, 4 days before the first observation of XTE J1118+480. We allowed for free normalization of the instruments in multi-instrument fits with respect to MECS. For clarity of display, the unfolded spectra from multi-instrument fits were renormalized to the MECS level.

The quoted errors for the spectral parameters correspond to 90% confidence for one parameter ($`\mathrm{\Delta }\chi ^2=2.71`$). The elemental abundances are those by Anders & Ebihara (1982), and the opacities are from Morrison & McCammon (1983). For comparison with the first observation results (F01), we assume the same distance (1.5 kpc) and disk inclination ($`i=70\mathrm{°}`$) assumed in the analysis of the first observation. The parameter values within square parentheses in the Tables are kept fixed in the fits.

## 3 Results

The source was detected in the first three observations, but it was no more visible in the last one. Separately we discuss the first three observations (§ 3.1 and § 3.2) and the last one (§ 3.3).

### 3.1 Spectral behavior with time

Since the energy spectrum proved to be stable throughout each single observation, we accumulated spectra corresponding to each of them. As done in the case of the first observation (see F01), also for the count spectra of the observations 2 and 3, a large number of spectral models were tested: power–law (pl), cutoff power–law (cutoffpl), which is equivalent to the pexriv model Magdziarz & Zdziarski  (1995) in xspec with no Compton reflection, Comptonization model (comptt) of Titarchuk (1994), thermal-Compton model (compps v3.4111compps is available on the internet at ftp://ftp.astro.su.se/pub/juri/XSPEC/COMPPS.) of Poutanen & Svensson (1996), all either singly taken or with the addition a blackbody (bb), all photoelectrically absorbed (wabs model in xspec). Either spherical (sph) or slab (sl) geometries of the Comptonizing electron cloud as well as solar or free metal abundances $`Z`$ of the cold medium were tested. In the fits with the compps model, which allows for the presence of Compton reflection Magdziarz & Zdziarski  (1995) from a cold medium, variable element abundances with respect to the solar ones, could be assumed. For consistency, also a narrow iron emission line with Gaussian profile (centroid energy $`E_l=6.4`$ keV and width with $`\sigma =0.01`$ keV) was added in the fits. Similarly to what found in the TOO1 (F01), also for TOO3 (for TOO2 this test could not be done given the absence of LECS) the fit results with no addition of a direct bb are worse in the case of cutoffpl and give the same goodness in the case of the comptt and compps models. But, in the latter case, the best-fit $`N_\mathrm{H}`$ is found lower or, like in the case of cutoffpl, implausibly low (see discussion in F01). The $`\chi ^2/\mathrm{dof}`$ obtained for cutoffpl, comptt and compps with the addition of bb are reported in Table 2.

It is noteworthy that the compps plus bb model, with $`Z/Z_{}`$ free to vary, systemically provides a significantly lower $`\chi ^2`$ than that in which $`Z/Z_{}`$ is frozen to 1: using the F–test (e.g., Bevington 1969), the probability of chance improvement in the case of slab geometry is $`1.4\times 10^4`$ for TOO1, $`2.5\times 10^4`$ for TOO2 and $`4.7\times 10^8`$ for TOO3. In the case of a spherical geometry, the probability values are higher but still low, specially for observation 3 ($`3.7\times 10^5`$). Thus we consider this two–component model with non solar metal abundance $`Z`$ of the cold medium (likely an accretion disk), the most suitable model capable of describing the spectra of XTE J1118+480. The blackbody seed photons are assumed to be homogeneously distributed in the plasma. Either spherical or slab geometries of the Comptonizing electron cloud fit the data (see Table 2). In Table 3 we show the best fit results in the case a slab geometry (F01). The Thomson optical depth $`\tau `$ corresponds to the half-thickness of the slab. The metal abundance $`Z`$ is about a factor 10 lower than the solar. In observation 1 the best fit absorption column density $`N_\mathrm{H}`$ is consistent with the Galactic column of Hi measured in radio in the direction to the source ($`N_\mathrm{H}(1.28`$$`1.44)\times 10^{20}`$ cm-2, Dickey & Lockman 1990), but it is lower by a factor $`2`$ in the last observation. We observe a systematically significant Compton reflection, which is not required (2$`\sigma `$ upper limits of 0.15, 0.09 and 0.08 for TOO1, TOO2 and TOO3, respectively), when solar metal abundances are assumed. The Compton reflection is consistent with zero even if only the Fe abundance is left free to vary in the fit (in this case $`(Z/Z_{})_{\mathrm{Fe}}`$ converges to 0.1). Using the pexriv model, in place of compps, to compare our results with those by Miller et al. (2002), a Compton reflection is requested by the data ($`\mathrm{\Omega }/2\pi 0.2`$ independently of the observation, with an uncertainty of about 0.1 at 90% confidence level) even in the case of solar metal abundances ($`\chi ^2/\mathrm{dof}=`$ 206.8/175, 108.3/107 and 189.1/167 for TOO1, TOO2 and TOO3, respectively) . However we find that, also with this model, a better fit is found, specially for TOO3, leaving $`Z/Z_{}`$ free to vary (probability of chance improvement of $`3.7\times 10^2`$ for TOO1, $`5.2\times 10^2`$ for TOO2 and $`6.0\times 10^6`$ for TOO3). A Compton reflection component is still needed in this case with a mean metal abundance of $`0.27\pm 0.09`$.

The count rate spectra and the best fit model (compps plus bb for a slab geometry and with reflection, $`Z/Z_{}`$ free to vary) are shown in Fig. 2. In the same figure the residuals to the best fit model are shown when the Compton reflection component is removed from the model. As can be seen, the effect of this removal is apparent.

The compps parameters do not show statistically relevant changes with time. The best-fit temperature of the Comptonizing electrons increases from $`60`$ keV to $`90`$ keV, but, within the 90% errors, these values are consistent with each other. Also the Compton reflection, metal abundance and optical depth of the electron cloud show statistically negligible changes. However the temperature of the direct bb emission increases and its luminosity decreases from observation 1 to 3, with the radius of the bb emission region decreasing from $`35`$ to $`8R_g`$222$`R_gGM_X/c^2`$, assuming $`M_X=10M_{}`$. In observation 2, given the absence of the LECS data, the addition of a bb does not influence the fits. No evidence of an iron fluorescence K line is found in the observations from 1 to 3, with a $`2\sigma `$ upper limit of the equivalent width ($`EW`$) of $`30`$ eV. This result is consistent with the low Compton reflection level.

The best fit results with the photoelectrically absorbed and unabsorbed compps plus bb with free $`Z`$ and slab geometry are shown in Fig. 3 and Fig. 4, respectively. The small residuals to the best fit model are apparent.

As in the case of TOO1 (see F01), we have also considered for TOO2 and TOO3 a multi-component model consisting of the compps model in which the spectrum of seed photons peaks below the observed range ($`kT_{\mathrm{seed}}`$ fixed at 10 eV), plus an additional bb component plus a narrow Gaussian profile at 6.4 keV. Such a low energy of seed photons is expected, e.g., when Comptonization of thermal synchrotron emission dominates (e.g. Wardziński & Zdziarski 2000). This model, in both geometries (sphere or slab), yields a good description of the data (see Table 2). The best fit parameters for the three TOOs are reported in Table 4. As can be seen, also in this case the electron temperature appears to increase and the luminosity of the bb component to decrease from TOO1 to TOO3.

Leaving the metallicity free to vary, as done for observation 1 (see F01), also for observation 3 (for the second observation it could not be done due to the absence of the LECS data) we have tested the effect of replacing a bb with a disk blackbody, in this case assuming the seed photons for Comptonization to be also those of the disk blackbody. This model for the third observation yields plasma parameters very similar to the blackbody case above and a similar fit quality ($`\chi ^2/\mathrm{dof}=169/165`$ for a slab and $`=175/165`$ for a sphere). The inner disk temperature and radius are still consistent with the values found in TOO1: $`kT_{\mathrm{in}}=41_4^{+3}`$ eV, $`R_{in}500`$ km. The lower limit of $`R_{in}`$ corresponds to $`34R_g`$.

The mean flux levels of the source in the three observations are reported in Table 3 for three different energy ranges. Correspondingly, the bolometric (0.01–$`10^3`$ keV) luminosity, corrected for absorption, decreases with time from $`1.1\times 10^{36}`$ erg s-1 to $`9.9\times 10^{35}`$ erg s-1.

### 3.2 Temporal behavior

A temporal analysis of the data with Fourier techniques was performed for each of the first three TOOs, where the source was detected. We estimated the PSD in four energy intervals (0.1–0.5, 0.1–1.5, 1.6–10, 15–200 keV) for each of the TOOs in the 0.0035–50 Hz frequency range of the time variations. For all data we adopted a time binning of 0.05 s and data stretches $`410`$ s long. The number of stetches ranged from $`40`$ to $`120`$, depending on the specific observation and instrument considered. PSDs had been produced from each of the stretches and averaged over the number of data stretches available for the given TOO and energy band. When necessary, the average PSDs were also rebinned in order to increase the source signal. The white-noise level due to Poissonian statistics was subtracted. The PSDs were normalized such that its integral gives the squared rms fractional variability of the source. The derived PSDs multiplied by its Fourier frequency $`f`$ are shown in Figs. 5, 6 and 7 as a function of $`f`$. The QPO feature first reported by Revnivtsev et al. (2000) is apparent in most of the estimated PSDs. Each average spectrum $`P(f)`$ was thus fit with a Lorentzian plus a smoothly broken power–law function (e.g., Lazzati 2002 ) plus a constant $`K`$:

$`P(f)`$ $`=`$ $`{\displaystyle \frac{R_{QPO}\mathrm{\Delta }_{QPO}}{2\pi }}{\displaystyle \frac{1}{\left(ff_{QPO}\right)^2+\left(\frac{\mathrm{\Delta }_{QPO}}{2}\right)^2}}+`$ (1)
$`{\displaystyle \frac{2F_0}{\left[\left(\frac{f}{f_0}\right)^{2\alpha _1}+\left(\frac{f}{f_0}\right)^{2\alpha _2}\right]^{1/2}}}+K`$
where $`\mathrm{\Delta }_{QPO}`$ is the FWHM of the fundamental frequency $`f_{QPO}`$ of the QPO, $`R_{QPO}`$ is the fractional variation of the QPO, $`f_0`$ is the break frequency, $`\alpha _1`$ is the PSD slope below $`f_0`$, $`\alpha _2`$ is the slope at higher frequencies, $`F_0`$ is the value of $`P(f)`$ at $`f_0`$, and $`K`$ is the contribution of white noise above the Poissonian variance. $`K`$ was found to be consistent with zero. All fits were acceptable. However, in the 0.1–0.5 keV and 0.1–1.5 keV energy bands, where there is no evidence of a break (see Figs. 5 and 7), $`f_0`$ could not be constrained and the fit was done with a simple power–law of slope $`\alpha _2`$. The best fit parameters and derived quantities (fractional variation $`R_t`$ of the total source flux, $`R_{QPO}`$ and their ratio) are summarized in Table 5. Some interesting features can be derived from these results. The power law index above the break is almost stable ($`1.3`$), except in the 0.5–1 keV range, where changes from $`1`$ in observation 1 to $`1.7`$ in the third observation. A flattening of the PSDs at low frequencies is observed in all energy bands except below 1.6 keV, as it is also apparent in the $`fP(f)`$ spectra, which must show a maximum corresponding to a break. The behavior of the fractional variation of the source flux with energy is shown in Fig. 8. $`R_t`$ is highest in the 0.1–0.5 keV energy range, where the bb component shows its maximum contribution. However it decreases from the first (67% rms) to the third observation, where it gets a value of 56% rms. At higher energies, $`R_t`$ is lower and similarly decreases with time like its time behavior in the 0.1–0.5 keV band. A peculiar behavior is shown by the centroid frequency of the QPO: it rises from $`0.08`$ Hz to $`0.12`$ Hz from TOO1 to TOO2, in agreement with the results reported by Wood et al. (2000), but returns back to $`0.075`$ Hz in the June 26 observation. In addition (see Figs. 5, 6 and 7), while in the 0.1–1.5 keV energy range the QPO feature is apparent in both TOO1 and TOO3, in the higher energy bands it is not visible in the third observation. Similarly to the fractional variation of the continuum $`R_t`$, the fractional variation under the QPO peak $`R_{QPO}`$ decreases with energy. However its relative contribution with respect to the the total power is approximately stable with energy and time (see Table 5).

### 3.3 Source flux upper limit of the December 2000 observation

No statistically significant X–ray emission was detected in the long TOO observation of December 2000 (TOO4). The 2$`\sigma `$ upper limit of the source flux in the 0.1–2, 2–10 and 15–200 keV energy bands is given by $`1.2\times 10^{13}`$erg cm-2 s-1, $`4.9\times 10^{14}`$erg cm-2 s-1and $`1.9\times 10^{11}`$erg cm-2 s-1, respectively. Assuming a distance of 1.5 kpc, the corrisponding 2$`\sigma `$ upper limit of the source luminosity is $`3.2\times 10^{31}`$ erg s-1, $`1.3\times 10^{31}`$ erg s-1, $`5.1\times 10^{33}`$ erg s-1, respectively. These upper limits are in agreement with the luminosity estimates derived for other black hole candidates with the Chandra satellite Garcia et al.  (2001).

## 4 Discussion

The bolometric luminosity undergoes a small decrease ($`10`$%) in three months (April–June 2000) while the spectral shape remains essentially constant. The spectral shape is compatible with a direct blackbody plus a Comptonization component due to electron scattering in a hot central disk of seed photons. Two possible origins for the seed photons are found to be consistent with our data. One is that they come from the outer disk and thus that they are due to bb emission, part of which we directly observe. We find that its temperature increases with time from $`36`$ to $`52`$ eV and its luminosity correspondingly decreases (see Table 3).

The other possibility is that the seed photons are due to synchrotron of thermal electrons located in the hot plasma itself. Indeed, assuming a photon temperature of 10 eV, corresponding to the turnover frequency above which the plasma becomes optically thin to the synchrotron radiation, the fits are equally good (see Tables 2 and 4). As discussed by F01, in this case the soft excess, visible in the three TOOs, can represent either the peak of the self-absorbed thermal synchrotron emission (e.g. Wardziński & Zdziarski 2000) or blackbody emission not related to the dominant source of the seed photons. The low source luminosity ($`L_\mathrm{X}/L_\mathrm{E}10^3`$) is compatible with the synchrotron scenario Wardziński & Zdziarski  (2000). The temporal properties of the source flux can help to understand the nature of the seed photons and that of the soft photons (0.1–0.5 keV) directly observed. The derived PSD spectra (see Figs. 5, 6 and 7 and Table 5) and the fractional variation (see Fig. 8 and Table 5) of the source time variability show the presence of a significant level of non-poissonian noise. This noise is particularly strong at the lowest energies, where the fractional variation achieves its maximum value (67% in TOO1 and 56% in TOO3). A non-poissonian variance is not expected in the case of a bb radiation, as also confirmed in the case of high/soft states of BHCs (see, e.g., GX339$``$4, Belloni et al. 1999), where the thermal component dominates the spectrum and there is little variability observed. Thus a mere bb is inconsistent with the source variability properties, while the addition of a non-thermal process (likely synchrotron) appears more likely. The optical flickering (about 20% of the total optical flux), the 0.08 Hz QPOs also observed in the optical band and the very flat $`EF(E)`$ spectrum from the NIR to the UV Haswell et al. 2000b ; Chaty et al.  (2001); Kanbach et al.  (2001) confirm this picture, without excluding the contribution to the total soft X-ray flux of a thermal component McClintock et al. 2001b . The inverted power-law spectrum of the radio emission definetely points to a synchrotron radiation component in this band Fender et al. 2001a .

Asssuming a synchrotron origin for the soft X–ray excess, in F01 we constrained the source magnetic field intensity to be $`3\times 10^6B10^8`$ G. We confirm that the data of the second and third TOOs give the same constraint for $`B`$.

The best-fit values of the Comptonizing electron temperature increase with time from $`60`$ to $`100`$ keV; however, due to their statistical uncertainties, we cannot conclude that the this temperature actually change with time. The optical thickness of the electron cloud appears stable, within errors. We definitely observe radiation which is Compton reflected by a medium (likely the accretion disk around the BH) with metal abundance lower, by about a factor 10, than that of the solar environment. The reflection is not detected if we assume a solar metallicity, but this assumption provides a worse description of the data. Our results found with the compps model are not in disagrement with those obtained by Miller et al. (2002), who instead used the pexriv model, finding a Compton reflection consistent with zero assuming either a solar metallicity or $`(Z/Z_{})_{Fe}=0.1`$. However with pexriv we find a Compton reflection component even assuming a solar metallicity. Likely the higher accuracy of our spectra at high energies is at the origin of the difference between our results and those by Miller et al. (2002). The low metallicity derived by us (mean value of $`Z/Z_{}=0.13_{0.04}^{+0.06}`$) is expected in the case of a halo object, as it is XTE J1118+480. Haswell et al. (2002), analyzing ultraviolet observations of the source, find a very high underabundance of carbon with respect to the other metals and do not exclude a lower abundance of these metals with respect to that typical of a solar–like environment. No evidence of an iron line is found down to $`30`$ eV. As we discussed in our first paper (F01), the weakness of the Compton–reflection components could be naturally accounted for by a small solid angle subtended by the cold medium as seen from the hot disk, but could also be explained by the sub-solar abundances derived. Esin et al. (2001), in the context of the the Comptonization model propose that the hot central disk is advection–dominated. As discussed by F01, if such interpretation is correct, it is not clear how to compare the spectral results found for XTE J1118+480 with those obtained for Cygnus X–1, which has a much larger luminosity and almost the same spectral parameters Esin et al.  (1998); Gierliński et al.  (1997); Frontera et al. 2001a .

Markoff et al. (2001) propose that not only the radio–optical but also the X–ray emission could be due to non-thermal jet synchrotron. According to these authors, the radio to optical power output is attributed to optically thick synchrotron emission from the jet at distances from the BH higher than the region where the charged particles are shock accelerated ($`z>z_{acc}100R_g`$, while the X–ray output is due to optically thin synchrotron emission at the shock acceleration region ($`zz_{acc}`$). On the basis of this model, the spectrum expected in the hard X–ray band is a power–law with a cutoff. The exact shape of the cutoff has not been fully worked out for this model. They base their conclusion on the XTE J1118+480 emission model on the spectrum up to 100 keV derived from the High Energy X–ray Timing Experiment (HEXTE) aboard RXTE Hynes et al.  (2000), which however does not show any cutoff. The BeppoSAX data demonstrate the presence of this feature, but also show that a power–law with an exponential cutoff does not describe the data. In addition a Compton reflection component, even if weak, is apparent in the data. These facts put strong constraints to the synchrotron model proposed by these authors. At this state of knowledge, while a synchrotron emission component appears consistent with the low energy data (below 1 keV), an Inverse Compton scattering component appears to be the best scenario for fully describing the hard X–ray energy band.

## 5 Conclusions

The column density measured in the first BeppoSAX observation is consistent with the Galactic $`N_\mathrm{H}^\mathrm{G}`$ obtained from radio measurements in the direction to the source ($`N_\mathrm{H}(1.28`$$`1.44)\times 10^{20}`$ cm-2, Dickey & Lockman 1990). However the $`N_\mathrm{H}`$ derived from the June observation (TOO3) is lower by about a factor 2. Likely a local absorption contributes to the absorption measured during the April observation (TOO1). The centroid frequency of the source QPOs is found higher during the second observation, consistently with the monitoring results found by Wood et al. (2000), but we find that in the third observation (2000 Jume 26), unexpectedly it again decreases, going back to the April 12 value Wood et al.  (2000).

The source spectra show a soft excess which is consistent with a bb emission with temperature which increases with time from $`35_4^{+3}`$ eV (TOO1) to $`52_6^{+7}`$ eV (TOO3), even though the power spectra flux variations do not favour this interpretation. The high energy part of the spectra is well fit by a Comptonization in a thermal plasma with stable Thomson optical depth of $`\tau 1`$ and electron temperature which does not significantly change with time (mean value of $`T_e=84_{15}^{+13}`$. The values of $`kT_e`$ and $`\tau `$ we find are very similar to those typical of more luminous black-hole binaries in the hard state (e.g., $`L_\mathrm{X}0.02L_\mathrm{E}`$ in Cyg X-1), whereas the X-ray luminosity in our measurement is only $`10^3L_\mathrm{E}`$. A Compton reflection component is apparent and stable, even if weak (mean value of $`\mathrm{\Omega }/2\pi =0.21_{0.04}^{+0.05}`$). This component is only detected when the reflector metallicity is left free to vary in the fits, but the BeppoSAX data, in particular those of the third observation, definitely point to a reflector with a non-solar metallicity (mean value of $`Z/Z_{}=0.13_{0.04}^{+0.06}`$), as expected by an environment at high galactic latitude, as it is the case for XTE J1118+480. Our results are consistent with the assumption, discussed by Mirabel et al. (2001), that XTE J1118+480 is the relic of an ancient massive star formed in the Galactic halo. No Fe $`K\alpha `$ line is detected ($`2\sigma `$ upper limit of $`2\times 10^4`$ cm-2 s-1).

On the basis of the fit results, a hot central disk appears the best scenario for the high energy photons. As far as the origin of the soft photons is concerned, the low amplitude of reflection and the iron line intensity would point to the assumption that they are bb radiation from the outer cold disk. However, taking into account the temporal properties, in particular the non-poissonian variance of the time variations of the soft X–ray flux, likely a relevant part of them have a different origin, likely synchrotron emission internal to the hot disk.

We wish to thank Sera Markoff for useful comments to the paper. The BeppoSAX satellite is a joint program of Italian (ASI) and Dutch (NIVR) space agencies. We acknowledge ASI for supporting this research. FF also aknowledge a financial support from the Ministry of University and Scientific Research of Italy (COFIN 2000 and 2002). AAZ acknowledges support from the Foundation for Polish Science and KBN grants 5P03D00821, 2P03C00619P1,2 and PBZ-KBN-054/P03/2001.


text:
# Hardness as Randomness: A Survey of Universal DerandomizationResearch supported by NSF Award CCR-0098197 and USA-Israel BSF Grant 97-00188.

## 1. Introduction

The use of random choices in algorithms has been a suprisingly productive idea. Many problems that have no known efficient deterministic algorithms have fast randomized algorithms, such as primality and polynomial identity testing. But to what extent is this seeming power of randomness real? Randomization is without doubt a powerful algorithm design tool, but does it dramatically change the notion of efficient computation?

To formalize this question, consider $`BPP`$, the class of problems solvable by bounded error probabilistic polynomial time algorithms. It is possible that $`P=BPP`$, i.e., randomness never solves new problems. However, it is also possible that $`BPP=EXP`$, i.e., randomness is a nearly omnipotent algorithmic tool.

Unlike for $`Pvs.NP`$, there is no consensus intuition concerning the status of $`BPP`$. However, recent research gives strong indications that adding randomness does not in fact change what is solvable in polynomial-time, i.e., that $`P=BPP`$. Surprisingly, the problem is strongly connected to circuit complexity, the question of how many operations are required to compute a function.

A priori, possibilities concerning the power of randomized algorithms include:

1. Randomization always helps for intractable problems, i.e., $`EXP=BPP`$.
2. The extent to which randomization helps is problem-specific. It can reduce complexity by any amount from not at all to exponentially.
3. True randomness is never needed, and random choices can always be simulated deterministically, i.e., $`P=BPP`$.

Either of the last two possibilities seem plausible, but most consider the first wildly implausible. However, while a strong version of the middle possibility has been ruled out, the implausible first one is still open. Recent results indicate both that the last, $`P=BPP`$, is both very likely to be the case and very difficult to prove.

More precisely:

1. Either no problem in $`E`$ has strictly exponential circuit complexity or $`P=BPP`$. This seems to be strong evidence that, in fact, $`P=BPP`$, since otherwise circuits can always shortcut computation time for hard problems.
2. Either $`BPP=EXP`$, or any problem in $`BPP`$ has a deterministic sub-exponential time algorithm that works on almost all instances. In other words, either randomness solves every hard problem, or it does not help exponentially, except on rare instances. This rules out strong problem-dependence, since if randomization helps exponentially for many instances of some problem, we can conclude that it helps exponentially for all intractible problems.
3. If $`BPP=P`$, then either the permanent problem requires super-polynomial algebraic circuits or there is a problem in $`NEXP`$ that has no polynomial-size Boolean circuit. That is, proving the last possibility requires one to prove a new circuit lower bound, and so is likely to be difficult.

The above are joint work with Kabanets and Wigderson, and use results from many others.

All of these results use the hardness-vs-randomness paradigm introduced by Yao \[Yao82\]: Use a hard computational problem to define a small set of “pseudo-random” strings, that no limited adversary can distinguish from random. Use these “pseudo-random” strings to replace the random choices in a probabilistic algorithm. The algorithm will not have enough time to distinguish the pseudo-random sequences from truly random ones, and so will behave the same as it would given random sequences.

In this paper, we give a summary of recent results relating hardness and randomness. We explain how the area drew on and contributed to coding theory, combinatorics, and structural complexity theory. We will use a very informal style. Our main objective is to give a sense of the ideas in the area, not to give precise statements of results. Due to space and time limitations, we will be omitting a vast amount of material. For a more complete survey, please see \[Kab02\].

## 2. Models of computation and complexity classes

The $`P`$ vs. $`BPP`$ question arises in the broader context of the robustness of models of computation. The famous Church-Turing Thesis states that the formal notion of recursive function captures the conceptual notion of computation. While this is not in itself a mathematical conjecture, it has been supported by theorems proving that various ways of formalizing “computability”, e.g., Turing Machines and the lambda calculus, are in fact equivalent.

When one considers complexity as well as computability, it is natural to ask if a model also captures the notion of computation time. While it became apparant that exact computation time was model-dependent, simulations between models almost always preserved time up to a polynomial. The time-restricted Church-Turing thesis is that any two reasonable models of computation should agree on time up to polynomials; equivalently, that the class of problems decideable in polynomial time be the same for both models. For many natural models, this is indeed the case, e.g. RAM computation, one-tape Turing machines, multi-tape Turing machines, and Cobham’s axioms all define the same class $`P`$ of poly-time decideable problems.

Probabilistic algorithms for a long time were the main challenge to this time-restricted Church-Turing thesis. If one accepts the notion that making a fair coin flip is a legitimate, finitely realizable computation step, then our model of poly-time computation seems to change. For example, primality testing \[SS79, Rab80\] and polynomial identity testing \[Sch80, Zip79\] are now polynomial-time, whereas we do not know any deterministic polynomial-time algorithms. The $`P`$ vs. $`BPP`$ question seeks to formalize the question of whether this probabilistic model is actually a counter-example, or whether there is some way to simulate randomness deterministically.

As a philisophical question, the Church-Turing Thesis has some ambiguities. We can distinguish at least two variants: a conceptual thesis that the standard model captures the conceptual notion of computation and computation time, and a physical thesis that the model characterizes the capabilities of physically-implementable computation devices. In the latter interpretation, quantum physics is inherrently probabilistic, so probabilistic machines seem more realistic than deterministic ones as such a characterization.

Recently, researchers have been taking this one step further by studying models for quantum computation. Quantum computation is probably an even more serious challenge to the time-limited Church-Turing thesis than probabilistic computation. This lies beyond the scope of the current paper, except to say that we do not believe that any analagous notion of pseudo-randomness can be used to deterministically simulate quantum algorithms. Quantum computation is intrinsically probabilistic; however, much of its power seems to come from interference between various possible outcomes, which would be destroyed in such a simulation.

### 2.1. Complexity classes

We assume familiarity with the standard deterministic and non-deterministic computation models (see \[Pap94\] for background.) To clarify notation, $`P=`$$`DTIME(n^{O(1)})`$ is the class of decision problems solvable in deterministic polynomial time, $`E=DTIME(2^{O(n)})`$ is the class of such problems decideable in time exponential in the input length, and $`EXP=DTIME(2^{n^{O(1)}})`$ is the class of problems solvable in time exponential in a polynomial of the input length. $`NP,NE,`$ and $`NEXP`$ are the analogs for non-deterministic time. If $`C_1`$ and $`C_2`$ are complexity classes, we use $`CoC_1`$ to denote the class of complements to problems in $`C_1`$, and $`C_1^{C_2}`$ to represent the problems solvable by a machine of the same type as normally accept $`C_1`$, but which is also allowed to make oracle queries to a procedure for a fixed language in $`C_2`$. ( This is not a precise definition, and to make it precise, we would usually have to refer to the definition of $`C_1`$. However, it is also usually clear from context how to do this.) The polynomial hierarchy $`PH`$ is the union of $`NP,\mathrm{\Sigma }_2^P=NP^NP,\mathrm{\Sigma }_3^P=NP^{\mathrm{\Sigma }_2^P},\mathrm{}`$.

A probabilistic algorithm running in $`t(|x|)`$ time is an algorithm $`A`$ that uses, in addition to its input $`x`$, a randomly chosen string $`r\{0,1\}^{t(n)}`$. Thus, $`A(x)`$ is a probability distribution on outputs $`A(x,r)`$ as we vary over all strings $`r`$. We say that $`A`$ recognizes a language $`L`$ if for every $`xL`$, $`Prob[A(x,r)=1]>2/3`$ and every $`xL`$, $`Prob[Ax,r=1]<1/3`$, where probabilities are over the random tape $`r`$. $`BPP`$ is the class of languages recognized by polynomial-time probabilistic algorithms.

The gap between probabilities for acceptance and rejection ensures that there is a statistically significant difference between accepting and rejecting distributions. Setting the gap at 1/3 is arbitrary; it could be anything larger than inverse polynomial, and smaller than $`1`$ an inverse exponential, without changing the class $`BPP`$. However, it does mean that there are probabilistic algorithms, perhaps even useful ones, that do not accept any language at all. Probabilistic heuristics might clearly accept on some inputs, clearly reject on others, but be undecided sometimes.

To handle this case, we can introduce a stronger notion of simulating probabilistic algorithms than solving problems in $`BPP`$. Let $`A`$ be any probabilistic algorithm. We say that a deterministic algorithm $`B`$ solves the promise problem for $`A`$ if, $`B(x)=1`$ whenever $`Prob[A(x,r)=1]>2/3`$ and $`B(x)=0`$ whenever $`Prob[A(x,r)=1]<1/3`$. Note that, unlike for $`BPP`$ algorithms, there may be inputs on which $`A`$ is basically undecided; for these $`B`$ can output either $`0`$ or $`1`$. We call the class of promise problems for probabilistic polynomial time machines $`PromiseBPP`$. Showing that $`PromiseBPPP`$ is at least as strong and seems stronger than showing $`BPP=P`$. (See \[For01, KRC00\] for a discussion.)

As happens frequently in complexity, the negation of a good definition for “easy” is not a good definition for “hard”. While $`EXP=BPP`$ is a good formalization of “Randomness always helps”, $`BPP=P`$ is less convincing as a translation of “Randomness never helps”; $`PromiseBPPP`$ is a much more robust statement along these lines.

$`\mathrm{\#}P`$ is the class of counting problems for polynomail-time verifiable predicates. i.e., For each poly-time predicate $`B(x,y)`$ and polynomial $`p`$, the associated counting problem is: given input $`x`$, how many $`y`$ with $`|y|=p(|x|)`$ satisfy $`B(x,y)=1`$? Valiant showed that computing the permanent of a matrix is $`\mathrm{\#}P`$-complete \[Val79\], and Toda showed that $`PHP^{\mathrm{\#}P}`$ \[Toda\].

A class that frequently arises in proofs is $`MA`$, which consists of languages with probabilistically verifiable proofs of membership. Formally, a language $`L`$ is in $`MA`$ if there is a predicate $`B(x,y,r)`$ in $`P`$ and a polynomial $`p`$ so that, if $`xL`$, $`y|y|=p(|x|)`$ so that $`Prob_{r_U\{0,1\}^{p(|x|}}[B(x,y,r)=1]>2/3`$ and if $`xL`$, $`y,|y|=p(|x|)`$, $`Prob_{r_U\{0,1\}^{p(|x|}}[B(x,y,r)=1]<1/3`$. Although $`MA`$ combines non-determinism and probabilism, there is no direct connection known between derandomizing $`BPP`$ and derandomizing $`MA`$. This is because if $`xL`$, there still may be some poorly chosen witnesses $`y`$ which are convincing to $`B`$ about 1/2 the time. However, derandomizing $`PromiseBPP`$ also derandomizes $`MA`$, because we don’t need a strict guarantee.

###### Lemma 1.

Let $`T(n)`$ be a class of time-computable functions closed under composition with polynomials. If $`PromiseBPPNTIME[T(n)]`$ then $`MANTIME[T(n)]`$ .

### 2.2. Boolean and algebraic circuits

The circuit complexity of a finite function measures the number of primitive operations needed to compute the function. Starting with the input variables, a circuit computes a set of intermediate values in some order. The next intermediate value in the sequence must be computed as a primitive operation of the inputs and previous intermediate values. One or more of the values are labelled as outputs; for one output circuits this is without loss of generality the last value to be computed. The size of a circuit is the number of values computed, and the circuit complexity of a function $`f`$, $`Size(f)`$, is the smallest size of a circuit computing $`f`$.

Circuit models differ in the type of inputs and the primitive operations. Boolean circuits have Boolean inputs and the Boolean functions on 1 or 2 inputs as their primitive operations. Algebraic circuits have inputs taking values from a field $`G`$ and whose primitive operations are addition in $`G`$, multiplication in $`G`$, and the constants $`1`$ and $`1`$. Algebraic circuits can only compute polynomials. Let $`f_n`$ represent the function $`f`$ restricted to inputs of size $`n`$ We use the notation $`P/poly`$ to represent the class of functions $`f`$ so that the Boolean circuit complexity of $`f_n`$ is bounded by a polynomial in $`n`$; we use the notation $`AlgP/poly`$ for the analagous class for algebraic circuits over the integers.

Circuits are non-uniform in that there is no a priori connection between the circuits used to compute the same function on different input sizes. Thus, it is as if a new algorithm can be chosen for each fixed input size. While circuits are often viewed as a combinatorial tool to prove lower bounds on computation time, circuit complexity is also interesting in itself, because it gives a concrete and non-asymptotic measure of computational difficulty.

## 3. Converting hardness to pseudorandomness

To derandomize an algorithm $`A`$, we need to, given $`x`$, estimate the fraction of strings $`r`$ that cause probabilistic algorithm $`A(x,r)`$ to output 1. If $`A`$ runs in $`t(|x|)`$ steps, we can construct an approximately $`t(|x|)`$ size circuit $`C`$ which on input $`r`$ simulates $`A(x,r)`$. So the problem reduces to: given a size $`t`$ circuit $`C(r)`$, estimate the fraction of inputs on which it accepts. Note that solving this circuit-estimation problem allows us to derandomize $`PromiseBPP`$ as well as $`BPP`$.

We could solve this by searching over all $`2^t`$ $`t`$-bit strings, but we’d like to be more efficient. Instead, we’ll search over a specially chosen small sample set $`S=\{r_1,\mathrm{}r_s\}`$ of such strings. The average value over $`r_iS`$ of $`C(r_i)`$ approximate the average over all $`r`$’s for any small circuit $`C`$. This is basically the same as saying that the task of distinguishing between a random string and a member of $`S`$ is so computationally difficult that it lies beyond the abilities of size $`t`$ circuits. We call such a sample set pseudo-random. Pseudo-random sample sets are usually described as the range of a function called a pseudo-random generator. This made sense for the original constructions, which had cryptographic motivations, and where it was important that $`S`$ could be sampled from very quickly \[BM, Yao82\]. However, we think the term pseudo-random generator for hardness vs. randomness is merely vestigial, and in fact has misleading connotations, so we will use the term pseudo-random sample set.

We want to show the existence of a function with small

Since we want distinguishing members of $`S`$ to be hard for all small circuits, we need to start with a problem $`f`$ of high circuit complexity, say $`Size(f)t^c`$ for some constant $`c>0`$. We assume that we have or compute the entire truth table for $`f`$.

For the direct applications, we’ll obtain $`f`$ as follows. Start with some function $`FE`$ defined on all input sizes, where $`F_\eta `$ is has circuit size at least $`H(\eta )`$ for a super-polynomial function $`H`$. Pick $`\eta `$ so that $`H(\eta )t^c`$ and let $`f=F_\eta `$. Note that $`t^{o(1)}\eta >\mathrm{log}t`$. Since $`FE`$, we can construct the truth-table for $`f`$ in time exponential in $`\eta `$, which means polynomial time in the size of the truth-table, $`n=2^\eta `$.

Other applications, in later sections, will require us to be able to use any hard function, not necessarily obtained from a fixed function in $`E`$.

We then construct from $`f`$ the pseudo-random sample set $`S_f\{0,1\}^t`$. Given the truth table of $`f`$, we list the members of $`S_f`$ in as small a deterministic time as possible. It will almost always be possible to do so in time polynomial in the number of such elements, so our main concern will be minimizing the size of $`S_f`$. We then need to show that no $`t`$ gate circuit can distinguish between members of $`S_f`$ and truly random sequences. We almost always can do so in a very strong sense: given a test $`T`$ that distinguishes $`S_f`$ from the uniform distribution, we can produce a size $`t^{c1}`$ size circuit using $`T`$ as an oracle, $`C^T`$, computing $`f`$. If such a test were computable in size $`t`$, we could then replace the oracle with such a circuit, obtaining a circuit of size $`t^c`$ computing $`f`$, a contradiction.

The simulation is: Choose $`\eta `$. Construct the truth table of $`f=F_\eta `$. Construct $`S_f`$. Run $`A(x,r_i)`$ for each $`r_iS_f`$. Return the majority answer. In almost all constructions, the dominating term in the simulation’s time is the size of $`S_f`$. In the most efficient constructions, making the strongest hardness assumption, $`H(\eta )2^{\mathrm{\Omega }(\eta )}`$, \[IW97, STV01\] obtain constructions with $`|S_f|=n^{O(1)}=t^{O(1)}`$. This gives us the following theorem:

###### Theorem 2.

If there is an $`FE`$ with $`Size(F_\eta )2^{\mathrm{\Omega }(\eta )}`$ then $`P=BPP`$.

\[Uma02\] gives an optimally efficient construction for any hardness, not just exponential hardness.

### 3.1. The standard steps

The canonical outline for constructing the pseudo-random sample set was first put together in \[BFNW93\]; however, each of their three steps was at least implicit in earlier papers. Later constructions either improve one of the steps, combine steps, or apply the whole argument recursively. However, a conceptual break-through that changed the way researchers looked at these steps is due to \[Tre01\] and will be explored in more detail in the next section.

1. Extension and random-self-reduction. Construct from $`f`$ a function $`\widehat{f}`$ so that, if $`\widehat{f}`$ has a circuit that computes its value correctly on almost all inputs, then $`f`$ has a small circuit that is correct on all inputs.
This is usually done by viewing $`f`$ as a multi-linear or low-degree polynomial over some field of moderate characteristic (poly in $`\eta `$). Then that polynomial can be extrapolated to define it at non-Boolean inputs, giving the extension $`\widehat{f}`$. If we have a circuit that is almost always correct, we can produce a probabilistic circuit that is always correct as follows. To evaluate $`\widehat{f}`$ at $`v`$, pick a point $`w`$ at random, and evaluate the almost always correct circuit at random points on the line $`l=v+xw`$. Since any point is on exactly one line with $`v`$, these points are uniform, and chances are the circuit is correct on these points. $`\widehat{f}`$ restricted to $`l`$ can be viewed as a low-degree polynomial in the single variable $`x`$. Thus, we can interpolate this polynomial, and use its value at $`x=0`$ to give us the value $`\widehat{f}(v)`$. (\[BF90\] is the first paper we know with this construction.)
The key parameter that influences efficiency for this stage is $`\widehat{\eta }`$, since the size of the truth-table for $`\widehat{f}`$ is $`\widehat{n}=2^{\widehat{\eta }}`$. Ideally, $`\widehat{\eta }O(\eta )`$, so that $`\widehat{n}n^{O(1)}`$, and we can construct $`\widehat{f}`$ in polynomial-time.
2. Hardness Amplification: From $`\widehat{f}`$, construct a function $`\overline{f}`$ on inputs of size $`\overline{\eta }`$ so that, from a circuit that can predict $`\overline{f}`$ with an $`ϵ`$ advantage over guessing, we can construct a circuit that computes $`\widehat{f}`$ on almost all inputs.
The prototypical example of a hardness amplification construction is the exclusive-or lemma \[Yao82, Le1\]. Here $`\overline{f(y_1y_2\mathrm{}y_k)}=\widehat{f}(y_1)\widehat{f}(y_2)\mathrm{}\widehat{f}(y_k)`$. Efficiency for this stage is mostly minimizing $`\widehat{\eta }`$. The $``$ construction above is not particularly efficient, so much work went into more efficient amplification.
3. Finding quasi-independent sequences of inputs. Now we have a function whose outputs are almost as good as random bits at fooling a size-limited guesser. However, we need many output bits that look mutually random. In this step, a small sets of input vectors $`V`$ is constructed so that for $`(v_1,\mathrm{}v_t)_UV`$, guessing $`\overline{f}`$ on $`v_i`$ is hard and in some sense independent of the guess for $`v_j`$.
Then the sample set will be defined as: $`S=\{(\overline{f}(v_1),\mathrm{}\overline{f}(v_t))|(v_1,\mathrm{}v_t)V\}`$
The classical construction for this step is from \[NW94\]. This construction starts with a design, a family of subsets $`D_1,..D_t[1,..\mu ],|D_i|=\overline{\eta }`$, and $`|D_iD_j|\mathrm{\Delta }`$ for $`ij`$. Then for each $`w\{0,1\}^\mu `$ we construct $`v_1,\mathrm{}v_t`$, where $`v_i`$ is the bits of $`w`$ in $`D_i`$, listed in order. Intuitively, each $`v_i`$ is “almost independent” of the other $`v_j`$, because of the small intersections. More precisely, if a test predicts $`\widehat{f}(v_i)`$ from the other $`v_j`$, we can restrict the parts of $`w`$ outside $`D_i`$. Then each restricted $`v_j`$ takes on at most $`2^\mathrm{\Delta }`$ values, but we haven’t restricted $`v_i`$ at all. We can construct a circuit that knows these values of $`\widehat{f}`$ and uses them in the predictor.
The size of $`S_f`$ is $`2^\mu `$, so for efficiency we wish to minimize $`\mu `$. However, our new predicting circuit has size $`2^\mathrm{\Delta }poly(t)`$, so we need $`\mathrm{\Delta }O(\mathrm{log}t)`$. Such designs are possible if and only if $`\mu \mathrm{\Omega }(\overline{\eta }^2/\mathrm{\Delta })`$. Thus, the construction will be poly-time if we can have $`\overline{\eta }=O(\eta )=O(\mathrm{log}t)`$.

## 4. Extractors, Graphs, and Hardness vs. Randomness

As mentioned before, \[Tre01\] changed our persective on hardness vs. randomness. We mentioned earlier that it was plausible that nature had truly probabilistic events. But is it plausible that we can physically construct a perfect fair coin? Many physical sources of randomness have imperfections and correlations. From the strong versions of hardness vs. randomness constructions, we can simulate a randomized algorithm without making the assumption that perfect random bits are available. Say we are simulating a randomized algorithm using $`t`$ perfect random bits. (We don’t need to have a time bound for the algorithm). Let $`T`$ be the set of random sequences on which the algorithm accepts.

Assume we have a physical source outputting $`n`$ bits, but all we know about it is that no single output occurs more than $`2^{t^{c+1}}`$ of the time, i.e., that it has min-entropy at least $`t^{c+1}`$. Treating the output of the source as a function $`f`$ on $`\eta =\mathrm{log}n`$ bits, we construct the sample set $`S_f`$, and simulate the algorithm on the sample set. The min-entropy and a simple counting argument suffices to conclude that most outputs do not have small circuits relative to $`T`$. Therefore, most outputs of the source have about the right number of neighbors in $`T`$, and so our simulation works with high probability.

This connection has been amazingly fruitful, leading to better constructions of extractors as well as better hardness vs. randomness results.

This construction is also interesting from the point of view of quasi-random graphs. Think globally. Instead of looking at the sample set construction on a single function $`f`$, look at it on all possible functions.

This defines a bipartite graph, where on the right side, we have all $`2^{2^\eta }=2^n`$ functions on $`\eta `$ bits, and on the left side, we have all $`t`$ bit strings; the edges are between each function $`f`$ and the members of the corresponding sample set $`S_f`$. Let $`T`$ be any subset of the left side. Then we know that any function $`f`$ that has many more or fewer than $`s|T|/2^t`$ neighbors in $`T`$ has small circuit complexity relative to $`T`$. In particular, there cannot be too many such functions. Contrapositively, any large set of functions must have about the right number of neighbors in $`T`$. Thus, we get a combinatorially interesting construction of an extremely homogenous bipartite graph from any hardness vs. randomness result.

### 4.1. The steps revisited

Once we look at the hardness vs. randomness issue from the point of view of extracting randomness from a flawed source, we can simplify our thoughts about the various steps. Any particular bits, and even most bits, from a flawed random source might be constant, because outputs might tend to be close in Hamming distance. This problem suggests its own solution: Use an error correcting code first. Then any two outputs are far apart, so most bit positions will be random. In fact, in retrospect, what the first two steps of the standard hardness vs. randomness method are doing is error-correcting the function. We do not care very much about rate, unless the rate is not even inverse polynomial. However, we want to be able to correct even if there is only a slight correlation between the recieved coded message and the actual coded message. It is information-theoretically impossible to uniquely decode under such heavy noise, but it is sometimes possible to list decode, producing a small set of possible messages. At the end of the hardness amplification stage, this is in fact what we have done to the function.

However, there are some twists to standard error- correction that make the situation unique. Most interestingly, we need decoding algorithms that are super-fast, in that to compute any particular bit of the original message can be done in poly-log time, assuming random access to the bits of the coded message. This kind of local decodability was implicit in \[AS97\], and applied to hardness vs. randomness in \[STV01\].

In retrospect, much of the effort in hardness-vs-randomness constructions has been in making locally list-decodeable error-correcting codes in an ad hoc manner. \[STV01\] showed that even natural ways of encoding can be locally list-decodeable. However, there might be some value in the ad hoc approaches. For example, many of the constructions assume the input has been weakly error-corrected, and then do a further construction to increase the amount of noise tolerated. Thus, these constructions can be viewed as error-correction boosters: codes where, given a code word corrupted with noise at a rate of $`\gamma `$, one can recover not the original message, but a message of lower relative noise, i.e. Hamming distance $`\delta n`$ from the original message, where $`\delta <\gamma `$. These might either be known or of interest to the coding community.

## 5. Hardness from derandomization

Are circuit lower bounds necessary for derandomization? Some results that suggested they might not be are \[IW98\] and \[Kab01\], where average-case derandomization or derandomization vs. a deterministic adversary was possible based on a uniform or no assumption. However, intuitively, the instance could code a circuit adversary in some clever way, so worst-case derandomization based on uniform assumptions seemed difficult. Recently, we have some formal confirmation of this: Proving worst-case derandomization results automatically prove new circuit lower bounds.

These proofs usually take the contrapositive approach. Assume that a large complexity class has small circuits. Show that randomized computation is unexpectedly powerful as a result, so that the addition of randomness to a class jumps up its power to a higher level in a time hierarchy. Then derandomization would cause the time hierarchy to collapse, contradicting known time hierarchy theorems.

An example of unexpected power of randomness when functions have small circuits is the following result from \[BFNW93\]:

###### Theorem 3.

If $`EXPP/poly`$, then $`EXP=MA`$.

This didn’t lead directly to any hardness from derandomization, because $`MA`$ is the probabilistic analog of $`NP`$, not of $`P`$. However, combining this result with Kabanet’s easy witness idea (\[Kab01\]), \[IKW01\] managed to extend it to $`NEXP`$.

###### Theorem 4.

If $`NEXPP/poly`$, then $`NEXP=MA`$.

Since as we observed earlier, derandomizing $`PromiseBPP`$ collapses $`MA`$ with $`NP`$, it does follow that full derandomization is not possible without proving a circuit lower bound for $`NEXP`$.

###### Corollary 5.

If $`PromiseBPPNE`$, then $`NEXPP/poly`$.

A very recent unpublished observation of Kabanets and Impagliazzo is that the problem of, given an arithmetic circuit $`C`$ on $`n^2`$ inputs, does it compute the permanent function. is in $`BPP`$. This is because one can set inputs to constants to set circuits that should compute the permanent on smaller matrices, and then use the Schwartz-Zippel test (\[Sch80, Zip79\]) to test that each function computes the expansion by minors of the previous one. Then assume $`PermAlgP/poly`$. It follows that $`PHP^{Perm}NP^{BPP}`$, because one could non-deterministically guess the algebraic circuit for Perm and then verify one’s guess in $`BPP`$. Thus, if $`BPP=P`$ (or even $`BPPNE`$) and $`PermAlgP/poly`$, then $`PHNE`$. If in addition, $`NEP/poly`$, we would have $`CoNEXP=NEXP=MAPHNE`$, a contradiction to the non-deterministic time hierarchy theorems. Thus, if $`BPPNE`$, either $`PermAlgP/poly`$ or $`NEP/poly`$. In either case, we would obtain a new circuit lower bound.

## 6. Conclusions

This is an area with a lot of “good news/bad news” results. While the latest results seem pessimistic about finally resolving the $`P`$ vs. $`BPP`$ question, the final verdict is still out. Perhaps $`NE`$ is high enough in complexity that proving a circuit lower bound there would not require a major breakthrough, only persistance. Perhaps derandomization will lead to lower bounds, not the other way around. In any case, derandomization seems to be a nexus of interesting connections between complexity and combinatorics.


text:
# Bounds for the size of sets with the property 𝐷(𝑛)

## 1 Introduction

Let $`n`$ be a nonzero integer. A set of $`m`$ positive integers $`\{a_1,a_2,\mathrm{},a_m\}`$ is called *a $`D(n)`$-$`m`$-tuple* (or *a Diophantine $`m`$-tuple with the property $`D(n)`$*) if $`a_ia_j+n`$ is a perfect square for all $`1i<jm`$.

Diophantus himself found the $`D(256)`$-quadruple $`\{1,\mathrm{\hspace{0.17em}33},\mathrm{\hspace{0.17em}68},\mathrm{\hspace{0.17em}105}\}`$, while the first $`D(1)`$-quadruple, the set $`\{1,\mathrm{\hspace{0.17em}3},\mathrm{\hspace{0.17em}8},\mathrm{\hspace{0.17em}120}\}`$, was found by Fermat (see ). In 1969, Baker and Davenport  proved that this Fermat’s set cannot be extended to a $`D(1)`$-quintuple, and in 1998, Dujella and Pethő  proved that even the Diophantine pair $`\{1,3\}`$ cannot be extended to a D(1)-quintuple. A famous conjecture is that there does not exist a $`D(1)`$-quintuple. We proved recently that there does not exist a $`D(1)`$-sextuple and that there are only finitely many, effectively computable, $`D(1)`$-quintuples (see ).

The question is what can be said about the size of sets with the property $`D(n)`$ for $`n1`$. Let us mention that Gibbs  found several examples of Diophantine sextuples, e.g. $`\{99,\mathrm{\hspace{0.17em}315},\mathrm{\hspace{0.17em}9920},\mathrm{\hspace{0.17em}32768},\mathrm{\hspace{0.17em}44460},\mathrm{\hspace{0.17em}19534284}\}`$ is a $`D(2985984)`$-sextuple.

Define

$$M_n=sup\{|S|:S\text{ has the property }D(n)\}.$$

Considering congruences modulo $`4`$, it is easy to prove that $`M_n=3`$ if $`n2(mod4)`$ (see ). On the other hand, if $`n2(mod4)`$ and $`n\{4,3,1,\mathrm{\hspace{0.17em}3},\mathrm{\hspace{0.17em}5},\mathrm{\hspace{0.17em}8},\mathrm{\hspace{0.17em}12},\mathrm{\hspace{0.17em}20}\}`$, then $`M_n4`$ (see ).

In , we proved that $`M_n32`$ for $`|n|400`$ and

$$M_n<267.81\mathrm{log}|n|(\mathrm{log}\mathrm{log}|n|)^2\text{for }|n|>400.$$

The purpose of the present paper is to improve this bound for $`M_n`$, specially in the case $`|n|>400`$. We will remove the factor $`(\mathrm{log}\mathrm{log}|n|)^2`$, and also the constants will be considerably smaller.

The above mentioned bounds for $`M_n`$ were obtained in  by considering separately three types (large, small and very small) of elements in a $`D(n)`$-$`m`$-tuple. More precisely, let

$`A_n`$ $`=`$ $`sup\{|S[|n|^3,+\mathrm{}|:S\text{ has the property }D(n)\},`$
$`B_n`$ $`=`$ $`sup\{|Sn^2,|n|^3|:S\text{ has the property }D(n)\},`$
$`C_n`$ $`=`$ $`sup\{|S[1,n^2]|:S\text{ has the property }D(n)\}.`$
In , it was proved that $`A_n21`$ and $`B_n<0.65\mathrm{log}|n|+2.24`$ for all nonzero integers $`n`$, while $`C_n<265.55\mathrm{log}|n|(\mathrm{log}\mathrm{log}|n|)^2+9.01\mathrm{log}\mathrm{log}|n|`$ for $`|n|>400`$ and $`C_n5`$ for $`|n|400`$. The combination of these estimates gave the bound for $`M_n`$.

In the estimate for $`A_n`$, a theorem of Bennett  on simultaneous approximations of algebraic numbers was used in combination with a gap principle, while a variant of the gap principle gave the estimate for $`B_n`$. The bound for $`C_n`$ (number of ”very small” elements) was obtained using the Gallagher’s large sieve method  and an estimate for sums of characters.

In the present paper, we will significantly improve the bound for $`C_n`$ using a result of Vinogradov on double sums of Legendre’s symbols. Let us mention that Vinogradov’s result, in a slightly weaker form, was used recently, in similar context, by Gyarmati  and Sárközy & Stewart . We will prove the following estimates for $`C_n`$.

###### Proposition 1

If $`|n|>400`$, then $`C_n<11.006\mathrm{log}|n|`$. If $`|n|10^{100}`$, then $`C_n<8.37\mathrm{log}|n|`$.

More detailed analysis of the gap principle used in  will lead us to the slightly improved bounds for $`B_n`$.

###### Proposition 2

For all nonzero integers $`n`$ it holds $`B_n<0.6114\mathrm{log}|n|+2.158`$. If $`|n|>400`$, then $`B_n<0.6071\mathrm{log}|n|+2.152`$.

By combining Propositions 1 and 2 with the above mentioned estimate for $`A_n`$, we obtain immediately the following estimates for $`M_n`$.

###### Theorem 1

If $`|n|400`$, then $`M_n31`$. If $`|n|>400`$, then $`M_n<15.476,\mathrm{log}|n|`$. If $`|n|10^{100}`$, then $`M_n<9.078\mathrm{log}|n|`$.

## 2 Three lemmas

###### Lemma 1 (Vinogradov)

Let $`p`$ be an odd prime and $`\mathrm{gcd}(n,p)=1`$. If $`A,B\{0,1,\mathrm{},p1\}`$ and

$$T=\underset{xA}{}\underset{yB}{}\left(\frac{xy+n}{p}\right),$$

then $`|T|<\sqrt{p|A||B|}`$.

Proof. See \[19, Problem V.8.c)\].

###### Lemma 2 (Gallagher)

If all but $`g(p)`$ residue classes mod $`p`$ are removed for each prime $`p`$ in a finite set $`𝒮`$, then the number of integers which remain in any interval of length $`N`$ is at most

$$\left(\underset{p𝒮}{}\mathrm{log}p\mathrm{log}N\right)/\left(\underset{p𝒮}{}\frac{\mathrm{log}p}{g(p)}\mathrm{log}N\right)$$
(1)
provided the denominator is positive.

Proof. See .

###### Lemma 3

If $`\{a,b,c\}`$ is a Diophantine triple with the property $`D(n)`$ and $`ab+n=r^2`$, $`ac+n=s^2`$, $`bc+n=t^2`$, then there exist integers $`e`$, $`x`$, $`y`$, $`z`$ such that

$$ae+n^2=x^2,be+n^2=y^2,ce+n^2=z^2$$

and

$$c=a+b+\frac{e}{n}+\frac{2}{n^2}(abe+rxy).$$

Proof. See \[9, Lemma 3\].

## 3 Proof of Proposition 1

Let $`Nn^2`$ be a positive integer. Since $`|n|>400`$, we have $`N>1.610^5`$. Let $`D=\{a_1,a_2,\mathrm{},a_m\}\{1,2,\mathrm{},N\}`$ be a Diophantine $`m`$-tuple with the property $`D(n)`$. We would like to find an upper bound for $`m`$ in term of $`N`$. We will use the Gallagher’s sieve (Lemma 2). Let

$$𝒮=\{p:p\text{ is prime, }\mathrm{gcd}(n,p)=1\text{ and }pQ\},$$

where $`Q`$ is sufficiently large. For a prime $`p𝒮`$, let $`C`$ denotes the set of integers $`b`$ such that $`b\{0,1,2,\mathrm{},p1\}`$ and there is at least one $`aD`$ such that $`ba(modp)`$. Then $`\left(\frac{xy+n}{p}\right)\{0,1\}`$ for all distinct $`x,yC`$. Here $`\left(\frac{.}{p}\right)`$ denotes the Legendre symbol. If $`0C`$, then $`\left(\frac{n}{p}\right)=1`$. For given $`xC\{0\}`$, we have $`\left(\frac{xy_0+n}{p}\right)`$ for at most one $`y_0C`$. If $`yx,y_0`$, then $`\left(\frac{xy+n}{p}\right)=1`$. Therefore,

$`T`$ $`=`$ $`{\displaystyle \underset{x,yC}{}}\left({\displaystyle \frac{xy+n}{p}}\right)={\displaystyle \underset{xC}{}}\left({\displaystyle \underset{yC}{}}\left({\displaystyle \frac{xy+n}{p}}\right)\right)`$
$``$ $`{\displaystyle \underset{xC}{}}(|C|3)|C|(|C|3).`$
On the other hand, Lemma 1 implies

$$T<|C|\sqrt{p}.$$

Thus, $`|C|<\sqrt{p}+3`$ and we may apply Lemma 2 with

$$g(p)=\mathrm{min}\{\sqrt{p}+3,p\}.$$

Let us denote the numerator and denominator from (1) by $`E`$ and $`F`$, respectively. By \[17, Theorem 9\], we have

$$E=\underset{p𝒮}{}\mathrm{log}p\mathrm{log}N<\theta (Q)<1.01624Q.$$

The function $`f(x)=\frac{\mathrm{log}x}{\mathrm{min}\{\sqrt{x}+3,x\}}`$ is strictly decreasing for $`x>25`$. Also, if $`Q118`$, then $`f(p)f(Q)`$ for all $`pQ`$.

For $`p𝒮`$ it holds $`\mathrm{gcd}(n,p)=1`$. This condition comes from the assumptions of Lemma 1. However, we will show later that $`n`$ can be divisible only by small proportion of the primes $`Q`$. Assume that $`n`$ is divisible by at most 5% of primes $`Q`$. Then, for $`Q118`$, we have

$`F`$ $``$ $`{\displaystyle \underset{p𝒮}{}}f(p)\mathrm{log}N{\displaystyle \frac{\mathrm{log}Q}{\sqrt{Q}+3}}|𝒮|\mathrm{log}N`$ (2)
$``$ $`{\displaystyle \frac{\mathrm{log}Q}{\sqrt{Q}+3}}{\displaystyle \frac{19}{20}}\pi (Q)\mathrm{log}N>{\displaystyle \frac{0.95Q}{\sqrt{Q}+3}}\mathrm{log}N.`$
Since $`F`$ has to be positive in the applications of Lemma 2, we will choose $`Q`$ of the form

$`Q=c_1\mathrm{log}^2N.`$
We have to check whether our assumption on the proportion of primes which divide $`n`$ is correct. Suppose that $`n`$ is divisible by at least 5% of the primes $`Q`$. Then $`|n|p_1p_2\mathrm{}p_{\pi (Q)/20}`$, where $`p_i`$ denotes the $`i`$-th prime. By \[17, 3.5 and 3.12\], we have $`p_{\pi (Q)/20}>R`$, where

$$R=\frac{1}{20}\frac{Q}{\mathrm{log}Q}\mathrm{log}\left(\frac{1}{20}\frac{Q}{\mathrm{log}Q}\right).$$

Assume that $`c_16`$. Then $`Q>860`$ and $`R>11.77`$. From \[17, 3.16\], it follows that

$$\mathrm{log}|n|>\underset{pR}{}\mathrm{log}p>R\left(1\frac{1.136}{\mathrm{log}R}\right).$$
(3)
Furthermore, $`\frac{1}{20}\frac{Q}{\mathrm{log}Q}>Q^{0.273}`$ and $`R>0.0136Q`$. Hence, (3) implies $`\mathrm{log}R>7.793`$ and therefore

$$\mathrm{log}N2\mathrm{log}|n|>0.01466Q0.08796\mathrm{log}^2N,$$

contradiction the assumption that $`N>1.610^5`$.

Therefore, we have that $`n`$ is divisible by at most 5% of the primes $`Q`$, and hence we have justifies the estimate (2).

Under the assumption that $`c_16`$, the inequality (2) implies

$$F>0.861\sqrt{Q}\mathrm{log}N=(0.861\sqrt{c_1}1)\mathrm{log}N$$

and

$$\frac{E}{F}<\frac{1.017c_1}{0.861\sqrt{c_1}1}\mathrm{log}N.$$

For $`c_1=6`$ we obtain

$$\frac{E}{F}<5.503\mathrm{log}N.$$
(4)
Assume now that $`N10^{200}`$ and $`c_14`$. Then $`Q>848303`$ and we can prove in the same manner as above that $`n`$ is divisible by at most 1% of the primes $`Q`$. This fact implies

$$\frac{E}{F}<\frac{1.017c_1}{0.986\sqrt{c_1}1}\mathrm{log}N.$$

For $`c_1=4.11`$ we obtain

$$\frac{E}{F}<4.185\mathrm{log}N.$$
(5)
Setting $`N=n^2`$ in (4) and (5), we obtain the statements of Proposition 1.

## 4 Proof of Proposition 2

We may assume that $`|n|>1`$. Let $`\{a,b,c,d\}`$ be a $`D(n)`$-quadruple such that $`n^2<a<b<c<d`$. We apply Lemma 3 on the triple $`\{b,c,d\}`$. Since $`b>n^2`$ and $`be+n^20`$, we have that $`e0`$. If $`e=0`$, then $`d=b+c+2\sqrt{bc+n}<2c+2\sqrt{c(c1)+n}<4c`$, contradicting the fact that $`d>4.89c`$ (see \[9, Lemma 5\]).

Hence $`e1`$ and

$$d>b+c+\frac{2bc}{n^2}+\frac{2t\sqrt{bc}}{n^2}.$$
(6)
Lemma 3 also implies

$$ca+b+2r.$$
(7)
From $`r^2ab\sqrt[4]{ab}`$ and $`ab30`$ it follows that $`r>0.96a`$, and (7) implies $`c>3.92a`$. Similarly, $`bc42`$ implies $`t>0.969\sqrt{bc}`$ and, by (6), $`d>b+c+3.938\frac{bc}{n^2}>4.938c+b`$.

Assume now that $`\{a_1,a_2,\mathrm{},a_m\}`$ is a $`D(n)`$-$`m`$-tuple and $`n^2<a_1<a_2<\mathrm{}<a_m<|n|^3`$. We have

$`a_3>3.92a_1,a_i>4.938a_{i1}+a_{i2},\text{for }i=4,5,\mathrm{},m.`$
Therefore, $`a_m>\alpha _ma_1`$, where the sequence $`(\alpha _k)`$ is defined by

$`\alpha _k=4.938\alpha _{k1}+\alpha _{k2},\alpha _2=1,\alpha _3=3.92.`$ (8)
Solving the recurrence (8), we obtain $`\alpha _k\beta \gamma ^{k3}`$, with $`\beta 3.964355`$, $`\gamma 5.132825`$. More precisely,

$$|\alpha _k\beta \gamma ^{k3}|<\frac{1}{\beta \gamma ^{k3}}.$$

From $`|n|^31a_m>\alpha _ma_1\alpha _m(n^2+1)`$, it follows $`\alpha _m|n|\frac{1}{|n|}`$ and $`\beta \gamma ^{m3}<|n|`$. Hence,

$$m<\frac{1}{\mathrm{log}\gamma }\mathrm{log}|n|+3\frac{\mathrm{log}\beta }{\mathrm{log}\gamma }.$$
(9)
For the above values of $`\beta `$ and $`\gamma `$ we obtain

$$m<0.6114\mathrm{log}|n|+2.158.$$

Assume now that $`|n|>400`$. Then $`bc>ab>400^4`$, which implies $`c>3.999999a`$ and $`d>4.999999c+b`$. Therefore, in this case the relation (9) holds with $`\beta 4.042648`$, $`\gamma 5.192581`$, and we obtain

$$m<0.6071\mathrm{log}|n|+2.152.$$

###### Remark 1

The constants in Theorem 1 can be improved, for large $`|n|`$, by using formula (2.26) from  in the estimate for the sum $`_{p𝒮}f(p)`$. In that way, it can be proved that for every $`\epsilon >0`$, $`F>(2\epsilon )\sqrt{Q}\mathrm{log}N`$ holds for sufficiently large $`Q`$.

Also, in the proof of Proposition 2, for sufficiently large $`|n|`$ we have $`c>(4\epsilon )a`$ and $`d>(5\epsilon )c+b`$, which leads to $`B_n<\left({\displaystyle \frac{1}{\mathrm{log}(\frac{5+\sqrt{29}}{2})}}+\epsilon \right)\mathrm{log}|n|`$.

These results imply that for every $`\epsilon >0`$ there exists $`n(\epsilon )`$ such that for $`|n|>n(\epsilon )`$ it holds

$$M_n<\left(2+\frac{1}{\mathrm{log}(\frac{5+\sqrt{29}}{2})}+\epsilon \right)\mathrm{log}|n|.$$

Acknowledgements. The author is grateful to the referees for valuable comments, and in particular for pointing out a gap in the proof of Proposition 1 in the first version of the manuscript.

Department of Mathematics
University of Zagreb
Bijenička cesta 30, 10000 Zagreb
Croatia
E-mail address: duje@math.hr