# The amoeba dimension of a linear space

Jan Draisma  Mathematical Institute, University of Bern, Sidlerstrasse 5, 3012
Bern, Switzerland; and Department of Mathematics and Computer Science,
Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The
Netherlands<EMAIL_ADDRESS>,  Sarah Eggleston  Institut für Mathematik,
Albrechtstraße 28a, 49076 Osnabrück, Germany  sarah.eggleston@uni-
osnabrueck.de ,  Rudi Pendavingh  Department of Mathmematics and Computer
Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven,
The Netherlands<EMAIL_ADDRESS>,  Johannes Rau  Departamento de
Matemáticas, Universidad de los Andes, Carrera 1 # 18A - 12, 111711 Bogotá,
Colombia<EMAIL_ADDRESS>and  Chi Ho Yuen  Department of Mathematical
Sciences, University of Copenhagen, Universitetsparken 5, 2100 Copenhagen,
Denmark<EMAIL_ADDRESS>
###### Abstract.

Given a complex vector subspace $V$ of $\mathbb{C}^{n}$, the dimension of the
amoeba of $V\cap(\mathbb{C}^{*})^{n}$ depends only on the matroid that $V$
defines on the ground set $\\{1,\ldots,n\\}$. Here we prove that this
dimension is given by the minimum of a certain function over all partitions of
the ground set, as previously conjectured by Rau. We also prove that this
formula can be evaluated in polynomial time.

JD was partially supported by Swiss National Science Foundation (SNSF) project
grant 200021_191981 and by Vici grant 639.033.514 from the Netherlands
Organisation for Scientific Research (NWO). JR was supported by the FAPA
project “Matroids in tropical geometry” from the Facultad de Ciencias,
Universidad de los Andes, Colombia. CHY was supported by the Trond Mohn
Foundation project “Algebraic and Topological Cycles in Complex and Tropical
Geometries”; he also acknowledges the support of the Centre for Advanced Study
(CAS) in Oslo, Norway, which funded and hosted the Young CAS research project
“Real Structures in Discrete, Algebraic, Symplectic, and Tropical Geometries”
during the 2021/2022 and 2022/2023 academic years

##  1\. Introduction

###  1.1. The goal

Let $V\subseteq{\mathbb{C}}^{n}$ be a complex vector subspace, and set
$X:=V\cap({\mathbb{C}}^{*})^{n}$. We assume throughout that $X\neq\emptyset$,
i.e., that $V$ is not contained in any coordinate hyperplane. We denote by
$\mathcal{A}(X)\subseteq{\mathbb{R}}^{n}$ the amoeba of $X$, defined as the
image $\operatorname{Log}(X)$ of $X$ under the map

$\operatorname{Log}:({\mathbb{C}}^{*})^{n}\to{\mathbb{R}}^{n},\
z=(z_{1},\ldots,z_{n})\mapsto(\log(|z_{1}|),\ldots,\log(|z_{n}|)).$

An open dense subset of $\mathcal{A}(X)$ (in the Euclidean topology) is a real
manifold, and we write $\dim_{\mathbb{R}}\mathcal{A}(X)$ for the dimension of
this manifold. We will derive a purely combinatorial expression for
$\dim_{\mathbb{R}}\mathcal{A}(X)$. This expression depends only on the matroid
$M_{V}$ that $V$ defines on the ground set $[n]:=\\{1,\ldots,n\\}$ (see
below), and in fact makes sense for any matroid $M$ on that ground set, not
just those represented by some complex vector space. Furthermore, we derive an
algorithm for computing the said expression that uses a polynomial number of
rank evaluations in $M$. In particular, if $V$ is given as the row space of an
input matrix with, for example, entries in the field ${\mathbb{Q}}(i)$ of
Gaussian rationals, then $\dim_{\mathbb{R}}\mathcal{A}(X)$ can be computed in
polynomial time in the bit-length of the input.

###  1.2. The matroid of $V$

For $S\subseteq[n]$ we denote by $r_{V}(S)$ the dimension of the image of $V$
under the projection ${\mathbb{C}}^{n}\to{\mathbb{C}}^{S}$. More explicitly,
if $d:=\dim_{\mathbb{C}}V$ and $V$ is presented as the row space of a $d\times
n$-matrix $A$, then $r_{V}(S)$ is the dimension of the span of the columns of
$A$ labelled by $S$. This is the rank function of the matroid $M_{V}$ defined
by $V$. The assumption that $X\neq\emptyset$ is equivalent to the condition
that $M_{V}$ has no loops, and to the condition that $A$ has no zero column.

###  1.3. Main results

We will prove the following formula, first conjectured by Rau [Rau20].
Throughout the paper, a partition of a finite set $S$ is a set of pairwise
disjoint, nonempty subsets of $S$, called the parts of the partition, whose
union is $S$.

######  Theorem 1.3.1.

We have

(1) $\dim_{\mathbb{R}}\mathcal{A}(X)=\min\sum_{i=1}^{k}(2\,r_{V}(P_{i})-1),$

where the minimum is over all partitions $\\{P_{1},\ldots,P_{k}\\}$ of $[n]$.

######  Example 1.

The two obvious upper bounds $2d-1$ (see Lemma 2.1.1) and $n$ (the dimension
of the ambient space) can be recovered by choosing the trivial partition and
the partition into singletons, respectively. More generally, if the matroid
has connected components $M_{1},\ldots,M_{k}$, then choosing the partition
consisting of their respective ground sets shows that
$\dim_{\mathbb{R}}\mathcal{A}(X)\leq 2d-k$.

The following example, due to Mounir Nisse, shows that the
$\dim_{\mathbb{R}}\mathcal{A}(X)$ can drop below $\min\\{n,2d-1\\}$ even if
$M_{V}$ is connected.

######  Example 2.

Consider the $4\times 7$ matrix

$\begin{pmatrix}1&0&0&0&*&*&*\\\ 0&1&0&0&*&*&*\\\ 0&0&1&0&0&0&*\\\
0&0&0&1&0&0&*\end{pmatrix},$

where the stars represent any sufficiently general tuple of complex numbers.
The matroid represented by such a matrix is connected. However, the partition
of columns $\\{1,2,5,6\\},\\{3\\},\\{4\\},\\{7\\}$ yields
$\dim_{\mathbb{R}}\mathcal{A}(X)\leq(2\cdot 2-1)+3\cdot(2\cdot
1-1)=6<\min\\{7,2\cdot 4-1\\}$.

The next result interprets the expression in the theorem as the rank of a
matroid. To this end, let $M$ be a loopless matroid on the finite set $E$,
with rank function $r:2^{E}\rightarrow\mathbb{N}$. For subsets
$S_{1},\ldots,S_{k}\subseteq E$, put

$\tilde{r}(S_{1},\ldots S_{k}):=\sum_{i=1}^{k}(2r(S_{i})-1)$

and define the function $r^{\prime}:2^{E}\rightarrow\mathbb{N}$ as

(2) $r^{\prime}(S):=\min\tilde{r}(P_{1},\ldots,P_{k})$

where the minimum is over all partitions $\\{P_{1},\ldots,P_{k}\\}$ of $S$.

######  Theorem 1.3.2.

Let $M$ be a loopless matroid on $E$ with rank function $r$, and let
$r^{\prime}$ be defined as in (2). Then $r^{\prime}$ is the rank function of a
matroid $M^{\prime}$ on $E$.

Moreover, we will establish the following algorithmic result.

######  Theorem 1.3.3.

The rank function $r^{\prime}$ of $M^{\prime}$ can be evaluated on an input
set $S\subseteq E$ by a polynomial number of rank evaluations in $M$.

######  Corollary 1.3.4.

There exists an algorithm that, on input of a $d\times n$-matrix $A$ with
entries in ${\mathbb{Q}}(i)$ and with no zero column, computes the amoeba
dimension of $V\cap({\mathbb{C}}^{*})^{n}$, where $V$ is the complex row space
of $A$, in polynomial time in the bit-length of $A$.

###### Proof.

This is a direct consequence of Theorems 1.3.1 and 1.3.3, plus the fact that
the rank of the submatrix $A[S]$, obtained from $A$ by picking the columns
labelled by any subset $S\subseteq[n]$, can be computed in polynomial time in
the bit-length of $A$. ∎

###  1.4. A matroid conjecture

From [DRY20], we know that, for any irreducible subvariety $X$ of
$({\mathbb{C}}^{*})^{n}$, $\dim_{\mathbb{R}}\mathcal{A}(X)$ depends only on
the tropicalisation or Bergman fan $\operatorname{Trop}(X):=\lim_{t\to
0}t\cdot\mathcal{A}(X)$ of $X$ [Ber71]. In our current setting, where $X$ is
the intersection with $({\mathbb{C}}^{*})^{n}$ of a linear space
$V\subseteq{\mathbb{C}}^{n}$, $\operatorname{Trop}(X)$ is the support
$\Sigma(M_{V})$ of the _matroid fan_ of $M_{V}$ [Stu02], so it was already
known that the amoeba dimension of $X$ depends only on $M_{V}$. However, this
dependence via [DRY20] is rather implicit and not quite sufficient for
algorithmic computation: it states that
$\dim_{\mathbb{R}}\mathcal{A}(X)=\operatorname{adim}(M_{V})$ with

(3)
$\operatorname{adim}(M):=\min\\{2\dim_{\mathbb{R}}(\Sigma(M)+R)-\dim_{\mathbb{R}}(R)\mid
R\subseteq{\mathbb{R}}^{E}\text{ rational subspace}\\}.$

Here a rational subspace of ${\mathbb{R}}^{E}$ is a real subspace spanned by
its intersection with ${\mathbb{Q}}^{E}$, and $\Sigma(M)+R$ is the Minkowski
sum of the $r(E)$-dimensional polyhedral fan $\Sigma(M)$ and the linear space
$R$. The formula in Theorem 1.3.1 was inspired by the following conjecture.

######  Conjecture 1.4.1.

Let $M$ be a loopless matroid on $E$ and let
$\Sigma(M)\subseteq{\mathbb{R}}^{E}$ be the matroid fan of $M$. Then the
minimum in (3) is attained by some space $R$ in the braid arrangement, that
is, an intersection of a number of hyperplanes of the form $x_{i}=x_{j}$ with
distinct $i,j\in E$.

To make the connection with Theorem 1.3.1, consider the subspace $R$ for which
$x_{i}=x_{j}$ whenever $i$ and $j$ lie in the same part of the partition
$\\{P_{1},\ldots,P_{k}\\}$. It is then easy to check that
$\tilde{r}(P_{1},\ldots,P_{k})=2\dim_{\mathbb{R}}(\Sigma(M)+R)-\dim_{\mathbb{R}}(R)$.
Hence clearly $r^{\prime}(E)\geq\operatorname{adim}(M)$, and Conjecture 1.4.1
is in fact equivalent to the equality $r^{\prime}(E)=\operatorname{adim}(M)$.

In particular, if $M$ is the loopless matroid of a linear space
$V\subseteq{\mathbb{C}}^{n}$, then Conjecture 1.4.1 follows from Theorem 1.3.1
and the formula for the amoeba dimension from [DRY20]. It would be very
interesting to have a direct proof of Conjecture 1.4.1 that works also for
non-representable matroids.

In any case, an important benefit of Theorem 1.3.1 over the formula
$\dim_{\mathbb{R}}\mathcal{A}(X)=\operatorname{adim}(M_{V})$ is that Theorem
1.3.1 allows for efficient computation of $\dim_{\mathbb{R}}\mathcal{A}(X)$.

###  1.5. Amoeba dimensions and algebraic matroids

Let $K$ be an infinite field. Any irreducible variety $X\subseteq(K^{*})^{n}$
defines an algebraic matroid $M_{X}$ on $[n]$ by declaring $S\subseteq[n]$ to
be independent if the projection from $X$ to $({\mathbb{C}}^{*})^{S}$ is
dominant (this is equivalent to the functions $\\{x_{i}:i\in S\\}$, regarded
as polynomial functions on $X$, being algebraically independent over $K$). If
$K=\mathbb{R}$ and $A\subset(\mathbb{R}^{*})^{n}$ is an irreducible semi-
algebraic set, we define the matroid of $A$ as the matroid of its Zariski
closure $\overline{A}\subset(\mathbb{R}^{*})^{n}$, that is,
$M_{A}:=M_{\overline{A}}$. Note that, for example by the decomposition theorem
for semi-algebraic sets, $\overline{A}=(\mathbb{R}^{*})^{n}$ if and only if
$A$ contains a nonempty Euclidean-open subset. It follows easily that
$S\subseteq[n]$ is independent in $M_{A}$ if and only if the projection of $A$
to ${\mathbb{R}}^{S}$ contains a nonempty Euclidean-open subset of
${\mathbb{R}}^{S}$.

######  Proposition 1.5.1.

Let $X\subset(\mathbb{C}^{*})^{n}$ be an irreducible variety. The amoeba
$\mathcal{A}(X)$ defines a matroid $M_{\mathcal{A}(X)}$, by declaring
$S\subseteq[n]$ to be independent if the projection of $\mathcal{A}(X)$ to
${\mathbb{R}}^{S}$ contains a nonempty Euclidean-open subset of
${\mathbb{R}}^{S}$.

###### Proof.

