text:
# 1 Introduction

## 1 Introduction

Quark models based on Quantum Chromodynamics (QCD)  predict the existence of charm mesons whose radial wave functions are not in their ground state. A spin doublet containing a pseudoscalar $`2^1\mathrm{S}_0`$ and a vector $`2^3\mathrm{S}_1`$ state is expected. These states are referred to as the $`\mathrm{D}^{}`$ and $`\mathrm{D}^{}`$, respectively. Their masses are predicted to be $`m_\mathrm{D}^{}=2.579\mathrm{GeV}/c^2`$ and $`m_\mathrm{D}^{}=2.629\mathrm{GeV}/c^2`$  (see Table 1). The uncertainty on these masses is estimated to be of the order of $`20\mathrm{MeV}/c^2`$ from the difference between the values obtained in computations  and observations  of the masses of orbitally excited states.

The kinematically favoured decay mode of the $`\mathrm{D}^+`$ is presumed to be the direct three-body decay into a $`\mathrm{D}^+\pi ^+\pi ^{}`$ final state111 Charge conjugates will be implied throughout this paper.. This is an S-wave decay and thus generally expected to be broad, although a model exists  which estimates the partial width of this decay mode to be less than $`1\mathrm{MeV}/c^2`$. Decays via an intermediate orbitally excited $`\mathrm{D}`$ meson could also contribute to the same final state; these decay widths are estimated to be several $`\mathrm{MeV}/c^2`$ by the same model. If enough phase space is available, $`\mathrm{D}^+`$ decays to a $`\mathrm{D}^+\rho `$ state with $`\rho \pi ^+\pi ^{}`$ might also be allowed. The decays via orbitally excited states include S-wave ($`\mathrm{D}^+\mathrm{D}_1^0\pi ^+,\mathrm{D}_1^0\mathrm{D}^+\pi ^{}`$), and D-wave transitions (e.g. $`\mathrm{D}^+\mathrm{D}_2^0\pi ^+`$, $`\mathrm{D}_2^0\mathrm{D}^+\pi ^{}`$). The decays involving a $`\rho `$ are P-wave transitions. The higher partial waves are expected to be suppressed due to lack of phase space.

The only experimental evidence for the existence of radially excited $`\mathrm{D}`$ mesons comes from the DELPHI collaboration which has published an observation of a narrow resonance decaying to $`\mathrm{D}^+\pi ^+\pi ^{}`$ . The observed mass of $`2.637\pm 0.002(\mathrm{stat}.)\pm 0.006(\mathrm{syst}.)\mathrm{GeV}/c^2`$ is close to the theoretical prediction. However, the interpretation of this $`\mathrm{D}`$ resonance as $`\mathrm{D}^{}`$ is controversial, since the narrow width is incompatible with most theoretical models . The DELPHI measurement of the width of the state is limited by their detector resolution and quoted to be smaller than $`15\mathrm{MeV}/c^2`$ at $`95\%`$ C.L.

This paper presents a search for the state reported by DELPHI in hadronic $`\mathrm{Z}`$ decays recorded with the OPAL detector. The search covers both the region of the resonance measured by DELPHI as well as any other narrow resonance in the vicinity of the predicted $`\mathrm{D}^\pm `$ mass. Therefore the particle being searched for will be referred to as $`\mathrm{D}^\pm (2629)`$ throughout this paper.

After a description of the data and Monte Carlo samples, the selection criteria for the $`\mathrm{D}^+`$ mesons are presented. Since the production mechanism of $`\mathrm{D}^+`$ mesons is different in $`\mathrm{Z}\mathrm{b}\overline{\mathrm{b}}`$ and $`\mathrm{Z}\mathrm{c}\overline{\mathrm{c}}`$ events, two different selections are used to reconstruct $`\mathrm{D}^+`$ mesons. One is optimized to select $`\mathrm{D}^+`$ candidates in primary b-events using vertex information, while the second selection uses harder cuts on the momentum of the $`\mathrm{D}^+`$ candidate, resulting in a sample enhanced in $`\mathrm{c}\overline{\mathrm{c}}`$ events. In Section 5, the selection results for data and Monte Carlo events are presented. Systematic checks are discussed subsequently, and the calculation of limits on the production rate is described in Section 7. In the concluding Section our results are compared with those published by DELPHI .

## 2 The OPAL Detector and Event Simulation

A detailed description of the OPAL detector can be found elsewhere . The most important components of the detector for this analysis are the silicon microvertex detector, the tracking chambers and the electromagnetic calorimeter. The microvertex detector consists of two layers of silicon strip detectors which provide high spatial resolution near the interaction region. The central jet chamber is optimized for good spatial resolution in the plane perpendicular to the beam axis222The OPAL coordinate system is defined as a right-handed Cartesian coordinate system, with the $`x`$-axis pointing in the plane of the LEP collider towards the centre of the ring and the $`z`$-axis along the electron beam direction.. The resolution along the beam direction is improved by the $`z`$ information delivered by the silicon microvertex detector, by a vertex drift chamber between the silicon detector and the main tracking chambers, and by $`z`$-chambers surrounding the main tracking chamber. The central detector provides precise determination of momenta of charged particles by measuring the curvature of their trajectories in a magnetic field of $`0.435`$T. The solenoid is mounted outside the tracking chambers but inside the electromagnetic calorimeter, which consists of approximately $`\mathrm{12\hspace{0.17em}000}`$ lead glass blocks providing an azimuthal coverage up to polar angles of $`|\mathrm{cos}\theta |<0.98`$. To improve the shower energy and spatial resolution, a preshower detector (presampler) is mounted between the solenoid and the electromagnetic calorimeter.

For background studies, about 8 million hadronic decays of the $`\mathrm{Z}`$ have been simulated using the JETSET 7.4 Monte Carlo  with parameters tuned to the OPAL data . In addition, samples with simulated $`\mathrm{D}^{}`$ decays have been generated since JETSET does not include $`\mathrm{D}^{}`$ production by default. For the production of the $`\mathrm{D}^{}`$ Monte Carlo samples with JETSET, radially excited $`\mathrm{D}`$ meson states have been implemented into JETSET with the mass set to $`2.629\mathrm{GeV}/c^2`$, according to the most recent calculation , and the width set to zero. The possible effects of a non-zero width are treated later as systematic uncertainty. DELPHI only measured the ratio of the $`\mathrm{D}^+`$ and $`\mathrm{D}_J^{()0}`$ production rates333The symbol $`\mathrm{D}_J^{()}`$ represents the two narrow orbital resonances $`\mathrm{D}_1`$ and $`\mathrm{D}_2^{}`$. , and therefore this measurement has been combined with the OPAL measurement of $`\mathrm{D}_J^{()0}`$ production  to calculate the expected absolute $`\mathrm{D}^+`$ production rate. $`\mathrm{D}^{}`$ production is simulated in fragmentation and in $`\mathrm{B}`$ meson decays. In the latter case, $`\mathrm{D}^{}`$ mesons were produced in the same b decay channels as $`\mathrm{D}_2^{}`$, in proportion chosen to reproduce the DELPHI measurement .

Four samples of $`\mathrm{D}^{}`$ Monte Carlo events have been generated: production in $`\mathrm{Z}\mathrm{c}\overline{\mathrm{c}}`$ and $`\mathrm{Z}\mathrm{b}\overline{\mathrm{b}}`$ events and the decay channels $`\mathrm{D}^+\mathrm{D}^+\pi ^+\pi ^{}`$ and $`\mathrm{D}^+\mathrm{D}_1^0\pi ^+`$. The signal Monte Carlo sample contains 600,000 events in total, with at least one charged $`\mathrm{D}^{}`$ meson in each event. In all Monte Carlo samples, heavy quark fragmentation has been implemented using the the model of Peterson et al.  with fragmentation parameters determined from LEP data . The samples have been passed through a detailed simulation of the OPAL detector  and then analyzed in the same manner as the data.

## 3 Event and Track Selection

Hadronic $`\mathrm{Z}`$ decays are selected based on the number of reconstructed tracks and the energy deposited in the electromagnetic calorimeter, as described in Ref. . The analysis uses an initial sample of $`3.73`$ million hadronic decays of the $`\mathrm{Z}`$ collected with the OPAL detector between 1991 and 1995.

Tracks are used in the reconstruction if they pass loose quality cuts requiring $`|d_0|<0.5\mathrm{cm}`$, $`|z_0|<20\mathrm{cm}`$, $`p>0.5\mathrm{GeV}/c`$, and $`p_{xy}>0.150\mathrm{GeV}/c`$. Here $`|d_0|`$ is the distance of closest approach of the track to the primary vertex, measured in the plane perpendicular to the beam, $`z_0`$ the distance along the beam at this point, $`p`$ the momentum, and $`p_{xy}`$ the momentum in the plane perpendicular to the beam. Only tracks with more than 40 hits out of a maximum of 159 in the main tracking chamber are used. The primary vertex in a collision is reconstructed from the tracks in the event and constrained by the known average position and spread of the $`\mathrm{e}^+\mathrm{e}^{}`$ interaction point. To improve the mass resolution, a track is required to have a precise $`z`$ measurement at the exit point of the tracking chamber, either from an associated hit in the $`z`$-chamber surrounding the central drift chamber, or from the presampler. In cases where the particle exited the tracking chamber in the endcap region, i.e. $`|\mathrm{cos}\theta |>0.73`$, the exit point is determined precisely from the last sense wire used for the track measurement.

## 4 Reconstruction of $`𝐃^\mathbf{}\mathbf{+}`$ Candidates

The reconstruction of $`\mathrm{D}^+\mathrm{D}^+\pi ^+\pi ^{}`$ decays involves $`\mathrm{D}^+`$ reconstruction and, subsequently, the combination of accepted $`\mathrm{D}^+`$ candidates with additional pion candidates. The $`\mathrm{D}^+`$ reconstruction follows closely a recent OPAL publication , with the exception of the cut on the kaon particle identification probability which has been tightened for this analysis, in order to reduce combinatorial background.

The following decay sequence is reconstructed exclusively:

| $`\mathrm{D}^+`$ | $`\mathrm{D}^+\pi ^+\pi ^{}`$ |
| --- | --- |
|  | $`\mathrm{D}^0\pi ^+`$ |
|  |  | $`\text{}\text{ }\mathrm{K}^{}\pi ^+`$ |

All tracks that fulfil the criteria described in Section 3 are considered for the construction of $`\mathrm{D}^+`$ candidates. Only combinations of tracks that have the correct charge assignments, and which pass intermediate requirements imposed by the reconstruction of the $`\mathrm{D}^+`$, are taken into account. The two pions produced in the initial $`\mathrm{D}^+`$ decay will be referred to as “$`\mathrm{D}^+`$ pions”, whereas the pion coming from the $`\mathrm{D}^+`$ decay will be referred to as “slow pion”.

Two tracks of opposite charge are accepted as a $`\mathrm{D}^0`$ candidate if their invariant mass lies within the range $`1.791.94\mathrm{GeV}/c^2`$, assigning the pion mass to one particle and the kaon mass to the other . $`\mathrm{D}^0`$ candidates are combined with tracks of charge opposite to that of the kaon candidate to form $`\mathrm{D}^+`$ candidates. The scaled energy $`x_\mathrm{E}`$ of the $`\mathrm{D}^+`$ candidate, i.e. the ratio of the energy sum of all participating tracks over the beam energy, is required to be larger than $`0.2`$ in order to reject combinatorial background from low-energy fragmentation tracks. The difference of the invariant masses of $`\mathrm{D}^+`$ and $`\mathrm{D}^0`$ candidates, $`\mathrm{\Delta }m=m_\mathrm{D}^{}m_{\mathrm{D}^0}`$, must lie within the interval from $`142`$ to $`149\mathrm{MeV}/c^2`$.

Background in the sample is further reduced by cutting on the helicity angle $`\theta ^{}`$ measured between the direction of the $`\mathrm{D}^0`$ candidate in the laboratory frame and the direction of the kaon in the rest frame of the $`\mathrm{D}^0`$ candidate. The kaon candidate from the $`\mathrm{D}^0`$ decay is expected to be isotropically distributed in $`\mathrm{cos}\theta ^{}`$, while the background peaks at $`\mathrm{cos}\theta ^{}=1`$ and, particularly at small $`x_\mathrm{E}`$, at $`\mathrm{cos}\theta ^{}=+1`$. This effect is taken into account by requiring $`\mathrm{cos}\theta ^{}>0.9`$ for $`x_\mathrm{E}>0.5`$ and $`|\mathrm{cos}\theta ^{}|<0.8`$ for $`x_\mathrm{E}<0.5`$.

At low $`x_\mathrm{E}`$, where the background is most pronounced, the particle identification power of the OPAL detector is used to enrich the sample in true kaons from $`\mathrm{D}^0`$ decays. A probability $`W_\mathrm{K}`$ is computed from the ionization energy loss measurement of a track in the drift chamber, the track momentum, and the theoretical expectation for a kaon. At least $`20`$ $`\mathrm{d}E/\mathrm{d}x`$ out of a possible 159 measurement points and $`W_\mathrm{K}>10\%`$ are required for the kaon candidate in a $`\mathrm{D}^+`$ candidate with $`x_\mathrm{E}<0.5`$.

