Divisibility patterns and the size of a witness

The quantities and the results

Let dₙ(j) be 1 when j divides n and 0 otherwise. A binary word w = w(0)⋯w(m − 1) occurs at k if dₙ(k + i) = w(i) for every 0 ≤ i < m. Define N(w) as the least positive n with such an occurrence, M(m) as the largest N(w) among all length-m words, and A(m) as their arithmetic mean. All logarithms in this note are natural.

Maximum lower bound. As m tends to infinity, log M(m) ≥ m log m − 2m log log m + (2 log 2 − 1)m + o(m). Thus the worst-case least witness grows faster than any fixed exponential in m.

Family theorem. If H(m) = N(01^(m−1)), where the word consists of one zero and then m − 1 ones, then log H(m) = (2 + o(1))m as m tends to infinity.

Universal bound. The maximum satisfies log M(m) ≤ (1 + o(1))m(log m)² / log log m. The same upper bound holds for log A(m), since A(m) ≤ M(m).

Since the mean is at least M(m)/2ᵐ, the same construction gives log A(m) ≥ m log m − 2m log log m + (log 2 − 1)m + o(m). There remains a gap between these lower bounds and the universal upper bound.

A least-common-multiple lemma

For positive integers k and r, put D = lcm(k + 1, …, k + r). We need two divisibilities: lcm(1, …, r) divides D, and binom(k + r, r) divides D. In particular, D ≥ kʳ/r!. The original question cites Farhi for a related consecutive-integer lcm estimate; here is a direct proof of the precise version used below. Farhi’s paper.

A block of r consecutive integers contains a multiple of every integer from 1 to r. This proves the first divisibility.

For the second, fix a prime p. For each j ≥ 1, the number of multiples of pʲ in the block is either floor(r/pʲ) or floor(r/pʲ) + 1. The p-adic valuation of (k + 1)⋯(k + r)/r! is therefore a sum of zeros and ones. A nonzero summand requires pʲ to divide a member of the block. The number of such possible j is the largest p-adic valuation among the block members, which is the valuation of D. This proves the second divisibility. Finally, the binomial coefficient is at least kʳ/r!.

A superexponential lower bound for the maximum

Choose a prime p ≤ m/2, put r = m−p, and take the word 0ᵖ1ʳ. Suppose an occurrence has its first one at position u. Then u ≥ p+1. If u ≤ p², the preceding p zero-positions contain a multiple qp with 1 ≤ q < p. Because p is prime, q and p are coprime, so qp divides lcm(1,…,p).

The block of r ≥ p consecutive one-positions has a least common multiple D divisible by lcm(1,…,p). Thus qp divides D, and D divides the witness n. This contradicts the zero at qp. Every occurrence therefore has u ≥ p²+1.

The lcm lemma now gives n ≥ D ≥ binom(u+r−1,r) ≥ binom(p²+r,r). This finite certificate holds for every prime p ≤ m/2; no search over occurrence positions is required.

By the prime number theorem, choose p = (2+o(1))m/log m. With r = m−p, the logarithm of the binomial certificate is r log(p²/r) + r + o(m). Stirling’s formula justifies this expansion because p²/r tends to infinity and r²/p² = O((log m)²) = o(m).

Expand log p = log m−log log m+log 2+o(1), and use p log m = 2m+o(m). The certificate becomes m log m−2m log log m+(2 log 2−1)m+o(m), proving the stated lower bound. This exceeds the earlier family bound with rate 2m, so that family cannot determine the eventual maximum.

The family: every witness is large

Suppose the word 01^(m−1) occurs at k in dₙ, with m ≥ 2. Necessarily k ≥ m. Otherwise 2k is among the next m − 1 positions, so 2k divides n and forces k to divide n, contradicting the initial zero. Put r = m − 1. Every one-position divides n, hence D = lcm(k + 1, …, k + r) divides n.

Write θ(x) = Σₚ≤ₓ log p and ψ(x) = log lcm(1, …, floor x). The prime number theorem gives θ(x) = x + o(x) and ψ(x) = x + o(x). First consider m ≤ k ≤ 3m. The lemma puts lcm(1, …, r) inside D. Every prime in (k, k + r] also divides D, and these primes exceed r. Their product is therefore coprime to that lcm. Thus log D ≥ ψ(r) + θ(k + r) − θ(k) = 2m + o(m).

