[MD-sorular] idempotent ve bir üst sınır sorusu

25 Tem 2010 Paz 15:26:23 EEST

Hemen belirteyim, altlara doğru örnek vereceğim.

Kendisiyle çarpıp ne zaman birime eşit olduğuna bakmak derken, kendisiyle
çarpıp ne zaman kendisine eşit olacak diye bakmayı kastediyorsunuz sanırım,
çünkü o şekilde de birimi bulabiliriz. Ben şöyle varsaydım, elimizdeki
elemanlar arasında birim var ama hangisinin birim olduğunu bilmiyoruz.
Mesela çok absürd matrisler şeklinde verilebilir elemanlar. Birim kendini
hemen belli etmeyebilir. Tamam, bazı durumlarda elemanlara (ya da bir takım
başka verilere belki) bakarak hemen falanca gruba izomorf bu denilebilir,
ama burada öyle bir durum olmadığını varsayalım.

Aklıma bir soru takıldı sizin postanız üzerine.

*Bir grupta her adımda belli bir elemanın güçleri olan iki elemanı çarparak
(önceki adımlarda bulunan elemanları kullanmak serbest) bir elemanın kaçıncı
gücünün kendisi ettiğini X adımda bulalım. X için |G| cinsinden bir üst
sınır nedir?*
*
*
*Bu soruyu örnekle açıklayacağım. Bence ilginç şeyler var.*

Not: Sadece bir eleman kullanıyoruz ve yukarıda da dediğim gibi çarpacağımız
elemanlar başta işe başladığımız elemanların güçleri olmak zorunda, soruyu
böyle soruyorum.

İlk paragrafta bahsettiğim ve sanırım Zati Lokum'un da kastettiği gibi bir
elemanı kendisiyle çarparak ne zaman kendisine eşit olacağını bulduğumuz
anda aslında hem 1'i, hem de o elemanın tersini bulmuş oluruz. Çünkü,
basitçe görüleceği üzere,

(Toplamsal olarak yazıyorum, yani x^n yerine nx.)

n>=2, nx=x ise 1=(n-1)x, -x=(n-2)x.

Örnek:

Diyelim 30 tane eleman verildi ve bunlar arasından x elemanını kullanarak
birimi ve x'in tersini, -x'i, bulmak istiyoruz.

Algoritma 1:

x'in gücünü bir artırarak ne zaman kendisini bulacağına bak. x'i bulunca
dur.

Yani,

x.x=2x, x.x=3x, (3x).x=4x, ... Bunların x edip etmediğine bak. Bu arada x'in
herhangi iki elemanını çarpmanın aynı zorlukta olduğunu varsayıyorum.
Mesela, öyle olur ki Bir matrisin 6. kuvvetinde çok karışık girdiler vardır,
o yüzden bu matrisi x ile çarpmak çok zordur. Bunlara girmiyoruz... Burada
x.x işlemini yapmak ne kadar zorsa ya da hafızada ne kadar yer tutarsa işte
(6x).x veya misal, (6x).(5x) aynı zorlukta, hafızada aynı miktar yer
kaplıyopr falan diye düşünelim. Yani biz işin sadece adım kısmına konsantre
olalım.

Algoritma 2:

Zati Lokum'un dediği gibi Lagrange teoremini kullanalım.

30'un bölenleri: 1, 2, 3, 6, 10, 12, 15, 30

Önce 2. güce bakalım x mi diye. Sonra 3x=x mi, sonra,...

2...  x.x=2x (1 işlem)
3...  (2x).x=3x (1 işlem)
4.... Bakmıyoruz: 4, 30'u bölmez. O yüzden bu adımı atlayarak hızlanıyoruz,
sağol Lagrange.
5.... Geç
6... 3x.3x (1 işlem)
10... 6x.3x.x (Dikkat: 2 işlem)