A fraction ($`1.5\%`$) of all $`\mathrm{D}^+`$ candidates share the same slow pion candidate with another $`\mathrm{D}^+`$ candidate in the same event. In this case only the $`\mathrm{D}^+`$ candidate with a $`\mathrm{D}^0`$ invariant mass closest to the mean value obtained from a fit to the $`\mathrm{D}^0`$ mass distribution is kept for the further analysis. The $`\mathrm{D}^+`$ candidates surviving the cuts described above are combined with all remaining pairs of oppositely charged tracks. For these combinations, a mass difference $`\mathrm{\Delta }m^{^{}}=m_\mathrm{D}^{}m_\mathrm{D}^{}`$ is calculated.

In order to suppress background from $`\mathrm{uds}`$ events, charm and bottom tags are used. The mean fractional energy of $`\mathrm{D}^+`$ mesons in $`\mathrm{Z}\mathrm{c}\overline{\mathrm{c}}`$ events is expected to be large compared to $`\mathrm{D}^+`$ from $`\mathrm{B}`$ decays, and especially compared to fake $`\mathrm{D}^+`$ candidates in events of all flavours consisting of low-energy fragmentation tracks. Since most of the energy of the $`\mathrm{D}^+`$ is transferred to the $`\mathrm{D}^+`$, a charm enriched sample is selected by imposing a cut on the energy fraction of the $`\mathrm{D}^+`$ of $`x_\mathrm{E}>0.4`$. Additionally, in the Monte Carlo simulation, the $`\mathrm{D}^+`$ pions have a higher momentum if the $`\mathrm{D}^{}`$ is produced in $`\mathrm{c}\overline{\mathrm{c}}`$ events compared to the production via the decay of b hadrons. This information has been exploited by selecting only candidates for which the magnitude of the vector sum of the two $`\mathrm{D}^{}`$ pion momenta is greater than $`3.6\mathrm{GeV}/c`$ (Figure 1). The mass resolution in the charm enriched sample is improved by constraining all $`\mathrm{D}^+`$ candidate tracks except those from the $`\mathrm{D}^0`$ decay to the primary event vertex.

A bottom-enriched sample is selected by requiring an apparent $`\mathrm{D}^0`$ decay length of at least $`0.3\mathrm{mm}`$, defined as the distance between the reconstructed $`\mathrm{D}^0`$ vertex and the primary event vertex, measured in the plane perpendicular to the beam. $`\mathrm{D}^0`$ candidates from light quark ($`\mathrm{uds}`$) events and $`\mathrm{c}\overline{\mathrm{c}}`$ events are expected to be made up from tracks in the vicinity of the primary vertex. In contrast, $`\mathrm{D}^0`$ candidates in $`\mathrm{b}\overline{\mathrm{b}}`$ events tend to have a larger decay length with respect to the primary vertex, due to the $`\mathrm{B}`$ meson lifetime.

The separation significance of two vertices is defined as the distance between them in the plane perpendicular to the beam, divided by the uncertainty on this quantity. The separation significance of the $`\mathrm{D}^0`$ vertex and the reconstructed vertex formed by the $`\mathrm{D}^{}`$ pion tracks is required to be between $`2.0`$ and $`+4.0`$. The distribution of this variable is not centred at zero, because the $`\mathrm{D}^0`$ has a lifetime large enough to be observed. The separation significance between the $`\mathrm{D}^+`$ pion vertex and the $`\mathrm{D}^0`$ vertex is shown in Figure 2. A positive sign indicates that the $`\mathrm{D}^0`$ vertex is farther from the primary interaction point than the $`\mathrm{D}^+`$ pion vertex. Positive values are expected for signal, because the $`\mathrm{D}^0`$ occurs later in the decay chain.

The Monte Carlo flavour composition of the $`\mathrm{D}^+`$ candidates passing all selection criteria is shown in Table 2. For $`\mathrm{D}^+`$ mesons from primary charm and bottom quarks, the reconstruction efficiencies are estimated from Monte Carlo analysis to be $`14.1\%`$ and $`7.1\%`$, respectively. The combined efficiency for $`\mathrm{D}^+`$ from both sources is $`11.4\%`$, assuming equal rates for production in charm and bottom events. This assumption is motivated by the range of production rate ratios observed for $`\mathrm{D}^\pm `$  and orbitally excited $`\mathrm{D}_J^{()0}`$ mesons . The analysis has also been performed with several other assumptions, and the dependence of the results on these different scenarios is included as a systematic error.

## 5 Selection Results

In order to maximize the expected sensitivity of the analysis, the charm and bottom enriched samples with 1765 and 3051 candidates, respectively, in the $`\mathrm{\Delta }m^{^{}}=\mathrm{m}_\mathrm{D}^{}\mathrm{m}_\mathrm{D}^{}`$ region between $`2.3\mathrm{GeV}/c^2`$ and $`3.0\mathrm{GeV}/c^2`$ are merged into a combined sample. The overlap of 324 candidates between charm and bottom sample is taken into account; candidates that have been tagged as charm and bottom are used only once. This sample contains a total of $`4492`$ $`\mathrm{D}^+`$ candidates in 2192 events. The results for the combined sample and the $`\mathrm{b}`$ and $`\mathrm{c}`$ enriched samples are discussed below.

The $`\mathrm{\Delta }m^{^{}}`$ distribution of the combined charm and bottom enriched sample is shown in Figure 3a. No narrow resonance is observed anywhere in the $`\mathrm{\Delta }m^{^{}}`$ region between $`0.3`$ and $`1.0\mathrm{GeV}/c^2`$, although the Monte Carlo simulation with a $`\mathrm{D}^{}`$ production rate fixed at the value published by DELPHI  shows a clear signal (see Figure 3b). This is also separately true for the $`\mathrm{c}`$ and $`\mathrm{b}`$ enriched samples, shown in Figures 4 and 5, respectively. Shape and normalization of the background differ in data and simulation, especially in the b enriched sample. This is due to $`\mathrm{D}^+`$ candidates in the Monte Carlo where one track is incorrectly assigned to the $`\mathrm{D}^+`$ candidate. These candidates lead to a broad enhancement in the mass distribution. The mean scaled energy $`x_\mathrm{E}`$ of these candidates is small. Therefore, they contribute more to the b enriched sample than to the c enriched sample. The analysis has also been performed on a Monte Carlo sample without $`\mathrm{D}^{}(2629)`$ production. It has been found that in this case the background shape and normalization agree very well with the data. This absence of a significant enhancement over the expected background in data provides additional confidence that the $`\mathrm{D}^+(2629)`$ production rate must be small.

A limit on the $`\mathrm{D}^+(2629)`$ production rate is calculated by defining a mass window in the $`\mathrm{\Delta }m^{^{}}`$ range of $`0.58\mathrm{GeV}/c^2<\mathrm{\Delta }m^{^{}}<0.66\mathrm{GeV}/c^2`$, corresponding to a $`\mathrm{D}^{}`$ mass window of $`2.592.67\mathrm{GeV}/c^2`$. This includes the $`\pm 2\sigma `$ range of both the theoretical prediction of the $`\mathrm{D}^{}`$  and the excess observed by DELPHI . The background distribution has been fitted using a parametrisation of the form

$$\mathrm{f}(\mathrm{\Delta }m^{^{}})=\alpha (\mathrm{\Delta }m^{^{}}m_0)^\beta \mathrm{e}^{\gamma (\mathrm{\Delta }m^{^{}}m_0)},$$
(1)
where $`m_0=0.28\mathrm{GeV}/c^2`$ is the kinematic limit for $`\mathrm{D}^+\pi ^+\pi ^{}`$ combinations, and $`\alpha `$, $`\beta `$ and $`\gamma `$ are the fit parameters. The signal region has been excluded from the fit. The number of $`\mathrm{D}^+`$ candidates in the mass window is determined to be $`14\pm 28`$ by subtracting the integrated interpolated background function from the observed number of candidates in the signal interval. The quoted statistical error is obtained by combining the Gaussian variance of the number of entries in the mass window ($`\pm 25`$) and the uncertainty on the background integral obtained by propagating the uncertainties on the fit parameters ($`\pm 14`$), taking into account the correlations.

## 6 Systematic Checks

The $`\mathrm{D}^+`$ analysis has been checked by applying a similar selection to $`\mathrm{D}^+\pi ^{}`$ final states, looking for the narrow orbital resonances $`\mathrm{D}_1^0`$ and $`\mathrm{D}_2^0`$. The $`\mathrm{D}^+`$ selection criteria are as described earlier. Accepted $`\mathrm{D}^+`$ candidates are combined with pion candidates passing selection criteria similar to those applied to the $`\mathrm{D}^+`$ pions, except for the cuts on the pion-pion momentum sum and the pion-pion vertex separation, which are inappropriate here. Instead, the pion momentum is required to be larger than 2.0 GeV/c, as was done in an earlier OPAL publication on orbitally excited D mesons . The efficiency of the $`\mathrm{D}_J^{()0}\mathrm{D}^+\pi ^{}`$ reconstruction is about $`7.3\%`$. The results achieved on data and simulated events can be compared in Figure 6. The method used for determining the number of signal events is the same as was used for the $`\mathrm{D}^+`$. The lower mass window boundary has been set to $`2.382\mathrm{GeV}/c^2`$, two $`\mathrm{D}_1^0`$ widths below the world average $`\mathrm{D}_1^0`$ mass. The upper boundary has been chosen to be $`2.507\mathrm{GeV}/c^2`$, two $`\mathrm{D}_2^0`$ widths above the world average $`\mathrm{D}_2^0`$ mass. The production rates of the two narrow $`\mathrm{D}_J^{()0}`$ resonances have been adjusted in the simulation to match the previous OPAL measurement . The amount of signal found in Monte Carlo is $`281\pm 16`$, whereas in data the excess is $`189\pm 41`$ in a sample of 4711 selected $`\mathrm{D}_J^{()0}`$ candidates. The analysis presented here and the previous OPAL publication on orbitally excited D mesons  that was used to adjust the $`\mathrm{D}_J^{()0}`$ production rates in Monte Carlo use a similar dataset. Both results are therefore expected to be correlated. Nevertheless, it has been found that the overlap of the selected $`\mathrm{D}_J^{()0}`$ candidate samples of old and new analysis is very small, and the results can thus be considered almost statistically independent. This leads to the conclusion that the measured rates are statistically compatible.

Having confirmed in the case of $`\mathrm{D}^+\pi ^{}`$ final states that the reconstruction procedure performs as expected, the results of the search in the $`\mathrm{D}^+\pi ^+\pi ^{}`$ final state are used to place limits on the production rate of the $`\mathrm{D}^+(2629)`$. The efficiency of $`\mathrm{D}^+`$ reconstruction is taken from Monte Carlo simulation. The efficiency calculation accounts for several sources of systematic uncertainties. They are evaluated as follows:

* The efficiency has been calculated from a simulation with zero $`\mathrm{D}^+`$ width. To quantify the effect of a non-zero width, the analysis has been repeated with a $`\mathrm{D}^+`$ width of $`15\mathrm{MeV}/c^2`$, the $`95\%`$ C.L. upper limit obtained by DELPHI . This results in a relative decrease of the efficiency of $`16.5\%`$, taken as systematic uncertainty.
* The simulated detector resolutions of momentum, impact parameters and track angles have been varied by $`\pm 10\%`$, as in previous publications , around the values that best describe the data. The largest relative deviation in the selection efficiency ($`{}_{5.7\%}{}^{}{}_{}{}^{+4.9\%}`$) is taken as systematic uncertainty.
* Equal production rates of $`\mathrm{D}^+`$ in $`\mathrm{c}`$ and $`\mathrm{b}`$ decays have been assumed. Other possible assumptions include the same ratio as observed in $`\mathrm{D}^\pm `$ production , or in $`\mathrm{D}_J^{()0}`$ production . Equal numbers of $`\mathrm{D}^{}`$ from both primary heavy flavours are simulated as well as the ratio of candidates from $`\mathrm{b}\overline{\mathrm{b}}`$ and $`\mathrm{c}\overline{\mathrm{c}}`$ events observed by DELPHI , corrected for the different reconstruction efficiencies of the respective analyses. The ratios thus obtained cover a $`{}_{23\%}{}^{}{}_{}{}^{+33\%}`$ range around the central assumption of equal production rates in $`\mathrm{b}\overline{\mathrm{b}}`$ and $`\mathrm{c}\overline{\mathrm{c}}`$ events. The largest observed variations in the efficiency in both directions, $`{}_{4.6\%}{}^{}{}_{}{}^{+3.8\%}`$, are taken as systematic uncertainty.
* A Peterson function has been used to parametrise the heavy quark fragmentation in the Monte Carlo samples. Other fragmentation models by Collins and Spiller  and Kartvelishvili  have also been tested. The fragmentation parameters have been varied in the limits implied by the measurement of the mean $`x_\mathrm{E}`$ distribution of $`\mathrm{D}^+`$ mesons at LEP . The largest resulting uncertainty of $`{}_{2.3\%}{}^{}{}_{}{}^{+1.7\%}`$ is taken as systematic uncertainty.
* The efficiency depends on the performance of the particle identification by $`\mathrm{d}E/\mathrm{d}x`$ measurements. The $`\mathrm{d}E/\mathrm{d}x`$ calibration for kaons has been checked in a previous analysis  under identical circumstances. An error of $`\pm 3.2\%`$ was found for the total rate of kaons passing the selection. Because this cut is applied only for candidates with $`x_\mathrm{E}<0.5`$, the expected contribution to the uncertainty on the efficiency is $`\pm 2.1\%`$.
* The $`\mathrm{D}^0`$ lifetime is currently measured with a precision of $`0.7\%`$, whereas the average b hadron lifetime is known to $`0.9\%`$ . The cut on the $`\mathrm{D}^0`$ apparent decay length and thus the $`\mathrm{b}`$ flavour enrichment is sensitive to the modelling of this quantity. The cut value has therefore been varied within the combined uncertainty on $`\mathrm{D}^0`$ and $`\mathrm{B}`$ lifetime. The resulting deviation of $`{}_{0.0\%}{}^{}{}_{}{}^{+0.2\%}`$ is taken as systematic uncertainty.
* The calculated production limit depends on the branching ratio $`\mathrm{Br}(\mathrm{D}^+\mathrm{D}^0\pi ^+)\times \mathrm{Br}(\mathrm{D}^0\mathrm{K}^{}\pi ^+)`$. The world average value is $`(0.677\pm 0.005)\times (0.0383\pm 0.0009)`$ . The relative uncertainty on the product branching ratio is $`\pm 2.5\%`$.
* The reconstruction efficiencies of the decay chains $`\mathrm{D}^+\mathrm{D}_1^0\pi ^+`$, $`\mathrm{D}_1^0\mathrm{D}^+\pi ^{}`$ and $`\mathrm{D}^+\mathrm{D}^+\pi ^+\pi ^{}`$ are identical within the statistical uncertainties. No systematic uncertainty is introduced.
* The reconstructed number of $`\mathrm{D}^+`$ in Monte Carlo has been compared to the actual number of $`\mathrm{D}^+`$ in the sample. The excess over the background fit is $`138\pm 30`$, with $`175`$ entries due to $`\mathrm{D}^+`$ with all tracks reconstructed. It is thus concluded that the fit is free of significant bias.
* The width of the signal region has been varied from $`90\%`$ to $`130\%`$ of the nominal value to check whether the resulting counting rate variations are consistent with statistical effects. All results are clearly within the statistical error. Thus no additional systematic uncertainty is assigned.
* The bin width of the $`\mathrm{\Delta }m^{^{}}`$ histograms in which the fit is performed has been varied from $`75\%`$ to $`125\%`$ of the value used for the analysis. No significant impact on the rate is observed.

