text:
# Charmed meson resonances from chiral coupled-channel dynamics

## Abstract

Charmed meson resonances with quantum numbers $`J^P=0^+`$ and $`J^P=1^+`$ are generated in terms of chiral coupled-channel dynamics. At leading order in the chiral expansion a parameter-free prediction is obtained for the scattering of Goldstone bosons off charmed pseudo-scalar and vector mesons. The recently announced narrow open charm states observed by the BABAR and CLEO collaborations are reproduced. We suggest the existence of states that form an anti-triplet and a sextet representation of the SU(3) group. In particular, so far unobserved narrow isospin-singlet states with negative strangeness are predicted.

Recently a new narrow state of mass 2.317 GeV that decays into $`D_s^+\pi ^0`$ was announced BaBar . This result was confirmed CLEO  and a second narrow state of mass 2.463 GeV decaying into $`D_s^{}\pi ^0`$ was observed. Such states were first predicted in NRZ93 ; BH94  based on the spontaneous breaking of chiral symmetry. The theoretical predictions NRZ93 ; BH94 ; BEH03 ; NRZ03  rely on the chiral quark model which predicts the heavy-light $`0^+,1^+`$ resonance states to form an anti-triplet representation of the SU(3) group. If one insists on a non-linear realization of the chiral SU(3) group and excludes any further model assumptions, no a priori prediction can be made for the existence of chiral partners of any given state.

Recently it was shown LK03  that solving the coupled-channel Bethe-Salpeter equation with the interaction kernel following from a non-linear chiral SU(3) Lagrangian one is able to predict two octets and a singlet multiplets of the light $`1^+`$ mesons consistent with the empirical spectrum. Similar results were obtained for light meson resonances with $`J^P=0^+`$ quantum numbers Rupp86 ; WI90 ; JPHS95 ; OOP99 ; NVA02 ; NP02 . In view of the evident success of the chiral coupled-channel dynamics to predict the existence of a wealth of meson and baryon resonances in the ($`u,d,s`$)-sector of QCD LK03 ; Granada ; Copenhagen  it is expectable that the chiral SU(3) symmetry should also predict spectra of hadrons with open charm or beauty (see also BR03 ). In this talk we review the $`\chi `$-BS(3) approach LK00 ; LK01 ; LK02 ; LH02 ; LK03 ; Granada ; Copenhagen  as applied to open-charm meson resonances KL03 ; HL03 . We will not have space to discuss further exciting results concerning open-beauty meson resonances KL03 , open-charm baryon resonances LK03-baryon  or results in the ($`u,d,s`$)-sector of QCD LK03 ; Granada ; Copenhagen .

Heavy-light meson states with quantum numbers $`J^P=0^+`$ and $`J^P=1^+`$ may be studied by considering the s-wave scattering of Goldstone bosons off the heavy-light ground state mesons with $`J^P=0^{}`$ and $`J^P=1^{}`$. If scalar or axial vector resonances exist they should manifest themselves as poles in the corresponding scattering amplitudes. The starting point to describe low-energy scattering processes is the chiral SU(3) Lagrangian Wein-Tomo ; Wise92 ; YCCLLY92 ; BD92  including heavy-light $`0^{}`$ and $`1^{}`$ fields. A systematic approximation scheme arises due to a successful scale separation justifying chiral power counting rules book:Weinberg . Our effective field theory for the scattering of Goldstone bosons off any heavy field is based on the assumption that the scattering amplitudes are perturbative at subthreshold energies with the expansion parameter $`Q/\mathrm{\Lambda }_\chi `$. The small scale $`Q`$ is to be identified with any small momentum of the system. The chiral symmetry-breaking scale is

$$\mathrm{\Lambda }_\chi 4\pi f1.13\mathrm{GeV},$$

with the parameter $`f90`$ MeV determined by the pion decay process. Once the available energy is sufficiently high to permit elastic two-body scattering a further typical dimensionless parameter $`m_K^2/(8\pi f^2)1`$ arises LK00 ; LK01 ; LK02  if strangeness is considered explicitly. This extra parameter invalidates any perturbative calculation within chiral SU(3) effective theory. Since this ratio is uniquely linked to two-particle reducible diagrams it is sufficient to sum those diagrams keeping the perturbative expansion of all irreducible diagrams, i.e. the coupled-channel Bethe-Salpeter equation has to be solved. This is the basis of the $`\chi `$-BS(3) approach developed in LK00 ; LK01 ; LK02 ; LK03 .

We identify the leading-order Lagrangian density Wein-Tomo ; Wise92 ; YCCLLY92 ; BD92  describing the interaction of Goldstone bosons with pseudo-scalar and vector mesons,

$`(x)`$ $`=`$ $`{\displaystyle \frac{1}{8f^2}}\mathrm{tr}\left[\mathrm{P}_{}(\mathrm{x})(^\nu \mathrm{P}_{}^{}(\mathrm{x}))(^\nu \mathrm{P}_{}(\mathrm{x}))\mathrm{P}_{}^{}(\mathrm{x})\right][\mathrm{\Phi }(\mathrm{x}),(_\nu \mathrm{\Phi }(\mathrm{x}))]_{}`$ (1)
$``$ $`{\displaystyle \frac{1}{8f^2}}\mathrm{tr}\left[\mathrm{P}^\mu (\mathrm{x})(^\nu \mathrm{P}_\mu ^{}(\mathrm{x}))(^\nu \mathrm{P}^\mu (\mathrm{x}))\mathrm{P}_\mu ^{}(\mathrm{x})\right][\mathrm{\Phi }(\mathrm{x}),(_\nu \mathrm{\Phi }(\mathrm{x}))]_{},`$
where $`\mathrm{\Phi }`$ is the octet of Goldstone boson fields and $`P`$ and $`P_\mu `$ are the triplets of massive pseudo-scalar and vector-meson fields in the matrix representation.

Within the $`\chi `$BS(3) approach LK02 ; LK03  the s-wave scattering amplitudes, $`M_{J^P}^{(I,S)}(\sqrt{s})`$ take the simple form

$`M_{J^P}^{(I,S)}(\sqrt{s})=\left[1V^{(I,S)}(\sqrt{s})J_{J^P}^{(I,S)}(\sqrt{s})\right]^1V^{(I,S)}(\sqrt{s}).`$ (2)
The effective interaction kernel $`V^{(I,S)}(\sqrt{s})`$ in (2) is determined by the leading order chiral SU(3) Lagrangian (1),

$`V^{(I,S)}(\sqrt{s})={\displaystyle \frac{C^{(I,S)}}{8f^2}}\left(3sM^2\overline{M}^2m^2\overline{m}^2{\displaystyle \frac{M^2m^2}{s}}(\overline{M}^2\overline{m}^2)\right),`$ (3)
where $`(m,M)`$ and $`(\overline{m},\overline{M})`$ are the masses of initial and final mesons. We use capital $`M`$ for the masses of heavy-light mesons and small $`m`$ for the masses of the Goldstone bosons. The matrix of coefficients $`C^{(I,S)}`$, that characterize the interaction strength in a given channel, and the loop functions $`J_{J^P}^{(I,S)}(\sqrt{s})`$ are given LK03 . As expected from heavy-quark symmetry the interaction kernels as well as the loop functions are identical for the $`0^{}`$ and $`1^{}`$ sectors in the limit $`M\mathrm{}`$.

In order to guarantee the perturbative nature of the scattering amplitude at subthreshold energies the $`\chi `$BS(3) approach insists on a renormalization condition of the form

$`M^{(I,S)}(\sqrt{s}=\mu ^{(I,S)})=V^{(I,S)}(\sqrt{s}=\mu ^{(I,S)})`$ (4)
with the natural subtraction scales

$`\mu _{0^+}^{(I,0)}=M_{D(1867)},\mu _{0^+}^{(I,\pm 1)}=M_{D_s(1969)},\mu _{0^+}^{(I,2)}=M_{D(1867)},`$
$`\mu _{1^+}^{(I,0)}=M_{D(2008)},\mu _{1^+}^{(I,\pm 1)}=M_{D_s(2110)},\mu _{1^+}^{(I,2)}=M_{D(2008)}.`$ (5)
A crucial ingredient of the $`\chi `$-BS(3) approach is a matching of s- and u-channel unitarized scattering amplitudes at subthreshold energies LK02 ; LK03 . This construction reflects our basic assumption that diagrams showing an s-channel or u-channel unitarity cut need to be summed to all orders at least at energies close to where the diagrams develop their imaginary part. By construction, a matched scattering amplitude satisfies crossing symmetry exactly at energies where the scattering process takes place. At subthreshold energies crossing symmetry is implemented approximatively only, however, to higher and higher accuracy when more chiral correction terms are considered. Insisting on the renormalization condition (4,5) guarantees that subthreshold amplitudes match smoothly and therefore the final ’matched’ amplitudes comply with the crossing-symmetry constraint to high accuracy. A conceivable small variation of the subtraction scales around their natural values (5) has very little effect on the results. In fact chiral correction terms modify the effective interaction $`V(\sqrt{s})`$ rather than giving rise to a modification of the subtraction scale LK02 ; LK03 ; HL03 . Changing the optimal subtraction scale (5) would deteriorate the quality of the matching of u- and s-channel unitarized amplitudes LK02 ; LK03 .

We turn to the results of the $`\chi `$-BS(3) approach for charmed mesons. It is instructive to explore first the SU(3) multiplet structure of the resonance states formed by the chiral coupled-channel dynamics. First the $`0^+`$ sector is discussed in a ’heavy’ SU(3) limit Copenhagen ; LK03  with $`m_{\pi ,K,\eta }=500`$ MeV and $`M_D=1800`$ MeV. In this case we obtain an anti-triplet of mass 2204 MeV with poles in the $`(0,+1),(1/2,0)`$ amplitudes. The sextet channel does not show a bound-state signal in this case. However if the attraction is increased slightly by using $`f=80`$ MeV rather than the canonical value $`90`$ MeV, poles at mass 2298 MeV arise in the $`(1,+1),(1/2,0),(0,1)`$ amplitudes. This finding reflects that the Weinberg-Tomozawa interaction,

