text:
# Impurity Scattering in a Bose-Einstein Condensate at finite temperature.

## Abstract

We consider the effects of finite temperature on the scattering of impurity atoms in a Bose-Einstein condensate, showing that the scattering rate is enhanced by the thermal atoms. Collisions can increase or decrease the impurity energy. Below the Landau velocity only the first process occurs, i.e., the collisions cool the condensate. Above the critical velocity the dissipative collisions prevail over the cooling ones for sufficiently low temperatures. These considerations are applied to a recent experiment.

Superfluidity is a phenomenon observed for the first time in $`{}_{}{}^{4}He`$. It consists in the suppression of the viscosity of the superfluid below a critical velocity $`v_L`$, due to linear behavior of the dispersion curve $`E(p)`$ in the neighborhood of $`p=0`$. Landau landau  showed with kinematic arguments that $`v_L=min[E(p)/p]`$. Superfluidity can be observed also in atomic Bose-Einstein condensates (BEC), Bogoliubov equations indicate that $`v_L`$ is equal to the local speed of sound. The first evidence of a critical velocity in a BEC was obtained by stirring the condensate with a laser beam raman , but the observed critical velocity was much lower than the speed of sound, because of the presence of quantized vortices matthews ; madison .

A recent experiment ketterle  demonstrated the superfluid suppression of scattering in agreement with the Landau criterion. This outcome was obtained by propagating microscopic impurities through the condensate. The impurities were created by a Raman transition from the $`|F=1,m_F=1`$ state to the untrapped $`|F=1,m_F=0`$ state. The velocity acquired by the untrapped atoms was due mainly to gravitational acceleration. The radial trapping frequency was varied to change the velocity of sound and the average impurity velocity. The number of the overall scattered atoms was evaluated for some values of the radial frequency. A suppression of the scattering was observed when the average velocity was near the Landau velocity at the center of the condensate. In Ref. ketterle,  a zero-temperature theory is used to evaluate the scattering rate nota .

In this work we first evaluate the scattering rate at finite temperature for an homogeneous system, demonstrating that the thermal cloud can enhance the scattering rate. This effect would provide an indirect measurement of the condensate temperature. We then evaluate the number of scattered atoms in a trapped system and show that the thermal atoms may have an observable effect upon the experimental data of Ref. ketterle, . Furthermore, we calculate the variation of temperature per impurity atom, showing that the impurity collisions cool the condensate for tight confinements.

The scattering rate at $`T=0`$ can be evaluated using Fermi’s golden rule pines ; ketterle ,

$`\mathrm{\Gamma }=n_0\left({\displaystyle \frac{2\mathrm{}a}{M}}\right)^2{\displaystyle 𝑑q𝑑\mathrm{\Omega }q^2S(q)}`$
$`\times \delta \left({\displaystyle \frac{\mathrm{}\stackrel{}{k}\stackrel{}{q}}{M}}{\displaystyle \frac{\mathrm{}q^2}{2M}}\omega _q^B\right),`$ (1)
where $`n_0`$ is the condensate density, $`M`$ the atomic mass, $`a`$ the scattering length for s wave collisions between the impurity atoms and the condensate atoms, and $`S(q)=\omega _q^0/\omega _q^B`$ the static structure factor of the condensate, with $`\mathrm{}\omega _q^0=\mathrm{}^2q^2/2M`$ and $`\mathrm{}\omega _q^B=\sqrt{\mathrm{}\omega _q^0(\mathrm{}\omega _q^0+2\mu )}`$ being the energies of a free particle and a Bogoliubov quasiparticle of momentum $`q`$, respectively. $`\mu `$ is the chemical potential.

In the scattering process an impurity atom changes its momentum and a phonon in the condensate is created. If the temperature is finite and the phononic modes are already populated we expect that the scattering is enhanced because of the bosonic stimulation, i.e.,

$`\mathrm{\Gamma }_1(\beta )=n_0\left({\displaystyle \frac{2\mathrm{}a}{M}}\right)^2{\displaystyle 𝑑q𝑑\mathrm{\Omega }q^2S(q)}`$
$`\times \delta \left({\displaystyle \frac{\mathrm{}\stackrel{}{k}\stackrel{}{q}}{M}}{\displaystyle \frac{\mathrm{}q^2}{2M}}\omega _q^B\right){\displaystyle \frac{e^{\beta \mathrm{}\omega _q^B}}{e^{\beta \mathrm{}\omega _q^B}1}},`$ (2)
where $`1/\beta T`$ is the condensate temperature.

At finite temperatures there is another important channel that contributes to $`\mathrm{\Gamma }`$: in a scattering process an impurity can change its momentum annihilating a phonon. In this case a thermal atom loses energy and increases the condensate population (this picture is exact for non-interacting atoms, but it is not completely appropriate for interacting ones), therefore the second channel is important because a single quantum state is macroscopically populated. We get the following additional contribute (cooling scattering rate)

$`\mathrm{\Gamma }_2(\beta )=n_0\left({\displaystyle \frac{2\mathrm{}a}{M}}\right)^2{\displaystyle 𝑑q𝑑\mathrm{\Omega }q^2S(q)}`$
$`\times \delta \left({\displaystyle \frac{\mathrm{}\stackrel{}{k}\stackrel{}{q}}{M}}{\displaystyle \frac{\mathrm{}q^2}{2M}}+\omega _q^B\right){\displaystyle \frac{1}{e^{\beta \mathrm{}\omega _q^B}1}}.`$ (3)
There are two differences between $`\mathrm{\Gamma }_1`$ and $`\mathrm{\Gamma }_2`$. First, in the Dirac’s delta the sign of $`\omega _q^B`$ and $`\stackrel{}{k}`$ are changed, because a phonon is annihilated in the second channel $`(II)`$, whereas it is created in the first one $`(I)`$. The second difference is the additional temperature-dependent factor. For $`\mathrm{\Gamma }_1`$ it is nonzero even for $`T=0`$ (spontaneous transition), whereas for $`\mathrm{\Gamma }_2`$ it is zero at $`T=0`$. In fact, no phonon can be annihilated if it does not exist.

$`\mathrm{\Gamma }_1`$ can be evaluated by a one-dimensional integration,

$$\mathrm{\Gamma }_1=8\pi n_0a^2\frac{v}{\eta ^2}Q_\eta \left(\frac{1}{2}\beta Mc^2\right),$$
(4)
where $`v`$ is the impurity velocity, $`\eta v/c`$, $`c`$ is the velocity of sound and $`Q_\eta `$ stays for

$$Q_\eta (\overline{\beta })=_1^h𝑑xx(1x^2)^2\frac{e^{\overline{\beta }\left(x^21/x^2\right)}}{e^{\overline{\beta }\left(x^21/x^2\right)}1},$$
(5)
$`h`$ being equal to $`max[1,\eta ]`$. The cross section is $`\sigma _1=\mathrm{\Gamma }_1/n_0v`$.

$`\mathrm{\Gamma }_2`$ can be evaluated by a similar integral, but in this case the integration range is independent of $`\eta `$ if $`\eta 1`$. We have

$$\mathrm{\Gamma }_2=8\pi n_0a^2\frac{v}{\eta ^2}P_\eta \left(\frac{1}{2}\beta Mc^2\right),$$
(6)
where

$$P_\eta (\overline{\beta })=_0^h𝑑x\frac{x(1x^2)^2}{e^{\overline{\beta }\left(1/x^2x^2\right)}1},$$
(7)
$`h`$ being equal to $`min[1,\eta ]`$.

Using the transformation $`x1/x`$ it is simple to demonstrate that

$$P_{\eta 1}(\overline{\beta })=\underset{\eta \mathrm{}}{lim}\left[Q_\eta (\overline{\beta })Q_\eta (\mathrm{})\right],$$
(8)
i.e., for $`\eta 1`$, the stimulated dissipative scattering rate is equal to the cooling scattering rate. However for a generic value of $`\eta `$ the cooling scattering rate is always larger than the stimulated dissipative one, because $`Q_\eta (\overline{\beta })Q_\eta (\mathrm{})`$ is a increasing monotonic function in $`\eta `$.

The average impurity-phonon cross section for $`(II)`$ is enhanced by a factor $`n_0`$ because of the presence of the condensate, furthermore for $`\eta >1`$ it depends inversely on $`\eta ^2`$, it grows upon decreasing the impurity velocity or increasing the sound velocity. Therefore in an inhomogeneous trapped condensate the cooling scattering rate is lower near the borders because the condensate density $`n_0`$ and $`c`$ are smaller.

In Fig. 1 we report $`P_1(\overline{\beta })`$ as a function of $`\overline{\beta }`$. Note that the integral $`P_1(\beta Mc^2/2)`$ drops to zero for $`T0`$. Since the number of thermal atoms is approximately proportional to $`1/\beta ^3`$, the behavior of $`P_1(\overline{\beta })\overline{\beta }^3`$, as a function of $`\overline{\beta }`$, is identical to the behavior of the scattering rate divided by the number of thermal atoms. Such function is shown in the inset of Fig. 1. We can see that for sufficiently high temperatures the average scattering rate of a single phonon grows upon decreasing the temperature. This occurs because a larger percentage of phonons fulfills the kinematic conditions.

In Fig. 2 we have plotted $`Q_\eta (\overline{\beta })`$ as a function of $`\overline{\beta }`$ and for some values of $`\eta `$. For a large $`\beta `$, i.e. a small temperature, the stimulated scattering drops to zero and only the spontaneous scattering contributes to $`Q_\eta `$. For $`\beta 0`$ $`Q_\eta \mathrm{}`$, because of the increase of the phonon population.

It is interesting to note that for values of $`\eta `$ near $`1`$ the dissipative scattering rate lowers and becomes zero for $`\eta <1`$, whereas the cooling scattering rate due to $`(II)`$ remains finite. Therefore below the Landau critical velocity the collisions can only annihilate phonons, cooling the condensate. The maximum cooling rate is reached below the critical velocity. It vanishes for an impurity velocity approaching zero, because the required energy of the annihilated phonons increases. Above the critical velocity the cooling collisions can prevail over the dissipative ones for sufficiently high temperatures.

To refer to a realistic situation we apply Eqs. (4) and (6) to the data of Ref. ketterle, . As reported, a variation of the radial trapping frequency between $`165`$ and $`33`$ Hz implies a variation of the speed of sound from $`1.1`$ to $`0.55`$ cm/s. These values require that $`N_0g_{GP}2.18\times 10^{43}Jm^3`$, where $`N_0`$ is the number of condensed atoms and $`g_{GP}=4\pi \mathrm{}^2a_{1,1}/M`$, $`a_{1,1}`$ being the s-wave scattering length of the condensate atoms. In the following we will use this value for $`N_0g_{GP}`$. The impurity atoms are created in an untrapped hyperfine level, therefore they are gravitationally accelerated. For experimental reasons they are produced with an initial axial velocity equal to $`7mm/s`$. The number of scattered atoms is obtained by counting the impurity atoms in a region of the time-of-flight image below the unscattered impurity atoms, where the impurities that have lost kinetic energy are present. Since in this region there are Raman outcoupled thermal $`m_F=0`$ atoms, the number of collided atoms in the counting region is obtained by subtracting the thermal background, determined by counting a similar sized region above the unscattered impurity atoms, where a few collision products are present. This background can be overvalued because some impurities, that have acquired energy by annihilating phonons, can be in the region above the unscattered atoms, where the presence of sole thermal atoms is supposed. In fact in Ref. nota,  the authors conclude that, because of this overvaluation, the data of Ref. ketterle,  are not affected by finite temperature. However, we show now that if the velocity is sufficiently larger than the sound velocity, the atoms that scatter annihilating phonons populate equally both regions.

If the scattering creates a phonon, the impurity loses the velocity $`\stackrel{}{v}_l`$, with $`|\stackrel{}{v}_l|=v\mathrm{cos}\theta c^2/(v\mathrm{cos}\theta )`$. Here $`v`$ is the impurity velocity and $`\theta `$ is the angle between that velocity and the phonon momentum. $`\theta `$ goes from $`0`$ to $`\mathrm{arccos}(c/v)`$, therefore the lost velocity has a direction around the impurity one. Because of this directionality the dissipative scattering products move in the region of the time-of-flight image below the unscattered impurity atoms. If the scattering annihilates a phonon, the impurity increases the velocity by $`\stackrel{}{v}_a`$, with $`|\stackrel{}{v}_a|=c^2/(v\mathrm{cos}\theta )v\mathrm{cos}\theta `$, where $`\theta `$ ranges between $`\mathrm{arccos}(c/v)`$ and $`\pi /2`$. If $`v/c1`$ the acquired velocity is near orthogonal to the impurity velocity, i.e. the cooling scattering products are not confined within a narrow cone as the particles that collide creating phonons. Therefore we expect that the products of $`(II)`$ are equally distributed in both the measurement regions nota2  and thus their contribution is negligible because of the background subtraction method. For example, with $`v/c=2`$ and $`v/c=5`$, $`\theta `$ ranges, respectively, between $`60^o`$ and $`90^o`$ and between $`80^o`$ and $`90^o`$ (the velocities are distributed near the surface of an open umbrella); furthermore its mean value approaches $`90^o`$ upon increasing the temperature.

