# Products of polymatroids with the strong exchange property

Lisa Nicklasson  Max-Planck Institute for Mathematics in the Sciences,
Leipzig, Germany
<EMAIL_ADDRESS>
###### Abstract.

It was conjectured by White in 1980 that the toric ring associated to a
matroid is defined by symmetric exchange relations. This conjecture was
extended to discrete polymatroids by Herzog and Hibi, and they prove that the
conjecture holds for polymatroids with the so called _strong exchange
property_. In this paper we generalize their result to polymatroids that are
products of polymatroids with the strong exchange property. This also extends
a result by Conca on transversal polymatroids.

##  1\. Polymatroidal bases

Let $\mathbb{K}$ be a field, and let $\mathbb{K}[X]$ denote the polynomial
ring over $\mathbb{K}$ on the set of variables $X=\\{x_{1},\ldots,x_{n}\\}$.
We equip $\mathbb{K}[X]$ with the standard grading, meaning that
$\deg(x_{1}^{\alpha_{1}}\cdots
x_{n}^{\alpha_{n}})=\alpha_{1}+\dots+\alpha_{n}$. We will also use the
notation $\deg_{i}(x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}})=\alpha_{i}$.

######  Definition 1.1.

We call a set $B$ of monomials in $\mathbb{K}[X]$ a _polymatroidal basis_ if
all the monomials in $B$ are of the same degree and the following property
holds. If $f$ and $g$ are monomials in $B$ with $\deg_{i}f>\deg_{i}g$ for some
$i$, then there is a $j$ such that $\deg_{j}f<\deg_{j}g$ and
$\frac{x_{j}}{x_{i}}f\in B$.

The name _polymatroidal_ comes from the fact that a polymatroidal basis is the
set of base elements of a discrete polymatroid, phrased in the language of
monomials. An ideal generated by a polymatroidal basis is called a
_polymatroidal ideal._ The structure of a polymatroidal basis is actually more
symmetric than the definition reveals.

######  Theorem 1.2 (Symmetric exchange property).

Let $B$ be a polymatroidal base, and suppose $f,g\in B$ with
$\deg_{i}f>\deg_{i}g$. Then there is a $j$ with $\deg_{j}f<\deg_{j}g$ such
that $\frac{x_{j}}{x_{i}}f,\frac{x_{i}}{x_{j}}g\in B$.

For a proof of this theorem, as well as a more extensive background on
discrete polymatroids, see [5].

To a polymatroidal basis $B$ we can associate the toric ring $\mathbb{K}[B]$.
This is the subring of $\mathbb{K}[X]$ generated by the monomials in $B$. In
the language of discrete polymatroids $\mathbb{K}[B]$ is also known as the
base ring of $B$, or in the language of monomial ideals as the fiber ring of
the ideal generated by $B$. If $B=\\{f_{1},\ldots,f_{m}\\}$, let
$Y=\\{y_{1},\ldots,y_{m}\\}$ and define a homomorphism
$\varphi:\mathbb{K}[Y]\to\mathbb{K}[X]$ by $\varphi(y_{i})=f_{i}$. Then
$\mathcal{J}_{B}:=\ker\varphi$ is called the _toric ideal of $B$_, and
$\mathbb{K}[B]\cong\mathbb{K}[Y]/\mathcal{J}_{B}$. It is a well known fact
that such an ideal is generated by binomials, more precisely by differences of
monomials. If we take two variables $y_{r},y_{s}\in Y$, Theorem 1.2 induces
binomials of degree two in $\mathcal{J}_{B}$ in the following way. Say
$\varphi(y_{r})=f$ and $\varphi(y_{s})=g$. Assuming $f\neq g$ Theorem 1.2
tells us that there are $i$ and $j$ such that $\deg_{i}f>\deg_{i}g$,
$\deg_{j}f<\deg_{j}g$, and $\frac{x_{j}}{x_{i}}f,\frac{x_{i}}{x_{j}}g\in B$.
Then there are some $y_{t},y_{u}\in Y$ so that
$\varphi(y_{t})=\frac{x_{j}}{x_{i}}f$ and
$\varphi(y_{u})=\frac{x_{i}}{x_{j}}g$ and
$y_{r}y_{s}-y_{t}y_{u}\in\mathcal{J}_{B}$. The elements in $\mathcal{J}_{B}$
of this type are called _symmetric exchange relations_. To be precise,
$y_{r}y_{s}-y_{t}y_{u}$ is a symmetric exchange relation if there are $i$ and
$j$ such that

$\displaystyle\deg_{i}\varphi(y_{r})>\deg_{i}\varphi(y_{s}),\ \
\deg_{j}\varphi(y_{r})<\deg_{j}\varphi(y_{s}),$
$\displaystyle\varphi(y_{t})=\frac{x_{j}}{x_{i}}\varphi(y_{r}),\ \mbox{ and
}\varphi(y_{u})=\frac{x_{i}}{x_{j}}\varphi(y_{s}).$

######  Conjecture 1.3 (White 1980, Herzog-Hibi 2002).

The toric ideal $\mathcal{J}_{B}$ of a polymatroidal basis $B$ is generated by
the symmetric exchange relations.

This conjecture was originally posed in [9] for matroids, which correspond to
squarefree polymatroidal bases, and for discrete polymatroids in [5]. Since
the symmetric exchange relations are quadratic it is natural to ask whether
the algebra $\mathbb{K}[B]$ is Koszul, and if the toric ideal has a quadratic
Gröbner basis. Recall that a $\mathbb{K}$-algebra $R$ is Koszul if
$\mathbb{K}$ has a linear free resolution over $R$. Every Koszul algebra is
defined by an ideal generated in degree two, and every algebra defined by an
ideal with a quadratic Gröbner basis is Koszul.

######  Example 1.4.

The set
$B=\\{{x}_{1}{x}_{2}{x}_{3},{x}_{1}{x}_{3}^{2},{x}_{2}^{2}{x}_{3},{x}_{2}{x}_{3}^{2},{x}_{2}{x}_{3}{x}_{4},{x}_{3}^{2}{x}_{4}\\}$
is a polymatroidal basis. The toric ideal $\mathcal{J}_{B}$ is the kernel of
the homomorphism $\varphi:\mathbb{K}[X]\to\mathbb{K}[Y]$ defined by

$\displaystyle\varphi(y_{1})={x}_{1}{x}_{2}{x}_{3},\ \
\varphi(y_{2})=x_{1}x_{3}^{2},\ \ \varphi(y_{3})=x_{2}^{2}x_{3},$
$\displaystyle\varphi(y_{4})=x_{2}x_{3}^{2},\ \
\varphi(y_{5})=x_{2}x_{3}x_{4},\ \ \varphi(y_{6})=x_{3}^{2}x_{4}.$

A computation in Macaulay2 [4] gives that

$\mathcal{J}_{B}=(y_{1}y_{4}-y_{2}y_{3},\ y_{1}y_{6}-y_{2}y_{5},\
y_{3}y_{6}-y_{4}y_{5}).$

This generating set is a Gröbner basis w. r. t. the Lex order. We also check
that the generators are symmetric exchange relations. The fact that
$\deg_{1}(x_{1}x_{3}^{2})>\deg_{1}(x_{2}^{2}x_{3})$,
$\deg_{2}(x_{1}x_{3}^{2})<\deg_{2}(x_{2}^{2}x_{3})$, and

$\frac{x_{2}}{x_{1}}x_{1}x_{3}^{3}=x_{2}x_{3}^{2},\ \
\frac{x_{1}}{x_{2}}x_{2}^{2}x_{3}=x_{1}x_{2}x_{3}\ \ \mbox{both belongs to }B$

gives rise to the symmetric exchange relation $y_{2}y_{3}-y_{1}y_{4}$.
Moreover, $\deg_{1}(x_{1}x_{2}x_{3})>\deg_{1}(x_{3}^{2}x_{4})$,
$\deg_{4}(x_{1}x_{2}x_{3})<\deg_{4}(x_{3}^{2}x_{4})$, and

$\frac{x_{4}}{x_{1}}x_{1}x_{2}x_{3}=x_{2}x_{3}x_{4},\ \
\frac{x_{1}}{x_{4}}x_{3}^{2}x_{4}=x_{1}x_{3}^{2}\ \ \mbox{both belongs to }B$

gives the symmetric exchange relation $y_{1}y_{6}-y_{2}y_{5}$. Last,
$y_{3}y_{6}-y_{4}y_{5}$ is a symmetric exchange relation which comes from the
fact that $\deg_{2}(x_{2}^{2}x_{3})>\deg_{2}(x_{3}^{2}x_{4})$,
$\deg_{3}(x_{2}^{2}x_{3})<\deg_{3}(x_{3}^{2}x_{4})$, and

$\frac{x_{3}}{x_{2}}x_{2}^{2}x_{3}=x_{2}x_{3}^{2},\ \
\frac{x_{2}}{x_{3}}x_{3}^{2}x_{4}=x_{2}x_{3}x_{4}\ \ \mbox{both belongs to
}B.\qed$

We finish this section with a lemma regarding the symmetric exchange
relations, which we will need later.

######  Lemma 1.5.

Let $B$ be a polymatroidal basis and let $\mathcal{E}_{B}$ be the ideal
generated by the symmetric exchange relations. Suppose we have
$y_{r},y_{s},y_{t},y_{u}$ such that
$\varphi(y_{t})=\frac{x_{j}}{x_{i}}\varphi(y_{r})$ and
$\varphi(y_{u})=\frac{x_{i}}{x_{j}}\varphi(y_{s})$ for some $i$ and $j$. Then
$y_{r}y_{s}-y_{t}y_{u}\in\mathcal{E}_{B}$.

###### Proof.

If $\deg_{i}\varphi(y_{r})>\deg_{i}\varphi(y_{s})$ and
$\deg_{j}\varphi(y_{r})<\deg_{j}\varphi(y_{s})$ then $y_{r}y_{s}-y_{t}y_{u}$
is a symmetric exchange relation.

Suppose $\deg_{i}\varphi(y_{r})>\deg_{i}\varphi(y_{s})$ and
$\deg_{j}\varphi(y_{r})\geq\deg_{j}\varphi(y_{s})$. Since $B$ is polymatroidal
there is some index $k$ such that
$\deg_{k}\varphi(y_{r})<\deg_{k}\varphi(y_{s})$ and
$\frac{x_{k}}{x_{i}}\varphi(y_{r})$, $\frac{x_{i}}{x_{k}}\varphi(y_{s})\in B$.
Then there are some $y_{v},y_{w}$ such that
$\varphi(y_{v})=\frac{x_{k}}{x_{i}}\varphi(y_{r})$ and
$\varphi(y_{w})=\frac{x_{i}}{x_{k}}\varphi(y_{s})$. It follows that
$y_{r}y_{s}-y_{v}y_{w}\in\mathcal{E}_{B}$. We also have
$y_{t}y_{u}-y_{v}y_{w}\in\mathcal{E}_{B}$ because

$\deg_{j}\varphi(y_{t})=\deg_{j}\varphi(y_{r})+1>\deg_{j}\varphi(y_{s})-1=\deg_{j}\varphi(y_{u}),$
$\deg_{k}\varphi(y_{t})=\deg_{k}\varphi(y_{r})<\deg_{k}\varphi(y_{s})=\deg_{k}\varphi(y_{u}),$
$\varphi(y_{v})=\frac{x_{k}}{x_{i}}\varphi(y_{r})=\frac{x_{k}}{x_{i}}\frac{x_{i}}{x_{j}}\varphi(y_{t})=\frac{x_{k}}{x_{j}}\varphi(y_{t})\
\mbox{and similarily}\ \varphi(y_{w})=\frac{x_{j}}{x_{k}}\varphi(y_{u})$

Then
$y_{r}y_{s}-y_{t}y_{u}=(y_{r}y_{s}-y_{v}y_{w})-(y_{t}y_{u}-y_{v}y_{w})\in\mathcal{E}_{B}$.