$`\overline{3}8=\overline{3}6\overline{15}`$ (6)
predicts attraction in the anti-triplet and sextet channel but repulsion for the anti-15-plet. In contrast performing a ’light’ SU(3) limit Copenhagen ; LK03  with $`m_{\pi ,K,\eta }140`$ MeV together with $`M_D=1800`$ MeV we do not find any signal of a resonance in both anti-triplet and sextet channels. Analogous results are found in the $`1^+`$ sector.

To study the formation of meson resonances we generate speed plots speed  as suggested by Höhler Hoehler:speed  (for definitions cf. KL03 ). Fig. 1 shows the spectra of $`0^+`$ (left panel) and $`1^+`$ (right panel) as they arise in calculations with physical masses. We predict a bound state of mass 2303 MeV in the $`(0,1)`$-sector of $`0^+`$ mesons (see Fig. 1, left panel). According to BEH03 ; NRZ03  this state can be identified with a narrow resonance of mass 2317 MeV recently observed by the BABAR collaboration BaBar . Since we do not consider isospin violating processes like $`\eta \pi _0`$ the latter state is a true bound state in our present scheme. Given the fact that our computation is parameter-free this is a remarkable result. In the $`(1,+1)`$-speeds where we expect a signal from the sextet a strong cusp effect at the $`KD(1867)`$-threshold is seen. The large coupling constant to the $`\pi D_s(1969)`$ channel leads to the broad structure seen in the figure. Fig. 1 (left panel) illustrates that in the $`(\frac{1}{2},0)`$-sector we predict a narrow $`0^+`$ state of mass 2413 MeV just below the $`\eta D(1867)`$-threshold and a broad state of mass 2138 MeV. Modulo some mixing effects the heavier of the two is part of the sextet the lighter a member of the anti-triplet. The latter $`(\frac{1}{2},0)`$-state was expected to have a large branching ratio into the $`\pi D(1867)`$-channel BR03 ; NRZ03 . This is confirmed by our analysis. Finally in the $`(0,1)`$-speed a pronounced cusp effect at the $`\overline{K}D(1867)`$-threshold is seen.

The spectrum predicted for the $`1^+`$ states is very similar to the spectrum of the $`0^+`$ states. Fig. 1 (right panel) demonstrates that it is shifted up by approximatively 140 MeV with respect to the $`0^+`$ spectrum. The bound state in the $`(0,1)`$-sector comes at 2440 MeV. Thus the mass splitting of the $`1^+`$ and $`0^+`$ states in this channel agrees very well with the empirical value of about 140 MeV measured by the BABAR and CLEO collaborations BaBar ; CLEO . A narrow structure at 2552 MeV is predicted in the $`(\frac{1}{2},0)`$-channel which may be identified with the $`D(2420)`$-resonance PDG02 . Even though the resonance mass is overestimated by about 130 MeV our result is consistent with its small width of about 20 MeV. The triplet state in this sector of mass 2325 MeV has again a quite large width reflecting the strong coupling to the $`\pi D(2008)`$-channel. Finally we obtain strong cusp effects at the $`\overline{K}D(2008)`$\- and $`KD(2008)`$-thresholds in the $`(0,1)`$\- and $`(1,+1)`$-sectors. It is interesting to speculate whether chiral correction terms conspire to slightly increase the net attraction in these sectors. This would lead to a $`(0,1)`$-bound state. The fact that we overestimate the mass of the sextet state $`D(2420)`$ by about 130 MeV we take as a prediction that this should indeed be the case HL03 . An analogous statement holds for the $`0^+`$ sector since due to heavy-quark symmetry chiral correction effects in the $`0^+`$ and $`1^+`$ are identical at leading order.

To summarize: We presented a coupled-channel description of the meson-meson scattering in the open charm sector using the chiral SU(3) Lagrangian involving light-heavy $`J^P=0^{}`$ and $`J^P=1^{}`$ fields that transform non-linearly under the chiral SU(3) group. The major result of our study is the prediction of the charmed mesonic states with $`J^P=0^+,1^+`$ quantum numbers forming anti-triplet and sextet representations of the SU(3) group. This differs from the results implied by the chiral quark model leading to anti-triplet states only. Our result suggests the existence of $`J^P=0^+,1^+`$ states with unconventional quantum numbers $`(I,S)=(1,1)`$ and $`(I,S)=(0,1)`$.


format: text

text:
# Reply to “Comment on “Light-Front Schwinger Model at Finite Temperature””

## Abstract

In hep-th/0310278, Blankleider and Kvinikhidze criticize the form of the thermal propagator used in das1  and propose an alternate thermal propagator for the fermions in the light-front Schwinger model. We show that, within the standard light-front quantization used in das1 , the thermal propagator for the fermions is unique as presented in that paper.

In an earlier paper das1 , we studied various questions associated with the light-front Schwinger model at finite temperature where the theory was quantized on the standard light-front surface $`\overline{x}^0=x^0+x^1=0`$. (We refer the reader to das1  for notations and conventions.) We had argued in that paper that one of the components of the fermion field does not thermalize and correspondingly had used the real time propagator (only the $`++`$ component of the propagator and we will suppress the “$`iϵ`$” for simplicity)

$`iS_+^{(T)(\mathrm{DZ})}(\overline{p})`$ $`=`$ $`\overline{p}_1\left({\displaystyle \frac{i}{(2\overline{p}_0+\overline{p}_1)\overline{p}_1}}2\pi n_F(|\overline{p}_0|)\delta ((2\overline{p}_0+\overline{p}_1)\overline{p}_1)\right),`$
$`iS_{}^{(T)(\mathrm{DZ})}(\overline{p})`$ $`=`$ $`{\displaystyle \frac{i}{\overline{p}_1}},`$ (1)
where $`n_F(|\overline{p}_0|)`$ represents the Fermi-Dirac distribution function. This propagator was obtained from the structure of the fermion Lagrangian density of the light-front Schwinger model and was not derived from Eq. (33) in das1  which describes the propagator for a massive fermion in higher dimensions. (The authors in blankleider  seem to suggest that our propagator was derived from an erroneous limit of that expression.) We had, however, indicated that Eq. (1) can be obtained from Eq. (33) in das1  in a limiting manner. One of the results found in that paper showed that the off-shell thermal $`n`$-point photon amplitudes in this theory do not coincide with the ones calculated in the conventionally quantized (equal-time) Schwinger model das2  and we had traced the origin of the difference to the fact that one of the fermion components in the light-front Schwinger model is nondynamical in the quantization used and as a result does not thermalize, while both the fermion components in the conventionally quantized theory are dynamical and do thermalize. We note, on the other hand, that all the thermal corrections to the $`n`$-point photon amplitudes vanish at zero temperature in both the quantizations and the $`n`$-point photon amplitudes do coincide.

In blankleider  the authors comment that the difference found in das1  has its origin in the use of an erroneously simplified thermal fermion propagator and suggest that the proper thermal propagator for the fermions that should have been used in das1  is of the form (only the $`++`$ component)

$`iS_+^{(T)(\mathrm{BK})}(\overline{p})`$ $`=`$ $`\overline{p}_1\left({\displaystyle \frac{i}{(2\overline{p}_0+\overline{p}_1)\overline{p}_1}}2\pi n_F(|\overline{p}_0|)\delta ((2\overline{p}_0+\overline{p}_1)\overline{p}_1)\right),`$
$`iS_{}^{(T)(\mathrm{BK})}(\overline{p})`$ $`=`$ $`(2\overline{p}_0+\overline{p}_1)\left({\displaystyle \frac{i}{(2\overline{p}_0+\overline{p}_1)\overline{p}_1}}2\pi n_F(|\overline{p}_0|)\delta ((2\overline{p}_0+\overline{p}_1)\overline{p}_1)\right).`$ (2)
They obtain this propagator from Eq. (33) in das1  by setting $`m=0`$ (and restricting to $`1+1`$ dimensions). The difference between (1) and (2) lies in the thermal part of the propagator $`iS_{}^{(T)}(\overline{p})`$. Namely, their contention is that both components of the fermion field in the light-front Schwinger model should thermalize, even though one of them is nondynamical. In this case, of course, one should not expect any difference from the results of the conventionally quantized theory. The basic issue, therefore, is whether the $`\psi _{}`$ component in the light-front Schwinger model thermalizes in the quantization used in das1 .

Given the quantization conditions in a theory, the propagators are, of course, uniquely determined as vacuum expectation values of time ordered products of fields. Therefore, it is not entirely clear from blankleider , whether the authors find the fermion propagator in das1  to be incorrect within the quantization used or whether their objection is addressed to the quantization used in that paper. We will try to address both these issues in the following.

First, let us discuss the form of the propagator within the quantization used in das1 . There are various ways to see, both in the imaginary time and the real time formalisms, that the $`\psi _{}`$ component in the light-front Schwinger model does not thermalize in the standard light-front quantization used in das1 . We briefly discuss the imaginary time formalism before going into the real time formalism. We note that the quadratic part of the fermion Lagrangian density (which is relevant for a discussion of the propagator) for the light-front Schwinger model has the form

$$=i\psi _+^{}(2\overline{}_0+\overline{}_1)\psi _+i\psi _{}^{}\overline{}_1\psi _{}.$$
(3)
Here $`\psi _+,\psi _{}`$ represent the two chiral components of the theory. The zero temperature propagators of the theory in (3) have the simple forms

