Functions — injection, surjection আর তথ্য হারানোর গণিত

f : ℤ → ℤ ক্ষেত্রে:

Injective — হ্যাঁ। 2a = 2b হলে a = b (২ দিয়ে ভাগ করে)।

Surjective — না। 3 কোনো x-এর জন্য 2x হতে পারে না (x = 1.5 পূর্ণসংখ্যা নয়)। বিজোড় সংখ্যাগুলো কেউ hit করে না।

Bijective — না।

f : ℤ → 2ℤ ক্ষেত্রে:

Codomain বদলে জোড় সংখ্যা করা হয়েছে। এখন:

Injective — হ্যাঁ (একই যুক্তি)। Surjective — হ্যাঁ। যেকোনো জোড় সংখ্যা 2k-এর জন্য x = k আছে। Bijective — হ্যাঁ, আর f⁻¹(y) = y/2।

একই সূত্র, ভিন্ন codomain, ভিন্ন উত্তর।

একটা মজার ফল: এই bijection প্রমাণ করে |ℤ| = |2ℤ| — পূর্ণসংখ্যা আর জোড় পূর্ণসংখ্যার “সংখ্যা” সমান, যদিও জোড়গুলো ℤ-এর একটা proper subset!

অসীম set-এ এটা স্বাভাবিক — একটা set তার নিজের proper subset-এর সাথে bijection-এ থাকতে পারে। আসলে এটাই অসীমের সংজ্ঞা (Dedekind-এর সংজ্ঞা)।

Hilbert’s Hotel-এর গল্পটা এই ধারণার জনপ্রিয় রূপ: অসীম কামরার হোটেল পূর্ণ থাকলেও নতুন অতিথিকে জায়গা দেওয়া যায় — সবাইকে এক কামরা সরিয়ে দিলেই হলো।

প্রোগ্রামিং-এ পাঠ: type signature-এ codomain লেখা থাকে, কিন্তু আসল range আলাদা হতে পারে। -> int লেখা থাকলেও function হয়তো শুধু জোড় সংখ্যা ফেরত দেয় — আর সেই তথ্যটা type-এ নেই।

অংশ ১ — f অবশ্যই injective।

Contrapositive প্রমাণ করি: f injective না হলে g ∘ f injective নয়।

f injective না হলে এমন a₁ ≠ a₂ আছে যে f(a₁) = f(a₂)।

তাহলে: $(g \circ f)(a_1) = g(f(a_1)) = g(f(a_2)) = (g \circ f)(a_2)$

দুইটা ভিন্ন input, একই output — তাই g ∘ f injective নয়। ∎

অংশ ২ — g injective না হয়েও চলে।

A = {1, 2}        B = {a, b, c}      C = {x, y}

f: 1 → a          g: a → x
   2 → b             b → y
                     c → y      ← g injective নয় (b, c দুটোই y-তে)

g ∘ f: 1 → x
       2 → y      ← injective ✓

g injective নয় (g(b) = g(c) = y), কিন্তু g ∘ f injective — কারণ c কখনো f-এর range-এ আসে না, তাই সেই collision-টা কখনো প্রকাশ পায় না।

মূল অন্তর্দৃষ্টি: g-কে শুধু f-এর range-এর উপর injective হতে হবে, পুরো domain-এর উপর নয়।

বাস্তব উদাহরণ:

def f(user_id: int) -> str:
    return f"user:{user_id}"          # injective

def g(key: str) -> int:
    return hash(key) % (2**32)        # injective নয় — collision আছে

g ∘ f বাস্তবে injective হতে পারে যদি আপনার সব user id-এর জন্য কোনো collision না ঘটে — যদিও g সাধারণভাবে injective নয়।

এটাই hash table কাজ করার কারণ: hash function সাধারণভাবে non-injective, কিন্তু আপনার নির্দিষ্ট key set-এর উপর প্রায় injective হতে পারে।

