Search for a good generating vector involves enumerating the values its components can take.

The representation of search spaces in LatBuilder is based on sequences of possible values for the components of the generating vector.

See also: GenSeq

Coprime Integers-Polynomials

In the general case, one normally needs to enumerate all integers (respectively polynomials) that are relatively prime with the modulus \(n\) (respectively \(P\)) of the lattice point set. This is implemented by the class template GenSeq::GeneratingValues.

For ordinary lattices, some figures of merit are invariant under the transformation \(a \mapsto n - a\) where \(a\) is any component of the generating vector. When using such a symmetric figure of merit, redundancy can be avoided by enumerating only the first half of the sequence of integers coprime with \(n\), i.e. by compressing the search space.
In that case, we pass Compress::Symmetric as second template argument to GenSeq::GeneratingValues:

typedef GenSeq::GeneratingValues<LatticeType::ORDINARY, Compress::SYMMETRIC> HalfSeqIntegers;

Otherwise, we pass Compress::None:

typedef GenSeq::GeneratingValues<LatticeType::ORDINARY, Compress::NONE> WholeSeqIntegers;

For polynomial lattices, to our knowledge, no symmetry properties have been identified so far:

typedef GenSeq::GeneratingValues<LatticeType::POLYNOMIAL, Compress::NONE> WholeSeqPolynomials;

These concepts are illustrated in tutorial/GenSeqGeneratingValues.cc :

For ordinary lattices:
for (uInteger n : {7, 8, 12}) {
std::cout << "lattice size: " << n << std::endl;
std::cout << " whole sequence: " << WholeSeqIntegers(n) << std::endl;
std::cout << " half sequence: " << HalfSeqIntegers(n) << std::endl;
}
The ouput of the above code is:
```
lattice size: 7
    whole sequence: [1, 2, 3, 4, 5, 6]
     half sequence: [1, 2, 3]
lattice size: 8
    whole sequence: [1, 3, 5, 7]
     half sequence: [1, 3]
lattice size: 12
    whole sequence: [1, 7, 5, 11]
     half sequence: [1, 5]
```
For polynomial lattices:
for (Polynomial P : {PolynomialFromInt(10), PolynomialFromInt(13)}) {
std::cout << "lattice size: " << P << std::endl;
std::cout << " whole sequence: " << WholeSeqPolynomials(P) << std::endl;

}
The ouput of the above code is:
```
polynomial lattice size: [0 1 0 1]
    whole sequence: [[1], [1 1 1]]
polynomial lattice size: [1 0 1 1]
    whole sequence: [[1], [0 1], [1 1], [0 0 1], [1 0 1], [0 1 1], [1 1 1]]
```

Random Traversal

Sometimes, as with random Korobov or random CBC, it is necessary to randomly select a certain number of elements from a GenSeq::GeneratingValues instance. GenSeq::GeneratingValues optionally takes a third template arguments that specifies a method of traversal of its values; it defaults to Traversal::Forward which enumerates the values in their original order in the sequence. It can be replaced with Traversal::Random for the above purpose:

typedef Traversal::Random<LFSR258> Trav;

typedef GenSeq::GeneratingValues<LatticeType::ORDINARY, Compress::SYMMETRIC, Trav> RandomSeq;

The traversal type Traversal::Random also takes a template argument that specifies the type of random generator to use. We use LFSR258 in our example, but any C++11-compliant random engine could be used. Next, a random traversal object must be instantiated with the desired number r of random samples:

Trav trav(r);

Then, the sequence object can be instantiated with the lattice size n, and the traversal object:

RandomSeq seq(n, trav);

A complete example can be found in tutorial/GenSeqRandom.cc :

   typedef Traversal::Random<LFSR258> Trav;
   typedef GenSeq::GeneratingValues<LatticeType::ORDINARY, Compress::SYMMETRIC, Trav> RandomSeq;
   size_t r = 4; // 4 random samples
   Trav trav(r);
   for (uInteger n : {31, 256}) {
      std::cout << "lattice size: " << n
         << " (" << trav.size() << " random samples)" << std::endl;
      RandomSeq seq(n, trav);
      std::cout << "          sequence: " << seq << std::endl;
      std::cout << "     same sequence: " << seq << std::endl;
      seq.randomGenerator().jump();
      std::cout << "    other sequence: " << seq << std::endl;
   }

The output of the above code is:

