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-0.018
River stage zero No dependents
/ Math::DifferenceSet::Planar

NAME

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

VERSION

This documentation refers to version 0.018 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
  );
  $ds = Math::DifferenceSet::Planar->from_elements_fast(
    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
  $e0 = $ds->min_element;
  $e0 = $ds->max_element;
  $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);
  ($e1, $e2, $delta) = $ds->largest_gap;
  $eta               = $ds->eta;
  $zeta              = $ds->zeta;
  $bool              = $ds->contains($e1);

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

  $cmp  = $ds1->compare($ds2);
  $bool = $ds1->same_plane($ds2);
  @e    = $ds1->common_elements($ds2);

  ($factor, $delta) = $ds1->find_linear_map($ds2);
  # $ds2 == $ds1->multiply($factor)->translate($delta)
  foreach my $fd ( $ds1->find_all_linear_maps($ds2) ) {
    my ($factor, $delta) = @{$fd};
    # as above
  }

  $r  = Math::DifferenceSet::Planar->check_elements(    # DEPRECATED
    [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;

  print "ok" if Math::DifferenceSet::Planar->known_space(9);
  $desc = Math::DifferenceSet::Planar->known_space_desc(9);
  $min = Math::DifferenceSet::Planar->known_space_min_order;
  $max = Math::DifferenceSet::Planar->known_space_max_order;
  $count = Math::DifferenceSet::Planar->known_space_count;
  $it3 = Math::DifferenceSet::Planar->iterate_known_spaces;
  $it3 = Math::DifferenceSet::Planar->iterate_known_spaces(10,20);

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. A perhaps more commonly used term would be complete residue system.

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. The database with orders up to 2¹⁷ requires 2 GB of storage space, while the default database only occupies 2.5 MB.

We work with pre-computed data for lack of super-efficient generators. Difference sets can be generated with O(k²) operations with order 3 polynomials in an order k Galois field, which means only polynomial complexity, but still more than would be practical to perform at runtime. Getting rid of the databases will require better algorithms.

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. The canonical representative is also the lexically first set of its plane when sorted with priority on small elements.

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.

Sets of a plane could also be sorted lexically with priority on large elements. The first set in that ordering is the one with the largest gap between consecutive elements just left of zero. We call this set gap-canonical.

As divisors of the order, like order_base and order itself, are always multipliers, multiplying a planar difference set by order_base or order will yield translations of the original set. The translation amount upon multiplying a set with its order_base or with its order we call eta or zeta, respectively.

If eta is zero, so is zeta, and every plane has at least one such set. With some additional condition for uniqueness this yields another kind of choice of a canonical representative. This library provides it by the name of zeta_canonize.

Yet another conjecture asserts that for any two planar difference sets of the same order there is a linear function mapping one of them to the other. This is relevant for some of the algorithms implemented here. Notably, it gives rise to the notion of a "logarithm" identifying sets or planes by their linear relationship with some reference set. If there was a consensus among researchers on the choice of a reference set and of a particular solution from the solution space of the linear equation, math libraries could identify any such set by only two uniquely chosen numbers and be interoperable.

Such a convention would be an analogy for planar difference sets to what Conway polynomials are for finite fields. The choice, however, is not an easy one. A major disadvantage of Conway polynomials is that, for large orders, they are computationally expensive (read: practically impossible) to obtain. All candidates for reference sets, so far, including some actually based on Conway polynomials, seem to share this disadvantage.

Thus, this library makes use of linear mappings without exposing their "logarithm" aspect. We prefer to postpone any suggestion for this standardization until we are confident it is economically preferable. The library offers methods to find linear mappings between arbitrary sets, so users can pick their own reference sets and treat linear mappings relative to them as absolute. But see also the "ROADMAP" section below.

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.

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

Improper arguments, such as lists of numbers not actually defining a planar difference set, will cause from_elements to raise an exception either immediately rejecting the arguments or from failing initial checks. Note also that this method expects elements to be normalized, i.e. integer values from zero to the modulus minus one.

from_elements_fast

The method from_elements_fast is an alternative to from_elements that may be used if the arguments are known to be correct. Arguments not verified to define a planar difference set may yield a broken object with undefined behaviour, though. You have been warned.

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

DEPRECATED. OBSOLETE. Since an efficient and conclusive check is now integrated in the from_elements method, checking elements with incomplete evidence is now almost pointless. This method will be removed in release 1.0.

From the original documentation:

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.

End quote.

Before it was deprecated, the check_elements method in general and its parametrizations in particular were already flagged as experimental.

Progress has indeed been made by replacing the non-conclusive multiplier check by the conclusive linear mapping check: The conjecture that any two sets of same order can be mapped to each other with a linear function, and an efficient way to find such a function, now constitute a very practical verification of Singer type difference sets. It is considered cheap enough to run that it is now included in the from_elements constructor.

The assumption that all planar difference sets are of this type, however, which has lead to the initial scope of this library, should still not be taken for granted. This means the whole library may well be incomplete in this regard and fail to handle valid sets. The only exception is the verify_elements method, at the price of unpleasantly poor performance. To make progress here, some more research is needed. Contributions are welcome.

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_desc

The class method Math::DifferenceSet::Planar->known_space_desc($order) returns a descriptive string if pre-computed rotator space information for order $order is available to the module, otherwise undef.

The precise meaning of strings returned by known_space_desc is implementation specific and should not be relied upon. They are intended for documentation rather than further processing.

iterate_known_spaces

The class method Math::DifferenceSet::Planar->iterate_known_spaces returns a code reference that, repeatedly called, returns descriptions of all pre-computed rotator spaces known to the module, one by one. The iterator returns a false value when it is exhausted.

Math::DifferenceSet::Planar->iterate_known_spaces($lo, $hi) returns an iterator over all pre-computed spaces 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.

The strings returned by the iterators are the same as if obtained by known_space_desc.

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.

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

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.

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 start element. The canonical representative of a plane is also its lexicographically first set when sets are compared element-wise from smallest to largest element.

gap_canonize

If $ds is a planar difference set object, $ds->gap_canonize returns an object representing the translate of the set with the largest gap placed so that it is followed by zero. This is also the lexicographically first set of the plane when sets are compared element-wise from largest to smallest element.

zeta_canonize

If $ds is a planar difference set object, $ds->zeta_canonize returns an object representing the unique translate of the set defined as follows: If the plane has only one set with zeta equal to zero, take this. Otherwise, from the three sets with zeta equal to zero, take the set not containing the element zero. Here, zeta means the translation amount when the set is multiplied by its order, which always is a multiplier (see below).

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 first set returned will be on the same plane as the invocant. The iterator returns a false value when it is exhausted.

The succession of sets returned by iterate_planes, after the first set, may come in any implementation-specific order. If iterate_planes is repeatedly called within one program run and while the rotator space database is not changed, 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).

min_element

$ds->min_element returns the smallest element of the set.

max_element

$ds->max_element returns the largest element of the set.

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. It may fail if 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 )

