This week settled several open problems across discrete mathematics and information theory. It was established that allowing negative denominations strictly increases the consecutive integers reachable by postage stamp combinations. In information theory, subadditivity of mutual information was refuted for Hellinger distance and quarter-power divergences. In graph theory, new findings classified when spectral bounds on clique numbers hold, answered questions about permutation groups generated by graph hops, and established exact covering numbers for powers of cycle graphs.
Covering all edges of a third-power cycle graph with equivalence relations requires 4 relations whenever the cycle length leaves remainder 2 upon division by 4.
A strong formula bounding the size of the largest fully connected subgraph from matrix eigenvalues holds for five-block graphs except on three infinite families.
Information about a source shared across 2 conditionally independent observations can strictly exceed the sum of the individual shared informations.
Lean accepted 360 new theorems this week, drawn from 38 papers and 16 topics. Of these, 22 are new here, 0 correct a published claim, 74 formalize a published result and 264 are helper lemmas. 83 statements posed this week are not yet proved. The reading covered 81 new papers. This report covers 11 results in 7 fields.
The story of the week
Negative stamp values expand the consecutive postage amounts 8 stamps can reach
Imagine a postal system where every parcel must carry an exact total value using at most 8 stamps from a fixed menu of 4 denominations, one of which can be 0. Mathematicians study how far an unbroken run of consecutive integer postage amounts can stretch before encountering a value that cannot be paid.
When all stamp denominations must be positive, an exhaustive search established that the longest possible consecutive run with 4 denominations covers every integer from 0 up to 89, achieved by denominations of 0, 1, 9, and 14. It was long believed that allowing negative denominations—effectively giving the recipient the ability to return change—could not increase this threshold in such small systems.
That expectation fails for 8 stamps. A newly verified construction shows that choosing the 4 denominations -4, 1, 13, and 14 forms an unbroken chain of valid sums reaching all the way to 99.
Allowing a single negative denomination provides extra flexibility that surpasses every purely positive collection of the same size, proving that negative entries strictly increase the span of 4-stamp sets.
Verified that negative denominations strictly improve 4-denomination postage stamp ranges at order 8, and checked lower bounds for zero-sum Davenport constants in planar integer boxes.
Proved
Four stamps with one negative value reach 99 consecutive postage amounts
Allowing one negative value among 4 stamp types lets 8 stamps reach more consecutive totals than any 4 positive stamp types.
Before
With 4 non-negative stamp denominations and at most 8 stamps, the maximum unbroken range of postage amounts starting from 0 was known to be 89.
Now
The set {-4, 1, 13, 14} forms an 8-basis for 99, proving that allowing a negative denomination strictly increases the maximal postage range from 89 to at least 99.
Why it matters
Disproves the intuition that positive denominations are always optimal for small stamp collections, demonstrating the advantage of negative values.
The idea
Evaluates the reachable integers of {-4, 1, 13, 14} and shows every integer from 0 to 99 is an 8-fold sum of its elements.
postage_stamp_number_three_eight_eqThe classical postage stamp number with four stamps (one of them 0) and h = 8: n_8(3) = 89, attained by {0, 1, 9, 14}.
Davenport constant of two-dimensional integer boxes bounded via minimal zero sums
Long sequences in two-dimensional integer grids can avoid having sub-sequences that sum to zero up to a precise length.
Before
The maximal length of zero-sum-free sequences in planar integer boxes was conjectured to be governed by the smallest prime not dividing the box radius.
What is checked
arXiv:2610.16562 shows the Davenport constant of the box ⟦-m, m⟧² is at least 4m² - q(m), where q(m) is the smallest prime not dividing m; Lean now checks the proof.
Why it matters
Establishes the exact lower bound for zero-sum sequences in planar boxes by verifying minimality of the extremal sequence.
The idea
Constructs an explicit zero-sum sequence on 3 vectors and proves that no non-empty proper sub-sequence sums to zero.
int_box_extremal_sequence_countsIf integers A, B, C with 0 ≤ C ≤ M(2M−1) satisfy A·(M, M) + B·(−M, M−1) + C·(M−Q, −M) = 0, where M ≥ 2, gcd(M, Q) = 1 and gcd(2M−1, 2M−Q)…
Settled the equivalence covering number of cycle cubes for lengths congruent to 2 modulo 4, and formalized bounded-defect Mondrian partitions.
Proved
Equivalence covering number of cycle cubes equals 4 when length is 2 modulo 4
Covering all edges of a third-power cycle graph with equivalence relations requires 4 relations whenever the cycle length leaves remainder 2 upon division by 4.
Before
For cycle cubes of even length not divisible by 4, previous work left the equivalence covering number open between 3 and 4.
Now
For every n ≥ 10 with n ≡ 2 (mod 4), the equivalence covering number of the cube of the n-cycle is exactly 4.
Why it matters
Settles the first open family of the cycle-power covering problem, showing the lower bound of 4 is tight.
The idea
Proves that any 3-cover forces a rigid periodic chord structure whose cycle count requires 4 to divide the vertex number.
Seven-rectangle Mondrian partitions achieve defect 280 infinitely often
Tiling large squares with 7 unequal integer rectangles can keep the area difference between the largest and smallest tiles down to 280.
Before
It was unknown whether square Mondrian dissections using 7 pairwise non-congruent rectangles could achieve uniformly bounded area defects for arbitrarily large squares.
What is checked
arXiv:2610.19193 proves infinitely many squares admit 7-rectangle non-congruent dissections with defect 280, giving liminf defect at most 280; Lean now checks the proof.
Why it matters
Solves the bounded-defect question for 7-rectangle partitions by exhibiting an infinite family of square side lengths.
The idea
Parameterizes 7 non-congruent rectangles in a square of side 105q and relates their area defect to solutions of a Pell-type equation.
mondrian_seven_rects_partition_defectLet p, q be positive integers of the same parity with q < p < 7q, n = 105q and E = p² − 19q². The seven rectangles R₁, …, R₇ of (2)–(3)…
mondrian_seven_rects_defect_geWithin the seven-rectangle family, the defect is always at least 280 (in particular never 0): if p, q are odd then p² − 19q² ≡ 2 (mod 4),…
mondrian_liminf_min_defect_seven_leliminf_{n→∞} M₇(n) ≤ 280: infinitely many squares have a seven-rectangle Mondrian partition with defect at most 280.
Graph Theory & Graph Algorithms
Classified spectral clique bounds for five-block graphs, refuted conjectures on leap groups of kayak paddle graphs, and proved dijoin symmetry for acyclic tournaments.
Proved
Complete classification of strong spectral clique bounds for five-block graphs
A strong formula bounding the size of the largest fully connected subgraph from matrix eigenvalues holds for five-block graphs except on three infinite families.
Before
The strong spectral bound on clique numbers was proven for three-block and four-block graphs with isolated exceptions, but remained open for 5 blocks.
Now
For five-block graphs B_5, the strong spectral clique bound holds if and only if the first four block sizes do not form (1,1,1,1), (1,1,1,2), or (1,2,1,1).
Why it matters
Completely characterizes the domain of validity for the strengthened spectral clique bound on five-block graphs.
The idea
Computes the quotient matrix trace of squares in closed form and evaluates the algebraic gap against the clique bound.
Kayak paddle graphs with an even cycle never generate symmetric or alternating leap groups
When a graph formed by 2 loops connected by a path has an even loop, its step-permutations cannot generate the full permutation group.
Before
It was questioned whether all kayak paddle graphs admitting hops generate either the full symmetric group or the alternating group on their vertices.
Now
Every kayak paddle graph with an even cycle has leap group strictly smaller than the symmetric and alternating groups; the instance with cycle lengths 3 and 4 and path length 1 provides a 7-vertex counterexample.
Why it matters
Refutes the expectation that derangements of connected kayak paddle graphs generally generate the symmetric or alternating group.
The idea
Shows that any hop must map the vertex set of an even cycle to itself, trapping the generated group inside a proper set stabilizer.
kayak_paddle_leap_group_ne_of_even_cycleIf one of the two cycles of the kayak paddle graph KP(k, m, l) has even length, its leap group is neither the symmetric nor the…
Inversion values for tournament dijoins are symmetric when one side is transitive
Joining 2 tournaments with all edges directed from one to the other requires the same number of reversals to become acyclic regardless of joining order if one is transitive.
Before
Conjecture 4.1 of arXiv:2610.13798 posited that the inversion count of a dijoin of 2 tournaments is invariant under swapping the 2 components.
Now
The symmetry inv(D₁ → D₂) = inv(D₂ → D₁) holds whenever D₁ is acyclic, with both sides equal to the inversion count of D₂.
Why it matters
Confirms the symmetry conjecture for tournament dijoins in the broad case where at least one component has no directed cycles.
The idea
Squeezes the dijoin inversion count between the maximum and the sum of component inversion counts, which coincide when one is acyclic.
tournament_inversion_number_le_dijoinFor finite tournaments D₁, D₂: inv(D₁ → D₂) ≥ max(inv(D₁), inv(D₂)), since D₁ and D₂ are induced subtournaments of the dijoin and a…
Information Theory & Coding
Refuted subadditivity of mutual f-information for power divergences, constructing explicit counterexamples for the Hellinger divergence and quarter-power divergences.
Disproved
Mutual information subadditivity fails for Hellinger divergence and quarter-power divergences
Information about a source shared across 2 conditionally independent observations can strictly exceed the sum of the individual shared informations.
Before
It was conjectured that mutual f-information generated by power divergences satisfies subadditivity under Markov chains Y ← X → Z for all β between 0 and 1.
Now
Subadditivity fails for Hellinger mutual information at β = 1/2 on binary variables, and for the power divergence at β = 1/4 on ternary variables.
Why it matters
Disproves subadditivity for power divergences in the lower parameter range, restricting potential subadditivity to parameters above two-thirds.
The idea
Constructs explicit discrete channels where joint mutual information strictly exceeds the sum of marginal mutual informations.
Extended witness extraction for Schnorr protocols to affine-related public keys that share commitments, establishing explicit algebraic soundness bounds.
New result
Schnorr identification extracts witnesses from transcripts sharing commitments under affine-related keys
Secret keys can be mathematically recovered if 2 digital proof transcripts reuse the same initial commitment across related keys.
Before
Schnorr witness extraction traditionally assumes 2 transcripts generated with the same public key and distinct challenges.
Now
A secret witness w₁ is efficiently extracted from 2 Schnorr transcripts with identical commitments under affine-related keys w₂ = α·w₁ + β whenever s₁ - α⁻¹·s₂ - α⁻¹·β·c₂ is invertible modulo q.
Why it matters
Proves soundness of Schnorr proofs under affine related-key attacks, showing shared commitments compromise security across distinct related keys.
The idea
Cross-multiplies verification equations to cancel the shared commitment and solves the resulting linear exponent equation modulo q.
schnorr_zpow_eq_pow_zmod_valLet G be a commutative group, q a prime, and g in G an element of order q. For any integer z, the integer power g^z equals g^(z.val) where…
schnorr_mem_zpowers_iff_exists_zmodLet G be a commutative group, q a prime, and g in G an element of order q. Any element x in the cyclic subgroup generated by g is of the…
Online Algorithms
Formalized the lower bound of k + 1/2 on the competitive ratio of deterministic deadline paging, confirming that deadlines strictly increase paging difficulty.
Formalized
Deterministic deadline paging competitive ratio is bounded below by k plus a half
Algorithms managing memory caches with deadlines cannot be better than k plus a half times the offline optimum.
Before
Competitive ratios for deterministic online paging with deadlines were known to exceed the classical bound k of standard paging.
What is checked
arXiv:2610.18767 proves that for cache size k and at least k + 2 pages, no deterministic online algorithm achieves competitive ratio strictly less than k + 1/2; Lean now checks the proof.
Why it matters
Establishes that the presence of deadlines strictly worsens the optimal competitive ratio of online paging from k to at least k + 1/2.
The idea
Constructs an adversarial request sequence with deadlines that forces excessive cache misses on any online strategy.
Formalized separation results showing that randomized mechanisms with subsidies can satisfy fairness simultaneously in expectation and ex post, even where pure allocations cannot.
Formalized
Best-of-both-worlds fair lotteries exist even when deterministic fair allocations do not
A lottery over item distributions can guarantee fairness both on average and in the worst case, even when no single item assignment achieves this.
Before
It was unknown whether randomized allocations could achieve best-of-both-worlds fairness when no single deterministic allocation is simultaneously EF1 and envy-freeable with subsidies.
What is checked
arXiv:2610.14994 proves that for 3 submodular agents and 4 items, no pure allocation is both EF1 and envy-freeable, yet a randomized lottery is; Lean now checks the proof.
Why it matters
Demonstrates the strict superiority of randomized mechanisms with subsidies over deterministic fair division under submodular valuations.
The idea
Verifies a concrete profile of 3 submodular agents over 4 items where every pure allocation fails one requirement while a mixture satisfies both.
Does the inversion count of a tournament dijoin satisfy symmetry for all pairs of finite tournaments?
Does the stacking pebbling number of every finite tree equal its explicit tree estimate?
Does Tuza's conjecture that the minimum triangle cover is at most twice the maximum packing hold for all finite graphs?
Is mutual f-information for power divergences subadditive under Markov chains for all parameter values from two-thirds to one?
Does the equivalence covering number of cycle powers equal m plus 2 for all even cycle lengths not divisible by 2^m?
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).
TCS
TCS: the mathematical study of discrete algorithms, complexity, and combinatorics.
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.