# Determination of the Proton Trace Anomaly Energy from the Near-Threshold
Vector Meson Photoproduction Data

Wei Kou<EMAIL_ADDRESS>Institute of Modern Physics, Chinese Academy of
Sciences, Lanzhou 730000, China  University of Chinese Academy of Sciences,
Beijing 100049, China  Rong Wang<EMAIL_ADDRESS>Institute of Modern
Physics, Chinese Academy of Sciences, Lanzhou 730000, China  University of
Chinese Academy of Sciences, Beijing 100049, China  Xurong Chen
<EMAIL_ADDRESS>Institute of Modern Physics, Chinese Academy of Sciences,
Lanzhou 730000, China  University of Chinese Academy of Sciences, Beijing
100049, China  Guangdong Provincial Key Laboratory of Nuclear Science,
Institute of Quantum Matter, South China Normal University, Guangzhou 510006,
China

###### Abstract

The trace anomalous energy contribution to the proton mass is an important and
interesting ingredient of the QCD mass structure. In experiments, it is under
discussions on how to measure the trace anomalous energy. The scale-dependence
of the proton trace anomaly is still unclear. To connect the theory with the
experiment, we extract the trace anomaly and study its scale-dependence by
analyzing the near-threshold photoproduction data of $\phi$ and J/$\psi$
vector mesons. We use the vector-meson-dominance model and the QCD Van der
Waals interaction suggested by D. Kharzeev. We find that the quantum anomalous
energy to the proton mass is scale-dependent and it can be described by
$M_{a}=0.25\exp(-A/\mu^{2})M_{N}$ with $A=0.101\pm 0.029$ GeV2. This empirical
formula agrees with the LQCD calculation at $\mu^{2}=4$ GeV2. Based on the
result, the corresponding evolution equation is given for the proton trace
anomaly.

##  I Introduction

The generation of nucleon mass is one of the puzzles in modern particle
physics. The origin of the masses of fundamental particles (leptons, quarks,
and gauge bosons) are delicately explained by the famous Higgs mechanism. The
proton mass comes mainly from the complicated workings of non-perturbative
Quantum Chromodynamics (QCD) Gross and Wilczek (1973a, b, 1974). QCD theory
originates from Yang-Mills theory Yang and Mills (1954) in the 1950s, which
belongs to a non-abelian gauge theory. To calculate the proton mass in the
first principle view, one encounters two main challenges: the color
confinement for the constitutes (quarks and gluons) Wilson (1974) and the
divergent strong coupling constant at low energy scale.

The proton is a composite particle made of quarks and gluons, hence its mass
is usually argued to be from some different sources. X.-D. Ji first comes up
with the proton mass decomposition with the decomposition of QCD Hamiltonian
operators Ji (1995a, b). Four gauge-invariant Hamiltonian operators are
introduced as,

$H_{\mathrm{QCD}}=H_{q}+H_{g}+H_{m}+H_{a},$ (1)

where

$\displaystyle H_{q}$ $\displaystyle=\int
d^{3}\vec{x}\left[\psi^{\dagger}(-i\mathbf{D}\cdot\alpha)\psi\right],$ (2)
$\displaystyle H_{g}$ $\displaystyle=\int
d^{3}\vec{x}\frac{1}{2}\left(\mathbf{E}^{2}+\mathbf{B}^{2}\right),$
$\displaystyle H_{m}$ $\displaystyle=\int
d^{3}\vec{x}\left(1+\frac{1}{4}\gamma_{m}\right)\bar{\psi}m\psi,$
$\displaystyle H_{a}$ $\displaystyle=\int
d^{3}\vec{x}\frac{1}{4}\beta(g)\left(\mathbf{E}^{2}-\mathbf{B}^{2}\right).$

In Ref. Ji (1995b), Ji assumes that the hadron mass can be calculated as the
expectation value of the Hamiltonian in the hadron rest frame:

$M_{N}=\left.\frac{\left\langle
P\left|H_{\mathrm{QCD}}\right|P\right\rangle}{\langle P\mid
P\rangle}\right|_{\text{rest frame }},$ (3)

which is decomposed into four terms characterized by the QCD trace anomaly
parameter $b(\mu^{2})$ and the momentum fraction $a(\mu^{2})$ carried by all
quarks Ji (1995b). The four terms of the proton mass partitions are written as
Ji (1995b),

$\displaystyle M_{q}=\frac{3}{4}\left(a-\frac{b}{1+\gamma_{m}}\right)M_{N},$
(4) $\displaystyle M_{g}=\frac{3}{4}(1-a)M_{N},$ $\displaystyle
M_{m}=\frac{4+\gamma_{m}}{4\left(1+\gamma_{m}\right)}bM_{N},$ $\displaystyle
M_{a}=\frac{1}{4}(1-b)M_{N},$

where $\gamma_{m}$ is the anomalous dimension of quark mass Buras (1980)
describing the renormalization. The momentum fraction $a(\mu^{2})$ of the
quarks is easily computed with the parton distributions determined in
experiments,

$a\left(\mu^{2}\right)=\sum_{f}\int_{0}^{1}x\left[q_{f}\left(x,\mu^{2}\right)+\bar{q}_{f}\left(x,\mu^{2}\right)\right]dx.$
(5)

Ji’s proton mass decomposition is from the analysis of the energy-momentum
tensor (EMT) in QCD theory Ji (1995b). The first three terms in Eq. (4) can be
understood in the classical picture of the field theory. However the last term
is an extension of the classical description in the quantum field theory – the
quantum anomaly. It is a completely quantum effect! In the recent papers Ji
(2021); Ji and Liu (2021), the authors make more discussions on the the source
of quantum anomalous energy (QAE) to the proton mass and argue that it arises
from the scale symmetry breaking due to the ultraviolet (UV) divergences in
the quantum field theories. The trace anomaly part to the proton mass
resembles the dynamical Higgs mechanism to the mass of the fundamental
fermions. Ji mentions that the quantum anomalous contribution is scale-
independent in the chiral limit Ji (2021). However the quark mass is not
exactly zero. Therefore the quantum anomalous energy should be scale-dependent
due to the contribution of the quark mass.

Although the proton mass is mainly given by the dynamical chiral symmetry
breaking, a small portion does arise from the masses of the quarks. The quark
mass contribution is usually characterized by a parameter $b$. The quark mass
correction parameter $b$ to the QCD trace anomaly is related to the quark
masses and the quark scalar charges of the proton via,

$\displaystyle bM_{N}$ $\displaystyle=\left\langle
N\left|m_{u}\bar{u}u+m_{d}\bar{d}d\right|N\right\rangle+\left\langle
N\left|m_{s}\bar{s}s\right|N\right\rangle$ (6) $\displaystyle=m_{l}\langle
N|\bar{u}u+\bar{d}d|N\rangle+m_{s}\langle N|\bar{s}s|N\rangle$
$\displaystyle=\Sigma_{\pi N}+\Sigma_{sN}.$

