Skillnadsuppsättning

För uppsättningen element i en uppsättning men inte en annan, se Relativt komplement . För uppsättningen av skillnader av par av element, se Minkowski skillnad .

I kombinatorik är en $(v,k,\lambda )$ skillnadsmängd en delmängd $D$ av storleken $k$ av en grupp $G$ av ordningen $v$ så att varje icke-identitetselement i $G$ kan uttryckas som en produkt $d_{1}d_{2}^{-1}$ av element i $D$ på exakt $\lambda$ sätt. En skillnadsmängd $D$ sägs vara cyklisk , abelisk , icke-abelsk , etc., om gruppen $G$ har motsvarande egenskap. En skillnadsmängd med $\lambda =1$ kallas ibland plan eller enkel . Om $G$ är en abelsk grupp skriven i additiv notation, är det definierande villkoret att varje element som inte är noll i $G$ kan skrivas som en skillnad mellan element i $D$ i exakt ${ \displaystyle \lambda }$ sätt. Termen "differensuppsättning" uppstår på detta sätt.

Grundläggande fakta

• Ett enkelt räkneargument visar att det finns exakt $k^{2}-k$ elementpar från $D$ som kommer att ge icke-identitetselement, så varje skillnadsmängd måste uppfylla ekvationen $k^{2}-k=(v-1)\lambda$ .
• Om $D$ är en skillnadsmängd, och $g\in G$ , då $gD=\{gd:d\in D \}$ är också en skillnadsmängd och kallas en översättning av $D$ ( $D+g$ i additiv notation).
• Komplementet av en $(v,k,\lambda )$ -differensmängd är en $(v,vk, v-2k+\lambda )$ -skillnadsuppsättning.
• Uppsättningen av alla översättningar av en skillnadsmängd $D$ bildar en symmetrisk blockdesign , kallad utvecklingen av $D$ och betecknad med $dev(D)$ . I en sådan design finns $v$ -element (vanligtvis kallade punkter) och $v$ -block (delmängder). Varje block i designen består av $k$ punkter, varje punkt finns i $k$ block. Alla två block har exakt $\lambda$ element gemensamma och två valfria punkter är samtidigt inkluderade i exakt $\displaystyle \lambda }$ block. Gruppen $G$ fungerar som en automorfismgrupp för designen. Det är kraftigt transitivt på både punkter och block.
  • I synnerhet, om $\lambda =1$ , så ger skillnadsmängden upphov till ett projektivt plan . Ett exempel på en (7,3,1) skillnadsuppsättning i gruppen $\mathbb {Z} /7\mathbb {Z}$ är delmängden $\ {1,2,4\}$ . Översättningarna av denna skillnadsuppsättning bildar Fano-planet .
• Eftersom varje skillnadsmängd ger en symmetrisk design måste parameteruppsättningen uppfylla Bruck-Ryser-Chowla-satsen .
• Inte varje symmetrisk design ger en skillnadsuppsättning.

Ekvivalenta och isomorfa skillnadsuppsättningar

Två skillnadsuppsättningar $D_{1}$ i grupp $G_{1}$ och $D_{2}$ i grupp $G_{2}$ är ekvivalenta om det finns en gruppisomorfism $\psi$ mellan $G_{1}$ och $G_{2}$ så att $D_{1}^{\psi }=\{d^{\psi}\colon d\in D_{1}\}=gD_{2}$ för vissa ${\ displaystyle g\in G_{2}}$ . De två skillnadsuppsättningarna är isomorfa om designen $dev(D_{1})$ och $dev(D_{2})$ är isomorfa som block mönster.

Ekvivalenta skillnadsuppsättningar är isomorfa, men det finns exempel på isomorfa skillnadsuppsättningar som inte är ekvivalenta. I det cykliska differensuppsättningsfallet är alla kända isomorfa skillnadsuppsättningar ekvivalenta.

Multiplikatorer

En multiplikator av en skillnadsmängd $D$ i grupp $G$ är en gruppautomorfism $\phi$ av $G$ så att $D^ {\phi }=gD$ för vissa $g\in G$ . Om $G$ är abelsk och $\phi$ är automorfismen som avbildar $h\mapsto h^{t}$ , då kallas ${\displaystyle t} en$ numerisk eller Hall multiplikator .

