2025-11-12T01:01:29.514663

Existence of 3 anti-cocircular truncated Möbius planes and constructions of strength-4 covering arrays

Shokri, Moura, Stevens
Two projective (affine) planes with the same point sets are orthogoval if the common intersection of any two lines, one from each, has size at most two. The existence of a pair of orthogoval projective planes has been proven and published independently many times. A strength-$t$ covering array, denoted by CA$(N; t, k, v)$, is an $N \times k$ array over a $v$-set such that in any $t$-set of columns, each $t$-tuple occurs at least once in a row. A pair of orthogoval projective planes can be used to construct a strength-$3$ covering array CA$(2q^3-1; 3, q^2 + q + 1, q)$. Our work extends this result to construct arrays of strength $4$. A $k$-cap in a projective geometry is a set of $k$ points no three of which are collinear. In $PG(3,q)$, an ovoid is a maximum-sized $k$-cap with $k =q^2+1$. Its plane sections (circles) are the blocks of a $3-(q^2 + 1, q + 1, 1)$ design, called a Möbius plane of order $q$. For $q$ an odd prime power, we prove the existence of three truncated Möbius planes, such that for any choice of these circles, one from each plane, their intersection size is at most three. From this, we construct a strength-$4$ covering array CA$(3q^4-2; 4, \frac{q^2+1}{2}, q)$. For $q \geq 11$, these covering arrays improve the size of the best-known covering arrays with the same parameters by almost 25 percent. The CA$(3q^4 -3; 4, \frac{q^2 +1}{2}, q)$ is used as the main ingredient in a recursive construction to obtain a CA$(5q^4 - 4q^3 - q^2 + 2q; 4, q^2 +1, q)$. Some improvements are obtained in the size of the best-known arrays using these covering arrays.
academic

৩টি অ্যান্টি-কোসার্কুলার ট্রাংকেটেড মোবিয়াস প্লেনের অস্তিত্ব এবং শক্তি-৪ কভারিং অ্যারের নির্মাণ

মৌলিক তথ্য

  • পেপার আইডি: 2510.13122
  • শিরোনাম: Existence of 3 anti-cocircular truncated Möbius planes and constructions of strength-4 covering arrays
  • লেখক: কিয়ানুশ শোকরি (অটাওয়া বিশ্ববিদ্যালয়), লুসিয়া মোউরা (অটাওয়া বিশ্ববিদ্যালয়), ব্রেট স্টিভেন্স (কার্লটন বিশ্ববিদ্যালয়)
  • শ্রেণীবিভাগ: math.CO (সমন্বয়বিদ্যা)
  • প্রকাশনার সময়: ২০২৫ সালের ১৫ অক্টোবর (arXiv প্রিপ্রিন্ট)
  • পেপার লিংক: https://arxiv.org/abs/2510.13122

সারসংক্ষেপ

এই পেপারটি সীমিত জ্যামিতি এবং কভারিং অ্যারের সমন্বয়গত নির্মাণ সমস্যা অধ্যয়ন করে। লেখকরা প্রমাণ করেছেন যে বিজোড় মৌলিক শক্তি q এর জন্য, তিনটি অ্যান্টি-কোসার্কুলার ট্রাংকেটেড মোবিয়াস প্লেন বিদ্যমান, যেখানে প্রতিটি প্লেন থেকে একটি করে বৃত্ত নির্বাচন করলে তাদের ছেদের আকার সর্বোচ্চ ৩। এই জ্যামিতিক কাঠামোর উপর ভিত্তি করে, শক্তি ৪ এর কভারিং অ্যারে CA(3q⁴-2; 4, (q²+1)/2, q) নির্মাণ করা হয়েছে। q≥11 এর জন্য, এই কভারিং অ্যারেগুলি পরিচিত সর্বোত্তম ফলাফলের চেয়ে প্রায় ২৫% উন্নত। অতিরিক্তভাবে, পুনরাবৃত্তিমূলক নির্মাণ পদ্ধতি প্রদান করা হয়েছে, যা CA(5q⁴-4q³-q²+2q; 4, q²+1, q) প্রদান করে।

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

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

