Işık çağrışım testi - Lights associativity test

İçinde matematik, Light'ın çağrışım testi F.W. Light tarafından geliştirilen bir prosedür olup olmadığını test etmek için ikili işlem bir Sınırlı set tarafından Cayley çarpım tablosu dır-dir ilişkisel. Her üçlü elemandan oluşturulabilen iki ürünü karşılaştıran, bir Cayley tablosu tarafından belirlenen ikili işlemin birleşebilirliğinin doğrulanması için naif prosedür, zahmetlidir. Light'ın çağrışım testi, bazı durumlarda görevi basitleştirir (saf algoritmanın en kötü durumdaki çalışma zamanını iyileştirmese de, yani ${ displaystyle { mathcal {O}} sol (n ^ {3} sağ)}$ boyut setleri için ${ displaystyle n}$).

Prosedürün açıklaması

İkili işlem '·' sonlu bir kümede tanımlansın Bir bir Cayley masası tarafından. Bazı unsurları seçmek a içinde Biriki yeni ikili işlem tanımlanmıştır Bir aşağıdaki gibi:

x ${ displaystyle yıldız}$ y = x · ( a · y )

x ${ displaystyle circ}$ y = ( x · a ) · y

Bu işlemlerin Cayley tabloları oluşturulmuş ve karşılaştırılmıştır. Tablolar çakışırsa o zaman x · ( a · y ) = ( x · a ) · y hepsi için x ve y. Bu, setin her öğesi için tekrarlanır Bir.

Aşağıdaki örnek, işlemlerin Cayley tablolarının oluşturulması ve karşılaştırılması için prosedürde daha fazla basitleştirmeyi göstermektedir. ${ displaystyle yıldız}$ ' ve ' ${ displaystyle circ}$ '.

Cayley tablolarını inşa etmek bile gerekli değildir. ${ displaystyle yıldız}$ ' ve ' ${ displaystyle circ}$ ' için herşey unsurları Bir. Cayley tablolarını karşılaştırmak yeterlidir. ${ displaystyle yıldız}$ ' ve ' ${ displaystyle circ}$ uygun bir üretici alt kümesindeki öğelere karşılık gelir Bir.

İşlem ne zaman '. ' dır-dir değişmeli, sonra x ${ displaystyle yıldız}$ y = y ${ displaystyle circ}$ x. Sonuç olarak, her bir Cayley tablosunun yalnızca bir kısmı hesaplanmalıdır çünkü x ${ displaystyle yıldız}$ x = x ${ displaystyle circ}$ x her zaman tutar ve x ${ displaystyle yıldız}$ y = x ${ displaystyle circ}$ y, y anlamına gelir ${ displaystyle yıldız}$ x = y ${ displaystyle circ}$ x.

Ne zaman bir kimlik öğesi e, Cayley tablolarına dahil edilmesine gerek yoktur çünkü x ${ displaystyle yıldız}$ y = x ${ displaystyle circ}$ x ve y'den en az biri e'ye eşitse y her zaman tutar.

Misal

Küme içindeki '·' ikili işlemi düşünün Bir = { a, b, c, d, e } aşağıdaki Cayley tablosu ile tanımlanmıştır (Tablo 1):

tablo 1

·	a	b	c	d	e
a	a	a	a	d	d
b	a	b	c	d	d
c	a	c	b	d	d
d	d	d	d	a	a
e	d	e	e	a	a

Set { c, e }, küme için bir üretici kümesidir Bir yukarıdaki tabloda tanımlanan ikili işlem altında, a = e · e, b = c · c, d = c · e. Bu nedenle, ikili işlemlerin ' ${ displaystyle yıldız}$ ' ve ' ${ displaystyle circ}$ karşılık gelen c çakışır ve ayrıca ikili işlemlerin ${ displaystyle yıldız}$ ' ve ' ${ displaystyle circ}$ karşılık gelen e çakıştı.

İkili işlemlerin ' ${ displaystyle yıldız}$ ' ve ' ${ displaystyle circ}$ karşılık gelen c çakışırsa, öğeye karşılık gelen Tablo 1'deki satırı seçin c:

