\section{Introduction}
The idea of byzantine fault-tolerance was first introduced by Lamport et al. \cite{ByzantineGeneral}. Byzantine consensus has since become a large research topic, with applications such as blockchain technology \cite{Blockchain} and machine learning \cite{ByzantineML}.

Dolev et al. \cite{Dolev} modified and extended the problem of byzantine agreement by introducing \textit{approximate Byzantine agreement}, allowing machines to reach approximate consensus rather than exact consensus. This was motivated by the fact that exact consensus in asynchronous systems was proven to be impossible \cite{Lynch}. Additionally, in synchronous systems, approximate byzantine consensus can be used to create algorithms that do not require complete knowledge of the network topology \cite{IABCPart1}.

This approximate byzantine consensus problem aims to have all honest machines converge to a single state within the convex hull of initial states as the number of iterations approaches infinity \cite{Dolev}. Vaidya \cite{Transition} utilizes a method describing the progression of states in the network using transition matrices to prove consensus.

The main contribution of this paper is to utilize two key tools that have seen a lot of use and success in traditional byzantine consensus problems: messages with unforgeable signatures \cite{DolevStrong, ByzantineGeneral,Dishonest} and relaying messages \cite{ByzantineGeneral,Relay}; our work is a generalization of \cite{Transition}, with signatures and relays used to circumvent certain network assumptions that would otherwise be necessary. To the best of my knowledge, this is the first time either of these two tools have been used in approximate byzantine consensus algorithms.

Byzantine consensus has had applications to machine learning by having machines perform gradient descent steps to minimize a loss function on top of consensus techniques. The combination of delays and signatures may have additional applications in byzantine gradient descent.  \cite{BRIDGE} extends approximate byzantine consensus algorithms for use in byzantine gradient descent methods. We leave the question as to whether Relay-ABC may have a similar extension to our future work.

\section{Problem Formulation}
\subsection{Definitions}
\subsubsection{Graph Notation and Definitions}
\begin{itemize}
    \item Let $m$ be the total number of machines (or "nodes"), $h$ the number of honest machines, and $b$ be the number of byzantine machines ($h+b=m$).

    \item Let $B$ denote the set of byzantine nodes and $H$ denote the set of honest nodes. The set of all nodes $V$ is equal to $B \cup H$.

    \item Denote $N_{i}^{I}$ to be the set of all machines that have incoming edges from machine $i$. Denote $N_{i}^{O}$ to be the set of all machines that have outgoing edges to machine $i$

    \item Define $dist(i,j)$, for some $i,j \in V$ as the length of the shortest path from node $i$ to $j$

    \item In this paper, a "non-zero value" refers to a value that can be lower bounded by some positive constant. In the context of transition matrices, this value doesn't approach 0 as the number of iterations approaches infinity.
\end{itemize}

\subsubsection{Matrix Definitions}
Let $M$ denote some arbitrary matrix, and $M[t]$ denote some arbitrary matrix with respect to iteration $t$.
\begin{itemize}
    \item Transition matrix $M$ denotes a square matrix of size $hD\times hD$

    \item $M_{i}[t]$ denotes the $i$th row of matrix $M[t]$

    \item $M_{ij}[t]$ denotes the element at row $i$ and column $j$ of matrix $M[t]$

    \item We define the first row and column in every matrix as row/column 0

    \item Matrix Splicing: $M[a,b:c,d]$ denotes the submatrix spliced by top row $a$, bottom row $b$, left column $c$ and right column $d$ (all inclusive) of matrix $M$

    \begin{figure}

    $M=\left[\begin{matrix}
    0 & 1 & 2\\
    3 & 4 & 5\\
    6 & 7 & 8\\
    \end{matrix}\right]$
    \centering

    \medskip
    $M[0,1:0,1]=\left[\begin{matrix}
    0 & 1\\
    3 & 4\\
    \end{matrix}\right]$
    \centering
    \caption{Example of Matrix Splicing}
    \label{fig:5}
\end{figure}

    \item A non-zero column is a matrix column filled entirely with non-zero elements
\end{itemize}

\subsection{Decentralized Learning Model}
We consider a static, directed network $G(V, E)$, where $V = \{0,1,2,... m-1\}$ and $E$ representing communication links between neighboring nodes. If $(i, j) \in E$, then node $i$ may send messages to node $j$.

Our protocol is analyzed in the synchronous communication setting, where communication occurs over a sequence of iterations. Messages sent during an iteration are guaranteed to be received by the intended recipient within a given finite amount of time.

Each node $i\in V$ starts with an initial real-valued input. The goal of the protocol is to approach a state that satisfies the following two conditions:
\begin{itemize}
    \item Validity condition: After each iteration of the protocol, the state of each honest node remains within the convex hull of the initial inputs of all honest nodes.

    \item Convergence condition: The difference between the states of any two honest nodes approaches zero as the number of iterations approaches infinity
\end{itemize}

\subsection{Byzantine Failure Model}
Among the $m$ machines in the decentralized network, $b$ of them are byzantine machines. Byzantine machines may deviate arbitrarily from the protocol. For example, a byzantine machine may output any arbitrary real value, and send mismatching messages to each of its neighbors. However, a key restriction of byzantine nodes is that they cannot forge signatures of honest users.

\section{Relay-ABC Algorithm}
\subsection{Assumptions}
\theoremstyle{definition}
\begin{definition}{Honest Subgraph:}
Define the honest subgraph as the graph that is formed by removing all byzantine nodes and all edges connected to byzantine nodes in the original graph.
\end{definition}
\begin{itemize}
    \item The number of byzantine machines is strictly less than one-third the total number of machines ($b<\frac{1}{3}m$).

    \item We assume the honest subgraph is bidirectionally connected (there exists directed paths from every honest node to every other honest node).

    \item We assume the diameter of the honest subgraph is upper-bounded by $D$.
\end{itemize}

\subsection{Our Contributions}
Our work is an extension of the work done in \cite{Transition}. Our network assumptions are much less restrictive. In particular, we assume no network connectivity assumptions besides the honest subgraph being bidirectionally connected, which is necessary for any algorithm to achieve consensus over all honest nodes.

The goal of this protocol is to use a relay system to bypass traditional network connectivity assumptions outlined in \cite{IABCPart2}, which has a necessary but insufficient condition that each node has an indegree of at least $2b+1$. This requires that each honest node have at least $b+1$ incoming edges from honest neighbors. On the other hand, bidirectional connectivity of the honest subgraph may possibly be achieved when each honest node has a maximum indegree of as low as one honest neighbor.

This comes at the tradeoff of higher communication costs, as now machines send to each other at most $m$ sets of parameters in each message, as opposed to one parameter in most other algorithms in literature.

Our paper provides theoretical guarantees of validity and convergence to an approximate byzantine consensus algorithm with message delays, which to our knowledge has never been done before. Our work also introduces the use of unforgeable signatures. Signatures have seen lots of successful usage in standard byzantine consensus, but until now have not been used in approximate byzantine consensus methods.

\subsection{High-Level Idea}
Since the honest subgraph is bidirectionally connected, this allows all honest machines to receive signed messages from every other honest machine through a broadcast and relay system. Thus we create a pseudo-complete communication graph over the course of an entire phase of $D$ rounds. Since a complete graph does indeed satisfy the necessary conditions of \cite{IABCPart2}, our relay protocol achieves convergence as well.

We use a trimmed-mean aggregation step \cite{BRIDGE,Transition} to ensure byzantine robustness. The trimmed-mean step works by eliminating the greatest $b$ values and the smallest $b$ values, and then taking the arithmetic mean of the remaining values. By removing the greatest and least $b$ values, we ensure that the maximum and minimum values of the set of remaining values are both values of honest machines. This prevents byzantine machines from making the states of honest machines deviate arbitrarily.
\medskip

Each machine $i$ keeps track of their own vector $v_{i}$. This vector consists of $(v_{i}(0), v_{i}(1)... v_{i}(m-1))$, where \textbf{$v_{i}(j)$ represents machine $i$'s most recently updated record of machine $j$'s state.} $v_{i}$ may not always contain a state that was received from an actual message for each machine in the network, as machine $i$ may not have received a message from all machines.

Machine $i$ only starts performing trimmed-mean steps after $D$ iterations, as this ensures that the first broadcast of all honest machines has had sufficient time to relay across the entire graph and reach every other honest node. This means that each honest machine is outputting an identical message, their initial input value, for the first $D$ iterations.

We choose the specific value $D$, the upper-bound of the diameter of the honest subgraph, so after $D$ iterations, all honest vectors will always contain more honest parameters than byzantine parameters. $D$ is in the worst-case $O(h)$, but with high probability is $O(\log h)$ in Erdos-Renyi random graphs \cite{RandomGraph}.

\medskip

For all honest machines $i$ and $j$, any state $v_{i}(j)$ in the vector will contain a valid signature from machine $j$, as well as an iteration marker, which shows which iteration the parameter was calculated on. Denote $T(v_{i}(j))$ to be the iteration that parameter $v_{i}(j)$ was calculated on.

See Algorithm \ref{Alg1} for the Relay-ABC algorithm.

\begin{algorithm} \label{Alg1}
\SetAlgoLined
    \begin{remark}
        This algorithm is implemented by a specific machine $i$. Each machine $i \in H$ will implement this algorithm concurrently.
    \end{remark}