আর এটাই perfect hashing-এর ধারণা: key set জানা থাকলে এমন g বেছে নিন যা ঠিক সেই set-এর উপর injective।

যা দরকার — expand অবশ্যই একটা function হতে হবে।

অর্থাৎ প্রতিটা code ঠিক একটা URL-এ যাবে। এটা না হলে সিস্টেম অর্থহীন — একটা short link দুই জায়গায় নিয়ে যেতে পারে না।

সমতুল্যভাবে: shorten injective হতে হবে — দুইটা ভিন্ন URL কখনো একই code পাবে না।

যা দরকার নেই — surjective।

সব সম্ভাব্য code ব্যবহৃত হওয়ার দরকার নেই। বেশিরভাগ code খালি থাকবে, আর সেটাই স্বাভাবিক।

একটা নকশাগত পছন্দ — shorten কি deterministic হবে?

দৈর্ঘ্য নির্ধারণ — birthday bound দিয়ে।

Alphabet ৬২টা অক্ষর (a-zA-Z0-9)। n অক্ষরের code মানে 62ⁿ টা সম্ভাবনা।

Random code ব্যবহার করলে, k টা code বরাদ্দের পর collision-এর সম্ভাবনা প্রায়:

$P \approx 1 - e^{-k^2 / (2 \cdot 62^n)}$

সিদ্ধান্ত: ১০০ মিলিয়ন URL আশা করলে ৮ অক্ষর নিন, আর তার সাথে retry on collision রাখুন:

def shorten(url, max_tries=5):
    for _ in range(max_tries):
        code = random_code(8)
        if db.insert_if_absent(code, url):    # atomic
            return code
    raise RuntimeError("collision retry শেষ")

insert_if_absent atomic হতেই হবে — নাহলে দুইটা concurrent request একই code পেয়ে যেতে পারে (race condition)।

একটা অতিরিক্ত বিবেচনা — অনুমানযোগ্যতা।

Counter-ভিত্তিক code (1, 2, 3, … কে base62-তে) ছোট আর সুন্দর, কিন্তু কেউ পরপর code চেষ্টা করে সব link দেখে ফেলতে পারে। Private link-এর জন্য random অপরিহার্য।

মাঝামাঝি সমাধান: counter নিন, কিন্তু একটা bijective obfuscation প্রয়োগ করুন (যেমন Feistel network বা multiplicative inverse mod 62ⁿ)। তখন code এলোমেলো দেখায় কিন্তু collision গাণিতিকভাবে অসম্ভব — কারণ transformation-টা bijection।

Level 10-এ আমরা Feistel network দেখব।

Injective নয় (domain যদি 256-এর চেয়ে বড় হয়)।

f(0) = f(256) = f(512) = … = 0

Domain ℤ হলে প্রতিটা output-এ অসীম সংখ্যক input map হয়।

যেসব bug এটা তৈরি করে:

১. Integer truncation।

int  big  = 300;
char small = big;        // 300 % 256 = 44
printf("%d\n", small);   // 44

char -এ ৩০০ আঁটে না। তথ্য হারায় নীরবে — কোনো warning ছাড়া (-Wconversion না দিলে)।

২. Buffer size overflow।

uint8_t len = strlen(input);      // input যদি 300 byte হয়?
char buf[256];
memcpy(buf, input, len);          // len = 44, তাই এখানে নিরাপদ
// কিন্তু পরে কেউ যদি strlen(input) আবার ব্যবহার করে — mismatch

আরো খারাপ ক্ষেত্রে:

uint8_t n = user_count;           // 256 → 0
if (n > 0) { allocate(n); }       // কখনো চলবে না, বা 0 byte allocate

৩. Hash table-এ modulo bias।

bucket = hash(key) % num_buckets

num_buckets যদি 256 হয় আর hash function-এর low bit দুর্বল হয়, তাহলে শুধু low 8 bit ব্যবহার হচ্ছে — উপরের সব bit-এর তথ্য ফেলে দেওয়া হচ্ছে।