Suppose instead $\deg_{i}\varphi(y_{r})\leq\deg_{i}\varphi(y_{s})$ and
$\deg_{j}\varphi(y_{r})<\deg_{j}\varphi(y_{s})$. Since $B$ is polymatroidal,
$\deg_{j}\varphi(y_{s})>\deg_{j}\varphi(y_{r})$ implies that there is some
index $k$ such that $\deg_{k}\varphi(y_{s})<\deg_{k}\varphi(y_{r})$ and
$\frac{x_{k}}{x_{j}}\varphi(y_{s}),\frac{x_{j}}{x_{k}}\varphi(y_{s})\in B$.
Then there are $y_{v}$ and $y_{w}$ such that
$\varphi(y_{v})=\frac{x_{k}}{x_{j}}\varphi(y_{s})$ and
$\varphi(y_{w})=\frac{x_{j}}{x_{k}}\varphi(y_{r})$, and we have
$y_{s}y_{r}-y_{v}y_{w}\in\mathcal{E}_{B}$. In a similar way as in the previous
case one can verify that $\deg_{i}\varphi(y_{u})>\deg_{i}\varphi(y_{t})$,
$\deg_{k}\varphi(y_{u})<\deg_{k}\varphi(y_{t})$,
$\varphi(y_{v})=\frac{x_{k}}{x_{i}}\varphi(y_{u})$ and
$\varphi(y_{w})=\frac{x_{i}}{x_{k}}\varphi(y_{t})$, so that
$y_{u}y_{t}-y_{v}y_{w}\in\mathcal{E}_{B}$. Then
$y_{r}y_{s}-y_{t}y_{u}=(y_{r}y_{s}-y_{v}y_{w})-(y_{t}y_{u}-y_{v}y_{w})\in\mathcal{E}_{B}$.

Last we consider the case $\deg_{i}\varphi(y_{r})\leq\deg_{i}\varphi(y_{s})$
and $\deg_{j}\varphi(y_{r})\geq\deg_{j}\varphi(y_{s})$. In this case the
binomial $y_{t}y_{u}-y_{r}y_{s}$ is a symmetric exchange relation, as
$\varphi(y_{r})=\frac{x_{i}}{x_{j}}\varphi(y_{t})$,
$\varphi(y_{s})=\frac{x_{j}}{x_{i}}\varphi(y_{u})$,
$\deg_{i}\varphi(y_{t})<\deg_{i}\varphi(y_{u})$, and
$\deg_{j}\varphi(y_{t})>\deg_{j}\varphi(y_{u})$. We have now seen that
$y_{r}y_{s}-y_{t}y_{u}\in\mathcal{E}_{B}$ in all possible cases.∎

##  2\. The Strong Exchange Property

It was proved in [5] that Conjecture 1.3 holds for discrete polymatroids with
the so called _strong exchange property_.

######  Definition 2.1.

A set $B$ of monomials in $\mathbb{K}[X]$ is called a basis with the _strong
exchange property (SEP)_ if all the monomials in $B$ are of the same degree
and if $f,g\in B$ with $\deg_{i}f>\deg_{i}g$ and $\deg_{j}f<\deg_{j}g$, for
some $i$ and $j$, then $\frac{x_{j}}{x_{i}}f\in B$.

Notice that we will also have $\frac{x_{i}}{x_{j}}g\in B$ in the above
definition.

######  Theorem 2.2 (Herzog-Hibi 2002).

If $B$ is a basis with the SEP then the toric ideal $\mathcal{J}_{B}$ is
generated by the symmetric exchange relations, and has a quadratic Gröbner
basis.

We say that a monomial ideal has the SEP if it is generated by a basis with
the SEP. Every basis with the SEP is polymatroidal, but the converse does not
hold. It was proved in [6] that bases with the SEP are isomorphic to bases of
Veronese type. In Theorem 2.3 we make this characterization a bit more
explicit. For a basis $B$ with the SEP, let $\max_{B}(i)=\max\\{\deg_{i}(f)\
|\ f\in B\\}$ and $\min_{B}(i)=\min\\{\deg_{i}(f)\ |\ f\in B\\}$.

######  Theorem 2.3.

Let $B$ be a basis with the SEP of monomials of degree $d$. Then

$B=\left\\{x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}\ \Big{|}\
\sum_{i=1}^{n}\alpha_{i}=d,\
{\min}_{B}(i)\leq\alpha_{i}\leq{\max}_{B}(i)\right\\}$

###### Proof.

We begin by proving the following claim: For any $i$ and $j$ there is a
monomial $f\in B$ with $\deg_{i}f=\min_{B}(i)$ and $\deg_{j}f=\max_{B}(j)$. To
prove this, let $f$ be a monomial in $B$ such that $\deg_{i}f=\min_{B}(i)$ and
$\deg_{j}f$ is as high as possible for a monomial $f$ with
$\deg_{i}f=\min_{B}(i)$. If $\deg_{j}f<\max_{B}(j)$, take $g\in B$ with
$\deg_{j}g=\max_{B}(j)$. Then $\deg_{j}g>\deg_{j}f$ and there is a $k$ with
$\deg_{k}g<\deg_{k}f$ and $\frac{x_{j}}{x_{k}}f\in B$. But this contradicts
our choice of $f$, and we can conclude that $\deg_{j}f=\max_{B}(j)$.

A consequence of the claim is that if $f\in B$ and $\deg_{i}f>\min_{B}(i)$ and
$\deg_{j}f<\max_{B}(j)$ we have $\frac{x_{j}}{x_{i}}f\in B$. Now let
$x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}$ be a monomial of degree $d$ such
that $\min_{B}(i)\leq\alpha_{i}\leq\max_{B}(i)$ for each $i$. Take any
monomial $x_{1}^{\beta_{1}}\cdots x_{n}^{\beta_{n}}\in B$. If
$x_{1}^{\beta_{1}}\cdots x_{n}^{\beta_{n}}\neq x_{1}^{\alpha_{1}}\cdots
x_{n}^{\alpha_{n}}$ then $\beta_{i}>\alpha_{i}$ and $\beta_{j}<\alpha_{j}$ for
some $i$ and $j$, say $i=1$ and $j=2$. Then $\beta_{1}>\min_{B}(1)$ and
$\beta_{2}<\max_{B}(2)$, and we have
$x_{1}^{\beta_{1}-1}x_{2}^{\beta_{2}+1}x_{3}^{\beta_{3}}\cdots
x_{n}^{\beta_{n}}\in B$. If
$x_{1}^{\beta_{1}-1}x_{2}^{\beta_{2}+1}x_{3}^{\beta_{3}}\cdots
x_{n}^{\beta_{n}}\neq x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}$ we repeat
the same argument. Eventually we will get that $x_{1}^{\alpha_{1}}\cdots
x_{n}^{\alpha_{n}}\in B$, which is what we wanted to prove. ∎

We define the product of two polymatroidal bases $B_{1}$ and $B_{2}$ as

$B_{1}B_{2}=\\{b_{1}b_{2}\ |\ b_{1}\in B_{1},b_{2}\in B_{2}\\}.$

If we consider $B_{1}$ and $B_{2}$ as generating sets of ideals $I_{1}$ and
$I_{2}$, then clearly $B_{1}B_{2}$ is a generating set for the ideal
$I_{1}I_{2}$. A nice feature of polymatroidal bases, proved in [2], is that
their products are again polymatroidal. Products of bases with the SEP does
not necessarily have the SEP. For example
$\\{x_{1},x_{2}\\}\\{x_{3},x_{4}\\}=\\{x_{1}x_{3},x_{1}x_{4},x_{2}x_{3},x_{2}x_{4}\\}$
does not have the SEP. However, powers of bases with the SEP do have the SEP.

######  Proposition 2.4.

If $B$ has the SEP, so does $B^{k}$ for any positive integer $k$.

###### Proof.

By Theorem 2.3

$B=\Big{\\{}x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}\ |\
{\min}_{B}(i)\leq\alpha_{i}\leq{\max}_{B}(i),\sum_{i=1}^{n}\alpha_{i}=d\Big{\\}}.$

Let

$\mathcal{M}=\Big{\\{}x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}\ |\
k{\min}_{B}(i)\leq\alpha_{i}\leq
k{\max}_{B}(i),\sum_{i=1}^{n}\alpha_{i}=dk\Big{\\}}$

We can see that $\mathcal{M}$ is a basis with the SEP, and
$B^{k}\subseteq\mathcal{M}$. We shall prove $B^{k}\supseteq\mathcal{M}$. Let
$x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}\in\mathcal{M}$, and write
$\alpha_{i}=k\beta_{i}+r_{i}$ with $0\leq r_{i}<k$. Since
$\sum_{i=1}^{n}\alpha_{i}=dk$, the number $\sum_{i=1}^{n}r_{i}$ must also be
divisible by $k$. Since $r_{i}<k$ we can factorize $x_{1}^{r_{1}}\cdots
x_{n}^{r_{n}}=M_{1}\cdots M_{k}$ where $M_{1},\ldots M_{k}$ are squarefree
monomials all of the same degree. Then we have a factorization

$x_{1}^{\alpha_{1}}\cdots
x_{n}^{\alpha_{n}}=\prod_{i=1}^{k}(x_{1}^{\beta_{1}}\cdots
x_{n}^{\beta_{n}}M_{i})$

and $x_{1}^{\beta_{1}}\cdots x_{n}^{\beta_{n}}M_{i}\in B$ since

${\min}_{B}(j)\leq\left\lfloor\frac{\alpha_{j}}{k}\right\rfloor\leq\deg_{j}(x_{1}^{\beta_{1}}\cdots
x_{n}^{\beta_{n}}M_{i})\leq\left\lceil\frac{\alpha_{j}}{k}\right\rceil\leq{\max}_{B}(j).$

We have now proved that $x_{1}^{\alpha_{1}}\cdots a_{n}^{\alpha_{n}}\in
B^{k}$, and hence $B^{k}$ has the SEP. ∎

The main results of this paper is Theorem 2.5 which describes the structure of
the toric ring $\mathbb{K}[B]$ when $B$ is a product of bases with the SEP. In
particular, we show that Conjecture 1.3 holds in this case.

For two graded $\mathbb{K}$-algebras $R=\bigoplus_{i\geq 0}R_{i}$ and
$S=\bigoplus_{i\geq 0}S_{i}$ we let $R\circ S$ denote their _Segre product_ ,
i. e. $R\circ S=\bigoplus_{i\geq 0}R_{i}\otimes_{\mathbb{K}}S_{i}$.

######  Theorem 2.5.

Let $B=B_{1}\cdots B_{s}$ where $B_{1},\ldots,B_{s}$ are bases with the SEP.
Then

  1. (1)

$\mathcal{J}_{B}$ is generated by symmetric exchange relations, and

  2. (2)

$\mathbb{K}[B]\cong\mathbb{K}[B_{1}]\circ\dots\circ\mathbb{K}[B_{s}]/L$ where
$L$ is generated by binomials of degree one.

The theorem is proved in Section 3. Here we should point out that Conjecture
1.3 is still open, since not every polymatroidal basis is the product of bases
with the SEP. Consider for example the polymatroidal basis

$B=\\{x_{1}x_{2},x_{1}x_{3},x_{2}x_{3},x_{2}x_{4},x_{3}x_{4}\\}.$

It is not of the form in Theorem 2.3, so it does not have the SEP. If $B$
would be a product of two bases, it would be the product of two sets of
variables, but one easily checks that this is not the case.

In the proof of Theorem 2.5 we will need the following lemma.

######  Lemma 2.6.

Let $B$ be a basis with the SEP. Suppose
$f,g,\frac{x_{i}}{x_{j}}f,\frac{x_{k}}{x_{\ell}}g\in B$. Then there is an
index $m$ such that
$\frac{x_{i}}{x_{m}}f,\frac{x_{\ell}}{x_{m}}f,\frac{x_{m}}{x_{\ell}}g\in B$.

###### Proof.

If $\frac{x_{i}}{x_{\ell}}f\in B$ we are done, as we can choose $m=\ell$.
Suppose $\frac{x_{i}}{x_{\ell}}f\notin B$. Since $\frac{x_{i}}{x_{j}}f\in B$
we have $\deg_{i}f<\max_{B}(i)$. Then $\frac{x_{i}}{x_{\ell}}f\notin B$
implies $\deg_{\ell}f=\min_{B}(\ell)$. As $\frac{x_{k}}{x_{\ell}}g\in B$ we
have $\deg_{\ell}g>\min(\ell)=\deg_{\ell}f$. Then there is an $m$ such that
$\deg_{m}g<\deg_{m}f$ and $\frac{x_{m}}{x_{\ell}}g,\frac{x_{\ell}}{x_{m}}f\in
B$. Also, $\deg_{m}f>\min_{B}(m)$ and $\deg_{i}f<\max_{B}(i)$ gives
$\frac{x_{i}}{x_{m}}f\in B$. ∎