\KwResult{Each state $v_{i}(i)$ converges to the same value within the convex hull of the initial states as Iteration $t \rightarrow \infty$}

    Initialization:

    $v_{i}(i)\gets$ Intial State of node $i$ (with signature $i$ and iteration marker $-1$).

    \medskip

    \For{Iteration $t\gets0$ \KwTo $T$}{
        Broadcast $v_{i}$ to all machines $j\in N_{i}^{O}$

        Receive $v_{j}$ from all machines $j\in N_{i}^{I}$

        \begin{remark}
            When receiving $v_{j}$, ignore all parameters received that are not properly signed or without a proper iteration marker. If no proper message is from a node, set their incoming value to be an arbitrary predefined real value (e.g. 0).
        \end{remark}

        $G_{i}\gets N_i^O \cup \{i\}$

        \For{$j\gets0$ \KwTo $m-1$}{
            \begin{remark}
                In the next two lines, we do the following: Out of all parameters $v(j)$ received from the broadcast step, set $v_{i}(j)$ to the value with the highest iteration marker.
            \end{remark}

            \If{$j \neq i$}{
                $g'\gets \argmax_{g:\{g \in G_{i}\}}  T(v_{g}(j))$

                $v_{i}(j)\gets v_{g'}(j)$
            }
        }

        \If{$t\geq D$}{
            \textbf{Trimmed-mean update step:}

            \medskip
            In a new vector, sort the values of $v_{i}$ in increasing order:

            \begin{equation}
                v^*_{i} \gets sort(v_{i})
            \end{equation}

            Ignore the least and greatest $b$ values, and set the value of $v_{i}(i)$ to be the average of all remaining values in $v^*_{i}$, as defined below:

            \begin{equation} \label{update}
                v_{i}(i) \gets \frac{1}{m-2b} \sum_{k=b}^{m-b-1} v^*_{i}(k)
            \end{equation}

            Add signature $i$ and iteration marker $t$ to $v_{i}(i)$
        }
    }
 \caption{Relay-ABC}
\end{algorithm}

\section{Theoretical Guarantees}
\subsection{Overview}
In the following section, we prove that the Relay-ABC algorithm satisfies the validity and convergence conditions.

We define transition matrix $M[t]$ and construct it so that it models the state update of all honest nodes as defined in Algorithm 1. The transition matrices are then used to prove that Algorithm 1 guarantees convergence over all honest nodes.

\subsection{Matrix Definitions}
We introduce several definitions for matrices, most of which are adapted from \cite{Transition}.

To make analysis easier, we will differentiate between \textit{iterations} ($r$) and \textit{phases} ($t$). Define an \textit{iteration} as a single instance in time of communications. During each iteration, every node sends and receives messages from its neighbors. Define a \textit{phase} as a set of $D$ iterations. Therefore the $ith$ phase contains iterations $(i-1)D$ to $iD$. Note that the first iteration of the protocol is iteration 0, while the first phase is phase 1. Since the distance between any two honest nodes is at most $D$, any message from an honest node is guaranteed to reach all other honest nodes within $D$ iterations. We consider phases of $D$ iterations for theoretical analysis, not for any actual implementation in the protocol.

Denote $v[t]$ as the column vector consisting of the states of all honest nodes in phase $t$ (over all $D$ iterations). $\|v[t]\| = hD$, and $v_{rh + i}[t]$ represents the state of node $i$ at iteration $r$ of phase $t$.

Denote $v[0]$ to be the column vector consisting of the initial states of all honest nodes during the first $D$ iterations. Since all machines output the same identical message for the first $D$ iterations, $v[0]$ consists of $D$ identical $h\times1$ column vectors stacked on top of each other.

We express the iterative update of the state of a fault-free node $i \in H$ in any single phase using the matrix form below:
\begin{equation}
    v_{i}[t] = M_{i}[t-1]*v[t-1]
\end{equation}

The row vector $M_{i}[t]$ satisfies the following conditions:

$M_{i}[t]$ is a stochastic row vector of size $hD$ (proven in Appendix \ref{appendixC}). Thus, $M_{ij}[t]\geq 0$ for $0\leq j \leq hD-1$, and
\begin{equation*}
    \sum_{j=1}^{hD} M_{ij}[t]= 1
\end{equation*}

\medskip

By stacking $hD$ stochastic row matrices $M_{i}[t]$ on top of one another, where M[t] is an $hD \times hD$ matrix, we can represent to state update of all honest nodes in a single matrix multiplication:
\begin{equation} \label{TransitionUpdate}
    v[t] = M[t-1]*v[t-1]
\end{equation}

The matrix M[t] models the state update detailed in Algorithm 1. We detail the specifics of the construction in Section \ref{matrixConstruction}.

Each element in a row of the transition matrix represents some weight of the state column of the previous $D$ iterations. We describe every update of (\ref{update}) of a single node during a single phase as a matrix row.

By repeating the transition matrix update of (\ref{TransitionUpdate}) $T+1$ times, we get:
\begin{equation}
    v[T] = \prod_{t=0}^{T} M[t]*v[0]
\end{equation}

Note that this is an extension of the transition matrix idea of \cite{Transition}. Instead of a $h \times h$ transition matrix and a $h \times 1$ state vector representing the update of a single iteration, we use an expanded transition matrix to describe the update for the set of the next phase ($D$ iterations) using the set of states from the previous phase.

\subsection{Transition Matrix Construction} \label{matrixConstruction}
In this section, we introduce how to construct transition matrices to exactly model the transition of states as dictated by the Relay-ABC algorithm (Algorithm \ref{Alg1}).

We define how to construct a given row of the transition matrix. We introduce some new definitions and notation, most of which is adapted from \cite{Transition}:

\medskip
Let us consider an arbitrary honest node $i$ performing the update step (\ref{update}) at some iteration.
Vector $v_{i}$ is the set of all most updated states from each machine known to machine $i$, and is the set of all values being considered in the trimmed-mean step. It is known that $\| v_{i} \| = m$. Define set $L$ and $S$ to be the largest and smallest $b$ values, respectively, in vector $v_{i}$. Let $N_{i}^{*}$ denote the set all all states that were not removed in the trimmed-mean update step. It is known that $L$ and $S$ are disjoint sets, $|L|=|S|=b$, $N_i^* = v_i - (L\cup S)$, and $\| N_{i}^{*} \| = m-2b$.

Denote $f$ to be the number of faulty states within $N_{i}^{*}$ (faulty states that were not trimmed away.) Define subsets $L^*$ and $S^*$ such that $L^*\subseteq L$, $S^*\subseteq S$, $|L^*|=|S^*|=X$, and that $L^*$ and $S^*$ consist of only honest states (which may be arbitrarily chosen.) It is shown in \cite{Transition} that such subsets always exist.

\begin{algorithm} \label{construction}
\SetAlgoLined
    \begin{remark}
        This algorithm describes how to construct row $t$ of $M$, the $hD \times hD$ transition matrix.
    \end{remark}

    Initialization:
    For all integers $k$ such that $0 \leq k<hD: M_{tk} \gets 0$

    \medskip

    \uIf{$f=0$}{
        $G \gets $ Case 1 Construction
    }
    \uElse{
         $G \gets $ Case 2 Construction
    }

    \medskip

    \For{Node $k \in V$}{
        \uIf{$k \neq i$}{
            $iter = t \bmod h - dist(i,k)$
        }
        \uElse{
            $iter = t \bmod h - 1$
        }

        $j = iter \bmod D$

        $j = j*h + k$

        \uIf{$iter < 0$}{
            \begin{equation} \label{sum1}
                M_{tj} = M_{tj} + G_{ik}
            \end{equation}
        }
        \uElse{
             \For{$v \gets0$ \KwTo $hD-1$}{
                \begin{equation} \label{sum2}
                    M_{tv} = M_{tv} + G_{ik}*M_{jv}
                \end{equation}
             }
        }
    }

 \caption{Row Construction Algorithm}
\end{algorithm}

\subsubsection{Matrix Construction Algorithm Overview}
To construct our matrix, we consider two cases: Case 1 where $N_{i}^{*}$ contains no states from faulty nodes ($f=0$), and Case 2 where $N_{i}^{*}$ contains states from at least one faulty node ($f>0$) \cite{Transition}. We describe our transition matrix by using elements of the transition matrices in \cite{Transition}.

Without loss of generality, we denote the first iteration of the given phase corresponding to the transition matrix as iteration 0. This is for simplicity, and in actuality all iterations will be shifted upwards by some positive multiple of $D$. Here we will describe how to construct row $M_t$, which represents iteration $\lfloor\frac{t}{h}\rfloor$, where $t < hD$. Assume without loss of generality that row $t$ is a Node $i$ row.

In the first iteration of updates of a phase (represented by a single transition matrix), every value $v_{i}(j)$ in (\ref{update}) can be represented exactly by a value in the state vector (a state of the previous phase). However, we note that this is not true for any subsequent iteration: updates in iteration 1 may utilize states of iteration 0, which is a state of the current phase rather than the previous one.

Our paper's main contribution is to extend the transition matrix work of \cite{Transition}: any state from the current phase, rather than the previous state, may be represented as a convex combination of states from the previous phase. Specifically, the state of node $i$ at iteration $r$ of the current phase may be represented as
\begin{equation}
    \sum_{k=0}^{hD-1} M_{(rh + i)(k)} * v_{k}
\end{equation}

We prove that matrix $M$ is stochastic in both Case 1 and Case 2 in Appendix \ref{appendixC}.

\subsubsection{Case 1: $f=0$}
Define matrix $G$ to be the matrix constructed in Section 5.1.1 of \cite{Transition}, using our value of $v_i$ as $N_i^-$. $G$ is an $h\times h$ stochastic matrix.

Algorithm \ref{construction} is motivated by the fact that at iteration $t$, node $i$ is receiving a state from every other node. In particular, node $i$ receives the state of node $j$ from iteration $t - dist(i,j)$, as this will always be the most up-to-date iteration of node $j$ received by node $i$. We construct the matrix such that each state in $N_i^*$ is given an equal weight, as defined in (\ref{update}).

Since each node in $N_i^*$ is honest, each of its states can either be described by an element in a transition matrix, or a row of values in the transition matrix.

\subsubsection{Case 2: $f>0$}
Define matrix $G$ to be the matrix constructed in Section 5.1.2 of \cite{Transition}, using our value of $v_i$ as $N_i^-$. $G$ is an $h\times h$ stochastic matrix.

This construction is motivated by the fact every state in $N_{i}^*$ can we represented by a weighted average of two honest nodes, one in $L^*$ and one in $S^*$. This allows even the behavior of byzantine nodes to be able to be represented in the transition matrix of honest states.

\subsection{Validity Proof}
The update in (\ref{update}) of each node always results in a convex combination of some set of node states during some iterations. This means that any update will always stay within the convex hull of the set of initial input states, proving the validity condition.

\subsection{Convergence Proof}
\subsubsection{Matrix Characteristics}
\theoremstyle{definition}
\begin{definition}{Node $i$ Row:}
row $j$ of Matrix $M$ is considered a Node $i$ Row iff $j \bmod h \cong i$
\end{definition}

A Node $i$ Row represents the state update of node $i$ during some iteration of the phase.

To characterize what the weights of matrix rows representing iterations after iteration 0, we introduce the following observation:
\begin{theorem} \label{T1}
    If an element of the transition matrix $M_{ij}$ is a non-zero weight for $i < h$, then the value of $M_{zj}$ is non-zero as well, $\forall z$ such that $z$ is a Node $i$ row and $z\geq h$
\end{theorem}

\begin{proof}
    Row $i$ represents the matrix update of node $i$ in iteration 0, while row $z$ represents the matrix update of node $i$ in any iteration $[1,D]$. We denote $z = kh + i$, for some integer $k<D$.

    We proof the theorem with induction:

    Base case ($k=0$): If $k=0$, then $z=i$. The theorem is trivially true.

    Induction Step ($0<k<D$): We noted previously that not every update can be exactly expressed as a convex combination of weights from the previous phase. Specifically, node $i$ will always use the most up-to-date value of its own state, which is no longer a state of the previous phase.

    However, this state may still be represented as a \textit{combination} of weights of the previous phase: in iteration $t$, node $i$ uses state of node $i$ in iteration $t-1$. Iteration $t-1$ of phase $a$ is represented by row $h(t-1)+i$ of matrix M:
    \begin{equation}
        v_{i}(i) = M_{h(t-1) + i} * v[a]
    \end{equation}

    Therefore, instead of using a single weight to denote the state of node $i$ in iteration $t-1$, we may instead add every single weight of row $h(t-1)+i$ to row $ht + i$, scaled by a factor of $\frac{1}{hD}$. The induction step is completed by setting $k$ as t.
\end{proof}

We now describe specific characteristics of which weights are non-zero in transition matrix $M$:

We first note the existence of a diagonal of non-zero values at the rightmost $h$ columns of the transition matrix.
\begin{theorem} \label{T2}
   $\forall k, i$ such that $k, i \in \mathbb{R}$, $0\leq k < D$ and $0 \leq i \leq h$, $M_{kh + i, h(D-1) + i}$ is a non-zero value.
\end{theorem}

\begin{proof}
    For $k=0$, row $kh+i$ represents the update of node $i$ during iteration 0, or the first iteration of the previous phase. Column $h(D-1) + i$ represents the state of node $i$ during iteration $D-1$ of the previous phase, or the last iteration of the previous phase. Since each honest node always uses the state of the previous iteration in its update, this matrix value is non-zero.

    For $k>0$, the result generalizes from Theorem \ref{T1}.
\end{proof}

\begin{figure} [ht]

$\left[\begin{matrix}
0 & 0 & \frac{1}{3} & \boldsymbol{\frac{1}{3}} & \frac{1}{3} & 0\\[6pt]
0 & 0 & 0 & \frac{1}{3} & \boldsymbol{\frac{1}{3}} & \frac{1}{3}\\[6pt]
\frac{1}{3} & 0 & 0 & 0 & \frac{1}{3} & \boldsymbol{\frac{1}{3}}\\[6pt]
0 & 0 & \frac{1}{9} & \boldsymbol{\frac{2}{9}} & \frac{2}{9} & \frac{4}{9}\\[6pt]
\frac{1}{9} & 0 & \frac{1}{9} & \frac{2}{9} & \boldsymbol{\frac{1}{3}} & \frac{2}{9}\\[6pt]
\frac{1}{9} & 0 & 0 & \frac{4}{9} & \frac{2}{9} & \boldsymbol{\frac{2}{9}}
\end{matrix}\right]$
    \centering
    \caption{A sample matrix illustrating Theorem \ref{T2}, with $h=3$ and $D=2$ is shown.}
    \label{fig:1}
\end{figure}

Now we introduce some definitions relating to the network graph.

\theoremstyle{definition}
\begin{definition}{Complete Graph:}
A complete graph is a graph with vertex set $V$, and edge set $E'$, such that $\forall i,j, i \neq j: (i,j) \in E'$. The graph contains $b$ byzantine nodes, $h$ honest nodes, and $\|V\| = m$.
\end{definition}

A complete graph describes the de-facto communication during an entire phase: since the longest path between any two honest nodes is at most $D$, any two nodes may communicate with each other for at least one iteration during every single phase. We now introduce a graph that represents the network graph after the trimming in (\ref{update}).

\theoremstyle{definition}
\begin{definition}{Reduced Graph:}
A reduced graph is a complete graph with all nodes in set $B$ removed, along with their incoming and outgoing edges. Additional, we remove any arbitrary set of $b$ incoming edges from each remaining node. Note that there are several reduced graph for every complete graph, but only a finite number of them. Define $R_{f}$ to be the set of all reduced graphs for a given complete graph, and define $r$ as $\| R_{f} \|$. Note that this definition comes from \cite{Transition}.

Note that even though nodes do not have edges connecting to themselves, they can also "send" messages to themselves. Thus the adjacency matrix $A$ of a reduced graph will always be non-zero at $A_{ii}, \forall i\in V$
\end{definition}

The reduced graph represents the communication links between the entire graph after trimming is done.

We introduce one last theorem describing the qualities of transition matrix $M$.
\begin{theorem} \label{T3}
   Every Node $i$ row contains a non-zero value in column $z$, where $z \bmod h$ is a node with an incoming edge of node $i$ in some reduced graph in $R_{f}$
\end{theorem}
\begin{proof}
    For rows $t$ such that $\lfloor\frac{t}{h}\rfloor = 0$ (which correspond to the updates of node $i$ in iteration 0), we note that every single node received some message from every other node from the previous phase. The reduced graph represents some form of trimming of all incoming information, where an incoming edge of the reduced graph represents an incoming state that is not trimmed. Column $z \bmod h \cong j$, column $z$ represents a state of node $j$. The theorem is proven by induction.

    \paragraph{Base Step}
    The base step is proven in \ref{appendix A}

    \paragraph{Induction Step}
    For rows $t$ such that $\lfloor\frac{t}{h}\rfloor > 0$, the result generalizes from Theorem \ref{T1}
\end{proof}

This theorem describes how every state update in the matrix is based off of at least one weight corresponding to each node in the graph.

\subsubsection{Transition Matrix Behavior}
To prove convergence, we show that a finite number of matrices in the transition matrix product forms a non-zero column in the stochastic matrix (scrambling matrix). This guarantees that the matrix $\lim_{T\to\infty} \prod_{t=0}^{T} M[t]$ has identical rows, which in turn ensures the convergence condition \cite{Transition, Wolfowitz}.

To do this, we introduce a repeated matrix product $Q[t]$, which represents a repeated product of $2rD+1$ matrices. Specifically, we define the following:
\begin{equation}
    Q[t] = \prod_{i=t(2rD+1)}^{(t+1)(2rD+1)} M[i]
\end{equation}

We may write our transition matrix update thus as:
\begin{equation}
    v[T] = \prod_{t=0}^{T / (2rD+1)} Q[t]*v[0]
\end{equation}

Now we introduce a new theorem that explains the behavior of transition matrices.

 \theoremstyle{definition}
\begin{definition}{Matrix Inequality:}
We define matrices $A < B$ iff $\forall i, j: A_{ij} < B_{ij}$.
\end{definition}

\begin{theorem} \label{T4}
   $\forall t$, matrix $Q[t]$ contains at least one non-zero column within the last $n$ columns of the matrix.
\end{theorem}
\begin{proof}
   We introduce Lemma \ref{L1}, which explains how the product of two transition matrices creates a $h \times h$ adjacency matrix of a reduced graph at the bottom right corner of the matrix.

 \begin{lemma} \label{L1}
    Define $M^1 * M^2$ to be two arbitrary transition matrices constructed from Algorithm \ref{construction}. $M^1 * M^2[h(D-1) + 1, hD : h(D-1) + 1, hD] \geq \beta*r_{f}$, where $r_{f}$ is the adjacency matrix of some reduced graph and $\beta$ is some positive constant \cite{Transition}.
 \end{lemma}
 \begin{proof}
    The proof is derived from Theorem \ref{T3}. Within any row of matrix $M^1$, if there is a non-zero value in column $z$, where $z \bmod h \cong j$, then there will be a non-zero value in column $h(D-1) + j$ of matrix $M^1 * M^2$. This is due to diagonals of Theorem \ref{T2} in matrix $M^2$.
 \end{proof}

 We now use a key result of \cite{Transition} to show the generation of a partial non-zero column in this bottom-right matrix.

 \begin{lemma} \label{L2}
    The product of $2rD$ arbitrary transition matrices (denoted as $Z$) results in a non-zero column of the matrix $Z[h(D-1) + 1, hD : h(D-1) + 1, hD]$.
 \end{lemma}
 \begin{proof}
     From Lemma \ref{L1}, the product of $2rD$ transition matrices can be represented as a product of $rD$ matrices, where each matrix has some arbitrary adjacency matrix of a reduced graph in its bottom rightmost $h \times h$ submatrix. Given that $\|R_{f}\| = r$, by the pigeonhole principle, we can conclude that at least one arbitrary reduced graph is repeated at least $D$ times. In Appendix \ref{appendixB}, it is also proven that there exists a directed path from some node to all other nodes in all reduced graphs. Since the shortest directed path of between any two honest nodes is at most length $D$, it is proven in \cite{Transition} that a non-zero column is formed in matrix $Z[h(D-1) + 1, hD : h(D-1) + 1, hD]$
 \end{proof}

 Given that matrix $Z$ has a non-zero column in the bottom rightmost $h \times h$ matrix, it can be shown that $Z*M$, where $M$ is an arbitrary transition matrix, creates a non-zero column of the entire matrix in the same column where the $h \times h$ matrix column was. This is once again due to the diagonals of Theorem \ref{T2} and a simple application of linear algebra.

 Given that $Z$ represents the product of $2rD$ matrices and $M$ represents a single transition matrix, we have shown that the product of $2rD+1$ transition matrices creates a non-zero column. This concludes the proof of Theorem \ref{T4}.
\end{proof}

\begin{figure}

$\left[\begin{matrix}
0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 & 0\\[6pt]
0 & 0 & 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\[6pt]
\frac{1}{3} & 0 & \frac{1}{3} & 0 & 0 & \frac{1}{3}\\[6pt]
0 & 0 & \frac{1}{9} & \frac{2}{9} & \boldsymbol{\frac{2}{9}} & \frac{4}{9}\\[6pt]
\frac{1}{9} & 0 & \frac{1}{9} & \frac{2}{9} & \boldsymbol{\frac{1}{3}} & \frac{2}{9}\\[6pt]
\frac{1}{9} & 0 & 0 & \frac{4}{9} & \boldsymbol{\frac{2}{9}} & \frac{2}{9}
\end{matrix}\right]$
    \centering
    \caption{A sample matrix $Z$ with a non-zero column in the bottom rightmost $h \times h$ matrix.}
    \label{fig:2}
\end{figure}

\begin{figure}
$\left[\begin{matrix}
0 & 0 & \frac{1}{3} & \frac{1}{3} & \boldsymbol{\frac{1}{3}} & 0\\[6pt]
0 & 0 & 0 & \frac{1}{3} & \boldsymbol{\frac{1}{3}} & \frac{1}{3}\\[6pt]
\frac{1}{3} & 0 & 0 & 0 & \boldsymbol{\frac{1}{3}} & \frac{1}{3}\\[6pt]
0 & 0 & \frac{1}{9} & \frac{2}{9} & \boldsymbol{\frac{2}{9}} & \frac{4}{9}\\[6pt]
\frac{1}{9} & 0 & \frac{1}{9} & \frac{2}{9} & \boldsymbol{\frac{1}{3}} & \frac{2}{9}\\[6pt]
\frac{1}{9} & 0 & 0 & \frac{4}{9} & \boldsymbol{\frac{2}{9}} & \frac{2}{9}
\end{matrix}\right]$
    \centering
    \caption{A sample matrix $Z*M$ with a non-zero column in the entire matrix in the same column as the partial non-zero column of Figure \ref{fig:2} above.}
    \label{fig:3}
\end{figure}

\begin{theorem} \label{T7}
   $\lim_{T\to\infty} v[T] = c* \textbf{1}$, where $c$ is some constant and $\textbf{1}$ is the column vector of ones. Note this proves the convergence condition.
\end{theorem}
\begin{proof}
    \begin{align*}
       \lim_{T\to\infty} v[T] = \\
       \lim_{T\to\infty} \prod_{t=0}^{T} M[t]*v[0] = \\
       \lim_{T\to\infty} \prod_{t=0}^{T / (2rD+1)} Q[t]*v[0]
    \end{align*}

    From Theorem \ref{T4}, we have shown that $\forall t$, matrix $Q[t]$ contains at least one non-zero column. Since $Q[t]$ is also stochastic, it is a scrambling matrix. \cite{Transition} proves that the product of any infinite number of scrambling matrices converges to a matrix with identical rows. Thus the product $\prod_{t=0}^{T / (2rD+1)} Q[t]*v[0]$ results in a column vector with identical elements, proving the theorem.
\end{proof}

\section*{Acknowledgements}
First of all, I would like to thank MIT and the MIT PRIMES program for giving me this wonderful opportunity to conduct research.

I'd like to thank Jun Wan, Prof. Lili Su, and Prof. Nitin Vaidya for all of our discussions. Finally, the biggest thanks goes out to my research mentor, Hanshen Xiao, for all of his support and guidance.

\bibliographystyle{IEEEtran}


\section{Introduction}\label{Introduction}
In \cite{PSW}, the authors prove a positive mass theorem using properties of the causal structure of spacetime. The proof has the advantage of relying specifically on properties of spacetime which one would expect to be characteristic of positive mass, in particular the focusing and retarding of null geodesics which pass near the source (as well as the corresponding relative time advancement of geodesics passing far from the source). Conversely, null geodesics which pass far from a negative mass source will be delayed relative to those which pass nearby. This is used to show that a certain class of negative mass spacetimes must contain a null line as defined by Galloway \cite{Galloway}:
\begin{definition}
A null line is an inextendible null geodesic which is achronal. In particular, null lines cannot contain conjugate points.
\end{definition}

On the other hand, under certain conditions (see for example Theorem \ref{thm:Borde} in section \ref{A Focusing Theorem in Higher Dimensions}) it is possible to prove that such a null line must exist. This allows us to prove a positive mass theorem among spacetimes satisfying these conditions (Corollary \ref{cor}). If the Einstein equations are assumed, these conditions usually amount to demanding some sort of local positivity of energy.

The proof in \cite{PSW} concerns only $3+1$ dimensional spacetimes and relies upon the fact that null geodesics become infinitely delayed as we let their distance of closest approach to a negative mass source tend to infinity (see \cite{Penrose} for further discussion). As discussed in \cite{PCMD} for the specific example of the Schwarzschild metric, this effect becomes vanishingly small in higher dimensions (i.e. in $D+1$ dimensions with $D\geq4$), owing to the faster decay at infinity of the leading order non-Minkowski terms in the metric. Indeed, \cite{PSW} contains a brief discussion of this point and notes that this prevents the proof given from immediately generalising to higher dimensions.

In \cite{poorman2}, the result is generalised to include higher dimensions (albeit with a more restrictive class of metrics than those considered in \cite{PSW}). The assumptions made in this paper are weaker than those of \cite{poorman2} - namely we will require the metric to be \textit{asymptotically Schwarzschildean} (Definition \ref{defn:asymptoticallyschwarzschildean}) rather than the more restrictive assumption that it is \textit{strongly uniformly Schwarzschildean} (\cite{poorman2} Section 1). We will also drop the assumption in \cite{poorman2} that the metric is stationary. On the other hand, unlike in \cite{poorman2}, we will be unable to obtain a rigidity result concerning the zero mass case. Our proof will also apply only to higher dimensions. We hope that this method of proof will prove enlightening as it is closer in spirit to the methods employed in \cite{PSW}, namely the construction of a null line as a \textit{fastest causal curve} (Section \ref{Constructing a Fastest Causal Curve}) between two generators of past and future null infinity.

The theorem we will prove is the following (see later sections for definitions of various terms):
\begin{thm}\label{thm:nullline}
Let $(M,g)$ be an asymptotically Schwarzschildean spacetime in $D+1$ dimensions with ADM mass $m_{ADM}<0$ such that $\mathcal{D}\cup\mathcal{I}$ is globally hyperbolic as a subset of $\tilde{M}$. Then $(M,g)$ contains a null line.
\end{thm}

For $3+1$ dimensional spacetimes, the proof in \cite{PSW} proceeds by constructing a ``fastest causal curve'' between a generator, $\Lambda^-$, of past null infinity (denoted $\mathcal{I}^-$) and a generator, $\Lambda^+$, of future null infinity (denoted $\mathcal{I}^+$). We say that a causal (i.e. nowhere spacelike) curve is ``faster'' than some other if it departs $\mathcal{I}^-$ no earlier and arrives at $\mathcal{I}^+$ no later. A fastest causal curve (if it exists) is defined to be such that no other causal curve is faster.

In order to specify the generator $\Lambda^+$, we specify some radial, outgoing, future pointing, Minkowski-null direction\footnote{We follow Penrose's ``abstract index notation'' where Latin indices label the rank of a tensor, while Greek indices denote the components of a tensor in some co-ordinate basis.} $k^a$. We then define $\Lambda^+$ to be the intersection of $\mathcal{I}^+$ with the set of null geodesics whose tangent vector asymptotes towards this direction at future null infinity. We similarly define $\Lambda^-$ as the intersection of $\mathcal{I}^-$ with the set of null geodesics with tangent vector asymptoting to $-k^a$ at past null infinity. In this paper we will restrict attention to a quasi-Cartesian frame (Definition \ref{defn:quasicart}) and choose co-ordinates $(x_0,x_1,...,x_D)$ such that $k^a$ has components $k^\mu=(1,0,...,0,1)$ in this frame.

The key Lemma in \cite{PSW} is Lemma III.2.1. This gives an estimate of the ``time of flight" along a curve comprised of the union of two null geodesics joined at a point\footnote{Note that our choice of co-ordinates such that $k^\mu=(1,0,...,0,1)$ ensures our curve must pass through such a point. We are using the ``mostly plus'' signature (-,+,...,+).} with $x_D=0$ and with endpoints on $\Lambda^\pm$. The time of flight is defined to be the retarded time of arrival on $\Lambda^+$ minus the advanced time of departure from $\Lambda^-$ (where these are defined using the Hamilton-Jacobi functions describing null geodesics with endpoints on $\mathcal{I}^+$ and $\mathcal{I}^-$ respectively - see \cite{PSW}). This quantity is shown to behave asymptotically like
\begin{equation}\label{eqn:timeofflightestimate}
    4P\cdot k\log(b_0/R_0)
\end{equation}
where $P^a$ is the ADM 4-momentum of the spacetime \cite{ADM}, $b_0$ is the value of $r=\sqrt{\sum\limits_{i=1}^{D}x_i^2}$ (defined using quasi-Cartesian co-ordinates) at the point where the null geodesics join, and $R_0$ is a positive constant.

Suppose $P\cdot k>0$, i.e. the 4-momentum of the spacetime is not future causal. The aim is to show that there must then exist a fastest causal curve from $\Lambda^-$ to $\Lambda^+$ which enters the interior of the spacetime. If this is the case then the curve must lie on the boundary of the causal future of some point $p\in\Lambda^-$, denoted $\partial J^+(p)$ which is equal to $\partial I^+(p)$. As a result this curve must lie entirely in the boundary of the future null cone from $p$ and hence must be a null geodesic (\cite{Wald} Corollary after Theorem 8.1.2) without conjugate points (\cite{HawkingEllis} Proposition 4.5.12).

The construction begins by finding points $p\in\Lambda^-$, $q\in\Lambda^+$ such that there is no causal curve which departs $\Lambda^-$ later than $p$ and arrives at $\Lambda^+$ earlier than $q$. These will be the endpoints of the fastest causal curve, $\gamma$, to be constructed. Consider a sequence of causal curves, $(\gamma_i)_{i=0}^\infty$, with endpoints on $\Lambda^\pm$ which tend towards $p$ and $q$ and with $\gamma_i$ faster than $\gamma_j$ for $i>j$. The curve $\gamma$ is defined to be the ``limit'' of this sequence of causal curves, where we use the fact that, in a globally hyperbolic set, the space of causal curves between two compact sets is compact (\cite{SorkinWoolgar} Theorem 23).

It remains to check that $\gamma$ does in fact enter the interior of the spacetime and hence define a null line.  We can modify the curves $(\gamma_i)_{i=0}^\infty$ (possibly making them faster) so that they consist of two null geodesics joined at a point with $x_D=0$, $r=b_0$. This means that the estimate (\ref{eqn:timeofflightestimate}) now applies. If we were to have $b_0\rightarrow\infty$ as $i\rightarrow\infty$ then this estimate tells us that the time of flight along $\gamma_i$ would also diverge to $+\infty$ as $i\rightarrow\infty$. In particular, the sequence ($\gamma_i)^\infty_{i=0}$ would eventually become slower than $\gamma_0$. This contradicts the definition of the sequence, so we conclude that $b_0$ must not diverge along the sequence and hence, possibly restricting to a subsequence, all of the $\gamma_i$ must enter the compact set defined by $r\leq B_0$ for some fixed $B_0>0$. Once again using the compactness result of \cite{SorkinWoolgar}, we conclude that $\gamma$ must also enter this set, and hence must enter the interior of the spacetime. We therefore conclude that $\gamma$ is a null line.

This proof does not generalise to higher dimensions because the time of flight of curves restricted to arbitrarily large values of $r$ no longer diverges. Instead, the time of flight estimate (\ref{eqn:timeofflightestimate}) is replaced by Lemma \ref{lemma:timeofflight}. This says that the time of flight tends to 0 as we let $b\rightarrow\infty$, where $b$ denotes the impact parameter, defined to be the minimal value of $r$ along the curve.

However, this result combined with ideas from \cite{PCMD} turns out to be sufficient to construct a null line for negative mass spacetimes in higher dimensions (with some slightly modified assumptions). In particular, we generalise a result of \cite{PCMD} to show that, by a comparison argument involving a Minkowski metric on a neighbourhood of conformal infinity, the presence of negative mass allows us to construct a Minkowski-null curve from $\Lambda^-$ to $\Lambda^+$ which is timelike with respect to the physical metric $g$. To do this, we show that for such spacetimes the Minkowski null cones at sufficiently large $r$ are contained inside the $g$-null cones. Defining retarded and advanced time co-ordinates as in Equation \ref{eqn:retadv}, it is a straightforward calculation to show that the time of flight along a Minkowski null geodesic is exactly zero. As a result, if we choose a $\eta$-null geodesic restricted to sufficiently large values of $r$, then this curve must be timelike with respect to the metric $g$. Then since the timelike future of any point is an open set, it must be possible to modify this curve slightly and obtain a $g$-timelike curve, $\gamma_0$, between $\Lambda^-$ and $\Lambda^+$ which has time of flight strictly less than zero. This allows us to use a similar construction as was used in $3+1$ dimensions based on a sequence of faster and faster causal curves $(\gamma)_{i=0}^\infty$ from $\Lambda^-$ to $\Lambda^+$. If $b\rightarrow\infty$ along this sequence then we will eventually get a time of flight larger than that of $\gamma_0$. As in 3+1 dimensions, this allows us to conclude that a fastest causal curve from $\Lambda^-$ to $\Lambda^+$ does exist. This completes the proof of Theorem \ref{thm:nullline}.

\section{Definitions and Assumptions}\label{Definitions and Assumptions}
In order to carry out the comparison with Minkowski spacetime mentioned in the previous section, it will be necessary to impose stronger conditions than those used in \cite{PSW}. These assumptions will be more similar to the ones used in \cite{poorman} and \cite{poorman2}. In this section we outline the various assumptions used.
\begin{definition}\label{defn:spacetime}
A \textit{spacetime} $(M,g)$ is a connected manifold $M$ of dimension $D+1$, where $D\geq3$, equipped with a $C^1$ Lorentzian metric $g$ of signature $(D,1)$.
\end{definition}
For the purposes of Theorem \ref{thm:nullline}, requiring the metric to be $C^1$ will be sufficient. In order to obtain a focusing result in Section \ref{A Focusing Theorem in Higher Dimensions}, it may be necessary to make stronger assumptions. For example, in Theorem \ref{thm:Borde} we assume that the metric is $C^2$.
\begin{definition}\label{defn:quasicart}
A spacetime $(M,g)$ admits \textit{quasi-Cartesian co-ordinates} if there are co-ordinates, defined on some subset of $M$ diffeomorphic to $\mathbbm{R}\times\mathbbm{R}^D\setminus B$ (where $B$ denotes a closed ball in $\mathbbm{R}^3$ centred on the origin), with respect to which the components of the metric, $g$, take the form
\begin{equation}
    g_{\mu\nu}=\eta_{\mu\nu}+h_{\mu\nu}
\end{equation}
where for the purposes of Lemma \ref{lemma:timeofflight} it will be sufficient to assume that $h_{\mu\nu}=O\left(r^{1+\delta}\right)$ for some $\delta>0$.
\end{definition}

We will show in Section \ref{A Focusing Theorem in Higher Dimensions} that such spacetimes are weakly asymptotically empty and simple as defined in \cite{PCMD}. In particular, they admit a conformal compactification $(\tilde{M},\tilde{g})$ defined on the same manifold as a conformal compactification of Minkowski spacetime. As in $\cite{PSW}$, we actually assume that $\tilde{M}$ extends slightly past infinity so that it is indeed a manifold.

Requiring that a spacetime admits quasi-Cartesian co-ordinates will allow us to prove Lemma \ref{lemma:timeofflight}, however in order to construct a null line we will need to consider a more restrictive class of metrics. Recall that the $D+1$ dimensional Schwarzschild metric with ADM mass $m_{ADM}\in\mathbbm{R}$, which we denote $g_m$, has line element
\begin{equation}\label{eqn:Schwarzschild}
    ds_m^2=-\left(1-\frac{2m}{r^{D-2}}\right)dt^2+\frac{dr^2}{1-\frac{2m}{r^{D-2}}}+r^2d\omega^2_{D-1}
\end{equation}
where $d\omega^2_{D-1}$ is the round line element on the unit $(D-1)$-sphere, $S^{D-1}$, and the \textit{mass parameter}, $m$, is related to the ADM mass $m_{ADM}$ by\footnote{We work in units in which $c=G=1$.}
\begin{equation}\label{eqn:mass}
    m_{ADM}=\frac{(D-1)Area(S^{D-1})}{8\pi}m
\end{equation}
\begin{definition}\label{defn:asymptoticallyschwarzschildean}
We say that a metric $g$ on $\mathbbm{R}\times\left(\mathbbm{R}^D\setminus B\right)$, $R^{D-2}>m/2$, is \textit{asymptotically Schwarzschildean} with ADM mass $m_{ADM}\neq0$ (related to the parameter $m$ by Equation \ref{eqn:mass}) if, in the co-ordinates of \ref{eqn:Schwarzschild} (or equivalently in the co-ordinates of eqn (1) of \cite{poorman}):
\begin{equation}
    g-g_m=o\left(|m||x|^{-(D-2)}\right)
\end{equation}
We will say that a metric is asymptotically Schwarzschildean with mass $0$ if it is flat for $r>R$, for some $R\in\mathbbm{R}_{\geq0}$.\footnote{This definition will not be important since we will be unable to comment on the $m=0$ case.}
\end{definition}
Note that the conditions imposed on the spacetime are less restrictive than the ones used in \cite{poorman2}, where the spacetime is assumed to be \textit{strongly uniformly Schwarzschildean} (although as discussed in section \ref{Conclusion}, the result we obtain is weaker since we are unable to comment on the $m=0$ case). Physically this assumption seems reasonable. It says that, near infinity, a localised matter distribution will resemble a point mass to first approximation.

We will also refer to the following sets:
\begin{equation}
    \begin{split}
        J^+(p)&=\{q\in\tilde{M}|\exists\text{ a smooth future-directed causal curve from $p$ to $q$}\}\\
        J^-(p)&=\{q\in\tilde{M}|p\in J^+(q)\}\\
        I^+(p)&=\{q\in\tilde{M}|\exists\text{ a smooth future-directed timelike curve from $p$ to $q$}\}\\
        I^-(p)&=\{q\in\tilde{M}|p\in I^+(q)\}\\
    \end{split}
\end{equation}
For non-compact spacetimes, $(M,g)$, we can define the same sets as subsets of $M$ rather than as subsets of $\tilde{M}$.

In Theorem \ref{thm:nullline}, we will require that $\mathcal{D}\cup\mathcal{I}$ be globally hyperbolic as a subset of $\tilde{M}$, where $\mathcal{D}$ denotes the \textit{domain of outer communications} $\mathcal{D}=I^-(\mathcal{I}^+)\cap I^+(\mathcal{I}^-)$ and $\mathcal{I}=\mathcal{I}^+\cup\mathcal{I}^-$. By this we mean that $\mathcal{D}\cup\mathcal{I}$ is strongly causal and contains $J^+(p)\cap J^-(q)$ as a compact subset for each $p,q\in\mathcal{D}\cup\mathcal{I}$ (\cite{HawkingEllis} Section 6.6).

\section{Time of Flight Estimate in Higher Dimensions}\label{time of flight Estimate in Higher Dimensions}
In this section we will derive a higher dimensional analogue of Lemma III.2.1 in \cite{PSW} which gives an estimate for the time of flight of causal curves near infinity with endpoints on $\Lambda^\pm$. In \cite{PSW} it was found that the time of flight diverged logarithmically as we considered curves restricted to increasingly large values of $r$. In higher dimensions, we show that the time of flight tends to $0$ as we let the impact parameter approach infinity. The difference between the two estimates is the reason the 3+1 dimensional proof given in \cite{PSW} could not be generalised to higher dimensions. In \cite{PSW}, the authors make the point that, to first order, the ``phase delay'' along a $g$-null geodesic consists of two contributions. These consist of the phase delay due to the perturbation to the background metric as well as the contribution due to the subsequent bending of geodesics. The authors only consider the first of these effects, arguing that the second will be sub-leading. Since we will require the phase delay along a geodesic to tend to zero as this geodesic is restricted to arbitrarily large values of $r$, we will need to consider both effects together.

\begin{lemma}(\textbf{Time of Flight Estimate}) \label{lemma:timeofflight}
Let $(M,g)$ be a spacetime in $D+1$ dimensions which admits quasi-Cartesian co-ordinates and let $\gamma$ be a causal curve which connects $\Lambda^-$ to $\Lambda^+$. Let $b$ denote the impact parameter (the minimum value of $r$ along $\gamma$). Then the time of flight along $\gamma$ tends to zero as $b\rightarrow\infty$.
\end{lemma}

\textbf{Proof}: We begin by showing that, for spacetimes admitting quasi-Cartesian co-ordinates as in Definition \ref{defn:quasicart}, the co-ordinates
\begin{equation}\label{eqn:retadv}
    \begin{split}
        u=t-r\\
        v=t+r
    \end{split}
\end{equation}
are good co-ordinates on $\mathcal{I}^+$ and $\mathcal{I}^-$ respectively. Recall that for Schwarzschild in $3+1$ dimensions, we use the retarded and advanced time co-ordinates
\begin{equation}
    \begin{split}
        u_s&=t-r-2m\log(r/2m-1)\\
        v_s&=t+r+2m\log(r/2m-1)
    \end{split}
\end{equation}
where $m$ is the mass of the spacetime and the quantities $t-r$ and $t+r$ diverge along outgoing and ingoing radial null geodesics respectively. This divergence means that $u$ and $v$ are not good co-ordinates on $\mathcal{I}^+$ and $\mathcal{I}^-$ in this spacetime.

Another way of saying this is that the Hamilton-Jacobi functions $S^\pm$ defined for $(M,g)$ as in \cite{PSW} agree with $u$ and $v$ at infinity. We will define the (possibly negative) time of flight along an endless curve as $u_\infty-v_\infty$, where $u_\infty$ denotes the value of $u$ at the future endpoint of the curve and $v_\infty$ denotes the value of $v$ at its past endpoint.

Consider a future endless $g$-null curve whose direction approaches $k^\mu$ as the affine parameter $\tau\rightarrow\infty$. We see that this curve becomes asymptotically radial in the far future. For a $g$-null curve, we have
\begin{equation}
    \begin{split}
    0&=\left(\frac{ds}{d\tau}\right)^2=-\dot{u}\dot{v}+r^2\dot{\omega}_{D-1}^2+h_{\mu\nu}\dot{x}^\mu\dot{x}^\nu\\
        \implies\dot{u}&=\frac{1}{\dot{v}}\left(r^2\dot{\omega}_{D-1}^2+h_{\mu\nu}\dot{x}^\mu\dot{x}^\nu\right)
    \end{split}
\end{equation}
where $\dot{\omega}_{D-1}^2$ denotes $\frac{d\boldsymbol{\omega}^2_{D-1}}{d\tau^2}$ and $d\boldsymbol{\omega}_{D-1}$ is an infinitesimal displacement on the unit $(D-1)$-sphere.

In Minkowski spacetime we have
\begin{equation}
    r^2\dot{\omega}_{D-1}^2=\frac{l^2}{r^2}
\end{equation}
for some constant $l$. For now we are only interested in what happens in the infinite future along a $g$-null curve. We see that
\begin{equation}
    \begin{split}
        r^2\dot{\omega}_{D-1}^2=O\left(1/r^2\right)
    \end{split}
\end{equation}
We also note that $\dot{x}^\mu=O(1)$ and hence that $\dot{v},\dot{r}=O(1)$. From this we deduce (assuming $\delta\leq1$, otherwise replace $\delta$ with 1 in what follows) that
\begin{equation}
    \begin{split}
        \dot{u}&=O\left(1/r^{1+\delta}\right)\\
        \implies \frac{du}{dr}&=O\left(1/r^{1+\delta}\right)\\
        \implies \Delta u&=O(1/r_*^\delta)
    \end{split}
\end{equation}
where $\Delta u$ denotes the change in $u$ along some future endless portion of $\gamma$ with past endpoint $p$ at which $r=r_*$ and along which $r$ is strictly increasing. Similarly, the time of flight along some past endless portion of $\gamma$ with future endpoint at $q$ and along which $r$ is decreasing must also be finite.
\begin{figure}
    \centering
    \includegraphics[scale=0.3]{gamma.png}
    \caption{The time of flight along both the future endless portion of $\gamma$ from $p$ and the past endless portion of $\gamma$ from $q$ (shown as unbroken lines) are both finite. The time of flight from $q$ to $p$ must be finite since these points both lie in the interior of the spacetime and therefore have finite values of the co-ordinates $t$ and $r$.}
    \label{fig:gamma}
\end{figure}
We therefore conclude that defining the time of flight along $\gamma$ as $u_\infty-v_\infty$, where $u_\infty$ denotes the value of $u$ on $\Lambda^+$ and $v_\infty$ denotes the value of $v$ at $\Lambda^-$, gives a finite quantity (note that the time of flight from $p$ to $q$ must be finite since both these points have finite values of $t$ and $r$ co-ordinates). This is shown in figure \ref{fig:gamma}. This shows that $g$-null geodesics have endpoints on $\mathcal{I}^\pm$ defined using the co-ordinates $u$ and $v$. In other words, we have shown that if $(M,g)$ admits quasi-Cartesian co-ordinates, then it can be conformally compactified using the same co-ordinate transformations and conformal factor as is used in the standard conformal compactification of Minkowski spacetime (see e.g. \cite{PCMD} Section 3).

From this we see that if we restrict our curve to arbitrarily large values of $r$, the time of flight along it must tend to $0$ (which is the value for a Minkowski-null curve). Indeed, suppose we define
\begin{equation}
\begin{split}
   \epsilon&=\frac{1}{b^{\delta/2}}\\ \Tilde{h}_{\mu\nu}&=r^{\delta/2} h_{\mu\nu}
   \end{split}
\end{equation}
Let $\tilde{\gamma}$ be a curve with endpoints on $\Lambda^\pm$ and which is comprised of two curves which are null with respect to the metric $\eta+\epsilon\Tilde{h}$. Note that $\Tilde{h}_{\mu\nu}=O(1/r^{1+\delta/2})$ (regarding $b$ as fixed), so by the above argument, the time of flight along $\Tilde{\gamma}$ is finite. It therefore makes sense to say that the time of flight along $\tilde{\gamma}$ is an $O(\epsilon)$ quantity. We can now consider the limit as $b\rightarrow\infty$. In this limit, $\epsilon\rightarrow0$ which means the time of flight along $\Tilde{\gamma}$ must tend to $0$. However we also note that
\begin{equation}
    |\epsilon\Tilde{h}_{\mu\nu}|\geq |h_{\mu\nu}|
\end{equation}
for each $\mu,\nu\in\{0,1,...,D\}$, so we conclude that the time of flight along $\gamma$ must also tend to $0$ as $b\rightarrow\infty$. \qedsymbol

Note that it would not have been sufficient to simply carry out the calculation to first order in $\epsilon$. This is because, before taking the limit as $b\rightarrow\infty$, we need to take another limit as the future endpoint of the curve tends to null infinity. It is not obvious that each of the terms in any expansion in powers of $\epsilon$ will be finite in this limit. The argument above fails for Schwarzschild in $3+1$ dimensions because $u_\infty-v_\infty$ is infinite along future endless null curves.

The above proof also shows that spacetimes which admit quasi-Cartesian co-ordinates are weakly asymptotically simple and empty as defined in \cite{PCMD} Definition 2.3. The compactification map is given by defining the compactified co-ordinates $T$ and $\chi$ as in \cite{PCMD} Equation 3.6. By showing that $u$ and $v$ as defined in Equation \ref{eqn:retadv} are finite in the infinite future and infinite past respectively of null geodesics, we have shown that null geodesics which do not enter black or white holes have endpoints on $\mathcal{I}^\pm$. This means it makes sense for us to talk about the compactification $(\tilde{M},\tilde{g})$ of the spacetime.
\section{Constructing a Fastest Causal Curve}\label{Constructing a Fastest Causal Curve}
As discussed in section \ref{Introduction}, we will begin by constructing a causal curve from $\Lambda^-$ to $\Lambda^+$ which has negative time of flight. To do this we use a comparison argument based on Minkowski spacetime, similar to the ones used in \cite{PCMD}. This argument relates to the compactified spacetimes.

\begin{lemma}\label{lemma:negativetimeofflight}
Let $(M,g)$ be an asymptotically Schwarzschildean spacetime in $D+1$ dimensions with ADM mass $m_{ADM}<0$. Then there exists an endless timelike curve from $\Lambda^-$ to $\Lambda^+$ which has negative time of flight $u_\infty-v_\infty$.
\end{lemma}

\textbf{Proof}: The metric is asymptotically Schwarzschildean to first order, so the line element can be written in some neighbourhood of conformal infinity as
\begin{equation}\label{eqn:lineeleement}
    \begin{split}
        ds^2=ds^2_{Mink}+\frac{2m}{r^{D-2}}\left(dt^2+dr^2\right)+o\left(r^{-(D-2)}\right)
    \end{split}
\end{equation}
where by $o\left(r^{-(D-2)}\right)$ we mean that this term is equal to $g'_{\mu\nu}dx^\mu dx^\nu$ for some $g'_{\mu\nu}=o\left(r^{-(D-2)}\right)$.

As shown in the proof of Lemma \ref{lemma:timeofflight}, the Minkowski space retarded and advanced time co-ordinates, $u$ and $v$, are finite along $g$-null geodesics. This means we can describe the compactified spacetime $(\Tilde{M},\Tilde{g})$ (or strictly speaking the submanifold diffeomorphic to $\mathbbm{R}\times\left(\mathbbm{R}^D\setminus B\right)$ of Minkowski where the quasi-Cartesian co-ordinates are defined) using compactified Minkowski co-ordinates. Furthermore, since the two compactifications are defined on the same manifold (i.e. neighbourhood of infinity), we can consider a curve in Minkowski spacetime (provided it lies entirely in this neighbourhood) as also defining a curve in the spacetime $(M,g)$.

Consider a Minkowski-null geodesic restricted to sufficiently large values of $r$ to ensure that the quasi-Cartesian co-ordinates are valid. It is clear from \ref{eqn:lineeleement} that for sufficiently large $r$, the term proportional to $m$ will dominate the other non-Minkowski terms. This means that if $m_{ADM}<0$ (or equivalently $m<0$) there exists some $r_0$ such that
\begin{equation}\label{eqn:bound}
    \begin{split}
        ds^2<ds^2_{Mink}
    \end{split}
\end{equation}
for all $r>r_0$.

Consider a Minkowski null geodesic with past endpoint at $v=0$ on $\Lambda^-$, future endpoint at $u=0$ on $\Lambda^+$ and impact parameter $b>r_0$. So this curve is restricted to the region where $r> r_0$ and hence inequality (\ref{eqn:bound}) guarantees that it is a $g$-timelike curve between the same two endpoints in $(\Tilde{M},\Tilde{g})$.\footnote{This argument only works in higher dimensions. In $3+1$ dimensions, although inequality (\ref{eqn:bound}) still holds, $g$-null geodesics are infinitely delayed or advanced compared to $\eta$-null geodesics (for $m\neq0$). As a result, $g$-null geodesics have endpoints at past and future timelike infinity in compactified Minkowski spacetime (for $m>0$) or at spatial infinity (for $m<0$). See \cite{Penrose} or \cite{PCMD} for more details.}

Now since $I^\pm(p)$ are open sets for any point $p\in \tilde{M}$, we must be able to modify this curve slightly so that it remains $g$-timelike but has past endpoint at $v>0$ on $\Lambda^-$ and future endpoint at $u<0$ on $\Lambda^+$. This ensures that the curve has negative time of flight (see Figure \ref{fig:negativeToF}).  \qedsymbol

We will use this curve as the starting point for our sequence of faster and faster causal curves used in the proof of Theorem \ref{thm:nullline} to construct a fastest causal curve from $\Lambda^-$ to $\Lambda^+$.

\textbf{Theorem \ref{thm:nullline}}. Let $(M,g)$ be an asymptotically Schwarzschildean spacetime in $D+1$ dimensions with ADM mass $m_{ADM}<0$ such that $\mathcal{D}\cup\mathcal{I}$ is globally hyperbolic as a subset of $\tilde{M}$. Then $(M,g)$ contains a null line.

\textbf{Proof:} Using Lemma \ref{lemma:negativetimeofflight}, we construct a causal curve from $\Lambda^-$ to $\Lambda^+$ which has negative time of flight. Denote this curve by $\gamma_0$ and label its past and future endpoints $p_0$ and $q_0$ respectively.
\begin{figure}
    \centering
    \includegraphics[scale=0.3]{NegativeToF.png}
    \caption{The Minkowski null path between $\Lambda^-$ and $\Lambda^+$ with endpoints at $u=0$ and $v=0$ respectively and impact parameter $b>r_0$ is shown as a dotted line. If the metric $g$ is asymptotically Schwarzschildean with negative mass then this path can be modified so that it still connects $\Lambda^-$ to $\Lambda^+$ but is $g$-timelike and has strictly negative time of flight.}
    \label{fig:negativeToF}
\end{figure}

Following \cite{PSW}, we introduce a partial ordering $\leq$ on $\left(\left(J^+(p_0)\cap \Lambda^-\right)\cup i^0\right)\times\left(\left(J^-(q_0)\cap \Lambda^+\right)\cup i^0\right)$. We say that $(p',q')\leq (p'',q'')$ if $p'\in J^+(p'')$ and $q'\in J^-(q'')$. Define the set $F$ to contain all pairs of points in $\left(J^+(p_0)\cap \Lambda^+\right)\times\left(J^-(q_0)\cap \Lambda^-\right)$ which can be connected by a causal curve through $\mathcal{D}$ and choose $(p,q)$ to be any element of the closure of this set which is minimal with respect to the partial ordering $\leq$ (so in principle one or both of these points could lie at $i^0$).

We can then define sequences of points $\{p_i\}_{i=0}^\infty$ along $\Lambda^-$ and $\{q_i\}_{i=0}^\infty$ along $\Lambda^+$ such that
\begin{itemize}
    \item $(p_i,q_i)\leq(p_j,q_j)$ for $i>j$
    \item $p_i$ and $q_i$ are connected by a causal curve $\gamma_i$
    \item $p_i\rightarrow p$ and $q_i\rightarrow q$ as $i\rightarrow\infty$
\end{itemize}
The first condition here ensures that the time of flight along $\gamma$ is less than or equal to the time of flight along $\gamma_j$ for $i>j$.

Next we use a result of Sorkin and Woolgar (\cite{SorkinWoolgar} Theorem 23)\footnote{As stated, this theorem only applies to open subsets of spacetime. However, as mentioned in Section \ref{Definitions and Assumptions}, we assume that $\tilde{M}$ extends slightly beyond infinity so that the set $\mathcal{O}:=\mathcal{D}\cup\mathcal{I}$ is open. Alternatively, one can define $p'\in\Lambda^-\cap J^-(p)$ and $q'\in\Lambda^+\cap J^+(q)$. Then, omitting finite subsequences if necessary, we may assume that all the $p_n$ lie in $K^+(p')$ and all the $q_n$ lie in $K^-(q')$, where $K^+$ is defined as in Definition 8 of \cite{SorkinWoolgar} and $K^-$ is defined similarly by replacing $I^+$ with $I^-$. From here on the proof continues unchanged.} to deduce that the sequence $(\gamma_i)_{i=0}^\infty$ tends towards a causal curve $\gamma$ with endpoints at $p$ and $q$. This convergence will be defined in the \textit{Vietoris topology} (see Appendix or \cite{SorkinWoolgar}). By definition, the curve $\gamma$ is a fastest causal curve from $\Lambda^-$ to $\Lambda^+$. It will also define a null line provided it enters the interior of the spacetime.

Suppose that $\gamma$ does not enter the interior of the spacetime. Following Lemma \ref{lemma:timeofflight}, we can choose $b$ sufficiently large that any causal curve from $\Lambda^-$ to $\Lambda^+$ with $r>b$ along its entire length has time of flight strictly greater than the time of flight of $\gamma_0$. But this contradicts the definition of the sequence $(\gamma_i)_{i=0}^\infty$ as consisting of faster and faster causal curves. We therefore conclude that, restricting to a subsequence if necessary, all of the causal curves $\gamma_i$ enter the ball $B_b=\{r\leq b\}$. But this set is compact, so from the definition of the Vietoris topology \cite{SorkinWoolgar}, the limit curve $\gamma$ must also enter this set.

We therefore conclude that a fastest causal curve from $\Lambda^-$ to $\Lambda^+$ which enters the interior of the spacetime does exist. \qedsymbol
\section{A Focusing Theorem in Higher Dimensions}\label{A Focusing Theorem in Higher Dimensions}
Theorem \ref{thm:nullline} shows that certain classes of higher dimensional, negative mass spacetimes must contain a null line.  This means negativity of mass would be impossible if we also impose conditions on the spacetime which forbid the existence of such a curve.

We will require conditions which ensure that endless null geodesics encounter sufficient regions of positive focusing to guarantee that conjugate points will occur. This focusing of geodesics is consistent with the sort of behaviour we would expect to be caused by regions of positive mass (assuming the Einstein equations hold). In this sense, Corollary \ref{cor} agrees with our prior understanding of positivity of mass.

In \cite{PSW}, the conditions imposed are those stated in Borde's Focusing Theorem \cite{Borde} (where we now assume that the metric is $C^2$):
\begin{thm}(\textbf{Focusing Theorem 2 \cite{Borde}})\label{thm:Borde}
Let $\gamma$ be a complete, affinely parametrized, causal geodesic with tangent $T^a$ such that $T_{[a}R_{b]cd[e}T_{f]}T^cT^d\neq0$ at some point on $\gamma$. Suppose that for any $\epsilon>0$ and any $t_1<t_2$, there exists $\delta>0$ and intervals $I_1$ and $I_2$ of length $\geq\delta$ with endpoints $<t_1$ and $>t_2$ respectively such that
\begin{equation}
    \int_{t'}^{t''}R_{ab}T^aT^bdt\geq-\epsilon \quad\quad\forall t'\in I_1,\quad \forall t''\in I_2
\end{equation}
Then $\gamma$ contains a pair of conjugate points.
\end{thm}
Theorem \ref{thm:Borde} was stated in $3+1$ dimensions, although the proof does not rely on this and so also holds in higher dimensions. For this reason, we may use the conditions of this theorem in our higher dimensional generalisation of the positive mass theorem.

It may be the case that we can impose weaker conditions than those used in Borde's theorem and still rule out the existence of null lines. For example, Theorem \ref{thm:nullline} only required the metric to be $C^1$, so a focusing result for metrics which fail to be $C^2$ would provide a more general result. This is mentioned at the end of Section II.2 in \cite{PSW} and in \cite{Perspectives}. The important thing is merely that we impose sufficiently strong conditions to ensure that such geodesics are ruled out. As is pointed out in \cite{PSW}, if we impose the Einstein equations on our spacetime, then the conditions of Borde's theorem can equivalently be expressed in terms of the energy-momentum tensor. The condition that $T_{[a}R_{b]cd[e}T_{f]}T^cT^d\neq0$ at some point on every geodesic is called the \textit{generic condition} and is satisfied for all but a very special class of spacetimes \cite{PenHaw}. As discussed in \cite{PSW}, it does not appear to be a particularly restrictive assumption. This is because if it is not satisfied by our spacetime, then we would expect it to be satisfied by some other spacetime which is ``nearby'' in some sense and whose 4-momentum differs by an arbitrarily small amount. As a result, imposing this assumption does not appear to weaken the positivity of mass result obtained in this paper or in \cite{PSW}.

Using Theorems \ref{thm:nullline} and \ref{thm:Borde}, we derive the following corollary, which is our version of the positive mass theorem in higher dimensions.
\begin{cor}\label{cor}
Let $(M,g)$ be an asymptotically Schwarzschildean spacetime in $D+1$ dimensions which satisfies the conditions of Borde's theorem and is such that $\mathcal{D}\cup\mathcal{I}$ is globally hyperbolic as a subset of $\tilde{M}$. Then $m_{ADM}\geq0$.
\end{cor}

\section{Conclusion}\label{Conclusion}
We have proved a version of the positive mass theorem for higher dimensional asymptotically Schwarzschildean spacetimes. As mentioned in section \ref{Definitions and Assumptions}, the assumptions made about the spacetime are weaker than those of \cite{poorman2}. In particular, we only require the metric to be asymptotically Schwarzschildean, whereas in \cite{poorman2} the more restrictive requirement that the metric be \textit{strongly uniformly Schwarzschildean} is made. We also drop the assumption of stationarity. However our result is less satisfactory in that we fail to prove anything specifically regarding the $m=0$ case (a similar problem is encountered in \cite{PSW}). This is because the method used in section \ref{Constructing a Fastest Causal Curve} to construct the timelike curve $\gamma_0$ with strictly negative time of flight is no longer guaranteed to work. Its success will be determined by the higher order terms in the metric.

The assumptions made in this paper are also fundamentally different to those used in the proofs by Witten \cite{Witten} and Schoen and Yau \cite{SchoenYau} (extended to all dimensions up to seven by Eichmeir, Huang, Lee and Schoen \cite{EHLS}). The proof given here relies on properties of the spacetime in a neighbourhood of conformal infinity whereas these other methods impose conditions only on some initial data surface. However, unlike these approaches, the proof contained here relies more clearly on properties we expect to hold in positive mass spacetimes. In particular, we show that null geodesic focusing is compatible only with spacetimes of non-negative mass. In this sense, the proof presented here also acts as evidence that it is consistent to think of the ADM mass defined in higher dimensions as describing the total mass contained in spacetime.
\subsection*{Acknowledgements} I am grateful to Maciej Dunajski, Greg Galloway, Roger Penrose, Harvey Reall, Paul Tod and Claude Warnick for useful discussions. I am also grateful to St. John's College, Cambridge for their support through a College Scholarship from the Todd/Goddard Fund. Some of this work was carried out while I was visiting Institut Mittag-Leffler in Djursholm, Sweden, where I was supported by the Swedish Research Council under grant no. 2016-06596.
\begin{appendices}
\section{Compactness of Causal Curves Following \cite{SorkinWoolgar}}
In this appendix we summarise how the convergence of the sequence of causal curves $(\gamma_i)_{i=0}^\infty$ is defined. We define $\gamma$ to be the limit of this sequence in the Vietoris topology \cite{SorkinWoolgar}. To understand this convergence, we follow \cite{Convergence} and make the following definitions:
\begin{definition}
The sequence of causal curves $(\gamma_i)_{i=0}^\infty$ converges to $\gamma$ in the \textit{upper topology} iff the $\gamma_i$ are eventually included in every open set which includes $\gamma$.
\end{definition}
\begin{definition}
The sequence of causal curves $(\gamma_i)_{i=0}^\infty$ converges to $\gamma$ in the \textit{lower topology} iff the $\gamma_i$ eventually meet every open set which meets $\gamma$.
\end{definition}
\begin{definition}
The sequence of causal curves $(\gamma_i)_{i=0}^\infty$ converges to $\gamma$ in the \textit{Vietoris topology} iff it converges in both the upper and lower topologies.
\end{definition}
Since we have assumed that $\mathcal{D}\cup\mathcal{I}$ is globally hyperbolic, if we were to  assume that the metric were $C^2$ (as in Theorem \ref{thm:Borde}) then these three definitions would coincide (\cite{SorkinWoolgar} Alternative Definition 26 and comments after proof of Lemma 28).
\end{appendices}