|
Sibirskii Matematicheskii Zhurnal, 2014, Volume 55, Number 3, Pages 540–552
(Mi smj2551)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
Random systems of equations in free abelian groups
A. V. Men'shov Omsk State University, Omsk, Russia
Abstract:
We study the solvability of random systems of equations on the free abelian group $\mathbb Z^m$ of rank $m$. Denote by $\operatorname{SAT}(\mathbb Z^m,k,n)$ and $\operatorname{SAT}_{\mathbb Q^m}(\mathbb Z^m,k,n)$ the sets of all systems of $n$ equations of $k$ unknowns in $\mathbb Z^m$ satisfiable in $\mathbb Z^m$ and $\mathbb Q^m$ respectively. We prove that the asymptotic density $\rho(\operatorname{SAT}_{\mathbb Q^m}(\mathbb Z^m,k,n))$ of the set $\operatorname{SAT}_{\mathbb Q^m}(\mathbb Z^m,k,n)$ equals 1 for $n\le k$ and 0 for $n>k$. As regards, $\operatorname{SAT}(\mathbb Z^m,k,n)$ for $n<k$, some new estimates are obtained for the lower and upper asymptotic densities and it is proved that they lie between $\left(\prod^k_{j=k-n+1}\zeta(j)\right)^{-1}$ and $\left(\frac{\zeta(k+m)}{\zeta(k)}\right)^n$, where $\zeta(s)$ is the Riemann zeta function. For $n\le k$, a connection is established between the asymptotic density of $\operatorname{SAT}(\mathbb Z^m,k,n)$ and the sums of inverse greater divisors over matrices of full rank. Starting from this result, we make a conjecture about the asymptotic density of $\operatorname{SAT}(\mathbb Z^m,n,n)$. We prove that $\rho(\operatorname{SAT}(\mathbb Z^m,k,n))=0$ for $n>k$.
Keywords:
free abelian group, equation in a group, asymptotic density, Ehrhart quasipolynomial.
Received: 18.09.2013
Citation:
A. V. Men'shov, “Random systems of equations in free abelian groups”, Sibirsk. Mat. Zh., 55:3 (2014), 540–552; Siberian Math. J., 55:3 (2014), 440–450
Linking options:
https://www.mathnet.ru/eng/smj2551 https://www.mathnet.ru/eng/smj/v55/i3/p540
|
|