Jimmy Lominé
email: jlomine@rockwellcollins.com

Christophe Morlaas

Hervé Aubert

Herve Aubert

Novel Vector Sensors Design with Three Co-located or Distributed Elements for the 3D DoA Estimation

In this paper, two novel vector sensors using a reduced number of radiating elements are proposed to estimate the directions of arrival of incoming electromagnetic signals in the 3D space, azimuth and elevation angles. The first one uses co-located radiating elements while the other one is based on distributed antenna elements. These two sensors combine only two half-loops and one linear monopole placed on a metallic plate in view of embedded applications. Full wave electromagnetic simulations are performed to take into account the electromagnetic coupling effects between the antenna elements. The directions of arrival estimation accuracy of electromagnetic signals incoming in arbitrary directions in the full 3D space are computed from the MUSIC algorithm. For experimental validation purpose, a prototype is manufactured and the directions of arrival measurements are performed. Then a novel vector sensor design with a reduced number of antenna elements is presented. The antenna elements are spatially distributed. An analysis is carried out to determine the largest distance between the antenna elements without causing ambiguous estimations in the 3D space. The estimation accuracy of the resulting sensor is reported. Finally the performances of these two vector sensors are compared.

INTRODUCTION

The direction of arrival (DoA) estimation is present in different applications such as radar, radio astronomy, sonar and navigation [START_REF] Tuncer | Classical and Modern Direction-of-arrival Estimation[END_REF][START_REF] Gething | Radio Direction Finding and Superresolution[END_REF]. The purpose is to estimate the DoA of incoming electromagnetic (EM) signals transmitting by sources located at unknown positions. It can be used for defense applications by detecting and localizing enemy transmissions or for civil applications by finding emergency beacons for Search And Rescue (SAR). In order to determine the DoA of incoming EM signals, two strategies are usually applied: the use of the spatial diversity [START_REF] Gething | Radio Direction Finding and Superresolution[END_REF] and the use of the polarization diversity [START_REF] Hatke | Conditions for unambiguous source location using polarization diverse arrays[END_REF]. A combination of these two well-known techniques could also be performed [START_REF] Lo Monte | Distributed 6D vector antennas design for direction of arrival applications[END_REF][START_REF] Lo Monte | Design and realization of a distributed vector sensor for polarization diversity applications[END_REF][START_REF] Sun | Distributed vector sensor cross product added with music for direction of arrival estimation[END_REF][START_REF] Chabory | Efficiency characterization of vector-sensor antennas with distributed elements for 3D direction finding[END_REF][START_REF] See | Source localization with distributed electromagnetic component sensor array processing[END_REF][START_REF] Wong | vector cross-product direction-finding' with an electromagnetic vectorsensor of six orthogonally oriented but spatially noncollocating dipoles/loops[END_REF]. Nowadays many direction finding algorithms use the spatial diversity such as interferometry [START_REF] Malloy | Analysis and synthesis of general planar interferometer arrays[END_REF], which consists of measuring the phase differences between radiating elements of the sensor when it is illuminated by an incoming EM signals. In principle this approach can be applied to the 3D DoA estimation but the design of the sensors is not easy when it is applied to DoA in the full 3D space. The application of the polarization diversity requires smaller sensors because it does not need a minimum distance between radiating elements to estimate the DoA of incoming signals [START_REF] Nehorai | Vector-sensor array processing for electromagnetic source localization[END_REF]. The DoA is estimated through the measurement of the EM field components of the incoming signal. The spatial distribution, combined with the diversity of polarization, has the advantage to improve the accuracy of the DoA estimation [START_REF] See | Source localization with distributed electromagnetic component sensor array processing[END_REF] and also, to decrease the undesirable mutual coupling between the antenna elements [START_REF] Wong | vector cross-product direction-finding' with an electromagnetic vectorsensor of six orthogonally oriented but spatially noncollocating dipoles/loops[END_REF]. Following [START_REF] Hatke | Conditions for unambiguous source location using polarization diverse arrays[END_REF] the polarization diversity can be applied by using a vector sensor of six co-located antenna elements, such as three orthogonal electric dipoles and three orthogonal magnetic dipoles [START_REF] Nehorai | Vector-sensor array processing for electromagnetic source localization[END_REF], in order to measure the six components of the incoming EM field.

For vector sensors embedded on vehicles, the metallic objects that surrender the antennas can alter the measurement of the field components. However, the measurement of less than six components can be sufficient to estimate the DoA of an incoming transverse magnetic (TM) signal from regions that are not hidden by the surrounding metallic objects. Thus only three co-located antenna elements combining two orthogonal magnetic dipoles and one electric dipole may be sufficient for the DoA estimation of TM incoming signals from the upper half-space [START_REF] Yuan | Various compositions to form a triad of collocated dipoles/loops, for direction finding and polarization esitmation[END_REF][START_REF] Hirari | DoA estimation using blind separation of sources[END_REF][START_REF] Mir | Source localization using airborne vector sensors[END_REF][START_REF] Mir | Passive direction finding using airborne vector sensors in the presence of manifold perturbations[END_REF][START_REF] Wong | Inexpensive upgrade of base-station dumb antennas by two magnetic loops for 'blind' adaptive downlink beamforming[END_REF][START_REF] Lominé | Method for vector sensor design based on a spherical mode approach for 3D DoA estimation[END_REF][START_REF] Appadwedula | Direction-finding results for a vector sensor antenna on a small UAV[END_REF]. However, to the authors' knowledge, no vector sensor using only three distributed antenna elements for polarization diversity applied to the 3D DoA estimation (azimuth and elevation angles) has been reported yet. Very recently Slater et al. [START_REF] Slater | Demonstration of an electrically small antenna array for UHF direction-of-arrival esitmation[END_REF] have investigated a vector sensor design with linearly distributed elements but only the 2D DoA estimation (azimuth angles only) has been reported.

In this paper two compact sensors combining only three dipoles are proposed for the 3D DoA estimation (azimuth and elevation angles). The first one (sensor A) uses co-located radiating elements while the second one (sensor B) combines distributed antenna elements. These two sensors incorporate two orthogonal loops and one dipole placed on a metallic plate in view of embedded applications. The DoA accuracy is computed and measured using the MUltiple SIgnal Classification (MUSIC) algorithm reported in [START_REF] Schmidt | Multiple emitter location and signal parameter estimation[END_REF].

This article is organized as follows. The Section 2 introduces the electromagnetic analysis of vector sensor using a reduced number of antenna elements. The design of a vector sensor with co-located radiating elements is reported in the Section 3 and the DoA accuracy is computed. This accuracy is measured in an anechoic chamber to validate the simulation approach. An original compact vector sensor using only three distributed antennas is proposed in the Section 4. A criterion based on the orthogonality between the signal and noise subspaces is proposed to determine the largest separation distance between constitutive elements of the sensor without causing ambiguous estimations. Finally the DoA accuracy obtained with the proposed sensors are compared.

DATA MODEL OF THE VECTOR SENSOR COMBINING TWO MAGNETIC DIPOLES AND ONE ELECTRIC DIPOLE

The analysis of a vector sensor combining six antenna elements is presented. From this analysis the data model of the sensor with a reduced number of radiating elements, combining only two magnetic dipoles and one electric dipole, is derived and the DoA estimation of incoming EM waves is introduced. In this section, mutual coupling between the antenna elements is neglected.

Data Model of a Vector Sensor Measuring the Six Components of the Incoming EM Fields

When the polarization diversity approach is applied to determine the DoA of an incoming signal, a vector sensor is generally used to simultaneously measure the six components of the EM field. Theoretically these components can be measured by using three orthogonal magnetic dipoles and three orthogonal electric dipoles. The data model of such vector sensor is given as follows [START_REF] Nehorai | Vector-sensor array processing for electromagnetic source localization[END_REF]:

       E x (φ, θ, γ, η) E y (φ, θ, γ, η) E z (φ, θ, γ, η) H x (φ, θ, γ, η) H y (φ, θ, γ, η) H z (φ, θ, γ, η)        A(φ,θ,γ,η) =        cos φ cos θ -sin φ sin φ cos θ cos φ -sin θ 0 -sin φ -cos φ cos θ cos φ -sin φ cos θ 0 sin θ        g(φ,θ) × sin γe jη cos γ p(γ,η)           e -j k(φ,θ).
r Ex e -j k(φ,θ). r Ey e -j k(φ,θ). r Ez e -j k(φ,θ). r Hx e -j k(φ,θ). r Hy e -j k(φ,θ). r Hz

          d(φ,θ) (1)
where E x , E y and E z denote to the three components of the electric field and, H x , H y and H z denote to the three components of the magnetic field in the Cartesian (XY Z) coordinate system. A (φ, θ, γ, η) is called the steering vector. Each component depends on the azimuth angle φ ∈ [0; 2π], the elevation angle θ ∈ [0; π/2] (refer to Figure 1 for the definition of the azimuth and elevation angles) and the

E x E z y H x E y H z H y z x u θ v k(φ,θ) φ Figure 1.
Vector sensor representation with three magnetic dipoles and three electric dipoles (φ: azimuth angle; θ: elevation angle). polarization vector p (γ, η). In the (u, v) polarization plane, orthogonal to the free space wave vector k (φ, θ) (see Figure 1), the electric field is defined as follows:

