Dima Grigoriev

Nicolai Vorobjov

COMPLEXITY OF DECIDING WHETHER A TROPICAL LINEAR PREVARIETY IS A TROPICAL VARIETY

Keywords: 2010 Mathematics Subject Classification 14T05 Tropical linear prevariety, Tropical variety, Complexity. 1

We give an algorithm, with a singly exponential complexity, deciding whether a tropical linear prevariety is a tropical linear variety. The algorithm relies on a criterion to be a tropical linear variety in terms of a duality between the tropical orthogonalization A ⊥ and the double tropical orthogonalization A ⊥⊥ of a subset A of the vector space (R ∪ {∞}) n . We also give an example of a countable family of tropical hyperplanes such that their intersection is not a tropical prevariety.

Introduction

In this paper we use the operation A ⊥ of tropical orthogonalization, applied to a subset A of a vector space (R ∪ {∞}) n , and its iteration, A ⊥⊥ , to formulate a criterion and an algorithm, deciding whether a tropical linear prevariety is a tropical linear variety.

General concepts of tropical algebra can be found in [START_REF] Joswig | Essentials of tropical combinatorics[END_REF][START_REF] Maclagan | Introduction to Tropical Geometry[END_REF][START_REF] Richter-Gebert | First steps in tropical geometry[END_REF]. Specific questions of tropical linear algebra were considered in [START_REF] Develin | On the rank of a tropical matrix[END_REF][START_REF] Develin | Tropical convexity[END_REF][START_REF] Speyer | Tropical linear spaces[END_REF][START_REF] Yu | Representing tropical linear spaces by circuits[END_REF].

In Section 1 we list basic definitions, including the concept of a tropical linear hull of a subset in (R ∪ {∞}) n . We recall a theorem, proved in [START_REF] Butkovic | An elimination method for finding all solutions of the system of linear equations over an extremal algebra[END_REF][START_REF] Gaubert | Minimal half-spaces and external representation of tropical polyhedra[END_REF], stating that any tropical linear prevariety is the tropical linear hull of a finite set of vectors. We list some properties of double orthogonalization, in particular, we prove that A ⊥⊥ is the minimal tropical linear prevariety containing the finite set A. Further in Section 1, we recall a theorem, implicitly proved in [START_REF] Speyer | Tropical linear spaces[END_REF] (see also [START_REF] Gaubert | Minimal half-spaces and external representation of tropical polyhedra[END_REF] and [START_REF] Murota | On circuit valuation of matroids[END_REF]), stating that for two mutually complementary and orthogonal linear subspaces P and Q of the vector space (C((t 1/∞ ))) n over Puiseux series, there exists a finite set A ⊂ (R ∪ {∞}) n such that tropicalizations of P and Q coincide with A ⊥ and A ⊥⊥ respectively. This theorem is essential for the main result in Section 3, and for reader's convenience we present its new short proof.

Sections 2 and 3 contain descriptions of some algorithms and estimates of their complexities. Each of these algorithms can, in principle, be modelled by a Turing machine, and complexity is understood in terms of its steps, i.e., as bit complexity.

In Section 2 we describe an algorithm, with singly exponential complexity in the number of variables, which for a given (classical) algebraic set V ⊂ (C((t 1/∞ ))) n and a point x ∈ Q n decides whether or not x belongs to the tropicalization of V , and, if it does, produces a lifting of x in V . This algorithm serves as a key subroutine for algorithms in Section 3, but also is of independent interest. An algorithm for the same problem follows from [START_REF] Jensen | An algorithm for lifting points in a tropical variety[END_REF] and apparently has doubly exponential complexity bound in the number of variables. Section 3 contains the main result of the paper: a criterion and deciding algorithms for a tropical linear prevariety to be a tropical linear variety. We propose two deciding algorithms. One has the complexity exponential in bit-sizes of rational generators of the tropical linear hull representing tropical linear prevariety and singly exponential in the number of variables. Another algorithm is polynomial in bit-size of generators. Its complexity also depends on the complexity of computing of a tropical basis (see [START_REF] Bogart | Computing tropical varieties[END_REF][START_REF] Hept | Tropical bases by regular projections[END_REF][START_REF] Joswig | The degree of a tropical basis[END_REF][START_REF] Ya | Tropical noetherity and Gröbner bases[END_REF]) of a system of (classical) multivariate polynomial equations. Apparently, the latter complexity is doubly exponential in the number of variables, in which case the complexity of our second algorithm is also doubly exponential in the number of variables.

We also describe an algorithm which for a given tropical linear variety A ⊥ produces a linear subspace P whose tropicalization coincides with A ⊥ . This algorithm has a singly exponential complexity in the number of variables.

In Section 4 we give an example of a countable family of tropical hyperplanes in (R∪{∞}) 6 such that their intersection is not a tropical prevariety. This strengthens examples in [START_REF] Dress | Algebraic, tropical, and fuzzy geometry[END_REF] (example of T. Theobald) and [START_REF] Grigoriev | Upper bounds on Betti numbers of tropical prevarieties[END_REF] about countable intersections of non-linear tropical hypersurfaces.

The extended abstract of this paper appeared in [START_REF] Grigoriev | Orthogonal tropical linear prevarieties[END_REF].

1. Preliminaries 1.1. Tropical linear prevarieties and tropical linear hulls. We use the notation R ∞ for R ∪ {∞}. We assume that for all a ∈ R the rules

a < ∞, a + ∞ = ∞, ∞ + ∞ = ∞, and, for positive a, a • ∞ = ∞ hold.
The element ∞ is a "tropical zero", being the neutral element with respect to taking minimum.

Definition 1.1 ([7]

, [START_REF] Maclagan | Introduction to Tropical Geometry[END_REF]). For a given (a 1 , . . . ,

a n ) ∈ R n ∞ , a tropical hyperplane in R n ∞ is the set of all points (x 1 , . . . , x n ) ∈ R n
∞ at which the set {x 1 + a 1 , . . . , x n + a n } has at least two minimal elements. A tropical linear prevariety in R n ∞ is the intersection of a finite number of tropical hyperplanes.

Remark 1.2. The point (∞, . . . , ∞) belongs to every tropical linear prevariety. A tropical hyperplane according to Definition 1.1 corresponds to the notion of a codimension one linear subspace in classical linear algebra. It can be identified with a special case, when a n+1 = ∞, of a more general notion of a tropical hyperplane, defined as a set of all points (x 1 , . . . , [START_REF] Maclagan | Introduction to Tropical Geometry[END_REF]). For a finite set of vectors A = {a 1 , . . . , a k } ⊂ R n ∞ define its tropical linear hull Trophull(A) as the set of all vectors in R n ∞ of the kind min

x n ) ∈ R n ∞ at which a set {x 1 + a 1 , . . . , x n + a n , a n+1 }, where a i ∈ R ∞ , 1 ≤ i ≤ n + 1, has at least two minimal elements. Definition 1.3 ([7], [25]). Vectors v = (v 1 , . . . , v n ), a = (a 1 , . . . , a n ) ∈ R n ∞ are called tropically orthogonal if among numbers v i + a i , 1 ≤ i ≤ n there are at least two minimal. Note that (∞, . . . , ∞) is tropically orthogonal to every vector a ∈ R n ∞ . For a set of vectors A = {a 1 , . . . , a k } ⊂ R n ∞ denote by A ⊥ the set of all vectors in R n ∞ tropically orthogonal to each a i , 1 ≤ i ≤ k. It is clear that {a} ⊥ is a tropical hyperplane for a vector a ∈ R n ∞ , while A ⊥ is a tropical linear prevariety when A ⊂ R n ∞ is finite. Conversely, every tropical linear prevariety in R n ∞ coincides with A ⊥ for a suitable finite set of vectors A ⊂ R n ∞ . Definition 1.4 ([7],
1≤i≤k {t i 1 n + a i },
where t 1 , . . . , t k are arbitrary elements in R ∞ , min 1≤i≤k denotes the componentwise minimum of a set of vectors, and 1 n = (1, . . . , 1) is the unit vector in R n . For an arbitrary subset X ⊂ R n ∞ define Trophull(X) as the union of sets Trophull(A) over all finite subsets A ⊂ X.

Note that Trophull(A) is the direct tropical analogy of the concept of linear hull of a finite set of vectors in classical linear algebra. It always contains the point (∞, . . . , ∞) ∈ R n ∞ , because all t i , 1 ≤ i ≤ k can be chosen to be ∞. Definition 1.5. For every partition {i 1 , . . .

, i p } ∪ {i p+1 , . . . , i n } of {1, . . . , n} a chart in R n ∞ is an open convex polyhedron C i1,...,ip := {x i1 = • • • = x ip = ∞} ∩ {x ip+1 < ∞} ∩ • • • ∩ {x in < ∞} ⊂ R n ∞ . Clearly, R n
∞ is the union of all 2 n pair-wise disjoint charts. One can extend the standard concepts of a convex polyhedron and a finite polyhedral complex to the case of the subsets of the space R n ∞ (see [START_REF] Gaubert | Minimal half-spaces and external representation of tropical polyhedra[END_REF]). Restriction of a convex polyhedron P ⊂ R n ∞ to a chart C i1,...,ip coincides with a usual convex polyhedron in R n-p translated by a vector in {0, ∞} n-p with ∞ in positions i 1 , . . . , i p . Hence, P is a finite union of translated usual convex polyhedra, and we define the dimension dim(P ) as the maximum of the dimensions of restrictions of P to all charts. The dimension of a finite polyhedral complex is defined as the maximum of dimensions of its convex polyhedra.

The following theorem directly follows from [9, Theorem 1] (part (2) of the theorem, except the complexity bound, was proved earlier in [START_REF] Butkovic | An elimination method for finding all solutions of the system of linear equations over an extremal algebra[END_REF]Proposition 2]).

Let A = {a 1 , . . . , a k } ⊂ R n ∞ be a set of vectors. Theorem 1.6.