১. কভারিং অ্যারের গুরুত্ব: কভারিং অ্যারে সফটওয়্যার পরীক্ষায় গুরুত্বপূর্ণ প্রয়োগ রয়েছে এবং পরীক্ষার কেস সংখ্যা উল্লেখযোগ্যভাবে হ্রাস করতে পারে। শক্তি t এর কভারিং অ্যারে CA(N; t, k, v) একটি N×k ম্যাট্রিক্স, যা নিশ্চিত করে যে যেকোনো t কলামের সমস্ত সম্ভাব্য t-টুপল কমপক্ষে একবার উপস্থিত হয়।

२. জ্যামিতিক নির্মাণ পদ্ধতি: সীমিত জ্যামিতি কভারিং অ্যারে নির্মাণের জন্য শক্তিশালী সরঞ্জাম প্রদান করে। পরিচিত যে অর্থোগোনাল প্রজেক্টিভ প্লেন শক্তি ৩ এর কভারিং অ্যারে নির্মাণ করতে পারে, কিন্তু শক্তি ৪ এর নির্মাণে সাধারণীকরণ সর্বদা একটি চ্যালেঞ্জ ছিল।

३. বিদ্যমান পদ্ধতির সীমাবদ্ধতা:

  • বিদ্যমান শক্তি ৪ কভারিং অ্যারে নির্মাণ পদ্ধতি প্রধানত গণনামূলক অনুসন্ধানের উপর নির্ভর করে
  • পদ্ধতিগত জ্যামিতিক নির্মাণ তত্ত্বের অভাব রয়েছে
  • বৃহত্তর পরামিতির জন্য, পরিচিত ফলাফলের স্কেল এখনও উন্নতির জায়গা রয়েছে

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

এই পেপারের মূল প্রেরণা হল অর্থোগোনাল প্রজেক্টিভ প্লেনের সফল অভিজ্ঞতা উচ্চতর জ্যামিতিক বস্তুতে সাধারণীকরণ করা, বিশেষত PG(3,q) তে ওভয়েড (ovoid) এবং এর প্লেন সেকশন দ্বারা গঠিত মোবিয়াস প্লেন, যা আরও ভাল শক্তি ৪ কভারিং অ্যারে নির্মাণ করতে পারে।

মূল অবদান

१. তাত্ত্বিক অবদান: প্রমাণ করা হয়েছে যে বিজোড় মৌলিক শক্তি q এর জন্য, তিনটি অ্যান্টি-কোসার্কুলার ট্রাংকেটেড মোবিয়াস প্লেন বিদ্যমান, যেখানে যেকোনো তিনটি বৃত্ত (প্রতিটি প্লেন থেকে একটি) নির্বাচন করলে তাদের ছেদের আকার সর্বোচ্চ ৩।

२. নির্মাণ পদ্ধতি: জ্যামিতিক কাঠামোর উপর ভিত্তি করে, শক্তি ৪ কভারিং অ্যারে CA(3q⁴-2; 4, (q²+1)/2, q) এর স্পষ্ট নির্মাণ প্রদান করা হয়েছে।

३. কর্মক্ষমতা উন্নতি: q≥11 এর জন্য, নতুন নির্মাণ পরিচিত সর্বোত্তম ফলাফলের তুলনায় প্রায় ২৫% উন্নত।

४. পুনরাবৃত্তিমূলক সম্প্রসারণ: পুনরাবৃত্তিমূলক নির্মাণ পদ্ধতি প্রদান করা হয়েছে, যা সমস্ত ওভয়েড পয়েন্ট ব্যবহার করে কভারিং অ্যারে CA(5q⁴-4q³-q²+2q; 4, q²+1, q) প্রদান করে।

