The Strong (α,β)-Divisor Conjecture of Umans and Wang: structured sets S, T whose difference set contains a multiple of every integer in [n], with α, β < 1/2

Umans and Wang (2025) proposed, as the engine of a strategy to break the long-standing exponent-3/2 barrier for factoring degree-$n$ polynomials over finite fields, the Strong (α,β)-Divisor Conjecture: for infinitely many $n$ there exist sets $S$, $T$ of positive integers, each of size at most $n^{β}$ and magnitude at most $\exp(n^{α})$, and each a sum of at most $n^{o(1)}$ arithmetic progressions, such that every integer in $\{1,\dots,n\}$ divides some positive difference $s-t$. Proving the conjecture at any parameters $\alpha,\beta<1/2$ — best possible at $\alpha=\beta=1/3$ — would give a randomized distinct-degree factorization algorithm with exponent below $3/2$ (down to $4/3$), and a prefactored strengthening would improve the best deterministic integer-factorization exponent from $1/5$ to $1/6$. He and Sahai (2026) unconditionally refuted the one-dimensional arithmetic-progression variant at all parameters $\alpha<1/2$, $\beta<3/8$ (including the optimal point $(1/3,1/3)$), but their result explicitly does not touch the higher-rank Strong conjecture. No proof or refutation of the Strong (α,β)-Divisor Conjecture itself is known: the problem of settling it — constructing structured $S$, $T$ at some $\alpha,\beta<1/2$, or proving that none exist — remains open.

Background

Factoring a univariate polynomial of degree $n$ over a finite field $F_q$ (a field with $q$ elements) is one of the workhorses of computer algebra. The standard pipeline first performs distinct-degree factorization (DDF): given a monic squarefree $f$ of degree $n$, output $f = f_1 f_2 \cdots f_n$ where $f_i$ is the product of the irreducible factors of $f$ of degree $i$. The algebraic engine is the identity $X^{q^i} - X = \prod_{d \mid i} \Psi_d(X)$, where $\Psi_d$ is the product of all monic irreducible polynomials of degree $d$ over $F_q$: the gcd of $f$ with $X^{q^i} - X$ isolates precisely the factors whose degrees divide $i$. Each such gcd can be computed with a nearly linear number of field operations using fast modular composition — the operation $f(g(X)) \bmod h(X)$ on degree-$n$ polynomials, which Kedlaya and Umans (2011) showed takes $n^{1+o(1)}$ operations — but there are $n$ of these gcds, and the best-known way to batch them is a baby-steps-giant-steps schedule (precompute $X^{q^a} \bmod f$ for a block of small $a$, then compose in strides) for the products of blocks of the polynomials $X^{q^i} - X$. This yields the current-best running time $O(n^{3/2+o(1)}) \, \mathrm{polylog}\, q$ of Kedlaya and Umans (2011) — here and below $\widetilde{O}$ suppresses polylogarithmic factors — and the exponent $3/2$ is considered a genuine barrier of the baby-steps-giant-steps motif: Guo, Narayanan, and Umans (2016) exhibited a collection of algebraic problems, mutually reducible with polynomial factorization, all of whose best algorithms are stuck at exponent $3/2$ through the same bottleneck.

Umans and Wang (2025) proposed a strategy to go below $3/2$: take gcds with $X^{q^A} - X$ for single large exponents $A$ (as large as $\exp(n^{1/3})$), computable modulo $f$ by repeated modular composition; one such gcd strips off, in one shot, all factors whose degrees divide $A$. To cover all degrees in $[n] = \{1,\dots,n\}$ one needs a family of such exponents that is simultaneously small in number, small in magnitude, and cheap to enumerate. Say that a set $A$ of positive integers has the $n$-divisor property if every $i \in \{1,\dots,n\}$ divides some element of $A$; when the property is applied to a difference set, the witnessing element must be positive, and $0$ is never an admissible witness (every positive integer divides $0$, so allowing it would make the property vacuous). Umans and Wang ask for the difference set $\{s - t : s \in S, t \in T\}$ to have the $n$-divisor property, where $|S|, |T| \le n^{\beta}$, every element of $S \cup T$ has magnitude at most $\exp(n^{\alpha})$, and $S$ and $T$ are structured as generalized arithmetic progressions — a generalized arithmetic progression (GAP) is a sum $S_1 + \cdots + S_c = \{s_1 + \cdots + s_c : s_i \in S_i\}$ of ordinary arithmetic progressions, and $c$ is its rank — of rank at most $n^{o(1)}$. The structure requirement is what makes the computation feasible: a low-rank GAP admits a short addition sequence (a sequence in which each element is a sum of two earlier elements, generalizing the classical addition chains for exponentiation), along which the polynomials $X^{q^s} \bmod f$ for $s \in S \cup T$ can be produced by composition within the overall time budget.

