Group — symmetry, cyclic group আর Lagrange-এর উপপাদ্য

১ · Symmetry থেকে group — binary operation আর চারটি axiom

অপারেশন যোগ হলে আমরা a + b, একক 0 আর inverse −a লিখি; গুণ হলে ab, একক 1 আর a⁻¹. সাধারণ আলোচনায় গুণের লেখাই চলে। কয়েকটি পরিচিত সেট-অপারেশন জোড়া যাচাই করা যাক:

শেষ সারির সেটটি এই পর্বের প্রধান উদাহরণ। পর্ব ২২-এর ℤ_n = {0, 1, …, n − 1} থেকে শুধু n-এর সঙ্গে সহমৌলিক সংখ্যাগুলো নিন:

ℤ_n^* = { a : 1 ≤ a ≤ n − 1, gcd(a, n) = 1 }, |ℤ_n^*| = φ(n).

এখানে φ হলো পর্ব ২৪-এর Euler-এর totient. একে n-এর unit group বলে, কারণ এর উপাদানগুলোই mod n-এ উল্টানো যায়। এটি group কেন: (১) gcd(a, n) = gcd(b, n) = 1 হলে gcd(ab, n) = 1, কারণ n-এর কোনো মৌলিক উৎপাদক ab-কে ভাগ করলে a বা b-কে ভাগ করত (Euclid-এর lemma), তাই closure আছে; (২) সাধারণ গুণের সংযোজন নিয়ম mod n-এও খাটে; (৩) একক 1; (৪) gcd(a, n) = 1 বলে Bézout থেকে ax + ny = 1, তাই x mod n হলো a-এর modular inverse (পর্ব ২১), আর x-ও n-এর সঙ্গে সহমৌলিক। ∎ যেমন ℤ₉^* = {1, 2, 4, 5, 7, 8}, আকার φ(9) = 6.

২ · প্রথম উপপাদ্যগুলো — একক, inverse আর cancellation

Axiom থেকে প্রথম যে ফলগুলো আসে, সেগুলো দেখতে নিরীহ, কিন্তু পরের প্রতিটি প্রমাণ এদের ওপর দাঁড়িয়ে। প্রতিটি শুধু চারটি axiom ব্যবহার করে, তাই যেকোনো group-এ খাটে।

1. (ক) ধরুন e আর e′ দুটিই একক। e ∗ e′ = e′, কারণ e একক; আবার e ∗ e′ = e, কারণ e′ একক। তাই e = e′. — এককের সংজ্ঞা দুবার
2. (খ) ধরুন b আর c দুটিই a-এর inverse. তাহলে b = b ∗ e = b ∗ (a ∗ c) = (b ∗ a) ∗ c = e ∗ c = c. — একক, inverse, সংযোজন নিয়ম
3. দুই ক্ষেত্রেই “দুটি” বলে যা ধরেছিলাম, তারা আসলে একই উপাদান। ∎

এর একটি ফল: (ab)⁻¹ = b⁻¹a⁻¹, কারণ (ab)(b⁻¹a⁻¹) = a(bb⁻¹)a⁻¹ = aa⁻¹ = e, আর inverse অনন্য। ক্রম উল্টে যায়, ঠিক যেমন আগে মোজা তারপর জুতা পরলে খোলার সময় আগে জুতা, তারপর মোজা।

1. ab = ac-এর দুই দিকে বাঁ থেকে a⁻¹ গুণ করুন: a⁻¹(ab) = a⁻¹(ac). — inverse আছে
2. সংযোজন নিয়মে (a⁻¹a)b = (a⁻¹a)c, অর্থাৎ eb = ec, তাই b = c. ডান দিকের ক্ষেত্রে ডান থেকে গুণ করুন। ∎ — সংযোজন, একক

সাধারণ পূর্ণসংখ্যার গুণে কাটাকাটি সবসময় চলে না: mod 6-এ 2 · 1 ≡ 2 · 4 ≡ 2, অথচ 1 ≠ 4. কারণ 2-এর mod 6-এ কোনো inverse নেই, অর্থাৎ ({0, …, 5}, × mod 6) group নয় (পর্ব ২২-এর সতর্কতা এখানে উপপাদ্যের ভাষা পেল)।

1. a সারিতে দুটি ঘরে একই উপাদান থাকলে ab = ac, যেখানে b ≠ c. Cancellation বলে b = c, বিরোধ। তাই সারির |G|টি ঘরে সব উপাদান আলাদা। — উপপাদ্য ২.২
2. |G|টি আলাদা উপাদান, আর G-তে মোট |G|টি উপাদান, তাই প্রতিটি উপাদান ঠিক একবার। — পর্ব ৩২-এর গণনা
3. কলামের জন্য ba = ca থেকে একই যুক্তি। ∎

