This is the last question in the series of questions about the ability to cover $\mathbb Z/n\mathbb Z$ with arithmetic progressions (see previous discussions here and here).

The problem is as follows. Let $n \geq 13$ be a fixed positive integer and let $t_0$ be an integer such that $1 \leq t_0 \leq n / 2$. Let $A$ be a subset of the group of units $(\mathbb Z/n \mathbb Z)^*$ with the following three properties:

(1) $1 \in A$;

(2) for every $a_1, a_2 \in A$ it is the case that $a_1 \not \equiv ta_2 \pmod n$ for all $t \in \{2, 3, \ldots, t_0\}$;

(3) for every $m \in (\mathbb Z/n\mathbb Z)^* \setminus A$, there exist $t \in \{2, 3, \ldots, t_0\}$ and $a \in A$ such that either $m \equiv ta \pmod n$ or $tm \equiv a \pmod n$ hold.

In $(\mathbb Z/n\mathbb Z)^*$, there might exist several subsets with such properties. I am interested in a non-trivial upper bound on their cardinality, which depends solely on $n$ and $t_0$. In my case, $t_0 = \varphi(n)/2 - 2$, but I am curious to see any kind of analysis for $t_0$ "not too far away" from $\varphi(n)/2$.

An alternative formulation for this problem would be the following: for a subset $B$ of $(\mathbb Z/n\mathbb Z)^*$, let $B\cdot B^{-1}$ denote the set

$B\cdot B^{-1} := \{b_1b_2^{-1} \colon b_1, b_2 \in B\}$.

Now consider a subset $B$ of $(\mathbb Z/n\mathbb Z)^*$ with the property

(+) $B\cdot B^{-1} \subseteq \{2, 3, \ldots, t_0\}^c,$

where $X^c := (\mathbb Z/n\mathbb Z)^* \setminus X$. Once again, there are many subsets with such a property (for example, $B = \{1\}$ works), and one can convince yourself that the subsets satisfying properties (1), (2) and (3) also satisfy property (+), and in fact are maximal with respect to this property, in the sense that the addition of one more element into the set would force it to violate property (+). Once again, I am interested in a non-trivial upper bound on the cardinality of all the subsets $B$ satisfying property (+), which depends only on $n$ and $t_0$.

I ran some computations and they are pretty convincing that, when $t_0 = \varphi(n)/2 - 2$, the result should be $o(n)$. In fact, I believe it should be $O((\log n)^k)$ for some $k$. Let me give several examples when $n$ is prime:

1. For $n = 101$ and $t = 48$, one can take

$A = \{1,50,52,54,58,68,99\}, \,\,\, |A| = 7;$

2. For $n = 1009$ and $t = 502$, one can take

$A = \{1, 503, 510, 516, 545, 623, 764, 788, 860\}, |A| = 9;$

3. For $n = 10007$ and $t = 5001$, one can take

$A = \{1, 5003, 5005, 5016, 5030, 5035, 5206, 5258, 5484, 6770, 7639\}, \,\,\, |A| = 11;$

4. For $n = 100003$ and $t = 49999$, one can take

$A = \{1, 50000, 50007, 50040, 50054, 50172, 50399, 50409, 51052, 51072, 55407, 55954, 68071, 76026, 76434\}, \,\,\, |A| = 15.$

I would be thankful for any suggestions on how to approach this problem.

This is the last question in the series of questions about the ability to cover $\mathbb Z/n\mathbb Z$ with arithmetic progressions (see previous discussions here and here).

The problem is as follows. Let $n \geq 13$ be a fixed positive integer and let $t_0$ be an integer such that $1 \leq t_0 \leq n / 2$. Let $A$ be a subset of the group of units $(\mathbb Z/n \mathbb Z)^*$ with the following three properties:

(1) $1 \in A$;

(2) for every $a_1, a_2 \in A$ it is the case that $a_1 \not \equiv ta_2 \pmod n$ for all $t \in \{2, 3, \ldots, t_0\}$;

(3) for every $m \in (\mathbb Z/n\mathbb Z)^* \setminus A$, there exist $t \in \{2, 3, \ldots, t_0\}$ and $a \in A$ such that either $m \equiv ta \pmod n$ or $tm \equiv a \pmod n$ hold.

In $(\mathbb Z/n\mathbb Z)^*$, there might exist several subsets with such properties. I am interested in a non-trivial upper bound on their cardinality, which depends solely on $n$ and $t_0$. In my case, $t_0 = \varphi(n)/2 - 2$, but I am curious to see any kind of analysis for $t_0$ "not too far away" from $\varphi(n)/2$.

