A Representation of Large Integers from Combinatorial Sieves

Abstract

For any positive integers k and m, and any /, 0 ≤ / < m, we show that there is a number β = β(k, m) > 0 such that any sufficiently large integer x can be represented as x = ƒ_1··· ƒ_k + r · m + / where ƒ_1,..., ƒ_k and r are nonnegative integers and r·m + / ≤ x^β and ƒ_i≥ x^β for each i = l,..., k. This says one can find numbers with certain factorizations in "short arithmetic sequences". The representation is proven by way of the number sieve of Brun and its generalization to multiplicative functions by Alladi; by studying the distribution of the arithmetic function ν(n), the number of distinct prime divisors of n, on sieved short arithmetic sequences. This has applications in Combinatorial Design Theory and Coding Theory.