The error is uniform over this entire range of k. Indeed, writing θ(x) = x + xη(x) with η(x) → 0, the two endpoint errors have total absolute value at most 7m supₓ≥ₘ |η(x)| = o(m). The ψ(r) error is o(m) as well.

For k > 3m, the lemma and Stirling’s formula give log D ≥ r log k − log(r!) ≥ (1 + log 3)m − O(log m). Since 1 + log 3 > 2, this also exceeds (2 − o(1))m. Every possible occurrence has now been covered, so log H(m) ≥ (2 − o(1))m.

The family: a matching witness

Choose a prime p ≥ m with p = (1 + o(1))m; its existence follows from the prime number theorem. Take n = lcm(p + 1, …, p + m − 1). Every selected entry divides n, but p does not: all entries lie strictly between p and 2p, so none contains the prime p. The required zero followed by m − 1 ones therefore occurs at p.

Also n divides lcm(1, …, p + m − 1), so log n ≤ ψ(p + m − 1) = (2 + o(1))m. Combined with the lower bound, this proves log H(m) = (2 + o(1))m.

For example, H(4) = 168: at positions 5, 6, 7 and 8, the divisor indicator of 168 is 0, 1, 1, 1. The first six family values are 1, 3, 20, 168, 504 and 3960. These are H(m), not the maximum M(m); in particular, the original question reports M(5) = 660, whereas H(5) = 504.

A block that realizes every word

Call an integer m-smooth when all its prime factors are at most m; include 1 among the smooth integers. Suppose a block k, …, k + m − 1 contains no m-smooth integer. Each entry k + i then has a prime factor pᵢ > m. Such a prime divides no other entry of the block, because a nonzero difference between entries is smaller than m.

For any length-m word w, multiply exactly the entries at its one-positions: n_w = ∏ᵢ:w(i)=1 (k + i). Each one-position divides n_w. At any zero-position i, the prime pᵢ divides none of the selected factors, so k + i does not divide n_w. Thus the same block realizes every word, using a different integer n_w for each word. For the all-zero word the product is empty and equals 1.

If the block lies inside [1, X], then n_w ≤ Xᵐ for every w. It remains to find such a block with log X no larger than (1 + o(1))(log m)²/log log m.

Finding a block with no smooth integer

Let Ψ(X, m) count the m-smooth positive integers up to X. Rankin’s method gives, for any s > 0, Ψ(X, m) ≤ Xˢ ∏ₚ≤ₘ (1 − p^(−s))^(−1). To see this, bound the indicator of a ≤ X by (X/a)ˢ and sum over all m-smooth a. The geometric series over the finitely many allowed primes produce the Euler product. Granville’s exposition, §3.10.

Put L = log m, B = log L, δ = B/L and s = 1 − δ. We claim that the logarithm of this Euler product is o(L). For sufficiently large m, s ≥ 3/4. In the logarithmic expansion, terms of degree at least two have bounded total, uniformly in s; they are bounded by a constant times Σₙ≥₂ n^(−3/2). The remaining term is Σₚ≤ₘ p^(−s).

Chebyshev’s estimate π(t) = O(t/log t), followed by partial summation and the substitution u = log t, gives Σₚ≤ₘ p^(−s) = O(1 + ∫[log 2,L] e^(δu) du/u). The endpoint term is bounded because m^δ/L = 1. Split the integral at 1/δ. The first piece is O(log(1/δ)) = O(B). In the second, substitute v = δu to obtain an integral from 1 to B of eᵛ/v, which is O(eᴮ/B) = O(L/B). Both quantities are o(L), proving the claim.

Fix ε > 0 and set X = floor(exp((1 + ε)L²/B)). Rankin’s bound now gives Ψ(X, m)/X ≤ exp(−δ log X + o(L)) = m^(−1−ε+o(1)).

There are X − m + 1 length-m intervals inside [1, X]. A smooth integer belongs to at most m of them, so at most mΨ(X, m) = o(X) intervals contain a smooth integer. Since m = o(X), at least one interval contains none.