উল্টোটা সত্য নয়: Latin square হলেই group হয় না, কারণ টেবিল দেখে সংযোজন নিয়ম বোঝা যায় না। তাই নিচের কোড চারটি শর্তই আলাদা করে পরীক্ষা করে, সংযোজন নিয়মের জন্য সব |G|³টি ত্রয়ী। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from math import gcd
def check_group(G, op):
    G = list(G)
    if any(op(a, b) not in G for a in G for b in G):
        return "not closed"
    if any(op(op(a, b), c) != op(a, op(b, c)) for a in G for b in G for c in G):
        return "not associative"
    ids = [e for e in G if all(op(e, a) == a == op(a, e) for a in G)]
    if not ids:
        return "no identity"
    e = ids[0]
    if any(all(op(a, b) != e for b in G) for a in G):
        return "some element has no inverse"
    rows_ok = all(sorted(op(a, b) for b in G) == sorted(G) for a in G)
    return f"group, identity {e}, Latin square: {rows_ok}"
tests = {
    "Z6, + mod 6": (range(6), lambda a, b: (a + b) % 6),
    "Z9*, x mod 9": ([a for a in range(1, 9) if gcd(a, 9) == 1],
                     lambda a, b: a * b % 9),
    "{1..5}, x mod 6": (range(1, 6), lambda a, b: a * b % 6),
    "Z5, - mod 5": (range(5), lambda a, b: (a - b) % 5),
    "Z6, x mod 6": (range(6), lambda a, b: a * b % 6),
}
for name, (G, op) in tests.items():
    print(f"{name:16} -> {check_group(G, op)}")
U9 = [a for a in range(1, 9) if gcd(a, 9) == 1]
print("Z9* =", U9)
for a in U9:
    print(a, [a * b % 9 for b in U9])

Z6, + mod 6      -> group, identity 0, Latin square: True
Z9*, x mod 9     -> group, identity 1, Latin square: True
{1..5}, x mod 6  -> not closed
Z5, - mod 5      -> not associative
Z6, x mod 6      -> some element has no inverse
Z9* = [1, 2, 4, 5, 7, 8]
1 [1, 2, 4, 5, 7, 8]
2 [2, 4, 8, 1, 5, 7]
4 [4, 8, 7, 2, 1, 5]
5 [5, 1, 2, 7, 8, 4]
7 [7, 5, 1, 8, 4, 2]
8 [8, 7, 5, 4, 2, 1]

৩ · তিনটি পরিবার — ℤ_n, বর্গের symmetry আর permutation

সসীম group-এর তিনটি পরিবার বারবার ফিরে আসে। প্রথমটি দেখেছেন: ℤ_n (যোগ) আর ℤ_n^* (গুণ), দুটিই abelian.

দ্বিতীয়: dihedral group. একটি বর্গকে তার জায়গায় ফিরিয়ে আনে এমন নড়াচড়া ৮টি: 0°, 90°, 180°, 270° ঘোরানো আর চারটি অক্ষ বরাবর উল্টানো। দুটি পরপর করাই অপারেশন। পর্ব ৫১-এ দেখেছেন এরা একটি group D₄, আর সাধারণভাবে নিয়মিত n-ভুজের D_n-এর আকার 2n. এটি abelian নয়: আগে 90° ঘুরিয়ে তারপর উল্লম্ব অক্ষে উল্টানো আর আগে উল্টে তারপর ঘোরানো আলাদা ফল দেয়। ঘোরানো r আর একটি উল্টানো s হলে সম্পর্কটি sr = r⁻¹s.

তৃতীয়: symmetric group S_n. {1, …, n}-এর সব permutation, অর্থাৎ নিজের ওপর সব bijection, অপারেশন composition (পর্ব ১৬)। দুটি bijection-এর composition আবার bijection (closure), ফাংশনের composition সবসময় সংযোজনীয়, একক হলো identity ফাংশন, আর inverse হলো উল্টো ফাংশন। আকার n!. Permutation-কে cycle-এ লেখা হয় (পর্ব ৫০): (1 2 3) মানে 1 → 2, 2 → 3, 3 → 1.

S₃-এ r = (1 2 3) আর s = (2 3) নিন। “আগে s, তারপর r” করলে 1 → 1 → 2, 2 → 3 → 1, 3 → 2 → 3, অর্থাৎ (1 2). “আগে r, তারপর s” করলে 1 → 2 → 3, 2 → 3 → 2, 3 → 1 → 1, অর্থাৎ (1 3). ফল আলাদা, তাই S₃ abelian নয়। আকার 6, আর এটিই সবচেয়ে ছোট non-abelian group (৫ বা তার কম আকারের প্রতিটি group abelian; এর প্রমাণ এই পর্বের Lagrange থেকে কিছুটা আসে, পুরোটা এখানে বাদ)। বাজারঘরের ভাষায়: একটি প্যাকেট আগে উল্টে তারপর ঘোরানো আর আগে ঘুরিয়ে তারপর উল্টানো এক জিনিস নয়, তাই গুদামের রোবটকে নির্দেশের ক্রম ঠিক রাখতে হয়।

৪ · Order, cyclic group আর generator

a^k মানে a-কে k বার নিজের সঙ্গে গুণ (a⁰ = e, a^−k = (a⁻¹)^k); যোগের group-এ একই জিনিসকে ka লেখা হয়। সাধারণ ঘাতের নিয়ম a^ma^k = a^m+k আর (a^m)^k = a^mk সংযোজন নিয়ম থেকেই আসে।