The problem is complicated both by the inhomogeneity of the condensate and the continuous variation of the impurity direction of motion during the free fall. Therefore to understand or to evaluate the exact contribution of the two collisions channels to the experimental data is not a trivial task. We have calculated only the overall collisional density for each channel.

If the initial axial velocity is small, an impurity produced at the point $`(x,y,z)`$ has the following probability to collide dissipatively ketterle

$$p(x,y,z)=_z^{e(x,y)}𝑑z_1n(x,y,z_1)\sigma _1(\eta ,c(x,y,z_1)),$$
(9)
where $`\eta `$ is determined by the local condensate density and the downward impurity velocity, $`n`$ is the condensate density and $`e(x,y)=\sqrt{2\mu /m\omega _z^2(\omega _x^2x^2+\omega _y^2y^2)/\omega _z^2}`$. $`c(\stackrel{}{x})`$ is $`c_0\sqrt{n(\stackrel{}{x})/n(0)}`$, $`c_0`$ being the speed of sound at the center of the condensate. Note that for $`1/\beta =0`$ the $`\sigma _1`$ function depends only on $`\eta `$, as considered in Ref. ketterle, . As a first approximation, we have taken into account also the axial velocity using the total velocity, and not only the vertical component, to evaluate $`\eta `$. We have also replaced $`dz_1`$ with $`dz_1(v_{}^2+v_z^2)^{1/2}/v_z`$, where $`v_{}`$ and $`v_z`$ are the axial and vertical velocities, respectively. We have supposed that the condensate is nearly homogeneous in the axial direction, so the variation of sound velocity and of $`e(x,y)`$ in that direction is negligible.

The total number of dissipatively scattered atoms is $`C_\beta (\overline{\eta })=𝑑\stackrel{}{r}n_I(\stackrel{}{r})p(\stackrel{}{r})`$, where $`n_I(\stackrel{}{r})`$ is the initial impurity density and $`\overline{\eta }v_g/c_0`$, $`v_g\sqrt{2gz_c}`$ being the average vertical velocity and $`z_c`$ the Thomas-Fermi radius in the z direction. We can assume $`n_In`$ ketterle . In Fig. 3 we have reported (solid lines) $`C_\beta (\overline{\eta })/C_{\mathrm{}}`$ as a function of $`\overline{\eta }`$ and for some values of the temperature $`T`$. $`C_{\mathrm{}}`$ is the collisional density for high velocities and zero temperature. We have reported also the collisional density for the channel $`(II)`$ (dashed line), calculated in a similar fashion. The dashed-dotted line refers to $`(I)`$ and is evaluated for $`T=0`$ and $`v_{}=0`$. We can see that the contribution of the axial velocity is important also for high $`\overline{\eta }`$. This is true especially for $`(II)`$, because the scattering rate is higher for small velocities and, therefore, we have an important contribution at the beginning of the free fall. In particular, for high $`\overline{\eta }`$ the horizontal velocity decreases the scattering rate, because it is higher than $`v_L`$. In fact, the cooling scattering rate has a maximum peak below $`v_L`$. For $`\overline{\eta }=5`$ the temperature extracted from the time-of-flight pictures is about $`100nK`$ kettco . For this value the dissipative scattering rate is enhanced by about $`30\%`$.

For low $`\overline{\eta }`$ the cooling scattering rate is higher than the dissipative one, suggesting that the overall effect of the collisions is the cooling of the condensate. We have calculated for each channel the average energy loss or gain of the trapped system per impurity atom. The temperature growth per impurity atom is $`\mathrm{\Delta }T=\mathrm{\Delta }E/C_N(T)`$, where $`\mathrm{\Delta }E`$ is the energy increase per impurity atom and $`C_N(T)`$ is the heat capacity, which for $`N`$ interacting trapped atoms is stringari

$$C_N=\left(\frac{E}{T}\right)_N=Nk_B\left[12\frac{\zeta (4)}{\zeta (3)}t^3+1.2\gamma \frac{t^2(58t^3)}{(1t^3)^{3/5}}\right].$$
(10)
$`k_B`$ is the Boltzmann constant, $`\zeta `$ the Riemann function, $`t`$ is $`T`$ divided by the critical temperature, and $`\gamma =1.57(N^{1/6}a_{1,1}/a_{ho})^{2/5}`$, $`a_{ho}`$ being the geometric average of the three harmonic oscillator lengths. $`C_N`$ has a very weak dependence upon $`N`$ for $`t1`$, we have used the value $`N=2\times 10^7`$. In Fig. 4 we have reported $`|\mathrm{\Delta }E|`$ as a function of $`\overline{\eta }`$ for each channel and for some values of $`T`$. For small $`\overline{\eta }`$ and high temperatures the cooling rate prevails over the heating one, i.e, the condensate cools. While $`T`$ decreases, the heating rate grows and the mimimum theoretic temperature is reached when the two contributions balance. For a tight trap the typical temperature of a condensate is $`200nK`$. With $`\overline{\eta }=1.5`$, $`T=200nK`$ and $`5\times 10^6`$ impurity atoms the temperature decrease is about $`25nK`$, if we neglect the variation of $`C_N`$ and suppose that the thermalization velocity is larger than the cooling one. For $`\overline{\eta }=0.75`$ $`(\nu _{}300Hz)`$ and $`T=200nK`$, $`|\mathrm{\Delta }T|`$ is $`100nK`$, which is a remarkable value.

In conclusion, we have considered the effects of finite temperature on the scattering of impurity atoms and we have shown that there are two important collision channels. In $`(I)`$ the collisions are dissipative and the impurities lose energy heating the condensate, in $`(II)`$ the impurities acquire energy cooling the condensate. Below the Landau velocity only $`(II)`$ has a non zero scattering rate. We have calculated the scattering rate for each channel with reference to the experimental configuration of Ref. ketterle,  and we have shown that the temperature may have a visible effect upon the experimental data. We have evaluated the energy loss or gain of the trapped atoms and demonstrated that the overall scattering process cools the condensate for tight traps and sufficiently high temperatures. This effect can become much more efficient using different experimental configurations future .

I am grateful to Professor F. T. Arecchi for helpful discussions, A. P. Chikkatur for useful exchange of information and Professor W. Ketterle for valuable comments. This work is partly supported by CNR contract n. CT98.00154.


format: text

text:
# The negative index of refraction demystified

## 1 Introduction

Materials with either negative real relative permittivity or negative real relative permeability at a certain frequency are not uncommon. Consideration of materials for which both these quantities are simultaneously negative and real–valued, commenced with Veselago’s paper of 1968 . Although he pointed out many unusual properties of such materials, including inverse refraction, negative radiation pressure, inverse Doppler effect, over three decades ago, the considerations were completely speculative in view of the lack of a material, or even a nonhomogeneous composite medium, with a relative permittivity having a negative real part and a very small imaginary part. A breakthrough was achieved by Smith et al. , who, developing some earlier ideas by Pendry et al. , presented evidence for a weakly dissipative composite medium displaying negative values for the real parts of its effective permittivity and effective permeability. Their so–called meta–material consists of various inclusions of conducting rings and wires embedded within printed circuit boards. Their conclusions were based on observations from three separate composite mediums.

* Medium 1 consisted of a lattice of ring–like inclusions, which for a certain field configuration was presumed to have a resonant relative permeability $`\mu _{eff}(\omega )`$ of the form

$$\mu _{eff}(\omega )=1\frac{F\omega ^2}{\omega ^2\omega _0^2+i\omega \mathrm{\Gamma }},$$
(1)
where the resonance frequency $`\omega _0`$ depends principally on the geometry of the rings. In this model, dissipation is facilitated by $`\mathrm{\Gamma }`$, and $`F`$ ($`0<F<1`$) is the ratio of the area occupied by a ring and that of a unit cell. For weak dissipation, the real part of $`\mu _{eff}`$ is negative for $`\omega _0<\omega <\omega _0/\sqrt{1F}`$.
* Medium 2 consisted of an included matrix of wires. The effective relative permittivity $`ϵ_{eff}`$ of this composite medium supposedly displays plasma–like behaviour according to

$$ϵ_{eff}(\omega )=1\frac{\omega _p^2}{\omega ^2},$$
(2)
the effective plasma frequency $`\omega _p`$ being dependent on the geometry. In such a medium, $`ϵ_{eff}`$ is negative for $`\omega <\omega _p`$.
* Medium 3 combined the first two, it being postulated that the combination would exhibit negative real–valued permeability and negative real–valued permittivity within a certain frequency range. Although some numerical and experimental evidence was presented in 2000 , the most striking report appeared the following year  and gave preliminary indications of the observation of the so–called negative index of refraction.

Other types of nanostructural combinations with similar response properties can also be devised .

The emergence of a clear terminology is often a difficult process with regards to scientific findings relating to novel effects, something that is also apparent in the present instance. The original classification of the materials exhibiting the effects discussed labelled them left–handed electromagnetic materials . But chiral materials are important subjects of electromagnetics research and the terms left–handedness and right–handedness have been applied to the molecular structure of such materials for well over a century . The continued use of the term left–handed materials (LHMs) for achiral materials in, for example,  will thus confuse the crucial issues. Other authors  are promoting the term backward medium (BW) which presumes the a priori definitions of forward and backward directions. In the most recent contribution  (which also provides the most extensive theoretical and numerical analysis of the negative index of refraction to date), the authors introduce the technical term double negative (DNG) medium to indicate that the real parts of both permittivity and permeability are negative. While sensible enough, such nomenclature conceals the importance of dissipative effects.

In time, a consensus about terminology will undoubtedly emerge; and it is not our aim to contribute to this particular discussion. Instead the purpose of this note is pedagogical. In the first instance, it is important that dissipation be included in the analysis. This was largely neglected in the reports cited earlier, with the exemption of the most recent study .

Secondly, it is desirable to derive the general condition for the type of anomalous propagation that is characteristic of the considered materials: namely, where the phase velocity is directed oppositely to the power flow.

## 2 Plane Wave Propagation

Consider a plane wave propagating along the $`z`$ axis in a linear, homogeneous, isotropic, dielectric–magnetic medium whose relative permittivity and relative permeability are denoted by $`ϵ_r`$ and $`\mu _r`$, respectively. An $`\mathrm{exp}(i\omega t)`$ time–dependence is assumed here. Then

$`𝐄(z)=A\mathrm{exp}(ik_0nz)𝐮_x,`$ (3)
$`𝐁(z)={\displaystyle \frac{1}{i\omega }}\times 𝐄(z)={\displaystyle \frac{nk_0}{\omega }}A\mathrm{exp}(ik_0nz)𝐮_y,`$ (4)
$`𝐇(z)={\displaystyle \frac{n}{\mu _r\eta _0}}A\mathrm{exp}(ik_0nz)𝐮_y,`$ (5)
where $`k_0`$ is the free–space wavenumber, $`\eta _0`$ is the intrinsic impedance of free space, and $`n^2=ϵ_r\mu _r`$. Consequently, the Poynting vector is parallel to the $`z`$ axis and its time–average is given as

$$P_z(n)=\frac{1}{2}𝐮_z\text{ }\text{ }\text{}\text{ }\mathrm{Re}\left[𝐄(z)\times 𝐇^{}(z)\right]=\mathrm{Re}\left[\frac{n}{\mu _r}\right]\frac{|A|^2}{2\eta _0}\mathrm{exp}(2k_0\mathrm{Im}[n]z),$$
(6)
where $`\mathrm{Re}[]`$ and $`\mathrm{Im}[]`$, respectively, denote the operations of taking the real and the imaginary part, whilst  indicates complex conjugation.

Let us now assume a Lorentzian model for $`ϵ_r`$ and $`\mu _r`$. This will include the specified forms (1) and (2) as special cases. Dissipation results from the imaginary parts of $`ϵ_r`$ and $`\mu _r`$ whilst causality dictates that $`\mathrm{Im}[\mu _r]>0`$ and $`\mathrm{Im}[ϵ_r]>0`$, so that $`ϵ_r`$ and $`\mu _r`$ lie in the upper half of the complex plane.

However, there are two resultant complex refractive indexes, $`n_\pm =\pm \sqrt{ϵ_r\mu _r}`$, of which $`n_+`$ lies in the upper half of the complex plane and $`n_{}`$ in the lower half. The situation is summarized in Figure 1 for which the resonant form of (1) was used as representative of both $`ϵ_r(\omega )`$ and $`\mu _r(\omega )`$. Of course, the resonances of $`ϵ_r(\omega )`$ and $`\mu _r(\omega )`$ are unlikely to coincide, so that for a particular value of $`\omega `$, the arrows corresponding to $`ϵ_r`$ and $`\mu _r`$ will not be necessarily parallel. Only the upper half of the complex plane is shown in the figure.

Now $`n_\pm `$ may be written as

$$n_\pm =\pm n_0\mathrm{exp}i\varphi _n,$$
(7)
where

$$n_0=+\sqrt{|ϵ_r||\mu _r|},\varphi _n=\frac{\varphi _ϵ+\varphi _\mu }{2}.$$
(8)
Here $`\varphi _ϵ`$ and $`\varphi _\mu `$, representing the arguments of $`ϵ_r`$ and $`\mu _r`$ respectively, must obey the conditions $`0\varphi _{ϵ,\mu }\pi `$. Consequently, $`0\varphi _n\pi `$. We then always have

