AFTD Auto-Formalizing Theoretical Domains

Research-level results, written up

Research Blogs

The results Lean accepted that a researcher in the field would want to read — a published claim shown false, a conjecture or an open question settled, an exact value where there was a gap — each written up the way a short paper is: the question and where it comes from, the definitions, the result with its Lean statement, the proof, and what it leaves open. Results that bear on the same open problem or the same paper share one post, so a post can hold several research-level results. Every theorem a post names links to its Lean proof.

Researchlow tier2026-11-15OP-1027reviewed by Claude Code中文版

Non-Extremal Permutations of the Integers Modulo 105 Have at Most 40 Good Slopes

Question 10.2 of arXiv:2611.04551 investigates the cardinality of the set of good slopes $D_n(f) = \{m \in \mathbb{Z}/n\mathbb{Z} : x \mapsto f(x) + mx \text{ is bijective}\}$ for permutations $f$ of the residue ring $\mathbb{Z}/n\mathbb{Z}$, where $n$ is an odd composite integer with at least two distinct prime divisors and $q$ is its largest prime divisor. A permutation is extremal when $|D_n(f)|$ reaches Euler's totient $\varphi(n)$. The paper asks whether every non-extremal permutation satisfies the gap bound $|D_n(f)| \le \varphi(n)\frac{q-2}{q-1}$, and names $n = 105$ (for which $q = 7$, $\varphi(105) = 48$, and the conjectured bound is 40) as the smallest modulus its results do not cover. We present a machine-checked proof in Lean 4 of the theorem good_slopes_gap_mod_105, establishing that every non-extremal permutation of $\mathbb{Z}/105\mathbb{Z}$ indeed satisfies $|D_{105}(f)| \le 40$. The proof combines a unit-translation certificate (good_slopes_unit_cover_mod105) that embeds the good slopes into the unit group $(\mathbb{Z}/105\mathbb{Z})^\times$ with a Chinese Remainder Theorem splitting $\mathbb{Z}/105\mathbb{Z} \cong \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$. A two-row fiber rigidity theorem (good_slopes_two_row_fiber_rigidity) shows that if the sum of the sizes of the two unit fibers modulo 35 exceeds 40, then every unit slope modulo 35 must be injective in both fibers. This forces the shifted set of good slopes to be the entire unit group of order 48, contradicting non-extremality. Since the paper shows the bound is attained for every odd composite modulus, 40 is the largest number of good slopes of a non-extremal permutation of $\mathbb{Z}/105\mathbb{Z}$.

Researchmedium tier2026-11-13OP-1385reviewed by Codex中文版

Winning Strategies Compress to Positional Strategies When Hidden Opponent Choices Eventually Cease

In prioritized Borel tree games on the infinite binary tree, players navigate positions composed of a tree node and an internal state, producing an infinite sequence of directions and priorities evaluated by Borel winning sets. While games with one or two priorities admit small, state-independent winning strategies, games with three priorities require memory growing with the state space, and whether every such game admits a finite-memory winning strategy remains open (arXiv:2611.10136). In this paper, we consider the question of strategy compression for prioritized Borel games with an arbitrary number of priorities and an arbitrary, possibly infinite, state space. We prove that whenever a player has a winning strategy, with any memory type, and every legal play encounters only finitely many opponent moves with hidden choices—moves where the transition is not uniquely determined by the chosen branch direction and current position—that player also has a memoryless (positional) winning strategy. The result imposes no uniform bound on the number of hidden choices across plays and allows infinitely many public branch choices. The construction selects representative histories by minimizing their hidden-choice records under a well-founded linear order, proves they eventually extend one another along plays without persistent hidden choices, extracts a shadow play consistent with the original strategy, and establishes tail congruence of priorities alongside exact agreement of directions. The main theorem, prioritized_borel_finite_hidden_opponent_choices_positional, has been mechanically formalized and verified in Lean 4.

Researchlow tier2026-11-13OP-13704 research-level results in one postreviewed by Claude Code中文版

Non-Empty Strongly Incomparable Uncomplemented Families: the Bound $2^{n-1}-1$ When Some Element Is Private to One Family

For integers $n \ge 3$ and $3 \le t \le n$, Conjecture 4.3 of arXiv:2611.12199 posits that the maximum total cardinality $M(n,t)$ of $t$ non-empty, mutually strongly incomparable, and uncomplemented families of subsets of an $n$-element set is exactly $2^{n-1} - 1$. While previous results established that $2^{n-1} - 1 \le M(n,t) \le 2^{n-1}$, the upper bound left a gap of one. We prove that the conjectured upper bound $\sum_{j} |\mathcal{A}_j| \le 2^{n-1} - 1$ holds whenever at least one ground-set element occurs in sets from at most one family $\mathcal{A}_i$, requiring uncomplementedness only for $\mathcal{A}_i$ itself. The paper's own extremal construction has such an element, so no configuration of that shape reaches $2^{n-1}$. The proof shows that the union of the other families shatters strictly more sets than it contains, and bounds the designated family together with these shattered sets inside the subsets of the remaining $n-1$ elements. We also establish the conjectured bound in the three-family setting when two families are singletons, when the two families other than an uncomplemented one have combined cardinality strictly below $2^{\lceil n/2 \rceil}$, and for any $t \ge 3$ when the families other than an uncomplemented one have a union of VC-dimension strictly below $\lceil n/2 \rceil$. All definitions, lemmas, and theorems have been formalized and verified in Lean 4.

Researchlow tier2026-11-13reviewed by Claude Code中文版

A Counterexample to the Class-A Repeated-Prefix Adjacency Formula for Lexical Sequences at Prime Degree Seventeen

DOI 10.1006/jcta.2000.3112 (Theorem 5.1, class A) describes the structure of adjacent pairs of lexical sequences: if $a < b$ are adjacent among the lexical sequences with $1 + \sum a = 1 + \sum b = n$, their meet $f$ has $1 + \sum f = m$, and $n = md + r$ with $0 < r < m$, then the smaller sequence is $a = (f_e)^d \delta$, where $f_e$ is the even-length extension of $f$. We show that this formula is false. The sequences $a = [3, 1, 1, 3, 3, 2, 2, 1]$ and $b = [3, 1, 1, 2, 1, 3, 2, 2, 1]$ are lexical of degree 16 ($n = 17$), satisfy $a < b$, are adjacent among lexical sequences of degree 16, and have meet $f = [3, 1, 1, 2]$, so $m = 8$, $d = 2$, $r = 1$. But $a$ does not begin with $(f_e)^2 = [3, 1, 1, 3, 3, 1, 1, 3]$: it differs at the sixth entry. Adjacency is the substantial part: lexical order on sequences of equal sum is inverse Gray-code rank order, so an intermediate lexical sequence would have one of 50 ranks, and at the prime length 17 each of these is excluded by a rotation-maximality criterion. The whole statement is checked in Lean 4.

Researchlow tier2026-11-13reviewed by Claude Code中文版

Doubly Exponential Tail Bounds and Log-Log Discrepancy for Randomized Greedy Carpooling on Forest Edge Sequences

The online carpooling problem asks how to orient arriving edges between vertices to minimize the running vertex discrepancy, defined as the difference between indegree and outdegree. For arbitrary edge sequences fixed in advance, arXiv:2611.00388 gives a randomized algorithm with discrepancy $O((\log T)^{1/3})$, which matches a known lower bound. We ask how the simple randomized greedy algorithm behaves when the arriving edges form a forest, a question we pose here; the paper does not raise it. In this work, we analyze the performance of randomized greedy carpooling on oblivious forest arrival sequences. We show that for any sequence of $T$ edges whose underlying graph is acyclic, the probability that the maximum absolute discrepancy across all vertices and all prefix times exceeds an integer threshold $D \ge 1$ is bounded by $4 T \cdot \text{forest\_carpool\_tail\_envelope}(D)$, where the tail envelope equals $3/8$ for $D = 2$ and $(1/2)^{\text{Fib}(D)}$ for all other thresholds. Because the Fibonacci numbers grow exponentially, this tail bound is doubly exponential in $D$, establishing that the maximum prefix discrepancy is $O(\log \log T)$ with high probability. The proof shows that every vertex's discrepancy law stays symmetric, of fixed parity and below the envelope when two independent components are merged by an edge, and then reduces the prefix maximum to the $4T$ endpoint events at the arrival times of the edges. The entire development is formally verified in Lean 4.

Researchlow tier2026-11-12OP-193reviewed by Claude Code中文版

A cycle plus an isolated vertex is $k$-tight once the cycle has length at least $k((k-1)^2+1)$

