residue classes of primes, covering intervals and bounds on the different ways - MathOverflow

residue classes of primes, covering intervals and bounds on the different ways

2011-03-06T13:18:21Z

Take the first $n$ primes $p_1,...,p_n$ and the primorial $P_n$ .Denote by $p_i$ every prime bigger than $p_n$ and smaller than $P_n$.

1) Is that true that there always be a number in any interval of consecutive integers of length $P_n$ not divided by any $p_i$? (It's the same as taking a residue class $r_i\bmod p_i$ for every $p_i$ in every possible way and wondering if you can cover all the numbers in the interval $[0,P_n-1]$.)

ADDED:

2) Even if we do not know if we can cover this interval, can we have any good upper bound on the number of ways?

Answer by Will Jagy for residue classes of primes, covering intervals and bounds on the different ways

2011-03-06T21:33:20Z

I did some computer programming to check plausibility. In future I request that you do this step yourself.

For $p_n = 3$ and $P_n = 6,$ the only prime in between is 5, and any interval of length 6 contains an integer not congruent to any prescribed value mod 5.

In C++ I was able to check up to 10,000,000. For definiteness I took the residue classes to all be 0, that is I checked multiples of the primes between $p_n$ and $P_n.$ For the $p_n$ I checked, I was able to find only relatively short intervals of consecutive numbers, each of which is divisible by at least one prime between $p_n$ and $P_n.$ That is, these intervals have lengths much shorter than $P_n$ itself. Thus in any interval of length $P_n,$ it should be quite easy to find numbers that are not divisible by any of those primes. Indeed, the probability of picking a success at random appears to increase with $p_n.$

For example, for $p_n = 5, P_n = 30,$ I tried to find long intervals where each number had at least one divisor in the set 7, 11, 13, 17, 19, 23, 29.

 691558 = 2 * 7 * 47 * 1051
 691559 = 11 * 62869
 691560 = 2^3 * 3^2 * 5 * 17 * 113
 691561 = 13 * 53197
 691562 = 2 * 19 * 18199
 691563 = 3 * 29 * 7949
 691564 = 2^2 * 23 * 7517
 691565 = 5 * 7 * 19759

The bound of 10,000,000 is not on primes, it is on the output, such as 691565 < 10,000,000.

  p_n = 5       P_n = 30    0.592302   2.96151
 length = 8
  691558  691559  691560  691561  691562  691563  691564  691565


  p_n = 7    P_n = 210  0.454539   3.18177 
  length = 20
  635088  635089  635090  635091  635092  635093  635094  635095  635096  635097
  635098  635099  635100  635101  635102  635103  635104  635105  635106  635107

    p_n = 11     P_n = 2310   0.348014   3.82815
length = 43
    2113    2114    2115    2116    2117    2118    2119    2120    2121    2122
    2123    2124    2125    2126    2127    2128    2129    2130    2131    2132
    2133    2134    2135    2136    2137    2138    2139    2140    2141    2142
    2143    2144    2145    2146    2147    2148    2149    2150    2151    2152
    2153    2154    2155

    p_n = 13     P_n = 30030   0.283807   3.68949
length = 207
   29745   29746   29747   29748   29749   29750   29751   29752   29753   29754
   29755   29756   29757   29758   29759   29760   29761   29762   29763   29764
   29765   29766   29767   29768   29769   29770   29771   29772   29773   29774
   29775   29776   29777   29778   29779   29780   29781   29782   29783   29784
   29785   29786   29787   29788   29789   29790   29791   29792   29793   29794
   29795   29796   29797   29798   29799   29800   29801   29802   29803   29804
   29805   29806   29807   29808   29809   29810   29811   29812   29813   29814
   29815   29816   29817   29818   29819   29820   29821   29822   29823   29824
   29825   29826   29827   29828   29829   29830   29831   29832   29833   29834
   29835   29836   29837   29838   29839   29840   29841   29842   29843   29844
   29845   29846   29847   29848   29849   29850   29851   29852   29853   29854
   29855   29856   29857   29858   29859   29860   29861   29862   29863   29864
   29865   29866   29867   29868   29869   29870   29871   29872   29873   29874
   29875   29876   29877   29878   29879   29880   29881   29882   29883   29884
   29885   29886   29887   29888   29889   29890   29891   29892   29893   29894
   29895   29896   29897   29898   29899   29900   29901   29902   29903   29904
   29905   29906   29907   29908   29909   29910   29911   29912   29913   29914
   29915   29916   29917   29918   29919   29920   29921   29922   29923   29924
   29925   29926   29927   29928   29929   29930   29931   29932   29933   29934
   29935   29936   29937   29938   29939   29940   29941   29942   29943   29944
   29945   29946   29947   29948   29949   29950   29951

     p_n = 17     P_n = 510510   0.236611   4.0224
   length = 1 + 435005 -  433756 = 1250
   433756  433757  433758  433759  433760  433761  433762  433763  433764  433765