The scalar nucleon matrix element of up and down quarks $\Sigma_{\pi N}$ is
about 45 MeV, determined from the low energy $\pi-N$ scattering amplitude
Gasser  _et al._ (1991); Ruiz de Elvira  _et al._ (2018); Ren  _et al._
(2018). In Ref. Alarcon  _et al._ (2012), the authors present a new result
using new experimental data and chiral effective field theory $\sigma_{\pi
N}=59(7)$ MeV. Very little is known about the $\Sigma_{sN}$ term, and it is
considered to be large because the strange quark is heavier. In theory, the
QCDSF Collaboration finds $\Sigma_{sN}=11\pm 13$ MeV Bali  _et al._ (2012) and
the $\chi$QCD Collaboration finds $\Sigma_{sN}=40\pm 12$ MeV Yang  _et al._
(2016). The strange $\Sigma$ term is also suggested to be small around 16 MeV
from an effective field theory Alarcon  _et al._ (2014). The nucleon scalar
charge is an important parameter for calculating the scattering between the
nucleon and the dark matter particle Bottino  _et al._ (2000); Ellis  _et al._
(2005, 2008); Bottino  _et al._ (2008); Hill and Solon (2012); Cline  _et al._
(2013). Hence studying the QCD trace anomaly parameter $b$ is helpful in
investigating the method of detecting the weakly-interacting dark matter
particle.

Measuring the quantum effect of the many-body system inside the proton is
generally difficult. But the low-energy scattering between the heavy
quarkonium and the nucleon can be used to probe the trace anomaly of the
nucleon, since the two-gluon exchange is dominant for the process. It is not
difficult to compute the scattering amplitude using the local operator
production expansion with the gluon operator Boussarie and Hatta (2020).
Hatta, Rajan, and Yang had tried to extract the trace anomaly from the
J/$\psi$ photo-production data near threshold, based on a holographic QCD
framework Hatta and Yang (2018); Hatta  _et al._ (2019). The QCD trace anomaly
of the proton is also evaluated by the lattice calculation Yang  _et al._
(2018). In this work, we begin with the VMD model suggested by Kharzeev
Kharzeev (1996); Kharzeev  _et al._ (1999). Following the recent prior
analysis based on the model Wang  _et al._ (2020), we try to extract the trace
anomalous energy of the proton from the diffractive production data of $\phi$
and J/$\psi$ vector mesons near the thresholds Mibe  _et al._ (2005); Ali  _et
al._ (2019). Based on the extracted trace anomaly parameter $b$ at different
energy scales, we come up with an empirical scale-dependence for the trace
anomaly contribution to the proton mass and the corresponding evolution
equation.

##  II Methods

In the vector-meson-dominance (VMD) model, the forward cross section of the
vector meson $X$ ($\phi$, J/$\psi$, $\Upsilon$, etc.) photoproduction on the
nucleon target is formulated as Kharzeev  _et al._ (1999),

$\displaystyle\left.\frac{d\sigma_{\gamma N\rightarrow XN}}{dt}\right|_{t=0}$
(7) $\displaystyle=\left.\frac{3\Gamma\left(X\rightarrow
e^{+}e^{-}\right)}{\alpha m_{X}}\left(\frac{k_{XN}}{k_{\gamma
N}}\right)^{2}\frac{d\sigma_{XN\rightarrow XN}}{dt}\right|_{t=0},$

where $\alpha=1/137$ is the fine structure constant,
$k_{ab}^{2}=\left[s-\left(m_{a}+m_{b}\right)^{2}\right]\left[s-\left(m_{a}-m_{b}\right)^{2}\right]/4s$
denotes the center-of-mass momentum square of the corresponding two-body
system, and $\Gamma$ is the partial decay width of the $X$ meson decaying into
$e^{+}e^{-}$ pair. The $\left.\frac{d\sigma_{XN\rightarrow
XN}}{dt}\right|_{t=0}$ term of elastic scattering at forward limit is given
by,

$\left.\frac{d\sigma_{XN\rightarrow
XN}}{dt}\right|_{t=0}=\frac{1}{64\pi}\frac{1}{m_{X}^{2}\left(\lambda^{2}-m_{N}^{2}\right)}\left|F_{XN}\right|^{2},$
(8)

where $\lambda=(p_{N}p_{X}/m_{X})$ is the nucleon energy in the quarkonium
rest frame Kharzeev  _et al._ (1999). $F_{XN}$ denotes the invariant amplitude
of $X-N$ elastic scattering. At low energy, the scattering amplitude takes the
form Kharzeev (1996),

$\displaystyle F_{XN}$ $\displaystyle\simeq
r_{0}^{3}d_{2}\frac{2\pi^{2}}{27}2M_{N}\left(M_{N}-\left\langle
N\left|\sum_{i=u,d,s}m_{i}\bar{q}_{i}q_{i}\right|N\right\rangle\right)$ (9)
$\displaystyle=r_{0}^{3}d_{2}\frac{2\pi^{2}}{27}2M_{N}^{2}(1-b),$

which is dominated by the QCD trace anomaly part. For the low-energy
scattering and at the chiral limit, the mass of a hadron state comes purely
from the quantum fluctuations of the gluons. Away from the chiral limit, the
factor $(1-b)$ is used to characterize the QCD trace anomaly contribution to
the proton mass. In Eq. (9), the “Bohr” radius $r_{0}$ of the meson $X$ is
given by Kharzeev (1996),

$r_{0}=\left(\frac{4}{3\alpha_{s}}\right)\frac{1}{m_{q}},$ (10)

where $m_{q}$ is the mass of the constituent quark (strange quark $s$ for the
$\phi$ meson and charm quark $c$ for the J/$\psi$ meson). In Eq. (9), the
Wilson coefficient $d_{2}$ can be found in Refs. Kharzeev (1996); Peskin
(1979); Kharzeev  _et al._ (1996),

$d_{n}^{(1S)}=\left(\frac{32}{N_{c}}\right)^{2}\sqrt{\pi}\frac{\Gamma\left(n+\frac{5}{2}\right)}{\Gamma(n+5)},$
(11)

where $N_{c}$ is the number of colors. The strong coupling constant
$\alpha_{s}$ depends on the renormalization scale $\mu^{2}$, and the scale is
chosen to be the “Rydberg” energy square $\epsilon_{0}^{2}$ for the bound
state of the quarkonium $X$ Kharzeev (1996); Kharzeev  _et al._ (1996).

The strong coupling $\alpha_{s}$ of perturbative QCD diverges eventually at
the low energy scale, and this property is related to the Landau pole Gribov
and Pomeranchuk (1963). To avoid the Landau pole of the running coupling
constant at low $\mu^{2}$, the analytic approach to describe the coupling
$\alpha_{s}$ is suggested Deur  _et al._ (2016). The resulting analytic form
of $\alpha_{s}$ is written as,

$\alpha_{s}^{\mathrm{ana}}=\frac{4\pi}{\beta_{0}}\left(\frac{1}{\ln\left(\mu^{2}/\Lambda_{\mathrm{QCD}}^{2}\right)}+\frac{\Lambda_{\mathrm{QCD}}^{2}}{\Lambda_{\mathrm{QCD}}^{2}-\mu^{2}}\right).$
(12)

The QCD running coupling can be determined from the global analysis of deep
inelastic scattering data in a wide $\mu^{2}$ range, such as GRV98 Glück  _et
al._ (1998) and CT14 Dulat  _et al._ (2016). One finds
$\Lambda_{\mathrm{QCD}}^{2}=0.0643$ GeV2 in Eq. (12) by matching to the
CT14(LO) $\alpha_{s}$. In this analysis, we use the analytic form of strong
coupling in order to take into account of the nonperturbative effect. The
running strong coupling is depicted in Fig. 1.

Figure 1: (Color online) The strong coupling constant $\alpha_{s}$ in the
analytic approach described by Eq. (12) with
$\Lambda_{\mathrm{QCD}}^{2}=0.0643$ GeV2.

