show/hide this revision's text 4 added 1205 characters in body; added 1 characters in body

Below is a strengthening

[Edit: Originally, I gave the bound of Harrison Brown's argument. It does not settle $\frac{5-\sqrt{17}}{2}n^2$, but the remaining slack in the problem was easy to eliminate by considering the row with minimal sum. If my calculations are correct, but shows where this solves the slack problem. ]

This is modification of Harrison Brown's argument.

Suppose the total is less than $cn^2$. Then there is a row Let $r_1$ be a row with minimal sum at most $cn$. sn\leq cn$. Let us say that $r_1$ has $tn$ non-zero entries. Of course, $t\leq s$. Consider any other row $r$, which has $c_r n$ zeros at places that $r_1$ does not, and whose sum is $s_r n$. Then the total sum is at least $c_r(1-s_r)n^2+(1-c)^2n^2$. c_r(1-s_r)n^2+(1-s)(1-t)n^2$. On the other hand, the sum of $r$ restricted to columns where $r_1$ is non-zero is at least $c_r (t-c_r) n$. Hence the total sum is at least $\sum_r (c-c_r) t-c_r) n + (1-c)^2 1-s)(1-t) n^2$. cn^2&\geq (1-c)^2n^2+\max_r 1-s)(1-t)n^2+\max_r c_r(1-s_r)n^2\\cn^2&\geq (1-c)^2n^2+\sum_r 1-s)(1-t)n^2+\sum_r (c-c_r)n\\For a fixed value of $\sum c_r$ and $T=\max c_r(1-s_r)$ the minimum of $\sum s_r$ is achieved when all but one $c_r$ are equal to $T$ T/(1-s)$ or $c$ (that follows by optimizing a sum of two terms of the form $\max(0,1-T/c_r)$ \max(s,1-T/c_r)$ ). Let $p$ be the proportion of rows $r$ such that $c_r=c$. Then c&\geq p(1-T/c)t&\leq s\leq cSolving I claim that the optimization problem in minimum of $c$ under these three variablesconstraints occurs when the firs of these inequalities are equalities. Indeed, if the first inequality is strict, increase $T$. If the second inequality is strict, decrease $p$. Moreover, if $s\neq t$, we can decrease $s$. Thusc&= (1-c)(1-s)+T\\c&= (1-c)(1-s)+(1-p)(c-T)\\c&\geq p(1-T/c)+(1-p)s\\s&\leq cEliminating $T$ we obtainSolving the equation for $s$ and substituting into the inequality $s\leq c$, we get (please check!)Substituting this inequality for $p$ into $c\geq p(1-T/c)+(1-p)s$ and using the expressing for $s$ and $T$ that we have, we finally arrive (please double check!) to$$(1-2c)(2-c)(2c^3-6c^2+3c-1)\geq 0$$. Since $2c^3-6c^2+3c-1$ is negative for $c<1$, the inequality $c\geq \frac{5-\sqrt{17}}{2}=0.4384$.1/2$ follows.

[Before the edit, the answer was concluded by the following sentence, to which the comment refers].

show/hide this revision's text 3 added 2 characters in body

Below is a strengthening of Harrison Brown's argument. It does not settle the problem, but shows where the slack is.

Suppose the total is less than $cn^2$. Then there is a row $r_1$ with sum at most $cn$. Consider any other row $r$, which has $c_r n$ zeros at places that $r_1$ does not, and whose sum is $s_r n$. Then the total sum is at least $c_r(1-s_r)n^2+(1-c)^2n^2$. On the other hand, the sum of $r$ restricted to columns where $r_1$ is non-zero is at least $c_r n$. Hence the total sum is at least $\sum_r (c-c_r) n + (1-c)^2 n^2$. To summarize $$\begin{align*} cn^2&\geq (1-c)^2n^2+\max_r c_r(1-s_r)n\c_r(1-s_r)n^2\\ cn^2&\geq (1-c)^2n^2+\sum_r (c-c_r)n\\ cn^2&\geq \sum_r s_r n \end{align*} $$ For a fixed value of $\sum c_r$ and $T=\max c_r(1-s_r)$ the minimum of $\sum s_r$ is achieved when all but one $c_r$ are equal to $T$ or $c$ (that follows by optimizing a sum of two terms of the form $\max(0,1-T/c_r)$ ). Let $p$ be the proportion of rows $r$ such that $c_r=c$. Then $$\begin{align*} c&\geq (1-c)^2+T\\ c&\geq (1-c)^2+(1-p)(c-T)\\ c&\geq p(1-T/c) \end{align*}$$ Solving the optimization problem in these three variables, we get that $c\geq \frac{5-\sqrt{17}}{2}=0.4384$.

In general it is tempting to consider arbitrary sets of $k$ rows, and if the union of their zero sets is large, use that to say that the sum over corresponding columns is large.
show/hide this revision's text 2 Fixed a typo.

Below is a strengthening of Harrison Brown's argument. It does not settle the problem, but shows where the slack is.

Suppose the total is less than $cn^2$. Then there is a row $r_1$ with sum at most $cn$. Consider any other row $r$, which has $c_r n$ zeros at places that $r$ r_1$ does not, and whose sum is $s_r n$. Then the total sum is at least $c_r(1-s_r)n^2+(1-c)^2n^2$. On the other hand, the sum of $r$ restricted to columns where $r_1$ is non-zero is at least $c_r n$. Hence the total sum is at least $sum_r \sum_r (c-c_r) n + (1-c)^2 n^2$. To summarize $$\begin{align*} cn^2&\geq (1-c)^2n^2+\max_r c_r(1-s_r)n\\ cn^2&\geq (1-c)^2n^2+\sum_r (c-c_r)n\\ cn^2&\geq \sum_r s_r n \end{align*} $$ For a fixed value of $\sum c_r$ and $T=\max c_r(1-s_r)$ the minimum of $\sum s_r$ is achieved when all but one $c_r$ are equal to $T$ or $c$ (that follows by optimizing a sum of two terms of the form $\max(0,1-T/c_r)$ ). Let $p$ be the proportion of rows $r$ such that $c_r=c$. Then $$\begin{align*} c&\geq (1-c)^2+T\\ c&\geq (1-c)^2+(1-p)(c-T)\\ c&\geq p(1-T/c) \end{align*}$$ Solving the optimization problem in these three variables, we get that $c\geq \frac{5-\sqrt{17}}{2}=0.4384$.

In general it is tempting to consider arbitrary sets of $k$ rows, and if the union of their zero sets is large, use that to say that the sum over corresponding columns is large.
show/hide this revision's text 1