(

⊥ ⊂ R n
∞ is the union of all convex polyhedra of a polyhedral complex in R n ∞ . Theorem 1.6, (2) states that any tropical linear prevariety A ⊥ = {a 1 , . . . , a n } ⊥ ⊂ R n ∞ coincides with the tropical linear hull of a finite subset of its vectors. This is not necessarily true for the restriction A ⊥ ∩ R n (see Example 1.11 below). 1.2. Dual tropical linear prevarieties. We extend the operation X ⊥ , introduced in Definition 1.3, so that it can be applied to arbitrary (not necessarily finite) subsets X ⊂ R n ∞ . Namely, denote by X ⊥ the set of all vectors in R n ∞ orthogonal to each a ∈ X. We will use notations X ⊥⊥ := (X ⊥ ) ⊥ and X ⊥⊥⊥ := (X ⊥⊥ ) ⊥ . Remark 1.8. Observe that by the definition, for a finite subset A ⊂ R n ∞ , the set A ⊥⊥ is an intersection of an infinite number of tropical hyperplanes in R n ∞ . As we will show in Section 4 below, not every intersection of even countable number of tropical hyperplanes is a union of cells of a finite polyhedral complex, let alone tropical linear prevariety. However, in the special case of a finite A, the set A ⊥⊥ is a tropical linear prevariety (Proposition 1.10). Lemma 1.9. For any subset X ⊂ R n ∞ we have:

(1) Trophull(X) ⊂ X ⊥⊥ ; (2) X ⊥ = X ⊥⊥⊥ .
Proof. (1) Directly follows from definitions.

(2) Inclusions X ⊂ X ⊥⊥ and X ⊥ ⊂ X ⊥⊥⊥ are trivial. The first of these inclusions implies that every x ∈ X ⊥⊥⊥ is orthogonal to every y ∈ X. Hence x ∈ X ⊥ . Proposition 1.10. Let A be a finite set of vectors in R n ∞ . Then A ⊥⊥ is the minimal (with respect to the subset relation) tropical linear prevariety containing A.

Proof. By Theorem 1.6, A ⊥ = Trophull({b 1 , . . . b N }) for some b 1 , . . . b N ∈ R n ∞ , hence A ⊥⊥ = (Trophull({b 1 , . . . b N })) ⊥ . According to [6, 7], (Trophull({b 1 , . . . b N })) ⊥ = {b 1 , . . . b N } ⊥ , which implies that A ⊥⊥ is a tropical linear prevariety.
Let C be any tropical linear prevariety containing A. 2)), we conclude that A ⊥⊥ is the minimal tropical linear prevariety containing A.

