# Shape of the asymptotic maximum sum-free sets in integer lattice grids

Hong Liu Mathematics Institute, University of Warwick, UK. Email:
<EMAIL_ADDRESS>H.L. was supported by the UK Research and Innovation
Future Leaders Fellowship MR/S016325/1. Guanghui Wang School of Mathematics,
Shandong University, China. Email<EMAIL_ADDRESS>G.W. was supported by
Natural Science Foundation of China (11871311, 11631014) and seed fund program
for international research cooperation of Shandong University. Laurence
Wilkies Department of Computer Science, KU Leuven, Belgium. Email:
<EMAIL_ADDRESS> Donglei Yang Data Science Institute, Shandong
University, China, Email<EMAIL_ADDRESS>D.Y. was supported by the China
Postdoctoral Science Foundation (2021T140413) and Natural Science Foundation
of China (12101365).

###### Abstract

We determine the shape of all sum-free sets in $\\{1,\dots,n\\}^{2}$ of size
close to the maximum $\frac{3}{5}n^{2}$, solving a problem of Elsholtz and
Rackham. We show that all such asymptotic maximum sum-free sets lie completely
in the stripe $\frac{4}{5}n-o(n)\leq x+y\leq\frac{8}{5}n+o(n)$. We also
determine for any positive integer $p$ the maximum size of a subset
$A\subseteq\\{1,\dots,n\\}^{2}$ which forbids the triple $(x,y,z)$ satisfying
$px+py=z$.

##  1 Introduction

A cornerstone result of Schur [Sch16] states that for sufficiently large
integer $n$ and a fixed integer $r$, any $r$-coloring of $[n]:=\\{1,...,n\\}$
yields a monochromatic triple $x,y,z$ such that $x+y=z$. For an integer
$n\in\mathbb{N}$ a subset $A\subseteq[n]$ is _sum-free_ if it has no solution
for the equation $x+y=z$, i.e. for all $x,y\in A$ we have $x+y\notin A$. The
topic of sum-free sets of integers is well-studied in combinatorial number
theory and has a long history.

It is clear that the sets

$\displaystyle S_{1}$
$\displaystyle=\left\\{1,3,5,\dots,2\left\lfloor\frac{n-1}{2}\right\rfloor+1\right\\}\quad\text{
and }\quad
S_{2}=\left\\{\left\lceil\frac{n+1}{2}\right\rceil,\left\lceil\frac{n+1}{2}\right\rceil+1,\dots,n\right\\}$

are sum-free and of size $\left\lceil\frac{n}{2}\right\rceil.$ If $n$ is even,
$S_{3}=S_{2}-1$ is another one of the same size. Let us denote the density of
a maximum sum-free subset of $[n]$ by $\mu([n]):=\max\\{\frac{|S|}{n}\mid
S\subseteq[n],\textit{S is sum-free}\\}$. If $S\subseteq[n]$ is a sum-free set
and $a\in S$ is the largest element, then at most one of $x$ or $a-x$ can be
in $S$ for each $x\leq a.$ Therefore
$|S|\leq\left\lceil\frac{a}{2}\right\rceil\leq\left\lceil\frac{n}{2}\right\rceil$.
Together with the above examples, we see that