##  3\. Proof of Theorem 2.5

Let $B_{1},\ldots,B_{s}$ be bases in $\mathbb{K}[X]$ with the SEP, and let
$B=B_{1}\cdots B_{s}$. We let $Y$ be the set of $\prod_{j=1}^{s}|B_{j}|$
variables $y_{v}$ indexed by vectors $v=(f_{1},\ldots,f_{s})$ where $f_{j}\in
B_{j}$. We define our homomorphism $\varphi:\mathbb{K}[Y]\to\mathbb{K}[X]$ so
that $y_{v}$ maps to the product of the entries in the vector $v$. For a
monomial $y_{v_{1}}\cdots y_{v_{d}}\in\mathbb{K}[Y]$ we associate a $d\times
s$ matrix with row vectors $v_{1},\ldots,v_{d}$. The matrix associated to a
monomial is unique up to permutations of the rows, and
$\varphi(y_{v_{1}}\cdots y_{v_{d}})$ is the product of all the entries in this
matrix.

Notice that the toric ideal $\mathcal{J}_{B}=\ker\varphi$, as we defined it
here, may contain binomials of degree one, as it can happen that
$\varphi(y_{v})=\varphi(y_{w})$ even though $v\neq w$. Let $\mathcal{L}_{B}$
denote the ideal generated by the binomials of degree one in
$\mathcal{J}_{B}$. Let $\mathcal{E}_{B}$ be the ideal generated by the
symmetric exchange relations in $\mathcal{J}_{B}$. Also, let $\mathcal{P}_{B}$
be the ideal generated by the binomials $F-G\in\mathcal{J}_{B}$ such that the
matrices of $F$ and $G$ differ in at most one column (up to a permutation of
the rows). We will see that
$\mathcal{J}_{B}=\mathcal{E}_{B}+\mathcal{L}_{B}=\mathcal{P}_{B}+\mathcal{L}_{B}$.
This proves that $\mathcal{J}_{B}$ is generated by the symmetric exchange
relations, as the given generating set of $\mathcal{E}_{B}$ will still
correspond to symmetric exchange relations after reducing modulo
$\mathcal{L}_{B}$. The fact that
$\mathcal{J}_{B}=\mathcal{P}_{B}+\mathcal{L}_{B}$ proves the second part of
Theorem 2.5, as

$\frac{\mathbb{K}[Y]}{\mathcal{P}_{B}}\cong\frac{\mathbb{K}[Y_{1}]}{\mathcal{J}_{B_{1}}}\circ\dots\circ\frac{\mathbb{K}[Y_{s}]}{\mathcal{J}_{B_{s}}}.$

Now it remains to prove
$\mathcal{J}_{B}=\mathcal{E}_{B}+\mathcal{L}_{B}=\mathcal{P}_{B}+\mathcal{L}_{B}$,
or equivalently
$\mathcal{J}_{B}\subseteq(\mathcal{E}_{B}+\mathcal{L}_{B})\cap(\mathcal{P}_{B}+\mathcal{L}_{B})$.

######  Lemma 3.1.

Let $F$ be a monomial in $\mathbb{K}[Y]$, and let $(f_{ij})$ be the associated
matrix. Let $F^{\prime}$ be the monomial in $\mathbb{K}[Y]$ with the
associated matrix $(f^{\prime}_{ij})$ obtained from $(f_{ij})$ by permuting
the elements in one column. Then
$F-F^{\prime}\in\mathcal{E}_{B}\cap\mathcal{P}_{B}$.

###### Proof.

It is clear from the definition of $\mathcal{P}_{B}$ that
$F-F^{\prime}\in\mathcal{P}_{B}$, so we need to prove that
$F-F^{\prime}\in\mathcal{E}_{B}$. As any permutation can by performed as a
sequence of transpositions, it is enough to consider a transposition of
elements in a column. Without loss of generality, we assume that
$f^{\prime}_{11}=f_{21}$, $f^{\prime}_{21}=f_{11}$, and otherwise
$f^{\prime}_{ij}=f_{ij}$. We define $u_{i}=(f_{i1},\ldots,f_{is})$ and
$v_{i}=(f^{\prime}_{i1},\ldots,f^{\prime}_{is})$, so that $F=y_{u_{1}}\cdots
y_{u_{d}}$ and $F^{\prime}=y_{v_{1}}\cdots y_{v_{d}}$. Then

$F-F^{\prime}=y_{u_{1}}\cdots y_{u_{d}}-y_{v_{1}}\cdots
y_{v_{d}}=(y_{u_{1}}y_{u_{2}}-y_{v_{1}}y_{v_{2}})y_{u_{3}}\cdots y_{u_{d}},$

and we want to prove that
$y_{u_{1}}y_{u_{2}}-y_{v_{1}}y_{v_{2}}\in\mathcal{E}_{B}$. Recall that
$f_{11},f_{21}\in B_{1}$, which is a basis with the SEP. We have

$f_{21}=\frac{x_{a_{1}}x_{a_{2}}}{x_{b_{1}}x_{b_{2}}}\cdots\frac{x_{a_{k}}}{x_{b_{k}}}f_{11}$

for some $a_{1},\ldots,a_{k},b_{1},\ldots b_{k}$, and we may assume
$\\{a_{1},\ldots,a_{k}\\}\cap\\{b_{1},\ldots b_{k}\\}=\emptyset$, so that no
variable occurs both in the numerator and in the denominator. By Theorem 2.3

$f_{11}^{(m)}:=\frac{x_{a_{1}}x_{a_{2}}}{x_{b_{1}}x_{b_{2}}}\cdots\frac{x_{a_{m}}}{x_{b_{m}}}f_{11}\in
B_{1},\ \ m=1,\ldots,k,$

since with this construction $\deg f_{11}^{(m)}=\deg f_{11}$ and

${\min}_{B_{1}}\\!(i)\leq\min(\deg_{i}\\!f_{11},\deg_{i}\\!f_{21})\leq\deg_{i}\\!f_{11}^{(m)}\leq\max(\deg_{i}\\!f_{11},\deg_{i}\\!f_{21})\leq{\max}_{B_{1}}\\!(i).$

In the same way

$f_{21}^{(m)}:=\frac{x_{b_{1}}x_{b_{2}}}{x_{a_{1}}x_{a_{2}}}\cdots\frac{x_{b_{m}}}{x_{a_{m}}}f_{21}\in
B_{1},\ \ m=1,\ldots,k.$

Let

$u_{1}^{(m)}=(f_{11}^{(m)},f_{12},\ldots,f_{1s})\ \mbox{and}\
u_{2}^{(m)}=(f_{21}^{(m)},f_{22},\ldots,f_{2s}),\ \mbox{for}\ m=1,\ldots,k$

and notice that $u_{1}^{(k)}=v_{1}$ and $u_{2}^{(k)}=v_{2}$. By Lemma 1.5

$y_{u_{1}}y_{u_{2}}=y_{u_{1}^{(1)}}y_{u_{2}^{(1)}}=y_{u_{1}^{(2)}}y_{u_{2}^{(2)}}=\ldots=y_{u_{1}^{(k)}}y_{u_{2}^{(k)}}=y_{v_{1}}y_{v_{2}}\
\mbox{in}\ \mathbb{K}[Y]/\mathcal{E}_{B},$

and it follows that $F=F^{\prime}$ in $\mathbb{K}[Y]/\mathcal{E}_{B}$. ∎

######  Lemma 3.2.

Let $F$ and $G$ be monomials in $\mathbb{K}[Y]$ such that their matrices are
identical in the first $m<s$ columns, and $F-G\in\mathcal{J}_{B}$. If
$\mathcal{J}_{B^{\prime}}=\mathcal{E}_{B^{\prime}}+\mathcal{L}_{B^{\prime}}=\mathcal{P}_{B^{\prime}}+\mathcal{L}_{B^{\prime}}$,
where $B^{\prime}=B_{m+1}\cdots B_{s}$, then
$F-G\in(\mathcal{E}_{B}+\mathcal{L}_{B})\cap(\mathcal{P}_{B}+\mathcal{L}_{B})$.

The analogous statement is also true if the matrices of $F$ and $G$ are
identical in the last $m$ columns, or more generally in any subset of the
columns. The proof in this situation follows the same recipe.

###### Proof.

As the first $m$ columns of the matrices $(f_{ij})$ and $(g_{ij})$
representing $F$ and $G$ are identical, and $F-G\in\mathcal{J}_{B}$, we have

$\prod_{\begin{subarray}{c}1\leq i\leq d\\\ m<j\leq
s\end{subarray}}f_{ij}=\prod_{\begin{subarray}{c}1\leq i\leq d\\\ m<j\leq
s\end{subarray}}g_{ij}$

which corresponds to a relation in $\mathcal{J}_{B^{\prime}}$. Then there is a
monomial $H\in\mathbb{K}[Y]$ such that $G=H$ in
$\mathbb{K}[Y]/((\mathcal{E}_{B}+\mathcal{L}_{B})\cap(\mathcal{P}_{B}+\mathcal{L}_{B}))$
and $H$ is identical to $F$ and $G$ in the first $m$ columns, and identical to
$F$ in the last $s-m$ columns after possibly permuting the rows. Then we can
apply Lemma 3.1 and get that $G=H=F$ in
$\mathbb{K}[Y]/((\mathcal{E}_{B}+\mathcal{L}_{B})\cap(\mathcal{P}_{B}+\mathcal{L}_{B}))$.
∎

######  Lemma 3.3.

Let $F$ be a monomial in $\mathbb{K}[Y]$ such that
$\frac{x_{1}}{x_{2}}\varphi(F)\in B^{d}$. Then there are monomials
$F^{\prime}$ and $H$ such that
$F-F^{\prime}\in\mathcal{E}_{B}\cap\mathcal{P}_{B}$,
$\varphi(H)=\frac{x_{1}}{x_{2}}\varphi(F^{\prime})$, and the matrices
associated to $F^{\prime}$ and $H$ differ in at most one entry in each column.

###### Proof.

Let $(f_{ij})$ be the matrix associated to $F$. Since
$\frac{x_{1}}{x_{2}}\varphi(F)\in B^{d}$ there are $h_{ij}$’s, such that

$\frac{x_{1}}{x_{2}}\varphi(F)=\prod_{\begin{subarray}{c}1\leq i\leq d\\\
1\leq j\leq s\end{subarray}}h_{ij},\ \ \ h_{ij}\in B_{j}.$

For each pair $i,j$ there is a multiset
$\Lambda_{ij}\subset\\{1,\ldots,n\\}^{2}$ such that

$h_{ij}=\Big{(}\prod_{(a,b)\in\Lambda_{ij}}\frac{x_{a}}{x_{b}}\Big{)}f_{ij}.$

The choice of the $h_{ij}$’s is not unique, and the goal is the choose them so
that for each $j$ there is only one $i$ for which $\Lambda_{ij}$ in nonempty.
First note that we can choose $\Lambda_{ij}$ so that for each
$(a,b)\in\Lambda_{ij}$ it holds that

$\deg_{a}f_{ij}<\deg_{a}h_{ij}\ \text{and}\ \deg_{b}f_{ij}>\deg_{b},h_{ij}.$

It follows that $\frac{x_{a}}{x_{b}}f_{ij}\in B_{j}$, since $B_{j}$ has the
SEP. As

$\Big{(}\prod_{\begin{subarray}{c}1\leq i\leq d\\\ 1\leq j\leq
s\end{subarray}}\prod_{(a,b)\in\Lambda_{ij}}\frac{x_{a}}{x_{b}}\Big{)}\varphi(F)=\prod_{\begin{subarray}{c}1\leq
i\leq d\\\ 1\leq j\leq
s\end{subarray}}\prod_{(a,b)\in\Lambda_{ij}}\frac{x_{a}}{x_{b}}f_{ij}=\prod_{\begin{subarray}{c}1\leq
i\leq d\\\ 1\leq j\leq s\end{subarray}}h_{ij}=\frac{x_{1}}{x_{2}}\varphi(F)$

we have

$\Big{(}\prod_{\begin{subarray}{c}1\leq i\leq d\\\ 1\leq j\leq
s\end{subarray}}\prod_{(a,b)\in\Lambda_{ij}}\frac{x_{a}}{x_{b}}\Big{)}=\frac{x_{1}}{x_{2}}$

