Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2207.05017 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916280379899904 |
|---|---|
| author | Shi, Ke Xu, Chao |
| author_facet | Shi, Ke Xu, Chao |
| contents | A subset $B$ of the ring $\mathbb{Z}_n$ is referred to as a $\ell$-covering set if $\{ ab \pmod n | 0\leq a \leq \ell, b\in B\} = \mathbb{Z}_n$. We show that there exists a $\ell$-covering set of $\mathbb{Z}_n$ of size $O(\frac{n}{\ell}\log n)$ for all $n$ and $\ell$, and how to construct such a set. We also provide examples where any $\ell$-covering set must have a size of $Ω(\frac{n}{\ell}\frac{\log n}{\log \log n})$. The proof employs a refined bound for the relative totient function obtained through sieve theory and the existence of a large divisor with a linear divisor sum. The result can be used to simplify a modular subset sum algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_05017 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Almost optimum $\ell$-covering of $\mathbb{Z}_n$ Shi, Ke Xu, Chao Discrete Mathematics Combinatorics 05B40 G.2.1 A subset $B$ of the ring $\mathbb{Z}_n$ is referred to as a $\ell$-covering set if $\{ ab \pmod n | 0\leq a \leq \ell, b\in B\} = \mathbb{Z}_n$. We show that there exists a $\ell$-covering set of $\mathbb{Z}_n$ of size $O(\frac{n}{\ell}\log n)$ for all $n$ and $\ell$, and how to construct such a set. We also provide examples where any $\ell$-covering set must have a size of $Ω(\frac{n}{\ell}\frac{\log n}{\log \log n})$. The proof employs a refined bound for the relative totient function obtained through sieve theory and the existence of a large divisor with a linear divisor sum. The result can be used to simplify a modular subset sum algorithm. |
| title | Almost optimum $\ell$-covering of $\mathbb{Z}_n$ |
| topic | Discrete Mathematics Combinatorics 05B40 G.2.1 |
| url | https://arxiv.org/abs/2207.05017 |