Based on the theoretical framework discussed above, we can extract the QCD
trace anomaly $M_{a}$ from the extrapolated value of the differential cross
section at $t=0$ GeV2. We take the differential cross section data about the
diffractive $\phi$ photoproduction on the proton near the threshold published
by LEPS Collaboration Mibe  _et al._ (2005) and about the diffractive J/$\psi$
photoproduction on the proton near the threshold by GlueX Collaboration at
Jefferson Laboratory (JLab) Ali  _et al._ (2019). The synchrotron radiation
and bremsstrahlung photon energies are at $1.62$ GeV and at $10.72$ GeV in
average for the $\phi$ and J/$\psi$ productions, respectively. At the
energies, $|t|_{min}$ are $0.3164$ GeV2 and $0.4361$ GeV2, for $\phi$ and
J/$\psi$ channels respectively. The differential cross sections as a function
of $-t$ are shown in Fig. 2 and Fig. 3. The data are fitted with an
exponential function ($d\sigma/dt=d\sigma/dt|_{t=0}\times e^{-kt}$) which
describes the $t$-dependence of the cross section. Using the exponential
function for the extrapolation of the data, we get the forward cross sections
and the errors. $d\sigma/dt|_{t=0}$ for $\phi$ at $E_{\gamma}=1.62$ GeV is
found to be $1.194\pm 1.128\ \mu$b/GeV2; and $d\sigma/dt|_{t=0}$ for J/$\psi$
at $E_{\gamma}=10.72$ GeV is found to be $3.792\pm 1.324$ nb/GeV2. The errors
are determined by fixing $\chi^{2}-\chi^{2}|_{\mathbf{best\ fit}}=1$.
Comparing the forward cross sections to the $b$-dependent predictions yield
the fits of $b$ and the QCD trace anomaly, which are discussed in the
following section.

Figure 2:  (Color online) The differential cross section of $\phi$
photoproduction near threshold of $E_{\gamma}=$ 1.62 GeV by LEPS Collaboration
Mibe  _et al._ (2005). The red line shows our fit with an exponential
function.  Figure 3:  (Color online) The differential cross section of
J/$\psi$ photoproduction near threshold of $E_{\gamma}=$ 10.72 GeV by GlueX
Collaboration Ali  _et al._ (2019). The red line shows our fit with an
exponential function.

##  III Results and discussions

Table 1 lists the key parameters and the experimental inputs for the
extraction of the QCD trace anomaly. In this work we assume that the energy
scale of the strong interaction ($\mu^{2}$) is equal to the “Rydberg” energy
$\epsilon_{0}$ of the quark-antiquark pair, for the production near the
threshold. Using the masses of the constituent quarks $m_{s}=0.486$ GeV and
$m_{c}=1.55$ GeV Griffiths (2008) of the vector mesons, we finalize the
results on the QCD trace anomaly in Table 2 and Fig. 4. In table 2, the size
of trace anomaly contribution by the lattice QCD is referred from Ref. Yang
_et al._ (2018).

Table 1: Forward cross sections by fitting the experimental data and some physical quantities regarding the photoproductions of the vector mesons. We use the “Rydberg” energies $\epsilon_{0}^{2}$ to define the running energy scale $\mu^{2}$ for the vector meson photoproduction at the threshold.  Meson |  $d\sigma/dt|_{t=0}$ (nb/GeV2) |  $\mu^{2}$ (GeV2) | $\alpha_{s}(\mu^{2})$ |  $E_{\gamma}$ (GeV)
---|---|---|---|---
$\phi$ | $1194\pm 1128$ | 0.0625 | 0.701 | 1.62
J/$\psi$ | $3.792\pm 1.324$ | 0.41 | 0.494 | 10.72
Table 2: The trace anomaly contribution to the proton mass from different vector meson production channels and lattice QCD result.  Results |  $\mu^{2}$ (GeV2) | $b$ | $\frac{1}{4}(1-b),\%$
---|---|---|---
$\phi$ | 0.0625 | $0.7887\pm 0.0998$ | $5.28\pm 2.50$
J/$\psi$ | 0.41 | $0.2578\pm 0.1296$ | $18.56\pm 3.24$
LQCD Yang  _et al._ (2018) | 4.0 |  | $23\pm 1$
Figure 4: (Color online) The trace anomaly contribution to the proton mass
from different vector meson production channels ($\phi,\ \mathrm{J}/\psi$).
The horizontal axis shows the renormalization scale $\mu^{2}$ for the
corresponding channels of the vector meson productions near the thresholds.
The red dashed curve and the light blue band show the fit to a empirical
formula $0.25e^{-A/\mu^{2}}$ and the uncertainties respectively. The violet
vertical dash line shows where the energy scale for the $\Upsilon$
photoproduction near threshold is. The result of lattice QCD calculation (blue
circle) is also shown in the figure but not used in the fit.

Figure 4 shows the extracted trace anomaly contribution to the proton mass
$M_{a}/M_{N}$ from the fittings to the data of $\phi$ and J/$\psi$. By the
reference to lattice QCD calculation, we assume that the anomalous
contribution is about $25\%$ as the energy scale goes to infinity. Naively we
assume that the contribution of the trace anomaly in the proton is scale-
dependent. Although the idea is crude, we give a simple expression for the
scale-dependence,

$\frac{M_{a}}{M_{N}}=0.25\exp\left(-\frac{A}{\mu^{2}}\right),$ (13)

where $A$ is a free parameter to be constrained by the extracted trace anomaly
contributions at $\phi$ and J/$\psi$ meson scales. Performing the fit to the
data, we get $A=0.101\pm 0.029$ GeV2 with $\chi^{2}=0.1081$. The underlying
evolution equation for the QCD trace anomaly then is written as,

$\frac{dT_{a}}{d\mu^{2}}=\frac{A}{\mu^{4}}T_{a},$ (14)

where $T_{a}\equiv M_{a}/M_{N}=0.25(1-b)$ is the fraction of the QCD trace
anomaly contribution to the proton mass. According to Eq. (14), we see that
the evolution rate of $T_{a}$ is fast at the low scale. We explain the found
scale-dependence of the trace anomaly in the following paragraph. We give a
prediction of the trace anomaly of the proton at the scale of $\Upsilon$ near-
threshold photoproduction from the empirical scale-dependence established.
This prediction can be tested with the future Electron-Ion Collider (EIC) in
the U.S.A. Accardi  _et al._ (2016); Abdul Khalek  _et al._ (2021) and
Electron-ion collider in China (EicC) Chen (2018); Chen  _et al._ (2020);
Anderle  _et al._ (2021).

The contribution of the gluons to the trace anomaly plays a dominant role in
the processes of $\gamma p\rightarrow p{\rm VectorMeson}$ closed to the
production threshold of the vector meson. From Kharzeev’s method Kharzeev
(1996), the interaction between a vector meson $X$ and the nucleon $N$ can be
described as transferring gluons at the threshold energy region. In the chiral
limit and for the low-energy scattering, the mass of a nucleon state comes
totally from the quantum fluctuations of gluons. But away from the chiral
limit, the QCD trace anomaly and the $\Sigma$-term (the term described with
the parameter $b$ in Eq. (6)) together provide the mass of the proton. The
different vector meson probes interact with the proton are under different
renormalization scales, which are defined as the binding (“Rydberg”) energies
of the vector mesons. The scale-dependence of the trace anomaly can be
understood from the following two physical pictures. First, the gluon density
inside the proton is scale-dependent, which directly quantifies the
contribution of gluon exchange to the scattering between the proton and the
vector meson. Second, the trace anomaly contribution to the proton mass is
anti-proportional to the $\Sigma$-term which introduces the parameter $b$. The
quark masses for $\Sigma_{\pi N}$ and $\Sigma_{sN}$ terms are scale-dependent
according to the renormalization group equation. The quark mass goes down as
the renormalization scale goes up Roberts  _et al._ (2021); Zyla  _et al._
(2020). Both the increasing of the gluon density and the reducing of the quark
mass can qualitatively explain the scale-dependence of the trace anomaly shown
in Fig. 4. The detailed and quantitative studies should be carried out in the
future.