Ayrıca burada bence ilginç bir şey var. Şimdi, tamam, 10x'i bulmak için önce
9x'i mi yoksa 4x'i mi bulduğumuz önemli olmayabilir ama ileride belki 9x çok
lazım olacak... Bunu önceden kestirebilsek güzel olur, gerçi burada fark
etmiyor... Bu düşünce üst sınır bulmada işe yarayabilir.

12: 6x.6x (Bir işlem)
15: (12x).(3x) (Bir işlem)

Dikkat edilirse çarptığım elemanlar x'in güçleri ve daha önceden bulduğumuz
güçleri kullanıyoruz. Toplam 7 adımda bulduk. Aslında ufak bir hata yaptım
ama geriye dönmek istemiyorum. 15x=x mi diye bakmaktansa 16x=x mi diye
bakmamız lazımdı ve gerideki adımlarda da öyle... Ama 16'dan sonra taa 31'e
kadar bakmamıza gerek yok... 16x=x olmuyorsa x'in mertebesi 30'dur. Neyse
devam edelim.

26 eleman olsaydı, 26'nın bölenleri 1, 2, 13, 16

2: x.x (1 işem)
13: 2x.2x=4x (Tek işlem)
     4x.4x=8x (Tek işlem)
     8x.4x.x=13x (3 işlem)

Burada 5 işlem var.

Özetle 30 elemanlı bir grup için 7 adım, 26 elemanlı bir grup için 5 adım.
(Gerçi bunlar yanlış değerler. Güçleri kontrol ederken bölenlerin bir
fazlalarına bakmalıydım...)

Benim bulduğum üstsınırlar:

