Julien Destombes
email: julien.destombes@lirmm.fr

Andrei Romashchenko
email: andrei.romashchenko@lirmm.fr

Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts

Keywords: 2012 ACM Subject Classification Mathematics of computing → Information theory; Mathematics of computing → Combinatorics Sofic shifts, Block complexity, Kolmogorov complexity

We suggest necessary conditions of soficness of multidimensional shifts formulated in terms of resource-bounded Kolmogorov complexity. Using this technique we provide examples of effective and non-sofic shifts on Z 2 with very low block complexity: the number of globally admissible patterns of size n × n grows only as a polynomial in n.

Introduction

Symbolic dynamics originally appeared in mathematics as a branch of the theory of dynamical systems that studies smooth or topological dynamical systems by discretizing the underlying space. Since the late 1930s, symbolic dynamics became an independent field of research, see [START_REF] Morse | Symbolic dynamics[END_REF][START_REF] Morse | Symbolic dynamics II: Sturmian trajectories[END_REF]. A classical dynamical system is a space (of states) S with a function F acting on this space; this function represents the "evolution rule," i.e., the time dependence of a configuration in the space. The central notion of the theory of dynamical systems is a trajectory -a sequence of configurations obtained by iterating the evolution rules,

x, F (x), F (F (x)), . . . , F (n) (x), . . .

In symbolic dynamics the space of states reduces to a finite set (an alphabet). The trajectories are represented by infinite (or bi-infinite) sequences of letters over this alphabet, and the "evolution rule" is the shift operator acting on these sequences. Symbolic dynamics focuses on the shift spaces -the sets of bi-infinite sequences of letters (over a finite alphabet) that are defined by a shift-invariant constraint on the factors of finite length. More precisely, a shift over an alphabet Σ is a subset of bi-infinite sequences over Σ that is translation invariant and closed in the natural topology of the Cantor space. Every shift can be defined in terms of forbidden finite patterns: we fix a set of (finite) words F and say that a configuration (a bi-infinite sequence) belongs to the corresponding shift S F if and only if it does not contain any factor from F.

Obviously, the properties of shifts heavily depend on the corresponding set of forbidden patterns. The following three large classes of shifts play an important role in symbolic dynamics and computability theory:

shifts of finite type (SFT), which are defined by a finite set of forbidden finite patterns; sofic shifts (introduced in [16]), where the set of forbidden finite patterns is a regular language; effective (or effectively closed) shifts, which are defined by a computable set of forbidden finite patterns. These three classes are different: [the SFTs] [the sofic shifts] [the effective shifts].

The sofic shifts can be equivalently defined as the coordinate-wise projections of configurations from an SFT: Definition 1. A shift S over an alphabet Σ is sofic if there is an SFT S over an alphabet Σ and a mapping π : Σ → Σ, such that S consists of the coordinate-wise projections (. . . π(y -1 )π(y 0 )π(y 1 )π(y 2 ) . . .) of all configurations (. . . y -1 y 0 y 1 y 2 . . .) from S .

There is a simple characterization of soficness. Let us say that two words w 1 , w 2 are equivalent in a shift S, if exactly the same half-infinite configurations occur in S immediately to the right of w 1 and to the right of w 2 . A shift is sofic if and only if the finite patterns in this shift are subdivided in a finite number of equivalence classes (see [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF]Theorem 3.2.10]). Loosely speaking, when we read a configuration from the left to the right and verify that it belongs to a sofic shift, we need to keep in mind only a finite information.

The SFTs and even the sofic shifts are rather restrictive classes of shifts with several very special properties. Not surprisingly, many important examples of effective shifts are not sofic. Non-soficness of a shift is usually proved with some version of the pumping lemma from automata theory.

Multidimensional shifts

The formalism of shifts can be naturally extended to the grids Z d for d > 1. A shift on Z d (over a finite alphabet Σ) is defined as a set of d-dimensional configurations f : Z d → Σ that are (i) translation-invariant (under translations in all directions) and (ii) closed in Cantor's topology. Similar to the one-dimensional case, the shifts can be defined in terms of forbidden finite patterns.

The definitions of the effective shifts (the set of forbidden patterns is computable) and of the SFTs (the set of forbidden patterns is finite) apply to the multidimensional shift spaces directly, without any revision. The sofic shifts on Z d are defined as in Definition 1 above (as the coordinate-wise projections of SFTs).

For multidimensional shifts spaces, the classes of the effective shifts, the sofic shifts, and the SFTs remain distinct, though the difference between these classes is more elusive than in the one-dimensional case. In this paper we discuss the tools that help to reveal the reasons why one or another effective multidimensional shift is not sofic.

The class of sofic shifts in dimension d ≥ 2 is surprisingly wide. Besides many simple and natural examples, there are shifts whose soficness follow from rather subtle considerations. For instance, S. Mozes showed that the shift generated by (a natural class of) non deterministic multidimensional substitutions systems are sofic [START_REF] Mozes | Tilings, substitution systems and dynamical systems generated by them[END_REF]. L. B. Westrick proved that the twodimensional shift on the alphabet {0, 1} whose configurations consist of squares of 1s of pairwise different sizes on a background of 0s, is sofic; moreover, any effectively closed subshift of this shift is also sofic [17].

On the other hand, there are several examples of effective multidimensional shifts that are known to be non-sofic. In what follows we briefly discuss two of them.

Example 2 (the mirror shift). One of the standard examples of a non-sofic shift is the shift of mirror-symmetric configurations on Z 2 . Let Σ be the alphabet with three letters (e.g., black, white, and red), and the configurations of the shift are all black-and-white configurations (without any red cell) and the configurations with an infinite horizontal line of red cells and symmetric black-and-white half-planes above and below this line, see Fig. 1.

It is easy to see that this shift is effective (the forbidden patterns are those where the red cells are not aligned, and those where the areas above and below the horizontal red line are not symmetric). At the same time, this shift is not sofic. The intuitive explanation of this fact is as follows. Let us focus on a pair of symmetric patterns of size n × n in black and white, above and below the horizontal red line (see the blue squares in Fig. 1). To make sure that the configuration belongs to the shift, we must "compare" these two patterns with each other. To this end, we need to transmit the information about a pattern of size n 2 through its border line (of length O(n)). However, in a sofic shift, the "information flow" across a contour of length O(n) is bounded by O(n) bits, and this contradiction implies non-soficness. For a more formal argument see, e.g. [START_REF] Aubrun | About the Domino Problem for Subshifts on Groups. Sequences, Groups, and Number Theory[END_REF] and [START_REF] Jeandel | Propriétés structurelles et calculatoires des pavages[END_REF], or a similar example [START_REF] Kass | A sufficient condition for non-soficness of higher-dimensional subshifts[END_REF]Example 2.4].

Example 3 (the high complexity shift). Let S be the set of all binary configurations on Z 2 where for each n × n pattern P its Kolmogorov complexity is quadratic, C(P ) = Ω(n 2 ). Technically, this means that no globally admissible pattern can be produced by a program of size below cn 2 , for some factor c > 0 (see the formal definition of Kolmogorov complexity below).

This shift is obviously effective: we can algorithmically enumerate the patterns whose Kolmogorov complexity is below the specified threshold. However, this shift is not sofic. This follows from two facts (proven in [START_REF] Durand | Complex tilings[END_REF]):

(i) For some c < 1, the shift defined above is not empty.

(ii) In every non-empty sofic shift on Z 2 , there is a configuration where the Kolmogorov complexity of each n × n pattern is bounded by O(n).

23:4 An Obstacle to Soficness

Note that the non-sofic shifts in the two examples above have positive entropy (the number of globally admissible patterns of size n × n grows as 2 Ω(n 2 ) ). This is not surprising: the proofs of non-soficness of these shifts use the intuition about the information flows (super-linear amount of information cannot flow through a linear contour). This type of argument can be adapted for several shifts where the number of globally admissible patterns of size n×n grows slower than 2 Ω(n 2 ) but still faster than 2 O(n) (see, e.g. [15, Proposition 15]). As it was noticed in [17], "all examples known to the author of effectively closed shifts which are not sofic were obtained by in some sense allowing elements to pack too much important information into a small area."

This type of argument was formalized as rather general sufficient conditions of nonsoficness in [START_REF] Pavlov | A class of nonsofic multidimensional shift spaces[END_REF] and [START_REF] Kass | A sufficient condition for non-soficness of higher-dimensional subshifts[END_REF]. The theorems by Kass and Madden ([8, Theorem 3.2.10]) and Pavlov ([13, Theorem 1.1]) apply only to the two-dimensional shifts where the number of globally admissible n × n patterns is greater than 2 O(n) . However, there is no reason to think that this condition is necessary for non-soficness (see, e.g. the discussion in [4, Section 1.2.2]). It is instructive to observe that non-effective non-sofic shifts can have very low block complexity [START_REF] Kass | A sufficient condition for non-soficness of higher-dimensional subshifts[END_REF][START_REF] Ormes | Extender sets and multidimensional subshifts[END_REF].

In this paper we extend the usual approach to the proof of non-soficness. We show that a shift cannot be sofic if the essential information contained in an n × n pattern cannot be compressed to the size O(n) in bounded time.

The intuition behind our argument is similar to those used in [START_REF] Durand | Complex tilings[END_REF] and [START_REF] Kass | A sufficient condition for non-soficness of higher-dimensional subshifts[END_REF] but with the idea of compression with bounded computational resources. This approach applies to several shifts with very low block complexity: we cannot "communicate" the essential information across a contour not because this information is too large, but since we do not have enough time and space to compress it. In particular, we provide examples of non-sofic effective shifts with only polynomial block complexity (and thus zero entropy). Remark 4. A standard and straightforward approach to the measure of the "information flow through the border line of a pattern" uses the notion of extender. Let S be a shift and P be a globally admissible pattern for this shift. The extender of P in S is the set of all configurations Q completing P to a valid configuration of S (in particular, the support of Q should be the complement of the support of P ).

Let S be a shift on Z 2 ; denote by N k the number of different extenders for the patterns with a support of size k × k. (Several patterns can share one and the same extender, so the number of extenders might be much less than the number of globally admissible patterns of this size). It seems natural to interpret log N k as "the information flowing going through the border line" of a k × k pattern.