....
...
   434996  434997  434998  434999  435000  435001  435002  435003  435004  435005.

Answer by Aaron Meyerowitz for residue classes of primes, covering intervals and bounds on the different ways

2011-03-07T01:07:15Z

Edited version: Just to be clear, the question is: can we find integers $n$ and $s$ and arithmetic progressions $r_{n+i} \mod p_{n+i}$ where i ranges from 1 to the largest $j$ such that $p_{n+j} \lt P_n$ such that the arithmetic progressions cover the interval $[s,s+P_n-1]$? I would guess that it IS possible (but I could be wrong). However it would likely require a huge number of progressions. A better question might be given a certain set of primes (or pairwise relatively prime moduli), what is the longest interval you can cover?

There is no harm in assuming that $s=0$ since we can instead look at the progressions $r_{n+i}-s \mod p_{n+i}$.

If it can be done at all then the number of ways to do it (provided that we do get to pick $s$ to be what we want) is simply the product of all the primes in the range: Whatever residue classes you choose will create a pattern of covered and uncovered integers which is periodic but with an extremely long period. Picking different residue classes creates the same pattern, just shifted.

A question which makes some sense is: Bound the number of ways to choose residue classes and cover $[0,P_n-1]$ . Even that would be huge. One would have some carefully chosen progressions for the smaller primes and also an enormous number of one member residue classes filling in the holes. Those one member progressions could be shuffled around at will.

We would certainly need to have $\sum_1^j\lceil\frac{P_n}{p_{n+i}}\rceil \gt P_n$ but this is on the overly optimistic chance that we could have all the progressions distinct (At least for $p_{n+i} \lt \sqrt{P_n}$ the progressions will not be completely disjoint) and that every one could be positioned to get in the maximum number of occurrences.

A condition which does not make the second assumption is $\sum_1^j\frac{1}{p_{n+i}} \gt 1$ so $\sum_1^{n+j}\frac{1}{p_{k}} \gt 1+\sum_1^{n}\frac{1}{p_{k}}$. By my calculations using this estimate $$\sum_{p \lt x}\frac1p \ge \ln \ln (x+1) - \ln\frac{\pi^2}6$$ that condition requires that $p_n$ is at least $23$ meaning that $P_n$ is greater than $2.23\cdot 10^8$ and $j>1.2 \cdot 10^7$. This makes the greedy strategy unattractive (Start with $s=0$ and pick residue classes repeatedly to take care of the smallest uncovered integer).

Answer by Gerhard Paseman for residue classes of primes, covering intervals and bounds on the different ways

2011-03-07T08:36:34Z

To clarify Aaron's observations: since the original post asked for something to be true in every interval (of consecutive integers) of length P_n, the residue classes are indeed a red herring. The Chinese Remainder Theorem says that there will be a number common to all those residue classes, and therefore the problem will look the same whether the classes are nonzero residues or not, since we are dealing with finitely many primes.

This now turns into a problem of Jacobsthal's function on numbers of the form (P_N/P_n), where P_N is the product of all primes less than P_n, which in turn is the product of all primes less than n. Jacobsthal's function asks for the length j(m) of the smallest interval of integers which guarantees at least one integer coprime to m, i.e. lies outside the desired residue classes. Aaron is right when he requests that the sum of the reciprocals of the primes involved should be greater than 1. My computation suggests this starts to happen when n=5, p_n= 11, P_n = 2310, and there are roughly 340 (+ or - 20) primes involved in the product (P_N/P_n). I am trying to refine estimates to decide if j(P_N/P_n) is less than or equal to or greater than 2310. My instinct tells me greater, and that this will hold true for n> 4. I will update this later with the computations. In the meantime, you can try to use the upper bound estimates in the recent answer I posted to my Westzynthius question on MathOverflow.

Gerhard "Ask Me About Coprime Intervals" Paseman, 2011.03.07

Answer by Gerhard Paseman for residue classes of primes, covering intervals and bounds on the different ways

2011-03-16T10:23:36Z

