Dvojitá mříž - Dual lattice

Algebraická struktura → Skupinová teorie Skupinová teorie
Základní pojmy Podskupina Normální podskupina Kvocientová skupina (Částečně)přímý produkt Skupinové homomorfismy jádro obraz přímý součet věnec produkt jednoduchý konečný nekonečný kontinuální multiplikativní přísada cyklický abelian vzepětí nilpotentní řešitelný Glosář teorie skupin Seznam témat teorie skupin
Konečné skupiny Klasifikace konečných jednoduchých skupin cyklický střídavý Typ lži sporadický Cauchyova věta Lagrangeova věta Sylowovy věty Hallova věta p-skupina Základní abelianská skupina Skupina Frobenius Multiplikátor Schur Symetrická skupina Sn Kleinova čtyřčlenná skupina PROTI Vzepětí skupina Dn Čtveřice skupina Q Dicyklická skupina Dicn
Diskrétní skupiny Mříže Celá čísla (Z) Zdarma skupina Modulární skupiny PSL (2,Z) SL (2,Z) Aritmetická skupina Mříž Hyperbolická skupina
Topologické a Lež skupiny Solenoid Kruh Obecné lineární GL (n) Speciální lineární SL (n) Ortogonální Ó(n) Euklidovský E(n) Speciální ortogonální TAK(n) Unitary U (n) Speciální unitární SU (n) Symplektický Sp (n) G2 F4 E6 E7 E8 Lorentz Poincaré Konformní Difomorfismus Smyčka Nekonečná dimenzionální Lieova skupina O (∞) SU (∞) Sp (∞)
Algebraické skupiny Lineární algebraická skupina Redukční skupina Abelianská odrůda Eliptická křivka

V teorii mříže, dvojitá mříž je konstrukce analogická konstrukci duálního vektorového prostoru. V určitých ohledech je geometrie dvojité mřížky mřížky ${ textstyle L}$ je převrácená hodnota geometrie ${ textstyle L}$, perspektiva, která je základem mnoha jeho použití.

Duální mřížky mají v rámci teorie mřížky, teoretické informatiky, kryptografie a matematiky širší uplatnění. Například se používá ve výpisu z Poissonův součtový vzorec, věty o přenosu poskytují spojení mezi geometrií mřížky a geometrií její duální a mnoho mřížkových algoritmů využívá duální mřížku.

Článek s důrazem na aplikace fyziky / chemie viz Reciproční mříž. Tento článek se zaměřuje na matematické pojetí dvojí mřížky.

Definice

Nechat ${ textstyle L subseteq mathbb {R} ^ {n}}$ být mříž. To znamená, ${ textstyle L = B mathbb {Z} ^ {n}}$ pro nějakou matici ${ textový styl B}$.

Dvojitá mřížka je množina lineární funkcionáři na ${ textstyle L}$ které berou celočíselné hodnoty v každém bodě ${ textstyle L}$:

${ displaystyle L ^ {*} = {f in ({ text {span}} (L)) ^ {*}: forall x in L, f (x) in mathbb {Z} }.}$

Li ${ textstyle ( mathbb {R} ^ {n}) ^ {*}}$ je identifikován s ${ textstyle mathbb {R} ^ {n}}$ za použití Tečkovaný produkt, můžeme psát ${ textstyle L ^ {*} = {v in { text {span}} (L): forall x in L, x cdot v in mathbb {Z} }.}$ Je důležité omezit na vektory v rozpětí z ${ textstyle L}$, jinak výsledný objekt není a mříž.

Navzdory této identifikaci okolních euklidovských prostor je třeba zdůraznit, že mřížka a její duální jsou zásadně odlišné druhy objektů; jeden se skládá z vektorů v Euklidovský prostor a druhá se skládá ze sady lineárních funkcionálů v daném prostoru. V těchto liniích lze také poskytnout abstraktnější definici takto:

${ displaystyle L ^ {*} = {f: L to mathbb {Z}: { text {f je lineární funkce}} } = { text {Hom}} _ { text {Ab} } (L, mathbb {Z}).}$

Poznamenáváme však, že duál není považován pouze za abstrakt Abelian skupina funkcionálů, ale přichází s přirozeným vnitřním produktem: ${ textstyle f cdot g = součet _ {i} f (e_ {i}) g (e_ {i})}$, kde ${ textstyle e_ {i}}$ je ortonormální na základě ${ textstyle { text {span}} (L)}$. (Ekvivalentně lze prohlásit, že z ortonormálního základu ${ textstyle e_ {i}}$ z ${ textstyle { text {span}} (L)}$, duální vektory ${ textstyle e_ {i} ^ {*}}$, definován ${ textstyle e_ {i} ^ {*} (e_ {j}) = delta _ {ij}}$ jsou ortonormálním základem.) Jedním z klíčových použití duality v teorii mřížky je vztah geometrie primární mřížky s geometrií její duální, pro kterou tento vnitřní produkt potřebujeme. V konkrétním popisu uvedeném výše je vnitřní produkt na dualu obecně implicitní.

