NAME

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

VERSION

This documentation refers to version 0.015 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);
$e0 = $ds->start_element;             # equivalent
$np = $ds->n_planes;
$p  = $ds->order_base;
$n  = $ds->order_exponent;

($e1, $e2) = $ds->find_delta($delta);
($e1, $e2) = $ds->peak_elements;
($e1, $e2) = $ds->find_delta(($ds->modulus - 1) / 2);
$eta       = $ds->eta;
$bool      = $ds->contains($e1);

$ds1 = $ds->translate(1);
$ds2 = $ds->canonize;
$ds2 = $ds->translate(- $ds->element(0)); # equivalent
@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
}

$r  = Math::DifferenceSet::Planar->check_elements(
  [0, 1, 3, 9, 27, 49, 56, 61, 77, 81], 10
);
print "not small non-negative integers"  if !defined $r;
print "not a planar difference set"      if !$r;
print "multiplier check failed"          if defined $r and 0 eq $r;
print "probably a planar difference set" if defined $r and 1 == $r;
print "verified planar difference set"   if defined $r and 2 == $r;

@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";
}
$min   = Math::DifferenceSet::Planar->available_min_order;
$max   = Math::DifferenceSet::Planar->available_max_order;
$count = 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 multiplier of D. If t is coprime to n but either identical to 1 (mod n) or not a multiplier, 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.

Each planar difference set has, for each nonzero element delta of its ring ℤ_n, a unique pair of elements (e1, e2) satisfying e2 - e1 = delta. For delta = 1, we call e1 the start element. For delta = (n - 1) / 2, we call e1 and e2 the peak elements.

As order_base is (conjecturally) always a multiplier, multiplying a planar difference set by order_base will yield a translation of the original set. We call the translation amount eta.

CLASS VARIABLES

$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 expensive, having quadratic space and time complexity, 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.

The return value is undef if the set is not a set of non-negative integers of appropriate size, defined but false if it is, but not happens to represent a cyclic planar difference set, and true on success.

check_elements

If @e is an array of integer values, Math::DifferenceSet::Planar->check_elements(\@e) returns a true value if those values probably 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 may wrongly return true in some cases, but is less expensive than the exhaustive check verify_elements as it has only fixed space and linear time complexity.

An optional positive second argument $depth governs the effort to be taken, larger values meaning more work and higher accuracy. A depth value of half the modulus (rounded down) will make check_elements equivalent to verify_elements in complexity and accuracy.

More precisely, the check looks for unique small differences of elements of the set. Proper planar difference sets will of course provide only uniqe differences and thus pass the test.

The return value is 2 if the set is proven to be correct, 1 if it is probably correct, a false but defined value if it is proven to be not correct and undef if it is not even a set of distinct non-negative integers of appropriate size.

An optional third argument $factor controls the check whether the given factor is a multiplier. For planar difference sets this module generates, order_base is indeed a multiplier. Thus this combined check should give a good heuristic whether a given set is actually representing a planar difference set related to a finite field like the ones generated by this module.

If the factor is not specified, the check will be performed with a suitable multiplier, i.e. the smallest base the order is a power of. To skip the multiplier check, a factor of 1 can be specified. This should be done to avoid using conjectural evidence.

Currently, the return value is an empty string if the small difference uniqueness check failed and '0' if it succeeded but the multiplier check failed. This may be taken as a debugging aid, but productive code should not rely on particular false values, as future releases may have different checks and thus no longer support the same kind of distinction.

If the conjecture that all planar difference sets have order_base as multiplier holds, the combined check will rather efficiently detect most sets that aren't. For a counterexample to the conjecture, the check might return 2 with a high depth value and 0 with a low depth value.

Currently, the check_elements method should be regarded as experimental. Future research might provide other, more useful check types or parametrizations.

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_min_order

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

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.

known_space

The class method Math::DifferenceSet::Planar->known_space($order) returns a positive integer if pre-computed rotator space information for order $order is available to the module, otherwise zero. Currently, in case of availability, the integer number is the number of radices used for difference set plane enumeration. For sets with known space, iterate_planes and iterate_rotators will be more efficient than otherwise.

The precise meaning of non-zero values returned by known_space is implementation specific and should not be relied upon.

known_space_min_order

The class method Math::DifferenceSet::Planar->known_space_min_order returns the smallest order of pre-computed rotator space information available to the module, if any, otherwise undef.