$$iS_+^{(0)}(\overline{p})=\frac{i\overline{p}_1}{(2\overline{p}_0+\overline{p}_1)\overline{p}_1}=\frac{i}{(2\overline{p}_0+\overline{p}_1)},iS_{}^{(0)}(\overline{p})=\frac{i(2\overline{p}_0+\overline{p}_1)}{(2\overline{p}_0+\overline{p}_1)\overline{p}_1}=\frac{i}{\overline{p}_1}.$$
(4)
In the imaginary time formalism in light-front theories within the quantization used in das1 , one obtains the thermal propagators simply by letting das3 ; weldon

$$\overline{p}_0(2n+1)i\pi T,$$
(5)
where $`T`$ denotes temperature. This introduces a temperature dependence to $`iS_+^{(T)}(\overline{p})`$ in (4), while $`iS_{}^{(T)}(\overline{p})`$ remains temperature independent since it does not depend on $`\overline{p}_0`$. This is probably the most direct way to see that the component $`\psi _{}`$ does not thermalize in the standard light-front quantization.

Let us next analyze the propagator in the real time formalism. This is best done in the operatorial formalism of thermofield dynamics umezawa ; das4 . We note that a Hamiltonian analysis of the theory in (3) shows that, when quantized on the surface $`\overline{x}^0=0`$, the only nontrivial anti-commutation relation has the form

$$\{\psi _+(\overline{x}),\psi _+^{}(\overline{y})\}_{\overline{x}^0=\overline{y}^0}=P^+\delta (\overline{x}^1\overline{y}^1),$$
(6)
where $`P^+`$ represents the projection operator for the positive chirality spinors. Since the fermion field $`\psi _{}`$ satisfies trivial anti-commutation relations, it follows in particular that

$$\{\psi _{}(\overline{x}),H\}=0,$$
(7)
namely, the $`\psi _{}`$ component has no time evolution. As a result, the propagator for the $`\psi _{}`$ field has the form

$$iS_{}^{(0)}(\overline{x}\overline{y})=0|\mathrm{T}\left(\psi _{}(\overline{x})\psi _{}^{}(\overline{y})\right)|0=0|\psi _{}(\overline{x})\psi _{}^{}(\overline{y})|0=F(\overline{x}^1\overline{y}^1),$$
(8)
which is consistent with the form of the zero temperature propagator $`iS_{}^{(0)}`$ in (4).

In going to finite temperature, in thermofield dynamics, one doubles the degrees of freedom (with tilde fields) and obtains a thermal vacuum through a Bogoliubov transformation of the form

$$|0(\beta )=U(\theta )|0|\stackrel{~}{0},$$
(9)
where $`\beta `$ represents the inverse temperature in units of the Boltzmann constant. The formally unitary transformation involves both the physical and the tilde fields and has the form

$$U(\theta )=e^{iQ(\theta )},$$
(10)
with the parameter $`\theta `$ related to the fermion distribution function umezawa ; das4 . The finite temperature propagator for the $`\psi _{}`$ field is then defined in the standard manner as

$$iS_{}^{(\beta )}(\overline{x}\overline{y})=0(\beta )|\mathrm{T}\left(\psi _{}(\overline{x})\psi _{}^{}(\overline{y})\right)|0(\beta ).$$
(11)
From (8)-(11) as well as the fact that $`\psi _{}`$ satisfies trivial anti-commutation relations in the standard light-front quantization, it follows that

$`iS_{}^{(\beta )}(\overline{x}\overline{y})`$ $`=`$ $`\stackrel{~}{0}|0|\left(e^{iQ(\theta )}\psi _{}(\overline{x})\psi _{}^{}(\overline{y})e^{iQ(\theta )}\right)|0|\stackrel{~}{0}=\stackrel{~}{0}|0|\left(\psi _{}(\overline{x})\psi _{}^{}(\overline{y})\right)|0|\stackrel{~}{0}`$ (12)
$`=`$ $`0|\psi _{}(\overline{x})\psi _{}^{}(\overline{y})|0=iS_{}^{(0)}(\overline{x}\overline{y})=F(\overline{x}^1\overline{y}^1).`$
This demonstrates clearly that within the standard light-front quantization used in das1 , the fermion field $`\psi _{}`$ does not thermalize and that the unique finite temperature propagator coincides with that at zero temperature which is the the form used in das1 .

As we had indicated in das1 , this form of the propagator can also be obtained from a limit of Eq. (33) (a massive propagator) of that paper. Essentially, this involves looking at the vanishing mass limit of a delta function of the form $`(2\overline{p}_0+\overline{p}_1)\delta ((2\overline{p}_0+\overline{p}_1)\overline{p}_1+m^2)`$. If $`m=0`$, there are two roots for the vanishing of the delta function. Keeping both the roots leads to the propagator in (2) which, however, would not be compatible with (12) and would lead to a nontrivial time dependence (in the coordinate space). Therefore, naively setting $`m=0`$ in Eq. (33) of das1  would not lead to the proper propagator within the quantization being discussed. The propagator in (12) (and, therefore, (1)), on the other hand, can be obtained from a massive theory (Eq. (33) of das1 ) only if a particular limiting value is chosen (namely, $`|\overline{p}_0|,|\overline{p}_1|m0`$) which selects out only the root $`(2\overline{p}_0+\overline{p}_1)=0`$ of the delta function. As is also noted in blankleider , the massless limit in light-front theories is subtle; therefore, when necessary one must go back to the basic definitions, as we have just done for the propagator (and as was also done in das1 ).

The authors of blankleider  have also argued how the $`\psi _{}`$ field can become dynamical in the non-standard light-front quantization due to McCartor mccartor  which involves quantizing the $`\psi _+`$ field on the conventional surface $`x^+=x^0+x^1=0`$ while quantizing the $`\psi _{}`$ component on the surface $`x^{}=x^0x^1=0`$. This brings us to the question of whether their objection is really to the quantization used in das1 . It is worth recognizing that a given quantization defines a unique quantum theory and different quantizations do not yield equivalent quantum theories in general. As McCartor himself has pointed out mccartor1 , his non-standard quantization leads to a vanishing fermion condensate (in the infinite volume limit) which is in disagreement with all the other calculations. The theory quantized on $`\overline{x}^0=x^0+x^1=0`$, on the other hand, does lead to the condensate prem  (even at finite temperature das1 ) which agrees with the results of equal-time quantization. Therefore, it is not clear a priori which of the two theories should be called the light-front Schwinger model (if that is the objection being raised by the authors in blankleider ). It is, of course, an interesting question to see if McCartor’s alternative quantization (or a generalization of it) does allow a statistical description (We remind the reader that the conventional light-front quantization does not.) and if so whether it leads to the propagator in Eq. (2) at finite temperature. Even if it does, that would not be the appropriate propagator to use in a calculation involving the standard light-front quantization such as in das1 . As we have argued above the propagator used in das1  is the unique propagator within that quantization and leads to the result that at zero temperature the $`n`$-point photon amplitudes agree with the calculations using equal-time relations, while at finite temperature, the results are different.

Acknowledgment:

This work was supported in part by US DOE Grant number DE-FG 02-91ER40685.


text:
# Early results from the VIMOS VLT Deep Survey

## 1. Introduction

Understanding how galaxies and large scale structures formed and evolved is one of the major goals of modern cosmology. In order to identify the relative contributions of the various physical processes at play and the associated timescales, a comprehensive picture of the evolutionary properties of the constituents of the universe is needed over a large volume and a large time base. Samples of high redshift galaxies known today reach less than a few thousand at redshifts $`13`$, and statistical analysis suffer from small number statistics, small explored volumes, selection biases, which prevent detailed analysis. In the local universe, large surveys like the 2dFGRS and the SDSS, will contain from $`2.5\times 10^5`$ up to $`10^6`$ galaxies to reach a high level of accuracy in measuring the fundamental parameters of the galaxies and AGNs populations. Similarly, we need to gather large numbers of galaxies at high redshifts to accurately describe the various populations in environments ranging from low density to the dense cluster cores, and relate the properties observed at different redshifts to identify the main processes driving evolution.

This goal can only be achieved through massive observational programs assembling galaxies and QSO samples representative of the universe at the various look-back times explored. As the observed galaxies are at large distances and therefore very faint, instruments have to be conceived to combine wide field, high throughput, and high multiplex gain in order to efficiently observe large samples. Multi-object spectrographs are routinely in operation since $``$15 years, and the new generation now in place on the $`610`$m telescopes, like DEIMOS on the Keck-10m or VIMOS on the VLT-8m, allows to explore large volumes of the distant universe through the observations of many tens of thousand of objects.

Because of this leap forward in instrument performances, several large deep surveys are now in progress. We are presenting here the VIMOS VLT Deep Survey (VVDS). It is combining a common observing strategy to assemble more than 100000 redshifts in 3 large galaxy datasets observed over more than 16deg2 in 5 equatorial fields, selected in magnitude from $`I_{AB}22.5`$ to $`I_{AB}25`$. The general strategy of the survey has been presented in e.g. Le Fèvre et al. (2001).

## 2. Survey observations status

The first survey observations have been conducted during the dark time of November and December 2002. A total of 29 nights have been allocated from the garanteed time, out of which 18 have been clear. The survey priority was set to accumulate as much observations as possible on the VVDS-0226-04 deep field, to a depth $`I_{AB}=24`$. The remaining time was spend on the 2217+00 and the 1002+03 fields, as part of the VVDS-wide survey. Targets have been selected from the deep imaging survey we have conducted in these fields (Le Fèvre et al., 2003). The VIMOS observations have been performed using 1 arcseconds wide slits and the LRRed grism. This provides a spectral resolution of $`R=210`$. The length of spectra at this resolution allows to pack on average 350–400 spectra for the “wide” $`I_{AB}22.5`$ survey on the 4 VIMOS detectors, and 500 to 600 spectra (figure 1) for the “faint” $`I_{AB}24`$, a key factor to accumulate redshifts in a very efficient way.

