GitHub

Frames over Finite Fields

Over finite fields there are two cases: Case O (case=:O) and Case U (case=:U) which must be specified on calls to functions. See [1], [2] and [5] for more details.

Instructions for Case U

Case U (case=:U) requires that the underlying field be a field extension of even degree. You can select such a field using Oscar in a variety of ways (Oscar is loaded by FrameTheory.jl but not imported). Examples below:

using Oscar
ff = GF(5,2,"a");
ff = GF((5^3)^2);

You can also explicitly build a quadratic extension with an irreducible polynomial of degree 2. But this is generally not recommended as fields built this way will be much slower.

base_f = GF(5,2,"b");
Kx, x = base_f["x"];
# specify degree 2 irreducible polynomial.
ff, a = finite_field(x^2+x+1, "a");

When computing with matrices in case U, you must always specify case=:U, when calling functions. An example of constructing and using an ETF in case U is the following:

ff = GF(125^2);
ffx, x = ff["x"];
a = roots(x^2+x+1)[1];

sic = matrix(ff, [
        1    1       1    -1 -1  -1    0   0      0;
        0    0       0     1  a  a^2  -1 -1*a   -1*a^2;
       -1  -1*a^2  -1*a    0  0   0    1  a^2     a
]);
gram = conjugate_transpose(sic)*sic;

binder_finder(gram, case=:U)

Instructions for Case O

Case O (case=:O) requires that the underlying field have odd characteristic. Specify the finite field using Oscar.

using Oscar

ff = GF(5,3,"a");

Then specify case=:O when calling functions.

ff = GF(3);
Phi = matrix(ff, [
   0 0 0  0  1  1  1  1  1  1;
   0 0 2  1  0  0  1  1  2  2;
   1 2 0  0  0  0  1  2  1  2;
   1 1 2  2  1  2  0  0  0  0     
])
# Here the frame Phi is defined in F_3^4 with a scalar product whose gram is Diag(1,1,1,2).
gram = transpose(Phi)*diagonal_matrix([ff(1),ff(1),ff(1),ff(2)])*Phi

is_discr_Phi_square = is_discr_square(gram);  # returns false

binder_finder(3, gram, case=:O)

Frames in case O, have the added complexity of their discriminant, which can be determined by is_discr_square.

Basic Functionality

FrameTheory.is_frame — Method
is_frame(gram, case) -> Tuple{Bool,Int}

Arguments

  • gram::FqMatrix: A square matrix defined over a finite field.
  • case::Symbol: :U for case U and :O for case O.

Returns

  • frame_bool::Bool
  • d::Int

Determines if the matrix gram is the Gram matrix for some frame, in the provided case. Returns a boolean frame_bool if the provided matrix is the Gram matrix of a frame for some d-dimensional space. if frame_bool is false then d would be nothing.

Examples

The following example shows that the following matrix is a frame for a 4 dimensional space.

julia> ff = GF(3);

julia> Phi = matrix(ff, [
        0 0 0  0  1  1  1  1  1  1;
        0 0 2  1  0  0  1  1  2  2;
        1 2 0  0  0  0  1  2  1  2;
        1 1 2  2  1  2  0  0  0  0     
       ]);

julia> is_frame(transpose(Phi)*Phi, case=:O)
(true, 4)
source
FrameTheory.is_discr_square — Function
is_discr_square(gram) -> Bool

Arguments

  • gram::FqMatrix: A square matrix defined over a finite field which is the Gram matrix of a frame in case :O.

Returns

  • square_discr::Bool boolean value on if the the discriminant of the frame's Gram is a square.

Given the Gram matrix of a frame in Case O, this determines if the frame's span has a discriminant that is a square or not.

Examples

The following example shows a matrix which is a frame for a 4 dimensional space.

julia> ff = GF(3);

julia> Phi = matrix(ff, [
        0 0 0  0  1  1  1  1  1  1;
        0 0 2  1  0  0  1  1  2  2;
        1 2 0  0  0  0  1  2  1  2;
        1 1 2  2  1  2  0  0  0  0     
       ]);

julia> is_discr_square(transpose(Phi)*Phi)
true

julia> # Here the frame Phi is defined in F_3^4 with a scalar product whose gram is Diag(1,1,1,2).
       gram = transpose(Phi)*diagonal_matrix([ff(1),ff(1),ff(1),ff(2)])*Phi

julia> is_discr_square(transpose(Phi)*Phi)
false
source
FrameTheory.is_equiangular — Method
is_equiangular(gram, case) -> Tuple{Bool,FqFieldElem,FqFieldElem}

