গ্রোবনার ভিত্তি এবং একটি রৈখিক কোডের দ্বিতীয় সাধারণীকৃত হ্যামিং ওজন

মৌলিক তথ্য

• পেপার আইডি: 2510.09917
• শিরোনাম: গ্রোবনার ভিত্তি এবং একটি রৈখিক কোডের দ্বিতীয় সাধারণীকৃত হ্যামিং ওজন
• লেখক: হার্নান দে আলবা (জাকাটেকাস স্বায়ত্তশাসিত বিশ্ববিদ্যালয়), সেসিলিয়া মার্টিনেজ-রেয়েস (জাকাটেকাস স্বায়ত্তশাসিত বিশ্ববিদ্যালয়)
• শ্রেণীবিভাগ: math.AC (বীজগণিতীয় সংযোজন), cs.IT (তথ্য তত্ত্ব), math.IT (গাণিতিক তথ্য তত্ত্ব)
• প্রকাশনার সময়: ২০২৫ সালের ১০ অক্টোবর
• পেপার লিঙ্ক: https://arxiv.org/abs/2510.09917v1

সারসংক্ষেপ

দ্বিমুখী কোডের জন্য, গ্রোবনার ভিত্তি ব্যবহার করে ন্যূনতম সমর্থিত কোডওয়ার্ডের একটি উপসেট পাওয়া যায়, যা কোডের দ্বিতীয় সাধারণীকৃত হ্যামিং ওজন নির্ধারণ করতে ব্যবহৃত হয়। এই পেপারটি অ-দ্বিমুখী কোডগুলির জন্য একই বৈশিষ্ট্য সন্তুষ্ট করার শর্তগুলি প্রতিষ্ঠা করে। আমরা যেকোনো অ-দ্বিমুখী সীমিত ক্ষেত্রে এই বৈশিষ্ট্য সন্তুষ্ট না করে এমন কোডের পরিবার তৈরি করি। অধিকন্তু, আমরা প্রমাণ করি যে যখন গ্রোবনার ভিত্তি দ্বারা প্রাপ্ত উপসেট দ্বিতীয় সাধারণীকৃত হ্যামিং ওজন নির্ধারণের জন্য যথেষ্ট হয়, তখন এই অপরিবর্তনীয়টি ন্যূনতম মুক্ত সমাধানের সহ-সীমানার ডিগ্রি থেকেও পুনরুদ্ধার করা যায়।

গবেষণার পটভূমি এবং প্রেরণা

সমস্যার পটভূমি

সাধারণীকৃত হ্যামিং ওজন (Generalized Hamming Weights, GHWs) রৈখিক কোডের গুরুত্বপূর্ণ পরামিতি এবং তথ্য তত্ত্বে ব্যাপক প্রয়োগ রয়েছে। রৈখিক কোড C ⊂ F_q^n এর জন্য, i-তম সাধারণীকৃত হ্যামিং ওজন সংজ্ঞায়িত হয়:

d_i(C) = min{ω(D) : D হল C এর i-মাত্রিক উপস্থান}

যেখানে ω(D) উপস্থান D এর ওজন (সমর্থনের আকার) প্রকাশ করে।

গবেষণার প্রেরণা

1. দ্বিমুখী কোডের পরিচিত ফলাফল: দ্বিমুখী কোডের জন্য, গার্সিয়া-মার্কো এবং অন্যরা প্রমাণ করেছেন যে কোডের সাথে সম্পর্কিত দ্বিপদী আদর্শের হ্রাসকৃত গ্রোবনার ভিত্তি ব্যবহার করে প্রথম এবং দ্বিতীয় সাধারণীকৃত হ্যামিং ওজন নির্ধারণ করা যায়।
2. অ-দ্বিমুখী কোডের চ্যালেঞ্জ: অ-দ্বিমুখী কোডের জন্য (q > 2), একই পদ্ধতি প্রযোজ্য কিনা তা স্পষ্ট নয়, যা গার্সিয়া-মার্কো এবং অন্যরা 10 এ তাদের চতুর্থ প্রশ্ন হিসাবে উত্থাপন করেছেন।
3. তাত্ত্বিক সম্পূর্ণতা: বিভিন্ন সীমিত ক্ষেত্রে গ্রোবনার ভিত্তি পদ্ধতির প্রযোজ্যতা বোঝার জন্য একটি সম্পূর্ণ তাত্ত্বিক কাঠামো প্রতিষ্ঠা করা প্রয়োজন।

