text:
# References

The US 2000-2003 Market Descent: Clarifications

Didier Sornette $`^{\text{1}\text{,}\text{2}\text{,}\text{3}}`$ and Wei-Xing Zhou $`^\text{1}`$

1. Institute of Geophysics and Planetary Physics, University of California, Los Angeles, CA 90095
2. Department of Earth and Space Sciences, University of California, Los Angeles, CA 90095
3. Laboratoire de Physique de la Matière Condensée, CNRS UMR 6622 and Université de Nice-Sophia Antipolis, 06108 Nice Cedex 2, France

## Abstract

In a recent comment \[Johansen A 2003 An alternative view, Quant. Finance 3: C6-C7, cond-mat/0302141\], Anders Johansen has criticized our methodology and has questioned several of our results published in \[Sornette D and Zhou W-X 2002 The US 2000-2002 market descent: how much longer and deeper? Quant. Finance 2: 468-81, cond-mat/0209065\] and in our two consequent preprints \[cond-mat/0212010, physics/0301023\]. In the present reply, we clarify the issues on (i) the analogy between rupture and crash, (ii) the Landau expansion, “double cosine” and Weierstrass-type solutions, (iii) the symmetry between bubbles and anti-bubbles and universality, (iv) the condition of criticality, (v) the meaning of “bullish anti-bubbles”, (vi) the absolute value of $`t_ct`$, (vii) the fractal log-periodic power law patterns, (viii) the similarity between the Nikkei index in 1990-2000 and the S&P500 in 2000-2002 and (ix) the present status of our prediction.

In a recent comment , Anders Johansen has criticized our methodology and has questioned several of our results published in this journal  and in our two consequent preprints . We regret the controversial tone adopted in  but welcome this opportunity to clarify our work further.

In a series of works starting with  (see  and references therein), financial bubbles have been defined as regimes in which the stock market exhibits an unsustainable super-exponential growth, that can be characterized quantitatively as a genuine critical phenomenon with specific log-periodic power-law (LPPL) signatures. The underlying mechanism is proposed to be found in imitation between investors and their herding behavior, which lead to self-reinforcement positive feedbacks.

In , Johansen and Sornette introduced the concept of “anti-bubbles” to describe decaying LPPL price trajectories that are sometimes found to follow very large market highs. Based on models of imitation between investors and their cooperative herding behavior , it was realized that speculation and imitation also occur during bearish markets, leading to price trajectories that seem approximately symmetric to the accelerating speculative bubbles ending in crashes, under a time reversal transformation ($`t_cttt_c`$ where $`t_c`$ is a critical time corresponding to the end of the bubble or the start of the anti-bubble). The two first examples of anti-bubbles were found  in the Japanese Nikkei stock index from 1990 to 1998, whose analysis led to the successful prediction of two trend reversals , and in the Gold future prices after 1980, both after their all-time highs. Several other examples have been described in the Russian stock market  and in emergent and western markets . Our recent work  adds many other cases that all started in the summer of 2000.

Status of the rupture analogy. More precise and probably more relevant than the analogy with material rupture is the concept of a finite-time singularity as developed in , which emerges from positive feedbacks. The concept of a finite-time singularity is the counterpart in the time-domain of the concept of criticality. The fight between positive and negative feedbacks is the key concept underlying the proposal of LPPL signatures of speculative bubbles and anti-bubbles in stock markets .

Landau expansion, “double cosine” and Weierstrass-type solutions. A. Johansen criticizes our use of the “double cosine” function on the basis that a sound theoretical justification is lacking, while he puts his faith in the Landau expansion introduced in  and extended up to third order in . Actually, the full solution of the simplest renormalization group equation for a critical point has been analyzed in depth in  and provides an improvement of these approaches in the form of Weierstrass-type functions of the form

$$\mathrm{ln}[p(t)]=A+B\tau ^m+\mathrm{}\left(\underset{n=1}{\overset{N}{}}C_n\mathrm{e}^{i\psi _n}\tau ^{s_n}\right),$$
(1)
where $`\tau =|tt_c|`$, $`s_n=m+in\omega `$ and $`\mathrm{}()`$ is the real part operator. The existence of different phases $`\psi _n`$ incriminated by A. Johansen can be seen to derive naturally from the Mellin transform of the regular part of the renormalization group equation. In simple words, the different phases $`\psi _n`$ embody an information on the mechanisms of interactions between investors. There is thus a sound theoretical justification for such a phase shift (understand $`\psi _2\psi _1`$) between the first and the second harmonics (understand the first two terms $`n=1`$ and $`2`$ of the expansion (1)). When the phases have certain relationships (phase locking), a discrete hierarchy of critical times emerge, which has been found to describe very well the US stock market since the summer of 2000 . A. Johansen’s misconception can probably be traced to the incorrect idea that the phase of the simple cosine formula (case $`N=1`$) has no financial meaning because it can be gauged away in a redefinition of the time scale.

Symmetry between bubbles and anti-bubbles and universality. From a mechanistic view point, we advocate the existence of anti-bubbles from the idea that the fight between positive and negative feedbacks is operative both in bullish as well as in bearish markets . From a descriptive view point, our recent works  just follow Johansen and Sornette’s previous works , which introduced the concept of an “anti-bubble” from a symmetry perspective. A symmetry may have distinct consequences. It can be used to justify the same functional expressions both for bubbles and anti-bubbles. Thus, in the mathematical expressions, the symmetry between bubbles and anti-bubbles amounts to changing $`t_ct`$ for bubbles to $`tt_c`$ for anti-bubbles. Here, we should stress that, if a LPPL anti-bubble follows a LPPL bubble (which is not the general case), the critical time $`t_c`$ is not generally the same. A noteworthy exception is the Russian stock market around 1997 . We report in  dozens of anti-bubbles in many different stock markets worldwide which started almost all in August 2000, that is, 4 months later than the end of the “new economy” bubble and its crash in April 2000. Another case is Chile around 1994-1995, where the bubble ended in February 1994 while the anti-bubble started in July 1995 .

A. Johansen would like that the symmetry between bubbles and anti-bubbles should be extended so that the same log-periodic angular frequency $`\omega `$ describes both cases. He thus invokes more than just a functional but a numerical symmetry. We think that this belief may be too rigid at the present time when we still have a rather limited understanding of this complex problem. We propose an open-minded approach more adapted to a learning phase. It is correct that, for LPPL bubbles, there is rather well-defined cluster of values for $`\omega 6.36\pm 1.56`$ and for $`m0.33\pm 0.18`$ as reported in  (see equation (4) of ). For anti-bubbles in the USA S&P and in many EU markets, we find almost the same value $`\omega 12`$. This value is comparable with those obtained for the anti-bubbles in the Latin-American markets and Western markets in the 1990’s . It is interesting that this value $`\omega 12`$ is approximately twice the most probably value $`\omega `$ found for LPPL bubbles. Does it correspond to a log-periodicity different from that of bubbles? Probably not for the following reason: we have found in  that both $`\omega `$ and $`2\omega `$ were quite significant in the anti-bubbles, including the Nikkei case that started in 1990. Due to the probable variation of the strength of nonlinear processes in the stock markets, it can be expected that the amplitudes of the first and second harmonics can be different from one realization to the next. Within the renormalization group framework, the relative strength of the first and second harmonics is controlled by the regular part  which describes the specific interactions of the investors that led to a given realization of the market. Let us add that the importance of the role of log-periodic harmonics has been demonstrated for turbulence , where the evidence is much stronger. For the emergent markets, the LPPL signatures are not as significant as for the major western markets, as noted already in . A. Johansen also notes the $`\omega `$’s found for different worldwide markets are not peaked and may be due to noise. Instead, we think that this is due to a possible lack of sufficient robustness of the fits, which does not diminish the evidence for log-periodicity but suggests to interpret with care the specific reported values. This can be seen from the fact that, if we impose the additional condition in our fits that the different worldwide markets exhibit an anti-bubble with the same critical time $`t_c`$, we find that their angular log-periodic frequency $`\omega `$ are very close to each other. The quasi-simultaneity of the starting time and the ensuing strong synchronization of the anti-bubbles exhibited by the major stock markets in the world, which has been documented in , provides an additional justification for the use of the same critical time $`t_c`$.

Criticality. A. Johansen criticizes our abandoning of the constraint $`m<1`$ as a necessary condition to qualify the existence of a bubble or anti-bubble, suggesting that we have renounced the concept of criticality. There are several issues here that need to be distinguished. First, our many tests performed by the present authors and previously by A. Johansen with D. Sornette (reported as the work that Johansen performed with Matt Lee in ) show that the condition on the exponent $`m`$ is much less effective in the detection of bubbles than a condition on $`\omega `$ for instance (see also discussion in Chapter 9 of ). This is one justification for abandoning any constraint on this rather sensitive parameter to “let the data speak.” Second, finding values of $`m1`$ does not amount to an absence of criticality, because the equation is still critical (that is, it exhibits a singularity) due to the presence of the theoretically infinite hierarchy of log-periodic oscillations. In other words, criticality remains present due to the imaginary part $`\omega `$ of the exponent $`s_n=m+in\omega `$ of the LPPL (see equation (1)) as long as it is non-zero, whatever the value $`m`$ of its real part. Third, we can relax the condition $`0<m<1`$ for the present purpose because our LPPL formulas describe only a finite range of the time interval: it is well-known that true singularities do not exist in nature as friction, finite-size effects and other regularization mechanisms come into play close enough to the theoretical mathematical singularity. What is important is the ability of the LPPL formula to describe with good accuracy a large range of the data, not necessarily the very close proximity to the phantom singularity. In this respect, we refer to the rather detailed discussion of the effect of finite-size effects on singularities presented in .

“Bullish anti-bubbles”. In our analysis of the largest stock markets in the world, we have identified six examples which give a positive coefficient $`B`$ in (1). In particular, the statistical significance of this result is very high for Australia, Mexico and Indonesia. This regime $`B>0`$ is different from the normal bubble and anti-bubble cases previously reported for which $`B<0`$. This regime $`B>0`$ has been coined “bullish anti-bubbles”  to describe the joint features of decelerating log-periodic oscillations and of an overall increasing price. In contradiction with Johansen’s remark, this regime $`B>0`$ does not lead to infinite prices in a finite time but describes a long-term growth which turns out to be slower than standard exponential growth. The same remark applies for $`m>1`$.

Absolute value of $`t_ct`$. In complete disagreement with A. Johansen’s remark, our use of $`|t_ct|`$ in our fits to locate the critical time $`t_c`$ does not abandon “another restriction coming from the data.” Rather than adding a degree of freedom, this approach instead removes an arbitrariness previously present in the fitting procedure in choosing the time interval over which the fit is performed. Rather than determining an approximate starting time and/or estimating the critical time $`t_c`$ by the location of the largest market peak, using $`|t_ct|`$ makes the fits almost independent of the chosen starting time. This improved robustness has been documented in details by our many numerical tests presented in .

Fractal LPPL patterns. As we quoted in , Drozdz et al.  have reported the existence of LPPL within LPPL within LPPL, using eye-balling in a single case. As mentioned by A. Johansen , he with D. Sornette studied this phenomenon rather systematically about a year earlier but never published due to the rather marginal quality level of the results. In , we mentioned that the worldwide anti-bubble started in the summer of 2000 has also left its imprint on the Japanese market, leading to an anti-bubble within the large scale anti-bubble that started in January 1990. This possibility of structures within structures is expected on general grounds from the renormalization group model of LPPL singularities leading to Weierstrass-like solutions (see ). The problem is that such observation is not very robust when one goes to small time scales, probably due to the fact that “noise” and idiosyncratic news affect more and more strongly the price time series, the smaller is the time scale of observation. However, we note that our report  of a $`2.5`$ year long anti-bubble decorating a $`13`$ year long anti-bubble of the Nikkei index should have a special status because both time scales are sufficiently long to compare with the time span over which previous LPPL have been qualified. A. Johansen himself acknowledges that “the real success was with a LPPL analysis on time scales of one to two years of data.” Our report in  passes this criterion and should thus be considered at a level different from the published  and unpublished analyses at smaller time scales.

