Let $M \in \{0, 1\}^{n\times n}$. Given a constant integer $c \ge 2$, let the number of $1$s in each row be equal to $n/c$ (assuming $c$ is a divisor of $n$).

Given a constant $\beta \in (0,1)$, we call a row vector $r\,$
"$z$-*orthogonal*" if the number of $M$'s row vectors $r'$ such that $\,r' r^{\top} \le z\,n\,$ is greater or equal to $n-n^{\beta}$.

Question: When $n$ approaches infinity, what is the maximum number $N$ of $z$-orthogonal row vectors of $M$, in the case $z$ is strictly smaller than $1/c^2$?

Note: If $z \ge 1/c^2$ is very easy to show how to construct $M$ such that $N=n$.

In the case $z < 1/c^2$, it seems to me that $N=(c-1)n^{\beta}$, but I am not completely sure and I do not know how to prove it.

## ---

**Update**: I just posted now the "real" (complete) question from which this (sub)problem arose: Combinatorial 0-1 vector problem.

won'tdelete them. $\endgroup$ – Gerry Myerson Dec 8 '17 at 11:247more comments