Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

FeeFrac arithmetic, Core's chunk-diagram comparison, and the cluster-mempool replacement check

Definition
BitcoinFeerateDiagram

by pitimespi · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

bitcoincluster-mempoolfeefracfeerate-diagramformal-verificationmathlibmempoolpolicyrbf

A transcription of the cluster mempool's replacement check over the replace-by-fee mission's BitcoinReplacement, at Bitcoin Core revision a773e1e, where it replaced BIP125 rule 3.

FeeFrac — a fee and a size (integers). IsEmpty, mul, mulFallback (the 32-bit split multiplication), div (round down or up), divFallback, ceilDiv, evaluateFee, evaluateFeeDown, evaluateFeeUp — Core's arithmetic, with both code paths. byRatioCmp a b — compare (a.fee · b.size) (b.fee · a.size), the ByRatio ordering; ratio a — fee / size in Q\mathbb{Q}Q.

PartialOrdering — less, equivalent, greater, unordered; boolCompare. sweep — the loop of CompareChunks, one equation per iteration over the two chunk lists with the accumulated (fee, size) of each and the two "better somewhere" flags; compareChunks c0 c1 — Core's CompareChunks. ImprovesFeerateDiagram old new — compareChunks new old = greater (policy/rbf.cpp).

diagram cs x — the feerate diagram as a function: the cumulative fee at cumulative size xxx, linear within each chunk and constant after the last; diagramFee, diagramSize — totals. SizesPos — every chunk has positive size; FeeratesNonIncreasing — chunk feerates in non-increasing order. Dominates c0 c1 — diagram c0 ≥ diagram c1 on [0,∞)[0, \infty)[0,∞); BetterSomewhere c0 c1 — strictly greater at some x≥0x \ge 0x≥0; StrictlyBetter — both.

Formalization Note. Imports Mathlib and the replacement mission. The chunk lists (the linearization of the affected clusters, txmempool.cpp/txgraph.cpp) are taken as input; fees and sizes are unbounded integers, so overflow is not modelled.

Definition code
import Mathlib
import Definitions.Def_BitcoinReplacement

/-!
# Bitcoin Core's feerate-diagram replacement check (`ImprovesFeerateDiagram`)

At bitcoin/bitcoin revision `a773e1e33b349dc819b5a0edc1c7a4839dc73b48` BIP125 rule 3
("the replacement pays a higher feerate than each directly conflicting transaction") is gone from
`policy/rbf.cpp`; it has been replaced by the cluster-mempool check

```cpp
std::optional<std::pair<DiagramCheckError, std::string>> ImprovesFeerateDiagram(CTxMemPool::ChangeSet& changeset)
{
    const auto chunk_results{changeset.CalculateChunksForRBF()};
    if (!chunk_results.has_value()) { return {DiagramCheckError::UNCALCULABLE, ...}; }
    if (!std::is_gt(CompareChunks(chunk_results.value().second, chunk_results.value().first))) {
        return {DiagramCheckError::FAILURE, "insufficient feerate: does not improve feerate diagram"};
    }
    return std::nullopt;
}
```
(`policy/rbf.cpp`, lines 127–140).  `CalculateChunksForRBF` (`txmempool.cpp` 1042–1051) returns
`TxGraph::GetMainStagingDiagrams()` (`txgraph.cpp` 2810–2834): `first` is the list of chunk
feerates (`FeeFrac`s) of every *main* cluster that the replacement touches, `second` the list of
chunk feerates of every *staging* cluster (the same transactions with the conflicts removed and the
replacement added), each list sorted by decreasing feerate (`ByRatioNegSize`).  The replacement is
accepted iff `CompareChunks(new, old)` is `std::partial_ordering::greater`.

This file transcribes

* `FeeFrac` (`util/feefrac.h`): a (fee, size) pair with `int64_t` fee and `int32_t` size, its `+`
  and `-`, the `ByRatio` feerate comparison by cross-multiplication, and the fee evaluation
  `EvaluateFee<RoundDown>` together with the `Mul`/`Div` and `MulFallback`/`DivFallback` helpers;
* `CompareChunks` (`util/feefrac.cpp`, lines 12–75): the sweep over the breakpoints of the two
  piecewise-linear diagrams, as a function on `List FeeFrac`;