largest_gap

If $ds is a planar difference set object with modulus $modulus, there is a unique pair of consecutive elements ($e1, $e2) of the set, when sorted by residue value and repeated cyclically, with the largest difference modulo the modulus.

For example, the set {3, 4, 6} (mod 7) has increases of {1, 2, 4} with the largest increase 4 between the elements 6 and 3 (wrapping around).

$ds->largest_gap returns both elements ($e1, $e2) and the increase amount ($e2 - $e1) % $ds->modulus called $delta. The number of modular integers not in the set between two consecutive elements of the set is called their gap. This gap can be calculated as $delta - 1.

eta

The sets provided by this module have prime power order and thus the prime is a divisor of the order and a multiplier. This means, 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.

zeta

The translation amount from multiplying a set by its order is called zeta here, and the method zeta returns its value. For sets with prime order, zeta and eta are of course equal.

Binary Operators

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.

Note that $e has to be in the range of zero to the modulus minus one to be found, as modular integers are represented by their standard residue values throughout this library.

compare

If $ds1 and $ds2 are planar difference set objects, $ds1->compare($ds2) returns a comparison value less than zero, zero, or greater than zero, if $ds1 precedes, is equal, or follows $ds2 according to this order relation: Smaller sets before larger sets, sets of equal size in lexicographic order when written from smallest to largest element and compared element-wise left to right.

Example: {0, 4, 5} < {1, 2, 4} < {1, 2, 6} < {0, 1, 3, 9}.

