For integers \(0 \le k \le n\) and \(2 \le d \le \min\{k,n-k\}\) such that \(d\) is even, we have \(A_q(n,d;k)\le \max \left.\left\{ 1+\sum_{i=d/2}^k x_i \,\right|\, \sum_{i=d/2}^k -Q_j(i) x_i \le u_j \,\forall j=1, 2, \ldots, k \text{ and } x_i \ge 0 \,\forall i=d / 2, d/2+1, \ldots, k \right\}\) with \(u_j=\binom{n}{j}_{q}-\binom{n}{j-1}_{q}\), \(v_i=q^{i^2}\binom{l}{i}_{q}-\binom{n-1}{i}_{q}\), \(E_i(j)=\sum_{m=0}^i (-1)^{i-m} q^{\binom{i-m}{2}+jm}\binom{k-m}{k-1}_{q}\binom{k-j}{m}_{q}\binom{n-k-j+m}{m}_{q}\) and \(Q_j(i)=\frac{u_j}{v_i}E_i(j)\). ZhangJiangXia2011 (Proposition 3),
Delsart1973,
Delsart1978,
Delsart19782
partial_spread_5
\(d=2k \land k \nmid n \Rightarrow A_q(n,d;k) \le \left\lfloor\frac{q^n-1}{q^k-1}\right\rfloor-1 \) EtzionVardy2011
\(A_2(4k+3,8;4)\le 2^4l+4\), where \(l=\frac{2^{4k-1}-2^3}{2^4-1}\) and \(k \ge 2\),\(A_2(6k+4,12;6)\le 2^6l+8\), where \(l=\frac{2^{6k-2}-2^4}{2^6-1}\) and \(k \ge 2\),\(A_2(6k+5,12;6)\le 2^6l+18\), where \(l=\frac{2^{6k-1}-2^5}{2^6-1}\) and \(k \ge 2\),\(A_3(4k+3,8;4)\le 3^4l+14\), where \(l=\frac{3^{4k-1}-3^3}{3^4-1}\) and \(k \ge 2\),\(A_3(5k+3,10;5)\le 3^5l+13\), where \(l=\frac{3^{5k-2}-3^5}{3^3-1}\) and \(k \ge 2\),\(A_3(5k+4,10;5)\le 3^5l+44\), where \(l=\frac{3^{5k-1}-3^4}{3^5-1}\) and \(k \ge 2\),\(A_3(6k+4,12;6)\le 3^6l+41\), where \(l=\frac{3^{6k-2}-3^4}{3^6-1}\) and \(k \ge 2\),\(A_3(6k+5,12;6)\le 3^6l+133\), where \(l=\frac{3^{6k-1}-3^5}{3^6-1}\) and \(k \ge 2\),\(A_3(7k+4,14;7)\le 3^7l+40\), where \(l=\frac{3^{7k-3}-3^4}{3^7-1}\) and \(k \ge 2\),\(A_4(5k+3,10;5)\le 4^5l+32\), where \(l=\frac{4^{5k-2}-4^3}{4^5-1}\) and \(k \ge 2\),\(A_4(6k+3,12;6)\le 4^6l+30\), where \(l=\frac{4^{6k-3}-4^3}{4^6-1}\) and \(k \ge 2\),\(A_4(6k+5,12;6)\le 4^6l+548\), where \(l=\frac{4^{6k-1}-4^5}{4^6-1}\) and \(k \ge 2\),\(A_4(7k+4,14;7)\le 4^7l+128\), where \(l=\frac{4^{7k-3}-4^4}{4^7-1}\) and \(k \ge 2\),\(A_5(5k+2,10;5)\le 5^5l+7\), where \(l=\frac{5^{5k-3}-5^2}{5^5-1}\) and \(k \ge 2\),\(A_5(5k+4,10;5)\le 5^5l+329\), where \(l=\frac{5^{5k-1}-5^4}{5^5-1}\) and \(k \ge 2\),\(A_7(5k+4,10;5)\le 7^5l+1246\), where \(l=\frac{7^{5k-1}-7^2}{7^5-1}\) and \(k \ge 2\),\(A_8(4k+3,8;4)\le 8^4l+264\), where \(l=\frac{8^{4k-1}-8^3}{8^4-1}\) and \(k \ge 2\),\(A_8(5k+2,10;5)\le 8^5l+25\), where \(l=\frac{8^{5k-3}-8^2}{8^5-1}\) and \(k \ge 2\),\(A_8(6k+2,12;6)\le 8^6l+21\), where \(l=\frac{8^{6k-4}-8^2}{8^6-1}\) and \(k \ge 2\),\(A_9(3k+2,6;3)\le 9^3l+41\), where \(l=\frac{9^{3k-1}-9^2}{9^3-1}\) and \(k \ge 2\), and\(A_9(5k+3,10;5)\le 9^5l+365\), where \(l=\frac{9^{5k-2}-9^3}{9^5-1}\) and \(k \ge 2\) Kurz20173
Let \(G\) be a graph, \(A\) its adjacency matrix, and \(\omega(G)\) clique number of \(G\). Then \(\omega(G) \le \begin{cases}\text{rk}_p(A) + 1, & \text{ if } p \mid \omega(G) - 1,\\\text{rk}_p(A), & \text{ otherwise.}\end{cases}\) IhringerSinXiang2017 (Lemma 1.3),
NuffelenRompay2003 (Theorem 1)
\(A_q(n,4;3) \ge q^{2(n-3)} + \sum_{i=1}^{\alpha} q^{2(n-3-(q^2+q+2)i)}\) if \(q^2+q+1 < s\) with \(s=n-4\) if n is odd and \(s=n-3\) else and \(\alpha = \left\lfloor \frac{n-3}{q^2+q+2} \right\rfloor\) EtzionSilberstein2013 (Construction 2, see chapter IV, Theorem 17)
Let \(n\geq \frac{k^2+3k-2}{2}\) and \(q^2+q+1\geq \ell \), where \(\ell= n-\frac{k^2+k-6}{2}\) for odd \( n-\frac{k^2+k-6}{2}\) (or \( \ell= n-\frac{k^2+k-4}{2}\) for even \(n-\frac{k^2+k-6}{2}\)). Then \( A_q(n, 2k-2; k) \ge q^{2(n-k)}+\sum_{j=3}^{k-1} q^{2(n-\sum_{i=j}^k i)}+\binom{n-\frac{k^2+k-6}{2}}{2}_{q}\). SilbersteinTrautmann2015 (Construction A, see chapter III, Theorem 19, Corollary 20)
For all \(q\), we have \(A_q(8,4;4)\ge q^{12} + \binom{4}{2}_q (q^2+1)q^2+1\).For each \(k\ge 4\) and arbitrary \(q\) we have \(A_q(3k-3,2k-2;k)\ge q^{4k-6}+\frac{q^{2k-3}-q}{q^{k-2}-1}-q+1\). We have \(A_2(18,6;9) \ge 9241456945250010249\) HeinleinKurz20173 (Section V-A, Theorem 11)
If \(\binom{\mathbb{F}_q^{n_i}}{k_i} \) admit parallelisms, i.e., a partition into spreads, for \(i=1,2\) then \(A_q(n_1+n_2,4;k_1+k_2) \ge s_1 \cdot s_2 \cdot \min\{p_1,p_2\} \cdot m\), where \(s_i=\frac{q^{n_i}-1}{q^{k_i}-1}\) is the size of a spread and \(p_i=\frac{\binom{n_i}{k_i}_{q}}{s_i}\) is the size of a parallelism in \(\binom{\mathbb{F}_q^{n_i}}{k_i}\) for \(i=1,2\), and \(m=\lceil q^{\max\{k_1,n_2-k_2\}(\min\{k_1,n_2-k_2\}-1)} \rceil\) is the size of an MRD code with shape \(k_1 \times (n_2-k_2)\) and rank distance \(2\) over \(\mathbb{F}_q\). HeinleinKurz20173 (Theorem 9)
We use an ILP to solve the question which Hamming weight vectors to use. It may happen that the solution process takes too much time and is aborted. Then the comments near the sizes of the codes indicate “not optimal”. In both cases the current best choice of Hamming weight vectors is written to the comments. Let \(V\) be the set of Hamming weight vectors: \(V:=\binom{n}{k}\) and \(c(v)\) be the number of CDC codewords corresponding to the Hamming weight vector \(v \in V\) then the ILP is: $$\begin{align}\max & \sum_{v \in V} c(v) \cdot x_v && \\ & x_a + x_b \le 1 && \forall a \ne b \in V : d_H(a,b) < d \\ & x_v \in \mathbb{B} && \forall v \in V\end{align}$$ EtzionSilberstein2009,
GorlaRavagnani2017,
EtzionGorlaRavagnaniWachterZeh2016,
TrautmannRosenthal2010
This is handled similar to the Echelon Ferrers construction, but the ILP is adjusted.
Let \(pd(v)\) be the set of pending dots of the Ferrers diagramm of the Hamming weight vector \(v\). Let \(f:\{0,1,\ldots,q-1\}\rightarrow \mathbb{F}_q\) be a bijection.
Let \(D := \{ (u,v) \in V \times V \mid u \ne v \land ( d_H(u,v) \le d-4 \lor (d_H(u,v) = d-2 \land pd(u) \cap pd(v) = \emptyset))\}\) and \(C := \{ (u,v) \in V \times V \mid u \ne v \land d_H(u,v) = d-2 \land pd(u) \cap pd(v) \ne \emptyset \}\).
We use the following variables: \(x_v \in \mathbb{B} \;\forall v \in V, p_v \in \{0,1,\ldots,q-1\} \;\forall v \in V, a_{u,v,i} \in \mathbb{B} \;\forall (u,v) \in C, i \in pd(u)=pd(v), b_{u,v} \in \mathbb{B} \;\forall (u,v) \in C \).
The meaning of the variables is: \(x_v=1 \Leftrightarrow\) the Hamming weight vector \(v\) is in the solution. \(p_{v,i}=d \Leftrightarrow\) allocation for the pending dot \(i\) in the Ferrers diagramm of the vector \(v\) with \(f(d)\). \(a_{u,v,i}=1 \Leftrightarrow pd(u)_i > pd(v)_i \). \(b_{u,v}=1 \Leftrightarrow pd(u) \ne pd(v)\).
Important remark: For any \((u,v) \in C\) and \(i \in pd(u)=pd(v)\), the case \(a_{u,v,i}=a_{v,u,i}=1\) is not possible due to the last constraint.
EtzionSilberstein2013,
GorlaRavagnani2017
Let \(q \ge 2\) be a prime power and \(2 \le d/2 \le k \le n-k\) integers. If additionally \(d \le k+1\), then \(A_q(n,d;k) \ge q^{(n-k)(k-d/2+1)} \frac{q^{(d/2)^2(M+1)}-1}{q^{(d/2)^2}-1}q^{-(d/2)^2M}\) with \(M=\lceil 2(n-k)/d \rceil\). EtzionGorlaRavagnaniWachterZeh2016
\(A_q(n,2r;k)\le \frac{\binom{n}{k}_q A_q(m,2r-2t;k-t)}{\sum_{i=0}^t q^{i(m+i-k)}\binom{m}{k-i}_q\binom{n-m}{i}_q}\) for \(0\le t< r\le k\), \(k-t\le m\le v\), and \(t\le v-m\). Note that the description contains the value of \(t,m\) in brackets. An optional \(o\) indicates that the bound is applied to the orthogonal code parameters. AhlswedeAydinian2009 (Theorem 3, containing a typing error),
HeinleinKurz20172 (Theorem 8)