The Arithmetic Entropy Barrier: Decoupling of Algebraic Rank and Construction Cost in Dense Boolean Matrices
Fuente:
Zenodo
Saved in:
| Main Author: | |
|---|---|
| Format: | Recurso digital |
| Language: | English |
| Published: |
Zenodo
2026
|
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866901533118955520 |
|---|---|
| author | Uygun, Ender |
| author_facet | Uygun, Ender |
| contents | <p>The Log-Rank conjecture posits that the complexity of a matrix is polynomially related<br>to the logarithm of its rank. We investigate this intuition through the lens of “Scholz<br>Arithmetic Cost”, an empirical metric derived from addition chain complexity. In density-<br>controlled Monte-Carlo simulations scaling up to N = 128, we report a robust decoupling<br>phenomenon: Dense low-rank matrices (r = 3) are information-theoretically trivial (LZMA<br>compression ratio ≈ 0.01), yet their normalized arithmetic construction cost remains statis-<br>tically indistinguishable from random noise ( eC ≈ 0.74). Regression analysis confirms that<br>the arithmetic cost is driven almost exclusively by bit-density (βdensity ≈ 0.51), with the<br>low-rank indicator having a negligible effect (βrank ≈ −0.0025). These findings suggest an<br>“Arithmetic Entropy Barrier”: a noise floor where algebraic simplification fails to reduce<br>arithmetic construction cost, serving as a critical caveat for complexity bounds based solely<br>on rank.</p> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_18439301 |
| institution | Zenodo |
| language | eng |
| publishDate | 2026 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | The Arithmetic Entropy Barrier: Decoupling of Algebraic Rank and Construction Cost in Dense Boolean Matrices Uygun, Ender <p>The Log-Rank conjecture posits that the complexity of a matrix is polynomially related<br>to the logarithm of its rank. We investigate this intuition through the lens of “Scholz<br>Arithmetic Cost”, an empirical metric derived from addition chain complexity. In density-<br>controlled Monte-Carlo simulations scaling up to N = 128, we report a robust decoupling<br>phenomenon: Dense low-rank matrices (r = 3) are information-theoretically trivial (LZMA<br>compression ratio ≈ 0.01), yet their normalized arithmetic construction cost remains statis-<br>tically indistinguishable from random noise ( eC ≈ 0.74). Regression analysis confirms that<br>the arithmetic cost is driven almost exclusively by bit-density (βdensity ≈ 0.51), with the<br>low-rank indicator having a negligible effect (βrank ≈ −0.0025). These findings suggest an<br>“Arithmetic Entropy Barrier”: a noise floor where algebraic simplification fails to reduce<br>arithmetic construction cost, serving as a critical caveat for complexity bounds based solely<br>on rank.</p> |
| title | The Arithmetic Entropy Barrier: Decoupling of Algebraic Rank and Construction Cost in Dense Boolean Matrices |
| url | https://doi.org/10.5281/zenodo.18439301 |