E(t) = E 0 sin(γ) cos wt -k • r • û + E 0 cos(γ) cos wt -k • r + η • v (2)
where E 0 is the norm of the field vector E(t), γ ∈ [0; π/2] denotes the auxiliary polarization angle, η ∈ [-π; π] denotes the polarization phase difference and w the radial frequency. Thus the polarization vector p is defined in terms of two angles: γ and η. The angles φ and θ define the DoA of the incoming EM signal and consequently denote the angles to be derived from the measurement of all field components by the vector sensor. This derivation may be performed using specific direction finding algorithms such as MUSIC [START_REF] Schmidt | Multiple emitter location and signal parameter estimation[END_REF] or ESPRIT [START_REF] Roy | ESPRIT-estimation of signal parameters via rotational invariance techniques[END_REF]. The operator in Eq. ( 1) denotes the elementwise multiplication operator and d(φ, θ) designates the spatial phase shift vector due to an eventual spatial distribution of the radiating elements. This vector depends on the free space wave vector k (φ, θ) of the incoming EM wave and the vector position r i of the ith antenna elements. If the vector sensor is placed on the surface of a metallic support, some electromagnetic field components cannot be measured.

Data Model of a Vector Sensor Measuring the E z , H x and H y Components of the Incoming EM Fields

When a sensor is located on the surface of a metallic plate in the xOy plane, the components E x , E y and H z cannot be measured on this surface. Thus the vector sensor consists only of a combination of two magnetic dipoles, one to measure the component H x and the other to measure the component H y , and one electric dipole to measure the component E z . The data model Eq. ( 1) can then be reduced to:

E z (φ, θ, γ, η) H x (φ, θ, γ, η) H y (φ, θ, γ, η) Ar(φ,θ,γ,η) = -sin θ 0 -sin φ -cos φ cos θ cos φ -sin φ cos θ gr(φ,θ) ×p(γ, η)    e -j k(φ,θ). r Ez e -j k(φ,θ). r Hx e -j k(φ,θ). r Hy    dr(φ,θ) (3)
If the incoming EM waves are transverse electric (TE) (η = 0 and γ = 0) or transverse magnetic (TM) (η = 0 and γ = π/2), the data model can be reduced to Eq. ( 4) and Eq. ( 5) respectively as shown in [START_REF] Appadwedula | Direction-finding results for a vector sensor antenna on a small UAV[END_REF]:

A TE (φ, θ) = 0 -cos φ cos θ -sin φ cos θ d r (φ, θ) (4) A TM (φ, θ) = -sin θ -sin φ cos φ d r (φ, θ) (5)
where A TE and A TM denote the steering vector of the reduced vector sensor in the case of the horizontal and the vertical polarization, respectively. In this paper, only incoming EM signals with vertical polarization are considered, and consequently A(φ, θ, γ, η) = A TM (φ, θ). The dipole will be used to estimate the elevation angles of the DoA and the two loops will be used to estimate the azimuth angles. This data model does not allow the computation of the Poynting vector of the incoming EM field because the components E x , E y and H z are not measured. Consequently a DoA direction finding algorithm based on the Poynting vector is not applicable in this case.

In this paper, the MUSIC algorithm is used to estimate the DoA of a vertically-polarized incoming EM signals from the data model:

X(φ, θ, γ, η, t) = A(φ, θ, γ, η)S(t) + n(t) (6)
where X (φ, θ, γ, η, t) is the measured snapshots at the sensor ports, S(t) the incoming EM signal and n(t) the uncorrelated noise assumed to be gaussian with a zero-mean and a variance σ 2 . This algorithm is based on the concept of signal and noise subspaces [START_REF] Schmidt | Multiple emitter location and signal parameter estimation[END_REF]. The noise subspace is derived from the eigenvalue decomposition from the covariance matrix of the snapshots X (φ, θ, γ, η, t). Then the signal subspaces are projected on the noise subspace, and the DoA angle is determined by the lowest projection value which is caused by the orthogonality between both subspaces. The quality of the noise subspace computation and consequently the accuracy of the DoA estimation, depend on the number of snapshots and the noise level [START_REF] Chandran | Advances in Direction-of-arrival Estimation[END_REF]. The signal-to-noise ratio (SNR) at each antenna input port varies according to the amplitude variation of each field component in the full 3D space. Therefore, a reference signal-to-noise ratio (RSNR) for an arbitrary direction (φ ref = 0 • , θ ref = 0 • , in this paper) and for only one antenna input port is defined to compute the receiver noise power P N as follows:

P N = X (i) (φ ref , θ ref , t) 2 /RSNR (7)
where X (i) (φ, θ, t) denotes the ith element of the vector X (φ, θ, t) and RSNR the reference signal-tonoise ratio. For a given P N the SNR at each antenna port can be deduced as follows:

SNR (i) (φ, θ, t) = |X (i) (φ, θ, t)| 2 /P N ( 8
)
where SNR (i) (φ, θ, t) denotes the signal-to-noise ratio at the ith antenna input port for the DoA (φ, θ).

In this paper, the selected port is the loop port used to measure the H y component.

SENSOR A: THREE CO-LOCATED ANTENNA ELEMENTS FOR MEASURING E z , H x AND H y

The vector sensor A combines two loops and one linear dipole to measure the components E z , H x and H y . For this sensor, the antenna elements are co-located and consequently d r (φ, θ) is a unit vector.

DoA Estimation Results through Analytic Approach

A first simulation of DoA estimation is performed by neglecting the EM coupling between radiating elements. The closed-form equations of elementary dipoles radiation are used in this simulation to compute the signal received at each antenna input port. The incoming signals are assumed to be incident plane waves. The RSNR is set to 15 dB. A number (N ) of 100 snapshots has been used in the MUSIC algorithm. Moreover the average of the estimation accuracy has been obtained by using a number (IT ) of 100 estimations per DoA. Various angles of arrival of incoming signals have been selected between 45 • and 135 • in azimuth to assess the DoA estimation errors. Outside this angular range, the accuracy can be predicted due to the symmetry of the sensor geometry. The simulation results are shown in Table 1.

The accuracy of the DoA estimation is excellent for azimuth angles due to the absence of EM coupling between the antenna elements. However the estimation error of the elevation angle reaches 5 • when θ is close to 90 • . This error is intrinsic to the sensor A because θ is estimated mainly from

• 20 • 0 • 0 • 95 • 40 • 0 • 0.35 • 130 • 60 • 0 • 1.2 • 45 • 80 • 0 • 5 •
the knowledge of the E z component (see the steering vector A TM ). In Figure 2, the variation of A TM according to θ is analyzed through the power P r (θ) received by the electric dipole and computed from [START_REF] Wong | vector cross-product direction-finding' with an electromagnetic vectorsensor of six orthogonally oriented but spatially noncollocating dipoles/loops[END_REF].

P r (θ) = 20 log   A (1) TM (θ) max A (1) TM (θ)   (9)
where (1) denotes the first component of the steering vector A TM . In the angular range from θ = 60 • to θ = 90 • , the maximum dynamic of the received power is 1.25 dB while it is 11.3 dB for the elevation angles included between θ = 10 • and θ = 40 • . The higher the variation in an angular range, the higher the accuracy of the estimation. It correlates with the results given in Table 1. Beside, as shown in Figure 2, the SNR decreases for θ lower than 10 • and consequently the DoA estimation deteriorates. In pratice eventual sensor anomalies or mutual coupling between dipoles may affect the DoA estimation accuracy. To take into account these effects, full wave electromagnetic simulations have been performed and the results are reported in Section 3.3.

Antenna Design

The vector sensor A, shown in Figure 3 has been modeled and simulated with the electromagnetic simulation software HFSS. The operating frequency has been set to 2.8 GHz. The sensor dimensions are given in Figure 5 and in Table 2. The antenna elements are printed on double layers FR4 PCB with a thickness of 1.5 mm, a relative permittivity r = 4.4 and a loss tangent of 0.02. The double layers PCB used for the horizontal support is the ROGER4003 with a thickness of 1.542 mm, r = 3.55 and loss tangent of 0.0027. A metallic disc is placed at the bottom of the sensor A in view of embedded applications. Its diameter is fixed to 300 mm (≈ 2.8λ). This metallic plate allows to reduce the size of the antenna elements by using the image theory (the loops are replaced by half-loops and the dipole by a monopole). Capacitive effects are performed to increase the electric length of the radiating elements and to get the impedance matching as shown in Figure 4. The loop feeding is performed through a coupling effect between the metallic plate A connected to the SMA connector E and the loop D. This coupling effect allows to set the antenna input impedance. A second capacitive effect, between the plates B and C, is used to adjust the resonant frequency at the required value. Since the half-loops are printed on a double PCB layers, the same process is applied to the other half-loops extremity. A phase shift of π is applied to the opposite feeding to generate a constant current distribution all along the half-loops. For the monopole G, there are two capacitive effects. The first one is in parallel to the feeding port connected to the SMA connector H. It uses to adjust the impedance matching. It is performed through the coupling between the metallic plates F and C. The second one is located at the end of the monopole with the metallic disc I. It uses to increase the electric length of the radiating element. All antenna elements are connected together at the point indicated in Figure 3.

DoA Estimation Results through Full Wave Electromagnetic Simulations

In order to estimate the DoA of incoming EM signals in the presence of the EM coupling between antenna elements, incident plane waves have been considered by using full wave electromagnetic simulations. The resulting steering vectors have been extracted and imported into the MUSIC algorithm. A gaussian noise is added to these data to create the snapshots X (φ, θ, γ, η, t). The eventual EM coupling between the sensor antennas can alter the estimation accuracy. These effects have to be compensated with a calibration process [START_REF] Lemma | Experimental analysis of antenna coupling for high-resolution DoA estimation algorithms[END_REF]. Several calibration methods have been proposed in litterature [START_REF] Lemma | Experimental analysis of antenna coupling for high-resolution DoA estimation algorithms[END_REF][START_REF] Wang | Mutual coupling calibration for electromagnetic vector sensor array[END_REF][START_REF] Khallaayoun | A blind iterative calibration method for high resolution DoA estimation[END_REF]. In this work, it is directly performed through full wave electromagnetic simulations. The sensor is illuminated by an incident plane wave for each direction in the 3D half-space. An angular step of 5 • in azimuth and elevation has been chosen for limiting the use of high memory ressources. For each DoA, the steering vector is extracted and stored in a matrix, called "calibration matrix". The eventual amplitude and phase distortions are taken into account by substituting the antenna model used in the MUSIC algorithm by the calibration matrix. Thus the calibration process is ideal for the DoA estimation through full wave electromagnetic simulations.