For $k \ge 3$ and $m \ge 4k-3$, arXiv:2610.17884 asks whether the disjoint union $C_m \sqcup K_1$ of an $m$-cycle and an isolated vertex is $k$-tight, that is, whether its stable Kneser graph $\operatorname{KG}(C_m \sqcup K_1, k)$, whose vertices are the independent $k$-sets and whose edges join disjoint ones, has chromatic number $m-2k+3$. The paper calls this the simplest open case of its Conjecture 1.3 and proves it only for $m$ beyond an implicit threshold $n_0(k)$, defined by a counting comparison between anchored colour classes and the number of stable $k$-sets. We prove that $C_m \sqcup K_1$ is $k$-tight for every $k \ge 3$ and every $m \ge k((k-1)^2+1)$, for example from $m = 15$ on when $k = 3$ and from $m = 40$ on when $k = 4$. The proof keeps the paper's reduction to a non-anchored colour class, but finds that class differently: by Turán's theorem, any $m-2k+2$ sets of at most $k$ cycle vertices are each met in at most one vertex by some independent $k$-set of the cycle, so no optimal colouring of the cycle's stable Kneser graph can have all its classes anchored. The result is verified in Lean 4 as op_193_cubic_tight_if_cycle_lower, taking as a hypothesis the classical lower bound $\chi(\operatorname{KG}(C_m,k)) \ge m-2k+2$ for the cycle alone.

Researchlow tier2026-11-11OP-861reviewed by Claude Code中文版

Bipartite Subset Graphs with Intersection Threshold Two Are List Colorable for Every Parameter at Least Five

For an integer $k \ge 2$ and an integer threshold $r \ge 0$, the bipartite subset graph $G(k,r)$ has vertex classes $A$ and $B$, two disjoint copies of the family $\binom{[2k-1]}{k}$ of all $k$-element subsets of $\{1, \dots, 2k-1\}$, with an edge between $a_S \in A$ and $b_T \in B$ if and only if $|S \cap T| \le r$. Give every vertex its own subset as its list, and let $r^*(k)$ be the least $r$ for which these standard lists admit no proper coloring. arXiv:2610.42094 shows that $r^2 > 2(2k-1)\ln(2k-1)$ forces uncolorability, so $r^*(k) = O(\sqrt{k \ln k})$, and notes that its method says nothing about the true least $r$. We prove two facts on the other side. First, standard-list colorability at a fixed threshold $r$ passes from $k$ to $k+1$, so $r^*(k)$ is nondecreasing in $k$. Second, $G(5,2)$ is colorable from its standard lists, by a single rule on $\mathbb{Z}_9$ used on both sides. Together they give that $G(k,2)$ is colorable from its standard lists for every $k \ge 5$, that is, $r^*(k) \ge 3$ for all $k \ge 5$. All statements are checked in Lean 4.

Researchlow tier2026-11-11OP-1400reviewed by Claude Code中文版

Existence of a Simple Graph of Order 20 with a Non-Unimodal Zero Forcing Polynomial

The zero forcing polynomial $\mathcal{Z}(G; x) = \sum_{i=1}^n z(G, i) x^i$ of a graph $G$ of order $n$ counts its zero forcing sets by size. Whether it is always unimodal was asked in earlier work; arXiv:2611.11352 answered no with an infinite family, its smallest member having order 81, and asked for the smallest graph with a non-unimodal zero forcing polynomial. We give an explicit graph of order 20 whose zero forcing polynomial is not unimodal: Lean proves $z(G,15) \ge 932$, $z(G,16) \le 909$ and $z(G,17) \ge 939$, so the coefficients dip at 16. Exhaustive enumeration gives the whole polynomial, $420x^{14}+932x^{15}+909x^{16}+939x^{17}+180x^{18}+20x^{19}+x^{20}$. This brings the known upper bound on the smallest order from 81 down to 20.

Researchmedium tier2026-11-10OP-1323reviewed by Claude Code中文版

Subgame-Perfect Equilibria in Two-Agent Block-Snake Picking Games Satisfy Envy-Freeness Up to One Object and No Envy Toward Larger Bundles

In sequential picking games where two agents divide an odd number of indivisible items $2k+1$ under complete information, compensatory picking sequences are designed to balance the order advantages inherent in sequential selection. A question posed in Section 7 of arXiv:2611.09685 asks whether the unique subgame-perfect equilibrium allocations induced by such sequences guarantee compensatory fairness criteria—specifically envy-freeness up to one object (EF1) and no envy toward larger bundles up to any object (NEL)—with respect to the agents' true preferences under pairwise dominance. This post presents the formal verification of the theorem block_snake_two_agent_spe_nel_ef1, which answers its picking-game part in the affirmative for the two-agent block-snake draft sequence. For any positive additive utilities with distinct values per item, every subgame-perfect equilibrium continuation profile produces a root allocation that satisfies both EF1 and NEL under pairwise dominance. The block-snake sequence lets agent 0, who receives $k$ items, pick first in each of the first $k$ rounds, and gives agent 1 the extra item at the end. The proof formalizes the classical bottom-up characterization of the equilibrium, showing that every equilibrium root allocation coincides with a reverse crossout allocation, and proves that reverse crossout allocations under the block-snake sequence satisfy both fairness properties. All definitions, lemmas, and theorems are formally verified in Lean 4.

Researchlow tier2026-11-09OP-1312reviewed by Claude Code中文版

Existence of Range-Criterion Subspaces in $\mathbb{C}^5 \otimes \mathbb{C}^5$ for the Sporadic Krawtchouk Quadruple $(5, 5, 3, 5)$

This paper reports the formal verification in Lean 4 of the existence of range-criterion subspaces for the sporadic Krawtchouk quadruple $(m, n, k, \ell) = (5, 5, 3, 5)$. The range-criterion conjecture, studied in arXiv:2611.08518 (citing prior literature [4]), asks whether for any quadruple of positive integers satisfying $m \le n$, $k \le \ell$, $k + \ell = m + n - 2$, and the binary Krawtchouk polynomial condition $P_{m-1}^{k+\ell}(k) = 0$, there exist complex subspaces $D, E \subset \mathbb{C}^m \otimes \mathbb{C}^n$ of codimensions $k$ and $\ell$ such that no nonzero product vector satisfies $x \otimes y \in D$ and $\bar{x} \otimes y \in E$. While the conjecture was established for all infinite asymmetric families with $m = 3$ and $m = 4$, sporadic zeros for $m \ge 5$ remained open, with $(5, 5, 3, 5)$ being the minimal instance. We settle this case affirmatively by verifying the existence of two linearly independent matrix pencils over the Gaussian integers of sizes $3 \times 5 \times 5$ and $5 \times 5 \times 5$ whose combined $8 \times 5$ pencil maintains full column rank for all nonzero $x \in \mathbb{C}^5$. The formal proof is mechanized in Lean 4 under the theorem range_criterion_subspaces_sporadic_five_five_three_five.

Researchlow tier2026-11-07OP-259reviewed by Claude Code中文版

The Zero-Sum Constant $w_3(3)$ Equals 13, Matching the Linear Dimension Lower Bound

For integers $r \ge 1$ and $n > 1$, the zero-sum constant $w_r(n)$ is defined as the least positive integer $N$ such that every admissible sequence of length $N$ in $\mathbb{Z}^r$—meaning no term is congruent to the zero vector modulo $n$—contains a nonempty subsequence whose sum is congruent to $\mathbf{0} \pmod n$ but not congruent to $\mathbf{0} \pmod{n^2}$. Question 3.1 of arXiv:2610.19965 asks whether $w_r(n) = 2r(n-1) + 1$ holds for all $r \ge 1$ and $n > 1$, matching the universal lower bound $w_r(n) \ge 2r(n-1) + 1$. Equality was known for $r = 1$, for $n = 2$, and for $r = 2$ when $n = 2^k 3^\ell p$; no case with $r \ge 3$ and $n \ge 3$ was settled. This post presents the formal verification in Lean 4 of zero_sum_w_three_three, which establishes that $w_3(3) = 13$, settling the case $r = 3, n = 3$. The proof combines the general lower bound zero_sum_w_ge with an upper bound ZeroSumW33.upper, which classifies, length by length, the residue patterns modulo 3 of the sequences without a good subsequence, up to invertible linear maps modulo 3, by a certificate checked by the Lean kernel. All statements and proofs are machine-checked in Lean 4.

Researchlow tier2026-11-06OP-1112reviewed by Codex中文版

Equal-Marginal Chore Lotteries for Two Agents with Bivalued Costs

For two agents with additive chore costs, suppose that each chore costs agent $i$ either a positive baseline $a_i$ or $r a_i$, with a common ratio $1\le r\le2$. We prove that there is a lottery assigning each chore to each agent with probability $1/2$ and giving each agent at most $(r+1)/2$ times her two-agent chore maximin share in every allocation in the lottery's support. The construction balances the number of chores and each agent's number of high-cost chores across one partition, then mixes that allocation equally with its swap. This gives a ratio-sensitive improvement over the general two-agent equal-marginal $3/2$ guarantee when $r<2$. The upper bound is verified in Lean; the statement does not establish a matching lower bound.

Researchlow tier2026-11-05OP-1087reviewed by Codex中文版

Subcubic Triangle-Free Non-Bipartite Graphs Do Not Always Admit Independent Partitions with Complementary Component Order at Most Three

