# Details for constraints

### upper bound, not derived

XiaFuJohnson1
$$A_q(n,d;k) \le \left\lfloor \frac{(q^k-q^{k-d/2})(q^n-1)}{(q^k-1)^2-(q^n-1)(q^{k-d/2}-1)} \right\rfloor$$ if $$(q^k-1)^2-(q^n-1)(q^{k-d/2}-1) > 0$$
XiaFu2009 (Theorem 2)
all_subs
$$A_q(n,d;k) \le \# G_q(n,k)$$
anticode
$$A_q(n,d;k) \le \frac{\binom{n}{k}_q}{\binom{n-k+d/2-1}{d/2-1}_q}$$
EtzionVardy2011
ilp_2
$$A_q(n,d;k) \le \frac{\binom{n}{w}_q}{\binom{k}{w}_q} \;\forall w \in \{k-d/2+1, \ldots, k-1\}$$
ilp_3
$$A_q(n,d;k) \le \frac{\binom{n}{a}_q}{\binom{n-k}{a-k}_q} \;\forall a \in \{k+1, \ldots, k+d/2-1\}$$
$$d=2k \land n=k(t+1)+r \land 0 < r < k \Rightarrow A_q(n,d;k) \le \sum_{i=0}^t q^{ik+r} - \lfloor \theta \rfloor -1$$ where $$2\theta = \sqrt{1+4q^k(q^k-q^r)}-(2q^k-2q^r+1)$$
BoseBush1952 (3.8), DrakeFreeman1979 (Corollary 8)
$$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
$$r \ge 1 \land t \ge 2 \land y \ge \max\{r,2\} \land z \ge 0 \land r,t,y,z \in \mathbb{Z} \land u=q^y \land y \le k \land k= \binom{r}{1}_q +1 -z >r \land v=kt+r \land l=\frac{q^{v-k}-q^r}{q^k-1}$$ $$\Rightarrow A_q(v,2k;k) \le lq^k + \lceil u-1/2 - 1/2\sqrt{1+4u(u-(z+y-1)(q-1)-1)}\rceil$$
HonoldKiermaierKurz20162 (Theorem 10)
$$r=n\pmod t \land 2 \le r < t \le \binom{r}{1}_q \Rightarrow A_q(n,2t;t) \le \frac{q^n-q^{t+r}}{q^t-1} +q^r-(q-1)(t-2)-c_1+c_2$$ where $$c_1 = 2-t \pmod{q}$$ and $$c_2 = \begin{cases} q & q^2 \mid (q-1)(t-2)+c_1 \\ 0 & \text{else} \end{cases}$$ such that $$-q+1 \le -c_1+c_2 \le q$$
NastaseSissokho20162 (Theorem 6)
$$r=n\pmod t \land 2 \le r < t \le 2^r-1 \Rightarrow A_2(n,2t;t) \le \frac{2^n-2^{t+r}}{2^t-1} +2^r-t+1+c$$ where $$c = \begin{cases} 1 & 4 \mid t-1 \\ 0 & \text{else} \end{cases}$$
NastaseSissokho20162 (Theorem 7)
$$r=n\pmod t \land t=\binom{r}{1}_q < n \land r\ge 2 \Rightarrow A_q(n,2t;t) \le lq^t + \min\{q,\lceil q^r/2\rceil\}$$ where $$l=\frac{q^{n-t}-q^r}{q^t-1}$$
NastaseSissokho2016 (Lemma 10 and Remark 11)
$$r \ge 1 \land k \ge 2 \land z,u \ge 0 \land t = \binom{r}{1}_q +1 -z+u > r \Rightarrow A_q(n,2t;t) \le lq^t+1+z(q-1)$$ where $$l=\frac{q^{n-t}-q^r}{q^t-1}$$ and $$n=kt+r$$
Kurz2016
$$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$$

Kurz2016
$$A_3(k(t+1)+2,2k;k) \le \frac{3^{k(t+1)+2}-3^2}{3^k-1}-\frac{3^2+1}{2}$$ where $$t \ge 1$$ and $$k \ge 4$$ are integers
Kurz2015 (Lemma 4.6)
singleton
$$A_q(n,d;k) \le \binom{n-d/2+1}{k-d/2+1}_q$$
KoetterKschischang2008
special_case_2_8_6_4
$$A_2(8,6;4) \le 272$$
HeinleinKurz2017
sphere_packing
$$A_q(n,d;k) \le \frac{\binom{n}{k}_q}{\sum_{i=0}^{\lfloor(d/2-1)/2\rfloor} \binom{k}{i}_q \cdot \binom{n-k}{i}_q \cdot q^{i^2}}$$
KoetterKschischang2008
$$A_q(n,2k;k) \le \left\lfloor\frac{q^n-1}{q^k-1}\right\rfloor$$