same_plane

If $ds1 and $ds2 are planar difference set objects, $ds1->same_plane($ds2) returns a boolean value of true if $ds2 is a translate of $ds1, otherwise false. If they do, they will have either precisely one element or all elements in common and the translation amount will be equal to the difference of their start elements.

common_elements

If $ds1 and $ds2 are planar difference set objects of equal order, $ds1->common_elements($ds2) returns a list of elements that are in both sets. For sets of different size, an empty list will be returned. In scalar context, the length of the list will be returned.

find_linear_map

If $ds1 and $ds2 are planar difference set objects of equal order, $ds1->find_linear_map($ds2) returns two values $factor and $delta with the property that $ds1->multiply($factor)->translate($delta) will be equal to $ds2. It is conjectured that this is always possible. For sets of different size, or if the arguments constitute a counterexample to the conjecture, exceptions will be raised.

Note that the solution will not be unique and may depend on circumstances not easy to predict.

find_all_linear_maps

If $ds1 and $ds2 are planar difference set objects of equal order, $ds1->find_all_linear_maps($ds2) returns a list of arrayrefs holding two values $factor and $delta each, with the property that $ds1->multiply($factor)->translate($delta) will be equal to $ds2. It is conjectured that this is always possible. For sets of different size, or if the arguments constitute a counterexample to the conjecture, an empty list will be returned.

The pairs in the result will be sorted in ascending order by their first component.

Technically, the list will be created using find_linear_map and multipliers. The completeness of the solution space thus depends on the 3n multipliers conjecture, asserting that each set has precisely 3·n multipliers.

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.

apparently not a planar difference set: %s

The class method from_elements was called with values that apparently define no planar difference set. Note that this verdict might be incorrect if the linear mapping conjecture turned out to be wrong, when verifying a counterexample, but it will be correct with all actually wrong sets.

You can override the internal linear mapping check by using from_elements_fast in place of from_elements. Unverified sets may yield broken objects with inconsistent behaviour, though.

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.

sets of same size expected

One of the methods find_linear_map or find_all_linear_maps was called with two sets of different size. Linear map functions can only exist for sets with equal size.

unaligned sets: %s versus %s

One of the methods find_linear_map or find_all_linear_maps surprisingly did not succeed. This would prove another conjecture wrong, or, more likely, indicate one of the objects was created from elements not actually representing a valid planar difference set. Abbreviated element lists of two difference sets are included in the message. For technical reasons, these may be translates of the original invocants.

DEPENDENCIES

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

To build and install, it also needs:

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.

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.

ROADMAP

Except possibly for small corrections, the series of beta releases is now drawing to an end, and work on release 1.0 has begun. This will maintain most of the current API but also include major changes.

We will drop the limitation on from_elements() to require a set size that is represented in the database. The database will be more space-efficient, so that we can ship more sets, and the sets there will provide shortcuts to searches that can also be carried out without them.

The internal data format will be extended to speed up some algorithms, particularly the logarithm calculation and set verification. And yes, we will finally settle on a logarithm base set for each order, and thus give each set a unique identification by two numbers (three, if the order is taken into account), and we will expose both directions of the mapping between sets and logarithms as methods.

Releases after 1.0 will of course reflect research progress, as we get along, and also work towards other goals mentioned in the CONTRIBUTING agenda. In particular, we intend to cover more geometric and algebraic aspects of planar difference sets. We will also look out for opportunities to interface with more generic set types.

SEE ALSO

  • Math::DifferenceSet::Planar::Data - planar difference set storage.

  • Math::ModInt - modular integer arithmetic.

  • PDL - the Perl Data Language.

  • Moore, Emily H., Pollatsek, Harriet S., "Difference Sets", American Mathematical Society, Providence, 2013, ISBN 978-0-8218-9176-6.

  • Dinitz, J.H., Stinson, D.R., "Contemporary Design Theory: A collection of surveys", John Wiley and Sons, New York, 1992, ISBN 0-471-53141-3.

  • Gordon, Daniel M., "La Jolla Difference Set Repository". https://www.dmgordon.org/diffset/

AUTHOR

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

COPYRIGHT AND LICENSE

Copyright (c) 2019-2022 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.