In the study of graph partitions and cut problems in subcubic graphs, Question 5.4 of arXiv:2611.05178 asks whether every finite simple graph with maximum degree at most 3 and odd girth exactly 5 admits a partition of its vertex set into disjoint subsets $L$ and $R$ such that $L$ is an independent set and every connected component of the induced subgraph on $R$ has order at most 3. This question is answered in the negative. A counterexample is formalized and mechanically verified in Lean 4 as the theorem subcubic_odd_girth_five_partition_component_le_three_negation. The counterexample has vertices $0,\ldots,7$, with edges between consecutive vertices modulo 8 and between vertices four apart. It is cubic and triangle-free, and $0,1,2,3,4,0$ is a 5-cycle, so its odd girth is exactly 5. By establishing that every independent set $L$ leaves at least one vertex whose reachable component in the complementary induced subgraph exceeds order 3, the universal claim is contradicted. This result delineates the boundary of defective vertex partitions in sparse graphs, contrasting with the bipartite case where such partitions always exist.

Researchmedium tier2026-11-05OP-337reviewed by Claude Code中文版

Weighted Half-Coverage by Quasi-Kernels in Oriented Graphs Whose Non-Neighborhoods Have Kernels

The Small Quasi-kernel Conjecture asks whether every finite source-free digraph has a quasi-kernel of at most half its vertices. arXiv:2610.23487 proves that a source-free digraph satisfies this bound as soon as every nonnegative integer weighting of its vertices admits a quasi-kernel whose closed out-neighborhood carries at least half the total weight, and applies this to break digraphs, for which such a weighted theorem was known. We prove this weighted half-coverage property for every finite loopless oriented graph in which the non-neighborhood of every vertex induces a digraph with a kernel. The class contains all tournaments and all oriented complete multipartite graphs, and it contains oriented graphs that are not break digraphs. The proof chooses a vertex of minimum in-weight, ties broken by in-degree: this vertex together with a kernel of its non-neighborhood is a quasi-kernel, since otherwise one of its in-neighbors would have a smaller score, and in an oriented graph the minimum in-weight is at most half the total weight. Combined with the transfer theorem of arXiv:2610.23487, which is not formalized here, this gives the half-order bound for every source-free digraph of the class. The theorem and its lemmas are checked in Lean 4.

Researchlow tier2026-11-03reviewed by Claude Code中文版

A 24-Vertex Oriented Graph Showing f(4) ≥ 5/4 in a Source-Neighborhood Problem for Quasi-Kernels

For a vertex $v$ of a sourceless digraph, let $S(v)$ be the set of sources of $D - N^+[v]$ and let $E(v) = N^+(v) \cup N^+(S(v))$. Problem 5.2 of arXiv:2601.11847 asks, for each $d \ge 2$, for the least constant $f(d)$ such that every sourceless oriented graph of maximum out-degree at most $d$ has a vertex $v$ with $f(d)|E(v)| \ge |S(v)| + 1$, and for the least $d$ with $f(d) > 1$. We give an explicit loopless sourceless oriented graph on 24 vertices with maximum out-degree four in which every vertex satisfies $5|E(v)| \le 4(|S(v)|+1)$: the eight non-sink vertices have $|S(v)| = |E(v)| = 4$ and the sixteen sinks have $S(v) = E(v) = \emptyset$. Hence $f(4) \ge 5/4$, and the least $d$ with $f(d) > 1$ is at most 4; if the paper's Conjecture 5.1 (the case $d = 3$ with constant 1) holds, it is exactly 4. The graph is an instance of the paper's construction for Proposition 2.3, sink leaves attached to a regular core, with a 2-diregular oriented core on eight vertices in place of the regular tournament, which that construction needs on at least seven vertices to beat ratio 1. The same graph has a quasi-kernel of six vertices. All properties are verified in Lean 4.

Researchmedium tier2026-11-03reviewed by Claude Code中文版

An Unweighted 71-Vertex Graph Admits a 33-Step Cycle of Inclusion-Minimal Profitable Deviations in Three-Color Max-Cut

In the max $k$-cut game each vertex of a graph chooses one of $k$ colors and earns the number of its neighbors with a different color. arXiv:1810.09278 showed on a weighted graph that improving deviations performed by minimal coalitions can cycle, so that weighted games admit no strong potential function even when only minimal coalitions may deviate; its concluding section leaves open whether a strong potential function exists on unweighted graphs. We answer this negatively for three colors. On an explicit unweighted graph with 71 vertices, made of four core blocks of eight vertices and three anchor blocks of thirteen, we give a cycle of 33 strong improvements that returns to its starting coloring: the 32 core vertices first deviate jointly, each gaining exactly one, and then return to their original colors one at a time, each again gaining one. Every step is inclusion-minimal: from the coloring where the step starts, no proper subset of the changing vertices has any profitable joint deviation. The joint step lowers the cut by 32 and each of the 32 single moves raises it by one. The definitions, the cycle and its minimality are verified in Lean 4.

Researchlow tier2026-11-02reviewed by Claude Code中文版

Existence of a Five-Step Strong Deviation Cycle in an Unweighted Three-Color Max-Cut Game on 46 Vertices

In the Max-$k$-Cut game, players correspond to the vertices of an undirected graph and choose one of $k$ colors to maximize the number of incident cut edges. While individual best-response dynamics in unweighted graphs always converge to a Nash equilibrium via the cut-weight potential function, coalitional stability behaves differently. In weighted Max-$k$-Cut games, cycles of profitable coalitional deviations are known to exist, and arXiv:1810.09278 discusses whether unweighted graphs admit a strong potential function; its cycle (Proposition 2) uses weighted edges. This post presents an explicit unweighted simple graph on 46 vertices and a sequence of five 3-color profiles that forms a closed cycle of profitable coalitional deviations. At each transition, every vertex whose color changes strictly increases its utility, defined as the number of neighbors assigned a different color. The cycle alternates between a coordinated 32-player deviation across four core blocks of eight vertices and four sequential single-block deviations of eight players each, stabilized by two fixed 7-vertex anchor blocks. This establishes the existence of a periodic sequence of strong deviations returning to the initial coloring after five steps, ruling out any strong potential function for profitable coalitional deviations in unweighted three-color Max-Cut games. The construction, utility calculations, and periodic recurrence are formally verified in Lean 4 under the theorem maxcut_unweighted_strong_deviation_cycle_exists.

Researchmedium tier2026-11-01OP-7332 research-level results in one postreviewed by Claude Code中文版

Positive Trace-Preserving Maps Violate the Universal Spectral Bound $\operatorname{Tr}\Phi \le d\,m(\Phi) + d^2 - d$ in Every Dimension $d \ge 3$

The question whether every positive trace-preserving linear map $\Phi: M_d(\mathbb{C}) \to M_d(\mathbb{C})$ in dimension $d \ge 3$ satisfies the universal spectral bound $\operatorname{Tr}\Phi \le d\,m(\Phi) + d^2 - d$, where $m(\Phi) = \min\{\operatorname{Re}\lambda : \lambda \in \sigma(\Phi)\}$ and $\operatorname{Tr}\Phi$ is the operator trace of $\Phi$, was raised in arXiv:2506.02145 and left open in Section 9 of arXiv:2610.37187. The bound is known for all 2-positive maps. We show, with proofs verified in Lean 4, that the bound fails in every dimension $d \ge 3$. In dimension $d = 3$ it fails for the positive trace-preserving map $\Phi(X) = K X K + \frac{3}{4} P X^T P$ on $M_3(\mathbb{C})$, with diagonal matrices $K = \operatorname{diag}(1/2, 1/2, 1)$ and $P = \operatorname{diag}(1, 1, 0)$. Being the sum of a completely positive map and a completely copositive map, $\Phi$ is positive, and the identity $K^2 + \frac{3}{4} P = I_3$ ensures that $\Phi$ is trace-preserving. It has operator trace $11/2$ and the eigenvalue $-1/2$ (eigenvector $E_{12} - E_{21}$). Consequently, the bound evaluates to $3\,m(\Phi) + 6 \le 9/2$, which is strictly less than the operator trace $11/2$. The same construction with $K = \operatorname{diag}(a, a, 1, \dots, 1)$, $P$ the projection onto the first two coordinates, the weight $1 - a^2$ in place of $3/4$ and $a = (d-2)/(d-1)$ violates the bound in dimension $d$ by exactly $2/(d-1)$. So 2-positivity cannot be weakened to positivity in the trace-preserving bound.

Researchlow tier2026-11-01OP-7reviewed by Claude Code中文版

Extension of Complete EFX Allocations by Two Universally Small Goods with Arbitrary Internal Ranking While Preserving Bundles

The existence of an envy-free up to any good (EFX) allocation for four or more agents with additive valuations remains an open problem in discrete fair division. While the literature provides techniques to insert a single universally least good, extending allocations by multiple items when agents hold conflicting preferences over those items presents a difficulty. We show that any complete EFX allocation of $m$ indivisible goods among $n$ agents with nonnegative additive valuations extends to a complete EFX allocation of $m+2$ goods whenever every agent values each of the two additional goods weakly less than all of the original $m$ goods. The agents need not agree on the relative ranking between the two added goods. The construction preserves every original bundle as an intact unit, permuting the bundles across agents and giving each new good to one agent (possibly the same agent for both), so that every agent's utility weakly increases. The existence of the required permutation and recipient pair follows from an assignment principle for real utility matrices equipped with two additive vector bonuses. Iterating it gives a complete EFX allocation for any number of agents and goods whenever all agents agree on the order of consecutive pairs of goods, while possibly disagreeing within each pair. All definitions, lemmas, and the main extension theorem are formalized and verified in Lean 4.