Similarity between the Nikkei index in 1990-2000 and the S&P500 in 2000-2002. Johansen downplays the “remarkable similarity” we as well as many observers noticed between these two markets. First, the factor of $`2`$ in the value of the log-periodic frequency is explained by the competition between the two first harmonics $`n=1`$ and $`n=2`$ in (1), as we explained above. In , we stress the remarkable similarity in the two markets with respect to the existence of two harmonics in both cases. Second, the Nikkei did go through a now well-recognized speculative bubble culminating at the end of December 1989, even if its price trajectory does not qualify as a very good LPPL. We note in this vain that an anti-bubble is usually the follow-up of very high prices, not necessarily of a LPPL bubble. Even in the case of the US market, we stressed above that the critical time of the bubble occurred $`4`$ months before the critical time of the following anti-bubble. This again stresses that one should exercise caution in twinning rigidly in time the occurrence of bubbles and of anti-bubbles. Third, Johansen argues that the analysis of the Nikkei was based on $`9`$ years of data compared with less than $`3`$ years for the US market which, he argues, makes these two cases apart. Johansen forgets to mention is that the $`9`$ years of Nikkei data required the use of a log-periodic formula extended to third-order in the Landau expansion mentioned above while the analysis in  of the US market used only the first-order formula and its extension with a second harmonics. Johansen and Sornette’s initial analysis of the Nikkei data in  showed that, similarly to the US market, the first three years of the Nikkei time series could be adequately described by the first-order formula. It is by extending to large time horizon that it was necessary to use the higher-order terms in the Landau expansion. It is also interesting to note that there was a global anti-bubble starting in January 1994 in the major western stock markets , which also bears similarities to the present worldwide 2000-2003 anti-bubble case . The global anti-bubble in the mid-1990’s lasted less than one year, while the 2000-2003 anti-bubble is still alive on many more markets, resulting in a much higher statistical significance level. There is thus no qualitative nor quantitative difference between the Japanese and USA data sets. We would like to add that the similarity between the Nikkei in 1990-2000 and the S&P500 in 2000-2002 can be further strengthened by paralleling the economic and financial distresses of the two countries, as explained in .