However, this interpretation is deceptive. In a sofic shift the value of log N k can grow much faster the length of the border line of the pattern ( [START_REF] Kass | A sufficient condition for non-soficness of higher-dimensional subshifts[END_REF] attributes this observation to unpublished works of C. Hoffman, A. Quas, and R. Pavlov). In fact, for a sofic shift on Z 2 , the value of log N k can grow even as Ω(k 2 ). Therefore, we cannot use the asymptotic of log N k to prove non-soficness of a multi-dimensional shift. This why we need a subtler implementation of the intuition of "information flows" in the sofic shifts.

The rest of the paper is organized as follows. After recalling the main definitions of the theory of Kolmogorov in the second section, we prove in the third one our main result. In the last section we elaborate our technique to a more general setting; in particular, we show that an argument from [START_REF] Kass | A sufficient condition for non-soficness of higher-dimensional subshifts[END_REF] (a proof of non-soficness with the method of union-increasing sequences of extenders) can be explained in the language of Kolmogorov complexity.

Preliminaries

Kolmogorov complexity

In this section we recall the main definitions of the theory of Kolmogorov complexity. Let U be a (partial) computable function. The complexity of x with respect to the description method U is defined as C U (x) := min{ |p| :

U (p) = x }. If there is no p such that U (p) = x, we assume that C U (x) = ∞.
Here U is understood as a programming language; p is a program that prints x; the complexity of x is the length of (one of) the shortest programs p that generate x (on the empty input).

The obvious problem with this definition is its dependence on U . The theory of Kolmogorov complexity becomes possible due to the invariance theorem: Theorem 5 (Kolmogorov [6]). There exists a computable function U such that for any other computable function V there is a constant c such that

C U (x) ≤ C V (x) + c for all x.
This U is called an optimal description method. We fix an optimal U and in what follows omit the subscript in C U (x). The value C(x) is called the (plain) Kolmogorov complexity of x.

In a similar way, we define Kolmogorov complexity in terms of programs with bounded resources (the time of computation). Let U be a Turing machine; we define the Kolmogorov complexity C t U (x) as the length of the shortest p such that U (p) produces x in at most t steps. There exists an optimal description method U in the following sense: for every Turing machine V we have C 1). For multi-tape Turing machines a slightly stronger statement can be proven: Theorem 6 (see [START_REF] Li | An introduction to Kolmogorov complexity and its applications[END_REF]; the proof uses the simulation technique from [START_REF] Hennie | Two-tape simulation of multitape Turing machines[END_REF]). There exists an optimal description method (multi-tape Turing machine) U in the following sense: for every multi-tape Turing machine V there exists a constant c such that

poly(t) U (x) ≤ C t V (x) + O(
C ct log t U (x) ≤ C t V (x) + c for all strings x.
We fix such a machine U , and in the sequel use for the resource-bounded version of Kolmogorov complexity the notation C t (x) instead of C t U (x). Without loss of generality we may assume that C(x) ≤ C t (x) for all x and for all t.

We fix a computable enumeration of finite patterns (over a finite alphabet) that assigns a binary string (a code) to each pattern in dimension two. In the sequel we take the liberty of talking about Kolmogorov complexity of finite patterns in dimension two (assuming the Kolmogorov complexity of the codes of these patterns).

Shift spaces

In this paper we focus on two-dimensional shifts, though all arguments can be extended to the shifts on Z d for all d ≥ 2. A (finite) pattern on Z 2 over a finite alphabet Σ is a mapping from a (finite) subset of Z 2 to Σ; the domain of this mapping is the support of the pattern. Sometimes a pattern P with a support A is called a coloring of A (the "colors" are letter from Σ).

For a shift S, we say that a pattern P is globally admissible, if P is a restriction of a configuration from S to some finite support. For a shift of finite type determined by a set of forbidden patterns F, we say that a pattern is locally admissible if it contains no forbidden patterns from F.

The block complexity of a shift is a function that gives for each integer n > 0 the number of globally admissible patterns of size n × n (patterns with support {1, . . . , n} 2 ) in this shift.

S TA C S 2 0 1 9

23:6 An Obstacle to Soficness

If a sofic shift S is a coordinate-wise projection of configurations from Ŝ, we say that Ŝ is a covering of S. Every sofic shift has a covering SFT such that the supports of all forbidden patterns in this SFT are pairs of neighboring cells (see, e.g. [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF]).

High resource-bounded Kolmogorov complexity is compatible with low block complexity

The following theorem was proven implicitly in [START_REF] Durand | Complex tilings[END_REF]:

Theorem 7.
In every non-empty sofic shift S there exists a configuration x such that for all n × n-patterns P in x, we have

C T (n) (P ) = O(n) for a time threshold T (n) = 2 O(n 2 ) .
In [START_REF] Durand | Complex tilings[END_REF] a weaker version of this theorem is stated: it is claimed only that the plain complexity of n × n patterns is O(n). However, the argument from [START_REF] Durand | Complex tilings[END_REF] implies a bound for a resourcebounded version of Kolmogorov complexity. For the sake of self-containedness, we provide a proof of this theorem in the full version of this paper. Theorem 8. For every > 0 and for every computable T (n) there exists an effective shift on Z 2 such that for every n and for every globally admissible pattern P of size n × n, we have that (i) C(P ) = O(log n), and

(ii) C T (n) (P ) = Ω(n 2-).
Theorem 8 is proven is the full version of the paper. In what follows we prove a slightly weaker version of this theorem, which is nevertheless strong enough for our main applications:

Theorem 8 . For every computable T (n) there exists an effective shift on Z 2 such that (i) for every n and for every globally admissible pattern P of size n × n, we have C(P ) = O(log n), and (ii) for infinitely many n and for every globally admissible pattern P of size n × n, we have that C T (n) (P ) = Ω(n 1.5 ).

From Theorem 7 and Theorem 8 we deduce the following corollary:

Corollary 9.
There exists an effective non-sofic shift on Z 2 with block complexity poly(n), i.e., with ≤ poly(n) globally admissible blocks of size n × n.

Proof. We take the shift from Theorem 8 assuming that the threshold T (n) is much greater than 2 Ω(n 2 ) (e.g., we can let T (n) = 2 n 3 ). On the one hand, property (ii) of Theorem 8 and Theorem 7 guarantee that this shift is not sofic. On the other hand, property (i) of Theorem 8 implies that the number of globally admissible blocks of size n × n is not greater than 2 O(log n) . Remark 10. Our proof of Theorem 8 implies a stronger bound than property (i). In fact, instead of the bound C(P ) = O(log n) we can prove that for every globally admissible n × n pattern P in this shift,

C T (n) (P ) ≤ λ log n, ( 1
)
where λ is a (large enough) constant and T (n) is a (large enough) computable function of n.

The constant λ and the threshold T (n) can be defined quite explicitly given T (n) and .

When T (n) (compatible with given and T (n)) is chosen, we can define another shift S T, that consists of the configurations where all n × n patterns P satisfy (1). The shift from Theorem 8 is a proper subshift of S T, . Besides all configurations from Theorem 8, the shift S T, contains also configurations with patterns of very low time bounded complexity (e.g., the configuration with all 0s and the configuration with all 1s). In the next section we use this shift S T, to construct some other examples of effective non-sofic shifts.

Proof of Theorem 8 . In this proof we construct the required shift explicitly. Let us fix a sequence (n i ) where n 0 is a large enough integer number, and

n i+1 := (n 0 • . . . • n i ) c for i = 0, 1, 2, . . . , (2)
where c ≥ 3 is a constant. We set

N i := n 0 • . . . • n i .
In what follows we construct for each i a pair of standard binary patterns

Q 0 i and Q 1 i of size N i × N i such that the plain Kolmogorov complexities of the standard patterns C(Q 0 i ) and C(Q 1 i ) are not greater than O(log N i ), and the resource-bounded Kolmogorov complexities C T (Ni) (Q 0 i ) and C T (Ni) (Q 1 i ) are not less than Ω(N 1.5 i ). The construction is hierarchical: both Q 0 i and Q 1 i are defined as n i × n i matrices composed of patterns Q 0 i-1 and Q 1 i-1 ;
for each i the blocks Q 0 i and Q 1 i are bitwise inversions of each other.

When the standard patterns Q 0 i and Q 1 i are constructed for all i, we define the shift as the closure of these patterns: we say that a finite pattern is globally admissible if and only if it appears in some standard pattern Q j i or at least in a 2 × 2-block composed of Q 0 i and Q 1 i (for some i).

Remark 11. Due to the hierarchical structure of the standard patterns, we can guarantee that every globally admissible pattern P of size N i × N i appears in a 2 × 2-block composed of Q 0 i and Q 1 i (no need to try the blocks Q j s for s > i). Since the construction of Q j i is explicit, the resulting shift is effective. Properties (i) and (ii) of the theorem will follow from the properties of the standard patterns.

In what follows we explain an inductive construction of Q 0 i and Q 1 i . Let Q 0 0 and Q 0 1 be the squares composed of only 0s and only 1s respectively. Further, for every i we take the lexicographically first binary matrix R i of size n i × n i such that

C ti (R i ) ≥ n 2 i (3)
(the time bound t i is fixed in the sequel). We claim that such a matrix exists. Indeed, there exists a matrix of size n i × n i that is incompressible in the sense of the plain Kolmogorov complexity. The resource-bounded Kolmogorov complexity of a matrix can be only greater than the plain complexity. Therefore, there exists at least one matrix satisfying (3). If t i is a computable function of i, then given i we can find R i algorithmically. Now we substitute in R i instead of each zero and one entry the copies of

Q 0 i-1 and Q 1 i-1
respectively, e.g.,

R i =       0 0 0 0 1 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 0 1 0 1 0       =⇒ Q 0 i :=        Q 0 i-1 Q 0 i-1 Q 0 i-1 Q 0 i-1 Q 1 i-1 Q 0 i-1 Q 1 i-1 Q 0 i-1 Q 0 i-1 Q 1 i-1 Q 1 i-1 Q 1 i-1 Q 1 i-1 Q 1 i-1 Q 0 i-1 Q 0 i-1 Q 1 i-1 Q 1 i-1 Q 0 i-1 Q 0 i-1 Q 0 i-1 Q 1 i-1 Q 0 i-1 Q 1 i-1 Q 0 i-1       
The resulting matrix (of size Claim 12. Assuming that t i t i (in what follows we discuss the choice of t i in more detail) we have

N i × N i ) is denoted Q 0 i . Matrix Q 1 i is defined as the bitwise inversion of Q 0 i .

S TA C S

C t i (Q 0 i ) = Ω(N 1.5 i ) and C t i (Q 1 i ) = Ω(N 1.5 i ).
Proof of Claim 12. Given Q j i (for j = 0, 1) we can retrieve the matrix R i (this retrieval can be implemented in polynomial time). Therefore, for every time bound t

C t+poly(Ni) (R i ) ≤ C t (Q j i ) + O(1).
Therefore, if t i > t i + poly(N i ) then

n 2 i ≤ C ti (R i ) ≤ C t i (Q j i ).
It remains to observe that our choice of parameters in (2) with c ≥ 3 implies n

1/2 i ≥ (n 0 • . . . • n i-1 )
3/2 , and therefore

n 2 i ≥ (n 0 • . . . • n i ) 1.5 = (N i ) 1.5 .
Thus, we obtain

C t i (Q j i ) ≥ (N i ) 1.5 -O(1)
, and the claim is proven.

Remark 13. By choosing a larger constant c in (2), we can achieve a lower bound C t i (Q j i ) = Ω(n 2-) for any > 0.

Claim 14. For every globally admissible pattern P of size N i × N i (and not only for the standard patterns, as it was in Claim 1) its time-bounded Kolmogorov complexity C T (Ni) (P ) is Ω(n 1.5 ) (assuming that T (N i ) t i ).

Proof of Claim 14. If a pattern P of size N i × N i is globally admissible then it is covered by a quadruple of standard patterns of rank i, see Remark 11 on p 7 above. Then P can be divided into four rectangles which are "corners" of standard patterns of rank i, see Fig. 2 (a). Since the standard blocks Q 0 i and Q 1 i are the inversions of each other, these four "corners" (with a bitwise inversion if necessary) form together the entire standard pattern, as shown in Fig. 2 (b). Therefore, we can reconstruct Q j i from P given (a) the position of P with respect to the grid of standard blocks (this involves O(log N i ) bits) and (b) the four bits identifying the standard blocks covering P (we need to know which of them is a copy of Q 0 i and which one is a copy of Q 1 i ).

The retrieval of Q j i from P requires only poly(N i ) steps of computation (in addition to the time we need to produce P ). Now the claim follows from the bound for the resource-bounded Kolmogorov complexity of the standard patterns Q 0 i and

Q 1 i . Claim 15. For every k × k-pattern in Q 0 i or Q 1 i , its plain Kolmogorov complexity is at most O(log k).
Proof of Claim 15. First of all, we observe that the standard patterns

Q 0 i or Q 1 i can be computed given i. Therefore, C(Q 0 i ) = O(log i) and C(Q 1 i ) = O(log i). Every globally admissible k × k-pattern is covered by at most four standard patterns Q 0 i or Q 1 i with N i-1 < k ≤ N i ,
see Remark 11 on p. 7. Therefore, to obtain a globally admissible pattern P of size k × k we need to produce a quadruple of standard patterns of size N i × N i and then to specify the position of P with respect to the grid of standard blocks. This description consists of only O(log N i ) bits, and we conclude that C(P ) = O(log k).

Given a computable threshold T (N i ), we choose a suitable t i T (N i ) and then a suitable t i t i . The theorem follows from Claim 14 and Claim 15.

Remark 16. For all large enough i, the incompressible pattern R i constructed in the proof of Theorem 8 contains copies of all 2 4 binary patterns of size 2 × 2. Therefore, we can guarantee that every standard block Q j i contains all globally admissible patterns of size N i-1 × N i-1 . It follows that the shift constructed in Theorem 8 is transitive and even minimal.

There exists a non-empty effective shift on Z 2 where the Kolmogorov complexity of all n × n patterns is Ω(n 2 ) (see [START_REF] Durand | Complex tilings[END_REF] and [14]). So a natural question arises: can we improve Theorem 8 and strengthen condition (ii) to C T (n) (P ) = Ω(n 2 )? The answer is negative: we cannot achieve the resource bounded complexity Ω(n 2 ), even with a much weaker version of property (i) for the plain complexity: Proposition 17. For all large enough time bounds T (n), there is no shift on Z 2 such that (i) for every globally admissible pattern P of size n × n, we have that C(P ) = o(n 2 ), and (ii) for infinitely many n and for every globally admissible pattern P of size n × n, we have that C T (n) (P ) = Ω(n 2 ).

Proof. Assume for the sake of contradiction that such a shift exists. For every k, the number of globally admissible k × k patterns in this shift is not greater than

L k ≤ 2 o(k 2 ) 2 k 2 .
Therefore, for any N , every globally admissible pattern P of size (N k) × (N k) can be specified by the list of all globally admissible patterns of size k × k (which requires L k • k 2 bits), by an array of N × N indices of k × k blocks that constitute P (which requires N 2 • log L k bits). Clearly, P can be reconstructed from such a description in polynomial time. It follows that

C poly(N k) (P ) ≤ 2 o(k 2 ) • k 2 + N 2 • o(k 2 ). For N 2 o(k 2 ) this bound contradicts the condition C T (N k) (P ) = Ω (N k) 2 .

S TA C S 2 0 1 9 Epitomes

The technique from Section 3 does not apply to the shifts that contain very simple configurations (with low resource-bounded Kolmogorov complexity of all patterns). In particular, it does not apply to Example 2 from Introduction. In this section we propose a different technique (also based on resource-bounded Kolmogorov complexity) that helps to handle these examples. The intuitive idea behind this technique is as follows: we try to capture the "essential" information in each pattern (discarding irrelevant data) and then measure the resource-bounded Kolmogorov complexity of an "epitome" of this essential information.

Let us fix some notation. We denote by B n the set {0, . . . , n -1} 2 ⊂ Z 2 and by F n its complement, F n := Z 2 \ B n . We say that two patterns with disjoint supports are compatible (for a shift S) if the union of these patterns is globally admissible in S. In particular, a finite pattern P with support B n and an infinite pattern R with support F n are compatible, if the union of these patterns is a valid configuration of the shift.

Plain epitomes

Definition 18. We say that a family of functions

E n : [pattern of size n × n] → [binary string]
is a family of epitomes for a shift S, if for every globally admissible pattern P with support B n there exists a pattern R on F n compatible with P such that for all patterns P with support B n compatible with R, we have E n (P ) = E n (P ) (i.e., the pattern R on the complement of B n determines the E n -epitome of the pattern on B n ). We say that a family of epitomes is uniformly computable if there is an algorithm (one algorithm for all n) that computes the mappings E n . If, in addition, E n are computable in time 2 O(n 2 ) , we say that this family of epitomes is exp-time computable.

Proposition 19. For every sofic shift with an exp-time computable family of epitomes E n , for every globally admissible pattern

P of size n × n, we have C T (n) (E n (P )) = O(n) for a time threshold T (n) = 2 O(n 2 ) .
Remark 20. If patterns P 1 , . . . , P m with support B n have pairwise distinct epitomes, then these patterns have a union-increasing sequence of extenders in the sense of [START_REF] Kass | A sufficient condition for non-soficness of higher-dimensional subshifts[END_REF]. Thus, a version of Proposition 19 with the plain (non time bounded) Kolmogorov complexity is a special case of [START_REF] Kass | A sufficient condition for non-soficness of higher-dimensional subshifts[END_REF]Theorem 2.3].

