/ 
Math-DifferenceSet-Planar-1.002
River stage zero No dependents
/ Math::DifferenceSet::Planar

NAME

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

VERSION

This documentation refers to version 1.002 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
);
$ds = Math::DifferenceSet::Planar->from_lambda(9, 1);
$ds = Math::DifferenceSet::Planar->from_lambda(9, 1, 0);
$ds = Math::DifferenceSet::Planar->lex_reference(9);
$ds = Math::DifferenceSet::Planar->gap_reference(9);
$ds = Math::DifferenceSet::Planar->std_reference(9);
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;
$e0 = $ds->element(0);
$e0 = $ds->start_element;             # equivalent
@e  = $ds->elements_sorted;
$e0 = $ds->element_sorted(0);
$e0 = $ds->min_element;               # equivalent
$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;
$theta             = $ds->theta;
$lambda            = $ds->lambda;
$bool              = $ds->contains($e1);

@ep = $ds->plane_principal_elements;
@es = $ds->plane_supplemental_elements;
@ef = $ds->plane_fill_elements;
@ed = $ds->plane_derived_elements_of(@ep, @es);
@ue = $ds->plane_unit_elements;
@ne = $ds->plane_nonunit_elements;

$ds1 = $ds->translate(1);
$ds2 = $ds->canonize;
$ds2 = $ds->lex_canonize;                     # equivalent
$ds2 = $ds->translate(- $ds->start_element);  # equivalent
$ds2 = $ds->gap_canonize;
$ds2 = $ds->translate(- ($ds->largest_gap)[1]);   # eqv.
$ds2 = $ds->zeta_canonize;
$ds2 = $ds->translate(- $ds->theta);          # equivalent
@pm  = $ds->multipliers;
$it  = $ds->iterate_rotators;
while (my $m = $it->()) {
  $ds3 = $ds->multiply($m)->lex_canonize;
}
$it = $ds->iterate_planes;
while (my $ds3 = $it->()) {
  # as above, yielding canonical sets
}
$it = $ds->iterate_planes_zc;
while (my $ds3 = $it->()) {
  # similar, but yielding zeta-canonical sets
}
$it = $ds->iterate_principal_planes;
while (my $ds3 = $it->()) {
  # as above, yielding sets containing 0, 1, and 3
}
$it = $ds->iterate_principal_planes_zc;
while (my $ds3 = $it->()) {
  # similar, but yielding zeta-canonical sets containing 1
}

$cmp  = $ds1->compare($ds2);
$cmp  = $ds1->compare_topdown($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
}

@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;

$bool  = Math::DifferenceSet::Planar->known_std_ref(9);
$it    = Math::DifferenceSet::Planar->iterate_known_std_refs(10, 20);
$min   = Math::DifferenceSet::Planar->known_std_ref_min_order;
$max   = Math::DifferenceSet::Planar->known_std_ref_max_order;
$count = Math::DifferenceSet::Planar->known_std_ref_count;

$bool  = Math::DifferenceSet::Planar->known_lex_ref(9);
$it    = Math::DifferenceSet::Planar->iterate_known_lex_refs(10, 20);
$min   = Math::DifferenceSet::Planar->known_lex_ref_min_order;
$max   = Math::DifferenceSet::Planar->known_lex_ref_max_order;
$count = Math::DifferenceSet::Planar->known_lex_ref_count;

$bool  = Math::DifferenceSet::Planar->known_gap_ref(9);
$it    = Math::DifferenceSet::Planar->iterate_known_gap_refs(10, 20);
$min   = Math::DifferenceSet::Planar->known_gap_ref_min_order;
$max   = Math::DifferenceSet::Planar->known_gap_ref_max_order;
$count = Math::DifferenceSet::Planar->known_gap_ref_count;

$bool  = 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.

Sometimes, the two-element sets {0, 1}, {0, 2}, and {1, 2}, describing a simple triangle geometry, are also included in this class, but not here.

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 cyclic planar difference sets exist. Planar difference sets on other than cyclic groups do exist, though. We intend to cover them in a future extension of this library.

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. Another terminology calls such a set a reduced 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 can be found in the "SEE ALSO" section below. The database with orders up to 2¹⁷ requires 700 MB of storage space, while the default database only occupies 1 MB.

