# Details for constraints

### upper bound, recursive

cdc_upper_bound
$$A_q(n,d) \le \sum_{k=0}^n A_q(n,d;k)$$
ilp
ILP upper bound
EtzionVardy2011
improved_cdc_upper_bound
$$\sum_{k=0 \land k \equiv \lfloor v / 2 \rfloor \pmod{d}}^{v} A_q(v,2\lceil d/2 \rceil;k) \le A_q(v,d) \le 2 + \sum_{k=\lceil d/2 \rceil}^{v- \lceil d/2 \rceil} A_q(v,2\lceil d/2 \rceil;k)$$
HonoldKiermaierKurz20152 (Upper bound of Theorem 2.5)
relax_d
$$2 \nmid d \Rightarrow A_q(n,d) \le A_q(n,d-1)$$
special_cases_upper
Here we collect some special and unique connections.
Etzion2013

### lower bound, recursive

cdc_average_argument
$$\max_{k=0}^n \frac{q^{n+1-k}+q^k-2}{q^{n+1}-1} \cdot A_q(n+1,d+1;k) \le A_q(n,d)$$
EtzionSilberstein2009
cdc_lower_bound
$$\max_{k=0}^n A_q(n,d;k) \le A_q(n,d)$$
improved_cdc_lower_bound
$$\sum_{k=0 \land k \equiv \lfloor v / 2 \rfloor \pmod{d}}^{v} A_q(v,2\lceil d/2 \rceil;k) \le A_q(v,d) \le 2 + \sum_{k=\lceil d/2 \rceil}^{v- \lceil d/2 \rceil} A_q(v,2\lceil d/2 \rceil;k)$$
HonoldKiermaierKurz20152 (Lower bound of Theorem 2.5)
layer_construction
The bound is $$A_q(n,d) \ge \max\{ \sum_{k \in K} A_q(n,d;k) \mid K \subseteq \{0,\ldots,n\} : |k_1-k_2| \ge d \;\forall k_1 \ne k_2 \in K \}$$. This is computed using dynamic programming and the function $$L(N) := \max\{\sum_{k \in K} A_q(n,d;k) \mid K \subseteq \{0,\ldots,N\} : |k_1-k_2| \ge d \;\forall k_1 \ne k_2 \in K\} = \max\{ L(N-1), L(N-d) + A_q(n,d;N) \}$$ for all $$N = 0,\ldots,n$$.
HonoldKiermaierKurz20152
special_cases_lower
Here we collect some special and unique connections.
Etzion2013