Proof. Assume S is a sofic shift with a covering SFT Ŝ (S is a coordinate-wise π-projection of Ŝ). Let P be a pattern with support B n in S and R be the pattern on the complement of B n that enforces the value of the E n -epitome of P (as specified in Definition 18). Denote by y a configuration in Ŝ whose π-projection gives the union of P and R. Let Q be a pattern of size n × n in y such that P is a coordinate-wise projection of Q, see Fig. 3. Denote by ∂Q the border of Q.

We assume that the local constraints in Ŝ involve only pairs of neighboring nodes in Z 2 . Then, every locally admissible pattern Q of size n × n that is compatible with the border ∂Q, must be compatible with the rest of configuration y. Therefore, the π-projections of these Q are compatible with R. Thus, the E n -epitomes of the projections of these Q must be equal to the E n -epitome of P . It follows that E n (P ) can be computed in time 2 O(n 2 ) given only the coloring of the border line ∂Q: we use the brute-force search to find one Q computable with this border, apply projection π, and then compute the epitome. Observe that the computed projection π(Q ) may be different from P , but the epitome must coincide with the epitome of P . Since the size of ∂Q is linear in n, we conclude that C 2 O(n 2 ) (P ) = O(n).

Proposition 19 gives a necessary condition for soficness. To prove that a shift is not sofic, we need to provide an exp-time computable family of epitomes with high resource-bounded Kolmogorov complexities. In what follows we discuss a simple application of this technique.

Example 2 revisited

Let S be the shift from Example 2 in the Introduction (the mirror-symmetric configurations). For this example we can define epitome functions E n as follows:

if an n × n pattern P contains only black and white letters, then E n (P ) maps it to a binary string of length n 2 that identifies P uniquely (roughly speaking, E n does not compress the patterns in black and white); all patterns with red letters are mapped to the empty string. It is not hard to see that E n is an exp-time computable family of epitomes for this shift (since a configuration below the red line determines all black-and-white patterns above this line). Since for some patterns of size n × n we have C(P ) ≥ n 2 (i.e., even the plain Kolmogorov complexity of P is super-linear), we can apply Proposition 19 and conclude that the shift is not sofic.

Example 2 with low plain Kolmogorov complexity

Let us consider a subshift of S: we still admit only symmetric configurations, but we now allow only those n × n patterns P in black and white that are globally admissible for the shift S T, defined in Remark 10 on p. 6, assuming T (n) = 2 n 3 . (We have chosen the time threshold so that T (n)

2 O(n 2 ) .) A typical configuration of this shift looks as follows: there is an infinite horizontal line in red, and the symmetric half-planes above and below this line are areas in black and white, with n × n patterns P such that C T (n) (P ) = O(log n).

The new shift is effective, and the number of globally admissible patterns is 2 O(log n) = poly(n). Due to Theorem 8 know that some n × n patterns in this shift satisfy the condition C 2 n 3 (P ) = Ω(n 2-).

S TA C S 2 0 1 9

