\section{Introduction}
\label{sec:introduction}

Given a tamely embedded closed curve $\gamma$ in $\mathbb{R}^3$, its \emph{superbridge number} $\operatorname{sb}(\gamma)$ is the maximum number of local maxima of any projection of $\gamma$ to a line. For a knot type $K$, its \emph{superbridge index} $\operatorname{sb}[K]$ is the minimum superbridge number of any realization of $K$. This knot invariant was first defined by Kuiper~\cite{kuiper_new_1987}, and was the first example of a so-called \emph{superinvariant}~\cite{adams_introduction_2002,Adams:2009ha}.

Although Kuiper determined it for all torus knots, the superbridge index is generally quite hard to compute; for example, prior to this work it was known for only 49 of the 249 nontrivial knots in the Rolfsen table. The goal here is to determine the superbridge index of a number of knots, including 15 of the 27 9-crossing knots for which it was previously unknown and, for the first time, for some 12-crossing knots.

\begin{theorem}\label{thm:main}
	The knots $9_3$, $9_4$, $9_6$, $9_9$, $9_{11}$, $9_{13}$, $9_{17}$, $9_{18}$, $9_{22}$, $9_{23}$, $9_{25}$, $9_{27}$, $9_{30}$, $9_{31}$, and $9_{36}$ have superbridge index equal to 4, and the knots $11n_{72}$, $11n_{77}$, $12n_{60}$, $12n_{66}$, $12n_{219}$, $12n_{225}$, and $12n_{553}$ have superbridge index equal to 5.
\end{theorem}

\begin{figure}[t]
	\centering
		\subfloat[$9_{25}$]{\includegraphics[height=2in,width=2in,keepaspectratio,valign=c]{9_25.pdf}} \qquad \qquad
		\subfloat[$12n_{66}$]{\includegraphics[height=2in,width=2in,keepaspectratio,valign=c]{K12n66.pdf}}
	\caption{Superbridge-minimizing realizations of $9_{25}$ and $12n_{66}$. Both are shown in orthographic perspective, viewed from the direction of the positive $z$-axis relative to the vertex coordinates given in \Cref{sec:coords}.}
	\label{fig:9_25 and K12n66}
\end{figure}

For each knot, the strategy is to find a (polygonal) realization of the knot with superbridge number equal to a known lower bound; the realizations of $9_{25}$ and $12n_{66}$ are shown in \Cref{fig:9_25 and K12n66}, and visualizations and coordinates for all knots mentioned in the theorem are given in \Cref{sec:coords}. These realizations were found by generating very large ensembles of polygonal knots in tight confinement using the approach described in~\cite{TomClay} and implemented in {\tt stick-knot-gen}~\cite{stick-knot-gen}. Overall, I generated more than 1 trillion random 9-, 10-, 11-, 12-, and 13-gons in the search for these examples. Interestingly, at least half of these superbridge-minimizing examples do not minimize the stick number of the knot. For example, the polygonal realization of $9_{25}$ shown in \Cref{fig:9_25 and K12n66} has 11 edges, but there are polygonal realizations of $9_{25}$ with only 10 edges~\cite{TomClay}.

Aside from the computational challenge of generating such large ensembles and determining knot types, the main difficulty is to identify potential examples and to rigorously compute their superbridge numbers. Different knots in the statement of the theorem require different arguments, so the proof will proceed in the following three sections, each of which groups together knots requiring the same argument, sorted in order of increasing complexity. Specifically, \Cref{thm:main} is a direct consequence of \Cref{cor:11n72 and 12n553}, \Cref{prop:9_22 11n77 12n60 12n219}, and \Cref{prop:rest}.

For reference, \Cref{sec:table} gives complete, up-to-date information about the superbridge index of all knots from the Rolfsen table, and \Cref{sec:exact values} lists all prime knots through 16 crossings for which the exact superbridge index is known. This information, along with the coordinate data from \Cref{sec:coords}, is also available from the {\tt stick-knot-gen} project~\cite{stick-knot-gen}.

\section{Stick number bounds}
\label{sec:stick bounds}

The easiest way to get an upper bound on superbridge index is using Jin's bound relating superbridge index to stick number. Recall that the \emph{stick number} $\operatorname{stick}[K]$ of a knot $K$ is the minimum number of edges needed for any polygonal realization of the knot.

\begin{theorem}[Jin~\cite{jin_polygon_1997}]\label{thm:JinBound}
	For any knot $K$, $\operatorname{sb}[K] \leq \frac{1}{2} \operatorname{stick}[K]$.
\end{theorem}

Both $11n_{72}$ and $12n_{553}$ have stick number no bigger than 11.

\begin{proposition}\label{prop:11n72 and 12n553}
	$\operatorname{stick}[11n_{72}],\operatorname{stick}[12n_{553}] \leq 11$.
\end{proposition}

\begin{proof}
	11-stick realizations of both knots are shown in \Cref{fig:11n72 and 12n553}. The coordinates of these realizations are given in \Cref{sec:coords}.
\end{proof}

\begin{figure}[t]
	\centering
		\subfloat[$11n_{72}$]{\includegraphics[height=2in,width=2in,keepaspectratio,valign=c]{K11n72.pdf}} \qquad \qquad
		\subfloat[$12n_{553}$]{\includegraphics[height=2in,width=2in,keepaspectratio,valign=c]{K12n553.pdf}}
	\caption{11-stick realizations of $11n_{72}$ and $12n_{553}$. Both are shown in orthographic perspective, viewed from the direction of the positive $z$-axis relative to the vertex coordinates given in \Cref{sec:coords}.}
	\label{fig:11n72 and 12n553}
\end{figure}

It is then an immediate consequence of \Cref{thm:JinBound} that these knots both have superbridge index $\leq 5$. On the other hand, a useful lower bound on superbridge index comes from the bridge index $\operatorname{b}[K]$.

\begin{theorem}[Kuiper~\cite{kuiper_new_1987}]\label{thm:bridge bound}
	For any nontrivial knot $K$, $\operatorname{b}[K] < \operatorname{sb}[K]$.
\end{theorem}

Since $11n_{72}$ and $12n_{553}$ are both 4-bridge knots~\cite{Musick:2012uz,blair_wirtinger_2020,knotinfo}, this completely determines the superbridge index of both knots.

\begin{corollary}\label{cor:11n72 and 12n553}
	$\operatorname{sb}[11n_{72}] = \operatorname{sb}[12n_{553}] = 5$.
\end{corollary}

\section{Linear programming bounds}
\label{sec:linear programming bounds}

The proof of Jin's bound $\operatorname{sb}[K] \leq \frac{1}{2}\operatorname{stick}[K]$ (\Cref{thm:JinBound}) is straightforward: the projection of any polygonal closed curve to a line cannot have more critical points than there are vertices along the original curve. In other words, the superbridge number of any $n$-edge polygonal realization of a knot is no more than $\frac{n}{2}$. This is more significant than it might first appear, since it is generally quite challenging to give any useful upper bound on the superbridge number of a closed curve. After all, if the projection of a closed curve $\gamma$ in to a line has $k$ local maxima, this shows that $\operatorname{sb}(\gamma) \geq k$: the inequality goes the wrong way! So it is a special situation to have an easily computed certificate (in this case, the count of edges) that a particular realization of a knot has superbridge number $\leq m$ for some concrete $m$.

The problem is that Jin's bound can be arbitrarily bad: while there are only finitely many knots $K$ with $\operatorname{stick}[K] \leq n$ for any $n$~\cite{calvo_geometric_2001,negami_ramsey_1991}, there are infinitely many knots with superbridge index equal to 4 (including all $(2,p)$-torus knots~\cite{kuiper_new_1987}). So it is frequently necessary to find some other way of certifying an upper bound on the superbridge number of a realization.

In a previous paper~\cite{shonkwiler_new_2020}, I developed a new approach based on linear programming, as follows. Suppose a polygonal closed curve has edge vectors $\vec{e}_1, \dots, \vec{e}_n$. Then for any $\vec{v} \in \mathbb{R}^3$, the number of local maxima of the projection of the curve to the line spanned by $\vec{v}$ is the number of times that $\vec{v} \cdot \vec{e}_i$ changes from positive to negative (computed cyclically, so that $\vec{v} \cdot \vec{e}_n > 0$ and $\vec{v} \cdot \vec{e}_1 < 0$ contributes 1 to the count). Jin's bound implies that $\operatorname{sb}(\vec{e}_1, \dots , \vec{e}_n) \leq \frac{n}{2}$, with equality if and only if $n$ is even and there is some line onto which every vertex projects to a local minimum or a local maximum; i.e., $\vec{v} \cdot \vec{e}_1, \dots , \vec{v} \cdot \vec{e}_n$ alternates signs. Since $\vec{v}$ can be replaced by $-\vec{v}$, it is no restriction to assume that the alternating sign pattern is $+, -, \dots , +, -$.

Equivalently, if
\begin{equation}\label{eq:E}
	E := \left[\, \vec{e}_1 \,\,\vline\, -\vec{e}_2 \,\,\vline\,\, \cdots \,\,\vline\,\, \vec{e}_{2k-1} \,\,\vline\, -\vec{e}_{2k} \,\right],
\end{equation}
then $\operatorname{sb}(\vec{e}_1 , \dots , \vec{e}_{2k}) < k$ if and only if there is no $\vec{v} \in \mathbb{R}^3$ so that $\vec{v}^T E$ has all positive entries. In other words, infeasibility of a system of linear inequalities provides a stronger upper bound on the superbridge number of a polygonal realization of a knot than that coming from Jin's bound.

This is helpful, because classical theorems of the alternative~\cite{Tucker:1956ve,dantzig_linear_2003} control feasibility of such systems. For example:

\begin{theorem}[Gordan~\cite{gordan_uber_1873}]\label{thm:Gordan}
	If $A$ is a $k \times \ell$ matrix, then exactly one of the following is true:
	\begin{enumerate}
		\item There is $\vec{v} \in \mathbb{R}^k$ so that $\vec{v}^T A$ has all positive entries.
		\item There is a nonzero vector $\vec{u} \in \mathbb{R}^\ell$ with nonnegative entries so that $A \vec{u} = \vec{0}$.
	\end{enumerate}
\end{theorem}

This yields the desired bound on superbridge numbers.

\begin{corollary}[Shonkwiler~\cite{shonkwiler_new_2020}]\label{cor:Gordan}
	Suppose $\vec{e}_1, \dots , \vec{e}_{2k}$ are the edges of a closed polygonal curve in $\mathbb{R}^3$. Then $\operatorname{sb}(\vec{e}_1, \dots , \vec{e}_{2k}) < k$ if and only if there exists a nonzero vector $\vec{u} \in \mathbb{R}^n$ with nonnegative entries so that
	\begin{equation} \label{eq:even gordan}
		E \vec{u} = \vec{0},
	\end{equation}
	with the matrix $E$ defined as in \eqref{eq:E}.
\end{corollary}

The vector $\vec{u}$ provides a certificate that the superbridge number of the polygonal realization is strictly less than half the number of vertices. This approach is enough to determine the superbridge indices of four more knots in the statement of \Cref{thm:main}.

\begin{proposition}\label{prop:9_22 11n77 12n60 12n219}
	$\operatorname{sb}[9_{22}] = 4$ and $\operatorname{sb}[11n_{77}] = \operatorname{sb}[12n_{60}] = \operatorname{sb}[12n_{219}] = 5$.
\end{proposition}

\begin{figure}[t]
	\centering
		\begin{tabular*}{0.75\textwidth}{C{2.2in} R{.4in} R{.4in} R{.4in}}
		\multicolumn{4}{c}{$9_{22}$} \\
		\cline{1-4}\noalign{\smallskip}
		\multirow{12}{*}{\includegraphics[height=1.8in,width=1.8in,keepaspectratio]{9_22.pdf}}
		& $0$ & $0$ & $0$ \\
		& $1000$ & $0$ & $0$ \\
		& $92$ & $419$ & $0$ \\
		& $268$ & $-564$ & $44$ \\
		& $716$ & $266$ & $374$ \\
		& $411$ & $-63$ & $-519$ \\
		& $1029$ & $-280$ & $236$ \\
		& $37$ & $-226$ & $352$ \\
		& $489$ & $10$ & $-509$ \\
		& $879$ & $-326$ & $349$\\
		\end{tabular*}
		\medskip
		\[(107029574,1,1,1,2,97177084,37335363,57495926,18717108,9955666)\]
	\caption{A 10-stick $9_{22}$ with superbridge number $4$. The three columns to the right of the image give the coordinates of the vertices, and the vector below is the $\vec{u}$ solving~\eqref{eq:even gordan}. The knot is shown in orthographic perspective, viewed from the direction of the positive $z$-axis.}
	\label{fig:9_22}
\end{figure}

