Daniele Bartoli
email: dbartoli@cage.ugent.be

Leo Storme

The second and the third smallest arrangements of hyperplanes in finite projective spaces

Keywords:

In this paper we determine the second and the third smallest configuration of hyperplanes in PG(N, q). We present links with the unique extendability of arcs in PG(2, q), and with (k, 3)-arcs having a unique trisecant. These results have links to the study of weights of the d-th order q-ary projective Reed-Muller codes PRM(q, d, N ).

Introduction

In recent years, the distribution of the weights of the d-th order q-ary projective Reed-Muller codes PRM(q, d, N ) and of the affine Reed-Muller codes RM(q, d, N ) has received the attention of different authors [START_REF] Bartoli | Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes[END_REF][START_REF] Geil | On the second weight of generalized Reed-Muller codes[END_REF][START_REF] Rodier | Les Arrangements Minimaux et Maximaux d'Hyperplans dans P n (Fq)[END_REF][START_REF] Rolland | The second weight of generalized Reed-Muller codes in most cases[END_REF][START_REF] Sboui | Second highest number of points of hypersurfaces in F n q[END_REF][START_REF] Sboui | Special numbers of rational points on hypersurfaces in the n-dimensional projective space over a finite field[END_REF].

In particular, Serre determined the smallest weight of the projective Reed-Muller code PRM(q, d, N ), for d ≤ q -1. One of the interesting facts about these results is that they are equivalent to results on the maximal number of points in the projective space PG(N, q), of dimension N over the finite field F q of order q, on the algebraic hypersurfaces of degree d. For instance, the result of Serre geometrically shows that the largest algebraic hypersurfaces of degree d ≤ q -1 in PG(N, q) are equal to a union of d hyperplanes passing through a common (N -2)-space of PG(N, q) [START_REF] Serre | Lettre à M. Tsfasman du 24 Juillet 1989[END_REF]. The number of points in this configuration

A d 1 (N ) is dq N -1 + θ N -2 , (1)
with θ N -2 = q N -2 + q N -3 + • • • + q + 1. This inspired Sboui to determine the second smallest and the third smallest weight of the code PRM(q, d, N ), for 7 < d < q. This led to the investigation of the second largest and third largest configuration of hyperplanes in PG(N, q). In particular he proved that the second weight of the code PRM(q, d, N ) is defined by the algebraic hypersurfaces A d 2 (N ) of degree d which are the union of d hyperplanes, d -1 of which meet in a common subspace of dimension N -2 and with the d-th hyperplane not passing through this common subspace of dimension N -2. The number of points in this configuration is

dq N -1 + θ N -2 -(d -2)q N -2 . (2)
Also, the third weight of the code PRM(q, d, N ), with 7 < d < q, is defined by the algebraic hypersurfaces A d 3 (N ) of degree d which are the union of d hyperplanes, d -2 of which meet in a common subspace K 1 of dimension N -2, and where the last two hyperplanes H d-1 and H d meet in a subspace K 2 , different from K 1 , such that K 2 is contained in exactly one of the d-2 hyperplanes passing through K 1 . The number of points in this configuration

A d 3 (N ) is dq N -1 + θ N -2 -2(d -3)q N -2 . ( 3
)
All the other configurations different from

A d 1 (N ) and A d 2 (N ) are smaller in size than A d 3 (N ) if d > 7.
Sboui also determined the smallest configuration of d hyperplanes in PG(N, q), d < q, to compare the weights of the codewords of PRM(q, d, N ) arising from algebraic hypersurfaces of degree d consisting of d hyperplanes to the weights of the codewords arising from algebraic hypersurfaces not equal to the union of hyperplanes of PG(N, q). This configuration is described in the following way: for every 1 ≤ i, j ≤ d, i = j, we have H i ∩ H j = K i j , where the spaces K i j are d 2 subspaces of dimension N -2, all distinct and meeting in a common subspace Ω of dimension N -3. Equivalently, H 1 , . . . , H d share exactly an (N -3)-space Ω and intersect a fixed plane disjoint from Ω in d lines no three of which pass through the same point (that is they form a dual d-arc in the quotient geometry of Ω).

The consequence of this result for the codes PRM(q, d, N ) is the following: the weight w l m given by the minimal hyperplane arrangement is the highest weight of a codeword in PRM(q, d, N ) which can be given by any hyperplane arrangement. Moreover, for q > d(d -1)/2, any algebraic hypersurface of degree d in PG(N, q) containing an absolutely irreducible non-linear factor cannot correspond to a codeword with weight less than w l m , see [START_REF] Rodier | Les Arrangements Minimaux et Maximaux d'Hyperplans dans P n (Fq)[END_REF]. In particular, for d small enough with respect to q, all the configurations of d hyperplanes give weights in PRM(q, d, N ) smaller than the weights corresponding to the hypersurfaces of degree d containing non-linear factors. Therefore, the study of possible configurations of hyperplanes and their number of points is interesting in order to have more information on the codewords of PRM(q, d, N ) having weights close to the minimum distance δ. Unfortunately, due to the complexity of the problem, this investigation is possible only either for the largest configurations of hyperplanes or for the smallest ones.

We continue this study by determining the second and the third smallest configuration of hyperplanes in PG(N, q). Here, we see that links with the unique extendability of arcs (i.e. set of points no three of which are collinear) in PG(2, q), and with (k, 3)-arcs (i.e. set of points no four of which are collinear) having a unique trisecant occur.

We now situate the problems that we will investigate and define the required codes and geometrical structures.

Let F q [X 0 , . . . , X N ] h d be the set of all homogeneous polynomials of degree d over the finite field F q in the variables X 0 , . . . , X N . Consider the projective space PG(N, q), and order the points P 0 , . . . , P θ N -1 , where θ N = q N +1 -1 q-1 , of PG(N, q) in a certain way, where we normalize the coordinates of the points P i by making the leftmost non-zero coordinate equal to one.

The d-th order q-ary projective Reed-Muller code PRM(q, d, N ) is the image of the map

Φ : F q [X 0 , . . . , X N ] h d ∪ {0} → F θ N q : F (X 0 , . . . , X N ) → (F (P 0 ), . . . , F (P θ N -1 )
). The parameters of these linear codes are:

-Length of PRM(q, d, N ) is θ N (see [START_REF] Lachaud | The parameters of projective Reed-Muller codes[END_REF]). [START_REF] Sørensen | Projective Reed-Muller codes[END_REF][START_REF] Sørensen | On the number of rational points on codimension-1 algebraic sets in P n (Fq)[END_REF]). For d < q, this reduces to δ = q N -(d -1)q N -1 .

-The dimension of PRM(q, d, N ) is k = N +d N , for d < q ([5]), while for d ≤ N (q -1), k = t=d mod q-1 0<t≤d   N +1 j=0 (-1) j N + 1 j t -jq + N t -jq   ([12]). -Minimum distance of PRM(q, d, N ): δ = (q -s)q N -r-1 , with d -1 = r(q -1) + s, 0 ≤ s < q -1, d ≤ N (q -1) (see
The non-zero codewords of minimum weight δ of PRM(q, d, N ) correspond to the algebraic hypersurfaces of degree d having the largest number of points in PG(N, q).

For d ≤ q -1, by the result of Serre [START_REF] Serre | Lettre à M. Tsfasman du 24 Juillet 1989[END_REF], the smallest weight codewords correspond to the algebraic hypersurfaces which are the union of d hyperplanes passing through a common (N -2)-dimensional subspace of PG(N, q).

In this article, we investigate the smallest configurations of d hyperplanes, determining in particular the second and the third smallest one; see Section 2. We would like to remark that these results hold only for d ≤ ϕ(1) and d ≤ ϕ(2) respectively (see Theorem 1 for the notations) and then the problem of determining the second and the third smallest configurations of hyperplanes in general remains still open. For this reason, we also give a construction which leads to an upper bound on the size of the second smallest configuration of hyperplanes; see Remark 1. Also, we determine the minimum number of points of a configuration of hyperplanes all passing through the same (N -4)-space, but not through a common (N -3)-space. Finally, in Section 3 we discuss the existence of examples of configurations attaining the bounds of Section 2.

Smallest configurations of hyperplanes

In this section we determine the smallest configurations of hyperplanes. Recall that a dual arc in a projective plane is a set of lines intersecting in pairwise distinct points and a dual (d, 3)-arc is a set of lines no four of which pass through a fixed point.

Definition 1. Let H 1 , . . . , H d be d hyperplanes in PG(N, q) such that H 1 ∩ • • • ∩ H d = S,
dq N -1 - d(d -3) 2 q N -2 + θ N -3 . (4)
2. B d 2 (N ): L is the dual of a (d, 3)-arc having only one trisecant. Its size is

dq N -1 - d 2 -3d -2 2 q N -2 + θ N -3 . (5)
3. B d 3 (N ): L is the dual of a (d, 3)-arc having two trisecants. Its size is

dq N -1 - d 2 -3d -4 2 q N -2 + θ N -3 . (6)
In [START_REF] Sboui | Special numbers of rational points on hypersurfaces in the n-dimensional projective space over a finite field[END_REF]Theorem 3.4], Sboui proves that the configuration

B d 1 (N ) (A d 4 in [9]
) is the smallest possible in terms of number of points.

Two hyperplanes in PG(N, q) intersect in a common (N -2)-space, therefore their union has 2q N -1 + θ N -2 points. There are only two possible configurations of three hyperplanes: either they share the same (N -2)-space and then their union has 3q N -1 + θ N -2 points or they share the same (N -3)-space and then their union has 3q N -1 + θ N -3 points. The possibilities for four hyperplanes are as follows:

1. C 1 (N ): all the hyperplanes pass through a common (N -2)-space: the size of this union is 4q N -1 + θ N -2 ; 2. C 2 (N ): all the hyperplanes pass through a common (N -3)-space and three of them pass through a common (N -2)-space: the size of this union is 4q N -1 -q N -2 + θ N -3 ; 3. C 3 (N ): all the hyperplanes pass through a common (N -4)-space and three of them pass through a common (N -3)-space: the size of this union is 4q N -1 -2q N -2 + 2q N -3 + θ N -4 ; 4. C 4 (N ): all the hyperplanes pass through a common (N -3)-space and no three of them pass through a common (N -2)-space: the size of this union is 4q

N -1 -2q N -2 + θ N -3 .
The following theorem presents the result about the second and the third smallest configurations of d hyperplanes in PG(N, q).

Theorem 1. 1. Let d > 3 + √ 2q and
d ≤ ϕ(1) = 2 3 (q + 2) + 2, q odd 1 2 q + 3, q even . Then, B d 2 (N ) is the second smallest configuration of d hyperplanes in PG(N, q). 2. Let d > 3 + 2 √ q and d ≤ ϕ(2) = 2 3 (q + 2) + 3, q odd 1 2 q + 4, q even .
Then, B d 3 (N ) is the third smallest configuration of d hyperplanes in PG(N, q). Let H 1 , . . . , H d , d > 3, d ≤ q + 2 if q is odd and d ≤ q + 3 if q is even, be d hyperplanes in PG(N, q), passing through a common (N -4)-space S, but not through a common (N -3)-space. It is possible to prove that their size is at least The difference between the size of the configurations B d 2 (N ) and B d 3 (N ), and the size of a configuration of hyperplanes passing through a common (N -4)space but not through a common (N -3)-space is greater than

