DIMACS TR: 2005-29
Universal Subsets of Zn, Linear Integer Optimization, and Integer Factorization
Author: Zhivko Nedev
ABSTRACT
We consider two classes of sets in Zn . A non-empty subset U of Zn is universal (the first
class) if for all x \in U , and for all 0 < l ≤ n/2 at least one of x +/- l (mod n) lies in U . For
each universal U its complement, Zn\U, is from the second class and vice versa. We define
\beta(n) to be the minimum cardinality of an universal set modulo n. Completely characterizing
all sets in the second class we derive a formula for \beta(n).
We demonstrate that universal sets arise in the context of a two-player game that was
analyzed for the first time in [3] and has interesting connections to the prime factorization
of n. Finally we model our optimization problem, find \beta(n), as an integer linear program.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-29.pdf
DIMACS Home Page