準ランダムグループ

数学において、準ランダム群とは、大きな積のない部分集合を含まない群のことである。このような群は、小さな非自明な既約表現を持たない群とまったく同じである。これらの群の名前は、グラフ理論との関連に由来する。準ランダム群の任意の部分集合上の二部ケーリーグラフは、常に二部準ランダムグラフである。

準ランダム群の概念は、群のサブセットを考えるときに生じ、そのサブセット内のどの 2 つの要素もサブセット内で積を持たない。このようなサブセットは積なし と呼ばれる。László BabaiとVera Sós は、順序を持つすべての有限群が少なくともサイズを持つ積なしサブセットを持つ定数の存在について質問した。^[1]ポール・エルデシュの整数の和なし集合に関するよく知られた結果を使用して、アーベル群に対して が十分であることを証明できるが、非アーベル群に対してはそのような定数は存在しないことが判明した。^[2]${\displaystyle c}$${\displaystyle G}$${\displaystyle n}$${\displaystyle cn}$${\textstyle c={\frac {1}{3}}}$

位数 の群の最大の積なし部分集合のサイズについては、非自明な下限と上限の両方が現在知られています。 の下限は、十分な数の剰余類の和集合の大きな部分集合を取ることによって証明できます。^[3]の上限は、任意の素数 の射影特殊線型群を考慮することによって与えられます。^[4]上限を証明する過程で、ティモシー・ガワーズは、積なし条件をカプセル化する準ランダム群の概念を定義し、グラフ理論における準ランダム性を含む同値性を証明しました。 ${\displaystyle n}$${\textstyle cn^{\frac {11}{14}}}$${\textstyle cn^{\frac {8}{9}}}$ ${\displaystyle \operatorname {PSL} (2,p)}$ ${\displaystyle p}$

形式的には、単一のグループが準ランダムであるかどうかを議論するのは意味がありません。準ランダム性の厳密な定義はグループのシーケンスに適用されますが、まず二部グラフの準ランダム性を定義する必要があります。グループのシーケンスを検討する動機は、ある意味でグラフの限界として定義されるグラフオンとの関連性に由来します。

実数 を固定します。頂点、頂点部分、および辺を持つ二部グラフのシーケンス(ここでは が無限大に近づく限り整数をスキップできます) は、次の同等の条件のいずれかが満たされる場合、準ランダムです。 ${\displaystyle p\in [0,1].}$${\displaystyle (G_{n})}$${\displaystyle n}$${\displaystyle n}$${\displaystyle G_{n}}$${\displaystyle n}$${\displaystyle A_{n}}$${\displaystyle B_{n}}$${\displaystyle (p+o(1))|A_{n}||B_{n}|}$

• 頂点部分とを持つ任意の2部グラフに対して、に埋め込まれ、に埋め込まれたのラベル付きコピーの数は、ここで関数はに依存することが許される。${\displaystyle H}$${\displaystyle A'}$${\displaystyle B'}$${\displaystyle H}$${\displaystyle G_{n}}$${\displaystyle A'}$${\displaystyle A}$${\displaystyle B'}$${\displaystyle B}$${\textstyle \left(p^{e(H)}+o(1)\right)|A|^{|A'|}|B|^{|B'|}.}$${\displaystyle o(1)}$${\displaystyle H.}$
• から始まる長さ4の閉じたラベル付きウォークの数は${\displaystyle G_{n}}$${\displaystyle A_{n}}$${\displaystyle (p^{4}+o(1))|A_{n}|^{2}|B_{n}|^{2}.}$
• との間の辺の数は、任意の部分集合のペアとに対して${\displaystyle A'}$${\displaystyle B'}$${\displaystyle p|A'||B'|+n^{2}o(1)}$${\displaystyle A'\subseteq A_{n}}$${\displaystyle B'\subseteq B_{n}.}$
• ${\displaystyle \sum \limits _{a_{1},a_{2}\in A_{n}}N(a_{1},a_{2})^{2}=(p^{4}+o(1))|A_{n}|^{2}|B_{n}|^{2}}$、ここで はとの共通近傍の数を表します。${\displaystyle N(u,v)}$${\displaystyle u}$${\displaystyle v.}$
• ${\displaystyle \sum \limits _{b_{1},b_{2}\in B_{n}}N(b_{1},b_{2})^{2}=(p^{4}+o(1))|A_{n}|^{2}|B_{n}|^{2}.}$
• の隣接行列の最大固有値は であり、他のすべての固有値の大きさは最大で${\displaystyle G_{n}}$${\textstyle (p+o(1)){\sqrt {|A||B|}}}$${\textstyle {\sqrt {|A||B|}}o(1).}$

チャン・グラハム・ウィルソンの結果、上記の各条件は同等である。^{[5]このようなグラフは、各条件が、考慮されている量が、}エルデシュ・レーニのランダムグラフモデルに従って生成された2部グラフの場合に予想される量に近いことを主張しているため、準ランダムと呼ばれます。つまり、との各可能な辺を独立して確率で含めて生成されます。${\displaystyle A_{n}}$${\displaystyle B_{n}}$${\displaystyle p.}$

