On the maximum order complexity ofsubsequences of the Thue-Morse andRudin-Shapiro sequence along squares
Arne Winterhof
Austrian Academy of Sciences
Johann Radon Institute for Computational and Applied Mathematics
Linz

UDT, Luminy, Oct. 2, 2018

A.Winterhof (RICAM)

max-order complexity

UDT, Luminy, Oct. 2, 2018

0 / 19

How do we measure the suitability of a binary sequence forcryptography?

A.Winterhof (RICAM)

max-order complexity

UDT, Luminy, Oct. 2, 20181 / 19

How do we measure the suitability of a binary sequence forcryptography?
How do we detect ’bad’ cryptographic sequences?
How do we find ’good’ cryptographic sequences?

A.Winterhof (RICAM)

max-order complexity

UDT, Luminy, Oct. 2, 20181 / 19

How do we measure the suitability of a binary
sequence for cryptography?
Study several quality measures:
linear complexity
maximum order complexity
correlation measure
Gowers norm
expansion complexity...

A.Winterhof (RICAM)

max-order complexity

UDT, Luminy, Oct. 2, 20182 / 19Studied sequences

Thue-Morse sequence (Rudin-Shapiro sequence)pattern sequences(non-periodic) automatic sequences
subsequence of Thue-Morse along the squares
Legendre sequence (with polynomials)...

A.Winterhof (RICAM)

max-order complexity

UDT, Luminy, Oct. 2, 20183 / 19

Linear Complexity
For a positive integer N the Nth linear complexity L(sn , N) of asequence (sn ) over F2 is the smallest positive integer L such that
there are constants c0 , . . . , cL−1 ∈ F satisfying
sn+L = cL−1 sn+L−1 + . . . + c0 sn ,0 ≤ n ≤ N − L − 1.

A.Winterhof (RICAM)

max-order complexity

UDT, Luminy, Oct. 2, 20184 / 19Linear Complexity
For a positive integer N the Nth linear complexity L(sn , N) of asequence (sn ) over F2 is the smallest positive integer L such that
there are constants c0 , . . . , cL−1 ∈ F satisfying
sn+L = cL−1 sn+L−1 + . . . + c0 sn ,0 ≤ n ≤ N − L − 1.
small linear complexity implies predictability and thus
unsuitability in cryptography
there are predictable sequences with large linear complexity
we need further measures for the unpredictability of a sequence

A.Winterhof (RICAM)

max-order complexity

UDT, Luminy, Oct. 2, 20184 / 19Automatic sequences:high linear complexity
still predictable

A.Winterhof (RICAM)

max-order complexity

UDT, Luminy, Oct. 2, 2018

5 / 19

2-automatic sequences
Thue-Morse sequence s0 = 0, s2n+1 = sn + 1, s2n = sn , n = 0, 1, . . .
Input n = (n0 n1 . . . nj )2

Output:0, 1
0110100110010110 . . .

n = 5 = (101)2

Rudin-Shapiro

0001001000011101 . . .
A.Winterhof (RICAM)

max-order complexity

UDT, Luminy, Oct. 2, 20186 / 19Christol’s theoremgenerating function G (x) of (sn ):G (x) =∞X

sn x nn=0(sn ) is 2-automatic over F2 if and only if G (x) is algebraic over F2 [x].
Example. Thue-Morse sequence(x + 1)3 G (x)2 + (x + 1)2 G (x) + x = 0
G (x) rational if and only if (sn ) is ultimately periodic.

A.Winterhof (RICAM)

max-order complexity

UDT, Luminy, Oct. 2, 20187 / 19

Linear complexity of Thue-Morse sequenceMérai/W., 2018:
tn+L =L−1Xc` tn+` = 0,0≤n ≤N −1−L`=0f (x) =LXc` x L−n ,cL = 1

n=0

g (x) := f (x)G (x) mod x Ndeg(g ) < L, deg(f ) ≤ L(x + 1)3 g (x)2 + (x + 1)2 f (x)g (x) + xf (x)2 = k(x)x N ,L(tn , N) ≥A.Winterhof (RICAM)

k(x) 6= 0

N −1
2

max-order complexity

UDT, Luminy, Oct. 2, 20188 / 19

A different method gives L(tn , N) = 2b(N + 2)/4c.
The method works for any (non-periodic) automatic sequence (ifwe know h 6= 0 with h(x, G (x)) = 0).
What measure(s) can be used to see that the Thue-Morsesequence (other automatic sequences) is (are) predictable?
What can we say about (non-automatic) subsequences ofautomatic sequences?
Are there any sequences with good results under all commonlyused measures of pseudorandomness?

A.Winterhof (RICAM)

max-order complexity

UDT, Luminy, Oct. 2, 2018

9 / 19Correlation measure of order k
Mauduit/Sárközy, 1997:−1
The correlation measure of order k of a binary sequence (sn )Tn=0of
length T is introduced as
Ck (sn ) = maxM,DM
X(−1)sn+d1 · · · (−1)sn+dk ,k ≥ 1,n=1

where the maximum is taken over all D = (d1 , d2 , . . . , dk ) with
non-negative integers d1 < d2 < · · · < dk and M such thatM − 1 + dk ≤ T − 1.

A.Winterhof (RICAM)

max-order complexity

UDT, Luminy, Oct. 2, 201810 / 19

Correlation measure of order k
Mauduit/Sárközy, 1997:−1The correlation measure of order k of a binary sequence (sn )Tn=0oflength T is introduced as
Ck (sn ) = max
M,DMX(−1)sn+d1 · · · (−1)sn+dk ,k ≥ 1,n=1

