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.

Improve this question
$\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
    Commented Dec 10, 2017 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
    Commented Dec 10, 2017 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
    Commented Dec 10, 2017 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
    Commented Dec 10, 2017 at 20:57

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Dec 10, 2017 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
    Commented Dec 10, 2017 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
    Commented Dec 10, 2017 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
    Commented Dec 10, 2017 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
    Commented Dec 10, 2017 at 22:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .