AFTD Auto-Formalizing Theoretical Domains

Weekly report · 2026-W43 · 19–25 Oct 2026

Minimal turn-taking failures, cycle power covering bounds, and negative stamp bases

Short version: 2 minFull report: 8 min中文版

The week in one minute

Key questions were settled across game theory, number theory, and graph algorithms. Strategic turn-taking among three participants was proved fair up to one item for seven items, showing that eight items is the minimal failure point. A problem on covering cycle powers by equivalence graphs was bounded for power seven. New gap and classification results settled the behavior of three-stamp bases with negative denominations, and line cubic syndrome representations were constructed uniformly for all dimensions.

  • 2 Proved
  • 2 Partial
  • 2 New result
  • 3 Formalized
  • 5 still open

Lean accepted 1074 new theorems this week, drawn from 90 papers and 23 topics. Of these, 33 are new here, 0 correct a published claim, 154 formalize a published result and 887 are helper lemmas. 6 are research-level results -- they lead the report. 768 statements posed this week are not yet proved. The reading covered 86 new papers. This report covers 9 results in 4 fields.

Research-level results

The story of the week

Strategic turn taking with three people remains fair up to seven items

When three people take turns selecting items from a shared pool, they often look ahead rather than simply grabbing the best available item. Economists study whether the resulting stable outcomes remain fair, in the sense that no person envies another once any single item is removed from the other person bundle.

Recent work showed that with eight items, strategic picking can indeed break this fairness guarantee, leaving an agent genuinely envious even after discounting the rival best item. That left open whether unfairness could appear with fewer items, or whether the eight-item failure was the earliest possible glitch.

A complete analysis now establishes that every stable outcome with three agents and seven items is fair up to one item. Because instances with six or fewer items were already known to be fair, eight items is the exact threshold where strategic turn-taking can produce an unfair allocation.

At a glance

Fair Division

A sharp threshold was established for strategic round-robin picking, proving that eight items is the minimal size for fairness failures with three players. The eight-item counterexample was also formally verified.

Proved

Round-Robin pure Nash equilibria are EF1 for three agents and seven goods

When three people take turns picking at most seven items, every stable strategic outcome leaves no one envious after removing one item.

Before

Strategic turn-taking with three agents was known to fail EF1 at eight goods, but whether smaller counterexamples existed remained open.

Now

For three agents with non-negative additive valuations and seven goods, every pure Nash equilibrium of Round-Robin is EF1, proving eight goods strictly minimal.

Why it matters
Closes the gap between the trivial six-good guarantee and the eight-good counterexample, establishing the exact boundary for fairness.
The idea
Every agent other than agent 0 picks at most twice, and deviation certificates prove that no agent envies agent 0.
2 supporting theorems

Formalized

Round-Robin pure Nash equilibrium can fail EF1 with three agents and eight goods

When three people take turns selecting from eight items, their strategic choices can lead to an outcome where someone remains envious even after removing one item.

Before

Whether strategic turn-taking with three agents always guarantees allocations that are fair up to one item was open.

What is checked

arXiv:2610.23686 shows that an eight-good instance with three agents admits a pure Nash equilibrium that is not EF1; Lean now checks the proof.

Why it matters
Establishes that the eight-good counterexample to EF1 in Round-Robin is verified.
1 supporting theorem

Quantum Computation

A uniform recursive construction resolved the general parity representation problem for the line cubic syndrome across all dimensions.

Proved

Line cubic syndrome has a parity representation of 2n plus 1 supports

A specific quantum gate simplification problem can always be solved using an exact number of components proportional to the input size.

Before

Explicit parity representations of size 2n + 1 for the line cubic syndrome were known only for dimensions up to n = 12.

Now

For every integer n ≥ 5, the line cubic syndrome admits a parity representation of exactly 2n + 1 supports.

Why it matters
Resolves the open problem from Appendix K.2 of arXiv:2610.01024 for all dimensions n ≥ 5.
The idea
Constructs an inductive extension that modifies boundary supports and adjoins the new coordinate to preserve all cubic moment invariants.
2 supporting theorems
  • line_cubic_boundary_extensionRemoving the two designated boundary supports, adjoining the new index to every other support and adding four boundary supports preserves…
  • line_cubic_nat_family_existsEvery n at least five admits a bounded natural-index support family of size 2n+1 with the required line cubic moments and the boundary…

Elementary Number Theory

The negative-allowed postage stamp problem for three stamps was completely classified for near-extremal gaps, settling the unit gap and refuting a conjectured gap of four at h = 419.

New result

Unit gap for negative-allowed three-stamp bases occurs exactly when h is 9 modulo 12

Allowing negative numbers in three-stamp collections produces a range just one below the classical maximum exactly when the stamp budget leaves remainder nine modulo twelve.

