Department of Computer Science
University of California at Riverside Department of Computer Science
University of California at RiversideThe copyright is retained by the authors
Research supported by NSF grant CCF-1536026.

# Towards a Theory of Mixing Graphs: A Characterization of Perfect Mixability

Miguel Coviello Gonzalez  and  Marek Chrobak$\star$

###### Abstract.

Some microfluidic lab-on-chip devices contain modules whose function is to mix
two fluids, called reactant and buffer, in desired proportions. In one of the
technologies for fluid mixing the process can be represented by a directed
acyclic graph whose nodes represent micro-mixers and edges represent micro-
channels. A micro-mixer has two input channels and two output channels; it
receives two fluid droplets, one from each input, mixes them perfectly, and
produces two droplets of the mixed fluid on its output channels. Such a mixing
graph converts a set $I$ of input droplets into a set $T$ of output droplets,
where the droplets are specified by their reactant concentrations. The most
fundamental algorithmic question related to mixing graphs is to determine,
given an input set $I$ and a target set $T$, whether there is a mixing graph
that converts $I$ into $T$. We refer to this decision problem as _mix-
reachability_. While the complexity of this problem remains open, we provide a
solution to its natural sub-problem, called _perfect mixability_ , in which we
ask whether, given a collection $C$ of droplets, there is a mixing graph that
mixes $C$ perfectly, producing only droplets whose concentration is the
average concentration of $C$. We provide a complete characterization of such
perfectly mixable sets and an efficient algorithm for testing perfect
mixability. Further, we prove that any perfectly mixable set has a perfect-
mixing graph of polynomial size, and that this graph can be computed in
polynomial time.

###### Key words and phrases:

algorithms, graph theory, lab-on-chip, fluid mixing

###### 1991 Mathematics Subject Classification:

[500]Discrete Mathematics Combinatorial Optimization $\bullet$ [500]Theory of
Computation Network Flows

##  1\. Introduction

_Microfluidics_ is an area of science and engineering dedicated to the study
and manipulation of very small (picoliter to nanoliter [6]) amounts of fluids.
Research advances in microfluidics led to the development of _lab-on-chip_
(LoC) devices that integrate on a small chip various functions of bulky and
costly biochemical systems, including dispensing, mixing, and filtering of
fluids, particle separation, and detection of chemicals. LoCs play
increasingly important roles in applications that include cancer research
[10], environment monitoring [11], protein analysis [18], drug discovery [3]
and physiological sample analysis [16]. The importance of LoC devices will
soon scale up with the introduction of _cloud laboratories_ [4], which give
researchers access to state-of-the-art equipment and data analysis tools and
allow them to carry out their experiments remotely.

One of the most fundamental functions of LoC devices is _mixing_ of different
fluids. In particular, in applications related to sample preparation, the
objective is to produce desired volumes of pre-specified mixtures of fluids.
In typical applications only two fluids are involved, in which case the
process of mixing is often referred to as _dilution_. The fluid to be diluted
is called _reactant_ and the diluting fluid is called _buffer_. For example,
in clinical diagnostics common reactants include blood, serum, plasma and
urine, while phosphate buffered saline is often used as buffer [16].

There is a variety of different technologies that can be used to manufacture
microfluidic devices for fluid mixing. In our work, we consider microfluidic
chips that involve a collection of tiny components called _micro-mixers_
connected by _micro-channels_. In such chips, input fluids are injected into
the chip using fluid dispensers, then they travel, following appropriate
micro-channels, through a sequence of micro-mixers in which they are subjected
to mixing operations, and are eventually discharged into output reservoirs. We
focus on _droplet-based_ chips, where fluids are manipulated in discrete units
called _droplets_. In such chips each micro-mixer has exactly two input and
two output channels. It receives one droplet of fluid from each input, mixes
them perfectly, producing two identical droplets on its outputs. Specifically,
if the input droplets have (reactant) concentrations $a,b$, then the produced
droplets will have concentration ${\textstyle\frac{1}{2}}(a+b)$. It follows
that all droplets flowing through the chip have concentrations of the form
$c/2^{d}$, where $c$ and $d\geq 0$ are integers. This simply means that their
binary representations are finite, and we will refer to such numbers simply as
_binary numbers_. Throughout the paper we will assume (often tacitly) that all
concentration values are binary numbers. In this representation, the number
$d$, called _precision_ , is the number of fractional bits (assuming $c$ is
odd when $d\geq 1$).

Processing of droplets on such chips can be naturally represented by a
directed acyclic graph $G$ that we call a _mixing graph_. The edges of $G$
represent micro-channels. Source vertices (with in-degree $0$ and out-degree
$1$) represent dispensers, internal vertices (with in-degree and out-degree
$2$) represent micro-mixers, and sink vertices (with in-degree $1$ and out-
degree $0$) represent output reservoirs. Given a set $I$ of input droplets
injected into the source nodes, $G$ will convert it into a set $T$ of droplets
in its sink nodes. We refer to this set $T$ as a _target set_. An example of a
mixing graph is shown in Figure 1. Here, and elsewhere in the paper, we
represent each droplet by its reactant concentration (which uniquely
determines the buffer concentration, as both values add up to $1$).

Figure 1. A mixing graph that produces target set
$T={\left\\{{\textstyle\frac{1}{8}},{\textstyle\frac{5}{16}},{\textstyle\frac{5}{16}},{\textstyle\frac{1}{2}},{\textstyle\frac{3}{4}}\right\\}}$
from input set $I={\left\\{0,0,0,1,1\right\\}}$. Numbers on the micro-mixers
(internal nodes) represent droplet concentrations produced by these mixers.

There is growing literature in the embedded systems and bioengineering
communities on designing microfluidic chips represented by such mixing graphs.
The most fundamental algorithmic problem emerging in this area is the
following:

:

MixReachability: Given an input set $I$ and a target set $T$ of droplets with
given reactant concentrations, design (if at all possible) a mixing graph that
converts $I$ into $T$.

If there is a mixing graph that converts $I$ into $T$ then we say that $T$ is
_mix-reachable_ , or just _reachable_ , from $I$. For $T$ to be reachable from
$I$, clearly, $I$ and $T$ must have the same cardinality and equal reactant
volumes. However, these conditions are not sufficient. For example,
$T={\left\\{{\textstyle\frac{1}{4}},{\textstyle\frac{3}{4}}\right\\}}$ is not
reachable from $I={\left\\{0,1\right\\}}$ (or from any other input set
consisting only of pure buffer and reactant droplets), because producing
${\textstyle\frac{1}{4}}$ requires at least two buffer droplets and one
reactant droplet, but $T$ itself contains only two droplets.

In typical applications the input set $I$ consists of pure reactant and buffer
droplets (that is, only $0$’s and $1$’s). We denote this variant by
MixProducibility, and target sets reachable from such input sets are caled
_mix-producible_ , or just _producible_. MixProducibility is not likely to be
computationally easier than MixReachability. If ${\cal A}$ is an algorithm
that solves MixProducibility then, via a simple linear mapping, it can also
solve the variant of MixReachability where the input set has droplets of _any_
two given concentrations (instead of $0$ and $1$). Further, consider the
family ${\left\\{C_{i}\right\\}}$ of concentration sets produced by up to some
constant number $k$ of mixing operations from $I$. Then ${\cal A}$ in fact
determines whether $T$ is reachable from at least one $C_{i}$, yet these sets
$C_{i}$ have up to $k+2$ different concentrations. While we do not have a
formal reduction, these properties indicate that taking advantage of the
special form of inputs in MixProducibility may be challenging.

Related work. The previous work in the literature focuses on designing mixing
graphs that dilute the reactant to produce some desired concentrations – that
is on the MixProducibility problem. To generate target sets that are not
producible, one can consider mixing graphs that besides a target set $T$ also
produce some amount of superfluous fluid called _waste_. If we allow waste
then, naturally, MixProducibility can be extended to an optimization problem
where the objective is to design a mixing graph that generates $T$ while
minimizing waste. Alternative objective functions have been studied, for
example minimizing the reactant waste, minimizing the number of micro-mixers,
and other.

Most of the previous papers on this topic study designing mixing graphs using
heuristic approaches. Earlier studies focused on producing _single-
concentration targets_ , where only one droplet of some desired concentration
is needed. This line of research was pioneered by Thies et al. [17], who
proposed an algorithm called Min-Mix that constructs a mixing graph for a
single target droplet. Roy et al. [14] developed a single-droplet algorithm
called DMRW that considered waste reduction and the number of mixing
operations. Huang et al. [7] and Chiang et al. [1] proposed single-droplet
algorithms designed to minimize reactant usage.

Many applications, however, require target sets with multiple concentrations
(see, for example, [19, 18, 15, 16, 5]). Target sets that arise in sample
preparation typically involve concentration values that form arithmetic or
geometric sequences (referred to, respectively, as “linear” and “logarithmic”
in some literature – see, for example [9]), but the special form of such sets
does not seem to facilitate the design of mixing graphs. For multiple-
concentration targets, Huang et al. [8] proposed an algorithm called WARA,
which is an extension of Algorithm REMIA from [7]. Mitra et al. [13] model the
problem of producing multiple concentrations as an instance of the Asymmetric
TSP on a de Brujin graph.

The papers cited above describe heuristic algorithms with no formal
performance guarantees. Dinh et al. [2] take a more rigorous approach. They
model the problem as an equal-split flow problem [12] on a “universal” graph
that contains all possible mixing graphs of depth at most $d$ as subgraphs,
where $d$ is the maximum precision in $T$. By assigning appropriate capacity
and cost values to edges, the problem of extracting a mixing subgraph that
minimizes waste can be represented as an integer linear program, resulting in
an algorithm that is doubly exponential in $d$. Unfortunately, contrary to the
claim in [2], their algorithm does not necessarily produce mixing graphs with
minimum waste. The reason is, as we show in Appendix A, that there are target
sets with maximum precision $d$ that require mixing graphs of depth larger
than $d$ to be produced without waste.

Our results. To our knowledge, the computational complexity of MixReachability
is open; in fact, (given the flaw in [2] mentioned above) it is not even known
whether the MixProducibility variant is decidable. This paper reports partial
progress towards resolving this problem. We consider the following sub-problem
of MixReachability:

:

PerfectMixability: Given a set $C$ of $n$ droplets with binary concentrations
and binary average value $\mu=(\sum_{c\in C}c)/n$, is there a mixing graph
that mixes $C$ perfectly, converting $C$ into the set of $n$ droplets of
concentration $\mu$?

Figure 2. A mixing graph that perfectly mixes set
$C={\left\\{{\textstyle\frac{1}{16}},{\textstyle\frac{3}{16}},{\textstyle\frac{7}{32}},{\textstyle\frac{11}{32}},{\textstyle\frac{7}{16}}\right\\}}$.

Figure 2 shows an example of a perfect-mixing graph. As an example of a set
that is not perfectly mixable, consider
$D={\left\\{0,{\textstyle\frac{3}{16}},{\textstyle\frac{9}{16}}\right\\}}$.
After any (non-zero) number of mixing operations the resulting set of
concentrations will have the form $D^{\prime}={\left\\{a,a,b\right\\}}$ for
$a\neq b$, so no finite mixing graph will convert $D$ into its perfect mixture
${\left\\{{\textstyle\frac{1}{4}},{\textstyle\frac{1}{4}},{\textstyle\frac{1}{4}}\right\\}}$.

In this paper, addressing the PerfectMixability problem, we provide a complete
characterization of perfectly mixable droplet sets (with binary concentration
values), and show that there is a polynomial-time algorithm that tests whether
a given set is perfectly mixable, and if so, constructs a polynomial-size
perfect-mixing graph for it.

We represent droplet sets as multisets of concentration values. First, we
observe that without loss of generality we can assume that
$C\cup{\left\\{\mu\right\\}}{\,\sqsubset\,}{\mathbb{Z}}$, for otherwise we can
simply rescale all values by an appropriate power of $2$. (${\mathbb{Z}}$ is
the set of integers; ${\mathbb{Z}_{>0}}$ and ${\mathbb{Z}_{\geq 0}}$ are the
sets of positive and non-negative integers, respectively. Symbol
${\,\sqsubset\,}$ is used to specify a ground set of a multiset.) For any
finite multiset $A{\,\sqsubset\,}{\mathbb{Z}}$ and $b\in{\mathbb{Z}_{>0}}$, we
define $A$ to be _$b$ -congruent_ if $x\equiv y\pmod{b}$ for all $x,y\in A$.
(Otherwise we say that $A$ is _$b$ -incongruent_.)

We say that $C$ satisfies _Condition(MC)_ if, for each odd
$b\in{\mathbb{Z}_{>0}}$, if $C$ is $b$-congruent then
$C\cup{\left\\{\mu\right\\}}$ is $b$-congruent as well, where
$\mu={\textsf{ave}}(C)$. The following theorem summarizes our results.

######  Theorem 1.1.

Assume that $n\geq 4$ and
$C\cup{\left\\{\mu\right\\}}{\,\sqsubset\,}{\mathbb{Z}}$, where
$\mu={\textsf{ave}}(C)$. Then:

(a):

$C$ is perfectly mixable if and only if $C$ satisfies Condition (MC).

(b):

If $C$ satisfies Condition (MC) then it can be perfectly mixed with precision
at most $1$ and in a polynomial number of steps. (That is, $C$ has a perfect-
mixing graph of polynomial size where all intermediate concentration values
are half-integral.)

(c):

There is a polynomial-time algorithm that tests whether $C$ is perfectly
mixable and, if so, computes a polynomial-size perfect-mixing graph for $C$.

Part (b) implies that, in general (if the concentrations in
$C\cup{\left\\{\mu\right\\}}$ are arbitrary binary values), if $C$ is
perfectly mixable at all then $C$ can be mixed perfectly with precision at
most $d+1$, where $d$ is the maximum precision in
$C\cup{\left\\{\mu\right\\}}$; in other words, at most one extra bit of
precision is needed in the intermediate nodes of a perfect-mixing graph for
$C$.

This extra 1-bit of precision in part (b) of Theorem 1.1 is necessary. For
example, $C={\left\\{0,0,0,3,7\right\\}}$ (for which $\mu=2$) cannot be mixed
with precision $0$. If we mix $3$ and $7$, we will obtain multiset
${\left\\{0,0,0,5,5\right\\}}$ which is not perfectly mixable, as it violates
Condition (MC). Any other mixing creates fractional values. However, $C$ does
have a mixing graph where the intermediate precision is at most $1$ — see
Figure 3.

Figure 3. A perfect mixing graph for $C={\left\\{0,0,0,3,7\right\\}}$ with
precision $1$.

Note that in Theorem 1.1 we assume that $n=|C|\geq 4$. Regarding smaller
values of $n$, for $n\leq 2$, trivially, all configurations $C$ with at most
two droplets are perfectly mixable with precision $0$. The case $n=3$ is
exceptional, as in this case Theorem 1.1 is actually false. (For example,
consider configuration $C={\left\\{0,1,5\right\\}}$, for which $\mu=2$. This
configuration is $b$-incongruent for all odd $b>1$, so it satisfies condition
(MC), but is not perfectly mixable.) Nevertheless, for $n=3$, perfectly
mixable configurations are easy to characterize: Let
$C={\left\\{a,b,c\right\\}}$, where $a\leq b\leq c$. Then $C$ is perfectly
mixable if and only if $b={\textstyle\frac{1}{2}}(a+c)$. Further, if this
condition holds, $C$ is perfectly mixable with precision $0$. (That this
condition is sufficient is obvious. That it is also necessary can be proven by
following the argument for the example configuration $D$ right after the
definition of PerfectMixability.)

To clarify the polynomial bounds in Theorem 1.1, we assume that the input
configuration $C$ is specified by listing the concentration values of
individual droplets, and its size is the total number of bits used in this
representation. For the sake of concretness, we will assume that $C$ is
already rescaled to consist only of integers, and we will define the input
size as $s(C)=\sum_{c\in C}\log(|c|+2)$. This value is within a small constant
factor of the actual number of bits representing $C$. Consequently, the
polynomial bounds in Theorem 1.1 are with respect to $s(C)$.

Overview of the paper. The proof of Theorem 1.1 is given in several sections.
The necessity of Condition (MC) in Theorem 1.1(a) is relatively simple to
show; the proof appears in Section 3. The proof that Condition (MC) is
sufficient is more challenging. We first show in Section 4 (see Corollary 4.7)
that, in essence, in Condition (MC) it is sufficient to consider only the
values of $b$ that do not exceed the maximum concentration in $C$ and are
powers of prime factors of $n$. This property is used in Section 5 to show
that any set $C$ that satisfies Condition (MC) has a perfect-mixing graph,
completing the proof of Theorem 1.1(a). The mixing graph constructed in
Section 5 has precision at most $1$, proving the frst part of Theorem 1.1(b).
The second part, showing the existence of a perfect-mixing graph of polynomial
size is established in Section 6. The proof of Theorem 1.1(c) is divided into
two parts: that testing Condition (MC) can be done in polynomial time follows
directly from Corollary 4.7 in Section 4, while a polynomial-time algorithm
for constructing a perfect-mixing graph is described in Sections 6 and 7.

##  2\. Preliminaries

Let ${\mathbb{Q}}_{0}$ be the set of binary numbers. For
$c\in{\mathbb{Q}}_{0}$, we denote by ${\textsf{prec}}(c)$ the precision of
$c$, that is the number of fractional bits in the binary representation of
$c$, assuming there are no trailing $0$’s. In other words,
${\textsf{prec}}(c)$ is the smallest $d\in{\mathbb{Z}_{\geq 0}}$ such that
$c=a/2^{d}$ for some $a\in{\mathbb{Z}}$. If $c=a/2^{d}$ represents actual
fluid concentration, then we have $0\leq a\leq 2^{d}$. However, it is
convenient to relax this restriction and allow “concentration values” that are
arbitrary binary numbers, even negative. In fact, as we show shortly, it will
be convenient to work with integral values.