23:12 An Obstacle to Soficness

We cannot apply Theorem 8 directly and conclude that the new shift is non-sofic. Indeed, this shift also admits patterns with very low time-bounded complexity. For example, the shift admits the configuration with an infinite horizontal line in red and only white cells above and below this line.

Note that the functions E n defined above provide for this shift an exp-time computable family of epitomes. Since for some (though not for all) n × n patterns P we have

C 2 n 3 (E n (P )) = Ω(n 2-),
it follows from Proposition 19 that the shift is not sofic.

Ordered epitomes

The argument based on Definition 18 does not apply to [ We say that a family of ordered epitomes is uniformly computable if there is an algorithm (one algorithm for all n) that computes the relations ≤ n and the mappings E n . If, moreover, E n and ≤ n are computable in time 2 O(n 2 ) , we say that this family of ordered epitomes is exp-time computable.

Remark 22. When we say that a partial function is computable (or computable in bounded time), we assume that its domain is decidable (respectively, decidable in bounded time). Thus, for an exp-time computable family of epitomes we can decide effectively whether E n (x) is defined.

Definition 18 can be viewed as a special case of Definition 21. If E n is a family of exp-time computable epitomes in the sense of Definition 18 and ≤ n is an arbitrary effectively computable order on the E n -epitomes, then (E n , ≤ n ) is an exp-time computable family of ordered epitomes in the sense of Definition 21 (in Definition 18, the neighborhood R enforces the exact value of E n (P ) over all P compatible with R, while in Definition 21 we need to enforce only the maximum of E n (P )).

Proposition 23. For every sofic shift with an exp-time computable ordered family of epitomes (E n , ≤ n ), for every globally admissible pattern P of size n × n, C T (n) (E n (P )) = O(n) for a time threshold T (n) = 2 O(n 2 ) . interfere with the red stripes in lines 3n, 3n-1, . . . , 3n-i, since this black stripe is too short to form a forbidden pattern together with any of these red stripes; on the other hand, the black cells of the i-th line cannot interfere with the red stripes in lines 3n-i-1, 3n-i-2, . . . , 2n+1, since those red stripes are too short.

Claim 28. The constructed pattern R is compatible only with simple patterns P such that E n (P ) ≤ n E n (P ).

Proof of Claim 28. If R is compatible with an n × n pattern P , the profile of P is not determined uniquely. In fact, R can be compatible with simple patterns P whose profiles are strictly less than the profile of P (in each row of P the number of black cells must be not greater than the number of black cells in the corresponding row of P ), see Fig. 6 below. On the other hand, if at least one row of P contains more black cells that the same row in P , than P and R are incompatible, i.e., the joint of P and R contains a forbidden pattern, as shown in Fig. 7.

The lemma follows from Claim 27 and Claim 28. For a more detailed argument we refer the reader to [START_REF] Kass | A sufficient condition for non-soficness of higher-dimensional subshifts[END_REF].

Remark 29. In the construction discussed above, pattern R does not determine uniquely the epitomes of P compatible with R (these epitomes can be different, though they must be not greater than the epitome of the initial pattern P ). This is why we cannot apply Proposition 19, and we have to employ the extended definition of partial epitomes.

To prove the proposition, it remains to observe that for every n there are (n + 1) n simple patterns of size n × n (in each row of a simple pattern the frontier between black and white areas varies between 0 and n). Therefore, for some simple patterns P of size n × n the Kolmogorov complexity of their profile is greater than n log(n + 1), i.e., even the plain Kolmogorov complexity C(P ) is super-linear. We apply Proposition 23 and conclude that the shift is not sofic.

this n × n pattern P is compatible with the neighborhood Open Problem 2. The shift in Example 24 has positive entropy, and in the argument discussed above we could employ the definition of uniformly computable (but not exp-time computable) ordered epitomes. It would be interesting to suggest a natural example of an effective (but non-sofic) shift where the technique of exp-time computable ordered epitomes is valid while uniformly computable but not exp-time computable ordered epitomes do not apply.

Figure 1 A

 1 Figure1A configuration with mirror symmetry with respect to the horizontal red line. The blue squares select two symmetric black-and-white patterns.

Figure 2 A

 2 Figure 2 A pattern of size N k × N k (shown in gray in fig. (a)) covered by a quadruple of standard blocks of the same size contains enough information to reconstruct a standard pattern (fig. (b)).

Figure 3

 3 Figure 3 Projection of an n × n pattern from an SFT onto a sofic shift.

Figure 6 A

 6 Figure6A pattern P with En(P ) ≤n En(P ) matches the neighborhood.

Figure 7 A

 7 Figure7A pattern P with En(P ) ≤n En(P ) does not match the neighborhood.

  5, Example 2.5] and similar examples.To handle this class of (non-sofic) shifts we introduce a slightly more general version for epitomes: for every pattern P on support B n compatible with R, if E n (P ) is defined then E n (P ) ≤ n E n (P ) (i.e., this configuration R on the complement of B n determines the maximum of the E nepitomes over all valid P ).

	Definition

21. Let E n be a finite set with a partial order ≤ n on it, and

E n : [pattern of size n × n] → [element of E n ]

be a partial function, for each integer n > 0. We say that (E n , ≤ n ) is a family of ordered epitomes for a shift S, if for every globally admissible pattern P with support B n such that E n (P ) is defined, there exists a pattern R on F n such that (i) R is compatible with P , i.e., the union of P and R forms a valid configuration in S, and (ii)

A. Rumyantsev and M. Ushakov. Forbidden substrings, Kolmogorov complexity and almost periodic sequences. In Proc. Annual Symposium on Theoretical Aspects of Computer Science, pages 396-407, 2006.

V. Salo. Subshifts with sparse projective subdynamics. arXiv preprint, arXiv:1605.09623, 2016.

B. Weiss. Subshifts of finite type and sofic systems. Monatsh.Math., 77:462-474, 1973.

L.B. Westrick. Seas of squares with sizes from a Π 0 1 set. Israel Journal of Mathematics, 22:1, 2017.

Proof. The proof is similar to the proof of Proposition 19, except for the last part. In the previous proof, we use brute-force search to find one pattern Q compatible with the given border line ∂Q, apply projection π, and then compute the epitome. Now we should find all patterns Q compatible with ∂Q, apply to each of them the projection π, try to compute their epitomes (E n is partial), and then take the maximum of the obtained results. It remains to notice that for an exp-time computable ordered family of epitomes this exhaustive search runs in time 2 O(n 2 ) .

(a) Forbidden pattern: a square with a red top and a black bottom.

(b) A pattern for which the epitome En is defined: each row starts with a few black cells on the left followed by white cells on the right.

(c) A pair of incomparable patterns.

Figure 4

Example 24 (the shift with no hidden red-black squares). Now we discuss an example proposed by Kass and Madden in [5, Example 2.5], and reformulate the argument given in [START_REF] Kass | A sufficient condition for non-soficness of higher-dimensional subshifts[END_REF] in the language of Kolmogorov complexity, in terms of ordered epitomes.

Let Σ be the alphabet with three letters (e.g., black, white, and red), and the forbidden patterns be all squares (of all sizes) where the top side consists of red cells, and the bottom one consists of black cells (hidden red-black squares), as shown in Fig. 4a. Proposition 25 ([5]). The shift on Z 2 defined by the set of forbidden patterns specified above is not sofic.

In [START_REF] Kass | A sufficient condition for non-soficness of higher-dimensional subshifts[END_REF]

this proposition was proven with the technique of union-increasing sequence of extenders.

In what follows we propose a similar argument, but explain it in terms of ordered epitomes.

Proof of Proposition 25. We define for this shift a family of ordered epitomes. First of all, we define a class of simple patterns: the simple patterns are all square patterns that (i) consist of only black and white letters (with no red letters), where (ii) every row starts with a few successive black letters followed by a sequence of white letters, as show in Fig. 4b. Every simple pattern of size n × n can be specified by its profile -a tuple of integers (k 1 , . . . , k n ), where k i is the number of black cells in the i-th row of the pattern. (Thus, a simple pattern with the profile (k 1 , . . . , k n ) is an n × n square where each i-th row starts with k i black letters followed by (n -k i ) white letters.)

Let epitome E n assign to each simple pattern its profile, and be undefined for all other patterns. For example, for the pattern P show in Fig. 4b we have E 8 (P ) = (4, 3, 8, 5, 4, 2, 4, 6).

We introduce the natural order ≤ n on the profiles of simple patterns of size n × n; we say that the profile of P 1 is not greater than the profile of P 2 , if the first profile is coordinate-wise not greater than the second profile. For example, the profiles of the two patterns shown in Fig. 4c are not greater than the profile of the pattern in Fig. 4b (and incomparable with each other).

The introduced E n and ≤ n are obviously computable, even in polynomial time. Some work is required to show that E n and ≤ n satisfy Definition 21:

Lemma 26. The defined above (E n , ≤ n ) provide a family of exp-time computable ordered epitomes for the shift under consideration.

This lemma is proven implicitly in [START_REF] Kass | A sufficient condition for non-soficness of higher-dimensional subshifts[END_REF]. In what follows, for the sake of self-containedness, we sketch this proof.

Proof of Lemma 26. For every simple pattern P of size n × n we should construct a configuration R on the complement of B n , so that (i) P and R are compatible, (ii) for every other simple pattern P compatible with R we have E n (P ) ≤ n E n (P ). We build R by following the construction from [START_REF] Kass | A sufficient condition for non-soficness of higher-dimensional subshifts[END_REF]. By definition, each row of P consists of a contiguous sequence of black cells followed by a contiguous sequence of white cells, as shown in Fig. 4b. The pattern R will consist of a finite number of black and red cells (the other cells will be white).

Black cells in R. To construct R, we extend each stripes of black cells in P to the left, so that in the first line we get a contiguous sequence of (3n -1) black cells (including those black cells that belong to P ), in the second line a contiguous sequence of (3n -3) black cells, in the third line a contiguous sequence of (3n -5) black cells, etc. In the n-th line we obtain a contiguous sequence of (n + 1) black cell, see Fig. 5.

Red cells in R. Similarly, we put in R stripes of red cells: 3n contiguous red cells in line 3n, (3n -2) contiguous red cells in line 3n -1, . . . , (n + 2) contiguous red cells in line (2n + 1). We place these stripes of red cells so that for each i = 1, . . . , n the leftmost red cell in the line (3n -i + 1) is vertically aligned with the leftmost black cell in the line i, as shown in Fig. 5.