Researchlow tier2026-10-31OP-744reviewed by Claude Code中文版

The Minimal Advantage Graph of 11-Sided Dice Contains a Non-Transitive Cycle of Length 12

A collection of non-standard dice is non-transitive when the relation "beats" contains a directed cycle. In arXiv:2610.40321, $n$-sided dice with face values in $\{1, \dots, n\}$ are studied through the directed graph $G_n$ on all $\binom{2n-1}{n}$ such dice, with an edge $\mathbf{x} \to \mathbf{y}$ when $\mathbf{x}$ beats $\mathbf{y}$ by exactly the minimal winning advantage. The paper finds cycles longer than $n$ for $n = 7, 8, 9, 10$ by exhaustive search, reports that the cases $n = 11$ and $n = 12$ were considerably more time-consuming, and surmises that $G_{11}$ and $G_{12}$ contain non-transitive cycles of length at least $12$ and $13$.

We settle the $n = 11$ half of this surmise: $G_{11}$, on $\binom{21}{11} = 352,716$ vertices, contains a directed simple cycle of length $12$. The proof is an explicit list of 12 distinct 11-sided dice, each with face sum $66$, in which every die beats the next, cyclically, in exactly $(11^2+1)/2 = 61$ of the $121$ face pairings. The theorem op744_dice11_has_directed_cycle_ge_twelve is checked in Lean 4 by kernel evaluation. The case $n = 12$ remains open.

Researchmedium tier2026-10-31OP-726reviewed by Claude Code中文版

Mutual Power-Divergence Information Strictly Fails Subadditivity for Every Exponent Below the Golden Ratio

Does subadditivity of mutual $f$-information across conditionally independent observations hold for power-divergence generators, and what characterizes the exact range of exponents where it is valid? For exponents $\beta \in (0, 1)$, mutual power-divergence information $I_\beta(X; Y)$ generalizes mutual information to the power-divergence family generated by $f_\beta(t) = (t^\beta - \beta t + \beta - 1)/(\beta(\beta - 1))$. In the conditionally independent observation model $Y \leftarrow X \rightarrow Z$, subadditivity requires $I_\beta(X; (Y, Z)) \le I_\beta(X; Y) + I_\beta(X; Z)$. Sufficient conditions for general $f$-divergences are known, but they do not identify the exact range of exponents for the power-divergence family; numerical evidence points to a boundary at the golden ratio conjugate. This post demonstrates that subadditivity strictly fails for every exponent $\beta$ strictly below the golden ratio conjugate $\beta_* = (\sqrt{5} - 1)/2 \approx 0.618034$. Specifically, for every $\beta \in (0, \beta_*)$, there exists an explicit, strictly positive binary Markov chain $Y \leftarrow X \rightarrow Z$ exhibiting strict superadditivity, $I_\beta(X; (Y, Z)) > I_\beta(X; Y) + I_\beta(X; Z)$. The counterexample is constructed via an asymmetric binary channel with a rare input symbol of probability $p$ and crossover probability of order $\kappa p$. The subadditivity slack vanishes at $p = 0$, and its derivative there can be made positive by a choice of the channel parameters exactly when $1 - \beta - \beta^2 > 0$, that is, when $\beta < \beta_*$. These results have been formalized and verified in the Lean 4 proof assistant.

Researchmedium tier2026-10-30OP-205reviewed by Claude Code中文版

Equivalence Covering Number of the Seventh Power of Cycles of Order Not Divisible by Eight Is Five

An equivalence subgraph of a simple graph is a spanning subgraph that forms a disjoint union of cliques, and the equivalence covering number $\operatorname{eq}(G)$ is the minimum number of equivalence subgraphs whose edge sets together cover all edges of $G$. For the $k$th power $C_n^k$ of the cycle $C_n$ on $n$ vertices, where distinct vertices are adjacent whenever their cyclic distance is at most $k$, determining $\operatorname{eq}(C_n^k)$ when $k+1 = 2^m$ and $n$ is an even integer not divisible by $k+1$ was left open by arXiv:2610.15635, which established that $\operatorname{eq}(C_n^k) \in \{1 + \lceil\log_2(k+1)\rceil, 2 + \lceil\log_2(k+1)\rceil\} = \{m+1, m+2\}$ for sufficiently large $n$ (Theorem 1.4). In this post, we present a verified formalization showing that for $k = 7$ (where $m = 3$) and every integer $n \ge 98$ not divisible by $8$, the equivalence covering number of $C_n^7$ is exactly $5 = 2 + \lceil\log_2 8\rceil$. The result combines a general dyadic upper bound construction yielding $\operatorname{eq}(C_n^k) \le m+2$ whenever $n \ge \max\{2k+2, 2k^2\}$ with a non-covering theorem ruling out any cover of $C_n^7$ by $4$ equivalence subgraphs for all $n \ge 22$ with $8 \nmid n$. All definitions, lemmas, and the main theorem simple_graph_equivalence_covering_number_cycle_power_seven_of_not_dvd have been verified in the Lean 4 proof assistant.

Researchmedium tier2026-10-30OP-205reviewed by Claude Code中文版

The equivalence covering number of the fifteenth cycle power is six for all large even cycle lengths not divisible by sixteen

For the $k$th power $C_n^k$ of the cycle graph $C_n$, an equivalence subgraph is a disjoint union of cliques, and $\operatorname{eq}(C_n^k)$ denotes the minimum number of equivalence subgraphs required to cover all edges of $C_n^k$. While $\operatorname{eq}(C_n^k)$ is known when $k+1$ is not a power of $2$, when $k+1$ divides $n$, or when $n$ is odd, the residual case where $k+1 = 2^m$, $n$ is even, and $2^m$ does not divide $n$ was left open in arXiv:2610.15635, which established only the two-value bound $\operatorname{eq}(C_n^k) \in \{m+1, m+2\}$. We determine the exact equivalence covering number for bandwidth $k = 15$ ($m = 4$): for every even integer $n \ge 3825 = 15^2 \cdot 17$ not divisible by $16$, $\operatorname{eq}(C_n^{15}) = 6 = 2 + \lceil\log_2 16\rceil$. The proof applies a dyadic reduction theorem showing that under the numerical hypotheses of the problem, an equivalence covering number of $m+1$ is impossible whenever every tight, exactly dyadically covered, fully ordinarily covered integer Boolean class model with $m+1$ active classes per vertex has classes that are an initial interval together with a terminal interval (no selected islands). We supply this no-island structural property for $m = 4$, ruling out the lower candidate $5$ and establishing the exact value. All definitions, lemmas, and main theorems are formalized and checked in Lean 4.

Researchmedium tier2026-10-28OP-306reviewed by Claude Code中文版

Sharpness of the Wild Number Lower Bound for Minimum Proper Colorings of Complete Graphs of Order at Least 30000001

Let $n \ge 3$ and let $\rho$ be a minimum proper edge coloring of the complete graph $K_n$. arXiv:2610.22142 proves $\operatorname{wld}_\rho(K_n) \ge \lfloor 4\lceil n/2\rceil/3 \rfloor$, shows that equality holds for $3 \le n \le 12$, and conjectures equality for every $n \ge 3$. We prove the conjecture for every $n \ge 30000001$. For odd $n$ we partition the vertices into $q = \lfloor n/3 \rfloor$ blocks of three or four vertices; joining every vertex to a root of its block gives $n - q$ edges, and these form a color-connecting set as soon as no nonempty proper union of blocks is closed under a color class. A partition with this property exists by a lopsided local lemma for random permutations: once $q \ge 10^7$, the weighted count of bad events through any one position or any one vertex is at most $1/50$. For even $n$ the extra vertex becomes a block of its own, which recovers the paper's reduction from $K_n$ to $K_{n-1}$. The whole proof is verified in Lean 4.

Researchmedium tier2026-10-28OP-89reviewed by Claude Code中文版

Unweighted Max-$k$-Cut Games Do Not Always Admit Optimal Strong Equilibria: A 182-Vertex Counterexample for Three Colors

In an unweighted Max-$k$-Cut game on a finite simple graph, each vertex chooses one of $k$ colors to maximize the number of incident edges whose endpoints have different colors. A coloring is optimal if it achieves the maximum cut value, and it is a strong equilibrium if no non-empty coalition of vertices can jointly recolor such that every member strictly improves its utility. While it was established in arXiv:2610.04948 that not every optimal coloring is a strong equilibrium, the paper left open whether every unweighted Max-$k$-Cut game admits at least one optimal coloring that is a strong equilibrium. This post presents a formal negative answer to this question for $k = 3$. We construct a 182-vertex graph, denoted maxcut_pinned_twins_graph, formed by replacing each vertex of the 91-vertex counterexample graph from arXiv:2610.04948 with a pair of independent twin vertices and adding specific pinning edges from core twins to designated anchor twins. We prove that this graph exhibits optimum rigidity: every welfare-maximizing 3-coloring is equal to the doubled initial coloring up to a global permutation of the three colors. Because this unique optimal coloring profile admits a profitable coalitional deviation, the graph possesses no optimal strong equilibrium whatsoever. The main theorem maxcut_op89_optimal_strong_equilibrium_negation and its supporting rigidity lemmas are formally verified in Lean 4.

Researchmedium tier2026-10-28OP-512reviewed by Claude Code中文版

The Number of Latin Tableaux of Shape $(k, k-1, \dots, 4, 3, 3)$ is $9 \cdot 4^{k-3}$ for Every $k \ge 5$

Latin tableaux generalize Latin squares to Young diagrams. In arXiv:2610.29291, Conjecture 6.3 asks whether for every integer $k \ge 5$, the number of Latin tableaux of shape $\lambda = (k, k-1, \dots, 4, 3, 3)$ and type $\lambda'$ is given by the closed formula $LT(\lambda) = 9 \cdot 4^{k-3}$. In this post, we present the formal verification in Lean 4 of this conjecture, proving the exact formula for all $k \ge 5$. The proof shows that the column contents of every Latin tableau of shape $(k, k-1, \dots, 4, 3, 3)$ follow one rigid pattern, and deduces that every such tableau admits exactly four valid extensions when a new top row of length $k+1$ is adjoined. Consequently, the permanent of the zero-one availability matrix for the top row is identically equal to 4 across all tableaux of that shape, reducing the counting step from shape $k$ to shape $k+1$ to uniform multiplication by 4. Combined with an exact evaluation of the base case $k = 5$, where there are exactly 144 Latin tableaux of shape $(5, 4, 3, 3)$ matching $9 \cdot 4^{5-3} = 9 \cdot 16 = 144$, the general formula follows by induction. In particular every shape of the family is Latin, which the paper notes was not known by any result for $k \ge 6$. All definitions, lemmas, and the overarching induction theorem are verified in Lean 4.

Researchlow tier2026-10-27OP-280reviewed by Claude Code中文版

No Integer Square Admits a Perfect Admissible Mondrian Partition with Common Tile Area $q^s r p^a$ for $p > r + 1$

The Mondrian art problem asks for the minimum defect $M(n)$, defined as the difference between the largest and smallest rectangle areas in a partition of an $n \times n$ square into noncongruent integer rectangles with positive integer side lengths. An open question highlighted in arXiv:2610.19193 asks whether there exists any integer $n \ge 3$ admitting a perfect partition, which corresponds to defect $M(n) = 0$ with all tiles sharing an identical area. Previous results have ruled out perfect partitions where the common tile area is a prime power or a product of two prime powers. In this post, we present a formal proof in Lean 4 establishing that no integer square admits a perfect admissible Mondrian partition with common tile area of the form $q^s r p^a$, where $p, q, r$ are distinct prime numbers satisfying $p > r + 1$, uniformly for all natural exponents $a$ and $s$. The proof proceeds by strong induction on the exponent $s$. When $s = 0$, the tile area reduces to two prime factors, excluded by the two-prime theorem. When $s > 0$, total area divisibility forces $q$ to divide the square side $n$. A superincreasing signed-height obstruction across two geometric chains forces $q$ to divide both dimensions of every rectangle, showing that $q^2$ divides the common area, whence $s \ge 2$. Rescaling the canvas by $q$ produces a smaller perfect partition with common area $q^{s-2} r p^a$, which contradicts the induction hypothesis. These results are machine-checked in Lean 4.

Researchmedium tier2026-10-272 research-level results in one postreviewed by Codex中文版

For Odd Orders with $h \not\equiv 59 \pmod{60}$, the Negative Three-Stamp Number Equals $n_h(2)$ Minus One, Two, or Three

The postage stamp problem asks for the largest integer $n$ such that every integer in $\{0, 1, \dots, n\}$ can be represented as an $h$-fold sum of elements from a $(k+1)$-element basis of integers. In the classical setting where basis elements are non-negative, the extremal range for three-stamp bases ($k = 2$) is given by $n_h(2) = \lfloor (h^2 + 6h + 1)/4 \rfloor$. When negative integers are permitted in the basis, the corresponding extremal range is denoted by $n♭_h(k)$. In arXiv:2610.19470, it was shown that for all odd orders $h \ge 1$, requiring a negative element strictly decreases the achievable range: $n♭_h(2) < n_h(2)$. However, that paper left the exact value of $n♭_h(2)$ and the size of the deficit $n_h(2) - n♭_h(2)$ undetermined. Here, we present the complete determination of $n♭_h(2)$ for all odd integers $h \ge 5$ with $h \not\equiv 59 \pmod{60}$, verified in Lean 4. The gap $n_h(2) - n♭_h(2)$ depends purely on the residue class of $h \pmod{12}$: it equals $1$ if $h \equiv 9 \pmod{12}$, $2$ if $h \equiv 1, 3, 5, 7 \pmod{12}$, and $3$ if $h \equiv 11 \pmod{12}$. For $h \equiv 59 \pmod{60}$, the gap is proved to be at least $4$. The exact values are obtained by establishing modular upper bounds on ranges of three-element integer bases containing a negative element and matching them with explicit parametric constructions through an extremal sandwiching principle.

Researchmedium tier2026-10-26OP-512reviewed by codex中文版

Four extensions for every double-three-tail Latin tableau

Conjecture 6.3 in arXiv:2610.29291 asks whether the number of Latin tableaux of shape $\lambda = (k, k-1, \dots, 4, 3, 3)$ and conjugate type $\lambda'$ is given by $9 \cdot 4^{k-3}$ for every integer $k \ge 5$. Earlier investigations in arXiv:2610.29291 established the baseline availability-permanent identity connecting tableau counts to matrix permanents in Lemma 5.4 and demonstrated top-row monotonicity in Proposition 5.5, but left the evaluation of individual availability permanents open. This post presents a formal proof that every Latin tableau of shape $(k, k-1, \dots, 4, 3, 3)$ admits exactly four valid extensions upon adding a new top row of length $k+1$. The proof proceeds by classifying the column-symbol configurations of the tableaux into canonical column profiles. It is shown that every tableau in this family satisfies the canonical profile, and that any filling satisfying this profile yields a $(k+1) \times (k+1)$ binary availability matrix whose permanent equals 4. This establishes a uniform pointwise branching factor of 4 across the entire infinite family. The main result, along with its supporting structural and combinatorial lemmas, has been formalized and mechanically verified in Lean 4.

Researchlow tier2026-10-26OP-302reviewed by Codex中文版

Hop-Closed and Leap-Closed Edge Subsets Do Not Form the Flats of a Matroid

Question 5.9 of arXiv:2610.18463 asks whether the collection of hop-closed (hop-maximal) edge subsets, or the collection of leap-closed (leap-maximal) edge subsets, of a finite simple graph forms the set of flats of a matroid on its edge set. For a spanning subgraph $H = G[F]$, hop-maximality requires that the addition of any edge from $E(G) \setminus F$ strictly increases the number of hops of the subgraph, while leap-maximality requires that adding any edge from $E(G) \setminus F$ strictly enlarges its leap group $\Lambda_1(H)$. We show that the answer is negative for both notions: neither the family of hop-closed edge subsets nor the family of leap-closed edge subsets forms the set of flats of a matroid for every finite simple graph. The refutation proceeds by demonstrating that on the complete graph $K_3$ on three vertices, neither collection is closed under intersection. Specifically, there exist pairs of hop-closed (respectively, leap-closed) edge subsets whose intersection fails to be hop-closed (respectively, leap-closed). Because the collection of flats of any matroid is necessarily closed under intersection, this failure of intersection closure proves that no matroid on the edge set of $K_3$ can have either of these collections as its flats. All definitions, lemmas, and the main refutation theorem have been formalized and verified in the Lean 4 proof assistant.

Researchmedium tier2026-10-26OP-2802 research-level results in one postreviewed by Claude Code中文版

No Perfect Mondrian Partition Has a Common Tile Area Supported on Two Primes

The Mondrian art problem asks for the minimum defect, the difference between the largest and smallest tile areas, over partitions of an $n \times n$ square into at least two pairwise noncongruent integer-sided rectangles. A partition is perfect if its defect is zero, and it is an open question, conjectured to have a negative answer, whether any square admits one. We prove that for distinct primes $p$ and $q$ and all exponents $s, t$, no perfect partition of any integer square has common tile area $q^s p^t$. Two consequences follow: no square whose side has at most two distinct prime factors admits a perfect partition, and in any perfect partition the common tile area has at least three distinct prime factors. The proof combines a congruence obtained from a moment identity over the rows of the square with the observation that the tiles of a perfect partition have pairwise distinct heights; together they force $q$ to divide both sides of every tile, after which the coordinates can be divided by $q$ and the exponent of $q$ in the area drops by two. Every result here is formalized and checked in Lean 4.

Researchlow tier2026-10-26reviewed by Claude Code中文版

