Sada rozdílů - Difference set

Sada prvků v jedné sadě, ale ne v jiné, viz relativní doplněk. Sada rozdílů dvojic prvků viz Minkowski rozdíl.

v kombinatorika, a ${ displaystyle (v, k, lambda)}$ sada rozdílů je podmnožina ${ displaystyle D}$ z velikost ${ displaystyle k}$ a skupina ${ displaystyle G}$ z objednat ${ displaystyle v}$ tak, že každý prvek neidentity z ${ displaystyle G}$ lze vyjádřit jako produkt ${ displaystyle d_ {1} d_ {2} ^ {- 1}}$ prvků ${ displaystyle D}$ přesně ${ displaystyle lambda}$ způsoby. Sada rozdílů ${ displaystyle D}$ se říká, že je cyklický, abelian, neabelskýatd., pokud skupina ${ displaystyle G}$ má odpovídající vlastnost. Rozdíl nastaven na ${ displaystyle lambda = 1}$ se někdy nazývá rovinný nebo jednoduchý.^[1] Li ${ displaystyle G}$ je abelianská skupina napsáno v aditivní notaci, definující podmínkou je, že každý nenulový prvek ${ displaystyle G}$ lze psát jako rozdíl prvků ${ displaystyle D}$ přesně ${ displaystyle lambda}$ způsoby. Tímto způsobem vzniká pojem „rozdílová sada“.

Základní fakta

• Jednoduchý argument počítání ukazuje, že existují přesně ${ displaystyle k ^ {2} -k}$ dvojice prvků z ${ displaystyle D}$ který přinese prvky neidentity, takže každá množina rozdílů musí splňovat rovnici ${ displaystyle k ^ {2} -k = (v-1) lambda}$.
• Li ${ displaystyle D}$ je sada rozdílů a ${ displaystyle g v G}$, pak ${ displaystyle gD = {gd: d v D }}$ je také sada rozdílů a nazývá se a přeložit z ${ displaystyle D}$ (${ displaystyle D + g}$ v aditivní notaci).
• Doplněk a ${ displaystyle (v, k, lambda)}$-difference set je a ${ displaystyle (v, v-k, v-2k + lambda)}$- sada rozdílů.^[2]
• Sada všech překladů rozdílové sady ${ displaystyle D}$ tvoří a symetrický design bloku, nazvaný rozvoj z ${ displaystyle D}$ a označeno ${ displaystyle dev (D)}$. V takovém designu existují ${ displaystyle v}$ elementy (obvykle nazývané body) a ${ displaystyle v}$ bloky (podmnožiny). Každý blok designu se skládá z ${ displaystyle k}$ body, každý bod je obsažen v ${ displaystyle k}$ bloky. Jakékoli dva bloky mají přesně ${ displaystyle lambda}$ společné prvky a jakékoli dva body jsou současně obsaženy přesně ${ displaystyle lambda}$ bloky. Skupina ${ displaystyle G}$ působí jako automorfická skupina designu. Je ostře tranzitivní v obou bodech a blocích.^[3]
  • Zejména pokud ${ displaystyle lambda = 1}$, pak z množiny rozdílů vznikne a projektivní rovina. Příklad (7,3,1) rozdílu nastaveného ve skupině ${ displaystyle mathbb {Z} / 7 mathbb {Z}}$ je podmnožina ${ displaystyle {1,2,4 }}$. Překlady této rozdílové sady tvoří Fano letadlo.
• Protože každá sada rozdílů dává a symetrický design, sada parametrů musí splňovat Věta Bruck – Ryser – Chowla.^[4]
• Ne každý symetrický design dává rozdíl set.^[5]

Soubory ekvivalentních a izomorfních rozdílů

Dvě rozdílné sady ${ displaystyle D_ {1}}$ ve skupině ${ displaystyle G_ {1}}$ a ${ displaystyle D_ {2}}$ ve skupině ${ displaystyle G_ {2}}$ jsou ekvivalent pokud existuje skupinový izomorfismus ${ displaystyle psi}$ mezi ${ displaystyle G_ {1}}$ a ${ displaystyle G_ {2}}$ takhle ${ displaystyle D_ {1} ^ { psi} = {d ^ { psi} dvojtečka d v D_ {1} } = gD_ {2}}$ pro některé ${ displaystyle g v G_ {2}}$. Dvě rozdílné sady jsou izomorfní pokud vzory ${ displaystyle dev (D_ {1})}$ a ${ displaystyle dev (D_ {2})}$ jsou izomorfní jako blokové vzory.