By a _configuration_ we mean a multiset of $n$ binary numbers, called droplets
or concentrations. In the literature, multisets are often represented by their
characteristic functions (that specify the multiplicity of each element of the
ground set). In this paper we will generally use set-theoretic terminology,
with its natural interpretation. For example, for a configuration $C$ and a
concentration $a$, $a\in C$ means that the multiplicity of $a$ in $C$ is
strictly positive, while $a\notin C$ means that it’s zero. Or,
$C-{\left\\{a\right\\}}=C^{\prime}$ means that the multiplicity of $a$ in
$C^{\prime}$ is one less than in $C$, while other multiplicities are the same.
The number of droplets in $C$ is denoted ${|C|}=n$, while the number of
different concentrations is denoted ${\|C\|}=m$. We will typically denote a
configuration by
$C={\left\\{f_{1}:c_{1},f_{2}:c_{2},...,f_{m}:c_{m}\right\\}}{\,\sqsubset\,}{\mathbb{Q}}_{0}$,
where each $c_{i}$ represents a (different) concentration value and $f_{i}$
denotes the multiplicity of $c_{i}$ in $C$, so that $\sum_{i=1}^{m}f_{i}=n$.
Occasionally, if it does not lead to confusion, we may say “droplet $c_{i}$”
or “concentration $c_{i}$”, referring to some droplet with concentration
$c_{i}$. If $f_{i}=1$, we shorten “$f_{i}:c_{i}$” to just “$c_{i}$”. If
$f_{i}=1$ we say that droplet $c_{i}$ is a _singleton_ , if $f_{i}=2$ we say
that droplet $c_{i}$ is a _doubleton_ and if $f_{i}\geq 2$ we say that droplet
$c_{i}$ is a _non-singleton_. By ${\textsf{sum}}(C)$ we denote the sum of $C$,
that is ${\textsf{sum}}(C)=\sum_{c\in C}c$.
${\textsf{ave}}(C)={\textsf{sum}}(C)/n$ is the average value of the
concentrations in $C$ and will be typically denoted by $\mu$. (Later, we will
typically deal with configurations $C$ such that
$C\cup{\left\\{\mu\right\\}}{\,\sqsubset\,}{\mathbb{Z}}$.)

Mixing graphs were defined in the introduction. As we are not concerned in
this paper with the topological properties of mixing graphs, we will often
identify a mixing graph $G$ with a corresponding _mixing sequence_ , which is
a sequence (not necessarily unique) of mixing operations that convert $C$ into
its perfect mixture. In other words, a mixing sequence is a sequence of mixing
operations in a topological ordering of a mixing graph.

Of course in a perfect-mixing graph (or sequence) $G$ for $C$, all
concentrations in $G$, including those in $C\cup{\left\\{\mu\right\\}}$, must
have finite precision (that is, belong to ${\mathbb{Q}}_{0}$); in fact, the
maximum concentration in $G$ is at least
$\max{\left\\{{\textsf{prec}}(C),{\textsf{prec}}(\mu)\right\\}}$. In addition
to the basic question about finding a perfect-mixing graph for $C$, we are
also interested in bounding the precision required to do so.

For $x\in{\mathbb{Q}}_{0}$, define multisets $C+x={\left\\{c+x\mid c\in
C\right\\}}$, $C-x=C+(-x)$, and $C\cdot x={\left\\{c\cdot x\mid c\in
C\right\\}}$. The next observation says that offsetting all values in $C$ does
not affect perfect mixability, as long as the offset value’s precision does
not exceed that of $C$ or $\mu$.

######  Observation 1.

Let $\mu={\textsf{ave}}(C)$ and $x\in{\mathbb{Q}}_{0}$. Also, let
$d\in{\mathbb{Z}_{>0}}$ be such that
$d\geq\max{\left\\{{\textsf{prec}}(C),{\textsf{prec}}(\mu),{\textsf{prec}}(x)\right\\}}$.
Then $C$ is perfectly mixable with precision $d$ if and only if
$C^{\prime}=C+x$ is perfectly mixable with precision $d$.

######  Proof 2.1.

$(\Rightarrow)$ Suppose that $G$ is a perfect-mixing sequence for $C$ with
precision $d$. Run the same sequence $G$ on input $C^{\prime}$. If some mixing
step in $G$ produces a value $z$ when the input is $C$ then on $C^{\prime}$
its value is $z+x$, and
${\textsf{prec}}(z+x)\leq\max{\left\\{{\textsf{prec}}(z),{\textsf{prec}}(x)\right\\}}\leq
d$. Thus the maximum precision in $G$ for input $C^{\prime}$ is at most $d$.

$(\Leftarrow)$ The proof for this implication follows from noting that
$\mu^{\prime}={\textsf{ave}}(C^{\prime})=\mu+x$,
$\max{\left\\{{\textsf{prec}}(C^{\prime}),{\textsf{prec}}(\mu^{\prime})\right\\}}\leq
d$, and by applying the above argument to $-x$ instead of $x$.

######  Observation 2.

Let $\mu={\textsf{ave}}(C)$,
$\delta=\max{\left\\{{\textsf{prec}}(C),{\textsf{prec}}(\mu)\right\\}}$,
$C^{\prime}=C\cdot 2^{\delta}$ with
$\mu^{\prime}={\textsf{ave}}(C^{\prime})=2^{\delta}\mu$. (Thus
$C^{\prime}\cup{\left\\{\mu^{\prime}\right\\}}{\,\sqsubset\,}{\mathbb{Z}}$.)
Then $C$ is perfectly mixable with precision $d\geq\delta$ if and only if
$C^{\prime}$ is perfectly mixable with precision $d^{\prime}=d-\delta$.

######  Proof 2.2.

$(\Rightarrow)$ Let $G$ be a perfect-mixing sequence for $C$, with precision
$d$. Run the same sequence $G$ on input $C^{\prime}$. If some node in $G$
produces a value $z$ on input $C$, then its value on input $C^{\prime}$ will
be $z2^{\delta}$, and
${\textsf{prec}}(z2^{\delta})=\max{\left\\{{\textsf{prec}}(z)-\delta,0\right\\}}\leq
d-\delta=d^{\prime}$.

$(\Leftarrow)$ Let $G^{\prime}$ be a perfect-mixing sequence for $C^{\prime}$
with precision $d^{\prime}$. Run $G^{\prime}$ on input $C$. If some node in
$G^{\prime}$ produces a value $y$ on input $C^{\prime}$, then its value on
input $C$ will be $y/2^{\delta}$, and
${\textsf{prec}}(y/2^{\delta})\leq{\textsf{prec}}(y)+\delta\leq
d^{\prime}+\delta=d$.

Integral configurations. Per Observation 2, we can restrict our attention to
configurations with integer values and average, that is, we will be assuming
that $C\cup{\left\\{\mu\right\\}}{\,\sqsubset\,}{\mathbb{Z}}$.

For $x\in{\mathbb{Z}_{>0}}$, if each $c\in C$ is a multiple of $x$, let
$C/x={\left\\{c/x\mid c\in C\right\\}}$. For integral configurations, we can
extend Observation 2 to also multiplying $C$ by an odd integer or dividing it
by a common odd factor of all concentrations in $C$.

######  Observation 3.

Assume that $C\cup{\left\\{\mu\right\\}}{\,\sqsubset\,}{\mathbb{Z}}$ and let
$x\in{\mathbb{Z}_{>0}}$ be odd.

:

_(a)_ Let $C^{\prime}=C\cdot x$. Then $C$ is perfectly mixable with precision
$0$ if and only if $C^{\prime}$ is perfectly mixable with precision $0$.

:

_(b)_ Suppose that $x$ is a divisor of all concentrations in
$C\cup{\left\\{\mu\right\\}}$. Then $C$ is perfectly mixable with precision
$0$ if and only if $C/x$ is perfectly mixable with precision $0$.

######  Proof 2.3.

Part (b) follows from (a), so we only prove part (a). Any sequence $G$ of
mixing operations for $C$ can be applied to $C\cdot x$. By simple induction,
if some intermediate value in $G$ was an integer $z$, now its value will be
$zx$, also an integer. This shows the $(\Rightarrow)$ implication.

To justify the $(\Leftarrow)$ implication, suppose that $G^{\prime}$ is a
sequence of mixing operations for $C^{\prime}$ and that all concentrations in
$G^{\prime}$ are integer. Since $x$ is odd and all concentrations in
$C^{\prime}$ are multiples of $x$, every concentration in $G^{\prime}$ will be
also a multiple of $x$, including ${\textsf{ave}}(C^{\prime})$. Thus, if we
run $G^{\prime}$ on $C$ instead of $C^{\prime}$, if some node’s concentration
was $cx$, now it will be $c$. Thus, the $(\Leftarrow)$ implication holds.

##  3\. Necessity of Condition (MC)

In this section we prove that Condition (MC) in Theorem 1.1(a) is necessary
for perfect mixability. So let
$C\cup{\left\\{\mu\right\\}}{\,\sqsubset\,}{\mathbb{Z}}$, where
$\mu={\textsf{ave}}(C)$, and assume that $C$ is perfectly mixable. Let $G$ be
a graph (or a sequence) that mixes $C$ perfectly. We want to prove that $C$
satisfies Condition (MC).

Suppose that $C$ is $b$-congruent for some odd $b\in{\mathbb{Z}_{>0}}$.
Consider an auxiliary configuration $C^{\prime}=C\cdot 2^{\delta}$, where
$\delta$ is sufficiently large, so that all intermediate concentrations in $G$
when applying $G$ to $C^{\prime}$ are integral. This $C^{\prime}$ is
$b$-congruent, and starting from $C^{\prime}$, $G$ produces a perfect mixture
of $C^{\prime}$, that is ${\left\\{n:\mu^{\prime}\right\\}}$, for
$\mu^{\prime}=2^{\delta}\mu$.

Since $C^{\prime}$ is $b$-congruent, there is
$\beta\in{\left\\{0,...,b-1\right\\}}$ such that for each $x\in C^{\prime}$ we
have $x\equiv\beta\pmod{b}$. We claim that this property is preserved as we
apply mixing operations to droplets in $C^{\prime}$. Indeed, suppose that we
mix two droplets with concentrations $x,y\in C^{\prime}$, producing two
droplets with concentration $z$. Since $x\equiv\beta\pmod{b}$ and
$y\equiv\beta\pmod{b}$, we have $x=\alpha b+\beta$ and
$y=\alpha^{\prime}b+\beta$, for some $\alpha,\alpha^{\prime}\in{\mathbb{Z}}$,
so
$z={\textstyle\frac{1}{2}}(x+y)=({\textstyle\frac{1}{2}}(\alpha+\alpha^{\prime}))b+\beta$.
As $b$ is odd (and $z$ is integer), $\alpha+\alpha^{\prime}$ must be even, and
therefore $z\equiv\beta\pmod{b}$, as claimed. Eventually $G$ produces
$\mu^{\prime}$, so this must also hold for $z=\mu^{\prime}$. This implies that
$C^{\prime}\cup{\left\\{\mu^{\prime}\right\\}}$ is $b$-congruent.

Finally, since $C^{\prime}\cup{\left\\{\mu^{\prime}\right\\}}$ is
$b$-congruent, for all $2^{\delta}x,2^{\delta}y\in
C^{\prime}\cup{\left\\{\mu^{\prime}\right\\}}$ it holds that
$2^{\delta}x\equiv 2^{\delta}y\pmod{b}$. But this implies that $x\equiv
y\pmod{b}$, because $b$ is odd. So we can conclude that
$C\cup{\left\\{\mu\right\\}}$ is $b$-congruent, thus proving that $C$
satisfies Condition (MC).

##  4\. Some Auxiliary Lemmas

In this section we show that, for Condition (MC), we only need to consider
$b$’s that are odd-prime factors of $n$ and satisfy $b\leq c_{max}$, where
$c_{max}$ denotes the maximum absolute value of concentrations in $C$. These
properties play an important role in the sufficiency proof of Condition (MC)
in Theorem 1.1(a). Additionally, they lead to an efficient algorithm for
testing perfect mixability (see Section 7), thus showing the first part of
Theorem 1.1(c).

######  Lemma 4.1.

Let $b,c\in{\mathbb{Z}_{>0}}$ and $A{\,\sqsubset\,}{\mathbb{Z}}$. (a) If $A$
is $bc$-congruent then $A$ is also $b$-congruent. (b) If
${\textsf{gcd}}(b,c)=1$ and $A$ is both $b$-congruent and $c$-congruent then
$A$ is $bc$-congruent.

######  Proof 4.2.

Part (a) is trivial, because $x\equiv y\pmod{bc}$ implies that $x\equiv
y\pmod{b}$. Part (b) is also simple: Suppose that $x\equiv y\pmod{b}$ and
$x\equiv y\pmod{c}$. This means that $b|(x-y)$ and $c|(x-y)$. This, since
$b,c$ are co-prime, implies that $(bc)|(x-y)$, which is equivalent to $x\equiv
y\pmod{bc}$.

######  Lemma 4.3.

If Condition (MC) holds for all $b\in{\mathbb{Z}_{>0}}$ that are a power of an
odd prime then it holds for all odd $b\in{\mathbb{Z}_{>0}}$.

######  Proof 4.4.

Assume that condition (MC) holds for all $b$ that are odd prime powers. Let
$b^{\prime}\in{\mathbb{Z}_{>0}}$ be odd, with factorization
$b^{\prime}=p_{1}^{\gamma_{1}}...p_{k}^{\gamma_{k}}$, for different odd primes
$p_{1},...,p_{k}$, and suppose that $C$ is $b^{\prime}$-congruent. Then, by
Lemma 4.1(a), $C$ is also $p_{i}^{\gamma_{i}}$-congruent for all $i$. Since
condition (MC) holds for $p_{i}^{\gamma_{i}}$, this implies that
$C\cup{\left\\{\mu\right\\}}$ is $p_{i}^{\gamma_{i}}$-congruent for all $i$.
By repeated application of Lemma 4.1(b), we then obtain that
$C\cup{\left\\{\mu\right\\}}$ is $b^{\prime}$-congruent as well. So Condition
(MC) holds for $b^{\prime}$.

######  Lemma 4.5.

Let $b\in{\mathbb{Z}_{>0}}$ be odd. If $\gcd(b,n)=1$ then Condition (MC) holds
for $b$.

######  Proof 4.6.

Assume that $C$ is $b$-congruent. By Observation 1, without loss of generality
we can assume that all numbers in $C$ are multiples of $b$. (Otherwise we can
consider $C^{\prime}=C-c$, for an arbitrary $c\in C$, because Condition (MC)
is not affected by offsetting $C$.) Thus ${\textsf{sum}}(C)=b\beta$, for some
$\beta\in{\mathbb{Z}}$, which gives us that
$\mu={\textsf{sum}}(C)/n=b\beta/n$. As $\mu$ is integer and $\gcd(b,n)=1$,
$\beta$ must be a multiple of $n$. We can thus conclude that $\mu$ is a
multiple of $b$. This means that $C\cup{\left\\{\mu\right\\}}$ is
$b$-congruent, proving that Condition (MC) holds for $b$.

######  Corollary 4.7.

Let $c_{max}$ be the maximum absolute value of concentrations in $C$. If
Condition (MC) holds for all $b\in{\mathbb{Z}_{>0}}$ with $b\leq c_{max}$ that
are powers of odd prime factors of $n$, then Condition (MC) holds for all odd
$b$.

To substantiate Corollary 4.7, note that $C$ satisfies Condition (MC) for all
odd $b\in{\mathbb{Z}_{>0}}$ larger than $c_{max}$. This holds because for each
such $b$, $c\mod b=c$ for all $c\in C$, so the remainders of the (different)
concentrations in $C$ modulo $b$ are all different. (In the trivial case where
all concentrations in $C$ are equal, $\mu$ is also equal and thus $C$
satisfies Condition (MC); such $C$ is actually perfectly mixed already.)

##  5\. Sufficiency of Condition (MC)

In this section we prove that Condition (MC) in Theorem 1.1(a) is sufficient
for perfect mixability. A perfect-mixing graph constructed in our argument has
precision at most $1$, showing also the first part of Theorem 1.1(b).

Assume that $n\geq 4$. Let $C$ with $\mu={\textsf{ave}}(C)$ and
$C\cup{\left\\{\mu\right\\}}{\,\sqsubset\,}{\mathbb{Z}}$ be the input
configuration, and assume that $C$ satisfies Condition (MC). The outline of
our proof is as follows:

  * •

First we prove that $C$ is perfectly mixable with precision $0$ when $n$ is a
power of $2$. This easily extends to configurations $C$ called _near-final_ ,
which are disjoint unions of multisets with the same average and cardinalities
being powers of $2$. In particular, this proves Theorem 1.1(a) for $n=4$.

  * •

Next, we give a proof for $n\geq 7$. The basic idea of the proof is to define
an invariant (I) and show that any configuration that satisfies (I) has a pair
of droplets whose mixing either preserves invariant (I) or produces a near-
final configuration. Condition (I) is stronger than (MC) (it implies (MC), but
not vice versa), but we show that that any configuration that satisfies
Condition (MC) can be modified to satisfy (I).

  * •

We then give separate proofs for $n=5,6$. The proof for $n=5$ is similar to
the case $n\geq 7$, but it requires a more subtle invariant. The proof for
$n=6$ is derived by minor modifications to the proof for $n=5$.

###  5.1. Perfect Mixability of Near-Final Configurations

Let $C{\,\sqsubset\,}{\mathbb{Z}}$ be a configuration with ${|C|}=n=\sigma
2^{\tau}$, for some odd $\sigma\in{\mathbb{Z}_{>0}}$ and
$\tau\in{\mathbb{Z}_{\geq 0}}$, with ${\textsf{ave}}(C)=\mu\in{\mathbb{Z}}$.
We say that $C$ is _near-final_ if it can be partitioned into disjoint
multisets $C_{1},C_{2},...,C_{k}$, such that, for each $j$,
${\textsf{ave}}(C_{j})=\mu$ and ${|C_{j}|}$ is a power of $2$. In this sub-
section we show (Lemma 5.1 below) that near-final configurations are perfectly
mixable with precision $0$. We also show that configurations with only two
different concentrations that satisfy Condition (MC) are near-final, and thus
perfectly mixable.

Define ${\Psi}(C)=\sum_{c\in C}(c-\mu)^{2}$, which can be thought of as the
un-normalized variance of $C$. Obviously ${\Psi}(C)\in{\mathbb{Z}_{\geq 0}}$,
${\Psi}(C)=0$ if and only if $C$ is a perfect mixture, and, by a
straightforward calculation, mixing any two different same-parity
concentrations in $C$ decreases the value of ${\Psi}(C)$ by at least $1$.

######  Lemma 5.1.

If $C$ is near-final then $C$ is perfectly mixable with precision $0$.

######  Proof 5.2.

It is sufficient to prove the lemma for the case when $n$ is a power of $2$.
(Otherwise, we can apply it separately to each set $C_{j}$ in the partition of
$C$ from the definition of near-final configurations.)

So assume that $n$ is a power of $2$. It is sufficient to show that if
${\|C\|}=m\neq 1$ (that is, $C$ is not yet perfectly mixed) then $C$ contains
two different concentrations with the same parity. (Each such mixing strictly
decreases ${\Psi}(C)$, so a finite sequence of such mixing operations will
perfectly mix $C$.) This is trivially true when $m\geq 3$, so it is sufficient
to prove it for $m=2$, that is for
$C={\left\\{f_{1}:c_{1},f_{2}:c_{2}\right\\}}$. Without loss of generality, by
Observation 1, we can assume that $c_{2}=0$, and then we claim that $c_{1}$ is
even. We have ${\textsf{ave}}(C)=\mu=f_{1}c_{1}/n$. As $\mu\in{\mathbb{Z}}$,
$f_{1}<n$ and $n$ is a power of $2$, we have that $c_{1}$ must be even, as
claimed.

