back to table · edit · history · where entries came from · files · download
6496 bytes, as of the version from 2026-09-16 17:31 (current). Recorded here, not run.
"""Satisfiability thresholds of random $k$-SAT -- numberdb.org/T277.
For k >= 3, alpha_s(k) is the one-step replica-symmetry-breaking
cavity-method prediction for the satisfiability threshold of random k-SAT,
with density alpha = m/n clauses per variable. Mertens, Mezard and Zecchina
tabulate these values as alpha_c for k = 3..7; this table uses alpha_s(k),
the notation of Krzakala, Montanari, Ricci-Tersenghi, Semerjian and
Zdeborova for the SAT-UNSAT threshold.
This generator transcribes the published values:
k = 3: 4.26675 +/- 0.00015 from MMZ Eq. (43)
k = 4..7: 9.931, 21.117, 43.37, 87.79 from MMZ Table 1
Run it with SageMath:
$ sage -pip install numberdb # once
$ sage -python generate.py # check the table against this code
$ sage -python generate.py --publish # fill the draft, with NUMBERDB_API_KEY set
The values are heuristic because they come from the cavity-method population
dynamics calculation. The rows k = 4, 5, 6 were checked against the rounded
values in Krzakala et al. Table 1, and every row was compared with the
large-k asymptotic 2^k log(2) - (1 + log(2))/2.
"""
import os
import sys
import numberdb.sage as numberdb
from numberdb._compare import digits_of
TABLE = os.environ.get("NUMBERDB_TABLE", "T277")
VALUES = {
3: "4.26675 +/- 0.00015",
4: "9.931",
5: "21.117",
6: "43.37",
7: "87.79",
}
COMMENTS = {
3: (
r"Mertens, Mezard and Zecchina give "
r"$\alpha_s(3)=4.26675\pm0.00015$ in Eq. (43), using the notation "
r"$\alpha_c$ for the satisfiability threshold CITE{MMZ}."
),
4: (
r"Mertens, Mezard and Zecchina print $9.931$ CITE{MMZ}; "
r"Krzakala, Montanari, Ricci-Tersenghi, Semerjian and Zdeborova "
r"round it to $9.93$ CITE{KMRTSZ}."
),
5: (
r"Mertens, Mezard and Zecchina print $21.117$ CITE{MMZ}; "
r"Krzakala, Montanari, Ricci-Tersenghi, Semerjian and Zdeborova "
r"round it to $21.12$ CITE{KMRTSZ}."
),
6: (
r"Mertens, Mezard and Zecchina print $43.37$ CITE{MMZ}; "
r"Krzakala, Montanari, Ricci-Tersenghi, Semerjian and Zdeborova "
r"round it to $43.4$ CITE{KMRTSZ}."
),
7: (
r"Mertens, Mezard and Zecchina print $87.79$ CITE{MMZ}."
),
}
KRZAKALA_ROUNDED = {
4: "9.93",
5: "21.12",
6: "43.4",
}
def _key_from_stdin():
if os.environ.get("NUMBERDB_KEY_FROM_STDIN") != "1":
return
token = sys.stdin.read().strip()
if "=" in token and token.split("=", 1)[0].isupper():
token = token.split("=", 1)[1].strip().strip("'\"")
if token:
os.environ["NUMBERDB_API_KEY"] = token
def check_against_krzakala():
"""Return complaints if the source cross-check no longer matches."""
from decimal import Decimal, ROUND_HALF_UP
complaints = []
for k, expected in KRZAKALA_ROUNDED.items():
places = abs(Decimal(expected).as_tuple().exponent)
rounded = Decimal(VALUES[k]).quantize(
Decimal(1).scaleb(-places),
rounding=ROUND_HALF_UP,
)
if format(rounded, "f") != expected:
complaints.append(
"k=%d: %s rounds to %s, not %s"
% (k, VALUES[k], format(rounded, "f"), expected)
)
return complaints
def large_k_leading(k):
"""The leading large-k prediction used only as a scale check."""
from decimal import Decimal, localcontext
with localcontext() as context:
context.prec = 60
log_two = Decimal(2).ln()
return (Decimal(2) ** k) * log_two - (Decimal(1) + log_two) / 2
def asymptotic_differences():
"""Absolute differences from the leading large-k expression."""
from decimal import Decimal
out = {}
for k, text in VALUES.items():
centre = text.split("+/-", 1)[0].strip()
out[k] = abs(Decimal(centre) - large_k_leading(k))
return out
class RandomKSATSatisfiabilityThresholds(numberdb.Generator):
table = TABLE
parameters = ("k",)
type = "R"
digits = 5
rigour = "heuristic"
def enumerate(self):
for k in sorted(VALUES):
yield {"k": str(k)}
def value(self, params, digits):
k = int(params["k"])
text = VALUES[k]
return {
"number": text,
"digits": digits_of(text),
"comment": COMMENTS[k],
}
def fill_draft_once(generator, message):
"""Fill a fresh draft without the client's empty upsert probe."""
from numberdb._generate import (
_check_precision,
_check_rigour,
_producer,
_run_name,
_source_files,
)
from numberdb._write import Entries, attach, submit_entries, to_text
table = generator.table
run = _run_name(generator)
entries = Entries(*generator.parameters)
for params in generator.enumerate():
params = dict(params)
wanted = generator.digits_for(params)
entry = generator._entry(params, wanted)
value = entry["number"]
identity = ",".join(str(params[name]) for name in generator.parameters)
_check_rigour(generator, table, identity, value)
written = to_text(value, entry.get("digits", wanted), generator.format)
_check_precision(table, identity, written, entry.get("digits", wanted), lowering=False)
record = dict(entry)
record.pop("digits", None)
entries.add(**params, **record, digits=entry.get("digits", wanted))
answer = submit_entries(
table,
entries,
message=message,
produced_by=_producer(generator, os.environ.get("NUMBERDB_ASSISTED_BY", "")),
upsert=False,
run=run,
rigour=generator.rigour,
)
for name, body in sorted(_source_files(generator).items()):
attach(table, name, body, run=run, message=message, rigour=generator.rigour)
return answer
if __name__ == "__main__":
_key_from_stdin()
generator = RandomKSATSatisfiabilityThresholds()
if "--publish" in sys.argv or os.environ.get("NUMBERDB_PUBLISH") == "1":
print(fill_draft_once(
generator,
message=(
"random k-SAT cavity-method satisfiability thresholds for 3 <= k <= 7, "
"transcribed from MMZ and checked against Krzakala et al."
),
))
else:
report = generator.verify(sample=None)
print(report)
sys.exit(0 if report.ok else 1)