$$\mathrm{Re}\left[\frac{n_+}{\mu _r}\right]>0\mathrm{i}.\mathrm{e}.P_z(n_+)>0$$
(9)
and also

$$\mathrm{Re}\left[\frac{n_{}}{\mu _r}\right]<0\mathrm{i}.\mathrm{e}.P_z(n_{})<0.$$
(10)
Thus the choice $`n_+`$ always relates to power flow in the $`+z`$ direction, whilst $`n_{}`$ always relates to power flow in the $`z`$ direction. Since necessarily $`\mathrm{Im}[n_+]>0`$ and $`\mathrm{Im}[n_{}]<0`$, power flow is always in the direction of exponential decrease of the fields’ amplitudes.

We can now identify when the phase velocity is opposite to the direction of power flow. This occurs whenever $`\mathrm{Re}[n_+]<0`$ (and consequently $`\mathrm{Re}[n_{}]>0`$, also). After setting

$$ϵ_r=ϵ_r^{}+iϵ_r^{\prime \prime },\mu _r=\mu _r^{}+i\mu _r^{\prime \prime },$$
(11)
(where $`ϵ_r^{},ϵ_r^{\prime \prime }`$ and $`\mu _r^{},\mu _r^{\prime \prime }`$ are the real and imaginary parts of the relative permittivity and the relative permeability, respectively), the following condition is straightforwardly derived for such propagation:

$$\left[+\left(ϵ_{r}^{}{}_{}{}^{2}+ϵ_{r}^{\prime \prime }{}_{}{}^{2}\right)^{1/2}ϵ_r^{}\right]\left[+\left(\mu _{r}^{}{}_{}{}^{2}+\mu _{r}^{\prime \prime }{}_{}{}^{2}\right)^{1/2}\mu _r^{}\right]>ϵ_r^{\prime \prime }\mu _r^{\prime \prime }.$$
(12)
Before turning to a fully illustrative example in the proceeding section, let us investigate some immediate repercussions of the inequality (12) which is central to this paper.

* Consider, in the first instance, the behaviour at a resonance of the relative permittivity, i.e. $`ϵ_r^{}=0`$, $`ϵ_r^{\prime \prime }>0`$. Then, (12) reduces to

$$\left[+\left(\mu _{r}^{}{}_{}{}^{2}+\mu _{r}^{\prime \prime }{}_{}{}^{2}\right)^{1/2}\mu _r^{}\right]>\mu _r^{\prime \prime },$$
(13)
an inequality that is always fulfilled when $`\mu _r^{}<0`$.

Likewise, at a resonance of the relative permeability, i.e. $`\mu _r^{}=0`$, $`\mu _r^{\prime \prime }>0`$, (12) is fulfilled whenever $`ϵ_r^{}<0`$.
* Further insight into inequality (12) can be gained by requiring that

$$+\left(ϵ_{r}^{}{}_{}{}^{2}+ϵ_{r}^{\prime \prime }{}_{}{}^{2}\right)^{1/2}>ϵ_r^{}+ϵ_r^{\prime \prime }$$
(14)
and

$$+\left(\mu _{r}^{}{}_{}{}^{2}+\mu _{r}^{\prime \prime }{}_{}{}^{2}\right)^{1/2}>\mu _r^{}+\mu _r^{\prime \prime }$$
(15)
simultaneously hold. Consequently, (12) is definitely satisfied. It should be remarked though, that the parameter space of the permittivity and permeability that fulfils (14) and (15) is only a subset of the one fulfilling (12). In any case, (14) holds if and only if $`ϵ_r^{}<0`$, and (15) holds if and only if $`\mu _r^{}<0`$ (we remind the reader that $`ϵ_r^{\prime \prime }>0`$, $`\mu _r^{\prime \prime }>0`$ because of causality requirements). We note that $`ϵ_r^{}<0`$ and $`\mu _r^{}<0`$ can only occur close to absorption resonances (as discussed in the previous item).
* Finally, consider an electromagnetic wave propagating in a plasma below the plasma frequency ($`ϵ_r^{}<0,\mu _r^{}=1`$) and in which dissipation is very small ($`ϵ_r^{\prime \prime }1`$, $`\mu _r^{\prime \prime }1`$). Straighforward Taylor expansions reduce inequality (12) to

$$|ϵ_r^{}|>\frac{ϵ_r^{\prime \prime }}{\mu _r^{\prime \prime }}.$$
(16)
Therefore, the existence of the type of anomalous propagation being studied here depends in this case crucially on the ratio of the imaginary parts of the relative permittivity and relative permeability. Whether the criterion (16) is satisfied or not, the power flow in this case is in any case small.

## 3 A detailed illustrative case study

Let us exemplify the foregoing in detail by an explicit invocation of the Lorentz model for both $`ϵ_r`$ and $`\mu _r`$; thus,

$`ϵ_r(\lambda _0)=1+{\displaystyle \frac{p_e}{1+\left(N_e^1i\lambda _e\lambda _0^1\right)^2}},`$ (17)
$`\mu _r(\lambda _0)=1+{\displaystyle \frac{p_m}{1+\left(N_m^1i\lambda _m\lambda _0^1\right)^2}}.`$ (18)
Here $`\lambda _0=2\pi /k_0`$ is the free–space wavelength, $`p_{e,m}`$ are the oscillator strengths, $`\lambda _{e,m}(1+N_{e,m}^2)^{1/2}`$ are the resonance wavelengths, while $`\lambda _{e,m}/N_{e,m}`$ are the resonance linewidths.

Figures 2a and 2b comprise plots of the real and imaginary parts of $`ϵ_r`$ and $`\mu _r`$ as functions of $`\lambda _0`$, when $`p_e=1`$, $`p_m=0.8`$, $`N_e=N_m=100`$, $`\lambda _e=0.3`$ mm and $`\lambda _m=0.32`$ mm. Clearly, five separate spectral regions can be identified in Figure 2. At the either extremity of the horizontal axis are the two regions wherein $`ϵ_r^{}>0`$ and $`\mu _r^{}>0`$. In the neighbourhood of $`\lambda _0=0.22`$ mm, $`ϵ_r^{}<0`$ but $`\mu _r^{}>0`$. Both $`ϵ_r^{}<0`$ and $`\mu _r^{}<0`$ in the neighbourhood of $`\lambda _0=0.25`$ mm. Finally, $`ϵ_r^{}>0`$ but $`\mu _r^{}<0`$ around $`\lambda _0=0.31`$ mm. Of course, both $`ϵ_r^{\prime \prime }>0`$ and $`\mu _r^{\prime \prime }>0`$ for all $`\lambda _0`$.

Detailed calculations confirm that the spectral region wherein the inequality (12) is satisfied is larger than the middle region (wherein both $`ϵ_r^{}<0`$ and $`\mu _r^{}<0`$). The former cover parts of the adjoining regions, in which either (14) or (15) holds.

In the five spectral regions identified, the isotropic dielectric–magnetic medium would respond differently to monochromatic electromagnetic excitation. Suppose that a plane wave is normally incident on a half–space occupied by this medium. The reflectance $`R(\lambda _0)`$ is then given by the standard expression

$$R(\lambda _0)=\left|\frac{+\sqrt{\mu _r(\lambda _0)/ϵ_r(\lambda _0)}1}{+\sqrt{\mu _r(\lambda _0)/ϵ_r(\lambda _0)}+1}\right|^2,$$
(19)
where $`0R1`$ for all $`\lambda _0`$ by virtue of the principle of conservation of energy. The reflectance spectrum calculated with the constitutive parameters used for Figures 2a and 2b is shown in Figure 3. The reflectance is markedly high in the two regions wherein $`ϵ_r^{}`$ and $`\mu _r^{}`$ have opposite signs, but not in the other three regions. The reflectance is particularly low in the leftmost and the rightmost regions ($`ϵ_r^{}>0`$ and $`\mu _r^{}>0`$) because the ratio $`\mu _r(\lambda _0)/ϵ_r(\lambda _0)`$ is close to unity therein. However, the reflectance is somewhat higher in the central region ($`ϵ_r^{}<0`$ and $`\mu _r^{}<0`$) because $`|\mu _r(\lambda _0)/ϵ_r(\lambda _0)|<0.25`$.

## 4 Conclusions

In this pedagogical note, we have derived a general condition for the phase velocity to be oppositely directed to the power flow in isotropic dielectric–magnetic mediums in which the only constraints on the values of the relative permittivity and relative permeability are those imposed by causality. In this regard, the topical case of mediums in which $`ϵ_r`$ and $`\mu _r`$ have negative real parts is seen to be a sufficient, but not necessary, condition for such propagation, as noted in the comments succeeding (12). An illustrative case study has shown that there are, in general, five distinct spectral regions, characterized by the various sign combinations of the real parts of $`ϵ_r`$ and $`\mu _r`$.

## 5 Acknowledgement

MWM acknowledges the support of the Engineering and Physical Sciences Research Council of Great Britain (EPSRC grant no. GR/R55078/01).

## References

Figure Captions

Figure 1. Argand diagram parametrically displaying $`\mu _{eff}(\omega )`$ from equation (1), with $`\mathrm{\Gamma }=0.1\omega _0`$ and $`F=0.5`$. On taking (1) as a model resonance form for meta–materials, the plot can also be regarded as displaying the effective permittivity $`ϵ_{eff}`$, for which the resonance at $`\omega =\omega _0`$ is unlikely to coincide, and hence the arrows indicating $`ϵ_{eff}`$ and $`\mu _{eff}`$ do not coincide in general. The complex number $`n_+=+\sqrt{ϵ_{eff}\mu _{eff}}`$, while the corresponding index $`n_{}=\sqrt{ϵ_{eff}\mu _{eff}}`$ is not shown. The dots indicate equi–spaced frequencies from $`\omega =0`$ to $`\omega =2\omega _0`$.

Figure 2. (a) Real parts of the relative permittivity and relative permeability according to equations (17) and (18), respectively, when $`p_e=1`$, $`p_m=0.8`$, $`N_e=N_m=100`$, $`\lambda _e=0.3`$ mm and $`\lambda _m=0.32`$ mm. The significance of the identified five regions of the spectrum is explained in the text. (b) Imaginary parts of the relative permittivity and relative permeability according to equations (17) and (18), respectively, when $`p_e=1`$, $`p_m=0.8`$, $`N_e=N_m=100`$, $`\lambda _e=0.3`$ mm and $`\lambda _m=0.32`$ mm.

Figure 3. Plane wave reflectance $`R(\lambda _0)`$ calculated with the constitutive parameters depicted in Figures 2.


text:
# 1 The contribution to nucleon axial charge from distances r<R.

Nonlocality of the Nucleon Axial Charge and Solar Neutrino Problem

N.I. Kochelev

Bogolyubov Laboratory of Theoretical Physics,
Joint Institute for Nuclear Research,
Dubna, Moscow region, 141980 Russia

## Abstract

It is shown that the specific space distribution of the nucleon axial charge may lead to the significant reduction of the cross section of the reaction $`p+pD+e^++\nu `$ and may provide the mechanism to explain observed deficit of solar neutrinos.

The deficit of solar neutrinos is one of the longstanding unsolved problem in astrophysics (see review ). The reaction $`p+pD+e^++\nu `$ is most important process which cross section determines the solar neutrino flux from pp cycle. Its value has never been directly measured and only theoretical predictions exist so far. There is a wide spread opinion that theoretical uncertainties in the calculation are very small and therefore one can conclude that it is impossible to explain the small observed flux of solar neutrinos without involving new physics (e.g. neutrino oscillations etc).

In this Letter we will show that rather extended space distribution of nucleon axial charge may lead to significant reduction of the cross section of the reaction $`p+pD+e^++\nu `$.

The main assumption which was used to calculate the rate of this reaction was the hypothesis of the locality of nucleon axial charge . As the result, the cross section is proportional to product of two factors

$$\sigma _{FA}^{p+pD+e^++\nu }g_A^2|\mathrm{\Psi }_D^{}\mathrm{\Psi }_{pp}𝑑\stackrel{}{r}|^2,$$
(1)
where factor $`g_A`$, axial charge of nucleon, comes from weak interaction matrix element, and second factor is overlapping of $`\mathrm{\Psi }_D`$, deuteron wave function and $`\mathrm{\Psi }_{pp}`$, the initial wave function of two protons. We should emphasize that such approach can be correct only for the point-like distribution of the nucleon axial charge, i.e. only for the case when the characteristic scale of axial charge distribution is much smaller than the corresponding scale related to overlapping of initial and final hadron wave functions.

Recently Jaffe has shown  that the distribution of axial charge of the nucleon is rather nonlocal and in chiral limit $`m_\pi 0`$ one third of $`g_A`$ comes from infinite distance $`R\mathrm{}`$ from the center of nucleon. It means that in this limit one should expect that cross section of the reaction $`p+pD+e^++\nu `$ should be much smaller than its factorized value (1)

$$\sigma ^{p+pD+e^++\nu }(m_\pi 0)=\frac{4}{9}\sigma _{FA}^{p+pD+e^++\nu }.$$
(2)
The chiral limit is a rather good approximation for many calculations in hadronic physics and therefore it would be difficult to believe that factorization hypothesis would give the correct answer in the case of the physical pion mass.