এই কারণেই ভালো hash table implementation prime সংখ্যক bucket ব্যবহার করে, বা hash-কে আগে “mix” করে (Java-র HashMap উপরের bit-গুলো নিচে XOR করে দেয়)।

৪. Random সংখ্যায় modulo bias।

int roll = rand() % 6;      // 0..5 চাই

RAND_MAX যদি 6-এর গুণিতক না হয়, তাহলে ছোট মানগুলো সামান্য বেশি সম্ভাব্য হয়। Cryptographic প্রসঙ্গে এটা গুরুতর।

সঠিক পদ্ধতি — rejection sampling:

int r;
do { r = rand(); } while (r >= RAND_MAX - RAND_MAX % 6);
return r % 6;

৫. Sequence number wraparound।

TCP-র sequence number ৩২ bit, তাই 2³² byte পর wrap করে। উচ্চ-গতির লিঙ্কে এটা সেকেন্ডে ঘটতে পারে — তাই TCP-তে PAWS (Protection Against Wrapped Sequence numbers) নামে একটা প্রক্রিয়া আছে। Level 7-এ দেখব।

মূল পাঠ: % একটা non-injective function। প্রতিবার % লেখার মানে আপনি ইচ্ছাকৃতভাবে তথ্য ফেলে দিচ্ছেন — নিশ্চিত হোন যে সেটাই আপনি চান।

Level 1-এ আমরা integer overflow আর wraparound bit ধরে দেখব।

sort একটা function — একই input list-এ সবসময় একই output। Deterministic, side-effect-মুক্ত (যদি copy ফেরত দেয়)।

shuffle function নয় — একই input-এ ভিন্ন output। এটা determinism শর্ত ভাঙে।

গাণিতিকভাবে shuffle একটা function হতে পারে যদি random state-কেও input ধরা হয়:

$\text{shuffle} : (\text{List}, \text{Seed}) \to \text{List}$

এখন এটা deterministic — একই seed, একই ফল।

Testing-এ কেন গুরুত্বপূর্ণ:

১. Function-দের সহজে test করা যায়।

def test_sort():
    assert sort([3,1,2]) == [1,2,3]      # সরাসরি তুলনা

২. Non-function-দের property দিয়ে test করতে হয়।

def test_shuffle():
    original = [1,2,3,4,5]
    result = shuffle(original[:])
    assert sorted(result) == sorted(original)   # permutation
    assert len(result) == len(original)
    # কিন্তু ঠিক কী হবে তা বলা যায় না

৩. Seed ঢুকিয়ে reproducible করা যায়।

def test_shuffle_deterministic():
    rng = random.Random(42)
    a = shuffle([1,2,3,4,5], rng=random.Random(42))
    b = shuffle([1,2,3,4,5], rng=random.Random(42))
    assert a == b            # এখন function-এর মতো আচরণ

এই কারণেই ভালো library-তে RNG inject করা যায়, global state ব্যবহার করে না। numpy.random.Generator, Rust-এর rand::Rng trait — সবাই এই নকশা অনুসরণ করে।

৪. একই যুক্তি সব impure function-এ প্রযোজ্য।

এই সবগুলো একই কৌশল: লুকানো input-কে স্পষ্ট parameter বানান। তখন non-function টা function হয়ে যায়, আর testable হয়ে যায়।

Haskell-এ এটা type-এ বাধ্যতামূলক — IO type-এ না থাকলে function pure হতেই হবে। Level 5-এ আমরা দেখব এই সীমাবদ্ধতা কীভাবে compiler-কে আরো আক্রমণাত্মক optimization করতে দেয়: pure function memoize করা যায়, পুনর্বিন্যাস করা যায়, সমান্তরালে চালানো যায় — কারণ কোনো লুকানো নির্ভরতা নেই।