Counting linear congruence systems with a fixed number of solutions
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913930402594816 |
|---|---|
| author | Nilsson, Marcus |
| author_facet | Nilsson, Marcus |
| contents | For a prime $p$ and a positive integer $s$ consider a homogeneous linear system over the ring $\mathbb{Z}_{p^s}$ (the ring of integers modulo $p^s$) described by an $n \times m$-matrix. The possible number of solutions to such a system is $p^j$, where $j=0,1,\ldots, sm$. We study the problem of how many $n \times m$-matrices over $\mathbb{Z}_{p^s}$ there are given that we have exactly $p^j$ homogeneous solutions. For the case $s=1$ (when $\mathbb{Z}_{p^s}$ is a field) George von Landsberg proved a general formula in 1893. However, there seems to be few published general results for the case $s>1$ except when we have a unique solution ($j=0$). In this article we present recursive methods for counting such matrices and present explicit formulas for the case when $j\le s$ and $n\ge m$. We will use a generalization of Euler's $ϕ$-function and Gaussian binomial coefficients to express our formulas. As an application we compute the probability that gcd$(\det(A),p^s)$ gives the number of solutions to the quadratic system $Ax=0$ in $\mathbb{Z}_{p^s}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_04688 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Counting linear congruence systems with a fixed number of solutions Nilsson, Marcus Number Theory Combinatorics For a prime $p$ and a positive integer $s$ consider a homogeneous linear system over the ring $\mathbb{Z}_{p^s}$ (the ring of integers modulo $p^s$) described by an $n \times m$-matrix. The possible number of solutions to such a system is $p^j$, where $j=0,1,\ldots, sm$. We study the problem of how many $n \times m$-matrices over $\mathbb{Z}_{p^s}$ there are given that we have exactly $p^j$ homogeneous solutions. For the case $s=1$ (when $\mathbb{Z}_{p^s}$ is a field) George von Landsberg proved a general formula in 1893. However, there seems to be few published general results for the case $s>1$ except when we have a unique solution ($j=0$). In this article we present recursive methods for counting such matrices and present explicit formulas for the case when $j\le s$ and $n\ge m$. We will use a generalization of Euler's $ϕ$-function and Gaussian binomial coefficients to express our formulas. As an application we compute the probability that gcd$(\det(A),p^s)$ gives the number of solutions to the quadratic system $Ax=0$ in $\mathbb{Z}_{p^s}$. |
| title | Counting linear congruence systems with a fixed number of solutions |
| topic | Number Theory Combinatorics |
| url | https://arxiv.org/abs/2507.04688 |