Tablo 2

·	a	b	c	d	e
a	a	a	a	d	d
b	a	b	c	d	d
c	a	c	b	d	d
d	d	d	d	a	a
e	d	e	e	a	a

Bu satır, yeni bir tablonun başlık satırı olarak kopyalanır (Tablo 3):

Tablo 3

	a	c	b	d	d

Başlığın altında a başlığın altındaki Tablo 1'deki ilgili sütunu kopyalayın b İlgili sütunu Tablo 1, vb. içinde kopyalayın ve Tablo 4'ü oluşturun.

Tablo 4

	a	c	b	d	d
	a	a	a	d	d
	a	c	b	d	d
	a	b	c	d	d
	d	d	d	a	a
	d	e	e	a	a

Tablo 4'ün sütun başlıkları artık Tablo 5'i almak için silinmiştir:

Tablo 5

	a	a	a	d	d
	a	c	b	d	d
	a	b	c	d	d
	d	d	d	a	a
	d	e	e	a	a

İkili işlemin Cayley tablosu ' ${ displaystyle yıldız}$ öğeye karşılık gelen c Tablo 6'da verilmiştir.

Tablo 6

${ displaystyle yıldız}$ (c)	a	b	c	d	e
a	a	a	a	d	d
b	a	c	b	d	d
c	a	b	c	d	d
d	d	d	d	a	a
e	d	e	e	a	a

Sonra şunu seçin c Tablo 1 sütunu:

Tablo 7

·	a	b	c	d	e
a	a	a	a	d	d
b	a	b	c	d	d
c	a	c	b	d	d
d	d	d	d	a	a
e	d	e	e	a	a

Tablo 8'i almak için bu sütunu dizin sütununa kopyalayın:

Tablo 8

a
c
b
d
e

Dizin girişine karşı a Tablo 8'de Tablo 1'deki ilgili satırı indeks girişine karşı kopyalayın b Tablo 1'deki ilgili satırı kopyalayın, vb. ve Tablo 9'u oluşturun.

Tablo 9

a	a	a	a	d	d
c	a	c	b	d	d
b	a	b	c	d	d
d	d	d	d	a	a
e	d	e	e	a	a

Tablo 9'un ilk sütunundaki dizin girişleri, Tablo 10'u almak için silinmiştir:

Tablo 10

	a	a	a	d	d
	a	c	b	d	d
	a	b	c	d	d
	d	d	d	a	a
	d	e	e	a	a

İkili işlemin Cayley tablosu ' ${ displaystyle circ}$ öğeye karşılık gelen c Tablo 11'de verilmiştir.

Tablo 11

${ displaystyle circ}$(c)	a	b	c	d	e
a	a	a	a	d	d
b	a	c	b	d	d
c	a	b	c	d	d
d	d	d	d	a	a
e	d	e	e	a	a

Tablo 6'daki çeşitli hücrelerdeki girişlerin Tablo 11'in karşılık gelen hücrelerindeki girişlerle uyumlu olduğu doğrulanabilir. Bu, şunu gösterir: x · ( c · y ) = ( x · c ) · y hepsi için x ve y içinde Bir. Bazı tutarsızlıklar olsaydı, o zaman bu doğru olmazdı x · ( c · y ) = ( x · c ) · y hepsi için x ve y içinde Bir.

Bu x · ( e · y ) = ( x · e ) · y hepsi için x ve y içinde Bir aşağıdaki tablolar oluşturularak benzer şekilde doğrulanabilir (Tablo 12 ve Tablo 13):

Tablo 12

${ displaystyle yıldız}$(e)	a	b	c	d	e
a	d	d	d	a	a
b	d	d	d	a	a
c	d	d	d	a	a
d	a	a	a	d	d
e	a	a	a	d	d

Tablo 13

${ displaystyle circ}$(e)	a	b	c	d	e
a	d	d	d	a	a
b	d	d	d	a	a
c	d	d	d	a	a
d	a	a	a	d	d
e	a	a	a	d	d

Daha fazla basitleştirme

