alphaFeedback

WorksMathematics

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

AI contributions
Not recorded for this paper
View details
Ancillary data
2 code links
View

Abstract

The subsets of {1}∪{p≤N}\{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 FN(z)=Π(1+zw)F_N(z) = \Pi(1 + z^w) on the unit circle and follow one object, the arc at a rational a/qa/q, through three settings. For the primes, the centre of the arc a/qa/q rises above the sea of the minor arcs exactly when q=2k(k≥2)q = 2^k (k \ge 2) or q=2pjq = 2p^j, with excess Λ(q/2)/φ(q)\Lambda(q/2)/\varphi(q), and the neighbourhoods of all the other arcs are bounded uniformly in qq; Theorem E gives the expansion arc by arc. The height of an arc is a race of the primes modulo qq with weights log⁡∣cos⁡(πra/q)∣\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=8q = 8, 10 and 14, where the zero-free segments it needs are certified; at q=14q = 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 bb bits the method has rigorous guarantees, in time 2b/2+o(b)2^{b/2+o(b)} and, with the filter, 2b/3+o(b)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=Tcomp∘TstructT = T_{\mathrm{comp}} \circ T_{\mathrm{struct}}.

Arc plot showing labelled rational arcs

Figure 10.

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=Tcomp∘TstructT = T_{\mathrm{comp}} \circ T_{\mathrm{struct}}.

Introduction

Two questions can be asked about the subset sums of a set of positive integers: whether a target is reached, and how many times. For the primes the answers live at very different depths.

The floor. Let WN={1}∪{p≤N}W_N = \{1\} \cup\{p \le N\}. Ordered increasingly, each weight is at most one more than the sum of the previous ones, because pk+1<2pkp_{k+1} < 2p_k (Bertrand’s postulate). A set with this property is complete: its subset sums are all the integers from 0 to its total (§ 3). For the primes the decision problem is therefore trivial, and it rests on the prime number theorem at its weakest.

The ceiling. The number rN(T)r_N(T) of subsets with sum TT is the coefficient of zTz^T in FN(z)=∏w∈WN(1+zw)F_N(z) = \prod_{w \in W_N}(1+z^w). Near z=1z = 1 the product gives a Gaussian; this is the local limit theorem, and in the bulk it already determines rN(T)r_N(T) to great accuracy (§ 4.8). Away from z=1z = 1 the product is small, but its size along the arcs at the rationals a/qa/q is not random. Each factor has modulus 2∣cos⁡(πwa/q)∣2|\cos(\pi wa/q)|, so log⁡∣FN(e(a/q))∣\log|F_N(e(a/q))| is a sum over the primes of a function of pp mod qq: a prime race. The question of this paper is what the arcs know about the primes, and what they can do when the weights are not primes.

The thread. The paper follows one object, the arc, through three settings.

  • In §2–3 the weights are the primes. We determine which arcs rise above the sea of the minor arcs (Lemma 1), bound the neighbourhoods of all arcs uniformly in qq (Lemmas P and Q), and state the arc expansion arc by arc (Theorem E).

  • In §4 we read the height of an arc as a prime race. Under two conditions on the characters it sees, (R)(R) and (N)(N), a one-sided bound on it is equivalent to GRH for them (Proposition 3); both conditions are verified for q=8,10,14q = 8, 10, 14. The principal arc carries ζ\zeta (Proposition 30). They are reformulations of the Knapowski–Turán type, in which the hypothesis becomes a statement about counting subsets.

  • In §5–6 the weights are arbitrary. The floor fails, the dummies of HURS restore it, and the arcs, once the dummies are removed exactly, which makes them unnecessary in the solver, become the decision rule of a Subset Sum solver. We give its cost law, its benchmarks, and the rigorous form of its guarantees on random and on dense instances.

  • The arc, seen from far enough, is propagation on a quotient. In §7 we develop the general theory of constraint propagation behind the algorithm: a structural part (equalities with parity, functional definitions on a complete DAG) solved in one pass, a computational part iterated to a fixpoint, the convergence of the full operator, and definitional variables that make implicit links evaluable. In §8 we read the solver of §5 inside it.

Why it matters. Prime races and Subset Sum have so far been separate subjects. The first belongs to analytic number theory (Chebyshev’s bias, Knapowski–Turán, Rubinstein–Sarnak); the second is a classical NP-complete problem whose algorithms are combinatorial. The arcs join them. Counting subsets of the primes is a circle-method problem in which every arc is a prime race, so a hypothesis about the zeros of Dirichlet LL-functions becomes a statement about how many subsets of primes have a given sum, and the selection rule q=2kq = 2^k, 2pj2p^j with excess Λ(q/2)/ϕ(q)\Lambda(q/2)/\phi(q) is read off a cyclotomic value. In the other direction, the same arcs, read on arbitrary weights, are a working decision rule: they find the congruence obstructions that the structure theorem of dense Subset Sum predicts, and they steer a solver on instances where a dynamic-programming table is out of reach. The bridge is a dictionary, and both sides of it are proved.

§9 places the results in the literature and states their scope.

Notation. e(x)=e2πixe(x) = e^{2\pi i x}; Λ\Lambda is von Mangoldt’s function; ϕ\phi is Euler’s function; Φq\Phi_q is the qq-th cyclotomic polynomial; π(N,χ)=∑p≤Nχ(p)\pi(N,\chi) = \sum_{p\le N}\chi(p); li⁡x=∫2xdtlog⁡t+li⁡2\operatorname{li}x = \int_2^x \frac{dt}{\log t}+\operatorname{li}2. Constants CC are absolute unless indexed.

Map of the results.

ResultWhat it saysWhereInputs
Lemma 2.1, Proposition 2.3the primes with 1 are complete; without 1 they miss six values§2—
Lemma 1the arcs that emerge, q=2kq = 2^k, 2pj2p^j, with excess Λ(q/2)/ϕ(q)\Lambda(q/2)/\phi(q)§3.2—
Lemmas P, Q, Corollary Q′the lobes, bounded uniformly in qq; the highest is at q=3q = 3§3.3Arb certificate (Q′)
Propositions C, C′the Edgeworth expansion of the core of an arc§3.4—
Lemmas M, L₀, L, W; Theorem Ethe arc expansion: minor, non-emerging and emerging arcs§3.5Siegel–Walfisz, Vinogradov–Vaughan, Jackson
Proposition 3a one-sided bound on an arc is equivalent to GRH for its characters§4.2(R) by Arb, (N)
Theorem Sno last sign change of the race at q=14q = 14§4.3(R) by Arb, a zero on the line
Proposition 30the principal arc carries ζ\zeta§4.4von Koch (one direction)
Lemmas 5.1, 5.3, blur identitythe solver and the exact de-blurring§5—
Lemmas A, B0′, B, B‴; Propositions B′, B‴′the centre rule; a local limit theorem uniform in MM; the endgame is non-empty§6.1–6.3[BR, Thm 22.1] (B′); B‴′ computed
Theorems R, R′success with probability ≥1−δ\ge1-\delta in time 2b/2+o(b)2^{b/2+o(b)}§6.4—
Lemma C, Corollaries C′, C″an exact decider on dense instances§6.5Bringmann–Wellnitz
Theorem LVthe endgame count has an exponential tail: Las Vegas§6.6certified ρ≤0.44495\rho\le0.44495
Lemmas J, K, V, Proposition K′, Theorem R″the filtered endgame, time 2b/3+o(b)2^{b/3+o(b)}§6.7Rosser–Schoenfeld
Theorems 7.2–7.13T=Tcomp∘TstructT = T_{\mathrm{comp}}\circ T_{\mathrm{struct}}, the information limit, convergence§7—
Propositions 8.1–8.5the solver as propagation; the blur is invertible on counts§8—

Table 12.

The floor: completeness and linear search

Define the omicron of a set of positive integers w1≤w2≤⋯≤wnw_1 \le w_2 \le\cdots\le w_n as o=max⁡kwk+1/(1+∑i≤kwi)o = \max_k w_{k+1}/(1+\sum_{i\le k} w_i).

Lemma 2.1 (gap filling; Brown). Let w1≤w2≤⋯≤wnw_1 \le w_2 \le\cdots\le w_n be positive integers and Sk=∑i≤kwiS_k = \sum_{i\le k}w_i, S0=0S_0 = 0. Every integer 0≤T≤Sn0 \le T \le S_n is a subset sum if and only if wk+1≤1+Skw_{k+1} \le1+S_k for every 0≤k<n0 \le k < n, that is, if and only if o≤1o \le1 [Brown]. Since o≥w1≥1o \ge w_1 \ge1, the condition reads o=1o = 1. For WNW_N it holds by Bertrand’s postulate.

Proof. If the condition holds, the subset sums of the first kk weights fill [0,Sk][0,S_k] by induction, and adding wk+1≤Sk+1w_{k+1} \le S_k+1 fills [0,Sk+1][0,S_{k+1}]. Conversely, if wk+1>1+Skw_{k+1} > 1+S_k for some kk, the integer Sk+1≤SnS_k+1 \le S_n is not a subset sum: the subsets of the first kk weights sum to at most SkS_k, and every other subset contains a weight wj≥wk+1>Sk+1w_j \ge w_{k+1} > S_k+1. □

Linear search. Scan the weights downwards and take wkw_k whenever wk≤Tremw_k \le T_{\mathrm{rem}}. Before wkw_k is examined, Trem≤∑i≤kwiT_{\mathrm{rem}} \le\sum_{i\le k} w_i. If Trem≥wkT_{\mathrm{rem}} \ge w_k, it is taken and Trem−wk≤∑i<kwiT_{\mathrm{rem}}-w_k \le\sum_{i<k}w_i. Otherwise Trem≤wk−1≤∑i<kwiT_{\mathrm{rem}} \le w_k-1 \le\sum_{i<k}w_i by completeness. The scan ends at Trem=0T_{\mathrm{rem}}=0. Decision is always “yes”, and search costs O(n)O(n) after the sieve. Two more facts complete the floor: rN(T)≥1r_N(T) \ge1 for 0≤T≤SN0 \le T \le S_N, and rN(T)=rN(SN−T)r_N(T) = r_N(S_N-T) by complementation.

References

  1. [1]Apt K. R. Apt, The essence of constraint propagation, Theoretical Computer Science 221 (1999) 179–210.
  2. [2]BCJ A. Becker, J.-S. Coron, A. Joux, Improved generic algorithms for hard knapsacks, EUROCRYPT 2011.
  3. [3]BCP C. Borgs, J. Chayes, B. Pittel, Phase transition and finite-size scaling for the integer partitioning problem, Random Structures & Algorithms 19 (2001), 247–288.DOI
  4. [4]Beth E. W. Beth, On Padoa’s method in the theory of definition, Indagationes Mathematicae 15 (1953) 330–339.DOI
  5. [5]BHM B. Bzdega, A. Herrera-Poyatos, P. Moree, Cyclotomic polynomials at roots of unity, arXiv:1611.06783.arxiv.org/abs/1611.06783
  6. [6]BR R. N. Bhattacharya, R. Ranga Rao, Normal Approximation and Asymptotic Expansions, Wiley (1976); reprinted SIAM Classics in Applied Mathematics 64 (2010).
  7. [7]Brown J. L. Brown Jr., Note on complete sequences of integers, Amer. Math. Monthly 68 (1961) 557–560.DOI
  8. [8]BW K. Bringmann, P. Wellnitz, On near-linear-time algorithms for dense Subset Sum, SODA 2021, arXiv:2010.09096.arxiv.org/abs/2010.09096
  9. [9]CJLOSS M. J. Coster, A. Joux, B. A. LaMacchia, A. M. Odlyzko, C.-P. Schnorr, J. Stern, Improved low-density subset sum algorithms, Computational Complexity 2 (1992).DOI
  10. [10]CPS A. Mennillo, Cumulative prime sums and Riemann zeros, Zenodo (2026).DOI
  11. [11]CLRS T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press (2009).
  12. [12]Craig W. Craig, Three uses of the Herbrand–Gentzen theorem in relating model theory and proof theory, J. Symbolic Logic 22 (1957) 269–285.DOI
  13. [13]Davenport H. Davenport, Multiplicative Number Theory, 3rd ed., Springer.
  14. [14]FP A. Flaxman, B. Przydatek, Solving medium-density subset sum problems in expected polynomial time, STACS 2005, LNCS 3404, 305–314.DOI
  15. [15]Freuder E. C. Freuder, A sufficient condition for backtrack-free search, J. ACM 29 (1982) 24–32.DOI
  16. [16]GHK S. M. Gonek, C. P. Hughes, J. P. Keating, A hybrid Euler–Hadamard product for the Riemann zeta function, Duke Math. J. 136 (2007) 507–549.
  17. [17]GM Z. Galil, O. Margalit, An almost linear-time algorithm for the dense subset-sum problem, SIAM J. Comput. 20 (1991).
  18. [18]HGJ N. Howgrave-Graham, A. Joux, New generic algorithms for hard knapsacks, EUROCRYPT 2010.
  19. [19]Halim S. Halim, F. Halim, Competitive Programming 3, Lulu (2013).
  20. [20]IK H. Iwaniec, E. Kowalski, Analytic Number Theory, AMS Colloquium Publications 53.
  21. [21]Ingham A. E. Ingham, The Distribution of Prime Numbers, Cambridge.
  22. [22]Koch H. von Koch, Sur la distribution des nombres premiers, Acta Math. 24 (1901) 159–182.DOI
  23. [23]KT S. Knapowski, P. Turán, Comparative prime-number theory I–VIII, Acta Math. Acad. Sci. Hungar. 13–14 (1962–63).DOI
  24. [24]Landau E. Landau, Über einen Satz von Tschebyschef, Math. Ann. 61 (1905).DOI
  25. [25]Littlewood J. E. Littlewood, Sur la distribution des nombres premiers, C. R. Acad. Sci. Paris 158 (1914).
  26. [26]LLM J.-M. Lagniez, E. Lonca, P. Marquis, Improving model counting by leveraging definability, IJCAI 2016.
  27. [27]LMS I. Lynce, J. Marques-Silva, Probing-based preprocessing techniques for propositional satisfiability, ICTAI 2003.DOI
  28. [28]LN D. Lokhshtanov, J. Nederlof, Saving space by algebraization, STOC 2010.
  29. [29]LO J. C. Lagarias, A. M. Odlyzko, Solving low-density subset sum problems, J. ACM 32 (1985).
  30. [30]LV H. Lin, P. N. Vasudevan, On Wagner’s k-tree algorithm over integers, arXiv:2410.06856 (2024).arxiv.org/abs/2410.06856
  31. [31]LUF D. Lesbre et al., Labeled union-find for constraint factorization, NSAD 2024 (work in progress).
  32. [32]Lyu V. Lyubashevsky, On random high density subset sums, ECCC TR05-007 (2005).
  33. [33]Mackworth A. K. Mackworth, Consistency in networks of relations, Artificial Intelligence 8 (1977) 99–118.
  34. [34]MS G. Martin, J. Scarfy, Comparative prime number theory: a survey, arXiv:1202.3408.
  35. [35]Nkosi T. Nkosi, Algorithmic structure in Subset Sum: deterministic in-bound navigation and the counting complexity divide, arXiv:2506.12019 (2025).arxiv.org/abs/2506.12019
  36. [36]Richert H.-E. Richert, Über Zerfällungen in ungleiche Primzahlen, Math. Z. 52 (1949).DOI
  37. [37]RoS J. B. Rosser, L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962) 64–94.
  38. [38]Rosser J. B. Rosser, Real roots of real Dirichlet L-series, J. Res. Nat. Bur. Standards 45 (1950), 505–513.DOI
  39. [39]RS M. Rubinstein, P. Sarnak, Chebyshev’s bias, Experimental Mathematics 3 (1994).
  40. [40]RSz K. F. Roth, G. Szekeres, Some asymptotic formulae in the theory of partitions, Quart. J. Math. 5 (1954).DOI
  41. [41]Rumely R. Rumely, Numerical computations concerning the ERH, Math. Comp. 61 (1993), 415–440.DOI
  42. [42]Schaefer T. J. Schaefer, The complexity of satisfiability problems, STOC 1978, 216–226.DOI
  43. [43]Sha A. Shallue, An improved multi-set algorithm for the dense subset sum problem, ANTS VIII, LNCS 5011 (2008).DOI
  44. [44]Shamir A. Shamir, A polynomial-time algorithm for breaking the basic Merkle–Hellman cryptosystem, IEEE Trans. Inf. Theory 30 (1984).
  45. [45]SS R. Schroeppel, A. Shamir, A T = O(2ⁿ/²), S = O(2ⁿ/⁴) algorithm for certain NP-complete problems, SIAM J. Comput. 10 (1981) 456–464.
  46. [46]SNC M. Soos, K. Nohl, C. Castelluccia, Extending SAT solvers to cryptographic problems, SAT 2009.DOI
  47. [47]Tarjan R. E. Tarjan, Efficiency of a good but not linear set union algorithm, J. ACM 22 (1975) 215–225.
  48. [48]Vinogradov I. M. Vinogradov, The Method of Trigonometrical Sums in the Theory of Numbers.
  49. [49]Wag D. Wagner, A generalized birthday problem, CRYPTO 2002, LNCS 2442, 288–304.DOI
  50. [50]WGS R. Williams, C. P. Gomes, B. Selman, Backdoors to typical case complexity, IJCAI 2003, 1173–1178.
  51. [51]WS D. Wan, W. Shi, Solving medium-density subset sum problems in expected polynomial time: an enumeration approach, arXiv:0712.3203.

Paper details

vlnc:W_e5jgtexr
v1 · latestHistory (1)

published · Fresh — added to the Hub within the last 30 days

added ·

Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

CC BY 4.0

Original source

  • Mathematics

Not recorded for this paper · View statement →

Looking for related papers…
Contents