Paper deep dive
Bolzano: Case Studies in LLM-Assisted Mathematical Research
Jan Grebík, Pavel Hubáček, Martin Koutecký, Matěj Kripner, Václav Rozhoň, Robert Šámal, Adrián Zámečník
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 99%
Last extracted: 4/27/2026, 3:27:28 AM
Summary
The paper presents 'Bolzano', an open-source multi-agent LLM system designed to assist in mathematical research. The system utilizes a multi-agent architecture consisting of parallel prover agents and a verifier agent, maintaining a persistent knowledge base across research rounds. The authors demonstrate Bolzano's capability by documenting six case studies across complexity theory, additive combinatorics, cryptography, and data structures, where the system either autonomously produced results or collaborated with human experts to resolve significant mathematical problems.
Entities (7)
Relation Signals (4)
Bolzano → resolved → PWPP
confidence 100% · In one case, Bolzano autonomously provided a hardness proof and a polynomial-time algorithm for a restricted class... black-box PWPP is not closed under adaptive Turing reductions.
Bolzano → resolved → KZG
confidence 100% · Together with Bolzano, we resolved this gap [in univariate KZG batching].
Bolzano → uses → Prover Agent
confidence 100% · Bolzano orchestrates rounds of interaction between parallel prover agents and a verifier agent
Bolzano → uses → Verifier Agent
confidence 100% · Bolzano orchestrates rounds of interaction between parallel prover agents and a verifier agent
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We report new results on six problems in mathematics and theoretical computer science, produced with the assistance of Bolzano, an open-source multi-agent LLM system. Bolzano orchestrates rounds of interaction between parallel prover agents and a verifier agent while maintaining a persistent knowledge base that is carried across rounds. Classified using the significance-autonomy taxonomy of Feng et al., four of the six results reach the level of publishable research, and three of the six were produced essentially autonomously by Bolzano. Our results provide evidence that LLMs can contribute meaningfully to mathematical research, complementing recent reports by Bubeck et al., Woodruff et al., and others.
Tags
Links
- Source: https://arxiv.org/abs/2604.16989v1
- Canonical: https://arxiv.org/abs/2604.16989v1
Trouble viewing inline? Open PDF directly →
Full Text
78,246 characters extracted from source content.
Expand or collapse full text
Bolzano: Case Studies in LLM-Assisted Mathematical Research Jan Grebík1 Pavel Hubáček1,2 Martin Koutecký1 Matěj Kripner3 Václav Rozhoň1 Robert Šámal1 Adrián Zámečník1 1Computer Science Institute, Charles University 2Institute of Mathematics, Czech Academy of Sciences 3Institute of Formal and Applied Linguistics, Charles University Abstract We report new results on six problems in mathematics and theoretical computer science, produced with the assistance of Bolzano–an open-source multi-agent LLM system. Bolzano orchestrates rounds of interaction between parallel prover agents and a verifier agent while maintaining a persistent knowledge base that is carried across rounds. Classified using the significance–autonomy taxonomy of Feng et al. [F+26b], four of the six results reach the level of publishable research, and three of the six were produced essentially autonomously by Bolzano. Our results provide evidence that LLMs can contribute meaningfully to mathematical research, complementing recent reports by Bubeck et al. [BCE+25], Woodruff et al. [WCAJ+26], and others. 1 Introduction The integration of large language models into mathematical research has moved rapidly from speculation to documented practice. We highlight two recent reports that have established this as a real phenomenon (see Related Work for many more results in this direction): • Woodruff, Mirrokni et al. [WCAJ+26] present a collection of case studies in which Google’s Gemini Deep Think solved open problems across mathematics, theoretical computer science, and physics. • Bubeck et al. [BCE+25] document experiments in which OpenAI’s GPT-5 contributed to research in mathematics, physics, and computer science. This paper provides more evidence in this direction. Bolzano [Bol25b] is an open-source AI system that assists with mathematical research and is available to interested researchers. The system runs research on a problem using several rounds of interaction between several provers and a verifier. Each prover and verifier is implemented by state-of-the-art LLMs (GPT, Gemini, Claude, or others). Its architecture is described in Section 2. We use Bolzano to provide new results for six problems in mathematics and theoretical computer science. Strengths of Bolzano Across our case studies, Bolzano was most useful as a generator of mathematically meaningful intermediate research moves: it was particularly good at finding counterexamples and obstructions, proposing concrete constructions and gadgets, or extending a known base case or simpler proof template to a more general statement. This mirrors the findings in [WCAJ+26, BCE+25]. In one case, Bolzano autonomously provided a hardness proof and a polynomial-time algorithm for a restricted class, and corrected a small error in the human-provided problem formulation. Limitations This work has several limitations. First, we do not provide a thorough comparison between Bolzano and single-session chatbot interactions; while such a comparison is feasible in principle, it is difficult to carry out rigorously in a case study with six problems, and the advantage of the multi-agent architecture over direct use of the same underlying models remains unquantified. Second, it is hard to cleanly disentangle the human and AI contributions; even selecting the right problem to work on is a nontrivial human input. Solved problems We document six problems in mathematics and theoretical computer science that Bolzano has resolved or made progress on. This was done either autonomously or through collaboration with domain-expert mathematicians and computer scientists. For each of the problems, we include discussion. The corresponding formal results are proved either in the appendices of this paper or in separate papers. H (Primarily human) C (Collaboration) A (Autonomous) Negligible novelty Minor novelty Partitioning (Section 3.5) Tilings (Section 3.2) Publishable research Heaps (Section 3.4) PWPP (Section 3.1) KZG (Section 3.3) KKOS Optimization (Section 3.6) Major advance Landmark breakthrough Table 1: Classification of our results by significance and autonomy, following the taxonomy proposed by Feng et al. [F+26b]. to landmark breakthrough. Autonomy ranges from H (primarily human, secondary AI input) through C (human–AI collaboration) to A (essentially autonomous). 1. Complexity theory: We construct an oracle separation showing that PWPP is not closed under adaptive Turing reductions (Section 3.1). The human input was the question, and after Bolzano returned a proof, a human researcher suggested to keep the main structure (the same choice of problem showing that PWPP is not closed) but try a different strategy for the analysis, after which Bolzano essentially finished the proof. 2. Additive combinatorics: We provide an example of a tiling of ℝ2R^2 by a single tile that shows a limit on the technique from a forthcoming paper [dDGGM26] (Section 3.2). 3. Cryptography: We prove special soundness for multi-polynomial, multi-point KZG batching in the standard model (Section 3.3). The human researchers proposed a variant of the protocol and provided a simpler base-case proof as context. Bolzano found the full proof in six rounds, producing a lengthy but essentially complete formal argument. 4. Data structures: We prove that two beyond worst-case properties of heaps are equivalent (Section 3.4). This was first proven by a human researcher in a (yet unpublished) project. Bolzano independently reproved the equivalence and independently came up with a stronger statement and its proof. 5. Combinatorics: We disprove a conjecture on function-preimage partitioning from the KAMAK 2020 workshop [Krá20]. Moreover, Bolzano establishes a corrected hypothesis and proves some bounds for it (Section 3.5). 6. Computational complexity: We determine the complexity of an optimization problem over the KKOS cultural dynamics model [KKOS16] (Section 3.6). The decision version is NP-complete on general graphs; on forests, we give a polynomial-time algorithm. Bolzano worked autonomously, also correcting a small error in the original problem formulation. In general, our experience parallels the findings of [WCAJ+26] and [BCE+25] in several respects. LLMs excel at generating proof candidates, constructing counterexamples, and making cross-domain connections. In early 2026, human guidance remains relevant for problem selection, high-level strategy, and verification. Related work Recent work has begun to document the use of LLMs for mathematical and scientific research. GPT-5 has been shown to contribute to research in mathematics, physics, and other sciences, including solving open problems and improving constants [BCE+25]. Similar results have been reported with Gemini [WCAJ+26]. Aletheia [F+26b] is a mathematics research agent based on a Generator–Verifier–Reviser loop that autonomously solved research-level problems, including 6 out of 10 problems in the First Proof challenge [FJhK+26]. First Proof [ABH+26] is a benchmark of 10 research-level problems from unpublished work of 11 mathematicians; OpenAI [Ope26] reported at least 5 likely correct solutions. AlphaEvolve [N+25] has been applied to 67 problems [GGSTW25], mostly in constant optimization and construction search, with expert hints improving efficiency without clearly changing the ceiling of performance. FunSearch [RPBN+24] pairs an LLM with an evaluator in an evolutionary loop and has produced new results in combinatorics and algorithms. Many systems pursue automated theorem proving with formal verification. AlphaGeometry [TWL+24] solves olympiad geometry problems via a neuro-symbolic engine. Many recent systems target the Lean proof assistant, including AlphaProof [HMS+25], which achieves IMO medal-level performance via reinforcement learning; Hilbert [V+25], which combines informal proof sketches with formal verification; Aleph Prover [Log25], a formal theorem prover that leads PutnamBench; Ax-Prover [B+25], which targets quantum physics and abstract algebra; and autoformalization of a 130,000-line topology textbook at low cost [Urb26]. We view formal verification as complementary to our approach: Bolzano relies on informal proof generation followed by expert verification, which currently offers broader coverage but weaker guarantees. A large-scale evaluation of over 5,000 LLM-generated proofs across 1,000 problems [D+25] finds substantially stronger performance in informal than in formal proof generation. Multi-agent architectures for mathematical reasoning have been explored in several directions, including multiagent debate, step-level verification, iterative self-refinement, and LLM scaffolding for problem solving [DLT+23, G+25, HY25, MTG+23]. In late 2025, open Erdős problems emerged as a testing ground for LLM mathematical capabilities, with models producing original proofs of previously unsolved problems [PSV26, F+26a]; however, the problems solved so far are generally amenable to straightforward techniques [F+26a]. Roadmap Section 2 describes the architecture and design of Bolzano. Section 3 presents each of the solved problems, including the problem statement, context, a discussion of the human–AI collaboration, and a link to the Bolzano transcript. For problems whose proofs are not contained in a separate paper, the full proofs appear in the appendices. All proofs have been verified by domain experts. 2 Bolzano Bolzano is a research tool available at https://bolzano.app. It provides an automated pipeline consisting of prover, verifier, and summarizer agents designed to iteratively investigate mathematical research problems. Throughout this section, by agent we mean a callable function that makes a preconfigured request to an LLM with a custom prompt specifying a research persona, tasks, and goals. Overall architecture We call one iteration of the Bolzano pipeline a research round. It involves running n parallel prover agents, followed by one verifier agent, and concluded by a summarizer agent. Research rounds run sequentially; between rounds, the state of the investigation is preserved in three human-readable files. Agents. The prover agents are tasked with coming up with proof ideas, finding counterexamples, proving special cases, identifying mistakes, and writing proofs. The verifier agent checks the work of the provers—identifying errors and unjustified steps, combining ideas into viable solutions—and is the sole agent that decides what gets written into the knowledge base files. The summarizer agent produces a concise summary of each research round for the user and for subsequent agents. Knowledge base files. In between research rounds, we maintain three files that serve as a persistent knowledge base. The notes file aggregates insights, failed approaches, conjectures, and simplified proofs. The proofs file maintains rigorous, fully detailed proofs. The output file provides a short summary of the current status for the human researcher. All agents read from these files, but only the verifier can write to them. Model diversity. Bolzano allows the user to select a different LLM for each prover agent. Since models differ in training data, this seems to generate a wider variety of approaches. This approach is also reported to counteract self-preference bias [PBF24]. Human guidance. Between research rounds, the user may provide additional instructions to steer the investigation. In our experience, human guidance often leads to stronger results—for example, the PWPP result (Section 3.1) was obtained after an expert advised Bolzano to try a different strategy. 3 Solved Problems This section contains the six selected problems solved by Bolzano. For each problem, we add discussion about what parts of the research pipeline have been done by a human, and which parts by Bolzano. We always add a link to the Bolzano system containing the proof. However, Bolzano-generated proofs are not intended to be publication-ready. We thus always either add expert-verified proof to appropriate appendix, or link to a paper containing the proof. 3.1 Black-Box Separation of Adaptive and Non-Adaptive PWPP – Pavel Hubáček The complexity class PWPP (Polynomial Weak Pigeonhole Principle) [Jeř16] captures collision finding within TFNP. Its canonical complete problem Collision asks: given a shrinking circuit C:0,1n→0,1n−1C:\0,1\^n→\0,1\^n-1, find distinct x1,x2∈0,1nx_1,x_2∈\0,1\^n such that C(x1)=C(x2)C(x_1)=C(x_2). PWPP consists of all total search problems many-one reducible to Collision. Jeřábek [Jeř16] showed that PWPP is closed under non-adaptive Turing reductions, i.e. P∥PWPP=PWPPP^\|PWPP=PWPP: solving k independently prepared PWPP instances reduces to a single collision query. A basic structural question for TFNP subclasses is whether they remain closed under adaptive Turing reductions, where later oracle queries may depend on earlier answers [BJ12]. For several classes (e.g. PLS, PPA, PPAD) adaptive and non-adaptive oracle access coincide [BJ12], while for the related class P (Polynomial strong Pigeonhole Principle), Fleming et al. [FGPR24] proved a black-box separation showing it is not Turing-closed. Together with Bolzano, in [Hub26] we resolve the analogous question for PWPP in the black-box setting by introducing a natural adaptive task NestedCollision, suggested by Bolzano, which requires two dependent collision-finding steps. After being given the problem, Bolzano produced the core construction and proof in four rounds of interaction. While the initial proof had flaws, after being instructed to adopt a different high-level strategy,111Concretely: “Discard the case analysis strategy. Instead, prove that Π∉PWPP ∈ PWPP^O by establishing that, with overwhelming probability, the reduction circuit contains ”useless” collisions that do not reveal a solution to Π .” Bolzano delivered a mostly complete formal proof in four additional rounds, with only minor typographical errors and no significant logical gaps. Formal results. The theorem proven in [Hub26] is the following. Theorem 1 (Black-box PWPP is not Turing-closed [Hub26]). In the decision-tree model, the search problem NestedCollision admits no shallow Collision-formulation. Therefore, black-box PWPPPWPP is not closed under adaptive Turing reductions. The Bolzano research transcript is available at [Bol26d]. The complete proof appears in [Hub26]. 3.2 Structural Results on Multi-Slope Tilings – Jan Grebík Motivation and result The problem originated in the study of translational monotilings of ℝdR^d, or less generally ℤdZ^d, where the setup is the following. We are given a measurable set Ω⊆ℝd ^d of finite positive Lebesgue measure and want to understand if there is a (necessarily uniformly discrete) set of translates T⊆ℝdT ^d such that Ω⊕T=ℝd, T=R^d, where Ω⊕T T means that the collection of translates Ω+tt∈T\ +t\_t∈ T are disjoint up to null sets and cover all of ℝdR^d. In this case, T is called a tiling of ℝdR^d by Ω , and Ω is called a tile. The definitions for translational monotilings of ℤdZ^d are analogous. Much of the recent development in the area [Bha20, GT21, GT24, GT25] have been driven by the so-called periodic tiling conjecture. Conjecture 2 (Periodic tiling conjecture (PTC), [LW96]). Let Ω⊆ℝd ^d be a tile. Then there is a tiling T of ℝdR^d by Ω that is periodic, that is, γ∈ℝd:γ+T=T\γ ^d:γ+T=T\ contains a lattice. Unlike in the case of general tiling problems, where more tiles are allowed, PTC holds in ℤ2Z^2 which was proven by Bhattacharya [Bha20]. On the other hand Greenfeld and Tao [GT24] showed that PTC fails in ℤdZ^d (and thus ℝdR^d) for large enough d. In ℝ2R^2 Kenyon [Ken92] showed that PTC holds for tiles that are topological disks, but the general case is widely open. Together with de Dios, Greenfeld and Madrid we investigated the case of tiles that are polygonal sets (possibly disconnected with holes) with edges being axes parallel that may have irrational lengths. We obtain the following general statement, providing a weak form of PTC. Theorem 3 ([dDGGM26]). Let Ω⊆ℝ2 ^2 be an axes parallel polygonal tile. Then there is k∈ℕk and a tiling T=T1⊔⋯⊔TkT=T_1 … T_k of ℝ2R^2 by Ω such that after possibly swapping the vertical and horizontal axes the following holds: 1. TiT_i is periodic for every 1≤i≤k1≤ i≤ k, 2. Ω⊕Ti T_i is a union of cosets of ℝ(0,1)R(0,1), 3. there is γ∈ℝ2∖0γ ^2 \0\ such that T+γ=T+γ=T, more specifically, if k>1k>1, then γ is of the form γ=(0,α)γ=(0,α) for some α>0α>0. Note that if k=1k=1 (or in the discrete case ℤ2Z^2), then (1) above would already imply that T is periodic, thus establishing the PTC for Ω . Our current techniques do not seem to give any information about the possible relation between TiT_i’s or the sets of the form Ω⊕Ti T_i. This leads to the question of whether there exist interesting tilings as in Theorem 3. Without any restriction, the answer to this question is trivial, as one might consider the lattice tiling of ℝ2R^2 by a unit square [0,1]×[0,1][0,1]×[0,1] and construct for any k∈ℕk a tiling T as above by shifting different columns. In order to avoid this trivial case we need a definition. Definition 4. We say that Ω⊆ℝ2 ^2 tiles a column (or is a column tile), if there is S⊆ℝ(0,1)S (0,1) such that Ω⊕S S is a union of cosets of ℝ(0,1)R(0,1). Bolzano produced non-column examples for Theorem 3, where T=T1⊔T2T=T_1 T_2 and each part of the decomposition is periodic with different lattices. This is a first step towards understanding additional flexibility that tilings of ℝ2R^2 enjoy compared to tilings of ℤ2Z^2. Theorem 5. For every irrational α∈(2/3,1)α∈(2/3,1) there is an axis parallel polygonal tile Ωα⊆ℝ2 _α ^2 that is not a column tile together with a tiling Tα=T1,α⊔T2,αT_α=T_1,α T_2,α of ℝ2R^2 by Ωα _α such that the following holds: 1. T1,αT_1,α is (2ℤ)×ℤ(2Z)×Z periodic, 2. T2,αT_2,α is periodic with lattice (2k,kα+ℓ):k,ℓ∈ℤ\(2k,kα+ ):k, \, 3. Ωα⊕Ti,α _α T_i,α is a union of cosets of ℝ(0,1)R(0,1) for 1≤i≤21≤ i≤ 2, 4. TαT_α is (0,1)(0,1)-periodic. The proofs appear in Appendix A. The Bolzano research transcript is available at [Bol26e]. Remark 6. Let us mention that each of the tiles Ωα _α tile a horizontal column (that is, when we swap the horizontal and vertical axes, then the modified tile Ωα′ _α tiles a column), and the projection of Ωα⊕Ti _α T_i to the first coordinate is equal to (2ℤ+(i−1))+[0,1](2Z+(i-1))+[0,1]. It seems that finding examples that would not have such a structure, or that would admit tilings that split as T=T1⊔T2⊔T3T=T_1 T_2 T_3 with the period of T3T_3 parametrized by β>0β>0 such that both β,β−αβ,β-α are irrational, is significantly more complicated, and Bolzano was not able to find an example nor to prove a general obstruction result for any of these conditions. 3.3 Special Soundness for Univariate KZG Batching – Pavel Hubáček Polynomial Commitment Schemes (PCS) are a core building block of modern zero-knowledge proofs (zk-SNARKs). To minimize proof size and verification costs, practical systems often rely on batching techniques that allow a prover to aggregate evaluations of multiple polynomials at multiple points into a single proof. For the popular univariate KZG commitment scheme [KZG10], existing multi-polynomial, multi-point batching protocols (e.g., [BDFG20]) have predominantly been analyzed only in idealized settings, limiting the assurance for their practical deployments. Proving their knowledge soundness in the standard model under falsifiable assumptions is a notoriously difficult task; the first prior standard-model analysis was strictly limited to the simpler case of batching evaluations of many polynomials at a single evaluation point [LPS25]. In the development of CHOPIN [BHKM26], an optimal pairing-based multilinear PCS, we required a fully rigorous standard-model security proof for multi-polynomial, multi-point batching that was not known. The human researchers proposed a variant of the KZG batch proof from [BDFG20] to simplify the task of proving its special soundness in the standard model, the core task towards a complete proof of knowledge soundness of the scheme. However, the human researchers did not have any rigorous proof. Together with Bolzano, we resolved this gap. To assist the system, the input also contained a proof of the more basic theorem establishing the special soundness for batching KZG evaluation proofs for many polynomials at a single evaluation point from [LPS25], streamlined by the human researchers. After being given the problem, Bolzano found the proof of special soundness for the proposed variant of univariate KZG batching in six rounds of interaction. The proof was lengthy and technical, but, besides minor edits in notation and presentation, it was complete and formal as verified by the authors. Formal results. The lemma proven in [BHKM26] is the following. Lemma 7 (Special soundness of multi-polynomial, multi-point KZG batching [BHKM26, Lemma 3]). Let m,M,M′∈poly(λ)m,M,M (λ). Let T=⋃t=1mStT= _t=1^mS_t and let L=|T|+ML=|T|+M. Assume that KZG for degree less than M has M-special soundness in the following sense. From any set of M′≥M ≥ M accepting KZG opening transcripts for the same commitment C at M′M distinct points a1,…,aM′a_1,…,a_M with aj≠τa_j≠τ, one can extract a polynomial p∈[X]<Mp [X]^<M such that C=[p(τ)]1C=[p(τ)]_1 and p(aj)=yjp(a_j)=y_j for all j∈[M′]j∈[M ]. Then there exists an extractor that, given as input any product-structured accepting (m,L)(m,L)-tree =(ij)i∈[m],j∈[L]T=( tr_ij)_i∈[m],\,j∈[L] for the batch evaluation protocol of Figure 7 of [BHKM26], outputs polynomials p1,…,pm∈[X]<Mp_1,…,p_m [X]^<M such that Ct=[pt(τ)]1C_t=[p_t(τ)]_1 for all t∈[m]t∈[m] and pt(z)=ηzp_t(z)= _z for all t∈[m]t∈[m] and all z∈Stz∈ S_t. Equivalently, the batch evaluation protocol is (m,L)(m,L)-special sound with respect to product-structured accepting transcript trees. The Bolzano research transcript is available at [Bol26b]. The complete proof appears in [BHKM26]. 3.4 Equivalence of Weak and Strong Working Set Properties for Heaps – Václav Rozhoň The setting for this subsection is the beyond worst-case theory of data structures, in particular heaps. Two plausible definitions of a beyond worst-case heap occur in the literature – the strong working set property from [Iac00] and the weak working set property from [Elm06]. The strong working set property in particular has been crucial in a recent line of research [HHR+23, Iac00]. It was long assumed that the strong working set property was strictly stronger than the weak one. Surprisingly, they turn out to be equivalent. This was first proven by a human expert, but when given this task, Bolzano independently came up with a different proof and suggested a quantitative strengthening Equation 1 that was not apparent from the original proof. The strengthening gives an even tighter picture of how close the two definitions are. Formal results Consider heaps that support the operations Insert and ExtractMin. We study two notions of locality-sensitive cost for such data structures. Definition 8 (Weak working set property). A heap satisfies the weak working set property if, for any sequence of m operations, the total cost of serving them is O(m+∑xlog(tx′−tx+1))O(m+ _x (t _x-t_x+1)), where the sum is over all extracted elements x, txt_x is the insertion time of x, and tx′t _x is the extraction time of x. Definition 9 (Strong working set property). A heap satisfies the strong working set property if, for any sequence of m operations, the total cost of serving them is O(m+∑xmaxtx≤t<tx′log(|Wt,x|+1))O(m+ _x _t_x≤ t<t _x (|W_t,x|+1)), where Wt,xW_t,x is the set of all elements that have been inserted after time txt_x and are still present at time t. Theorem 10. A heap has the weak working set property if and only if it has the strong one. In fact, the following holds for any ε>0 >0. ∑xlogLx≤(1+ε)∑xlogKx+O(m/ε) _x L_x≤(1+ ) _x K_x+O(m/ ) (1) where Lx=tx′−tx+1L_x=t _x-t_x+1 is the lifetime of element x and Kx=maxtx≤t<tx′(|Wt,x|+1)K_x= _t_x≤ t<t _x(|W_t,x|+1) is its strong working set cost. The theorem is proven in Appendix B. The Bolzano research transcript is available at [Bol25a]. 3.5 Partitioning under Function Preimage Constraints – Robert Šámal KAMAK is a Czech problem-solving workshop where participants propose and collect open problems in combinatorics and discrete mathematics. The present problem appears as Problem 1 in the collection from the 2020 edition [Krá20]. The problems are suggested by the participants and are of various difficulty, but always meant as potentially interesting research problems. Consider sets E and F, together with functions f1,…,fk:E→Ff_1,…,f_k:E→ F satisfying pointwise distinctness, meaning that fi(x)≠fj(x)for every x∈E and every i≠j.f_i(x)≠ f_j(x) every x∈ E and every i≠ j. Conjecture suggested by C. Feghali asked whether a condition on fibre sizes forces a certain bounded partition. (Pointwise distinctness is obviously necessary.) The case k=2k=2 was known and had applications in digraph coloring [BHB06]. Conjecture 11 (Original conjecture; the case k=2k=2 is known). If for every z∈Fz∈ F there exists t∈1,…,kt∈\1,…,k\ with |ft−1(z)|≤n|f_t^-1(z)|≤ n, then E can be partitioned into 2n+12n+1 parts E1,…,E2n+1E_1,…,E_2n+1 such that fp(Ei)∩fq(Ei)=∅for every i and every p<q.f_p(E_i)∩ f_q(E_i)= every i and every p<q. A convenient way to view the problem is through the conflict graph on vertex set E, in which distinct x,y∈Ex,y∈ E are adjacent whenever fp(x)=fq(y)f_p(x)=f_q(y) for some p≠qp≠ q. Then a partition with the required disjointness property is exactly a proper coloring of this graph. Bolzano’s first contribution was to observe that for k≥3k≥ 3 the original hypothesis can be satisfied vacuously: a dummy function may have empty fibers and thus the remaining functions are not controlled. This leads to the following negative result. Theorem 12 (Counterexample to the original conjecture). For every n≥1n≥ 1 and every M≥1M≥ 1, there exist sets E,FE,F and functions f1,f2,f3:E→Ff_1,f_2,f_3:E→ F such that: 1. fi(x)≠fj(x)f_i(x)≠ f_j(x) for all x∈Ex∈ E and all i≠ji≠ j; 2. for every z∈Fz∈ F there exists t∈1,2,3t∈\1,2,3\ with |ft−1(z)|≤n|f_t^-1(z)|≤ n; 3. every partition of E satisfying fp(Ei)∩fq(Ei)=∅for all i and all p<qf_p(E_i)∩ f_q(E_i)= all i and all p<q requires more than M parts. The construction realizes the conflict graph as a shift graph, whose chromatic number is unbounded. The full proof appears in Appendix C. The counterexample suggests that the right assumption is not to control single fibers, but to control them pairwise. This leads to the following notion, also suggested by Bolzano. Definition 13 (Pairwise n-boundedness). The functions f1,…,fk:E→Ff_1,…,f_k:E→ F are pairwise n-bounded if for every z∈Fz∈ F and every pair p≠qp≠ q, min(|fp−1(z)|,|fq−1(z)|)≤n. (|f_p^-1(z)|,\;|f_q^-1(z)| )≤ n. Under this stronger hypothesis one gets a positive result. Theorem 14 (Pairwise n-boundedness implies bounded partition). Assume pointwise distinctness and pairwise n-boundedness. Then E can be partitioned into 2nk(k−1)+12nk(k-1)+1 parts E1,…,E2nk(k−1)+1E_1,…,E_2nk(k-1)+1 such that fp(Ei)∩fq(Ei)=∅for every i and every p<q.f_p(E_i)∩ f_q(E_i)= every i and every p<q. The proof orients each conflict toward the endpoint whose side of the witnessing equality comes from a small fiber, thereby obtaining a bounded-indegree orientation of the conflict graph. This implies bounded degeneracy and hence bounded chromatic number. Appendix C contains the full proof, together with a stronger bound under uniform n-boundedness and complementary lower-bound constructions. The Bolzano research transcript is available at [Bol26c]. 3.6 Complexity of Optimization in KKOS Cultural Dynamics – Martin Koutecký Kempe, Kleinberg, Oren, and Slivkins [KKOS16] introduced a model of cultural dynamics in which agents on a social network update their opinions to reduce disagreement with neighbors. In their local model, the equilibrium condition requires that neighboring agents in the support of a distribution experience equal “mass” – that is, the total weight in their closed neighborhood is the same. It is natural (especially motivated by bribery-type viewpoints, see [FGKT22]) to consider the problem of finding a closest equilibrium x to a given (arbitrary) distribution y. Formally, given an undirected graph G=(V,E)G=(V,E) with adjacency matrix A′A , set A=A′+IA=A +I (adding self-loops), and given an initial distribution y∈ℝ≥0Vy _≥ 0^V with ‖y‖1=1\|y\|_1=1 and a cost vector c∈ℝ≥0Vc _≥ 0^V, the task is to find a distribution x∈ℝ≥0Vx _≥ 0^V with ∑vxv=1 _vx_v=1 minimizing ∑vcv|xv−yv| _vc_v|x_v-y_v| subject to the constraint that for every edge uv∈Euv∈ E, if xu,xv>0x_u,x_v>0 then (Ax)u=(Ax)v(Ax)_u=(Ax)_v. Bolzano worked on this problem autonomously over three rounds. In Round 1, Bolzano found a clean NP-hardness proof via a reduction from Clique: adding a universal vertex forces any feasible support to be a clique, and the ℓ1 _1 cost becomes monotone in the clique size. In Round 2, Bolzano established membership in NP (via an LP-based polynomial certificate), corrected a small error in the original problem formulation,222The task statement asserted that for a fixed support S, one can compute a cost-minimizing vector by linear programming. This is not true in the straightforward LP formulation because the exact-support constraint involves strict inequalities, so the feasible region can be open. Bolzano provided a counterexample and a correct reformulation using a max-margin LP. and proved structural results for chordal graphs and forests. In Round 3, Bolzano designed a polynomial-time O(n2)O(n^2) algorithm for forests via dynamic programming on dissociation sets. Formal results. Theorem 15 (NP-completeness). Under the standard binary encoding of rational inputs, the decision version of the KKOS optimization problem is NP-complete. NP-hardness holds even with unit costs, positive rational y, and a universal vertex. The optimization problem is NP-hard. Proposition 16 (Forest characterization). On a forest, the feasible supports are exactly the dissociation sets, i.e., the vertex sets S such that G[S]G[S] has maximum degree at most 11. Theorem 17 (Polynomial-time algorithm for forests). If G is a forest, the optimization problem can be solved in O(n2)O(n^2) time. The forest-restricted decision problem is in P. Remark 18. On chordal graphs, connected feasible supports must be cliques (Proposition 34), so feasible supports are exactly disjoint unions of cliques. The proofs appear in Appendix D. The Bolzano research transcript is available at [Bol26a]. Acknowledgements We thank Tomáš Gavenčiak and Vojtěch Rozhoň for helpful discussions and for their contributions to the development of the Bolzano system. JG, VR, and AZ were supported by the Czech Science Foundation (GA ČR), project No. 26-23599M. RŠ was supported by grant no.25-16627S from the Czech Science Foundation (GAČR). MK was supported by grant no.25-17221S from the Czech Science Foundation (GAČR). References [ABH+26] Mohammed Abouzaid, Andrew J. Blumberg, Martin Hairer, Joe Kileel, Tamara G. Kolda, Paul D. Nelson, Daniel Spielman, Nikhil Srivastava, Rachel Ward, Shmuel Weinberger, and Lauren Williams. First Proof, 2026. [B+25] Benjamin Breen et al. Ax-Prover: A deep reasoning agentic framework for theorem proving in mathematics and quantum physics, 2025. [BCE+25] Sébastien Bubeck, Christian Coester, Ronen Eldan, Timothy Gowers, Yin Tat Lee, Alexandru Lupsasca, Mehtaab Sawhney, Robert Scherrer, Mark Sellke, Brian K. Spears, Derya Unutmaz, Kevin Weil, Steven Yin, and Nikita Zhivotovskiy. Early science acceleration experiments with GPT-5, 2025. [BDFG20] Dan Boneh, Justin Drake, Ben Fisch, and Ariel Gabizon. Efficient polynomial commitment schemes for multiple points and polynomials. IACR Cryptol. ePrint Arch., page 81, 2020. [Bha20] Siddhartha Bhattacharya. Periodicity and decidability of tilings of ℤ2Z^2. American Journal of Mathematics, 142(1):255–266, 2020. [BHB06] S. Bessy, F. Havet, and E. Birmelé. Arc-chromatic number of digraphs in which every vertex has bounded outdegree or bounded indegree. J. Graph Theory, 53(4):315–332, December 2006. [BHKM26] Juraj Belohorec, Pavel Hubáček, Aleksi Kalsta, and Kristýna Mašková. CHOPIN: Optimal pairing-based multilinear polynomial commitments from bivariate KZG. IACR Cryptol. ePrint Arch., page 480, 2026. https://eprint.iacr.org/archive/2026/480/20260308:102759. [BJ12] Samuel R. Buss and Alan S. Johnson. Propositional proofs and reductions between NP search problems. Annals of Pure and Applied Logic, 163(9):1163–1182, 2012. [Bol25a] Bolzano transcript: Heap equivalence. https://bolzano.app/heap-equivalence, 2025. [Bol25b] Bolzano Team. Bolzano. https://bolzano.app/, 2025. [Bol26a] Bolzano transcript: KKOS optimization. https://bolzano.app/kkos-optimization, 2026. [Bol26b] Bolzano transcript: KZG batching. https://bolzano.app/kzg-batching, 2026. [Bol26c] Bolzano transcript: Function-preimage partitioning. https://bolzano.app/function-preimage-partitioning, 2026. [Bol26d] Bolzano transcript: PWPP separation. https://bolzano.app/pwpp-separation, 2026. [Bol26e] Bolzano transcript: Multi-slope tilings. https://bolzano.app/multi-slope-tilings, 2026. [D+25] Jasper Dekoninck et al. The Open Proof Corpus: A large-scale study of LLM-generated mathematical proofs, 2025. [dDGGM26] Jaume de Dios Pont, Jan Grebík, Rachel Greenfeld, and José Madrid. Translational tilings by axes-parallel polygonal sets. Work in progress, 2026. [DLT+23] Yilun Du, Shuang Li, Antonio Torralba, Joshua B. Tenenbaum, and Igor Mordatch. Improving factuality and reasoning in language models through multiagent debate, 2023. [Elm06] Amr Elmasry. A priority queue with the working-set property. Int. J. Found. Comput. Sci., 17(6):1455–1466, 2006. [F+26a] Tony Feng et al. Semi-autonomous mathematics discovery with Gemini: A case study on the Erdős problems, 2026. [F+26b] Tony Feng et al. Towards autonomous mathematics research, 2026. [FGKT22] Piotr Faliszewski, Rica Gonen, Martin Koutecký, and Nimrod Talmon. Opinion diffusion and campaigning on society graphs. J. Log. Comput., 32(6):1162–1194, 2022. [FGPR24] Noah Fleming, Stefan Grosser, Toniann Pitassi, and Robert Robere. Black-box P is not Turing-closed. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 1405–1414, 2024. [FJhK+26] Tony Feng, Junehyuk Jung, Sang hyun Kim, Carlo Pagano, et al. Aletheia tackles FirstProof autonomously, 2026. [G+25] Jiaxing Guo et al. Right is not enough: The pitfalls of outcome supervision in training LLMs for math reasoning, 2025. [GGSTW25] Bogdan Georgiev, Javier Gómez-Serrano, Terence Tao, and Adam Zsolt Wagner. Mathematical exploration and discovery at scale, 2025. [GT21] Rachel Greenfeld and Terence Tao. The Structure of Translational Tilings in ℤdZ^d. Discrete Analysis, 2021. [GT24] Rachel Greenfeld and Terence Tao. A counterexample to the periodic tiling conjecture. Annals of Mathematics, 200(1):301–363, 2024. [GT25] Rachel Greenfeld and Terence Tao. Undecidability of translational monotilings. J. Eur. Math. Soc., 2025. [HHR+23] Bernhard Haeupler, Richard Hladík, Václav Rozhoň, Robert Tarjan, and Jakub Tětek. Universal optimality of Dijkstra via beyond-worst-case heaps, 2023. [HMS+25] Thomas Hubert, Rishi Mehta, Laurent Sartran, Miklós Z. Horváth, et al. Olympiad-level formal mathematical reasoning with reinforcement learning. Nature, 2025. [Hub26] Pavel Hubáček. Black-box PWPP is not Turing closed. CoRR, abs/2602.23809, 2026. https://doi.org/10.48550/arXiv.2602.23809. [HY25] Hao Huang and Lin F. Yang. Winning gold at IMO 2025 with a model-agnostic verification-and-refinement pipeline, 2025. [Iac00] John Iacono. Improved upper bounds for pairing heaps. In Scandinavian Workshop on Algorithm Theory, pages 32–45. Springer, 2000. [Jeř16] Emil Jeřábek. Integer factoring and modular square roots. Journal of Computer and System Sciences, 82(2):380–394, 2016. [Ken92] Richard Kenyon. Rigidity of planar tilings. Inventiones Mathematicae, 107(3):637–651, 1992. [KKOS16] David Kempe, Jon M. Kleinberg, Sigal Oren, and Aleksandrs Slivkins. Selection and influence in cultural dynamics. Netw. Sci., 4(1):1–27, 2016. [Krá20] Karel Král. Open problems. https://kam.mff.cuni.cz/~kamak/static/problems/2020.pdf, 2020. KAMAK Problem Solving Workshop. [KZG10] Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-size commitments to polynomials and their applications. In Masayuki Abe, editor, Advances in Cryptology - ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings, volume 6477 of Lecture Notes in Computer Science, pages 177–194. Springer, 2010. [Log25] Logical Intelligence. Aleph Prover, 2025. https://logicalintelligence.com/aleph-prover.html. [LPS25] Helger Lipmaa, Roberto Parisella, and Janno Siim. On knowledge-soundness of Plonk in ROM from falsifiable assumptions. In Yael Tauman Kalai and Seny F. Kamara, editors, Advances in Cryptology - CRYPTO 2025 - 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2025, Proceedings, Part VII, volume 16006 of Lecture Notes in Computer Science, pages 362–395. Springer, 2025. [LW96] Jeffrey C. Lagarias and Yang Wang. Tiling the line with translates of one tile. Inventiones Mathematicae, 124(1–3):341–365, 1996. [MTG+23] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback. arXiv preprint arXiv:2303.17651, 2023. [N+25] Alexander Novikov et al. AlphaEvolve: A coding agent for scientific and algorithmic discovery, 2025. [Ope26] OpenAI. Our First Proof submissions. https://openai.com/index/first-proof-submissions/, 2026. [PBF24] Arjun Panickssery, Samuel R. Bowman, and Shi Feng. LLM evaluators recognize and favor their own generations, 2024. [PSV26] Moe Putterman, Mehtaab Sawhney, and Gregory Valiant. On infinite sets with no 3 on a line, 2026. [RPBN+24] Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M. Pawan Kumar, Emilien Dupont, Francisco J. R. Ruiz, Jordan S. Ellenberg, Pengming Wang, Omar Fawzi, Pushmeet Kohli, and Alhussein Fawzi. Mathematical discoveries from program search with large language models. Nature, 625(7995):468–475, 2024. [TWL+24] Trieu H. Trinh, Yuhuai Wu, Quoc V. Le, He He, and Thang Luong. Solving olympiad geometry without human demonstrations. Nature, 625(7995):476–482, 2024. [Urb26] Josef Urban. 130k lines of formal topology in two weeks: Simple and cheap autoformalization for everyone?, 2026. [V+25] Sumanth Varambally et al. Hilbert: Recursively building formal proofs with informal reasoning, 2025. [WCAJ+26] David P. Woodruff, Vincent Cohen-Addad, Lalit Jain, Jieming Mao, Song Zuo, et al. Accelerating scientific research with Gemini: Case studies and common techniques, 2026. Appendix A Structural Results on Multi-Slope Tilings This appendix contains the proofs of Theorem 5 from Section 3.2. The periodicity in Theorem 3 allows to simplify the problem by working in the group G=ℤ×G=Z×T, where :=ℝ/ℤT:=R/Z, with counting measure on ℤZ and normalized Lebesgue measure μ on ℝ/ℤR/Z. Addition is componentwise, that is, (m,θ)+(n,φ)=(m+n,θ+φ)(m,θ)+(n, )=(m+n,\,θ+ ). All equalities, coverings, and disjointness statements are understood a.e. with respect to the product measure. In this setup, we work with measurable sets A⊂GA⊂ G of the form A=⋃i=1ℓni×IiA= _i=1 \n_i\× I_i with ni∈ℤn_i distinct and each Ii⊂I_i a half-open interval. The integer support of A is supp(A):=ni:1≤i≤ℓsupp(A):=\n_i:1≤ i≤ \, and the fiber at n is An:=t∈:(n,t)∈AA_n:=\t :(n,t)∈ A\. A set T⊂GT⊂ G is a tiling of G by A if A+T=GA+T=G and the translates A+tt∈T\A+t\_t∈ T are pairwise disjoint up to null sets. This is denoted as A⊕T=GA T=G. If A⊕T=GA T=G, then A is called a tile. Analogously to Definition 4, a set A⊆GA G is a column tile if there exist finite sets C⊂ℤC and Λ⊂ such that A⊂C×A⊂ C×T and the vertical translates A+(0,λ):λ∈Λ\A+(0,λ):λ∈ \ tile C×C×T. A.1 Auxiliary claims Lemma 19 (Multi-coset affine arithmetic-splitting criterion). Let q≥1q≥ 1, and H⊂qℤH⊂ qZ be a finite set of distinct integers. Let Jh⊂J_h be measurable for each h∈Hh∈ H, and βr,αr∈ _r, _r for each 0≤r≤q−10≤ r≤ q-1. Define A:=⋃h∈H(h×Jh)⊂G and Tr:=(qk+r,βr+kαr):k∈ℤ⊂G for each 0≤r≤q−1.A:= _h∈ H(\h\× J_h)⊂ G and T_r:=\(qk+r, _r+k _r):k \⊂ G for each 0≤ r≤ q-1. Then the following are equivalent: 1. A⊕T=GA T=G where T=⋃r=0q−1TrT= _r=0^q-1T_r, 2. for every r∈Rr∈ R, one has the circle partition identity ⨆h∈H(Jh−hqαr)=a.e. _h∈ H (J_h- hq _r )=T .e. Proof. First observe that if 1≤r≤q−11≤ r≤ q-1 and t=(qk+r,βr+kαr)∈Trt=(qk+r, _r+k _r)∈ T_r, then A+t⊆(qℤ+r)×A+t (qZ+r)×T. Hence, it is enough to understand each fixed 1≤r≤q−11≤ r≤ q-1 separately. For m∈ℤm , define the set Fr,m=θ∈:(r+qm,θ)∈A+Tr.F_r,m=\θ :(r+qm,θ)∈ A+T_r\. A point (r+qm,θ)(r+qm,θ) lies in A+(qk+r,βr+kαr)A+(qk+r, _r+k _r) for some k∈ℤk if and only if there exists h∈Hh∈ H such that • q(m−k)=hq(m-k)=h, and • θ∈Jh+βr+kαrθ∈ J_h+ _r+k _r. Because h∈qℤh∈ qZ, the above equation has the unique solution k=m−hqk=m- hq. Substituting this into the vertical condition gives θ∈(Jh−hqαr)+βr+mαrθ∈ (J_h- hq _r )+ _r+m _r. This gives Fr,m=(⋃h∈H(Jh−hqαr))+βr+mαr.F_r,m= ( _h∈ H (J_h- hq _r ) )+ _r+m _r. (2) Now we are ready to show the equivalence. (2)⇒(1)(2) (1). Let 1≤r≤q−11≤ r≤ q-1 and m∈ℤm . Since translation on T preserves Lebesgue measure and preserves pairwise disjointness a.e., the assumed partition identity implies Fr,m=F_r,m=T a.e., and the pieces contributing to (2) are pairwise disjoint a.e. As m∈ℤm was arbitrary, we get that A⊕Tr=(qℤ+r)×A T_r=(qZ+r)×T. This proves (1) by the remark in the beginning of this proof. (1)⇒(2)(1) (2). By the remark in the beginning of the proof and the assumption, we have that (2) reads as =Fr,0=(⨆h∈H(Jh−hqαr))+βr.T=F_r,0= ( _h∈ H (J_h- hq _r ) )+ _r. for every 1≤r≤q−11≤ r≤ q-1 and m=0m=0. Shifting by −βr- _r gives (2). ∎ Proposition 20 (Fiberwise criterion for column tiles). Let A=⋃i=1ℓni×Ii⊆ℤ×A= _i=1 \n_i\× I_i ×T be a column tile. Then there is k∈ℕk such that μ(Ani)=1/kμ (A_n_i )=1/k for every 1≤i≤ℓ1≤ i≤ . Proof. By the definition, there are C⊂ℤC and a finite nonempty set Λ⊂ such that the translates A+(0,λ):λ∈Λ\A+(0,λ):λ∈ \ are pairwise disjoint a.e., and ⨆λ∈Λ(A+(0,λ))=C× _λ∈ (A+(0,λ))=C×T. For each 1≤i≤ℓ1≤ i≤ , observe that =⨆λ∈ΛAni+λT= _λ∈ A_n_i+λ. Therefore 1=μ()=∑λ∈Λμ(Ani+λ)=|Λ|μ(Ani)1=μ(T)= _λ∈ μ(A_n_i+λ)=| |μ(A_n_i) as Lebesgue measure is translation-invariant. ∎ A.2 Explicit construction Choose an irrational ε∈(0,1/3) ∈(0,1/3) and define: • α=1−εα=1- , • I0:=[ε,2ε)I_0:=[ ,2 ), I2:=[2ε,1)I_2:=[2 ,1), I4:=[0,ε)I_4:=[0, ), • Aα=(0×I0)∪(2×I2)∪(4×I4)⊂ℤ×A_α=(\0\× I_0)∪(\2\× I_2)∪(\4\× I_4) ×T, • S1,α:=(2k,0):k∈ℤS_1,α:=\(2k,0):k \ and S2,α:=(2k+1,kα):k∈ℤ.S_2,α:=\(2k+1,kα):k \. We show that Aα⊕Sα=GA_α S_α=G where Sα=S1,α⊔S2,αS_α=S_1,α S_2,α. We verify (2) in Lemma A.1 with q=2q=2, β0=β1=0 _0= _1=0, α0=0 _0=0 and α1=α _1=α. For r=0r=0, we have ⨆2i∈0,2,4I2i=[ε,2ε)⊔[2ε,1)⊔[0,ε)=, _2i∈\0,2,4\I_2i=[ ,2 ) [2 ,1) [0, )=T, and for r=1r=1, we have ⨆2i∈0,2,4(I2i−iα)=[ε,2ε)⊔([2ε,1)−(1−ϵ))⊔([0,ε)−2(1−ϵ))=[ε,2ε)⊔([0,ϵ)⊔[3ϵ,1))⊔([2ϵ,3ε)=, split _2i∈\0,2,4\ (I_2i-iα )=&\ [ ,2 ) ([2 ,1)-(1-ε)) ([0, )-2(1-ε))\\ =&\ [ ,2 ) ([0,ε) [3ε,1)) ([2ε,3 )\\ =&\ T, split where [2ε,1)−(1−ϵ)=[0,ϵ)⊔[3ϵ,1)[2 ,1)-(1-ε)=[0,ε) [3ε,1) follows from the assumption that ϵ∈(0,1/3)ε∈(0,1/3). Observe that, by Proposition 20, A is not a column tile as μ(A∩(0×))μ(A∩(\0\×T)) is not rational. A.3 Proof of Theorem 5 Given an irrational α∈(2/3,1)α∈(2/3,1), consider the tile Aα⊆ℤ×A_α ×T described above, and define Ωα=(n,x)+(t,0):x,t∈[0,1) and (n,x)∈Aα⊆ℝ2. _α=\(n,x)+(t,0):x,t∈[0,1) and (n,x)∈ A_α\ ^2. It follows from the properties of AαA_α and SαS_α that Ωα _α does not tile a column, and that Tα=T1,α⊔T2,αT_α=T_1,α T_2,α, where T1,α=(2ℤ)×ℤT_1,α=(2Z)×Z and T2,α=(2k,kα+ℓ):k,ℓ∈ℤT_2,α=\(2k,kα+ ):k, \, have all the desired properties. Appendix B Equivalence of Weak and Strong Working Set Properties In this appendix we prove the equivalence between the weak and strong working set properties stated in Section 3.4. In fact, we prove the stronger quantitative estimate ∑xlogLx≤(1+ε)∑xlogKx+O(m/ε), _x L_x\;≤\;(1+ ) _x K_x+O(m/ ), (3) valid for every ε>0 >0, where the sum ranges over all extracted elements. The easy point is that Kx≤LxK_x≤ L_x for every element x, so the strong working set bound always implies the weak one. The substance is the converse direction: although an individual lifetime LxL_x can be much larger than the corresponding strong parameter KxK_x, this can only happen for relatively few elements at the same time. The proof makes this precise via a packing argument: at any time t, there cannot be many live elements with small strong parameter. Grouping elements according to the size of KxK_x, this packing bound yields an upper bound on the total lifetime within each group, and Jensen’s inequality then controls the total contribution of log(Lx/Kx) (L_x/K_x). Setup. Consider any sequence of m heap operations, each either Insert of a fresh element or ExtractMin removing a present element. Elements are distinct even if keys coincide. For each element x that is eventually extracted, let txt_x be its insertion time, tx′t _x its extraction time, and define its lifetime Lx:=tx′−tx+1.L_x:=t _x-t_x+1. For each time t with tx≤t<tx′t_x≤ t<t _x, let Wt,xW_t,x be the set of all elements inserted after time txt_x that are still present immediately after operation t. We also define Kx:=maxtx≤t<tx′(|Wt,x|+1).K_x:= _t_x≤ t<t _x (|W_t,x|+1 ). Thus LxL_x is the weak working set parameter and KxK_x is the strong one. For a time t, let A(t)A(t) denote the set of elements present immediately after operation t. All logarithms are base 22. Lemma 21. For every extracted element x, we have Kx≤LxK_x≤ L_x. Proof. Fix t with tx≤t<tx′t_x≤ t<t _x. Every element of Wt,xW_t,x was inserted after time txt_x and no later than time t, so |Wt,x|≤t−tx|W_t,x|≤ t-t_x. Hence |Wt,x|+1≤(t−tx)+1≤(tx′−tx)+1=Lx.|W_t,x|+1≤(t-t_x)+1≤(t _x-t_x)+1=L_x. Taking the maximum over all admissible t gives Kx≤LxK_x≤ L_x. ∎ The next lemma is the key combinatorial input. It says that elements with small strong parameter cannot overlap too much in time. Lemma 22 (Packing lemma). Fix a time t and an integer k≥1k≥ 1. Then at most k elements x∈A(t)x∈ A(t) satisfy Kx≤kK_x≤ k. Proof. Suppose for contradiction that there are k+1k+1 such elements alive after operation t. Let x be the oldest among them, i.e. the one with minimum insertion time. Then the other k elements were all inserted after x and are all present at time t, hence they all belong to Wt,xW_t,x. Therefore |Wt,x|≥k,soKx≥|Wt,x|+1≥k+1,|W_t,x|≥ k, K_x≥|W_t,x|+1≥ k+1, contradicting Kx≤kK_x≤ k. ∎ We now prove the quantitative comparison (3). Theorem 23. For every ε>0 >0 and every operation sequence of length m, ∑xlogLx≤(1+ε)∑xlogKx+O(m/ε), _x L_x\;≤\;(1+ ) _x K_x+O(m/ ), where the sum ranges over all extracted elements x. Proof. Fix ε>0 >0. We may assume ε≤1 ≤ 1, since otherwise the claim is weaker than the case ε=1 =1. Let b:=⌈1ε⌉,b:= 1 , so that 1/b≤ε1/b≤ and b=O(1/ε)b=O(1/ ). We partition the extracted elements into coarse levels according to the size of KxK_x: for each integer j≥0j≥ 0, let Xj:=x:2bj≤Kx<2b(j+1),Nj:=|Xj|.X_j:=\x:2^bj≤ K_x<2^b(j+1)\, N_j:=|X_j|. We first bound the total lifetime inside one level. Since an element x is alive after exactly the times t=tx,tx+1,…,tx′−1t=t_x,t_x+1,…,t _x-1, it contributes Lx−1L_x-1 to ∑tx∈A(t) _t1_x∈ A(t). Therefore ∑x∈Xj(Lx−1)=∑t=1m|Xj∩A(t)|. _x∈ X_j(L_x-1)= _t=1^m|X_j∩ A(t)|. Now if x∈Xjx∈ X_j, then Kx<2b(j+1)K_x<2^b(j+1), hence Kx≤2b(j+1)−1K_x≤ 2^b(j+1)-1. Applying Appendix B with k=2b(j+1)−1k=2^b(j+1)-1, we get |Xj∩A(t)|≤2b(j+1)−1≤2b(j+1)for every t.|X_j∩ A(t)|≤ 2^b(j+1)-1≤ 2^b(j+1) every t. Summing over t yields ∑x∈Xj(Lx−1)≤m⋅2b(j+1), _x∈ X_j(L_x-1)≤ m· 2^b(j+1), and hence ∑x∈XjLx≤m⋅2b(j+1)+Nj≤2m⋅2b(j+1). _x∈ X_jL_x≤ m· 2^b(j+1)+N_j≤ 2m· 2^b(j+1). (4) We now estimate the excess G:=∑xlog(LxKx).G:= _x \! ( L_xK_x ). For x∈Xjx∈ X_j we have Kx≥2bjK_x≥ 2^bj, and therefore log(LxKx)≤log(Lx2bj). \! ( L_xK_x )≤ \! ( L_x2^bj ). Set yx:=Lx/2bjy_x:=L_x/2^bj. By Appendix B, we have yx≥1y_x≥ 1. Also, by (4), ∑x∈Xjyx=∑x∈XjLx2bj≤2m⋅2b(j+1)2bj=2m⋅2b. _x∈ X_jy_x= _x∈ X_j L_x2^bj≤ 2m· 2^b(j+1)2^bj=2m· 2^b. Since log is concave, Jensen’s inequality gives ∑x∈Xjlog(LxKx)≤∑x∈Xjlogyx≤Njlog(2m⋅2bNj). _x∈ X_j \! ( L_xK_x )≤ _x∈ X_j y_x≤ N_j \! ( 2m· 2^bN_j ). Summing over all levels, G≤∑jNjlog(2m⋅2bNj).G≤ _jN_j \! ( 2m· 2^bN_j ). Let n:=∑jNjn:= _jN_j be the number of extracted elements, and let pj:=Nj/np_j:=N_j/n. Then G≤nlog(2m⋅2bn)+nH(p),G≤ n \! ( 2m· 2^bn )+nH(p), where H(p):=−∑jpjlogpjH(p):=- _jp_j p_j is the entropy of the distribution (pj)j(p_j)_j. We bound the two terms separately. For the first term, nlog(2m⋅2bn)=n(b+1)+nlog(m/n).n \! ( 2m· 2^bn )=n(b+1)+n (m/n). Since n≤mn≤ m, the first summand is at most m(b+1)m(b+1). For the second, using the elementary inequality logz≤(z−1)/ln2 z≤(z-1)/ 2 for z≥1z≥ 1, we get nlog(m/n)≤mln2.n (m/n)≤ m 2. Hence nlog(2m⋅2bn)=O(mb).n \! ( 2m· 2^bn )=O(mb). (5) For the entropy term, compare p with the geometric distribution qj:=2−(j+1)q_j:=2^-(j+1) on 0,1,2,…\0,1,2,…\. Nonnegativity of relative entropy gives H(p)≤−∑jpjlogqj=∑jpj(j+1)=1+∑jpjj,H(p)≤- _jp_j q_j= _jp_j(j+1)=1+ _jp_jj, and thus nH(p)≤n+∑jNjj.nH(p)≤ n+ _jN_jj. Now if x∈Xjx∈ X_j, then Kx≥2bjK_x≥ 2^bj, so logKx≥bj K_x≥ bj, i.e. j≤logKxb.j≤ K_xb. Therefore ∑jNjj=∑xj(x)≤1b∑xlogKx, _jN_jj= _xj(x)≤ 1b _x K_x, where j(x)j(x) denotes the unique level index such that x∈Xj(x)x∈ X_j(x). Since also n≤mn≤ m, we obtain nH(p)≤m+1b∑xlogKx.nH(p)≤ m+ 1b _x K_x. (6) Combining (5) and (6), we conclude that G≤O(mb)+1b∑xlogKx.G≤ O(mb)+ 1b _x K_x. Using 1/b≤ε1/b≤ and b=O(1/ε)b=O(1/ ), this becomes G≤ε∑xlogKx+O(m/ε).G≤ _x K_x+O(m/ ). Finally, ∑xlogLx=∑xlogKx+G≤(1+ε)∑xlogKx+O(m/ε), _x L_x= _x K_x+G≤(1+ ) _x K_x+O(m/ ), as claimed. ∎ As an immediate consequence, the weak and strong working set properties are equivalent. Corollary 24. A heap satisfies the weak working set property if and only if it satisfies the strong working set property. Proof. If a heap satisfies the weak working set property, then its total cost on every operation sequence is O(m+∑xlogLx).O\! (m+ _x L_x ). Applying Theorem 23 with any fixed ε (say ε=1 =1), we get ∑xlogLx=O(m+∑xlogKx), _x L_x=O\! (m+ _x K_x ), and therefore the total cost is O(m+∑xlogKx),O\! (m+ _x K_x ), which is exactly the strong working set property. Conversely, if a heap satisfies the strong working set property, then by Appendix B we have Kx≤LxK_x≤ L_x for every extracted element x, hence ∑xlogKx≤∑xlogLx. _x K_x≤ _x L_x. So a bound of the form O(m+∑xlogKx)O\! (m+ _x K_x ) immediately implies O(m+∑xlogLx),O\! (m+ _x L_x ), which is the weak working set property. ∎ Appendix C Partitioning under Function Preimage Constraints In this appendix we prove the two main results stated in Section 3.5: the counterexample to the original conjecture (Theorem 12) and the positive partition theorem under the stronger pairwise boundedness hypothesis (Theorem 14). We also record two complementary observations: under the stronger assumption of uniform n-boundedness the constant improves from 2nk(k−1)+12nk(k-1)+1 to nk(k−1)+1nk(k-1)+1, and even under pairwise n-boundedness one cannot hope for a bound smaller than 2k−12k-1 in general. The natural language for the problem is graph coloring. The following reformulation will be used throughout. Lemma 25 (Conflict graph reformulation). Let E and F be sets, and let f1,…,fk:E→Ff_1,…,f_k:E→ F satisfy fi(x)≠fj(x)f_i(x)≠ f_j(x) for every x∈Ex∈ E and every i≠ji≠ j. Define the conflict graph G on vertex set E by declaring distinct x,y∈Ex,y∈ E adjacent whenever fp(x)=fq(y)for some p≠q.f_p(x)=f_q(y) some p≠ q. Then for every integer m≥1m≥ 1, the following are equivalent: 1. E admits a partition E=E1⊔⋯⊔EmE=E_1 ·s E_m such that fp(Ei)∩fq(Ei)=∅for every i and every p<q;f_p(E_i)∩ f_q(E_i)= every i and every p<q; 2. the graph G is properly m-colorable. Proof. Suppose first that E=E1⊔⋯⊔EmE=E_1 ·s E_m is such a partition. If two distinct vertices x,y∈Eix,y∈ E_i were adjacent in G, then for some p≠qp≠ q we would have fp(x)=fq(y)f_p(x)=f_q(y), and hence fp(Ei)∩fq(Ei)≠∅f_p(E_i)∩ f_q(E_i)≠ , a contradiction. Thus every EiE_i is an independent set, so the partition defines a proper m-coloring of G. Conversely, suppose that c:E→1,…,mc:E→\1,…,m\ is a proper m-coloring of G, and let Ei:=c−1(i)E_i:=c^-1(i). If for some i and some p≠qp≠ q the sets fp(Ei)f_p(E_i) and fq(Ei)f_q(E_i) were not disjoint, we could choose x,y∈Eix,y∈ E_i with fp(x)=fq(y)f_p(x)=f_q(y). Then x≠yx≠ y by assumptions, so x and y would be adjacent in G, contradicting the fact that EiE_i is a color class. ∎ C.1 A counterexample to the original conjecture We now prove Theorem 12. The mechanism behind the counterexample is simple: while for k=2k=2 the assumption implies that the maximum degree in the conflict graph is at most 2n2n, for k≥3k≥ 3, the original assumption can be satisfied vacuously by means of a “dummy” function with many empty fibers, while the remaining two functions create a highly chromatic conflict graph. Proof of Theorem 12. Fix n≥1n≥ 1 and M≥1M≥ 1. Let m>2Mm>2^M, and define E:=(i,j):1≤i<j≤m,F:=0,1,…,m.E:=\(i,j):1≤ i<j≤ m\, F:=\0,1,…,m\. Define three functions on E by f1(i,j):=i,f2(i,j):=j,f3(i,j):=0.f_1(i,j):=i, f_2(i,j):=j, f_3(i,j):=0. The pointwise distinctness condition holds: for every (i,j)∈E(i,j)∈ E we have i<ji<j and 0∉1,…,m0∉\1,…,m\, so the three values f1(i,j),f2(i,j),f3(i,j)f_1(i,j),f_2(i,j),f_3(i,j) are pairwise distinct. The fiber size condition is also satisfied. Indeed, if z∈1,…,mz∈\1,…,m\, then f3−1(z)=∅f_3^-1(z)= , while for z=0z=0 we have f1−1(0)=∅f_1^-1(0)= . Thus for every z∈Fz∈ F there exists some t∈1,2,3t∈\1,2,3\ with |ft−1(z)|=0≤n|f_t^-1(z)|=0≤ n. It remains to analyze the conflict graph G. Since f3f_3 takes only the value 0, while neither f1f_1 nor f2f_2 ever takes the value 0, no edge of G is witnessed by an equality involving f3f_3. Thus two distinct vertices (i,j)(i,j) and (i′,j′)(i ,j ) are adjacent if and only if either f2(i,j)=f1(i′,j′)⟺j=i′,f_2(i,j)=f_1(i ,j ) j=i , or f1(i,j)=f2(i′,j′)⟺i=j′.f_1(i,j)=f_2(i ,j ) i=j . This graph is known as the shift graph SmS_m. It is well-known, that χ(Sm)>Mχ(S_m)>M; we include a simple proof to keep the treatment self-contained. Let c be any proper coloring of SmS_m using r colors. For each j∈1,…,mj∈\1,…,m\ define Aj:=ℓ: there exists i<j with c(i,j)=ℓ.A_j:=\ : there exists i<j with c(i,j)= \. We claim that the sets A1,…,AmA_1,…,A_m are pairwise distinct subsets of 1,…,r\1,…,r\. Indeed, take 1≤j<k≤m1≤ j<k≤ m, and let ℓ:=c(j,k) :=c(j,k). Then ℓ∈Ak ∈ A_k by definition. If also ℓ∈Aj ∈ A_j, then there exists i<ji<j with c(i,j)=ℓc(i,j)= . But in the shift graph the vertices (i,j)(i,j) and (j,k)(j,k) are adjacent, since their second and first coordinates coincide, a contradiction, as c is a coloring. Hence ℓ∉Aj ∉ A_j, so Aj≠AkA_j≠ A_k. Thus we have m distinct subsets of an r-element set, which implies m≤2rm≤ 2^r. Since m>2Mm>2^M, we conclude that r>Mr>M. Therefore χ(Sm)>Mχ(S_m)>M, and hence the conflict graph G is not M-colorable. By Appendix C, any partition satisfying the required disjointness condition must use more than M parts. ∎ The same construction immediately rules out the original conjecture for all larger values of k. Corollary 26. For every k≥3k≥ 3, the original conjecture fails. Proof. Starting from the construction above for f1,f2,f3f_1,f_2,f_3, add functions f4,…,fkf_4,…,f_k whose ranges are disjoint from one another and from the range of f1,f2,f3f_1,f_2,f_3. This preserves pointwise distinctness and does not remove any edges from the conflict graph, so the graph still contains the shift graph SmS_m and therefore has arbitrarily large chromatic number. ∎ C.2 The strengthened hypothesis The counterexample shows that the original assumption is too weak because it constrains only individual fibers. A natural fix is to require smallness pairwise across the functions involved in a potential conflict. We now prove Theorem 14. Proof of Theorem 14. Let G be the conflict graph from Appendix C; we orient its edges so that every vertex has bounded indegree. Consider an edge xyxy of G. By definition, there exist indices p≠qp≠ q such that fp(x)=fq(y)=:z.f_p(x)=f_q(y)=:z. By pairwise n-boundedness, min(|fp−1(z)|,|fq−1(z)|)≤n. (|f_p^-1(z)|,\;|f_q^-1(z)| )≤ n. If |fp−1(z)|≤n|f_p^-1(z)|≤ n, orient the edge from x to y; otherwise orient it from y to x. (If both inequalities hold, choose either orientation.) We claim that every vertex has indegree at most d:=nk(k−1)d:=nk(k-1). Fix a vertex y∈Ey∈ E. For an incoming edge x→yx→ y, there exist indices p≠qp≠ q such that fp(x)=fq(y)and|fp−1(fq(y))|≤n.f_p(x)=f_q(y) |f_p^-1(f_q(y))|≤ n. For any y∈Ey∈ E, the number of such triples (p,q,x)(p,q,x) is at most k(k−1)nk(k-1)n, thus indeg(y)≤k(k−1)n=dindeg(y)≤ k(k-1)n=d. Now any induced subgraph H of G has at most d|V(H)|d|V(H)| edges (counting arcs by their tails), thus average degree at most 2d2d. Therefore, G is 2d2d-degenerate and therefore (2d+1)(2d+1)-colorable, so χ(G)≤2nk(k−1)+1.χ(G)≤ 2nk(k-1)+1. The desired partition now follows from Appendix C. ∎ Under even stronger hypothesis that every fiber of every function has size at most n, one gets a better constant, because then the conflict graph has maximum degree (rather than merely maximum indegree) bounded by d. Theorem 27 (Uniform n-boundedness). Assume pointwise distinctness and suppose that |fi−1(z)|≤nfor every i∈1,…,k and every z∈F.|f_i^-1(z)|≤ n every i∈\1,…,k\ and every z∈ F. Then E can be partitioned into nk(k−1)+1nk(k-1)+1 parts with the required disjointness property. Proof. Let G be the conflict graph. Fix a vertex y∈Ey∈ E. For each ordered pair (p,q)(p,q) with p≠qp≠ q, define Np,q(y):=x∈E∖y:fp(x)=fq(y).N_p,q(y):=\x∈ E \y\:f_p(x)=f_q(y)\. Then |Np,q(y)|≤|fp−1(fq(y))|≤n|N_p,q(y)|≤|f_p^-1(f_q(y))|≤ n. Since every neighbor of y belongs to at least one such set, degG(y)≤∑p≠q|Np,q(y)|≤nk(k−1). _G(y)≤ _p≠ q|N_p,q(y)|≤ nk(k-1). Thus Δ(G)≤nk(k−1) (G)≤ nk(k-1), and therefore G is (nk(k−1)+1)(nk(k-1)+1)-colorable. The claim follows from Appendix C. ∎ C.3 Lower bounds The upper bounds above are not tight in general, but even under pairwise n-boundedness one cannot hope for a bound independent of k. Proposition 28. For every k≥2k≥ 2 and every n≥1n≥ 1, there exist examples satisfying pairwise n-boundedness for which at least 2k−12k-1 parts are required. Proof. Let E=F=ℤ2k−1E=F=Z_2k-1 and define for i=1,…,ki=1,…,k fi(x):=x+i.f_i(x):=x+i. Each fif_i is a bijection, so in particular all fibers have size 1≤n1≤ n. Hence the instance satisfies the stronger uniform n-boundedness condition. We claim that the conflict graph is the complete graph K2k−1K_2k-1. Indeed, let x≠yx≠ y and write δ:=y−x∈ℤ2k−1∖0δ:=y-x _2k-1 \0\. The set of ordered differences p−q:p≠q=−(k−1),…,−1,1,…,k−1\p-q:p≠ q\=\-(k-1),…,-1,1,…,k-1\ coincides with all nonzero residues modulo 2k−12k-1. Hence there exist p≠qp≠ q with p−q=δp-q=δ, which is equivalent to fp(x)=x+p=y+q=fq(y).f_p(x)=x+p=y+q=f_q(y). Thus every two distinct vertices are adjacent. Therefore the conflict graph is K2k−1K_2k-1 and requires 2k−12k-1 colors. ∎ Appendix D Complexity of Optimization in KKOS Cultural Dynamics In this appendix we prove the results stated in Section 3.6. We first establish NP-hardness of the decision problem via a reduction from Clique, then prove membership in NP under rational input encoding, yielding NP-completeness. Finally, we characterize feasible supports on forests and give a polynomial-time algorithm. Throughout, G=(V,E)G=(V,E) is an undirected graph, A′A is its adjacency matrix, A=A′+IA=A +I (self-loops added), y∈ℝ≥0Vy _≥ 0^V is a distribution with ‖y‖1=1\|y\|_1=1, and c∈ℝ≥0Vc _≥ 0^V is a cost vector. A distribution x∈ℝ≥0Vx _≥ 0^V with ∑vxv=1 _vx_v=1 is feasible if for every edge uv∈Euv∈ E, whenever xu,xv>0x_u,x_v>0 one has (Ax)u=(Ax)v(Ax)_u=(Ax)_v. We write supp(x)=v:xv>0supp(x)=\v:x_v>0\ and call (Ax)v(Ax)_v the mass at vertex v. D.1 NP-hardness Lemma 29 (Universal vertex forces clique support). Let G be a graph with a universal vertex z. If x is a feasible distribution with z∈supp(x)z (x), then G[supp(x)]G[supp(x)] is a clique. Proof. Let S=supp(x)S=supp(x). Fix any u∈Su∈ S with u≠zu≠ z. Since z is universal, zu∈Ezu∈ E. Because xz,xu>0x_z,x_u>0, feasibility gives (Ax)u=(Ax)z(Ax)_u=(Ax)_z. Now z is adjacent to every vertex of S, and A includes self-loops, so (Ax)z=∑v∈Sxv=1(Ax)_z= _v∈ Sx_v=1. Hence (Ax)u=1(Ax)_u=1. But (Ax)u=∑v∈S∩NG[u]xv(Ax)_u= _v∈ S∩ N_G[u]x_v, and every xvx_v with v∈Sv∈ S is positive. This sum equals 1=∑v∈Sxv1= _v∈ Sx_v only if S⊆NG[u]S N_G[u]. Since this holds for every u∈Su∈ S, the support induces a clique. ∎ Lemma 30 (ℓ1 _1 cost lower bound). Assume ci=1c_i=1 for all i. Let S⊆VS V, and let x be any distribution with supp(x)⊆Ssupp(x) S. Then ‖x−y‖1≥2(1−y(S))\|x-y\|_1≥ 2(1-y(S)), where y(S)=∑i∈Syiy(S)= _i∈ Sy_i. Proof. Because xi=0x_i=0 for i∉Si∉ S, ∑i∉S|xi−yi|=∑i∉Syi=1−y(S) _i∉ S|x_i-y_i|= _i∉ Sy_i=1-y(S). Also, ∑i∈Sxi=1 _i∈ Sx_i=1 and ∑i∈Syi=y(S) _i∈ Sy_i=y(S), so ∑i∈S(xi−yi)=1−y(S) _i∈ S(x_i-y_i)=1-y(S). By the triangle inequality, ∑i∈S|xi−yi|≥1−y(S) _i∈ S|x_i-y_i|≥ 1-y(S). Adding gives ‖x−y‖1≥2(1−y(S))\|x-y\|_1≥ 2(1-y(S)). ∎ Theorem 31 (NP-hardness). The decision problem—given G, rational y,cy,c, and rational threshold B, decide whether a feasible distribution x with ∑vcv|xv−yv|≤B _vc_v|x_v-y_v|≤ B exists—is NP-hard. Hardness holds even with ci=1c_i=1 for all i, positive rational y, and G having a universal vertex. Proof. We reduce from Clique. Let (H,k)(H,k) be an instance with H=(U,F)H=(U,F) and m=|U|m=|U|. Construct G by adding a universal vertex z adjacent to all of U. Set ci=1c_i=1 for all i, yz=2/3y_z=2/3, yu=1/(3m)y_u=1/(3m) for each u∈Uu∈ U, and threshold Tk=2/3−2k/(3m)T_k=2/3-2k/(3m). Forward. If H has a clique C of size k, set S=z∪CS=\z\∪ C. Then G[S]G[S] is a clique, so any distribution on S is feasible. Define xu=1/(3m)x_u=1/(3m) for u∈Cu∈ C, xu=0x_u=0 for u∈U∖Cu∈ U C, xz=1−k/(3m)x_z=1-k/(3m). Its cost is 2(m−k)/(3m)=Tk2(m-k)/(3m)=T_k. Backward. Suppose x is feasible with cost ≤Tk≤ T_k. If xz=0x_z=0, the z-coordinate contributes 2/32/3 and ∑u∈U|xu−yu|≥2/3 _u∈ U|x_u-y_u|≥ 2/3 (since ∑uxu=1 _ux_u=1 while ∑uyu=1/3 _uy_u=1/3), giving cost ≥4/3>Tk≥ 4/3>T_k, a contradiction. So z∈supp(x)z (x), and by Section D.1, supp(x)=z∪Csupp(x)=\z\∪ C for a clique C in H of size t. By Section D.1, the cost is ≥2/3−2t/(3m)≥ 2/3-2t/(3m), so t≥kt≥ k. ∎ D.2 Membership in NP Theorem 32 (NP-membership). Under the standard binary encoding of rational input, the decision problem belongs to NP. Proof. Let the instance be a yes-instance, with feasible distribution x and S=supp(x)S=supp(x). Consider the linear program P(S)P(S) with variables u∈ℝVu ^V, t∈ℝVt ^V, δ∈ℝδ : ui=0 u_i=0 for i∉S, i∉ S, ui≥δ u_i≥δ for i∈S, i∈ S, 0≤ui≤1 0≤ u_i≤ 1 for all i,∑iui=1, all i, _iu_i=1, (Au)a=(Au)b (Au)_a=(Au)_b for every edge ab with a,b∈S, every edge ab with a,b∈ S, ti≥ui−yi,ti≥yi−ui t_i≥ u_i-y_i,\;t_i≥ y_i-u_i for all i,0≤ti≤1, all i, 0≤ t_i≤ 1, ∑iciti≤B, _ic_it_i≤ B, 0≤δ≤1. 0≤δ≤ 1. Maximize δ. The point (u,t,δ)=(x,|x−y|,mini∈Sxi)(u,t,δ)=(x,|x-y|, _i∈ Sx_i) is feasible with δ>0δ>0, so the optimum is positive. All coefficients are rational. An optimal basic feasible solution has coordinates whose length is polynomial in the input, so there exists an optimal solution (u∗,t∗,δ∗)(u^*,t^*,δ^*) with δ∗>0δ^*>0, supp(u∗)=Ssupp(u^*)=S, and polynomial encoding length. Since u∗u^* satisfies all constraints, it is a feasible distribution with cost ≤B≤ B. Thus every yes-instance has a polynomial-size rational certificate, verifiable in polynomial time. ∎ D.3 Structural characterization Lemma 33 (Dominated neighborhoods obstruct feasibility). Let H be a graph. If there is an edge uv∈E(H)uv∈ E(H) with NH[u]⊊NH[v]N_H[u] N_H[v], then no strictly positive vector x∈ℝ>0V(H)x _>0^V(H) can satisfy (Ax)u=(Ax)v(Ax)_u=(Ax)_v for all edges. Proof. We have (Ax)v−(Ax)u=∑w∈NH[v]∖NH[u]xw>0(Ax)_v-(Ax)_u= _w∈ N_H[v] N_H[u]x_w>0, since NH[v]∖NH[u]≠∅N_H[v] N_H[u]≠ and xw>0x_w>0 for all w. ∎ Proposition 34 (Chordal feasible supports are disjoint unions of cliques). Let G be a chordal graph. If S⊆VS V is a feasible support, then every connected component of G[S]G[S] is a clique. Proof. Let H be a connected component of G[S]G[S]. Since G is chordal, H is chordal. Restricting a feasible distribution to the vertices of H gives a strictly positive vector satisfying the mass-equality constraints on H. If H is not a clique, then H has a simplicial vertex s that is not universal (every chordal graph has a simplicial vertex, and a non-clique has one that is not adjacent to all others). Pick any neighbor v of s in H. Since s is simplicial, NH(s)N_H(s) is a clique, so every neighbor of s is also a neighbor of v. Thus NH[s]⊆NH[v]N_H[s] N_H[v], and since s is not universal, NH[s]⊊NH[v]N_H[s] N_H[v]. By Section D.3, no strictly positive feasible vector exists on H, a contradiction. ∎ Proposition 35 (Feasible supports on forests are dissociation sets). Let G be a forest and S⊆VS V nonempty. Then there exists a feasible distribution with support exactly S if and only if G[S]G[S] has maximum degree at most 11. Proof. (⇒)( ) Suppose x is feasible with supp(x)=Ssupp(x)=S. Let H=G[S]H=G[S]. If H has a component with ≥3≥ 3 vertices, let u be a leaf and v its unique neighbor in that component. Then v has another neighbor in the component, so NH[u]⊊NH[v]N_H[u] N_H[v]. Since (Ax)w=∑t∈NH[w]xt(Ax)_w= _t∈ N_H[w]x_t for w∈Sw∈ S (vertices outside S carry zero mass), Section D.3 gives a contradiction. (⇐)( ) If Δ(H)≤1 (H)≤ 1, set xi=1/|S|x_i=1/|S| for i∈Si∈ S, xi=0x_i=0 otherwise. Every support edge uvuv is an isolated K2K_2 in H, so NH[u]=NH[v]=u,vN_H[u]=N_H[v]=\u,v\ and (Ax)u=(Ax)v=2/|S|(Ax)_u=(Ax)_v=2/|S|. ∎ D.4 Polynomial-time algorithm for forests Lemma 36 (Closed-form cost for fixed support). Let S⊆VS V be nonempty. Among all distributions supported within S, the minimum ℓ1 _1-cost is F(S)=∑i∉Sciyi+(1−y(S))mini∈Sci.F(S)= _i∉ Sc_iy_i+(1-y(S)) _i∈ Sc_i. Note: the least-cost distribution above may not be an equilibrium. Proof. Let m=1−y(S)m=1-y(S) and c∗=mini∈Scic_*= _i∈ Sc_i. For any distribution x supported within S, we have xi=0x_i=0 for every i∉Si∉ S, so ∑i∉Sci|xi−yi|=∑i∉Sciyi _i∉ Sc_i|x_i-y_i|= _i∉ Sc_iy_i. For the in-S part, setting di=xi−yid_i=x_i-y_i, we have ∑i∈Sdi=m _i∈ Sd_i=m, so ∑i∈Sci|di|≥c∗∑i∈S|di|≥c∗m _i∈ Sc_i|d_i|≥ c_* _i∈ S|d_i|≥ c_*m. To attain equality, pick r∈Sr∈ S with cr=c∗c_r=c_* and set xi=yix_i=y_i for i∈S∖ri∈ S \r\, xr=yr+mx_r=y_r+m. ∎ Theorem 37 (Polynomial-time algorithm for forests). If G is a forest, the optimization problem is solvable in O(n2)O(n^2) time. The decision problem on forests is therefore in P. Proof. Step 1: reduction to dissociation sets. By Proposition 35, the feasible supports are exactly the nonempty dissociation sets (vertex sets S with Δ(G[S])≤1 (G[S])≤ 1). Since dissociation sets are hereditary, OPT=minF(S):∅≠S⊆V,Δ(G[S])≤1OPT= \F(S): ≠ S V,\; (G[S])≤ 1\. Step 2: anchor at a minimum-cost vertex. Set K=∑i∈VciyiK= _i∈ Vc_iy_i. For each r∈Vr∈ V, let Vr=i∈V:ci≥crV_r=\i∈ V:c_i≥ c_r\, let Gr=G[Vr]G_r=G[V_r], and assign weight wi(r)=(ci+cr)yiw_i^(r)=(c_i+c_r)y_i to each i∈Vri∈ V_r. Let MrM_r be the maximum total weight of a dissociation set in GrG_r containing r. Using Section D.4, for any nonempty dissociation set S with anchor r∈Sr∈ S minimizing cic_i over S: F(S)=K+cr−∑i∈Swi(r)≥K+cr−MrF(S)=K+c_r- _i∈ Sw_i^(r)≥ K+c_r-M_r. Conversely, the dissociation set achieving MrM_r gives F(Sr)=K+cr−MrF(S_r)=K+c_r-M_r. Hence OPT=minr∈V(K+cr−Mr)OPT= _r∈ V(K+c_r-M_r). Step 3: dynamic programming. Each GrG_r is a forest. In the component containing r, root the tree at r. For each vertex v in a rooted subtree, define: • PvP_v: max weight of a dissociation set in the subtree of v with v∉Sv∉ S, • QvQ_v: max weight with v∈Sv∈ S and no child of v in S, • RvR_v: max weight with v∈Sv∈ S and exactly one child of v in S. Base case (leaf): Pv=0P_v=0, Qv=w(v)Q_v=w(v), Rv=−∞R_v=-∞. For children u1,…,utu_1,…,u_t: Pv P_v =∑j=1tmaxPuj,Quj,Ruj, = _j=1^t \P_u_j,Q_u_j,R_u_j\, Qv Q_v =w(v)+∑j=1tPuj, =w(v)+ _j=1^tP_u_j, Rv R_v =w(v)+∑j=1tPuj+max1≤j≤t(Quj−Puj). =w(v)+ _j=1^tP_u_j+ _1≤ j≤ t(Q_u_j-P_u_j). (The RvR_v formula uses the observation that selecting child uju_j adds Quj−PujQ_u_j-P_u_j over the baseline. If v∈Sv∈ S and child uj∈Su_j∈ S, then uju_j cannot have a selected child, so uju_j must be in state Q.) For the root component, MrM_r uses maxQr,Rr \Q_r,R_r\ (the root must be selected). For other components, add maxPρ,Qρ,Rρ \P_ρ,Q_ρ,R_ρ\ at each root ρ. Each MrM_r is computed in O(n)O(n) time; iterating over all anchors takes O(n2)O(n^2). Once a minimizing anchor and optimal dissociation set SrS_r are found, the optimal distribution is xi=0x_i=0 for i∉Sri∉ S_r, xi=yix_i=y_i for i∈Sr∖ri∈ S_r \r\, xr=yr+1−y(Sr)x_r=y_r+1-y(S_r). ∎