Arguments

  • gram::FqMatrix: A square matrix defined over a finite field.
  • case::Symbol: :U for case U and :O for case O.

Returns

  • equiangular_bool::Bool
  • a::FqFieldElem
  • b::FqFieldElem

Determines if the matrix gram is the Gram matrix for some collection of equiangular vectors, in the provided case. Returns a boolean equiangular_bool if the provided matrix is the Gram matrix of a collection of equiangular lines. With a being the vectors common "magnitudes" and b the "angle". If equiangular_bool is false, then a and b will be nothing.

Examples

julia> ff = GF(125^2);

julia> ffx, x = ff["x"];

julia> a = roots(x^2+x+1)[1];

julia> sic = matrix(ff, [
            1    1       1    -1 -1  -1    0   0      0;
            0    0       0     1  a  a^2  -1 -1*a   -1*a^2;
           -1  -1*a^2  -1*a    0  0   0    1  a^2     a
       ]);

julia> gram = conjugate_transpose(sic)*sic;

julia> is_equiangular(gram, case=:U)
(true, 2, 1)
source
FrameTheory.is_frame_tight — Method
is_frame_tight(gram) -> Tuple{Bool,FqFieldElem}

Arguments

  • gram::FqMatrix: A square matrix defined over a finite field which is the Gram matrix for a frame.

Returns

  • tight_bool::Bool
  • c::FqFieldElem

Determines if the matrix gram is the Gram matrix for frame which is tight. Assumes gram is already known to be a frame. If so returns c being the constant such that gram^2=c*gram. If tight_bool is false, then c will be nothing.

Examples

julia> ff = GF(125^2);

julia> ffx, x = ff["x"];

julia> a = roots(x^2+x+1)[1];

julia> sic = matrix(ff, [
            1    1       1    -1 -1  -1    0   0      0;
            0    0       0     1  a  a^2  -1 -1*a   -1*a^2;
           -1  -1*a^2  -1*a    0  0   0    1  a^2     a
       ]);

julia> gram = conjugate_transpose(sic)*sic;

julia> is_frame_tight(gram)
(true, 1)
source
FrameTheory.is_ETF — Method
is_ETF(gram, case) -> Tuple{Bool,FqFieldElem,FqFieldElem,fqfieldelem}

Arguments

  • gram::FqMatrix: A square matrix defined over a finite field.
  • case::Symbol: :U for case U and :O for case O.

Returns

  • etf_bool::Bool
  • a::FqFieldElem
  • b::FqFieldElem
  • c::FqFieldElem
  • d::Int

Determines if the matrix gram is the Gram matrix for some collection of vectors which form an equiangular tight frame (ETF). Calls and returns the same parameters from is_frame, is_equiangular, and is_frame_tight.

Examples

julia> ff = GF(125^2);

julia> ffx, x = ff["x"];

julia> a = roots(x^2+x+1)[1];

julia> sic = matrix(ff, [
            1    1       1    -1 -1  -1    0   0      0;
            0    0       0     1  a  a^2  -1 -1*a   -1*a^2;
           -1  -1*a^2  -1*a    0  0   0    1  a^2     a
       ]);

julia> gram = conjugate_transpose(sic)*sic;

julia> is_ETF(gram, case=:U)
(true, 2, 1, 1, 3)

The following indicates that gram, is the Gram matrix of of a c=0 tight frame, which is not equiangular.

julia> ff = GF(3);

julia> Phi = matrix(ff, [
        0 0 0  0  1  1  1  1  1  1;
        0 0 2  1  0  0  1  1  2  2;
        1 2 0  0  0  0  1  2  1  2;
        1 1 2  2  1  2  0  0  0  0     
       ]);

julia> gram = transpose(Phi)*Phi;

julia> is_ETF(gram, case=:O)
(false, nothing, nothing, 0, 4)
source
FrameTheory.reconstruct_frame_from_gram — Function
reconstruct_frame_from_gram(gram, case) -> FqMatrix

Arguments

  • gram:FqMatrix: A square matrix defined over a finite field, which is the Gram matrix of some frame.
  • case:Symbol: :U for case U and :O for case O.

Returns

  • Phi::FqMatrix: A matrix whose columns form a frame.

Attempt to construct the corresponding frame for the Gram matrix gram. In case :O, the output Phi may live in a field extension of the field in which gram was defined in. The output will always be in the real or complex models, so the the corresponding scalar product is just the standard dot product, or conjugate dot product.

See Theorems 3.13 and 3.15 of [1]

Examples

