nx_group.nx source
↩ module page · 116 lines · 3558 B
1// nx_group.nx -- small finite group primitives.
2//
3// Cayley table representation: order n, table[i*n + j] = product i*j
4// where elements are labeled 0..n-1. Identity element conventionally 0.
5//
6// genealogy_id: galois_1832 + cayley_1854 + lagrange_1771
7// lineage_id: algebra_associativity + identity + inverse + closure
8// axioms: NX_AX_ALG_ASSOCIATIVITY, NX_AX_ALG_IDENTITY_ELEMENT,
9// NX_AX_ALG_INVERSE_ELEMENT, NX_AX_ALG_CLOSURE
10
11// nx_safety_envelope:
12// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
13// sil_target: SIL1
14// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
15// verdict: NOT_YET_EVALUATED
16
17import "syscalls.nx"
18import "nx_axioms.nx"
19
20// Verify Cayley table satisfies group axioms.
21// closure: every entry is in 0..n-1
22// identity: 0 * x = x and x * 0 = x for all x
23// inverse: every x has some y with x * y = 0
24// associativity: (a*b)*c == a*(b*c)
25func nx_group_verify_axioms(table: *i64, n: i64) -> i64 {
26 if n <= 0 { return 0 }
27 // Closure + identity
28 var i: i64 = 0
29 while i < n {
30 if table[0 * n + i] != i { return 0 } // 0*i = i (left identity)
31 if table[i * n + 0] != i { return 0 } // i*0 = i (right identity)
32 var j: i64 = 0
33 while j < n {
34 let p: i64 = table[i * n + j]
35 if p < 0 { return 0 }
36 if p >= n { return 0 }
37 j = j + 1
38 }
39 i = i + 1
40 }
41 // Inverse
42 i = 0
43 while i < n {
44 var found: i64 = 0
45 var j: i64 = 0
46 while j < n {
47 if table[i * n + j] == 0 { found = 1 }
48 j = j + 1
49 }
50 if found == 0 { return 0 }
51 i = i + 1
52 }
53 // Associativity (n^3 check)
54 var a: i64 = 0
55 while a < n {
56 var b: i64 = 0
57 while b < n {
58 var c: i64 = 0
59 while c < n {
60 let lhs: i64 = table[table[a * n + b] * n + c]
61 let rhs: i64 = table[a * n + table[b * n + c]]
62 if lhs != rhs { return 0 }
63 c = c + 1
64 }
65 b = b + 1
66 }
67 a = a + 1
68 }
69 return 1
70}
71
72// Order of element x in group.
73func nx_group_element_order(table: *i64, n: i64, x: i64) -> i64 {
74 if x == 0 { return 1 }
75 var cur: i64 = x
76 var ord: i64 = 1
77 while cur != 0 {
78 cur = table[cur * n + x]
79 ord = ord + 1
80 if ord > n { return -1 } // not a valid group
81 }
82 return ord
83}
84
85// Subgroup test: given a subset specified by membership array
86// (membership[i] = 1 iff element i is in subset), check closure under
87// the group operation. Identity is assumed in subset (caller verifies).
88func nx_group_is_subgroup(table: *i64, n: i64, member: *i64) -> i64 {
89 if member[0] != 1 { return 0 }
90 var i: i64 = 0
91 while i < n {
92 if member[i] == 1 {
93 var j: i64 = 0
94 while j < n {
95 if member[j] == 1 {
96 let p: i64 = table[i * n + j]
97 if member[p] != 1 { return 0 }
98 }
99 j = j + 1
100 }
101 }
102 i = i + 1
103 }
104 return 1
105}
106
107// Count elements of order p in the group (for Sylow).
108func nx_group_count_order_p_elements(table: *i64, n: i64, p: i64) -> i64 {
109 var count: i64 = 0
110 var i: i64 = 0
111 while i < n {
112 if nx_group_element_order(table, n, i) == p { count = count + 1 }
113 i = i + 1
114 }
115 return count
116}