\section{Introduction}

The various six-dimensional supersymmetric gauge theories attract a
certain interest in context of string/brane dynamics. It is known
that the superconformal $\cN=(2,0)$ theory of self-dual tensor
multiplet is closely related with low-energy dynamics of M5-branes
(see, e.g., for a review \cite{L,BL}). The study of the maximally
extended $\cN=(1,1)$ SYM theory in six-dimensions is motivated by
the connection with D5-branes (see \cite{GK} for a review). Both the
$\cN=(2,0)$ superconformal field theory and the $\cN=(1,1)$ SYM
theory were also considered as low energy limits for the little
string theories with corresponding $\cN=(2,0)$ and $\cN=(1,1)$
supersymmetries (see \cite{Ah,K}).

The $\cN=(1,1)$ SYM theory is a maximally extended supersymmetric
gauge theory of vector multiplet in six dimensions. This theory can
be treated as the $\cN=(1,0)$ vector multiplet theory coupled to
hypemultiplet which transforms under the adjoint representation of
gauge group. Although the $\cN=(1,1)$ theory is non-renormalizable
by power counting, it possesses the remarkable properties in quantum
domain and it is the subject of comprehensive research. It was
proved that the theory under consideration is on-shell finite at
one- and two loops \cite{FT,MS1,MS2,HS,HS1,BHS,BHS1} and the first
divergences here can appear only starting from three loops (see e.g.
\cite{Bork} and the references therein). Moreover it was shown,
using the $6D$ harmonic superspace approach
\cite{BIKOS,GIOS,HST,HSW,Zupnik,ISZ,IS,BIS}, that the one- and some
two-loop divergent contributions to effective action in $\cN=(1,1)$
SYM theory are finite even off-shell \cite{BIMS2,BIMS3,BIMS4} in
Fermi-Feynman gauge\footnote{The study of the gauge dependence of
the one-loop divergent contributions to one-loop effective actions
in $\cN=(1,0)$ and $\cN=(1,1)$ SYM was recently done in
\cite{BIMS5,BIMS6,BIMS7}}. The finite leading low energy
contributions to one-loop effective action were recently calculated
in superfield approach as well \cite{BIM}. Also we point out that
the essential progress in studying of the $\cN=(1,1)$ theory was
achieved in analysis of four-point on-shell scattering amplitudes
\cite{Yin1,Yin2,Amplitudes1,Amplitudes2,Amplitudes3}. In particular,
the leading and subleading divergences in all loops are obtained in
the framework of the spinor-helicity and on-shell supersymmetric
formalism (the recent results are presented in the review
\cite{Amplitudes4}).

In the present paper we study the quantum aspects of the $\cN=(1,0)$
and $\cN=(1,1)$ gauge theories in the framework of component
approach. As well known, in supersymmetric quantum field theory the
component and superfield approaches complement each other. The
component formulation of SUSY theories, although does not possess
the manifest supersymmetry, very closely relates with conventional
field theory and allows to analyze and test independently the
results which where obtained in superfield approach. Besides, the
component approach allows to use efficiently in SUSY theories the
different special methods well developed in conventional quantum
field theory. In four dimensional SUSY theories the component and
superfield approaches were developed in parallel. As to
six-dimensional SUSY theories, the component analysis of off-shell
quantum effective action is not well worked out in many details.

In this paper we are going to focus on the component calculations of
the one-loop divergences in $\cN=(1,0)$ and $\cN=(1,1)$ gauge
theories and derive the leading low-energy contribution to one-loop
effective action in $\cN=(1,1)$ theory in bosonic sector. Also we
will demonstrate the absence of the one-loop contribution to
effective potential for constant background scalar fields in the
$\cN=(1,1)$ SYM theory.

The  paper is organized as follows. In section 2 we  briefly discuss
some details of the supersymmetry in six dimensions. Also we present
an independent derivation of the action for six-dimensional ${\cal
N}=(1,0)$ SYM theory in terms of physical component fields and the
corresponding supersymmetry transformations of these fields. In
section 3, using the background field method, we evaluate the
one-loop effective action. Then we calculate the logarithmic
divergent contributions to one-loop effective action in the
$\cN=(1,0)$ and $\cN=(1,1)$ SYM theories. Section 4 includes the
details of calculation of leading low-energy contributions to
one-loop effective action and one-loop contribution to the effective
potential. The last section contains discussion of obtained results
and some possible further directions of the work.

\section{Six-dimensional $\cN=(1,0)$ SYM theory}

We begin with discussing the classical six-dimensional $\cN=(1,0)$
SYM theory. The $\cN=(1,0)$ SYM theory in six dimensions describes
the interaction of vector multiplet with a set of hypermultiplets.
The six-dimensional on-shell vector multiplet consists of real
vector field  $A_M$ and a left-handed $\lambda^{a}_i$ pseudoreal
Weyl spinor one, both in adjoint representation of gauge group. The
on-shell hypermultiplet contains complex scalar $\vp^{{\cA} i}$ and
right-handed $\psi^{\cA}_{a}$ pseudoreal Weyl spinor fields. We
denote the indices of spinor representation by the small latin
letters $a,b,..=1,2,3,4$ and for Minkowski space-time indices stand
the capital ones $M,N,..=0,1,..,5$. The indices $i,j,..=1,2$
correspond to $SU(2)$ group of $R$-symmetry of $\cN=(1,0)$
superalgebra in six dimensions. By the calligraphic letters ${\cA},
{\cB}, ..$ we denote the Pailu-G\"ursey $SU(2)$ indexes. Both
$i,j,..$ and ${\cA}, {\cB},..$ are lowered and raised by
antisymmetric quantities $\epsilon_{ij}$ and $\epsilon_{\cA\cB}$
correspondingly.

We use the antisymmetric representation of six-dimensional Weyl
matrices
 \bea
 (\gamma_M)_{ab} = - (\gamma_M)_{ba}\,, \quad
 (\tilde{\gamma}_M)^{ab} = \tfrac12\varepsilon^{abcd}(\gamma_M)_{cd}\,,
 \eea
where $\varepsilon^{abcd}$ is the totally antisymmetric tensor. The
matrices $\gamma_M$ and $\tilde{\gamma}_M$ subject to basic
relations for Weyl matrices
 \bea
 (\gamma_M)_{ac} (\tilde{\gamma}_N)^{cb}+ (\gamma_N)_{ac} (\tilde{\gamma}_M)^{cb} = -2 \delta_a{}^b \eta_{MN},
 \qquad (\gamma^M)_{ac} ({\gamma}_M)_{cb} = 2 \varepsilon_{abcd}\,.
  \eea
We choose the Minkowski metric $\eta_{MN}$ with a mostly negative
signature. The generators of the spinor representation $\sigma_{MN}$
are real, where
 \bea
 (\sigma_{MN})^a{}_b = \f12 (\tilde{\gamma}^M \gamma^N - \tilde{\gamma}^N \gamma^M)^a{}_b\,.
 \eea

The action of the theory can be derived as a sum of actions for $6D$
vector multiplet and hypermultiplet with specific scalar and Yukawa
interactions and reads\footnote{Some comments about derivation of
this action are given at the end of this section.}
 \bea
 S_{\rm SYM}^{(1,0)} &=&\f{1}{2 {\rm f}^2}\tr\int d^6 x \Big(-F_{MN}F^{MN}
 + i\lambda^{ia}(\gamma^M)_{ab}\nabla_{M}\lambda_{i}^{b}\Big) \nn \\
 && +\f{1}{2 {\rm f}^2}\int d^6 x \Big( -\vp^{\cA i}\,\nabla^2\vp_{\cA i}
 + i \psi^{\cA}_{a}(\tilde{\gamma}^M)^{ab}\nabla_{M}\psi_{\cA b}
 - \f{1}4(\varphi^{\cA i}\varphi_{\cA}^j)^2  - 2\psi^{\cA}_{a}\lambda^{ia}\vp_{{\cA}i} \Big),
 \label{S0}
 \eea
where the hypermultiplet fields are taken in some representation of
the gauge group and $\nabla_M$ is a covariant derivative
$\nabla_M=\partial_M-i A_{M}$. The coupling constant ${\rm f}$ has a
dimension of inverse mass, $[{\rm f}]=-1$. The action \eq{S0} is
invariant under the gauge transformation
 \bea
 \d_{\Lambda} A_M = \nb_M \Lambda\,, &\quad&  \d_{\Lambda} \vp^{\cA}_i = i\Lambda\vp^{\cA}_i\,, \\
 \d_{\Lambda} \lambda^{a}_i = i[\Lambda,\lambda^{a}_i]\,,
 &\quad& \d_{\Lambda} \psi^{\cA}_{a} = i\Lambda\psi^{\cA}_{a}\,,
 \label{gtr}
 \eea
with the gauge transformation parameter $\Lambda = \Lambda(x)$ which
takes value in the Lie algebra of gauge group of the theory in the
vector multiplet and hypermultiplet representations respectively.

The action \eq{S0} possesses $\cN=(1,0)$ supersymmetry. It relates
the spinor field $\psi^{\cA}_{a}$ with the complex scalar
$\vp^{\cA}_i$ and the spinor field $\lambda^{a}_i$ with the gauge
vector field $A_M$ and scalar one $\vp^{\cA}_i$. Explicitly we have
\bea && \delta \vp_{\cA i}=-i\epsilon^{a}_{i}\psi_{\cA a}, \qquad
\qquad
\delta \psi_{\cA a}=\epsilon^{ib}(\gamma^M)_{ba}\nabla_{M}\vp_{\cA i}, \nn \\
&& \delta
A_{M}=\tfrac{i}{2}\epsilon^{ia}(\gamma_M)_{ab}\lambda_{i}^{b},
\qquad \delta
\lambda^{ia}=-\tfrac{1}{2}F^{MN}(\sigma_{MN})^{a}{}_{b}\epsilon^{bi}
+\tfrac{i}{2}\epsilon^{aj}\vp^{\cA i}\vp_{\cA j}, \lb{del4}
\eea
where $\epsilon^{a}_{i}$ is a left-handed parameter of $\cN=(1,0)$
supersymmetry transformation.

If the hypermultiplet component fields $\vp^{\cA i}$ and $ \psi_{\cA
a}$ align in the  adjoint representation of gauge group, the action
\eq{S0} possesses an additional implicite $\cN=(0,1)$ supersymmetry
and describes the six-dimensional $\cN=(1,1)$ SYM theory
 \bea
 S^{(1,1)}_{\rm SYM}=\f{1}{2 {\rm f}^2}\tr\int d^6 x \Big(-F_{MN}F^{MN}
 + i\lambda^{ia}(\gamma^M)_{ab}\nabla_{M}\lambda_{i}^{b}
 - \vp^{\cA i}\,\nabla^2\vp_{\cA i}+\nn \\
 + i \psi^{\cA}_{a}(\tilde{\gamma}^M)^{ab}\nabla_{M}\psi_{\cA b}
 - \f{1}4[\varphi^{\cA i},\varphi_{\cA}^j]^2  - 2\psi^{\cA}_{a}[\lambda^{ia},\vp_{{\cA}i}] \Big).
 \label{S11}
 \eea