known_space_max_order

The class method Math::DifferenceSet::Planar->known_space_max_order returns the maximum order of pre-computed rotator space information available to the module, if any, otherwise zero.

known_space_count

The class method Math::DifferenceSet::Planar->known_space_count returns the number of records of pre-computed rotator space information available to the module, for statistics.

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.

File names can be absolute paths or relative to the distribution-specific share directory.

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 or start 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.

The succession of sets returned by iterate_planes may come in any implementation-specific order. If iterate_planes is repeatedly called within one program run, the same difference set will always yield the same sequence of planes, however. Multiple iterators will each have an individual state and run independently, even if generated from the same sample difference set.

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.

start_element

$ds->start_element is equivalent to $ds->element(0).

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.

find_delta

If $ds is a planar difference set object and $delta is an integer value, $ds->find_delta($delta) returns a pair of elements ($e1, $e2) of the set with the property that $e2 - $e1 == $delta (modulo the modulus of the set). If $delta is not zero or a multiple of the modulus this pair will be unique.

The unique existence of such a pair is in fact the defining quality of a planar difference set. The algorithm has an O(n) time complexity if n is the cardinality of the set. If it fails, the set stored in the object is not actually a difference set. An exception will be raised in that case.

peak_elements

If $ds is a planar difference set object with modulus $modulus, there is a unique pair of elements ($e1, $e2) of the set with maximal distance: $dmax = ($modulus - 1) / 2, and ($e2 - $e1) % $modulus == $dmax, and ($e1 - $e2) % $modulus == $dmax + 1. $ds->peak_elements returns the pair ($e1, $e2).

Equivalently, $e1 and $e2 can be computed as: ($e1, $e2) = $ds->find_delta( ($ds->modulus - 1) / 2 )

eta

The prime power conjecture of planar difference sets states that any such set has prime power order. This would also be implied by the stronger conjecture that all finite projective planes have prime power order. Another conjecture asserts that the prime number is a multiplier of the set. Thus multiplying the set by the prime is equivalent to a translation. The translation amount is called eta here and the method eta returns its value.

Technically, $ds->eta is equivalent to $ds->multiply($ds->order_base)->element(0)-$ds->element(0), wich would still be defined if one of the conjectures was proven wrong, though not quite meaningful if the multiplication result was on a different plane.

contains

If $ds is a planar difference set object and $e an integer number, $ds->contains($e) returns a boolean that is true if $e is an element of the set.

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.
bogus set: delta not found: %d (mod %d): One of the methods find_delta or peak_elements was called on an object of a set lacking the required delta value. This means that the set was not actually a difference set, which in turn means that previously a constructor must have been called with unverified set elements. The delta value and the modulus are reported in the message.

DEPENDENCIES

This library requires these other modules and libraries at run-time:

Carp,
DBD::SQLite version 1.48 or later,
DBIx::Class,
File::Share,
File::Spec,
Math::Prime::Util version 0.59 or later.

To build and install, it also needs:

ExtUtils::MakeMaker version 7.06 or later,
File::ShareDir::Install,
File::Spec,
Test::More.

The minimum required perl version is 5.10. Some example scripts use <<>> and thus require perl version 5.22 or later to run.

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 several orders of magnitude 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. With 64 bit integer arithmetic it is safe to handle sets with 21 bit order, or 42 bit modulus, or 2 million elements. On platforms with 32 bit perl integers, do not use sets with more than 1290 elements.

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.

The verify_elements() method currently builds a complete operator table in memory. This does not scale very well in terms of either space or time for larger sets.

Other methods for verifying difference sets are still under development. The current version of check_elements() may be considered a first step. As sets with multipliers are much rarer than sets with unique small differences, multiplier checks could speed up verification considerably. Note, however, that the multiplier check as implemented here is based on conjectural matter and thus might inaccurately reject some sets.

Bug reports and suggestions are welcome. Please submit them through the github issue tracker, https://github.com/mhasch/perl-Math-DifferenceSet-Planar/issues.

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

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 VARIABLES

CLASS METHODS

Constructors

Other class methods

OBJECT METHODS

Constructors

Property Accessors

EXAMPLES

OTHER FILES

DIAGNOSTICS

DEPENDENCIES

BUGS AND LIMITATIONS

SEE ALSO

AUTHOR

COPYRIGHT AND LICENSE

DISCLAIMER OF WARRANTY

Module Install Instructions