The contributions to the systematic uncertainty are summarized in Table 3.

## 7 Calculation of $`𝐃^\mathbf{}\mathbf{\pm }\mathbf{(}\mathrm{𝟐𝟔𝟐𝟗}\mathbf{)}`$ Production Limits

The limit is calculated assuming that the candidate sample in the signal region is composed of a large background and a small signal sample. Each contribution has a Poisson probability density function although the background can be approximated by a Gaussian distribution $`𝒢(n;e_{\mathrm{bck}},\sigma )`$ since the background expectation is large. The width of the Gaussian, $`\sigma =28`$, has two contributions, one accounting for the statistical uncertainty in the signal window, the other one taking into account the fit error. $`n_0=610`$ candidates are observed in the signal window. The probability to count $`n_0`$ candidates or less is given by

$$P(n_0;e_{\mathrm{sig}})=\underset{n=0}{\overset{n_0}{}}\underset{n_{\mathrm{sig}}=0}{\overset{n}{}}𝒫(n_{\mathrm{sig}};e_{\mathrm{sig}})𝒢(nn_{\mathrm{sig}};e_{\mathrm{bck}},\sigma )$$
(2)
where $`e_{\mathrm{sig}}`$ is the unknown expectation value of the signal and $`𝒫`$ its Poisson distribution. The summation is performed over all possible combinations of $`n`$, the total number of candidates in the mass window, and $`n_{\mathrm{sig}}`$, the amount of signal within these $`n`$ candidates, where $`nn_0`$. Assuming no narrow $`\mathrm{D}^+`$ are produced, i.e. $`e_{\mathrm{sig}}=0`$, a probability of $`0.70`$ is obtained to observe 610 candidates or less. Given the prior knowledge of the maximum amount of background, the 95% C.L. limit is obtained at $`P(n_0;e_{\mathrm{sig}})=0.70\times 0.050`$. At large $`n`$ ($`10`$) the systematic uncertainties affecting the efficiency start playing a role in calculating the limit. They are considered by substituting the Poisson distribution of the signal with a Gaussian distribution at $`n>10`$ and adding in quadrature the asymmetric systematic uncertainty of the efficiency to the width of the Gaussian given by $`\sqrt{n}`$. The obtained limit on the production of narrow $`\mathrm{D}^\pm (2629)`$ in hadronic $`\mathrm{Z}`$ decays is:

$$f(\mathrm{Z}\mathrm{D}^\pm (2629))\times Br(\mathrm{D}^+\mathrm{D}^+\pi ^+\pi ^{})<3.1\times 10^3(95\%\mathrm{C}.\mathrm{L}.).$$
(3)
This corresponds to a $`95\%`$ C.L. upper limit of 66 on the number of reconstructed $`\mathrm{D}^+`$ in the signal region. The approach used here is similar to a Bayesian approach with a flat prior distribution for positive $`\mathrm{D}^+`$ production rates and zero elsewhere, but superior in the fact that negative expectation values are excluded in principle by using the proper Poisson distribution.

Limits on the $`\mathrm{D}^+(2629)`$ production rate in charm and bottom events are also calculated. In the charm and bottom enriched samples, the numbers of events in the signal region, relative to the expectations derived from the fitted background functions, are $`5\pm 18`$ and $`29\pm 23`$, respectively. In using these results to calculate limits, a further systematic uncertainty arises due to the experimental uncertainties on $`\mathrm{\Gamma }_{\mathrm{c}\overline{\mathrm{c}}}/\mathrm{\Gamma }_{\mathrm{had}}=0.1671\pm 0.0048`$ and $`\mathrm{\Gamma }_{\mathrm{b}\overline{\mathrm{b}}}/\mathrm{\Gamma }_{\mathrm{had}}=0.21644\pm 0.00075`$ . Under the conservative assumption that $`\mathrm{D}^+`$ are only produced in $`\mathrm{Z}\mathrm{c}\overline{\mathrm{c}}`$ events, i.e. that the measured excess can be fully assigned to $`\mathrm{D}^+`$ candidates in $`\mathrm{c}\overline{\mathrm{c}}`$ events, a production limit of

$$f(\mathrm{c}\mathrm{D}^+(2629))\times Br(\mathrm{D}^+\mathrm{D}^+\pi ^+\pi ^{})<0.9\times 10^2(95\%\mathrm{C}.\mathrm{L}.)$$
(4)
is obtained from the charm enriched sample, while under the opposite assumption that all $`\mathrm{D}^+`$ are only produced in the decay of $`\mathrm{b}`$-hadrons, a limit of

$$f(\mathrm{b}\mathrm{D}^+(2629))\times Br(\mathrm{D}^+\mathrm{D}^+\pi ^+\pi ^{})<2.4\times 10^2(95\%\mathrm{C}.\mathrm{L}.)$$
(5)
is computed using the bottom enriched sample. The systematic uncertainties assumed for the calculations in the separate samples are given in Table 3.

## 8 Discussion

The result of the OPAL $`\mathrm{D}^+`$ search does not agree with the published DELPHI results . Both analyses apply standard selection criteria to obtain a high-purity $`\mathrm{D}^+`$ sample. In contrast to the OPAL analysis, DELPHI reconstructs $`\mathrm{D}^0`$ candidates in two decay channels, $`\mathrm{D}^0\mathrm{K}^{}\pi ^+`$ and $`\mathrm{D}^0\mathrm{K}^{}\pi ^+\pi ^+\pi ^{}`$. The loss in efficiency associated with using only the $`\mathrm{K}^{}\pi ^+`$ channel is in part compensated by the softer kinematic cuts and a slightly larger hadronic event sample. Combinatorial background is reduced by applying a best candidate selection to $`\mathrm{D}^+`$ candidates which share tracks. These candidates can produce correlated entries in the $`\mathrm{\Delta }m^{^{}}`$ distribution if they are combined with the same $`\mathrm{D}^+`$ pions. The expected sensitivity of the analysis to the existence of a narrow resonance in the mass region including the theoretical predictions for the $`\mathrm{D}^{}`$ as well as the mass of the published DELPHI result, produced at a rate published by DELPHI, is demonstrated in Figure 3. The excess observed in the Monte Carlo sample with comparable size to the data sample has a significance of $`4.7\sigma `$ (statistical error only), or $`3.5\sigma `$ including all systematic uncertainties.

The OPAL and DELPHI selection criteria used to select charm and bottom enriched samples, and for the pions from the $`\mathrm{D}^+`$ decay, have been optimized in different ways. For example, the kinematic cuts for the pion candidates from the $`\mathrm{D}^+`$ are less restrictive, $`0.5\mathrm{GeV}/c`$ in this analysis while DELPHI requires $`1.0\mathrm{GeV}/c`$.

The sensitivity of the OPAL analysis has been checked with the $`\mathrm{D}_J^{()0}`$ reconstruction described above, where agreement between data and simulation is observed. The selection criteria that are specific to either the $`\mathrm{D}^+`$ or $`\mathrm{D}_J^{()0}`$ analysis are checked by performing the analysis without these cuts. This did not change the result of the $`\mathrm{D}^+`$ search.

Overall, the sensitivities of the two analyses are found to be similar, although the background in this analysis is higher. A comparison between the analyses can be made by calculating the $`\mathrm{D}^+`$ versus $`\mathrm{D}_J^{()0}`$ rate for which DELPHI published a number :

$`R`$ $`=`$ $`{\displaystyle \frac{N_{\mathrm{D}^+}\mathrm{B}r(\mathrm{D}^+\mathrm{D}^+\pi ^+\pi ^{})}{N_{\mathrm{D}_1^0}\mathrm{B}r(\mathrm{D}_1^0\mathrm{D}^+\pi ^{})+N_{\mathrm{D}_2^0}\mathrm{B}r(\mathrm{D}_2^0\mathrm{D}^+\pi ^{})}}`$
$`=`$ $`0.49\pm 0.18(\mathrm{stat}.)\pm 0.10(\mathrm{syst}.),`$
where $`N_{\mathrm{D}^+}`$ denotes the expected number of $`\mathrm{D}^+`$ in a sample with $`N_{\mathrm{D}_1^0}`$ and $`N_{\mathrm{D}_2^0}`$ being the corresponding quantities for the $`\mathrm{D}_1^0`$ and $`\mathrm{D}_2^0`$. Based on the numbers presented in Sections 5 and 6,

$$R=0.05\pm 0.10(\mathrm{stat}.)\pm 0.002(\mathrm{syst}.)$$
(7)
is calculated. The statistical error of the fit and the systematic uncertainties resulting from the $`\mathrm{D}^{}`$ width and relative production rates in b and c are included. In the ratio calculation, all other systematic uncertainties largely cancel and have therefore been neglected. Using a statistical approach analogous to the one described earlier, a limit of

$$R<0.22(95\%\mathrm{C}.\mathrm{L}.)$$
(8)
is computed.

In summary, the evidence of $`\mathrm{D}^+`$ production in hadronic decays of the $`\mathrm{Z}`$ published by the DELPHI collaboration  is not confirmed with OPAL data.

Acknowledgements

We particularly wish to thank the SL Division for the efficient operation of the LEP accelerator at all energies and for their continuing close cooperation with our experimental group. We thank our colleagues from CEA, DAPNIA/SPP, CE-Saclay for their efforts over the years on the time-of-flight and trigger systems which we continue to use. In addition to the support staff at our own institutions we are pleased to acknowledge the
Department of Energy, USA,
National Science Foundation, USA,
Particle Physics and Astronomy Research Council, UK,
Natural Sciences and Engineering Research Council, Canada,
Israel Science Foundation, administered by the Israel Academy of Science and Humanities,
Minerva Gesellschaft,
Benoziyo Center for High Energy Physics,
Japanese Ministry of Education, Science and Culture (the Monbusho) and a grant under the Monbusho International Science Research Program,
Japanese Society for the Promotion of Science (JSPS),
German Israeli Bi-national Science Foundation (GIF),
Bundesministerium für Bildung und Forschung, Germany,
National Research Council of Canada,
Research Corporation, USA,
Hungarian Foundation for Scientific Research, OTKA T-029328, T023793 and OTKA F-023259.


format: text

text:
# Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings

## 1 Introduction

This paper investigates the problem of encoding a given graph $`G`$ into a binary string $`S`$ with the requirement that $`S`$ can be decoded to reconstruct $`G`$. The problem has been studied generally with two primary objectives. One is to minimize the length of $`S`$, while the other is to minimize the time needed to compute and decode $`S`$. In light of these goals, a coding scheme is efficient if its encoding and decoding procedures both take polynomial time. A coding scheme is succinct if the length of $`S`$ is not much larger than its information-theoretic tight bound, i.e., the shortest length over all possible coding schemes.