We consider the “squared algebraic amoeba”
$\mathcal{A}^{\prime}(X)\subset(\mathbb{R}_{>0})^{n}$ defined as the image of
$X$ under the map $|.|^{2}\colon(\mathbb{C}^{*})^{n}\to(\mathbb{R}_{>0})^{n}$,
$(z_{i})_{i}\mapsto(|z_{i}|^{2})_{i}$. Since $X$ is irreducible and
${\mathbb{C}}/{\mathbb{R}}$ is a finite separable extension, $X$ is also
irreducible with respect to the real Zariski topology of
$(\mathbb{C}^{*})^{n}$. Since $|.|^{2}$ is a real regular map, it follows that
$\mathcal{A}^{\prime}(X)$ is an irreducible semi-algebraic set with associated
(algebraic) matroid $M_{\mathcal{A}^{\prime}(X)}$. Taking square roots and
logarithm provides a diffeomorphism $(\mathbb{R}_{>0})^{n}\to\mathbb{R}^{n}$
sending $\mathcal{A}^{\prime}(X)$ to $\mathcal{A}(X)$, and this diffeomorphism
is compatible with projections in the obvious sense. Hence
$M_{\mathcal{A}(X)}$ as defined in the statement is equal to
$M_{\mathcal{A}^{\prime}(X)}$, which proves the claim. ∎

######  Proposition 1.5.2.

If $X=V\cap({\mathbb{C}}^{*})^{n}$ where $V\subseteq{\mathbb{C}}^{n}$ is a
linear space not contained in any coordinate hyperplane, then the matroid
$M_{\mathcal{A}(X)}$ is the matroid from Theorem 1.3.2 with the rank function
$r^{\prime}$ constructed from $M:=M_{X}=M_{V}$. In particular, $r^{\prime}$
defines an algebraic matroid.

###### Proof.

Let $S$ be a subset of $[n]$ and let $X_{S}$ be the projection of $X$ into
$({\mathbb{C}}^{*})^{S}$. Then $S$ is independent in $M_{\mathcal{A}(X)}$ if
and only if $\dim\mathcal{A}(X_{S})=|S|$, which by Theorem 1.3.1 applied to
$X_{S}$ is equivalent to the condition that $r^{\prime}(S)=|S|$. ∎

We note that the proof above only uses Theorem 1.3.1 and not Theorem 1.3.2.
Hence when $M=M_{V}$ is a matroid representable over ${\mathbb{C}}$, Theorem
1.3.1 and the two propositions above imply Theorem 1.3.2.

Given that, for $X$ arising from a linear space, $M_{\mathcal{A}(X)}$ has such
a nice description in terms of $M_{X}$, one might wonder whether the same
holds for general irreducible varieties $X$. In particular, one could ask
whether the amoeba dimension of $X$ is also determined by $M_{X}$, for
instance via the formula from Theorem 1.3.1.

The answer, however, is no in general. For an extreme counterexample, let $X$
be a $d$-dimensional subtorus of $({\mathbb{C}}^{*})^{n}$ such that $M_{X}$ is
the uniform matroid $U_{d,n}$ of rank $d$ on $[n]$—this is achieved by
choosing the subtorus $X$ whose Lie algebra, i.e., tangent space at
$(1,\ldots,1)$, is the ${\mathbb{C}}$-span $\langle R\rangle_{\mathbb{C}}$ of
any rational subspace $R$ of ${\mathbb{Q}}^{n}$ that represents the matroid
$U_{d,n}$. Since $X$ is a subtorus, its amoeba is a linear space, namely, the
real span $\langle R\rangle_{\mathbb{R}}$. Hence
$\dim_{\mathbb{R}}\mathcal{A}(X)$ is $d$, which is the minimum among all
amoeba dimensions of $d$-dimensional varieties (actually, this minimum is
attained only for translates of subtori; see [NS22, Theorem 4.6]). On the
other hand, the tangent space $V$ to $X$ at any point $p\in X$ equals
$p\cdot\langle R\rangle_{\mathbb{C}}$ (the Hadamard product) and hence also
represents the matroid $U_{d,n}$. Therefore
$\dim_{\mathbb{R}}\mathcal{A}(V\cap({\mathbb{C}}^{*})^{n})=\min\\{n,2d-1\\}$,
as is easily seen with the formula in Theorem 1.3.1.

###  1.6. Organisation of this paper

In Section 2, we prove Theorem 1.3.1, in Section 3 we prove Theorem 1.3.2, and
in Section 4 we derive the algorithm in Theorem 1.3.3.

### Acknowledgments

This paper grew out of several sources: JR’s talk on amoebas [Rau20] where the
formula of Theorem 1.3.1 was first conjectured, SE’s Master’s thesis [Egg22]
at the University of Bern under the supervision of JD, work by CHY on a
combinatorial analysis of the Jacobian of $\operatorname{Log}$ at a general
point of a linear space, and RP’s work on the matroid $M^{\prime}$ of Theorems
1.3.2 and 1.3.3. CHY thanks Kris Shaw for suggesting this problem to him. All
authors thank Frank Sottile for discussions on an early version of this work.

##  2\. Proof of Theorem 1.3.1

###  2.1. Proof of the inequality $\leq$ in (1)

As mentioned in §1.4, the inequality $\leq$ in (1) is a consequence of [DRY20]
via $\dim_{\mathbb{R}}\mathcal{A}(X)=\operatorname{adim}(M_{V})\leq
r^{\prime}(E)$. Nevertheless, we include a short proof which also serves as
preparation for later arguments.

Recall from [DRY20] that if a closed subvariety $X$ of
$({\mathbb{C}}^{*})^{n}$ is stable under a subtorus $T$ of
$({\mathbb{C}}^{*})^{n}$, and if we set
$Y:=X/T\subseteq({\mathbb{C}}^{*})^{n}/T\cong({\mathbb{C}}^{*})^{m}$ with
$m=n-\dim_{\mathbb{C}}(T)$, then we have a surjective map
$\mathcal{A}(X)\to\mathcal{A}(Y)$ whose fibres are translates of
$\mathcal{A}(T)$. It then follows that

$\dim_{\mathbb{R}}\mathcal{A}(X)=\dim_{\mathbb{R}}\mathcal{A}(Y)+\dim_{\mathbb{R}}\mathcal{A}(T)=\dim_{\mathbb{R}}\mathcal{A}(Y)+\dim_{\mathbb{C}}T.$

######  Lemma 2.1.1.

Let $X=V\cap({\mathbb{C}}^{*})^{n}$ where $V$ is a $d$-dimensional complex
subspace of ${\mathbb{C}}^{n}$ not contained in any coordinate hyperplane.
Then $\dim_{\mathbb{R}}\mathcal{A}(X)\leq 2d-1$.

###### Proof.

Since $V$ is closed under scalar multiplication, $X$ is stable under the one-
dimensional torus $T=\\{(t,\ldots,t)\mid t\in{\mathbb{C}}^{*}\\}$. Then
$Y:=X/T$ has dimension $d-1$, and hence
$\dim_{\mathbb{R}}\mathcal{A}(Y)\leq\dim_{\mathbb{C}}Y=2(d-1)$. It therefore
follows from the above that

$\dim_{\mathbb{R}}\mathcal{A}(X)=\dim_{\mathbb{R}}\mathcal{A}(Y)+\dim_{\mathbb{C}}T\leq
2(d-1)+1=2d-1,$

as desired. ∎

######  Proposition 2.1.2.

In Theorem 1.3.1, the inequality $\leq$ holds.

###### Proof.

Let $\\{P_{1},\ldots,P_{k}\\}$ be a partition of $[n]$. Let $V_{i}$ be the
image of $V$ under the projection ${\mathbb{C}}^{n}\to{\mathbb{C}}^{P_{i}}$,
set $d_{i}:=\dim_{\mathbb{C}}V_{i}$, and let $X_{i}$ be the intersection of
$V_{i}$ with $({\mathbb{C}}^{*})^{P_{i}}$. Since $V$ is contained in
$\prod_{i}V_{i}$, $X$ is contained in $X^{\prime}:=\prod_{i}X_{i}$, and hence
also $\mathcal{A}(X)\subseteq\mathcal{A}(X^{\prime})$. Then we find

$\dim_{\mathbb{R}}\mathcal{A}(X)\leq\dim_{\mathbb{R}}\mathcal{A}(X^{\prime})=\sum_{i}\dim_{\mathbb{R}}\mathcal{A}(X_{i})\leq\sum_{i}(2d_{i}-1)$

where the equality follows from the fact that the amoeba of a product is the
product of the amoebas, and where the last inequality follows from Lemma 2.1.1
applied to each $V_{i}$. ∎

###  2.2. Proof of the inequality $\geq$ in (1)

To prove $\geq$ in Theorem 1.3.1, we need to construct a partition for which
equality holds. We will do so in an inductive manner.

By definition, $m:=\dim_{\mathbb{R}}\mathcal{A}(X)$ equals the maximum, over
all $p\in X$, of the real rank of the real linear map
$d_{p}\operatorname{Log}:T_{p}X=V\to{\mathbb{R}}^{n}$, and this maximum is
attained in an open dense subset of $X$ (in the Euclidean topology).

In what follows, for vectors $v,w\in{\mathbb{C}}^{n}$, we write $v\cdot w$ for
their Hadamard product $(v_{1}w_{1},\ldots,v_{n}w_{n})$; and if
$w\in({\mathbb{C}}^{*})^{n}$, then we write $v/w$ for the Hadamard quotient
$(v_{1}/w_{1},\ldots,v_{n}/w_{n})$. We also write
${\mathbf{1}}\in{\mathbb{C}}^{n}$ for the all-one vector $(1,\ldots,1)$.
Furthermore, if $z$ is a complex number or vector of complex numbers, then we
write $\Re(z)$ and $\operatorname{Im}(z)$ for the real and imaginary parts of
parts of $z$, respectively; we also use this notation for a subset of vectors
in ${\mathbb{C}}^{n}$ (e.g., a subspace).

######  Lemma 2.2.1.

For $p\in X$ and $v\in T_{p}X=V$ we have

$(d_{p}\operatorname{Log})(v)=\Re(v/p)=(\Re(v_{1}/p_{1}),\ldots,\Re(v_{n}/p_{n})).$

###### Proof.

Define $w:=v/p$ and decompose $w=x+iy$ with $x,y\in{\mathbb{R}}^{n}$. For
$\epsilon\in{\mathbb{R}}$ tending to $0$ we have

$\operatorname{Log}(p+\epsilon v)=\operatorname{Log}(p({\mathbf{1}}+\epsilon
w))=\operatorname{Log}(p)+\operatorname{Log}({\mathbf{1}}+\epsilon(x+iy))=\operatorname{Log}(p)+\epsilon
x+O(\epsilon^{2}).$

The last equality holds because in each component,

$\displaystyle\log|1+\epsilon(x_{j}+iy_{j})|$
$\displaystyle=\log\left(\sqrt{1+2\epsilon
x_{j}+\epsilon^{2}(x_{j}^{2}+y_{j}^{2})}\right)=\frac{1}{2}\log\left(1+2\epsilon
x_{j}+\epsilon^{2}(x_{j}^{2}+y_{j}^{2})\right)$
$\displaystyle=\frac{1}{2}(2\epsilon
x_{j}+\epsilon^{2}(x_{j}^{2}+y_{j}^{2})-\frac{1}{2}\left(2\epsilon
x_{j}+\epsilon^{2}(x_{j}^{2}+y_{j}^{2})\right)^{2}+\dots)=\epsilon
x_{j}+O(\epsilon^{2}).$

This implies $(d_{p}\operatorname{Log})(v)=x=\Re(v/p)$, as desired. ∎

Pick $p_{0}\in X$ such that the linear map
$A:=d_{p_{0}}\operatorname{Log}:V\to{\mathbb{R}}^{n}$ has the maximal possible
rank $m$. This means that $A$ is a point in the real manifold
$\operatorname{Hom}\nolimits_{\mathbb{R}}(V,{\mathbb{R}}^{n})_{m}$ of real
linear maps $V\to{\mathbb{R}}^{n}$ of rank precisely $m$. We will use the
following description of the tangent space
$T_{A}\operatorname{Hom}\nolimits_{\mathbb{R}}(V,{\mathbb{R}}^{n})_{m}$ (see
e.g. [Har92, Example 14.16]):

(4)
$T_{A}\operatorname{Hom}\nolimits_{\mathbb{R}}(V,{\mathbb{R}}^{n})_{m}=\\{B\in\operatorname{Hom}\nolimits_{\mathbb{R}}(V,{\mathbb{R}}^{n})\mid
B\ker(A)\subseteq\operatorname{im}(A)\\}.$

Now, for a Euclidean-open neighbourhood $U$ of $p_{0}$ in $X$, the map

$\Phi:U\to\operatorname{Hom}\nolimits_{\mathbb{R}}(V,{\mathbb{R}}^{n})_{m},\quad
p\mapsto d_{p}\operatorname{Log}$

is a map of smooth manifolds.

######  Lemma 2.2.2.

The derivative $d_{p_{0}}\Phi$ is the map

$T_{p_{0}}U=V\to
T_{A}\operatorname{Hom}\nolimits_{\mathbb{R}}(V,{\mathbb{R}}^{n})_{m},\quad
u\mapsto(v\mapsto-\Re((v\cdot u)/(p_{0}\cdot p_{0})))$

where
$A=d_{p_{0}}\operatorname{Log}\in\operatorname{Hom}\nolimits_{\mathbb{R}}(V,{\mathbb{R}}^{n})$.

###### Proof.

For $u\in V$ define $w:=u/p_{0}$. Then, for $\epsilon$ real and tending to
zero, and for $v\in V$, by Lemma 2.2.1 we have

$\displaystyle\Phi(p_{0}+\epsilon u)(v)$ $\displaystyle=(d_{p_{0}+\epsilon
u}\operatorname{Log})(v)=\Re(v/(p_{0}+\epsilon
u))=\Re(v/(p_{0}({\mathbf{1}}+\epsilon w)))$
$\displaystyle=\Re((v/p_{0})\cdot({\mathbf{1}}-\epsilon
w))+O(\epsilon^{2})=\Re(v/p_{0})-\epsilon\Re((v\cdot
w)/p_{0})+O(\epsilon^{2}).$

