Infinite play with tape, or covering the integers with prime arithmetic progressions

Question

It is possible that a more technical version of this question has been asked and answered in the literature. If so, then a reference is much appreciated. I will phrase it in terms of colored tapes placed on a number line.

I have an unlimited supply of transparent but partially colored arithmetic progression tapes, one for each prime number. Thus, the tape for 3 looks a lot like the tape for 29, except instead of having a blue square at every third inch, I have a yellow square at every 29th inch; the tape is clear otherwise. I am going to make several arrangements of tape. My first arrangement produces a color coding of integers similar to indicating divisibility, except I perversely decide to line up all the colors at 1. This leaves positions 0 and 2 with no colors, and every other position gets finitely many colors (88 gets only blue and yellow).

What other arrangements can I make? I can pick any nonempty set of integers and arrange that each get some of a partition of colors, although the integer may get more colors than I assigned. I can sometimes arrange to leave a square uncolored, regardless of how the primes are partitioned. That is not the main question though.

Main question: can I arrange that every integer gets only finitely many colors?

An amusing fact (courtesy of the Chinese Remainder Theorem) is that, with a finite number of such tapes and modulo translation, every such arrangement looks the same. Thus I do not expect a finite upper bound to the number of colors received by an integer.

Although I would appreciate a specific example, I am also interested in knowing how weak a subtheory of ZF or PA is needed to prove existence of such an arrangement. (I harbor a suspicion that PRA will resolve it negatively if it resolves at all.) Specific references to the literature on covering congruences are welcome (as are alternate search terms), but for this problem I am considering prime moduli only.

Gerhard "Your Responses Are Being Recorded" Paseman, 2014.03.14

Answer 1

There is a map $\varphi: \mathbb{Z}\rightarrow \prod \mathbb{F}_p$, given by reduction mod $p$ in each coordinate. If you place the tapes centered at $0$ (to account for divisibility), you can read off the number of colors $n\in \mathbb{Z}$ gets by counting the zero-entries of $\varphi(n)$.

Now in your situation, you shift every tape by a certain amount. This accounts for the choice of an element in $\mathbb{F}_p$ for each $p$, or an element $\sigma\in \prod \mathbb{F}_p$.

In your setting, the number of colors associated to $n\in\mathbb{Z}$ will be given by the number of coordinates in which $\varphi(n)$ agrees with $\sigma$.

So we are left with the question of constructing $\sigma\in \prod \mathbb{F}_p$, which agrees with each of the $\varphi(n)$ only on finitely many digits.

However, this is easy: We can even do an explicit example. Just choose the $p$-th coordinate of $\sigma$ (for example) to be $\lfloor{p/2}\rfloor$. This way $\phi(n)$ will differ from $\sigma$ in the $p$-th coordinate for all $p$ with $p > 2|n|+1$.

The idea is that you place each tape such that $0$ is approximately in the middle of two successive colored spots, this way you get similar behaviour to the $\mathbb{N}$-situation.

Just for the sake of completeness, this explicit example obviously does not rely on any abstract existence arguments, so I guess this proof holds in any reasonable theory.

Answer 2

I like Achim Krause's answer, but I prefer a simpler explanation. Here goes:

Place the 2 tape to cover zero, and for $k \gt 0$ place the tape for the $2k$th prime $p_{2k}$ to cover the $k$th positive odd number $(2k-1)$, and place the tape for $p_{2k+1}$ to cover the corresponding negative odd number $(1-2k)$. As $p_n \geq 2n-1$, any number in $[-n,n]$ will have colors only from tapes for $p_k$ with $k \leq n + 2$. So all numbers are colored with only finitely many colors. (That they each get a color is left to the reader.)

This should make apparent ways to extend the result in weak subsystems of arithmetic for sequences $q_n$ replacing $p_n$ that are definable in such a system and are provably increasing in that system.

Gerhard "Looking To Make Things Simpler" Paseman, 2014.04.09

Answer 3

I became surprised at an insight which occurred after reviewing a similar covering question by asterios gantzounis. The surprise was why I did not see this before today.

In the standard coloring (using divisibility) of the integers by the primes, every number gets covered by finitely many primes except a single number, namely zero. So let's remove zero, and remove all the even numbers, and push the rest of the squares together. Now the problem square is removed along with exactly one tape, namely the tape for two. What is left is a coloring by divisibility of the odd numbers by odd primes, which is (isomorphic to) one tape short of a solution to the original problem. So just add the tape for two. Done.

Gerhard "Interesting Divide And Conquer Technique" Paseman, 2018.01.02.