# Tight lower bound on $|A+\lambda A|$ for algebraic integer $\lambda$

Dmitry Krachun, Fedor Petrov

###### Abstract

We prove an asymptotically tight lower bound on $|A+\lambda A|$ for
$A\subset\mathbb{C}$ and algebraic integer $\lambda$. The proof combines
strong version of Freiman’s theorem, structural theorem on dense subsets of a
hypercubic lattice and a generalisation of the continuous result on tight
bound for the measure of $K+\tau K$ for a compact subset
$K\subset\mathbb{R}^{d}$ of unit Lebesgue measure and a fixed linear operator
$\tau\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$, obtained by the authors in [7].

##  1 Introduction

For a subset $A\subset\mathbb{R}$ and a real number $\lambda\in\mathbb{R}$ we
define the set $A+\lambda A$ to be

$A+\lambda A:=\\{a_{1}+\lambda a_{2}:\,a_{1},a_{2}\in A\\}.$

The question of finding the asymptotically minimal possible size of $A+\lambda
A$ in term of the size of $A$ and $\lambda$ has received considerable
attention over recent years.

When $\lambda=p/q$ is a rational number with coprime integers $p,q$, Bukh [2]
proved that

$|A+\tfrac{p}{q}A|\geqslant(|p|+|q|)\cdot|A|-o(A),$

and the error term was later improved to a constant $C=C(p,q)$ in the work of
Balog and Shakan [1]. This is the best possible up to the dependence of $C$ on
$p,q$.

For transcendental $\lambda$ (it is easy to see that the bound does not depend
on $\lambda$ in this case) the lower bound is no longer linear. Indeed,
Konyagin and Łaba [6] showed that

$|A+\lambda A|\geqslant C\frac{|A|\log|A|}{\log\log|A|}$

for an absolute constant $C$.

This bound was then improved by Sanders [8] to $|A|\log^{4/3-o(1)}|A|$, then
by Schoen [10] to $(\log{|A|})^{c\log\log{|A|}}|A|$ and again by Sanders [9]
to $e^{\log^{c}{|A|}}|A|$ for some $c>0$. All these bounds relied on the
quantitative refinements of Freiman’s theorem. Very recently Conlon and Lim
[4] improved the bound to $e^{c\sqrt{\log{|A|}}}|A|$ for an absolute constant
$c>0$, using much more elementary methods. This bound is tight up to value of
the constant $c>0$, as follows from a construction from [6].

For the case of algebraic $\lambda$ we formulated a conjecture [7, Conjecture
1] about the value of $\liminf|A+\lambda A|/|A|$ and proved the upper bound,
see Conjecture 2 below. We also proved the conjecture for the specific case
$\lambda=\sqrt{2}$. For the case $\lambda:=(p/q)^{1/d}$ this conjecture was
proved by Conlon and Lim [3]. In this paper we prove the conjecture for all
algebraic integers $\lambda$.

To formulate the conjecture for arbitrary algebraic $\lambda$ we need the
following

######  Definition 1.1.

For an irreducible polynomial $f(x)\in\mathbb{Z}[x]$ of degree $d\geqslant 1$
(irreducibility in particular means that the coefficients of $f$ do not have a
common integer divisor greater than 1) denote

$H(f)=\prod_{i=1}^{d}(|a_{i}|+|b_{i}|),$

where $f(x)=\prod_{i=1}^{d}(a_{i}x+b_{i})$ is a full complex factorization of
$f$.

For arbitrary polynomial $f(x)\in\mathbb{C}[x]$ we define $H(f)$ to be equal
to $\min_{g|f}H(g)$, where the minimum is taken over all irreducible
polynomials $g(x)\in\mathbb{Z}[x]$ such that $g$ divides $f$ in
$\mathbb{C}[x]$. In the case when $f$ has no non-constant divisors with
integer coefficients we define $H(f):=\infty$.

For a linear operator $\mathcal{T}\in\operatorname{End}(\mathbb{R}^{d})$ we
define $H^{\circ}(\mathcal{T})$ to be equal to $H(f)$, where $f$ is the
characteristic polynomial of $\mathcal{T}$.

We also define, for a linear operator
$\mathcal{T}\in\operatorname{End}(\mathbb{R}^{d})$, $H(\mathcal{T})$ to be
equal to $\prod_{i=1}^{d}(1+|\lambda_{i}|)$, where $\lambda_{i}$’s are the
eigenvalues of $\mathcal{T}$.

Clearly, the value of $H(f)$ is well-defined, i.e. does not depend on the
factorization.

######  Remark 1.1.

We note that $H(\mathcal{T})$ is not in general equal to
$H^{\circ}(\mathcal{T})$. The former corresponds to the continuous problem of
bounding the measure of $\Omega+\mathcal{T}\Omega$ for a set
$\Omega\subset\mathbb{R}^{d}$ of measure 1, whereas the latter conjecturally
corresponds to discrete problem of bounding $A+\mathcal{T}A$ for large sets
$A$ of fixed size. In the case when
$\mathcal{T}\in\operatorname{End}(\mathbb{Z}^{d})$ has no invariant subspaces
we have $H(\mathcal{T})=H^{\circ}(\mathcal{T})$, see Proposition 1.

With this definition, [7, Conjecture 2] reads as

######  Conjecture 1.

Let $\mathcal{T}\in\operatorname{End}(\mathbb{R}^{d})$ be a linear operator.
Then

$\liminf_{|A|\rightarrow\infty,\,A\subset\mathbb{R}^{d}}\frac{|A+\mathcal{T}A|}{|A|}=H^{\circ}(\mathcal{T}).$

This conjecture yields the following result for the behaviour of
$\liminf|A+\lambda A|/|A|$ for algebraic $\lambda$, see [7] for details.

######  Conjecture 2.

Let $\lambda\in\mathbb{C}$ be an algebraic number with minimal polynomial
$f\in\mathbb{Z}[x]$. Then

$\liminf_{|A|\rightarrow\infty,\,A\subset\mathbb{C}}\frac{|A+\lambda
A|}{|A|}=H(f).$

The main goal of the paper is to prove Conjecture 1 for the case of
$\mathcal{T}\in\operatorname{End}(\mathbb{Z}^{d})$ and as a corollary, prove
Conjecture 2 for the case of algebraic integer $\lambda$. We prove the
following

######  Theorem 1.

Let $\mathcal{T}\in\operatorname{End}(\mathbb{R}^{d})$ be a linear operator
such that $\mathcal{T}(\mathbb{Z}^{d})\subset\mathbb{Z}^{d}$. Then

$\liminf_{|A|\rightarrow\infty,\,A\subset\mathbb{R}^{d}}\frac{|A+\mathcal{T}A|}{|A|}=H^{\circ}(\mathcal{T}).$

######  Theorem 2.

Let $\lambda\in\mathbb{C}$ be an algebraic integer number with minimal
polynomial $f$. Then

$\liminf_{|A|\rightarrow\infty,\,A\subset\mathbb{C}}\frac{|A+\lambda
A|}{|A|}=H(f)=\prod(1+|\lambda_{i}|),$ (1)

where $\lambda_{i}$’s are all algebraic conjugates of $\lambda$.

The rest of the paper is organised as follows. In Section 2 we relate
$H^{\circ}(\mathcal{T})$ to $H(\mathcal{T})$ for
$\mathcal{T}\in\operatorname{End}(\mathbb{Z}^{d})$, deduce Theorem 2 from
Theorem 1, and prove the upper bound in Theorem 1. Then in Section 3, we
reduce Theorem 1 to the special case when the set $A$ is a subset of a
$\mathbb{Z}^{n}\cap[0,N)^{n}$ of density at least
$\varepsilon=\varepsilon(\mathcal{T})$. This reduction relies on a cirtain
refinement of Freiman’s theorem. Finally, in Section 4, we complete the proof
of Theorem 1 by using a structural lemma on the dense subsets of a hypercube,
see Lemma 4.2, together with the continuous version of Theorem 1.

##  2 Preliminary observations

In this section we establish a relation between $H^{\circ}(\mathcal{T})$ and
$H(\mathcal{T})$ for endomorphisms of the $\mathbb{Z}^{d}$ lattice, deduce
Theorem 2 from Theorem 1 and also prove an upper bound in Theorem 1.

######  Proposition 1.

Let $\mathcal{T}\in\operatorname{End}(\mathbb{Z}^{d})$ then

$H^{\circ}(\mathcal{T})=\min_{\alpha:\mathcal{T}\alpha\subset\alpha}H(\mathcal{T}_{|\alpha}),$

where the minimum is taken over all invariant subspaces $\alpha$ of
$\mathbb{Q}^{d}$ and $\mathcal{T}$, as well as $\mathcal{T}_{|\alpha}$, is
identified, with a slight abuse of notation, with its extensition to a linear
operator on $\mathbb{Q}^{d}$ and $\mathbb{R}^{d}$.

###### Proof.

Let $f$ be the characteristic polynomial of $\mathcal{T}$. We first show that
the minimum is at least $H^{\circ}(\mathcal{T})$. Take any invariant subspace
$\alpha$, and let $g$ be the characteristic polynomial of
$\mathcal{T}_{|\alpha}$. Clearly $g$ is a divisor of $f$, and taking rational
basis of $\alpha$ and writing the matrix of $\mathcal{T}$ in this basis one
sees that $g$ has rational coefficients. Moreover, since $\pm g$ is monic and
all its roots are algebraic integers, it, in fact, has integer coefficients.
So we have

$\min_{\alpha:\mathcal{T}\alpha\subset\alpha}H(\mathcal{T}_{|\alpha})\geqslant\min_{g|f}H(g)=:H^{\circ}(\mathcal{T}).$

In the other direction, let $g$ be an irreducible divisor of $f$ of degree $m$
with integer coefficients. In particular, $\pm g$ is monic. Take the subspace
$\beta:=\operatorname{Ker}(g(\mathcal{T}))$ of $\mathbb{Q}^{d}$ which is non-
trivial since $g(\mathcal{T})$ is singular. Then take an arbitrary non-zero
vector $v\in\beta$ and consider the subspace $\beta^{\prime}:=\langle
v,\mathcal{T}v,\dots,\mathcal{T}^{m-1}v\rangle$ which is an invariant subspace
of $\mathcal{T}$, as follows from the fact that $g(\mathcal{T})v=0$. Note that
the characteristic polynomial of $\mathcal{T}_{|\beta^{\prime}}$ is $\pm g$
since any eigenvalue of $\mathcal{T}_{|\beta^{\prime}}$ is a root of $g$, the
dimension of $\mathcal{T}_{|\beta^{\prime}}$ is at most $m$, and $g$ is monic.
Hence, we have

$H^{\circ}(\mathcal{T}):=\min_{g|f}H(g)\geqslant\min_{\alpha:\mathcal{T}\alpha\subset\alpha}H(\mathcal{T}_{|\alpha}).$

∎

######  Remark 1.

Since $H(\mathcal{T}_{|\alpha})$ is non-decreasing in $\alpha$ under the
partial ordering given by inclusion of subspaces, the invariant subspace
$\alpha$ of minimal possible dimension among those with the minimal value of
$H(\mathcal{T}_{|\alpha})$ additionally does not have any non-trivial
invariant subspaces of $\mathcal{T}_{|\alpha}$.

###### Proof of Theorem 2 given Theorem 1.

The observation made in [7, Lemma 2.1] implies that we may work with subsets
of $\mathbb{Q}[\lambda]$, namely, that

$\liminf_{|A|\rightarrow\infty,\,A\subset\mathbb{C}}\frac{|A+\lambda
A|}{|A|}=\liminf_{|A|\rightarrow\infty,\,A\subset\mathbb{Q}[\lambda]}\frac{|A+\lambda
A|}{|A|}=\liminf_{|A|\rightarrow\infty,\,A\subset\mathbb{Z}[\lambda]}\frac{|A+\lambda
A|}{|A|},$