Status of the prediction. Finally, “The proof of the pudding is in the eating.” The ultimate evidence attesting the true nature of something lies in the verification of ex-ante predictions by future data. We have offered the predictions for the future of the US market in  and of many worldwide markets in  as an important additional step for testing the LPPL hypothesis. These predictions for the S&P500 US market are compared with the realized values and are also updated monthly (go to the URL http://www.ess.ucla.edu/faculty/sornette/ and then click on “The future of the USA stock market”). Recall that the prediction published in  was made at the end of August 2002. At the time of the latest comparison, March 18 2003, one can see that we correctly predicted the recovery of the market until the end of 2002 but missed the severe drop that followed, which was probably due to the uncertainties associated with the coming war with Iraq. We should also stress that these last months have exhibited a very large volatility, leading to deviations from our prediction that are however comparable in magnitude with previous deviations in the in-sample period. Our predictions are fundamentally “low-frequency” in nature and cannot obviously capture the detailed idiosyncratic volatility. The comparison between our predictions and the realized price should thus be made at the time scale of the prediction horizon, that is, from August 2002 till summer 2004. We stand by our prediction that the market should appreciate somewhat and then resume its overall bearish anti-bubble descent.

Acknowledgments: This work was partially supported by the James S. Mc Donnell Foundation 21st century scientist award/studying complex system.


format: text

text:
# Photon number resolution using time-multiplexed single-photon detectors

## I Introduction

There has been considerable interest recently in the development of photon detectors that are capable of resolving the number $`n`$ of photons present in an incident pulse. Photon number-resolving detectors of this kind are needed for a linear optics approach to quantum computing Knill et al. (2001); Franson et al. (2002), for example, and they may have other applications as well Gilchrist et al. (2003), such as conditional state preparation Kok et al. (2001); Lee et al. (2001). Here we describe a simple time-multiplexing technique that allows ordinary single-photon detectors to be used as photon number-resolving detectors. The achievable performance of these devices is comparable to that of cryogenic devices Kim et al. (1999); Takeuchi et al. (1999); Cabrera et al. (1998) that are being developed specifically for number-resolving applications. Detectors based on an atomic vapor have also been proposed Imamoḡlu (2002); James and Kwiat (2002).

Photon number-resolving detectors can be characterized in part by the probability $`P(m|n)`$ that $`m`$ photons will be detected in a pulse that actually contains $`n`$ photons. For linear optics quantum computing, it is essential that $`P(n|n)`$ be as close to unity as possible. As one might expect, this requires the single-photon detection efficiency $`\eta `$ to be as large as possible in order to maximize the probability of detecting all of the photons present in a pulse. Silicon avalanche photodiodes (APDs) operating in the visible have a relatively large value of $`\eta `$ and a small dark count rate, but they only produce a single output pulse regardless of the number of incident photons. The time-multiplexing technique described here avoids that limitation while retaining the large value of $`\eta `$ and other potential advantages associated with the use of commercially-available APDs.

The basic idea of the time-multiplexing technique is to divide the incident pulse into $`N`$ separate pulses of approximately equal amplitude that are displaced in time by a time interval $`\mathrm{\Delta }t`$ that is larger than the detector dead time $`\tau `$. The probability that one of the divided pulses contains two or more photons becomes negligibly small for $`Nn`$, in which case the fact that an APD can only produce a single output pulse is no longer a limitation.

Our implementation of such a time-multiplexed detector is illustrated in Figure 1. An incident pulse propagating in a single-mode optical fiber was divided equally into two paths using a 50/50 coupler. The difference $`L`$ in path lengths was sufficiently large that the propagation times differed by more than the detector dead time. The two pulses were then recombined at a second 50/50 coupler and split equally into two more paths differing in length by $`2L`$, which results in four pulses all separated in time by $`\mathrm{\Delta }t`$. This process was repeated once more with a path-length difference of $`4L`$, after which a fourth 50/50 coupler split the pulses again and directed them into one of two silicon APDs. The net result was the creation of $`N=16`$ pulses of approximately equal amplitude. Unlike earlier approaches involving detector arrays Song et al. (1990); Paul et al. (1996); Kok and Braunstein (2001); Kok (2003), this technique requires only two detectors, and it avoids the need for optical switches and a storage loop Banaszek and Walmsley (2003); Řeháček et al. (2003); Haderka et al. (2003).

The remainder of this paper is organized as follows: In Section II, we present a theoretical analysis of the expected performance of a time-multiplexed detector (TMD) as a function of the detector efficiency and photon losses. The analysis makes clear that high detector efficiency is needed for any photon number resolving detector, including the TMD and various cryogenic detectors under development Kim et al. (1999); Takeuchi et al. (1999); Cabrera et al. (1998). Section III describes an experimental implementation of a TMD and the results obtained using coherent state inputs. A summary and conclusions are presented in Section IV.

## II Theoretical Analysis

In the most likely application of a time-multiplexed detector, an incident pulse will contain an unknown number $`n`$ of photons and the TMD is intended to measure the value of $`n`$. Since the measurement process destroys any coherence between states with different values of $`n`$, it is sufficient to consider an incident number state (Fock state) with a specific value of $`n`$ and then calculate the response of the detector in the form of the probability distribution $`P(m|n)`$. The response to an incident coherent state will be considered in the next section.

It is therefore assumed that a number state $`|n=(1/\sqrt{n!})(\widehat{a}^{})^n|0`$ is incident on the initial 50/50 coupler, where the operator $`\widehat{a}^{}`$ creates a photon in the incident mode and $`|0`$ is the vacuum state. The effects of the first coupler can be described by the operator transformation

$$\widehat{a}^{}(\widehat{a}_s^{}+\widehat{a}_l^{})/\sqrt{2}$$
(1)
where the operators $`\widehat{a}_s^{}`$ and $`\widehat{a}_l^{}`$ create photons in the shorter and longer paths, respectively. Similar transforms can be applied to represent the remainder of the 50/50 couplers. After these transformations, the state vector will involve $`n`$ photons distributed over 16 different modes.

It is important to include the effects of photon loss, which will degrade the performance of the device in a way that is similar to the effects of limited detector efficiency. The largest source of loss is absorption and scattering in the optical fiber. This can be described by the fraction $`f`$ of the incident power that is transmitted through a length $`L`$ of fiber. (In the experiments described in the next section, $`f`$ has an approximate value of 0.97). The transmission through the fiber section of length $`2L`$ is then $`f^2`$, etc. In order to simplify the analysis, it was assumed that the short sections of fiber have negligible length and that losses in the fiber connections are also negligible.

Losses in the optical fiber were included in the analysis by inserting an additional fiber coupler into each of the longer loops. The reflection and transmission coefficients of these couplers were adjusted to give a transmission probability of $`f`$ (or the appropriate power of $`f`$) for each of the sections of fiber. An additional field mode corresponding to the photons removed from the loop by these couplers for each of the pulses was included in the state vector, which increased the total number of modes from 16 to 23. The effects of photon loss could then be taken into account by applying operator transformations analogous to Eq. 1.

After all of the operator transformations had been applied, the state vector contained a large number of terms corresponding to all of the ways in which $`n`$ photons can be distributed over the 23 modes. As a result, mathematica was used to sum the contribution of each term in the state vector to the probability distribution $`P(m|n)`$. In doing so, it was assumed that $`P_0=(1\eta )^q`$, where $`P_0`$ is the probability that a detector will detect no photons if $`q`$ photons are incident upon it. (This ignores any possible correlations between the effects of multiple photons.) The probability $`P_A`$ that a detector will detect at least one photon and produce an output pulse is then given by $`P_A=1P_0`$. Having determined the values of $`P_0`$ and $`P_A`$ for each of the detectors, it was straightforward to calculate the probability of obtaining $`m`$ detection events and add that contribution to the probability distribution $`P(m|n)`$ for each term in the state vector.

This analysis includes the fact that each of the 16 pulses will have different probabilities of reaching the detector, since they all travel through different lengths of optical fiber. In the limit of no loss ($`f1`$) and perfect detection efficiency ($`\eta 1`$), the TMD is mathematically equivalent to a lossless multiport device, whose output properties can be obtained analytically Paul et al. (1996). Our numerical calculations agree with the analytic results in that limit.

Figure 2 shows the results of this analysis for the case of two incident photons ($`n=2`$), which is a case of interest Knill et al. (2001); Pittman et al. (2001, 2002, 2003); Franson et al. (2002) in linear optics quantum computing. The detection efficiency was taken to be $`\eta =0.7`$, which is typical of commercially-available silicon APDs, while the losses were assumed to be zero ($`f=1`$) in this example. The limited value of $`N=16`$ reduces the probability of detecting the correct number of photons to $`15/16`$, while the limited detection efficiency further reduces the probability of a successful measurement to $``$45%. It can be seen that a detection efficiency of 0.7 substantially limits the ability of a TMD to resolve the number of photons present in a pulse, even for the simple case of $`n=2`$, and higher detection efficiencies will be required in order to improve the performance.

Similar results are shown in Figure 3 for the case of $`\eta =0.2`$, which is comparable to the estimated external efficiency of the superconducting detector in Ref. Cabrera et al. (1998). Detectors of that kind are mathematically equivalent to taking the limit of large N, which would increase the probability of obtaining the correct photon number by 6% $`(1/16)`$ above that shown in Figure 3. Nevertheless, it is apparent that further increases in the detection efficiency will be required.

Larger numbers of incident photons give a correspondingly smaller probability of measuring the correct value of $`n`$. As an example, Figure 4 shows the probability distribution $`P(m|n)`$ for the case of $`n=5`$, $`f=0.97`$, and $`\eta =0.43`$. These parameters correspond to the experimental apparatus described in the next section, where the reduced value of $`\eta `$ includes the combined averaged effects of input and output coupling loss, connector and splice losses, and excess losses in the fiber couplers.

More generally, the probability $`P(n|n)`$ of measuring the correct number of photons is plotted in Figure 5 as a function of the detector efficiency. For simplicity, the losses were assumed to be zero here, in which case $`P(n|n)`$ has the analytic result

$$P(n|n)=\frac{16!}{16^n(16n)!}\eta ^n\text{for}n16$$
(2)
as shown in the Appendix. In addition to the effects of limited detector efficiency, it can be seen that the limited number of secondary pulses ($`N=16`$) also has a significant effect as the value of $`n`$ increases, even for perfect detector efficiency. At telecom wavelengths, the losses in optical fibers are much smaller and it should be possible to use much larger values of $`N`$.

## III Experimental Results

In order to perform a proof-of-principle demonstration of a time-multiplexed detector, we implemented the TMD of Figure 1 using single-mode optical fiber and $`2\times 2`$ fiber couplers designed to give 50/50 reflection and transmission at a wavelength of 702 nm. Since a source of number states is not currently available for large values of $`n`$, the experiments were performed using a weak coherent state. This was intended to allow a comparison of the theory with experiment and a demonstration of the basic feasibility of the TMD approach.

The input and output ports of the TMD had FC-style connectors while all of the other connections were made using a fusion splicer in order to minimize the losses. The two detectors were commercial silicon APD single-photon detectors (Perkin-Elmer model SPCM-AQR-13) with measured deadtimes of approximately 60 ns. The length $`L`$ of the first long loop was chosen to be 22 m, which gave a delay between adjacent pulses of $`\mathrm{\Delta }t=110`$ ns, which was substantially larger than the deadtime. Short pulses (50 ps duration) were generated using an externally triggered fiber-coupled diode laser at 680 nm. A custom-made electronic circuit was used to count the total number of photon detections in a specified time window following each trigger. The triggering rate was kept sufficiently small that there was no overlap of the sequence of $`N`$ pulses from two different triggering events.

The optical fiber used for the delay loops had a 4 $`\mu `$m core, which supported single-mode propagation of visible light (610 nm to 730 nm). The attenuation at 700 nm was specified by the manufacturer to be 6 dB/km, which corresponds to a transmission factor of $`f=0.97`$. Small but significant losses also occurred in the input and output couplers, fusion splices, and excess loss in the $`2\times 2`$ fiber couplers (typically 3% each). The total transmission of the fiber multiplexing device was measured to be 0.55, averaged over all $`N`$ pulses.

The photon number distribution of the coherent state at one of the outputs of the TMD is given by a Poisson distribution:

$$P(\mu ,n)=\frac{\mu ^ne^\mu }{n!}$$
(3)
where $`\mu `$ is the mean photon number. For a perfect detector ($`\eta =1`$), $`P(\mu ,0)`$ would give the probability $`P_0`$ of detecting no photons. It can be shown from the linearity of the system that this result can be generalized to the case of an imperfect detector by replacing $`\mu `$ with $`\mu ^{}=\eta \mu `$. (The limited detection efficiency is equivalent to placing an attenuator in front of the detector.) Thus $`P_0=\mathrm{exp}(\mu ^{})`$ and $`P_A=1P_0`$, where $`P_A`$ is defined once again as the probability that a detector will detect at least one photon and produce an output pulse.

For values of $`f`$ close to 1, the losses for all $`N`$ pulses can be taken to be approximately the same without significantly affecting the distribution of the total number of counts. In that case, $`\mu ^{}=\eta l\mu _o/16`$ for each of the pulses incident on the detectors, where the transmission factor $`l`$ accounts for the average total loss in the system (measured value $`l=0.55`$), $`\eta `$ is the APD detection efficiency (typ. 0.7), and $`\mu _o`$ is the mean number of photons incident upon the TMD. The probability $`𝒫(m)`$ of obtaining exactly $`m`$ detection events (for $`m16`$) is then given by the binomial distribution

$$𝒫(m)=\frac{16!}{(16m)!m!}(P_0)^{16m}(1P_0)^m.$$
(4)
A comparison of the theoretical predictions of Eq. 4 with the experimental results from a relatively intense coherent state are shown in Figure 6. The data corresponds to a histogram of the total number of events in which $`m`$ photons were counted in an arbitrary data collection interval, which is proportional to the probability distribution $`𝒫(m)`$. The theoretical results correspond to a least-squares fit to Eq. 4 with two free parameters, a normalization constant (which reflects the length of the data collection interval) and the value of $`\mu ^{}`$, which corresponded to a best-fit value $`\eta l\mu _o=13.1`$. It can be seen that the data are in relatively good agreement with the theoretical predictions. The small discrepancies between the theory and experiment are probably due to the approximation that all 16 pulses are subject to the same loss.

Similar comparisons of the theoretical predictions and the experimental results are shown in Figure 7 for a less intense coherent state ($`\eta l\mu _o=2.65`$) and in Figure 8 for a relatively weak pulse ($`\eta l\mu _o=0.57`$). It can be seen that a TMD can provide reliable estimates of the mean number of photons in a coherent-state pulse, but it can also be seen that the observed peak in the data is substantially less than the true mean number of photons.

## IV Summary

In summary, we have described the use of time-multiplexing techniques to allow ordinary silicon avalanche photodiodes to be used as photon-number detectors. Although silicon APDs have high efficiencies and low dark counts, they only produce a single output pulse regardless of the number of photons that are incident. This difficulty can be avoided by splitting the incident pulse into a time sequence of $`N`$ weaker pulses, provided that $`Nn`$. The use of time multiplexing does lengthen the effective detector response time, which may also be of importance depending on the intended application Paul et al. (1996); Schleich and Wheeler (1987); Schleich et al. (1988); Dowling et al. (1991).

A proof-of-principle experiment was performed using optical fiber loops for the case of $`N=16`$ and a coherent state input pulse. Good agreement was observed between the theoretical predictions and the experimental results.

The calculated response of a TMD to an incident number state makes it clear that high detection efficiencies will be required in order to truly resolve the number of photons in an incident pulse. But the same comment applies to any other detector intended for photon number-resolving applications, such as the cryogenic detectors that are being developed for that purpose. The results of our analysis suggest that the most important requirement for true number-resolving detectors is a high single-photon detection efficiency; an intrinsic ability to resolve photon numbers may be of lesser importance, since that capability can also be achieved using ordinary single-photon detectors.

Finally, we would like to note that a similar device has been independently demonstrated and analyzed by Achilles *et al.* Achilles et al. (2003).

*

## Appendix A

In this Appendix, we provide a derivation of Eq. 2, and generalize it to arbitrary numbers of detected photons.

Non-classical photon statistics have been observed Mattle et al. (1995) at a multiport beam splitter when the path lengths are matched, and to describe such effects, a quantum formalism must be used (as in Section II above). In contrast, the path lengths in the TMD are far from matched, with relative delays of $`>100`$ ns. As this is two or three orders of magnitude longer than the coherence length, the possibility of photon interferences can be neglected, and the relevant detection probabilities can be calculated from classical probability theory.

Let the input mode be evenly distributed to $`N`$ output modes, so that a single photon on the input has a probability $`1/N`$ of reaching any given output mode. We further assume there are no losses, corresponding to $`f=1`$ above, so this model describes a balanced, lossless $`N`$-port. At each output mode, there is a detector with efficiency $`\eta `$. Suppose that $`n`$ photons are sent to the input. Let the probability of $`m`$ detection events ($`0mn`$) be written $`P_\eta ^N(m|n)`$. In the case of zero detections, $`P_\eta ^N(0|n)`$ is given by:

$$P_\eta ^N(0|n)=(1\eta )^n$$
(5)
which assumes that each photon fails to be detected with an independent probability of $`1\eta `$. For the case where all photons are detected, $`P_\eta ^N(n|n)`$, must include a probability of $`(\eta /N)^n`$ for each of the ways in which a photon can be detected. Since all $`n`$ photons must have gone to distinct output modes, there is a combinatoric factor which counts the number of different ways to distribute $`n`$ objects among $`N`$ bins, so that:

$$P_\eta ^N(n|n)=\left(\frac{\eta }{N}\right)^n\frac{N!}{(Nn)!}\text{for}nN.$$
(6)
Eq. 6 reduces to Eq. 2 for the special case in which $`N=16`$.

For detectors of unit efficiency ($`\eta =1`$), Paul *et al.* Paul et al. (1996) gave a recursion relation for (in our notation) $`P_{\eta =1}^N(m|n)`$, along with a closed form solution. Their results can be extended to include non-unit detection efficiency by using the recursion relation:

$$\begin{array}{cc}\hfill P_\eta ^N(m|n+1)& =P_\eta ^N(m|n)\left[(1\eta )+\frac{\eta m}{N}\right]\hfill \\ & +P_\eta ^N(m1|n)\left[(N+1m)\frac{\eta }{N}\right]\hfill \end{array}$$
(7)
where the first term on the right hand side describes an additional photon failing to be detected or else exiting in a previously occupied output mode. The second term on the right hand side describes the detection of an additional photon in a previously unoccupied output mode. In the limit $`\eta 1`$, the recursion relation Eq. 7 agrees with that given by Paul *et al.* (see Eq. 9 in Ref. Paul et al. (1996)).

Using the boundary conditions of Equations 5 and 6, the recursion relation Eq. 7 can be solved, with the result:

$$P_\eta ^N(m|n)=\left(\genfrac{}{}{0pt}{}{N}{m}\right)\underset{j=0}{\overset{m}{}}(1)^j\left(\genfrac{}{}{0pt}{}{m}{j}\right)\left[(1\eta )+\frac{(mj)\eta }{N}\right]^n$$
(8)
for $`mnN`$, where the binomial coefficient is $`\left(\genfrac{}{}{0pt}{}{N}{m}\right)N!/[m!(Nm)!]`$. The derivation of Eq. 8 is lengthy, but it can be verified that it satisfies the recursion relation.

Although Eqs. 5 through 8 were derived using classical probability theory, they give exactly the same numerical results as the field operator approach of Section II.

###### Acknowledgements.

We acknowledge useful discussions with M. T. Lamar. This work was supported by ARO, NSA, ARDA and IR&D funding.


text:
# Fluctuating particle motion during shear induced granular compaction

## Abstract

Using a refractive index matching method, we investigate the trajectories of particles in a three dimensional granular packing submitted to cyclic shear deformation. The particle motion observed during compaction is not diffusive but exhibits transient cage effect, similar to the one observed in colloidal glasses. We precisely study the statistics of the step size between two successive cycles and observe that it is proportional to the shear amplitude. The link between the microscopic observations and the macroscopic evolution of the volume fraction during compaction is discussed.

Granular material are often described as athermal systems liu98 ; danna01 . For grains greater than few microns, thermal fluctuations are negligible and play no role in the dynamics. A granular assembly can then be trapped in a metastable configuration and will not evolve unless an external perturbation such as vibration or shear is applied. The compaction of an initially loose granular sample represents a simple configuration to study the dynamics of athermal system.

Two configurations have been experimentally investigated to study granular compaction. The first one consists in imposing vertical taps to a granular packing Knight95 ; nowak98 ; josserand00 ; philippe03 . The second consists in imposing a periodic shear deformation to a sample contained in a box nicolas00 ; nicolas01 . In both cases, when the amplitude of excitation is constant (the tap intensity or the shear amplitude), a slow logarithmic relaxation towards more compact states is observed Knight95 ; philippe03 ; nicolas00 . In contrast to this slow dynamics, rapid changes in volume fraction can be observed when a sudden change in excitation is imposed josserand00 ; nicolas00 . The packing dilates (resp. compacts) when the excitation amplitude increases (resp. decreases). Moreover the system exhibits a short term memory, i.e. two packings at the same volume fraction but being prepared differently do not evolve the same way when submitted to the same excitation. The coexistence of a slow and a rapid dynamics and the observation of memory effects have motivated number of numerical or theoretical models mainly based on free volume concept and geometrical constraints coniglio96 ; caglioti97 ; barker92 ; barrat01 ; boutreux97 ; head99 . However, to our knowledge, no link has been made between the macroscopic dynamics and the microscopic structure of the packing during compaction. Does the slow and rapid dynamics correspond to different grains rearrangements? What does the memory effect mean for the particles position? In this study we address these questions by analyzing the individual motion of the grains during a cyclic shear compaction.

In thermal system like colloidal suspensions, the microscopic motion of the particles has been recently studied in detail. Using confocal microscopy, Weeks et al. weeks00 ; weeks02  have been able to follow the three dimensional trajectories of the particles in colloidal hard spheres suspensions. They have shown that for dense systems near the glass transition the particles spend most of the time trapped in localized regions or ”cages” and occasionally exhibit longer excursions. Considering the analogy often proposed between granular compaction and aging in glassy systems danna01 , one can legitimately wonder if similar microscopic behaviors are present in granular compaction.

The experimental setup is described in details in nicolas00  and is presented in Fig. 1. Spherical glass beads ($`d=3`$ mm in diameter) contained in a parallelepipedic box (7.7 cm wide, 10.2 cm deep and typically 10.5 cm high) are submitted to a periodic shear by inclining the two side walls. The top plate which applies a constant pressure on the packing is free to move vertically only. During compaction the top plate slowly goes down. The measure of its vertical position gives the bulk volume fraction. All the experiments are carried out in a quasistatic regime and the only control parameter is the amplitude of the cyclic shear measured by the maximum inclination $`\theta `$ of the side walls.

The particles are tracked during compaction using an index matching method. The material is immersed in a mixture of $`67\%`$ of turpentine and $`33\%`$ of methylnaphtalene matching the glass refractive index of the beads. The packing is then transparent and it is possible to follow few colored glass beads initially introduced in the packing (Fig. 1b). The experimental procedure is the following. The top plate being removed, the particles are gently poured in the container filled with the index matching liquid. Colored particles are then carefully introduced in the packing and the top plate is slowly put into contact with the beads. The mean initial volume fraction is typically 0.61. Once the packing is ready, the shear deformation is imposed: the side walls are successively inclined to an angle $`+\theta `$ then $`\theta `$, then put back at the vertical position. After each cycle, we measure the volume fraction from the position of the top plate and we take a front picture of the packing. The tracers locations in the x-y plan are determined from the picture using a particle tracking algorithm. The location accuracy is $`\pm 15\mu m`$.

In order to observe trajectory correlations between adjacent particles, another visualization technics is developed. Fluorescent dye is added to the mixture (with some alcohol to help dilution) and the packing is lighted with a vertical thin laser sheet in the x-y plane. One then obtains a picture where the particles appear as black disks (Fig 1c). This technics allows to study short time correlation motion but does not allow to follow particles in the long time, as they can move perpendicular to the laser plane and eventually leave it.

The first experiments are performed at a constant shear amplitude $`\theta `$. An example of the particle motion obtained for $`\theta =5.4^o`$ is presented in Fig. 2b. The plot represents the stroboscopic trajectory i.e. the successive positions of the particles measured after each shear cycle. Trajectories are first characterized by an overall decrease of the vertical coordinate as the number of cycles increases, reminiscent of the macroscopic compaction. The corresponding evolution of the volume fraction is plotted in Fig 2a. On top of this mean vertical displacement, one observes fluctuating motion characterized by ball-like regions as shown in the close-up Fig 2c. This could reveal caging process. The random motion of the particles seems to be trapped in a finite volume before escaping and being trapped again in another cage. Notice that the change of cage corresponds to a displacement quite smaller than the particle diameter (about one fourth). When compaction goes on, the time spent in a cage becomes longer and longer and the particles eventually move around a fixed position. The cage effect is reminiscent of what has been observed in colloidal glasses by Weeks et al. weeks00 ; weeks02 . The main difference here is that the system is not time invariant and evolves towards more and more compact states. Cage properties changing with time and particle experiencing only few cage changes before being trapped in its final location (between 2 and 5), we have not been able to get significant statistics about the cage sizes.

However, in order to investigate how the random motion evolves with compaction, we study the statistics of the displacement $`\mathrm{\Delta }r=\sqrt{\mathrm{\Delta }x^2+\mathrm{\Delta }y^2}`$ experienced by the particles between two successive cycles. The distribution of $`P(\mathrm{\Delta }r)`$ obtained at various stages of the compaction process are plotted in Fig. 3, the step size being normalized by the standard deviation $`\sigma `$. One observes that the distribution is slightly larger than that obtained if the $`x`$ and $`y`$ displacements were distributed according to a gaussian centered on zero (solid line in Fig. 3). This observation is again very similar to the step size statistics observed in colloidal glasses weeks02 .

Another analogy with colloidal glasses is observed when studying the correlation between two successive cycles : the random motion seems to be anti correlated. When a particle moves in one direction, it has a great probability to move in the opposite direction the next step, which is reminiscent of a cage effect. This is shown in Fig. 3b where the component $`x^{}`$ of the $`n+1^{th}`$ displacement along the direction of the $`n^{th}`$ displacement is plotted against the size $`\mathrm{\Delta }r`$ of the $`n^{th}`$ displacement. As in thermal colloidal glasses, $`x^{}`$ is statistically negative, revealing anti correlation.

The granular compaction system being not invariant in time, we study how the step size distribution varies during compaction. The different curves in Fig. 3 correspond to the distribution at different time in an experiment at $`\theta =8.1^o`$ and show that the shape of the normalized distribution does not vary much with time. However, the mean value $`<\mathrm{\Delta }r>`$ varies during the compaction as shown in Fig. 4. The mean step size $`<\mathrm{\Delta }r>`$ is plotted as a function of the volume fraction $`\mathrm{\Phi }`$ during experiments carried out for three different shear angles $`\theta `$. In the three runs, the mean step displacement first decreases down to $`\mathrm{\Phi }=0.63`$ which corresponds roughly to 500 cycles and eventually reaches a constant value for dense enough packing. The asymptotic value depends on the shear amplitude and is smaller for small $`\theta `$. An interesting observation is that once the packing is dense enough ($`\mathrm{\Phi }>0.64`$), the mean step displacement is only a function of $`\theta `$ independent of the history of the packing. This means that the same $`<\mathrm{\Delta }r>`$ is measured if the compaction is carried out at a constant $`\theta `$ or if the packing is first compacted under a shear amplitude $`\theta _1`$ and then sheared at $`\theta `$. This is shown in Fig. 5 where we plot $`<\mathrm{\Delta }r>`$ as a function of $`\theta `$ for many different experiments carried out at constant or non constant shear amplitude. The striking feature is the linear relation $`<\mathrm{\Delta }r>=\beta \theta `$ with $`\beta =8\mu m/deg`$. The higher the shear amplitude, the larger the random displacement between two cycles.

This linear relation between microscopic displacement and shear amplitude is reminiscent of the macroscopic observations of our previous study nicolas00 . When a sudden change $`\mathrm{\Delta }\theta `$ was imposed to the packing, a rapid (in less than 10 cycles) variation of volume fraction $`\mathrm{\Delta }\mathrm{\Phi }`$ was measured. $`\mathrm{\Delta }\mathrm{\Phi }`$ was found to vary linearly with $`\mathrm{\Delta }\theta `$ independently of the packing history for compacted enough packing. One can wonder if a link exists between the microscopic random motion and the macroscopic behavior.

In order to investigate this link, experiments are performed where the shear amplitude is discontinuously varied. A typical run is presented in Fig. 6. The packing is first compacted at a fixed amplitude $`\theta =8.4^o`$ for $`10^4`$ cycles and then $`\theta `$ is varied from $`10.2^o`$ to $`0.6^o`$ by step of $`1.2^o`$, the angle being kept constant during 1000 cycles. The corresponding volume fraction variation is plotted in Fig 6a. As expected from our previous study nicolas00 , successive increasing steps in volume fraction are observed. The typical microscopic behavior of a particle during this experiment is presented in Fig 6b. The volume explored by the particle during its random motion successively shrinks when the shear amplitude decreases because the mean step size $`<\mathrm{\Delta }r>`$ decreases with $`\theta `$ (Fig. 5). However, each time the shear angle changes, the other particles below the test particle experience the same decrease in their exploration volume. The result is a net downward motion observed when the angle changes. The observed volume fraction variation thus seems to result from the change in the volume randomly explored by the particles. This becomes clear when looking at the displacement of all the particles during a change in $`\theta `$ (Fig. 6c). Thanks to the laser light visualization, we are able to follow each particle in a plane when the shear angle changes from 10.4o to 1.4o. An homogeneous deformation is observed (Fig. 6c), as if when the angle decreases, all the particles deflate yielding a change in volume fraction. An estimation of the change in volume fraction can be made. Assuming that the random fluctuating motion of a particle occupies a volume of the order $`\left(d+<\mathrm{\Delta }r>\right)^3`$, the volume fraction is $`\mathrm{\Phi }=\mathrm{\Phi }_0\frac{d^3}{\left(d+<\mathrm{\Delta }r>(\theta )\right)^3}`$ where $`\mathrm{\Phi }_0`$ is a reference volume fraction. Knowing from Fig. 5 that $`<\mathrm{\Delta }r>=\beta \theta `$, a change $`\mathrm{\Delta }\theta `$ in the shear amplitude induces a volume fraction variation $`\mathrm{\Delta }\mathrm{\Phi }=3\mathrm{\Phi }_0\beta \mathrm{\Delta }\theta `$. A linear variation is predicted as observed in nicolas00  and the predicted coefficient (taking $`\mathrm{\Phi }_0=0.7`$) is $`3\mathrm{\Phi }_0\beta =\mathrm{0.56\hspace{0.33em}10}^3`$deg-1 having the right order of magnitude compared to the value $`\mathrm{1.5\hspace{0.33em}10}^3`$ deg-1 measured in nicolas00 .

All the results presented up to now are obtained for monodispersed glass beads. In this case, the compaction occurs towards crystallization nicolas00 . We have checked that the microscopic behavior does not qualitatively change when using a bidispersed material (mixture of 2 mm and 3 mm beads) which do not crystallize. Cages are still observed and the sudden change of volume fraction when changing the shear amplitude nicolas01  is correlated to a change of the mean random step size. The crystal nature of the packing then does not qualitatively influence the dynamics of the system.

In conclusion a simple scenario can be proposed for the compaction process. We have seen that the particles motion can be divided in two kinds : random motion within confined volumes or cages, whose extent is directly proportional to the shear amplitude, and occasionally longer exploration corresponding to a change of cage. We think that the slow dynamics of compaction observed in experiment at constant amplitude may be attributed to the change in cages. This changes are irreversible and push the system towards more and more compact configurations. How cage deformations occur, what is the influence of one cage rearrangement on the next ones are open questions. The cage changes certainly involve complex cooperative processes associated to modifications in the contact and force network which have not been studied here. However, we have shown that the rapid change of volume fraction observed when changing the amplitude is of different nature: it is simply related to the change of the cage size, without important structural changes. This means that this variation of volume is reversible and can be recovered by coming back to the previous amplitude of excitation. The existence of these two processes which affect differently the packing volume fraction, explains that memory effects can be observed.

We thank F. Ratouchniak for his technical assistance.


text:
# Iron and Nickel line properties in the X–ray reflecting region of the Circinus Galaxy

## 1 Introduction

The Circinus galaxy, at the distance of about 4 Mpc, is the closest and brightest among Compton-thick Seyfert 2 galaxies (see Matt 2002a and Matt et al. 2000 for reviews). Its nuclear 2–10 keV X–ray spectrum is dominated by reflection from a spatially unresolved region (which hereinafter we will call the ‘torus’, Antonucci 1993) with a size less than about 15 pc (Sambruna et al. 2001a). Most of the line spectrum (Sambruna et al. 2001b; Guainazzi et al. 1999; Matt et al. 1996) can be explained in terms of a single, mildly ionized reflector (Bianchi et al. 2001) even if a second, more ionized reflecting region is required to account for the faint He–like Fe K$`\alpha `$ line detected by the $`Chandra/HETG`$ (Sambruna et al. 2001b). Given the brightness of the source and the dominance of the cold reflection component, the Circinus Galaxy is ideal to study the physical, chemical and geometrical properties of the torus.

Above 10 keV, the nuclear emission becomes visible, piercing through a cold absorber with $`N_\mathrm{H}=4\times 10^{24}`$ cm-2 (Matt et al. 1999). It is natural to identify the absorber with the reflector, as the latter should be Compton–thick, as implied by its spectrum (e.g. Matt et al. 2003) and by the relative flux of the Compton Shoulder (Bianchi et al. 2002; Matt 2002b; this paper), i.e. the part of the line profile due to photons which are scattered before escaping the matter. With this assumption, from the modeling of the line spectrum a value of about 0.2 pc for the inner radius of the torus can be derived (Bianchi et al. 2001).

In this Letter we analyze and discuss the hardest part of the spectrum with the aim of studying the iron and nickel properties, taking advantage of the unprecedented sensitivity of XMM–$`Newton`$ at these energies. A complete spectral and spatial analysis is beyond the scope of this paper, and is deferred to a future work.

## 2 Data reduction

The Circinus Galaxy was observed by XMM–$`Newton`$ for about 110 ks on August 6 and 7 2001. The EPIC p-n and MOS1 cameras were operated in full frame mode while the EPIC MOS2 was operated in large window mode. ODF files were downloaded from the public archive and processed using version 5.4.1 of the SAS software. Further screening for soft proton flares and residual hot pixels was performed using procedures described in Baldi et al. (2002). The effective exposure times after cleaning are 75, 77 and 70 ks for MOS1, MOS2 and p-n respectively. For our spectral analysis we used pattern 0 to 12 events for MOS1 and MOS2 while for p-n we accumulated separately single and double events spectra. Spectra for all three cameras were extracted from a 30′′ radius circle centered on the source peak. Two nearby sources lie within this radius, but were excluded by excising circles with a 7′′ radius centered on the respective peaks. Inspection of a 6-10 keV image shows that the intensity at the peak for these sources is less then a 10-15% of the Circinus peak intensity. Exclusion of their core is therefore sufficient to make contamination very small. Background spectra for the 3 cameras were extracted from annuli with bounding radii 90′′ and 150′′ centered on the source, after having verified that in these regions no detectable sources were present. Redistribution matrices and effective areas were generated using the rmfgen and arfgen tools. Above $``$2 keV the standard energy binning for matrices generated by rmfgen is 50 eV for p-n and 5 eV for MOS. Because our aim is to perform detailed spectroscopy on Fe and Ni lines observed between 6 and 8 keV, we have chosen a finer binning of 1 eV for both MOS and p-n matrices. The effective areas were of course generated with the same binning. For the fitting procedure, we rebinned the data to have at least 20 counts per bin, in order to ensure applicability of $`\chi ^2`$ statistics.

## 3 Data analysis and results

In Fig. 1 the (p-n, single event) spectrum of the nucleus above 5 keV is shown. Three emission lines are obviously present, readily identified with iron K$`\alpha `$ and K$`\beta `$ as well as nickel K$`\alpha `$. The expected energies of these lines, assuming neutral atoms, are: 6.400 keV (actually a doublet, composed by a 6.391 keV and a 6.405 keV line); 7.058 keV (a doublet, with energies of 7.057 keV and 7.058 keV) and 7.472 keV (a doublet, with energies of 7.461 keV and 7.478 keV). All line energies are from Kaastra & Mewe (1993). For each doublet, the intensity ratio between the two lines is 1:2, and the given energies are the weighted mean.

In the following, unless explicitely stated, we will adopt the cosmic element abundances given by Anders & Grevesse (1989), which are 4.68$`\times `$10-5 for iron and 1.78$`\times `$10-6 for nickel (by number with respect to hydrogen); and the fluorescent yields given by Kaastra & Mewe (1993), which for neutral atoms are: 0.304 (iron K$`\alpha `$); 0.038 (iron K$`\beta `$); 0.368 (nickel K$`\alpha `$).

In the following, we will also assume that the absorbing material is dust-free. In fact, from the observed NH of 4$`\times 10^{24}`$ cm-2 a value of $`A_\mathrm{V}`$=2000 is expected for a gas-to-dust ratio like that in the ISM of our own galaxy (Savage & Mathis 1979), while the derived value from IR observations is 50 only (Moorwood 1996).

We fitted separately the spectra from MOS1, MOS2, p-n single events and double events. The p-n single events gives values of the line energies close to the expected ones for neutral atoms (the other instruments giving values systematically higher, MOS1 being the most discrepant, giving e.g. 6.436 for the iron K$`\alpha `$). Therefore, in the following we will limit the analysis to this instrument which is the one with the larger signal–to–noise. In principle, as it is possible that the matter is mildly ionized, this choice is somewhat arbitrary, but it is supported by the K$`\beta `$ line flux, as explained in Sec. 3.3.

The spectrum in the 4.5 to 13 keV range has been fitted with a model composed of a cold reflection component (model pexrav in XSPEC), produced by a power-law with $`\mathrm{\Gamma }=1.56`$ and a exponential cutoff at $`E_\mathrm{C}=56`$ keV (Matt et al. 1999, Bianchi et al. 2001), and the three emission lines mentioned above, all of them described by a gaussian model with $`\sigma `$=1 eV (i.e. much less than the instrument energy resolution) and a redshift of 0.0015 (Freeman et al. 1997). The $`\chi ^2`$ is poor (381/117 d.o.f.), largely due to residuals around the iron K$`\alpha `$ line (see Fig. 2). Leaving the width of the line free to vary, the fit improves significantly ($`\chi ^2`$=206/116 d.o.f.), but residuals are still visible, and the width of the line, $`\sigma =42`$ eV, is not easy to explain if we assume that the line emitting matter is the molecular torus111If the line is emitted by a torus rotating around the black hole with keplerian velocity, and assuming a black hole mass of 1.7$`\times 10^6M_{}`$ (Greenhill et al. 2003) and an inner radius of the torus of 0.2 pc (Bianchi et al. 2001), the expected value of $`\sigma `$ is about 2 eV.. It seems more likely that the line ‘wings’ are instead due to the Compton shoulder (Bianchi et al. 2002), redwards of the line core, and to the He–like iron line (Sambruna et al. 2001b), bluewards of the line core. The Compton shoulder is indeed expected on theoretical ground (Matt 2002b), while the He–like iron line probably originates from reflecting circumnuclear ionized matter. We therefore added two more lines, with energies fixed at 6.3 keV (Matt 2002b) and 6.68 keV, respectively (the width of the line core, as well as that of the added lines, held fixed to 1 eV for simplicity). The fit improves significantly ($`\chi ^2`$=157/115 d.o.f.), and no strong systematic residuals are left (Fig. 3). The significance of each line is $`>`$99.99%, according to the F-test. The Compton shoulder is actually expected to have a finite width, but unfortunately its profile (Sunyaev & Churazov 1996, Matt 2002) is different from any xspec model. As a check, we tried for the Compton Shoulder also gaussians with $`\sigma `$=40 and 70 eV (the latter value corresponding to a FWHM of the same order of the total width of the Shoulder). A worse fit ($`\chi ^2`$ of 162/115 and 179/115, respectively) is obtained, but the fluxes of both the Shoulder and the line core remain almost unchanged.

The best fit results are summarized in Table 1. All errors refer to 90% confidence level for one interesting parameter. It is worth noting that the measured iron K$`\alpha `$ line energy constrains, at the above confidence level, the ionization state of iron (before the photoionization) to be between xii and xiii (House 1969), or to be exactly xvii if the MOS1 value is considered. While of course, given the present uncertainties on the instruments calibrations, these results cannot be taken too literally, they highlight the potentially extraordinary precision of the measure. More solid constraints on the ionization states can be derived from the Fe K$`\beta `$/K$`\alpha `$ lines ratio, as discussed in Sec. 3.3.

### 3.1 The Fe abundance

The iron abundance is directly measured by the depth of the iron edge in the Compton reflection continuum, and it is measured with respect to the elements responsible for the photoabsorption below the edge, mainly oxygen and neon but with significant contributions from magnesium, silicon and sulphur. The high quality of the spectrum permits to estimate this parameter with high (statistical) precision, i.e. less than 10%. The result, i.e $`A_{\mathrm{Fe}}`$1.7, has been obtained assuming an illuminating spectrum as that derived from the BeppoSAX observation (Matt et al. 1999). Leaving the photon index free to vary (and with the high energy exponential cut–off fixed at 100 keV), a significantly better fit is found ($`\chi ^2`$=138/114 d.o.f., the improvement being significant at the 99.98% confidence level), and the iron abundance decreases to about 1.2, a value which is more consistent with the iron K$`\alpha `$ EW (e.g. Matt et al. 2003 and references therein). The best fit power law photon index is 1.90$`\pm `$0.05.

In all fits described so far the inclination angle of the reflector has been held fixed to the XSPEC default value of 63. Leaving this parameter free to vary no significant difference in the value of $`A_{\mathrm{Fe}}`$ is found.

In conclusion, given the uncertainties on the primary continuum as well as on the geometry of the reflector (the pexrav model is for a plane–parallel slab), we can conclude that the iron abundance is confined to be between 1 and 2. This is in agreement with the results obtained by comparing the line EW and the Compton reflection continuum in a sample of Seyfert 1 galaxies (Perola et al. 2002).

### 3.2 The Ni abundance

In order to derive, from the observed Ni to Fe K$`\alpha `$ line fluxes, the relative abundances of the two elements, we calculated the expected values of their ratio, using the method proposed by Basko (1978) and valid for a semi–infinite plane–parallel slab that is isotropically illuminated. For the nickel line we included in the calculations both the unscattered and once scattered line photons, while for the iron line, for which the two components are separated in the fit procedure, we included only photons in the line core. The values of the calculated ratio range from 0.03 to 0.045, depending on the inclination angle and the assumed power law index. The measured value, 0.07 with an error of less than 20%, is significantly larger, strongly indicating a nickel-to-iron overabundance. In the calculations, we adopted cosmic abundances. However, the results do not depend much on the iron and nickel abundances, provided that they vary together. In fact, if e.g. both iron and nickel are twice the cosmic value, we calculate that the flux of the nickel line increases only by a factor $``$1.3 (because of the increased photoelectric absorption), similar to the increase expected for the flux of the iron line (Matt et al. 1997), so leaving the need for a nickel-to-iron overabundance unchanged.

It must also be noted that, as we fitted the Ni line with a narrow gaussian, part of its Compton Shoulder could be lost in the fitting procedure, so possibly further increasing the relative Ni overabundance.

Finally, we recall that in the calculations we have used the Anders & Grevesse (1989) abundances. If we instead use the Anders & Ebihara (1982) set, which differs mainly in having the iron abundance 1.4 times lower, the expected values are of course not much different from what we measure. The same is true if we use the Grevesse & Sauval (1998) or, even more, the Holweger (2001) sets. Put it in a different way, our results implies that the nickel-to-iron absolute abundance ratio is around 0.055-0.075, independently of course of the set of solar abundances chosen for reference.

### 3.3 The Fe K$`\beta `$/K$`\alpha `$ ratio

The ratio between the Fe K$`\beta `$ and K$`\alpha `$ (core only) lines is 0.14 with a statistical error of about 10%. This number slightly increases, but within the statistical error, when the power law index of the illuminating continuum is kept free. The expected value, again using the Basko (1978) formulae, is 0.155-0.16 (depending on the inclination angle), only marginally consistent with the measured value. Again, it is possible that in the fit procedure part at least of the Fe K$`\beta `$ Compton Shoulder is lost, so reducing the discrepancy. Alternatively, it is possible that the actual value of the K$`\beta `$/K$`\alpha `$ probabilities is slightly lower (for instance, Kikoin (1976) quoted a ratio of 17:150), or that the iron is moderately ionized; interestingly, the observed value is the one expected from Fe ix or x (Kaastra & Mewe 1993), close to what found from the p-n single event iron K$`\alpha `$ line energy. Instead, a too small value is expected for more ionized atoms, and of course no K$`\beta `$ line at all is expected for Fe xvii (the ionization state found from the MOS1) or more, when M electrons are no longer present.

### 3.4 The Compton Shoulder

The ratio between the iron K$`\alpha `$ Compton Shoulder and the line core is 20$`\pm `$3%, fully consistent with the value found by $`Chandra`$ (Bianchi et al. 2002). The greater precision of the present estimate with respect to the $`Chandra`$ one strengthens the case for a Compton–thick reflector (Matt 2002b), giving further support to the identification of the reflector with the absorber. It is important to note that, while absorption provides information on the optical depth of the line-of-sight material, features in reflection, being integrated over the whole visible part of the matter, give information on the average value of the optical depth. The very fact that the amount of Compton shoulder is consistent with the optical depth derived from absorption suggests that the material is fairly homogeneous, so supporting the classical toroidal model for the cold circumnuclear matter222See Matt & Guainazzi 2003 for a case in which the optical depth derived from the Compton Shoulder is an order of magnitude lower than that of the intervening matter..

## 4 Summary

The results discussed in this paper may be summarized as follows:

a) From the Fe K$`\alpha `$ edge a value of $`A_{\mathrm{Fe}}`$=1.7 in number with respect to solar (using the set of values given by Anders & Grevesse 1989) has been found, assuming the primary illuminating continuum measured by BeppoSAX (Matt et al. 1999). If the slope of the primary power law is left free to vary, a steeper spectrum and a lower iron abundance (about 1.2) is found.