For a magnitude limited sample potentialy going to redshifts up to $`5`$, the choice of the observed wavelength range is difficult: too blue and the rest frame domain around OII-4000$`\AA `$ break which contains strong features, disappears from the band already for $`z1`$, too red and the UV domain comes into the band for quite high redshifts. We have compromised with a wavelength domain $`55009400\AA `$, which allows to follow \[OII\] up to $`z=1.5`$, at the expense of having to deal with the faint absorption features present in the rest frame domain corresponding to the redshift range $`1.5<z<3`$.

A total of 49 pointings (one pointing is a set of 4 masks in each of the 4 VIMOS quadrants) have been observed, and a total of 20741 spectra have been obtained, some objects being observed in two different pointings to measure the redshift measurement errors associated to the observational process.

## 3. Data processing and redshift measurement

The data processing is conducted in two steps. First the large number of raw data frames are organised in the object data and various calibration categories. This is followed by 2D spectra extraction, sky correction, sum/combine, and then by 1D optimal spectra extraction, wavelength and flux calibration. This is performed very efficiently with the VVDS consortium pipeline VIPGI with a minimum of human interaction (Scodeggio et al., in preparation).

The KBRED environment developed under IDL is then used to compute redshifts (Scaramella et al., in preparation). KBRED is run automatically on the whole sample, followed by systematic examination of each single spectrum by eye in the VIPGI environment. KBRED basically works by cross-correlation of observed spectra with a set of library template spectra followed by a reconstruction of each spectrum on a base of template vectors (Principal Component Analysis, PCA). There are two main limitations for this process to be fully automated. Because the range of possible redshift solutions to explore is large, with objects as diverse as stars, galaxies with redshifts possibly up to z=5 or more, or AGNs, it is essential to assemble as complete as possible a set of star templates, galaxies and AGN templates covering the full rest frame wavelength range from Ly$`\alpha 1216`$ to H$`\alpha 6562\AA `$, for early to late spectral types. Because of the lack of observed template spectra in the literature in the range between CIV-1548 and OII-3727, critical for redshifts $`1.53`$ given our wavelength range, we had to devise a scheme to go through this so called “redshift desert”, which is obviously only produced by the observational bias of spectroscopy set-ups. We have taken an iterative approach, creating templates from VIMOS spectra, and updating them along the reduction process as new galaxies are identified at redshifts $`z>1.3`$. This process is helping to significantly reduce the first-pass incompletness, and we are identifying several hundred galaxies beyond z=1.5 (Le Fèvre et al., in preparation). The second limitation is linked to the residuals of the sky subtraction and fringing correction still present in the reduced spectra which produce a noise pattern highly non linear, variable from spectra to spectra. Eye examination of both the 2D and 1D spectra are therefore sometimes required to validate a redshift proposed by KBRED. We are currently working at computing a two 2D noise model in each slit to help reduce this limitation.

Example spectra processed through VIPGI and KBRED are shown in Figures 6 and 7.

## 4. Redshift distribution to $`I_{AB}=22.5`$ and $`I_{AB}=24`$

The redshift distribution of the $`I_{AB}=24`$ sample is presented in Figure 2, the first time such a distribution is observed to this depth. At the time of this writing, this distribution is affected by incompletness above $`z1.5`$, waiting for a complete treatment of the as yet unidentified spectra as described in the previous section. However, there are two main features to be noted: the mean redshift is $`<z>=0.7`$, and there is a small but significant high redshift tail of galaxies identified up to z=5. In comparison, our $`I_{AB}=22.5`$ sample shows a mean redshift of $`<z>=0.6`$ (Figure 2). Most semi-analytic models make predictions for a higher mean redshift and a more numerous high redshift tail above z=1.5 for a $`I_{AB}=24`$ limited sample. While our current incompletness is most probably caused by objects at $`z>1`$ as identified from photometric redshifts estimates, unidentified objects cannot significantly affect the mean redshift of the full sample. This is dicussed in more details in Le Fèvre et al. (in preparation).

## 5. Evolution of the luminosity function

With the current sample, we can compute the luminosity function out to $`z1.5`$ although our current incompletness starts to kick in at $`z>1.2`$. Figure 3 shows the luminosity function of a $`I_{AB}=24`$ sample of 4015 galaxies, as a function of redshift out to z=1.5. There is an overall brightening of the luminosity by about 1 magnitude at $`z1`$, with a strong steepening of the faint end slope clearly identified (see Zucca et al., in preparation).

Since we have sufficient number statistics, we can for the first time break up the evolution of the LF by galaxy spectral types with the current data set reliably up to redshifts $`z1.2`$ and $`M_{B_{AB}}19`$. Each galaxy can be assigned a spectral type based on the SED model fitting of the photometric data (covering a larger wavelength base than the spectra themselves). With all galaxies classified in 4 types, the LF build for the two extreme types of the sample, early types and blue star forming spectral types is shown in Figure 4 & 5. While the LF of the early type population seems not to be evolving my more than 0.5 mag., the LF of the blue star forming galaxies is strongly evolving with redshift, with the L\* luminosity measured from the Schechter function fit increasing by more than two magnitudes by redshift $`1`$. This strong differential evolution vs. spectral type is discussed in Ilbert et al., in preparation.

We will aim to describe the evolution of the population vs. type as well as vs. local galaxy density when the processing of the current sample is complete.

## 6. Other VVDS products

The luminosity density and the star formation rate history are being produced from the luminosity functions. We will be computing the correlation function $`\xi (r_p,\pi ,z)`$ and $`w(r_p,z)`$ projections for the full sample as well as per each galaxy spectral type to map the evolution of the clustering vs. redshift.

Several other data products are directly available from the VVDS because it is a magnitude limited survey. About 100 type 1 AGNs have been identified in the current sample, the highest redshift QSO being at $`z=5.000`$ (Figure 5), this faint AGN sample is highly complementary to other surveys to date since it is surveying AGNs $`23`$ magnitudes deeper. Several clusters of galaxies are being identified and their properties studied.

The high redshift population observed in the VVDS is a unique sample assembled from a purely magnitude selected photometric sample. This galaxy census, when complete, will enable to derive evolution out to $`z4`$ from within the same, large, homogeneous sample.

The VVDS is extending to multiwavelength observations: we have been conducting a deep radio survey (Bondi et al., 2003), and are associated with other teams conducting observations at other wavelengths: Galex, XMM, SIRTF. Furthermore, the VVDS-10h field is now the target of the COSMOS program with a 640 orbits HST-ACS coverage of 2 deg2, with extensive multi-wavelength coverage (P.I.: N. Scoville).

## 7. Summary

The VVDS is on-going. The preliminary first epoch results show:
– a mean redshift lower than anticipated for a $`I_{AB}24`$ sample, despite a high redshift tail reaching $`z5`$.
– a strong evolution of the global LF out to $`z1.5`$, with the blue star forming galaxies identified as the population carrying most of the evolution, while the LF of the early type (“redder”) galaxies does not seem to evolve much.

Many different properties of the sample are being currently being explored.

## References

Bondi, M., Ciliegi, P., et al., 2003, A&A, 403, 857

Le Fèvre, O., Vettolani, G., et al., 2001, ESO Astrophysics Symposia Series “Deep Fields”, Cristiani, Renzini, Williams, Eds, Springer, p.231

Le Fèvre, O., Mellier, Y., McCracken, H.J., et al., 2003, A&A, in press


text:
# An Optimal Algorithm for the Maximum-Density Segment ProblemAn early version of this paper was presented at 11th Annual European Symposium on Algorithms, Budapest, Hungary, September 15-20, 2003.

## 1 Introduction

We address the following fundamental problem: The input consists of two numbers $`w_{\mathrm{min}}`$ and $`w_{\mathrm{max}}`$ and a sequence $`S`$ of number pairs $`(a_i,w_i)`$ with $`w_i>0`$ for $`i=1,\mathrm{},n`$. A segment $`S(i,j)`$ is a consecutive subsequence of $`S`$ starting with index $`i`$ and ending with index $`j`$. For a segment $`S(i,j)`$, the width is $`w(i,j)=w_i+w_{i+1}+\mathrm{}+w_j`$, and the density is $`d(i,j)=(a_i+a_{i+1}+\mathrm{}+a_j)/w(i,j)`$. It is not difficult to see that with an $`O(n)`$-time preprocessing to compute all $`O(n)`$ prefix sums $`a_1+a_2+\mathrm{}+a_j`$ and $`w_1+w_2+\mathrm{}+w_j`$, the density of any segment can be computed in $`O(1)`$ time. $`S(i,j)`$ is feasible if $`w_{\mathrm{min}}w(i,j)w_{\mathrm{max}}`$. The maximum-density segment problem is to find a maximum-density segment over all $`O(n^2)`$ feasible segments.

This problem arises from the investigation of non-uniformity of nucleotide composition within genomic sequences, which was first revealed through thermal melting and gradient centrifugation experiments . The GC content of the DNA sequences in all organisms varies from 25% to 75%. GC-ratios have the greatest variations among bacteria’s DNA sequences, while the typical GC-ratios of mammalian genomes stay in 45-50%. Despite intensive research effort in the past two decades, the underlying causes of the observed heterogeneity remain debatable . Researchers  observed that the compositional heterogeneity is highly correlated to the GC content of the genomic sequences. Other investigations showed that gene length , gene density , patterns of codon usage , distribution of different classes of repetitive elements , number of isochores , lengths of isochores , and recombination rate within chromosomes  are all correlated with GC content. More research related to GC-rich segments can be found in  and the references therein.

