Lattiaratkaisusta

Lattiaratkaisusta viitataan tilanteisiin, joissa ratkaisut muodostuvat kokonaisluvuista ja ratkaisujoukko muistuttaa lattiaa eli latticeia tai affiinilattiaa. Matematiikassa lattice on diskreetti alijoukko R^n, joka on generoitu tietyllä vektoriperustalla. Tässä yhteydessä lattiaratkaisu tarkoittaa ratkaisujoukkoa, joka on latticein kaltainen tai, lineaarisessa tapauksessa affiin lattia.

Lineaarisessa diophanttisessa järjestelmässä Ax = b, missä A ∈ Z^{m×n} ja b ∈ Z^m, ratkaisujoukko on joko tyhjä tai se on affiini lattice: x = x0 + L, jossa x0 on jokin kokonaislukuratkaisu ja L = { ∑ i z_i t_i : t_i ∈ Z } on lattice, joka koostuu kaikkien Ax = 0 -yhtälöitä täyttävien kokonaislukuratkaisujen joukosta. Latticein generaattorit z_1, ..., z_k antavat sen, miten koko ratkaisujoukko voidaan rakentaa.

Esimerkki: ratkaistaan x + 2y = 4 kokonaislukujen avulla. Ratkaisujoukko on { (4 − 2t, t) | t ∈ Z }. Tämä on affiin lattice, jossa x0 = (4,0) ja L = { t(−2,1) | t ∈ Z }. Homogeenisen osan ratkaisut muodostavat latticein, jonka yksinkertainen perusvektori on (−2, 1).

Lattiaratkaisujen käsite esiintyy laajasti number theoryssä, kokonaislukujen optimoinnissa (integer programming) sekä lattice-pohjaisessa kryptografiassa. LLL-algoritmi ja muut lattice-reduktiostrategiat ovat keskeisiä työkaluja lyhyiden vektoreiden etsimisessä sekä erilaisten diophanttisten ongelmien ja käytännön sovellusten ratkaisemisessa.