θ N -4 + dq 2 - d 2 -3d 2 q + d 2 -5d + 8 2 q N -3 . (7)
3 + 2 √ q 2 -5 3 + 2 √ q + 6 2 -q q N -3 = q N -5 2 and 3 + √ 2q 2 -5 3 + √ 2q + 6 2 -q q N -3 = √ 2 2 q N -5 2
respectively.

In Section 3 we will show that the bound in Theorem 1 is sharp for q even, whereas for q odd the existence of configurations of hyperplanes attaining the bound is still an open problem.

Construction of 3-arcs having a unique trisecant

In this section, we discuss the existence of point sets in the projective plane PG(2, q) having a fixed number of i-secants. In particular, we will construct some examples of 3-arcs with a unique trisecant which give rise to the second smallest configuration of hyperplanes in PG(N, q).

Starting from an arc S of size n which admits a point P ∈ PG(2, q) \ S lying on b bisecants, it is possible to construct a 3-arc S of size n -b + 2, having a unique trisecant, simply by adding P and by removing one point of S from b -1 bisecants of S through P .

For instance, if q is odd, starting from a conic C and considering for P an external point to C, it is possible to construct a 3-arc of size q+7 2 having a unique trisecant.

Moreover, if q is even, starting from a hyperoval H (i.e. an arc in P G(2, q) of size q + 2) and considering for P any point not belonging to H, the number of bisecants to H passing through P is constant and it is equal to 1 2 q + 1. Then, it is possible to construct a 3-arc of size 1 2 q + 3 having a unique trisecant. As already mentioned after Theorem 1, it is worth noting that while in the even case this construction reaches the bound of Theorem 1, in the odd case that bound is far from reached.

Also, it is possible to construct 3-arcs with a unique trisecant of size q+1 2 + 2 starting from a particular type of plane cubic curve.

Remark 1. If d ≤ q + 1 (q odd) or d ≤ q + 2 (q even), then it is always possible to construct the smallest configuration of d hyperplanes. Otherwise, from the results of this section and from Corollary 1, if d ∈ 3 + √ 2q, q+1 2 + 3 (q odd) or d ∈ 3 + √ 2q, q 2 + 3 (q even), then it is always possible to construct the second smallest configuration of d hyperplanes. Unfortunately, in the interval q+1 2 + 4, q + 1 , q odd, no examples of 3-arcs with a unique trisecant are known. So it is presently unclear if this second smallest configuration of d hyperplanes, with d ∈ q+1 2 + 4, q + 1 , q odd, effectively occurs. For this reason, we also give a construction which leads to an upper bound on the size of the second smallest configuration of d hyperplanes.

Note that from a (d -1, 2)-arc, it is possible to obtain a (d, 3)-arc having at most d-1 2 trisecants. Therefore for d ≤ q + 2 (q odd) or d ≤ q + 3 (q even), and for α(S) ≤ d-1 2 , it is possible to construct a configuration of d hyperplanes having at most

dq N -1 - d 2 -3d 2 q N -2 + d -1 2 q N -2 + θ N -3 = dq N -1 - d 2 -4d + 1 2 q N -2 + θ N -3
points.

  with dim(S) = N -3. Let π be a plane not intersecting S and let L = {H i ∩ π | i ∈ {1, . . . , d}}. Consider the following configurations. 1. B d 1 (N ): L is a dual arc in π. Its size is (see also [9, Theorem 3.4])

  Furthermore, if Z is a solid disjoint from S, then equality holds if and only ifd -1 hyperplanes H 1 , . . . , H d-1 pass through a common (N -3)-space R ⊂ H d and the lines H 1 ∩ H d ∩ Z, . . . , H d-1 ∩ H d ∩ Z form a dual arc of H d ∩ Z.


Margaret Archibald
email: margaret.archibald@wits.ac.za

Aubrey Blecher
email: aubrey.blecher@wits.ac.za

Charlotte Brennan
email: charlotte.brennan@wits.ac.za

Arnold Knopfmacher
email: arnold.knopfmacher@wits.ac.za

Toufik Mansour
email: tmansour@univ.haifa.ac.il

Two by two squares in set partitions

Keywords: Set partitions, restricted growth functions, generating functions, Bell numbers

come

Introduction

A partition π of a set S is a collection B 1 , B 2 , . . . , B k of non-empty disjoint subsets of S such that k i=1 B i = S (see for example [START_REF] Mansour | Combinatorics of Set Partitions, Discrete Mathematics and its applications[END_REF]). The B i 's are called blocks, and the size |B| of a block B is the number of elements in B. We assume that B 1 , B 2 , . . . , B k are listed in increasing order of their minimal elements, that is, min B 1 < min B 2 < • • • < min B k . This is known as the canonical representation. The collection of all set partitions of S is denoted by P (S). We define [n] to be the set {1, 2, . . . , n}. For example, the canonical representations of the five partitions of [START_REF] Mansour | Combinatorics of Set Partitions, Discrete Mathematics and its applications[END_REF] are {1, 2, 3}; {1, 2}, {3}; {1, 3}, {2}; {1}, {2, 3} and {1}, {2}, {3}.

Let A be a (totally ordered) alphabet of k letters. A word w of size n over the alphabet A is an element of A n . In the case A = [k], an element of A n is called k-ary word of size n. For example, the 2-ary words of size 3 are 111, 112, 121, 122, 211, 212, 221, and 222. In the word form of the set partition canonical representation, we indicate for each integer the block in which it occurs. Thus a partition into k blocks would be represented by a word π = π 1 π 2 • • • π n , where for 1 ≤ j ≤ n, π j ∈ [k] and n i=1 {π i } = [k], and π j indicates that j ∈ B π j . For example, the above set partitions of [START_REF] Mansour | Combinatorics of Set Partitions, Discrete Mathematics and its applications[END_REF]

n = 0, 1, 2, • • • (see [4, Section 1.4], A000110 in [1]).
It is a fact (see [START_REF] Mansour | Combinatorics of Set Partitions, Discrete Mathematics and its applications[END_REF]) that the canonical representations of all set partitions of [n] are precisely the words π = π 1 π 2 • • • π n such that π 1 = 1, and if i < j then the first occurrence of the letter i precedes the first occurrence of j. Such words are known as restricted growth functions.

Set partitions (or restricted growth functions) have been extensively studied in the literature, see [START_REF] Mansour | Combinatorics of Set Partitions, Discrete Mathematics and its applications[END_REF] and references therein. The exponential generating function for set partitions is given by e e x -1 = ∑ ∞ n=0 B n

x n n! , and the Bell numbers B n satisfy the binomial recurrence

B n+1 = ∑ n k=0 n k B k with B 0 = 1.
In this paper we wish to find the number of squares of side two in the canonical representation or growth restriction function of set partitions of [n]. These squares can overlap and their bases are not necessarily on the x-axis.

For example the set partition {14}{23}{5}{6} has restricted growth function 122134. Our example has a total of three 2 × 2 squares. We illustrate one of these squares below. 1 2 2 1 3 4

Fig. 1: An example of a two by two square in the restricted growth function 122134

Generating function

Let P k (x, q) be the generating function for the number of set partitions of [n] with exactly k blocks, according to the number of squares of size 2 (2 by 2 squares). The number of parts is counted by x and the number of 2 by 2 squares by q. We introduce P k (x, q|a), the generating function for partitions that end with the letter a and similarly P k (x, q|ba) for those that end in ba (column b followed by column a).

Thus for set partitions ending in a we have

P k (x, q|a) = k ∑ b=1 P k (x, q|ba) = a-1 ∑ b=1 P k (x, q|ba) + k ∑ b=a P k (x, q|ba) = x a-1 ∑ b=1 q b-1 P k (x, q|b) + xq a-1 k ∑ b=a P k (x, q|b). (1)
For set partitions ending with the letter k, we have

P k (x, q|k) = k-1 ∑ b=1 P k (x, q|bk) + P k (x, q|kk) = x k-1 ∑ b=1 q b-1 [P k (x, q|b) + P k-1 (x, q|b)] + xq k-1 P k (x, q|k). (2)
The term P k-1 (x, q|b) corresponds to the case where the k-th block contains only one element.

To simplify the notation, we shall omit the variables x and q and write P k (a) for P k (x, q|a). Thus we have two cases depending on the size of a:

Case I: For 1 ≤ a ≤ k -1 P k (a) = x a-1 ∑ b=1 q b-1 P k (b) + q a-1 x k ∑ b=a P k (b), (3)
from equation [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF].

Case II: For a = k

P k (k) = x k ∑ b=1 q b-1 P k (b) + x k-1 ∑ b=1 q b-1 P k-1 (b) = xP k (x, q; q) + xP k-1 (x, q; q), (4)
from equation ( 2), where we define

P k (x, q; v) := k ∑ a=1 P k (a)v a-1 . (5)
We proceed with equation (3), multiply it by v a-1 and sum over all values of a for 1 ≤ a ≤ k -1 and obtain P k (x, q; v)

-P k (k)v k-1 = xA + xB -xq k-1 v k-1 P k (k), (6)
where

A = q 0 P k (1)v 1 + q 0 P k (1) + qP k (2)v 2 + • • • + q 0 P k (1)v k-2 + q 1 P k (2)v k-2 + • • • + q k-3 P k (k -2)v k-2
and

B =q 0 v 0 P k (1) + q 0 v 0 P k (2) + • • • + q 0 v 0 P k (k) + q 1 v 1 P k (2) + • • • + q 1 v 1 P k (k) + • • • + q k-2 v k-2 P k-1 (k -1) + q k-2 v k-2 P k-1 (k) + q k-1 v k-1 P k (k).
Now using equation ( 4) in ( 6) we have

P k (x, q; v) -x[P k (x, q; q) + P k-1 (x, q; q)]v k-1 = x q 0 P k (1) v -v k-1 1 -v + qP k (2) v 2 -v k-1 1 -v + • • • + q k-3 P k (k -2) v k-2 -v k-1 1 -v + q k-2 P k (k -1) v k-1 -v k-1 1 -v + x 1 -qv 1 -qv P k (1) + 1 -(qv) 2 1 -qv P k (2) + • • • + 1 -(qv) k 1 -qv P k (k) -x(qv) k-1 P k (k).
This implies that for k ≥ 2

P k (x, q; v) -x [P k (x, q; q) + P k-1 (x, q; q)] v k-1 = xv 1 -v P k (x, q; qv) -P k (k)(qv) k-1 - xv k-1 1 -v P k (x, q; q) -P k (k)(q) k-1 + x 1 -qv P k (x, q; 1) - xqv 1 -qv P k (x, q; qv) -x(qv) k-1 [P k (x, q; q) + P k-1 (x, q; q)] so that P k (x, q; v) = xv 1 -v P k (x, q; qv) - xv k-1 1 -v P k (x, q; q) + x 1 -qv P k (x, q; 1) - xqv 1 -qv P k (x, q; qv) + xP k (k)v k-1 .
We define P 0 (x, q; v) = 1 and P 1 (x, q; v) = x 1-x . Thus, if we introduce the variable y that counts the number of blocks, which is k in P(x, y, q; v) = ∑ k≥0 P k (x, q; v)y k we have

P(x, y, q; v) - xy 1 -x -1 = xv(1 -q) (1 -v)(1 -qv) P(x, y, q; qv) - xy 1 -x -1 - x 1 -v P(x, yv, q; q) - xvy 1 -x -1 + x 1 -qv P(x, y, q; 1) - xy 1 -x -1 + xy [P(x, yv, q; q) -1].
This simplifies to the following result.

Theorem 2.1. We have

P(x, y, q; v) = xv(1 -q) (1 -v)(1 -qv)
P(x, y, q; qv) + xy -x 1v P(x, yv, q; q) + x 1qv P(x, y, q; 1) + 1.

