No label defined (Q4429166)

The authors study indivisibility polytopes, i.e., polytopes of binary \(n\)-strings that encode positive integers that are not divisible by \(p\). First they present a detailed analysis of a class of polytopes called ``clipped cubes''. This analysis includes a characterization of their facets, a characterization as the set of solutions of a totally dual integral system of linear inequalities, a characterization of adjacency of extreme points, a description of how to find short edge paths, a polynomial time algorithm for optimizing a linear function over a clipped cube, relationships with fractional generalized covering polyhedra and balanced matrices, the computation of their volume, and alternative models. Indivisibility polytopes comprise dyadic (\(p=2^k\)) and nondyadic cases. The latter are clipped cubes, the former are not. Linear inequality descriptions and characterizations of extreme point adjacency for dyadic and further results on nondyadic indivisibility polytopes are proved. An application of indivisibility polytopes in factoring large integers is outlined. Finally, properties of facet defining inequalities of divisibility polytopes, i.e., polytopes of binary \(n\)-strings that encode positive integers that are divisible by \(p\) are investigated. For the entire collection see [Zbl 1013.00014].