In the most basic form of the maximum-density segment problem, the sequence $`S`$ corresponds to the given DNA sequence, where $`a_i=1`$ if the corresponding nucleotide in the DNA sequence is G or C; and $`a_i=0`$ otherwise. In the work of Huang , sequence entries took on values of $`p`$ and $`1p`$ for some real number $`0p1`$. More generally, we can look for regions where a given set of patterns occur very often. In such applications, $`a_i`$ could be the relative frequency that the corresponding DNA character appears in the given patterns. Further natural applications of this problem can be designed for sophisticated sequence analysis such as mismatch density , ungapped local alignments , annotated multiple sequence alignments , promoter mapping , and promoter recognition .

For the uniform case, i.e., $`w_i=1`$ for all indices $`i`$, Nekrutendo and Li , and Rice, Longden and Bleasby  employed algorithms for the case $`w_{\mathrm{min}}=w_{\mathrm{max}}`$, which is trivially solvable in $`O(n)`$ time. More generally, when $`w_{\mathrm{min}}w_{\mathrm{max}}`$, the problem is also easily solvable in $`O(n(w_{\mathrm{max}}w_{\mathrm{min}}+1))`$ time, linear in the number of feasible segments. Huang  studied the case where $`w_{\mathrm{max}}=n`$, i.e., there is effectively no upper bound on the width of the desired maximum-density segments. He observed that an optimal segment exists with width at most $`2w_{\mathrm{min}}1`$. Therefore, this case is equivalent to the case with $`w_{\mathrm{max}}=2w_{\mathrm{min}}1`$ and can be solved in $`O(nw_{\mathrm{min}})`$ time in a straightforward manner. Lin, Jiang, and Chao  gave an $`O(n\mathrm{log}w_{\mathrm{min}})`$-time algorithm for this case based on right-skew decompositions of a sequence. (See  for a related software.) The case with general $`w_{\mathrm{max}}`$ was first investigated by Goldwasser, Kao, and Lu , who gave an $`O(n)`$-time algorithm for the uniform case. Recently, Kim  showed an alternative algorithm based upon a geometric interpretation of the problem, which basically relates the maximum-density segment problem to the fundamental slope selection problem in computational geometry . Unfortunately, Kim’s analysis of time complexity has some flaw which seems difficult to fix.111Kim claims that all the progressive updates of the lower convex hulls $`L_jR_j`$ can be done in overall linear time. The paper only sketches how to obtain $`L_{j+1}R_{j+1}`$ from $`L_jR_j`$. (See the fourth-to-last paragraph of page 340 in .) Unfortunately, Kim seems to overlook the marginal cases when the upper bound $`w_{\mathrm{max}}`$ forces the $`p_z`$ of $`L_jR_j`$ to be deleted from $`L_{j+1}R_{j+1}`$. As a result, obtaining $`L_{j+1}R_{j+1}`$ from $`L_jR_j`$ could be much more complicated than Kim’s sketch. A naive implementation of Kim’s algorithm still takes $`\mathrm{\Omega }(n(w_{\mathrm{max}}w_{\mathrm{min}}+1))`$ time in the worst case. We believe that any correct implementation of Kim’s algorithm requires $`\mathrm{\Omega }(n\mathrm{log}(w_{\mathrm{max}}w_{\mathrm{min}}+1))`$ time in the worse case. For the general (i.e., non-uniform) case, Goldwasser, Kao, and Lu  also gave an $`O(n\mathrm{log}(w_{\mathrm{max}}w_{\mathrm{min}}+1))`$-time algorithm. By bypassing the complicated preprocessing step required in , we successfully reduce the required time for the general case down to $`O(n)`$. Our result is based upon the following set of equations, stating that the order of $`d(x,y)`$, $`d(y+1,z)`$, and $`d(x,z)`$ with $`xy<z`$ can be determined by that of any two of them:

$$\begin{array}{c}d(x,y)d(y+1,z)d(x,y)d(x,z)d(x,z)d(y+1,z);\\ d(x,y)d(y+1,z)d(x,y)d(x,z)d(x,z)d(y+1,z).\end{array}$$
(1)
(Both equations can be easily verified by observing the existence of some number $`\rho `$ with $`0<\rho <1`$ and $`d(x,z)=\rho d(x,y)+(1\rho )d(y+1,z)`$. See Figure 1.) Our algorithm is capable of processing the input sequence in an online manner, which is an important feature for dealing with genome-scale sequences.

For bioinformatics applications, e.g., in , the input sequence $`S`$ is usually very sparse. That is, $`S`$ can be represented by $`m=o(n)`$ triples $`(a_1^{},w_1^{},n_1),(a_2^{},w_2^{},n_2),\mathrm{},(a_m^{},w_m^{},n_m)`$ with $`0=n_0<n_1<n_2<\mathrm{}<n_m=n`$ to signify that $`(a_i,w_i)=(a_j^{},w_j^{})`$ holds for all indices $`i`$ and $`j`$ with $`n_{j1}<in_j`$ and $`1jm`$. If $`w_j^{}=1`$ holds for all $`1jm`$, we show how to exploit the sparsity of $`S`$ and solve the maximum-density problem for $`S`$ given in the above compact representation in $`O(m)`$ time.

The remainder of the paper is organized as follows. Section 2 shows the main algorithm. Section 3 explains how to cope with the simple case that the width upper bound $`w_{\mathrm{max}}`$ is ineffective. Section 4 takes care of the more complicated case that $`w_{\mathrm{max}}`$ is effective. Section 5 explains how to exploit the sparsity of the input sequence for the uniform case.

## 2 The main algorithm

For any integers $`x`$ and $`y`$, let $`[x,y]`$ denote the set $`\{x,x+1,\mathrm{},y\}`$. Throughout the paper, we need the following definitions and notation with respect to the input length-$`n`$ sequence $`S`$ and width bounds $`w_{\mathrm{min}}`$ and $`w_{\mathrm{max}}`$. Let $`j_0`$ be the smallest index with $`w(1,j_0)w_{\mathrm{min}}`$. Let $`J=[j_0,n]`$. For each $`jJ`$, let $`\mathrm{}_j`$ (respectively, $`r_j`$) be the smallest (respectively, largest) index $`i`$ with $`w_{\mathrm{min}}w(i,j)w_{\mathrm{max}}`$. That is, $`S(i,j)`$ is feasible if and only if $`i[\mathrm{}_j,r_j]`$. (Figure 3 is an illustration for the definitions of $`\mathrm{}_j`$ and $`r_j`$.) Clearly, for the uniform case, we have $`\mathrm{}_{i+1}=\mathrm{}_i+1`$ and $`r_{i+1}=r_i+1`$. As for the general case, we only know that $`\mathrm{}_j`$ and $`r_j`$ are both (not necessarily monotonically) increasing. One can easily compute all $`\mathrm{}_j`$ and $`r_j`$ in $`O(n)`$ time. Let $`i_j^{}`$ be the largest index $`k[\mathrm{}_j,r_j]`$ with $`d(k,j)=\mathrm{max}\{d(i,j)i[\mathrm{}_j,r_j]\}`$. Clearly, there must be an index $`j^{}`$ such that $`S(i_j^{}^{},j^{})`$ is a maximum-density segment of $`S`$. Therefore, a natural but seemingly difficult possibility to solve the maximum-density segment problem would be to compute $`i_j^{}`$ for all indices $`jJ`$ in $`O(n)`$ time. Instead, our strategy is to compute an index $`i_j[\mathrm{}_j,r_j]`$ for each index $`jJ`$ by the algorithm shown in Figure 2, where $`\varphi (x,y)`$ is defined to be the largest index $`z[x,y]`$ that minimizes $`d(x,z)`$. That is, $`S(x,\varphi (x,y))`$ is the longest minimum-density prefix of $`S(x,y)`$. The rest of the section ensures the correctness of our algorithm by showing $`i_j^{}=i_j^{}^{}`$, and thus reduces the maximum-density segment problem to implementing our algorithm to run in $`O(n)`$ time.

###### Lemma 1

The index returned by function call $`\text{best}(\mathrm{},r,j)`$ is the largest index $`i[\mathrm{},r]`$ that maximizes $`d(i,j)`$.

Proof.  Let $`i^{}`$ be the largest index in $`[\mathrm{},r]`$ that maximizes $`d(i,j)`$, i.e., $`d(i^{},j)=\mathrm{max}_{i[\mathrm{},r]}d(i,j)`$. Let $`i_j`$ be the index returned by function call $`\text{best}(\mathrm{},r,j)`$. We show $`i_j=i^{}`$ as follows. If $`i_j<i^{}`$, then $`i_j<r`$. By the condition of the while-loop at Step 2 of best, we know $`d(i_j,\varphi (i_j,r1))>d(i_j,j)`$. By $`d(i_j,j)d(i^{},j)`$ and Equation (1), we have $`d(i_j,i^{}1)d(i_j,j)`$. It follows that $`d(i_j,i^{}1)<d(i_j,\varphi (i_j,r1))`$, contradicting the definition of $`\varphi (i_j,r1)`$.

On the other hand, suppose that $`i_j>i^{}`$. By definition of best, there must be an index $`i[\mathrm{},r]`$ with $`i<r`$, $`d(i,\varphi (i,r1))d(i,j)`$, and $`ii^{}<\varphi (i,r1)+1`$. If $`i=i^{}`$, by Equation (1) we have $`d(i^{},\varphi (i^{},r1))d(i^{},j)d(\varphi (i^{},r1)+1,j)`$, where the last inequality contradicts the definition of $`i^{}`$. Now that $`i<i^{}`$, we have $`d(i^{},j)d(i,j)d(i,i^{}1)d(i,\varphi (i,r1))d(i^{},\varphi (i,r1))`$, where (a) the first inequality is by definition of $`i^{}`$, (b) the second inequality is by Equation (1) and the first inequality, (c) the third inequality is by $`i^{}\varphi (i,r1)`$ and definition of $`\varphi (i,r1)`$, and (d) the last inequality is by Equation (1) and the third inequality. It follows from $`d(i^{},j)d(i^{},\varphi (i,r1))`$ and Equation (1) that $`d(\varphi (i,r1)+1,j)d(i^{},j)`$, contradicting the definition of $`i^{}`$ by $`i^{}<\varphi (i,r1)+1`$.