b) From the flux ratio of the Ni to Fe K$`\alpha `$ lines, a nickel-to-iron abundance ratio of 0.055-0.075 is found, i.e. a factor of 1.5-2 Ni relative overabundance compared to the Anders & Grevesse (1989) cosmic values, and instead roughly consistent with the Anders & Ebihara (1982) set. To the best of our knowledge this is the first unambiguous X–ray detection of a Ni line in an AGN. Previous detections, like in the ASCA spectrum of Ark 564 (Turner et al. 2001) and in the BeppoSAX spectrum of Circinus itself (Guainazzi et al. 1999) were affected by confusion with the Fe K$`\beta `$ line.

c) The Fe K$`\beta `$/K$`\alpha `$ flux ratio is $``$0.14, somewhat lower than expected. A possible explanation is that the iron is mildly ionized, but not much more than Fe x, otherwise the Fe K$`\beta `$ line emission would be much fainter then observed (and of course absent at all for Fe xvii or more).

d) The presence of the Fe K$`\alpha `$ Compton Shoulder, already discovered by Bianchi et al. (2002) in the $`Chandra`$/HETG spectrum, is confirmed. The relative flux of the Compton Shoulder is 20$`\pm `$3%, fully consistent with the $`Chandra`$ finding, and implying Compton–thick matter (Matt 2002b). This provides further support to the identification of the reflecting region with the absorber and suggests that the torus is fairly homogeneous.