As the two primary objectives are often in conflict, a number of coding schemes with different trade-offs have been proposed from practical and theoretical perspectives. The most well-known efficient succinct scheme is the folklore scheme of encoding a rooted ordered $`n`$-vertex tree into a string of balanced $`n1`$ pairs of left and right parentheses, which uses $`2(n1)`$ bits. Since the total number of such trees is at least $`\frac{1}{2(n1)}\frac{(2n2)!}{(n1)!(n1)!}`$, the minimum number of bits needed to differentiate these trees is the logarithm111All logarithms are of base 2. of this quantity, which is $`2no(n)`$ by Stirling’s approximation. Thus, 2 bits per edge is an information-theoretic tight bound for encoding rooted ordered trees. The standard adjacency-list encoding of a graph is widely useful but requires $`\mathrm{\Theta }(m\mathrm{log}n)`$ bits where $`m`$ and $`n`$ are the numbers of edges and vertices, respectively . For certain graph families, Kannan, Naor and Rudich  gave schemes that encode each vertex with $`O(\mathrm{log}n)`$ bits and support $`O(\mathrm{log}n)`$-time testing of adjacency between two vertices. For connected planar graphs, Jacobson  gave an $`\mathrm{\Theta }(n)`$-bit encoding which supports traversal in $`\mathrm{\Theta }(\mathrm{log}n)`$ time per vertex visited. This result was recently improved by Munro and Raman ; their schemes encode binary trees, rooted ordered trees and planar graphs succinctly and support several graph operations in constant time. For dense graphs and complement graphs, Kao, Occhiogrosso, and Teng  devised two compressed representations from adjacency lists to speed up basic graph techniques such as breadth-first search and depth-first search. Galperin and Wigderson  and Papadimitriou and Yannakakis  investigated complexity issues arising from encoding a graph by a small circuit that computes its adjacency matrix. For labeled planar graphs, Itai and Rodeh  gave an encoding procedure that requires $`\frac{3}{2}n\mathrm{log}n+O(n)`$ bits. For unlabeled general graphs, Naor  gave an encoding of $`\frac{n^2}{2}n\mathrm{log}n+O(n)`$ bits, which is optimal to the second order.

Our work aims to minimize the number of bits needed to encode an embedded planar graph $`G`$ which is unlabeled and undirected. We assume that $`G`$ has $`n`$ vertices, $`m`$ edges, and $`f`$ faces but has no self-loop or multiple edge. (See  for the graph-theoretic terminology used in this paper.) Note that if polynomial time for encoding and decoding is not required, then any given graph in a large family can be encoded with the information-theoretic minimum number of bits by brute-force enumeration. This paper focuses on schemes that use only $`O(n)`$ time for both encoding and decoding.

For a general planar graph $`G`$, Turán  gave an encoding using $`4m`$ bits asymptotically. This space complexity was improved by Keeler and Westbrook  to about $`3.58m`$ bits. They also gave encoding algorithms for several important classes of planar graphs. In particular, they showed that if $`G`$ is triangulated, it can be encoded in about $`1.53m`$ bits. If $`G`$ is triconnected, it can be encoded using $`3m`$ bits. In this paper, these latter two results are improved as follows. If $`G`$ is triangulated, it can be encoded using $`\frac{4}{3}m1`$ bits. It is interesting that rooted ordered trees require 2 bits per edge, while the seemingly more complex plane triangulations need fewer bits. Note that Tutte  gave an enumeration theorem that yields an information-theoretic tight bound of roughly $`1.08m`$ bits for plane triangulations that may contain multiple edges. If $`G`$ is triconnected, we can encode it using at most $`(2.5+2\mathrm{log}3)\mathrm{min}\{n,f\}7`$ bits, which is at most $`2.835m`$ bits. Both of our coding schemes are intuitive and simple. They require only $`O(n)`$ time for encoding as well as decoding. The schemes make new uses of the canonical orderings of planar graphs, which were originally introduced by de Fraysseix, Pach and Pollack  and extended by Kant . These structures and closely related ones have proven useful also for drawing planar graphs in organized and compact manners .

This paper is organized as follows. In §2, we present our coding scheme for plane triangulations. In §3, we generalize the scheme to encode triconnected plane graphs. We conclude the paper with some open problems in §4.

## 2 A Coding Scheme for Plane Triangulations

This section assumes that $`G`$ is a plane triangulation. Thus, $`n3`$ and $`G`$ has $`m=3n6`$ edges.

Let $`v_1,\mathrm{},v_n`$ be an ordering of the vertices of $`G`$, where $`v_1,v_2,v_n`$ are the three exterior vertices of $`G`$ in the counterclockwise order. After fixing such an ordering, let $`G_k`$ be the subgraph of $`G`$ induced by $`v_1,\mathrm{},v_k`$. Let $`H_k`$ be the exterior face of $`G_k`$. Let $`GG_k`$ be the subgraph of $`G`$ obtained by removing $`v_1,\mathrm{},v_k`$. Our coding scheme uses a special kind of ordering defined as follows.

###### Definition 1 (see ).

An ordering $`v_1,\mathrm{},v_n`$ of $`G`$ is canonical if the following statements hold for every $`k=3,\mathrm{},n`$:

1. $`G_k`$ is biconnected, and its exterior face $`H_k`$ is a cycle containing the edge $`(v_1,v_2)`$.
2. The vertex $`v_k`$ is on the exterior face of $`G_k`$, and the set of its neighbors in $`G_{k1}`$ forms a subinterval of the path $`H_{k1}\{(v_1,v_2)\}`$ and consists of at least two vertices. Furthermore, if $`k<n`$, $`v_k`$ has at least one neighbor in $`GG_k`$. Note that the case $`k=3`$ is somewhat ambiguous due to degeneracy, and $`H_2\{(v_1,v_2)\}`$ is regarded as the edge $`(v_1,v_2)`$ itself.

Figure 1 illustrates a canonical ordering of a plane triangulation. Note that every plane triangulation has a canonical ordering which can be computed in $`O(n)`$ time . A canonical ordering of $`G`$ can be viewed as an order in which $`G`$ is reconstructed from a single edge $`(v_1,v_2)`$ step by step. At step $`k`$ with $`3kn`$, the vertex $`v_k`$ and the edges between $`v_k`$ and its lower ordered neighbors are added into the graph. For the sake of enhancing intuitions, we call $`H_{k1}`$ the contour of $`G_{k1}`$; denote its vertices by $`c_1(=v_1),c_2,\mathrm{},c_{t1},c_t(=v_2)`$ in the consecutive order along the cycle $`H_{k1}`$; and visualize them as arranged from left to right above the edge $`(v_1,v_2)`$ in the plane. When the vertex $`v_k`$ is added to $`G_{k1}`$ to construct $`G_k`$, let $`c_{\mathrm{}},c_{\mathrm{}+1},\mathrm{},c_r`$ be the neighbors of $`v_k`$ on the contour $`H_{k1}`$. After $`v_k`$ is added, the vertices $`c_{\mathrm{}+1},\mathrm{},c_{r1}`$ are no longer contour vertices. Thus, we say that these vertices are covered by $`v_k`$. The edge $`(v_k,c_{\mathrm{}})`$ is the left edge of $`v_k`$; the edge $`(v_k,c_r)`$ is the right edge of $`v_k`$; the edges $`(c_p,v_k)`$ with $`\mathrm{}<p<r`$ are the internal edges of $`v_k`$.

There is no published reference for the following folklore lemma; for the sake of completeness, we include its proof here.

###### Lemma 2.

Let $`v_1,\mathrm{},v_n`$ be a canonical ordering of $`G`$. Let $`T_1`$ $`(`$respectively, $`T_2`$$`)`$ be the collection of the left $`(`$respectively, right$`)`$ edges of $`v_j`$ for $`3jn1`$; similarly, let $`T_n`$ be that of the internal edges of $`v_j`$ for $`3jn`$.

1. $`T_1`$ is a tree spanning over $`G\{v_2,v_n\}`$.
2. $`T_2`$ is a tree spanning over $`G\{v_1,v_n\}`$.
3. $`T_n`$ is a tree spanning over $`G\{v_1,v_2\}`$.

###### Proof.

The statements are proved separately as follows.

Statement 1. For $`i=3,\mathrm{},n1`$, let $`D_i`$ be the collection of the left edges of $`v_j`$ for $`3ji`$. We prove by induction on $`i`$ the claim that $`D_i`$ is a tree spanning over $`v_1,v_3,\mathrm{},v_i`$. Then, since $`T_1=D_{n1}`$, the claim implies the statement. For the base case $`i=3`$, the claim trivially holds. The induction hypothesis is that the claim holds for $`i=k1<n1`$. The induction step is to prove the claim for $`i=kn1`$. $`D_k`$ is obtained from $`D_{k1}`$ by adding the left edge $`(v_k,c_{\mathrm{}})`$ of $`v_k`$. By the induction hypothesis, $`D_{k1}`$ is a tree spanning over $`v_1,v_3,\mathrm{},v_{k1}`$. Since $`c_{\mathrm{}}`$ is the leftmost neighbor of $`v_k`$ on $`H_{k1}`$, $`c_{\mathrm{}}`$ is some $`v_j`$ with $`1jk1`$ and $`j2`$. Thus, $`D_{k1}`$ contains $`c_{\mathrm{}}`$, and $`D_k`$ is a tree spanning over $`v_1,v_3,\mathrm{},v_{k1},v_k`$.

Statement 2. The proof is symmetric to that of Statement 1.

Statement 3. $`G`$ has $`n`$ vertices and $`3n6`$ edges. The edges $`(v_1,v_2),(v_2,v_n),(v_1,v_n)`$ are not in $`T_1T_2T_n`$. Thus, since $`T_1`$ and $`T_2`$ have $`n3`$ edges each, $`T_n`$ has $`n3`$ edges. Then, since $`T_n`$ is acyclic and does not contain $`v_1`$ and $`v_2`$, $`T_n`$ is a spanning tree of $`G\{v_1,v_2\}`$. ∎

A canonical ordering $`v_1,\mathrm{},v_n`$ is rightmost if for all $`v_k`$ and $`v_k^{}`$ with $`k^{}>k`$ such that the neighbors of $`v_k^{}`$ on $`H_{k^{}1}`$ are all in $`H_{k1}`$, the leftmost neighbor of $`v_k^{}`$ appears before that of $`v_k`$ when traversing $`H_{k1}`$ from $`v_1`$ to $`v_2`$ in the clockwise direction. Intuitively speaking, if there are more than one vertex that can be added to $`G_{k1}`$, we always add the rightmost one. The ordering in Figure 1 is rightmost. A rightmost canonical ordering is symmetric to a leftmost one in  and can be computed from $`G`$ in linear time similarly.

Let $`v_1,\mathrm{},v_n`$ be a rightmost canonical ordering of $`G`$. Let $`T_1`$ be as in Lemma 2 for this ordering. Let $`T`$ be the tree $`T_1\{(v_1,v_n),(v_1,v_2)\}`$. In Figure 1, $`T`$ is indicated by the thick lines. Our coding scheme uses $`T`$ extensively. The rightmost depth-first search of $`T`$ proceeds as follows. We start at $`v_1`$ and traverse the edge $`(v_1,v_2)`$ first. Afterwards, if two or more vertices can be visited from $`v_k`$, we choose the rightmost one. More precisely, let $`P`$ be the path in $`T`$ from $`v_k`$ to $`v_1`$ and then to $`v_2`$. Let $`D`$ be the set of edges between $`v_k`$ and the available vertices. We visit a new vertex through the edge in $`D`$ that is next to $`P`$ in the counterclockwise cyclic order around $`v_k`$ formed by $`P`$ and the edges in $`D`$. Note that the order in which the vertices are visited by the rightmost depth-first search is the rightmost canonical ordering $`v_1,\mathrm{},v_n`$ that defines $`T`$.

We are now ready to describe the encoding $`S`$ of $`G`$ as the concatenation of two binary strings $`S_1`$ and $`S_2`$ as follows.

$`S_1`$ is the binary string that encodes $`T`$ using the folklore parenthesis coding scheme where $`0`$ and $`1`$ correspond to $`{}_{}{}^{\prime \prime }(_{}^{\prime \prime }`$ and $`{}_{}{}^{\prime \prime })^{\prime \prime }`$, respectively. In this encoding, $`T`$ is rooted at $`v_1`$, and the branches are ordered the same as their enpoints are in the rightmost canonical ordering. Since $`T`$ contains $`n`$ vertices, $`S_1`$ has $`2(n1)`$ bits.

$`S_2`$ encodes the number of contour vertices covered by each $`v_k`$ with $`3kn`$. First, we create a string of $`n2`$ copies of $`0`$. The $`(k2)`$-th $`0`$ corresponds to $`v_k`$. If $`v_k`$ covers $`d`$ vertices, we insert $`d`$ copies of $`1`$ before the corresponding $`0`$. For example, the string $`S_2`$ for Figure 1 is:

$$00010101110$$

Since each vertex $`v_k`$ with $`3kn1`$ is covered exactly once, $`S_2`$ has $`n3`$ copies of 1. So $`|S_2|=(n2)+(n3)=2n5`$ bits. Hence, $`|S|=|S_1|+|S_2|=4n7`$ bits.

