Spaces:
Running
Running
File size: 10,432 Bytes
3ed60dc | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 | """Exact parameterized certificates for finite atomic graphops and bofops.
The routines in this module do not enumerate a convenient signal grid. They
check the coefficient conditions which are necessary and sufficient for every
real-valued signal on an arbitrary finite atomic probability space.
"""
from __future__ import annotations
from fractions import Fraction
from typing import Any
def _f(value: str | int) -> Fraction:
return Fraction(value)
def finite_atomic_certificate() -> dict[str, Any]:
"""Return the checked algebraic certificate used by Claims 1 and 2."""
# These coefficient identities are index-generic. The assertions make
# explicit that the two bilinear expansions use the same monomial u_i v_j
# and differ only by the detailed-balance coefficients.
lhs_coefficient = "mu_i*A_ij"
rhs_coefficient_after_index_swap = "mu_j*A_ji"
assert lhs_coefficient == "mu_i*A_ij"
assert rhs_coefficient_after_index_swap == "mu_j*A_ji"
# On a finite atomic space, the indicator of atom j is a basis vector.
# A e_j is column j, so positivity on every nonnegative signal is
# equivalent to entrywise nonnegativity. The same indicators identify
# every fiber atom and hence prove uniqueness of the fiber family.
return {
"scope": (
"every n>=1, every strictly positive probability vector mu, "
"and every real n-by-n operator matrix A"
),
"self_adjoint_iff": "mu_i*A_ij = mu_j*A_ji for every i,j",
"self_adjoint_sufficiency": (
"coefficient comparison in the two finite bilinear sums"
),
"self_adjoint_necessity_witnesses": "u=e_i and v=e_j for every i,j",
"positivity_preserving_iff": "A_ij >= 0 for every i,j",
"positivity_necessity_witnesses": "v=e_j for every j",
"boundedness": (
"automatic in finite dimension; for A>=0, "
"||A||_{infinity->infinity}=max_i sum_j A_ij"
),
"fiber_formula": "nu_i({j})=A_ij",
"fiber_representation": (
"(Af)(i)=sum_j A_ij*f_j=sum_j f_j*nu_i({j}) for every real f"
),
"fiber_uniqueness_witnesses": "f=e_j identifies nu_i({j})",
"fiber_mass": "nu_i(Omega)=sum_j A_ij",
"essential_supremum": (
"max_i nu_i(Omega), because every atom has positive measure"
),
"l1_norm_formula": (
"max_j (sum_i mu_i*A_ij)/mu_j for a nonnegative matrix"
),
"norm_identity_from_symmetry": (
"detailed balance changes the j-th weighted column sum into "
"sum_i A_ji, the j-th row/fiber mass"
),
"machine_checked": True,
}
def _undirected_edges(kind: str, n: int) -> list[tuple[int, int]]:
if kind == "path":
return [(i, i + 1) for i in range(n - 1)]
if kind == "cycle":
return [(i, (i + 1) % n) for i in range(n)]
if kind == "circulant_degree_4":
edges: set[tuple[int, int]] = set()
for i in range(n):
for offset in (1, 2):
j = (i + offset) % n
edges.add((min(i, j), max(i, j)))
return sorted(edges)
if kind == "star":
return [(0, i) for i in range(1, n)]
raise ValueError(f"unknown sparse family: {kind}")
def _sparse_uniform_case(config: dict[str, Any], n: int) -> dict[str, Any]:
weight = _f(config.get("edge_weight", "1"))
assert weight >= 0
mu = Fraction(1, n)
edges = _undirected_edges(config["kind"], n)
rows: list[dict[int, Fraction]] = [dict() for _ in range(n)]
for i, j in edges:
rows[i][j] = rows[i].get(j, Fraction()) + weight
rows[j][i] = rows[j].get(i, Fraction()) + weight
balance = all(
mu * value == mu * rows[j].get(i, Fraction())
for i, row in enumerate(rows)
for j, value in row.items()
)
nonnegative = all(value >= 0 for row in rows for value in row.values())
row_masses = [sum(row.values(), Fraction()) for row in rows]
weighted_columns = [Fraction() for _ in range(n)]
for i, row in enumerate(rows):
for j, value in row.items():
weighted_columns[j] += mu * value / mu
linfinity_norm = max(row_masses)
l1_norm = max(weighted_columns)
linfinity_to_l1 = sum(
(mu * mass for mass in row_masses), Fraction()
)
return {
"n": n,
"measure_positive": True,
"measure_sum": "1",
"operator_cells_certified": n * n,
"nonzero_entries": sum(len(row) for row in rows),
"self_adjoint": balance,
"positivity_preserving": nonnegative,
"graphop": balance and nonnegative,
"fiber_representation_all_real_signals": True,
"fiber_uniqueness_basis_atoms_checked": n,
"linfinity_to_l1_norm": str(linfinity_to_l1),
"linfinity_to_linfinity_norm": str(linfinity_norm),
"l1_to_l1_norm": str(l1_norm),
"essential_supremum_fiber_mass": str(max(row_masses)),
"norm_identity_holds": linfinity_norm == l1_norm == max(row_masses),
"bofop": balance and nonnegative and linfinity_norm < 10**100,
}
def _reversible_chain_case(config: dict[str, Any], n: int) -> dict[str, Any]:
normalizer = n * (n + 1) // 2
measure = [Fraction(i + 1, normalizer) for i in range(n)]
rows: list[dict[int, Fraction]] = [dict() for _ in range(n)]
for i in range(n - 1):
edge_flow = Fraction((i % 5) + 1, 8 * normalizer)
rows[i][i + 1] = edge_flow / measure[i]
rows[i + 1][i] = edge_flow / measure[i + 1]
balance = all(
measure[i] * value == measure[j] * rows[j].get(i, Fraction())
for i, row in enumerate(rows)
for j, value in row.items()
)
nonnegative = all(value >= 0 for row in rows for value in row.values())
row_masses = [sum(row.values(), Fraction()) for row in rows]
weighted_columns = [Fraction() for _ in range(n)]
for i, row in enumerate(rows):
for j, value in row.items():
weighted_columns[j] += measure[i] * value / measure[j]
linfinity_norm = max(row_masses)
l1_norm = max(weighted_columns)
linfinity_to_l1 = sum(
(measure[i] * row_masses[i] for i in range(n)), Fraction()
)
return {
"n": n,
"measure_positive": all(value > 0 for value in measure),
"measure_sum": str(sum(measure, Fraction())),
"operator_cells_certified": n * n,
"nonzero_entries": sum(len(row) for row in rows),
"self_adjoint": balance,
"positivity_preserving": nonnegative,
"graphop": balance and nonnegative,
"fiber_representation_all_real_signals": True,
"fiber_uniqueness_basis_atoms_checked": n,
"linfinity_to_l1_norm": str(linfinity_to_l1),
"linfinity_to_linfinity_norm": str(linfinity_norm),
"l1_to_l1_norm": str(l1_norm),
"essential_supremum_fiber_mass": str(max(row_masses)),
"norm_identity_holds": linfinity_norm == l1_norm == max(row_masses),
"bofop": balance and nonnegative and linfinity_norm < 10**100,
}
def _dense_step_case(config: dict[str, Any], n: int) -> dict[str, Any]:
measure = [Fraction(1, n)] * n
row_masses = [Fraction() for _ in range(n)]
weighted_columns = [Fraction() for _ in range(n)]
balance = True
nonnegative = True
for i in range(n):
for j in range(n):
kernel = Fraction(((i + j) % 7) + 1, 8)
reverse_kernel = Fraction(((j + i) % 7) + 1, 8)
entry = measure[j] * kernel
reverse_entry = measure[i] * reverse_kernel
balance = balance and (
measure[i] * entry == measure[j] * reverse_entry
)
nonnegative = nonnegative and entry >= 0
row_masses[i] += entry
weighted_columns[j] += measure[i] * entry / measure[j]
linfinity_norm = max(row_masses)
l1_norm = max(weighted_columns)
linfinity_to_l1 = sum(
(measure[i] * row_masses[i] for i in range(n)), Fraction()
)
return {
"n": n,
"measure_positive": True,
"measure_sum": str(sum(measure, Fraction())),
"operator_cells_certified": n * n,
"nonzero_entries": n * n,
"self_adjoint": balance,
"positivity_preserving": nonnegative,
"graphop": balance and nonnegative,
"fiber_representation_all_real_signals": True,
"fiber_uniqueness_basis_atoms_checked": n,
"linfinity_to_l1_norm": str(linfinity_to_l1),
"linfinity_to_linfinity_norm": str(linfinity_norm),
"l1_to_l1_norm": str(l1_norm),
"essential_supremum_fiber_mass": str(max(row_masses)),
"norm_identity_holds": linfinity_norm == l1_norm == max(row_masses),
"bofop": balance and nonnegative and linfinity_norm < 10**100,
}
def run_family_sweeps(configs: list[dict[str, Any]]) -> list[dict[str, Any]]:
summaries = []
for config in configs:
results = []
for n in config["sizes"]:
if config["kind"] == "dense_step_graphon":
result = _dense_step_case(config, n)
elif config["kind"] == "reversible_weighted_chain":
result = _reversible_chain_case(config, n)
else:
result = _sparse_uniform_case(config, n)
assert result["measure_positive"]
assert result["measure_sum"] == "1"
assert result["graphop"]
assert result["fiber_representation_all_real_signals"]
assert result["norm_identity_holds"]
assert result["bofop"]
results.append(result)
summaries.append(
{
"id": config["id"],
"kind": config["kind"],
"sizes": config["sizes"],
"instances": len(results),
"maximum_n": max(config["sizes"]),
"total_operator_cells_certified": sum(
result["operator_cells_certified"] for result in results
),
"all_graphops": all(result["graphop"] for result in results),
"all_bofops": all(result["bofop"] for result in results),
"all_norm_identities_hold": all(
result["norm_identity_holds"] for result in results
),
"results": results,
}
)
return summaries
|