\begin{proof}
	By \Cref{thm:JeonJin}, stated below, $\operatorname{sb}[9_{22}] \geq 4$. On the other hand, \Cref{fig:9_22} gives a 10-stick realization of $9_{22}$ which has superbridge number $\leq 4$. To verify this with \Cref{cor:Gordan}, it suffices to find a nonzero vector $\vec{u} \in \mathbb{R}^{10}$ with nonnegative entries so that
	\[
		\begin{bmatrix}1000 & 908 & 176 & -448 & -305 & -618 & -992 & -452 & 390 & 879 \\
 0 & -419 & -983 & -830 & -329 & 217 & 54 & -236 & -336 & -326 \\
 0 & 0 & 44 & -330 & -893 & -755 & 116 & 861 & 858 & 349 \end{bmatrix} \vec{u} = \vec{0}.
	\]
	It is easy to check that
	\[
		\vec{u} = (107029574, 1, 1, 1, 2, 97177084, 37335363, 57495926, 18717108, 9955666)
	\]
	is such a vector, so this completes the proof that $\operatorname{sb}[9_{22}] = 4$.

	A similar argument shows that the knots $11n_{77}$, $12n_{60}$, and $12n_{219}$ have superbridge index $\leq 5$: 12-stick realizations of these knots together with vectors $\vec{u}$ solving~\eqref{eq:even gordan} are given in \Cref{sec:coords}. The certificate vectors $\vec{u}$ were found using \emph{Mathematica}'s {\tt FindInstance} function.

	Since $11n_{77}$, $12n_{60}$, and $12n_{219}$ are all 4-bridge knots~\cite{Musick:2012uz,blair_wirtinger_2020,knotinfo}, \Cref{thm:bridge bound} implies that each of these knots has superbridge index $\geq 5$, completing the proof that their superbridge indices are exactly 5.
\end{proof}

Each of the polygonal realizations used in the above proof was originally generated with coordinates given as double-precision floating point numbers. However, these coordinates were all rounded to three significant digits and converted to integers (while verifying this did not change the knot type) to make it easier to verify the existence of exact solutions to~\eqref{eq:even gordan}.

The lower bound on $\operatorname{sb}[9_{22}]$ comes from Jeon and Jin's characterization of the possible 3-superbridge knots.

\begin{theorem}[Jeon--Jin~\cite{jeon_computation_2002}]\label{thm:JeonJin}
	Every knot except $3_1$ and $4_1$ and possibly $5_2$, $6_1$, $6_2$, $6_3$, $7_2$, $7_3$, $7_4$, $8_4$, and $8_9$ has superbridge index $\geq 4$.
\end{theorem}

This statement is slightly different than the one given in Jeon and Jin's paper, which included $8_7$ among the possible 3-superbridge knots; see~\cite{shonkwiler_new_2020} for the proof that $\operatorname{sb}[8_7]=4$.

\section{An extension to odd numbers of edges}
\label{sec:extension}

Between \Cref{prop:9_22 11n77 12n60 12n219} and~\cite{shonkwiler_new_2020}, \Cref{cor:Gordan} has now been used to determine the superbridge indices of 21 8- and 9-crossing knots, but as stated it is limited to polygonal realizations of knots with an even number of edges. The goal now is to extend this approach to polygonal knots with an odd number of edges.

Suppose $\vec{e}_1, \dots , \vec{e_{2k+1}}$ are the edge vectors of some closed polygonal curve in $\mathbb{R}^3$. By \Cref{thm:JinBound}, $\operatorname{sb}(\vec{e}_1, \dots , \vec{e}_{2k+1}) \leq k$. If this is actually an equality, then there must be some vector $\vec{v} \in \mathbb{R}^3$ so that the projection of the polygon to the line containing $\vec{v}$ has exactly $k$ local maxima, meaning that the list $\vec{v} \cdot \vec{e}_1, \dots, \vec{v} \cdot \vec{e}_{2k+1}$ switches from positive to negative $k$ times (when considered cyclically). After possibly replacing $\vec{v}$ with $-\vec{v}$, the sign pattern can be assumed to be some cyclic permutation of
\[
	+, +, -, +, -, \dots , +, -.
\]

Let $(s_1, \dots , s_{2k+1})=(0,0,1,0,1,\dots,0,1)$ and, for each $j \in \{1, \dots , 2k+1\}$, define the matrix
\[
	E_j := \left[\,(-1)^{s_{1+j}} \vec{e}_1 \,\,\vline\,\, (-1)^{s_{2+j}}\vec{e}_2 \,\,\vline\,\, \cdots \,\,\vline\, (-1)^{s_{2k+1+j}} \vec{e}_{2k+1}\,\right],
\]
where the subscripts are computed cyclically (i.e., $s_{2k+2} = s_1$, $s_{2k+3} = s_2$, etc.).

Then $\operatorname{sb}(\vec{e}_1, \dots , \vec{e}_{2k+1}) = k$ if and only if there exist $\vec{v} \in \mathbb{R}^3$ and $j \in \{1, \dots , 2k+1\}$ so that $\vec{v}^T E_j$ has all positive entries. Contrapositively, none of the linear systems $\vec{v}^T E_j > 0$ have solutions if and only if $\operatorname{sb}(\vec{e}_1, \dots , \vec{e}_{2k+1}) < k$. Stated in this way, the following corollary of \Cref{thm:Gordan} gives new bounds on the superbridge indices of polygonal curves with an odd number of edges.

\begin{corollary}\label{cor:Gordan2}
	Suppose $\vec{e}_1, \dots , \vec{e}_{2k+1}$ are the edge vectors of a closed polygonal curve in $\mathbb{R}^3$. Then the curve has superbridge number $<k$ if and only if there exist nonzero vectors $\vec{u}_1 , \dots , \vec{u}_{2k+1} \in \mathbb{R}^{2k+1}$ with nonnegative entries solving the matrix equations
	\begin{equation}\label{eq:odd gordan}
		E_j \vec{u}_j = \vec{0}
	\end{equation}
	for all $j=1, \dots , 2k+1$. If $U = \left[\, \vec{u}_1 \,\vline\, \cdots \,\vline\, \vec{u}_{2k+1}\,\right]$, the $(2k+1)\times(2k+1)$ matrix $U$ serves as a computable certificate of the superbridge number bound.
\end{corollary}

\Cref{cor:Gordan2} can now be used to determine the superbridge indices of the rest of the knots in \Cref{thm:main}.

	\begin{figure}[t]
		\centering
			\begin{tabular*}{0.75\textwidth}{C{2.2in} R{.4in} R{.4in} R{.4in}}
			\multicolumn{4}{c}{$9_{36}$} \\
			\cline{1-4}\noalign{\smallskip}
			\multirow{12}{*}{\includegraphics[height=1.8in,width=1.8in,keepaspectratio]{9_36.pdf}}
			& $0$ & $0$ & $0$ \\
			& $1000$ & $0$ & $0$ \\
			& $567$ & $902$ & $0$ \\
			& $-185$ & $294$ & $-256$ \\
			& $759$ & $245$ & $71$ \\
			& $318$ & $816$ & $764$ \\
			& $646$ & $-13$ & $311$ \\
			& $718$ & $908$ & $-72$ \\
			& $-183$ & $662$ & $285$ \\
			& $718$ & $517$ & $694$ \\
			& $406$ & $897$ & $-177$ \\
			\end{tabular*}
			 \[\begin{tiny}\begin{bmatrix}$1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ \
			& $1$ & $1$ & $1$ & $1$ \\
			$1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $12523027847$ & $1$ & $1$ & \
			$1$ \\
			$5426124359$ & $1$ & $1$ & $1$ & $1424202531$ & $1$ & $1$ & $1$ & $1$ \
			& $6584192388$ & $8992884808$ \\
			$1$ & $1$ & $1$ & $12223967$ & $1$ & $1$ & $263408915$ & \
			$29465794187$ & $9986903746$ & $1$ & $1$ \\
			$495044898$ & $5412091732$ & $100403683$ & $1$ & $3$ & $212199095$ & \
			$1$ & $1$ & $1$ & $1$ & $1$ \\
			$1$ & $1$ & $1$ & $3$ & $2159516409$ & $1$ & $65852229$ & $1$ & $1$ & \
			$6627781141$ & $1$ \\
			$1$ & $1$ & $38906659$ & $19412935$ & $1$ & $53049774$ & $39336205$ & \
			$1$ & $1$ & $1$ & $1$ \\
			$1125551611$ & $1735612295$ & $29180733$ & $858339$ & $1557767516$ & \
			$11511945$ & $88068805$ & $355250231$ & $6884251289$ & $36701288$ & \
			$398991934$ \\
			$1241803067$ & $3170128948$ & $69866228$ & $11625485$ & $267607237$ & \
			$79522441$ & $20150485$ & $2006088206$ & $2575693266$ & $1056878715$ \
			& $2505218830$ \\
			$45910998$ & $355246092$ & $26475285$ & $6280015$ & $89877512$ & \
			$374500950$ & $1677801$ & $145553542$ & $1448979271$ & $824513076$ & \
			$3204959462$ \\
			$3901711428$ & $1642348279$ & $12533499$ & $2078963$ & $40849202$ & \
			$426090556$ & $184771845$ & $27474391863$ & $3948141106$ & \
			$5211154861$ & $7748788486$\end{bmatrix}\end{tiny}\]
		\caption{Visualization of an 11-stick realization of $9_{36}$ with superbridge number $4$. The three columns to the right of the image give the coordinates of the vertices, and the matrix below is the $U$ whose columns are the~$\vec{u}_j$ satisfying~\eqref{eq:odd gordan}. The knot is shown in orthographic perspective, viewed from the direction of the positive $z$-axis.}
		\label{fig:9_36}
	\end{figure}

\begin{proposition}\label{prop:rest}
	The knots $9_3$, $9_4$, $9_6$, $9_9$, $9_{11}$, $9_{13}$, $9_{17}$, $9_{18}$, $9_{23}$, $9_{25}$, $9_{27}$, $9_{30}$, $9_{31}$, and $9_{36}$ have superbridge index equal to 4, and $\operatorname{sb}[12n_{66}] = \operatorname{sb}[12n_{225}] = 5$.
\end{proposition}

\begin{proof}
	Each of these knots has superbridge index $\geq 4$ by \Cref{thm:JeonJin}, so for the 9-crossing knots it suffices to find 11-stick realizations and certificate matrices $U$ showing they have superbridge number $\leq 4$, as in \Cref{cor:Gordan2}. $12n_{66}$ and $12n_{225}$ are both 4-bridge knots~\cite{blair_wirtinger_2020,knotinfo}, so their superbridge indices are $\geq 5$ and it suffices to find 13-stick realizations with corresponding $U$.

	These realizations and certificate matrices are given in \Cref{sec:coords}. The entry for $9_{36}$ is reproduced in \Cref{fig:9_36}. In each case, a visualization of the knot is shown next to the coordinates of the vertices, and the matrix $U$ is given below.
\end{proof}

\section{Conclusion}
\label{sec:conclusion}

One virtue of \Cref{cor:Gordan2} is that it provides examples of superbridge-minimizing polygonal knots which do not minimize stick number. Specifically, all of the 9-crossing knots mentioned in \Cref{prop:rest} except $9_6$, $9_{23}$, and $9_{36}$ are known to have stick number $\leq 10$~\cite{TomClay,rawdon_upper_2002,shonkwiler_all_2021}, but to my knowledge there are no 10-stick realizations of these knots with superbridge number 4. For example, in the course of this project I generated 1147 random 10-stick realizations of $9_{27}$ (out of more than 170 billion random 10-gons), none of which seem to have superbridge number equal to 4. This suggests the very plausible but still intriguing possibility that there may exist knots for which the stick number and superbridge index cannot be achieved by the same realization.

\begin{conjecture}
	There exists a knot type $K$ for which no polygonal realization achieves both $\operatorname{stick}[K]$ and $\operatorname{sb}[K]$.
\end{conjecture}

The algorithm used to generate large ensembles of random polygons for this project produces \emph{equilateral} polygons---that is, closed polygonal curves for which all edges are the same length. While I don't know of any evidence either way, it is conceivable that minimizing superbridge number is easier with heterogeneous edgelengths, so it might be worthwhile to perform similar investigations with non-equilateral random polygons.

\subsection*{Acknowledgments}
\label{sub:acknowledgments}