মূল অবদান

1. যথেষ্ট শর্ত প্রতিষ্ঠা: অ-দ্বিমুখী কোডের সেট M_G এর d_2-পরীক্ষা সেট হওয়ার যথেষ্ট শর্ত প্রস্তাব করা (উপপাদ্য 4.7)
2. প্রতিউদাহরণ নির্মাণ: প্রতিটি q > 2 এর জন্য, M_G যা d_2-পরীক্ষা সেট নয় এমন রৈখিক কোডের পরিবার তৈরি করা (উপপাদ্য 5.1)
3. মুক্ত সমাধানের সংযোগ: যখন M_G একটি d_2-পরীক্ষা সেট হয় তখন ন্যূনতম মুক্ত সমাধানের বেটি সংখ্যা থেকে দ্বিতীয় সাধারণীকৃত হ্যামিং ওজন নির্ধারণ করা যায় তা প্রমাণ করা (উপপাদ্য 6.2)
4. d_2-পরীক্ষা সেট ধারণা প্রবর্তন: দ্বিতীয় সাধারণীকৃত হ্যামিং ওজনের গণনা আরও নির্ভুলভাবে চিহ্নিত করার জন্য তাত্ত্বিক সরঞ্জাম প্রদান করা

পদ্ধতির বিস্তারিত বর্ণনা

কাজের সংজ্ঞা

রৈখিক কোড C ⊂ F_q^n দেওয়া, লক্ষ্য হল নির্ধারণ করা যে কখন গ্রোবনার ভিত্তি পদ্ধতির মাধ্যমে দ্বিতীয় সাধারণীকৃত হ্যামিং ওজন d_2(C) গণনা করা যায়।

মূল ধারণা

d_2-পরীক্ষা সেট

সংজ্ঞা 3.1: রৈখিক কোড C ⊂ F_q^n এর জন্য, সেট M ⊂ M_C কে C এর d_2-পরীক্ষা সেট বলা হয়, যদি c_1, c_2 ∈ M বিদ্যমান থাকে যেমন dim⟨c_1, c_2⟩ = 2 এবং ω(⟨c_1, c_2⟩) = d_2(C)।

মূল সেট নির্মাণ

মাত্রা k ≥ 2 এর রৈখিক কোড C এর জন্য, সংজ্ঞায়িত করুন:

• M_1 = {m ∈ C \ {0} | ∃m' ∈ C এমন যে d_2(C) = ω(⟨m,m'⟩)}
• m_1 = min_≺(M_1) (নির্দিষ্ট ক্রম সম্পর্ক ব্যবহার করে)
• M_2 = {m ∈ C | d_2(C) = ω(⟨m_1,m⟩)}
• m_2 = min_≺(M_2)

প্রধান তাত্ত্বিক ফলাফল

উপপাদ্য A (উপপাদ্য 4.7)

যথেষ্ট শর্ত: ধরুন C ⊂ F_q^n একটি রৈখিক কোড, যা |I_C ∩ J_C| ≤ (|J_C| + 1)/2 সন্তুষ্ট করে, যেখানে I_C = supp(m_1), J_C = supp(m_2)। ধরুন G হল I(C) এর হ্রাসকৃত গ্রোবনার ভিত্তি, তাহলে M_G একটি d_2-পরীক্ষা সেট।

উপপাদ্য B (উপপাদ্য 5.1)

প্রতিউদাহরণের অস্তিত্ব: প্রতিটি q > 2 এর জন্য, রৈখিক কোড C ⊂ F_q^n বিদ্যমান যেমন M_G একটি d_2-পরীক্ষা সেট নয়।

উপপাদ্য C (উপপাদ্য 6.2)

মুক্ত সমাধান চিহ্নিতকরণ: ধরুন C ⊂ F_q^n মাত্রা k এর একটি রৈখিক কোড, M ⊂ M_C। তাহলে:

