Divesh Aggarwal
email: divesha@inf.ethz.ch

Ueli Maurer
email: maurer@inf.ethz.ch

Igor Shparlinski

The Equivalence of Strong RSA and Factoring in the Generic Ring Model of Computation ⋆

Let N be the result of an RSA modulus generation, i.e., a random variable distributed according to some appropriate distribution over the set of products of two primes, such that factoring N is believed to be hard. The Strong RSA assumption states that, given an x chosen uniformly at random from ZN , it is computationally infeasible to compute a y ∈ ZN and an e ∈ N \ {1} such that y e ≡ x (mod N ) . This assumption is important in cryptography and has been used to construct several cryptosystems. Due to the lack of complexity-theoretic lower bound proofs for cryptographic problems in a general model of computation, it is a common practice in cryptography to give proofs of computational security in meaningful restricted models of computation. Some examples of restricted models that are interesting in cryptography are the generic group model for proving lower bounds for the discrete logarithm problem and related problems, and the random oracle model for proving the soundness of protocols or hash function constructions. A generic model captures that an algorithm does not exploit the bit representation of the elements other than for testing equality. The security of the RSA public-key cryptosystem can be analyzed in the generic ring model. In this paper, we prove that for almost all possible distributions of N , the problem of factoring N can be efficiently reduced to solving the Strong RSA problem on ZN in the generic ring model of computation, where an algorithm can perform ring operations, inverse ring operations, and test equality.

1 Introduction

The Strong RSA Assumption

The RSA [START_REF] Rivest | A method for obtaining digital signatures and public key cryptosystems[END_REF] public key cryptosystem is probably the most widely used public key cryptosystem. Its security relies on the assumption that, given an RSA public ⋆ This version is an extended abstract of the paper. key (n, e) and an x ∈ Z n , it is hard to compute a y ∈ Z n such that y e ≡ x (mod n) .

The Strong RSA assumption was introduced by Baric and Pfitzmann [START_REF] Baric | Collision-free accumulators and fail-stop signature schemes without trees[END_REF]. Cramer and Shoup [START_REF] Cramer | Signature schemes based on the Strong RSA assumption[END_REF] gave a signature scheme based on this assumption. This assumption differs from the RSA assumption in that it states that it is hard to compute e-th roots even if the adversary is allowed to choose e. Clearly, the RSA assumption is potentially a weaker assumption. A still weaker assumption is that factoring the modulus n is hard.

Before stating these assumptions, we define a non-negligible function. A function f : N → R is called non-negligible if there exists c > 0 and k 0 ∈ N such that for all k > k 0 , we have |f (k)| > k -c .

We consider a random variable N that is chosen according to a certain probability distribution over a set of products of two primes. The set of primes for which the result of this paper holds will be discussed in Section 2.1. The Strong RSA problem is the problem of computing, given N and an element x chosen uniformly at random from Z N , y ∈ Z N and e ∈ N\{1} such that y e ≡ x (mod N ) . The assumptions are defined with respect to N and are formally stated below:

Strong RSA Assumption for N : There exists no probabilistic polynomial-time (PPT) algorithm that solves the Strong RSA problem for N with nonnegligible probability. RSA Assumption for N and e: There exists no PPT algorithm that, given N , an element x chosen uniformly at random from Z N , and an integer e ∈ N \ {1} , computes y ∈ Z N such that y e ≡ x (mod N ) with non-negligible probability. Factoring Assumption for N : There exists no PPT algorithm that, given N , finds a non-trivial factor of N with non-negligible probability.

It is easy to see that if the Strong RSA assumption holds then the factoring assumption holds. However, it is not known whether the converse is true. In this paper, we show that this converse holds with respect to a restricted class of algorithms called generic algorithms. Our result thus subsumes the result of [START_REF] Aggarwal | Breaking RSA generically is equivalent to factoring[END_REF] and proves a more general result.

Generic algorithms are algorithms that do not exploit the representation of the elements. This class of algorithms was introduced by Shoup [START_REF] Shoup | Lower bounds for discrete logarithms and related problems[END_REF], based on the work of Nechaev [START_REF] Nechaev | Complexity of a deterministic algorithm for the discrete logarithm[END_REF]. They proved lower bounds on the complexity of computing discrete logarithms and some related problems in cyclic groups in the context of generic algorithms. Maurer [START_REF] Maurer | Abstract models of computation in cryptography[END_REF] provided a simpler and more general model for analyzing representation-independent algorithms.

The Generic Ring Model of Computation

We give a brief description of the model of [START_REF] Maurer | Abstract models of computation in cryptography[END_REF]. This is almost the same as the description used in [START_REF] Aggarwal | Breaking RSA generically is equivalent to factoring[END_REF] and is sufficient for our purpose. The model is characterized by a black-box B which can store values from a certain set T in internal For this paper, the set T is Z N . Also ℓ = 1 and V 0 is always set to be the unit element 1 of Z N and V 1 is the value x that is the input to the algorithm. Also, N is assumed to be explicitly given to the algorithm. A generic ring algorithm (GRA) is an algorithm that is allowed only ring operations and equality queries, i.e., Π = {+, -, •, /} and Σ = {=} .

state variables V 0 , V 1 , V
Note that division by non-invertible elements of Z N is not defined. This can be modeled in the above generic ring model by having the black-box B send an "exception" bit b to the algorithm and leaving the corresponding state variable undefined whenever there is a division by a non-invertible element. For more details on this, refer to [START_REF] Aggarwal | Breaking RSA generically is equivalent to factoring[END_REF].

The Strong RSA Problem in the Generic Ring Model of Computation

The difficulty in formulating the Strong RSA problem in the generic ring model is that an algorithm for solving this problem should output e and y where e is not an element of the ring Z N and hence cannot be computed in the black-box. If we model the problem such that the algorithm outputs e explicitly, then e does not depend on the input except possibly on the result of equality queries. The natural solution to this problem is to model e as an element of the ring Z N which is interpreted as an integer in {0, . . . , N -1}. In particular, for u, v ∈ Z N , the element u v ∈ Z N is defined as an element of Z N obtained from raising u to the power corresponding to the integer representing v modulo N . The Strong RSA problem in our model can thus be stated as the problem of computing (y, e) such that y e ≡ x (mod N ) when

V 0 = 1, V 1 = x and Π = {+, -, •, /} and Σ = {=} .

Comparison With the Model of Damgård and Koprowski

The only result that looks at the Strong RSA problem with respect to generic algorithms is due to Damgård and Koprowski [START_REF] Damgård | Generic lower bounds for root extraction and signature schemes in general groups[END_REF]. In [START_REF] Damgård | Generic lower bounds for root extraction and signature schemes in general groups[END_REF], the authors show that no generic group algorithm(GGA) can, given an x chosen uniformly at random from a certain group G , efficiently compute y ∈ G and e ∈ Z such that y e = x for a reasonable choice of the group G , where GGAs are algorithms that allow only the multiplication operation, which in our model would correspond to Π = {•} and Σ = {=} .

Their result is very restricted in the sense that they assume that e is computed outside the black-box and hence does not depend on the input except possibly on the result of equality queries. Thus, their result is not much more general than proving the hardness of the RSA problem in this model (that is, when e is fixed). In contrast, in our model, e can be computed in the black-box as an element of Z N using a GRA which is given x as input.

In [START_REF] Damgård | Generic lower bounds for root extraction and signature schemes in general groups[END_REF], they consider only GGAs while we prove the equivalence for GRAs. Since both the ring operations, multiplication and addition modulo N , are easy to perform on the ring Z N , it is more interesting to study the complexity of Strong RSA problem for GRAs rather than for GGAs.

Other Related Work

In addition to the result [START_REF] Damgård | Generic lower bounds for root extraction and signature schemes in general groups[END_REF] mentioned in Section 1.4, there have been some other results studying the RSA and related problems with respect to generic algorithms.

Boneh and Venkatesan [START_REF] Boneh | Breaking RSA may be easier than factoring[END_REF] showed that any straight-line program that factors N by making at most a logarithmic number of queries to an oracle solving the Low Exponent RSA (LE-RSA) problem, which is the RSA problem when the public exponent e is small, can be converted into a PPT algorithm for factoring N . This result is, however, of limited interest because the complexity of the factoring algorithm that does not use the oracle increases exponentially with the number of oracle queries made by the algorithm that uses the oracle.

Brown [START_REF] Brown | Breaking RSA may be as difficult as factoring[END_REF] showed that if factoring is hard then the LE-RSA problem is intractable for straight-line programs (SLPs), i.e., where Π = {+, -, •, /} . More precisely, he proved that an efficient SLP for breaking LE-RSA can be transformed into an efficient factoring algorithm. Leander and Rupp [START_REF] Leander | On the equivalence of RSA and factoring regarding generic ring algorithms[END_REF] generalized the result of [START_REF] Brown | Breaking RSA may be as difficult as factoring[END_REF] to GRAs which, as explained earlier, can test for equality of elements in addition to the computation operations. Aggarwal and Maurer [START_REF] Aggarwal | Breaking RSA generically is equivalent to factoring[END_REF] further generalized these results to show that any GRA for computing e-th roots (for any e) can be transformed into an efficient factoring algorithm.

Preliminaries

Notation

Let n be some value taken by the random variable N . By Z n [X] , we denote the ring of polynomials in x with coefficients in the ring Z n of integers modulo n .

Let τ (k) denote the number of positive integer divisors of an integer k ≥ 2. For η > 0, we define L η as the set of primes ℓ with τ (ℓ -1)

