Pith. sign in

REVIEW 4 minor 5 references

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

T0 review · 0 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read An arithmetic progression whose largest term is not too large must have length at least sqrt(8/27) n^(3/4)/sqrt(log n), up to lower-order terms, to contain a multiple of every integer up to n.

desk verdict A clean, unconditional refutation of the informal AP version of the Umans–Wang divisor conjecture; the proof is short, checkable, and the scope limits are stated honestly. read the letter →

arxiv 2608.06681 v1 pith:76VQ3AWN submitted 2026-08-07 math.NT math.CO

Xinjie He , Amit Sahai This is my paper · ORCID
classification math.NTmath.CO MSC 11B2511N05
keywords n-divisorsetarithmeticprogressiondivisorcoverprimenumbertheoremfinitelinearspacelowerboundStrongConjecturesemiprimedivisibility
topics The Twin Prime Conjecture
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves an unconditional lower bound on the length of any arithmetic progression whose entries include a multiple of every integer from 1 through $n$. Under the condition that the progression's largest term $H$ satisfies $\log H = o(\sqrt n)$, the length $L$ must be at least $(\sqrt{8/27} - o(1)) n^{3/4}/\sqrt{\log n}$. This rules out the proposed 'arithmetic-progression version' of the Strong Divisor Conjecture at the $(\alpha,\beta)=(1/3,1/3)$ exponent point, even when the length and height bounds are relaxed by $n^{o(1)}$. The proof is elementary apart from the prime number theorem, and it applies only to one-dimensional progressions, not to the higher-rank conjecture.

What carries the argument

The argument converts semiprime divisibility into a finite incidence structure. Take the primes $p$ in a fixed band $a\sqrt n \le p \le b\sqrt n$ that do not divide the progression's step $c$; each progression term $u+ic$ yields a block consisting of the primes in the band that divide it. The $n$-divisor property ensures every pair of distinct band primes lies in some block (their product $pq \le b^2 n \le n$), while the small height makes every block proper and the small length limits each prime to about $L/(a\sqrt n)$ blocks. A bounded-degree linear-space lemma (Lemma 2.1) then forces the number $v$ of such primes to satisfy $v \le \Delta(\Delta-1)+1$, and the prime number theorem supplies $v$ and the log-product of the band primes. Optimizing $a=2/3$, $b=1$ gives the constant $\sqrt{8/27}$.

What would settle it

Find an unbounded sequence of $n$ and $n$-divisor arithmetic progressions with $\log H = o(\sqrt n)$ and length $L \le (\sqrt{8/27} - \varepsilon) n^{3/4}/\sqrt{\log n}$ for some fixed $\varepsilon>0$; any such example would disprove the theorem. A finite search for small $n$ comparing minimal progression length against the claimed bound would give an immediate sanity test, though only an infinite sequence would be decisive.

Watch

Extended reading notes

Core claim

The central claim is that short arithmetic progressions cannot cover $1,\dots,n$ when the logarithm of their largest term is much smaller than $\sqrt n$. Formally, any $n$-divisor progression with $\log H = o(\sqrt n)$ has $L \ge (\sqrt{8/27} - o(1)) n^{3/4}/\sqrt{\log n}$. A direct corollary excludes every exponent pair $\alpha<1/2$, $\beta<3/8$, including the originally proposed $(1/3,1/3)$, even under $n^{o(1)}$ slack. The obstruction is sharp at the level of the argument: the constant $\sqrt{8/27}$ arises from optimizing the band $a=2/3$, $b=1$ below $\sqrt n$ and is not claimed to be optimal.

Load-bearing premise

The proof's quantitative conclusion rests on the prime number theorem for the count and log-product of primes in a fixed band just below $\sqrt n$; with only weaker prime-count estimates, the constant and possibly the whole proper-block argument would not go through.

Editorial extensions

