O6 — Factoring a positive-density set of integers

Definitions and mathematical statement

For $S\subseteq\mathbb N=\{1,2,\ldots\}$, define its lower asymptotic density by \[ \underline d(S)=\liminf_{X\to\infty}\frac{|S\cap\{1,\ldots,\lfloor X\rfloor\}|}{\lfloor X\rfloor}. \] Thus positive lower density requires a positive proportion of all sufficiently long initial intervals, not merely infinitely many easily factored integers.

Does there exist a set $S$ with $\underline d(S)>0$, together with a deterministic algorithm and a fixed polynomial $P$, such that the complete prime factorization of every $N\in S$ is produced within $P(\ell(N))$ bit operations? Here $\ell(N)$ is binary length, and complete factorization means all distinct prime factors with their multiplicities. The factorization of $1$ is the empty list.

Equivalently, one may seek a polynomial-time algorithm on all positive inputs that outputs either a verified complete factorization or a failure symbol, and whose set of successful inputs has positive lower density. To pass from the promised-set formulation to this version, run the algorithm for its polynomial time bound and check any proposed factorization; the converse uses its success set as $S$.

No efficient membership test for $S$ is required separately. The polynomial and the algorithm must be fixed uniformly, while the set $S$ may be chosen as part of a positive answer. A result restricted to a set of density zero does not establish the requested conclusion.

Short English statement

Can a deterministic polynomial-time algorithm completely factor a set of integers having positive lower density?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 8400006 (AMR-083-0006), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Adleman & McCurley - Open Problems in Number Theory Complexity II (1994), O6, p8 / LNCS p298. Original source indexed by AMR-083-0006. https://mccurley.org/papers/open.ps.gz.