######  Lemma 5.3.

Assume that ${\|C\|}=2$, say $C={\left\\{f_{1}:c_{1},f_{2}:c_{2}\right\\}}$,
and that $C$ satisfies Condition (MC). Then $\sigma$ divides $f_{1}$ and
$f_{2}$. Consequently, we have that $n$ is not prime and $C$ is near-final.

######  Proof 5.4.

Without loss of generality, assume that $c_{2}=0$. (Otherwise consider
$C^{\prime}=C-c_{2}$ instead. This does not affect Condition (MC) and the
property of being near-final.) Let $c_{1}=\alpha 2^{\gamma}$, for some odd
$\alpha\in{\mathbb{Z}_{>0}}$. Then $\mu=f_{1}c_{1}/n=f_{1}\alpha
2^{\gamma}/(\sigma 2^{\tau})$. Since $\alpha$ divides $c_{1}$ and $c_{2}$,
Condition (MC) implies that $\alpha$ must also divide $\mu$. In other words,
$\mu/\alpha=f_{1}2^{\gamma}/(\sigma 2^{\tau})$ is integer. This implies, in
turn, that $f_{1}$ is a multiple of $\sigma$, as claimed. Since
$f_{2}=n-f_{1}$, it also gives us that $f_{2}$ is a multiple of $\sigma$.

This immediately implies that $n$ cannot be prime, for $n=f_{1}+f_{2}$ is a
sum of two non-zero multiples of $\sigma$.

To prove the last claim, let $f_{1}=\sigma f^{\prime}_{1}$ and $f_{2}=\sigma
f^{\prime}_{2}$, for some $f^{\prime}_{1},f^{\prime}_{2}\in{\mathbb{Z}_{>0}}$.
Partition $C$ into $\sigma$ sub-multisets of the form
$C_{j}={\left\\{f_{1}^{\prime}:c_{1},f^{\prime}_{2}:0\right\\}}$, for
$j=1,2,...,\sigma$. The cardinality of each $C_{j}$ is
$f^{\prime}_{1}+f^{\prime}_{2}=n/\sigma=2^{\tau}$ and its average is
${\textsf{ave}}(C_{j})=f^{\prime}_{1}c_{1}/(f^{\prime}_{1}+f^{\prime}_{2})=(f_{1}/\sigma)c_{1}/(n/\sigma)=f_{1}c_{1}/n=\mu$.
Therefore $C$ is near-final, as claimed.

We remark that when $n$ is a power of $2$ there is an alternative way to
perfectly mix $C$, using a divide-and-conquer approach: partition $C$ into two
equal-size multisets $C^{\prime},C^{\prime\prime}$, mix each of these
recursively, obtaining $n/2$ droplets with concentration
$\mu^{\prime}={\textsf{ave}}(C^{\prime})$ and $n/2$ droplets with
concentration $\mu^{\prime\prime}={\textsf{ave}}(C^{\prime\prime})$, and then
mix $n/2$ disjoint pairs of droplets, one $\mu^{\prime}$ and the other
$\mu^{\prime\prime}$, producing $n$ droplets with concentration
$\mu={\textsf{ave}}(C)$. This approach, however, produces mixing graphs where
the intermediate precision could be quite large, so it is not sufficient for
our purpose.

###  5.2. Proof for arbitrary $n\geq 7$

In this sub-section we prove that Condition (MC) in Theorem 1.1(a) is
sufficient for perfect mixability when $n\geq 7$. Let $C$ be a configuration
that satisfies Condition (MC), where
$C\cup{\left\\{\mu\right\\}}{\,\sqsubset\,}{\mathbb{Z}}$ and ${|C|}=n$. Also,
let the factorization of $n$ be
$n=2^{\tau_{0}}p_{1}^{\tau_{1}}p_{2}^{\tau_{2}}...p_{s}^{\tau_{s}}$, where
${\left\\{p_{1},p_{2},...,p_{s}\right\\}}={\bar{p}}$ is the set of the odd
prime factors of $n$ and ${\left\\{\tau_{1},\tau_{2},...,\tau_{s}\right\\}}$
are their corresponding multiplicities.

If $A{\,\sqsubset\,}{\mathbb{Z}}$ is a configuration with ${|A|}=n$ (where $n$
is as above) and ${\textsf{ave}}(A)\in{\mathbb{Z}}$, we will say that $A$ is
_${\bar{p}}$ -incongruent_ if $A$ is $p_{r}$-incongruent for all $r$. If $A$
is ${\bar{p}}$-incongruent then, by Lemma 4.1(a), it is $b$-incongruent for
all $b$ that are powers of $p_{r}$’s, which, by Corollary 4.7, implies that
$A$ satisfies Condition (MC). Further, if $A$ is also not near-final then
Lemma 5.3 implies that ${\|A\|}\geq 3$. We summarize these observations below.
(They will be often used in this section without an explicit reference.)

######  Observation 4.

Assume that a configuration $A{\,\sqsubset\,}{\mathbb{Z}}$ with
${\textsf{ave}}(A)\in{\mathbb{Z}}$ is ${\bar{p}}$-incongruent. Then (a) $A$
satisfies Condition (MC), and (b) if $A$ is not near-final then ${\|A\|}\geq
3$.

Proof outline. The outline of the sufficiency proof for $n\geq 7$ is as
follows (see Figure 4): Assume that $C$ is not perfectly mixed. Instead of
dealing with $C$ directly, we will consider a ${\bar{p}}$-incongruent
configuration ${\check{C}}{\,\sqsubset\,}{\mathbb{Z}}$ with
${\check{\mu}}={\textsf{ave}}({\check{C}})\in{\mathbb{Z}}$ that is
“equivalent” to $C$ in the sense that $C$ is perfectly mixable with precision
at most $1$ if and only if ${\check{C}}$ is perfectly mixable with precision
$0$.

It is thus sufficient to show that ${\check{C}}$ is perfectly mixable with
precision $0$. To this end, we first apply some mixing operations to
${\check{C}}$, producing only integer concentrations, that convert
${\check{C}}$ into a configuration $E$ such that:

:

(I.0) $E{\,\sqsubset\,}{\mathbb{Z}}$ and ${\textsf{ave}}(E)={\check{\mu}}$,

:

(I.1) $E$ has at least $2$ distinct non-singletons, and

:

(I.2) $E$ is ${\bar{p}}$-incongruent.

We refer to the three conditions above as Invariant (I). Then we show that any
configuration $E$ that satisfies Invariant (I) has a pair of different
concentrations whose mixing either preserves Invariant (I) or converts $E$
into a near-final configuration. We can thus repeatedly mix such pairs,
preserving Invariant (I), until we produce a near-final configuration, that,
by the previous section, can be perfectly mixed with precision $0$.

Figure 4. Proof outline for $n\geq 7$. The first dashed arrow represents
replacing $C$ by ${\check{C}}$. Solid arrows represent mixing operations.

Replacing $C$ by ${\check{C}}$. We now explain how to modify $C$. We will do
it in steps. First, let $C^{\prime}=C-c_{1}$, for some arbitrarily chosen
$c_{1}\in C$. Note that $\mu^{\prime}={\textsf{ave}}(C^{\prime})=\mu-
c_{1}\in{\mathbb{Z}}$, that $0\in C^{\prime}$, and that $C^{\prime}$ satisfies
Condition (MC). By Observation 1, $C$ is perfectly mixable if and only if
$C^{\prime}$ is perfectly mixable (with the same precision), so it is
sufficient to show that $C^{\prime}$ is perfectly mixable.

Then, let $\theta\in{\mathbb{Z}_{>0}}$ be the maximum odd integer that divides
all concentrations $c\in C^{\prime}$ (that is, the greatest common odd divisor
of $C^{\prime}$). Let $C^{\prime\prime}=C^{\prime}/\theta$. By Observation
3(b) and the paragraph above, $C$ is perfectly mixable if and only
$C^{\prime\prime}$ is perfectly mixable (with the same precision), so from now
on we can replace $C$ by $C^{\prime\prime}$.

By Condition (MC) applied to $C^{\prime}$, $\theta$ is a divisor of
$\mu^{\prime}$, so
$\mu^{\prime\prime}={\textsf{ave}}(C^{\prime\prime})=\mu^{\prime}/\theta\in{\mathbb{Z}}$.
Next, we claim that $C^{\prime\prime}$ is ${\bar{p}}$-incongruent. To show
this, we argue by contradiction. Suppose that $C^{\prime\prime}$ is
$p_{r}$-congruent for some $r$. This means that there is
$\beta\in{\left\\{0,1,...,p_{r}-1\right\\}}$ such that
$c\equiv\beta\pmod{p_{r}}$ for all $c\in C^{\prime\prime}$. Since $0\in
C^{\prime\prime}$ (because $0\in C^{\prime}$), we must have $\beta=0$. In
other words, all $c\in C^{\prime\prime}$ are multiples of $p_{r}$. That would
imply, however, that all $c\in C^{\prime}$ are multiples of $\theta p_{r}$,
which contradicts the choice of $\theta$, completing the proof.

Finally, let ${\check{C}}=2\cdot C^{\prime\prime}$ and
${\check{\mu}}=2\mu^{\prime\prime}={\textsf{ave}}({\check{C}})$. All
concentrations in ${\check{C}}$ are even and, since multiplying all
concentrations by $2$ does not affect ${\bar{p}}$-incongruence, ${\check{C}}$
is ${\bar{p}}$-incongruent. By Observation 2, and the properties of
$C^{\prime\prime}$ established above, $C$ is perfectly mixable with precision
at most $1$ if and only if ${\check{C}}$ is perfectly mixable with precision
$0$. Therefore, from now on, it is sufficient to show a mixing sequence with
all integral concentration values that converts ${\check{C}}$ into its perfect
mixture ${\left\\{n:{\check{\mu}}\right\\}}$.

Converting ${\check{C}}$ into $E$. Let ${\check{C}}$ be the configuration
constructed above. We now show that with at most two mixing operations,
producing only integer values, we can convert ${\check{C}}$ into a
configuration $E$ that satisfies Invariant (I). We start with an auxiliary
lemma (Lemma 5.5 below).

Let $A{\,\sqsubset\,}{\mathbb{Z}}$ be a configuration with
${\textsf{ave}}(A)\in{\mathbb{Z}}$ and ${|A|}=n$. Assume that $A$ is
${\bar{p}}$-incongruent. For different concentrations $a,a^{\prime}\in A$ with
the same parity, we say that the pair $(a,a^{\prime})$ is _$p_{r}$ -safe_ if
mixing $a$ and $a^{\prime}$ converts $A$ into a $p_{r}$-incongruent
configuration; in other words, there is $a^{\prime\prime}\in
A-{\left\\{a,a^{\prime}\right\\}}$ that satisfies
$a^{\prime\prime}\not\equiv{\textstyle\frac{1}{2}}(a+a^{\prime})\pmod{p_{r}}$.
(Otherwise, we say that the pair $(a,a^{\prime})$ is _$p_{r}$ -unsafe_.) We
will also say that $(a,a^{\prime})$ is _${\bar{p}}$ -safe_ if it is
$p_{r}$-safe for all $r$, and we call it _${\bar{p}}$ -unsafe_ otherwise.

For example, let $n=15$ and $A={\left\\{11:3,10,16,18,28\right\\}}$, for which
${\textsf{ave}}(A)=7$. We have ${\bar{p}}={\left\\{p_{1},p_{2}\right\\}}$,
where $p_{1}=3$ and $p_{2}=5$. The pair $(10,16)$ is $5$-unsafe, because
mixing these two droplets produces two droplets with concentration $13$, hence
producing a $5$-congruent configuration (all concentrations will have residue
$3$ modulo $5$). Thus the pair $(10,16)$ is ${\bar{p}}$-unsafe. All other
pairs $(a,a^{\prime})$ of same-parity concentrations from $A$ are
${\bar{p}}$-safe.

######  Lemma 5.5.

Let $A$ be a ${\bar{p}}$-incongruent configuration with
${\textsf{ave}}(A)\in{\mathbb{Z}}$ and ${|A|}=n$. (Recall that $n\geq 7$.)
Then

:

(a) For each $r$, there is at most one $p_{r}$-unsafe pair in $A$.

:

(b) There are at most $n-5$ droplets involved in same-parity concentration
pairs that are ${\bar{p}}$-unsafe.

:

(c) If a concentration $a\in A$ is a non-singleton (has multiplicity at least
$2$) then for any $b\in A$ with $b\neq a$ and the same parity as $a$, the pair
$(a,b)$ is ${\bar{p}}$-safe.

######  Proof 5.6.

(a) Suppose that some pair $(a_{1},a_{2})$ of concentrations with $a_{1}\neq
a_{2}$ and same parity is $p_{r}$-unsafe, and let
$\beta=({\textstyle\frac{1}{2}}(a_{1}+a_{2}))\bmod p_{r}$. The assumption
about $a_{1},a_{2}$ implies that $b\equiv\beta\pmod{p_{r}}$ for all $b\in
A-{\left\\{a_{1},a_{2}\right\\}}$, and the assumption that $A$ is
${\bar{p}}$-incongruent implies that $a_{i}\not\equiv\beta\pmod{p_{r}}$ for at
least one $i\in{\left\\{1,2\right\\}}$. We claim that this must in fact hold
for _both_ $i\in{\left\\{1,2\right\\}}$. Indeed, say that
$a_{1}\not\equiv\beta\pmod{p_{r}}$ but $a_{2}\equiv\beta\pmod{p_{r}}$. This
means that $p_{r}\nmid(a_{1}-\beta)$ and $p_{r}|(a_{2}-\beta)$, which implies
that $p_{r}\nmid({\textstyle\frac{1}{2}}(a_{1}+a_{2})-\beta)$, contradicting
the definition of $\beta$. Thus $a_{i}\not\equiv\beta\pmod{p_{r}}$ for both
$i\in{\left\\{1,2\right\\}}$, as claimed.

It remains to show that any other pair of concentrations is $p_{r}$-safe. Fix
three arbitrary concentrations ${\left\\{b_{1},b_{2},b_{3}\right\\}}\subseteq
A-{\left\\{a_{1},a_{2}\right\\}}$, so that we have
$b_{j}\equiv\beta\pmod{p_{r}}$ for $j\in{\left\\{1,2,3\right\\}}$. Consider
any two different same-parity concentrations $c_{1},c_{2}\in A$ with
${\left\\{c_{1},c_{2}\right\\}}\neq{\left\\{a_{1},a_{2}\right\\}}$, and let
$A^{\prime}$ be obtained from $A$ by mixing droplets $c_{1}$ and $c_{2}$. Then
$A^{\prime}$ must still contain some droplet $b_{j}$ and, since
${\left\\{c_{1},c_{2}\right\\}}\neq{\left\\{a_{1},a_{2}\right\\}}$,
$A^{\prime}$ will also contain some droplet $a_{i}$. As we have
$a_{i}\not\equiv b_{j}\pmod{p_{r}}$, $A^{\prime}$ is $p_{r}$-incongruent, and
thus $(c_{1},c_{2})$ is $p_{r}$-safe.

(b) By part (a), the number of concentrations involved in same-parity
${\bar{p}}$-unsafe pairs is at most $2s$, where $s$ is the number of distinct
odd prime factors of $n$, so it remains to show that $2s\leq n-5$. Indeed, if
$n$ equals either $7$ or $8$ (for which $s=1$ or $0$, respectively), then the
inequality holds. For $n\geq 9$, using the fact that $s\leq\log_{3}{n}$, it is
sufficient to show that $2\log_{3}{n}\leq n-5$. This is true, because for
$n=9$ the equality holds, and for $n\geq 9$ the left-hand side grows slower
than the right-hand side.

(c) Fix some factor $p_{r}$ of $n$. As $A$ is $p_{r}$-incongruent, there is a
concentration $c\in A$ with $c\not\equiv a\pmod{p_{r}}$. We have two cases. If
$b\equiv a\pmod{p_{r}}$ then $b\neq c$, so after mixing the new configuration
$A^{\prime}$ will contain $c$ and ${\textstyle\frac{1}{2}}(a+b)$, where
${\textstyle\frac{1}{2}}(a+b)\equiv a\pmod{p_{r}}$, so
$c\not\equiv{\textstyle\frac{1}{2}}(a+b)\pmod{p_{r}}$. On the other hand, if
$b\not\equiv a\pmod{p_{r}}$, then $A^{\prime}$ will contain $a$ and
${\textstyle\frac{1}{2}}(a+b)$, and
$a\not\equiv{\textstyle\frac{1}{2}}(a+b)\pmod{p_{r}}$. Thus $(a,b)$ is
$p_{r}$-safe. As this holds for all $r$, $(a,b)$ is ${\bar{p}}$-safe.

The configuration ${\check{C}}$ constructed earlier contains only even
concentration values, already satisfies
${\check{C}}\cup{\left\\{{\check{\mu}}\right\\}}{\,\sqsubset\,}{\mathbb{Z}}$
and is ${\bar{p}}$-incongruent (that is, it satisfies conditions (I.0) and
(I.2) for $E$). It remains to show that there are mixing operations involving
only droplets already present in ${\check{C}}$ (and thus of even value, to
assure that Condition (I.0) holds) that preserve condition (I.2), and such
that the resulting configuration $E$ satisfies condition (I.1). If
${\check{C}}$ already has two or more non-singletons, we can take
$E={\check{C}}$ and we are done, so assume otherwise, namely that there is
either exactly one non-singleton in ${\check{C}}$ or none. We consider three
cases.

Case 1: ${\check{C}}$ has one non-singleton $a$ and its multiplicity is $f\geq
3$. Mix $a$ with any singleton $b$ and let $E$ be the resulting configuration.
In $E$ we have two non-singletons and condition (I.2) will be satisfied, by
Lemma 5.5(c). Thus $E$ satisfies Invariant (I).

Case 2: ${\check{C}}$ has one non-singleton $a$ and its multiplicity is $2$.
By Lemma 5.5(b), there are at least $5$ droplets in ${\check{C}}$ not involved
in any ${\bar{p}}$-unsafe pair. Thus there are at least $3$ singletons, say
$b,c,d$, that are not involved in any ${\bar{p}}$-unsafe pair. Mixing one of
pairs $(b,c)$ or $(b,d)$ produces a concentration other than $a$. Mix this
pair, and let $E$ be the resulting configuration. Then $E$ satisfies Invariant
(I).