### lower bound, not derived

CossidentePavese14_theorem311
If $$n \ge 5$$ is odd, then $$A_q(2n,4;n) \ge q^{n^2-n} + \sum_{r=2}^{n-2} \binom{n}{r}_q \sum_{j=2}^{r} (-1)^{(r-j)} \binom{r}{j}_q q^{\binom{r-j}{2}}(q^{n(j-1)}-1) + \prod_{i=1}^{n-1} (q^i+1) - q^{\frac{n(n-1)}{2}} - \binom{n}{1}_q \left( q^{\frac{(n-1)(n-2)}{2}} - q^{\frac{(n-1)(n-3)}{4}} \prod_{i=1}^{\frac{n-1}{2}} (q^{2i-1}-1) \right) +y(y-1) + 1$$, using $$y:=q^{n-2}+q^{n-4}+\dots+q^3+1$$.
CossidentePavese2014 (Theorem 3.11)
CossidentePavese14_theorem38
If $$n \ge 4$$ is even, then $$A_q(2n,4;n) \ge q^{n^2-n} + \sum_{r=2}^{n-2} \binom{n}{r}_q \sum_{j=2}^{r} (-1)^{(r-j)} \binom{r}{j}_q q^{\binom{r-j}{2}}(q^{n(j-1)}-1) + (q+1) \left( \prod_{i=1}^{n-1} (q^i+1) - 2q^{\frac{n(n-1)}{2}} + q^{\frac{n(n-2)}{4}} \prod_{i=1}^{\frac{n}{2}} (q^{2i-1}-1) \right) - q \cdot |G| + \binom{\frac{n}{2}}{1}_{q^2} \left( \binom{\frac{n}{2}}{1}_{q^2} - 1 \right) + 1$$ using $$|G| = 2 \prod_{i=1}^{n/2-1}(q^{2i}+1) - 2q^{(n(n-2)/4)}$$ if $$n/2$$ is odd and $$|G| = 2 \prod_{i=1}^{n/2-1}(q^{2i}+1) - 2q^{(n(n-2)/4)} + q^{n(n-4)/8}\prod_{i=1}^{n/4}(q^{4i-2}-1)$$ if $$n/2$$ is even.
CossidentePavese2014 (Theorem 3.8)
CossidentePavese14_theorem43
$$A_q(8,4;4) \ge q^{12}+q^2(q^2+1)^2(q^2+q+1)+1$$
CossidentePavese2014 (Theorem 4.3)
CossidentePavese_n6_d4_k3
$$A_q(6,4;3) \ge q^3(q^2-1)(q-1)/3 + (q^2+1)(q^2+q+1)$$
CossidentePavese2015 (Corollary 7.4)
Gorla_Ravagnani_2014
Application of Echelon Ferrers Construction
GorlaRavagnani2014
HonoldKiermaierKurz_n6_d4_k3
$$A_q(6,4;3) \ge q^6+2q^2+2q+1$$ for $$3 \le q$$
HonoldKiermaierKurz2015 (Theorem 2)
construction_honold
Construction by Thomas Honold, presented at ALCOMA15
coset_construction
HeinleinKurz2015
coset_construction_parallelism_part
HeinleinKurz2015
echelon_ferrers
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, GorlaRavagnani2014
ef_computation
Exact computation of echelon ferrers construction.
EtzionSilberstein2009, GorlaRavagnani2014
expurgation_augmentation_general
$$A_2(v,4;3) \geq 2^{2(v-3)}+\frac{9}{8}\binom{v-3}{2}_2$$ for $$v \equiv 7\pmod{8}$$
$$A_2(v,4;3)\geq 2^{2(v-3)}+\frac{81}{64}\binom{v-3}{2}_2$$ for $$v\equiv 3\pmod{8}$$ and $$v\geq 11$$
AiHonoldLiu2016 (Main Theorem)
expurgation_augmentation_special_cases
$$A_2(7,4;3) \ge 2^{8} + 45$$
$$A_2(8,4;3) \ge 2^{10} + 93$$
$$A_2(9,4;3) \ge 2^{12} + 756$$
$$A_2(10,4;3) \ge 2^{14} + 2540$$
$$A_2(11,4;3) \ge 2^{16} + 13770$$
$$A_2(12,4;3) \ge 2^{18} + 47523$$
$$A_2(13,4;3) \ge 2^{20} + 239382$$
$$A_2(14,4;3) \ge 2^{22} + 775813$$
$$A_2(15,4;3) \ge 2^{24} + 3783708$$
$$A_2(16,4;3) \ge 2^{26} + 12499466$$
AiHonoldLiu2016 (Table 1)
graham_sloane
$$\frac{(q-1)\binom{n}{k}_q}{(q^n-1)q^{n(d/2-2)}} \le A_q(n,d;k)$$
Xia2008
greedy_multicomponent
Construction by Alexander Shishkin.
Shishkin2014, ShishkinGabidulinPilipchuk2014
lin_poly
$$q^{(n-k)(k-d/2+1)} \le A_q(n,d;k)$$
Note that this is the same size as the Lifted MRD codes.
KoetterKschischang2008
multicomponent
$$A_q(n,2d;k) \ge \sum_{i=0}^{\lfloor \frac{n-2k}{d} \rfloor} q^{(k-d+1)(n-k-di)} + \sum_{i=\lfloor \frac{n-2k}{d} \rfloor+1}^{\lfloor \frac{n-k}{d} \rfloor} \lceil q^{k(n-k+1-d(i+1))} \rceil$$
Trautmann2013
$$d=2k \Rightarrow \frac{q^n-q^k(q^{(n \bmod k)}-1)-1}{q^k-1} \le A_q(n,d;k)$$
EtzionVardy2011
pending_dots

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)$$.

