# Optimal and maximal codes

Is there an example of a code which is maximal but not optimal?

Definitions.

An $(n,M,d)$ code $C$ over $\mathbb{F}_q$ is maximal if $C$ is not contained in an $(n,M+1,d)$ code.

An $(n,M,d)$ code $C$ is optimal if $|C|=M=A_q(n,d)$, where $A_q(n,d)=\max \{M\mid\exists (n,M,d)\text{ code}\}$.

I know that each optimal code is maximal, but I do not really understand the difference between the two definitions.

Thank you for help,

Best regards

One way of attempting to get an optimal code $\mathcal C$ is to begin with $\mathcal C$ consisting of $\mathbf 0 \in \mathbb F_q^n$ , and then iteratively include in $\mathcal C$ an element of $\mathbb F_q^n-\mathcal C$ that is at distance $d$ or more from all of the already chosen codewords in $\mathcal C$. Note that beginning with $\mathcal C = \{\mathbf 0\}$ is not required; we could begin with any other element of $\mathbb F_q^n$ if we wish without affecting the results.
A maximal but non-optimal code $\mathcal C$ is defined to be the result achieved when $|\mathcal C| < A_q(n,d)$ but $\mathcal C$ cannot be enlarged any further in this manner -- that is, all the elements of $\mathbb F_q^n - \mathcal C$ are at distance smaller than $d$ from one or more of the codewords already chosen to be in $\mathcal C$. Note that the $\mathcal C$ that we have found is not a proper subset of a larger code with the same minimum distance $d$. If we want to arrive at an optimal code, we are blocked in this direction; and need to backtrack, that is, replace some of the previously chosen codewords for $\mathcal C$ by other choices that are also at distance $d$ or more from the codewords in $\mathcal C$ and then explore other subsets of $\mathbb F_q^n$ to find a code of cardinality $A_q(n,d)$.
If the value of $A_q(n,d)$ is known exactly, we can stop the search-and-include-and- backtrack-when-stuck process as soon as we find a $\mathcal C$ with $A_q(n,d)$ codewords in it, and this will be an optimal code, which, as you point out, is also maximal.
As an example, consider that with $q=2$, $n=3$, $d=2$, if we include codewords in $\mathcal C$ in order $000,~ 011, 101,~ 110$, we get an optimal code but had we begun with $000$ and then picked $111$ as our second choice, we would end up with the maximal but non-optimal code $\{000, 111\}$, all dressed up and nowhere to go, as the atheist's tombstone said.