Optimizing alphabet reduction pairs of arrays

In [1], we introduced a family of combinatorial designs, which we call "alphabet reduction pairs of arrays", ARPAs for short. These designs depend on three integer parameters q, p ≤ q, k≤ p: q is the size of the symbol set \0, 1 ,…, q -1\ in which the coefficients of the arrays take their values; p is the maximum number of distinct symbols allowed in a row of the second array of the pair; k is the larger integer for which the two arrays of the pair coincide -- up to the order of their rows -- on any k-ary subset of their columns. The first array must contain at least one occurrence of the word 0\ 1\ …\ q -1. Intuitively, the idea is to cover "as many as possible" occurrences of this word of q symbols with "as few as possible" words of at most p different symbols. These designs are related to the approximability of "Constraint Satisfaction Problems with bounded constraint arity", known as $k\,$CSPs. In this context, we are particularly interested in ARPAs in which the frequency of the word 0\ 1\ …\ q -1 is maximal. We introduce a seemingly simpler family of combinatorial designs as "Cover pairs of arrays" (CPAs). The arrays of a CPA take Boolean coefficients, and must still coincide on any k-ary subset of their columns. The purpose is, as it were, to cover "as many as possible" occurrences of the word of q ones using "as few as possible" q-length Boolean words of weight at most p. We show that, when it comes to maximizing the frequency of the words 0\ 1\ …\ q -1 in ARPAs and 1\ 1\ …\ 1 in CPAs, ARPAs and CPAs are equivalent. We prove the optimality of the ARPAs given in [1] for the case $p =k$. In addition, we provide optimal ARPAs for the cases $k =1$ and $k =2$. We emphasize the fact that both families of combinatorial designs are related to the approximability of $k\,$CSPs.