For finite mass of pion the contribution to axial charge from the distances $`r<R`$ is

$$g_A(R)=g_A(1\frac{1}{3}(1+m_\pi R)e^{m_\pi R}),$$
(3)
where $`g_A=1.26`$ is total nucleon axial charge. In Fig.1 the distribution of $`g_A(R)`$ is shown. It is evident that the distribution is quite extended and therefore the locality approximation which was used to get Eq.(1) is not very well justified.

Nonlocality of axial charge leads to suppression of the reaction $`p+pD+e^++\nu `$ due to smaller value of effective $`\stackrel{~}{g}_A`$ which should enter in Eq. (1).

One can roughly estimates the effect of suppression by using the formula

$$\frac{\sigma ^{p+pD+e^++\nu }(m_\pi )}{\sigma _{FA}^{p+pD+e^++\nu }}\frac{g_A^2(R_{eff})}{g_A^2}.$$
(4)
In Eq.(4) $`R_{eff}`$ is the effective size of interaction region which should be of the order of a characteristic size of deutron $`r_m2fm`$, defined as the rms-half distance between two nucleons

$$r_m^2=\frac{1}{4}_0^{\mathrm{}}(u^2(r)+w^2(r))r^2𝑑r,$$
(5)
with $`u(r)`$ and $`w(r)`$ are $`S`$ and $`D`$ waves of deuteron.  111 More accurate estimation will be published elsewhere.. Therefore we get the large reduction factor of

$$\frac{\sigma ^{p+pD+e^++\nu }(m_\pi )}{\sigma _{FA}^{p+pD+e^++\nu }}0.65.$$
(6)
Thus, it is shown that nonlocality of the nucleon axial charge may lead to the large decreasing of the rate of the basic solar reaction for neutrino production and may give the mechanism to explain the solar neutrino deficiency.

The author is grateful to A.E.Dorokhov, V.A. Bednyakov, S.B. Gerasimov, E.A.Kuraev and V.Vento for useful discussion. This work is partially supported by RFBR-01-02-16431 and INTAS-2000-366 grants.


text:
# Ion Trap Proposal for Quantum Search

## Acknowledgement

J. Bae is supported in part by the Fellowship of Hanyang University and Y. Kwon is supported in part by the Fund of Hanyang University.


text:
# Asymptotically efficient triangulations of the 𝑑-cube

## 1. Introduction

“Simple” triangulations of the regular $`d`$-cube $`I^d=[0,1]^d`$ have several applications, such as solving differential equations by finite element methods or calculating fixed points. See, for example, . In particular, it has brought special attention both from a theoretical point of view and from an applied one to determine the smallest size of a triangulation of the $`d`$-cube (see \[8, Section 14.5.2\] for a recent survey). Let us point up that the general problem of computing the smallest triangulation of an arbitrary polytope is NP-complete even when restricted to dimension 3, see .

When we speak about *triangulations* of a polytope $`P`$ of dimension $`d`$ we mean decompositions of $`P`$ into $`d`$-simplices that (i) use as vertices only vertices of $`P`$, and (ii) intersect face to face (i.e., forming a geometric simplicial complex). Some authors do not require these two conditions in triangulations. We will always require the first one, and when the second condition is not fulfilled, we call the decompositions *simplicial dissections* of $`P`$. The *size* of a triangulation or dissection $`T`$ is its number of $`d`$-simplices and we denote it $`|T|`$. It is an open question whether high dimensional cubes admit dissections with less simplices than needed in a triangulation. Actually, the minimum size of dissections of $`I^7`$ is unknown, while the minimum triangulation is known (see below).

The paper  describes a general method to obtain the smallest triangulation of a polytope $`P`$ as the optimal integer solution of a certain linear program. The linear program has as many variables as $`d`$-simplices with vertex set contained in the vertices of $`P`$ exist. That is, $`\left(\genfrac{}{}{0pt}{}{\mathrm{\#}\text{vertices}}{dim(P)+1}\right)`$ if the vertices of $`P`$ are in general position and less than that if not. For the $`d`$-cube, the direct application of this method is impossible in practice beyond dimension 4 or 5. With a somewhat similar method but simplifying the system of equations via the symmetries of the cube, Anderson and Hughes  have calculated the smallest size among triangulations of the $`6`$-cube and the $`7`$-cube, in a computational *tour-de-force* which involved a problem with 1 456 318 variables and *ad hoc* ways of decomposing the system into smaller subsystems. The smallest sizes up to dimension 7 is shown in Table 1.

In order to compare sizes of triangulations of cubes in different dimensions, Todd  defines the *efficiency* of a triangulation $`T`$ of the $`d`$-cube to be the number $`(|T|/d!)^{\frac{1}{d}}`$. This number is at most 1, since every simplex with integer vertices has a multiple of $`1/d!`$ as Euclidean volume, so $`|T|d!`$. Triangulations of efficiency 1 (i.e., unimodular) can be easily constructed in any dimension. On the other extreme, Hadamard’s inequality for determinants of matrices with coefficients in $`[1,1]`$ implies that the volume of every $`d`$-simplex inscribed in the regular $`d`$-cube $`I^d=[0,1]^d`$ is at most $`(d+1)^{(d+1)/2}/2^dd!`$. Hence, every triangulation has size at least $`2^dd!/(d+1)^{(d+1)/2}`$ and efficiency at least $`2/(d+1)^{\frac{d+1}{2d}}2/\sqrt{d+1}`$.

Following the notation in \[8, Section 14.5.2\], let $`\varphi _d`$ and $`\rho _d`$ be the smallest size and efficiency, respectively, of all triangulations of the cube of dimension $`d`$. The number $`\varphi _d`$ (or some variations in which one or both of the conditions (i) and (ii) are not required) is known as *simplexity* of the $`d`$-cube. Obviously, $`\rho _d=(\varphi _d/d!)^{1/d}`$.

In  (see also , pages 283-284), Haiman observes that a triangulation of $`I^{k+l}`$ with $`t_kt_l\left(\genfrac{}{}{0pt}{}{k+l}{k}\right)`$ simplices can be constructed from given triangulations of $`I^k`$ and $`I^l`$ with $`t_k`$ and $`t_l`$ simplices respectively. With this, one easily concludes:

###### Theorem 1.1 (Haiman).

For every $`k`$ and $`l`$, $`\rho _{k+l}^{}{}_{}{}^{k+l}\rho _{k}^{}{}_{}{}^{k}\rho _{l}^{}{}_{}{}^{l}`$.

###### Corollary 1.2.

The sequence $`(\rho _i)_i\text{}`$ converges and

$$\underset{i\mathrm{}}{lim}\rho _i\rho _dd\text{}.$$

###### Proof.

Let us fix $`d\text{}`$ and $`k\{1,\mathrm{},d\}`$. Haiman’s theorem implies that, for every $`i\text{}`$,

$$\rho _{k+id}\rho _{k}^{}{}_{}{}^{k/(k+id)}\rho _{d}^{}{}_{}{}^{id/(k+id)}.$$

Since the right-hand side converges to $`\rho ^d`$ when $`i`$ grows, the $`d`$ subsequences of indices modulo $`d`$, and hence the whole sequence $`(\rho _i)_i\text{}`$, have upper limit bounded by $`\rho _d`$. An upper limit bounded by every term in the sequence must coincide with the lower limit. ∎

What is the limit of this sequence? In particular, is it positive or is it zero? The known values of $`\rho _d`$ (up to $`d=7`$) form a strictly decreasing sequence, as shown in Table 1, but it is not even known whether this occurs in general.

Concerning lower bounds, the only significant improvement to Hadamard’s inequality has been obtained in , where the same volume argument is used, but with respect to a hyperbolic metric. The last row of the Table 1 shows the lower bound obtained, translated into efficiency of triangulations. For small dimensions, it is an excellent approximation of the smallest efficiency. Asymptotically, it only increases the lower bound obtained using Hadamard’s inequality by a constant factor $`\sqrt{3/2}`$.

In this paper we propose a method to obtain efficient triangulations of a product polytope $`P\times Q`$ starting from a triangulation of $`Q`$ and another of $`P\times \mathrm{\Delta }^{m1}`$, where $`\mathrm{\Delta }^{m1}`$ denotes a simplex of dimension $`m1`$ and $`m`$ is any relatively small number. We apply this with $`P`$ being a small-dimensional cube and $`Q`$ a high-dimensional one, iteratively. This allows to obtain asymptotically efficient triangulations of arbitrarily high-dimensional cubes from any (efficient) triangulation of $`I^l\times \mathrm{\Delta }^{m1}`$. Sections 3, 4, and 5 explain our method, which is first outlined in Section 2. If the reader is happy with dissections, we cannot offer better efficiencies for them than for triangulations, but at least he or she can skip Section 5, which contains most of the technicalities in this paper.

The asymptotic efficiency of the triangulations obtained, clearly, depends on how good our triangulation of $`I^l\times \mathrm{\Delta }^{m1}`$ is. Finding the triangulation of $`I^l\times \mathrm{\Delta }^{m1}`$ which is optimal for our purposes reduces to an integer programming problem, similar to finding the smallest triangulation of that polytope (actually, it is the same system of linear equations, with a different objective function). Using the linear programming software CPLEX, we have solved the system for some values of $`l`$ and $`m`$. The best triangulation we have found is one of $`I^3\times \mathrm{\Delta }^2`$, with which we obtain

$$\underset{i\mathrm{}}{lim}\rho _i\sqrt[3]{\frac{44/3}{27}}0.8159$$

The best bound existing before was $`lim_i\mathrm{}\rho _i\rho _7=0.840`$. In other words, we prove that (asymptotically) the $`d`$-cube can be triangulated with $`0.8159^dd!`$ simplices, instead of the $`0.840^dd!`$ achievable before.

It has to be observed that, even if the particular triangulation of $`I^3\times \mathrm{\Delta }^2`$ that we use was obtained by an intensive computer calculation, once the triangulation is found it is a simple task to check that it is indeed a triangulation and compute the asymptotic efficiency obtained from it. Actually, in Section 7 we use the so-called Cayley Trick  to do this checking with no need of computers at all. We also use the Cayley Trick to explore the minimum efficiency that can be obtained from the product $`I^2\times \mathrm{\Delta }^k`$ for any $`k`$. We briefly explain the trick in Section 6, where we also interpret our whole construction in terms of it.

## 2. Overview of the method and results

We start describing Haiman’s proof of Theorem 1.1, which is related to our method. Let $`T_k`$ and $`T_l`$ be triangulations of the regular cubes $`I^k`$ and $`I^l`$, respectively. The product $`T_k\times T_l`$ of the two triangulations gives a decomposition of the cube $`I^k\times I^l=I^{k+l}`$ into $`|T_k||T_l|`$ subpolytopes, each of them isomorphic to the product of simplices $`\mathrm{\Delta }^k\times \mathrm{\Delta }^l`$. It is well known that every triangulation of $`\mathrm{\Delta }^k\times \mathrm{\Delta }^l`$ has size $`\left(\genfrac{}{}{0pt}{}{k+l}{k}\right)`$ (see, e.g., \[5, Chapter 7\]). Hence, refining $`T_k\times T_l`$ in an arbitrary way one gets a triangulation of $`I^{k+l}`$ of size $`|T_k||T_l|\left(\genfrac{}{}{0pt}{}{k+l}{k}\right)`$. The implication of this is that starting with a triangulation of a cube $`I^k`$ of a certain efficiency $`\rho `$, one can construct a sequence of triangulations of $`I^{nk}`$ for $`n\text{}`$ whose asymptotic efficiencies converge to $`\rho `$.

Our method is, in a way, similar. Starting from a triangulation of $`I^{n1}`$ and another one of $`I^l\times \mathrm{\Delta }^{m1}`$, we get one of $`I^{l+n1}`$ with the following general method to triangulate $`P\times Q`$ starting from a triangulation of $`Q`$ and another one of $`P\times \mathrm{\Delta }^{m1}`$:

1. We first show (Sections 3 and 4) how to obtain triangulations of $`P\times \mathrm{\Delta }^{n1}`$ from triangulations of $`P\times \mathrm{\Delta }^{m1}`$, where $`n1=dim(Q)`$ is supposed to be much bigger than $`m1`$. We call our triangulations *multi-staircase triangulations*.
2. A triangulation of $`Q`$ induces, as in Haiman’s method, a decomposition of $`P\times Q`$ into polytopes isomorphic to $`P\times \mathrm{\Delta }^{n1}`$. Each of them can be triangulated using the previous paragraph, although this in principle only gives a dissection of $`P\times Q`$; if we want a triangulation, we have to apply (1) to all the polytopes $`P\times \mathrm{\Delta }^{n1}`$ in a compatible way. In Section 5 we will show how to do this using an $`m`$-coloring of the vertices of $`Q`$.
3. The analysis of the size of the triangulation obtained will also be carried out in Section 5.

In step (2), the final size of the triangulation is just the sum of the individual sizes of the triangulations used for the different subpolytopes $`P\times \mathrm{\Delta }^{n1}`$. In particular, if we are just interested in obtaining dissections, we can take an efficient triangulation of $`P\times \mathrm{\Delta }^{n1}`$ and repeat it in every subpolytope.

