Code used in the paper “Ranks of matrices with few distinct entries”

In a previous version of the paper, I made a conjecture about representation of totally real algebraic integers by integral symmetric matrices. I proved the conjectured for totally real algebraic integers of degree $d\leq 2$, and performed computer calculations in support of this conjecture for $d=3$. Below is the description of these calculations.

However, the same conjecture was previously made Estes and Guralnick [2], who also proved it for $d\leq 4$. The conjecture was disproved by Dobrowolski [1]. Later, McKee [3] gave a counterexample of degree $6$. I thank Gary Greaves for bringing these works to my attention.

Representable algebraic integers

In the paper I called a totally real algebraic integer $\alpha$ representable if there exists a integral symmetric matrix $M$ such that $\alpha\mapsto M$ is an isomorphism of algebras $\Z[\alpha]$ and $\Z[M]$.

It is fruitful to extend this definition to arbitrary algebraic integers: an algebraic integer $\alpha$ is represented by a matrix $M$ if the $*$-algebra $\Z[\alpha,\overline{\alpha}]$ is isomorphic to the $*$-algebra $\Z[M,M^*]$. In this definition, we do not require that entries of $M$ are integers. If $\alpha$ is represented by a matrix $M$ whose entries belong to a number ring $R$, then we say that $\alpha$ is $R$-representable. We reserve word ‘representable’ to mean $\Z$-representable.

If $\alpha$ is represented by $M$, then $i\alpha$ is represented by the block matrix $\left(\begin{smallmatrix}0&M\\-M&0\end{smallmatrix}\right)$. As we saw in the paper, every number of the form $\sqrt{m}$ with $m\in\Z_+$ is representable. Hence numbers of the form $\sqrt{-m}$ are also representable.

This observation can be generalized. Indeed, suppose $M_{\alpha}$ is a matrix representing $\alpha$ over $\Z[\beta]$, where $\beta$ itself is represented by $M_{\beta}$ over $\Z$. Then one can obtain a $\Z$-representation of $\alpha$ by replacing each entry $f(\beta)$ in matrix $M_{\alpha}$, for a polynomial $f\in\Z[x]$, by the matrix $f(M_{\beta})$. The resulting block matrix represents $\alpha$ over $\Z$ because the matrices of the form $f(M_{\beta})$ commute with one another.

Representations of the roots of $x^3-Ax+B=0$

We apply the preceding discussion to find representations of roots of $x^3-Ax+B=0$ whenever these are totally real. The latter happens when the discriminant $4 A^3-27 B^2$ is nonnegative. The matrices that I used to represent these are $$ \begin{pmatrix} a&b+c\sqrt{-m}&d+e\sqrt{-m}\\ b-c\sqrt{-m}&f&g+h\sqrt{-m}\\ d-e\sqrt{-m}&g-h\sqrt{-m}&-a-f \end{pmatrix}$$ for $a,b,c,d,e,f,g,h\in\Z$. One can compute the $A$ and $B$ to be \begin{align} A&=a^2+a f+b^2+c^2 m+d^2+e^2 m+f^2+g^2+h^2 m,\\ B&=a^2 f-a b^2-a c^2 m+a f^2+a g^2+a h^2 m-b^2 f-2 b d g-2 b e h m-c^2 f m+2 c d h m-2 c e g m+d^2 f+e^2 f m \end{align} via the following Mathematica code.

M={{a,b+c*Sqrt[-m],d+e*Sqrt[-m]},{b-c*Sqrt[-m],f,g+h*Sqrt[-m]},{d-e*Sqrt[-m],g-h*Sqrt[-m],-a-f}};
CP=CharacteristicPolynomial[M,x];
CL=CoefficientList[-CP,x];
Print[CL[[1;;2]]//TeXForm];

The following C++ code then enumerates all $-8\leq a,b,c,d,e,f,g,h\leq 8$ and $1\leq m\leq 3$ in trying to represent cubic algebraic integers of the form above with $A\leq 240$. It reports that all of them are representable.

#include <iostream>
#include <iomanip>      // std::setw                                                                                         
#include <string.h>     // memset                                                                                             
const int R=8;
const int mx=240;
const int mxw=4096;
int tbl[mx+1][mxw];
static_assert(27*mxw*mxw>4*(mx+1)*(mx+1)*(mx+1),"Too small");

int int_sqrt(int num) // Compute floor(sqrt(num))  
{
  if (num<=0) return 0;
  int vl=1;
  while (vl*vl<=num) vl++;
  return vl-1;
}

int main()
{
  memset(tbl,0,sizeof(tbl));
  for(int a=-R;a<=R;a++)
    for (int f=-R;f<=R;f++)
      {
        int P1=a*a+a*f+f*f; // Pre-compute for speed
        int P2=a*a*f+a*f*f;
        std::cout<<"Progress report: a="<<a<<"  f="<<f<<std::endl;
        for (int b=-R;b<=R;b++)
          for (int c=-R;c<=R;c++)
            for (int d=-R;d<=R;d++)
              for (int e=-R;e<=R;e++)
                for (int g=-R;g<=R;g++)
                  for (int h=-R;h<=R;h++)
                    for (int m=1;m<=3;m++)
                      {
                        int A=P1+b*b+d*d+g*g+m*(c*c +e*e +h*h);
                        if (A>mx) continue;
                        int B=P2-a*b*b-a*c*c*m+a*g*g+a*h*h*m-b*b*f-2*b*d*g-2*b*e*h*m-f*c*c*m+f*d*d+f*e*e*m+2*c*d*h*m-2*c*e*g*m;
                        if (B<0) continue;
                        tbl[A][B]=1;
                      }
      }
  // Print the results
  for (int A=0;A<=mx;A++)
    {
      int Mx=int_sqrt(4*A*A*A/27);
      std::cout<<"For A="<<std::setw(3)<<A<<" ";
      int flg=0;
      for (int vl=0;vl<=Mx;vl++)
        {
          if (tbl[A][vl]==0)
            {
              if (flg)
		std::cout<<",";
              else
                std::cout<<"not represented is/are ";
              flg=1;
              std::cout<<vl;
            }
        }
      if (!flg) std::cout<<"all are represented";
      std::cout<<"."<<std::endl;
    }
  std::cout<<std::endl<<std::endl;
  return 0;
}

References

[1]

Edward Dobrowolski.
A note on integer symmetric matrices and Mahler's measure.
Canad. Math. Bull., 51(1):57–59, 2008.

[2]

Dennis R. Estes and Robert M. Guralnick.
Minimal polynomials of integral symmetric matrices.
Linear Algebra Appl., 192:83–99, 1993.
Computational linear algebra in algebraic and related problems (Essen, 1992).

[3]

James McKee.
Small-span characteristic polynomials of integer symmetric matrices.
In Algorithmic number theory, volume 6197 of Lecture Notes in Comput. Sci., pages 270–284. Springer, Berlin, 2010.