If this is right

  • The arithmetic-progression version of the Strong Divisor Conjecture is false at $(\alpha,\beta)=(1/3,1/3)$, so the proposed sufficient statement does not hold.
  • The failure persists: both the length bound and the height bound can be relaxed by a factor $n^{o(1)}$ at the exponent level before the contradiction disappears.
  • Any $n$-divisor progression with $\log H = o(\sqrt n)$ must have length at least $(\sqrt{8/27} - o(1)) n^{3/4}/\sqrt{\log n}$, a quantitative obstruction independent of the conjecture.
  • The theorem says nothing when $\beta=3/8$ or when $\log H = \Theta(\sqrt n)$; these boundary cases remain open.
  • The higher-rank Strong Divisor Conjecture is untouched by this result.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same bounded-degree incidence argument may transfer to other structured covering sets, but the one-dimensional step identity $(u+ic)-(u+jc)=(i-j)c$ carries the proof; for rank-two progressions the difference becomes vector-valued and the pairwise-intersection argument does not follow.
  • A natural next test is to attempt constructions of $n$-divisor progressions near the new lower bound; if such constructions exist, the constant $\sqrt{8/27}$ would be optimal up to the $o(1)$ term.
  • The role of the prime number theorem is only to count primes in a fixed band below $\sqrt n$; replacing it with explicit Chebyshev-type bounds would turn the asymptotic lower bound into an explicit finite-$n$ inequality, at the cost of worse constants.
  • The qualitative phenomenon here is that semiprime divisibility alone forces a super-polynomial separation between length and height; this suggests similar trade-offs may hold for other divisor-cover structures, but that is an extrapolation beyond the paper.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper proves an unconditional lower bound on the length L of any arithmetic progression of positive integers that is n-divisor (every integer 1 through n divides at least one term) and has height H with log H = o(sqrt n). The bound is L >= (sqrt(8/27) - o(1)) n^{3/4} / sqrt(log n). As a consequence, the arithmetic-progression version of the Strong (alpha, beta)-Divisor Conjecture of Umans and Wang is false whenever alpha < 1/2 and beta < 3/8, including the proposed (1/3, 1/3) point even under n^{o(1)} exponent-level relaxations. The proof combines a bounded-degree linear-space lemma (Lemma 2.1) with a construction of blocks from primes in a fixed band below sqrt n (Lemma 3.1). The only external analytic input is the prime number theorem.

Significance. If correct, the result is a clean and decisive refutation of the one-dimensional arithmetic-progression variant of the Umans-Wang conjecture over a substantial parameter range. The proof is fully written and self-contained; the combinatorial core is elementary and transparent. The paper is careful to state that the higher-rank Strong Divisor Conjecture is not affected. The PNT is the only external input, and the argument does not rely on numerical computation, fitted parameters, or any circular assumption. This should be of interest to number theorists and theoretical computer scientists working on divisor covers and factorization algorithms.

minor comments (4)
  1. [Section 1 (Discovery using Codex)] The disclosure that the proof was discovered in an OpenAI Codex run is unusual for a mathematics paper; the authors should verify that this presentation conforms to the journal's policies on AI-assisted work and should consider moving it to the acknowledgments.
  2. [Section 3, proof of Lemma 3.1] The phrase "If the progression has only one distinct term" covers both the case L=1 and the case c=0; the subsequent reduction to L>=2 and c>=1 is correct, but the two cases could be stated explicitly for readability.
  3. [Section 4, Corollary 1.2] The phrase "relaxed by n^{o(1)} at the exponent level" is clear from context, but it could be made explicit by writing L_n <= n^{2 beta + o(1)} and H_n <= exp(n^{alpha + o(1)}) directly after the corollary statement.
  4. [Introduction] The reference to "Proposition 3.4 and Section 6" of the Umans-Wang paper would be more helpful with a precise statement or a page/equation number, since these items are used to frame the conjecture being refuted.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof is self-contained and unconditional, using only the prime number theorem and an elementary incidence lemma.

full rationale

The paper's central claim (Theorem 1.1) is derived from Lemma 3.1, which is proved using only the prime number theorem and the elementary bounded-degree linear-space lemma (Lemma 2.1). No parameter is fitted to the conjecture, no normalization is chosen to force the lower bound, and the conjecture's falsity is not assumed. The singleton case is eliminated by the standard estimate log lcm(1,...,n) ~ n, and the block-intersection and properness arguments use only the hypotheses plus PNT estimates on prime counts and log-products in a fixed band. The only self-citations are provenance and acknowledgment items ([3], [5]) that are not used as mathematical evidence; the external analytic input is the standard prime number theorem [2]. Therefore there is no circular step: the derivation chain is unconditional and self-contained apart from established analytic number theory.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