1. (ক) a, a², a³, … সবাই সসীম G-তে, তাই কোনো i < j-তে aⁱ = a^j. দুই দিকে a⁻ⁱ গুণ করলে a^j−i = e, আর j − i ধনাত্মক। — pigeonhole
2. (খ) m = qd + r লিখুন, 0 ≤ r < d (পর্ব ২০-এর division algorithm). a^m = (a^d)^qa^r = a^r. তাই a^m = e ⇔ a^r = e ⇔ r = 0, কারণ d-এর চেয়ে ছোট কোনো ধনাত্মক ঘাতে e আসে না। — ভাগশেষ
3. (গ) 0 ≤ i < j ≤ d − 1-এ aⁱ = a^j হলে a^j−i = e, অথচ 0 < j − i < d: order-এর সংজ্ঞার বিরোধ। ∎

(ℤ, +) cyclic, generator 1 আর −1. ℤ_n cyclic, generator 1. প্রতিটি cyclic group abelian, কারণ gⁱg^j = g^i+j = g^jgⁱ. কিন্তু প্রতিটি abelian group cyclic নয়: ℤ₈^* = {1, 3, 5, 7}-এ 3² = 9 ≡ 1, 5² = 25 ≡ 1, 7² = 49 ≡ 1. কোনো উপাদানের order 4 নয়, তাই কোনো generator নেই। ℤ_n-এর কোন উপাদান generator, তার একটি পরিষ্কার উত্তর আছে।

1. d = gcd(k, n). যোগের group-এ “k-এর m-গুণ = 0” মানে n ∣ mk. — ℤ_n-এ শূন্য
2. n ∣ mk ⇔ (n/d) ∣ m(k/d), আর gcd(n/d, k/d) = 1, তাই ⇔ (n/d) ∣ m. — Euclid-এর lemma, পর্ব ২১
3. সবচেয়ে ছোট ধনাত্মক এমন m হলো n/d, তাই ord(k) = n/d. — সংজ্ঞা ৪.১
4. k generator ⇔ ord(k) = n ⇔ d = 1. 0 থেকে n − 1-এর মধ্যে এমন k ঠিক φ(n)টি। ∎ — সংজ্ঞা ৪.৩

ℤ₁₂-এ generator 1, 5, 7, 11 (φ(12) = 4), আর যেমন ord(8) = 12/gcd(8, 12) = 3: 8, 16 ≡ 4, 24 ≡ 0. গুণের group-এ উত্তরটি কঠিন। পর্ব ২৪-এ দেখেছেন মৌলিক p-এ ℤ_p^*-এর সবসময় একটি primitive root আছে, অর্থাৎ ℤ_p^* cyclic; সেই প্রমাণ এখানে বাদ। কিন্তু কোনটি generator, তার কোনো সরল সূত্র জানা নেই; ঘাত গুনে দেখতে হয়। নিচের stepper সবচেয়ে ছোট উদাহরণে দুটি কাজই করে।

1G = {1, 2, 3, 4}, ab mod 52সারি 1: 1·b3সারি 2: 2·b4সারি 3: 3·b5সারি 4: 4·b64-এর ঘাত72 আর 3-এর ঘাত

৫ · Subgroup — group-এর ভেতরের group

⟨a⟩ সবসময় একটি subgroup, একে a-এর তৈরি cyclic subgroup বলে। ℤ₁₂-এ ⟨4⟩ = {0, 4, 8}, ℤ₅^*-এ ⟨4⟩ = {1, 4}. চারটি axiom আবার একে একে না দেখে subgroup চেনার একটি সংক্ষিপ্ত পরীক্ষা আছে।

1. (ক) সংযোজন নিয়ম G-তে সব উপাদানে খাটে, তাই H-এর উপাদানেও। Closure ধরে নেওয়া আছে। — উত্তরাধিকার
2. H অশূন্য, তাই কোনো a ∈ H আছে; a⁻¹ ∈ H, আর closure থেকে aa⁻¹ = e ∈ H. Inverse শর্তে ধরা আছে, তাই H একটি group. — একক H-এ আছে
3. (খ) a ∈ H হলে closure থেকে a, a², a³, … সবাই H-এ। G সসীম, তাই d = ord(a) সসীম (উপপাদ্য ৪.২)। d = 1 হলে a = e = a⁻¹. নইলে a⁻¹ = a^d−1, কারণ a · a^d−1 = a^d = e, আর a^d−1 ∈ H. তাই inverse শর্ত আপনা থেকেই মেলে, আর (ক) প্রযোজ্য। ∎ — ঘাতের চক্র

(খ)-তে “সসীম” শর্তটি বাদ দেওয়া যায় না: (ℤ, +)-এ ℕ = {0, 1, 2, …} অশূন্য আর যোগে বদ্ধ, অথচ subgroup নয়, কারণ 1-এর inverse −1 নেই। অসীম group-এ তাই inverse-এর শর্ত আলাদা করে দেখতে হয়।