५. জ্যামিতিক অন্তর্দৃষ্টি: হাইপারসারফেস তত্ত্ব এবং কভারিং অ্যারে নির্মাণের মধ্যে গভীর সংযোগ স্থাপন করা হয়েছে।

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

কাজের সংজ্ঞা

শক্তি ৪ এর কভারিং অ্যারে নির্মাণ করা, অর্থাৎ N×k ম্যাট্রিক্স A খুঁজে বের করা, যাতে যেকোনো ৪ কলামের জন্য, সমস্ত সম্ভাব্য ৪-টুপল (a,b,c,d)∈F_q⁴ কমপক্ষে কোনো একটি সারিতে উপস্থিত হয়।

মূল জ্যামিতিক নির্মাণ

१. মোবিয়াস প্লেন এবং ওভয়েড

  • ওভয়েডের সংজ্ঞা: PG(3,q) তে ওভয়েড O হল q²+1 টি পয়েন্টের সমষ্টি, যেখানে যেকোনো তিনটি পয়েন্ট সহরৈখিক নয়
  • মোবিয়াস প্লেন: ওভয়েডের প্লেন সেকশন 3-(q²+1, q+1, 1) ডিজাইন গঠন করে, যাকে q ক্রমের মোবিয়াস প্লেন বলা হয়

२. তিনটি ট্রাংকেটেড মোবিয়াস প্লেনের নির্মাণ

জেনারেটিং ম্যাট্রিক্স G_l^c এর উপর ভিত্তি করে, তিনটি ট্রাংকেটেড মোবিয়াস প্লেন সংজ্ঞায়িত করা হয়:

  • M₁: (M^(e), {C∩M^(e) : C∈C}), যেখানে M^(e) সমান সূচকযুক্ত পয়েন্ট সেট
  • M₂: (M^(e), {(C∩M^(e))/2 : C∈C})
  • M₁/₂: (M^(e), {2(C∩M^(e)) : C∈C})

সংশ্লিষ্ট জেনারেটিং ম্যাট্রিক্স যথাক্রমে G_{q+1}^{(q²+1)/2}, G_{2(q+1)}^{(q²+1)/2}, G_{(q+1)/2}^{(q²+1)/2}।

३. অ্যান্টি-কোসার্কুলার বৈশিষ্ট্যের প্রমাণ

মূল উপপাদ্য ४.२५: তিনটি ট্রাংকেটেড মোবিয়াস প্লেন M₁, M₂, M₁/₂ অ্যান্টি-কোসার্কুলার বৈশিষ্ট্য সন্তুষ্ট করে, অর্থাৎ যেকোনো তিনটি বৃত্ত (প্রতিটি প্লেন থেকে একটি) নির্বাচন করলে তাদের ছেদের আকার সর্বোচ্চ ৩।

প্রমাণের কৌশল: १. রৈখিক রূপান্তর Ω এর মাধ্যমে জ্যামিতিক সমস্যাকে PG(3,q⁴) তে হাইপারসারফেস ছেদ সমস্যায় রূপান্তরিত করা २. ট্রেস ফাংশন Tr(α^i) এর বৈশিষ্ট্য ব্যবহার করে পার্থক্য সেট এবং হাইপারসারফেসের মধ্যে সংযোগ স্থাপন করা ३. বিস্তারিত বীজগণিতীয় গণনার মাধ্যমে ছেদের উপরের সীমা প্রমাণ করা

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

१. জ্যামিতি-বীজগণিত সংযোগ: মোবিয়াস প্লেনের বৃত্ত এবং PG(3,q⁴) তে হাইপারসারফেসের মধ্যে এক-এক সংযোগ স্থাপন করা

२. হাইপারসারফেস ছেদ তত্ত্ব: রৈখিক, দ্বিঘাত, চতুর্ঘাত হাইপারসারফেস এবং ওভয়েডের ছেদ বৈশিষ্ট্য পদ্ধতিগতভাবে অধ্যয়ন করা