Thanks, as ever, to Allison Moore and Chuck Livingston for maintaining KnotInfo~\cite{knotinfo} and to Jason Cantarella and Tom Eddy for technical support. This work was partially supported by grants from the Simons Foundation (\#354225 and \#709150).


\section{Introduction} \label{secn:twoterminalsourcecoding}

Consider the two-terminal source coding setup in \fig{two_terminal_coding}, where the terminals operate the encoder-decoder pairs $(\cc{E}_1,\cc{D}_1)$ and $(\cc{E}_2,\cc{D}_2)$.
Let $\{X_{1,i},X_{2,i}\}_{i=1}^{\infty}$ be a sequence of independent and identically distributed (i.i.d.) pairs of random variables, and let $(X_1, X_2)$ have the same joint distribution as $(X_{1,i},X_{2,i})$.
We denote by $X_1^n$ and $X_2^n$ the first $n$ observations of $X_{1,i}$ and $X_{2,i}$.
The sequences $X_1^n$ and $X_2^n$ are observed separately at the two terminals (e.g., both/only $\cc{E}_1$ and $\cc{D}_1$ observe $X_1^n$).
The two encoders respectively use rates $R_1$ and $R_2$ to encode $X_1^n$ and $X_2^n$.
The decoders produce $\hat{Z}_1^n$ and $\hat{Z}_2^n$, two reconstructions of the sum $Z^n=X_1^n+X_2^n$, which satisfy ${\mathbb{E}}[d(Z^n,\hat{Z}_1^n)]\leq D$ and ${\mathbb{E}}[d(Z^n,\hat{Z}_2^n)]\leq D$ for some distortion measure $d(\cdot,\cdot)$ and $D\geq0$.
We obtain the ``Two-terminal Source Coding with Common Sum Reconstruction'' (CSR) problem by adding the constraint that with high probability $\hat{Z}_1^n$ and $\hat{Z}_2^n$ must be equal, i.e., both decoders must produce a Common Reconstruction (CR) of the sum $Z^n=X_1^n+X_2^n$.
The goal of this paper is presentation of inner and outer bounds to the achievable rates distortion region (to be defined formally later) in the CSR problem, consisting of achievable rates distortion triples $(R_1,R_2,D)$, when $(X_{1},X_{2})$ is a Doubly Symmetric Binary Source (DSBS) and $d(\cdot,\cdot)$ is Hamming distortion measure.
The summation in this case is modulo-two.

One may make the following two important observations about the CSR problem.
First, since $X_{1}$ and $X_{2}$ are correlated, the decoders may use $X_1^n$ and $X_2^n$ as side information at $\cc{D}_1$ and $\cc{D}_2$ respectively.
Due to the availability of decoder side information, the encoders can lower the required rates $R_1$ and $R_2$.
Second, decoders only need to reconstruct the sum $X_1^n+X_2^n$. The recovery of $X_1^n$ (at $\cc{D}_2$) and $X_2^n$ (at $\cc{D}_1$) is not needed.
Reconstructing the sum should not take a larger bit-rate than the rate required for reconstructing the individual sources.

\begin{figure}
\centering\includegraphics[width=0.8\columnwidth]{two_terminal_coding}
\caption{
The dashed line separates the two terminals.
The decoder outputs $\hat{Z}_1^n$ and $\hat{Z}_2^n$, two reconstructions of $Z^n=X_1^n+X_2^n$.
The CSR problem is obtained by adding the constraint that $\hat{Z}_1^n=\hat{Z}_2^n$ with high probability.
}
\label{fig:two_terminal_coding}
\vspace*{-0.063in}
\end{figure}

The CSR problem is motivated by its application to algorithms that require computation of the average of correlated random variables. Examples include distributed counterparts of Stochastic Gradient Descent (SGD), power iteration and Lloyd's ($k$-means) algorithm \cite{suresh2017distributed}.
In practice, algorithms such as butterfly all-reduce \cite{thakur2005optimization} facilitate the computation of averages over a large number of compute nodes.
For example, let the two terminals in \fig{two_terminal_coding} be two compute nodes optimizing some function with synchronous SGD, and let $X_1$ and $X_2$ be two (scalar) stochastic gradients of the function computed by the $i$th node.
Two stochastic gradients are correlated since they are noisy estimates of the gradient of the function.
In synchronous SGD, each compute node wants to update its optimizing variable using the average gradient $(X_1+X_2)/2$.
\fig{two_terminal_coding} presents a suitable communication setup for this two-terminal setting.
The butterfly all-reduce algorithm employs the two-terminal communication setup as a basic building block, and uses it recursively to extend the sum computation to an arbitrary number of compute nodes.
A similar mechanism can be employed for distributed counterparts of power iteration and Lloyd's algorithm as well. Both algorithms require mean computation, and depending on the underlying dataset, one may observe correlations in the vectors that participate in the mean computation.

The remainder of the paper is organized as follows.
In \secn{Definitionsandnotations} we formally define the CSR problem.
In \secn{innerboundsCSR}, we develop an inner bound to the achievable CSR rate distortion region by considering existing achievability results for Steinberg's CR problem \cite{steinberg2009coding}.
In \secn{achievabilityLKM} we develop a new achievability result for the ``lossy'' version of the K\"orner-Marton modulo-two sum problem \cite{korner1979encode}, and use this new achievability result to obtain another inner bound.
In \secn{outerboundsCSR} we develop an outer bound by considering Wyner-Ziv's problem of source coding with side information \cite{wyner1976rate}.
In \secn{comparebounds} we compare the inner bounds and the outer bound for different DSBS sources.
Finally, in \secn{conclusion} we present concluding remarks.

\section{Definitions and notations} \label{secn:Definitionsandnotations}

Since in this paper we focus on binary sources, we present the formal definition of the CSR problem for binary sources as follows. For a positive integer $N$, let $[N]$ denote the index set $\{1,\dots,N\}$, and let $\GF{2}$ denote the finite field of order $2$.
An $(n,N_1,N_2,D,\epsilon)$-CSR coding scheme consists of
two encoding functions
$\cc{E}_1:\GF{2}^n\to[N_1]$ and
$\cc{E}_2:\GF{2}^n\to[N_2]$,
and two decoding functions
$\cc{D}_1:\GF{2}^n\times[N_2]\to\GF{2}^n$ and
$\cc{D}_2:\GF{2}^n\times[N_1]\to\GF{2}^n$,
such that for
$\hat{Z}_1^n = \cc{D}_1(X_1^n, \cc{E}_2(X_2^n))$,
$\hat{Z}_2^n = \cc{D}_2(X_2^n, \cc{E}_1(X_1^n))$ and
$Z^n=X_1^n+X_2^n$,
we have
${\mathbb{E}}[d(Z^n,\hat{Z}_1^n)]\leq D$ and
${\mathbb{E}}[d(Z^n,\hat{Z}_2^n)]\leq D$,
and $\Pr(\hat{Z}_1^n\neq\hat{Z}_2^n)\leq\epsilon$,
where $d(\cdot,\cdot)$ is the Hamming distortion measure.
A specific CSR coding scheme is denoted by the four mappings $(\cc{E}_1, \cc{E}_2, \cc{D}_1, \cc{D}_2)$.

A scalar triple $(R_1, R_2, D)$ is called CSR-achievable if for every $\epsilon>0$ and $n$
sufficiently large there exists an $(n,2^{n(R_1+\epsilon)},2^{n(R_2+\epsilon)},D,\epsilon)$-CSR coding scheme.
We denote by $\RR{CSR}\subset\mathbb{R}^3$ the set of all CSR-achievable triples.

A source $(X,Y)$ is a DSBS$(p)$ if $X$ and $Y$ are binary sources that satisfy
$\Pr(X=0,Y=0)=\Pr(X=1,Y=1)=(1-p)/2$ and $\Pr(X=0,Y=1)=\Pr(X=1,Y=0)=p/2$
for some $0\leq p\leq\frac{1}{2}$.
We denote the binary entropy function by $H_b(\cdot)$, i.e., $H_b(p)=-p\log_2 p - (1-p)\log_2 (1-p)$,
and the binary convolution operator by $*$, i.e., $p*q = p(1-q)+(1-p)q$.

\section{Inner bound with Steinberg's CR problem} \label{secn:innerboundsCSR}

\begin{figure}
	\centering\includegraphics[width=0.68\columnwidth]{rate_dist_side_info}\\~\\
	\caption{

		Steinberg's CR problem.
	}
	\label{fig:rate_dist_side_info}
\end{figure}

A set $\RR{}\subset\mathbb{R}^3$ provides an inner bound to $\RR{CSR}$ if $\RR{}\subseteq\RR{CSR}$.
An inner bound to $\RR{CSR}$ can easily be obtained by considering Steinberg's CR problem \cite{steinberg2009coding} presented in \fig{rate_dist_side_info}.
Steinberg's problem adds one constraint to the problem of source coding with side information considered by Wyner and Ziv in \cite{wyner1976rate}. The constraint is that with high probability the encoder is able to reconstruct the decoder output.
In \fig{rate_dist_side_info}, the function triple $(\cc{E},\cc{D},\psi)$ constitutes a CR code, where
$\cc{E}$ encodes $X^n$ with rate $R$,
and $\cc{D}$ reconstructs $X^n$ as $\hat{X}^n$ with the help of side information $Y^n$,
such that ${\mathbb{E}}[d(X^n,\hat{X}^n)]\leq D$ and $\psi(X^n)=\hat{X}^n$ with high probability.
The last constraint
limits the decoder's ability to exploit fully the side information $Y^n$, since $Y^n$ is not available at the encoder.
Other variants of Steinberg's problem have also been considered.
For example, in \cite{lapidoth2014constrained} the authors generalize Steinberg's CR problem to allow the encoder and decoder reconstructions to be different within some fidelity constraint,
and in \cite{lu2016binary} the authors consider an encoder that observes side information that is different from the side information available to the decoder.

\begin{figure}
\centering
\includegraphics[width=0.9\columnwidth]{two_steinberg_systems}
\caption{Application of Steinberg's CR problem to CSR.}
\label{fig:two_steinberg_systems}
\end{figure}

For a DSBS$(p)$ source $(X,Y)$, the rate distortion function for Steinberg's problem in \fig{rate_dist_side_info} is given by $\Rate{CR}(D)$ where $\Rate{CR}(D) = H_b(p*D) - H_b(D)$ for $0\leq D\leq\frac{1}{2}$ and $\Rate{CR}(D) = 0$ for $\frac{1}{2}\leq D$.
We refer the reader to \cite{steinberg2009coding} for more details.
An inner bound to $\RR{CSR}$ can be obtained by considering two CR codes as we summarize next.
\begin{prop} \label{prop:propositionSteinberg}
Let $(X_{1},X_{2})$ be a DSBS$(p)$ with $0\leq p\leq\frac{1}{2}$,
\begin{equation}\label{eqn:Ronesteinberg}
\RR{A} = \left\{ (R_1,R_2,D)\ \middle\vert \begin{array}{l}
0\leq D_1,D_2\leq\frac{1}{2}, \\
R_1\geq\Rate{CR}(D_1), \\
R_2\geq\Rate{CR}(D_2), \\
D\geq D_1*D_2
\end{array}\right\},
\end{equation}
and
\begin{equation}\label{eqn:Rtwosteinberg}
\RR{B} = \{ (R_1,R_2,D) \mid R_1\geq0, R_2\geq0, D\geq p \}.
\end{equation}
Then, the convex hull $\text{conv}(\RR{A}\cup\RR{B})$,
is a subset of $\RR{CSR}$
and provides an inner bound to $\RR{CSR}$.
\comment{
\begin{equation}\label{eqn:Rsteinberg}
\RR{} = \left\{ (R_1,R_2,D)\ \middle\vert \begin{array}{l}
R_1\geq0, R_2\geq0, 0\leq\theta\leq1 \\
(a_1, a_2,\alpha)\in\RR{A}, \\
(b_1, b_2,\beta)\in\RR{B}, \\
R_1 = \theta a_1 + (1-\theta)b_1, \\
R_2 = \theta a_2 + (1-\theta)b_2, \\
D\geq \argmin \theta \alpha + (1-\theta)\beta
\end{array}\right\},
\end{equation}
}
\end{prop}
The proof of Proposition~\ref{prop:propositionSteinberg} can be sketched as follows.
First, note that the triples in $\RR{B}$ are CSR-achievable, since for $D\geq p$, the decoders can deterministically set $\hat{Z}_1^n=\hat{Z}_2^n=0$, requiring zero rates for $R_1$ and $R_2$.
Second, we show later that all triples in $\RR{A}$ are also CSR-achievable.
Then, any triple in $\text{conv}(\RR{A}\cup\RR{B})$ is CSR-achievable by time-sharing between triples in $\RR{A}$ and $\RR{B}$.
To see that all triples in $\RR{A}$ are CSR-achievable, let $(\cc{E}_1,\cc{D}_2,\psi_1)$ and $(\cc{E}_2,\cc{D}_1,\psi_2)$ be two independent CR codes
such that ${\mathbb{E}}[d(X_1^n,\hat{X}_1^n)]\leq D_1$ and ${\mathbb{E}}[d(X_2^n,\hat{X}_2^n)]\leq D_2$.
Let the two codes be applied to the CSR setup as shown in \fig{two_steinberg_systems}.
Due to the use of the two CR codes we have $\hat{Z}_1^n=\hat{Z}_2^n$ with high probability.
Since the two CR codes are selected independently, and due to the Markov chain $\hat{X}_1\--(X_1,X_2)\--\hat{X}_2$,
the quantization errors $X_1+\hat{X}_1$ and $X_2+\hat{X}_2$ are independent of each other,
and ${\mathbb{E}}[X_1+X_2 + \hat{X}_1 + \hat{X}_2]\leq D_1*D_2$.
Therefore,
${\mathbb{E}}[d(Z^n,\hat{Z}_1^n)] \leq D_1*D_2 + \delta$
\comment{
Letting $\text{wt}(\cdot)$ denote the Hamming weight of the input and by using the triangle inequality we have
\begin{align}
n{\mathbb{E}}[d(Z^n,\hat{Z}_1^n)]
&= {\mathbb{E}}[\text{wt}(X_1^n+X_2^n + \psi(X_1^n) + \hat{X}_2^n)] \\
&= {\mathbb{E}}[\text{wt}(X_1^n+\psi_1(X_1^n)) + \text{wt}(X_2^n+\hat{X}_2^n)] \\
&\leq nD_1+nD_2 + n\delta,
\end{align}}
where $\delta$ is due to the event that $\psi_1(X_1^n)\neq\hat{X}_1^n$,
and $\delta$ can be made arbitrarily small with the choice of $(\cc{E}_1,\cc{D}_2,\psi_1)$.
A similar sequence of arguments apply to ${\mathbb{E}}[d(Z^n,\hat{Z}_2^n)]$.
This completes the sketch of the proof of Proposition~\ref{prop:propositionSteinberg}.
Note that the decoders reconstruct individual sources, and the decoders do not exploit the fact that only the sum of the sources has to be reconstructed.
Therefore, $\RR{A}$ and $\text{conv}(\RR{A}\cup\RR{B})$ provide only inner bounds to $\RR{CSR}$.

\section{Inner bound with Lossy K\"orner-Marton (LKM) problem} \label{secn:achievabilityLKM}

\begin{figure}
	\centering\includegraphics[width=0.655\columnwidth]{korner_marton}\\~\\
	\caption{Lossy K\"orner-Marton problem. The decoder reconstructs $Z^n=X^n+Y^n$ as $\hat{Z}^n$ under some fidelity criterion.}
	\label{fig:korner_marton}
\end{figure}

Another inner bound to $\RR{CSR}$ can be obtained by considering the Lossy K\"orner-Marton (LKM) problem presented in \fig{korner_marton}.
In the LKM problem, the decoder wishes to reconstruct the sum $Z^n=X^n+Y^n$ as $\hat{Z}^n$ under some fidelity criterion.
The LKM problem is a generalization of the (lossless) K\"orner-Marton problem~\cite{korner1979encode}.
When $(X,Y)$ is a DSBS$(p)$ and $d(\cdot,\cdot)$ is Hamming distance, the authors of \cite{korner1979encode} exploit the linearity of the sum modulo-two computation $Z^n=X^n+Y^n$ and demonstrate that with high probability the decoder can reconstruct $Z^n$ (losslessly) if and only if $R_1\geqH_b(p)$ and $R_2\geqH_b(p)$.
In more recent work, the authors of \cite{sefidgaran2015korner} develop inner and outer bounds to the set of achievable rate pairs $(R_1,R_2)$ in the lossless case when $(X,Y)$ is an asymmetric binary source. The authors of \cite{nair2020optimal} show that the result in \cite{korner1979encode} applies to larger class of binary distributions.

\begin{figure}
	\centering\includegraphics[width=0.845\columnwidth]{two_terminal_korner_marton}\\~\\
	\caption{Application of LKM problem to CSR.}
	\label{fig:two_terminal_korner_marton}
	\vspace*{-0.1in}
\end{figure}

The LKM problem can be formally defined as follows.
An $(n,N_1,N_2,D)$-LKM coding scheme consists of
two encoding functions $\cc{E}_1:\GF{2}^n\to[N_1]$ and $\cc{E}_2:\GF{2}^n\to[N_2]$,
and a decoding function $\cc{D}:[N_1]\times[N_2]\to\GF{2}^n$,
such that for $Z^n=X^n+Y^n$ and $\hat{Z}^n = \cc{D}(\cc{E}_1(X^n), \cc{E}_2(Y^n))$
we have ${\mathbb{E}}[d(Z^n,\hat{Z}^n)]\leq D$, where $d(\cdot,\cdot)$ is Hamming distortion.
A specific LKM coding scheme is denoted by the three mappings $(\cc{E}_1, \cc{E}_2, \cc{D})$.
A scalar triple $(R_1, R_2, D)$ is called LKM-achievable if for every $\epsilon>0$ and sufficiently large $n$ there exists an $(n,2^{n(R_1+\epsilon)},2^{n(R_2+\epsilon)},D)$-LKM coding scheme.

\fig{two_terminal_korner_marton} shows how the LKM coding scheme can be applied to obtain an inner bound to the CSR problem.
The two decoders in \fig{two_terminal_korner_marton} are identical and they are located at the two terminals.
With \fig{two_terminal_korner_marton} we observe that every triple in $\RR{LKM}$ is CSR-achievable, i.e., $\RR{LKM}\subseteq\RR{CSR}$.
Note that $\RR{LKM}$ provides only an inner bound to $\RR{CSR}$ since the decoders in \fig{two_terminal_korner_marton} do not exploit the fact that at least one of the sources is available to each decoder with full fidelity.
For example, in CSR $\cc{D}_1$ has access to $X_1^n$ (cf. \fig{two_terminal_coding}),
although in \fig{two_terminal_korner_marton} $\cc{D}_1$ observes $X_1^n$ only with a rate $R_1$.

To the best of our knowledge, a tight bound for $\RR{LKM}$, i.e., \emph{lossy} K\"orner-Marton problem, has not yet been proposed.
In \cite{krithivasan2009lattices, wagner2010distributed, yang2014distributed} the authors obtain inner bounds to $\RR{LKM}$ for Gaussian sources under squared distortion, and the bounds have been shown to be tight for some special cases.
The authors of \cite{lim2019towards} present an inner bound for a generalized version of the LKM problem setup that includes an arbitrary number of linear combinations of the sources. The authors employ joint typicality-based encoding and decoding functions to obtain the inner bound. In contrast, in this paper we employ minimum distance-based encoding and decoding functions. The authors of \cite{lim2019towards} do not evaluate the inner bound for the special case of the binary-Hamming LKM problem.

We consider the LKM problem for the special case of binary sources.
In \secn{proposedcoding} we propose an LKM coding scheme,
and in \secn{achievabilityofproposed} we characterize the achievable rate distortion region in the proposed scheme, assuming $(X,Y)$ is a DSBS$(p)$. As a corollary we obtain an inner bound to $\RR{CSR}$.

\subsection{Proposed coding scheme} \label{secn:proposedcoding}
The proposed scheme is defined by two matrices $A\in\GF{2}^{m\times n}$ and $B\in\GF{2}^{r\times n}$.
For a column vector $z^n\in\GF{2}^n$, let $A z^n$ and $B z^n$ be the products
of the matrices with $z^n$ in $\GF{2}$.
Let
\[\cc{C}=\{ z^n\in\GF{2}^n \mid A z^n=\mathbf{0} \},\]
where
$\mathbf{0}$ is the all-zeros column vector of length-$m$, and let
\[Q(x^n) = \argmin_{z^n\in\cc{C}} \text{wt}(x^n+z^n),\]
where $x^n+z^n$ is the element-wise sum in $\GF{2}$ and
$\text{wt}(\cdot)$ is the Hamming weight of the input.
Since $Q(\cdot)$ searches for the element in $\cc{C}$ closest to the input,
we refer to $Q(\cdot)$ as the quantizing function
and to $\cc{C}$ as the quantizing codebook.
Let
$f:\GF{2}^n\to\GF{2}^r$ and
$g:\GF{2}^r\times\GF{2}^r\times\GF{2}^m\to\GF{2}^n$ be defined as
$f(x^n) =
BQ(x^n)$,
i.e., composition of $B$ with $Q$,
and
\begin{equation} \label{eqn:decoderfunc}
\begin{aligned}
g(x^r, y^r,s^m) =
\argmin_{z^n\in\GF{2}^n} \quad &
\text{wt}(z^n) \\
\textrm{s.t.}
\quad\quad & A z^n=s^m, ~Bz^n = x^r+y^r.
\end{aligned}
\end{equation}
In the proposed scheme, the function $f$ is used by the encoders and $g$ by the decoder.
In comparison to the encoder in \cite{korner1979encode}, $f$ consists of an additional quantization step that employs the linear codebook $\cc{C}$.
The linearity of the codebook dovetails with the linear structure of the sum computation, thereby making a rate reduction possible, as we will see in \secn{achievabilityofproposed}.
\comment{The two encoding functions as
$\cc{E}_1(x^n)\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily def}}}{=}}(B\circQ)(x^n)$ and
$\cc{E}_2(y^n)\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily def}}}{=}}(B\circQ)(y^n)$,
where $\circ$ is the composition of the two functions.
}