## Acknowledgments

GM and SB acknowledges ASI and MIUR (under grant cofin-00-02-36) for financial support.


text:
# Topological obstructions to graph colorings

## 1. Introduction

One of the central questions of graph theory is to find lower bounds for the number of colors in an admissible coloring of the set of vertices of a graph (a coloring is called admissible if any 2 vertices, which are connected by an edge get different colors). The minimal possible number of colors in an admissible coloring is called the chromatic number of the graph, and is denoted by $`\chi (G)`$. In 1978 L. Lovász solved the Kneser conjecture by finding geometric obstructions of Borsuk-Ulam type to graph colorings.

###### Theorem 1.1.

(Kneser-Lovász, ). Let $`\mathrm{\Gamma }_{k,n}`$ be the graph whose vertices are all $`k`$-subsets of $`[n]`$, and edges are all pairs of disjoint $`k`$-subsets; here $`1kn/2`$. Then $`\chi (\mathrm{\Gamma }_{k,n})=n2k+2`$.

The hard part was to show the inequality $`\chi (\mathrm{\Gamma }_{k,n})n2k+2`$. Lovász’ idea to achieve that was to associate a simplicial complex $`𝒩(G)`$, called the neighborhood complex, to an arbitrary graph $`G`$, and then use the connectivity information of the topological space $`𝒩(G)`$ to find obstructions to the colorability of $`G`$.