* `ImprovesFeerateDiagram` as the predicate `CompareChunks new old = greater`;
* the mathematical object the sweep compares: the *diagram function* `diagram cs : ℚ → ℚ` of a chunk
  list, the piecewise-linear function through the cumulative (size, fee) points, extended
  horizontally to the right ("The implied diagram for each starts at (0, 0), then contains for each
  chunk the cumulative fee and size up to that chunk, and then extends infinitely to the right with
  a horizontal line", `util/feefrac.h`).

The chunk lists themselves (the output of cluster linearisation and chunking,
`ChunkLinearization` in `cluster_linearize.h`) are taken as *input*: nothing here models
clusters, dependencies or linearisations.  Machine-integer overflow is not modelled: all arithmetic
is in `ℤ`/`ℚ`, which is what the C++ computes under the documented preconditions
("the sum of the FeeFracs in either of the chunks' data set do not overflow").
-/

namespace BitcoinFeerateDiagram

/-- `struct FeeFrac { int64_t fee; int32_t size; }` (`util/feefrac.h`).  A fee and a size; "the size
of a FeeFrac cannot be zero unless the fee is also zero".  Modelled with unbounded integers. -/
structure FeeFrac where
  /-- `int64_t fee` (satoshi; may be negative, e.g. after `prioritisetransaction`). -/
  fee : ℤ
  /-- `int32_t size` (vbytes or weight units, depending on the tag). -/
  size : ℤ
  deriving DecidableEq, Repr

namespace FeeFrac

/-- `FeeFrac()` : the empty `FeeFrac` (fee 0, size 0), the initial value of `accum` in
`CompareChunks`. -/
instance : Zero FeeFrac := ⟨⟨0, 0⟩⟩

/-- `operator+(a, b) = {a.fee + b.fee, a.size + b.size}`. -/
instance : Add FeeFrac := ⟨fun a b => ⟨a.fee + b.fee, a.size + b.size⟩⟩

/-- `operator-(a, b) = {a.fee - b.fee, a.size - b.size}`. -/
instance : Sub FeeFrac := ⟨fun a b => ⟨a.fee - b.fee, a.size - b.size⟩⟩

/-- `IsEmpty()`: `size == 0`. -/
def IsEmpty (a : FeeFrac) : Prop := a.size = 0

/-- `FeeFrac::Mul(int64_t a, int32_t b)` (the `__int128` version): the exact product. -/
def mul (a b : ℤ) : ℤ := a * b

/-- `FeeFrac::MulFallback(int64_t a, int32_t b)`: the 32×64 signed product returned as a pair
`(high, low32)` whose value is `high * 2^32 + low32`:
```cpp
int64_t low = int64_t{static_cast<uint32_t>(a)} * b;
int64_t high = (a >> 32) * b;
return {high + (low >> 32), static_cast<uint32_t>(low)};
```
`static_cast<uint32_t>(x)` is `x mod 2^32` and the arithmetic shift `x >> 32` is
`⌊x / 2^32⌋`; in ℤ, `/` and `%` are floor division and nonnegative remainder, which is exactly this. -/
def mulFallback (a b : ℤ) : ℤ × ℤ :=
  let low := (a % 2 ^ 32) * b
  let high := (a / 2 ^ 32) * b
  (high + low / 2 ^ 32, low % 2 ^ 32)

/-- `FeeFrac::Div(__int128 n, int32_t d, bool round_down)`: C++ `/` and `%` truncate towards zero
(`Int.tdiv`, `Int.tmod`), then the quotient is corrected so that the result rounds towards
`-∞` (if `round_down`) or `+∞` (otherwise):
```cpp
int64_t quot = n / d;
int32_t mod = n % d;
return quot + ((mod > 0) - (mod && round_down));
```
Requires `d > 0`. -/
def div (n d : ℤ) (roundDown : Bool) : ℤ :=
  n.tdiv d + ((if 0 < n.tmod d then 1 else 0) - (if n.tmod d ≠ 0 ∧ roundDown then 1 else 0))

/-- `FeeFrac::DivFallback(std::pair<int64_t, uint32_t> n, int32_t d, bool round_down)`, the 96/32
division of the value `n.first * 2^32 + n.second` (as produced by `mulFallback`):
```cpp
int64_t quot_high = n.first / d;
int64_t n_low = ((n.first % d) << 32) + n.second;
int64_t quot_low = n_low / d;
int32_t mod_low = n_low % d;
quot_low += (mod_low > 0) - (mod_low && round_down);
return (quot_high << 32) + quot_low;
```
C++ `/`, `%` truncate towards zero; `<< 32` on a signed value is multiplication by `2^32`. -/
def divFallback (n : ℤ × ℤ) (d : ℤ) (roundDown : Bool) : ℤ :=
  let quotHigh := n.1.tdiv d
  let nLow := (n.1.tmod d) * 2 ^ 32 + n.2
  let quotLow := nLow.tdiv d
  let modLow := nLow.tmod d
  let quotLow' := quotLow + ((if 0 < modLow then 1 else 0) - (if modLow ≠ 0 ∧ roundDown then 1 else 0))
  quotHigh * 2 ^ 32 + quotLow'

/-- `CeilDiv(dividend, divisor)` (`util/overflow.h`, unsigned): `dividend / divisor + (dividend %
divisor != 0)`.  Stated on `ℤ` for nonnegative operands, where `/` and `%` agree with the unsigned
operations. -/
def ceilDiv (n d : ℤ) : ℤ := n / d + (if n % d ≠ 0 then 1 else 0)

/-- `FeeFrac::EvaluateFee<RoundDown>(int32_t at_size)` (`util/feefrac.h`): the fee for `at_size`
units at this object's feerate, `(fee * at_size) / size` rounded towards `-∞` (`RoundDown`) or
`+∞`.  Requires `size > 0` and `at_size ≥ 0`.
```cpp
if (fee >= 0 && fee < 0x200000000) [[likely]] {
    if constexpr (RoundDown) { return (uint64_t(fee) * at_size) / uint32_t(size); }
    else                     { return CeilDiv(uint64_t(fee) * at_size, uint32_t(size)); }
} else {
    return Div(Mul(fee, at_size), size, RoundDown);
}
```
In the first branch all operands are nonnegative, so the unsigned `uint64_t` operations are the
integer operations on `ℤ` (no overflow by the stated precondition). -/
def evaluateFee (f : FeeFrac) (atSize : ℤ) (roundDown : Bool) : ℤ :=
  if 0 ≤ f.fee ∧ f.fee < 2 ^ 33 then
    if roundDown then (f.fee * atSize) / f.size else ceilDiv (f.fee * atSize) f.size
  else div (mul f.fee atSize) f.size roundDown

/-- `EvaluateFeeDown(at_size) = EvaluateFee<true>(at_size)`. -/
def evaluateFeeDown (f : FeeFrac) (atSize : ℤ) : ℤ := evaluateFee f atSize true

/-- `EvaluateFeeUp(at_size) = EvaluateFee<false>(at_size)`. -/
def evaluateFeeUp (f : FeeFrac) (atSize : ℤ) : ℤ := evaluateFee f atSize false

/-- `ByRatio` comparison `operator<=>(ByRatio a, ByRatio b)`:
```cpp
auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
return cross_a <=> cross_b;
```
i.e. the feerates `a.fee / a.size` and `b.fee / b.size` compared by cross-multiplication, with no
rounding (`std::strong_ordering`, mapped to `Ordering`). -/
def byRatioCmp (a b : FeeFrac) : Ordering := compare (mul a.fee b.size) (mul b.fee a.size)

/-- The feerate of a `FeeFrac` as an exact rational number (`fee / size`). -/
def ratio (a : FeeFrac) : ℚ := (a.fee : ℚ) / (a.size : ℚ)

end FeeFrac

/-- `std::partial_ordering`, the result type of `CompareChunks`. -/
inductive PartialOrdering
  | less
  | equivalent
  | greater
  | unordered
  deriving DecidableEq, Repr

/-- `better_somewhere[0] <=> better_somewhere[1]` on `bool` (`false < true`), the final `return` of
`CompareChunks` (reached only when at most one of the two flags is set). -/
def boolCompare (b0 b1 : Bool) : PartialOrdering :=
  match b0, b1 with
  | false, false => .equivalent
  | false, true => .less
  | true, false => .greater
  | true, true => .equivalent

/-- The `do { … } while(true)` loop of `CompareChunks` (`util/feefrac.cpp`, lines 29–71), as a
function of its state: `rem0`, `rem1` are the unprocessed chunks of the two inputs
(`chunk[i][next_index[i]..]`), `acc0`, `acc1` the accumulated points `accum[i]`, and `b0`, `b1` the
flags `better_somewhere[i]`.  Each arm is one iteration:

* `done_0 && done_1` → `break`, then `return better_somewhere[0] <=> better_somewhere[1]`;
* exactly one side done → `unproc_side` is the other side, `P = next_point(unproc_side)`,
  `A = prev_point(!unproc_side)`, and `cmp = ByRatio{P - A} <=> ByRatio{FeeFrac(0, 1)}`
  ("act as if AB has slope tail_feerate(of 0)");
* both sides have points left → `unproc_side = next_point(0).size > next_point(1).size`,
  `B = next_point(!unproc_side)`, `cmp = ByRatio{P - A} <=> ByRatio{B - A}`, and if
  `B.size == P.size` the other side is advanced as well;

then `if (is_gt(cmp)) better_somewhere[unproc_side] = true; if (is_lt(cmp))
better_somewhere[!unproc_side] = true; advance(unproc_side); if (both flags) return unordered;`. -/
def sweep : List FeeFrac → List FeeFrac → FeeFrac → FeeFrac → Bool → Bool → PartialOrdering
  | [], [], _, _, b0, b1 => boolCompare b0 b1
  | c0 :: r0, [], acc0, acc1, b0, b1 =>
      -- done_1: unproc_side = 0, P = chunk[0][next] + accum[0], A = accum[1]
      let p := c0 + acc0
      let cmp := FeeFrac.byRatioCmp (p - acc1) ⟨0, 1⟩
      let b0' := b0 || (cmp == .gt)
      let b1' := b1 || (cmp == .lt)
      if b0' && b1' then .unordered else sweep r0 [] p acc1 b0' b1'
  | [], c1 :: r1, acc0, acc1, b0, b1 =>
      -- done_0: unproc_side = 1, P = chunk[1][next] + accum[1], A = accum[0]
      let p := c1 + acc1
      let cmp := FeeFrac.byRatioCmp (p - acc0) ⟨0, 1⟩
      let b1' := b1 || (cmp == .gt)
      let b0' := b0 || (cmp == .lt)
      if b0' && b1' then .unordered else sweep [] r1 acc0 p b0' b1'
  | c0 :: r0, c1 :: r1, acc0, acc1, b0, b1 =>
      let p0 := c0 + acc0
      let p1 := c1 + acc1
      if p0.size > p1.size then
        -- unproc_side = 1: P = p1, A = accum[0], B = p0 (B.size ≠ P.size here)
        let cmp := FeeFrac.byRatioCmp (p1 - acc0) (p0 - acc0)
        let b1' := b1 || (cmp == .gt)
        let b0' := b0 || (cmp == .lt)
        if b0' && b1' then .unordered else sweep (c0 :: r0) r1 acc0 p1 b0' b1'
      else
        -- unproc_side = 0: P = p0, A = accum[1], B = p1
        let cmp := FeeFrac.byRatioCmp (p0 - acc1) (p1 - acc1)
        let b0' := b0 || (cmp == .gt)
        let b1' := b1 || (cmp == .lt)
        if b0' && b1' then .unordered
        else if p1.size = p0.size then sweep r0 r1 p0 p1 b0' b1'   -- advance(!unproc_side) too
        else sweep r0 (c1 :: r1) p0 acc1 b0' b1'
  termination_by r0 r1 => r0.length + r1.length

/-- `CompareChunks(chunks0, chunks1)` (`util/feefrac.cpp`): compare the feerate diagrams implied by
two sorted chunk lists; `next_index = {0, 0}`, `accum = {FeeFrac(), FeeFrac()}`,
`better_somewhere = {false, false}`. -/
def compareChunks (chunks0 chunks1 : List FeeFrac) : PartialOrdering :=
  sweep chunks0 chunks1 0 0 false false

/-- `ImprovesFeerateDiagram` (`policy/rbf.cpp`): with `old` the main-mempool diagram
(`chunk_results.first`) and `new` the staging diagram (`chunk_results.second`), the replacement
passes iff `std::is_gt(CompareChunks(new, old))`, i.e. the new diagram is strictly greater. -/
def ImprovesFeerateDiagram (old new : List FeeFrac) : Prop :=
  compareChunks new old = .greater

/-- The feerate diagram of a chunk list as a function of cumulative size: it starts at `(0, 0)`,
is linear with slope `c.fee / c.size` across each chunk `c` in order, and is constant (the total
fee) beyond the total size.  (For the chunk lists produced by Core every chunk has positive size;
`diagram` is only meaningful under `SizesPos`.) -/
def diagram : List FeeFrac → ℚ → ℚ
  | [], _ => 0
  | c :: cs, x => if x ≤ c.size then (c.fee : ℚ) * x / c.size else c.fee + diagram cs (x - c.size)

/-- Total fee of a chunk list (the final height of its diagram). -/
def diagramFee (cs : List FeeFrac) : ℤ := (cs.map FeeFrac.fee).sum

/-- Total size of a chunk list (the last breakpoint of its diagram). -/
def diagramSize (cs : List FeeFrac) : ℤ := (cs.map FeeFrac.size).sum

/-- Every chunk has positive size (`Assume(slope_ap.size > 0)` in `CompareChunks`; true of every
chunk of a linearisation, since a chunk is a nonempty set of transactions of positive weight). -/
def SizesPos (cs : List FeeFrac) : Prop := ∀ c ∈ cs, 0 < c.size

/-- The chunks are listed in non-increasing feerate order (`ByRatio` comparison), as
`GetMainStagingDiagrams` sorts them. -/
def FeeratesNonIncreasing (cs : List FeeFrac) : Prop :=
  cs.IsChain fun a b => b.fee * a.size ≤ a.fee * b.size

/-- `Dominates c0 c1`: the diagram of `c0` lies (weakly) above the diagram of `c1` at every
nonnegative size. -/
def Dominates (c0 c1 : List FeeFrac) : Prop :=
  ∀ x : ℚ, 0 ≤ x → diagram c1 x ≤ diagram c0 x

/-- `BetterSomewhere c0 c1`: the diagram of `c0` lies strictly above that of `c1` at some
nonnegative size. -/
def BetterSomewhere (c0 c1 : List FeeFrac) : Prop :=
  ∃ x : ℚ, 0 ≤ x ∧ diagram c1 x < diagram c0 x

/-- `StrictlyBetter c0 c1`: `c0` dominates `c1` and is strictly better somewhere — the intended
meaning of `CompareChunks(c0, c1) == greater`. -/
def StrictlyBetter (c0 c1 : List FeeFrac) : Prop :=
  Dominates c0 c1 ∧ BetterSomewhere c0 c1

end BitcoinFeerateDiagram
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: util/feefrac.h (FeeFrac :20, MulFallback :25-30, DivFallback :40-59, Mul/Div :64-82, operator+/- :120-131, EvaluateFee :147-175, ByRatio :217-240), util/overflow.h (CeilDiv :70-74), util/feefrac.cpp (CompareChunks :12-75), policy/rbf.cpp (ImprovesFeerateDiagram :127-140, PaysForRBF :100-125): https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/util/feefrac.cpp; test vectors from src/test/rbf_tests.cpp (feerate_chunks_utilities) and src/test/feefrac_tests.cpp
Read-back

What the Lean code literally says, in plain math · claude-fable-5-1 (independent sub-agent, blind: Lean code + auditor instructions only)

Read-back: definitions of Def_BitcoinFeerateDiagram

All definitions live in a single namespace. The file imports the standard mathematics library and a companion file of replacement definitions (FeeRate, getFee, Tx, Replacement, totalFee, PaysForRBF), none of which are used by the definitions below. All arithmetic is in the unbounded integers Z\mathbb ZZ or the rationals Q\mathbb QQ.

Division conventions. Three kinds of division occur.

  • Default integer division n/dn \mathbin{/} dn/d with remainder n mod dn \bmod dnmodd (Euclidean convention). For d>0d > 0d>0: n/d=⌊n/d⌋n / d = \lfloor n/d \rfloorn/d=⌊n/d⌋ and n mod d=n−d⌊n/d⌋∈[0,d)n \bmod d = n - d\lfloor n/d \rfloor \in [0, d)nmodd=n−d⌊n/d⌋∈[0,d), also for negative nnn (e.g. −7/2=−4-7/2 = -4−7/2=−4, −7 mod 2=1-7 \bmod 2 = 1−7mod2=1). For d<0d < 0d<0: n/d=−⌊n/∣d∣⌋n / d = -\lfloor n/|d| \rfloorn/d=−⌊n/∣d∣⌋ and n mod d∈[0,∣d∣)n \bmod d \in [0, |d|)nmodd∈[0,∣d∣). For d=0d = 0d=0: n/0=0n / 0 = 0n/0=0 and n mod 0=nn \bmod 0 = nnmod0=n.
  • Truncated division tdiv⁡(n,d)\operatorname{tdiv}(n,d)tdiv(n,d) with remainder tmod⁡(n,d)=n−d⋅tdiv⁡(n,d)\operatorname{tmod}(n,d) = n - d\cdot\operatorname{tdiv}(n,d)tmod(n,d)=n−d⋅tdiv(n,d): the quotient is rounded toward zero, so the remainder is 000 or has the sign of nnn, with ∣tmod⁡(n,d)∣<∣d∣|\operatorname{tmod}(n,d)| < |d|∣tmod(n,d)∣<∣d∣ (e.g. tdiv⁡(−7,2)=−3\operatorname{tdiv}(-7,2) = -3tdiv(−7,2)=−3, tmod⁡(−7,2)=−1\operatorname{tmod}(-7,2) = -1tmod(−7,2)=−1). For d=0d = 0d=0: tdiv⁡(n,0)=0\operatorname{tdiv}(n,0) = 0tdiv(n,0)=0, tmod⁡(n,0)=n\operatorname{tmod}(n,0) = ntmod(n,0)=n.
  • Rational division in Q\mathbb QQ, with the convention q/0=0q / 0 = 0q/0=0. For q∈Qq \in \mathbb Qq∈Q, ⌊q⌋\lfloor q \rfloor⌊q⌋ is the greatest integer ≤q\le q≤q and ⌈q⌉\lceil q \rceil⌈q⌉ the least integer ≥q\ge q≥q.

Below, [P][P][P] denotes 111 if the condition PPP holds and 000 otherwise.

The definitions, in order

1. FeeFrac. A FeeFrac is a structure with two fields, fee(X)∈Z\mathrm{fee}(X) \in \mathbb Zfee(X)∈Z and size(X)∈Z\mathrm{size}(X) \in \mathbb Zsize(X)∈Z, both completely arbitrary integers (zero, negative or huge values allowed; no machine-word bounds, and no requirement that the size be positive or that a zero size forces a zero fee). Equality of FeeFracs is decidable (componentwise) and they have a printable representation.

2. Zero. The zero FeeFrac is 0=(0,0)0 = (0, 0)0=(0,0).

3. Addition. X+Y=(fee(X)+fee(Y), size(X)+size(Y))X + Y = \big(\mathrm{fee}(X) + \mathrm{fee}(Y),\ \mathrm{size}(X) + \mathrm{size}(Y)\big)X+Y=(fee(X)+fee(Y), size(X)+size(Y)).

4. Subtraction. X−Y=(fee(X)−fee(Y), size(X)−size(Y))X - Y = \big(\mathrm{fee}(X) - \mathrm{fee}(Y),\ \mathrm{size}(X) - \mathrm{size}(Y)\big)X−Y=(fee(X)−fee(Y), size(X)−size(Y)).

5. IsEmpty. IsEmpty(X)\mathrm{IsEmpty}(X)IsEmpty(X) is the proposition size(X)=0\mathrm{size}(X) = 0size(X)=0 (regardless of the fee).

6. mul. mul(a,b)=a⋅b\mathrm{mul}(a, b) = a \cdot bmul(a,b)=a⋅b, the exact product of two integers.

7. mulFallback. For integers a,ba, ba,b, with default (floor) integer division by 232=42949672962^{32} = 4294967296232=4294967296:

ℓ=(a mod 232)⋅b,h=(a/232)⋅b,mulFallback(a,b)=(h+ℓ/232, ℓ mod 232).\ell = (a \bmod 2^{32}) \cdot b,\qquad h = (a / 2^{32}) \cdot b,\qquad \mathrm{mulFallback}(a,b) = \big(h + \ell / 2^{32},\ \ell \bmod 2^{32}\big).ℓ=(amod232)⋅b,h=(a/232)⋅b,mulFallback(a,b)=(h+ℓ/232, ℓmod232).

Here a mod 232∈[0,232)a \bmod 2^{32} \in [0, 2^{32})amod232∈[0,232) and a/232=⌊a/232⌋a / 2^{32} = \lfloor a / 2^{32} \rfloora/232=⌊a/232⌋ also for negative aaa; the second output component lies in [0,232)[0, 2^{32})[0,232). No bounds on a,ba, ba,b are assumed.

8. div. For integers n,dn, dn,d and a boolean ρ\rhoρ ("round down"), with q=tdiv⁡(n,d)q = \operatorname{tdiv}(n,d)q=tdiv(n,d) and r=tmod⁡(n,d)r = \operatorname{tmod}(n,d)r=tmod(n,d) (truncated division):

div(n,d,ρ)=q+[ r>0 ]−[ r≠0 and ρ ].\mathrm{div}(n, d, \rho) = q + [\,r > 0\,] - [\,r \neq 0 \text{ and } \rho\,].div(n,d,ρ)=q+[r>0]−[r=0 and ρ].

Case by case: if r=0r = 0r=0 the result is qqq; if r>0r > 0r>0 it is qqq when ρ\rhoρ is true and q+1q + 1q+1 when ρ\rhoρ is false; if r<0r < 0r<0 it is q−1q - 1q−1 when ρ\rhoρ is true and qqq when ρ\rhoρ is false. The definition places no condition on ddd: for d=0d = 0d=0 it gives q=0q = 0q=0, r=nr = nr=n, hence [n>0]−[n≠0 and ρ][n > 0] - [n \ne 0 \text{ and } \rho][n>0]−[n=0 and ρ]; for d<0d < 0d<0 the remainder still carries the sign of nnn.

9. divFallback. For a pair of integers n=(n1,n2)n = (n_1, n_2)n=(n1​,n2​), an integer ddd and a boolean ρ\rhoρ, using truncated division throughout:

qH=tdiv⁡(n1,d),nL=tmod⁡(n1,d)⋅232+n2,qL=tdiv⁡(nL,d),rL=tmod⁡(nL,d),q_H = \operatorname{tdiv}(n_1, d),\quad n_L = \operatorname{tmod}(n_1, d)\cdot 2^{32} + n_2,\quad q_L = \operatorname{tdiv}(n_L, d),\quad r_L = \operatorname{tmod}(n_L, d),qH​=tdiv(n1​,d),nL​=tmod(n1​,d)⋅232+n2​,qL​=tdiv(nL​,d),rL​=tmod(nL​,d), qL′=qL+[ rL>0 ]−[ rL≠0 and ρ ],divFallback(n,d,ρ)=qH⋅232+qL′.q_L' = q_L + [\,r_L > 0\,] - [\,r_L \ne 0 \text{ and } \rho\,],\qquad \mathrm{divFallback}(n, d, \rho) = q_H \cdot 2^{32} + q_L'.qL′​=qL​+[rL​>0]−[rL​=0 and ρ],divFallback(n,d,ρ)=qH​⋅232+qL′​.

No range restriction is placed on n2n_2n2​ (it may be negative or ≥232\ge 2^{32}≥232) or on ddd.

10. ceilDiv. For integers n,dn, dn,d, with default (Euclidean) integer division:

ceilDiv(n,d)=n/d+[ n mod d≠0 ].\mathrm{ceilDiv}(n, d) = n / d + [\,n \bmod d \ne 0\,].ceilDiv(n,d)=n/d+[nmodd=0].

The definition is stated for all integers (not only nonnegative ones); for d=0d = 0d=0 it gives [ n≠0 ][\,n \ne 0\,][n=0].

11. evaluateFee. For a FeeFrac XXX, an integer ttt and a boolean ρ\rhoρ:

evaluateFee(X,t,ρ)={(fee(X)⋅t)/size(X)if 0≤fee(X)<233 and ρ is true,ceilDiv(fee(X)⋅t, size(X))if 0≤fee(X)<233 and ρ is false,div(mul(fee(X),t), size(X), ρ)if fee(X)<0 or fee(X)≥233,\mathrm{evaluateFee}(X, t, \rho) = \begin{cases} \big(\mathrm{fee}(X)\cdot t\big) \mathbin{/} \mathrm{size}(X) & \text{if } 0 \le \mathrm{fee}(X) < 2^{33} \text{ and } \rho \text{ is true},\\ \mathrm{ceilDiv}\big(\mathrm{fee}(X)\cdot t,\ \mathrm{size}(X)\big) & \text{if } 0 \le \mathrm{fee}(X) < 2^{33} \text{ and } \rho \text{ is false},\\ \mathrm{div}\big(\mathrm{mul}(\mathrm{fee}(X), t),\ \mathrm{size}(X),\ \rho\big) & \text{if } \mathrm{fee}(X) < 0 \text{ or } \mathrm{fee}(X) \ge 2^{33},\end{cases}evaluateFee(X,t,ρ)=⎩⎨⎧​(fee(X)⋅t)/size(X)ceilDiv(fee(X)⋅t, size(X))div(mul(fee(X),t), size(X), ρ)​if 0≤fee(X)<233 and ρ is true,if 0≤fee(X)<233 and ρ is false,if fee(X)<0 or fee(X)≥233,​

where 233=85899345922^{33} = 8589934592233=8589934592 and "///" in the first line is the default (Euclidean) integer division. No condition on size(X)\mathrm{size}(X)size(X) (it may be 000 or negative) or on ttt is part of the definition.

12. evaluateFeeDown. evaluateFeeDown(X,t)=evaluateFee(X,t,true)\mathrm{evaluateFeeDown}(X, t) = \mathrm{evaluateFee}(X, t, \text{true})evaluateFeeDown(X,t)=evaluateFee(X,t,true).

13. evaluateFeeUp. evaluateFeeUp(X,t)=evaluateFee(X,t,false)\mathrm{evaluateFeeUp}(X, t) = \mathrm{evaluateFee}(X, t, \text{false})evaluateFeeUp(X,t)=evaluateFee(X,t,false).

14. byRatioCmp. For FeeFracs X,YX, YX,Y, byRatioCmp(X,Y)\mathrm{byRatioCmp}(X, Y)byRatioCmp(X,Y) is the three-way comparison of the two integers fee(X)⋅size(Y)\mathrm{fee}(X)\cdot\mathrm{size}(Y)fee(X)⋅size(Y) and fee(Y)⋅size(X)\mathrm{fee}(Y)\cdot\mathrm{size}(X)fee(Y)⋅size(X):

byRatioCmp(X,Y)={ltif fee(X) size(Y)<fee(Y) size(X),eqif they are equal,gtif fee(X) size(Y)>fee(Y) size(X).\mathrm{byRatioCmp}(X,Y) = \begin{cases}\mathrm{lt} & \text{if } \mathrm{fee}(X)\,\mathrm{size}(Y) < \mathrm{fee}(Y)\,\mathrm{size}(X),\\ \mathrm{eq} & \text{if they are equal},\\ \mathrm{gt} & \text{if } \mathrm{fee}(X)\,\mathrm{size}(Y) > \mathrm{fee}(Y)\,\mathrm{size}(X).\end{cases}byRatioCmp(X,Y)=⎩⎨⎧​lteqgt​if fee(X)size(Y)<fee(Y)size(X),if they are equal,if fee(X)size(Y)>fee(Y)size(X).​

No sign condition on the sizes is part of the definition. In particular, byRatioCmp(X,(0,1))\mathrm{byRatioCmp}(X, (0,1))byRatioCmp(X,(0,1)) is the comparison of fee(X)\mathrm{fee}(X)fee(X) with 000, independent of size(X)\mathrm{size}(X)size(X).

15. ratio. ratio(X)=fee(X)/size(X)∈Q\mathrm{ratio}(X) = \mathrm{fee}(X) / \mathrm{size}(X) \in \mathbb Qratio(X)=fee(X)/size(X)∈Q, rational division, which yields 000 when size(X)=0\mathrm{size}(X) = 0size(X)=0.

16. PartialOrdering. A type with exactly four values: less\mathsf{less}less, equivalent\mathsf{equivalent}equivalent, greater\mathsf{greater}greater, unordered\mathsf{unordered}unordered (with decidable equality).

17. boolCompare. For booleans β0,β1\beta_0, \beta_1β0​,β1​:

boolCompare(false,false)=equivalent,boolCompare(false,true)=less,boolCompare(true,false)=greater,boolCompare(true,true)=equivalent.\mathrm{boolCompare}(\text{false},\text{false}) = \mathsf{equivalent},\quad \mathrm{boolCompare}(\text{false},\text{true}) = \mathsf{less},\quad \mathrm{boolCompare}(\text{true},\text{false}) = \mathsf{greater},\quad \mathrm{boolCompare}(\text{true},\text{true}) = \mathsf{equivalent}.boolCompare(false,false)=equivalent,boolCompare(false,true)=less,boolCompare(true,false)=greater,boolCompare(true,true)=equivalent.

18. sweep. sweep(R0,R1,A0,A1,β0,β1)∈PartialOrdering\mathrm{sweep}(R_0, R_1, A_0, A_1, \beta_0, \beta_1) \in \mathrm{PartialOrdering}sweep(R0​,R1​,A0​,A1​,β0​,β1​)∈PartialOrdering, where R0,R1R_0, R_1R0​,R1​ are lists of FeeFracs, A0,A1A_0, A_1A0​,A1​ are FeeFracs and β0,β1\beta_0, \beta_1β0​,β1​ are booleans, is defined by recursion (each recursive call shortens R0R_0R0​ or R1R_1R1​, so it terminates) as follows.

  1. Both lists empty (R0=R1=[ ]R_0 = R_1 = [\,]R0​=R1​=[]): the result is boolCompare(β0,β1)\mathrm{boolCompare}(\beta_0, \beta_1)boolCompare(β0​,β1​).
  2. R0=c0::R0′R_0 = c_0 :: R_0'R0​=c0​::R0′​ nonempty, R1=[ ]R_1 = [\,]R1​=[]: put P=c0+A0P = c_0 + A_0P=c0​+A0​ and κ=byRatioCmp(P−A1,(0,1))\kappa = \mathrm{byRatioCmp}(P - A_1, (0,1))κ=byRatioCmp(P−A1​,(0,1)), i.e. the comparison of fee(P)−fee(A1)=fee(c0)+fee(A0)−fee(A1)\mathrm{fee}(P) - \mathrm{fee}(A_1) = \mathrm{fee}(c_0) + \mathrm{fee}(A_0) - \mathrm{fee}(A_1)fee(P)−fee(A1​)=fee(c0​)+fee(A0​)−fee(A1​) with 000 (sizes play no role). Set β0′=β0∨(κ=gt)\beta_0' = \beta_0 \lor (\kappa = \mathrm{gt})β0′​=β0​∨(κ=gt), i.e. β0\beta_0β0​ or fee(P)>fee(A1)\mathrm{fee}(P) > \mathrm{fee}(A_1)fee(P)>fee(A1​); and β1′=β1∨(κ=lt)\beta_1' = \beta_1 \lor (\kappa = \mathrm{lt})β1′​=β1​∨(κ=lt), i.e. β1\beta_1β1​ or fee(P)<fee(A1)\mathrm{fee}(P) < \mathrm{fee}(A_1)fee(P)<fee(A1​). If β0′\beta_0'β0′​ and β1′\beta_1'β1′​ are both true, the result is unordered\mathsf{unordered}unordered; otherwise it is sweep(R0′,[ ],P,A1,β0′,β1′)\mathrm{sweep}(R_0', [\,], P, A_1, \beta_0', \beta_1')sweep(R0′​,[],P,A1​,β0′​,β1′​).
  3. R0=[ ]R_0 = [\,]R0​=[], R1=c1::R1′R_1 = c_1 :: R_1'R1​=c1​::R1′​ nonempty (mirror image): put P=c1+A1P = c_1 + A_1P=c1​+A1​ and κ=\kappa = κ= comparison of fee(P)−fee(A0)\mathrm{fee}(P) - \mathrm{fee}(A_0)fee(P)−fee(A0​) with 000. Set β1′=β1∨(fee(P)>fee(A0))\beta_1' = \beta_1 \lor (\mathrm{fee}(P) > \mathrm{fee}(A_0))β1′​=β1​∨(fee(P)>fee(A0​)) and β0′=β0∨(fee(P)<fee(A0))\beta_0' = \beta_0 \lor (\mathrm{fee}(P) < \mathrm{fee}(A_0))β0′​=β0​∨(fee(P)<fee(A0​)). If both are true, the result is unordered\mathsf{unordered}unordered; otherwise it is sweep([ ],R1′,A0,P,β0′,β1′)\mathrm{sweep}([\,], R_1', A_0, P, \beta_0', \beta_1')sweep([],R1′​,A0​,P,β0′​,β1′​).
  4. Both nonempty, R0=c0::R0′R_0 = c_0 :: R_0'R0​=c0​::R0′​, R1=c1::R1′R_1 = c_1 :: R_1'R1​=c1​::R1′​: put P0=c0+A0P_0 = c_0 + A_0P0​=c0​+A0​ and P1=c1+A1P_1 = c_1 + A_1P1​=c1​+A1​.
    • (a) If size(P0)>size(P1)\mathrm{size}(P_0) > \mathrm{size}(P_1)size(P0​)>size(P1​): κ=byRatioCmp(P1−A0, P0−A0)\kappa = \mathrm{byRatioCmp}(P_1 - A_0,\ P_0 - A_0)κ=byRatioCmp(P1​−A0​, P0​−A0​), i.e. the comparison of
(fee(P1)−fee(A0))(size(P0)−size(A0))with(fee(P0)−fee(A0))(size(P1)−size(A0)).\big(\mathrm{fee}(P_1) - \mathrm{fee}(A_0)\big)\big(\mathrm{size}(P_0) - \mathrm{size}(A_0)\big) \quad\text{with}\quad \big(\mathrm{fee}(P_0) - \mathrm{fee}(A_0)\big)\big(\mathrm{size}(P_1) - \mathrm{size}(A_0)\big).(fee(P1​)−fee(A0​))(size(P0​)−size(A0​))with(fee(P0​)−fee(A0​))(size(P1​)−size(A0​)).
 Set $\beta_1' = \beta_1 \lor (\kappa = \mathrm{gt})$ and $\beta_0' = \beta_0 \lor (\kappa = \mathrm{lt})$. If both are true, the result is $\mathsf{unordered}$; otherwise it is $\mathrm{sweep}(c_0 :: R_0',\ R_1',\ A_0,\ P_1,\ \beta_0', \beta_1')$ (list $0$ and $A_0$ unchanged; the head of list $1$ is consumed and $A_1$ becomes $P_1$).
  • (b) Otherwise (size(P0)≤size(P1)\mathrm{size}(P_0) \le \mathrm{size}(P_1)size(P0​)≤size(P1​)): κ=byRatioCmp(P0−A1, P1−A1)\kappa = \mathrm{byRatioCmp}(P_0 - A_1,\ P_1 - A_1)κ=byRatioCmp(P0​−A1​, P1​−A1​), i.e. the comparison of
(fee(P0)−fee(A1))(size(P1)−size(A1))with(fee(P1)−fee(A1))(size(P0)−size(A1)).\big(\mathrm{fee}(P_0) - \mathrm{fee}(A_1)\big)\big(\mathrm{size}(P_1) - \mathrm{size}(A_1)\big) \quad\text{with}\quad \big(\mathrm{fee}(P_1) - \mathrm{fee}(A_1)\big)\big(\mathrm{size}(P_0) - \mathrm{size}(A_1)\big).(fee(P0​)−fee(A1​))(size(P1​)−size(A1​))with(fee(P1​)−fee(A1​))(size(P0​)−size(A1​)).
 Set $\beta_0' = \beta_0 \lor (\kappa = \mathrm{gt})$ and $\beta_1' = \beta_1 \lor (\kappa = \mathrm{lt})$. If both are true, the result is $\mathsf{unordered}$. Otherwise, if $\mathrm{size}(P_1) = \mathrm{size}(P_0)$ the result is $\mathrm{sweep}(R_0', R_1', P_0, P_1, \beta_0', \beta_1')$ (both heads consumed); and if $\mathrm{size}(P_0) < \mathrm{size}(P_1)$ it is $\mathrm{sweep}(R_0',\ c_1 :: R_1',\ P_0,\ A_1,\ \beta_0', \beta_1')$.

The flags only ever change from false to true, and the function returns unordered\mathsf{unordered}unordered at the first step at which both become true; a recursive call is made only when at most one of them is true. The case boolCompare(true,true)=equivalent\mathrm{boolCompare}(\text{true},\text{true}) = \mathsf{equivalent}boolCompare(true,true)=equivalent can therefore be reached only if sweep is entered with both flags already true and both lists empty. The definition makes no assumption on signs of fees or sizes, nor on the order of the chunks; zero or negative sizes simply enter the comparisons above.

19. compareChunks. For chunk lists (finite lists of FeeFracs, possibly empty) c0,c1c^0, c^1c0,c1:

compareChunks(c0,c1)=sweep(c0,c1,(0,0),(0,0),false,false).\mathrm{compareChunks}(c^0, c^1) = \mathrm{sweep}\big(c^0, c^1, (0,0), (0,0), \text{false}, \text{false}\big).compareChunks(c0,c1)=sweep(c0,c1,(0,0),(0,0),false,false).

In particular compareChunks([ ],[ ])=boolCompare(false,false)=equivalent\mathrm{compareChunks}([\,],[\,]) = \mathrm{boolCompare}(\text{false},\text{false}) = \mathsf{equivalent}compareChunks([],[])=boolCompare(false,false)=equivalent, and once one list is exhausted only fees are compared (cases 2 and 3 of sweep).

20. ImprovesFeerateDiagram. For chunk lists old,new\mathit{old}, \mathit{new}old,new (in this argument order), ImprovesFeerateDiagram(old,new)\mathrm{ImprovesFeerateDiagram}(\mathit{old}, \mathit{new})ImprovesFeerateDiagram(old,new) is the proposition

compareChunks(new,old)=greater,\mathrm{compareChunks}(\mathit{new}, \mathit{old}) = \mathsf{greater},compareChunks(new,old)=greater,

i.e. the second argument is passed first to compareChunks.

21. diagram. For a chunk list ccc and x∈Qx \in \mathbb Qx∈Q, diagram(c,x)∈Q\mathrm{diagram}(c, x) \in \mathbb Qdiagram(c,x)∈Q is defined recursively:

diagram([ ],x)=0,diagram(c1::c′,x)={fee(c1)⋅x/size(c1)if x≤size(c1),fee(c1)+diagram(c′,x−size(c1))if x>size(c1),\mathrm{diagram}([\,], x) = 0, \qquad \mathrm{diagram}(c_1 :: c', x) = \begin{cases} \mathrm{fee}(c_1)\cdot x / \mathrm{size}(c_1) & \text{if } x \le \mathrm{size}(c_1),\\ \mathrm{fee}(c_1) + \mathrm{diagram}\big(c', x - \mathrm{size}(c_1)\big) & \text{if } x > \mathrm{size}(c_1),\end{cases}diagram([],x)=0,diagram(c1​::c′,x)={fee(c1​)⋅x/size(c1​)fee(c1​)+diagram(c′,x−size(c1​))​if x≤size(c1​),if x>size(c1​),​

with rational division (⋅/0=0\cdot/0 = 0⋅/0=0). It is defined for every rational xxx, including negative xxx. For the empty list it is identically 000. When every size is positive, writing Sk=∑i≤ksize(ci)S_k = \sum_{i \le k}\mathrm{size}(c_i)Sk​=∑i≤k​size(ci​) and Fk=∑i≤kfee(ci)F_k = \sum_{i \le k}\mathrm{fee}(c_i)Fk​=∑i≤k​fee(ci​) (with S0=F0=0S_0 = F_0 = 0S0​=F0​=0) for c=[c1,…,cn]c = [c_1,\dots,c_n]c=[c1​,…,cn​], n≥1n \ge 1n≥1, the recursion unfolds to: diagram(c,x)=fee(c1) x/size(c1)\mathrm{diagram}(c,x) = \mathrm{fee}(c_1)\,x/\mathrm{size}(c_1)diagram(c,x)=fee(c1​)x/size(c1​) for all x≤S1x \le S_1x≤S1​ (including negative xxx); Fk−1+fee(ck)(x−Sk−1)/size(ck)F_{k-1} + \mathrm{fee}(c_k)(x - S_{k-1})/\mathrm{size}(c_k)Fk−1​+fee(ck​)(x−Sk−1​)/size(ck​) for Sk−1≤x≤SkS_{k-1} \le x \le S_kSk−1​≤x≤Sk​; and FnF_nFn​ for x≥Snx \ge S_nx≥Sn​ — the piecewise-linear function through (0,0),(S1,F1),…,(Sn,Fn)(0,0), (S_1,F_1), \dots, (S_n,F_n)(0,0),(S1​,F1​),…,(Sn​,Fn​), horizontal to the right. If a size is zero or negative the recursion still evaluates but need not have this shape (e.g. a chunk with size(c1)<0\mathrm{size}(c_1) < 0size(c1​)<0 gives diagram(c,0)=fee(c1)+diagram(c′,−size(c1))\mathrm{diagram}(c, 0) = \mathrm{fee}(c_1) + \mathrm{diagram}(c', -\mathrm{size}(c_1))diagram(c,0)=fee(c1​)+diagram(c′,−size(c1​)); a chunk with size 000 contributes a jump of fee(c1)\mathrm{fee}(c_1)fee(c1​) just after x=0x = 0x=0).

22. diagramFee. diagramFee([c1,…,cn])=∑i=1nfee(ci)∈Z\mathrm{diagramFee}([c_1,\dots,c_n]) = \sum_{i=1}^n \mathrm{fee}(c_i) \in \mathbb ZdiagramFee([c1​,…,cn​])=∑i=1n​fee(ci​)∈Z (000 for the empty list).

23. diagramSize. diagramSize([c1,…,cn])=∑i=1nsize(ci)∈Z\mathrm{diagramSize}([c_1,\dots,c_n]) = \sum_{i=1}^n \mathrm{size}(c_i) \in \mathbb ZdiagramSize([c1​,…,cn​])=∑i=1n​size(ci​)∈Z (000 for the empty list).

24. SizesPos. SizesPos(c)\mathrm{SizesPos}(c)SizesPos(c): every chunk cic_ici​ of ccc has size(ci)>0\mathrm{size}(c_i) > 0size(ci​)>0 (vacuously true for the empty list; nothing is said about fees).

25. FeeratesNonIncreasing. FeeratesNonIncreasing(c)\mathrm{FeeratesNonIncreasing}(c)FeeratesNonIncreasing(c) means: for every pair of adjacent chunks ci,ci+1c_i, c_{i+1}ci​,ci+1​,

fee(ci+1)⋅size(ci)≤fee(ci)⋅size(ci+1)\mathrm{fee}(c_{i+1})\cdot\mathrm{size}(c_i) \le \mathrm{fee}(c_i)\cdot\mathrm{size}(c_{i+1})fee(ci+1​)⋅size(ci​)≤fee(ci​)⋅size(ci+1​)

(integer cross-multiplication). It holds automatically for lists of length 000 or 111.

26. Dominates. Dominates(c0,c1)\mathrm{Dominates}(c^0, c^1)Dominates(c0,c1): for every rational x≥0x \ge 0x≥0, diagram(c1,x)≤diagram(c0,x)\mathrm{diagram}(c^1, x) \le \mathrm{diagram}(c^0, x)diagram(c1,x)≤diagram(c0,x).

27. BetterSomewhere. BetterSomewhere(c0,c1)\mathrm{BetterSomewhere}(c^0, c^1)BetterSomewhere(c0,c1): there exists a rational x≥0x \ge 0x≥0 with diagram(c1,x)<diagram(c0,x)\mathrm{diagram}(c^1, x) < \mathrm{diagram}(c^0, x)diagram(c1,x)<diagram(c0,x).

28. StrictlyBetter. StrictlyBetter(c0,c1)\mathrm{StrictlyBetter}(c^0, c^1)StrictlyBetter(c0,c1): Dominates(c0,c1)\mathrm{Dominates}(c^0, c^1)Dominates(c0,c1) and BetterSomewhere(c0,c1)\mathrm{BetterSomewhere}(c^0, c^1)BetterSomewhere(c0,c1).

In 26–28 only rational x≥0x \ge 0x≥0 are considered (x=0x = 0x=0 included, negative xxx excluded), over the whole half-line, including points beyond both lists' total sizes.

Human review
  • Endorsed by Shuze Chen · Oct 30, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Oct 30, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me