३. অ্যান্টি-কোসার্কুলার ধারণা: অর্থোগোনাল প্লেনের ধারণা মোবিয়াস প্লেনে সাধারণীকরণ করা এবং অ্যান্টি-কোসার্কুলার বৈশিষ্ট্য সংজ্ঞায়িত করা

४. নির্মাণমূলক প্রমাণ: সমস্ত অস্তিত্ব ফলাফল স্পষ্ট নির্মাণ পদ্ধতি প্রদান করে

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

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

পেপারটি প্রধানত তাত্ত্বিক কাজ, কঠোর গাণিতিক প্রমাণের মাধ্যমে ফলাফলের সঠিকতা যাচাই করে।

পরামিতি পরিসীমা

  • মৌলিক শক্তি: বিজোড় মৌলিক শক্তি q = 3, 5, 7, 9, 11, 13, 17, 19, 23, 25 বিবেচনা করা হয়
  • কভারিং অ্যারে পরামিতি: শক্তি t=4, কলাম সংখ্যা k=(q²+1)/2 বা q²+1, প্রতীক সংখ্যা v=q

তুলনা মানদণ্ড

কলবোর্ন দ্বারা রক্ষণাবেক্ষণকৃত কভারিং অ্যারে টেবিলে পরিচিত সর্বোত্তম ফলাফলের সাথে তুলনা করা হয়।

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

প্রধান ফলাফল

শক্তি ৪ কভারিং অ্যারে CA(3q⁴-2; 4, (q²+1)/2, q) এর কর্মক্ষমতা

qk=(q²+1)/2নতুন পদ্ধতি N_sপরিচিত সর্বোত্তম N_cউন্নতির হার
116143,92155,891-21.4%
138585,681109,837-22.0%
17145250,561329,137-23.9%
19181390,961520,543-24.9%
23265839,5211,119,361-25.0%
253131,171,8731,562,497-25.0%

পুনরাবৃত্তিমূলক নির্মাণ CA(5q⁴-4q³-q²+2q; 4, q²+1, q) এর কর্মক্ষমতা

qk=q²+1নতুন পদ্ধতি N_sপরিচিত সর্বোত্তম N_cউন্নতির হার
1112267,78270,521-3.9%
13170133,874138,385-3.3%
17290397,698412,369-3.6%
19362623,846644,347-3.2%

মূল আবিষ্কার

१. উল্লেখযোগ্য উন্নতি: q≥11 এর জন্য, নতুন নির্মাণ k=(q²+1)/2 পরামিতিতে ২१-२५% উন্নতি অর্জন করে

२. পুনরাবৃত্তিমূলক সম্প্রসারণ: পুনরাবৃত্তিমূলক পদ্ধতির মাধ্যমে আরও বেশি কলাম পরিচালনা করা যায়, যদিও উন্নতির মাত্রা ছোট কিন্তু এখনও পরিচিত ফলাফলের চেয়ে ভাল

३. তাত্ত্বিক সর্বোত্তমতা: নির্মাণ পদ্ধতি স্পষ্ট জ্যামিতিক ভিত্তি রয়েছে, যা আরও অপ্টিমাইজেশনের জন্য তাত্ত্বিক নির্দেশনা প্রদান করে

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

অর্থোগোনাল প্লেন তত্ত্ব

  • ঐতিহাসিক উন্নয়ন: অর্থোগোনাল প্রজেক্টিভ প্লেনের অস্তিত্ব একাধিকবার স্বাধীনভাবে প্রমাণিত হয়েছে
  • নির্মাণ পদ্ধতি: প্রাথমিক বহুপদ পদ্ধতি, ক্রেমোনা রূপান্তর ইত্যাদি বিভিন্ন কৌশল অন্তর্ভুক্ত করে
  • প্রয়োগ: শক্তি ३ কভারিং অ্যারে CA(2q³-1; 3, q²+q+1, q) সফলভাবে নির্মাণ করেছে

কভারিং অ্যারে নির্মাণ

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