All other cells outside B n are made white.

Claim 27. The constructed R is compatible with P .

Proof of Claim 27. This fact is easy to verify: we have chosen the lengths of black and red stripes so that they cannot form a forbidden pattern (as in Fig. 4a), regardless the horizontal placement of each stripes. Indeed, on the one hand, the black cells of the i-th line cannot


Helene Berthet
email: helene.berthet@espci.fr

Olivia Du Roure
email: olivia.duroure@espci.fr

Anke Lindner
email: anke.lindner@espci.fr

Microfluidic Fabrication Solutions for Tailor-Designed Fiber Suspensions

Keywords: micro-fluidics, fibers, fiber suspensions, fluid-structure interactions, flexible fibers

Fibers are widely used in different industrial processes, for example in paper manufacturing or lost circulation problems in the oil industry. Recently, interest towards the use of fibers at the microscale has grown, driven by research in bio-medical applications or drug delivery systems. Microfluidic systems are not only directly relevant for lab-on-chip applications, but have also proven to be good model systems to tackle fundamental questions about the flow of fiber suspensions. It has therefore become necessary to provide fiber-like particles with an excellent control of their properties. We present here two complementary in situ methods to fabricate controlled micro-fibers allowing for an embedded fabrication and flow-on-a-chip platform. The first one, based on a photo-lithography principle, can be used to make isolated fibers and dilute fiber suspensions at specific locations of interest inside a microchannel. The self-assembly property of super-paramagnetic colloids is the principle of the second fabrication method, which enables the fabrication of concentrated suspensions of more flexible fibers. We propose a flow gallery with several examples of fiber flow illustrating the two methods' capabilities and a range of recent laminar flow results.

Introduction

The flow of fiber suspensions occurs in a large number of industrial processes and applications, ranging from paper fabrication [START_REF] Lundell | Fluid Mechanics of Papermaking[END_REF] to lost circulation problems in the oil industry [START_REF] Gupta | Novel Fiber-Based Lost Circulation Treatment Cured Total Losses in Depleted Zones in Emeraude Field[END_REF]. A good control of these processes relies on the understanding of the underlying mechanisms, notably the interaction between fibers and flows. These interactions depend strongly on the fiber and flow properties of the given situation and are often found to be complex in industrial applications.

Recent efforts to build lab-on-a-chip applications has created increasing interest in microscopic systems containing fiber-like particles, for example for biomedical applications, drug delivery or micro-filtration devices [START_REF] Jun | Microfluidic spinning of micro-and nano-scale fibers for tissue engineering[END_REF][START_REF] Pamme | Continuous flow separations in microfluidic devices[END_REF]. In this case, the precise understanding of the fiber flow interactions is a necessary ingredient for the development of efficient devices.

Well-controlled model systems are needed to gain this fundamental understanding, and the fabrication of fibers with controlled and tunable properties is crucial. Carbon nanotubes, micro-structures fabricated from soft-lithography-derived-techniques [START_REF] Merkel | Scalable, shape-specific, top-down fabrication methods for the synthesis of engineered colloidal particles[END_REF][START_REF] Tavacoli | The fabrication and directed self-assembly of micron-sized superparamagnetic non-spherical particles[END_REF] or techniques combining capillarities and coating [START_REF] Lee | Macroscopic nanoparticle ribbons and fabrics[END_REF] are attractive strategies to fabricate suspensions of microscopic objects with a well-defined geometry and volumic fraction. However, the collection and the suspension of these particles, as well as the injection of the suspension itself into a microfluidic device are problematic issues, which would become even more difficult for flexible particles: clearly, in situ fabrication methods are required to obtain well-controlled systems. It is possible to use microfluidic flow-focusing to fabricate long fibers of different geometries [START_REF] Jeong | Hydrodynamic microfabrication via "on the fly" photopolymerization of microscale fibers and tubes[END_REF], but this approach is limited when decreasing the sizes to tens of microns. In this paper, we present a review of the methods developed in our group, which allow the combination of the microfabrication of fibers and the observation of their flow in microfluidic channels. One of them is based on an existing UV-curing method of micro-objects directly inside micro-channels [START_REF] Dendukuri | The Synthesis and Assembly of Polymeric Microparticles Using Microfluidics[END_REF][START_REF] Helgeson | Hydrogel microparticles from lithographic processes: Novel materials for fundamental and applied colloid science[END_REF], whereas the second uses self-assembly properties of magnetic colloids into chains to fabricate long and flexible filaments.

Microfabrication of Suspensions of Polymeric Fibers by Photo-Polymerization

Principle and Setup Description

We adapted a microscope-based photolithography method initially developed by Dendukuri et al. [START_REF] Dendukuri | Continuous-flow lithography for high-throughput microparticle synthesis[END_REF] to produce confined fibers directly inside a microfluidic chip. The idea is to project UV light through a fiber-shaped lithography mask into a microfluidic channel filled with a reactive substance. The solution, a mixture of an oligomer and photo-initiator, crosslinks under UV light: the illumination of the target fluid region through the mask polymerizes it within hundreds of milliseconds. A schematic drawing of the method for fiber fabrication is presented in Figure 1.

When using an all-PDMS (polydimethylsiloxane) channel, oxygen diffuses through the PDMS walls and inhibits the radical crosslinking reaction close to the channel walls. The two inhibition layers formed in this way at the upper and lower walls prevent the fibers from sticking to the latter. The light projection along the channel height therefore leads to free fibers with a rectangular cross-section. The inhibition layers can be taken advantage of to adapt the fiber geometry, for example to control the confinement, as we will see later in this article. The choice of the oligomer and the concentration of photo-initiator should be made in regards to the targeted mechanical properties of the fabricated fiber [START_REF] Berthet | Single and Collective Fiber Dynamics in Confined Microflows[END_REF][START_REF] Duprat | Microfluidic in situ mechanical testing of photopolymerized gels[END_REF]; see Section 2.3.3. The photo-initiator excitation wavelength should match the light source available and the setup constraints (like the transmission of UV light). Here, we use Darocur 1173 photo-initiator (PI; Ciba Specialty Chemicals Inc., Basel, Switzerland) (2-hydroxy-2-methylpropiophenone, Sigma, Saint Louis, MO, USA), whose excitation peak is around 365 nm. This peak is twice more intense with an HBO lamp as compared to a Xcite120Q source, leading to faster curing with the HBO lamp. For an application requiring softer materials or the presence of water, one can benefit from the solubility of polyethylene glycol diacrylate (PEGDA) in water to fabricate soft hydrogel particles.

As illustrated in Figure 1, we built a fabrication and flow study platform in a single setup. A transparent all-PDMS (Sylgard 184; Corning, Midland, MI, USA) microchannel is made with traditional soft-lithography techniques [START_REF] Berthet | Single and Collective Fiber Dynamics in Confined Microflows[END_REF]. It is then placed on the stage of an inverted microscope (Zeiss Axio Observer, Oberkochen, Germany) equipped with a UV light source, a shutter and a fiber-shaped mask (Shutter Uniblitz V25, Lamp HBO 130W, Osram, Munchen, Germany). The UV light is filtered through a narrow-UV-excitation filter set (11004v2 Chroma, Burlington, VT, USA) with an emission peak at λ ∼ 365 nm.

We work with rectangular-section microchannels where the width is up to ten-times larger than the height. The orders of magnitude of channel dimensions are: width 200-500 µm, height 20-50 µm and a length of several centimeters.

The lithography mask determines specifically the aspect ratio in the plane (x, y) perpendicular to the optical axis. It consists of a transparent-fiber shape drawn in the center part of a 25 mm-diameter black disk. We place this mask in the field stop position of the microscope to get it focused into the objective image plane. The mask is designed with AUTOCAD 2009 and printed at high resolution (50,800 dpi) in order to limit defects on the border line and black spots inside the fiber shape. Anti-UV coated tubings are used to connect the inlet and outlet of the microchannel to a syringe or fluid reservoir, preventing inside polymerization.

Fabrication Protocol

We describe here the typical workflow of a fabrication experiment. The preparation prior to the experiment involves the design of the mask, the design and fabrication of the microchannel, accordingly, and the placement of the channel and mask on the microscope. We use a mixture of polyethylene glycol diacrylate (PEGDA, Mw = 575, Sigma) (without solvent) with Darocur 1173 photo-initiator (PI) (2-hydroxy-2-methylpropiophenone, Sigma) at 10 wt % and introduce the mixture into the channel by pressure difference. Just before exposition to UV light, we position the chip to get the fabrication of the particle in the chosen location. A camera (PIXELINK, Gloucester, ON, CA) is used for direct observation of the channel. Then, the computer-controlled shutter opens, typically for 200 ms in our setup, and the fiber is crosslinked in the channel. A movie showing the fiber fabrication is available in Supplementary Materials Video S1.

The focusing step is the most delicate one due to the corrections of microscope objectives for achromatic aberrations. It is usually necessary to calibrate the optical system under UV light prior to fabrication, in particular in the case of high-magnification objectives, which have a short depth of field. On our system, using the microscope objective 10×, the focusing done with visible light is corrected with UV light. For objectives 20× and higher, we had to slightly "unfocus" when switching to UV light: for example, a quarter of a full knob rotation for the 40×. This can be avoided using objectives with very small achromatic aberration in UV.

It may be useful to perform the fabrication without stopping the flow [START_REF] Dendukuri | Continuous-flow lithography for high-throughput microparticle synthesis[END_REF]. We often worked with a y-shaped microfluidic channel (see Figure 2) allowing, in one of the entry branches, the fiber fabrication with a low-imposed flow rate for high fabrication quality. The second branch was used to adjust the final flow rate, but could be used to inject a different fluid or suspension of particles.

We used this fabrication and flow platform to study the flow dynamics of fibers with varying initial orientation [START_REF] Berthet | Single fiber transport in a confined channel: Microfluidic experiments and numerical study[END_REF].

Control of Fiber Properties

Fiber Geometry

