Superlogarithmic Real Blocky Rank

lax-100002·created ·Lean v4.33.0 epoch · mathlib db584cd6d46c

Abstract

Boolean matrices can require more than logarithmically many blocky summands even when arbitrary real coefficients are allowed. We give a self-contained proof for a family obtained by polynomial evaluation over a binary finite field followed by binary Hadamard encoding. A distance argument, a count across disjoint degree intervals, and an integer-minor argument give real blocky rank of order at least log N times log log N along the constructed sequence of square dimensions N. The Lean formalization proves the finite bound and its superlogarithmic consequence without an external graph theorem. The field basis is chosen noncomputably, so the result makes no claim about efficient entry computation.

View annotated paper

5 pages · 12 marked passages

Concepts

Concept map
100%

Preparing this local graph with the browser’s fonts…

Proven claimDefinitionThis submissionA → B: B builds on A

Proofs

Proof network

100%

Preparing this local graph with the browser’s fonts…

assumptions conclusionProven claimStatement 1, 2, … of a claim with several statementsClaim from this submissionProof — open large view for details
Proof list

Proof code is not displayed; the archive records each proof's checked relationship between claims.

Related submissions

No other submission in the archive builds on this one, and this one builds on none.

References

  1. Daniel Avraham and Amir Yehudayoff. On Blocky Ranks of Matrices. Computational Complexity, 2024. doi:10.1007/s00037-024-00248-1