# Is there a random-seeming language that is a proper subset of $\{s \in \{0,1\}^n: s \text{ has } k \; 1\text{'s}\}$?

I call a language $L$ a random-seeming language of length $n$ and weight $k$ if $L\subset\{0,1\}^n$, $s\in L \rightarrow (s \text{ has } k \;1\text{'s})$, and $$\forall _{I\subset[n]}\forall_{m\le \min\left(k,|I|\right)} \left(S=\{s \in L: \sum_{i\in I}b_i(s)=m\}\rightarrow\forall_{i\in I}\left[|\{s\in S:b_i(s)=1\}|=\frac {m|S|} {|I|}\right]\right)$$where $b_i(s)$ is the $i^\text{th}$ bit of $s$.

Obviously the language $L_\max=\left\{s\in\{0,1\}^n:\sum_{i\in \left[n\right]}b_i(s)=k\right\}$ is random-seeming, but are there any random-seeming languages of length $n$ and weight $k$ smaller than $L_\max$? More generally, given an integer $l \le |L_\max|$, what is the smallest $\epsilon\ge 0$ such that $$\exists _{L\subset L_\max}\forall _{I\subset[n]}\forall_{m\le \min\left(k,|I|\right)} \left(\left|L\right|\le l \wedge S=\{s \in L: \sum_{i\in I}b_i(s)=m\}\rightarrow\forall_{i\in I}\left[\left|\left|\left\{s\in S:b_i(s)=1\right\}\right|-\frac {m|S|} {|I|}\right|\le\epsilon\right]\right)$$

Note: I included the probability tag because this is essentially a probability question in my mind: a language $L$ is "random-seeming" iff for every set of set of digits $I$ and integer $m\le k$, the probability that a random string $s\in \{0,1\}^n$ with $m$ $1$'s in $I$ will be in $L$ is independent of the distribution of the $1$'s in $I$, and in the general problem, $\epsilon$ represents the maximum deviation such a probability can have from the mean probability for any given distribution of $1$'s in any given $I$. At least, that is what I intended it to mean. It's possible that I messed up the formal statement above (though I'm pretty sure I got it right), but the point of being random-seeming, is that the number of $1$'s among some of the digits tells you nothing (or in the general case, little) about the distribution of $1$'s in the rest of the digits, only their total number.

• Don't forget about the empty set. More importantly, note that the group $S_n$ of permutations of $[n]$ acts transitively on $\{0,1\}^n$. Perhaps, random-seemingness already implies $S_n$-invariance? In this case, the only two random-seeming languages would be the maximal and the empty one. – Ben Nov 18 '16 at 3:46
• Right, of course the empty set would be random-seeming. I'm looking for non-trivial examples though. I'm a curious as to how $S_n$ acts transitively on $\{0,1\}^n$, though, as the natural group action which occurs to me (rearranging the bits) isn't transitive. Do you mean that $S_n$ acts transitively on $\{s \in \{0,1\}^n : s \text{ has } k \;1 \text{'s}\}$, or is there some less obvious action of $S_n$ which is transitive on all of $\{0,1\}^n$? In any case, I suspect that the answer to the strict question is no, which is why I asked the general question about approximating random-seeming. – Gabriel Burns Nov 28 '16 at 16:36
• Dear @GabrielBurns, you're right, the action of the symmetric group isn't transitive on $\{0,1\}^n$ but the maximal language of weight $k$, sorry. Anyways, that idea doesn't seem to be useful at all. I also expect that the empty and maximal language are the only random-seeming ones, and I'd bet that there is a collection of your conditions which allows an induction and thus to reduce to a trivial case. The question about approximations seems pretty hard to me. Have you computed it for small $n$? – Ben Nov 28 '16 at 19:00
• @Ben, not yet. I'll try that when I have time, and see if I find any sort of pattern. – Gabriel Burns Nov 28 '16 at 21:01