準ランダム性はグラフのシーケンスに対してのみ定義できますが、グラフの準ランダム性の上記の定義のいずれかに誤差許容範囲を許容することで、特定のグラフに対して -準ランダム性の概念を定義できます。具体的には、準ランダム性の同等の定義のいずれかが与えられた場合、項は小さな定数 に置き換えることができ、その特定の修正条件を満たすグラフは -準ランダムと呼ぶことができます。任意の条件下での -準ランダム性は、ある絶対定数に対する他の任意の条件下での -準ランダム性と同等であることがわかります。${\displaystyle c}$${\displaystyle o(1)}$${\displaystyle c>0}$${\displaystyle c}$${\displaystyle c}$${\displaystyle c^{k}}$${\displaystyle k\geq 1.}$

グループの準ランダム性を定義する次のステップは、ケイリー グラフです。二部ケイリー グラフは、グラフ理論の設定における準ランダム性をグループ理論の設定に変換する方法を提供します。

有限群と部分集合が与えられたとき、二部ケイリーグラフは、 の要素でラベル付けされた頂点集合 と を持つ二部グラフであり、その辺は、比がの要素である頂点 の間にある。${\displaystyle \ガンマ}$${\displaystyle S\subseteq \Gamma }$ ${\displaystyle \operatorname {BiCay} (\Gamma ,S)}$${\displaystyle A}$${\displaystyle B}$${\displaystyle G}$${\displaystyle a\sim b}$${\displaystyle ab^{-1}}$${\displaystyle S.}$

上記で定義したツールを使うと、群の準ランダム性を定義することができる。（ここでも整数を飛ばすことは許される）群の列が準ランダムであるとは、 の任意の実数と のサブセットの選択に対して、グラフの列が準ランダムであることを意味する。^[4]${\displaystyle (\Gamma _{n})}$${\displaystyle |\Gamma _{n}|=n}$${\displaystyle n}$${\displaystyle p\in [0,1]}$${\displaystyle S_{n}\subseteq \Gamma _{n}}$${\displaystyle |S_{n}|=(p+o(1))|\Gamma _{n}|}$${\displaystyle \operatorname {BiCay} (\Gamma _{n},S_{n})}$

準ランダム性はグループのシーケンスに対してのみ定義できますが、特定のグループに対する - 準ランダム性の概念は、特定のグラフに対する - 準ランダム性の定義を使用してグループに拡張できます。 ${\displaystyle c}$${\displaystyle c}$

Gowers によって証明されたように、グループの準ランダム性はさまざまな条件と同等であることがわかります。

正確に言うと、一連のグループが与えられた場合、以下は同等です。 ${\displaystyle (\Gamma _{n})}$

• ${\displaystyle (\Gamma _{n})}$は準ランダムです。つまり、 によって定義されるケイリーグラフのすべてのシーケンスは準ランダムです。${\displaystyle (\Gamma _{n})}$
• の最小の非自明な表現の次元は無制限です。${\displaystyle \Gamma_{n}}$
• の最大の積のない部分集合の大きさは${\displaystyle \Gamma_{n}}$${\displaystyle o(|\Gamma _{n}|).}$
• の最小の非自明な商の大きさは無制限である。^[4]${\displaystyle \Gamma_{n}}$

擬似ランダム群から生成されたケイリーグラフは、強い混合特性を持ちます。つまり、 は、が無限大に向かうにつれて 0 に向かうに対して二部グラフです。(グラフは、各頂点が次数 で、隣接行列の 2 番目に大きい固有値が最大 であるグラフです。) ${\displaystyle \operatorname {BiCay} (\Gamma _{n},S)}$${\displaystyle (n,d,\lambda )}$${\displaystyle \lambda}$${\displaystyle n}$${\displaystyle (n,d,\lambda )}$${\displaystyle n}$${\displaystyle d}$${\displaystyle \lambda .}$

実際、任意の-準ランダム群に対して、 、 、となるの解の数は、がランダムに選択された場合に予想される数とほぼ等しいことが示されます。つまり、 は とほぼ等しくなります。この結果は、エキスパンダー混合補題を直接適用することで得られます。 ${\displaystyle c}$${\displaystyle \ガンマ}$${\displaystyle xy=z}$${\displaystyle x\in X}$${\displaystyle y\in Y}$${\displaystyle z\in Z}$${\displaystyle S}$${\displaystyle {\tfrac {|X||Y||Z|}{|\Gamma |}}.}$

準ランダム グループには注目すべきファミリーがいくつかあります。それぞれの場合、準ランダム性の特性は、その最小の非自明な表現の次元をチェックすることによって最も簡単に検証できます。

• 素数の射影特殊線型群は、フロベニウスの古典的な結果によればその最小の非自明な表現の次元が少なくとも であるため、準ランダム群のシーケンスを形成します。実際、これらの群は、群の順序の関数として、最大の既知の最小の非自明な表現を持つ群です。${\displaystyle \operatorname {PSL} (2,p)}$${\displaystyle p}$${\displaystyle {\tfrac {1}{2}}(p-1).}$
• 交代群は 準ランダムである。なぜなら、その最小の非自明な表現は次元${\displaystyle (A_{n})}$${\displaystyle n-1.}$
• 増加する順序を持つ非巡回単純群の任意の列は準ランダムである。なぜなら、その最小の非自明な表現は少なくとも次元を持ち、ここで は群の順序であるからである。^[4]${\displaystyle {\tfrac {1}{2}}{\sqrt {\log n}}}$${\displaystyle n}$