The estimation configuration in the MUSIC algorithm are: RSNR = 15 dB, N = 100 and IT = 100. The considered DoA of the incoming waves are those used in the analytic approach. The simulation results, given in Table 3, indicate that the sensor A allows estimating the DoA with an error of 4.8 • . This DoA estimation error is due to the lack of dynamics of the power received at the monopole port as explained in the Section 3.1. The error is low and close to the theoretical prediction indicated in Table 1. The estimation of the DoA (φ, θ) = (55 • , 20 • ) is performed with an error of 1.7 • . This is explained by a low SNR value at the monopole input port due to the low levels of the received signals for this elevation angle. This field attenuation is increased in the presence of the metallic plate: this plate alters the received field in this DoA as shown in the simulated radiation patterns in Figure 7. Thus the estimation of the elevation angles is less robust to the noise in this area. In these graphs, the elevation angles are on the radial axis and the azimuth angles on the circular axis.

• 20 • 0.8 • 1.7 • 95 • 40 • 0.05 • 0.5 • 130 • 60 • 0.2 • 0.4 • 45 • 80 • 2.1 • 4.8 •

DoA Estimation Results through Experimentations

The purpose of these experimentations is to validate the design methodology and the simulation results relative to the sensor A. A prototype of the sensor A, with an operating frequency set to 2.8 GHz, has been manufactured for this experimental validation as shown in Figure 6. The measurements are performed in an anechoic chamber. The calibration matrix obtained from the full wave electromagnetic simulation derived in the Section 3.3 is used into the MUSIC algorithm for this experimentation. In this case, the calibration process is no more ideal because the calibration matrix is determined from simulations and not from measurement. The DoA estimation is firstly performed by mean of full wave electromagnetic simulation. The corresponding results are summerized in the Table 4. Then the measurement of the DoA estimation is reported in Table 5. Both estimations are performed with the same configuration: RSNR = 30 dB, N = 1 and IT = 100. The simulation and measurement results are in good agreement. The highest errors are obtained for the same directions of arrival. The maximum measured errors of the DoA estimation are 9.2 • in azimuth and 7.5 • in elevation for (φ, θ) = (55 • , 20 • ). The estimation of the DoA (φ, θ) = (55 • , 20 • ) and (φ, θ) = (45 • , 80 • ) are not accurate, as expected from the simulation results. These errors are due to the low SNR in these directions. The measured radiation patterns are in good agreement with the simulated ones as shown in Figure 7. In these graphs, the elevation angles are on the radial axis and the azimuth angles on the circular axis. To improve the estimation accuracy in these DoA, the number of snapshots has to be increased (see Table 3). For the DoA (φ, θ) = (95 • , 40 • ) and (φ, θ) = (130 • , 60 • ), the estimation accuracy is close to the simulation results with an error lower than 5 • by measurement and 2.75 • by simulation. This small difference of accuracy is due to amplitude and phase distortions not taken into account in the simulated calibration matrix.

• 20 • 9.2 • 7.5 • 95 • 40 • 2.3 • 5 • 130 • 60 • 3.6 • 1.6 • 45 • 80 • 7.6 • 2.8 • (a) (b) (c) (d) (e) (f)

SENSOR B: THREE DISTRIBUTED ANTENNA ELEMENTS FOR MEASURING E z , H x AND H y

In this section a vector sensor, called sensor B, with distributed antenna elements (i.e., not co-located) is proposed as shown in Figure 8. Compared with the co-located configuration of the sensor A, the spatial distribution of the radiating elements provides an additionnal phase shift at the antenna ports. This phase shift depends on the DoA of the incoming EM waves but also on the position of each antenna elements of the vector sensor. According to the electrical separation distance between the antenna elements and to the array geometry, some DoA estimations can be ambiguous. Thus to design the sensor B, a process allowing to spot ambiguous angles had to be implemented.

Ambiguity Analysis Process

The presence of ambiguous angles means that at least two steering vectors associated with two different DoA are orthogonal to the noise vector subspace [START_REF] Tan | Ambiguity in MUSIC and ESPRIT for direction of arrival estimation[END_REF]. The MUSIC algorithm computes the orthogonality between the signal vector subspaces and the noise vector subspace to estimate the DoA [START_REF] Schmidt | Multiple emitter location and signal parameter estimation[END_REF]. Thus this algorithm cannot distinguished two DoA with coplanar steering vectors. Before designing an antenna array applied to the DoA estimation, an analysis has to be carried out in order to define the largest separation distance between the antenna elements without causing ambiguous estimations. The angle between two steering vectors can be used as criterion to spot these ambiguities [START_REF] Eric | Ambiguity characterization of arbitrary antenna array: Type I ambiguity[END_REF][START_REF] Spielman | Performance analysis of the MUSIC algorithm[END_REF]. This angle is given by:

α(φ 1 , θ 1 , φ 2 , θ 2 ) = cos -1 |A r (φ 1 , θ 1 ) * • A r (φ 2 , θ 2 )| ||A r (φ 1 , θ 1 )|| • ||A r (φ 2 , θ 2 )|| (10)
where α ∈ [0; π/2] denotes the angle (modulo π/2) between the two steering vectors A r (φ 1 , θ 1 ) and A r (φ 2 , θ 2 ). Two coplanar steering vectors give α = 0 • and two orthogonal steering vectors give α = 90 • .

Antenna Design

To determine the distance between the antenna elements of the sensor B, an ambiguity analysis is carried out. The range of the separation distance r covered by this analysis starts from 0 (co-located elements) up to λ/2. The radiating elements are equidistant of each others and located on a circle of r/ √ 3 in radius. They are considered as elementary dipoles (magnetic and electric) and EM coupling effects are neglected. Since the sensor B is applied to the direction estimation in 3D half-space, the criterion α, given in [START_REF] Malloy | Analysis and synthesis of general planar interferometer arrays[END_REF], is computed for φ 1 and φ 2 ∈ [0; 2π] and for θ 1 and θ 2 ∈ [0; π/2]. For each DoA (φ 1 , θ 1 ), the minimum α is extracted to obtain the 3D ambiguity spectra given in Figure 9. Up to a distance of λ/4, no ambiguous angle is detected (α min (φ 1 , θ 1 ) > 0). However for r close to λ/3 an ambiguity appears between φ 1 = 0 • and φ 1 = 180 • for θ 1 close to 90 • as shown in Figure 9 Thus the distance r is set to λ/4 to avoid ambiguous angles as shown in Figure 11(a). The sensor B is modeled using HFSS. The dimensions of the antenna (two half-loops and one linear monopole) are given in Figure 10 and in Table 6. The operating frequency has been set to 2.4 GHz. A metallic disc is placed at the bottom of the sensor B. Its diameter is fixed to 350 mm (≈ 2.8λ).

A new ambiguity analysis is carried out with the steering vector obtained from full wave electromagnetic simulation. This analysis confirms that for r = λ/4 there is no ambiguous angle with this realistic vector sensor (see Figure 11(b)). The metallic disc at the bottom of the sensor B alters the ambiguity spectrum by reducing the received power for elevation angles close to 22.5 • . However, the resulting 3D ambiguity spectrum is close to the theoretical results for other directions of arrival.

• 45 • 0.1 • 0.1 • 0.45 • 0.3 • 45 • 10 • 0.2 • 5.4 • 0.7 • 0.65 • 45 • 80 • 2.1 • 4.8 • 1.25 • 4.2 • 55 • 20 • 0.8 • 1.7 • 0.45 • 0 • 90 • 80 • 2.2 • 5.7 • 0.8 • 5.2 • 95 • 40 • 0.1 • 0.5 • 0.5 • 0.4 • 130 • 60 • 0.2 • 0.4 • 0.15 • 1.35 • 135 • 90 • 4.5 • 3 • 1.75 • 2.3 • 180 • 45 • 0.15 • 0.35 • 0.25 • 0.3 • 225 • 10 • 0.05 • 5.3 • 0.15 • 0.1 • 270 • 45 • 0.2 • 0.5 • 0.1 • 0.25 • 315 • 80 • 2.35 • 5.3 • 0.6 • 3.75 •

Comparison of the DoA Estimation Accuracy between the Sensor A and the Sensor B

The DoA estimation accuracy of the sensor B is computed for a RSNR of 15 dB and 10 dB and compared with one obtained by using the sensor A. The calibration matrix computed with the same process such as in the Section 3.3 is imported into the MUSIC algorithm. The number of snapshots (N ) and iterations (IT ) are both set to 100. The results are given in Table 7 and in Table 8.

• 40 • 1.4 • 2.8 • 1.45 • 1.65 • 130 • 60 • 2 • 2.65 • 2 • 6.6 • 135 • 90 • 9.3 • 6.3 • 4.85 • 3.95 • 180 • 45 • 1.05 • 2.3 • 1.25 • 2.15 • 225 • 10 • 3.2 • 7.35 • 1.7 • 0.7 • 270 • 45 • 1 • 2.55 • 0.8 • 2.
The simulation results show that the sensor B is more accurate than the sensor A. For high RSNR (≥ 15 dB), the maximum estimation error in the half-space for the sensor B is 1.65 • in azimuth and 5.2 • in elevation and 4.5 • and 5.7 • for the sensor A. When the RSNR is 10 dB, the highest error is 4.85 • in azimuth and 6.8 • in elevation for the sensor B and 13.45 • and 7.35 • for the sensor A. Such improvement of the accuracy is due to the additional information on DoA provided by the spatial phase shift but also to the reduction of the coupling effect, as shown in Table 9 and in Table 10 for the sensor A and the sensor B respectively. The mutual coupling reduces the dynamic of the power received by each antenna port and consequently alters the DoA estimation sensitivity. Thus the sensor A is found to be less robust to the noise level than the sensor B.

