3 solved out of 16 shown

Is there a covering system all of whose moduli are odd?

Asked by Erdős and Selfridge (sometimes also with Schinzel). They also ask can there be such that no two of the moduli divide each other, or where all the moduli are odd and square-free?

Selfridge has shown (as reported in [Sc67]) that such a covering system exists if a covering system exists with moduli $n_1,\ldots,n_k$ such that no $n_i$ divides any other $n_j$.

Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST21] have proved that if the moduli are all squarefree then at least one must be even.

For any finite colouring of the integers is there a covering system all of whose moduli are monochromatic?

Conjectured by Erdős and Graham, who also ask about a density-type version: for example, is
\[\sum_{\substack{a\in A\\ a>N}}\frac{1}{a}\gg \log N\]
a sufficient condition for $A$ to contain the moduli of a covering system?
The answer (to both colouring and density versions) is no, due to the result of Hough [Ho15] on the minimum size of a modulus in a covering system - in particular one could colour all integers $<10^{18}$ different colours and all other integers a new colour.

$100

An $\epsilon$-almost covering system is a set of congruences $a_i\pmod{n_i}$ for distinct moduli $n_1<\ldots<n_k$ such that the density of those integers which satisfy none of them is $\leq \epsilon$. Is there a constant $C>1$ such that for every $\epsilon>0$ and $N\geq 1$ there is an $\epsilon$-almost covering system with $N\leq n_1$ and $n_k\leq Cn_1$?

By a simple averaging argument the set of moduli $[m_1,m_2]\cap \mathbb{N}$ has a choice of residue classes which form an $\epsilon(m_1,m_2)$-almost covering system with
\[\epsilon(m_1,m_2)=\prod_{m_1\leq m\leq m_2}(1-1/m).\]
A $0$-covering system is just a covering system, and so by Hough [Ho15] these only exist for $n_1<10^{18}$.
[NOTE: This is my best attempt at recovering problem 5 from [Er95], which doesn't make sense as written.]

Let $n_1<\cdots < n_r\leq N$ with associated $a_i\pmod{n_i}$ such that the congruence classes are disjoint (that is, every integer is $\equiv a_i\pmod{n_i}$ for at most one $1\leq i\leq r$). How large can $r$ be in terms of $N$?

Let $f(N)$ be the maximum possible $r$. Erdős and Stein conjectured that $f(N)=o(N)$, which was proved by Erdős and Szemerédi [ErSz68], who showed that, for every $\epsilon>0$,
\[\frac{N}{\exp((\log N)^{1/2+\epsilon})} \ll_\epsilon f(N) < \frac{N}{(\log N)^c}\]
for some $c>0$. Erdős believed the lower bound is closer to the truth.

Is there an integer $m$ with $(m,6)=1$ such that none of $2^k3^\ell m+1$ are prime, for any $k,\ell\geq 0$?

There are odd integers $m$ such that none of $2^km+1$ are prime, which arise from covering systems (i.e. one shows that there exists some $n$ such that $(2^km+1,n)>1$ for all $k\geq 1$). Erdős and Graham also ask whether there is such an $m$ where a covering system is not 'responsible'. The answer is probably no since otherwise this would imply there are infinitely many Fermat primes of the form $2^{2^t}+1$.

Do there exist $n$ with an associated covering system $a_d\pmod{d}$ on the divisors of $n$ (so that $d\mid n$ for all $d$ in the system), such that if
\[x\equiv a_d\pmod{d}\textrm{ and }x\equiv a_{d'}\pmod{d'}\]
then $(d,d')=1$? For a given $n$ what is the density of the integers which do not satisfy any of the congruences?

The density of such $n$ is zero. Erdős and Graham believed that no such $n$ exist.

If a finite system of $r$ congruences $\{ a_i\pmod{n_i} : 1\leq i\leq r\}$ covers $2^r$ consecutive integers then it covers all integers.

This is best possible as the system $2^{i-1}\pmod{2^i}$ shows. This was proved indepedently by Selfridge and Crittenden and Vanden Eynden [CrVE70].

Is there an infinite Lucas sequence $a_0,a_1,\ldots,$ where $(a_0,a_1)=1$ and $a_{n+2}=a_{n+1}+a_n$ for $n\geq 0$ such that all $a_k$ are composite, and yet no integer has a common factor with every term of the sequence?

Whether such a composite Lucas sequence even exists was open for a while, but using covering systems Graham [Gr64] showed that
\[a_0 = 1786772701928802632268715130455793\]
\[a_1 = 1059683225053915111058165141686995\]
generate such a sequence. This problem asks whether one can have a composite Lucas sequence without 'an underlying system of covering congruences responsible'.

Let $k\geq 3$. Is there a choice of congruence classes $a_p\pmod{p}$ for every prime $p$ such that all except finitely many integers can be written as $a_p+tp$ for some prime $p$ and integer $t\geq k$?

Even the case $k=3$ seems difficult. This may be true with the primes replaced by any set $A\subseteq \mathbb{N}$ such that
\[\lvert A\cap [1,N]\rvert \gg N/\log N\]
and
\[\sum_{\substack{n\in A\\ n\leq N}}\frac{1}{n} -\log\log N\to \infty\]
as $N\to \infty$.

For $k=1$ or $k=2$ any set $A$ such that $\sum_{n\in A}\frac{1}{n}=\infty$ has this property.

Let $n_1<n_2<\cdots $ be an infinite sequence of integers with associated $a_i\pmod{n_i}$, such that for some $\epsilon>0$ we have $n_k>(1+\epsilon)k\log k$ for all $k$. Then
\[\#\{ m<n_k : m\not\equiv a_i\pmod{n_i} \textrm{ for }1\leq i\leq k\}\neq o(k).\]

Erdős and Graham [ErGr80] suggest this 'may have to await improvements in current sieve methods' (of which there have been several since 1980).

Let $n_1<n_2<\cdots$ be an infinite sequence with associated congruence classes $a_i\pmod{n_i}$ such that the set of integers not satisfying any of the congruences $a_i\pmod{n_i}$ has density $0$.

Is it true that for every $\epsilon>0$ there exists some $k$ such that the density of integers not satisfying any of the congruences $a_i\pmod{n_i}$ for $1\leq i\leq k$ is less than $\epsilon$?

The latter condition is clearly sufficient, the problem is if it's also necessary. The assumption implies $\sum \frac{1}{n_i}=\infty$.