Indeed the action \eq{S11} is invariant under both $\cN=(1,0)$
supersymmetry transformations
 \bea
 && \delta \vp_{\cA
i}=-i\epsilon^{a}_{i}\psi_{\cA a}, \qquad \qquad
\delta \psi_{\cA a}=\epsilon^{ib}(\gamma^M)_{ba}\nabla_{M}\vp_{\cA i}, \nn \\
&& \delta
A_{M}=\tfrac{i}{2}\epsilon^{ia}(\gamma_M)_{ab}\lambda_{i}^{b},
\qquad \delta
\lambda^{ia}=-\tfrac{1}{2}F^{MN}(\sigma_{MN})^{a}{}_{b}\epsilon^{bi}
+\tfrac{i}{2}\epsilon^{aj}[\vp^{\cA i},\vp_{\cA j}], \lb{del5} \eea
and $\cN=(0,1)$ ones \bea && \delta_0 A_{M} =
\tfrac{i}{2}\epsilon^{\cA}_a (\tilde{\gamma}_{M})^{ab}\psi_{\cA
b}\,, \qquad \
\delta_0 \vp_{Ai} =-i\epsilon_{Aa} \lambda^{a}_{i}, \nn \\
&& \delta_0 \lambda^{ia} =
\epsilon^{\cA}_{b}(\tilde{\gamma}^{M})^{ba}\nabla_{M}\vp^{i}_{\cA},
\qquad \delta_0 \psi_{\cA a}
=-\tfrac{1}{2}\epsilon_{Ab}(\sigma^{MN})^b{}_a F_{MN}
+\tfrac{i}{2}\epsilon_{\cB a}[\vp^{\cB i},\vp_{\cA i}], \label{del5}
 \eea
mixing the spinor field $\lambda^{ia}$ and the scalar $\vp_{\cA i}$
one and etc. with corresponding right-handed spinor parameter
$\epsilon_{\cA a}$.

The action \eq{S11} of the $\cN=(1,1)$ SYM theory was obtained at
first by dimensional reduction of the corresponding ten-dimensional
SYM theory (see e.g., \cite{MS1},\cite{MS2}). As to the action for
$\cN=(1,0)$ vector multiplet theory interacting with
hypermultiplets, it was known only in superfield form \cite{BIS} and
its complete component form was unknown. It is evident that the
component form of such an action can be useful for various aims. The
action \eq{S0} fills this gap. Let us briefly comment on the
derivation of this action. We follow to Noether procedure beginning
with the free actions for vector multiplet and hypermultiplet and
assuming invariance under the linearized supersymmetry
transformations. Then we include the appropriate interactions and
modify the supersymmetry transformations. As a result, we arrive at
the action \eq{S0} and transformations (\ref{del4}). The action of
$\cN=(1,1)$ theory (\ref{S11}) is obtained from \eq{S0} if to take
the hypermultiplet in the adjoint representation. Then we construct
the transformations (\ref{del5}) and explicitly check that the
action (\ref{S11}) is invariant under these transformations. As far
as we know, the component actions \eq{S0} and \eq{S11} for the
$\cN=(1,0)$ and $\cN=(1,1)$ SYM theories with corresponding
supersymmetry transformation \eq{del4}, \eq{del5} were not obtained
earlier in the framework of component formulation.

\section{Background field method and  one-loop divergences}

We are going to study the effective action in the theory with a
classical action \eq{S0}. To preserve the manifest gauge invariance
we will use the background field method (see e.g., \cite{Weinberg}, \cite{sred}). First of all we split the
initial gauge field $A_M$ and scalar field $\vp_{\cA i}$ to
classical {\it background} fields $\mathbf{A}_{M},
\mathbf{\Phi}_{\cA i}$ and {\it quantum} ones $a_{M}, \vp_{\cA i},
\lambda^{a}_i, \psi_{\cA a} $
\bea
&& A_M \rightarrow {\rm f} a_M + \mathbf{A}_M, \qquad \vp_{\cA i} \rightarrow {\rm f}\vp_{\cA i}
+ \mathbf{\Phi}_{\cA i}, \nn \\
&&\,\,\,\, \lambda^{a}_i \rightarrow  {\rm f} \lambda^{a}_i,\qquad
\qquad \quad \psi_{\cA a} \rightarrow {\rm f}\psi_{\cA a}.
\label{bgr1} \eea We are going to study the bosonic sector of
effective action in the model \eq{S0}. Therefore we introduce the
background field only for $A_M$ and $\vp_{\cA i}$ and keep the
spinor fields $\lambda^{ai}$ and $\psi_{\cA a}$ as a quantum ones.

Following Fadeev-Popov method we choose the gauge fixing action in
the standard way (see e.g., \cite{Weinberg}, \cite{sred})
 \bea
 S_{\rm gf} = - \tr \int
d^6 x (\boldsymbol{\nabla}^M a_M)^2\,. \label{Sgf}
 \eea
Here  $\boldsymbol{\nabla}_M=\partial_{M}-i\mathbf{A}_{M}$ are the
background dependent covariant derivative. The corresponding
Fadeev-Popov ghosts $\bar c$ and $c$ action is
 \bea
 S_{\rm gh} =- \tr \int d^6x\,\, \bar c\,  \boldsymbol{\nabla}^M \Big(\partial_M - i (\mathbf{A} + a)_M\Big)c\,.
 \label{Sgh}
 \eea

The total quantum action $S_{\rm quant}$ constructs as sum of the
classical action \eq{S0} with shifted field variables \eq{bgr1} and
the actions \eq{Sgf} and \eq{Sgh}. According to the background field
method one has to introduce the corresponding background and quantum
gauge transformations for both quantum fields and classical
background ones. These transformations are constructed on the base
of the initial gauge transformation \eq{gtr} and splitting \eq{bgr1}
(see for details, e.g., \cite{Weinberg}, \cite{sred})). The
background field method provides the procedure of constructing the
effective action $\Gamma[{\bf A}, {\bf \Phi}]$ for background fields
${\bf A}_M$ and ${\bf \Phi}_{\cA i}$ which is invariant under the
classical gauge transformations.

\subsection{One-loop divergences in the $\cN =(1,0)$ SYM theory}

Let we proceed to the study of the one-loop divergences in the
$\cN=(1,0)$ SYM theory, where the hypermultiplet transforms under
the arbitrary representation $R$ of the gauge group. We consider the
logarithmic divergences in a sector of gauge field ${\bf A}_M$ and
switch off the background scalar field ${\bf \Phi}_{\cA i}=0$. We
assume the background field ${\bf A}_M$ is completely off-shell. We
choose the gauge group to be compact Lie one and use the Hermitian
basis for generators
 \bea
 [T^{\rm I},T^{\rm J}]=i f^{\rm IJK} T^{\rm K}\,, \qquad \tr(T^{\rm I} T^{\rm J}) = {\rm T_R}\d^{\rm IJ}, \qquad
 \tr(T^{\rm I} T^{\rm J}T^{\rm K}) = \tfrac12 {\rm T_R} f^{\rm IJK} + \tfrac12 {\rm A_R} d^{\rm IJK},
  \eea
where $f^{\rm IJK}$ is a totally antisymmetric structure constants,
$d^{\rm IJK}$ is  a totally symmetric tensor and ${\rm A_R}$ is the
anomaly coefficient of the representation $R$ \cite{sred}. The
generators of the fundamental representation $T_f^{\rm I} \equiv
t^{\rm I}$ are normalized in the standard way $\tr(t^{\rm I} t^{\rm
J}) = \f12 \delta^{\rm IJ}$. In this case the one-loop contribution
to effective action is
 \bea
 \Gamma^{(1)}_{(1,0)}[{\bf A}] &=& \frac{i}{2}\Tr_{\rm Adj}\ln \Big(- \eta_{MN} (\boldsymbol{\nabla}^2)^{\rm IJ}-2f^{\rm IKJ}
 {\bf F}^{\rm K}_{MN}\Big)  -\frac{i}{4}\Tr_{\rm Adj}\ln \Big(   i \d_i{}^j (\gamma^M)_{ab} \boldsymbol{\nabla}_M \Big)^2 \nn \\
 && +  \frac{i}{2}\Tr_{\rm R}\ln \Big( -\d_i{}^j\d_\cA{}^\cB \boldsymbol{\nabla}^2 \Big) -\frac{i}{4}\Tr_{\rm R}\ln \Big( i \d_\cA{}^\cB (\tilde\gamma^M)^{ab} \boldsymbol{\nabla}_M\Big)^2
\nn \\
&& -i\Tr_{\rm Adj}\ln \Big(-\boldsymbol{\nabla}^2\Big),
 \label{Gamma2}
 \eea
where ${\bf F}^{\rm K}_{MN}$ is a background vector field strength
and we have denoted $\boldsymbol{\nabla}^2 = \boldsymbol{\nabla}^M
\boldsymbol{\nabla}_M$. The first two contributions in \eq{Gamma2}
come from vector multiplet. The next two terms in the second line of
\eq{Gamma2} are the contributions from hypermultiplet which
transforms under some irreducible representation $R$ of the gauge
group $G$. The last term in \eq{Gamma2} is a contribution from the
ghosts fields.

We use proper time method to study one-loop effective action. For
differential operators $\Delta$ associated with action \eq{Gamma2} we
define
 \bea
 \f{i}2\Tr \ln \Delta = -\f{i}2\mu^{2\omega} \tr \int d^6 x \int_0^\infty \f{d (is)}{(is)^{1-\omega}}
 e^{is \Delta} \delta^6(x-x')\Big|_{x=x'},
 \label{proper}
 \eea
