Plünnecke-Ruzsa eşitsizliği

İçinde katkı kombinasyonu, Plünnecke-Ruzsa eşitsizliği çeşitli boyutlarını sınırlayan bir eşitsizliktir toplamlar bir setin ${ displaystyle B}$ , başka bir set olduğu göz önüne alındığında ${ displaystyle A}$ Böylece ${ displaystyle A + B}$ daha büyük değil ${ displaystyle A}$ . Bu eşitsizliğin biraz daha zayıf bir versiyonu ilk olarak Helmut Plünnecke (1970) tarafından kanıtlanmış ve yayınlanmıştır.^[1]Imre Ruzsa (1989)^[2] daha sonra eşitsizliğin mevcut, daha genel versiyonunun daha basit bir kanıtını yayınladı.Eşitsizlik, ispatında çok önemli bir adım oluşturur Freiman teoremi.

Beyan

Devamındaki sumset notasyon, eklemeli kombinasyonlarda standarttır. Alt kümeler için ${ displaystyle A}$ ve ${ displaystyle B}$ bir değişmeli grup ve doğal bir sayı ${ displaystyle k}$ aşağıdakiler tanımlanmıştır:

${ displaystyle A + B = {a + b: a A'da, b B'de }}$
${ displaystyle A-B = {a-b: a A'da, b B'de }}$
${ displaystyle kA = underbrace {A + A + cdots + A} _ {k { text {zamanlar}}}}$

Set ${ displaystyle A + B}$ olarak bilinir sumset nın-nin ${ displaystyle A}$ ve ${ displaystyle B}$ .

Plünnecke-Ruzsa eşitsizliği ifadesinin en çok alıntı yapılan versiyonu şudur.^[3]

Teoremi (Plünnecke-Ruzsa eşitsizliği) — Eğer ${ displaystyle A}$ ve ${ displaystyle B}$ değişmeli bir grubun sonlu alt kümeleridir ve ${ displaystyle K}$ sabittir, öyle ki ${ displaystyle | A + B | leq K | A |}$ , sonra negatif olmayan tüm tamsayılar için ${ displaystyle m}$ ve ${ displaystyle n}$ ,

{ displaystyle | mB-nB | leq K ^ {m + n} | A |.}

Bu genellikle ne zaman kullanılır? ${ displaystyle A = B}$ , bu durumda sabit ${ displaystyle K = | 2A | / | A |}$ olarak bilinir sabiti ikiye katlamak nın-nin ${ displaystyle A}$ . Bu durumda, Plünnecke-Ruzsa eşitsizliği, küçük ikiye katlama sabiti olan bir kümeden oluşan toplamların da küçük olması gerektiğini belirtir.

Plünnecke eşitsizliği

Bu eşitsizliğin orijinal olarak Plünnecke (1970) tarafından kanıtlanmış versiyonu^[1] biraz daha zayıf.

Teoremi (Plünnecke eşitsizliği) — Varsayalım ${ displaystyle A}$ ve ${ displaystyle B}$ değişmeli bir grubun sonlu alt kümeleridir ve ${ displaystyle K}$ sabittir, öyle ki ${ displaystyle | A + B | leq K | A |}$ . Negatif olmayan tüm tamsayılar için ${ displaystyle m}$ , ${ displaystyle | mB | leq K ^ {m} | A |.}$

Kanıt

Ruzsa üçgeni eşitsizliği

Ruzsa üçgeni eşitsizliği, Plünnecke eşitsizliğini Plünnecke-Ruzsa eşitsizliğine genellemek için kullanılan önemli bir araçtır. İfadesi:

Teoremi (Ruzsa üçgen eşitsizliği) — Eğer ${ displaystyle A}$ , ${ displaystyle B}$ , ve ${ displaystyle C}$ değişmeli bir grubun sonlu alt kümeleridir, o zaman

{ displaystyle | A || B-C | leq | A-B || A-C |.}

Plünnecke-Ruzsa eşitsizliğinin kanıtı

Plünnecke-Ruzsa eşitsizliğinin aşağıdaki basit kanıtı Petridis'e (2014) bağlıdır.^[4]

Lemma: İzin Vermek ${ displaystyle A}$ ve ${ displaystyle B}$ değişmeli bir grubun sonlu alt kümeleri olmak ${ displaystyle G}$ . Eğer ${ displaystyle X subseteq A}$ değerini en aza indiren boş olmayan bir alt kümedir ${ displaystyle K '= | X + B | / | X |}$ , sonra tüm sonlu alt kümeler için ${ displaystyle C alt kümesi G}$ ,

{ displaystyle | X + B + C | leq K '| X + C |.}

Kanıt: Bu, boyuttaki tümevarımla gösterilmiştir. ${ displaystyle | C |}$ . Temel durum için ${ displaystyle | C | = 1}$ , Bunu not et ${ displaystyle S + C}$ sadece bir çevirisidir ${ displaystyle S}$ herhangi ${ displaystyle S subseteq G}$ , yani

{ displaystyle | X + B + C | = | X + B | = K '| X | = K' | X + C |.}

Endüktif adım için, eşitsizliğin herkes için geçerli olduğunu varsayın. ${ displaystyle C subseteq G}$ ile ${ displaystyle | C | leq n}$ bazı pozitif tamsayılar için ${ displaystyle n}$ . İzin Vermek ${ displaystyle C}$ alt kümesi olmak ${ displaystyle G}$ ile ${ displaystyle | C | = n + 1}$ ve izin ver ${ displaystyle C = C ' sqcup { gamma }}$ bazı $C’de { displaystyle gamma }$ . (Özellikle, eşitsizlik için geçerlidir ${ displaystyle C '}$ .) Son olarak, izin ver ${ displaystyle Z = {x in X: x + B + { gamma } subseteq X + B + C '}}$ . Tanımı ${ displaystyle Z}$ ima ediyor ki ${ displaystyle Z + B + { gamma } subseteq X + B + C '}$ . Böylece, bu setlerin tanımına göre,

{ displaystyle X + B + C = (X + B + C ') cup ((X + B + { gamma }) ters eğik çizgi (Z + B + { gamma })).}

Bu nedenle setlerin boyutları dikkate alındığında,

{ displaystyle { başlar {hizalı} | X + B + C | & leq | X + B + C '| + | (X + B + { gamma }) ters eğik çizgi (Z + B + { gamma }) | & = | X + B + C '| + | X + B + { gamma } | - | Z + B + { gamma } | & = | X + B + C '| + | X + B | - | Z + B |. End {hizalı}}}

Tanımı ${ displaystyle Z}$ ima ediyor ki ${ displaystyle Z subseteq X subseteq A}$ yani tanımına göre ${ displaystyle X}$ , ${ displaystyle | Z + B | geq K '| Z |}$ . Böylece, tümevarım hipotezinin uygulanması ${ displaystyle C '}$ ve tanımını kullanarak ${ displaystyle X}$ ,

{ displaystyle { başlar {hizalı} | X + B + C | & leq | X + B + C '| + | X + B | - | Z + B | & leq K' | X + C '| + | X + B | - | Z + B | & leq K' | X + C '| + K' | X | - | Z + B | & leq K '| X + C '| + K' | X | -K '| Z | & = K' (| X + C '| + | X | - | Z |). End {hizalı}}}

Bu eşitsizliğin sağ tarafını sınırlamak için ${ displaystyle W = {x in X: x + gamma in X + C '}}$ . Varsayalım ${ displaystyle y X + C '}$ ve ${ displaystyle y in X + { gamma }}$ o zaman var ${ displaystyle x X'te}$ öyle ki ${ displaystyle x + gamma = y X + C '}$ . Böylece, tanımı gereği, ${ displaystyle x W olarak}$ , yani ${ displaystyle y in W + { gamma }}$ . Dolayısıyla setler ${ displaystyle X + C '}$ ve ${ displaystyle (X + { gamma }) ters eğik çizgi (W + { gamma })}$ ayrık. Tanımları ${ displaystyle W}$ ve ${ displaystyle C '}$ böylece ima eder

{ displaystyle X + C = (X + C ') sqcup ((X + { gamma }) ters eğik çizgi (W + { gamma })).}

Yine tanım gereği, ${ displaystyle W subseteq Z}$ , yani ${ displaystyle | W | leq | Z |}$ . Dolayısıyla

{ displaystyle { başlar {hizalı} | X + C | & = | X + C '| + | (X + { gamma }) ters eğik çizgi (W + { gama }) | & = | X + C '| + | X + { gamma } | - | W + { gamma } | & = | X + C' | + | X | - | W | & geq | X + C '| + | X | - | Z |. End {hizalı}}}

Yukarıdaki iki eşitsizliği bir araya getirmek

{ displaystyle | X + B + C | leq K '(| X + C' | + | X | - | Z |) leq K '| X + C |.}

Bu lemmanın kanıtını tamamlar.

Plünnecke-Ruzsa eşitsizliğini kanıtlamak için ${ displaystyle X}$ ve ${ displaystyle K '}$ lemmanın ifadesindeki gibi. İlk önce bunu göstermek gerekiyor

{ displaystyle | X + nB | leq K ^ {n} | X |.}

Bu, tümevarım ile kanıtlanabilir. Temel durum için, tanımları ${ displaystyle K}$ ve ${ displaystyle K '}$ Ima etmek ${ displaystyle K ' leq K}$ . Böylece, tanımı ${ displaystyle X}$ ima ediyor ki ${ displaystyle | X + B | leq K | X |}$ . Endüktif adım için, bunun için doğru olduğunu varsayalım ${ displaystyle n = j}$ . Lemma ile uygulama ${ displaystyle C = jB}$ ve endüktif hipotez verir

{ displaystyle | X + (j + 1) B | leq K '| X + jB | leq K | X + jB | leq K ^ {j + 1} | X |.}

Bu, indüksiyonu tamamlar. Son olarak, Ruzsa üçgeni eşitsizliği verir

{ displaystyle | mB-nB | leq { frac {| X + mB || X + nB |} {| X |}} leq { frac {K ^ {m} | X | K ^ {n} | X |} {| X |}} = K ^ {m + n} | X |.}

Çünkü ${ displaystyle X subseteq A}$ durum böyle olmalı ${ displaystyle | X | leq | A |}$ . Bu nedenle,

{ displaystyle | mB-nB | leq K ^ {m + n} | A |.}

Bu, Plünnecke-Ruzsa eşitsizliğinin kanıtını tamamlar.

Plünnecke grafikleri

Plünnecke'nin Plünnecke eşitsizliğinin kanıtı ve Ruzsa'nın Plünnecke-Ruzsa eşitsizliğinin orijinal kanıtı Plünnecke grafikleri yöntemini kullanır. Plünnecke grafikleri, setlerin toplamsal yapısını yakalamanın bir yoludur ${ displaystyle A, A + B, A + 2B, noktalar}$ grafik teorik bir şekilde^[5]^[6] Plünnecke grafiklerini tanımlamak için ilk önemli olan, değişmeli grafik kavramıdır.

Tanım. Bir Yönlendirilmiş grafik ${ displaystyle G}$ denir yarı değişmeli ne zaman olursa olsun farklı ${ displaystyle x, y, z_ {1}, z_ {2}, noktalar, z_ {k}}$ öyle ki ${ displaystyle (x, y)}$ ve ${ displaystyle (y, z_ {i})}$ kenarlar ${ displaystyle G}$ her biri için ${ displaystyle i}$ , sonra da farklı ${ displaystyle y_ {1}, y_ {2}, dots, y_ {k}}$ Böylece ${ displaystyle (x, y_ {i})}$ ve ${ displaystyle (y_ {i}, z_ {i})}$ kenarlar ${ displaystyle G}$ her biri için ${ displaystyle i}$ . ${ displaystyle G}$ denir değişmeli yarı değişmeli ise ve tüm kenarlarını ters çevirerek oluşturulan grafik de yarı değişmeli.

Şimdi bir Plünnecke grafiği aşağıdaki gibi tanımlanmıştır.

Tanım. Bir katmanlı grafik (yönlendirilmiş) bir grafiktir ${ displaystyle G}$ köşe kümesi bölümlenebilen ${ displaystyle V_ {0} cup V_ {1} cup dots cup V_ {m}}$ böylece tüm kenarlar ${ displaystyle G}$ -dan ${ displaystyle V_ {i}}$ -e ${ displaystyle V_ {i + 1}}$ , bazı ${ displaystyle i}$ . Bir Plünnecke grafiği değişmeli olan katmanlı bir grafiktir.

Bir Plünnecke grafiğinin ilgili örneği, kümelerin yapısının nasıl ${ displaystyle A, A + B, A + 2B, dots, A + mB}$ Plünnecke grafiğinin bir durumudur.

Misal. İzin Vermek ${ displaystyle A, B}$ değişmeli bir grubun alt kümeleri olabilir. O halde bırak ${ displaystyle G}$ katmanlı grafik olun, böylece her katman ${ displaystyle V_ {j}}$ kopyası ${ displaystyle A + jB}$ , Böylece ${ displaystyle V_ {0} = A}$ , ${ displaystyle V_ {1} = A + B}$ , ..., ${ displaystyle V_ {m} = A + mB}$ . Kenarı yaratın ${ displaystyle (x, y)}$ (nerede ${ displaystyle x in V_ {i}}$ ve ${ displaystyle y in V_ {i + 1}}$ ) ne zaman varsa $B'de { displaystyle b }$ öyle ki ${ displaystyle y = x + b}$ . (Özellikle, eğer ${ displaystyle x in V_ {i}}$ , sonra ${ displaystyle x + b in V_ {i + 1}}$ tanım gereği, her köşede üstünlük boyutuna eşit ${ displaystyle B}$ .) Sonra ${ displaystyle G}$ bir Plünnecke grafiğidir. Örneğin, kontrol etmek için ${ displaystyle G}$ yarı değişmeli, eğer ${ displaystyle (x, y)}$ ve ${ displaystyle (y, z_ {i})}$ kenarlar ${ displaystyle G}$ her biri için ${ displaystyle i}$ , sonra $B'de { displaystyle y-x, z_ {i} -y }$ . O halde bırak ${ displaystyle y_ {i} = x + z_ {i} -y}$ , Böylece $B'de { displaystyle y_ {i} -x = z_ {i} -y }$ ve ${ displaystyle z_ {i} -y_ {i} = y-x B'de}$ . Böylece, ${ displaystyle G}$ yarı değişmeli. Benzer şekilde, tüm kenarları ters çevrilerek oluşturulan grafiğin ${ displaystyle G}$ aynı zamanda yarı değişmeli olduğu için ${ displaystyle G}$ bir Plünnecke grafiğidir.

Bir Plünnecke grafiğinde, görüntü bir setin ${ displaystyle X subseteq V_ {0}}$ içinde ${ displaystyle V_ {j}}$ , yazılı ${ displaystyle { text {im}} (X, V_ {j})}$ , içindeki tepe noktaları kümesi olarak tanımlanır ${ displaystyle V_ {j}}$ bazı köşelerden başlayan bir yolla ulaşılabilen ${ displaystyle X}$ . Özellikle yukarıda belirtilen örnekte, ${ displaystyle { text {im}} (X, V_ {j})}$ sadece ${ displaystyle X + jB}$ .

büyütme oranı arasında ${ displaystyle V_ {0}}$ ve ${ displaystyle V_ {j}}$ , belirtilen ${ displaystyle mu _ {j} (G)}$ , daha sonra bir setin görüntüsünün orijinal setin boyutunu aşması gereken minimum faktör olarak tanımlanır. Resmen,

{ displaystyle mu _ {j} (G) = min _ {X subseteq V_ {0}, X neq emptyset} { frac {| { text {im}} (X, V_ {j} ) |} {| X |}}.}

Plünnecke teoremi, Plünnecke grafikleri ile ilgili aşağıdaki ifadedir.

Teoremi (Plünnecke teoremi) — İzin Vermek ${ displaystyle G}$ bir Plünnecke grafiği olabilir. Sonra, ${ displaystyle mu _ {j} (G) ^ {1 / j}}$ azalıyor ${ displaystyle j}$ .

Plünnecke teoreminin kanıtı, "tensör çarpımı hilesi" olarak bilinen bir tekniği içerir. Menger'in teoremi.^[5]

Plünnecke-Ruzsa eşitsizliği, Plünnecke teoreminin ve Ruzsa üçgeni eşitsizliğinin oldukça doğrudan bir sonucudur. Plünnecke teoremini örnekte verilen grafiğe uygulamak, ${ displaystyle j = m}$ ve ${ displaystyle j = 1}$ , eğer ${ displaystyle | A + B | / | A | = K}$ o zaman var ${ displaystyle X subseteq A}$ Böylece ${ displaystyle | X + mB | / | X | leq K ^ {m}}$ . Bu sonucu bir kez daha uygulamak ${ displaystyle X}$ onun yerine ${ displaystyle A}$ var ${ displaystyle X ' subseteq X}$ Böylece ${ displaystyle | X '+ nB | / | X' | leq K ^ {m}}$ . Sonra, Ruzsa'nın üçgen eşitsizliği (on ${ displaystyle -X ', mB, nB}$ ),

{ displaystyle | mB-nB | leq | X '+ mB || X' + nB || X '| leq K ^ {m + n} | X | leq K ^ {m + n} | X | ,}

böylece Plünnecke-Ruzsa eşitsizliğini kanıtlıyor.

Ayrıca bakınız

Referanslar

^ ^a ^b Plünnecke, H. (1970). "Eine zahlentheoretische anwendung der graphtheorie". J. Reine Angew. Matematik. 243: 171–183.
^ Ruzsa, I. (1989). "Eklemeli sayı teorisine grafik teorisinin bir uygulaması". Scientia, Ser. Bir. 3: 97–109.
^ Candela, P .; González-Sánchez, D .; de Roton, A. (2017). "Kompakt değişmeli gruplarda bir Plünnecke-Ruzsa eşitsizliği". arXiv:1712.07615 [math.CO ].
^ Petridis, G. (2014). "Plünnecke – Ruzsa Eşitsizliği: Genel Bakış". Springer Proc. Matematik. İstatistik. Matematik ve İstatistikte Springer Proceedings. 101: 229–241. doi:10.1007/978-1-4939-1601-6_16. ISBN 978-1-4939-1600-9.
^ ^a ^b Tao, T .; Vu, V. (2006). Katkı Kombinatorikleri. Cambridge: Cambridge University Press. ISBN 978-0-521-85386-6.
^ Ruzsa, I., Toplamlar ve yapı (PDF).

[Plu-1] Plünnecke, H. (1970). "Eine zahlentheoretische anwendung der graphtheorie". J. Reine Angew. Matematik. 243: 171–183.

[2] Ruzsa, I. (1989). "Eklemeli sayı teorisine grafik teorisinin bir uygulaması". Scientia, Ser. Bir. 3: 97–109.

[3] Candela, P .; González-Sánchez, D .; de Roton, A. (2017). "Kompakt değişmeli gruplarda bir Plünnecke-Ruzsa eşitsizliği". arXiv:1712.07615 [math.CO ].

[4] Petridis, G. (2014). "Plünnecke – Ruzsa Eşitsizliği: Genel Bakış". Springer Proc. Matematik. İstatistik. Matematik ve İstatistikte Springer Proceedings. 101: 229–241. doi:10.1007/978-1-4939-1601-6_16. ISBN 978-1-4939-1600-9.

[TaoVu-5] Tao, T .; Vu, V. (2006). Katkı Kombinatorikleri. Cambridge: Cambridge University Press. ISBN 978-0-521-85386-6.

[6] Ruzsa, I., Toplamlar ve yapı (PDF).

[1]

[2]

[3]

[4]

[5]

[6]