We work with pre-computed data for lack of super-efficient generators. Difference sets of order k can be generated with O(k²) operations with order 3 polynomials over 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). But accessing elements in strictly ascending numeric succession is possible as well.

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 or lex-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 can 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.

Another conjecture asserts that for any two cyclic 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 an identification of 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, different math libraries could identify any such set by its order and only two uniquely chosen numbers and be interoperable.

Such a convention would be an analogy for cyclic planar difference sets to what Conway polynomials are for finite fields. What makes the choice difficult is that each has its advantages and disadvantages. A major disadvantage of Conway polynomials is that, for large orders, they are computationally expensive (read: practically impossible) to obtain. Many candidates for reference difference sets, so far, including some actually based on Conway polynomials, seem to share this disadvantage.

Nevertheless, we do suggest a particular representative set for each set size here, which can be computed considerably faster than, say, the overall lexically minimal set. Our set of choice is the lexically minimal zeta-canonical set. We provide an algorithm that has to consider at most k/3 of the O(k⁴) possible sets of order k to find it. From the linear mappings taking this reference set to a given set we choose the one with the smallest linear factor, yielding unique values lambda and theta for the factor and translation amount. Together with the order, these two values define a unique fingerprint of each set. Linear mappings between sets can be computed from their lambda, theta value pairs and vice versa. Both directions of the mapping between complete sets and lambda, theta pairs can also be computed efficiently once the reference set is given.

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.

lex_reference

If $q or $p ** $j is a prime power, lex_reference is a replacement for new returning the lexicographically lowest difference set of that order, compared from smallest to largest element. If that set is not known, undef is returned.

For example, Math::DifferenceSet::Planar->lex_reference(3) returns an object representing the set {0, 1, 3, 9}.

If $q is not a prime power, or $p is not a prime, or the modulus of the set would exceed the size of a perl integer value, an exception is raised.

gap_reference

If $q or $p ** $j is a prime power, gap_reference is a replacement for new returning the lexicographically lowest difference set of that order, compared from largest to smallest element. If that set is not known, undef is returned.

For example, Math::DifferenceSet::Planar->gap_reference(3) returns an object representing the set {0, 1, 4, 6}.

If $q is not a prime power, or $p is not a prime, or the modulus of the set would exceed the size of a perl integer value, an exception is raised.

std_reference

If $q or $p ** $j is a prime power, std_reference is a replacement for new returning the lexicographically lowest zeta-canonical difference set of that order, compared from smallest to largest element. If that set is not known, undef is returned.

For example, Math::DifferenceSet::Planar->std_reference(2) returns an object representing the set {1, 2, 4}.

If $q is not a prime power, or $p is not a prime, or the modulus of the set would exceed the size of a perl integer value, 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.

Sets with sizes beyond those of stored sample sets can not be strictly validated. Only together with a true value of available(order) may success of from_elements be regarded as proof of correctness.

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. To be used with caution.

from_lambda

The method from_lambda creates a planar difference set from its order, lambda, and optional theta values. These values uniquely identify a set like a fingerprint. Reconstructing sets from their fingerprints is possible for orders with stored standard reference sets. Otherwise, or for invalid values, an exception is raised. If theta is not specified it is taken as zero, so that the result will be zeta-canonical.

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.

multipliers

The class method Math::DifferenceSet::Planar->multipliers(@args) is equivalent to the object method multipliers, called with the same arguments. See below.

n_planes

The class method Math::DifferenceSet::Planar->n_planes(@args) is equivalent to the object method n_planes, called with the same arguments. See below.

iterate_rotators

The class method Math::DifferenceSet::Planar->iterate_rotators(@args) is equivalent to the object method iterate_rotators, called with the same arguments. See below.

available

The class method Math::DifferenceSet::Planar->available(@params) checks whether new can be successfully called with the same parameters. This means either an order $q or a prime $p and an exponent $j specifies a prime power order, and a sample set of that order is available from the database of planar difference set 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 one stored sample planar difference set for each order 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 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 with distinct orders currently known to the module.

known_std_ref
known_lex_ref
known_gap_ref

