Damien Jamet
email: damien.jamet@loria.fr

Jean-Luc Toutant
email: jean-luc.toutant@lirmm.fr

Minimal arithmetic thickness connecting discrete planes

Keywords: Discrete geometry, arithmetic discrete planes, connectedness

While connected arithmetic discrete lines are entirely characterized, only partial results exist for the more general case of arithmetic discrete hyperplanes. In the present paper, we focus on the 3-dimensional case, that is on arithmetic discrete planes. Thanks to arithmetic reductions on a vector n, we provide algorithms either to determine whether a given arithmetic discrete plane with n as normal vector is connected, or to compute the minimal thickness for which an arithmetic discrete plane with normal vector n is connected.

Introduction

The discrete geometry attempts to provide an analogue of Euclidean geometry for the discrete space Z n . Such an investigation has not only theoretical motivations, but also practical applications since digital images can be seen as arrays of pixels.

In [START_REF] Reveillès | Géométrie discrète, calcul en nombres entiers et algorithmique[END_REF], J.-P. Reveillès initiated a new approach for linear discrete objects and defined arithmetic discrete lines as sets of pair of integers satisfying a double Diophantine inequality. The arithmetic discrete line with normal vector n ∈ R 2 , translation parameter µ ∈ R and arithmetic thickness ω ∈ R is the set L(n, µ, ω) defined by:

L(n, µ, ω) = v = (v 1 , v 2 ) ∈ Z 2 ; 0 ≤ l n,µ (v) < ω , where l n,µ (v) = n 1 v 1 + n 2 v 2 + µ.
Geometrically, it can be viewed as the set of integer points in a strip bounded by two parallel Euclidean lines. The width of this strip is ruled by the arithmetic thickness, which plays a key role in the definition. In particular, the connectedness of a given arithmetic discrete line is entirely characterized by its arithmetic thickness.

The definition of arithmetic discrete lines extends naturally to the definition of arithmetic discrete planes in the 3-dimensional discrete space Z 3 , and to the definition of arithmetic discrete hyperplanes in higher dimensions [START_REF] Andres | Discrete analytical hyperplanes[END_REF].

It is thus natural to expect a deep relation between the connectedness of an arithmetic discrete hyperplane and its arithmetic thickness. In fact, the 2dimensional case is somewhat confusing since a connected arithmetic discrete line is also a separating set (see Section 2). Indeed, it is easy to characterized this last property for discrete planes with the arithmetic thickness, whereas it is yet unclear under which kind of conditions such a discrete object is connected.

Connectedness is a main topological property for the characterization and the understanding of discrete objects. Discrete planes are fundamental primitives in volume modelling. Improving the knowledge on connected discrete planes is thus of wide interest from theoretical perspective and may also lead to new powerful tools and applications. Besides, a section is devoted to this problem in [START_REF] Brimkov | Digital planarity -a review[END_REF] In the present paper, we deal with the following questions:

1. Given n ∈ R 3 , µ ∈ R and ω ∈ R, is P(n, µ, ω) connected? 2.
Given n ∈ R 3 and µ ∈ R, how much is the thickness of the thinnest connected arithmetic discrete plane with normal vector n and translation parameter µ?

These questions have already been addressed. In [START_REF] Andres | Discrete analytical hyperplanes[END_REF], E. Andres, R. Acharya and C. Sibata characterized separating arithmetic discrete hyperplanes as connected set. This result gave a partial answer to the first question. In [START_REF] Gérard | Periodic graphs and connectivity of the rational digital hyperplanes[END_REF], Y. Gérard deeper investigated it. He provided an algorithm which determines whether a rational arithmetic discrete hyperplane, that is, with a normal vector n ∈ Z d , is connected. He reduced the (possibly) infinite graph of connectedness of the considered arithmetic discrete hyperplane to a finite one by quotienting it by a subgroup of the lattice of periods of the arithmetic discrete hyperplane. In [START_REF] Brimkov | Connectivity of discrete planes[END_REF], V. Brimkov and R. Barneva focused on the second question. They introduced explicit formulas for some particular cases and provided an algorithm for the general case. Unfortunately, their algorithm appears to be incorrect [START_REF] Jamet | On the connectedness of rational arithmetic discrete hyperplanes[END_REF].

In the present paper, we extend previous work [START_REF] Jamet | On the connectedness of rational arithmetic discrete hyperplanes[END_REF] and give short and elementary algorithms, which take a vector n ∈ Z 3 as input and answer to both previously mentioned questions: to determine whether an arithmetic discrete plane is connected and to compute the minimal thickness making it connected. While Y. Gérard, V. Brimkov and R. Barneva approaches need to determine a connected component, our algorithms are entirely arithmetic and do not need to consider any graph of connectedness.

Basic Notions and First Properties

The aim of this section is to introduce the basic notions and definitions we use throughout the present paper.

Let d be an integer equal or greater than 2 and let {e 1 , . . . , e d } denote the canonical basis of the Euclidean vector space R d . Let us call discrete set, any subset of the discrete space Z d . In the following, for the sake of clarity, we denote by (x 1 , . . . , x d ) the point x

= d i=1 x i e i ∈ R d . An integer point v ∈ Z d is called a voxel (or a pixel if d = 2) and a subset of Z d ,a discrete set. Definition 1 (κ-adjacency). Let κ ∈ {0, . . . , d -1}. Two voxels v, w ∈ Z d are said to be κ-adjacent if: v -w ∞ = 1 and v -w 1 ≤ d -κ. Remarque 1. v ∞ = max i∈{1,...,d} {|v i |} and v 1 = d i=1 |v i |.
In other words, the voxel v and the voxel w are κ-adjacent if they are distinct, the differences of their coordinates are at most 1 and v and w have at most d -κ different coordinates. A κ-path is a (finite or infinite) sequence of consecutive κ-adjacent voxels. If (γ i ) 1≤i≤n is a finite κ-path, then we say that γ links the voxel γ 1 to the voxel γ n .

Definition 2 (κ-connected sets). Let E be a discrete set and let κ ∈ {0, . . . , d -1}. Then E is κ-connected if, for each pair of voxels (v, w) ∈ E 2 , there exists a κ-path in E linking v to w.

In [START_REF] Reveillès | Géométrie discrète, calcul en nombres entiers et algorithmique[END_REF], J.-P. Reveillès introduced the arithmetic discrete line as a set of integer points satisfying a double Diophantine inequality.

Definition 3 (Arithmetic discrete lines [START_REF] Reveillès | Géométrie discrète, calcul en nombres entiers et algorithmique[END_REF]). Let n ∈ R 2 , µ ∈ R and ω ∈ R. The arithmetic discrete line L(n, µ, ω) with normal vector n, translation parameter µ and arithmetic thickness ω is the discrete set defined by:

L(n, µ, ω) = v ∈ Z 2 ; 0 ≤ l n,µ (v) < ω , (1)
where

l n,µ (v) = n 1 v 1 + n 2 v 2 + µ.
This definition extends in a natural way to higher dimensions:

Definition 4 (Arithmetic discrete hyperplanes [1, 2]). Let n ∈ R d , µ ∈ R and ω ∈ R.
The arithmetic discrete hyperplane P(n, µ, ω) with normal vector n, translation parameter µ and arithmetic thickness ω is the discrete set defined by:

P(n, µ, ω) = v ∈ Z d ; 0 ≤ p n,µ (v) < ω , ( 2
)
where p n,µ (v) = µ + d i=1 n i v i .
Definition 5 (Rational arithmetic discrete hyperplanes). If there exists α ∈ R * such that αn ∈ Z d , then the arithmetic discrete hyperplane P(n, µ, ω) and its normal vector n are said to be rational.

Throughout the present paper, if P(n, µ, ω) is a rational arithmetic hyperplane, then we assume, without loss of generality, n ∈ Z d , µ ∈ Z, ω ∈ Z and gcd{n 1 , . . . , n d } = 1 [START_REF] Andres | Discrete analytical hyperplanes[END_REF].

In [START_REF] Reveillès | Géométrie discrète, calcul en nombres entiers et algorithmique[END_REF], J.-P. Reveillès showed how the κ-connectedness of an arithmetic discrete line only depends on its normal vector and its thickness:

Theorem 1 ([1]). Let n ∈ R 2 , µ ∈ R and ω ∈ R. The arithmetic discrete line L(n, µ, ω) is 0-connected (resp. 1-connected) if and only if ω ≥ n ∞ (resp. ω ≥ n 1 ).
It becomes natural to try to extend Theorem 1 to higher dimensions, that is, given n ∈ R d , µ ∈ R and κ ∈ {0, . . . , d -1}, to try to characterize the thickness of the thinnest κ-connected arithmetic discrete hyperplane with normal vector n and translation parameter µ.

Nevertheless, it is not difficult to exhibit a 0-connected arithmetic discrete plane P(n, µ, ω) with ω < n ∞ (see Fig. 1). Similarly, one easily finds a 2-connected arithmetic discrete plane P(n, µ, ω) with ω < n 1 . In fact, the case of arithmetic discrete lines is somewhat confusing. Indeed, in Z 2 , an arithmetic discrete line is κ-connected if, and only if, it separates (in some sense to define) the discrete space Z 2 . Let us introduce the notion of κ-separating sets.

Definition 6 (κ-separating sets). Let E be a discrete set and κ ∈ {0, . . . , d-1}. Then E is said to be κ-separating in Z d if its complement in Z d has exactly two κ-connected components.

It directly follows from Theorem 1:

