NAME

Math::DifferenceSet::Planar - object class for planar difference sets

VERSION

This documentation refers to version 0.008 of Math::DifferenceSet::Planar.

SYNOPSIS

  use Math::DifferenceSet::Planar;

  $ds = Math::DifferenceSet::Planar->new(9);
  $ds = Math::DifferenceSet::Planar->new(3, 2);
  $ds = Math::DifferenceSet::Planar->from_elements(
    0, 1, 3, 9, 27, 49, 56, 61, 77, 81
  );
  print "ok" if Math::DifferenceSet::Planar->verify_elements(
    0, 1, 3, 9, 27, 49, 56, 61, 77, 81
  );
  $o  = $ds->order;
  $m  = $ds->modulus;
  @e  = $ds->elements;
  @e  = $ds->elements_sorted;
  $e0 = $ds->element(0);
  $np = $ds->n_planes;
  $p  = $ds->order_base;
  $n  = $ds->order_exponent;

  $ds1 = $ds->translate(1);
  $ds2 = $ds->canonize;
  $ds2 = $ds->translate(- $ds->element(0));
  @pm  = $ds->multipliers;
  $it  = $ds->iterate_rotators;
  while (my $m = $it->()) {
    $ds3 = $ds->multiply($m)->canonize;
  }
  $it = $ds->iterate_planes;
  while (my $ds3 = $it->()) {
    # as above
  }

  @db = Math::DifferenceSet::Planar->list_databases;
  $count = Math::DifferenceSet::Planar->set_database($db[0]);

  print "ok" if Math::DifferenceSet::Planar->available(9);
  print "ok" if Math::DifferenceSet::Planar->available(3, 2);
  $it1 = Math::DifferenceSet::Planar->iterate_available_sets;
  $it2 = Math::DifferenceSet::Planar->iterate_available_sets(10, 20);
  while (my $ds = $it2->()) {
    $o = $ds->order;
    $m = $ds->modulus;
    print "$o\t$m\n";
  }
  $om = Math::DifferenceSet::Planar->available_max_order;
  $ns = Math::DifferenceSet::Planar->available_count;

DESCRIPTION

A planar difference set in a modular integer ring ℤ_n, or cyclic planar difference set, is a subset D = {d_1, d_2, ..., d_k} of ℤ_n such that each nonzero element of ℤ_n can be represented as a difference (d_i - d_j) in exactly one way. By convention, only sets with at least three elements are considered.

Necessarily, for such a set to exist, the modulus n has to be equal to (k - 1) · k + 1. If (k - 1) is a prime power, planar difference sets can be constructed from a finite field of order (k - 1). It is conjectured that no other planar difference sets exist. If other families of planar difference sets should be discovered, this library would be due to be extended accordingly.

If D = {d_1, d_2, ..., d_k} ⊂ ℤ_n is a difference set and a is an element of ℤ_n, D + a = {d_1 + a, d_2 + a, ..., d_k + a} is also a difference set. D + a is called a translate of D. The set of all translates of a planar difference set as lines and the elements of ℤ_n as points make up a finite projective plane (hence the name).

If t is an element of ℤ_n coprime to n, D · t = {d_1 · t, d_2 · t, ..., d_k · t} is also a difference set. If D · t is a translate of D, t is called a multiplicator of D. If t is coprime to n but either identical to 1 (mod n) or not a multiplicator, it is called a rotator. Rotators of planar difference sets are also rotators of planes as translates of a difference set are mapped to translates of the rotated set. We call a minimal set of rotators spanning all plane rotations a rotator base.

Math::DifferenceSet::Planar provides examples of small cyclic planar difference sets constructed from finite fields. It is primarily intended as a helper module for algorithms employing such sets. It also allows to iterate over all sets of a given size via translations and rotations, and to verify whether an arbitrary set of modular integers is a cyclic planar difference set.

Currently, only sets with k ≤ 4097, or moduli ≤ 16_781_313, are supported by the CPAN distribution of the module. These limits can be extended by installing a database with more samples. Instructions on where to obtain additional data will be included in an upcoming release.

Conventions

For efficiency, all elements handled by this module are represented as simple Perl integers rather than proper Math::ModInt objects. All elements of a difference set share the same modulus, accessible through the modulus method. Thus the integers can easily be converted to modular integer objects if necessary.

By convention, the default order elements of a difference set are enumerated in by this module starts with the unique elements s and s + 1 that are both in the set, and continues by smallest possible increments. For example, { 3, 5, 10, 11, 14 } (mod 21) would be enumerated as (10, 11, 14, 3, 5).

Each plane (i.e. complete set of translates of a planar difference set) has a unique set containing the elements 0 and 1. We call this set the canonical representative of the plane.

CLASS VARIABLE

$VERSION: $VERSION is the version number of the module and of the distribution.

CLASS METHODS

Constructors

new