The coefficient of $\epsilon$ is the expression in the lemma. ∎

We simplify the situation as follows: we replace $V$ by $V/p_{0}$, $X$ by
$X/p_{0}$, and $p_{0}$ by ${\mathbf{1}}$. This only translates the amoeba of
$X$, and it has no effect on the matroid $M_{V}$. Consequently, both sides in
(1) are unaltered. In this simplified setting, Lemma 2.2.1 says that

$Av=(d_{\mathbf{1}}\operatorname{Log})(v)=\Re(v).$

In particular,

(5) $\displaystyle m$
$\displaystyle=\dim_{\mathbb{R}}\mathcal{A}(X)=\dim_{\mathbb{R}}V-\dim_{\mathbb{R}}\ker(A)=\dim_{\mathbb{R}}V-\dim_{\mathbb{R}}(V\cap(i{\mathbb{R}}^{n}))$
$\displaystyle=\dim_{\mathbb{R}}V-\dim_{\mathbb{R}}(V\cap{\mathbb{R}}^{n}).$

Furthermore, Lemma 2.2.2 says that $d_{\mathbf{1}}\Phi$ is the linear map that
sends $u$ to the linear map $B_{u}(v):=-\Re(v\cdot u)$. We now come to the
crucial point in the proof.

######  Proposition 2.2.3.

Under the standing assumption that $p={\mathbf{1}}\in V$ is a point where
$d_{p}\operatorname{Log}$ has the maximal rank
$m=\dim_{\mathbb{R}}\mathcal{A}(X)$, the real vector space
$V+{\mathbb{R}}^{n}\subseteq{\mathbb{C}}^{n}$ is closed under Hadamard
multiplication with the real vector space $V\cap{\mathbb{R}}^{n}$.

###### Proof.

For each $u\in V$, the linear map $B_{u}:V\to{\mathbb{R}}^{n}$ lies in the
image of $d_{\mathbf{1}}\Phi$ and hence in
$T_{A}\operatorname{Hom}\nolimits_{\mathbb{R}}(V,{\mathbb{R}}^{n})_{m}$. By
(4), this means that $B_{u}$ maps $\ker(A)$ into $\operatorname{im}(A)$. Since
$A$ maps a vector to its real part, we have $\ker(A)=V\cap(i{\mathbb{R}}^{n})$
and $\operatorname{im}(A)=\Re(V)$. Hence we find that $B_{u}(v)=-\Re(v\cdot
u)$ is in $\Re(V)$ for all $v\in V\cap(i{\mathbb{R}}^{n})$. Then, for $v\in
V\cap{\mathbb{R}}^{n}$, we have $iv\in(V\cap(i{\mathbb{R}}^{n}))$ and hence
the real part of $-iv\cdot u$ is in $\Re(V)$; but this is also the imaginary
part of $v\cdot u$. Furthermore, since $\Re(V)$ is also the set of imaginary
parts of vectors in $V$ (recall that $V$ is a complex vector space, so $V$ is
invariant under the multiplication by $i$), we find that for all $u\in V$ and
all $v\in V\cap{\mathbb{R}}^{n}$, the imaginary part of $v\cdot u$ equals that
of a vector in $V$, so that $v\cdot u\in V+{\mathbb{R}}^{n}$. Thus

$(V\cap{\mathbb{R}}^{n})\cdot V\subseteq V+{\mathbb{R}}^{n},$

and since clearly also

$(V\cap{\mathbb{R}}^{n})\cdot{\mathbb{R}}^{n}\subseteq{\mathbb{R}}^{n}\subseteq
V+{\mathbb{R}}^{n}$

the proposition follows. ∎

######  Proposition 2.2.4.

Assume that $m=\dim_{\mathbb{R}}\mathcal{A}(X)<2d-1$. Then there exists a
partition $\\{P_{1},P_{2}\\}$ of $[n]$ into two parts with the following
property. Let $V_{i}$ be the projection of $V$ in ${\mathbb{C}}^{P_{i}}$ and
set $X_{i}:=V_{i}\cap({\mathbb{C}}^{*})^{P_{i}}$. Then

$\dim_{\mathbb{R}}\mathcal{A}(X)=\dim_{\mathbb{R}}\mathcal{A}(X_{1})+\dim_{\mathbb{R}}\mathcal{A}(X_{2}).$

###### Proof.

In this case, $\ker
d_{{\mathbf{1}}}\operatorname{Log}=V\cap(i{\mathbb{R}}^{n})$ has real
dimension at least $2$. Hence so does $V\cap{\mathbb{R}}^{n}$. Let $v\in
V\cap{\mathbb{R}}^{n}$ be a vector linearly independent from ${\mathbf{1}}$.
After adding a suitable multiple of ${\mathbf{1}}$, we may assume that all
entries of $v$ are positive, and after scaling we may assume that the maximal
entry of $v$ equals $1$. Let $P_{1}\subseteq[n]$ be the positions where $v$
takes this maximal value $1$, and let $P_{2}$ be the complement of $P_{1}$ in
$[n]$. By construction, $P_{1}$ and $P_{2}$ are both nonempty.

By Proposition 2.2.3, $V+{\mathbb{R}}^{n}$ is preserved under Hadamard
multiplication with $v$. Iterating this multiplication and taking the limit,
we find that $V+{\mathbb{R}}^{n}$ is preserved under setting the coordinates
labelled by $P_{2}$ to zero. Then $V+{\mathbb{R}}^{n}$ is also preserved under
setting the coordinates labelled by $P_{1}$ to zero. Hence we have

$V+{\mathbb{R}}^{n}=(V_{1}+{\mathbb{R}}^{P_{1}})\times(V_{2}+{\mathbb{R}}^{P_{2}}),$

where $V_{1},V_{2}$ are defined in the proposition.

We assume that for $i=1,2$, the all-one vector ${\mathbf{1}}_{i}\in
V_{i}\subseteq{\mathbb{C}}^{P_{i}}$ has the same property required of
${\mathbf{1}}$, namely, that $\dim_{\mathbb{R}}\mathcal{A}(X_{i})$ equals the
rank of the linear map
$d_{{\mathbf{1}}_{i}}\operatorname{Log}:V_{i}\to{\mathbb{R}}^{P_{i}}$. (This
might not follow from the corresponding property of ${\mathbf{1}}$, but it may
be achieved by picking the original $p_{0}$ in a suitable dense subset of $X$
and then dividing by that $p_{0}$.)

Now we have

$\displaystyle\dim_{\mathbb{R}}\mathcal{A}(X)$
$\displaystyle=\dim_{\mathbb{R}}V-\dim_{\mathbb{R}}(V\cap{\mathbb{R}}^{n})=\dim_{\mathbb{R}}(V+{\mathbb{R}}^{n})-\dim_{\mathbb{R}}{\mathbb{R}}^{n}$
$\displaystyle=\dim_{\mathbb{R}}(V_{1}+{\mathbb{R}}^{P_{1}})+\dim_{\mathbb{R}}(V_{2}+{\mathbb{R}}^{P_{2}})-|P_{1}|-|P_{2}|$
$\displaystyle=(\dim_{\mathbb{R}}(V_{1}+{\mathbb{R}}^{P_{1}})-\dim_{\mathbb{R}}{\mathbb{R}}^{P_{1}})+(\dim_{\mathbb{R}}(V_{2}+{\mathbb{R}}^{P_{2}})-\dim_{\mathbb{R}}{\mathbb{R}}^{P_{2}})$
$\displaystyle=(\dim_{\mathbb{R}}V_{1}-\dim_{\mathbb{R}}(V_{1}\cap{\mathbb{R}}^{P_{1}}))+(\dim_{\mathbb{R}}V_{2}-\dim_{\mathbb{R}}(V_{2}\cap{\mathbb{R}}^{P_{2}}))$
$\displaystyle=\dim_{\mathbb{R}}\mathcal{A}(X_{1})+\dim_{\mathbb{R}}\mathcal{A}(X_{2}),$

as desired. Here we use the dimension formula for vector subspaces and (5)
three times for $V,V_{1},$ and $V_{2}$. ∎

###### Proof of Theorem 1.3.1..

The inequality $\leq$ was proved in §2.1. For $\geq$ we proceed by induction
on $n$; we therefore assume that the inequality holds for all strictly smaller
values of $n$.

Now if $\dim_{\mathbb{R}}\mathcal{A}(X)=2d-1$, where $d=\dim_{\mathbb{C}}V$,
then $\geq$ is witnessed by the partition of $[n]$ into a single part $P_{1}$.
Otherwise, by Proposition 2.2.4, there is a partition $\\{P_{1},P_{2}\\}$ of
$[n]$ such that

$\dim_{\mathbb{R}}\mathcal{A}(X)=\dim_{\mathbb{R}}\mathcal{A}(X_{1})+\dim_{\mathbb{R}}\mathcal{A}(X_{2})$

where $X_{i}:=V_{i}\cap({\mathbb{C}}^{*})^{n}$ and $V_{i}$ is the projection
of $V$ onto ${\mathbb{C}}^{P_{i}}$. Since $P_{1}$ and $P_{2}$ both have
cardinalities strictly smaller than $n$, the induction hypothesis applies:
there exist partitions $\\{P_{i1},\ldots,P_{ik_{i}}\\}$ of $P_{i}$ for $i=1,2$
with

$\dim_{\mathbb{R}}\mathcal{A}(X_{i})=\sum_{j=1}^{k_{i}}(2\,r_{V_{i}}(P_{ij})-1).$

Then the partition $\\{P_{11},\ldots,P_{1k_{1}},P_{21},\ldots,P_{2k_{2}}\\}$
of $[n]$ has the desired property for $X$. ∎

##  3\. The function $r^{\prime}$ is a rank function

In this section, we analyse the right-hand side of the amoeba dimension
formula in Theorem 1.3.1, and show that it is the rank function of another
matroid (Theorem 1.3.2). We fix a finite set $E$.

###  3.1. Preliminaries on multisets of subsets

We study finite multisets of subsets of $E$ and denote these by boldface
letters such as $\mathbf{S}$. If $\mathbf{S},\mathbf{T}$ are such multisets,
then so is their multiset union $\mathbf{S}\cup\mathbf{T}$. We write
$\\#\mathbf{S}$ for the number of elements of $\mathbf{S}$ counting
multiplicities.

Denote by $\succeq$ the transitive relation on the set of finite multisets of
subsets of $E$ such that $\mathbf{S}\succeq\mathbf{T}$ if and only if there is
a sequence of multisets

$\mathbf{S}=\mathbf{S}_{1},\ldots,\mathbf{S}_{\ell}=\mathbf{T}$

so that each $\mathbf{S}_{i+1}$ arises from $\mathbf{S}_{i}$ by replacing some
intersecting pair $S,S^{\prime}\in\mathbf{S}_{i}$, i.e., a pair such that
$S\cap S^{\prime}\neq\emptyset$, with the pair $S\cap S^{\prime},S\cup
S^{\prime}$. Note that we have
$\emptyset\not\in\mathbf{S}\Rightarrow\emptyset\not\in\mathbf{T}$.
Furthermore, if we define $n(\mathbf{S}):=\sum_{S\in\mathbf{S}}|S|^{2}$, then
we have $n(\mathbf{S}_{i+1})\geq n(\mathbf{S}_{i})$ with equality if and only
if $\mathbf{S}_{i+1}=\mathbf{S}_{i}$. Hence

$\mathbf{S}\succeq\mathbf{T}\Longrightarrow n(\mathbf{S})\leq n(\mathbf{T}),$

with equality if and only if $\mathbf{S}=\mathbf{T}$. It follows that
$\succeq$ is a partial order on finite multisets of subsets of $E$. Also,
since a multiset $\mathbf{S}$ with $k$ elements (counting multiplicities) has
$n(\mathbf{S})\leq k|E|^{2}$, there are no infinite decreasing sequences in
the partial order $\succeq$. Hence, for any multiset $\mathbf{S}$, there
exists $\mathbf{T}\preceq\mathbf{S}$ with $\mathbf{T}$ minimal with respect to
$\preceq$, that is, $\mathbf{T}\succeq\mathbf{U}$ implies
$\mathbf{T}=\mathbf{U}$. Moreover $\mathbf{T}$ is minimal with respect to
$\preceq$ if and only if it is cross-free: there are no sets
$T,T^{\prime}\in\mathbf{T}$ that cross in the sense that $T\cap
T^{\prime},T\setminus T^{\prime},T^{\prime}\setminus T$ are all nonempty.

For any multiset $\mathbf{S}$ of subsets of $E$, the finest common coarsening
is the set of subsets of $E$ defined by

$\mbox{fcc}(\mathbf{S}):=\left\\{T\subseteq\bigcup\mathbf{S}\mid T\text{ is an
inclusion-wise minimal nonempty set so that }\forall S\in\mathbf{S}:S\cap
T=\emptyset\text{ or }S\subseteq T\right\\}.$

Intuitively, every $T\in\mbox{fcc}(\mathbf{S})$ is obtained from starting with
some nonempty $S\in\mathbf{S}$, and keep merging with any other
$S^{\prime}\in\mathbf{S}$ with nonempty intersection until it stabilises. In
particular, $\mbox{fcc}(\mathbf{S})$ is a partition of $\bigcup\mathbf{S}$,
and the definition of the partial order $\succeq$ implies that

$\mathbf{S}\succeq\mathbf{T}\Longrightarrow\mbox{fcc}(\mathbf{S})=\mbox{fcc}(\mathbf{T}).$

Note that if $\mathbf{T}$ is cross-free, then
$\mbox{fcc}(\mathbf{T})\subseteq\mathbf{T}$.

For a partition $\mathbf{P}$ of $S\subseteq E$ and a partition
$\mathbf{P}^{\prime}$ of $S^{\prime}\subseteq E$, we define

