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](http://terrytao.wordpress.com/2012/03/01/254b-notes-7-sieving-and-expanders/) "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?](https://mathoverflow.net/questions/37679/erik-westzynthiuss-cool-upper-bound-argument-update)



Analogues of Jacobsthal's function
I will register a lengthy opinion here, which represents my feelings
on the subject. I have no proofs to offer at this time.


I have not taken the perspective of viewing the set of numbers coprime to
a squarefree integer $m$ as the Cartesian product of smaller sets. This
perspective may be useful, but it is hard for me to translate this into
finding long regions which avoid this set. It is easy for me to view this
as a collection of short intervals of integers, each of which is coprime to $m$,
but computing how many of each length and where they are positioned and how
far apart they are when laid out on a number line, in short, linearizing
the set and looking at its distribution that way, is a challenge I have yet
to tackle, and I do not see what general results I can glean from this
approach. I think understanding the distribution is important, and hope
this perspective will yield insight.


As an exercise, try using this perspective to show that if all the
primes dividing $m$ are greater than $n$, with $n$ being the number of distinct
prime factors of $m$, then $j(m) = n+1$. A failure to do so should not been
taken as a sign that this is a bad perspective; it should be taken as a
sign of how radical a shift one must make in one's thinking about Jacobsthal's
function. If you succeed in this exercise, try deriving some other simple
results, for example, what should $j(m)$ be roughly if the smallest prime factor is at least $2n/3$. At this writing, I do not know how to try either problem with this perspective.


I believe (and it should be easily confirmed), that if one were to take just one
different residue class other than 0 for each prime $p$ dividing $m$, that the
Chinese Remainder Theorem shows you are just considering the same problem with
a different offset. So you might standardize things by always removing the
0 class along with whatever other residue classes you might consider removing.


I too would expect some power of $\log m$ to be an upper bound for the maximum
length of an interval of consecutive integers which happen to lie in the
union of the removed classes. However, I would look at data using small numbers first, with $n$ the number of distinct prime factors of $m$ being slowly ramped up, and seeing how much of a role the sizes of the prime factors with respect to $n$ play in the
analogous function. You will need to give an exact definition in order to play with it,
but I imagine an argument like that of Stevens combined with an aggressive attitude
of error control that I brought to the argument should give you an upper bound for your analogous function like $O(2^{C\log n \log\log n})$, which is worse than Iwaniec's but is easily made explicit. My feeling is that C will be proportional to the bound you put
on the number of classes removed for each prime $p$. You may have to treat $p=2$
separately or ignore that prime in your studies to get more manageable proofs.


Jacobsthal's function currently has uses in proofs regarding billiards, regular languages, visibility problems, and lower bounds for prime gaps, among others.
Your analogues may prove similarly useful, but it would be nice to have a
motivating example. Perhaps you could tell us why this version interests you.


Gerhard "Also Considering Jacobsthal Function Variations" Paseman, 2012.02.12