If $q is a prime power, Math::DifferenceSet::Planar->new($q) returns a sample planar difference set object with $q + 1 elements, unless $q exceeds some implementation limitation (see below).

If $p is a prime number and $j is an integer > 0, Math::DifferenceSet::Planar->new($p, $j) returns a sample planar difference set object with $p ** $j + 1 elements, unless $p ** $j exceeds some implementation limitation.

If $q is not a prime power, or $p is not a prime, or the number of elements would exceed the limitation, an exception is raised.

from_elements

If @e is a cyclic planar difference set, represented as distinct non-negative integer numbers less than some modulus, Math::DifferenceSet::Planar->from_elements(@e) returns a planar difference set object with precisely these elements.

Note that arguments not verified to define a planar difference set may yield a broken object with undefined behaviour. Note also that this method expects elements to be normalized, i.e. integer values from zero to the modulus minus one.

The modulus itself is not a parameter, as it can be computed from the number k of arguments as m = k² - k + 1.

Other class methods

verify_elements

If @e is an array of integer values, Math::DifferenceSet::Planar->verify_elements(@e) returns a true value if those values define a cyclic planar difference set and are normalized, i.e. non-negative and less than the modulus, otherwise a false value. Note that this check is somewhat expensive, but should work regardless of the method the set was constructed by. It may thus be used to verify cyclic planar difference sets this module would not be capable of generating itself.

available

The class method Math::DifferenceSet::Planar->available(@params) checks whether new can be called with the same parameters, i.e. either an order $q or a prime $p and an exponent $j indicating a prime power order that are available from the database of PDS samples. It returns a true value if sample sets with the given parameters are present, otherwise false.

iterate_available_sets

The class method Math::DifferenceSet::Planar->iterate_available_sets returns a code reference that, repeatedly called, returns all sample planar difference sets known to the module, one by one. The iterator returns a false value when it is exhausted.

Math::DifferenceSet::Planar->iterate_available_sets($lo, $hi) returns an iterator over all samples with orders between $lo and $hi (inclusively), ordered by ascending size. If $lo is not defined, it is taken as zero. If $hi is omitted or not defined, it is taken as plus infinity. If $lo is greater than $hi, they are swapped and the sequence is reversed, so that it is ordered by descending size.

available_max_order

The class method Math::DifferenceSet::Planar->available_max_order returns the order of the largest sample planar difference set currently known to the module.

available_count

The class method Math::DifferenceSet::Planar->available_count returns the number of sample planar difference sets currently known to the module.

set_database

Although normally set automatically behind the scenes, the database of sample difference sets may be reset to a known alternative file location. Math::DifferenceSet::Planar->set_database($filename) does this and tries to open the file for subsequent lookups. On success, it returns the number of available sets in the database. On failure, it raises an exception.

list_databases

Math::DifferenceSet::Planar->list_databases returns a list of available databases from the distribution-specific share directory, ordered by decreasing priority. Priority is highest for file names beginning with "pds", and for large files. Normal installations will have a single database named 'pds.db'. Installing data extensions will result in additional databases. It should be safe to call set_database with each of the database names returned by list_databases.

OBJECT METHODS

Constructors

translate

If $ds is a planar difference set object and $t is an integer number, $ds->translate($t) returns an object representing the translate of the set by $t % $ds->modulus.

Translating by each element of the cyclic group in turn generates all difference sets belonging to one plane.

canonize

If $ds is a planar difference set object, $ds->canonize returns an object representing the canonical translate of the set. All sets of a plane yield the same set upon canonizing. Using our enumeration convention, an equivalent operation to canonizing is to translate by the negative of the first element.

multiply

If $ds is a planar difference set object and $t is an integer number coprime to the modulus, $ds->multiply($t) returns an object representing the difference set generated by multiplying each element by $t.

iterate_planes

If $ds is a planar difference set object, $ds->iterate_planes returns a code reference that, repeatedly called, returns all canonized planar difference sets of the same size, generated using a rotator base, one by one. The iterator returns a false value when it is exhausted.

Property Accessors

order: $ds->order returns the order of the difference set $ds. This is one less than the number of its elements.
modulus: $ds->modulus returns the size of the cyclic group the difference set $ds is a subset of. If k is the number of elements of a planar difference set, its order is k - 1, and its modulus is k² - k + 1.
elements: $ds->elements returns all elements of the difference set as a list, ordered as defined in "Conventions". In scalar context, it returns the number of elements.
elements_sorted: $ds->elements_sorted returns all elements of the difference set as a list, ordered by ascending numerical value. In scalar context, it returns the number of elements.
element: $ds->element($index) is equivalent to ($ds->elements)[$index], only more efficient.
n_planes: $ds->n_planes returns the number of distinct planes that can be generated from the planar difference set $ds or, equivalently, the number of elements in a rotator base of order $ds->order.
order_base: If $ds is a planar difference set object with prime power order, $ds->order_base returns the prime.
order_exponent: If $ds is a planar difference set object with prime power order, $ds->order_exponent returns the exponent of the prime power.
multipliers: If $ds is a planar difference set object, $ds->multipliers returns the set of its multipliers as a list sorted by ascending numeric value. In scalar context, the number of multipliers is returned.
iterate_rotators: If $ds is a planar difference set object, $ds->iterate_rotators returns a code reference that, repeatedly called, returns the elements of a rotator base of the set. The iterator returns a zero value when it is exhausted.

