Many fair-division problems are guaranteed to have solutions by topological theorems. Splitting a necklace of mixed beads fairly among $p$ thieves is one example, and bisecting several measures at once is another. These guarantees usually come from a combinatorial "labelling lemma" on a triangulated space. The lemma says that if every vertex receives a label, and the labelling respects a symmetry of the space exactly, then some small simplex carries a complete, complementary set of labels. The prime-cyclic version is the $\mathbb{Z}_p$-Star-Tucker Lemma. It underlies the result that $p$-thief necklace splitting belongs to PPA-$p$, the class of total search problems whose solutions are guaranteed by counting modulo $p$. Real inputs never respect symmetry exactly: valuations are noisy, labels come from approximate oracles, and membership in a label is often a matter of degree. The existing lemma is silent on such inputs. It either applies fully or not at all.
This note proposes a graded version of the lemma. Labels become quantale-valued relations, meaning each vertex belongs to each label to some degree taken from an ordered algebra of truth values. That algebra, called a quantale, is a complete lattice with an associative "combine" operation that distributes over joins. Examples are $[0,\infty]$ with addition, which measures distances, and $[0,1]$ with a t-norm, which measures fuzzy truth. The central question is how the guarantee degrades when the symmetry holds only up to a defect $\delta$. The answer we expect is that it depends on the quantale's combine operation, and specifically on whether defects accumulate or saturate along a symmetry orbit. That dependence is what would make the quantale more than notation.
Core Claim
Let $K$ be a triangulated complex with a free $\mathbb{Z}_p$ action, as in Filos-Ratsikas, Hollender, Sotiraki, Zampetakis. Let the labelling be a $Q$-valued relation $\lambda(v,\ell)\in Q$ between vertices and labels, where the labels also carry a $\mathbb{Z}_p$ action. Define the equivariance defect as the worst-case failure of the symmetry condition, measured inside the quantale:
$$\delta \;=\; \bigvee_{v,\ell,g}\; d_Q\big(\lambda(g v, g\ell),\, \lambda(v,\ell)\big).$$
Here $d_Q$ is the quantale's internal distance, which for the Lawvere quantale $([0,\infty],\ge,+,0)$ is truncated subtraction, and $g$ ranges over $\mathbb{Z}_p$. The degree to which a simplex $\sigma$ is complementary is the tensor, over the vertices of $\sigma$, of their membership in the required labels.
We conjecture a graded lemma of the following form. There is always a simplex that is complementary to degree at least $\mathbf{1}\ominus\varphi_Q(\delta)$, where $\ominus$ is the quantale's residuation and $\varphi_Q$ is a loss function determined by the tensor.
The cases split by whether the tensor is idempotent. For idempotent quantales, such as the min/max (ultrametric or Gödel) structures, we expect $\varphi_Q(\delta)=\delta$ with no dependence on $p$. For the additive Lawvere quantale we expect $\varphi_Q(\delta)$ of order $p\,\delta$, because a defect composes once per step of the $p$-element orbit. We also aim for a matching lower-bound construction showing that this accumulation is unavoidable. The existing lemma is the case $\delta=0$ over the two-element quantale.
The new content is the non-idempotent case and the lower bound. Idempotent quantales admit a level-set reduction to the crisp lemma. We treat that reduction as a baseline and do not count it as a contribution.
Research Program
The first part is mathematical: stating and proving the graded lemma.
The idempotent case should follow by cutting $\lambda$ at a threshold. This yields crisp labellings, and the crisp lemma applies at each level. The additive case needs a different argument. We plan to revisit the modulo-$p$ counting proof of Filos-Ratsikas et al.. We will track how each non-equivariant vertex perturbs the count of complementary simplices, and bound that perturbation using the triangle inequality of the quantale.
Two prior results constrain which quantales are admissible. Zhang and Zhang show that lax extensions of filter monads to quantale-valued relations compose only when the continuous t-norm satisfies a condition (S). This warns us that some t-norms will break composition along orbits. Their companion work on Kleisli convolution provides the composition law we reuse. We expect an analogous algebraic condition to separate quantales where $\varphi_Q$ is linear in $\delta$ from those where it is worse, and pinning that condition down is a stated goal.
The second part is computational. We will define Graded-$\mathbb{Z}_p$-Star-Tucker as a search problem: given a circuit labelling and a threshold, output a sufficiently complementary simplex or a vertex whose defect exceeds the budget. We will then prove that this problem lies in PPA-$p$.
Solutions will be certified in the linear quantitative logic of Bacci, Mardare, Panangaden, and Plotkin. That logic interprets propositions over $[0,\infty]$ and decides consequence using Farkas-type duality. It gives a checkable certificate that a claimed simplex meets its degree bound, and that check stays in co-NP. The path-following and parity machinery comes from Deng et al. and Filos-Ratsikas and Goldberg.
We deliberately do not claim progress on the open problem of whether $p$-thief necklace splitting is PPA-$p$-hard. A graded lemma may later help reductions tolerate constant error, which is another open problem noted in that literature. That is speculation, and success of this project does not depend on it.
The third part is the application. We will apply the lemma to $p$-thief necklace splitting where bead colours are known only approximately, for example from misclassified or noisy counts. From the graded lemma we will derive how the discrepancy of the resulting split scales with input noise at a fixed number of cuts.
Baselines
The naive reference point is to ignore the defect: run the crisp $\mathbb{Z}_p$-Star-Tucker procedure on the thresholded labelling and report whatever simplex it returns. Its failure mode is that the returned simplex can have arbitrarily low true complementarity. The graded lemma must certify something this procedure cannot.
The strongest structural competitor is symmetrize-then-solve. This method keeps the labels on one fundamental domain of the $\mathbb{Z}_p$ action, extends them equivariantly, and applies the crisp lemma. It always produces an exact solution of a nearby problem, so it is the method a skeptic would reach for first.
We will run it on identical complexes, labellings and defect levels, with the same search procedure and no extra tuning. The comparison measures true complementarity under the original labelling. The proposal beats this baseline if its guaranteed degree $\varphi_Q(\delta)$ is provably and empirically better than the worst-case error symmetrization incurs along the seams of the fundamental domain. We predict symmetrization loses a factor that grows with the dimension of those seams.
For the necklace application, the strongest existing method is the offline multi-agent splitting of Alishahi et al.. It reports a bound of $n(k-1)[4+\log_2(3km)]$ proper cuts for $k$ agents, $n$ colours and $m$ beads under bounded discrepancy. We will compare discrepancy at an equal cut budget on the same noisy necklaces. Beating it means lower discrepancy under the true colours when the input colours are corrupted, at no more cuts.
The key ablation replaces the additive quantale with an idempotent one on the same instances. If the measured degradation does not change, then the tensor-dependence claim is false.
No empirical runtime or accuracy numbers for solving $\mathbb{Z}_p$-Star-Tucker instances were found on Lacuna. The cited work reports only PPA-$p$-completeness. We will therefore publish our own reference implementation and instance generator.
Why not just…?
Why not just use ordinary metric perturbation bounds on the real-valued labelling? For the Lawvere quantale, this is essentially what we do, and the quantale language would add nothing if that were the only case. The claim that justifies the abstraction is comparative. Different combine operations give provably different loss functions, and a single proof parametrised by the tensor explains why. The idempotent-versus-additive ablation tests this directly. If the two curves coincide, we will drop the general quantale and present a plain metric stability result.
Why not just symmetrize the labelling and apply the crisp lemma? This is the real threat. Symmetrization always returns a valid simplex, and for some complexes its seam error may already match $p\,\delta$. The proof must exhibit complexes where seam error is larger, or show the two are equivalent. Head-to-head experiments on high-dimensional complexes will settle the question in either direction, and a tie would be reported as a negative result.
Why not just threshold the graded labels and solve at each level? For idempotent quantales, this works and is our own proof of that case. It fails for additive quantales because the threshold sets of an additive combination do not compose. Showing where the level-set method gives a vacuous bound while the graded lemma does not is the decisive check for the non-idempotent contribution.
Why not just use practical solvers or heuristics? Divide-and-conquer allocation such as POP reports staying "within 1.5% of the optimal" on fungible resource problems, but it offers no existence guarantee. The query lower bound of Deligkas et al. is $\Theta((L/\epsilon)^{n-1})$ for general consensus-halving. This means black-box search cannot beat worst-case barriers. We include a local-search heuristic in the necklace experiments to measure the practical gap honestly.
Proposed Experiments
The first experiment tests the loss functions directly. We will generate triangulations of $\mathbb{Z}_p$-free complexes for $p\in\{3,5,7\}$ in dimensions 2 through 6. On these we will plant complementary simplices, then inject equivariance defects of controlled size $\delta$ under each of three quantales: Lawvere additive, product t-norm, and Gödel min. For every solver we will plot achieved complementarity against $\delta$.
The prediction is falsifiable in two ways. The Gödel curve should be flat in $p$. The Lawvere curve should grow roughly linearly in $p$ and should saturate the lower-bound construction on adversarial instances.
The second experiment uses noisy $p$-thief necklaces. We start from random necklaces with $n\le 20$ colours and flip bead colours with a given probability. We then compare discrepancy under the true colours for three methods at equal cut budgets: the graded-lemma solution, symmetrize-then-solve, and the Alishahi et al. offline construction.
The decisive checks are two. If symmetrization matches the graded lemma everywhere, the lemma's contribution reduces to certification alone. If the additive and idempotent curves coincide, the quantale dependence is not real. Either outcome would narrow the claim before any complexity result is written up.
References
- A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting
- Lax Extensions of Conical I-Semifilter Monads
- On Discrete Presheaf Monads
- Propositional Logics for the Lawvere Quantale
- Understanding PPA-Completeness
- The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
- Efficient Splitting of Necklaces
- Solving Large-Scale Granular Resource Allocation Problems Efficiently with POP
- Two's Company, Three's a Crowd: Consensus-Halving for a Constant Number of Agents