Corollary 1. Let n ∈ R 2 , µ ∈ R and ω ∈ R. The arithmetic discrete line L((n, µ, ω) is 0-separating (resp. 1-separating) if and only if ω ≥ n 1 (resp. ω ≥ n ∞ ).
Although Theorem 1 does not seem to extend naturally to higher dimensions, there exists a quite nice extension of Corollary 1 relating to the κ-separating arithmetic discrete hyperplanes.

For the sake of clarity, let us introduce a notation, providing a norm on R d .

Definition 7 (κ-minimality norms). Let x ∈ R d , κ ∈ {0, . . . , d -1} and let σ be a permutation over the set {1, . . . , d} satisfying:

∀i ∈ {1, . . . , d -1}, |x σ(i) | ≤ |x σ(i+1) |. The κ-minimality norm ]x[ κ of x is: ]x[ κ = d i=d-κ |x σ(i) |.
In other words, ]x[ κ is equal to the sum of the (κ+1) greatest absolute values of the coordinates of x. One easily checks that, for each κ ∈ {0, . . . , d -1}, the map ]

• [ κ : R d -→ R d is a norm on R d . Moreover, one has ]x[ 0 = x ∞ and ]x[ d-1 = x 1 .
In Z 2 , the κ-connected arithmetic discrete lines are exactly the (2 -(κ + 1))separating ones and Corollary 1 extends in any dimension d ≥ 2 as follows:

Theorem 2 (κ-separating hyperplanes [2]). Let n ∈ R d , let µ ∈ R and let ω ∈ R. Let κ ∈ {0, . . . , d -1}. The arithmetic discrete hyperplane P(n, µ, ω) is κ-separating in Z d if and only if ω ≥ ]n[ κ .
Let us now notice that the fact that an arithmetic discrete hyperplane P(n, µ, ω) κ-separates Z d does not depend on the translation parameter µ.

Moreover, one shows that, given two rational arithmetic discrete hyperplanes P and P ′ with the same normal vector n ∈ Z d , then P is the image of P ′ by a translation: µ can be expressed as an integer linear combination of the coordinates of n, thanks to Bezout's Lemma. Hence, for all κ ∈ {0, . . . , d -1}, the κ-connectedness of a rational arithmetic discrete hyperplane P(n, µ, ω) does not depend on µ. In other words, P(n, µ, ω) is κ-connected if and only if so is P(n, 0, ω). In the general case, one does not know whether the κ-connectedness of an arithmetic discrete hyperplane depends on its translation parameter. [START_REF] Brimkov | Plane digitization and related combinatorial problems[END_REF] gives an idea of current knowledge on planes with arbitrary real coefficients.

Consequently, although it only provides a partial answer of our problem, we focus on the present paper on the arithmetic discrete planes with null translation parameter. For the sake of clarity, we refer to them by P(n, ω) and to the map p n,0 by p n .

In the following sections, we investigate the three classes of connected arithmetic discrete planes. Let us start with the easiest case, that is, the 2-connected arithmetic discrete planes. The other cases can be deduced from that one.

2-connected arithmetic discrete planes

Let us first introduce some technical properties.

Technical properties

Lemma 1 (A lower bound). Let n ∈ R 3 and ω ∈ R. If the arithmetic discrete plane P(n, ω) is 2-connected, then ω ≥ n ∞ .
Proof Without loss of generality, let us suppose that 0

≤ n 1 ≤ n 2 ≤ n 3 . If n 1 = n 2 = 0, then n 3 = 1 and P(n, ω) is 2-connected if and only if ω ≥ 1.
Assume now n 2 = 0 and let 0 < ω < n 3 . Then P(n, ω) has voxels belonging to different level lines (i.e. voxels v and w such that v 3 = w 3 ). Let v ∈ P(n, ω). Then, 0 ≤ p n (v) and w < n 3 ≤ p n (v + e 3 ) = p n (v) + n 3 . Hence, v + e 3 / ∈ P(n, ω). In other words, two voxels of P(n, ω) belonging to different level line are not linked by a 2-path included in P(n, ω). Hence P(n, ω) is not 2-connected. This bound is not very accurate but useful to prove that the arithmetic thicknesses of the arithmetic discrete planes, with a given normal vector, form an interval.

Lemma 2. Let n ∈ R 3 . The set {ω ∈ R; P(n, ω) is 2-connected} is an interval. Proof Without loss of generality, let us suppose that 0 ≤ n 1 ≤ n 2 ≤ n 3 . Let ω ∈ R such that P(n, ω) is 2-connected. According to Lemma 1, ω ≥ n 3 . Let α ∈ R + and let v ∈ Z 3 such that β = p n (v) ∈ [ω, ω + α[. Let (q, r) ∈ N × R + satisfying β -ω = qn 3 +
Ω 2 (n) = inf {ω ∈ R; P(n, ω) is 2-connected} .
Let us remind that, if n is a rational vector then the thickness ω is considered to be an integer. In that case, Ω 2 (n) becomes:

Ω 2 (n) = min {ω ∈ Z; P(n, ω) is 2-connected} .
In this particular case, one remarks that P(n, Ω 2 (n)) is 2-connected. As far as we know, it has not been proved it holds in the general case.

Arithmetic reductions preserving 2-connected components

In the present section, we show that the determination of Ω 2 (n) reduces to the one of Ω 2 (m), with m ∞ < n ∞ , by an elementary reduction on the components of n.

Theorem 3. Let n ∈ R 3 + such that 0 ≤ n 1 ≤ n 2 ≤ n 3 and let m ∈ R 3 such that m = (n 1 , n 2 + n 1 , n 3 + n 1 )
. For all ω ∈ R, the arithmetic discrete plane P(n, ω) is 2-connected if and only if so is P(m, ω + n 1 ).

Proof Let us consider the map Ψ 2 : R 3 -→ R 3 defined by:

Ψ 2 : R 3 -→ R 3   x 1 x 2 x 3   -→   x 1 -x 2 -x 3 x 2 x 3  
One checks that Ψ 2 provides a bijection from P(n, ω) to P(m, ω).

1. Let us assume P(n, ω) to be 2-connected and let us show that P(m, ω + n 1 ) is 2-connected too. One first notes that, given an element v ∈ P(m, ω

+ n 1 ), if p m (v) ∈ [ω, ω + a[, then v -e 1 ∈ P(m, ω + a) and p m (v -e 1 ) ∈ [0, ω[.
In other words, an element of P(m, ω + n 1 ) is either an element of P(m, ω) or 2-adjacent to an element of P(m, ω). Thanks to this remark, it remains to show that each pair of points of P(m, ω) is 2-linked in P(m, ω + n 1 ). Since Ψ 2 : P(n, ω) -→ P(m, ω) is a bijection, it remains to show that the images of two 2-adjacent elements of P(n, ω) are 2-linked in P(m, ω + n 1 ).

For short, we give a geometric interpretation of the action of the map Ψ 2 on two 2-adjacent voxels of P(n, ω) (see Figure 2) : the right grey voxels are the images of the left grey ones, while the right white voxels are elements of P(m, ω + n 1 ) which allow us to 2-link the grey voxels. For ensuring the existence of such white voxels, we remind that the right grey ones belongs to P(m, ω) and, for any such voxels v, the (white) voxel v + e 1 belongs to P(m, ω + n 1 ). 2. Conversely, let us suppose P(m, ω + n 1 ) to be 2-connected. Then, ω + n 1 ≥ n ∞ (see Lemma 1). Hence, for all v ∈ P(m, ω

+ n 1 ) such that p m (v) ∈ [ω, ω + n 1 [, p m (v -e 1 ) = p m (v) -n 1 ∈ [0, ω[ and v -e 1 ∈ P(m, ω).
Let Ψ 2 : P(m, ω + n 1 ) -→ P(n, ω) be the surjective map defined by:

Ψ 2 : P(m, ω + n 1 ) -→ P(n, ω) v -→ Ψ -1 2 (v), if p m (v) ∈ [0, ω[, Ψ -1 2 (v -e 1 ), otherwise.
Since Ψ 2 is surjective, then it remains to show that the image of two 2adjacent voxels in P(m, ω + n 1 ) are either equal or 2-linked in P(n, ω).

i. Let v and w in P(m, ω + n 1 ) such that vw = e 1 . Two cases occur:

• If p m (v) ∈ [0, ω[, i.e. v ∈ P(m, ω), then Ψ 2 (v) -Ψ 2 (w) = e 1 .
Hence, Ψ 2 (v) and Ψ 2 (w) are 2-adjacent.

• If p m (v) ∈ [ω, ω + n 1 [, then Ψ 2 (v) = Ψ 2 (v -e 1 ) = Ψ 2 (w) = e 1 .
ii. Let v and w in P(m, ω + n 1 ) such that vw = e 2 .

•

If p m (v) ∈ [0, ω[, then p m (v) = p m (w) + n 1 + n 2 and, v + e 1 ∈ P(m, ω + n 1 ) and p m (w + e 1 ) ∈ [0, ω[ (since n 1 ≤ n 2 )
. One finally checks that ( Ψ 2 (w), Ψ 2 (w + e 1 ), Ψ 2 (v)) forms a 2-path in P(n, ω).

• If p m (v) ∈ [ω, ω + n 1 [, then Ψ 2 (v) -Ψ 2 (w) = Ψ -1 2 (e 2 -e 1 ) = e 2 . iii. Let v and w in P(m, ω + n 1 ) such that v -w = e 3 . • If p m (v) ∈ [0, ω[, then p m (v) = p m (w) + n 1 + n 3 and, v + e 1 ∈
P(m, ω + n 1 ) and p m (w + e 1 ) ∈ [0, ω[ (since n 1 ≤ n 3 ). One then checks that ( Ψ 2 (w), Ψ 2 (w + e 1 ), Ψ 2 (v)) form a 2-path in P(n, ω).

• If p m (v) ∈ [ω, ω + n 1 [, then Ψ 2 (v) -Ψ 2 (w) = Ψ -1
2 (e 3e 1 ) = e 3 .

To sum up, let us give a geometrical interpretation of the last three cases (see Figure 3). By induction, a direct consequence of Theorem 3 is:

Corollary 2. Let n ∈ R 3 + such that 0 ≤ n 1 ≤ n 2 ≤ n 3 , let q = ⌊n 2 /n 1 ⌋ and let m ∈ R 3 such that m = (n 1 , n 2 -qn 1 , n 3 -qn 1 )
. For all ω ∈ R, the arithmetic discrete plane P(n, ω) is 2-connected if and only if so is P(m, ω + qn 1 ). plane P(n, ω). It rather requires to update this value at each iteration. Nevertheless Algorithm 2 is very similar to Algorithm 1. Indeed, we just have to initialize the process with the value of ω and, at each step, to decrease it according to Corollary 2. Then, P(n, ω) is 2-connected only if, at the end of the process, the value of ω remains greater than or equal to 0.

Algorithm 2 Is a given arithmetic discrete plane 2-connected ?

Input : ω ∈ N * n ∈ N 3 such that 0 ≤ n 1 ≤ n 2 ≤ n 3 and gcd{n 1 , n 2 , n 3 } = 1 Output :
Decision on the 2-connectedness of P(n, ω)

while (n 1 = 0 and ω > 0) do n = n 2 - n 2 n 1 n 1 , min n 1 , n 3 - n 2 n 1 n 1 , max n 1 , n 3 - n 2 n 1 n 1 ; ω ← ω - n 2 n 1 n 1 ;
end while return (ω > 0);

Comparison of Algorithm 2 with Y. Gérard's algorithm [START_REF] Gérard | Periodic graphs and connectivity of the rational digital hyperplanes[END_REF] is difficult since we do not know neither time complexity nor space complexity for this last one. In the one hand, it obviously requires space for storing the adjaceny graph and it uses set operations which are generally more time-consuming than simple arithmetic operations. In the other hand, it can apply whatever the dimension or the connectedness. Our algorithm just solve the case of 2-connected arithmetic discrete planes. In the sequel of the present paper, we extend it to the other connectedness of the 3-dimensional discrete space, but higher dimensions stay yet out of our scope.

1-connected arithmetic discrete planes

In the present section, we show how to reduce the problem of deciding the 1connectedness of an arithmetic discrete plane to the 2-connectedness of another one.

Notation.

-From now on, we denote by Ψ 1 : R 3 -→ R 3 the following linear bijection:

Ψ 1 : R 3 -→ R 3   x 1 x 2 x 3   -→   x 1 x 2 -x 1 x 3 -x 2  
The following theorem shows how the map Ψ 1 is useful for the determination of the 1-connectedness of a given arithmetic discrete plane.

Theorem 5. Let n ∈ R 3 such that 0 ≤ n 1 ≤ n 2 ≤ n 3 and let ω ∈ R. The arithmetic discrete plane P(n, ω) is 1-connected if and only if the arithmetic discrete plane P(Ψ 1 (n), ω) is 2-connected.
Before proving this result and for the sake of clarity, let us introduce a terminology:

Terminology.

-Let E be a discrete set, let v and v ′ be two elements of E and let κ ∈ {0, 1, 2}. We say that v and v ′ are κ-linked in E if they share the same κ-connected component in E.

Proof For short, let us state P = P(n, ω) and

P ′ = P(Ψ 1 (n), ω). Let Ψ 1 = t Ψ 1 -1 : Ψ 1 : R 3 -→ R 3   x 1 x 2 x 3   -→   x 1 + x 2 + x 3 x 2 + x 3 x 3  
One easily checks that Ψ 1 : R 3 -→ R 3 provides a bijection from P to P ′ and, for all v ∈ P,

p n (v) = p Ψ1(n) ( Ψ 1 (v)).
It remains to show that two voxels v and w in P are 1-linked in P if and only if Ψ 1 (v) and Ψ 1 (w) are 2-linked in P ′ . Equivalently, it is sufficient to prove the following assertions:

1. Let v ∈ P and w ∈ P. If v and w are 1-adjacent in P, then Ψ 1 (v) and Ψ 1 (w) are 2-linked in P ′ .

2. Let v ′ ∈ P ′ and w ′ ∈ P ′ . If v ′ and w ′ are 2-adjacent in P ′ , then Ψ -1 1 (v ′ ) and Ψ -1 1 (w ′ ) are 1-linked in P.

1. Let v and w be two 1-adjacent voxels of P.

i If vw = e 1 , then Ψ 1 (v) -Ψ 1 (w) = e 1 . Hence Ψ 1 (v) and Ψ 1 (w) are 2-linked in P ′ .

ii If vw = e 2 , then Ψ 1 (v) -Ψ 1 (w) = e 1 + e 2 . Moreover, one checks that Ψ 1 (v) + e 1 ∈ P ′ and we have shown that Ψ 1 (v) and Ψ 1 (w) are 2-linked in P ′ . Geometrically, the action of Ψ 1 can be represented as in Figure 4 : the grey voxels correspond to the images of the extremities of the original 1-path, the white ones belong to P ′ and allow us to construct a 2-path in P ′ .

The other cases, that is, vw ∈ {e 3 , e 1 ± e 2 , e 2 ± e 3 , e 1 ± e 3 } are handled by the same method. Moreover, the cases vw ∈ {e 1 + e 2 , e 2 + e 3 , e 1 + e 3 } can be splited into the elementary cases vw ∈ {e 1 , e 2 , e 3 }.

Conversely, one checks that for all

v ∈ Z 3 satisfying v 1 ≤ 1, then Ψ -1 1 (v) ∞ ≤ 1 and Ψ -1 1 (v) ∞ ≤ 2.
It follows that the image under Ψ -1 1 of two 2-adjacent voxels of P ′ are 1-adjacent.

Ψ 1 Ψ 1 Ψ 1 Ψ 1 Ψ 1 Ψ 1 Ψ 1 Ψ 1 Figure 4:
The action of Ψ 1 on two 2-adjacent voxels of P.

From Theorem 5 and Lemma 2, it directly follows that, given n ∈ R 3 , the set {ω ∈ R; P(n, ω) is 1-connected} is an interval. Its determination is equivalent to the one of its lower bound, also called the minimal 1-connecting thickness of n: Definition 9 (Minimal 1-connecting thickness). Let n ∈ R 3 . The minimal 1-connecting thickness of n is the number Ω 1 (n) defined by:

Ω 1 (n) = inf {ω ∈ R; P(n, ω) is 1-connected} .
A direct consequence of Theorem 5 is:

Corollary 4. Let n ∈ R 3 such that 0 ≤ n 1 ≤ n 2 ≤ n 3 and let Ψ 1 be as defined in Notation above. Then Ω 1 (n) = Ω 2 (Ψ 1 (n)).
Thanks to Algorithm 1 and Corollary 4, one easily determines the minimal 1-connecting thickness of a given rational vector. In the same way, one easily decides whether a given arithmetic discrete plane is 1-connected.

0-connected arithmetic discrete planes

The last case, which has been the most studied in the literature [START_REF] Andres | Discrete analytical hyperplanes[END_REF][START_REF] Gérard | Periodic graphs and connectivity of the rational digital hyperplanes[END_REF][START_REF] Brimkov | Connectivity of discrete planes[END_REF], concerns the 0-connectedness of the arithmetic discrete plane. This part is almost similar to the previous one. Let us first recall a technical lemma, called Symmetry lemma in [START_REF] Brimkov | Connectivity of discrete planes[END_REF]:

Lemma 5 (Symmetry lemma [5]). Let n ∈ R 3 + such that 0 ≤ n 1 , n 2 ≤ n 3 and let n ′ = (n 3 -n 1 )e 1 + n 2 e 2 + n 3 e 3 . Let ω ∈ R. The arithmetic discrete plane P(n, ω) is 0-connected if and only so is P(n ′ , ω).
The main interest of Lemma 5 is that it allows us to assume 0 ≤ 2n 1 ≤ n 3 . Moreover, since the role of n 1 and n 2 are symmetric in Lemma 5, one can also suppose 0 ≤ 2n 2 ≤ n 3 . In particular, one can suppose that 0

≤ n 1 ≤ n 2 ≤ n 1 + n 2 ≤ n 3 .
Let us now introduce a notation before stating the main result of the present section.

Notation. -From now on, we denote by Ψ 0 : R 3 -→ R 3 the following linear bijection:

Ψ 0 : R 3 -→ R 3   x 1 x 2 x 3   -→   x 1 x 2 -x 1 x 3 -x 2 -x 1  
The main result of this section is then:

Theorem 6. Let n ∈ R 3 such that 0 ≤ n 1 ≤ n 2 ≤ n 1 + n 2 ≤ n 3 and let ω ∈ R. The arithmetic discrete plane P(n, ω) is 0-connected if and only if the arithmetic discrete plane P(Ψ 0 (n), ω) is 2-connected.
Proof The proof is almost the same as the one of Theorem 5. Here we consider the action of the map Ψ 0 = t Ψ 0 -1 from P(n, ω) to P(Ψ 0 (n), ω).

From Theorem 6 and Lemma 2, it directly follows that, given n ∈ R 3 , the set {ω ∈ R; P(n, w) is 0-connected} is an interval. Its computation is equivalent to the one of its lower bound, also called the minimal 0-connecting thickness of n:

Definition 10 (minimal 0-connecting thickness). Let n ∈ R 3 . The minimal 0-connecting thickness of n is the number Ω 0 (n) defined by:

Ω 0 (n) = inf {ω ∈ R; P(n, ω) is 0-connected} .
A direct consequence of Theorem 6 is:

Corollary 5. Let n ∈ R 3 such that 0 ≤ n 1 ≤ n 2 ≤ n 1 + n 2 ≤ n 3 and let Ψ 0 be as defined in Notation above. One has Ω 0 (n) = Ω 2 (Ψ 0 (n)).
Thanks to Algorithm 1, one easily determines the minimal 0-connecting thickness of a given rational vector. Just remind that, with no loss of generality, up to exchange n 1 and n 3 -n 1 (resp. n 2 and n 3 -n 2 ), one can suppose that 0 ≤ n 1 ≤ n 2 ≤ n 1 + n 2 ≤ n 3 and apply Lemma 5 and Theorem 6 to determine Ω 0 (n) in every case. In the same way, one can decide whether a given arithmetic discrete plane is 0-connected.

Additional remarks on the minimal 0-connected thickness

The determination of Ω 0 (n) has already been deeply investigated in [START_REF] Brimkov | Connectivity of discrete planes[END_REF] as already mentioned. V. Brimkov and R. Barneva focused on rational arithmetic discrete planes and found explicit formulas in some particular cases:

Theorem 7 (Explicit formulas [START_REF] Brimkov | Connectivity of discrete planes[END_REF]). Let n ∈ Z 3 satisfying 0 ≤ n 1 ≤ n 2 ≤ n 3 . One has:

• if n 3 < n 1 + n 2 /2, Ω 0 (n) = n 1 + n 2 -n 3 + gcd(n 3 -n 2 , n 3 -n 1 ) -1,

• if n 1 + n 2 < n 3 < 2n 2 -n 1 , Ω 0 (n)) = n 2 -n 1 + gcd(n 1 , n 3 -n 2 ) -1, • if n 3 ≥ 2n 2 + n 1 , Ω O (n) = n 3 -(n 1 + n 2 ) + gcd(n 1 , n 2 ) -1.

Conclusion

In the present paper, we have shown how to compute the minimal 2-connecting thickness of a vector n. The reduction exhibited in Theorem 3 works whatever the type (rational or irrational) of the considered vector. Nevertheless, we have restricted our investigation to rational vectors and provided an algorithm which computes their minimal 2-connecting thickness. This algorithm can be easily adapted to decide whether a given rational arithmetic discrete plane is 0-connected or not. Then, we have shown how to reduce the problem of determining the minimal 1-connecting and 0-connecting thicknesses of a vector n to the determination of the minimal 2-connecting thickness of an appropriate vector (see Theorem 5 and Theorem 6).

In forthcoming work, we plan to deeply investigate the case of non-rational arithmetic discrete planes. Since reductions of Theorem 3, Theorem 5 and Theorem 6 do not depend on the nature of the input vector (integer or not), we hope to extend our approach to any vector n ∈ R 3 . Currently, some particular points still need to be investigated. In particular, given n ∈ R 3 and κ ∈ {0, 1, 2}, we do not know whether P(n, Ω κ (n)) is κ-connected. In other words, is Ω κ (n) the smallest element of the set {ω ∈ R; P(n, ω) is κ-connected} ? or just a lower bound? Besides, does the translation parameter change the κ-connectedness of an arithmetic discrete plane if its normal vector is not rational?

Another interesting investigation will be the extension of this work to arithmetic discrete hyperplane in any dimension.

Figure 1 :

 1 Figure 1: Connected arithmetic discrete planes (with normal vector n = (9, 14, 31)) thinner than the naive one.

  r and 0 ≤ r < n 3 . For all k ∈ {0, . . . , q}, p n (v -ke 3 ) = β -kn 3 ∈ [ω, ω +α[ and p n (v -(q +1)e 3 ) ∈ [0, ω[. Hence, we have built a 2-path (v -ke 3 ) k∈{0,...,q+1} in P(n, ω + α) linking v to the voxel v -(q + 1)e 3 ∈ P(n, ω) which is 2-connected by assumption.Lemma 2 reduces the determination of {ω ∈ R; P(n, ω) is 2-connected } to the determination of its lower bound. Let us now define the minimal 2connecting thickness of a vector.Definition 8 (Minimal 2-connecting thickness). Let n ∈ R 3 . The minimal 2-connecting thickness of n is the number Ω 2 (n) defined by:

e 3 e 1 e 2 Ψ 2 Ψ 2 Ψ 2 Figure 2 :

 122222 Figure 2: The action of Ψ 2 on two 2-adjacent voxels of P(n, ω).

Figure 3 :

 3 Figure 3: The action of Ψ 2 on two 2-adjacent voxels of P(m, ω + n 1 ).

Acknowledgements

We would like to thank É. Andres for having pointed out the original problem to the authors. We also thank P. Arnoux, V. Berthe, V. Brimkov, É. Domenjoud, C. Fiorio, Y. Gérard and D. Vergnaud for many interesting discussions on the subject.

The second important consequence of Theorem 3 links the minimal 2connected thickness of n with the one of m (as defined in Corollary 2). Corollary 3. Let n ∈ R 3 + such that 0 < n 1 ≤ n 2 ≤ n 3 and q = ⌊n 2 /n 1 ⌋. Then, we have:

Ω 2 (n 1 , n 2 , n 3 ) = Ω 2 (n 1 , n 2 -qn 1 , n 3 -qn 1 ) + qn 1 .

In this reduction, n 1 , n 2 and n 3 are assumed to be all non-zero. If

and one checks that P(n, ω) is 2-connected if and only if so is the set v ∈ Z 3 ; x 1 = 0 and 0 ≤ p n (v) < ω . From Theorem 1, it follows:

Composing both reductions (see Theorem 3 and Theorem 4) directly provides two algorithms: one that determines the minimal 2-connected thickness Ω(n) of a vector n ∈ N 3 , one that returns whether an arithmetic discrete plane is 2-connected.

Applications

In the present section we provide an algorithm computing the 2-minimal thickness of a given integer vector n. A first naive approach consists in "translating" Corollary 3, such as it is, in terms of an algorithm, in order to reduce n and increase ω while n does not satisfy conditions of Theorem 4. In fact, thanks to the following technical lemma, we can obtain a shorter and nicer way to compute Ω 2 (n).

Notation. -Let φ 2 : Z ⋆ × Z 2 -→ Z 3 be the map defined by:

Proof The first assertions, that is, 0

The last assertions follows from that

Given n ∈ ∆ and n ′ = φ 2 (n), one has n ′ 1 < n 1 . Hence, there exists k ∈ N such that n

In that case, it follows from Theorem 4 that Ω 2 (n ′ ) = n ′ 2 + n ′ 3 and:

Proof By Lemma 3,

n ′ 1 and the result follows.

In fact, Lemma 3 and Lemma 4 prove the correction of the following algorithm calculating Ω 2 (n) for any n ∈ ∆.

Algorithm 1 Compute the minimal 2-connecting thickness

This algorithm has obviously a constant space complexity, but also a reasonable time complexity.

Proof We refer to the vector n at iteration i by n (i) . By definition of q, for all i, n

1 . Thus, by induction, for all i, n

1 being an integer, this stopping criteria can be rewritten as n The global computation of the thickness ω used in Algorithm 1 is not appropriate for the decision on the 2-connectedness of a given arithmetic discrete


N Arnaud

CHARMLESS HADRONIC B-DECAYS AT BABAR AND Belle

We report recent results for charmless hadronic B decays from the B-factories. Three BABAR analyses are presented: B → φφK; B + → ρ 0 K * + and B + → f0(980)K * + ; inclusive B → XK + , XK 0 and Xπ + beyond the charm threshold. Two Belle results are described: search for the X(214) through charmless rare B decays; first measurement of inclusive B → Xsη.

Introduction

Charmless hadronic B decays are rare processes which branching fractions (BFs) are mostly in the 10 -6 -10 -5 range. Yet, about 100 decay modes have been measured 1 with a significance ≥ 4σ, mostly by the B-factories. Indeed these modes allow one to probe the Standard Model of particle physics (SM). The processes are dominated by b → u trees and b → s, d gluonic penguins. As the trees are suppressed by the Cabibbo-Kobayashi-Maskawa mechanism 2 , the penguins amplitudes are often significant or even dominant. Such loops are ideal places to look for New Physics (NP) as yet-unknown heavy particles could contribute to these decays and yield amplitudes that are significantly different from the SM ones. Moreover, interferences between amplitudes accommodate searches for CP violation and allow relative phase measurements through Dalitz Plot (DP) analysis. Finally, studying such decays helps testing predictions from factorization, perturbative QCD, SU(3) flavour symmetry, etc.

These proceedings review recent results 3,4,5,6,7 from the BABAR 8 and Belle 9 experiments which took data during the past decade at the high luminosityB-factories PEP-II 10 and KEK-B [START_REF] Kurokawa | [END_REF] . Unless otherwise noted, the first uncertainty quoted for a result is statistical and the second systematic. Charge-conjugate states are assumed throughout this document.

Analysis techniques

When studying charmless hadronic B decays, the signal is usually small relatively to a large background coming from the production of light quark pairs (e + e -→ qq with q = u, d, s, c: the 'continuum') and other B decays. Correctly reconstructed B decays are selected using two kinematical variables computed in the center-of-mass (CM) frame: the energy-substituted mass

m ES = E CM beam 2 -p CM B 2
(Belle: M bc ) which peaks at the B mass, and the energy difference ∆E = E B -√ s/2 that peaks at 0 ( √ s is the total CM energy). Multivariate analyses combining event-shape variables computed in the CM frame are used to separate B decays ('spherical' as the BB pairs are almost produced at rest) from continuum events ('jet-like' as more kinetic energy is available for these decays). Several exclusive or inclusive B background decays are studied and then grouped in classes with similar kinematics and topological properties. These event categories are used in an unbinned extended likelihood fit which combines several discriminating variables and is usually conducted to compute the contributions of the different event categories included in the analysis. The 'B reco ' technique is another way to fight against background. In this case, one of the two B mesons produced in the event is fully reconstructed through exclusive hadronic (B → D ( * ) Y ± where Y ± is a combination of hadrons) or semi-leptonic (B → D ( * ) lν l ) decays. For each of these channels, Monte-Carlo simulations allow one to compute their purity and efficiency. Depending on the analysis needs, samples favouring either of these criteria can be selected by choosing a subset of the numerous 'B reco ' modes reconstructed in data.

3 Results The final state φφK occurs through either a one-loop 'penguin' b → sss transition or the b → ccs tree-level decay B → η c K with η c → φφ. Therefore, these two amplitudes can interfere if the φφ invariant mass m φφ is close to the η c resonance. In the SM, no CP violation is expected from this effect as the relative weak phase difference between the two amplitudes is approximately 0. Conversely, measuring a significant direct CP asymmetry in this channel 12 would clearly trigger NP contributions to the penguin loop. This analysis uses 464 × 10 6 BB events. The branching fractions measured in the invariant mass range below the η c resonance (m φφ < 2.85 GeV) are B(B + → φφK + ) = (5.6 ± 0.5 ± 0.3) × 10 -6 and B(B 0 → φφK 0 ) = (4.5 ± 0.8 ± 0.3) × 10 -6 -the neutral mode had not been previously observed with a significance greater than 5σ. They are consistent with the previous BABAR measurement 13 (now superseded) and larger than (although statistically compatible with) the Belle results 14 . They are also higher than the theoretical predictions 15 . The direct CP asymmetries for the B ± modes are A CP = -0.10 ± 0.08 ± 0.02 below the η c threshold (m φφ < 2.85 GeV/c 2 ) and A CP =0.09 ± 0.10 ± 0.02 in the η c resonance region (2.94 ≤ m φφ ≤ 3.02 GeV/c 2 ). These are consistent with zero, in agreement with the SM. Finally, angular distributions of the B + → φφK + decays have been studied. They are consistent with J P =0 -in the η c resonance region and favor J P =0 + below.

3.1 B → φφK (BABAR ) (GeV) 1 φ m 1 1.05 1.1 1. 15 1.2 (GeV

B

+ → ρ 0 K * + and B + → f 0 (980)K * + (BABAR )
Several B decays to vector-vector (VV) modes like B + → ρ 0 K * + (not observed prior to this analysis) have been studied. For most of them, there is a discrepancy regarding the longitudinal polarization f L between the predictions from QCD factorization models (f L ∼ 1) and the mea-surements (f L ∼ 0.5). Several attempts to understand this 'polarization puzzle' 16 have been made, either within or beyond the SM. This analysis uses a sample of (467 ± 5) × 10 6 BB pairs and supersedes the previous BABAR results. It reports measurements of the branching fraction B(B + → ρ 0 K * + ) = (4.6±1.0±0.4)× 10 -6 (first observation with a 5.3σ significance, compatible with theoretical predictions), longitudinal polarization f L =0.78 ± 0.12 ± 0.03 (both consistent with the theoretical predictions and with the measured values for the two other K * ρ modes) and direct CP-violation asymmetry A CP =0.31 ± 0.13 ± 0.03 for the decay B + → ρ 0 K * + such as measurement of the branching fraction B(B + → f 0 (980)K * + ) = (4.2 ± 0.6 ± 0.3) × 10 -6 and direct CP-violation asymmetry A CP = -0.15 ± 0.12 ± 0.03 for the mode B + → f 0 (980)K * + which shares the same final states (assuming a branching fraction of 100% for f 0 (980) → π + π -).

3.3

Inclusive B → XK + , XK 0 and Xπ + beyond the charm threshold (BABAR ) For these decays, theoretical models 18 predict enhancements up to one order of magnitude of the branching fractions with respect to the SM if NP enters in the loop diagrams. This analysis uses 383 × 10 6 BB pairs out of which 2 × 10 6 events are reconstructed using the hadronic B reco selection technique. Partial branching fractions above the end point for decays to charmed mesons -the momentum p * of the candidate hadron greater than 2.34 (2.36) GeV/c for kaons (pions) in the B sig rest frame -are reported: B(B → XK + ,p * > 2.34 GeV/c) = (1.2 ± 0.3 ± 0.4) × 10 -4 < 1.9 × 10 -4 at 90% C.L.; B(B → XK 0 ,p * > 2.34 GeV/c) = (1.9 ± 0.5 ± 0.5) × 10 -4 < 2.9 × 10 -4 at 90% C.L.; B(B → Xπ + ,p * > 2.34 GeV/c) = (3.7 ± 0.5 ± 0.6) × 10 -4 , a decay observed inclusively independently of known exclusive modes. These results are in agreement with the SM and exclude large enhancement due to NP. In addition, no direct CPasymmetry is observed in the charged modes: A CP (B → XK + )=0 .57 ± 0.24 ± 0.05 and A CP (B → Xπ + ) = 0.10 ± 0.16 ± 0.05.

Search for the X(214) through charmless rare B decays (Belle)

The goal of this analysis is to search for a light scalar or vector particle decaying into a pair of muons. Such X particle could help understanding recent astrophysical observations 19 . Moreover, the HyperCP collaboration has reported the observation of 3 events Σ + → pX(→ µ + µ -) with a mass of 214.3 MeV/c 2 and a lifetime around 10 -14 s. Two rare decay modes (B 0 → K * 0 X and B 0 → ρ 0 X are searched in a dataset of 657 × 10 6 BB events; branching fractions in the range 10 -9 -10 -6 are expected 20 for a sgoldstino of mass 214 MeV/c 2 . Two techniques have been used to evaluate the background yield in the signal box defined using the variables M bc and ∆E. The first one consists in counting the number of selected events using MC samples about 3 times larger than the dataset; in the second approach, the number of events is fitted using parameterizations based on sidebands. As a cross-check, various MC distributions are compared to those computed using a small fraction of the data. Finally, no signal is observed and frequentist upper limits are derived: B(B 0 → K * 0 X) < 2.26 (2.27) × 10 -8 and B(B 0 → ρ 0 X) < 1.73 (1.73) × 10 -8 for a scalar (vector) X particle decaying into two muons with a lifetime smaller than 10 -12 s. This rules out some models for a sgoldstino interpretation of the HyperCP observation.

First measurement of inclusive

B → X s η (Belle)
This study is motivated by the results of inclusive B → X s η analysis which show an unexpectedly large branching fraction and a spectrum which peaks at high mass 21 . It uses as well 657×10 6 BB events and is based on a pseudo-inclusive method: the X s is reconstructed in 18 exclusive channels containing a K + or a K 0 s (→ π + π -) and up to 4 pions of which at most 1 is a π 0 (→ γγ). For m Xs < 2.6 GeV/c 2 , the B → X s η measured branching fraction is [26.1±3.0 +1.9 -2.1 +4.0 -7.1 ]×10 -5 , where the last error comes from the modeling of the X s system with PYTHIA. This result is consistent with the known decays B → Kη and B → K * (892)η. Over half of the events (7σ significance) are located in the high-mass region (m Xs > 1.8 GeV/c 2 ), which was not covered by previous exclusive measurements. Using the 13 modes for which the B flavor is given by the final state, the direct CP-asymmetry can be computed: A CP = -0.13 ± 0.04 +0.02 -0.03 which is consistent with predictions. The m Xs spectrum shapes and branching fractions are comparable for the η and the η , which rules out the hypothesis of specific η mechanisms.

Figure 1 :

 1 Figure 1: Left plot: signal-enhanced distribution of the selected data in the m φ2 vs. m φ1 plane. 5 zones have been defined in this plane (see inset) to measure the signal yield and the contributions of the 4 peaking B background categories. Right plot: fitted B → φφK + yield as a function of the φφ invariant mass. The ηc resonance is clearly visible whereas there is no sign of the χc resonances in the two narrow bins around 3.5 GeV/c 2 .

Figure 2 :

 2 Figure 2: Left: M bc distribution for the full mass range; the points are the data, the solid red line the overall fit function, the magenta dashed line the signal, the green dotted line the b → c background and the blue dash-dotted the continuum. Right: differential branching fraction as a function of mX s .

Acknowledgments

I'd like to thank E. Ben-Haim and A. Gaz for their comments on my talk and the proceedings.


N Makovec

W and Z physics with the ATLAS detector

We present measurements involving W and Z boson production in pp collisions at √ s=7 TeV with an integrated luminosity of ∼35 pb -1 recorded by the ATLAS detector at the Large Hadron Collider. Several analysis are presented: Drell-Yan W → ℓν and Z/γ * → ℓℓ (ℓ = e, µ) production cross sections, muon charge asymmetry from W boson decays, production of jets in association with a Z/γ * boson in the final state and diboson production (W γ,Zγ,W + W -). The measurements are compared to perturbative QCD predictions with various parton distribution functions.

Introduction

The leptonic decays of W and Z bosons provide a very clean experimental signature with which to measure their production cross sections and test the predictions from perturbative Quantum ChromoDynamics (pQCD) at the Large Hadron Collider (LHC) and the accuracy of Parton Distribution Functions (PDF) which parameterize the parton's momentum distribution in the proton. Measurements of such processes, in particular in association with jets, are also important to control backgrounds to other Standard Model measurements like the top cross-section measurement 1 or to searches for physics beyond the Standard Model like the search for squark and gluino production 2 . Here we report measurements involving W and Z boson production in pp collisions at √ s=7 TeV with an integrated luminosity of ∼35 pb -1 .

2 Measurement of the total W ± and Z/γ * cross sections and muon charge asymmetry

The total W and Z cross section is measured using the following formula:

σ tot = σ W/Z × BR(W/Z → ℓν/ℓℓ) = N -B A W/Z .C W/Z .L int . ( 1
)
Here N is the number of candidate events measured in data, B the number of background events, determined using data and simulation and L int the integrated luminosity corresponding to the run selections and trigger employed. BR(W/Z → ℓν/ℓℓ) stands for branching ratio. The correction by the efficiency factor C W/Z , measured partly with data, determines the integrated cross sections σ f id within the fiducial regions of the measurement, while the acceptance factor A W/Z , estimated from Monte-Carlo, is introduced to extrapolate the measurement of σ f id to the full kinematic region which determines the total cross section, σ tot . The details of the analysis can be found in Reference 3 . As shown in Figure 1, the measured W ± and Z/γ * cross sections are found to be described by Next-to-Next-to-Leading Order (NNLO) QCD calculations based on a number of different PDF sets.

In pp collisions the overall production rate of W + bosons is significantly larger than the corresponding W -rate, since the proton contains two u and one d valence quarks. The measurement of the lepton charge asymmetry:

A l = dσ Wl + /dη l -dσ Wl -/dη l dσ Wl + /dη l + dσ Wl -/dη l , (2)
can contribute significantly to the understanding of PDFs in the parton momentum fraction range 10 -3 < x < 10 -1 . Systematic effects on the W-production cross-section measurements are typically the same for positive and negative muons, mostly canceling in the asymmetry. Measurements in the muon channel are presented in Figure 1 together with predictions obtained with MC@NLO 4 and different PDF sets. More details can be found in Reference 5 . The data are roughly compatible with all the predictions with different PDF sets, though some are slightly preferred to others. The data presented here are expected to contribute to the determination of the next generation of PDF sets, helping to reduce their uncertainties, particularly the shapes of the valence quark distributions in the low-x region.

3 Measurement of the production cross section for Z/γ * in association with jets Production of jets of particles in association with a Z/γ * boson in the final state was measured. Jets are defined using the anti-k T algorithm with R = 0.4 and the measurements are performed for jets in the region p jet T > 30 GeV and |η jet | < 2.8. The full analysis is described in Reference 6 and the measured cross section as a function of the inclusive jet multiplicity for the electron channel and as a function of p jet T for the muon channel are presented in Figure 2. The measured cross sections are well described by Next-to-Leading Order (NLO) pQCD predictions obtained by MCFM 7 and including non-perturbative corrections, as well as by the predictions from LO matrix elements supplemented by parton showers, as implemented in the ALPGEN 8 and SHERPA 9 MC generators but not by PYTHIA 10 which underestimates the measured cross sections. 4 Measurement of diboson production (W γ,Zγ,W + W -)

ATLAS has also performed the measurement of diboson production of high energy photons in association with either a W or Z boson. Such measurements allow to test pQCD. Moreover, the W γ process includes a diagram sensitive to Triple Gauge boson Coupling (TGC) of the electroweak sector. Events with W and Z bosons decaying into high-p T electrons and muons are required in addition to have a photon with E T > 15 GeV located outside a cone of radius 0.7 in η φ space centered on the lepton(s) from the boson decay. To further reduce the background due to photons from π 0 and η decays, an isolation requirement of E iso T < 5 GeV is applied. E iso T is the total transverse energy recorded in the calorimeter in a cone of radius 0.4 around the photon direction (excluding a small window which contains the photon energy). E iso T is corrected for the leakage of the photon energy into the isolation cone and the contributions from the underlying and pile-up activities in the event. A total of 95 (97) pp → eνγ + X (pp → µνγ + X) and 25 (23) pp → e + e -γ + X (pp → µ + µ -γ + X) event candidates are selected 11 . The measured production cross sections, together with the kinematic distributions of the leptons and photons in data signal candidate events, are found to agree with the O(αα s ) Standard Model predictions (see Table 1

GeV , ∆R(l, γ) > 0.5 and ǫ p h < 0.5 where ǫ p h is defined at particle level as the ratio between sum of the energies carried by final state particles in the cone ∆R < 0.4 around the photon and the energy carried by the photon.

The WW production cross section in pp collisions was also measured using three leptonic decay channels: electron-electron, muon-muon and muon-electron channels. Such processes are also sensitive to TGC as predicted by the Standard Model. The decay products from both toppair (t t → W bW b) and single top (tW → W bW ) processes contain also WW in the final states. The top events are characterized by hadronic jet activity in the final state. Using a jet-veto cut the majority of the top background can be removed from the WW event selection. A total of eight candidates are selected with an estimated background of 1.7 ± 0.6 events. The probability for the estimated background to fluctuate up to at least the observed eight events is 1.4×10 -3 , corresponding to a signal significance of 3.0 standard deviations. The measured cross section is 40 +20

-16 (stat)±7(syst) pb, consistent with the SM NLO prediction of 46 ± 3 pb.

Summary

First measurements involving W and Z boson production in pp collisions at √ s=7 TeV with an integrated luminosity of ∼35 pb -1 recorded by the ATLAS detector at the Large Hadron Collider were presented. Theoretical predictions are in good agreement with all measurements within statistical and systematic uncertainties. The increase of integrated luminosity with 2011 data will permit more stringent test of perturbative QCD and tighter constraints on parton distribution functions.

Figure 1 :

 1 Figure1: To the left, measured and predicted cross sections times leptonic branching ratios: (σ W + + σ W -) vs σ Z/γ * . The projections of the ellipse to the axes correspond to one standard deviation uncertainty of the cross sections. To the right, the muon charge asymmetry from W-boson decays in bins of absolute pseudorapidity. The data points (shown with error bars including the statistical and systematic uncertainties) are compared to MC@NLO predictions with different PDF sets.

Figure 2 :

 2 Figure 2: To the left (resp. right), measured cross section (black dots) in Z/γ * (→ e + e -)+jets (resp. Z/γ * (→ µ + µ -)+jets) production as a function of the inclusive jet multiplicity (resp. p jet T ), for events with at least one jet with p jet T > 30 GeV and |η jet | < 2.8 in the final state. The error bars indicate the statistical uncertainty and the dashed areas the statistical and systematic uncertainties added in quadrature. The measurements are compared to NLO pQCD predictions from MCFM (only available up to 2 jets), as well as the predictions from ALPGEN, SHERPA, and PYTHIA. The shadowed areas around the ALPGEN and SHERPA predictions denote a 5% uncertainty on the absolute normalization.

Table 1 :

 1 ). Total cross sections of the pp → lνγ + X and pp → llγ + X process at √ s = 7 T eV . Both, experimental measurement and SM model NLO prediction are given. The total cross sections are measured with pT (γ) >

		Experimental measurement	SM model prediction
		σ total [pb](measured)	σ total [pb](predicted)
	pp → eνγ pp → µνγ pp → e + e -γ pp → µ + µ -γ	73.9 ± 10.5(stat) ± 14.6(syst) ± 8.1(lumi) 58.6 ± 8.2(stat) ± 11.3(syst) ± 6.4(lumi) 16.4 ± 4.5(stat) ± 4.3(syst) ± 1.8(lumi) 10.6 ± 2.6(stat) ± 2.5(syst) ± 1.2(lumi)	69.0 ± 4.6(syst) 69.0 ± 4.6(syst) 13.8 ± 0.9(syst) 13.8 ± 0.9(syst)


F Robinet

SEARCHES FOR GRAVITATIONAL WAVE TRANSIENTS IN THE LIGO AND VIRGO DATA

In 2011, the Virgo gravitational wave (GW) detector will definitively end its science program following the shut-down of the LIGO detectors the year before. The years to come will be devoted to the development and installation of second generation detectors. It is the opportune time to review what has been learned from the GW searches in the kilometric interferometers data. Since 2007, data have been collected by the LIGO and Virgo detectors. Analyses have been developed and performed jointly by the two collaborations. Though no detection has been made so far, meaningful upper limits have been set on the astrophysics of the sources and on the rate of GW events. This paper will focus on the transient GW searches performed over the last 3 years. This includes the GW produced by compact binary systems, supernovae core collapse, pulsar glitches or cosmic string cusps. The analyses which have been specifically developed for that purpose will be presented along with the most recent results.

Introduction

Gravitational waves (GW) were predicted by Albert Einstein 1 with his theory of general relativity. It shows that an asymmetric, compact and relativistic object will radiate gravitationally. The waves propagate with a celerity c and their amplitude is given by the dimensionless strain h which can be projected over two polarizations h + and h × . The existence of GW was indirectly confirmed through observations on the binary pulsar PSR 1913+16 discovered in 1974. This binary system has been followed-up over more than 30 years and the orbit decay can be fully explained by the energy loss due to the gravitational wave emission [START_REF] Taylor | [END_REF] . The great challenge of this century is to be able to detect gravitational waves directly by measuring the space-time deformation induced by the wave. The Virgo 3 and the two LIGO 4 interferometric detectors are designed to achieve this goal. Thanks to kilometric arms, Fabry-Perot cavities, sophisticated seismic isolation, a high laser power and the use of power-recycling techniques, the LIGO and Virgo detectors were able to reach their design sensitivity which is to measure h below 10 -21 over a wide frequency band, from tens to thousands of Hz (and below 10 -22 at a few hundreds Hz). Such sensitivity over a large range of frequencies offers the possibility to detect gravitational waves originating from various astrophysical sources which will be described in Section 2.

The searches for GW in LIGO-Virgo were historically divided into four analysis groups. The physics of these groups does not really match the type of GW sources but rather the expected signals. This has the advantage to develop efficient searches adapted to the signal seen in the detector. The CBC group is specifically searching for signals resulting from the last instants of the coalescence and the merging of compact binary systems of two neutron stars, two black holes or one of each. The expected signal is well-modeled, especially the inspiral part, so that the searches are designed to be very selective. On the contrary, the burst group performs more generic searches for any type of sub-second signals. This unmodeled approach offers a robustness to the analyses and remains open to the unexpected. Doing so, the burst group covers a large variety of GW sources for which the expected signals are poorly known. This includes the asymmetric core bounce of supernovae, the merging of compact objects, the starquakes of neutron stars or the oscillating loops of cosmic strings. This paper will focus on the work performed within the CBC and the burst group and present the searches for short-duration GW signals. C. Palomba will describe the searches for continuous signals and for a stochastic background of GW 5 . Section 3 will detail the different aspects of a multi-detector GW transient search while Section 4 will highlight some of the latest results of the analyses.

Very early on, the Virgo and LIGO collaborations chose to share their data and to perform analyses in common in order to maximize the chance of detection. Indeed, having several detectors in operation presents many advantages such as performing coincidences, reconstructing the source location, having a better sky coverage or estimating the background for analyses. This close collaboration started in 2007 with the Virgo first science run VSR1 (2007) and LIGO S5 (2005-2007) run and continued until recently with the following science runs VSR2 (2009), VSR3 (2010) and S6 (2009-2010). In October 2010, the LIGO detectors shut-down to install the second generation of detectors which should resume science in 2015. Virgo will perform one more science run, VSR4, during the summer jointly with the GEO 600 6 detector in Germany. After that, Virgo will start the preparation for the next phase with Advanced Virgo.

As the first generation of interferometers is about to take an end, the analyses performed so far were not able to claim a detection. However it was possible to set astrophysically relevant upper limits and this paper will present some of them. Moreover the pioneering work performed to build efficient analyses pipelines will be a great strength for the Advanced detector era and the first steps of gravitational wave astronomy.

Sources, signals and searches

The coalescence of binary objects

The coalescence of stellar compact binary systems is often seen as the most promising candidate for a first detection. Indeed, such objects have been extensively studied and the expected waveform is rather well-modeled. The inspiral phase, up to the last stable circular orbit, can be reliably described with a post-Newtonian approximation 7 . The signal is expected to sweep upwards in frequency and to cross the detector bandwidth for a short period of time (from a few ms to tens of s). This is followed by the merger of the two bodies whose waveform can be derived from numerical relativity 8 even though this part of the waveform is the least known of the evolution of the binary. Finally, the resulting black hole is excited and loses part of its energy by radiating gravitationally. Black hole pertubation theory is well able to predict the ringdown waveform 9 and the signal is expected to be in the detector sensitive band for masses larger than 100 M ⊙ .

The search for coalescence signals, led by the CBC group, takes two free parameters into account: the masses of the two binary components. The low-mass search covers a total mass range between 2 and 35 M ⊙ where most of the energy is contained in the inspiral phase. As a complement, the high-mass search probes the 25-100 M ⊙ total mass region where the signal-tonoise ratio is significant mostly during the merger and ringdown phase. A ringdown-only search is also performed for very high-mass systems (75-750 M ⊙ ) in which case it is possible to use the spin as an additional parameter. The merger and the ringdown signals are also included in the burst searches. The robust nature of the burst analyses offers a nice complement to the CBC searches, especially for the merger phase for which the waveform is less reliable.

Astrophysical rates for compact binary coalescence are still uncertain since they are based on a few assumptions like the population of observed double pulsars in our galaxy. A plausible rate for the coalescence of two neutron stars could be somewhere between 0.01 to 10 Myr -1 Mpc -3 . These numbers offers a chance for a detection which could span between 2 × 10 -4 and 0.2 events per year 10 with the initial detector sensitivities.

Supernovae core collapse

The core bounce of supernovae could also be an interesting source of GW bursts. In this case, the GW production is a complex interplay of general relativity, nuclear and particle physics.

Recent studies 11 show that various emission mechanisms could come into play. The coherent motion of the collapsing and bouncing core during the proto-neutron star formation could be asymmetric enough to produce GW. Then the prompt convective motion behind the hydrodynamic shock in the central part of the star due to non-axisymmetric rotational instabilities could also trigger some GW radiation. Recent 2-or 3-dimensional simulations 11 are able to extract complex waveforms but they are extremely parameter-dependent and not robust enough to be used directly in a GW search. In this case again, the burst's unmodeled searches are well-suited. Some studies are in progress to decompose the supernova signatures over a basis of main components which could be then searched in the data 12 .

Isolated neutron stars

Instabilities of isolated neutron stars can also produce GW bursts which could be detected by earth-based interferometers. The invoked mechanism corresponds to the excitation of quasinormal mode oscillations which couple to GW emission. This excitation could occur as a consequence of flaring activity in soft-gamma repeaters (SGR) resulting from intense magnetic fields 13 . Another possibility comes from the merging of a binary system of two neutron stars. In that case a massive neutron star can be formed. Often excited, it could radiate gravitational waves. Fractures or star-quakes of the neutrons star crust are other possible scenarios for the quasi-normal mode oscillations of the star. F-modes oscillations are the preferred mechanism to produce GW in case of neutron stars. Hence, ringdown waveforms are often used in the searches with a high frequency (from 500 Hz to 3 kHz) and a short damping time (from 50 ms to 500 ms).

Cosmic strings

The hypothetic existence of cosmic strings 14 could be proven by looking for a signature in the GW spectrum. Indeed, gravitational radiation is the main mechanism for the cosmic string network to lose its energy. When intersecting with each other, strings can form loops which oscillate and produce some cuspy features with a strong Lorentz boost. Cosmic string cusps are therefore a powerful source of GW. Gravitational waveforms are very well predicted 15 and this motivates a dedicated search in the LIGO/Virgo data. In case of no detection, it is possible to set constraints on the string tension which is the main parameter to describe the cosmic string network.

External triggers

GW emission often results from violent events in the universe. Therefore, these events could also be seen through other channels like electro-magnetism or neutrino emission. The coincidence of a GW event with another type of trigger could critically increase the confidence into the veracity of the event. Moreover the knowledge of the position and/or the time of the event can considerably enhance the sensitivity of the searches. For instance, a gamma-ray burst (GRB) trigger could be an indication that either a binary system merged or a hyper-massive star collapsed. Dedicated analyses over GRB triggers are performed and are presented by M. Was in these proceedings 16 .

3 How to extract a GW signal

Trigger production

As discussed above, many LIGO/Virgo GW searches benefit from the knowledge of the expected waveform. In this case, match-filtering techniques can be used to produce the GW triggers. One first needs to define a template bank where the reference waveforms are covering the parameter space (the component masses for the CBC searches, for example). The distance from one template to the next must be small enough to insure a negligible loss of efficiency but large enough to limit the total number of templates and the computational cost. Then each template is slid over the detector gravitational wave strain h det (t) and the match between the two is computed as a function of time. If this match exceeds a given threshold then a trigger is produced and a signal-to-noise ratio (SNR) is defined. Most of the burst searches cannot rely on a modeled waveform. The main procedure is to perform a time-frequency analysis. It consists in tiling the time-frequency plane and in looking for an excess of energy in clusters of pixels. Again, a threshold on the energy is set to define triggers.

With an ideal detector, if no GW event is present in the detection strain, the distribution of the SNR should follow a Gaussian statistic. Then a GW event could be detected if its SNR is much larger than the noise SNR distribution. In reality the noise of the detector displays a non Gaussian behavior and the tail of the distribution is composed by many detector artefacts called glitches. Therefore, using only a single detector output, a genuine GW event cannot be disentangled from the noise. When performing a multi-detector analysis, it is possible to set in coincidence different parameters of the search like the time of the trigger or any discriminative variables describing the event. This significantly reduces the tail of the background. However the remaining distribution of events is still not Gaussian and the accidental background distribution needs to be evaluated to quantify confidence of a given event.

Background estimation

There is a reliable way to evaluate the accidental background distribution when performing a multi-detector analysis. It consists in time-sliding the data of one detector with respect to the other and looking at the time-coincident triggers which cannot contain any real signal. This gives a fair estimation for the background provided that the time shift is larger than the duration of the expected signals and that the noise is locally stationary. With the resulting distribution one can set a detection threshold corresponding to a fixed false alarm rate.

Data quality

After having performed coincidences between detectors, the background tail is still the main limiting factor for the searches. It is crucial to understand the origin of the glitches to remove them safely and to be able to lower the detection threshold as much as possible. The data quality groups in Virgo 17 and LIGO 18 play a major role in the analysis. They study the couplings between the detection channel and the auxiliary channels to define efficient vetoes to reduce the number of glitches in the tails. Interferometers are sensitive instruments to the environment so it is imperative to monitor disturbances of different natures: acoustic, magnetic, mechanical etc. Then selective vetoes based on environmental channels are produced to increase the sensitivity of the searches.

Upper limits

Until now, no GW detection has been made. However upper limits can be obtained provided that the efficiency of the search is known. To achieve this, analyses pipelines are run on the detector data streams where fake signals have been injected. The number of recovered injections provides the efficiency of the search. In case of template searches, the modeled waveforms are injected to cover the parameter space. Then upper limits can be given as a function of the physical parameters. For unmodeled searches generic waveforms are injected with varying parameters. For instance, for the burst all-sky analyses, sine-Gaussian, Gaussian, ringdowns and cosmic string cusps signals are injected. Because of the unmodeled nature of the search, the upper limits are given on the rate as a function of the GW amplitude for a specific set of waveforms.

Selection of results

Limits on the rate of binary coalescence

The first search for gravitational waves from compact binary coalescence with the coincidence of the LIGO and Virgo data was performed on S5 and VSR1 data 19 . It covers the low-mass region (from 2 to 35 M ⊙ ). No detection resulted from this search and upper limits on the rate of compact binary coalescence were estimated. If the spin is neglected and assuming a mass of 1.35 ± 0.04 M ⊙ for the neutron star and 5.0 ± 1.0 M ⊙ for the black hole, the upper limits at 90% confidence level are:

R BN S 90% = 8.7 × 10 -3 yr -1 L -1 10 , (1)
R BHN S 90% = 2.2 × 10 -3 yr -1 L -1 10 , (2)
R BBH 90% = 4.4 × 10 -4 yr -1 L -1 10 , (3)
where BNS stands for binary neutron stars, BHNS for black hole neutron star binary and BBH for binary black holes. L 10 corresponds to 10 10 times the blue solar luminosity (typical for a galaxy) which is expected to be proportional to the binary coalescence rate (blue luminosity density 20 : (1.98 × 10 -2 ) L 10 Mpc -3 ). Upper limits can also be produced in mass bins and are presented on Figure 1. Recently, the high-mass search (from 25 to 100 M ⊙ ) has also been completed and full coalescence waveforms have been used 21 . The analysis has been performed only on LIGO data since the Virgo sensitivity was not sufficient for these high mass systems during VSR1. Upper limits have been placed on the merger rate of binary black holes as a function of the component masses. For example, for two black holes with a component mass between 19 and 28 M ⊙ the merger rate should not exceed 2.0 Myr -1 Mpc -3 at 90 % confidence.

All-sky burst search

The all-sky search for unmodeled gravitational-wave bursts has been performed on the LIGO and Virgo data for S5 and VSR1 science runs 22 . This is a null result for a detection and upper limits have been estimated in terms of an event rate versus strength for several types of plausible burst waveforms as presented on Figure 2. The signal strength is measured with h rss defined as:

h rss = +∞ -∞ dt (|h + (t)| 2 + |h × (t)| 2 ). ( 4
)
Figure 2: Selected exclusion diagrams showing the 90% confidence rate limit as a function of signal amplitude for sine-Gaussian with a quality factor of 9 and various frequencies (left) and Gaussian of different widths (right) waveforms for the results of the entire S5 and VSR1 runs compared to the results reported with the previous runs (S1, S2, and S4).

GW associated to neutron stars

There are several new LIGO/Virgo results dealing with the physics of neutron stars. The search for GW associated with the timing glitch of the Vela pulsar (PSR B083345) has recently been published 23 . Upper limits have been placed on the peak intrinsic strain amplitude of gravitational wave ring-down signals, depending on which spherical harmonic mode is excited as shown in Table 1.

Spherical Harmonic Indices h 90% 2m E 90% 2m (erg) l = 2, m = 0 1.4 × 10 -20 5.0 × 10 44 l = 2, m = ±1 1.2 × 10 -20 1.3 × 10 45 l = 2, m = ±2 6.3 × 10 -21 6.3 × 10 44
Table 1: The Bayesian 90% confidence upper limits on the intrinsic strain amplitude and energy associated with each spherical harmonic mode of oscillation assuming only a single harmonic (i.e. value of |m|) is excited.

An external triggered search has been conducted on electromagnetic triggers from six magnetars which are neutron stars powered by extreme magnetic fields 24 . These rare objects are characterized by repeated and sometimes spectacular gamma-ray bursts which could also be a source of GW. The upper limits for band-and time-limited white noise bursts in the detector sensitive band, and for f-mode ringdowns (at 1090 Hz), are 3.0 × 10 44 d 2 1 erg and 1.4 × 10 47 d 2 1 erg respectively, where d 1 = d 0501 /1kpc and d 0501 is the distance to SGR 0501+4516 which is likely to be ∼ 1 kpc from Earth. These limits on GW emission from f-modes are an order of magnitude lower than any previous results, and approach the range of electromagnetic energies seen in SGR giant flares for the first time.

Cosmic string upper limits

The burst group tries to constrain the cosmic string parameter space by looking for GW emitted by cuspy features of oscillating loops 25 . The first analyses of the S4 LIGO data reports upper limits on the Gµ-ε plane where Gµ is the string tension and ε is a parameter for the loop size. Figure 3 shows the region of the parameter space which can be rejected for a cosmic string reconnection probability of 10 -3 . The up-coming analysis of S5/S6-VSR1/VSR2/VSR3 should be able to place the most stringent limits on the cosmic string models. Areas to the right of the red curves show the regions excluded at the 90% level. The dotted curves indicate the uncertainty. The black and blue curves limit the regions of parameter space unlikely to result in a cosmic string cusp event detected in S4: a cosmic string network with model parameters in these regions would result in less than one event (on average) surviving the search. The black curve was computed using the efficiency for all recovered injections. The blue curve shows regions of parameter space unlikely to result in a cosmic string cusp being detected in a year long search with the initial LIGO sensitivity estimate.

Conclusion

Searches for GW transient signals in Virgo and LIGO data have reached maturity. No GW detection can be claimed yet but significant astrophysical upper limits can be extracted from the data covering a large variety of sources. The data-taking campaigns are now over for the first generation of GW detectors but some more analysis results are expected to be released in the next months. The most recent data of S6/VSR2-3 are being analyzed and new results are about to be published. The second generation of detectors is now in preparation and the GW science should resume in 2015. With an increased sensitivity of about a factor 10, we should expect to extend the visible volume of sources by a factor 1000. This offers a great opportunity for a detection. Even with the most pessimistic scenarios, advanced detectors should be able to detect GW. For instance, it is reasonable to expect a rate for binary neutron star coalescences of about 40 events per year.

Figure 1 :

 1 Figure1: The 90% rate upper limits as a function of mass. The first figure gives the upper-limit on the rate of coalescence from BBH system as a function of the total mass of the system. The second figure gives the BHNS upper-limit as a function of black hole mass, assuming a fixed neutron star mass of 1.35 M⊙.

Figure 3 :

 3 Figure3: Plot of the upper-limit results of the S4 cosmic string analysis for a reconnection probability of 10 -3 . Areas to the right of the red curves show the regions excluded at the 90% level. The dotted curves indicate the uncertainty. The black and blue curves limit the regions of parameter space unlikely to result in a cosmic string cusp event detected in S4: a cosmic string network with model parameters in these regions would result in less than one event (on average) surviving the search. The black curve was computed using the efficiency for all recovered injections. The blue curve shows regions of parameter space unlikely to result in a cosmic string cusp being detected in a year long search with the initial LIGO sensitivity estimate.

Acknowledgments

The authors gratefully acknowledge the support of the United States National Science Foundation for the construction and operation of the LIGO Laboratory, the Science and Technology Facilities Council of the United Kingdom, the Max-Planck-Society, and the State of Niedersachsen/Germany for support of the construction and operation of the GEO600 detector, and the Italian Istituto Nazionale di Fisica Nucleare and the French Centre National de la Recherche Scientifique for the construction and operation of the Virgo detector. The authors also gratefully acknowledge the support of the research by these agencies and by the Australian Research Council, the International Science Linkages program of the Commonwealth of Australia, the Council of Scientific and Industrial Research of India, the Istituto Nazionale di Fisica Nucleare of Italy, the Spanish Ministerio de Educación y Ciencia, the Conselleria d'Economia Hisenda i Innovació of the Govern de les Illes Balears, the Foundation for Fundamental Research on Matter supported by the Netherlands Organisation for Scientific Research, the Polish Ministry of Science and Higher Education, the FOCUS Programme of Foundation for Polish Science, the Royal Society, the Scottish Funding Council, the Scottish Universities Physics Alliance, The National Aeronautics and Space Administration, the Carnegie Trust, the Leverhulme Trust, the David and Lucile Packard Foundation, the Research Corporation, and the Alfred P. Sloan Foundation.