≤ (log ℓ) 1+η . Let π * η (L) = #(L η ∩ [1, L]
) and let π(L) be the number of primes ℓ ≤ L. The following result states that for any constant η > 0, π * η (L) is almost as large as π(L) , i.e., L η contains almost all primes. The proof is deferred to the full version.

Lemma 1. For any fixed η > 0 , we have

π * η (L) = π(L) 1 -O (log L) -η
.

Thus, for any η > 0, the set L η contains almost all sufficiently large primes that are used for RSA. In particular, it includes all safe primes, i.e., primes ℓ such that (ℓ -1)/2 is also a prime which are the primes most often used for RSA.

Let n be the product of primes p and q . Without loss of generality, we can assume that q < p . In this paper, we assume κ to be the security parameter and the term non-negligible is with respect to κ . We define a set N η as follows:

N η = {n = p • q : p, q are primes, 2 κ ≤ n < 2 κ+1 , q < p, and p, q ∈ L η } .

The set of RSA moduli considered in this paper are elements of the set N η .

Definitions: SLPs and GRAs

In this section, we define two classes of algorithms, namely Straight Line Programs (SLPs) and Generic Ring Algorithms(GRAs). These definitions and the corresponding interpretation is taken from [START_REF] Aggarwal | Breaking RSA generically is equivalent to factoring[END_REF] and the reader should refer to [START_REF] Aggarwal | Breaking RSA generically is equivalent to factoring[END_REF] for a more detailed description.

An SLP corresponds to Π = {+, -, •, /} and Σ = {} in the model of [START_REF] Maurer | Abstract models of computation in cryptography[END_REF] and is defined as follows:

Definition 1. An L-step straight-line program (SLP) S is a sequence of L - 1 triples (i 2 , j 2 , • 2 ) , . . ., (i L , j L , • L ) such that 0 ≤ i k , j k < k and • k ∈ {+, -, •, /}.
The interpretation of an SLP is that if x is considered a variable, then the SLP S computes a sequence of rational functions f 2 , . . . , f L , where,

f 0 = 1, f 1 = x and f k = f i k • k f j k for 2 ≤ k ≤ L.
The rational functions f i can be interpreted as a pair of polynomials (a i , b i ) representing the numerator and the denominator of f i . A (randomized) GRA is a generalization of an SLP and is defined as follows: Definition 2. An L-step (randomized) GRA G is an algorithm that, in the k th step, for 2 ≤ k ≤ L, outputs an operation of the form (i k , j k , • k ) , where 0 ≤ i k , j k < k and • k ∈ {+, -, •, /, =} and if • k is =, it takes an input bit (as the result of the equality query). 33 Generic Strong RSA vs Factoring

The Statement of the Main Result

As mentioned earlier, in this paper we restrict our attention to the case where the adversary is only allowed to use a GRA to solve the Strong RSA problem. We refer to the Strong RSA assumption in this case as the Generic Strong RSA assumption for the random variable N : Generic Strong RSA Assumption for N : For any L bounded by a polynomial in the security parameter, there exists no L-step randomized GRA thatsolves the Strong RSA problem for N with non-negligible probability.

Theorem 1. Let η > 0 be fixed. Let N be a random variable taking values in the set N η . If the Factoring Assumption for N holds, then the Generic Strong RSA Assumption for N holds.

It should be noted that this theorem is proved for any distribution of N over the set N η . Also, n is a value taken by the random variable N .

The Proof for Straight-Line Programs

Here we obtain a version of Theorem 1 in the case when a randomized GRA is replaced by an SLP in the definition of the Generic Strong RSA Assumption.

The following result is a slight generalization of [START_REF] Aggarwal | Breaking RSA generically is equivalent to factoring[END_REF]Lemma 6] and we need this to prove the result for straight line programs. Lemma 2. For all µ > 0 and L ∈ N , there exists an algorithm that takes as input n and, for every L-step SLP S that computes the rational function f

(x) ∈ Z n [x] not identically 0 such that Pr x∈ R Zn (f (x) ≡ 0 (mod n)) ≥ µ, returns a factor of n in expected time O(L 4 /µ) .
This proof is almost the same as the proof of [1, Lemma 6]. Now, we prove the main technical result of this section. It shows that any SLP that, given x, computes a y and an e such that y e ≡ x (mod n) for some e > 1, can be used to factor n . Lemma 3. For all η > 0, α > 0 and L ∈ N , there exists an algorithm that takes as input n and an L-step SLP S , and satisfies the following property. If S computes the rational functions P 1 (x)/Q 1 (x) and P 2 (x)/Q 2 (x) such that the cardinality of the set4

x ∈ Z n :

P 1 (x) Q 1 (x) P2(x)/Q2(x) ≡ x (mod n) ∧ P 2 (x) ≡ Q 2 (x) (mod n)
is at least 3n(log n) -α , then the algorithm returns a factor of n in expected time O log 2α+2η+3 n L 4 + log 4 n .

Proof. We define two events E 1 and E 2 .

-Let E 1 be the event that there exists c ∈ Z n (c = 1) such that

# x ∈ Z n : P 2 (x) Q 2 (x) -c ≡ 0 (mod n) ≥ n (log n) α+1+η (1)
-Let E 2 be the event that there exists c ∈ Z n (c = 1) such that

# x ∈ Z n : P 2 (x) Q 2 (x) -c ≡ 0 (mod q) ≥ 2n (log n) α+1+η (2)
For an event E , we use E to denote the complementary event of E .

We split the proof into three cases that are mutually exhaustive. In the first two cases, we give an algorithm for factoring n , and in the third case, we show that the inequality in the statement of Lemma 3 is not satisfied. CASE 1: E 1 holds.

In this case, P 2 (x)/Q 2 (x) is a constant c with non-negligible probability, i.e., P 2 (x)-cQ 2 (x) ≡ n 0 with non-negligible probability. Thus, if P 2 (x)-cQ 2 (x) is not identically zero, then, using Lemma 2, we can obtain a factor of n . If P 2 (x) -cQ 2 (x) is identically zero, then P 1 (x) c -xQ 1 (x) c ≡ n 0 with non-negligible probability and thus, we can use Lemma 2 for the polynomial P 1 (x) c -xQ 1 (x) c , thus obtaining a factor of n . CASE 2: The events E 1 and E 2 hold.

In this case, as can be seen from the definitions of E 1 and E 2 , the expression P 2 (X) /Q 2 (X) behaves differently modulo p and modulo q for a random X . Thus, it can be shown that gcd

(P 2 (X 1 )/Q 2 (X 1 ) -P 2 (X 2 )/Q 2 (X 2 ), n)
for randomly chosen X 1 , X 2 returns a factor of n with non-negligible probability. The details of the proof of CASE 1 and CASE 2 is deferred to the full version of the paper.

CASE 3:

The event E 2 holds.

In this case, we bound the cardinality of the set

x ∈ Z n : P 1 (x) Q 1 (x) P2(x)/Q2(x) ≡ x mod n, P 2 (x) ≡ Q 2 (x) mod n .
Let us consider the natural homomorphism from Z n to Z q and define

R = max c∈Zq # x ∈ Z q : P 2 (x) Q 2 (x) ≡ c (mod q) ≤ 2q(log n) -(α+1+η) , (3)
where the inequality follows from the fact that E 2 holds. Each x = 0, . . . , n -1 can be uniquely written as m + pk with m = 0, . . . , p -1 and k = 0, . . . , q -1. We also note that for any polynomial P , P (m + pk) ≡ P (m) (mod p) . Thus, the congruence P1(x)

Q1(x) P2(x)/Q2(x) ≡ x (mod n) , taken modulo p is P 1 (m) Q 1 (m) P 2 (m+pk) Q 2 (m+pk) ≡ m (mod p), 0 ≤ m ≤ p -1, 0 ≤ k ≤ q -1. ( 4
)
The number of solutions with m = 0 is at most q . Now, we bound the number of solutions if m = 0. In this case, for (4) to hold, P 1 (m) ≡ 0 and Q 1 (m) ≡ 0 (mod p) . Hence, in order to give an upper bound on the cardinality of X , we also assume that P 1 (m) and Q 1 (m) are not 0 modulo p . We now fix a primitive root g modulo p . Then, for all m , there exist u m and v m such that m ≡ g um (mod p), P 1 (m)

Q 1 (m) ≡ g vm (mod p), 0 ≤ u m , v m ≤ p -2 .
From (4), we get that

v m • P 2 (m + pk) Q 2 (m + pk) ≡ u m (mod p -1). ( 5
) Let t m = gcd (p -1, v m , u m ) and s m = p-1 tm . Then, (5) is equivalent to v m t m • P 2 (m + pk) Q 2 (m + pk) ≡ u m t m (mod s m ) . (6)
Clearly, if gcd(v m /t m , s m ) > 1, then the above congruence has no solutions. Therefore, gcd(v m /t m , s m ) = 1 must hold. Then, by multiplying ( 6) by (v m /t m ) -1 modulo s m , it leads to a congruence of the type

P 2 (m + pk) Q 2 (m + pk) ≡ w m (mod s m ), (7)
with some integer w m depending only on m and not on k . Thus P 2 (m + pk)/Q 2 (m + pk) can take at most one value modulo s m for a fixed m . Also, P 2 (m + pk)/Q 2 (m + pk) takes a unique value modulo p for a fixed m . Thus, by the Chinese Remainder Theorem, P 2 (m + pk)/Q 2 (m + pk) takes at most one value modulo ps m . This implies (using q < p ) that, for a fixed m , there are at most pq psm = qtm p-1 ≤ t m possible values for P 2 (m + pk)/Q 2 (m + pk) . Note that m + pk is uniformly random in Z q if m is fixed and k is chosen uniformly at random in Z q . So, from (5), P 2 (m + pk)/Q 2 (m + pk) takes any of these possible values for at most R possible values of k . Since t m | gcd(u m , p -1) , t m = t for at most (p -1)/t values of m.

