6
$\begingroup$

Quite some time ago I saw an article where a Monte-Carlo algorithm for computing the Smith normal form of an integer matrix was described. In this article the following problem was posed:

Suppose $P, Q\in\mathbb{Z}[X,Y]$ are polynomials without a common factor. Then $(P(n,m), Q(n,m))$ has a density, i.e. there exist real numbers $\delta_k$, such that $$ \lim_{N\rightarrow\infty} \frac{1}{4N^2}\#\big\{(n,m):-N\leq n,m\leq N, (P(n,m), Q(n,m)) = k\big\} = \delta_k, $$ and $\sum_k\delta_k = 1$.

Can someone please give me a reference to this paper?

Improve this question
$\endgroup$
2
  • $\begingroup$ Does anyone know whether the limit in the question has been established? This sounds quite approachable. $\endgroup$
    – Anthony Quas
    Commented Jun 17, 2015 at 14:17
  • $\begingroup$ It is not completely trivial, but also not too difficult. I am interested in a reference because the function $(n,m)\mapsto (P(n,m), Q(n,m))$ is an example of a new notion of almost periodicity, which retains distributions but not mean values. When talking about a class of functions it is always nice to have someone else stumbling about a function in this class before you. $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Commented Jun 17, 2015 at 14:46

1 Answer 1

Reset to default
2
$\begingroup$

Typing "Monte-Carlo" and "Smith normal" into MathSciNet turned up a few possibilities.

Mustafa Elsheikh, Mark Giesbrecht, Andy Novocin, B. David Saunders, Fast computation of Smith forms of sparse matrices over local rings, ISSAC 2012—Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation, 146–153, ACM, New York, 2012, MR3206298.

David Saunders, Zhendong Wan, Smith normal form of dense integer matrices, fast algorithms into practice. (English summary) ISSAC 2004, 274–281, ACM, New York, 2004, MR2126954 (2005k:15039).

[The review mentions a "fast Monte Carlo algorithm of Eberly, Giesbrecht and Villard for computing the Smith form of an integer matrix," but gives no reference.]

Mark Giesbrecht, Fast computation of the Smith form of a sparse integer matrix, Comput. Complexity 10 (2001), no. 1, 41–69, MR1867308 (2003d:15014).

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I don't think these references contain the "density formula" that the OP is searching for. Neither does the "Eberly, Giesbrecht, Villard paper", which you can find here: perso.ens-lyon.fr/gilles.villard/BIBLIOGRAPHIE/POSTSCRIPT/… $\endgroup$
    – Carlo Beenakker
    Commented Jun 18, 2015 at 5:22
  • $\begingroup$ @Carlo, thanks for looking into this more deeply than I did. I note that the references in (at least one of) the papers I listed seem to include papers that discuss probabilistic computation of Smith normal form, and maybe one of those is the one Jan-Christophe is looking for. $\endgroup$
    – Gerry Myerson
    Commented Jun 18, 2015 at 5:34
  • $\begingroup$ I think I looked at all relevant articles by Giesbrecht and the references therein and tried several combinations on Mathscinet and scholar.google. However, chances are high that someone has this article on his desk right now and can tell me about it. $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Commented Jun 18, 2015 at 11:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .