How to construct a small coprime?

Question

Given an integer $n$, is there a deterministic algorithm to find in poly$(\log n)$ time an integer $q$, $n < q< n^{c}$, such that $gcd(q,n!)=1$? Here $c>1$ is some fixed constant.

Obviously, a small prime $n< q < 2n$ works. But those are really hard to find deterministically. One can of course, deterministically test primality of $n+1, n+2, \ldots, n+C(\log n)^2,$ but that's not yet proved to work. Taking $q=n!+1$ works for the $gcd$ condition, but such $q$ is too large for my applications. If $q< n^c$ is open, but say for the case $q< n^{O((\log n)^k)}$ this is known, what are the best known bounds?

Answer 1

This is really an extended comment.

I think that it's unlikely that an unconditional result of this type is known, because your problem is not all that different from the problem of finding a prime in the desired interval. For fixed $c$, the number of positive integers less than or equal to $x^c$ with no prime factor less than $x$ is asymptotic to $$c\cdot\omega(c){x \over \log x}$$ where $\omega$ is the Buchstab function. In other words the density of the numbers you're interested in is only larger than the density of primes by a constant factor, so it would be rather surprising to me if one of them could be found much more efficiently than a prime could be. Of course this is not a proof and one could imagine that suitable weakenings of the standard conjectures have been proved unconditionally, but again I would be rather surprised if that were true.

Also I'm not sure I understand your suggested weakening of the upper bound to $q < n^{O(n^\epsilon)}$. If $q$ is that large, then it takes something like $n^\epsilon \log n$ bits just to write it down, and that can't be done in polylog time. I suppose you could allow $q$ to be expressed using some "formula" that is more compact than binary representation, but in that case, very few numbers of that size are going to be expressible by a short formula.

Answer 2

If we could find a number co-prime to $2^n!$ in $n^{O(1)}$ time, or even just a number divisible by at least one prime greater than $2^n$, we could factor it to find such a prime. This would constitute a solution to the strong conjecture with factoring, so it is an open problem.

As far as I know, it is open whether or not it is possible to find a prime larger than $2^n$ in time $2^{\frac{n}{2}+o(1)}$ with or without a factoring oracle. The finding primes page doesn't say this explicitly but I don't see any obvious method to beat this using a factoring oracle from the information presented. Perhaps someone can confirm that this weaker problem is open.

Answer 3

Did someone say coprime?

Let $k=\pi(n)$ be the number of primes at most $n$, and $P$ be their product. The question asks for a number coprime to $P$ within a certain range. Gerry Myerson notes that one conjecturally has to test only about $(\log n)^2$ numbers for primality. I recommend more explicitly looking near a chosen number $d$ for a number $c$ that is coprime to $P$.

Estimates by Iwaniec shows $c-d$ is $O((k\log k)^2)$, however the constant is not known to me. An uglier but explicit (and not entirely original) estimate is hiding behind a link at MathOverflow question 37679, and a weak version is that $c-d$ is (for $k$ not too small) less than $k^{3.81 \log\log k}$. So a brute force algorithm still has to check a lot of numbers, but not as many as $n^{O(n^\epsilon)}$.

Indeed, by sieving around $d$, one can cut the number of candidates to be tested for coprimality by a sizable fraction. The problem is now to build $P$ and check $\gcd(P,c)=1$. One can take a product of c's, find the common divisor of this product with $P$, and use that information to rule out false candidates. However, that could still be $O(n)$ many bits to play with.

If you are freely willing to let go of determinism, you can try some dynamic systems to generate candidates. One is iterations of the Collatz function on a seed $d$, one is choosing one or more low degree irreducible polynomials and feeding values to them in hopes of finding a coprime, and another is bit concatenation. Take the operation $ f(n) = \lfloor n/2 \rfloor $, and form the bit string from bit strings for $n,$ $f(n),$ $f(f(n)),$ and whatever combination of iterates you choose, for a candidate to be coprime. Again, testing for coprimality will be expensive.

Gerhard "Didn't Say Jacobsthal This Time" Paseman, 2017.09.13.