Primes in Legendre Intervals over F_q[t]: An Exact Explicit-Formula Algorithm, Verification for d <= 10, and an Anomaly in Characteristic 2

For a monic polynomial f in F_q[t] of degree d, the Legendre interval I_f = {f^2 + s : deg s <= d} is the function field analogue of [n^2, (n+1)^2]. The Hayes-Weil estimate shows that I_f contains an irreducible polynomial whenever q >= d-1 (see doi:10.5281/zenodo.23185896); the range q <= d-2 is open. We give an algorithm that computes the prime count Psi(f) = sumP in I_f Lambda(P) for all qᵈ⁻¹ intervals of a given (q, d) at once. It evaluates every Hayes L-function by a fast transform over the Hayes group, whose structure (an explicit basis for every F_q) we determine, and runs in about d^2 qᵈ⁻¹ operations instead of about q²ᵈ for testing every polynomial. Carried out in exact modular arithmetic (two primes and the Chinese remainder theorem), it proves that every Legendre interval contains an irreducible polynomial for every prime power q when d <= 10, and for q = 2 with d <= 25, q = 3 with d <= 16, q = 4 with d <= 13, and q = 5 with d <= 11. Each Hayes L-function has degree exactly m-2, where u^m is its conductor, with all inverse roots of absolute value sqrt(q); the computed numbers of L-functions of each degree match qᵐ⁻¹ - qᵐ⁻² exactly. For odd q the fluctuations of Psi across intervals follow the Keating-Rudnick variance (d-2) qᵈ⁺¹ and a Gaussian law already for q = 3, and the form factor of the L-functions equals an explicit arithmetic diagonal term for n <= d-1 and the circular unitary ensemble value beyond. In characteristic 2 the Legendre intervals form the subgroup of squares of the Hayes group, every element has the shape h^2 + t b^2, and the variance of Psi over them differs from the full-group value by factors between 0.33 and 21. This discrepancy is carried entirely by correlations between L-functions twisted by quadratic characters; its explanation is stated as an open problem. Code and data: https://github.com/Ruqing1963/legendre-intervals-explicit-formula