Case 3: ${\check{C}}$ has only singletons. By Lemma 5.5(b), there is a
singleton, say $b\in{\check{C}}$, that is not involved in any
${\bar{p}}$-unsafe pair (in fact, there are at least five, but we need just
one here). Let $c\in{\check{C}}-{\left\\{b\right\\}}$ be a singleton nearest
to $b$, that is one that minimizes $|c-b|$. By the choice of $b$, the pair
$(b,c)$ is ${\bar{p}}$-safe. Let
${\check{C}}^{\prime}={\check{C}}-{\left\\{b,c\right\\}}\cup{\left\\{a,a\right\\}}$,
for $a={\textstyle\frac{1}{2}}(b+c)$, be the configuration obtained by mixing
this pair. ${\check{C}}^{\prime}$ is ${\bar{p}}$-incongruent and in
${\check{C}}^{\prime}$ we have only one non-singleton $a$ and its multiplicity
is $2$. We can thus apply Case 2 above to ${\check{C}}^{\prime}$, converting
it to $E$. (Note that, unlike for the ${\check{C}}$ in Case 2, our $a$ may be
odd. But since we do not mix $a$ in Case 2, the argument is still valid.)

Preserving Invariant (I). We now present the last part of the proof, following
the outline given at the beginning of this section. Let
$E{\,\sqsubset\,}{\mathbb{Z}}$ be the configuration, say
$E={\left\\{f_{1}:e_{1},f_{2}:e_{2},...,f_{m}:e_{m}\right\\}}$, with
${\textsf{ave}}(E)={\check{\mu}}$, obtained from ${\check{C}}$ by a sequence
of mixing operations, as described earlier. If $E$ is near-final then $E$ has
a perfect-mixing sequence by Lemma 5.1. Otherwise, we show that $E$ has a pair
of concentrations whose mixing produces a configuration that either preserves
Invariant (I) or is near-final.

Let $e_{i},e_{j}\in E$ be two different concentrations. Let
$e={\textstyle\frac{1}{2}}(e_{i}+e_{j})$, and denote by
$E^{\prime}=E-{\left\\{e_{i},e_{j}\right\\}}\cup{\left\\{e,e\right\\}}$ the
configuration obtained from $E$ by mixing $e_{i}$ and $e_{j}$. The following
two notions will be useful in our analysis:

  * •

Pair $(e_{i},e_{j})$ will be called _(I)-safe_ if $E^{\prime}$ satisfies
Invariant (I). We will be always choosing $e_{i}$ and $e_{j}$ with the same
parity, which is a sufficient and necessary condition for $E^{\prime}$ to
satisfy condition (I.0). Also, for $E^{\prime}$ to satisfy condition (I.2),
the pair $(e_{i},e_{j})$ must be ${\bar{p}}$-safe.

  * •

Pair $(e_{i},e_{j})$ will be called _near-final_ if $E^{\prime}$ is near-
final. Note that it is possible for $(e_{i},e_{j})$ to be both (I)-safe and
near-final.

We next prove that if configuration $E$ satisfies Invariant (I) then it must
contain a pair of different concentrations that is either (I)-safe or near-
final. This will show that we can repeatedly mix $E$, maintaining Invariant
(I), until we turn $E$ into a near-final configuration, which we can then
perfectly mix using Lemma 5.1.

######  Lemma 5.7.

Assume that $E$ contains two different concentrations $e_{i},e_{j}\in E$ with
the same parity and $f_{i}\geq 3$. If $E$ satisfies Invariant (I) then the
pair $(e_{i},e_{j})$ is (I)-safe.

######  Proof 5.8.

Let $e={\textstyle\frac{1}{2}}(e_{i}+e_{j})$ and let
$E^{\prime}=E-{\left\\{e_{i},e_{j}\right\\}}\cup{\left\\{e,e\right\\}}$ be
obtained from mixing $e_{i}$ and $e_{j}$. Since $f_{i}>1$, Lemma 5.5(c)
implies that condition (I.2) holds for $E^{\prime}$. In $E^{\prime}$ we will
still have at least two droplets of concentration $e_{i}$ and at least two
droplets of concentration $e\neq e_{i}$. So condition (I.1) holds as well. (We
remark that we could end up with ${\|E^{\prime}\|}=2$, which can happen if
$f_{j}=1$ and ${\|E\|}=3$ with $e\in E$. If so, since $E^{\prime}$ satisfies
(I.2), it must also satisfy condition (MC), and therefore, by Lemma 5.3, in
this case $E^{\prime}$ is actually near-final; that is, $(e_{i},e_{j})$ is a
near-final pair.)

######  Lemma 5.9.

Assume that $E$ contains three different concentrations $e_{i},e_{j},e_{k}\in
E$ with the same parity and $f_{i},f_{j}\geq 2$. If $E$ satisfies Invariant
(I) then one of $(e_{i},e_{k})$, $(e_{j},e_{k})$ is (I)-safe.

######  Proof 5.10.

Without loss of generality, assume that $|e_{i}-e_{k}|\leq|e_{j}-e_{k}|$
(otherwise swap $i$ and $j$). We show that $(e_{i},e_{k})$ is (I)-safe. Let
$e={\textstyle\frac{1}{2}}(e_{i}+e_{k})$ and let
$E^{\prime}=E-{\left\\{e_{i},e_{k}\right\\}}\cup{\left\\{e,e\right\\}}$ be
obtained from mixing $e_{i}$ and $e_{k}$. Since $f_{i}>1$, Lemma 5.5(c)
implies that condition (I.2) holds for $E^{\prime}$. From
$|e_{i}-e_{k}|\leq|e_{j}-e_{k}|$, we have that $e\neq e_{j}$. So in
$E^{\prime}$ we will have at least two droplets of concentration $e_{j}$ and
at least two droplets of concentration $e\neq e_{j}$. This means that
condition (I.1) holds as well.

######  Lemma 5.11.

Assume that ${\|E\|}\geq 4$ and that $E$ contains three different
concentrations $e_{i},e_{j},e_{k}\in E$ with the same parity such that
$f_{i}\geq 2$ and $f_{j}=f_{k}=1$. If $E$ satisfies Invariant (I), then one of
$(e_{i},e_{j})$, $(e_{i},e_{k})$ is (I)-safe.

######  Proof 5.12.

By condition (I.1), there is another concentration $e_{l}\in
E-{\left\\{e_{i},e_{j},e_{k}\right\\}}$ with $f_{l}\geq 2$. Without loss of
generality, we can assume that $e={\textstyle\frac{1}{2}}(e_{i}+e_{j})\neq
e_{l}$ (otherwise we can use $e_{k}$ instead of $e_{j}$). Mixing $e_{i}$ and
$e_{j}$ produces
$E^{\prime}=E-{\left\\{e_{i},e_{j}\right\\}}\cup{\left\\{e,e\right\\}}$. Since
$f_{i}\geq 2$, condition (I.2) is satisfied. In $E^{\prime}$ there are at
least two droplets with concentration $e_{l}$ and at least two droplets with
concentration $e\neq e_{l}$, so condition (I.1) is satisfied as well.

######  Lemma 5.13.

Assume that ${\|E\|}=3$. If $E$ satisfies Invariant (I) then $E$ has a pair of
concentrations that is either (I)-safe or near-final.

######  Proof 5.14.

Let $E={\left\\{f_{1}:e_{1},f_{2}:e_{2},f_{3}:e_{3}\right\\}}$. Reorder $E$ so
that $f_{1}\geq f_{2}\geq f_{3}$. From $f_{1}+f_{2}+f_{3}=n\geq 7$ we have
that $f_{1}\geq 3$ and $f_{2}\geq 2$. By symmetry, we can also assume that
$e_{1}$ is even. If either $e_{2}$ or $e_{3}$ is even, then the existence of
an (I)-safe pair follows from Lemma 5.7. So we can assume that $e_{2},e_{3}$
are odd.

Let $e={\textstyle\frac{1}{2}}(e_{2}+e_{3})$ and let
$E^{\prime}=E-{\left\\{e_{2},e_{3}\right\\}}\cup{\left\\{e,e\right\\}}$ be
obtained from mixing $e_{2}$ and $e_{3}$. Since $f_{2}\geq 2$, Lemma 5.5(c)
implies that condition (I.2) holds for $E^{\prime}$. This, and Observation
4(a) imply that if ${\|E^{\prime}\|}=2$ then, by Lemma 5.3, $E^{\prime}$ is
near-final and thus $(e_{2},e_{3})$ is a near-final pair. So for the rest of
the proof we assume that ${\|E^{\prime}\|}\geq 3$. (For $(e_{2},e_{3})$ to be
(I)-safe, it is now sufficient to prove that $E^{\prime}$ satisfies (I.1).)

If $e\neq e_{1}$, in $E^{\prime}$ we have at least three droplets with
concentration $e_{1}$ and at least two with concentration $e$, so $E^{\prime}$
satisfies (I.1). Otherwise, $e=e_{1}$. Now, $f_{2}=f_{3}$ implies that
$E^{\prime}$ is near-final (by partitioning $E^{\prime}$ into singletons
${\left\\{e_{1}\right\\}}$ and pairs ${\left\\{e_{2},e_{3}\right\\}}$), and
thus $(e_{2},e_{3})$ is a near-final pair. Instead, assume that $f_{2}>f_{3}$.
As ${\|E^{\prime}\|}\geq 3$ (and $e=e_{1}$), $f_{3}\geq 2$ and thus $f_{2}\geq
3$. This implies that in $E^{\prime}$ there are at least five droplets with
concentration $e_{1}$ and at least two droplets with concentration $e_{2}$, so
$E^{\prime}$ satisfies (I.1).

######  Lemma 5.15.

Assume that ${\|E\|}=4$. If $E$ satisfies Invariant (I) then $E$ has an
(I)-safe pair.

######  Proof 5.16.

Let $E={\left\\{f_{1}:e_{1},f_{2}:e_{2},f_{3}:e_{3},f_{4}:e_{4}\right\\}}$. By
symmetry and reordering, respectively, we can assume that $e_{1}$ is even and
that $f_{1}\geq f_{2}\geq f_{3}\geq f_{4}$. This, and condition (I.1) imply
that $f_{1}\geq f_{2}\geq 2$. We consider two cases, depending on the value of
$f_{1}$.

Case 1: $f_{1}\geq 3$. If at least one of $e_{2},e_{3},e_{4}$ is even, then
the existence of an (I)-safe pair follows from Lemma 5.7.

So assume now that $e_{2},e_{3},e_{4}$ are all odd. If $f_{3}\geq 2$, we
obtain an (I)-safe pair from Lemma 5.9. Otherwise, $f_{3}=f_{4}=1$, and we
obtain an (I)-safe pair from Lemma 5.11.

Case 2: $f_{1}=2$. Then $n\geq 7$ implies that $f_{2}=f_{3}=2$ as well. If two
concentrations among $e_{2},e_{3},e_{4}$ are even, or if $e_{2},e_{3},e_{4}$
are all odd, the existence of an (I)-safe pair follows from Lemma 5.9.

Otherwise, one of $e_{2},e_{3},e_{4}$ is even and two are odd. We then want to
mix $e_{4}$ with the one of $e_{1},e_{2},e_{3}$ that has the same parity as
$e_{4}$. For concreteness, assume that $e_{2}$ is even and $e_{3},e_{4}$ are
odd. (The argument in all other cases is the same.) We claim that
$(e_{3},e_{4})$ is (I)-safe. Indeed, let
$E^{\prime}=E-{\left\\{e_{3},e_{4}\right\\}}\cup{\left\\{e,e\right\\}}$, for
$e={\textstyle\frac{1}{2}}(e_{3}+e_{4})$. Since $f_{3}>1$, Lemma 5.5(c)
implies that condition (I.2) holds. In $E^{\prime}$ we have at least two
droplets with concentration $e$. If $e\neq e_{1}$, then $E^{\prime}$ has two
droplets with concentration $e_{1}\neq e$; otherwise, if $e=e_{1}$, then
$E^{\prime}$ has two droplets with concentration $e_{2}\neq e$. Thus condition
(I.1) holds for $E^{\prime}$.

######  Lemma 5.17.

Assume that ${\|E\|}\geq 5$. If $E$ satisfies Invariant (I) then $E$ has an
(I)-safe pair.

######  Proof 5.18.

Let $E={\left\\{f_{1}:e_{1},f_{2}:e_{2},...,f_{m}:e_{m}\right\\}}$, for $m\geq
5$. By symmetry and reordering, respectively, we can assume that $e_{1}$ is
even and that $f_{i}\geq f_{i+1}$, for $i=1,2,....,m-1$. By condition (I.1),
we have $f_{1},f_{2}\geq 2$. We consider several cases.

Case 1: $f_{1}\geq 3$. The same argument as in Case 1 in the proof of Lemma
5.15 applies here.

Case 2: $f_{1}=2$. Then $f_{2}=2$ as well. We have some sub-cases.

:

Case 2.1: $f_{3}=2$. In this case, choose three concentrations among
$e_{1},e_{2},e_{3},e_{4},e_{5}$ with the same parity. This will give us three
concentrations $e_{i},e_{j},e_{k}$ with the same parity and with $f_{i}=2$. If
$f_{j}=2$ or $f_{k}=2$, we obtain an (I)-safe pair from Lemma 5.9, otherwise
we obtain an (I)-safe pair from Lemma 5.11.

:

Case 2.2: $f_{3}=...=f_{m}=1$ and $e_{2}$ is odd. Among $e_{3},e_{4},e_{5}$
there are either two even or two odd concentrations. By symmetry, we can
assume $e_{3},e_{4}$ are even. This gives us three concentrations
$e_{i},e_{j},e_{k}$ that satisfy the assumptions of Lemma 5.11, so we obtain
an (I)-safe pair by applying this lemma.

:

Case 2.3: $f_{3}=...=f_{m}=1$ and $e_{2}$ is even. If any concentration among
$e_{3},e_{4},...,e_{m}$ is even, then we obtain an (I)-safe pair from Lemma
5.9. Otherwise, $e_{3},e_{4},\ldots,e_{m}$ are all odd. This set has $m-2=n-4$
droplets. Thus, by Lemma 5.5(b), there is at least one concentration $e_{i}$,
for $i\in{\left\\{3,4,...,m\right\\}}$, such that any pair $(e_{i},e_{j})$,
for $j\in{\left\\{3,4,...,m\right\\}}-{\left\\{i\right\\}}$, is
${\bar{p}}$-safe. Let
$E^{\prime}=E-{\left\\{e_{i},e_{j}\right\\}}\cup{\left\\{e,e\right\\}}$ be
obtained from mixing $e_{i}$ and $e_{j}$, for
$e={\textstyle\frac{1}{2}}(e_{i}+e_{j})$. By the choice of $e_{i}$,
$E^{\prime}$ satisfies (I.2). $E^{\prime}$ satisfies (I.1) because it has at
least two droplets with concentration $e_{1}$ and at least two droplets with
concentration $e_{2}$.

Completing the proof. We are now ready to complete the proof that Condition
(MC) in Theorem 1.1(a) is sufficient for perfect mixability when $n\geq 7$.
The argument follows the outline given at the beginning of this section and
depicted in Figure 4.

Assume that $C$ satisfies Condition (MC). If $C$ is already perfectly mixed
then we are done. Otherwise, as described earlier in the proof, we first
replace $C$ by configuration ${\check{C}}{\,\sqsubset\,}{\mathbb{Z}}$ such
that (i) ${\check{\mu}}={\textsf{ave}}({\check{C}})\in{\mathbb{Z}}$, all
values in ${\check{C}}$ are even, and ${\check{C}}$ is
${\bar{p}}$-incongruent, and (ii) $C$ is perfectly mixable with precision at
most $1$ if and only if ${\check{C}}$ is perfectly mixable with precision $0$.

Then we show that ${\check{C}}$ has a perfect-mixing sequence (with precision
$0$), converting ${\check{C}}$ into its perfect mixture
${\left\\{n:{\check{\mu}}\right\\}}$. To this end, we first perform some
mixing operations (at most two) that convert ${\check{C}}$ into a
configuration $E$ that either satisfies Invariant (I) or is near-final. If
this $E$ is near-final, we can complete the mixing sequence using Lemma 5.1.
If this $E$ is not near-final, then condition (I.2) implies that $E$ satisfies
Condition (MC) which, in turn, by Lemma 5.3, implies that ${\|E\|}\geq 3$.
Therefore, depending on the value of ${\|E\|}$, we can apply one of Lemmas
5.13, 5.15, or 5.17, to show that $E$ has a pair of concentrations that is
either (I)-safe or near-final. We can thus apply the above argument repeatedly
to $E$. As in Section 5.1, each mixing decreases the value of
${\Psi}(E)=\sum_{e\in E}(e-{\check{\mu}})^{2}$. Thus after a finite number of
steps we eventually convert $E$ into a near-final configuration (as in the
cases for Lemma 5.13), that has a mixing sequence by Lemma 5.1.

###  5.3. Proof for $n=5$

In this sub-section we prove that Condition (MC) in Theorem 1.1(a) is
sufficient for perfect mixability when $n=5$. The overall argument is similar
to the case $n\geq 7$ we considered in Section 5.2 (and depicted in Figure 4),
although this time we need a slightly different invariant. This is because in
the case when $n=5$ there are configurations that satisfy Invariant (I) but do
not contain any pair of concentrations whose mixing preserves Invariant (I).
For example, $E={\left\\{0,0,4,4,7\right\\}}$ with ${\textsf{ave}}(E)=3$
satisfies Invariant (I). The only pair of different concentrations with the
same parity is $(0,4)$; however, after mixing these concentrations, the new
configuration will violate condition (I.1).

Let $A{\,\sqsubset\,}{\mathbb{Z}}$ be a configuration with $n={|A|}=5$ and
${\textsf{ave}}(A)\in{\mathbb{Z}}$. We say that $A$ is _blocking_ if
$A={\left\\{3:a_{1},a_{2},a_{3}\right\\}}$ where
$a_{1}\neq{\textstyle\frac{1}{2}}(a_{2}+a_{3})$ and $a_{1}$ has parity
different than $a_{2},a_{3}$. Otherwise we say that $A$ is _non-blocking_. For
example, $A={\left\\{0,0,0,3,7\right\\}}$, with ${\textsf{ave}}(A)=2$, is
blocking. The intuition is that this $A$ has only one pair of same-parity
different concentrations, namely $(3,7)$, but this pair is not $5$-safe –
mixing $3$ and $7$ produces configuration
$A^{\prime}={\left\\{0,0,0,5,5\right\\}}$ that is $5$-congruent (in fact, it
also violates Condition (MC)).

