Identifier
F:fp16-add-monotone-rne
Proof route
smt-clausal
External status
proved
Axiom footprint
ieee754-2019-arithmetic-semantics-for-the-binary16-layout-as-encoded-by-axeyum-fp-fpa2bv-lowering-and-as-implemented-by-rustc_apfloat, axeyum-fp.add-is-a-differentially-VALIDATED-not-proven-bit-blaster, rounding-mode-roundNearestTiesToEven-only-for-this-fact-unlike-fp8-this-run-did-not-sweep-the-other-four-rounding-modes, smtlib2-fp.leq-ordering-nan-unordered-plus-zero-equals-minus-zero, tseitin-cnf-encoding-preserves-satisfiability, adr-0613-elaborate_drat_to_lrat_backward-is-an-UNTRUSTED-producer-of-antecedent-hints-only-its-output-is-never-accepted-without-check_lrat, adr-0613-check_lrat-search-free-linear-hint-following-verification-is-what-discharges-Certified, adr-0613-check_drat_backward-appears-only-in-REJECTING-position-inside-UnsatProof::recheck-never-accepting, format-binary16-only-this-fact-is-not-format-generic-and-says-nothing-about-other-widths, no-exhaustive-enumeration-at-this-width-2^48-triples-is-not-searchable-unlike-the-fp8-sibling

Recorded description

Let F be the IEEE-754 binary16 interchange format, SMT-LIB `(_ FloatingPoint 5 11)`, and let RNE denote roundNearestTiesToEven. For all values a, b, c of F: if fp.leq(a, b) holds and neither fp.add(RNE, a, c) nor fp.add(RNE, b, c) is NaN, then fp.leq(fp.add(RNE, a, c), fp.add(RNE, b, c)). This is the binary16 instance of F:fp8-add-monotone-rne. It was `open` from 2026-08-14 to 2026-08-28 because AXEYUM HAD NOT SETTLED IT -- not because it was doubted; ADR-0613's LRAT hint-following certification route closed the measured checking-throughput obstruction and this fact moved to `proved` on the symbolic CNF/DRAT/LRAT route alone (binary16's 2^48-triple space is not exhaustively enumerable, unlike the fp8 E5M2 sibling).

Formal statement
(assert (=> (and (fp.leq a b) (not (fp.isNaN (fp.add RNE a c))) (not (fp.isNaN (fp.add RNE b c)))) (fp.leq (fp.add RNE a c) (fp.add RNE b c))))

Dependencies

The graph shows direct ledger edges. Follow a node to open its artifact page.

Direct dependencies appear to the left. The current fact is in the center. Facts that depend directly on it appear to the right. Current fact
0 direct dependencies 0 direct dependents

Evidence

fp16-monotone-unsat-lrat-certified

Kind
unsat-certificate
Status
checked

Supports: The negation of formal.statement is unsatisfiable over binary16 (IEEE 754 (_ FloatingPoint 5 11)), decided symbolically via CNF/DRAT and certified via the ADR-0613 LRAT hint-following route -- without enumerating the 2^48 triples, which is not searchable at this width (contrast the fp8 E5M2 sibling, F:fp8-add-monotone-rne, settled partly by exhaustive enumeration of all 2^24 triples).

Checker command
OUT=$(cargo run --release -q -p axeyum-bench --example smtcomp_cli -- --evidence artifacts/facts/smt2/neg-fp16-add-monotone-rne.smt2 2>&1); U=$(printf '%s\n' "$OUT" | /usr/bin/grep -c '^unsat$'); C=$(printf '%s\n' "$OUT" | /usr/bin/grep -c 'certified=1 '); R=$(printf '%s\n' "$OUT" | /usr/bin/grep -c 'recheck=ok'); test "$U" = 1 && test "$C" = 1 && test "$R" = 1
Evidence notes

