What does The Cliff of Stacked Rules conclude, in numbers, about “Where the Cliff Lies: the First-Moment Bound, the Exact Threshold of 2-SAT and Rule Length”?
Answer: Chapter 3 gives the first-moment bound of 5.191, the exact threshold of 2-SAT and the role of rule length.
Scope of the numbers: The rulebooks and data are illustrative; every calculation is generated by the book's programs; the book offers general business method, not legal, compliance or business-decision advice. Chapter 4 checks an illustrative rulebook of 24 switches: bare ratio 0.958, load 0.475, a median clause ratio at deadlock of only 1.292, and a minimal conflict core spanning three rule families.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 5.191
| first-moment bound: alpha < ln 2 / ln(8/7) = 5.191 | ||||
| n = 20, 40 formulas per ratio, exact solution counts | ||||
| alpha | E[X] formula | mean X | median X | P(sat) |
| 2.0 | 5022.5 | 5129.8 | 4821.5 | 1.000 |
| 3.0 | 347.6 | 343.8 | 266.0 | 1.000 |
| 4.0 | 24.1 | 23.2 | 9.0 | 0.875 |
| 4.3 | 10.8 | 9.8 | 2.0 | 0.575 |
| 5.0 | 1.7 | 1.3 | 0.0 | 0.275 |
| 5.5 | 0.4 | 0.9 | 0.0 | 0.225 |
Key formula
Show the full program
# Chapter 3. p31: the first-moment bound and what the mean hides
# Model: each random 3-rule forbids 1 of the 8 sign patterns of its
# switches, so a fixed assignment survives m rules with probability
# (7/8)^m and the expected number of solutions is E[X] = 2^n (7/8)^m.
# E[X] < 1 forces P(sat) -> 0, giving alpha < ln 2 / ln(8/7). Exact
# solution counts (counting DPLL, integers only) for n = 20, 40
# formulas per ratio, illustrative sizes; fixed seed.
import math
import random
import statistics
from collections import Counter
N, TRIALS = 20, 40
ALPHAS = [2.0, 3.0, 4.0, 4.3, 5.0, 5.5]
def assign(cls, lit):
out = []
for c in cls:
if lit in c:
continue
if -lit in c:
c = [x for x in c if x != -lit]
if not c:
return None
out.append(c)
return out
def count(cls, free):
if not cls:
return 1 << free
w = Counter(abs(x) for c in cls for x in c)
v = max(w, key=lambda x: (w[x], -x))
total = 0
for b in (v, -v):
nxt = assign(cls, b)
if nxt is not None:
total += count(nxt, free - 1)
return total
bound = math.log(2.0) / math.log(8.0 / 7.0)
print("first-moment bound: alpha < ln 2 / ln(8/7) = %.3f" % bound)
rng = random.Random(20261117)
print("n = %d, %d formulas per ratio, exact solution counts" % (N, TRIALS))
print("alpha E[X] formula mean X median X P(sat)")
for a in ALPHAS:
m = round(a * N)
xs = []
for _ in range(TRIALS):
f = []
for _ in range(m):
vs = rng.sample(range(1, N + 1), 3)
f.append([v if rng.random() < 0.5 else -v for v in vs])
xs.append(count(f, N))
ex = 2.0 ** N * (7.0 / 8.0) ** m
sat = len([x for x in xs if x > 0]) / TRIALS
print("%4.1f %11.1f %10.1f %9.1f %6.3f"
% (a, ex, statistics.fmean(xs), statistics.median(xs), sat))Single source and citation
Fan, Y. (2026). Boolean Satisfiability Phase Transitions: the Critical Constraint Ratio at Which Stacked Promotion, Compliance and Gate Rules Deadlock, and How to See It Coming (Version 1.0.0), Chapter 3: Where the Cliff Lies: the First-Moment Bound, the Exact Threshold of 2-SAT and Rule Length. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-252 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026252,
author = {Fan, Yafu},
title = {Boolean Satisfiability Phase Transitions: the Critical Constraint Ratio at Which Stacked Promotion, Compliance and Gate Rules Deadlock, and How to See It Coming},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 1 · The Cliff of Stacked Rules: the Satisfiability Phase Transition of Random 3-SAT
- Chapter 2 · DPLL with the Standard Library: Unit Propagation, Branching and "Easy, Hard, Easy"
- Chapter 4 · Measuring a Rulebook: Load, Forced Values, Minimal Conflict Cores and Headroom
- Chapter 5 · Real Rules Are Not Random Rules: Mixed Lengths, the 2+p Model and the Balance of Demands and Prohibitions
- Chapter 6 · Signals on the Eve of Deadlock: Solution Counts, the Backbone and the Hazard of the Next Rule
- Chapter 7 · Classical Sources East and West: the Spear and Shield of the Han Feizi, and Boole's x² = x
- Chapter 8 · Closing the Loop: a Monthly Constraint-Ratio Scan of the Five-Kit Rulebooks and a Pre-Registered Test