Superlogarithmic Real Blocky Rank
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.
5 pages · 12 marked passages
Concepts
- thm✓
Main
- def
Definitions
Concept map
Preparing this local graph with the browser’s fonts…
Proofs
Proof network
Preparing this local graph with the browser’s fonts…
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
- Daniel Avraham and Amir Yehudayoff. On Blocky Ranks of Matrices. Computational Complexity, 2024. doi:10.1007/s00037-024-00248-1