Sharp rank bounds for powers-of-two matrices

Open problem: improved quantitative rank bounds · arXiv:2109.00618

arXiv Informal medium confidence— first stated 2021-09-01

Authors: Noga Alon, Jozsef Solymosi

Status open high confidence

Alon and Solymosi prove rank lower bounds of order $\log n$ (with weak polynomial dependence on the multiplicative-group rank $r$ and dimension $d$) via the Evertse–Schlickewei–Schmidt Subspace Theorem, and pose obtaining sharper quantitative bounds as an explicit open problem. No follow-up paper improving these bounds, nor any resolution of the special powers-of-2 instance, was found in a wide web search spanning 2021–2026.

Reviewer notes. The source paper appeared in IMRN 2023 (Vol. 2023, Issue 14, pp. 12383–12399). The open problem asks for better bounds than roughly $\log n \leq r d^8$, highlighting the case where all off-diagonal entries are integer powers of 2 as a concrete open instance. No follow-up resolving or improving these bounds was found in the indexed literature.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. It would be very interesting to get better bounds even for cases where the rank of the multiplicative group is very small, for example when all non-diagonal elements are powers of two.

Context

After the first proof of Theorem 1, the authors note that the quantitative bound obtained (essentially $\log\log n \leq r d^7$, improved to $\log n \leq r d^8$ in Section 4) is quite weak. They pose the challenge of obtaining sharper rank lower bounds, highlighting the special case where all off-diagonal entries are integer powers of $2$ as a concrete open instance.

Notes. No labelled theorem environment; expressed as an open research direction following the first proof. PDF source — the surrounding mathematical bounds may be garbled, but this prose statement is clear.

Source paper

Rank of matrices with entries from a multiplicative group
Noga Alon, Jozsef Solymosi · 2021-09-01
https://arxiv.org/abs/2109.00618 PDF source