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 $\frac{n}{c}$ (assuming $c$ is a divisor of $n$). Let $\mathcal{M}\_c$ be the set of such matrices.


Given a *constant* $\beta \in (0,1)$ and a matrix $M \in \mathcal{M}\_c$, we say that "a row vector $r$ of $M$ is $\beta$-*covered*" if the number of row vectors $r'$ of $M$ such that $\,r' r^{\top} \ge \frac{n}{c^2}\,$ is greater than $n^{\beta}$.


**Question**: When $n$ approaches infinity, what is the **minimum** number $N$ of $\beta$-covered rows of a matrix in $\mathcal{M}\_c$? -- (My conjecture is $N=n-\Theta(n^{\beta})$).


---
---


PS: My previous questions [0-1 matrix combinatorial problem](https://mathoverflow.net/questions/287695/0-1-matrix-combinatorial-problem) and [A combinatorial 0-1 matrix problem](https://mathoverflow.net/questions/287962/a-combinatorial-0-1-matrix-problem) arose from this problem.



Combinatorial 0-1 vector problem
Here is an example of $\approx n^{1/3}$ vectors of length $n/c$ with overlaps strictly less than $n/c^2$. Probably, one can do $\approx n$ too, but I do not see any neat construction.


Take a prime $p$ of the form $p=cq-1$. Now, for the index set, use $\mathbb Z\_p^2\times\{1,2,\dots,p+1\}$, so $n=p^2(p+1)$. For the $k$-th vector $k=0,1,2,\dots,p-1$, place $1$'s at the triples $(a,b,c)$ with $a+kb\in\{0,1,\dots,q-1\}$ (in $\mathbb Z\_p$) and $c\ne k$. Then the cardinality of each set is $p^2q=n/c$. The overlaps are $q^2(p-1)$ (every linear system has unique solution and excluding $2$ indices leaves us with $p-1$ admissible ones). However
$$
\frac {q^2(p-1)}n=\frac{q^2}{p^2}\frac{cq-2}{cq}=\frac{q^2}{p^2}\left(1-\frac 2{cq}\right)<\frac{q^2}{p^2}\left(1-\frac 1{cq}\right)^2=c^{-2}\,.
$$


**Small edit**


For $c=2$ there is a nice example with $n/2$ vectors when $n=2^s-2$. Take the $s$-dimensional discrete unit cube $Q=\{-1,1\}^s$ and take all Walsh functions $x\_I=\prod\_{i\in I}x\_i$ with odd $|I|$. They are all $1$ at $e\_+=(1,\dots,1)$ and $-1$ at $e\_-=(-1,\dots,-1)$, so the vectors $v\_I=(1+x\_I)/2$ considered on $Q\setminus\{e\_+,e\_-\}$ all have $\frac n2$ ones and intersections of size $\frac{n-2}4$. I guess we can generalize this to other $c$ as well, but it is pretty clear now that if you cannot get your boung from Cauchy-Schwarz in this problem, then it is most likely just not there. 