CONCLUSION

In this work, two new designs of vector sensor have been proposed to estimate the directions of arrival in the 3D space (azimuth and elevation angles) of TM electromagnetic signals. The two sensors are composed of three antenna elements only: two orthogonal half-loops and one linear monopole. Each design uses a metallic plate as antenna support in view of embedded applications. One sensor, called sensor A, uses co-located elements while the other one, called sensor B, is based on distributed antenna elements. The accuracy of the DoA estimation with the sensor A has been computed through full wave electromagnetic simulations and by using the MUSIC algorithm. A prototype of this antenna has been manufactured for validation purpose with measurements performed in an anechoic chamber. The sensor B has been studied with the same simulation process. A 3D ambiguity analysis has been carried out to determine the separation distance between the antenna elements without causing ambiguous estimations. This distance is found to be close to λ/3. The DoA estimation with the sensor B has been found more accurate than one obtained by using the sensor A. It is due to the reduction of the EM coupling and the additional information on the DoA provided by the spatial phase shift resulting from the spatial distribution of the antenna elements of the sensor B.

Figure 2 .

 2 Figure 2. Normalized P r (θ) at the input port of the electric dipole in the E-plane -simulation results.

Figure 3 .Figure 4 .

 34 Figure 3. Design of the vector sensor A.

Figure 5 .

 5 Figure 5. Vector sensor A combining three co-located radiating elements: two orthogonal half-loops and one linear monopole.

Table 3 .

 3 Mean estimation error by using the sensor A -simulation results by taking into account EM coupling between the antenna elements -RSNR = 15 dB, N = 100 and IT = 100. φ θ Mean azimuth error Mean elevation error 55

Figure 6 .

 6 Figure 6. Prototype of the sensor A on a metallic plate of 300 mm in diameter.

Figure 7 .

 7 Figure 7. Normalized gain from 45 • to 135 • in azimuth and 0 • to 90 • in elevation of (a) the simulated monopole E z , (b) the measured monopole E z , (c) the simulated half-loop H x , (d) the measured half-loop H x , (e) the simulated half-loop H y , (f) the measured half-loop H y .

Figure 8 .

 8 Figure 8. Design of the vector sensor B.

Figure 9 .

 9 Figure 9. Theoretical 3D ambiguity spectra (α min (φ 1 , θ 1 )) associated with the sensor B with (a) r = 0, (b) r = 0.1 × λ, (c) r = 0.2 × λ, (d) r = 0.3 × λ, (e) r = 0.4 × λ, (f) r = 0.5 × λ. Table 6. Dimensions of the sensor B (in mm). a 6.74 c 1 4 d 1 2.2 e 23.5 g 100 b 19 c 2 3.5 d 2 2.2 f 25

Figure 10 .Figure 11 .Table 7 .

 10117 Figure 10. Vector sensor B combining three distributed radiating elements: two half-loops and one linear monopole.

Table 1 .

 1 Mean estimation error of the sensor A -Simulation results without EM coupling between the antenna elements -RSNR = 15 dB, N = 100 and IT = 100.

	φ	θ	Mean azimuth error Mean elevation error
	55

Table 2 .

 2 Dimensions of the sensor A (in mm).

	Antenna design

a 6.74 c1 3 d1 0.8 e 11 g 13.41 i 60 b 20 c2 3 d2 2 f 36.5 h 25

Table 4 .

 4 Simulated estimation error by using the sensor A with EM coupling -RSNR = 30 dB, N = 1 and IT = 100.

	φ	θ	Mean azimuth error	Mean elevation error
	55 •	20 •	7.4 •	2.95 •
	95 •	40 •	1.2 •	2.75 •
	130 • 60 •	1.35 •	2.1 •
	45 •	80 •	4.65 •	5.9 •

Table 5 .

 5 Measured estimation error by using the sensor A -RSNR = 30 dB, N = 1 and IT = 100.

	φ	θ	Mean azimuth error	Mean elevation error
	55

Table 8 .

 8 Mean DoA estimation error -Simulation results by using the sensor A and the sensor B -RSNR = 10 dB, N = 100 and IT = 100.

	φ	θ	Sensor A Mean φ error Mean θ error Sensor A	Sensor B Mean φ error Mean θ error Sensor B
	0 •	45 •	1.7 •	2.75 •	2.8 •	2.8 •
	45 •	10 •	4.65 •	7.2 •	3.95 •	1.6 •
	45 •	80 •	6.55 •	6.8 •	3.5 •	6.3 •
	55 •	20 •	13.45 •	3.25 •	4.35 •	0.15 •
	90 •	80 •	5.35 •	7.15 •	2.6 •	6.8 •
	95

Table 9 .

 9 Simulated coupling between the antenna elements of the sensor A.

	25 •

Sensor A

Ez monopole Hx half-loop Hy half-loop

Table 10 .

 10 Simulated coupling between the antenna elements of the sensor B.

	Ez monopole	X	-20.8 dB	-15.5 dB
	Hx half-loop	-20.8 dB	X	-35.6 dB
	Hy half-loop	-15.5 dB	-35.6 dB	X

Sensor B

Ez monopole Hx half-loop Hy half-loop

ACKNOWLEDGMENT

The authors wish to acknowledge M. Christophe IMBERT, from Rockwell Collins, for providing his support in this work.


Perspective on "New and Less New Opportunities For Mathematical

Another conception that makes applications of mathematics quite different from applications of mathematics to sole biology resides in the interventionist nature of medicine ...

This perspective, bouncing from Philip Maini's "Perspective on The Changing Face of Mathematical Biology"1 , focuses on the specific case of mathematics as applied to medicine. Philip Maini acknowledges the pioneering work of James D. Murray in Oxford: for sure, this immense founding enterprise with no equivalent worldwide has led, through his stimulating teaching and research, to the training of scores of students, from pure to very applied mathematicians, many of whom have themselves become leading scientists in different fields of mathematical biology.

In other parts of the world, such pioneers were scarce, but little by little, by the virtue of example, scientists coming either from the engineering world or from pure and applied mathematics learnt to know that non-trivial mathematics had been written by some of them, starting from open biology questions, often by transposing methods from physics or chemistry. For instance, reaction-diffusion equations have been studied as providing a theoretical basis for traveling waves of physical phenomena by Kolmogorov, Petrovsky and Piskunov and independently by Fisher (for the spread of a gene in a population), all in 1937, and later a basis for morphogenesis by Turing in 1952. However, James Murray reports (Mathematical Biology 3rd ed.,vol. 1,13.2) that the first discovery of the so-called KPP-Fisher equation is due to the German chemist Luther in 1906, but also that his publication soon sank into oblivion, to be rediscovered later, much later than 1937. The scientific audience likely was not ripe then to catch the scope of this discovery and its potential applications to biology, even though Fick (1855) in the same country had already presented his law of diffusion 50 years earlier. The now classical examples of Hodgkin-Huxley (1952) and later FitzHugh-Nagumo models of action potential propagation (1961,1962) or Turing instability (1952) came later, on apparently more favorable ground.

What had changed? Maybe the fact that biological phenomena that were until then considered as just being there -the propagation of nerve impulse or the spots on a leopard -were investigated by advanced scientists -physicists or mathematicians -as having in fact a physical basis and hence a mathematical expression. Maybe in about the same way as in the Greek antiquity, presocratic philosophers and the mathematicians among them tried to organize a corpus of pre-existing observations (in particular from Babylon and Egypt) according to rules, some of which could be shown to be more than rules.

The situation in which we are now is indeed somewhat different. In a world where scientists of different disciplines regularly meet in conferences and workshops, and publish jointly in journals in which attention is given to both mathematical modeling and experimental results, it is less likely that breakthrough discoveries may be lost. Furthermore, centers for mathematical biology, and as regards oncology, centers for integrated research on cancer (essentially in the US for the latter) now exist and offer institutional opportunities to exchange knowledge between disciplines, including mathematics and clinical medicine. In the UK, the Mathematics in Medicine Study Group (MMSG) organizes meetings in different locations to model and tackle during 2-3 days problems coming from requests by biologists or physicians. Even in places where such institutions are not yet present, grants coming from international and national calls more and more allow constituting coherent teams of applied mathematicians working in close contact with teams of biologists and -less frequently -physicians.

As Philip Maini stresses, data coming from biological experiments are most often static, i.e., snapshot-like, when we need movie-like data to identify the dynamics of the biological systems under study. Furthermore, a frequent and simplifying underlying assumption is that tissues are homoge-neous, genetically and phenotypically, when for instance multilocular samples in the same tumor show that this is frequently not the case, at least in cancer. In biological and medical research teams, people are keen on identifying intracellular signaling pathways -or cell membrane targets upstream of them -searching for so-called "druggable targets" to block or enhance them. But the dynamic viewpoint that mathematicians are fond of "where does this lead to? i.e., what is the asymptotic behavior of the system, controlled or not?", is seldom present. However, such a dynamic perspective has always been present in the mind of biologists dealing with evolution, and recently -remembering that, as stated by Theodosius Dobzhansky in 1973, "Nothing in biology makes sense except in the light of evolution" -it has also become clear at least for some cancer biologists. Some indeed consider cancer as an evolutionary disease, in the sense that cell populations evolve, partly with prescribed rules, partly due to random events and partly under the influence of tissue environmental factors, towards diseased states as populations of multicellular organisms do. In my opinion, this view is about to deeply change our conception of diseases, and in particular of cancer.