The class methods Math::DifferenceSet::Planar->known_<type>_ref($order) with <type> one of std, lex, or gap, returns a boolean value of true if the current difference set samples database contains the reference set of the respective type, otherwise false. With the default database, this will be the true for all available sets, but data extension modules might provide large sample sets without accompanying reference sets of all kinds.

iterate_known_std_refs
iterate_known_lex_refs
iterate_known_gap_refs

The class methods Math::DifferenceSet::Planar->iterate_known_<type>_refs(@args) with <type> one of std, lex, or gap, provide iterators analogous to iterate, but iterating over the reference sets of the respective type rather than unspecified samples. Note that these iterations may terminate sooner than iterate and may even skip some orders.

known_std_ref_min_order
known_std_ref_max_order
known_std_ref_count
known_lex_ref_min_order
known_lex_ref_max_order
known_lex_ref_count
known_gap_ref_min_order
known_gap_ref_max_order
known_gap_ref_count

The class methods Math::DifferenceSet::Planar ->known_<type>_ref_<property> with <type> one of std, lex, or gap, and with <property> one of min_order, max_order, or count, return the smallest and largest order and the number of known reference sets of the respective kind.

In the unusual case of a database not containing any reference sets of the desired type, minimum and maximum will be undef and count will be zero.

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

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 (as returned by list_databases).

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. Files with other suffixes than ".db" will be ignored. Normal installations will have a single database named "pds.db". Installing data extensions will result in additional databases. By virtue of the naming scheme, extensions can provide larger default databases or special-case data not intended to replace the main data source. 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 number from zero to the modulus minus one (i.e. all elements 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.

If $t and the modulus have a common divisor greater than one, an exception is raised, as such a multiplication would not generate another planar difference set.

lex_canonize

If $ds is a planar difference set object, $ds->lex_canonize returns an object representing the lexically 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.

canonize

This method is an alias for lex_canonize. We keep it for historical reasons and because this kind of canonizing seems to be the most common one in the literature.

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. The order is always 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 canonical 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.

iterate_planes_zc

If $ds is a planar difference set object, $ds->iterate_planes_zc is similar to $ds->iterate_planes, but returns zeta-canonical rather than lexically canonical sets. This currently is the most efficient way to iterate over difference set planes.

iterate_principal_planes_zc

If $ds is a planar difference set object, $ds->iterate_principal_planes_zc is similar to $ds->iterate_planes_zc, but returns only the subsequence of zeta-canonical sets containing 1. This can be used to find zeta-canonical reference sets for orders not covered by the precomputed data available, from an arbitrary sample difference set. The number of principal planes of a particular order is equal to the number of principal elements of sets of that order. Cf. "plane_principal_elements".

iterate_principal_planes

If $ds is a planar difference set object, $ds->iterate_principal_planes is similar to $ds->iterate_principal_planes_zc, but returns lex-canonical rather than zeta-canonical sets. Apparently, the sets generated by this iterator are precisely the sets starting with elements 0, 1, and 3 [citation needed]. If this is true, this iterator can be used to efficiently find lex-canonical reference sets for orders not covered by the precomputed data available, from an arbitrary 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.

element

$ds->element($index) is equivalent to ($ds->elements)[$index], only more efficient.

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_sorted

$ds->element_sorted($index) is equivalent to ($ds->elements_sorted)[$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 and is thus equivalent to $ds->element_sorted(0).

max_element

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

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 of integer residues, in the order they are generated as powers of $ds->order_base. In scalar context, the number of multipliers is returned.

If $order is a prime power, or $p is a prime and $n is a positive integer, and $ds is a planar difference set object or its class, $ds->multipliers($order) or $ds->multipliers($p, $n) returns the set of multipliers for planes of order $order or $p ** $n, respectively. The class method call can be used to generate multipliers without creating a difference set first. For invalid arguments, an exception will be raised.

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.

If $order is a prime power, or $p is a prime and $n is a positive integer, and $ds is a planar difference set object or its class, $ds->iterate_rotators($order) or $ds->iterate_rotators($p, $n) returns an iterator generating rotators for planes of order $order or $p ** $n, respectively. The class method call can be used to generate rotators without creating a difference set first. For invalid arguments, an exception will be raised.

n_planes

If $ds is a planar difference set object, $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.

If $order is a prime power, or $p is a prime and $n is a positive integer, and $ds is a planar difference set object or its class, $ds->n_planes($order) or $ds->n_planes($p, $n) returns the number of distinct planes of order $order or $p ** $n, respectively. The class method call can be used to calculate this number without creating a difference set first. For invalid arguments, an exception will be raised.

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.

theta

The translation amount that takes the zeta-canonical representative of a set's plane to the set itself is called theta. Thus, zeta-canonizing is equivalent to translating by minus theta.

lambda

Starting with version 1.000, the library contains data of pre-computed reference sets, uniquely defined as outlined in the "Conventions" section above. The lambda, theta pair of values then identifies each individual set, and lambda in particular the plane of the set. This method returns the lambda value if the reference set is known, otherwise undef.

Note that, while lambda may be unknown for some sets, theta will always be defined even in the absence of the reference set.

plane_principal_elements

Each plane of k-element cyclic planar difference sets can be constructed from a set of at most floor(k/3) main elements and additional elements derived from these by an arithmetic progression. The main elements that are coprime to the modulus are called principal elements, the other main elements are called supplemental elements. Principal elements are sufficient to determine linear mappings between planes, while supplemental elements are sufficient to determine subplanes. Main elements, derived elements and at most two fill elements build a complete zeta-canonical set.

The method plane_principal_elements returns the principal elements of the plane of a set in list context, or their number in scalar context.

plane_supplemental_elements

The method plane_supplemental_elements returns the supplemental elements of the plane of a set in list context, or their number in scalar context.

plane_fill_elements

The method plane_fill_elements returns the fill elements of the plane of a set in list context, or their number in scalar context.

plane_derived_elements_of

The method plane_derived_elements_of, called with a single principal or supplemental element as argument, returns the elements derived from that element. This will be 3 * order_exponent - 1 elements for a principal element, and 3 * n - 1 elements, with n some divisor of order_exponent, for a supplemental element, in any order.

Called with a list of elements, the method will return a collected list of all derived elements of these elements.

Calling plane_derived_elements_of with other elements than principal or supplemental elements will yield some list with no meaningful relation to the plane at hand.

plane_unit_elements

In list context, elements of the zeta-canonical representative of a set's plane that are coprime to the modulus. In scalar context, their number. This number is also called τ₀ (tau zero) and is equal for all planes of equal order.

In the output, elements in the same p-orbit are grouped together.

plane_nonunit_elements

In list context, elements of the zeta-canonical representative of a set's plane that are not coprime to the modulus. In scalar context, their number.

In the output, elements in the same p-orbit are grouped together and longer orbits precede shorter ones.

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

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

compare_topdown

The method compare_topdown is a drop-in replacement for compare with the property that larger elements take priority over smaller elements on comparison.

Example: {0, 2, 3} < {0, 1, 5} when compared with this method, since 3 < 5.

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 order, 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 of order p**n has precisely 3·n multipliers.

EXAMPLES

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

To read the documentation of an example with filename file, run: perldoc -F file

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, are 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

A constructor method was called with an order not equal to a prime power. The order (which is the number of elements 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 all the elements returned true), the prime power conjecture would be proven wrong. Publishing this counter-example could earn you scientific merit. Alternatively, you may report a bug in this module's bug tracker. Please include all arguments.

order %d too large for this platform
order %d ** %d too large for this platform

A constructor method was called with an order or base and exponent pair defining an order too large for arithmetic with perl scalars. On 32-bit platforms, only sets with orders ≤ 46337 can be handled, and on 64-bit platforms, only sets with orders ≤ 3,037,000,493. This restriction might be lifted in a future release.

order %d is not a prime power
order base %d is not a prime

A constructor method was called with an order that was not a prime power or a base and power pair where the base was not a prime. If unsure about the factorization of the order, leave it to the module and call the constructor with just an order value. If the desired order is not a prime power at all, there is no finite field with this order and this module will not be able to generate a difference set.

element values inside range 0..%d expected

The class method from_elements or from_elements_fast 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 range of values from zero to the modulus minus one, matching the number of arguments, is indicated in the message.

impossible lambda value %d

The class method from_lambda was called with a lambda value not coprime to the modulus. Such lambda values are not possible.

non-canonical lambda value %d

The class method from_lambda was called with a lambda value not conforming to the convention achieving unambiguity by allowing just the smallest of equivalent values.

non-canonical theta value %d

The class method from_lambda was called with a theta value less than zero or greater than the modulus minus one. Theta values must be normalized.

reference set of order %d not available

The class method from_lambda was called with an order value no std_reference set is available for. To handle orders that large, a data extension module would be necessary.

apparently not a planar difference set

A constructor method 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 automatic 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 or from_elements_fast was called with non-unique values. One value occurring more than once is reported in the message.

delta %d elements missing

The class method from_elements or from_elements_fast was called with a set lacking elements with the specified difference. This is not a difference set.

factor %d 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 or from_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 a constructor must have been called with unverified set elements. The delta value and the modulus are reported in the message.

bogus set: divisor %d of order %d is not a multiplier

The method from_elements or from_elements_fast was called with a set with the property that a prime divisor of its order is not a multiplier. The divisor and the order are reported in the message. Sets with this property may also be reported as "apparently not a planar difference set", depending on other properties.

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

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.

parameters expected if called as a class method

One of the methods n_planes, sigma, multipliers, or iterate_rotators was called as a class method but without either an order parameter or an order base and exponent parameter pair. Methods describing properties of spaces need a specific space to relate to.

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. Extensions in various sizes are available on GitHub, but not intended to be uploaded to CPAN, to save storage space. To improve efficiency for much larger sets, the API should presumably be changed to use PDL vectors rather than plain perl arrays.

Sets beyond the size of sets in the sample database can be handled but will not be strictly verified upon instantiation. There is also a size limit imposed by the perl integer value size: Where it is 32 bit, only orders up to 46,337 are accepted, while with 64 bit the highest possible order is 3,037,000,493. Note that sample sets available via extension modules may very well exceed the 32 bit limit.

As our precomputed data is the result of computer programs running for hours or even days, there is a small probability some values may be wrong due to random malfunctions, especially for very large sets. We intend to double-check all of them and also hope for independent verification and extensions. Software to re-generate the data is included in the git repository.

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. 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 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 documentation points out where conjectures play a part in the computations. The library should thus be safe to use for studying sample sets and their properties and relationships, but not for nonexistence claims.

If, against popular expectations, the prime power conjecture for Singer sets, the existence of linear mappings conjecture, or the conjecture that all multipliers are divisors of the order should be proven wrong, we will have to decide how this library should be improved to reflect on the matter. Conversely, if some of these conjectures are finally confirmed, at least the documentation should be updated.

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.

The documentation should be reorganized to move detailed explanations into separate POD files while keeping API descriptions in the modules themselves.

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

With version 1.000, a release series intended to be more stable than previous versions has been established. New functionality may yet be introduced, but with backwards compatibility as an objective not to be given up lightly. There is of course room for improvements behind the scenes, too, notably addressing time and space efficiency.

Other changes may 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.

The inclusion of sets of order one has been considered to perhaps not justify the extra work so far. These three sets would satisfy difference set definitions but not all projective plane properties.

Further extensions of the sample set database are a part of the project but will only affect the collection of extension modules Math::DifferenceSet::Planar::Data::M, Math::DifferenceSet::Planar::Data::L, Math::DifferenceSet::Planar::Data::XL, etc.

For most planes in the larger collections, gap reference sets are not yet computed. At the time of the 1.002 release, we have computed gap reference sets for 644 planes only, while standard and lex reference sets are available for all of the 12400 planes included in the XL database, and even for most of the sets with millions of elements provided as an extra. Lacking more efficient algorithms, a substantial extension of gap reference sets would require massive computing power, but we expect to at least gradually increase their number over time.

More important perhaps is double- and triple-checking the data that is already present, before it can be regarded as scientifically acceptable. For each order, we used Singer's construction to generate a sample set, which is provably valid, and iterated through its multiples to find reference sets with their respective optimality properties. As this was of course performed by computer programs and computers may malfunction, repetitions or, even better, independent reiterations will increase confidence in the results and weed out actual errors.

Verifying difference set properties using complete difference tables is impractical for large sets. Verification using reference sets, on the other hand, relies partly on conjectures. Therefore, we are still looking for an efficient and proven verification method for very large sets.

SEE ALSO

AUTHOR

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

COPYRIGHT AND LICENSE

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