\begin{align} \max & \sum_{v \in V} c(v) \cdot x_v && \\ & x_u + x_v \le 1 && \forall (u,v) \in D \\ & x_u + x_v \le 1 + b_{u,v} && \forall (u,v) \in C \\ & a_{u,v,i} \cdot (q-1) \ge p_{u,i} - p_{v,i} \ge 1-q(1-a_{u,v,i}) && \forall (u,v) \in C, i \in pd(u)=pd(v) \\ & a_{v,u,i} \cdot (q-1) \ge p_{v,i} - p_{u,i} \ge 1-q(1-a_{v,u,i}) && \forall (u,v) \in C, i \in pd(u)=pd(v) \\ & \sum_{i \in pd(u)=pd(v)} a_{u,v,i} + a_{v,u,i} \ge b_{u,v} && \forall (u,v) \in C \\ & b_{u,v} \ge a_{u,v,i} + a_{v,u,i} && \forall (u,v) \in C, i \in pd(u)=pd(v) \\ \end{align}

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.
SilbersteinEtzion2011, GorlaRavagnani2014

sphere_covering
$$\frac{\#G_q(n,k)}{\sum_{i=0}^{(d/2-1)+1} \binom{k}{i}_q \cdot \binom{n-k}{i}_q \cdot q^{i^2}} \le A_q(n,d;k)$$
KoetterKschischang2008
trivial_1
$$0 \le A_q(n,d;k)$$

### upper bound, derived

ilp_1
$$A_q(n,d;k) \le \frac{\binom{n}{w}_q}{\binom{k}{w}_q}A_q(n-w,d;k-w) \;\forall w \in \{1,\ldots,k-d/2\}$$
ilp_4
$$A_q(n,d;k) \le \frac{\binom{n}{a}_q}{\binom{n-k}{a-k}_q}A_q(a,d;k) \;\forall a \in \{k+d/2,\ldots,n-1\}$$
johnson_1
$$A_q(n,d;k) \le \left\lfloor\frac{(q^n-1)A_q(n-1,d;k-1)}{q^k-1}\right\rfloor$$
EtzionVardy2011
johnson_2
$$A_q(n,d;k) \le \left\lfloor\frac{(q^n-1)A_q(n-1,d;k)}{q^{n-k}-1}\right\rfloor$$
EtzionVardy2011

### lower bound, derived

construction_ST_using_old_codes
$$A_q(n,2d;k) \ge q^{\Delta(k-2d+1)}A_q(n-\Delta,2d;k)+A_q(\Delta,2d;k)$$ for $$3k \le n$$ and $$k \le \Delta \le n$$
SilbersteinTrautmann2014 (Corollary 39)
$$A_q(n,d;k) \ge A_q(m,d;k) \cdot \left\lceil q^{ \max\{k,n-m\}(\min\{k,n-m\}-d/2+1) } \right\rceil + A_q(n-m,d;k)$$ for $$k \le m \le n-k$$. Note that the description contains the value of $$m$$ in brackets. Presented at ALCOMA15.