where the last equality follows by dilating $A$. Since $\lambda$ is an
algebraic integer, the linear operator $\mathcal{T}_{\lambda}$ defined by
$x\mapsto\lambda x$ is an endomorphism of $\mathbb{Z}[\lambda]$. Furthermore,
$\mathcal{T}_{\lambda}$ does not have invariant subspaces and its
characteristic polynomial is equal, up to a sign, to the minimal polynomial
$f$ of $\lambda$. So by Theorem 1 we have

$\liminf_{|A|\rightarrow\infty,\,A\subset\mathbb{Z}[\lambda]}\frac{|A+\lambda
A|}{|A|}=H^{\circ}(\mathcal{T}_{\lambda})=H(f),$

as desired.∎

Recall that a very similar argument is used in [7, Proposition 1].

###### Proof of the upper bound in Theorem 1.

Using Remark 1, choose a $\mathcal{T}$-invariant subspace
$\alpha\subset\mathbb{Q}^{d}$ satisfying
$H^{\circ}(\mathcal{T})=H(\mathcal{T}_{|\alpha})$, and such that $\alpha$ has
no non-trivial invariant subspaces of $\mathcal{T}_{|\alpha}$. Again, with
some abuse of notation we identify $\alpha$ with a subspace of
$\mathbb{R}^{d}$. It then suffices to construct large sets $A\subset\alpha$
such that $|A+\mathcal{T}_{|\alpha}A|\geqslant
H(\mathcal{T}_{|\alpha})\cdot|A|-o(|A|)$, since $\mathcal{T}$ and
$\mathcal{T}_{|\alpha}$ coinside on $\alpha$. So passing to
$\mathcal{T}_{|\alpha}$ if needed, without loss of generality we may assume
that the operator $\mathcal{T}$ itself has no non-trivial invariant subspaces
and so $H^{\circ}(\mathcal{T})=H(\mathcal{T})$.

Fix some small $\varepsilon>0$. As explained after the proof of [7, Theorem
2], the inequality
$\mu_{\star}(\Omega+\mathcal{T}\Omega)/\mu_{\star}(\Omega)\geqslant
H(\mathcal{T})$ is sharp and we can consider a convex compact set
$\Omega\subset\mathbb{R}^{d}$ which satisfies
$\mu(\Omega+\mathcal{T}\Omega)/\mu(\Omega)\leqslant
H(\mathcal{T})+\varepsilon$. Take $M$ large enough and consider the set
$\Omega_{M}:=\mathbb{Z}^{d}\cap M\cdot\Omega$. We have
$|\Omega_{M}|=\mu(\Omega)\cdot M^{d}+o(M^{d})$, and since
$\Omega_{M}+\mathcal{T}\Omega_{M}\subset(\Omega+\mathcal{T}\Omega)\cap\mathbb{Z}^{d}$
we have
$|\Omega_{M}+\mathcal{T}\Omega_{M}|\leqslant\mu(\Omega+\mathcal{T}\Omega)\cdot
M^{d}+o(M^{d})$, where we used the fact that both $\Omega$ and
$\Omega+\mathcal{T}\Omega$ are convex to approximate the number of integer
points in their dilates. This immediately implies that
$|\Omega_{M}+\mathcal{T}\Omega_{M}|/|\Omega_{M}|\leqslant
H(\mathcal{T})+\varepsilon+o_{M}(1)$, and since we can take $\varepsilon$ to
be arbitrary small, the upper bound follows. ∎

##  3 Reduction to the case of a dense subset of a box

To prove the lower bound in Theorem 1 we first want to reduce the problem to
the case of a set $A$ which forms a dense subset of a cube, i.e to the
following statement

######  Lemma 3.1.

Let $\mathcal{T}:\mathbb{Z}^{d}\rightarrow\mathbb{Z}^{d}$ be a linear operator
and $\varepsilon>0$. For any subset $A\subset\\{0,1,\dots,N-1\\}^{d}$ of size
$|A|\geqslant\varepsilon\cdot N^{d}$ we have

$|A+\mathcal{T}A|\geqslant H^{\circ}(\mathcal{T})\cdot|A|-o(|A|),$

where the implied constant in $o(\cdot)$ may depend both on $\mathcal{T}$ and
$\varepsilon$.

To deduce Theorem 1 from Lemma 3.1 we need a strong version of Freiman’s
theorem which we now state and prove.

###  3.1 Freiman’s theorem

######  Definition 3.1.

Let $(G,+)$ be an abelian group. A set $P\subset G$ is a _generalised
arithmetic progression_ 111Strictly speaking, a generalised arithmetic
progressions is not just a set but the collection of data
$(G;P;d;v_{0},v_{1},\dots,v_{d};L_{1},\dots L_{d})$ but this would be
cumbersome to write so with some abuse of notation we just write $P$ to denote
this collection of data. (GAP) of dimension $d\geqslant 1$ if it has the form

$P=\left\\{v_{0}+\ell_{1}v_{1}+\dots+\ell_{d}v_{d}\,:\,0\leqslant\ell_{j}\leqslant
L_{j}\right\\},$ (2)

where $v_{0},v_{1},\dots,v_{d}\in G,L_{1},L_{2},\dots,L_{d}\in\mathbb{Z}_{+}$.
The generalised arithmetic progression $P$ is said to be _proper_ if all sums
in (2) are distinct (in which case $|P|=(L_{1}+1)(L_{2}+1)\dots(L_{d}+1)$). We
say that $P$ is _$k$ -proper_ if

$k\cdot
P:=\left\\{v_{0}+\ell_{1}v_{1}+\dots+\ell_{d}v_{d}\,:\,0\leqslant\ell_{j}\leqslant
kL_{j}\right\\},$ (3)

has all elements on the RHS distinct, i.e. if $P$ is proper and $|k\cdot
P|=\prod_{j=1}^{d}(kL_{j}+1))$.

It will be convenient for us to work with GAPs which are (almost) symmetric
with respect to the origin. So we use the following

######  Definition 3.2.

Let $(G,+)$ be an abelian group. We call a set $P\subset G$ is a _centered
generalised arithmetic progression_ (c-GAP) of dimension $d\geqslant 1$ if it
has the form

$P=\left\\{\ell_{1}v_{1}+\dots+\ell_{d}v_{d}\,:\,-L_{j}\leqslant\ell_{j}\leqslant
L_{j}\right\\},$ (4)

where $v_{0},v_{1},\dots,v_{d}\in G,L_{1},L_{2},\dots,L_{d}\in\mathbb{Z}_{+}$.
For $k\geqslant 1$ and a centered GAP $P$ we write

$k\star
P:=\left\\{\ell_{1}v_{1}+\dots+\ell_{d}v_{d}\,:\,-kL_{j}\leqslant\ell_{j}\leqslant
kL_{j}\right\\}.$ (5)

We say that $P$ is _$k$ -proper_ if all elements on the RHS of (5) are
pairwise distinct.

######  Remark 3.1.

Note that any centered GAP $P$ can be seen as a GAP with $v_{0}=-\sum
L_{j}v_{j}$ and in this case $k\cdot P\not=k\star P$ for $k\geqslant 2$.
However, the notion of being $k$-proper coincides for these two points of
view, and this slight ambiguity should hopefully cause no confusion.

The following result is taken from [5, Theorem 1.1].

######  Lemma 3.2.

For every $K>0$ there exist constants $d=d(K)$ and $f=f(K)$ such that for any
abelian group $G$ and any subset $A\subset G$ with doubling constant at most
$K$ (i.e. such that $|A+A|\leqslant K|A|$) there exists a proper arithmetic
progression $P\subset G$ containing $A$ which has dimension at most $d(K)$ and
size at most $f(K)|A|$.

We need the following strengthening of this theorem, which ensures that not
only $P$ itself is proper but also its large multiple is proper. Note that in
this case we require the group $G$ to be torsion-free.

######  Lemma 3.3.

Let $\gamma:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$ be an arbitrary
function. For any $K>0$ there exist constants $d=d(K)$ and $F=F(K,\gamma)$
such that for any torsion-free abelian group $G$ and any subset $A\subset G$
with doubling constant at most $K$ (i.e. such that $|A+A|\leqslant K|A|$)
there exists a generalized arithmetic progression $P\subset G$ containing $A$
which has dimension at most $d(K)$, size at most $F(K,\gamma)|A|$, and is
$k$-proper with $k:=\gamma(\lfloor|P|/|A|\rfloor,d(P))$, where $d(P)$ is the
dimension of $P$.

###### Proof.

We use [11, Theorem 3.40] which states that any $d$-dimensional GAP $P$ in a
torsion-free abelian group $G$ can be embedded in a proper GAP $P^{\prime}$ of
size at most $d^{C_{0}d^{3}}|P|$ for fixed constant $C_{0}$, and that if $P$
is non-proper, then $P^{\prime}$ can be taken to have dimension at most $d-1$.
Note a caveat that in [11, Theorem 3.40] this latter statement about the
decrease in the dimension is stated for any abelian group $G$ but it, in fact,
only holds, and is proved, for the torsion-free case.

Now, we prove the lemma with the same $d(K)$ as in Lemma 3.2. First, consider
a proper arithmetic progression $P_{0}$ of dimension $d_{0}\leqslant d(K)$ and
size at most $f(K)|A|$ which contains $A$. If $P_{0}$ is $k_{0}$-proper with
$k_{0}:=\gamma(\lfloor|P_{0}|/|A|\rfloor,d)$ we stop. Otherwise, consider a
GAP $P_{1}\supset k_{0}\cdot P_{0}$ of dimension $d_{1}\leqslant d_{0}-1$ and
size at most $d^{C_{0}d^{3}}|k_{0}P_{0}|$. Again, if $P_{1}$ is $k_{1}$-proper
with $k_{1}:=\gamma(\lfloor|P_{1}|/|A|\rfloor,d_{1})$ we stop, otherwise we
consider $P_{2}\supset k_{1}\cdot P_{1}$ of dimension $d_{2}\leqslant d_{1}-1$
and size at most $d^{C_{0}d^{3}}|k_{1}P_{1}|$, etc. After some $s\leqslant
d(K)$ steps we stop and obtain a GAP $P_{s}$ of dimension $d_{s}\leqslant d$
which is $k_{s}$ proper with $k_{s}:=\gamma(\lfloor|P_{s}|/|A|\rfloor,d_{s})$.
Moreover, $|P_{s}|/|A|$ is bounded by a function which only depends on
$d(K),F(K)$ and $\gamma$.

∎

###  3.2 Lemma 3.1 implies Theorem 1

Recall that it only remains to prove the lower bound in Theorem 1. Before
proving the reduction to the case of a dense subset of a cube, we observe that
we may assume that $A\subset\mathbb{Q}^{d}$, see Lemma 3.4, and then show that
if $|A+\mathcal{T}A|\ll|A|$ then the set $A\cup\mathcal{T}A$ can be embedded
in a centered generalised arithmetic progression $P$ which is $k$-proper for
some large $k$, see Lemma 3.5. We also prove a simple lemma which is then used
in the proof of the reduction.

######  Lemma 3.4.

The lower bound in Theorem 1 follows from the lower bound in the special case
when $A\subset\mathbb{Q}^{d}$.

###### Proof.

Take an arbitrary finite set $A\subset\mathbb{R}^{d}$ write all relations of
the form $a+\mathcal{T}b=c+\mathcal{T}d$ for $(a,b,c,d)\in A^{4}$ which are
satisfied in coordinates. This gives a system of homogeneous linear equations
over $\mathbb{Q}$. Together with all conditions ensuring that all points of
$A$ are distinct (for any two points $a\neq b\in A$ we take a condition of
non-equality type $a_{j}\neq b_{j}$ for certain coordinate index $j$) this
gives us a system of equalities and non-equalities that, since solvable over
$\mathbb{R}$ (by elements of $A$) is also solvable over $\mathbb{Q}$ giving us
a set $A^{\prime}\subset\mathbb{Q}$ for which
$|A^{\prime}+\mathcal{T}A^{\prime}|\leqslant|A+\mathcal{T}A|$.