Another conception that makes applications of mathematics quite different from applications of mathematics to sole biology resides in the interventionist nature of medicine, that is absolutely irreducible to an applicative branch of biology. Whereas the physicist describes the evolution with time of natural phenomena, and in particular of diseases, the physician is expected to correct them or prevent them, otherwise said to control them. This leads to the idea, not only to apply optimization and optimal control principles to therapeutics, but also to design models of health and disease in tissues and organisms as dynamical systems under physiological control mechanisms that can be corrected when they fail. In this respect, firstly it is necessary to reintroduce physiology at the era of genetics at all levels where physiological regulations occur: intracellular gene regulatory networks, equilibria between competing populations of cells, whole body hormonal regulations, and also between these levels; and secondly, setting such physiological controls and the correction of their disruptions as optimization problems (physiologically solved or to be solved by therapeutic intervention) should foster much more work between physicians and mathematicians specialists of optimal control. This is another opportunity that I see for the future, and it will make all the more sense as the biological control mechanisms will be more known. Even if they are not known in detail to perform quantitative predictions, qualitative results about optimized therapeutic strategies to combine drugs should prove helpful to clinicians.

Of course, the continuous progress of imagery techniques, at all possible biological levels of observation, from intracellular signaling pathways to whole-body recordings, in a more and more dynamic way, i.e. with space and time resolutions that are driving us from a scenery of poorly defined snapshots to another one of high precision movies, will never exclude the fact that important variables of the dynamic systems under study will remain hidden. This naturally calls for other new mathematical developments, which resort to statistical theory and to inverse problem methods.

Such perspectives, some of them rather recent, together with a growing open-mindedness of biologists and physicians towards mathematics open new tracks to follow for the growing number of mathematicians interested in doing "mathematics for medicine". There are hard problems -and less hard ones -to solve, that will be a source of inspiration for mathematicians and a help to physicians -be it only to provide new ways to ask questions -provided that the initial question is of biological and medical nature, transposable in mathematical settings, and that a collaborative work is performed interactively between members of the two disciplines towards advances in solving them.

About The Author:

Dr. Jean Clairambault, PhD, MD, trained -in that order -in mathematics and medicine, is presently a senior scientist ("directeur de recherche") at INRIA and Laboratoire Jacques-Louis Lions, Pierre et Marie Curie University in Paris. His current research interests are the emergence of drug resistance in cancer and the evolution from premalignant cell populations to tumors, together with therapeutic optimization methods using combined drug delivery strategies to overcome such evolutions at the cell population level. Website: http://www.rocq.inria.fr/bang/ JC/Jean_Clairambault_en.html.

http://www.smb.org/publications/newsletter/vol27no1.pdf


Jean Clairambault

My long journey in mathematics as applied to biology and medicine began by a training in pure maths, geometry, that did not push me towards applications in any manner. At that time (late seventies), research in geometry was dominated by abstract concepts (e.g., sheaf cohomology), which had little to do with objects that one can touch. Conversely, having been trained in maths, I was demanding on understanding in depth how phenomena occur, not by principles, but by theorems, which will always remain the only way of proving results. I was not satisfied either with the idea to be a teacher all my life, although I had passed with success an application (the French agrégation) to obtain the right to teach at least in good conditions if I had to.

I was then available for something new. I have read somewhere that to fall in love, one has to be available for new things, and there should be many examples of this in literature. Well, it can be the same with science. I began with science, be-ing more trained in this domain than in the other (love came a little later, but this is another story). Being thus available, and interested in working on not just transmitting, but as far as possible creating, knowledge in a field where some potential place for maths would exist, I considered different possibilities, among which the most obvious were offered by economics and by biology. I had not had any training in economics and I was very mediocre at biology, making very little sense of what I was taught in the lycée. But I had at the university the example of a geometer who, being one year ahead of me in mathematical studies, was at the same time studying medicine, and dealing with interesting geometrical problems coming from radiology. During my training for the agrégation, I had learnt to learn quickly and efficiently, I was not bad either at learning lists and I thought that I might be more useful as a doctor than as a teacher. I should also mention in the personal mental process that led me to medicine the movie by Akira Kurosawa '' Akihige" (Red Beard), in which the character played by Toshiro Mifune is both able to break bones if necessary, as the master of martial arts he is, defeating a gang of ruffians who claim to prevent him from taking to his hospital a tuberculous prostitute from the brothel she works in, and later repair them, as the talented surgeon he also is. [When I tell this to my children, they seem to think that it is just one more odd thing of me.] Furthermore, during the summer preceding my first classes in medicine, I spent two months visiting Peru by myself, and the poverty I discovered there convinced me of the interest of being a physician rather than a teacher if one wants to be active and useful.

If I had not studied mathematics first, I might have become one of these ''French doctors" for a time. Indeed, one can find real addiction in practicing first aid care or surgery, or even plain medicine when a fast and right diagnosis saves a life. What I discovered early in medicine were first very interesting classes in biology, anatomy and physiology -which then made sense to me, because they were meant to give the basic knowledge necessary to practice medicine -and also a close contact with real life. When you study maths, problems are generally designed in such a way that the student is guided by a succession of questions to the main result to be shown, and it would be unfair to put traps on the way towards the solution. Of course you have to keep in mind that apparently likely things are not true (e.g., that exp(A) * exp(B) is not always equal to exp(A + B) for endomorphisms, etc.), but one learns to be cautious, and you can always count on proofs relying on theorems to sever between true and false. In medicine, nothing of the kind exists. Diagnosis is often difficult, and snares put on your way, just by hazards of life, are frequent. Doubt (popularized by medical TV serials) is also frequent, and no theorems exist to pull you out of it. What you can always reckon on is anatomy and physiology, but whereas anatomy is usually a faithful help, physiology is more ambiguous since its various negative feedbacks may be used to hypothesize one thing and its contrary. So that, confronted with clinical puzzles, rather that indulging in impassioned discussions as in TV serial staff meetings, physicians often apply therapeutic rules learnt in books, updated according to current treatments referenced by the Faculty.

Such generalized absence of theory with sound foundations left me unsatisfied as I had been, years earlier, by sheaf cohomology. I was again available (not in all domains, for I was then married with a newborn child) for discovering new things in maths and in medicine to find my own way. But how can you be useful to medicine when you have studied pure maths? I had in the course of my medical studies taken some time to learn classical statistics (teaching them at the same time, for there is no better way to learn than in teaching), which has always proved useful to me, be it only to understand how statistical tests are used in processing biological data. Being firstly recruited as a volunteer in the research institute that still hires me (on a permanent position now), and later detached in it from the national education service, I learnt at that time basics of signal processing and multidimensional statistical methods to deal with physiological recordings.

This was far from the mathematical modeling and analysis for medicine I am busy with now, but it was necessary to know what biological data are and what sort of physiological hypotheses one can propose from statistical processing of data, according to a well-designed method, to answer a pathophysiological question. The first study I led then was the core of my MD thesis, and it was later extended to more such studies. It was also very useful to me to establish contacts with medical teams, showing that I could provide them with new methods of investigation. Being hired for a prolonged detachment in my institute, I could then begin to get involved in more theoretical studies. It began with cardiac electrophysiology. After some time (ten years), I met an oncologist interested in mathematical modeling, not to understand better cancer treatments by the use of theorems, but to see what new insights mathematical models could bring to his therapeutic practice.

Limited as these expectations may seem, they are not so frequent and show some open-mindedness that allowed me to establish a long-lasting collaboration (twelve years). From it, my regular participation in lab meetings resulted in biological and therapeutic control questions that led me to design models of tumor growth control by drugs, and later to enter in contact with specialists of optimal control, with whom I still work on theoretical optimization of treatments by anticancer drugs. Presently, understanding resistance in cancer to overcome it by optimized time schedules of combinations of drugs is one of my major goals. This also leads me now to try and take advantage, at the genomic era (which includes epigenetics), of data on intracellular signaling pathways, to connect them with cell fate at the level of cell populations, the right level to observe cancer progression and its control by drugs.

Let the reader take this personal journey as a complement to the "Perspective" short paper I published last year in the May issue of this newsletter, and to a paper I published three years ago in Acta Biotheoretica on "Commitment of mathematicians in medicine". I hope that it shows an example of a way of career that may be followed -or on the contrary, that must be absolutely avoided! Example or quixotic counterexample, I will go on searching for theorems to found clinical practice (see on this a perspective I wrote in 2013 for J. Math. Biol.), and if I may have contributed to finding some in the future, I shall be happy with my journey.

About The Author:

Jean Clairambault, PhD, MD, trained -in that order -in mathematics and in medicine, is presently a senior scientist ("directeur de recherche") at IN-RIA and Laboratoire Jacques-Louis Lions, Pierre et Marie Curie University in Paris. His current interests in research are the emergence of drug resistance in cancer and the evolution from premalignant cell populations to tumors, together with therapeutic optimization methods using combined drug delivery strategies to overcome such evolutions at the cell population level. Website: http://www.rocq. inria.fr/bang/JC/Jean_Clairambault_en.html.


Alexandra Skripchenko

Serge Troubetzkoy
email: serge.troubetzkoy@univ-amu.fr

ENTROPY AND COMPLEXITY OF POLYGONAL BILLIARDS WITH SPY MIRRORS

We prove that a polygonal billiard with one-sided mirrors has zero topological entropy. In certain cases we show sub exponential and for other polynomial estimates on the complexity.

1. Introduction 1.1. Polygonal billiards with one-sided mirrors. We consider a table consisting of a polygon Q ⊂ R 2 (not necessarily rational) with several one-sided mirrors inside; i.e. a straight line segments connection pairs of points in Q, each of which has two sides, a transparent side and a reflecting side. The billiard is defined as follows. Consider a point particle and a direction θ ∈ S 1 ; the point moves in the direction θ with a unit speed up to the moment when it reaches the boundary, if it arrives at a transparent side of a mirror it passes through it unperturbed, while if it arrives at a reflecting side of a mirror or at the boundary of Q it is reflected with the usual law of geometric optics, the angle of incidence equals the angle of reflection.