উচ্চতর জ্যামিতিক বস্তু

  • ওভয়েড তত্ত্ব: PG(3,q) তে ওভয়েডের শ্রেণীবিভাগ এবং বৈশিষ্ট্য গবেষণা
  • মোবিয়াস প্লেন: ३-ডিজাইনের সমন্বয়গত কাঠামো হিসাবে
  • হাইপারসারফেস জ্যামিতি: দ্বিঘাত, চতুর্ঘাত ইত্যাদি বীজগণিতীয় বৈচিত্র্যের জ্যামিতিক বৈশিষ্ট্য

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

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

१. অস্তিত্ব উপপাদ্য: যেকোনো বিজোড় মৌলিক শক্তি q এর জন্য, তিনটি অ্যান্টি-কোসার্কুলার ট্রাংকেটেড মোবিয়াস প্লেন বিদ্যমান

२. নির্মাণ উপপাদ্য: এই জ্যামিতিক কাঠামোর উপর ভিত্তি করে শক্তি ४ কভারিং অ্যারে স্পষ্টভাবে নির্মাণ করা যায়

३. কর্মক্ষমতা উপপাদ্য: নতুন নির্মাণ একাধিক পরামিতিতে পরিচিত সর্বোত্তম ফলাফল অর্জন করে

সীমাবদ্ধতা

१. বিজোড় মৌলিক শক্তি সীমাবদ্ধতা: বর্তমান ফলাফল শুধুমাত্র বিজোড় মৌলিক শক্তিতে প্রযোজ্য, সমান মৌলিক শক্তির ক্ষেত্রে এখনও সমাধান অপেক্ষা করছে

२. পরামিতি পরিসীমা: যদিও উল্লেখযোগ্য উন্নতি রয়েছে, কিন্তু শুধুমাত্র নির্দিষ্ট পরামিতি পরিসীমায় কার্যকর

३. গণনামূলক জটিলতা: নির্মাণ প্রক্রিয়া জটিল বীজগণিতীয় গণনা জড়িত, বাস্তব বাস্তবায়ন চ্যালেঞ্জের সম্মুখীন হতে পারে

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

१. শক্তি ५ সাধারণীকরণ: লেখকরা শক্তি ५ কভারিং অ্যারে নির্মাণের সম্ভাবনা উল্লেখ করেছেন

२. সমান মৌলিক শক্তি সম্প্রসারণ: সমান মৌলিক শক্তির জন্য অনুরূপ নির্মাণ খুঁজে বের করা

३. পুনরাবৃত্তিমূলক অপ্টিমাইজেশন: পুনরাবৃত্তিমূলক নির্মাণ উন্নত করে আরও ভাল পরামিতি অর্জন করা

४. গণনামূলক বাস্তবায়ন: এই তাত্ত্বিক নির্মাণগুলি বাস্তবায়নের জন্য দক্ষ অ্যালগরিদম বিকাশ করা

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

সুবিধা

१. তাত্ত্বিক গভীরতা: বিমূর্ত জ্যামিতিক তত্ত্ব এবং কংক্রিট সমন্বয়গত নির্মাণ সমস্যা নিখুঁতভাবে একত্রিত করা

२. উদ্ভাবনী শক্তি: অ্যান্টি-কোসার্কুলার ধারণার প্রস্তাব এই ক্ষেত্রে নতুন গবেষণা দিকনির্দেশনা খুলে দেয়

३. উল্লেখযোগ্য ফলাফল: २५% কর্মক্ষমতা উন্নতি এই ক্ষেত্রে একটি প্রধান অগ্রগতি

४. পদ্ধতি পদ্ধতিগত: তাত্ত্বিক প্রমাণ থেকে কংক্রিট নির্মাণ পর্যন্ত, একটি সম্পূর্ণ পদ্ধতি ব্যবস্থা গঠন করে

५. লেখার স্পষ্টতা: জটিল জ্যামিতি এবং বীজগণিতীয় ধারণা স্পষ্টভাবে ব্যাখ্যা করা হয়েছে

অসুবিধা

१. প্রযোজ্যতার পরিসীমা: শুধুমাত্র বিজোড় মৌলিক শক্তিতে সীমাবদ্ধ, পদ্ধতির সর্বজনীনতা সীমিত করে

२. গণনামূলক জটিলতা: যদিও স্পষ্ট নির্মাণ প্রদান করা হয়েছে, বাস্তব গণনা এখনও জটিল

३. পরীক্ষামূলক যাচাইকরণ: তাত্ত্বিক কাজ হিসাবে, বড় আকারের গণনামূলক যাচাইকরণের অভাব রয়েছে

४. প্রয়োগ বিশ্লেষণ: বাস্তব সফটওয়্যার পরীক্ষা প্রয়োগের জন্য আলোচনা তুলনামূলকভাবে কম

প্রভাব

१. একাডেমিক মূল্য: কভারিং অ্যারে তত্ত্বে নতুন জ্যামিতিক দৃষ্টিভঙ্গি প্রদান করে, আরও গবেষণা অনুপ্রাণিত করতে পারে

२. ব্যবহারিক মূল্য: উল্লেখযোগ্য কর্মক্ষমতা উন্নতি সফটওয়্যার পরীক্ষা ইত্যাদি প্রয়োগ ক্ষেত্রে সরাসরি মূল্য রয়েছে

३. পদ্ধতিগত অবদান: প্রতিষ্ঠিত জ্যামিতি-বীজগণিত কাঠামো অন্যান্য সমন্বয়গত অপ্টিমাইজেশন সমস্যায় প্রযোজ্য হতে পারে

४. সম্প্রসারণযোগ্যতা: শক্তি ५ এবং উচ্চতর শক্তির কভারিং অ্যারে নির্মাণের ভিত্তি স্থাপন করে

প্রযোজ্য পরিস্থিতি

१. সফটওয়্যার পরীক্ষা: বড় আকারের সফটওয়্যার সিস্টেমের সমন্বয়গত পরীক্ষা কেস জেনারেশন

२. পরীক্ষামূলক ডিজাইন: পরিসংখ্যানে অর্থোগোনাল পরীক্ষা ডিজাইন

३. কোডিং তত্ত্ব: ত্রুটি সংশোধন কোডের নির্মাণ এবং বিশ্লেষণ

४. ক্রিপ্টোগ্রাফি: কিছু ক্রিপ্টোগ্রাফিক প্রোটোকলের নিরাপত্তা বিশ্লেষণ

তথ্যসূত্র

পেপারটি ३३টি সম্পর্কিত তথ্যসূত্র উদ্ধৃত করে, প্রধানত অন্তর্ভুক্ত করে:

  • জ্যামিতিক তত্ত্বের ভিত্তি: প্রজেক্টিভ জ্যামিতির ক্লাসিক পাঠ্যপুস্তক
  • অর্থোগোনাল প্লেন তত্ত্ব: অগ্রগামী কাজ
  • কভারিং অ্যারে তত্ত্ব: সংক্ষিপ্ত সাহিত্য
  • গণনামূলক পদ্ধতি: নির্মাণমূলক ফলাফল

সামগ্রিক মূল্যায়ন: এটি একটি উৎকৃষ্ট পেপার যেখানে তাত্ত্বিক গভীরতা এবং ব্যবহারিক মূল্য উভয়ই রয়েছে। চতুর জ্যামিতিক নির্মাণের মাধ্যমে কভারিং অ্যারে তত্ত্বে একটি গুরুত্বপূর্ণ সমস্যা সমাধান করে, এই ক্ষেত্রের উন্নয়নে গুরুত্বপূর্ণ অবদান রাখে। যদিও কিছু সীমাবদ্ধতা রয়েছে, তবে এর উদ্ভাবনী পদ্ধতি এবং উল্লেখযোগ্য ফলাফল এটিকে এই ক্ষেত্রের একটি গুরুত্বপূর্ণ অগ্রগতি করে তোলে।