Let us fix some arbitrarily lexicographical ordering over $E$. This allows us
to uniquely identify a representative:

###### Definition D.2.

Given an equivalence class $R$ under $\sim$, the primitive representative is
the lexicographically first element in $R$ achieving the longest sequence
length.

It is not hard to see that this maximal element consists entirely of primitive
operations, hence the name.

###### Definition D.3.

For any $t\in\mathcal{T}$, we define the length of $t$, denoted $|t|$, as the
number of transformations in the primitive representative of its equivalence
class.

Under this definition of length, $(t_{1},\ldots,t_{n})\in\mathcal{T}^{n}$ and
$\tau=t_{n}\circ\cdots\circ t_{1}\in\mathcal{T}$ have the same length.

###### Proof of Theorem 4.4.

Soundness and completeness follows from the fact that $d(v_{i},v)=0$ if and
only if $\alpha(p_{i})\models v$. Progress follows also from the fact that $T$
is a uniform covering and we decrease $d$ by at least $\epsilon$ each step. At
each step we consider each transformation $t\in T$, and we do this once for
each transformation in the returned sequence. Hence, the total runtime is
linear in $|T|$ and the number of transformations in the returned sequence
(which is bounded by the length of the returned sequence). ∎

Next, we provide a formal definition of a recursively consistent synthesis
algorithm, which was first introduced informally in Section 4.2.2:

###### Definition D.4.

Let $D$ be a positive integer. Then $A$ is recursively consistent at depth $D$
if there is a constant $C\geq 0$ such that for all feasible $p,v$, there
exists a pair of transformations $(t_{1},t_{2})\sim A(p,v)$ with $|t_{1}|\leq
D$ satisfying

  1. (1)

$A(t_{1}(p),v)\sim t_{2}$; and

  2. (2)

$A(t_{1}(p),v)$ runs in at most $C$ more steps than $A(p,v)$.

We claim that our definition of a recursively consistent algorithm is
relatively natural. Roughly speaking, the synthesis problem has a recursively
consistent algorithm $A$ if there are “stopping points” along the way for
which $A$ can output partial solutions (of bounded length). For instance,
large programs are often organized into several files, which themselves are
broken down into functions; when tackling a theorem, lemmas can be used to
streamline the proof. Hence, focusing on synthesis problems that are solvable
via recursively consistent means does not materially limit the scope of our
results from a practical standpoint. Note that recursive consistency is not
just a condition on the inherent difficulty of the synthesis task (as in
standard computational complexity) but also the difficulty of computing a
solution under the semantics of the language of transformations $E^{*}$.

We also need a more nuanced way to quantify the efficiency of synthesis. So
far (e.g., in Theorem 4.4), we have been using the following measure of
efficiency:

###### Definition D.5.

A synthesis algorithm $A$ is output-efficient if its computational complexity
is polynomial in the length of its output, $|A(p,v)|$.

The main issue with this definition is that achieving a run time that is
polynomial in output length is, in some sense, trivial. For instance, suppose
that algorithm $A$ runs in time that is exponential in its output, but there
exists a transformation $t_{\text{id}}\in\mathcal{T}$ that is the identity
transformation, i.e., $t_{\text{id}}(p)=p$ for all $p\in\mathcal{P}$. Then we
can make $A$ run in “polynomial time” simply by appending an exponentially
long sequence of $t_{\text{id}}$ to the end of the original output. More
generally, using output efficiency leads to a host of problems that can be
summarized as rewarding “verbose” algorithms (i.e., those that return longer
sequences of transformations).

To avoid such issues, we instead define efficiency with respect to an
independent baseline:

###### Definition D.6.

A complexity function is a function
$K:\mathcal{P}\times\mathcal{V}\rightarrow\mathbb{R}^{+}$.

###### Definition D.7.

A synthesis algorithm is _K_ -efficient if its computational complexity is
polynomially bounded by the complexity function $K$.

One way to understand this is that the complexity function $K$ measures how
“difficult” a particular synthesis task $(p,v)$ is. Then a $K$-efficient
algorithm scales gracefully with the difficulty of the input instance.
Alternatively, the complexity function tells us roughly how much time we are
willing to spend on solving a particular instance of a synthesis task. In this
case, a synthesis algorithm is $K$-efficient if the amount of time it takes to
solve an input instance grows polynomially with the computational budget. Both
of these interpretations give an objective way to compare the efficiency of
different synthesis algorithms. Note that there is no requirement that the
complexity function itself be efficiently computable.

Algorithm 3 Parallel progressive synthesis

1:initial program $p$, program property $v$, a distance function $d$, uniform
covering $T$ with lower bound $\epsilon$

2:$\not\models$ if $(p,v)$ is infeasible; otherwise, a sequence of
transformations $\tau$ such that $\tau(p)\models v$

3:$d_{0}\leftarrow d(p,v)$

4:if $d_{0}=\infty$ then

5: return $\not\models$

6:end if

7:$\tau\leftarrow\\{\\}$, $p_{0}\leftarrow p$

8:for $i$ = 1, … do

9: if $d_{i-1}=0$ then

10: return $\tau$

11: end if

12: $t_{i}\leftarrow\textsc{ParallelSearch}\big{(}T;\lambda
t.\big{(}d(t(p_{i-1}),v)+\epsilon\leq d_{i-1}\big{)}\big{)}$

13: $p_{i}\leftarrow t_{i}(p_{i-1})$

14: $d_{i}\leftarrow d(p_{i},v)$

15: $\tau\leftarrow(t_{1},\ldots,t_{i})$

16:end for

We now introduce a new progressive synthesis algorithm that is designed for
$K$-efficiency (rather than output efficiency). Algorithm 3 presents the
pseudocode for this variant, which we call parallel progressive synthesis. The
main difference between the greedy and parallel variants of progressive
synthesis is the use of the subroutine ParallelSearch on line 12 in Algorithm
3. $\textsc{ParallelSearch}(T;\textsc{Cond})$ takes two arguments: the first
argument $T$ is a set, and the second argument Cond is a conditional that
takes an element of $T$ and returns either True or False. ParallelSearch then
initializes one instance of Cond for each element $t\in T$, and begins
executing Cond _in parallel, one step at a time_. Every time an instance of
Cond finishes computing, we check its output value and return if the condition
is satisfied. Then the run time of ParallelSearch is bounded by the size of
the set $T$ multiplied by the minimum amount of time it takes to verify a
satisfying $t\in T$.

