/*
Copyright (c) 2021 Corinne Diakhoumpa et Erwan Iev-Le Tac
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/
const p = 229;
// If Q = [v1 v2 v3] is an orthogonal matrix with rational coefficients then:
//
// [v1^T]
// Q^T Q = [v2^T] [v1 v2 v3] = [v_i.v_j] = [δ_ij] = I
// [v3^T]
//
// This can be rewritten for some integer q
//
// (q v_i).(q v_j) = q^2 δ_ij
//
// where the q v_i are vectors with integer coefficients. This becomes:
//
// (q v_i).(q v_j) = q^2 δ_ij mod p
//
// and if q is invertible in F_p we can write w_i = q^{-1} (qv_i) and
//
// w_i.w_j = δ_ij mod p
//
// so Q_p = [w1, w2, w3] is an orthogonal matrix in F_p.
//
// Given the previous observation, this program performs brute force search on
// Householder matrices mod p in order to find such an "orthogonal" matrix in
// F_p, written with a minimal number of characters. It could perform a more
// exhaustive search but the result is already good enough. The one chosen is:
//
// Q = [10, 9, 7]
// [ 9, 10, 7] det Q = -1
// [ 7, 7,-19]
//
// It then performs brute force search on upper triangular matrices R mod p such
// that R and A = QR are written with a minimal number of characters. The ones
// chosen are:
//
// R = [ 1, 2, 1]
// [ 0, -1, 6] det R = 9
// [ 0, 0, -9]
//
// A = [10, 11, 1]
// [ 9, 8, 6] det A = -9
// [ 7, 7, -9]
// Return canonical representation in (-p/2, p/2).
function canonical(n) {
n = n % p
if (n < -p/2)
n += p;
else if (n > p/2)
n -= p;
return n;
}
// Return inverse of n mod p.
function inv(n) {
return [2, 77, 92, 33, 102, 21, 53, 107, 54, -24, 11, 20, 110, 34, -71, 37,
7, -85, 31, 94, 95, 32, 112, 78, -28, 18, 13, 50, -8, -97, -30, 80,
-81, -82, 83, -29, 91, 113, 3, 58, -65, 69, -35, -100, -36, 73, -64,
41, -59, -74, -68, -40, 48, 15, -42, -66, 75, 4, -45, -25, 106, 108,
22, -9, 87, 14, 62, -39, -5, -56, 26, -16, -60, 67, -63, -47, 6, 99,
-70, -72, 101, 111, 93, 96, -84, -79, -90, -17, 44, -55, -105, -10,
52, 109, 103, 12, 89, -27, -43, 61, 49, 88, 19, 104, -23, -51, -86,
98, 38, -46, 57, 76, 114, -1, undefined, 1, -114, -76, -57, 46, -38,
-98, 86, 51, 23, -104, -19, -88, -49, -61, 43, 27, -89, -12, -103,
-109, -52, 10, 105, 55, -44, 17, 90, 79, 84, -96, -93, -111, -101,
72, 70, -99, -6, 47, 63, -67, 60, 16, -26, 56, 5, 39, -62, -14, -87,
9, -22, -108, -106, 25, 45, -4, -75, 66, 42, -15, -48, 40, 68, 74,
59, -41, 64, -73, 36, 100, 35, -69, 65, -58, -3, -113, -91, 29, -83,
82, 81, -80, 30, 97, 8, -50, -13, -18, 28, -78, -112, -32, -95, -94,
-31, 85, -7, -37, 71, -34, -110, -20, -11, 24, -54, -107, -53, -21,
-102, -33, -92, -77, -2][canonical(n) + 114];
}
// Calculate Householder matrix.
// H_p(v1, v2, v3) = I - 2 * (v.v^T) / (v^T.v) "modulo p"
function householder(v1, v2, v3) {
let N = canonical(v1**2 + v2**2 + v3**2);
if (N == 0)
return [];
let H = [
[N - 2*v1*v1, - 2*v1*v2, - 2*v1*v3],
[ - 2*v1*v2, N - 2*v2*v2, - 2*v2*v3],
[ - 2*v1*v3, - 2*v2*v3, N - 2*v3*v3]]
let invN = inv(N);
for (var i = 0; i < H.length; i++) {
for (var j = 0; j < H.length; j++) {
H[i][j] = canonical(invN * H[i][j]);
}
}
return H;
}
// Try and find the Householder matrices with shortest text length. These are
// orthogonal.
function shortest_householder() {
let min_H = new Set();
let min_length = 10 * 9;
for (var v1 = 1; v1 < p; v1++) {
console.log(`${100 * v1 / p}%`)
for (var v2 = 1; v2 <= v1; v2++) {
for (var v3 = 1; v3 <= v2; v3++) {
let H = householder(v1, v2, v3);
if (H.length == 0)
continue;
let l = H.toString().length;
if (l < min_length) {
min_length = l;
min_H = new Set();
}
if (l == min_length)
min_H.add(H)
}
}
}
console.log(min_length);
min_H.forEach(H => console.log(H));
}
shortest_householder();
function shortest_A_and_R() {
let min_A = new Set();
let min_length = 3 * 10;
for (var a = 1; a < p; a++) {
console.log(`${100 * a / p}%`);
let V = [canonical(a), canonical(10*a), canonical(9*a), canonical(7*a)];
let l = V.toString().length;
if (V.includes(0))
continue;
if (l < min_length) {
min_length = l;
min_A = new Set();
}
if (l == min_length)
min_A.add(V)
}
min_B_D = new Set();
min_length = 3 * 10;
for (var b = 1; b < p; b++) {
console.log(`${100 * b / p}%`);
for (var d = 1; d < p; d++) {
let V = [canonical(b), canonical(d),
canonical(9*d+10*b), canonical(10*d+9*b),
canonical(7*d+7*b)];
if (V.includes(0))
continue;
let l = V.toString().length;
if (l < min_length) {
min_length = l;
min_B_D = new Set();
}
if (l == min_length)
min_B_D.add(V)
}
}
min_C_E_F = new Set();
min_length = 3 * 10;
for (var c = 1; c < p; c++) {
console.log(`${100 * c / p}%`);
for (var e = 1; e < p; e++) {
for (var f = 1; f < p; f++) {
let V = [canonical(c),
canonical(e),
canonical(f),
canonical(7*f+9*e+10*c),
canonical(7*f+10*e+9*c),
canonical(-19*f+7*e+7*c)
];
if (V.includes(0))
continue;
let l = V.toString().length;
if (l < min_length) {
min_length = l;
min_C_E_F = new Set();
}
if (l == min_length)
min_C_E_F.add(V)
}
}
}
min_A.forEach(x => console.log(x));
min_B_D.forEach(x => console.log(x));
min_C_E_F.forEach(x => console.log(x));
}
shortest_A_and_R();