|G|                (2x ten başlarak (|G+1|x'e kadar kontrol etmek)
Daha iyi bir üstsınır [|G|]/2
Daha iyisini bulan var mı?

Biraz ince hatalar olabilir, onlara girmiyorum. Sonuçta ben fikirleri ifade
etmek istedim.

Bu arada Ezgi Kantarcı'nın ayırdığı kümelere tekrar dönersek,

1, tersi kendisi olanlar, bazıları, bazılarının tersleri

Son iki kümeye bakalım, son iki kümenin birleşiminde 4 eleman varsa bir
tespitim var. Diyelim bu elemanlar x, -x, y, -y

Diyelim x'in tersini bulmak istiyoruz. x'in mertebesi çok yüksek olabilir.
Bir kere mertebenin 2 olmadığı açık zaten, yoksa x tersi kendisi olanlar
kümesinde olurdu. Bu durumda bir senaryo yazıyorum. Diyelim çok yüksek bir
köprüden karşıya geçeceğiz ama köprü tahta. Girişte bir cihaz var size bir
eleman veriyor, hemen o elemanın tersini bulmazsanız köprüye giriş kapısı
açılmıyor. Siz de uçurumda kalıp açlık tehlikesiyle karşı karşıyasınız. Yani
hemen karar vermeniz gerekiyor. Diyelim xin bir gücünü de almak 2 saniye
sürüyor ama sizin de zamanınız yok. Şöyle yaparsınız Geri kalan üç elemanı
çarparsınız! Eğer -x ortaya gelmezse güzel. Ki gelmeme olasılığı 2/3. Yani
-xy-y, y-y-x çarpımları -x ediyor. Sadece y-x-y durumunda tersi
bulamıyorsunuz. İşin içerisne olasılık terosii de girebilir. Ben ters ve güç
bulmayla uğraşırken birimi bulma olasılığı ve  aklıma şu üç kapılı meşhur
olasılık sorusu geldi. Ondan da da bir sonraki mailde bahsedeceğim.

Metin

24 Temmuz 2010 19:02 tarihinde zati lokum <zati.lokum at gmail.com> yazdı:

> 2. yazdığınız yol baya uzun sürer, çünkü tek tek ters arıyorsunuz. Grup
> sonlu ise ve birim varsa elemanı kendisiyle çarpıp ne zaman birime eşit
> olduğunu bulmak daha kolay (efficient) sanırım. Grup hele de çok büyükse, en
> azından elemanın orderı grubun orderını böler, yani daha küçüktür. Daha iyi
> yöntem olabilir. Çok güzel soruymuş.
>
> Zati
>
> 2010/7/24 Metin Odun <metamaths at gmail.com>
>
>  Sizin dediğiniz 4 kümeye ayırma işlemi için şöyle bir algortma düşündüm.
>>
>> 1- Bir grupta biricik idempotent olduğundan, her elemanı kendisiyle çarpıp
>> kendisine eşit mi diye bakarız. Böylece birimi tespit ederiz.
>> 2- Artık elimizde birim eleman olduğundan, her elemanı kendisiyle çarpıp
>> birime eşit mi diye bakarız, eşit olanların tersleri kendileridir. Ve geriye
>> kalan elemanlar da tersleri kendisine eşit olmayanlardır. Geriye tek sayıda
>> eleman kalırsa ilk verilen elemanların grup oluşturmadığı anlaşılır. Ama
>> tersi kendisi olmayanları iki kümeye bölmek için (kendileri ve tersleri diye
>> iki küme) iyi bir yol bulamadım. Bunun için, mesela bir elemanı alıp tek tek
>> diğerleriyle çarparız, birimi bulursak eldeki elemanın da tersini bulmuş
>> oluruz.
>>
>> Metin
>>
>> 24 Temmuz 2010 12:10 tarihinde Metin Odun <metamaths at gmail.com> yazdı:
>>
>>> m + n^2 -n + 2nm <= (1+n+2m)^2. olacak.
>>>
>>> 24 Temmuz 2010 12:09 tarihinde Metin Odun <metamaths at gmail.com> yazdı:
>>>
>>>  Teşekkürler. Bu biraz geliştirilebilir belki ama keyfi bir grup için
>>>> pek sanmıyorum. Sonuçta bu bulduğunuz bir upper bound, yani 2m^2 -m + n^2 -n
>>>> + 2nm <= (1+m+2m)^2. Ve daha iyi boundlar olabilir, en azından bazı gruplar
>>>> için bu soru çok zor olabilir. Açıkçası internette aradım ama bulamadım.
>>>>
>>>> Go:kh at n Zeytin'in bir mesajı var: "Bir küme ve o küme üzerinde ikili
>>>> işlem tanımı gereği kapalılığı göstermeye gerek yoktur. Çünkü o küme
>>>> üzerindeki işlemde birleşme, etkisiz eleman, ters eleman özelliği bilinirken
>>>> grup için yeterli şartlar sağlanmış olur. A boştan farklı küme olmak üzere
>>>>
>>>> * : AxA -) A   ikili işlem tanımlı olduğundan kapalılık göstermeye gerek
>>>> yok. Küme üzerinde ikili işlem tanımlı olduğunu bilmek yeterli."
>>>>
>>>> Bu arada Ali Nesin'in bir evvelki matematiksel soruma verdiği tek
>>>> cümlelik yanıtı daha iyi anladım. O cümle trivial caseleri ekarte edip
>>>> herşeyi ortaya koyuyordu, üzerine mesaj yazmam gereksizdi. Derin bir
>>>> cümleydi.
>>>>
>>>> 24 Temmuz 2010 00:35 tarihinde Ezgi Kantarcı <ezzzgi at gmail.com> yazdı:
>>>>
>>>> Merhaba,
>>>>>
>>>>> Birleşmelilik ve ters elemanların verdiği avantaj, mesela tersi -
>>>>> olarak düşünürsek, a,-a,b,-b dört elemansa diyelim,
>>>>> normalde a+b, a-b, -a+b, -a+b, b+a, b-a,-b+a,-b-a'yı kontrol
>>>>> edeceksek, onun yerine a+b, a-b, b+a, b-a'yı kontol etmemizin yeterli
>>>>> olması.
>>>>>
>>>>> grubu ayrık dört parçaya ayırdık diyelim: 0 (etkisiz eleman), tersi
>>>>> kendisi olan 0 dışındaki elemanlar, "bazı elemanlar", onların tersleri
>>>>> olarak.
>>>>> diyelim ki bu grupların eleman sayıları sırayla 1,n,m ve m. O zaman
>>>>> "bazı elemanlar" arasından a,b ikilileri seçip onlar için a+b, a-b,
>>>>> b+a, b-a 'ya bakarız. Bu 4 m (m-1)/2 işlem. Sonra "bazı elemanlar"daki
>>>>> her a elemanı için a+a 'ya bakarız. Bu m işlem verir. Tersi kendisi
>>>>> olan elemanlardan a,b ikilileri seçeriz ve onlar için a+b ve b+a'ya
>>>>> bakarız. Bu 2 n (n-1)/2 işlem verir. Son olarak da
>>>>> "bazı elemanlar"dan a elemanları, tersi kendisi olanlardan b
>>>>> elemanları için a+b ve b+a 'ya bakarız. Bu da 2n*m işlem verir.
>>>>> Toplam 2m^2 -m + n^2 -n + 2nm işlem oluyor.
>>>>>
>>>>> Örneğin 20 elemanlık grupta  0 dışında tersi kendisi olan tek eleman
>>>>> varsa n=1, m=9 oluyor. 171 adım.
>>>>>
>>>>> Yani çok takip edilebilir oldu mu emin değilim, işlem sayısını
>>>>> azaltmak için aklıma gelen bu şu anda.
>>>>>
>>>>> Ezgi
>>>>>
>>>>>
>>>>> 2010/7/23 Metin Odun <metamaths at gmail.com>:
>>>>>  > Bir küme ve o küme üzerinde bir işlemin birleşmeliliği, etkisiz
>>>>> eleman
>>>>> > özelliği ve ters eleman özelliğini sağladığı bilinirken kapalılığı
>>>>> > sağladığını göstermenin pratik bir yolu var mı?
>>>>> > Sadece kapalılık olsaydı soru zordu ama birleşmelilik ve ters eleman
>>>>> > özellikleri bazen adımları kısaltıyor. Belki bununla ilgili güzel bir
>>>>> örnek
>>>>> > bilen vardır. Mesela 20 tane eleman vardır. Normalde tabloda 400
>>>>> eleman var.
>>>>> > Ama belki mesela 100 küsur adımda kapalılığı gösterebiliriz...
>>>>> > Asıl soru w^3=1 olmak üzere w kullanarak (Yani sanırım "Dihedral grup
>>>>> olarak
>>>>> > kompleks matris temsili" deniyor.) S_3'e izomorf olduğu iddia edilen
>>>>> bir
>>>>> > grupla ilgiliydi. Orada w, w^2 ve w^3 kullanılarak 6 tane eleman
>>>>> verilmiş
>>>>> > matris olarak. Bunun 6 elemanlı grup olduğunu göstermekti soru.
>>>>> Kapalılığı
>>>>> > tek tek tüm elemanları bularak gösterdim, bir-iki yerde işlem kısaldı
>>>>> ama bu
>>>>> > yol genelde uzun.
>>>>> > Yukarıdaki soru oradan aklıma geldi.
>>>>> > _______________________________________________
>>>>> > MD-sorular e-posta listesi
>>>>> > sorular at matematikdunyasi.org
>>>>> > http://lists.math.bilgi.edu.tr/cgi-bin/mailman/listinfo/md-sorular
>>>>> >
>>>>>
>>>>
>>>>
>>>
>>
>> _______________________________________________
>> MD-sorular e-posta listesi
>> sorular at matematikdunyasi.org
>> http://lists.math.bilgi.edu.tr/cgi-bin/mailman/listinfo/md-sorular
>>
>
>
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: <http://lists.math.bilgi.edu.tr/pipermail/md-sorular/attachments/20100725/0904c7a0/attachment.htm>