اختبار الترابط الضوئي

في الرياضيات ، يُعد اختبار التجميع لـ لايت إجراءً ابتكره إف دبليو لايت لاختبار ما إذا كانت عملية ثنائية مُعرَّفة في مجموعة منتهية بواسطة جدول ضرب كايلي تجميعية . الإجراء البسيط للتحقق من تجميعية عملية ثنائية مُحدَّدة بواسطة جدول كايلي، والذي يقارن بين الناتجين اللذين يمكن تكوينهما من كل ثلاثية من العناصر، مُعقَّد. يُبسِّط اختبار التجميع لـ لايت المهمة في بعض الحالات (على الرغم من أنه لا يُحسِّن وقت التشغيل في أسوأ الحالات للخوارزمية البسيطة، أي${\displaystyle {\mathcal {O}}\left(n^{3}\right)}$لمجموعات من الأحجام${\displaystyle n}$).

لنفترض أن العملية الثنائية '·' معرفة في مجموعة منتهية A بواسطة جدول كايلي. باختيار عنصر a من A ، تُعرَّف عمليتان ثنائيتان جديدتان في A كما يلي:

${\displaystyle x\star y=x\cdot (a\cdot y)}$

${\displaystyle x\circ y=(x\cdot a)\cdot y}$

يتم إنشاء جداول كايلي لهذه العمليات ومقارنتها. إذا تطابقت الجداول،${\displaystyle x\cdot (a\cdot y)=(x\cdot a)\cdot y}$لكل x و y . يتم تكرار هذا لكل عنصر من عناصر المجموعة A.

يوضح المثال أدناه تبسيطًا إضافيًا في إجراء إنشاء ومقارنة جداول كايلي للعمليات${\displaystyle \star }$' و '${\displaystyle \circ }$'.

ليس من الضروري حتى إنشاء جداول كايلي الخاصة بـ${\displaystyle \star }$' و '${\displaystyle \circ }$لجميع عناصر المجموعة A. يكفي مقارنة جداول كايلي الخاصة بـ${\displaystyle \star }$' و '${\displaystyle \circ }$'المقابلة للعناصر في مجموعة فرعية مولدة مناسبة من A.

عندما تكون العملية '·' تبديلية ، فإن x${\displaystyle \star }$ص = ص${\displaystyle \circ }$x. ونتيجة لذلك، يجب حساب جزء فقط من كل جدول من جداول كايلي، لأن x${\displaystyle \star }$س = س${\displaystyle \circ }$x دائمًا ما يكون صحيحًا، و x${\displaystyle \star }$ص = س${\displaystyle \circ }$y يستلزم y${\displaystyle \star }$س = ص${\displaystyle \circ }$x.

عندما يكون هناك عنصر محايد e، فلا يلزم تضمينه في جداول كايلي لأن x${\displaystyle \star }$ص = س${\displaystyle \circ }$يتحقق الشرط y دائمًا إذا كان أحد الشرطين x أو y على الأقل يساوي e.

ضع في اعتبارك العملية الثنائية ' · ' في المجموعة A = { a , b , c , d , e } المعرفة بواسطة جدول كايلي التالي (الجدول 1):

المجموعة { c , e } هي مجموعة مولدة للمجموعة A في ظل العملية الثنائية المحددة في الجدول أعلاه، حيث a = e · e ، وb = c · c ، وd = c · e . وبالتالي، يكفي التحقق من أن العمليات الثنائية '${\displaystyle \star }$' و '${\displaystyle \circ }$«المقابل لـ c يتطابق، وكذلك العمليات الثنائية»${\displaystyle \star }$' و '${\displaystyle \circ }$' يتوافق مع e يتطابق.

للتحقق من أن العمليات الثنائية '${\displaystyle \star }$' و '${\displaystyle \circ }$إذا تطابقت القيم المقابلة للعنصر c ، فاختر الصف في الجدول 1 المقابل للعنصر c :

يتم نسخ هذا الصف كصف رأس لجدول جديد (الجدول 3):

تحت العنوان "أ"، انسخ العمود المقابل في الجدول 1، وتحت العنوان " ب" ، انسخ العمود المقابل في الجدول 1، وهكذا، وقم بإنشاء الجدول 4.

تم حذف عناوين الأعمدة في الجدول 4 للحصول على الجدول 5:

جدول كايلي للعملية الثنائية${\displaystyle \star }$يتم تحديد العنصر المقابل للعنصر c بواسطة الجدول 6.

الجدول 6

${\displaystyle \star }$(ج)	أ	ب	ج	د	هـ
أ	أ	أ	أ	د	د
ب	أ	ج	ب	د	د
ج	أ	ب	ج	د	د
د	د	د	د	أ	أ
هـ	د	هـ	هـ	أ	أ

ثم اختر العمود ج من الجدول 1:

انسخ هذا العمود إلى عمود الفهرس للحصول على الجدول 8:

قم بنسخ الصف المقابل في الجدول 1 مقابل مدخل الفهرس أ في الجدول 8، وقم بنسخ الصف المقابل في الجدول 1 مقابل مدخل الفهرس ب ، وهكذا، وقم بإنشاء الجدول 9.

تم الآن حذف إدخالات الفهرس في العمود الأول من الجدول 9 للحصول على الجدول 10:

