Analogues of Jacobsthal's function

Question

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?

Answer 1

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

Answer 2

In looking for some simple bounds on Jacobsthal's function, I came across an argument which can be viewed as a slight modification of an argument of Kanold in his 1967 paper in Math. Annalen 170. (It could be viewed as a recombination of Hilfsatz 4 and Saetze 2,3, and 4.) However, Kanold's wording does not reflect the perspective above offered by Timothy Foo, and I want to suggest a technique that he might apply to his analogues.

Kanold shows an upper bound on $g(nm)$ with $n$ coprime to $m$ as the smaller of two expressions, one slightly smaller than $ng(m)$ and the other slightly smaller than $mg(n)$. A key fact is that the coprimality with respect to $n$ of members of an arithmetic progression AP with difference $m$ are not severely altered by multiplication mod $n$ by $f$, the inverse of $m$. Now AP$f$ looks mod $n$ like a sequence of common difference 1, so any $g(n)$ consecutive members of AP$f$ (and thus of AP) will have a member coprime to $n$.

The perspective here is that there is a map which preserves both coprimality status and enough order to get results mod $n$. What brings it home is if we use Timothy's perspective, we take an integer $N=nm$ and view it as a Cartesian product, then we can use a kind of (limited order, limited coprimality)-preserving transformation to get results like those of Jacobshal and Kanold. At present they will not be as good as Iwaniec's techniques, but for the original problem I am finding results which improve on those of Kanold, and I suspect Timothy can use them for his analogues, once he finds the right maps.

For those who might prefer a revised take on Kanold's Hilfsatz 4, here is the key idea: for squarefree $n$ and nice divisor $d$ of $n$, let's write $f=n/d$, note that $f$ and $d$ are coprime, and finally that any $g(d)$ consecutive members of the sequence $1+tf$ as $t$ ranges over the integers have at least one member coprime to $d$ as well as coprime to $f$. This immediately leads to $g(n)\leq fg(d)$.

I will follow up elsewhere with how nicely this can be used, as wells as remarks on a recent arXiv preprint which helped inspire this post.

Gerhard "Ask Me About Jacobsthal's Function" Paseman, 2012.10.22