So, assume that we are given a configuration $C$ with $n={|C|}=5$ and
$C\cup{\left\\{\mu\right\\}}{\,\sqsubset\,}{\mathbb{Z}}$, that satisfies
Condition (MC). As in Section 5.2, if $C$ is already perfectly mixed then we
are done. Otherwise we start by converting $C$ into a configuration
${\check{C}}{\,\sqsubset\,}{\mathbb{Z}}$, with
${\check{\mu}}={\textsf{ave}}({\check{C}})\in{\mathbb{Z}}$, such that (i) all
concentrations in ${\check{C}}$ are even, (ii) ${\check{C}}$ is
$5$-incongruent, and (iii) $C$ is perfectly mixable with precision at most $1$
if and only if ${\check{C}}$ is perfectly mixable with precision $0$.

We then simply take $E={\check{C}}$ (unlike in Section 5.2, we don’t need to
modify ${\check{C}}$). It thus remains to show that $E$ is perfectly mixable
with precision $0$. In order to do so, we will have $E$ maintain the following
Invariant (I’):

:

(I.0) $E{\,\sqsubset\,}{\mathbb{Z}}$ and ${\textsf{ave}}(E)={\check{\mu}}$,

:

(I.1’) $E$ is non-blocking, and

:

(I.2) $E$ is $5$-incongruent.

By the properties of ${\check{C}}$, the initial set $E$ satisfies conditions
(I.0) and (I.2) and, since all concentrations in $E$ are even, it also
satisfies (I.1’). Thus $E$ satisfies Invariant (I’) and the rest of the proof
is devoted to constructing a sequence of mixing operations that preserve
Invariant (I’) until $E$ becomes near-final, which can be mixed perfectly
using Lemma 5.1.

At this point, we observe that, although in the previous section we considered
the case $n\geq 7$, the claims in Lemma 5.5(a) and (c) hold also for $n=5$
(with ${\bar{p}}={\left\\{5\right\\}}$), and we will be using them in the
proof. (Lemma 5.5(b) does not apply to $n=5$, however.) We will also
frequently use Observation 4 (with ${\bar{p}}={\left\\{5\right\\}}$) that
follows directly from Lemma 5.3.

Preserving Invariant (I’). Assume that $E$ satisfies Invariant (I’). We say
that a pair of distinct concentrations in $E$ is _(I’)-safe_ if the
configuration obtained from $E$ by mixing these concentrations satisfies
Invariant (I’). (This is an analogue of the notion of (I)-safe pairs,
introduced in Section 5.2.) We now show that each configuration $E$ that
satisfies Invariant (I’) has a pair of concentrations that is either (I’)-safe
or near-final. As we will always choose a pair of concentrations with the same
parity for mixing, condition (I.0) will be trivially preserved, so in the
proofs below, to show that a pair is (I’)-safe, we will focus on explaining
why the other two conditions are preserved.

######  Lemma 5.19.

Assume that ${\|E\|}=3$. If $E$ satisfies Invariant (I’) then $E$ has a pair
of concentrations that is either (I’)-safe or near-final.

######  Proof 5.20.

Let $E={\left\\{f_{1}:e_{1},f_{2}:e_{2},f_{3}:e_{3}\right\\}}$. By symmetry
and reordering, respectively, we can assume that $e_{1}$ is even and that
$f_{1}\geq f_{2}\geq f_{3}$. We analyze two cases based on $f_{1}$’s value:

Case 1: $f_{1}=2$. Thus, $f_{2}=2$ and $f_{3}=1$. We consider two sub-cases.

:

Case 1.1: $e_{2}$ is even. We will mix $e_{1}$ and $e_{2}$, producing
$E^{\prime}={\left\\{e_{1},e_{2},e_{3},2:e\right\\}}$, for
$e={\textstyle\frac{1}{2}}(e_{1}+e_{2})$. Obviously,
$e\notin{\left\\{e_{1},e_{2}\right\\}}$. If $e=e_{3}$ then $E^{\prime}$ is
near-final (using the partition of $E^{\prime}$ into
${\left\\{e_{1},e_{2}\right\\}},{\left\\{e_{3}\right\\}},{\left\\{e_{3}\right\\}},{\left\\{e_{3}\right\\}}$)
and thus $(e_{1},e_{2})$ is a near-final pair. So, assume that $e\neq e_{3}$.

Since $f_{1}=2$, by Lemma 5.5(c), $E^{\prime}$ satisfies condition (I.2).
Further, as ${\|E^{\prime}\|}=4$, $E^{\prime}$ also satisfies condition
(I.1’). Therefore, $(e_{1},e_{2})$ is indeed (I’)-safe.

:

Case 1.2: $e_{2}$ is odd. Without loss of generality we can assume that
$e_{3}$ is even (by the odd-even symmetry between $e_{1}$ and $e_{2}$.) We mix
$e_{1}$ and $e_{3}$, and let $E^{\prime}$ be the resulting configuration.
Since $f_{1}=2$, by Lemma 5.5(c), pair $(e_{1},e_{3})$ is $5$-safe, so
$E^{\prime}$ satisfies condition (I.2). This, together with Lemma 5.3 (as
$n=5$ is prime), implies that ${\|E^{\prime}\|}>2$, which means that
${\textstyle\frac{1}{2}}(e_{1}+e_{3})\neq e_{2}$, implying in turn that
$E^{\prime}$ has two non-singletons. Thereby, $E^{\prime}$ satisfies (I.1’)
and thus we can conclude that pair $(e_{1},e_{3})$ is (I’)-safe.

Case 2: $f_{1}=3$. Thus, $f_{2}=f_{3}=1$. Since $E$ satisfies (I.1’) we have
that at least one of $e_{2}$ and $e_{3}$ is even. By symmetry, we can assume
that $e_{2}$ is even. We mix $e_{1}$ and $e_{2}$, and let $E^{\prime}$ be the
new configuration. As $f_{1}=3$, by Lemma 5.5(c), $E^{\prime}$ satisfies
(I.2). Further, ${\textstyle\frac{1}{2}}(e_{1}+e_{2})\neq e_{3}$, because
otherwise we would have ${\|E^{\prime}\|}=2$, contradicting Lemma 5.3. So
$E^{\prime}$ contains two non-singletons, and thus it satisfies condition
(I.1’). Therefore, pair $(e_{1},e_{2})$ is (I’)-safe.

######  Lemma 5.21.

Assume that ${\|E\|}=4$. If $E$ satisfies Invariant (I’) then $E$ has an
(I’)-safe pair.

######  Proof 5.22.

Let $E={\left\\{f_{1}:e_{1},f_{2}:e_{2},f_{3}:e_{3},f_{4}:e_{4}\right\\}}$. By
symmetry and reordering, respectively, we can assume that $e_{1}$ is even and
that $f_{1}=2$ and $f_{2}=f_{3}=f_{4}=1$. We analyze three cases based on the
parities of $e_{2},e_{3},e_{4}$.

Case 1: At least two of $e_{2},e_{3},e_{4}$ are even. Assume without loss of
generality that $e_{2},e_{3}$ are even. Let
$e={\textstyle\frac{1}{2}}(e_{1}+e_{2})$. Further, assume that $e\neq e_{4}$
(for otherwise we can use $e_{3}$ instead of $e_{2}$). Let
$E^{\prime}=E-{\left\\{e_{1},e_{2}\right\\}}\cup{\left\\{e,e\right\\}}$ be
obtained by mixing $e_{1}$ and $e_{2}$. As $f_{1}=2$, $E^{\prime}$ satisfies
(I.2) by Lemma 5.5(c). If $e\neq e_{3}$ then ${\|E^{\prime}\|}=4$, so
$E^{\prime}$ satisfies (I.1’). If $e=e_{3}$ then
$E^{\prime}={\left\\{e_{1},3:e_{3},e_{4}\right\\}}$ and $e_{1},e_{3}$ are
even, so $E^{\prime}$ satisfies (I.1’) as well. Thus, pair $(e_{1},e_{2})$ is
(I’)-safe.

Case 2: Exactly one of $e_{2},e_{3},e_{4}$ is even. Assume without loss of
generality that $e_{2}$ is even. Let $e={\textstyle\frac{1}{2}}(e_{1}+e_{2})$,
and let
$E^{\prime}=E-{\left\\{e_{1},e_{2}\right\\}}\cup{\left\\{e,e\right\\}}$ be
obtained by mixing $e_{1}$ and $e_{2}$. $E^{\prime}$ satisfies (I.2) by Lemma
5.5(c). If $e\in E$ then $e\in{\left\\{e_{3},e_{4}\right\\}}$, where both
$e_{3},e_{4}$ are odd, and one of $e_{3},e_{4}$ is a non-singleton in
$E^{\prime}$. Otherwise, $e\notin E$ and thus ${\|E^{\prime}\|}=4$. Either way
$E^{\prime}$ satisfies (I.1’) and thus pair $(e_{1},e_{2})$ is (I’)-safe.

Case 3: $e_{2},e_{3},e_{4}$ are all odd. By Lemma 5.5(a) there is at most one
$5$-unsafe pair. Assume that $(e_{2},e_{3})$ is $5$-safe (otherwise use
$e_{4}$ instead of $e_{3}$). Thus mixing $e_{2}$ and $e_{3}$ produces
$E^{\prime}=E-{\left\\{e_{2},e_{3}\right\\}}\cup{\left\\{e,e\right\\}}$, for
$e={\textstyle\frac{1}{2}}(e_{2}+e_{3})$, that satisfies condition (I.2).
Moreover, $e\in E$ would imply ${\|E^{\prime}\|}=2$ (contradicting Lemma 5.3),
so we must have $e\notin E$, and thus both $e_{1}$ and $e$ are non-singletons
in $E^{\prime}$. Therefore, $E^{\prime}$ preserves (I.1’) and pair
$(e_{2},e_{3})$ is (I’)-safe.

######  Lemma 5.23.

Assume that ${\|E\|}=5$. If $E$ satisfies Invariant (I’) then $E$ has an
(I’)-safe pair.

######  Proof 5.24.

Let $E={\left\\{e_{1},e_{2},e_{3},e_{4},e_{5}\right\\}}$. By symmetry and
reordering we can assume that $e_{1},e_{2},e_{3}$ have the same parity, say
even. Additionally, by Lemma 5.5(a), there is at most one $5$-unsafe pair in
$E$, so we can assume that it does not involve $e_{1}$. In other words, all
pairs involving $e_{1}$ and any other even concentration are $5$-safe. We now
have three cases, given below. In each case we mix $e_{1}$ with some other
even concentration, so conditions (I.0) and (I.2) will be satisfied, and we
only need to ensure that (I.1’) is satisfied as well in order to show an
(I’)-safe pair in $E$.

Case 1: $e_{4}$ and $e_{5}$ are even. Choose $i\neq 1$ for which
$|e_{1}-e_{i}|$ is minimized, and let
$e={\textstyle\frac{1}{2}}(e_{1}+e_{i})$. Then $e\notin E$. Mixing $e_{1}$ and
$e_{i}$ gives us configuration
$E^{\prime}=E-{\left\\{e_{1},e_{i}\right\\}}\cup{\left\\{e,e\right\\}}$ with
${\|E^{\prime}\|}=4$, so $E^{\prime}$ satisfies (I.1’).

Case 2: $e_{4}$ and $e_{5}$ have different parity. Say that $e_{4}$ is even
and $e_{5}$ is odd. Let $e={\textstyle\frac{1}{2}}(e_{1}+e_{2})$ and, without
loss of generality, assume that $e\neq e_{5}$ (otherwise, use $e_{3}$ instead
of $e_{2}$). Mixing $e_{1}$ and $e_{2}$ gives us configuration
$E^{\prime}=E-{\left\\{e_{1},e_{2}\right\\}}\cup{\left\\{e,e\right\\}}$. If
$e\notin E$, then ${\|E^{\prime}\|}=4$. Otherwise,
$e\in{\left\\{e_{3},e_{4}\right\\}}$ and, as $e_{3},e_{4}$ are both even,
$E^{\prime}$ is non-blocking. Thus in both sub-cases $E^{\prime}$ satisfies
(I.1’).

Case 3: $e_{4}$ and $e_{5}$ are odd. Without loss of generality, assume that
$|e_{1}-e_{2}|\leq|e_{1}-e_{3}|$. Then
$e={\textstyle\frac{1}{2}}(e_{1}+e_{2})\neq e_{3}$. Let
$E^{\prime}=E-{\left\\{e_{1},e_{2}\right\\}}\cup{\left\\{e,e\right\\}}$ be
obtained by mixing $e_{1}$ and $e_{2}$. If $e\notin E$, then
${\|E^{\prime}\|}=4$. Otherwise, $e\in{\left\\{e_{4},e_{5}\right\\}}$ and, as
$e_{4},e_{5}$ are both odd, $E^{\prime}$ is non-blocking. Thus in both sub-
cases $E^{\prime}$ satisfies (I.1’).

Completing the proof. We can now prove that Condition (MC) in Theorem 1.1(a)
is sufficient for perfect mixability when $n=5$. Assume that $C$ satisfies
Condition (MC). If $C$ is perfectly mixed, then we are done. Otherwise, as
described earlier in this section, we convert $C$ into configuration
${\check{C}}{\,\sqsubset\,}{\mathbb{Z}}$ such that $C$ is perfectly mixable
with precision at most $1$ if and only if ${\check{C}}$ is perfectly mixable
with precision $0$. This ${\check{C}}$ is $5$-incongruent, all its
concentrations are even, and it satisfies
${\check{\mu}}={\textsf{ave}}({\check{C}})\in{\mathbb{Z}}$. Thus, if we take
$E={\check{C}}$, this $E$ satisfies Invariant (I’).

If $E$ is near-final, then we use Lemma 5.1 to perfectly mix $E$. If this $E$
is not near-final, then, depending on the value of ${\|E\|}$, we apply one of
Lemmas 5.19, 5.21, or 5.23, to show that $E$ has a pair of concentrations that
is either (I’)-safe or near-final. As in Section 5.2, the value of ${\Psi}(E)$
decreases at least by $1$ after each mixing operation. So after a finite
sequence of mixing operations involving (I’)-safe pairs, $E$ must become near-
final (as in the cases for Lemma 5.19), which we then perfectly mix using
Lemma 5.1.

###  5.4. Proof for $n=6$

We now sketch the proof that Condition (MC) in Theorem 1.1(a) is sufficient
for perfect mixability when $n=6$. This proof can be obtained by modifying the
proof for $n=5$ in Section 5.3. This modification takes advantage of the fact
that the proof for $n=5$ relies on $n=5$ having only one odd prime factor,
which is also true for $n=6$. As for $n=5$, Lemma 5.5(a) and (c) hold also for
$n=6$ (with ${\bar{p}}={\left\\{3\right\\}}$).

The overall structure of the argument is identical. Let
$C\cup{\left\\{\mu\right\\}}{\,\sqsubset\,}{\mathbb{Z}}$ be the given
configuration satisfying Condition (MC). If $C$ is perfectly mixed, we are
done. Otherwise, construct ${\check{C}}$ as in Section 5.2 and take
$E={\check{C}}$. We then repeatedly mix (I’)-safe pairs in $E$ until it
becomes near-final, which can be perfectly mixed using Lemma 5.1.

The definition of Invariant (I’) (and thus the corresponding concept of
(I’)-safe pairs) is adjusted in a natural way: Condition (I.2) now requires
$E$ to be 3-incongruent. Further, a configuration $A$ is now called _blocking_
if $A={\left\\{4:a_{1},a_{2},a_{3}\right\\}}$ where
$a_{1}\neq{\textstyle\frac{1}{2}}(a_{2}+a_{3})$ and $a_{1}$ has parity
different than $a_{2},a_{3}$.

Given a configuration $E$ that satisfies Invariant (I’), we identify an
(I’)-safe pair in $E$ using appropriate analogues of Lemmas 5.19, 5.21, and
5.23 (with the last lemma extended to cover the case when ${\|E\|}=6$).
Intuitively, these proofs are now in fact easier, because there are more
choices for (I’)-safe pairs.

Here is one possible way to adapt these proofs, essentially by reducing the
argument to the case for $n=5$. Instead of $E$, consider the configuration
${\tilde{E}}=E-{\left\\{{\tilde{e}}\right\\}}$ where ${\tilde{e}}\in E$ is a
concentration with maximum multiplicity. Then ${|{\tilde{E}}|}=5$, and $E$ is
non-blocking (for $n=6$) if and only if ${\tilde{E}}$ is non-blocking (for
$n=5$). We now apply the analysis from Lemmas 5.19, 5.21, and 5.23 to identify
an (I’)-safe mixing pair for ${\tilde{E}}$ (except that we maintain
$3$-incongruence instead of $5$-incongruence, since the only odd prime factor
of $6$ is $3$). We then use this pair for $E$.

There is one case where this suggested adaptation of the proof needs a
modification, namely Case 1.1 in Lemma 5.19. In this case we have
$E={\left\\{3:e_{1},2:e_{2},e_{3}\right\\}}$, so ${\tilde{e}}=e_{1}$ and
${\tilde{E}}={\left\\{2:e_{1},2:e_{2},e_{3}\right\\}}$. We also have that
$e_{1}$ and $e_{2}$ are even, and the proof uses the fact that
${\textstyle\frac{1}{2}}(e_{1}+e_{2})=e_{3}$ implies that ${\tilde{E}}$ is
near-final, and thus $(e_{1},e_{2})$ is a near-final pair. However, this
implication is not true for $E$. Nevertheless, pair $(e_{1},e_{2})$ is
(I’)-safe for $n=6$ even if ${\textstyle\frac{1}{2}}(e_{1}+e_{2})=e_{3}$, by
applying Lemma 5.5(c) to show that after mixing condition (I.2) holds, and
using the fact that the new configuration has two non-singletons $e_{1}$ and
$e_{3}$ to show that condition (I.1’) holds.

##  6\. Polynomial bound for the number of mixing operations

Let $C{\,\sqsubset\,}{\mathbb{Z}}$ with ${\textsf{ave}}(C)\in{\mathbb{Z}}$ and
${|C|}=n\geq 4$ be a configuration that satisfies Condition (MC). The
existence of a perfect-mixing graph for $C$ was established in Section 5. This
graph, however, might be very large – it can be shown that if arbitrary
droplets are mixed at each step then it might take an exponential number of
steps for the process to converge. In this section we prove Theorem 1.1(b),
namely that $C$ can be perfectly mixed with precision at most $1$ and in a
polynomial number of mixing operations. The essence of the proof is to show
that in the construction in Section 5 it is possible to choose a mixing
operation at each step so that the overall number of steps will be polynomial
in the input size. We assume here that the reader is familiar with the results
from Section 5; in fact, some of the lemmas or observations from that section
may be used here occasionally without an explicit reference.

It is sufficient to show that configuration $E$, constructed from $C$ in
Section 5.2, is perfectly mixable with precision $0$ in a polynomial number of
mixing operations. (As described in Section 5.2, constructing such $E$ from
$C$ requires only two mixing operations. Recall that this construction also
involves a linear mapping, but this mapping does not change the constructed
mixing graph.) For this reason we will assume in this section that $E$ is the
initial configuration.