In step (1) the computation of the size is more complicated and to state it in a simple way we introduce the following definitions. When we speak about simplices in a polytope $`P`$ we will implicitly suppose that its vertices are vertices of $`P`$, and we will identify the simplex with its vertex set.

###### Definition 2.1.

Let $`P`$ be a polytope of dimension $`l`$ and let $`\tau `$ be a simplex of dimension $`l+m1`$ in $`P\times \mathrm{\Delta }^{m1}`$. Let $`\{v_1,\mathrm{},v_m\}`$ be the vertices of $`\mathrm{\Delta }^{m1}`$. Then, $`\tau `$, understood as a vertex set, decomposes as $`\tau =\tau _1\mathrm{}\tau _m`$ with $`\tau _iP\times \{v_i\}`$.

1. We define the sequence $`(|\tau _1|1,\mathrm{},|\tau _m|1)`$ to be the *type* of the simplex $`\tau `$. The *weight* of a simplex $`\tau `$ of type $`(t_1,\mathrm{},t_m)`$ is the number $`\frac{1}{_{i=1}^mt_i!}.`$
2. The *weighted size* of a triangulation $`T`$ of $`P\times \mathrm{\Delta }^{m1}`$ is $`_{\tau T}\mathrm{weight}(\tau )`$, and the *weighted efficiency* is

$$\sqrt[l]{\frac{\underset{\tau T}{}\mathrm{weight}(\tau )}{m^l}}$$

With this, our main result can be stated as:

###### Theorem 2.2.

Consider polytopes $`P`$ of dimension $`l`$ and $`Q`$ of dimension $`n1`$. Let $`m`$ be such that $`mn`$. Given a triangulation $`T_0`$ of $`P\times \mathrm{\Delta }^{m1}`$ of weighted size $`t_0`$ and a triangulation $`T_Q`$ of $`Q`$, then there are triangulations of $`P\times Q`$ with size at most

$$|T_Q|t_0\left(\frac{n}{m}+l\right)^l.$$

Using this method to triangulate $`I^{l+n1}=I^l\times I^{n1}`$ starting from a triangulation of $`I^{n1}`$ and another one of $`I^l\times \mathrm{\Delta }^{m1}`$ we will conclude:

###### Theorem 2.3.

If there is a triangulation $`T_0`$ of $`I^l\times \mathrm{\Delta }^{m1}`$ with weighted efficiency $`\rho _0`$, then for every $`ϵ>0`$ and all $`n`$ bigger than $`lm\rho _0/ϵ`$ we have

$$\rho _{n+l1}^{}{}_{}{}^{n+l1}\rho _{n1}^{}{}_{}{}^{n1}(\rho _0+ϵ)^l.$$

As a consequence,

$$\underset{i\mathrm{}}{lim}\rho _i\rho _0.$$

Observe that the definition of weighted efficiency makes sense even in the case $`m=1`$, where all the simplices of $`P\times \mathrm{\Delta }^0`$ have the same type, equal to $`(l)`$ if $`dim(P)=l`$, and the same weight, equal to $`1/l!`$. In particular, the weighted efficiency of a triangulation of $`I^l\times \mathrm{\Delta }^0`$ is the same as the usual “non-weighted” one. Another common point between efficiency and weighted efficiency is that the weighted efficiency of a triangulation of $`I^l\times \mathrm{\Delta }^{m1}`$ is always less or equal to 1, and it is 1 if and only if the triangulation is unimodular; i.e., if every simplex has volume $`1/(l+m1)!`$ (this is proved in Section 6).

We now describe the practical results obtained. The last theorem leads us to study the smallest weighted efficiency of triangulations of $`I^l\times \mathrm{\Delta }^{m1}`$; let us denote it by $`\rho _{l,m}`$. This number can be calculated minimizing a linear form over the so-called *universal polytope* of all the triangulations of $`I^l\times \mathrm{\Delta }^{m1}`$.

The definition of this universal polytope for triangulations of an arbitrary polytope $`P`$ is as follows (see  for further details): let $`\mathrm{\Sigma }(P)`$ be the set of all the simplices of maximal dimension which use as vertices only vertices of $`P`$. Given a triangulation $`T`$ of $`P`$, its *incidence vector* $`V_T\text{}^{\mathrm{\Sigma }(P)}`$ has a 1 in the coordinates corresponding to simplices of $`T`$ and a 0 in the others. The *universal polytope* of $`P`$ is $`\mathrm{conv}\{V_T:T\text{ is a triangulation of }P\}`$.

In our case, to calculate the smallest weighted size (and efficiency), we have to minimize over the universal polytope of $`I^l\times \mathrm{\Delta }^{m1}`$ the linear form having as coefficient of each simplex its weight $`1/_{i=1}^mt_i!`$. (To minimize non-weighted efficiency and size one just uses the functional with all coefficients equal to 1). One of the results in  is a description of the vertices of the universal polytope as integer solutions of a certain system of linear inequalities derived from the oriented matroid of $`P`$. Thus, our minimization problem is restated as an integer linear programming problem.

In order to apply our method, we have used the program UNIVERSAL BUILDER by Jesús A. de Loera and Samuel Peterson . Given as input the vertices of $`P`$, the program generates the linear system of equations defining the universal polytope of $`P`$. The output is a file readable by the linear programming software CPLEX. We have created a routine that generates our particular objective function. Table 2 shows the results obtained in the cases we have been able to solve. Note that $`\rho _{l,1}=\rho _l`$ and so the column $`m=1`$ in Table 2 is the same as the second row of Table 1.

The fact that $`\rho _{1,m}=1`$ for every $`m`$ reflects that every triangulation of the prism $`I\times \mathrm{\Delta }^{m1}`$ is unimodular. In the case of $`\rho _{2,m}`$ we prove (Subsection 7.1) that the smallest weighted efficiency is always $`\sqrt{3m^2/4/m^2}`$. That is to say, $`\sqrt{3/4}`$ for even $`m`$ and $`\sqrt{3/4}+\mathrm{\Theta }(m^2)`$ for odd $`m`$.

The computation of $`\rho _{3,3}`$ involved a system with 74 400 variables, whose resolution by CPLEX took 37 hours of CPU on a SUN UltraSparc.

## 3. Polyhedral subdivision of $`P\times \mathrm{\Delta }^{k_1+\mathrm{}+k_m1}`$ induced by a polyhedral subdivision of $`P\times \mathrm{\Delta }^{m1}`$

We call *polyhedral subdivisions* of a polytope $`P`$ its face-to-face partitions into subpolytopes which only use vertices of $`P`$ as vertices.

Let $`P`$ be a polytope of dimension $`l`$. Let $`m`$ and $`k_1,\mathrm{},k_m`$ be natural numbers and let us call $`n:=k_1+\mathrm{}+k_m`$. Let $`v_1,\mathrm{},v_m`$ be the $`m`$ vertices of the standard simplex $`\mathrm{\Delta }^{m1}`$ and $`v_1^1,\mathrm{},v_{k_1}^1,\mathrm{}\mathrm{},v_1^m,\mathrm{},v_{k_m}^m`$ the vertices of $`\mathrm{\Delta }^{n1}`$. Observe that, implicitly, we have the following surjective map:

| $`\mathrm{vert}(\mathrm{\Delta }^{n1})`$ | $``$ | $`\mathrm{vert}(\mathrm{\Delta }^{m1})`$ |
| --- | --- | --- |
| $`v_j^i`$ | $``$ | $`v_i`$ |

This map uniquely extends to an affine projection $`\pi _0:\mathrm{\Delta }^{n1}\mathrm{\Delta }^{m1}`$. In turn, this induces a projection

| $`\pi =\mathrm{}\times \pi _0:P\times \mathrm{\Delta }^{n1}`$ | $``$ | $`P\times \mathrm{\Delta }^{m1}`$ |
| --- | --- | --- |
| $`(p,a)`$ | $``$ | $`(p,\pi _0(a))`$ |

Given the projection $`\pi `$ and a polyhedral subdivision $`S`$ of the target polytope $`P\times \mathrm{\Delta }^{m1}`$, it is obvious that the inverse images $`\pi ^1(B)`$ of the subpolytopes of $`S`$ form a subdivision of $`P\times \mathrm{\Delta }^{n1}`$ into subpolytopes matching face to face. In a more general projection it would not be true that those subpolytopes use as vertices only vertices of $`P\times \mathrm{\Delta }^{n1}`$. But it is true in our case:

###### Lemma 3.1.

Let $`BP\times \mathrm{\Delta }^{m1}`$ be a subpolytope with $`\mathrm{vert}(B)\mathrm{vert}(P\times \mathrm{\Delta }^{m1})`$. Let $`\pi `$ be the projection considered before. Let be $`\stackrel{~}{B}=\{(p,v_j^i):(p,v_i)\mathrm{vert}(B)\}`$. Then:

$$\pi ^1(B)\mathrm{conv}(\stackrel{~}{B}).$$

###### Proof.

Let $`(p,a)`$ be a point of $`\pi ^1(B)`$, so $`(p,\pi _0(a))B`$. Let us write $`a`$ as a convex combination of the vertices of $`\mathrm{\Delta }^{n1}`$, that is $`a=_{i=1}^m_{j=1}^{k_i}\lambda _j^iv_j^i`$, with $`\lambda _j^i0`$, $`i,j`$ and $`_i_j\lambda _j^i=1`$. Without loss of generality, we can suppose that none of the sums $`_{j=1}^{k_i}\lambda _j^i`$ is zero, otherwise everything “happens” on a face of $`\mathrm{\Delta }^{m1}`$ and we can restrict the statement to that face.

Let $`(p_1^1,v_1),\mathrm{},(p_{l_1}^1,v_1)`$, $`(p_1^2,v_2),\mathrm{},(p_{l_2}^2,v_2)`$, $`\mathrm{}`$, $`(p_1^m,v_m),\mathrm{},(p_{l_m}^m,v_m)`$ be the vertices of $`B`$, so we have $`\stackrel{~}{B}=\{(p_h^i,v_j^i):i=1,\mathrm{},m,j=1,\mathrm{},k_i,h=1,\mathrm{},l_i\}.`$ We write now $`(p,\pi _0(a))`$ as convex combination of the vertices of $`B`$, that is,

$$(p,\pi _0(a))=\underset{i=1}{\overset{m}{}}\underset{h=1}{\overset{l_i}{}}\mu _h^i(p_h^i,v_i),$$

with $`\mu _h^i0`$, $`i,h`$, and $`_i_h\mu _h^i=1`$. Observe that $`_{j=1}^{k_i}\lambda _j^i=_{h=1}^{l_i}\mu _h^i`$ for every $`i`$, because $`\pi _0(a)=_{i=1}^m_{j=1}^{k_i}\lambda _j^iv_i`$. Then, it is easy to check that:

$$(p,a)=\underset{i=1}{\overset{m}{}}\underset{j=1}{\overset{k_i}{}}\underset{h=1}{\overset{l_i}{}}\frac{\lambda _j^i\mu _h^i}{_{j=1}^{k_i}\lambda _j^i}(p_h^i,v_j^i)\text{ and }1=\underset{i=1}{\overset{m}{}}\underset{j=1}{\overset{k_i}{}}\underset{h=1}{\overset{l_i}{}}\frac{\lambda _j^i\mu _h^i}{_{j=1}^{k_i}\lambda _j^i}$$

That is, $`(p,a)`$ is a convex combination of points of $`\stackrel{~}{B}`$, as we wanted to prove. ∎

###### Corollary 3.2.

Under the previous conditions;

1. $`\pi ^1(B)=\mathrm{conv}(\pi ^1(\mathrm{vert}(B))).`$
2. $`\mathrm{vert}(\pi ^1(B))=\stackrel{~}{B}`$.

###### Proof.

In both equalities, the inclusion from right to left is trivial. In the second one, observe that if $`(p,v_j^i)`$ is in $`\stackrel{~}{B}`$, then $`(p,v_i)`$ is a vertex of $`B`$. Therefore, $`(p,v_j^i)\pi ^1(B)`$ and it is a vertex of $`P\times \mathrm{\Delta }^{n1}`$, which implies that it is a vertex of $`\pi ^1(B)`$.

Inclusions from left to right follow from Lemma 3.1, because:

(1) $`\stackrel{~}{B}\pi ^1(\mathrm{vert}(B))\pi ^1(B)\mathrm{conv}(\stackrel{~}{B})\mathrm{conv}(\pi ^1(\mathrm{vert}(B))).`$

(2) $`\pi ^1(B)\mathrm{conv}(\stackrel{~}{B})\mathrm{vert}(\pi ^1(B))\mathrm{vert}(\mathrm{conv}(\stackrel{~}{B}))=\stackrel{~}{B}`$, where the last equality follows from the fact that all the elements of $`\stackrel{~}{B}`$ are vertices of $`P\times \mathrm{\Delta }^{n1}`$. ∎

###### Corollary 3.3.

Every polyhedral subdivision $`S`$ of $`P\times \mathrm{\Delta }^{m1}`$ induces a polyhedral subdivision $`\stackrel{~}{S}:=\pi ^1(S)=\{\pi ^1(B):BS\}`$ of $`P\times \mathrm{\Delta }^{n1}`$. Furthermore, the vertices of each subpolytope $`\pi ^1(B)`$ in this subdivision are $`\stackrel{~}{B}:=\{(p,v_j^i):(p,v_i)\mathrm{vert}(B)\}`$. ∎

