The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.
 / 
Math-DifferenceSet-Planar-1.002
River stage zero No dependents
/ Math::DifferenceSet::Planar::Computation

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 three Pari/GP scripts prime_order_samples.gp, nonprime_order_samples.gp, and extra_large_sample.gp working like this.

Another implementation of the algorithm will be included in the examples collection of the separate perl library Math-GaloisField (work in progress by the same author).

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. Algorithms for other orders 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 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 zeta-canonical set 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 planes of the candidate sets for zeta-references are called principal planes and are at the same time the planes containing zeta-canonical sets containing the element 1 and of lex-canonical sets containing 0, 1, and 3. Thus browsing through principal planes yields both zeta-canonical and lex-canonical references (for orders other than 4).

The example script pds_find_std_ref generates zeta-canonical reference sets from arbitrary samples. The example script pds_find_lex_ref generates lex-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 and lex reference sets, this is of course less efficient than the specialized algorithms but can be used for independent verification. Indeed one may choose to use only the generic algorithm for lex-canonical references as long as we lack a citation for a proof of the principal planes property concerning 0-1-3 sets. The result has been verified for orders up to 11069 at least, giving the statement some heuristic support.

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-2024 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).

The licence grants freedom for related software development but does not cover incorporating code or documentation into AI training material. Please contact the copyright holder if you want to use the library whole or in part for other purposes than stated in the licence.

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.