Collecting together the values m such that t m = t for all t | p -1 and counting q possible values of x for m = 0, we obtain that

#X ≤ q + t|p-1 p -1 t • tR = q + (p -1)R t|p-1 1
= q + (p -1)Rτ (p -1) ≤ q + 2(p -1)q(log n) -(α+1+η) (log n) 1+η < q + 2n(log n) -α < 3n(log n) -α , where the third last inequality follows from the fact that p ∈ L η and using (3), and the last inequality follows from the fact that q < √ n (since p > q ) and √ n is larger than (log n) α for n large enough. However, this contradicts our assumption. ⊓ ⊔

Generalizing the Proof from SLPs to GRAs

In this section we state how to obtain a factoring algorithm that, given access to a GRA that solves the Strong RSA problem in Z n , outputs either a factor of n or an SLP that solves the Strong RSA problem in Z n with almost the same success probability.

Definition 3. For a GRA G , let λ n (G) denote the probability that G , when run on an x chosen uniformly at random from Z n , computes a pair y, e such that y e ≡ x (mod n) .

Note that λ n (S) for an SLP S is implicitly defined by the above definition, since an SLP is a special type of a GRA.

Lemma 4. For all ε > 0 and L ∈ N , there exists an algorithm of time complexity O((L/ε) 5/2 ) that, given access to an L-step randomized GRA G such that λ n (G) = µ, with probability µ/2ε , either outputs a factor of n or an L-step SLP S such that λ n (S) ≥ µ/2 .

The proof of Lemma 4 is the same as the proof of [1, Lemma 8]. Note that the statement of Lemma 4 is different from [START_REF] Aggarwal | Breaking RSA generically is equivalent to factoring[END_REF] because of different definitions of λ n (G) , but this does not change anything in the proof.

Combining Lemma 4 and Lemma 3, we can obtain the proof of Theorem 1. The details of this proof can be found in the full version of the paper.

  [START_REF] Baric | Collision-free accumulators and fail-stop signature schemes without trees[END_REF]

  , • • • . The initial state (the input of the problem to be solved) consists of the values of [V 0 , . . ., V ℓ ] for some positive integer ℓ, which are set according to some probability distribution over T ℓ+1 . , . . . , i t+1 of t +1 state variables. The black-box B computes f (V i1 , . . . , V it ) and stores the result in V it+1 . -Relation Queries. For a set Σ of relations on T , a query consists of selecting a relation ρ ∈ Σ (say t -ary) as well as the indices i 1 , . . . , i t of t state variables. The query is replied by the binary output ρ(V i1 , . . . , V it ) that takes the value 1 if the relation is satisfied, and 0 otherwise.An algorithm in this model is characterized by its interactions with the black box B . The algorithm inputs operations (computation operations and relation queries) to the black box, and the replies to the relation queries are returned to the algorithm. The complexity of an algorithm for solving any problem can be measured by the number of operations it performs on B .

	The black box B allows two types of operations:
	-Computation operations. For a set Π of operations on T , a computation
	operation consists of selecting f ∈ Π (say t -ary) as well as the indices i 1

The choice of the operation at each step may be randomized.

Note that P2 (x)/Q2 (x) is understood as being computed modulo n .


Ville Junnila

Tero Laihonen

Optimality of a 2-identifying code in the hexagonal grid

Keywords: Identifying code, optimal code, hexagonal grid

. In this paper, we prove that the 2-identifying code with density 4/19 is optimal, i.e. that there does not exist a 2-identifying code in the hexagonal grid with smaller density.

Introduction

Let G = (V, E) be a simple, connected and undirected graph with V as the set of vertices and E as the set of edges. Let u and v be vertices in V . If u and v are adjacent to each other, then the edge between u and v is denoted by {u, v} (or in short by uv). The distance between u and v is denoted by d(u, v) and is defined as the number of edges in any shortest path between u and v. Let r be a positive integer. We say that u r-covers v if the distance d(u, v) is at most r. The ball of radius r centered at u is defined as

B r (u) = {x ∈ V | d(u, x) ≤ r}.
A nonempty subset of V is called a code in G, and its elements are called codewords. Let C ⊆ V be a code and u be a vertex in V . An I-set (or an identifying set) of the vertex u with respect to the code C is defined as

I r (C; u) = I r (u) = B r (u) ∩ C.
The following definition is due to Karpovsky et al. [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF].

⋆ Research supported by the Academy of Finland under grant 210280.

Definition 1. Let r be a positive integer. A code C ⊆ V is said to be ridentifying in G if for all u, v ∈ V (u = v) the set I r (C; u) is nonempty and

I r (C; u) = I r (C; v).
Let X and Y be subsets of V . The symmetric difference of X and Y is defined as X △ Y = (X \ Y ) ∪ (Y \ X). We say that the vertices u and v are r-separated by a code C ⊆ V (or by a codeword of C) if the symmetric difference I r (C; u) △ I r (C; v) is nonempty. The definition of r-identifying codes can now be reformulated as follows: C ⊆ V is an r-identifying code in G if and only if for all u, v ∈ V (u = v) the vertex u is r-covered by a codeword of C and

I r (C; u) △ I r (C; v) = ∅.
In this paper, we study identifying codes in the hexagonal grid. We define the hexagonal grid G H = (V H , E H ) using the brick wall representation as follows: the set of vertices V H = Z 2 and the set of edges

E H = {{u = (i, j), v} | u, v ∈ Z 2 , u -v ∈ {(0, (-1) i+j+1 ), (±1, 0)}}.
This definition is illustrated in Figure 1(a). The hexagonal grid can also be illustrated using the honeycomb representation as in Figure 1(b). In both illustrations, lines represent the edges and intersections of the lines represent the vertices of G H . The labeling of the vertices in the brick wall representation is self-explanatory. This labeling can also be applied to the honeycomb representation, if we visualize the honeycomb to be obtained from the brick wall by squeezing it from left and right. For an example of the labeling of the vertices, we refer to Figure 1. To measure the size of an identifying code in the infinite hexagonal grid, we introduce the notion of density. For the formal definition, we first define

Q n = {(x, y) ∈ V H | |x| ≤ n, |y| ≤ n}.
Then the density of a code C ⊆ V H is defined as

D(C) = lim sup n→∞ |C ∩ Q n | |Q n | .
Naturally, we try to construct identifying codes with as small density as possible. Moreover, we say that an r-identifying code is optimal, if there do not exist any r-identifying codes with smaller density. Previously, r-identifying codes in G H have been studied in various papers. The first results concerning r-identifying codes in G H have been presented in the seminal paper [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF] in the case r = 1. Later these results have been improved by showing that there exists a 1-identifying code with density 3/7 (see Cohen et al. [START_REF] Cohen | Bounds for codes identifying vertices in the hexagonal grid[END_REF]) and that there do not exist 1-identifying codes in G H with density smaller than 12/29 (see Cranston and Yu [6]). For general r ≥ 2, Charon et al. [START_REF] Charon | General bounds for identifying codes in some infinite regular graphs[END_REF] showed that each r-identifying code C in G H has D(C) ≥ 2/(5r + 3) if r is even and D(C) ≥ 2/(5r + 2) if r is odd. They also presented a construction for each r ≥ 2 giving an r-identifying code C ⊆ V H with D(C) ∼ 8/(9r).

For small values of r, the previous constructions have been improved in [4] by Charon et al. In particular, it is shown that there exists a 2-identifying code in G H with density 4/19. In the case r = 2, the lower bound 2/11 from [4, Equation (1)] (and the aforementioned general lower bound) is improved in Martin and Stanton [START_REF] Martin | Lower bounds for identifying codes in some infinite grids[END_REF] by showing that the density of any 2-identifying code in G H is at least 1/5. In this paper, we further improve this lower bound to 4/19. In other words, we show that the previously presented 2-identifying code with density 4/19 is optimal.

Notice that, besides the hexagonal grid, identification has also been studied in various other grids such as the square, triangular and king grids. For the results in these grids, we refer to [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Charon | The minimum density of an identifying code in the king lattice[END_REF][START_REF] Charon | Identifying codes with small radius in some infinite regular graphs[END_REF][START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF][START_REF] Martin | Lower bounds for identifying codes in some infinite grids[END_REF]. Moreover, in [START_REF] Honkala | On identifying codes in the triangular and square grids[END_REF], one can found tables summarizing known result in these grids.

Lower bounds using share

Let G = (V, E) be a simple, connected and undirected graph. Assume also that C is a code in G. The following concept of the share of a codeword has been introduced by Slater in [START_REF] Slater | Fault-tolerant locating-dominating sets[END_REF]. The share of a codeword c ∈ C is defined as

s r (C; c) = s r (c) = u∈Br(c) 1 |I r (C; u)| .
The notion of share proves to be useful in determining lower bounds of ridentifying codes (as explained in the following).

Assume that

G = (V, E) is a finite graph and D is a code in G such that B r (u) ∩ D is nonempty for all u ∈ V . Then it is easy to conclude that c∈D s r (D; c) = |V |. Assume further that s r (D; c) ≤ α for all c ∈ D. Then we have |V | ≤ α|D|, which immediately implies |D| ≥ 1 α |V |.
Assume then that for any r-identifying code C in G we have s r (C; c) ≤ α for all c ∈ C. By the aforementioned observation, we then obtain the lower bound |V |/α for the size of an r-identifying code in G. In other words, by determining the maximum share for any r-identifying code, we obtain a lower bound for the minimum size of an r-identifying code.

The previous reasoning can also be generalized to the case when an infinite graph is considered. In particular, if for any r-identifying code in G H we have s r (C; c) ≤ α for all c ∈ C, then it can be shown that the density of an r-identifying code in G H is at least 1/α (compare to Theorem 1). The main idea behind the proof of the lower bound (in Section 3) is based on this observation, although we use a more sophisticated method by showing that for any 2-identifying code the share is on average at most 19/4. In Theorem 1, we present a formal proof to verify that this method is indeed valid.

In the proof of the lower bound, we need to determine upper bounds for shares of codewords. To formally present a way to estimate shares, we first need to introduce some notations. Let D ⊆ V be a code and c be a codeword of D. Consider then the I-sets I r (D; u) when u goes through all the vertices in B r (c).

(Notice that all of these I-sets do not have to be different.) Denote the different identifying sets by I 1 , I 2 , . . . , I k , where k is a positive integer. Furthermore, denote the number of identifying sets equal to I j by i j (j = 1, 2, . . . , k). Now we are ready to present the following lemma, which provides a method to estimate the shares of the codewords.

s 2 (C; (0, 1)) ≤ 1 + 3 • 1 2 + 1 2 + 3 • 1 3 + 1 3 + 1 4 = 55 12 .
Furthermore, since we have

I 2 (D; (-1, -1)) = I 2 (D; (1, -1)) = I 2 (D; (2, 0)) = {(0, 0), ( 1
, -1)}, we obtain (again by Lemma 1) that

s 2 (C; (0, 0)) ≤ 1 + 2 • 1 2 + 6 • 1 3 + 1 4 = 17 4 .

The proof of the lower bound

From now on, we assume that C is a 2-identifying code in G H . In this section, we first show that on average s 2 (c) ≤ 19/4 for all c ∈ C. Then, in Theorem 1, we finally prove that the density D(C) ≥ 4/19.

The averaging process is done by introducing a shifting scheme designed to even out the shares among the codewords of C. Notice that the shifting scheme can also be understood as a discharging method. The rules of the shifting scheme are illustrated in Figure 2. Translations, rotations and reflections (over the line passing vertically through u) can be applied to each rule in such a way that the structure of the underlying graph G H is preserved. In the rules, share is shifted as follows:

-In the rules 1, 2, 4 and 7, we shift 1/4 units of share from u to v. -In the rule 3, we shift 1/6 and 1/12 units of share from u to v and v ′ , respectively. -In the rule 5, we shift 1/6 units of share from u to v. -In the rules 6, 8, 9 and 10, we shift 1/12 units of share from u to v.

We also have the following modifications to the previous rules:

-If in the rules 1, 2 and 7 we have u + (0, -1) ∈ C, then we only shift 1/12 units of share from u to v and denote these new rules (respectively) by 1. The modified share of a codeword c ∈ C, which is obtained after the shifting scheme is applied, is denoted by s2 (c). In what follows, we show that s2 (c) ≤ 19/4 for all c ∈ C. Lemma 2. Let c ∈ C be a codeword such that c is adjacent to another codeword and share is shifted to c according to the previous rules. Then we have s2 (c) ≤ 19/4.

Proof. Since c is adjacent to another codeword, it is immediate that c can receive share only according to the rules 1-6 and their modifications. The proof of the lemma is now divided into three cases depending on the number of codewords adjacent to c.

Assume first that c is adjacent to exactly one codeword. Without loss of generality, we may assume that c = (0, 0) and the adjacent codeword is (0, 1). (Notice that (-1, 0) / ∈ C and (1, 0) / ∈ C.) Now the only possibilities for c to receive share is from the vertices (-3, 0) or (3, 0) (the rule 1.2) and from the vertices that belong to S 1 = {(5, 1), (4, 1), (3, 1), (3, 2), (2, 2)} and S 2 = {(-5, 1), (-4, 1), (-3, 1), (-3, 2), (-2, 2)}. It is straightforward to verify that the codewords in each of the sets S 1 and S 2 can shift at most 1/4 units of share to c. (Notice that only the rules 2.1 and 5, or the rules 2.1 and 6 can be used simultaneously.) Assume that the rule 1.2 is used. (Clearly, this rule can be used only once.) Without loss of generality, we may assume that (-3, 0) ∈ C and (1, -1) ∈ C. Therefore, choosing D = {c, (0, 1), (-3, 0), (1, -1)} in Lemma 1, we obtain that s 2 (c) ≤ 15/4. Thus, since the codewords in each of the sets S 1 and S 2 can shift at most 1/4 units of share to c, we have s2 (c) ≤ s 2 (c) + 3 • 1/4 ≤ 9/2. Assume then that the rule 1.2 cannot be applied to c. Since c and (0, 1) are 2-separated by C, there exists at least one codeword in the symmetric difference B 2 (c) △ B 2 (0, 1). Thus, without loss of generality, we may assume that (1, -1

) ∈ C, (1, 2) ∈ C, (2, 0) ∈ C or (2, 1) ∈ C.
Assume first that (1, -1) ∈ C. Now, by Example 1, we know that s 2 (c) ≤ 17/4. Therefore, we have s2 (c) ≤ s 2 (c) + 2 • 1/4 ≤ 19/4. Assume then that (1, 2) ∈ C. It is straightforward to verify that share can be shifted to c only from (-3, 1), (-2, 2), (-3, 2), (-4, 1) and (-5, 1) according to the rules 1.1, 2.3, 3, 5 and 6, respectively. Moreover, it is easy to see that at most one of these rules can be used (and only once). Thus, the codeword c receives at most 1/6 units of share. Hence, we have s2 (c) ≤ s 2 (c) + 1/6 ≤ 19/4 since s 2 (c) ≤ 55/12 by Example 1.

Assume now that (2, 0) ∈ C. Then it is easy to conclude that the vertices (5, 1), (4, 1) and (3, 1) cannot shift share to c. Hence, only either (3, 2) according to the rule 3 or (2, 2) according to the rule 2.2 (but not both) is capable of shifting share to c. In both cases, c receives at most 1/6 units of share. Choosing D = {c, (0, 1), (2, 0)} in Lemma 1, we obtain that s 2 (c) ≤ 13/3. Therefore, since at most 1/4 units of share is received from S 2 , we have s2 (c) ≤ s 2 (c)+1/4+1/6 ≤ 19/4. Finally, assume that (2, 1) ∈ C. By Lemma 1, we have s 2 (c) ≤ 9/2. Since now share can be shifted to c only from S 2 , we obtain that s2 (c) ≤ s 2 (c) + 1/4 ≤ 19/4.

The proofs of the other two cases, where c is adjacent to two or three codewords, are similar to (and even easier than) the one of the first case. Hence, these proofs are omitted here. However, for the proofs, the interested reader is referred to [START_REF] Junnila | Optimal lower bound for 2-identifying code in the hexagonal grid[END_REF].

⊓ ⊔

The proof of the following lemma is analogous to the previous proof and it is omitted in this presentation. However, the complete proof of the lemma can be found from [START_REF] Junnila | Optimal lower bound for 2-identifying code in the hexagonal grid[END_REF].

Lemma 3 ([8]

). Let c ∈ C be a codeword such that c is not adjacent to another codeword and share is shifted to c according to the previous rules. Then we have s2 (c) ≤ 19/4. From now on, we may assume that I 2 (c) = {c}. Furthermore, suppose first that (-2, 1), ( 2 Using similar arguments as above, we obtain that s2 (c) ≤ 19/4 also in this case. Thus, we may assume that (-4, 1) / ∈ C and (-3, 2) / ∈ C. The previous reasoning also applies when we consider the sets {(3, 0), (2, -1)} and {(-3, 0), (-2, -1)} instead of {(-1, 2), (1, 2)}. This leads straightforwardly to the observation that we have only two different neighbourhoods of c (up to rotations and reflections). These neighbourhoods are illustrated in Figure 3.

Consider first the case in Figure 3(a). In what follows, we show that c shifts 1/12 units of share to (-1, 2) or [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Charon | The minimum density of an identifying code in the king lattice[END_REF], or that we originally have s 2 (c) ≤ 5 -1/12 = 59/12. This observation can then be generalized to the (other two) symmetrical cases implying s2 (c) ≤ 5 -3 • 1/12 = 19/4. If (2, 2) ∈ C, then we have s 2 (c) ≤ 29/6 ≤ 59/12. Assume then that (2, 2) / ∈ C. If we can shift 1/12 units of share from c to (-1, 2) according to the rule 8, then we are immediately done. Hence, we may assume that (-2, 3) / ∈ C and (0, 3) / ∈ C. Since (-1, 2) and (1, 2) are 2-separated by C, the vertex (2, 3) belongs to C. Furthermore, since (-1, 2) and (0, 2) are 2-separated by C, at least one of the vertices (-1, 3) and (1, 3) is a codeword. Therefore, at least 1/12 units of share can shifted from c according to the rule 6 or 9.

Consider then the case in Figure 3(b). Let us now show that c shifts at least 1/6 units of share to (-1, -2) or (1, -2), or that we originally have s 2 (c) ≤ 5 -1/6 = 29/6. This result together with the observation above, which states that c shifts 1/12 units of share to (-1, 2) or [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Charon | The minimum density of an identifying code in the king lattice[END_REF], or that we originally have s 2 (c) ≤ 5 -1/12 = 59/12, implies that s2 (c) ≤ 5 -1/6 -1/12 = 19/4. If now (0, -2) ∈ C, then we obtain by Lemma 1 that s 2 (c) ≤ 29/6. Hence, we may assume that (0, -2) / ∈ C. Since c, (-1, -1) and (1, -1) are 2-separated by C, the vertices (-2, -2) and (2, -2) belong to C. Furthermore, since (0, -1) is 2-covered by a codeword of C, we have (-1, -2) ∈ C or (1, -2) ∈ C. Therefore, we can shift at least 1/6 units of share to (-1, -2) or (1, -2) according to the rule 5. In conclusion, if c is a codeword such that I 2 (c) = {c} and (-2, 1), (2, 1), (0, -1) / ∈ C, then we have s2 (c) ≤ 19/4.

Assume then that c is a codeword such that I 2 (c) = {c}, (-2, 1) / ∈ C, (2, 1) / ∈ C and (0, -1) ∈ C. The proof of this case is similar to the previous one. Hence, the proof of this case is omitted here. For the complete proof, we again refer to [START_REF] Junnila | Optimal lower bound for 2-identifying code in the hexagonal grid[END_REF]. Notice that in this case the modified rules 1.1, 2.1 and 7.1 are used.

Finally, assume that c is a codeword such that I 2 (c) = {c}, and that at least two of the vertices (-2, 1), (2, 1) and (0, -1) belong to C. Then, by Lemma 1, we have s 2 (c) ≤ 14/3. This observation completes the proof of the lemma.

⊓ ⊔

In the previous lemmas, we have shown that s2 (c) ≤ 19/4 for any c ∈ C. Now we are ready to prove the main theorem of the paper.

|Q n+6 \ Q n |, (2)
because shifting shares inside Q n does not affect the sum and each codeword in Q n+6 \ Q n can receive at most 19/4 units of share (by Lemma 2 and 3). Notice also that codewords in Q n cannot shift share to codewords outside Q n+6 . Therefore, combining the equations ( 1) and ( 2) with the fact that s2 (c) ≤ 19/4 for any c ∈ C, we obtain

|C ∩ Q n | |Q n | ≥ 4 19 • |Q n-2 | |Q n | - |Q n+6 \ Q n | |Q n | .
Since |Q k | = (2k +1) 2 for any positive integer k, it is straightforward to conclude from the previous inequality that the density D(C) ≥ 4/19. ⊓ ⊔

Fig. 1 .

 1 Fig. 1. The brick wall and the honeycomb representations illustrated.

Lemma 1 .

 1 Let C be an r-identifying code in G and let D be a nonempty subset of C. For c ∈ D, using the previous notations, we haves r (C; c) ≤ k j=1 1 |I j | + (i j -1) 1 |I j | + 1 .Proof. Assume that c ∈ D. Then, for each j = 1, 2, . . . , k, defineI j = {u ∈ B r(c) | I j = I r (D; u)}. Now it is obvious that for at most one vertex u ∈ I j we have I j = I r (C; u) and the other vertices of I j are r-covered by at least |I j | + 1 codewords of C. Hence, the claim immediately follows. ⊓ ⊔ The use of the previous lemma is illustrated in the following example. Example 1. Let C be a 2-identifying code in the hexagonal grid G H . Assume further that D = {(0, 0), (0, 1), (1, -1)} ⊆ C. Now we have I 2 (D; (-2, 1)) = I 2 (D; (-1, 2)) = I 2 (D; (1, 2)) = I 2 (D; (2, 1)) = {(0, 1)}, I 2 (D; (-1, 1)) = I 2 (D; (0, 1)) = I 2 (D; (1, 1)) = I 2 (D; (-1, 0)) = {(0, 0), (0, 1)} and I 2 (D; (0, 0)) = I 2 (D; (1, 0)) = {(0, 1), (0, 0), (1, -1)}. Thus, by Lemma 1, we obtain that

1 , 2 .1 and 7 . 1 .

 1271 Moreover, in the rule 1.1, we shift 1/12 units of share to v whether (-3, 2) belongs to C or not.-If in the rule 1 we have u + (-3, 2) ∈ C, then we shift 1/4 units of share from u to u + (-1, 2) (no share is shifted to v) and denote this new rule by 1.2. -If in the rule 2 we have u + (-3, 1) ∈ C, then we shift 1/6 units of share from u to v and denote this new rule by 2.2. -If in the rule 2 we have u + (1, 2) ∈ C, then we shift 1/12 units of share from u to v and denote this new rule by 2.3.

Fig. 2 .

 2 Fig.2. The rules of the shifting scheme illustrated. The black dots represent codewords and the white dots represent non-codewords. In the rules 7 and 8, at least one of the vertices marked with a white square is a codeword.

Lemma 4 .

 4 Let c ∈ C be a codeword such that no share is shifted to c according to the previous rules. Then we have s2 (c) ≤ 19/4.

Fig. 3 .

 3 Fig. 3. Two cases of the proof of Lemma 4 illustrated.

  , 1), (0, -1) / ∈ C. Since c, (-1, 0), (1, 0) and (0, 1) are 2-separated by C, each of the sets {(-1, 2), (1, 2)}, {(3, 0), (2, -1)} and {(-3, 0), (-2, -1)} contains at least one codeword. Therefore, by Lemma 1, we have s 2 (c) ≤ 1 + 6 • 1/2 + 3 • 1/3 = 5. Consider then the set {(-1, 2), (1, 2)} that contains at least one codeword as stated above. Assume first that both (-1, 2) ∈ C and (1, 2) ∈ C. If the vertex (0, 2) also belongs to C, then we have s2 (c) ≤ s 2 (c) ≤ 14/3 by Lemma 1 (and we are done). Hence, suppose that (0, 2) / ∈ C. If now (-2, 2) ∈ C or (2, 2) ∈ C, then s 2 (c) ≤ 29/6 and the rule 2.3 can be applied to c. Therefore, we have s2 (c) ≤ s 2 (c) -1/12 ≤ 19/4. Thus, we may assume that (-2, 2) / ∈ C and (2, 2) / ∈ C. Since the vertices (-1, 2) and (1, 2) are 2-separated by C, at least one of the vertices (-3, 2), (-2, 3), (2, 3) and (3, 2) belongs to C. Hence, we can shift at least 1/4 units of share from c according to the rule 7. Therefore, we have s2 (c) ≤ s 2 (c) -1/4 ≤ 19/4. By the considerations above, we may without loss of generality assume that (-1, 2) ∈ C and (1, 2) / ∈ C. If (0, 2) ∈ C, then 1/4 units of share can be shifted from c according to the rule 1 or 1.2, and we are done. Thus, suppose that (0, 2) / ∈ C. Assume then that (-2, 2) ∈ C. If the rule 2 applies to c, then we are immediately done (1/4 units of share is shifted from c). On the other hand, if (-3, 1) ∈ C, then by Lemma 1 s 2 (c) ≤ 59/12 and we are again done since at least 1/6 units of share is shifted from c according to the rule 2.2. Hence, assume that (-2, 2) / ∈ C. Since (0, 1) and (-1, 1) are 2-separated by C, the vertex (-3, 1) belongs to C. If now either (-3, 2) ∈ C, or (-4, 1) ∈ C, (-3, 2) / ∈ C and (-3, 0) / ∈ C, then (respectively) either the rule 3 or the rule 4 can be used and we are done. Furthermore, if (-4, 1) ∈ C, (-3, 2) / ∈ C and (-3, 0) ∈ C, then instead of the set {(-1, 2), (1, 2)} we can consider the set {(-3, 0), (-2, -1)}.

Theorem 1 .

 1 If C is a 2-identifying code in the hexagonal grid G H , then the densityD(C) ≥ 4 19 . Proof. Assume that C is a 2-identifying code in G H . Since each vertex u ∈ Q n-2 with |I 2 (u)| = i contributesthe summand 1/i to s 2 (c) for each of the i codewords c ∈ B 2 (u), we have c∈C∩Qn s 2 (c) ≥ |Q n-2 |.


Maarten De Boeck
email: mdeboeck@cage.ugent.be

The Dual Code of Points and t-Spaces in the Projective Space

Keywords: Linear codes, Projective spaces, Small weight codewords

The most important results on C ⊥ t (n, q), the dual code of points and t-spaces in PG(n, q) are presented. We focus on the minimum distance and on the small weight codewords. In the third section, a recent result about the classification of the small weight codewords in C ⊥ n-1 (n, q), q even, is given.

Introduction

In the 1970's, the p-ary code of points and lines in a projective plane was introduced. In the same decade, also the study of the linear code C t (n, q) generated by the points and t-spaces (t-dimensional subspaces) of the projective space PG(n, q) began. The dimensions and minimum distances of these codes have been found and their minimum weight codewords were classified. However, there remain unanswered questions, even in the case of the projective plane PG (2, q). Also in the case of the linear codes of non-Desarguesian projective planes, there are still many open problems.

The dual code C ⊥ t (n, q) of these codes has been studied as well, but, in general, less is known about them. The question about the minimum distance has only been answered in some specific cases. We will start by introducing these codes.

Definition 1. The incidence matrix M n,q,t of the points and the t-spaces in the projective space PG(n, q) is the {0, 1}-matrix whose columns are indexed by the points and whose rows are indexed by the t-spaces, and such that the entries fulfill

(M n,q,t ) i,j = 1 if the i-th t-space contains the j-th point 0 otherwise . (1)
Definition 2. The p-ary code C t (n, q), q = p h and p prime, is the linear code over F p generated by the rows of M n,q,t .

The dimension of the codes C t (n, q), and hence of their duals, is known by a theorem of Hamada.

Theorem 1 ([6]). Let q = p h and let k be the dimension of the p-ary code C t (n, q), 0 < t < n. Then:

k = s0 • • • s h-1 h-1 j=0 L(sj+1,sj ) i=0 (-1) i n + 1 i n + s j+1 p -s j -ip n , (2)
with s h = s 0 . The summation indices fulfill

t + 1 ≤ s j ≤ n + 1 and 0 ≤ s j+1 p -s j ≤ (n + 1) (p -1) , with L (s j+1 , s j ) = s j+1 p -s j p .
For the case t = n -1, i.e. the code of points and hyperplanes, the dimension was known earlier and is given by the following, easier, formula.

Theorem 2 ([5]

). The dimension of the p-ary code C n-1 (n, q), q = p h and p prime, equals

n + p -1 n h + 1 . (3)
2 Minimum distance and small weight codewords for q odd

In this case, the minimum distance is not known in general. However, some theorems giving bounds on these minimum distances or giving relations between these minimum distances, were proven.

Theorem 3 [START_REF] Lavrauw | On the code generated by the incidence matrix of points and k-spaces in PG (n, q) and its dual[END_REF]Theorem 10]). If n ≥ 2 and

1 ≤ t ≤ n -1, then d C ⊥ t (n, q) = d C ⊥ 1 (n -t + 1, q)
, with q = p h and p prime.

Theorem 4 ([1, Proposition 1]). If n ≥ 2 and 1 ≤ t ≤ n -1, then (q + p) q n-t-1 ≤ d C ⊥ t (n, q) ≤ 2q n-t
, with q = p h and p prime.

Combining these results, the minimum distance can be determined when q = p.

Corollary 1. If n ≥ 2, 1 ≤ t ≤ n -1 and p prime, d C ⊥ t (n, p) = 2p n-t .
Since the minimum distances are unknown in general, the codewords of minimum weight cannot be studied. However, if q = p, not only the minimum distances are known, but also the codewords of minimum weight were classified.

Theorem 5 [START_REF] Lavrauw | On the code generated by the incidence matrix of points and k-spaces in PG (n, q) and its dual[END_REF]Theorem 12]). Let c be a codeword of C ⊥ t (n, p), n ≥ 2, 1 ≤ t ≤ n -1 and p prime, with wt(c) = 2p n-t . Then, c = α (c ′c ′′ ) with c ′ and c ′′ the incidence vectors of two (nk)-spaces intersecting each other in an (nk -1)-space, and with α ∈ F * p .

The construction used in this theorem, consisting of the difference of the incidence vectors of two (nk)-spaces with a maximal intersection, was also used in the proof of Theorem 4 to construct a codeword of C ⊥ t (n, q), with weight 2q n-t , thus giving the upper bound for the minimum distance.

The upper and lower bound of Theorem 4 were improved using various techniques. This first theorem is proven by looking at the number of different symbols occurring in the codeword.

Theorem 6 ([11, Theorem 14, Theorem 15]). If n ≥ 2, 1 ≤ t ≤ n -1 and q = p h is odd, with p prime, then d C ⊥ t (n, q) ≥ 1 3 (4θ n-t (q) + 2). Moreover, if p = 7, respectively p > 7, then d C ⊥ t (n, q) ≥ 1 7 (12θ n-t (q) + 2), respectively d C ⊥ t (n, q) ≥ 1 7 (12θ n-t (q) + 6
). Hereby, we used the notation θ i (q) = q i+1 -1 q-1 .

The upper bound was improved by constructing a codeword with weight smaller than 2q n-t , if q is not a prime. Such a codeword was constructed using a minimal blocking set of Rédei type.

Theorem 7 ([10, Theorem 4.13, Theorem 4.14]). There exists a minimal (nt)-blocking set B in PG (n, q) of size |B| = q n-t + δ, such that there is a (nt)-space τ with |B ∩ τ | = δ = q n-t-1 q-1 p-1 + q n-t-1 -1 q-1 . Denote the incidence vector of B by c B and the incidence vector of τ by c τ . Then c Bc τ ∈ C ⊥ t (n, q) and wt (c Bc τ ) = 2q n-tq-p p-1 q n-t-1 .