∎

So from now on we assume that $A\subset\mathbb{Q}^{d}$ and using induction we
further assume that the statement has been proved for all operators in
dimensions $1,2,\dots,d-1$.

######  Lemma 3.5.

For any function $\gamma:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$, an
operator $\mathcal{T}\in\operatorname{End}(\mathbb{Z}^{d})$, and $K>0$ there
exist constants $n_{0}=n_{0}(\mathcal{T},K)$ and $F=F(\gamma,\mathcal{T},K)$
such that the following holds. Assume that $A\subset\mathbb{Z}^{d}$ satisfies
$|A+\mathcal{T}A|\leqslant K\cdot|A|$. Then there exists a centred generalised
arithmetic progression $P$ in $\mathbb{Z}^{d}$ of dimension $n\leqslant n_{0}$
which has size at most $F\cdot|A|$, contains $(A-x)\cup\mathcal{T}(A-x)$ for
some $x\in\mathbb{Z}^{d}$, and is $k$-proper with
$k:=\gamma(\lfloor|P|/|A|\rfloor,n)$.

###### Proof.

Without loss of generality we may assume that $\gamma$ is increasing in each
variable. By Plünnecke inequality the set $B:=A\cup\mathcal{T}A$ satisfies
$|B+B|\leqslant(2K^{2}+K)\cdot|B|$ and so by Lemma 3.3 we can embed both $A$
and $\mathcal{T}A$ in some GAP $P$ of dimension $n=O_{K}(1)$ and size
$O_{K}(|A|)$ which is
$\gamma^{\prime}(\lfloor|P|/|A|\rfloor,n):=2\cdot\gamma(2^{n}\cdot\lfloor|P|/|A|\rfloor,n)$
proper.

Take arbitrary $x\in A$ and consider $A^{\prime}:=A-x$. Since
$A,\mathcal{T}A,\\{x\\},\\{\mathcal{T}x\\}\subset P$, we have
$A^{\prime},\mathcal{T}A^{\prime}\subset P-P=:P^{\prime}$ which is a centred
GAP. Also $P^{\prime}$ has size at most $4^{n}|P|$ and is $k/2$ proper
whenever $P$ is $k$-proper. It remains to note that
$\gamma(\lfloor|P^{\prime}|/|A^{\prime}|\rfloor,n)\leqslant\gamma^{\prime}(\lfloor|P|/|A|\rfloor,n)/2$
by the definition of $\gamma^{\prime}$. ∎

######  Lemma 3.6.

Let $v_{1},\dots,v_{d},v\in\mathbb{Z}^{n}$ be vectors such that $v\in\langle
v_{1},\dots,v_{d}\rangle$. Assume that all coordinates of all $v_{j}$ are
bounded, in absolute value, by some constant $C$. Then there exist integers
$s,s_{1},\dots,s_{d}$ such that

$sv=\sum_{j=1}^{d}s_{j}v_{j}$

where $s_{j}=O_{C,n}(\|v\|_{L^{\infty}})$ for each $j=1,\dots,d$ and
$s=O_{C,n}(1)$.

###### Proof.

Take some minimal subset $S$ of vectors among $v_{1},\dots,v_{d}$ which
linearly span $v$. Then vectors from $S$ are linearly independent and so we
can augment them with several vectors of the standard basis of
$\mathbb{Q}^{n}$ to form a basis $S^{\prime}$ of $\mathbb{Q}^{n}$. It then
remains to consider the unique linear combination of vectors in $S^{\prime}$
giving $v$. All vectors that we added to $S$ will come with zero coefficients
and so we will obtain a linear combination of vectors in $S$ giving $v$ in
which all coefficients are rational numbers with denominators of size
$O_{C,n}(1)$ and numerators of size $O_{C,n}(\|v\|_{L^{\infty}})$ as changing
one basis to another multiplies the vector of coefficients by some fixed
matrix with entries having bounded numerators and denominators. ∎

###### Proof of Theorem 1 given Lemma 3.1.

By Lemma 3.4 and dilating $A$ if necessary, we assume that
$A\subset\mathbb{Z}^{d}$. We also induct on the dimension $d$ assuming that
statement has been proved for all smaller dimensions. Note that for the base
case $d=1$ equivalence of Theorem 1 and Lemma 3.1 immediately follows from
Freiman’s theorem.

For a large finite set $A\subset\mathbb{Z}^{d}$ we want to show that

$|A+\mathcal{T}A|\geqslant H^{\circ}(\mathcal{T})\cdot|A|+o(|A|).$

In proving this we may assume the contrary, so $|A+\mathcal{T}A|\leqslant
K\cdot|A|$ with $K=K(\mathcal{T})=H^{\circ}(\mathcal{T})$. Since
$|A+\mathcal{T}A|=|(A-x)+\mathcal{T}(A-x)|$ for every $x\in\mathbb{Z}^{d}$,
using Lemma 3.5 we may assume that both $A$ and $\mathcal{T}A$ are inside some
centred generalised arithmetic progression $P$ of dimension $n$ which is
$k$-proper with $k:=\mathbb{k}(\lfloor|P|/|A|\rfloor,n)$ with function
$\mathbb{k}$ to be defined later, and such that
$|A|/|P|\geqslant\varepsilon=\varepsilon(\mathbb{k},\mathcal{T})$.

Let $w$ be the basis vector of $P$ corresponding to the largest $L_{j}$. For
this vector we know that $w,2w,\dots,Lw\in P$ where $L:=L_{j}\gg|A|^{1/n}$.
Since $L\gg|A|^{1/n}$, we may assume that $L$ is large enough in terms of
$\mathcal{T}$ for our argument to work. Consider vectors
$w_{0}:=w,w_{1}:=\mathcal{T}w,w_{2}:=\mathcal{T}^{2}w,\dots,w_{d-1}:=\mathcal{T}^{d-1}w$.
We consider two cases depending on whether these vectors are linearly
independent or not.

Case 1:  Vectors $w_{0},w_{1},\dots,w_{d-1}$ are linearly dependent in
$\mathbb{Q}^{d}$. Then the hyperplane $\alpha$ spanned by these vectors has
dimension smaller than $d$ and is such that the set $A$ lies in at most
$O(|A|/L)=O(|A|^{1-1/n})$ translates of $\alpha$. So we may write
$A=A_{1}\sqcup A_{2}\sqcup\dots\sqcup A_{m}$ where $A_{i}\subset
x_{i}+\alpha$, and $m\leqslant C(\mathcal{T})\cdot|A|^{1-1/n}$. We may assume
that $\lambda=-1$ is not an eigenvalue of $\mathcal{T}$, as otherwise
$H^{\circ}(\mathcal{T})=2$ and the inequality $|A+\mathcal{T}A|\geqslant
H^{\circ}(\mathcal{T})\cdot|A|-1$ follows from the torsion-free version of
Cauchy–-Davenport theorem. Note that for $i\not=j$ we have
$(A_{i}+\mathcal{T}A_{i})\cap(A_{j}+\mathcal{T}A_{j})=\emptyset$ as otherwise
we would have $[\operatorname{Id}+\mathcal{T}](x_{i}-x_{j})\in\alpha$ and
since $\operatorname{Id}+\mathcal{T}$ is invertible and
$\mathcal{T}\alpha\subset\alpha$ this would imply $x_{i}-x_{j}\in\alpha$
contradicting the fact that translates $x_{i}+\alpha$ and $x_{j}+\alpha$ are
distinct.

For the sets $B_{i}:=A_{i}-x_{i}\subset\alpha$ we have
$|A_{i}+\mathcal{T}A_{i}|=|B_{i}+\mathcal{T}_{|\alpha}B_{i}|$ and so the lower
bound for the operator $\mathcal{T}_{|\alpha}$, which has dimension smaller
than $d$, and sets $B_{1},\dots,B_{m}$ gives us

$|A+\mathcal{T}A|=\sum_{j=1}^{m}|B_{j}+\mathcal{T}_{|\alpha}B_{j}|\geqslant\sum_{j=1}^{m}H^{\circ}(\mathcal{T}_{|\alpha})\cdot|B_{j}|-o\left(\sum_{j=1}^{m}|B_{j}|\right)-O(m),$

where the last term comes from all the sets $B_{j}$ of constant size. Since
$\sum|B_{j}|=|A|$ and $m\ll|A|^{1-1/n}$ this immediately implies the result
for the operator $\mathcal{T}$ since
$H^{\circ}(\mathcal{T}_{|\alpha})\leqslant H^{\circ}(\mathcal{T})$ by
Proposition 1.

Case 2: Vectors $w_{0},w_{1},\dots,w_{d-1}$ are linearly independent in
$\mathbb{Q}^{d}$. We proceed in several steps:

Step 1: We show that there exist some constants
$\lambda=\lambda(\mathcal{T},d,n,\varepsilon)$ and
$k^{\prime}=k^{\prime}(\mathcal{T},d,n,\varepsilon)$ such that all vectors
$\ell\lambda w_{i}$ with $i\in\\{0,1,\dots,d-1\\}$ and $\ell\in[0\dots L]$ are
going to be in a multiple $k^{\prime}\star P$ of $P$.

It suffices to show the existence of such $\lambda_{j}$ and $k_{j}$ for each
$w_{j}$ separately and then take $\lambda:=\prod\lambda_{j}$ and
$k^{\prime}:=\lambda\cdot\max_{j}\\{k_{j}\\}$. We induct on $j$. For
$w_{0}:=w$ this follows from the construction as we took $w$ to be the basis
vector with the largest coordinate $L$. Now, assume that for $w_{j-1}$ we have
some values $\lambda_{j-1},k_{j-1}$. Then
$\lambda_{j-1}w_{j-1},2\lambda_{j-1}w_{j-1},\dots,L\lambda_{j-1}w_{j-1}$ are
all in $k_{j-1}\star P$. We want to show that there exist some
$\lambda_{j},k_{j}$ such that $\lambda_{j}sw_{j}\in k_{j}\star P$ for any
$s\in[1,\dots,L]$. To prove this, note that it is sufficient to find
$\lambda_{j},k_{j}$ such that $\lambda_{j}sw_{j}\in k_{j}\star P$ holds for
any $s\in[1,\dots,\delta L]$ with some constant
$\delta=\delta(\lambda_{j-1},k_{j-1},\varepsilon,n)>0$ and then multiply
$k_{j}$ by $\lceil 1/\delta\rceil$ to cover all $s\in[1,\dots,L]$. Indeed,
this follows from a trivial observation that any $s\in[1,\dots L]$ can be
written as a sum of at most $\lceil 1/\delta\rceil$ summands, each of which is
in $[1,\dots,\delta L]$, and the fact that we have $L$ large enough. We now
show how to construct such $\lambda_{j},k_{j}$ for
$\delta:=\varepsilon/(k_{j-1}+1)^{n}$, where we recall that $\varepsilon$ is a
lower bound for $|A|/|P|$.

To this end, choose arbitrary $s\in[1,\dots,\delta L]$ and let
$w=w(s):=sw_{j-1}$. Consider the following shifts of $A$:

$A,A+\lambda_{j-1}w,A+2\lambda_{j-1}w,\dots
A+\frac{(k_{j-1}+1)^{n}}{\varepsilon}\cdot\lambda_{j-1}w.$

Since $A\subset P$, by induction hypothesis and the fact that
$s\cdot\tfrac{(k_{j-1}+1)^{n}}{\varepsilon}\leqslant L$, all these sets are in
$P+k_{j-1}\star P$. As each of these sets has size
$|A|\geqslant\varepsilon|P|$ and the set $P+k_{j-1}\star P$ has size smaller
than $(1+k_{j-1})^{n}|P|$, by Dirichlet’s principle two of the sets must
intersect and so we have, for some
$c=c(s)\leqslant\tfrac{(k_{j-1}+1)^{n}}{\varepsilon}$, that
$c\lambda_{j-1}w\in A-A$. Since
$\mathcal{T}(A-A)=\mathcal{T}A-\mathcal{T}A\subset P-P\subset 2\star P$, this
implies that $c\cdot s\lambda_{j-1}w_{j}=\mathcal{T}(c\lambda_{j-1}w)\in
2\star P$. Which implies that for
$C:=\operatorname{lcm}(1,\dots,\lfloor\tfrac{(k_{j-1}+1)^{n}}{\varepsilon}\rfloor)$
we have