$\mathbf{P}\vee\mathbf{P}^{\prime}:=\mbox{fcc}(\mathbf{P}\cup\mathbf{P}^{\prime})\text{
and }\mathbf{P}\wedge\mathbf{P}^{\prime}:=\\{P\cap
P^{\prime}:P\in\mathbf{P},P^{\prime}\in\mathbf{P}^{\prime}\\}\setminus\\{\emptyset\\}.$

Then $\mathbf{P}\vee\mathbf{P}^{\prime}$ is a partition of $S\cup S^{\prime}$,
and $\mathbf{P}\wedge\mathbf{P}^{\prime}$ is a partition of $S\cap
S^{\prime}$.

###  3.2. A new matroid from $M$

Now let $M$ be a loopless matroid on $E$ with rank function
$r:2^{E}\rightarrow\mathbb{N}$. Recall from §1.3 that, for a multiset
$\mathbf{S}$ consisting of nonempty subsets $S_{1},\ldots,S_{k}$ of $E$, we
have defined

$\tilde{r}(\mathbf{S})=\tilde{r}(S_{1},\ldots
S_{k}):=\sum_{i=1}^{k}2r(S_{i})-1.$

Furthermore, we have defined $r^{\prime}:2^{E}\rightarrow\mathbb{N}$ as

$r^{\prime}(S):=\min\left\\{\tilde{r}(\mathbf{P})\mid\mathbf{P}\text{ is a
partition of }S\right\\}.$

A partition $\mathbf{P}$ of $S$ with $r^{\prime}(S)=\tilde{r}(\mathbf{P})$
will be called an optimal partition of $S$ or simply optimal for $S$.

The submodularity of $r$ implies that, if
$\mathbf{S}=\mathbf{S}_{1},\ldots,\mathbf{S}_{\ell}=\mathbf{T}$ is a sequence
witnessing $\mathbf{S}\succeq\mathbf{T}$ and $\mathbf{S}_{i+1}$ arises from
$\mathbf{S}_{i}$ by replacing the pair $S,S^{\prime}$ by $S\cup
S^{\prime},S\cap S^{\prime}$, then

$\tilde{r}(\mathbf{S}_{i})-\tilde{r}(\mathbf{S}_{i+1})=(2r(S)-1)+(2r(S^{\prime})-1)-(2r(S\cup
S^{\prime})-1)-(2r(S\cap S^{\prime})-1)\geq 0$

for each $i$, so that

$\mathbf{S}\succeq\mathbf{T}\Longrightarrow\tilde{r}(\mathbf{S})\geq\tilde{r}(\mathbf{T}).$

######  Lemma 3.2.1.

Let $\mathbf{P},\mathbf{P}^{\prime}$ be partitions of $S,S^{\prime}\subseteq
E$, respectively. There is a partition $\mathbf{Q}$ of $S\cap S^{\prime}$ so
that

$\tilde{r}(\mathbf{P})+\tilde{r}(\mathbf{P}^{\prime})\geq\tilde{r}(\mathbf{P}\vee\mathbf{P}^{\prime})+\tilde{r}(\mathbf{Q}),$

$\mathbf{Q}$ is a coarsening of $\mathbf{P}\wedge\mathbf{P}^{\prime}$, and
$\\#\mathbf{P}+\\#\mathbf{P}^{\prime}=\\#\mathbf{P}\vee\mathbf{P}^{\prime}+\\#\mathbf{Q}$.

In the proof, we use the notation $c(\mathbf{S})_{e}$ for the number of sets
$S$ in the multiset $\mathbf{S}$ that contain a given $e\in E$ (counting
multiple occurrences of $S$). Note that

$\mathbf{S}\succeq\mathbf{T}\Longrightarrow
c(\mathbf{S})_{e}=c(\mathbf{T})_{e}.$

###### Proof.

Set $\mathbf{S}:=\mathbf{P}\cup\mathbf{P}^{\prime}$ and let $\mathbf{T}$ be a
cross-free multiset so that $\mathbf{S}\succeq\mathbf{T}$. We have

$\mathbf{P}\vee\mathbf{P}^{\prime}=\mbox{fcc}(\mathbf{P}\cup\mathbf{P}^{\prime})=\mbox{fcc}(\mathbf{S})=\mbox{fcc}(\mathbf{T}),$

Since $\mathbf{T}$ is cross-free, we have
$\mbox{fcc}(\mathbf{T})\subseteq\mathbf{T}$. Let $\mathbf{Q}$ be the multiset
that arises from $\mathbf{T}$ by taking away $\mbox{fcc}(\mathbf{T})$.

Then, for each $e\in E$,

