Metraipolis › archive › dc_cd3cdf421389
The satisfiability threshold of random linear equations over finite commutative rings — arXiv:2609.23282
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.23282
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T21:44:47.069Z
- SHA-256 of the archived text
7c43f23365a986d4bb1a305bbf8e26de5d377ce0ea0552717b02f65041a200fb- Stable URL of this page
https://metraipolis.com/documento/dc_cd3cdf421389
How to cite
The satisfiability threshold of random linear equations over finite commutative rings — arXiv:2609.23282 — arXiv (en), https://arxiv.org/abs/2609.23282 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cd3cdf421389 (Metraipolis archive dc_cd3cdf421389, sha256 7c43f23365a986d4bb1a305bbf8e26de5d377ce0ea0552717b02f65041a200fb)
BibTeX
@misc{dccd3cdf421389,
title = {The satisfiability threshold of random linear equations over finite commutative rings — arXiv:2609.23282},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.23282},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cd3cdf421389; sha256 7c43f23365a986d4bb1a305bbf8e26de5d377ce0ea0552717b02f65041a200fb},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.23282. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We extend the study of random linear equations over finite fields to equations over finite commutative rings. We characterize precisely when the satisfiability threshold occurs at a sublinear scale; namely, when the random system become unsatisfiable with high probability with a number of constraints $m$ that is sublinear in $n$, the number of variables. In this regime, we determine the exact value of the satisfiability threshold. In the complementary regime where the satisfiability threshold is linear in $n$, we determine its precise value when $R$ is a principal ring. Interestingly, this value is independent of the choice of $R$, mirroring the same phenomenon when $R$ is a finite field. We further prove that this independence of $R$ breaks down if $R$ is nonprincipal. In particular, we investigate a classical family of nonprincipal rings and determine the satisfiability thresholds for all rings in this family. Remarkably, in this setting, the satisfiability threshold depends not only on the underlying ring, but also on other parameters defining the random linear equation model. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-22 in math.CO). Categorie arXiv: Combinatorics (math.CO). Pagina del lavoro: https://arxiv.org/abs/2609.23282 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-09T21:26:41.113Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).