Then C = {c 1 , . . . , c M } ⊥ for some vectors c 1 , . . . , c M ∈ R n ∞ . Since c 1 , . . . , c M ∈ A ⊥ , we get the inclusion A ⊥⊥ ⊂ {c 1 , . . . , c M } ⊥ = C. Because A ⊂ A ⊥⊥ (cf. proof of Lemma 1.9 (
Lemma 12 in [START_REF] Grigoriev | Complexity of tropical and min-plus linear prevarieties[END_REF] (also Theorem 4.2 in [START_REF] Develin | On the rank of a tropical matrix[END_REF]) implies that dim(A ⊥ )+dim(A ⊥⊥ ) ≥ n for finite A ⊂ R n ∞ . The following example shows that the equality dim(A ⊥ ) = dim(A ⊥⊥ ) = n -1 is possible for some A ⊂ R n , which does not happen in classical linear algebra.

Example 1.11 (cf. [START_REF] Grigoriev | Complexity of tropical and min-plus linear prevarieties[END_REF]). Let A 0 = {a 1 , . . . , a n-1 } ⊂ R n , where

a i = (1, . . . , 1, 0 i , 1, . . . , 1, 0, 0) for 1 ≤ i ≤ n -2 and a n-1 = (1, . . . , 1, 0, 0).
It is easy to see that every vector

x = (x 1 , . . . , x n ) ∈ A ⊥ 0 ⊂ R n ∞ should have minimal elements x n-1 ,
x n , and, conversely, every vector x with minimal elements

x n-1 , x n is in A ⊥ 0 . Therefore, A ⊥ 0 = {t1 n + (c 1 , . . . , c n-2 , 0, 0)| for all 0 ≤ c i ∈ R ∞ and t ∈ R ∞ }.
From the example, we see that every vector y

= (y 1 , . . . , y n ) ∈ A ⊥⊥ 0 ⊂ R n ∞
should have minimal elements y n-1 , y n , and, conversely, every vector y with minimal elements

y n-1 , y n is in A ⊥⊥ 0 . It follows that A ⊥⊥ 0 = A ⊥ 0 . Note that dim(A ⊥ 0 ) = dim(A ⊥⊥ 0 ) = n -1.

For another property of this example, observe that

A ⊥ 0 = Trophull({b 1 , . . . , b n-1 }), where b i = (∞, . . . , ∞, 0 i , ∞, . . . , ∞, 0, 0) for 1 ≤ i ≤ n -2 and b n-1 = (∞, . . . , ∞, 0, 0).
On the other hand, take n = 3 in the example. For any finite set {v

1 , . . . , v N } ⊂ A ⊥ 0 ∩ R 3 we have A ⊥ 0 ∩ R 3 ̸ = Trophull({v 1 , . . . , v N }) ∩ R 3 . Indeed, assume, for contradiction, that there is a set of vectors V = {v 1 , . . . , v N } such that A ⊥ 0 ∩ R 3 = Trophull(V ) ∩ R 3 .
Without loss of generality, assume that v j = (c j , 0, 0) for each 1 ≤ j ≤ N , where c j ≥ 0. Denoting M := max 1≤j≤N {c j }, we consider the vector (M + 1, 0, 0

) ∈ A ⊥ 0 ∩ R 3 and prove that it is not in Trophull(V ). Indeed, if (1.1) (M + 1, 0, 0) = min 1≤j≤N (t j 1 3 + v j )
for some t 1 , . . . , t N , then, considering either second or third coordinate, we conclude that every t j ≥ 0 and at least one of them, t j0 = 0. It follows that the first coordinate of the vector min 1≤j≤N (t j 1 3 + v j ) in (1.1) is at most c j0 , which is less than M + 1.

1.3. Tropicalization of linear subspaces. Let K be an algebraically closed field of characteristic 0 and F denote the field K((t 1/∞ )) of Puiseux series over K. For an element y ∈ F different from 0, let val(y) ∈ Q denote the valuation of the element y in F, i.e., the power in the lowest term of the Puiseux series y. Separately define val(0) = ∞.

Definition 1.12 (cf. [START_REF] Maclagan | Introduction to Tropical Geometry[END_REF]). Let

f := a 1 x 1 + • • • + a n x n , where 0 ̸ = a i ∈ F for all 1 ≤ i ≤ n. The formal tropicalization of the hyperplane {f = 0} ⊂ F n is the tropical hyperplane, Tropf({f = 0}) ⊂ R n ,
{(val(x 1 ), . . . , val(x n ))| (x 1 , . . . , x n ) ∈ {f = 0} ∩ (F \ {0}) n }.
The following definition is "dual" to Definition 1.5.

Definition 1.13. For every partition {i

1 , . . . , i r } ∪ {i r+1 , . . . , i n } of {1, . . . , n} a chart in F n is a set D i1,...,ir := {x i1 = • • • = x ir = 0} ∩ {x ir+1 ̸ = 0} ∩ • • • ∩ {x in ̸ = 0} ⊂ F n .
For any X ⊂ F n we obviously have

X = ∪ {i1,...,ir} (X ∩ D i1,...,ir ),
where the union is taken over all subsets {i 1 , . . . , i r } of {1, . . . , n}. Definition 1.14 (cf. [START_REF] Maclagan | Introduction to Tropical Geometry[END_REF]). The tropicalization Trop(X ∩ D i1,...,ir ) of X ∩ D i1,...,ir is the set of all points (y 1 , . . . ,

y n ) ∈ R n ∞ such that y i1 = • • • = y ir = ∞ and (y ir+1 , . . . , y in ) belongs to the Euclidean closure in R n-r of the set {(val(x ir+1 ), . . . , val(x in ))| (x 1 , . . . , x n ) ∈ X ∩ D i1,...,ir }.
The tropicalization Trop(X) of X is defined as ∪ {i1,...,ir} Trop(X ∩ D i1,...,ir ). Remark 1.15. Definition 1.14 immediately implies that for any two sets X, Y ⊂ F n there is the inclusion Trop(X ∩ Y ) ⊂ Trop(X) ∩ Trop(Y ). The inverse inclusion ⊃ is not generally true even for linear subspaces.

Let P ⊂ F n be a linear subspace, with dim(P ) = d, and z 1 , . . . , z d ∈ P be a basis of P . Recall that Plücker coordinates of P in the Grassmanian Gr(d, F n ) are all (d × d)-minors p j1,...,j d of the matrix with rows z 1 , . . . , z d , corresponding to the columns 1 Trop(P j1,...,j d+1 ).

≤ j 1 < • • • < j d ≤ n. Any z = (z 1 , . . . , z n ) ∈ P satisfies the relation (1.2) ∑ 1≤i≤d+1 (-1) i p j1,...,ji-1,ji+1,...,j d+1 z ji = 0, for every subset of columns 1 ≤ j 1 < • • • < j d+1 ≤ n.
Let Q ⊂ F n be a linear subspace orthogonal to P with dim(Q) = n-d. According to [START_REF] Bogart | Computing tropical varieties[END_REF][START_REF] Speyer | Tropical linear spaces[END_REF], the tropicalizations Trop(P ) and Trop(Q) are tropically orthogonal, with dim(

Trop(P )) = d and dim(Trop(Q)) = n -d.
The following theorem implicitly appears in [START_REF] Speyer | Tropical linear spaces[END_REF]. Formulated in the language of valuated matroids, an analogous statement can be found in [START_REF] Murota | On circuit valuation of matroids[END_REF]. To make our exposition closed, for reader's convenience, we give another proof, using the technique of Plücker relations.

Theorem 1.17. There is a finite subset

A ⊂ R n ∞ such that Trop(P ) = A ⊥ and Trop(Q) = A ⊥⊥ .
Proof. Consider the relations (1.2) for the subspace P . For every subset 1 ≤ j 1 < • • • < j d+1 ≤ n introduce a vector p j1,...,j d+1 ∈ F n such that its j i -coordinate is (-1) i p j1,...,ji-1,ji+1,...,j d+1 for 1 ≤ i ≤ d + 1, and all the rest of coordinates are equal to 0. Then every vector in P j1,...,j d+1 is orthogonal to the vector p j1,...,j d+1 , hence every vector in ∩ {j1,...,j d+1 } P j1,...,j d+1 is orthogonal to vectors p j1,...,j d+1 for all subsets 1 ≤ j 1 < • • • < j d+1 ≤ n. By val(p j1,...,j d+1 ) denote the vector in R n ∞ obtained from p j1,...,j d+1 by taking val(•) of all non-zero coordinates and replacing all zero coordinates by ∞. As A take the set of all vectors val(p j1,...,

j d+1 ) ∈ R n ∞ for all 1 ≤ j 1 < • • • < j d+1 ≤ n. By Definition 1.12, A ⊥ = ∩ 1≤j1<•••<j d ≤n ∪ I Tropf(P j1,...,j d+1 ∩ D I ),
where the union is taken over all I ⊂ {1, . . . , n} and D I are the corresponding charts in F n . By Kapranov's Theorem, Tropf(P j1,...,j d+1 ∩ D I ) = Trop(P j1,...,j d+1 ∩ D I ), while, by Definition 1.14, ∪ I Trop(P j1,...,j d+1 ∩ D I ) = Trop(P j1,...,j d+1 ). Then, by Lemma 1.16, A ⊥ = Trop(P ).

Since the linear subspaces P and Q are orthogonal, for every y ∈ Q we have P ⊂ {y•z = 0}. Tropicalizing both sides of this inclusion, we conclude that Trop(Q) and Trop(P ) are tropically orthogonal. Hence, Trop(Q) ⊂ (Trop(P )) ⊥ = A ⊥⊥ . Vectors p j1,...,j d+1 lie in Q, since they are orthogonal to P . It follows that A ⊂ Trop(Q). By Proposition 1.10, A ⊥⊥ ⊂ Trop(Q), since Trop(Q) is a tropical linear prevariety. We conclude that A ⊥⊥ = Trop(Q).

Testing membership in a tropical variety and computing a lifting

For computational purposes, from now on we will assume that the field K = Q, thus F := Q((t 1/∞ )) is the field of formal Puiseux series in a variable t with complex algebraic coefficients.

Definition 2.1. Let x ∈ (Q ∪ {∞}) n and v ∈ F n such that Trop(v) = x. Then v is called a lifting of x.
In this section we describe an algorithm for testing membership of a given point x ∈ Q n in a tropical variety. If x does belong to the variety, the algorithm computes its lifting. The complexity of the algorithm is singly exponential in n.

For elements α 1 , . . . , α m ∈ F that are algebraic over Q(t) let η be the primitive element of the algebraic extension [START_REF] Lang | Algebra[END_REF]Theorem 4.6]). The primitive element η is defined (up to a conjugacy class) by its minimal (irreducible

Q(t)(α 1 , . . . , α m ) of the field Q(t), hence Q(t)(α 1 , . . . , α m ) = Q(t)[η] (see
) polynomial ψ ∈ Z[t][Z], i.e., ψ(η) = 0. Then α i = ζ i (η) for a polynomial ζ i ∈ Q(t)[Z], for every 1 ≤ i ≤ m. Consider (classical) polynomials f 1 , . . . , f k ∈ F[X 1 , . . . , X n ],
where the set of all coefficients α 1 , . . . , α m ∈ F of f 1 , . . . , f k is represented, as above, via a primitive element. Let

V (f 1 , . . . , f k ) := {f 1 = • • • = f k = 0} ⊂ F n .
We describe an algorithm, with singly exponential complexity, which for given f 1 , . . . , f k and a point x = (x 1 , . . . , x n ) ∈ Q n decides whether or not x belongs to Trop(V (f 1 , . . . , f k )) ⊂ R n . Moreover, if x ∈ Trop(V (f 1 , . . . , f k )) the algorithm produces a lifting of x (see Definition 2.1). According to [START_REF] Grigoriev | Polynomial complexity recognizing a tropical linear variety[END_REF], this computational problem is NP-hard.

Without loss of generality, we assume that x = 0, performing if necessary the coordinate transformation X i → X i t -xi in polynomials f j , 1 ≤ j ≤ k. We keep the same notation, f j , 1 ≤ j ≤ k, for polynomials appearing after the change of coordinates.

The rest of the algorithm consists of three parts. Firstly, it reduces testing whether 0 belongs to Trop(V (f 1 , . . . , f k )) to testing whether 0 lies in the tropicalization of one of 0-dimensional algebraic sets. Next, the algorithm does the latter testing. Finally, in the case of positive result, it constructs the lifting of 0.

2.1. Reduction to 0-dimensional algebraic sets. Applying algorithms from [START_REF] Chistov | An algorithm of polynomial complexity for factoring polynomials, and determination of the components of a variety in a subexponential time[END_REF][START_REF] Grigoriev | Polynomial factoring over a finite field and solving systems of algebraic equations[END_REF], represent V (f 1 , . . . , f k ) as the finite union of its irreducible components over

Q(t), V (f 1 , . . . , f k ) = ∪ ν V ν .
Each irreducible component is represented in two forms: by a system of equations with coefficients in Q(t), and by a generic point (a point such that the field generated by its coordinates has the transcendence degree, over the field generated by the coefficients of the equations, equal to the dimension of the component). More precisely, a generic point of an irreducible component V ν , with dim(V ν ) = s, is represented as follows. Among coordinates X 1 , . . . , X n a transcendence basis is chosen, let it be X 1 , . . . , X s . Then coordinates X s+1 , . . . , X n are algebraic over Q(X 1 , . . . , X s )(t), and algorithms from [START_REF] Chistov | An algorithm of polynomial complexity for factoring polynomials, and determination of the components of a variety in a subexponential time[END_REF][START_REF] Grigoriev | Polynomial factoring over a finite field and solving systems of algebraic equations[END_REF] describe the primitive element µ of the extension Q(X 1 , . . . , X n )(t) as µ = λ s+1 X s+1 +• • •+λ n X n for positive integers λ s+1 , . . . , λ n , and by its minimal polynomial χ ∈ Q(X 1 , . . . , X s )(t) [Z]. Each coordinate X i , s + 1 ≤ i ≤ n is then represented by a polynomial expression in µ with coefficients in Q(X 1 , . . . , X s )(t).

Let Y 0 , . . . , Y n be new variables. Fix a component V ν with dim(V ν ) > 0, and consider the algebraic set V ν defined by the same equations as V ν over the field

Q(Y 0 , Y 1 , . . . , Y n )((t 1/∞ )). Let W ν := V ν ∩    Y 0 + ∑ 1≤i≤n Y i X i = 0    .
Then [18, Proposition 4.6] (see also [START_REF] Osserman | Lifting tropical intersections[END_REF]Theorem 2.7.8], [START_REF] Jensen | Stable intersections of tropical varieties[END_REF]Theorem 3.5]) implies that if 0 ∈ Trop(V ν ), then 0 ∈ Trop( W ν ). The converse statement is obvious. Let dim(V ν ) = s. Introducing new sets of variables, Y p,q , 0 ≤ q ≤ n, where 1 ≤ p ≤ s, and adding equations Y p,0 + ∑ 1≤i≤n Y p,i X i = 0 to the system of equations defining V ν , we will obtain a system of equations defining a zero-dimensional algebraic set U ν over the field Q({Y p,q } 1≤p≤s,0≤q≤n )((t 1/∞ )). Find all points in U ν using algorithms from [START_REF] Chistov | An algorithm of polynomial complexity for factoring polynomials, and determination of the components of a variety in a subexponential time[END_REF][START_REF] Grigoriev | Polynomial factoring over a finite field and solving systems of algebraic equations[END_REF]. The algorithm will conclude that 0 ∈ Trop(V ν ) if and only if for some point v ∈ U ν its tropicalization is 0. We now describe how the algorithm checks the latter condition.

Testing existence of the lifting of a point in 0-dimensional algebraic set.

Algorithms from [START_REF] Chistov | An algorithm of polynomial complexity for factoring polynomials, and determination of the components of a variety in a subexponential time[END_REF][START_REF] Grigoriev | Polynomial factoring over a finite field and solving systems of algebraic equations[END_REF] represent each point in v = (v 1 , . . . , v n ) ∈ U ν as follows. For every 1 ≤ i ≤ n the coordinate v i is represented as v i = ξ i (θ), where θ is a root of an irreducible polynomial φ ∈ Z({Y p,q } p,q )(t)[Z], with deg Z (φ) = r, while the expression ξ i (θ) is of the form 1) is the series of terms containing t in positive degree, while a i is the sum of terms of degrees in t at most 0. More precisely, let α be the smallest integral (possibly negative) degree in t of the rational in t coefficients in the expression ξ i . Let β be the degree of the first term in the Puiseux series θ = θ(t). For a positive integer γ ≥ β, let Θ be the sum of all consecutive terms in the Puiseux series θ starting with the term of degree β and ending with the term of the smallest degree not less than γ.