Ekvivalentní rozdílové sady jsou izomorfní, ale existují příklady izomorfních rozdílových sad, které nejsou ekvivalentní. V případě sady cyklických rozdílů jsou všechny známé izomorfní sady rozdílů ekvivalentní.^[6]

Multiplikátory

A násobitel množiny rozdílů ${ displaystyle D}$ ve skupině ${ displaystyle G}$ je skupinový automorfismus ${ displaystyle phi}$ z ${ displaystyle G}$ takhle ${ displaystyle D ^ { phi} = gD}$ pro některé ${ displaystyle g v G}$. Li ${ displaystyle G}$ je abelian a ${ displaystyle phi}$ je automorfismus, který mapuje ${ displaystyle h mapsto h ^ {t}}$, pak ${ displaystyle t}$ se nazývá a numerické nebo sál násobitel.^[7]

Předpokládalo se, že pokud p je prvotní dělení ${ displaystyle k- lambda}$ a nedělit proti, pak skupinový automorfismus definovaný ${ displaystyle g mapsto g ^ {p}}$ opravuje nějaký překlad z D (to je ekvivalent multiplikátoru). Je známo, že to platí pro ${ displaystyle p> lambda}$ když ${ displaystyle G}$ je abelianská skupina a je známá jako první multiplikační věta. Obecnější známý výsledek, věta o druhém multiplikátoru, říká, že pokud ${ displaystyle D}$ je ${ displaystyle (v, k, lambda)}$- rozdíl nastavený v abelianské skupině ${ displaystyle G}$ exponentu ${ displaystyle v ^ {*}}$ (dále jen nejmenší společný násobek řádů každého prvku), let ${ displaystyle t}$ být celé číslo coprime ${ displaystyle v}$. Pokud existuje dělitel ${ displaystyle m> lambda}$ z ${ displaystyle k- lambda}$ tak, že pro každého prima p dělení m, existuje celé číslo i s ${ displaystyle t equiv p ^ {i} { pmod {v ^ {*}}}}$, pak t je číselný dělitel.^[8]

Například 2 je multiplikátor výše uvedené (7,3,1) -diferenční sady.

Bylo zmíněno, že numerický multiplikátor rozdílové množiny ${ displaystyle D}$ v abelianské skupině ${ displaystyle G}$ opravuje překlad z ${ displaystyle D}$, ale lze také ukázat, že existuje překlad z ${ displaystyle D}$ který je opraven všemi číselnými multiplikátory ${ displaystyle D}$.^[9]

Parametry

Známé sady rozdílů nebo jejich doplňky mají jednu z následujících sad parametrů:^[10]

