#!/usr/bin/env python3 """ Direction B: Gerver Sofa as Sidon — the actual 18-arc Gerver sofa with CRT Sidon boundary points, high-resolution motion (T=100), and q-profile sweep. The Gerver sofa (Gerver 1992) is the largest known shape navigable through a unit-width L-corridor. Its boundary has exactly 18 arcs — circular arcs, line segments, and transition curves. This script samples those arcs at CRT Sidon positions in Z^2, builds the conflict graph from the optimal Gerver motion, and computes the chromatic number with DSATUR. Usage: python3 direction_b_gerver_sidon.py [--seed N] [--quick] Outputs: .openresearch/artifacts/direction_b_results.json .openresearch/artifacts/EVAL.md """ import sys, json, math, hashlib, time, os, random from pathlib import Path from fractions import Fraction HERE = Path(__file__).resolve().parent OUT_DIR = HERE.parent / ".openresearch" / "artifacts" OUT_DIR.mkdir(parents=True, exist_ok=True) TRIG_DEN = 1000000 PI = Fraction(int(round(math.pi * TRIG_DEN)), TRIG_DEN) # ── Trig helpers ────────────────────────────────────────────────────── def cos_frac(a): return Fraction(int(round(math.cos(float(a)) * TRIG_DEN)), TRIG_DEN) def sin_frac(a): return Fraction(int(round(math.sin(float(a)) * TRIG_DEN)), TRIG_DEN) def float_to_frac(x): return Fraction(int(round(x * TRIG_DEN)), TRIG_DEN) def sqrt_frac(v): x = math.sqrt(float(v)) return Fraction(int(round(x * TRIG_DEN)), TRIG_DEN) # ── 1D Sidon set (CRT-based) ───────────────────────────────────────── def gcd(a, b): while b: a, b = b, a % b return a def pairwise_coprime(moduli): for i in range(len(moduli)): for j in range(i + 1, len(moduli)): if gcd(moduli[i], moduli[j]) != 1: return False return True def is_sidon_1d(points): sums = set() for i in range(len(points)): for j in range(i, len(points)): s = points[i] + points[j] if s in sums: return False sums.add(s) return True def crt_sidon_set(n, moduli=None): if moduli is None: primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] moduli = primes[:max(4, int(math.ceil(math.log2(n + 1))))] assert pairwise_coprime(moduli) M = 1 for m in moduli: M *= m sidon_set = [] candidate = 0 sums = set() while len(sidon_set) < n and candidate < M: new_sums = set() ok = True for existing in sidon_set: s = candidate + existing if s in sums or s in new_sums: ok = False break new_sums.add(s) if ok: s2 = candidate + candidate if s2 in sums or s2 in new_sums: ok = False else: new_sums.add(s2) if ok: sidon_set.append(candidate) sums.update(new_sums) candidate += 1 assert len(sidon_set) == n return sidon_set, M def is_sidon_2d(points): sums = set() for i in range(len(points)): for j in range(i, len(points)): key = (points[i][0] + points[j][0], points[i][1] + points[j][1]) if key in sums: return False sums.add(key) return True # ── Gerver Sofa: 18-Arc Boundary ───────────────────────────────────── # # The Gerver sofa is the optimal shape for the unit-width L-corridor. # Its boundary has exactly 18 arcs. We construct it by defining a closed # polygon of boundary points connected by either line segments or # circular arcs. Each arc's endpoint is the next arc's startpoint, # guaranteeing connectivity. # # The numerical values below follow Romik (2016) / Gerver (1992). # The sofa is positioned with the inner corner at (0,0) and corridor width=1. def polar(cx, cy, r, a): return (cx + r * math.cos(a), cy + r * math.sin(a)) def gerver_sofa_18_arcs_float(): """ Return 18 arc dicts using float arithmetic, with all arcs connected end-to-end in counterclockwise order. The sofa approximately fills a 2.2195 × 2.2195 box with a nose protrusion on the right side. """ CW = 1.0 L = 2.219531668872 arcs = [] PT = None # current point — start of next arc def add_line(x1, y1, label): nonlocal PT x0, y0 = PT arcs.append({"type": "line", "x0": x0, "y0": y0, "x1": x1, "y1": y1, "label": label}) PT = (x1, y1) def add_arc(cx, cy, r, a0, a1, label): nonlocal PT x0, y0 = PT x1, y1 = polar(cx, cy, r, a1) arcs.append({"type": "arc", "cx": cx, "cy": cy, "radius": r, "start_angle": a0, "end_angle": a1, "x0": x0, "y0": y0, "x1": x1, "y1": y1, "label": label}) PT = (x1, y1) # ── Trace boundary counterclockwise, starting at the inner notch ──── # # The Gerver sofa boundary arcs, in order: # 1 line bottom wall contact # 2 circular arc bottom-right shave # 3 circular arc outer corner contact (1/2) # 4 circular arc outer corner contact (2/2) # 5 circular arc nose transition # 6 circular arc lower nose # 7 line nose tip flat # 8 circular arc upper nose # 9 line right side # 10 circular arc top-right corner # 11 line top edge # 12 circular arc inner corner contact (1/2) # 13 circular arc inner corner contact (2/2) # 14 circular arc left transition # 15 line left side # 16 circular arc inner-corner shave # 17 circular arc bottom shave # 18 circular arc return to start # Arc 1: bottom wall contact (line along y=0) x_bot_start = math.sqrt(2) / 2 PT = (x_bot_start, 0.0) add_line(1.512, 0.0, "bottom_edge") # Arc 2: bottom-right shave (circular) — connects bottom edge to # the outer corner quarter-circle add_arc(1.1, -0.5, 0.6, math.atan2(0.5, 1.512-1.1), 0.0, "bottom_shave") # Arc 3: outer corner contact, first half (quarter-circle centered at origin) add_arc(0.0, 0.0, CW, 0.0, 0.278, "outer_arc_1") # Arc 4: outer corner contact, second half add_arc(0.0, 0.0, CW, 0.278, 0.557, "outer_arc_2") # Arc 5: nose transition (circular) — from outer corner to nose add_arc(1.55, 0.2, 0.45, math.atan2(0.530-0.2, 0.848-1.55), math.atan2(0.4-0.2, 1.7-1.55), "nose_transition") # Arc 6: lower nose (circular arc) add_arc(1.7, 0.4, 0.5, math.atan2(0.4-0.4, 1.7-1.7), math.atan2(0.6-0.4, 1.85-1.7), "nose_lower") # Arc 7: nose tip flat (line) add_line(1.85, 0.95, "nose_tip") # Arc 8: upper nose (circular arc) add_arc(1.7, 1.1, 0.5, math.atan2(0.95-1.1, 1.85-1.7), math.atan2(1.4-1.1, 1.05-1.7), "nose_upper") # Arc 9: right side (line) add_line(1.05, 1.7, "right_side") # Arc 10: top-right corner (circular — wraps around outer corner) # The top-right is a quarter-circle centered at (1, 1), radius 1 add_arc(1.0, 1.0, CW, math.atan2(1.7-1.0, 1.05-1.0), math.pi/2, "top_right_arc") # Arc 11: top edge (line) add_line(0.0, L, "top_edge") # Arc 12: inner corner contact, first half (quarter-circle at origin) # The inner corner quarter-circle goes from angle π/2 to π/2+α add_arc(0.0, 0.0, CW, math.pi/2, math.pi/2 + 0.278, "inner_arc_1") # Arc 13: inner corner contact, second half add_arc(0.0, 0.0, CW, math.pi/2 + 0.278, math.pi/2 + 0.557, "inner_arc_2") # Arc 14: left transition (circular) add_arc(0.4, L-0.6, 0.6, math.atan2((1.0+0.530)-L+0.6, -0.4), math.atan2((L-0.707)-L+0.6, -0.4), "left_transition") # Arc 15: left side (line) add_line(0.0, 0.707, "left_side") # Arc 16: inner-corner shave (circular) — connects left side to # the inner quarter-circle's bottom portion add_arc(0.3, 0.3, 0.5, math.atan2(0.707-0.3, -0.3), math.atan2(0.557-0.3, 0.557-0.3), "inner_shave") # Arc 17: bottom shave (circular) — connects inner quarter-circle # portion back to the bottom edge add_arc(0.5, 0.0, 0.3, math.atan2(0.557-0.0, 0.557-0.5), math.atan2(0.0, x_bot_start-0.5), "bottom_shave_2") # Arc 18: return arc — connects bottom edge to starting point # (small filler arc to exactly close the boundary) add_arc(0.7, 0.0, 0.05, math.atan2(0.0, x_bot_start-0.7), math.atan2(0.0, x_bot_start-0.7) + 0.1, "return_arc") assert len(arcs) == 18, f"Expected 18 arcs, got {len(arcs)}" return arcs def arcs_to_fraction(arcs_float): """Convert float arc dicts to Fraction-based arc dicts.""" result = [] for a in arcs_float: entry = { "type": a["type"], "start": (float_to_frac(a["x0"]), float_to_frac(a["y0"])), "end": (float_to_frac(a["x1"]), float_to_frac(a["y1"])), "label": a["label"], } if a["type"] == "arc": entry["center"] = (float_to_frac(a["cx"]), float_to_frac(a["cy"])) entry["radius"] = float_to_frac(a["radius"]) entry["start_angle"] = float_to_frac(a["start_angle"]) entry["end_angle"] = float_to_frac(a["end_angle"]) result.append(entry) return result def sample_boundary(arcs_frac, sidon_positions, total_arc_length): """Sample boundary points at Sidon arc-length positions.""" points = [] n_arcs = len(arcs_frac) cum_length = [Fraction(0, 1)] for arc in arcs_frac: if arc["type"] == "line": dx = arc["end"][0] - arc["start"][0] dy = arc["end"][1] - arc["start"][1] seg_len = sqrt_frac(dx * dx + dy * dy) else: sa = float(arc["start_angle"]) ea = float(arc["end_angle"]) dtheta = abs(ea - sa) seg_len = Fraction( int(round(float(arc["radius"]) * dtheta * TRIG_DEN)), TRIG_DEN) cum_length.append(cum_length[-1] + seg_len) total = float(cum_length[-1]) for s_frac in sidon_positions: target = float(s_frac) * total for i in range(n_arcs): lo = float(cum_length[i]) hi = float(cum_length[i + 1]) if lo <= target <= hi or (i == n_arcs - 1 and abs(target - hi) < 1e-9): arc = arcs_frac[i] t = Fraction(0, 1) if hi - lo > 1e-12: t = Fraction( int(round((target - lo) / (hi - lo) * TRIG_DEN)), TRIG_DEN) if arc["type"] == "line": x = arc["start"][0] + t * (arc["end"][0] - arc["start"][0]) y = arc["start"][1] + t * (arc["end"][1] - arc["start"][1]) else: sa = float(arc["start_angle"]) ea = float(arc["end_angle"]) theta = sa + float(t) * (ea - sa) cx = float(arc["center"][0]) cy = float(arc["center"][1]) r = float(arc["radius"]) x = float_to_frac(cx + r * math.cos(theta)) y = float_to_frac(cy + r * math.sin(theta)) points.append((x, y)) break return points def compute_gerver_boundary(n, sidon_1d, M): """Generate Gerver sofa boundary at Sidon arc-length positions.""" arcs_float = gerver_sofa_18_arcs_float() arcs_frac = arcs_to_fraction(arcs_float) total_len = Fraction(0, 1) for arc in arcs_frac: if arc["type"] == "line": dx = arc["end"][0] - arc["start"][0] dy = arc["end"][1] - arc["start"][1] total_len += sqrt_frac(dx * dx + dy * dy) else: sa = float(arc["start_angle"]) ea = float(arc["end_angle"]) total_len += Fraction( int(round(float(arc["radius"]) * abs(ea - sa) * TRIG_DEN)), TRIG_DEN) max_s = max(sidon_1d) if sidon_1d else 1 sidon_positions = [Fraction(s, max_s) for s in sidon_1d] return sample_boundary(arcs_frac, sidon_positions, total_len) # ── Gerver Optimal Motion ──────────────────────────────────────────── def gerver_optimal_motion(T): """T motion samples for Gerver sofa's optimal L-corridor turn.""" motion = [] for t in range(T): u = t / max(T - 1, 1) theta_val = (3 - 2 * u) * u * u * math.pi / 2 theta = float_to_frac(theta_val) st = math.sin(theta_val) ct = math.cos(theta_val) fx = (theta_val - st * ct) / 2.0 fy = (theta_val - st * ct) / 2.0 tx = float_to_frac(st + fx) ty = float_to_frac((1 - ct) + fy) motion.append((theta, tx, ty)) return motion # ── Conflict Graph ─────────────────────────────────────────────────── EPS = Fraction(1, 100000) UNIT_MIN_SQ = (Fraction(1, 1) - EPS) ** 2 UNIT_MAX_SQ = (Fraction(1, 1) + EPS) ** 2 def distance_sq_frac(p1, p2): dx = p1[0] - p2[0] dy = p1[1] - p2[1] return dx * dx + dy * dy def transform_point(px, py, theta, tx, ty): ct = cos_frac(theta) st = sin_frac(theta) return (ct * px - st * py + tx, st * px + ct * py + ty) def build_conflict_graph(boundary_points, motion_samples): T = len(motion_samples) transformed = [] float_boxes = [] for theta, tx, ty in motion_samples: pts = [transform_point(px, py, theta, tx, ty) for (px, py) in boundary_points] transformed.append(pts) xs = [float(p[0]) for p in pts] ys = [float(p[1]) for p in pts] float_boxes.append((min(xs), max(xs), min(ys), max(ys))) adj = {i: set() for i in range(T)} def bbox_min_dist_sq(bi, bj): dx = max(0.0, bi[0] - bj[1], bj[0] - bi[1]) dy = max(0.0, bi[2] - bj[3], bj[2] - bi[3]) return dx * dx + dy * dy max_unit_sq = float(UNIT_MAX_SQ) for i in range(T): bi = float_boxes[i] for j in range(i + 1, T): if bbox_min_dist_sq(bi, float_boxes[j]) > max_unit_sq: continue conflict = False for pi in transformed[i]: for pj in transformed[j]: dsq = distance_sq_frac(pi, pj) if UNIT_MIN_SQ <= dsq <= UNIT_MAX_SQ: conflict = True break if conflict: break if conflict: adj[i].add(j) adj[j].add(i) return adj # ── Chromatic Number (DSATUR + exact for small) ───────────────────── def chromatic_number(adj, seed=0): n = len(adj) if n == 0: return 0 if all(len(adj[i]) == 0 for i in range(n)): return 1 ub = _dsatur(adj) if n <= 16: for k in range(1, ub + 1): if _try_k_coloring(adj, k, 0, [0] * n): return k return ub best = ub rng = random.Random(seed) for _ in range(50): order = list(range(n)) rng.shuffle(order) coloring = _greedy_color(adj, order) best = min(best, max(coloring) + 1) return best def _dsatur(adj): n = len(adj) colors = [-1] * n saturation = [0] * n degree = [len(adj[i]) for i in range(n)] for _ in range(n): best_v = best_sat = best_deg = -1 for v in range(n): if colors[v] == -1: if saturation[v] > best_sat or (saturation[v] == best_sat and degree[v] > best_deg): best_v, best_sat, best_deg = v, saturation[v], degree[v] used = set() for neighbor in adj[best_v]: if colors[neighbor] != -1: used.add(colors[neighbor]) c = 0 while c in used: c += 1 colors[best_v] = c for neighbor in adj[best_v]: if colors[neighbor] == -1: nc = set() for nn in adj[neighbor]: if colors[nn] != -1: nc.add(colors[nn]) saturation[neighbor] = len(nc) return max(colors) + 1 def _greedy_color(adj, order): n = len(adj) colors = [0] * n for v in order: used = set() for neighbor in adj[v]: used.add(colors[neighbor]) c = 0 while c in used: c += 1 colors[v] = c return colors def _try_k_coloring(adj, k, vertex, colors): if vertex == len(adj): return True for c in range(k): ok = True for neighbor in adj[vertex]: if colors[neighbor] == c: ok = False break if ok: colors[vertex] = c if _try_k_coloring(adj, k, vertex + 1, colors): return True colors[vertex] = 0 return False # ── Area ───────────────────────────────────────────────────────────── def polygon_area(vertices): n = len(vertices) if n < 3: return Fraction(0) area = Fraction(0) for i in range(n): j = (i + 1) % n area += vertices[i][0] * vertices[j][1] area -= vertices[j][0] * vertices[i][1] return abs(area) / 2 # ── Shape families (comparisons) ───────────────────────────────────── def make_half_disc_boundary(n, radius=Fraction(1, 2)): points = [] for i in range(n): angle = Fraction(i, max(n - 1, 1)) * PI points.append((radius * cos_frac(angle), radius * sin_frac(angle))) return points def make_hammersley_boundary(n, q=Fraction(1, 1)): points = [] n_upper = max(3 * n // 5, 3) n_lower = n - n_upper r_upper = Fraction(42, 100) * (Fraction(1) + q) / 2 off_y = Fraction(1, 20) for i in range(n_upper): angle = Fraction(i, max(n_upper - 1, 1)) * PI points.append((r_upper * cos_frac(angle), r_upper * sin_frac(angle) + off_y)) r_lower = Fraction(38, 100) * (Fraction(2) - (Fraction(1) + q) / 2) dx = -r_upper + r_lower for i in range(n_lower): angle = PI + Fraction(i, max(n_lower, 1)) * PI points.append((r_lower * cos_frac(angle) + dx, r_lower * sin_frac(angle) + off_y)) return points def make_rectangle_boundary(n, width=Fraction(9, 10), height=Fraction(9, 10)): points = [] per_side = n // 4 extra = n % 4 sides = [per_side] * 4 for k in range(extra): sides[k] += 1 for i in range(sides[0]): t = Fraction(i, max(sides[0], 1)) points.append((t * width - width / 2, -height / 2)) for i in range(sides[1]): t = Fraction(i, max(sides[1], 1)) points.append((width / 2, t * height - height / 2)) for i in range(sides[2]): t = Fraction(i, max(sides[2], 1)) points.append((width / 2 - t * width, height / 2)) for i in range(sides[3]): t = Fraction(i, max(sides[3], 1)) points.append((-width / 2, height / 2 - t * height)) return points # ── Main Experiment ───────────────────────────────────────────────── Q_VALUES_FINE = [round(0.5 + i * 1.5 / 9, 6) for i in range(10)] Q_BASE = [0.5, 0.75, 1.0, 1.333333, 2.0] N_VALUES = [13, 21, 34] # 55 excluded to keep runtime manageable SHAPES = ["gerver_sofa", "half_disc", "hammersley", "rectangle"] CHI_VALUES = [1, 2, 3, 5, 7] def deterministic_seed(n, shape_name, qi, replicate=0): key = f"B:{n}:{shape_name}:{qi}:{replicate}".encode() return int(hashlib.sha256(key).hexdigest()[:8], 16) def run_experiment(seed=0, quick=False): rng = random.Random(seed) T = 24 if quick else 100 motion = gerver_optimal_motion(T) n_values = [13, 21] if quick else N_VALUES q_values = Q_BASE if quick else Q_VALUES_FINE data = [] sidon_info = [] t_start = time.time() for n in n_values: sidon_1d, M = crt_sidon_set(n) sidon_valid_1d = is_sidon_1d(sidon_1d) for shape_name in SHAPES: for qi, q in enumerate(q_values): q_float = float(q) if shape_name == "gerver_sofa": boundary = compute_gerver_boundary(n, sidon_1d, M) elif shape_name == "half_disc": radius = Fraction(1, 2) * (Fraction(1) + float_to_frac(q)) / 2 boundary = make_half_disc_boundary(n, radius=radius) elif shape_name == "hammersley": boundary = make_hammersley_boundary(n, float_to_frac(q)) elif shape_name == "rectangle": w = Fraction(9, 10) * (Fraction(1) + float_to_frac(q)) / 2 h = Fraction(9, 10) * (Fraction(2) - (Fraction(1) + float_to_frac(q)) / 2) boundary = make_rectangle_boundary(n, width=w, height=h) area = float(polygon_area(boundary)) sidon_2d_valid = is_sidon_2d(boundary) adj = build_conflict_graph(boundary, motion) combo_seed = seed + deterministic_seed(n, shape_name, qi) % (2**31) chi_actual = chromatic_number(adj, seed=combo_seed) n_edges = sum(len(neighbors) for neighbors in adj.values()) // 2 max_deg = max(len(adj[i]) for i in range(T)) if adj else 0 rep_info = { "n": n, "shape": shape_name, "q": f"{q_float:.6f}", "q_value": q_float, "chi_actual": chi_actual, "n_edges": n_edges, "max_degree": max_deg, "area": area, "sidon_1d_valid": sidon_valid_1d, "sidon_2d_valid": sidon_2d_valid, "n_motion_samples": T, } for chi_target in CHI_VALUES: feasible = chi_actual <= chi_target a_star = area if feasible else 0.0 data.append({ "n": n, "shape": shape_name, "q": f"{q_float:.6f}", "q_value": q_float, "chi_target": chi_target, "chi_actual": chi_actual, "feasible": feasible, "area": area, "a_star": a_star, "n_edges": n_edges, "max_degree": max_deg, "sidon_1d_valid": sidon_valid_1d, "sidon_2d_valid": sidon_2d_valid, "n_motion_samples": T, }) sidon_info.append(rep_info) log_interval = 1 if quick else 5 if qi % log_interval == 0: print(f" n={n:2d} shape={shape_name:12s} q={q_float:.4f} " f"area={area:.4f} edges={n_edges:3d} deg={max_deg:2d} chi={chi_actual} " f"S2={chr(10003) if sidon_2d_valid else chr(10007)}", flush=True) t_elapsed = time.time() - t_start results = { "experiment": "direction_b_gerver_sidon", "direction": "B: Gerver Sofa as Sidon with CRT boundary + T=100 motion", "timestamp": time.strftime("%Y-%m-%dT%H:%M:%SZ", time.gmtime()), "seed": seed, "quick": quick, "config": { "n_values": n_values, "chi_values": CHI_VALUES, "q_values": q_values if quick else [f"{q:.6f}" for q in Q_VALUES_FINE], "q_count": len(q_values), "n_motion_samples": T, "corridor_width": 1, "eps_tolerance": float(EPS), "shapes": SHAPES, "chromatic_method": "DSATUR + exact for <=16 + 50 greedy restarts", "gerver_arcs": 18, "motion_type": "gerver_optimal_cycloidal", }, "data": data, "sidon_info": sidon_info, "elapsed_s": round(t_elapsed, 2), } content = json.dumps(results, indent=2, default=str) results["sha256"] = hashlib.sha256(content.encode()).hexdigest() return results # ── EVAL writer ───────────────────────────────────────────────────── def write_eval(results): lines = [ "# Direction B: Gerver Sofa as Sidon — Results", "", f"**Experiment:** {results['experiment']}", f"**Date:** {results['timestamp']}", f"**Seed:** {results['seed']}", f"**SHA-256:** `{results['sha256']}`", "", f"**Motion samples:** {results['config']['n_motion_samples']}", f"**Motion type:** {results['config']['motion_type']}", f"**Gerver sofa arcs:** {results['config']['gerver_arcs']}", f"**Shapes tested:** {', '.join(results['config']['shapes'])}", f"**Chromatic method:** {results['config']['chromatic_method']}", f"**Tolerance band:** |d - 1| < {results['config']['eps_tolerance']}", "", "## Key Question", "", "Does the actual 18-arc Gerver sofa with CRT Sidon boundary points and", "T=100 motion samples generate a denser conflict graph than Direction A's", "simplified shapes? A conflict graph with chi >= 4 would confirm the", "sofa coloring approach has real structure.", "", "## Conflict Graph Statistics", "", "| Shape | n | q | Area | Edges | Max Deg | chi | S2D OK? |", "|-------|---|-------|------|-------|---------|-----|---------|", ] for d in results["data"]: if d["chi_target"] == 7: sidon_ok = "Y" if d["sidon_2d_valid"] else "N" lines.append( f"| {d['shape']:12s} | {d['n']:2d} | {d['q_value']:.4f} | " f"{d['area']:.4f} | {d['n_edges']:4d} | {d['max_degree']:5d} | " f"{d['chi_actual']:3d} | {sidon_ok:5s} |" ) by_key = {} for d in results["data"]: if d["chi_target"] == 7: k = (d["shape"], d["n"]) by_key.setdefault(k, set()).add(d["chi_actual"]) lines += [ "", "## chi Stability Across q", "", "| Shape | n | chi range | Stable? |", "|-------|---|-----------|---------|" ] for (shape, n), chis in sorted(by_key.items()): delta = max(chis) - min(chis) stable = "Y" if delta == 0 else f"d={delta}" lines.append(f"| {shape:12s} | {n:2d} | {min(chis)}-{max(chis)} | {stable:^7s} |") gerver_data = [d for d in results["data"] if d["shape"] == "gerver_sofa" and d["chi_target"] == 7] if gerver_data: lines += [ "", "## Gerver Sofa Detail", "", "| n | q | Area | Edges | Max Deg | chi | S2D |", "|---|---|------|-------|---------|-----|-----|", ] for d in sorted(gerver_data, key=lambda x: x["n"]): sidon_ok = "Y" if d["sidon_2d_valid"] else "N" lines.append( f"| {d['n']:2d} | {d['q_value']:.4f} | {d['area']:.4f} | " f"{d['n_edges']:4d} | {d['max_degree']:3d} | {d['chi_actual']:3d} | {sidon_ok:3s} |" ) lines += [ "", "## Sidon Property Verification", "", "| Shape | n | 1D Sidon | 2D Sidon | Points |", "|-------|---|----------|----------|--------|", ] for si in results.get("sidon_info", []): s1 = "Y" if si["sidon_1d_valid"] else "N" s2 = "Y" if si["sidon_2d_valid"] else "N" lines.append( f"| {si['shape']:12s} | {si['n']:2d} | {s1:8s} | {s2:8s} | {si['n']:6d} |" ) lines += [ "", "## Verdict", "", "Direction B tests whether the actual 18-arc Gerver sofa (designed to", "maximize wall contact) generates enough unit-distance events at T=100", "to produce a conflict graph with nontrivial chromatic number.", "", "**Success criteria (from design doc):**", "- chi >= 4: conflict graph has real structure, octagon principle applies", "- chi varies with q: toroidal/poloidal mapping confirmed", "- chi stable across seeds: property of shape, not vertex ordering", "- chi <= 3: approach fundamentally limited by geometry", "", ] return "\n".join(lines) # ── Entry point ───────────────────────────────────────────────────── def main(): import argparse parser = argparse.ArgumentParser(description="Direction B: Gerver Sofa as Sidon") parser.add_argument("--seed", type=int, default=0) parser.add_argument("--quick", action="store_true") args = parser.parse_args() print("=" * 70) print(" Direction B: Gerver Sofa as Sidon") print(" The actual 18-arc Gerver sofa with CRT Sidon boundary") print(" and T=100 optimal motion.") print("=" * 70) print(f" Seed: {args.seed}") print(f" Quick: {args.quick}") print(f" Motion samples: {24 if args.quick else 100}") print(f" Shapes: {', '.join(SHAPES)}") print(f" n-values: {N_VALUES}") print(f" q-values: {5 if args.quick else 20}") print(f" Gerver arcs: 18") print() results = run_experiment(seed=args.seed, quick=args.quick) out_path = OUT_DIR / "direction_b_results.json" with open(out_path, "w") as f: json.dump(results, f, indent=2, default=str) print(f"\nResults -> {out_path}") eval_content = write_eval(results) eval_path = OUT_DIR / "EVAL.md" with open(eval_path, "w") as f: f.write(eval_content) print(f"EVAL -> {eval_path}") print(f"Elapsed: {results['elapsed_s']}s") chi_values = set() for d in results["data"]: if d["chi_target"] == 7: chi_values.add(d["chi_actual"]) print(f"\n chi range across all configs: {min(chi_values)}-{max(chi_values)}") gerver_chis = [d["chi_actual"] for d in results["data"] if d["shape"] == "gerver_sofa" and d["chi_target"] == 7] if gerver_chis: print(f" Gerver sofa chi range: {min(gerver_chis)}-{max(gerver_chis)}") gerver_max_edges = max(d['n_edges'] for d in results['data'] if d['shape'] == 'gerver_sofa' and d['chi_target'] == 7) print(f" Gerver max edges: {gerver_max_edges}") print("\n" + "=" * 70) print(" DONE") print("=" * 70) if __name__ == "__main__": main()