Recall that ${\Psi}(E)=\sum_{e\in E}(e-{\hat{\mu}})^{2}$, where
${\hat{\mu}}={\textsf{ave}}(E)\in{\mathbb{Z}}$. We use ${\Psi}(E)$ to measure
the progress of the mixing process, ultimately showing that ${\Psi}(E)$ can be
decreased down to $0$ after a number of steps that is polynomial in the
initial value of $\log{\Psi}(E)$, and thus also in $s(E)$, the size of $E$.
(What we actually show is that after the mixing process we achieve
${\Psi}(E)\leq 1$. Since
$E\cup{\left\\{{\hat{\mu}}\right\\}}\subseteq{\mathbb{Z}}$, this implies that
in fact ${\Psi}(E)=0$.)

The general idea is to always mix two concentrations whose difference is large
enough, so that after a polynomial number of mixing operations, ${\Psi}(E)$
decreases at least by a factor of ${\textstyle\frac{1}{2}}$. This is
sufficient to establish a polynomial bound for the whole process. Of course,
the pair of concentrations that we mix must either preserve the corresponding
invariant or produce a near-final configuration. When $n$ is a power of $2$,
it is relatively simple to identify good pairs to mix (see Section 6.2),
because then we only need to ensure that the concentrations mixed at each step
have the same parity. This also easily extends to near-final configurations.
For arbitrary configurations $E$ (that satisfy the appropriate invariant),
however, identifying such good pairs to mix is more challenging (see Sections
6.3 and 6.4).

In the following sub-sections, we will present some auxiliary mixing sequences
that will be later combined to construct a polynomial-length mixing sequence
for $E$. To streamline the arguments, we will focus on estimating the length
of these sequences; that these mixing sequences can actually be computed in
polynomial time will be implicit in their construction. We will return to the
time complexity analysis in Section 7.

###  6.1. Auxiliary observations

Let $A{\,\sqsubset\,}{\mathbb{Z}}$ with
${\textsf{ave}}(A)=\mu_{A}\in{\mathbb{Z}}$ and ${|A|}=n_{A}$ be an arbitrary
configuration (that is, a multiset of integers). We define $\min(A)$ and
$\max(A)$ as the lowest and highest concentrations in $A$, respectively. We
also define the diameter of $A$ as ${\textsf{diam}}(A)=\max(A)-\min(A)$.
Recall that the size of $A$ is defined as $s(A)=\sum_{a\in A}\log(|a|+2)$. We
denote by $A_{even}$ and $A_{odd}$ two disjoint multisets containing all even
and odd concentrations in $A$, respectively. We use notation
$\pi\in{\left\\{even,odd\right\\}}$ for a parity value, with
${\bar{\pi}}\in{\left\\{even,odd\right\\}}$ standing for the opposite parity
(that is ${\bar{\pi}}\neq\pi$), and we use these for subscripts, as in
$A_{\pi}$ and $A_{{\bar{\pi}}}$. In the contexts when $A$ is subjected to some
mixing sequence, we will use notation ${\Psi}_{A,0}$ as the initial value of
${\Psi}(A)$, before any mixing has been performed on $A$.

The following observations show that repeatedly mixing two droplets with
concentrations that are sufficiently far apart eventually decreases
${\Psi}(A)$ at least by a factor of ${\textstyle\frac{1}{2}}$.

######  Observation 5.

Let $x,y\in A$ be two different concentrations with the same parity, and let
$A^{\prime}$ be obtained from $A$ by mixing $x$ and $y$. Then:

:

(a) ${\Psi}(A^{\prime})<{\Psi}(A)$.

:

(b) If $\gamma\in{\mathbb{Z}_{>0}}$ is a constant and
$|x-y|\geq{\textsf{diam}}(A)/\gamma$, then
${\Psi}(A^{\prime})\;\leq\;\big{(}1-\frac{1}{2\gamma^{2}n_{A}}\big{)}{\Psi}(A)$.

######  Proof 6.1.

Without loss of generality we can assume that $\mu_{A}=0$, so that
${\Psi}(A)=\sum_{a\in A}a^{2}$. Note that we then also have
${\textsf{ave}}(A^{\prime})=\mu_{A^{\prime}}=0$. Part (a) now follows by
simple calculation:

${\Psi}(A)-{\Psi}(A^{\prime})\;=\;x^{2}+y^{2}-2\Big{(}\frac{x+y}{2}\Big{)}^{2}\;=\;\frac{(x-y)^{2}}{2}>0.$

To prove (b), we use the above calculation and inequality ${\Psi}(A)\leq
n_{A}{\textsf{diam}}(A)^{2}$ (that follows directly from the definition of
${\Psi}(A)$):

${\Psi}(A)-{\Psi}(A^{\prime})\;=\;\frac{(x-y)^{2}}{2}\;\geq\;\frac{{\textsf{diam}}(A)^{2}}{2\gamma^{2}}\;\geq\;\frac{{\Psi}(A)}{2\gamma^{2}n_{A}},$

completing the proof.

######  Observation 6.

Let $\gamma\in{\mathbb{Z}_{>0}}$ be a constant. Let $A^{\prime}$ be obtained
from $A$ by a sequence of $2\gamma^{2}n_{A}$ mixing operations, each involving
droplets $x,y\in A$ that satisfy $|x-y|\geq{\textsf{diam}}(A)/\gamma$. Then
${\Psi}(A^{\prime})\leq{\Psi}(A)/2$.

######  Proof 6.2.

Applying Observation 5(b) repeatedly, for each of the $2\gamma^{2}n_{A}$
mixing steps, we obtain

${\Psi}(A^{\prime})\leq{\Psi}(A)\Big{(}1-\frac{1}{2\gamma^{2}n_{A}}\Big{)}^{2\gamma^{2}n_{A}}\leq\frac{{\Psi}(A)}{2},$

where the last inequality holds because $(1-1/k)^{k}\leq 1/2$ for $k\geq 2$.

We state two more observations that will be used later in the proof, typically
without an explicit reference.

######  Observation 7.

$\log{{\Psi}(A)}\leq 2s(A)$.

######  Proof 6.3.

Let $\psi_{A}(x)=\sum_{a\in A}(a-x)^{2}$. By calculus, we have that
$\psi_{A}(x)$ is minimized for $x=\mu_{A}$, and thus

${\Psi}(A)\;=\;\psi_{A}(\mu_{A})\;\leq\;\psi_{A}(0)\;=\;\sum_{a\in
A}a^{2}\;\leq\Big{(}\,\sum_{a\in A}|a|\,\Big{)}^{2}.$

Therefore

$\displaystyle\log{\Psi}(A)$ $\displaystyle\leq\;\log\Big{(}\,\sum_{a\in
A}|a|\,\Big{)}^{2}$ $\displaystyle\leq\;2\log\prod_{a\in
A}\big{(}|a|+2\big{)}\;=\;2\sum_{a\in A}\log(|a|+2)\;=\;2s(A),$

completing the proof.

######  Observation 8.

Let $A^{\prime}\subseteq A$. Then ${\Psi}(A^{\prime})\leq{\Psi}(A)$.

######  Proof 6.4.

Using the properties of the function $\psi_{A}(x)$ from the proof of
Observation 7, we have

${\Psi}(A^{\prime})\;=\;\psi_{A^{\prime}}(\mu_{A^{\prime}})\;\leq\;\psi_{A^{\prime}}(\mu_{A})\;\leq\;\psi_{A}(\mu_{A})\;=\;{\Psi}(A),$

where the second inequality follows from $A^{\prime}\subseteq A$.

###  6.2. Proof for near-final configurations

In this sub-section we prove that $E$ can be perfectly mixed with precision
$0$ in a polynomial number of mixing operations when ${|E|}=n$ is a power of
$2$. This extends easily to near-final configurations.

Assume that $n$ is a power of $2$. To establish our upper bound, we consider a
sequence of mixing operations on $E$, where at each step we mix farthest-apart
same-parity concentrations in $E$. These concentrations are both in the same
set $E_{\pi}$, but the two droplets obtained from mixing can be either in
$E_{\pi}$ or in $E_{\bar{\pi}}$. Thus this mixing sequence might change
cardinalities and structure of these sets over time. To obtain our bound, we
will need to analyze how these sets evolve during the segments of mixing
operations that preserve parity (namely when mixing in each $E_{\pi}$ produces
a concentration in the same $E_{\pi}$).

More specifically, the proof idea is this: By the choice of the mixing pair,
if the mixed concentrations are far apart (say, they differ at least by
${\textsf{diam}}(E)/3$), then the value of ${\Psi}(E)$ will significantly
decrease, per Observation 5(b). Otherwise, if the mixed concentrations are
close to each other, the subsets $E_{even}$ and $E_{odd}$ must be separated by
a gap of at least ${\textsf{diam}}(E)/3$. For such a separated configuration,
the decreases of ${\Psi}(E)$ may be very small (because the diameters of
$E_{even}$ and $E_{odd}$ may be small compared to ${\textsf{diam}}(E)$). We
show, however, that after at most a polynomial number of steps there will be a
mixing operation in some $E_{\pi}$ that will produce a concentration with
parity ${\bar{\pi}}$. This guarantees that at the next step the diameter of
$E_{{\bar{\pi}}}$ is large, so in this step ${\Psi}(E)$ will decrease
significantly.

The above intuition is formalized in the proof of Lemma 6.7 below. We first
prove the following auxiliary lemma.

######  Lemma 6.5.

Let $\pi\in{\left\\{even,odd\right\\}}$. Consider a sequence of farthest-apart
mixing operations on $E_{\pi}\subseteq E$, such that each mixing in $E_{\pi}$
produces a concentration with the same parity $\pi$. If this sequence contains
$4ns(E)$ mixing operations, then after this sequence we have
${\|E_{\pi}\|}=1$.

######  Proof 6.6.

Recall that ${\Psi}_{E_{\pi},0}$ denotes the value of ${\Psi}(E_{\pi})$ before
any mixing has been performed. Let ${|E_{\pi}|}=n_{\pi}$. By Observation 6
(with $\gamma=1$), if we repeatedly mix $\min(E_{\pi})$ with $\max(E_{\pi})$,
then after at most $2n_{\pi}$ mixes the value of ${\Psi}(E_{\pi})$ decreases
at least by a factor of ${\textstyle\frac{1}{2}}$. Thus, after at most
$2n_{\pi}\log{{\Psi}_{E_{\pi},0}}$ such mixing operations we must have
${\Psi}(E_{\pi})=0$; that is ${\|E_{\pi}\|}=1$. (More precisely, we achieve
${\Psi}(E_{\pi})\leq 1$. Since all concentrations in $E_{\pi}$ have the same
parity, by simple calculation, this implies that in fact ${\Psi}(E_{\pi})=0$.
It is worth to point out here that this argument is different than our earlier
argument for ${\Psi}(E)$, since in this case ${\textsf{ave}}(E_{\pi})$ may not
be integer.) To complete the proof, note that $n_{\pi}\leq n$ and
${\Psi}_{E_{\pi},0}\leq{\Psi}_{E,0}$ and therefore
$2n_{\pi}\log{{\Psi}_{E_{\pi},0}}\leq 2n\log{{\Psi}_{E,0}}\leq 4ns(E)$.

######  Lemma 6.7.

After any sequence of at most $8ns(E)$ farthest-apart same-parity mixing
operations, ${\Psi}(E)$ decreases at least by a factor of $1-1/18n$.

######  Proof 6.8.

The proof follows the idea outlined at the beginning of this section. Let
$\delta={\textsf{diam}}(E)$, be the (initial) diameter of $E$. If the
farthest-apart same-parity pair $x,y\in E$ satisfies $|x-y|\geq\delta/3$, then
by Observation 5, mixing $x$ and $y$ decreases ${\Psi}(E)$ at least by a
factor of $1-1/18n$, and we are done.

Otherwise, we have that any two same-parity concentrations differ by at most
$\delta/3$. Consider $E_{even}$ and $E_{odd}$. By the case assumption, these
sets are not empty. Assume without loss of generality that
$\max(E_{odd})>\max(E_{even})$. We then have that
$\min(E_{odd})>\max(E_{odd})-\delta/3$, $\min(E)=\min(E_{even})$ and
$\max(E_{even})<\min(E_{even})+\delta/3$. Hence,
$\min(E_{odd})\geq\max(E_{even})+\delta/3$.

Now, from Lemma 6.5, we derive that it takes at most $4ns(E)$ farthest-apart
mixing operations on $E_{even}$ for either an odd concentration to be produced
or for ${\|E_{even}\|}=1$ to hold (similarly for $E_{odd}$). Thus, if we
repeatedly mix farthest-apart same-parity droplets in $E$, eventually, after
fewer than $8ns(E)$ such mixing operations, either a mixing in $E_{even}$ will
produce an odd concentration or a mixing in $E_{odd}$ will produce an even
concentration. (This is true because we cannot have both ${\|E_{even}\|}=1$
and ${\|E_{odd}\|}=1$: as mentioned in the proof for Lemma 5.1, $n$ being a
power-of-$2$ guarantees the existence of two distinct concentrations with
same-parity.)

So, if an odd $x$ was produced from a mixing in $E_{even}$, then we can mix
$x$ with $\max(E_{odd})$. Otherwise, an even $y$ was produced from a mixing in
$E_{odd}$ and we can mix $y$ with $\min(E_{even})$. As both
$|x-\max(E_{odd})|$ and $|y-\min(E_{even})|$ are at least $\delta/3$, either
mixing decreases ${\Psi}(E)$ at least by a factor of $1-1/18n$ (see
Observation 5), and thus the lemma holds.

Using Lemma 6.7 we can now establish a bound on the length of mixing sequences
when $n$ is a power of $2$, and, more generally, when $E$ is near-final.

######  Theorem 6.9.

If ${|E|}=n$ is a power of $2$, then $E$ can be perfectly mixed with precision
$0$ by a mixing sequence of length at most $288n^{2}s^{2}(E)$.

######  Proof 6.10.

By Lemma 6.7, after a mixing sequence of at most $8ns(E)$ same-parity
farthest-apart mixing operations, ${\Psi}(E)$ decreases at least by a factor
of $(1-1/18n)$. It follows that after at most $18n$ such mixing sequences,
${\Psi}(E)$ decreases at least by a factor of ${\textstyle\frac{1}{2}}$ (see
the proof of Observation 6). Consequently, after at most
$18n\log{{\Psi}_{E,0}}$ such mixing sequences, $E$ becomes perfectly mixed.
Finally, as $\log{{\Psi}_{E,0}}\leq 2s(E)$ and each mixing sequence contains
at most $8ns(E)$ mixing operations, we obtain that the total number of mixing
operations is at most
$(18n\log{{\Psi}_{E,0}})\cdot(8ns(E))\leq(36ns(E))\cdot(8ns(E))=288n^{2}s^{2}(E)$.

######  Theorem 6.11.

If $E$ is near-final, then $E$ can be perfectly mixed, with precision $0$, by
a mixing sequence of length at most $144n^{3}s^{2}(E)$.

######  Proof 6.12.

Assume that $E$ is near-final. Recall that ${\textsf{ave}}(E)={\hat{\mu}}$. By
definition, $E$ can be partitioned into singletons ${\hat{\mu}}$ and at most
$n/2$ disjoint multisets $A\subseteq E$, each satisfying
${\textsf{ave}}(A)={\hat{\mu}}$ and having cardinality that is a (non-zero)
power of $2$. By Theorem 6.9 above, each multiset $A$ in this partition can be
perfectly mixed with at most $288n^{2}s^{2}(E)$ mixing operations, and the
theorem holds.

###  6.3. An exponential bound on mixing sequences

In this sub-section we give a simple upper bound on the number of mixing
operations to perfectly mix $E$ with precision $0$ when ${|E|}=n\geq 5$. This
bound is exponential in $n$ — so it’s too weak for our purpose for general $n$
— but we will use it only to get a polynomial bound when $n$ is at most $22$
(see Theorem 6.17).

Let $E$ satisfy Invariant $(\lambda)$, where $\lambda=I^{\prime}$ for $n=5,6$
and $\lambda=I$ for $n\geq 7$. Also, let $A\subseteq E$. We say that a pair of
distinct concentrations in $A$ is _$(\lambda)$ -safe_ if it is
$(\lambda)$-safe with respect to $E$, that is, if mixing this pair preserves
Invariant $(\lambda)$ for $E$. If there is no $(\lambda)$-safe pair in $A$
then we say that $A$ is _$(\lambda)$ -mixed_. Recall that, since $E$ satisfies
Invariant $(\lambda)$, according to the properties established in Sections 5.2
and 5.3, it is guaranteed that in $E$ there exists a pair of concentrations
that is either $(\lambda)$-safe or near-final; however, this pair may not be
in the set $A$ under consideration. (In other words, $A$ being
$(\lambda)$-mixed does not mean that all droplets in $A$ have the same
concentration — it only means that we cannot mix any pairs from $A$ in our
perfect-mixing sequence for $E$.)

First, in Lemma 6.13 below we show an upper bound on the number of mixing
operations to $(\lambda)$-mix a subset $A\subseteq E$. Then, we prove Theorem
6.15 that gives an upper bound for the number of mixing operations to
perfectly mix $E$ with precision $0$.

######  Lemma 6.13.

Assume that $E$ satisfies Invariant $(\lambda)$. If $A\subseteq E$ and
${|A|}=k$, then $A$ can be $(\lambda)$-mixed with precision $0$ by a mixing
sequence of length at most $(8k^{3}s(A))^{k}$.

######  Proof 6.14.

We prove the lemma by induction with respect to $k$. Let $\phi(A)$ denote the
number of furthest-apart $(\lambda)$-safe mixing operations needed to
$(\lambda)$-mix $A$. We use induction to prove that
$\phi(A)\leq(8k^{3}s(A))^{k}$. This will imply the lemma.

In the base case, when $k\leq 1$, we have $\phi(A)=0$, since $A$ is trivially
$(\lambda)$-mixed. So for the rest of the proof assume that $k\geq 2$ and that
every $A^{\prime}\subset A$ with ${|A^{\prime}|}=k^{\prime}<k$ can be
$(\lambda)$-mixed in
$\phi(A^{\prime})\leq(8{k^{\prime}}^{3}s(A^{\prime}))^{k^{\prime}}$ mixing
operations. We next show that $A$ can be $(\lambda)$-mixed in at most
$(8k^{3}s(A))^{k}$ mixing operations.