EXAMPLES

The distribution contains an examples directory with several self-documenting command line tools for generating and manipulating planar difference sets, and for displaying available databases.

OTHER FILES

The library is packaged together with a small SQLite version 3 database named pds.db. This is installed in a distribution-specific share directory and accessed read-only at run-time.

The same directory can hold additional databases from extension projects. Larger databases, as well as tools to create them, will be distributed separately.

DIAGNOSTICS

PDS(%s) not available: The class method new was called with parameters this implementation does not cover. The parameters are repeated in the message. To avoid this exception, verify the parameters using the available method before calling new.
this implementation cannot handle order %d: The class method from_elements was called with a number of elements not equal to a prime power plus one. The number of arguments minus one is repeated in the message. The given arguments may or may not define a planar difference set, but if they were (i.e. verify_elements called with the same arguments returned true), the prime power conjecture would be proven wrong. Many mathematical journals would certainly be keen to publish this counter-example. Alternatively, you may report a bug in this module's bug tracker. Please include all arguments.
element values inside range 0..%d expected: The class method from_elements was called with elements that were not normalized, i.e. integer values from zero to the modulus minus one, or some values were too large for a difference set of the given size. The modulus matching the number of arguments, minus one, is indicated in the message.
elements of PDS expected: The class method from_elements was called with values that obviously define no planar difference set. Note that not all cases of wrong values will be detected this way. Dubious values should always be verified before they are turned into an object.
duplicate element: %d: The class method from_elements was called with non-unique values. One value occuring more than once is reported in the message.
%d: factor is not coprime to modulus: The object method multiply was called with an argument that was not an integer coprime to the modulus. The argument is repeated in the message. Factors not coprime to the modulus would not yield a proper difference set.

BUGS AND LIMITATIONS

As this library depends on a database with sample sets, it will not generate arbitrarily large sets. The database packaged with the base module is good for sets with at most 4097 elements. An extension by factor 16 is in preparation. For much larger sets, the API should presumably be changed to use PDL vectors rather than plain perl arrays, to improve efficiency.

To handle difference sets on groups other than cyclic groups, some slight API changes would be required. It should accept group elements as well as small integers as arguments. Although lacking practical examples, this is intended to be dealt with in a future release.

The literature on difference sets, connecting algebra, combinatorics, and geometry, is quite rich in vocabulary. Specialized libraries like this one can only cover a small selection of the concepts presented there, and the nomenclature will be more consistent with some authors than others. The topic is also abundant with unanswered questions.

This library is provided as a calculator tool, but not claiming to prove any of its implicit or explicit assumptions. If you do find something wrong or inaccurate, however, the author will be glad to be notified about it and address the issue.

Bug reports and suggestions are welcome. Please submit them through the CPAN RT, https://rt.cpan.org/NoAuth/ReportBug.html?Queue=Math-DifferenceSet-Planar.

More information for potential contributors can be found in the file named CONTRIBUTING in this distribution.

AUTHOR

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

COPYRIGHT AND LICENSE

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.10.0 or, at your option, any later version of Perl 5 you may have available.

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.

To install Math::DifferenceSet::Planar, copy and paste the appropriate command in to your terminal.

cpanm

cpanm Math::DifferenceSet::Planar

CPAN shell

perl -MCPAN -e shell
install Math::DifferenceSet::Planar

For more information on module installation, please visit the detailed CPAN module installation guide.

	Global
`s`	Focus search bar
`?`	Bring up this help dialog

	GitHub
`g` `p`	Go to pull requests
`g` `i`	go to github issues (only if github is preferred repository)

	POD
`g` `a`	Go to author
`g` `c`	Go to changes
`g` `i`	Go to issues
`g` `d`	Go to dist
`g` `r`	Go to repository/SCM
`g` `s`	Go to source
`g` `b`	Go to file browse

	Search terms
module: (e.g. module:Plugin)
distribution: (e.g. distribution:Dancer auth)
author: (e.g. author:SONGMU Redis)
version: (e.g. version:1.00)

NAME

VERSION

SYNOPSIS

DESCRIPTION

Conventions

CLASS VARIABLE

CLASS METHODS

Constructors

Other class methods

OBJECT METHODS

Constructors

Property Accessors

EXAMPLES

OTHER FILES

DIAGNOSTICS

BUGS AND LIMITATIONS

SEE ALSO

AUTHOR

COPYRIGHT AND LICENSE

DISCLAIMER OF WARRANTY

Module Install Instructions