and we may order the factors $\frac{x_{a}}{x_{b}}$ in the left hand side so
that

(1) $\Big{(}\prod_{\begin{subarray}{c}1\leq i\leq d\\\ 1\leq j\leq
s\end{subarray}}\prod_{(a,b)\in\Lambda_{ij}}\frac{x_{a}}{x_{b}}\Big{)}=\frac{x_{1}}{x_{a_{1}}}\frac{x_{a_{1}}}{x_{a_{2}}}\frac{x_{a_{2}}}{x_{a_{3}}}\cdots\frac{x_{a_{k-1}}}{x_{a_{k}}}\frac{x_{a_{k}}}{x_{2}}$

Each factor in the right hand side still corresponds to an index pair in some
$\Lambda_{ij}$. Now, if there are two different values of $i$ such that
$\Lambda_{i1}$ is nonempty we do the following. In the right hand side of (1)
consider the leftmost and rightmost factors corresponding to index pairs from
any $\Lambda_{i1}$. Say for instance that it is $(a_{1},a_{2})\in\Lambda_{11}$
and $(a_{5},a_{6})\in\Lambda_{21}$. Then

$f_{11},f_{21},\frac{x_{a_{1}}}{x_{a_{2}}}f_{11},\ \text{and}\
\frac{x_{a_{5}}}{x_{a_{6}}}f_{21}\ \mbox{all belong to}\ B_{1}.$

By Lemma 2.6 there is an $m$ such that

$\frac{x_{a_{1}}}{x_{m}}f_{11},\frac{x_{a_{6}}}{x_{m}}f_{11},\ \text{and}\
\frac{x_{m}}{x_{a_{6}}}f_{21}\in B_{1}.$

Now we define $F^{\prime}$ as the matrix $(f^{\prime}_{ij})$ with
$f^{\prime}_{ij}=f_{ij}$ except
$f^{\prime}_{11}=\frac{x_{a_{6}}}{x_{m}}f_{11}$ and
$f^{\prime}_{21}=\frac{x_{m}}{x_{a_{6}}}f_{21}$. Notice that
$F^{\prime}-F\in\mathcal{E}_{B}\cap\mathcal{P}_{B}$. In $\Lambda_{11}$ we
replace $(a_{1},a_{2})$ by $(a_{1},a_{6})$, and we remove
$(a_{2},a_{3}),(a_{3},a_{4}),(a_{4},a_{5}),$ and $(a_{5},a_{6})$ from their
corresponding $\Lambda_{ij}$’s. This means that
$\Lambda_{11}=\\{(a_{1},a_{6})\\}$ and $\Lambda_{i1}=\emptyset$ for $i>1$. We
also redefine the $h_{ij}$’s as

$h_{ij}=\Big{(}\prod_{(a,b)\in\Lambda_{ij}}\frac{x_{a}}{x_{b}}\Big{)}f^{\prime}_{ij}.$

Notice that we still have $h_{ij}\in B_{j}$, in particular

$h_{11}=\frac{x_{a_{1}}}{x_{a_{6}}}f^{\prime}_{11}=\frac{x_{a_{1}}}{x_{a_{6}}}\frac{x_{a_{6}}}{x_{m}}f_{11}=\frac{x_{a_{1}}}{x_{m}}f_{11}\in
B_{1}$

and

$h_{i1}=f^{\prime}_{i1}\in B_{1}\ \text{for}\ i>1.$

Now we do the same procedure for $j=2$, but with $F$ replaced by $F^{\prime}$
and the right hand side of (1) replaced by

$\frac{x_{1}}{x_{a_{1}}}\frac{x_{a_{1}}}{x_{a_{6}}}\frac{x_{a_{6}}}{x_{a_{7}}}\cdots\frac{x_{a_{k-1}}}{x_{a_{k}}}\frac{x_{a_{k}}}{x_{2}}.$

We continue with this for all values of $j$. Finally we end up with $h_{ij}$’s
that for each $j$ there is at most one $i$ for which $h_{ij}\neq
f^{\prime}_{ij}$. Then $H$ given by the matrix $(h_{ij})$ together with
$F^{\prime}$ has the desired properties. ∎

Now we are ready to prove that
$\mathcal{J}_{B}\subseteq(\mathcal{E}_{B}+\mathcal{L}_{B})\cap(\mathcal{P}_{B}+\mathcal{L}_{B})$.
Suppose we have monomials $F$ and $G$ of degree $d\geq 2$ in $\mathbb{K}[Y]$
such that their difference is in $\mathcal{J}_{B}$. We shall prove that $F=G$
in
$\mathbb{K}[Y]/((\mathcal{E}_{B}+\mathcal{L}_{B})\cap(\mathcal{P}_{B}+\mathcal{L}_{B}))$
by induction over $s$. The base case $s=1$ is clear, as then $B=B_{1}$ has the
SEP, and the matrices have only one column. Now suppose the statement is true
for any product of fewer than $s$ bases with the SEP. The idea of the proof is
the following. Let $(f_{ij})$ and $(g_{ij})$ be the matrices corresponding to
$F$ and $G$. Say we are in the special situation where
$\prod_{i=1}^{d}f_{i1}=\prod_{i=1}^{d}g_{i1}.$ Then we also have
$\prod_{\begin{subarray}{c}1\leq i\leq d\\\ 2\leq j\leq
s\end{subarray}}f_{ij}=\prod_{\begin{subarray}{c}1\leq i\leq d\\\ 2\leq j\leq
s\end{subarray}}g_{ij}$. Let $H$ be the monomial in $\mathbb{K}[Y]$ associated
to the matrix

$\begin{pmatrix}g_{11}&f_{12}&\cdots&f_{1s}\\\ g_{21}&f_{22}&\cdots&f_{2s}\\\
\vdots&\vdots&&\vdots\\\ g_{d1}&f_{d2}&\cdots&f_{ds}\end{pmatrix}$

We have
$\mathcal{J}_{B^{\prime}}=(\mathcal{E}_{B^{\prime}}+\mathcal{L}_{B^{\prime}})\cap(\mathcal{P}_{B^{\prime}}+\mathcal{L}_{B^{\prime}})$
by the induction hypothesis. By Lemma 3.2 we have $H=G$ in
$\mathbb{K}[Y]/((\mathcal{E}_{B}+\mathcal{L}_{B})\cap(\mathcal{P}_{B}+\mathcal{L}_{B}))$.
If $f_{i1}=g_{i1}$ for each $i$ we are done. If not we can apply the induction
hypothesis and Lemma 3.2 one more time to $F$ and $H$, since they are
identical in the last column. It then follows that $F=H=G$ in
$\mathbb{K}[Y]/((\mathcal{E}_{B}+\mathcal{L}_{B})\cap(\mathcal{P}_{B}+\mathcal{L}_{B}))$.

Now, what if we are not in the special situation with
$\prod_{i=1}^{d}f_{i1}=\prod_{i=1}^{d}g_{i1}$? If
$\prod_{i=1}^{d}f_{i1}\neq\prod_{i=1}^{d}g_{i1}$ then also
$\prod_{\begin{subarray}{c}1\leq i\leq d\\\ 2\leq j\leq
s\end{subarray}}f_{ij}\neq\prod_{\begin{subarray}{c}1\leq i\leq d\\\ 2\leq
j\leq s\end{subarray}}g_{ij}$. Since $B_{2}^{d}\cdots B_{s}^{d}$ is
polymatroidal there are say $x_{1}$ and $x_{2}$ so that

(2) $\deg_{1}\prod_{\begin{subarray}{c}1\leq i\leq d\\\ 2\leq j\leq
s\end{subarray}}f_{ij}<\deg_{1}\prod_{\begin{subarray}{c}1\leq i\leq d\\\
2\leq j\leq s\end{subarray}}g_{ij}\ \text{and}\
\deg_{2}\prod_{\begin{subarray}{c}1\leq i\leq d\\\ 2\leq j\leq
s\end{subarray}}f_{ij}>\deg_{2}\prod_{\begin{subarray}{c}1\leq i\leq d\\\
2\leq j\leq s\end{subarray}}g_{ij}$

and

$\frac{x_{1}}{x_{2}}\prod_{\begin{subarray}{c}1\leq i\leq d\\\ 2\leq j\leq
s\end{subarray}}f_{ij}\in B_{2}^{d}\cdots B_{s}^{d}.$

By Lemma 3.3 we can, after replacing $F$ modulo
$\mathcal{E}_{B}\cap\mathcal{P}_{B}$, find $h_{ij}$’s $1\leq i\leq d$, $2\leq
j\leq s$ so that

$\frac{x_{1}}{x_{2}}\prod_{\begin{subarray}{c}1\leq i\leq d\\\ 2\leq j\leq
s\end{subarray}}f_{ij}=\prod_{\begin{subarray}{c}1\leq i\leq d\\\ 2\leq j\leq
s\end{subarray}}h_{ij},\ \ \ h_{ij}\in B_{j}$

such that for each $j$ there is at most one $i$’s for which $h_{ij}\neq
f_{ij}$.

Because of (2) we also have

$\deg_{1}\prod_{i=1}^{d}f_{i1}>\deg_{1}\prod_{i=1}^{d}g_{i1}\ \text{and}\
\deg_{2},\prod_{i=1}^{d}f_{i1}<\deg_{2},\prod_{i=1}^{d}g_{i1}.$

By Proposition 2.4 $B_{1}^{d}$ has the SEP, and it follows that

$\frac{x_{2}}{x_{1}}\prod_{i=1}^{d}f_{i1}\in B_{1}^{d}.$

Here we can apply Lemma 3.3 once more, to get that

$\frac{x_{2}}{x_{1}}\prod_{i=1}^{d}f_{i1}=\prod_{i=1}^{d}h_{i1},\ \ h_{i1}\in
B_{1}$

where $h_{i1}\neq f_{i1}$ for at most one $i$. Now, let $H$ be the monomial
with the associated matrix $(h_{ij})$, $1\leq i\leq d$, $1\leq j\leq s$. For
each $j$ there is at most one $i$ for which $h_{ij}\neq f_{ij}$. We can use
Lemma 3.1 to, for one $j$ at a time, rearrange the $h_{ij}$’s so that the $i$
where possibly $h_{ij}\neq f_{ij}$ is $i=1$. Since now $F$ and $H$ differ only
in the first row they are equal modulo $\mathcal{L}_{B}$. If
$\prod_{i=1}^{d}h_{i1}\neq\prod_{i=1}^{d}g_{i1}$ we can repeat this process,
now with $H$ and $G$. After finitely many repetitions we will get
$\prod_{i=1}^{d}h_{i1}=\prod_{i=1}^{d}g_{i1}$. Then we have arrived in the
special situation described in the beginning of this proof, and the result
follows by induction.

##  4\. Rees algebras

An object closely related to the toric ring $\mathbb{K}[B]$ is the _Rees
algebra_ of the monomial ideal generated by $B$. In general, the Rees algebra
of an ideal $I\subseteq\mathbb{K}[X]$ is defined as
$\mathcal{R}(I)=\bigoplus_{j\geq 0}I^{j}t^{j}$. If $I=(f_{1},\ldots,f_{m})$ we
have $\mathcal{R}(I)=\mathbb{K}[X][f_{1}t,\ldots,f_{m}t]$. Let
$Y=\\{y_{1},\ldots,y_{m}\\}$ and let $\mathbb{K}[X,Y]$ be the polynomial ring
on the variables $X\cup Y$ with the bigrading $\deg x_{i}=(1,0)$ and $\deg
y_{i}=(0,1)$. We say that an element has degree $(k,*)$ if it has degree
$(k,s)$ for any $s$, and similarly for $(*,k)$. We can present
$\mathcal{R}(I)$ as $\mathbb{K}[X,Y]/\ker\phi$ where
$\phi:\mathbb{K}[X,Y]\to\mathbb{K}[X][t]$ is the homomorphism defined by
$\phi(x_{i})=x_{i}$ and $\phi(y_{i})=f_{i}t$. The defining ideal $\ker\phi$ is
called the _Rees ideal_ of $I$. An ideal $I$ is said to be of _fiber type_ if
its Rees ideal is generated in degrees $(0,*)$ and $(*,1)$.

######  Lemma 4.1 ([8, Lemma 3.2]).