جدول كايلي للعملية الثنائية${\displaystyle \circ }$يتم تحديد العنصر المقابل للعنصر c بواسطة الجدول 11.

الجدول 11

${\displaystyle \circ }$(ج)	أ	ب	ج	د	هـ
أ	أ	أ	أ	د	د
ب	أ	ج	ب	د	د
ج	أ	ب	ج	د	د
د	د	د	د	أ	أ
هـ	د	هـ	هـ	أ	أ

يمكن التحقق من أن القيم في خلايا الجدول 6 تتطابق مع القيم في الخلايا المقابلة لها في الجدول 11. وهذا يدل على أن x · ( c · y ) = ( x · c ) · y لجميع قيم x و y في A. ولو كان هناك أي اختلاف، لما كان صحيحًا أن x · ( c · y ) = ( x · c ) · y لجميع قيم x و y في A.

يمكن التحقق من أن x · ( e · y ) = ( x · e ) · y لجميع x و y في A بطريقة مماثلة عن طريق إنشاء الجداول التالية (الجدول 12 والجدول 13):

الجدول 12

${\displaystyle \star }$( هـ )	أ	ب	ج	د	هـ
أ	د	د	د	أ	أ
ب	د	د	د	أ	أ
ج	د	د	د	أ	أ
د	أ	أ	أ	د	د
هـ	أ	أ	أ	د	د

الجدول 13

${\displaystyle \circ }$( هـ )	أ	ب	ج	د	هـ
أ	د	د	د	أ	أ
ب	د	د	د	أ	أ
ج	د	د	د	أ	أ
د	أ	أ	أ	د	د
هـ	أ	أ	أ	د	د

يمكن كتابة برامج حاسوبية لإجراء اختبار التجميع لـ Light. وقد طور Kehayopulu و Argyris برنامجًا كهذا لبرنامج Mathematica . ^{[ 1 ]}

يمكن توسيع اختبار الترابط الخاص بـ "لايت" لاختبار الترابط في سياق أكثر عمومية. ^{[ 2 ] [ 3 ]}

ليكن T = { t ₁ , t ₂ ,${\displaystyle \ldots }$_{ليكن { x1} , x2 , t, _m } صهارة يُرمز فيها للعملية بالتجاور . ليكن X = { x1 , x2 , _t , m }${\displaystyle \ldots }$لتكن {t , x, _n } مجموعة. ولتكن هناك دالة من حاصل الضرب الديكارتي T × X إلى X يُرمز لها بـ ( t , x ) ↦ tx ، وليكن المطلوب اختبار ما إذا كانت هذه الدالة تمتلك الخاصية التالية:

( st ) x = s ( tx ) لجميع s ، t في T وجميع x في X .

يمكن تطبيق تعميم لاختبار التجميع لـ Light للتحقق مما إذا كانت الخاصية المذكورة أعلاه صحيحة أم لا. رياضياً، يكون التعميم كما يلي: لكل t في T ، ليكن L ( t ) مصفوفة m × n لعناصر X التي يكون صفها i هو

(( t _i t ) x ₁ , ( t _i t ) x ₂ ,${\displaystyle \ldots }$، ( t _i t ) x _n ) لـ i = 1،${\displaystyle \ldots }$، م

ولتكن R ( t ) مصفوفة من الرتبة m × n لعناصر X ، وعناصر عمودها j هي

( t ₁ ( tx _j ), t ₂ ( tx _j ),${\displaystyle \ldots }$، t _m ( tx _j ) ) لـ j = 1،${\displaystyle \ldots }$، ن .

وفقًا للاختبار المعمم (الذي وضعه بيدناريك)، فإن الخاصية المراد التحقق منها تتحقق إذا وفقط إذا كان L ( t ) = R ( t ) لجميع قيم t في T. عندما X = T ، يختزل اختبار بيدناريك إلى اختبار لايت.

توجد خوارزمية عشوائية من تطوير راجاغوبالان وشولمان لاختبار خاصية التجميع في وقت يتناسب مع حجم المدخلات. (تعمل هذه الطريقة أيضًا لاختبار بعض الهويات الأخرى). تحديدًا، زمن التشغيل هو${\displaystyle O(n^{2}\log {\frac {1}{\delta }})}$لـ${\displaystyle n\times n}$الجدول واحتمالية الخطأ${\displaystyle \delta }$يمكن تعديل الخوارزمية لإنتاج ثلاثية${\displaystyle \langle a,b,c\rangle }$والتي${\displaystyle (ab)c\neq a(bc)}$إن وُجد واحد، مع مرور الوقت${\displaystyle O(n^{2}\log n\cdot \log {\frac {1}{\delta }})}$[ ^{4 ]​}

• كليفورد، ألفريد هوبليتزيل ؛ بريستون، جوردون بامفورد (1961). النظرية الجبرية لأنصاف الزمر. المجلد الأول . دراسات رياضية، العدد 7. بروفيدنس، رود آيلاند: الجمعية الرياضية الأمريكية . ISBN 978-0-8218-0272-4MR 0132791 .​ {{cite book}}: عدم توافق رقم ISBN / التاريخ ( مساعدة ) (الصفحات  7-9 )