İkili işlemlerin Cayley tablolarını (Tablo 6 ve tablo 11) oluşturmak gerekli değildir ' ${ displaystyle yıldız}$ ' ve ' ${ displaystyle circ}$ '. Başlığa karşılık gelen sütunu kopyalamak yeterlidir. c Tablo 1'de Tablo 5'teki dizin sütununa gidin ve aşağıdaki tabloyu (Tablo 14) oluşturun ve a- Tablo 14'ün satırı, a- Tablo 1'in satırı, b- Tablo 14'ün satırı, b- Tablo 1'in sırası, vs. Bu tekrarlanacaktır. gerekli değişiklikler yapılarak jeneratör grubunun tüm öğeleri için Bir.

Tablo 14

	a	c	b	d	d
a	a	a	a	d	d
c	a	c	b	d	d
b	a	b	c	d	d
d	d	d	d	a	a
e	d	e	e	a	a

Program

Bilgisayar yazılımı Light'ın çağrışım testini yapmak için yazılabilir. Kehayopulu ve Argyris böyle bir program geliştirdiler. Mathematica.^[1]

Uzantı

Light'ın çağrışım testi, daha genel bir bağlamda çağrışımsallığı test etmek için genişletilebilir.^[2][3]

İzin Vermek T = { t₁, t₂, ${ displaystyle ldots}$, t_m } olmak magma operasyonun gösterdiği yan yana koyma. İzin Vermek X = { x₁, x₂, ${ displaystyle ldots}$, x_n } bir küme olabilir. Bir eşleme olsun Kartezyen ürün T × X -e X ile gösterilir (t, x) ↦ tx ve bu haritanın mülke sahip olup olmadığını test etmesine izin verin

(st)x = s(tx) hepsi için s, t içinde T ve tüm x içinde X.

Light'ın çağrışım testinin bir genellemesi, yukarıdaki özelliğin geçerli olup olmadığını doğrulamak için uygulanabilir. Matematiksel gösterimlerde genelleme şu şekilde çalışır: Her biri için t içinde T, İzin Vermek L(t) ol m × n elemanlarının matrisi X kimin ben - inci sıra

( (t_bent)x₁, (t_bent)x₂, ${ displaystyle ldots}$ , (t_bent)x_n ) için ben = 1, ${ displaystyle ldots}$, m

ve izin ver R(t) ol m × n elemanlarının matrisi Xkimin unsurları j - inci sütun

( t₁(tx_j), t₂(tx_j), ${ displaystyle ldots}$ , t_m(tx_j) ) için j = 1, ${ displaystyle ldots}$, n.

Genelleştirilmiş teste göre (Bednarek'e bağlı olarak), doğrulanacak mülkün ancak ve ancak L(t) = R(t) hepsi için t içinde T. Ne zaman X = TBednarek'in testi Light'ın testine indirgenir.

Daha gelişmiş algoritmalar

Rajagopalan tarafından rastgele bir algoritma var ve Schulman İlişkilendirilebilirliği girdi boyutuyla orantılı olarak test etmek. (Yöntem aynı zamanda belirli diğer kimlikleri test etmek için de çalışır.) Özellikle, çalışma zamanı ${ displaystyle O (n ^ {2} log { frac {1} { delta}})}$ bir ... için ${ displaystyle n kere n}$ tablo ve hata olasılığı ${ displaystyle delta}$. Algoritma, üçlü oluşturmak için değiştirilebilir ${ displaystyle langle a, b, c rangle}$ hangisi için ${ displaystyle (ab) c neq a (bc)}$eğer varsa, zamanında ${ displaystyle O (n ^ {2} log n cdot log { frac {1} { delta}})}$.^[4]

Notlar

Referanslar

• Clifford, Alfred Hoblitzelle; Preston, Gordon Bamford (1961). Yarıgrupların cebirsel teorisi. Cilt ben. Matematiksel Araştırmalar, No. 7. Providence, R.I .: Amerikan Matematik Derneği. ISBN  978-0-8218-0272-4. BAY  0132791. (sayfa 7-9)