1
$\begingroup$

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 and A combinatorial 0-1 matrix problem arose from this problem.

$\endgroup$
4
  • 1
    $\begingroup$ That is a bit too optimistic. If $n=c^m$, you can create $cm$ pairwise $c^{-2}$ orthogonal vectors $v_{kp}$ putting $1$'s in the positions having the $k$-th digit equal to $p$ in their $c$-ary representation. Repeat all but one of them $n^\beta$ times and fill the rest of the matrix with the remaining one. This already gives $n-cn^\beta\log_c n$. If it were sets on the interval $[0,1]$, you would be able to go with this forever, but the discrete nature of the problem imposes some restrictions on such games, so, $n-n^{\beta+o(1)}$ may be already correct. Will that be enough for your purposes? $\endgroup$ – fedja Dec 10 '17 at 4:22
  • 1
    $\begingroup$ Actually every $n\times n$ Hadamard matrix gives an example (if you remove the constant row and replace $-1$ by $0$ in the remaining ones) of $n-1$ vectors with $n/2$ ones and the overlap of any $2$ exactly $n/4$. Of course, you were cunning enough to use $\ge$ instead of $>$ in the definition, but I doubt very much that it matters in the slightest except for making a counterexample ugly instead of neat and clean (I can do a reasonably clean one with $n^{1/3}$ instead of $n-1$ and strict inequalities, as requested, so $\beta>2/3$ definitely gives no gain over the trivial bound of $n+1$). $\endgroup$ – fedja Dec 10 '17 at 5:35
  • $\begingroup$ @fedja, thank you a lot for your precious help! I am very surprised by the existence of $n^{1/3}$ vectors having exactly $n/2$ ones such that the pairwise overlap is always strictly smaller than $n/4$. Could you please describe it? I now designed a method to create, when $n=c^m$, $\sum_{i=1}^{m} c^{(c^i)}$ vectors with $n/c$ ones such that the pairwise overlap is exactly $n/c^2$ (perhaps this method lists all vectors satisfying these properties "with the equality"). However I cannot see how to construct a list of vectors when the pairwise overlap is strictly smaller than $n/c^2$. $\endgroup$ – Penelope Benenati Dec 10 '17 at 13:17
  • 1
    $\begingroup$ Argh, I answered you in the comments to my post without the at construct, so you, most likely, haven't been notified yet. Ping! $\endgroup$ – fedja Dec 10 '17 at 20:57
3
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ That's really a great answer, thank you a lot! However I have to admit I am bit confused, because something (probably extremely basic) is not clear to me. I would have two (perhaps too) simple questions: 1. Why does this not contradict that here mathoverflow.net/questions/287962/… we got (as you wrote at the end) "[...] if $z<c^{−2}$, so the linear term can hold the inequality valid only for constant time"? The sum of all pairwise overlaps in your set of $N_0\approx n^{1/3}$ vectors should be asymptotically at least $N_0^2 n/c^2$. $\endgroup$ – Penelope Benenati Dec 10 '17 at 18:51
  • $\begingroup$ 2. Since for $c=2$ (i.e. $n/2$ ones) we cannot even have $3$ vectors such that the pairwise overlap is always smaller than $n/8$, I guess that there exists a threshold $\tau(c)$ smaller than the threshold $1/c^2$ I used, such that the answer to the this problem is $N \ge n-\Theta(n^{\beta})$. Am I right? $\endgroup$ – Penelope Benenati Dec 10 '17 at 18:52
  • 1
    $\begingroup$ Any coefficient at $n$ that is strictly below $c^{-2}$ would give you such a bound, as we discussed earlier. However, for that you need the reduction by a fixed portion of $n$ while the reduction in my example is only by about $n^{1/3}$. $\endgroup$ – fedja Dec 10 '17 at 19:36
  • $\begingroup$ Thank you! For any number N of vectors in $\{0,1\}^n$, using Cauchy Schwarz (as you suggested earlier here mathoverflow.net/questions/287962/…) we obtain more precisely $$zn(N^2-N)\ge\frac{N^2 n c^{-2}-Nnc^{-1}}{N^2-N}$$ which implies, when $z<c^{-2}$, $$N\le\frac{z-c^{-1}}{z-c^{-2}}.$$ Here, replacing the inner product threshold $\frac{n}{c^2}$ (of the above problem) with $\frac{n}{2c^2}$, we finally get $$N \le 2c-1 .$$ Since $c$ is a constant, can we state that with this new threshold we have $N = n-\Theta(n^{\beta})$? Thank you! $\endgroup$ – Penelope Benenati Dec 10 '17 at 21:32
  • $\begingroup$ To clarify: $N \le 2c-1$ is an upper bound for the number of $z$-orthogonal vectors in the related question mathoverflow.net/questions/287962/… if we set $z=\frac{1}{2c^2}$. I think that transposing this upper bound here, halving the inner product threshold, yields to the fact that we can repeat $n^{\beta}$ times a construction using not more than $2c-1=\Theta(1)$ $z$-orthogonal vectors, while all the other vectors $n-\Theta(n^{\beta})$ are $\beta$-covered. $\endgroup$ – Penelope Benenati Dec 10 '17 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.