1. min{j | β_{1,j}(R/I_M) ≠ 0} = d_1(C) যদি এবং শুধুমাত্র যদি M ন্যূনতম হ্যামিং ওজনের কোডওয়ার্ড ধারণ করে
2. min{j | β_{2,j}(R/I_M) ≠ 0} = d_2(C) যদি এবং শুধুমাত্র যদি M একটি d_2-পরীক্ষা সেট হয়

প্রযুক্তিগত উদ্ভাবনী বিন্দু

1. শর্ত চিহ্নিতকরণ: দ্বিমুখী কোডে অসমতা |I_C ∩ J_C| ≤ |I_C|/2 কে অ-দ্বিমুখী ক্ষেত্রে |I_C ∩ J_C| ≤ (|J_C| + 1)/2 এ সাধারণীকরণ করা
2. প্রতিউদাহরণ নির্মাণ: সূক্ষ্ম কোড নির্মাণের মাধ্যমে অ-দ্বিমুখী ক্ষেত্রে গ্রোবনার ভিত্তি পদ্ধতির সীমাবদ্ধতা প্রমাণ করা
3. বীজগণিত জ্যামিতি সংযোগ: কোডিং তত্ত্ব এবং সংযোজনীয় বীজগণিতে মুক্ত সমাধান তত্ত্বের মধ্যে গভীর সংযোগ স্থাপন করা

পরীক্ষামূলক সেটআপ

নির্মাণ উদাহরণ

উদাহরণ 4.8: F_3^9 এ রৈখিক কোড বিবেচনা করুন, উৎপাদক ম্যাট্রিক্স সহ:

G = [1 0 0 0 0 1 0 2 0]
    [0 1 0 0 1 1 1 0 1]
    [0 0 1 1 2 2 1 1 0]

গণনার মাধ্যমে যাচাই করুন:

• I_C = {1, 6, 8}, J_C = {2, 5, 6, 7, 9}
• |I_C ∩ J_C| = 1 < 3 = (|J_C| + 1)/2
• d_2(C) = |I_C ∪ J_C| = 7
• M_G সত্যিই একটি d_2-পরীক্ষা সেট

প্রতিউদাহরণ নির্মাণ

উদাহরণ 5.4: q > 2 এর জন্য, D' = ⟨c_1, c_2⟩ ⊂ F_q^{2q+2} তৈরি করুন, যেখানে:

• c_1 = (1, 1, α, α^2, ..., α^{q-1}, α, α^2, ..., α^{q-1}, 0, 0)
• c_2 = (0, 0, 1, 1, ..., 1, 1, 1, ..., 1, 1, 1)

যাচাই করুন |I_{D'} ∩ J_{D'}| = 2q - 2 > (2q + 1)/2, যথেষ্ট শর্ত সন্তুষ্ট করে না।

পরীক্ষার ফলাফল

প্রধান আবিষ্কার

1. শর্তের প্রয়োজনীয়তা: নির্দিষ্ট উদাহরণের মাধ্যমে উপপাদ্য 4.7 এ শর্তের গুরুত্ব যাচাই করা
2. অ্যালগরিদম বাস্তবায়ন: হ্রাসকৃত গ্রোবনার ভিত্তি গণনা করতে SageMath ব্যবহার করে FGLM অ্যালগরিদম বাস্তবায়ন করা
3. গণনার জটিলতা: উদাহরণ 4.8 এ, হ্রাসকৃত গ্রোবনার ভিত্তি G তে 457 টি দ্বিপদী রয়েছে, যার মধ্যে 27 টি R_X এর অন্তর্গত

তাত্ত্বিক যাচাইকরণ

নির্মিত প্রতিউদাহরণের মাধ্যমে প্রমাণ করা:

• q > 2 এর জন্য, রৈখিক কোড বিদ্যমান যেমন M_G একটি d_2-পরীক্ষা সেট নয়
• এটি নির্দেশ করে যে দ্বিমুখী কোডের ফলাফল অ-দ্বিমুখী ক্ষেত্রে সরাসরি প্রসারিত হতে পারে না
• পদ্ধতির কার্যকারিতা নিশ্চিত করতে অতিরিক্ত শর্ত প্রয়োজন

সম্পর্কিত কাজ

কোডিং তত্ত্বের পটভূমি

