A putative intersection array that does not satisfy one of the conditions in Lemmas 7.7, 7.8(ii), 7.4(congruence to -n), 7.6(i) below for some n, does not satisfy it for any n. Such an array is unfeasible and we do not include it in the table (with an exception of Lemma 7.8(ii), which kills a relatively small number of arrays). All other arrays are included in the small-value tables, grouped by q and covering radius (q=2, ρ=1,2,3,4,5,6,7,8; q=3, ρ=1,2,3,4,5), provided the values are small. Other necessary conditions can give a nontrivial lower bound on n (the trivial one is maxi(Si,i-1+Si,i+1)).
Considering the neighborhoods of two adjacent vertices at distance i-1 and i from C, it is not difficult to establish the following.
Lemma 7.1. If there exists a {b0,...,bρ-1;c1,...,cρ}-CR code C in H(n,q), then bi-1>bi and ci<ci+1, i=1,...,ρ-1.
The cardinality of each cell must be integer. The cardinalities can be calculated from the quotient matrix. For H(n,q): if the proportion between the cell cardinalities is s0:s1:...:sρ, then (s0+s1+...+sρ)/GCD(s0,s1,...,sρ) must divide a power of q.
Moreover, each cell of an equitable partition of H(n,q) is an orthogonal array of strength t, where (q-1)n-q(t+1) is the smallest eigenvalue of the quotient matrix. Therefore, the cardinality of each cell must be a multiple of qt. This gives an effective lower bound on n for some intersection arrays for q>2.
An equitable partition with quotient matrix S of a distance-regular graph G is an equitable partition of the corresponding distance-w graph for every w up to the diameter of G. For H(n,q), the corresponding quotient matrix is Sw=Kw(K1-1(S)), where Kw=Kw;n,q is the Krawtchouk polynomial of degree w. This test is stronger than the integrity of the cardinalities and also "monotonic" in n. That is, if the matrix Sw is not integer and i is minimum with this property, then for the next dimension the corresponding matrices are calculated as Tw=Sw+(q-1)Sw-1, and Tw is not integer as well (it is implied that S satisfies the eigenvalues condition below).
Lemma 7.7. If Sw=Kw(K1-1(S)) is not an integer matrix for some w∈{0,1,...,n}, then for every nonnegative integer k, equitable partitions with quotient matrix S+k(q-1)Id do not exist in H(n+k,q).
On the other hand, the matrices Sw must be nonnegetive (experimentally, this test does not reject any parameters for q=2, but for q>2 it works well).
Lemma 7.8. (i) If for some w∈{0,1,...,n} the matrix Sw=Kw(K1-1(S)) has a negative entry, then equitable partitions with quotient matrix S do not exist in H(n,q).
(ii) If Kn(K1-1(S)) has a negative entry and S has a complete collection of eigenvalues that are eigenvalues of H(n,q) (i.e., of form n(q-1)-iq, i∈{0,...,n}), then for every nonnegative integer k, equitable partitions with quotient matrix S+k(q-1)Id do not exist in H(n+k,q).
Lemma 7.4. All eigenvalues of the quotient matrix S of an equitable partition of a graph Γ are eigenvalues of Γ. In particular, if Γ = H(n,q), then all eigenvalues of S are in {−n,−n+q,...,(q−1)n} (in particular, congruent to -n modulo q).
Proposition 7.1 (correlation-immunity bound for arithmetic CR codes). If there exists a {ρb,...,2b,b;c,2c,...,ρc}-CR code C in H(n,2), where b≠c, then n≥3(b+c)ρ/4. (For ρ=1, we have θ≥-n/3, where θ=a-c=d-b [FDF07b]).
Lemma 7.5 ([KLM10]). The difference between the two largest eigenvalues of the quotient matrix S of a CR code in H(n,q) must be the largest difference between two neighbor eigenvalues of S.
Proposition 7.1 and Lemma 7.5 are special cases (that is, there is no need to check them separately for a putative quotient matrix if does not contradict Lemma 7.6) of the following lemma, whose proof uses zeroes of the Krein coefficients of the Hamming graph.
Lemma 7.6 (Triangle inequality). Assume we have a fixed basis from eigenvectors of the
quotient matrix S of an equitable partition of H(n,q). For basis vectors f, g, h corresponding to the eigenvalues (q-1)n-qi, (q-1)n-qj, (q-1)n-qk of S and H(n,q), respectively, assume that the decomposition of f•g (componentwise product) into the sum of basis eigenfunctions includes h with nonzero coefficient. Then
(i) |i-j|≤k≤i+j;
(ii) for q=2, we also have k≤2n-i-j and i+j+k≡0 mod 2.
Given the quotient matrix, we can calculate the interweight distributions of a putative equitable partition of H(n,2) [Vas09], [Kro14]. All the values must be nonnegative (they are "always" integer provided the weight-distribution integrality condition is satisfied). For some intersection arrays, this gives a lower bound on the dimension of the Hamming graph containing a corresponding CR code.
[Hyun10] Hyun. A bound on equitable partitions of the Hamming space. IEEE Trans. Inf. Theory 56(5) 2010, 2109-2111. DOI 10.1109/TIT.2010.2043773
[KLM10] J. H. Koolen, W. S. Lee, W. J. Martin. Characterizing completely regular codes from an algebraic viewpoint. Contemp. Math. 531 (2010), 223-242 http://arxiv.org/abs/0911.1828
[Kro14] D. S. Krotov. On Calculation of the Interweight Distribution of an Equitable Partition. J. Algebr.Comb. 40(2) 2014, 373-386. DOI 10.1007/s10801-013-0492-3
[Vas08] A. Yu. Vasil'eva. Linear binary completely regular codes with distance 2. Computational Technologies in Electrical and Electronics Engineering, 2008. SIBIRCON 2008. IEEE Region 8 International Conference on. 12-15. DOI 10.1109/SIBIRCON.2008.4602615
[Vas09] A. Yu. Vasil’eva. Local and interweight spectra of completely regular codes and of perfect colorings. Probl. Inf. Transm. 45(2), 2009, 151-157. DOI 10.1134/S0032946009020069, translated from Probl. Peredachi Inf. 45(2) 2009, 84-90.