An alternative formulation for this problem would be the following: for a subset $B$ of $(\mathbb Z/n\mathbb Z)^*$, let $B\cdot B^{-1}$ denote the set

$B\cdot B^{-1} := \{b_1b_2^{-1} \colon b_1, b_2 \in B\}$.

Now consider a subset $B$ of $(\mathbb Z/n\mathbb Z)^*$ with the property

(+) $B\cdot B^{-1} \subseteq \{2, 3, \ldots, t_0\}^c,$

where $X^c := (\mathbb Z/n\mathbb Z)^* \setminus X$. Once again, there are many subsets with such a property (for example, $B = \{1\}$ works), and one can convince yourself that the subsets satisfying properties (1), (2) and (3) also satisfy property (+), and in fact are maximal with respect to this property, in the sense that the addition of one more element into the set would force it to violate property (+). Once again, I am interested in a non-trivial upper bound on the cardinality of all the subsets $B$ satisfying property (+), which depends only on $n$ and $t_0$.

I ran some computations and they are pretty convincing that, when $t_0 = \varphi(n)/2 - 2$, the result should be $o(n)$. In fact, I believe it should be $O((\log n)^k)$ for some $k$. Let me give several examples when $n$ is prime:

1. For $n = 101$ and $t = 48$, one can take

$A = \{1,50,52,54,58,68,99\}, \,\,\, |A| = 7;$

2. For $n = 1009$ and $t = 502$, one can take

$A = \{1, 503, 510, 516, 545, 623, 764, 788, 860\}, |A| = 9;$

3. For $n = 10007$ and $t = 5001$, one can take

$A = \{1, 5003, 5005, 5016, 5030, 5035, 5206, 5258, 5484, 6770, 7639\}, \,\,\, |A| = 11;$

4. For $n = 100003$ and $t = 49999$, one can take

$A = \{1, 50000, 50007, 50040, 50054, 50172, 50399, 50409, 51052, 51072, 55407, 55954, 68071, 76026, 76434\}, \,\,\, |A| = 15.$

I would be thankful for any suggestions on how to approach this problem.

This is the last question in the series of questions about the ability to cover $\mathbb Z/n\mathbb Z$ with arithmetic progressions (see previous discussions here and here).

The problem is as follows. Let $n \geq 13$ be a fixed positive integer and let $t_0$ be an integer such that $1 \leq t_0 \leq n / 2$. Let $A$ be a subset of the group of units $(\mathbb Z/n \mathbb Z)^*$ with the following three properties:

(1) $1 \in A$;

(2) for every $a_1, a_2 \in A$ it is the case that $a_1 \not \equiv ta_2 \pmod n$ for all $t \in \{2, 3, \ldots, t_0\}$;

(3) for every $m \in (\mathbb Z/n\mathbb Z)^* \setminus A$, there exist $t \in \{2, 3, \ldots, t_0\}$ and $a \in A$ such that either $m \equiv ta \pmod n$ or $tm \equiv a \pmod n$ hold.

In $(\mathbb Z/n\mathbb Z)^*$, there might exist several subsets with such properties. I am interested in a non-trivial upper bound on their cardinality, which depends solely on $n$ and $t_0$. In my case, $t_0 = \varphi(n)/2 - 2$, but I am curious to see any kind of analysis for $t_0$ "not too far away" from $\varphi(n)/2$.

An alternative formulation for this problem would be the following: for a subset $B$ of $(\mathbb Z/n\mathbb Z)^*$, let $B\cdot B^{-1}$ denote the set

$B\cdot B^{-1} := \{b_1b_2^{-1} \colon b_1, b_2 \in B\}$.

Now consider a subset $B$ of $(\mathbb Z/n\mathbb Z)^*$ with the property

(+) $B\cdot B^{-1} \subseteq \{2, 3, \ldots, t_0\}^c,$

where $X^c := (\mathbb Z/n\mathbb Z)^* \setminus X$. Once again, there are many subsets with such a property (for example, $B = \{1\}$ works), and one can convince yourself that the subsets satisfying properties (1), (2) and (3) also satisfy property (+), and in fact are maximal in cardinality with respect to this property. Once again, I am interested in a non-trivial upper bound on the cardinality of all the sets $B$ satisfying property (+), which depends only on $n$ and $t_0$.