• সাধারণীকৃত হ্যামিং ওজন: Wei দ্বারা 1991 সালে প্রবর্তিত, তথ্য তত্ত্বে গুরুত্বপূর্ণ প্রয়োগ রয়েছে
• বিশেষ কোড শ্রেণীর গবেষণা: চক্রীয় কোড, রিড-মুলার কোড, ট্রেস কোড ইত্যাদির সাধারণীকৃত হ্যামিং ওজন ব্যাপকভাবে অধ্যয়ন করা হয়েছে
• গণনা পদ্ধতি: দ্বিঘাত ফর্ম পদ্ধতি, গ্রোবনার ভিত্তি পদ্ধতি, মুক্ত সমাধান পদ্ধতি ইত্যাদি অন্তর্ভুক্ত

কোডিং তত্ত্বে গ্রোবনার ভিত্তির প্রয়োগ

• দ্বিপদী আদর্শ: মার্কেজ-কর্বেলা এবং অন্যরা রৈখিক কোড এবং দ্বিপদী আদর্শের মধ্যে সংযোগ প্রতিষ্ঠা করেছেন
• পরীক্ষা সেট তত্ত্ব: বার্গ এবং অন্যরা ন্যূনতম দূরত্ব ডিকোডিংয়ের জন্য পরীক্ষা সেটের ধারণা বিকশিত করেছেন

বীজগণিত জ্যামিতি পদ্ধতি

• মুক্ত সমাধান: জনসেন এবং ভার্ডুর প্রমাণ করেছেন যে স্ট্যানলি-রেইসনার রিংয়ের বেটি সংখ্যা থেকে সমস্ত সাধারণীকৃত হ্যামিং ওজন পুনরুদ্ধার করা যায়
• একপদী আদর্শ: কোডওয়ার্ড সমর্থনের সাথে সম্পর্কিত একপদী আদর্শের গবেষণা

উপসংহার এবং আলোচনা

প্রধান উপসংহার

1. শর্ত চিহ্নিতকরণ: অ-দ্বিমুখী কোডে M_G এর d_2-পরীক্ষা সেট হওয়ার যথেষ্ট শর্ত প্রতিষ্ঠা করা
2. সীমাবদ্ধতা প্রকাশ: দ্বিমুখী কোডের ফলাফল অ-দ্বিমুখী ক্ষেত্রে সহজভাবে প্রসারিত হতে পারে না তা প্রমাণ করা
3. বীজগণিত সংযোগ: কোডিং তত্ত্ব এবং সংযোজনীয় বীজগণিতের মধ্যে গভীর সংযোগ স্থাপন করা

সীমাবদ্ধতা

1. যথেষ্ট শর্ত: প্রদত্ত শর্ত যথেষ্ট কিন্তু সম্ভবত প্রয়োজনীয় নয়
2. গণনার জটিলতা: গ্রোবনার ভিত্তির গণনা বাস্তব প্রয়োগে জটিলতার সম্মুখীন হতে পারে
3. সাধারণীকরণ: ফলাফল প্রধানত দ্বিতীয় সাধারণীকৃত হ্যামিং ওজনে কেন্দ্রীভূত, উচ্চতর ক্রমের ওজনে সাধারণীকরণ আরও গবেষণার প্রয়োজন

ভবিষ্যত দিকনির্দেশনা

1. প্রয়োজনীয় এবং যথেষ্ট শর্ত: M_G এর d_2-পরীক্ষা সেট হওয়ার প্রয়োজনীয় এবং যথেষ্ট শর্ত খুঁজে বের করা
2. অ্যালগরিদম অপ্টিমাইজেশন: আরও দক্ষ গণনা পদ্ধতি বিকাশ করা
3. উচ্চতর ক্রমের সাধারণীকরণ: ফলাফল উচ্চতর ক্রমের সাধারণীকৃত হ্যামিং ওজনে প্রসারিত করা
4. প্রয়োগ অন্বেষণ: ক্রিপ্টোগ্রাফি এবং যোগাযোগ তত্ত্বে নির্দিষ্ট প্রয়োগ

গভীর মূল্যায়ন

সুবিধা

