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.

Instructions for Case U

Case U requires the 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 reccommended 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");

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

hessa_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
]);
hessa_gram = conjugate_transpose(hessa_sic)*hessa_sic;

binder_finder(hessa_gram, case=:U)

Instructions for Case O

Case O requires the the underlying field be of odd degree. 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 = case_O_frame_discr_is_square(gram);  # false

binder_finder(3, gram, case=:O)

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.case_O_frame_discr_is_square — Function

case_O_frame_discr_is_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

For a Gram of a frame is Case O, this determines if the frame lives in a space whose discriminant 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> case_O_frame_discr_is_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> case_O_frame_discr_is_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 'magnatudes' 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> hessa_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> hessa_gram = conjugate_transpose(hessa_sic)*hessa_sic;

julia> is_equiangular(hessa_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. 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> hessa_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> hessa_gram = conjugate_transpose(hessa_sic)*hessa_sic;

julia> is_frame_tight(hessa_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> hessa_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> hessa_gram = conjugate_transpose(hessa_sic)*hessa_sic;

julia> is_ETF(hessa_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 Theorem 3.13 and 3.15 of https://arxiv.org/pdf/2012.12977

Examples

julia> ff = GF(125^2);

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

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

julia> hessa_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> hessa_gram = conjugate_transpose(hessa_sic)*hessa_sic;

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

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

julia> Phi == hessa_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=false: 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 strangly.

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=false: 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 strangly.

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_conf_mat — Function

FFCons.etf_from_conf_mat(q, conf_mat) -> FqMatrix

Arguments

q::Int: prime power
conf_mat::Matrix{Int}: An nxn conference matrix, possibly skew

Returns

gram::FqMatrix: The Gram matrix of a (n/2)xn ETF over the field of q^2 elements, in case U, if the conference matrix was skew, and over the field of q elements in case O otherwise.

source

Since many of these cosntructions rely on multiplictive generators, there is teh 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

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.

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> hessa_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> hessa_gram = conjugate_transpose(hessa_sic)*hessa_sic;

julia> binder_finder(hessa_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