2025/07/07 by Marcus Nilsson, Nilsson, Marcus
Computer Science · #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2507.04688
openalex publication_date 2025/07/07 · openalex created_date 2025/10/20 · openalex updated_date 2026/07/28
For a prime p and a positive integer s consider a homogeneous linear system over the ring ℤps (the ring of integers modulo ps) described by an n × m-matrix. The possible number of solutions to such a system is pj, where j=0,1,…, sm. We study the problem of how many n × m-matrices over ℤps there are given that we have exactly pj homogeneous solutions. For the case s=1 (when ℤps 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≤ s and n≥ 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),ps) gives the number of solutions to the quadratic system Ax=0 in ℤps.