Two elementary counting constraints shape the feasible parameters. Since every prime $p \le n$ divides some difference, the product of all primes up to $n$, of magnitude $\exp(n)$, must divide the product of the $|S| \cdot |T| \le n^{2\beta}$ differences; hence some difference has magnitude at least $\exp(n^{1-2\beta})$, forcing $\alpha \ge 1 - 2\beta$. Conversely, a trivial construction sits near the corner $\beta = 1$ of the feasible region: for every fixed $\varepsilon > 0$ the two ordinary progressions $S = \{2, 3, \dots, n+1\}$ and $T = \{1\}$ satisfy $|S| = n \le n^{1+\varepsilon}$, $|T| = 1 \le n^{1+\varepsilon}$ with every element at most $n + 1 \le \exp(n^{\varepsilon})$, and their difference set is exactly $\{1, 2, \dots, n\}$ (since $i = (i+1) - 1$), so it plainly has the $n$-divisor property; this meets all three conditions at $\alpha = \varepsilon$, $\beta = 1+\varepsilon$; hence no nontrivial construction with both $\alpha, \beta < 1/2$ is known. The algorithmic payoffs are theorems of Umans and Wang (2025): the Strong (α,β)-Divisor Conjecture at $\alpha, \beta < 1/2$ implies a randomized DDF algorithm running in time $\widetilde{O}(n^{1 + \max(\alpha,\beta) + o(1)}) \, \mathrm{polylog}\, q$, strictly beating $3/2$, with the best-possible point $\alpha = \beta = 1/3$ giving exponent $4/3$ (best possible because $\alpha \ge 1-2\beta$). A prefactored strengthening — additionally requiring that the prime factorization of each difference $s-t$ be outputable in deterministic $\widetilde{O}(n^{\alpha})$ time — implies a deterministic algorithm computing the prime factorization of an integer $N$ in time $\widetilde{O}(N^{\max(\alpha,\beta)/2 + o(1)})$. Here deterministic integer factoring refers to the exponential-time regime measured in $N$ (as opposed to heuristic subexponential randomized methods such as the number field sieve): the classical exponent $1/4$ was improved to $1/5$ by Harvey (2021), and the prefactored conjecture at $\alpha = \beta = 1/3$ would improve it to $1/6$.

Umans and Wang singled out as the most attackable form the Arithmetic Progression Version: a single arithmetic progression of length at most $n^{2\beta}$ and height at most $\exp(n^{\alpha})$ with the $n$-divisor property, which implies the Strong conjecture (by splitting the progression's index range into $n^{\beta}$ giant steps). This variant has now been refuted at the decisive parameters: He and Sahai (2026) proved unconditionally that any $n$-divisor arithmetic progression of height $H$ with $\log H = o(\sqrt n)$ must have length at least $(\sqrt{8/27} - o(1))\, n^{3/4} / \sqrt{\log n}$, so no such progression exists with $\alpha < 1/2$ and $\beta < 3/8$ — in particular not at $(1/3, 1/3)$, even allowing $n^{o(1)}$ slack in both bounds. Their proof converts divisibility of semiprimes $pq \le n$, for primes $p, q$ in a band just below $\sqrt n$, into a finite incidence structure and applies an elementary bounded-degree linear-space counting lemma. Crucially for the present problem, He and Sahai state explicitly that this does not disprove the higher-rank Strong conjecture: their at-most-one-intersection argument exploits the one-dimensional difference structure $(i-j)c$, which has no analogue for GAPs of rank $\ge 2$, and the arithmetic-progression version implies, but is not implied by, the Strong conjecture. The endpoints $\alpha = 1/2$ and $\beta = 3/8$ remain uncovered, so even the arithmetic-progression variant at $\beta \in [3/8, 1/2)$ with $\alpha < 1/2$ — still sufficient for an exponent below $3/2$ — is open.

Problem Statement

The Strong (α,β)-Divisor Conjecture of Umans and Wang (2025) asserts:

For infinitely many $n$ there exist sets $S, T \subseteq \mathbb{Z}^+$ such that the difference set

$$A = \{s - t : s \in S,\ t \in T\}$$

satisfies the $n$-divisor property — every $i \in \{1, \dots, n\}$ divides some positive element of $A$ (zero is excluded as a witness, since every positive integer divides $0$ and would make the property vacuous) — and:

1. every element of $S \cup T$ has magnitude at most $\exp(n^{\alpha})$;
2. $|S|, |T| \le n^{\beta}$;
3. there exist $c, c' \le n^{o(1)}$ such that $S = S_1 + \cdots + S_c$ and $T = T_1 + \cdots + T_{c'}$, where each $S_i$ and $T_j$ is an arithmetic progression.

