AIと代数系を作る

非可換置換多項式とベクトルHadamard積の簡易実装

概要

このプログラムは、ベクトル係数を持つ多項式に対して、置換作用とHadamard積を組み合わせた非可換な代数系を扱う例です。

• 素体 $( \mathbb{F}_p )$ 上のベクトルを係数とする多項式
• 置換 $(\pi)$ を係数ベクトルに作用させる
• 乗法は Hadamard積 + 置換作用 による非可換積
• 加法は通常のベクトル加算 $mod (p)$

---

代数系の定義

• ベクトル長: $( N )$

• 素体: $( \mathbb{F}_P )（ここでは (P=7)$ の簡易例）

• 多項式:

  f(x) = v_0 + v_1 x + v_2 x^2 + ... + v_{d-1} x^{d-1}, v_i ∈ F_P^N
  

• 置換作用:

  π(v)_i = v[π[i]]
  

• Hadamard積:

  (v ∘ w)_i = v_i * w_i (mod P)
  

• 多項式加算:

  (f+g)_i = v_i + w_i (mod P)
  

• 多項式乗法（非可換）:

  (f * g)_k = Σ_{i+j=k} v_i ∘ π(w_j)
  

---

プログラムでの実装のポイント

1. Vec構造体でベクトルを表現
2. Poly構造体で多項式を表現
3. vec_perm：置換作用
4. vec_hadamard_mul：Hadamard積
5. poly_mul：非可換積（置換作用 + Hadamard積）
6. poly_add, poly_sub：ベクトルごとの加減算
7. poly_div_mod_noncomm：非可換割り算（簡易版）
8. poly_inv：簡易逆元（deg=1 で非零ベクトルなら単位ベクトルで代用）

---

満たされる代数的性質

性質	成立 / 非成立
加法の結合律	成立
加法の可換律	成立
加法の零元	成立
加法の逆元	成立
乗法の結合律	非可換だが結合は成り立つ場合あり
乗法の可換律	成立しない
乗法の単位元	定義可能（単位ベクトルを定数項に置く）
分配律	成立

⚠ 注意

• 逆元は簡易的に deg=1 の場合のみ模擬
• 完全な多項式割り算や逆元計算は、循環行列やガウス消去が必要

---

プログラム例

int pi[N] = {2,0,3,1}; // 置換
Poly f, g, h;

h = poly_mul(f,g,pi);  // f*g
h = poly_mul(g,f,pi);  // g*f 非可換
Poly finv = poly_inv(f); // 簡易逆元
Poly r = poly_div_mod_noncomm(h,f,pi); // 非可換剰余

---

まとめ

• 非可換置換多項式は置換作用を乗法に組み込むことで可換律を破れる
• Hadamard積でベクトルごとの演算を簡単に実装
• 実験用代数系として暗号や符号理論の検証に応用可能
• 今後は逆元計算や剰余演算の完全化でさらに発展可能

---

人工知能と数学で遊ぶ

今日一日自分のアイデアをAIにやらせて、いろんな代数系を作って遊んでみました。
非可換性を持たせるために多項式の係数に置換作用付きベクトルを使ったのですが、なんとなくうまく行った感じ。
思いつきを計算機に与えてどうなるか見てみました。
多項式の不定元に置換を代入することで、トレースとしてベクトルが得られます。（素体上で）
暗号に使えるかどうかは今後考えます。
なにか応用が出来るといいかも知れない。
とりあえず巡回しないと思う。
割り算が定義できるので、modを取れば巡回する場合があるのかも。

#include <stdio.h>
#include <stdlib.h>

#define N 4   // ベクトル長
#define P 7   // 素体の素数

typedef struct { int coef[N]; } Vec;
#define MAX_DEG 3
typedef struct { Vec v[MAX_DEG]; int deg; } Poly;

int modp(int x){ x%=P; if(x<0)x+=P; return x; }

Vec vec_add(Vec a, Vec b){ Vec r; for(int i=0;i<N;i++) r.coef[i]=modp(a.coef[i]+b.coef[i]); return r; }
Vec vec_sub(Vec a, Vec b){ Vec r; for(int i=0;i<N;i++) r.coef[i]=modp(a.coef[i]-b.coef[i]); return r; }
Vec vec_hadamard_mul(Vec a, Vec b){ Vec r; for(int i=0;i<N;i++) r.coef[i]=modp(a.coef[i]*b.coef[i]); return r; }