###### Theorem 1

Algorithm main correctly solves the maximum-density problem.

Proof.  We prove the theorem by showing $`i_j^{}=i_j^{}^{}`$. Clearly, by $`\mathrm{}_{j_0}=i_{j_01}=1`$ and Lemma 1, the equality holds if $`j^{}=j_0`$. The rest of the proof assumes $`j^{}>j_0`$. By Lemma 1 and $`\mathrm{}_j^{}i_j^{}^{}`$, it suffices to ensure $`i_{j^{}1}i_j^{}^{}`$. Assume for contradiction that there is an index $`j[j_0,j^{}1]`$ with $`i_{j1}i_j^{}^{}<i_j`$. By $`j<j^{}`$, we know $`\mathrm{}_ji_j^{}^{}`$. By Lemma 1 and $`\mathrm{max}(\mathrm{}_j,i_{j1})i_j^{}^{}<i_jr_j`$, we have $`d(i_j,j)d(i_j^{}^{},j)`$. It follows from Equation (1) and $`i_j^{}^{}<i_j`$ that $`d(i_j^{}^{},j)d(i_j^{}^{},i_j1)`$. By $`\mathrm{}_j^{}i_j^{}^{}<i_jr_j^{}`$ and definition of $`j^{}`$, we know $`d(i_j^{}^{},j^{})>d(i_j,j^{})`$. It follows from $`i_j^{}^{}<i_j`$ and Equation (1) that $`d(i_j^{}^{},i_j1)>d(i_j^{}^{},j^{})`$. Therefore, $`d(i_j,j)d(i_j^{}^{},j)d(i_j^{}^{},i_j1)>d(i_j^{}^{},j^{})`$, contradicting the definition of $`j^{}`$.

One can verify that the value of $`i`$ increases by at least one each time Step 3 of best is executed. Therefore, to implement the algorithm to run in $`O(n)`$ time, it suffices to maintain a data structure to support $`O(1)`$-time query for each $`\varphi (i,r_j1)`$ in Step 2 of best.

## 3 Coping with ineffective width upper bound

When $`w_{\mathrm{max}}`$ is ineffective, i.e., $`w_{\mathrm{max}}w(1,n)`$, we have $`\mathrm{}_j=1`$ for all $`jF`$. Therefore, the function call in Step 3 of main is exactly $`\text{best}(i_{j1},r_j,j)`$. Moreover, during the execution of the function call $`\text{best}(i_{j1},r_j,j)`$, the value of $`i`$ can only be $`i_{j1}`$, $`\varphi (i_{j1},r_j1)+1`$, $`\varphi (\varphi (i_{j1},r_j1)+1,r_j1)+1,\mathrm{},r_j`$. Suppose that a subroutine call to $`\text{update}(j)`$ yields an array $`\mathrm{\Phi }`$ of indices and two indices $`p`$ and $`q`$ of $`\mathrm{\Phi }`$ with $`pq`$ and $`\mathrm{\Phi }[p]=i_{j1}`$ such that the following condition holds.

$`\mathrm{\Phi }[q]=r_j`$ and $`\mathrm{\Phi }[t]=\varphi (\mathrm{\Phi }[t1],r_j1)+1`$ holds for each index $`t[p+1,q]`$.

(See Figure 4 for an illustration.) Then, the subroutine call to $`\text{best}(i_{j1},r_j,j)`$ can clearly be replaced by $`\text{lbest}(j)`$, as defined in Figure 5. That is, $`\text{lbest}(j)`$ can access the value of each $`\varphi (i,r_j1)`$ by looking up $`\mathrm{\Phi }`$ in $`O(1)`$ time. It remains to show how to implement $`\text{update}(j)`$ such that all $`O(n)`$ subroutine calls to update from Step 3 of lmain run in overall $`O(n)`$ time. The following lemma is crucial in ensuring the correctness and efficiency of our implementation shown in Figure 5, where Condition $`C_{j_01}`$ stands for $`p=1`$, $`q=0`$, and $`i_{j_01}=1`$.

###### Lemma 2

For each index $`jJ`$, the following statements hold.

1. If Condition $`C_{j1}`$ holds right before calling $`\text{update}(j)`$, then Condition $`C_j`$ holds right after the subroutine call.
2. If Condition $`C_j`$ holds right before calling $`\text{lbest}(j)`$, then the index returned by the function call is exactly that returned by $`\text{best}(\mathrm{\Phi }[p],\mathrm{\Phi }[q],j)`$.

Proof.  Statement 1. It is not difficult to verify that with the initialization $`p=1`$, $`q=0`$, and $`i_{j_01}=1`$, Condition $`C_{j_0}`$ holds with $`p=1`$ and $`q1`$ after calling $`\text{update}(j_0)`$. The rest of the proof assumes $`jJ\{j_0\}`$. For each $`r[r_{j1}+1,r_j]`$, one can see from the definition of $`\varphi `$ that $`\varphi (\mathrm{},r1)`$ is either $`\varphi (\mathrm{},r2)`$ or $`r1`$. More precisely, we have $`\varphi (\mathrm{},r1)=r1`$ if and only if $`d(\mathrm{},\varphi (\mathrm{},r2))d(\mathrm{},r1)`$. Furthermore, if $`\varphi (\mathrm{},r2)<r2`$, then one can prove as follows that $`\varphi (\varphi (\mathrm{},r2)+1,r1)=\varphi (\varphi (\mathrm{},r2)+1,r2)`$ implies $`\varphi (\mathrm{},r1)=\varphi (\mathrm{},r2)`$.

> Let $`m=\varphi (\mathrm{},r2)`$. By $`\varphi (m+1,r1)=\varphi (m+1,r2)`$, we have $`d(m+1,\varphi (m+1,r1))<d(m+1,r1)`$. By definition of $`\varphi `$ and Equation (1), we have $`d(\mathrm{},m)<d(m,\varphi (m+1,r1))<d(m+1,\varphi (m+1,r1))`$. As a result, we have $`d(\mathrm{},m)<d(m+1,r1)`$, which by Equation (1) implies $`d(\mathrm{},m)<d(\mathrm{},r1)`$. Thus $`\varphi (\mathrm{},r1)=\varphi (\mathrm{},r2)`$.

Therefore, at the end of each iteration of the for-loop of $`\text{update}(j)`$, we have that $`\mathrm{\Phi }[q]=r`$ and $`\mathrm{\Phi }[t]=\varphi (\mathrm{\Phi }[t1],r1)+1`$ holds for each index $`t[p+1,q]`$. (The value of $`q`$ may change, though.) It follows that at the end of the for-loop, Condition $`C_j`$ holds.

Statement 2. By Condition $`C_j`$, one can easily verify that $`\text{lbest}(j)`$ is a faithful implementation of $`\text{best}(\mathrm{\Phi }[p],\mathrm{\Phi }[q],j)`$. Therefore, the statement holds.

###### Lemma 3

The implementation lmain solves the maximum-density problem for the case with ineffective $`w_{\mathrm{max}}`$ in $`O(n)`$ time.

Proof.  By Lemma 2(1) and definitions of update and lbest, both Condition $`C_j`$ and $`\mathrm{\Phi }[p]=i_{j1}`$ hold right after the subroutine call to $`\text{update}(j)`$. By Condition $`C_j`$ and Lemma 2(2), $`\text{lbest}(j)`$ is a faithful implementation of $`\text{best}(\mathrm{\Phi }[p],\mathrm{\Phi }[q],j)`$. Therefore, the correctness of lmain follows from $`\mathrm{\Phi }[p]=i_{j1}`$, $`\mathrm{\Phi }[q]=r_j`$, and Theorem 1.

As for the efficiency of lmain, observe that $`qp1`$ holds throughout the execution of lmain. Note that each iteration of the while-loops of lbest and update decreases the value of $`qp`$ by one. Clearly, Step 4 of update is the only place that increases the value of $`qp`$. Since it increases the value of $`qp`$ by one for $`O(n)`$ times, the overall running time of lmain is $`O(n)`$.

## 4 Coping with effective width upper bound

In contrast to the previous simple case, when $`w_{\mathrm{max}}`$ is arbitrary, $`\mathrm{}_j`$ may not always be $`1`$. Therefore, the first argument of the function call in Step 3 of main could be $`\mathrm{}_j`$ with $`\mathrm{}_j>i_{j1}`$. It seems quite difficult to update the corresponding data structure $`\mathrm{\Phi }`$ in overall linear time such that both $`\mathrm{\Phi }[p]=\mathrm{max}(i_{j1},\mathrm{}_j)`$ and Condition $`C_j`$ hold throughout the execution of our algorithm. To overcome the difficulty, our algorithm sticks with Condition $`C_j`$ but allows $`\mathrm{\Phi }[p]>\mathrm{max}(i_{j1},\mathrm{}_j)`$. As a result, $`\mathrm{max}_{jJ}d(i_j,j)`$ may be less than $`\mathrm{max}_{jJ}d(i_j^{},j)`$. Fortunately, this potential problem can be resolved if we simultaneously solve a series of variant versions of the maximum-density segment problem.

### 4.1 A variant version of the maximum-density segment problem

