אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

For a set M = {−µ, −µ + 1, . . . , λ} \ {0} with non-negative integers λ, µ < q not both 0, a subset S of the residue class ring Zq modulo an integer q ? 1 is called a (λ, µ; q)-covering set if MS = {ms mod q : m ∈ M, s ∈ S} = Zq .

Small covering sets play an important role in codes correcting limited-magnitude errors.

We use some number theoretic methods to 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 of 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 we show 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. (Joint work with Zhixiong Chen and Arne Winterhof).