• ${ displaystyle ((q ^ {n + 2} -1) / (q-1), (q ^ {n + 1} -1) / (q-1), (q ^ {n} -1) / (q-1))}$-diference nastavena na nějakou hlavní sílu ${ displaystyle q}$ a nějaké kladné celé číslo ${ displaystyle n}$. Tito jsou známí jako klasické parametry a existuje mnoho konstrukcí sad rozdílů, které mají tyto parametry.
• ${ displaystyle (4n-1,2n-1, n-1)}$-diference nastavena na nějaké kladné celé číslo ${ displaystyle n}$. Rozdílové sady s proti = 4n - 1 jsou volány Rozdílové sady typu Paley.
• ${ displaystyle (4n ^ {2}, 2n ^ {2} -n, n ^ {2} -n)}$-diferencia nastavena pro kladné celé číslo ${ displaystyle n}$. Rozdíl nastavený pomocí těchto parametrů je a Hadamardův rozdíl je nastaven.
• ${ displaystyle (q ^ {n + 1} (1+ (q ^ {n + 1} -1) / (q-1)), q ^ {n} (q ^ {n + 1} -1) / (q-1), q ^ {n} (q ^ {n} -1) / (q-1))}$-diference nastavena na nějakou hlavní sílu ${ displaystyle q}$ a nějaké kladné celé číslo ${ displaystyle n}$. Známý jako McFarlandovy parametry.
• ${ displaystyle (3 ^ {n + 1} (3 ^ {n + 1} -1) / 2,3 ^ {n} (3 ^ {n + 1} +1) / 2,3 ^ {n} ( 3 ^ {n} +1) / 2)}$-diference nastavena na nějaké kladné celé číslo ${ displaystyle n}$. Známý jako Spence parametry.
• ${ displaystyle (4q ^ {2n} (q ^ {2n} -1) / (q-1), q ^ {2n-1} (1 + 2 (q ^ {2n} -1) / (q + 1 )), q ^ {2n-1} (q ^ {2n-1} +1) (q-1) / (q + 1))}$-diference nastavena na nějakou hlavní sílu ${ displaystyle q}$ a nějaké kladné celé číslo ${ displaystyle n}$. Sady rozdílů s těmito parametry se nazývají Rozdílové sady Davis-Jedwab-Chen.

Známé sady rozdílů

V mnoha konstrukcích sad rozdílů se skupiny, které se používají, vztahují k aditivním a multiplikativním skupinám konečných polí. Zápis používaný k označení těchto polí se liší podle disciplíny. V této části, ${ displaystyle { rm {GF}} (q)}$ je Galoisovo pole řádu ${ displaystyle q}$, kde ${ displaystyle q}$ je hlavní nebo hlavní síla. Přidávaná skupina je označena ${ displaystyle G = ({ rm {GF}} (q), +)}$, zatímco ${ displaystyle { rm {GF}} (q) ^ {*}}$ je multiplikativní skupina nenulových prvků.

• Paley ${ displaystyle (4n-1,2n-1, n-1)}$-diferenční sada:

Nechat ${ displaystyle q = 4n-1}$ být hlavní silou. Ve skupině ${ displaystyle G = ({ rm {GF}} (q), +)}$, nechť ${ displaystyle D}$ být množina všech nenulových čtverců.

• Zpěvák ${ displaystyle ((q ^ {n + 2} -1) / (q-1), (q ^ {n + 1} -1) / (q-1), (q ^ {n} -1) / (q-1))}$-diferenční sada:

Nechat ${ displaystyle G = { rm {GF}} (q ^ {n + 2}) ^ {*} / { rm {GF}} (q) ^ {*}}$. Pak sada ${ displaystyle D = {x v G ~ | ~ { rm {Tr}} _ {q ^ {n + 2} / q} (x) = 0 }}$ je ${ displaystyle ((q ^ {n + 2} -1) / (q-1), (q ^ {n + 1} -1) / (q-1), (q ^ {n} -1) / (q-1))}$-diferenční sada, kde ${ displaystyle { rm {Tr}} _ {q ^ {n + 2} / q}: { rm {GF}} (q ^ {n + 2}) rightarrow { rm {GF}} (q )}$ je stopová funkce ${ displaystyle { rm {Tr}} _ {q ^ {n + 2} / q} (x) = x + x ^ {q} + cdots + x ^ {q ^ {n + 1}}}$.

• Twin prime power ${ displaystyle left (q ^ {2} + 2q, { frac {q ^ {2} + 2q-1} {2}}, { frac {q ^ {2} + 2q-3} {4} }že jo)}$- rozdíl nastaven, když ${ displaystyle q}$ a ${ displaystyle q + 2}$ jsou oba hlavní síly:

Ve skupině ${ displaystyle G = ({ rm {GF}} (q), +) oplus ({ rm {GF}} (q + 2), +)}$, nechť ${ displaystyle D = {(x, y) colon y = 0 { text {nebo}} x { text {a}} y { text {jsou nenulové a oba jsou čtverce nebo oba nejsou čtverce}} }.}$^[11]

Dějiny

