# How many independent yes/no questions can be asked about a point in binary space (linear vs nonlinear codes)?

This question springs from thinking about the potential benefits of using nonlinear codes instead of linear codes. Say we have a point $x \in \{0,1\}^k$ and we want to guess what it is. A naive scheme would be to ask $2^k$ questions of the form "is $x=[0100001\dots 01]$?" etc, while a refinement would be "is the $i$:th bit a one?" while linear codes generalizes this one step further to "is $x_i + x_j + \dots + x_\ell = 1$?"

With linear codes we can enumerate $k$ independent questions of this form. What I'm wondering is: can we do better?

Call $\{0,1\}^k$ our codebook with a corresponding matrix $C$ containing the coordinates of the codewords in its rows, i.e. $C_0 = [0\dots 0], C_1 = [0\dots 0 1]$ etc. Say we permute this matrix and make the permutation known to the receiver prior to transmission.

Couldn't we produce more than $k$ independent questions by asking questions of the form "is $b_i + b_j + \dots = 1$?", where $b_i$ is the $i$:th bit of the binary representation of the permuted codebook index?

It seems this could generalize into any "type division": to form a question, divide the codebook into $A_i$ and $B_i$ where $|A_i| = |B_i|$ and ask questions of the form "is $x$ of type $A_i$ or $B_i$?"

Clearly, this scheme is a strict generalization of linear coding since parity checks follow this general even division algorithm. Is it a vacuous generalization or could we in fact produce more than $k$ independent questions in this manner?

EDIT: Clarifying independence due to demand - could we by using nonlinear coding construct a list of $k+2$ or more questions such that any size $k$ subset would recover the unique answer? (I made it $k+2$ since I think we can construct a list of $k+1$ questions by using linear codes - just make the $k+1$:th question about the parity of all the rest)

EDIT: This is not a question on decoding tractability, so please refrain on commenting on that aspect.

• Questions of the form $x=x_0?$ display this independence: any $2^n-1$ of them are independent, in the sense that knowing the answer to $2^n-2$ of them doesn't always determine the answer of the remaining one. Feb 29, 2016 at 19:34
• Yeah but we also want any $k$ independent questions to yield the unique answer. Feb 29, 2016 at 19:44
• I suggest you specify what you mean by independence in your question. Feb 29, 2016 at 19:45
• Done, but the edit kind of made me suspect that a positive answer to this question could have some serious repercussions in the coding world. Nonetheless, an explanatory answer in the negative would be nice as well. Feb 29, 2016 at 19:56

Linear codes which satisfy your requirement are known as linear MDS (maximum distance separable) codes. While there are no non-trivial (in your sense) binary linear MDS codes, there are such codes over larger alphabets. It might be that binary non-linear MDS codes are what you are after. In that case, you might be able to construct some from linear MDS codes over $\mathbb{F}_{2^k}$ for $k>1$.
• The following is called the MDS conjecture (Fundamentals of Error Correcting Codes, Huffman): "If there is a nontrivial $[n, k]$ MDS code over $F_q$ , then $n ≤ q + 1$, except when $q$ is even and $k = 3$ or $k = q − 1$ in which case $n ≤ q + 2.$" Feb 29, 2016 at 21:45