ξ i (θ) = 1 b i ∑ 0≤ℓ<r c i,ℓ θ ℓ , where b i , c i,ℓ ∈ Z[{Y p,q } p,q ](t). We can represent ξ i (θ) in a form ξ i (θ) = a i + R(t), where R(t) = o(
If β > 0, then choose γ to be the smallest integer such that α + γ ≥ 0. Then ξ i (Θ) contains all terms in ξ i (θ) having non-positive degrees in t.

If β ≤ 0, then Θ r-1 contains the term with the degree not less than α + (r -2)β + γ, hence choosing γ to be the smallest integer such that α + (r -2)β + γ ≥ 0, we guarantee that ξ i (Θ) contains all terms in ξ i (θ) having non-positive degrees in t.

Using the algorithm from [START_REF] Chistov | Polynomial complexity of Newton-Puiseux algorithm[END_REF], find sum Θ of all first consecutive terms in the Puiseux expansion of θ in t up to the term of the smallest degree not less than γ. Substituting Θ into ξ i , we compute the sum a i of terms in ξ i (θ) of degrees in t at most 0. Let for each i, among the terms in a i , the lowest degree in t be 0, i.e., a i is independent of t. Then we conclude that 0 belongs to Trop(V (f 1 , . . . , f k )) ⊂ R n . If among the terms in a i the lowest degree in t is different from 0 for some i, then Trop(v) ̸ = 0. If the latter condition holds for every point v ∈ U ν , then 0 ̸ ∈ Trop(V ν ).

2.3.

Constructing the lifting of a point. To find a lifting of 0 (in case of a i independent of t for all i), observe that for each i the element a i belongs to a finite extension of the field Q({Y p,q } p,q ), and is defined by a polynomial expression via the primitive element of this extension, while the primitive element is defined by its minimal polynomial (cf. representation of algebraic elements α 1 , . . . α m at the beginning of this section). All coefficients in the polynomial expressions and the minimal polynomial belong to Q({Y p,q } p,q ). Choose a point y ∈ Z s(n+1) such that (1) after the substitution y in variables {Y p,q } p,q neither of the denominators of these coefficients vanish; (2) after the substitution y in variables {Y p,q } p,q neither of the numerators at leading terms of minimal polynomials vanish. Coordinates of y can be taken to be non-negative integers not exceeding the degrees of the polynomials mentioned in (1), ( 2). Thus, one can estimate the complexity of choosing point y by the bound on the degrees of these polynomials which is provided below.

The condition (2) implies that after the substitution of y in (Y 1 , . . . , Y s(n+1) ) each minimal polynomial may become reducible but its degree does not change.

Recall that each coordinate

v i in v = (v 1 , . . . , v n ) ∈ U ν is represented by polyno- mials φ, ξ i ∈ Q({Y p,q } p,q )(t)[Z]
. Substituting in coefficients of these polynomials the vector of variables (Y 1 , . . . , Y s(n+1) ) by y, we obtain a representation of a point in (Q(t)) n which is a lifting of 0. This ends the description of the algorithm.

Complexity of the algorithm.

Let d = max 1≤j≤k deg X1,...,Xn (f j ) and δ be the maximum among the degrees in t of polynomials ψ, ζ i , which define coefficients α i of polynomials f j . Let M be the maximum among the common denominator of rational numbers x 1 , . . . , x n and the absolute values of their numerators. By the Bezout Theorem, the degree of the algebraic set V := V (f 1 , . . . , f k ) does not exceed D := d n . After the change of coordinates X i → X i t -xi in polynomials f j , 1 ≤ j ≤ k, the bound δ will be multiplied a positive number not exceeding M 2 .

Algorithms in [START_REF] Chistov | An algorithm of polynomial complexity for factoring polynomials, and determination of the components of a variety in a subexponential time[END_REF][START_REF] Grigoriev | Polynomial factoring over a finite field and solving systems of algebraic equations[END_REF], applied to intersections of the irreducible components of V (considered over the field

Q({Y p,q } p,q )((t 1/∞ ))) with s hyperplanes    Y p,0 + ∑ 1≤i≤n Y p,i X i = 0    ,
produce a union of 0-dimensional irreducible (over Q({Y p,q } p,q )(t)) algebraic sets (conjugacy classes) each defined by some polynomials

g 1 , . . . , g r ∈ Q({Y p,q } p,q )(t)[X 1 , . . . , X n ],
where r ≤ D n , of degrees at most D n 2 with respect to O(n 2 ) variables {Y p,q } p,q , and with coefficients represented by univariate polynomials φ, ξ i of degrees at most D 2 with respect to Z and at most δM 2 D n 2 with respect to t. Complexity of the algorithm from [START_REF] Chistov | Polynomial complexity of Newton-Puiseux algorithm[END_REF], applied to polynomials φ, ξ i , is polynomial in δM D n 2 and bit-sizes of their rational coefficients.

As a result, the complexity of the algorithm is polynomial in bit-sizes of rational coefficients of polynomials ψ, ζ i , which define coefficients α i of the input polynomials f j , in the number k of these polynomials, in δM , and in D n 4 = d n 5 .

We now summarise the results of this section.

Theorem 2.2.

There is an algorithm which for given polynomials f 1 , . . . , f k ∈ F[X 1 , . . . , X n ] and a point x = (x 1 , . . . , x n ) ∈ Q n decides whether or not x belongs to

Trop(V (f 1 , . . . , f k )) ⊂ R n . Moreover, if x ∈ Trop(V (f 1 , . . . , f k ))
the algorithm produces a lifting of x.

To describe the complexity, let d = max 1≤j≤k deg X1,...,Xn (f j ), let δ be the maximum among the degrees in t of polynomials ψ, ζ i , which define coefficients α i of polynomials f j . Let M be the maximum among the common denominator of rational numbers x 1 , . . . , x n and absolute values of numerators. Then the complexity of the algorithm is polynomial in bit-sizes of rational coefficients of ψ, ζ i , in the number k of polynomials f j , in δM , and in d n 5 . Remark 2.3. The part of algorithm in the proof of Theorem 2.2, which checks whether 0 is a tropicalization of a point in U ν , actually computes the tropicalization of the (0-dimensional) U ν . Since the dimension of a (classical) algebraic set in F n coincides with the dimension of its tropicalization, the same procedure can be used to compute the tropicalization of any 0-dimensional algebraic set.

Remark 2.4. In case of tropical linear varieties (d = 1), a deciding algorithm, with complexity similar to the one in Theorem 2.2, is given in [START_REF] Grigoriev | Polynomial complexity recognizing a tropical linear variety[END_REF].

Criterion and deciding algorithm for being a tropical linear variety

Let A ⊂ (Q∪{∞}) n be a set of k vectors with bit-sizes of coordinates not exceeding L. Since A ⊥ and A ⊥⊥ are tropical linear prevarieties (see Proposition 1.10), Theorem 1.6 implies that A ⊥ = Trophull({x 1 , . . . , x p }) and A ⊥⊥ = Trophull({y 1 , . . . , y q }) for some vectors x 1 , . . . , x p , y 1 , . . . , y q ∈ (Q ∪ {∞}) n . Moreover, the algorithm, stated in Theorem 1.6, computes vectors x 1 , . . . , x p , with complexity polynomial in L, n k , and vectors y 1 , . . . , y q with complexity polynomial in L, n n k . Theorem 3.1. Let A ⊥ and A ⊥⊥ be the tropical linear hulls of the points x 1 , . . . , x p and y 1 , . . . , y q respectively as above. The following three statements are equivalent.

(1) There exist mutually complementary and orthogonal linear subspaces P, Q in F n such that A ⊥ = Trop(P ), and A ⊥⊥ = Trop(Q) (in particular, A ⊥ , A ⊥⊥ are tropical linear varieties). (2) There exist liftings v 1 , . . . v p , w 1 , . . . , w q ∈ F n of vectors x 1 , . . . x p , y 1 , . . . , y q ∈ (Q ∪ {∞}) n respectively, such that (v i , w j ) = 0 for all 1 ≤ i ≤ p, 1 ≤ j ≤ q.

(3) A ⊥ is a tropical linear variety.

For the proof of this theorem we recall the following definition.

Finally, implication (1) ⇒ (3) is trivial. To prove (3) ⇒ (1) notice that since there is a subspace P ⊂ F n such that Trop(P ) = A ⊥ , by Corollary 1.18, Trop(Q) = A ⊥⊥ for the subspace Q complement orthogonal to P .

Corollary 3.3.

There is an algorithm which for given tropical linear prevarieties A ⊥ = Trophull({x 1 , . . . , x p }) and A ⊥⊥ = Trophull({y 1 , . . . , y q }), where x 1 , . . . , x p , y 1 , . . . , y q ∈ (Q ∪ {∞}) n , decides whether A ⊥ is a tropical linear variety. The complexity of the algorithm is exponential in bit-sizes of rational coordinates of vectors x i , y j , 1 ≤ i ≤ p, 1 ≤ j ≤ q, and in n, p, q.

Proof. The input of the algorithm under construction is the set

{x 1 , . . . , x p , y 1 , . . . , y q } ⊂ (Q ∪ {∞}) n .
Consider, over F * ∼ = F \ {0}, the system of equations (3.1)

∑ 1≤ν≤n V iν W jν = 0 for all 1 ≤ i ≤ p, 1 ≤ j ≤ q such that x iν ̸ = ∞ and y jν ̸ = ∞ for all 1 ≤ ν ≤ n,
where (V i1 , . . . , V in ), (W j1 , . . . , W jn ) are vectors of variables.

Consider vectors x i , y j , 1 ≤ i ≤ p, 1 ≤ j ≤ q in the input, from which coordinates x iν and y jν with either x iν = ∞ or y jν = ∞ are removed. Applying Theorem 2.2, the algorithm checks whether there exist liftings of these vectors, satisfying the system of equations (3.1). If no, then A ⊥ is not a tropical linear variety, by Theorem 3.1. Otherwise, let P be the linear hull of vectors v 1 , . . . v p such that in every v i each coordinate corresponding to x iν ̸ = ∞ is the lifting v iν , while each coordinate corresponding to x iν = ∞ is 0. Similarly, let Q be the linear hull of vectors w 1 , . . . w q such that in every w j each coordinate corresponding to y jν ̸ = ∞ is the lifting w jν , while each coordinate corresponding to y jν = ∞ is 0. Then, by Theorem 3.1, P and Q are mutually complementary and orthogonal linear subspaces of F n , while A ⊥ = Trop(P ) and A ⊥⊥ = Trop(Q). In particular, A ⊥ and A ⊥⊥ are tropical linear varieties.

Theorem 2.2 implies that the complexity of the algorithm is exponential in bitsizes of rational coordinates of vectors x i , 1 ≤ i ≤ p, y j , 1 ≤ j ≤ q, and in n, p, q. Remark 3.4. There is an alternative algorithm for the problem described in Corollary 3.3. Using [START_REF] Bogart | Computing tropical varieties[END_REF][START_REF] Hept | Tropical bases by regular projections[END_REF] or [START_REF] Ya | Tropical noetherity and Gröbner bases[END_REF], it constructs a tropical basis of the system of equations (3.1), which is a finite set of polynomials H ℓ , with integer coefficients and (p + q)n variables V iν , W jν such that x iν ̸ = ∞ and y jν ̸ = ∞. (See a detailed definition and properties of a tropical basis in [START_REF] Maclagan | Introduction to Tropical Geometry[END_REF]Section 2.6].) The algorithm checks whether, for all H ℓ , vectors x 1 , . . . x p , y 1 , . . . , y q , from which coordinates x iν and y jν with either x iν = ∞ or y jν = ∞ are removed, satisfy tropicalizations Trop(H ℓ ). If yes, then, by the definition of tropical basis, there exist liftings v iν , w jν ∈ F * of all x iν ̸ = ∞, y jν ̸ = ∞ respectively, which satisfy the system (3.1). Then the algorithm continues as the algorithm from Corollary 3.3. If vectors x 1 , . . . x p , y 1 , . . . , y q from which coordinates x iν and y jν with either x iν = ∞ or y jν = ∞ are removed, do not satisfy Trop(H ℓ ) for all H ℓ , then A ⊥ is not a tropical linear variety, by Theorem 3.1.