## 4. Triangulation of $`P\times \mathrm{\Delta }^{k_1+\mathrm{}+k_m1}`$ induced by a triangulation of $`P\times \mathrm{\Delta }^{m1}`$

We will suppose now that the polyhedral subdivision $`S`$ of $`P\times \mathrm{\Delta }^{m1}`$ is a triangulation. A convenient graphic representation of the vertices of the polytope $`P\times \mathrm{\Delta }^{m1}`$ is as a grid whose rows represent vertices of $`P`$ and whose $`m`$ columns represent the vertices $`v_1,\mathrm{},v_m`$ of $`\mathrm{\Delta }^{m1}`$. In order to represent a subset of vertices of $`P\times \mathrm{\Delta }^{m1}`$ we just mark the corresponding squares. In the same way we can represent the vertices of $`P\times \mathrm{\Delta }^{k_1+\mathrm{}+k_m1}`$, but now it is convenient to divide the grid horizontally in blocks, each of them corresponding to each $`k_i`$ and containing the vertices $`v_1^i,\mathrm{},v_{k_i}^i`$ of $`\mathrm{\Delta }^{k_1+\mathrm{}+k_m1}`$.

Figure 1 shows how to obtain, with the notation of the previous section, the set $`\stackrel{~}{B}`$ associated to a simplex $`BS`$ in this graphic representation. In the $`i`$-th block, rows corresponding to vertices $`(p,v_i)`$ in $`B`$ have all its squares marked. Restricting $`\stackrel{~}{B}`$ to that block gives precisely $`\mathrm{conv}(\{p_1^i,\mathrm{},p_{l_i}^i\})\times \mathrm{conv}(\{v_1^i,\mathrm{},v_{k_i}^i\})`$, with the notation used for the vertices of $`B`$ in the proof of Lemma 3.1.

Since $`B`$ is a simplex, any subset of its vertices forms also a simplex; thus, the restriction of $`\stackrel{~}{B}`$ to each block is a product of two simplices. Let us recall that the *staircase triangulation* of the product of two simplices $`\mathrm{\Delta }^k\times \mathrm{\Delta }^l`$ is the one whose $`\left(\genfrac{}{}{0pt}{}{k+l}{k}\right)`$ simplices are all the possible monotone staircases in a grid of size $`(k+1)\times (l+1)`$. Following this analogy, we define *multi-staircases* as follows:

###### Definition 4.1.

Let $`\stackrel{~}{B}=\pi ^1(B)`$ be a subpolytope of $`P\times \mathrm{\Delta }^{k_1+\mathrm{}+k_m1}`$, of the kind obtained in Section 3.

1. A *multi-staircase* in $`\stackrel{~}{B}`$ is any subset of vertices which restricted to every block forms a monotone staircase.
2. The *multi-staircase triangulation* of $`\stackrel{~}{B}`$ is the one which has as simplices the different multi-staircases (see Figure 2).

###### Lemma 4.2.

The multi-staircases indeed form a triangulation of $`\stackrel{~}{B}`$ and taking the multi-staircase triangulations of the different $`\stackrel{~}{B}`$’s obtained from a triangulation of $`P\times \mathrm{\Delta }^{m1}`$ we get a triangulation of $`P\times \mathrm{\Delta }^{k_1+\mathrm{}+k_m1}`$, which we call *multi-staircase triangulation*.

###### Proof.

It is clear that multi-staircases form full-dimensional simplices in $`\stackrel{~}{B}`$. A way to prove that a collection $`T`$ of full-dimensional simplices in a polytope $`\stackrel{~}{B}`$ is a triangulation is to show that:

1. They induce a triangulation on one face of $`\stackrel{~}{B}`$.
2. For each full-dimensional simplex in the collection, the removal of any single vertex produces a codimension one simplex either

* lying on a facet of $`\stackrel{~}{B}`$ and not contained in any other simplex of $`T`$, or
    * contained in exactly another full-dimensional simplex of $`T`$ which is separated from the first one by their common facet.

In our case, the first condition follows by induction on $`k_1+\mathrm{}+k_m`$, the base case being $`k_1+\mathrm{}+k_m=m`$.

For the second condition, let $`\sigma `$ be a multi-staircase, and let $`(p,v)`$ be a vertex in it. Then, one of the following three things happens (Figure 3 gives an example of a multi-staircase):

* If $`(p,v)`$ is the only point of $`\sigma `$ in its column, then no other multi-staircase contains $`\sigma \{(p,v)\}`$. Removing $`(p,v)`$ produces indeed a codimension one simplex contained in a facet $`P\times \mathrm{\Delta }^{k_1+\mathrm{}+k_m2}`$ of $`P\times \mathrm{\Delta }^{k_1+\mathrm{}+k_m1}`$.
* If $`(p,v)`$ is the only point of $`\sigma `$ in a row within a block, then no other multi-staircase contains $`\sigma \{(p,v)\}`$. Removing $`(p,v)`$ produces indeed a codimension one simplex in a facet of $`\stackrel{~}{B}`$ of the form $`\pi ^1(B\{(p,\pi _0(v))\})`$ (remember that $`B=\pi (\stackrel{~}{B})`$ is a simplex).
* If $`(p,v)`$ is an elbow in the multi-staircase, then removing it leads to a unique different way of completing the multi-staircase. More precisely, let $`(p^{},v)`$ and $`(p,v^{})`$ be the points of the multi-staircase adjacent to $`(p,v)`$. Then removing $`(p,v)`$ and inserting $`(p^{},v^{})`$ produces the other possible multi-staircase. The obvious affine dependency $`(p,v)+(p^{},v^{})=(p,v^{})+(p^{},v)`$ implies that the two multi-staircases lie in opposite sides of their common facet.

###### Lemma 4.3.

Let $`l_i`$ be the number of vertices of $`B`$ in the $`i`$-th column. Then the multi-staircase triangulation of $`\stackrel{~}{B}`$ has exactly $`_{i=1}^m\left(\genfrac{}{}{0pt}{}{k_i1+l_i1}{k_i1}\right)`$ simplices.

###### Proof.

In each sub-block there are $`\left(\genfrac{}{}{0pt}{}{k_i1+l_i1}{k_i1}\right)`$ possible monotone staircases. ∎

## 5. A triangulation of $`P\times Q`$

We will consider polytopes $`P`$ of dimension $`l`$ and $`Q`$ of dimension $`n1`$. We assume we are given a triangulation $`T_Q`$ of $`Q`$, which induces a decomposition of $`P\times Q`$ into cells isomorphic to $`P\times \mathrm{\Delta }^{n1}`$. Then, any decomposition $`n:=k_1+\mathrm{}+k_m`$ allows us to apply the procedure of Sections 3 and 4 to triangulate the cells $`P\times \mathrm{\Delta }^{n1}`$ starting from a triangulation $`T_0`$ of $`P\times \mathrm{\Delta }^{m1}`$.

There are two important tasks remaining: First, show that the triangulations of the different $`P\times \mathrm{\Delta }^{n1}`$ can be achieved in a coordinated way to obtain a real triangulation of $`P\times Q`$; second, analyze the efficiency of that triangulation. Both of them will be done in this section, using the following trick:

Consider a partition of the vertices of $`Q`$ into $`m`$ “colors”. Then, in each subpolytope $`P\times \mathrm{\Delta }^{n1}`$ of $`P\times Q`$ the vertices of the factor $`\mathrm{\Delta }^{n1}`$ are colored as well. We use this coloring to construct the projections $`\mathrm{\Delta }^{n1}\mathrm{\Delta }^{m1}`$ we need for each of them. Then, on each common face (isomorphic to $`P\times \mathrm{\Delta }^k,k<n1`$) of two of the cells $`P\times \mathrm{\Delta }^{n1}`$ we get the multi-staircase triangulation induced by the $`m`$-coloring of $`Q`$ restricted to that face. Hence, the triangulations of the different cells $`P\times \mathrm{\Delta }^{n1}`$ intersect face-to-face, and we obtain a triangulation $`T_{P\times Q}`$ of $`P\times Q`$, which we call *multi-staircase triangulation* of $`P\times Q`$.

In order to analyze the size of $`T_{P\times Q}`$, we will suppose that the $`m`$-coloring of the vertices of $`Q`$ is chosen at random with a uniform distribution.

For each $`\sigma T_Q`$ let $`\sigma _i:=\{\text{vertices of }\sigma \text{ colored }i\}`$. And for each $`\tau T_0`$, $`\tau _i:=\{\text{vertices of }\tau \text{ over the }i\text{-th vertex of }\mathrm{\Delta }^{m1}\}`$. By Lemma 4.3, the triangulation $`T_{P\times Q}`$ we obtain has

$$\underset{\sigma T_Q}{}\underset{\tau T_0}{}\underset{i=1}{\overset{m}{}}\left(\genfrac{}{}{0pt}{}{|\sigma _i|1+|\tau _i|1}{|\tau _i|1}\right)$$

simplices. The expected value of this sum, when the coloring is random, equals the sum of the expected values. So let us fix a pair of simplices $`\tau T_0`$ and $`\sigma T_Q`$ and calculate the expected value of

$$\underset{i=1}{\overset{m}{}}\left(\genfrac{}{}{0pt}{}{|\sigma _i|1+|\tau _i|1}{|\tau _i|1}\right)$$

We call $`l_i:=|\tau _i|`$ and $`k_i:=|\sigma _i|`$. The $`l_i`$’s are considered constants, while the $`k_i`$’s are random variables depending on the coloring. They follow a multinomial distribution, in which the probability of the $`m`$-tuple $`(k_1,\mathrm{},k_m)`$ is $`P(k_1,\mathrm{},k_m)=\frac{n!}{k_1!\mathrm{}k_m!m^n}.`$

Since $`\left(\genfrac{}{}{0pt}{}{x}{n}\right)=x^{\underset{¯}{n}}/n!`$, where $`x^{\underset{¯}{n}}:=x(x1)\mathrm{}(xn+1)`$ is the $`n`$-th *falling power* of $`x`$, we can write:

$$E(\underset{i=1}{\overset{m}{}}\left(\genfrac{}{}{0pt}{}{k_i1+l_i1}{l_i1}\right))=\frac{E(_{i=1}^m(k_i1+l_i1)^{\underset{¯}{l_i1}})}{_{i=1}^m(l_i1)!}$$

For the numerator in the RHS of this equation we will use the following result from  (Theorem 4.4.4):

###### Theorem 5.1.

Let $`X_1,\mathrm{},X_m`$ be scalar random variables. Then, the expected value of $`_{i=1}^mX_i^{\underset{¯}{v_i}}`$ is given by the formal calculus

$$E(\underset{i=1}{\overset{m}{}}X_i^{\underset{¯}{v_i}})=\left[\begin{array}{c}\frac{^{v_1+\mathrm{}+v_m}}{z_1^{v_1}\mathrm{}z_m^{v_m}}E(_{i=1}^mz_i^{X_i})\end{array}\right]_{z_1=\mathrm{}=z_m=1}$$

in which extra variables $`z_i,i=1,\mathrm{},m`$ appear with formal purposes.

###### Lemma 5.2.

Let $`l_1,\mathrm{},l_m`$ be positive integers with $`l_i=l+m`$ and let $`k_1,\mathrm{},k_m`$ be random variables obeying a multinomial distribution with $`k_i=n`$. Then,

$$E(\underset{i=1}{\overset{m}{}}(k_i1+l_i1)^{\underset{¯}{l_i1}})\left(l+\frac{n}{m}\right)^l$$

###### Proof.

If some $`l_i`$ equals 1 we can neglect it in the statement: we remove it and will still have $`(l_i1)=l`$. Hence we will assume $`l_i2`$ for every $`i`$.

We will use the following formula for expectations under a multinomial distribution, again taken from  (p. 53, last formula in the proof of Theorem 4.2.1):

$$E(\underset{i=1}{\overset{m}{}}z_i^{k_i})=\left(\underset{i=1}{\overset{m}{}}\frac{1}{m}z_i\right)^n$$

Since $`_{i=1}^m(l_i1)=l`$ and only the $`k_i`$ depend on the random process, applying Theorem 5.1 to the random variables $`X_i:=k_i+l_i2`$ and using the equality above we get:

$$E(\underset{i=1}{\overset{m}{}}(k_i1+l_i1)^{\underset{¯}{l_i1}})=\left[\begin{array}{c}\frac{^l}{z_1^{l_11}\mathrm{}z_m^{l_m1}}E(_{i=1}^mz_i^{k_i1+l_i1})\end{array}\right]_{\overline{z}=1}=$$

$$=\left[\begin{array}{c}\frac{^l}{z_1^{l_11}\mathrm{}z_m^{l_m1}}\left(_{i=1}^mz_i^{l_i2}E(_{i=1}^mz_i^{k_i})\right)\end{array}\right]_{\overline{z}=1}=$$

