Summary

Implement the random rotation matrix Π used by PolarQuant. This is the first mathematical building block — everything else depends on it.

Paper Reference

• Paper: arXiv 2504.19874, Section 1.3 and Algorithm 1
• Key property: Random rotation makes each coordinate follow Beta(d/2, d/2) → Gaussian N(0, 1/d) for large d
• The rotation must be Haar-distributed (uniformly random orthogonal matrix)

Requirements

Dense rotation (primary)

• Generate Haar-distributed random rotation via QR decomposition of Gaussian matrix
• Ensure det(Π) = +1 (proper rotation, not reflection) by correcting signs via diagonal of R
• Must be deterministic given a seed (for reproducibility)
• Input: dimension d, NumPy random generator
• Output: orthogonal matrix Π ∈ R^(d×d)

Fast structured rotation (optimization, can be deferred)

• Walsh-Hadamard + random sign flips: O(d log d) instead of O(d²)
• Pad to next power of 2
• Separate apply_fast_rotation and apply_fast_rotation_transpose functions
• Batch version for multiple vectors

Tests Required (write FIRST)

1. Orthogonality test: Π @ Π.T ≈ I (within numerical tolerance)
2. Determinant test: det(Π) ≈ +1
3. Deterministic test: same seed → same matrix
4. Different seeds test: different seeds → different matrices
5. Rotation preserves norms: ||Π @ x|| ≈ ||x|| for random x
6. Rotation preserves inner products: ⟨Π@x, Π@y⟩ ≈ ⟨x, y⟩
7. Post-rotation distribution test: after rotating many random unit vectors, each coordinate should have mean ≈ 0 and variance ≈ 1/d
8. Fast rotation matches dense (if implemented): apply_fast_rotation(x) produces similar statistical properties

Acceptance Criteria

• Tests written and reviewed with codex BEFORE implementation
• Implementation passes all tests
• codex-review on implementation
• Roast review on implementation
• Coverage >95% for rotation.py