More explicitly, define $S(f;x)$ to be the total number of steps needed to
compute the function $f$ on the input $x$. Define the set of transformations
that decrease the distance by at least $\epsilon$ as $T^{\downarrow}=\\{t\in
T\ |\ d(t(p_{i}),v)+\epsilon\leq d_{i}\\}$. Then each call to ParallelSearch
on line 12 in Algorithm 3 terminates after exactly $|T|\min_{t\in
T^{\downarrow}}S(d;(t(p_{i}),v))$ steps. We say that ParallelSearch returns
the _fastest continuation_ :

(18) $\displaystyle t_{i}=\operatorname*{\arg\min}_{t\in
T^{\downarrow}}S(d;(t(p),v))$

We can compare this with the analogous greedy search subroutine from Algorithm
1 (greedy progressive synthesis), which always takes the _most progressive
continuation_ :

(19) $\displaystyle t_{i}=\operatorname*{\arg\min}_{t\in T}d(t(p),v)$

In contrast to ParallelSearch, the run time of this line is bounded _from
below_ by the _maximum_ amount of time it takes to compute $d(t(p),v)$ for any
$t\in T$. This explains why we need to use the ParallelSearch function, since
we have no control over the worst-case performance of $d$.

We now state the first version of our main result.

###### Theorem D.8.

Given a synthesis task specified by a space of programs $\mathcal{P}$; a
program property $\Pi=(\mathcal{V},\leq,\alpha)$; and a set of primitive
transformations $E$; for all complexity functions $K(p,v)$, the following are
equivalent:

  1. (1)

There exists a sound, complete, $K$-efficient, and recursively consistent
synthesis algorithm $A$.

  2. (2)

There exists a distance function $d$ with a uniform covering, such that the
parallel progressive synthesis algorithm is sound, complete, and
$K$-efficient.

###### Proof.

$(2)\implies(1)$ follows immediately from the fact that progressive synthesis
is recursively consistent (with depth 1). The other direction requires us to
demonstrate that the existence of a recursively consistent synthesis algorithm
also implies that the existence of a viable distance function $d$ for
progressive synthesis.

Then let us assume that $A$ is a sound, complete, $K$-efficient, and
recursively consistent synthesis algorithm with depth $D$. The first step is
to construct the distance function $d$. We define the following distance
function:

(20) $\displaystyle d(p,v)$ $\displaystyle:=\begin{cases}\infty,&\text{if
}A(p,v)\text{ returns }\not\models\\\ |A(p,v)|&\text{otherwise}\end{cases}$

By the soundness and completeness of $A$, $d$ satisfies the definition of a
distance function.

Next, define $T$ to to be the set of all strings of length at most $D$, formed
from the alphabet $E$. Then $T$ is a uniform covering with $\epsilon=1$ since
$A$ is recursively consistent: given $A(p,v)=(t_{1},\ldots,t_{n})$, there is
some $(s_{1},s_{2})\sim(t_{1},\ldots,t_{n})$ with $s_{1}\in
T^{\downarrow}\subseteq T$ such that $d(p,v)=|A(p,v)|$ and
$d(s_{1}(p),v)=|A(s_{1}(p),v)|=|s_{2}|\leq|A(p,v)|-1$. So by Theorem 4.4, the
parallel progressive synthesis algorithm is sound and complete.

It remains to show that parallel progressive synthesis is $K$-efficient given
the distance function $d$ constructed above. Denote the output
$A(p,v)=(t_{1},\ldots,t_{n})$. We will prove the following two statements
about the parallel progressive synthesis algorithm:

  1. (1)

The total number of iterations is at most $n$.

  2. (2)

Within each iteration, the call to ParallelSearch is polynomially bounded by

(22) $\displaystyle|T|(S(A;(p,v)+C*i)$

where $C$ is a constant.

Combining the two estimates yields an upper bound for the computational
complexity of

(23) $\displaystyle n|T|(S(A;(p,v))+C*n)$

for the parallel progressive synthesis algorithm. Since $A$ is $K$-efficient
by assumption, $S(A;(p,v))$ is polynomially bounded by $K(p,v)$. Similarly,
the original output length $n=|A(p,v)|$ is upper bounded by the run time of
$A$, and hence is also polynomially bounded by $K(p,v)$. Thus, the total
computational complexity of the parallel progressive synthesis algorithm is
polynomially bounded by $K(p,v)$, as claimed.

It remains to prove the two claims. The first one follows from the fact that
ParallelSearch is guaranteed to return a transformation that reduces the
distance by at least 1, and since the distance is initialized to
$d_{0}=d(p,v)=|A(p,v)|=n$, the loop terminates after at most $n$ iterations.
To prove the second invariant, consider the $i^{th}$ iteration of the loop. By
the definition of recursive consistency, there exists some $s_{i}\in
T^{\downarrow}$ such that $A(s_{i}(p_{i-1}),v)$ runs in at most $C$ more steps
than $A(p_{i-1},v)$. Inducting backward on $i$ we see that
$A(s_{i}(p_{i-1}),v)$ runs in at most $C*i$ more steps than $A(p_{0},v)$.
Furthermore, ParallelSearch is guaranteed to return $t_{i}\in T^{\downarrow}$
such that $d(t_{i}(p),v)$ takes at most as many steps as $d(s_{i}(p),v)$.
Hence, ParallelSearch takes at most $|T|S(A;(p,v)+C*i)$ steps in the $i^{th}$
iteration. ∎

Note that there is a hidden constant in the total run time of the parallel
progressive synthesis algorithm in Eq. 23 that depends the size of the
covering $|T|=O(|E|^{D}+D)$ (the addition of $D$ makes explicit the dependence
on depth when $|E|=1$). Our proof relies crucially on the depth $D$ of the
recursive synthesis algorithm in order to construct the covering set $T$ of
all transformations of length at most $D$. We also see that Theorem 4.5 is the
informal statement of the special case when the depth $D=1$.

The final result of this section presents a different approach based on
universal search (Levin, 1973). Our objective is to define a version of
progressive synthesis that does not need to be provided with a covering set
$T$. The entire problem is then reduced to defining a suitable distance
function $d$.

The main challenge without _a priori_ access to a covering set $T$ is that we
can no longer rely on ParallelSearch, which essentially searches over a known
finite set guaranteed to contain a fast solution. Instead, we will define a
new subroutine UniversalSearch that only requires the existence of a fast
solution of some (unknown) finite length.

$\textsc{UniversalSearch}(E,\textsc{Cond})$ takes two arguments: an alphabet
$E$ and a conditional Cond that takes as input any string $t\in E^{*}$ and
returns either True or False. The execution of UniversalSearch then proceeds
in phases, starting from phase $i=0$. During the $i^{th}$ phase,
UniversalSearch evaluates Cond on all strings $t\in E^{*}$ of length at most
$i$, up to a total of $\max(i,|E|^{i})$ steps per instance in parallel (i.e.,
first by running all $t\in\mathcal{T}$ of length _equal_ to $i$ for up to
$\max(i-1,|E|^{i-1})$ steps in parallel, then by running all $t\in\mathcal{T}$
of length _at most_ $i$ for up to a total of $\max(i,|E|^{i})$ steps in
parallel). The rest of the strategy is the same as ParallelSearch: whenever an
instance of Cond completes, we return if the condition is satisfied. Algorithm
4 presents the resulting synthesis algorithm, which we call universal
progressive synthesis.

Algorithm 4 Universal progressive synthesis

1:initial program $p$, program property $v$, a distance function $d$,
primitives $E$

2:$\not\models$ if $(p,v)$ is infeasible; otherwise, a sequence of
transformations $\tau$ such that $\tau(p)\models v$

3:$d_{0}\leftarrow d(p,v)$

4:if $d_{0}=\infty$ then

5: return $\not\models$

6:end if

7:$\tau\leftarrow\\{\\}$, $p_{0}\leftarrow p$

8:for $i$ = 1, … do

9: if $d_{i-1}=0$ then

10: return $\tau$

11: end if

12: $t_{i}\leftarrow\textsc{UniversalSearch}\big{(}E;\lambda
t.\big{(}d(t(p_{i-1}),v)<d_{i-1}\big{)}\big{)}$

13: $p_{i}\leftarrow t_{i}(p_{i-1})$

14: $d_{i}\leftarrow d(p_{i},v)$

15: $\tau\leftarrow(t_{1},\ldots,t_{i})$

16:end for

###### Theorem D.9.

Given a synthesis task specified by a space of programs $\mathcal{P}$; a
program property $\Pi=(\mathcal{V},\leq,\alpha)$; and a set of primitive
transformations $E$; for all complexity functions $K(p,v)$, the following are
equivalent:

  1. (1)

There exists a sound, complete, $K$-efficient, and recursively consistent
synthesis algorithm $A$.

  2. (2)

There exists a distance function $d$ such that the universal progressive
synthesis algorithm is sound, complete, and $K$-efficient.

###### Proof.

This proof is nearly the same as the proof of Theorem D.8, except that we need
to analyze the performance of the subroutine UniversalSearch instead of
ParallelSearch. In particular, we will use the same distance as in the proof
of Theorem D.8, namely,

(24) $\displaystyle d(p,v)$ $\displaystyle:=\begin{cases}\infty,&\text{if
}A(p,v)\text{ returns }\not\models\\\ |A(p,v)|&\text{otherwise}\end{cases}$

Now assume that UniversalSearch returns a solution $t$ of length $D$ that
takes $S$ steps to verify. We can upper bound the run time of UniversalSearch
as follows.

First, if $|E|=1$, then $\textsc{Cond}(t)$ begins execution during phase $D$
and completes execution during phase $D+S$. At the end of phase $D+S$, there
are exactly $D+S$ instances of Cond which have begun execution, each of which
has been run for at most $D+S$ steps. This yields an upper bound for the total
run time of at most $(D+S)^{2}$.

Otherwise, if $|E|>1$, then $\textsc{Cond}(t)$ begins execution in phase $D$
and completes execution by the end of phase $D+\lceil\log_{E}(S)\rceil$. At
this point there are exactly

(26) $\displaystyle\sum_{i=0}^{D+\lceil\log_{E}(S)\rceil}|E|^{i}$

instances of Cond that have begun execution, which can be bounded from above
by

(27) $\displaystyle\sum_{i=0}^{D+\lceil\log_{E}(S)\rceil}|E|^{i}$
$\displaystyle\leq 2|E|^{D+\lceil\log_{E}(S)\rceil}$ (28) $\displaystyle\leq
2S|E|^{D+1}$

The total number of sequential steps taken by any instance of Cond is upper
bounded by

(29) $\displaystyle|E|^{D+\log_{E}(S)}=S|E|^{D}$

Putting all this together, the total number of steps taken by UniversalSearch
is at most

(30) $\displaystyle 2S^{2}|E|^{2D+1}+(D+S)^{2}=O(S^{2}(|E|^{2D+1}+D^{2}))$

In particular, we see that UniversalSearch pays at most a quadratic overhead
over ParallelSearch, except that here $D$ refers to the _unknown_ finite depth
of the recursively consistent algorithm $A$. We omit the remainder of this
proof as it is otherwise identical to the proof of Theorem D.8. ∎

###  D.3. Product Properties and Monotonic Transformations

The main result of this section is a proof of Theorem 4.7. We begin with a
method of combining two properties by taking their product.

###### Definition D.10.

Let $\Pi_{1}=(\mathcal{V}_{1},\leq_{1},\alpha_{1})$ and
$\Pi_{2}=(\mathcal{V}_{2},\leq_{2},\alpha_{2})$ be two properties. The product
property $\Pi=(\mathcal{V},\leq,\alpha)$, denoted $\Pi=\Pi_{1}\times\Pi_{2}$,
takes values $\mathcal{V}=\mathcal{V}_{1}\times\mathcal{V}_{2}$, with the
partial order $(u_{1},u_{2})\leq(v_{1},v_{2})$ if and only if
$u_{1}\leq_{1}v_{2}$ and $u_{2}\leq_{2}v_{2}$, and abstraction function
$\alpha(p):=(\alpha_{1}(p),\alpha_{2}(p))$.

Here are some useful facts about the product property:

###### Lemma D.11.

Let $\Pi_{1}=(\mathcal{V}_{1},\leq_{1},\alpha_{1})$ and
$\Pi_{2}=(\mathcal{V}_{2},\leq_{2},\alpha_{2})$ be two properties, and let
$d_{1}$ and $d_{2}$ be distance functions on $\Pi_{1}$ and $\Pi_{2}$,
respectively. Denote their product property as
$\Pi=\Pi_{1}\times\Pi_{2}=(\mathcal{V},\leq,\alpha)$, and define a function
$d:\mathcal{P}\rightarrow\mathcal{V}$ as $d(p,(u,v))=d_{1}(p,u)+d_{2}(p,v)$.
Let $T\subseteq\mathcal{T}$ be a set of transformations. We have the following
facts:

  1. (0)

$\Pi$ is a program property (cf. Definition 2.1).

  2. (1)

$p\models u\in\mathcal{V}_{1}$ and $p\models v\in\mathcal{V}_{2}$ if and only
if $p\models(u,v)\in\mathcal{V}$.

  3. (2)

$d$ is a distance function for $\Pi$ (cf. Definition 4.1).

  4. (3)

If $T$ is monotonic with respect to $d_{1}$ and $d_{2}$, then $T$ is also
monotonic with respect to $d$.

  5. (4)

Let $T_{1}$ and $T_{2}$ be monotonic with respect to $d_{2}$ and $d_{1}$,
respectively, and define $T=T_{1}\cup T_{2}$.

    1. (a)

If $T_{1}$ is a covering for $\Pi_{1}$ (with respect to $d_{1}$), and $T_{2}$
is a covering for $\Pi_{2}$ (with respect to $d_{2}$), then $T$ is also a
covering for $\Pi$ (with respect to $d$).

    2. (b)

Furthermore, if $T_{1}$ and $T_{2}$ are both _uniform_ coverings, then so is
$T$.

From the first two facts, we see that for a synthesis task with multiple
properties, it suffices to solve the synthesis task on a single product
property. The next statement gives an easy way to construct a new distance
function for the product property, and the following statement says any set
which was monotonic for the individual distance functions is also monotonic
for this new distance function. We omit these proofs as they follow
immediately from the definitions.

Lemma D.11 (4a) and (4b) give sufficient conditions for constructing coverings
for the product property. Note that these statements are not true in general
without monotonicity—in fact, even if $T$ is a _uniform_ covering for both
$\Pi_{1}$ and $\Pi_{2}$, the following statements about the product property
$\Pi=\Pi_{1}\times\Pi_{2}$ are _false_ in general:

  1. (1)

$T$ is a covering for $\Pi$.

  2. (2)

if $T$ is a covering for $\Pi$, then $T$ is a uniform covering for $\Pi$.

Hence we see that monotonicity is the key to progressive synthesis over
multiple properties when taking the product.

###### Proof of Lemma D.11.

Given $p\in\mathcal{P},u\in\mathcal{V}_{1},v\in\mathcal{V}_{2}$, we first show
that if $0<d(p,(u,v))<\infty$, there exists $t\in T$ such that
$d(t(p),(u,v))<d(p,(u,v))$. Since $d(p,(u,v))=d_{1}(p,u)+d_{2}(p,v)>0$, and by
the definition of a distance function $d_{1}$ and $d_{2}$ are nonnegative, it
follows that at least one of $d_{1}$ or $d_{2}$ is also strictly positive.

Assume without loss of generality that $d_{1}(p,u)>0$. If $T_{1}$ is a
covering, it follows that there exists $t\in T_{1}$ such that
$d_{1}(t(p),u)<d_{1}(p,u)$. Since $d_{2}$ is monotonic with respect to
$T_{1}$, $d_{2}(t(p),v)\leq d_{2}(p,v)$. Adding these together yields that

(31) $\displaystyle d_{1}(t(p),u)+d_{2}(t(p),v)<d_{1}(p,u)+d_{2}(p,v)$

i.e.,

(32) $\displaystyle d(t(p),(u,v))<d(p,(u,v))$

Hence, $T$ is a covering for $d$, which proves Lemma D.11 (4a).

Furthermore, if $T_{1}$ is actually a _uniform_ covering for $d_{1}$ with
lower bound $\epsilon_{1}$, then there exists $t\in T_{1}$ such that
$d_{1}(t(p),u)+\epsilon_{1}<d_{1}(p,u)$. Hence,

(33) $\displaystyle
d_{1}(t(p),u)+d_{2}(t(p),v)+\epsilon_{1}<d_{1}(p,u)+d_{2}(p,v)$

i.e.,

(34) $\displaystyle d(t(p),(u,v))+\epsilon_{1}<d(p,(u,v))$

So $T$ is also a uniform covering for $d$ (with lower bound equal to the
minimum of the lower bounds for $d_{1}$ and $d_{2}$), which proves Lemma D.11
(4b). ∎

###### Proof of Theorem 4.7.

We will prove this by inducting on the number of properties $N$. If $N=1$,
then the statement is trivially true. Otherwise, assume the result holds for
$N=M$; we will show it holds for $M+1$.

We first prove the case when each $T_{i}$ is a covering for $d_{i}$,
respectively. By the inductive hypothesis, $T^{M}=\cup_{i=1}^{M}T_{i}$ is a
covering for the distance function
$d^{M}(p,S^{M})=\sum_{i=1}^{M}d_{i}(p,v_{i})$ with respect to the product
property $\Pi^{M}=\Pi_{1}\times\cdots\times\Pi_{M}$. By assumption, $T^{M}$ is
monotonic with respect to $d_{M+1}$, and by Lemma D.11 (4a), $T_{M+1}$ is
monotonic with respect to $d^{M}$. Hence, we can apply Lemma D.11 (4a) to
conclude that

(35) $\displaystyle T^{M+1}=T^{M}\cup T_{M+1}=\bigcup_{i=1}^{M+1}T_{i}$

is a covering for the distance function

(36) $\displaystyle d^{M+1}=d^{M}+d_{M+1}=\sum_{i=1}^{M+1}d_{i}$

with respect to the product property

(37)
$\displaystyle\Pi^{M+1}=\Pi^{M}\times\Pi_{M+1}=\Pi_{1}\times\cdots\times\Pi_{M+1}$

as desired.

If each $T_{i}$ is a uniform covering for $d_{i}$, then by the same argument,
we can conclude via Lemma D.11 (4b) that $T^{M+1}$ is a uniform covering for
$d^{M+1}$ with respect to $\Pi^{M+1}$. ∎

####  D.3.1. Weak uniform coverings

We conclude this section with a short technical note. Recall that for a set
$T$ to be a uniform covering of a distance function $d$, there must be some
constant $\epsilon>0$ such that if $d(p,v)>0$, then we can find a $t\in T$
such that $d(t(p),v)+\epsilon\leq d(p,v)$. A consequence of this definition is
that $d(p,v)<\epsilon$ implies that $d(p,v)=0$. It follows that if the
distance function $d$ can get arbitrarily small, it cannot be uniformly
covered.

We address this by introducing a weaker notion of uniform covering which can
be applied to distance functions that vanish:

###### Definition D.12.

A covering $T$ is a weak uniform covering if there exists a constant
$\epsilon>0$ such that for all programs $p\in\mathcal{P}$ and properties
$v\in\mathcal{V}$ with $d(p,v)>0$, there exists $t\in T$ such that

(38) $\displaystyle d(t(p),v)+\min(\epsilon,d(p,v))\leq d(p,v)$

For a single program property, a weak uniform covering $T$ is almost as good
as a uniform covering in that if $d(p,v)\geq\epsilon$, then searching over $T$
achieves the same uniform lower bound $\epsilon$; but if $d(p,v)<\epsilon$,
although the improvement achieved by searching over $T$ is not uniformly
bounded from below, it is still guaranteed to reach a distance of 0.

For multiple program properties, a subtle issue remains in that Lemma D.11
(4a) and (4b) do not hold for weak uniform coverings, i.e., if $T_{1}$ and
$T_{2}$ are _weak_ uniform coverings, then $T=T_{1}\cup T_{2}$ is only
guaranteed to be a covering (rather than a weak uniform covering). One way to
address this that $T^{2}$, the set of all _pairs_ of transformations from $T$,
is a weak uniform covering for $d=d_{1}+d_{2}$; however, this introduces a
quadratic factor to the dependence on the number of transformations in the
respective covering sets (and in general, for the product of of $n$ program
properties, we would need to search over transformations in $T^{n}$, which is
undesirable).

Fortunately, there is a simple way to convert a weak uniform covering into a
uniform covering that resolves this issue:

###### Lemma D.13.

If $T$ is a weak uniform covering for a distance function $d$, then there
exists another function $d^{\prime}$ such that $T$ is a uniform covering for
$d^{\prime}$.

###### Proof.

Assume that $T$ is a weak uniform covering with lower bound $\epsilon$. Define
the following function:

(39) $\displaystyle d^{\prime}(p,v)$ $\displaystyle:=\begin{cases}0,&\text{if
}d(p,v)=0\\\ d(p,v)+\epsilon&\text{otherwise}\end{cases}$

Clearly, $d^{\prime}$ is a distance function, and $T$ is a uniform covering
for $d^{\prime}$. ∎

###  D.4. Progressive Synthesis for NAS

Before presenting the next few results characterizing the depth, mixing, and
shape properties, we begin with a simple lemma that provides sufficient
conditions for a covering $T$ to be a uniform covering.

###### Lemma D.14.

If the image of the distance function $d$ is a discrete set (with the usually
topology on $\mathbb{R}$), then any covering $T$ is also a uniform covering.

We omit the proof as it follows immediately from the definitions. Since all
our distance functions take integer values, for the remainder of this section,
it suffices to show that the set of simple primitives $E_{s}$ is a covering.

The next three results culminate in the proof of Lemma 4.10, which says that
the set of primitive operations are monotonic for the mixing property.

###### Lemma D.15.

The set $\\{\texttt{x}{},\texttt{o}{},\texttt{m}{},\texttt{a}{}\\}$ along with
the operations $+$ and $*$ as defined in Lemma 3.7 forms a semi-ring.

###### Proof.

The additive identity $0$ is the element x, and the $\max$ operator is
commutative and reflexive. The multiplicative identity element is o, and the
annihilating element is x. Finally, $*$ distributes over $+$ from both the
right and the left. ∎

###### Corollary D.16.

The set of $m$-by-$m$ mixing properties form a semi-ring with the usual matrix
multiplication and element-wise addition.

In other words, the abstract interpretation in Lemma 3.7 is just
multiplication in the semi-ring of square matrices over
$\\{\texttt{x}{},\texttt{o}{},\texttt{m}{},\texttt{a}{}\\}$. Note that the
multiplicative identity element is the usual identity matrix $I_{m}$, where
the diagonal is $O$ and all other entries are $x$. As a mixing property, the
identity corresponds to an element-wise operation (e.g., a ReLU).

###### Proof of Lemma 4.10.

First, all (shape-preserving) operations preserve at least the diagonal, i.e.,
for all $e\in E_{s}$, we have that $\alpha_{M}(e)+I=\alpha_{M}(e)$. Let
$e_{n1}\circ\cdots\circ e_{11}=t_{1}\in\mathcal{T}_{s}$ and
$e_{m2}\circ\cdots\circ e_{12}=t_{2}\in\mathcal{T}_{s}$. Then following the
usual rules of matrix multiplication and addition, for any
$U\in\mathcal{V}_{M}$ we have

(40) $\displaystyle(t_{2})^{\alpha}_{M}((t_{1})^{\alpha}_{M}(U))$
$\displaystyle=\alpha_{M}(e_{m2})\cdots\alpha_{M}(e_{12})\,\times\,\alpha_{M}(e_{n1})\cdots\alpha_{M}(e_{11})\,\times\,U$
(41)
$\displaystyle=(I+\alpha_{M}(e_{m2}))\cdots(I+\alpha_{M}(e_{12}))\,\times\,(I+\alpha_{M}(e_{n1}))\cdots(I+\alpha_{M}(e_{11}))\,\times\,U$
(42)
$\displaystyle\geq(I+\alpha_{M}(e_{m2})\cdots\alpha_{M}(e_{12}))\,\times\,(I+\alpha_{M}(e_{n1})\cdots\alpha_{M}(e_{11}))\,\times\,U$

At this point, we either drop the second term on the right hand side to get:

(43) $\displaystyle(t_{2})^{\alpha}_{M}((t_{1})^{\alpha}_{M}(U))$
$\displaystyle\geq(I+\alpha_{M}(e_{m2})\cdots\alpha_{M}(e_{12}))\,\times\,U$
(44) $\displaystyle\geq\alpha_{M}(e_{m2})\cdots\alpha_{M}(e_{12})\,\times\,U$
(45) $\displaystyle=(t_{2})^{\alpha}_{M}(U)$

or drop the first term on the right hand side to get:

(46) $\displaystyle(t_{2})^{\alpha}_{M}((t_{1})^{\alpha}_{M}(U))$
$\displaystyle\geq(I+\alpha_{M}(e_{n1})\cdots\alpha_{M}(e_{11}))\,\times\,U$
(47) $\displaystyle\geq\alpha_{M}(e_{n1})\cdots\alpha_{M}(e_{11})\,\times\,U$
(48) $\displaystyle=(t_{1})^{\alpha}_{M}(U)$

Putting these together yields $(t^{\alpha}_{2}\circ
t^{\alpha}_{1})(U)\geq\max(t^{\alpha}_{2}(U),t^{\alpha}_{1}(U))$ as desired. ∎

###### Proof of Theorem 4.8.

We will apply Theorem 4.7 to the depth, mixing, and shape properties. From
Theorems 4.12 and 4.11, we have that the set of simple primitives $E_{s}$ is a
uniform monotone covering of both the depth and mixing properties,
respectively. From Theorem 4.14, we have that $E_{s}$ is a uniform covering of
the shape property. Hence, all we need to show is that $E_{s}\cap M_{S}$,
where $M_{S}$ is the set of monotonic transformations for the shape property,
is also a uniform covering of the depth and mixing properties.

Note that $M_{S}$ consists exactly of the set of operations that preserve the
shape of their input tensor. Only 3 operations cause a change in the shape of
their input tensor: (1) pooling operations, (2) dense layers with a different
number of output features, and (3) convolution layers with a different number
of output features. For the mixing property, the remaining variants that do
not change the number of output features are equivalent in the abstract
semantics but still preserve their output shapes. Hence, removing (2) and (3)
still leaves a uniform covering. For the pooling operations, these introduce
many-to-one locality between the spatial dimensions, but this can be achieved
by a convolution layer (that also preserves the shape). Hence, $E_{s}\cap
M_{S}$ is also a uniform covering of the mixing property. For the depth
property, removing these operations clearly still leaves a uniform covering. ∎


# Davenport constant with weights

Pingzhi Yuan
School of Mathematics, South China Normal University , Guangzhou 510631,
P.R.CHINA
e-mail<EMAIL_ADDRESS>
Xiangneng Zeng
Department of Mathematics, Sun Yat-Sen University, Guangzhou 510275, P.R.CHINA

###### Abstract

For the cyclic group $G=\mathbb{Z}/n\mathbb{Z}$ and any non-empty
$A\in\mathbb{Z}$. We define the Davenport constant of $G$ with weight $A$,
denoted by $D_{A}(n)$, to be the least natural number $k$ such that for any
sequence $(x_{1},\cdots,x_{k})$ with $x_{i}\in G$, there exists a non-empty
subsequence $(x_{j_{1}},\,\cdots,\,x_{j_{l}})$ and $a_{1},\,\cdots,\,a_{l}\in
A$ such that $\sum_{i=1}^{l}a_{i}x_{j_{i}}=0$. Similarly, we define the
constant $E_{A}(n)$ to be the least $t\in\mathbb{N}$ such that for all
sequences $(x_{1},\,\cdots,\,x_{t})$ with $x_{i}\in G$, there exist indices
$j_{1},\,\cdots,\,j_{n}\in\mathbb{N},1\leq j_{1}<\cdots<j_{n}\leq t$, and
$\vartheta_{1},\,\cdots,\,\vartheta_{n}\in A$ with
$\sum^{n}_{i=1}\vartheta_{i}x_{j_{i}}=0$. In the present paper, we show that
$E_{A}(n)=D_{A}(n)+n-1$. This solve the problem raised by Adhikari and Rath
[3], Adhikari and Chen [2], Thangadurai [12] and Griffiths [10].

MSC: 11B50

Key words: Zero-sum problems, weighted EGZ, zero-sum free sequences.

00footnotetext:  Supported by the Guangdong Provincial Natural Science
Foundation (No. 8151027501000114) and NSF of China (No. 10571180).

##  1 Introduction

For an abelian group $G$, the Davenport constant $D(G)$ is defined to be the
smallest natural number $k$ such that any sequence of $k$ elements in $G$ has
a non-empty subsequence whose sum is zero (the identity element). Another
interesting constant $E(G)$ is defined to be the smallest natural number $k$
such that any sequence of $k$ elements in $G$ has a subsequence of length
$|G|$ whose sum is zero.

The following result due to Gao [7] connects these two invariants.

###### Theorem 1.1

If $G$ is a finite abelian group of order $n$, then $E(G)=D(G)+n-1$.

For a finite abelian group $G$ and any non-empty $A\in\mathbb{Z}$, Adhikari
and Chen [2] defined the Davenport constant of $G$ with weight $A$, denoted by
$D_{A}(G)$, to be the least natural number $k$ such that for any sequence
$(x_{1},\cdots,x_{k})$ with $x_{i}\in G$, there exists a non-empty subsequence
$(x_{j_{1}},\,\cdots,\,x_{j_{l}})$ and $a_{1},\,\cdots,\,a_{l}\in A$ such that
$\sum_{i=1}^{l}a_{i}x_{j_{i}}=0$. Clearly, if $G$ is of order $n$, it is
equivalent to consider $A$ to be a non-empty subset of $\\{0,1,\cdots,n-1\\}$
and cases with $0\in A$ are trivial.

Similarly, for any such set $A$, for a finite abelian group $G$ of order $n$,
the constant $E_{A}(G)$ is defined to be the least $t\in\mathbb{N}$ such that
for all sequences $(x_{1},\,\cdots,\,x_{t})$ with $x_{i}\in G$, there exist
indices $j_{1},\,\cdots,\,j_{n}\in\mathbb{N},1\leq j_{1}<\cdots<j_{n}\leq t$,
and $\vartheta_{1},\,\cdots,\,\vartheta_{n}\in A$ with
$\sum^{n}_{i=1}\vartheta_{i}x_{j_{i}}=0$.

For the group $G=\mathbb{Z}/n\mathbb{Z}$, we write $E_{A}(n)$ and $D_{A}(n)$
respectively for $E_{A}(G)$ and $D_{A}(G)$. In the cases
$A=\\{1\\},\,\\{-1,\,1\\},\mathbb{Z}_{n}^{\star}$ or $A=(a_{1},\cdots,a_{r})$
with $\gcd(a_{2}-a_{1},\cdots,a_{r}-a_{1},n)=1$ or $n=p$ is a prime, it is
proved that $E_{A}(n)=D_{A}(n)+n-1$. The following conjecture has been raised
by Adhikari and Rath [3], Adhikari and Chen [2], Thangadurai [12] and
Griffiths [10], they seems to believe that Conjecture 1.1 is true and have
proved it in some special cases.

###### Conjecture 1.1

For any non-empty set $A\in\mathbb{Z}$, $E_{A}(n)=D_{A}(n)+n-1$.

The main purpose of the present paper is to prove Conjecture 1.1. By using the
main theorem of Devos, Goddyn and Mohar [5] and a recently proved theorem of
the authors [13], we shall prove the following theorem

###### Theorem 1.2

For any non-empty set $A\in\mathbb{Z}$, $E_{A}(n)=D_{A}(n)+n-1$.

Throughout this paper, let $G$ be an additive finite abelian group.
$\mathcal{F}(G)$ denotes the free abelian monoid with basis $G$, the elements
of which are called $sequences$ (in $G$). A sequence of not necessarily
distinct elements from $G$ will be written in the form
$S=g_{1}\,\cdots\,g_{k}=\prod_{i=1}^{k}g_{i}=\prod_{g\in
G}g^{\mathsf{v}_{g}(S)}\in\mathcal{F}(G)$, where $\mathsf{v}_{g}(S)\geq 0$ is
called the $multiplicity$ of $g$ in $S$. We call $|S|=k$ the $length$ of $S$,
$\mathsf{h}(S)=\max\\{\mathsf{v}_{g}(S)|g\in G\\}\in[0,|S|]$ the maximum of
the multiplicities of $S$, ${\rm supp}(S)=\\{g\in G:\,\mathsf{v}_{g}(S)>0\\}$
the $support$ of $S$. For every $g\in G$ we set
$g+S=(g+g_{1})\cdots(g+g_{k})$.

We say that $S$ contains some $g\in G$ if $\mathsf{v}_{g}(S)\geq 1$ and a
sequence $T\in\mathcal{F}(G)$ is a $subsequence$ of $S$ if
$\mathsf{v}_{g}(T)\leq\mathsf{v}_{g}(S)$ for every $g\in G$, denoted by $T|S$.
Furthermore, by $\sigma(S)$ we denote the sum of $S$, (i.e.
$\sigma(S)=\sum_{i=1}^{k}g_{i}=\sum_{g\in G}\mathsf{v}_{g}(S)g\in G$). For
every $k\in\\{1,2,\cdots,\,|S|\\}$, let
$\sum_{k}(S)=\\{g_{i_{1}}+\cdots+g_{i_{k}}|1\leq
i_{1}<\cdots<i_{k}\leq|S|\\},\,\sum_{\leq k}(S)=\cup_{i=1}^{k}\sum_{i}(S)$,
and let $\sum(S)=\sum_{\leq|S|}(S)$.

Let $S$ be a sequence in $G$. We call $S$ a $zero-sum$ $sequence$ if
$\sigma(S)=0$.

Also, we follow the same terminologies and notations as in the survey article
[8] or in the book [9].

##  2 Lemmas

First, we need a result on the sum of $l$ finite subsets of $G$. If ${\bf
A}=(A_{1},A_{2},\cdots,A_{m})$ is a sequence of finite subsets of $G$, and
$l\leq m$, we define

$\sum_{l}({\bf A})=\\{a_{i_{1}}+\cdots+a_{i_{l}}:1\leq i_{1}<\cdots<i_{l}\leq
m\,\mbox{ and}\,a_{i_{j}}\in A_{i_{j}}\,\mbox{ for every}\,1\leq j\leq l\\}.$

So $\sum_{l}({\bf A})$ is the set of all elements which can be represented as
a sum of $l$ terms from distinct members of ${\bf A}$. The following is the
main result of Devos, Goddyn and Mohar [5].

Theorem DGM Let ${\bf A}=(A_{1},A_{2},\cdots,A_{m})$ be a sequence of finite
subsets of $G$, let $l\leq m$, and let $H=stab(\sum_{l}({\bf A}))$. If
$\sum_{l}({\bf A})$ is nonempty, then

$|\sum_{l}({\bf A})|\geq|H|(1-l+\sum_{Q\in
G/H}\min\\{l,|\\{i\in\\{1,\cdots,m\\}:A_{i}\cap Q\neq\emptyset\\}|\\}).$

We still need the following new result on Davenport’s constant [13].

Theorem YZ Let $G$ be a finite abelian group of order $n$ and Davenport
constant $D(G)$. Let $S=0^{\mathsf{h}(S)}\prod_{g\in
G}g^{\mathsf{v}_{g}(S)}\in\mathcal{F}(G)$ be a sequence with a maximal
multiplicity $\mathsf{h}(S)$ attained by $0$ and $|S|=t\geq n+D(G)-1$. Then
there exists a subsequence $S_{1}$ of $S$ with length $|S_{1}|\geq t+1-D(G)$
and $0\in\sum_{k}(S_{1})$ for every $1\leq k\leq|S_{1}|$. In particular, for
every sequence $S$ in $G$ with length $|S|\geq n+D(G)-1$, we have

$0\in\sum_{km}(S),\,\mbox{ for every }\quad 1\leq k\leq(|S|+1-D(G))/m,$

where $m$ is the exponent of $G$.

##  3 Proof of Theorem 1.2

  * Proof.

The proof of $E_{A}(n)\geq D_{A}(n)+n-1$ is easy, so it is sufficient to prove
the reverse inequality.

For any non-empty set $A=\\{a_{1},\cdots a_{r}\\}\subset\mathbb{Z}$ and a
cyclic group $G=\mathbb{Z}/n\mathbb{Z}$, let $t=D_{A}(n)+n-1$ and
$S=x_{1}\cdots x_{t}$ is any sequence in $G$ with length $|S|=t=D_{A}(n)+n-1$.
Put

$A_{i}=Ax_{i}=\\{a_{1}x_{i},\cdots,a_{r}x_{i}\\}\mbox{ for}\,i=1,\cdots,t$

and ${\bf A}=(A_{1},\,\cdots,\,A_{t})$. It suffices to prove that
$0\in\sum_{n}({\bf A})$.

We shall assume (for a contradiction) that the theorem is false and choose a
counterexample $(A,G,\,S)$ so that $n=|G|$ is minimum, where $G$ is a cyclic
group of order $n$, $A$ is a finite subset of $\mathbb{Z}$ and $S=x_{1}\cdots
x_{t}$ is a sequence in $G$ such that

$0\not\in\sum_{n}({\bf A}).$

Next we will show that our assumptions imply $H=stab(\sum_{n}({\bf
A}))=\\{0\\}$. Suppose (for a contradiction) that $H=stab(\sum_{n}({\bf
A}))\neq\\{0\\}$ and let $\varphi:\,G\longrightarrow G/H$ denote the canonical
homomorphism and $\varphi(x_{i})$ the image of $x_{i}$ for $1\leq i\leq t$.
Let ${\bf A_{\varphi}}=(\varphi(A_{1}),\cdots,\varphi(A_{t}))$. By our
assumption for the minimal of $|G|$, the theorem holds for
$(A,\varphi(G),\,\varphi(S))$. Since $n>|\varphi(G)|+D_{A}(\varphi(G))-1$,
$|\varphi(G)||n$ and $D_{A}(G)\geq D_{A}(\varphi(G))$, repeated applying the
theorem to the sequence $\varphi(S)=\varphi(x_{1}),\cdots,\varphi(x_{t})$ we
have

$\varphi(0)=\varphi(H)\in\sum_{n}({\bf A_{\varphi}}),$

thus $0\in H\subset\sum_{n}({\bf A})$. This contradiction implies that
$H=stab(\sum_{n}({\bf A}))=\\{0\\}$.

If there is an element $a\in G$ such that $|\\{j\in\\{1,\cdots,t\\}:a\in
A_{j}\\}|\geq n$, then $0\in\sum_{n}({\bf A})$, a contradiction. Therefore we
may assume that for every $a\in G$, $|\\{j\in\\{1,\cdots,t\\}:a\in
A_{j}\\}|\leq n$. Let $r$ be the number of $i\in\\{1,\cdots,t\\}$ with
$|A_{i}|=1$, by Theorem DGM and the assumptions, we have

$n-1\geq\sum_{n}({\bf A})\geq 1-n+\sum_{a\in
G}\min\\{n,|\\{j\in\\{1,\cdots,t\\}:a\in A_{j}\\}|\\}$
$=1-n+\sum_{i=1}^{t}|A_{i}|\geq 1-n+2(n+D_{A}(G)-1-r)+r.$

It follows that

$r\geq 2D_{A}(G).$ (1)

Without loss of generality, we may assume that $x_{1},\cdots,x_{r}$ are all
the elements in $\\{x_{1},\,\cdots,\,x_{t}\\}$ such that $|A_{i}|=1$, and
$x_{1}$ is the element in $\\{x_{1},\,\cdots,\,x_{r}\\}$ such that
$a_{1}x_{1}$ attains the maximal multiplicity in the sequence
$S_{1}=(a_{1}x_{1})\cdots(a_{1}x_{r})$. Observe that $\sum_{n}({\bf
A})=\sum_{n}(A(x_{1}-x_{u}),\,\cdots,\,A(x_{t}-x_{u}))$ for every $1\leq u\leq
r$. Therefore without loss of generality we may assume that $a_{1}x_{1}=0$ and
$\mathsf{v}_{0}(S_{1})=\mathsf{h}(S_{1})$ for the sequence

$S_{1}=(a_{1}x_{1})\cdots(a_{1}x_{r})=0^{\mathsf{h}(S_{1})}(a_{1}x_{\mathsf{h}(S_{1})+1})\cdots(a_{1}x_{r}).$
(2)

Let $H_{1}=<x_{1},\cdots,x_{r}>$ be the group generated by
$x_{1},\cdots,x_{r}$, $H=a_{1}H_{1}$. We have the following claim.

Claim: $D_{A}(G)\geq D_{A}(H_{1})\geq D(H)=|H|$.

The last equality of the Claim follows from the fact that $H$ is a subgroup of
the cyclic group $G$. The first inequality in the Claim is obvious, so we only
need to prove that $D_{A}(H_{1})\geq D(H)$. Suppose that $W=y_{1}\cdots
y_{D(H)-1}$ is a zero-sum free sequence in $H$. Since $H=a_{1}H_{1}$, we have
$y_{i}=a_{1}w_{i},w_{i}\in H_{1},i=1,\cdots r$. Further, it is easy to see
that $Aw_{i}=a_{1}w_{i},\,i=1,\cdots,r$ by the definition of $H_{1}$, so
$w_{1}\cdots w_{D(H)-1}$ is a zero-sum free sequence in $H_{1}$ with respect
to the weight $A$, thus $D_{A}(H_{1})\geq D(H)$ and the Claim follows.

By the Claim, (1), (2) and Theorem YZ, $S_{1}$ has a subsequence $S_{2}$ of
length $|S_{2}|=s\geq r+1-|H|$ such that $0\in\sum_{l}(S_{2})$ for every
$1\leq l\leq s$. Without loss of generality, we may assume that
$S_{2}=(a_{1}x_{1})\cdots(a_{1}x_{s})$.

If $s\geq n$ then $0\in\sum_{n}(S_{2})\subset\sum_{n}({\bf A})$, we are done.

If $s<n$, then $|x_{s+1}\cdots x_{t}|=t-s=n-1+D_{A}(G)-s\geq D_{A}(G)$.
Repeated using the definition of $D_{A}(G)$, there exists an integer $v$ such
that $v\leq n,\,t-s-v\leq D_{A}(G)-1$ and

$0\in\sum_{v}((A_{s+1},\cdots A_{t})).$

Since $\sum_{l}(S_{2})=\sum_{l}((A_{1},\cdots,A_{s}))$ and
$0\in\sum_{l}((A_{1},\cdots,A_{s}))$ for every $1\leq l\leq s$, we have

$0\in\sum_{v+k}({\bf A})\quad\mbox{ for every }0\leq k\leq s.$

Therefore $0\in\sum_{n}({\bf A})$ since $v+s\geq t+1-G_{A}(G)\geq n$. This
completes the proof of the theorem.

$\Box$

## References

  * [1] S.D. Adhikari, Y.G. Chen, J.B. Friedlander, S.V. Konyagin, F. Pappalardi, Contributions to zero-sum problems, Discrete Math. 306 (2006) 1-10.
  * [2] S.D. Adhikari, Y.G. Chen, Davenport constant with weights and some related questions, II, J. Combin. Theory Theory Ser.A 115(2008), 178-184.
  * [3] S.D. Adhikari, P. Rath, Davenport constant with weights and some related questions, Integers, Paper A 6 (2006) 30.
  * [4] S.D. Adhikari, P. Rath, Zero-sum problems in Combinatorial Number Theory, in: R. Balasubramanian, K. Srinivas (Eds.), The Riemann Zeta Function and Related Themes: Papers in Honour of Professor K. Ramachandra, Proceedings of International Conf. Held at National Institute of Advanced Studies, Bangalore, 13-15 December, 2003, in: Ramanujan Math. Soc. Lect. Notes Ser., vol. 2, 2006.
  * [5] M. DeVos, L. Goddyn and B. Mohar, A generalization of Kneser’s addition theorem, Advance in Mathematics (to appear).
  * [6] P. Erd$\ddot{o}$s, A. Ginzburg, A. Ziv, Theorem in the additive number theory, Bull. Res. Council Israel 10F (1961) 41-43.
  * [7] W.D. Gao, A combinatorial problem on finite abelian groups, J. Number Theory 58 (1996) 100-103.
  * [8] W.D. Gao, A. Geroldinger, Zero-sum problems in finite abelian groups: A survey, Expo. Math. 24 (2006) 337-369.
  * [9] A. Geroldinger, F. Halter-Koch, Non-Unique Factorizations, Chapman and Hall/CRC, 2006.
  * [10] The Erd$\ddot{o}$s-Ginzberg-Ziv theorem with units, Discrete Mathematics 308(2008), 5473-5484.
  * [11] Florian Luca, A generalization of a classical zero-sum problem, Discrete Math. 307(2007) 1672-1678.
  * [12] Thangadurai R, A variant of Davenport’s constant, Proc. Indian Acad. Sci. (Math. Sci.) 117(2007), 147-158.
  * [13] P. Yuan and X. Zeng, A new result on Davenport’s constant, submitted.