# 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)[source]#

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

>>> from sage.all import *
>>> from sage.combinat.t_sequences import turyn_sequences_smallcases, T_sequences_construction_from_base_sequences
>>> seqs = turyn_sequences_smallcases(Integer(4))
>>> 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)[source]#

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

>>> from sage.all import *
>>> from sage.combinat.t_sequences import turyn_sequences_smallcases, T_sequences_construction_from_turyn_sequences, is_T_sequences_set
>>> seqs = turyn_sequences_smallcases(Integer(4))
>>> 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)[source]#

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

>>> from sage.all import *
>>> from sage.combinat.t_sequences import T_sequences_smallcases, is_T_sequences_set
>>> T_sequences_smallcases(Integer(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

>>> from sage.all import *
>>> T_sequences_smallcases(Integer(9), existence=True)
True

sage.combinat.t_sequences.base_sequences_construction(turyn_type_seqs, check=True)[source]#

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

>>> from sage.all import *
>>> from sage.combinat.t_sequences import base_sequences_construction
>>> X = [Integer(1),Integer(1),-Integer(1),Integer(1),-Integer(1),Integer(1),-Integer(1),Integer(1)]
>>> Y = [Integer(1),-Integer(1),-Integer(1),-Integer(1),-Integer(1),-Integer(1),-Integer(1),Integer(1)]
>>> Z = [Integer(1),-Integer(1),-Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),-Integer(1)]
>>> W = [Integer(1),Integer(1),Integer(1),-Integer(1),Integer(1),Integer(1),-Integer(1)]
>>> 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]]

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

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

>>> from sage.all import *
>>> from sage.combinat.t_sequences import base_sequences_smallcases
>>> base_sequences_smallcases(Integer(8), Integer(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

>>> from sage.all import *
>>> base_sequences_smallcases(Integer(8), Integer(7), existence=True)
True
>>> base_sequences_smallcases(Integer(7), Integer(5), existence=True)
False

sage.combinat.t_sequences.is_T_sequences_set(sequences, verbose=False)[source]#

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

>>> from sage.all import *
>>> from sage.combinat.t_sequences import is_T_sequences_set
>>> seqs = [[Integer(1), Integer(1), Integer(0), Integer(0), Integer(0)], [Integer(0), Integer(0), Integer(1), Integer(0), Integer(0)], [Integer(0), Integer(0), Integer(0), Integer(1), -Integer(1)], [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)]]
>>> is_T_sequences_set(seqs)
True
>>> seqs = [[Integer(1), Integer(1), Integer(0), Integer(1), Integer(0)], [Integer(0), Integer(0), Integer(1), Integer(0), Integer(0)], [Integer(0), Integer(0), Integer(0), Integer(1), -Integer(1)], [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)]]
>>> 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)[source]#

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

>>> from sage.all import *
>>> from sage.combinat.t_sequences import is_base_sequences_tuple
>>> seqs = [[Integer(1), -Integer(1), -Integer(1), Integer(1), Integer(1), Integer(1), Integer(1), -Integer(1), Integer(1), Integer(1), Integer(1), -Integer(1), Integer(1), Integer(1), -Integer(1)],[Integer(1), -Integer(1), -Integer(1), Integer(1), Integer(1), Integer(1), Integer(1), -Integer(1), -Integer(1), -Integer(1), -Integer(1), Integer(1), -Integer(1), -Integer(1), Integer(1)],[Integer(1), Integer(1), -Integer(1), Integer(1), -Integer(1), Integer(1), -Integer(1), Integer(1)],[Integer(1), -Integer(1), -Integer(1), -Integer(1), -Integer(1), -Integer(1), -Integer(1), Integer(1)]]
>>> 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

>>> from sage.all import *
>>> seqs = [[Integer(1), -Integer(1)], [Integer(1), Integer(1)], [-Integer(1)], [Integer(2)]]
>>> is_base_sequences_tuple(seqs, verbose=True)
Base sequences should only contiain -1, +1, found 2
False

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

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

>>> from sage.all import *
>>> from sage.combinat.t_sequences import is_skew
>>> is_skew([Integer(1), -Integer(1), Integer(1), -Integer(1), Integer(1), -Integer(1)])
True
>>> is_skew([Integer(1), -Integer(1), -Integer(1), -Integer(1)], verbose=True)
Constraint not satisfied at index 1
False

sage.combinat.t_sequences.is_symmetric(seq, verbose=False)[source]#

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

>>> from sage.all import *
>>> from sage.combinat.t_sequences import is_symmetric
>>> is_symmetric([Integer(1), -Integer(1), Integer(1), -Integer(1), Integer(1)])
True
>>> is_symmetric([Integer(1), -Integer(1), Integer(1), Integer(1), Integer(1)], verbose=True)
Constraint not satisfied at index 1
False

sage.combinat.t_sequences.turyn_sequences_smallcases(l, existence=False)[source]#

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

>>> from sage.all import *
>>> from sage.combinat.t_sequences import turyn_sequences_smallcases
>>> turyn_sequences_smallcases(Integer(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

>>> from sage.all import *
>>> turyn_sequences_smallcases(Integer(4), existence=True)
True

sage.combinat.t_sequences.turyn_type_sequences_smallcases(n, existence=False)[source]#

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

>>> from sage.all import *
>>> from sage.combinat.t_sequences import turyn_type_sequences_smallcases
>>> turyn_type_sequences_smallcases(Integer(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

>>> from sage.all import *
>>> turyn_type_sequences_smallcases(Integer(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]).