Random subset-sum covering thresholds in finite cyclic groups

Choose random residues in a cyclic group of order N and form all subset sums. How many choices are needed to cover the group, beyond the leading log₂N term?

Why it matters and what counts as progress

Why it matters: The smaller correction term measures the cost of complete coverage rather than merely having enough possible sums.

What counts as progress: A sharper threshold bound, or a lower bound disproving log₂N+o(log log N), with prime-modulus cases distinguished from assertions for all N.

How the problem developed

1965 · Bound [1]
Paul Erdős and Alfréd Rényi Proved a universal upper bound f(N) ≤ log₂N + (1/log 2 + o(1))log log N for the random subset-sum covering threshold.
1973 · Conjecture [1]
Paul Erdős Conjectured that the log-log term in the upper bound cannot be improved to o(log log N).
5 Feb 2026 · Reported claim [1]
Jie Ma and Quanyu Tang; ChatGPT-5.2 Pro The paper confirms the conjecture by proving a lower bound for prime orders p, with leading correction (1/(2 log 2) + o(1))log log p; the prime-order case suffices to rule out the proposed universal improvement.

AI contribution

An Erdős problem on random subset sums in finite abelian groups

Jie Ma, Quanyu Tang

A repaired GPT-5.2 Pro argument uses prime cyclic groups to refute f(N)≤log₂N+o(log log N) for the random subset-sum covering threshold. Ma and Tang later prove the stronger lower bound f(p)≥log₂p+(1/(2 log 2)+o(1))log log p; the constant and quantitative refinement are their work.

AI involvementAI-autonomous

ImportanceNotable

Technical verificationFormal (human)

Human understandingFull