To define $`𝒩(G)`$ we need some notations. For any graph $`G`$, let $`V(G)`$ denote the set of its vertices, and $`E(G)V(G)\times V(G)`$ the set of its edges. Since all the graphs in this paper are undirected, $`(x,y)E(G)`$ implies $`(y,x)E(G)`$. We allow our graphs to contain loops. For a graph $`G`$ we distinguish between looped and unlooped complements, namely we let $`\mathrm{}G`$ be the graph defined by $`V(\mathrm{}G)=V(G)`$, $`E(\mathrm{}G)=(V(G)\times V(G))E(G)`$, while $`\overline{G}`$ is the graph defined by $`V(\overline{G})=V(G)`$, $`E(\overline{G})=E(\mathrm{}G)\{(v,v)|vV(G)\}`$. For a graph $`G`$ and $`SV(G)`$ we denote by $`G[S]`$ the graph on the vertex set $`S`$ induced by $`G`$, that is $`V(G[S])=S`$, $`E(G[S])=(S\times S)E(G)`$.

The complex $`𝒩(G)`$ can then be defined by taking as its vertices all non-isolated vertices of $`G`$, and as its simplices all the subsets of $`V(G)`$ which have a common neighbor; in other words, the maximal simplices of $`𝒩(G)`$ are $`𝒩(v)`$, for $`vV(G)`$, where $`𝒩(v)=\{wV(G)|(v,w)E(G)\}`$ is the set of all neighbors of $`v`$.

###### Theorem 1.2.

(Lovász, ). Let $`G`$ be a graph without loops, such that $`𝒩(G)`$ is $`k`$-connected, then $`\chi (G)k+3`$.

Numerous papers followed Lovász’ pioneering work, see  for a good recent survey. Generalizing the original line of thought, for any pair of graphs $`G`$ and $`H`$, Lovász has defined a cell complex $`\text{Hom}(G,H)`$.

Recall that a graph homomorphism is a map $`\varphi :V(G)V(H)`$, such that $`\varphi \times \varphi :E(G)E(H)`$, that is if $`x,yV(G)`$ are connected by an edge, then $`\varphi (x)`$ and $`\varphi (y)`$ are also connected by an edge. We denote the set of all homomorphisms from $`G`$ to $`H`$ by $`om(G,H)`$.

###### Definition 1.3.

$`\text{Hom}(G,H)`$ is a polyhedral complex whose cells are indexed by all functions $`\eta :V(G)2^{V(H)}\{\mathrm{}\}`$, such that if $`(x,y)E(G)`$, for any $`\stackrel{~}{x}\eta (x)`$ and $`\stackrel{~}{y}\eta (y)`$ we have $`(\stackrel{~}{x},\stackrel{~}{y})E(H)`$.

The closure of a cell $`\eta `$ consists of all cells indexed by $`\stackrel{~}{\eta }:V(G)2^{V(H)}\{\mathrm{}\}`$, which satisfy $`\stackrel{~}{\eta }(v)\eta (v)`$, for all $`vV(G)`$.

In particular, the set of vertices of $`\text{Hom}(G,H)`$ is precisely $`om(G,H)`$.

As the Proposition 2.1 shows, already the complexes $`\text{Hom}(K_2,G)`$ contain the homotopy type information of the neighbourhood complexes. This observation makes one try to look for obstructions coming from maps from other graphs than $`K_2`$.

In this paper we announce the proof of the following conjecture of Lovász, which is a natural next step, after the Theorem 1.2, in the general program of finding topological obstructions to the existence of the graph homomorphisms.

###### Theorem 1.4.

Let $`G`$ be a graph, and let $`r,k`$, such that $`r1`$, $`k1`$. If $`\text{Hom}(C_{2r+1},G)`$ is $`k`$-connected, then $`\chi (G)k+4`$.

Here, $`C_{2r+1}`$ is a $`(2r+1)`$-cycle, i.e. a graph defined by $`V(C_{2r+1})=/(2r+1)`$, $`E(C_{2r+1})=\{([x],[x+1]),([x+1],[x])|x/(2r+1)\}`$.

To state our main result we need more notations. Let $`X`$ be a CW complex with a free $`_2`$-action. By the general theory of principal bundles, there exists a $`_2`$-equivariant map $`\stackrel{~}{w}:XS^{\mathrm{}}`$, where $`_2`$ acts on $`S^{\mathrm{}}`$ by the antipodal map, and the induced map $`w:X/_2^{\mathrm{}}`$ is unique up to homotopy. This in turn induces a canonical algebra homomorphism $`w^{}:H^{}(^{\mathrm{}};_2)H^{}(X/_2;_2)`$. Let $`zH^1(^{\mathrm{}};_2)`$ denote the nontrivial cohomology class, then $`H^{}(^{\mathrm{}};_2)_2[z]`$ as graded algebras. We denote $`w^{}(z)H^1(X/_2;_2)`$ by $`\varpi _1(X)`$, and call it the first Stiefel-Whitney class of the $`_2`$-space X. Clearly, $`\varpi _1^k(X)=w^{}(z^k)`$.

Let $`_2`$ act on $`C_{2r+1}`$ by mapping $`[x]/(2r+1)`$ to $`[x]`$, and let $`\gamma om(C_{2r+1},C_{2r+1})`$ denote the corresponding graph homomorphism. Furthermore, let $`_2`$ act on $`K_m`$ for $`m2`$, by swapping the vertices 1 and 2 and fixing the vertices $`3,\mathrm{},m`$; here, $`K_m`$ is the graph defined by $`V(K_m)=[m]`$, $`E(K_m)=\{(x,y)|x,y[m],xy\}`$. These induce free $`_2`$-actions on $`\text{Hom}(C_{2r+1},G)`$ and $`\text{Hom}(K_m,G)`$.

###### Theorem 1.5.

Let $`G`$ be a graph.

1. If $`\varpi _1^k(\text{Hom}(C_{2r+1},G))0`$, then $`\chi (G)k+3`$.
2. If $`\varpi _1^k(\text{Hom}(K_m,G))0`$, then $`\chi (G)k+m`$.

Since we know that for a $`k`$-connected space $`X`$ with a free $`_2`$-action $`\varpi _1^{k+1}(X)0`$, the Theorem 1.5 implies the Theorem 1.4 as well as the following corollary.

###### Corollary 1.6.

Let $`G`$ be a graph, and let $`m,k`$, such that $`m2`$, $`k1`$. If $`\text{Hom}(K_m,G)`$ is $`k`$-connected, then $`\chi (G)k+m+1`$.

Acknowledgments. We would like to thank László Lovász and Péter Csorba for insightful discussions. The second author acknowledges support by the University of Washington, Seattle, the Swiss National Science Foundation, and the University of Bern.

## 2. Homotopy type of the Hom complexes

First, we remark two properties of the Hom complexes:

1. Cells of $`\text{Hom}(G,H)`$ are direct products of simplices. More specifically, each $`\eta `$ as in the Definition 1.3 is a product of $`|V(G)|`$ simplices, having dimensions $`|\eta (x)|1`$, for $`xV(G)`$.
2. $`\text{Hom}(H,)`$ is a covariant, while $`\text{Hom}(,H)`$ is a contravariant functor from Graphs to Top, where Graphs is a category having graphs as objects, and graph homomorphisms as morphisms. If $`\varphi om(G,G^{})`$, then we shall denote the induced topological maps as $`\varphi ^H:\text{Hom}(H,G)\text{Hom}(H,G^{})`$ and $`\varphi _H:\text{Hom}(G^{},H)\text{Hom}(G,H)`$.

###### Proposition 2.1.

$`\text{Hom}(K_2,G)`$ is homotopy equivalent to $`𝒩(G)`$.

If the Proposition 2.1 coupled with the Theorem 1.2 were to be interpreted as that the obstructions to colorability found by Lovász in 1978 stem from the graph $`K_2`$, then the idea behind the Lovász Conjecture could be thought of as that the next natural class of obstructions should come from the odd cycles, $`C_{2r+1}`$.

The next proposition is the crucial step in the proof of the Theorem 1.5(b).

###### Proposition 2.2.