where $\mu$ is an arbitrary parameter of mass dimension and trace is
taken over all gauge group, spinor and Minkowski space-time indexes.
Also we introduce  the parameter of dimension regularization
$\omega$. Logarithmic divergent contributions in \eq{Gamma2} arise
as a pole $\frac{1}{\omega}$ in the limit $\omega \to 0$. To
calculate such terms we use \eq{proper} and expand the exponent of
each operator up to sixth order over covariant derivative
$\boldsymbol{\nabla}_M$. After that we pass to momentum
representation for delta-function and calculate the integral over
momentum and proper time $s$. The result for each contribution in
\eq{Gamma2} is listed below
 \bea
 \frac{i}{2}\Tr\ln \Big(-\eta_{MN} (\boldsymbol{\nabla}^2)^{\rm IJ}-2f^{\rm IKJ} {\bf F}^{\rm K}_{MN}\Big)\Big|_{\rm div}
 &=& -\frac{C_2}{(4\pi)^3 \omega}\Big(\frac{3}{90}F_3 + \frac{17}{60}I_3\Big),
 \label{div1} \\
 \frac{i}{2}\Tr\ln \Big( -\d_i{}^j\d_\cA{}^\cB \boldsymbol{\nabla}^2\Big)\Big|_{\rm div}
 &=& - \frac{\rm T_R}{(4\pi)^3 \omega} \Big(\frac{2 }{90}F_3-\frac{ 2 }{60}I_3\Big)
 - \frac{\rm A_R}{(4\pi)^3 \omega} \frac{2}{90}\bar F_3, \label{3.9}\\
  -\frac{i}{4}\Tr\ln \Big(i \d_i{}^j (\gamma^M)_{ab} (\boldsymbol{\nabla}_M\Big)^2\Big|_{\rm div}
  &=& \frac{C_2}{(4\pi)^3 \omega} \Big(\frac{2}{90}F_3+\frac{2}{15}I_3\Big),\\
 -\frac{i}{4}\Tr\ln \Big(i \d_\cA{}^\cB  (\tilde\gamma^M)^{ab} (\boldsymbol{\nabla}_M)^{\rm IJ}\Big)^2\Big|_{\rm div}
  &=& \frac{\rm T_R}{(4\pi)^3 \omega} \Big(\frac{2}{90}F_3+\frac{2}{15}I_3\Big)
  +\frac{\rm A_R}{(4\pi)^3 \omega} \frac{2}{90}\bar F_3, \label{3.11}\\
 -i\Tr\ln\Big(-(\boldsymbol{\nabla}^2)^{\rm IJ}\Big)\Big|_{\rm div}
  &=& \frac{C_2}{(4\pi)^3 \omega}\, \Big(\frac{1}{90}F_3-\f{1}{60}I_3\Big), \label{div2}
 \eea
where $C_2$ is a second Casimir operator of adjoint representation
of gauge group and we have introduced the quantities
 \bea
 && F_3 = \int d^6x f^{\rm IJK}\big({\bf F}_M{}^N\big)^{\rm I}
 \big({\bf F}_N{}^L\big)^{\rm J}\big({\bf F}_L{}^M\big)^{\rm K}, \qquad
 I_3 = \int d^6x \big(\boldsymbol{\nabla}_M {\bf F}^{M L} \big)^{\rm I}
 \big(\boldsymbol{\nabla}^N {\bf F}_{N L}\big)^{\rm I}\,, \nn \\
 && \bar F_3 = \int d^6x d^{\rm IJK}\big({\bf F}_M{}^N\big)
 ^{\rm I}\big({\bf F}_N{}^L\big)^{\rm J}\big({\bf F}_L{}^M\big)^{\rm K}.
 \label{F3}
 \eea
Summing up all divergent contributions  \eq{div1} - \eq{div2} to the
one-loop effective action  \eq{Gamma2} one can see that all
contributions with $F_3$ and $\bar F_3$ cancel each other and the
divergent part of effective action is proportional to the equation
of motion for background vector field
 \bea
 \Gamma^{(1)}_{\rm div}[{\bf A}] = \f{{\rm T_R}-C_2}{3 (4\pi)^3 \, \omega}
 \tr \int d^6x \boldsymbol{\nabla}_M {\bf F}^{M L} \boldsymbol{\nabla}^N {\bf F}_{N L}. \label{Gamma2_1}
 \eea
The absence of divergent contributions with $F_3$ and $\bar F_3$ in
the $\cN=(1,0)$ SYM theory without hypermultiplet was mentioned
earlier \cite{HRT}.  Here we demonstrate absence of these terms by
explicit calculation of the divergences in theory including the
hypermultiplet in arbitrary representation of the gauge group.  The
divergent contribution from quantum hypermultiplet \eq{3.9} and
\eq{3.11} containing $F_3$ and $\bar F_3$ exactly cancel each other.
Also we note that this result is consistent with the superfield
calculations \cite{BIMS2,BIMS3}. The divergent part of one-loop
superfield effective action in gauge multiplet sector includes the
square of classical superfield equations of motion and the
contributions with $(F_{MN})^3$ in the components are ruled out.

In the $\cN=(1,1)$ SYM theory the hypermultiplet transforms under
adjoin representation of gauge group. In this case ${\rm T_R} = C_2$
and ${\rm A_R} = 0$ and we obtain the cancelation of ultraviolet
divergences in \eq{Gamma2_1} off-shell \cite{Kazakov,BIMS2,BIMS3}.
However result is valid only for Fermi-Feynman gauge and in case of
general off-shell background it can be gauge-dependent
\cite{Kazakov,BIMS5}. It means that in general the one-loop
divergences of the theory under consideration apparently are absent
only on-shell.

\subsection{One-loop effective action in $\cN=(1,1)$ SYM theory}

In this subsection we consider the finite one-loop contribution to the
effective action for the $\cN=(1,1)$ SYM theory. Unlike the previous section,
the background scalar field is also taken into account.

One-loop
contribution $\Gamma^{(1)}[{\bf A}, {\bf \Phi}]$ is determined by
the quadratic over quantum fields part of quantum action
 \bea
 S^{(1,1)}_2[{\bf A},{\bf \Phi}] &=& \f12\tr \int d^6 x \Big(
   2 a^M \boldsymbol{\nabla}^2 a_M
   + 4i a^M[\mathbf{F}_{MN},a^N]
   -[a^M,\mathbf{\Phi}^{\cA i}]^2
   - 2i [a^M, {\bf \Phi}^{\cA i}]\boldsymbol{\nabla}_M \vp_{\cA i}
   \nn \\
&&
 -\vp^{\cA i}\boldsymbol{\nabla}^2 \vp_{\cA i}
 - [\vp^{\cA i},{\bf \Phi}_{\cA}^j]^2 -\f{1}2[\vp^{\cA i},\vp_{\cA}^j]
 [{\bf \Phi}^{\cB}_i,{\bf \Phi}_{\cB j}]
  -2i[a^M, \vp^{\cA i}]  \boldsymbol{\nabla}_M {\bf \Phi}_{\cA i}   \nn \\
&& + i\lambda^{i a} (\gamma^M)_{ab}\boldsymbol{\nabla}_M
\lambda^{a}_i
 + i\psi^{\cA}_a(\tilde{\gamma}^M)^{ab} \boldsymbol{\nabla}_M \psi_{\cA b}
 - 2\psi^\cA_a[\lambda^{ia},\mathbf{\Phi}_{\cA i}] - 2 \bar c \boldsymbol{\nabla}^2 c \Big).
    \label{S2}
 \eea
We  note that the quadratic action $\eq{S2}$ contains terms
mixing quantum vector $a_M$ and scalar $\vp_{\cA i}$ fields as well as the
quantum spinor
$\lambda^{ia}$ and $\psi^\cA_a$ fields. In order to exclude the mixed $a_M$
and $\vp_{\cA i}$ terms we introduce the gauge fixing action in
form of the $R_{\xi}$ gauge (see e.g., \cite{Weinberg}, \cite{sred})
 \bea
 S_{\rm gf} = - \tr \int d^6x (\boldsymbol{\nabla}_M a^M - \tfrac{i}2 [\mathbf{\Phi}^{\cA i}, \varphi_{\cA i}])^2\,.
 \label{Sgf2}
 \eea
Using the gauge fixing action \eq{Sgf2} instead of \eq{Sgf} leads to
cancelation of mixed $a_M$ and $\vp_{\cA i}$ terms in quadratic
action \eq{S2}. However in that case the additional contribution
arises for the ghosts fields.

Integrating over quantum fields in the functional integral we
produce the one-loop contribution to the effective action
 \bea
 \Gamma^{(1)}_{(1,1)}[{\bf A}, {\bf \Phi}]
 =\frac{i}{2}\Tr\ln \cB-\frac{i}{4}\Tr\ln\mathbf \cF^2
 -i\Tr\ln{\cal G},
 \label{Gamma1}
 \eea
where ${\cal G} = -(\boldsymbol{\nabla}^2)^{\rm IJ} + \tfrac12
f^{\rm IKP}f^{\rm JLP} ({\bf \Phi}^{\cA i})^{\rm K}({\bf \Phi}_{\cA
i})^{\rm L}$. The matrices $\cB$ and $\cF$ depend on the background
fields $\boldsymbol{A}_M$ and $\boldsymbol{\Phi}_{\cA i}$. To reveal
the explicit structure of the matrices  $\cB$ and $\cF$ it is useful
to write down the the gauge group indices. All
fields we assumed in adjoint representation of gauge group.  We
represent the matrices $\cB$ and $\cF$ in a block form \bea
\cB=\begin{pmatrix}
\cB_1 & 0 \\
0 & \cB_2
\end{pmatrix}, \qquad
\cF=\begin{pmatrix}
\cF_1 & \cF_2 \\
\cF_3 & \cF_4
\end{pmatrix},
\eea where for the $\cB$ matrix elements we have introduced the
notations
 \bea
 (\cB_1^{\rm IJ})_{MN} &=& -\eta_{MN}
 (\boldsymbol{\nabla}^2)^{\rm IJ}-2f^{\rm IKJ} {\bf F}^{\rm K}_{MN}
 +\tfrac12\eta_{MN} f^{\rm IKP}f^{\rm JLP}
  ({\bf \Phi}^{\cA i})^{\rm K}({\bf \Phi}_{\cA i})^{\rm L}, \\
  (\cB_2^{\rm IJ})_{\cA i}{}^{\cB j} &=& - \tfrac12\d_i{}^j\d_\cA{}^\cB
 (\boldsymbol{\nabla}^2)^{\rm IJ}
-\tfrac{1}2 \d_i{}^j f^{\rm IKP}f^{\rm JLP}({\bf \Phi}^k_\cA)^{\rm
K}
({\bf \Phi}^{\cB}_k)^{\rm L} \nn \\
&& -\tfrac{1}4 \d_\cA{}^\cB f^{\rm IJP}f^{\rm PKL}({\bf \Phi}^{\cal
C}_i)^{\rm K} ({\bf \Phi}_{\cal C}^j)^{\rm L}\,,
 \eea
and for the $\cF$ elements  we have the following expressions
 \bea
 (\cF_1^{\rm IJ})_{ab}{}_i^j &=& \tfrac{i}2 \d_i{}^j (\gamma^M)_{ab}
 (\boldsymbol{\nabla}_M)^{\rm IJ}, \\
 (\cF_2^{\rm IJ})_a^b{}^\cB_i &=& -\tfrac{i}{2}\d_a{}^b f^{\rm IKJ}
 ({\bf \Phi}^{\cB}_i)^{\rm K},\\
 (\cF_3^{\rm IJ})^a_b{}_\cA^j &=& -\tfrac{i}{2}\d^a{}_b f^{\rm IKJ}
 ({\bf \Phi}_{\cA}^j)^{\rm K},\\
 (\cF_4^{\rm IJ})^{ab}{}_\cA^\cB &=& \tfrac{i}2 \d_\cA{}^\cB
 (\tilde\gamma^M)^{ab} (\boldsymbol{\nabla}_M)^{\rm IJ}.
 \eea
Equations of motion for background fields has the following form
 \bea
 \boldsymbol{\nabla}^M F_{MN} + \tfrac{i}2[{\bf \Phi}^{\cA i},
 \boldsymbol{\nabla}_N {\bf \Phi}_{\cA i}] &=& 0, \nn \\
 \boldsymbol{\nabla}^2 {\bf \Phi}^{\cA i} -\tfrac{ 1}{2} {\bf \Phi}^{\cA}_j
 [{\bf \Phi}^{\cB i}, {\bf \Phi}^{j}_\cB] &=& 0. \label{EQM1}
 \eea

The one-loop divergences in the theory under consideration were
studied in many details both in component and superfield approaches
\cite{MS1,MS2,FT,HS,HS1,BHS,BHS1,Kazakov,BIMS2,BIMS3,HRT}. The
absence of  one-loop divergences  in the six-dimensional $\cN=(1,1)$
SYM theory on-shell was known \cite{MS1,MS2,FT} and, as we discussed
in the previous section, it is immediately following from the
\eq{Gamma2_1}.

\section{Leading low-energy contribution to one-loop
effective action of $\cN=(1,1)$ SYM theory}

Next we proceed to the evaluation of leading low-energy finite
contribution to effective action \eq{Gamma1}. In what follows we
assume the gauge group of the theory to be $SU(2)$. We choose
standard Hermitian basis for generators $\tau^{\rm I} =\f12
\sigma^{\rm I}$ using Pauli matrices
 \bea
 \sigma^{1} =\begin{pmatrix}
0& 1 \\
1& 0
\end{pmatrix}, \quad
 \sigma^{2}  =\begin{pmatrix}
0& -i \\
i& 0
\end{pmatrix}, \quad
 \sigma^{3}  =\begin{pmatrix}
1& 0\\
0& -1
\end{pmatrix}. \quad
 \eea
Generators $\tau^{\rm I}, \, {\rm I}=1,2,3,$ satisfy the $su(2)$
algebra, $[\tau^{\rm I}, \tau^{\rm J}] = i \epsilon ^{\rm IJK}
\tau^{\rm K}$, with totally antisymmetric symbol $\epsilon ^{\rm
IJK}$ and they are normalized as, $\tr (\tau^{\rm I} \tau^{\rm J}) =
\f12 \d^{\rm IJ}$.

We also suppose that background fields ${\bf A}_M$ and ${\bf
\Phi}_{\cA i}$ align into Cartan subalgebra of $su(2)$ generated by
$\tau^3$ matrix
 \bea
 {\bf A}_M = A_M \tau^3, \qquad {\bf\Phi}_{\cA i} = \Phi_{\cA i} \tau^3.
 \label{bg1}
 \eea
We have denoted by $A_M$ and $\Phi_{\cA i}$ the third components of
background fields ${\bf A}_M$ and ${\bf \Phi}_{\cA i}$. Our choice
of background corresponds to the case when gauge symmetry group
$SU(2)$ is broken to $U(1)$. Equations of motion for background
fields \eq{EQM1} in accordance with restriction \eq{bg1} take a free
form
 \bea
 \partial^M F_{MN}=0, \qquad \partial^2 \Phi_{\cA i} = 0,
 \label{EQM2}
 \eea
where $F_{MN} = \partial_M A_N - \partial_N A_M$ is an Abelian field
strength corresponding to ${\bf F}_{MN} = F_{MN}\tau^3$. Also we
assume that background fields are slowly varying in space-time
 \bea
 \partial_M F_{NL} = 0, \qquad \partial_M \Phi_{\cA i} = 0.
 \label{bg2}
 \eea
The last condition means that we systematically neglect all terms
with derivatives of the background field strength $F_{MN}$ and the
scalar one $\Phi_{\cA i}$.

Gauge transformations for background fields in case of \eq{bg1} are
simplified and take the form
 \bea
\d_\Lambda A_M = \partial_M \Lambda, \qquad \d_\Lambda \Phi_{\cA i}
= 0, \label{BGgauge2}
 \eea
where $\Lambda = \Lambda(x)$ is an Abelian gauge parameter. In
Abelian case the gauge field strength $F_{MN}$ is known to be
invariant under gauge transformation \eq{BGgauge2}, $\d_\Lambda
F_{MN}=0$. Hence the effective action as a polynomial function of
$F_{MN}$ is a gauge invariant under construction.

\subsection{Leading low-energy contribution}

First of all let we rewrite the matrices $\cB$ and $\cF$ in
accordance with our choice of background fields \eq{bg1} and
\eq{bg2}. We consider non-vanishing background for scalar field
$\Phi_{\cA i}$, hence we have
  \bea
 \Gamma^{(1)}[A, \Phi]
 &=&\frac{i}{2}\Tr\ln \Big( -\eta_{MN}(\nb^2)^{\rm IJ}
 +\tfrac12\eta_{MN} \d^{\rm IJ} \Phi^2
 - 2\epsilon^{\rm I3J} F_{MN} \Big)\nn \\
 && + \frac{i}{2}\Tr\ln \Big(-\d_i{}^j\d_\cA{}^\cB (\nabla^2)^{\rm IJ}
+\tfrac12\d_i{}^j \d_\cA{}^\cB \d^{\rm IJ}\Phi^2\Big)  \nn \\
&&-\frac{i}{4}\Tr\ln \Big(-\d_i{}^j (\nb^2)^{\rm
IJ}-\tfrac{i}{2}\d_i{}^j\epsilon^{\rm I3J}\sigma^{MN}F_{MN}
+\tfrac{1}{2}\d_i{}^j\d^{\rm IJ} \Phi^2\Big) \nn \\
&&-\frac{i}{4}\Tr\ln \Big(-\d_\cA{}^\cB(\nb^2)^{\rm
IJ}-\tfrac{i}{2}\d_\cA{}^\cB\epsilon^{\rm I3J}\sigma^{MN}F_{MN}
+ \tfrac{1}{2} \d_\cA{}^\cB\d^{\rm IJ} \Phi^2 \Big) \nn \\
 && -i\Tr\ln\Big(-(\nb^2)^{\rm IJ}+\tfrac12\d^{\rm IJ} \Phi^2\Big),
 \label{Gamma3}
 \eea
where the operator $(\nb^2)^{\rm IJ}$ is constructed using the
Abelian  covariant derivative $(\nb_M)^{\rm IJ} = \d^{\rm
IJ}\partial_M + \epsilon^{\rm I3J} A_M$ and we introduced $\Phi^2 =
\Phi^{\cA i} \Phi_{\cA i}$. In order to obtain the leading
low-energy contribution to one-loop effective action \eq{Gamma3} one
should follow the same method as in study of divergences in previous
section. We use the proper time technique $\eq{proper}$ to study the
one-loop effective action \eq{Gamma3}. We are interested in the
leading low-energy contributions to one-loop effective action which
have not higher than fourth power of gauge field strength $F_{MN}$.
Thus we have to expand the exponent in the $\eq{proper}$ and collect
all terms up to the eighth power of covariant derivative or the
forth power of background gauge field strength. In order to
determine the structure of the leading contribution to effective
action we consider the contribution of forth power over background
gauge field strength from the determinant of spinor field
$\lambda^{i a}$
 \bea
-\frac{i}{4}\Tr\ln \Delta_{1/2}  = \frac{i}{4}\mu^{2\omega}\tr \int
d^6 x \int_0^\infty \f{d (is)}{(is)^{1-\omega}} e^{is \Delta_{1/2}}
\delta^6(x-x')\Big|_{x=x'},
 \eea
where $\Delta_{1/2} = -\d_i{}^j (\nb^2)^{\rm
IJ}-\tfrac{i}{2}\d_i{}^j\epsilon^{\rm I3J}\sigma^{MN}F_{MN}
+\tfrac{1}{2}\d_i{}^j\d^{\rm IJ} \Phi^2$. We assume the constant
background scalar field, thus the covariant d'Alembertian in the
exponent is comute with the $\Phi^2$ term
 \bea
-\frac{i}{4} \Tr\ln \Delta_{1/2}  &=& \frac{i}{4}\tr \int d^6 x \int_0^\infty \f{d (is)}{(is)} e^{\tfrac{i}{2}s \Phi^2}e^{-is\nb^2 -\tfrac{i}{2}s \sigma_{MN} F^{MN}} \delta^6(x-x')\Big|_{x=x'} \nn \\
&=& \f{i}{24} \int d^6 x \, \tr \big(\tfrac12  \sigma_{MN} F^{MN}
\big)^4 \int_0^\infty d (is)\,(is)^3 e^{\tfrac{i}{2}s \Phi^2}
e^{-is\nb^2}\delta^6(x-x')\Big|_{x=x'}+...,\nn
 \eea
where the trace is taken over spinor indexes and dots mean over
contributions of the forth power of $F_{MN}$. After that we pass to
momentum space for delta-function and calculate the integral over
proper-time. We have
 \bea
-\frac{i}{4} \Tr\ln \Delta_{1/2} \sim \frac{1}{(4\pi)^3}
 \int d^6 x\frac{1}{\Phi^2}\Big(4F^4-3F^2 F^2\Big),
 \eea
where we  denote  $F^4 = F_{M}{}^N F_N{}^P F_P{}^Q F_Q{}^M$ and $F^2
= F_{M}{}^N F_N{}^M$. The same strategy we apply to the remaining
terms in \eq{Gamma3}.  We omit tedious details of calculations and
the result is
 \bea
 \Gamma^{(1)}_{\rm lead}[A, \Phi]= \frac{1}{(4\pi)^3}\frac{1}{360}
 \int d^6 x\frac{1}{\Phi^2}\Big(4F^4-3F^2 F^2\Big).
 \label{lead}
 \eea
Recently \cite{BIM} the leading low-energy contribution to the
one-loop effective action in $\cN=(1,1)$ SYM theory was analyzed
using superfield approach. The effective action \eq{lead} coincides
with bosonic sector the superfield effective action obtained in
\cite{BIM}. The component calculation, carried out here, can be
considered as an independent test of the superfield result.

\subsection{Effective potential}
In order to evaluate the one-loop contribution to the effective
action for scalar field $\Phi_{\cA i}$ we switch off the vector
background field $A_M = 0$ in the effective action  \eq{Gamma3}.
Then we obtain
 \bea
 V^{(1)}[\Phi]
 &=&\frac{i}{2}\Tr\ln \Big( -\eta_{MN}\d^{\rm IJ} \partial^2
 +\tfrac12\eta_{MN} \d^{\rm IJ} \Phi^2 \Big)\nn \\
 && + \frac{i}{2}\Tr\ln \Big(-\d_i{}^j\d_\cA{}^\cB \d^{\rm IJ} \partial^2
+\tfrac12\d_i{}^j \d_\cA{}^\cB \d^{\rm IJ}\Phi^2\Big)  \nn \\
&&-\frac{i}{4}\Tr\ln \Big(-\d_i{}^j\d^{\rm IJ} \d_a{}^b\partial^2
+\tfrac12\d_i{}^j\d^{\rm IJ}\d_a{}^b \Phi^2\Big) \nn \\
&&-\frac{i}{4}\Tr\ln \Big(-\d_\cA{}^\cB\d^{\rm IJ}\d^a{}_b
\partial^2 + \tfrac12 \d_\cA{}^\cB\d^{\rm IJ} \d^a{}_b\Phi^2 \Big) \nn \\
&& -i\Tr\ln\Big(-\delta^{\rm IJ}\partial^2+\tfrac12\d^{\rm IJ}
\Phi^2\Big).
 \label{Gamma4}
 \eea
Note that indices of adjoin representation ${\rm I,J} = 1,2$ in the
expression \eq{Gamma4}.

The direct evaluation of the above functional determinants on the
base of proper-time technique leads to cancelation of all
contributions in effective potential \eq{Gamma2}
 \bea
  V^{(1)}[\Phi] =0\,.
 \eea
The absence of the one-loop effective potential for scalar fields is
in consistence with the $\cN=(1,1)$ supersymmetry. The same result
can be explained explicitly using $\cN=(1,0)$ harmonic superfield
consideration in the $\cN=(1,1)$ SYM theory \cite{BIM}. In terms of
superfields the  effective potential for background scalar
superfields corresponds to the contributions which depend only on
constant background hypermultiplet. But all such contributions are
forbidden by the on-shell hidden $\cN=(0,1)$ supersymmetry
\cite{BIM}. The absence of the one-loop contribution to the
effective potential for scalar field in $\cN=(1,1)$ SYM theory is
also dictated by the absence of the Coulomb branch in the theory
under consideration \cite{SW}. However, as far as we know it was
never confirmed before by the direct calculation.

\section{Summary}

In this paper we have studied the bosonic sector of the low-energy
effective action in the six-dimensional $\cN=(1,0)$ and $\cN=(1,1)$
SYM theories \eq{S0} and \eq{S11} formulated in terms of physical
components. First of all we have derived the component action of
$6D,\, \cN=(1,0)$ SYM theory and the corresponding supersymmetry
transformations. The one-loop effective action is considered on the
base the background field method with help of $R_{\xi}$-type gauge.
We provided the explicit calculation of the divergent contributions
to the one-loop effective action in $\cN=(1,0)$ SYM theory
interacting with hypermultiplets. We have demonstrated by direct
calculation of corresponding contributions to the one-loop effective
action that all $F^3$-type divergent contributions (\ref{F3}) cancel
each other. The result is in an agreement with the earlier component
calculations \cite{MS1,MS2,FT,HS,HS1,BHS,BHS1,Kazakov,HRT} without
hypermultiplet contributions and with the superfield analysis
\cite{BIMS2,BIMS3,BIMS4}. We also demonstrated that divergent
contributions in the $\cN=(1,1)$ theory cancel each other and the
theory is one-loop off-shell finite as expected.

Studying the finite contributions to the $\cN=(1,1)$ SYM theory we
have considered the gauge group $SU(2)$ and have assumed that the
background fields take the value in Cartan subalgebra of $su(2)$. To
construct the finite low-energy contribution to the effective action
of the theory we assume the non-zero values for both vector and
scalar background fields and using the $R_{\xi}$ gauge. In case of
slowly varying on-shell background fields we calculated the leading
low-energy contribution to the one-loop effective action. It is
determined by the contributions of the fourth power of the gauge
field strength $F_{MN}$. The obtaining result being in agreement
with the bosonic part of the leading contribution to the one-loop
harmonic superfield effective action \cite{BIM} and it can be
considered as an independent test of the superfield calculation. We
also demonstrate the absence of the one-loop contribution to the
effective potential for the background scalar field, which as we
know was not mentioned before by direct calculations.

As a further development of the approach under consideration we plan
to study the divergences in the fermionic sector and investigate the
two-loop counterterms in the theory \eq{S0}. Also it would be
interesting to study the finite low-energy contributions to the
effective action in high derivative SYM theory \cite{ISZ,CT}.

\subsection*{Acknowledgements}
The authors acknowledge a partial support from the RFBR grant,
project No 18-02-00153. Their research was also supported in parts
by Russian Ministry of Science and High Education, project No.
3.1386.2017.  The work of A.S.B. and B.S.M. was supported in part by
the Russian Federation President grant, the project MK-1649.2019.2.


\section{Introduction}

Modern data sets increasingly consist of noisy or incomplete information, which means that traditional ways of matching database records often fall short.
One approach to dealing with this in database systems is to provide \emph{similarity join} operators that find pairs of tuples satisfying a similarity predicate.
We refer to the book of Augsten and B{\"o}hlen~\cite{DBLP:series/synthesis/2013Augsten} for a survey of similarity joins in relational database systems, and to~\cite{conf/icdt/Pagh15} for an overview of theoretical results in the area.
Note that joins can be implemented using similarity search \emph{indexes} that allow searching a relation for tuples that satisfy a similarity predicate with a given query~$q$.
Thus we include works on similarity search indexes in discussion of previous work on similarity join.

In this paper we consider \emph{inner product similarity} predicates of the form $\langle x, y\rangle /geq \alpha$, where $x,y\in\mathbb{R}^{d}$ are real-valued vectors, i.e., the predicate is true for vectors whose inner product $\sum_{i=1}^d x_i y_i$ exceeds a user-specified threshold~$\alpha$.
This notion of similarity is important, for example, in neural network training and inference, (see~\cite{DBLP:conf/kdd/SpringS17}).
In that context, an inner product similarity join can be used for classifying a collection of vectors according to a neural network model.

Inner product similarity join is a special case of similarity join under Euclidean distance, implemented for example in the Apache Spark framework\footnote{\url{https://spark.apache.org/}}.
Conversely, it generalizes \emph{cosine similarity}, which has been studied for more than a decade (see, e.g.,~the influential papers~\cite{bayardo2007scaling, DBLP:conf/stoc/Charikar02} and more recent works such as~\cite{anastasiu2014l2ap,DBLP:conf/icassp/BaluFJ14,DBLP:conf/icde/ChristianiPS18,satuluri2012bayesian}). In recent years the general inner product similarity join problem has attracted increasing attention (see e.g.~\cite{ahle2016complexity,DBLP:conf/kdd/RamG12,DBLP:conf/nips/Shrivastava014,teflioudi2017exact,DBLP:conf/nips/YanLDCC18}).
Recently proposed practical inner product similarity join algorithms work by reducing the general problem to a number of instances with unit length vectors, which is equivalent to join under cosine similarity~\cite{DBLP:conf/nips/YanLDCC18}.

\medskip

{\bf Candidate generation approach.}
State-of-the-art algorithms computing similarity joins on high-dimensional vectors use a two-phase approach:
\begin{enumerate}
\item Generate a set of \emph{candidate pairs} $(x,y)$ that contains all pairs satisfying the predicate (keeping track of the corresponding tuples in the relations).
\item Iterate over the candidate pairs to \emph{check} which ones satisfy the predicate.
\end{enumerate}
Suppose for simplicity that both relations in the similarity join contain~$n$ tuples.
A na\"ive candidate generation phase would output all $n^2$ corresponding pairs of vectors.
For many data sets it is possible to reduce the number of candidate pairs significantly below $n^2$, but the check phase remains a bottleneck.
A direct implementation of the check phase would require full information about the vectors $(x,y)$, in practice $d$ floating point numbers per vector.
Though the inner product computation is trivial, for high-dimensional vectors the cost of transferring data from memory can be a bottleneck.

\medskip

{\bf Filtering candidate pairs using approximation.}
An approach to reducing communication is to \emph{approximate} inner products, which is enough to handle those candidate pairs that do not have inner product close to the threshold $\alpha$.
The exact inner product is computed only for the remaining pairs, often a small fraction of the set of all candidates.
We stress that globally, the join computation we consider is not approximate, but approximations are used to speed up parts of the algorithm.
(Note that under common assumptions in fine-grained complexity, the inner product similarity join problem is difficult in the worst case, even with approximation~\cite{DBLP:conf/focs/AbboudRW17,ahle2016complexity}.)

Such additional filtering of candidate pairs has been successfully used in ``Monte Carlo'' style randomized algorithms that allow the algorithm to sometimes fail to identify a pair satisfying the predicate, e.g.~\cite{satuluri2012bayesian,DBLP:conf/esa/0001CPV19}.
While the error in Monte Carlo algorithms can usually be made very small at a reasonable computation cost, such algorithms are not suitable in all settings. For example:
\begin{itemize}
\item Firm guarantees may be needed to comply with regulation, or to ensure a clear and consistent semantics of a system (such as a DBMS) in which the similarity estimation algorithm is part.
\item Guarantees on accuracy are shown under the assumption that the input data is independent of the random choices made by the algorithm. Technically this assumption may not hold if output from the algorithm can affect future inputs. Maybe more seriously, if vectors can be chosen adversarially based on (partial) knowledge of the randomness of the algorithm, for example obtained by timing attacks, the guarantees cease to hold (see e.g.~\cite{DBLP:conf/ccs/ClaytonPS19} for more discussion of adversarial settings).
\end{itemize}

In this paper we study what kind of approximation is possible without randomization, targeting settings where false negatives are not permitted, or where we cannot ensure that inputs are independent of any randomization used by the algorithm.

We seek to efficiently eliminate all candidate pairs that have inner product less than~$\beta$, for some $\beta$ smaller than the threshold $\alpha$, so that the number of remaining candidate pairs (for which an expensive inner product computation must be done) may be significantly reduced.
In order to not eliminate any candidate pair passing the threshold it is necessary and sufficient that the approximation is strong enough to distinguish the cases $\langle x, y\rangle\leq\beta$ and $\langle x, y\rangle\geq \alpha$.

\medskip

{\bf Similarity join memory bottlenecks.}
The complexity of similarity joins in the I/O model was studied in~\cite{DBLP:conf/esa/PaghPSS15}, which assumes that a block transfer moves $B$ vectors from or to external memory, and that internal memory can hold $M$ vectors.
Reducing the amount of data that needs to be transferred to evaluate a similarity predicate leads to a larger capacity of blocks as well as internal memory, in turn leading to a reduction in I/O complexity that is roughly proportional to the reduction in size.
The exact improvement is a bit more complicated because additional I/Os are needed to evaluate the exact inner products of pairs with similarity above $\beta$.
McCauley and Silvestri~\cite{mccauley2018adaptive} studied the related problem of similarity joins in MapReduce where considerations similar to the I/O model can be made.

\subsection{Our results}

Without loss of generality we can consider \emph{unit vectors}, since the general estimation problem can be reduced to this case by storing an (approximate) norm of each vector in space independent of the number of dimensions. Similarly, lower bounds shown for unit vectors imply lower bounds for arbitrary vector lengths by a scaling argument

We study the following version of the inner product estimation problem for unit vectors: Distinguish inner products smaller than $\beta$ from inner products larger than $\alpha$, for threshold parameters $\alpha$ and $\beta$.
This problem can of course be solved by estimating the inner product with additive error less than $\alpha - \beta$.
However, we will see that the number of bits needed is not a function of $\alpha - \beta$, and that guarantees can be improved when these parameters have values close to~1.

Let $x$ and $y$ be vectors from the $d$-dimensional Euclidean unit sphere $\S^{d-1}$.
When represented in a computer with limited precision floating or fixed-point numbers, the precision we can obtain when computing the inner product $\doot x y$ will of course depend on the precision of the representation of $x$ and $y$.
Suppose we round coordinates $x$ and $y$ to the nearest integer multiple of $\varepsilon / d$, for some parameter $\varepsilon > 0$, to produce ``uniformly quantized'' vectors $x'$ and $y'$.
Then it is easy to see that the difference between $\doot x y$ and $\doot{x'}{y'}$ is at most~$\varepsilon$.
The space required to store each coordinate $x'_i, y'_i \in [-1,+1]$ is $\lceil \log_2(2d/\varepsilon)\rceil$ bits, so we get $d\log_2(d/\varepsilon) + \BOx{d}$ bits in total using standard, uniform quantization.
 On the upper bound side we know that the number of bits per dimension can be made independent of~$d$.
 The following lemma appears to be folklore --- a proof can be found in~\cite[Theorem 4.1]{Alon2017optimal}.
\begin{lemma}\label{thm:main-upper}    For every $\varepsilon > 0$ there exists a mapping $\mathcal{E}: S^{d-1} \rightarrow \{0,1\}^\ell$, where $\ell = d\log_2(1/\varepsilon) + \BOx{d}$ such that $\doot x y$ can be estimated from $\enc{x}$ and $\enc{y}$ with additive error at most $\varepsilon$.
 \end{lemma}

 In this paper we ask if this space usage is optimal for the problem of distinguishing between two specific inner product values.
 Our methods will work through a decoding function that produces a unit vector from a bit representation (i.e., the approximation is a result of quantizing the input vectors).
 Specifically, we consider the following problem:

   \begin{definition}		 For positive integers $d$ and $\ell$, and $\alpha,\beta\in [0,1]$ with $\alpha>\beta$ the $(\alpha,\beta,d,\ell)$-{\sc InnerProduct} problem is to construct mappings $\mathcal{E}: \S^{d-1}\rightarrow \{0,1\}^{\ell}$ and $\mathcal{D}: \{0,1\}^\ell\rightarrow \S^{d-1}$ and choose $t\in\mathbb{R}$, such that for every choice of unit vectors $x,y\in \S^{d-1}$ we have:
  \begin{align*}
    \doot xy\geq\alpha &\implies \doot {\dec{\enc{x}}} {\dec{\enc{y}}}\geq t\text{ and }\\
    \doot xy\leq\beta &\implies \doot {\dec{\enc{x}}} {\dec{\enc{y}}} < t \enspace .
  \end{align*}
  We refer to the parameter $\ell$ as the \emph{space usage} of a construction.
	Whenever $d$ and $\ell$ are understood from the context we omit them and talk about the $(\alpha,\beta)$-{\sc InnerProduct} problem.
\end{definition}

On the upper bound side our main technical lemma is the following:
\begin{theorem} \label{thm:distinguish}
  $(\alpha,\beta)$-{\sc InnerProduct} can be solved using space $\ell=d\log_2\left(\frac {\sqrt{1-\beta}}{\alpha-\beta}\right)+\BOx{d}$.
\end{theorem}

Theorem~\ref{thm:distinguish} upper bounds the space needed to approximate inner products between unit vectors.
For example we can distinguish pairs with inner product $\alpha=1-\epsilon$ from pairs with inner product less than $\beta=1-2\epsilon $ using space $\frac{d}{2} \log_2{\frac 1 \epsilon }+\BOx{d}$.
The problem is closely linked to estimation, so it is unsurprising that it matches the bound in Lemma~\ref{thm:main-upper} for $\alpha-\beta=\epsilon$ in the worst case of $\beta=0$. What is interesting is that for $\beta$ close to $1$ we get improved constants, saving up to a factor 2 on the space when $\alpha$ approaches~1.

Our proof uses a variant of \emph{pyramid vector quantization}~\cite{fischer1986pyramid} and the technique is essentially an implementation of a grid-based $\varepsilon$-net as described in~\cite{Alon2017optimal}, though the analysis is different.
The exposition is supposed to be self-contained, and in particular we do not assume that the reader is familiar with pyramid vector quantization or $\varepsilon$-nets.

\medskip

Finally, we show a tight lower bound.
Consider a communication protocol where Alice is given $x\in \S^{d-1}$ and Bob is given $y\in \S^{d-1}$.
For parameters $\alpha, \beta \in (0,1)$, with $\alpha = \beta + \varepsilon$, known to both parties, how many bits of information does Alice need to send to Bob in order for Bob to be able to distinguish the cases $\langle x,y\rangle \geq \alpha$ and $\langle x,y\rangle \leq \beta$?
Specifically, how many bits must Alice send, in the worst case over all vectors $x$, to allow Bob to answer correctly for every vector $y$?
We note that a solution for the $(\alpha,\beta)$-{\sc InnerProduct} problem implies a communication protocol using $\ell$ bits, but our lower bound applies more generally to any one-way communication protocol, not necessarily based on quantization.

\begin{theorem}\label{thm:main-lower}   For each choice of $\alpha,\beta\in (0,1)$ with $\alpha > \beta$, suppose that there exists a mapping $\mathcal{E}: S^{d-1} \rightarrow \{0,1\}^\ell$ such that for all $x,y\in S^{d-1}$ we can determine from $\enc{x}$ and $\enc{y}$ whether $\doot x y \leq \beta$ or $\doot x y \geq \alpha$ (or output anything if $\doot x y \in (\beta,\alpha))$.
   Then $\ell \geq d \log_2 \left(\tfrac{\sqrt{1-\beta}}{\alpha - \beta}\right) - \BOx{d}$.
\end{theorem}
This matches the upper bound up to the additive term of $\BOx{d}$ bits.

\section{Further related work}\label{sec:related}

\subparagraph*{Motivating applications.}
Calculating the inner product of two vectors is a frequently used sub-routine in linear algebra,
and many machine learning algorithms rely heavily on inner product calculation.
For example, the inner loop of algorithms for training of complex neural networks uses millions and millions of inner product computations.
Often what is ultimately learned is an embedding onto a high dimensional unit sphere where the inner product can be used directly as a similarity measure.

In such large scale computations the bottleneck is often the limited bandwidth of the hardware in question, and having slightly smaller vector representations can massively improve the execution time.
This gives rise to the idea of computing inner products with reduced precision.
Recently, several studies showed that deep neural networks can be trained using low precision arithmetic, see e.g.~\cite{chen2015compressing,gupta2015deep,han2015deep}.
This has led to a new generation of software and reduced-precision hardware for machine learning algorithms:
\begin{itemize}
	\item NVIDIA's TensorRT GPU framework and Google's TensorFlow and Tensor Processing Unit, that both operate with 8- or 16-bit fixed point number representations, and
	\item Intel's Nervana processor that uses the so-called \emph{FlexPoint} vector representation~\cite{flexpoint}, combining 16-bit uniform quantization with a shared exponent that allows representing vectors in a large dynamic range of magnitudes.
\end{itemize}
From a theoretical point of view these hardware representations use at least $\log_2 d \pm O(1)$ more bits per dimension than what is required to ensure a given additive error.

Reduced precision inner products have also been employed in knowledge discovery~\cite{blalock2017bolt} and similarity search~\cite{guo2016quantization,jegou2011product}.

\subparagraph*{Dimensionality reduction.}
There is a large literature on the space complexity of estimating Euclidean distances, usually studied in the setting where a certain failure probability $\delta > 0$ is allowed, and with number of \emph{dimensions} (rather than bits) as the measure of space.
For certain ``random projection'' mappings $f: \mathbb{R}^d\rightarrow \mathbb{R}^D$ one can estimate the Euclidean distance $||x-y||_2$ from $f(x)$ and $f(y)$ up to a multiplicative error of $1+\varepsilon$, with failure probability~$\delta$.
It is known that using $D=\BOx{\log(\delta^{-1})\varepsilon^{-2}}$ dimensions is necessary~\cite{jayram2013optimal,kane2011almost} and sufficient~\cite{johnson1984extensions}.
For unit vectors this implies an approximation of inner products with $\BOx{\varepsilon}$ additive error through the identity
\begin{equation}\label{eq:length2inner}
\doot x y = \tfrac{1}{2}(||x||_2^2+||y||_2^2-||x-y||_2^2) \enspace .
\end{equation}
Using (a specific type of) random projections to estimate inner products, with an additive error guarantee, is known as ``feature hashing''~\cite{weinberger2009feature}.

Indyk et al.~\cite{indyk2017practical, indyk2017near} considered the bit complexity of representing all distances, up to a given relative error $1+\varepsilon$, within a given set $S$ of $n$ vectors in $\mathbb{R}^d$.
For this problem one can assume without loss of generality that $d=\BOx{\varepsilon^{-2}\log n}$, using dimension reduction.
Suppose that we only need to preserve distances of unit vectors up to an additive $\varepsilon$, which implies that inner products are preserved up to $\BOx{\varepsilon}$.
Then for $d = \varepsilon^{-2}\log n$ the space usage per point of the method described in~\cite{indyk2017near} is $\BOx{d\log(1/\varepsilon)}$.
This is within a constant factor of our upper bound, but not directly comparable to our result which works for all unit vectors.
Recently, Indyk and Wagner~\cite{indyk2018approximate} studied the space required to solve the $d$-dimensional Euclidean $(1+\varepsilon)$-approximate nearest neighbor problem in the setting where vector coordinates are integers in a bounded range (e.g.~of size $n^{\BOx{1}}$).
While this method gives guarantees for new vectors outside of $S$ their method is randomized and can fail to correctly determine an approximate nearest neighbor, while our method is deterministic.

\subparagraph*{Vector quantization.}

In a nutshell, vector quantization~\cite{gersho2012vector} is the process of mapping vectors in a space (usually a bounded subset of Euclidean space) to the nearest in a finite set of vectors~$Q$.
The goal is to minimize the size of $Q$ and the distance between vectors and their quantized versions, often with respect to a certain distribution of source (or input) vectors.
Fischer first described \emph{pyramid vector quantization}~\cite{fischer1986pyramid}, showing that it is near-optimal for Laplacian sources.
Since high-dimensional Laplacian vectors have lengths that are tightly concentrated around the expectation, it is natural to speculate if the method is also near-optimal for fixed-length (or unit) vectors.
It turns out to be easier to analyze a variant of pyramid vector quantization for which we can show that this is indeed the case.
This is described in section~\ref{sec:upper}.

Quantization methods have previously been used to speed up nearest neighbor search.
The technique of \emph{product quantization}~\cite{jegou2011product} has been particularly successful for this application.
Product quantization uses an initial random rotation of input vectors followed by application of an optimal quantization method on low-dimensional blocks.
Since the size of the codebook is fixed for each block the resulting quantization error cannot be bounded with probability 1.

Quantization of the unit sphere has been studied in complexity theory as
 \emph{$\varepsilon$-nets for spherical caps}.
 Rabani and Shpilka~\cite{rabani2010explicit} give a construction in which $|Q|$ is polynomially related to the best size possible with a given quantization error.
 Along and Klartag~\cite{Alon2017optimal} use such nets to achieve $|Q|$ that is within a factor $\exp(\BOx{d})$ of optimal, improving~\cite{rabani2010explicit} whenever the quantization error is $o(1)$, such that $|Q|$ must be superexponential in~$d$.

In the literature on machine learning (and its application areas) there is a myriad of methods for learning a data-dependent quantization mapping that exploits structure in a data set to decrease the quantization error.
We refer to the survey of Wang et al.~\cite{wang2016learning} for details.
In contrast to such methods, we seek guarantees for all vectors, not just vectors from a given data set or distribution.

\subparagraph*{Communication complexity.}

Consider a communication protocol in which Alice and Bob are given unit vectors $x,y\in \left\{\pm \tfrac{1}{\sqrt{d}}\right\}^d$ and need to approximate $\doot x y$.
The \emph{gap hamming} problem is the special case where the task is to distinguish between cases of weak positive and negative correlation:
Is $\doot x y > 1/\sqrt{d}$ or is $\doot x y < - 1/\sqrt{d}$?
This problem is known to require $\Omega(d)$ bits of communication~\cite{chakrabarti2012optimal,indyk2003tight,sherstov2012communication}, even for randomized protocols with error probability, say, $1/3$.
In turn, this implies a lower bound for the space complexity of estimating inner products, since a space complexity of $\ell$ bits implies a (one-way) communication protocol using $\ell$ bits of communication.
The lower bound extends to arbitrary thresholds $\alpha$ and $\beta$ with $\alpha - \beta = \Theta(1/\sqrt{d})$ by translation.
In this paper we consider general unit vectors $x,y\in\mathbb{R}^d$ and are able to show a higher lower bound of $\tfrac{1}{2} d \log_2 d - \BOx{d}$ bits for distinguishing inner products of distance $\varepsilon = \Theta(1/\sqrt{d})$.

\section{Upper bound}\label{sec:upper}
We use a well-known grid-based rounding method to construct our representation, see e.g.~\cite{Alon2017optimal,fischer1986pyramid}.
For completeness we provide a simple, self-contained description of a representation and show that it has the properties described in Theorem~\ref{thm:distinguish}.
The grid resolution is controlled by a parameter $\delta\in [0,1]$.
For every vector $x\in\mathbb{R}^d$ let $f(x)\in \mathbb{R}^d$ be defined by
  \begin{equation}\label{eq:pyramid}
  f(x)=x'/||x'||_2, \text{ where } x_i'=\left\lfloor x_i \tfrac{\sqrt{d} } \delta + \tfrac 1 2 \right\rfloor \frac \delta {\sqrt{d}} \text{ for } i=1,\dots,d \enspace .
  \end{equation}

  It is clear that the number of bits for storing a single integer coordinate $x_i'$ can be large in high dimensions, up to $\log_2(2\sqrt{d}/\delta)$ bits, but we can give a much better bound on the \emph{average} number of bits per coordinate.
  If $\|x\|\leq1$ we can store $f(x)$ using $\ell=d\log_2(1 / \delta)+\BOx{d}$ bits of space.
  To compute $x'$ it suffices to know the integers $z_i=\lfloor x_i \tfrac{\sqrt{d} } \delta + \tfrac 1 2 \rfloor$.
  We first allocate $d$ bits to store the set $\{ i \; | \; z_i < 0\}$, such that it only remains to store the sequence of absolute values $|z_1|,\dots,|z_d|$.
     Next, using $\|x\|_2\leq 1$ we observe that
	 	 \[\sum_{i=1}^d |z_i| \leq \|x\|_1 \tfrac{\sqrt{d}}{\delta} + d/2 \leq \sqrt{d}\,\|x\|_2\,\tfrac{\sqrt{d}}{\delta} + d/2 \leq d / \delta + d/2 \enspace .\]
	      Thus if we set $s=\left\lfloor d/\delta + d/2\right\rfloor$ we can encode $|z_1|,\dots,|z_d|$ by specifying a partitioning of $s$ elements into $d+1$ parts.
     There are ${s+d\choose d}$ such partitionings so we can assign each vector a unique representation of $\ell = \left\lceil \log_2{s+d\choose d}\right\rceil + d
	      = d\log_2\left(1/\delta \right) + \BOx{d}$ bits.

Before proving Theorem~\ref{thm:distinguish} we give a simple space bound for distance distortion which is useful in it own right.

\begin{lemma}
  \label{lem:distortion}
   For $\delta \leq 1$ and every choice of $x,y\in\mathbb{R}^d$, defining $f$ according to (\ref{eq:pyramid}) we have:
   \[\| x-y \|_2- \delta \leq \|f(x)-f(y)\|_2 \leq \|x-y\|_2 + \delta\enspace .\]
\end{lemma}

   \begin{proof}

     Observe that $|x_i-x_i'|\leq \frac \delta {2\sqrt{d}}$. This means that:
          \[ \|x-x'\|_2 = \sqrt{\sum_{i=1}^d (x_i-x_i')^2}\leq \sqrt{\sum_{i=1}^d \frac {\delta^2} {4d}} = \frac \delta 2 \enspace . \]
	 	 Since $\delta \leq 1$ the angle between $x$ and $x'$ is bounded by $\pi/3$, and hence $\|x-f(x)\|_2 \leq 1$.
	 This implies that
	 $\|x-f(x)\|^2_2 = 2 - 2\doot{x}{x'/||x'||_2} \leq 1+\|x'\|_2 - 2\doot{x}{x'} =\|x-x'\|^2_2$, and in particular we get $\|x-f(x)\|_2 \leq \|x-x'\|_2 \leq \delta / 2$.
     Finally, using the triangle inequality:
	 	 \begin{align*}
	 \|f(x)-f(y)\|_2 & \leq \|x-f(x)\|_2 + \| x - y \|_2 + \| y-f(y)\|_2 \leq \|x-y\|_2 + \delta  ,\text{ and}\\
     \|f(x)-f(y)\|_2 & \geq\|x-y\|_2-\|x-f(x)\|_2-\|y-f(y)\|_2\geq \|x-y\|_2-\delta \enspace .
	 \end{align*}
\end{proof}
We are now ready to prove Theorem~\ref{thm:distinguish}.
\begin{proof}[Proof of Theorem~\ref{thm:distinguish}]
	Let the encoding function $\enc{\cdot}$ map a vector $x$ to the $\ell$-bit representation of $x'$ as defined in $(\ref{eq:pyramid})$.
    The decoding function $\dec{\cdot}$ is defined such that $\dec{\enc{x}} = f(x)$.

    By Lemma~\ref{lem:distortion} we have:
  \[\max\{0,\| x- y \|- \delta\} \leq \|f(x)-f(y)\| \leq \|x- y\| + \delta\enspace .\]

\noindent
  Using the distance bounds and the identity (\ref{eq:length2inner}) several times we get:
    \begin{align*}
    \doot {f(x)}{f(y)} &= \tfrac 12 (\|f(x)\|^2+\|f(y)\|^2-\|f(x)-f(y)\|^2)\\
                        &\leq\min\{1,\tfrac12 (2+2\|x-y\|\delta-\|x-y\|^2-\delta^2)\}\\
                        &=\min\{1,\doot x y +\|x-y\|\delta-\delta^2/2\}, \text{ and }\\[2ex]
    \doot {f(x)}{f(y)} &\geq\tfrac12 (2-2\|x-y\|\delta-\|x-y\|^2-\delta^2)\\
                        &=\doot x y -\|x-y\|\delta-\delta^2/2 \enspace .
  \end{align*}

  \noindent
  We can then see
    \begin{align*}
      \doot x y\geq \alpha \implies \doot {\dec{\enc{x}}} {\dec{\enc{y}}}&\geq \alpha-\delta\sqrt{2-2\alpha}-\delta^2/2\text{ and}\\
      \doot x y\leq \beta \implies \doot {\dec{\enc{x}}} {\dec{\enc{y}}}&\leq \min\{1,\beta+\delta\sqrt{2-2\beta}-\delta^2/2\}
    \end{align*}
    Setting $\delta=\frac {\alpha-\beta}{2\sqrt{2-2\beta}}$ and $t=\alpha-\delta\sqrt{2-2\alpha}-\delta^2/2$ we get a valid solution to the $(\alpha,\beta)$-{\sc InnerProduct} problem.
\end{proof}

The same grid, as specified by $\delta$, works for every $(\alpha',\beta')$-{\sc InnerProduct} instance (with a suitable choice of threshold $t$) as long as
		\begin{equation}\label{eq:delta-bound}
	\delta < \frac{\alpha'-\beta'}{\sqrt{2-2\alpha'}+\sqrt{2-2\beta'}} \enspace .
	\end{equation}

Note that Lemma~\ref{thm:main-upper} also follows from Theorem~\ref{thm:distinguish}:
For a given inner product value $p$ consider $\alpha' = p + \varepsilon / 2$ and $\beta' = p - \varepsilon / 2$.
Setting $\delta = \varepsilon / 4$, we satisfy (\ref{eq:delta-bound}) for all $p$ and get that for every choice of unit vectors $x,y\in \S^{d-1}$:
  \[\doot x y - \epsilon \leq \doot {\dec{\enc{x}}}{\dec{\enc{x}}}\leq \doot x y + \epsilon  \enspace. \]

\section{Lower bound}\label{sec:lower}

Consider a one-way communication protocol solving the $(\alpha,\beta)$-{\sc InnerProduct} problem where Alice sends a string $\enc{x}$ to Bob, and Bob must be able to output a real number $p(\enc{x},y)$ and a threshold $t\in\mathbb{R}$ such that
$$\langle x,y\rangle \geq \alpha \implies p(\enc{x},y)\geq t \text{, and}$$
$$\langle x,y\rangle \leq \beta\implies p(\enc{x},y) < t \enspace . $$
Note that there is no requirement on $p(\enc{x},y)$ whenever $\langle x,y\rangle \in (\beta,\alpha)$.
We wish to answer the following question: How many bits must Alice send, in the worst case over all vectors $x$, to allow Bob to answer correctly for every vector $y$?

Let $d>1$ be an integer.
For $\varepsilon > 0$ and $x\in \mathbb{R}^d$ let
$B_\varepsilon(x) = \{ y\in \mathbb{R}^d \; | \; ||x-y||_ 2\leq\varepsilon \}$
be the ball of radius $\varepsilon$ centered at $x$, let $B_1 = B_1(0)$ be the unit ball centered at the origin, and denote by $\text{cap}_{\Theta}(x) = \{ y \in \S^{d-1} \; | \; \langle x, y\rangle \geq \cos \Theta \}$ the unit spherical cap around $x$ with polar angle $\Theta$.

\subsection{Preliminaries}

The gamma function is an extension of the factorial function to complex numbers.
We will need the following formulas for the value of the gamma function on integers and half-integers (see e.g.~\cite{vidunas2005}). For integer $n > 0$:
\begin{equation}\label{eq:gamma}
\begin{split}
\Gamma(n + \tfrac{1}{2}) & = \frac{(2n)!\sqrt{\pi}}{2^{2n} n!}\\
\Gamma(n + 1) & = n!
\end{split}
\end{equation}

\begin{lemma}\label{lem:gamma_fraction}
	For integer $d>1$, $\Gamma(d/2+\tfrac{1}{2}) / \Gamma(d/2+1) > 1/(3\sqrt{d})$.
\end{lemma}
\begin{proof}
	We use Stirling's approximation to the factorial:
		$$ \sqrt{2\pi} n^{n+1/2} e^{-n} \leq n! \leq e\, n^{n+1/2} e^{-n}$$
		Together with (\ref{eq:gamma}) we get, for even $d$:
		\begin{alignat*}{1}
		\Gamma(d/2+\tfrac{1}{2}) / \Gamma(d/2+1)
		= \frac{d!\sqrt{\pi}}{2^d((d/2)!)^2}
		\geq \frac{\sqrt{2}\pi \, d^{d+1/2} e^{-d}}{2^d e^2 (d/2)^{d+1} e^{-d}}
		 = \frac{2\sqrt{2}\pi}{e^2 \sqrt{d}}
		 > 1/(3\sqrt{d}) \enspace .
	\end{alignat*}
	The case of odd $d$ is similar.
\end{proof}

\begin{lemma}\label{lem:vol}
	Let $c_d = \frac{\pi^{d/2}}{\Gamma(d/2+1)}$, $r>0$, and $\delta\in(0,1)$. Then:
\begin{enumerate}
\item\label{eq:1} The volume of $B^d_r$, the $d$-dimensional ball of radius $r$, is
$c_d\, r^d$.
\item\label{eq:2} The surface area of $\S^{d-1}_r$, the $d$-dimensional sphere of radius $r$, is
$c_{d}\, d\, r^{d-1}$.
\item\label{eq:3} The surface area of $\text{cap}^d_{\Theta}(x)$, a unit spherical cap with polar angle $\Theta$, is at most $$c_{d-1}\, d\, (2(1 - \cos \Theta))^{(d-1)/2} \enspace .$$
\end{enumerate}
\end{lemma}
\begin{proof}
	Volume bound \ref{eq:1}.~is standard, see e.g.~\cite[page 11]{pisier1999volume}.
	Differentiating with respect to~$r$ gives the surface area in line~\ref{eq:2}.
	For the upper bound \ref{eq:3}.~we express the surface area as an integral.
	Let $r(h)=\sqrt{h(2-h)} < \sqrt{2h}$ be the radius of the $d-1$-dimensional sphere at the base of the cap of height $h$.
	Note that the sphere has surface area $c_{d-1}\, d\, r(x)^{d-1}$.
	Integrating over cap heights from $0$ to $1-\cos\Theta$ we bound the surface area:
		$$\int^{1 - \cos \Theta}_0 c_{d-1}\, d\, r(x)^{d-1} dx \leq (1 - \cos \Theta) c_{d-1}\, d\, (2(1 - \cos \Theta))^{(d-1)/2} \enspace . $$
		The inequality uses that $r(x)\leq r(1 - \cos \Theta) \leq \sqrt{2(1 - \cos \Theta)}$ for $x\in [0,1 - \cos \Theta]$.
\end{proof}

\begin{lemma}
	For every $\Theta \in (0,\pi/2)$ there exists a code $\mathcal{C}_\Theta \subset S^{d-1}$ of size
		\[|\mathcal{C}_\Theta| \geq (2(1-\cos\Theta))^{(d-1)/2} / (3\sqrt{d}) \]
		such that for all $x,y\in\mathcal{C}_\Theta$ with $x\ne y$ we have $\langle x, y\rangle \geq \cos\Theta$.
\end{lemma}
\begin{proof}
	We follow the outline of the standard non-constructive proof of the Gilbert-Varshamov bound.
	That is, we argue that $\mathcal{C}_\Theta$ can be constructed in a greedy manner by adding an additional point from
		$$\S^{d-1} \backslash \bigcup_{x\in\mathcal{C}_\Theta} \text{cap}^d_\Theta(x)$$
		until this set is empty.
	Clearly this construction produces a set $\mathcal{C}_\Theta$ with the property that every pair of points have angle greater than $\Theta$.
	We observe that the procedure can stop only when the area of $\bigcup_{x\in\mathcal{C}_\Theta} \text{cap}_{\Theta}(x)$ exceeds that of $\S^{d-1}$.
	The number of iterations, and thus the size of $\mathcal{C}_\Theta$ is at least the ratio between the surface area of the unit sphere and a spherical cap, $\text{cap}_{\Theta}(\cdot)$.
	In turn, this is lower bounded by the ratio of bound number~\ref{eq:2}~(with $r=1$) and~\ref{eq:3}~from Lemma~\ref{lem:vol}. Using Lemma~\ref{lem:gamma_fraction} we get:
		$$ \frac{c_d\, d}{c_{d-1}\, d\, (2(1-\cos\Theta))^{(d-1)/2}} \geq (2(1-\cos\Theta))^{-(d-1)/2} / (3\sqrt{d}) \enspace .$$
\end{proof}

\subsection{Space complexity}

Define $\Theta = \arccos \beta - \arccos \alpha$.
We claim that for every pair of vectors $x_1,x_2\in \S^{d-1}$ with angle $\theta = \arccos \, \langle x_1, x_2\rangle \geq \Theta$ there exists a vector $y\in \S^{d-1}$ such that $\langle x_1, y\rangle =\beta$ and $\langle x_2, y\rangle \geq \alpha$.
Specifically, let
\begin{equation}\label{eq:y-def}
y = y(x_1,x_2)
= \left(\beta - \sqrt{1-\beta^2}\, \tfrac{\cos\theta}{\sin\theta}\right) x_1 + \tfrac{\sqrt{1-\beta^2}}{\sin\theta} \, x_2 \enspace .
\end{equation}
To see that $y$ is indeed a unit vector we compute $||y||_2^2 = \langle y,y\rangle$.
Since $\langle x_1, x_2\rangle = \cos\theta$ (by definition of $\theta$) and $\langle x_1, x_1\rangle = \langle x_2, x_2\rangle = 1$ (since $x_1$ and $x_2$ are unit vectors) we get:
\begin{align*}
\langle y,y\rangle & = \left(\beta - \sqrt{1-\beta^2} \, \tfrac{\cos\theta}{\sin\theta}\right)^2 + \left(\tfrac{\sqrt{1-\beta^2}}{\sin\theta}\right)^2 + 2 \left(\beta - \sqrt{1-\beta^2}\, \tfrac{\cos\theta}{\sin\theta}\right) \left(\tfrac{\sqrt{1-\beta^2}}{\sin\theta}\right) \cos\theta\\
 & = \beta^2 + \tfrac{1-\beta^2}{\sin^2\theta} (1-\cos^2\theta)\\
 & = \beta^2 + (1-\beta^2) = 1 \enspace .
\end{align*}
The third equality uses the Pythagorean identity $\cos^2\theta + \sin^2\theta = 1$.
Next, we check that $y$ has the claimed inner products with $x_1$ and $x_2$:
\begin{align*}
\langle x_1, y \rangle & = \left(\beta - \sqrt{1-\beta^2}\, \tfrac{\cos\theta}{\sin\theta}\right) + \sqrt{1-\beta^2}\, \tfrac{\cos\theta}{\sin\theta} = \beta,\\
\langle x_2, y \rangle
& = \left(\beta - \sqrt{1-\beta^2}\, \tfrac{\cos\theta}{\sin\theta}\right) \cos\theta + \tfrac{\sqrt{1-\beta^2}}{\sin\theta}\\
& = \langle (\beta, \sqrt{1-\beta^2}), (\cos\theta,\tfrac{1-\cos^2\theta}{\sin\theta})\rangle\\
& = \langle (\beta, \sqrt{1-\beta^2}), (\cos\theta,\sin\theta)\rangle
\geq \alpha \enspace .
\end{align*}
The final inequality follows since the angle between the vectors $(\beta, \sqrt{1-\beta^2})$ and $(\cos\theta,\sin\theta)$ is at most $\arccos(\beta) - \theta \leq \arccos(\beta) - \Theta = \arccos\alpha$.

\medskip

Now consider the code $\mathcal{C}_\Theta$.
For distinct $x_1,x_2\in \mathcal{C}_\Theta$ we must have, for $y = y(x_1,x_2)$ as defined in (\ref{eq:y-def}), $p(e(x_1),y) < t \leq p(e(x_2),y)$, which means that $e(x_1)\ne e(x_2)$.
Hence $R = \{ \enc{x} \; | \; x\in \S^{d-1}\}$ must contain at least $|\mathcal{C}_\Theta|$ binary strings, and in particular
\begin{align*}
	\ell \geq \log_2 |\mathcal{C}_\Theta|
	& \geq \log_2\left( (2(1-\cos\Theta))^{-(d-1)/2} / (3\sqrt{d}) \right)\\
	& \geq \tfrac{d}{2} \log_2\left(\frac{1}{1-\cos\Theta}\right) - \BO{d}\\
	& \geq d \log_2 (1/\Theta) - \BO{d} \enspace .
\end{align*}
For the final inequality we use that $1-\cos\Theta \leq \Theta^2$, which holds when $\Theta \in (0,\pi/2)$.
To finish the proof we will show that whenever $0 \leq \beta \leq \alpha\leq 1$:
\begin{equation}\label{eq:arccos}
\Theta = \arccos\beta - \arccos\alpha \leq \tfrac{\pi}{2} \tfrac{\alpha-\beta}{\sqrt{1-\beta}} \enspace .
\end{equation}
For each fixed $\beta\in [0,1]$ we must show that $\arccos \alpha \geq \arccos\beta - \tfrac{\pi}{2} \tfrac{\alpha-\beta}{\sqrt{1-\beta}}$ for all $\alpha\in [\beta,1]$.
Since $\alpha \mapsto \arccos\alpha$ is concave for $\alpha\in [0,1]$, and the function $\alpha\mapsto \arccos\beta - \tfrac{\pi}{2} \tfrac{\alpha-\beta}{\sqrt{1-\beta}}$ is linear, it suffices to check the inequality at the endpoints where $\alpha=\beta$ and $\alpha = 1$.
In the former case we clearly get equality.
In the latter we use the fact $\arccos \beta - \tfrac{\pi}{2} \sqrt{1-\beta} \leq 0$ for $\beta\in [0,1]$
to see that the inequality (\ref{eq:arccos}) holds.

This proves that $\ell \geq d\log_2\left(\frac{\sqrt{1-\beta}}{\alpha-\beta}\right) - \BOx{d}$ bits are needed, establishing Theorem~\ref{thm:main-lower}.

\section{Experiments}

Since the encoding in our upper bound is potentially practical, we evaluated the accuracy of the method experimentally on several data sets.
We also computed the space usage of each set of vectors, based on an optimal encoding of the method of Section~\ref{sec:upper} with various values of parameter $\delta$, and compared it to a baseline of using 32-bit floating point numbers.

We considered three data sets, MNIST (handwritten digits), SIFT (image features), and DLIB-FACES (neural net embeddings of faces on a 128-dimensional unit sphere).
The data sets are chosen to span different distributions of entry magnitude.
Whereas MNIST vectors are approximately sparse, DLIB vectors have smoothly distributed magnitudes.
MNIST and SIFT are not natively unit vectors, so we normalized the vectors prior to encoding.

We computed the inner product error for 2000 vector pairs in each data set.
Table~\ref{experiments} shows the maximum absolute error observed when calculating inner products using the decoded vectors compared to using the original vectors.
It also shows the median absolute error and the error at the 90th percentile.

In all cases the observed errors are well below the worst case bound of~$\epsilon = 4\delta$.
This can partly be explained by sparsity of vectors, since our method represents zero entries in vectors with no error.
Also, while the effect of $d$ rounding errors is $d$ times the individual error in the worst case (which is what our theoretical results bound), in the typical case errors will tend to cancel since not all errors go in the same direction.
Heuristically we could imagine that errors are independent and random, in which case we would expect the sum of all errors to be proportional to $\sqrt{d}$ rather than $d$.

\begin{table}[t]
\centering

\begin{tabular}{lll|c|lll}
 Dataset & $d$      &  $\delta$  & space 	& median  & 90th pct.       & max                        \\\hline
  MNIST  & 784      &  0.1         & 16\% 	& 0.0019  &  0.0052         & 0.0165              \\
  SIFT   & 128      &  0.1         & 16\% 	& 0.0034  &  0.0084         & 0.0181               \\
  DLIB   & 128      &  0.1         & 16\% 	& 0.0028  &  0.0071         & 0.0135              \\\hline
  MNIST  & 784      &  0.05        & 19\% 	& 0.0008  &  0.0027         & 0.0103               \\
  SIFT   & 128      &  0.05        & 19\% 	& 0.0019  &  0.0044         & 0.0091               \\
  DLIB   & 128      &  0.05        & 19\% 	& 0.0012  &  0.0033         & 0.0075              \\\hline
  MNIST  & 784      &  0.01        & 26\% 	& 0.0002  &  0.0007         & 0.0027              \\
  SIFT   & 128      &  0.01        & 26\% 	& 0.0004  &  0.0008         & 0.0100               \\
  DLIB   & 128      &  0.01        & 26\% 	& 0.0002  &  0.0005         & 0.0011
\end{tabular}
\caption{\small Space usage and absolute inner product error using the method of Section~\ref{sec:upper} on pairs of vectors from various real-life data sets.
The space usage is measured against a baseline of using a 32-bit floating point numbers to represent each of the $d$ dimensions.
Observed errors are smaller than our worst-case bound of $4\delta$, probably due to cancellation effects.}\label{experiments}
\end{table}

\section{Conclusion}

We have established tight upper and lower bounds for the problem of representing unit vectors such that inner products can be estimated within a given additive error (with probability~1).
An interesting possibility would be to consider relative error estimates of Euclidean distances (as in the recent work~\cite{indyk2018approximate}) while not allowing any failure probability. Another potential direction would be to achieve provably smaller \emph{expected} error, while preserving the worst-case guarantees, by applying an initial random rotation to all data vectors.