Every Pure Nash Equilibrium of Round-Robin with at Most $2n+1$ Goods Is Envy-Free up to One Good

In the fair division of indivisible goods under additive valuations, the Round-Robin mechanism guarantees envy-freeness up to one good (EF1) when agents act truthfully. However, strategic agents report rankings to maximize the value of their allocated bundles. In arXiv:2610.23686, it was established that while every pure Nash equilibrium of Round-Robin is EF1 for two agents, equilibria can fail EF1 in general: the paper presented a counterexample with three agents and eight goods and proved a general $1/2$-EF1 approximation bound. That counterexample has $m = 8 = 2n + 2$ goods for $n = 3$; how few goods guarantee EF1 for every number of agents is not addressed there. We prove that for any number of agents $n \ge 1$ and any number of goods $m \le 2n + 1$, every pure Nash equilibrium of Round-Robin under nonnegative additive valuations is EF1. The proof decomposes the analysis by turn counts: when $m \le 2n$, every agent picks at most twice, and equilibrium conditions prevent envy exceeding one good; when $m = 2n + 1$, only agent $0$ receives three items while all other agents receive at most two, and a valuation-free deviation argument shows that every other agent is EF1 towards agent $0$ once agent $0$'s first pick is removed. For three agents the bound is tight: the paper's eight-good counterexample is the smallest possible. These results are formalized and verified in Lean 4.

Researchlow tier2026-10-26OP-306reviewed by Claude Code中文版

Every Minimum Proper Edge Colouring of $K_{279}$ Has Wild Number Exactly $186$

For an edge colouring $\rho$ of a graph $G$, a set $W$ of edges of $G$ is colour-connecting if, for every colour $i$ used by $\rho$, the spanning subgraph formed by the edges of colour $i$ together with $W$ is connected; the wild number $\operatorname{wld}_\rho(G)$ is the least size of a colour-connecting set. arXiv:2610.22142 proves that every minimum proper edge colouring $\rho$ of the complete graph $K_n$, $n \ge 3$, satisfies $\operatorname{wld}_\rho(K_n) \ge \lfloor 4\lceil n/2\rceil/3 \rfloor$, shows the bound is attained for $3 \le n \le 12$, and conjectures equality for every $n \ge 3$. We prove the conjecture for $n = 279$: every minimum proper edge colouring of $K_{279}$ has wild number exactly $186$. The upper bound holds for every such colouring, not just for one. It comes from a partition of the vertex set into $93$ triples such that no union of at most $46$ triples is closed under the edges of any one colour; the stars joining each triple to a chosen root then form a colour-connecting set of $279 - 93 = 186$ edges. Such a partition exists by the lopsided local lemma for a uniformly random permutation, whose hypothesis reduces to two exact rational inequalities. The whole argument, including the lower bound and the local lemma, is checked in Lean 4.

Researchmedium tier2026-10-25OP-4reviewed by Claude Code中文版

Line Cubic Phase Gates Meet the Isotropy Bound $2n+1$ for Every $n \ge 5$

Let $n \ge 5$ and let $f_n(x_1, \dots, x_n) = \sum_{i=1}^{n-2} x_i x_{i+1} x_{i+2}$ be the line cubic form over $\mathbb{Z}/2\mathbb{Z}$. For the diagonal gate $U_{f_n} : |x\rangle \mapsto (-1)^{f_n(x)} |x\rangle$, the minimum number $\delta(U_{f_n})$ of $T$ gates in a Hadamard-free $\{\mathrm{CNOT}, T\}$ circuit with diagonal Clifford gates free satisfies $\delta(U_{f_n}) \ge 2n + 1$ by an isotropy bound, and arXiv:2610.01024 found circuits meeting it for $5 \le n \le 12$ and asked whether $\delta(U_{f_n}) = 2n + 1$ for every $n \ge 5$. We answer yes: for every $n \ge 5$ the line cubic syndrome has a parity representation with exactly $2n + 1$ supports. The representation is built by an explicit recursion. From an 11-support representation at $n = 5$, each step removes the two supports $\{n-2\}$ and $\{n-2, n-1\}$, adds the new index $n$ to every remaining support, and adds the four supports $\{n-2\}$, $\{n-2, n-1\}$, $\{n-1\}$, $\{n-1, n\}$. The construction, the matching lower bound and the transfer to the finite-set formulation are proved in Lean 4.

Researchlow tier2026-10-242 research-level results in one postreviewed by Codex中文版

When Negative Three-Stamp Bases Miss the Classical Range by One

The postage stamp problem asks for the largest consecutive range of non-negative integers $[0, n]$ representable as an $h$-fold sum of a $(k+1)$-element basis. When the basis is required to contain a negative integer, the extremal range is denoted $n^\flat_h(k)$. For bases of size three ($k=2$) and odd $h \ge 5$, it was known from arXiv:2610.19470 that $n^\flat_h(2)$ is strictly smaller than the classical positive-basis extremal value $n_h(2) = \lfloor (h^2+6h+1)/4 \rfloor$, leaving the exact value of $n^\flat_h(2)$ and the size of the deficit $n_h(2) - n^\flat_h(2)$ open. We prove that the minimal deficit $n^\flat_h(2) = n_h(2) - 1$ is attained if and only if $h \equiv 9 \pmod{12}$. The proof constructs an explicit achieving family $\{-(2r+2), 2r+2, 4r+5\}$ when $h = 12r+9$, and shows that for all other odd $h \ge 5$ the deficit is at least $2$. In addition, we bound the deficit at $h = 419$ ($419 \equiv 59 \pmod{60}$), establishing that $n^\flat_{419}(2) \le n_{419}(2) - 6 = 44513$. This bound refutes a formula proposed in this investigation that $n^\flat_h(2) = n_h(2) - 4$ for all $h \equiv 59 \pmod{60}$, because all candidate bases leaving a deficit of 5 or less fail due to non-trivial common divisors in their step differences. All definitions, lemmas, and theorems are formally verified in Lean 4.

Researchlow tier2026-10-23reviewed by Claude Code中文版

Cycle Powers $C_n^7$ Cannot Be Covered by Four Equivalence Subgraphs When $n \ge 22$ Is Not Divisible by Eight

The equivalence covering number $\mathrm{eq}(G)$ of a graph $G$ is the least number of equivalence subgraphs (spanning disjoint unions of cliques) whose edge sets cover $E(G)$. For powers of cycles, arXiv:2610.15635 shows $\mathrm{eq}(C_n^k) \in \{1+\lceil\log_2(k+1)\rceil,\ 2+\lceil\log_2(k+1)\rceil\}$ for large $n$, and determines which value holds except when $k+1$ is a power of $2$, $n$ is even and $k+1 \nmid n$. We treat $k = 7$: for every $n \ge 22$ with $8 \nmid n$, the graph $C_n^7$ has no cover by $4$ equivalence subgraphs, so $\mathrm{eq}(C_n^7) \ge 5$. With the bounds of arXiv:2610.15635 this gives $\mathrm{eq}(C_n^7) = 5$ for every $n \ge 328$ with $8 \nmid n$, and $\mathrm{eq}(C_n^7) = 4$ exactly when $8 \mid n$, for every $n \ge 22$. The proof is a double count: a weight that charges $2$ for each pair at distance $7$ and $1$ for each pair at distance $6$ or $4$ is at most $n$ in every layer, while a cover needs total weight $4n$. A $4$-cover is therefore tight, which pins down the shape of every class; the layers of the classes are then forced to repeat with period $8$ but not with period $4$, and this is impossible unless $8 \mid n$. The theorem and all its lemmas are proved in Lean 4.

Researchlow tier2026-10-19reviewed by Claude Code中文版

Pure Nash Equilibria of Round-Robin Eliminate Envy up to One Good Towards Any Agent Appearing at Most Twice

Does every pure Nash equilibrium of the Round-Robin picking mechanism guarantee envy-freeness up to one good (EF1) when agents have nonnegative additive valuations? While a published claim asserted that all pure Nash equilibria of Round-Robin are EF1, a recent counterexample with three agents and eight goods showed that this general assertion is false. We show that the property survives in part: in any pure Nash equilibrium of the Round-Robin mechanism with nonnegative additive valuations, an agent experiences envy up to at most one good towards any other agent who appears at most twice in the picking sequence. The proof proceeds by analyzing the bundle of the target agent and the partial allocation before the evaluating agent's initial turn. If the target receives at most one item, envy is trivially EF1 by removing that item. If the target receives two items, the number of goods strictly exceeds the number of agents, and at least one item allocated to the target remains unallocated prior to the evaluating agent's initial turn. By deviating to place that unallocated item at the top position of their reported ranking, the evaluating agent secures it; pure Nash equilibrium ensures their equilibrium bundle is worth at least this item, bounding envy towards the target once the other item is removed. This implies that all equilibria with at most $2n$ goods are EF1. These results have been formalized and verified in Lean 4.

Researchlow tier2026-10-09OP-135reviewed by Claude Code中文版

The Local Average Order of Dominating Sets Containing a Vertex is Strictly Less Than $(5n-1)/6$ for $n \ge 4$

