Linear Algorithm and Density Asymptotics for Huang's Quadratic Form

Let G = N a, b be the gap set of the numerical semigroup generated by coprime $a < b$, and $N = |G|$. Yifeng Huang (2026) defined the quadratic form Q(n) = ∑ K(j-i) nᵢ nⱼ on RG, where K(d) = 1d ≥ 0 - 1d ≥ a - 1d ≥ b + 1d ≥ a+b, and showed that it recovers the dinv statistic on rational Dyck paths. The naive evaluation of Q requires O(N²) operations. This paper extends these findings in two main directions: Linear-Time Evaluation ($O(N)$ Algorithm): We prove that the interval structure of K allows one to reduce Q to a linear combination of sliding-window sums, yielding an $O(N)$ algorithm (Theorem 1.1). Generalization to n Generators: We generalize the framework to semigroups p₁, ..., pₙ with n generators. The generalized kernel K⁽ⁿ⁾, defined by inclusion-exclusion with 2ⁿ terms, has at most w(n) ≤ σₙ active windows due to parity cancellation. These windows are computable incrementally in time O(n · σₙ) (Theorem 1.2). Empirically, w(n) ~ σₙ while w(n) 2ⁿ: exponential combinatorics reduces to a sparse interval structure. For a sequence of pairwise distinct integers pᵢ ≥ 2 satisfying log pₙ = o(n), we prove that the density of active windows becomes asymptotically negligible relative to the semigroup density (Theorem 1.5): w(n)/2ⁿ - 1 = o(∏ᵢ₌₁ⁿ (1 - 1/pᵢ)), n → ∞