$`\text{Hom}(K_m,K_n)`$ is homotopy equivalent to a wedge of $`(nm)`$-dimensional spheres.

Next, we need a technical Quillen-type lemma. For any small category $`C`$ (in particular a finite poset) we denote by $`\mathrm{\Delta }(C)`$ the realization of the nerve of that category. For any finite poset $`P`$, we let $`P^{op}`$ denote the finite poset which has the same set of elements as $`P`$, but the opposite partial order. Also, for any finite poset $`P`$, whenever the subset of the elements of $`P`$ is considered as a poset, the partial order is taken to be induced from $`P`$.

###### Proposition 2.3.

Let $`\varphi :PQ`$ be a map of finite posets. Consider a list of possible conditions on $`\varphi `$.

Condition $`(A)`$. For every $`qQ`$, $`\mathrm{\Delta }(\varphi ^1(q))`$ is contractible.

Condition $`(B)`$. For every $`pP`$ and $`qQ`$ with $`\varphi (p)q`$ the poset $`\varphi ^1(q)P_p`$ has a maximal element.

Condition $`(B^{op})`$. Let $`\varphi ^{op}:P^{op}Q^{op}`$ be the poset map induced by $`\varphi `$. We require that $`\varphi ^{op}`$ satisfies Condition $`B`$.

Then

1. If $`\varphi `$ satisfies $`(A)`$ and either $`(B)`$ or $`(B^{op})`$, then $`\varphi `$ is a homotopy equivalence.
2. If $`\varphi `$ satisfies $`(B)`$ and $`(B^{op})`$, and $`Q`$ is connected, then for any $`q,q^{}Q`$ we have $`\mathrm{\Delta }(\varphi ^1(q))\mathrm{\Delta }(\varphi ^1(q^{}))`$. Furthermore, we have a fibration homotopy long exact sequence:

(2.1)
$$\mathrm{}\pi _i(\mathrm{\Delta }(\varphi ^1(q)))\pi _i(\mathrm{\Delta }(P))\pi _i(\mathrm{\Delta }(Q))$$

Proof. The argument is based on using the Quillen’s Theorems A and B, see \[3, pp. 85,89\], for the induced map $`\text{Bd}\varphi :\text{Bd}P\text{Bd}Q`$, here Bd denotes the barycentric subdivision, that is the poset of all the chains in the given poset. The details will appear elsewhere. ∎

###### Proposition 2.4.

If $`G`$ and $`H`$ are graphs and $`u`$ and $`v`$ are vertices of $`G`$, such that $`N(v)N(u)`$, then $`i:GvG`$ induces a homotopy equivalence $`i_H:\text{Hom}(G,H)\text{Hom}(Gv,H)`$.

Proof. Apply the Proposition 2.3 (1) for the cellular map $`i_H:\text{Hom}(G,H)\text{Hom}(Gv,H)`$, which forgets the colors of $`v`$. ∎

###### Corollary 2.5.

If $`T`$ is a tree with at least one edge, then the map $`i_{K_n}:\text{Hom}(T,K_n)\text{Hom}(K_2,K_n)`$ induced by any inclusion $`i:K_2T`$ is a homotopy equivalence. Furthermore, if $`F`$ is a forest, then $`\text{Hom}(\overline{F},K_n)\text{Hom}(K_m,K_n)`$, where $`m`$ is the maximal cardinality of an independent set in $`F`$.

## 3. $`\text{Hom}_+`$ and filtrations

For a finite graph $`H`$, let $`H_+`$ be the graph obtained from $`H`$ by adding an extra vertex, called the base vertex, and connecting it by edges to all the vertices of $`H_+`$ including itself.

###### Definition 3.1.

Let $`G`$ and $`H`$ be two graphs. The simplicial complex $`\text{Hom}_+(G,H)`$ is defined to be the link in $`\text{Hom}(G,H_+)`$ of the homomorphism mapping every vertex of $`G`$ to the base vertex in $`H_+`$.

So $`\text{Hom}_+(G,H)`$ is just like $`\text{Hom}(G,H)`$ with the difference that we also allow empty lists of colors, i.e., the cells are functions $`\eta :V(G)2^{V(H)}`$, which also makes it simplicial. We remark that $`\text{Hom}_+(H,)`$ is a covariant functor from Graphs to Top.

###### Proposition 3.2.

$`\text{Hom}_+(G,H)`$ is isomorphic to the independence complex of $`G\times \mathrm{}H`$. In particular, $`\text{Hom}_+(G,K_n)`$ is isomorphic to $`\text{I}nd(G)^n`$, where $``$ denotes the simplicial join.

The chain complex of $`\text{Hom}_+(G,K_n)`$ has a natural filtration. For each simplex of $`\text{Hom}_+(G,K_n)`$, $`\eta :V(G)2^{V(K_n)}`$, define the support of $`\eta `$ to be $`\text{supp}\eta =V(G)\eta ^1(\mathrm{})`$. In fact, the same definition for supp holds for any $`\text{Hom}_+(G,H)`$. One concise way to phrase it is to simply consider the map $`t^G:\text{Hom}_+(G,H)\text{Hom}_+(G,\mathrm{}K_1)\mathrm{\Delta }_{|V(G)|1}`$ induced by the homomorphism $`t:H\mathrm{}K_1`$.

We can now filter $`C_{}(\text{Hom}_+(G,K_n))`$ by the cardinalities of the support. Namely,

$$F_1=0,F_0=|\text{supp}\eta |=1,\mathrm{},F_k=|\text{supp}\eta |k+1,\mathrm{},$$

that is $`F_k`$ is the chain subcomplex of $`C_{}(\text{Hom}_+(G,K_n))`$ generated by all simplices whose support set has cardinality at most $`k+1`$.

Clearly, for any $`k`$,

$$F_k/F_{k1}=C_{}(\underset{SV(G),|S|=k+1}{}\text{Hom}(G[S],K_n))[k],$$

where the brackets $`[]`$ denote shifting. In particular, $`F_{|V(G)|1}=C_{}(\text{Hom}_+(G,K_n))`$, and $`F_{|V(G)|1}/F_{|V(G)|2}=C_{}(\text{Hom}(G,K_n))[|V(G)|1]`$.

Next, we describe a natural filtration on $`C_{}(\text{Hom}_+(C_{2r+1},K_n)/_2;)`$. Let $`c,a_1,\mathrm{},a_r,b_1,\mathrm{},b_r`$ denote the vertices of $`C_{2r+1}`$ so that $`\gamma (a_i)=b_i`$, for any $`i[r]`$, and $`(c,a_1),(a_i,a_{i+1})E(C_{2r+1})`$, for any $`i[r1]`$. Identify $`V(C_{2r+1})`$ with the vertices of an abstract simplex $`\mathrm{\Delta }_{2r}`$ of dimension $`2r`$.

We subdivide $`\mathrm{\Delta }_{2r}`$ by adding $`r`$ more vertices, denoted $`c_1,c_2,\mathrm{},c_r`$, and defining a new abstract simplicial complex $`\stackrel{~}{\mathrm{\Delta }}_{2r}`$ on the set $`\{c,a_1,\mathrm{},a_r,b_1,\mathrm{},b_r,c_1,\mathrm{},c_r\}=V(\stackrel{~}{\mathrm{\Delta }}_{2r})`$. The simplices of $`\stackrel{~}{\mathrm{\Delta }}_{2r}`$ are all the subsets of $`V(\stackrel{~}{\mathrm{\Delta }}_{2r})`$ which do not contain the subset $`\{a_i,b_i\}`$, for any $`i[r]`$.

One can think of this new complex $`\stackrel{~}{\mathrm{\Delta }}_{2r}`$ as the one obtained from $`\mathrm{\Delta }_{2r}`$ by representing it as a join $`\{c\}[a_1,b_1]\mathrm{}[a_r,b_r]`$, inserting one additional vertex into the middle of each $`[a_i,b_i]`$, and then taking the join of $`\{c\}`$ and the subdivided intervals. For $`\stackrel{~}{\sigma }\stackrel{~}{\mathrm{\Delta }}_{2r}`$ we define $`\vartheta (\stackrel{~}{\sigma })\mathrm{\Delta }_{2r}`$ by $`\vartheta (\stackrel{~}{\sigma })=(\stackrel{~}{\sigma }\{c_1,\mathrm{},c_r\})_{c_i\stackrel{~}{\sigma }}\{a_i,b_i\}`$.

$`\stackrel{~}{\mathrm{\Delta }}_{2r}`$ has an additional property: if a simplex of $`\stackrel{~}{\mathrm{\Delta }}_{2r}`$ is $`\gamma `$-invariant, then it is fixed pointwise. This allows us to introduce a simplicial structure on $`\stackrel{~}{\mathrm{\Delta }}_{2r}/_2`$ by taking the orbits of the simplices of $`\stackrel{~}{\mathrm{\Delta }}_{2r}`$ as the simplices of $`\stackrel{~}{\mathrm{\Delta }}_{2r}/_2`$.

Let us now describe a chain complex $`\stackrel{~}{C}_{}(\text{Hom}_+(C_{2r+1},K_n))`$, which comes from a different triangulation of the topological space $`\text{Hom}_+(C_{2r+1},K_n)`$. The chain complex consists of vector spaces over $`_2`$. The generators are pairs $`(\eta ,\sigma )`$, where $`\eta \text{Hom}_+(C_{2r+1},K_n)`$, and $`\sigma \stackrel{~}{\mathrm{\Delta }}_{2r}`$, such that $`\vartheta (\sigma )=\text{supp}\eta `$. Such a pair corresponds to the cell $`\eta \text{supp}^1(\sigma )`$. The codimension 1 boundary of $`(\eta ,\sigma )`$ is the sum of the following generators:

1. $`(\stackrel{~}{\eta },\sigma )`$, if $`\text{supp}\stackrel{~}{\eta }=\text{supp}\eta `$, and $`\stackrel{~}{\eta }\eta `$;
2. $`(\eta ,\stackrel{~}{\sigma })`$, if $`\stackrel{~}{\sigma }\sigma `$, and $`\vartheta (\sigma )=\vartheta (\stackrel{~}{\sigma })`$;
3. $`(\stackrel{~}{\eta },\sigma \{x\})`$, if $`xV(\stackrel{~}{\mathrm{\Delta }}_{2r})`$, $`Y=\vartheta (\{x\})\vartheta (\sigma \{x\})\mathrm{}`$, where $`\stackrel{~}{\eta }`$ is obtained from $`\eta `$ by setting $`\eta `$ to be $`\mathrm{}`$ on the vertex set $`\eta ^1(Y)`$, and where we require that all the values of $`\eta |_{\eta ^1(Y)}`$ have cardinality 1.

Here $``$ denotes the codimension 1 boundary. The degree of $`(\eta ,\sigma )`$ in $`\stackrel{~}{C}_{}(\text{Hom}_+(C_{2r+1},K_n))`$ is given by

$$\mathrm{deg}(\eta ,\sigma )=|\sigma |1+\underset{vV(C_{2r+1}),|\eta (v)|0}{}(|\eta (v)|1)=\mathrm{deg}\eta +|\sigma ||\vartheta (\sigma )|.$$

$`_2`$ acts on $`\stackrel{~}{C}_{}(\text{Hom}_+(C_{2r+1},K_n))`$ and we let $`\stackrel{~}{C}_{}^_2(\text{Hom}_+(C_{2r+1},K_n))`$ denote its subcomplex consisting of the invariant chains. By construction of the subdivision, $`\stackrel{~}{C}_{}^_2(\text{Hom}_+(C_{2r+1},K_n))`$ is a chain complex for a triangulation of the space $`\text{Hom}_+(C_{2r+1},K_n)/_2`$.

Just like before, we consider the natural filtration $`(\stackrel{~}{F}_1\stackrel{~}{F}_0\mathrm{})`$ on the chain complex $`\stackrel{~}{C}_{}^_2(\text{Hom}_+(C_{2r+1},K_n))`$ by the cardinality of $`\sigma `$. This time, for any $`k`$