The complexity of this algorithm is polynomial in the bit-size of rational coordinates of vectors x i , 1 ≤ i ≤ p, y j , 1 ≤ j ≤ q. The complexity also depends on the complexity of computing of a tropical basis for (3.1). Apparently, the latter complexity is doubly exponential in n, p, q, though we are unaware of a proof of this bound in literature. Note that there is a doubly exponential upper bound on the degree of a tropical basis [START_REF] Joswig | The degree of a tropical basis[END_REF] (cf. also [START_REF] Markwig | Computing Tropical Varieties Over Fields with Valuation[END_REF][START_REF] Görlach | Detecting tropical defects of polynomial equations[END_REF]).

Corollary 3.5.

There is an algorithm which for tropical linear prevarieties A ⊥ = Trophull({x 1 , . . . , x p }) and A ⊥⊥ = Trophull({y 1 , . . . , y q }), where x 1 , . . . , x p , y 1 , . . . , y q ∈ (Q∪{∞}) n , produces bases of linear subspaces P and Q, such that A ⊥ = Trop(P ) and A ⊥⊥ = Trop(Q), in case these subspaces exist. The complexity of the algorithm is exponential in bit-sizes of rational coordinates of vectors x i , 1 ≤ i ≤ p, y j , 1 ≤ j ≤ q, and in n, p, q.

Proof. Apply the algorithm from Theorem 2.2 to vectors x i , y j , 1 ≤ i ≤ p, 1 ≤ j ≤ q, from which coordinates x iν and y jν with either x iν = ∞ or y jν = ∞ are removed, and to the system (3.1). The algorithm from Theorem 2.2 will either produce liftings v iν , w jν ∈ F * of all x iν ̸ = ∞, y jν ̸ = ∞ respectively, which satisfy (3.1), or will indicate that liftings do not exist, i.e., vectors x i , y j with removed coordinates do not belong to the tropicalization of (3.1). If liftings exist, then P is the linear hull of vectors v 1 , . . . v p such that in every v i each coordinate corresponding to x iν ̸ = ∞ is the lifting v iν of x iν , while each coordinate corresponding to x iν = ∞ is 0. Similarly, Q is the linear hull of vectors w 1 , . . . w q such that in every w j each coordinate corresponding to y jν ̸ = ∞ is the lifting w jν of y jν , while each coordinate corresponding to y jν = ∞ is 0. Herewith, all coordinates of vectors v i , w j are Puiseux series in Q((t 1/∞ )) represented as algebraic elements over the field Q(t), as described in the proof of Theorem 2.2. Choosing maximal linearly independent vectors among v 1 , . . . v p (respectively, among w 1 , . . . w q ), we get a basis of P (respectively, of Q).

Theorem 2.2 implies that the complexity of this algorithm is exponential in the bit-size of rational coordinates of vectors x i , 1 ≤ i ≤ p, y j , 1 ≤ j ≤ q, and exponential in n, p, q.

Infinite intersections of tropical linear prevarieties

By the definition, the intersection of a finite number of tropical hyperplanes is a tropical linear prevariety. In this section we give an example of a countable family of tropical hyperplanes in R 6 ∞ such that their intersection is not a finite union of convex polyhedra, in particular, not a tropical prevariety. This strengthens examples in [START_REF] Dress | Algebraic, tropical, and fuzzy geometry[END_REF] (example of T. Theobald) and [START_REF] Grigoriev | Upper bounds on Betti numbers of tropical prevarieties[END_REF], in which intersections of a countable families of tropical (non-linear) prevarieties were shown not to be finite unions of convex polyhedra.

Choose a sequence {ε i } ∞ i=1 of pair-wise distinct real numbers ε i such that 0 < ε i < 1/4, and consider the tropical hyperplane L i ⊂ R 6 ∞ defined by the set L i (x 1 , x 2 , y 1 , y 2 , z 1 , z 2 ) := {-i + x 1 , -i + x 2 , -i/2 -ε i + y 1 , -i/2 + y 2 , z 1 , z 2 } (see Definition 1.1).

Let

M := ∩ 1≤i<∞ L i ⊂ R 6 ∞ .
Proposition 4.1. The set M ∩ R 6 is not a finite union of convex polyhedra. In particular, M is not a tropical prevariety.

Corollary 1 . 18 .

 118 Let P, Q ⊂ F n be orthogonal complements of one another andTrop(P ) = A ⊥ . Then Trop(Q) = A ⊥⊥ . Proof. By Theorem 1.17, there is a finite subset B ⊂ R n ∞ such that Trop(P ) = B ⊥ and Trop(Q) = B ⊥⊥ . Since Trop(P ) = A ⊥ , we get A ⊥ = B ⊥ , hence Trop(Q) = A ⊥⊥ .Remark 1.19. Corollary 1.18 implies, in particular, that in Example 1.11 the tropical linear prevariety A ⊥ 0 is not a tropical linear variety.

b N } ⊂ Q n ∞ . The complexity of this algorithm is polynomial in L and n k . Bit-sizes of coordinates of the computed vectors b 1 , . . . , b N do not exceed L + log k, while N = O(n k ). Corollary 1.7. Every tropical linear prevariety A

	1) The set Trophull(A) is a union of all convex polyhedra of
	a polyhedral complex in R n ∞ . (2) For the tropical linear prevariety A ⊥ ⊂ R n ∞ there exists a finite set of vec-tors {b 1 , . . . , b N } ⊂ R n ∞ such that A ⊥ = Trophull({b 1 , . . . , b N }). More-
	over, there is an algorithm which for a given set {a 1 , . . . , a k } of vectors
	in Q n ∞ , with bit-sizes of coordinates not exceeding L, computes the set
	{b 1 , . . . ,

  Note that the relations in (1.2) are independent of the choice of a basis in P .Denote the set of points z satisfying (1.2) by P j1,...,j d+1 .The following statement is a strengthening for R ∞ of [30, Proposition 4.2] (also[START_REF] Maclagan | Introduction to Tropical Geometry[END_REF] Theorem 4.3.17]), and can be proved analogously.

	Lemma 1.16.	∩
	(1.3)	Trop(P ) =
		j1,...,j d+1

Acknowledgements

We thank M. Joswig, N. Kalinin, H. Markwig, and T. Theobald for useful discussions, and anonymous referees for constructive remarks and suggestions. Part of this research was carried out during our joint visit in September 2017 to the Hausdorff Research Institute for Mathematics at Bonn University, under the program Applied and Computational Algebraic Topology, to which we are very grateful. D. Grigoriev was partly supported by the RSF grant 16-11-10075.

Definition 3.2 ([6]

). A square (r×r)-matrix with elements m ij ∈ R ∞ , 1 ≤ i, j ≤ r, is called tropically singular if the minimum among {m 1σ1 + • • • + m rσr | for all permutations (σ 1 , . . . , σ r ) of (1, . . . , r)} is attained on at least two elements, and tropically non-singular otherwise. The tropical rank, trk(M ), of a matrix M is the largest integer r such that this matrix has a non-singular (r × r)-submatrix.

Proof of Theorem 3.1. Implication (1) ⇒ (2). Suppose there exist subspaces P, Q ⊂ F n as in [START_REF] Akian | Tropical polyhedra are equivalent to mean payoff games[END_REF]. Then arbitrary liftings v 1 , . . . , v p ∈ P and w 1 , . . . , w q ∈ Q, of x 1 , . . . , x p and y 1 , . . . , y q respectively, satisfy [START_REF] Bogart | Computing tropical varieties[END_REF].

