The bounded blocky-matrix complexity conjecture for bounded max-norm

About 1 year old · traced to

Let MM be a Boolean matrix, meaning a matrix with entries in {0,1}\{0,1\}. Its factorization max-norm is denoted by γ2(M)\gamma_2(M), and let bl⁡(M)\operatorname{bl}(M) be the minimum number of blocky matrices whose ±1\pm1-linear combination is MM. The bounded blocky-matrix complexity conjecture. For every γ>0\gamma>0 there exists bγb_{\gamma} such that every Boolean matrix MM with γ2(M)≤γ\gamma_2(M)\leq\gamma satisfies bl⁡(M)≤bγ\operatorname{bl}(M)\leq b_{\gamma}. This conjecture asks for a qualitative converse to the inequality γ2(M)≤bl⁡(M)\gamma_2(M)\leq\operatorname{bl}(M) and is equivalent to Conjecture III of HHH. Its resolution status is not specified in the source.

References

Primary source

István Tomon, “Factorization norms and Zarankiewicz problems”, arXiv:2502.18429 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.