Parallel DAG Scheduling and Direct Coordinate Geometry for Sublinear Dirichlet Summatory Algorithms

Summatory arithmetic functions—such as the Mertens function M(X) = sumn <= X mu(n), Euler's totient summatory function Phi(X) = sumn <= X phi(n), and the prime counting function pi(X)—are central to computational and analytic number theory. While sublinear dynamic programming algorithms over integer hyperbola states V(X) = {floor(X/i) : 1 <= i <= X} evaluate these functions in O(X3/4) sequential work, existing implementations rely on runtime dynamic memory lookups (inducing hash collisions or binary search overhead) and have historically been executed sequentially due to loop-carried state dependencies. In this paper, we establish two primary theoretical and algorithmic results: 1. Direct Coordinate Bijection: We prove that the state space V(X) admits an exact, order-preserving arithmetic bijection tau: V(X) -> {0, 1, ..., |V(X)|-1} computable in O(1) elementary operations, eliminating hash tables, dynamic memory allocations, and search overhead entirely. 2. Doubling-Stage DAG Decomposition Theorem: We prove that the dependency directed acyclic graph (DAG) of the Dirichlet hyperbola recurrence partitions into exactly K + 1 = ceil(log2 X) + 1 independent antichains (V_0 = {1} and V_m = {v in V(X) : 2ᵐ⁻¹ < v <= 2^m} for 1 <= m <= K). This structure enables lock-free, communication-free parallel evaluation with total work W(X) = Theta(X3/4) and critical path span T_infinity(X) = Theta(sqrt(X)) (reducible to O(log^2 X) via parallel inner tree reduction), establishing an asymptotic parallel speedup of Omega(X1/4). We implement this architecture in an open-source C++20 template library supporting arbitrary Dirichlet convolutions across multi-core CPUs (OpenMP), Apple Metal GPU, and NVIDIA CUDA. We report empirical benchmarks scaling up to X = 10¹⁶ (10 quadrillion), computing M(10¹²) = 62,366 in 0.20 seconds, M(10¹⁴) = -875,575 in 6.12 seconds, M(10¹⁵) = -3,216,373 in 79.56 seconds, and M(10¹⁶) = -3,195,437 in 622.43 seconds (~10.37 minutes) on a consumer workstation with 8 parallel worker threads (Apple M1 8-core CPU). Source Code: https://github.