The series expansion starts 1 + xy + x 2 (y + vy 2 ) + x 3 (y + y 2 + vy 2 + qvy 2 + qv 2 y 3 ) + x 4 (y + 2y 2 + qy 2 + 2vy 2 + qvy 2 + vq 2 y 2 + qy 3 + q 2 vy 3 + v 2 y 3 + qv 2 y 3 + q 2 v 2 y 3 + q 3 v 2 y 3 + q 3 v 3 y 4 ). We illustrate the coefficient of x 4 i.e., the 15 set partitions with 4 parts in Figure 2. Recall v counts m -1 where m is the size of the last letter and y counts the number of blocks. Below each drawing is the number of two by two squares. It is well known that the generating function for the number of set partitions of [n] with exactly k blocks is given by P(x, y,

1 1 1 1 y 1 1 2 1 y 2 1 2 1 1 y 2 1 2 2 1 qy 2 1 2 1 2 vy 2 1 1 1 2 vy 2 1 1 2 2 qvy 2 1 2 2 2 q 2 vy 2 1 2 3 1 qy 3 1 2 3 2 q 2 vy 3 1 2 1 3 v 2 y 3 1 1 2 3 qv 2 y 3 1 2 2 3 q 2 v 2 y 3 1 2 3 3 q 3 v 2 y 3 1 2 3 4 q 3 v 3 y 4
1; 1) = ∑ k≥0 x k y k ∏ k j=1 (1-jx) .
On the other hand, Theorem 2.1 for q = 1 gives

P(x, y, 1; v) = xy - x 1 -v P(x, yv, 1; 1) + x 1 -v P(x, y, 1; 1) + 1.
Hence, the generating function for the number of set partitions of [n] with exactly k blocks according to which block the element n appears in is given by

P(x, y, 1; v) = 1 + ∑ k≥1 x k y k-1 (1 + v + • • • + v k-2 + v k-1 y) ∏ k-1 j=0 (1 -jx)
.

Theorem 2.1 with q = 0, we have

P(x, y, 0; v) = xv 1 -v P(x, y, 0; 0) + xy - x 1 -v P(x, yv, 0; 0) + xP(x, y, 0; 1) + 1,
which implies that P(x, y, 0; 0) = (xyx) + xP(x, y, 0; 1) + 1. Thus,

P(x, y, 0; v) = xv + 1 -v 1 -v P(x, y, 0; 0) + xy - x 1 -v P(x, yv, 0; 0) + x -xy. ( 7
)
Lemma 2.2. The generating function f k (x) for the number of words over alphabet [k] of length n with no squares of size 2 is given by 1+(k-1)x 1-x-(k-1)x 2 . Moreover, the generating function for the number of words aπ over alphabet [k] of length n with no squares of size 2 is given by

x 1-x-(k-1)x 2 .
Proof. Let f k (x|a) be the generating function for the number of words aπ over alphabet [k] of length n with no squares of size 2. Each word aπ with a ≥ 2 and π is not empty word, we have the first letter of π is 1, otherwise aπ has a square of size 2. Thus,

f k (x|a) = x + x 2 f k (x), for all a = 2, 3, . . . , k. Note that f k (x|1) = x f k (x). Therefore, by the fact that f k (x) = 1 + ∑ k a=1 f k (x|a), we obtain f k (x) = 1 + (k -1)x 1 -x -(k -1)x 2 . Moreover, f k (x|a) = x 1-x-(k-1)
x 2 , which completes the proof.

Each set partition π1 with exactly k blocks with no squares of size 2 can be written as

π (1) 12π (2) 13π (3) • • • 1kπ (k) 1,
where π ( j) is a word over alphabet [ j] such that jπ ( j) has no squares of size 2. Hence, by Lemma 2.2, we have

P(x, y, 0; 0) = 1 + ∑ k≥1 xy k 1 -x k ∏ i=2 x 2 1 -x -(i -1)x 2 = 1 + ∑ k≥1 x 2k-1 y k ∏ k-1 i=0 (1 -x -ix 2 )
.

Hence, by (7), we obtain

P(x, y, 0; v) = 1 + ∑ k≥1 x 2k-1 y k ∏ k-1 i=0 (1 -x -ix 2 ) + ∑ k≥1 x 2k y k (v + v 2 + • • • + v k-1 ) ∏ k-1 i=0 (1 -x -ix 2 ) + xy ∑ k≥1 x 2k-1 v k y k ∏ k-1 i=0 (1 -x -ix 2 )
, which implies the following result.

Theorem 2.3. We have P(x, y, 0; 1)

= 1 + ∑ k≥1 x 2k-1 y k (1 + (k -1)x + xy) ∏ k-1 i=0 (1 -x -ix 2 )
.

Although we did not succeed to solve the functional equation in Theorem 2.1, we have come with a new technique to study the generating function P(x, y, q; 1). In order to do that, we define the following notation. Let W k (x) be the generating function for the words over alphabet [k] of length n according to the number of squares of size 2. Theorem 2.4. Fix 1 ≤ a ≤ k. Let W k (x|a) be the generating function for the words aπ over alphabet [k] of length n according to the number of squares of size 2. Then

W k (x) = 1 + ∑ k i=1 x i ∑ k-1≥ j 1 > j 2 >•••> j i ≥0 (1 -q j i ) ∏ i m=2 (q j m -q j m-1 ) 1 -∑ k i=1 x i ∑ k-1≥ j 1 > j 2 >•••> j i ≥0 q j i ∏ i m=2 (q j m -q j m-1 )
.

Moreover, W k (x|a) = M a (x; q)W k (x) + L a (x; q), where

M a (x; q) = a ∑ i=1 x i ∑ a-1= j 1 > j 2 >•••> j i ≥0 q j i i ∏ m=2 (q j m -q j m-1 ), L a (x; q) = a ∑ i=1 x i ∑ a-1= j 1 > j 2 >•••> j i ≥0 (1 -q j i ) i ∏ m=2
(q j mq j m-1 ).

Proof. By the definitions

W k (x|a) = x + x a-1 ∑ j=1 q j-1 W k (x| j) + xq a-1 k ∑ j=a W k (x| j), which, by W k (x) = 1 + ∑ k a=1 W k (x|a), is equivalent to W k (x|a) = x(1 -q a-1 ) + xq a-1 W k (x) + x a-1 ∑ j=1 (q j-1 -q a-1 )W k (x| j).
Assume that W k (x|a) = M a (x; q)W k (x) + L a (x; q). Then M a (x; q) = xq a-1 + x a-1 ∑ j=1 (q j-1q a-1 )M j (x; q). and L a (x; q) = x(1q a-1 ) + x a-1 ∑ j=1 (q j-1q a-1 )L j (x; q). By induction on a, we have

M a (x; q) = a ∑ i=1 x i ∑ a-1= j 1 > j 2 >•••> j i ≥0 q j i i ∏ m=2 (q j m -q j m-1 ), L a (x; q) = a ∑ i=1 x i ∑ a-1= j 1 > j 2 >•••> j i ≥0 (1 -q j i ) i ∏ m=2
(q j mq j m-1 ).

Thus,

a ∑ j=1 M j (x; q) = a ∑ i=1 x i ∑ a-1≥ j 1 > j 2 >•••> j i ≥0 q j i i ∏ m=2 (q j m -q j m-1 ), a ∑ j=1 L j (x; q) = a ∑ i=1 x i ∑ a-1≥ j 1 > j 2 >•••> j i ≥0 (1 -q j i ) i ∏ m=2
(q j mq j m-1 ).

Hence, the generating function W k (x) is given by

W k (x) = 1 + ∑ k j=1 L j (x; q) 1 -∑ k j=1 M j (x; q)
, and the generating function W k (x|a) is given by W k (x|a) = M a (x; q)W k (x) + L a (x; q), as required.

Example 2.5. Theorem 2.

4 for k = 1, 2, 3 gives W 1 (x) = 1 1-x , W 2 (x) = 1+(1-q)x 1-(1+q)x-(1-q)x 2 and W 3 (x) = 1+x(2-q-q 2 )+x 2 q(1-q) 2 1-x(1+q+q 2 )-x 2 (2-q-q 3 )-x 3 q(1-q) 2 .
In the next result, we study a particular case, namely, the generating function W * k (x) for the number of words π over alphabet [k] of length n according to the number of squares of size 2 in π(k + 1). More generally, Let W * k (x|a) be the generating function for the number of words aπ over alphabet [k] of length n according to the number of squares of size 2 in aπ(k + 1).

Theorem 2.6. We have

W * k (x) = 1 1 -∑ k i=1 x i ∑ k-1≥ j 1 > j 2 >•••> j i ≥0 q j i ∏ i m=2 (q j m -q j m-1 )
.

Moreover, for all a = 1, 2, . . . , k,

W * k (x|a) = ∑ a i=1 x i ∑ a-1= j 1 > j 2 >•••> j i ≥0 q j i ∏ i m=2 (q j m -q j m-1 ) 1 -∑ k i=1 x i ∑ k-1≥ j 1 > j 2 >•••> j i ≥0 q j i ∏ i m=2 (q j m -q j m-1 )
.

Proof. By the definitions

W * k (x|a) = xq a-1 + x a-1 ∑ j=1 q j-1 W * k (x| j) + xq a-1 k ∑ j=a W * k (x| j).
As usual by

W * k (x) = 1 + ∑ k a=1 W * k (x|a). Hence W * k (x|a) = xq a-1 W * k (x) + x a-1 ∑ j=1 (q j-1 -q a-1 )W * k (x| j).
Thus, by induction on a, we obtain

W * k (x|a) = W * k (x) a ∑ i=1 x i ∑ a-1= j 1 > j 2 >•••> j i ≥0 q j i i ∏ m=2 (q j m -q j m-1 ). Hence, by W * k (x) = 1 + ∑ k a=1 W * k (x|a), we have W * k (x) = 1 1 -∑ k i=1 x i ∑ k-1≥ j 1 > j 2 >•••> j i ≥0 q j i ∏ i m=2 (q j m -q j m-1 )
, as required.

Theorem 2.7. The generating function P(x, y, q, 1) for the number of set partitions of [n] with exactly k blocks according to the number of squares of size 2 is given by P(x, y, q, 1)

= 1 + ∑ k≥1 y k M k (x; q) 1 + ∑ k i=1 L i (x; q) 1 -∑ k i=1 M i (x; q) + L k (x; q) k-1 ∏ ℓ=1 M ℓ (x; q) 1 -∑ ℓ i=1 M ℓ (x; q)
, where

M a (x; q) = a ∑ i=1 x i ∑ a-1= j 1 > j 2 >•••> j i ≥0 q j i i ∏ m=2 (q j m -q j m-1 ), L a (x; q) = a ∑ i=1 x i ∑ a-1= j 1 > j 2 >•••> j i ≥0 (1 -q j i ) i ∏ m=2
(q j mq j m-1 ).

Proof. Fix k. Note that each set partition with exactly k blocks can be presented as 1π (1) 2π (2) • • • kπ (k) , where π ( j) is a word over alphabet [ j]. By using Theorem 2.4 and Theorem 2.6, we obtain that the generating function for the number of set partitions of [n] with exactly k blocks according to the number of squares of size 2 is given by

W * 1 (x|1)W * 2 (x|2) • • •W * k-1 (x|k -1)W k (x|k),
as claimed.

Example 2.8. Let us consider Theorem 2.7 when q = 1. For q = 1, M a (x) | q=1 = x and L a (x) | q=1 = 0. Thus, P(x, y, 1, 1)