1) is equivalent to asking if it is true that property $J(n)$, which is the assertion $j(P_N/P_n) \leq P_n$, holds for all integers $n$, where $P_n$ is the product of the first $n$ primes, $P_N$ is the product of the first $N$ primes where $N$ is the largest index such that $p_N < P_n$, and $j()$ is Jacobsthal's function $j(m)$ which gives the smallest integer $j$ such that any interval of $j$ or more consecutive integers contains at least one integer which is coprime to $m$. The original formulation involving covering an interval with residue classes, one for each prime $p_i$ with $n < i \leq N$, can be translated by the Chinese Remainder Theorem into one where the residues are 0, i.e. the classes are multiples of the prime instead of being an arithemtic sequence with common difference p_i. Aaron Meyerowitz showed that $J(n)$ was true for $n=3$ and claimed it was for $n=4$, Will Jagy observed that $J(n)$ was true and easy for $n=2$, and I showed that $j(P_N/P_n) = 9$ for $n = 3$ by a method similar to one outlined by Aaron in one comment, and that $74 < j(P_N/P_n)<=85$ for $n=4$ by an undisclosed but elementary method. I also suggested that $J(n)$ is false for all $n > 4$.

A method of showing for $n < 5$ that $j(P_N/P_n) < P_n$ comes from the fact that $\sum_{n < i \leq N} 1/p_i < 1$, and some simple estimates on $j(m)$ which are applicable to any $m$ such that the sum of the inverses of $m$'s distinct prime factors add up to less than 1. This method is no longer applicable for $n \geq 5$, as the indicated sum grows roughly as $\log(\log(p_N)/\log(p_n))$, but it does grow, suggesting that $J(n)$ is eventually false for sufficiently large $n$.

I had hoped to show upper or lower bounds to resolve the matter, but the upper bounds I have at my disposal, while explicit, are too weak to show $J(n)$ is true, and the best asymptotic bounds are also too weak, even making favorable assumptions on the (as yet unknown) multiplicative constants, while the best known lower bounds in the literature can probably be used to show $j(P_N/P_n) > c P_N$ for $c$ some constant less than 1, so the lower bounds are tantalizingly close to showing that $J(n)$ is false, that is that the interval $[0, P_N -1]$ can be covered by $N-n$-many residue classes, one for each prime $p_i$.

If one were to tweak things slightly, say allowing a couple smaller primes less than $p_n$ to help cover, or allowing not very many primes larger than $p_N$ to help (probably less than $n^6$ primes), then the answer to the modified question $J'(n)$ would be no, there would always be enough primes to cover.

One cover which shows how near a miss this is uses a midpoint sieve. Choose $L$ odd less than $P_n$ and forget even numbers for a while, and pretend you are covering the odd numbers in $[-L,L]$ with the classes centered about the missing point 0. For $n=4$ I used $L =73$ and covered both endpoints with the class belonging to 73, the next with the class belonging to 71, the next with the class belonging to 23 ( = 69/3) all the way down to 11, then I filled in the holes (odd numbers less than 74 which were 7-smooth) with 26 primes.

For $n=5$ one can use a midpoint sieve to cover something like 1700 number with the primes from 13 to 2309, and for $n=6$ something like 25000 for the primes from 17 up to 30030. (I have yet to double check the figures, so I am being purposely vague.) In particular, it seems that the coverage ratio for the set using the midpoint sieve is increasing, and this suggests one can do better by tweaking the midpoint sieve to show $J(n)$ true. Such tweaking is either random, so hit-or-miss, or computationally expensive, and I have no good heuristics at present for making substantial improvements on the midpoint sieve. The fact that the midpoint sieve does far better than 50% coverage for $n>4$ is one of my reasons for believing $J(n)$ is false.

I am trying to develop a technique to refine upper bounds, especially in the cases that the sum of the reciprocals of the distinct prime divisors is larger than 1 but still close to one. It is related to the following problem, which perhaps someone here can shed light upon. For $M$ small, I was able to use a relative of this problem to show $j(P_{46}/P_4) < 83$.

I want to see how poorly I can cover small portions of the number line according to the following constraints: 1) I only need to cover some subset around 0 of the number line $[-M, M]$, so I can set my boundaries for computation to numbers not exceeding $2M$; 2) I have 0 already covered by something other than a tile, so no need to worry about that; 3) I have $k$ tiles of distinct lengths, the lengths ranging from 2 to $l$ where $l$ is larger than $k$ but not by much, and $l < 2M$; 4) each tile has to cover exactly one positive integer $p$ and exactly one negative integer $n$, and only a tile of length $p - n$ can cover both $p$ and $n$; and 5) I want to minimize simultaneously the amount of overlap and maximize the number of tiles I use. For an example cost function this could be maximizing $j - o$, where $j$ is the number of tiles I use and $o$ represents overlap; $o$ itself could be $(2j-u)$ where $u$ is the number of integers in $[-M,M]$ that are covered by at least one tile in the arrangement of $j$ tiles.

