1
$\begingroup$

For each $(i,j)\in \mathbb{N}^2$, $a(i,j)=1$ or $0$, and 1) $a(i,i)=0$ for all $i$; 2)for fixed $i$, there is at most one $j$ such that $a(i,j)=1$. Suppose we know that there is a finite $\kappa$ such that \begin{equation} \sum_{i\in S, j\in S^{C}}a(i,j)\le\kappa\end{equation} for any subset $S$ of $\mathbb{N}$,then one can show $\sum a(i,j)$ is bounded by $3\kappa$.

I am asking what is the largest possible value of $\sum a(i,j)$.

For people who are interested in the background, I am considering an operator $T\in\mathcal{L}(\ell^2)$. With respect to the natural basis, the entries of $T$ are $a(i,j)$. The existence of $\kappa$ in the first inequality is the same as \begin{equation}rank(TP-PTP)\le\kappa\end{equation} for all orthogonal projections $P$ in the masa (maximal abelian, self-adjoint subalgebra) of diagonal operators.

In a recent paper by Popov, Marcoux and Radjavi (Almost Invariant Halfspaces and Approximate Commutation), they have shown $\sum a(i,j)$ is bounded by $3\kappa$ (Thm 4.7), but in almost all examples I can think of, $\sum a(i,j)\le 2\kappa$, so I wonder whether the coefficient can be improved.

Again, I think the problem has been reduced to a purely algebraic or number theoretic problem in the first two paragraph of this post.

Thanks very much!

  • 2
    Cross post on MO http://mathoverflow.net/questions/100417/how-many-1s-could-be-there-in-this-sequence2012-06-23

1 Answers 1

1

I believe there is a small counterexample with $\kappa=3$: $\left( \begin{array}{ccccc} 0&1&1&0&0\\ 0&0&1&1&0\\ 0&0&0&1&1\\ 1&0&0&0&1\\ 1&1&0&0&0 \end{array} \right).$ More generally, it is easy to prove an upper bound of $4 \kappa$, and I am inclined to believe it is asymptotically best possible (I guess the Alon paper cites a bound of the form $4 \kappa - O(\sqrt{\kappa}))$.

For the modified problem, where each row can have at most one 1, the stated upper bound $3\kappa$, assuming it is now accurate, is achieved by taking multiple disjoint copies of $\left( \begin{array}{ccc} 0&1&0\\ 0&0&1\\ 1&0&0\\ \end{array} \right)$. This satisfies the constraint using $\kappa$ copies for a total of $3\kappa$.

  • 0
    @HuiYu In the $6\times 6$ version formed from two copies of the $3\times 3$ example, I get $\kappa = 2$ with the matrix adding up to $6$. How do you arrive at $2\kappa+1$?2012-06-23