Corollary 2 ([10, Corollary 4.15]). If n ≥ 2, 1 ≤ t ≤ n -1 and q = p h with p = 2 prime, then d C ⊥ t (n, q) ≤ 2q n-tq-p p-1 q n-t-1 .

Apart from the case q = p, the exact minimum distance of C ⊥ t (n, q) is only known for q = p 2 , n = 2, t = 1, p ∈ {3, 5}, if q is odd.

Theorem 8 ([7], [2, Corollary 1.2], [8, Theorem 1]). -d C ⊥ 1 (2, 9) = 15, -d C ⊥ 1 (2, 25) = 45, -88 ≤ d C ⊥ 1 (2, 49) ≤ 91.
The lower bound given for p = 7 is better than any of the lower bounds derived before. The upper bound coincides with the upper bound of Corollary 2.

Minimum distance and small weight codewords for q even

In this case, the minimum distances are known. Moreover, we have a result on the codewords of minimal weight.

Theorem 9 ([1, Theorem 1]). Let q = 2 h and 0 < t < n, then d C ⊥ t (n, q) = (q + 2) q n-t-1 .

Theorem 10 ([11, Theorem 11]). Consider a codeword c ∈ C ⊥ t (n, q), 0 < t < n, such that wt (c) = d C ⊥ t (n, q) . Then supp (c) is contained in an (n-t+1)space of PG (n, q). Definition 3. A hyperoval is a point set H in PG (2, q), q even, such that every line in PG (2, q) intersects H in 0 or 2 points.

The proof of Theorem 9 has two parts. In the first part, it is proven that (q + 2) q n-t-1 is a lower bound on the minimum distance, using earlier work of Delsarte. In the second part, it is proven that this lower bound is sharp by constructing a codeword of weight (q + 2) q n-t-1 in the following way. Let V be a plane and σ an (nt -2)-space skew to it, and let H be a hyperoval in V . Consider the cone σH, with σ as vertex and H as base. Then the incidence vector of σH \ σ is a codeword c ∈ C ⊥ t (n, q), with wt(c) = (q + 2) q n-t-1 . The codewords constructed above are codewords of minimum weight. It is however not proven that all codewords of minimum weight can be constructed in this way. For the geometrical interpretation of codewords of minimum weight in C ⊥ t (n, q), we can only rely on Theorem 10. About the codewords of small, non-minimum weight, nothing is known in general.

Recently however, the classification of the small weight codewords was done for the case t = n -1; this is the dual code of points and hyperplanes. If we look at the codewords of minimum weight q + 2 in this code, we know by Theorem 10 that the support of such a codeword is contained in a plane. It can easily be seen that their support must be a hyperoval. Hyperovals are examples of even sets. Definition 4. An even set is a point set in PG (2, q), q even, such that every line in PG (2, q) intersects S in an even number of points.

Other examples of even sets are the symmetric difference of an even number of lines, the symmetric difference of hyperovals and the so-called (q + t)-arcs of type (0, 2, t) (see [START_REF] Gács | On (q + t)-arcs of type (0, 2, t)[END_REF][START_REF] Korchmáros | On (q + t)-arcs of type (0, 2, t) in a desarguesian plane of order q[END_REF][START_REF] Vandendriessche | Codes of Desarguesian projective planes of even order, projective triads and (q + t, t)-arcs of type (0, 2, t)[END_REF]). By an easy counting argument, one can see that the number of points of an even set is always even.

It is obvious that the incidence vector of an even set in a plane of PG(n, q) is a codeword of C ⊥ n-1 (n, q). One might expect that all the small weight codewords are the incidence vector of an even set in a plane of the projective space. The following two theorems state that this turns out to be true. However the width of the interval of weights for which all codewords are the incidence vector of an even set depends on the fact whether q is a square. If q is a non-square, this width is at least 3 q 2 . If q is a square, this width is 2 √ q -3. In this case, a second possibility for the geometrical interpretation of the codewords pops up as soon as the weight of the codewords exceeds q + 2 √ q -1. The support of the next codewords is contained in a 3-space.

Theorem 11 ([3, Theorem 5.3]). Let c be a codeword in C ⊥ n-1 (n, q), q even, with wt (c) ≤ q + 3 q 2 + 1.

-If q is a non-square or q ∈ {4, 16}, then c is the incidence vector of an even set in a plane of PG (n, q). -If q is a square and q ≥ 64, then c is the incidence vector of an even set in a plane of PG (n, q) or the incidence vector of a set in a 3-dimensional Baer subgeometry B in PG (n, q) such that the restriction of c to the positions indexed by the points of B is a codeword of C ⊥ 1 3, √ q .

Theorem 12 ([3, Corollary 4.13]). Let c be a codeword in C ⊥ n-1 (n, q), q = 2 h ≥ 64 a square, such that wt (c) < q + 2 √ q. Then, it is the incidence vector of an even set in a plane of PG (n, q).

The proof of both theorems relies on the classification of the small blocking sets. We have a closer look at the second possibility occurring in the case q ≥ 64 square.

Theorem 13 ([3, Theorem 4.12]). If c ∈ C ⊥ 1 3, √ q , q even, is completed to a vector c by zeros on the positions indexed by the points of PG (n, q) \B, with B a 3-dimensional Baer subgeometry in PG (n, q), then c ∈ C ⊥ n-1 (n, q).

Hence, the bound of Theorem 12 is sharp. It corresponds with the bound d C ⊥ 1 (3, √ q) = q + 2 √ q, given by Theorem 9.

⋆ The research of the author is supported by FWO-Vlaanderen (Fund for Scientific Research -Flanders).


James McDougall (éd.), "Nation, Society and Culture in North Africa", Journal of North African Studies, vol.8, n°1, 2003, 35-42. An earlier version of this article was presented to the Tunisian Association for the Promotion of Film Criticism (ATPCC) in Tunis in 1994. Feature-length films produced in Tunisia since 1956now (September 2002) number around 100. The production examined here consists of those 60 or so films made in the first 40 years of Tunisian independence.

IDEOLOGIES OF THE NATION IN TUNISIAN CINEMA

KMAR Kchir Bendana

What is Tunisian cinema? Or, what do we understand by 'Tunisian' cinema? Would it be simply the totality of films produced since the country's independence by directors of Tunisian nationality, in Tunisian studios with Tunisian crews and budgets? Or all films shot in Tunisia? These criteria, which are national' at least in the sense of juridical and financial nationality', are generally appropriate in respect of the 60 or so films which can be considered as constituting a corpus of contemporary (that is, post-independence) Tunisian cinematography. The considerations which I shall develop here revolve around a central question, that of understanding what is signified by 'Tunisian', or tunisianité, and are intended as an attempt to read, through the diverse marquetry of cultural production represented by these films, the various meanings which they give to the 'nationality' they apparently share.

What can we understand by 'tunisianité'? And how is such a national identity expressed through such varied artistic works? Or rather, how does the ideological expression of 'the national' manifest itself, on different levels, according to different viewpoints and approaches? in other words, what we are seeking to isolate, in sociological terms, is the relation between the material bases of social organisation and the most highly elaborated forms of intellectual, artistic and cultural production; taking the Tunisian cinema as a case study, I observe in this article the field constituted by 40 years' production of films in order to test a grille de lecture, experiment with certain definitions, and advance a certain number of hypotheses.

Since I have raised the notion of 'ideology', I should first of all explain which of ail its definitions I mean -although several would suit the present purpose. Among them -ideology as the science of ideas (as facts of consciousness, their nature and laws), or, by extension, the study of a system of ideas, that is, of a philosophy of the world and of life or, again, as a classical Marxist reading would have it, the totality of ideas and beliefs particular to a given global historical period, society or class -I opt for the point of view presented by Althusser, that ideology is the imaginary relation of individuals to their real conditions of existence. 1 The term thus designates the totality, not only of representations, but also of practices and behaviour both conscious and unconscious. 'National identity' here does not, then, mean the supposedly 'objective' criteria held to characterise a nation -territorial space, language, and juridical considerations were only just appropriate for the initial steps towards an insufficient definition with which we began. To 'belong to a nation' is to adhere, voluntarily or not, consciously or not, to a representation -not to a political regime, nor to a doctrine or a culture, but to the framework within which all of these are expressed, the ideological form of modern social community.2 An idea, or ideology, of the nation is not reducible to nationalism, and vice versa; nationalism might rather be thought of as one possible form of expression of the broader system of a national ideology, a form most often today identified as pathological, as a hypertrophy of national sentiment. For our purposes here, I consider 'nationalism' as one level of ideological expression which might be encountered in the reading of our corpus of films -in official discourse, in propaganda, in underlying assumptions -but which might equally be encountered, diffused or explicit, in the writing of some of our films' critics. There are, for example, certain affirmations made here and there in the press or in literature on the subject which deserve attention. Tunisian cinema has a 'national tonality' less acute than that of its Algerian neighbour3 (where 'national' means what I call 'nationalist'). Tunisian cinema in the 1970s arrived at a certain 'Tunisian ethic';4 the same decade is said to have witnessed the creation of a 'national cinematographic aesthetic'.5 Such question-begging uses of the terms 'Tunisian' and 'national' oblige us to interrogate the films themselves in order to investigate what is meant by their being 'Tunisian' or 'national', and what is the ideology of the national in this 'Tunisian' cinema.

One attitude, common to a certain number of films, and whose decoding is extremely simple, is first and most obviously remarkable. Pure political engagement marks those films which take as their subject the political history of nationalism, exalting with a certain gusto a glorious national history, relating the struggle for the country's political liberation from colonialism. One thinks in particular of the films of Omar Khlifi, a director whose début, al-Fajr ('The Dawn') of 1966, is considered the first Tunisian film. He would go on to make three further films: Le rebelle, ('Rebel', 1968); Les fellaghas, ('Bandits ', 1970);and Hurlements, ('The Roaring', 1972). Khlifi produced a cinema which relates and illustrates in its images exactly what is produced and reproduced by school history books, radio and television programmes, and all the official public histories. These films define themselves as national because they are nationalist. Their content and tone is determined by what 'the nation' says, tells itself, and teaches about itself. The struggle against colonialism is idealised, presented as a uniformly heroic enterprise in such a way as to serve directly, through cinema, the project of constructing a nationalist epic in line with a state-sponsored cultural production dominated by unanimism. The creation of the production company SATPEC (Société Anonyme Tunisienne de Production et d'Exploitation Cinématographique) in 1959, and then the building of a film laboratory at Gammarth, completed in 1967, were essentially political decisions, intended to give the new national cinema an infrastructure which would allow it to develop.

