EDIT: Gerhard Paseman has given some wonderful answers to this question below. Thank you. This is an attempt to revisit this to hopefully make the question more rigorous with some notation and try to provide motivation from the context of the Bateman-Horn conjecture, and ask whether this is fruitful or not. (It seems not. I'd love to get the opinion of anyone interested, even privately if you prefer.) Gerhard has mentioned other applications of Jacobsthal's function, and those certainly sound very interesting.

"Disclaimer": Everything here is redundant. There is probably nothing written here that has not been expressed in better form in the language of sieve theory, in

J. B. Friedlander, H. Iwaniec, Opera De Cribo

or Terry Tao's blog post "254B, Notes 7, Sieving and Expanders".

Therefore, the purpose of writing this is only to provide "closure" to the original question and to answer Gerhard's question of "why Jacobsthal's function interests me". First define: A "Jacobsthal-type function for polynomials":

Let $f\in \mathbb{Z}[x]$. Define $g_f(n)$ to be the length of the shortest interval so that there always exists an $m$ in that interval with $(f(m),n)=1$. When $f(x)=x$, we recover the original Jacobsthal's function. Let's now set up some notation: $f$ has degree $d$. $C_k$ is the set of primes for which $f$ has $k$ roots mod $p$. These all have some density from Chebotarev's density theorem. Let

$$ P_{x,f}=\prod_{k > 0}\left(\prod_{\substack{p \in C_k\\2 \leq p \leq x^{d/2}}}p\right). $$

Let $A \subset \mathbb{Z}$ be defined by $m\in A$ iff $(f(m),P_{x,f})=1$.

The Bateman-Horn conjecture says that for irreducible $f\in \mathbb{Z}[x]$ where the gcd of all its values is $1$, we should expect:

$$ \sum_{\substack{n \leq x\\f(n) \in \mathbb{P}}}1 \sim \mathfrak{S}(f)\frac{x}{d\log x}, $$

where $\mathfrak{S}(f)$ is a constant depending on $f$. The question is as follows: The Bateman-Horn conjecture implies that for sufficiently large $x$, we should expect that

$$ A \cap (x^{1/2},x) \not= \emptyset. $$

From

R.C. Vaughan, On the order of magnitude of Jacobsthal's function, Proc. Edinburgh Math. Soc., 20, pp329--331,

we learn that the original Jacobsthal's function, $g(n)$, is believed to satisfy an upper bound of the form

$$ g(n) \ll \omega(n)^{1+\epsilon}. $$

This is believed but stronger than what has been proven. Consider the functions $g_f(n)$. In line with what Gerhard Paseman described in a previous answer to the original question, perhaps $g_f(n)$ will satisfy analogous upper bounds, but now the upper bound must be able to combine the

$$ \omega\left(\prod_{\substack{p|n\\p\in C_k}}p\right) $$

in some way that also involves $k$. In any case, in order to achieve the intersection of $(x^{1/2},x)$ with $A$ via the route of using only $g_f(n)$, we would require $g_f(P_{x,f})$ to be majorized by $x-x^{1/2}$. But the number of primes dividing $P_{x,f}$ has order of magnitude $\asymp x^{d/2}/\log x$, so this doesn't seem likely for general $f$. As a formality, and also to hopefully learn any perspectives on this, here are some questions anyway.

Firstly, what's a good conjectural, in terms of strongest possible belief, upper bound on $g_f(n)$ that accounts for $f$ having possibly a different number of roots for different primes (hence reflecting the information in the $C_k$), and is also able to show that irreducible polynomials of the form, for instance, $f(x)=x^5-x+5r$ will simply have $g_f(P_{x,f})$ infinite? (Cases like irreducible instances of $f(x)=x^5-x+5r$ have a prime $p$ for which $k=p$.)

Secondly, in the context of Bateman-Horn, would even the strongest possible beliefs concerning $g_f(P_{x,f})$ be insufficient to get $A$ to intersect $(x^{1/2},x)$? (From Bateman-Horn, it seems like any interval $(a,a+x)$ of length $\sim x$ should be expected to intersect $A$ when $a$ is not too large relative to $x$.) For $f(x)=x$ with $d=1$, it seems that the beliefs about $g(n)$ do give $g_f(P_{x,f}) \ll (x^{1/2}/\log x)^{1+\epsilon} \ll x-x^{1/2}$ and thus one can use beliefs concerning $g(n)$ to get a prime in $(x^{1/2},x)$. This is really a question on this approach not seeming to extend to general $f$. Perhaps it could be converted to a question on relating beliefs about $g_f(n)$ to representation of numbers with at most n_f prime factors by $f$, for some $n_f$ depending on $f$, but there already exist ways to deal with this. Example: Exercise 5 of Terry Tao's blog post, "254B, Notes 7: Sieving and Expanders".

Thank you very much!

Original Question:

Hello,

Jacobsthal's function, $j(n)$, is defined to be the longest sequence of consecutive integers such that all integers in the sequence are not relatively prime to $n$. H. Iwaniec has shown that

$$ j(n) \ll (\log n)^2. $$

So this is like saying that if you take a sequence longer than that upper bound, it will definitely intersect $(\mathbb{Z}/n\mathbb{Z})^{*}$. Now here's where the analogue comes in. (Let's suppose that $n$ is squarefree.) $(\mathbb{Z}/n\mathbb{Z})^{*}$ is not just any subset of $\mathbb{Z}/n\mathbb{Z}$, it is constructed as the cartesian product of $(\mathbb{Z}/p\mathbb{Z})^{*}$ over each $p|n$.

I would like to replace $(\mathbb{Z}/p\mathbb{Z})^{*}$ here by some other subset of $\mathbb{Z}/p\mathbb{Z}$ formed by deleting other congruence classes modulo $p$ (not necessarily $p\mathbb{Z}$). But let's say that for each $p$, the number of congruence classes deleted is bounded by a constant. Then take the cartesian product over $p|n$ to obtain the subset, say, $A(n)$, of $\mathbb{Z}/n\mathbb{Z}$ for which we want an upper bound for a function analogous to $j(n)$. So that any sufficiently long string of consecutive integers will intersect $A(n)$.

Since these sets $A(n)$ don't seem too different from $(\mathbb{Z}/n\mathbb{Z})^{*}$, should one expect that a power of $\log n$ is reasonable as an upper bound to the function analogous to $j(n)$? Gerhard Paseman, perhaps you've well thought through all this already!

I will link to the question Gerhard Paseman asked on sieves, since it could be relevant. Link: Erik Westzynthius's cool upper bound argument: update?