Systematické používání cyklických diferenčních sad a metod pro konstrukci návrhů symetrických bloků sahá až do roku R. C. Bose a jeho klíčová práce z roku 1939.^[12] Avšak dříve se objevily různé příklady, například „Paley Difference Sets“, které sahají až do roku 1933.^[13] Zobecnění konceptu sady cyklických rozdílů na obecnější skupiny je způsobeno R.H. Bruck^[14] v roce 1955.^[15] Multiplikátory představil Marshall Hall Jr.^[16] v roce 1947.^[17]

aplikace

Nalezli jej Xia, Zhou a Giannakis že sady rozdílů lze použít ke konstrukci komplexního vektoru číselník který dosáhne obtížného Welch vázán na maximální amplitudě křížové korelace. Takto vytvořený číselník také tvoří tzv Grassmannian potrubí.

Zobecnění

A ${ displaystyle (v, k, lambda, s)}$ rozdílová rodina je sada podmnožin ${ displaystyle B = {B_ {1}, ... B_ {s} }}$ a skupina ${ displaystyle G}$ takové, že objednat z ${ displaystyle G}$ je ${ displaystyle v}$, velikost z ${ displaystyle B_ {i}}$ je ${ displaystyle k}$ pro všechny ${ displaystyle i}$a každý prvek neidentity prvku ${ displaystyle G}$ lze vyjádřit jako produkt ${ displaystyle d_ {1} d_ {2} ^ {- 1}}$ prvků ${ displaystyle B_ {i}}$ pro některé ${ displaystyle i}$ (tj. obojí ${ displaystyle d_ {1}, d_ {2}}$ pocházejí ze stejného ${ displaystyle B_ {i}}$) přesně ${ displaystyle lambda}$ způsoby.

Sada rozdílů je rodina rozdílů ${ displaystyle s = 1}$. Výše uvedená rovnice parametrů zobecňuje na ${ displaystyle s (k ^ {2} -k) = (v-1) lambda}$.^[18] Vývoj ${ displaystyle dev (B) = {B_ {i} + g: i = 1, ..., s, g v G }}$ rozdílné rodiny je 2-design Každý 2-design s pravidelnou automorfickou skupinou je ${ displaystyle dev (B)}$ pro nějakou odlišnou rodinu ${ displaystyle B}$.

Viz také

• Kombinatorický design

Poznámky

Reference

• Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1986), Teorie designu, Cambridge: Cambridge University Press, ISBN  0-521-33334-2, Zbl  0602.05001
• Colbourn, Charles J .; Dinitz, Jeffrey H. (2007), Příručka kombinatorických vzorů, Diskrétní matematika a její aplikace (2. vydání), Boca Raton: Chapman & Hall / CRC, ISBN  1-58488-506-8, Zbl  1101.05001
• van Lint, J.H .; Wilson, R.M. (1992), Kurz kombinatoriky, Cambridge: Cambridge University Press, ISBN  0-521-42260-4, Zbl  0769.05001
• Wallis, WD (1988). Kombinatorické vzory. Marcel Dekker. ISBN  0-8247-7942-8. Zbl  0637.05004.

Další čtení

• Moore, EH; Pollastek, HSK (2013). Sady rozdílů: Spojování algebry, kombinatoriky a geometrie. AMS. ISBN  978-0-8218-9176-6.
• Storer, Thomas (1967). Cyklomtomie a rozdílové sady. Chicago: Markham Publishing Company. Zbl  0157.03301.
• Xia, Pengfei; Zhou, Shengli; Giannakis, Georgios B. (2005). „Dosažení hranice Welch s rozdílnými sadami“ (PDF). Transakce IEEE na teorii informací. 51 (5): 1900–1907. doi:10.1109 / TIT.2005.846411. ISSN  0018-9448. Zbl  1237.94007..

Xia, Pengfei; Zhou, Shengli; Giannakis, Georgios B. (2006). "Oprava na" Dosažení Welche spojené s rozdílnými sadami ". IEEE Trans. Inf. Teorie. 52 (7): 3359. doi:10.1109 / tit.2006.876214. Zbl  1237.94008.

• Zwillinger, Daniel (2003). Standardní matematické tabulky a vzorce CRC. CRC Press. str.246. ISBN  1-58488-291-3.