2
$\begingroup$

Help me please to solve the following problem.

There are $n$ arithmetic progressions of the form:

$$(2i+1)k + x_i,~~~~ i = 1,\ldots,n, k \geq 0$$

Initial integer terms $x_i \geq 0$ are varying.

The problem is to cover $m(n)$ - the maximum possible number of consecutive integers starting with $ 1 $ (the number is covered, if it belongs to at least one of these progressions).

For example, is it true, that: $$m(n) \approx \operatorname*{LCM}\limits_{i=1,\,\ldots\,,\,n}(\{2i+1\}) \text{?}$$

But it is so much and I am in search of the best solutions for this problem.

Numerical simulation shows something like this: $m(n) \approx Cn$

Update: Thank you for your answers! I did not imagine that it is so difficult problem.

Question: What is known about bounds of $m(n)$?

Is it proposition about upper bound whether true or not:

For fixed integer $k \geq 0$, and for all integers $x_i$ perform:

If $$u = \operatorname*{LCM}\limits_{i=1,\,\ldots\,,\,n}(\{(2i+1)k+x_i\})+1$$

Then number $u$ is not belong to any of $n$ arithmetic progressions of the form: $(2i+1)k+x_i,~~~i = 1,\ldots,n$ ?

It seems to me that it is obviously true.

$\endgroup$
  • $\begingroup$ The way you've written it, the a.p. starts with $2i+1+x_0 \ge 2i+2$, so you can't cover $1$, $2$ or $3$. Perhaps you meant $\ge$ rather than $>$? $\endgroup$ – Robert Israel Jul 27 '16 at 20:01
  • $\begingroup$ "Help me please" questions belong to mat stackexchange. $\endgroup$ – Franz Lemmermeyer Jul 28 '16 at 8:19
  • $\begingroup$ Considering the answers it got, this question seems to be both valid and beyond math stackexchange. Moreover, every question is a "help me please" question. I am no expert but nevertheless I doubt that this question should be on hold. $\endgroup$ – Helene Sigloch Jul 28 '16 at 14:19
  • $\begingroup$ Your "obviously true" statement is quite false. For example, take $n=2,k=6, x_1 = 1, x_2 = 3$. $u= \text{LCM}(3\cdot 6 + 1, 5\cdot6 + 3) +1 = 628 = 3 \cdot 209 + 1$. $\endgroup$ – Robert Israel Jul 28 '16 at 18:15
  • $\begingroup$ I understand that it's hopeless, but why it is not perform for fixed $k$: $\operatorname*{LCM}\limits_{i=1,\,\ldots\,,\,n}(\{(2i+1)k\}) + x^{*},~~~x^{*} \notin \{x_i\}_{i=1,\,\ldots,\,\,n},~~~x^{*} < k$? $\endgroup$ – Dmitry Pyatin Jul 28 '16 at 20:13
9
$\begingroup$

Not only is no upper bound known, it is unknown whether $m(n)$ can be infinite. It is a well-known open conjecture of Erdős and Selfridge that there does not exist an incongruent covering system whose moduli are all odd numbers $> 1$. A counterexample to that conjecture would be a finite set of a.p.'s with distinct odd differences that cover all of $\mathbb N$ (and would be worth \$900 from Selfridge).

EDIT: Using depth-first search for $n \le 10$ and Cplex after that, I find that the first few $m(n)$ are as follows:

$$ \matrix{n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16\cr m(n) & 1 & 2 & 4 & 6 & 10 & 13 & 17 & 22 & 30 & 38 & 45 & 53 & 63 & 74 & 83 & 96\cr} $$ The sequence doesn't appear to be in the OEIS. These data do support a low-order polynomial growth, maybe $\Theta(n^2)$.

EDIT: It is now in the OEIS as sequence A275489.

$\endgroup$
  • 1
    $\begingroup$ Or perhaps from John's estate. legacy.com/obituaries/daily-chronicle/… $\endgroup$ – Gerry Myerson Jul 27 '16 at 22:57
  • $\begingroup$ Thank you for running the experiment. Hagedorn has some tables in his 2009 paper which would give lengths just using prime moduli. Perhaps you could calculate some lower bounds for m(n) for larger n by "filling in" around some of those long intervals? My guess is (for n = 19 where he uses the 19 smallest odd primes to get a covered interval of length 86 =w(n)) that near there you can get m(34) to be 3*w(19) or better. Since Hagedorn has located the intervals covered by prime moduli, extending these should not take much time. Gerhard "Much Computer Time, That Is" Paseman, 2016.07.28. $\endgroup$ – Gerhard Paseman Jul 28 '16 at 20:13
  • $\begingroup$ I think having small composite moduli available changes the problem a lot, so the results for prime moduli are not going to be very useful in practice. $\endgroup$ – Robert Israel Jul 28 '16 at 20:33
  • $\begingroup$ @RobertIsrael, "EDIT: It is now in the OEIS as sequence A275489." -- good job!!! :) $\endgroup$ – Włodzimierz Holsztyński Aug 27 '16 at 4:12
2
$\begingroup$

If instead of common difference (2i+1) and varying x_i and hoping to cover 1 through m(n), you had common differences p_i for n distinct primes and all the x_i were 0, and you were just looking for the longest covered interval, you would bump into Jacobsthal's function (length of longest interval of consecutive nontotatives of m, in this case m being the product of the odd primes used).

Your problem is slightly more general, but you could use some existing data to inform your lower bound. I have a reading list and bibliography in an ArXiv print 1311.5944 : I recommend the papers by Hagedorn and (Hadju and Saradha), from which (just by choosing those progressions with prime arithmetic difference) you should achieve at least n log n growth.

Here is a quick way to get better than order n growth: Set x_i to 0 for those (2i+1) less than n which are prime. This leaves uncovered powers of 2, primes greater than n, and their products, using only n/log n of the progressions. Now use the remaining to cover the powers of two (so set x_i to 1, 2 , 4, ...) and as many primes and products larger than n until you run out. This will cover from 1 to about (n log n)/2 or better, because there aren't that many primes less than (n log n)/2 and the number does not get much bigger when you multiply those primes by small powers of 2. The theory predicts better than this, even when only prime difference arithmetic progressions are used.

Gerhard "All Publicity Is Good Publicity" Paseman, 2016.07.27.

$\endgroup$
  • $\begingroup$ I don't know what the upper bound is for this problem. I suspect that LCM is orders of magnitude too large though for m(n). My guess is that m(n) is bounded by a low degree polynomial in n. Gerhard "Most Guesses Aren't Very Bad" Paseman, 2016.07.27. $\endgroup$ – Gerhard Paseman Jul 27 '16 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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