$$=\left[\begin{array}{c}\frac{^l}{z_1^{l_11}\mathrm{}z_m^{l_m1}}\left(_{i=1}^mz_i^{l_i2}\left(_{i=1}^m\frac{1}{m}z_i\right)^n\right)\end{array}\right]_{\overline{z}=1}\stackrel{()}{}\underset{i=1}{\overset{m}{}}\left(l_i2+\frac{n}{m}\right)^{l_i1}$$

$$\underset{i=1}{\overset{m}{}}\left(l+\frac{n}{m}\right)^{l_i1}=\left(l+\frac{n}{m}\right)^l,$$

where the last inequality comes from $`l_il+1`$ (since $`(l_i1)=l`$ and $`l_i11`$), and the one marked with an asterisk needs to be proved. For this we call $`F_{l_1,\mathrm{},l_m}(\overline{z}):=_{i=1}^mz_i^{l_i2}`$ and $`G_n(\overline{z}):=\left(_{i=1}^m\frac{1}{m}z_i\right)^n`$. Using that

$$\frac{^k}{x^k}f(x)g(x)=\underset{j=0}{\overset{k}{}}\left(\genfrac{}{}{0pt}{}{k}{j}\right)\frac{^j}{x^j}f(x)\frac{^{kj}}{x^{kj}}g(x)$$

we come up to

$$\frac{^{l_i1}}{z_i^{l_i1}}\left(F_{l_1,\mathrm{},l_m}(\overline{z})G_n(\overline{z})\right)=\underset{j=0}{\overset{l_i1}{}}\left(\genfrac{}{}{0pt}{}{l_i1}{j}\right)(l_i2)^{\underset{¯}{l_i1j}}\left(\frac{1}{m}\right)^jn^{\underset{¯}{j}}F_{l_1,\mathrm{},j+1,\mathrm{},l_m}(\overline{z})G_{nj}(\overline{z}).$$

Therefore, since

$$\frac{^l}{z_{1}^{}{}_{}{}^{l_11}\mathrm{}z_{m}^{}{}_{}{}^{l_m1}}h(\overline{z})=\frac{^{l_m1}}{z_{m}^{}{}_{}{}^{l_m1}}\left(\mathrm{}\left(\frac{^{l_11}}{z_{1}^{}{}_{}{}^{l_11}}\left(h(\overline{z})\right)\right)\mathrm{}\right)$$

and

$$\left[F_{h_1,\mathrm{},h_m}(\overline{z})\right]_{\overline{z}=1}=\left[G_t(\overline{z})\right]_{\overline{z}=1}=1,$$

we get

$$\left[\frac{^l}{z_1^{l_11}\mathrm{}z_m^{l_m1}}F_{l_1,\mathrm{},l_m}(\overline{z})G_n(\overline{z})\right]_{\overline{z}=1}=$$

$$=\underset{j_1=0}{\overset{l_11}{}}\mathrm{}\underset{j_m=0}{\overset{l_m1}{}}\left(\underset{i=1}{\overset{m}{}}\left(\genfrac{}{}{0pt}{}{l_i1}{j_i}\right)(l_i2)^{\underset{¯}{l_i1j_i}}\left(\frac{1}{m}\right)^{j_i}(nj_1\mathrm{}j_{i1})^{\underset{¯}{j_i}}\right)=$$

$$=\underset{j_1=0}{\overset{l_11}{}}\mathrm{}\underset{j_m=0}{\overset{l_m1}{}}\left(\underset{i=1}{\overset{m}{}}\left(\genfrac{}{}{0pt}{}{l_i1}{j_i}\right)(l_i2)^{\underset{¯}{l_i1j_i}}\left(\frac{1}{m}\right)^{j_i}\right)n^{\underset{¯}{{\scriptscriptstyle j_i}}}$$

$$\underset{j_1=0}{\overset{l_11}{}}\mathrm{}\underset{j_m=0}{\overset{l_m1}{}}\left(\underset{i=1}{\overset{m}{}}\left(\genfrac{}{}{0pt}{}{l_i1}{j_i}\right)(l_i2)^{l_i1j_i}\left(\frac{1}{m}\right)^{j_i}\right)n^{{\scriptscriptstyle j_i}}=$$

$$=\underset{i=1}{\overset{m}{}}\left(\underset{j_i=0}{\overset{l_i1}{}}\left(\genfrac{}{}{0pt}{}{l_i1}{j_i}\right)(l_i2)^{l_i1j_i}\left(\frac{1}{m}\right)^{j_i}n^{j_i}\right)=\underset{i=1}{\overset{m}{}}\left(l_i2+\frac{n}{m}\right)^{l_i1},$$

as wanted. ∎

This lemma is crucial to prove the two theorems announced in Section 2. Indeed, Theorem 2.2 is just a version of the following more precise statement:

###### Lemma 5.3.

Consider polytopes $`P`$ of dimension $`l`$ and $`Q`$ of dimension $`n1`$. Let $`m`$ be such that $`mn`$. Given a triangulation $`T_0`$ of $`P\times \mathrm{\Delta }^{m1}`$ of weighted size $`t_0`$ and a triangulation $`T_Q`$ of $`Q`$, the expected size of the multi-staircase triangulation $`T_{P\times Q}`$ of $`P\times Q`$ is bounded above by

$$|T_Q|t_0\left(\frac{n}{m}+l\right)^l.$$

###### Proof.

Lemma 5.2 implies that

$$E\left(\underset{i=1}{\overset{m}{}}\left(\genfrac{}{}{0pt}{}{k_i1+l_i1}{l_i1}\right)\right)=E\left(\underset{i=1}{\overset{m}{}}\frac{(k_i1+l_i1)^{\underset{¯}{l_i1}}}{(l_i1)!}\right)\frac{1}{_{i=1}^m(l_i1)!}\left(l+\frac{n}{m}\right)^l.$$

Hence:

$$E\left(\underset{\sigma T_Q}{}\underset{\tau T_0}{}\underset{i=1}{\overset{m}{}}\left(\genfrac{}{}{0pt}{}{k_i1+l_i1}{l_i1}\right)\right)\underset{\sigma T_Q}{}\underset{\tau T_0}{}\frac{1}{_{i=1}^m(l_i1)!}\left(\frac{n}{m}+l\right)^l=$$

$$=|T_Q|\left(\underset{\tau T_0}{}\frac{1}{_{i=1}^m(l_i1)!}\right)\left(\frac{n}{m}+l\right)^l=|T_Q|t_0\left(\frac{n}{m}+l\right)^l.$$

###### Proof of Theorem 2.3.

Let $`t_0=\rho _0^lm^l`$ be the weighted size of the triangulation in the statement. For any $`n\frac{lm\rho _0}{ϵ}`$:

$$\rho _0+ϵ\rho _0\frac{m}{n}\left(\frac{n}{m}+l\right),$$

$$n^l\left(\rho _0+ϵ\right)^l\rho _0^lm^l\left(\frac{n}{m}+l\right)^l=t_0\left(\frac{n}{m}+l\right)^l,$$

$$\frac{(n+l1)!}{(n1)!}\left(\rho _0+ϵ\right)^lt_0\left(\frac{n}{m}+l\right)^l.$$

Theorem 2.2, with $`Q=I^{n1}`$ and $`P=I^l`$, tells us that

$$\varphi _{n+l1}\varphi _{n1}t_0\left(\frac{n}{m}+l\right)^l,$$

or, in other words,

$$\frac{(n+l1)!\rho _{n+l1}^{}{}_{}{}^{n+l1}}{(n1)!\rho _{n1}^{}{}_{}{}^{n1}}t_0\left(\frac{n}{m}+l\right)^l.$$

So, we have proved the first part of the theorem:

$$ϵ>0,n\frac{lm\rho _0}{ϵ},\rho _{n+l1}^{}{}_{}{}^{n+l1}\rho _{n1}^{}{}_{}{}^{n1}(\rho _0+ϵ)^l.$$

The second part of the statement follows from the first one with arguments similar to those of Corollary 1.2. Recursively, we have that:

$$ϵ>0,i\text{},n\frac{lm\rho _0}{ϵ},\rho _{n+il}\rho _{n}^{}{}_{}{}^{\frac{n}{n+il}}(\rho _0+ϵ)^{\frac{il}{n+il}}.$$

This implies that for the given $`l`$ and any fixed $`n`$, taking $`ϵ=\frac{lm\rho _0}{n}`$ we get

$$\underset{i\mathrm{}}{lim}\rho _{n+il}\rho _0+\frac{lm\rho _0}{n}.$$

That is, the sequence of indices congruent to $`n`$ modulo $`l`$ has limit bounded by the right hand side. Since we can make $`n`$ as big as we want and the rest of the right-hand side are constants, the $`l`$ subsequences of indices modulo $`l`$ have limit bounded by $`\rho _0`$, hence the limit of the whole sequence has this bound. ∎

## 6. Interpretation of our method via the Cayley Trick

The Cayley Trick allows to study triangulations of a product $`P\times \mathrm{\Delta }^{n1}`$ as mixed subdivisions of the Minkowski sum $`P+\mathrm{}+P`$ ($`n`$ summands). We overview here this method, but the reader should look at  for more details.

Let $`Q_1,\mathrm{},Q_m\text{}^d`$ be convex polytopes of vertex sets $`𝒜_i`$. Consider their Minkowski sum, defined as

$$\underset{i=1}{\overset{m}{}}Q_i=\{x_1+\mathrm{}+x_m:x_iQ_i\}\text{.}$$

We understand $`_{i=1}^mQ_i`$ as a marked polytope, whose associated point configuration is $`_{i=1}^m𝒜_i:=\{q_1+\mathrm{}+q_m:q_i𝒜_i\}`$. Here a marked polytope is a pair $`(P,𝒜)`$ where $`P`$ is a polytope and $`𝒜`$ is a finite set of points of $`P`$ including all the vertices. Subdivisions of a marked polytope are defined in \[5, Chapter 7\] (sometimes they are called subdivisions of $`𝒜`$). Roughly speaking, they are the polyhedral subdivisions of $`P`$ which use only elements of $`𝒜`$ as vertices (but perhaps not all of them). They form a poset under the refinement relation. The minimal elements are the triangulations of $`𝒜`$.

A subset $`B`$ of $`_{i=1}^m𝒜_i`$ is called mixed if $`B=B_1+\mathrm{}+B_m`$ for some non-empty subsets $`B_i𝒜_i`$, $`i=1,\mathrm{},m`$. A mixed subdivision of $`_{i=1}^mQ_i`$ is a subdivision of it whose cells are all mixed. Mixed subdivisions form a subposet of the poset of all subdivisions, whose minimal elements are called fine mixed, in which every mixed cell is *fine*, i.e., does not properly contain any other mixed cell.

We call Cayley embedding of $`\{Q_1,\mathrm{},Q_m\}`$ the marked polytope

$$(𝒞(Q_1,\mathrm{},Q_m),𝒞(𝒜_1,\mathrm{},𝒜_m))\text{ in }\text{}^d\times \text{}^{m1}$$

defined as follows: let $`e_1,\mathrm{},e_m`$ denote an affine basis in $`\text{}^{m1}`$ and $`\mu _i:\text{}^d\text{}^d\times \text{}^{m1}`$ be the inclusion given by $`\mu _i(x)=(x,e_i)`$. Then we define

$$𝒞(𝒜_1,\mathrm{},𝒜_m):=_{i=1}^m\mu _i(𝒜_i),𝒞(Q_1,\mathrm{},Q_m):=\text{conv}(𝒞(𝒜_1,\mathrm{},𝒜_m))$$

Each $`Q_i`$ is naturally embedded as a face in $`𝒞(Q_1,\mathrm{},Q_m)`$. Moreover, the vertex set of $`𝒞(Q_1,\mathrm{},Q_m)`$ is the disjoint union of the vertices of all the $`Q_i`$’s. This induces the following bijection between cells in $`𝒞(Q_1,\mathrm{},Q_m)`$ and mixed cells in $`Q_1+\mathrm{}+Q_m`$: To each mixed cell $`B_1+\mathrm{}+B_m`$ we associate the disjoint union $`B_1\mathrm{}B_m`$. To a cell $`B`$ in $`𝒞(Q_1,\mathrm{},Q_m)`$, we associate the Minkowski sum $`B_1+\mathrm{}+B_m`$, where $`B_i=BQ_i`$.

###### Theorem 6.1 (The Cayley Trick,).

Let $`Q_1,\mathrm{},Q_m\text{}^d`$ be convex polytopes. The bijection just exhibited induces an isomorphism between the poset of all subdivisions of $`𝒞(Q_1,\mathrm{},Q_m)`$ and the poset of mixed subdivisions of $`_{i=1}^mQ_i`$. In this isomorphism triangulations correspond to fine mixed subdivisions.

###### Remark 6.2.

With the previous definitions, for any polytope $`P`$:

$$P\times \mathrm{\Delta }^{m1}=𝒞(P,\stackrel{m}{\mathrm{}},P).$$

In particular, in our context the Cayley Trick provides the following bijections between triangulations and mixed subdivisions:

$$\begin{array}{ccc}\text{Triangulation of }P\times \mathrm{\Delta }^{m1}& & \text{Triangulation of }P\times \mathrm{\Delta }^{n1}\\ & & \\ \text{Cayley Trick}& & \text{Cayley Trick}\\ & & \\ \text{Fine mixed subdivision of }P+\stackrel{m}{\mathrm{}}+P& & \text{Fine mixed subdivision of }P+\stackrel{n}{\mathrm{}}+P\end{array}$$