$c(\mathbf{Q})_{e}=c(\mathbf{T})_{e}-c(\mbox{fcc}(\mathbf{T}))_{e}=c(\mathbf{S})_{e}-c(\mbox{fcc}(\mathbf{S}))_{e}=\left\\{\begin{array}[]{ll}1-1=0&\text{if
}e\in S\cup S^{\prime}\text{ and }e\not\in S\cap S^{\prime}\\\ 2-1=1&\text{if
}e\in S\cap S^{\prime}\\\ 0-0=0&\text{if }e\not\in S\cup
S^{\prime}\end{array}\right.$

So $\mathbf{Q}$ is a partition of $S\cap S^{\prime}$, and since each element
of $\mathbf{T}$ arises by taking unions and intersections starting from
$\mathbf{P}\cup\mathbf{P}^{\prime}$, $\mathbf{Q}$ is a coarsening of
$\mathbf{P}\wedge\mathbf{P}^{\prime}$. Since $\mathbf{S}\succeq\mathbf{T}$, we
have

$\tilde{r}(\mathbf{P})+\tilde{r}(\mathbf{P}^{\prime})=\tilde{r}(\mathbf{S})\geq\tilde{r}(\mathbf{T})=\tilde{r}(\mathbf{P}\vee\mathbf{P}^{\prime})+\tilde{r}(\mathbf{Q})$

as required. Finally,
$\\#\mathbf{P}+\\#\mathbf{P}^{\prime}=\\#\mathbf{S}=\\#\mathbf{T}=\\#(\mathbf{P}\vee\mathbf{P}^{\prime})+\\#\mathbf{Q}.$
∎

###  3.3. Proof of Theorem 1.3.2

###### Proof.

We show that $r^{\prime}$ satisfies the matroid rank axioms:

  1. (1)

$r^{\prime}(S)\geq 0$ for all $S\subseteq E$: Let $\mathbf{P}$ be an optimal
partition of $S$. As $M$ is loopless, we have $r(P)\geq 1$ whenever
$P\neq\emptyset$, and so

$r^{\prime}(S)=\tilde{r}(\mathbf{P})=\sum_{P\in\mathbf{P}}(2r(P)-1)\geq 0,$

as required.

  2. (2)

$r^{\prime}(S)\leq|S|$ for all $S\subseteq E$: this follows by taking the
partition $\mathbf{P}$ to be the partition into singletons.

  3. (3)

$r^{\prime}(S^{\prime})\leq r^{\prime}(S)$ whenever $S^{\prime}\subseteq
S\subseteq E$: Let $\mathbf{P}$ be an optimal partition of $S$. Then

$r^{\prime}(S^{\prime})\leq\tilde{r}(\mathbf{P}\wedge\\{S^{\prime}\\})\leq\tilde{r}(\mathbf{P})=r^{\prime}(S)$

as required.

  4. (4)

$r^{\prime}(S)+r^{\prime}(S^{\prime})\geq r^{\prime}(S\cup
S^{\prime})+r^{\prime}(S\cap S^{\prime})$ for all $S,S^{\prime}\subseteq E$:
Let $\mathbf{P},\mathbf{P}^{\prime}$ be optimal partitions of $S,S^{\prime}$,
respectively. By Lemma 3.2.1, there is a partition $\mathbf{Q}$ of $S\cap
S^{\prime}$ so that

$r^{\prime}(S)+r^{\prime}(S^{\prime})=\tilde{r}(\mathbf{P})+\tilde{r}(\mathbf{P}^{\prime})\geq\tilde{r}(\mathbf{P}\vee\mathbf{P}^{\prime})+\tilde{r}(\mathbf{Q})\geq
r^{\prime}(S\cup S^{\prime})+r^{\prime}(S\cap S^{\prime}),$

as required.∎

###  3.4. Structure of $M^{\prime}$

The matroid on $E$ with rank function $r^{\prime}$ is denoted $M^{\prime}$. We
make a few observations on the structure of $M^{\prime}$ in relation to $M$.

If $M$ and $N$ are matroids on a ground set $E$, then $M$ is a quotient of $N$
if each flat of $M$ is also a flat of $N$.

######  Lemma 3.4.1.

The matroid $M$ is a quotient of $M^{\prime}$.

###### Proof.

Let $F$ be a flat of $M$. Assume that $F$ is not a flat in $M^{\prime}$. Then
there exists $e\in E\setminus F$ such that $r^{\prime}(F+e)=r^{\prime}(F)$.
Let $\\{P_{1},\dots,P_{k}\\}$ be an optimal partition of $F+e$. We may assume
$e\in P_{1}$. Now $\tilde{r}(P_{1},\dots,P_{k})=r^{\prime}(F)$ implies that
$r(P_{1})=r(P_{1}-e)$. In particular, $e$ is contained in any flat containing
$P_{1}-e\subset F$, a contradiction to $F$ being a flat in $M$. Hence the
claim follows. ∎

The truncation of a matroid $M$ of rank $d>0$ is the matroid $N$ on the same
ground set with rank function $r_{N}(S):=\min\\{r_{M}(S),d-1\\}$.

######  Lemma 3.4.2.

If $M$ has rank $d>1$ and $N$ is the truncation of $M$, then

$r^{\prime}_{N}(S)=\min\\{r^{\prime}_{M}(S),2d-3\\}$

for all $S\subseteq E$.

###### Proof.

Clearly $r^{\prime}_{N}(S)\leq r^{\prime}_{M}(S)$. Suppose
$r^{\prime}_{N}(S)<r^{\prime}_{M}(S)$. Let $\mathbf{P}$ be an optimal
partition of $S$ with respect to $N$. Then

$\sum_{P\in\mathbf{P}}(2r_{N}(P)-1)=\tilde{r}_{N}(\mathbf{P})=r^{\prime}_{N}(S)<r^{\prime}_{M}(S)\leq\tilde{r}_{M}(\mathbf{P})=\sum_{P\in\mathbf{P}}(2r_{M}(P)-1)$

hence $r_{M}(P)>r_{N}(P)=\min\\{r_{M}(P),d-1\\}$ for some $P\in\mathbf{P}$.
Then $r_{M}(P)=d$ and $r_{N}(P)=d-1$, so that

$2d-3\geq 2r_{N}(S)-1=\tilde{r}_{N}(\\{S\\})\geq
r^{\prime}_{N}(S)=\tilde{r}_{N}(\mathbf{P})\geq 2r_{N}(P)-1=2d-3.$

Then $r^{\prime}_{N}(S)=2d-3$, as required. ∎

Let $c\in\mathbb{N}$. A matroid $M$ on the ground set $E$ and with rank
function $r$ is $c$-connected if there is no subset $S\subseteq E$ so that
$|S|\geq c,|E\setminus S|\geq c$, and

$r(S)+r(E\setminus S)-r(E)<c.$

The next example illustrates that even if we assume that $M$ has a high
connectivity (and representable over $\mathbb{C}$), the rank of $M^{\prime}$
may still be strictly less than the trivial bound $\min\\{|E|,2r(M)-1\\}$ from
Example 1. Indeed, a high connectivity will not even force the existence of an
optimal partition into few parts.

######  Example 3.

Let $c,k$ be positive integers so that $k>2c+1$. Consider the matroid $M$ that
arises from the disjoint union of matroids $M_{1},\ldots,M_{k}$ by truncating
$c$ times, where each $M_{i}$ has ground set $E_{i}$ and is isomorphic to the
uniform matroid $U_{c,2c}$. Let $E$ be the ground set of $M$, and let
$\mathbf{P}_{0}:=\\{E_{1},\ldots,E_{k}\\}$. Then the ground set of $M$ has
$n:=|E|=2ck$ elements, the rank of $M$ is $d:=ck-c$, and the rank in $M$ of
$S\subseteq E$ equals

$r(S)=\min\left\\{d,\sum_{i=1}^{k}\min\\{c,|S\cap E_{i}|\\}\right\\}.$

We first verify that $M$ is $c$-connected. Let $S\subseteq E$ with $|S|\geq c$
and $|E\setminus S|\geq c$. If $r(E\setminus S)=d$, then $r(S)+r(E\setminus
S)-r(E)=r(S)\geq\min\\{c,|S|\\}=c$. If $r(S)=d$, then similarly
$r(S)+r(E\setminus S)-r(E)\geq c$. In the remaining case $r(S)<d$ and
$r(E\setminus S)<d$, hence

$r(S)+r(E\setminus S)-r(E)=\sum_{i=1}^{k}\left(\min\\{c,|S\cap
E_{i}|\\}+\min\\{c,|S\setminus E_{i}|\\}\right)-(ck-c)\geq ck-(ck-c)=c$

as required.

Next, we show that the rank of $M^{\prime}$ is strictly less than
$\min\\{n,2d-1\\}$, and that any optimal partition will have at least $k$
parts. Consider an optimal partition $\mathbf{P}$ of $E$ so that
$\\#\mathbf{P}$ is as small as possible. Let $i\in[k]$. By Lemma 3.2.1, there
exists a partition $\mathbf{Q}$ of $E_{i}$ so that
$\tilde{r}(\mathbf{P})+\tilde{r}(\\{E_{i}\\})\geq\tilde{r}(\mathbf{P}\vee\\{E_{i}\\})+\tilde{r}(\mathbf{Q}).$
Since $\\{E_{i}\\}$ is an optimal partition for $E_{i}$, if follows that
$\mathbf{P}\vee\\{E_{i}\\}$ is optimal partition for $E$. By our choice of
$\mathbf{P}$, we have $\\#\mathbf{P}\leq\\#(\mathbf{P}\vee\\{E_{i}\\})$, so
that $E_{i}\subseteq P$ for some $P\in\mathbf{P}$. It follows that
$\mathbf{P}$ is a coarsening of $\mathbf{P}_{0}$. If $r(P)<d$ for each
$P\in\mathbf{P}$, then $\tilde{r}(\mathbf{P})=2ck-\\#\mathbf{P}$, so that
$\mathbf{P}=\mathbf{P}_{0}$ by the optimality of $\mathbf{P}$. If on the other
hand $r(P)=d$ for some part $P\in\mathbf{P}$, then $\tilde{r}(\mathbf{P})\geq
2d-1=2ck-2c-1>2ck-k=\tilde{r}(\mathbf{P}_{0})$ as $k>2c+1$, contradicting that
$\mathbf{P}$ is optimal. We conclude that $\mathbf{P}=\mathbf{P}_{0}$, and in
particular, that there are no optimal partitions with less than
$\\#\mathbf{P}_{0}=k$ parts. Then the rank of $M^{\prime}$ is
$\tilde{r}(\mathbf{P}_{0})=2ck-k<\min\\{2ck,2(ck-c)-1\\}=\min\\{n,2d-1\\}$, as
required.

Finally, as $U_{c,2c}$ is representable over $\mathbb{C}$ and taking disjoint
unions and truncation preserves representability over $\mathbb{C}$, $M$ is
also the matroid of some subspace $V\subseteq{\mathbb{C}}^{n}$, and
$M^{\prime}$ the matroid of the amoeba
$\mathcal{A}(V\cap({\mathbb{C}}^{*})^{n})$ (by Theorem 1.3.1 and Proposition
1.5.1).

##  4\. An algorithm for evaluating $r^{\prime}$

We retain the notation of the previous section and continue to explore the
functions $r^{\prime}$ and $\tilde{r}$ derived from a fixed rank function $r$
of a loopless matroid $M$ on a finite set $E$, aiming for an algorithm to
evaluate $r^{\prime}(S)$ given any $S\subseteq E$.

###  4.1. Optimal partitions form a lattice

######  Lemma 4.1.1.

Let $\mathbf{P},\mathbf{P}^{\prime}$ be optimal partitions of
$S,S^{\prime}\subseteq E$, respectively. If

$r^{\prime}(S)+r^{\prime}(S^{\prime})=r^{\prime}(S\cup
S^{\prime})+r^{\prime}(S\cap S^{\prime}),$

then $\mathbf{P}\vee\mathbf{P}^{\prime}$ is optimal for $S\cup S^{\prime}$ and
$\mathbf{P}\wedge\mathbf{P}^{\prime}$ is optimal for $S\cap S^{\prime}$.

###### Proof.

By Lemma 3.2.1, there exists a partition $\mathbf{Q}$ of $S\cap S^{\prime}$
that is a coarsening of the partition $\mathbf{P}\wedge\mathbf{P}^{\prime}$ so
that

$r^{\prime}(S)+r^{\prime}(S^{\prime})=\tilde{r}(\mathbf{P})+\tilde{r}(\mathbf{P}^{\prime})\geq\tilde{r}(\mathbf{P}\vee\mathbf{P}^{\prime})+\tilde{r}(\mathbf{Q})\geq
r^{\prime}(S\cup S^{\prime})+r^{\prime}(S\cap S^{\prime}).$

By our assumption that $r^{\prime}(S)+r^{\prime}(S^{\prime})=r^{\prime}(S\cup
S^{\prime})+r^{\prime}(S\cap S^{\prime})$, we have $r^{\prime}(S\cup
S^{\prime})=\tilde{r}(\mathbf{P}\vee\mathbf{P}^{\prime})$ and
$r^{\prime}(S\cap S^{\prime})=\tilde{r}(\mathbf{Q})$. So
$\mathbf{P}\vee\mathbf{P}^{\prime}$ is optimal for $S\cap S^{\prime}$, and
$\mathbf{Q}$ is optimal for $S\cap S^{\prime}$ as well as a coarsening of
$\mathbf{P}\wedge\mathbf{P}^{\prime}$.

Let $\mathbf{Q}^{*}$ be an optimal partition of $S\cap S^{\prime}$, as well as
a coarsening of $\mathbf{P}\wedge\mathbf{P}^{\prime}$, with
$\\#\mathbf{Q}^{*}$ as large as possible. By Lemma 3.2.1 there is a coarsening
$\mathbf{Q}^{\prime}$ of $\mathbf{P}\wedge\mathbf{Q}^{*}$ with

$r^{\prime}(S)+r^{\prime}(S\cap
S^{\prime})=\tilde{r}(\mathbf{P})+\tilde{r}(\mathbf{Q}^{*})\geq\tilde{r}(\mathbf{P}\vee\mathbf{Q}^{*})+\tilde{r}(\mathbf{Q}^{\prime})\geq
r^{\prime}(S)+r^{\prime}(S\cap S^{\prime}),$

so that we again have equality throughout, and with
$\\#\mathbf{P}+\\#\mathbf{Q}^{*}=\\#(\mathbf{P}\vee\mathbf{Q}^{*})+\\#\mathbf{Q}^{\prime}$.
Then $\mathbf{Q}^{\prime}$ is also a coarsening of
$\mathbf{P}\wedge\mathbf{P}^{\prime}$ and $r^{\prime}(S\cap
S^{\prime})=\tilde{r}(\mathbf{Q}^{\prime})$, so that
$\\#\mathbf{Q}^{\prime}\leq\\#\mathbf{Q}^{*}$ by our choice of
$\mathbf{Q}^{*}$. It follows that
$\\#\mathbf{P}\geq\\#(\mathbf{P}\vee\mathbf{Q}^{*})$ and hence each element of
$\mathbf{Q}^{*}$ is a subset of an element of $\mathbf{P}$. Similarly, each
element of $\mathbf{Q}^{*}$ is the subset of an element of
$\mathbf{P}^{\prime}$. Then
$\mathbf{Q}^{*}=\mathbf{P}\wedge\mathbf{P}^{\prime}$, and so
$\mathbf{P}\wedge\mathbf{P}^{\prime}$ is optimal for $S\cap S^{\prime}$. ∎

###  4.2. Coarsest optimal partition and submodular minimisation

It follows from Lemma 4.1.1 that for any set $S\subseteq E$ there is a unique
coarsest optimal partition

$\mathbf{P}^{*}:=\bigvee_{\mathbf{P}\text{ optimal for }S}\mathbf{P}$

so that each optimal partition for $S$ refines $\mathbf{P}^{*}$. Similarly,
there is a unique finest optimal partition

$\mathbf{P}_{*}:=\bigwedge_{\mathbf{P}\text{ optimal for }S}\mathbf{P}$

which refines each optimal partition for $S$.

We will describe an algorithm to calculate the coarsest optimal partition for
any given $S\subseteq E$. The coarsest optimal partition $\mathbf{P}$ for $S$
equals

(6) $\mathbf{Q}:=\\{Q\subseteq S\mid Q\text{ is inclusion-wise maximal so that
}r^{\prime}(Q)=2r(Q)-1\\}$

To see this, note that because $\mathbf{P}$ is optimal, each part
$P\in\mathbf{P}$ has $r^{\prime}(P)=2r(P)-1$ and hence is contained in one of
the elements $Q\in\mathbf{Q}$. The inclusion $P\subseteq Q$ cannot be strict,
for then $\mathbf{P}\vee\\{Q\\}$ would be a coarser optimal partition for $S$
than $\mathbf{P}$ by Lemma 4.1.1. Hence $\mathbf{P}=\mathbf{Q}$.

Because (6) refers to the value $r^{\prime}(Q)$, which we do not yet know how
to compute, (6) is not directly useful for finding the coarsest partition for
a general subset $S\subseteq E$. But if we assume that $S$ is independent in
$M^{\prime}$, i.e., that $|S|=r^{\prime}(S)$, then each $Q\subseteq S$ has
$r^{\prime}(Q)=|Q|$, so that we can identify the part $Q$ of the coarsest
optimal partition containing a given $e\in S$ as the largest $Q\subseteq S$
such that $e\in Q$ and $2r(Q)-1=|Q|$. Finding this $Q$ can be cast as a
submodular function minimisation problem; in the following lemma to this
effect, $B+e$ plays the role of $S$.

######  Lemma 4.2.1.

Let $B\subseteq E$ and $e\in E\setminus B$ be such that
$r^{\prime}(B+e)=|B+e|$. Then the function $f:2^{B}\rightarrow\mathbb{Q}$
determined by

(7) $f(I):=2r(I+e)-1-|I+e|-\frac{|I|}{2|B|}$

is submodular, and $J$ is a largest subset of $B$ so that $2r(J+e)-1=|J+e|$ if
and only $f(J)=\min_{I}f(I)$.

###### Proof.

The submodularity of $f$ follows from the submodularity of the rank function
$r$. For each $I\subseteq B$ we have
$|I+e|=r^{\prime}(I+e)\leq\tilde{r}(\\{I+e\\})=2r(I+e)-1$; hence,

$f(I)\leq
0~{}\Leftrightarrow~{}2r(I+e)-1\leq|I+e|+\frac{|I|}{2|B|}~{}\Leftrightarrow~{}2r(I+e)-1=|I+e|~{}\Leftrightarrow~{}f(I)=-\frac{|I|}{2|B|}.$

Here, the second $\Leftrightarrow$ uses the fact that
$0\leq\frac{|I|}{2|B|}\leq\frac{1}{2}$, while every other term is an integer.
Since $f(\emptyset)=0$, we have $0\geq\min_{I}f(I)$. The lemma follows.∎

That a submodular function $f$ obtained from a matroid rank function as in (7)
can be minimised in polynomial time was first established by Cunningham in
[Cun84]. The weakly polynomial time algorithm of Lee, Sidford, and Wong
[LSW15] for submodular set function minimisation takes
$O(k^{2}\log(k)\cdot\gamma+k^{3}\log^{O(1)}(k))$ time to minimise $f$, where
$k:=|B|$ and $\gamma$ is the time needed to evaluate $f$.

###  4.3. Proof of Theorem 1.3.3

To make sure that an optimal partition for $S$ is the coarsest, it will
suffice to consider the intersection of that partition with a spanning subset
$S^{\prime}$ of $S$.

######  Lemma 4.3.1.

Suppose that $S^{\prime}\subseteq S\subseteq E$, and let
$\mathbf{P}^{\prime},\mathbf{P}$ be partitions of $S^{\prime},S$ resp. so that
$\mathbf{P}^{\prime}=\mathbf{P}\wedge\\{S^{\prime}\\}$. Then:

  1. (1)

$\tilde{r}(\mathbf{P})=r^{\prime}(S)=r^{\prime}(S^{\prime})$ if and only if
$r(P\cap S^{\prime})=r(P)$ for all $P\in\mathbf{P}$ and $\mathbf{P}^{\prime}$
is optimal for $S^{\prime}$, and

  2. (2)

if $\tilde{r}(\mathbf{P})=r^{\prime}(S)=r^{\prime}(S^{\prime})$, then
$\mathbf{P}$ is the coarsest optimal partition of $S$ if and only if
$\mathbf{P}^{\prime}$ is the coarsest optimal partition of $S^{\prime}$.

###### Proof.

We have

$\tilde{r}(\mathbf{P}^{\prime})=\sum_{P\in\mathbf{P},P\cap
S^{\prime}\neq\emptyset}(2r(P\cap
S^{\prime})-1)\leq\sum_{P\in\mathbf{P}}(2r(P)-1)=\tilde{r}(\mathbf{P}),$

so that $\tilde{r}(\mathbf{P}^{\prime})=\tilde{r}(\mathbf{P})$ if and only if
$r(P\cap S^{\prime})=r(P)$ for all $P\in\mathbf{P}$. Since $r(P)>0$ for all
$P\in\mathbf{P}$, it follows that if
$\tilde{r}(\mathbf{P}^{\prime})=\tilde{r}(\mathbf{P})$, then
$\\#\mathbf{P}^{\prime}=\\#\mathbf{P}$.

  1. (1)

If $\tilde{r}(\mathbf{P})=r^{\prime}(S)=r^{\prime}(S^{\prime})$, then since
$r^{\prime}(S^{\prime})\leq\tilde{r}(\mathbf{P}^{\prime})\leq\tilde{r}(\mathbf{P})$
we have $\tilde{r}(\mathbf{P}^{\prime})=\tilde{r}(\mathbf{P})$ and
$r^{\prime}(S^{\prime})=\tilde{r}(\mathbf{P}^{\prime})$. Conversely if
$\tilde{r}(\mathbf{P}^{\prime})=\tilde{r}(\mathbf{P})$ and
$r^{\prime}(S^{\prime})=\tilde{r}(\mathbf{P}^{\prime})$, then
$r^{\prime}(S)\geq
r^{\prime}(S)=\tilde{r}(\mathbf{P}^{\prime})=\tilde{r}(\mathbf{P})\geq
r^{\prime}(S)$, and then we have equality throughout.

  2. (2)

Now assume that $\tilde{r}(\mathbf{P})=r^{\prime}(S)=r^{\prime}(S^{\prime})$,
so that $\mathbf{P}^{\prime}$ is optimal for $S^{\prime}$ and
$\tilde{r}(\mathbf{P}^{\prime})=\tilde{r}(\mathbf{P})$. Suppose that
$\mathbf{P}$ is not the coarsest optimal partition of $S$ and that say,
$\mathbf{Q}$ is a coarser optimal partition of $S$. Then
$\mathbf{Q}^{\prime}:=\mathbf{Q}\wedge\\{S^{\prime}\\}$ is an optimal
partition for $S^{\prime}$ by (1) and
$\\#\mathbf{Q}^{\prime}=\\#\mathbf{Q}<\\#\mathbf{P}=\\#\mathbf{P}^{\prime}$,
so that $\mathbf{P}^{\prime}$ is not the coarsest optimal partition of
$S^{\prime}$. Conversely, suppose that $\mathbf{P}^{\prime}$ is not coarsest
and that say, $\mathbf{Q}^{\prime}$ is an optimal partition of $S^{\prime}$
coarser than $\mathbf{P}^{\prime}$. Then
$\mathbf{Q}:=\mathbf{P}\vee\mathbf{Q}^{\prime}$ is an optimal partition of $S$
by Lemma 4.1.1. It follows that
$\mathbf{Q}\wedge\\{S^{\prime}\\}=\mathbf{Q}^{\prime}$, and hence
$\\#\mathbf{Q}=\\#\mathbf{Q}^{\prime}<\\#\mathbf{P}^{\prime}=\\#\mathbf{P}$.
Then $\mathbf{P}$ is not the coarsest optimal partition of $S$.

This proves the two parts of the lemma. ∎

Algorithm 1 Coarsest optimal partition $\mathbf{P}$ and basis $B$ for
$S\subseteq E$

if $S=\emptyset$ then

Put $\mathbf{P}:=\emptyset$, $B:=\emptyset$ and return $\mathbf{P}$, $B$

else

Pick $e\in S$, and put $S^{\prime}:=S-e$

Compute the coarsest optimal partition $\mathbf{P}^{\prime}$ and a basis
$B^{\prime}$ for $S^{\prime}$

if $r(P^{\prime}+e)=r(P^{\prime})$ for a $P^{\prime}\in\mathbf{P}^{\prime}$
then

Put $\mathbf{P}:=\mathbf{P}^{\prime}\vee\\{P^{\prime}+e\\},B:=B^{\prime}$

return $\mathbf{P}$, $B$

else

Compute a largest set $J\subseteq B^{\prime}$ such that $2r(J+e)-1=|J+e|$

Put $\mathbf{P}:=\mathbf{P}^{\prime}\vee\\{J+e\\}$, $B:=B^{\prime}+e$

return $\mathbf{P}$, $B$

end if

end if

######  Theorem 4.3.2.

Given a set $S\subseteq E$, Algorithm 1 determines the coarsest optimal
partition $\mathbf{P}$ for $S$ and a subset $B\subseteq S$ such that

$|B|=r^{\prime}(B)=r^{\prime}(S)=\tilde{r}(\mathbf{P}).$

Moreover, the algorithm runs in polynomial time, taking $O(nk+k^{3}\log(k))$
rank evaluations in $M$, where $n:=|S|,k:=r^{\prime}(S)$.

###### Proof.

We first argue that the output of the algorithm is correct, using induction on
$|S|$. The case that $S=\emptyset$ is trivial, so assume that
$S\neq\emptyset$, and let $e\in S$. By induction, the algorithm correctly
computes the coarsest optimal partition $\mathbf{P}^{\prime}$ for
$S^{\prime}:=S-e$ and a subset $B^{\prime}\subseteq S^{\prime}$ such that
$|B^{\prime}|=r^{\prime}(B)=r^{\prime}(S^{\prime})=\tilde{r}(\mathbf{P}^{\prime})$
initially.

If $r(P^{\prime}+e)=r(P^{\prime})$ for some
$P^{\prime}\in\mathbf{P}^{\prime}$, then consider the output
$\mathbf{P}:=\mathbf{P}^{\prime}\vee\\{P^{\prime}+e\\}$ and $B:=B^{\prime}$ in
this case. By construction of $\mathbf{P}$, we have
$\mathbf{P}^{\prime}=\mathbf{P}\vee\\{S^{\prime}\\}$, and $r(P-e)=r(P)$ for
all $P\in\mathbf{P}$. By application of Lemma 4.3.1(1) to
$S^{\prime},S,\mathbf{P}^{\prime},\mathbf{P}$, we find that
$\tilde{r}(\mathbf{P})=r^{\prime}(S)=r^{\prime}(S^{\prime})$. Since
$\mathbf{P}^{\prime}$ is the coarsest optimal partition of $S^{\prime}$, part
(2) of the same lemma yields that $\mathbf{P}$ is the coarsest optimal
partition of $S$. Since the rank and cardinality of $B=B^{\prime}$ equal
$r^{\prime}(S^{\prime})=r^{\prime}(S)$, the output is correct in this case.

If there is no $P^{\prime}\in\mathbf{P}^{\prime}$ so that
$r(P^{\prime}+e)=r(P^{\prime})$, then the algorithm proceeds to find some
largest set $J\subseteq B^{\prime}$ such that $2r(J+e)-1=|J+e|$. We will show
that the output $\mathbf{P}:=\mathbf{P}^{\prime}\vee\\{J+e\\}$,
$B:=B^{\prime}+e$ is again correct. We first argue that
$r(S)=r^{\prime}(S^{\prime})+1$. Consider the coarsest optimal partition
$\mathbf{Q}$ of $S$, and put
$\mathbf{Q}^{\prime}:=\mathbf{Q}\wedge\\{S^{\prime}\\}$. If
$r^{\prime}(S)=r^{\prime}(S^{\prime})$, then an application of Lemma 4.3.1(2)
to $S^{\prime},S,\mathbf{Q}^{\prime},\mathbf{Q}$ shows that
$\mathbf{Q}^{\prime}=\mathbf{P}^{\prime}$, and using part (1) we find that for
the element $Q\in\mathbf{Q}$ so that $e\in Q$, we have $r(Q-e)=r(Q)$. Then
$P^{\prime}:=Q-e\in\mathbf{Q}^{\prime}=\mathbf{P}^{\prime}$ has
$r(P^{\prime}+e)=r(P^{\prime})$, a contradiction. So
$r(S)=r^{\prime}(S^{\prime})+1$. By submodularity of $r^{\prime}$, we have
$r^{\prime}(S^{\prime})+r^{\prime}(B)\geq
r^{\prime}(S)+r^{\prime}(B^{\prime}).$ It follows that
$r^{\prime}(B)=r(B^{\prime})+1=|B^{\prime}|+1=|B|$. Since $J+e\subseteq B$, we
have

$r^{\prime}(J+e)=|J+e|=2r(J+e)-1=\tilde{r}(\\{J+e\\})$

so that $\\{J+e\\}$ is an optimal partition for $J+e$. By Lemma 4.1.1, and
noting that

$r^{\prime}(S^{\prime})+r^{\prime}(J+e)=r(S)+r^{\prime}(J),$

if follows that $\mathbf{P}=\mathbf{P}^{\prime}\vee\\{J+e\\}$ is optimal for
$S$. Let $\mathbf{Q}:=\mathbf{P}\wedge\\{B\\}$. Then $\mathbf{Q}$ is an
optimal partition of $B$ by Lemma 4.3.1(1) applied to
$B,S,\mathbf{Q},\mathbf{P}$. If there is a coarser optimal partition
$\mathbf{Q}^{\prime}$ of $B$, then there is a part
$Q^{\prime}\in\mathbf{Q}^{\prime}$ that is not contained in any part of
$\mathbf{Q}$, hence is not contained in any part of $\mathbf{P}$. If $e\not\in
Q^{\prime}$, then $\mathbf{P}^{\prime}\vee\\{Q^{\prime}\\}$ is a coarser
optimal partition of $S^{\prime}$ than $\mathbf{P}^{\prime}$, a contradiction.
So $e\in Q^{\prime}$, hence $J+e$ is properly contained in $Q^{\prime}$, and
$|Q^{\prime}|=\tilde{r}(\\{Q^{\prime}\\})=2r(Q^{\prime})-1$. But then
$J^{\prime}:=Q^{\prime}-e$ contradicts the choice of $J$. Therefore
$\mathbf{Q}$ is the coarsest optimal partition of $B$. By Lemma 4.3.1(2)
applied to $B,S,\mathbf{Q},\mathbf{P}$, it follows that $\mathbf{P}$ is the
coarsest optimal partition of $S$.

It remains to show that the algorithm takes polynomial time, and
$O(nk+k^{3}\log(k))$ rank evaluations in $M$. We only count the number of rank
evaluations in $M$, the remaining work clearly being less significant in
comparison. Not counting the rank evaluations used to recursively compute
$B^{\prime},\mathbf{P}^{\prime}$ for $S^{\prime}:=S-e$, the algorithm performs
at most $\\#\mathbf{P}^{\prime}\leq r^{\prime}(S^{\prime})\leq
r^{\prime}(S)=k$ rank evaluations to test if $r(P^{\prime}+e)=r(P^{\prime})$
for a $P^{\prime}\in\mathbf{P}^{\prime}$. If so, then $|B|=|B^{\prime}|$ and
no further rank evaluations are performed. If not, then $|B|=|B^{\prime}|+1$
and for the calculation of $J$ one may use submodular function minimisation as
in Lemma 4.2.1, taking $O(k^{2}\log(k))$ evaluations of the submodular
function $f$, each evaluation of $f$ taking one rank evaluation in $M$. The
depth of the recursion equals $|S|$, with at most $k$ rank evaluations at each
depth for testing and $O(k^{2}\log(k))$ for computing $J$ at each depth where
the cardinality of the basis $B$ increases. Thus the entire recursive
algorithm will see at most $|S|\cdot k+|B|\cdot
O(k^{2}\log(k))=O(nk+k^{3}\log(k))$ rank evaluations in $M$, as required. ∎

### Remark

It was pointed out to us by an anonymous referee that the matroid $M^{\prime}$
arises as a sub-matroid of the Dilworth truncation $N$ of the direct sum of
two copies $M_{1}$ and $M_{2}$ of $M$. That is,

$r^{\prime}(F)=r_{N}\left(\\{\\{f_{1},f_{2}\\}:f\in F\\}\right),$

where $e_{i}\in E(M_{i})$ denotes the copy of $e\in E(M)$. See also [Sch03,
Ch. 48] for an algorithm to evaluate the rank function of a Dilworth
truncation in the more general context of submodular functions. In that
reference,

$r^{\prime}(U)=\hat{f}(U):=\min\left\\{\sum_{P\in\mathcal{P}}f(P):\mathcal{P}\text{
a partition of }U\right\\}$

where we choose $f(P):=2r(P)-1$ as the base submodular function.

## References

  * [Ber71] G. M. Bergman.  The logarithmic limit-set of an algebraic variety.  Trans. Amer. Math. Soc., 157:459–470, 1971.
  * [Cun84] William H. Cunningham.  Testing membership in matroid polyhedra.  J. Combin. Theory Ser. B, 36(2):161–188, 1984.
  * [DRY20] Jan Draisma, Johannes Rau, and Chi Ho Yuen.  The dimension of an amoeba.  Bull. Lond. Math. Soc., 52(1):16–23, 2020.
  * [Egg22] Sarah Eggleston.  The dimension of amoebas of linear spaces.  Master’s thesis, Faculty of Science, University of Bern, 2022.
  * [Har92] Joe Harris.  Algebraic geometry. A first course, volume 133 of Grad. Texts Math. Berlin etc.: Springer-Verlag, 1992.
  * [LSW15] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong.  A faster cutting plane method and its implications for combinatorial and convex optimization.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015, pages 1049–1065. IEEE Computer Soc., Los Alamitos, CA, 2015.
  * [NS22] Mounir Nisse and Frank Sottile.  Describing amoebas.  Pac. J. Math., 317(1):187–205, 2022.
  * [Rau20] Johannes Rau.  The dimension of an amoeba.  LAGARTOS,
https://sites.google.com/site/cotterillethan/ethan-cotterill-eng/latin-
american-real-and-tropical-geometry-seminar, 2020\.

  * [Sch03] Alexander Schrijver.  Combinatorial optimization. Polyhedra and efficiency. Vol. B, volume 24,B of Algorithms and Combinatorics.  Springer-Verlag, Berlin, 2003.  Matroids, trees, stable sets, Chapters 39–69.
  * [Stu02] Bernd Sturmfels.  Solving systems of polynomial equations.  Number 97 in CBMS Regional Conferences Series. Providence, RI: American Mathematical Society, 2002.


# Quantum algorithm for doubling the amplitude of the search problem’s
solution states.

Mauro Mezzini  Roma Tre University, Italy  Fernando L. Pelayo  University of
Castilla - La Mancha, Spain  Fernando Cuartero  University of Castilla - La
Mancha, Spain

###### Abstract

In this paper we present a quantum algorithm which increases the amplitude of
the states corresponding to the solutions of the search problem by a factor of
almost two.

##  1 Introduction and preliminaries

We denote the set of natural number excluding the 0 element by
$\mathbb{N}^{+}$. If $x\in\mathbb{N}$, $0\leq x<2^{n}$ then we say that
$|x\rangle$ is a _computational state_. We denote by $|x_{n-1}x_{n-2}\dots
x_{0}\rangle$ the binary representation of $|x\rangle$ where $x_{n-1}$ is the
most significant bit of the binary representation of $x$. Let also denote by
$w(x)=\sum_{j=0}^{n-1}x_{j}$. If $z\in\mathbb{N}$, $0\leq z<2^{n}$ we denote
by $z\cdot x$ the sum $z\cdot x=\sum_{j=0}^{n-1}x_{j}z_{j}$. Furthermore, for
any $k\in\mathbb{N}$, $0<k<n$, we denote by $z_{\text{-k}}$ a natural number
obtained from $z$ by considering only the least $n-k$ significant bits, that
is, if the binary representation of $z$ is $z_{n-1}z_{n-2}\dots z_{1}z_{0}$
then the binary representation of $z_{\text{-k}}$ is $z_{n-k-1}z_{n-k-2}\dots
z_{0}$. The $S$ gate for a single qubit is represented by the following
matrix:

$S=\left|\begin{array}[]{cc}1&0\\\ 0&i\\\ \end{array}\right|$ (1)

$\dots$
$\dots$

##  2 The effect of applying Hadamard, S and Hadamard gates to
$|0\rangle^{\otimes^{n}}$

In this section we want to determine the effect of applying the Hadamard, S
and Hadamard gates on quantum state $|0\rangle^{\otimes^{n}}$, that is, we
want to determine a formula for

$|\alpha\rangle=H^{\otimes^{n}}S^{\otimes^{n}}H^{\otimes^{n}}|0\rangle^{\otimes^{n}}$
(2)

and we show that in the final superposition
$|\alpha\rangle=\sum_{z=0}^{2^{n}-1}a_{z}|z\rangle$ the amplitude $a_{z}$ of a
sigle state $|z\rangle$ depends by $w(z)$.

It is known [2] that given any computational state $|x\rangle$, $0\leq
x<2^{n}$

$|\psi\rangle=H^{\otimes^{n}}|x\rangle=\dfrac{1}{\sqrt{2^{n}}}\sum_{z=0}^{2^{n}-1}(-1)^{x\cdot
z}|z\rangle$ (3)

Now we start with the following Lemma

######  Lemma 1.

Let $0\leq x<2^{n}$

$S^{\otimes^{n}}|x\rangle=i^{w(x)}|x_{n-1}x_{n-2}\dots x_{0}\rangle$

###### Proof.

By induction on $n$ being the base case with $n=1$ straightforward. So suppose
that the statement holds for $n-1$. Then

$\displaystyle S^{\otimes^{n}}|x\rangle$
$\displaystyle=S|x_{n-1}\rangle\otimes S|x_{n-2}\rangle\dots\otimes
S|x_{0}\rangle=S^{\otimes^{n-1}}|x_{n-1}\dots x_{1}\rangle\otimes
S|x_{0}\rangle=$ $\displaystyle=i^{\sum_{j=1}^{n-1}x_{j}}|x_{n-1}\dots
x_{1}\rangle\otimes S|x_{0}\rangle=\text{ (by induction hypothesys) }$
$\displaystyle=i^{\sum_{j=1}^{n-1}x_{j}}|x_{n-1}\dots x_{1}\rangle\otimes
i^{x_{0}}|x_{0}\rangle=$ $\displaystyle=i^{w(x)}|x_{n-1}x_{n-2}\dots
x_{0}\rangle$

∎

Now by Lemma 1 and equation (3), we have that

$\displaystyle|\psi_{1}\rangle=S^{\otimes^{n}}H^{\otimes^{n}}|0\rangle^{\otimes^{n}}=S^{\otimes^{n}}\dfrac{1}{\sqrt{2^{n}}}\sum_{x=0}^{2^{n}-1}|x\rangle=\dfrac{1}{\sqrt{2^{n}}}\sum_{x=0}^{2^{n}-1}i^{w(x)}|x\rangle$

and applying the Hadamard to $|\psi_{1}\rangle$, by (3), we have that

$\displaystyle|\psi_{2}\rangle=H^{\otimes^{n}}|\psi_{1}\rangle=\dfrac{1}{\sqrt{2^{n}}}\sum_{x=0}^{2^{n}-1}i^{w(x)}\left[\dfrac{1}{\sqrt{2^{n}}}\sum_{z=0}^{2^{n}-1}(-1)^{x\cdot
z}|z\rangle\right]$

and reordering the term of the sum we have that

$\displaystyle|\psi_{2}\rangle=\dfrac{1}{2^{n}}\sum_{z=0}^{2^{n}-1}\sum_{x=0}^{2^{n}-1}(-1)^{x\cdot
z}i^{w(x)}|z\rangle=\dfrac{1}{2^{n}}\sum_{z=0}^{2^{n}-1}\left(\sum_{x=0}^{2^{n}-1}i^{w(x)}(-1)^{x\cdot
z}\right)|z\rangle$

So in order to compute the amplitudes of $|\psi_{2}\rangle$ we need to compute
the sum

$\sum_{x=0}^{2^{n}-1}i^{w(x)}(-1)^{x\cdot z}$

for every $0\leq z<2^{n}$. We will do this in the following two theorems.
First of all we need the following Lemma.

######  Lemma 2.

Let $0\leq z<2^{2m+1}$ and $0\leq x<2^{2m+1}$ and let $z_{2m}z_{2m-1}\dots
z_{0}$ and $x_{2m}x_{2m-1}\dots z_{0}$ be the binary representation,
respectively, of $z$ and $x$. We have that

$\displaystyle\sum_{x=2^{2m}}^{2^{2m+1}-1}$ $\displaystyle
i^{w(x)}(-1)^{\sum_{j=0}^{2m}z_{j}\cdot
x_{j}}=i(-1)^{z_{2m}}\sum_{x=0}^{2^{2m}-1}i^{w(x)}(-1)^{\sum_{j=0}^{2m-1}z_{j}\cdot
x_{j}}$ (4)

###### Proof.

We note that, on the left hand of the equation (4), for every element of the
sum, we have that $x_{2m}=1$. Therefore $\sum_{j=0}^{2m}z_{j}\cdot
x_{j}=\sum_{j=0}^{2m-1}z_{j}\cdot x_{j}+z_{2m}$. Based on this we have that

$\displaystyle\sum_{x=2^{2m}}^{2^{2m+1}-1}$ $\displaystyle
i^{w(x)}(-1)^{\sum_{j=0}^{2m}z_{j}\cdot
x_{j}}=(-1)^{z_{2m}}\sum_{x=2^{2m}}^{2^{2m+1}-1}i^{w(x)}(-1)^{\sum_{j=0}^{2m-1}z_{j}\cdot
x_{j}}$

Furthermore for the same reason above, if $2^{2m}\leq x<2^{2m+1}$ and if
$0\leq\bar{x}<2^{2m}$ then we have that $w(x)=w(\bar{x})+1$ and this prove the
equation (4). ∎

######  Theorem 3.

Let $0\leq z<2^{n}$, $z\in\mathbb{N}$. If $n=2m$ is even we have that

$\sum_{x=0}^{2^{n}-1}i^{w(x)}(-1)^{z\cdot x}=(-1)^{w(z)}i^{m+w(z)}2^{m}$ (5)

###### Proof.

We prove the equation (5) on induction on $m$ being the base case with $m=1$
easily verifiable for all $z\in\\{0,1,2,3\\}$. So suppose the statement holds
for all $h\leq m$ and for all $0\leq z<2^{2m}$. Then, for any $0\leq
z<2^{2m+2}$ we have

$\displaystyle\sum_{x=0}^{2^{2m+2}-1}i^{w(x)}(-1)^{z\cdot x}=$
$\displaystyle\sum_{x=0}^{2^{2m}-1}i^{w(x)}(-1)^{\sum_{j=0}^{2m-1}z_{j}\cdot
x_{j}}$ (6) $\displaystyle+$
$\displaystyle\sum_{x=2^{2m}}^{2^{2m+1}-1}i^{w(x)}(-1)^{\sum_{j=0}^{2m}z_{j}\cdot
x_{j}}+$ (7) $\displaystyle+$
$\displaystyle\sum_{x=2^{2m+1}}^{2^{2m+2}-1}i^{w(x)}(-1)^{\sum_{j=0}^{2m+1}z_{j}\cdot
x_{j}}$ (8)

Now, by equation (4) and by induction hypothesys, we have that (7) is equal to

$\displaystyle\sum_{x=2^{2m}}^{2^{2m+1}-1}$ $\displaystyle
i^{w(x)}(-1)^{\sum_{j=0}^{2m}z_{j}\cdot
x_{j}}=i(-1)^{z_{2m}}\sum_{x=0}^{2^{2m}-1}i^{w(x)}(-1)^{\sum_{j=0}^{2m-1}z_{j}\cdot
x_{j}}=$
$\displaystyle=i(-1)^{z_{2m}}(-1)^{w(z_{\text{-2}})}i^{m+w(z_{\text{-2}})}2^{m}$
(9)

Likewise, in the term (8), for each $x$ is the sum, the bit $x_{2m+1}$ is
always set to 1, so we have that (8) is, by equation (4), equal to

$\displaystyle\sum_{x=2^{2m+1}}^{2^{2m+2}-1}$ $\displaystyle
i^{w(x)}(-1)^{\sum_{j=0}^{2m+1}z_{j}\cdot
x_{j}}=i(-1)^{z_{2m+1}}\sum_{x=0}^{2^{2m+1}-1}i^{w(x)}(-1)^{\sum_{j=0}^{2m}z_{j}\cdot
x_{j}}$ (10)

Now by repeatedly applying equation (4) and the induction hypothesys we have
that the sum in right hand of equation (10) is

$\displaystyle\sum_{x=0}^{2^{2m+1}-1}$ $\displaystyle
i^{w(x)}(-1)^{\sum_{j=0}^{2m}z_{j}\cdot x_{j}}=$ (11) $\displaystyle=$
$\displaystyle\sum_{x=0}^{2^{2m}-1}i^{w(x)}(-1)^{\sum_{j=0}^{2m-1}z_{j}\cdot
x_{j}}+\sum_{x=2^{2m}}^{2^{2m+1}-1}i^{w(x)}(-1)^{\sum_{j=0}^{2m}z_{j}\cdot
x_{j}}=$
$\displaystyle=(-1)^{w(z_{\text{-2}})}i^{m+w(z_{\text{-2}})}2^{m}+i(-1)^{z_{2m}}\sum_{x=0}^{2^{2m}-1}i^{w(x)}(-1)^{\sum_{j=0}^{2m-1}z_{j}\cdot
x_{j}}=$
$\displaystyle=(-1)^{w(z_{\text{-2}})}i^{m+w(z_{\text{-2}})}2^{m}\left[1+i(-1)^{z_{2m}}\right]$
(12)

So if we replace (12) in (10) and if we sum togheter (6), (9) and (10) we
obtain

$\displaystyle a_{z}=$
$\displaystyle(-1)^{w(z_{\text{-2}})}i^{m+w(z_{\text{-2}})}2^{m}\left[1+i(-1)^{z_{2m}}+i(-1)^{z_{2m+1}}+i^{2}(-1)^{z_{2m}+z_{2m+1}}\right]=$
$\displaystyle=$
$\displaystyle(-1)^{w(z_{\text{-2}})}i^{m+1+w(z_{\text{-2}})}2^{m}\left[-i+(-1)^{z_{2m}}+(-1)^{z_{2m+1}}+i(-1)^{z_{2m}+z_{2m+1}}\right]$
(13)

Now if we denote by $P=(-1)^{w(z_{\text{-2}})}i^{m+1+w(z_{\text{-2}})}2^{m}$
we have that (13) is

$\displaystyle a_{z}=\left\\{\begin{array}[]{rl}2P&\text{ if
$z_{2m}=z_{2m+1}=0$ }\\\ -2iP&\text{ if $z_{2m}\neq z_{2m+1}$ }\\\ -2P&\text{
if $z_{2m}=z_{2m+1}=1$ }\\\ \end{array}\right.$

and it is now easy to verify that

$a_{z}=(-1)^{w(z)}i^{m+1+w(z)}2^{m+1}$

for every $0\leq z<2^{2m+2}$, and this proves the induction step. ∎

######  Theorem 4.

Let $n=2m+1$ an odd natural, $m\in\mathbb{N}$ and let $0\leq z<2^{n}$,
$z\in\mathbb{N}$. Then

$\sum_{x=0}^{2^{n}-1}i^{w(x)}(-1)^{z\cdot x}=(-1)^{w(z)}i^{m+w(z)}2^{m}(1+i)$
(14)

###### Proof.

First of all we note that equation (14) holds if $m=0$ and $z\in\\{0,1\\}$. So
in the following we suppose that $m>1$. We have that

$\displaystyle a_{z}$
$\displaystyle=\sum_{x=0}^{2^{2m+1}-1}i^{w(x)}(-1)^{z\cdot x}=$
$\displaystyle=$
$\displaystyle\sum_{x=0}^{2^{2m}-1}i^{w(x)}(-1)^{\sum_{j=0}^{2m-1}z_{j}\cdot
x_{j}}+\sum_{x=2^{2m}}^{2^{2m+1}-1}i^{w(x)}(-1)^{\sum_{j=0}^{2m}z_{j}\cdot
x_{j}}$

and, by Theorem 3, and by equation (4), we have

$\displaystyle a_{z}$
$\displaystyle=(-1)^{w(z_{\text{-1}})}i^{m+w(z_{\text{-1}})}2^{m}+i(-1)^{z_{2m}}\sum_{x=0}^{2^{2m}-1}i^{w(x)}(-1)^{\sum_{j=0}^{2m-1}z_{j}\cdot
x_{j}}=$ $\displaystyle=$
$\displaystyle(-1)^{w(z_{\text{-1}})}i^{m+w(z_{\text{-1}})}2^{m}+i(-1)^{z_{2m}}(-1)^{w(z_{\text{-1}})}i^{m+w(z_{\text{-1}})}2^{m}=$
$\displaystyle=$
$\displaystyle(-1)^{w(z_{\text{-1}})}i^{m+w(z_{\text{-1}})}2^{m}\left[1+i(-1)^{z_{2m}}\right]$
(15)

Let $z_{2m}z_{2m-1}\dots z_{0}$ be the binary representation of $z$. Suppose
first that $z_{2m}=0$. Then equation (2) become

$(-1)^{w(z)}i^{m+w(z)}2^{m}+(-1)^{w(z)}i^{m+w(z)+1}2^{m}$ (16)

and the Theorem is therefore proved. So suppose that $z_{2m}=1$. Then equation
(2) become

$(-1)^{w(z)-1}i^{m+w(z)-1}2^{m}+(-1)^{w(z)}i^{m+w(z)}2^{m}$ (17)

but observing that

$(-1)^{w(z)}i^{m+w(z)+1}=(-1)^{w(z)-1}i^{m+w(z)-1}$ (18)

we have that also in this case the Theorem is satisfied. ∎

As an example we have computed the amplitudes $a_{z}$ (disregarding the
normalization factor) for $n\in{3,4}$ and we report them on Table 1.

$\mathbf{|z\rangle}$ | $\mathbf{a_{z}}$
---|---
$|000\rangle$ | $-2+2i$
$|001\rangle$ | $2+2i$
$|010\rangle$ | $2+2i$
$|011\rangle$ | $2-2i$
$|100\rangle$ | $2+2i$
$|101\rangle$ | $2-2i$
$|110\rangle$ | $2-2i$
$|111\rangle$ | $-2-2i$

$\mathbf{|z\rangle}$ | $\mathbf{a_{z}}$
---|---
$|0000\rangle$ | $-4$
$|0001\rangle$ | $4i$
$|0010\rangle$ | $4i$
$|0011\rangle$ | $4$
$|0100\rangle$ | $4i$
$|0101\rangle$ | $4$
$|0110\rangle$ | $4$
$|0111\rangle$ | $-4i$
$|1000\rangle$ | $4i$
$|1001\rangle$ | $4$
$|1010\rangle$ | $4$
$|1011\rangle$ | $-4i$
$|1100\rangle$ | $4$
$|1101\rangle$ | $-4i$
$|1110\rangle$ | $-4i$
$|1111\rangle$ | $-4$

Table 1: Left the amplitudes of $a_{z}$ for $n=3$. Right the amplitudes of
$a_{z}$ for $n=4$. In order to get the final amplitudes one should multiply
them by a suitable normalization factor.

##  3 Doubling the amplitude of the search problem’s solution states

In this section we consider a quantum circuit for doubling the amplitude of
solution’s states of the search problem. For a search problem we refer, in
general, to the problem of finding a solution of some NP-complete problem.
Like in the Groover algorithm we will use the intrinsic quantum mechanical
parallelism and an oracle $f(|x\rangle)\in\\{0,1\\}$, specifically designed
for the specific problem at hand, which return $1$ is $x$ is a solution of the
problem and $0$ otherwise.

In particular, in order to present in the detail the results of this paper, we
will use a quantum oracle for the Partition Problem (PP). In the PP we have a
finite set of elements $E$ and a function $s:E\rightarrow\mathbb{N}^{+}$. We
want to find a subset $E^{\prime}\subset E$ such that $\sum_{e\in
E^{\prime}}s(e)=\sum_{e\in E\setminus E^{\prime}}s(e)$. From now on we do not
loss generality if we consider the set $E$ equal to the set of the first $|E|$
naturals, that is we always consider $E=\\{0,1,\dots,n-1\\}$. Furthermore we
note that if PP has a solution $E^{\prime}$ then $E-E^{\prime}$ is also a
solution of the PP:

The partition problem (PP) is well known to be an NP-complete problem [1].

We describe, in the following, an application of the gates described in the
previous section in a quantum circuit to deal with PP (see Figure 1). While
the following results apply specifically to the PP they can be applied to any
other search problem.

Denote by $\mathcal{S}=\sum_{e\in E}s(e)/2$. Recall that PP problem has a
solution only if $\mathcal{S}$ is an integer. We use the two’s complements
representation of $-\mathcal{S}$ requiring
$m=\lceil\log_{2}{\mathcal{S}}\rceil+1$ qubits. Then for each $e\in E$, we use
$k_{e}=\lceil\log_{2}{s(e)}\rceil+1$ qubits to encode $s(e)$. These qubits
will remain constant in every phase of the circuit and therefore we will not
consider them in the reasoning that follows. We use $n$ qubits to encode a
subset $E^{\prime}$ of $E$. If $|x_{n-1}x_{n-2}\dots x_{0}\rangle$ is the
state of those $n$ qubits, then an element $e$, $0\leq e<n$, is included in
the set $E^{\prime}$ if and only if $x_{e}=1$. We will use $m$ qubits, denoted
in the following by $|\sigma\rangle$, to store the sum
$\sigma=-\mathcal{S}+\sum_{e\in E^{\prime}}s(e)$ for the elements selected in
$|x\rangle$. In this way $|\sigma\rangle=|0\rangle^{\otimes^{m}}$ for a
solution $|x\rangle$ of the PP. We also use a control qubit $|c\rangle$.

So we have four groups of bits: $|x\rangle$, $|\sigma\rangle$, $|c\rangle$ and
the sets of qubits used to represent the constants $s(e)$ for each element of
$E$. Note that the number of qubits of the circuit, $n+m+1+\sum_{e\in
E}k_{e}$, is polynomial in the size of a coincise specification of the PP.

At the beginning of the circuit we have the following superposition:

$\displaystyle|\varphi_{0}\rangle=|0\rangle^{\otimes^{n}}|\sigma\rangle|c\rangle$

where $\sigma$ is set to the two’s complement of $-\mathcal{S}$ and
$|c\rangle$ is set to $|1\rangle$. Then, we apply the Hadamard gate to the
first $n$ qubits obtaining

$\displaystyle|\varphi_{1}\rangle$ $\displaystyle=\left(H^{\otimes^{n}}\otimes
I^{m+1}\right)|\varphi_{0}\rangle=\dfrac{1}{\sqrt{2^{n}}}\sum_{x=0}^{2^{n}-1}|x\rangle|\sigma\rangle|c\rangle$

Next, we uses each qubit $x_{e}$ to conditionally sum the element $s(e)$ to
$|\sigma\rangle$. If there exist a solution to the PP then, in the final
superposition of $|\sigma\rangle$, the amplitude of the state
$|x\rangle|0\rangle^{\otimes^{m}}|c\rangle$ will be not $0$. The states
$|x\rangle$ for which $|\sigma\rangle$ is zero wil be referred as the
_solutions states_ of the PP. The control qubit $|c\rangle$ will be set to
zero exactly for those states for which
$|\sigma\rangle=|0\rangle^{\otimes^{m}}$. At this point we apply an
uncomputational step in order to set $|\sigma\rangle=|-\mathcal{S}\rangle$.
Now if we apply the $S$ gate to the first $n$ qubits we obtain, by Lemma 1

$\displaystyle|\varphi_{2}\rangle$ $\displaystyle=\left(S^{\otimes^{n}}\otimes
I^{m+1}\right)|\varphi_{1}\rangle=\dfrac{1}{\sqrt{2^{n}}}\sum_{x=0}^{2^{n}-1}i^{w(x)}|x\rangle|\sigma\rangle|c\rangle$

After this we apply again the Hadamard gate to the first $n$ qubits. This
operation is controlled by the control qubit in a way that the Hadamard port
is applied only to non solution states. For the sake of simplicity we suppose
in the following, that the PP has only two solution whose numeric
representation are $y$ and its bitwise complement $\overline{y}$. By equation
(4), we obtain

$\displaystyle|\varphi_{2}\rangle$ $\displaystyle\xrightarrow{\text{contr
}H^{\otimes^{n}}}|\varphi_{3}\rangle=\dfrac{1}{\sqrt{2^{n}}}\sum_{z\in\\{y,\overline{y}\\}}i^{w(z)}|z\rangle|\sigma\rangle|0\rangle+$
$\displaystyle+$
$\displaystyle\dfrac{1}{2^{n}}\sum_{z=0}^{2^{n}-1}\sum_{x\notin\\{y,\overline{y}\\}}i^{w(x)}(-1)^{x\cdot
z}|z\rangle|\sigma\rangle|1\rangle=$ $\displaystyle=$
$\displaystyle\dfrac{1}{2^{n}}\left[\sqrt{2^{n}}\sum_{z\in\\{y,\overline{y}\\}}i^{w(z)}|z\rangle|\sigma\rangle|0\rangle+\sum_{z=0}^{2^{n}-1}\sum_{x\notin\\{y,\overline{y}\\}}i^{w(x)}(-1)^{x\cdot
z}|z\rangle|\sigma\rangle|1\rangle\right]$ (19)

Now we want to quantify the amplitude of the state
$|y\rangle|\sigma\rangle|1\rangle$ and
$|\overline{y}\rangle|\sigma\rangle|1\rangle$ of equation (19). We consider
only the state $|y\rangle|\sigma\rangle|1\rangle$ since the same arguments can
be applied to state $|\overline{y}\rangle|\sigma\rangle|1\rangle$. The
amplitude $b_{y}$ fr the state $|y\rangle|\sigma\rangle|1\rangle$ (in the
following we disregard the normalization factor $1/2^{n}$) is given by the
following formula

$\displaystyle b_{y}=\sum_{x\notin\\{y,\overline{y}\\}}i^{w(x)}(-1)^{x\cdot
y}$ (20)

We may write the above sum as

$\displaystyle b_{y}=\sum_{x\notin\\{y,\overline{y}\\}}i^{w(x)}(-1)^{x\cdot
y}=\sum_{x=0}^{2^{n}}i^{w(x)}(-1)^{x\cdot
y}-\sum_{x\in{\\{y,\overline{y}\\}}}i^{w(x)}(-1)^{x\cdot y}$ (21)

We have that

$\displaystyle\sum_{x\in{\\{y,\overline{y}\\}}}i^{w(x)}(-1)^{x\cdot y}$
$\displaystyle=i^{w(y)}(-1)^{y\cdot y}+i^{n-w(y)}(-1)^{\overline{y}\cdot y}=$
$\displaystyle=$ $\displaystyle i^{w(y)}(-1)^{{w(y)}}+i^{n-w(y)}=$ (22)

Then, recalling that $i^{x}=i^{-x}$ when $x$ is even and $i^{-x}=-i^{x}$ when
$x$ is odd, we have two cases: $w(y)$ is even and then

$\displaystyle i^{w(y)}(-1)^{{w(y)}}$
$\displaystyle+i^{n-w(y)}=i^{w(y)}(-1)^{{w(y)}}+i^{n+w(y)}=$
$\displaystyle=i^{w(y)}(1+i^{n})$ (23)

while if $w(y)$ is odd

$\displaystyle i^{w(y)}(-1)^{{w(y)}}$
$\displaystyle+i^{n-w(y)}=i^{w(y)}(-1)^{{w(y)}}-i^{n+w(y)}=$
$\displaystyle=-i^{w(y)}(1+i^{n})$ (24)

For simplicity of notation in the following we denote $w(y)$ as simply
$\overline{w}$. We have that if $n=2m$ is even then, by Theorem 3, $b_{y}$ is

$\displaystyle
b_{y}=\left\\{\begin{array}[]{ll}(-1)^{\overline{w}}i^{m+{\overline{w}}}2^{m}-i^{\overline{w}}(1+i^{2m})&\text{
if $\overline{w}$ is even}\\\ &\\\
(-1)^{\overline{w}}i^{m+{\overline{w}}}2^{m}+i^{\overline{w}}(1+i^{2m})&\text{
if $\overline{w}$ is odd}\\\ \end{array}\right.$ (28)

while if $n=2m+1$ is odd, by Theorem 4, $b_{y}$ is

$\displaystyle
b_{y}=\left\\{\begin{array}[]{ll}(-1)^{\overline{w}}i^{m+\overline{w}}2^{m}(1+i)-i^{\overline{w}}(1+i^{2m+1})&\text{
if $\overline{w}$ is even}\\\ &\\\
(-1)^{\overline{w}}i^{m+\overline{w}}2^{m}(1+i)+i^{\overline{w}}(1+i^{2m+1})&\text{
if $\overline{w}$ is odd}\\\ \end{array}\right.$ (32)

It is immediate to check that in the above equations (28) and (32) the term
$i^{\overline{w}}(1+i^{n})$ become trascurable, with respect to the other term
in the equation, as $m$ become bigger. We conclude that the amplitude of the
state $|y\rangle|\sigma\rangle|1\rangle$ is almost the same of the amplitude
of state $|y\rangle|\sigma\rangle|0\rangle$, thus effectively duplicating the
chances of state $|y\rangle$ at the end of the circuit. For example if
$n=2m+1=3$ and $|y\rangle=|011\rangle$ we have that $b_{y}=3-3i$, so that the
probability of getting $|y\rangle$ is, by (19),
$\dfrac{1}{64}\left[|2\sqrt{2}|^{2}+|3-3i|^{2}\right]=\dfrac{26}{64}=.40625$
which is exactly the output of the quirk simulator.

Figure 1: The circuit exploliting $S$ gates.

##  4 Conclusion and future work

We presented here a quantum algorithm for doubling the amplitude of the state
correspondig to the solution of the partition problem. This is interesting
because if we would be able to iterate such a doubling we could provide a
polynomial quantum algorithm for solving an NP-complete problem. Possible
future works should focus on: generalizing the mathematical results to istance
of search problems where there are more than 2 solutions, find out if this
algorithm can be combined to the Goover algorithm in order to seed up the
latter of a factor of $p$ where $p\geq 2$ and, more important, to check if and
how it is possibile to iterate the doubling of the amplitude in order to get
some polynomial time algorithm for solving the search problem.

## References

  * [1] R. Karp.  Reducibility among combinatorial problems.  In R. Miller and J. Thatcher, editors, Complexity of Computer Computations, pages 85–103. Plenum Press, 1972.
  * [2] M. A. Nielsen and I. L. Chuang.  Quantum Computation and Quantum Information: 10th Anniversary Edition.  Cambridge University Press, USA, 10th edition, 2011.