The lithography technique offers the possibility of making isolated fibers or a fairly limited number of fibers at precise positions inside the channel as illustrated in Figure 3d-f. Their geometry is entirely controlled by the design of the lithography mask. The fiber length and width are proportional to its dimensions, modulo a reduction factor due to both the microscope objective and tube lens. For an objective of a magnitude of 10, we typically obtain a reduction factor of 4.5, increasing to 18.2 for an objective of 40×. This needs to be determined for each experimental setup. Low-magnification objectives were preferred because of their larger depth of field allowing an easier focusing. Typically, the width of fibers is a few tens of microns, whereas their length is a few hundreds. As explained earlier, the particle height is given by the channel height and the thickness of the inhibition layers along the upper and lower channel walls. In order to measure this thickness, one can fabricate a particle of a width much smaller than the expected height. As it flows downstream, the fiber turns on its side to lower its confinement, its height appearing in the field of view to be precisely measured. In our operating conditions, we found an inhibition layer thickness of around 6 µm. Note that this value is slightly higher than the 2.5 µm given in [START_REF] Dendukuri | The Synthesis and Assembly of Polymeric Microparticles Using Microfluidics[END_REF], but remains of the same order of magnitude. The fiber height is thus given by the channel height minus twice the thickness of the inhibition layer. For example, for a channel height of 30 µm, a fiber height of 18 µm is obtained.

The produced fibers do not necessarily need to be smooth, but can also be fabricated with a rough surface. The Figure 3 shows a simple mask (a) and a mask drawn with a saw-tooth contour (b) used to fabricate respectively a smooth fiber (d-f) or a rough one (c). We expect such a roughness to modify fiber-fiber or fiber wall interactions.

Orientation and Concentration

As said before, orientation, inter-particle distance and fiber geometry are entirely determined by the design of the lithography mask, the magnification of the objective used and the placement of the channel on the microscope. When isolated fibers are drawn on the mask, individual fibers of a given geometry can thus be positioned at precise positions inside the channel, varying for example their orientation (see the top row of Figure 3).

A higher particle concentration can be adjusted with the mask; however, one must be careful when fabricating particles very close to each other. There is a threshold distance below which the fluid separating the particles will partially cure during illumination. The threshold distance between two fibers can easily be experimentally determined using lithography masks of two fibers drawn side by side. For a fabrication using the objective 40×, we found it to be 9 µm. The right panel (d,e) of Figure 3 shows two examples of a suspension of fibers obtained in this way, all parallel (d) or perpendicular (e) to the flow direction. The fibers' length is 200 µm and the width 14 µm, and they are separated by a distance of 12 µm.

Fiber Elasticity

We mechanically characterized the fiber through an in situ measurement of its Young's modulus with an adapted "bending beam" test [START_REF] Duprat | Microfluidic in situ mechanical testing of photopolymerized gels[END_REF]. The advantages of this in situ test are two-fold. First of all, the test reproduces the exact fabrication conditions used for the micro-fabrication (e.g., UV light intensity, exposure time, etc.), and second, the mechanical properties are tested in the fluid environment used to produce the fiber suspensions. This might be particularly important when working with diluted polymer solutions and, thus, hydrogels. The adapted bending test is the first in situ Young's modulus measurement method for particles fabricated with the photo-polymerization method.

A fiber is fabricated across a confined microchannel, sitting inside slots, allowing it to deform under the drag force created by the flow. Images of the bending fiber are captured at steps of increasing flow rates, as illustrated in Figure 4. The measurement of the deformation at controlled flow forcing provides direct access to the fiber material Young's modulus.

The experiment [START_REF] Berthet | Single and Collective Fiber Dynamics in Confined Microflows[END_REF][START_REF] Duprat | Microfluidic in situ mechanical testing of photopolymerized gels[END_REF] was conducted for five formulations in order to explore a range of Young's moduli. All contain PEGDA at Mw = 575 with Darocur 1173 photo-initiator at concentrations varying from 2%-10%. Young's moduli between 1 and 12 MPa were obtained depending on the photo-initiator content and the exposure time, as shown in Figure 4. Note that the nature of the gel, initiator, microscopic optics and projected UV light lamp all lead to a strongly setup-dependent measurement technique requiring an in situ measurement. The modulus can be varied further when working with polymer solutions at different dilutions in water, creating hydrogels with even lower Young's moduli [START_REF] Chapin | High-throughput flow alignment of barcoded hydrogel microparticles[END_REF].

Fiber Confinement and Flow Geometry

As the geometry of the fibers produced using the UV fabrication method depends on the channel geometry through the channel height, fiber dimensions and channel geometry are intrinsically linked. In parallel, the channel geometry also determines the type of flow a fiber or fiber suspension experiences in the channel.

First of all, the fiber is confined in the direction of the channel height. As introduced before, the fiber height is given by the channel height minus twice the inhibition layer. The inhibition layer thickness being constant, the fiber confinement, given by the fiber height over the channel height, can thus be varied by changing the channel height (see Figure 1c). Very specific flow properties result from this confinement and will be discussed in the flow gallery (see Section 5).

Furthermore, the fiber height being comparable to the channel height, to obtain square cross-sections and large aspect ratios (typically a length over width larger than 10), the channel height needs to be small compared to the channel width. This configuration is called a Hele-Shaw cell. In such a flow geometry, a plug flow is obtained in the direction of the channel width, and the shear is localized in the channel height with a small shear layer next to the lateral walls. The fabrication method thus determines not only the confinement of the fiber in the microfluidic channel, but also the overall flow geometry.

Microfabrication of Suspensions of Fibers by Colloidal Self-Assembly

We now present a second microfluidic in situ fabrication method to obtain suspensions of flexible fibers at a much higher concentration. We adapted an experimental technique initially developed by Goubault et al. [START_REF] Goubault | Colloides Magnétiques: Auto-Organisation et Applications Biologiques[END_REF] to generate elastic filaments in capillaries. This way, we are able to obtain flexible fibers with a well-controllable geometry, at high concentrations, directly inside microfluidic geometries onto a microscope.

Principle of Fabrication

The fabrication technique relies on the self-assembly property of superparamagnetic colloids and magneto-stimulated bridging between them. A microfluidic channel filled with a solution of such colloids is placed on the stage of a microscope equipped with a coil to produce a vertical magnetic field. When the magnetic field is applied, each colloidal particle acquires a magnetic moment parallel to the magnetic field B, along the height of the channel. Dipolar interactions are attractive in a solid angle along the direction of the field and with an apex of 55 • . They induce self-assembly of one-dimensional structures aligned with B. Since the particles are superparamagnetic, once the magnetic field is removed, the colloids move freely and independently in the solution due to Brownian motion. To form permanent filaments, we add polymer to the colloidal suspension. The polymers adsorbed on the surface of each particle will also adsorb to the neighboring particles in the chain (as illustrated in Figure 5) if the surfaces remain close enough during long enough time [START_REF] Cohen-Tannoudji | Polymer Bridging Probed by Magnetic Colloids[END_REF]. There is thus a threshold in the magnitude of the magnetic field above which permanent bridging is achieved and below which the chain will disassemble when the magnetic field is switched off. This threshold is essential to obtain a controlled one-dimensional structure. If particles were simply adhesive, the many collisions that they experience due to their Brownian motion would lead to random aggregation.

Experimental Protocol

The fabrication method consists of three steps as described in Figure 6. Left sketches illustrate each step seen from the side: the height and length of the microfluidic channel are visible. Right-side pictures are extracted from the experiment and show the channel from above. In the first step, the solution of superparamagnetic colloidal particles and polymer in water is introduced into the microchannel placed on the microscope stage (Figure 6(1)). Then, the flow is stopped, and a vertical magnetic field is applied (Figure 6(2)). During this step, the attractive magnetic interactions cause the colloids to self-assemble, and permanent bridging is achieved by the polymer. In the last step, the magnetic field is removed (Figure 6(3)). The superparamagnetic particles are provided by Ademtech (V2G colloids, radius 375 nm, magnetic susceptibility χ = 1.3). They are dispersed at a volume fraction of 2.5 wt % in an aqueous solution containing 0.1 wt % of polyacrylic acid (PAA, Mw = 250,000, Sigma) and 0.1 wt % NP10 surfactant (nonyl phenol ethoxylate, Sigma). The fabrication and flow experiments are done on a Nikon-inverted microscope equipped with a large coil creating a vertical magnetic field in its center. The microchannel is made with traditional soft-lithography techniques. We use a PDMS mold plasma-bonded to a glass slide. It is placed on the microscope stage at the center of the coil. During the fabrication step, we apply a magnetic field of 25 mT for 35 min. Note that any residual flow within the channel at this step would perturb the bridging and prevent the fabrication of the fibers.

The permanently-formed fibers sediment in the channel with random directions. Figure 7 shows a time series of images taken from above of the sedimenting fibers starting when the magnetic field is removed.

Control of Fiber Properties

Fiber Geometry

The fibers are characterized by a necklace-like shape: their diameter is given by the diameter of the colloidal particles as illustrated in Figure 5. As the magnetic field is applied in the direction of the channel height, if the magnetic field is applied quickly compared to the sedimentation of the colloids, the fiber length is only limited by the channel height. One can however add a sedimentation step prior to the application of the magnetic field to fabricate filaments shorter than the channel height [START_REF] Coq | Three-dimensional beating of magnetic microrods[END_REF]. In both cases, monodisperse fibers are obtained (see Figure 7).

The fiber aspect ratio can be very large: typical aspect ratios (fiber length over fiber width) are 30-50, but aspect ratios as high as 265 can be obtained [START_REF] Babataheri | Tethered fleximags as artificial cilia[END_REF]. As fibers form as chains of spherical particles, their surface roughness is given by the particles' radius and could be modified by changing the dimension of the particles.

Fiber Position, Orientation and Concentration

When applying the magnetic field, the vertical columns formed by the assembled colloids show a strong ordering: the dipolar magnetic interactions between columns is repulsive and the equilibrium distance, d, between columns is only determined by their length, L, and d = 1.33L 0.37 [START_REF] Jing | Field-Induced Structures in Ferrofluid Emulsions[END_REF]. One can see the strong ordering of the filaments, showing a constant distance between chains in top left image of Figure 7. This ordering leads to a homogeneous fiber concentration and random orientation once fibers have sedimented to the bottom of the channel (see Figure 7). One can however take advantage of the fact that the formed fibers are magnetic and can use a magnetic field to orient the fibers in the desired direction (see Figure 8). The maximum concentration of filaments is set by the above-cited relationship between L and d. Below this limit, the fiber concentration in the suspension can be adjusted by tuning the initial volume fraction of colloids. We illustrate this in Figure 9 showing pictures of fiber suspensions fabricated at three volume fractions both during the fabrication (top row) and after sedimentation (bottom row). The channel geometry used for the fabrication is the same for all three bottom pictures with a height of 24 µm.