Suppose that we are given two indices $`r`$ and $`y_0`$ with $`w(r,y_0)w_{\mathrm{min}}`$. Let $`X=[\mathrm{},r]`$ and $`Y=[y_0,y_1]`$ be two intervals such that $`\mathrm{}=\mathrm{}_{y_0}`$ and and $`y_1`$ is the largest index in $`J`$ with $`w(r,y_1)w_{\mathrm{max}}`$. See Figure 6 for an illustration. The variant version of the maximum-density segment problem is to look for a maximum-density segment over all feasible segments $`S(x,y)`$ with $`xX`$, $`yY`$, and $`w_{\mathrm{min}}w(x,y)w_{\mathrm{max}}`$ such that $`d(x,y)`$ is maximized.

For each $`yY`$, let $`x_y^{}`$ be the largest index $`xX`$ with $`w_{\mathrm{min}}w(x,y)w_{\mathrm{max}}`$ that maximizes $`d(x,y)`$. Let $`y^{}`$ be an index in $`Y`$ with $`d(x_y^{}^{},y^{})=\mathrm{max}_{yY}d(x_y^{},y)`$. Although solving the variant version can naturally be reduced to computing the index $`x_y^{}`$ for each index $`yY`$, the required running time is more than what we can afford. Instead, we compute an index $`x_yX`$ with $`w_{\mathrm{min}}w(x_y,y)w_{\mathrm{max}}`$ for each index $`yY`$ such that $`x_y^{}=x_y^{}^{}`$. By $`w(r,y_0)w_{\mathrm{min}}`$ and $`w(r,y_1)w_{\mathrm{max}}`$, one can easily see that, for each $`yY`$, $`r`$ is always the largest index $`xX`$ with $`w_{\mathrm{min}}w(x,y)w_{\mathrm{max}}`$. Our algorithm for solving the variant problem is as shown in Figure 7, presented in a way to emphasize the analogy between vmain and main. For example, the index $`x_y`$ in vmain is the counterpart of the index $`i_j`$ in main. Also, the index $`r`$ in vmain plays the role of the index $`r_j`$ in main. We have the following lemma whose proof is very similar to that of Theorem 1.

###### Lemma 4

Algorithm vmain correctly solves the variant version of the maximum-density problem.

Proof.  We prove the theorem by showing $`x_y^{}=x_y^{}^{}`$. Clearly, by $`\mathrm{}_{y_0}=x_{y_01}=\mathrm{}`$ and Lemma 1, the equality holds if $`y^{}=y_0`$. The rest of the proof assumes $`y^{}>y_0`$. By Lemma 1 and $`\mathrm{}_y^{}x_y^{}^{}`$, it suffices to ensure $`x_{y^{}1}x_y^{}^{}`$. Assume for contradiction that there is an index $`y[y_0,y^{}1]`$ with $`x_{y1}x_y^{}^{}<x_y`$. By $`y<y^{}`$, we know $`\mathrm{}_yx_y^{}^{}`$. By Lemma 1 and $`\mathrm{max}(\mathrm{}_y,x_{y1})x_y^{}^{}<x_yr`$, we have $`d(x_y,y)d(x_y^{}^{},y)`$. It follows from Equation (1) and $`x_y^{}^{}<x_y`$ that $`d(x_y^{}^{},y)d(x_y^{}^{},x_y1)`$. By $`\mathrm{}_y^{}x_y^{}^{}<x_yr`$ and definition of $`y^{}`$, we know $`d(x_y^{}^{},y^{})>d(x_y,y^{})`$. It follows from $`x_y^{}^{}<x_y`$ and Equation (1) that $`d(x_y^{}^{},x_y1)>d(x_y^{}^{},y^{})`$. Therefore, $`d(x_y,y)d(x_y^{}^{},y)d(x_y^{}^{},x_y1)>d(x_y^{}^{},y^{})`$, contradicting the definition of $`y^{}`$.

Again, the challenge lies in supporting each query to $`\varphi (i,r1)`$ of best in $`O(1)`$ time during the execution of vmain. Fortunately, unlike during the execution of main where both parameters of $`\varphi (i,r1)`$ may change, the second parameter $`r1`$ is now fixed. Therefore, to support each query to $`\varphi (i,r1)`$ in $`O(1)`$ time, we can actually afford $`O(r\mathrm{}+1)`$ time to compute a data structure $`\mathrm{\Psi }`$ such that $`\mathrm{\Psi }[i]=\varphi (i,r1)`$ for each $`i[\mathrm{},r1]`$. As a result, the function best can be implemented as the function vbest shown in Figure 8. The following lemma ensures the correctness and efficiency of our implementation variant shown in Figure 8.

###### Lemma 5

The implementation variant correctly solves the variant version of the maximum-density segment problem in $`O(r\mathrm{}+y_1y_0+1)`$ time.

Proof.  Clearly, if $`\mathrm{\Psi }[i]=\varphi (i,r1)`$ holds for each index $`i[\mathrm{},r1]`$, then vbest is a faithful implementation of best. By Lemma 4, the correctness of variant can be ensured by showing that after calling $`\text{init}(\mathrm{},r)`$, $`\mathrm{\Psi }[i]=\varphi (i,r)`$ holds for each index $`i[\mathrm{},r]`$. By Step 1 of init, we have $`\mathrm{\Psi }[r]=r=\varphi (r,r)`$. Now suppose that $`\mathrm{\Psi }[i]=\varphi (i,r)`$ holds for each index $`i[x+1,r]`$ right before init is about to execute the iteration for index $`x[\mathrm{},r]`$. It suffices to show $`\mathrm{\Psi }[x]=\varphi (x,r)`$ after the iteration. Let $`Z_x=\{x,\mathrm{\Psi }[x+1],\mathrm{\Psi }[\mathrm{\Psi }[x+1]+1],\mathrm{\Psi }[\mathrm{\Psi }[\mathrm{\Psi }[x+1]+1]+1],\mathrm{},r\}`$. Let $`|Z_x|`$ denote the cardinality of $`Z_x`$. We first show $`\varphi (x,r)Z_x`$ as follows.

> Assume for contradiction that $`\varphi (x,r)Z_x`$, i.e., there is an index $`zZ_x`$ with $`z<\varphi (x,r)<\mathrm{\Psi }[z+1]=\varphi (z+1,r)`$. By definition of $`\varphi `$ and Equation (1), we have $`d(z+1,\varphi (x,r))>d(z+1,\varphi (z+1,r))>d(\varphi (x,r)+1,\varphi (z+1,r))`$ and $`d(\varphi (x,r)+1,\varphi (z+1,r))d(x,\varphi (z+1,r))d(x,\varphi (x,r))`$. By $`d(z+1,\varphi (x,r))>d(x,\varphi (x,r))`$ and Equation (1), we have $`d(x,\varphi (x,r))>d(x,z)`$, contradicting the definition of $`\varphi (x,r)`$.

For any index $`zZ_x`$ with $`z<\varphi (x,r)`$, we know $`z<r`$ and $`\varphi (z+1,r)=\mathrm{\Psi }[z+1]\varphi (x,r)`$. By $`\varphi (z+1,r)\varphi (x,r)r`$ and definition of $`\varphi (z+1,r)`$, we have $`d(z+1,\varphi (x,r))d(z+1,\varphi (z+1,r))`$. By definition of $`\varphi (x,r)`$ and Equation (1), we have $`d(x,z)d(x,\varphi (x,r))d(z+1,\varphi (x,r))`$. By $`d(x,z)d(z+1,\varphi (z+1,r))`$ and Equation (1), we have $`d(x,z)d(x,\varphi (z+1,r))`$. Therefore, if $`z<\varphi (x,r)`$, then Step 5 of init will be executed to increase the value of $`z`$. Observe that $`\varphi (x,r)=z<r`$ and $`\mathrm{\Psi }[z+1]>z`$ imply $`d(x,z)<d(x,\mathrm{\Phi }[z+1])`$. It follows that as soon as $`z=\varphi (x,r)`$ holds, whether $`\varphi (x,r)=r`$ or not, the value of $`\mathrm{\Psi }[x]`$ will immediately be set to $`z`$ at Step 6 of init.

One can see that the running time is indeed $`O(r\mathrm{}+y_1y_0+1)`$ by verifying that throughout the execution of the implementation, (a) the while-loop of vbest runs for $`O(r\mathrm{}+y_1y_0+1)`$ iterations, and (b) the while-loop of init runs for $`O(r\mathrm{}+1)=O(r\mathrm{}+1)`$ iterations. To see statement (a), just observe that the value of index $`x`$ (i) never decreases, (ii) stays in $`[\mathrm{},r]`$, and (iii) increases by at least one each time Step 3 of vbest is executed. As for statement (b), consider the iteration with index $`s`$ of the for-loop of init. Note that if Step 6 of init executes $`t_s`$ times in this iteration, then $`|Z_s|=|Z_{s+1}|t_s+1`$. Since $`|Z_s|1`$ holds for each $`sX`$, we have $`_{sX}t_s=O(r\mathrm{}+1)`$, and thus statement (b) holds.

### 4.2 Our algorithm for the general case

With the help of variant, we have a linear-time algorithm for solving the original maximum-density segment problem as shown in Figure 9. Algorithm general is obtained by inserting four lines of codes (i.e., Steps 4–7 of general) between Steps 3 and 4 of lmain in order to handle the case $`i_{j1}<\mathrm{}_j`$. Specifically, when $`i_{j1}<\mathrm{}_j`$, we cannot afford to appropriately update the data structure $`\mathrm{\Phi }`$. Therefore, instead of moving $`i`$ to $`\mathrm{}_j`$, Steps 4 and 5 move $`i`$ to $`\mathrm{\Phi }[p]`$, where $`p`$ is the smallest index with $`\mathrm{}_j\mathrm{\Phi }[p]`$. Of course, these two steps may cause our algorithm to overlook the possibility of $`i_j[i_{j1},\mathrm{\Phi }[p]1]`$, as illustrated in Figure 10. This is when the variant version comes in: As shown in the next theorem, we can remedy the problem by calling $`\text{variant}(\mathrm{\Phi }[p],j)`$.