ℤ₁₂-এর subgroup কয়টি? প্রতিটি d ∣ 12-এর জন্য ⟨d⟩, অর্থাৎ ছয়টি: ⟨1⟩, ⟨2⟩, ⟨3⟩, ⟨4⟩, ⟨6⟩, ⟨0⟩ = {0}, আকার 12, 6, 4, 3, 2, 1. আর কোনো subgroup নেই, কারণ cyclic group-এর প্রতিটি subgroup cyclic: H ≠ {0} হলে H-এর সবচেয়ে ছোট ধনাত্মক উপাদান m নিন; H-এর যেকোনো x-কে x = qm + r লিখলে r = x − qm ∈ H আর 0 ≤ r < m, তাই r = 0, অর্থাৎ H = ⟨m⟩. প্রতিটি আকার 12-এর একটি ভাজক। এটাই পরের অংশের বড় উপপাদ্যের পূর্বাভাস।

৬ · Coset আর Lagrange-এর উপপাদ্য

ধারণাটি একটি ছবিতে ধরা যায়। ℤ₁₂-কে ঘড়ির ১২টি ঘর ভাবুন, আর H = ⟨4⟩ = {0, 4, 8}. H-এর তিনটি ঘর একটি সমবাহু ত্রিভুজ। এই ত্রিভুজকে এক ঘর ঘোরালে {1, 5, 9}, দুই ঘর ঘোরালে {2, 6, 10}, তিন ঘর ঘোরালে {3, 7, 11}. চারটি ত্রিভুজ মিলে ঘড়ির ১২টি ঘর ঠিক একবার করে ঢাকে।

Coset আসলে একটি equivalence relation-এর class (পর্ব ৫৫)। G-তে a ~ b বলুন, যদি a⁻¹b ∈ H. (১) Reflexive: a⁻¹a = e ∈ H. (২) Symmetric: a⁻¹b ∈ H হলে তার inverse b⁻¹a ∈ H. (৩) Transitive: a⁻¹b আর b⁻¹c দুটিই H-এ থাকলে গুণফল a⁻¹c ∈ H. আর b ~ a ⇔ a⁻¹b = h কোনো h ∈ H-এর জন্য ⇔ b = ah ⇔ b ∈ aH. তাই a-এর equivalence class ঠিক aH. পর্ব ৫৫-এর মৌলিক উপপাদ্য বলে class-গুলো G-এর একটি partition: দুটি coset হয় হুবহু এক, নয়তো সম্পূর্ণ আলাদা। ℤ_n-এ H = ⟨d⟩ হলে a ~ b মানে b − a ∈ ⟨d⟩, অর্থাৎ a ≡ b (mod d): coset-গুলো mod d-এর ভাগশেষ-শ্রেণি।

1. বাম coset-গুলো G-এর একটি partition, কারণ এগুলো ~-এর equivalence class. — পর্ব ৫৫
2. প্রতিটি coset aH-এর আকার |H|: ফাংশন f(h) = ah, H থেকে aH-এ, সংজ্ঞা অনুযায়ী onto; আর ah = ah′ হলে cancellation থেকে h = h′, তাই one-to-one. Bijection, তাই |aH| = |H|. — উপপাদ্য ২.২, পর্ব ১৬
3. G হলো [G : H]টি পরস্পর-বিচ্ছিন্ন সেটের union, প্রতিটির আকার |H|. যোগের নিয়মে |G| = [G : H] · |H|. ∎ — পর্ব ৩১-এর যোগের নিয়ম

প্রমাণটি তিনটি পুরোনো হাতিয়ার জোড়া দেয়: equivalence class-এর partition, cancellation থেকে bijection, আর যোগের নিয়ম। প্রথম stepper ঘড়ির ছবিটি ধাপে ধাপে বানায়, দ্বিতীয়টি একই প্রমাণ গুণের একটি group-এ চালায়।

1H = ⟨4⟩ = {0, 4, 8}21 + H32 + H43 + H54 + H, 5 + H ?612 = 4 × 3

1H = ⟨3⟩ = {1, 3, 9}22H34H47H5h → 2h: bijection612 = 4 × 3

নিচের কোড ℤ₁₂-এর সব 2¹² = 4096টি উপসেটে উপপাদ্য ৫.২(খ) চালিয়ে subgroup খোঁজে, coset গোনে, তারপর ℤ₁₃^*-এ order, generator আর Lagrange মেলায়।

from itertools import combinations
from math import gcd
n = 12
def is_subgroup(H):                      # finite test: nonempty and closed
    return 0 in H and all((a + b) % n in H for a in H for b in H)
subs = [set(H) for k in range(1, n + 1)
        for H in combinations(range(n), k) if is_subgroup(set(H))]
print("Z12 has", len(subs), "subgroups (checked all 4096 subsets):")
for H in subs:
    d = min(H - {0}, default=n)          # smallest positive element
    print(f"  size {len(H):2}  = <{d % n}>  {sorted(H)}  12/size = {n // len(H)}")
def cosets(G, H, op):
    left, out = list(G), []
    while left:
        c = sorted({op(left[0], h) for h in H})
        out.append(c); left = [x for x in left if x not in c]
    return out
H = {0, 4, 8}
print("cosets of <4>:", cosets(range(12), H, lambda a, h: (a + h) % 12))
p = 13
U = list(range(1, p))
def order(a):
    k, x = 1, a
    while x != 1:
        x, k = x * a % p, k + 1
    return k