$C\cdot s\lambda_{j-1}w_{j}\in 2C\star P.$

Since $s\in[1,\dots,\delta L]$ was arbitrary, we can take
$\lambda_{j}:=C\lambda_{j-1}$ and $k_{j}:=2C$. As mentioned above, to cover
all $s\in[1,\dots,L]$ it is then sufficient to multiply $k_{j}$ by $\lceil
1/\delta\rceil$. This completes the proof of the induction step.

Step 2:  We show that, for $\lambda$ and $k^{\prime}$ as above, all
$\lambda\cdot w_{j}$’s (which are in $k^{\prime}\star P$) have only small
coordinates in the basis of $P$, and all non-zero coordinates correspond to
dimensions with $L_{j}\gg L$. Indeed, write $\lambda
w_{j}=\sum_{s=1}^{n}x_{s}v_{s}$, where
$v_{s}\in[-k^{\prime}L_{s},k^{\prime}L_{s}]$. Then with
$t:=1+\min_{s}k^{\prime}\cdot L_{s}/|v_{s}|$ (where the minimum is taken over
the coordinates with $v_{s}\not=0$) we have $t\lambda
w_{j}\in(2k^{\prime})\star P\setminus k^{\prime}\star P$ by the fact that $P$
is at least $2k^{\prime}$ proper. This implies that we must have $t>L$ which
in turn implies that $|k^{\prime}L_{s}/v_{s}|>L$ for each coordinate $s$ where
$v_{s}\not=0$. Since $L=\max L_{j}$, this is only possible if
$|v_{s}|\leqslant k^{\prime}$ and $L_{s}\geqslant L/k^{\prime}$, proving the
claim.

Step 3: Now, consider a natural embedding $\iota$ of $P$ into
$\mathbb{Z}^{n}\subset\mathbb{Q}^{n}$ (i.e. $\iota$ maps basic vectors of $P$
to the standard basis of $\mathbb{Z}^{n}$) which by properness can be extended
to $k\star P$, and consider a linear subspace $\alpha\subset\mathbb{Q}^{n}$
spanned by $\\{\iota\lambda w_{0},\dots,\iota\lambda w_{d-1}\\}$. Split $\iota
A\subset\iota P$ into subsets given by the intersections with shifts of this
linear subspace. We claim that the corresponding subdivision
$A:=A_{1}\sqcup\dots\sqcup A_{m}$ satisfies
$(A_{i}+\mathcal{T}A_{i})\cap(A_{j}+\mathcal{T}A_{j})=\emptyset$ for
$i\not=j$.

Indeed, arguing from contradiction, we assume that
$y_{i}+\mathcal{T}x_{i}=y_{j}+\mathcal{T}x_{j}$ for certain $x_{i},y_{i}\in
A_{i}$ and $x_{j},y_{j}\in A_{j}$. Then
$\iota(\operatorname{Id}+\mathcal{T})(x_{i}-x_{j})=\iota(x_{i}-y_{i}-x_{j}+y_{j})\in\alpha$
and $\iota(x_{i}-x_{j})\not\in\alpha$.

Since $x_{i},x_{j}\in A\subset P$ and also $\mathcal{T}A\subset P$, we have
$z:=(\operatorname{Id}+\mathcal{T})(x_{i}-x_{j})\in P+P-P-P=4\star P$. We also
know that $\iota z\in\alpha$ and $\iota z$ has all coordinates in
$\mathbb{Z}^{n}$ at most $4L$ in absolute value. Since $\iota\lambda
w_{j}\in\mathbb{Z}^{n}$ has all coordinates of size
$O_{\mathcal{T},\varepsilon}(1)$ for each $j=0,1,\dots,d-1$ by the argument in
the second step of the proof, we can apply Lemma 3.6 to deduce that
$\iota\lambda^{\prime}z=\sum_{j=0}^{d-1}s_{j}\iota w_{j}$ with
$s_{j}=O_{\mathcal{T},\varepsilon}(L)$ and
$\lambda^{\prime}=O_{\mathcal{T},\varepsilon}(1)$. Since $\iota$ is well
defined on $k\star P$, choosing the function $\mathbb{k}$ correctly this
ensures that $\lambda^{\prime}z=\sum_{j=0}^{d-1}s_{j}w_{j}$.

Now, as $(\operatorname{Id}+\mathcal{T})^{-1}$ can be written as a polynomial
of $\mathcal{T}$ with integer coefficients of size $O_{\mathcal{T}}(1)$, call
it $f(\mathcal{T})$, we have

$\lambda^{\prime}(x_{i}-x_{j})=f(\mathcal{T})[\lambda^{\prime}(\operatorname{Id}+\mathcal{T})(x_{i}-x_{j})]=f(\mathcal{T})[\lambda^{\prime}z]$

Reducing $f(x)\cdot(\sum_{j}s_{j}x^{j})$ modulo the minimal polynomial of
$\mathcal{T}$, we can rewrite the latter expression as a linear combination of
$w_{0},\dots,w_{d-1}$ with integer coefficients of size
$O_{\mathcal{T},\varepsilon}(L)$. Again, assuming function $\mathbb{k}$ was
chosen large enough, this linear combination is in $k\star
P\cap\iota^{-1}\alpha$, and so this implies that
$\iota(x_{i}-x_{j})\in\alpha$, giving a contradiction. This completes the
proof of the fact that $A_{i}\cap\mathcal{T}A_{i}$ are pairwise disjoint.

Step 4: Second step in this proof ensures that in the representation
$A:=A_{1}\sqcup\dots\sqcup A_{m}$ we have
$m=O_{\mathcal{T},\varepsilon}(|P|/L^{d})$, and so it suffices to prove that
$|A_{j}+\mathcal{T}A_{j}|\geqslant
H^{\circ}(\mathcal{T})\cdot|A_{j}|-o(L^{d})$ for each $j=1,2,\dots,m$ and then
sum all these inequalities. After shifting $A_{j}$ by some $x_{j}\in A_{j}$ we
have $\iota(A_{j}-x_{j})\subset\alpha\cap[-2L,2L]^{n}\subset\mathbb{Z}^{n}$
and by Lemma 3.6 and the argument in the second step of this proof we know
that for some constants
$\lambda^{\prime\prime}=O_{\mathcal{T},\varepsilon}(1)$ and
$L_{0}=O_{\mathcal{T},\varepsilon}(L)$ we have that

$\lambda^{\prime\prime}(A_{j}-x_{j})\subset\left\\{\sum_{k=0}^{d-1}m_{k}w_{k}\,\mid\,m_{k}\in[-L_{0},L_{0}]\right\\},$

which gives us a natural linear map
$\iota^{\prime}:\lambda^{\prime\prime}(A_{j}-x_{j})\rightarrow[-L_{0},L_{0}]^{d}\subset\mathbb{Z}^{d}$
such that $\iota^{\prime}\mathcal{T}=\widetilde{\mathcal{T}}\iota$ with the
operator $\widetilde{\mathcal{T}}$ acting on the standard basis
$\\{e_{0},\dots e_{d-1}\\}$ of $\mathbb{Z}^{d}$ as $e_{i}\mapsto e_{i+1}$ for
$i=0,\dots,d-2$ and $e_{d-1}\mapsto\sum_{k=0}^{d-1}\alpha_{k}e_{k}$ where
$x^{n}-\sum_{k=0}^{d-1}\alpha_{k}x^{k}$ is the characteristic polynomial of
$\mathcal{T}$. Let $B_{j}$ be the image of $A_{j}-x_{j}$ in $\mathbb{Z}^{d}$
under $\iota^{\prime}$. Since
$H^{\circ}(\widetilde{\mathcal{T}})=H^{\circ}(\mathcal{T})$ we have, by Lemma
3.1,

$|A_{j}+\mathcal{T}A_{j}|=|\lambda^{\prime\prime}(A_{j}-x_{j})+\mathcal{T}[\lambda^{\prime\prime}(A_{j}-x_{j})]|=|B_{j}+\widetilde{\mathcal{T}}B_{j}|\geqslant
H^{\circ}(\mathcal{T})|B_{j}|+o(L^{d}),$

where we note that the last inequality is trivially true if
$|B_{j}|=o(L^{d})$.

∎

##  4 The case of a dense subset of a box

In this section we prove Lemma 3.1. In order to do so, we approximate a
discrete set $A\subset[0,N)^{d}\cap\mathbb{Z}^{d}$ by a continuous density
function and then use the following generalisation of [7, Theorem 2]

######  Lemma 4.1.

Let $\mathcal{T}\in\operatorname{End}(\mathbb{R}^{d})$, and
$K\subset\mathbb{R}^{d}$ be a compact set. Assume that measurable non-negative
functions $f:K\rightarrow\mathbb{R}_{+}$ and
$h:K+\mathcal{T}K\rightarrow\mathbb{R}_{+}$ satisfy, for any $x,y\in K$, the
inequality $h(x+\mathcal{T}y)\geqslant f(x)$. Then one has

$\int_{K+\mathcal{T}K}h(z)\,d\mu(z)\geqslant
H(\mathcal{T})\cdot\int_{K}f(x)\,d\mu(x),$

where $H(\mathcal{T}):=\prod_{i=1}^{d}(1+|\lambda_{i}|)$ with $\lambda_{i}$’s
being eigenvalues of $\mathcal{T}$, and $\mu$ is the Lebesgue measure on
$\mathbb{R}^{d}$.

######  Remark 4.1.

[7, Theorem 2] bounds the volume of $K+\mathcal{T}K$ from below as
$H(\mathcal{T})$ times the volume of $K$. In other words, it exactly coincides
with the case $f=\mathbbm{1}_{K}$ and $h=\mathbbm{1}_{K+\mathcal{T}K}$.

###### Proof.

Consider the set $K_{f}\subset\mathbb{R}^{d+1}$ defined by
$K_{f}:=\\{(x,t):\,x\in K,\,0\leqslant t\leqslant f(x)\\}$, and the operator
$\mathcal{T}^{\prime}\in\operatorname{End}(\mathbb{R}^{d+1})$ defined by
$\mathcal{T}^{\prime}(x,t):=(\mathcal{T}(x),0)$. Then the inequality
$h(x+\mathcal{T}y)\geqslant f(x)$ implies the inclusion

$K_{f}+\mathcal{T}^{\prime}(K_{f})\subset(K+\mathcal{T}K)_{h},$

and so it suffices to apply [7, Theorem 2] to the set $K_{f}$ of measure equal
to $\int_{K}f(x)\,d\mu(x)$ and the map $\mathcal{T}^{\prime}$ which satisfies
$H(\mathcal{T}^{\prime})=H(\mathcal{T})$. ∎

To approximate a discrete set $A$ by a continuous density function, we need
the following structural result. In the following, for an integer $M$ by an
_$M$ -cube_ we mean a cube $[0,M)^{d}$ shifted by an element of
$(M\mathbb{Z})^{d}$.

######  Lemma 4.2.

For any $\varepsilon,\delta>0$ and $d\geqslant 1$ there exists
$B_{0}=B_{0}(\varepsilon,\delta,d)$ such that the following holds. Let
$\mathcal{P}:=[0,N)^{d}\cap\mathbb{Z}^{d}$ be a cube and let
$A\subset\mathcal{P}$ be a set of size at least $\varepsilon|\mathcal{P}|$.
Then there exist $B\leqslant B_{0}$ and a collection
$\\{\mathcal{P}_{1},\dots,\mathcal{P}_{s}\\}$ of disjoint $N/B$-cubes such
that the set $A^{\prime}:=A\cap(\cup\mathcal{P}_{i})$ satisfies

  * •

