Antonio Mennillo

math.NT — Number Theory

Arcs of Π(1+z^p): prime races, the Gaussian core, Dirichlet L-functions and a certified solver for Subset Sum

Contributed by Antonio Mennillo

The subsets of $\{1\} \cup \{p \le N\}$ reach every integer between 0 and their total, by Bertrand's postulate, so deciding whether a target is a subset sum of the primes is trivial. Counting the solutions is not: the count carries the arithmetic of the primes. We study the generating function $F_N(z) = \Pi(1 + z^w)$ on the unit circle and follow one object, the arc at a rational $a/q$, through three settings. For the primes, the centre of the arc $a/q$ rises above the sea of the minor arcs exactly when $q = 2^k (k \ge 2)$ or $q = 2p^j$, with excess $\Lambda(q/2)/\varphi(q)$, and the neighbourhoods of all the other arcs are bounded uniformly in $q$; Theorem E gives the expansion arc by arc. The height of an arc is a race of the primes modulo $q$ with weights $\log |\cos (\pi ra/q)|$. By Landau's theorem a one-sided bound on it is equivalent to GRH for the even characters it sees, unconditionally at $q = 8$, 10 and 14, where the zero-free segments it needs are certified; at $q = 14$ the race changes sign infinitely often. The principal arc carries $\zeta$ in the centre and width of its Gaussian. For arbitrary weights, the arcs become the decision rule of a Subset Sum solver that reads them on the original weights and ends with a meet-in-the-middle filtered by a random residue class. Every answer it returns is verified. The dummy weights of HURS explain why the reading is exact: they blur the counts by a flat window, and the blur is invertible on counts, though not on reachable sets. On random weights of $b$ bits the method has rigorous guarantees, in time $2^{b/2+o(b)}$ and, with the filter, $2^{b/3+o(b)}$, resting on a local limit theorem uniform in the size of the weights and on a concentration bound for signed subset sums. Finally, the solver is read inside a general theory of constraint propagation, in which every network factors as $T = T_{\mathrm{comp}} \circ T_{\mathrm{struct}}$.