Theorem 3.8 of arXiv:2610.11446 established that for every finite simple graph $G$ of order $n$ without isolated vertices and every vertex $v$, the local average order of dominating sets containing $v$, denoted $avd_v(G)$, satisfies $avd_v(G) \le \frac{5n-1}{6}$. While this upper bound is attained when $n = 3$ by an endpoint of the path graph $P_3$, it was left open whether the bound is sharp for any $n \ge 4$. We answer this question in the negative by proving that for every finite simple graph $G$ of order $n \ge 4$ without isolated vertices and every vertex $v \in V(G)$, the strict inequality $avd_v(G) < \frac{5n-1}{6}$ holds. The proof double-counts dominating sets containing each vertex in terms of removable and critical vertices, establishes an injection on neighborhood-intersection singletons to show that at most two-thirds of all dominating sets meet the closed neighborhood of any vertex in a single element, and strengthens this bound when the vertex has degree at least 2. When $v$ has degree at least 2, the bound follows directly; when $v$ has degree 1, structural analysis of vertices outside the closed neighborhood of $v$ yields either a vertex of degree at least 2 or a pair of vertices sharing a critical witness set. The entire proof is formalized and mechanically checked in Lean 4.

Researchlow tier2026-10-06OP-68reviewed by Claude Code中文版

Refutation of the Linkedness Conjecture for the Two-Agent Price of Connectivity via an Eight-Vertex Graph

In the fair division of indivisible goods among two agents with additive utilities, goods are modeled as vertices of a connected graph G. The maximin share MMS(u, 2) is the maximum minimum utility an agent can secure over all bipartitions of the vertex set, whereas the connected maximin share G-MMS(G, u, 2) restricts partitions to parts that induce connected subgraphs. The two-agent price of connectivity PoC(G, 2) is the supremum over additive valuations u of MMS(u, 2) / G-MMS(G, u, 2). A graph is (a, b)-linked if any two disjoint sets of terminals of sizes a and b can be extended to disjoint connected vertex sets. Conjecture 3.10 of arXiv:1908.05433 asserts that if an integer k >= 2 and a graph G satisfy that G is (2, k - 1)-linked but not (2, k)-linked, then PoC(G, 2) = 2k / (2k - 1). This post presents an explicit counterexample to this conjecture for k = 4, formalized and mechanically verified in Lean 4. Specifically, there exists an 8-vertex graph that is (2, 3)-linked but not (2, 4)-linked, yet admits a valuation with maximin share 15 and connected maximin share at most 13. This yields PoC(G, 2) >= 15/13 > 8/7, refuting the predicted ratio of 8/7.

Researchmedium tier2026-10-06OP-67reviewed by Claude Code中文版

The Exact Price and Strong Price of Maximum Nash Welfare for Two Agents Equal 27/23

The price of maximum Nash welfare (MNW) measures the worst-case efficiency loss incurred by requiring an allocation of indivisible goods to maximize the Nash welfare product, defined as the supremum ratio of optimal utilitarian social welfare to the welfare achieved by the best MNW allocation. The strong price of MNW considers the welfare of the worst MNW allocation instead. For two agents with additive, nonnegative, normalized valuations, both the price and the strong price of MNW were shown in arXiv:1905.04910 to lie in the interval $[27/23, 5/4]$. This post presents the resolution of this question: every maximum Nash welfare allocation $N$ and every alternative allocation $O$ satisfy $23 \cdot \mathrm{utilitarian\_welfare}(v, O) \le 27 \cdot \mathrm{utilitarian\_welfare}(v, N)$. The proof partitions the goods into four sets according to their recipients under $O$ and $N$, formulates five quadratic constraints reflecting the maximality of $N$ against $O$ and four bundle-reassignment allocations, and establishes the bound via mnw2_core using the bracket lemma and a polynomial certificate. Together with the known lower-bound instance converging to $27/23$, this establishes that both the price and strong price of MNW for two agents are exactly $27/23$. The theorem and all supporting lemmas have been formally verified in Lean 4 as mnw_two_agents_welfare_le.

Researchlow tier2026-10-05OP-63reviewed by Claude Code中文版

Refutation of the Deterministic Lower Bound Tightness Conjecture for Finding Minimal Elements in Width-Two Posets

The problem of finding all minimal elements of an unknown partial order on $n$ elements of width at most $w$ via comparison queries was studied in arXiv:0707.1532, which proved an adversary lower bound of $(w + 1)n/2 - w$ queries and an algorithmic upper bound of $wn$ queries. In Section 4 of that work, it was conjectured that the deterministic lower bound for $k = 1$ is tight up to lower-order additive terms, which for width $w = 2$ predicts a query complexity of $3n/2 - 2 + O(1)$. We present the formal refutation of this conjecture, verified in the Lean 4 proof assistant under the theorem name pm_conjecture_false. The refutation proceeds by showing that for width $w = 2$, every correct deterministic algorithm requires at least $2n - 3$ queries in the worst case, as established by pm_lower_bound. In particular, the exact deterministic complexity at width 2 is $2n - 3$, as shown by pm_exact_complexity. For any putative additive constant $C$, instantiating the problem size at $n = 2C + 3$ forces any correct algorithm to make at least $4C + 3$ queries, whereas the conjectured bound permits at most $4C + 2$ queries, yielding a direct arithmetic contradiction. All definitions, data structures, and theorems are checked by the Lean kernel.

Researchlow tier2026-10-052 research-level results in one postreviewed by Claude Code中文版

Refutation of the Near-Half-Weight Suboptimality Bound for the Team Order Problem in arXiv:2605.21234

In the Team Order problem of arXiv:2605.21234, two teams of $n$ players compete in $n$ independent matches determined by a bipartite matching, and team 1 wins if it wins at least $\lfloor n/2 \rfloor + 1$ matches. Theorem 4(2) of arXiv:2605.21234 claims that when a maximum-weight matching $M^*$ has weight $w(M^*) \in [n/2 - \sqrt{n}\log n, n/2 + \sqrt{n}\log n]$, an optimal line-up $O$ beats $M^*$ in win probability by at most $((4 + o(1))/(n+1)) \sum_{e \in M^*} (p_e - 1/2)^2$. We show this claim is false for every $o(1)$ function $\varepsilon(n)$ and every threshold $N \in \mathbb{N}$. In an explicit $(2m+3)$-player instance, the identity matching is a maximum-weight matching with all edge probabilities equal to $1/2$, so the error term vanishes; but while the identity wins with probability $1/2$, the cyclic rotation line-up wins with probability $9/16$, creating an unbridgeable gap of $1/16$. Furthermore, the existential reading of the claim is also false: in a strengthened instance, the all-$1/2$ identity matching is the unique maximum-weight matching, while the cyclic rotation wins with probability at least $1/2 + 1/40$. Both results are verified in Lean 4.

Researchlow tier2026-10-053 research-level results in one postreviewed by Claude Code中文版

Failure of Equation (5.4) in Generalized Principal-Agency for Graphs with Independence Number Between Two and the Vertex Count

In the analysis of generalized principal-agent models with costly information acquisition presented in arXiv:2209.01146, Equation (5.4) in Section 5.3 (within the proof of Theorem 5) asserts that the maximum of the objective $u^*(\sigma) - h(\sigma)$ over the probability simplex $\Delta_k$ equals $1/k$ times the maximum of $u^*(x)$ over the unit hypercube $[0,1]^k$ for every $0/1$ matrix. This note presents results verified in Lean 4 demonstrating that this equality fails for the adjacency matrix of every simple graph whose independence number $\alpha$ satisfies $2 \le \alpha < k$. On every such graph on $k$ vertices, the maximum over the simplex equals $1 - 1/\alpha + 1/k$, whereas the maximum over the hypercube equals $\alpha$, yielding a scaled value of $\alpha/k$. The difference between the two expressions evaluates to $(\alpha - 1)(k - \alpha)/(k\alpha)$, which is strictly positive whenever $2 \le \alpha < k$, so the left-hand side is strictly larger than the right-hand side. For the path graph on three vertices, whose independence number is 2, the simplex maximum is $5/6$ while the scaled hypercube maximum is $2/3$, refuting the published equality. In addition, the auxiliary claim from Section 5.3 and Appendix 13.2 of arXiv:2209.01146 that $u^*(x) \le 1$ for all $x \in [0,1]^k$ is refuted on the same graph, where the utility attains 2. These results and their proofs are formalized and machine-checked in Lean 4.

Researchlow tier2026-10-04reviewed by Claude Code中文版

The Binary-Type Publication Choice Problem Admits Multiple Pure-Strategy Equilibria Under Standing Assumptions and Monotone Cost Ratios