No free parameters are fitted; the band endpoints a=2/3 and b=1 are chosen by optimization, not by data. The only external analytic input is the prime number theorem, and no new entities are introduced.

assumptions (2)
  • standard math Prime number theorem: pi(x) ~ x/log x and psi(x) ~ x.
    Used for the band prime count and log-product estimates in Lemma 3.1 (equations (4) and (5)) and for log lcm(1,...,n) ~ n in the singleton case.
  • domain assumption The n-divisor property is defined over positive integers, so zero is not an admissible witness.
    Remark 4.1 notes that allowing zero would make the condition vacuous; the proof relies on positivity so that log(u+ic) is bounded by log H.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Refuting a Conjecture of Umans and Wang on Arithmetic-Progression Divisor Covers." pith.science (2026). https://pith.science/paper/76VQ3AWN

@misc{pith2026260806681,
  author       = {Pith},
  title        = {Pith review of: Refuting a Conjecture of Umans and Wang on Arithmetic-Progression Divisor Covers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/76VQ3AWN}},
  note         = {Machine review of arXiv:2608.06681}
}
abstract

An \emph{$n$-divisor set} is a finite set of positive integers containing a multiple of every integer from $1$ through $n$. Umans and Wang proposed, as the arithmetic-progression version of their Strong $(\alpha,\beta)$-Divisor Conjecture, an $n$-divisor arithmetic progression having at most $n^{2\beta}$ terms, each of magnitude at most $\exp(n^\alpha)$. We prove unconditionally that an $n$-divisor arithmetic progression of height $H$ with $\log H=o(\sqrt n)$ must have length \[ L\ge \left(\sqrt{\frac{8}{27}}-o(1)\right) \frac{n^{3/4}}{\sqrt{\log n}}. \] Consequently, the arithmetic-progression version is false whenever $\alpha<1/2$ and $\beta<3/8$. In particular, it is false at the proposed point $(\alpha,\beta)=(1/3,1/3)$, even if both bounds are relaxed by $n^{o(1)}$ at the exponent level. The proof uses primes in a fixed band below $\sqrt n$ to turn semiprime divisibility into a finite incidence structure. An elementary bounded-degree linear-space estimate then gives the result. This theorem concerns the one-dimensional arithmetic-progression version only; it does not disprove the higher-rank Strong Divisor Conjecture.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

5 extracted references · 4 canonical work pages

  1. [4]

    Umans and S

    C. Umans and S. Wang, A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization, arXiv:2511.10851v1 (2025)

    work page arXiv 2025

  2. [1]

    N. G. de Bruijn and P. Erd˝ os, On a combinatorial problem,Proceedings of the Section of Sciences of the Koninklijke Nederlandse Akademie van Wetenschappen te Amsterdam51(1948), no. 10, 1277–1279; also published inIndagationes Mathematicae10(1948), 421–423

    work page 1948

  3. [2]

    H. L. Montgomery and R. C. Vaughan,Multiplicative Number Theory I: Classical Theory, Cambridge Studies in Advanced Mathematics, vol. 97, Cambridge University Press, Cambridge, 2007

    2007

  4. [3]

    OpenAI, GPT-5.6: Frontier intelligence that scales with your ambition, July 9, 2026, https: //openai.com/index/gpt-5-6/(accessed August 1, 2026)

    work page 2026

  5. [5]

    Zhang, X

    J. Zhang, X. He, H. Chae, E. Jiang, E. Ji, A. Taylor, Y. Kou, R. Raghavan, V. Sahai, K. Hess, Y. Lu, I. Hair, K.-W. Chang †, R. Meka †, V. Peng †, A. Sahai †, T. Tao †, and W. Wang †,UCLA Moonshot Harness, 2026. †Principal investigators, listed at the end in alphabetical order by last name. 6

    work page 2026

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.