##  IV Summary

In this work we firstly collate the extraction of the trace anomaly
contribution to the proton mass using the experimental data of the
photoproductions of $\phi$ and J/$\psi$ vector mesons under the frame work of
the VMD model. We find that the QCD trace anomaly of the proton is scale-
dependent. The scale-dependence is consistent with the Lattice QCD calculation
at $\mu^{2}=4$ GeV2. For the future studies, we suggest that more theoretical
frameworks on the near-threshold vector meson production is looking forward.
The underlying theory on the scale-dependence of the trace anomaly is needed
for a better understanding of the origin of the proton mass. Last but not
least, more precise data at JLab, the future EIC and EicC will be the key
tests of the observed scale-dependence of the QCD trace anomaly, which will
enhance our understanding of QCD theory.

###### Acknowledgements.

We are very grateful to Dr. Nu XU for his suggestions and the discussions.
This work is supported by the Strategic Priority Research Program of Chinese
Academy of Sciences under the Grant NO. XDB34030301 and the National Natural
Science Foundation of China under the Grant NO. 12005266.

## References

  * Gross and Wilczek (1973a) D. J. Gross and F. Wilczek, Phys. Rev. Lett. 30, 1343 (1973a).
  * Gross and Wilczek (1973b) D. J. Gross and F. Wilczek, Phys. Rev. D8, 3633 (1973b).
  * Gross and Wilczek (1974) D. J. Gross and F. Wilczek, Phys. Rev. D9, 980 (1974).
  * Yang and Mills (1954) C.-N. Yang and R. L. Mills, Phys. Rev. 96, 191 (1954).
  * Wilson (1974) K. G. Wilson, Phys. Rev. D10, 2445 (1974).
  * Ji (1995a) X.-D. Ji, Phys. Rev. Lett. 74, 1071 (1995a), arXiv:hep-ph/9410274 [hep-ph] .
  * Ji (1995b) X.-D. Ji, Phys. Rev. D52, 271 (1995b), arXiv:hep-ph/9502213 [hep-ph] .
  * Buras (1980) A. J. Buras,  _15th Design Automation Conference Las Vegas, Nevada, June 19-21, 1978_ , Rev. Mod. Phys. 52, 199 (1980).
  * Ji (2021) X. Ji, (2021), arXiv:2102.07830 [hep-ph] .
  * Ji and Liu (2021) X. Ji and Y. Liu, (2021), arXiv:2101.04483 [hep-ph] .
  * Gasser  _et al._ (1991) J. Gasser, H. Leutwyler, and M. E. Sainio, Phys. Lett. B253, 252 (1991).
  * Ruiz de Elvira  _et al._ (2018) J. Ruiz de Elvira, M. Hoferichter, B. Kubis, and U.-G. Meißner, J. Phys. G45, 024001 (2018), arXiv:1706.01465 [hep-ph] .
  * Ren  _et al._ (2018) X.-L. Ren, X.-Z. Ling, and L.-S. Geng, Phys. Lett. B783, 7 (2018), arXiv:1710.07164 [hep-ph] .
  * Alarcon  _et al._ (2012) J. M. Alarcon, J. Martin Camalich, and J. A. Oller, Phys. Rev. D 85, 051503 (2012), arXiv:1110.3797 [hep-ph] .
  * Bali  _et al._ (2012) G. S. Bali _et al._ (QCDSF), Phys. Rev. D85, 054502 (2012), arXiv:1111.1600 [hep-lat] .
  * Yang  _et al._ (2016) Y.-B. Yang, A. Alexandru, T. Draper, J. Liang, and K.-F. Liu (xQCD), Phys. Rev. D94, 054503 (2016), arXiv:1511.09089 [hep-lat] .
  * Alarcon  _et al._ (2014) J. M. Alarcon, L. S. Geng, J. Martin Camalich, and J. A. Oller, Phys. Lett. B730, 342 (2014), arXiv:1209.2870 [hep-ph] .
  * Bottino  _et al._ (2000) A. Bottino, F. Donato, N. Fornengo, and S. Scopel, Astropart. Phys. 13, 215 (2000), arXiv:hep-ph/9909228 [hep-ph] .
  * Ellis  _et al._ (2005) J. Ellis, K. A. Olive, Y. Santoso, and V. C. Spanos, Phys. Rev. D 71, 095007 (2005).
  * Ellis  _et al._ (2008) J. Ellis, K. A. Olive, and C. Savage, Phys. Rev. D 77, 065026 (2008).
  * Bottino  _et al._ (2008) A. Bottino, F. Donato, N. Fornengo, and S. Scopel, Phys. Rev. D 78, 083520 (2008).
  * Hill and Solon (2012) R. J. Hill and M. P. Solon, Phys. Lett. B707, 539 (2012), arXiv:1111.0016 [hep-ph] .
  * Cline  _et al._ (2013) J. M. Cline, P. Scott, K. Kainulainen, and C. Weniger, Phys. Rev. D 88, 055025 (2013).
  * Boussarie and Hatta (2020) R. Boussarie and Y. Hatta, Phys. Rev. D101, 114004 (2020), arXiv:2004.12715 [hep-ph] .
  * Hatta and Yang (2018) Y. Hatta and D.-L. Yang, Phys. Rev. D98, 074003 (2018), arXiv:1808.02163 [hep-ph] .
  * Hatta  _et al._ (2019) Y. Hatta, A. Rajan, and D.-L. Yang, Phys. Rev. D100, 014032 (2019), arXiv:1906.00894 [hep-ph] .
  * Yang  _et al._ (2018) Y.-B. Yang, J. Liang, Y.-J. Bi, Y. Chen, T. Draper, K.-F. Liu, and Z. Liu, Phys. Rev. Lett. 121, 212001 (2018).
  * Kharzeev (1996) D. Kharzeev, Proc. Int. Sch. Phys. Fermi 130, 105 (1996), arXiv:nucl-th/9601029 .
  * Kharzeev  _et al._ (1999) D. Kharzeev, H. Satz, A. Syamtomov, and G. Zinovjev, Eur. Phys. J. C9, 459 (1999), arXiv:hep-ph/9901375 [hep-ph] .
  * Wang  _et al._ (2020) R. Wang, J. Evslin, and X. Chen, Eur. Phys. J. C 80, 507 (2020), arXiv:1912.12040 [hep-ph] .
  * Mibe  _et al._ (2005) T. Mibe _et al._ (LEPS), Phys. Rev. Lett. 95, 182001 (2005), arXiv:nucl-ex/0506015 .
  * Ali  _et al._ (2019) A. Ali _et al._ (GlueX), Phys. Rev. Lett. 123, 072001 (2019), arXiv:1905.10811 [nucl-ex] .
  * Peskin (1979) M. E. Peskin, Nucl. Phys. B156, 365 (1979).
  * Kharzeev  _et al._ (1996) D. Kharzeev, H. Satz, A. Syamtomov, and G. Zinovev,  _Quark matter ’96. Proceedings, 12th International Conference on Ultrarelativistic Nucleus Nucleus Collisions, Heidelberg, Germany, May 20-24, 1996_ , Phys. Lett. B389, 595 (1996), arXiv:hep-ph/9605448 [hep-ph] .
  * Gribov and Pomeranchuk (1963) V. N. Gribov and I. Ya. Pomeranchuk, Sov. Phys. JETP 16, 1387 (1963), [Zh. Eksp. Teor. Fiz.43,1970(1962); Phys. Rev. Lett.9,239(1962)].
  * Deur  _et al._ (2016) A. Deur, S. J. Brodsky, and G. F. de Teramond, Nucl. Phys. 90, 1 (2016), [Prog. Part. Nucl. Phys.90,1(2016)], arXiv:1604.08082 [hep-ph] .
  * Glück  _et al._ (1998) M. Glück, E. Reya, and A. Vogt, Eur. Phys. J. C5, 461 (1998), arXiv:hep-ph/9806404 [hep-ph] .
  * Dulat  _et al._ (2016) S. Dulat, T.-J. Hou, J. Gao, M. Guzzi, J. Huston, P. Nadolsky, J. Pumplin, C. Schmidt, D. Stump, and C. P. Yuan, Phys. Rev. D93, 033006 (2016), arXiv:1506.07443 [hep-ph] .
  * Griffiths (2008) D. Griffiths,  _Introduction to Elementary Particles_, Physics textbook (Wiley, 2008).
  * Accardi  _et al._ (2016) A. Accardi _et al._ , Eur. Phys. J. A 52, 268 (2016), arXiv:1212.1701 [nucl-ex] .
  * Abdul Khalek  _et al._ (2021) R. Abdul Khalek _et al._ , (2021), arXiv:2103.05419 [physics.ins-det] .
  * Chen (2018) X. Chen, PoS DIS2018, 170 (2018), arXiv:1809.00448 [nucl-ex] .
  * Chen  _et al._ (2020) X. Chen, F.-K. Guo, C. D. Roberts, and R. Wang, Few Body Syst. 61, 43 (2020), arXiv:2008.00102 [hep-ph] .
  * Anderle  _et al._ (2021) D. P. Anderle _et al._ , (2021), arXiv:2102.09222 [nucl-ex] .
  * Roberts  _et al._ (2021) C. D. Roberts, D. G. Richards, T. Horn, and L. Chang, (2021), arXiv:2102.01765 [hep-ph] .
  * Zyla  _et al._ (2020) P. A. Zyla _et al._ (Particle Data Group), PTEP 2020, 083C01 (2020).