lattice size: 31 (4 random samples)
          sequence: [11, 2, 6, 15]
     same sequence: [11, 2, 6, 15]
    other sequence: [5, 14, 6, 8]
lattice size: 256 (4 random samples)
          sequence: [115, 71, 61, 51]
     same sequence: [115, 71, 61, 51]
    other sequence: [31, 115, 25, 37]

Note that GenSeq::Random stores its own copy of the random engine, so that successive iteration over the same random sequence objects yields the same sequence of values. To obtain a different random selection of values, the initial state of the random generator must be changed. The LFSR258 generator exposes a jump() function for this purpose:

seq.randomGenerator().jump();

In some situations, the number r of random samples is not known in advance. In that case, the preferred method is to instantiate the traversal object without passing the argument r, which defaults to infinity, then to add a stopping condition in loops that iterate over the elements of the sequence.

Cyclic Groups

For an integer \(n\) power of prime base, the multiplicative group of integers coprime with \(n\) is a cyclic group (or a product of two cyclic groups if \(2^3|n\)). For an irreducible polynomial \(P\), the multiplicative group of polynomials coprime with \(P\) is a cyclic group.

In these cases, the class template GenSeq::CyclicGroup can be used to enumerate the elements of the cyclic group of integers modulo \(n\) (respectively polynomials modulo \(P\)) in the natural group order where the \(i\)-th element is \(g^i \bmod n\) ( \(g^i \bmod P\) respectively), where \(g\) is the group generator. This is useful in particular to perform fast CBC exploration. Like GenSeq::GeneratingValues, GenSeq::CyclicGroup takes a compression type as the second template argument. This is illustrated in tutorial/GenSeqCyclicGroup.cc :

typedef GenSeq::CyclicGroup<LatticeType::ORDINARY, Compress::NONE> WholeIntSeq;
typedef GenSeq::CyclicGroup<LatticeType::ORDINARY, Compress::SYMMETRIC> HalfIntSeq;
typedef GenSeq::CyclicGroup<LatticeType::POLYNOMIAL, Compress::NONE> WholePolySeq;
void displayIntSeq(int base, int power)
{
   std::cout << "lattice size: " << base << "^" << power << std::endl;
   std::cout << "    whole sequence: " << WholeIntSeq(base, power) << std::endl;
   std::cout << "     half sequence: " << HalfIntSeq(base, power) << std::endl;
}
void displayPolySeq(Polynomial base, int power)
{
   std::cout << "polynomial lattice size: " << base << "^" << power << std::endl;
   std::cout << "    whole sequence: " << WholePolySeq(base, power) << std::endl;
}
int main()
{
   SET_PATH_TO_LATNETBUILDER_FOR_EXAMPLES();
   displayIntSeq(7, 1);
   displayIntSeq(2, 3);
   displayIntSeq(3, 2);
   displayPolySeq(PolynomialFromInt(13),1); 
   return 0;
}

The output of the above code is:

lattice size: 7^1
    whole sequence: [1, 3, 2, 6, 4, 5]
     half sequence: [1, 3, 2]
lattice size: 2^3
    whole sequence: [1, 5, 7, 3]
     half sequence: [1, 3]
lattice size: 3^2
    whole sequence: [1, 2, 4, 8, 7, 5]
     half sequence: [1, 2, 4]
polynomial lattice size: [1 0 1 1]^1
    whole sequence: [[1], [0 1], [0 0 1], [1 0 1], [1 1 1], [1 1], [0 1 1]]

For ordinary lattices, and in the symmetric case, each value \(a\) is mapped to \(\min\{a, n-a\}\). Note that in the polynomial case, the group is cyclic if the modulus is irreducible. This is only the case if power equals 1. Otherwise the group is not cyclic. This explains why the fast-CBC algorithm for polynomial lattice rules is only available for irreducible modulus. As a consequence, the fast-CBC construction is not available for embedded polynomial lattice rules.

Vectors of Integer/Polynomial Sequences

Construction algorithms often consider a distinct sequence of possible values
for each component of the generating vector. When distinct random selection of sequence elements are required for each coordinate, as with random CBC or plain random constructions; in this case, the initial state of the random generator must be different for each coordinate, as explained in Random Traversal. This functionality is provided by the convenience class template GenSeq::VectorCreator, which automatically calls jump() on the random generator between different coordinates if the traversal method is Traversal::Random.