Det har antagits att om p är ett primtal som dividerar $k-\lambda$ och inte dividerar v , så fixar gruppautomorfismen som definieras av $g\mapsto g^{p}$ vissa översätter av D (detta motsvarar att vara en multiplikator). Det är känt att det är sant för $p>\lambda$ när $G$ är en abelsk grupp, och detta är känt som den första multiplikatorsatsen. Ett mer allmänt känt resultat, Second Multiplikator Theorem, säger att om $D$ är en $(v,k,\lambda )$ -skillnadsmängd i en abelsk grupp ${ \displaystyle G}$ av exponent $v^{*}$ (den minsta gemensamma multipeln av ordningsföljden för varje element), låt $t$ vara ett heltal med primtal till $v$ . Om det finns en divisor $m>\lambda$ av $k-\lambda$ så att för varje primtal p som delar m , finns det ett heltal i med ${\displaystyle t\equiv p^{i}\ {\pmod {v^{*}}}} ,$ då är t en numerisk divisor.

Till exempel är 2 en multiplikator av (7,3,1)-differensuppsättningen som nämns ovan.

Det har nämnts att en numerisk multiplikator av en skillnadsmängd $D$ i en abelsk grupp $G$ fixar en översättning av $D$ , men det kan också visas att det finns en översättning av $D$ som är fixerad av alla numeriska multiplikatorer av $D$ .

Parametrar

De kända skillnadsuppsättningarna eller deras komplement har en av följande parameteruppsättningar:

• $((q ^{n+2}-1)/(q-1),(q^{n+1}-1)/(q-1),(q^{n}-1)/(q-1))$ -skillnadsuppsättning för någon primpotens $q$ och något positivt heltal $n$ . Dessa är kända som de klassiska parametrarna och det finns många konstruktioner av differensuppsättningar som har dessa parametrar.
• $(4n-1,2n-1,n-1)$ -skillnadsuppsättning för något positivt heltal $n$ . Skillnadsmängder med v = 4 n − 1 kallas differensmängder av Paley-typ .
• $(4n^{2},2n^{2}-n,n^{2}-n)$ -skillnadsuppsättning för något positivt heltal $n$ . En differensuppsättning med dessa parametrar är en Hadamard-differensuppsättning .
• ${\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))} -skillnadsuppsättning för viss primpotens q {\$ displaystyle $}$ och någon positiv heltal $n$ . Kända som McFarland-parametrarna .
• $(3^{n+1 }(3^{n+1}-1)/2,3^{n}(3^{n+1}+1)/2,3^{n}(3^{n}+1)/2 )$ -skillnadsuppsättning för något positivt heltal $n$ . Känd som Spence-parametrarna .
• $(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 ))$ -skillnadsuppsättning för någon primpotens $q$ och något positivt heltal $n$ . Skillnadsuppsättningar med dessa parametrar kallas Davis-Jedwab-Chen-differensuppsättningar .

Kända skillnadsuppsättningar

I många konstruktioner av skillnadsmängder är grupperna som används relaterade till additiva och multiplikativa grupper av finita fält. Beteckningen som används för att beteckna dessa fält skiljer sig beroende på disciplin. I detta avsnitt är ${\rm {GF}}(q)$ Galois ordningsfältet q $\displaystyle q}$ där $q$ är en primtal eller primtalspotens. Gruppen under addition betecknas med $G=({\rm {GF}}(q),+)$ , medan ${ \rm {GF}}(q)^{*}$ är den multiplikativa gruppen av element som inte är noll.

• Paley $(4n-1,2n-1,n-1)$ -skillnadsuppsättning:

Låt $q=4n -1$ vara en huvudkraft. I gruppen $G=({\rm {GF}}(q),+)$ , låt $D$ vara mängden av alla icke-noll rutor.

• Sångare $(( q^{n+2}-1)/(q-1),(q^{n+1}-1)/(q-1),(q^{n}-1)/(q-1) )$ -skillnadsuppsättning:

