# How to construct a small coprime?

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?

• @JasonStarr - Sure. Updated. Sep 13 '17 at 10:29
• There is a deterministic polynomial-time algorithm to test for primality, and you only have to test about $(\log n)^2$ numbers if the standard conjectures are true. Sep 13 '17 at 13:16
• @GerryMyerson Correct. I know. But I want to have a theorem free of conjectures. Sep 13 '17 at 16:47
• Then maybe you should say that, and any other secret conditions, in the body of the question. Please edit. Sep 13 '17 at 21:59
• @GerryMyerson Hoping for a result not a conjecture is not a secret condition. Maybe I am missing something about MO, but that's how questions normally work. Sep 13 '17 at 22:39

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.

• Ok, you are right. I really want something like $q<n^c$ but can live with $n^{O((\log n)^k)}$. Sep 14 '17 at 5:43

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.

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.

• The estimate is in Arxiv 1311.5944, if you want to skip question 37679. Gerhard "Is On A Link Diet" Paseman, 2017.09.13. Sep 13 '17 at 15:28
• As already observed in the problem there is a prime between $n$ and $2n$. This is already stronger than what would follow from Iwaniec's bound on the Jacobsthal problem. Sep 13 '17 at 15:35
• You misunderstand the question. I want deterministic algorithm which works in poly(log n) time. I want q to be as small as possible, but can live with somewhat larger q if that's the best known. None of what you wrote moves in that direction. Sep 13 '17 at 16:49
• Igor, it would not surprise me that what you seek to solve is CoNP hard. If so, do you still want to reject alternatives? @Steven, that is in the worst case. If time is important, one can try several starting $d$ and not test so many. However, I am offering what I know, and I may never be able to give Igor the answer he wants. Gerhard "Sometimes The Answer Takes Longer" Paseman, 2017.09.13. Sep 13 '17 at 19:37
• @GerhardPaseman : If Igor's problem is co-NP hard then either P = NP or Cramér's hypothesis on prime gaps fails badly. Either one of these would surprise most people. Sep 14 '17 at 15:17