3
$\begingroup$

The problem below is suggested by this one.

Suppose that we are given $2k$ integers $x_1,\dotsc,y_k$, and we want to find an integer $a$ so that $\gcd(a+x_i,a+y_i)>1$ for each $i\in[1,k]$. This is certainly possible if the product of any $\kappa$ of the differences $y_i-x_i$ has at least $\kappa$ distinct prime factors, for each $\kappa\in[1,k]$: for, by Hall's theorem, we can then associate with each $i\in[1,k]$ a prime $p_i\mid y_i-x_i$ so that all primes $p_1,\dotsc,p_k$ are pairwise distinct, and then use the Chinese Remainder Theorem to find $a$ subject to $a\equiv -x_i\pmod{p_i}$, $i\in[1,k]$.

Intuitively, I would expect that for the ``random'' choice of $x_1,\dotsc,y_k$ this should be possible. Can something of this sort be proved rigorously?

Fix an integer $k\ge 1$ and choose $z_1,\dotsc,z_k\in[1,N]$ at random, for $N$ large (or consider $[N,2N]$ instead). What is the probability that for every $\kappa\in[1,k]$, the product of any $\kappa$ of the numbers $z_i$ has at least $\kappa$ distinct prime factors?

If $k=1$, then the probability is $1-N^{-1}$ trivially; if $k=2$, then it still seems to be $1-O(N^{-1})$, in a slightly less obvious way. For any fixed $k$, the set of all integers with fewer than $k$ distinct prime factors is known to have zero density (references can be found here); consequently, for $k$ fixed and $N$ growing, with probability $1-o_k(1)$ all of $z_1,\dotsc,z_k$ will have at least $k$ distinct prime factors, whence, of course, the product of any $\kappa$ of them will have at least $k\ge\kappa$ distinct prime factors. Still, it seems to me that much more can be said; maybe, along the following lines:

What is the smallest number of integers to be deleted from $[1,N]$ so that for every choice of $\kappa\le k$ remaining integers, their product has at least $\kappa$ distinct prime factors?

$\endgroup$
  • $\begingroup$ Interesting question. $\endgroup$ – T. Amdeberhan Dec 25 '16 at 18:45
  • $\begingroup$ When you say "at random" do you mean with respect to a uniform distribution? $\endgroup$ – Stanley Yao Xiao Dec 25 '16 at 19:25
  • $\begingroup$ @Stanley Yao Xiao: Yes. $\endgroup$ – Seva Dec 25 '16 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.