0
$\begingroup$

I would like to define standard Gram matrices, and use them to help me understand the symmetries of lattices.

I define "standard Gram matrix" as the Gram matrix g that minimizes the deviation from Toeplitz and that satisfies abs(inv(g)) = abs(g).

I have obtained Gram matrices for D4, E8, A15+ with small deviations from Toeplitz that satisfy abs(inv(g)) = abs(g) but I cannot be sure that I have obtained the global optimum. My method for solving the optimization problem specified by the definition of "standard Gram matrix" is ad hoc and I cannot be sure that it has found the global optimum.

QUESTIONS:

-- How do I uniquely determine a standard Gram matrix for a lattice? Are there any other definitions of "standard Gram matrix" for lattices? Do you have any literature references in which "standard Gram matrix" is defined for any reason?

I seem to be able to uniquely define standard Gram matrices for D4, E8, A15+ for instance.

But I may have missed the optimum for E8 and A15+.

This is my ad-hoc method for determining the standard Gram matrix according to my definition:

I find a Gram matrix g for which abs(inv(g)) - abs(g) is zero. g seems to be unique up to permutations and sign flips, but I am not sure. I choose g to have the most positive signs. inv(mat) is the matrix inverse of mat, and abs(mat) is the absolute values of the matrix elements.

Furthermore I permute the basis vectors to make the Gram matrix maximally Toeplitz.

That seems to uniquely define the standard Gram matrices for D4 and E8.

("maximally" refers to the L1 norm of the matrix elements, sum of absolute values of deviations of matrix elements)

For instance, for the 24-cell D4 = D4* lattice I obtain a Toeplitz Gram matrix

$$ \mathrm{gd4} = \sqrt{\frac{1}{2}} \left( \begin{array}{cccc} 2 & 1 & 0 &-1 \\ 1 & 2 & 1 & 0 \\ 0 & 1 & 2 & 1 \\ -1& 0 & 1 & 2 \\ \end{array} \right)$$

The inverse is

$$ \mathrm{inv}(\mathrm{gd4}) = \sqrt{\frac{1}{2}} \left( \begin{array}{cccc} 2 &-1 & 0 & 1 \\ -1& 2 &-1 & 0 \\ 0 &-1 & 2 &-1 \\ 1 & 0 &-1 & 2 \\ \end{array} \right) $$

likewise E8 has gram matrix ge8, not quite Toepliz.

$$ \mathrm{ge8 =} \begin{array}{ccccccccc} && 2 && 0 && 1 && 0 && 0 && 0 && -1 && 1 \\ && 0 && 2 && 1 && 1 && 0 && 0 && 0 && -1 \\ && 1 && 1 && 2 && 0 && 1 && 0 && 0 && 0 \\ && 0 && 1 && 0 && 2 && -1 && 1 && 0 && 0 \\ && 0 && 0 && 1 && -1 && 2 && 0 && 1 && 0 \\ && 0 && 0 && 0 && 1 && 0 && 2 && 1 && 1 \\ && -1 && 0 && 0 && 0 && 1 && 1 && 2 && 0 \\ && 1 && -1 && 0 && 0 && 0 && 1 && 0 && 2 \\ \end{array} $$

Each basis vector is perpendicular (90 degrees) to four other basis vectors, and makes angles of 60, 60, 120 degrees with the other three basis vectors.

inverse

$$ \mathrm{inv(ge8) =} \begin{array}{ccccccccc} && 2 && 0 && -1 && 0 && 0 && 0 && 1 && -1 \\ && 0 && 2 && -1 && -1 && 0 && 0 && 0 && 1 \\ && -1 && -1 && 2 && 0 && -1 && 0 && 0 && 0 \\ && 0 && -1 && 0 && 2 && 1 && -1 && 0 && 0 \\ && 0 && 0 && -1 && 1 && 2 && 0 && -1 && 0 \\ && 0 && 0 && 0 && -1 && 0 && 2 && -1 && -1 \\ && 1 && 0 && 0 && 0 && -1 && -1 && 2 && 0 \\ && -1 && 1 && 0 && 0 && 0 && -1 && 0 && 2 \\ \end{array} $$

The "Dynkin diagrams" are a square for D4 and a cube for E8 as shown in the figure here: Dynkin diagrams for D4 and E8

In contrast the usual Dynkin diagram for D4 is a triangle: https://commons.wikimedia.org/wiki/File:Dynkin_diagram_D4.png

I wonder whether I have found the maximally Toeplitz Gram matrix for E8 and A15+.

For A15+ the permutations are irrelevant. In this case I obtain a Gram matrix ga15plus satisfying

abs(ga15plus) = abs(inv(ga15plus))

