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.


Your Answer

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

Browse other questions tagged or ask your own question.