If $A$ is already $(\lambda)$-mixed then we are done. Otherwise, let $x,y\in
A$ be the furthest-apart $(\lambda)$-safe pair. If
$|x-y|\geq{\textsf{diam}}(A)/k$, we will call pair $x,y$ _acceptable_. If this
pair $x,y$ is acceptable then mixing $x$ and $y$ decreases ${\Psi}(A)$ at
least by a factor of $1-1/2k^{3}$ (by applying Observation 5 with $\gamma=k$
and $n_{A}=k$). Then, by Observation 6, after at most $2k^{3}$ such acceptable
mixing operations ${\Psi}(A)$ decreases at least by a factor of
${\textstyle\frac{1}{2}}$, and it follows that after at most
$2k^{3}\log{{\Psi}_{A,0}}$ such mixing operations, $A$ becomes
$(\lambda)$-mixed. However, there may be many steps where there is no
acceptable pair. To address this, we show below a strategy (basically a
divide-and-conquer approach) that will bound the number of consecutive steps
needed for an acceptable pair to appear.

Let $\delta={\textsf{diam}}(A)$ before any mixing operation. Divide the
interval $[\min(A),\max(A)]$ into $k$ equal segments such that for at least
one segment, say $[l,r]$, no concentration in $A$ lies withing the open
interval $(l,r)$. Split $A$ into $A_{1}$ and $A_{2}$ such that
$\max(A_{1})\leq l$ and $\min(A_{2})\geq r$. Let $k_{i}=|A_{i}|$, for $i=1,2$.
By our inductive assumption, each $A_{i}$ can be $(\lambda)$-mixed in
$\phi(A_{i})\leq(8k_{i}^{3}s(A_{i}))^{k_{i}}<(8k^{3}s(A))^{k-1}$ mixing
operations, respectively. Therefore, after at most
$\phi(A_{1})+\phi(A_{2})+1\leq 2(8k^{3}s(A))^{k-1}$ mixing operations, one of
two things must happen: either (i) $A$ is already $(\lambda)$-mixed, or (ii)
there are $x\in A_{1}$ and $y\in A_{2}$ that form an $(\lambda)$-safe pair. In
option (ii), $x,y$ are in fact an acceptable pair, by the choice of the
segment $[l,r]$. As argued in the paragraph above, if we repeat the above
strategy, option (ii) can be repeated no more than $2k^{3}\log{{\Psi}_{A,0}}$
times before $A$ becomes $(\lambda)$-mixed. Since $\log{{\Psi}_{A,0}}\leq
2s(A)$, it follows that

$\displaystyle\phi(A)\;$ $\displaystyle\leq\;2k^{3}\log{\Psi}_{A,0}\cdot
2(8k^{3}s(A))^{k-1}$ $\displaystyle\leq\;4k^{3}s(A)\cdot
2(8k^{3}s(A))^{k-1}\;\leq\;(8k^{3}s(A))^{k},$

completing the inductive step and the proof of the lemma.

######  Theorem 6.15.

If $|E|=n\geq 5$, then $E$ can be perfectly mixed with a mixing sequence of
length at most $(8n^{3}s(E))^{n}+144n^{3}s^{2}(E)$.

######  Proof 6.16.

Let $E$ satisfy Invariant $(\lambda)$, where $\lambda=I$ for $n\geq 7$ and
$\lambda=I^{\prime}$ for $n=5,6$. We know that if $E$ satisfies Invariant
$(\lambda)$ then $E$ has a pair of concentrations that is either
$(\lambda)$-safe or near-final. Therefore, we first $(\lambda)$-mix $E$ using
Lemma 6.13, which produces a near-final pair. (Such a near-final pair becomes
available because, as sown in Sections 5.2 and 5.3, $E$ satisfying Invariant
($\lambda$) guarantees the existence of a pair that is either ($\lambda$)-safe
or near-final, and as $E$ is $(\lambda)$-mixed, the later must hold.) We then
mix this near-final pair, producing $E$ near-final that can be perfectly mixed
using Theorem 6.11. The total number of mixing operations in this sequence is
at most $(8n^{3}s(E))^{n}+144n^{3}s^{2}(E)$.

###  6.4. A polynomial bound on mixing sequences

We now complete the proof of Theorem 1.1(b). In Section 5 we have already
established an existence of a perfect-mixing sequence for $C$ with
intermediate precision $1$. It still remains to show that this mixing sequence
can be modified to have length that is polynomial in $s(C)$.

As explained in the beginning of Section 6, it remains to give such a bound
for the configuration $E$ constructed from $C$ in Section 5.2 and for mixing
sequences with precision $0$ (that is, with only integral concentrations).
Recall that in Section 6.2 we gave a polynomial bound if $E$ is near-final. In
Section 6.3 we gave a bound for arbitrary configurations $E$ that is
exponential only in $n$, thus yielding a polynomial bound for constant $n$. We
will be using these properties in our construction in this section. If $E$ is
not near-final and $n$ is arbitrary, the general idea for achieving a
polynomial bound is similar to that from Sections 6.2 and 6.3: we try to mix a
pair of concentrations that are far apart, to guarantee that we make a quick
progress, as measured by the decrease of ${\Psi}(E)$. (This is captured by
Observation 5, that will be used frequently and without explicit reference.)
Although this is not posible in each step, we (essentially) show that for any
$E$ there is a polynomial-length sequence of mix operations after which such a
far-apart pair will exist, yielding an overall polynomial bound on a perfect-
mixing sequence. Additionally, to obtain such a perfect-mixing sequence, at
each step we must mix pairs that are either $(\lambda)$-safe, for
corresponding $\lambda\in{\left\\{I,I^{\prime}\right\\}}$, or near-final.

In this section, for better clarity, we chose to use a top-down presentation
style, starting with the statement of the main theorem (Theorem 6.17 below)
and its proof, while all the necessary lemmas that cover different cases from
that proof are presented later. Also, throughout this section, $\gamma$
denotes a small integral constant; for concreteness we can assume that
$\gamma=2$.

######  Theorem 6.17.

$E$ can be perfectly mixed with precision $0$ in a polynomial number of mixing
operations.

######  Proof 6.18.

If $n=4$ (and, more generally, if $n$ is a power of $2$), we can simply use
Theorem 6.9 and we are done. Thus, we can assume that $n\geq 5$. If $n<22$, we
can perfectly mix $E$ using Theorem 6.15, where the bound on the length of the
mixing sequence is polynomial if $n$ is constant. Thus in the rest of the
argument below we assume that $n\geq 22$.

We show that as long as $E$ satisfies Invariant (I) (which is the invariant
that applies when $n\geq 22$), we can find a polynomial-length sequence of
mixing operations that will decrease ${\Psi}(E)$ by a factor of
$1-\Omega(1/n)$. This will be sufficient to prove the theorem.

So assume that $E$ is not yet perfectly mixed and let
$\delta={\textsf{diam}}(E)$. Let $\pi$ be the parity for which
${|E_{\pi}|}\geq{|E_{{\bar{\pi}}}|}$. (Recall that we say that $A\subseteq E$
is (I)-mixed if there is no (I)-safe pair in $A$, that is, there no pair of
distinct concentrations in $A$ whose mixing preserves Invariant (I) for $E$.
We will often use this terminology when mixing pairs of concentrations in
$E_{\pi},E_{\bar{\pi}}\subseteq E$.) We consider several cases.

Case 1: ${\|E_{\pi}\|}=1$. Let $a\in E_{\pi}$ (that is, $a$ is the only
concentration in $E_{\pi}$). Observe that $E_{{\bar{\pi}}}\neq\emptyset$. We
have two sub-cases:

:

Case 1.1: $\min(E_{\bar{\pi}})<a<\max(E_{\bar{\pi}})$. In this case, per Lemma
6.21, there are at most two consecutive mixing operations (involving either
(I)-safe or near-final pairs) after which ${\Psi}(E)$ decreases at least by a
factor of $1-1/32n$.

:

Case 1.2: $a<\min(E_{\bar{\pi}})$ or $a>\max(E_{\bar{\pi}})$. In this case,
per Lemma 6.23, there is a sequence of at most $128ns(E)+1$ (I)-safe mixing
operations after which ${\Psi}(E)$ decreases at least by a factor of
$1-1/32\gamma^{2}n$.

Case 2: ${\|E_{\pi}\|}\geq 2$ and ${\textsf{diam}}(E_{\pi})\geq\delta/\gamma$.
In this case, per Lemma 6.25, there is an (I)-safe pair in $E_{\pi}$ whose
mixing decreases ${\Psi}(E)$ at least by a factor of $1-1/8\gamma^{2}n$.

Case 3: ${\|E_{\pi}\|}\geq 2$ and ${\textsf{diam}}(E_{\pi})<\delta/\gamma$.
Using Lemma 6.27, there is a sequence of at most $128ns(E)$ (I)-safe mixing
operations in $E_{\pi}$, such that after this sequence $E_{\pi}$ is (I)-mixed.
Let $E^{\prime}$ be the configuration obtained from $E$ after applying this
sequence. We consider two sub-cases:

:

Case 3.1: ${|E^{\prime}_{\pi}|}\geq{|E^{\prime}_{\bar{\pi}}|}$. By Observation
9 below and since $E^{\prime}_{\pi}$ is (I)-mixed, we have that
${\|E^{\prime}_{\pi}\|}=1$. Hence, as in Case $1$ above, there is a sequence
of at most $128ns(E^{\prime})+1$ mixing operations (involving either (I)-safe
or near-final pairs) after which ${\Psi}(E^{\prime})$ decreases at least by a
factor of $1-1/32\gamma^{2}n$. Thus, ${\Psi}(E)$ also decreases at least by a
factor of $1-1/32\gamma^{2}n$.

:

Case 3.2: ${|E^{\prime}_{\pi}|}<{|E^{\prime}_{\bar{\pi}}|}$. As $\gamma=2$,
${\textsf{diam}}(E^{\prime}_{\pi})<\delta/\gamma$, and because the mixing
operations on $E_{\pi}$ produced at least one droplet with parity $\bar{\pi}$,
we have that ${\textsf{diam}}(E^{\prime}_{\bar{\pi}})>\delta/\gamma$. Hence,
as in Case $2$ above, there is an (I)-safe pair whose mixing decreases
${\Psi}(E^{\prime})$ at least by a factor of $1-1/8\gamma^{2}n$. Thus, such
mixing also decreases ${\Psi}(E)$ at least by a factor of $1-1/8\gamma^{2}n$.

Applying a sequence of mixing operations specified by the cases above results
in a decrease of ${\Psi}(E)$ at least by a factor of $1-1/32\gamma^{2}n$.
Thus, by a simple extension to Observation 6, we obtain that after at most
$32\gamma^{2}n$ such mixing sequences ${\Psi}(E)$ decreases at least by half.
It follows that after at most $32\gamma^{2}n\log{\Psi}(E)$ of these mixing
sequences (where ${\Psi}(E)$ denotes the initial potential value), $E$ becomes
(I)-mixed, and, as $E$ satisfies Invariant (I), there is a near-final pair in
$E$ that we then mix to make $E$ near-final. Since $\log{\Psi}(E)\leq 2s(E)$,
the length of this sequence is at most $64\gamma^{2}ns(E)$ (where $s(E)$
represents the original size of $E$). Each such mixing sequence involves at
most $256ns(E)+1$ mixing operations and, by Theorem 6.11, if $E$ is near-final
then it can be perfectly mixed by a sequence of at most $144n^{3}s^{2}(E)$
mixing operations. Therefore the total number of mixing operations to
perfectly mix $E$ is at most
$2^{14}\gamma^{2}n^{2}s^{2}(E)+64\gamma^{2}ns(E)+144n^{3}s^{2}(E)$.

######  Observation 9.

Assume that $E$ with ${|E|}=n\geq 22$ satisfies Invariant (I) and let $\pi$ be
the parity for which ${|E_{\pi}|}\geq{|E_{\bar{\pi}}|}$. There is at least one
droplet in $E_{\pi}$ such that, when paired with any other droplet in
$E_{\pi}$, the resulting pair is (I)-safe.

######  Proof 6.19.

Lemma 5.5(a) and the number of distinct odd prime factors of $n$ being less
than $\log_{3}{n}$ imply that $E$ has at most $2\lfloor\log_{3}{n}\rfloor$
droplets that are ${\bar{p}}$-unsafe when paired with other droplets in $E$.
This, and Observation 10 below give that the number of droplets that, when
mixed with other droplets in $E$ violate Invariant (I), is at most
$2\lfloor\log_{3}{n}\rfloor+6<n/2\leq{|E_{\pi}|}$, since $n\geq 22$. Thus, the
lemma holds.

######  Observation 10.

Assume that $E$ with ${|E|}=n\geq 7$ satisfies Invariant (I). The number of
droplets involved in mixing operations that decrease the number of non-
singletons in $E$ down to one is at most $6$.

######  Proof 6.20.

First of all, if the number of non-singletons in $E$ is more than three, then
no mixing decreases the number of non-singletons down to one; similarly when
mixing a non-singleton with frequency higher than two. Additionally, mixing
two singletons does not decrease the number of non-singletons. Now, $E$
satisfying Invariant (I) implies that there are at least two non-singletons
$a,b\in E$. We consider two types of situations where a mixing decreases the
number of non-singletons in $E$ down to one:

Case 1: Mixing two non-singletons, say $a$ and $b$. This can happen when the
frequency of both $a$ and $b$ is two each, leading to a total of $4$ droplets
involved. (There could be another non-singleton
$e={\textstyle\frac{1}{2}}(a+b)$ in $E$, however no mixing involving $e$ would
decrease the number of non-singletons down to one because either $a$ or $b$
would remain non-singleton after the mixing.)

Case 2: Mixing a non-singleton with a singleton. (This can happen when $E$ has
exactly two non-singletons, $a$ and $b$ respectively.) Let $a$ and $c$ be the
non-singleton and singleton, respectively. If $a$ is a doubleton and
$b={\textstyle\frac{1}{2}}(a+c)$, then mixing $a$ and $c$ decreases the number
of non-singletons down to one. Similarly, if $b$ is a doubleton and
$a={\textstyle\frac{1}{2}}(b+d)$, for some singleton $d\in E$, then mixing $b$
and $d$ decreases the number of non-singletons down to one. Therefore, the
total number of droplets (excluding $a$ and $b$, which were already counted in
Case $1$ above) is at most $2$.

Therefore, the number of droplets involved in mixing operations that decrease
the number of non-singletons down to one is at most $6$.

######  Lemma 6.21.

Assume that $E$ with ${|E|}=n\geq 7$ satisfies Invariant (I). Also, assume
that ${|E_{\pi}|}\geq{|E_{\bar{\pi}}|}\geq 1$ and that ${\|E_{\pi}\|}=1$, with
$a\in E_{\pi}$. If $\min(E_{\bar{\pi}})<a<\max(E_{\bar{\pi}})$ then there
exist at most two consecutive mixing operations (involving either (I)-safe or
near-final pairs) that decrease ${\Psi}(E)$ at least by a factor of $1-1/32n$.

######  Proof 6.22.

Let $\delta={\textsf{diam}}(E)$ before any mixing operation. Assume without
loss of generality that $\pi=even$. Since $E$ satisfies Invariant (I), there
is at least one non-singleton $b\in E_{odd}$. Either $\min(E_{odd})$ or
$\max(E_{odd})$ is furthest from $b$, so assume without loss of generality
that $\min(E_{odd})$ is furthest from $b$; $|b-\min(E_{odd})|\geq\delta/2$. If
pair $(b,\min(E_{odd}))$ is (I)-safe, then we are done. So, assume otherwise,
namely that pair $(b,\min(E_{odd}))$ is not (I)-safe;
$a={\textstyle\frac{1}{2}}(b+\min(E_{odd}))$ and $b$ (which is a doubleton)
are non-singletons in $E$. (There could be at most one more non-singleton in
$E$, namely $\min(E_{odd})$ strictly doubleton; otherwise $(b,\min(E_{odd}))$
would be in fact (I)-safe.) Consider the following cases:

Case 1: $b=\max(E_{odd})$. We further consider the following two sub-cases
based on the number of distinct concentrations in $E$:

:

Case 1.1: ${\|E\|}=3$. Then
$E={\left\\{{|E_{odd}|}-2:\min(E_{odd}),{|E_{even}|}:a,2:b\right\\}}$, with
${|E_{odd}|}\leq 4$. If ${|E_{odd}|}=3$, then $\min(E_{odd})$ is a singleton,
and, after the mixing, ${\|E\|}=2$ holds, which implies that $E$ is now near-
final, by Lemma 5.3 and thus $(b,\min(E_{odd}))$ is actually a near-final
pair. Otherwise, ${|E_{odd}|}=4$ and $\min(E_{odd})$ is a doubleton. This
trivially implies that after (and before) the mixing $E$ is near-final, so
$(b,\min(E_{odd}))$ is a near-final pair. (Recall that
$|b-\min(E_{odd})|\geq\delta/2$, so the lemma holds by Observation 5.)

:

Case 1.2: ${\|E\|}\geq 4$. This implies that there is $c\in E_{odd}$ such that
$\min(E_{odd})<c<b$; mixing $b$ and $c$ produces a non-singleton other than
$a$, which preserves Invariant (I), so $(b,c)$ is (I)-safe. We analyze the
following sub-cases:

:

Case 1.2.1: $c<a$. Since $|b-c|\geq\delta/2$, mixing $b$ and $c$ decreases
${\Psi}(E)$ at least by a factor of $1-1/8n$, so we mix them.

:

Case 1.2.2: $c>a$. Let $d={\textstyle\frac{1}{2}}(b+c)$ be the output of the
mixing between $b$ and $c$. If $d$ is odd, then mixing $d$ and $\min(E_{odd})$
decreases ${\Psi}(E)$ at least by a factor of $1-1/8n$. (Pair
$(d,\min(E_{odd}))$ is (I)-safe because its mixing produces a non-singleton
other than $a$.) Otherwise, $d$ is even and, as $|d-a|\geq\delta/4$, mixing
$a$ and $d$ decreases ${\Psi}(E)$ at least by a factor of $1-1/32n$. (Note
that $(a,d)$ is (I)-safe because, after its mixing, $a$ remains non-
singleton.)

Case 2: $b<\max(E_{odd})$. This is similar to Case $1.2.2$ above under the
assumption that $b<\max(E_{odd})$ and using $c=\max(E_{odd})$.

######  Lemma 6.23.

Assume that $E$ with ${|E|}=n\geq 7$ satisfies Invariant (I). Also, assume
that ${|E_{\pi}|}\geq{|E_{\bar{\pi}}|}\geq 1$ and that ${\|E_{\pi}\|}=1$ with
$a\in E_{\pi}$. If either $a<\min(E_{\bar{\pi}})$ or $a>\max(E_{\bar{\pi}})$,
then there exists a mixing sequence (of (I)-safe pairs) of length at most
$128ns(E)+1$ that decreases ${\Psi}(E)$ at least by a factor of
$1-1/32\gamma^{2}n$, for constant $\gamma\in{\mathbb{Z}_{>0}}$.

######  Proof 6.24.

Let $\delta={\textsf{diam}}(E)$ before any mixing operation. Assume without
loss of generality that $\pi=even$ and that $a<\min(E_{odd})$. We analyze two
sub-cases:

Case 1: ${\textsf{diam}}(E_{odd})\geq\delta/2\gamma$. $E$ satisfying Invariant
(I) implies that there is a non-singleton $b\in E_{odd}$. Either
$\min(E_{odd})$ or $\max(E_{odd})$ is furthest from $b$, so assume without
loss of generality that $\min(E_{odd})$ is furthest from $b$. As
$a<{\textstyle\frac{1}{2}}(b+\min(E_{odd}))$, pair $(b,\min(E_{odd}))$ is
(I)-safe (mixing $b$ and $\min(E_{odd})$ produces a non-singleton other than
$a$) that satisfies $|b-\min(E_{odd})|\geq\delta/4\gamma$. Therefore, mixing
$b$ and $\min(E_{odd})$ decreases ${\Psi}(E)$ at least by a factor of
$1-1/32\gamma^{2}n$.

Case 2: ${\textsf{diam}}(E_{odd})<\delta/2\gamma$. This implies that
$|\min(E_{odd})-a|\geq\delta/2\gamma$. (I)-mix $E_{odd}$ using Lemma 6.27; $E$
satisfying Invariant (I) (and our proof in Section 5.2) implies that an even
concentration $b$ is eventually produced. Since $a$’s frequency is at least
$\lceil n/2\rceil\geq 3$, pair $(a,b)$ is (I)-safe; $a$ remains non-singleton
after the mixing. Additionally, since $b>\min(E_{odd})$,
$|b-a|>\delta/2\gamma$ and thus mixing $a$ and $b$ decreases ${\Psi}(E)$ at
least by a factor of $1-1/8\gamma^{2}n$. Finally, Lemma 6.27 takes at most
$128ns(E)$ mixing operations, so the lemma holds.

######  Lemma 6.25.

Assume that $E$ with ${|E|}=n\geq 22$ satisfies Invariant $(I)$. Also, assume
that ${|E_{\pi}|}\geq{|E_{\bar{\pi}}|}$ and that ${\|E_{\pi}\|}\geq 2$. If
${\textsf{diam}}(E_{\pi})\geq{\textsf{diam}}(E)/\gamma$, for constant
$\gamma\in{\mathbb{Z}_{>0}}$, then there exists an (I)-safe pair whose mixing
decreases ${\Psi}(E)$ at least by a factor of $1-1/8\gamma^{2}n$.

######  Proof 6.26.

Assume without loss of generality that $\pi=even$ and let $a=\min(E_{even})$
and $b=\max(E_{even})$. Mixing $a$ and $b$ decreases ${\Psi}(E)$ at least by a
factor of $1-1/2\gamma^{2}n$. So, if $(a,b)$ is (I)-safe then we are done.
Instead, assume otherwise; namely, that $(a,b)$ is not (I)-safe.

The above assumption, and Observation 9, imply that there is $c\in E_{even}$
with $c\notin{\left\\{a,b\right\\}}$ for which any pair involving $c$ is
(I)-safe. Now, either $a$ or $b$ is furthest from $c$, so assume without loss
of generality that $a$ is furthest from $c$. Then,
$|c-a|\geq{\textsf{diam}}(E)/2\gamma$ and thus mixing $a$ and $c$ decreases
${\Psi}(E)$ at least by a factor of $1-1/8\gamma^{2}n$.

######  Lemma 6.27.

Assume that $E$ with ${|E|}=n\geq 7$ satisfies Invariant $(I)$. Then, there
exists a mixing sequence (of (I)-safe pairs) of length at most $128ns(E)$ that
(I)-mixes $E_{\pi}$.

######  Proof 6.28.

Assume without loss of generality that $\pi=even$ and let
${|E_{even}|}=n^{\prime}$ and $\delta={\textsf{diam}}(E_{even})$ before any
mixing operation. If a mixing in $E_{even}$ produces droplets with an odd
concentration, then these droplets are excluded from $E_{even}$ and included
in $E_{odd}$; this can happen at most $n^{\prime}/2$ times before $E_{even}$
becomes (I)-mixed.

Assume that the number of (I)-safe pairs in $E_{even}$ is non-zero and let
$a=\min(E_{even})$ and $b=\max(E_{even})$. If an (I)-safe pair $x,y\in
E_{even}$ satisfies $|x-y|\geq\delta/4$, then mixing $x$ and $y$ decreases
${\Psi}(E_{even})$ at least by a factor of $1-1/32n^{\prime}$. It follows from
Observation 6 that after at most $32n^{\prime}$ such mixing operations,
${\Psi}(E_{even})$ decreases at least by a factor of
${\textstyle\frac{1}{2}}$. Hence, $E_{even}$ can be (I)-mixed after at most
$32n^{\prime}\log{{\Psi}(E_{even})}$ such mixing operations.

We next show that if $E_{even}$ has not been (I)-mixed, then after at most two
consecutive (I)-safe mixing operations either an odd concentration is produced
or ${\Psi}(E_{even})$ decreases at least by a factor of $1-1/32n^{\prime}$.
Consequently, after at most $128ns(E)$ (I)-safe mixing operations, $E_{even}$
becomes (I)-mixed.

So, if $(a,b)$ is (I)-safe then we are done; $|a-b|=\delta$ and thus mixing
$a$ and $b$ decreases ${\Psi}(E)$ at least by a factor of $1-1/2n$. Instead,
assume that $(a,b)$ is not (I)-safe and consider the following cases:

Case 1: $E_{even}$ has only singletons. This implies that no mixing in
$E_{even}$ decreases the number of non-singletons in $E$. So, let $c,d\in
E_{even}$ be the furthest-apart (I)-safe pair and
$x={\textstyle\frac{1}{2}}(c+d)$ be the output of their mixing. If either
$|c-d|\geq\delta/2$ or $x$ odd holds, then we are done. Otherwise, let
$y\in{\left\\{a,b\right\\}}$ be furthest from $x$. By the choice of $y$, we
have that $|x-y|\geq\delta/2$, and as $x$ is a doubleton, $(x,y)$ is (I)-safe
and thus we mix it.

Case 2: $E_{even}$ has exactly one non-singleton $c$. Either $a$ or $b$ is
furthest from $c$, so assume without loss of generality that $b$ is furthest
from $c$; $|b-c|\geq\delta/2$. If $(b,c)$ is (I)-safe then we mix it and we
are done. Otherwise, $(b,c)$ is not (I)-safe, therefore there are exactly two
non-singletons in $E$, $c\in E_{even}$ (which is a doubleton) and
$e=(b+c)/2\notin E_{even}$. Since there is an (I)-safe pair in $E_{even}$,
there is some $d\in E_{even}$ such that $d\notin{\left\\{b,c\right\\}}$. Then,
$(c,d)$ is (I)-safe because mixing $c$ and $d$ produces a non-singleton
$x={\textstyle\frac{1}{2}}(c+d)$ other than $e$. So, mix $c$ and $d$. If
$|c-d|\geq\delta/2$ then we are done; similarly if $x$ is odd. Otherwise,
$(b,x)$ is (I)-safe ($e\neq{\textstyle\frac{1}{2}}(b+x)$) and
$|x-b|\geq\delta/4$, so we mix it.

Case 3: $E_{even}$ has at least two non-singletons $c<d$. We analyze two sub-
cases:

:

Case 3.1: $a=c$. Since $(a,b)$ is not (I)-safe, then mixing $b$ and $c$
decreases the number of non-singletons down to one. This gives us two sub-
cases:

:

Case 3.1.1: $d=b$. $E_{even}$ having an (I)-safe pair implies that there is
some $x\in E_{even}$ such that $x\notin{\left\\{c,d\right\\}}$. Either $c$ or
$d$ is furthest from $x$, so assume without loss of generality that $d$ is
furthest from $x$; $|d-x|\geq\delta/2$. Mixing $x$ and $d$ produces a non-
singleton other than $c$, so $(x,d)$ is (I)-safe and we mix it.

:

Case 3.1.2: $d<b$. This implies that $d={\textstyle\frac{1}{2}}(c+b)$,
$b-d=\delta/2$ and $(b,d)$ is (I)-safe (mixing $b$ and $d$ produces a non-
singleton other than $c$), so we mix $b$ and $d$.

:

Case 3.2: $a<c$. If $|a-c|\geq\delta/2$ then we mix $a$ and $c$ and we are
done; ${\textstyle\frac{1}{2}}(a+c)<d$ implies that mixing $a$ and $c$
produces a non-singleton other than $d$, so $(a,c)$ is (I)-safe. Instead, let
$|a-c|<\delta/2$ which implies $|b-c|\geq\delta/2$. Now, if pair $(b,c)$ is
(I)-safe then we mix it and we are done, so also assume that $(b,c)$ is not
(I)-safe. (We cannot have $b=d$ because that would contradict $(a,b)$ not
being (I)-safe; $|a-c|<\delta/2$ implies $c<{\textstyle\frac{1}{2}}(a+b)$, so
mixing $a$ and $b$ would produce a non-singleton other than $c$.) Therefore,
as $(b,c)$ is not (I)-safe, we have that $d={\textstyle\frac{1}{2}}(b+c)$ and
mixing $b$ and $d$ produces a non-singleton other than $c$. Hence, $(b,d)$ is
(I)-safe satisfying $|b-d|\geq\delta/4$, and we mix it.

All the pairs mentioned above have difference at least $\delta/4$, so their
mixing decreases ${\Psi}(E_{even})$ at least by a factor of
$1-1/32n^{\prime}$.

##  7\. Polynomial running time

In this section we address Theorem 1.1(c), namely the claim that in polynomial
time we can test whether a given configuration $C$ is perfectly mixable and,
if so, we can compute a polynomial-size perfect-mixing graph for $C$ — also in
polynomial time.

Let $C$ be the input configuration. To test whether $C$ is perfectly mixable
we just need to test whether it satisfies Condition (MC). That this can be
done in polynomial time follows directly from Corollary 4.7 in Section 4. To
justify this, recall that the input size is $s(C)=\sum_{c\in C}\log(|c|+2)\geq
n$. Thus the factoring of $n$ can be computed in time polynomial in the input
size. As $n$ has at most $\log n$ distinct odd prime factors and each such
prime factor has at most $\log{c_{max}}$ powers that are no bigger than
$c_{max}$, the total number of $b$’s that need to be considered is at most
$\log{n}\log{c_{max}}$, which is polynomial in $s(C)$. Putting it all together
(see the pseudo-code in Algorithm 1), we obtain that testing perfect-
mixability can be indeed accomplished in polynomial time, thus proving the
first part of Theorem 1.1(c).

Algorithm 1 PerfectMixabilityTesting($C$)

1:$n\,{\leftarrow}\,{|C|}$

2:$\mu\,{\leftarrow}\,{\textsf{ave}}(C)$

3:$c_{max}\,{\leftarrow}\,$ maximum absolute concentration in $C$

4:$P\,{\leftarrow}\,$ powers of odd prime factors of $n$ that are at most
$c_{max}$

5:for all $p\in P$ do

6: if $C$ is $p$-congruent but $C\cup{\left\\{\mu\right\\}}$ is not then

7: return false

8: end if

9:end for

10:return true

Now, assume that $C$ is perfectly mixable. To prove the second part of Theorem
1.1(c), namely that a polynomial-size perfect-mixing graph for $C$ can be
constructed in polynomial time, the idea is to follow the construction from
the proof in Section 6 for Theorem 1.1(b). In this proof, at each step we
choose a mixing pair in $E_{\pi}\subseteq E$, for
$\pi\in{\left\\{even,odd\right\\}}$, that is $(\lambda)$-safe (for the
appropriate invariant $\lambda\in{\left\\{I,I^{\prime}\right\\}}$), and
sufficiently far apart (with respect to either the entire configuration or a
subset of the same), until $E$ becomes near-final. The former conditions can
be checked in polynomial time and there are only quadratically many pairs to
try.

The only remaining obstacle is that, the way the argument is presented above,
we would have verify at each step whether $E$ is near-final and, if it is, to
find its near-final partition. This is not possible in polynomial time (see
the remarks below). We now explain how to circumvent this problem. For $n<22$,
then this is simple, since $n$ is a constant, so we focus on the case when
$n\geq 22$. For our construction in Section 6.4, we can just continuously mix
$(\lambda)$-safe pairs until $E$ becomes $(\lambda)$-mixed. When this happens,
as $E$ satisfies Invariant ($\lambda$), it holds that there is a near-final
pair in $E$. Furthermore, as explained in Case 1.1 of the proof of Lemma 6.21,
this $E$ has the form
$E={\left\\{f_{1}:c_{1},f_{2}:c_{2},f_{3}:c_{3}\right\\}}$ with $f_{1}\leq 2$,
$f_{2}=2$ and ${\textstyle\frac{1}{2}}(c_{1}+c_{2})=c_{3}$, so $(c_{1},c_{2})$
is a near-final pair. In this case, computing the corresponding “near-final”
partition of $E$ in polynomial-time is easy: if $f_{1}=1$, then mixing
$(c_{1},c_{2})$ produces $E$ satisfying ${\|E\|}=2$ and the near-final
partition is given in Lemma 5.3. Else $f_{1}=2$ and the near-final partition
involves sets of the form ${\left\\{c_{1},c_{2}\right\\}}$ and
${\left\\{c_{3}\right\\}}$, where $c_{3}={\textsf{ave}}(E)$.

_Remarks._ The last two paragraphs bring up a question of whether checking the
near-final property can be done in polynomial time. While this is not
essential to our algorithm, we address it here for the sake of interested
readers.

Let ${|E|}=n$. Observe first that if $E$ is near-final then it has a near-
final partition where all sets in the partition have different cardinalities.
The reason is simple: if two sets have the same cardinality, we can merge them
into one set, retaining the average value and the property that all
cardinalities are powers of $2$. As a consequence of this, the cardinalities
of the sets in $E$’s partition are uniquely determined by $n$, namely these
are the powers of $2$ that appear in the binary representation of $n$. Let
$\omega={\textsf{sum}}(E)=n\cdot{\hat{\mu}}$ be the sum of all concentrations
in $E$, and let $k$ be some cardinality (a power of $2$) in this partition of
$E$. A subset $F\subseteq E$ of cardinality $k$ has
${\textsf{ave}}(F)={\hat{\mu}}$ if and only if ${\textsf{sum}}(F)=\omega k/n$.

The above properties lead to an ${\mathbb{NP}}$-completeness proof. The idea
is this. Consider a restricted variant of the problem where $n=3\cdot 2^{l}$,
for some $l$. Using the notation from the paragraph above, we need to
determine whether $E$ has a subset $F$ of cardinality $k=n/3$ and total sum
${\textsf{sum}}(F)=\omega/3$. This is a variant of the Partition problem that
can easily be shown to be ${\mathbb{NP}}$-complete. (Details are left to the
reader.)

##  8\. Final Comments

In this paper we gave a complete characterization of perfectly mixable sets,
as well as a polynomial-time algorithm that tests perfect mixability and, for
perfectly mixable sets, computes a polynomial-size perfect-mixing graph.

The computational complexity of MixReachability remains wide open, even for
the special case of MixProducibility, where the inputs consist of pure
reactant and buffer droplets. The only hardness result related to
MixReachability that we can prove is that its modified variant, where we ask
whether $T$ is reachable from $I$ via a graph with a fixed (constant) depth is
${\mathbb{NP}}$-hard (see Appendix B).

There are a number of other open questions about computing mixing graphs. For
the case when the target consists of just one droplet [17, 14, 7, 1], it is
not known whether minimizing waste can be done efficiently, nor even whether
the minimum-waste value is computable. Unsurprisingly, no complexity results
are known for other objective functions, like minimizing reactant usage or
minimizing the number of micro-mixers.

As another example, one can consider the problem of computing a mixing graph
that realizes a given linear mapping. More specifically, with each mixing
graph $G$ we can associate a linear mapping $L_{G}$ that maps the vector of
concentration values on its inputs to the vector of concentration values on
its outputs. In this problem, given a linear mapping $L$, we ask whether there
exists a mixing graph $G$ with $L_{G}=L$. An algorithm for this problem would
allow us to construct mixing graphs that can produce a collection of target
sets, by changing the buffer/reactant combinations on input.

## References

  * [1] Ting-Wei Chiang, Chia-Hung Liu, and Juinn-Dar Huang.  Graph-based optimal reactant minimization for sample preparation on digital microfluidic biochips.  In 2013 International Symposium on VLSI Design, Automation and Test (VLSI-DAT), pages 1–4. IEEE, 2013.
  * [2] Trung Anh Dinh, Shinji Yamashita, and Tsung-Yi Ho.  A network-flow-based optimal sample preparation algorithm for digital microfluidic biochips.  In 19th Asia and South Pacific Design Automation Conference (ASP-DAC), pages 225–230. IEEE, 2014.
  * [3] Shirit Einav, Doron Gerber, Paul D Bryson, Ella H Sklan, Menashe Elazar, Sebastian J Maerkl, Jeffrey S Glenn, and Stephen R Quake.  Discovery of a hepatitis C target and its pharmacological inhibitors by microfluidic affinity analysis.  Nature Biotechnology, 26(9):1019–1027, 2008.
  * [4] Erika Check Hayden.  The automated lab.  Nature News, 516(7529):131, 2014.
  * [5] Frank Hsieh, Hasmik Keshishian, and Craig Muir.  Automated high throughput multiple target screening of molecular libraries by microfluidic MALDI-TOF MS.  Journal of Biomolecular Screening, 3(3):189–198, 1998.
  * [6] Yi-Ling Hsieh, Tsung-Yi Ho, and Krishnendu Chakrabarty.  A reagent-saving mixing algorithm for preparing multiple-target biochemical samples using digital microfluidics.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 31(11):1656–1669, 2012.
  * [7] Juinn-Dar Huang, Chia-Hung Liu, and Ting-Wei Chiang.  Reactant minimization during sample preparation on digital microfluidic biochips using skewed mixing trees.  In Proceedings of the International Conference on Computer-Aided Design, pages 377–383. ACM, 2012.
  * [8] Juinn-Dar Huang, Chia-Hung Liu, and Huei-Shan Lin.  Reactant and waste minimization in multitarget sample preparation on digital microfluidic biochips.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 32(10):1484–1494, 2013.
  * [9] Choong Kim, Kangsun Lee, Jong Hyun Kim, Kyeong Sik Shin, Kyu-Jung Lee, Tae Song Kim, and Ji Yoon Kang.  A serial dilution microfluidic device using a ladder network generating logarithmic or linear concentrations.  Lab on a Chip, 8(3):473–479, 2008.