4
$\begingroup$

For a quick exposition of how I arrived at this question: I found the Wikipedia page on covering sets and through some experiments on my own (fixing the constant at the end, the factor $k$ itself etc.), I wanted to find numbers fitting in a cover given a certain set of primes and their "periods". Explaining what all of this means would take a while and would be outside the scope of this question, so I keep it short.

What I am trying to achieve is: Given a set of natural numbers $\{a_1,\ldots,a_n\} \in \mathbb{N}^n$ with the property $\sum\limits_{k = 1}^{n} \frac{1}{a_i} = 1$ (an "egyptian unit fraction", see here and here), can we find $n$ arithmetic progressions of the form $a_i k + c_i$ for $i \in \{1,\ldots,n\}$ such that for $P := \text{ lcm}(a_1,\ldots,a_n)$ $$a_i k + c_i \mod P$$ for varying $k$ (and taken over every $i$) will eventually cover every residue class?

A condition that seems to work out at least for a small number of terms $n$ is that $\gcd(a_i,a_j) > 1$ for any $i,j$ and that the $\text{lcm}$ of two terms with $\gcd$ equal to one would need to be strictly bigger than $P$ (but I am not sure if the latter can ever be attained someway). By design of the problem, we also never can have any overlap between the residue classes of different sequences, or else some residue class will never be attained by one of these sequences.

Visually, a list and an example seems useful for this kind of question: Take $\{2,4,8,8\}$, then $\color{blue}{2k+1},\color{red}{4k+2}$, $\color{purple}{8k}$ and $\color{green}{8k+4}$ $$\color{purple}0,\color{blue}1,\color{red}2,\color{blue}3,\color{green}4,\color{blue}5,\color{red}6,\color{blue}7$$ cover $\mathbb{Z}_{8}$ and $\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{8} = 1$, so we have a set with four terms with the properties I want. It works with other sets as well like $\{2,4,4\},\{3,3,3\}$ and $\{3,3,6,6\}$, all giving a nice set of numbers I can subsequently treat with the mentioned covering sets above. The crux is that this does not work with every such "egyptian decomposition" like $\{2,3,9,18\}$ (try it, there will always be at least one overlap) and $\{2,3,6,12\}$ (just coprimality doesn't cut it). So my question(s) are these:

  1. Is there any sufficient criterion which can tell me when one of these egyptian unit fractions is valid for a "covering set"?
  2. Do there exist any references in the OEIS, MathWorld, books in general etc., especially on the number of these sets for any fixed size $n$?

Thank you for listening to me waffle about elementary number theory, have a good day!

EDIT: I have realized that the statements "non-overlapping arithmetic sequences" and "has egyptian fraction representation" can easily be seen to be equivalent. Oh well, I still think the egyptian fraction way captures the idea more succinctly. I have also noticed that sets gained from splitting up terms in $\frac{1}{k}+\ldots+\frac{1}{k} = k \frac{1}{k} = 1$ into sums of the form $\frac{1}{lk} + \ldots + \frac{1}{lk} = l\frac{1}{lk} = \frac{1}{k}$ with $l \in \mathbb{N}$ will necessarily have such a covering. Visually speaking, we are "refining" an arithmetic progression with factor $k$ into $l$ subprogressions and arranging these offset from one another in such a way that they resemble the original $k$-period progression.

EDIT2: Having spent the evening yesterday trying to construct sets with the wanted properties, I have arrived at $$\begin{array}{c|c|c|c|c|c|c|c|c|c} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \cdots \\ \hline \#\text{gen. coverings} & 1 & 1 & 2 & 4 & 10 & 23 & 60 & 153 & 405 & 1076 & 2909 & 7909 \end{array}$$ for a fixed set size $n$. That this simple sequence is not in the OEIS yet is sticking up some huge flags for me (though it is relatively close to the "meandric numbers"). Any ideas on what this sequence could be represented by? The number of sets up to size $n$ is given by $$\begin{array}{c|c|c|c|c|c|c|c|c|c} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \cdots \\ \hline \#\text{gen. coverings} & 1 & 2 & 4 & 8 & 18 & 41 & 101 & 254 & 659 & 1735 & 4644 & 12551 \end{array}$$ -- also not in the OEIS (though relatively close to A057151).

$\endgroup$
5
  • 1
    $\begingroup$ A necessary criterion is that the set doesn't contain any pair of coprime integer, but it is not sufficient, considering $\{2,4,6,12\}$ $\endgroup$
    – aerile
    Commented Jun 10, 2022 at 23:14
  • $\begingroup$ Yes exactly, I just forgot to include it in the post. Thank you. The more I think about it, the sets that I speak about in my edit seem to be the only ones that I find, so they very well might characterise all such sets. $\endgroup$
    – TheOutZ
    Commented Jun 11, 2022 at 7:07
  • $\begingroup$ A good measure up to now has been that for every two numbers $i,j$ in such a set with $i > j$ we have $\frac{i}{j} \in \mathbb{N}$, but since I constructed all examples with the method mentioned in the edit (having this property by design), this might not exhaust all possibilities. $\endgroup$
    – TheOutZ
    Commented Jun 11, 2022 at 7:17
  • 1
    $\begingroup$ That criterion seems to be too strong. $\{3,6,6,9,9,9\}$ satisfies the covering property without that criterion. $\endgroup$
    – aerile
    Commented Jun 11, 2022 at 8:43
  • $\begingroup$ Uh. Yeah. I even have that in my handwritten list, don't know why I said that. You are right of course. $\endgroup$
    – TheOutZ
    Commented Jun 11, 2022 at 8:45

1 Answer 1

2
$\begingroup$

Let $d=gcd(a_1,..,a_n)$. Then, each residue class mod $d$ is covered by some subset. Let the subset $S_i\ (i=0,..,d-1)$ cover $P/d$ integers congruent to $i \pmod d$. Then, dividing all elements of $S_i$ by $d$ provides new set satisfying the covering property. From such consideration, I also concluded that the set satisfying the covering property can be obtained by repeating refinement.

From this perspective, I found one description using tree: The $n$-th term of the sequence is the number of plane trees with (unordered) $n$ leaves such that "for each node, the number of children of children has no common divisor".

(I mean: when the node $A$ has $d$ children $B_1,..,B_d$ and $B_k$ has $b_k$ children, then $gcd(b_1,..,b_d)=1$.)

I demonstrated the correspondence for $n=6$ by the picture.

I manually enumerated for $n\leq 7$ and got same the result, which was not registered in the OEIS. I think this sequence is interesting enough to be registered in the OEIS.

Edit: The upper bound of (see comment) the sequence can be described by following: $a_1 = 1$, $a_n = \sum a_{i_1}..a_{i_k}$, where $1\leq i_1\leq..\leq i_k<n$, $\sum_{j=1}^{k} i_j=n$, and $gcd(i_1,..,i_k)=1$.
(For example, $a_5 = a_1a_1a_1a_1a_1+a_1a_1a_1a_2+a_1a_1a_3+a_1a_4+a_2a_3$)

enter image description here

$\endgroup$
2
  • 1
    $\begingroup$ Your recursion is not correct, it only gives an upper bound, since some covering sets will be duplicated. For example, $a_2a_3$ counts both [4,4,6,6,6] and [4,4,4,8,8], but the latter is also counted by $a_1a_1a_1a_2$. $\endgroup$
    – Cecilia
    Commented Jun 12, 2022 at 20:25
  • 1
    $\begingroup$ @Richard You are right. I edited. $\endgroup$
    – aerile
    Commented Jun 12, 2022 at 22:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .