1
$\begingroup$

From set of numbers from $\Bbb S=\{0,1,\dots,m\}$, how many distinct $3\times 3$ unimodular matrices parametrized by $(a,b,c,d,e,f)\in\Bbb S^6$ of following type can one form? \begin{bmatrix} a^2 &ab &b^2\\ c^2 &cd &d^2\\ e^2 &ef &f^2\\ \end{bmatrix}

Is it at least $3m^{2+\beta}$ for some $\beta>0$ when $m\gg0$?

From comment below determinant is $$(ad-bc)(af-be)(cd-ef).$$

So how many $3$ tuples of $2\times 2$ matrices of following type with determinant being simultaneously $\pm1$ with entries from $\Bbb S$? $$\begin{bmatrix} a &c\\ b &d \end{bmatrix}\quad \begin{bmatrix} c &e\\ d &f \end{bmatrix}\quad \begin{bmatrix} e &a\\ f &b \end{bmatrix}$$

An example matrix: \begin{bmatrix} 1 &1 &1\\ 9 &6 &4\\ 4 &2 &1\\ \end{bmatrix} has determinant $-1$.

Update:

As determined below by Kantelope and Neil Strickland, rough asymptotics seem to be at least $3m^2$. Could this be improved to $3m^{2+\beta}$ for some $\beta>0$ when $m\gg0$?

$\endgroup$
10
  • 1
    $\begingroup$ The determinant is $(ad-bc)(af-be)(cf-de)$. $\endgroup$
    – kantelope
    Sep 1, 2015 at 2:49
  • 2
    $\begingroup$ Take $(a,b,c,d,e,f)=(1,0,x+1,1,x,1)$. This only gives you $\approx m$ solutions though. Also $(a,b,c,d,e,f)=(1,1,x,x+1,x+1,x+2)$, etc. $\endgroup$
    – kantelope
    Sep 1, 2015 at 5:12
  • $\begingroup$ Please post as answer. There should be a way to get more. That gives you $m+1$ solutions each. What does 'etc' mean? There should be a convenient bivariate parametrization yielding $\Theta(m^2)$ such $3\times 3$ determinant $\pm1$ transformations. $\endgroup$
    – user76479
    Sep 1, 2015 at 5:15
  • $\begingroup$ Is there a way to count all? $\endgroup$
    – user76479
    Sep 1, 2015 at 5:17
  • 3
    $\begingroup$ I was only guessing but none of the questions indicate any work from your side. $\endgroup$
    – knsam
    Sep 2, 2015 at 16:48

2 Answers 2

1
$\begingroup$

I will first refine kantelope's analysis slightly.

We want $(ad-bc)(af-be)(cf-de)=1$, so the three factors must be $\pm 1$. For the moment I will consider the case where $(ad-bc)=(af-be)=(cf-de)=1$. This means that $a$ and $b$ are coprime.

Let $(u,v)$ be the smallest pair of strictly positive integers such that $av-bu=1$. Any other such pair must then have the form $(u+ia,v+ib)$ for some $i\geq 0$. Thus, there must be integers $i,j\geq 0$ such that $(c,d)=(u+ia,v+ib)$ and $(e,f)=(u+ja,v+jb)$. This gives $$cf-de=(u+ia)(v+jb)-(v+ib)(u+ja)=(i-j)(av-bu)=i-j,$$ so we need $i=j+1$. Thus, the number of solutions starting with $(a,b)$ is the number of $j\geq 0$ such that $u+(j+1)a\leq m$ and also $v+(j+1)b\leq m$. This makes it easy to write code to calculate the number $G(m)$ of solutions for any given $m$. It appears from the numerics that $G(m)/m^2$ converges to a limit which is about $0.6$. However, I have only calculated as far as $m=1000$, which is not far enough to see whether there might be logarithmic corrections.

$\endgroup$
3
  • $\begingroup$ Would it be $2^3\times 0.6=4.8$ if you include $\pm1$ sign? $\endgroup$
    – user76479
    Sep 1, 2015 at 19:05
  • $\begingroup$ @Arul: I think that it is more complicated than that, but I do not have a complete analysis. The function is invariant under a group of order $6$ generated by $(a,b,c,d,e,f)\mapsto (c,d,e,f,a,b)$ and $(a,b,c,d,e,f)\mapsto (d,c,b,a,f,e)$. $\endgroup$ Sep 1, 2015 at 19:16
  • $\begingroup$ do you have any updates on this? $\endgroup$
    – user76479
    Sep 15, 2015 at 2:48
0
$\begingroup$

For any given $(a,b)$, find $(c,d)$ with $ad-bc=1$ (Euclid), and note $(a,b,c,d,a+c,b+d)$ is a solution. You still have to worry about whether $a+c$ or $b+d$ is too large, but if $a,b\le m/2$ everything should be OK.

$\endgroup$
5
  • $\begingroup$ Following Bézout, the extended GCD algorithm gives you $c,d$ with $|d|\lt |a|$ and $|c|\lt |b|$. This follows straight from quotient-remainder. That's why I said it's OK if $a,b\le m/2$ (and $a,b$ should be coprime of course). Then $c,d\le m/2$ also, and their sums are $\le m$. See en.wikipedia.org/wiki/B%C3%A9zout%27s_identity $\endgroup$
    – kantelope
    Sep 1, 2015 at 10:21
  • $\begingroup$ oh I see this does seem to give $\Theta(m^2)$ distinct matrices. Can this be improved to $\Theta(m^3)$ or is this the best? $\endgroup$
    – user76479
    Sep 1, 2015 at 10:28
  • $\begingroup$ The variety $ad-bc=af-be=cf-de=1$ (or any of the $2^3$ related $\pm$ varieties) should be dimension 3. However, you want integral solutions (not rational), so I'd expect $m^2$ is the right rough order of magnitude, though likely times some log-power -- compare: the number of integral $ad-bc=1$ solutions (again a dim 3 variety) up to height $m$ should be like $\sum_{a,b\le m}(m/a)(m/b)\approx (m\log m)^2$. $\endgroup$
    – kantelope
    Sep 1, 2015 at 10:37
  • $\begingroup$ Oops, maybe that last bit should be $\sum_{a,b\le m} m/\max(a,b)\approx 2\sum_{a\le b\le m} m/b\approx 2m^2$ (and multiply by $6/\pi^2$ for coprimality, though I've been ignoring any constants throughout, and again taking $a,b\le m/2$ might be easier to analyze), so I don't know if there are logs or not. $\endgroup$
    – kantelope
    Sep 1, 2015 at 10:57
  • $\begingroup$ Could you elaborate the algebraic geometric picture more clearly in your posting? Also some references. I could take a look and get back. How does dimension relate to integer or rational point count? $\endgroup$
    – user76479
    Sep 1, 2015 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.