julia> ff = GF(125^2);

julia> ffx, x = ff["x"];

julia> a = roots(x^2+x+1)[1];

julia> sic = matrix(ff, [
            1    1       1    -1 -1  -1    0   0      0;
            0    0       0     1  a  a^2  -1 -1*a   -1*a^2;
           -1  -1*a^2  -1*a    0  0   0    1  a^2     a
       ]);

julia> gram = conjugate_transpose(sic)*sic;

julia> Phi = reconstruct_frame_from_gram(gram, case=:U);

julia> is_ETF(conjugate_transpose(Phi)*Phi)
(true, 2, 1, 1, 3)

julia> Phi == sic
false

The following shows how the underlying field may change

julia> ff = GF(3);

julia> Phi = matrix(ff, [
        0 0 0  0  1  1  1  1  1  1;
        0 0 2  1  0  0  1  1  2  2;
        1 2 0  0  0  0  1  2  1  2;
        1 1 2  2  1  2  0  0  0  0     
       ]);

julia> gram = transpose(Phi)*diagonal_matrix([ff(1),ff(1),ff(1),ff(2)])*Phi;

julia> Phi = reconstruct_frame_from_gram(gram, case=:O)
(false, nothing, nothing, 0, 4)

julia> is_ETF(transpose(Phi)*Phi, case=:O)
(true, 0, 1, 0, 4)

julia> Phi.base_ring
Finite field of degree 2 and characteristic 3
source

Constructions

FrameTheory.FFCons.etf_from_triangular_graph — Function
FFCons.etf_from_triangular_graph(d, p) -> FqMatrix

Arguments

  • d:Int: positive integer.
  • p:Int: prime such that p divides d-7.

Returns

  • gram::FqMatrix: The Gram matrix of a d by (d^2-d)/2 ETF in case :O over the field of p elements.

See Theorem 5.4 of [2]

Examples

julia> gram = FFCons.etf_from_triangular_graph(12, 5);

julia> is_ETF(gram, case=:O)
(true, 3, 1, 2, 12)

julia> size(gram)
(78, 78)
source
FrameTheory.FFCons.etf_from_pmod_diff_set — Function
FFCons.etf_from_pmod_diff_set(D, n, q[; return_gram, verify_mult_gen]) -> FqMatrix

Arguments

  • D::Vector{Union{Int,BigInt}}: a p-modular difference set contained in Z/nZ
  • n::Union{Int,BigInt}: positive integer.
  • q::Union{Int,BigInt}: prime power q=p^k such that n divides q+1.
  • return_gram::Bool=true: return gram or Phi
  • verify_mult_gen::Bool=true: depending on how the underlying finite field is implemented, computing a multiplicative generator is either trivial or very very difficult. This will ensure the finite field has an easily computable multiplicative generator. If it does not this function may behave strangely.

Returns

  • gram::FqMatrix: The Gram matrix of a d=|D| by n ETF in case :U over the field of q^2 elements.

This function will not verify that D is a p-modular difference set.

See Theorem 5.7 of [1].

Examples

julia> k=2; p=3*k-1; q=p^3;

julia> D = sort([[x for x in 0:3:(9k-1)]; 1]); # sorting not needed

julia> Phi = FFCons.etf_from_pmod_diff_set(D, 9k, q, return_gram=false);

julia> gram = conjugate_transpose(Phi)*Phi;

julia> is_ETF(gram, case=:U)
(true, 2, 1, 3, 7)
source
FrameTheory.FFCons.etf_from_modular_hadamard — Function
FFCons.etf_from_modular_hadamard(modHadamard[; return_gram]) -> FqMatrix

Arguments

  • modHadamard::FqMatrix: a dxd modular Hadamard matrix defined over a quadratic extension of a finite field

such that x^2+1 does not split in the base field and d = 8 modulo the characteristic.

  • return_gram::Bool=true: return gram or Phi

Returns

  • gram::FqMatrix: The Gram matrix of a dxd^2 ETF in case U.

This function will not verify that modHadamard is a p-modular Hadamard matrix.

See Theorem 2 in [4].

Examples

julia> gram = FFCons.etf_from_modular_hadamard(matrix(GF((3^3)^2), [1 1; 1 -1]));

julia> is_ETF(gram, case=:U)
(true, 0, 1, 0, 2)
source
FrameTheory.FFCons.etf_from_singer_diff_set — Function
FFCons.etf_from_singer_diff_set(D, n, q[; return_gram, verify_mult_gen]) -> FqMatrix