We now prove implication (2) ⇒ (1). Let P (respectively, Q) be the linear hull of v 1 , . . . , v p (respectively, of w 1 , . . . , w q ). Since (v i , w j ) = 0 for all 1 ≤ i ≤ p, 1 ≤ j ≤ q, each vector v ∈ P is orthogonal to each vector w j , in particular, subspaces P and Q are orthogonal. Hence, Trop(v) ⊥ y j for each 1 ≤ j ≤ q. Then Trop(v) ⊥ y for each y ∈ Trophull({y 1 , . . . , y q }) = A ⊥⊥ , thus Trop(v) ∈ A ⊥⊥⊥ . By Lemma 1.9, (2), this means Trop(v) ∈ A ⊥ , thus Trop(P ) ⊂ A ⊥ . Similarly, we can prove that Trop(Q) ⊂ A ⊥⊥ .

We prove the inclusion A ⊥ ⊂ Trop(P ) by restricting it to charts in R n ∞ (see Definition 1.5). Choose a chart C I in R n ∞ , where I ⊂ {1, . . . , n}, in R n , and the corresponding chart

For each 1 ≤ j ≤ n let α 1j , . . . , α pj be coefficients of lowest degrees in Puiseux series v 1j t r1 , . . . , v pj t rp respectively. Choose s 1 , . . . , s p ∈ C so that

In case when in the representation x = min 1≤i≤p {r i 1 n + x i } elements r i belong to R, consider a sequence of points

Taking the union over all subsets I ⊂ {1, . . . , n}, in the inclusions

Similarly, we can prove that A ⊥⊥ ⊂ Trop(Q). We conclude that A ⊥ = Trop(P ) and A ⊥⊥ = Trop(Q). We now prove that subspaces P and Q are mutually complementary. In [START_REF] Grigoriev | Complexity of tropical and min-plus linear prevarieties[END_REF] it is shown that dim(A ⊥ ) + dim(A ⊥⊥ ) ≥ n. Hence, by [6, Theorem 4.2], trk({x 1 , . . . , x p }) + trk({y 1 , . . . , y q }) = dim(A ⊥ ) + dim(A ⊥⊥ ) ≥ n.

On the other hand, [START_REF] Develin | On the rank of a tropical matrix[END_REF] implies that rk({v 1 , . . . , v p }) ≥ trk({x 1 , . . . , x p }) and rk({w 1 , . . . , w p }) ≥ trk({y 1 , . . . , y q }).

It follows that rk({v 1 , . . . , v p })+rk({w 1 , . . . , w p }) ≥ n, hence P and Q are mutually complementary, given that they are orthogonal.

Proof. Choose an integer 2 ≤ j < ∞ and consider the point

A direct calculation shows that p j ∈ M because minima in the set L i (p j ) are attained at

Moreover, the same calculation shows that any point p j +(δ 1 , δ 1 , δ 2 , δ 2 , δ 3 , δ 3 ), for all sufficiently small positive |δ 1 |, |δ 2 |, |δ 3 |, also belongs to M . Hence, a neighbourhood of p j in M contains a 3-cube, denote it by C j .

Conversely, a neighbourhood of p j in M is contained in C j . Indeed, consider a point q j ∈ M which is sufficiently close to p j in M . It can be represented as

for some small positive |α ℓ |, 1 ≤ ℓ ≤ 6. Since q j ∈ L j-1 ∩ L j ∩ L j+1 , we conclude that each of the following three sets has at least two minimal elements:

(1)

are small, minimal (hence equal) elements in (1) are α 5 , α 6 , in (2) they are -1/4 + α 3 , -1/4 + α 4 , and in (3) they are -1 + α 1 , -1 + α 2 . It follows that α 1 = α 2 , α 3 = α 4 , and α 5 = α 6 , hence q j ∈ C j .

We have proved that the 3-cube C j is a neighbourhood of p j in M . By a direct calculation, any two points of the kind

where i ̸ = j and all a ℓ , b ℓ ̸ = ∞, 1 ≤ ℓ ≤ 3, are distinct due to ε i ̸ = ε j . This means that affine hulls of cubes C i and C j are disjoint in R 6 for any two i ̸ = j, 2 ≤ i, j < ∞, and therefore, M ∩ R 6 is not a finite union of convex polyhedra. Since every tropical prevariety is a finite polyhedral complex (see, e.g., [START_REF] Maclagan | Introduction to Tropical Geometry[END_REF]), M is not a tropical prevariety.

CNRS, Mathématiques, Université de Lille, Villeneuve d'Ascq, 59655, France Email address: dmitry.grigoryev@math.univ-lille1.fr Department of Computer Science, University of Bath, Bath BA2 7AY, England, UK Email address: nnv@cs.bath.ac.uk


D Kundys

A Cascales

A S Makhort

H Majjad

F Chevrier

B Doudin

A Fedrizzi

B Kundys

Optically Rewritable Memory in a Graphene-Ferroelectric-Photovoltaic Heterostructure

Keywords:

Achieving optical operation of logic elements, especially those that involve two-dimensional (2D) layers, can begin the long-awaited era of optical computing. However, efficient optical modulation of the electronic properties of 2D materials, including the rewritable memory effect, is currently lacking. Here we report a fully optical control of the conductivity of graphene with write-erase operation yet under ultralow optical fluence. The competition between light-induced charge generation in a ferroelectric-photovoltaic substrate and relaxation processes provides the selective photocarrier-trapping control affecting the doping of the 2D overlayer. These findings open the way to photonic control of 2D devices for all-optical modulators and a variety of all-optical logic circuits, memories, and field-effect transistors.

I. INTRODUCTION

One of the key challenges of today's technology is to overcome the slowing down of Moore's law for circuit miniaturization, which is approaching the single-atom level [START_REF] Waldrop | The chips are down for Moore's law[END_REF]. The development of new device paradigms is therefore crucial. In that respect, single-atom layer structures with unique electronic properties [START_REF] Castro Neto | The electronic properties of graphene[END_REF] allow atomic scale control [START_REF] Bao | Graphene photonics, plasmonics, and broadband optoelectronic devices[END_REF] that combines electronic and photonic degrees of freedom. In particular, the high sensitivity of two-dimensional (2D) layers to the presence of nearby electric charges can be exploited in their combination with electric-charge-tunable environments. The most-successful materials in that respect are ferroelectric (FE) compounds, which provide electric-field-driven large-scale changes in charge doping related to bistable 180°polarization switching [START_REF] Zheng | Gate-controlled nonvolatile graphene-ferroelectric memory[END_REF][START_REF] Zheng | Graphene Field-Effect Transistors with Ferroelectric Gating[END_REF][START_REF] Raghavan | Long-term retention in organic ferroelectric-graphene memories[END_REF][START_REF] Jandhyala | Grapheneferroelectric hybrid devices for multi-valued memory system[END_REF][START_REF] Hwang | Novel multi-bit memory device using metal/PVDF-TrFE/graphene stack[END_REF][START_REF] Hong | Unusual resistance hysteresis in n-layer graphene field effect transistors fabricated on ferroelectric Pb(Zr 02 Ti 08 )O 3[END_REF][START_REF] Baeumer | Tunable carrier type and density in graphene/PbZr 02 Ti 08 O 3 hybrid structures through ferroelectric switching[END_REF][START_REF] Song | Robust bi-stable memory operation in single-layer graphene ferroelectric memory[END_REF][START_REF] Si | Ferroelectric field-effect transistors based on MoS 2 and CuInP 2 S 6 Two-dimensional van der waals heterostructure[END_REF][START_REF] Yusuf | Local control of the resistivity of graphene through mechanically induced switching of a ferroelectric superlattice[END_REF][START_REF] Lipatov | Polarization-Dependent electronic transport in graphene/Pb(Zr, Ti)O 3 ferroelectric field-effect transistors[END_REF] or a variety of possible intermediate states that are associated with the existence of a FE-domain structure [START_REF] Iurchuk | Multi-state and non-volatile control of graphene conductivity with surface electric fields[END_REF][START_REF] Baeumer | Ferroelectrically driven spatial carrier density modulation in graphene[END_REF][START_REF] Zelenovskii | Effect of ferroelectric domains on electric properties of single layer graphene[END_REF]. As the demand for operating speeds approaches photonic regimes [START_REF] Ducournau | Silicon photonics targets terahertz region[END_REF][START_REF] Haffner | All-plasmonic Mach-Zehnder modulator enabling optical high-speed communication at the microscale[END_REF], the electric control, however, must be replaced by optical control to enable fast and low-power-consumption data processing [START_REF] Haffner | All-plasmonic Mach-Zehnder modulator enabling optical high-speed communication at the microscale[END_REF]. To accomplish this transition fully, current integrated photonics urgently needs to achieve optical functionalities that can efficiently interface photonic and electronic degrees of freedom for active and passive elements performing data processing and photon routing for memory read-write integrated elements [START_REF] Cheben | Subwavelength integrated photonics[END_REF][START_REF] Thomas | Nanomechanical electro-optical modulator based on atomic heterostructures[END_REF][START_REF] Thomas | Strong coupling of diffraction coupled plasmons and optical waveguide modes in gold stripedielectric nanostructures at telecom wavelengths[END_REF]. *

kundysATipcms.fr