$$ \mathrm{ga15plus \ =} \begin{array}{ccccccccccccccccc} && 2 && 1 && 1 && 1 && 1 && 1 && 1 && 4 && 1 && 1 && 1 && 1 && 1 && 1 && 1 \\ && 1 && 2 && 1 && 1 && 1 && 1 && 1 && 4 && 1 && 1 && 1 && 1 && 1 && 1 && 1 \\ && 1 && 1 && 2 && 1 && 1 && 1 && 1 && 4 && 1 && 1 && 1 && 1 && 1 && 1 && 1 \\ && 1 && 1 && 1 && 2 && 1 && 1 && 1 && 4 && 1 && 1 && 1 && 1 && 1 && 1 && 1 \\ && 1 && 1 && 1 && 1 && 2 && 1 && 1 && 4 && 1 && 1 && 1 && 1 && 1 && 1 && 1 \\ && 1 && 1 && 1 && 1 && 1 && 2 && 1 && 4 && 1 && 1 && 1 && 1 && 1 && 1 && 1 \\ && 1 && 1 && 1 && 1 && 1 && 1 && 2 && 4 && 1 && 1 && 1 && 1 && 1 && 1 && 1 \\ && 4 && 4 && 4 && 4 && 4 && 4 && 4 && 15 && 4 && 4 && 4 && 4 && 4 && 4 && 4 \\ && 1 && 1 && 1 && 1 && 1 && 1 && 1 && 4 && 2 && 1 && 1 && 1 && 1 && 1 && 1 \\ && 1 && 1 && 1 && 1 && 1 && 1 && 1 && 4 && 1 && 2 && 1 && 1 && 1 && 1 && 1 \\ && 1 && 1 && 1 && 1 && 1 && 1 && 1 && 4 && 1 && 1 && 2 && 1 && 1 && 1 && 1 \\ && 1 && 1 && 1 && 1 && 1 && 1 && 1 && 4 && 1 && 1 && 1 && 2 && 1 && 1 && 1 \\ && 1 && 1 && 1 && 1 && 1 && 1 && 1 && 4 && 1 && 1 && 1 && 1 && 2 && 1 && 1 \\ && 1 && 1 && 1 && 1 && 1 && 1 && 1 && 4 && 1 && 1 && 1 && 1 && 1 && 2 && 1 \\ && 1 && 1 && 1 && 1 && 1 && 1 && 1 && 4 && 1 && 1 && 1 && 1 && 1 && 1 && 2 \\ \end{array} $$

$$ \mathrm{inv(ga15plus) \ =} \begin{array}{ccccccccccccccccc} && 2 && 1 && 1 && 1 && 1 && 1 && 1 && -4 && 1 && 1 && 1 && 1 && 1 && 1 && 1 \\ && 1 && 2 && 1 && 1 && 1 && 1 && 1 && -4 && 1 && 1 && 1 && 1 && 1 && 1 && 1 \\ && 1 && 1 && 2 && 1 && 1 && 1 && 1 && -4 && 1 && 1 && 1 && 1 && 1 && 1 && 1 \\ && 1 && 1 && 1 && 2 && 1 && 1 && 1 && -4 && 1 && 1 && 1 && 1 && 1 && 1 && 1 \\ && 1 && 1 && 1 && 1 && 2 && 1 && 1 && -4 && 1 && 1 && 1 && 1 && 1 && 1 && 1 \\ && 1 && 1 && 1 && 1 && 1 && 2 && 1 && -4 && 1 && 1 && 1 && 1 && 1 && 1 && 1 \\ && 1 && 1 && 1 && 1 && 1 && 1 && 2 && -4 && 1 && 1 && 1 && 1 && 1 && 1 && 1 \\ && -4 && -4 && -4 && -4 && -4 && -4 && -4 && 15 && -4 && -4 && -4 && -4 && -4 && -4 && -4 \\ && 1 && 1 && 1 && 1 && 1 && 1 && 1 && -4 && 2 && 1 && 1 && 1 && 1 && 1 && 1 \\ && 1 && 1 && 1 && 1 && 1 && 1 && 1 && -4 && 1 && 2 && 1 && 1 && 1 && 1 && 1 \\ && 1 && 1 && 1 && 1 && 1 && 1 && 1 && -4 && 1 && 1 && 2 && 1 && 1 && 1 && 1 \\ && 1 && 1 && 1 && 1 && 1 && 1 && 1 && -4 && 1 && 1 && 1 && 2 && 1 && 1 && 1 \\ && 1 && 1 && 1 && 1 && 1 && 1 && 1 && -4 && 1 && 1 && 1 && 1 && 2 && 1 && 1 \\ && 1 && 1 && 1 && 1 && 1 && 1 && 1 && -4 && 1 && 1 && 1 && 1 && 1 && 2 && 1 \\ && 1 && 1 && 1 && 1 && 1 && 1 && 1 && -4 && 1 && 1 && 1 && 1 && 1 && 1 && 2 \\ \end{array} $$

With this Gram matrix there is one unique basis vector, so for A15+, there are 15 equivalent permutations, 15 equivalent standard gram matrices according to my definition.

But perhaps a different ga15plus also satisfies the inverse equality and can be made more Toeplitz.

