The satisfiability threshold of random linear equations over finite commutative rings

@misc{gao2026satisfiability,
  title = {{The satisfiability threshold of random linear equations over finite commutative rings}},
  author = {Pu Gao and Theodore Morrison},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.23282},
  eprint = {2609.23282},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.23282},
}

TY  - UNPB
TI  - The satisfiability threshold of random linear equations over finite commutative rings
AU  - Pu Gao
AU  - Theodore Morrison
PY  - 2026
DA  - 2026/09/20
PB  - arXiv
DO  - 10.48550/arxiv.2609.23282
UR  - https://arxiv.org/abs/2609.23282
AB  - 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.
ER  -