论文标题
$ \ mathbb {z} _n $几乎最佳$ \ ell $ -Covering
Almost optimum $\ell$-covering of $\mathbb{Z}_n$
论文作者
论文摘要
如果$ \ {ab \ pmod n | 0 \ leq a \ leq \ ell，b \ in b \} = \ mathbb {z} _n $。我们表明，所有$ n $ and $ \ ell $的$ \ mathbb {z} _n $的$ \ mathbb {z} _n $的$ \ mathbb {z} _n $的$ \ ell $ - 覆盖集的集合中存在$ \ ell $（\ frac {n} {\ ell} \ log n）$的$ \ mathbb {z} _n $，对于所有$ n $和$ \ ell $）我们还提供了示例，任何$ \ ell $ - 覆盖集必须具有$ω（\ frac {n} {\ ell} {\ ell} \ frac {\ log n} {\ log log \ log \ log n}）$。该证明采用了通过筛理论获得的相对基本函数的精致绑定，以及具有线性除数总和的大除数的存在。结果可用于简化模块集子集和算法。
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.