= 1 + ∑ k≥1 xy k 1 -kx k-1 ∏ ℓ=1 x 1 -ℓx = ∑ k≥0 x k y k (1 -x)(1 -2x) • • •(1 -kx) ,
as is well known.

Example 2.9. Here, we focus on the case q = 0, namely, set partitions with no squares of size 2. Theorem 2.7 with q = 0 gives that M 1 (x) | q=0 = x, L 1 (x) = 0, and M a (x) | q=0 = xL a (x) | q=0 = x 2 for a = 2, 3, . . . , k, i.e., L a (x)| q=0 = x. Hence, P(x, y, 0, 1)

= 1 + xy 1 -x + ∑ k≥2 y k x 2k ∏ k ℓ=1 (1 -x -(ℓ -1)x 2 )
.

Average

According to the definitions in Theorem 2.7, we have

M a (x; 1) = x, L a (x; 1) = 0, d dq M a (x; q)| q=1 = (a -1)x - a 2 x 2 , d dq L a (x)| q=1 = -(a -1)x.
Thus, by Theorem 2.7, we obtain Corollary 3.1. The generating function d dq P(x, y, q, 1)| q=1 for the total number of squares of size 2 in all set partitions of [n] with exactly k blocks is given by d dq P(x, y, q, 1)

q=1 = 1 6 ∑ k≥1 y k k ∏ ℓ=1 x 1 -ℓx k(k -1)(3 -x -kx)x 1 -kx + k-1 ∑ ℓ=1 (ℓ -1)(6 -6ℓx -ℓ(1 -2ℓ)x 2 ) 1 -ℓx .
In order to study the generating function d dq P(x, y, q, 1)| q=1 , we will find an exponential generating function E(x, y) for the total number of squares of size 2 in all set partitions of [n] with exactly k blocks. This can be done by extending the coefficient of x n in d dq P(x, y, q, 1)| q=1 and then replacing x n by x n /n!. At first, we write d dq P(x, y, q, 1)

q=1 = 1 6 ∑ k≥1 y k k ∏ ℓ=1 x 1 -ℓx - 2k x + 2k 2 -7k + 6 - x 6 (4k 3 -21k 2 + 17k) + k ∑ ℓ=1 2/x 1 -ℓx + k ∑ ℓ=1 x -3 1 -ℓx .
The ordinary and exponential generating functions for the number of set partitions of [n] with k blocks are given by ∑ k≥1 y k ∏ k ℓ=1 x 1-ℓx and e y(e x -1) -1 respectively. We obtain that the exponential generating function that corresponding to the ordinary generating function By collecting all theses terms together, we obtain that E(x, y) = e y(e x -1) -1 -ye y(e x -1) 3 1 + y + 7 2 (e x -1) + y 6 e x+y(e x -1) (2x + 2xye x ) -y 9

x 0 (e t -1)e y(e t -1) (y(e t -1) + (1 + y(e t -1)) 2 )dt + 7y 12

x 0 (e t -1)e y(e t -1) (1 + y(e t -1))dt -17y 36

x 0 ((e t -1)e y(e t -1) dt + y 6

x 0 te t e y(e t -1) dt.

At y = 1, we have that

  in canonical representation are respectively 111, 112, 121, 122 and 123. We denote the set of all partitions of [n] by P ([n]), and the number of all set partitions of [n] by B n = |P ([n])|, with B 0 = 1 for the empty set. The B n are known as the Bell numbers. Their sequence starts with 1, 1, 2, 5, 15, 52, 203, 877, • • • for

Fig. 2 :

 2 Fig. 2: Two by two squares in the 15 set partitions with 4 parts

  Note that F(x) = ∑ n≥0 a n x n = ∑ k x n = ∑ k≥1 y k ∑ n≥k nS n,k x n-1 ,where S n,k is the Stirling number of the second kind. Therefore, the corresponding exponential generating function is given by ∑

- 1 .

 1 Let B(x) = e e x -1 = ∑ n≥0 B n x n n! be the exponential generating function for the number of set partitions of [n].

This material is based upon work supported by the National Research Foundation under grant numbers 89147 This material is based upon work supported by the National Research Foundation under grant numbers 86329 This material is based upon work supported by the National Research Foundation under grant numbers 81021

Hence, the coefficient of x n n! in d dx E(x, 1) is given by Kasraoui [START_REF] Kasraoui | Average values of some z-parameters in a random set partition[END_REF] showed

) . Hence, asymptotically, the mean of the number of squares of size 2 over all set partitions of [n] is given by n 2 3 log n .


Anthony Journault

François-Xavier Standaert

Improving the Security and Efficiency of Block Ciphers based on LS-Designs -Extended Abstract

LS-designs are a family of bitslice ciphers aiming at efficient masked implementations against side-channel analysis. This paper discusses their security against invariant subspace attacks, and describes an alternative family of eXtended LS-designs (XLS-designs), that enables additional options to prevent such attacks. LS-and XLS-designs provide a large family of ciphers from which efficient implementations can be obtained, possibly enhanced with countermeasures against physical attacks. We argue that they are interesting primitives in order to discuss the general question of "how simple can block ciphers be?".

Introduction

LS-designs are a family of block ciphers proposed at FSE 2014, aimed for efficient bitslice implementations [START_REF] Grosso | LS-designs: Bitslice encryption for efficient masked software implementations[END_REF]. They essentially combine linear diffusion L-boxes with non-linear bitslice S-boxes. The instances proposed so far (namely the involutive cipher Robin and the non-involutive cipher Fantomas) have additionally been selected to minimize the total number of AND gates, in order to allow efficient masked implementations against side-channel attacks [START_REF] Chari | Towards sound approaches to counteract power-analysis attacks[END_REF], which is also beneficial to multiparty computation and fully homomorphic encryption [START_REF] Albrecht | Ciphers for MPC and FHE[END_REF]. In a more recent work by Leander et al., it has been shown that the involutive instance Robin was susceptible to an invariant subspace attack, leading to a weak keys set of density 2 -32 for this cipher [START_REF] Leander | A generic approach to invariant subspace attacks: Cryptanalysis of Robin, iSCREAM and Zorro[END_REF]. This raised questions regarding the origin of the attack and the possibility to prevent it for involutive LS-designs.

In this paper, we complement these works with two main contributions.

First, we analyze the invariant subspace attack against Robin and show that one can prevent it, e.g. with a better choice of round constants. Of particular interest in this respect is the fact that these constants should have all their bits varying (in bitslice representation), in order to avoid invariant subspaces for the S-boxes or L-boxes to be trivially propagated through the rounds.

Second we question the possibility to improve the efficiency of LS-designs with a better choice (and different sizes) of components. In particular, Robin and Fantomas are based on 8-bit S-boxes and 16-bit L-boxes. While very convenient from an implementation point-of-view, the selection of these components was partially heuristic (since, e.g. an exhaustive analysis of 8-bit S-boxes is computationally out of reach). As a result, we investigate an alternative approach in two steps. First, we design 32-bit "Super S-Boxes" based on optimal components (i.e. 4-bit S-box and 32-bit L-box based on a MDS code). Second, we combine these Super S-boxes with an additional ShiftColumns operation. Both the use of Super S-boxes and their combination with a ShiftColumns operation are naturally reminiscent from an AES-like cipher [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF][START_REF] Gilbert | Super-sbox cryptanalysis: Improved attacks for AES-like permutations[END_REF], but with a bitslice rather than block-oriented structure. Interestingly, we show that the resulting eXtended LSdesigns (XLS-designs) can also be implemented very efficiently, e.g. based only on table lookups and word-oriented operations, yet leading to slighly more complex tradeoffs than LS-designs, due to their slightly more involved structure. For concreteness and further investigations, we additionally specify an instance of such XLS-design, denoted as Mysterion, with 128-bit or 256-bit block size.

2 Fixing the invariant subspace attacks against Robin 2.1 LS-designs, Robin and Fantomas LS-designs are a family of block ciphers that are composed of a combination of lookup table-based L-boxes and bitslice S-boxes. The definition of s-bit Sboxes and l-bit L-boxes directly gives rise to an instance of n = s • l-bit cipher. One advantage of LS-designs is their inherent simplicity, as illustrated with the short specifications given in Algorithm 1. The cipher takes n-bit plaintext and key blocks as input, and follows Substitution Permutation Network (SPN) approach. Namely, the inputs and state are represented as s • l arrays of bits, with s the number of rows and l is the number of columns. In each round, the S-box operation acts on the columns, and the L-box operation acts on the rows. These two components combined with constant and key addition define the round function of LS-designs, that is iterated N r times in order to obtain the ciphertext.

Algorithm 1 LS-design with l-bit L-boxes and s-bit S-boxes

x ← P ⊕ K; x is an s • l-bit matrix for 0 ≤ r < Nr do for 0 ≤ i < l do S-box Layer x[i, ] = S[x[ , i]]; for 0 ≤ j < s do L-box Layer x[ , j] = L[x[j, ]]; x ← x ⊕ K ⊕ C(r);
Key addition and round constant return x Concretely, both Robin and Fantomas were based on 8-bit S-boxes and 16-bit Lboxes. For the former one, these components are involutive, in order to improve the performances of the cipher when decryption has to be implemented.

Invariant subspace attacks and results on Robin

The invariant subspace attack was first introduced at CRYPTO 2011 [START_REF] Leander | A cryptanalysis of PRINTcipher: The invariant subspace attack[END_REF] and applied to the lightweight "PRINTcipher" [START_REF] Knudsen | Printcipher: A block cipher for ic-printing[END_REF]. We can summarize the attack as follows. Let us consider an n-bit iterative block cipher, with round function

R k : F n 2 × F n 2 → F n 2 , such that R k (x) = E(x + k)
, with E an n-bit permutation. If there exists a subspace S ⊆ F n 2 and two constants a, b ∈ F n 2 such that E(S + a) = S + b, then for a round key k = s + a + b with s ∈ S, the following holds:

R k (S + b) = E((S + b) + (s + a + b)) = E(S + a) = S + b.
That is, the round function maps the affine subspace S + a onto S + b. Furthermore, if all round keys are in S + (a + b), then this property is iterative. This is the case for some Even-Mansour block ciphers, where the same master key is used as subkey through the whole cipher, e.g. LED [START_REF] Guo | The LED block cipher[END_REF], Zorro [START_REF] Gérard | Block ciphers that are easier to mask: How far can we go?[END_REF], Noekeon [START_REF] Daemen | The block cipher Noekeon[END_REF], Fantomas and Robin [START_REF] Grosso | LS-designs: Bitslice encryption for efficient masked software implementations[END_REF], which are therefore natural targets for invariant subspace attacks. The Eurocrypt 2015 paper that exhibits a weak keys set of density 2 -32 for Robin is based in this property, and essentially takes advantage of the involutive nature of its components together with weak round constants [START_REF] Leander | A generic approach to invariant subspace attacks: Cryptanalysis of Robin, iSCREAM and Zorro[END_REF].

More precisely, the involutive building blocks of Robin helps finding selfsimilarities within the cipher -a new type of such self-similarities (for the Lboxes) is actually given in the Eurocrypt paper. Besides, and as mentioned above, LS-designs are such that S-boxes act through columns and the linear layer acts through rows. Hence, if there exists an invariant subspace (e.g.) for the S-box layer and all inputs to the S-boxes are chosen from it, then the linear layer will not change this subspace1 . That is, if we call the bits which form the invariant subspace active and other bits passive (as in differential cryptanalysis), then the linear layer does not mix active and passive bits. Combined with the fact that the round constants of Robin are sparse, and only apply to one state row, this allowed the propagation of invariant subspaces through the cipher. An illustration of the attack based on an invariant subspace for the S-box layer is given in Figure 1, where black boxes represent bits that form an invariant subspace.

