The Arithmetic Entropy Barrier: Decoupling of Algebraic Rank and Construction Cost in Dense Boolean Matrices

The Log-Rank conjecture posits that the complexity of a matrix is polynomially relatedto the logarithm of its rank. We investigate this intuition through the lens of “ScholzArithmetic Cost”, an empirical metric derived from addition chain complexity. In density-controlled Monte-Carlo simulations scaling up to N = 128, we report a robust decouplingphenomenon: Dense low-rank matrices (r = 3) are information-theoretically trivial (LZMAcompression ratio ≈ 0.01), yet their normalized arithmetic construction cost remains statis-tically indistinguishable from random noise ( eC ≈ 0.74). Regression analysis confirms thatthe arithmetic cost is driven almost exclusively by bit-density (βdensity ≈ 0.51), with thelow-rank indicator having a negligible effect (βrank ≈ −0.0025). These findings suggest an“Arithmetic Entropy Barrier”: a noise floor where algebraic simplification fails to reducearithmetic construction cost, serving as a critical caveat for complexity bounds based solelyon rank.