In 2012, Bournez, Fraigniaud, and Koegler proved a remarkable theorem: every algebraic number can be computed by a large-population protocol [1]. Their proof constructs an explicit polynomial ODE system whose equilibrium is the target algebraic number, then converts it into a population protocol. The result was a landmark — it showed that extremely simple molecular processes (pairwise interactions in a well-mixed solution) can compute any root of a polynomial.

But there is a gap in their construction. It is subtle, and it lives in the translation from ODE systems to chemical reaction networks. Understanding it requires only Vieta’s theorem and a careful look at what “CRN-implementable” really means.

The CRN-Implementability Constraint

A Chemical Reaction Network is a polynomial ODE system $x' = f(x)$ where each equation has the form

This is not just a convention. It is a structural constraint coming from chemistry: the positive term $p_i$ represents production of species $i$ by other species, while $q_i \cdot x_i$ represents degradation — you can only consume a species that is present. Both $p_i$ and $q_i$ must have non-negative coefficients to correspond to actual chemical reactions.

A population protocol is a more restricted CRN with conservation: $\sum x_i' = 0$. This means the total mass is preserved, as expected for a system of pairwise interactions ($X + Y \to W + Z$) where no molecules are created or destroyed.

The Conservation Trick

Given a polynomial $P(X) = a_0 + a_1 X + \cdots + a_n X^n$ with $P(\nu) = 0$, the construction in [1] builds an ODE system whose variables $x_1, \ldots, x_{n-1}$ track the polynomial evaluation, with

To make this conservative, they introduce a balancing variable

so that $\sum x_j + x_\delta = 1$ on the simplex. This is a natural move: define the leftover variable to absorb whatever the other variables produce or consume.

The problem: is this system CRN-implementable?

The Obstruction

Consider the simplest non-trivial case: a single variable with

Conservation gives

For CRN-implementability, we need to decompose this as $p_\delta(x) - q_\delta(x) \cdot x_\delta$ with $p_\delta \geq 0$ on $\mathbb{R}_{\geq 0}^2$.

The constant term $-\varepsilon a_0$ has no factor of $x_\delta$, so it must belong to $p_\delta$. At the origin $(x_1, x_\delta) = (0, 0)$:

If $a_0 > 0$, this is negative. No valid CRN decomposition exists.

The system lives on the simplex where $x_1 + x_\delta = 1$, and the dynamics are perfectly well-defined there. But CRN-implementability is a global polynomial condition on all of $\mathbb{R}_{\geq 0}^n$, not just on the simplex. The negative constant kills it at the origin.

How Vieta’s Theorem Generates Counterexamples

When does $a_0 > 0$? For a quadratic $P(X) = X^2 - qX + p$, Vieta’s theorem gives us the roots $a, b$ with $a + b = q$ and $ab = p$. The constant term is $a_0 = p = ab$.

For the construction to compute a number in $(0, 1)$, we need both roots in $(0, 1)$. The conditions are:

• Real roots: $q \geq 2\sqrt{p}$ (discriminant $\geq 0$)
• Both roots $< 1$: $(1-a)(1-b) = 1 - q + p > 0$, so $q < 1 + p$

The design space is the region $\{(p, q) : 0 < p < 1, \; 2\sqrt{p} \leq q < 1 + p\}$.

Every point in this region gives a quadratic ODE whose equilibrium is a number in $(0, 1)$, but whose conservation variable violates CRN-implementability — because $a_0 = p > 0$.

Some concrete examples:

The second row — $X^2 - X + 1/9$ — was constructed by Huang as a specific counterexample to demonstrate the issue [2]. It is nearly the simplest choice: $p = 1/9$ gives two irrational roots while keeping the arithmetic clean.

The Fix: Balancing Dilation

Instead of defining $\dot{x}_0 = -\sum \dot{x}_j$ (which creates the negative constant), one can multiply the conservation equation by $x_0$:

If the inner field is CRN-implementable — $f_j = p_j - q_j \cdot x_j$ with $p_j, q_j \geq 0$ — then the balanced system decomposes as:

Both terms are manifestly non-negative on $\mathbb{R}_{\geq 0}^n$: the production term is a product of non-negative factors, and the degradation coefficient is a sum of non-negative polynomials. CRN-implementability is preserved.

This construction, introduced as the “balancing dilation” (or $g$-trick) in [3], solves the problem at its root. It is not merely an alternative to taking $\dot{x}_\delta = -\sum \dot{x}_j$; it is a redesign that maintains CRN algebraic structure through the conservation step.

The price is modest: multiplication by $x_0$ introduces a time dilation (the dynamics slow down by a factor of $x_0(t)$), and the degree increases by one. But the algebraic structure — which is what makes a population protocol a population protocol — is intact.

Remarks

The result of Bournez, Fraigniaud, and Koegler [1] is correct: algebraic numbers are indeed LPP-computable. Their paper pioneered the connection between polynomial root-finding and population protocols, and their four-stage construction (rational base case, derandomization, equilibrium construction, stability analysis) provides the blueprint that subsequent work builds on. The gap in CRN-implementability affects the construction, not the conclusion.

The counterexample construction is elementary — Vieta’s theorem and the constraint $p > 0$ is all that is needed. But identifying what to test (CRN-implementability of the conservation variable, at the origin) requires understanding the precise algebraic constraints that chemistry imposes on ODE systems. This constraint is easy to overlook when thinking purely in terms of the balance equation on the simplex, where everything cancels nicely.

References

[1] O. Bournez, P. Fraigniaud, and X. Koegler. “Computing with Large Populations Using Interactions.” In Proc. 37th International Symposium on Mathematical Foundations of Computer Science (MFCS 2012), pp. 234–246, 2012. doi:10.1007/978-3-642-32589-2_23

[2] X. Huang and A. Migunov. “GPAC-to-PP Compiler (CF'24).” Manuscript, 2024. The example $x' = x^2 - x + 1/9$ was designed to expose the CRN-implementability gap.

[3] X. Huang and R. Huls. “Computing Real Numbers with Large-Population Protocols.” In Proc. 28th International Conference on DNA Computing and Molecular Programming (DNA 28), pp. 48–67, 2022. doi:10.1007/978-3-031-20624-5_4

知其然，知其所以然，知其所以必然。 — 朱熹

Know what is so; know why it is so; know why it must be so. — Zhu Xi