Elasticity

Fiber elasticity depends on the nature of the polymer bridging the particles together. A bending modulus of 7.8 × 10 -26 J•m was measured [START_REF] Goubault | Colloides Magnétiques: Auto-Organisation et Applications Biologiques[END_REF] for filaments obtained with the same protocol, colloids and polymer we use in our experiments. A way of increasing the fiber rigidity is to form chains of more than one array of particles. If the volume fraction of particles in solution is increased, it becomes possible to form chains that interact laterally with a half-colloid-long shift (according to the 55 • ). The field threshold to permanently bridge these lateral interactions is larger because the force in directions not aligned with the field is smaller. However, it is possible to use intense-enough fields to generate chains made of two or three rows of particles, as illustrated by Figure 10.

Fiber Confinement and Flow Geometry

The fabrication process, using a vertical magnetic field, implies that the length of the fibers is comparable to the channel height. The value of the channel height is thus imposed by the desired length of the fibers to be fabricated. As typically the channel width is two-or three-times the fiber length, channels with a nearly square cross-section are used, in contrast to the channels used for the UV method. This has two important consequences: the flow in the channel is close to a three-dimensional Poiseuille flow [START_REF] Guyon | Physical Hydrodynamics[END_REF], as observed in a capillary tube, and fibers are not confined between the top and bottom wall of the channel.

However, as the magnetic fibers are made of colloids filled with iron oxide nanoparticles, they are much denser than water. Thus, when the field vanishes the magnetic fibers sediment to the bottom of the chamber, and all fibers are found in a narrow layer close to the bottom wall. The height of this layer is determined by the Brownian motion of the fibers against the confining gravity forces. One could thus consider this situation as a 'gravity-confined' suspension.

Comparison of the Two Fabrication Methods

Traditional soft-lithography methods for the fabrication of microfluidic channels allow the user to easily design a suitable channel geometry so that the desired fiber design matches the type of flow geometry required. This way, a platform enabling fiber fabrication, observation and two-dimensional or three-dimensional flow is obtained. The two methods of in situ fabrication of microscale fibers presented in this paper are easy to implement on a lab-on-a-chip flow platform, and both allow for a direct flow of fibers downstream a microfluidic channel. These two methods are complementary on the fiber initial position, orientation, geometry, concentration, elasticity and surface characteristics and enable a choice of a number of important features for their flow: the initial state before flow and the flow geometry. We summarize and compare, in Table 1, all of these parameters to provide a clear overview of the fabrication techniques' capabilities.

Flow Gallery

In this section, we give a number of examples of the flow dynamics of individual fibers and fiber suspensions. These examples illustrate not only the intriguing phenomena that occur during the flow of fiber suspensions, but also give an idea of the large variety of questions that can be treated with the model systems presented in the previous paragraphs. We also specifically present some useful methods to analyze the fibers' flow dynamics.

Transport of a Single Confined Fiber

We used the photo-lithography technique to study the transport of individual confined fibers in a Hele-Shaw microchannel. We previously reported [START_REF] Berthet | Single and Collective Fiber Dynamics in Confined Microflows[END_REF][START_REF] Berthet | Single fiber transport in a confined channel: Microfluidic experiments and numerical study[END_REF] experimental results completed with numerical simulations, treating in particular the role of confinement and orientation on the fiber dynamics. We have shown that under these confined conditions, a transport anisotropy is observed: a fiber-oriented perpendicular to the flow direction is transported faster compared to a parallel fiber under similar flow conditions [START_REF] Berthet | Single fiber transport in a confined channel: Microfluidic experiments and numerical study[END_REF]. When such an isolated and confined fiber is flowing with an angle (different from zero or ninety degrees) to the main flow direction, it will thus drift with respect to the flow direction and will inevitably approach one of the lateral walls of the microchannel. Hydrodynamic interactions between the fiber and the wall align the fiber parallel to the latter. Any small perturbation will cause the fiber to rotate again and to drift away from the wall with a constant orientation until the interaction with the opposite wall will again lead to fiber alignment. This series of rotation and drift leads to a very regular oscillation of the fiber between the two walls, as illustrated by Figure 11 and described in more detail in [START_REF] Nagel | Oscillations of confined fibers transported in microchannels[END_REF]. This phenomenon could for example be used as an active mixing method.

The dynamics becomes more complicated when the fiber is flexible enough to be deformed by the viscous flow (see Figure 12) when approaching the channel walls. Due to the deformation of the fiber, the symmetry between fiber approach and departure is broken. The precise effect of flexibility on the oscillation dynamics remains however still largely unexplored.

Two-Dimensional Dynamics of Fiber Suspensions Near a Flow Constriction

Fabrication of ordered suspensions is illustrated by two cases of different initial fiber orientation in the right panel of Figure 3d,e. In such experiments, the objective was to investigate the flow of ordered suspensions towards a constriction. The lithography mask contains respectively eleven and eight fiber shapes. It is carefully aligned on the microscope to fabricate all of the fibers inside the channel, before manually moving the stage to position the mask upstream and fabricate a new batch of fibers. The operation is repeated as many times as necessary. Fabrication was done at zero flow, then a calibrated hydrostatic pressure was imposed to start the flow. In this case, we designed the channels in such a way as not to allow fibers to flow above each other.

The fiber dynamics at the approach of a constriction was investigated in both configurations (fibers all parallel or all initially perpendicular to the flow direction) [START_REF] Berthet | Single and Collective Fiber Dynamics in Confined Microflows[END_REF][START_REF] Lindner | Flow of complex suspensions[END_REF]. Figure 13 shows images of the parallel suspension at different times after the flow is applied. The initial configuration of the suspension is well organized, and when the flow is applied, the fibers in the middle of the first row experience the largest flow velocity and, thus, pass through the constriction. The two outer fibers on both sides are then blocked by the wall of the constriction. When the second row approaches, the outer fibers of the first row are pushed and rotate, allowing the fibers closest to the constriction to pass, while most outer fibers are still blocked. This mechanism is illustrated in the first column of Figure 13 where 200 ms separate the different frames. Then, the suspension disorganizes, breaking its lateral symmetry, and clogging occurs rapidly, as can be seen on the second column of Figure 13. Note that the time between frames in this column is 3 s. From that moment onwards, the flow of fibers into the constriction is drastically slowed down as shown on the third column of Figure 13 where the time between frames is 6 s.

The bottom image of Figure 13 is a spatio-temporal representation showing the time evolution of a given area. Here, time goes from left to right, whereas the vertical axis corresponds to the pixels of a vertical line from each picture. Its position on the pictures is indicated by the thin black line on the last frame on the bottom right of Figure 13. This type of representation is very useful to obtain a global view of a time-dependent phenomena. Each elongated bright object corresponds to a fiber passing through the observed line, but the length of the object is not the fiber length, but the duration of the passage. The shorter the object, the fastest the fiber. On the spatio-temporal image, one can identify the passage and reorientation of the first row (from the beginning to the end of the yellow line). Then, in the first half of the red line, the fibers enter the constriction quickly, and the lateral symmetry starts to be broken. From this moment onwards, all horizontal objects on the spatio-temporal image are very long, meaning that the dynamics is strongly slowed down, and the constriction remains clogged. The observed dynamics are very different in the perpendicular configuration (shown in Figure 14). During the first period (the first column in Figure 14), the first fibers accumulate at the constriction as their orientation prevents them from passing through. Then, they start to bend slightly (as can be seen in the fifth image of this column). The fiber deformation can also be seen in the spatio-temporal image at the bottom of Figure 14, where a black area appears in the last third of the period indicated by the yellow line. Then, the first fibers rotate, breaking the lateral symmetry, and subsequently, clusters of several fibers are formed in the upstream channel, as can be seen in the middle column. Note that the dynamics during this period are faster than for the two other columns (total duration of the first column (yellow): 6 s; middle column (red): 2.8 s; last column (blue): 12 s). The flow of the suspension then becomes very heterogeneous: clusters accumulate on one side, whereas isolated fibers are transported quickly into the constriction at an almost constant speed on the other side (left column of Figure 14). This can be easily seen in the spatio-temporal image, where during the end of the intermediate period (indicated in red) and during all of the last period (indicated in blue), the bright objects have almost the same size. The cluster formation is seen more easily in the second spatio-temporal image showing a cut in the direction of the flow in Figure 15.

Finally, Figure 16 shows a suspension of flexible fibers transported perpendicular to the flow direction. The fibers are strongly deformed by the flow when arriving at the constriction. Subsequently, they enter the constriction easily, being still deformed, and only relax back to a straight shape further downstream. Then, quickly, clusters start to form upstream as in the previous example for more rigid fibers (Figure 14). Again, this leads to a lateral symmetry breaking after which fibers go through the constriction as clusters of mainly undeformed fibers, and the dynamics is slowed down. A spatio-temporal representation of these dynamics looks very similar to the one represented in Figure 14 and is thus not shown explicitly. The first column focuses on the initial times (0.85 s between frames); the second shows the lateral symmetry breaking on a longer time scale (6 s after applying the flow, 0.4 s between frames); and the third one shows later times (10 s after applying the flow, 1.7 s between frames). The suspension changes from an ordered spatial organization to a disorganized state, which evolves very slowly. The bottom image is a spatio-temporal representation of a cut perpendicular to the flow direction. Time is represented as the x-axis going from left to right (≈12 s in total), whereas the y-axis represents a line drawn in black on the last image. Note that the total number of images treated here is smaller than the one used for Figure 13, resulting in a smaller spatio-temporal image. The corresponding video is available in Supplementary Materials Video S6.

Collective Dynamics of Flexible Fibers Close to the Bottom Wall

We present in this section examples of the flow of fibers fabricated with the colloidal self-assembly method in a microchannel. They represent the flow of a dense suspension of very flexible and rough fibers confined by gravity to a narrow layer close to the channel bottom.

