T-sequences#

T-sequences are tuples of four (-1, 0, 1) sequences of length \(t\) where for every \(i\) exactly one sequence has a nonzero entry at index \(i\) and for which the nonperiodic autocorrelation function is equal to zero (i.e. they are complementary). See Definition 7.5 of [Seb2017].

These can be constructed from Turyn sequences. In particular, if Turyn sequences of length \(l\) exists, there will be T-sequences of length \(4l-1\) and \(2l-1\).

Turyn sequences are tuples of four (-1, +1) sequences \(X, U, Y, V\) of length \(l\), \(l\), \(l-1\), \(l-1\) with nonperiodic autocorrelation equal to zero and the additional constraints that:

  • the first element of \(X\) is 1

  • the last element of \(X\) is -1

  • the last element of \(U\) is 1

The nonperiodic autocorrelation of a familiy of sequences \(X=\{A_1, A_2, ..., A_n\}\) is defined as (see Definition 7.2 of [Seb2017]):

\[N_X(j) = \sum_{i=1}^{n-j}(a_{1,i}a_{1,i+j} + a_{2,i}a_{2,i+j} + ... + a_{n,i}a_{n,i+j})\]

AUTHORS:

  • Matteo Cati (2022-11-16): initial version

sage.combinat.t_sequences.T_sequences_construction_from_base_sequences(base_sequences, check=True)#

Construct T-sequences of length \(2n+p\) from base sequences of length \(n+p, n+p, n, n\).

Given base sequences \(A, B, C, D\), the T-sequences are constructed as described in [KTR2005]:

\[\begin{split}\begin{aligned} T_1 &= \frac{1}{2}(A+B); 0_{n} \\ T_2 &= \frac{1}{2}(A-B); 0_{n} \\ T_3 &= 0_{n+p} + \frac{1}{2}(C+D) \\ T_4 &= 0_{n+p} + \frac{1}{2}(C-D) \end{aligned}\end{split}\]

INPUT:

  • base_sequences – the base sequences that should be used to construct the T-sequences.

  • check – boolean, if true (default) checks that the sequences created are T-sequences before returning them.

EXAMPLES:

sage: from sage.combinat.t_sequences import turyn_sequences_smallcases, T_sequences_construction_from_base_sequences
sage: seqs = turyn_sequences_smallcases(4)
sage: T_sequences_construction_from_base_sequences(seqs)
[[1, 1, -1, 0, 0, 0, 0],
[0, 0, 0, -1, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 1],
[0, 0, 0, 0, 0, 1, 0]]
sage.combinat.t_sequences.T_sequences_construction_from_turyn_sequences(turyn_sequences, check=True)#

Construct T-sequences of length \(4l-1\) from Turyn sequences of length \(l\).

Given Turyn sequences \(X, U, Y, V\), the T-sequences are constructed as described in theorem 7.7 of [Seb2017]:

\[\begin{split}\begin{aligned} T_1 &= 1; 0_{4l-2} \\ T_2 &= 0; X/Y; 0_{2l-1} \\ T_3 &= 0_{2l}; U/0_{l-2} \\ T_4 &= 0_{2l} + 0_{l}/V \end{aligned}\end{split}\]

INPUT:

  • turyn_sequences – the Turyn sequences that should be used to construct the T-sequences .

  • check – boolean, if true (default) checks that the sequences created are T-sequences before returning them.

EXAMPLES:

sage: from sage.combinat.t_sequences import turyn_sequences_smallcases, T_sequences_construction_from_turyn_sequences, is_T_sequences_set
sage: seqs = turyn_sequences_smallcases(4)
sage: T_sequences_construction_from_turyn_sequences(seqs)
[[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, -1, 1, -1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, -1, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 1, 0]]
sage.combinat.t_sequences.T_sequences_smallcases(t, existence=False, check=True)#

Construct T-sequences for some small values of \(t\).

This method will try to use the constructions defined in T_sequences_construction_from_base_sequences() and T_sequences_construction_from_turyn_sequences() together with the Turyn sequences stored in turyn_sequences_smallcases(), or base sequences created by base_sequences_smallcases().

This function contains also some T-sequences taken directly from [CRSKKY1989].

INPUT:

  • t – integer, the length of the T-sequences to construct.

  • existence – boolean (default false). If true, this method only returns whether a T-sequences of the given size can be constructed.

  • check – boolean, if true (default) check that the sequences are T-sequences before returning them.

EXAMPLES:

By default, this method returns the four T-sequences

sage: from sage.combinat.t_sequences import T_sequences_smallcases, is_T_sequences_set
sage: T_sequences_smallcases(9)
[[1, 1, 0, 1, 0, 0, 0, 0, 0],
[0, 0, -1, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0, -1],
[0, 0, 0, 0, 0, 0, 1, -1, 0]]

If the existence flag is passed, the method returns a boolean

sage: T_sequences_smallcases(9, existence=True)
True
sage.combinat.t_sequences.base_sequences_construction(turyn_type_seqs, check=True)#

Construct base sequences of length \(2n-1, 2n-1, n, n\) from Turyn type sequences of length \(n,n,n,n-1\).

Given Turyn type sequences \(X, Y, Z, W\) of length \(n,n,n,n-1\), Theorem 1 of [KTR2005] shows that the following are base sequences of length \(2n-1, 2n-1, n, n\):

\[\begin{split}\begin{aligned} A &= Z;W \\ B &= Z; -W \\ C &= X \\ D &= Y \end{aligned}\end{split}\]

INPUT:

  • turyn_type_seqs – The list of 4 Turyn type sequences that should be used to construct the base sequences.

  • check – boolean, if True (default) check that the resulting sequences are base sequences before returning them.

OUTPUT: A list containing the four base sequences.

EXAMPLES:

sage: from sage.combinat.t_sequences import base_sequences_construction
sage: X = [1,1,-1,1,-1,1,-1,1]
sage: Y = [1,-1,-1,-1,-1,-1,-1,1]
sage: Z = [1,-1,-1,1,1,1,1,-1]
sage: W = [1,1,1,-1,1,1,-1]
sage: base_sequences_construction([X, Y, Z, W])
[[1, -1, -1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1],
[1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1, 1, -1, -1, 1],
[1, 1, -1, 1, -1, 1, -1, 1],
[1, -1, -1, -1, -1, -1, -1, 1]]

See also

is_base_sequences_tuple()

sage.combinat.t_sequences.base_sequences_smallcases(n, p, existence=False, check=True)#

Construct base sequences of length \(n+p, n+p, n, n\) from available data.

The function uses the construction base_sequences_construction(), together with Turyn type sequences from turyn_type_sequences_smallcases() to construct base sequences with \(p = n-1\).

Furthermore, this function uses also Turyn sequences (i.e. base sequences with \(p=1\)) from turyn_sequences_smallcases().

INPUT:

  • n – integer, the length of the last two base sequences.

  • p – integer, \(n+p\) will be the length of the first two base sequences.

  • existence – boolean (default False). If True, the function will only check whether the base sequences can be constructed.

  • check – boolean, if True (default) check that the resulting sequences are base sequences before returning them.

OUTPUT:

If existence is False, the function returns a list containing the four base sequences, or raises an error if the base sequences cannot be constructed. If existence is True, the function returns a boolean, which is True if the base sequences can be constructed and False otherwise.

EXAMPLES:

sage: from sage.combinat.t_sequences import base_sequences_smallcases
sage: base_sequences_smallcases(8, 7)
[[1, -1, -1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1],
[1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1, 1, -1, -1, 1],
[1, 1, -1, 1, -1, 1, -1, 1],
[1, -1, -1, -1, -1, -1, -1, 1]]

If existence is True, the function returns a boolean

sage: base_sequences_smallcases(8, 7, existence=True)
True
sage: base_sequences_smallcases(7, 5, existence=True)
False
sage.combinat.t_sequences.is_T_sequences_set(sequences, verbose=False)#

Check if a family of sequences is composed of T-sequences.

Given 4 (-1, 0, +1) sequences, they will be T-sequences if (Definition 7.4 of [Seb2017]):

  • they have all the same length \(t\)

  • for each index \(i\), exactly one sequence is nonzero at \(i\)

  • the nonperiodic autocorrelation is equal to \(0\)

INPUT:

  • sequences – a list of four sequences.

  • verbose – a boolean (default false). If true the function will be verbose when the sequences do not satisfy the contraints.

EXAMPLES:

sage: from sage.combinat.t_sequences import is_T_sequences_set
sage: seqs = [[1, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, -1], [0, 0, 0, 0, 0]]
sage: is_T_sequences_set(seqs)
True
sage: seqs = [[1, 1, 0, 1, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, -1], [0, 0, 0, 0, 0]]
sage: is_T_sequences_set(seqs, verbose=True)
There should  be exactly a nonzero element at every index, found 2 such elemnents at index 3
False
sage.combinat.t_sequences.is_base_sequences_tuple(base_sequences, verbose=False)#

Check if the given sequences are base sequences.

Four (-1, +1) sequences \(A, B, C, D\) of length \(n+p, n+p, n, n\) are called base sequences if for all \(j \ge 1\):

\[N_A(j)+N_B(j)+N_C(j)+N_D(j) = 0\]

where \(N_X(j)\) is the nonperiodic autocorrelation (See definition in [KTR2005]).

INPUT:

  • base_sequences – The list of 4 sequences that should be checked.

  • verbose – a boolean (default false). If true the function will be verbose when the sequences do not satisfy the contraints.

EXAMPLES:

sage: from sage.combinat.t_sequences import is_base_sequences_tuple
sage: seqs = [[1, -1, -1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1],[1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1, 1, -1, -1, 1],[1, 1, -1, 1, -1, 1, -1, 1],[1, -1, -1, -1, -1, -1, -1, 1]]
sage: is_base_sequences_tuple(seqs)
True

If verbose is true, the function will be verbose

sage: seqs = [[1, -1], [1, 1], [-1], [2]]
sage: is_base_sequences_tuple(seqs, verbose=True)
Base sequences should only contiain -1, +1, found 2
False

See also

base_sequences_construction()

sage.combinat.t_sequences.is_skew(seq, verbose=False)#

Check if the given sequence is skew.

A sequence \(X=\{x_1, x_2, ...,x_n\}\) is defined skew (according to Definition 7.4 of [Seb2017]) if \(n\) is even and \(x_i = -x_{n-i+1}\).

INPUT:

  • seq – the sequence that should be checked.

  • verbose – a boolean (default false). If true the function will be verbose when the sequences do not satisfy the contraints.

EXAMPLES:

sage: from sage.combinat.t_sequences import is_skew
sage: is_skew([1, -1, 1, -1, 1, -1])
True
sage: is_skew([1, -1, -1, -1], verbose=True)
Constraint not satisfied at index 1
False
sage.combinat.t_sequences.is_symmetric(seq, verbose=False)#

Check if the given sequence is symmetric.

A sequence \(X=\{x_1, x_2, ...,x_n\}\) is defined symmetric (according to Definition 7.4 of [Seb2017]) if \(n\) is odd and \(x_i = x_{n-i+1}\).

INPUT:

  • seq – the sequence that should be checked.

  • verbose – a boolean (default false). If true the function will be verbose when the sequences do not satisfy the contraints.

EXAMPLES:

sage: from sage.combinat.t_sequences import is_symmetric
sage: is_symmetric([1, -1, 1, -1, 1])
True
sage: is_symmetric([1, -1, 1, 1, 1], verbose=True)
Constraint not satisfied at index 1
False
sage.combinat.t_sequences.turyn_sequences_smallcases(l, existence=False)#

Construction of Turyn sequences for small values of \(l\).

The data is taken from [Seb2017] and [CRSKKY1989].

INPUT:

  • l – integer, the length of the Turyn sequences.

  • existence – boolean (default False). If true, only return whether the Turyn sequences are available for the given length.

EXAMPLES:

By default, this method returns the four Turyn sequences

sage: from sage.combinat.t_sequences import turyn_sequences_smallcases
sage: turyn_sequences_smallcases(4)
[[1, 1, -1, -1], [1, 1, -1, 1], [1, 1, 1], [1, -1, 1]]

If we pass the existence flag, the method will return a boolean

sage: turyn_sequences_smallcases(4, existence=True)
True
sage.combinat.t_sequences.turyn_type_sequences_smallcases(n, existence=False)#

Construction of Turyn type sequences for small values of \(n\).

The data is taken from [KTR2005] for \(n= 36\), and from [BDKR2013] for \(n\le 32\).

INPUT:

  • n – integer, the length of the Turyn type sequences.

  • existence – boolean (default False). If true, only return whether the Turyn type sequences are available for the given length.

EXAMPLES:

By default, this method returns the four Turyn type sequences

sage: from sage.combinat.t_sequences import turyn_type_sequences_smallcases
sage: turyn_type_sequences_smallcases(4)
[[1, 1, 1, 1], [1, 1, -1, 1], [1, 1, -1, -1], [1, -1, 1]]

If we pass the existence flag, the method will return a boolean

sage: turyn_type_sequences_smallcases(4, existence=True)
True

ALGORITHM:

The Turyn type sequences are stored in hexadecimal format. Given \(n\) hexadecimal digits \(h_1, h_2,...,h_n\), it is possible to get the Turyn type sequences by converting each \(h_i\) (\(1 \le i \le n-1\)) into a four digits binary number. Then, the j-th binary digit is \(0\) if the i-th number in the j-th sequence is \(1\), and it is \(1\) if the number in the sequence is -1.

For the n-th digit, it should be converted to a 3 digits binary number, and then the same mapping as before can be used (see also [BDKR2013]).