The satisfiability threshold of random linear equations over finite commutative rings
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.23282
curl -X POST /api/v1/records/arxiv/2609.23282/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.23282/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'