Group-Invariant Certificates and Solvers for Diversity Selection in Combinatorial Libraries

Selection of massive, mutually non-redundant subset of highly scoring compounds from a combinatorial library is a standardized design in early stage drug discovery. It is usually solved by heuristics that return a ranking of capable candidates, however there is no quality guarantee. We formulate and introduce a method as maximum weighted independent set with a parameter soft redundancy penalty on a Cayley graph over the abelian group ℤ𝑛 𝑞 — where 𝑛 is the number of substitution positions and 𝑞 the number of substituents per position. The formulation rests on one explicit and falsifiable modelling commitment: pairwise redundancy should depend only on the group difference of two compounds. Under this commitment the interaction matrix is diagonalised by the group characters, its spectrum is available in closed form via Krawtchouk polynomials, and classical coding-theoretic bounds (Hoffman ratio, Delsarte linear programming) apply verbatim to the unweighted problem. Our contribution is an interface rather than new bound technology: we derive two valid upper bounds for the weighted objective, report the resulting a posteriori approximation-ratio lower bound 𝜌lower = 𝑓(𝑆)/𝑈 , and introduce a coset-decomposition family of certificates that recouples the weight term with the combinatorial structure. On synthetic libraries the spectral certificate yields a mean quality floor of 59.3%, the Delsarte version 67.7%, and the coset family a further 3.3 points. A gap decomposition against exhaustively computed optima shows that 77% of the residual gap is bound looseness rather than solver suboptimality, which redirects effort to the certificate side. On the solver side, group invariance permits column generation in 𝑂(𝑁 ) without ever materialising the 𝑁 ×𝑁 matrix, and evaluation of all 𝑁 translates of a linear code by a single group Fourier transform in 𝑂(𝑁 log 𝑁 ); exhaustive enumeration of cyclic codes combined with this step doubles the quality floor relative to a lookahead greedy at 𝑁 = 8192 while running four times faster. We report three negative results that we believe are useful to record: Pólya-based budget allocation is significantly worse than uniform allocation (𝑡 = −4.65), non-coordinate conjugacy classes of index-2 subgroups are systematically looser, and orbit-level selection never wins. All experiments use synthetic libraries; no chemical validation is claimed.