Length bounds for arithmetic-progression divisor systems

How short can a positive arithmetic progression of height H be if every integer up to n divides at least one of its members? The low-height regime log H=o(√n) is the setting of the recorded lower bound; this arithmetic-progression variant is distinct from the higher-rank Strong Divisor Conjecture.

Why it matters and what counts as progress

Why it matters: The low-height progression variant was proposed as a sufficient route to stronger divisor-system conjectures and faster factoring algorithms.

What counts as progress: Improve length-versus-height lower bounds or construct shorter n-divisor progressions within the same height regime.

How the problem developed

2025 · Conjecture [1]
Chris Umans and Shihui Wang Proposed the arithmetic-progression version of the Strong (α,β)-Divisor Conjecture as a sufficient condition for the higher-rank conjecture.
7 Aug 2026 · Refutation of ap version [2]
Xinjie He and Amit Sahai Proved a lower bound of (√(8/27)−o(1))n^(3/4)/√log n for short-height n-divisor arithmetic progressions, refuting the proposed point (α,β)=(1/3,1/3).

AI contribution

Refuting a Conjecture of Umans and Wang on Arithmetic-Progression Divisor Covers

Xinjie He, Amit Sahai

Any positive n-divisor arithmetic progression of height H with log H=o(√n) has length at least (√(8/27)−o(1))n^(3/4)/√log n. This excludes the proposed arithmetic-progression bounds at (α,β)=(1/3,1/3), and whenever α<1/2 and β<3/8.

AI involvementAI-led

ImportanceNotable

Technical verificationFormal (human)

Human understandingFull