If $I$ has linear free resolution and is of fiber type then its Rees ideal is
generated in degrees $(0,*)$ and $(1,1)$.

Polymatroidal ideals are of fiber type and have linear free resolution, see
[6] and [7], so Lemma 4.1 applies to polymatroidal ideals. If $I$ has the SEP
then its Rees ideal is generated in degrees $(0,2)$ and $(1,1)$, see [8,
Theorem 3.5]. We can now extend this theorem to products of ideals with the
SEP.

######  Theorem 4.2.

The Rees ideal of a product of ideals with the SEP is generated in degrees
$(0,2)$ and $(1,1)$.

###### Proof.

Let $B$ be a product of bases with the SEP, and let $\mathcal{I}$ be the Rees
ideal of the ideal generated by $B$. By Lemma 4.1 $\mathcal{I}$ is generated
in degrees $(0,*)$ and $(1,1)$. The set of elements of degree $(0,*)$ in
$\mathcal{I}$ is precisely the toric ideal $\mathcal{J}_{B}$. Then the result
follows by Theorem 2.5. ∎

As the generators of the Rees ideals in Theorem 4.2 has total degree 2 we
conclude this section with the following question.

######  Question 4.3.

Is the Rees algebra of a product of ideals with the SEP Koszul?

##  5\. Gröbner bases and transversal polymatroidal bases

Polymatroids that are given as products of subsets of $X$ are called
_transversal_. This is a special case of the class of polymatroids considered
in this paper, as subsets of $X$ indeed have the SEP. Theorem 2.5 (2) was
proved for transversal polymatroids in [1, Theorem 3.5], which in this case
says that $\mathbb{K}[B]$ is isomorphic to the Segre product of polynomial
rings modulo an ideal of linear binomials. Moreover [1, Theorem 3.5] states
that $\mathbb{K}[B]$ is Koszul when $B$ is transversal. By Theorem 2.5 (1) we
now also know that White’s conjecture holds for transversal polymatroids.
However, the following questions are still open.

######  Question 5.1.

Does the toric ideal of a transversal polymatroid, or more generally a product
of bases with the SEP, have a quadratic Gröbner basis?

######  Question 5.2.

If $B$ is a product of bases with the SEP, is $\mathbb{K}[B]$ Koszul?

It is not obvious which monomial order to use when searching for a quadratic
Gröbner basis of $\mathcal{J}_{B}$. Let $B=X_{1}\cdots X_{s}$, where
$X_{1},\ldots,X_{s}$ are subsets of $X$. Then $\mathcal{J}_{B}$ is generated
by the so called _Hibi relations_ together with binomials of degree one, see
[1, Proposition 3.7]. The Hibi relations are defined in the following way. We
fix an order of the variables in each $X_{i}$. The orderings do not have to be
compatible with each other. Then we let $Y$ be the set of variables indexed by
integer vectors $\alpha=(\alpha_{1},\ldots,\alpha_{s})$ so that
$1\leq\alpha_{j}\leq|X_{j}|$. The toric ideal $\mathcal{J}_{B}$ is the kernel
of $\varphi:K[Y]\to\mathbb{K}[X]$ where $\varphi(y_{\alpha})$ is defined as
the product of the $\alpha_{1}$-th element of $X_{1}$, the $\alpha_{2}$-th
element of $X_{2}$, and so on. The Hibi relations are all relations
$y_{\alpha}y_{\beta}-y_{\alpha\wedge\beta}y_{\alpha\vee\beta}$ where
$\alpha\wedge\beta=(\max(\alpha_{1},\beta_{1}),\ldots,\max(\alpha_{s},\beta_{s}))$
and
$\alpha\vee\beta=(\min(\alpha_{1},\beta_{1}),\ldots,\min(\alpha_{s},\beta_{s})).$
We have a partial ordering on the variables $Y$ by $y_{\alpha}\leq y_{\beta}$
if $\alpha_{i}\leq\beta_{i}$ for all $i$. Notice that the Hibi relation
$y_{\alpha}y_{\beta}-y_{\alpha\wedge\beta}y_{\alpha\vee\beta}$ is nonzero only
if $y_{\alpha}$ and $y_{\beta}$ are incomparable. The Hibi relations are a
Gröbner basis w. r. t. the DegRevLex order with any order on $Y$ extending the
partial order. The leading term of
$y_{\alpha}y_{\beta}-y_{\alpha\wedge\beta}y_{\alpha\vee\beta}$ is
$y_{\alpha}y_{\beta}$. We make the following observation.

######  Proposition 5.3.

Let $B=X_{1}\cdots X_{s}$ be a transversal polymatroidal basis such that
$\mathcal{J}_{B}$ is generated by the Hibi relations together with one
binomial of degree one. Then $\mathcal{J}_{B}$ has a quadratic Gröbner basis.
Moreover, if $|X_{1}|=\dots=|X_{s}|$ then $\mathbb{K}[B]$ is Gorenstein.

###### Proof.

We may order the variables in each $X_{i}$ so that the one binomial of degree
one in $\mathcal{J}_{B}$ is $y_{\alpha}-y_{\beta}$ with
$\alpha=(|X_{1}|,\ldots,|X_{s}|)$ and $\beta=(1,1,\ldots,1)$. The Hibi
relations are a Gröbner basis, and we shall prove that they remain so after
replacing every occurrence of $y_{\alpha}$ by $y_{\beta}$. First notice that
$y_{\alpha}$ does not divide the leading term of any Hibi relation. Indeed,
$y_{\alpha}\geq y_{\gamma}\geq y_{\beta}$ for any $y_{\gamma}\in Y$. This
shows that replacing $y_{\alpha}$ by $y_{\beta}$ does not change the leading
term of any binomial in $\mathcal{J}_{B}$.

Now assume $|X_{1}|=\dots=|X_{s}|=m$. Then $\mathbb{K}[B]\cong S/L$ there $S$
is the Segre product of $s$ copies of the polynomial ring in $m$ variables,
and $L$ is generated by a binomial of degree one. The Segre product of several
of copies of a Gorenstein ring is again Gorenstein, by a result in [3]. The
polynomial ring is Gorenstein, so $T$ is Gorenstein. $T$ is also a domain, and
hence $T/L$ is Gorenstein. ∎

######  Example 5.4.

Let
$B=\\{x_{1},x_{2}\\}\\{x_{2},x_{3}\\}\\{x_{3},x_{4}\\}\\{x_{4},x_{5}\\}\\{x_{5},x_{1}\\}$.
Then $Y$ is the set of variables indexed by integer vectors
$\alpha=(\alpha_{1},\ldots,\alpha_{5})$ where $1\leq\alpha_{i}\leq 2$. We have
$\varphi(y_{11111})=x_{1}x_{2}x_{3}x_{4}x_{5}$ and
$\varphi(y_{22222})=x_{2}x_{3}x_{4}x_{5}x_{1}$, and $y_{22222}-y_{11111}$ is
the only linear relation in $\mathcal{J}_{B}$. Hence the Hibi relations, with
every occurrence of $y_{22222}$ replaced by $y_{11111}$, is a quadratic
Gröbner basis defining $\mathbb{K}[B]$. One example of a Hibi relation is
$y_{11122}y_{12221}-y_{11121}y_{12222}$ where

$\displaystyle\varphi(y_{11122})=x_{1}x_{2}x_{3}x_{5}x_{1},\ \
\varphi(y_{12221})=x_{1}x_{3}x_{4}x_{5}x_{5},$
$\displaystyle\varphi(y_{11121})=x_{1}x_{2}x_{3}x_{5}x_{5},\ \mbox{and}\
\varphi(y_{12222})=x_{1}x_{3}x_{4}x_{5}x_{1}.$

The Segre product of five polynomial rings in two variables is a Gorenstein
algebra with Hilbert series

$\frac{1+26t+66t^{2}+26t^{3}+t^{4}}{(1-t)^{6}}.$

Hence $K[B]$ is Gorenstein with Hilbert series

$\frac{1+26t+66t^{2}+26t^{3}+t^{4}}{(1-t)^{5}}.\qed$

We finish with a question inspired by Proposition 5.3.

######  Question 5.5.

Which transversal polymatroidal bases define Gorenstein algebras?

## Acknowledgement

I would like to thank Aldo Conca for our discussion about Gröbner bases and
transversal polymatroids which led to the content of Section 5.

## References

  * [1] A. Conca.  Linear spaces, transversal polymatroids and ASL domains.  J. Algebr. Comb., 25:25–41, 2007.
  * [2] A. Conca and J. Herzog.  Castelnuovo-Mumford regularity of products of ideals.  Collect. Math., 54(2):137–152, 2003.
  * [3] S. Goto and K. Watanabe.  On graded rings I.  J. Math. Soc. Japan, 30(2):179–213, 1978.
  * [4] D. R. Grayson and M. E. Stillman.  Macaulay2, a software system for research in algebraic geometry.  Available at https://faculty.math.illinois.edu/Macaulay2/.
  * [5] J. Herzog and T. Hibi.  Discrete Polymatroids.  J. Algebr. Comb., 16:239–268, 2002.
  * [6] J. Herzog, T. Hibi, and M. Vlădoiu.  Ideals of fiber type and polymatroids.  Osaka J. Math., 42:807–829, 2005.
  * [7] J. Herzog and Y. Takayama.  Resolutions by mapping cones.  Homology Homotopy Appl., 4:277–294, 2002.  The Roos Festschrift Vol. 2.
  * [8] L. Nicklasson.  On the Betti numbers and Rees algebras of ideals with linear powers.  arXiv:1904.01995.v2, 2021.  To appear in J. Algebr. Comb.
  * [9] N. White.  A unique exchange property for bases.  Linear Algebra Appl., 31:81–91, 1980.


# Collaborative Generative AI: Integrating GPT-$k$ for
Efficient Editing in Text-to-Image Generation

Wanrong Zhu¶, Xinyi Wang¶, Yujie Lu¶, Tsu-Jui Fu¶,
Xin Eric Wang§, Miguel Eckstein¶, William Yang Wang¶
¶UC Santa Barbara, §UC Santa Cruz
{wanrongzhu, xinyi_wang, yujielu, tsu-juifu, migueleckstein,
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

The field of text-to-image (T2I) generation has garnered significant attention
both within the research community and among everyday users. Despite the
advancements of T2I models, a common issue encountered by users is the need
for repetitive editing of input prompts in order to receive a satisfactory
image, which is time-consuming and labor-intensive. Given the demonstrated
text generation power of large-scale language models, such as GPT-$k$, we
investigate the potential of utilizing such models to improve the prompt
editing process for T2I generation. We conduct a series of experiments to
compare the common edits made by humans and GPT-$k$, evaluate the performance
of GPT-$k$ in prompting T2I, and examine factors that may influence this
process. We found that GPT-$k$ models focus more on inserting modifiers while
humans tend to replace words and phrases, which includes changes to the
subject matter. Experimental results show that GPT-$k$ are more effective in
adjusting modifiers rather than predicting spontaneous changes in the primary
subject matters. Adopting the edit suggested by GPT-$k$ models may reduce the
percentage of remaining edits by 20-30%.

##  1 Introduction

The task of text-to-image (T2I) generation, which involves generating images
from natural language descriptions, holds significant potential to create new
avenues and job opportunities for content creators while also providing
insights into the grounding of natural language in the visual world through
the application of generative AI. A number of models have demonstrated
exceptional performance in terms of image quality, such as StableDiffusion
(Rombach et al., 2021), Midjourney (Midjourney, 2022), Imagen (Saharia et al.,
2022), and DALLE-2 (Ramesh et al., 2022). Despite the popularity of T2I
generation and the ability of these models to generate impressive images, the
difficulty of “prompt-engineering” – which is writing accurate prompts to
describe the desired image in this scenario – still remains a significant
challenge. Users often need to edit the prompt for several rounds before
arriving at a satisfactory image, which makes the process of T2I generation
time-consuming and laborious (and expensive for commercialized models). Figure
1 shows the #edits distribution in the editing traces made by StableDiffusion
Discord server users (Wang et al., 2022). This phenomenon highlights the need
to improve the efficiency and effectiveness of prompting T2I models.

Figure 1:  The histogram plots #edit per trace in DiffusionDB (Wang et al.,
2022) while the lineplot shows the cumulative percentage of traces less than
certain #edit. The y-axis on the left is on log-scale. On average, there are
6.9 edits being made in each user editing trace.

