MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The ordinary Jacobsthal function $j$ is defined by setting $j(n)$ as the smallest number $m$, such that for each consecutive $m$ numbers in the integers, there is at least one of the numbers comprime to $n$. There are estimes for $j$, for example $$j(n) \ll \log ^2 (n)$$ and it is conjectured by Jacobsthal, that we could improve this to $$j(n) \ll ( \log (n) / \log ( \log (n)) )^2.$$ See for example .

We define now $h(n)$ as the smallest number $m$, such that for each square $a \in \mathbb{N}$, the sequence $$a+1, a+1, \ldots, a+m$$ contains at least one number comprime to $n$. My question is now, are there any good upper estimates for $h(n)$ ? Clearly, $h(n) \leq j(n)$ holds, so we could take the above estimate, but I am searching for something stronger, perhaps like $$h(n) \leq C \log(n),$$ where $C=2$ or so.

share|cite|improve this question
There are still a lot of quadratiic residues for many numbers. My guess is that the upper bound will not drop significantly, and may not drop at all. The analysis becomes more challenging for me because the answer may depend on the multiplicity of prime factors in the number. If -1 is not a quadratic residue and there are about half as many qrs as nqrs less than n, then by symmetry I expect the upper bound to be the same. Even in the general case I expect there to be no provable decrease in the upper bound. Gerhard "Ask Me About Jacobsthal's Function" 2011.07.14 – Gerhard Paseman Jul 14 '11 at 15:56
Also, Erdos has for almost all n that j(n) is not far from a bound like log(n)log(log(n)) in a 1962 paper. You might review that paper to see how much carries over to your situation. Gerhard "Email Me About System Design" Paseman, 2011.07.14 – Gerhard Paseman Jul 14 '11 at 18:38
I would like to know the motivation for choosing squares. Is it an approach to study primes of the form $a^2+1$? Also, I should mention that I do not see a way to provide any tight bounds on $h(m)$ without making assumptions on $m$ like "Suppose every prime factor of $m$ has -3 as a nqr..." Gerhard "Ask Me About System Design" Paseman, 2011.07.15 – Gerhard Paseman Jul 15 '11 at 18:53
Do we have to start with a given n? I have a function that when given m will create an n that will be prime to all a in those ranges. – Fred Kline Dec 11 '11 at 8:39
@panoramix, sorry for the delay. "On the integers relatively prime...[long title] ... by Jacobsthal" in Math. Scand. (1962) pp 163-170, by Erd\H{o}s. You can find a copy online with not too hard a web search. I put up a preprint on ArXiv with a short reading list and bibliography, if you want to see some recent progress. I especially recommend Hagedorn's paper. Gerhard "Version Two Arriving Next Week" Paseman, 2014.01.07 – Gerhard Paseman Jan 7 '14 at 23:52

I take back what I said in the comments about the bound not shrinking.  I am convinced that one can get much tighter bounds, and that the tighter bounds will depend massively on the quadratic residues for each of the primes involved.

To set the stage, I change notation slightly.  I use $m$ for the argument to $j()$, and I use $n$ for the number of distinct prime factors of $m$.  I also insist $m > 1$.

One of the more accessible results is that $j(m) = j(k)$ if $m$ and $k$ have the same prime factors.  Further if the prime factors are all larger than $n$, then $j(m)= n+1$, so there is a certain uniformity in the analysis and results for a large and simply stated class of numbers.

(Advertisement; I am working on similar statements where $n$ is replaced by something like $\sqrt(n)$.  Email me for more detail.)

Many of the standard bounds for $j(m)$ can be expressed in terms of $n$.  When I posted my comments above, I thought something similar would be true for this version.  However, checking a few examples leads me somewhere completely different.

For $m$ a prime power, $j(m)=2$.  The same holds for the new variation if and only if $-1$ is a qr of the prime dividing $m$.  However, things change when $n>1$. $h(6)=j(6)=4$, but this does not hold for all numbers of the form $2p$. $h(m)$ can vary from 2 to 4 depending on $m$ even if $n$ is restricted to 2.

To make things interesting, I computed $h(385)$, which is bounded above by 4. There are 6 values of a mod 385 to show $j(385)=4$. To get $h(385)=4$, I had to find a square which was 4 mod 7, 9 mod 11, and 4 mod 5. The square of 47 fit the bill, but I could imagine different primes with qrs that would not nicely fit in the set {-3,-2,-1}, so $h(m)$ will not always reach 4 or higher when $n=3$; it will depend on getting qrs which are small negative numbers. For higher $n$, you may not achieve $h(m)>n$ without choosing the $n$ prime factors carefully. And this analysis is using only squarefree $m$; I do not know what happens in the general case.

EDIT 2011.07.29 I let the presence of quadratic residues rattle me into thinking that $h(m)$ would depend on the multiplicity of prime factors of $m$. It does not. As is the case for $j(m)$, the value of $h(m)$ depends only on the set of prime factors of $m$, and so there is no "general case": it suffices to assume $m$ is squarefree. END EDIT 2011.07.29

I am having a few challenges showing upper bounds without having to worry about quadratic residues. This problem is a can of worms I am not ready to tackle. Certainly nothing like the uniform results involving sufficiently large prime factors will hold. One approach involves "tiling" a candidate interval with appropriate primes, and then solving $n$ many quadratic congurences simultaneously. I don't know enough about quadratic residues to see any clean looking results here. It is an interesting variation on which I welcome other viewpoints.

Gerhard "Jacobsthal's Function Is Tough Already" Paseman, 2011.07.15

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.