Question: does this conjecture hold for some parameters $\alpha, \beta < 1/2$ — optimally at $\alpha = \beta = 1/3$, the best-possible point on the necessary feasibility line $\alpha \ge 1 - 2\beta$? Resolve it in either direction:

• constructively, by exhibiting such structured sets $S, T$ (together with a proof that they meet conditions 1-3 and the $n$-divisor property for infinitely many $n$) at some $\alpha, \beta < 1/2$; or
• negatively, by proving that for all $\alpha, \beta < 1/2$ and all sufficiently large $n$ no sets $S, T$ satisfying conditions 1-3 with the $n$-divisor difference property exist.

A determination of the full feasible trade-off region between $\alpha$ and $\beta$ for structured difference sets with the $n$-divisor property is a stronger, optional goal: exhibiting a single admissible pair $(\alpha, \beta)$ with $\alpha, \beta < 1/2$, or proving the negative statement above, already resolves the question. The structure requirement is exactly condition 3 (generalized arithmetic progressions of rank up to $n^{o(1)}$; rank $\ge 2$ is allowed and, after the refutation of the one-dimensional arithmetic-progression variant for $\alpha < 1/2$, $\beta < 3/8$ by He and Sahai (2026), rank $\ge 2$ is where the question genuinely lives); no one-dimensional restriction may be imposed on, or read into, the conjecture. The algorithmic stakes are those of the source: a positive answer at any $\alpha, \beta < 1/2$ yields, via the theorems of Umans and Wang (2025), a randomized distinct-degree factorization algorithm over finite fields with exponent $1 + \max(\alpha,\beta) < 3/2$, and the prefactored strengthening yields deterministic integer factorization with exponent $\max(\alpha,\beta)/2 < 1/4$ (reaching $1/6$ at $(1/3,1/3)$, below the current best $1/5$).

References

1. Chris Umans, Siki Wang. A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization. arXiv:2511.10851 (2025), DOI 10.48550/arXiv.2511.10851, https://arxiv.org/abs/2511.10851
2. Xinjie He, Amit Sahai. Refuting a Conjecture of Umans and Wang on Arithmetic-Progression Divisor Covers. arXiv:2608.06681 (2026), DOI 10.48550/arXiv.2608.06681, https://arxiv.org/abs/2608.06681
3. Kiran S. Kedlaya, Christopher Umans. Fast Polynomial Factorization and Modular Composition. SIAM Journal on Computing 40(6):1767-1802 (2011), DOI 10.1137/08073408x, https://doi.org/10.1137/08073408x
4. David Harvey. An exponent one-fifth algorithm for deterministic integer factorisation. Mathematics of Computation 90(332):2937-2950 (2021), DOI 10.1090/mcom/3658, https://doi.org/10.1090/mcom/3658
5. Zeyu Guo, Anand Kumar Narayanan, Chris Umans. Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields. arXiv:1606.04592 (2016), DOI 10.48550/arXiv.1606.04592, https://arxiv.org/abs/1606.04592