1. তাত্ত্বিক গভীরতা: কোডিং তত্ত্ব এবং বীজগণিত জ্যামিতির মধ্যে গভীর সংযোগ প্রতিষ্ঠা করে, উল্লেখযোগ্য তাত্ত্বিক মূল্য রয়েছে
2. সম্পূর্ণতা: শুধুমাত্র ইতিবাচক ফলাফল নয়, প্রতিউদাহরণও তৈরি করে, সমস্যার সম্পূর্ণ চিত্র উপস্থাপন করে
3. প্রযুক্তিগত উদ্ভাবন: d_2-পরীক্ষা সেট ধারণা প্রবর্তন করে, সম্পর্কিত গবেষণার জন্য নতুন সরঞ্জাম প্রদান করে
4. কঠোর প্রমাণ: সমস্ত প্রধান ফলাফলের সম্পূর্ণ গাণিতিক প্রমাণ রয়েছে, যুক্তি সুসংগত

অসুবিধা

1. ব্যবহারিক সীমাবদ্ধতা: প্রধানত তাত্ত্বিক ফলাফল, বাস্তব কোডিং প্রয়োগে মূল্য যাচাই করা প্রয়োজন
2. গণনার জটিলতা: গ্রোবনার ভিত্তি গণনার জটিলতা পদ্ধতির ব্যবহারিকতা সীমিত করতে পারে
3. সাধারণীকরণ সীমাবদ্ধতা: ফলাফল প্রধানত দ্বিতীয় সাধারণীকৃত হ্যামিং ওজনের জন্য, আরও সাধারণ ক্ষেত্রে সাধারণীকরণ অস্পষ্ট

প্রভাব

1. একাডেমিক অবদান: কোডিং তত্ত্ব এবং বীজগণিত জ্যামিতির আন্তঃবিভাগীয় গবেষণার জন্য নতুন দিকনির্দেশনা খোলে
2. তাত্ত্বিক সম্পূর্ণতা: সাধারণীকৃত হ্যামিং ওজন গণনার তাত্ত্বিক কাঠামো সম্পূর্ণ করে
3. পদ্ধতিগত মূল্য: অনুরূপ সমস্যা গবেষণার জন্য পদ্ধতিগত নির্দেশনা প্রদান করে

প্রযোজ্য দৃশ্য

1. তাত্ত্বিক গবেষণা: কোডিং তত্ত্ব এবং বীজগণিত জ্যামিতির আন্তঃবিভাগীয় গবেষণার জন্য উপযুক্ত
2. অ্যালগরিদম ডিজাইন: সাধারণীকৃত হ্যামিং ওজন গণনার নতুন অ্যালগরিদম বিকাশের জন্য তাত্ত্বিক ভিত্তি প্রদান করে
3. শিক্ষা গবেষণা: কোডিং তত্ত্বে বীজগণিত পদ্ধতির প্রয়োগের সাধারণ উদাহরণ হিসাবে কাজ করে

সংদর্ভ

প্রধান সংদর্ভগুলি অন্তর্ভুক্ত করে:

• 10 গার্সিয়া-মার্কো এবং অন্যদের দ্বিমুখী কোডের মুক্ত সমাধান এবং সাধারণীকৃত হ্যামিং ওজন সম্পর্কিত কাজ
• 19 জনসেন এবং ভার্ডুরের স্ট্যানলি-রেইসনার রিংয়ের বেটি সংখ্যা এবং হ্যামিং ওজন সম্পর্কের গবেষণা
• 23 মার্কেজ-কর্বেলা এবং অন্যদের রৈখিক কোড সম্পর্কিত আদর্শের ভিত্তিগত কাজ
• 30 Wei এর সাধারণীকৃত হ্যামিং ওজনের মূল সংজ্ঞা

এই পেপারটি কোডিং তত্ত্ব এবং বীজগণিত জ্যামিতির আন্তঃবিভাগীয় ক্ষেত্রে উল্লেখযোগ্য অবদান রাখে, কঠোর গাণিতিক বিশ্লেষণের মাধ্যমে অ-দ্বিমুখী কোডে গ্রোবনার ভিত্তি পদ্ধতির প্রযোজ্যতা এবং সীমাবদ্ধতা প্রকাশ করে, সম্পর্কিত ক্ষেত্রের আরও গবেষণার জন্য একটি দৃঢ় তাত্ত্বিক ভিত্তি স্থাপন করে।