$|A^{\prime}|\geqslant(1-\delta)|A|$

  * •

$A^{\prime}$ is topologically $\delta$-dense in each $\mathcal{P}_{i}$, in the
sense that $\forall x\in\mathcal{P}_{i}\,\exists y\in
A^{\prime}\cap\mathcal{P}_{i}:\,|x_{j}-y_{j}|_{L^{\infty}}\leqslant\delta N/B$
for $j=1,\dots,d$.

###### Proof.

In the following we tacitly assume $1/\delta$ to be an integer. For
$\ell\geqslant 0$ let $B_{\ell}:=\delta^{-\ell}$. For each $\ell$ split
$\mathcal{P}$ into $B_{\ell}^{d}$ equal parts and let
$\mathcal{P}^{(\ell)}:=\cup_{i=1}^{s_{\ell}}\mathcal{P}_{i}^{(\ell)}$ be the
union of parts which contain at least one point of $A$. By construction we
have $\mathcal{P}^{(\ell)}\subset\mathcal{P}^{(\ell-1)}$.

Notice that
$|\mathcal{P}^{(\ell)}|\geqslant|A|\geqslant\varepsilon\cdot|\mathcal{P}|$ and
so for some
$\ell\leqslant\tfrac{\log{\varepsilon}}{\log{(1-\delta^{d+1}\varepsilon)}}$ we
must have
$|\mathcal{P}^{(\ell+1)}|\geqslant(1-\delta^{d+1}\varepsilon)|\mathcal{P}^{(\ell)}|$.
This means that at least $1-\varepsilon\delta$ fraction of
$\mathcal{P}_{i}^{(\ell)}$’s are subsets of $\mathcal{P}^{(\ell+1)}$ (i.e. we
kept all $\delta^{-d}$ smaller parts of them). Let
$\mathcal{Q}^{(\ell)}\subset\mathcal{P}^{(\ell)}$ be the union of such
$\mathcal{P}_{i}^{(\ell)}$’s and define
$A^{\prime}:=A\cap\mathcal{Q}^{(\ell)}$. Then the second condition of the
lemma is satisfied and we also have

$|A^{\prime}|\geqslant|A|-|\mathcal{P}^{(\ell)}\setminus\mathcal{Q}^{(\ell)}|\geqslant|A|-\varepsilon\delta\cdot|\mathcal{P}^{(\ell)}|\geqslant|A|-\varepsilon\delta|\mathcal{P}|\geqslant(1-\delta)|A|.$

Moreover, by construction we have
$B=\delta^{-\ell}\leqslant\exp{\\{\tfrac{-\log{\varepsilon}\cdot\log{\delta}}{\log{(1-\delta^{d+1}\varepsilon)}}\\}}$
∎

######  Remark 4.2.

By throwing away additionally at most $\varepsilon|A|$ points from
$A^{\prime}$ we could ask the density of $A^{\prime}$ to be at least
$\varepsilon^{2}/2$ in each of the $\mathcal{P}_{i}$.

We now turn to proving Lemma 3.1 which we restate for the convenience of the
reader.

######  Lemma 3.1.

Let $\mathcal{T}:\mathbb{Z}^{d}\rightarrow\mathbb{Z}^{d}$ be a linear operator
and $\varepsilon>0$. For any subset $A\subset\\{0,1,\dots,N-1\\}^{d}$ of size
$|A|\geqslant\varepsilon\cdot N^{d}$ we have

$|A+\mathcal{T}A|\geqslant H^{\circ}(\mathcal{T})\cdot|A|-o_{N}(|A|),$

where the implied constant in $o_{N}(\cdot)$ may depend both on $\mathcal{T}$
and $\varepsilon$.

###### Proof of Lemma 3.1.

Let $\delta>0$ be small enough. Since $A\subset[0,N)^{d}$, we have
$\mathcal{T}A\subset[-CN,CN]^{d}$ for some $C=C(\mathcal{T})$. Using Lemma 4.2
we construct $\mathcal{T}A^{\prime}\subset\mathcal{T}A$ of size at least
$(1-\delta)|A|$ and a collection $\\{\mathcal{Q}_{1},\dots,\mathcal{Q}_{s}\\}$
of cubes of size $N/B$, where $B<B_{0}(\varepsilon,\delta,d,C)$, such that
$\mathcal{T}A^{\prime}$ is topologically $\delta$-dense in each of
$\mathcal{Q}_{i}$’s.

Now, consider a set $\mathcal{T}^{-1}\left(\cup\mathcal{Q}_{i}\right)$ and
approximate it with a collection of $\delta^{\prime}N/B$-cubes
$\\{\mathcal{P}_{1},\dots,\mathcal{P}_{s^{\prime}}\\}$ by taking all
$\delta^{\prime}N/B$-cubes inside each of the sets
$\mathcal{T}^{-1}\mathcal{Q}_{j}$. For any $\delta^{\prime}$ small enough in
terms of $\mathcal{T}$ we can ensure that

$|\mathcal{Q}_{j}\setminus(\cup_{j^{\prime}=1}^{s^{\prime}}\mathcal{P}_{j^{\prime}})|\leqslant
C_{1}(\mathcal{T})\cdot\delta^{\prime}\cdot|\mathcal{Q}_{j}|,$

with some constant $C_{1}(\mathcal{T})$ depending only on $\mathcal{T}$.

We now consider the set $K:=\cup_{i=1}^{s^{\prime}}\mathcal{P}_{i}$ and a
piece-wise constant function $f:K\rightarrow\mathbb{R}_{+}$ defined on it by
$f(x):=|A\cap\mathcal{P}_{i}|/|\mathcal{P}_{i}|$ for each
$x\in\mathcal{P}_{i}$. We then cover $K+\mathcal{T}K$ by $\delta^{\prime}N/B$
cubes $\\{\mathcal{R}_{1},\dots,\mathcal{R}_{s^{\prime\prime}}\\}$ and
consider a piece-wise constant function
$h:K+\mathcal{T}K\rightarrow\mathbb{R}_{+}$ defined by
$h(z):=|(A+\mathcal{T}A)\cap\mathcal{R}_{i}|/|\mathcal{R}_{i}|+(1+\delta/\delta^{\prime})^{d}-1$
for each $z\in\mathcal{R}_{i}$.

Claim: Functions $f,h$ satisfy the assumption of Lemma 4.1, i.e for any $x\in
K$ and $y\in K$ one has $h(x+\mathcal{T}y)\geqslant f(x)$.

Proof of the claim: Indeed, consider a $\delta^{\prime}N/B$-cubes
$\mathcal{P}_{j^{\prime}}$ containing $x$ and $\mathcal{R}_{j^{\prime\prime}}$
containing $x+\mathcal{T}y$. For some
$y_{0}\in(\delta^{\prime}N/B\cdot\,\mathbb{Z})^{d}$ we have
$\mathcal{R}_{j^{\prime\prime}}=y_{0}+\mathcal{P}_{j^{\prime}}$. Since
$x+\mathcal{T}y$ lies both in $\mathcal{P}_{j^{\prime}}+\mathcal{T}y$ and
$\mathcal{R}_{j^{\prime\prime}}=y_{0}+\mathcal{P}_{j^{\prime}}$, we must have
$\|y_{0}-\mathcal{T}y\|_{L^{\infty}}\leqslant\delta^{\prime}N/B$.

By construction we have $\mathcal{T}K\subset\cup\mathcal{Q}_{i}$, so there
exists some $j\in[1,\dots,s]$ such that $\mathcal{T}y\in\mathcal{Q}_{j}$. The
fact that $y_{0}\in(\delta^{\prime}N/B\,\mathbb{Z})^{d}$ and
$\|y_{0}-\mathcal{T}y\|_{L^{\infty}}\leqslant\delta^{\prime}N/B$ implies that
$y_{0}$ also lies in (the closer of) $\mathcal{Q}_{j}$. Since
$\mathcal{T}A^{\prime}$ is $\delta$-dense in $\mathcal{Q}_{j}$ there exists
$y^{\prime}\in A^{\prime}$ such that
$\|\mathcal{T}y^{\prime}-y_{0}\|\leqslant\delta N/B$. We then have

$|(A+\mathcal{T}A)\cap\mathcal{R}_{j^{\prime\prime}}|\geqslant|((A\cap\mathcal{P}_{j^{\prime}})+\mathcal{T}y^{\prime})\cap\mathcal{R}_{j^{\prime\prime}}|\geqslant|A\cap\mathcal{P}_{j^{\prime}}|-|(\mathcal{P}_{j^{\prime}}+\mathcal{T}y^{\prime})\setminus\mathcal{R}_{j^{\prime\prime}}|$
(6)

Since $\mathcal{R}_{j^{\prime\prime}}=y_{0}+\mathcal{P}_{j^{\prime}}$ and
$\|\mathcal{T}y^{\prime}-y_{0}\|\leqslant\delta N/B$ we can bound the last
term by

$(\delta^{\prime}N/B+\delta
N/B)^{d}-(\delta^{\prime}N/B)^{d}\leqslant|\mathcal{R}_{j^{\prime\prime}}|\cdot\left((1+\delta/\delta^{\prime})^{d}-1\right).$

Dividing (6) by $|\mathcal{R}_{j^{\prime\prime}}|=|\mathcal{P}_{j^{\prime}}|$
we infer that $h(x+\mathcal{T}y)\geqslant f(x)$. This concludes the proof of
the claim.

Now by Lemma 4.1 we know that

$\int_{K+\mathcal{T}K}h(z)\,d\mu(z)\geqslant
H(\mathcal{T})\cdot\int_{K}f(x)\,d\mu(x).$ (7)

Recalling the definition of $h$ we can upper bound the LHS by

$|A+\mathcal{T}A|+((1+\delta/\delta^{\prime})^{d}-1)\cdot|K+\mathcal{T}K|\leqslant|A+\mathcal{T}A|+((1+\delta/\delta^{\prime})^{d}-1)\cdot|A|/\varepsilon\cdot
C_{2}(\mathcal{T}).$

Whereas for the integral on the right we have a lower bound of

$\displaystyle|A^{\prime}|-|\mathcal{T}^{-1}(\cup\mathcal{Q}_{j})\setminus(\cup\mathcal{P}_{j^{\prime}})|$
$\displaystyle\geqslant(1-\delta)|A|-C_{1}(\mathcal{T})\cdot\delta^{\prime
1/d}\cdot|\cup\mathcal{Q}_{j}|$
$\displaystyle\geqslant|A|-\delta|A|-C_{3}(\mathcal{T})\cdot(|A|/\varepsilon)\cdot\delta^{\prime
1/d},$

where for the last inequality we used the fact that $|A|/\varepsilon\geqslant
N^{d}$ and that all cubes $\mathcal{Q}_{j}$ are inside $[-CN,CN]^{d}$ for
$C=C(\mathcal{T})$. It then remains to choose first $\delta^{\prime}$ small
enough in terms of $\mathcal{T}$ and $\varepsilon$ and then $\delta$ small
enough in terms of $\delta^{\prime},\varepsilon,\mathcal{T}$ to conclude that
(7) implies that

$|A+\mathcal{T}A|\geqslant H(\mathcal{T})\cdot|A|-o(|A|).$

∎

Acknowledgement:  We would like to thank Ilya Losev for useful discussions and
useful comments on earlier version of the paper.