Use this interval in the preceding construction. Every word has a witness no larger than Xᵐ, hence log M(m) ≤ (1 + ε)m(log m)²/log log m. The conclusion with coefficient 1 + o(1) follows because ε was an arbitrary fixed positive number.

Exact checks and their scope

The main Python program computes H(m) exactly for 1 ≤ m ≤ 250. At a fixed start k, the least candidate witness is Dₖ = lcm(k + 1, …, k + m − 1). The start works exactly when k does not divide Dₖ. If k divides Dₖ, it divides every possible witness at that start as well.

A prime start gives an initial finite witness. For m ≥ 2, the lcm lemma then makes the search finite: once k^(m−1) > H(m)(m − 1)!, every later start has a larger lower bound than the current witness. The stopping comparison uses exact integers. The program also verifies 18,000 instances of both divisibilities in the lemma.

A separately written program uses prime valuations and the stronger binomial cutoff to recompute all family values through m = 40. A literal scan of divisor indicators independently checks m ≤ 5. All agree. These computations check the implementations and finite examples; the asymptotic results follow from the proofs above.

The newer maximum-growth certificate has a separate exact audit: 12,000 lcm divisibility cases, 94,782 forbidden-start cases and nine exact minimum examples with a proved stopping bound. Those checks and the one-zero-profile verifiers are in the further research download. The asymptotic estimate is proved analytically in the new paper.

What remains open, and who did the work

The maximum and arithmetic mean growth rates remain open here. The new lower bound shows that the difficult patterns have superexponential least witnesses, while the smooth-number construction supplies the stated universal upper bound. A sharp asymptotic for one family does not imply that it attains the maximum, and the construction does not determine the typical least witness.

The original question and direct Stack Exchange API showed no answers when checked on October 19, 2026. A focused search of the question, its terminology, family values and related lcm literature did not locate a matching result. That search does not establish historical priority.

Sulayman Bowles initiated and directed the work. OpenAI Codex selected and developed the arguments, wrote the exposition and verification programs, and carried out separately prompted mathematical reviews and exact computations. These checks are automated review, without independent human peer review or formal verification. This page publishes the completed bounds as author-hosted research; it does not represent journal acceptance.

Sources

1. Ilkka Törmä — Occurrence of binary words in divisibility patterns

   MathOverflow · 2020-09-30 · Original mathematical question

   Verified Oct 19, 2026

   Defines the maximum and arithmetic mean problems and supplies the displayed prior bounds. The page and recorded direct API response showed no answers when checked; no answer has been submitted to MathOverflow by this work.

2. Bakir Farhi — Minorations non triviales du plus petit commun multiple de certaines suites finies d’entiers

   Comptes Rendus Mathématique 341(8), 469–474 · 2005 · Prior lcm estimate cited in the original question

   The particular consecutive-interval divisibilities needed in this article are proved directly above. This citation credits the context supplied by Törmä.

3. Andrew Granville — Smooth numbers: computational number theory and beyond

   MSRI Publications 44, Cambridge University Press, 2008, 267–323 · 2008 · Prior smooth-number method

   Section 3.10 presents Rankin’s upper-bound method. The Euler-product inequality used here is also derived explicitly in the article.

Supporting material

• New note: divisor-word growth and the stronger maximum bound

  Five-page paper proving the prime-zero-block lower bound, refined maximum and mean estimates, and the uniform one-zero profile. Includes verification scope, sources and Codex attribution.

• Earlier note: sharp family rate and universal bound

  Four-page earlier note with the complete family theorem and smooth-number upper bound, references, finite-check results and Codex disclosure. The newer maximum lower bound appears in the further research download.

• Earlier note: source, exact computations and automated audit

  LaTeX source, two standard-library Python verification programs, exact witnesses through m = 250, separately prompted automated review and reproduction instructions. The retained README describes status before website publication.

• Further checked mathematical work: proofs and exact programs

  Partial results for harder A078121 diagonal questions and divisor-word growth, with source, exact programs and automated reviews. General unresolved cases are stated explicitly.

Read next