Abstract. Exact rational mixed-volume realizability is undecidable already for
forty-four compact convex bodies in three dimensions, even when every prescribed
coefficient is nonnegative. More precisely, rational membership in this fixed
coefficient locus is co-recursively enumerable complete. The reduction encodes
products of stochastic matrices in contractive systems of planar zonoids and forces
those systems from complete cubic volume polynomials. Every coefficient, including
repeated-index coefficients, is computed by finite rational matrix operations, while
the reverse implication allows arbitrary compact convex realizations. The same
construction gives a quadratic three-parameter section of the twelve-body locus
whose boundary contains infinitely many distinct planar pieces, providing an
explicit geometric obstruction to semialgebraicity.
1. Introduction
The volume polynomial of compact convex sets is
Let denote the set of its complete coefficient arrays, with all nonempty. Prescribing
these coefficients asks for one simultaneous realization of all the mixed volumes, including
those with repeated arguments. The Heine–Shephard problem seeks a characterization of
this locus. An algorithmic version asks whether a finite array of rational numbers can be
recognized as realizable.
Theorem 1.1.Rational membership in is co-recursively enumerable complete, also
when inputs are restricted to nonnegative coefficients. In particular, it is undecidable,
and there is no sound effective verifier accepting finite certificates for every realizable
rational input.
Here a set is co-recursively enumerable if an algorithm eventually recognizes every
input outside it. Completeness is under computable many-one reductions. Thus
nonrealizability has effective finite certificates, whereas no such complete system exists for
realizability. The theorem fixes both the ambient dimension and the number of
bodies; padding by points gives the same conclusion for every in dimension
three.
The geometric construction starts from a rational probabilistic automaton. Its
transition matrices act on states, while a second family of contracting planar maps assigns
a distinct direction to each finite word. The acceptance value of that word is recorded in
the length of an exposed edge of a convergent zonoid sum. The condition that every word
remain below a cutpoint is then equivalent to the existence of one Minkowski
summand.
To recover this infinite system from finitely many numbers, two ingredients are needed.
A small collection of reference segments calibrates oblique projections between two
coordinate planes, and equality in the planar Minkowski inequality forces the prescribed
images and recurrences. At the same time, the geometry of the word directions makes
every complete cubic coefficient rational and effectively computable. This exact summation
is what permits a reduction whose input consists solely of finitely many rational
coefficients.
The construction also retains real parameters. For fixed rational transition
data it gives a rational quadratic map such that realizability is equivalent to
A three-state example turns these inequalities into an intersection of halfspaces with
infinitely many distinct exposed boundary planes. It yields an explicit polynomial section
witnessing nonsemialgebraicity of over . The sharper three-body threshold is established
in [2]; the section here describes a different feature of the locus through the same encoding
that produces the algorithmic obstruction.
2. Encoding words by segment directions
Fix an alphabet with and rational row-stochastic matrices sharing a rational stationary
probability row . Thus for every . Let be a rational probability row, an output column,
and a rational cutpoint. For , write , including . The condition to be encoded is
Set
The geometric word vector and its tag are
The tags lie in and are distinct. They are finite base- expansions whose digits lie in , so
no expansion can be obtained from another by adding trailing zeros.
For , write . Define planar zonoids
The contribution of words of length is , so the sums converge in Hausdorff distance.
Every has positive area, since the nonparallel segments and occur with positive
coefficients. Stationarity makes the unweighted body recoverable from the state bodies.
With , the equality for every word gives
Put for . Splitting words by their first letter gives the state equations
Their contraction is the reason these bodies can later be forced from their projected
areas.
Lemma 2.1.System (4) has a unique tuple of compact convex solutions. If a tuple
satisfies the equations up to independent translations, it consists of translates of the
state bodies in (2).
Proof.Use Hausdorff distance induced by the planar infinity norm, and the maximum
distance on tuples. Since each is row-stochastic and , the right side of (4) has
Lipschitz constant . The contraction theorem gives uniqueness and existence, the
latter also supplied by (2).
If the equations contain translation errors , their effect on translation vectors is
the linear operator
Solve and translate the th body by . This removes all errors and reduces to the
unique exact solution. □
Let . The cutpoint condition can now be read from the lengths of exposed
faces.
Lemma 2.2.There is a compact convex set satisfying
Proof.If every deficit is nonnegative, the convergent sum satisfies (5).
For the converse, write for the exposed face of in direction . Absolute summability
identifies each sum in (2) with the compact image of the product of its segments.
A point lies in an exposed face exactly when every segment coordinate does, since
its support deficit is the sum of nonnegative coordinate deficits. Thus exposed faces
commute with these infinite sums.
At , only is perpendicular to ; every other generator contributes a point to the
exposed face. The faces of and therefore have lengths and , respectively. Taking
lengths of the parallel exposed faces in (5) gives
The bodies above contain infinitely many generators, but their mixed volumes can be
summed by finite rational operations. The only comparisons needed are signs of
affine expressions in word tags; no automaton acceptance inequality enters this
calculation.
A rational recognizable weight has the form , where the matrices and vectors are
rational and . Initial and terminal vectors may be signed. This includes all state weights in
(2), their finite rational linear combinations, and their prefix-filtered versions. For
example, the weight that equals when and zero otherwise is obtained by adding
an initial state whose first transition on enters the old representation. For the
state weights, that entering row is a coordinate row and preserves the norm
bound.
Lemma 3.1.For recognizable weights and rational , the sums
are rational and effectively computable. The same holds for one-word affine
absolute-value sums and for polynomial moments in of degree at most one in each
variable over any regular relation on pairs of words.
Proof.Read the words synchronously over , padding the shorter word by zeros and
using two flags to forbid letters after padding begins. This gives a unique encoding
for every pair, including the empty encoding for two empty words.
After clearing denominators, assume are integers. A finite automaton determines
the sign of the affine expression by tracking
The absolute contribution of every possible remaining tail, at this scale, is at most
. If or , the sign is settled and the state may be replaced by an absorbing positive
or negative state. Otherwise it is an integer in the finite interval . At termination its
sign is exactly the required sign, including zero.
To sum polynomial moments on a regular relation, tensor its deterministic finite
automaton with the recognizable weight matrices and the geometric matrices . For
each nonzero letter of the first word, use , and use the identity for padding; do the
same for the second word. The resulting finite rational transfer matrix has absolute
row sum at most
Its resolvent is therefore rational. Suitable initial and terminal vectors select the
factors and , since . The resolvent sums their product over the accepted encodings,
with its identity term including empty words. Split the affine absolute-value
expression into its nonnegative and negative sign languages, expand it, and apply
these moment sums. The one-word construction is identical with a smaller transfer
bound. □
For nonnegative weights, let . The usual zonotope area formula gives
Thus mixed areas, areas, and widths in rational directions are rational and
computable.
To obtain cubic volume polynomials, place these planar bodies in
using coordinates and , respectively. A tagged direction becomes in or in . Use the
reference segments with vectors
Proposition 3.2.The complete cubic volume polynomial of these reference
segments and any finite collection of the state zonoids and image zonoids , placed
in or , has effectively computable rational coefficients.
Proof.For a finite zonotope, volume is the sum of the absolute determinants
of unordered generator triples. Absolute convergence extends this formula to the
countable sums. With repeated body labels, use independent copies of the same
generating measure; the coefficient for multiplicity is the ordered determinant sum
with prescribed body labels, divided by .
All determinants reduce to the expressions
Three generators in one plane give zero; one planar generator and two reference
vectors give an affine function of one tag, and three references give a rational
determinant. In a three-word sum, the unused tag factors into an ordinary word-mass
sum. Lemma 3.1 therefore computes every case. Finally , so the image zonoids are
represented by the prefix-filtered weights already included in that lemma. □
4. Forcing the prescribed geometry
A volume polynomial records both dimension and projected area. The following
elementary facts explain how the reference segments turn those numerical records into
fixed geometric maps.
Lemma 4.1.If the total Minkowski sum of a tuple has interior, the degree of its
volume polynomial in the variable belonging to is .
Proof.Translate into its -dimensional direction space and let be the sum of the
other bodies. The projection of to has positive -volume. Each of its nonempty
fibers contributes a translate of to , so Fubini gives a lower bound . Boundedness
in coordinates adapted to gives an upper bound . The polynomial with all other
variables equal to one therefore has degree , and nonnegativity of mixed-volume
coefficients identifies this with the degree in the original polynomial. □
Lemma 4.2.Suppose the first three vectors of an ordered segment family form a
basis and the fourth has every basis coordinate nonzero. Their absolute three-by-three
minors determine the whole segment family up to a common linear transformation
of determinant modulus one and independent translations.
Proof.Normalize the first basis to the prescribed basis; its determinant modulus is
fixed by its triple coefficient. Single-replacement minors give the absolute coordinates
of every remaining vector. Coordinate reflections make the fourth vector equal to its
prescribed value . For another vector , the minors involving and one basis vector give
. Squaring determines from the known coordinate squares. Since every is nonzero,
these products determine all relative nonzero coordinate signs. Only an overall sign
remains, which does not change a centered segment. □
For , define . The determinant-one shear taking to gives the exact extrusion identity
They restrict to the identity on . On , the first is the coordinate identification and the
second is . Hence, with the fixed rational scalar ,
The final ingredient is the equality case of the planar Minkowski inequality [5]. If for
and , the two bodies are translates. Their areas and mixed area agree, so equality gives
positive homothety and the equal areas fix its ratio at one. This conclusion holds for
arbitrary compact convex planar sets.
Theorem 4.3.From the rational automaton data one can compute a complete
rational cubic coefficient array on
labels which is realizable by compact convex sets in if and only if (1) holds. For
fixed rational , the array is a rational polynomial map of degree at most two, and
the equivalence holds for all real probability rows and real .
Proof.Use the reference segments in (6), together with the canonical bodies
Proposition 3.2 computes their entire rational volume polynomial . Adjoin a variable ,
put , and make the formal substitutions
The resulting polynomial has variables, and its full coefficient vector is the target.
Since all affected lie in one plane, has total degree at most two in those variables; this
proves the polynomial degree bound in .
If (1) holds, Lemma 2.2 and (3) give an actual with
On the nonempty open cone of positive parameters satisfying , this identity makes the
substituted sum equal to the genuine Minkowski sum including . Their volume
polynomials agree on an open set and hence identically, proving realizability of every
prescribed coefficient.
For the reverse implication, suppose arbitrary compact convex bodies realize the target.
The coefficient on the first three reference variables is one, so the total sum has
interior. Every reference variable has degree exactly one, so Lemma 4.1 makes its
body a segment. Since has all three basis coordinates nonzero, it serves as the
fourth vector in Lemma 4.2, which normalizes all reference bodies to (6). The
coefficients of and with the segments are their -widths, and are zero; thus these
bodies can be translated into . The analogous coefficients of with put them in
.
Write . Read the coefficient of the reference segment in the polynomial of . In the
target it is
In the competing realization, (7) identifies it with . Planar Minkowski equality forces
Next form the actual body in
In the canonical tuple the recurrence (4) makes it , under the planar identification. The
coefficient of in the polynomial of is consequently . In the competing realization, (7) and
Minkowski equality make a translate of the planar shape of . Together with (9), these are
precisely the contractive equations (4), up to translation. Lemma 2.1 fixes every to its
canonical , up to translation.
Finally, in put and . Both are actual convex bodies. On the parameters of ,
substitution (8) cancels the coefficients and leaves for the state bodies. Extrusion along
and (3) therefore give
Minkowski equality makes translates, and the forced state shapes identify with .
Lemma 2.2 now forces (1). The argument uses only nonnegativity and unit sum of , and ,
proving the assertion for real parameters as well. □
An arbitrary automaton acquires a common stationary row by adjoining a
zero-output absorbing state. Replace the transition matrices, output and initial row by
The acceptance values are unchanged, while the first coordinate row is stationary for
every . The same construction therefore encodes arbitrary rational automata with
labels.
5. The algorithmic obstruction
Strict cutpoint emptiness asks whether some finite word satisfies . Rote [4, Theorem 1(a)]
proves this problem undecidable for automata with four positive rational doubly
stochastic transition matrices, a rational initial distribution, output and cutpoint .
The uniform probability row is stationary, so these automata fall directly within
Theorem 4.3. The complement of strict cutpoint emptiness is the universal property
(1).
These automata already encode arbitrary Turing-machine halting. Neary [3, Lemma 9
and Theorem 11] maps an arbitrary Turing-machine halting instance to a binary tag
system, and then to a five-pair Post correspondence instance, preserving existence of a
halting computation. Rote’s construction in Sections 2.8–2.9 transforms those instances
into the four-letter seven-state automata, preserving existence of a word above the
cutpoint. The end-pair argument is supplied in Rote’s correction in Section 2.8. Therefore
the universal cutpoint property is co-recursively enumerable complete for this fixed size.
Its complement is directly enumerable by testing finite words with exact rational
arithmetic.
Proof of Theorem 1.1. Apply Theorem 4.3 with . It gives
and a computable reduction from the universal cutpoint property to rational
membership in . Thus membership is co-recursively enumerable hard.
The upper bound follows from the finite rational-net criterion for volume
polynomials [2, Theorem 8.2]. For each fixed , that criterion gives an effective
sequence of finite rational tests, all satisfied exactly by realizable coefficient arrays,
such that every nonrealizable rational array fails a test. Running those tests
enumerates the complement. This proves completeness.
To restrict the inputs to nonnegative coefficients, inspect the generated array. If
an entry is negative, the source condition cannot hold, by the forward implication
of Theorem 4.3. Replace that output by the nonnegative polynomial , padded by
zero coefficients. It is not realizable, since Brunn–Minkowski forces the sum of
two volume-one bodies in to have volume at least eight, whereas this polynomial
takes value two at . The modified reduction preserves the equivalence and has only
nonnegative outputs.
A sound complete finite-certificate verifier for realizability would enumerate the
realizable rational arrays. Together with the enumeration of nonrealizability, it would
decide membership, contrary to the reduction. Equivalently, on a constructed array
one could search for a certificate while enumerating violating words; one of the two
searches would always terminate. □
The dependence on input coefficients can be confined to a fixed quadratic
family.
Corollary 5.1.There is a rational quadratic map from the probability simplex in to the coefficient space of for which rational membership of the image is undecidable.
Proof.Use Rote’s two fixed matrices, fixed output and cutpoint [4, Theorem 1(d)].
Only the initial distribution varies. The construction in Sections 3.3–3.4 of [4]
makes both row and column sums one, so the uniform probability row is stationary.
Theorem 4.3 gives , with the fixed quadratic dependence on the initial distribution.
□
6. An explicit section with infinitely many boundary planes
The parameter form of the encoding also gives a concrete geometric obstruction over the
real numbers. Take one letter and three states, so and , and fix
Since is symmetric, its uniform probability row is stationary and
The encoding therefore has twelve labels, with membership condition for every
.
Theorem 6.1.A rational quadratic three-parameter section of is, near an interior
parameter point, the cone
Its boundary has a relatively open piece in every plane . Consequently is not
semialgebraic over .
Proof.The vectors , and are eigenvectors of with eigenvalues . Hence
On the affine parameter space , use coordinates
Their inverse is
A sufficiently small ball about the origin lies entirely in the domain , .
Theorem 4.3 identifies the preimage of on this ball with .
Put and . For sufficiently small , the point
lies in . The th defining expression of (10) takes value there. It vanishes for and
is at most for every . Since all coefficient vectors have norm at most , a relatively
open neighborhood of in preserves every other inequality strictly. Each such point
is on the boundary, as a small displacement across changes membership.
If were semialgebraic, its boundary would lie in the union of the zero sets of finitely
many nonzero defining polynomials. Their product would vanish on a relatively open
subset of every , hence on every entire plane . Every distinct linear form would divide
that nonzero product, which is impossible. Polynomial preimages of semialgebraic
sets are semialgebraic, so the encoding map proves the final assertion. □
Padding by points carries this explicit section into every with . The example gives a
direct negative answer to the semialgebraicity question of Averkov, Borger and
Soprunov [1] in these dimensions. On the relatively open boundary piece in , the
deficit for the word of length vanishes while all other deficits remain positive.
That plane therefore records the disappearance of the corresponding exposed
edge of the summand . The undecidability theorem shows that exact rational
feasibility of the word inequalities cannot be replaced by a terminating recognition
procedure.
References
[1]
Gennadiy Averkov, Christopher Borger and Ivan Soprunov, Inequalities between mixed volumes
of convex bodies: volume bounds for the Minkowski sum, Mathematika 66 (2020), 1003–1027.
[2]
Caius Folkerts, Volume polynomials and the Heine–Shephard problem, manuscript, 2026.
[3]
Turlough Neary, Undecidability in binary tag systems and the Post correspondence problem for
five pairs of words, in 32nd International Symposium on Theoretical Aspects of Computer Science,
Leibniz International Proceedings in Informatics 30 (2015), 649–661.
[4]
Günter Rote, Probabilistic finite automaton emptiness is undecidable for a fixed automaton,
in 50th International Symposium on Mathematical Foundations of Computer Science, Leibniz
International Proceedings in Informatics 345 (2025), 86.1–86.18.
[5]
Rolf Schneider, Convex Bodies: The Brunn–Minkowski Theory, second expanded edition,
Encyclopedia of Mathematics and its Applications 151, Cambridge University Press, 2014.