Polygonal billiards with one-sided mirrors were described for the first time by M. Boshernitzan and I. Kornfeld in [BoK], in this article one-sided mirrors were called spy mirrors. However, they considered the less general case of rational polygons with the mirrors that form rational angles with the sides of polygonal table. Such tables give rise to interval translation maps, a generalization of interval exchange maps. In contrast of interval exchange transformations, interval translation maps are poorly understood, only a few results are known (see [BoK], [SmT], [Ba], [BrT], [SuIA], [BrC], [V], [SkT]). A particular example of a rational billiard with onesided mirrors, the square with a vertical one-sided mirror with one end point on the bottom side of the square, was studied in [SkT].

In this article we will prove two types of results. In the setting of an arbitrary polygon with one-sided mirrors we show that the topological entropy of our system is zero. In certain more restricted settings we show that we have sub exponential or polynomial growth estimates. The next two subsections describe these results in more detail.

1.2. Topological entropy. We prove that the polygonal billiard with one-sided mirrors has zero topological entropy. To do this we first consider the inverse limit space of a polygonal billiard with one-sided mirrors and show that it has zero topological entropy (an exact statement is provided below). We show that the inverse limit space in our case is closely related with the attractor (the notion of the attractor of the billiard map was introduced in [SkT]) and that the attractor 1 has zero topological entropy. Then we extend the zero entropy result to the full phase space.

There exist several different proofs of zero topological entropy for polygonal billiards without one-sided mirrors (see [K], [GaKT], [GuH]). Our proof mainly uses some ideas from [GaKT] and [K]. The main difference with the situation of classical billiards is the non-invertibility of our system. Also, J. Buzzi in [Bu] showed a closely related result that piecewise isometries in any dimension are of zero entropy. For rational polygonal billiards with rational one-sided spy mirrors, zero topological entropy is a corollary from the fact that the directional complexity is at most polynomial [Ba], and the variational principle.

Throughout the article the term side will denote a side of the polygon Q or a side of a one-sided mirror, and the term vertex denotes an end point of a side. We will are denote by q the number of sides of Q and r the number of spy mirrors, thus we have q + 2r sides. The collection of sides will be call the boundary Γ. We will consider the billiard map T , the first return map to Γ. The phase space T Γ of the billiard map is the subset of inner pointing vectors of unit tangent bundle (for vectors with base point in a one-sided mirror this means that if we reverse the direction of the vector it will point at the reflecting side of the mirror). Note that if the billiard orbit arrives at a vertex of Q then the collision rule is not well defined since we can reflect with respect two different sides, thus the billiard map is not defined for such points. Let π : T Γ → Γ denote the natural projection.

Let I i : 1 ≤ i ≤ q + 2r be an enumeration of the sides of Q. The forward orbit of a point x can be coded by the sequence of sides hit by the orbit. Let

Σ + =: { a := (a i ) I∈N : ∃x such that π(T i x) ∈ I ai ∀i ≥ 0}.
In this definition it is implicitly assumed that the map T i x is defined for all i ≥ 0. We use the discrete topology on the collection of sides, and the product topology on Σ + . The left shift map on Σ + will be denoted by σ. The main result of this section is the following theorem.

Theorem 1. For any polygon with spy mirrors we have

h top (Σ + , σ) = 0.
Suppose that µ + is an invariant measure on Σ + , Theorem 1 implies that σ is µ + almost surely invertible. The complexity p(n) is the number of words on length n which appear in Σ + . Theorem 1 implies that lim n→∞ log(p(n))/n = 0.

Our proof of Theorem 1 uses invertibility, we begin by working in the inverse limit of the coding space

Σ =: { a := (a i ) I∈Z : (a i-j ) i≥j ∈ Σ + ∀j ∈ Z}.
We also introduce

Σ -=: { a := (a i ) I∈N : ∃(b i ) i∈Z ∈ Σ such that a i = b i ∀i ≤ 0}.
Finally the inverse limit of the billiard map is

Ω =: { x := (x i ) i∈Z : T x i = x i+1 ∀i ∈ Z}.
Here we again assume that the forward orbit T j x i is definite for all i and all j ≥ 0. We use the natural topology of T Γ on x 0 and the product topology on Ω.

The attractor of the billiard map is the set A := ∩ n≥0 T n (T Γ), where for the set T n (T Γ) we consider only the points in T Γ for which T n (T Γ) is defined.

All shift maps (on Σ or Ω) will be denoted by σ. We extend the shift map to Ω, Σ + and Σ. We show that Theorem 2. For any polygon with spy mirrors we have

h top (A, T ) = h top (Ω, σ) = h top (Σ, σ) = 0.
and then we show that Theorem 1 follows from Theorem 2. 1.3. Complexity estimates in special cases. A generalized diagonal is an orbit segment which starts and ends in a vertex of Q, let N vert (n) denote the number of generalized diagonals of combinatorial length at most n.

We begin with a general theorem, and then we will apply it to specific examples.

Theorem 3. Suppose that Q is a q-gon with r spy mirrors, then

p(n) ≤ 1 + (q + 2r -1)n +   2((q + 2r) 2 -3) n-1 j=0 j i=0 N vert (i)   .
We call Q a symmetric polygon with spy mirrors if there is a polygon P such that Q is obtained from P via a finite unfolding and there are finitely many spy mirrors which are contained in the common edges of the unfolded copies of P (see Figure 1). Theorem 4. Suppose that Q is a rational symmetric polygon with spy mirrors. Then there is a constant C > 0 so that the total complexity satisfies p(n) ≤ Cn 4 for all n ≥ 0.

Next we consider symmetric polygon with spy mirrors obtained from a triangle (non necessarily rational). Two smallest angles determine a triangle up to scaling, and billiards are scaling invariant. Thus, up to scaling, the set of triangles is a subset of R 2 equipped with Lebesgue measure. In the next theorem the word typical will mean Lebesgue almost every.

Theorem 5. Suppose that Q is a symmetric polygon with spy mirrors obtained from a typical triangle. Then for every ε > 0 there is a constant K > 0 so that p(n) ≤ Ke n ε for all n ≥ 0.

Also one can prove a special complexity estimation for a generalization of the billiard with square table that we studied in [SkT].

Theorem 6. Suppose that Q is the square with k vertical spy mirrors. Then there is a constant K > 0 so that the total complexity satisfies p(n) ≤ Kn k+4 for all n ≥ 0.

The proofs of the entropy results

2.1. Unfolding and strips. Consider the backwards billiard flow starting from a point in Γ; instead of reflecting the orbit about a side of Q we reflect the polygon about the same side and continue the orbit as a straight line. When it meets another side of the reflected polygon we repeat the procedure with respect to this side, etc. We can continue up to the moment when we hit the vertex. The copies of Q obtained after such a reflection we will label with respect to a side that was an axis of reflecting (Q A , for instance.) Lemma 7. Suppose x, y ∈ Ω and that x 0 and y 0 are not parallel, then their backward codings can not coincide.

Proof. We look at unfolding lines for the past orbits, see Figure 2, we suppose there codes coincide for a certain interval of times. We remark that when a backward orbit hits a one-sided mirror, there are two possible preimages, by definition these preimages have different codings; thus for the interval of times when the backward codings coincide the choice of preimages (which is given since x and y are in the inverse limit space Ω) is the same for x and for y.

These lines are eventually linearly divergent, thus the distance between them is eventually more than twice the diameter of Q, and so the backwards unfoldings of x 0 and y 0 must be different, i.e. the reflections must occur in different edges, so the codings are different.

A B M C ❅ ❅ ❅ ■ Q A ✛ Q AM ✒ Q ✛ Q AM A ✠ Q AM C Figure 2.
Non-parallel orbits have different coding 2.2. Uniqueness of the coding. For each a ∈ Σ, there exist at least one point x ∈ Ω such π( x i ) = a i for all i ∈ Z, we denote the set of such x by X( a). The set X( a) can also be defined for a ∈ Σ -, and since for x ∈ Ω from the definition it is immediate that (x i ) i≤0 determines x uniquely, it follows that X( a) ⊂ Ω for points a ∈ Σ -. Lemma 7 implies that the set X( a) consists of parallel points.

Fix a ∈ Σ -. We call S ⊂ X( a) a strip if the set {x 0 : x ∈ S} consists of parallel vectors whose base points form an interval. Note that the backwards orbit of all the x ∈ S are nonsingular. Using the unfolding procedure, we will think of S as being a geometric strip in R 2 , hence the name. We have Proposition 8. Suppose that Q is an arbitrary polygon with a finite number of spy mirrors.

(1) For any a ∈ Σ -which is not periodic the set X( a) consists of only one point.

(2) For any a ∈ Σ -which is periodic the set X( a) consists of a finite union of parallel strips. Proof.

(1) The proof is by contradiction, consider two points x, y ∈ Ω with exactly the same aperiodic backwards coding a, Lemma 7 implies that x i and y i are parallel for all i ≤ 0. It may happen that the trajectories of points between them are not exactly the same (see Figure 3 for a possible example). Note that this can not happen for the usual billiard in a simply connect polygon. In order to avoid this problem, and enable us to use the strip argument from [GaKT], we construct an auxiliary dynamical system by declaring that for all points in between our two special have the same dynamics. Thus, with respect to this auxiliary dynamics the set S := X aux ( a) is a strip. More precisely, the auxiliary dynamics is defined as the map g which rigidly maps the vectors in the strip with base-point in the interval (x i-1 , y i-1 ) onto vectors in the strip with the base-point in the interval (x i , y i ) (for all i ≤ 0). Consider the sequence of vectors z := (z i ) i≤0 in the middle of the strip S, and the α-limit set Z of the auxiliary dynamics g of z. The set Z is compact, and since strips can not contain vertices the inverse map g -1 is continuous on Z, thus we can apply the Birkhoff recurrence theorem, to conclude that Z contains a uniformly recurrent point x * for the map g -1 . Fix a sequence n i so that g -ni z → x * . We consider images of the original strip S under g -ni and denote it by S i . Note that the widths of the S i are all greater than or equal to the width of S, and that S i converge to a strip S( x * ) centered at x * of the same width or more. We can suppose (by re-enumerating the sides) that x * 0 ∈ I 1 . The point x * 0 is not tangent to the side I 1 since then the orbit of z would come arbitrarily close to one of the endpoints of the side I 1 which contradicts the positive width of the strip S.