# Comparison communication protocols

Michael R. Klug

###### Abstract

We introduce a restriction of the classical 2-party deterministic
communication protocol where Alice and Bob are restricted to using only
comparison functions. We show that the complexity of a function in the model
is, up to a constant factor, determined by a complexity measure analogous to
Yao’s tiling number, which we call the geometric tiling number which can be
computed in polynomial time. As a warm-up, we consider an analogous restricted
decision tree model and observe a 1-dimensional analog of the above results.

##  1 Introduction

Communication complexity is the study of several related models of computation
that measure and attempt to minimize the amount of information that needs to
be communicated between different parties to compute a function. It has been
remarkably successful within computational complexity with strong lower bounds
having been proven in various models of communication complexity. Many of
these results have had applications throughout theoretical computer science,
including leading to lower bounds in other concrete models of computation (for
example circuit depth). In this note, we study a variation of the usual
2-party deterministic communication protocol where Alice and Bob are
restricted to only using comparison functions. As a warm-up, we study the
analogous restriction of the usual deterministic decision tree model where the
query node functions are restricted to being comparison functions. This
restricted decision tree model “collapses” in the sense that there is a simple
to compute lower bound for the complexity in this model that also is an upper
bound and hence determining the complexity of a function in this model is
straight-forward. Up a dimension, an analogous lower bound holds for our
restricted communication complexity model and, up to a constant factor, this
model also collapses in the same sense that the lower bound ends up being an
upper bound. This bound for the complexity of our model is similar to the
tiling number introduced by Yao [10]. We then show that this modified tiling
number can be computed in polynomial time.

We now elaborate on some of the specifics of the models under discussion
although precise details will be withheld until the relevant sections. Let
$f:X\times Y\to Z$. In the classical 2-party deterministic communication
complexity model, Alice and Bob are each given half of the input, $x\in X$ and
$y\in Y$, respectively, and asked to together compute $f(x,y)$ using some
protocol $\mathcal{P}$. The size of $\mathcal{P}$ is the worst-case number of
bits that need to be exchanged between Alice and Bob in order to arrive at
$f(x,y)$ and the complexity of $f$, denoted $C(f)$ is the minimal size of a
protocol $\mathcal{P}$ that computes $f$. For simplicity, we restrict our
attention to functions of the form
$f:\\{0,1\\}^{n}\times\\{0,1\\}^{n}\to\\{0,1\\}$ together with the
lexicographical ordering on $\\{0,1\\}^{n}$.

A lower bound for $C(f)$ dating back to Yao’s original article is the
invariant $\chi(f)$ which is the minimum number of tilings of any
$f$-monochromatic tiling of $\\{0,1\\}^{n}\times\\{0,1\\}^{n}$. By taking any
protocol $\mathcal{P}$ that computes $f$ and labeling every element $(x,y)\in
X\times Y$ by the communication history between Alice and Bob when the
protocol is run on the input $(x,y)$, Yao observed that the subset of $X\times
Y$ with a given communication history is not arbitrary, but rather is always
combinatorial rectangles, thus leading to the bound $C(f)\geq\log\chi(f)$.
Many other lower bound techniques in this setting follow by giving lower
bounds for $\chi(f)$ (for example, the size of a fooling set for $f$, the rank
of $M(f)$, or the reciprocal of the discrepancy of $M(f)$ all yield lower
bounds for $C(f)$ by giving lower bounds for $\chi(f)$ – see [8]).

We introduce here a variation of (in fact, a weakening of) the deterministic
2-party communication complexity model which we call the _comparison
communication complexity model_. A comparison function is a function of the
form $\theta_{x}:\\{0,1\\}^{n}\to\\{0,1\\}$ with $x\in\\{0,1\\}^{n}$ and
$\theta_{x}(y)=1$ if and only if $y\geq x$. In the comparison communication
complexity model, Alice and Bob’s computational power is limited to the use of
comparison functions (as opposed to arbitrary functions which are allowed in
the classical model). We denote the complexity of a function in this model by
$C^{\operatorname{comp}}(f)$. We find a variation of Yao’s tiling number,
using geometric rectangles in place of combinatorial rectangles (see section
3), which we denote by $\chi^{\operatorname{geom}}(f)$. We prove that up to a
logarithm and a constant factor $C(f)$ is equal to
$\chi^{\operatorname{geom}}(f)$. Motivated by this, we give a polynomial-time
algorithm for computing $\chi^{\operatorname{geom}}(f)$ that comes from a more
general consideration of finding the minimal number of rectangles needed to
tile a finite planar region that can be tiled by rectangles.

As a warm-up to this, we study a variation on the decision tree model, where
instead of allowing arbitrary coordinate query functions, the query functions
are comparison functions. We denote the complexity of a function with respect
to this model by $D^{\operatorname{comp}}(f)$. We find an explicit formula for
$D^{\operatorname{comp}}(f)$ in terms of a simple to compute complexity
measure $\mu(f)$, which is essentially a one-dimensional version of
$\chi^{\operatorname{geom}}$.

