0:006:20

Recursos

Resumen

Take any integer with at most k prime factors. How long can a run of consecutive integers get when every one of them shares a factor with it? This class shows you how to bound that length, and how the new proof that it grows at most quadratically fits together.

From covering to counting

  • Jacobsthal's function j(n) is the least m such that every m consecutive integers include one coprime to n. h(k) is the largest j(n) over all n with at most k prime divisors, so h(k) − 1 is the longest run that k primes can cover [0:05]. For example, 2, 3 and 5 cover 24–28, and h(3) = 6. The first k primes are the worst case up to k = 23, but not at k = 24.
  • Jacobsthal asked whether h(k) ≪ k². Iwaniec proved k² log² k, and the best lower bound is about k(log k)². The new result gives h(k) ≤ C k²/(log log 3k)² [0:54].
  • Turn it around and count survivors. Forbid one class aₚ at each prime p ≤ z. By the CRT, this is the same as being coprime to ∏p after a shift. Theorem 1.2 says at least c·YV₀/B² integers in [1, Y] survive [1:32].

Why a count, not positivity

If no choice can cover Y integers, then no run of length Y is covered by the primes ≤ z. But n can also have prime divisors above z, and each one strikes out survivors [2:21]. Take z ≍ k log k / log log k. Then Y ≍ k²/(log log k)², and the at most k large primes remove only O(k(1 + X/log X)) survivors, where X = Y/z. That is a small fraction of the guaranteed count, so an integer coprime to n remains [2:59].

The engine

  • Decreasing-prime tree: S_d = N_d − Σ S_dp. Signs alternate with depth, as in Brun's sieve. An admission rule keeps the progressions long, and replacing N_d by μ_d = (Y/d)V₀ gives the reference tree [3:36].
  • Parameter 2: the lower linear-sieve function f vanishes at s = 2, which is where the exponent 2 comes from. A boundary term of size B⁻² survives. Derivative weights of f and F turn paths into a Markov chain with regenerations, and the key renewal theorem evaluates the term [4:19].
  • Comparison: the fundamental lemma handles long progressions. On short ones, an inverse estimate forces alignment with a rational A/D. Variance bounds and stops at even nodes keep the losses inside the positive margin [5:12].

Next time you read a sieve bound for gaps or coverings, ask: does it prove positivity, or a count that pays for the primes it left out?

Jacobsthal's function and the quadratic bound

OpenAI Math Preprints

Clase 47 / 100

Ver clases