Egyenlő távolságra egymástól: hány kódszó fér el a Hamming-térben?

Hány olyan bináris adatsort választhatunk ki, amelyek közül bármely kettő pontosan ugyanannyi pozícióban tér el egymástól? Ez az egyszerűnek tűnő kérdés a kombinatorika, a kódelmélet és a diszkrét geometria határterületére vezet. Egy (n) hosszúságú bináris szó az (n)-dimenziós hiperkocka egy pontjaként képzelhető el, két szó Hamming-távolsága pedig azoknak a koordinátáknak a száma, amelyekben különböznek. A Neumann János Informatikai Kar egyetemi docense, Dr. habil. Hegedüs Gábor azt vizsgálta, mekkora lehet egy olyan kód, amelyben a különböző kódszópárok Hamming-távolsága ugyanaz a rögzített (lambda) érték.

A korábban ismert általános becslések szerint egy ilyen bináris kódnak legfeljebb (n+1) eleme lehet. Hegedüs fő eredménye ezt a korlátot szinte minden esetben (n)-re javítja: ha a közös távolság nem éppen ((n+1)/2), akkor legfeljebb (n) darab, egymástól egyenlő Hamming-távolságra lévő bináris szó választható ki. Másképpen fogalmazva: az (n)-dimenziós bináris térben az egyenlő távolságú konfigurációk méretét alapvetően maga a dimenzió korlátozza. A becslés nem csupán elméleti: bizonyos Hadamard-mátrixok sorait felhasználva pontosan (n) elemű konstrukciók állíthatók elő, tehát a felső korlát számos esetben valóban elérhető.

A bizonyítás kulcsa, hogy a nullákból és egyesekből álló szavakat (+1) és (-1) koordinátájú vektorokká alakítjuk. Ekkor a Hamming-távolság skalárszorzatként is kifejezhető: ha két szó (lambda) helyen különbözik, akkor a hozzájuk tartozó vektorok skalárszorzata (n-2\lambda). Az összes ilyen skalárszorzatot felhasználva egy úgynevezett Gram-mátrixot készíthetünk. Kollégánk ennek a különleges szerkezetű mátrixnak a determinánsát vizsgálta, és a mátrix regularitásából vezette le, hogy a kód elemszáma nem haladhatja meg a tér dimenzióját. A kivételes (lambda=(n+1)/2) értéknél azonban a Gram-mátrix szingulárissá válhat, ezért ott az (n)-es korlát nem következik a bizonyításból.

Scott Duke Kominers Hegedüs Gábor eredményére épülő munkája ugyanazt a Gram-mátrixot más nézőpontból elemzi: a determináns helyett közvetlenül a sajátértékeket vizsgálja. Ez nem pusztán rövidebb bizonyítást eredményez, hanem megmutatja az eredmény mögött álló geometriát is. A megfelelően normált kódszavak egy gömb felületén fekvő, egymástól egyenlő távolságú pontoknak felelnek meg. Az ilyen pontok egy szabályos szimplex csúcsai, amelyből (n)-dimenziós térben legfeljebb (n+1) lehet. Az (n+1) csúcsú teljes szimplex azonban pontosan a kivételes (lambda=(n+1)/2) távolságnál jelenik meg; minden más esetben legfeljebb (n) pont maradhat. Kominers példákkal azt is megmutatja, hogy a kivétel valódi: például háromdimenziós bináris térben négy, páronként 2 Hamming-távolságra lévő szó alkothat egy szabályos tetraédernek megfelelő konfigurációt.

A sajátérték-alapú megközelítés további előnye, hogy közvetlenül általánosítható nem bináris ábécékre. Ha minden koordináta (q) különböző értéket vehet fel, a szavak egy (n(q-1))-dimenziós euklideszi térbe ágyazhatók be. Ebben az esetben — egyetlen különleges távolság kivételével — legfeljebb (n(q-1)) páronként egyenlő Hamming-távolságú szó létezhet. Kominers elemzése egyben pontosítja Hegedüs eredeti sejtésének kivételes értékét is: a helyes küszöb nem ((q-1)(n+1)/q), hanem (((q − 1)n + 1) / q). Ezt az általános korlátot időközben Hu, Huang és Yu is igazolták, Kominers bizonyítása azonban egyetlen egyszerű lineáris algebrai állításból vezeti le mind a bináris, mind a (q)-elemű esetet.

A két tanulmány jól példázza, hogyan kapcsolódik össze a kódelmélet, a lineáris algebra és a geometria. Dr. habil. Hegedüs Gábor eredménye új, szoros felső korlátot adott az egyenlő Hamming-távolságú kódokra, Kominers pedig feltárta, hogy a korlát mögött valójában a szabályos szimplexek klasszikus geometriája húzódik meg. Az eredmény így nemcsak azt mondja meg, hány különleges kódszó fér el egy diszkrét térben, hanem azt is megmutatja, hogy az egyenlő távolság követelménye milyen erősen korlátozza a nagy dimenziós adatreprezentációk lehetséges szerkezetét.