Låt $G={\rm {GF}}(q^{n+2})^{*} /{\rm {GF}}(q)^{*}$ . Då mängden ${\displaystyle D=\{x\in G~|~{\rm {Tr}}_{q^{n+2}/q}(x)= 0$$((q^{n+2}-1)/(q-1),(q^{n+1}-1)/(q-1),(q^{n}-1)/ (q-1))$ är -differensmängd, där ${\rm {Tr}}_{q^{ n+2}/q}:{\rm {GF}}(q^{n+2})\högerpil {\rm {GF}}(q)$ är spårfunktionen ${\rm {Tr}}_{q^{n+2}/q}(x)=x+x^{q}+\ cdots +x^{q^{n+1}}$ .

• Tvillingprimeffekt $\left(q^{2}+2q,{\frac {q^{2 }+2q-1}{2}},{\frac {q^{2}+2q-3}{4}}\right)$ -skillnaden inställd när $q$ och $q+2$ är båda primpotenser:

I gruppen $G=({\rm {GF}}(q ),+)\oplus ({\rm {GF}}(q+2),+)$ , låt $D=\{(x,y)\colon y=0{\text{ eller }}x{\text{ och }}y{\text{ är icke-noll och båda är kvadrater eller båda är icke- rutor}}\}.$

Historia

Den systematiska användningen av cykliska skillnadsuppsättningar och metoder för konstruktion av symmetriska blockdesigner går tillbaka till RC Bose och hans historiska uppsats 1939. Men olika exempel dök upp tidigare än detta, till exempel "Paley Difference Sets" som går tillbaka till 1933. Generaliseringen av konceptet med cykliska skillnader till mer allmänna grupper beror på RH Bruck 1955. Multiplikatorer introducerades av Marshall Hall Jr. 1947.

Ansökan

Det har upptäckts av Xia, Zhou och Giannakis att skillnadsuppsättningar kan användas för att konstruera en komplex vektorkodbok som uppnår den svåra Welch bunden på maximal korskorrelationsamplitud. Den så konstruerade kodboken bildar också den så kallade Grassmannian manifolden.

Generaliseringar

En $(v,k,\lambda ,s)$ skillnadsfamilj är en uppsättning delmängder $B_{s}\}}$${\displaystyle B=\{B_ {1},\ldots$ , av en grupp $G$ så att ordningen på $G$ är $v$ , storleken på $B_{i}$ är $k$ för all $i$ , och varje icke-identitetselement i $G$ kan uttryckas som en produkt $d_{1 }d_{2}^{-1}$ av element i $B_{i}$ för vissa $i$ (dvs både $d_{1},d_{ 2}$ kommer från samma $B_{i}$ ) på exakt $\lambda$ sätt.

En skillnadsmängd är en skillnadsfamilj med $s=1$ . Parameterekvationen ovan generaliserar till $s(k^{2}-k)=(v-1)\lambda$ . Utvecklingen $dev(B)=\{B_{i}+g:i=1,\ldots ,s,g\in G\}$ av en skillnadsfamilj är en 2-design . Varje 2-design med en vanlig automorfismgrupp är $dev(B)$ för en viss skillnadsfamilj $B$ .

Se även

• Kombinatorisk design

Anteckningar

•    Beth, Thomas; Jungnickel, Dieter ; Lenz, Hanfried (1986), Design Theory , Cambridge: Cambridge University Press, ISBN 0-521-33334-2 , Zbl 0602.05001
•    Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs , Discrete Mathematics and its Applications (2nd ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 1-58488-506-8 , Zbl 1101.05001
•    van Lint, JH; Wilson, RM (1992), A Course in Combinatorics , Cambridge: Cambridge University Press , ISBN 0-521-42260-4 , Zbl 0769.05001
•    Wallis, WD (1988). Kombinatoriska mönster . Marcel Dekker. ISBN 0-8247-7942-8 . Zbl 0637.05004 .

Vidare läsning

•   Moore, EH; Pollastek, HSK (2013). Skillnadsuppsättningar: Anslutning av algebra, kombinatorik och geometri . AMS. ISBN 978-0-8218-9176-6 .
•   Storer, Thomas (1967). Cyklotomi och skillnadsuppsättningar . Chicago: Markham Publishing Company. Zbl 0157.03301 .
•    Xia, Pengfei; Zhou, Shengli; Giannakis, Georgios B. (2005). "Att uppnå Welch Bound with Difference Sets" (PDF) . IEEE-transaktioner på informationsteori . 51 (5): 1900–1907. doi : 10.1109/TIT.2005.846411 . ISSN 0018-9448 . Zbl 1237.94007 . .

  Xia, Pengfei; Zhou, Shengli; Giannakis, Georgios B. (2006). "Korrektion för att uppnå Welch bunden med skillnadsuppsättningar". IEEE Trans. Inf. Teori . 52 (7): 3359. doi : 10.1109/tit.2006.876214 . Zbl 1237.94008 .

•   Zwillinger, Daniel (2003). CRC standard matematiska tabeller och formler . CRC Tryck. sid. 246 . ISBN 1-58488-291-3 .