Before the pressure-induced flow starts, the distribution of fibers in the channel is homogeneous (see Figure 7). For high enough concentrations, many collisions between fibers are provoked when the flow is started and aggregates start to form. Contrary to fiber clusters observed in sedimentation, these aggregates are immobilized within the channel. They grow in size as more fibers flow into the channel. We believe that their formation is triggered by fibers slowed down by or adhering to the bottom wall. In the three examples shown in Figure 17, a frame indicates the cluster location, before and after its formation. These flocs of fibers are not persistent in the flow and detach after some time. We observed that in most cases, a cluster leaves as a whole; but then, inter-fiber contacts break immediately, and fibers disentangle. A small cluster is usually left behind, probably due to the fact that one or a few fibers were blocked at the bottom wall prior to the clustering. We illustrate such disaggregation of a cluster in Figure 18. At even higher concentrations, we observed the formation of a fiber network flowing downstream at a constant velocity. Some isolated fibers remain in the channel and flow faster than the network, which extends across the channel width. Successive pictures illustrate this behavior in Figure 19.

Conclusions

In this paper, we described two attractive methods to fabricate microscopic fibers directly inside microfluidic channels. Intimately linked with the channel geometry, they provide a large choice for the design of fiber characteristics, such as geometry, mechanical properties or surface roughness. Both techniques are in situ and microscope-based. In the first case, fibers or fiber suspensions are produced by UV-polymerization, whereas in the second method, we use the assembling properties of super-paramagnetic colloidal particles initially introduced in the channel to obtain fiber suspensions.

Flow of single particles, as well as suspensions of fibers at varying concentrations can be easily obtained using these methods, as we have illustrated by a number of examples.

In the future, these methods can be used to tackle fundamental problems on the interaction of complex particles with viscous flows. The better understanding of these fundamental questions might pave the way to the development of sophisticated microfluidic flow separation or analytical biomedical devices. These methods might be used, as well as building blocks for the design of microfluidic devices as flow sensors, or valves, or targeted delivery devices.

Figure 1 .

 1 Figure 1. (a) Schematic drawing of the in situ fiber fabrication technique, using a microscope-based projection lithography technique.UV light is projected into the channel through a fiber-shaped mask, polymerizing the polymer inside the channel, typically within 100 ms; (b) one or several fiber shapes can be used on the mask depending on the number of fibers to make in one step; (c) the polymerization is prevented close to the PDMS walls due to the presence of oxygen allowing free fibers to be fabricated. The thickness of the inhibition layer being constant, the confinement increases with the channel height.

Figure 2 .

 2 Figure 2. Y-shaped microfluidic channel for in-flow fabrication with a fiber made in the low-flow rate branch. Inset: successive positions of the flowing fiber.

Figure 3 .

 3 Figure 3. Examples of photopolymerized fibers. Left panel: (a) example of the mask used to fabricate the fibers. The mask shown here is smooth and will allow the fabrication of smooth fibers like the ones shown in the top row of the right panel; (b,c) the surface roughness of the fiber can be increased by drawing its borders with saw-tooth lines instead of straight ones ((b) mask; (c) resulting fiber). Right panel: top, isolated fibers (d-f); and suspensions of fibers (g,h) fabricated at varying initial orientation. A movie showing the fabrication of the parallel fiber suspension is available in Supplementary Materials Video S1.

Figure 4 .

 4 Figure 4. Adapted from [13] with permission from the Royal Society of Chemistry, 2015. (a) Successive positions of deformed fiber; (b) measured fiber deformation with respect to the flow velocity; (c) results of Young's moduli for different exposure times. A movie showing the fiber deforming under flow is available in Supplementary Materials Video S2.

Figure 5 .

 5 Figure 5. Super-paramagnetic colloids bridged by a polymer chain, forming flexible fibers.

Figure 6 .

 6 Figure 6. Principle of fabrication of fibers using super-paramagnetic colloids. Left drawings represent a vertical section view of the channel through the three steps of fabrication, illustrated on the right by frames of the channel captured from above on the microscope, extracted from an experiment.

Figure 7 .

 7 Figure 7. Successive photographs of the channel from above starting when the magnetic field is removed until the end of the sedimentation of fibers to the bottom of the channel. The channel height (and fiber length) is 28 µm. A video of these fabrication steps is available in Supplementary Materials Video S3.

BFigure 8 .Figure 9 .

 89 Figure 8. Photographs of suspensions of short fibers with an imposed orientation using an external magnet.

Figure 10 .

 10 Figure 10. The top picture shows fibers formed by several chains of colloids bridged together. The bottom picture shows a very long (several centimeters) single-row fiber fabricated in the tubing connecting the inlet of the channel. Blue dots help with locating the fiber.

Figure 11 .Figure 12 .

 1112 Figure 11. Time-lapse image of a fiber flowing in the channel. Two hundred milliseconds separate two successive positions. The channel width is 200 µm; fiber length 290 µm. The corresponding video is available in Supplementary Materials Video S4.

Figure 13 .

 13 Figure 13. Time series of images showing the behavior of a suspension of 200 µm-long fibers, oriented parallel to the flow, which goes from left to right on the pictures. The first column (yellow) focuses on the initial times (200 ms between frames); the second column (red) shows the lateral symmetry breaking on a longer time scale (3 s after applying the flow, 3 s between frames); and the third column (blue) shows later times (20 s after applying the flow, 6 s between frames). The suspension changes from an ordered spatial organization to a disorganized state, which evolves very slowly. The bottom image is a spatio-temporal representation. Time is represented as the x-axis going from left to right (≈60 s in total), whereas the y-axis represents a line from each picture always positioned at the same place and indicated as a black line on the bottom right image. The colored lines indicate the start and duration of corresponding sets of images shown above. The corresponding video is available in Supplementary Materials Video S5.

Figure 14 .

 14 Figure 14. Time series of images showing the behavior of a suspension of 200 µm-long fibers oriented perpendicular to the flow. Flow goes from left to right in the pictures.The first column focuses on the initial times (0.85 s between frames); the second shows the lateral symmetry breaking on a longer time scale (6 s after applying the flow, 0.4 s between frames); and the third one shows later times (10 s after applying the flow, 1.7 s between frames). The suspension changes from an ordered spatial organization to a disorganized state, which evolves very slowly. The bottom image is a spatio-temporal representation of a cut perpendicular to the flow direction. Time is represented as the x-axis going from left to right (≈12 s in total), whereas the y-axis represents a line drawn in black on the last image. Note that the total number of images treated here is smaller than the one used for Figure13, resulting in a smaller spatio-temporal image. The corresponding video is available in Supplementary Materials Video S6.

Figure 15 .

 15 Figure 15. Spatio-temporal representation of a cut parallel to the flow direction. The top image is the first image of the whole image sequence of the fiber suspension shown in Figure 14. The orange line indicates the cut used to build the spatio-temporal representation of the image sequence shown below. Here, time goes from top to bottom (total duration around 12 s), and the horizontal axis corresponds to the orange line drawn in the picture above. The position of the constriction is indicated in white, and the colored lines indicate the start and duration of corresponding sets of images shown in Figure 14. In this representation, cluster formation upstream of the restriction can be easily seen. The white arrows indicate empty spaces separating clusters.

Figure 16 .

 16 Figure 16. Time series of images showing the behavior of a suspension of 250 µm-long fibers oriented perpendicular to the flow, which goes from left to right in the pictures. The consecutive images (from top to bottom in the two columns) are separated by 1.2 s and the total duration is 18 s. The corresponding video is available in Supplementary Materials Video S7.

Figure 17 .

 17 Figure 17. Three cases of fiber clustering. The first picture is taken before the formation of the cluster.One can note the orientations of the fibers in the cluster, mostly perpendicular to the flow direction. The channel width is 100 µm. The corresponding video is available in Supplementary Materials Video S8.

Figure 18 .

 18 Figure 18. Disaggregation of a fiber cluster caused by incoming fibers. The channel width is 100 µm. The corresponding video is available in Supplementary Materials Video S9.

Figure 19 .

 19 Figure 19. Formation of a network of fibers, all flowing at the same velocity, extending over the channel width. Fiber density fluctuations can be seen between the three pictures; however, all fibers have flown by the same distance.

Table 1 .

 1 Comparison of the two micro-fiber fabrication methods. Typical dimensions are given in italics.

		Photo-Lithography	Colloidal Assembly
	Fiber
	Geometry	Square or rectangular cross-section	Necklace
	Length	Mask	Channel height
		50-300 µm	20-300 µm
	Width	Mask	Colloids' diameter
		5-30 µm	∼ 1 µm
	Height	Channel height and inhibition layer Colloids' diameter
		5-30 µm	∼ 1 µm
	Elasticity	Cross-linked polymer	Polymer chains bridging the colloids
		Young's modulus: 50 kPa-10 MPa	Bending elasticity: 7.8 × 10 -26 J•m
	Roughness	Smooth unless drawn on mask	Roughness from structure
	Initial position	User-defined	Random
	Orientation	User-defined	Controlled by external magnetic field
	Flow
	Channel geometry Flat	Close to square
	Flow profile	Hele-Shaw flow	Poiseuille flow
	Confinement	By top and bottom walls	By gravity

Supplementary Materials: Zenodo DOI:10.5281/zenodo.195103 (https://zenodo.org/record/195103). Video S1: Microfluidic fabrication technique of fibers by in situ photopolymerization; Video S2: In situ microfluidic measurement of the fiber's Young's modulus; Video S3: Microfluidic fabrication technique of fibers by super-paramagnetic particles self-assembly; Video S4: Fiber oscillating between the two lateral walls of a microfluidic channel; Video S5: Flow through a constriction of a suspension of parallel fibers fabricated by photo-polymerization; Video S6: Flow through a constriction of a suspension of rigid perpendicular fibers fabricated by photo-polymerization; Video S7: Flow through a constriction of a suspension of flexible perpendicular fibers fabricated by photo-polymerization; Video S8: Concentrated suspension of fibers flowing through a microfluidic constriction; and Video S9: Fibers made by colloids self-assembly flowing through a constriction and forming non-permanent clusters.

Acknowledgments:

We thank Yoann Maurin for his help with the experiments on the auto-assembled fibers and Osvanny Ramos and Gerard Daccord for interesting discussions on fiber clustering. A.L. acknowledges funding from the European Research Council (ERC) under the Framework Programme Horizon 2020 of the European Commission (Grant Agreement no. 682367).

Conflicts of Interest:

The authors declare no conflict of interest.