SSE proofs

function poly(x, names, sep){
        
        let s = "";
        let zero =  true;
        for (let i = 0; i < 10; i++){
            if(x[i]){
                if(!zero){
                    s += '+';
                }
                zero = false;
                if (!i){
                  s += x[i]
                }
                else
                {
                if(x[i] != 1){
                    s += x[i];
                    s += sep;
                        }
                    s += names[i];
                }                                   
            }
        }
        if(zero)
            return '0';
        return s;       

}

function polyHTML(x){
    if(typeof(x) == typeof(666)){
    return x;
    }
    if(x.length == 10){
        return poly(x,  [ '1', 'x', 'y', 'z', 'x<sup>2</sup>', 'xy', 'xz', 'y<sup>2</sup>', 'yz', 'z<sup>2</sup>'], "");
    }
    return x;
}

function poly_sage(x){
    if(typeof(x) == typeof(666)){
    return x;
    }
    if(x.length == 10){
        return poly(x,  [ '1', 'x', 'y', 'z', 'x^2', 'x*y', 'x*z', 'y^2', 'y*z', 'z^2'], '*');
    }
    return x;
}

function poly_tex(x){
    if(typeof(x) == typeof(666)){
    return x;
    }
    if(x.length == 10){
        return poly(x,  [ '1', 'x', 'y', 'z', 'x^2', 'xy', 'xz', 'y^2', 'yz', 'z^2'], '');
    }
    return x;
}


function matrix_sage(matrix){
  const {cols, rows, m} = matrix;
  let matrix_array = Array.from({length: rows}, (_, i) => m.slice(i * cols, (i + 1) * cols));
  return  "matrix([" + matrix_array.map(row => "["+row.map(v => poly_sage(v)).join(',')+"]").join(',') + "])"
}


function matrix_tex(matrix){
  const {cols, rows, m} = matrix;
  let matrix_array = Array.from({length: rows}, (_, i) => m.slice(i * cols, (i + 1) * cols));
  return  "\\begin{pmatrix}\n" + matrix_array.map(row => ""+row.map(v => poly_sage(v)).join('&')+"\\\\").join('\n') + "\n\\end{pmatrix}\n"
}

function tex(proof){
    let s = '\\documentclass{article}\\usepackage{amsmath}\\setcounter{MaxMatrixCols}{11}\\begin{document}\n'
    for (const [i, [a,b,c,d]] of proof.entries()){
      s += "\\[ A_{" + i + "} = " + matrix_tex(a) + "=" + matrix_tex(b) + matrix_tex(c) + "\\]\n"
      s += "\\[ " + matrix_tex(c) + matrix_tex(b) + "=" + matrix_tex(d) + "= A_{" + (i+1) + "} \\]\n"
    }
    s += "\\end{document}";
    return s
}

function sage(proof){
    let s = 'steps = [\n';
    for (const [i, [a,b,c,d]] of proof.entries()){
      s += "(" + matrix_sage(a) + "," + matrix_sage(b)+ "," + matrix_sage(c) + "," + matrix_sage(d) + ")";
      s += ",\n"
    }
    s += "]";
    return s
}

function pynb(proof){
 const notebook = {
    cells: [{
      cell_type: "code",
      execution_count: null,
      id: "1",
      metadata: {},
      outputs: [],
      source: [sage(proof)+"\n", ""]
    },
    {
      cell_type: "code",
      execution_count: null,
      id: "2",
      metadata: {},
      outputs: [],
      source: [
       "for (A,R,S,B) in steps:\n",
       "    assert A == R*S\n",
       "    assert S*R == B\n",
       ""
      ]
    }
    
    
    ],
    metadata: {},
    nbformat: 4,
    nbformat_minor: 5
  };

return JSON.stringify(notebook);
}



