There are sorted, positive-size chunkings with ImprovesFeerateDiagram old new and equal total fees (one chunk (4, 2) against (3, 1), (1, 1)): the diagram check alone does not make the replacement pay more; PaysForRBF does.
Preamble
import Definitions.Def_BitcoinFeerateDiagram
open BitcoinFeerateDiagram BitcoinReplacement
Formal statement
theorem BitcoinFeerateDiagram.improves_total_fee_not_strict :
∃ old new : List FeeFrac, SizesPos old ∧ SizesPos new ∧ FeeratesNonIncreasing old ∧
FeeratesNonIncreasing new ∧ ImprovesFeerateDiagram old new ∧
diagramFee old = diagramFee new := by sorry
Statement. There exist two finite lists of FeeFracs old and new such that all of the following hold:
SizesPos(old): every chunk of old has strictly positive size;
SizesPos(new): every chunk of new has strictly positive size;
FeeratesNonIncreasing(old): adjacent chunks a,b of old (with b right after a) satisfy fee(b)size(a)≤fee(a)size(b);
FeeratesNonIncreasing(new): the same for new;
ImprovesFeerateDiagram(old,new), i.e. compareChunks(new,old)=greater;
diagramFee(old)=diagramFee(new): the two lists have exactly the same total fee ∑fee(c).
Binders and edge cases. This is a pure existence statement with no hypotheses: it asserts that at least one such pair exists and gives no information about any other pair, nor about which pair. The witnesses are not specified. Conditions 1–4 hold vacuously for an empty list, so they do not by themselves rule out an empty witness; condition 5 rules out both lists being empty at once, since compareChunks([],[])=equivalent. Fees of the witnesses may be any integers (zero or negative not excluded). Nothing is asserted about the diagrams themselves beyond what condition 5 says about the compareChunks outcome.
Definitions used, unfolded
Division conventions. Three kinds of division occur.
Default integer divisionn/d with remainder nmodd (Euclidean convention). For d>0: n/d=⌊n/d⌋ and nmodd=n−d⌊n/d⌋∈[0,d), also for negative n (e.g. −7/2=−4, −7mod2=1). For d<0: n/d=−⌊n/∣d∣⌋ and nmodd∈[0,∣d∣). For d=0: n/0=0 and nmod0=n.
Truncated divisiontdiv(n,d) with remainder tmod(n,d)=n−d⋅tdiv(n,d): the quotient is rounded toward zero, so the remainder is 0 or has the sign of n, with ∣tmod(n,d)∣<∣d∣ (e.g. tdiv(−7,2)=−3, tmod(−7,2)=−1). For d=0: tdiv(n,0)=0, tmod(n,0)=n.
Rational division in Q, with the convention q/0=0. For q∈Q, ⌊q⌋ is the greatest integer ≤q and ⌈q⌉ the least integer ≥q.
Below, [P] denotes 1 if the condition P holds and 0 otherwise.
FeeFrac. A FeeFrac is a pair X=(fee(X),size(X)) of two arbitrary integers. Nothing constrains them: either component may be zero or negative, and no machine-word bounds are imposed. Addition and subtraction are componentwise,
X±Y=(fee(X)±fee(Y),size(X)±size(Y)),
and the zero FeeFrac is (0,0). A chunk list is a finite list c=[c1,…,cn] of FeeFracs; the empty list (n=0) is allowed.
byRatioCmp. For FeeFracs X,Y, byRatioCmp(X,Y) is the three-way comparison of the two integers fee(X)⋅size(Y) and fee(Y)⋅size(X):
byRatioCmp(X,Y)=⎩⎨⎧lteqgtif 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)) is the comparison of fee(X) with 0, independent of size(X).
PartialOrdering and boolCompare.PartialOrdering is a four-element type with values less, equivalent, greater, unordered. For booleans β0,β1:
sweep.sweep(R0,R1,A0,A1,β0,β1)∈PartialOrdering, where R0,R1 are lists of FeeFracs, A0,A1 are FeeFracs and β0,β1 are booleans, is defined by recursion (each recursive call shortens R0 or R1, so it terminates) as follows.
Both lists empty (R0=R1=[]): the result is boolCompare(β0,β1).
R0=c0::R0′ nonempty, R1=[]: put P=c0+A0 and κ=byRatioCmp(P−A1,(0,1)), i.e. the comparison of fee(P)−fee(A1)=fee(c0)+fee(A0)−fee(A1) with 0 (sizes play no role). Set β0′=β0∨(κ=gt), i.e. β0 or fee(P)>fee(A1); and β1′=β1∨(κ=lt), i.e. β1 or fee(P)<fee(A1). If β0′ and β1′ are both true, the result is unordered; otherwise it is sweep(R0′,[],P,A1,β0′,β1′).
R0=[], R1=c1::R1′ nonempty (mirror image): put P=c1+A1 and κ= comparison of fee(P)−fee(A0) with 0. Set β1′=β1∨(fee(P)>fee(A0)) and β0′=β0∨(fee(P)<fee(A0)). If both are true, the result is unordered; otherwise it is sweep([],R1′,A0,P,β0′,β1′).
Both nonempty, R0=c0::R0′, R1=c1::R1′: put P0=c0+A0 and P1=c1+A1.
(a) If size(P0)>size(P1):κ=byRatioCmp(P1−A0,P0−A0), i.e. the comparison of
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)):κ=byRatioCmp(P0−A1,P1−A1), i.e. the comparison of
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 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 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.
Edge cases: compareChunks([],[])=equivalent; when one list is (or becomes) exhausted, only the fees of the remaining cumulative points versus the other side's accumulated fee are compared (case 2/3 of sweep).
ImprovesFeerateDiagram. For chunk lists old and new (in this argument order),
i.e. the second argument is passed first to compareChunks.
diagramFee, diagramSize. For c=[c1,…,cn]: diagramFee(c)=∑i=1nfee(ci)∈Z and diagramSize(c)=∑i=1nsize(ci)∈Z (both 0 for the empty list).
SizesPos.SizesPos(c) means size(ci)>0 for every chunk ci in c (vacuously true for the empty list). It says nothing about fees, which may be zero or negative.
FeeratesNonIncreasing.FeeratesNonIncreasing(c) means: for every pair of adjacent chunks ci,ci+1,
fee(ci+1)⋅size(ci)≤fee(ci)⋅size(ci+1)
(integer cross-multiplication). It holds automatically for lists of length 0 or 1.
Confirmed by the moderator at approval.