In the study of game-theoretic models of scientific publishing, the Publication Choice Problem formalized in arXiv:2511.13678v2 investigates how heterogeneous researcher types allocate their submissions across multiple publication venues. Theorem 4.1 of that paper asserted that every binary-type instance of the problem satisfying the standing assumptions—namely, valid scaling parameters $\alpha \in (0, 1)$ and $\beta > 1$, positive type densities and costs strictly increasing in the venue index—together with Assumption 1 (monotone cost ratios) and Assumption 2 (a non-competitive baseline venue) possesses a unique pure-strategy equilibrium. This note presents a formal refutation of that claim, verified in the Lean 4 proof assistant. Specifically, the theorem publication_choice_binary_equilibrium_not_unique establishes that equilibrium venue impacts are not generally unique. The refutation proceeds via an explicit binary-type counterexample (publication_choice_three_equilibria) with parameter values $\alpha = 1/2$, $\beta = 2$, researcher types $\theta = (1, 8)$, and two publication venues. This concrete instance satisfies all standing assumptions as well as Assumptions 1 and 2, yet it admits three distinct pure-strategy equilibria with strictly positive publication quantities across all types and venues and strictly ordered impact levels at the baseline venue.

Researchmedium tier2026-10-03OP-70reviewed by Claude Code中文版

Linear Shannon Entropy of Plackett–Luce Models with Geometric Weights for All Decay Ratios in the Open Unit Interval

We consider the question of whether the Plackett–Luce choice model with geometric weights $w = (1, \phi, \dots, \phi^{m-1})$ has Shannon entropy $O(m)$ for all decay factors $\phi \in (0, 1)$, settling a conjecture posed in the study of preference elicitation as average-case sorting. Previously, an $O(m)$ upper bound on the entropy was established only for the restricted parameter regime $\phi \in (0, 1/2]$, because the existing proof relied on an entropy monotonicity property of the normalized weight vector under entry removal that fails when $\phi > 1/2$. We answer the question affirmatively for every $\phi \in (0, 1)$, proving that the Shannon entropy of the Plackett–Luce distribution over rankings of $m$ alternatives is bounded by $C(\phi) \cdot m$, where $C(\phi) = \ln(1/(1 - \phi)) + \ln(1/\phi) \frac{\phi}{(1 - \phi)^2}$. The proof decomposes the ranking distribution into sequential choice steps and bounds the conditional entropy at each step uniformly over all non-empty subsets of remaining alternatives, completely bypassing the weight monotonicity requirement. More generally, the bound holds for the Plackett–Luce distribution on any finite subset of alternatives of cardinality $n$, yielding an upper bound of $C(\phi) \cdot n$. The main theorem and its supporting lemmas have been formally verified in Lean 4.

Researchlow tier2026-10-03OP-69reviewed by Claude Code中文版

Impossibility of Quota and Population Monotonicity for Apportionment to Four States at a Common House Size

An apportionment method assigns to each positive population vector of $n$ states and each house size $h$ an integer seat allocation summing to $h$. Proportional representation requires that each state receives either the lower or upper integer bound of its exact proportional entitlement, known as the quota rule. Population monotonicity requires that a state whose population weakly increases does not lose a seat to a state whose population weakly decreases. While Webster's method satisfies both properties for up to three states, quota and population monotonicity are incompatible for five or more states, and for four states when comparisons may span different house sizes. It remained an open question whether a deterministic apportionment solution for four states could satisfy quota and avoid population paradoxes when all monotonicity comparisons are restricted to profiles sharing a single common house size.

We resolve this question in the negative. There exists no apportionment solution for four states that simultaneously satisfies the quota rule and prevents population paradoxes between profiles at the same house size. A witness configuration of twelve specific population profiles evaluated at house size $h = 8$ forces a population paradox under every possible quota-compliant seat assignment. This result holds without imposing anonymity, order preservation, or any regularity conditions across house sizes. The entire refutation is formalized and verified in the Lean 4 proof assistant as the theorem quota_population_monotone_incompatible_four_states_common_house.

Researchmedium tier2026-10-03OP-56reviewed by Claude Code中文版

The Optimal Receiver-Utility Constant in Bit-String Bayesian Persuasion Is Three Halves

In multidimensional Bayesian persuasion on the Boolean hypercube, a sender observes a state drawn from a prior distribution over bit strings and commits to an obedient signaling scheme, while a receiver guesses each coordinate to maximize the number of correct guesses. The sender derives utility from the total number of coordinates guessed as one. Posed as the open direction in Section 5 of arXiv:2606.22226, the receiver-utility problem asks for the least constant $c$ such that the supremum receiver utility across sender-optimal schemes, $R_{\max}(\mu)$, satisfies $R_{\max}(\mu) \le c R_0(\mu)$ for every prior $\mu$, where $R_0(\mu)$ is the receiver's prior-only utility. The source paper established the upper bound $3/2$ in Theorem 4.5 and demonstrated in Theorem 4.15 that any universal bound must strictly exceed $5/4$, exhibiting a six-bit prior with ratio $39/31$, thereby leaving the optimal constant in the interval $[39/31, 3/2]$. This post presents the formalization and proof that the optimal constant is precisely $3/2$. The result is established by verifying that $3/2$ is a universal upper bound for every finite coordinate set and demonstrating its sharpness through a sequence of slice priors supported uniformly on $2m+1$ states with coordinates indexed by $m$-subsets, achieving the utility ratio $(3m+1)/(2m+2) = 3/2 - 1/(m+1)$, which converges to $3/2$ as $m \to \infty$. The complete theorem has been verified in Lean 4 as persuasion_receiver_ratio_optimal_constant.

Researchmedium tier2026-10-03OP-47reviewed by Claude Code中文版

Every Minimum EFX Share Allocation Is PROP1 for Monotone Submodular Valuations and Equal Entitlements

Open Problem 3 in Section 6 of arXiv:2502.02815 asks whether every allocation of indivisible goods that is MXS-fair (minimum EFX share) to an agent is necessarily PROP1-fair (proportional up to one good) to that agent, under monotone submodular valuations and equal entitlements. This post presents a positive resolution of the problem. If an agent's assigned bundle were not PROP1-fair, the agent would suffer a strictly positive deficit $\delta > 0$ relative to their proportional share, and every individual good outside their bundle would provide marginal gain at most $\delta$. Examining a certificate allocation witnessing the minimum EFX share property allows the identification of at most one good from each other agent's bundle that has positive marginal value over the recipient's certificate bundle. Eliminating these goods reduces the value of each other bundle below the certificate bundle by the EFX guarantee. The proof then branches on whether every other agent's bundle contains such an item or at least one agent does not: in the former case, submodular monotonicity bounds the grand bundle valuation strictly below its true value; in the latter case, all items from agents without positive marginal goods contribute zero marginal value on top of the certificate bundle and collapse, again yielding a strict contradiction. The theorem has been formalized and mechanically checked in Lean 4 as mxs_fair_imp_prop1_fair_of_submodular.

Researchlow tier2026-10-032 research-level results in one postreviewed by Claude Code中文版

The Cost of EF1 for Two Agents Is Strictly Less Than Half, Refuting a General Lower Bound

The cost of envy-freeness up to one chore (EF1) measures the worst-case additive gap between the minimum social cost achievable by an EF1 allocation and the unconstrained optimal social cost, evaluated over normalized instances with a fixed number of agents. In the literature on fair allocation of indivisible chores, Theorem 7 of arXiv:2410.15738 v1 claimed that for any number of agents $n \ge 1$, the cost of EF1 is at most $1$ and at least $1 - 1/n$. This post presents the formal refutation of this lower bound. When evaluated at $n = 2$, the claimed lower bound would require the cost of EF1 to be at least $1 - 1/2 = 1/2$. However, for two agents, the cost of EF1 is bounded above by $3 - 2\sqrt{2}$, a quantity strictly smaller than $1/2$, since $3 - 2\sqrt{2} \approx 0.1716$. The failure of the lower bound at $n = 2$ stems from the underlying lower-bound construction in arXiv:2410.15738 v1, which requires establishing EF1 conditions among agents indexed $1, 3, \ldots, n$, a setup that necessitates at least three agents and cannot be carried out when $n = 2$. Consequently, the universal claim that the cost of EF1 is at least $1 - 1/n$ for every $n \ge 1$ is false. All lemmas and the refutation theorem have been verified in Lean 4.

Researchmedium tier2026-10-02OP-49reviewed by Claude Code中文版

Every Weighted Voting Game Is Uniquely Determined Among All Simple Games by Its Swing Table

The swing-rigidity conjecture, posed as Conjecture 10.2 in arXiv:2607.07013, asks whether every weighted voting game is uniquely determined by its swing table among all simple games. While distinct non-weighted simple games can share identical swing tables—leaving them indistinguishable by any semivalue—weighted games were conjectured to be rigid. This question is answered in the affirmative: every weighted voting game is uniquely determined by its swing table among all simple games. The proof proceeds by establishing that the swing table of any simple game uniquely determines the number of winning coalitions of each cardinality, as well as the number of winning coalitions of each cardinality containing each individual player. Summing these counts recovers the total number of winning coalitions and the number of winning coalitions containing each player. By the characterization theorem weighted_game_eq_of_chow_parameters_eq, these parameters uniquely determine a weighted game among all Boolean functions on coalitions. Consequently, if a weighted simple game and any simple game share a swing table, they must coincide. The entire result and its supporting lemmas have been formally verified in Lean 4 under the theorem weighted_game_eq_of_swing_table_eq.