Fixing the attack

Based on the previous description, a couple of ways to fix the invariant subpace attack could be considered for Robin, e.g. changing its components (linear layer & S-box), applying a key scheduling, or changing the round constants. Among those, changing the round constants is the easiest one, since it implies minimum changes on the design. Concretely, one suggestion is to use a dense set of round constants, applied to all the rows rather than a single one. For example, a Linear Feedback Shift Register (LFSR) with 16-bit state size (and e.g. primitive polynomial P (X) = X 16 + X 5 + X 3 + X 2 + 1) could be used for this purpose. Eight consecutive states can then be combined together to form each round constant. We verified with the same generic algorithm as described in [START_REF] Leander | A generic approach to invariant subspace attacks: Cryptanalysis of Robin, iSCREAM and Zorro[END_REF] that this choice was sufficient to remove the invariant subspaces from the Robin rounds (up to the computational limits of the algorithm). We also checked exhaustively that no invariant subspaces can propagate through the rounds of reduced (32-bit) LS-designs using such dense constants. Note that despite no invariant subspace attack has been exhibited against the non-involutive cipher Fantomas, it has a similar structure as Robin, and its round constants are sparse as well. Therefore, tweaking this cipher (e.g. with stronger round constants) could be advisable too. Eventually, we mention that the tweak described in this subsection may not be the most efficient, and is mainly suggested as a proof-of-concept that involutive LS-designs are not inherently susceptible to invariant subspace attacks.

The Mysterion instance

The previous section highlighted that invariant subspace attacks against (noninvolutive) LS-designs exploit the structural simplicity of these ciphers. While this simplicity is highly beneficial to implementation efficiency, it also leads to the question whether a slightly more involved structure could provide better security margins. In this section, we consequently investigate this option and, motivated by the efficient masking goal of LS-designs, combine it with a further improvement of the balance between linear and non-linear operations within the cipher. The rationale behind this tweaked approach is twofold. First, for the linear part, we observe that from the security point-of-view it would be interesting to take advantage of a (non-binary) MDS code to build the diffusion layer. Second, for the non-linear part, it would be interesting to take advantage of optimal S-boxes, that we only know for smaller bit sizes. For example, Ullrich et al. found an optimal (from the linear and differential cryptanalysis points-ofview) 4-bit S-box requiring only 4 AND gates (next denoted as Class 13) [START_REF] Ullrich | Finding optimal bitsliced implementations of 4x4bit s-boxes[END_REF].

Based on these observations, we propose new instances of ciphers where we first combine an optimal 4-bit S-box with an MDS diffusion matrix, which results in 32-bit Super S-boxes, and then combine these Super S-boxes with a ShiftColumns operation to obtain 128-and 256-bit ciphers. Admittedly, this approach does not strictly follow the LS-design specifications, since (i ) its diffusion layer is not based on binary matrices anymore, and (ii ) it requires an additional ShiftColumns operations. So it primarily aims at improving the security margins of LS-designs, e.g. against linear and differential cryptanalysis and invariant subspace attacks (see Section 3.2). Yet, and quite interestingly, we will show in Section 3.3 that the resulting XLS-designs can still be implemented very efficiently, taking advantage of the linearity of the MDS diffusion and ShiftColumns operations. So intuitively, the main price to pay for the latter approach is slightly more complex specifications (although they can be viewed as a bitslice counterpart to AES-like ciphers and therefore have a concise description), which are interesting to compare with the extreme simplicity of LS-designs, both from the implementation efficiency and the physical security points-of-view.

Specifications

XLS-designs can be described as the gathering of b LS-designs of s • l bits, where s is the size of the S-box (in bits, as in LS-designs), and l is the size of the underlying MDS matrix of the L-box (and no longer the bit size of the L-box as in LS-designs), resulting in a n = b • s • l-bit cipher. Note that this slight change of meaning for the l notation is mandatory to keep notations consistent with LS-designs, since a binary matrix cannot be MDS. Concretely, the internal state of an XLS-design can be written as X[ , , ], such that

X[i, , ] is an s • l-bit block (with 1 ≤ i ≤ b), X[i, j, ] is block i's jth l-bit row (with 1 ≤ j ≤ s)
and X[i, , j] is block i's jth s-bit column (with 1 ≤ j ≤ l). As illustrated in Figure 2, the S-box layer of XLS-designs is strictly the same as in Algorithm 1. Their L-box layer slightly changes compared to LS-designs, since it is applied to all the rows of each block at once (rather than to row by row in LS-designs). And the main difference is the additional ShiftColumns layer, that can be viewed as the bitslice dual to the ShiftRows operation in the AES Rijndael, and will be defined next. XLS-designs are succintly described in Algorithm 2. We now describe the different components that give rise to the Mysterion-128 instance (with a state made of four 32-bit blocks), and the Mysterion-256 instance (with a state made of eight 32-bit blocks), that both exploit 4-bit S-boxes.

S-boxes S-boxes L-boxes L-box

ShiftColumns

LS-designs XLS-designs

Algorithm 2 XLS-design with l • s-bit L-boxes, s-bit S-boxes and b blocks

1: x ← P ⊕ K;
x is a s • (l.b) bits matrix 2: for 0 ≤ r < Nr do 3:

for 0 ≤ j < b do 4:

for 0 ≤ i < l do 5:

x[j, , i] = S[x[j, , i]]; S-box layer 6:

for 0 ≤ j < b do 7:

x

[j, , ] = L[x[j, , ]]; L-box layer 8:
for 0 ≤ k < s do 9:

x[ , k, ] = ShiftColumns[x[ , k, ]]; ShiftColumns layer 10:

x ← x ⊕ K ⊕ C(r); Key and round constant addition return x

The S-box. Mysterion uses the Class13 S-box [START_REF] Ullrich | Finding optimal bitsliced implementations of 4x4bit s-boxes[END_REF], that is non-involutive, has a bitslice representation with 4 AND2 and 4 XOR gates (see Appendix A), algebraic degree 3, differential probability of 2 -2 , and linear probability of 2 -1 .

The L-box. Mysterion uses a linear transform derived from the recent paper by Augot and Finiasz [START_REF] Augot | Direct construction of recursive mds diffusion layers using shortened bch codes[END_REF], in which an algorithm allowing to find recursive MDS diffusion layers using shortened BCH codes is described. A recursive MDS matrix is a matrix that can be expressed as a power of the companion matrix of a polynomial. This algorithm uses the degree of the polynomial k (hence the size of the companion matrices), and the field size q = 2 s as parameters, and provides all the polynomials of degree k over F 2 s such as their companion matrices raised to the power k gives MDS diffusion layers. We ran it with parameters k = 8 and s = 4 using Magma, in order to obtain an 8 × 8 MDS matrix over F 2 4 . The selected degree-8 polynomial with coefficients in

F 2 4 ∼ = F 2 [α]/(α 4 + α + 1), is P (X) = X 8 +α 3 •X 7 +α 4 •X 6 +α 12 •X 5 +α 8 •X 4 +α 12 •X 3 +α 4 •X 2 +α 3 •X +1.
The resulting diffusion layer is coming from an MDS code [START_REF] Piret | PICARO -A block cipher allowing efficient higher-order side-channel resistance -extended version[END_REF][START_REF] Gérard | Block ciphers that are easier to mask: How far can we go?[END_REF][START_REF] Gilbert | Super-sbox cryptanalysis: Improved attacks for AES-like permutations[END_REF] F 2 4 and therefore has both its differential and linear branch number equal to 9.

ShiftColumns. For Mysterion-128, ShiftColumns acts on columns two by two. The two first columns of each block are not moved, the two second columns are moved by one block, the two third columns are moved by two blocks, and the two fourth columns are moved by three blocks. This operation can also be described as a bit permutation of a 32-bit word, with logic operations:

X = (X & 0xC0C0C0C0) ∨ ROL(X & 0x03030303,8) ∨ ROL(X & 0x0C0C0C0C,16) ∨ ROL(X & 0x30303030,24)
, where ∨ and & stand for logic OR and AND, and ROL(X,n) stands for the left rotation of X by n bits. For Mysterion-256, ShiftColumns acts on columns one by one. The first columns of each block are not moved, the second columns are moved by one block, . . ., and the eighth columns are moved by seven blocks. See Appendix A for the alternative description. As for round constants, we suggest to use simpler ones as in the original Robin and Fantomas ciphers. This will be further justified in the next section.

These components directly define our two instances

Security analysis

A complete security analysis of the Mysterion instances is out of the scope of this extended abstract because of place constraints (more details will be given in the full version of the paper). Hence, our main goal in this section is twofold. On the one hand, we want to show that simple 4-round bounds against linear and differential cryptanalyses can be obtained for XLS-designs, inheriting from their AES-like structure. On the other hand, we want to argue why its more complex structure also improves resistance against invariant subspace attacks. Note that as for LS-designs, no related-key security is claimed for Mysterion.

