## Abstract

For a set M = {-μ,-μ + 1, . . . , λ} \ {0} with nonnegative integers λ,μ < q not both 0, a subset S of the residue class ring ℤ_{q} modulo an integer q ≥ 1 is called a (λ,μ; q)-covering set if MS = {ms mod q : m ε M, s ε S} = ℤ_{q} . Small covering sets play an important role in codes correcting limited-magnitude errors. We give an explicit construction of a (λ,μ; q)-covering set S, which is of the size q1+o(1) max{λ,μ} ^{-1/2} for almost all integers q ≥ 1 and optimal order of magnitude (that is up to a multiplicative constant) p max{λ,μ}^{-1} if q = p is prime. Furthermore, using a bound on the fourth moment of character sums of Cochrane and Shi that there is a (λ,μ; q)-covering set of size at most q1+o(1) max{λ,μ}^{-1/2} for any integer q ≥ 1, however the proof of this bound is not constructive.

Original language | English |
---|---|

Pages (from-to) | 5315-5321 |

Number of pages | 7 |

Journal | IEEE Transactions on Information Theory |

Volume | 60 |

Issue number | 9 |

DOIs | |

Publication status | Published - Sept 2014 |

Externally published | Yes |

## Keywords

- character sums.
- Covering sets
- limited-magnitude errors
- residue class rings