Arguments

  • D::Vector{Union{Int,BigInt}}: a p-modular difference set contained in Z/nZ
  • p::Union{Int,BigInt}: prime
  • k::Union{Int,BigInt}
  • r:Union{Int,BigInt}
  • return_gram::Bool=true: return gram or Phi
  • verify_mult_gen::Bool=true: depending on how the underlying finite field is implemented, computing a multiplicative generator is either trivial or very very difficult. This will ensure the finite field has an easily computable multiplicative generator. If it does not this function may behave strangley.

See Theorem 21 of [3].

Examples

The following would construct a 13x169 ETF in case :U over the field of 64^2 elements.

julia> gram = FFCons.etf_from_singer_diff_set([0,1,5,11], 2, 6, 3);

The following would construct a 73x5329 ETF in case U over the field of (7^12)^2 elements. Due to the size, this can be slow.

julia> gram = FFCons.etf_from_singer_diff_set([0,1,17,39,41,44,48,54,62], 7, 12, 8);
source
FrameTheory.FFCons.etf_from_prime_power — Function
ExactCons.etf_from_prime_power(prime_power, q) -> FqMatrix

Arguments

  • prime_power::Int: an odd prime power
  • q::Int: an odd prime power

Returns

  • gram::FqMatrix the Gram matrix of a (prime_power+1)/2 by prime_power+1 ETF over the field Fq or F{q^2} depending on prime_power.

Examples

A case O example

julia> gram = FFCons.etf_from_prime_power(7^2,7);

julia> is_ETF(gram, case=:O)
(true, 0, 1, 0, 16)

julia> gram = FFCons.etf_from_prime_power(9,3);

julia> is_ETF(gram, case=:O)
(true, 0, 1, 0, 4)

julia> n = size(gram)[1]
10

Case U examples

julia> gram = FFCons.etf_from_prime_power(7,3);

julia> is_ETF(gram, case=:U)
(true, 1, 1, 2, 4)

julia> n = size(gram)[1]
8

julia> gram = FFCons.etf_from_prime_power(7,7);

julia> is_ETF(gram, case=:U)
(true, 0, 1, 0, 4)

julia> n = size(gram)[1]
8

julia> transpose(gram) == gram
false
source

Since many of the constructions presented rely on knowing multiplicative generators of the fields used, be provide the following function to help ensure a multiplicative generator can be easily found.

FrameTheory.FFCons.is_conway — Function
FrameTheory.FFCons.is_conway(ff) -> Bool

Arguments

  • ff::FqField: A finite field

Returns

  • uses_conway_poly::Bool: determines if the finite field was generated using a Conway polynomial.

This is very important when a multiplicative generator is desired. if ff is generated with a Conway polynomial, then gen(ff) will return a multiplicative generator of the field, otherwise gen(ff) will return a generator for the field as an algebra over its base field.

Note that this is a wrapper for the C Flint library, which is loaded by Oscar. This is not exported by FiniteFieldFrames.jl

Examples

julia> FrameTheory.FFCons.is_conway(GF(7,43))
true

julia> FrameTheory.FFCons.is_conway(GF(7,44))
false

julia> FrameTheory.FFCons.is_conway(GF(7,47))
true
source

Field extensions that do no utilize Conway polynomials do not have easily determinable multiplicative generators. This function is called by many of the above constructions, and will fail is is_conway is false.

We also provide a method of exhaustive search, presented in [2].

FrameTheory.FFCons.etf_via_compatibility_graph — Function
FFCons.etf_via_compatibility_graph(ff, d, n; case[a,]) -> FqMatrix

Arguments

  • ff:FqField: A finite field
  • d:Int: dim of vector space to search through.
  • n:Int: number of vectors to try and find.
  • case:Symbol: :U for case U and :O for case O.
  • a::Union{FqFieldElem,Int,Nothing}: only used in the case where n-d is zero, in which case a value for a can not be infered.

Returns

  • gram::FqMatrix: The Gram matrix of a d by n ETF if it exists.

This method follows Lemma 6.2 of [3]. It is possible that the resulting frame is a d' by n frame where d'<d.

Examples

julia> ff = GF(5);

julia> gram = FFCons.etf_via_compatibility_graph(ff,2,3,case=:O);

julia> is_ETF(gram, case=:O)
(true, 2, 1, 3, 2)

julia> gram = FFCons.etf_via_compatibility_graph(GF(3),4,10,case=:O,a=0);

julia> is_ETF(gram, case=:O)
(true, 0, 1, 0, 4)

julia> is_discr_square(gram)
false

A case U example

