SilverSight/docs/research/iteration_dag.md

CRT Torus Embedding: Iteration DAG

Open Direction #1 — tracing iteration paths through modulus space.

---

1. DAG Structure

The iteration of F with parameter regeneration forms a Directed Acyclic Graph:

Nodes: (n, A_n, moduli_n, S_n, property_flags)

• n: step index
• A_n: current set (integer lifts)
• moduli_n: (L₁⁽ⁿ⁾, L₂⁽ⁿ⁾, …, Lₖ⁽ⁿ⁾)
• S_n: involution center
• property_flags: Sidon? B_h? Golomb?

Edges: (n, A_n, Ω_n, S_n) —[F]→ (n+1, A_{n+1}, Ω_{n+1}, S_{n+1})

• A_{n+1} = F_{Ω_n, S_n}(A_n) (apply F with current moduli)
• Ω_{n+1} = next moduli (from regeneration rule)
• S_{n+1} = next involution center (fixed or adaptive)

No cycles by design: each step changes moduli (geometric growth α, β ≥ 1), so Ω_n is strictly increasing in product M_n = ∏ L_i⁽ⁿ⁾. This prevents revisiting the same state, keeping the graph acyclic.

---

2. Regeneration Rules

Rule	Ω_{n+1}	S_{n+1}	Branching factor
Fixed	Ω_n (unchanged)	S_n	1 (deterministic)
Geometric	(α·L₁⁽ⁿ⁾, β·L₂⁽ⁿ⁾)	S_n	1 per (α,β) choice
Adaptive	chosen from candidate set	max(A_n)+min(A_n)
Exhaustive	primes from pool larger than current	either fixed or adaptive

The DAG explores all branches from adaptive/exhaustive rules.

---

3. Node Properties

Each node records:

Node {
  step: int
  A: List[int]           # current set (sorted)
  moduli: List[int]      # (L1, L2, ..., Lk)
  S: int                 # involution center
  M: int                 # product of moduli
  is_reflection_closed: bool   # A_n == S - A_n?
  is_injective: bool           # M > max(A)?
  sidon_status: bool           # is A_n a Sidon set?
  parent: Optional[NodeID]
  children: List[NodeID]
  depth: int
  terminal: bool               # no further steps possible
}

A node is terminal when:

• A_n is Sidon (goal reached), OR
• M_n > 2·max(A_n) (no-sum-alias regime — new collisions can't form, but wrapping could still break existing ones; if not already Sidon, try different moduli), OR
• A_n is F-invariant under current moduli (F(A_n) = A_n), OR
• No valid next moduli exist (Ω exhausted)

---

4. Path Tracing

A path through the DAG is a sequence of modulus choices:

Path P = (Ω₀, Ω₁, …, Ω_{m-1})
  where Ω_i = (L₁⁽ⁱ⁾, L₂⁽ⁱ⁾)

Each path transforms A₀ through m steps:

A₀ →[Ω₀] A₁ →[Ω₁] A₂ →[Ω₂] … →[Ω_{m-1}] A_m

Goal: find a path from A₀ to a Sidon set A_m.

Shortest path search

Since the DAG is acyclic (growing moduli), BFS finds the shortest path:

Queue ← [(A₀, Ω₀)]
While Queue not empty:
  (A, Ω) ← pop
  M ← product(Ω)
  if M > 2·max(A): continue (preservation regime, no improvement)
  for each candidate Ω' in next_moduli(Ω):
    A' ← F_{Ω', S}(A)
    if A' is Sidon: return path (success!)
    push (A', Ω')

---

5. Search Heuristics

Not all modulus choices are equally useful. Heuristics prune the search:

1. Prime preference — use small primes as moduli (2,3,5,7,…) for dense coverage of the [max(A), 2·max(A)] window.

2. Gap targeting — choose moduli that match differences found in Dₐ (the M-difference condition). This avoids creating new collisions.

3. Wrapping bias — prefer moduli where existing collisions wrap differently (condition (a) of the Sidon theorem).

4. Termination — stop expanding a branch when M > 2·max(A), since F can no longer improve the Sidon status (only preserve).

---

6. Implementation

See scripts/iteration_dag.py for the DAG tracing implementation.

Example trace:

A₀ = {1, 2, 5, 6}, S = 7, Ω₀ = (3, 4), M = 12
  → A₁ = {2, 5, 9, 10}, Sidon = True. Path length 1. ✓

A₀ = {0, 1, 3, 8, 13}, S = 27, Ω₀ = (3, 5), M = 15
  → A₁ = {12, 1, 9, 14, 4}, Sidon = False. New collision.
  → Try Ω₁ = (5, 7):
    → A₂ = F_{5,7}(A₁), M = 35. Check Sidon...

---

7. Connection to Braid DAG

The iteration DAG is the discrete version of the braid group Cayley graph. Each step F_{Ω,S} corresponds to a braid word: a sequence of generators σᵢ that act on the current configuration. The moduli Ω = (L₁, L₂, …, L₁₆) determine which generators are available (which strands cross).

In the full 16D chiral torus, each step applies a braid word, and the DAG traces the orbit of A₀ under the braid group action. A terminal Sidon node corresponds to a braid word that produces a collision-free configuration — a braid invariant.

---

8. Dual-Model DAG Implementation

The Chiral DAG (scripts/full_chiral_dag.py) combines both braid models:

Model	DAG action	Verifies	Verified
Axis-swap	σₛ swaps reflection moduli of strands s, s+1	YB, σ²=id, far commute	✓
Adjustment	crossing changes modulus values by ±2/±1	Coprimality bound	✓
Spacing tracking	capacity_left = min spacing / 2 per strand	Word length bound	✓

Node structure

Each DAG node stores:

• pairs: current chiral pairing (L_id, L_ref) per strand
• moduli: flattened 16-modulus vector
• A: current set (CRT lifts)
• M: product of all moduli
• capacity_left: max remaining crossings per strand
• braid_word: cumulative braid word from root to this node

Verified results (3-strand test, A₀ = [1,2,5,6])

Metric	Value
Nodes explored	65
Sidon paths found	3
Axis-swaps tried	43
Adjustments tried	21
Shortest braid word	σ₁
Root capacity	[6, 5, 5]
Max modulus (8-strand)	16637 < 32767 ✓

8-strand configuration

8 strands × 2 moduli = 16 moduli, all pairwise coprime (product of 4 distinct primes per strand). With spacing ~100+ between strands, capacity is 50+ crossings per strand.

Usage

from scripts.full_chiral_dag import ChiralDAG

dag = ChiralDAG(A0, S, n_strands=3, max_steps=8, max_branch=50)
dag.build(use_axis_swap=True, use_adjustment=True)
dag.summary()

# Export for visualization
dag.to_json("/path/to/export.json")