We next describe how to decode $`S`$ to reconstruct $`G`$. Given $`S`$, we can uniquely determine $`n`$ from the length of $`S`$. Subsequently, we can uniquely determine $`S_1`$ and $`S_2`$. From $`S_1`$, we can reconstruct $`T`$. From $`T`$, we can recover the ordering $`v_1,\mathrm{},v_n`$. Then, we draw the edge $`(v_1,v_2)`$ and perform a loop of $`n2`$ steps indexed by $`k`$ with $`3kn`$ where step $`k`$ processes $`v_k`$. Before $`v_k`$ is processed, $`G_{k1}`$ and its contour $`H_{k1}`$ have been constructed. At step $`k`$, we add $`v_k`$ and the edges between $`v_k`$ and its lower ordered neighbors into $`G_{k1}`$ to construct $`G_k`$ as follows. From $`T`$, we can identify the leftmost neighbor $`c_{\mathrm{}}`$ of $`v_k`$ on the contour $`H_{k1}`$, because $`c_{\mathrm{}}`$ is simply the parent of $`v_k`$ in $`T`$. From $`S_2`$, we can determine the number $`d`$ of vertices covered by $`v_k`$. Thus, we add the edges $`(c_{\mathrm{}},v_k),(c_{\mathrm{}+1},v_k),\mathrm{},(c_{\mathrm{}+d+1},v_k)`$ into $`G_{k1}`$; note that $`r=\mathrm{}+d+1`$. This gives us the subgraph $`G_k`$ and completes step $`k`$.

It is straightforward to carry out these encoding and decoding procedures in linear time. Also, we can save 1 bit by deleting the last $`0`$ in $`S_2`$. Since $`v_3`$ covers no vertex, for $`n4`$, we can save another bit by deleting the first $`0`$ in $`S_2`$. Note that for $`n=3`$, the last $`0`$ in $`S_2`$ is also the first $`0`$ and cannot be deleted twice, but we can simply encode the 3-vertex plane triangulation with zero bit without ambiguity. Thus, we have the following theorem.

###### Theorem 3.

A plane triangulation of $`m`$ edges and $`n`$ vertices with $`n4`$ can be encoded using $`4n9=\frac{4}{3}m1`$ bits. Both encoding and decoding take $`O(n)`$ time.

## 3 A Coding Scheme for Triconnected Plane Graphs

This section assumes that $`G`$ is triconnected. To avoid triviality, let $`n3`$.

Let $`v_1,\mathrm{},v_n`$ be an ordering of the vertices of $`G`$ where $`v_1,v_2,v_n`$ are on the exterior face of $`G`$, and $`v_2`$ and $`v_n`$ are neighbors of $`v_1`$. Let $`G_k`$ be the subgraph of $`G`$ induced by $`v_1,\mathrm{},v_k`$. Let $`H_k`$ be the exterior face of $`G_k`$. Let $`GG_k`$ be the subgraph of $`G`$ obtained by removing $`v_1,\mathrm{},v_k`$. Our coding scheme for triconnected plane graphs uses an ordering defined as follows.

###### Definition 4 (see ).

An ordering $`v_1,\mathrm{},v_n`$ of a triconnected plane graph $`G`$ is canonical if the integer interval $`[3,n]`$ can be partitioned into subintervals $`[k,k+q]`$ each satisfying either set of properties below:

1. The integer $`q`$ is $`0`$. The vertex $`v_k`$ is on the exterior face of $`G_k`$ and has at least two neighbors in $`G_{k1}`$. $`G_k`$ is biconnected and its exterior face contains the edge $`(v_1,v_2)`$. If $`k<n`$, $`v_k`$ has at least one neighbor in $`GG_k`$.
2. The integer $`q`$ is at least $`1`$. The sequence $`v_k,v_{k+1},\mathrm{},v_{k+q}`$ is a chain on the exterior face of $`G_{k+q}`$ and has exactly two neighbors in $`G_{k1}`$, one for $`v_k`$ and the other for $`v_{k+q}`$, which are on the exterior face of $`G_{k1}`$. $`G_{k+q}`$ is biconnected and its exterior face contains the edge $`(v_1,v_2)`$. Every vertex among $`v_k,\mathrm{},v_{k+q}`$ has at least one neighbor in $`GG_{k+q}`$.

As in §2, we similarly define a rightmost canonical ordering $`v_1,\mathrm{},v_n`$ of $`G`$. Figure 2 shows a rightmost canonical ordering of a triconnected plane graph. Given a triconnected plane graph, we can find a rightmost canonical ordering in linear time . With a rightmost canonical ordering, $`G`$ can be reconstructed from a single edge $`(v_1,v_2)`$ through a sequence of steps indexed by $`k^{}`$. There are two possible cases at step $`k^{}`$, which correspond to the two sets of properties in Definition 4 and are used throughout this section.

Case 1: A single vertex $`v_k`$ is added.

Case 2: A chain of $`q+1`$ vertices $`v_k,\mathrm{},v_{k+q}`$ is added.

While reconstructing $`G`$, we collect a set $`T`$ of edges as follows. Initially, $`T`$ consists of the edge $`(v_1,v_2)`$. Let $`c_1(=v_1),c_2,\mathrm{},c_{t1},c_t(=v_2)`$ be the vertices of $`H_{k1}`$, which are ordered consecutively along the boundary cycle of $`H_{k1}`$ and are arranged from left to right above the edge $`(v_1,v_2)`$ in the plane.

Case 1. Let $`c_{\mathrm{}}`$ and $`c_r`$ with $`1\mathrm{}<rt`$ be the leftmost and rightmost neighbors of $`v_k`$ in $`H_{k1}`$, respectively. After $`v_k`$ is added, $`c_{\mathrm{}+1},\mathrm{},c_{r1}`$ are no longer contour vertices; these vertices are covered at step $`k^{}`$. The edge $`(c_{\mathrm{}},v_k)`$ is included in $`T`$.

Case 2. Let $`c_{\mathrm{}}`$ and $`c_r`$ with $`1\mathrm{}<rt`$ be the neighbors of $`v_k`$ and $`v_{k+q}`$ in $`H_{k1}`$, respectively. After $`v_k,\mathrm{},v_{k+q}`$ are added, $`c_{\mathrm{}+1},\mathrm{},c_{r1}`$ are no longer contour vertices; these vertices are covered at step $`k^{}`$. The edges $`(c_{\mathrm{}},v_k),(v_k,v_{k+1}),\mathrm{},(v_{k+q1},`$ $`v_{k+q})`$ are included in $`T`$.

In Figure 2, the edges in $`T`$ are indicated by the thick lines. By an argument similar to the proof of Lemma 2(1), $`T`$ is a spanning tree of $`G`$. As in §2, we similarly define the rightmost depth-first search in $`T`$. Note that the order in which the vertices of $`T`$ are visited by the rightmost depth-first search is the rightmost canonical ordering $`v_1,\mathrm{},v_n`$ that defines $`T`$.

We are now ready to describe the encoding $`S`$ of $`G`$ by means of $`T`$. We further divide Case 1 into three subcases.

Case 1a: No vertex is covered at step $`k^{}`$.

Case 1b: At least one vertex is covered at step $`k^{}`$ and the leftmost covered vertex $`c_{\mathrm{}+1}`$ is adjacent to $`v_k`$.

Case 1c: At least one vertex is covered at step $`k^{}`$ and the leftmost covered vertex $`c_{\mathrm{}+1}`$ is not adjacent to $`v_k`$.

Let $`\beta `$ be the number of steps for reconstructing $`G`$. Let $`\beta _{1a},\beta _{1b},\beta _{1c}`$ and $`\beta _2`$ be the numbers of steps of Cases 1a, 1b, 1c, and 2, respectively. We first consider the case $`\beta _{1b}\beta _{1c}`$ to encode $`G`$ with Scheme I; afterwards, we modify Scheme I into Scheme II for the case $`\beta _{1b}<\beta _{1c}`$.

In Scheme I, the encoding $`S`$ of $`G`$ is the concatenation of three strings $`S_1`$, $`S_2`$ and $`S_3`$. $`S_1`$ is the folklore parentheses encoding of $`T`$, which is rooted and ordered in the same way as in §2. Since $`T`$ has $`n`$ vertices, $`S_1`$ has $`2(n1)`$ bits.

To construct $`S_2`$, first let $`Q=s_1s_2\mathrm{}s_\beta `$ where each $`s_k^{}`$ is a binary string that corresponds to the step $`k^{}`$ of reconstructing $`G`$ based on the ordering $`v_1,\mathrm{},v_n`$. $`s_k^{}`$ is determined as follows. The following two cases both assume that $`d`$ vertices are covered at step $`k^{}`$.

Case 1. Note that $`d=r\mathrm{}1`$. The string $`s_k^{}`$ has $`d`$ symbols corresponding to $`c_j`$ with $`j=\mathrm{}+1,\mathrm{},r1`$, respectively. If the edge $`(c_j,v_k)`$ is present in $`G`$, the symbol in $`s_k^{}`$ corresponding to $`c_j`$ is 1; otherwise, the symbol is 0. Note that in Case 1a, since no vertex is covered, $`s_k^{}`$ is empty.

Case 2. The string $`s_k^{}`$ consists of $`q`$ copies of $`0`$ followed by $`d`$ copies of $`1`$.

For example, the string $`Q`$ for Figure 2 is:

$`\begin{array}{cccccccccccccc}\underset{}{00}& & 0& & & 0& & 0& & \underset{}{1000}& & & \underset{}{10001}& \\ & & & & & & & & & & & & & \\ s_1& & s_2& & & s_4& & s_5& & s_6& & & s_8& \end{array}`$

$`S_2`$ is a binary representation of $`Q`$ defined as follows. A step of Case 1 adds one vertex to $`G`$ and correspondingly includes one $``$ in $`Q`$; similarly, a step of Case 2 adds $`q+1`$ vertices to $`G`$ and includes one $``$ and $`q`$ copies of $`0`$ in $`Q`$. Since exactly $`n2`$ vertices are added, the total number of these symbols is $`n2`$. Each symbol in $`Q`$ not yet counted corresponds to a vertex covered at the $`\beta `$ steps. Since each $`v_k`$ with $`3kn1`$ is covered at most once and $`v_1,v_2,v_n`$ are never covered, the total number of these latter symbols is at most $`n3`$. Thus $`Q`$ has at most $`2n5`$ symbols. For the sake of unambiguous decoding, we pad $`Q`$ with copies of 1 at its end to have exactly $`2n5`$ symbols. Since $`Q`$ uses 3 distinct symbols, we treat it as an integer of base 3 and convert it to a binary integer. Again, for the sake of unambiguous decoding, we use exactly $`(2n5)\mathrm{log}3`$ bits for this binary integer by padding copies of $`0`$ at its beginning. The resulting binary string is the desired $`S_2`$.

For the sake of decoding, we also need to know whether any given $`s_k^{}`$ is of Case 1 or 2. Thus, let $`S_3=t_1\mathrm{}t_\beta `$ where $`t_k^{}=1`$ if step $`k^{}`$ is of Case 1 and $`t_k^{}=0`$ otherwise. To save space, note that some bits $`t_k^{}`$ can be deleted as follows without incurring ambiguity. If step $`k^{}`$ is of Case 1a, $`t_k^{}`$ is deleted because $`s_k^{}`$ is empty and only a string of Case 1a can be empty. If step $`k^{}`$ is of Case 1b, $`t_k^{}`$ is deleted because $`s_k^{}`$ starts with 1, while the strings of Case 2 start with 0. If step $`k^{}`$ is of Case 1c or 2, $`t_k^{}`$ remains in $`S_3`$. For example, the string $`S_3`$ for Figure 2 consists of $`t_1=0`$, $`t_2=0`$, $`t_4=1`$, $`t_5=0`$. Thus, $`S_3`$ has $`\beta _{1c}+\beta _2`$ bits, which can be bounded as follows. A step of Case 1 adds one vertex into $`G`$ and a step of Case 2 adds at least two vertices. Since $`n2`$ vertices are added over the $`\beta `$ steps, $`\beta _{1a}+\beta _{1b}+\beta _{1c}+2\beta _2n2`$. Since Scheme I assumes $`\beta _{1b}\beta _{1c}`$, $`|S_3|=\beta _{1c}+\beta _2\frac{1}{2}(\beta _{1b}+\beta _{1c})+\beta _2\frac{1}{2}(\beta _{1a}+\beta _{1b}+\beta _{1c}+2\beta _2)0.5n1`$.

Since $`S=S_1//S_2//S_3`$, $`|S|2(n1)+(2n5)\mathrm{log}3+0.5n1(2.5+2\mathrm{log}3)n9`$ bits. This completes the description of the encoding procedure of Scheme I.

Next we describe how to decode $`S`$ to reconstruct $`G`$. This decoding assumes that both $`S`$ and $`n`$ are given. Thus, we can uniquely determine $`S_1`$, $`S_2`$ and $`S_3`$. Then we convert $`S_2`$ to $`Q`$. From $`Q`$ we can recover all $`s_k^{}`$ with $`1k^{}\beta `$. From $`S_3`$ and all $`s_k^{}`$, we can recover all $`t_k^{}`$ with $`1k^{}\beta `$. From $`S_1`$, we reconstruct $`T`$. From $`T`$, we find the ordering $`v_1,\mathrm{},v_n`$. Afterwards, we draw the edge $`(v_1,v_2)`$ and perform a loop of steps as follows. Each step is indexed by $`k^{}`$ and corresponds to step $`k^{}`$ of reconstructing $`G`$ using the rightmost canonical ordering.

If $`t_k^{}=1`$, step $`k^{}`$ is of Case 1. Thus, a vertex $`v_k`$ is added at this step where $`v_k`$ is the smallest ordered vertex not added into the current graph yet. From $`T`$, we can determine the leftmost neighbor $`c_{\mathrm{}}`$ of $`v_k`$ in the contour $`H_{k1}`$ because $`c_{\mathrm{}}`$ is the parent of $`v_k`$ in $`T`$. From $`s_k^{}`$, we know the number of vertices covered by $`v_k`$ and hence the rightmost neighbor $`c_r`$ of $`v_k`$ in the contour $`H_{k1}`$. From $`s_k^{}`$, we also know which of the covered vertices are connected to $`v_k`$. These corresponding edges are added to $`G`$.

If $`t_k^{}=0`$, step $`k^{}`$ is of Case 2. Thus, a chain $`v_k,\mathrm{},v_{k+q}`$ is added at this step where $`v_k`$ is the smallest ordered vertex not added into the current graph yet. The integer $`q`$ can be determined from the string $`s_k^{}`$ by counting its leading copies of $`0`$. From $`s_k^{}`$, we also know the number of vertices covered at step $`k^{}`$, which is the count of $`1`$ in $`s_k^{}`$. Thus, we know the neighbor $`c_r`$ of $`v_{k+q}`$ in the contour $`H_{k1}`$. The chain is added accordingly.

This completes the decoding procedure of Scheme I. It is straightforward to implement the whole Scheme I in $`O(n)`$ time. If $`\beta _{1b}<\beta _{1c}`$, we use Scheme II to encode $`G`$, which is identical to Scheme I with the following differences. If step $`k^{}`$ is of Case 2, $`s_k^{}`$ consists of $`q`$ copies of 1 followed by $`d`$ copies of 0. Also, all bits $`t_k^{}`$ for steps of Cases 1a and 1c are omitted from $`S_3`$ without incurring ambiguity since their corresponding strings $`s_k^{}`$ either are empty or start with 0 while the strings of Cases 1b and 2 start with 1. We use one extra bit to encode whether we use Scheme I or II. Thus we have the following lemma.

###### Lemma 5.

Any triconnected plane graph with $`n`$ vertices can be encoded using at most $`(2.5+2\mathrm{log}3)n8`$ bits. Both encoding and decoding take $`O(n)`$ time. The decoding procedure assumes that both $`S`$ and $`n`$ are given.

We can improve Lemma 5 as follows. Let $`G^{}`$ be the dual of $`G`$. $`G^{}`$ has $`f`$ vertices, $`m`$ edges and $`n`$ faces. Since $`G`$ is triconnected, $`G^{}`$ is also triconnected. Furthermore, if $`n>3`$, then $`f>3`$ and $`G^{}`$ has no self-loop or multiple edge. Thus, we can use the coding scheme of Lemma 5 to encode $`G^{}`$ with at most $`(2.5+2\mathrm{log}3)f8`$ bits. Since $`G`$ can be uniquely determined from $`G^{}`$, to encode $`G`$, it suffices to encode $`G^{}`$. To make $`S`$ shorter, for the case $`n>3`$, if $`nf`$, we encode $`G`$ using at most $`(2.5+2\mathrm{log}3)n8`$ bits; otherwise, we encode $`G^{}`$ using at most $`(2.5+2\mathrm{log}3)f8`$ bits. This new encoding has at most $`(2.5+2\mathrm{log}3)\mathrm{min}\{n,f\}8`$ bits. Since $`\mathrm{min}\{n,f\}\frac{n+f}{2}`$, the bit count is at most $`(1.25+\mathrm{log}3)m2`$ by Euler’s formula $`n+f=m+2`$. For the sake of decoding, we use one extra bit to denote whether we encode $`G`$ or its dual. Note that if $`n=3`$, we can simply encode $`G`$ using zero bit without ambiguity. Thus we have proved the following theorem.

###### Theorem 6.

Any triconnected plane graph with $`n`$ vertices, $`m`$ edges and $`f`$ faces can be encoded using at most $`(2.5+2\mathrm{log}3)\mathrm{min}\{n,f\}7(1.25+\mathrm{log}3)m1`$ bits. Both encoding and decoding take $`O(n)`$ time. The decoding procedure assumes that $`S`$ is given together with $`n`$ or $`f`$ as appropriate.

Remark. There are several ways to improve this coding scheme so that the decoding does not require $`n`$ as input. One is to use well-known data compression techniques to encode $`n`$ and append it to the beginning of $`S`$ using $`\mathrm{log}n+O(\mathrm{log}\mathrm{log}n)`$ bits . Another is to pad $`S`$ with copies of $`1`$ at its end so that it has exactly $`(2.5+2\mathrm{log}3)\mathrm{min}\{n,f\}7`$ bits. Then, since $`2.5+2\mathrm{log}3>1`$, given $`S`$ alone, we can uniquely determine $`n`$ or $`f`$ and proceed with the original decoding procedure. With the strings $`s_k^{}`$, we can unambiguously identify the padded bits.

## 4 Open Problems

This paper leaves several problems open. Since plane triangulations are useful in many application areas, it would be particularly helpful to encode them in $`O(n)`$ time using close to $`1.08m`$ bits. Similarly, it would be significant to obtain a linear-time coding scheme for triconnected plane graphs using close to $`2m`$ bits. Note that Tutte  proved an information-theoretic tight bound of $`2m+o(m)`$ bits for triconnected plane graphs that may contain multiple edges and self-loops. More generally, it would be of interest to encode graphs in a given family in polynomial time using their information-theoretic minimum number of bits. Solving these problems will most likely lead to the discovery of new structural properties of graphs.

Acknowledgments. The authors are grateful to anonymous referees for helpful comments.


text:
# 1 Introduction

## 1 Introduction

The definitions of the $`q`$-Bessel-Macdonald functions ($`q`$-BMF) and their properties were given in . Their representations by the Jackson $`q`$-integral have been constructed in .

The double integral appears necessarily if we consider the problems of the harmonic analysis on the quantum Lobachevsky space. As the double Jackson $`q`$-integral is connected hardly with the $`q`$-lattice we have not any possibility to pass to the polar coordinates. So we are forced to introduce the usual double integral for $`q`$-functions.

In the first sections we remind the known formulas for $`q`$-Bessel functions and $`q`$-binomial.

## 2 The modified $`q`$-Bessel functions and the $`q`$-BMF

In  the $`q`$-Bessel functions were defined as follows:

$$J_\nu ^{(1)}(z,q)=\frac{(q^{\nu +1},q)_{\mathrm{}}}{(q,q)_{\mathrm{}}}(z/2)_2^\nu \mathrm{\Phi }_1(0,0;q^{\nu +1};q,\frac{z^2}{4}),$$
(2.1)
$$J_\nu ^{(2)}(z,q)=\frac{(q^{\nu +1},q)_{\mathrm{}}}{(q,q)_{\mathrm{}}}(z/2)_0^\nu \mathrm{\Phi }_1(;q^{\nu +1};q,\frac{z^2q^{\nu +1}}{4}),$$
(2.2)
$$J_\nu ^{(3)}(z,q)=\frac{(q^{\nu +1},q)_{\mathrm{}}}{(q,q)_{\mathrm{}}}(z/2)_1^\nu \mathrm{\Phi }_1(0;q^{\nu +1};q,\frac{z^2q^{\frac{\nu +1}{2}}}{4}).$$
(2.3)
where $`{}_{r}{}^{}\mathrm{\Phi }_{s}^{}`$ is basic hypergeometric function ,

$${}_{r}{}^{}\mathrm{\Phi }_{s}^{}(a_1,\mathrm{},a_r;b_1,\mathrm{},b_s;q,z)=\underset{n=0}{\overset{\mathrm{}}{}}\frac{(a_1,q)_n\mathrm{}(a_r,q)_n}{(q,q)_n(b_1,q)_n\mathrm{}(b_s,q)_n}[(1)^nq^{n(n1)/2}]^{1+sr}z^n,$$

