Almost optimum \ell-covering of \mathbb{Z}_n

arXiv2207.05017MaRDI QIDQ6404637FDOQ6404637

Publication date: 11 July 2022

Abstract: A subset

B

of ring

m a t h b b Z_{n}

is called a

e l l

-covering set if

a b p m o d n m i d 0 l e q a l e q e l l, b i n B = m a t h b b Z_{n}

. We show there exists a

e l l

-covering set of

m a t h b b Z_{n}

of size

O (f r a c n e l l l o g n)

for all

n

and

e l l

, and how to construct such set. We also show examples where any

e l l

-covering set must have size

O m e g a (f r a c n e l l f r a c l o g n l o g l o g n)

. The proof uses a refined bound for relative totient function obtained through sieve theory, and existence of a large divisor with linear divisor sum.

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40)

This page was built for publication: Almost optimum $\ell$-covering of $\mathbb{Z}_n$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6404637)