The recent history which the first films set out to dramatise, of Course, was not nearly so simple and Manichean as it appears in Khlifi's work. Other directors, recognising the forgotten aspects of official history, revisited it, attempting to repair earlier omissions and tackling subjects which are not generally mentioned in treatments of the country's recent past. Abdellatif Ben Ammar's Sejnene (1973 -the title is taken from the name of a small agricultural and mining town in northern Tunisia) dealt with the workers' movement, rereading the history of national liberation through the story of the UGTT (Union Générale des Travailleurs Tunisiens, the Tunisian General Workers' Union, founded in 1946). Through the story of a print-worker and his son seen during the events of 1952-54, a crucial period of contemporary Tunisian history, the director sought to restore to the labour movement as a whole its place in the anticolonial struggle. Et Demain, ('And Tomorrow', 1972) by Brahim Babaï confronted two crucial problems of the immediate post-independence period -unemployment and the exodus from the countryside. The condition of immigrants in France was the burning subject of the moment when Naceur Ktari made Les Ambassadeurs in 1975. The film, set in the Goutte d'Or district of Paris (an area heavily populated by North African immigrants), plays on the grandiloquent and misleading title of 'ambassadors' given by the authorities at home to the migrants, whose living and working conditions give the lie to rosy official rhetoric.

Women, although never absent from the more 'officially' nationalist films, (Khlifi's Hurlements, for example), became heroines in their own right in this second category, which seemed intent on giving women the place of honour in a 'revised and corrected' national history whose task was the rehabililation of all those who had previously been forgotten. This was thus a cinematography whose political engagement had a revisionist agenda, but its desire to testify about Tunisian society and history was nonetheless articulated in the same affirmative register as more 'traditional' nationalism. This is true even of a film like Sejnene, which, despite its highly original viewpoint, did not depart from the fixed chronological scheme of those key dates accepted by everyone, more or less, as developmental steps of the national movement and through which the history of the struggle for liberation is told via that of the political parties. When, in Soleil des Hyènes ('Hyenas Sun ', 1976), Ridha Behi mounted a critique in which the ravages of the tourist industry were perceived as acts of rape, (the film showed the brutally penetrative impact of the expansion of tourism in a fishing village, where the new economy smashes social relations, the labour market, the landscape, and property rights...) it was, again, a question of affirming the 'defence of the nation'. Brahim Babaï was working from a similarly nationalist perspective in composing his political statement, La Nuit de la Décennie (1990) which dealt with the causes of the 1978 clashes between the regime and the workers' union. All these films have a second common denominator. They all focus on characters who generally lack consistency and exist only as symbolic flag wavers. Even when, in the best works, the characters have a certain depth, they nonetheless remain prisoners of prototypes: the traitor, the patriot; the bourgeois, the worker, the woman -a necessarily positive characterthe colonist, the intellectual, the bureaucrat. The ideology of the nation is thus expressed through a gallery of highly characteristic 'Tunisians'! Despite their entirely different genres -since they are, variously, Western-style epics, neo realist statements or quasi-documentary reportages, these films exhibit the same tendency to address tunisianité through a typology of more or less archetypal characters.

Other film makers, nonetheless, understood the impossibility of determining exactly what 'the national' signifies, appreciating that no representation of social or political history can ever exhaust the question of tunisianité by giving it a total and definitive form. Their films express in a more nuanced fashion the ambiguities and difficulties of being Tunisian. The 1969 film Khlifa Lagraa ('Khelifa the Bald') is emblematic of this approach. Director Hamouda Ben Halima describes with great individuality and a highly poetic economy of style the malaise of a man exceptionally authorised (or condemned) to enter the closed and private world of women by a skin disorder which leaves him bald. A few years later, Au Pays de Tararini, (1972) a collective film made up of short cinematic sketches, evoked the old city of Tunis. In its best moments achieving a level of refinement and intimacy comparable with those of Ben Halima's Khlifa Lagraa, the film sought to anchor itself in a mythical past, and represents the first appearance of what might be called the nostalgic side of Tunisian cinema. The past is reasserted, here, in warm retrospection, but can the return to certain values and sources of the urbane Tunisois, thus reclaimed through a certain stylised imagery, constitute the hallmark of tunisianité? An explicit interest in the work of Tunisian novelists characterises this tendency, which finds its legitimate subjects (Khelifa le Teigneux, Tararini, Barg Ellil) in the writings of Ali Douaji6 and Bechir Khraïef. 7Curiously, a film as radical and Brechtian as the Nouveau Théâtre's La Noce ('The Wedding') can also be considered, at least as regards its dialogue, as representative of this nostalgic current. However different the films undoubtedly are in form, La Noce (1978) can be read alongside Ali Labidi's Barg Ellil (1990) which relates in a conventional, televisual style a story of life in Tunis in the fifteenth century, at the time of the Spanish invasion, as weil as Halfaouine, L'enfant des terrasses (1990) in which Ferid Boughedir amuses himself with his childhood memories, Soltane el Madina, (1992) Moncef Dhouib's reflection on the degeneration of the old town's districts, or more recently Les Silences du Palais (1994), a film by Moufida Tlatli in which the action takes place around the end of the beylicate in the 1950s. In all these films one can observe a particular attention paid to language in the scripting of the dialogues, which most frequently employ a tunisois dialect, vehic1e of a certain, specific notion of tunisianité which is reductive and not, of course, shared by all.

For other directors, Tunisian identity is to be found in the countryside. Taïeb Louhichi's L'Ombre de la Terre ('The Shadow of the Land'), (1982) a chronic1e of the life of a nomadic community at the edge of the desert, is the most significant example of a group of films which have sought to glorify the rural world; Ali Abdewahab, in Om Abbès (1969), andOmar Khlifi in Hurlements (1972), also attached themselves to the effort of rehabilitating with a great deal of theatricality and rather less accuracy -a bedouin world that had been abandoned and ignored.

A further attempt to problematise dominant notions of 'national identity' emerged in work addressing the delicate question of biculturalism and plural identity, a tendency which emerged relatively early in Tunisian cinema with films like Mokhtar (1968) by Sadok Ben Aïcha, which related in episodic fragments the suicide of a young, francophone Tunisian novelist, and Une si Simple Histoire (1970) by Abdellatif Ben Ammar, who demanded of his audience a reflection on the déchirement of a Tunisian intellectual married to a Frenchwoman. The same director's Aziza (1980) similarly explored the difficulties of adapting from traditional ways of life to modern living, through the emigration of an artisan from the heart of the old medina, symbol of a disappearing socio-cultural urban network, to a newly built suburb. The changes in socio-economic conditions and values observed through this spatial shift appear limitless, as one of the characters, Aïcha, leaves with a Gulf emir, dazzled by the mirage of an easy life which marriage to him seems to offer.

A concern with boundaries, borders and imposed limitations also animates Mahmoud Ben Mahmoud 's Traversées (1982), whose action takes place outside Tunisia, and relates the painful failure of the attempted 'crossings' of the title through the story of a Tunisian intellectual's inability to cross a European frontier. More recently, Chichkhane, ('Diamond Oust', 1991) by Mahmoud Ben Mahmoud and Fadhel Jaïbi, and Les Zazous de la Vague, (1992) by Mohamed Ali Okbi, both explore (the latter in parodic mood) the complexity of a 'Tunisian identity' subject to the countervailing forces which pull their characters in different directions: these two films address, respectively, cultural mix, and the refusal to accept one's condition in life. The cohabitation of -at least -two identities, 'eastern' and 'western', is treated here in quite different ways, sometimes in a grave and even tragic tone (as in Diamond Dust), alternatively in a comical vein (Les Zazous).

In such films, which demonstrate a particular sensitivity arrived at through the development of cinematography in Tunisia more generally, it becomes possible to identify particular expressions of locality and singularity. The appearance of film makers working in this vein, such as Néjia Ben Mabrouk and Nouri Bouzid, consecrated an interest in film capable of scrutinising its characters, one which would endow them with a psychological density transcending simple typologies. Around the characters of their films, these directors construct a meticulously precise and realistic vision of space, décor and dialect, creating a specific ambiance and constituting a depth and sincerity for their protagonists, heroes who can finally be apprehended in the full complexity of their contradictions. Earlier works, it is true, had already given a foretaste of this achievement: well before Néjia Ben Mabrouk's La Trace (1982) or the 1986 production L'Homme de Cendres by Nouri Bouzid (a true homage to the old city of Sfax), Ahmed Khéchine, in his 1969 film Sous la Pluie de l'Automne, succeeded in depicting the conflicts of a poor family in Kairouan with a remarkably sure eye and tone -albeit without ever liberating himself from suppositions about 'the national' as a pre-existing given simply requiring illustration, rather than a problem in need of creative exploration. The culmination of this approach can be seen in Nouri Bouzid's sketch, C'est Schéhérazade qu'on assassine ('Murdering Sheherazade') in the collective film La Guerre du Golfe et Après...(1992), which addresses the 1991 war in the Gulf, an event translated into a spectacular worldwide phenomenon by its televisual hyper-mediatisation, through the lens of the everyday life of a Tunisian family. The director, concentrating his gaze on small, tightly circumscribed facts, succeeded in exposing a larger reality, one which gained the film a considerable audience. It is, in fact, local, particularistic films, assuming their specificity and presenting it in a way which is globally accessible, which have more recently achieved the greatest success at Tunisian box offices, and which have also most attracted foreign audiences: witness the popular success of Halfaouine, L' Homme de cendres and Les Silences du Palais.

Yet other directors have opted to ignore, or to refuse, the flagging of national colours; in such films, where some notion of tunisianité is not immediately evident, we might ask ourselves what significance such an absence might have. In establishing an ad hoc inventory of these films it is quickly apparent that they appeared very early on in Tunisian cinema -films which played on allegory or which effaced certain stock themes of 'Tunisianness '. In Yusra, (1972) Rachid Ferchiou set the action of his fantastic tale in an indeterminate Mediterranean space, as if to accentuate its ethereal aesthetic. Claude d 'Anna and Férid Boughedir's La Mort Trouble (1969) explored the master-slave problematic, but in an esoteric style, to investigate the colonial situation from an oblique angle. The Nouveau Theatre's Arab (1988) equally employed the detour of metaphor -in this case, the siege of a derelict cathedral-to explore the threats posed to Tunisia by conflicts in other Arab states, whereas Les Baliseurs du Désert, a (1984) film by Naceur Khémir, took refuge in allegory, beyond the limitations of any specific time, to pursue its search for the meaning of lost cultural values.

There is, too, a further wave of films -Mon Village (1979) by Mohamed Hammami, in which the village of the title is that of a group of Palestinian fida'iyin; Leila ma Raison (1989, the plot is that of a famous, seventh century Arabian legend, mediated through a novel by André Miquel of which the screenplay is an adaptation) by Taïeb Louhichi; La Ballade de Mamelouk (1982) by Hafedh Bouassida;Les Anges, (1984); Champagne Amer, (1986), and Les Hirondelles ne meurent pas à Jérusalem (1994), by Ridha Béhi; and finally Naceur Khémir's Le Collier Perdu de la Colombe (1988). The makers of these films, perhaps for reasons of marketing and distribution, have deliberately chosen as their setting spaces which evoke Tunisia only indirectly, if at all. Their screenplays, too, employ foreign languages or dialects, or else are couched in literary Arabic, or in an artificial, 'rootless' Arabic, supposedly comprehensible anywhere and thus capable of carrying tunisianité -whatever their tunisianité would then be -into a market-place otherwise inaccessible to an overly specific local ('national') production. Work in this vein, sacrificing local particularity, has yet to prove its commercial and artistic effectiveness, and the allegorical detours through which it finds expression demonstrate in themselves the difficulties of 'speaking the national' through filmand, thereby, also themselves speak of the complexity which 'Tunisian', if these are 'Tunisian' films, entails.

The brief, panoramic overview which I have attempted to sketch illustrates the variety of Tunisian film-makers' responses to the question of 'the national', whether the question itself is central to their preoccupations or uncomfortably lingers on the periphery of their vision. The inescapability, in any event, of 'national' classification, of 'being national', in whatever sense, and somehow expressing an ideology of the nation, is perhaps a reflection of the overwhelming dominance of what Balibar calls the 'nation-form'8 in global political and ideological organisation. Contemporary Tunisian cinema is obliged to organise and present itself as a 'national cinema' in a market where it has to face other national cinemas -Algerian, Egyptian, French -and all others (Indian, British, Italian cinema) do likewise, in the face of American cinema, which alone, perhaps, in the global marketplace is capable of transcending (or sufficiently extending?) its own frontiers and specific traits, and of imposing itself as 'translational'.

'L'idéologie et appareils idéologiques d'Etats', La Pensée (June 1970). Reprinted in English, 'Ideology and Ideological State Apparatuses' in Louis Althusser, Essays on Ideology (London: Verso 1984).

See the remarks of Pierre Nora, 'Présentation' in Les lieux de mémoire, vol.I, La nation (Paris: Gallimard 1986), especially, p.x.

Guy Hunebelle, in Férid Boughedir, Introduction aux Cinémas du Maghreb, special issue of Ciném'Action, (Paris, 1980) p.6.

Victor Bachy, Le cinémade Tunisie, 1956-77, (Tunis: STD 1978) p.147.

Férid Boughedir (note 3) p.67.

 A Tunisian novelist and short story writer, he was a member of the famous literary and artistic group Taht Essour ('Below the Ramparts') and also wrote radio plays, song lyrics.

 A writer, born in the Tunisian south, of novels and novellas which were serialised in the Tunis press, notably in the review al-Fikr

Etienne Balibar, 'The Nation Form: History and Ideology', in E. Balibar and Immanuel Wallerstein, Race, Nation, Class: Ambiguous Identities (London: Verso 1991).