Vlastnosti

Uvádíme některé základní vlastnosti duální mřížky:

• Li ${ textstyle B = [b_ {1}, ldots, b_ {n}]}$ je matice poskytující základ pro mřížku ${ textstyle L}$, pak ${ textstyle z in { text {span}} (L)}$ splňuje ${ textstyle z in L ^ {*} iff b_ {i} ^ {T} z in mathbb {Z}, i = 1, ldots, n iff B ^ {T} z in mathbb {Z} ^ {n}}$.
• Li ${ textový styl B}$ je matice poskytující základ pro mřížku ${ textstyle L}$, pak ${ textový styl B (B ^ {T} B) ^ {- 1}}$ dává základ pro dvojitou mříž. Li ${ textstyle L}$ je plná hodnost ${ textstyle B ^ {- T}}$ dává základ pro dvojitou mřížku: ${ textstyle z in L ^ {*} iff B ^ {T} z in mathbb {Z} ^ {n} iff z v B ^ {- T} mathbb {Z} ^ {n} }$.
• To ukazuje předchozí fakt ${ textstyle (L ^ {*}) ^ {*} = L}$. Tato rovnost platí za obvyklých identifikací vektorového prostoru s jeho dvojitým duálním nebo v prostředí, kde byl identifikován vnitřní produkt ${ textstyle mathbb {R} ^ {n}}$ s jeho duálním.
• Opravte dvě mřížky ${ textstyle L, M}$. Pak ${ textstyle L subseteq M}$ kdyby a jen kdyby ${ textstyle L ^ {*} supseteq M ^ {*}}$.
• Determinant mřížky je převrácený determinant jeho duálu: ${ textstyle { text {det}} (L ^ {*}) = { frac {1} {{ text {det}} (L)}}}$
• Li ${ textstyle q}$ je tedy nenulový skalární ${ textstyle (qL) ^ {*} = { frac {1} {q}} L ^ {*}}$.
• Li ${ textstyle R}$ je tedy rotační matice ${ textstyle (RL) ^ {*} = RL ^ {*}}$.
• Mříž ${ textstyle L}$ se říká, že je integrální, pokud ${ textstyle x cdot y in mathbb {Z}}$ pro všechny ${ textový styl x, y v L}$. Předpokládejme, že mříž ${ textstyle L}$je plná hodnost. Pod identifikací euklidovského prostoru s jeho dvojím, to máme ${ textstyle L subseteq L ^ {*}}$ pro integrální mřížky ${ textstyle L}$. Připomeňme si, pokud ${ textstyle L ' subseteq L}$ a ${ textstyle | L / L '| < infty}$, pak ${ textstyle { text {det}} (L ') = { text {det}} (L) | L / L' |}$. Z toho vyplývá, že pro integrální mřížku ${ textstyle { text {det}} (L) ^ {2} = | L ^ {*} / L |}$.
• Říká se, že integrální mřížka je unimodulární -li ${ textstyle L = L ^ {*}}$, což je výše uvedené ekvivalentní ${ textstyle { text {det}} (L) = 1.}$

Příklady

Pomocí výše uvedených vlastností lze duál mřížky efektivně vypočítat ručně nebo počítačem. Určité svazy důležité v matematice a informatice jsou vzájemně dvojí a některé zde uvádíme.

Základní příklady

• Dvojí ${ textstyle mathbb {Z} ^ {n}}$ je ${ textstyle mathbb {Z} ^ {n}}$.
• Dvojí ${ textstyle 2 mathbb {Z} oplus mathbb {Z}}$ je ${ textstyle { frac {1} {2}} mathbb {Z} oplus mathbb {Z}}$.
• Nechat ${ textstyle L = {x v mathbb {Z} ^ {n}: sum x_ {i} = 0 mod 2 }}$ být mřížkou celočíselných vektorů, jejichž souřadnice mají sudý součet. Pak ${ textstyle L ^ {*} = mathbb {Z} ^ {n} + ({ frac {1} {2}}, ldots, { frac {1} {2}})}$, to znamená, že duální je mřížka generovaná celočíselnými vektory spolu se všemi ${ textový styl 1/2}$s vektor.

q-ary mřížky

Důležitou třídu příkladů, zejména v krystalografii mřížek, uvádějí q-ary mřížky. Pro matici ${ textstyle A in mathbb {F} _ {q} ^ {m krát n},}$ definujeme ${ textstyle Delta _ {q} (A) = {x v mathbb {Z} ^ {n}: x mod q v A ^ {T} mathbb {F} _ {q} ^ { m} }, Delta _ {q} ^ { perp} (A) = {x in mathbb {Z} ^ {n}: Ax = 0 mod q }}$; tito se nazývají mřížky obrazu a jádra q-ary spojené s ${ textový styl A}$. Poté, co jsme identifikovali euklidovský prostor s jeho duálním, máme obraz a jádra q-ary mřížky matice ${ textový styl A}$ jsou dvojí, až skalární. Zejména, ${ textstyle Delta _ {q} (A) ^ {*} = { frac {1} {q}} Delta _ {q} ^ { perp} (A)}$ a ${ textstyle Delta _ {q} ^ { perp} (A) ^ {*} = { frac {1} {q}} Delta _ {q} (A)}$.^{[Citace je zapotřebí ]} (Důkaz lze provést jako cvičení.)

Věty o přenosu

Každý ${ textový styl v L ^ {*} setminus {0 }}$ oddíly ${ textstyle L}$ podle množin úrovní odpovídajících každé z celočíselných hodnot. Menší výběr ${ textstyle f}$ vyrábět sady úrovní s větší vzdáleností mezi nimi; zejména vzdálenost mezi vrstvami je ${ textstyle 1 / || f ||}$. Z tohoto důvodu lze ukázat, že hledání malých vektorů v ${ textstyle L ^ {*}}$ poskytuje spodní hranici největší velikosti nepřekrývajících se koulí, které lze umístit kolem bodů ${ textstyle L}$. Obecně platí, že věty vztahující se k vlastnostem mřížky s vlastnostmi její duální jsou známy jako věty o přenosu. V této části vysvětlíme některé z nich spolu s některými důsledky pro teorii složitosti.

Připomínáme si určitou terminologii: Pro mříž ${ textstyle L}$ , nechť ${ textstyle lambda _ {i} (L)}$ označuje nejmenší kouli o poloměru, která obsahuje sadu ${ textový styl i}$ lineárně nezávislé vektory ${ textstyle L}$. Například, ${ textstyle lambda _ {1} (L)}$ je délka nejkratšího vektoru ${ textstyle L}$. Nechat ${ textstyle mu (L) = { text {max}} _ {x v mathbb {R} ^ {n}} d (x, L)}$ označit poloměr pokrytí ${ textstyle L}$.

V tomto zápisu uvádí dolní mez uvedená v úvodu této části ${ textstyle mu (L) geq { frac {1} {2 lambda _ {1} (L ^ {*})}}}$.

Vždy existuje efektivně ověřitelný certifikát pro tvrzení, že mřížka má krátký nenulový vektor, konkrétně samotný vektor. Důležitým důsledkem Banaszcykovy věty o přenosu je to ${ textstyle lambda _ {1} (L) geq { frac {1} { lambda _ {n} (L ^ {*})}}}$, což znamená, že k prokázání, že mřížka nemá žádné krátké vektory, lze ukázat základ pro duální mřížku skládající se z krátkých vektorů. Pomocí těchto myšlenek lze ukázat, že aproximace nejkratšího vektoru mřížky na faktor n (the ${ textstyle { text {GAPSVP}} _ {n}}$ problém ) je v ${ textstyle { text {NP}} cap { text {coNP}}}$.^{[Citace je zapotřebí ]}

Další věty o přenosu:

• Vztah ${ textstyle lambda _ {1} (L) lambda _ {1} (L ^ {*}) leq n}$ vyplývá z Minkowski je vázán na nejkratší vektor; to je ${ textstyle lambda _ {1} (L) leq { sqrt {n}} ({ text {det}} (L) ^ {1 / n})}$, a ${ textstyle lambda _ {1} (L ^ {*}) leq { sqrt {n}} ({ text {det}} (L ^ {*}) ^ {1 / n})}$, z čehož vyplývá nárok od ${ textstyle { text {det}} (L) = { frac {1} {{ text {det}} (L ^ {*})}}}$.

Poissonův součtový vzorec

Dvojitá mřížka se používá ve výroku obecného Poissonova součtového vzorce.

Další čtení

• Ebeling, Wolfgang (2013). "Mříže a kódy". Pokročilé přednášky z matematiky. Wiesbaden: Springer Fachmedien Wiesbaden. doi:10.1007/978-3-658-00360-9. ISBN  978-3-658-00359-3. ISSN  0932-7134.

Reference