## References

  * [1] Antal Balog and George Shakan.  On the sum of dilations of a set.  Acta Arithmetica, 164(2):153–162, 2014.
  * [2] Boris Bukh.  Sums of dilates.  Combinatorics, Probability and Computing, 17(05):627–639, June 2008\.
  * [3] David Conlon and Jeck Lim.  Sums of linear transformations.  arXiv:2203.09827v1, 2022.
  * [4] David Conlon and Jeck Lim.  Sums of transcendental dilates.  arXiv:2212.10128v1, 2022.
  * [5] Ben Green and Imre Z. Ruzsa.  Freiman’s theorem in an arbitrary abelian group.  Journal of the London Mathematical Society, 75(1):163–175, January 2007.
  * [6] Sergei Konyagin and Izabella Łaba.  Distance sets of well-distributed planar sets for polygonal norms.  Israel Journal of Mathematics, 152(1):157–179, December 2006.
  * [7] Dmitry Krachun and Fedor Petrov.  On the size of $A+\lambda A$ for algebraic $\lambda$.  Mosc. J. Comb. Numb. Th., 12(2):117–126, 2023.
  * [8] Tom Sanders.  Appendix to ‘‘Roth’s theorem on progressions revisited’’, by J. Bourgain.  Journal d’Analyse Mathématique, 104(1):193–206, January 2008\.
  * [9] Tom Sanders.  On the Bogolyubov–Ruzsa lemma.  Anal. PDE, 5(3):627–655, 2012.
  * [10] Tomasz Schoen.  Near optimal bounds in Freiman’s theorem.  Duke Math. J., 158(1):1–12, 05 2011.
  * [11] Terence Tao and Van H. Vu.  Additive Combinatorics.  Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2006.


marginparsep has been altered.
topmargin has been altered.
marginparpush has been altered.
The page layout violates the ICML style. Please do not change the page layout,
or include packages like geometry, savetrees, or fullpage, which change it for
you. We’re not able to reliably undo arbitrary changes to the style. Please
remove the offending package(s), or layout-changing commands and try again.

Learning Observation Models with Incremental Non-Differentiable Graph
Optimizers in the Loop for Robotics State Estimation

Mohamad Qadri 1  Michael Kaess 1

††footnotetext:  1Robotics Institute, Department of Computer Science, Carnegie
Mellon University, Pittsburgh, United States. Correspondence to: Mohamad Qadri
<EMAIL_ADDRESS>
Published at the Differentiable Almost Everything Workshop of the
$\mathit{40}^{th}$ International Conference on Machine Learning, Honolulu,
Hawaii, USA. July 2023. Copyright 2023 by the author(s). Figure 1: The
parameter vector $\boldsymbol{\theta}^{t}$ serve as input to the least squares
problem which is solved by iSAM2. Gradients of the solution with respect to
the parameters are computed and used to update $\boldsymbol{\theta}^{t+1}$

###### Abstract

We consider the problem of learning observation models for robot state
estimation with incremental non-differentiable optimizers in the loop.
Convergence to the correct belief over the robot state is heavily dependent on
a proper tuning of observation models which serve as input to the optimizer.
We propose a gradient-based learning method which converges much quicker to
model estimates that lead to solutions of much better quality compared to an
existing state-of-the-art method as measured by the tracking accuracy over
unseen robot test trajectories.

##  1 Introduction

Robot state estimation is the problem of inferring the state of a robot (a set
of geometric or physical quantities such as position, orientation, contact
forces etc.) given sensor measurements. The problem is typically formulated as
Maximum a Posteriori (MAP) inference over factor graphs where each node (robot
state) is connected to other states via soft constraints or potentials
(factors) which are distilled from sensor measurements. Given a factor graph,
a potential way to perform the inference step is to convert it to a chordal
Bayes Net using an exact inference technique (i.e. variable elimination) and
then in turn, convert the Bayes Net to a tree like structure (i.e. junction
tree) where inference can be made easier. However, this procedure can become
ill-suited for real-time state estimation especially if the number of
variables in the problem increases with time (i.e. as the robot navigates the
environment). The Bayes tree Kaess et al. (2011) was introduced to tackle this
problem. It is a tree structure where nodes are formed from the maximal
cliques of a chordal Bayes net. The Bayes tree is directed and maintains the
conditional independences described by the original Bayes net. In addition, it
allows for fast incremental inference which corresponds to simple tree
editing.

iSAM2 Kaess et al. (2012) is an optimizer that leverages the Bayes tree to
solve incremental (i.e. as the number of factors $N$ grows continuously)
inference problems formulated as a factor graph. In essence, it solves
problems of the form:

$\displaystyle\mathbf{x}^{*}=\operatorname*{arg\,min}_{\mathbf{x}}\sum_{i=1}^{N}\frac{1}{2}||g_{i}(\mathbf{x}_{i})-z_{i}||_{\theta_{i}}^{2}$
(1)

or equivalently the MAP inference problem:

$\displaystyle\mathbf{x}^{*}=\operatorname*{arg\,max}_{\mathbf{x}}\prod_{i}^{N}\phi_{i}(\mathbf{x}_{i})$
(2)

where $\phi_{i}$ are the potentials assumed to take the form
$\phi_{i}\\!\propto\\!\exp\left(-\frac{1}{2}||g_{i}(\mathbf{x}_{i})-z_{i})||_{\theta_{i}}^{2}\right)$,
$\mathbf{x}$ is the vector of unknown states, $\mathbf{x}_{i}$ a subset of
$\mathbf{x}$, and $\mathbf{z}=\\{z_{i}\\}$ are the sensor measurements. Batch
solvers such as Levenberg-Marquardt perform the typical linearize-solve loop
which quickly becomes prohibitively expensive as the size of the problem
grows. iSAM2, on the other hand, leverages the Bayes tree and uses fluid
relinarization and partial state updates making it the de-facto optimizer for
online smoothing-based state estimation problems in robotics. However, these
features also prevent iSAM2 from being differentiable (i.e. dependence on
relinearization thresholds, inherent non-differentiable operations such as
removal and re-insertion of tree nodes.)

On the other hand, the quality of the solution of eq.1 is largely dependent on
a proper selection of the observation models $\\{\theta_{i}\\}$ which
parameterize the joint or conditional distributions over states and
measurements. However, due the non-differentiability of iSAM2, current methods
to tune these parameters are generally sampling-based which are slow and may
converge to poor optimas. In this work, we propose a gradient-based
optimization-based approach to tune $\\{\theta_{i}\\}$ with iSAM2 in the loop
using a direct tracking error loss. We compare our method with a state-of-the-
art sampling-based method on a synthetic robot navigation example and show
that our procedure converges order-of-magnitude faster to a better solution as
measured by the tracking accuracy over unseen robot test trajectories.

##  2 Related Work

Early state estimation techniques such as the family of Kalman Filters Julier
& Uhlmann (2004); Thrun et al. (2001) rely on the Markov assumption to enable
real-time performance. Recent algorithms have been proposed to make these
filters differentiable Kloss et al. (2021); Sun et al. (2016); Haarnoja et al.
(2016). However, the inherent reliance on the Markov assumption and the
inability to re-linearize past states can lead to convergence to poor
solutions. Hence, state-of-the-art robotic state estimation algorithms moved
to factor graph-based solutions which encode the inherent temporal structure
avoiding the need to marginalize past states and providing methods to
relinearize past estimates Kaess et al. (2012); Qadri et al. (2022). However,
observation models on factor graphs are either pre-specified and fixed Lambert
et al. (2019); Engel et al. (2014) or learned using surrogate losses
independent of the graph optimizer or final tracking performance Sodhi et al.
(2021); Sundaralingam et al. (2019); Czarnowski et al. (2020). Methods that
differentiate through the $\operatorname*{arg\,min}$ operator in eq. 1 by
unrolling the optimizer can be used to learn these models Yi et al. (2021);
Krishna Murthy et al. (2020); Bechtle et al. (2021). However, these techniques
are typically sensitive to hyperparameters such as the number of unrolling
steps Amos & Yarats (2020) in addition to suffering from vanishing as well as
high bias and variance gradients. Recently, a novel method LEO Sodhi et al.
(2022) took advantage of the probabilistic view offered by iSAM2 (as a solver
of eq.2) to provide a way to learn observation models, with iSAM2 in the loop,
by minimizing a novel tracking error. In essence, at every training iteration
LEO samples trajectories from the posterior distribution (a joint Gaussian
distribution over the states) and the deviation with respect to the ground
truth trajectory is minimized using an energy-based loss. In this work, we use
LEO as our baseline.

##  3 Method

In this work, we view the incremental optimizer (iSAM2) as a function
$f:\mathcal{X}\times\boldsymbol{\theta}\rightarrow\mathcal{X}$ which takes
initial estimates of the state
$\mathbf{x}\in\mathcal{X}:\mathcal{M}_{1}\times\ldots\times\mathcal{M}_{n}$ at
timestep $t$ (the number of states increases with time), as well as parameters
$\boldsymbol{\theta}=\\{\theta_{i}\;|\;\theta_{i}\in\mathcal{S}^{n_{i}}_{++}\\}$
and returns an estimate of the optimal state $\mathbf{x}_{*}\in\mathcal{X}$
after performing $N$ update steps. Here, $\mathcal{M}_{i}$ is a Lie Group (for
example the special Euclidean group $SE(n)$) and $\mathcal{S}^{n_{i}}_{++}$ is
the set of $n_{i}\times n_{i}$ positive definite matrices .

Our goal is to learn the parameters $\\{\theta_{i}\\}$ using gradient-based
methods from observed ground truth robots trajectories $\mathbf{x}_{GT}$.
Specifically, We consider the following inner-outer optimization procedure:

$\displaystyle\text{Inner Loop:
}\;\hat{\mathbf{x}}(\boldsymbol{\theta)}=\operatorname*{arg\,min}_{\mathbf{x}}H(\mathbf{x},\boldsymbol{\theta};\mathbf{z})$
$\displaystyle\quad\quad\quad\quad\quad\quad\;\;\;\;\,\,=\operatorname*{arg\,min}_{\mathbf{x}}\sum_{i}\frac{1}{2}||g_{i}(\mathbf{x})-z_{i}||^{2}_{\theta_{i}}$
(3) $\displaystyle\text{Outer
Loop:}\;\min_{\boldsymbol{\theta}}\mathcal{L}(\hat{\mathbf{x}}(\boldsymbol{\theta)},\mathbf{x}_{GT})$
(4)

Note that the gradient $\frac{\partial L}{\partial\boldsymbol{\theta}}$,
requires an estimate of
$\frac{\partial\hat{\mathbf{x}}}{\partial\boldsymbol{\theta}}$. Although iSAM2
includes different non-differentiable operations, the gradient of the solution
with respect to the parameter vector
$\frac{\partial\hat{\mathbf{x}}}{\partial\boldsymbol{\theta}}$ exists and can
be computed by the implicit function theorem Dontchev et al. (2009) as done in
existing work in convex optimization Amos & Kolter (2017); Agrawal et al.
(2019). Note that the original theorem consider functions operating on vector
spaces. However, the theorem can readily be extended to other manifolds by
applying the appropriate group operations. Let
$h(\mathbf{x},\boldsymbol{\theta}):=\frac{\partial H}{\partial\mathbf{x}}$.

The Implicit Function Theorem:
Let
$\mathbf{\hat{x}}(\boldsymbol{\theta}):=\\{\mathbf{x}\;|\;h(\mathbf{x},\boldsymbol{\theta})=0\\}$
where $\mathbf{x}\in\mathcal{X}$ and
$\boldsymbol{\theta}=\\{\theta_{i}\;|\;\theta_{i}\in\mathcal{S}^{n}_{++}\\}$.
Let $h$ be continuously differentiable in the neighborhood of
$(\mathbf{\hat{x}},\boldsymbol{\theta})$ namely
$\nabla_{\mathbf{x}}h(\mathbf{\hat{x}}(\boldsymbol{\theta}),\boldsymbol{\theta})$
be nonsingular. Then:

$\displaystyle\frac{\partial
f}{\partial\boldsymbol{\theta}}=\frac{\partial\mathbf{\hat{x}}(\boldsymbol{\theta})}{\partial\boldsymbol{\theta}}=-\left(\frac{\partial
h(\mathbf{\hat{x}}(\boldsymbol{\theta}),\boldsymbol{\theta})}{\partial\mathbf{x}}\right)^{-1}\frac{\partial
h(\mathbf{\hat{x}}(\boldsymbol{\theta}),\boldsymbol{\theta})}{\partial\mathbf{\boldsymbol{\theta}}}$
(5)