We consider the set of points S ∞ ( x * ) having the same auxiliary backwards code as x * . Clearly S ∞ ( x * ) is a strip and S ∞ ( x * ) ⊃ S( x * ). The left and right boundaries of S ∞ ( x * ) are two lines, we consider their ε-neighborhoods N L ε and N R ε . By the uniform recurrence of x * , vertices fall inside each of N L ε and N R ε with bounded gaps between their occurrences (see Figure 4). Fix one of the sides, say N ε := N L ε . Now S i → S( x * ), this can happen in two ways, either S i is parallel to S( x * ) for all sufficiently large i or not. In the second case the set N ε ∩ S i ⊂ N ε ∩ S contains an ε-width rectangle with a height L i that goes to infinity as i → ∞; thus there must be a vertex in S (see Figure 4(b)). This contradicts the fact that the backwards orbit of all x ∈ S = X( a) are non-singular, thus we can only have a single point x ∈ Ω with aperiodic backwards coding a. In the first case for sufficiently large i, since they are parallel we have S i ⊂ S ∞ ( x * ). We consider the set of points S ∞ i ( z) have the same auxiliary backward code as g -ni z, clearly this is the maximal width strip such that S ∞ i ⊃ S i . By maximality S ∞ i = S ∞ ( x * ). This implies that x * is periodic which contradicts the assumption that a is not periodic. Thus also in this case we can only have a single point x ∈ Ω with periodic backwards coding a.

N L ε ✲ ✛ N R ε ✛ S ∞ i ✛ S ∞ (x * ) ✲ L i ✟ ✟ ✟ ✟ ✟ ✯ ❙ ❙ ❙ ❙ ❙ ❙ ✇ (a) (b)
vertices or reflecting vertices (2) Now suppose that a ∈ Σ -is periodic. Lemma 7 implies that X( a) consists of parallel orbits. By the definition of the auxiliary dynamics, the set X aux ( a) with respect to the auxiliary dynamics is a strip. Suppose that the period of a is k and that x ∈ X aux ( a). From the periodicity of a we conclude that x i-k = x i , or T k (x i-k ) = x i , for all i ≤ 0. But since x i for i > 0 is defined as T i (x 0 ) we conclude that x is k periodic. Since the map T k is a local isometry we conclude that furthermore the width of the strip X aux ( a) is strictly positive.

( a) ∪ T -1 X aux ( a) ∪ • • • ∪ T -k+1 X aux ( a)
. Since we only consider a finite piece of the orbit the reflecting mirrors create at most finitely many "holes" in the auxiliary dynamics strip as in Figure 5, more precisely points for which the auxiliary dynamics and the real dynamic disagree, the set X( a) ⊂ X aux ( a) is a finite union of strips.

Let ∂Σ := Σ \ Σ and ∂Ω := Ω \ Ω. We extend X to Σ as follows. Suppose a ∈ ∂Σ, let a (n) ∈ Σ be such that a (n) → a. Let x (n) ∈ X( a (n) ). Since Ω is closed there is an x ∈ Ω which is a limit point of the x (n) . Let X( a) be the collection of all such x. We remark that all such points x ∈ ∂Ω since a ∈ Σ . Proposition 9. If x ∈ ∂Ω then there exist at most countably many a ∈ ∂Σ such that x ∈ X( a).

Proof. Suppose x ∈ ∂Ω. Consider x (n) ∈ Ω such that x (n) → x. Let a (n)
be the code of x (n) , and a any limit point of the a (n) , then clearly a ∈ ∂Σ, and x ∈ X( a). At a certain time the orbit of x reaches a vertex. There are clearly at most q + 2r possible extensions by continuity of the dynamics and of the code (see, for example, Figure 6 where the purple lines are the orbits that hit some vertex and several dotted lines represent possible extensions). Each of these extensions may again reach a vertex, so again each of them has at most q + 2r possible extensions. This can happen at most a countable number of times. 2.3. The attractor. For x in Ω let Y ( x) = x 0 . The following proposition shows that (A, T ) is a continuous factor of (Ω, σ).

Proposition 10. (i) x ∈ Ω ⇐⇒ Y ( x) ∈ A, (ii) Y (σ x) = T Y ( x), (iii) the map Y is continuous. Proof. (i) =⇒ Suppose x ∈ Ω, then T n (x n ) = x 0 since T (x i ) = x i+1 for all i.
⇐= Suppose x 0 ∈ A, then the set {T -i (x 0 )} is non-empty for all i ≥ 0. Consider the tree structure on these sets, i.e. draw an arrow from x i ∈ {T -i (x 0 )} to x i+1 ∈ {T -i-1 (x 0 )} iff T (x i ) = x i+1 . Since the vertex set on level n of the tree is nonempty for all n, there must be an infinite path in this tree, which defines the past of x := (x i ), and the future is defined by T i (x 0 ) with i > 0.

(ii) and (iii) follow immediately from the definition of Ω.

2.4. Entropy of ergodic measures. This subsection follows ideas in [K]. First, we show that nothing interesting happens on the boundaries.

Lemma 11. Every ergodic non-atomic shift invariant measure on Σ is supported by the set Σ.

Proof. We suppose that µ is an ergodic shift-invariant measure such that µ(∂Σ) > 0.

Let

Ω i := { x ∈ Ω : x i is a vertex} and Σ i = { a : X( a) ⊂ Ω i }. Clearly ∂Σ = ∪ i Σ i ,
thus our assumption implies that µ(∂Σ i ) > 0 for some i. Now by ergodicity, µalmost every point a ∈ Σ should visit this Σ i an infinite number of times, i.e. for each x ∈ X( a) there are times j < k so that x j and x k are vertices, i.e the orbit of x is generalized diagonal. But the set of generalized diagonals is countable, by Proposition 9 their lift is countable, and thus the measure is atomic.

Next we have

Lemma 12. For every ergodic shift invariant measure µ supported by the set Σ the entropy h µ (Σ) is equal to zero.

Proof. We consider the time zero partition ξ of Σ and the partition ξ -:= ∨ ∞ j=0 σ i ξ. An element P ∈ ξ -corresponds to a code in Σ -, there are two possibilities, either this code is periodic, or not.

(i) The code is periodic, then Proposition 8 tells us that X(P ) consists of a finite union of strips of periodic orbits, all with the same past code; thus all with the same future code. In particular P is a single point.

(ii) If the code is not periodic, then Proposition 8 tells us the X(P ) is a single point in Ω; thus P is a single point. Now we apply Rokhlin's theory of entropy ([R]), we have shown that ξ is a one sided generating partition (ξ -is the partition into points), thus

h µ (Σ) = h µ (Σ, ξ) = H(σξ/ξ -) = 0.

Proof of entropy theorems.

Proof of Theorem 2. h top (Σ, σ) = 0 follows immediately from Lemma 11, Lemma 12 and the variational principle. We have h top (Ω, σ) ≤ h top (Σ, σ) since (Ω, σ) is a continuous factor of (Σ, σ) (Proposition 9). Similarly, since (A, T ) is a continuous factor of (Ω, σ) (Proposition 10), we have

h top (A, T ) ≤ h top (Ω, σ) ≤ h top (Ω, σ).
Let f : X → X be a continuous map of a compact topological space X. Let (X, f ) denote the inverse limit of the map f . The non wandering set N W (X) of a continuous map f : X → X of a compact topological space X is the set {x ∈ X : for each neighborhood U of x, ∃n = 0 such that f n U ∩ U = ∅}.

Proposition 13. If h top (X, f ) = 0 the h top (X, f ) = 0.
Proof of Theorem 1. Theorem 1 follows immediately by combining Theorem 2 and the proposition.

Proof of Proposition 13. We use a theorem of Bowen ([Bo],Theorem 2.4) 5)). Thus applying once again the above mention theorem of Bowen we conclude that 0 = h top (N W (X), f ) = h top (X, f ).