print("orders in Z13*:", {a: order(a) for a in U})
print("generators:", [a for a in U if order(a) == p - 1])
H = {pow(3, k, p) for k in range(3)}
C = cosets(U, H, lambda a, h: a * h % p)
print("cosets of <3> =", sorted(H), ":", C)
print("Lagrange:", len(U), "=", len(C), "x", len(H))
print("a^12 = 1 for all a:", all(pow(a, 12, p) == 1 for a in U))

Z12 has 6 subgroups (checked all 4096 subsets):
  size  1  = <0>  [0]  12/size = 12
  size  2  = <6>  [0, 6]  12/size = 6
  size  3  = <4>  [0, 4, 8]  12/size = 4
  size  4  = <3>  [0, 3, 6, 9]  12/size = 3
  size  6  = <2>  [0, 2, 4, 6, 8, 10]  12/size = 2
  size 12  = <1>  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]  12/size = 1
cosets of <4>: [[0, 4, 8], [1, 5, 9], [2, 6, 10], [3, 7, 11]]
orders in Z13*: {1: 1, 2: 12, 3: 3, 4: 6, 5: 4, 6: 12, 7: 12, 8: 4, 9: 3, 10: 6, 11: 12, 12: 2}
generators: [2, 6, 7, 11]
cosets of <3> = [1, 3, 9] : [[1, 3, 9], [2, 5, 6], [4, 10, 12], [7, 8, 11]]
Lagrange: 12 = 4 x 3
a^12 = 1 for all a: True

৭ · Lagrange-এর ফল — Fermat, Euler আর মৌলিক আকারের group

Lagrange-এর আসল শক্তি তার ফলগুলোয়। G সসীম, |G| = n, আর a ∈ G যেকোনো উপাদান।

প্রমাণ: ⟨a⟩ একটি subgroup আর তার আকার ord(a) (উপপাদ্য ৪.২-এর গ), তাই Lagrange থেকে ord(a) ∣ n. n = ord(a) · m লিখলে aⁿ = (a^ord(a))^m = e^m = e. ∎

প্রমাণ: a mod n হলো ℤ_n^*-এর উপাদান, আর |ℤ_n^*| = φ(n). ফল ৭.১(খ) প্রয়োগ করুন। p মৌলিক হলে φ(p) = p − 1. ∎ পর্ব ২৪-এ এই দুটি উপপাদ্য গুণফল সাজিয়ে আলাদা করে প্রমাণ করেছিলেন, আর “order ভাগ করে φ(n)-কে”ও আলাদা উপপাদ্য ছিল। Group-এর দৃষ্টিতে তিনটিই একটি সাধারণ সত্যের বিশেষ রূপ: সংখ্যাতত্ত্বের কৌশল আসলে ℤ_n^* নামের একটি group-এর গঠন।

1. a ≠ e নিন। ord(a) ∣ p, তাই ord(a) = 1 বা p. — ফল ৭.১
2. ord(a) = 1 মানে a = e, যা বাদ। তাই ord(a) = p = |G|, অর্থাৎ ⟨a⟩ = G. ∎ — সংজ্ঞা ৪.৩

অর্থাৎ ৫, ৭ বা ১৩ আকারের group গঠনে একটিই: ℤ_p-এর মতো (§৮-এ isomorphism-এর ভাষায়)। আরেকটি ফল: মৌলিক আকারের group-এর subgroup শুধু {e} আর G.

উল্টোটা কি সত্য? d ∣ |G| হলেই কি d আকারের subgroup আছে? Cyclic group-এ হ্যাঁ: প্রতিটি d ∣ n-এর জন্য ℤ_n-এ ঠিক একটি, ⟨n/d⟩. সাধারণভাবে না। সবচেয়ে ছোট পাল্টা-উদাহরণ alternating group A₄: S₄-এর জোড় permutation-গুলো, আকার 12, অথচ তার কোনো 6 আকারের subgroup নেই। তবে মৌলিক ভাজকে আংশিক উল্টোটা সত্য: Cauchy-র উপপাদ্য বলে মৌলিক p ∣ |G| হলে p order-এর একটি উপাদান আছে (প্রমাণ এখানে বাদ)।

নিচের কোড S₄-এর ২৪টি permutation-কে cycle type অনুযায়ী ভাগ করে। Order হলো cycle-গুলোর দৈর্ঘ্যের lcm: দৈর্ঘ্য 2 আর 3-এর দুটি আলাদা cycle থাকলে 6 বার পরে দুটিই একসঙ্গে শুরুর অবস্থায় ফেরে (পর্ব ৫০-এর cycle). তারপর A₄-এর পাল্টা-উদাহরণটি ব্রুট ফোর্সে যাচাই করে।

from itertools import permutations, combinations
from collections import Counter
from math import lcm
def cycles(p):                           # p[i] = image of i
    seen, out = set(), []
    for i in range(len(p)):
        if i not in seen:
            c, j = [], i
            while j not in seen:
                seen.add(j); c.append(j); j = p[j]
            out.append(len(c))
    return tuple(sorted(out, reverse=True))
