2025/04/02 by Gijswijt, Dion, Polak, Sven
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2504.01932
Let Kq(n,r) denote the minimum size of a q-ary covering code of word length n and covering radius r. In other words, Kq(n,r) is the minimum size of a set of q-ary codewords of length n such that the Hamming balls of radius r around the codewords cover the Hamming space \0,…,q-1\n. The special case K3(n,1) is often referred to as the football pool problem, as it is equivalent to finding a set of forecasts on n football matches that is guaranteed to contain a forecast with at most one wrong outcome. In this paper, we build and expand upon the work of Gijswijt (2005), who introduced a semidefinite programming lower bound on Kq(n,r) via matrix cuts. We develop techniques that strengthen this bound, by introducing new semidefinite constraints inspired by Lasserre's hierarchy for 0-1 programs and symmetry reduction methods, and a more powerful objective function. The techniques lead to sharper lower bounds, setting new records across a broad range of values of q, n, and r.