In summary with my draft definition of "standard Gram matrix",

I seem to obtain unique standard Gram matrices for D4 and E8 and 15 equivalent standard Gram matrices for A15+. But I am not sure that I have obtained the most Toeplitz Gram matrices for E8 and A15+.

Again my questions are

-- How do I uniquely determine a standard Gram matrix for a lattice? Are there any other definitions of "standard Gram matrix" for lattices? ​Do you have any literature references in which "standard Gram matrix" is defined for any reason?

Improve this question
$\endgroup$
16
  • $\begingroup$ This is a very confusing question. First, you are asking about definitions, yet there is no single precise definition. Second, Dynkin diagrams are those corresponding to the "finite" case, there is no A15+ : perhaps you mean Coxeter diagrams. Finally, those diagrams encode reflection groups, or more generally abstract Coxeter groups, in particular, they encode a presentation by generators and relations, and as such are not at all arbitrary. Perhaps the question you should be asking is how trying to determine the orthogonal symmetries of a lattice helps to make some non-arbitrary choices. $\endgroup$
    – Vladimir Dotsenko
    Commented Jan 13, 2022 at 6:27
  • $\begingroup$ vladimir-dotsenko I am asking how to uniquely define the Gram matrix for a lattice. I know that there seems to be no precise definition of "standard" uniquely defined Gram matrix in the literature. That is why I am asking. Please forgive my confusion about the nomenclature. I tried to define the diagram I am describing. For E8 it is actually a cube not an octagon. The diagram places lines between points representing basis vectors at 60 or 120 degrees. $\endgroup$
    – Dan Haxton
    Commented Jan 13, 2022 at 6:36
  • $\begingroup$ No, you are asking "what do you think of my definition", yet you do not give a precise definition. $\endgroup$
    – Vladimir Dotsenko
    Commented Jan 13, 2022 at 6:39
  • $\begingroup$ The most compact definition is the gram matrix g that minimizes the deviation from Toeplitz and that satisfies abs(inv(g)) = abs(g) $\endgroup$
    – Dan Haxton
    Commented Jan 13, 2022 at 6:48
  • $\begingroup$ I agree, "Perhaps the question you should be asking is how trying to determine the orthogonal symmetries of a lattice helps to make some non-arbitrary choices." Do you have any guidance regarding D4 and E8? $\endgroup$
    – Dan Haxton
    Commented Jan 13, 2022 at 6:59

1 Answer 1

Reset to default
2
$\begingroup$

How do I uniquely determine a standard Gram matrix for a lattice? Are there any other definitions of "standard Gram matrix" for lattices? Do you have any literature references in which "standard Gram matrix" is defined for any reason?

Yes, this has been done in A Canonical Form for Positive Definite Matrices. In particular, for positive definite $A$ (Gram matrices of positive definite lattices are positive definite), they first define $A, B$ to be arithmetically equivalent if $A = U^tBU$ for uniomdular $U$.

They then define a mapping

$$A\mapsto Can(A)$$ such that

  1. $Can(A)$ is equivalent to $A$, and
  2. For any unimodular $U$, $Can(U^tAU)=Can(A)$.

Their (broad) strategy is to reduce to the case of graphs, for which there are recent quasi-polynomial time algorithms. This somewhat limits the maximum dimension they can handle (computationally) --- it appears they go up to dimension 40 at the most.

Note that this problem is thought to be hard though --- it would imply a solution to the Lattice Isomorphism Problem. Efficient algorithms for this have been open for quite a while (there has been some interest for 10+ years), and recently two cryptosystems have been proposed assuming (variants of) this problem are hard, so now one can concretely say that efficient algorithms would break cryptographic proposals (so if you find one, there is a more obvious motivation to write it up).

Improve this answer
$\endgroup$
3
  • $\begingroup$ This paper is beyond my expertise unfortunately; I cannot understand their Can(A). The standard I proposed is based on an optimization problem, a scalar function cost(U'AU), B = Can(A) = U'AU, cost is to be minimized wrt U, U(A) = argmin_U cost(U'AU). Please let me know if you understand what their Can(A) function gives for A = gram matrix of E8. My gram matrix B = Can(gramE8) corresponds to the graph of a cube as I described; furthermore, the unique (?) complete nonintersecting edge circuit of the 8 vertices of the cube may be drawn based on whether the edges correspond to B(i,j) = -1 or 1 $\endgroup$
    – Dan Haxton
    Commented Feb 11, 2022 at 18:04
  • $\begingroup$ @DanHaxton their code is online (they cite it) here, I encourage you to explore this yourself. $\endgroup$
    – Mark Schultz-Wu
    Commented Feb 11, 2022 at 21:13
  • $\begingroup$ Oh thank you! I did not notice that. It is a very dense paper imho. $\endgroup$
    – Dan Haxton
    Commented Feb 12, 2022 at 22:34

You must log in to answer this question.

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