h top (X, f ) = h top (N W (X), f ). Let p : X → X be the natural projection map. Clearly p • f ( x) = f • p( x) for any x ∈ X, which implies h top (N W (X), f ) ≥ h top (p(N W (X)), f ); therefore h top (p(N W (Σ)), f ) = 0. But p(N W (X)) = N W (X) ([AH] Theorem 3.5.1(

The proofs of the complexity results

Fix a q-gon Q with r spy mirrors. A spy generalized diagonal is an orbit which starts at a spy mirror (thus it has two backwards continuations) and ends in a vertex of Q, thus its orbit has two backwards continuations with different codes. Consider a spy generalized diagonal, since the length of the spy generalized diagonal is finite, slightly varying the angle of arrival at the vertex will yield a spy generalized diagonal with the same code (see Figure 7). Let N spy (n) denote the number of such families of length at most n. The set of spy generalized diagonals with a given code form a "sector" at the vertex, the boundaries of this sector are generalized diagonal of length at most n.

The boundary of a spy generalized diagonal sector of length n consists of two generalized diagonals of length at most n, one bounding from the left and one from the right (here left and right are with respect to a fixed orientation, say clockwise, at the vertices of arrival of the generalized diagonals). Thus we can define an injective map, the "right bounding generalized diagonal", from families of spy generalized diagonals of length n to generalized diagonal of length at most n yielding

Proposition 14. N spy (n) ≤ n i=0 N vert (i).
Proof of Theorem 3. The main technical tool will be a variant of Cassaigne's formula [C] developed in [SkT]. Let A be a finite alphabet, L ⊂ A N be a language, L(n) the set of words of length n which appear in L, and p(n) := #L(n). Note that p(0) = #{∅} = 1. For any n ≥ 0 let s(n) := p(n + 1)p(n), and thus

p(n) = 1 + n-1 j=0 s(j). For u ∈ L(n) let m l (u) := #{a ∈ A : au ∈ L(n + 1)}, m r (u) := #{b ∈ A : ub ∈ L(n + 1)}, m b (u) := #{(a, b) ∈ A 2 : aub ∈ L(n + 2)}.
We remark that while m r (u) ≥ 1 the other two quantities can be 0.

A word u ∈ L(n) is called left special if m l (u) > 1, right special if m r (u) > 1 and bispecial if it is left and right special. Let BL(n) := {u ∈ L(n) : u is bispecial}. Let L np (n) := {v ∈ L(n) : m l (v) = 0}.
In [SkT] we showed that

s(j +1)-s(j) = v∈BL(j) m b (v)-m l (v)-m r (v)+1 - v∈Lnp(j):mr(v)>1 m r (v)-1 .
Now we turn to the interpretation of this formula in the case that v is a bispecial word appearing in a q-gon Q with r spy mirrors. We make a worst case estimate, apriori the collection of orbits with the code v can hit all sides and all spy mirrors (forwards or backwards)

2 ≤ m l (v) ≤ (q + 2r) 2 ≤ m r (v) ≤ (q + 2r) 2 ≤ m b (v) ≤ (q + 2r) 2
Thus s(j + 1)s(j) ≤ ((q + 2r) 2 -3)#BL(j)

We have p(0) = 1 (the empty set) and p(1) = q +2r, thus s(0) = p(1)-1 = q +2r-1 and the method of telescoping sums yields

s(n) ≤ (q + 2r -1) + ((q + 2r) 2 -3) n-1 j=0 #BL(j).
To each bispecial word v corresponds a collection of generalize diagonals and/or spy generalized diagonal sectors of the same combinatorial length and code. Since the collections are determined by their code they are disjoint, thus

n-1 j=0 #BL(j) ≤ N vert (n) + N spy (n) ≤ N vert (n) + n i=0 N vert (i) ≤ 2 n i=0 N vert (i),
and thus s(n) ≤ (q + 2r -1) + 2((q + 2r) 2 -3)

n i=0 N vert (i).
Again by the method of telescoping sums we have

p(n) ≤ 1 + n-1 j=0
(q + 2r -1) + 2((q + 2r) 2 -3)

j i=0 N (i)) = 1 + (q + 2r -1)n +   2((q + 2r) 2 -3) n-1 j=0 j i=0 N vert (i)   .
Proof of Theorem 4. Consider a rational polygon P without spy mirrors. H.

Masur in [M] has shown that the number N g (t) of generalized diagonals of geometric length t satisfies N g (t) ≤ Ct 2 for some constant C = C(P ) for all t ≥ 0. By elementary reasoning there is a constant B > 1 such that B -1 ≤ N vert (n)/N g (n) ≤ B, thus there is a constant K = K(P ) so that N vert (n) ≤ Kn 2 for all n ≥ 0.

Suppose that the polygon Q with spy mirrors is a k fold cover of the rational polygon P . By the symmetry in the definition of Q each generalized diagonal in Q projects to a generalized diagonal in P , thus

N Q vert (n) ≤ kN Q vert (n) ≤ kKn 2 .
Thus the Theorem follows from Theorem 3.

Proof of Theorem 5. D. Scheglov in [Sg] has shown that for a typical triangle, for every ε > 0 there exists a constant C > 0 so that N vert (n) ≤ Ce n ε for all n ≥ 0.

Suppose that the polygon Q with spy mirrors is a k fold cover of typical triangle P . As in the proof of Theorem 4, each generalized diagonal in Q projects to a generalized diagonal in P , thus N Q vert (n) ≤ kN Q vert (n) ≤ kCe n ε and we again use Theorem 3 to conclude.

Proof of Theorem 6. First suppose the square is 1 × 1 and with a single spy mirror having x coordinate a. Let X denote the torus (2 × 2) obtained by unfolding the square with the one-sided mirrors identified as in the figure 8. Figure 8. A square billiard with the vertical mirror: table and unfolding Now we construct an explicit universal cover of X, first we unfold the square to a torus and then take the universal cover of the torus by the plane. Next we identify the one-sided mirrors at x = 2a + 2n with the one-sided mirror at x = 2 + a + 2n, i.e. all jumps are to the right and of the form 2a (see Figure 9).

❄ x = 2 -a + 2n ❄ x = 2 + a + 2n
Figure 9. A square billiard with the vertical mirror: universal cover Now consider the generalized diagonals starting at the origin which arrives at the point (m, n) (m > 0 and n > 0) which do not pass through any other vertex in-between. Label the squares traversed by the generalized diagonals by the coordinates of their bottom left corners. By the explicit construction of our universal cover, when the generalized diagonal is in the square with bottom left corner (i, j) then either we cross a horizontal side and are in square (i, j + 1) or we cross a spy mirror, or a vertical side and are in square (i + 1, j). Thus we cross n horizontal sides y = 1, y = 2, . . . , y = n -1, f vertical sides and g vertical mirrors with f + g = m -1. We conclude that the combinatorial length of any such generalized diagonal is (m -1) + f + g = m + n -2. We want to estimate how many such generalized diagonals we can have. Clearly there is at most one which hits no spy mirrors, it is the line segment of slope n/m starting at the origin and ending at (m, n), and it is a generalized diagonal if and only if this segment does not reflect form any spy mirrors. Now we claim that, for each 0 ≤ j ≤ m -1 there is at most one generalized diagonal connecting (0, 0) to (m, n) which hits exactly j spy mirrors. In fact, the slope of such a generalized diagonal must be n/(m -j2a), and then if we start an orbit segment at the origin with this slope it is a generalized diagonal (arrives at (m, n)) if and only if it hits exactly j spy mirrors.

Thus there are at most m generalized diagonals connecting (0, 0) to (m, n), all other cases of pairs of vertices are similar. There are const • N 2 lattice points and ends of spy mirrors at a distance N of the origin, yielding a cubic estimate for the number of generalized diagonals and thus a quintic estimate on the complexity by Theorem 3. Now consider the general case. Let x = a i , 1 ≤ i ≤ k be the x coordinates of the finite collection of vertical mirrors (there can be several mirrors with the same x coordinate). The reflecting sides of the mirrors are not necessarily the same. The universal cover identifies the copy of each mirror in x = 2a i + 2n with the associated one-sided mirror at x = 2 + a i + 2n for mirrors with the reflecting side of the left say, and if the right side is reflecting then x = a i + 2n with the associated mirror at x = 2a i + 2n. As we trace a trajectory it always jumps to the right, by b i := 2a i in the first case, and b i := 2 -2a i in the second case.

Consider the generalized diagonal connecting (0, 0) to (m, n). Let 0 ≤ j i ≤ m-1 denote the total number spy mirrors with x-coordinate a i which the generalize diagonal hits, and 0 ≤ j 0 ≤ m -1 denote the number of vertical sides it crosses. For each 0 ≤ ℓ < m -2 it hits exactly one spy mirror or one vertical mirror in each rectangle ℓ < x ≤ ℓ + 1, thus (1) k i=0 j i = m -1 (note that it can not hit a vertical mirror in the rectangle m -1 < x ≤ m and arrive at the point (m, n) and by definition it arrives, but does not cross the side x = m). Furthermore the total horizontal distance travelled by the generalized diagonal is n -k i=1 j i b i . Since the vertical distance it travelled is m it has slope n/(mi j i b i ).

We claim by induction that the number Q k (m) of integer solutions of (1) with each 0 ≤ j i ≤ m -1 satisfies Q k (m) ≤ m k /k! for all m ≥ 1. For k = 1 equality holds, this was used above. Suppose that this is true for some fixed k. As above we have shown that for each choice of the set {j i } we have at most one generalized diagonal connecting the origin to (m, n). Thus there are at most O(m k ) generalized diagonals connecting (0, 0) to (m, n), all other cases of pairs of vertices are similar. Again there are at most O(N 2 ) lattice points and ends of spy mirrors at a distance of at most N from the origin, yielding at most O(N k+2 ) generalized diagonals of length N and thus the complexity is at most O(N k+4 ) by Theorem 3. Remark, we actually prove a slightly stronger theorem Theorem 15. Suppose that Q is the square with a finite number of vertical spy mirrors cottoned in k vertical lines. Then the total complexity satisfies p(n) ≤ Cn k+4 for all n.

Acknowledgements.

We gratefully acknowledge the support of ANR Perturbations. The first author was also partially supported by Dynasty Foundation.

Figure 1 .

 1 Figure 1. A symmetric polygon with two spy mirrors

Figure 3 .

 3 Figure 3. The orbit in the middle of the strip has different dynamics.

Figure 4 .

 4 Figure 4. Vertices and recurrence points

mirrorsFigure 5 .

 5 Figure 5. Finite union of strips

Figure 6 .

 6 Figure 6. The purple trajectory hits a vertex, all possible symbolic extensions are indicated via close by orbits, there are 2 extensions for the left figure, 6 for the right figure.

Figure 7 .

 7 Figure7. All the orbit segments at the wedge are spy generalized diagonals with the same code cb. This word has 4 extension e ± cba and e ± cbd where e + and e -refer to the two sides of the one-sided mirror.

  To estimate Q k+1 (m) suppose that k 0 = p ∈ {0, 1, • • • , m -1}, then k i=1 k i = m -1p which has Q k (mp) ≤ (mp) k /k! solutions. Thus Q k+1 (m) ≤ m-1 p=0 (mp) k /k! ≤ m k+1 /(k + 1)!.