[GAP Forum] problem with OrthogonalEmbeddings

[Thomas Breuer]

Dear GAP Forum,

Benjamin Sambale had reported a bug in the GAP function
'OrthogonalEmbeddings'.
Indeed, the GAP implementation that is available for about 20 years
is not correct, some solutions may be missing from the result.

A corrected version of the function can be found at

    http://www.math.rwth-aachen.de/~Thomas.Breuer/gapfix/fix_orthemb_4_7_5

The fix may become available in one of the next GAP releases.
Benjamin had also mentioned a problem with the documentation of the
function; this will then be fixed as well.

All the best,
Thomas

P.S.:
Wrong results occur in the following situation:

- Setup:
  Suppose that the matrix $A$ is given as the argument of the function,
  that is, we are interested in all integral matrices $X$ such that
  $X X^{tr} = A$ holds.
  Further suppose that there are $m$ vectors (up to sign) that can occur
  as the columns of the solution matrices $X$.
  Each solution is described by the vector (called $\iota$ in the
  underlying paper) of multiplicities of these $m$ vectors.

- Technical description:
  The algorithm enumerates the relevant coefficient vectors in reverse
  lexicographical order, and the bug in the program has the effect that
  the following illegal shortcut happens.
  Whenever the $(m-1)$-th coefficient shall be decreased by $1$ during
  the enumeration, it is erroneously set to zero,
  and also the $(m-2)$-th coefficient gets decreased by $1$.
  Thus all those solutions with given coefficients of the first $m-2$
  vectors are skipped for which the $(m-1)$-th vector does not occur
  with the maximal possible multiplicity.

- Conceptual description:
  The error strikes whenever solutions exist that differ only w. r. t.
  the multiplicities of the last two vectors,
  in other words, if a solution is not determined already by the
  multiplicities of the first $m-2$ vectors.
  In this situation, all those solutions are missing for which the
  $(m-1)$-th coefficient is smaller than the maximal value.
  Additionally, if a solution is determined by the multiplicities of
  the first $m-2$ vectors then it is missing if the coefficient of the
  $(m-1)$-th vector is smaller than the maximal possible value for it,
  as is computed by the algorithm in this situation.

- Examples:
  1. In Benjamin's example, we have $A = [ [ 4 ] ]$,
     $m = 2$, and the possible vectors are $x_1 = [ 2 ]$ and $x_2 = [ 1 ]$.
     The current function finds the solution with the coefficient
     vector $[ 1, 0 ]$ but not the one with the vector $[ 0, 4 ]$.

  2. In the case $A = [ [ 1, 0 ], [ 0, 4 ] ]$,
     we have $m = 3$ and $x_1 = [ 1, 0 ]$, $x_2 = [ 0, 2 ]$,
     $x_3 = [ 0, 1 ]$.
     The coefficient vector $[ 1, 1, 0 ]$ is found but the vector
     $[ 1, 0, 4 ]$ is not.

  3. In the case $A = [ [ 4, 0 ], [ 0, 1 ] ]$,
     we have $m = 3$ and $x_1 = [ 2, 0 ]$, $x_2 = [ 0, 1 ]$,
     $x_3 = [ 1, 0 ]$.
     In this case, the two solutions $[ 1, 1, 0 ]$ and $[ 0, 1, 4 ]$
     are found.


On Fri, Sep 05, 2014 at 07:37:15AM +0200, Benjamin Sambale wrote:
> Dear GAP people,
>
> according to the manual, the command OrthogonalEmbeddings does the  
> following: Given an integral symmetric matrix M, compute all integral  
> matrices X such that X^tr X = M where X^tr denotes the transpose of X.  
> The solution matrices X are given up to permutations and signs of their  
> rows.
>
> If I do (with GAP 4.7.5) OrthogonalEmbeddings([[4]]), I only get one  
> solution, namely X = [[2]]. However, there is another solution X =  
> [[1],[1],[1],[1]] which is somehow missing! What is wrong here?
> Apparently, the implementation is quite old and based on a paper by  
> Plesken from 1995.
>
> There is also an inaccuracy in the manual: It says: "the list L = [ x_1,  
> x_2, ..., x_n ] of vectors that may be rows of a solution; these are  
> exactly those vectors that fulfill the condition x_i ⋅ gram^{-1} ⋅  
> x_i^tr ≤ 1 (see ShortestVectors (25.6-2)), and we have gram = ∑_{i =  
> 1}^n x_i^tr ⋅ x_i".
>
> The last equation is usually not true. The equation only holds for the  
> set of vectors of a solution. Moreover, one should mention that the list  
> of vectors is only up to signs.
>
> Thanks and best wishes,
> Benjamin