# O(1) Transforms: Three Reductions from O(n) to Constant Time

**Status:** documented from existing codebase, not new work
**Date:** 2026-07-03
**Source files:** all three already exist in the repo

## 1. CRT Gradient Update: O(N²) → O(1) per crossing

**Source:** `docs/research/unified_crt_torus_dag.md` (lines 337-395)
**Formal:** `archive/.../SidonWrapping.lean`

### The Problem
After each braid crossing, the Sidon energy must be recomputed
to check if the new state is still Sidon (no pairwise-sum collisions).
Naive: recompute all C(N,2) pairwise sums = O(N²) per crossing step.

### The O(1) Reduction
The CRT residue gradient identity: each crossing changes only ONE
strand's residue. The energy change is:

```python
delta = -4 * crossing_sign * crossing_contribution / total_modulus
child_energy = node.energy + delta  # O(1): one add
```

The crossing contribution is precomputed once per DAG node. Each
crossing update is a single addition + modulo:

```python
def crossing_residue(residue_before: int, step: int, mod: int) -> int:
    return (residue_before + step) % mod  # one add, one modulo, no multiply
```

### Why It Works
The CRT residue system is ADDITIVE: adding one crossing to strand i
changes only residue_i, not the other strands. The energy is a
LINEAR function of the residues (via the gradient identity), so the
energy change is a linear function of the single residue change.
O(1) because: one residue changes → one gradient term → one add.

### The Mixedbread Connection
The braid word (which crossings happened) is stored as 1 bit per
crossing (binary document = low precision, dominates storage).
The residue update is the int8 query (high precision, short-lived).
Same asymmetric split as mixedbread's 32x storage reduction.

---

## 2. CRT Lift Closed Form: O(search) → O(1) formula

**Source:** `archive/.../SidonWrapping.lean` (lines 25-30)

### The Problem
Given two residues (r₁ mod L₁, r₂ mod L₂), find the unique integer
x ∈ [0, L₁·L₂) with those residues. Naive: search through O(L₁·L₂)
candidates, checking each. This is O(N) where N = L₁·L₂.

### The O(1) Reduction
The CRT gives a closed-form formula (no search):

```
x = r₁ + L₁ · ((r₂ − r₁) · L₁⁻¹ mod L₂)
```

where L₁⁻¹ is the modular inverse of L₁ modulo L₂.

One formula, O(1) arithmetic operations (one subtraction, one
multiply, one modulo, one add). No enumeration of candidates.

### Why It Works
The CRT guarantees uniqueness when gcd(L₁, L₂) = 1. The formula
IS the reconstruction — it doesn't search for the answer, it
COMPUTES it directly. The coprimality condition (gcd = 1) is the
precondition that makes the formula valid.

### The Observerless Observer Connection
This IS the dolphin protocol: two observers (moduli L₁, L₂) each
see one shadow (residue r₁, r₂). The CRT formula reconstructs the
coordinate x in O(1). No search, no enumeration — the formula is
the shortcut. The coprimality is the precondition (two observers
with coprime moduli can reconstruct; two observers with shared
factors lose information).

---

## 3. Adleman DNA Computing: O(2ⁿ) → O(1) wet-lab steps

**Source:** `archive/.../FOUNDATIONAL_GUIDANCE.md` (lines 19-25)
**Reference:** Lipton (1995), Science 268:542-545

### The Problem
SAT with n variables: try all 2ⁿ possible assignments. Naive:
exponential time on a sequential computer. O(2ⁿ) steps.

### The O(1) Reduction
Encode each variable as a DNA strand. Mix all strands in one test
tube. All 2ⁿ assignments form in parallel (10¹⁴ molecules reacting
simultaneously). The correct assignment is isolated by:

1. Ligation (O(1) wet-lab step: add enzyme, wait)
2. PCR amplification (O(1) wet-lab step: add primers, cycle)
3. Gel electrophoresis (O(1) wet-lab step: run gel, read band)
4. Sequencing (O(1) wet-lab step: sequence the band)

Total: O(1) wet-lab steps (constant number of lab operations,
independent of n). The parallelism is physical: 10¹⁴ molecules
= 10¹⁴ parallel processors, for free, in one tube.

### Why It Works
DNA hybridization is massively parallel by physics, not by
algorithm. Each molecule IS a processor. The "O(1)" is the
number of HUMAN steps (lab operations), not the number of
molecular interactions (which is still O(2ⁿ), but happens
in parallel, not sequentially).

### The Catch
- The O(1) is wet-lab steps, not computational complexity
- The DNA must be synthesized (O(n) synthesis cost)
- The readout (sequencing) is O(n) in practice
- Error rates grow with n (Adleman's original: 7 vertices)
- Scaling to large n is impractical with current technology

### The Honest Status
This is a PHYSICAL shortcut, not an algorithmic one. The
conservation law still holds: the information content of the
answer is O(n) bits, and you must read O(n) bits from the gel.
But the SEARCH (trying all 2ⁿ assignments) is done in parallel
by physics, not sequentially by algorithm.

---

## Can These Three Be Combined Into a Single Transform?

### The Common Structure
All three share the same pattern:

```
O(n) search  →  O(1) formula/physics  →  answer
```

| Transform | What's searched | What replaces it | O(1) mechanism |
|-----------|----------------|-----------------|-----------------|
| CRT gradient | All pairwise sums | Gradient identity | Additivity of CRT residues |
| CRT lift | All integers in range | Closed-form formula | Coprimality → unique solution |
| Adleman DNA | All 2ⁿ assignments | Parallel hybridization | Physical parallelism |

### The Unification

The three form a HIERARCHY of the same principle:

1. **CRT lift** = the COORDINATE level: O(1) reconstruction from
   two residues (the dolphin protocol, the observerless observer)

2. **CRT gradient** = the DYNAMICS level: O(1) energy update after
   a crossing (the braid evolution, the Sidon preservation check)

3. **Adleman DNA** = the SEARCH level: O(1) wet-lab steps for
   exponential search (the physical substrate, the weird machine)

A unified transform would chain them:

```
Input: NP problem instance (n variables)
  ↓ Adleman level: encode as DNA, hybridize in parallel (O(1) lab steps)
  ↓ CRT lift level: reconstruct coordinates from residues (O(1) formula)
  ↓ CRT gradient level: verify Sidon property via energy update (O(1) per crossing)
Output: answer (verified)
```

### The Combined Transform (conceptual)

```
def unified_transform(problem_instance):
    # Step 1: Adleman — encode and parallel-search
    dna_pool = encode_as_dna(problem_instance)       # O(n) synthesis
    hybridize(dna_pool)                              # O(1) wet-lab (physics)
    candidates = extract_valid(dna_pool)             # O(1) wet-lab (gel)

    # Step 2: CRT lift — reconstruct coordinates
    for candidate in candidates:
        residue_1 = observe(candidate, modulus_1)    # O(1) per observation
        residue_2 = observe(candidate, modulus_2)    # O(1) per observation
        coordinate = crt_lift(residue_1, residue_2)  # O(1) formula

    # Step 3: CRT gradient — verify in O(1) per crossing
        energy = initial_energy                       # O(1) precompute
        for crossing in braid_word(candidate):
            energy += crossing_gradient(crossing)    # O(1) per crossing
        if energy < threshold:
            return candidate  # verified Sidon/valid

    return None  # no valid candidate
```

### Is This a Single O(1) Transform?

**No.** The three operate at different levels:

- Adleman: O(1) SEARCH (but O(n) readout)
- CRT lift: O(1) RECONSTRUCTION (but O(n) observations needed)
- CRT gradient: O(1) per CROSSING (but O(n) crossings in the braid word)

The bottleneck is always O(n): you must read O(n) bits of the answer,
observe O(n) residues, or process O(n) crossings. The conservation law
governs: the answer has O(n) bits of information, and you must extract
all of them.

### What WOULD Make It O(1) End-to-End

If the THREE levels collapsed — if the search (Adleman), reconstruction
(CRT lift), and verification (CRT gradient) all happened in a SINGLE
physical step — the total would be O(1).

This requires:
- The DNA hybridization AND the CRT reconstruction AND the energy
  verification to happen simultaneously in the same physical process
- Not sequentially (search → reconstruct → verify) but in PARALLEL
  (search = reconstruct = verify in one step)

Is this possible? It's the "weird machine" at its most extreme:
- DNA = the linear carrier (the octagon)
- CRT = the linear formula (the spectral tool)
- Hybridization = the physical parallelism (the search)
- If all three are the SAME physical process → O(1) end-to-end

This would be: DNA that hybridizes INTO a CRT-reconstructing structure
that self-verifies via the gradient identity. One test tube, one step,
answer out.

This is speculative. But the three transforms DO share the same
structure (O(n) search → O(1) formula/physics), and the hierarchy
(search → reconstruct → verify) is the natural pipeline order.

### The Honest Assessment

The three can be CHAINED (each feeds the next), but not MERGED into
a single O(1) step. The bottleneck is always the O(n) information
extraction. The conservation law prevents O(1) end-to-end: the answer
has O(n) bits, and reading O(n) bits takes O(n) time.

BUT: the three can be PIPELINED — while one candidate is being
verified (CRT gradient), the next is being reconstructed (CRT lift),
and the next batch is being searched (Adleman). This gives O(1)
AMORTIZED time per candidate (throughput, not latency).

This is the same pattern as the compression findings: amortized O(1)
is real (frozen model + arithmetic coder), self-contained O(1) is not
(model must ship = conservation law).