In section 2, we discuss the comparison decision tree model, give a formula
for computing the complexity of a function in this model which can be computed
in polynomial time, compare the complexity of a few functions in this model
with the complexity of those functions in the classical decision tree model,
and show that many functions have large complexity for this model. In section
3, we introduce and prove that analogous results for the comparison
communication complexity model where we show that the complexity of a function
in this model is $\Theta(\chi^{\operatorname{geom}}(f))$ where
$\chi^{\operatorname{geom}}$ is a complexity measure that is analogous to
Yao’s tiling number $\chi$ but with geometric rectangles used in place of
combinatorial rectangles.

##  2 Comparison decision trees

In the classical decision tree model of computation, one considers decision
trees $\mathcal{T}$ that compute a given boolean function
$f:\\{0,1\\}^{n}\to\\{0,1\\}$ where each non-leaf vertex $v$ in $\mathcal{T}$
is labeled by a query function of the form $\pi_{i}:\\{0,1\\}^{n}\to\\{0,1\\}$
for some $1\leq i\leq n$, where $\pi_{i}$ is projection onto the $i$-th
coordinate. The decision tree complexity of $f$, denoted by $D(f)$ is the
worst-case number of queries needed for a decision tree $\mathcal{T}$ to
compute $f$, minimized over all such decision trees $\mathcal{T}$ that compute
$f$ (see [2]).

We consider a variation of this model which we call the comparison decision
tree model where instead of having the vertices of a decision tree
$\mathcal{T}$ labeled by projection functions, each such $v$ is labeled by a
comparison function $\theta_{x}:\\{0,1\\}^{n}\to\\{0,1\\}$ where
$x\in\\{0,1\\}^{n}$ and $\theta_{x}(y)=1$ if and only if $y\geq x$ where here
we are using the lexicographical ordering on $\\{0,1\\}^{n}$. We additionally
we allow vertices to be labeled by the constant 0 function (which can be
thought of as asking if the input is less than $0^{n}$) – note that the
constant 1 function is given by $\theta_{1^{n}}$. We call such trees
comparison decision trees and define $D^{\operatorname{comp}}(f)$ analogously
to $D(f)$ but with comparison decision trees in place of decision trees.

We have the following immediate upper bound, identical to the trivial upper
bound for the classical decision tree complexity:

######  Proposition 1.

For all $f:\\{0,1\\}^{n}\to\\{0,1\\}$,

$D^{\operatorname{comb}}(f)\leq n$

###### Proof.

We construct a comparison decision tree $\mathcal{T}$ that computes $f$ in $n$
queries on all inputs. The first query determines if the input, considered as
the binary representation of a number, is in $[0,2^{n-1}]$ or
$(2^{n-1},2^{n}]$. The next round of queries further determines which half of
each of these intervals the input is in. Continuing in this fashion, after $n$
queries, we know exactly what the input is and we label those leaves of
$\mathcal{T}$ appropriately according to $f$. ∎

We now introduce a complexity measure of boolean functions that, for
comparative decision trees, completely captures the complexity. For
$f:\\{0,1\\}^{n}\to\\{0,1\\}$, let $\mu(f)$ denote the number of maximal
connected blocks of zeroes and of ones that occur in the length $2^{n}$-list
of the values of $f$ on the $2^{n}$ different inputs, ordered with the
lexicographical ordering.

The following result gives a straightforward formula for the complexity of the
comparison decision tree model and shows that $D^{\operatorname{comp}}(f)$ is
computable in polynomial time given $f$. Thus in some sense, the comparative
decision tree model collapses to something not so interesting. In contrast,
computing $D(f)$ is known to be NP-complete [5].

######  Theorem 1.

For all $f:\\{0,1\\}^{n}\to\\{0,1\\}$,

$\lceil\log\mu(f)\rceil=D^{\operatorname{comp}}(f)$

###### Proof.

We begin by proving that $\lceil\log\mu(f)\rceil\leq
D^{\operatorname{comp}}(f)$ The key observation is that whenever $f(x)\neq
f(x+1)$, then, for any comparison decision tree $\mathcal{T}$ that computes
$f$, there must be some vertex in $\mathcal{T}$ with the query function
$\theta_{x}$. Therefore, any such $\mathcal{T}$ computing $f$ must have at
least $\mu(f)-1$ query vertices.

Since the underlying tree of $\mathcal{T}$ is a full binary tree (i.e., each
non-leaf vertex has exactly two children), $\mu(f)$ is less than or equal to
the number of leaves of $\mathcal{T}$. Now the fact that
$\lceil\log\mu(f)\rceil\leq D^{\operatorname{comp}}(f)$ follows since the
number of leaves of $\mathcal{T}$ is less than or equal to
$2^{\operatorname{depth}(\mathcal{T})}$ and $D^{\operatorname{comp}}(f)$ is by
definition the minimum $\operatorname{depth}(\mathcal{T})$ for all
$\mathcal{T}$ that compute $f$.

For the other direction, namely that $\lceil\log\mu(f)\rceil\geq
D^{\operatorname{comp}}(f)$, note that we can construct a comparative decision
tree by a binary search as in the proof of Proposition 1 to determine which of
the $\mu(f)$ blocks the input is in. This requires at worst
$\lceil\log\mu(f)\rceil$ queries. ∎

The following two examples show that $D(f)$ and $D^{\operatorname{comp}}(f)$
can differ arbitrarily.

######  Example 1.

For $1^{n}\in\\{0,1\\}^{n}$, consider the comparison function
$\theta_{1^{n}}$. Then $D^{\operatorname{comp}}(\theta_{x})=1$, whereas
$s_{1^{n}}(\theta_{1^{n}})$ and therefore $s(\theta_{1^{n}})=n$ (where here
$s$ denotes the sensitivity), and therefore $D(\theta_{1^{n}})=n$.

######  Example 2.

Consider the projection function $\pi_{n}:\\{0,1\\}^{n}\to\\{0,1\\}$ which
gives the last coordinate. Then $D(\pi_{n})=1$, however $\mu(\pi_{n})=2^{n}$
and therefore, $D^{\operatorname{comp}}(f)=n$.

In the classical decision tree model, almost all boolean functions have
maximal decision tree complexity (i.e., the limit as $n$ goes to infinity of
the probability that a random boolean function $f:\\{0,1\\}\to\\{0,1\\}$ has
$D(f)=n$ goes to 1 – see, for example [2]). We now show that this is not the
case in the comparison decision tree model and in fact the analogous limit is
equal to $1/2$:

######  Proposition 2.

For all natural numbers $n$, we have

$\\#\\{f:\\{0,1\\}\to\\{0,1\\}:D^{\operatorname{comp}}(f)=n\\}=2^{2^{n}-1}$

###### Proof.

By Theorem 1, we have

$\\#\\{f:\\{0,1\\}\to\\{0,1\\}:D^{\operatorname{comp}}(f)=n\\}=\\#\\{f:\\{0,1\\}\to\\{0,1\\}:\mu(f)>2^{n-1}\\}$

Noting that

$\\#\\{f:\\{0,1\\}^{n}\to\\{0,1\\}:\mu(f)=k\\}=2\binom{2^{n}-1}{k-1}$

we have

$\displaystyle\\#\\{f:\\{0,1\\}^{n}\to\\{0,1\\}:\mu(f)>2^{n-1}\\}$
$\displaystyle=\sum_{k=2^{n-1}}^{2^{n}-1}{2\binom{2^{n}-1}{k-1}}$
$\displaystyle=2^{2^{n}-1}$

∎

##  3 Comparison 2-party deterministic communication complexity