def compose(p, q):                       # first q, then p
    return tuple(p[q[i]] for i in range(len(q)))
S4 = list(permutations(range(4)))
table = Counter(cycles(p) for p in S4)
print("cycle type   count  order")
for t, c in sorted(table.items(), key=lambda kv: -kv[1]):
    print(f"{str(t):12} {c:5}  {lcm(*t):5}")
orders = Counter(lcm(*cycles(p)) for p in S4)
print("orders:", dict(sorted(orders.items())), "| all divide 24:",
      all(24 % o == 0 for o in orders))
r, s = (1, 2, 0, 3), (0, 2, 1, 3)        # a 3-cycle and a swap
print("r then s:", compose(s, r), " s then r:", compose(r, s))
even = [p for p in S4 if sum(L - 1 for L in cycles(p)) % 2 == 0]
e = tuple(range(4))
found = 0
for rest in combinations([p for p in even if p != e], 5):
    H = set(rest) | {e}
    if all(compose(a, b) in H for a in H for b in H):
        found += 1
print("A4 has", len(even), "elements; subgroups of order 6:", found)

cycle type   count  order
(3, 1)           8      3
(2, 1, 1)        6      2
(4,)             6      4
(2, 2)           3      2
(1, 1, 1, 1)     1      1
orders: {1: 1, 2: 9, 3: 8, 4: 6} | all divide 24: True
r then s: (2, 1, 0, 3)  s then r: (1, 0, 2, 3)
A4 has 12 elements; subgroups of order 6: 0

৮ · Homomorphism, isomorphism আর প্রয়োগ

ℤ₅^*-এর Cayley table আর ℤ₄-এর যোগের table দেখতে আলাদা, কিন্তু 2^k ↔ k জোড়া মেলালে একটি অন্যটির হুবহু অনুবাদ। এই “গঠন-রক্ষাকারী অনুবাদ”-এর নাম homomorphism.

1. f(e_G) = f(e_Ge_G) = f(e_G)f(e_G); K-তে cancellation করলে f(e_G) = e_K. — উপপাদ্য ২.২
2. f(a)f(a⁻¹) = f(aa⁻¹) = e_K, তাই f(a⁻¹) = f(a)⁻¹. — inverse অনন্য
3. ker f একটি subgroup: e ∈ ker f; a, b ∈ ker f হলে f(ab) = e_Ke_K = e_K আর f(a⁻¹) = e_K⁻¹ = e_K; উপপাদ্য ৫.২(ক) প্রয়োগ করুন। ∎ — subgroup test

উদাহরণ: f: ℤ₁₂ → ℤ₄, f(x) = x mod 4. 4 ∣ 12 বলে mod 12-এ যোগ করে তারপর mod 4 নেওয়া আর সরাসরি mod 4-এ যোগ করা এক, তাই f একটি homomorphism; ker f = {0, 4, 8} = ⟨4⟩, §৬-এর সেই subgroup, আর f-এর একই মানের উপাদানগুলো ঠিক তার coset. কিন্তু x ↦ x mod 5 ℤ₁₂ থেকে homomorphism নয়: 7 + 5 = 12 ≡ 0, অথচ 2 + 0 = 2 ≢ 0 (mod 5).

প্রমাণের রূপরেখা: (১) f সুসংজ্ঞায়িত (well-defined): k ≡ k′ (mod n) হলে n ∣ k − k′, আর ord(g) = n, তাই উপপাদ্য ৪.২(খ) থেকে g^k−k′ = e, অর্থাৎ g^k = g^k′. (২) Homomorphism: f(k + m) = g^k+m = g^kg^m. (৩) Bijection: g⁰, …, gⁿ⁻¹ সব আলাদা (উপপাদ্য ৪.২-এর গ) আর এরাই পুরো G. ∎ তাই ℤ₁₃^* ≅ ℤ₁₂, আর ℤ₁₃^*-এর generator হলো g^k, যেখানে k ℤ₁₂-এর generator: উপপাদ্য ৪.৪ অনুযায়ী ঠিক φ(12) = 4টি, §৬-এর কোড যা পেয়েছিল। Isomorphism order রক্ষা করে, তাই ℤ₈^* (সব order ≤ 2) ℤ₄-এর isomorphic হতে পারে না। ℤ₈^*-এর গঠনের group-কে Klein four-group বলে।

from itertools import permutations
def is_hom(f, G, H, opG, opH):           # f(a*b) = f(a)*f(b) for all a, b
    return all(f[opG(a, b)] == opH(f[a], f[b]) for a in G for b in G)
Z4 = range(4)
add4 = lambda a, b: (a + b) % 4
U5 = [1, 2, 3, 4]; mul5 = lambda a, b: a * b % 5
isos = []
for img in permutations(U5):             # every bijection Z4 -> Z5*
    f = dict(zip(Z4, img))
    if is_hom(f, Z4, U5, add4, mul5):
        isos.append(img)
print("isomorphisms Z4 -> Z5*:", isos)
print("rule k -> 2^k mod 5:", tuple(pow(2, k, 5) for k in Z4))
def orders(G, op, e):
    out = []
    for a in G:
        k, x = 1, a
        while x != e:
            x, k = op(x, a), k + 1
        out.append(k)
    return sorted(out)