where the maximum is taken over all D = (d1 , d2 , . . . , dk ) with
non-negative integers d1 < d2 < · · · < dk and M such thatM − 1 + dk ≤ T − 1.
Mauduit/Sárközy, 1998: C2 (tn ) ≥ N/12, N ≥ 5
Mérai/W. 2018: lower bounds on C2 (sn ) for any automatic sequence.

A.Winterhof (RICAM)

max-order complexity

UDT, Luminy, Oct. 2, 201810 / 19Relation between linear complexity and correlation
measureBrandstätter/W., 2006:L(sn , N) ≥ N −A.Winterhof (RICAM)

max
1≤k≤L(sn ,N)+1

Ck (sn ),max-order complexity

2 ≤ N ≤ T − 1.

UDT, Luminy, Oct. 2, 201811 / 19

Example: Legendre sequence
Let p > 2 be a prime. The Legendre-sequence (`n ) is defined by (n= −1,1,p`n =n ≥ 0,0, otherwise, 
where p. is the Legendre-symbol.

A.Winterhof (RICAM)

max-order complexity

UDT, Luminy, Oct. 2, 201812 / 19

Example: Legendre sequence
Let p > 2 be a prime. The Legendre-sequence (`n ) is defined by (n= −1,1,p`n =n ≥ 0,0, otherwise, 
where p. is the Legendre-symbol.
The Nth linear complexity of the Legendre sequence satisfies
L(`n , N) A.Winterhof (RICAM)

min{N, p},p 1/2 log p

max-order complexity

N ≥ 1.

UDT, Luminy, Oct. 2, 201812 / 19L(sn , N) ≥ N −max1≤k≤L(sn ,N)+12 ≤ N ≤ T − 1.

Ck (sn ),Mauduit/Sárközy, 1997:Ck (`n )  kp 1/2 log pL(`n , N) A.Winterhof (RICAM)

min{N, p},p 1/2 log p

max-order complexity

N ≥ 1.

UDT, Luminy, Oct. 2, 201813 / 19

Maximum order complexity

Maximum order complexity: Smallest M = M(sn , N) withsn+M = f (sn+M−1 , . . . , sn ),0 ≤ n ≤ N − M − 1.

finer than linear complexity
much more complicated to calculate

A.Winterhof (RICAM)

max-order complexity

UDT, Luminy, Oct. 2, 201814 / 19

Maximum order complexity vs. correlation measure
Isik, W., 2017: For any binary sequence (sn ) we haveM(sn , N) ≥ N − 2M(sn ,N)+1A.Winterhof (RICAM)max
1≤k≤M(sn ,N)+1

max-order complexity

Ck (sn , N),N ≥ 1.

UDT, Luminy, Oct. 2, 201815 / 19

Maximum order complexity vs. correlation measure
Isik, W., 2017: For any binary sequence (sn ) we haveM(sn , N) ≥ N − 2M(sn ,N)+1max
1≤k≤M(sn ,N)+1

Ck (sn , N),N ≥ 1.

Example. Legendre sequence
Ck (`n )  kp 1/2 log pM(`n , N) ≥ log(min{N, p}/p 1/2 ) + O(log log p)
typical: M(sn , N) ≈ log N, Ck (sn ) ≈ N 1/2 logc(k) N

A.Winterhof (RICAM)

max-order complexity

UDT, Luminy, Oct. 2, 201815 / 19

Maximum-order complexity of Thue-Morsesequence
Sun/W., submitted: M(tn ) ≥ N/5
Thue-Morse sequence is predictable since C2 (tn ) is large.
still M(tn ) is very large

A.Winterhof (RICAM)

max-order complexity

UDT, Luminy, Oct. 2, 201816 / 19

Maximum-order complexity of Thue-Morsesequence
Sun/W., submitted: M(tn ) ≥ N/5
Thue-Morse sequence is predictable since C2 (tn ) is large.
still M(tn ) is very large
Do certain subsequences of the Thue-Morse sequence inherit alarge maximum order complexity?
For example, the Thue-Morse sequence along the squares is not
automatic and normal (Drmota/Mauduit/Rivat).

A.Winterhof (RICAM)

max-order complexity

UDT, Luminy, Oct. 2, 201816 / 19

Thue-Morse sequence along squares
sn = tn2 , n = 0, 1, . . .
Sun/W., submitted: M(sn )  N 1/2
Idea of proof: 5 · 2` < N ≤ 5 · 2`+1Verifyt(i+2`+1 )2 = t(i+2`+2 )2 ,i = 0, 1, . . . ,kjp
2`+2 − 1andt(2` +2`+1 )2 6= t(2` +2`+2 )2 .
j√kAssume M ≤2`+2 − 1 + 1 such thatt(i+M)2 = f (ti 2 , . . . , t(i+M−1)2 ),i = 0, 1, . . . , N − M − 1

we get a contradiction.
A.Winterhof (RICAM)

max-order complexity

UDT, Luminy, Oct. 2, 201817 / 19

A generalization
The pattern sequences Pk = (pn )∞n=0 is defined bypn ≡ sk (n) mod 2,
where Pk = 11 . . . 1 ∈ Fk2 is the all 1 pattern of length k and sk (n) is
the number of occurrences of Pk in the binary representation of n.
k = 1: Thue-Morse sequencek = 2: Rudin-Shapiro sequence
0M(Pk , N)  N 1/2 ,A.Winterhof (RICAM)N ≥ 22k+2 .

max-order complexity

UDT, Luminy, Oct. 2, 201818 / 19

Thank you for your attention!

A.Winterhof (RICAM)

max-order complexity

UDT, Luminy, Oct. 2, 201819 / 19