The photopolarization properties of FE compounds also make them exceptional components for 2D hybrid structures, where large changes in charge density can be induced optically. Indeed, the possibility of optical control in 2D-FE hybrid structures has recently gained increasing interest [START_REF] Wang | Ultrasensitive and broadband MoS 2 photodetector driven by ferroelectrics[END_REF][START_REF] Lipatov | Optoelectrical molybdenum disulfide (MoS 2 )-ferroelectric memories[END_REF][START_REF] Gorecki | Optical gating of graphene on photoconductive Fe:LiNbO3[END_REF][START_REF] Li | Optical control of polarization in ferroelectric heterostructures[END_REF][START_REF] Wu | MoTe 2 p-n homojunctions defined by ferroelectric polarization[END_REF]. However, to realize the full potential of the photopolarization properties of 2D -FE heterostructures, one should also take into account the possible existence of the photovoltaic effect in ferroelectrics [START_REF] Butler | Ferroelectric materials for solar energy conversion: Photoferroics revisited[END_REF][START_REF] Paillard | Photovoltaics with ferroelectrics: Current status and beyond[END_REF][START_REF] Grinberg | Perovskite oxides for visible-light-absorbing ferroelectric and photovoltaic materials[END_REF][START_REF] Lopez-Varo | Physical aspects of ferroelectric semiconductors for photovoltaic solar energy conversion[END_REF][START_REF] Matsuo | Gap-state engineering of visible-light-active ferroelectrics for photovoltaic applications[END_REF][START_REF] Spanier | Power conversion efficiency exceeding the shockley-queisser limit in a ferroelectric insulator[END_REF][START_REF] Inoue | Giant photovoltaic effect of ferroelectric domain walls in perovskite single crystals[END_REF]. The photopolarization in this case can additionally benefit from free photocarriers, as long as the light-excitation energy is close to the band gap. It is important to note that, in contrast to the slower thermal-pyroelectric effects, photopolarization of photovoltaic origin offers ultrafast (terahertz) operation [START_REF] Takahashi | Terahertz Radiation by an Ultrafast Spontaneous Polarization Modulation of Multiferroic BiFeO 3 Thin Films[END_REF][START_REF] Chen | Ultrafast terahertz gating of the polarization and giant nonlinear optical response in BiFeO 3 thin films[END_REF] and can consist of both reversible and irreversible parts [START_REF] Makhort | Photovoltaic effect and photopolarization in Pb[END_REF][START_REF] Quattropani | Tuning photovoltaic response in Bi 2 FeCrO 6 films by ferroelectric poling[END_REF]. Such effects can offer unprecedented functionalities for all-optical control not only preserving nonvolatility, which is indispensable for memories, but also offering optical tunability of electronic and plasmonic properties in 2D -FE-heterostructure devices. In this work repetitive optical writing and optical erasing of graphene resistive states in a graphene overlayer based on the photopolarization response of the photovoltaic-ferroelectric substrate. The distinct physical mechanism involves delicate interplay between screening of remanent polarization produced by the photogenerated carriers, on the one hand, and the amount of trapped charges, on the other hand. Such a demonstration of both writing and erasing operation of graphene resistive states performed all optically is much needed, but seems to be 1 Graphene-Ferroelectric-Photovoltaic Graphene-Ferroelectric-Photovoltaic Optical writing and erasing Optical writing and erasing absent from the literature. Our approach also allows an alloptical 87% conductivity change in a 2D graphene layer obtained totally by optical means with exceptional efficiency of the graphene light-matter interaction (fluence 6 mJ/cm 2 ). Furthermore, the observed rate of conductivity change is at least 3 orders of magnitude faster than previously reported [START_REF] Gorecki | Optical gating of graphene on photoconductive Fe:LiNbO3[END_REF] and has potential for further improvement. This method opens the prospect for ultraefficient, all-optically-controlled 2D-FE devices incorporating electronic and photonic functionalities for memories, integrated photonics, sensors, and other optoelectronic applications, including a whole variety of possible combinations. More generally, giant all-optical switching of graphene's conductivity is desired for efficient memory devices and integrated photonics, where graphene plays the role of an ultrathin waveguide and other optoelectronic applications for light emission, transmission, modulation, and detection. resistance is measured with Agilent LCR meter at 100 kHz under ambient conditions. The FE loop is measured in darkness with a quasistatic loop tracer similar to that described in Ref. [START_REF] Mastner | A quasistatic hysteresis loop tracer[END_REF] by ultralow-frequency (0.01-Hz) measurements. We use above-band-gap excitation [START_REF] Wan | Optical properties of (1-x) Pb(Mg 1-x3 Nb 2-x3 )O 3-x PbTiO 3 single crystals studied by spectroscopic ellipsometry[END_REF] provided by a 365-nm light-emitting diode (3.4 eV) with 30-nm spectral linewidth to generate free carriers in the Pb[(Mg 1/3 Nb 2/3 ) 0.70 Ti 0.30 ]O 3 substrate [Fig. 2(a)]. The Au electrodes are covered during illumination to prevent possible charge injection [START_REF] Williams | Photoemission in the photovoltaic effect in cadmium sulfide crystals[END_REF].

II. EXPERIMENTAL DETAILS AND ELECTRICAL GROUND STATE

The ground state of the structure is first characterized electrically to verify ferroelectricity and ferroelectricallydriven performance before optical excitation. The FE polarization of the substrate (Fig. 1, right inset) leads to charge-driven modification of the graphene electrode forming also the two remanent states of resistance (Fig. 1). The typical antihysteretic behavior with an electric field is observed, indicating the possible presence of water at the interface between graphene and the FE [START_REF] Hong | Unusual resistance hysteresis in n-layer graphene field effect transistors fabricated on ferroelectric Pb(Zr 02 Ti 08 )O 3[END_REF][START_REF] Song | Robust bi-stable memory operation in single-layer graphene ferroelectric memory[END_REF][START_REF] Lipatov | Polarization-Dependent electronic transport in graphene/Pb(Zr, Ti)O 3 ferroelectric field-effect transistors[END_REF][START_REF] Yusuf | Extrinsic and intrinsic charge trapping at the graphene/ferroelectric interface[END_REF]. This adds a background doping to the graphene overlayer, shifting the Dirac point. Therefore, the maximum resistance occurs at higher electric fields than the ferroelectric coercive force of the substrate (Fig. 1, right inset), where polarization should pass through zero. The optical excitations are performed at zero electric field in the well-defined remanent state (state 1) obtained after a positive poling.

III. OPTICAL MEMORY EFFECT

Because of the possible existence of multiple polarization states in ferroelectrics [START_REF] Lee | Multilevel data storage memory using deterministic polarization control[END_REF] the electric ground state should be precisely defined and stabilized before the optical excitation. To this end, the structure is electrically poled in darkness to the remanent FE state by sweeping electric field from 0 to -7 kV/cm followed by a sweep from -7 to 7 kV/cm and then back to 0 kV/cm (point 1 in Fig. 1). Time-dependent measurements of the electric polarization are then conducted to ensure polarization stability before the optical excitation (Fig. 2). Sample illumination along the [001] direction [Fig. 2(a)] results in the large change of graphene resistance reaching 87% even with an extremely weak light power of 75 µW (fluence 6 mJ/cm 2 ) [Fig. 2(b)], greatly exceeding previous observations [START_REF] Wang | Ultrasensitive and broadband MoS 2 photodetector driven by ferroelectrics[END_REF][START_REF] Lipatov | Optoelectrical molybdenum disulfide (MoS 2 )-ferroelectric memories[END_REF][START_REF] Gorecki | Optical gating of graphene on photoconductive Fe:LiNbO3[END_REF][START_REF] Li | Optical control of polarization in ferroelectric heterostructures[END_REF]. The light illumination decreases the electric field in the sample and hence the polarization [Fig. 2(b), lower part] due to the screening by the photogenerated charges. The dynamics of the photoresponse of the graphene consists of a faster contribution leading to a decrease in the resistance and a slower contribution leading to resistance increase [Fig. 2(b), inset]. It is worth noting that the response, which occurs on a subsecond timescale (approximately 200 ms), relates to the limit of our time resolution for resistive measurements and may have room for significant improvement. In particular, by changing the FE substrate to, for example, BiFeO 3 [START_REF] Takahashi | Terahertz Radiation by an Ultrafast Spontaneous Polarization Modulation of Multiferroic BiFeO 3 Thin Films[END_REF][START_REF] Chen | Ultrafast terahertz gating of the polarization and giant nonlinear optical response in BiFeO 3 thin films[END_REF] or optimizing its 0.0 3.0×10 2 6.0×10 2 9.0×10 2 1.2×10 3 1.5×10 3 thickness, a significant reduction in response time can be expected.

When the light is switched off, the change in polarization of the substrate experiences relaxation [Fig. 2(b), lower part] but does not return to the initial level, constituting an optically written state that can be erased electrically by poling the system back to point 1 again, thus enabling a functionality of repeated optical writing and electrical reset. The increase of graphene resistance under illumination correlates with a decrease of remanent polarization, in agreement with Fig. 1(b), and is attributed to the photo(de)polarization effect [START_REF] Makhort | Photovoltaic effect and photopolarization in Pb[END_REF]. The small decrease in the remanent polarization (approximately 1% of P z in this case) and uniform sample illumination rule out the formation of FE domains due to light in our initially monodomain sample. In the enlargement of the graphene photoresponse [Fig. 2(b), inset] the initial resistance decrease and the subsequent increase suggests a strong nonlinear mechanism involved in the observed phenomenon. To gain insight into the origin of the observed effect, the resistance is measured as a function of light intensity (Fig. 3).

The photogenerated electron-hole pairs distribute themselves along the previously formed polarization direction [001], allowing the graphene layer to be doped. This doping can be reversed electrically by our moving the system to point 2 [Fig. 1(b)], which agrees with our model of the photodepolarization effect described in detail in Ref. [START_REF] Makhort | Photovoltaic effect and photopolarization in Pb[END_REF]. This light-induced charge-generation process occurs at intensities below 20 mW/cm 2 (Fig. 3) and eventually reaches saturation at higher intensities when the excess photocarriers start to recombine, thus reducing the remanent polarization, which is reflected in the resistance readout of the graphene overlayer. Because some of the charges have recombined irreversibly [START_REF] Makhort | Photovoltaic effect and photopolarization in Pb[END_REF][START_REF] Quattropani | Tuning photovoltaic response in Bi 2 FeCrO 6 films by ferroelectric poling[END_REF][START_REF] Iurchuk | Optical Writing of Magnetic Properties by Remanent Photostriction[END_REF] a repeatable optical writing of the graphene resistive state is possible. Moreover, it is clear that one can control the state formation by simply controlling the amount of trapped charges.

