# 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. – Yuval Filmus Feb 29 '16 at 19:34
• Yeah but we also want any $k$ independent questions to yield the unique answer. – Benjamin Lindqvist Feb 29 '16 at 19:44
• I suggest you specify what you mean by independence in your question. – Yuval Filmus Feb 29 '16 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. – Benjamin Lindqvist Feb 29 '16 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.$" – Benjamin Lindqvist Feb 29 '16 at 21:45