In this problem, if I could prove that if I used $j$ tiles all of distinct lengths less than $3j/2$, that the overlap would be (say) at least $j/4$, I could use that in improving upper bounds on $j(m)$ (different from but related to $j$) for some useful class of numbers $m$. Part of the challenge is that I can use all odd or all even tiles to create a partial cover with no overlap, and there are some mixes of odd and even length tiles I could use with no overlap, so using less than $k/2$ tiles is useless to me unless most of their lengths are sufficiently small.

To summarize: the tile problem might help in showing that $J(n)$ is true for more $n$. My guess is still that $J(n)$ is false for $n > 4$.

So much for my latest attempt at 1). For 2), I am guided by the following scenario: let us suppose I am right and that for $n=6$, say, one needs only the primes from $p_7$ to $p_{N-8}$ to use in a cover. Based on my studies of near-prime gaps, I expect (but cannot prove) that there would be 2 gaps of size larger than $P_n$ in the sequence of integers relatively prime to all the primes from $p_7$ to $p_{N-8}$ inclusive. Suppose these gaps were each of size $P_n +d$; that would give $2d+2$ ways (including reflections) of covering the interval $[0, P_n-1]$ with residue classes using the primes from $p_7$ to $p_{N-8}$. Now multiplying the whole set by $r=p_{N-7}$, this gives at least $r(2d+2)$ ways to cover the interval by residue classes which now allow the use of the prime p_{N-7}, plus at least $2r$ more ways, since each of the 2 gaps before corresponds to r different gaps in the sequence of number relatively prime to all the primes from $p_7$ to $p_{N-7}$ inclusive, and each of the new gaps would be larger by some amount d', whose average is most likely related to the average gap size in the sequence ($M/\phi(M)$, where $M$ is a product of the primes involved). Continuing up this way, we get at least $(2d+4)R$, where $R$ is the product of the last 8 primes before and including $p_N$.

This scenario ignores distribution of gaps in general, and assumes the largest gap is rare and (for sufficiently large N) the next largest is much smaller and far removed from the largest, which is what is commonly seen. So I would expect (but cannot yet prove) that a good upper bound on the number of ways to cover would be something like $\prod_{0 \leq d < s} p_{N-d}$ where $s$ is small, conjecturally $s \in O(\log(\log(\log(N))))$.

Gerhard "Will Guess For Bounty Points" Paseman, 2011.03.16

Answer by Gerhard Paseman for residue classes of primes, covering intervals and bounds on the different ways

2011-04-27T01:12:12Z

Let $M_4 = \prod_{p \text{ prime }, 10 < p < 210} p$. Another answer referred to computing $j(M_4)$, where $j(m)$ is Jacobsthal's function, and said that elementary estimates established the inequalities $74 < j(M_4) < 85$. It is possible to tighten those inequalities, and perhaps produce a hand-checkable proof that $j(M_4)=79$. Right now though, the assertion is being made with computer assistance, and some theory may need to be developed to bring it to the level of human verification.

One part of the verification is easy. Earlier I had a program find the following partial covering, where the integers to be covered range from $0$ to $77$, and the pairs are of the form $(d,a)$, meaning they cover the arithmetic progression $a +nd$ that lies within the interval of interest: $(11,0), (13,4), (17,8), (19, 7), (23, 5), (29, 10), (31,9), (37, 1), (41, 16), (43, 18), (47, 15), (53, 12), (59, 13), (61, 6), (67, 3), (71, 2)$.

Except for the class represented by $19$, all of these are covering the maximum amount possible for sets of this type, i.e. they are disjoint and the size of each set represented by $(d,a)$ is $\ceil(78/d)$. This near-extreme situation is crucial in being able to find a partial cover of this size. The uncovered numbers in the interval start at $14$ and go up to $63$; they are covered by trivial progressions, one for each of the primes from $73$ up to $199$, the other prime factors of $M_4$. This example thus gives $j(M_4)>78$.

The program also found many other partial covers. I have not checked them to see if any cover even more elements.

The best I could do by hand turned out to cover $72$ elements, instead of $74$ as I had claimed earlier. Once a nice search order was determined, the example above was found by a laptop in less than an hour. The same program did not find any partial covers for either of the intervals $[0,78]$ or $[0, 79]$ that could be extended to full covers.

I was able by hand to come up with a proof that $[0, 80]$ could not be covered, giving $j(M_4) < 82$, but to go any further seemed impossible with the tools I was developing, so I resorted to computer search to get to $j(M_4) < 80$. I invite verification of the assertion $j(M_4)=79$.

It is my hope to refine the techniques so that good estimates of $j(M_5)$ are possible, where $M_5$ is the product of primes from $13$ up to just below $P_5=2310$. One such goal is to determine whether $2310 < j(M_5)$.

Gerhard "Ask Me About System Design" Paseman, 2011.04.26