Security against linear and differential cryptanalyses. A straightforward application of the wide-trail strategy [START_REF] Daemen | The wide trail design strategy[END_REF] leads to the following theorems. A sketch of the proofs is in Appendix B. As a result, we directly have the following bounds for the probabilities of linear and differential characteristics for 4 Mysterion-128 rounds (where we use the same definitions as in [START_REF] Grosso | LS-designs: Bitslice encryption for efficient masked software implementations[END_REF] Security against invariant subspace attacks. As briefly discussed in Section 2.2, invariant subspace attacks can be of two kinds. A (simpler) one taking advantage of invariant subspaces in the S-box and (a more intricate) one using equality spaces in the L-box (that is highly structured in the case of Robin). The first one is easy to bypass with a good choice of S-box, e.g. the Class13 S-box has no invariant subspaces. The second one is more difficult to analyze. So far, the Eurocrypt 2015 results only describe a heuristic tool allowing to look for such invariant subspaces. Hence, running this tool (with the available computational resources) on full cipher instances, and exhaustively on reduced cipher instances, is the best that we can currently do. For example, Leander et al. could not spot invariant subspaces against Fantomas using this appraoch. In the case of Mysterion, we first note that the use of a 32-bit L-box is not sufficient to prevent the existence of invariant subspaces within the rounds (as revealed by an exhaustive analysis performed on a 32-bit block). However, the addition of a ShiftColumns operation will break the propagation of any subspace found for the L-box with high probability. This was confirmed by a computationally-bounded analysis performed on Mysterion-128. We therefore conclude that XLS-designs can withstand invariant subspace attacks even with sparse round constants (as usually used in block cipher designs, in order to limit their memory requirements).

Performances

One of the goals of LS-designs (hence, by extesion, XLS-designs) is to allow efficient masked implementations. In this respect, a natural problem is to find out whether the slightly more complex structure of XLS-designs, using (nonbinary) MDS matrices and an additional ShiftColumns transform, leads to a loss of efficiency. In this section, we briefly discuss this issue and detail how efficient table lookup-based implementations of Mysterion-128 can be obtained.

In general, the implementation of a 32-bit Super S-box can be directly implemented with logic operations (which is more time consuming), or with table lookups as in the case of the AES Rijndael (which is faster, but requires 16 tables of 256 bytes, rather than 4 such tables for a 128-bit LS-design). Next, the ShiftColumns operation mixes bits of different blocks, which can exploit the logic representation given in Section 3.1, or be implemented with table lookups. This leads to interesting tradeoffs from the physical security point-of-view. On the one hand, the logic representation of ShiftColumns requires less memory than its table-based execution, and acts at the row level. On the other hand, performing ANDs with constants including some bits set to zero can be viewed as a bit manipulation that may lead to harder to prevent leakages (as argued in [START_REF] Grosso | LS-designs: Bitslice encryption for efficient masked software implementations[END_REF]).

For illustration, we implemented Mysterion-128 on a 8-bit microcontroller (Atmel AtMega644p), based on a mixed approach, namely table lookups for the L-boxes and logic operations for ShiftColumns. We wrote our reference code in C and used the avr-libc library with headers #include <avr/pgmspace.h> and #include <avr/io.h>. We also used the PROGMEM attribute to save RAM. Results were obtained with the avr-gcc compiler and optimization option -O2.

We simulated the execution time of the implementations using the Atmel AVR Studio 6 software. Performances are reported for an unrolled version of the code. Figure 3 summarizes our results in terms of number of cycles for Mysterion-128, together with natural competitors, i.e. Robin and Fantomas [START_REF] Grosso | LS-designs: Bitslice encryption for efficient masked software implementations[END_REF], Zorro [START_REF] Gérard | Block ciphers that are easier to mask: How far can we go?[END_REF], Noekeon [START_REF] Daemen | The block cipher Noekeon[END_REF], PICARO [START_REF] Piret | PICARO -A block cipher allowing efficient higher-order side-channel resistance -extended version[END_REF] and the AES [START_REF] Rivain | Provably secure higher-order masking of AES[END_REF]. Security order 0 means unprotected implementation i.e. one share or no mask, security order 1 means two shares or one mask, and so on. Excepted for unprotected implementions (for which Mysterion-128 is slightly less efficient than its competitors), the main conclusion of these evaluations is that such an XLS-design has excellent performances. More precisely, the reduced amount of non-linear operations in Mysterion-128 allows its implementations to compare favorably with its competitors already for firstorder security. As previously mentioned, the price to pay for these excellent performances are potentially more leaky operations, which can be avoided using table lookups, but would then lead to larger memory requirements.

Conclusions

This work enlarges the block cipher design space from LS-designs to XLS-designs. We believe this is an interesting step forward, since it is in line with the general question of "how simple can block ciphers be?", in a context -i.e. considering the risk of side-channel analysis -where simplicity is usually correlated with security. Indeed, simple and very structured ciphers are generally easier to protect against physical attacks. In this respect, our first contribution is to show that LS-designs are not inherently susceptible to invariant subspace attacks, but that their instantiation should carefully consider them. And our second contribution is to show that XLS-designs can indeed be implemented efficiently (and lead to better security bounds against linear and differential cryptanalysis), but that their best implementation requires informed decisions (e.g. on whether the use of bit manipulations can be critical). These questions lead to many open problems regarding the best cipher instances for different block/key sizes. For example, instances with 3-bit S-boxes could be considered to minimize the AND depth as in [START_REF] Albrecht | Ciphers for MPC and FHE[END_REF]; instances with 5-bit S-boxes could lead to even reduced round requirements (for linear and differential attacks); even for the 4-bit instances, it could be interesting to investigate the use of L-boxes based circulant matrices such as advertized in [START_REF] Albrecht | Block ciphers -focus on the linear layer (feat. PRIDE)[END_REF], which would allow alternative implementations to prevent cache-based timing attacks (although SSSE3 instructions can also be used for this), . . . And should we use LS-or XLS-designs for any of those instances? Whether a key scheduling has to be included and how, especially for cipher instances claiming some related key security (contrary to this work), but also to prevent invariant subspace attacks, is another interesting question.

Because of place constraints, this extended abstract focused on the main concepts that make LS-and XLS-designs intersting families of ciphers. More detailed specifications and security analysis will be provided in the full paper. A.2 Mysterion L-box

A Specifications of Mysterion's components

C =            
0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1

1 α 3 α 4 α 12 α 8 α 12 α 4 α 3             , C 8 =             1 α 3 α 4 α 12 α 8 α 12 α 4 α 3 α 3 α 13 α 4 α 1 α 2 α 2 α 12
α 12 α 14 α 12 α 14 α 2 α 7 α 5 α 8 α 8 1 α 5 α 14 α 7 α α 2 α 3 α 3 α 14 α 9 α 10 α 10 α 9 α 14 α 3 α 3 α 2 α α 7 α 14 α 5 1 α 8 α 8 α 5 α 7 α 2 α 14 α 12 α 14 α 12

α 12 α 2 α 2 1 α α 4 α 13 α 3             .
C is the companion matrix of the polynomial defined in Section 3.1. C 8 is the underlying matrix of the Mysterion L-box.

A.3 ShiftColumns of Mysterion-256

B Proofs for the bound of the number of active S-boxes

Proof of Theorem 2. The internal state of Mysterion-256 can be seen as a square, since the number of blocks is equal to the number of columns in a block in this case. Therefore, the proof directly results from the Four-Round Propagation Theorem of the AES Rijndael given in [START_REF] Daemen | The wide trail design strategy[END_REF]. That is, the number of active S-boxes over four rounds of Mysterion-256 is lower bounded by the square of the branch number of the L-box, which corresponds to 9 2 = 81 active S-boxes.

Proof of Theorem 1. Contrary to Mysterion-256, we cannot directly use the Four-Round Propagation Theorem of the AES to lower bound the number of active S-boxes in Mysterion-128, since its number of columns is larger than its number of blocks (i.e. the state is no longer a square). However, similar bounds can be deduced from a modified version of the theorem proven in [START_REF] Daemen | The wide trail design strategy[END_REF]. We show in the following how Mysterion-128 can fulfill the hypotheses of this theorem with a simple rearrangement of its operations. For this purpose, we first need to set some definitions and notations. First, a bundle is a 4-bit word and corresponds to a column in the representation of the internal state of Mysterion-128. We denote by L the application of the L-box on each block of the state, which are divided into four independent parts of eight bundles each. We call this partition of the bundles Ξ. Mysterion-128 is a key-alternating block cipher and iteratively applies the same round function, composed of an S-box layer, an L-box layer, a ShiftColumns layer, and key and round constant additions. As the latter do not influence the number of active S-boxes, we will omit them in the following.

Based on this, four rounds of Mysterion-128 can then be written as:

ShiftColumns•L•S•ShiftColumns•L•S•ShiftColumns•L•S•ShiftColumns•L•S.
We next reorganise these operations in order to highlight a particular structure of the linear transformation for 4 rounds, which allows a simpler analysis. More precisely, since ShiftColumns commutes with S, we have the following equivalent definition of four rounds of Mysterion-128: We finally exploit the following theorem from [START_REF] Daemen | The wide trail design strategy[END_REF]:

Theorem 3. For a key alternating block cipher with round tranformations τ a and τ b , the number of active S-boxes of any trail over

τ b • τ a • τ b • τ a
is lower bounded by B(L) × B(L, Ξ), where B(L) is the branch number of the linear transformation L and B(L, Ξ) is the branch number of the linear transformation L with respect to the partition of the bundles Ξ.

The branch number of L is 9 (the L-box of Mysterion is an MDS code [START_REF] Piret | PICARO -A block cipher allowing efficient higher-order side-channel resistance -extended version[END_REF][START_REF] Gérard | Block ciphers that are easier to mask: How far can we go?[END_REF][START_REF] Gilbert | Super-sbox cryptanalysis: Improved attacks for AES-like permutations[END_REF] F 2 4 ). The partition Ξ divide the state into the 4 blocks. We say a block is active when it has at least one active (.i.e non zero) bundle. As the ShiftColumns operation spreads two bundles of each block into other blocks, and as L is MDS, we have that the minimum number of input/output active blocks, therefore the branch number of L with respect to the partition Ξ, is 5. As a result, the number of active S-boxes over four rounds is lower bounded by 9 × 5 = 45.

Fig. 1 .

 1 Fig. 1. An example of invariant subspace attack against one round of Robin.

Fig. 2 .

 2 Fig. 2. 128-bit LS-design vs. 128-bit XLS-design.

  Mysterion-128, with parameters b = 4, s = 4, l = 8, and Mysterion-256, with parameters b = 8, s = 4, l = 8.

Theorem 1 .Theorem 2 .

 12 Four rounds of Mysterion-128 activate at least 45 S-boxes. Four rounds of Mysterion-256 activate at least 81 S-boxes.

Fig. 3 .

 3 Fig. 3. Encryption times for different 128-bit block ciphers in an Atmel AtMega644p.

A. 1

 1 Mysterion S-box Algorithm 3 Class13 S-box, bitslice representation Require: 4 input bits (A, B, C, D) Ensure: 4 output bits such as (a, b, c, d) = S(A, B, C, D) 1: a = A&B; 2: a = a ⊕ C; 3: c = B | C; 4: c = c ⊕ D; 5: d = a&D; 6: d = d ⊕ A; 7: b = c&A; 8: b = b ⊕ B; 9: return (a, b, c, d)

Fig. 4 .

 4 Fig. 4. ShiftColumns of Mysterion-256.

  ShiftColumns•L•ShiftColumns•S•L•S•ShiftColumns•L•ShiftColumns•S•L•S.Thanks to this representation, we easily identify two different transformations τ a = L • S and τ b = L • S, where L = ShiftColumns • L • ShiftColumns. Then four rounds of Mysterion -128 are the alternation of τ a and τ b :τ a • τ b • τ a • τ b .

Figure 5 Fig. 5 .

 55 Figure 5 summarizes our notations and modified representation of Mysterion-128.

Table 1 .

 1 The table for linear characteristics leads to similar recommendations. -256 2 -344 Prob. diff char. for Mysterion-128 2 -180 2 -270 2 -360 Prob. diff char. for Mysterion-256 2 -324 2 -486 2 -648 Max. prob. of differential characteristics for LS-and XLS-design instances.

	Number of rounds	8	12	16
	Prob. diff char. for Robin	2 -128 2 -192 2 -256
	Prob. diff char. for Fantomas	2 -160 2

): Pr char lin (4R) ≤ Pr max lin (S-box) 45 = 2 -45 , Pr char dif f (4R) ≤ Pr max dif f (S-box) 45 = 2 -90 .

And similarly, for the Mysterion-256 instance, we have:

Pr char lin (4R) ≤ Pr max lin (S-box) 81 = 2 -81 , Pr char dif f (4R) ≤ Pr max dif f (S-box) 81 = 2 -162 .

For illustration, Table

1

compares the upper bounds for the maximum probabilities of differential characteristics for Robin, Fantomas and Mysterion. Setting the number of rounds to 12 for Mysterion-128 and 16 for Mysterion-256 leads to very comfortable security margins, and better bounds than for Robin and Fantomas.

As just mentioned, this attack can be applied by finding an invariant subspace for the linear layer as well, in which case the S-box layer will not change the subspace.

More precisely,

ANDs and one OR, which can be masked at the same cost.

Acknowledgements. F.-X. Standaert is a research associate of the Belgian Fund for Scientific Research (FNRS-F.R.S.). This work has been funded in parts by the European Commission through the ERC project 280141 (CRASH).


Rodrick Wallace
email: wallace@nyspi.columbia.edu

Data Rate Theorem perspectives on the contribution of extrinsic risk factors to cancer development

Keywords: chemical exposure, control theory, information theory, social exposure