###### Theorem 2

The linear-time algorithm general solves the maximum-density segment problem in an online manner.

Proof.  We prove the correctness of general by showing that $`i_j^{}^{}i_j^{}`$ implies $`i_j^{}^{}=x_j^{}`$. By Lemma 2(1), after the subroutine call $`\text{update}(j)`$ at Step 3 of general, Condition $`C_j`$ holds. Clearly, Steps 4 and 5 of general, which may increase the value of $`p`$, do not affect the validity of Condition $`C_j`$. Clearly, Steps 6 and 7 do not modify $`p`$, $`q`$, and $`\mathrm{\Phi }`$. Let $`\mathrm{}_j^{}`$ be the value of $`\mathrm{\Phi }[p]`$ right before executing Step 8 of general. By Lemma 2(2), the index $`i_j`$ returned by $`\text{lbest}(j)`$ is the largest index in $`[\mathrm{}_j^{},r_j]`$ that maximizes $`d(i_j,j)`$. Clearly, $`i_j^{}=i_j^{}^{}`$ implies the correctness of general. If $`i_j^{}i_j^{}^{}`$, then there must be an index $`j[j_0,j^{}]`$ such that $`i_{j1}i_j^{}^{}<i_j`$. It can be proved as follows that $`i_j^{}^{}<\mathrm{}_j^{}`$.

> Assume $`\mathrm{}_j^{}i_j^{}^{}`$ for contradiction. It follows from Lemma 2(2) and Equation (1) that $`d(i_j,j)d(i_j^{}^{},j)d(i_j^{}^{},i_j1)`$. By definition of $`j^{}`$, we have $`d(i_j^{}^{},j^{})>d(i_j,j)`$, which by Equation (1) implies $`d(i_j^{}^{},i_j1)>d(i_j^{}^{},j^{})`$. Therefore, $`d(i_j,j)>d(i_j^{}^{},j^{})`$, contradicting the definition of $`j^{}`$.

Since $`i_{j1}i_j^{}^{}<\mathrm{}_j^{}`$, we know $`w(\mathrm{}_j^{}1,j^{})w(i_j^{}^{},j^{})w_{\mathrm{max}}`$. It follows from Lemma 5 that there is an index pair $`(x,y)`$ with $`w_{\mathrm{min}}w(x,y)w_{\mathrm{max}}`$ and $`d(x,y)=d(i_j^{}^{},j^{})`$.

As for the running time, observe that $`qp1`$ holds throughout the execution of general. Note that each iteration of the while-loops of general, lbest and update decreases the value of $`qp`$ by one. Clearly, Step 4 of update is the only place that increases the value of $`qp`$. Moreover, it increases the value of $`qp`$ by one for $`O(n)`$ times. Therefore, to show that the overall running time of general is $`O(n)`$, it remains to ensure that all those subroutine calls to variant at Step 7 of general take overall $`O(n)`$ time. Suppose that $`j`$ and $`k`$ are two arbitrary indices with $`k<j`$ such that general makes subroutine calls to $`\text{variant}(\mathrm{}_k^{},k)`$ and $`\text{variant}(\mathrm{}_j^{},j)`$. Let $`r_k^{}`$ be the largest index in $`[1,n]`$ with $`w(\mathrm{}_k^{},r_k^{})w_{\mathrm{max}}`$. By Lemma 5, it suffices to show that $`\mathrm{}_k^{}<\mathrm{}_j`$ and $`r_k^{}<j`$ as follows. (See Figure 11.) By definition of general, we know that $`i_{j1}<\mathrm{}_j`$, which is ensured by the situation illustrated in Figure 10. By $`k<j`$, we have $`\mathrm{}_k^{}i_{j1}`$, implying $`\mathrm{}_k^{}<\mathrm{}_j`$. Moreover, by definitions of $`\mathrm{}_j`$ and $`r_k^{}`$, one can easily verify that $`\mathrm{}_k^{}<\mathrm{}_j`$ implies $`r_k^{}<j`$.

It is clear that our algorithm shown in Figure 9 is already capable of processing the input sequence in an online manner, since the only preprocessing required is to obtain $`\mathrm{}_j`$, $`r_j`$, and the prefix sums of $`a_1,a_2,\mathrm{},a_j`$ and $`w_1,w_2,\mathrm{},w_j`$ (for the purpose of evaluating the density of any segment in $`O(1)`$ time), which can easily be computed on the fly.

## 5 Exploiting sparsity for the uniform case

In this section, we assume that $`S`$ is represented by $`m`$ pairs $`(a_1^{},n_1),(a_2^{},n_2),\mathrm{},(a_m^{},n_m)`$ with $`0=n_0<n_1<n_2<\mathrm{}<n_m=n`$ to signify that $`w_1=w_2=\mathrm{}=w_n=1`$ and $`a_i=a_j^{}`$ holds for all indices $`i`$ and $`j`$ with $`n_{j1}<in_j`$ and $`1jm`$. Our algorithm for solving the maximum-density problem for the $`O(m)`$-space representable sequence $`S`$ is shown in Figure 12.

###### Theorem 3

Algorithm sparse solves the maximum-density problem for the above $`O(m)`$-space representable sequence in $`O(m)`$ time.

Proof.  By Theorem 2, sparse runs in $`O(m)`$ time. Let $`S(i^{},j^{})`$ be a feasible segment with maximum density. We first show that without loss of generality $`i^{}1\{n_0,n_1,\mathrm{},n_{m1}\}`$ or $`j^{}\{n_1,n_2,\mathrm{},n_m\}`$ holds. More specifically, we show that if $`i^{}1\{n_0,n_1,\mathrm{},n_{m1}\}`$ and $`j^{}\{n_1,n_2,\mathrm{},n_m\}`$, then $`S(i^{}+1,j^{}+1)`$ is also a feasible segment with maximum density: By $`i^{}1\{n_0,n_1,\mathrm{},n_{m1}\}`$, we know $`a_{i^{}1}=a_i^{}`$. By $`j^{}\{n_1,n_2,\mathrm{},n_m\}`$, we know $`a_j^{}=a_{j^{}+1}`$. By the optimality of $`S(i^{},j^{})`$, we have $`a_i^{}a_{j^{}+1}`$ and $`a_{i^{}1}a_j^{}`$, implying $`a_{i^{}1}=a_i^{}=a_j^{}=a_{j^{}+1}`$. Therefore, $`S(i^{}+1,j^{}+1)`$ is also a maximum-density segment.

* Case 1: $`i^{}1\{n_0,n_1,\mathrm{},n_{m1}\}`$ and $`j^{}\{n_1,n_2,\mathrm{},n_m\}`$. Clearly, Steps 1–4 of sparse take care of this case.
* Case 2: $`i^{}1\{n_0,n_1,\mathrm{},n_{m1}\}`$ and $`j^{}\{n_1,n_2,\mathrm{},n_m\}`$. By Equation (1), we know that $`a_{i^{}1}=a_i^{}d(i^{},j^{})`$ implies $`d(i^{}1,j^{})>d(i^{},j^{})`$ or $`d(i^{}+1,j^{})>d(i^{},j^{})`$. If $`(i^{},j^{})`$ is not discovered by Steps 6 and 7 of sparse, then $`\mathrm{}_j^{}<i^{}<r_j^{}`$. Since $`i^{}1\{n_0,n_1,\mathrm{},n_{m1}\}`$ implies $`a_{i^{}1}=a_i^{}`$, we know that $`\mathrm{}_j^{}<i^{}<r_j^{}`$ implies $`d(i^{}1,j^{})=d(i^{},j^{})=d(i^{}+1,j^{})`$. Thus, $`S(i^{}1,j^{})`$ is also a feasible segment with maximum density. Clearly, we can continue the same argument until having a maximum-density segment $`S(i,j^{})`$ such that either $`i1\{n_0,n_1,\mathrm{},n_{m1}\}`$, which is handled in Case 1, or $`i=\mathrm{}_j^{}`$, which is handled by Steps 6 and 7 of sparse.
* Case 3: $`i^{}1\{n_0,n_1,\mathrm{},n_{m1}\}`$ and $`j^{}\{n_1,n_2,\mathrm{},n_m\}`$. By Equation (1), we know that $`a_j^{}=a_{j^{}+1}d(i^{},j^{})`$ implies $`d(i^{},j^{}1)>d(i^{},j^{})`$ or $`d(i^{},j^{}+1)>d(i^{},j^{})`$. If $`(i^{},j^{})`$ is not discovered by Steps 8 and 9 of sparse, then $`\mathrm{}_j^{}<i^{}<r_j^{}`$. Since $`j^{}\{n_1,n_2,\mathrm{},n_m\}`$ implies $`a_j^{}=a_{j^{}+1}`$, we know that $`\mathrm{}_j^{}<i^{}<r_j^{}`$ implies $`d(i^{},j^{}1)=d(i^{},j^{})=d(i^{},j^{}+1)`$. Thus, $`S(i^{},j^{}+1)`$ is also a feasible segment with maximum density. Clearly, we can continue the same argument until having a maximum-density segment $`S(i^{},j)`$ such that either $`j\{n_1,n_2,\mathrm{},n_m\}`$, which is handled in Case 1, or $`i^{}=\mathrm{}_j`$, which is handled by Steps 8 and 9 of sparse.

The theorem is proved.

## Acknowledgments

We thank Yi-Hsuan Hsin and Hsu-Cheng Tsai for discussions in the preliminary stage of this research. We thank Tien-Ching Lin for useful comments.