$$\stackrel{~}{F}_k/\stackrel{~}{F}_{k1}=C_{}(\underset{\sigma }{}(\text{Hom}(G[\vartheta (\sigma )],K_n)/_2)\underset{\tau }{}\text{Hom}(G[\vartheta (\tau )],K_n))[k],$$

where the first coproduct is taken over all $`\sigma \stackrel{~}{\mathrm{\Delta }}_{2r}`$ which are $`_2`$-invariant, and the second coproduct is taken over all $`\tau \stackrel{~}{\mathrm{\Delta }}_{2r}`$ which are not $`_2`$-invariant. In addition $`|\sigma |=|\tau |=k+1`$ is required.

## 4. The spectral sequences and the proof of the Lovász Conjecture

We shall show that

(4.1)
$$(\stackrel{~}{\iota }_{K_n})_{n2}:H_{n2}(\text{Hom}(C_{2r+1},K_n)/_2)H_{n2}(\text{Hom}(K_2,K_n)/_2),$$

is a 0-map, where the homology is taken with coefficients in $`_2`$. Here $`\iota :K_2C_{2r+1}`$ is either of the two $`_2`$-equivariant inclusion maps which take the vertices of $`K_2`$ to $`\{a_r,b_r\}`$. It induces a $`_2`$-equivariant map $`\iota _{K_n}:\text{Hom}(C_{2r+1},K_n)\text{Hom}(K_2,K_n)`$, and hence also the quotient map $`\stackrel{~}{\iota }_{K_n}:\text{Hom}(C_{2r+1},K_n)/_2\text{Hom}(K_2,K_n)/_2`$.

Note that if $`(\stackrel{~}{\iota }_{K_n})_{n2}`$ is a 0-map, then so is

$$(\stackrel{~}{\iota }_{K_n})^{n2}:H^{n2}(\text{Hom}(K_2,K_n)/_2;_2)H^{n2}(\text{Hom}(C_{2r+1},K_n)/_2;_2),$$

since we are working over a field. By the functoriality of the Stiefel-Whitney classes, this implies that $`\varpi _1^{n2}(\text{Hom}(C_{2r+1},K_n))=0`$, which is a crucial fact for our proof of Lovász Conjecture. We shall sketch the full computation for the case $`n`$ is odd. For even $`n`$ the Lovász Conjecture follows already from (4.2), see the discussion following (4.2).

The $`E^1`$-tableau of the first spectral sequence is given by $`E_{d,s}^1=H_d(F_s,F_{s1})`$. From our remarks above concerning this filtration it follows that each $`E_{d,s}^1`$ is a direct sum of the appropriate homology groups of $`\text{Hom}(H,K_n)`$, where $`H`$ is a subgraph of $`C_{2r+1}`$. Since all proper subgraphs of $`C_{2r+1}`$ are forests, we know the first tableau, except for the $`(2r)`$th row, by the Corollary 2.5. It can be shown (we omit the technical details) that the only part of the spectral sequence which is relevant for the computation of the homology groups of $`\text{Hom}(C_{2r+1},K_n)`$ up to dimension $`n2`$, consists of two chain complexes:

$$D_{}^0:E_{0,0}^1E_{1,1}^1E_{2,2}^1\mathrm{}E_{2r1,2r1}^1$$

and

$$D_{}^1:E_{n2,0}^1E_{n1,1}^1E_{n,2}^1\mathrm{}E_{n2+2r1,2r1}^1,$$

where all the differentials are $`d^1`$ from the spectral sequence. To start with, $`D_{}^0`$ is isomorphic to the chain complex of the $`(2r1)`$-skeleton of the $`(2r)`$-simplex $`\mathrm{\Delta }_{2r}`$, thus having only the homology in dimensions 0 and $`2r1`$. We can conclude that $`E_{0,0}^2=`$, while $`E_{1,1}^2=E_{2,2}^2=\mathrm{}=E_{2r,2r}^2=0`$, hence $`E_{2r,2r}^1=`$.

The analysis of $`D_{}^1`$ is a little more interesting. By taking the induced subgraphs, we identify subsets of $`V(C_{2r+1})`$ with collections of arcs on a circle (some arcs of length 1), such that every two arcs are separated by at least one vertex. The detailed analysis using the Corollary 2.5 shows that the generators of the vector spaces in $`D_{}^1`$ can be indexed with pairs $`(S,A)`$, where $`SV(C_{2r+1})`$, and $`A`$ a connected component of $`C_{2r+1}[S]`$ with at least one edge. We call such components arcs, and we call this specific $`A`$marked arc. The dimension of $`(S,A)`$ is $`|S|`$. The boundary of $`(S,A)`$ is the sum (with appropriate signs) over all pairs obtained by deleting an element of $`S`$. One can work out that, if the deleted element is not in $`A`$, then the arc remains the same, while a deleted element which is in $`A`$ contributes to the boundary a sum of two pairs, depending on which piece of $`A`$ is taken as a new arc, where the pieces of length 1 give 0 contribution.

We can now filter $`D_{}^1`$ by the length of the marked arc $`A`$. By the previous argument, the relative chain complexes will split into subcomplexes each corresponding to a particular marked arc. All these subcomplexes are acyclic (they are reduced chain complexes of simplices) except for two, namely, those corresponding to $`S=V(C_{2r+1})\{c\}`$ and $`S=V(C_{2r+1})\{a_r,b_r\}`$.

The complete computation of the first differential shows that

(4.2)
$$H_i(\text{Hom}(C_{2r+1},K_n);_2)=\{\begin{array}{cc}_2,\hfill & \text{ if }i=0,n3,n2,\hfill \\ 0,\hfill & \text{ if }1in4.\hfill \end{array}$$

Additionally, one can see that $`H_i(\text{Hom}(C_{2r+1},K_n);)=0`$, for $`1in4`$, and $`H_{n2}(\text{Hom}(C_{2r+1},K_n);)=H_{n3}(\text{Hom}(C_{2r+1},K_n);)=`$, for $`n`$ odd, while $`H_{n2}(\text{Hom}(C_{2r+1},K_n);)=0`$, $`H_{n3}(\text{Hom}(C_{2r+1},K_n);)=_2`$, for $`n`$ even.

We remark that from this computation Lovász Conjecture follows easily in the case $`n`$ is even. The essence is to show that there is no $`_2`$-map of $`S^{n2}`$ into $`\text{Hom}(C_{2r+1},K_n)`$. If this map existed, then, combined with the canonical map $`\text{Hom}(C_{2r+1},K_n)\text{Hom}(K_2,K_n)`$, induced by $`K_2C_{2r+1}`$, it would yield a $`_2`$-map of degree 0 of $`S^{n2}`$ into itself, which is impossible.

We assume for the rest of the paper that $`n`$ is odd. In this case one can show that the $`_2`$-action on $`H_{n3}(\text{Hom}(C_{2r+1},K_n);)`$ is always multiplication by $`1`$.

The $`E^1`$-tableau of the second spectral sequence is given by $`E_{d,s}^1=H_d(\stackrel{~}{F}_s,\stackrel{~}{F}_{s1})`$. This time each $`E_{d,s}^1`$ splits as a vector space over $`_2`$ into direct sums of $`H_i(\text{Hom}(H,K_n);_2)`$, where $`H`$ is an induced subgraph of $`C_{2r+1}`$, and of $`\text{Hom}(H,K_n)/_2`$, where $`H`$ is a $`_2`$-invariant induced subgraph of $`C_{2r+1}`$. The detailed analysis of the first tableau of this spectral sequence is rather technical and will appear elsewhere. We sketch here the basic steps of the argument.

(1) We single out the generator $`\rho `$ in $`E_{n2+r,r}^1`$, which is the contribution of $`\{c,c_1,\mathrm{},c_r\}`$. Let $`\stackrel{~}{E}_{n2+r,r}^1`$ denote the part of $`E_{n2+r,r}^1`$ which is spanned by the rest of the generators.

(2) Analysis of the boundary of $`\rho `$ shows that if $`(\stackrel{~}{\iota }_{K_n})_{n2}`$ is not a 0-map, then rank of $`d^1:E_{n2+r,r}^1E_{n3+r,r1}^1`$ is one higher than the rank of $`\stackrel{~}{d}^1:\stackrel{~}{E}_{n2+r,r}^1E_{n3+r,r1}^1`$. This is because the boundary of other generators of $`E_{n2+r,r}^1`$ does not contain the generator in $`E_{n3+r,r1}^1`$ indexed by $`\{c_1,\mathrm{},c_r\}`$. Indeed, the only place for it to be would be in the boundary of the generators indexed by $`\{x,c_1,\mathrm{},c_r\}`$, where $`x=a_i`$ or $`x=b_i`$, but omitting $`x`$ is a double covering map, which is a 0-map on the $`_2`$-homology.

(3) The differential $`d^1:E_{n2+r,r+1}^1E_{n3+r,r}^1`$ is a 0-map, because $`q_{n3}`$ in (4.3) below is a 0-map.

(4) The chain complex

$$E_{n2+r,r+1}^1E_{n1+r,r+2}^1\mathrm{}E_{n3+2r,2r}^1$$

is a chain complex of $`^{r1}`$ over $`_2`$. Hence $`E_{n2+r,r+1}^2=_2`$, and so $`d^2:E_{n2+r,r+1}^2E_{n3+r,r1}^2`$ has rank 1.

(5) By means of technical computations we can show that the sequence

$$E_{n4+r,r2}^1E_{n3+r,r1}^1\stackrel{~}{E}_{n2+r,r}^1$$

has homology $`_2`$ in the middle term. Altogether, this shows the equation (4.1).

It remains to see that

(4.3)
$$q_{n3}:H_{n3}(\text{Hom}(C_{2r+1},K_n);_2)H_{n3}(\text{Hom}(C_{2r+1},K_n)/_2;_2).$$

is a 0-map.

Proof of (4.3). First let us see (4.3) over integers. Take $`\zeta H_{n3}(\text{Hom}(C_{2r+1},K_n);)`$. By our previous computations $`\gamma ^{K_n}(\zeta )=\zeta `$, this means that $`q_{n3}(\gamma ^{K_n}(\zeta ))=q_{n3}(\zeta )`$. On the other hand, $`q_{n3}`$ commutes with the $`_2`$-action, that is $`q_{n3}(\gamma ^{K_n}(\zeta ))=q_{n3}(\zeta )`$, which yields $`q_{n3}(\zeta )=0`$.

Second, by the universal coefficient theorem the map

$$\tau :H_{n3}(\text{Hom}(C_{2r+1},K_n);)_2H_{n3}(C_{}(\text{Hom}(C_{2r+1},K_n);)_2)$$

is injective and functorial. In our concrete situation, this map is also surjective, hence the claim follows from the following diagram:

$$\begin{array}{ccc}H_{n3}(\text{Hom}(C_{2r+1},K_n);)_2& \stackrel{\text{0-map}}{}& H_{n3}(\text{Hom}(C_{2r+1},K_n)/_2;)_2\\ \tau \text{iso}& & & & \\ H_{n3}(\text{Hom}(C_{2r+1},K_n);_2)& \stackrel{q_{n3}}{}& H_{n3}(\text{Hom}(C_{2r+1},K_n)/_2;_2)\mathit{}\end{array}$$

Proof of the Lovász Conjecture.

If the graph $`G`$ is $`(k+3)`$-colorable, then there exists a homomorphism $`\varphi :GK_{k+3}`$. It induces a $`_2`$-equivariant map $`\varphi ^{C_{2r+1}}:\text{Hom}(C_{2r+1},G)\text{Hom}(C_{2r+1},K_{k+3})`$. Since the Stiefel-Whitney classes are functorial and $`\varpi _1^{k+1}(\text{Hom}(C_{2r+1},K_{k+3}))=0`$, the existence of the map $`\varphi ^{C_{2r+1}}`$ implies that $`\varpi _1^{k+1}(\text{Hom}(C_{2r+1},G))=0`$, which is a contradiction to the assumption of the theorem. ∎


text:
# Noncyclic mixed state phase in SU(2) polarimetry

## Acknowledgment

The work by E.S. was financed by the Swedish Research Council.