Our interest in the Cayley Trick is two-fold. On the one hand, it provides a way to visualize our candidate triangulations of $`I^l\times \mathrm{\Delta }^{m1}`$ as objects in dimension $`l`$, instead of $`l+m1`$. We will use this in Section 7.

On the other hand, the construction of the previous sections has a simple geometric interpretation in terms of the Cayley Trick. More precisely, the polyhedral subdivision of Corollary 3.3 can be obtained as follows: Let $`S`$ be a polyhedral subdivision of $`P\times \mathrm{\Delta }^{m1}`$, and $`S_M`$ the corresponding mixed subdivision of $`P+\stackrel{m}{\mathrm{}}+P`$. Each cell in $`S`$ decomposes uniquely as

$$_{i=1}^mB_i\times \{v_i\},$$

where the $`B_i`$ are subsets of vertices of $`P`$. The corresponding cell in $`S_M`$ is just $`B_1+\mathrm{}+B_m`$. To construct our polyhedral subdivision of $`P\times \mathrm{\Delta }^{n1}`$ we just need to scale each summand $`B_i`$ by the integer $`k_i`$ which tells us how many vertices of $`\mathrm{\Delta }^{n1}`$ correspond to the vertex $`v_i`$ of $`\mathrm{\Delta }^{m1}`$.

That is to say, from $`S_M`$ we construct a mixed subdivision of $`P+\stackrel{n}{\mathrm{}}+P`$ by the formula

$$\stackrel{~}{S_M}=\{B_1+\stackrel{k_1}{\mathrm{}}+B_1+\mathrm{}\mathrm{}+B_m+\stackrel{k_m}{\mathrm{}}+B_m:B_1+\mathrm{}+B_mS_M\}.$$

The polyhedral subdivision $`\stackrel{~}{S}`$ of $`P\times \mathrm{\Delta }^{n1}`$ stated in Corollary 3.3 is the one corresponding via the Cayley Trick to the mixed subdivision $`\stackrel{~}{S_M}`$ of $`P+\stackrel{n}{\mathrm{}}+P`$.

Also the type and weight of a simplex in $`P\times \mathrm{\Delta }^{m1}`$ have a simple interpretation via the Cayley Trick. With the notation of Definition 2.1, let $`\tau =\tau _1\mathrm{}\tau _m`$ be a simplex. The corresponding cell $`\tau _M`$ in $`P+\stackrel{m}{\mathrm{}}+P`$ is the Minkowski sum of the simplices $`\tau _1,\mathrm{},\tau _m`$, which lie in complementary affine subspaces. Hence, $`\tau _M`$ is combinatorially a product of $`m`$ simplices, of dimensions $`t_1,\mathrm{},t_m`$ where $`(t_1,\mathrm{},t_m)`$ is the type of $`\tau `$. Then the weight of $`\tau `$ represents the volume of $`\tau _M`$, normalized with respect to the unit parallelepiped in the lattice spanned by the vertices of $`\tau _M`$. With this we can prove:

###### Proposition 6.3.

Let $`P`$ be a lattice polytope of dimension $`l`$. Let $`V`$ be its volume, normalized to the unit parallelepiped in the lattice. Then, the weighted size of a triangulation of $`P\times \mathrm{\Delta }^{m1}`$ is at most $`m^lV`$, with equality if and only if the triangulation is unimodular (with respect to the lattice).

In particular, the weighted efficiency of a triangulation of $`I^l\times \mathrm{\Delta }^{m1}`$ is at most one, with equality for unimodular triangulations.

###### Proof.

If $`P`$ is a lattice polytope (e.g., a cube), then the lattice spanned by $`\tau _M`$ is a sublattice of the one spanned by the point configuration $`P+\stackrel{m}{\mathrm{}}+P`$, and coincides with it if and only if $`\tau `$ is unimodular. Then, for unimodular triangulations the weighted size is then just the volume of $`P+\stackrel{m}{\mathrm{}}+P`$, normalized to the unit parallelepiped, which equals $`m^lV`$. For non-unimodular triangulations the weighted size is smaller than that. ∎

## 7. More on $`\rho _{l,m}`$

In this section we obtain the value of $`\rho _{2,m}`$ for any $`m`$ and we will also show triangulations of $`I^3\times \mathrm{\Delta }^1`$ and $`I^3\times \mathrm{\Delta }^2`$ providing the values of $`\rho _{3,2}`$ and $`\rho _{3,3}`$ stated in Section 2.

### 7.1. Smallest weighted efficiency of triangulations of $`I^2\times \mathrm{\Delta }^{m1}`$

Here we prove:

###### Theorem 7.1.

The smallest weighted efficiency $`\rho _{2,m}`$ of triangulations of $`I^2\times \mathrm{\Delta }^{m1}`$ is

$$\rho _{2,m}=\sqrt{\frac{3m^2/4}{m^2}}.$$

That is, $`\sqrt{3/4}`$ for even $`m`$ and $`\sqrt{3/4}+\mathrm{\Theta }(m^2)`$ for odd $`m`$. A fine mixed subdivision of $`I^2+\stackrel{m}{\mathrm{}}+I^2`$ corresponding to a triangulation of $`I^2\times \mathrm{\Delta }^{m1}`$ with that weighted efficiency is given in Figure 4.

Let $`B_M=B_1+\stackrel{m}{\mathrm{}}+B_m`$ be a cell in a fine mixed subdivision of $`I^2+\stackrel{m}{\mathrm{}}+I^2`$ (a square of size $`m`$). Each $`B_i`$ must be a simplex coming from the $`i`$-th copy of $`I^2`$, and in order to have a fine mixed subdivision, the different $`B_i`$’s must lie in complementary affine subspaces. Then, there are the following possibilities:

* $`B_M`$ is a triangle, obtained as the sum of a triangle in one of the $`I^l`$’s and a single point in the others. The weight of $`B_M`$ is $`1/2`$.
* $`B_M`$ is a quadrangle, obtained as the sum of two (non-parallel) segments from two of the $`B_i`$’s and a point in the rest of them. Three types of quadrangles can appear, depending on whether none, one or both of the two segments involved is a diagonal of $`I^2`$: a square parallel to the axes, a rhomboid (both with area 1) and a diagonal square (of area 2). The weight of $`B_M`$ is $`1`$.

In particular, the weighted size of the mixed subdivision equals $`T/2+S_1+S_2+R`$, where $`T`$, $`S_1`$, $`S_2`$ and $`R`$ denote, respectively, the numbers of triangles, squares of area 1, squares of area 2 and rhombi in the subdivision. Since the total area of $`I^2+\stackrel{m}{\mathrm{}}+I^2`$ is $`m^2=T/2+S_1+2S_2+R`$, we conclude that:

###### Proposition 7.2.

The weighted size of a mixed subdivision of $`I^2+\stackrel{m}{\mathrm{}}+I^2`$ equals $`m^2S_2`$, where $`S_2`$ is the number of squares of size 2 in the subdivision.

With this we can already conclude that the fine mixed subdivisions shown in Figure 4 (one for $`m`$ even and one for $`m`$ odd) have weighted size equal to $`3m^2/4`$, since they have exactly $`m^2/4`$ squares of area 2.

Our task is now to prove that no mixed subdivision can have more than $`m^2/4`$ squares of area 2. For this we use:

###### Lemma 7.3.

Taking the $`i`$-th summands of all the mixed cells $`B_1+\stackrel{m}{\mathrm{}}+B_m`$ in a mixed subdivision of $`P_1+\stackrel{m}{\mathrm{}}+P_m`$ produces a polyhedral subdivision of $`P_i`$. If the mixed subdivision was fine, the polyhedral subdivision is a triangulation.

###### Proof.

By the Cayley Trick, the mixed subdivision of $`P_1+\stackrel{m}{\mathrm{}}+P_m`$ induces a polyhedral subdivision of $`𝒞(P_1,\mathrm{},P_m)`$, and a triangulation if the mixed subdivision is fine. Since the polytope $`P_i`$ appears as a face in $`𝒞(P_1,\mathrm{},P_m)`$, any subdivision (resp. triangulation) of $`𝒞(P_1,\mathrm{},P_m)`$ induces a subdivision (resp. triangulation) of $`P_i`$. That this subdivision is the one obtained taking the $`i`$-th summands of all the mixed cells follows from Theorem 6.1. ∎

###### Proposition 7.4.

Let $`S_M`$ be a fine mixed subdivision of $`I^2+\stackrel{m}{\mathrm{}}+I^2`$. Let $`a`$ and $`b`$ be the number of summands $`I^2`$’s which are triangulated in one and the other possible triangulations of $`I^2`$ (i.e., using one or the other diagonal). Then, the number of squares of area 2 in $`S_M`$ is at most $`ab`$ and the weighted size of $`S_M`$ is at least $`m^2ab`$.

###### Proof.

Each square of area 2 is the Minkowski sum of two opposite diagonals of two copies of $`I^2`$ (say, the $`i`$th and $`j`$th copies), and a point in the other $`m2`$ of the copies of $`I^2`$. Clearly, the two copies which contribute diagonals have to be triangulated in opposite ways. The only thing which remains to be shown is that the same pair of copies of $`I^2`$ cannot contribute two different squares of size 2. For this, observe that “contracting” in every mixed cell of a mixed subdivision all the summands other than the $`i`$th and $`j`$th should give a mixed subdivision of $`P_i+P_j`$. And in a mixed subdivision of two squares there is no room to put two different diagonal squares of area 2. ∎

In the statement of Proposition 7.4, we have that $`a+b=m`$. In particular, the maximum possible value of $`ab`$ is $`m^2/4`$. This finishes the proof of Theorem 7.1.

### 7.2. Smallest weighted efficiency triangulations of $`I^3\times \mathrm{\Delta }^{m1},m=2,3`$

Here we will try to visualize triangulations of $`I^3\times \mathrm{\Delta }^1`$ and $`I^3\times \mathrm{\Delta }^2`$ which minimize the weighted efficiency, which we computed using the integer programming approach sketched in Section 2.

Of course, we use the Cayley trick to decrease the dimension, so we show the corresponding fine mixed subdivision of a Minkowski sum instead of the triangulation itself.

* $`I^3\times \mathrm{\Delta }^1`$ $`I^3\times \mathrm{\Delta }^1=𝒞(I^3,I^3)I^3+I^3`$

We have to give a subdivision of a 3-cube of size 2. For this we first cut the eight corners of the cube, producing a *cubeoctahedron*, a semi-regular 3-polytope with 6 square and 8 triangular facets. The edges of the cubeoctahedron can be distributed in four “equatorial hexagons” each of which cuts the polytope into 2 halves. Figure 5 depicts these two halves for one of the equatorial hexagons. The labels in the vertices are heights, interpreted as follows: Our point configuration is $`\{0,1,2\}^3`$ and the height of point $`(i,j,k)`$ is just $`i+j+k`$.

It turns out that performing three of these four possible halvings, the cubeoctahedron is decomposed into six triangular prisms and two tetrahedra. In Figure 5 each half is actually decomposed into three prisms and one tetrahedron. These, together with the eight tetrahedra we have cut from corners, form a fine mixed subdivision of $`\{0,1,2\}^3`$ with 10 tetrahedra and 6 triangular prisms. Its weighted size is then

$$10\frac{1}{6}+6\frac{1}{2}=\frac{14}{3}$$

and its weighted efficiency $`\sqrt[3]{\frac{14/3}{8}}`$.
* $`I^3\times \mathrm{\Delta }^2`$ $`I^3\times \mathrm{\Delta }^2=𝒞(I^3,I^3,I^3)I^3+I^3+I^3`$

The fine mixed subdivision of $`I^3+I^3+I^3`$ is given in Figure 6. It consists of 20 triangular prisms, 16 tetrahedra and 2 parallelepipeds.

Thus, the weighted size of the triangulation is $`20\frac{1}{2}+16\frac{1}{6}+2\frac{1}{1}=\frac{44}{3}`$, and then the smallest weighted efficiency is

$$\rho _{3,3}=\sqrt[3]{\frac{44/3}{3^3}}.$$

Let us explain how to interpret Figure 6. Again, each point $`(i,j,k)`$ in $`\{0,1,2,3\}^3`$ has been given a height $`i+j+k`$, which is written next to it. The subdivision is displayed in five parts. The left-top portion in the figure is a half cubeoctahedron exactly as the one in Figure 6. The reader has to assume it divided into a tetrahedron and three triangular prisms, as before. The left-bottom portion consists of a corner tetrahedron and three triangular prisms located at corners of the cube, each joined to the half cubeoctahedron by a tetrahedron. So far we have six prisms and five tetrahedra, and the same is got from the right-top and right-bottom portions of the Figure.

In between the two half cubeoctahedra, however, we have now a hexagonal prism decomposed into two triangular prisms and two quadrilateral prisms, all of height $`\sqrt{3}`$. The hexagonal prism is surrounded by a belt formed by six triangular prisms and six tetrahedra.

The thick edges in Figure 6 represent edges of the big 3-cube of side 3, whose three visible facets are drawn by dotted lines. We have also shaded the facets of the subdivision which are contained in those facets of the big 3-cube.