A vector of dim sequences of type Seq with size parameter n can be created with:

auto vec = GenSeq::VectorCreator<Seq>::create(n, dim);

In most situations when constructing rank-1 lattices, we consider only the value 1 for the first component. For that purpose, we can replace the first integer (respectively polynomial) sequence with a singleton that contains only the value 1 with:

vec[0] = GenSeq::Creator<Seq>::create(n0);

where \(n_0\) is the size parameter with modulus 2 (or \(P(z)=z\) for polynomial lattices). A full example can be found in tutorial/GenSeqVector.cc :

template <LatticeType LA>
void SeqVector(typename LatticeTraits<LA>::Modulus modulus){
   typedef GenSeq::GeneratingValues<LA, Compress::NONE> Seq;
   SizeParam<LA, EmbeddingType::UNILEVEL> n(modulus);      // lattice size
   SizeParam<LA, EmbeddingType::UNILEVEL> n0(LatticeTraits<LA>::TrivialModulus);   // fake lattice size to obtain a single value (1)
   Dimension dim = 3;
   auto vec = GenSeq::VectorCreator<Seq>::create(n, dim);
   vec[0] = GenSeq::Creator<Seq>::create(n0);
   std::cout << "lattice size: " << n << std::endl;
   std::cout << "    generating value sequences: " << vec << std::endl;
}

SeqVector<LatticeType::ORDINARY>(7);

SeqVector<LatticeType::POLYNOMIAL>(PolynomialFromInt(7));

The output of the above code is:

lattice size: 7
    generating value sequences: [[1], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6]]
lattice size: [1 1 1]
    generating value sequences: [[[1]], [[1], [0 1], [1 1]], [[1], [0 1], [1 1]]]

For random sequence types, the number of random samples can be passed as an additional optional argument to GenSeq::VectorCreator::create():

template <LatticeType LA>
void RandomSeqVector(typename LatticeTraits<LA>::Modulus modulus){
   typedef GenSeq::GeneratingValues<LA, Compress::NONE, Traversal::Random<LFSR258>> RandomSeq;
   SizeParam<LA, EmbeddingType::UNILEVEL> n(modulus);      // lattice size
   SizeParam<LA, EmbeddingType::UNILEVEL> n0(LatticeTraits<LA>::TrivialModulus);   // fake lattice size to obtain a single value (1)
   Dimension dim = 3;
  
   auto randVec = GenSeq::VectorCreator<RandomSeq>::create(n, dim, 5);
   randVec[0] = GenSeq::Creator<RandomSeq>::create(n0, 1); // replace 1st with singleton
   std::cout << "lattice size: " << n << std::endl;
   std::cout << "    random generating value sequences: " << randVec << std::endl;
}

RandomSeqVector<LatticeType::ORDINARY>(7);

RandomSeqVector<LatticeType::POLYNOMIAL>(PolynomialFromInt(7));

The output of the above code is:

lattice size: 7
    random generating value sequences: [[1], [2, 2, 3, 5, 4], [4, 5, 4, 3, 6]]
lattice size: [1 1 1]
    random generating value sequences: [[[1]], [[0 1], [0 1], [1 1], [0 1], [1]], [[1], [0 1], [1], [1 1], [1 1]]]

Distinct random sequences are automatically created.

Extension of the Number of Points

A lattice with \(b^m\) points in dimension \(s\) and generating vector \(\boldsymbol a = (a_1,\dots,a_s)\) can be extended to \(b^{m+1}\) points by appending a \(m+1\)-st digit in base \(b\) to the left of each \(a_j\). It is easy to verify that the original lattice is indeed embedded in the extended lattice. The following instruction shows how to instantiate a sequence of generator values seq that adds a \(m+1\)-st digit in base b, where numPoints = b \(^m\) to the left of the \(m\) digits in base b of the integer gen (which stands for any of the \(a_j\)'s):

GenSeq::Extend<LatticeType::ORDINARY> seq(b * numPoints, numPoints, gen);

In practice, low would be one of the \(a_j\)'s. To add two digits instead of one, the first constructor argument b * numPoints must be replaced with b * b * numPoints.

The same applies for the polynomial case:

GenSeq::Extend<LatticeType::POLYNOMIAL> seq(base * P, P, generator);

A complete example can be found in tutorial/GenSeqExtend.cc.