$\mu([n])=\left\\{\begin{array}[]{ll}\frac{1}{2}&\text{if $n$
even},\\\\[4.30554pt] \frac{1}{2}+\frac{1}{2n}&\text{if $n$ odd}.\\\
\end{array}\right.$

###  1.1 Structure for large sum free sets

Given the extremal result, great efforts has been made to better understand
the general structure of large sum-free sets in $[n]$. The first result on
this topic was due to Freiman [Fre92] who showed that if the size of a sum-
free set in $[n]$ is large enough, then it will either consist of all odd
numbers as in $S_{1}$ above or it will be close to second half of the interval
as $S_{2}$. We remark that more structural results are known for large sum-
free sets in $1$-dimensional integer lattice (see [DFST99] and a recent
progress [Tra18]). Such structual results are not only interesting on their
own; they have been utilized e.g. in recent work on enumerating maximal sum-
free sets (see [BLST18]).

The problem of sum-free sets has been generalized to higher dimensional
lattice $\mathbb{Z}^{d}$, $d\geq 2$. Similarly, we define
$\mu([n]^{d}):=\max\\{\frac{|S|}{n^{d}}\mid S\subseteq[n]^{d}\textit{ is sum-
free}\\}$. In particular, for $d=2$, the problem of finding the largest sum-
free subset of $[n]^{2}=\\{1,2,\cdots,n\\}^{2}$ was firstly presented by
Cameron as an unsolved problem in [Cam05].

######  Conjecture 1.1.

_[Cam05]_ There exists a constant $c\in\mathbb{R}$ such that
$\mu([n]^{2})=c+O(1/n).$

Cameron later [Cam02] suggested that Conjecture 1.1 is true with $c=0.6$ and
gave a lower bound construction:

$S_{0}=\\{(x,y)\in[n]^{2}\mid u\leq x+y\leq 2u-1\\},$

which has maximum density $0.6$ when $u=\lfloor\frac{4n+7}{5}\rfloor$.
Recently, Elsholtz and Rackham settled Conjecture 1.1 in [ER17], proving that
indeed

$\mu([n]^{2})=0.6+O(1/n).$

In the same paper, Elsholtz and Rackham [ER17] raised the problem of
classifying the sum-free sets whose size are close to the extremal value.

In this paper, we resolve this problem by showing that any sum-free subset
$S\subseteq[n]^{2}$ of size at least $(\frac{3}{5}-o(1))n^{2}$ will have all
its points in the region $\\{(x,y)\in[n]^{2}$ $|$ $\frac{4n}{5}-o(n)\leq
x+y<\frac{8n}{5}+o(n)\\}.$

######  Theorem 1.2.

For all $\gamma>0$ there exists $\delta>0$ and $n_{0}\in\mathbb{N}$ such that
the following holds for all $n>n_{0}$. If $S\subseteq[n]^{2}$ is sum-free with
$|S|>(\frac{3}{5}-\delta)n^{2}$, then

$S\subseteq\\{(x,y)\in[n]^{2}\mid\frac{4n}{5}-\gamma n\leq
x+y<\frac{8n}{5}+\gamma n\\}.$

This gives a satisfying answer to 2-dimension sum-free problem. The situation
is, however, unclear for higher dimension. In particular, even the maximum
density of a sum-free set in 3-dimension grid $[n]^{3}$ is unknown.

###  1.2 $(p,q)$-sum free sets

Given positive integers $d,n$ and rational numbers $p,q$, a set
$S\subseteq[n]^{d}$ is called $(p,q)$-_sum free_ if it has no solution for the
equation $px+qy=z$. As a generalization of sum free sets (i.e. (1,1)-sum free
sets), the notion of $(p,q)$-sum free sets encapsulates many fundamental
topics in combinatorial number theory. In particular, for $d=1$, a
$(\frac{1}{2},\frac{1}{2})$-sum free set is precisely a set without $3$-term
arithmetic progression, which has received considerable attention in recent
decades. Therefore, it is a natural question to determine the size of the
largest $(p,q)$-sum free sets in $[n]^{d}$. Here one can similarly define

$\mu_{[p,q]}([n]^{d}):=\max\left\\{\frac{|S|}{n^{d}}\mid
S\subseteq[n]^{d}\textit{ is $(p,q)$-sum-free}\right\\}.$

By Roth’s theorem [Rot53], $\mu_{[1/2,1/2]}([n])=o(1)$. See [Blo16] for the
best known upper bound for the size of a $(1/2,1/2)$-sum free set. In [Ruz93,
Ruz95], instead of the form $x+y=z$, Ruzsa instigated the study of more
general linear equations $a_{1}x_{1}+\cdots+a_{k}x_{k}=b$. In particular, for
more general cases when $p,q$ are positive integers and $p\geq 2$, Hancock and
Treglown [HT17] completely determined the value $\mu_{[p,q]}([n])$. For higher
dimensional lattices, Choi and Kim [CKP20] initiated the investigation of the
form $x_{1}+x_{2}+\cdots+x_{k}=b$, where $b$ is a prescribed points in
$[n]^{2}$.

For 2-dimension $(p,q)$-sum free problem, we make the first attempt to
determine $\mu_{[p,p]}([n]^{2})$ for any integer $p$.

######  Theorem 1.3.

Let $p\in\mathbb{N}$ and $S\subseteq[n]^{2}$ be a $(p,p)$-sum free set. Then

$|S|\leq\Big{(}1-\frac{2}{4p^{2}+1}\Big{)}n^{2}+O(n).$

We observe that the upper bound in Theorem 1.3 is optimal up to the error term
$O(n)$, given by the following construction. For any positive integers $p,q$
and positive real $a$, define $S=\\{(x,y)\in[n]^{2}\mid a<x+y<(p+q)a\\}$. One
can easily check that $S$ is $(p,q)$-sum free with size

$|S|=\left(1-\frac{2}{(p+q)^{2}+1}\right)n^{2}+O(n),$

when $a=\frac{2(p+q)}{(p+q)^{2}+1}n$, corresponding to the stripe

$S=\left\\{(x,y)\in[n]^{2}\mid\frac{2(p+q)}{(p+q)^{2}+1}n<x+y<\frac{2(p+q)^{2}}{(p+q)^{2}+1}n\right\\}.$

We conjecture that for all integers $p$ and $q$, the above construction
provides the maximum $(p,q)$-sum free set.

######  Conjecture 1.4.

Given positive integers $p,q$ and $n$, where $n$ is sufficiently large,

$\mu_{[p,q]}([n]^{2})=\left(1-\frac{2}{(p+q)^{2}+1}\right)+O(1/n).$

Organization. The rest of the paper will be organized as follows. Section 2
includes some notation and tools needed. Section 3 is devoted to the proof of
Theorem 1.2. The proof of Theorem 1.3 is given in Section 4.

##  2 Preliminaries

Given a convex polygon $T$ in $\mathbb{R}^{2}_{[0,n]}$, denote by $\Lambda(T)$
the number of lattice points contained within $T$, and by $\|T\|$ the area of
$T$ with respect to the Lebesgue measure. Throughout the proof, we always use
the following result of Skriganov [Skr93] which relates the area of a shape
with the number of lattice points contained inside it.

######  Lemma 2.1 (Theorem 5 in [Skr93]).

If $P$ is a convex polygon (a simple closed curve with finitely many points
which are not part of a line segment) with at least one side having a rational
normal, then

$\displaystyle\max_{a\in\mathbb{Z}^{2}}\Big{|}\big{(}\|tP+a\|-\Lambda(tP+a)\big{)}\Big{|}=o(t),$

where $tP$ denotes the dilation of $P$ by $t>0.$

This lemma implies that any convex polygon $P$, described above, satisfies
that $\Lambda(P)=(1+o(1))\|P\|$, which allows us to focus on the area $\|P\|$
instead of $\Lambda(P)$.

For two points $p_{1},p_{2}\in\mathbb{R}^{2}_{[0,n]}$, denote by
$m(p_{1},p_{2})$ the gradient and by $c(p_{2},p_{2})$ the $y$-intercept of the
line in $\mathbb{R}^{2}$ passing through $p_{1}$ and $p_{2}.$

######  Definition 2.2 (Upper boundary).

Given a set $A\subseteq\mathbb{R}^{2}_{[0,n]}$, the upper boundary of $A$ is a
set of points in $A$, denoted by $\partial A$, such that for each
$p_{1}\in\partial A$ there exists a point $p_{2}\in A\setminus\\{p_{1}\\}$
with the following properties:

  * •

$m(p_{1},p_{2})<0$;

  * •

Let $T=\\{(x,y)\subseteq\mathbb{R}^{2}_{[0,n]}\mid
y>m(p_{1},p_{2})x+c(p_{1},p_{2})\\}$. Then $|A\cap T|=0$.

Any two such points $p_{1},p_{2}$ are said to be adjoint, and the line passing
through two points that are adjoint is called an upper boundary line. The
second condition above states that there is no point of $A$ strictly above any
upper boundary line.

The following lemma shows that if the upper boundary of a set $A$ is empty,
then $A$ has a ‘top right corner’.

######  Lemma 2.3 (Lemma 5.1 in [ER17]).

Suppose $A\subseteq\mathbb{R}^{2}_{[0,n]}$ such that $\partial A=\varnothing$.
Then there is a point $(a,b)\in A$ such that $a\geq x$ and $b\geq y$ for all
$(x,y)\in A.$

We also need the concept of pairing sets, which will be frequently used
throughout the proof.

######  Definition 2.4.

Given a point $a\in\mathbb{R}^{2}_{[0,n]}$ and a set
$P\subseteq\mathbb{R}^{2}_{[0,n]}$, we call $P$ a _pairing set for_ $a$ if for
any $x\in P$, we have $a-x\in P$.

The following lemma, which immediately follows from the definition of pairing
set, guarantees that for any point in a sum-free set $S$, every pairing set
for that point cannot intersect too much with $S$.

######  Lemma 2.5 (Lemma 3.4 in [ER17]).

Let $S$ be a sum-free set in $[n]^{2}$. Then for any $a\in S$ and a pairing
set $P$ for $a$, we have $|P\cap S|\leq\frac{1}{2}\Lambda(P)$.

The following lemma bounds the intersection of a set and its translate with a
sum-free set.

######  Lemma 2.6.

Given two sets $S,T\subseteq[n]^{2}$, if $S$ is sum-free, then for any $a\in
S$, it holds that

$|S\cap(T\cup(a\pm T))|\leq\Lambda(T).$

###### Proof.

For each element $t\in T$ there is a corresponding element $a\pm t\in a\pm T$.
Since $a\in S$, one can observe from sum-freeness that at most one of $t$ and
$a\pm t$ belongs to $S$. ∎

##  3 Proof of Theorem 1.2

We carry out the proof in a few steps. First, using Lagrange multiplier, we
show that any almost maximum-size sum-free set $S$ in $[n]^{2}$ has an upper
boundary line that is close to the line $y+x=\frac{8n}{5}$, see Lemma 3.3.
Then we show that there is a point $(x^{*},y^{*})$ in $S$ close to
$(\frac{4n}{5},\frac{4n}{5})$, see Lemma 3.4. Finally, using this point
$(x^{*},y^{*})$, we show in Section 3.3 that $S$ has no point below the line
$y+x=\frac{4n}{5}-o(n)$, which, together with the upper boundary line close to
$y+x=\frac{8n}{5}$, implies that $S$ must be close to the extremal stripe
$\frac{4n}{5}\leq x+y\leq\frac{8n}{5}$.

######  Definition 3.1.

A sum-free set $S\subseteq[n]^{2}$ with $\partial S\neq\varnothing$ is of
_Type_ 1 if there exists a point $p_{1}=(x_{1},y_{1})\in\partial S$ with
$x_{1}\leq y_{1}$ and $x_{1}y_{1}\geq xy$ for all $(x,y)\in\partial S$, and a
point $p_{2}=(x_{2},y_{2})$ adjoint to $p_{1}$ satisfying the following
conditions, where we simply write $m=m(p_{1},p_{2})$ and $c=c(p_{1},p_{2})$.

  * $(1)$

$x_{2}>x_{1}$, $y_{2}<y_{1}$ and $m<-\frac{y_{1}}{x_{1}}\leq-1$;

  * $(2)$

$c>n$ and $-c\leq nm$.

In addition, $S$ is of _Type_ 2 if there exist two adjoint points
$p_{1}=(x_{1},y_{1})$ and $p_{2}=(x_{2},y_{2})$ in $\partial S$ satisfying the
following conditions.

  * $(1)$

$x_{2}>x_{1}$, $y_{2}<y_{1}$ and $-\frac{y_{1}}{x_{1}}\leq
m\leq-\frac{y_{2}}{x_{2}}$;

  * $(2)$

$y_{2}\leq\frac{c}{2}\leq y_{1}$;

  * $(3)$

$c>n$ and $-c<nm$.

For either type of the sum-free set, we call the upper boundary lines passing
through $p_{1}$ and $p_{2}$ _typical_. Let

$A=\\{(x,y)\in\mathbb{R}^{2}_{[0,n]}\mid y>mx+c\\}$

with $m$ and $c$ given as above. Then $A$ is a triangle in both cases.

For the Type 1 set $S$, we claim that the upper boundary line $y=mx+c$
satisfies $x_{1}>\frac{n}{2}$. In fact, since $m<-\frac{y_{1}}{x_{1}}$ and
$y_{1}=mx_{1}+c$, we have that $x_{1}>\frac{c}{-2m}>\frac{n}{2}$ because
$-c<nm$.

If $S$ is of Type 2, then it is straightforward to check that the following
two sets are nonempty.

$T_{1}=\left\\{(x,y)\in\mathbb{R}^{2}_{[0,n]}\mid x\geq
x_{1},y-mx\leq\frac{c}{2}\right\\},$
$T_{2}=\left\\{(x,y)\in\mathbb{R}^{2}_{[0,n]}\mid y\geq
y_{2},y-mx\leq\frac{c}{2}\right\\}.$

Figure 1: Type 2 $S$

The two types we defined above correspond to the only two cases in [ER17] that
attain the maximum density $\frac{3}{5}$. We will use the following bounds for
these two types of sum-free sets.

######  Lemma 3.2 ([ER17]).

Given a sum-free set $S\subseteq[n]^{2}$, if $|S|>0.56n^{2}$, then either

  * _(1)_

$S$ is of Type 1 and
$|S|\leq(n+1)^{2}-\frac{1}{2}x_{1}y_{1}+\frac{(c+nm-n)^{2}}{2m}$, or

  * _(2)_

$S$ is of Type 2 and
$|S|\leq(n+1)^{2}+\frac{c^{2}}{8m}+\frac{1}{2m}(n-nm-c)^{2}.$

###  3.1 Fixing an upper boundary line

Given constants $\varepsilon$ and $C$, we call that a line $L$ is
$\varepsilon$-_close_ to the line $x+y=C$ if the portion of $L$ intersecting
$\mathbb{R}^{2}_{[0,n]}$ lies entirely within the set
$\\{(x,y)\in\mathbb{R}^{2}_{[0,n]}\mid|x+y-C|<\varepsilon n\\}.$ Similarly, we
call two point $p_{1}=(x_{1},y_{1})$ and $p_{2}=(x_{2},y_{2})$ are
$\varepsilon$-_close_ to each other if $|x_{1}-x_{2}|\leq\varepsilon n$ and
$|y_{1}-y_{2}|\leq\varepsilon n$.

######  Lemma 3.3.

Given $\varepsilon>0$, there exist $\delta>0$ and $n_{0}\in\mathbb{N}$ such
that the following holds for all $n>n_{0}$. If $S\subseteq[n]^{2}$ is sum-free
and $|S|>(\frac{3}{5}-\delta)n^{2}$, then there is a typical upper boundary
line for $S$ which is $\varepsilon$-close to $x+y=\frac{8n}{5}$.

###### Proof.

Given $\varepsilon>0$, let $\delta=\frac{\varepsilon^{2}}{100}$ and $n$ be
sufficiently large with respect to $\varepsilon$. Let $S\subseteq[n]^{2}$ be a
sum-free set with $|S|>(\frac{3}{5}-\frac{\varepsilon^{2}}{100})n^{2}$.

Suppose for contradiction that any upper boundary line $y=mx+c$ for $S$ is not
$\varepsilon$-close to $x+y=\frac{8n}{5}$. That is, either the $y$\- or the
$x$-intercept is far from where it should be:

$\text{either}\quad|c-8n/5|>\varepsilon
n\quad\text{or}\quad|c/m+8n/5|>\varepsilon n.$

We shall derive in both cases a contradiction that
$|S|\leq(3/5-\varepsilon^{2}/100)n^{2}$.

Considering the typical upper boundary line $y=mx+c$ passing through $p_{1}$
and $p_{2}$ given in Definition 3.1, we will finish the case when the
$y$-intercept is too far, that is, $|c-8n/5|>\varepsilon n$, whose proof will
be divided into two cases depending on the type of $S$. The case when the
$x$-intercept is too far (that is, $|c/m+8n/5|>\varepsilon n$) is similar and
we omit the details.

Suppose first that $S$ is of Type 1, then by Lemma 3.2(1), we have

$\displaystyle|S|\leq(n+1)^{2}-\frac{1}{2}\left(x_{1}(mx_{1}+c)-\frac{(c+mn-n)^{2}}{m}\right)=:f(x,m,c).$

To simplify the presentation, we introduce a new variable $\eta$ with
$\eta\in(-\infty,-\varepsilon)\cup(\varepsilon,+\infty)$ and define

$f_{\eta}:=\max\\{f(x,m,c)\mid c-8n/5=\eta n\\}.$

Let $L:=f(x,m,c)-\lambda g$, where $g=c-8n/5-\eta n$. By solving
$\frac{\partial L}{\partial x}=0$, $\frac{\partial L}{\partial m}=0$,
$\frac{\partial L}{\partial c}=0$ and $\frac{\partial L}{\partial\lambda}=0$,
we obtain $m=-\sqrt{1+2\eta+\frac{5\eta^{2}}{4}}$ and
$x=\frac{\frac{4}{5}+\frac{\eta}{2}}{\sqrt{1+2\eta+\frac{5\eta^{2}}{4}}}n$,
and thus the maximum value is

$f_{\eta}=(8/5+\eta-\sqrt{1+2\eta+5\eta^{2}/4})n^{2}+O(n).$

As $\eta$ takes values over $(-\infty,-\varepsilon)\cup(\varepsilon,+\infty)$,
we get

$f_{\eta}\leq(8/5+\varepsilon-\sqrt{1+2\varepsilon+5\varepsilon^{2}/4})n^{2}+O(n)\leq(3/5-\varepsilon^{2}/100)n^{2}.$

For the second case when $S$ is of Type 2, by Lemma 3.2(2), we have:

$|S|\leq(n+1)^{2}+\frac{c^{2}}{8m}+\frac{(n-nm-c)^{2}}{2m}.$

Using Lagrange multiplier again, we arrive at the same bound
$(8/5+\varepsilon-\sqrt{1+2\varepsilon+5\varepsilon^{2}/4})n^{2}+O(n)\leq(3/5-\varepsilon^{2}/100)n^{2}$
as desired. ∎

###  3.2 Top right corner

######  Lemma 3.4.

For any $\beta>0$, there exist $\delta>0$ and $n_{0}\in\mathbb{N}$ such that
for all $n>n_{0}$, if $S\subseteq[n]^{2}$ is sum-free with
$|S|>(\frac{3}{5}-\delta)n^{2}$, then there is a point $(x^{*},y^{*})\in S$
which is $\beta$-close to the point $(\frac{4n}{5},\frac{4n}{5})$.

###### Proof.

We first handle Type 1 sum-free sets. Given $\beta>0$, we have constants
$\delta=\delta_{\ref{lem-upper-boundary-line}}>0$ and $n_{0}\in\mathbb{N}$
returned from Lemma 3.3 with $\varepsilon=\beta/6$. Let $S\subseteq[n]^{2}$ be
a sum-free set of Type 1 with $|S|>(\frac{3}{5}-\delta)n^{2}$. Then Lemma 3.3
gives a typical upper boundary line $y=mx+c$ that is $\varepsilon$-close to
$x+y=\frac{8n}{5}$ and let $p_{1}=(x_{1},y_{1})$, $p_{2}=(x_{2},y_{2})$ be the
two points involved. Therefore, $|c-\frac{8n}{5}|<\varepsilon n$,
$|x_{1}+y_{1}-\frac{8n}{5}|<\varepsilon n$. Consequently, by triangle
inequality we have

$|m+1|=\frac{|x_{1}+y_{1}-c|}{x_{1}}<\frac{2\varepsilon
n}{x_{1}}<4\varepsilon,$

where the last inequality follows since $x_{1}>n/2$. Recall that
$m\leq-\frac{y_{1}}{x_{1}}\leq-1$. Then we have that
$|m+\frac{y_{1}}{x_{1}}|<4\varepsilon$.

Using these facts we can write $m=-\frac{y_{1}}{x_{1}}-\gamma_{1}$ and
$c=(\frac{8}{5}+\gamma_{2})n$ for constants $0\leq\gamma_{1}<4\varepsilon$ and
$|\gamma_{2}|<\varepsilon$. Using the equation $y_{1}=mx_{1}+c$, we obtain
that $y_{1}=\frac{4}{5}n+\frac{\gamma_{2}n-\gamma_{1}x_{1}}{2}.$ As $x_{1}\leq
n$, by triangle inequality, we have

$\Big{|}y_{1}-\frac{4n}{5}\Big{|}<\frac{5\varepsilon n}{2}<\beta n.$

Moreover, since $-\frac{y_{1}}{x_{1}}\geq m>-1-4\varepsilon$ and $x_{1}\leq
y_{1}$, we can easily obtain that $|x_{1}-\frac{4n}{5}|<6\varepsilon n=\beta
n$. So $(x_{1},y_{1})$ is $\beta$-close to the point
$(\frac{4n}{5},\frac{4n}{5})$ as desired.

Let us turn to Type 2 sum-free set. Now, given $\beta>0$, choose positive
constants $\varepsilon,\delta$ with $\delta\ll\varepsilon\ll\beta$. Let $S$ be
a sum-free set of Type 2 with $|S|>(\frac{3}{5}-\delta)n^{2}$. Then applying
Lemma 3.3 with $\sqrt{2}\varepsilon$ playing the role of $\varepsilon$ gives a
typical upper boundary line $y=mx+c$ passing through $(x_{1},y_{1})$ and
$(x_{2},y_{2})$ which is $\sqrt{2}\varepsilon$-close to $y+x=\frac{8n}{5}$.
This implies that the line $y=mx+\frac{c}{2}$ is
$\frac{\varepsilon}{\sqrt{2}}$-close to $x+y=\frac{4n}{5}$. We may assume for
contradiction that $S$ has no points in the region

$T_{\beta}=\left\\{(x,y)\in\mathbb{R}^{2}_{[0,n]}\mid
x,y\geq\frac{4n}{5}-\beta n\>,\>\>y+x\leq\frac{8n}{5}\right\\}.$

Redefine the regions as follows:

$A=\left\\{(x,y)\in\mathbb{R}^{2}_{[0,n]}\mid
y+x\geq\frac{8n}{5}+\sqrt{2}\varepsilon n\right\\},$
$T_{1}=\left\\{(x,y)\in\mathbb{R}^{2}_{[0,n]}\mid
y+x\leq\frac{4n}{5}-\frac{\varepsilon n}{\sqrt{2}},\>x\geq x_{1}\right\\},$
$T_{2}=\left\\{(x,y)\in\mathbb{R}^{2}_{[0,n]}\mid
y+x\leq\frac{4n}{5}-\frac{\varepsilon n}{\sqrt{2}},\>y\geq y_{2}\right\\}.$

Note that

$T_{1}+T_{2}=\left\\{(x,y)\in\mathbb{R}^{2}_{[0,n]}\mid
y+x\leq\frac{8n}{5}-\sqrt{2}\varepsilon n,\>y_{2}\leq y,\>x_{1}\leq
x\right\\}.$

Figure 2: S is Type 2

We now proceed by considering the areas which may be excluded from $S$.
Firstly, we show that $S$ has two points in $T_{1}$ that are far apart.

######  Claim 3.5.

There are two points in $T_{1}\cap S$ which are at least $\beta n$ far apart.

###### Proof of claim.

If this is not true, then there are less than $\beta^{2}n^{2}$ points of $S$
in $T_{1}$, given by the number of points in a square around a circle of diam
$\beta n$ in $T_{1}$. Since
$\|T_{\beta}\|=\frac{1}{2}(2\beta)^{2}n^{2}=2\beta^{2}n^{2}$, we then use the
pairing set $P_{1}$ for $(x_{1},y_{1})$ and thus

$\displaystyle|S|$ $\displaystyle\leq
n^{2}-\Lambda(A)-\frac{1}{2}\Lambda(P_{1})-\Lambda(T_{1})+\beta^{2}n^{2}-\Lambda(T_{\beta})$
$\displaystyle=n^{2}-\|A\|-\frac{1}{2}\|P_{1}\|-\|T_{1}\|+\beta^{2}n^{2}-\|T_{\beta}\|+O(n)$
$\displaystyle=n^{2}-\frac{1}{2}\left(\frac{2}{5}-\sqrt{2}\varepsilon\right)^{2}n^{2}-\frac{1}{2}x_{1}y_{1}-\frac{1}{2}\left(\frac{4}{5}-\frac{\varepsilon}{\sqrt{2}}-\frac{x_{1}}{n}\right)^{2}n^{2}+\beta^{2}n^{2}-2\beta^{2}n^{2}+O(n)$

It is easy to see this is maximized when $y_{1}$ is minimal and
$x_{1}+y_{1}=\frac{8n}{5}-\sqrt{2}\varepsilon n$. Then

$\displaystyle|S|$
$\displaystyle\leq\left(\frac{3}{5}-\beta^{2}+10\varepsilon\right)n^{2}.$

Therefore, we reach a contradiction by the fact that
$\delta\ll\varepsilon\ll\beta$. ∎

By Claim 3.5, we let $t^{\prime}$ and $t^{\prime\prime}$ be two points in
$T_{1}$ with distance greater than $\beta n$, and let

$T_{2}^{\prime}:=t^{\prime}+T_{2}\quad\text{and}\quad
T_{2}^{\prime\prime}:=t^{\prime\prime}+T_{2}.$

######  Claim 3.6.

$\Lambda(T_{\beta}\setminus T_{2}^{\prime}),\Lambda(T_{\beta}\setminus
T_{2}^{\prime\prime})<\frac{\beta^{2}}{L}n^{2}$, where
$L:=\frac{4}{5\sqrt{3}-6}$.

###### Proof of claim.

Suppose to the contrary that either $\Lambda(T_{\beta}\setminus
T_{2}^{\prime})\geq\frac{\beta^{2}}{L}n^{2}$ or $\Lambda(T_{\beta}\setminus
T_{2}^{\prime\prime})\geq\frac{\beta^{2}}{L}n^{2}$, and by symmetry we may
assume the first inequality holds. Considering the pairing set $P_{2}$ for
$(x_{2},y_{2})$ and $T_{2}$ paired with $T_{2}^{\prime}$, we can obtain from
Lemmas 2.5 and 2.6 that

$\displaystyle|S|$ $\displaystyle\leq
n^{2}-\Lambda(A)-\frac{1}{2}\Lambda(P_{2})-\Lambda(T_{2})-\Lambda(T_{\beta}\setminus
T_{2}^{\prime})$
$\displaystyle\leq\left(\frac{3}{5}-\frac{\beta^{2}}{L}+O(\varepsilon)\right)n^{2},$

which once again gives a contradiction as $\delta\ll\beta$. ∎

In the rest of the proof, we shall find a partition $T_{2}=T_{2,1}\cup
T_{2,2}$ into two regions such that theirs corresponding translates
$T^{\prime}_{2,1}=t^{\prime}+T_{2,1}$ and
$T^{\prime\prime}_{2,2}=t^{\prime\prime}+T_{2,2}$ are distantly separated in
$T_{1}+T_{2}$, which provides a significant portion of points in
$T_{\beta}\setminus(T^{\prime}_{2,1}\cup T^{\prime\prime}_{2,2})$ that are to
be excluded from $S$.

Write $t^{\prime}=(x^{\prime},y^{\prime})$ and
$t^{\prime\prime}=(x^{\prime\prime},y^{\prime\prime})$. By Claim 3.6, we can
find that the two points $t^{\prime}+(0,y_{2})$ and
$t^{\prime\prime}+(0,y_{2})$ belong to the region $\\{(x,y)\in[n]^{2}\mid
x,y\leq\frac{4n}{5}\\}$. We may assume $x^{\prime}+y^{\prime}\geq
x^{\prime\prime}+y^{\prime\prime}$ and let
$d:=x^{\prime}+y^{\prime}-(x^{\prime\prime}+y^{\prime\prime})$. It is easy to
see that $d$ is the difference between the corresponding $y$-intercepts of the
red diagonal and the blue diagonal in Figure 3. By the symmetry of all the
shapes involved, we can further assume that $x^{\prime}\geq x^{\prime\prime}$
and $x^{\prime}-x^{\prime\prime}\geq y^{\prime\prime}-y^{\prime}$.

$y+x=\frac{8n}{5}$$T_{\beta}$$(0,y_{2})+t^{\prime\prime}$$(0,y_{2})+t^{\prime}$
Figure 3:  The red triangle represents $T_{2}^{\prime\prime}$, the blue one
represents $T_{2}^{\prime}$ and the black one represents $T_{\beta}$.

######  Claim 3.7.

$d\leq\left(2-2\sqrt{\frac{2L-1}{2L}}\right)\beta n=\frac{\sqrt{3}-1}{2}\beta
n$.

###### Proof of claim.

It is easy to see the region $T_{\beta}\cap T_{2}^{\prime\prime}$ is a
triangle similar to $T_{\beta}$. Note that the area of $T_{\beta}\setminus
T_{2}^{\prime\prime}$ is at least

$\frac{1}{2}(2\beta n)^{2}-\frac{1}{2}(2\beta n-d)^{2}=\Big{(}2\beta
n-\frac{d}{2}\Big{)}d.$

By Claim 3.6, we have that $\left(2\beta
n-\frac{d}{2}\right)d\leq\frac{\beta^{2}n^{2}}{L}$, which yields the bound on
$d$ as desired. ∎

Define points

$X_{1}=(x^{\prime},y^{\prime}+y_{2}),\quad
X_{2}=(x^{\prime\prime},y^{\prime\prime}+y_{2})\quad\text{and}\quad
X_{3}=(x^{\prime},y^{\prime\prime}+y_{2}).$

Let $P_{1}X_{1}$ and $P_{2}X_{2}$ be line segments which are parallel to
$PX_{3}$ (see Figure 4). Construct a line passing through $(0,y_{2})$ which is
also parallel to the line segments $PX_{3}$, where
$P=(\frac{4n}{5},\frac{4n}{5})$. Such a line separates $T_{2}$ into two parts,
and we denote by $T_{2,2}$ the part above the line and $T_{2,1}$ for the rest.

Figure 4: The triangle $UVW$ represents $T_{\beta}$, in which
$P=(\frac{4n}{5},\frac{4n}{5})$ is the median point for the line segment $UW$.

######  Claim 3.8.

There exists a triangle $T_{\beta,1}\subseteq T_{\beta}$ similar to
$T_{\beta}$ such that $T_{\beta,1}$ does not intersect with either of the
regions $T_{2,1}+t^{\prime}$ or $T_{2,2}+t^{\prime\prime}$ and
$\Lambda(T_{\beta,1})\geq\frac{\beta^{2}n^{2}}{8}$.

###### Proof of claim.

Recall that $s:=y^{\prime\prime}-y^{\prime}$ is positive. Since $t^{\prime}$
and $t^{\prime\prime}$ are of distance at least $\beta n$ far apart, that is,
$(x^{\prime}-x^{\prime\prime})^{2}+(y^{\prime}-y^{\prime\prime})^{2}=(s+d)^{2}+s^{2}\geq\beta^{2}n^{2}$,
together with Claim 3.7, we obtain that $s\geq\frac{\beta n}{2}$. Thus, the
segment $P_{1}P_{2}$ has length at least $\frac{\sqrt{2}}{2}\beta n$. Let
$T_{\beta,1}$ be the rectangle triangle $P_{1}P_{2}Q$ with diagonal line
$P_{1}P_{2}$. Then $T_{\beta,1}$ has area at least $\frac{\beta^{2}n^{2}}{8}$
and does not intersect either of the regions $T_{2,1}+t^{\prime}$ or
$T_{2,2}+t^{\prime\prime}$. ∎

As aforementioned, now we are ready to finish the proof. Applying Lemma 2.6 to
$T_{2,1},T_{2,2}$ and their translates $T_{2,1}+t^{\prime}$,
$T_{2,2}+t^{\prime\prime}$, we obtain that

$\displaystyle|S|$ $\displaystyle\leq
n^{2}-\Lambda(A)-\frac{1}{2}\Lambda(P_{2})-\Lambda(T_{2})-\Lambda(T_{\beta,1})$
$\displaystyle=n^{2}-\|A\|-\frac{1}{2}\|P_{2}\|-\|T_{2}\|-\|T_{\beta,1}\|+O(n)$
$\displaystyle\leq
n^{2}-\frac{1}{2}\left(\frac{2}{5}-\sqrt{2}\varepsilon\right)^{2}n^{2}-\frac{1}{2}x_{2}y_{2}-\frac{1}{2}\left(\frac{4}{5}-\frac{\varepsilon}{\sqrt{2}}-\frac{x_{2}}{n}\right)^{2}n^{2}-\frac{\beta^{2}n^{2}}{8}+O(n).$

The right-hand side above is maximized when $y_{2}$ is minimal and
$x_{2}+y_{2}=\frac{8n}{5}-\sqrt{2}\varepsilon n$. Thus,

$\displaystyle|S|$
$\displaystyle\leq\left(\frac{3}{5}-\frac{\beta^{2}}{8}+O(\varepsilon)\right)n^{2},$

a final contradiction. ∎

###  3.3 Putting things together

We are now ready to prove our main result, knowing that any almost maximum
sum-free set contains an upper boundary line $o(1)$-close to
$y+x=\frac{8n}{5}$ and a point $o(1)$-close to $(\frac{4n}{5},\frac{4n}{5})$.

###### Proof of Theorem 1.2.

Given $\gamma>0$, choose $\delta\ll\varepsilon\ll\beta\ll\gamma$. Let
$S\subseteq[n]^{2}$ be a sum-free set of size at least $(3/5-\delta)n^{2}$.
Then by Lemma 3.3, $S$ has a typical upper boundary line $y=mx+c$ which is
$\varepsilon$-close to $y+x=\frac{8n}{5}$. Now it suffices to show that $S$
has no point below the line $x+y=\frac{4n}{5}-\gamma n$ (see the red line in
Figure 5).

Note that Lemma 3.4 ensures the existence of a point $(x_{1},y_{1})$ of $S$
that is $\beta$-close to $(\frac{4n}{5},\frac{4n}{5})$. Suppose to the
contrary that $p_{0}=(x_{0},y_{0})\in S$ is such a point below the line
$x+y=\frac{4n}{5}-\gamma n$, and without loss of generality we may assume that
$y_{0}\geq x_{0}.$

Let

$A=:\left\\{(x,y)\in[n]^{2}\mid y+x>\frac{8n}{5}+\varepsilon n\right\\}.$

Considering the pairing set $P:=\\{(x,y)\in[n]^{2}\mid x\leq x_{1},y\leq
y_{1}\\}$ for $(x_{1},y_{1})$, there are at most

$\displaystyle
n^{2}-\Lambda(A)-\frac{1}{2}\Lambda(P)\leq\left(\frac{3}{5}+\left(\frac{2}{5}-\frac{\varepsilon}{2}\right)\varepsilon+\left(\frac{4}{5}-\frac{\beta}{2}\right)\beta\right)n^{2}+O(n)$
(1)

points which may be included in $S$; and all these points are below the line
below the line $x+y=\frac{8n}{5}+\varepsilon n$. Then, writing

$D_{1}:=\left\\{(x,y)\in[n]^{2}\mid y>\frac{4n}{5}+\beta
n,\;y+x<\frac{8n}{5}-\varepsilon n\right\\}$

and

$D_{2}:=\left\\{(x,y)\in[n]^{2}\mid x>\frac{4n}{5}+\beta
n,\;y+x<\frac{8n}{5}-\varepsilon n\right\\},$

it follows from the assumption $|S|\geq(3/5-\delta)n^{2}$ and (1) that

$\displaystyle\frac{1}{n^{2}}|(D_{1}\cup D_{2})\setminus
S|\leq\delta+\left(\frac{2}{5}-\frac{\varepsilon}{2}\right)\varepsilon+\left(\frac{4}{5}-\frac{\beta}{2}\right)\beta=:\upsilon(\delta,\varepsilon,\beta).$
(2)

Note that we can choose $\delta,\varepsilon,\beta$ small enough such that
$\upsilon(\delta,\varepsilon,\beta)=o(\gamma^{2})$. In the remaining proof, we
shall find in $D_{1}\cup D_{2}$ (or its translate) a relatively large subset
of lattice points which are to be excluded from $S$, yielding a contradiction.

Figure 5: The case when $x_{0}<\frac{n}{5}-\frac{\gamma}{2}n$: The two grey
regions $R$ and its translate $R-(x_{0},y_{0})$ form a pairing, which excludes
from the sum-free set $S$ the amount of points which fit in one of the regions
.

First assume that $p_{0}$ is such that $x_{0}<\frac{n}{5}-\frac{\gamma}{2}n.$
Then the region $(D_{1}\cup D_{2})+p_{0}$ intersects $D_{1}\cup D_{2}$ on a
set of lattice points, denoted by $R$. Since $R,R-p_{0}\subseteq D_{1}\cup
D_{2}$, applying Lemma 2.6 with $a=p_{0}$ and $T=R-p_{0}$ gives that
$|(R\cup(R-p_{0}))\cap S|\leq|R|$, and thus

$|(D_{1}\cup D_{2})\setminus S|\geq|(R\cup(R-p_{0}))\setminus
S|\geq|R\cup(R-p_{0})|-|R|.$

It is easy to observe that $|R\cup(R-p_{0})|-|R|$ is minimized when $p_{0}$ is
close to the point $(\frac{n}{5}-\frac{\gamma n}{2},\frac{3n}{5}-\frac{\gamma
n}{2}),$ yielding a area of size at least
$\left(\frac{3}{8}\gamma^{2}-\frac{\gamma-2\beta}{4}(2\varepsilon-\beta)\right)n^{2}+O(n)$
(See Figure 5). Thus $|(D_{1}\cup D_{2})\setminus
S|\geq\left(\frac{3}{8}\gamma^{2}-\frac{\gamma-2\beta}{4}(2\varepsilon-\beta)\right)n^{2}+O(n)>\upsilon(\delta,\varepsilon,\beta)n^{2}$,
a contradiction to (2).

Now it remains to consider the case when $p_{0}$ satisfies
$x_{0}\geq\frac{n}{5}-\frac{\gamma n}{2}.$ We consider the overlap of
$(D_{1}\cup D_{2})-p_{0}$ with $(x_{1},y_{1})-((D_{1}\cup D_{2})-p_{0})$ and
denote by $\mathcal{O}$ the set of lattice points in the overlap (see Figure
6). Let

$D:=((D_{1}\cup D_{2})-p_{0})\setminus(D_{1}\cup D_{2}).$

Then it is easy to verify that $\mathcal{O}\subseteq D$. Note that by Lemma
2.6 with $a=p_{0}$ and $T=D_{1}\cup D_{2}$, one have that

$|(D\cup D_{1}\cup D_{2})\cap S|\leq|D_{1}\cup D_{2}|.$

Then, using (2), we have

$\displaystyle|\mathcal{O}\cap S|\leq|D\cap S|$ $\displaystyle=|(D\cup
D_{1}\cup D_{2})\cap S|-|(D_{1}\cup D_{2})\cap S|$
$\displaystyle\leq|(D_{1}\cup D_{2})\setminus
S|\leq\upsilon(\delta,\varepsilon,\beta)n^{2}.$

Moreover, by definition we know that
$(x_{1},y_{1})-\mathcal{O}\subseteq\mathcal{O}$, that is, $\mathcal{O}$ (and
also $P\setminus\mathcal{O}$) is a pairing set for $(x_{1},y_{1})$. It follows
from Lemma 2.5 that

Figure 6: All possible shapes of $\mathcal{O}$

$\displaystyle|S|$ $\displaystyle\leq
n^{2}-\Lambda(A)-\frac{1}{2}\Lambda(P\setminus\mathcal{O})-(|\mathcal{O}|-|\mathcal{O}\cap
S|)$ $\displaystyle\leq
n^{2}-\|A\|-\frac{1}{2}\|P\|-\frac{1}{2}|\mathcal{O}|+\upsilon(\delta,\varepsilon,\beta)n^{2}$
$\displaystyle=n^{2}-\frac{1}{2}\Big{(}\frac{2n}{5}-\varepsilon
n\Big{)}^{2}-\frac{1}{2}\Big{(}\frac{4n}{5}-\beta
n\Big{)}^{2}-\frac{1}{2}|\mathcal{O}|+\upsilon(\delta,\varepsilon,\beta)n^{2}$
$\displaystyle=\frac{3}{5}n^{2}+o(\gamma^{2})n^{2}-\frac{1}{2}|\mathcal{O}|.$

Therefore, it suffices to show that $|\mathcal{O}|=\Omega(\gamma^{2})n^{2}$,
and in the remaining proof we shall verify this by considering all possible
shapes of $\mathcal{O}$.

Figure 7: each numbered region will produce a unique shape of the overlap.

Since $(x_{1},y_{1})$ is $\beta$-close to $(\frac{4n}{5},\frac{4n}{5})$ and
$\beta=o(\gamma^{2})$, we may further assume that
$(x_{1},y_{1})=(\frac{4n}{5},\frac{4n}{5})$ in order not to cluster the
presentation. We list in Figure 6 all possible shapes of the overlap
$\mathcal{O}$, which originate from the location of the point $(x_{0},y_{0})$
(see Figure 7). In particular, the area of the overlap in each of these cases
is given as follows:

  1. 1.

$4\left(\frac{3n}{5}-y_{0}\right)\left(\frac{4n}{5}-y_{0}-x_{0}-\varepsilon
n\right),$ where $\frac{n}{2}+\frac{\beta n}{2}\leq
y_{0}\leq\frac{3n}{5}-\frac{\gamma n}{2}$.

  2. 2.

$4\left(y_{0}-\frac{2n}{5}-\beta
n\right)\left(\frac{4n}{5}-y_{0}-x_{0}-\varepsilon n\right)$, where
$\frac{n}{2}-\frac{(\beta+\varepsilon)n}{2}\leq
y_{0}\leq\frac{n}{2}+\frac{\beta n}{2}$.

  3. 3.

$\left(n-2y_{0}-\beta n-\varepsilon
n\right)^{2}+4\left(y_{0}-\frac{2n}{5}-\beta
n\right)\left(\frac{4n}{5}-y_{0}-x_{0}-\varepsilon n\right)$, where
$\frac{2n}{5}+\beta n\leq
y_{0}\leq\frac{n}{2}-\frac{(\beta+\varepsilon)n}{2}$.

  4. 4.

$4\left(\frac{4n}{5}-y_{0}-x_{0}-\varepsilon
n\right)\left(x_{0}-\frac{n}{5}-2\beta n\right)$, where
$x_{0}\geq\frac{3n}{10}+\frac{(\beta-\varepsilon)n}{2}$.

  5. 5.

$\left(n-2y_{0}-\beta n-\varepsilon n\right)^{2}$

  6. 6.

$4\left(\frac{4n}{5}-y_{0}-x_{0}-\varepsilon
n\right)\left(\frac{n}{5}+x_{0}-y_{0}-\beta n\right)$, where
$x_{0}\geq\frac{3n}{10}+\frac{(\beta-\varepsilon)n}{2},y_{0}\in[\frac{2n}{5}-\frac{\varepsilon
n}{2},\frac{2n}{5}+\beta n]$.

  7. 7.

$2\left(\frac{n}{5}-\beta n\right)^{2}-\left(2y_{0}-\frac{3n}{5}+\varepsilon
n-\beta n\right)^{2}$

  8. 8.

$2\left(\frac{n}{5}-\beta n\right)^{2}-\left(2y_{0}-\frac{3n}{5}+\varepsilon
n-\beta n\right)^{2}-\left(2x_{0}-\frac{3n}{5}+\varepsilon n-\beta
n\right)^{2}$, where

$\frac{3n}{10}+\frac{(\beta-\varepsilon)n}{2}\leq x_{0}\leq
y_{0}\leq\frac{2n}{5}-\frac{\varepsilon n}{2}.$

  9. 9.

$2\left(\frac{n}{5}-\beta n\right)^{2}.$

It is obvious that for the regions $5,$ $7$ and $9,$ the area of the overlap
has size $\Omega(\gamma^{2})n^{2}$. The only regions which interest us are the
ones bordering the line $y+x=\frac{4n}{5}-\gamma n$. Moreover, the regions in
question are $1,$ $2,$ $3,$ $4,$ $6$ and $8.$ Among them, the minimum overlap
is achieved in region $1$ by letting $(x_{0},y_{0})=(\frac{n}{5}-\frac{\gamma
n}{2},\frac{3n}{5}-\frac{\gamma n}{2})$, which yields a value of
$|\mathcal{O}|\geq 2\gamma(\gamma-\varepsilon)n^{2}$ as desired. This
completes the proof of Theorem 1.2. ∎

##  4 Proof of Theorem 1.3

In this section we investigate the maximum size of a $(p,p)$-sum free set $S$.
To simplify the presentation, we write $p$-sum free for $(p,p)$-sum free. Our
proof builds on the techniques developed in the work of Elsholtz and Rackham
[ER17]. We need a variant notion of pairing set as follows.

######  Definition 4.1.

For any $(a_{1},a_{2})\in\mathbb{R}^{2}_{[0,n]}$,
$P\subseteq\mathbb{R}^{2}_{[0,n]}$ is a $p$-pairing set for $(a_{1},a_{2})$
if, for any $(x_{1},x_{2})\in P$, we have
$(\frac{a_{1}}{p}-x_{1},\frac{a_{2}}{p}-x_{2})\in P$.

Analogous to Lemmas 2.5 and 2.6, the following lemma guarantees that for any
point $a\in S$ and its $p$-pairing set $P$, at least half of the points in $P$
are excluded from $S$. Similar statement also holds when we consider a set and
its translate dilated by $p$. We omit the proof.

######  Lemma 4.2.

Let $S\subseteq[n]^{2}$ be a $p$-sum free set.

  * _(1)_

If $P$ is a $p$-pairing set for some $a\in S$, then we have $|S\cap
P|\leq\frac{1}{2}\Lambda(P)$.

  * _(2)_

If $T\subseteq\mathbb{R}^{2}_{[0,n]}$ and $a\in S$, then $|S\cap(p(a+T)\cup
T)|\leq\Lambda(T)$.

######  Proof of Theorem 1.3.

Let $S\subseteq[n]^{2}$ be a $p$-sum free set. Our goal is to show that
$|S|\leq\left(1-\frac{2}{4p^{2}+1}\right)n^{2}+O(n)$ for $p\geq 2$. We may
neglect any boundary effects as they give error terms $O(n)$ for the size of
$S$, which will be omitted so as to ease the presentation. We consider cases
depending on the placement of upper boundary lines.

Case 1: $|\partial(S)|\leq 1$. As vertices in the upper boundary come in
(adjoint) pairs, we see that in this case $\partial(S)=\varnothing$, and thus
Lemma 2.3 ensures the existence a point $p_{1}=(x_{1},y_{1})\in S$ such that
$x_{1}\geq x$ and $y_{1}\geq y$ for all $(x,y)\in S.$ Let $P:=\\{(x,y)\mid
0\leq x\leq\frac{x_{1}}{p},0\leq y\leq\frac{y_{1}}{p}\\}$. Then $P$ is a
$p$-pairing set for $p_{1}$ and thus by Lemma 4.2, we have that

$\displaystyle|S|$
$\displaystyle\leq(n+1)^{2}-(n-x_{1})n-(n-y_{1})x_{1}-\frac{1}{2}\Lambda(P)$
$\displaystyle=\left(1-\frac{1}{2p^{2}}\right)x_{1}y_{1}+O(n)\leq\left(1-\frac{1}{2p^{2}}\right)n^{2}+O(n)<\left(1-\frac{2}{4p^{2}+1}\right)n^{2}.$

Case 2: $|\partial(S)|\geq 2$ and for every two points
$p_{1}=(x_{1},y_{1}),p_{2}=(x_{2},y_{2})$ that are adjoint in $\partial(S)$
with $x_{1}<x_{2}$ and $y_{1}>y_{2}$, we have either
$m(p_{1},p_{2})>-\frac{y_{2}}{x_{2}}$ or
$m(p_{1},p_{2})<-\frac{y_{1}}{x_{1}}$.

In this case, we choose $p_{1}=(x_{1},y_{1})\in\partial(S)$ such that
$x_{1}y_{1}\geq xy$ holds for every $(x,y)\in\partial(S)$ and
$P_{1}:=\\{(x,y)\mid 0\leq x\leq\frac{x_{1}}{p},0\leq
y\leq\frac{y_{1}}{p}\\}$. By symmetry, we may further assume that $y_{1}\geq
x_{1}$. If there does not exist $p_{2}=(x_{2},y_{2})\in\partial(S)$ adjoint to
$p_{1}$ with $x_{2}>x_{1}$ and $y_{2}<y_{1}$, then by Lemma 4.2 and that
$y_{1}\geq x_{1}$, we have

$\displaystyle|S|\leq n^{2}-(n-x_{1})n-\frac{1}{2}\Lambda(P_{1})\leq
nx_{1}-\frac{x_{1}^{2}}{2p^{2}}\leq\left(1-\frac{1}{2p^{2}}\right)n^{2}.$

Thus, we may assume that there exists $p_{2}=(x_{2},y_{2})\in\partial(S)$
adjoint to $p_{1}$ with $x_{2}>x_{1}$ and $y_{2}<y_{1}$. Let $L:y=mx+c$ be the
line passing through $p_{1},p_{2}$ and define

$A=\\{(x,y)\in\mathbb{R}^{2}_{[0,n]}\mid y>mx+c\\}.$

We claim that $m<-\frac{y_{1}}{x_{1}}\leq-1$. Indeed, by the assumption of
Case 2, assume for contradiction that $m>-\frac{y_{2}}{x_{2}}$, then

$x_{2}y_{2}=x_{2}(y_{1}+m(x_{2}-x_{1}))\geq
x_{2}y_{1}-y_{2}(x_{2}-x_{1})=x_{1}y_{1}+(y_{1}-y_{2})(x_{2}-x_{1})>x_{1}y_{1},$

contrary to the choice of $p_{1}$.

We split into two subcases depending on the $x$\- and $y$-intercept of $L$.
Note first that, if $c\leq n$, then we have $-\frac{c}{m}\leq n$ because
$m\leq-1$, and so $|S|<\frac{1}{2}n^{2}$ as $A\cap S=\varnothing$.

(I). If $c>n$ and $-\frac{c}{m}\leq n$, then

$|S|\leq
n^{2}-\Lambda(A)-\frac{1}{2}\Lambda(P_{1})=\frac{n}{m}\left(\frac{n}{2}-c\right)-\frac{1}{2p^{2}}x_{1}y_{1}=\frac{n}{m}\left(\frac{n}{2}-y_{1}\right)+x_{1}n-\frac{1}{2p^{2}}x_{1}y_{1}.$

Now if $y_{1}\leq\frac{n}{2}$, then as $m<-1$ and $x_{1}\leq
y_{1}\leq\frac{n}{2}$, we observe that $|S|\leq x_{1}n\leq\frac{1}{2}n^{2}$.
We may then assume $y_{1}>\frac{n}{2}$.

If $x_{1}<\frac{n}{2}$, then by the assumption that $m<-\frac{y_{1}}{x_{1}}$,
we have

$|S|\leq\frac{nx_{1}}{y_{1}}\left(y_{1}-\frac{n}{2}\right)+x_{1}n-\frac{1}{2p^{2}}x_{1}y_{1}\leq\left(2n-\frac{n^{2}}{2y_{1}}-\frac{y_{1}}{2p^{2}}\right)\frac{n}{2}\leq\left(1-\frac{1}{2p}\right)n^{2}.$

where the last inequality follows from
$\frac{n^{2}}{2y_{1}}+\frac{y_{1}}{2p^{2}}\geq
2\sqrt{\frac{n^{2}}{2y_{1}}\frac{y_{1}}{2p^{2}}}=\frac{n}{p}$.

Assume then $x_{1}\geq\frac{n}{2}$. Note that as $-\frac{c}{m}\leq n$, the
slope of $L$ is smaller than the slope of the line passing through $p_{1}$ and
$(n,0)$, and so $m\leq\frac{-y_{1}}{n-x_{1}}$. Thus, we have

$\displaystyle|S|$
$\displaystyle\leq\frac{n(n-x_{1})}{y_{1}}\left(y_{1}-\frac{n}{2}\right)+x_{1}n-\frac{1}{2p^{2}}x_{1}y_{1}\leq
n^{2}-\left(\frac{n-x_{1}}{2n}n^{2}+\frac{x_{1}y_{1}}{2p^{2}}\right)$
$\displaystyle=\frac{n^{2}}{2}+\left(\frac{n}{2}-\frac{y_{1}}{2p^{2}}\right)x_{1}\leq\frac{n^{2}}{2}+\left(\frac{n}{2}-\frac{y_{1}}{2p^{2}}\right)y_{1}\leq\left(1-\frac{1}{2p^{2}}\right)n^{2},$

where the second last inequality follows since $x_{1}\leq y_{1}$ and the last
one follows from $p\geq 2$.

(II). If $c>n$ and $-\frac{c}{m}>n$, then $A$ is a triangle and thus

$\displaystyle|S|$ $\displaystyle\leq
n^{2}-\Lambda(A)-\frac{1}{2}\Lambda(P_{1})$
$\displaystyle=n^{2}+\frac{(n-y_{1})^{2}}{2m}+\frac{m(n-x_{1})^{2}}{2}-(n-x_{1})(n-y_{1})-\frac{x_{1}y_{1}}{2p^{2}}.$

The right-hand side above is increasing when $m\leq-\frac{n-y_{1}}{n-x_{1}}$.
Since $\frac{n-y_{1}}{n-x_{1}}\leq\frac{y_{1}}{x_{1}}\leq-m$, it follows that

$\displaystyle|S|$ $\displaystyle\leq
n^{2}-\frac{(n-y_{1})^{2}}{\frac{2y_{1}}{x_{1}}}-\frac{y_{1}(n-x_{1})^{2}}{2x_{1}}-(n-x_{1})(n-y_{1})-\frac{x_{1}y_{1}}{2p^{2}}$
$\displaystyle\leq
2(x_{1}+y_{1})n-n^{2}-\left(2+\frac{1}{2p^{2}}\right)x_{1}y_{1},$

where the right-hand side of the last inequality is maximized when
$x_{1}=y_{1}=\frac{4p^{2}}{4p^{2}+1}n$, and thus
$|S|\leq\left(1-\frac{2}{4p^{2}+1}\right)n^{2}$.

Case 3: There exist $p_{1}=(x_{1},y_{1}),p_{2}=(x_{2},y_{2})$ adjoint in
$\partial(S)$ such that $x_{1}<x_{2}$, $y_{1}>y_{2}$ and
$-\frac{y_{1}}{x_{1}}\leq m(p_{1},p_{2})\leq-\frac{y_{2}}{x_{2}}$.

Let $P_{i}$ be a $p$-pairing set for each $p_{i}$ with $i\in[2]$, that is,
$P_{i}:=\\{(x,y)\mid 0\leq x\leq\frac{x_{i}}{p},0\leq
y\leq\frac{y_{i}}{p}\\}$. Set $A=\\{(x,y)\in\mathbb{R}^{2}_{[0,n]}\mid
y>mx+c\\}$. Since $m\leq-\frac{y_{2}}{x_{2}}$ and $y_{2}=mx_{2}+c$, we have
that $y_{2}\leq\frac{c}{2}$. Similarly, by the condition
$m\geq-\frac{y_{1}}{x_{1}}$, we have that $y_{1}\geq\frac{c}{2}$.

Define

$T_{1}=\\{(x,y)\in\mathbb{R}^{2}_{[0,n]}\mid x\geq\frac{x_{1}}{p},y\leq
mx+\frac{c}{2p}\\},$

and

$T_{2}=\\{(x,y)\in\mathbb{R}^{2}_{[0,n]}\mid y\geq\frac{y_{2}}{p},y\leq
mx+\frac{c}{2p}\\}.$

We claim that $T_{1},T_{2}\neq\varnothing$. These amount to proving
$-\frac{c}{2mp}\geq\frac{x_{1}}{p}$ and $\frac{c}{2p}\geq\frac{y_{2}}{p}$,
which in turn follows from the fact that $y_{2}\leq\frac{c}{2}\leq y_{1}$, see
Figure 8.

Figure 8: Nonempty $T_{1},T_{2}$.

If $T_{1}\cap S=\varnothing$, then a short calculation shows

$\displaystyle|S|\leq
n^{2}-\Lambda(T_{1})-\Lambda(A)-\frac{1}{2}\Lambda(P_{1})\leq
n^{2}+\frac{c^{2}}{8p^{2}m}-\|A\|.$

If $T_{1}\cap S\neq\varnothing$, then take a point $a\in T_{1}\cap S$, then
one can check that $p(a+T_{2})\cap T_{2}=\varnothing$. By Lemma 4.2, we have
$|S\cap(p(a+T_{2})\cup T_{2})|\leq\Lambda(T_{2})$. By the definition of
$T_{2}$, any point $(x,y)\in p(a+T_{2})$ satisfies that $y\leq mx+c$ and
$x\geq x_{1},y\geq y_{2}$. We again arrive to

$\displaystyle|S|\leq
n^{2}-\Lambda(T_{2})-\Lambda(A)-\frac{1}{2}\Lambda(P_{2})\leq
n^{2}+\frac{c^{2}}{8p^{2}m}-\|A\|.$

Suppose now that $c\leq n$. If $-\frac{c}{m}\leq n$, then
$|S|\leq\frac{1}{2}n^{2}$ by excluding $A$ alone. So $-\frac{c}{m}>n$. Then
$\|A\|=\frac{n(2n-mn-2c)}{2}$ and we get, using $c\leq n$ and $x+y\geq
2\sqrt{xy}$ for $x,y>0$,

$\displaystyle|S|$ $\displaystyle\leq
n^{2}+\frac{c^{2}}{8p^{2}m}-\|A\|=\frac{c^{2}}{8p^{2}m}+\frac{n^{2}m}{2}+cn\leq
cn-\frac{cn}{2p}\leq\left(1-\frac{1}{2p}\right)n^{2}.$

We may then assume $c>n$. The case $-\frac{c}{m}\leq n$ can be handled as the
above $c\leq n$ and $-\frac{c}{m}\geq n$ case. Thus, we can assume
$-\frac{c}{m}>n$. Then $A$ is a triangle with $\|A\|=-\frac{(n-mn-c)^{2}}{2m}$
and

$\displaystyle|S|\leq
n^{2}+\frac{c^{2}}{8p^{2}m}+\frac{(n-mn-c)^{2}}{2m}=\left(\frac{1}{8p^{2}}+\frac{1}{2}\right)\frac{c^{2}}{m}+\frac{n(m-1)}{m}c+\frac{n^{2}m}{2}+\frac{n^{2}}{2m}.$

The quadratic function of $c$ above is maximized when
$c=-\frac{(m-1)n}{1+\frac{1}{4p^{2}}}$. Thus

$\displaystyle|S|$ $\displaystyle\leq
n^{2}\left[\frac{4p^{2}}{4p^{2}+1}+\left(\frac{1}{2}-\frac{2p^{2}}{4p^{2}+1}\right)\left(m+\frac{1}{m}\right)\right]\leq\left(1-\frac{2}{4p^{2}+1}\right)n^{2},$

where the maximum is achieved when we choose $m=-1$ and thus
$c=\frac{8p^{2}}{4p^{2}+1}n$.

This completes the proof. ∎

## References

  * [Blo16] T. F. Bloom, _A quantitative improvement for Roth’s theorem on arithmetic progressions_ , J. Lond. Math. Soc. (2) 93 (2016), no. 3, 643–663. MR 3509957
  * [BLST18] József Balogh, Hong Liu, Maryam Sharifzadeh, and Andrew Treglown, _Sharp bound on the number of maximal sum-free subsets of integers_ , J. Eur. Math. Soc. (JEMS) 20 (2018), no. 8, 1885–1911. MR 3854894
  * [Cam02] Peter J. Cameron, _Sum-free sets of a square_ , manuscript (2002).
  * [Cam05] , _Research problems from the 19th British Combinatorial Conference_ , Discrete Math. 293 (2005), no. 1-3, 313–320. MR 2136071
  * [CKP20] Ilkyoo Choi, Ringi Kim, and Boram Park, _Maximum $k$-sum n-free sets of the 2-dimensional integer lattice_, Electron. J. Combin. 27 (2020), no. 4, Paper No. 4.2, 12. MR 4245177
  * [DFST99] Jean-Marc Deshouillers, Gregory A. Freiman, Vera Sós, and Mikhail Temkin, _On the structure of sum-free sets. II_ , no. 258, 1999, Structure theory of set addition, pp. xii, 149–161. MR 1701193
  * [ER17] Christian Elsholtz and Laurence Rackham, _Maximal sum-free sets of integer lattice grids_ , J. Lond. Math. Soc. (2) 95 (2017), no. 2, 353–372. MR 3656272
  * [Fre92] Gregory A. Freiman, _On the structure and the number of sum-free sets_ , no. 209, 1992, Journées Arithmétiques, 1991 (Geneva), pp. 13, 195–201. MR 1211012
  * [HT17] Robert Hancock and Andrew Treglown, _On solution-free sets of integers_ , European J. Combin. 66 (2017), 110–128. MR 3692141
  * [Rot53] K. F. Roth, _On certain sets of integers_ , J. London Math. Soc. 28 (1953), 104–109. MR 51853
  * [Ruz93] Imre Z. Ruzsa, _Solving a linear equation in a set of integers. I_ , Acta Arith. 65 (1993), no. 3, 259–282. MR 1254961
  * [Ruz95] , _Solving a linear equation in a set of integers. II_ , Acta Arith. 72 (1995), no. 4, 385–397. MR 1348205
  * [Sch16] I. Schur, _Uber die kongruenz $x^{m}+y^{m}\equiv z^{m}$ (mod p)_, Jahresber. Deutsch. Math.-Verein. 25 (1916), 114–117.
  * [Skr93] Maxim Skriganov, _On integer points in polygons_ , Ann. Inst. Fourier (Grenoble) 43 (1993), no. 2, 313–323. MR 1220271
  * [Tra18] Tuan Tran, _On the structure of large sum-free sets of integers_ , Israel J. Math. 228 (2018), no. 1, 249–292. MR 3874843


11institutetext: Princeton University, Princeton, NJ, USA 22institutetext:
University of California San Diego, La Jolla, CA, USA 33institutetext:
University of Illinois at Urbana-Champaign, Champaign, IL, USA

# Charged particle tracking via edge-classifying interaction networks

Gage DeZoort 11<EMAIL_ADDRESS>Savannah Thais 11<EMAIL_ADDRESS>Isobel Ojalvo 11 Peter Elmer 11 Vesal Razavimaleki 22 Javier Duarte 22 Markus
Atkinson 33 Mark Neubauer 33

###### Abstract

Recent work has demonstrated that geometric deep learning methods such as
graph neural networks (GNNs) are well-suited to address a variety of
reconstruction problems in HEP. In particular, tracker events are naturally
represented as graphs by identifying hits as nodes and track segments as
edges; given a set of hypothesized edges, edge-classifying GNNs predict which
correspond to real track segments. In this work, we adapt the physics-
motivated interaction network (IN) GNN to the problem of charged-particle
tracking in the high-pileup conditions expected at the HL-LHC. We demonstrate
the IN’s excellent edge-classification accuracy and tracking efficiency
through a suite of measurements at each stage of GNN-based tracking: graph
construction, edge classification, and track building. The proposed IN
architecture is substantially smaller than previously studied GNN tracking
architectures, a reduction in size critical for enabling GNN-based tracking in
constrained computing environments. Furthermore, the IN is easily expressed as
a set of matrix operations, making it a promising candidate for acceleration
via heterogeneous computing resources.

##  1 Introduction

Charged particle tracking is essential to many downstream reconstruction tasks
including vertex finding Piacquadio:2008zzb ; Chatrchyan:2014fea , particle
reconstruction Aaboud:2017aca ; Sirunyan:2017ulk , and jet flavor tagging
Larkoski:2017jix ; Sirunyan:2017ezt ; Aaboud:2018xwy . Current tracking
algorithms at the CERN Large Hadron Collider (LHC) experiments cms_tracking ;
atlas_tracking  are typically based on the combinatorial Kalman filter
combkalman1 ; combkalman2 ; combkalman3 ; kalman  and have been shown to scale
worse than linearly with increasing beam intensity and detector occupancy
hllhc_tracking . The high-luminosity phase of the LHC (HL-LHC) will see an
order of magnitude increase in luminosity ApollinariG.:2017ojx , highlighting
the need to develop new tracking algorithms demonstrating reduced latency and
improved performance in high-pileup environments. To this end, ongoing
research focuses on both accelerating current tracking algorithms via
dedicated hardware or parallelization and developing new tracking algorithms
with machine learning (ML) techniques.

Geometric deep learning (GDL) gdl ; zhang2020deep ; zhou2019graph ;
wu2019comprehensive  is a growing sub-field of ML focused on learning
representations on non-Euclidean domains such as sets, graphs, and manifolds.
Graph neural networks (GNNs) gnnmodel ; pointnet ; gilmer2017neural ; IN ;
relational ; DGCNN  are the subset of GDL algorithms that run on graphs, data
represented as a set of nodes connected by edges. Tracker data is naturally
represented as a graph; hits form a 3D point cloud and the edges between them
represent hypotheses about particle trajectories. Recent progress by the
Exa.TrkX project and other collaborations has demonstrated that edge-
classifying GNNs are well-suited to particle tracking applications heptrkx ;
exatrkx ; IN_fpga . Tracking via edge classification typically involves three
stages. In the graph construction stage, tracker hits are mapped to nodes and
an edge-assignment algorithm forms edges between certain nodes. In the edge
classification stage, an edge-classifying GNN infers the probability that each
edge corresponds to a true track segment. Finally, in the track building step,
a track-building algorithm leverages the edge weights to form full track
candidates.

In this work, we present a suite of measurements at each of these stages,
exploring a range of strategies and algorithms to facilitate GNN tracking. We
focus in particular on the interaction network (IN) IN , a GNN architecture
frequently used as a building block in more complicated architectures heptrkx
; IN_fpga . The IN itself demonstrates powerful edge-classification
capability, and its simple matrix formulation makes it a promising candidate
for acceleration via heterogeneous computing resources fpga . In Section 2, we
first present an overview of particle tracking and graph-based representations
of track hits. In Section 3, we introduce INs and describe the mathematical
foundations of our architecture. In Section 4, we present specific graph
construction, IN edge classification, and track building measurements on the
TrackML dataset. Additionally, we present IN inference time measurements,
framing this work in the context of ongoing GNN acceleration studies. In
Section 5, we summarize the results of our studies and contextualize them in
the broader space of ML-based particle tracking. We conclude in the same
section with outlook and discussion of future studies, in particular
highlighting efforts to accelerate INs via heterogeneous computing resources.

##  2 Theory and Background

###  2.1 Particle Tracking

In collider experiments such as the LHC, charged particle trackers are
comprised of cylindrical detector layers immersed in an axially-aligned
magnetic field. The detector geometry is naturally specified by cylindrical
coordinates $(r,\phi,z)$, where the $z$ axis is aligned with the beamline.
Pseudorapidity is a measure of angle with respect to the beamline, defined as
$\eta=-\log\tan\frac{\theta}{2}$ where $\theta$ is the polar angle. Charged
particles produced in collision events move in helical trajectories through
the magnetic field, generating localized hits in the tracker layers via
ionization energy deposits. Track reconstruction consists of “connecting the
dots,” wherein hits are systematically grouped to represent charged particle
trajectories. We refer to a pair of hits that belong to the same particle as a
track segment, such that the line extending between the hits is a linear
approximation of the particle’s trajectory. Reconstructed tracks are defined
by their respective hit patterns and kinematic properties, which are extracted
from each track’s helix parameters. Specifically, initial position and
direction follow directly from helical fits and the transverse momentum
$p_{\mathrm{T}}$ is extracted from the track’s curvature tracking .

In this work, we focus specifically on track finding in the pixel detector,
the innermost subdetector of the tracker. Many tracking algorithms run “inside
out,” where track seeds from the pixel detector are used to estimate initial
track parameters and propagated through the full detector cms_tracking .
Improving the seeding stage of the tracking pipeline is an important step
towards enabling efficient tracking at the HL-LHC; this approach is
complimentary to other GNN-based tracking efforts that focus on the full
tracker barrel (without including endcaps) using graph segmentation exatrkx .

###  2.2 Tracker Hits as Graphs

Tracking data is naturally represented as a graph by identifying hits as nodes
and track segments as (in general) directed edges. In this scheme, nodes have
cylindrical spatial features $x_{i}=(r_{i},\phi_{i},z_{i})$ and edges are
represented by two adjacency matrices:
$R_{i},R_{o}\in\mathbb{R}^{n_{\mathrm{edges}}\times n_{\mathrm{nodes}}}$. The
elements $(R_{i})_{e,h}$ are $1$ if edge $e$ is incoming to hit $h$ and $0$
otherwise. $R_{o}$ is defined similarly for outgoing edges. Each edge is
assigned a set of geometric features $e_{ij}=(\Delta
r_{ij},\Delta\phi_{ij},\Delta z_{ij},\Delta R_{ij})$, where $\Delta
R_{ij}=\sqrt{\Delta\eta_{ij}^{2}+\Delta\phi_{ij}^{2}}$. These relations are
stacked into matrices $X=[x_{i}]\in\mathbb{R}^{n_{\mathrm{nodes}}\times 3}$
and $R_{a}=[e_{ij}]\in\mathbb{R}^{n_{\mathrm{edges}}\times 4}$. Accordingly,
we define a hitgraph representing tracking data as
$\mathcal{G}\coloneqq(X,R_{a},R_{i},R_{o})$. The corresponding training target
is the vector $y\in\mathbb{R}^{n_{\mathrm{edges}}}$, whose components $y_{e}$
are $1$ when edge $e$ is a true track segment and $0$ otherwise.

Figure 1: (Left) A transverse view of a generic particle tracker. The magnetic
field is aligned with the $z$-axis such that tracks move with a radius of
curvature $R$ in the transverse plane, yielding measurements of transverse
momentum via $p_{\mathrm{T}}=0.3\
[\frac{\,\text{GeV}}{\text{T}\cdot\text{m}}]\ BR$. (Middle) The tracker barrel
layers are unrolled in the $r$–$z$ plane to show the full three-particle plus
noise event. (Right) The corresponding hitgraph is shown with example node and
edge labels.

##  3 Interaction Networks

The IN is a physics-motivated GNN capable of reasoning about objects and their
relations IN . Each IN forward-pass involves a relational reasoning step, in
which an interaction is computed, and an object reasoning step, in which
interaction effects are aggregated and object dynamics are applied. The
resulting predictions have been shown to generate next-timestep dynamics
consistent with various physical principles. We adapt the IN to the problem of
edge classification by conceptualizing each hitgraph as a complex network of
hit “objects” and hypothesized edge “relations.” In this context, the
relational and object reasoning steps correspond to edge and node re-
embeddings respectively. In an edge classification scheme, the IN must
determine whether or not each hitgraph edge represents a track segment.
Accordingly, we extend the IN forward pass to include an additional relational
reasoning step, which produces an edge weight for each hypothesized edge in
the hitgraph.

###  3.1 Mathematical Formulation

The IN forward pass begins with an input hitgraph
$\mathcal{G}=(X,R_{a},R_{i},R_{o})$. The hits receiving an incoming edge are
given by $X_{i}\coloneqq R_{i}X\in\mathbb{R}^{n_{\mathrm{edges}}\times 3}$;
likewise, the hits sending an outgoing edge are given by $X_{o}\coloneqq
R_{o}X\in\mathbb{R}^{n_{\mathrm{edges}}\times 3}$. Interaction terms are
defined by the concatenation
$m(\mathcal{G})\coloneqq[X_{i},X_{o},R_{a}]\in\mathbb{R}^{n_{\mathrm{edges}}\times
10}$, known as the marshalling step. A relational network $\phi_{R}^{(1)}$
predicts an “effect” for each interaction term,
$E\coloneqq\phi_{R}^{(1)}\big{(}m(\mathcal{G})\big{)}\in\mathbb{R}^{n_{\mathrm{edges}}\times
4}$. These effects are aggregated via summation for each receiving node,
$A\coloneqq a(\mathcal{G},E)=R_{i}^{T}E\in\mathbb{R}^{n_{\mathrm{nodes}}\times
4}$, and concatenated with $X$ to form a set of expanded hit features
$C\coloneqq[X,A]\in\mathbb{R}^{n_{\mathrm{nodes}}\times 7}$. An object network
$\phi_{O}$ re-embeds the hit positions as
$\tilde{X}\coloneqq\phi_{O}(C)\in\mathbb{R}^{n_{\mathrm{nodes}}\times 3}$. At
this point, the traditional IN inference is complete, having re-embedded both
the edges and nodes. Accordingly, we denote the re-embedded graph
$\mathrm{IN}(\mathcal{G})=\tilde{\mathcal{G}}=(\tilde{X},E,R_{i},R_{o})$.

In order to produce edge weights to be used in the track-building algorithm an
additional relational reasoning step is performed on $\tilde{\mathcal{G}}$.
The marshalling step yields new interaction terms
$m(\tilde{\mathcal{G}})=[\tilde{X}_{i},\tilde{X}_{o},E]\in\mathbb{R}^{n_{\mathrm{edges}}\times
10}$ and a second relational network $\phi_{R}^{(2)}$ predicts edge weights
for each edge:
$W\coloneqq\phi_{R}^{(2)}(m(\tilde{\mathcal{G}}))\in(0,1)^{n_{\mathrm{edges}}}$.
Summarily, we have a full forward pass of the edge classification IN:

$\displaystyle W(\mathcal{G})$
$\displaystyle=\phi_{R}^{(2)}\bigg{[}m\big{(}\mathrm{IN}(\mathcal{G})\big{)}\bigg{]}=\phi_{R}^{(2)}\bigg{[}m\bigg{(}\mathcal{G},\phi_{O}\big{[}\mathcal{G},a\big{(}\mathcal{G},\phi_{R}^{(1)}\big{[}m(\mathcal{G})\big{]}\big{)}\big{]}\bigg{)}\bigg{]}$
(1)

##  4 Measurements

###  4.1 TrackML Dataset

The TrackML dataset is a simulated set of proton-proton collision events
originally developed for the TrackML Particle Tracking Challenge TrackML .
TrackML events are generated with 200 pileup interactions on average,
simulating the high-pileup conditions expected at the HL-LHC. Each event
contains 3D hit position and truth information about the particles that
generated them. In particular, particles are specified by particle IDs
($p_{\mathrm{ID}}$) and three-momentum vectors ($\mathbf{p}$).

The TrackML detector is designed as a generalized LHC tracker; it contains
discrete layers of sensor arrays immersed in a strong magnetic field. We focus
specifically on the pixel layers, a highly-granular set of four barrel and
fourteen endcap layers in the innermost tracker regions. The pixel layers are
shown in Figure 2. We note that constraining our studies to the pixel layers
reduces the size of the hitgraphs such that the full graph can be held in
memory and processed by the GNN without segmentation.

Figure 2: The pixel detector is a set of highly-granular layers sitting in the
innermost region of the TrackML detector.

###  4.2 Graph Construction

In the graph construction stage, each event’s tracker hits are converted to a
hitgraph of the form $\mathcal{G}=(X,R_{a},R_{i},R_{o})$. Typically, a set of
filters are applied to hits before they are assigned to graph nodes. For
example, $p_{\mathrm{T}}$ filters reject hits generated by particles with
$p_{\mathrm{T}}<p_{\mathrm{T}}^{\mathrm{min}}$, noise filters reject noise
hits, and same-layer filters reject all but one hit per layer for each
particle. After initial hit filtering yields a set of nodes, edge-assignment
algorithms extend edges between certain nodes. These edges are inputs to the
inference stage and must therefore represent as many true track segments as
possible. Towards this goal, one might naively return a fully-connected
hitgraph. However, this strategy yields
$\frac{1}{2}n_{\mathrm{nodes}}(n_{\mathrm{nodes}}-1)$ edges, which for
$n_{\mathrm{nodes}}\sim\mathcal{O}(1,000)$ gives
$n_{\mathrm{edges}}\sim\mathcal{O}(500,000)$. This represents a fundamental
trade-off between different edge-assignment algorithms: they must
simultaneously maximize truth efficiency, the fraction of track segments
represented as true edges, and edge efficiency, the fraction of true edges to
total edges in the hitgraph.

In this work, we compare multiple graph construction algorithms, each of which
determines whether or not to extend an edge $e_{ij}$ between hits $x_{i}$ and
$x_{j}$. In all methods, only pixel detector hits are considered,
pseudorapidity is restricted to $\eta\in[-5,5]$, and the noise and same-layer
hit filters are applied. The same-layer filter introduces an ambiguity in
defining edges between the barrel and innermost endcap layers. Specifically,
barrel hits generated by the same particle could produce multiple true edges
incoming to a single endcap hit. The resulting triangular edge pattern
conflicts with the main assumption of the same-layer filter, that only one
true track segment exists between each subsequent layer. For this reason, a
barrel intersection cut was developed, in which edges between a barrel layer
and an innermost endcap layer are rejected if they intersect with any
intermediate barrel layers.

In the following studies, the $p_{\mathrm{T}}$ filter is varied to modulate
the graph size (see Fig. 3) and cuts on the geometric quantities
$z_{0}=z_{i}-r_{i}\frac{z_{j}-z_{i}}{r_{j}-r_{i}}$ and
$\phi_{\mathrm{slope}}=\frac{\phi_{j}-\phi_{i}}{r_{j}-r_{i}}$ are used to
reject edges. We compare three graph construction methods:

  1. 1.

HEP.TrkX (barrel only): Edges must satisfy $z_{0}$ and $\phi_{\mathrm{slope}}$
constraints.

  2. 2.

HEP.TrkX+ (barrel+endcaps): Edges must satisfy $z_{0}$ and
$\phi_{\mathrm{slope}}$ constraints and the barrel intersection cut.

  3. 3.

DBSCAN (barrel+encdaps): In addition to all HEP.TrkX+ cuts, edges must also
belong to the same cluster in $\eta$-$\phi$ space determined by the density-
based spatial clustering of applications with noise (DBSCAN) algorithm dbscan
.

Table 1: Configuration parameters for the graph construction methods at each $p_{\mathrm{T}}^{\mathrm{min}}$. Note that while the HEP.TrkX+ and DBSCAN share the same $\phi_{\mathrm{slope}}$ and $z_{0}$ parameters, DBSCAN requires two additional clustering parameters: $\epsilon$, which defines the neighborhood radius, and MinPts, the number of points required to seed a cluster. $p_{\mathrm{T}}^{\mathrm{min}}$ [GeV] | HEP.TrkX | HEP.TrkX+, DBSCAN | DBSCAN
---|---|---|---
$\phi_{\mathrm{slope}}$ [$10^{-4}$] |  $z_{0}$ [m] |  $\phi_{\mathrm{slope}}$ [$10^{-4}$] |  $z_{0}$ [m] | $\epsilon$ | MinPts
2 | 6 | 0.1 | 6 | 15 | 0.22 | 3
1.5 | 6 | 0.1 | 6 | 15 | 0.18 | 3
1 | 6 | 0.1 | 6 | 15 | 0.1 | 3
0.75 | 7.63 | 0.1 | 7.63 | 25 | 0.08 | 3
0.6 | 7.63 | 0.1 | 7.63 | 29.5 | 0.06 | 3
0.5 | 7.63 | 0.1 | 7.63 | 29.5 | 0.05 | 3

A summary of the parameters used for each graph construction method is given
in Tab. 1; key metrics corresponding to these graph construction algorithms
are shown in Fig. 4. The results indicate that incorporating the endcaps leads
to drops in both truth and edge efficiency with corresponding increases in
$n_{\mathrm{edges}}$ and $n_{\mathrm{nodes}}$. This suggests that simple
geometric cuts are increasingly unable to filter false edges as broader
detector information is introduced, further highlighting the need for GNN
edge-classification. Note that the DBSCAN truth efficiency is upper bounded by
the HEP.TrkX+ method’s, but in general the DBSCAN edge efficiency is
substantially higher. This reflects the fact that same-track hits are likely
to be clustered in $\eta$–$\phi$ space, such that even clusters capturing many
different particles form a solid basis from which to construct edges. For the
remainder of the studies in this paper we focus on the HEP.TrkX+ graph
construction method.

Figure 3: As $p_{\mathrm{T}}^{\mathrm{min}}$ is decreased, graphs are
increasingly composed of false edges; pre-clustering hits in $\eta$–$\phi$
space reduces the fraction of false edges, thereby increasing edge efficiency.
Figure 4: Measurements of truth efficiency (top left), edge efficiency (top
right), number of nodes per graph (bottom left) and number of edges per graph
(bottom right) as a function of $p_{\mathrm{T}}^{\mathrm{min}}$. Some data
points are slightly offset along the $x$-axis for visual effect only.

###  4.3 Edge Classification

Towards transparency and applicability to future acceleration studies, we have
implemented the IN in PyTorch pytorch  as the set of explicit matrix
multiplications, concatenations, and transposes detailed in Sec. 3. The full
forward-pass, comprised of edge and node re-embeddings used to predict edge
weights, is shown in Fig. 5 below. The functions $\phi_{R}^{(1)}$,
$\phi_{R}^{(2)}$, and $\phi_{O}$ are approximated as multilayer perceptrons
(MLPs) with rectified linear unit (ReLU) activation functions relu1 ; relu2 .
The ReLU activation function behaves as an identity function for positive
inputs and saturates at 0 for negative inputs. Notably, the $\phi_{R}^{(2)}$
outputs have a sigmoid activation $\sigma(\cdot)\in(0,1)$, such that they
represent probabilities, or edge weights,
$W(\mathcal{G})\in(0,1)^{n_{\mathrm{edges}}}$ that each edge is a track
segment. We therefore seek to optimize a binary cross-entropy (BCE) loss
between the truth targets $y_{i}=\\{0,1\\}$ and edge weights $w_{i}\in(0,1)$:

$\displaystyle\ell\left(y_{n},W_{n}(\mathcal{G})\right)=-\sum_{i=1}^{n_{\mathrm{edges}}}\left(y_{i}\log
w_{i}+(1-y_{i})\log(1-w_{i})\right)$ (2)

Here, $n$ is the sample index, so that the total loss per epoch is the average
BCE loss
$L(\\{\mathcal{G}_{n},y_{n}\\}_{n=1}^{N})=\frac{1}{N}\sum_{n=1}^{N}\ell\big{(}y_{n},W_{n}(\mathcal{G})\big{)}$.
Throughout the following studies, the architecture in Fig. 5 is held at a
constant size of 6,448 trainable parameters, corresponding to 40 hidden units
per layer in each of the MLPs. Validation studies indicated that even this
small network rapidly converged to losses at or below $\mathcal{O}(10^{-2})$,
similar to its larger counterparts (see Fig. 5). Specifically, we train graphs
produced via the HEP.TrkX+ method with $p_{\mathrm{T}}^{\mathrm{min}}$ ranging
from 0.6–2 GeV. At each value of $p_{\mathrm{T}}^{\mathrm{min}}$, 1500 graphs
belonging to the TrackML train_1 sample were randomly divided into 1000
training, 400 testing, and 100 validation samples. To facilitate training, we
use the Adam optimizer adam  with a learning rate of 0.005, which is decayed
by a factor of $\gamma=0.9$ every 5 epochs.

Figure 5: (Left) The complete IN forward-pass with the relational and object
models approximated as MLPs. (Right) An example hyperparameter scan, in which
a models with varying numbers of hidden units (h.u.) were trained on
$p_{\mathrm{T}}^{\mathrm{min}}=1\,\text{GeV}$ graphs.

In order to evaluate the IN edge-classification performance, it is necessary
to define a threshold $\delta$ such that each edge weight $w_{i}\in
W(\mathcal{G})$ satisfying $w_{i}\geq\delta$ or $w_{i}<\delta$ indicates that
edge $i$ was classified as true or false respectively. Here, we define
$\delta^{*}$ as the threshold at which the true positive rate (TPR) equals the
true negative rate (TNR). In principle, $\delta^{*}$ may be calculated
individually for each graph. However, this introduces additional overhead to
the inference step, which is undesirable in constrained computing
environments. We instead determine $\delta^{*}$ during the training process by
minimizing the difference $|\mathrm{TPR}-\mathrm{TNR}|$ for graphs in the
validation set. The resulting $\delta^{*}$, which is stored for use in
evaluating the testing sample, represents the average optimal threshold for
the validation graphs. Accordingly, we define the model’s accuracy at
$\delta^{*}$ as $(n_{\mathrm{TP}}+n_{\mathrm{TN}})/n_{\mathrm{edges}}$, where
$n_{\mathrm{TP}}$ ($n_{\mathrm{TN}}$) is the number of true positives
(negatives), and note that the BCE loss is independent of $\delta^{*}$.

Figure 6: (Left) Loss convergence for models trained on various
$p_{\mathrm{T}}^{\mathrm{min}}$ graphs. (Right) A model trained on
$p_{\mathrm{T}}^{\mathrm{min}}=1$ GeV graphs was used to evaluate an unseen
$p_{\mathrm{T}}^{\mathrm{min}}=1$ GeV graph, yielding a loss of $6.0\times
10^{-3}$ and accuracy of 99.81%. 57 out of 29,661 edges were incorrectly
classified; these erroneous classifications are magnified in the figure.

Figure 7: Models trained on various $p_{\mathrm{T}}^{\mathrm{min}}$ graphs in
the train_1 sample were tested on 500 graphs from the train_2 sample at
various $p_{\mathrm{T}}^{\mathrm{min}}$ thresholds.

As shown in Figs. 6 and 7, the training process results in smooth convergence
to excellent edge-classification accuracy. In particular, Fig. 7 shows that
models trained on different $p_{\mathrm{T}}^{\mathrm{min}}$ demonstrate
relatively robust performance on test sets with various
$p_{\mathrm{T}}^{\mathrm{min}}$, a critical performance criteria for tracking
applications.

###  4.4 Track Building

In the track building step, the predicted edge weights $w_{i}\in
W(\mathcal{G})$ are used to infer that edges satisfying $w_{i}\geq\delta^{*}$
represent true track segments. If the edge weight mask perfectly reproduced
the training target (i.e. $\mathtt{int}(W(\mathcal{G})\geq\delta^{*})=y$), the
edge-classification step would produce $n_{particles}$ disjoint subgraphs,
each corresponding to a single particle. Imperfect edge-classification leads
to spurious connections between these subgraphs, prompting the need for more
sophisticated track-building algorithms. Here, we use the union-find algorithm
unionfind  and DBSCAN to cluster hits in the edge-weighted graphs.

We define three tracking efficiency measurements using progressively tighter
requirements to allow comparison with current tracking algorithm efficiencies
and other on-going HL-LHC tracking studies.

  1. 1.

Cluster efficiency: the number of found clusters where all hits within the
cluster originate from the same particle, divided by the total number of found
clusters.

  2. 2.

Physics efficiency: the number of found clusters where at least 50% of hits
originate from the same particle and at least 50% of the corresponding
particle’s hits are represented in the cluster, divided by the number of
particles in the event.

  3. 3.

Tight efficiency: the number of found clusters where all hits within the
cluster originate from the same particle and the number of hits in the cluster
matches the total number of hits generated by the particle, divided by the
number of particles in the event.

Fig. 8 shows each of these tracking efficiencies as a function of
$p_{\mathrm{T}}^{\mathrm{min}}$ for both the DBSCAN and union-find clustering
approaches. In line with the performance of current tracking algorithms
cms_tracking , the tracking efficiency increases with increasing
$p_{\mathrm{T}}^{\mathrm{min}}$, and levels off around 1.5 GeV to a maximum of
approximately 99% cluster efficiency, 97% physics efficiency, and 95% tight
efficiency. DBSCAN demonstrates higher tracking efficiency than union-find
across all $p_{\mathrm{T}}$ values and efficiency definitions; the performance
gap is larger for lower $p_{\mathrm{T}}$ values.

Figure 8: Track finding efficiencies with DBSCAN and union-find clustering for
three efficiency definitions. Note that some data points are offset along the
x-axis for visual effect only.

###  4.5 Inference Timing

An important advantage of GNN-based approaches over traditional methods for
HEP reconstruction is the ability to natively run on highly parallel computing
architectures. The PyTorch library pytorch  natively supports graphics
processing units (GPUs) to parallelize the algorithm execution. For the IN
studied in this work, the average CPU and GPU inference times per graph for a
variety of minimum $p_{\mathrm{T}}$ cuts is shown in Table 2. As can be seen,
inference can be significantly sped up with heterogeneous resources like GPUs.
For instance, for a 1 GeV minimum $p_{\mathrm{T}}$ cut, the inference time for
the HEP.TrkX+ graphs can be reduced by nearly a factor of 20 using the GPU
with respect to the CPU. Other heterogeneous computing resources specialized
for inference may be even more beneficial. This speed up may benefit the
experiments’ computing workflows by accessing these resources as an on-demand,
scalable service Krupa:2020bwg ; Rankin:2020usv ; Wang:2020fjr .

Table 2: CPU and GPU inference time estimates for each $p_{\mathrm{T}}$ threshold. The timing test were performed with an Nvidia Titan Xp GPU with 12 GB RAM and a 12-core Intel Xeon CPU E5-2650 v4 @ 2.20 GHz. Inference is performed with a batch size of one graph. The inference is repeated 100 times (after some warm-up) and the best time per inference is found. The mean and standard deviation of the best inference time derived for 5 random graphs in the testing dataset is then reported. For $p_{\mathrm{T}}^{\mathrm{min}}$ of 0.5 and 0.6 GeV, the inference could not be performed with the 12 GB RAM available on the GPU, as indicated with “—” in the table. $p_{\mathrm{T}}^{\mathrm{min}}$ [GeV] | HEP.TrkX | HEP.TrkX+
---|---|---
CPU [ms] | GPU [ms] | CPU [ms] | GPU [ms]
2 | $1.5\pm 0.2$ | $0.8\pm 0.02$ | $2.9\pm 0.6$ | $0.9\pm 0.03$
1.5 | $2.8\pm 0.1$ | $0.8\pm 0.01$ | $13.1\pm 5.5$ | $1.0\pm 0.2$
1 | $11.1\pm 3.5$ | $1.0\pm 0.1$ | $130.7\pm 60.7$ | $8.0\pm 4.0$
0.75 | $44.6\pm 18.0$ | $2.9\pm 1.3$ | $686.2\pm 281.2$ | $44.3\pm 18.8$
0.6 | $131.0\pm 42.9$ | $8.4\pm 2.7$ | $1954.0\pm 724.7$ | —
0.5 | $250.2\pm 77.8$ | $16.0\pm 5.2$ | $1952.0\pm 717.0$ | —

Work has also been done to accelerate the inference of deep neural networks
with heterogeneous resources beyond GPUs, like field-programmable gate arrays
(FPGAs) FINN ; FINNR ; fpgadeep ; fpgaover ; Duarte:2018ite ; Summers:2020xiy
; bnnpaper ; Coelho:2020zfu ; Aarrestad:2021zos . This work extends to GNN
architectures Iiyama:2020wap ; IN_fpga . Specifically, in Ref. IN_fpga , a
compact version of the IN was implemented for $p_{\mathrm{T}}>2\,\text{GeV}$
segmented HEP.TrkX+ graphs with up to 28 nodes and 37 edges, and shown to have
a latency less than 1 $\mu$s, reproduce the floating-point precision model
with a fixed-point precision of 16 bits or less, and fit on a Xilinx Kintex
UltraScale FPGA.

While this preliminary FPGA acceleration work is promising, there are several
limitations of the current FPGA implementation of the IN:

  1. 1.

The design does not easily scale to beyond $\mathcal{O}(100)$ nodes and
$\mathcal{O}(1,000)$ edges.

  2. 2.

The neural network itself is small, and while it is effective for
$p_{\mathrm{T}}>2\,\text{GeV}$ graphs, it may not be sufficient for
lower-$p_{\mathrm{T}}$ graphs.

  3. 3.

The FPGA design makes no assumptions about the possible graph connectivity
(e.g. layer 1 nodes are only connected to layer 2 nodes), and instead allows
all nodes to potentially participate in message passing. However by taking
this additional structure into account, the hardware resources can be
significantly reduced.

  4. 4.

Quantization-aware training bertmoons ; NIPS2015_5647 ; zhang2018lq ;
ternary-16 ; zhou2016dorefa ; JMLR:v18:16-456 ; xnornet ;
micikevicius2017mixed ; Zhuang_2018_CVPR ; wang2018training ; bnnpaper  using
QKeras Coelho:2020zfu ; qkeras  or Brevitas FINNR ; brevitas , parameter
pruning optimalbraindamage ; han2016deep ; lotteryticket ; supermask ;
stateofpruning ; Hawks:2021ruw , and general hardware-algorithm codesign can
significantly reduce the necessary FPGA resources by reducing the required bit
precision and removing irrelevant operations.

  5. 5.

The design can be made more flexible, configurable, and reusable by
integrating it fully with a user-friendly interface like hls4ml hls4ml .

##  5 Summary and Outlook

In this work, we have shown that the physics-motivated IN is well-suited to
the task of charged particle tracking in the high-pileup conditions expected
at the HL-LHC. Through a suite of graph construction, edge classification, and
track building measurements, we have framed the IN’s performance in the
context of a complete GNN-based tracking pipeline. The graph construction
measurements demonstrated that both the HEP.TrkX+ and DBSCAN graph
construction methods achieve high truth efficiency in constructing graphs from
pixel barrel and endcap layers; although the overall edge efficiency decreases
with $p_{\mathrm{T}}$ for both methods, the graphs were found to be suitable
for IN inference. The lightweight IN models trained in the edge classification
step demonstrated extremely high edge classification efficiency for a range of
$p_{\mathrm{T}}$ values. The track building measurements compared DBSCAN and
union-find clustering on edge-weighted graphs to measure track building
efficiency, demonstrating that DBSCAN outperforms union-find across the full
$p_{\mathrm{T}}$ range for every efficiency metric.

The IN architecture presented here is substantially smaller than previous GNN
tracking architectures, which may enable its use in constrained computing
environments. Accordingly, we have compared the IN’s CPU and GPU inference
times and discussed related work on accelerating INs with FPGAs. As described
in Section 4.5, there are several limitations to the current FPGA
implementation of the IN and addressing these concerns is the subject of
ongoing work.

Another important aspect of GNN-based tracking is reducing the time it takes
to construct graphs. Ongoing efforts are dedicated to studying how best to
accelerate graph construction using heterogeneous resources. Alternative GNN
approaches that do not require an input graph structure, such as dynamic graph
convolutional neural networks DGCNN , distance-weighted GNNs Qasim:2019otl ,
attention-based transformers vaswani2017attention , reformers
kitaev2020reformer , and performers choromanski2021rethinking , may be
fruitful avenues of investigation as well.

In summary, geometric deep learning methods are well-suited to many physics
reconstruction tasks, and our work and related studies establish GNNs as an
extremely promising candidate for tracking at the HL-LHC.

## Acknowledgement

S. T. and V. R. are supported by IRIS-HEP through the U.S. National Science
Foundation (NSF) under Cooperative Agreement OAC-1836650. J. D. is supported
by the U.S. Department of Energy (DOE), Office of Science, Office of High
Energy Physics Early Career Research program under Award No. DE-SC0021187. G.
D. is supported by DOE Award No. DEâSC0007968. We gratefully acknowledge the
input and discussion from the Exa.TrkX collaboration.

## References

  * (1) G. Piacquadio, K. Prokofiev, A. Wildauer, J. Phys. Conf. Ser. 119, 032033 (2008)
  * (2) S. Chatrchyan et al. (CMS), JINST 9, P10009 (2014), 1405.6569
  * (3) M. Aaboud et al. (ATLAS), Eur. Phys. J. C 77, 466 (2017), 1703.10485
  * (4) A. Sirunyan et al. (CMS), JINST 12, P10003 (2017), 1706.04965
  * (5) A.J. Larkoski, I. Moult, B. Nachman, Phys. Rept. 841, 1 (2020), 1709.04464
  * (6) A.M. Sirunyan et al. (CMS), JINST 13, P05011 (2018), 1712.07158
  * (7) M. Aaboud et al. (ATLAS), JHEP 08, 089 (2018), 1805.01845
  * (8) S. Chatrchyan et al. (CMS), JINST 9, P10009 (2014), 1405.6569
  * (9) M. Aaboud, G. Aad, B. Abbott, J. Abdallah, O. Abdinov, B. Abeloos, S.H. Abidi, O.S. AbouZeid, N.L. Abraham, et al., The European Physical Journal C 77 (2017)
  * (10) P. Billoir, Comput. Phys. Comm. 57, 390 (1989)
  * (11) P. Billoir, S. Qian, Nucl. Instrum. Meth. A 294, 219 (1990)
  * (12) R. Mankel, Nucl. Instrum. Meth. A 395, 169 (1997)
  * (13) R. Frühwirth, Nucl. Instrum. Meth. A 262, 444 (1987)
  * (14) CMS Note CMS-NOTE-2018-006. CERN-CMS-NOTE-2018-006 (2018), https://cds.cern.ch/record/2650976
  * (15) 4/2017 (2017)
  * (16) M.M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, P. Vandergheynst, IEEE Signal Process. Mag. 34, 18 (2017), 1611.08097
  * (17) Z. Zhang, P. Cui, W. Zhu (2020), 1812.04202
  * (18) J. Zhou, G. Cui, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, M. Sun (2019), 1812.08434
  * (19) Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, P.S. Yu, IEEE Trans. Neural Netw. Learn. Syst. p. 1 (2020), 1901.00596
  * (20) F. Scarselli, M. Gori, A.C. Tsoi, M. Hagenbuchner, G. Monfardini, IEEE Trans. Neural Netw. 20, 61 (2009)
  * (21) C.R. Qi, H. Su, K. Mo, L.J. Guibas, _PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation_ , in _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ (2017), 1612.00593
  * (22) J. Gilmer, S.S. Schoenholz, P.F. Riley, O. Vinyals, G.E. Dahl, _Neural message passing for quantum chemistry_ , in _Proceedings of the 34th International Conference on Machine Learning_ (2017), Vol. 70 of _Proceedings of Machine Learning Research_ , p. 1263, 1704.01212, http://proceedings.mlr.press/v70/gilmer17a.html
  * (23) P.W. Battaglia, R. Pascanu, M. Lai, D.J. Rezende, K. Kavukcuoglu, _Interaction Networks for Learning about Objects, Relations and Physics_ , in _Advances in Neural Information Processing Systems 29_ , edited by D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, R. Garnett (Curran Associates, Inc., 2016), Vol. 29, p. 4502, 1612.00222, https://papers.nips.cc/paper/2016/hash/3147da8ab4a0437c15ef51a5cc7f2dc4-Abstract.html
  * (24) P.W. Battaglia et al. (2018), 1806.01261
  * (25) Y. Wang, Y. Sun, Z. Liu, S.E. Sarma, M.M. Bronstein, J.M. Solomon, ACM Trans. Graph. 38 (2019), 1801.07829
  * (26) S. Farrell et al., _Novel deep learning methods for track reconstruction_ , in _4th International Workshop Connecting The Dots 2018_ (2018), 1810.06111
  * (27) X. Ju et al., _Graph Neural Networks for Particle Reconstruction in High Energy Physics Detectors_ , in _Machine Learning and the Physical Sciences Workshop at the 33rd Annual Conference on Neural Information Processing Systems_ (2019), 2003.11603, https://ml4physicalsciences.github.io/files/NeurIPS_ML4PS_2019_83.pdf
  * (28) A. Heintz, V. Razavimaleki, J. Duarte, G. DeZoort, I. Ojalvo, S. Thais, M. Atkinson, M. Neubauer, L. Gray, S. Jindariani et al., _Accelerated charged particle tracking with graph neural networks on FPGAs_ , in _3rd Machine Learning and the Physical Sciences Workshop at the 34th Annual Conference on Neural Information Processing Systems_ (2020), 2012.01563, https://ml4physicalsciences.github.io/2020/files/NeurIPS_ML4PS_2020_137.pdf
  * (29) M. Besta, D. Stanojevic, J. de Fine Licht, T. Ben-Nun, T. Hoefler (2019), 1903.06697
  * (30) A. Strandlie, R. Frühwirth, Rev. Mod. Phys. 82, 1419 (2010)
  * (31) S. Amrouche et al., _The Tracking Machine Learning Challenge: Accuracy Phase_ , in _The NeurIPS ’18 Competition_ (2020), p. 231, ISBN 978-3-030-29135-8, 1904.06778
  * (32) M. Ester, H.P. Kriegel, J. Sander, X. Xu, _A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise_ , in _Proceedings of the Second International Conference on Knowledge Discovery and Data Mining_ (AAAI Press, 1996), p. 226, https://www.aaai.org/Papers/KDD/1996/KDD96-037.pdf
  * (33) A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga et al., _PyTorch: An Imperative Style, High-Performance Deep Learning Library_ , in _Advances in Neural Information Processing Systems_ , edited by H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, R. Garnett (Curran Associates, Inc., 2019), Vol. 32, 1912.01703, https://proceedings.neurips.cc/paper/2019/file/bdbca288fee7f92f2bfa9f7012727740-Paper.pdf
  * (34) V. Nair, G.E. Hinton, _Rectified Linear Units Improve Restricted Boltzmann Machines_ , in _27th International Conference on International Conference on Machine Learning_ (Omnipress, Madison, WI, USA, 2010), ICML’10, p. 807, ISBN 9781605589077
  * (35) X. Glorot, A. Bordes, Y. Bengio, _Deep Sparse Rectifier Neural Networks_ , in _14th International Conference on Artificial Intelligence and Statistics_ , edited by G. Gordon, D. Dunson, M. DudÃk (JMLR, Fort Lauderdale, FL, USA, 2011), Vol. 15, p. 315, http://proceedings.mlr.press/v15/glorot11a.html
  * (36) D.P. Kingma, J. Ba, _Adam: A Method for Stochastic Optimization_ , in _3rd International Conference on Learning Representations_ , edited by Y. Bengio, Y. LeCun (2015), 1412.6980
  * (37) M.M.A. Patwary, J. Blair, F. Manne, _Experiments on Union-Find Algorithms for the Disjoint-Set Data Structure_ , in _Experimental Algorithms_ , edited by P. Festa (Springer Berlin Heidelberg, Berlin, Heidelberg, 2010), pp. 411–423, ISBN 978-3-642-13193-6
  * (38) J. Krupa, K. Lin, M.A. Flechas, J. Dinsmore, J. Duarte, P. Harris, S. Hauck, B. Holzman, S.C. Hsu, T. Klijnsma et al. (2020), submitted to _Mach. Learn.: Sci. Technol._ , 2007.10359
  * (39) D.S. Rankin, J. Krupa, P. Harris, M.A. Flechas, B. Holzman, T. Klijnsma, K. Pedro, N. Tran, S. Hauck, S.C. Hsu et al., _FPGAs-as-a-Service Toolkit (FaaST)_ , in _2020 IEEE/ACM International Workshop on Heterogeneous High-performance Reconfigurable Computing (H2RC)_ (2020), 2010.08556
  * (40) M. Wang, T. Yang, M. Acosta Flechas, P. Harris, B. Hawks, B. Holzman, K. Knoepfel, J. Krupa, K. Pedro, N. Tran, Front. Big Data 3, 48 (2021), 2009.04509
  * (41) Y. Umuroglu, N.J. Fraser, G. Gambardella, M. Blott, P. Leong, M. Jahre, K. Vissers, _FINN: A Framework for Fast, Scalable Binarized Neural Network Inference_ , in _Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays_ (ACM, New York, NY, USA, 2017), p. 65, ISBN 9781450343541, 1612.07119
  * (42) M. Blott, T. Preußser, N. Fraser, G. Gambardella, K. O’Brien, Y. Umuroglu, ACM Trans. Reconfigurable Technol. Syst. 11 (2018), 1809.04570
  * (43) A. Shawahna, S.M. Sait, A. El-Maleh, IEEE Access 7, 7823 (2019), 1901.00121
  * (44) T. Wang, C. Wang, X. Zhou, H. Chen, _An Overview of FPGA Based Deep Learning Accelerators: Challenges and Opportunities_ , in _2019 IEEE 21st International Conference on High Performance Computing and Communications; IEEE 17th International Conference on Smart City; IEEE 5th International Conference on Data Science and Systems (HPCC/SmartCity/DSS)_ (2019), p. 1674, 1901.04988
  * (45) J. Duarte et al., JINST 13, P07027 (2018), 1804.06913
  * (46) S. Summers et al., JINST 15, P05026 (2020), 2002.02534
  * (47) J. Ngadiuba et al., Mach. Learn.: Sci. Technol. 2, 015001 (2020), 2003.06308
  * (48) C.N. Coelho, A. Kuusela, S. Li, H. Zhuang, T. Aarrestad, V. Loncar, J. Ngadiuba, M. Pierini, A.A. Pol, S. Summers (2020), submitted to _Nat. Mach. Intell._ , 2006.10159
  * (49) T. Åarrestad et al. (2021), submitted to _Mach. Learn.: Sci. Technol._ , 2101.05108
  * (50) Y. Iiyama et al., Front. Big Data 3, 44 (2021), 2008.03601
  * (51) B. Moons, K. Goetschalckx, N.V. Berckelaer, M. Verhelst, _Minimum Energy Quantized Neural Networks_ , in _2017 51st Asilomar Conference on Signals, Systems, and Computers_ (2017), p. 1921, 1711.00215
  * (52) M. Courbariaux, Y. Bengio, J.P. David, _BinaryConnect: Training Deep Neural Networks with binary weights during propagations_ , in _Advances in Neural Information Processing Systems_ , edited by C. Cortes, N.D. Lawrence, D.D. Lee, M. Sugiyama, R. Garnett (Curran Associates, Inc., 2015), Vol. 28, p. 3123, 1511.00363, https://proceedings.neurips.cc/paper/2015/file/3e15cc11f979ed25912dff5b0669f2cd-Paper.pdf
  * (53) D. Zhang, J. Yang, D. Ye, G. Hua, _LQ-nets: Learned quantization for highly accurate and compact deep neural networks_ , in _Proceedings of the European Conference on Computer Vision (ECCV)_ (2018), p. 365, 1807.10029
  * (54) F. Li, B. Liu (2016), 1605.04711
  * (55) S. Zhou, Y. Wu, Z. Ni, X. Zhou, H. Wen, Y. Zou (2016), 1606.06160
  * (56) I. Hubara, M. Courbariaux, D. Soudry, R. El-Yaniv, Y. Bengio, J. Mach. Learn. Res. 18, 1 (2018), 1609.07061
  * (57) M. Rastegari, V. Ordonez, J. Redmon, A. Farhadi, _XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks_ , in _14th European Conference on Computer Vision (ECCV)_ (Springer International Publishing, Cham, Switzerland, 2016), p. 525, 1603.05279
  * (58) P. Micikevicius, S. Narang, J. Alben, G. Diamos, E. Elsen, D. Garcia, B. Ginsburg, M. Houston, O. Kuchaiev, G. Venkatesh et al., _Mixed precision training_ , in _6th International Conference on Learning Representations_ (2018), 1710.03740, https://openreview.net/forum?id=r1gs9JgRZ
  * (59) B. Zhuang, C. Shen, M. Tan, L. Liu, I. Reid, _Towards Effective Low-Bitwidth Convolutional Neural Networks_ , in _2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition_ (2018), p. 7920, 1711.00205
  * (60) N. Wang, J. Choi, D. Brand, C.Y. Chen, K. Gopalakrishnan, _Training deep neural networks with 8-bit floating point numbers_ , in _Advances in Neural Information Processing Systems_ , edited by S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, R. Garnett (Curran Associates, Inc., 2018), Vol. 31, p. 7675, 1812.08011, https://proceedings.neurips.cc/paper/2018/file/335d3d1cd7ef05ec77714a215134914c-Paper.pdf
  * (61) C. Coelho, _QKeras_ (2019), https://github.com/google/qkeras
  * (62) A. Pappalardo, _Xilinx/brevitas_ (2020), https://doi.org/10.5281/zenodo.3333552
  * (63) Y. LeCun, J.S. Denker, S.A. Solla, _Optimal Brain Damage_ , in _Advances in Neural Information Processing Systems 2_ , edited by D.S. Touretzky (Morgan-Kaufmann, 1990), p. 598, http://papers.nips.cc/paper/250-optimal-brain-damage
  * (64) S. Han, H. Mao, W.J. Dally, _Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding_ , in _4th International Conference on Learning Representations_ (2016), 1510.00149
  * (65) J. Frankle, M. Carbin, _The Lottery Ticket Hypothesis: Training Pruned Neural Networks_ , in _7th International Conference on Learning Representations_ (2019), 1803.03635, https://openreview.net/forum?id=rJl-b3RcF7
  * (66) H. Zhou, J. Lan, R. Liu, J. Yosinski, _Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask_ , in _Advances in Neural Information Processing Systems_ , edited by H. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché Buc, E. Fox, R. Garnett (Curran Associates, Inc., 2019), Vol. 32, p. 3597, 1905.01067, https://proceedings.neurips.cc/paper/2019/file/1113d7a76ffceca1bb350bfe145467c6-Paper
  * (67) D. Blalock, J.J.G. Ortiz, J. Frankle, J. Guttag, _What is the State of Neural Network Pruning?_ , in _4th Conference on Machine Learning and Systems_ (2020), 2003.03033
  * (68) B. Hawks, J. Duarte, N.J. Fraser, A. Pappalardo, N. Tran, Y. Umuroglu (2021), 2102.11289
  * (69) V. Loncar, S. Summers, N. Tran, B. Kreis, J. Duarte, jngadiub, D. Hoang, E. Kreinar, A.A. Pol, D. Golubovic et al., _fastmachinelearning/hls4ml_ (2021)
  * (70) S.R. Qasim, J. Kieseler, Y. Iiyama, M. Pierini, Eur. Phys. J. C 79, 608 (2019), 1902.07987
  * (71) A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A.N. Gomez, Ł. Kaiser, I. Polosukhin, _Attention Is All You Need_ , in _Advances in Neural Information Processing Systems_ , edited by I. Guyon, U.V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, R. Garnett (Curran Associates, Inc., 2017), Vol. 30, p. 5998, 1706.03762, https://proceedings.neurips.cc/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf
  * (72) N. Kitaev, Ł. Kaiser, A. Levskaya, _Reformer: The Efficient Transformer_ , in _8th International Conference on Learning Representations_ (2020), 2001.04451, https://openreview.net/forum?id=rkgNKkHtvB
  * (73) K. Choromanski, V. Likhosherstov, D. Dohan, X. Song, A. Gane, T. Sarlos, P. Hawkins, J. Davis, A. Mohiuddin, L. Kaiser et al., _Rethinking Attention with Performers_ , in _International Conference on Learning Representations_ (2021), 2009.14794, https://openreview.net/forum?id=Ua6zuk0WRH