I ran some computations and they are pretty convincing that, when $t_0 = \varphi(n)/2 - 2$, the result should be $o(n)$. In fact, I believe it should be $O((\log n)^k)$ for some $k$. Let me give several examples when $n$ is prime:

1. For $n = 101$ and $t = 48$, one can take

$A = \{1,50,52,54,58,68,99\}, \,\,\, |A| = 7;$

2. For $n = 1009$ and $t = 502$, one can take

$A = \{1, 503, 510, 516, 545, 623, 764, 788, 860\}, |A| = 9;$

3. For $n = 10007$ and $t = 5001$, one can take

$A = \{1, 5003, 5005, 5016, 5030, 5035, 5206, 5258, 5484, 6770, 7639\}, \,\,\, |A| = 11;$

4. For $n = 100003$ and $t = 49999$, one can take

$A = \{1, 50000, 50007, 50040, 50054, 50172, 50399, 50409, 51052, 51072, 55407, 55954, 68071, 76026, 76434\}, \,\,\, |A| = 15.$

I would be thankful for any suggestions on how to approach this problem.

This is the last question in the series of questions about the ability to cover $\mathbb Z/n\mathbb Z$ with arithmetic progressions (see previous discussions here and here).

The problem is as follows. Let $n \geq 13$ be a fixed positive integer and let $t_0$ be an integer such that $1 \leq t_0 \leq n / 2$. Let $A$ be a subset of the group of units $(\mathbb Z/n \mathbb Z)^*$ with the following three properties:

(1) $1 \in A$;

(2) for every $a_1, a_2 \in A$ it is the case that $a_1 \not \equiv ta_2 \pmod n$ for all $t \in \{2, 3, \ldots, t_0\}$;

(3) for every $m \in (\mathbb Z/n\mathbb Z)^* \setminus A$, there exist $t \in \{2, 3, \ldots, t_0\}$ and $a \in A$ such that either $m \equiv ta \pmod n$ or $tm \equiv a \pmod n$ hold.

In $(\mathbb Z/n\mathbb Z)^*$, there might exist several subsets with such properties. I am interested in a non-trivial upper bound on their cardinality, which depends solely on $n$ and $t_0$. In my case, $t_0 = \varphi(n)/2 - 2$, but I am curious to see any kind of analysis for $t_0$ "not too far away" from $\varphi(n)/2$.

An alternative formulation for this problem would be the following: for a subset $B$ of $(\mathbb Z/n\mathbb Z)^*$, let $B\cdot B^{-1}$ denote the set

$B\cdot B^{-1} := \{b_1b_2^{-1} \colon b_1, b_2 \in B\}$.

Now consider a subset $B$ of $(\mathbb Z/n\mathbb Z)^*$ with the property

(+) $B\cdot B^{-1} \subseteq \{2, 3, \ldots, t_0\}^c,$

where $X^c := (\mathbb Z/n\mathbb Z)^* \setminus X$. Once again, there are many subsets with such a property (for example, $B = \{1\}$ works), and one can convince yourself that the subsets satisfying properties (1), (2) and (3) also satisfy property (+), and in fact are maximal with respect to this property, in the sense that the addition of one more element into the set would force it to violate property (+). Once again, I am interested in a non-trivial upper bound on the cardinality of all the subsets $B$ satisfying property (+), which depends only on $n$ and $t_0$.

I ran some computations and they are pretty convincing that, when $t_0 = \varphi(n)/2 - 2$, the result should be $o(n)$. In fact, I believe it should be $O((\log n)^k)$ for some $k$. Let me give several examples when $n$ is prime:

1. For $n = 101$ and $t = 48$, one can take

$A = \{1,50,52,54,58,68,99\}, \,\,\, |A| = 7;$

2. For $n = 1009$ and $t = 502$, one can take

$A = \{1, 503, 510, 516, 545, 623, 764, 788, 860\}, |A| = 9;$

3. For $n = 10007$ and $t = 5001$, one can take

$A = \{1, 5003, 5005, 5016, 5030, 5035, 5206, 5258, 5484, 6770, 7639\}, \,\,\, |A| = 11;$

4. For $n = 100003$ and $t = 49999$, one can take

$A = \{1, 50000, 50007, 50040, 50054, 50172, 50399, 50409, 51052, 51072, 55407, 55954, 68071, 76026, 76434\}, \,\,\, |A| = 15.$

I would be thankful for any suggestions on how to approach this problem.