The gradient in eq. 5 can be derived and computed analytically. However, we
note that since the size of parameter vector $\boldsymbol{\theta}$ is
typically small (for example, each $\theta_{i}$ has a maximum of $6$ free
parameters when working with elements in $SE(2)$), numerical differentiation
proved to be efficient especially when coupled with parallelization on CPU.

Figure 2: Convergence as a function of training time measured in minutes. Both
methods were run for 100 training iterations. Our method converges after a few
seconds while each iteration of LEO takes approximately 2.5 minutes.
Additionally, our method converges to parameters that track the training
trajectories more accurately. Figure 3: Accuracy on the test set. Our method
converges to parameters that generalize and track the test trajectories more
accurately.

###  3.1 Numerical Jacobians over Lie Groups

####  3.1.1 Jacobians on Vector Spaces

Given a multivariate function $f:\mathbb{R}^{m}\rightarrow\mathbb{R}^{n}$, the
Jacobian is defined as the $n\times m$ matrix:

$\displaystyle\frac{\partial
f(\mathbf{x})}{\partial\mathbf{x}}=\begin{bmatrix}\frac{\partial
f_{1}}{\partial x_{1}}&\ldots&\frac{\partial f_{1}}{\partial x_{m}}\\\
\vdots&\vdots&\vdots\\\ \frac{\partial f_{n}}{\partial
x_{1}}&\ldots&\frac{\partial f_{n}}{\partial x_{m}}\\\ \end{bmatrix}$ (6)

where $\frac{\partial f}{\partial x_{i}}=\lim\limits_{h\rightarrow
0}\frac{f(\mathbf{x}+h\mathbf{e}_{i})-f(\mathbf{x})}{h}$ and $\mathbf{e}_{i}$
is the $i$th standard basis of $\mathbb{R}^{m}$.

####  3.1.2 Left Jacobians on Lie Groups

We can similarly define the left Jacobian of functions acting on manifolds
$f:\mathcal{N}\rightarrow\mathcal{M}$ as the linear map from the Lie algebra
$T_{\epsilon}(\mathcal{N})$ of $\mathcal{N}$ to $T_{\epsilon}(\mathcal{M})$,
the Lie algebra of $\mathcal{M}$:

$\displaystyle\frac{{}^{\epsilon}Df(\mathcal{X})}{D\mathcal{Y}}=\lim\limits_{\tau\rightarrow
0}\frac{f(\tau\oplus\mathcal{Y})\ominus f(\mathcal{Y})}{\tau}$ (7)
$\displaystyle\quad\quad\quad\;\;\;=\lim\limits_{\tau\rightarrow
0}\frac{\text{Log}(f(\text{Exp}(\tau)\circ\mathcal{Y})\circ
f(\mathcal{Y})^{-1})}{\tau}$ (8)

where $\mathcal{Y}\in\mathcal{N}$, $\tau$ is a small increment defined on
$T_{\epsilon}(\mathcal{N})$. The Log operator map elements from a Lie Group to
its algebra while the Exp operator map elements from the algebra to the group.
$\oplus$, $\ominus$, and $\circ$ are the plus, minus, and composition
operators respectively Sola et al. (2018) where:

$\displaystyle\tau\oplus\mathcal{Y}=\text{Exp}(\tau)\circ\mathcal{Y}$ (9)
$\displaystyle\tau=\mathcal{Y}_{1}\ominus\mathcal{Y}_{2}=\text{Log}(\mathcal{Y}_{1}\circ\mathcal{Y}_{2}^{-1});\;\mathcal{Y}_{1},\mathcal{Y}_{2}\in\mathcal{N}$
(10)

In this work,
$\mathcal{N}=\mathcal{S}^{n_{1}}_{++}\times\ldots\times\mathcal{S}^{n_{m}}_{++}$
and $\mathcal{M}=\mathcal{X}$. Additionally, we assume that each vector
$\theta_{i}$ are the square root elements of some corresponding diagonal
positive definite matrix $\Sigma_{i}\in\mathcal{S}^{n_{i}}_{++}$. i.e., we
define the following map:

$\displaystyle\theta_{i}=\left(\text{diag}^{-1}(\Sigma_{i})\right)^{2}\in\mathbb{R}^{n_{i}}$
(11)

Hence, $\tau\in\mathbb{R}^{n_{i}}$ and the operator $\oplus$ is the standard
addition on vector space $\mathbb{R}^{n_{i}}$.

###  3.2 Tracking Loss

Let a parameter estimate $\boldsymbol{\theta}^{t}\in\mathbb{R}^{m}$. The outer
loss is the regularized mean squared error between the estimated trajectory
$\mathbf{\hat{x}}(\boldsymbol{\theta}^{t})$ and the ground truth
$\mathbf{x}_{GT}$. Let $\mathcal{D}$ be the training set, $T$ be the total
number of states in $\mathbf{x}_{\text{GT}}$, $D$ be the sum of the lie
algebra dimensions of all states, and $\lambda\in\mathbb{R}$:

$\displaystyle\\!\\!\\!\mathcal{L}(\boldsymbol{\theta})=\frac{1}{2|\mathcal{D}|}\sum_{j=1}^{\mathcal{|D|}}||\textbf{vec}(\mathbf{\hat{x}}^{j}(\boldsymbol{\theta}^{t})\ominus\mathbf{x}_{GT})||_{2}^{2}+\lambda||\boldsymbol{\theta}^{t}||_{2}^{2}$
(12)
$\displaystyle\\!\\!\\!\\!\frac{\partial\mathcal{L}}{\partial\boldsymbol{\theta}}\\!=\\!\frac{1}{|\mathcal{D}|}\sum_{j=1}^{|\mathcal{D}|}S(\mathbf{\hat{x}}^{j}(\boldsymbol{\theta}^{t}))^{T}\cdot\underbrace{\textbf{vec}(\mathbf{\hat{x}}^{j}(\boldsymbol{\theta}^{t})\ominus\mathbf{x}_{GT})}_{\in\mathbb{R}^{TD}}+2\lambda\boldsymbol{\theta}^{t}$
(13)

where $\mathbf{vec}$ is the vectorization operator and
$S(\boldsymbol{\hat{x}}(\boldsymbol{\theta}^{t}))\in\mathbb{R}^{TD\times m}$
is a matrix such that each row $r$ is equal to:

$\displaystyle
S(\mathbf{\hat{x}}^{j}(\boldsymbol{\theta}^{t}))_{r}=\textbf{vec}\left(\frac{\partial\mathbf{\hat{x}}^{j}}{\partial\theta_{ij}}\right)$
$\displaystyle\quad\quad\quad\quad\;\;=\lim\limits_{\tau_{ij}\rightarrow
0}\frac{\textbf{vec}(\text{Log}(\mathbf{\hat{x}}^{j}(\tilde{\boldsymbol{\theta}}^{t})\circ\mathbf{\hat{x}}^{j}(\boldsymbol{\theta}^{t})^{-1}))}{\tau_{ij}}$
(14)

where $\tilde{\theta}^{t}_{ij}=\theta^{t}_{ij}+\tau_{ij}$ and
$\tilde{\boldsymbol{\theta}}^{t}=\boldsymbol{\theta}^{t}$ otherwise. By the
implicit function theorem, the gradient
$\frac{\partial\mathbf{\hat{x}}}{\partial\theta_{ij}}$ exists and is estimated
in eq. 14 using finite differencing by perturbing the parameter $\theta_{ij}$
by $\mathbf{\tau}_{ij}$ . Parameters are then updated using gradient descent
with learning rate $\alpha$:

$\displaystyle\boldsymbol{\theta}^{t+1}=\boldsymbol{\theta}^{t}-\alpha\cdot\frac{\partial\mathcal{L}}{\partial\boldsymbol{\theta}}$
(15)

##  4 Results

Table I: Comparison between LEO and Ours (final training runtime and error,
test error statistics).

| LEO ($D_{1}$) | Ours ($D_{1}$) | LEO ($D_{2}$) | Ours ($D_{2}$)
---|---|---|---|---
Num training iterations | 100 | 100 | 100 | 100
Parallelization enabled during training | yes | no | yes | no
Time per training iteration (min) | 2.863 | $\mathbf{0.025}$ | $3.773$ | $\mathbf{0.022}$
Num of training trajectories | 5 | 5 | 5 | 5
Length of training trajectories | 300 | 100 | 300 | 100
Avg training RMS translation error (m) | 0.385 | 0.236 | 1.179 | 0.730
Avg training RMS rotation Avg error (rad) | 0.087 | 0.062 | 0.467 | 0.051
Num test trajectories | 20 | 20 | 20 | 20
Length of test trajectories | 300 | 300 | 300 | 300
Avg test RMS translation error (m) | 0.384 | 0.238 | 1.153 | 0.733
Avg test RMS rotation error (rad) | 0.067 | 0.063 | 0.463 | 0.050

We use two synthetic planar (i.e. in $SE(2)$) robotic navigation datasets
$\textit{D}_{1}$ and $\textit{D}_{2}$ consisting of GPS and odometric
measurements. Each dataset uses a different set of parameters
$\\{\theta_{\text{GPS}},\theta_{\text{odom}}\\}_{\textit{D}_{i}}$ to generate
$N$ trajectories (more details in appendix A.1). We use 5 training ground
truth trajectories of length111Length refers to the number of nodes in the
graph optimizer 300 to train LEO222We use the official implementation of LEO
by Paloma et al. and 5 training trajectories of length 100 to train our
method. We use a set of 20 unseen trajectories (all of length 300) to test the
tracking performance given our final learned parameters (the testing set is
fixed for both methods). For LEO, we enable multithreaded parallel trajectory
sampling while do not use any form of parallelization with our technique.

At each training iteration, iSAM2 optimizes the inner loop (eq. 3) objective
for both methods:

$\displaystyle\mathbf{\hat{x}}\\!=\\!\operatorname*{arg\,min}_{\mathbf{x}}H(\boldsymbol{\theta},\mathbf{x};\mathbf{z})\\!=\\!\operatorname*{arg\,min}_{\mathbf{x}}\\!\frac{1}{2}\\!\sum_{i}\biggl{(}\\!||g^{\text{gps}}(x_{i})\\!-\\!z_{i}^{\text{gps}}||_{\theta_{\text{gps}}}^{2}$
$\displaystyle\quad\quad\quad\quad\quad+\frac{1}{2}||g^{\text{odom}}(x_{i-1},x_{i})-z_{i-1,i}^{\text{odom}}||_{\theta_{\text{odom}}}^{2}\biggr{)}$
(16)

Our method then updates the parameters $\boldsymbol{\theta}$ using eq.15 while
LEO minimizes the following energy-based loss:

$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\mathcal{L}(\theta)\\!=\\!\frac{1}{|\mathcal{D}|}\\!\sum_{(\mathbf{x}_{\text{gt}}^{j},\mathbf{z}^{j})\in\mathcal{D}}\\!\\!\\!\\!\\!E(\boldsymbol{\theta},\mathbf{x}_{\text{gt}}^{j};\mathbf{z}^{j})\\!+\\!\log\\!\int_{\mathbf{x}}e^{-E(\boldsymbol{\theta},\mathbf{x};\mathbf{z}^{j})}d\mathbf{x}$
(17)

where $(\mathbf{x}_{\text{gt}}^{j},\mathbf{z}^{j})$ is a ground truth sample
from the training set $\mathcal{D}$, the energy
$E(\boldsymbol{\theta},\mathbf{x};\mathbf{z}):=H(\boldsymbol{\theta},\mathbf{x};\mathbf{z})$,
and the integral is over the space of trajectories. Fig. 2 shows the training
time and root mean squared error (RMSE) at each iteration. Fig. 3 shows the
RMSE on the test set, and table I gives a summary of the results. We note that
our method converges to parameters that lead to better tracking accuracy on
all unseen test trajectories. In addition, while LEO needs to generate samples
from a high dimensional probability distribution during training which is a
time consuming process, our method generates gradients by directly comparing
deviation from the training trajectories leading to order-of-magnitude faster
training time. We additionally analyze the performance of both methods as a
function of the training set size and provide the results in appendix A.2.

##  5 Conclusion and Future Work

We presented a gradient-based learning algorithm which estimates observation
models with non-differentiable optimizers (iSAM2) in the loop for robotic
state estimation. While current state of the art algorithms require sampling
trajectories from the posterior distribution to bypass the non-
differentiability of the optimizer, our technique learns parameters by
formulating the problem as a bilevel optimization procedure where gradients
are generated through numerical differentiation.

For future work, we want to extend our algorithm to learn parameters
$\\{\theta_{i}\\}$, with iSAM2 in the loop, that are themselves functions of
observations i.e. $\theta_{i}(z_{i},\phi_{i})$ where $\phi_{i}$ can, for
example, be the weights of a jointly trained neural network. Indeed, the
outputs of the network can be perturbed to approximate
$\frac{\partial\mathbf{\hat{x}}}{\partial\theta_{i}}$ as proposed in this work
and then simply chained with the gradient
$\frac{\partial\theta_{i}}{\partial\phi}$ (obtainable from existing auto-
differentiation packages such as PyTorch) to get the gradient of the optimized
output trajectory with respect to network weights. We plan to compare the
sample efficiency, training time, and generalization performance of our method
against different baselines. Finally, we plan to train our algorithm on real
robotics data and deploy our state estimator on real robotics platforms.

## References

  * Agrawal et al. (2019) Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S., and Kolter, J. Z.  Differentiable convex optimization layers.  _Advances in neural information processing systems_ , 32, 2019.
  * Amos & Kolter (2017) Amos, B. and Kolter, J. Z.  Optnet: Differentiable optimization as a layer in neural networks.  In _International Conference on Machine Learning_ , pp. 136–145. PMLR, 2017.
  * Amos & Yarats (2020) Amos, B. and Yarats, D.  The differentiable cross-entropy method.  In _International Conference on Machine Learning_ , pp. 291–302. PMLR, 2020.
  * Bechtle et al. (2021) Bechtle, S., Molchanov, A., Chebotar, Y., Grefenstette, E., Righetti, L., Sukhatme, G., and Meier, F.  Meta learning via learned loss.  In _2020 25th International Conference on Pattern Recognition (ICPR)_ , pp. 4161–4168. IEEE, 2021.
  * Czarnowski et al. (2020) Czarnowski, J., Laidlow, T., Clark, R., and Davison, A. J.  Deepfactors: Real-time probabilistic dense monocular slam.  _IEEE Robotics and Automation Letters_ , 5(2):721–728, 2020.
  * Dontchev et al. (2009) Dontchev, A. L., Rockafellar, R. T., and Rockafellar, R. T.  _Implicit functions and solution mappings: A view from variational analysis_ , volume 11.  Springer, 2009.
  * Engel et al. (2014) Engel, J., Schöps, T., and Cremers, D.  Lsd-slam: Large-scale direct monocular slam.  In _Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part II 13_ , pp. 834–849. Springer, 2014.
  * Haarnoja et al. (2016) Haarnoja, T., Ajay, A., Levine, S., and Abbeel, P.  Backprop kf: Learning discriminative deterministic state estimators.  _Advances in neural information processing systems_ , 29, 2016.
  * Julier & Uhlmann (2004) Julier, S. J. and Uhlmann, J. K.  Unscented filtering and nonlinear estimation.  _Proceedings of the IEEE_ , 92(3):401–422, 2004\.
  * Kaess et al. (2011) Kaess, M., Ila, V., Roberts, R., and Dellaert, F.  The bayes tree: An algorithmic foundation for probabilistic robot mapping.  In _Algorithmic Foundations of Robotics IX: Selected Contributions of the Ninth International Workshop on the Algorithmic Foundations of Robotics_ , pp. 157–173. Springer, 2011.
  * Kaess et al. (2012) Kaess, M., Johannsson, H., Roberts, R., Ila, V., Leonard, J. J., and Dellaert, F.  isam2: Incremental smoothing and mapping using the bayes tree.  _The International Journal of Robotics Research_ , 31(2):216–235, 2012.
  * Kloss et al. (2021) Kloss, A., Martius, G., and Bohg, J.  How to train your differentiable filter.  _Autonomous Robots_ , 45(4):561–578, 2021.
  * Krishna Murthy et al. (2020) Krishna Murthy, J., Saryazdi, S., Iyer, G., and Paull, L.  gradslam: Dense slam meets automatic differentiation.  In _arXiv_ , 2020.
  * Lambert et al. (2019) Lambert, A. S., Mukadam, M., Sundaralingam, B., Ratliff, N., Boots, B., and Fox, D.  Joint inference of kinematic and force trajectories with visuo-tactile sensing.  In _2019 International Conference on Robotics and Automation (ICRA)_ , pp. 3165–3171. IEEE, 2019.
  * Qadri et al. (2022) Qadri, M., Sodhi, P., Mangelson, J. G., Dellaert, F., and Kaess, M.  Incopt: Incremental constrained optimization using the bayes tree.  In _2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pp. 6381–6388, 2022.  doi: 10.1109/IROS47612.2022.9982178.
  * Sodhi et al. (2021) Sodhi, P., Kaess, M., Mukadam, M., and Anderson, S.  Learning tactile models for factor graph-based estimation.  In _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , pp. 13686–13692. IEEE, 2021.
  * Sodhi et al. (2022) Sodhi, P., Dexheimer, E., Mukadam, M., Anderson, S., and Kaess, M.  Leo: Learning energy-based models in factor graph optimization.  In _Conference on Robot Learning_ , pp. 234–244. PMLR, 2022.
  * Sola et al. (2018) Sola, J., Deray, J., and Atchuthan, D.  A micro lie theory for state estimation in robotics.  _arXiv preprint arXiv:1812.01537_ , 2018.
  * Sun et al. (2016) Sun, W., Venkatraman, A., Boots, B., and Bagnell, J. A.  Learning to filter with predictive state inference machines.  In _International conference on machine learning_ , pp. 1197–1205. PMLR, 2016.
  * Sundaralingam et al. (2019) Sundaralingam, B., Lambert, A. S., Handa, A., Boots, B., Hermans, T., Birchfield, S., Ratliff, N., and Fox, D.  Robust learning of tactile force estimation through robot interaction.  In _2019 International Conference on Robotics and Automation (ICRA)_ , pp. 9035–9042. IEEE, 2019.
  * Thrun et al. (2001) Thrun, S., Fox, D., Burgard, W., and Dellaert, F.  Robust monte carlo localization for mobile robots.  _Artificial intelligence_ , 128(1-2):99–141, 2001\.
  * Yi et al. (2021) Yi, B., Lee, M. A., Kloss, A., Martín-Martín, R., and Bohg, J.  Differentiable factor graph optimization for learning smoothers.  In _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pp. 1339–1345. IEEE, 2021.

##  Appendix A Appendix

###  A.1 Additional Details on Experimental Setup

Figure 4: The factor graph used to generate the synthetic robot navigation
trajectories.

Figure 4 shows the structure of the factor graph used to generate the
synthetic robot navigation trajectories. A unary GPS factor
$g^{\text{gps}}(x_{i})$ is added to each pose $x_{i}$ while a binary odometry
factor $g^{\text{gps}}(x_{i},x_{i-1})$ is specified between poses. To simulate
realistic robot navigation trajectories for each of datasets $D_{1}$ and
$D_{2}$, Gaussian noise $\sim\mathcal{N}(0,\theta_{\text{odom}})$ is injected
to ground truth relative odometry measurements while Gaussian noise
$\sim\mathcal{N}(0,\theta_{\text{gps}})$ is added to absolute ground truth GPS
measurements.

###  A.2 Additional Experiments

We analyze our method and LEO as a function of the training set size. Tables
II and III show the average training and testing RMS errors on datasets
$D_{1}$ and $D_{2}$ respectively. We note that our method possesses a much
faster training time as well as learns parameters that generalize better to
unseen test trajectories regardless of the training set size.

Table II: Dataset $D_{1}$ \- Comparison between LEO and Ours (final training
runtime and error, test error statistics).

Num trajectory in training set | 1 | 5 | 10 | 20 | 30
---|---|---|---|---|---
Algorithm | LEO | Ours | LEO | Ours | LEO | Ours | LEO | Ours | LEO | Ours
Num training iterations | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100
Parallelization enabled during training | yes | no | yes | no | $\text{yes}^{*}$ | no | $\text{yes}^{*}$ | no | $\text{yes}^{*}$ | no
Time per training iteration (min) | 0.937 | $\mathbf{0.005}$ | $2.863$ | 0.025 | 4.370 | 0.045 | 4.899 | 0.091 | 7.56 | 0.136
Average training RMS translation error (m) | 0.379 | 0.257 | 0.385 | 0.236 | 0.383 | 0.243 | 0.386 | 0.243 | 0.385 | 0.236
Average training RMS rotation Avg error (rad) | 0.071 | 0.060 | 0.087 | 0.062 | 0.076 | 0.063 | 0.079 | 0.068 | 0.079 | 0.064
Num test trajectories | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20
Length of test trajectories | 300 | 300 | 300 | 300 | 300 | 300 | 300 | 300 | 300 | 300
Average test RMS translation error (m) | 0.385 | 0.237 | 0.384 | 0.238 | 0.385 | 0.238 | 0.384 | 0.240 | 0.384 | 0.235
Average test RMS rotation error (rad) | 0.067 | 0.059 | 0.067 | 0.063 | 0.067 | 0.063 | 0.067 | 0.069 | 0.067 | 0.066

Table III: Dataset $D_{2}$ \- Comparison between LEO and Ours (final training
runtime and error, test error statistics).

Num trajectory in training set | 1 | 5 | 10 | 20 | 30
---|---|---|---|---|---
Algorithm | LEO | Ours | LEO | Ours | LEO | Ours | LEO | Ours | LEO | Ours
Num training iterations | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100 | 100
Parallelization enabled during training | yes | no | yes | no | $\text{yes}^{*}$ | no | $\text{yes}^{*}$ | no | $\text{yes}^{*}$ | no
Time per training iteration (min) | 0.934 | 0.004 | 3.773 | 0.022 | 4.403 | 0.038 | 4.901 | 0.075 | 6.96 | 0.113
Average training RMS translation error (m) | 1.129 | 0.715 | 1.179 | 0.730 | 1.090 | 0.731 | 1.057 | 0.718 | 1.104 | 0.761
Average training RMS rotation Avg error (rad) | 0.443 | 0.056 | 0.467 | 0.051 | 0.421 | 0.055 | 0.407 | 0.056 | 0.429 | 0.045
Num test trajectories | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20
Length of test trajectories | 300 | 300 | 300 | 300 | 300 | 300 | 300 | 300 | 300 | 300
Average test RMS translation error (m) | 1.132 | 0.728 | 1.153 | 0.733 | 1.583 | 0.735 | 1.043 | 0.734 | 1.093 | 0.771
Average test RMS rotation error (rad) | 0.447 | 0.051 | 0.468 | 0.050 | 0.419 | 0.055 | 0.402 | 0.056 | 0.427 | 0.045

For LEO, we faced compute memory problems on larger training sets (indicated
by an asterix in tables II and III) which required us to decrease the number
of threads and samples (needed to compute the loss in eq. 17). The values of
the hyperparameters used per training set size are specified in table IIII.

Table IIII: Hyperparameters used to train LEO per training set size

Num trajectory in training set | 1 | 5 | 10 | 20 | 30
---|---|---|---|---|---
Number of threads | 4 | 4 | 3 | 2 | 2
Number of samples generated per training trajectory per iteration | 10 | 10 | 8 | 4 | 4