IV. OPTICAL WRITING AND ERASING OF GRAPHENE RESISTIVE STATES

As seen from Fig. 3, light-excitation intensity below 20 mW/cm 2 leads to a decrease in graphene resistance, while intensities above this value have the opposite effect. Consequently, a balance can be found between the two processes by controlling the amount of trapped charges and their re-excitation. This can be done by varying the light fluence and illumination history [Fig. 4(a)]. Depending on the illumination profile, the graphene states with larger (L) and smaller (S) photoresistive responses can be formed [Fig. 4(a)]. For comparison purposes, all states indexed from 1 to 4 are formed with the incremental steps of the same intensity as in Fig. 3. The other states are formed by light pulses with specific profiles (Fig. 4, lower plots), demonstrating the possibility to increase the writing speed. While the states of the L type show a tendency for relaxation, states of the S type exhibit significant stability. It is also clear that one can operate between states of the S type is possible by use of a specific illumination history, in agreement with Fig. 3. This possibility is illustrated in detail in Fig. 4(b), where squarelike writing pulses of higher intensity are followed by stabilization pulses of lower intensity.

V. DISCUSSION

Although the graphene layer is acting only as a resistive reading element of the substrate-intrinsic photopolarization effect, the role of the interface should be discussed. The difference between the FE coercive field (Fig. 1, right inset) and the electric field position of the peak in the electroresistive loop (Fig. 1) indicates the presence of water at the interface. The electrostatic ground state of the interface between the ferroelectric substrate and graphene is therefore verified by warming the sample in vacuum to 350 °C and then cooling it to room temperature. The electroresistive loop is then remeasured at 300 K on the same sample. The both loops initial and after annealing are depicted in Fig. 5.

After annealing, the hysteresis is inverted and electroresistive maxima shrink to the values of the FE coercive force [Fig. 1(b), right inset], as expected for humidity removal from the interface. The electric state obtained after positive poling in darkness (point 1) from 0 to -7 kV/cm followed by a sweep from -7 to 7 kV/cm and then back to 0 kV/cm is now lower than that for negative pooling, in agreement with the change of the doping type. The remeasured optical writing of the graphene resistive states is shown in Fig. 6.

The optical-writing and optical-erasing effects still persist after annealing, although they are reversed with respect to Fig. 4(b); light pulses of higher intensity now lead to a decrease in resistance. Therefore, the sample annealing performed here to remove interface humidity confirms the intrinsic nature of the effect. In agreement with the inherent nature of the photo(de)polarization effect of the substrate (see Fig. 2 and Ref. [START_REF] Makhort | Photovoltaic effect and photopolarization in Pb[END_REF]), neither the type of the graphene doping nor the interface humidity undermines the photoresistive performance, although it adds an inverted background. Nevertheless, the control of the interface doping can be potentially used to modify the performance of such photovoltaic-ferroelectric hybrid memory devices. At the same time, it must be underlined that the sample annealing to 350 °C crosses the structural ferroelectric transition of the substrate occurring near 150 °C [START_REF] Shrout | Dielectric behavior of single crystals near the (1-X ) Pb(Mg 1/3 Nb 2/3 )O 3-(x) PbTiO 3 morphotropic phase boundary[END_REF]. Therefore, the annealing affects the structure, and is expected to introduce defects due to large stresses developed near the first-order structural phase transition. Considering the previous discussion, photovoltaic-ferroelectric substrates with higher critical temperatures or a dry 2D layer transfer on the FE are preferable. Additionally, because of the photovoltaicelectrostatic nature of the effect, the remanent polarization must be well defined to ensure a saturated polarization state.

VI. CONCLUSION

By exploiting photovoltaic and FE properties of the substrate, nondestructive optical-writing-optical-erasing cycles are demonstrated. Because of the scarcity of nondestructive optical ways to store information in solids, the results provide a promising concept fundamentally different from the well-known phase-change thermal effect [START_REF] Yamada | Erasable phase-change optical materials[END_REF][START_REF] Zhang | Designing crystallization in phase-change materials for universal memory and neuro-inspired computing[END_REF][START_REF] Ovshinsky | Reversible Electrical Switching Phenomena in Disordered Structures[END_REF][START_REF] Callan | Ultrafast Laser-Induced Phase Transitions in Amorphous GeSb Films[END_REF]. Furthermore, this approach allows all-optical manipulations of the electronic state of 2D overlayers with high responsivity and efficiency, yet importantly conserving the option of nonvolatility. The resistive readout also makes the device operation compatible with resistive random-access memories [START_REF] Gupta | Resistive random access memory: A review of device challenges[END_REF][START_REF] Zahoor | Resistive random access memory (RRAM): An overview of materials, switching mechanism, performance, multilevel cell (mlc) storage, modeling, and applications[END_REF], where optical control can be beneficial [START_REF] Mehonic | Light-activated resistance switching in SiOx RRAM devices[END_REF][START_REF] Mao | Photonic memristor for future computing: A perspective[END_REF][START_REF] Di | Optically accessible memristive devices[END_REF][START_REF] Zhou | 2D materials based optoelectronic memory: Convergence of electronic memory and optical sensor[END_REF]. The reported device also meets miniaturization requirements [START_REF] Lanza | Recommended methods to study resistive switching devices[END_REF], due to the expected existence of photovoltaic and FE properties down to the nanometer scale. Most importantly, because graphene is highly promising for high-speed optoelectronics [START_REF] Mueller | Graphene photodetectors for high-speed optical communications[END_REF][START_REF] Zhang | Graphene-Based mixed-dimensional van der waals heterostructures for advanced optoelectronics[END_REF][START_REF] Kim | Ultrafast graphene light emitters[END_REF] and plasmonics [START_REF] Grigorenko | Graphene plasmonics[END_REF][START_REF] Fan | Graphene plasmonics: A platform for 2D optics[END_REF][START_REF] Kundys | Non-linear light mixing by graphene plasmons[END_REF][START_REF] Ansell | Hybrid graphene plasmonic waveguide modulators[END_REF][START_REF] Melikyan | High-speed plasmonic phase modulators[END_REF][START_REF] Debu | Hyperbolic plasmon-phonon dispersion on group velocity reversal and tunable spontaneous emission in graphene-ferroelectric substrate[END_REF][START_REF] Ono | Ultrafast and energyefficient all-optical switching with graphene-loaded deepsubwavelength plasmonic waveguides[END_REF], our results also advance its all-optical-control possibility. Such functionality is a key for integrated photonics [START_REF] Romagnoli | Graphene-based integrated photonics for next-generation datacom and telecom[END_REF][START_REF] Metcalf | Multiphoton quantum interference in a multiport integrated photonic device[END_REF][START_REF] Spring | Boson sampling on a photonic chip[END_REF] focusing on a number of disruptive quantum-technology applications capable of delivering a source-waveguide-detector platform for quantum-information processing [START_REF] Smith | Phase-controlled integrated photonic quantum circuits[END_REF][START_REF] Metcalf | Quantum teleportation on a photonic chip[END_REF][START_REF] Flamini | Photonic quantum information processing: A review[END_REF], sensing, metrology [START_REF] Acín | The quantum technologies roadmap: A european community view[END_REF], and modulators [START_REF] Sun | Optical modulators with 2D layered materials[END_REF], where compact and scalable electronic-photonic platforms are in great demand.

6

Optical writing and erasing Optical writing and erasing Optical writing and erasing

Figure 1 (FIG. 1 .

 11 Figure 1 (left inset) illustrates the experimental approach used for electric-field-induced remanent-state formation. The Pb[(Mg 1/3 Nb 2/3 ) 0.70 Ti 0.30 ]O 3 crystal with dimensions of 2.43 × 1.09 × 0.26 mm 3 is cut from plates of (001) orientation supplied by Crystal GmbH (Germany). The graphene monolayer is deposited by CVD transfer on the top of the (001) plane without postannealing. The drain and source Au electrodes of 30-nm thickness are deposited on the graphene layer by electron-beam evaporation and wired with silver conductive paste. The

FIG. 2 .

 2 FIG. 2. (a) Experimental setup for optical excitations; the 2D graphene layer is illuminated by a 365-nm light-emitting diode along the [001] direction of the FE substrate, previously subjected to positive poling (state 1). (b) Polarization along the z axis and resistance of the graphene layer in response to a 10-s light pulse of extremely weak intensity (0.60 mW/cm 2 ). The inset shows an enlargement of the photoresistive response indicating the nonlinear behavior.

FIG. 3 .

 3 FIG.3. Light-intensity sweeps from 0 to 118 mW/cm 2 (back and forth), with a step of 2.36 mW/cm 2 , with the time step of 200 ms. Multiple light-written states of S and L types are possible depending on the driving-light intensity owing to the selective charge-trapping approach (see the text).

3

  Graphene-Ferroelectric-PhotovoltaicGraphene-Ferroelectric-PhotovoltaicOptical writing and erasing Optical writing and erasingOptical writing and erasingOptical writing and erasing

FIG. 4 .

 4 FIG. 4. (a) Time dependence of the graphene resistance illustrating optical writing. The initially positively poled substrate along the [001] direction, state 1 (see the text), is subjected to various light-illumination histories that trigger resistive states of L and S types. (b) States of the S type are written and erased all optically with use of deterministic light pulses. Right scales show corresponding light pulses.

4 OpticalFIG. 6 .

 46 FIG.5. Room-temperature evolution of the graphene resistance due to the electrostatic doping caused by FE hysteresis for the as-prepared structure and the structure annealed at 350 °C.

Graphene-Ferroelectric-Photovoltaic

ACKNOWLEDGMENTS

This work was partly supported by Labex NIE Grant No. 0058_NIE within the Investissement d'Avenir program ANR-10-IDEX-0002-02. A.S.M. acknowledges the Ph.D. cofund program of the Alsace region.