We introduce here a variation of the classical 2-party deterministic
communication complexity model which we will call the comparative (2-party
deterministic communication complexity) model. We will introduce a quantity
analogous to $\chi$ which we will denote by $\chi_{\text{geo}}$ (short for
“geometric”) and we will prove the analog of the result of Yao that
$D(f)\log\chi(f)$ in our setting.

We now define the 2-party comparison communication complexity model which is a
restriction of the classical 2-party communication complexity model. In the
classical model, we are given a function
$f:\\{0,1\\}^{n}\times\\{0,1\\}^{n}\to\\{0,1\\}$ and we consider communication
complexity protocols $\mathcal{P}$ that compute $f$, where each non-leaf
vertex $v$ of $\mathcal{P}$ is either an arbitrary function
$a_{v}:\\{0,1,\\}^{n}\to\\{0,1\\}$ or $b_{v}:\\{0,1,\\}^{n}\to\\{0,1\\}$ that
operates on Alice’s or Bob’s inputs respectively. The cost of such a protocol
$\mathcal{P}$ is the worst case number of edges that must be traversed over
all inputs, and the communication complexity of $f$, denoted $C(f)$, is the
minimization over all protocols $\mathcal{P}$ that compute $f$ of the cost of
$\mathcal{P}$. We modify the allowed protocols to define the comparison model
by only allowing protocols $\mathcal{P}$ where all of the vertex functions are
of the form $a_{v}=\theta_{x_{v}}$ or $b_{v}=\theta_{x_{v}}$ (operating on
Alice’s or Bob’s inputs respectively) for some $x_{v}\in\\{0,1\\}^{n}$ (where,
as in the previous section, $\theta_{x_{v}}(y)=1$ if and only if $y\geq x$).
Additionally, as in the previous comparison decision tree model, we allow also
for the vertices to be labeled by the constant 0 function (note the constant
one function is $\theta_{1^{n}}$. We define the cost of a comparative
communication protocol and the comparative communication complexity of $f$,
denoted $C^{\operatorname{comp}}(f)$ in direct analogy with the classical case
– namely the minimum over all comparison protocols $\mathcal{P}$ that compute
$f$ of $\operatorname{depth}(\mathcal{P})$.

Since any a comparative communication protocol is also classical communication
protocol, we always have

$C(f)\leq C^{\operatorname{comp}}(f)$

We have the following upper bound:

######  Theorem 2.

For all $f:\\{0,1\\}^{n}\times\\{0,1\\}^{n}\to\\{0,1\\}$, we have

$C^{\operatorname{comp}}(f)\leq 2n+1$

###### Proof.

We will reason as usual with Alice and Bob, however, it is important to bear
in mind that they are no longer all powerful (as in the the classical model).
In particular, even once Bob knows Alice’s input, he might still need some
time using comparison functions to determine the output.

Alice begins by telling Bob her input by first telling Bob if it represents a
number in the interval $[0,2^{n-1}]$ or not. If yes, she then says whether her
input represents a number in the interval $[0,2^{n-2}]$ or not. If no, she
says whether her input is in the interval $(2^{n-1},2^{n-1}+2^{n-2}]$ or not.
All this is accomplished using appropriate comparison functions and after the
application of at most $n$ comparison functions, Alice will have told Bob her
input.

Now through an analogous process, Bob can determine his input by a similar
process and then the leaf of the resulting tree can be labeled by the
appropriate constant. ∎

A subset $R\subset X\times Y$ is called a combinatorial rectangle if
$R=A\times B$ for some sets $A\subset X$ and $B\subset Y$. A tiling of
$X\times Y$ is a partition of $X\times Y$ into a disjoint collection of
combinatorial rectangles. Given a function $f:X\times Y\to Z$, a combinatorial
rectangle $S\subset X\times Y$ is $f$-monochromatic if $f$ is constant on $S$.
A tiling is $f$-monochromatic if all of the combinatorial rectangles in the
tiling are $f$-monochromatic.

In contrast to combinatorial rectangles, if $X$ and $Y$ are both given fixed
total orderings $<_{X}$ and $<_{Y}$ respectively, then a geometric rectangle
is subset $R=A\times B\subset X\times Y$ with the property that $A=\\{a\in
A:a_{\text{mi}}\leq a\leq a_{\text{max}}\\}$ and such that $B=\\{b\in
B:b_{\text{mi}}\leq b\leq b_{\text{max}}\\}$ for some
$a_{\text{min}},a_{\text{max}}\in A$ and $b_{\text{min}},b_{\text{max}}\in B$.
This terminology of geometric rectangles comes from the fact that such sets
are honest connected rectangles (in the everyday usage sense) when considered
as subsets of the matrix $M_{<_{X},<_{Y}}(f)$ whose $(i,j)$-entry is the value
$f(a_{i},a_{j})$ (here assuming $X$ and $Y$ are finite).

Specializing to our familiar setting with
$f:\\{0,1\\}^{n}\times\\{0,1\\}^{n}\to\\{0,1\\}$, a lower bound for the
classical 2-party communication complexity of $f$, $C(f)$, dating back to
Yao’s original article introducing communication complexity is the invariant
$\chi(f)$ which is defined as the minimum number of tilings of any
$f$-monochromatic tiling of $\\{0,1\\}^{n}\times\\{0,1\\}^{n}$. By taking any
protocol $\mathcal{P}$ that computes $f$ and labeling every entry of element
$(x,y)\in\\{0,1\\}^{n}\times\\{0,1\\}^{n}$ by the communication history
between Alice and Bob when the protocol is run on the input $(x,y)$, Yao
observed that the subset of $X\times Y$ with a given communication history is
not arbitrary, but rather is always an $f$-monochromatic combinatorial
rectangle, thus leading to the bound $D(f)\geq\log\chi(f)$.

We now prove an analogous result in the setting of comparison communication
complexity with geometric rectangles in place of combinatorial rectangles. Let
$\chi^{\operatorname{geom}}(f)$ denote the minimal number of $f$-monochromatic
geometric rectangles needed to tile $\\{0,1\\}^{n}\times\\{0,1\\}^{n}$, where
here and from now on we are using the lexicographical ordering on
$\\{0,1\\}^{n}$. The proof is completely analogous to the proof of Yao’s
result in [10] – see also Exercise 1.8 of [8].

######  Theorem 3.

For all $f:\\{0,1\\}^{n}\times\\{0,1\\}^{n}\to\\{0,1\\}$, we have

$\log\chi^{\operatorname{geom}}(f)\leq C^{\operatorname{comp}}(f)$

###### Proof.

Let $\mathcal{P}$ be a communication protocol that computes $f$. We prove that
for each vertex $v$ in $\mathcal{P}$, the set of all inputs that go through
$v$ when given to $\mathcal{P}$ forms a geometric rectangle. For each leaf
vertex, these rectangles are then $f$-monochromatic.

We proceed by induction on the depth of the vertex $v$. For the root vertex,
the corresponding set is all of $\\{0,1\\}^{n}\times\\{0,1\\}^{n}$ and hence a
geometric rectangle. Given a vertex $v$ with depth greater than 0, we let
$v^{\prime}$ denote the parent vertex of $v$. Let $R_{v}$ and $R_{v^{\prime}}$
denote the sets of all inputs that pass through $v$ and $v^{\prime}$. By the
inductive hypothesis, we have
$R_{v}=[x_{\min},x_{\max}]\times[y_{\min},y_{\max}]$ for some
$x_{\min},x_{\max},y_{\min},y_{\max}\in\\{0,1\\}^{n}$. Without loss of
generality, we assume that the vertex $v^{\prime}$ is one of Alice’s vertices
and we let $\theta_{x^{\prime}}$ denote the corresponding query function.
There are three possibilities: (1) $x^{\prime}<x_{\min}$, (2) $x^{\prime}\geq
x_{\max}$, or (3) $x_{\min}\leq x_{v^{\prime}}\leq x_{\max}$. In case (1),
$R_{v}$ is empty. In case (2), $R_{v}=R_{v^{\prime}}$. In case (3),
$R_{v}=[x_{\min},x^{\prime}]\times[y_{\min},y_{\max}]$. In any case,
$R_{v^{\prime}}$ is again a geometric rectangle.

Therefore, we obtain from $\mathcal{P}$ a geometric tiling of
$\\{0,1\\}^{n}\times\\{0,1\\}^{n}$ with the number of tiles being equal to the
number of leaves of $\mathcal{P}$. Since the number of leaves of $\mathcal{P}$
is at most $2^{\operatorname{depth}(\mathcal{P})}$, then
$2^{\operatorname{depth}(\mathcal{P})}\geq\chi^{\operatorname{geom}}(f)$.
Since this holds for all protocols $\mathcal{P}$ computing $f$, the result
follows. ∎

Just as Yao’s tiling number lower bound extends trivially to communication
protocols for computing relations (as used for example in proving circuit
depth lower bounds), the above result extends as well to comparison
communication protocols for relations.

We now give an example illustrating that $C(f)$ and
$C^{\operatorname{comb}}(f)$ can differ arbitrarily.

######  Example 3.

Let $\operatorname{PARITY}_{2n}:\\{0,1\\}^{n}\times\\{0,1\\}^{n}\to\\{0,1\\}$
with $\operatorname{PARITY}_{2n}(x,y)$ equal to the party of the number of 1’s
in $(x,y)$. Then the protocol where Alice sends Bob the parity of her input
and Bob then adds that to the parity of his input shows that
$C(\operatorname{PARITY}_{2n})=2$. For contrast, we have
$\chi^{\operatorname{geom}}(\operatorname{PARITY}_{2n})=2^{2n}$ and therefore
$C^{\operatorname{comp}}(\operatorname{PARITY}_{2n})\geq 2n$.

Note that this example shows that the analog of the log-rank conjecture fails
for the comparative communication complexity model since the rank of
$\operatorname{PARITY}_{2n}$ is 2 for $n\geq 2$.

######  Theorem 4.

For all $f:\\{0,1\\}^{n}\times\\{0,1\\}^{n}\to\\{0,1\\}$, we have
$C^{\operatorname{comp}}(f)=\Theta(\log\chi^{\operatorname{geom}}(f))$.

###### Proof.

From Theorem 3, it suffices to show that
$C^{\operatorname{comp}}(f)=\Omega(\log\chi^{\operatorname{geom}}(f))$.
Suppose we are given a geometric $f$-monochromatic tiling of
$\\{0,1\\}^{n}\times\\{0,1\\}^{n}$, $T$ where $T$ has
$\chi^{\operatorname{geom}}(f)$ tiles. We now construct a comparison protocol
$\mathcal{P}$ for $f$ using $T$.

Visualizing $T$ as a tiling of the matrix $M(f)$, we see that the tops and
bottoms of the rectangles extend to lines, of which there are at most
$\chi^{\operatorname{geom}}+1$. The comparison protocol begins with Alice
using comparisons in a binary search fashion to tell Bob between which two
horizontal lines constructed from $T$ her input is between. This requires
$\lceil\log\chi^{\operatorname{geom}}(f)\rceil$ comparison queries. Similarly,
Bob can determine the tile in $T$ that the input is in by using
$\lceil\log\chi^{\operatorname{geom}}(f)\rceil$ comparison queries
corresponding to the vertical lines coming from extending the tiles of $T$.
After this, the leaf is labeled with the appropriate output corresponding to
if the corresponding tile $t\in T$ is a 0-rectangle or a 1-rectangle. Thus in
total, the cost of this protocol $\mathcal{P}$ is
$2\lceil\log\chi^{\operatorname{geom}}(f)\rceil$. ∎

In [1], Aho, Ullman, and Yannnkakis proved that $D(f)=O(\log^{2}\chi(f))$. In
[8], the question is raised if this square factor can be removed – namely, if
$D(f)=O(\log\chi(f))$ (which would imply $D(f)=\Theta(\log\chi(f))$ are in
fact equal), however this was disproved in [4]. The question of exactly how
small the exponent can be made is still open [9]. In light of this, theorem 4
highlights the distinction between $\chi$ and $\chi^{\operatorname{geom}}$ by
showing that in the context of comparison communication complexity and
$\chi^{\operatorname{geom}}$, the exponent can be taken to be 1.

Komlós proved that a random (0,1)-matrix of size $m\times m$ has rank $m$
(over $\mathbb{Q}$) with probability tending to $1$ as $m$ goes to infinity
[6]. Therefore, using the rank lower bound for classical communication
complexity [7], almost all functions are hard from the perspective of
classical communication complexity (i.e., if
$f:\\{0,1\\}^{n}\times\\{0,1\\}^{n}\to\\{0,1\\}$ then $C(f)=n+1$). Since
$C(f)\leq C^{\operatorname{geom}}(f)$, this implies that almost all functions
$f:\\{0,1\\}^{n}\times\\{0,1\\}^{n}\to\\{0,1\\}$ have
$C^{\operatorname{comp}}(f)\geq n$. We are not sure to what extent this can be
improved.

The quantity $\chi^{\operatorname{geom}}(f)$ can be computed in polynomial-
time given $f$ by finding the minimal number of rectangles needed to tile the
planar regions given by the region of the matrix $M(f)$ consisting of zeroes
and the the region of the matrix $M(f)$ consisting of ones. These quantities
can be found in polynomial time using for example the algorithms for finding
minimal rectangulations of planar regions that can be built from rectangles as
in section 3 of [3] and the references therein.

## References

  * [1] Alfred V Aho, Jeffrey D Ullman, and Mihalis Yannakakis.  On notions of information transfer in VLSI circuits.  In Proceedings of the fifteenth annual ACM symposium on Theory of computing, pages 133–139, 1983.
  * [2] Harry Buhrman and Ronald de Wolf.  Complexity measures and decision tree complexity: a survey.  Theoretical Computer Science, 288(1):21–43, 2002.
  * [3] David Eppstein.  Graph-theoretic solutions to computational geometry problems.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 1–16. Springer, 2009.
  * [4] Mika Göös, Toniann Pitassi, and Thomas Watson.  Deterministic communication vs. partition number.  SIAM Journal on Computing, 47(6):2435–2450, 2018.
  * [5] Laurent Hyafil and Ron Rivest.  Constructing optimal binary search trees is np complete.  Information Processing Letters, 1976.
  * [6] János Komlós.  On the determinant of (0-1) matrices.  Studia Scientiarium Mathematicarum Hungarica, 2:7–21, 1967.
  * [7] Kurt Mehlhorn and Erik M Schmidt.  Las Vegas is better than determinism in VLSI and distributed computing.  In Proceedings of the fourteenth annual ACM symposium on Theory of computing, pages 330–337, 1982.
  * [8] Noam Nisan and Eyal Kushilevitz.  Communication Complexity.  Cambridge University Press, Cambridge, 1997.
  * [9] Anup Rao and Amir Yehudayoff.  Communication Complexity and Applications.  Cambridge University Press, 2020.
  * [10] Andrew Chi-Chih Yao.  Some complexity questions related to distributive computing (preliminary report).  In Proceedings of the eleventh annual ACM symposium on Theory of computing, pages 209–213, 1979.