\subsection{Achievability of the proposed coding scheme} \label{secn:achievabilityofproposed}
The proposed scheme can be used to show the achievability of the rate region summarized in Proposition~\ref{prop:propositionLKM}.
\begin{prop} \label{prop:propositionLKM}
Let $(X, Y)$ be a DSBS$(p)$ with $0\leq p\leq\frac{1}{2}$, and
$
\RR{LKM} = \{ (R_1,R_2,D) \mid  R_1, R_2\geq H_b(p*q*q)-H_b(q), D\geq q*q, 0\leq q\leq \frac{1}{2} \}.
$
For every scalar triple $(R_1, R_2, D)\in\RR{LKM}$, there exist a pair of matrices $(A, B)$ (as defined in \secn{proposedcoding}) such that the triple is LKM-achievable with the coding scheme $(\cc{E}_1, \cc{E}_2, \cc{D})$ in \secn{proposedcoding}.

Furthermore, the convex hull $\text{conv}(\RR{LKM}\cup\RR{B})$, where $\RR{B}$ is as defined in Proposition~\ref{prop:propositionSteinberg}, is a subset of $\RR{CSR}$ and provides an inner bound to $\RR{CSR}$.
\end{prop}

The proof of Proposition~\ref{prop:propositionLKM} can be sketched as follows.
Let $A$ be the ${m\times n}$ parity check matrix of a `good' linear rate distortion code for a uniform source that incurs average distortion $q$.
Such a source code will have $m\approx nH_b(q)$ \cite[Theorem 4]{goblick1963coding, berger1975advances}.
Let $D_X^n\in\GF{2}^n$ and $D_Y^n\in\GF{2}^n$ be two length-$n$ dither sequences sampled independently from the i.i.d. Bernoulli($\frac{1}{2}$) distribution.
Both dither sequences are also known to the decoder.
The encoders respectively compute, and send to the decoder, $f(X^n+D_X^n)$ and $f(Y^n+D_Y^n)$.
Let $\hat{X}^n=Q(X^n+D_X^n)$ and $\hat{Y}^n=Q(Y^n+D_Y^n)$.
The encoders send $B\hat{X}^n$ and $B\hat{Y}^n$ to the decoder, each using $r$ bits (recall $B$ is an ${r\times n}$ matrix).
Let $W_X^n$ and $W_Y^n$ be the quantization errors of the two sequences, i.e., $W_X^n=\hat{X}^n+X^n+D_X^n$ and $W_Y^n=\hat{Y}^n+Y^n+D_Y^n$.
Adding dither prior to quantization makes $W_X^n$ and $W_Y^n$ independent.
To see that $W_X^n$ and $W_Y^n$ are not always independent without dither, consider the limiting case $p=0$.
In this case $X^n=Y^n$ and $W_X^n=Q(X^n)+X^n=Q(Y^n)+Y^n=W_Y^n$ with probability $1$.
Adding dither makes the two quantizer inputs $X^n+D_X^n$ and $Y^n+D_Y^n$ independent,
which is important to making $W_X^n$ and $W_Y^n$ independent and obtaining the rate expression in Proposition~\ref{prop:propositionLKM}.

The decoder knows $B\hat{X}^n$, $B\hat{Y}^n$, $D_X^n$, $D_Y^n$ and computes
$B\hat{X}^n+B\hat{Y}^n+B D_X^n+B D_Y^n =
B\hat{Z}^n$, where $\hat{Z}=\hat{X}^n+\hat{Y}^n+D_X^n+D_Y^n$.
Observing that we can reexpress $\hat{Z}$ as $\hat{Z}=X^n+W_X^n+Y^n+W_Y^n=Z^n+W_X^n+W_Y^n$,
and by observing that $Z^n,W_X^n,W_Y^n$ are jointly independent,
the marginal statistics of $\hat{Z}$ are Bernoulli($p*q*q$).
Similarly, ${\mathbb{E}}[d(Z,\hat{Z})]=q*q$.
Per Lemma in \cite{korner1979encode}, there exists a matrix $B$ such that $\hat{Z}$ can be recovered from $B\hat{Z}^n$ if $r>H_b(p*q*q)$.
However, this rate can be reduced if the decoder employs $D_X^n$ and $D_Y^n$ as side information.
Specifically, let $A\hat{Z}^n = A\hat{X}^n+A\hat{Y}^n+A D_X^n+A D_Y^n=A(D_X^n+D_Y^n)\mathrel{\overset{\makebox[0pt]{\mbox{\normalfont\tiny\sffamily def}}}{=}} S^m$,
where $S^m\in\GF{2}^m$.
The decoder computes $\tilde{Z}=g(B\hat{X}^n, B\hat{Y}^n, S^m)$.
Since there exist only around $2^{n(1-H_b(q))}$ length-$n$ sequences that satisfy $A\hat{Z}^n=S^m$,
we only require that $r>H_b(p*q*q)-H_b(q)$ to obtain $\tilde{Z}=\hat{Z}$ with high probability.
Therefore, we conclude that all triples in $\RR{LKM}$ are LKM-achievable.

By following the time-sharing argument as in Proposition~\ref{prop:propositionSteinberg}, we have that all triples in $\text{conv}(\RR{LKM}\cup\RR{B})$ are CSR-achievable, showing that $\text{conv}(\RR{LKM}\cup\RR{B})$ is a subset of $\RR{CSR}$.
One may observe that a similar time-sharing argument is used in \cite{wyner1976rate} when obtaining the rate distortion function of a binary source with decoder side information.

\section{Outer bound with Wyner-Ziv problem} \label{secn:outerboundsCSR}

A set $\RR{}\subset\mathbb{R}^3$ provides an outer bound to $\RR{CSR}$ if $\RR{CSR}\subseteq\RR{}$.
An outer bound to $\RR{CSR}$ can be obtained by waiving the CR constraint in the CSR problem.
Specifically, reconsider the problem setup in \fig{two_terminal_coding} without the CR constraint.
We refer to this new problem as the ``Two-terminal Sum Estimation'' (TSE) problem.
Let the achievable rate distortion region for TSE problem be $\RR{TSE}\subset\mathbb{R}^3$, with $\RR{TSE}$ consisting of the triples $(R_1,R_2,D)$ that produce the decoder outputs that satisfy ${\mathbb{E}}[d(Z^n,\hat{Z}_1^n)]\leq D$ and ${\mathbb{E}}[d(Z^n,\hat{Z}_2^n)]\leq D$.
Due to the waiving of the CR constraint we have that $\RR{CSR}\subseteq\RR{TSE}$.

When $X_1$ and $X_2$ take values in $\GF{2}$ and $d(\cdot,\cdot)$ is Hamming distance, one can characterize $\RR{TSE}$ by considering two parallel source coding with side information problems, i.e., two Wyner-Ziv (WZ) systems \cite{wyner1976rate}.
With reference to \fig{two_terminal_coding}, the first WZ system is from $\cc{E}_1$ to $\cc{D}_2$ and the second WZ system is from $\cc{E}_2$ to $\cc{D}_1$.
In the first system, $\cc{E}_1$ encodes $X_1^n$ and sends to $\cc{D}_2$ with a rate $R_1$.
Decoder $\cc{D}_2$ uses $X_2^n$ as side information to reconstruct $X_1^n$ as $\hat{X}_1^n$, and $\cc{D}_2$ outputs $\hat{Z}_2^n=\hat{X}_1^n+X_2^n$.
The second WZ system works in a similar manner with $\cc{E}_2$ using a rate $R_2$ to send to $\cc{D}_1$, and $\cc{D}_1$ outputting $\hat{Z}_1^n=X_1^n+\hat{X}_2^n$.

Let $g(D) = H_b(p*D) - H_b(D)$ if $0\leq D<p$ and $g(D) = 0$ if $p\leq D$.
Let $\Rate{WZ}(D)$ be
the minimum rate required by the WZ scheme for decoder $\cc{D}_j$, $j\in\{1,2\}$, to produce $\hat{Z}_j$, satisfying ${\mathbb{E}}[d(Z,\hat{Z}_j)]\leq D$.
In \cite{wyner1976rate}, the authors show that $\Rate{WZ}(D) = \text{l.c.e}(g(D))$,
the lower convex envelope of $g(D)$ (see Sec.~II-A \cite{wyner1976rate} and Example~1 in \cite{steinberg2009coding}).

Note that when using the WZ scheme the decoders do not exploit the fact that only the sum of the sources, $Z=X_1+X_2$, needs to be reconstructed.
Although, this may make one think that the WZ scheme does not provide a tight bound for $\RR{TSE}$. This is not the case as we will see next.
For example, considering $\cc{D}_1$, it can be shown that there exists no scheme which with it is possible for $\cc{D}_1$ to obtain an reconstruction of $Z$, say $\tilde{Z}_1\in\GF{2}$, with a rate $\Rate{WZ}(D)$, such that ${\mathbb{E}}[d(Z,\tilde{Z}_1)]\leq D'<D$.
To see this, assume there exists such a scheme.
Then,
$d(X_2,(X_1+\tilde{Z}_1))
= d(X_2+X_1+\tilde{Z}_1)
= d(Z,\tilde{Z}_1)
$,
which yields
${\mathbb{E}}[d(X_2,(X_1+\tilde{Z}_1))]\leq D'<D$.
This result contradicts the WZ converse, since such a result would imply that $(X_1+\tilde{Z}_1)$, which can be computed at $\cc{D}_1$, is a better reconstruction of $X_2$ that can be obtained with rate $\Rate{WZ}(D)$.
A similar sequence of arguments is applicable to the reconstruction of $\hat{Z}_2$ at $\cc{D}_2$ as well.
Therefore, the two WZ systems can be used to obtain a tight characterization of $\RR{TSE}$ when $X_1$ and $X_2$ are in $\GF{2}$, and $d(\cdot,\cdot)$ is Hamming distance.

\iffalse
python plot_rate_dist_CR.py --probs 0.4 --plot inner conjecture outer --save --title inner_outer_bounds_0.4 --ax_size 5 3.2 1.1 --hidex
python plot_rate_dist_CR.py --probs 0.2 --plot inner conjecture outer --save --title inner_outer_bounds_0.2 --ax_size 5 3.55 1.1 --hide_legend

--data_dir "C:\Users\Tharindu\OneDrive - University of Toronto\graduate\publications\2022_grads_inter-worker\latex_src\figures"
--hide_details
\fi
\begin{figure}[h]
	\centering\includegraphics[width=.48\textwidth]{inner_outer_bounds_0.4}
	~\\ \vspace{-0.7em}
	\centering\includegraphics[width=.473\textwidth]{inner_outer_bounds_0.2}
	\caption{Inner and outer bounds for a DSBS$(p)$ source when $R_1=R_2$ with $p=0.4$ (top) and $p=0.2$ (bottom).
	}
	\label{fig:inner_outer_bounds}
\end{figure}

The outer bound to $\RR{CSR}$ can be summarized as follows.
\begin{prop} \label{prop:propositionWZ}
Let $(X_1, X_2)$ be a DSBS$(p)$ with $0\leq p\leq\frac{1}{2}$.
Then,

\RR{TSE} = \{ (R_1,R_2,D) \mid  R_1, R_2\geq\Rate{WZ}(D), D\geq0 \},

and since $\RR{CSR}\subseteq\RR{TSE}$, $\RR{TSE}$ is an outer bound to $\RR{CSR}$.
\end{prop}
The characterization of $\RR{TSE}$ in Proposition~\ref{prop:propositionWZ} directly follows from the results in \cite{wyner1976rate}.
In general, it can be shown that the two WZ systems can be used to characterize $\RR{TSE}$ as long as the distortion measure takes the form $d(a, \lambda(b,c))=d(a+b,c)$ for some function $\lambda$. Both Hamming (for binary inputs) and squared distortion measures are of this form.

\comment{
	Then, from \eqn{distMeasureForm},
	$d(X_2,\lambda(X_1,\tilde{Z}_1))
	= d(X_2+X_1,\tilde{Z}_1)
	= d(Z,\tilde{Z}_1)$,
}

\section{Numerical comparison of bounds} \label{secn:comparebounds}

\fig{inner_outer_bounds} illustrates the inner and outer bounds (solid lines) in Propositions
\ref{prop:propositionSteinberg}, \ref{prop:propositionLKM} and \ref{prop:propositionWZ},
for the special case $R_1=R_2$ when $(X_1,X_2)$ is a DSBS$(p)$.
Let $G(q)=H_b(p*q)-H_b(q)$ as defined in \cite{wyner1976rate} and \cite{steinberg2009coding}.
Non-solid lines in the three cases correspond to $G(q)$ plotted against $q*q$,
$H_b(p*q*q)-H_b(q)$ plotted against $q*q$, and $G(q)$ plotted against $q$, respectively.
In each case the straight portion of the solid line (i.e., the large $D$ portion) is tangent to the corresponding non-solid line. This results from time-sharing with the zero-sum-rate point. The inner and outer bounds get tighter as $p$ decreases (e.g., the bounds are tighter in right-hand figure compared to the left-hand figure).

Recall that an optimal scheme for the CSR problem will
(1) exploit fully the sources observed at each terminal as side information when reconstructing the sum, and
will (2) exploit the fact that only the sum of the sources needs to be reconstructed.
Out of the two requirements, only (1) applies to the inner bound obtained with Steinberg's problem,
and only (2) applies to the inner bound obtained with LKM problem.
We observe in the figures that the inner bound with Steinberg's problem gives a slightly tighter bound than that with LKM problem (i.e., the red plots are slightly below the green plots).

\section{Conclusion} \label{secn:conclusion}
In this paper we present the problem of two-terminal source coding with Common Sum Reconstruction (CSR),
in which two terminals want to reconstruct separately the sum of two correlated sources under the constraint that the two reconstructions must be identical with high probability.
In practice, the CSR problem setup can be observed in algorithms such as butterfly all-reduce \cite{thakur2005optimization}.
We develop two inner and outer bounds to the achievable rate distortion region of the CSR problem for a doubly symmetric binary source.
Specifically, we develop two inner bounds using the achievability results for Steinberg's common reconstruction and lossy version of K\"orner-Marton's modulo-two sum computation problems.
We develop an outer bound using Wyner-Ziv's source coding with side information problem.

\section*{Acknowledgment}
The authors would like to thank Maxim Goukhshtein of University of Toronto, and Jason Lam and Zhenhua Hu of Huawei Technologies Canada for technical discussions.

\bibliographystyle{unsrt}


\section{Introduction}

The fundamental disadvantage inherent to any (semi-) relativistically
consistent description of some quantum-theoretic system is obviously brought
about by the nonlocality of the ``square-root'' operator of the
relativistically correct kinetic energy, $\sqrt{{\bf p}^2 + m^2}$,
entering necessarily in the Hamiltonian $H$ which governs the dynamics of the
system under consideration. In contrast to the nonrelativistic limit,
obtained from the expansion of the square root up to the lowest ${\bf
p}^2$-dependent order, $\sqrt{{\bf p}^2 + m^2} = m + {\bf
p}^2/(2\,m) + \dots$, the presence of the relativistic kinetic-energy
operator prevents, in general, a thoroughly analytic discussion; one is
forced to rely on some numerical solution of the problem.

This inconvenience may be circumvented---at least in principle---by
approximating a given semi-relativistic Hamiltonian $H$ (incorporating, by
definition, relativistic kinematics) by the corresponding ``effectively
semi-relativistic'' Hamiltonian, formulated and investigated according to the
lines proposed in the present work. These effective Hamiltonians are
characterized by their rigorous maintenance of the easier-to-handle
nonrelativistic kinematics while resembling the relativistic formalisms to
the utmost possible extent by replacing their intrinsic parameters by
effective ones which depend in a well-defined manner on the square of the
relevant momentum ${\bf p}$.

In order to be as concrete as possible, we choose to illustrate our route of
constructing and evaluating these effectively semi-relativistic Hamiltonians
for the particular case of bound states of two particles of spin zero. For
simplicity, let us assume that the two constituents of these bound states are
of equal mass $m$; the generalization to different masses is then
straightforward. In the framework of a semi-relativistic description all the
forces acting between these two particles may be derivable from some
coordinate-dependent interaction potential $V({\bf x})$. Consequently, the
semi-relativistic Hamiltonian describing this system in the
center-of-momentum frame of its constituents is given by
\begin{equation}
H = 2\sqrt{{\bf p}^2 + m^2} + V({\bf x})\ .
\label{eq:hsemi-rel}
\end{equation}

The equation of motion resulting from this type of Hamiltonian is usually
called ``spinless Salpeter equation.'' As it stands, it represents a
standard approximation to the Bethe--Salpeter formalism for bound states
within some relativistic quantum field theory. It may be derived from the
Bethe--Salpeter equation \cite{salpeter51}
\begin{enumerate}
\item by eliminating---in accordance with the spirit of an instantaneous
interaction---any dependence on timelike variables, which leads to the
so-called ``Salpeter equation'' \cite{salpeter52}, and
\item by neglecting any reference to the spin degrees of freedom of the two
involved bound-state constituents and restricting to solutions corresponding
exclusively to positive energy.
\end{enumerate}

The outline of this paper is as follows. We introduce, in
Sect.~\ref{sec:effsemrelham}, the effectively semi-relativistic Hamiltonians
corresponding to the really semi-relativistic Hamiltonians $H$ of
Eq.~(\ref{eq:hsemi-rel}) in their most general form. In
Sect.~\ref{sec:genstrat}, we derive, for the special case of power-law
potentials, some sort of ``master equation'' for that central quantity the
knowledge of which enables us to imitate the effects of relativistic
kinematics within a formally nonrelativistic framework, namely, the
expectation value of the square of the momentum ${\bf p}$. From the
consideration of the most important prototypes of interaction potentials in
Sect.~\ref{sec:effhamappl}, we are led to conclude, in
Sect.~\ref{sec:effhamconcl}, that our effective Hamiltonians represent indeed
a viable alternative to the original semi-relativistic Hamiltonians
(\ref{eq:hsemi-rel}).

\section{Effectively Semi-Relativistic Hamiltonians}\label{sec:effsemrelham}

The main idea of our way of constructing effectively semi-relativistic
Hamiltonians has already been sketched in Refs.~\cite{lucha91,lucha92}. (For
a brief account of this procedure see also Ref.~\cite{lucha94como}.)

The starting point of this construction is a trivial but nevertheless
fundamental inequality. This inequality relates the expectation values of
both the first and second powers of any Hermitian (or, to be more precise,
self-adjoint) but otherwise arbitrary operator ${\cal O} = {\cal O}^\dagger$,
taken with respect to (at this stage) arbitrary Hilbert-space vectors
$|\rangle$ (in the domain of ${\cal O}$) normalized to unity; it reads
$$
|\langle{\cal O}\rangle| \le \sqrt{\langle{\cal O}^2\rangle}\ .
\label{eq:ineqop}
$$
Application of the above inequality to the relativistic kinetic-energy
operator $\sqrt{{\bf p}^2 + m^2}$ yields
$$
\left\langle\sqrt{{\bf p}^2 + m^2}\right\rangle
\le \sqrt{\langle{\bf p}^2\rangle + m^2}\ .
$$
By employing this inequality, we obtain for an arbitrary expectation value
$\langle H\rangle$ of the semi-relativistic Hamiltonian $H$,
Eq.~(\ref{eq:hsemi-rel}),
\begin{eqnarray}
\langle H\rangle
&=& 2\left\langle\sqrt{{\bf p}^2 + m^2}\right\rangle + \langle V\rangle
\nonumber\\
&\le& 2\,\sqrt{\langle{\bf p}^2\rangle + m^2} + \langle V\rangle \nonumber\\
&=& 2\,\frac{\langle{\bf p}^2\rangle + m^2}
{\sqrt{\langle{\bf p}^2\rangle + m^2}} + \langle V\rangle \nonumber\\
&=& \left\langle 2\,\frac{{\bf p}^2 + m^2}
{\sqrt{\langle{\bf p}^2\rangle + m^2}} + V\right\rangle\ .
\label{eq:hamexpectval}
\end{eqnarray}

{}From now on we specify the Hilbert-space vectors in all expectation values to
be the eigenstates of our Hamiltonian $H$. In this case the expectation value
of $H$, $\langle H\rangle$, as appearing, e.~g., in (\ref{eq:hamexpectval}),
becomes the corresponding semi-relativistic energy eigenvalue $E$, i.~e.,
$$
E \equiv \langle H\rangle\ ,
$$
and the inequality (\ref{eq:hamexpectval}) tells us that this energy
eigenvalue is bounded from above by \cite{lucha91,lucha92}
$$
E \le \left\langle 2\,\frac{{\bf p}^2 + m^2}
{\sqrt{\langle{\bf p}^2\rangle + m^2}} + V\right\rangle\ .
$$
The operator within brackets on the right-hand side of this inequality may be
regarded as some ``effectively semi-relativistic'' Hamiltonian $H_{\rm eff}$
which possesses, quite formally, the structure of a nonrelativistic
Hamiltonian \cite{lucha91,lucha92},
\begin{eqnarray}
H_{\rm eff}
&\equiv& 2\,\frac{{\bf p}^2 + m^2}{\sqrt{\langle{\bf p}^2\rangle + m^2}} + V
\nonumber\\
&=& 2\,\hat m + \frac{{\bf p}^2}{\hat m} + V_{\rm eff}\ ,
\label{eq:heffective}
\end{eqnarray}
but involves, however, the effective mass \cite{lucha91,lucha92}
\begin{equation}
\hat m = \frac{1}{2}{\sqrt{\langle{\bf p}^2\rangle + m^2}}
\label{eq:meffective}
\end{equation}
and the effective nonrelativistic potential \cite{lucha91,lucha92}
\begin{eqnarray}
V_{\rm eff} &=& \frac{2\,m^2}{\sqrt{\langle{\bf p}^2\rangle + m^2}}
- \sqrt{\langle{\bf p}^2\rangle + m^2} + V \nonumber\\
&=& 2\,\hat m - \frac{\langle{\bf p}^2\rangle}{\hat m} + V\ .
\label{eq:poteffective}
\end{eqnarray}
The effective mass $\hat m$ as given by Eq.~(\ref{eq:meffective}) as well as
the constant, i.~e., coordinate-independent, term in the effective potential
$V_{\rm eff}$ of Eq.~(\ref{eq:poteffective}),
$$
2\,\hat m - \frac{\langle{\bf p}^2\rangle}{\hat m}\ ,
$$
quite obviously depend on the expectation value of the square of the momentum
${\bf p}$, that is, on $\langle{\bf p}^2\rangle$, and will therefore differ
for different energy eigenstates.

Motivated by our above considerations, we propose to approximate the true
energy eigenvalues $E$ of the semi-relativistic Hamiltonian $H$ of
Eq.~(\ref{eq:hsemi-rel}) by the corresponding ``effective'' energy
eigenvalues $E_{\rm eff}$, defined as the expectation values of some
effective Hamiltonian $\tilde H_{\rm eff}$ taken with respect to the
eigenstates $|\rangle_{\rm eff}$ of its own,
$$
E_{\rm eff} = \langle\tilde H_{\rm eff}\rangle_{\rm eff}\ ,
$$
where the effective Hamiltonian $\tilde H_{\rm eff}$, as far as its form is
concerned, is given by Eqs.~(\ref{eq:heffective}) to (\ref{eq:poteffective})
but is implicitly understood to involve the expectation values of ${\bf
p}^2$ with respect to the effective eigenstates $|\rangle_{\rm eff}$
(that is, $\langle{\bf p}^2\rangle_{\rm eff}$ in place of $\langle{\bf
p}^2\rangle$):
$$
\tilde H_{\rm eff} = 4\,\tilde m
+ \frac{{\bf p}^2 - \langle{\bf p}^2\rangle_{\rm eff}}{\tilde m} + V\ ,
$$
with
$$
\tilde m = \frac{1}{2}{\sqrt{\langle{\bf p}^2\rangle_{\rm eff} + m^2}}\ .
$$
Accordingly, the effective energy eigenvalues $E_{\rm eff}$ are given by a
rather simple formal expression, viz., by
\begin{equation}
E_{\rm eff} = 4\,\tilde m + \langle V\rangle_{\rm eff}\ .
\label{eq:effenergy}
\end{equation}

\section{General Strategy of Evaluation}\label{sec:genstrat}

We intend to elaborate our general prescription for the construction of
effectively semi-relativistic Hamiltonians $\tilde H_{\rm eff}$ in more
detail for the particular case of power-law potentials depending only on the
radial coordinate $r \equiv |{\bf x}|$, i.~e., for potentials of the form
$$
V(r) = a\,r^n
$$
with some constant $a$. The reason for this restriction is twofold:
\begin{enumerate}
\item On the one hand, for power-law potentials the most general virial
theorem \cite{lucha89,lucha90mpla} in its nonrelativistic form
\cite{lucha91,lucha92} appropriate for the present case,
$$
\left\langle\frac{{\bf p}^2}{\tilde m}\right\rangle_{\rm eff}
= \frac{1}{2}\left\langle r\,\frac{dV(r)}{dr}\right\rangle_{\rm eff}\ ,
\label{eq:virial}
$$
enables us to replace the expectation value of the potential in
(\ref{eq:effenergy}) immediately by a well-defined function of the
expectation value of the squared momentum:
$$
a\,\langle r^n\rangle_{\rm eff}
= \frac{2}{n}\,\frac{\langle{\bf p}^2\rangle_{\rm eff}}{\tilde m}\ .
$$
This implies for the effective energy eigenvalues
\begin{equation}
E_{\rm eff} = 4\,\tilde m + \frac{2}{n}\,
\frac{\langle{\bf p}^2\rangle_{\rm eff}}{\tilde m}\ .
\label{eq:eeff}
\end{equation}
\item On the other hand, we may take advantage of the fact that for power-law
potentials it is possible to pass, without change of the fundamental
commutation relations between coordinate variables and their canonically
conjugated momenta, from the dimensional phase-space variables employed at
present to new, dimensionless phase-space variables and to rewrite the
Hamiltonian in form of a Hamiltonian which involves only these dimensionless
phase-space variables \cite{lucha91}. The eigenvalues $\epsilon$ of this
dimensionless Hamiltonian are, of course, also dimensionless \cite{lucha91}.
Applying this procedure, we find for the effective energy eigenvalues
\begin{eqnarray*}
E_{\rm eff} - 4\,\tilde m
+ \frac{\langle {\bf p}^2\rangle_{\rm eff}}{\tilde m}
&=& \left\langle\frac{{\bf p}^2}{\tilde m} + a\,r^n\right\rangle_{\rm eff} \\
&=& \left(\frac{a^2}{{\tilde m}^n}\right)^{1/(2+n)} \epsilon\ .
\end{eqnarray*}
\end{enumerate}
Combining both of the above expressions for $E_{\rm eff}$, we obtain a
relation which allows us to determine $\langle{\bf p}^2\rangle_{\rm eff}$
unambiguously in terms of the dimensionless energy eigenvalues $\epsilon$:
\begin{equation}
\langle{\bf p}^2\rangle_{\rm eff}^{2+n}
= \frac{1}{4}\left(\frac{n}{2+n}\right)^{2+n}a^2\,\epsilon^{2+n}
\left(\langle{\bf p}^2\rangle_{\rm eff} + m^2\right)\ .
\label{eq:master}
\end{equation}
For a given power $n$, this equation may be solved for $\langle{\bf
p}^2\rangle_{\rm eff}$. Insertion of the resulting expression into
Eq.~(\ref{eq:eeff}) then yields the corresponding eigenvalue $E_{\rm eff}$ of
the effectively semi-relativistic Hamiltonian $\tilde H_{\rm eff}$.

\section{Applications}\label{sec:effhamappl}

We would like to investigate the capabilities of the effective treatment
proposed in the previous sections by discussing some of its implications for
some familiar prototypes of interaction potentials, namely, for the
harmonic-oscillator, Coulomb, linear, and funnel potential. To this end we
compare for the lowest-lying energy eigenstates (which we will label
according to the usual spectroscopic notation) the energy eigenvalues
$E_{\rm eff}$ resulting from our effective description with the respective
energy eigenvalues $E_{\rm NR}$ obtained within the corresponding and by now
rather standard nonrelativistic approach \cite{lucha91,lucha92}.

Occasionally, it will prove to be favourable to inspect, in particular, the
ultrarelativistic limit of the developed effective formalism, defined by
vanishing mass $m$ of the bound-state constituents, i.~e., by $m = 0$.

The relevant parameter space of our effective Hamiltonian $\tilde H_{\rm
eff}$ with a power-law potential of the form $V(r) = a\,r^n$ is spanned by
the mass $m$ of the bound-state constituents and the coupling strength $a$ of
the potential. Quite obviously, the crucial question within this context is:
For a given level of excitation of the bound system and a given coupling
strength $a$, for which range of the mass $m$ does our effective treatment
represent indeed a better approximation to the correct semi-relativistic
description of the quantum system under consideration than the much more
simple-minded nonrelativistic approach?

Consequently, we compare in the following, for the above-mentioned prototype
potentials, the difference of the effective energy eigenvalues $E_{\rm eff}$
and the semi-relativistic energy eigenvalues $E$ with the difference of the
nonrelativistic energy eigenvalues $E_{\rm NR}$ and the semi-relativistic
energy eigenvalues $E$; in other words, we consider the ratio
\begin{equation}
R := \frac{E_{\rm eff} - E}{E_{\rm NR} - E}\ .
\label{eq:rodoel}
\end{equation}
As long as (the modulus of) this ratio $R$ is less than one, the errors of
the energy eigenvalues induced by our effective treatment are definitely
smaller than those brought about by the nonrelativistic approach.

The spectra of both nonrelativistic and effective energy eigenvalues of
harmonic-oscillator and Coulomb potential may be investigated on entirely
algebraic grounds. More sophisticated potentials as well as the
semi-relativistic spectra of harmonic-oscillator and Coulomb potential,
however, have to be handled with the help of numerical methods:
\begin{itemize}
\item The numerical results for all Schr\"odinger-like situations, that is,
for both the nonrelativistic and effective approaches to linear and funnel
potential as well as for the semi-relativistic approach to the
harmonic-oscillator potential---in which case the semi-relativistic
Hamiltonian may be transformed to the one of a nonrelativistic
Schr\"odinger-type problem---, have been computed in an iterative way with
the help of the numerical scheme developed in Ref.~\cite{falk85}.
\item The numerical results for the semi-relativistic treatment of linear and
funnel potential have been obtained by a procedure similar to the so-called
``method of orthogonal collocation'' \cite{orthcoll}. This method
approximates the action of the square-root operator $\sqrt{{\bf p}^2 + m^2}$
of the relativistic kinetic energy on some suitably chosen (truncated) set of
basis states by a well-defined (finite) matrix representation.
\end{itemize}

For obvious reasons, we do not attempt to fit the predicted effective energy
eigenvalues to some experimentally observed particle spectrum. Nevertheless,
for our numerical discussion we employ parameter values which indicate, at
least, the physically reasonable orders of magnitude. We increase the mass
$m$ of the bound-state constituents gradually from zero to $m = 1.8$ GeV,
which corresponds (roughly) to the typical mass of the constituent c quark,
while keeping the coupling constants in the considered potentials fixed at
some typical values suggested by various attempts of phenomenological
descriptions of hadrons as bound states of quarks by (nonrelativistic)
potential models \cite{lucha91,lucha92}.

For dimensional reasons, in the case of the Coulomb potential any kind of
energy eigenvalue must be necessarily proportional to the mass $m$ of the
bound-state constituents, which renders the energy-difference ratio $R$ given
by Eq.~(\ref{eq:rodoel}) independent of $m$. For the harmonic-oscillator,
linear, and funnel potentials, our numerical investigations result in the
following findings for the dependence of $R$ on the mass $m$ and on the level
of excitation:
\begin{enumerate}
\item There is a certain critical value of the mass $m$ of the bound-state
constituents, which depends, of course, on the considered level of excitation
and on the particular value of the coupling strength $a$ in the potential.
For particle masses $m$ smaller than this boundary mass, the ratio $R$
defined by Eq.~(\ref{eq:rodoel}) stays between 0 and 1. This means that below
this specific boundary mass the effective energy eigenvalues $E_{\rm eff}$
are, at least, closer to the (exact) semi-relativistic ones $E$ than their
nonrelativistic competitors $E_{\rm NR}$. Furthermore, the ratio $R$
decreases with decreasing mass $m$ of the bound-state constituents.
Consequently, a diminution of this mass $m$ certainly improves the quality of
the approximation induced by the effective formalism compared to the
nonrelativistic approach.
\item There appears to exist a general trend of the decrease of the ratio $R$
defined by Eq.~(\ref{eq:rodoel}) for successively higher levels of
excitation. As a consequence of this, the critical mass becomes the larger
the higher the excitation of the bound system under consideration is. Quite
obviously, this effect increases the range of applicability of our effective
formalism for higher levels of excitation.
\end{enumerate}

An important feature of the experimentally measured mass spectra of
hadrons---which may serve to provide a decisive criterion regarding the
usefulness of our effective treatment for a meaningful description of
hadrons---is the empirically well-established linearity of the Regge
trajectories: both mesons and baryons may be grouped to form sets of
particles which populate (approximately) linear Regge trajectories; the
different members of these sets are related by the fact that, apart from a
constant shift, the squares of their masses, i.~e., of the energy eigenvalues
of the corresponding bound states of quarks in their center-of-momentum
frame, are proportional to the relative orbital angular momentum $\ell$ of
the bound-state constituents or, equivalently, the spin of the composite
particles, with almost one and the same constant of proportionality, the
so-called Regge slope
$$
\beta \simeq 1.2 \mbox{ GeV}^2\ ,
$$
for all Regge trajectories \cite{pdg94}. We indicate these relationships by
$$
E^2(\ell) = \beta\,\ell + \mbox{const.}
$$
In general, the theoretical dependence of the energy eigenvalues $E$ on the
angular momentum $\ell$ will turn out to be described by some rather
complicated function of $\ell$. For this reason we only take a quick glance
on the asymptotic behaviour of the predicted energy eigenvalues $E(\ell)$ for
large values of the angular momentum $\ell$, symbolically denoted by the
limit $\ell \to \infty$. There we may expect to observe a simple power-law
rise of the calculated squares of energy eigenvalues $E^2(\ell)$ for
increasing values of $\ell$.

\subsection{Harmonic oscillator}

For the harmonic-oscillator potential $V(r) = a\,r^2$, that is, for $n = 2$,
Eq.~(\ref{eq:master}) reduces to a quartic equation for the expectation value
$\langle{\bf p}^2\rangle_{\rm eff}$. Inserting the well-known expression
\cite{lucha91} for the dimensionless energy eigenvalues $\epsilon$ of the
three-dimensional harmonic oscillator,
$$
\epsilon = 2\,N\ ,
$$
where the total quantum number $N$ is given in terms of the radial and
orbital angular-momentum quantum numbers $n_{\rm r}$ and $\ell$,
respectively, by
$$
N = 2\,n_{\rm r} + \ell + \frac{3}{2}\ ,
\quad n_{\rm r} = 0,1,2,\dots, \quad \ell = 0,1,2,\dots,
$$
it is a simple task to write down the analytic solution of this quartic
equation for $\langle{\bf p}^2\rangle_{\rm eff}$ in terms of the potential
parameter $a$, the mass $m$ of the bound-state constituents, and the above
total quantum number $N$. According to our above prescription, the effective
energy eigenvalue is then given by inserting this result into
Eq.~(\ref{eq:eeff}). In the ultrarelativistic limit this effective energy
eigenvalue takes a particularly simple form: for $m = 0$ one finds
$$
\langle{\bf p}^2\rangle_{\rm eff} = \left(\frac{a}{2}\right)^{2/3} N^{4/3}
$$
and
\begin{eqnarray*}
E_{\rm eff} &=& 4\sqrt{\langle{\bf p}^2\rangle_{\rm eff}} \\
&=& 2\,(4\,a)^{1/3}N^{2/3}\ .
\end{eqnarray*}

Table \ref{tab:ratio-harmosci} compares the nonrelativistic and effectively
semi-relativistic approaches for the harmonic oscillator, exemplifying
thereby the above findings 1 and 2.
{\normalsize
\begin{table}[hbt]
\begin{center}
\caption[]{Ratio $R$ of the differences between effective and
semi-relativistic and between nonrelativistic and semi-relativistic energy
eigenvalues, defined in Eq.~(\ref{eq:rodoel}), for the three lowest-lying
energy eigenstates (denoted by 1S, 1P, and 2S) of the harmonic-oscillator
potential $V(r) = a\,r^2$, with $a = 0.5 \mbox{ GeV}^3$ and increasing mass
$m$ of the bound-state constituents.}\label{tab:ratio-harmosci}
\vspace{0.5cm}
\begin{tabular}{|c|c|c|c|}
\hline\hline
&\multicolumn{3}{c|}{}\\[-1ex]
&\multicolumn{3}{c|}{State}\\
&\multicolumn{3}{c|}{}\\[-1.5ex]
\cline{2-4}
$\begin{array}{c}\mbox{$\qquad m$ [GeV]$\qquad$}\\[1ex]{}\end{array}$
&1S&1P&2S\\[-0.5ex]
\hline
&&&\\[-1.1ex]
$\qquad0.250\qquad$&$\qquad0.192\qquad$&$\qquad0.120\qquad$&
$\qquad0.122\qquad$\\
$\qquad0.336\qquad$&$\qquad0.250\qquad$&$\qquad0.156\qquad$&
$\qquad0.156\qquad$\\
$\qquad0.500\qquad$&$\qquad0.358\qquad$&$\qquad0.228\qquad$&
$\qquad0.218\qquad$\\
$\qquad0.750\qquad$&$\qquad0.515\qquad$&$\qquad0.339\qquad$&
$\qquad0.311\qquad$\\
$\qquad1.000\qquad$&$\qquad0.665\qquad$&$\qquad0.451\qquad$&
$\qquad0.401\qquad$\\
$\qquad1.800\qquad$&$\qquad1.147\qquad$&$\qquad0.812\qquad$&
$\qquad0.673\qquad$\\[1.3ex]
\hline\hline
\end{tabular}
\end{center}
\end{table}}

Furthermore, it is no problem to determine immediately the large-$\ell$
behaviour of the theoretical energy eigenvalues. In the ultrarelativistic
case, because of $N \propto \ell$ for large $\ell$, the effective energy
eigenvalues $E_{\rm eff}$ behave, according to their above-mentioned
explicit general form, like
$$
E_{\rm eff}^2(\ell) \propto \ell^{4/3}\ .
$$
In very clear contrast to that, the large-$\ell$ asymptotic behaviour of the
corresponding nonrelativistic energy eigenvalues $E_{\rm NR}$ is given by
\cite{lucha91,lucha92}
$$
E_{\rm NR} = 2\sqrt{\frac{a}{m}}\,\ell + \mbox{const.}\ ,
$$
which implies
$$
E_{\rm NR}^2(\ell) \propto \ell^2\ .
$$
Without really great surprise, we arrive at the satisfactory conclusion that
for the harmonic-oscillator potential (at least the ultrarelativistic limit
of) the effective treatment comes closer to the observed linearity of the
Regge trajectories than the nonrelativistic approach.

\subsection{Coulomb potential}

For the Coulomb potential $V(r) = - \kappa/r$, that is, for $n = - 1$,
Eq.~(\ref{eq:master}) reduces to a linear equation for the expectation value
$\langle{\bf p}^2\rangle_{\rm eff}$. Inserting the well-known expression
\cite{lucha91} for the dimensionless energy eigenvalues $\epsilon$ of the
nonrelativistic Coulomb problem,
$$
\epsilon = - \frac{1}{(2\,N)^2}\ ,
$$
where the total quantum number $N$ is given in terms of the radial and
orbital angular-momentum quantum numbers $n_{\rm r}$ and $\ell$,
respectively, by
$$
N = n_{\rm r} + \ell + 1\ ,
\quad n_{\rm r} = 0,1,2,\dots, \quad \ell = 0,1,2,\dots,
$$
we obtain from this linear equation for $\langle{\bf p}^2\rangle_{\rm eff}$
$$
\langle{\bf p}^2\rangle_{\rm eff}
= \frac{\kappa^2\,m^2}{16\,N^2 - \kappa^2}\ ,
$$
and, after inserting this expression into Eq.~(\ref{eq:eeff}), for the
effective energy eigenvalues
$$
E_{\rm eff}
= \frac{m}{N}\,\frac{8\,N^2 - \kappa^2}{\sqrt{16\,N^2 - \kappa^2}}\ .
$$

In the ultrarelativistic limit $m = 0$ all of these energy eigenvalues
vanish. For the Coulomb problem, because of the lack of any sort of
dimensional parameter inherent to the theory in the case $m = 0$, this kind
of degeneracy must take place already for dimensional reasons. It may be
understood completely by application of the most general, that is,
relativistic, so-called ``master'' virial theorem \cite{lucha89,lucha90mpla}
derived by the present authors.

Picking up the question of the large-$\ell$ behaviour of the theoretical
energy eigenvalues again, we find from the reported explicit expression that
in the limit $\ell \to \infty$ the effective energy eigenvalues
$E_{\rm eff}$ will not depend on the orbital angular momentum $\ell$ at all:
$$
E_{\rm eff}^2(\ell) \propto \ell^0\ .
$$
In the nonrelativistic case, on the other hand, the energy eigenvalues
$E_{\rm NR}$ behave asymptotically like \cite{lucha91,lucha92}
$$
E_{\rm NR} = - \frac{m\,\kappa^2}{4\,\ell^2} + \mbox{const.}\ ,
$$
which implies the asymptotic independence of also the nonrelativistic energy
eigenvalues $E_{\rm NR}$ of the orbital angular momentum $\ell$:
$$
E_{\rm NR}^2(\ell) \propto \ell^0\ .
$$

\subsection{Variational method}\label{subsec:varmeth}

In general, it will not be possible to find some analytic expressions for the
effective energy eigenvalues $E_{\rm eff}$. However, in order to obtain an
approximation to the spectrum of energy eigenvalues to be expected or to get,
at least, some idea of it one may adopt the variational method described in
the following.

This standard variational method proceeds along the steps of the following,
extremely simple recipe \cite{lucha92,flamm82}:
\begin{enumerate}
\item Choose a suitable set of trial states $\{|\lambda\rangle\}$. The
different members of this set $\{|\lambda\rangle\}$ are distinguished from
each other by some sort of variational parameter $\lambda$.
\item Compute the set of expectation values of the Hamiltonian under
consideration, $H$, with respect to these trial states $|\lambda\rangle$ in
order to obtain
$$
E(\lambda) \equiv \langle\lambda|H|\lambda\rangle\ .
$$
\item Determine, from the first derivative with respect to $\lambda$, that
value $\lambda_{\rm min}$ of the variational parameter $\lambda$ which
minimizes the resulting, $\lambda$-dependent expression $E(\lambda)$.
\item Compute $E(\lambda)$ at the point of the minimum $\lambda_{\rm min}$ to
find in this way the minimal expectation value $E(\lambda_{\rm min})$ of the
Hamiltonian $H$ in the Hilbert-space subsector of the chosen trial states
$|\lambda\rangle$.
\end{enumerate}
This minimum $E(\lambda_{\rm min})$ provides, of course, only an upper
bound\footnote{\normalsize\ The accuracy of this method is discussed in
Ref.~\cite{schoeberl82}.} to the proper energy eigenvalue $E$ of the
Hamiltonian $H$:
$$
E \le E(\lambda_{\rm min})\ .
$$

Application of this straightforward variational procedure to one of our
effectively semi-relativistic Hamiltonians $\tilde H_{\rm eff}$ leads to
$E_{\rm eff}(\lambda_{\rm min})$, which, according to its derivation,
represents at least an upper bound to the corresponding effective energy
eigenvalue $E_{\rm eff}$.

Note that, as far as the above variational procedure is concerned, the
expectation value $\langle{\bf p}^2\rangle_{\rm eff}$ entering in the
effective Hamiltonian has to be regarded as a constant. Consequently, it has
not to be taken into account in the course of minimization of the energy
expression $E(\lambda)$ by varying the characteristic parameter $\lambda$.
Rather, in the framework of this variational technique, it has to be equated
to the expectation value of ${\bf p}^2$ taken with respect to precisely
that trial state $|\lambda_{\rm min}\rangle$ which is characterized by just
the minimizing value $\lambda_{\rm min}$ of the variational parameter
$\lambda$, that is, to $\langle\lambda_{\rm min}|{\bf
p}^2|\lambda_{\rm min}\rangle$.

For the present investigation we adopt the simplest conceivable set of trial
states $|\lambda\rangle$, namely, the ones the coordinate-space
representation $\psi({\bf x})$ of which is given, for a vanishing radial
quantum number $n_{\rm r}$, by the Gaussian trial functions (w.~l.~o.~g.,
$\lambda > 0$)
$$
\psi_{\ell m}(r,\theta,\phi)
= \sqrt{\frac{2\,\lambda^{2\,\ell + 3}}
{\Gamma\left(\ell + \mbox{$\frac{3}{2}$}\right)}}\,r^\ell\,
\exp\left(- \frac{\lambda^2\,r^2}{2}\right)
{\cal Y}_{\ell m}(\theta,\phi)\ ,
$$
where ${\cal Y}_{\ell m}$ denote the spherical harmonics for angular momentum
$\ell$ and projection $m$, and the normalization factor of these trial
functions makes use of the so-called gamma function \cite{abramow}
$$
\Gamma(z) \equiv \int\limits_0^\infty dt\,t^{z - 1}\,\exp(- t)\ .
$$
For this particular set of trial functions we obtain for the expectation
values of the square ${\bf p}^2$ of the momentum ${\bf p}$ and of the
$n$-th power $r^n$ of the radial coordinate $r$, respectively, with respect
to the trial states $|\lambda\rangle$:
$$
\langle\lambda|{\bf p}^2|\lambda\rangle
= \left(\ell + \mbox{$\frac{3}{2}$}\right)\lambda^2
$$
and
$$
\langle\lambda|r^n|\lambda\rangle
= \frac{\Gamma\left(\ell + \mbox{$\frac{3 + n}{2}$}\right)}
{\Gamma\left(\ell + \mbox{$\frac{3}{2}$}\right)}\,
\frac{1}{\lambda^n}\ .
$$

\subsection{Linear potential}

For the linear potential $V(r) = a\,r$, that is, for $n = 1$,
Eq.~(\ref{eq:master}) reduces to a cubic equation for the expectation value
$\langle{\bf p}^2\rangle_{\rm eff}$ which, of course, may be solved
analytically. Unfortunately, for the linear potential the dimensionless
energy eigenvalues $\epsilon$ are only known \cite{lucha91} for the case of
vanishing orbital angular momentum $\ell$, i.~e., only for $\ell = 0$. In
this case they are given by the negative zeros of the Airy function
\cite{abramow}. In any case, that is, for arbitrary values of $\ell$, the
effective energy eigenvalues $E_{\rm eff}$ may be found by employing some
numerical procedure.

However, before performing a numerical computation of the energy eigenvalues
$E_{\rm eff}$ of the effective Hamiltonian $\tilde H_{\rm eff}$ with linear
potential, we apply the simple variational technique introduced in the
preceding subsection. For this Hamiltonian the value of the variational
parameter $\lambda$ which minimizes the relevant expectation value
$\langle\lambda|\tilde H_{\rm eff}|\lambda\rangle$, that is,
$\lambda_{\rm min}$, is implicitly given by
$$
\lambda_{\rm min}^3 = \frac{a}{2}\,\frac{\Gamma(\ell + 2)}
{\Gamma\left(\ell + \mbox{$\frac{5}{2}$}\right)}\,\tilde m\ .
$$
Recalling the definition of $\tilde m$ as given in
Sect.~\ref{sec:effsemrelham}, we obtain from this expression a cubic equation
for $\langle\lambda_{\rm min}|{\bf p}^2|\lambda_{\rm min}\rangle$,
$$
\langle\lambda_{\rm min}|{\bf p}^2|\lambda_{\rm min}\rangle^3
= \frac{a^2}{16}\left(\ell + \mbox{$\frac{3}{2}$}\right)
\left(\frac{\Gamma(\ell + 2)}
{\Gamma\left(\ell + \mbox{$\frac{3}{2}$}\right)}\right)^2\left(
\langle\lambda_{\rm min}|{\bf p}^2|\lambda_{\rm min}\rangle + m^2\right)\ ,
$$
the analytic solution of which may be written down quickly. Insertion of this
result into Eq.~(\ref{eq:eeff}) yields $E_{\rm eff}(\lambda_{\rm min})$ for
the linear potential. In the ultrarelativistic limit $m=0$ we find in this
way the (variational) effective energy eigenvalues
$$
E_{\rm eff}(\lambda_{\rm min})
= 3\left(\ell + \mbox{$\frac{3}{2}$}\right)^{1/4}
\sqrt{\frac{\Gamma(\ell + 2)}
{\Gamma\left(\ell + \mbox{$\frac{3}{2}$}\right)}\,a}\ .
$$

Table \ref{tab:ratio-linear} compares the nonrelativistic and effectively
semi-relativistic approaches for the linear potential, confirming thereby
again the above findings 1 and 2.
{\normalsize
\begin{table}[hbt]
\begin{center}
\caption[]{Ratio $R$ of the differences between effective and
semi-relativistic and between nonrelativistic and semi-relativistic energy
eigenvalues, defined in Eq.~(\ref{eq:rodoel}), for the three lowest-lying
energy eigenstates (denoted by 1S, 1P, and 2S) of the linear potential $V(r)
= a\,r$, with the slope $a = 0.211 \mbox{ GeV}^2$ and increasing mass $m$ of
the bound-state constituents.}\label{tab:ratio-linear}
\vspace{0.5cm}
\begin{tabular}{|c|c|c|c|}
\hline\hline
&\multicolumn{3}{c|}{}\\[-1ex]
&\multicolumn{3}{c|}{State}\\
&\multicolumn{3}{c|}{}\\[-1.5ex]
\cline{2-4}
$\begin{array}{c}\mbox{$\qquad m$ [GeV]$\qquad$}\\[1ex]{}\end{array}$
&1S&1P&2S\\[-0.5ex]
\hline
&&&\\[-1.1ex]
$\qquad0.250\qquad$&$\qquad0.603\qquad$&$\qquad0.452\qquad$&
$\qquad0.466\qquad$\\
$\qquad0.336\qquad$&$\qquad0.750\qquad$&$\qquad0.576\qquad$&
$\qquad0.572\qquad$\\
$\qquad0.500\qquad$&$\qquad1.013\qquad$&$\qquad0.802\qquad$&
$\qquad0.750\qquad$\\
$\qquad0.750\qquad$&$\qquad1.411\qquad$&$\qquad1.144\qquad$&
$\qquad1.002\qquad$\\
$\qquad1.000\qquad$&$\qquad1.825\qquad$&$\qquad1.498\qquad$&
$\qquad1.253\qquad$\\
$\qquad1.800\qquad$&$\qquad3.304\qquad$&$\qquad2.757\qquad$&
$\qquad2.117\qquad$\\[1.3ex]
\hline\hline
\end{tabular}
\end{center}
\end{table}}

Inspecting once again the large-$\ell$ behaviour of the predicted energy
eigenvalues, we may read off from the above explicit expression for the
ultrarelativistic (variational) effective energy eigenvalues
$E_{\rm eff}(\lambda_{\rm min})$, with the help of a useful relation
describing the asymptotic behaviour of the ratio of gamma functions
\cite{abramow}, viz.,
$$
\lim_{\ell \to \infty}\frac{\Gamma(\ell + z)}{\Gamma(\ell + u)}
= \ell^{z - u}\ ,
$$
the very pleasing result
$$
E_{\rm eff}^2(\lambda_{\rm min}) = 9\,a\,\ell\ .
$$
Accordingly, the effectively semi-relativistic energy eigenvalues of the
linear potential are perfectly able to reproduce the observed linearity of
the Regge trajectories with, however, a slope which is slightly larger than
the one obtained within different investigations \cite{kang75,lucha91regge}
based on the proper semi-relativistic Hamiltonian (\ref{eq:hsemi-rel}), all
of which end up with one and the same finding:
$$
E^2 = 8\,a\,\ell\ .
$$
Moreover, from the point of view of a correct description of the linear Regge
trajectories, both of the semi-relativistic treatments are clearly superior
to the corresponding nonrelativistic approach, which gives for the energy
eigenvalues of the linear potential \cite{lucha91,lucha92}
$$
E_{\rm NR} =
3\left(\frac{a^2}{4\,m}\right)^{1/3}\ell^{2/3} + \mbox{const.}
$$
and therefore
$$
E_{\rm NR}^2(\ell) \propto \ell^{4/3}\ .
$$

\subsection{Funnel potential}

Unfortunately, the potentials considered up to now are merely of more or less
academic interest. Finally, however, we would like to discuss a potential
which has been among the first ones to be proposed \cite{eichten75} for the
description of hadrons as bound states of constituent quarks, viz., the
funnel (or Cornell or Coulomb-plus-linear) potential.

This funnel potential comprehends the two basic ingredients of any realistic,
that is, phenomenologically acceptable, inter-quark potential, namely,
\begin{itemize}
\item at ``short'' inter-quark distances some Coulomb-like singularity of
perturbative origin, which arises from one-gluon exchange, and
\item at ``large'' inter-quark distances an (approximately) linear rise of
non-perturbative origin, which is obviously responsible for colour
confinement.
\end{itemize}
The funnel potential incorporates these two features in the simplest
conceivable manner:
$$
V(r) = - \frac{\kappa}{r} + a\,r\ .
$$
In this form it still represents the prototype of almost all forthcoming
potential models designed to describe all the (binding) forces acting between
quarks.\footnote{\normalsize\ For a brief survey see, for instance,
Ref.~\cite{lucha91}.}

This funnel potential is, beyond doubt, not of the power-law type.
Consequently, it cannot be subjected to the general effective formalism
developed so far but deserves a special treatment, which might consist of
some purely numerical approach.

However, as before, we first want to obtain some insight by applying the
variational procedure described in Subsect.~\ref{subsec:varmeth}. The value
$\lambda_{\rm min}$ of the variational parameter $\lambda$ which minimizes
for the case of the above funnel potential the expectation value of the
effective Hamiltonian $\tilde H_{\rm eff}$ with respect to our Gaussian
trial states is (because of the presence of $\tilde m$ only implicitly)
determined by the relation
$$
\lambda_{\rm min}^3 = \frac{\tilde m}{2}\,
\frac{\Gamma(\ell + 1)}{\Gamma\left(\ell + \mbox{$\frac{5}{2}$}\right)}
\left[\kappa\,\lambda_{\rm min}^2 + a\,(\ell + 1)\right]\ .
$$
In the ultrarelativistic limit $m = 0$ this relation fixes
$\lambda_{\rm min}$ to
$$
\lambda_{\rm min}
= \sqrt{\frac{a\,\Gamma(\ell + 2)}{4\sqrt{\ell + \mbox{$\frac{3}{2}$}}\,
\Gamma\left(\ell + \mbox{$\frac{3}{2}$}\right) - \kappa\,\Gamma(\ell + 1)}}
\ ,
$$
which, in turn, implies for the (variational) effective energy eigenvalues of
the funnel potential
$$
E_{\rm eff}(\lambda_{\rm min}) = 2\,\lambda_{\rm min}
\left(3\sqrt{\ell + \mbox{$\frac{3}{2}$}} - \kappa\,\frac{\Gamma(\ell + 1)}
{\Gamma\left(\ell + \mbox{$\frac{3}{2}$}\right)}\right)\ .
$$

Table \ref{tab:ratio-funnel} compares the nonrelativistic and effectively
semi-relativistic approaches for the funnel potential, illustrating thereby
once more the above findings 1 and 2.
{\normalsize
\begin{table}[hbt]
\begin{center}
\caption[]{Ratio $R$ of the differences between effective and
semi-relativistic and between nonrelativistic and semi-relativistic energy
eigenvalues, defined in Eq.~(\ref{eq:rodoel}), for the three lowest-lying
energy eigenstates (denoted by 1S, 1P, and 2S) of the funnel potential $V(r)
= - \kappa/r + a\,r $, with Coulomb coupling constant $\kappa = 0.456$, slope
$a = 0.211 \mbox{ GeV}^2$, and increasing mass $m$ of the bound-state
constituents.}\label{tab:ratio-funnel}
\vspace{0.5cm}
\begin{tabular}{|c|c|c|c|}
\hline\hline
&\multicolumn{3}{c|}{}\\[-1ex]
&\multicolumn{3}{c|}{State}\\
&\multicolumn{3}{c|}{}\\[-1.5ex]
\cline{2-4}
$\begin{array}{c}\mbox{$\qquad m$ [GeV]$\qquad$}\\[1ex]{}\end{array}$
&1S&1P&2S\\[-0.5ex]
\hline
&&&\\[-1.1ex]
$\qquad0.250\qquad$&$\qquad0.629\qquad$&$\qquad0.463\qquad$&
$\qquad0.500\qquad$\\
$\qquad0.336\qquad$&$\qquad0.764\qquad$&$\qquad0.584\qquad$&
$\qquad0.603\qquad$\\
$\qquad0.500\qquad$&$\qquad0.988\qquad$&$\qquad0.801\qquad$&
$\qquad0.771\qquad$\\
$\qquad0.750\qquad$&$\qquad1.288\qquad$&$\qquad1.118\qquad$&
$\qquad0.992\qquad$\\
$\qquad1.000\qquad$&$\qquad1.559\qquad$&$\qquad1.437\qquad$&
$\qquad1.191\qquad$\\
$\qquad1.800\qquad$&$\qquad2.277\qquad$&$\qquad2.489\qquad$&
$\qquad1.770\qquad$\\[1.3ex]
\hline\hline
\end{tabular}
\end{center}
\end{table}}

The large-$\ell$ behaviour of the ultrarelativistic (variational) effective
energy eigenvalues $E_{\rm eff}(\lambda_{\rm min})$ resulting from this
expression is the same as for the pure linear potential:
$$
E_{\rm eff}^2(\lambda_{\rm min}) = 9\,a\,\ell\ .
$$
This circumstance is an unavoidable consequence of the fact that in the limit
$\ell \to \infty$ all contributions of the Coulomb part of the funnel
potential to the above effective energy eigenvalues $E_{\rm eff}$ vanish,
which may be seen immediately by recalling once more the above-mentioned
asymptotic behaviour of the ratio of gamma functions. Accordingly, for large
orbital angular momenta $\ell$ the positioning of the energy levels of the
funnel potential is controlled by its confinement part
only.\footnote{\normalsize A similar observation has already been made in
Ref.~\cite{lucha91regge} within a slightly different context
\cite{lucha91rel,lucha90com}.}

\section{Conclusions}\label{sec:effhamconcl}

The present paper has been dedicated to the formulation of effectively
semi-relativistic Hamiltonians which are designed in such a way that---by a
suitable interpretation of their (effective) parameters---they allow us to
approximate an entirely semi-relativistic formalism at a formally
nonrelativistic level. Application of the developed formalism to a few
representative static interaction potentials gave indications that below some
specific critical mass of the involved particles, where our effective energy
eigenvalues are closer to the (exact) semi-relativistic ones than those of a
nonrelativistic description, the effective approach represents, at least in
relativistic regions, an improvement of the certainly rather crude
nonrelativistic approximation. Simultaneously, this observation might
contribute to the eventual explanation of the surprising success of (a
variety of) nonrelativistic potential models in describing hadrons as bound
states of quarks even for the case of relativistically moving constituents.

\newpage

\normalsize


\section*{Acknowledgements}
\noindent
AAB and AAP acknowledge the support and the hospitality
of INFN-Sezione di Trieste and the International Centre for
Theoretical Physics, Trieste.
The work of (NP) has been supported in part by the
Human Capital and Mobility Programme, EEC Contract ERBCHRXCT930132.

\newpage