We explore environmentally-induced tumors in the context of the ongoing conflict between long-evolved cancer control mechanisms and the central flaw of multicellularity, using a number of convergent necessary conditions statistical models based on the Data Rate Theorem linking control and information theories. Multicellular cancer suppression is an inherently unstable dynamic process that can fail through sufficient environmental insult, in particular for humans, involving the synergism of chemical exposures with the chronic inflammation of 'social' exposures that may be seen as accelerated aging.

Introduction

Recent controversy highlights an ongoing debate on the relative importance of environmental and intrinsic factors in the development and progression of malignancy. Thomasetti and Vogelstein (2015) argue that, in most cases, cancer onset is an inevitable consequence of the natural dynamics of stem cell proliferation, and often a matter of 'bad luck'. [START_REF] Wu | Substantial contribution of extrinsic risk factors to cancer development[END_REF] reply that stem cell division per se accounts for minimal rates of cancer in the context of significant environmental insult [START_REF] Ledford | Cancer studies clash[END_REF]. Here, we use necessary conditions asymptotic theorems from control and information theories to construct a set of statistical models of cancer proliferation focused on the central flaw of multicellularity, which [START_REF] Aktipis | Cancer across the tree of life: cooperation and cheating in multicellularity[END_REF] describe as follows:

Multicellularity requires the suppression of cell-level fitness in order to promote organism level fitness... Cancer represents a breakdown of this multicellular cooperation, with cancer cells 'cheating in ways that can have devastating effects for organism level fitness... Effective multicellularity requires not just cooperation among cells but also mechanisms for suppressing conflict that results from mutations that can enhance cell-level fitness at the expense of the organism... In other words, effective multicellularity requires the suppression of somatic cheating to some degree, and the cancer that results from that cheating. [START_REF] Nunney | Lineage selection and the evolution of multistage carcinogenesis[END_REF] further notes that, as animals become larger, cancer control becomes more difficult at a rate about the 4/10 power of the cell count, consequent, in part, on a synergism with increased lifespan. Large animals must then have tissue-specific cancer control mechanisms whose development may constitute a real barrier to their evolution.

We explore a series of control theory models of the suppression of cheating in multicellular organisms based on the Data Rate Theorem (DRT) that links control and information theories in the specific circumstance of inherent system instability [START_REF] Nair | Feedback control under data rate constraints: an overview[END_REF]. Inherently unstable biological systems can respond quickly to environmental or physiological signals and thus may have significant evolutionary advantage under certain powerful selection pressures, as exemplified, in addition to multicellularity itself, by consciousness, blood pressure and gene expression [START_REF] Wallace | Consciousness, crosstalk, and the mereological fallacy: an evolutionary perspective[END_REF].

Control theory has already found a place in the current cancer literature. For example, Schattler and Ledzewicz (2015 Ch 8) explore the [START_REF] Stepanova | Course of the immune reaction during the development of a malignant tumor[END_REF] model of interaction between tumorigenesis and immune surveillance, commenting that

The competitive interaction between tumor cells and the immune system is complex... and... involves an excessively large number of events with the kinetics of the interplay strongly nonlinear and characterized by multi-stability, i.e., persistence of both benign and malignant scenarios. The possible outcome of this interplay is not only constituted by tumor suppression or tumor outbreak, but there exist many intermediate scenarios.

They go on to examine deviations from nonequilibrium steady states using a linearized model in which stability is defined in terms of a matrix eigenstructure having negative eigenvalues, a standard method whose often complicated symmetries are more fully explored by [START_REF] Golubitsky | Genericity, bifurcation and symmetry[END_REF]. Here, via the DRT, we relax the stability conditions and take a more active perspective in which the immune system and other tissue-specific mechanisms [START_REF] Nunney | Lineage selection and the evolution of multistage carcinogenesis[END_REF] exercise ongoing control over the inherent instability of multicellularity in the context of accumulating environmental insult.

Indeed, an emerging strain of opinion on carcinogenesis takes an explicitly systems/network view. As [START_REF] Kreeger | Cancer systems biology: a network modeling perspective[END_REF] put it, Figure 1: Adapted from [START_REF] Kreeger | Cancer systems biology: a network modeling perspective[END_REF]. Environmental context impinges on molecular and genetic regulatory processes to produce malignant phenotypes.

Cancer is now appreciated as not only a highly heterogeneous pathology with respect to cell type and tissue origin but also as a disease involving dysregulation of multiple pathways governing fundamental cell processes such as death, proliferation, differentiation and migration. Thus, the activities of molecular networks that execute metabolic or cytoskeletal processes, or regulate these by signal transduction, are altered in a complex manner by diverse genetic mutations in concert with the environmental context.

Their figure 1, adapted here, schematically illustrates how genetic alterations convolute with environmental context to generate phenotypes, a process in which such context modulates transcriptional, translational and posttranslational processes including epigenetic influences.

A consequence of a systems perspective on cancer biology is the growing understanding that the processes involved are highly dynamic, very subtle, and increasingly defy the standard paradigm of carcinogenesis. As Hlatky and Hahnfeldt (2014) put it, ...[A] vast number of direct observations at the level of tumor progression are showing interactions of cancer cells with themselves and with cells of the host, may not only promote, but also slow, stop, or even reverse a carcinogenesis course... One is confronted with the realization that cancer risk determination from exposures to carcinogenic agents not only requires a multiscale effort to link the various levels at which data are available (from molecular to cellular to tissue to epidemiologic), but that the risk itself is influenced at multiple scales, having substantial population-and tissue-level components... Indeed, as the fundamental study by [START_REF] Folkman | Induction of angiogenesis during the transition from hyperplasia to neoplasia[END_REF] remarks, A distinguishing feature of most pre-neoplastic lesions is their lack of obvious neovascularization, as compared with the resulting neoplasias which are typically highly angiogenic. The 'switch' from the pre-vascular state to the vascularized stage may be followed by an increase in growth rate and metastasis.

Here, we use the DRT to construct a set of relatively simple statistical models describing how environmental and social exposures drive the expression of malignant phenotypes in complex regulatory networks for which suppression is an ongoing interactive process, with constant low levels of malignancy as a 'normal' condition of multicellularity.

As with regression models, more complicated versions are possible, and these can, perhaps, be fitted to data. And as with all such approaches, in addition to insight, scientific dividends lie in the empirical comparison of similar systems under different, or different systems under similar, conditions and dynamics.

The Data Rate Theorem

We assume, as do Schattler and Ledzewicz, that the cancer development/cancer control system has been placed in a nonequilibrium -but, in this case, inherently unstable -steady state kept from large-scale explosive tumor growth by a constant flow of externally-imposed control signals. Sufficiently fine-scale search would, however, always find some positive and fluctuating level of malignancy, in this model.

At first order near that steady state, an n-dimensional vector of system parameters at time t, x t , determines system development at time t+1 according to the relation

x t+1 = Ax t + Stochastic and Control terms (1)
where A is an n × n matrix, and the stochastic and control loop terms are also linear. The essence of the Data Rate Theorem [START_REF] Nair | Feedback control under data rate constraints: an overview[END_REF]) in this case is that the rate control information H needed to prevent explosive instability is determined by the relation

H > log[| det(A u )|] ≡ α 0 (2)
where det is the determinant and A u is the factored-out submatrix of A having eigenvalues ≥ 1. Since the left hand side of Eq. ( 2) is an information measure, the right hand side is interpreted as the rate at which the system generates 'topological information'. Generalizing to more complex structures, for stability the rate of control information must be greater than the rate at which an inherently unstable system generates topological information.

Given the relatively fixed nature -by evolution and individual development -of the immune/cancer interaction network, the source of 'topological information' is the sum total of 'environmental insult', in a large sense, which we write as 'ρ'. Under such insult, the control system responds, and Eq.( 2) can be written as

H(ρ) > f (ρ)α 0 (3)
where f (0)α 0 is to be interpreted as the rate at which the system generates topological information when unperturbed by environmental exposures. What, then, are the functions H(ρ) and f (ρ)?

We can approximate H(ρ) using a Black-Scholes approach [START_REF] Black | The pricing of options and corporate liabilities[END_REF].

The cost of regulation

Take H(ρ) as the control information rate 'cost' of stability at the level of environmental insult ρ. What is the mathematical form of H(ρ) under conditions of volatility i.e., variability in ρ proportional to it? Let

dρ t = g(t, ρ t )dt + bρ t dW t (4)
where dW t is taken as white noise and the function g(t, ρ) will 'fall out' of the calculation on the assumption of certain regularities. Let H(ρ t , t) be the minimum needed incoming rate of control information under the Data Rate Theorem, and expand in ρ using the Ito chain rule [START_REF] Protter | Stochastic Integration and Differential Equations[END_REF])

dH t = [∂H/∂t + g(ρ t , t)∂H/∂ρ + 1 2 b 2 ρ 2 t ∂ 2 H/∂ρ 2 ]dt +[bρ t ∂H/∂ρ]dW t (5)
Define a quantity L as a Legendre transform of the rate H, by convention having the form

L = -H + ρ∂H/∂ρ (6)
Since H is an information index, it is a kind of free energy in the sense of [START_REF] Feynman | Lectures on Computation[END_REF] and L is a classic entropy measure.

Heuristically, replacing dX with ∆X in these expressions and applying Eq.( 5),

∆L = (-∂H/∂t - 1 2 b 2 ρ 2 ∂ 2 H/∂ρ 2 )∆t (7)
As in the classical Black-Scholes model [START_REF] Black | The pricing of options and corporate liabilities[END_REF], the terms in g and dW t 'cancel out', and the effects of noise are subsumed into the Ito correction factor, a regularity assumption making this an exactly solvable but highly approximate model.

The conventional Black-Scholes calculation takes ∆L/∆T ∝ L. Here, at nonequilibrium steady state, we assume ∆L/∆t = ∂H/∂t = 0, so that

- 1 2 b 2 ρ 2 ∂ 2 H/∂ρ 2 = 0 (8)
By inspection,

H = κ 1 ρ + κ 2 (9)
where the κ i are nonnegative constants.

Taking the same level of approximation, we assume f (ρ) in Eq.( 3) can be similarly expressed as κ 3 ρ + κ 4 so that the stability relation becomes

κ 1 ρ + κ 2 κ 3 ρ + κ 4 > α 0 ( 10
)
At low ρ the stability condition is κ 2 /κ 4 > α 0 , and at high ρ it becomes κ 1 /κ 3 > α 0 . If κ 2 /κ 4 κ 1 /κ 3 , then at some intermediate value of ρ the essential inequality may be violated, leading to uncontrolled tumor growth. See figure 2.

A second line of argument leads in a similar direction.

Information bottleneck

A different possible approach to control system dynamics uses the information bottleneck method of [START_REF] Tishby | The information bottleneck method[END_REF]. The underlying conceit is that the control information needed to stabilize an inherently unstable system, which we have written as H, can be used to define an average distortion measure in a rate distortion calculation. This requires an iterated application of the Rate Distortion Theorem (RDT) [START_REF] Cover | Elements of Information Theory, Second Edition[END_REF]) to a control system in which a series of 'control orders' y n = y 1 , ..., y n , having probability p(y n ), is sent, and the outcomes monitored as ŷn = ŷ1 , ..., ŷn . The distortion measure to be associated with the RDT is now the minimum necessary control information for system stability, written as H(y n , ŷn ). We can thus, analogously to the standard RDT, define a new average 'distortion' Ĥ as

Ĥ ≡ y n p(y n )H(y n , ŷn ) ≥ 0 ( 11
)
It then is possible to define a new, iterated, Rate Distortion Function (RDF) R( Ĥ) in a standard manner. The central point of any RDF is that it is convex in the distortion measure, and convexity is a very powerful mathematical condition in describing system dynamics (e.g., [START_REF] Ellis | Entropy, Large Deviations and Statistical Mechanics[END_REF].

For simplicity, we take R to be a Gaussian RDF in Ĥ,

R( Ĥ) = 1/2 log[σ 2 / Ĥ] Ĥ < σ 2 R( Ĥ) = 0 Ĥ ≥ σ 2 (12)
Figure 2: The horizontal line represents the critical limit α 0 . If κ 2 /κ 4 κ 1 /κ 3 , at some intermediate value of accumulated environmental insult ρ the relation (κ 1 ρ + κ 2 )/(κ 3 ρ + κ 4 ) falls below that limit, and malignant growth becomes uncontrolled.

Again following [START_REF] Feynman | Lectures on Computation[END_REF], information must be recognized as a form of free energy and a Rate Distortion Function itself, as the minimum channel capacity needed to achieve a given level of average distortion, can be used to define an 'entropy' as the Legendre transform

S = R( Ĥ) -ĤdR/d Ĥ (13)
Taking Onsager's nonequilibrium thermodynamics perspective (de Groot and Mazur 1984), the dynamics can, in first order, be characterized in terms of the gradients of S, and we invoke an extended analog using the stochastic differential equation [START_REF] Protter | Stochastic Integration and Differential Equations[END_REF])

d Ĥt = [-µdS/d Ĥt -F (ρ)]dt + β Ĥt dW t = [ µ 2 Ĥt -F (ρ)]dt + β Ĥt dW t (14)
where dW t is standard white noise, and F (ρ) is a function of accumulated environmental insult ρ, that, given an essential 'topological factoring' of the cancer/control network, is the only possible determinant of the rate of generation of system 'topological information'. β represents the magnitude of a 'volatility' noise term independent of σ 2 in the definition of R: higher H, higher stochastic jitter.

Applying the Ito chain rule [START_REF] Protter | Stochastic Integration and Differential Equations[END_REF]) to the expectation of Ĥ2 t , it becomes possible to explore the second moment stability of the system (Khashminskii 2012). A simple calculation finds that the expectation for Ĥ2 cannot be a real number unless the discriminant of a quadratic equation is nonnegative, giving a necessary condition for stability as

F (ρ) ≥ β √ µ (15)
We force closure on the model by taking F (ρ) as given by Eq.( 10), so that, again,

κ 1 ρ + κ 2 κ 3 ρ + κ 4 ≥ β √ µ ≡ α 0 (16)
with similar restrictions on the constants κ i for stability.

Other channel forms will have analogous stability limit conditions on ρ as a consequence of the convexity of the RDF. It is of interest to carry the calculation through for the 'real' channel, having R( Ĥ) = σ 2 / Ĥ.

Turbulence

A third line of argument, adapted from the air traffic control model of [START_REF] Hu | Hybrid geodesics as optimal solutions to the collision-free motion planning problem[END_REF], involves geodesic streamline flow in a topological quotient space for cellular and tissue dynamics. Given the inherent instability of multicellularity, 'acceptable' dynamic trajectories can be envisioned as constrained to geodesic streamlines in a large 'biospace' M that have been factored according to a maximum microtumor crossection r. The equivalence class of such streamlines is written as W (r), and the topological quotient space as M/W (r), which may be very large indeed. Deviations from geodesics in this quotient space represent biological trajectories having microtumors with crossection greater than r. Let K t be an appropriate index of the degree of deviation from such an 'acceptable' geodesic trajectory at time t. We can express the dynamics of K t , in first order, by the stochastic differential equation

dK t ≈ aK t dt + σK t dW t ( 17
)
where a, σ ≥ 0 and dW t represents white noise. Applying the Ito chain rule to log[K t ], we obtain

d log[K t ] ≈ (a -σ 2 /2)dt + σdW t (18)
so that, if 2a ≡ α 0 < σ 2 , the expectation E[K] t → 0. Our assertion is that the 'noise' σ 2 is again H(ρ)/f (ρ) from Eq.( 3), since ρ is the only possible index for the generation of topological information by biological instability, and H is the control signal: everything else has been factored out through the construction of geodesics in M/W (r). We again invoke the closure relation of Eq.( 10). The 'characteristic area' method of Wallace (2016 Section 3) can now be used to extend this model to metastatic tumor proliferation along networks of tissues, as opposed to the dynamics of a biochemical regulatory network studied here.

A slightly more sophisticated model might use the product of the characteristic dimension r and its rate of growth, dr/dt, i.e., an index r ∝ dr 2 /dt, leading to an equivalence class W (r) and a quotient topology on M/W (r).

Cognitive symmetry breaking

A deeper approach to the dynamics of cancer regulation is via the 'cognitive paradigm' of [START_REF] Atlan | Immune information, self-organization, and meaning[END_REF], who recognized that the immune response is not simply an automatic reflex, but involves active choice of a particular response to insult from a larger repertoire of those possible to it. Such choice reduces uncertainty in a formal manner, and implies the existence of an information source. See [START_REF] Wallace | Consciousness, crosstalk, and the mereological fallacy: an evolutionary perspective[END_REF][START_REF] Wallace | An Information Approach to Miochondrial Dysfunction: Extending Swerdlow's hypothesis[END_REF] for details.

Given an information source associated with an inherently unstable, rapidfire cognitive cancer control system -characterized as 'dual' to it -an equivalence class algebra can be constructed by choosing different system origin states a 0 and defining the equivalence of two subsequent states at times m, n > 0, written as a m , a n , by the existence of high-probability meaningful paths connecting them to the same origin point. Disjoint partition by equivalence class, essentially similar to orbit equivalence classes in dynamical systems, defines a symmetry groupoid associated with the cognitive process. Groupoids represent generalizations of the group concept in which there is not necessarily a product defined for each possible element pair [START_REF] Weinstein | Groupoids: unifying internal and external symmetry[END_REF]. The simplest example would be a disjoint union of groups.

The equivalence classes define a set of cognitive dual information sources available to the inherently unstable cancer regulation system, creating a large groupoid, with each orbit corresponding to a transitive groupoid whose disjoint union is the full groupoid. Each subgroupoid is associated with its own dual information source, and larger groupoids will have richer dual information sources than smaller.

Let X Gi be the cancer control system's dual information source associated with the groupoid element G i , and let Y be the information source associated with incoming environmental stress, in a large sense See [START_REF] Wallace | Consciousness, crosstalk, and the mereological fallacy: an evolutionary perspective[END_REF][START_REF] Wallace | An Information Approach to Miochondrial Dysfunction: Extending Swerdlow's hypothesis[END_REF] for details of how environmental regularities imply the existence of an environmental information source.

We can construct a Morse Function [START_REF] Pettini | Geometry and Topology in Hamiltonian Dynamics[END_REF] as follows.

Let H(X Gi , Y ) ≡ H Gi be the joint uncertainty of the two information sources. Define a Boltzmann-like pseudoprobability as

P [H Gi ] = exp[-H Gi /κH] j exp[-H Gj /κH] ( 19
)
where κ is an appropriate constant depending on the particular system and its linkages to control signals, and the sum is over the different possible cognitive modes of the full system. A 'free energy' Morse Function F can be defined as

exp[-F/κH] ≡ j exp[-H Gj /κH] (20)
Given the inherent groupoid structure, it is possible to apply an extension of Landau's picture of phase transition [START_REF] Pettini | Geometry and Topology in Hamiltonian Dynamics[END_REF]. In Landau's formulation of spontaneous symmetry breaking, phase transitions driven by temperature changes occur as alteration of system symmetry, with higher energies at higher temperatures being more symmetric. The shift between symmetries is highly punctuated in the temperature index, here the minimum necessary control information rate H under the Data Rate Theorem for unstable control systems. Typically, such arguments involve only a very limited number of possible phases.

Decline in the richness of control information H, or in the ability of that information to influence the system, characterized by κ, can lead to punctuated decline in the complexity of cognitive process possible within the cancer control system, driving it into a ground state collapse in which tumors proliferate beyond the acceptable topological crossection r (or the expanded index r ∝ dr 2 /dt).

The essential feature is the integrated environmental insult ρ. Most of the topology of the inherently unstable multicellular system has been 'factored out' via the construction of geodesics in a topological quotient spaceM/W (r) or M/W (r), so that ρ remains the only possible index of the rate of topological information generation for the DRT. Thus, in Eqs( 19) and ( 20), H is again replaced by the ratio H/f (ρ), where f is a dimensionless monotonic increasing positive function.

For a fixed H, increasing ρ is then equivalent to lowering the 'temperature', and the system passes from high symmetry 'free flow' to different forms of 'crystalline' structure -broken symmetries representing onset of significant tumor growth.

Again, making an exactly-solvable Black-Scholes approximation, the 'cost' of the control information H can, in first order, be expressed in terms of a linear function of ρ and again, in first order, taking f (ρ) ≈ κ 3 ρ + κ 4 > 0, we obtain an effective 'temperature' as

κH(ρ)/f (ρ) ≈ κ 1 ρ + κ 2 κ 3 ρ + κ 4 (21)
If κ 2 /κ 4 κ 1 /κ 3 , accumulated environmental insult will quickly bring the effective 'temperature' below some critical value, triggering collapse into a dysfunctional ground state of tumor proliferation.

Discussion and conclusions

Following Eq.( 10) et seq., at a low level of cumulative environmental insult ρ, the stability condition across a spectrum of mathematical models of tumor proliferation is κ 2 /κ 4 > constant. At a high level, it is asymptotically κ 1 /κ 3 > constant. If κ 2 /κ 4 κ 1 /κ 3 , then, according to figure 2, at some point the cumulative effects of environmental insult may overwhelm the ability of the cancer control system to contain 'normal' conditions of malignancy to an acceptable level, initiating significant tumor growth.

Generalizations of the models might involve better assessment of the functions H(ρ) and f (ρ) in the various levels of DRT argument. Dynamics will be driven both by normal aging and by the deleterious effect of exposure itself on the control network that can be viewed as accelerated aging, increasing the network constant α 0 itself. Similar perspectives can, of course, be applied to a variety of pathological developmental trajectories, for example Alzheimer's disease [START_REF] Wallace | An Information Approach to Miochondrial Dysfunction: Extending Swerdlow's hypothesis[END_REF].

Something much like this has, of course, long been known. For example, [START_REF] Aktipis | Evolutionary foundations for cancer biology[END_REF] write When considering all cancers, the role of mismatch with modern environments is overwhelming. About one-third of cancers are direct complications of tobacco use, and another third are reported to be results of obesity, inactivity or poor diet... In addition, many cancers are caused by radiation, hormone treatments, environmental exposures, and new pathogens. In contrast, only about 5% of cancers are products of hereditary genetic abnormalities. Cancer in modern populations is caused mainly not by the innate inadequacies of our bodies, but by exposure to aspects of modern environments for which our bodies are ill prepared.

Somewhat more generally, however, chemical and, for humans, 'social', exposures, in the context of the mitochondrial burdens of aging, can trigger the chronic inflammation and other mechanisms leading to carcinogenesis (e.g., Wallace 2015 Ch. 8;[START_REF] Wallace | Gene Expression and its Discontents: The social production of chronic disease[END_REF]). An economically sustainable public health attack, as opposed to inordinantly expensive case-by-case disease treatment, involves reduction of such exposures at the population level, most typically through improvements in living and working conditions.