U8 = [1, 3, 5, 7]
print("orders in Z4 :", orders(Z4, add4, 0))
print("orders in Z8*:", orders(U8, lambda a, b: a * b % 8, 1))
f = {x: x % 4 for x in range(12)}         # Z12 -> Z4, reduce mod 4
print("x mod 4 is a homomorphism:",
      is_hom(f, range(12), Z4, lambda a, b: (a + b) % 12, add4))
ker = [x for x in range(12) if f[x] == 0]
print("kernel:", ker, " image size:", len(set(f.values())),
      " 12 / |kernel| =", 12 // len(ker))
g = {x: x % 5 for x in range(12)}
print("x mod 5 from Z12 is a homomorphism:",
      is_hom(g, range(12), range(5), lambda a, b: (a + b) % 12,
             lambda a, b: (a + b) % 5))

isomorphisms Z4 -> Z5*: [(1, 2, 4, 3), (1, 3, 4, 2)]
rule k -> 2^k mod 5: (1, 2, 4, 3)
orders in Z4 : [1, 2, 4, 4]
orders in Z8*: [1, 2, 2, 2]
x mod 4 is a homomorphism: True
kernel: [0, 4, 8]  image size: 4  12 / |kernel| = 4
x mod 5 from Z12 is a homomorphism: False

প্রয়োগ: key exchange, check digit আর symmetry

Diffie–Hellman: পর্ব ২৯-এর key exchange একটি cyclic group ⟨g⟩-এর ওপর চলে। Lagrange সেখানে নিরাপত্তার নকশা ঠিক করে: ℤ_p^*-এর subgroup-এর আকার শুধু p − 1-এর ভাজক হতে পারে, আর p − 1-এর ছোট ভাজক থাকলে আক্রমণকারী ছোট subgroup-এ সমস্যাটি টুকরো করে সমাধান করতে পারে (পর্ব ২৯-এর Pohlig–Hellman). তাই বাস্তবের নকশা বড় মৌলিক আকারের subgroup বেছে নেয়। ছোট সংখ্যার “textbook” Diffie–Hellman শুধু বোঝার জন্য; আসল ব্যবস্থায় বড় মানসম্মত parameter আর যাচাই-করা library লাগে (সাইবার সিকিউরিটি কোর্সের পর্ব ১০)।

Check digit: পর্ব ২৬-এর mod 10 পদ্ধতিগুলো abelian group-এ চলে, আর সেখানে কিছু পাশাপাশি অদলবদল (transposition error) ধরা পড়ে না। J. Verhoeff ১৯৬৯ সালে non-abelian dihedral group D₅ (আকার 10, তাই দশটি অঙ্কের জন্য উপযুক্ত) আর একটি অবস্থান-নির্ভর permutation ব্যবহার করে এমন পদ্ধতি দেন, যা সব একক-অঙ্কের ভুল আর সব পাশাপাশি অদলবদল ধরে বলে বর্ণিত। আমাদের scratch-এ একটি বাস্তবায়নে চার অঙ্কের সব ১০,০০০টি payload-এ পরীক্ষা করে একটিও ভুল ফসকায়নি; তবে আসল ব্যবহারের আগে মূল টেবিল প্রকাশিত উৎসে মিলিয়ে নিন।

Symmetry: Rubik's cube-এর সব বৈধ অবস্থা একটি group গঠন করে, যার আকার 43,252,003,274,489,856,000 বলে সুপরিচিত (প্রায় 4.3 × 10¹⁹; আমাদের scratch-এ 8! · 3⁷ · 12! · 2¹¹ / 2 সূত্রে মেলানো)। অণুর symmetry, স্ফটিকের গঠন আর কম্পিউটার গ্রাফিক্সে ঘোরানোর হিসাবও group-এর ভাষায় লেখা হয়।

৯ · পরীক্ষার অঙ্ক আর একটি ভুল প্রমাণ

অঙ্ক ১: ℤ₇^*-এর order, generator আর subgroup

1. |ℤ₇^*| = 6, তাই Lagrange অনুযায়ী order শুধু 1, 2, 3, 6 হতে পারে।
2. ঘাত গুনে: ord(1) = 1, ord(2) = 3 (2, 4, 8 ≡ 1), ord(3) = 6, ord(4) = 3, ord(5) = 6, ord(6) = 2 (36 ≡ 1).
3. Generator 3 আর 5, সংখ্যায় φ(6) = 2, উপপাদ্য ৮.২ আর ৪.৪ মেনে। Subgroup: {1}, {1, 6}, {1, 2, 4}, পুরো group; আকার 1, 2, 3, 6 (scratch-এ যাচাই করা)।

অঙ্ক ২: 7²⁰²⁶ mod 15

1. gcd(7, 15) = 1, তাই 7 ∈ ℤ₁₅^*, যার আকার φ(15) = 8. ফল ৭.১: 7⁸ ≡ 1.
2. 2026 = 8 · 253 + 2, তাই 7²⁰²⁶ ≡ 7² = 49 ≡ 4 (mod 15). আসলে ord(7) = 4 (7, 4, 13, 1), তাতেও 2026 ≡ 2 (mod 4), একই উত্তর। Python-এর pow(7, 2026, 15) একই 4 দেয়।

অঙ্ক ৩: 15 আকারের group

(ক) এর subgroup কোন কোন আকারের হতে পারে? (খ) এতে কি 6 order-এর উপাদান থাকতে পারে?

1. (ক) Lagrange: শুধু 15-এর ভাজক, 1, 3, 5, 15.
2. (খ) না: ord(a) ∣ 15, আর 6 ∤ 15. ফলে কোনো 2 order-এর উপাদানও নেই, অর্থাৎ e ছাড়া কোনো উপাদান নিজের inverse নয়।

অঙ্ক ৪: বাজারঘরের ১৮ দিনের ডেলিভারি-চক্র

বাজারঘরের একটি ভ্যান ১৮টি এলাকা ঘুরে আবার শুরুতে ফেরে: এলাকাগুলো 0 থেকে 17, আর প্রতিদিন ভ্যানটি k ঘর সামনে এগোয় (ℤ₁₈-এ যোগ)। (ক) k = 12 হলে ভ্যানটি কয়টি এলাকায় যায়, আর কোনগুলোতে? (খ) কোন কোন k দিলে ভ্যানটি সব ১৮টি এলাকায় পৌঁছায়? (গ) k = 12-এর বেলায় যে এলাকাগুলো বাদ পড়ে, সেগুলো কয়টি আলাদা ভ্যান দিয়ে ঢাকা যায়, যদি প্রতিটি ভ্যান একই নিয়মে চলে কিন্তু আলাদা এলাকা থেকে শুরু করে?

1. (ক) উপপাদ্য ৪.৪: ord(12) = 18/gcd(12, 18) = 18/6 = 3. ভ্যানটি 0, 12, 24 ≡ 6, তারপর 18 ≡ 0-তে ফেরে: ⟨12⟩ = {0, 6, 12}.
2. (খ) সব এলাকা মানে k একটি generator ⇔ gcd(k, 18) = 1: k = 1, 5, 7, 11, 13, 17, মোট φ(18) = 6টি।
3. (গ) প্রতিটি ভ্যানের পথ ⟨12⟩-এর একটি coset, যেমন 1 থেকে শুরু করলে {1, 7, 13}. Lagrange: index 18/3 = 6, তাই শুরুর এলাকা 0, 1, 2, 3, 4, 5 নিয়ে ছয়টি ভ্যান সব এলাকা ঠিক একবার করে ঢাকে (scratch-এ যাচাই করা)।

প্রমাণের ভুল ধরুন: “Lagrange উল্টো দিকেও খাটে”

একজন লিখলেন: “A₄-এর আকার 12, আর 6 ∣ 12. Lagrange-এর উপপাদ্য অনুযায়ী subgroup-এর আকার |G|-এর ভাজক, তাই A₄-এর একটি 6 আকারের subgroup আছে।”

ভুল কোথায়: Lagrange বলে “H subgroup ⇒ |H| ∣ |G|”, কিন্তু যুক্তিটি ব্যবহার করেছে উল্টো দিক “d ∣ |G| ⇒ d আকারের subgroup আছে”, যা converse, আর তা সাধারণভাবে মিথ্যা। §৭-এর কোড A₄-এর সব ৪৬২টি প্রার্থী উপসেট দেখে একটিও subgroup পায়নি। সঠিক কথা: cyclic group-এ প্রতিটি ভাজকে subgroup আছে, আর মৌলিক ভাজকে Cauchy একটি উপাদান দেয়; এর বাইরে প্রতিটি দাবি আলাদা প্রমাণ চায়।

১০ · AI-এর যুগে — group-এর প্রমাণ আর হিসাব যাচাই

AI সহকারী group-এর সংজ্ঞা সাধারণত ঠিক বলে, কিন্তু প্রমাণে শর্ত বাদ দেয়, উল্টো দিক গুলিয়ে ফেলে আর mod-এর ঘাতে হিসাবের ভুল করে। কয়েকটি নিয়মিত ভুল আর ধরার উপায়:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• চারটি axiom (closure-সহ) আলাদা করে যাচাই হয়েছে, শুধু Latin square দেখে নয়
• প্রতিটি উপাদানের order |G|-কে ভাগ করে, আর ঘাত Python-এ মিলিয়েছি
• Lagrange শুধু “subgroup ⇒ ভাজক” দিকে ব্যবহার হয়েছে
• Subgroup test-এ অসীম group হলে inverse-এর শর্ত দেখা হয়েছে
• Non-abelian group-এ গুণের ক্রম স্থির, আর (ab)⁻¹ = b⁻¹a⁻¹
• ঐতিহাসিক নাম আর সাল বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

Group-এর দাবি যাচাই সাধারণত সহজ: ছোট group-এ সব উপাদান আর সব জোড়া ব্রুট ফোর্সে দেখা যায়। AI-এর একটি সাধারণ দাবি ১২ বা ২৪ উপাদানের group-এ পরীক্ষা করতে কয়েক মিলিসেকেন্ড লাগে, আর সেটাই প্রায়ই ভুল ধরার দ্রুততম পথ।