julia> gram = FFCons.etf_via_compatibility_graph(GF(5^2),3,9,case=:U);

julia> is_ETF(gram, case=:U)
(true, 2, 1, 1, 3)

A case U non-example

julia> gram = FFCons.etf_via_compatibility_graph(GF(3^2),4,6,case=:U)
0 by 0 empty matrix
source

Binder Finder

FrameTheory.binder_finder — Method
binder_finder(gram; case[, verbose]) -> Matrix{Int}

Arguments

  • gram::FqMatrix: The Gram matrix of an ETF in the provided case, such that a != 0. If a = 0 then you can specify a value for s.
  • case::Symbol: either :O or :U.
  • verbose:Bool: due to the nature of this algorithm, it can be rather slow, and so verbose will provide a few additional outputs along the way.

Returns

  • binder::Matrix{Int}: The Binder of the provided frame, where each row denotes a simplex.
binder_finder(s, gram; case) -> Matrix{Int}

Arguments

  • s:Int In this case, binder_finder will only look for regular s-simplicies.
  • gram::FqMatrix: The Gram matrix of an ETF in the provided case,
  • case::Symbol: either :O or :U.
  • verbose:Bool: due to the nature of this algorithm, it can be rather slow, and so verbose will provide a few additional outputs along the way.

Binder Finder was original implemented for numerically defined frames over R and C in [6] with Matlab. This version has been modified for finite fields, based on the results from [5].

Examples

A case where a != 0

julia> ff = GF(125^2);

julia> ffx, x = ff["x"];

julia> a = roots(x^2+x+1)[1];

julia> sic = matrix(ff, [
          1    1       1    -1 -1  -1    0   0      0;
          0    0       0     1  a  a^2  -1 -1*a   -1*a^2;
         -1  -1*a^2  -1*a    0  0   0    1  a^2     a
       ]);

julia> gram = conjugate_transpose(sic)*sic;

julia> binder_finder(gram, case=:U)
12×9 Matrix{Int64}:
 1  1  1  0  0  0  0  0  0
 1  0  0  1  0  0  1  0  0
 1  0  0  0  1  0  0  0  1
 1  0  0  0  0  1  0  1  0
 0  1  0  1  0  0  0  0  1
 0  1  0  0  1  0  0  1  0
 0  1  0  0  0  1  1  0  0
 0  0  1  1  0  0  0  1  0
 0  0  1  0  1  0  1  0  0
 0  0  1  0  0  1  0  0  1
 0  0  0  1  1  1  0  0  0
 0  0  0  0  0  0  1  1  1

In the case where a=0

julia> ff = GF(3);

julia> Phi = matrix(ff, [
          0 0 0  0  1  1  1  1  1  1;
          0 0 2  1  0  0  1  1  2  2;
          1 2 0  0  0  0  1  2  1  2;
          1 1 2  2  1  2  0  0  0  0     
       ])

julia> gram = transpose(Phi)*diagonal_matrix([ff(1),ff(1),ff(1),ff(2)])*Phi;

julia> binder_finder(3, gram, case=:O)
30×10 Matrix{Int64}:
 1  1  1  1  0  0  0  0  0  0
 1  1  0  0  1  1  0  0  0  0
 1  1  0  0  0  0  1  1  0  0
        ⋮
 0  0  0  0  1  1  1  0  0  1
 0  0  0  0  1  1  0  1  1  0
 0  0  0  0  0  0  1  1  1  1
source

Constructing Real ETFs from ETFs in Case O

FrameTheory.realize_from_case_O — Function
realize_from_case_O(gram [; try_force]) -> MatElem{CalciumFieldElem}

Arguments

  • gram::FqMatrix: The gram matrix of an ETF in case O.
  • try_force::Bool=true: if false`, will first ensure the characteristic is large enough, and fail if not.

If true, the characteristic will not be checked before hand and instead the resulting matrix will be checked to see if it the Gram matrix of an ETF, and will fail if not.

Returns

  • realized_gram::MatElem{CalciumFieldElem}: The realized ETF

This function utilizes Proposition 3.3 from [2].

Examples

An example with large characteristic

julia> gram = FFCons.etf_from_prime_power(7^2,97);

julia> realized_gram = realize_from_case_O(gram, try_force=false);

julia> is_ETF(realized_gram)
(true, 7, 1, 14, 25)

An example where the characteristic is not checked

julia> gram = FFCons.etf_from_prime_power(7^2,29);

julia> realized_gram = realize_from_case_O(gram, try_force=true);

julia> is_ETF(realized_gram)
(true, 7, 1, 14, 25)
source