Mixing on $k$ Columns of the Transvection Walk
In Diaconis and Saloff-Coste (1996), the authors introduced the simple ``transvection" walk on $\mathrm{GL}_n(\mathbb F_2)$: at each step, choose two distinct rows and add one to the other. In Ben-Hamou (2025), the author recently proved that this walk has mixing time $O(n^2\log n)$. Inspired by applications in cryptography (see Sotiraki (2016)), Ben-Hamou and Peres (2018) conjectured that the first $k$ columns of this walk mixed in $O(nk \log(n))$ steps. Our main result is a proof of this conjecture uniformly in $n$ and $k.$ Our proof is based on a local-to-global entropy estimate, in the…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.27212
curl -X POST /api/v1/records/arxiv/2605.27212/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.27212/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'