$$(a,q)_n=\{\begin{array}{ccc}1\hfill & \mathrm{for}& n=0\hfill \\ (1a)(1aq)\mathrm{}(1aq^{n1})\hfill & \mathrm{for}& n1,\hfill \end{array}$$

$$(a,q)_{\mathrm{}}=\underset{n\mathrm{}}{lim}(a,q)_n,(a_1,\mathrm{},a_k,q)_{\mathrm{}}=(a_1,q)_{\mathrm{}}\mathrm{}(a_k,q)_{\mathrm{}}.$$

It allows to introduce the modified $`q`$-Bessel functions ($`q`$-MBFs) using (2.1), (2.2) and (2.3) similarly to the classical case .

###### Definition 2.1

The modified $`q`$-Bessel functions are the functions

$$I_\nu ^{(j)}(z,q)=\frac{(q^{\nu +1},q)_{\mathrm{}}}{(q,q)_{\mathrm{}}}(z/2)_\delta ^\nu \mathrm{\Phi }_1(\underset{\delta }{\underset{}{0,\mathrm{},0}};q^{\nu +1};q,\frac{z^2q^{\frac{\nu +1}{2}(2\delta )}}{4}).$$

Here

$$\delta =\{\begin{array}{ccc}2\hfill & \mathrm{for}& j=1\hfill \\ 0\hfill & \mathrm{for}& j=2\hfill \\ 1\hfill & \mathrm{for}& j=3.\hfill \end{array}$$
(2.4)
Obviously,

$$I_\nu ^{(j)}(z,q)=e^{\frac{i\nu \pi }{2}}J_\nu ^{(j)}(e^{i\pi /2}z,q),j=1,2,3.$$

In the sequel we consider the functions

$$I_\nu ^{(1)}((1q^2)z;q^2)=\underset{k=0}{\overset{\mathrm{}}{}}\frac{(1q^2)^k(z/2)^{\nu +2k}}{(q^2,q^2)_k\mathrm{\Gamma }_{q^2}(\nu +k+1)},|z|<\frac{2}{1q^2},$$
(2.5)
$$I_\nu ^{(2)}((1q^2)z;q^2)=\underset{k=0}{\overset{\mathrm{}}{}}\frac{q^{2k(\nu +k)}(1q^2)^k(z/2)^{\nu +2k}}{(q^2,q^2)_k\mathrm{\Gamma }_{q^2}(\nu +k+1)}.$$
(2.6)
$$I_\nu ^{(3)}((1q^2)z;q^2)=\underset{k=0}{\overset{\mathrm{}}{}}\frac{q^{k(\nu +k)}(1q^2)^k(z/2)^{\nu +2k}}{(q^2,q^2)_k\mathrm{\Gamma }_{q^2}(\nu +k+1)},$$
(2.7)
where

$$\mathrm{\Gamma }_{q^2}(\nu )=\frac{(q^2,q^2)_{\mathrm{}}}{(q^{2\nu },q^2)_{\mathrm{}}}(1q^2)^{1\nu }$$

is the $`q^2`$-gamma function. If $`|q|<1,`$ the series (2.6) and (2.7) are absolutely convergent for all $`z0`$. Consequently, $`I_\nu ^{(2)}((1q^2)z;q^2)`$ and $`I_\nu ^{(3)}((1q^2)z;q^2)`$ are holomorphic functions outside a neighborhood of zero.

###### Remark 2.1

$$\underset{q10}{lim}I_\nu ^{(j)}((1q^2)z;q^2)=I_\nu (z),j=1,2,3.$$

###### Proposition 2.1

The function $`I_\nu ^{(j)}((1q^2)z;q^2)`$ is a solution of the difference equation

$$f(q^1z)(q^\nu +q^\nu )f(z)+f(qz)=q^\delta \frac{(1q^2)^2}{4}z^2f(q^{1\delta }z),$$
(2.8)
where $`j=1,2,3`$ are connected with $`\delta =2,0,1`$ by relations (2.4).

###### Corollary 2.1

The function $`I_\nu ^{(j)}((1q^2)z;q^2)`$ satisfies equation (2.8).

###### Definition 2.2

We define the $`q`$-Bessel-Macdonald function ($`q`$-BMF) for $`j=1,2,3`$ as follows :

$$K_\nu ^{(j)}((1q^2)z;q^2)=$$

$$=\frac{1}{2}q^{\nu ^2+\nu }\mathrm{\Gamma }_{q^2}(\nu )\mathrm{\Gamma }_{q^2}(1\nu )\left[A_\nu ^{|1\delta |}I_\nu ^{(j)}((1q^2)z;q^2)A_\nu ^{|1\delta |}I_\nu ^{(j)}((1q^2)z;q^2)\right],$$
(2.9)
where

$$A_\nu =\sqrt{\frac{I_\nu ^{(2)}(2;q^2)}{I_\nu ^{(2)}(2;q^2)}}.$$
(2.10)
As in the classical case, this definition must be extended to integral values of $`\nu =n`$ by passing to the limit in (2.9).

###### Definition 2.3

The $`q`$-Wronskian of two solutions $`f_\nu ^1(z)`$ and $`f_\nu ^2(z)`$ of a second-order difference equation is defined as follows:

$$W(f_\nu ^1,f_\nu ^2)(z)=f_\nu ^1(z)f_\nu ^2(qz)f_\nu ^1(qz)f_\nu ^2(z).$$

If the $`q`$-Wronskian does not vanish, then any solution of the second-order difference equation can de written in form

$$f_\nu (z)=C_1f_\nu ^1(z)+C_2f_\nu ^2(z).$$

In this case the functions $`f_\nu ^1(z)`$ and $`f_\nu ^2(z)`$ form a fundamental system of the solutions of the given equation.

###### Proposition 2.2

The functions $`I_\nu ^{(j)}((1q^2)z;q^2)`$ and $`K_\nu ^{(j)}((1q^2)z;q^2)`$ form a fundamental system of the solutions of equation (2.8) ($`z\pm \frac{2q^r}{1q^2},r=0,1,\mathrm{}`$ if $`j=1`$).

This Proposition is following from

$$W(z)=\{\begin{array}{ccc}\frac{q^\nu (1q^2)}{2}A_\nu e_{q^2}(\frac{(1q^2)^2}{4}z^2)\hfill & \mathrm{for}& \delta =2\hfill \\ \frac{q^\nu (1q^2)}{2}\hfill & \mathrm{for}& \delta =1\hfill \\ \frac{q^\nu (1q^2)}{2}A_\nu E_{q^2}(\frac{(1q^2)^2}{4}q^2z^2)\hfill & \mathrm{for}& \delta =0.\hfill \end{array}$$

(See .) Obviously, this function is defined for $`z\pm \frac{2q^r}{1q^2},r=0,1,\mathrm{}`$ if $`j=1(\delta =2)`$ and does not vanish.

## 3 Some ancillary formulas

There is a $`q`$-analog of the classical binomial formula

$$(1z)^a=\underset{k=0}{\overset{\mathrm{}}{}}\frac{(a)_k}{k!}z^k,(a)_k=\frac{\mathrm{\Gamma }(a+k)}{\mathrm{\Gamma }(a)},|z|<1,$$

$$\frac{(q^\alpha z,q)_{\mathrm{}}}{(z,q)_{\mathrm{}}}=\underset{k=0}{\overset{\mathrm{}}{}}\frac{(q^\alpha ,q)_k}{(q,q)_k}z^k,|z|<1.$$

We need in two generalizations of the $`q`$-binomial

$$r(a,b,z,q)=\frac{(az,q)_{\mathrm{}}}{(bz,q)_{\mathrm{}}}$$
(3.1)
$$R(a,b,\gamma ,z,q^2)=\frac{(az^2,q^2)_{\mathrm{}}}{(bz^2,q^2)_{\mathrm{}}}z^\gamma $$
(3.2)
###### Proposition 3.1

The function $`R(a,b,\gamma ,z,q^2)`$ (3.2) satisfies the difference equation

$$z^2[bq^\gamma R(a,b,\gamma ,z,q^2)aR(a,b,\gamma ,qz,q^2)]=q^\gamma R(a,b,\gamma ,z,q^2)R(a,b,\gamma ,qz,q^2).$$
(3.3)
The Proof see in

It was shown in  that if $`\alpha >\beta `$ then

$$\frac{(q^{2\alpha }z^2,q^2)_{\mathrm{}}}{(q^{2\beta }z^2,q^2)_{\mathrm{}}}=\frac{(q^{2(\alpha \beta )},q^2)_{\mathrm{}}}{(q^2,q^2)_{\mathrm{}}}\underset{k=0}{\overset{\mathrm{}}{}}\frac{(q^{2(\beta \alpha +1)},q^2)_kq^{2(\alpha \beta 1)k}}{(q^2,q^2)_k(1+z^2q^{2\beta +2k})}.$$
(3.4)
###### Remark 3.1

Let $`a=ϵq^{2\alpha },b=ϵq^{2\beta },ϵ=\pm 1,`$ in (3.2). Then if $`q10`$ the difference equation (3.3) takes the form of the differential equation

$$z(1ϵz^2)R^{}(z)[\gamma +ϵ(2\alpha 2\beta \gamma )z^2]R(z)=0$$
(3.5)
with solution

$$R(z)=Cz^\gamma (1ϵz^2)^{\beta \alpha }.$$

Designate the $`q`$-derivative of $`g(x)`$ by

$$_xg(x)=\frac{g(x)g(qx)}{(1q)x}.$$

It follows from

$$J_0^{(j)}((1q^2)zs;q^2)=\underset{k=0}{\overset{\mathrm{}}{}}\frac{(1)^kq^{(2\delta )k^2}(1q^2)^{2k}(sz/2)^{2k}}{(q^2,q^2)_k^2}$$
(3.6)
that

$$\frac{2_z}{1+q}J_0^{(j)}((1q^2)q^1zs;q^2)=q^{1\frac{\delta }{2}}sJ_1^{(j)}((1q^2)q^{\frac{\delta }{2}}zs;q^2),$$
(3.7)
$$\frac{2_z}{1+q}J_0^{(j)}((1q^2)zs;q^2)=q^{1\frac{\delta }{2}}sJ_1^{(j)}((1q^2)q^{1\frac{\delta }{2}}zs;q^2)$$
(3.8)
and

$$\frac{2_s}{1+q}sJ_1^{(j)}((1q^2)q^{1\frac{\delta }{2}}zs;q^2)=q^{\frac{\delta }{2}}zsJ_0^{(j)}((1q^2)q^{1\delta }zs;q^2)$$
(3.9)
###### Lemma 3.1

If $`F(x)`$ is a differentiable (in classical sense) function in some neighborhood of zero then

$$\underset{\epsilon 0}{lim}_{q\epsilon }^\epsilon \frac{F(x)}{x}𝑑x=F(0)\mathrm{ln}q.$$
(3.10)
Proof. Integrating by parts we have

$$\underset{\epsilon 0}{lim}_{q\epsilon }^\epsilon \frac{F(x)}{x}𝑑x=\underset{\epsilon 0}{lim}\left[F(x)\mathrm{ln}x|_{q\epsilon }^\epsilon _{q\epsilon }^\epsilon F^{}(x)\mathrm{ln}xdx\right]=$$

$$=\underset{\epsilon 0}{lim}\left[(F(\epsilon )F(q\epsilon ))\mathrm{ln}\epsilon F(q\epsilon )\mathrm{ln}q_{q\epsilon }^\epsilon F^{}(x)\mathrm{ln}xdx\right].$$

Using Lagrange’s theorem and the theorem about mean value we obtain in the left side

$$\underset{\epsilon 0}{lim}\left[F^{}(\theta _1\epsilon )(1q)\epsilon \mathrm{ln}\epsilon F(q\epsilon )\mathrm{ln}q(1q)\epsilon F^{}(\theta _2\epsilon )\mathrm{ln}(\theta _2\epsilon )\right],$$

where $`\theta _1(0,1),\theta _2(0,1)`$. As $`lim_{\epsilon 0}\epsilon \mathrm{ln}\epsilon =0`$ we have (3.10).

###### Lemma 3.2

If $`f(x)`$ and $`g(x)`$ are integrable on $`(0,\mathrm{})`$ and differentiable ones in zero (in classical sense) then the $`q`$-analog of formula of integration by parts for the $`q`$-derivative takes place

$$_0^{\mathrm{}}_xf(x)g(x)dx=f(0)g(0)\frac{\mathrm{ln}q}{1q}_0^{\mathrm{}}f(qx)_xg(x)dx.$$
(3.11)
Proof.

$$_0^{\mathrm{}}_xf(x)g(x)dx=_0^{\mathrm{}}\frac{f(x)f(qx)}{(1q)x}g(x)𝑑x=$$

$$=_0^{\mathrm{}}\frac{f(x)g(x)f(qx)g(qx)}{(1q)x}𝑑x_0^{\mathrm{}}f(qx)\frac{g(x)g(qx)}{(1q)x}𝑑x=$$

$$=_0^{\mathrm{}}_x(f(x)g(x))dx_0^{\mathrm{}}f(qx)_xg(x)dx.$$

Using Lemma 3.1 calculate the first integral in the right side.

$$_0^{\mathrm{}}_x(f(x)g(x))dx=\frac{1}{1q}\underset{\epsilon 0}{lim}\left[_\epsilon ^{\mathrm{}}\frac{f(x)g(x)}{x}𝑑x_\epsilon ^{\mathrm{}}\frac{f(qx)g(qx)}{x}𝑑x\right]=$$

$$=\frac{1}{1q}\underset{\epsilon 0}{lim}_{q\epsilon }^\epsilon \frac{f(x)g(x)}{x}𝑑x=\frac{\mathrm{ln}q}{1q}f(0)g(0).$$

The statement of the Lemma follows from here.

###### Corollary 3.1

If $`f(s)g(s)s^1`$ is integrable function on $`(0,\mathrm{})`$ then

$$_0^{\mathrm{}}f(s)_sg(s)ds=_0^{\mathrm{}}_sf(s)g(qs)ds.$$
(3.12)
The Proof follows from $`f(0)g(0)=0`$ in this case.

## 4 The integral representations of the $`q`$-BMFs

We will assume that $`z`$ and $`s`$ are the commuting variables.

###### Proposition 4.1

$`q`$-BMF $`K_\nu ^{(j)}((1q^2)z;q^2)`$ for $`\mathrm{Re}\nu >0`$ can be represented as the integral

$$K_\nu ^{(j)}((1q^2)z;q^2)=\frac{q^{\nu ^2+\nu (1\delta )}(1q^2)}{2\mathrm{ln}q}\mathrm{\Gamma }_{q^2}(\nu +1)A_\nu ^{|1\delta |}\times $$

$$\times (z/2)^\nu _0^{\mathrm{}}\frac{(q^{2\nu +2\delta \nu }s^2,q^2)_{\mathrm{}}}{(q^{\delta \nu }s^2,q^2)_{\mathrm{}}}sJ_0^{(j)}((1q^2)zs;q^2)𝑑s,$$
(4.1)
where the constant $`A_\nu `$ is defined by (2.10) and $`j=1,2,3`$ are connected with $`\delta =2,0,1`$ by relations (2.4).

Proof. Consider the absolutely convergent integral

$$S^{(j)}(z)=_0^{\mathrm{}}f_\nu ^{(j)}(s)sJ_0^{(j)}((1q^2)zs;q^2)𝑑s,$$
(4.2)
and require that $`S^{(j)}(z)(z/2)^\nu `$ satisfies the difference equation (2.8). Then $`S^{(j)}(z)`$ satisfies the equation

$$S^{(j)}(q^1z)S^{(j)}(z)q^{2\nu }[S^{(j)}(z)S^{(j)}(qz)]=q^{\nu (\delta 2)\delta }(\frac{1q^2}{2})^2z^2S^{(j)}(q^{1\delta }z).$$
(4.3)
Substituting (4.2) in (4.3) and multiplying it on $`\frac{2z^1}{1q^2}`$ we obtain

$$_0^{\mathrm{}}f_\nu ^{(j)}(s)s\frac{2z^1}{1q^2}[J_0^{(j)}((1q^2)q^1zs;q^2)J_0^{(j)}((1q^2)zs;q^2)]𝑑s$$

$$q^{2\nu }_0^{\mathrm{}}f_\nu ^{(j)}(s)s\frac{2z^1}{1q^2}[J_0^{(j)}((1q^2)zs;q^2)J_0^{(j)}((1q^2)qzs;q^2)]𝑑s=$$

$$=q^{\nu (\delta 2)\delta }\frac{1q^2}{2}z_0^{\mathrm{}}f_\nu ^{(j)}(s)sJ_0^{(j)}((1q^2)q^{1\delta }zs;q^2)𝑑s.$$

Due to (3.7) - (3.9) we can write

$$_0^{\mathrm{}}f_\nu ^{(j)}(s)s^2J_1^{(j)}((1q^2)q^{\frac{\delta }{2}}zs;q^2)𝑑sq^{2\nu +1}_0^{\mathrm{}}f_\nu ^{(j)}(s)s^2J_1^{(j)}((1q^2)q^{1\frac{\delta }{2}}zs;q^2)𝑑s=$$

$$=q^{\nu (\delta 2)\frac{\delta }{2}}\frac{1q^2}{2}s_0^{\mathrm{}}f_\nu ^{(j)}(s)sJ_0^{(j)}((1q^2)q^{1\delta }zs;q^2)𝑑s$$

or

$$_0^{\mathrm{}}f_\nu ^{(j)}(s)s^{2\nu +2}\frac{2_s}{1+q}[s^{2\nu +1}J_1^{(j)}((1q^2)q^{\frac{\delta }{2}}zs;q^2)]𝑑s=$$

$$=q^{\nu (\delta 2)}_0^{\mathrm{}}f_\nu ^{(j)}(s)\frac{2_s}{1+q}J_1^{(j)}((1q^2)q^{\frac{\delta }{2}}zs;q^2)𝑑s.$$

Using (3.12) we obtain

$$_0^{\mathrm{}}_s(f_\nu ^{(j)}(s)s^{2\nu +2})q^{2\nu +1}s^{2\nu +1}J_1^{(j)}((1q^2)q^{1\frac{\delta }{2}}zs;q^2)ds=$$

$$=q^{\nu (\delta 2)}_0^{\mathrm{}}_sf_\nu ^{(j)}(s)qsJ_1^{(j)}((1q^2)q^{1\frac{\delta }{2}}zs;q^2)ds.$$

Thus we come to the difference equation for $`f_\nu ^{(j)}(s)`$

$$q^{\delta \nu }s^2[f_\nu ^{(j)}(s)+q^{2\nu +2}f_\nu ^{(j)}(qs)]=f_\nu ^{(j)}(s)f_\nu ^{(j)}(qs).$$
(4.4)
It follows from Proposition 3.1 the function

$$f_\nu ^{(j)}(s)=\frac{(q^{2\nu +2\delta \nu }s^2,q^2)_{\mathrm{}}}{(q^{\delta \nu }s^2,q^2)_{\mathrm{}}}$$
(4.5)
satisfies to (4.4), and it follows from (3.4) integral (4.2) is absolutely convergent.

As $`S^{(j)}(z)(z/2)^\nu `$ is a solution to (2.8) it can be represented as

$$S^{(j)}(z)(z/2)^\nu =AI_\nu ^{(j)}((1q^2)z;q^2)+BK_\nu ^{(j)}((1q^2)z;q^2).$$
(4.6)
Let $`j=1`$. As it follows from  $`I_\nu ^{(1)}((1q^2)z;q^2)`$ is a meromorphic function with the ordinary poles $`z=\pm \frac{2q^r}{1q^2},r=0,1,\mathrm{}`$, and $`K_\nu ^{(1)}((1q^2)z;q^2)`$ and the left side of (4.6) are the holomorphic functions in region $`\mathrm{Re}z>0`$.

Let $`j=2,3`$. It is easily to show (see ) that $`lim_z\mathrm{}I_\nu ^{(j)}((1q^2)z;q^2)=\mathrm{},lim_z\mathrm{}K_\nu ^{(j)}((1q^2)z;q^2)=0`$ and the left side of (4.6) tends to zero if $`z\mathrm{}`$.

So for any $`j=1,2,3A=0`$. Multiplying the both sides of (4.6) on $`(z/2)^\nu `$ and putting $`z=0`$ we obtain from (2.9) and (2.5) - (2.7)

$$_0^{\mathrm{}}\frac{(q^{2\nu +2\delta \nu }s^2,q^2)_{\mathrm{}}}{(q^{\delta \nu }s^2,q^2)_{\mathrm{}}}s𝑑s=\frac{B}{2}q^{\nu ^2+\nu }\mathrm{\Gamma }_{q^2}(\nu )A_\nu ^{|1\delta |}.$$
(4.7)
Now calculate the integral in the left side of (4.7).

$$_0^{\mathrm{}}\frac{(q^{2\nu +2\delta \nu }s^2,q^2)_{\mathrm{}}}{(q^{\delta \nu }s^2,q^2)_{\mathrm{}}}s𝑑s=\frac{q^{\delta \nu }}{2}_0^{\mathrm{}}\frac{(q_1^{\nu +1}x,q_1)_{\mathrm{}}}{(x,q_1)_{\mathrm{}}}𝑑x=\frac{q^{\delta \nu }}{2}_0^{\mathrm{}}e_{q_1}(x)E_{q_1}(q_1^{\nu +1}x)𝑑x,$$

where $`x=q^{\delta \nu }s^2`$ and $`q_1=q^2`$ .

Note, that

$$_xe_{q_1}(x)=\frac{1}{1q_1}e_{q_1}(x),_xE_{q_1}(q_1^{\nu +1}x)=\frac{q_1^{\nu +1}}{1q_1}E_{q_1}(q_1^{\nu +2}x).$$

Using Lemma 3.2 we obtain

$$_0^{\mathrm{}}e_{q_1}(x)E_{q_1}(q_1^{\nu +1}x)𝑑x=\mathrm{ln}q_1+q_1^\nu _0^{\mathrm{}}e_{q_1}(x)E_{q_1}(q_1^{\nu +1}x)𝑑x.$$

So

$$_0^{\mathrm{}}e_{q_1}(x)E_{q_1}(q_1^{\nu +1}x)𝑑x=\frac{\mathrm{ln}q_1}{1q_1^\nu },$$

and we have

$$_0^{\mathrm{}}\frac{(q^{2\nu +2\delta \nu }s^2,q^2)_{\mathrm{}}}{(q^{\delta \nu }s^2,q^2)_{\mathrm{}}}s𝑑s=\frac{q^{\delta \nu }\mathrm{ln}q}{1q^{2\nu }}.$$
(4.8)
It follows from (4.8) that

$$B=\frac{2q^{\nu ^2\nu (1\delta )}\mathrm{ln}q}{(1q^2)\mathrm{\Gamma }_{q^2}(\nu +1)A_\nu ^{|1\delta |}},$$

and we have (4.1).

###### Remark 4.1

It follows from \[2, Remark 5.1\] $`A_\nu 1`$ if $`q10`$, and it follows from Remark 3.1 that if $`q10`$ we come to the classical integral representation of Bessel-Macdonald function

$$K_\nu (z)=\mathrm{\Gamma }(\nu +1)\left(\frac{z}{2}\right)^\nu _0^{\mathrm{}}(1+s^2)^{\nu 1}sJ_0(zs)𝑑s.$$

## 5 The representation of the $`q`$-BMFs by a double integral

We take $`z,s𝐂`$ in this section.

Consider function

$$\xi _\eta ^{(\delta )}(s)=\underset{n=0}{\overset{\mathrm{}}{}}\frac{q^{(2\delta )\eta n^2}(1q^2)^n}{(q^2,q^2)_n}s^n,\eta 0.$$
(5.1)
Obviously this series converges for any $`s`$ if $`(2\delta )\eta >0`$ and for $`|s|<\frac{1}{1q^2}`$ if $`(2\delta )\eta =0`$. Consider three cases.
1. $`\eta =0.`$ It follows from (5.1)

$$\xi _0^{(\delta )}(s)=e_{q^2}((1q^2)s),\delta =2,0,1.$$
(5.2)
2. $`\eta =1.`$

$$\xi _1^{(\delta )}(s)=\{\begin{array}{ccc}e_{q^2}((1q^2)s)\hfill & \mathrm{for}& \delta =2\hfill \\ E_{q^2}((1q^2)qs)\hfill & \mathrm{for}& \delta =0\hfill \\ {}_{1}{}^{}\mathrm{\Phi }_{1}^{}(0;q;q,(1q^2)q^{\frac{1}{2}}s)\hfill & \mathrm{for}& \delta =1.\hfill \end{array}$$
(5.3)
3. $`\eta =\frac{1}{2}`$. It follows from (5.1)

$$\xi _{\frac{1}{2}}^{(\delta )}(s)=\{\begin{array}{ccc}e_{q^2}((1q^2)s)\hfill & \mathrm{for}& \delta =2\hfill \\ {}_{1}{}^{}\mathrm{\Phi }_{1}^{}(0;q;q,(1q^2)q^{\frac{1}{2}}s)\hfill & \mathrm{for}& \delta =0.\hfill \\ {}_{3}{}^{}\mathrm{\Phi }_{3}^{}(0,0,0;q^{\frac{1}{2}},iq^{\frac{1}{2}},iq^{\frac{1}{2}};q^{\frac{1}{2}},(1q^2)q^{\frac{1}{4}}s)\hfill & \mathrm{for}& \delta =1.\hfill \end{array}$$
(5.4)
Assume $`s=\rho e^{i\varphi },z=re^{i\psi }`$, and consider integral

$$J(r\rho )=_\pi ^\pi \xi _\eta ^{(\delta )}(ir\rho e^{i(\psi +\varphi )})\xi _{1\eta }^{(\delta )}(ir\rho e^{i(\psi +\varphi )})𝑑\varphi .$$
(5.5)
Let $`\delta <2,\eta =\frac{1}{2}`$. In this case we can calculate this integral term by term.

$$J(r\rho )=_\pi ^\pi \underset{n=0}{\overset{\mathrm{}}{}}\frac{q^{(2\delta )\frac{n^2}{2}}(1q^2)^n}{(q^2,q^2)_n}(ir\rho )^ne^{in\varphi }\underset{m=0}{\overset{\mathrm{}}{}}\frac{q^{(2\delta )\frac{m^2}{2}}(1q^2)^m}{(q^2,q^2)_m}(ir\rho )^me^{im\varphi }d\varphi =$$

$$=\underset{n=0}{\overset{\mathrm{}}{}}\frac{q^{(2\delta )\frac{n^2}{2}}(1q^2)^n}{(q^2,q^2)_n}(ir\rho )^n\underset{m=0}{\overset{\mathrm{}}{}}\frac{q^{(2\delta )\frac{m^2}{2}}(1q^2)^m}{(q^2,q^2)_m}(ir\rho )^m_0^{2\pi }e^{i(mn)\varphi }𝑑\varphi =$$

$$=2\pi \underset{n=0}{\overset{\mathrm{}}{}}(1)^n\frac{q^{(2\delta )n^2}(1q^2)^{2n}}{(q^2,q^2)_n^2}(r\rho )^{2n}.$$

It follows from (3.6) the last series is $`q^2`$-Bessel function and we have

$$J_0^{(j)}((1q^2)2r\rho ;q^2)=\frac{1}{2\pi }_\pi ^\pi \xi _{\frac{1}{2}}^{(\delta )}(ir\rho e^{i(\psi +\varphi )})\xi _{\frac{1}{2}}^{(\delta )}(ir\rho e^{i(\psi +\varphi )})𝑑\varphi ,$$
(5.6)
where $`\xi _{\frac{1}{2}}^{(\delta )}`$ is defined by (5.4) and $`j=2,3`$ are connected with $`\delta =0,1`$ by relations (2.4).

Let $`\delta <2`$ and $`\eta =0`$. Then we have the same result for $`r\rho <\frac{1}{1q^2}`$, e.i.

$$J_0^{(j)}((1q^2)2r\rho ;q^2)=\frac{1}{2\pi }_\pi ^\pi e_{q^2}(i(1q^2)r\rho e^{i(\psi +\varphi )})\xi _1^{(\delta })(ir\rho e^{i(\psi +\varphi )})d\varphi ,$$
(5.7)
where $`\xi _1^{(de)}`$ is defined by (5.3). The left side is a holomorphic function outside a neighborhood of zero, and so we can consider $`J_0^{(j)}((1q^2)2r\rho ;q^2),j=2,3`$ as the analytic continuation of (5.8).

Let $`\delta =2`$. It follows from (5.2) - (5.6) for $`r\rho <\frac{1}{1q^2}`$

$$J_0^{(1)}((1q^2)2r\rho ;q^2)=\frac{1}{2\pi }_\pi ^\pi e_{q^2}(i(1q^2)r\rho e^{i(\psi +\varphi )})e_{q^2}(i(1q^2)r\rho e^{i(\psi +\varphi )})𝑑\varphi .$$
(5.8)
In this case the both sides of (5.8) are the meromorphic functions with the ordinary poles in points $`r\rho =\pm \frac{iq^k}{1q^2}`$. So we will consider $`J_0^{(1)}((1q^2)2r\rho ;q^2)`$ as a analytic continuation of (5.8).

Now we can formulate

###### Proposition 5.1

The $`q`$-BMF can be represented by double integral

$$K\nu ^{(j)}(2(1q^2)|z|,q^2)=\frac{q^{\nu ^2+\nu (1\delta )}(1q^2)}{8\pi \mathrm{ln}q}\mathrm{\Gamma }_{q^2}(\nu +1)A_\nu ^{|1\delta |}|z|^\nu \times $$
(5.9)
$$\times \frac{(q^{2\nu +2\delta \nu }\overline{s}s,q^2)_{\mathrm{}}}{(q^{\delta \nu }\overline{s}s,q^2)_{\mathrm{}}}e_{q^2}(i(1q^2)\overline{z}\overline{s})\xi _1^{(\delta )}(izs)d\overline{s}ds$$

or

$$K\nu ^{(j)}(2(1q^2)|z|,q^2)=\frac{q^{\nu ^2+\nu (1\delta )}(1q^2)}{8\pi \mathrm{ln}q}\mathrm{\Gamma }_{q^2}(\nu +1)A_\nu ^{|1\delta |}|z|^\nu \times $$
(5.10)
$$\times \frac{(q^{2\nu +2\delta \nu }\overline{s}s,q^2)_{\mathrm{}}}{(q^{\delta \nu }\overline{s}s,q^2)_{\mathrm{}}}\xi _{\frac{1}{2}}^{(\delta )}(i\overline{z}\overline{s})\xi _{\frac{1}{2}}^{(\delta )}(izs)d\overline{s}ds,$$

where $`\xi _\eta ^{(\delta )}`$ are defined by (5.2) - (5.4), the constant $`A_\nu `$ is defined by (2.10) and $`j=1,2,3`$ are connected with $`\delta =2,0,1`$ by relations (2.4).

Proof. Substituting (5.6) - (5.8) in (4.1) we obtain (5.9) or (5.10) respectively.

###### Remark 5.1

It ie easily to show that if $`q10`$ the all functions (5.2) - (5.4) tend to the usual exponential $`e^s`$, and we come to the classical integral representation of Bessel-Macdonald function

$$K_\nu (2\sqrt{\overline{z}z})=\mathrm{\Gamma }(\nu +1)(\sqrt{\overline{z}z})^\nu (1+\overline{s}s)^{\nu 1}\mathrm{exp}(i(\overline{z}\overline{s}+zs))𝑑\overline{s}𝑑s.$$