Reproduced independently by the fp16-evidence lane, 2026-08-28, in its own worktree with a fresh `cargo build --release -p axeyum-bench --example smtcomp_cli` (this fact's evidence depends on code that landed within the hour, ADR-0613, so a stale prebuilt binary would have measured the OLD superlinear-checking route). Two full end-to-end runs, both `unsat`/`certified=1`/`recheck=ok`/`arena=ok`: run 1 (host load ~2.8/16): search 424,601 conflicts/26.556s -> 827,048 proof steps/193,214,020 bytes; backward_lrat_certify 827,048/827,048 steps, elapsed_ms=95,932, certified=true; printed line `; evidence kind=unsat-drat certified=1 recheck=ok arena=ok ms=136898`; verdict `unsat`. Measured via `/usr/bin/time -v` around the WHOLE process: wall clock 5:39.01 (339.01s), 99% CPU, RSS 3.11 GB. run 2 (host load ~20.7/16, contended): printed line `; evidence ... certified=1 recheck=ok arena=ok ms=168081`; verdict `unsat`. Measured via date-diff around the whole `cargo run` invocation: wall clock 353s. IMPORTANT CORRECTION TO THE ADR-0613 NUMBERS THIS FACT'S NOTES ALREADY QUOTE. The `; evidence ... ms=NNN` field printed by `smtcomp_cli` is captured in `evidence_report_line`'s caller BEFORE `UnsatProof::recheck()` and the `arena` fresh-parse check run (see `crates/axeyum-bench/examples/smtcomp_cli.rs`, the `started.elapsed().as_millis()` argument is evaluated before `evidence_report_line` calls `proof.recheck()` and `evidence.check_outcome(...)`). So `ms=136898`/`ms=168081` measure only parse+solve+certify, NOT the full checked claim this evidence row needs -- `recheck=ok` (an independent second pass: `check_lrat` plus, in rejecting-only position, `check_drat_backward` over the full 827,048-step proof) and `arena=ok` (a second fresh parse of the original SMT-LIB file plus re-evaluation) both run AFTER that timer stops. The ADR calls its `ms=125098` figure "end to end"; measured here, the ACTUAL end-to-end wall clock (what this checker_command, or any external caller of the binary, actually waits for) is 2.5-2.9x that: 339-353s across two runs at different contention levels, not ~125-137s. This does not weaken the ADR's underlying finding -- checking still moved from never-observed-to-finish to under six minutes, roughly two orders of magnitude, not three -- but the smaller number is a sub-stage timer, not the wall-clock cost of running the command. WHY THIS IS THE ONLY EVIDENCE ROW, UNLIKE THE FP8 SIBLING. F:fp8-add-monotone-rne is settled twice, by exhaustive enumeration of all 2^24 triples AND by this same symbolic CNF/DRAT route. Binary16 has 2^48 triples; brute-force enumeration is not available at this width (see that fact's own arity-wall note), so this fact rests on the symbolic route alone. The `checker_command`'s exit status depends on three independently-tested substrings of the real run's stdout (`^unsat$`, `certified=1 `, `recheck=ok`), each verified against BOTH a captured real positive run and two synthetic negative-control transcripts (sat/uncertified: U=C=R=0, chain fails; unsat-but-certified=0: C=0, chain fails) before this row was written -- if the claim were false, this command exits nonzero because at least one of those three greps would count zero matching lines and the chained `test` would fail on the first zero it hits.

Provenance

{
  "date": "2026-08-28",
  "established_by": "fp16-evidence lane, reproducing ADR-0613's LRAT hint-following certification route (docs/research/09-decisions/adr-0613-unsat-is-certified-by-following-hints-not-by-searching-for-them.md), landed on main the same day by the drat-evidence-route lane. This lane rebuilt smtcomp_cli --release in its own worktree and ran it twice end to end against the fact's own pinned negation file; both runs certified. The mathematics is unchanged from the prior open-status provenance below (monotonicity of correctly-rounded arithmetic); what changed is that the checking stage now terminates and is independently re-verified, closing the measured obstruction this fact was blocked on.",
  "source": "authored here as the binary16 instance of F:fp8-add-monotone-rne, which IS settled, by exhaustive enumeration at 8 bits.",
  "prior_art": [
    {
      "who": "IEEE 754-2019, clause 4.3 (rounding-direction attributes)",
      "what": "That each rounding-direction attribute defines a monotone map from the extended reals to the format, so a correctly-rounded operation inherits the monotonicity of the exact operation it rounds -- which gives the statement for every format, this one included.",
      "where": "IEEE Standard for Floating-Point Arithmetic",
      "year": 2019,
      "attribution": "standard textbook attribution; this lane did not consult the primary source, and records the citation as the received one."
    },
    {
      "who": "z3 4.13.3 and bitwuzla 0.9.1",
      "what": "Both report `unsat` on the negation, i.e. both prove the statement, in 30.6s and 8.3s respectively on artifacts/facts/smt2/neg-fp16-add-monotone-rne.smt2 (measured 2026-08-14, same machine, release builds).",
      "where": "run locally by the fp-kernels lane; the file is in this repository",
      "year": 2026,
      "attribution": "measured by this lane, not cited. Recorded under prior_art because these are OTHER systems establishing the fact -- deliberately NOT recorded as `evidence`, since evidence rows here would make the ledger say axeyum established something it did not."
    }
  ]
}