residue classes of primes, covering intervals and bounds on the different ways - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T18:37:18Z http://mathoverflow.net/feeds/question/57564 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/57564/residue-classes-of-primes-covering-intervals-and-bounds-on-the-different-ways residue classes of primes, covering intervals and bounds on the different ways asterios gantzounis 2011-03-06T13:18:21Z 2011-07-29T07:14:45Z <p>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$.</p> <p>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]$.)</p> <p>ADDED:</p> <p>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?</p> http://mathoverflow.net/questions/57564/residue-classes-of-primes-covering-intervals-and-bounds-on-the-different-ways/57603#57603 Answer by Will Jagy for residue classes of primes, covering intervals and bounds on the different ways Will Jagy 2011-03-06T21:33:20Z 2011-03-07T01:13:27Z <p>I did some computer programming to check plausibility. In future I request that you do this step yourself.</p> <p>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. </p> <p>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.$</p> <p>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. </p> <pre><code> 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 </code></pre> <p>The bound of 10,000,000 is not on primes, it is on the output, such as 691565 &lt; 10,000,000.</p> <pre><code> 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. </code></pre> http://mathoverflow.net/questions/57564/residue-classes-of-primes-covering-intervals-and-bounds-on-the-different-ways/57624#57624 Answer by Aaron Meyerowitz for residue classes of primes, covering intervals and bounds on the different ways Aaron Meyerowitz 2011-03-07T01:07:15Z 2011-03-16T08:35:30Z <p>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?</p> <p>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}$. </p> <p>If it can be done at all then the number of ways to do it (provided that we <em>do</em> 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. </p> <p>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.</p> <p>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.</p> <p>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 <a href="http://en.wikipedia.org/wiki/The_sum_of_the_reciprocals_of_the_primes_diverges" rel="nofollow">this estimate</a> $$\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). </p> http://mathoverflow.net/questions/57564/residue-classes-of-primes-covering-intervals-and-bounds-on-the-different-ways/57644#57644 Answer by Gerhard Paseman for residue classes of primes, covering intervals and bounds on the different ways Gerhard Paseman 2011-03-07T08:36:34Z 2011-03-07T08:36:34Z <p>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.</p> <p>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.</p> <p>Gerhard "Ask Me About Coprime Intervals" Paseman, 2011.03.07 </p> http://mathoverflow.net/questions/57564/residue-classes-of-primes-covering-intervals-and-bounds-on-the-different-ways/58627#58627 Answer by Gerhard Paseman for residue classes of primes, covering intervals and bounds on the different ways Gerhard Paseman 2011-03-16T10:23:36Z 2011-03-16T10:23:36Z <p>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 &lt; 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 &lt; 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 &lt; j(P_N/P_n)&lt;=85$ for $n=4$ by an undisclosed but elementary method. I also suggested that $J(n)$ is false for all $n > 4$.</p> <p>A method of showing for $n &lt; 5$ that $j(P_N/P_n) &lt; P_n$ comes from the fact that $\sum_{n &lt; i \leq N} 1/p_i &lt; 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$.</p> <p>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$.</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>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) &lt; 83$.</p> <p>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 &lt; 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.</p> <p>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.</p> <p>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$.</p> <p>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$.</p> <p>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 &lt; s} p_{N-d}$ where $s$ is small, conjecturally $s \in O(\log(\log(\log(N))))$.</p> <p>Gerhard "Will Guess For Bounty Points" Paseman, 2011.03.16</p> http://mathoverflow.net/questions/57564/residue-classes-of-primes-covering-intervals-and-bounds-on-the-different-ways/63097#63097 Answer by Gerhard Paseman for residue classes of primes, covering intervals and bounds on the different ways Gerhard Paseman 2011-04-27T01:12:12Z 2011-04-27T01:12:12Z <p>Let $M_4 = \prod_{p \text{ prime }, 10 &lt; p &lt; 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 &lt; j(M_4) &lt; 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.</p> <p>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)$. </p> <p>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$.</p> <p>The program also found many other partial covers. I have not checked them to see if any cover even more elements.</p> <p>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.</p> <p>I was able by hand to come up with a proof that $[0, 80]$ could not be covered, giving $j(M_4) &lt; 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) &lt; 80$. I invite verification of the assertion $j(M_4)=79$.</p> <p>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 &lt; j(M_5)$.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2011.04.26</p>