Recently, large language models (LLMs) such as GPT-$k$ (Radford et al., 2019;
Brown et al., 2020; Ouyang et al., 2022) have demonstrated impressive
abilities in text generation. This leads to the natural question of whether
these models can be utilized to improve the T2I prompting process (Chakrabarty
et al., 2023). However, LLMs and T2I models have different architectures and
are often trained on different modalities, which makes it challenging to
integrate them seamlessly.

In this paper, we conduct a series of experiments and analyses on user editing
traces on StableDiffusion,111Our experiments are conducted upon
StableDiffusion since it is a wide-adopted open-source large text-to-image
generative model with SoTA performance. and attempt to modify the T2I prompts
with eight GPT-$k$ models. The primary objective of our research is to examine
the potential of modifying T2I prompts with GPT-$k$ models. More specifically,
we aim to investigate the common edits made by humans and by GPT-$k$, as well
as the performance of prompting T2I generation with GPT-$k$ models.
Additionally, we aim to identify and investigate possible factors that might
influence the performance of GPT-$k$ in T2I generation tasks.

Through our experiments, we observe that:

  * •

While GPT-$k$ models tend to focus more on inserting modifiers, human users
have a greater tendency towards replacing words and phrases, which may include
spontaneous changes to the subject matter of the prompt.

  * •

Modifying the T2I prompt with GPT-$k$ models may not necessarily result in a
direct increase in similarity to the final target image in the editing trace.
Instead, the edit suggested by GPT-$k$ may be closely related to intermediate
editing steps, and the percentage of remaining edits may decrease by 20-30% if
the edit suggested by GPT-$k$ is adopted.

  * •

These findings suggest that instead of attempting to predict spontaneous
changes made by human users on the primary subject matter, GPT-$k$ models are
more effective in improving prompts by rewriting and performing edits related
to modifiers adjustment.

##  2 Research Questions and Settings

To investigate the potential of modifying T2I prompts with GPT-$k$ models, we
conduct a series of experiments and analysis, aiming to answer the following
questions:

  1. 1.

_To what extent can GPT- $k$ models help prompt text-to-image generation?_

  2. 2.

_What are the common types of edits made by humans and by GPT- $k$ models?_

  3. 3.

_What are the factors that may influence GPT- $k$ prompting text-to-image
generation?_

We describe the dataset, models and evaluation metrics used in this study
below.

Dataset  DiffusionDB-2M (Wang et al., 2022) scrapes 2M groups of user prompts,
hyperparameters and images generated by StableDiffusion (Rombach et al., 2021)
from the official Stable Diffusion Discord server. We group the prompts by
anonymized user_id, then cluster the user prompts into traces of edits based
on the prompt contents. More specifically, we encode prompts with Universal
Sentence Encoder (Cer et al., 2018), then cluster upon the prompt embeddings
with DBSCAN (Ester et al., 1996). The order of edits within each trace is
determined by the timestamps. We receive 100k traces of edits, the mean #edit
per trace is 6.9, with a standard deviation of 16.1. Figure 1 plots the #edit
in the clustered traces, which shows a long-tail distribution with about 5% of
the traces having more than 20 edits. Thus, in the following experiments, the
evaluation results were reported on traces with at most 20 edits.

GPT-$k$ Model Name #Parameters GPT-2 (Radford et al., 2019) gpt2-base 117M
gpt2-medium 345M gpt2-large 774M gpt2-xl 1.2B GPT-3 (Brown et al., 2020) text-
ada-001 350M text-babbage-001 1.3B text-curie-001 6.7B GPT-3.5 (Ouyang et al.,
2022) text-davinci-003 175B

Table 1:  The names and corresponding parameter sizes of the GPT-$k$ models
covered in our study.

GPT-$k$ & Text-to-Image Models  Table 2 lists the names and parameter sizes of
the eight GPT-$k$ models we covered in this study. We conduct T2I experiments
with the open-source StableDiffusion-v1-4 (Rombach et al., 2021), which is
used to render images in DiffusionDB (Wang et al., 2022).

Annotations  For each trace of length $n$, we denote the prompts as
(${\bm{t}}_{1}$, ${\bm{t}}_{2}$, …, ${\bm{t}}_{n}$), and the generated images
as (${\bm{i}}_{1}$, ${\bm{i}}_{2}$, …, ${\bm{i}}_{n}$). We refer to the
GPT-$k$-modified prompt as ${\bm{t}}^{\prime}$, and refer to the image
rendered from the modified prompt as ${\bm{i}}^{\prime}$.

Metrics  We use the cosine similarity of CLIP-ViT/B-32 (Radford et al., 2021)
visual features to evaluate the similarity between images. Let ${\bm{i}}_{k}$
denote the image in the original edit trace that is most similar to
${\bm{i}}^{\prime}$, we define the Relative Number of Edits (RNE) as
$\frac{n-k}{n-1}$. The RNE metric reflects the relative position of the edit
in the original trace that is most similar to the edit suggested by GPT-$k$
and also represents the percentage of remaining edits after the edit suggested
by GPT-$k$ is performed.

##  3 Prompting T2I w/ GPT-$k$

In the following experiments, we only reveal the initial prompts in the user
editing traces to GPT-$k$, and ask the models to perform _one_ round of edit.

Procedure  We split the 100k trace of edits into two parts, with 30k traces
used for evaluations and the remaining 70k serving as heldout set. For each of
the listed GPT-$k$ models, we provide the first prompt ${\bm{t}}_{1}$ in each
evaluation trace to the model, and let GPT-$k$ generate the modified prompt
${\bm{t}}^{\prime}$.

GPT-2 models are finetuned with the prompts in the heldout traces for two
epochs with a learning rate of $5e-5$ and a batch size of 128. For GPT-3/3.5
models, an in-context learning approach is adopted. Following previous studies
(Yang et al., 2021; Alayrac et al., 2022), supporting examples for in-context
learning are selected by comparing the similarity of the prompt text features
and retrieving ($\hat{{\bm{t}}}_{1}$, $\hat{{\bm{t}}}_{n}$) pairs from the
top-$m$ most similar traces. Modified prompts are generated through 16-shot
in-context learning with $m$=16. Appendix Table 8 shows how we prompt
GPT-3/3.5.

After receiving the GPT-$k$-modified prompt ${\bm{t}}^{\prime}$, we provide it
to StableDiffusion to generate image ${\bm{i}}^{\prime}$. The effectiveness of
GPT-$k$ in prompting T2I generation is evaluated by comparing the similarity
of the generated image ${\bm{i}}^{\prime}$ to images in the original trace.
The results reported in the following sections are the mean of three repeated
runs.

Model ${\bm{i}}_{1}$-${\bm{i}}_{n}$ ${\bm{i}}_{n-1}$-${\bm{i}}_{n}$
${\bm{i}}^{\prime}$-${\bm{i}}_{n}$ ${\bm{i}}^{\prime}$-${\bm{i}}_{MS}$ RNE(%)
gpt2-base 71.72 74.82 69.58 80.16 75.28 gpt2-medium 69.63 80.39 78.28
gpt2-large 69.70 80.50 78.88 gpt2-xl 69.57 80.37 75.25 gpt3-ada 66.95 76.37
69.43 gpt3-babbage 68.79 78.81 72.33 gpt3-curie 68.45 78.28 71.41
gpt3.5-davinci 68.79 78.09 69.22

Table 2:  The CLIP cosine similarity scores between images and the relative
number of edits (RNE). Here, ${\bm{i}}_{1}$, ${\bm{i}}_{n-1}$, ${\bm{i}}_{n}$
denotes the first, last-but-one, and last image in the trace of edits;
${\bm{i}}^{\prime}$ is the image generated from the modified prompt, and
${\bm{i}}_{MS}$ is the image that is most similar to ${\bm{i}}^{\prime}$ with
regard to CLIP cosine similarity. RNE scores suggest a 20-30% decrease in the
percentage of remaining edits if adopting edits suggested by GPT-$k$.

Automatic Evaluation  The CLIP cosine similarity scores, as listed in Table 2,
are used to evaluate image similarity. Two model-agnostic baselines are
established for comparison: the similarity between the first and last images
(${\bm{i}}_{1}$-${\bm{i}}_{n}$), and the similarity between the last-but-one
and last images (${\bm{i}}_{n-1}$-${\bm{i}}_{n}$).

We denote ${\bm{i}}_{MS}$ as the image in the original trace that is most
similar to the generated image ${\bm{i}}^{\prime}$ (has the highest CLIP
cosine similarity score). Examining results in Table 2, we notice that the
image ${\bm{i}}^{\prime}$ generated from the modified prompt may not be
directly similar to the final target ${\bm{i}}_{n}$, as
(${\bm{i}}^{\prime}$-${\bm{i}}_{n}$) is lower than the baselines. However, it
appears that ${\bm{i}}^{\prime}$ may be related to the intermediate steps in
the editing trace, as evidenced by the significantly higher similarity between
${\bm{i}}^{\prime}$ and ${\bm{i}}_{MS}$ compared to the baselines. RNE scores
show that, ${\bm{i}}^{\prime}$ is most similar to images in the first one-
third of the trace, and that the percentage of remaining edits decreases by
20-30% if the edit suggested by GPT-$k$ is adopted.

Human Evaluation  For each editing trace, we present MTurk annotators with the
initial prompt and image (${\bm{t}}_{1}$, ${\bm{i}}_{1}$), and two candidate
edits: (1) the GPT-$k$-modified prompt, ${\bm{t}}\textquoteright$; (2) the
human edit, ${\bm{t}}_{MS}$, from the original editing trace. Here,
${\bm{t}}_{MS}$ is the corresponding prompt to ${\bm{i}}_{MS}$, which has the
highest CLIP cosine similarity with ${\bm{i}}\textquoteright$. The annotators
are then asked to decide which edit was more effective and more likely to be
adopted by human editors, ${\bm{t}}\textquoteright$ or ${\bm{t}}_{MS}$. We
evaluate each listed GPT-$k$ model with 200 traces. For each trace, three
annotators are invited to provide their judgments.

As shown in Table 3, the three GPT-$k$ models all show tight wins against the
human edits regarding both effectiveness and likelihood of being adopted. This
verifies that the edits made by GPT-$k$ models are similar or comparable to
the intermediate steps in the human editing trace.

Effectiveness Likelihood Win(%) Tie(%) Lose(%) Win(%) Tie(%) Lose(%) gpt2-xl
38.57 29.77 31.66 38.99 22.01 38.99 gpt3-curie 40.89 21.33 37.78 39.33 21.56
39.11 gpt3.5-davinci 39.58 21.67 38.75 38.13 25.00 36.87

Table 3:  Human evaluation results of head-to-head comparison between edits
suggested by GPT-$k$ and human-made edits. We evaluate the effectiveness of
the edit and the likelihood of this edit being adopted by humans. “Win” and
“Tie” indicate that GPT-$k$-suggested edits are better than or comparable to
human edits.

##  4 Human’s Common Edits vs. GPT-$k$’s

Insert Delete Swap Replace Human - 29.9% 21.1% 2.0% 47.0% GPT-$k$ gpt2-base
95.4% 0.0% 0.0% 4.6% gpt2-medium 95.6% 0.1% 0.0% 4.4% gpt2-large 95.0% 0.1%
0.0% 4.9% gpt2-xl 95.9% 0.0% 0.0% 4.1% gpt3-ada 36.5% 14.9% 2.0% 46.6%
gpt3-babbage 39.6% 18.8% 3.3% 38.3% gpt3-curie 42.9% 17.7% 4.1% 35.3%
gpt3.5-davinci 68.5% 3.9% 2.3% 25.3%

Table 4:  The distribution of the common types of edits made by human and by
GPT-$k$ models.

Upon examination of the user editing traces, we identify four types of edits
commonly made by humans: (1) Insert: adding descriptive terms such as
modifiers to the prompt to specify the style, artistic technique, camera view,
lighting, etc; (2) Delete: removing certain terms; (3) Swap: changing the
order of certain terms in the prompt; (4) Replace: changing the modifiers or
the main subject of the prompt. Appendix Table 5 shows edit examples.