function MatrixHTML(matrix){
  const {cols, rows, m} = matrix;
  let matrix_array = Array.from({length: rows}, (_, i) => m.slice(i * cols, (i + 1) * cols));
  let pad = cols > 3 ? 4/ cols : 1;
  return html`
  <div style="display:flex; align-items:stretch; width:fit-content;">
    <div style="border:1px solid #333; border-right:none; width:6px; border-radius:3px 0 0 3px;"></div>
    <table style="border-collapse:collapse; margin:0 -4px;">
    ${matrix_array.map(row => html`<tr>
    ${row.map(v => html`<td style="padding:${3*pad}px ${6*pad}px; text-align:center;">${polyHTML(v)}</td>`)}
    </tr>`)}
    </table>
    <div style="border:1px solid #333; border-left:none; width:6px; border-radius:0 3px 3px 0;"></div>
   </div>
`
}


function onestep(step, index){
const A = step[0];
const R = step[1];
const S = step[2];
const B = step[3];

return  html`
 <div style="display:flex; align-items:stretch; width:fit-content;">
     <span style="align-self:center; margin-right:6px;">A${index} = </span> 
      ${MatrixHTML(A)}
    <span style="align-self:center; margin-right:6px;"> = </span>
      ${MatrixHTML(R)}
    <span style="align-self:center; margin-right:6px;">  </span>
      ${MatrixHTML(S)}
</div>
<div style="height: 20px;"></div>
 <div style="display:flex; align-items:stretch; width:fit-content;">
      ${MatrixHTML(S)}
    <span style="align-self:center; margin-right:6px;">  </span>
      ${MatrixHTML(R)}
    <span style="align-self:center; margin-right:6px;"> = </span>
      ${MatrixHTML(B)}
     <span style="align-self:center; margin-right:6px;">= A${index+1}</span>    
</div>

</div>`;

}

The proof

This is a companion to my article (to be on arxiv soon) “Combinatorial Search for SSE equivalence”. It contains proofs that the Baker matrices are SSE equivalent for small sizes, and that the Ashley matrix is SSE equivalent to the matrix 2.

files =  FileAttachment("list.csv").csv({typed: true})

viewof toShow = Inputs.select(
  files,
  {label: "Choose", format: d => d.label, value: files[3]}
)

proof = await fetch(toShow.file).then(r => r.json());
data = proof.proof;

Below is a proof that

html`${MatrixHTML(data[0][0])}
and
${MatrixHTML(data[data.length-1][3])}
`

md`are strong shift equivalent (SSE). It uses ${data.length} steps.`

toShow.note != null ? html`Note: <em>${toShow.note}</em>` : html``

Download options

Sage

The sage file give a list of 4-uples \((A,R,S,B)\) s.t. \(A = RS, B = SR\). The notebook version also contains a few ways to test the SSE. If you intend to use these for matrices with polynomials, add the line var('x', 'y', 'z') to the file.

sage_data = new Blob([sage(data)], { type: "text/x-sagemath"});
pynb_data = new Blob([pynb(data)], { type: "text/x-sagemath"});

DOM.download(
    sage_data,
    "SSE.sage",
    `Download (sage)`
  );

DOM.download(
    pynb_data,
    "SSE.ipynb",
    `Download (notebook)`
  );

Tex

For large matrices, add {\setlength{\arraycolsep}{2pt} before compiling

tex_data = new Blob([tex(data)], { type: "text/x-sagemath"});

DOM.download(
    tex_data,
    "SSE.tex",
    `Download (tex)`
  );

See the proof

To navigate using the keyboard, click on the selector and use left/right.

viewof mode = Inputs.radio(
  ["One step at a time", "All steps at once"],
  {label: "Mode", value: "One step at a time"}
);

viewof index = {
  const slider = Inputs.range(
    [0, data.length - 1],
    {step: 1, label: "Step", value: 0}
  );

  slider.style.display = mode === "One step at a time" ? "" : "none";

  return slider;
}

(mode === "One step at a time")
  ? onestep(data[index], index)
  : html`${data.map((d,i) => onestep(d,i))}`