DIMACS TR: 2005-29

Universal Subsets of Zn, Linear Integer Optimization, and Integer Factorization

Author: Zhivko Nedev


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