To count the frequency of edits, we first remove punctuation marks and
stopwords using NLTK (Bird et al., 2009). We then utilize the
SequenceMatcher222https://docs.python.org/3/library/difflib.html to compare
the adjacent prompts in the trace and detect the edit type. Table 4 lists the
frequency of common edits made by humans and by GPT-$k$ models. We notice a
discrepancy between the distribution of human edits and the ones made by
GPT-$k$. Nearly half of human edits pertain to replace, followed by insert and
delete. GPT-2 models, due to their autoregressive training nature, have a
tendency towards continual generation, resulting in a majority of edits being
insert. While GPT-3/3.5 also undergoes autoregressive training, its extensive
training data and enlarged model size empower it for emergent ability. Unlike
GPT-2, which solely receives the specific prompt requiring editing during
testing, GPT-3/3.5 is also provided with additional editing instances as
supportive exemplars for in-context learning. Consequently, while GPT-2 indeed
adheres to its autoregressive inference manner, the emergent capability of
GPT-3/3.5 enables it to attempt other edit types that simulate human-like
editing behavior. For GPT-3, as the model size increases, we see an increase
in the frequency of insert and a decrease in replace. For GPT-3.5, the most
frequent edit is insert, followed by replace; while delete and swap are
relatively rare.

##  5 Ablations & Analyses

Figure 2:  The CLIP cosine similarity scores between the image generated from
the GPT-3.5-modified prompt and the last image. Results are reported on
${\mathcal{S}}_{\text{eval}}$ (All-mixed), ${\mathcal{S}}_{\text{insert}}$,
${\mathcal{S}}_{\text{delete}}$, ${\mathcal{S}}_{\text{swap}}$ and
${\mathcal{S}}_{\text{replace}}$.

Effects of Edit Types  To investigate the effects of each individual edit type
${\bm{e}}_{i}$, we create four subsets ${\mathcal{S}}_{\text{insert}}$,
${\mathcal{S}}_{\text{delete}}$, ${\mathcal{S}}_{\text{swap}}$ and
${\mathcal{S}}_{\text{replace}}$ from the evaluation set
${\mathcal{S}}_{\text{eval}}$. Each subset ${\mathcal{S}}_{e_{i}}$, comprises
of traces that meet the criteria of “if and only if edit ${\bm{e}}_{i}$ is
applied on the first prompt can we receive the last prompt.” For each edit
type ${\bm{e}}_{i}$, the image similarity between the image generated from the
modified prompt and the last image for traces in ${\mathcal{S}}_{e_{i}}$ is
calculated and compared to the baseline results obtained from the complete
${\mathcal{S}}_{\text{eval}}$ that mixes all types of edits.

Figure 2 illustrates the impact of different edit types on image similarity.
The CLIP cosine similarities of traces that solely consist of insert, delete,
and swap edits are higher or comparable to the all-mixed baseline. This
suggests that GPT-$k$ performs better at adding, removing, and reordering
modifiers. Conversely, we observe that replace edits lead to lower image
similarities. This is likely due to the fact that the replace edit sometimes
results in a change of the subject matter, which can drastically alter the
painting. It is worth noting that shifting the primary subject matter of the
painting is a relatively spontaneous action made by humans. Appendix Table 6
shows a trace with multiple replace operation. The vast number of potential
replacements makes it particularly difficult for GPT-$k$ to accurately select
the desired edit.

Figure 3: The CLIP cosine similarity (upper) and RNE (lower) on traces with
#edit ranging from 2 to 20. Prompts for T2I generation are modified with
GPT-3.5. Here, ${\bm{i}}_{1}$, ${\bm{i}}_{\lfloor\frac{n-1}{2}\rfloor}$,
${\bm{i}}_{n-1}$, ${\bm{i}}_{n}$ denotes the first, middle, last-but-one, and
last image in the trace of edits; ${\bm{i}}^{\prime}$ is the image generated
from the modified prompt, and ${\bm{i}}_{MS}$ is the image that is most
similar to ${\bm{i}}^{\prime}$.

Effects of #Edits Figure 3 depicts how the CLIP cosine similarity changes with
the #edit in the trace. As #edit increases, the similarity between the last
image ${\bm{i}}_{n}$ and those at the beginning or middle of the trace
(${\bm{i}}_{1}$ or ${\bm{i}}_{\lfloor\frac{n-1}{2}\rfloor}$) decreases. This
trend may be attributed to the higher likelihood of changing primary subject
matters in longer traces. Meanwhile, the similarity between the last-but-one
and the last images (${\bm{i}}_{n-1}$ vs. ${\bm{i}}_{n}$) remains consistent,
suggesting that the majority of edits made towards the end of the prompt
editing process are minor in nature. As the trace of edits gets longer, the
similarity between the image ${\bm{i}}^{\prime}$ generated from the modified
prompt and the most similar image ${\bm{i}}_{MS}$ in the trace remains
constant, while the RNE metric gradually increases to approximately 80%. This
indicates that the modified prompt is related to the early edits in the trace.
This aligns with our previous findings, which suggest that GPT-$k$ is
proficient in rewriting prompts and adjusting modifiers, but may struggle to
predict spontaneous changes in the main subject matter of the painting.

##  6 Conclusion

Through our experiments and analyses, we hope to gain a deeper understanding
of the capabilities and limitations of using GPT-$k$ to edit prompts for text-
to-image generation, and provide valuable insights for future research in this
field.

## Limitations

In this work, we are focusing on the StableDiffusion model for text-to-image
generation. However, we have not examined user traces from other online text-
to-image generation servers such as Midjourney or DALLE-2, as these models
have not been publicly released and therefore cannot be replicated locally for
experimentation.

Additionally, the current experimental setup only uses GPT-$k$ for a single
round of editing, and future work should include human studies that use
GPT-$k$ to suggest edits for multiple turns, and compare these to user traces
without the use of GPT-$k$.

Furthermore, the current implementation only utilizes the initial prompt as
input to GPT-$k$. In future studies, it would be beneficial to provide
additional information to the GPT-$k$ models, including additional steps of
editing or the generated image, in order to receive more specific feedback on
the editing suggestions.

## Ethics Statement

The field of text-to-image generation is of great interest to the broad
public, and every content creator should have the opportunity to explore its
potential. However, the current prompt engineering process can be time-
consuming and expensive for content creators, and the repetitive editing and
re-generation process is computationally intensive and not environmentally
friendly. The goal of our work is to improve the efficiency of prompting text-
to-image models, benefiting both users and service providers.

We recognize that large language models (LLMs) such as GPT-$k$ may have the
possibility of generating biased content, as they may prefer the content they
have seen during training, resulting in a smaller chance of showing other
possibly related content. In light of this, we utilize GPT-$k$ models solely
for assisting humans in the prompt editing process, and will continue to keep
humans in the loop for the content creation process.

## Acknowledgments

The UCSB authors were sponsored by the Robert N. Noyce Trust. We thank the
Robert N. Noyce Trust for their generous gift to the University of California
via the Noyce initiative. The views and conclusions contained in this document
are those of the authors and should not be interpreted as representing the
sponsor.

## References

  * Alayrac et al. (2022) Jean-Baptiste Alayrac, Jeff Donahue, Pauline Luc, Antoine Miech, Iain Barr, Yana Hasson, Karel Lenc, Arthur Mensch, Katie Millican, Malcolm Reynolds, Roman Ring, Eliza Rutherford, Serkan Cabi, Tengda Han, Zhitao Gong, Sina Samangooei, Marianne Monteiro, Jacob Menick, Sebastian Borgeaud, Andy Brock, Aida Nematzadeh, Sahand Sharifzadeh, Mikolaj Binkowski, Ricardo Barreira, Oriol Vinyals, Andrew Zisserman, and Karen Simonyan. 2022.  Flamingo: a visual language model for few-shot learning.  _ArXiv_ , abs/2204.14198.
  * Bird et al. (2009) Steven Bird, Ewan Klein, and Edward Loper. 2009.  _Natural language processing with Python: analyzing text with the natural language toolkit_.  " O’Reilly Media, Inc.".
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, T. J. Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeff Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  _ArXiv_ , abs/2005.14165.
  * Cer et al. (2018) Daniel Matthew Cer, Yinfei Yang, Sheng yi Kong, Nan Hua, Nicole Limtiaco, Rhomni St. John, Noah Constant, Mario Guajardo-Cespedes, Steve Yuan, Chris Tar, Brian Strope, and Ray Kurzweil. 2018.  Universal sentence encoder for english.  In _Conference on Empirical Methods in Natural Language Processing_.
  * Chakrabarty et al. (2023) Tuhin Chakrabarty, Arkadiy Saakyan, Olivia Winn, Artemis Panagopoulou, Yue Yang, Marianna Apidianaki, and Smaranda Muresan. 2023.  I spy a metaphor: Large language models and diffusion models co-create visual metaphors.  In _Findings of the Association for Computational Linguistics: ACL 2023_ , pages 7370–7388, Toronto, Canada. Association for Computational Linguistics.
  * Dong et al. (2014) Chao Dong, Chen Change Loy, Kaiming He, and Xiaoou Tang. 2014.  Image super-resolution using deep convolutional networks.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 38:295–307.
  * Ester et al. (1996) Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. 1996.  A density-based algorithm for discovering clusters in large spatial databases with noise.  In _Knowledge Discovery and Data Mining_.
  * Han et al. (2018) Wei Han, Shiyu Chang, Ding Liu, Mo Yu, M. Witbrock, and Thomas S. Huang. 2018.  Image super-resolution via dual-state recurrent networks.  _2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 1654–1663.
  * Li et al. (2018) Xia Li, Jianlong Wu, Zhouchen Lin, Hong Liu, and Hongbin Zha. 2018.  Recurrent squeeze-and-excitation context aggregation net for single image deraining.  In _European Conference on Computer Vision_.
  * Midjourney (2022) Lab Midjourney. 2022.  [link].
  * Ouyang et al. (2022) Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke E. Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Francis Christiano, Jan Leike, and Ryan J. Lowe. 2022.  Training language models to follow instructions with human feedback.  _ArXiv_ , abs/2203.02155.
  * Radford et al. (2021) Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. 2021.  Learning transferable visual models from natural language supervision.  In _International Conference on Machine Learning_.
  * Radford et al. (2019) Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.
  * Ramesh et al. (2022) Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. 2022.  Hierarchical text-conditional image generation with clip latents.  _ArXiv_ , abs/2204.06125.
  * Rombach et al. (2021) Robin Rombach, A. Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. 2021.  High-resolution image synthesis with latent diffusion models.  _2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 10674–10685.
  * Saharia et al. (2022) Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily L. Denton, Seyed Kamyar Seyed Ghasemipour, Burcu Karagol Ayan, Seyedeh Sara Mahdavi, Raphael Gontijo Lopes, Tim Salimans, Jonathan Ho, David J. Fleet, and Mohammad Norouzi. 2022.  Photorealistic text-to-image diffusion models with deep language understanding.  _ArXiv_ , abs/2205.11487.
  * Wang et al. (2019) Tianyu Wang, Xin Yang, Ke Xu, Shaozhe Chen, Qiang Zhang, and Rynson W. H. Lau. 2019.  Spatial attentive single-image deraining with a high quality real rain dataset.  _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 12262–12271.
  * Wang et al. (2004) Zhou Wang, Alan Conrad Bovik, Hamid R. Sheikh, and Eero P. Simoncelli. 2004.  Image quality assessment: from error visibility to structural similarity.  _IEEE Transactions on Image Processing_ , 13:600–612.
  * Wang et al. (2022) Zijie J. Wang, Evan Montoya, David Munechika, Haoyang Yang, Benjamin Hoover, and Duen Horng Chau. 2022.  Diffusiondb: A large-scale prompt gallery dataset for text-to-image generative models.
  * Yang et al. (2021) Zhengyuan Yang, Zhe Gan, Jianfeng Wang, Xiaowei Hu, Yumao Lu, Zicheng Liu, and Lijuan Wang. 2021.  An empirical study of gpt-3 for few-shot knowledge-based vqa.  In _AAAI Conference on Artificial Intelligence_.
  * Zeng et al. (2021) Yu Zeng, Zhe L. Lin, and Vishal M. Patel. 2021.  Sketchedit: Mask-free local image manipulation with partial sketches.  _2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 5941–5951.

##  Appendix A Appendix

###  A.1 DiffusionDB

DiffusionDB-2M (Wang et al., 2022) is on MIT License. It contains 2M user
prompts with an average #token of 30.7 $\pm$ 21.2. Figure 4 shows the
distribution of #token per prompt.

