NAME

Math::DifferenceSet::Planar::Computation - planar difference set computation

DESCRIPTION

The Math::DifferenceSet::Planar library and its data extensions are bundled with databases of sample sets to make sets within certain size boundaries readily available and speed up tasks of enumerating, validating, or identifying planar difference sets.

Providing these sample sets, as well as studying the structure of their spaces, can thus be left out of run-time code, saving lots of CPU cycles.

This section of the documentation discusses the steps performed at pre-calculation time for providing this data. They could be repeated to verify the data or applied to larger orders to obtain more sets.

Currently, some steps use code that is not yet available in Perl libraries. The author is working on closing this gap, however, so that eventually the distribution package should be capable of completely reproducing itself alone from Perl code.

Producing samples

Singer-type difference sets can be obtained from logarithms in a Galois field like this (for sets of order k, all operations are performed in the Galois field of order k):

Find a monic primitive polynomial in GF(k) of degree 3. Iterate through powers of x modulo this polynomial from exponent zero up to exponent k²+k. The exponents yielding a remainder with degree less than two will be a planar difference set containing zero and one.

The git repository of this library has two Pari/GP scripts prime_order_samples.gp and extra_large_sample.gp working like this, employing modular integers, and thus only handling prime orders.

For orders that are prime powers with an exponent greater than one, the same algorithm is valid, but it needs Galois field arithmetic rather than simple modular integer arithmetic. A generic implementation will be in the examples collection of the separate perl library Math-GaloisField (due to be published not too long after this library).

Efficient implementation of field arithmetic becomes increasingly important as orders grow larger. The C program even_order_sample.c of the repository is a sample set generator for fields with characteristic two, or orders that are powers of two. The remaining case of odd prime powers could be implemented in similar fashion.

Obtaining space information

Enumerating all planar difference set planes of a given order can be sped up with knowledge about generators of subspaces of their multiplicative space. Finding such generators is related to finding generators of reduced residue systems of modular integers, which is covered in algebraic libriaries like Pari/GP (see the znstar function there).

The script pds_find_space in the examples directrory is a pure perl algorithm employing a search for such generators. It is not particularly efficient, though, and would have to be improved to handle larger spaces. Contributions are welcome.

Finding reference sets

There are different algorithms to generate the three types of reference sets this library supports. For lex-canonical and gap-canonical reference sets, all rotations of a set are considered, canonized and compared lexically to find the lexicographically first one. For zeta-canonical reference sets, a substantially smaller set of rotations needs to be considered, as the lambda value of any given set with order not equal to four is equal to one of the principal elements of its plane, which means only as many rotations as there are principal elements have to be calculated. At most one third of the points of a plane are principal elements. Order four is special in that it permits no principal elements, but there are only two order four planes and thus two zeta-canonical sets to choose from anyway.

The example script pds_find_std_ref generates zeta-canonical reference sets from arbitrary samples. The example script pds_find_any_ref generates all three types of reference sets employing the search over all rotations of its input sets. For standard reference sets, this is of course less efficient than pds_find_std_ref, but can be used for independent verification.

Creating databases

Scripts in the maint directory of the git repository can populate the databases from plaintext input and conversely dump their contents in text form. There is also a script to generate the POD documents describing each of the databases.

AUTHOR

Martin Becker, <becker-cpan-mp at cozap.com>

COPYRIGHT AND LICENSE

Copyright (c) 2022-2023 by Martin Becker, Blaubeuren.

This library is free software; you can distribute it and/or modify it under the terms of the Artistic License 2.0 (see the LICENSE file).

DISCLAIMER OF WARRANTY

This library is distributed in the hope that it will be useful, but without any warranty; without even the implied warranty of merchantability or fitness for a particular purpose.