An Exact Fixed-Parameter Algorithm for Extremal Unions of Residue Classes

Let \(A=\{n_1<\cdots<n_r\}\) be a finite set of positive integers. Choose one residue class \(a_i\bmod n_i\) for each modulus and maximize the natural density of their union. This is the unsettled maximum-density half of Erdős Problem 278. We give an exact uniform characterization whose state space depends on \(r\) , not on the magnitudes of the moduli. To a residue tuple we attach the graph in which \(ij\) is an edge precisely when \(a_i\equiv a_j\pmod{\gcd(n_i,n_j)}\) . Inclusion–exclusion makes the covered density a clique-weighted function of this graph. For every forced edge set, a finite-abelian-group kernel calculation counts compatible tuples by a Smith-normal-form lattice index. Boolean Möbius inversion then counts the tuples with each exact graph. Maximizing over the graphs with positive count gives the exact extremal density.

The resulting factoring-free algorithm uses \(2^{O(r^2)}\operatorname{poly}(B)\) bit operations, where \(B\) is the binary input length. We also give an independent prime-power layer formula for the kernel counts, a reduction to gcd kernels, and a factorization over the connected components of the non-coprimality graph. The construction is compatible with known arithmetic-coloring and abelian-arrangement machinery; the contribution is its exact-stratum composition with the Erdős–Graham density objective.