// 修正版 gf_inv
int gf_inv(int a){
    if(a==0) return 0;
    for(int i=1;i<P;i++) if(modp(a*i)==1) return i;
    return 0;
}

Vec vec_hadamard_inv_if_exists(Vec v){ Vec r; for(int i=0;i<N;i++) r.coef[i]=(v.coef[i]==0)?0:gf_inv(v.coef[i]); return r; }
Vec vec_perm(Vec v, int pi[N]){ Vec r; for(int i=0;i<N;i++) r.coef[i]=v.coef[pi[i]]; return r; }

Poly poly_add(Poly a, Poly b){ Poly r=a; if(b.deg>r.deg) r.deg=b.deg; for(int i=0;i<b.deg;i++) r.v[i]=vec_add(r.v[i],b.v[i]); return r; }
Poly poly_sub(Poly a, Poly b){ Poly r=a; if(b.deg>r.deg) r.deg=b.deg; for(int i=0;i<b.deg;i++) r.v[i]=vec_sub(r.v[i],b.v[i]); return r; }

Poly poly_mul(Poly a, Poly b, int pi[N]){
    Poly r; r.deg = a.deg + b.deg -1;
    for(int i=0;i<r.deg;i++) r.v[i]=(Vec){{0}};
    for(int i=0;i<a.deg;i++){
        for(int j=0;j<b.deg;j++){
            Vec w = vec_perm(b.v[j], pi); // 置換作用
            Vec prod=vec_hadamard_mul(a.v[i],w);
            r.v[i+j]=vec_add(r.v[i+j],prod);
        }
    }
    return r;
}

Poly poly_div_mod_noncomm(Poly a, Poly b, int pi[N]){
    Poly r = a;
    while(r.deg >= b.deg){
        int d = r.deg - b.deg;
        Vec b_top_perm = vec_perm(b.v[b.deg-1], pi); // b.deg-1 が最高次
        Vec scale = vec_hadamard_mul(r.v[r.deg-1], vec_hadamard_inv_if_exists(b_top_perm));
        for(int i=0;i<b.deg;i++){
            Vec t = vec_hadamard_mul(scale, vec_perm(b.v[i], pi));
            r.v[i+d] = vec_sub(r.v[i+d], t);
        }
        // 最高次がゼロなら次数を減らす
        while(r.deg>0){
            int zero=1; for(int k=0;k<N;k++) if(r.v[r.deg-1].coef[k]!=0) zero=0;
            if(zero) r.deg--; else break;
        }
    }
    return r;
}

Poly poly_inv(Poly a){ // 簡易逆元
    Poly r; r.deg=a.deg;
    for(int i=0;i<a.deg;i++) for(int j=0;j<N;j++) r.v[i].coef[j]=(a.v[i].coef[j]!=0)?1:0;
    return r;
}

void poly_print(Poly p){
    for(int i=0;i<p.deg;i++){
        printf("[");
        for(int j=0;j<N;j++) printf("%d ",p.v[i].coef[j]);
        printf("]*pi^%d + ",i);
    }
    printf("0\n");
}

int main(){
    Poly f,g,h;
    f.deg=2; f.v[0]=(Vec){{1,2,3,4}}; f.v[1]=(Vec){{3,1,2,1}};
    g.deg=2; g.v[0]=(Vec){{4,1,2,6}}; g.v[1]=(Vec){{2,2,2,2}};
    int pi[N]={2,0,3,1};

    printf("f = "); poly_print(f);
    printf("g = "); poly_print(g);

    h = poly_mul(f,g,pi); printf("f*g = "); poly_print(h);
    h = poly_mul(g,f,pi); printf("g*f = "); poly_print(h);

    Poly finv = poly_inv(f); printf("f^-1 = "); poly_print(finv);

    Poly r = poly_div_mod_noncomm(h,f,pi); printf("h mod f = "); poly_print(r);

    return 0;
}