Figure 4:  The distribution of the number of tokens per prompt in DiffusionDB
(Wang et al., 2022).

###  A.2 Hyperparameters

For the DBSCAN clustering, we set eps= $0.5$, min_samples= $1$ (note that we
will filter out the clusters with only 1 sample, since it does not form a
trace of edits), and metric=‘cosine’.

For the GPT2 model, our implementation is based on GPT2LMHeadModel on
HuggingFace. During inference, we set do_sample=True, num_beams=$5$,
max_new_tokens=$80$, and early_stopping=True.

For the GPT3 models, we set temperature=$0.7$ and max_tokens=$256$. The other
parameters just follows the default setting the OpenAI API.

For the Stable Diffusion model, our implementation is based on CompVis/stable-
diffusion-v1-4 on Huggingface. We set the random seed to $41,42,43$ for the
three repeated runs. The heigth, width, guidance_scale and num_inference_step
are kept the same as the original user specification collected in DiffusionDB
for each trace of edits.

###  A.3 Showcases

Table 5 presents an excerpt from an editing trace and provides examples of the
four types of common edits, including insert, delete, swap, and replace. Table
6 illustrates a user editing trace where the edit of replace occurs in every
step, and the primary subject matter of the prompt is constantly changing.
Table 9 displays two sets of prompts that have been modified by the eight
covered GPT-$k$ models. Figures 6 and 7 provide examples of the edits
suggested by GPT-$k$ and those made by humans for head-to-head comparisons in
terms of effectiveness and likelihood to be adopted by humans.

User Input Prompt Generated Image circular ornated ceiling highly detailed
photo of an ornated circular ceiling, full of paintings of angels, centered
symmetrical, highly detailed SWAP: “circular ornated” -> “ornated circular”
INSERTION: “full of painting of angels”, “centered symmetrical” ornate marble
and gold wall, full of paintings of angels, highly detailed REPLACE: “ceiling”
-> “marble and gold wall” DELETION: removed “centered symmetrical”

Table 5: Common types of edits.

User Input Prompt Generated Image side profile centered painted portrait,
spidergwen, matte painting concept art, art nouveau, beautifully backlit,
swirly vibrant color lines, fantastically gaudy, aesthetic octane render, 8 k
hd resolution, by ilya kuvshinov and cushart krentz and gilleard james side
profile centered painted portrait, megan fox as spidergwen, matte painting
concept art, art nouveau, beautifully backlit, swirly vibrant color lines,
fantastically gaudy, aesthetic octane render, 8 k hd resolution, by ilya
kuvshinov and cushart krentz and gilleard james side profile centered painted
portrait, spiderman, matte painting concept art, art nouveau, beautifully
backlit, swirly vibrant color lines, fantastically gaudy, aesthetic octane
render, 8 k hd resolution, by ilya kuvshinov and cushart krentz and gilleard
james side profile centered painted portrait, boba fett, matte painting
concept art, art nouveau, beautifully backlit, swirly vibrant color lines,
fantastically gaudy, aesthetic octane render, 8 k hd resolution, by ilya
kuvshinov and cushart krentz and gilleard james side profile centered painted
portrait, darth maul, matte painting concept art, art nouveau, beautifully
backlit, swirly vibrant color lines, fantastically gaudy, aesthetic octane
render, 8 k hd resolution, by ilya kuvshinov and cushart krentz and gilleard
james side profile centered painted portrait, the punisher, matte painting
concept art, art nouveau, beautifully backlit, swirly vibrant color lines,
fantastically gaudy, aesthetic octane render, 8 k hd resolution, by ilya
kuvshinov and cushart krentz and gilleard james side profile centered painted
portrait, wolverine, matte painting concept art, art nouveau, beautifully
backlit, swirly vibrant color lines, fantastically gaudy, aesthetic octane
render, 8 k hd resolution, by ilya kuvshinov and cushart krentz and gilleard
james

Table 6: A user trace where the edit of replace constantly occurs. The primary
subject matters of the prompts are in bold, and we can see that the main
subject changes from step to step in this editing trace.

###  A.4 Human Evaluation

In our study, we recruited Amazon Mechanical Turk annotators to conduct human
evaluations. To ensure the quality of the evaluations, we established two
additional qualifications for the annotators, which included a HIT Approval
Rate of higher than 99% and the completion of more than 100 approved HITs. The
instructions provided to the MTurk annotators are displayed in Figures 6 and
7. Each HIT assignment was compensated with a payment of $0.30, and the
average completion time for each assignment was approximately 2 minutes. This
equates to an average hourly pay of $9-10.

###  A.5 Other Image Similarity Metrics

Model SSIM PSNR ${\bm{i}}_{1}$-${\bm{i}}_{n}$ ${\bm{i}}_{n-1}$-${\bm{i}}_{n}$
${\bm{i}}^{\prime}$-${\bm{i}}_{n}$ ${\bm{i}}^{\prime}$-${\bm{i}}_{MS}$ RNE
${\bm{i}}_{1}$-${\bm{i}}_{n}$ ${\bm{i}}_{n-1}$-${\bm{i}}_{n}$
${\bm{i}}^{\prime}$-${\bm{i}}_{n}$ ${\bm{i}}^{\prime}$-${\bm{i}}_{MS}$ RNE
gpt2-base 18.93 20.39 17.60 22.99 52.32 9.16 9.37 9.35 10.44 52.92 gpt2-medium
17.54 22.96 52.60 9.36 10.45 53.30 gpt2-large 17.52 22.94 52.80 9.36 10.45
52.57 gpt2-xl 17.51 22.86 52.98 9.35 10.44 53.29 gpt3-ada 17.11 22.28 53.71
9.33 10.37 52.67 gpt3-babbage 16.97 22.12 52.85 9.26 10.30 52.40 gpt3-curie
17.41 22.80 53.51 9.29 10.36 52.25 gpt3.5-davinci 16.91 22.00 51.92 9.22 10.27
52.32

Table 7:  The SSIM and PSNR scores to evaluate image similarity. Here,
${\bm{i}}_{1}$, ${\bm{i}}_{n-1}$, ${\bm{i}}_{n}$ denotes the first, last-but-
one, and last image in the trace of edits; ${\bm{i}}^{\prime}$ is the image
generated from the modified prompt, and ${\bm{i}}_{MS}$ is the image that is
most similar to ${\bm{i}}^{\prime}$ with regard to current similarity metric.

Mode Prompt In-Context $k$-Shot The user wants to draw a picture and is
deciding upon what key elements should be included. You may add, swap, or
remove the modifiers, or even replace the main character. Please refer to the
examples of edits and predict the elements in the final painting. Input:
{first prompt in the $k$-most related trace} Output: {last prompt in the
$k$-most related trace} Input: {first prompt in the ($k$-1)-most related
trace} Output: {last prompt in the ($k$-1)-most related trace} $\dots$ Input:
{first prompt in the most related trace} Output: {last prompt in the most
related trace} Input: {first prompt in current trace} Output:

Table 8:  The prompts for GPT-3 and GPT-3.5 models.

In line with previous studies on image editing/generation (Dong et al., 2014;
Han et al., 2018; Li et al., 2018; Wang et al., 2019; Zeng et al., 2021), we
also employed the following metrics to evaluate the similarity between images:
(1) SSIM (Wang et al., 2004) which assesses pixel-wise errors from the
perspective of luminance, contrast, and structure; (2) PSNR, which compares
pixels using the mean squared error.

Table 7 presents the SSIM and PSNR scores used to evaluate image similarity.
For each metric, we established the similarity score between the first and
last images (${\bm{i}}_{1}$-${\bm{i}}_{n}$) and the last-but-one and last
images (${\bm{i}}_{n-1}$-${\bm{i}}_{n}$) as baselines. The similarity between
the images generated from the modified prompts and the target image of the
current trace (${\bm{i}}^{\prime}$-${\bm{i}}_{n}$) is comparable to the
baselines as per PSNR, however, it is lower as per SSIM. However, we also
observed that the similarity between ${\bm{i}}^{\prime}$-${\bm{i}}_{MS}$ is
significantly higher than the baselines, as per both listed metrics. This
suggests that even though the image generated from the modified prompt may not
be directly similar to the final target, it may be related to the intermediate
steps in the editing trace. The RNE results, as per SSIM and PSNR, indicate
that ${\bm{i}}^{\prime}$ is most similar to images in the middle of the trace
in terms of pixel-wise comparison.

Figure 5:  The SSIM, PSNR and CLIP cosine similarity scores between the image
generated from the GPT-3.5-modified prompt and the last image. Results are
reported on ${\mathcal{S}}_{\text{eval}}$ (All-mixed),
${\mathcal{S}}_{\text{insert}}$, ${\mathcal{S}}_{\text{delete}}$,
${\mathcal{S}}_{\text{swap}}$ and ${\mathcal{S}}_{\text{replace}}$.

Figure 5 plots the effect of the four common types of edits. Similar to what
we found in Section 2, SSIM and PSNR have similar performances on the ablated
evaluation traces – metric scores on traces that only involve insert, delete
and swap are higher than or comparable to corresponding baselines. Meanwhile,
we notice that replace leads to lower image similarities, which applies to all
three image similarity metrics.

Trace#1 Initial Prompt in User Editing Trace guns and roses on a crimson and
black background, intricate illustration Last Prompt in User Editing Trace an
epic guns and roses mural on a crimson and black background, intricate
illustration, highly ornate, exquisite detail, rtx, 4k Modified Prompt
gpt2-base guns and roses on a crimson and black background, intricate
illustration, highly detailed, simple, no jagged lines, smooth, artstation,
centered artwork by obey gpt2-medium guns and roses on a crimson and black
background, intricate illustration, concept art, pixiv fanbox, art by wlop and
greg rutkowski and makoto shinkai and studio ghibli and kyoto animation
gpt2-large guns and roses on a crimson and black background, intricate
illustration, detailed, award - winning, trending on artstation, 4 k, 8 k
gpt2-xl guns and roses on a crimson and black background, intricate
illustration gpt3-ada funky 8 0s eurobeat, album cover, realistic, hdr, clear
image gpt3-babbage guns and roses on a crimson and black background, art by
david deutsch, inspired by the movie ’Guns and Roses’ gpt3-curie guns and
roses on a crimson and black background, intricate illustration, david hellyer
gpt3.5-davinci guns and roses on a crimson and black background, intricate
illustration, vivid colors, concept art, artstation Trace#2 Initial Prompt in
User Editing Trace a bottle filled with dreams Last Prompt in User Editing
Trace a hamburger in the bottle Modified Prompt gpt2-base a bottle filled with
dreams, highly detailed, digital painting, artstation, concept art, sharp
focus, illustration, art by artgerm and greg rutkowski and alphonse mucha
gpt2-medium a bottle filled with dreams, highly detailed, digital painting,
artstation, concept art, sharp focus, illustration, art by artgerm and greg
rutkowski and alphonse mucha gpt2-large a bottle filled with dreams gpt2-xl a
bottle filled with dreams, art by James Jean and Wayne Barlowe, high detail,
cinematic, cgsociety 8k gpt3-ada A dream filled bottle. gpt3-babbage a
transparent plastic bottle filled with dreams, close up, 1 5 mm lens
photograph gpt3-curie a bottle filled with dreams, dreamlike background
gpt3.5-davinci a bottle of colorful dreams, vibrant colors, dreamlike
elements, surrealism, magical realism, abstract painting.

Table 9: Two sets of examples that compares the modified prompt generated by
each GPT-$k$ model. Figure 6:  This screenshot illustrates the interface used
in the MTurk study for a head-to-head comparison of the effectiveness of the
edits suggested by the GPT-$k$ model and those made by humans. In this
specific example, “Edit 1” was suggested by GPT-2-xl, while “Edit 2”
represents the most similar human edit in the original editing trace.  Figure
7:  This screenshot illustrates the interface used in the MTurk study for a
head-to-head comparison of the edits suggested by the GPT-$k$ model and those
made by humans. The purpose of this evaluation was to assess the likelihood of
an edit being adopted by humans. In this specific example, “Edit 1” was
suggested by GPT-3.5-davinci, while “Edit 2” represents the most similar human
edit in the original editing trace. Notice that in this example, the user
actually made a typo (misspelled “canvas” into “camvas” in both the initial
prompt and the prompt in Edit 2), which confused the Stable Diffusion model
and thus led to unrelated renderings.