Before

Odd stamp counts were known to satisfy a strict inequality between negative-allowed and non-negative ranges, but the exact deficit remained open.

Now

For odd h ≥ 5, the negative-allowed three-stamp number misses the classical value by exactly one if and only if h ≡ 9 modulo 12.

Why it matters
Characterizes precisely when permitting negative denominations costs only a single integer in achievable range.
The idea
Proves matching upper bounds for all residue classes and constructs an explicit three-stamp basis achieving the bound for residue nine.
3 supporting theorems

New result

At h = 419 the negative-allowed three-stamp number misses the maximum by at least six

At a budget of 419 stamps, allowing negative values causes a drop of at least six integers, refuting a conjectured gap of four.

Before

For odd h ≡ 59 modulo 60, the negative-allowed three-stamp number was conjectured to drop by exactly four below the classical maximum.

Now

At h = 419, the negative-allowed three-stamp number is at most 44513, which is 6 below the classical maximum 44519, refuting the conjecture.

Why it matters
Refutes the conjectured drop of four, demonstrating that arithmetic constraints force larger gaps at specific moduli.
The idea
Analyzes the six candidate basis sets surviving range bounds and proves every candidate has non-coprime steps.
2 supporting theorems

Formalized

Cubic lower bounds established for Davenport constants of three-dimensional boxes

The maximum length of a minimal zero-sum sequence in a three-dimensional box grows cubically with the box radius.

Before

Lower bounds for minimal zero-sum sequences of support four in low-dimensional integer boxes were established in the literature.

What is checked

arXiv:2610.16562 proves that for odd m ≥ 2, the Davenport constant of [[-m,m]]³ with support four is at least 16m³ - 16m² + 10m - 2; Lean checks it.

Why it matters
Verifies the explicit algebraic construction for minimal zero-sum sequences in integer lattices.
The idea
Constructs an explicit sequence of four vectors with tailored multiplicities and checks zero-sum minimality.
2 supporting theorems

Graph Theory & Graph Algorithms

Cycle power covering was bounded for power seven. The wild number conjecture was verified for the complete graph on 279 vertices, and degree bounds for additive colorings were checked.

Partial

Seventh cycle power requires at least five equivalence subgraphs when eight does not divide n

Covering all connections in a circular network of reach seven requires at least five simple cluster graphs unless the network size divides by eight.

Before

The equivalence covering number of cycle powers was known when k+1 divides n, but the lower bound for power k = 7 in general remained open.

Now

For n ≥ 22 not divisible by 8, the cycle power C_n^7 cannot be covered by 4 equivalence subgraphs, proving that the equivalence covering number of C_n^7 is at least 5.

Why it matters
Settles the lower bound half of the open question for the first previously unsolved case k = 7.
The idea
Analyzes chord tightness of distances 7, 6, and 4 to prove the covering layers must alternate with strict eight-fold periodicity.
2 supporting theorems

Partial

Wild number of K_279 equals 186 for every minimum proper edge colouring

Every most efficient edge coloring of the complete network on 279 nodes can connect all colors using exactly 186 edges.

Before

The wild number formula for complete graphs had been proved only for orders between 3 and 12, remaining conjectural for all larger n.

Now

For every minimum proper edge colouring of K_279, the wild number is exactly 186 = ⌊4⌈279/2⌉/3⌋, confirming the conjecture for n = 279.

Why it matters
Extends the verified range of the wild number conjecture far beyond the small cases checked in arXiv:2610.22142.
The idea
Constructs a seal-free partition into 93 triples certified by a local-lemma rational mass bound.
2 supporting theorems

Formalized

Additive colorings exist within vertex degree plus initial positive weight bounds

Every graph can be assigned positive numbers so that adjacent vertices have different neighbor sums, without exceeding each vertex degree plus an initial weight.

Before

Bounds on additive chromatic numbers and neighbor-sum distinguishing colorings were established using the Combinatorial Nullstellensatz.

What is checked

arXiv:2610.30174 proves that every finite graph admits an additive coloring f satisfying a(v) ≤ f(v) ≤ a(v) + degree(v) for any positive weight function a; Lean checks the proof.

Why it matters
Formalizes an elementary and tight degree bound for additive chromatic numbers.
The idea
Applies an edge-tail orientation matching combined with polynomial non-vanishing over integer lists.
2 supporting theorems

Still open

Terms

EF1
Envy-free up to one item: any envy disappears once some single item is removed (a good from the envied bundle, or a chore from the envious agent's own).

Written by a model (gemini-3.8-flash) from the week's Lean-verified results. Every declaration named here was checked by Lean; this summary is a reading aid and is not itself machine-checked.