Omar Fawzi
email: omar.fawzi@ens-lyon.fr

Paul Fermé
email: paul.ferme@ens-lyon.fr

Beating the Sum-Rate Capacity of the Binary Adder Channel with Non-Signaling Correlations

We address the problem of coding for multiple-access channels (MACs) with the assistance of nonsignaling correlations between parties. It is well-known that non-signaling assistance does not change the capacity of point-to-point channels. However, it was recently observed that one can construct MACs from two-player non-local games while relating the winning probability of the game to the capacity of the MAC. By considering games for which entanglement (a special kind of non-signaling correlation) increases the winning probability (e.g., the Magic Square game), this shows that for some specic kinds of channels, entanglement between the senders can increase the capacity.

Here, we show that the increase in capacity from non-signaling assistance goes beyond such special channels and applies even to a simple deterministic MAC: the binary adder channel. In particular, we show that, with non-signaling assistance, a sum-rate of log 2 (72) 4 1.5425 can be reached with zero error, beating the maximum classical sum-rate capacity of 3 2 . Furthermore, we show that this capacity increase persists if a small amount of noise is added to the channel.

In order to achieve this, we show that ecient linear programs can be formulated to compute the success probability of the best non-signaling assisted code for a nite number of copies of a multipleaccess channel. In particular, this can be used to give lower bounds on the zero-error non-signaling assisted capacity of multiple-access channels.

Introduction

Multiple-access channels (MACs for short) are one of the simplest model of network communication settings, where two senders aim to transmit individual messages to one receiver. The capacity of such channels has been entirely characterized by the seminal works by Liao [START_REF] Herng | Multiple access channels[END_REF] and Ahlswede [START_REF] Ahlswede | Multi-way communication channels[END_REF] in terms of the following single-letter formula:

Theorem 1.1. The capacity region C(W ) of the MAC W is the closure of all rate pairs (R 1 , R 2 ) such that:

R 1 ≤ I(X 1 : Y |X 2 ) , R 2 ≤ I(X 2 : Y |X 1 ) , R 1 + R 2 ≤ I((X 1 , X 2 ) : Y ) ,
for (X 1 , X 2 ) ∈ X 1 × X 2 following a product law P X 1 × P X 2 , and Y ∈ Y the outcome of W on inputs X 1 , X 2 .

From the point of view of quantum information, it is natural to ask whether additional resources, such as quantum entanglement between the parties, changes the capacity region. A well-known result [START_REF] Charles | Entanglement-assisted classical capacity of noisy quantum channels[END_REF] states that for classical point-to-point channels, entanglement and even more generally non-signaling correlations do not help; see also [START_REF] Matthews | A linear program for the nite block length converse of Polyanskiy-Poor-Verdú via nonsignaling codes[END_REF][START_REF] Barman | Algorithmic aspects of optimal channel coding[END_REF]. However, in [START_REF] Leditzky | Playing games with multiple access channels[END_REF], it is shown that quantum entanglement shared between the two senders of a multiple access channel can strictly extend the capacity region. It occurs for some channels constructed from two-player non-local games, such as the Magic Square game [START_REF] David | Simple unied form for the major no-hidden-variables theorems[END_REF][START_REF] Peres | Incompatible results of quantum measurements[END_REF][START_REF] Pk Aravind | A simple demonstration of Bell's theorem involving two observers and no probabilities or inequalities[END_REF][START_REF] Brassard | Quantum pseudo-telepathy[END_REF], translating known gaps between classical and quantum values of games into MAC capacity gaps. The MACs constructed this way have very special form though and one may wonder whether non-signaling correlations can help for more natural MACs. Here we focus on the simplest textbook MAC: the binary adder channel which maps (x 1 , x 2 ) ∈ {0, 1} 2 to x 1 + x 2 ∈ {0, 1, 2}. It is worth noting that, unlike the channels of [START_REF] Leditzky | Playing games with multiple access channels[END_REF], the BAC is deterministic. The capacity region of this channel is known to be given by

C(W BAC ) = {(R 1 , R 2 ) : R 1 ≤ 1, R 2 ≤ 1, R 1 + R 2 ≤ 3 2 }.
In this work, we focus on the quantity S NS (W, k 1 , k 2 ), which denotes the success probability of the best non-signaling assisted (k 1 , k 2 )-code for the MAC W . Contrary to the unassisted value S(W, k 1 , k 2 ), S NS (W, k 1 , k 2 ) can be formulated as a linear program; see Proposition 3.1. Furthermore, using symmetries, we have developed a linear program computing S NS for a nite number of copies of a MAC W with a size growing polynomially in the number of copies; see Theorem 3.9 and Corollary 3.10. Applied to the binary adder channel, we have shown that the sum-rate log 2 (72) [START_REF] Pk Aravind | A simple demonstration of Bell's theorem involving two observers and no probabilities or inequalities[END_REF] 1.5425 can be reached with zero error, which beats the maximum classical sum-rate capacity of 3 2 ; see Theorem 4.1. Finally, for noisy channels, where the zero-error non-signaling assisted capacity region is trivial, we can use concatenated codes to obtain achievable points in the capacity region. Applied to a noisy version of the binary adder channel, we have shown that non-signaling assistance still improves the sum-rate capacity.

In Section 2, we dene precisely the dierent notions of MAC capacities: the classical capacity (i.e. without any assistance) as well as the non-signaling assisted capacity. In Section 3, we address computational complexity questions concerning the probability of success of the best classical coding strategy and the best non-signaling strategy for a MAC. In Section 4, we apply these results to the binary adder channel. Finally, in Section 5, we handle the case of noisy channels through concatenated codes, and apply it to a noisy version of the binary adder channel.

2

Multiple Access Channels Capacities

Classical Capacities

Formally, a MAC W is a conditional probability distribution depending on two inputs in X 1 and X 2 , and an output in Y, so W := (W (y|x 1 x 2 )) x 1 ∈X 1 ,x 2 ∈X 2 ,y∈Y such that W (y|x 1 x 2 ) ≥ 0 and y∈Y W (y|x 1 x 2 ) = 1.

We will denote such a MAC by W : X 1 × X 2 → Y. The tensor product of two MACs W :

X 1 × X 2 → Y and W : X 1 × X 2 → Y is denoted by W ⊗ W : (X 1 × X 1 ) × (X 2 × X 2 ) → Y × Y and dened by (W ⊗W )(yy |x 1 x 1 x 2 x 2 ) := W (y|x 1 x 2 )•W (y |x 1 x 2 ). We denote by W ⊗n (y n |x n 1 x n 2 ) := n i=1 W (y i |x 1,i x 2,i ), for y n := y 1 . . . y n ∈ Y n , x n 1 := x 1,1 . . . x 1,n ∈ X n 1 and x n 2 := x 2,1 . . . x 2,n ∈ X n 2 .
We will use the notation [k] := {1, . . . , k}.

For a MAC W :

X 1 × X 2 → Y, we write S(W, k 1 , k 2 )
for the maximal probability of successfully sending k 1 messages for sender 1 and k 2 messages for sender 2. This means that one can encode k 1 messages in

X 1 through e 1 : [k 1 ] → X 1 , k 2 messages in X 2 through e 2 : [k 2 ] → X 2 ,
e 1 W e 2 d x 1 x 2 y i 1 i 2 (j 1 , j 2 ) Figure 1: Coding for a MAC W . S(W, k 1 , k 2 ) := maximize e 1 ,e 2 ,d 1 k 1 k 2 x 1 ,x 2 ,y,i 1 ,i 2 W (y|x 1 x 2 )e 1 (x 1 |i 1 )e 2 (x 2 |i 2 )d(i 1 i 2 |y) subject to x 1 ∈X 1 e 1 (x 1 |i 1 ) = 1, ∀i 1 ∈ [k 1 ] x 2 ∈X 2 e 2 (x 2 |i 2 ) = 1, ∀i 2 ∈ [k 2 ] j 1 ∈[k 1 ],j 2 ∈[k 2 ] d(j 1 j 2 |y) = 1, ∀y ∈ Y e 1 (x 1 |i 1 ), e 2 (x 2 |i 2 ), d(j 1 j 2 |y) ≥ 0 (1)
Since MACs are more general than point-to-point channels (by dening W (y|x 1 x 2 ) := Ŵ (y|x 1 ) for Ŵ a point-to-point channel and looking only at its rst input), computing a single value S(W, k 1 , k 2 ) is NP-hard, and it is even NP-hard to approximate S(W, k 1 , k 2 ) within a better ratio than 1 -e -1 , as a consequence of the hardness result on S(W, k) shown in [START_REF] Barman | Algorithmic aspects of optimal channel coding[END_REF].

The (classical) capacity of a MAC, as dened for example in [START_REF] Cover | Elements of Information Theory[END_REF], can be reformulated in the following way:

Denition 2.1 (Capacity Region C(W ) of a MAC W ). A rate pair (R 1 , R 2 ) is achievable if: lim n→+∞ S(W ⊗n , 2 R 1 n , 2 R 2 n ) = 1 .
We dene the (classical) capacity region C(W ) as the closure of the set of all achievable rate pairs. For the zero-error (classical) capacity, this leads to the following denition:

Denition 2.2 (Zero-Error Capacity Region C 0 (W ) of a MAC W ). A rate pair (R 1 , R 2 ) is achievable with zero-error if: ∃n 0 ∈ N * , ∀n ≥ n 0 , S(W ⊗n , 2 R 1 n , 2 R 2 n ) = 1 .
We dene the zero-error (classical) capacity region C 0 (W ) as the closure of the set of all achievable rate pairs with zero-error.

Non-Signaling Assisted Capacities

When non-signaling assistance is given to a MAC, both encoders e 1 , e 2 and the decoder d are replaced by a non-signaling box P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y), i.e., each party's output is conditionally independent from the inputs of the others, given this party's input. The way a non-signaling box can be used for coding is depicted in Figure 2. The maximal probability of successfully sending k 1 messages for sender 1 and k 2 messages for sender 2 with non-signaling assistance, which we call S NS (W, k 1 , k 2 ), is given by the following linear program, where the constraints translate the fact that P is a non-signaling box:

P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) i 1 i 2 (j 1 , j 2 ) W x 1 x 2 y Figure 2:
The use of a non-signaling box P as a coding strategy for the MAC W .

S NS (W, k 1 , k 2 ) := maximize P 1 k 1 k 2 x 1 ,x 2 ,y,i 1 ,i 2 W (y|x 1 x 2 )P (x 1 x 2 (i 1 i 2 )|i 1 i 2 y)
subject to

x 1 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) = x 1 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) x 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) = x 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) j 1 j 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) = j 1 j 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y ) x 1 ,x 2 ,j 1 ,j 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) = 1 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) ≥ 0 (2)
Since it is given as a linear program, the complexity of computing S NS (W, k 1 , k 2 ) is polynomial in the number of variables and constraints (see for instance Section 7.1 of [START_REF] Gärtner | Understanding and using linear programming[END_REF]), which is a polynomial in |X 1 |, |X 2 |, |Y|, k 1 and k 2 . Also, as it is easy to check that a classical strategy is a particular case of a non-signaling assisted strategy, we have that

S NS (W, k 1 , k 2 ) ≥ S(W, k 1 , k 2 ).
We have then the same denitions of capacity and zero-error capacity:

lim n→+∞ S NS (W ⊗n , 2 R 1 n , 2 R 2 n ) = 1 .
We dene the non-signaling assisted capacity region C NS (W ) as the closure of the set of all achievable rate pairs with non-signaling assistance.

Denition 2.4 (Zero-Error Non-Signaling Assisted Capacity Region C NS 0 (W ) of a MAC W ). A rate pair (R 1 , R 2 ) is achievable with zero-error and non-signaling assistance if:

∃n 0 ∈ N * , ∀n ≥ n 0 , S NS (W ⊗n , 2 R 1 n , 2 R 2 n ) = 1 .
We dene the zero-error non-signaling assisted capacity region C NS 0 (W ) as the closure of the set of all achievable rate pairs with zero-error and non-signaling assistance.

S NS (W, k 1 , k 2 ) = maximize r,r 1 ,r 2 ,p 1 k 1 k 2 x 1 ,x 2 ,y W (y|x 1 x 2 )r x 1 ,x 2 ,y subject to x 1 ,x 2 r x 1 ,x 2 ,y = 1 x 1 r 1 x 1 ,x 2 ,y = k 1 x 1 r x 1 ,x 2 ,y x 2 r 2 x 1 ,x 2 ,y = k 2 x 2 r x 1 ,x 2 ,y x 1 p x 1 ,x 2 = k 1 x 1 r 2 x 1 ,x 2 ,y x 2 p x 1 ,x 2 = k 2 x 2 r 1 x 1 ,x 2 ,y 0 ≤ r x 1 ,x 2 ,y ≤ r 1 x 1 ,x 2 ,y , r 2 x 1 ,x 2 ,y ≤ p x 1 ,x 2 p x 1 ,x 2 -r 1 x 1 ,x 2 ,y -r 2 x 1 ,x 2 ,y + r x 1 ,x 2 ,y ≥ 0 (3)
Proof. One can check that given a solution of the original program, the following choice of variables is a valid solution of the second program achieving the same objective value:

r x 1 ,x 2 ,y := i 1 ,i 2 P (x 1 x 2 (i 1 i 2 )|i 1 i 2 y) , r 1 x 1 ,x 2 ,y := j 1 ,i 1 ,i 2 P (x 1 x 2 (j 1 i 2 )|i 1 i 2 y) , r 2 x 1 ,x 2 ,y := j 2 ,i 1 ,i 2 P (x 1 x 2 (i 1 j 2 )|i 1 i 2 y) , p x 1 ,x 2 := j 1 ,j 2 ,i 1 ,i 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) . (4)
Note that p x 1 ,x 2 is well-dened since j 1 ,j 2 ,i 1 ,i 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) is independent from y by NS conditions. For the other direction, given those variables, a non-signaling probability distribution P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) achieving the same objective value is given by, for j 1 = i 1 and j 2 = i 2 :

P (x 1 x 2 (i 1 i 2 )|i 1 i 2 y) := r x 1 ,x 2 ,y k 1 k 2 , P (x 1 x 2 (j 1 i 2 )|i 1 i 2 y) := r 1 x 1 ,x 2 ,y -r x 1 ,x 2 ,y k 1 k 2 (k 1 -1) , P (x 1 x 2 (i 1 j 2 )|i 1 i 2 y) := r 2 x 1 ,x 2 ,y -r x 1 ,x 2 ,y k 1 k 2 (k 2 -1) , P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) := p x 1 ,x 2 -r 1 x 1 ,x 2 ,y -r 2 x 1 ,x 2 ,y + r x 1 ,x 2 ,y k 1 k 2 (k 1 -1)(k 2 -1)
.

(5)

3.2

Properties of S NS (W, k 1 , k 2 ), C NS (W ) and C NS 0 (W ) Denition 3.2. We say that a conditional probability distribution

Q(a n |x n ) dened on (A 1 × . . . × A n )× (X 1 × . . . × X n ) and Q (a n |x n ) is non-signaling if for all a n , x n , xn , we have ∀i ∈ [n], a i Q(a 1 . . . a i . . . a n |x 1 . . . x i . . . x n ) = a i Q(a 1 . . . a i . . . a n |x 1 . . . xi . . . x n ) . Denition 3.3. Let Q(a n |x n ) be a conditional probability distribution dened on (A 1 × . . . × A n ) × (X 1 × . . . × X n ) and Q (a n |x n ) a conditional probability distribution dened on (A 1 × . . . × A n )×(X 1 × . . . × X n ).
We dene P := Q⊗Q the tensor product conditional probability distribution dened on

((A 1 × A 1 ) × . . . × (A n × A n )) ((X 1 × X 1 ) × . . . × (X n × X n )) by P (a 1 a 1 . . . a n a n |x 1 x 1 . . . x n x n ) := Q(a n |x n ) • Q (a n |x n ). Lemma 3.4. If both Q and Q are non-signaling, then P = Q ⊗ Q is non-signaling. Proof. Let a 1 , . . . , a i-1 , a i+1 , . . . , a n ∈ A 1 × . . . × A i-1 × A i+1 × . . . × A n , a 1 , . . . , a i-1 , a i+1 , . . . , a n ∈ A 1 × . . . × A i-1 × A i+1 × . . . × A n , x 1 , . . . , x n ∈ X 1 × . . . × X n and x 1 , . . . , x n ∈ X 1 × . . . × X n .
We have:

a i a i P (a 1 a 1 . . . a i a i . . . a n a n |x 1 x 1 . . . x i x i . . . x n x n ) = a i a i Q(a 1 . . . a i . . . a n |x 1 . . . x i . . . x n ) • Q (a 1 . . . a i . . . a n |x 1 . . . x i . . . x n ) = a i Q(a 1 . . . a i . . . a n |x 1 . . . x i . . . x n ) • a i Q (a 1 . . . a i . . . a n |x 1 . . . x i . . . x n ) = a i Q(a 1 . . . a i . . . a n |x 1 . . . xi . . . x n ) • a i Q (a 1 . . . a i . . . a n |x 1 . . . x i . . . x n )
since Q and Q are non-signaling

a i a i P (a 1 a 1 . . . a i a i . . . a n a n |x 1 x 1 . . . xi x i . . . x n x n ) , (6)
so P is non-signaling.

Proposition 3.5. For a MAC W :

X 1 × X 2 → Y and k 1 , k 2 ∈ N * , we have: 1. 1 k 1 k 2 ≤ S NS (W, k 1 , k 2 ) ≤ 1. 2. S NS (W, k 1 , k 2 ) ≤ min |X 1 | k 1 , |X 2 | k 2 , |Y| k 1 k 2 . 3. If k 1 ≤ k 1 and k 2 ≤ k 2 , then S NS (W, k 1 , k 2 ) ≥ S NS (W, k 1 , k 2 ).

For any MAC

W : X 1 ×X 2 → Y and k 1 , k 2 ∈ N * , we have S NS (W ⊗W , k 1 k 1 , k 2 k 2 ) ≥ S NS (W, k 1 , k 2 )• S NS (W , k 1 , k 2 ).
In particular, for any positive integer n,

S NS (W ⊗n , k n 1 , k n 2 ) ≥ S NS (W, k 1 , k 2 ) n and S NS (W ⊗ W , k 1 , k 2 ) ≥ S NS (W, k 1 , k 2 ).
Proof.

1. Let us rst show that

S NS (W, k 1 , k 2 ) ≥ 1 k 1 k 2 . Take p x 1 ,x 2 := k 1 k 2 |X 1 ||X 2 | , r 1 x 1 ,x 2 ,y := px 1 ,x 2 k 2 , r 2 x 1 ,x 2 ,y := px 1 ,x 2 k 1 and r x 1 ,x 2 ,y := px 1 ,x 2 k 1 k 2 = 1 |X 1 ||X 2 |
. One can easily check that it is indeed a valid solution of the linear program computing S NS (W, k 1 , k 2 ). Thus we have:

S NS (W, k 1 , k 2 ) ≥ 1 k 1 k 2 x 1 ,x 2 ,y W (y|x 1 x 2 )r x 1 ,x 2 ,y = 1 k 1 k 2 x 1 ,x 2 1 |X 1 ||X 2 | y W (y|x 1 x 2 ) = 1 k 1 k 2 x 1 ,x 2 1 |X 1 ||X 2 | = 1 k 1 k 2 . (7)
Furthermore, in order to show that it is at most 1, let us consider an optimal solution of S NS (W, k 1 , k 2 ).

We have:

S NS (W, k 1 , k 2 ) = 1 k 1 k 2 x 1 ,x 2 ,y W (y|x 1 x 2 )r x 1 ,x 2 ,y ≤ 1 k 1 k 2 x 1 ,x 2 ,y W (y|x 1 x 2 )p x 1 ,x 2 = 1 k 1 k 2 x 1 ,x 2 p x 1 ,x 2 y W (y|x 1 x 2 ) = 1 k 1 k 2 x 1 ,x 2 p x 1 ,x 2 = 1 , (8)
since x 1 ,x 2 p x 1 ,x 2 = k 1 x 1 ,x 2 r 2 x 1 ,x 2 ,y = k 1 k 2 x 1 ,x 2 r x 1 ,x 2 ,y = k 1 k 2 .

First let us show that

S NS (W, k 1 , k 2 ) ≤ |X 1 | k 1 (the case S NS (W, k 1 , k 2 ) ≤ |X 2 | k 2 is symmetric): S NS (W, k 1 , k 2 ) = 1 k 1 k 2 x 1 ,x 2 ,y W (y|x 1 x 2 )r x 1 ,x 2 ,y ≤ 1 k 1 k 2 x 1 ,x 2 ,y W (y|x 1 x 2 )r 2 x 1 ,x 2 ,y ≤ 1 k 1 k 2 x 2 ,y   x 1 W (y|x 1 x 2 )   • x 1 r 2 x 1 ,x 2 ,y since nonnegative terms. = 1 k 1 k 2 x 2 ,y   x 1 W (y|x 1 x 2 )   • 1 k 1 x 1 p x 1 ,x 2 = 1 k 2 1 k 2 x 1 ,x 2 p x 1 ,x 2 x 1 y W (y|x 1 x 2 ) = |X 1 | k 2 1 k 2 x 1 ,x 2 p x 1 ,x 2 = |X 1 | k 1 . (9)
Let us show now that

S NS (W, k 1 , k 2 ) ≤ |Y| k 1 k 2 : S NS (W, k 1 , k 2 ) = 1 k 1 k 2 x 1 ,x 2 ,y W (y|x 1 x 2 )r x 1 ,x 2 ,y ≤ 1 k 1 k 2 y max x 1 ,x 2 W (y|x 1 x 2 ) x 1 ,x 2 r x 1 ,x 2 ,y ≤ 1 k 1 k 2 y x 1 ,x 2 r x 1 ,x 2 ,y = |Y| k 1 k 2 . ( 10
)
3. Let us assume that k 1 ≤ k 1 and that k 2 = k 2 , since this latter case will follow by symmetry. Consider an optimal solution of S NS (W,

k 1 , k 2 ) = 1 k 1 i 1 ∈[k 1 ] f (i 1 ) with: f (i 1 ) := 1 k 2 x 1 ,x 2 ,y,i 2 W (y|x 1 x 2 )P (x 1 x 2 (i 1 i 2 )|i 1 i 2 y) ,
and P non-signaling. Let us consider S ∈ argmax

S ⊆[k 1 ]:|S |=k 1 i 1 ∈S f (i 1 )
. Then, by construction, we have that 1

k 1 i 1 ∈S f (i 1 ) ≥ 1 k 1 i 1 ∈[k 1 ] f (i 1 ) = S NS (W, k 1 , k 2 )
, since we have taken the average of the k 1 largest values of the sum.

Let us dene the strategy P on the smallest set

X 1 × X 2 × (S × [k 2 ]) × S × [k 2 ] × Y: P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) := P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) + C(x 1 x 2 j 2 |i 1 i 2 y) , with C(x 1 x 2 j 2 |i 1 i 2 y) := 1 k 1 j 1 ∈[k 1 ]-S P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) . (11)
P is a correct conditional probability distribution. Indeed, it is nonnegative by construction, and we have that:

x 1 ,x 2 ,j 1 ∈S,j 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) = x 1 ,x 2 ,j 1 ∈S,j 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) + x 1 ,x 2 ,j 1 ∈S,j 2 C(x 1 x 2 j 2 |i 1 i 2 y) = x 1 ,x 2 j 2 j 1 ∈S P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) + x 1 ,x 2 ,j 2 j 1 ∈S 1 k 1 j 1 ∈[k 1 ]-S P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) = x 1 ,x 2 ,j 2 j 1 ∈S P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) + x 1 ,x 2 ,j 2 j 1 ∈[k 1 ]-S P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) = x 1 ,x 2 ,j 1 ,j 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) = 1 . (12)
Let us show that P is non-signaling:

(a) First with x 1 :

x 1 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) = x 1 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) + x 1 C(x 1 x 2 j 2 |i 1 i 2 y) = x 1 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) + 1 k 1 j 1 ∈[k 1 ]-S x 1 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) = x 1 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) + 1 k 1 j 1 ∈[k 1 ]-S x 1 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) since P is non-signaling. = x 1 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) . (13)
(b) Then with x 2 :

x 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) = x 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) + x 2 C(x 1 x 2 j 2 |i 1 i 2 y) = x 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) + 1 k 1 j 1 ∈[k 1 ]-S x 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) = x 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) + 1 k 1 j 1 ∈[k 1 ]-S x 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) since P is non-signaling. = x 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) . (14)
(c) Finally with (j 1 j 2 ):

j 1 ∈S,j 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) = j 2 j 1 ∈S P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) + j 2 j 1 ∈S C(x 1 x 2 j 2 |i 1 i 2 y) = j 2 j 1 ∈S P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) + j 2 j 1 ∈S 1 k 1 j 1 ∈[k 1 ]-S P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) = j 2 j 1 ∈S P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) + j 2 j 1 ∈[k 1 ]-S P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) = j 1 j 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y) = j 1 j 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y ) since P is non-signaling. = j 1 ∈S,j 2 P (x 1 x 2 (j 1 j 2 )|i 1 i 2 y ) .
(15) Thus P is a correct solution of the program computing S NS (W, k 1 , k 2 ), and it leads to the value:

S NS (W, k 1 , k 2 ) ≥ 1 k 1 k 2 x 1 ,x 2 ,y,i 1 ∈S,i 2 W (y|x 1 x 2 )P (x 1 x 2 (i 1 i 2 )|i 1 i 2 y) ≥ 1 k 1 k 2 x 1 ,x 2 ,y,i 1 ∈S,i 2 W (y|x 1 x 2 )P (x 1 x 2 (i 1 i 2 )|i 1 i 2 y) = 1 k 1 i 1 ∈S f (i 1 ) ≥ 1 k 1 i 1 ∈[k 1 ] f (i 1 ) = S NS (W, k 1 , k 2 ) . (16)
4. Consider optimal non-signaling probability distributions P and P reaching respectively the values S NS (W, k 1 , k 2 ) and S NS (W , k 1 , k 2 ). Then by Lemma 3.4, P ⊗ P is a non-signaling probability distribution on

(X 1 × X 1 ) × (X 2 × X 2 ) × (([k 1 ] × [k 1 ]) × ([k 2 ] × [k 2 ])) × ([k 1 ] × [k 1 ]) × ([k 2 ] × [k 2 ]) × (Y × Y ), which is trivially in bijection with (X 1 × X 1 ) × (X 2 × X 2 ) × ([k 1 k 1 ] × [k 2 k 2 ]) × [k 1 k 1 ] × [k 2 k 2 ] × (Y × Y ). This gives a valid solution of the program computing S NS (W ⊗ W , k 1 k 1 , k 2 k 2 ).
Thus, we get that S NS (W ⊗ W , k 1 k 1 , k 2 k 2 ) is larger than or equal to:

x 1 x 1 ,x 2 x 2 ,yy ,i 1 i 1 ,i 2 i 2 W ⊗ W (yy |x 1 x 1 x 2 x 2 ) P ⊗ P (x 1 x 1 x 2 x 2 (i 1 i 1 i 2 i 2 )|i 1 i 1 , i 2 i 2 yy ) = x 1 x 1 ,x 2 x 2 ,yy ,i 1 i 1 ,i 2 i 2 W (y|x 1 x 2 ) • W (y |x 1 x 2 ) P (x 1 x 2 (i 1 i 2 )|i 1 i 2 y) • P (x 1 x 2 (i 1 i 2 )|i 1 i 2 y ) =   x 1 ,x 2 ,y,i 1 ,i 2 W (y|x 1 x 2 )P (x 1 x 2 (i 1 i 2 )|i 1 i 2 y)   •   x 1 ,x 2 ,y ,i 1 ,i 2 W (y |x 1 x 2 )P (x 1 x 2 (i 1 i 2 )|i 1 i 2 y )   = S NS (W, k 1 , k 2 ) • S NS (W , k 1 , k 2 ) . (17)
In particular, applying this n times on the same MAC W gives the rst corollary, and the second one comes from the fact that

S NS (W ⊗ W , k 1 , k 2 ) ≥ S NS (W, k 1 , k 2 ) • S NS (W , 1, 1) = S NS (W, k 1 , k 2 ),
since S NS (W , 1, 1) = 1 by the rst property of Proposition 3.5.

Corollary 3.6. 1.

C NS (W ) is convex. 2. If (R 1 , R 2 ) is achievable with non-signaling assistance, then R 1 ≤ log 2 |X 1 |, R 2 ≤ log 2 |X 2 | and R 1 + R 2 ≤ log 2 |Y|. 3. If (R 1 , R 2 ) is achievable with non-signaling assistance, then for all R i ≤ R i , (R 1 , R 2 )
is achievable with non-signaling assistance.

Proof.

1. Let (R 1 , R 2 ) and ( R1 , R2 ), two pairs of rational rates achievable with non-signaling assistance for W , ie:

S NS (W ⊗n , 2 R 1 n , 2 R 2 n ) → n→+∞ 1 and S NS (W ⊗n , 2 R1 n , 2 R2 n ) → n→+∞ 1 . Let λ ∈ (0, 1) rational and dene R λ,i := λ•R i +(1-λ)• Ri , let us show that (R λ,1 , R λ,2
) is achievable with non-signaling assistance. Let us call respectively

k i := 2 R i , ki := 2 Ri , k λ,i := 2 R λ,i = k λ i • k (1-λ) i . We have R λ,i n = λ • R i n + (1 -λ) • Ri n = (λn) • R i + (1 -λ)n • Ri
. This is the idea of time-sharing : for λn copies of the MAC, we use the strategy with rate (R 1 , R 2 ) and for the (1 -λ)n other copies of the MAC, we use the strategy with rate ( R1 , R2 ). There exists some n such that λn, (1 -λ)n, λnR i , (1λ)n Ri are integers, since everything is rational. This implies that k λn i , k(1-λ)n i , k n λ,i are integers. Thus, thanks to the fourth property of Proposition 3.5, we have:

S NS (W ⊗n , k n λ,1 , k n λ,2 ) ≥ S NS (W ⊗(λn) , k λn 1 , k λn 2 ) • S NS (W ⊗((1-λ)n) , k(1-λ)n 1 , k(1-λ)n 2 ) → n→+∞ 1 • 1 = 1 . ( 18
)
Thus in particular, since we have

S NS (W ⊗n , k n λ,1 , k n λ,2 ) ≤ 1, we get that S NS (W ⊗n , k n λ,1 , k n λ,2 ) → n→+∞ 1, so (R λ,1 , R λ,2
) is achievable with non-signaling assistance. Finally, since C NS (W ) is dened as the closure of achievable rates with non-signaling assistance, we get that C NS (W ) is convex.

2. By the second property of Proposition 3.5, we have that

S NS (W ⊗n , k n 1 , k n 2 ) ≤ |X n 1 | k n 1 . In particular, if one takes R 1 > log 2 |X 1 |, then k 1 > |X 1 | and we get that S NS (W ⊗n , k n 1 , k n 2 ) ≤ |X 1 | k 1 n → n→+∞ 0, so R 1 > log 2 |X 1 |
, k n 1 , k n 2 ) ≤ |Y n | k n 1 k n 2 = |Y| k 1 k 2 n → n→+∞ 0. Thus, R 1 + R 2 >
∃n ∈ N * , S NS (W ⊗n , 2 R 1 n , 2 R 2 n ) = 1 . Proof. It is clear that if (R 1 , R 2 ) is such that ∃n 0 ∈ N * , ∀n ≥ n 0 , S NS (W ⊗n , 2 R 1 n , 2 R 2 n ) = 1, then in particular ∃n ∈ N * , S NS (W ⊗n , 2 R 1 n , 2 R 2 n ) = 1. So, C NS 0 (W )
, which is the closure of the former rate pairs, is in particular included in the closure of the latter rate pairs.

For the other inclusion, consider a rate pair (R 1 , R 2 ) and let us assume that there exists some positive integer n such that

S NS (W ⊗n , 2 R 1 n , 2 R 2 n ) = 1. Let us show that for any (R 1 , R 2 ) such that R 1 < R 1 and R 2 < R 2 : ∃n 0 ∈ N * , ∀n ≥ n 0 , S NS (W ⊗n , 2 R 1 n , 2 R 2 n ) = 1 ,
which is enough to conclude, since we consider only closure of such sets.

First, for all positive integer m, we have that S NS (W ⊗nm , 2 R 1 nm , 2 R 2 nm ) = 1. Indeed, by the fourth property of Proposition 3.5, we have that

S NS ((W ⊗n ) ⊗m , 2 R 1 n m , 2 R 2 n m ) ≥ S NS (W ⊗n , 2 R 1 n , 2 R 2 n ) m = 1, so S NS ((W ⊗n ) ⊗m , 2 R 1 n m , 2 R 2 n m ) = 1 since S NS (W, k 1 , k 2 ) ≤ 1 by the rst property of Proposition 3.5. But (W ⊗n ) ⊗m = W ⊗nm , and 2 R 1 n m ≥ 2 R 1 nm , 2 R 2 n m ≥ 2 R 2 nm
, so by the third property of Proposition 3.5, we have

S NS (W ⊗nm , 2 R 1 nm , 2 R 2 nm ) ≥ 1, so S NS (W ⊗nm , 2 R 1 nm , 2 R 2 nm ) = 1.
Then, consider some r ∈ {0, . . . , n -1}. By the fourth property of Proposition 3.5, we have that:

S NS (W ⊗(nm+r) , 2 R 1 nm , 2 R 2 nm ) = S NS (W ⊗nm ⊗ W ⊗r , 2 R 1 nm , 2 R 2 nm ) ≥ S NS (W ⊗nm , 2 R 1 nm , 2 R 2 nm ) = 1 , (19)
so

S NS (W ⊗(nm+r) , 2 R 1 nm , 2 R 2 nm ) = 1. But 2 R 1 nm = 2 R 1 nm nm+r (nm+r) = 2 R 1 1+δ (nm+r) with δ = r nm ≤ 1 m , and symmetrically 2 R 1 nm = 2 R 1 1+δ (nm+r) . Thus in particular, for all R 1 ≤ R 1 1+ 1 m and R 2 ≤ R 2 1+ 1 m , we have that for all n ≥ nm, S NS (W ⊗n , 2 R 1 n , 2 R 2 n ) = 1. So for any (R 1 , R 2 ) such that R 1 < R 1 and R 2 < R 2 , there is large enough m such that R 1 ≤ R 1 1+ 1 m and R 2 ≤ R 2 1+ 1 m
, and thus we get the expected property on (R 1 , R 2 ) for n 0 := nm.

Symmetrization

Although S NS (W, k 1 , k 2 ) can be computed in polynomial time in W , k 1 and k 2 , a channel of the form W ⊗n has exponential size in n. Thus, the linear program for S NS (W ⊗n , k 1 , k 2 ) grows exponentially with n. However, using the invariance of W ⊗n under permutations, one can nd a much smaller linear program computing S NS (W ⊗n , k 1 , k 2 ).

Denition 3.8. Let G a group acting on X 1 , X 2 , Y. We say that a MAC W :

X 1 × X 2 → Y is invariant under the action of G if: ∀g ∈ G, W (g • y|g • x 1 g • x 2 ) = W (y|x 1 x 2 ) .
In particular, for W ⊗n : X n 1 × X n 2 → Y n , the symmetric group G := S n acts in a natural way in any set A raised to power n. So for σ ∈ S n , we have that:

W ⊗n (σ • y n |σ • x n 1 σ • x n 2 ) = n i=1 W (y σ(i) |x 1,σ(i) x 2,σ(i) ) = n i=1 W (y i |x 1,i x 2,i ) = W ⊗n (y n |x n 1 x n 2 ) ,
and so W ⊗n is invariant under the action of S n .

Let

Z := {X 1 , X 2 , Y, X 1 × Y, X 2 × Y, X 1 × X 2 , X 1 × X 2 × Y}. Let us call O G (A)
the set of orbits of A under the action of G. Then, one can nd an equivalent smaller linear program for S NS (W, k 1 , k 2 ):

Theorem 3.9. Let W : X 1 × X 2 → Y a MAC invariant under the action of G. Let us name systematically w ∈ O G (X 1 ×X 2 ×Y), u ∈ O G (X 1 ×X 2 ), u 1 ∈ O G (X 1 ), u 2 ∈ O G (X 2 ), v 1 ∈ O G (X 1 ×Y), v 2 ∈ O G (X 2 ×Y), v ∈ O G (Y).
We will also call z A the projection of z ∈ O G (B) on A, for A, B ∈ Z and A projection of B; note that z A ∈ O G (A), since by denition of the action, the projection of an orbit is an orbit. Let us nally call W (w) := W (y|x 1 x 2 ) for any (x 1 , x 2 , y) ∈ w, which is well-dened since W is invariant under G. We have that S NS (W, k 1 , k 2 ) is the solution of the following linear program:

S NS (W, k 1 , k 2 ) = maximize r,r 1 ,r 2 ,p 1 k 1 k 2 w∈O G (X 1 ×X 2 ×Y) W (w)r w subject to w:w Y =v r w = |v|, ∀v ∈ O G (Y) w:w X 2 Y =v 2 r 1 w = k 1 w:w X 2 Y =v 2 r w , ∀v 2 ∈ O G (X 2 × Y) w:w X 1 Y =v 1 r 2 w = k 2 w:w X 1 Y =v 1 r w , ∀v 1 ∈ O G (X 1 × Y) u:u X 2 =v 2 X 2 p u = |v 2 X 2 | |v 2 | k 1 w:w X 2 Y =v 2 r 2 w , ∀v 2 ∈ O G (X 2 × Y) u:u X 1 =v 1 X 1 p u = |v 1 X 1 | |v 1 | k 2 w:w X 1 Y =v 1 r 1 w , ∀v 1 ∈ O G (X 1 × Y) 0 ≤ r w ≤ r 1 w , r 2 w ≤ |w| |w X 1 X 2 | p w X 1 X 2 , ∀w ∈ O G (X 1 × X 2 × Y) |w| |w X 1 X 2 | p w X 1 X 2 -r 1 w -r 2 w + r w ≥ 0, ∀w ∈ O G (X 1 × X 2 × Y) . (20)
Corollary 3.10. For a channel W :

X 1 × X 2 → Y, S NS (W ⊗n , k 1 , k 2 ) is the solution of a linear program of size bounded by O n |X 1 |•|X 2 |•|Y|-1
, thus it can be computed in polynomial time in n.

Proof. We use the linear program obtained in Theorem 3.9 with G := S n acting on W ⊗n as described before. The number of variables and constraints is linear in the number of orbits of the action of S n on the dierent sets A ∈ Z, where here

Z = {X n 1 , X n 2 , Y n , X n 1 × Y n , X n 2 × Y n , X n 1 × X n 2 , X n 1 × X n 2 × Y n }. For example, for A ∈ X n 1 × X n 2 × Y n , we have that: |O Sn (X n 1 × X n 2 × Y n )| = n + |X 1 ||X 2 ||Y| -1 |X 1 ||X 2 ||Y| -1 ≤ (n + |X 1 ||X 2 ||Y| -1) |X 1 ||X 2 ||Y|-1 .

So the number of variables and constraints is

O(n |X 1 |•|X 2 |•|Y|-1
). Note also that all the numbers occurring this linear program are integers or fractions of integers, with those integers ranging in

[(|X 1 ||X 2 ||Y|) n ], thus of size O(n log(|X 1 ||X 2 ||Y|)). So the size of this linear program is bounded by O(n |X 1 |•|X 2 |•|Y|-1
), and thus S NS (W ⊗n , k 1 , k 2 ) can be computed in polynomial time in n; see for instance Section 7.1 of [START_REF] Gärtner | Understanding and using linear programming[END_REF].

In order to prove Theorem 3.9, we will need several lemmas. For all of them, A and B will denote nite sets on which a group G is acting, and x G will denote the orbit of x under G: |(x,y) G | . We have:

f : B x τ → B x τ y → g • y . First, f is well dened. Indeed, if y ∈ B x τ = {y : (x, y) ∈ τ }, then g • y ∈ {y : (g • x, y) ∈ τ } = B x τ , since τ ∈ O G (A × B). Let us show that f is injective. If g • y = g • y , then g -1 • (g • y) = (g -1 g) • y = y, g -1 • (g • y ) = y ,
x∈A v x,y = 1 |y G | τ ∈O G (A×B):τ B =y G v τ , ∀y ∈ B . Proof. x∈A v x,y = τ ∈O G (A×B):τ B =y G x∈A:(x,y)∈τ v x,y = τ ∈O G (A×B):τ B =y G x∈A:(x,y)∈τ v τ |τ | since (x, y) G = τ = τ ∈O G (A×B):τ B =y G c y G τ v τ |τ | by Lemma 3.11, since y ∈ τ B = τ ∈O G (A×B):τ B =y G |τ | |y G | v τ |τ | = 1 |y G | τ ∈O G (A×B):τ B =y G v τ .
τ ∈O G (A×B):τ B =µ v τ = y∈µ x∈A v x,y . Proof. τ ∈O G (A×B):τ B =µ v τ = τ ∈O G (A×B):τ B =µ (x,y)∈τ v x,y = y∈µ x∈A v x,y .
Proof of Theorem 3.9. Let r x 1 ,x 2 ,y , r 1

x 1 ,x 2 ,y , r 2 x 1 ,x 2 ,y , p x 1 ,x 2 a feasible solution of the program dened in Proposition 3.1, and call S := 1

k 1 k 2 x 1 ,x 2 ,y W (y|x 1 x 2 )r x 1 ,x 2 ,
y its value. Dene:

r w := (x 1 ,x 2 ,y)∈w r x 1 ,x 2 ,y , r 1 w := (x 1 ,x 2 ,y)∈w r 1 x 1 ,x 2 ,y , r 2 w := (x 1 ,x 2 ,y)∈w r 2 x 1 ,x 2 ,y , p u := (x 1 ,x 2 )∈u p x 1 ,x 2 . (22)
Let us show that r w , r 1 w , r 2 w , p u is a feasible solution of the program dened in Theorem 3.9, and that its value

S * := 1 k 1 k 2 w W (w)r w = S.
First, we have S * = S. Indeed:

S * = 1 k 1 k 2 w W (w)r w = 1 k 1 k 2 w W (w) (x 1 ,x 2 ,y)∈w r x 1 ,x 2 ,y = 1 k 1 k 2 w (x 1 ,x 2 ,y)∈w W (y|x 1 x 2 )r x 1 ,x 2 ,y since W (w) = W (y|x 1 x 2 ) for all (x 1 , x 2 , y) ∈ w = 1 k 1 k 2 x 1 ,x 2 ,y W (y|x 1 x 2 )r x 1 ,x 2 ,y = S . (23)
Then, all the constraints are satised. Indeed, thanks to Lemma 3.13, we have for the rst constraint:

w:w Y =v r w = y∈v x 1 ,x 2 r x 1 ,x 2 ,y = y∈v 1 = |v| . (24)
For the second constraint (and symmetrically for the third constraint), we have:

w:w X 2 Y =v 2 r 1 w = (x 2 ,y)∈v 2 x 1 r 1 x 1 ,x 2 ,y = (x 2 ,y)∈v 2 k 1 x 1 r x 1 ,x 2 ,y = k 1 w:w X 2 Y =v 2 r w . (25)
For the fourth (and symmetrically for the fth), we have:

w:w X 2 Y =v 2 r 2 w = (x 2 ,y)∈v 2 x 1 r 2 x 1 ,x 2 ,y = (x 2 ,y)∈v 2 1 k 1 x 1 p x 1 ,x 2 = 1 k 1 x 2 ∈v 2 X 2 y:(x 2 ,y)∈v 2 x 1 p x 1 ,x 2 = 1 k 1 x 2 ∈v 2 X 2 |v 2 | |v 2 X 2 | x 1 p x 1 ,x 2 thanks to Lemma 3.11 = 1 k 1 |v 2 | |v 2 X 2 | u:u X 2 =v 2 X 2 p u . (26)
Finally for the last constraints, we only need to compute:

(x 1 ,x 2 ,y)∈w p x 1 ,x 2 = (x 1 ,x 2 )∈w X 1 X 2 y:(x 1 ,x 2 ,y)∈w p x 1 ,x 2 = (x 1 ,x 2 )∈w X 1 X 2 |w| |w X 1 X 2 | p x 1 ,x 2 = |w| |w X 1 X 2 | p w X 1 X 2 , (27)
which implies that the linear inequalities on p x 1 ,x 2 , r x 1 ,x 2 ,y , r 1 x 1 ,x 2 ,y , r 2 x 1 ,x 2 ,y get transposed respectively to the values |w| |w X 1 X 2 | p w X 1 X 2 , r w , r 1 w , r 2 w . Indeed, for instance, one has for any x 1 , x 2 , y that p x 1 ,x 2 -r 1 x 1 ,x 2 ,yr 2

x 1 ,x 2 ,y + r x 1 ,x 2 ,y ≥ 0. Thus for some orbit w:

(x 1 ,x 2 ,y)∈w p x 1 ,x 2 -r 1 x 1 ,x 2 ,y -r 2 x 1 ,x 2 ,y + r x 1 ,x 2 ,y ≥ 0 , and then |w| |w X 1 X 2 | p w X 1 X 2 -r 1 w -r 2 w + r w ≥ 0,
which was what we wanted to show. Now let us consider a feasible solution r w , r 1 w , r 2 w , p u of the program dened in Theorem 3.9, with a value S * := 1 k 1 k 2 w W (w)r w . Dene:

r x 1 ,x 2 ,y := r (x 1 ,x 2 ,y) G |(x 1 , x 2 , y) G | , r 1 x 1 ,x 2 ,y := r 1 (x 1 ,x 2 ,y) G |(x 1 , x 2 , y) G | , r 2 x 1 ,x 2 ,y := r 2 (x 1 ,x 2 ,y) G |(x 1 , x 2 , y) G | , p x 1 ,x 2 := p (x 1 ,x 2 ) G |(x 1 , x 2 ) G | . (28)
Let us show that r x 1 ,x 2 ,y , r 1 x 1 ,x 2 ,y , r 2 x 1 ,x 2 ,y , p x 1 ,x 2 is a feasible solution of the program dened in Propo- sition 3.1, and that its value S := 1

k 1 k 2 x 1 ,x 2 ,y W (y|x 1 x 2 )r x 1 ,x 2 ,y = S * .
First we have S = S * . Indeed:

S = 1 k 1 k 2 x 1 ,x 2 ,y W (y|x 1 x 2 )r x 1 ,x 2 ,y = 1 k 1 k 2 x 1 ,x 2 ,y W (y|x 1 x 2 ) r (x 1 ,x 2 ,y) G |r (x 1 ,x 2 ,y) G | = 1 k 1 k 2 w (x 1 ,x 2 ,y)∈w W (y|x 1 x 2 ) r w |w| = 1 k 1 k 2 w (x 1 ,x 2 ,y)∈w W (w) r w |w| = 1 k 1 k 2 w |w|W (w) r w |w| = 1 k 1 k 2 w W (w)r w = S * . (29)
Then, all the constraints are satised. Indeed, thanks to Lemma 3.12, we have for the rst constraint:

x 1 ,x 2 r x 1 ,x 2 ,y = 1 |y G | w:w Y =y G r w = |y G | |y G | = 1 . (30)
For the second constraint (and symmetrically for the third constraint), we have:

x 1 r 1 x 1 ,x 2 ,y = 1 |(x 2 , y) G | w:w X 2 Y =(x 2 ,y) G r 1 w = k 1 |(x 2 , y) G | w:w X 2 Y =(x 2 ,y) G r w = k 1 x 1 r x 1 ,x 2 ,y . (31)
For the fourth (and symmetrically for the fth), we have:

x 1 r 2 x 1 ,x 2 ,y = 1 |(x 2 , y) G | w:w X 2 Y =(x 2 ,y) G r 2 w = 1 |(x 2 , y) G | 1 k 1 |(x 2 , y) G | |(x 2 , y) G X 2 | u:u X 2 =(x 2 ,y) G X 2 p u = 1 k 1 1 |(x 2 , y) G X 2 | u:u X 2 =(x 2 ,y) G X 2 p u = 1 k 1 1 |x G 2 | u:u X 2 =x G 2 p u since (x 2 , y) G X 2 = x G 2 = 1 k 1 x 1 p x 1 ,x 2 .
(32)

Finally, to conclude with the last constraints, one has only to see that for any x 1 , x 2 , y:

|(x 1 , x 2 , y) G | |(x 1 , x 2 , y) G X 1 X 2 | p (x 1 ,x 2 ,y) G X 1 X 2 = |(x 1 , x 2 , y) G | |(x 1 , x 2 ) G | p (x 1 ,x 2 ) G = |(x 1 , x 2 , y) G |p x 1 ,x 2 , (33)
which implies that the linear inequalities on |w| |w X 1 X 2 | p w X 1 X 2 , r w , r 1 w , r 2 w get transposed respectively to the values p x 1 ,x 2 , r x 1 ,x 2 ,y , r 1

x 1 ,x 2 ,y , r 2 x 1 ,x 2 ,y . Indeed, for instance, one has for any w that

|w| |w X 1 X 2 | p w X 1 X 2 -r 1 w - r 2 w + r w ≥ 0. But for any (x 1 , x 2 , y) ∈ w, one has that r x 1 ,x 2 ,y = rw |w| , r 1 x 1 ,x 2 ,y = r 1 w |w| , r 2 x 1 ,x 2 ,y = r 2 w
|w| . Thanks to the previous inequality, we have that p

x 1 ,x 2 = pw X 1 X 2 |w X 1 X 2 |
, and thus:

p x 1 ,x 2 -r 1 x 1 ,x 2 ,y -r 2 x 1 ,x 2 ,y + r x 1 ,x 2 ,y = p w X 1 X 2 |w X 1 X 2 | - r 1 w |w| - r 2 w |w| + r w |w| ≥ 0 ,
which was what we wanted to show.

Application to the Binary Adder Channel

The binary adder channel W BAC is the following MAC:

∀x 1 , x 2 ∈ {0, 1}, ∀y ∈ {0, 1, 2}, W BAC (y|x 1 x 2 ) := δ y,x 1 +x 2 .
Its classical capacity region C(W BAC ) is well known and consists of all

(R 1 , R 2 ) such that R 1 ≤ 1, R 2 ≤ 1, R 1 + R 2 ≤ 3
2 , as a consequence of Theorem 1.1. Its zero-error classical capacity C 0 (W BAC )

is not yet characterized. A lot of work has been done in nding upper and lower bounds on this region [START_REF] Lindström | Determination of two vectors from the sum[END_REF][START_REF] Henk | An upper bound for codes in a two-access binary erasure channel (Corresp.)[END_REF][START_REF] Kasami | Bounds on the achievable rates of block coding for a memoryless multipleaccess channel[END_REF][START_REF] Weldon | Coding for a multiple-access channel[END_REF][START_REF] Kasami | Graph theoretic approaches to the code construction for the two-user multiple-access binary adder channel[END_REF][START_REF] Coebergh Van Den Braak | A family of good uniquely decodable code pairs for the two-access binary adder channel[END_REF][START_REF] Shraga | Upper bound for uniquely decodable codes in a binary input N-user adder channel[END_REF][START_REF] Urbanke | The zero-error capacity region of the 2-user synchronous BAC is strictly smaller than its Shannon capacity region[END_REF][START_REF] Ahlswede | Construction of uniquely decodable codes for the twouser binary adder channel[END_REF][START_REF] Mattas | A new bound for the zero-error capacity region of the twouser binary adder channel[END_REF][START_REF] Ordentlich | A VC-dimension-based outer bound on the zero-error capacity of the binary adder channel[END_REF]. To date, the best lower bound on the sum-rate capacity is log 2 (240/6) 1.3178 [START_REF] Mattas | A new bound for the zero-error capacity region of the twouser binary adder channel[END_REF]. Thanks to Corollary 3.10, we were able to compute all the values of S NS (W n BAC , k 1 , k 2 ) up to n = 6. In particular, taking the largest k 1 , k 2 where S NS (W n BAC , k 1 , k 2 ) = 1 gave us lower bounds on the zero-error non-signaling assisted capacity region C NS 0 (W BAC ). Finally, for n = 7, we were able to compute directly the border of the zero-error non-signaling assisted capacity region, which led to Figure 3. The code can be found on GitHub. It uses Mosek linear programming solver [START_REF] Erling | The Mosek interior point optimizer for linear programming: an implementation of the homogeneous algorithm[END_REF].

Note that the linear program from Theorem 3.9 has still a large number of variables and constraints although polynomial in n. Specically, for n = 2, it has 244 variables and 480 constraints; for n = 3, it has 1112 variables and 2054 constraints; for n = 7, it has 95592 variables and 162324 constraints; nally, for n = 8, it has 226911 variables and 383103 constraints.

The rst noticeable result coming from these curves is that the zero-error non-signaling assisted sumrate capacity beats with only 7 copies the classical sum-rate capacity of

Classical Capacity Region

Best ZE Lower Bounds [START_REF] Mattas | A new bound for the zero-error capacity region of the twouser binary adder channel[END_REF][START_REF] Coebergh Van Den Braak | A family of good uniquely decodable code pairs for the two-access binary adder channel[END_REF][START_REF] Kasami | Graph theoretic approaches to the code construction for the two-user multiple-access binary adder channel[END_REF] NS ZE Capacity Region for 2 copies NS ZE Capacity Region for 3 copies NS ZE Capacity Region for 7 copies Figure 3: Capacity regions of the binary adder channel W BAC . The black dashed curve depicts the classical capacity region C(W BAC ), whereas the grey dashed curve shows the best known lower bound border on the zero-error classical capacity region C 0 (W BAC ), made from results by [17, 23, 13]; see [17] for a description of this border. On the other hand, the continuous curves depict the best zero-error non-signaling assisted achievable rate pairs for respectively 2, 3 and 7 copies of the binary adder channel. constraint, with a value of 2 log 2 (42) 7

1.5406, coming from the fact that S NS (W ⊗7 BAC , 42, 42) = 1 and Proposition 3.7. This implies that C NS 0 (W BAC ) has larger sum-rate pairs than C(W BAC ), and that C NS (W BAC ) is strictly larger than C(W BAC ). This sum-rate can even be increased up to log 2 (72) 4 1.5425, since we have computed S NS (W ⊗8 BAC , 72, 72) = 1, which is the largest number of copies we have been able to manage with our ecient version of the linear program from Theorem 3.9. This should be compared with the only upper bound known on the non-signaling assisted sum-rate coming from Corollary 3.6 and given by log 2 (|Y|) = log 2 (3) 1.5850.

Another astonishing result is the speed at which one obtains ecient zero-error non-signaling assisted codes compared to classical zero-error codes. Indeed, with only three copies of the binary adder channel, one gets that S NS (W ⊗3 BAC , 4, 5) = 1, which corresponds to a sum-rate of 2+log 2 (5) 3 1.4406, which already largely beats the best known zero-error achieved sum-rate of log 2 (240/6) 1.3178 [START_REF] Mattas | A new bound for the zero-error capacity region of the twouser binary adder channel[END_REF]. These results are summarized in the following theorem: Theorem 4.1. We have that log

Handling Errors with Concatenated Codes

In Section 4, we have analyzed the non-signaling assisted capacity region through zero-error strategies in the case of the BAC, which is in particular deterministic. However, if some noise is added to that channel, its zero-error non-signaling assisted capacity region becomes trivial (see Proposition 5.3). Thus, the previous method fails to nd signicant lower bounds on the non-signaling assisted capacity region of noisy MACs.

In this section, we will present a new technique to overcome this diculty using concatenated codes, and apply it to a noisy version of the BAC.

Concatenated Codes

Given a MAC W and a non-signaling code P , dene

W [P ] : [k 1 ] × [k 2 ] → [ ] with W [P ](j|i 1 i 2 ) := x 1 ,x 2 ,y W (y|x 1 x 2 )P (x 1 x 2 j|i 1 i 2 y): P (x 1 x 2 j|i 1 i 2 y) i 1 i 2 j W x 1 x 2 y := W [P ] i 1 i 2 j Note that W [P ] is a MAC since W [P ](j|i 1 i 2 ) ≥ 0 and: j W [P ](j|i 1 i 2 ) = x 1 ,x 2 ,y W (y|x 1 x 2 ) j P (x 1 x 2 j|i 1 i 2 y) = x 1 ,x 2 y W (y|x 1 x 2 ) P (x 1 x 2 |i 1 i 2 ) since P is non-signaling = x 1 ,x 2 P (x 1 x 2 |i 1 i 2 ) = 1 .
The following proposition states that combining a classical code to a non-signaling strategy leads to lower bounds on the non-signaling assisted capacity region of a MAC: Proposition 5.1. If P is a non-signaling code for the MAC W , we have that C(W

[P ]) ⊆ C NS (W ). Proof. Let (R 1 , R 2 ) ∈ C(W [P ]
). Then, by denition, we have that:

lim n→+∞ S(W [P ] ⊗n , 2 R 1 n , 2 R 2 n ) = 1 .
Let us x ε > 0. There exists some rank N such that S(W

[P ] ⊗N , 2 R 1 N , 2 R 2 N ) ≥ 1 -ε. Let us call 1 := 2 R 1 N and 2 := 2 R 2 N . Thus, there exists encoders e 1 : [ 1 ] → [k 1 ], e 2 : [ 2 ] → [k 2 ] and a decoder d : [ ] → [ 1 ] × [ 2 ] such that: 1 1 2 i 1 ,i 2 ,j W [P ](j|i 1 i 2 ) a 1 ∈[ 1 ],a 2 ∈[ 2 ] e 1 (i 1 |a 1 )e 2 (i 2 |a 2 )d(a 1 a 2 |j) ≥ 1 -ε .
which implies the previous statement. But, for W ⊗n BAC,ε 1 ,ε 2 , one can easily check that for all y n , x n 1 , x n 2 , W ⊗n (y n |x n 1 x n 2 ) > 0 since ε 1 , ε 2 ∈ (0, 1). Indeed, you just have to ip the inputs to a valid preimage of the output. Thus if S N S (W ⊗n BAC,ε 1 ,ε 2 , k 1 , k 2 ) = 1, we have that ∀y n , x n 1 , x n 2 , r x n 1 ,x n 2 ,y n = p x n 1 ,x n 2 . In particular, this implies that

x n 1 ,x n 2 r x n 1 ,x n 2 ,y n = x n 1 ,x n 2 p x n 1 ,x n
2 , therefore 1 = k 1 k 2 , so k 1 = 1 and k 2 = 1. Thus S N S (W ⊗n , 2 nR 1 , 2 nR 2 ) = 1 implies that (R 1 , R 2 ) = (0, 0).

We have then applied the numerical method described in Proposition 5.2 to W BAC,ε 1 ,ε 2 for the sym- metric case ε 1 = ε 2 = ε := 10 -3 . Since it is hard to go through all non-signaling codes P and product distributions q 1 , q 2 , we have applied the heuristic of using non-signaling codes obtained while optimizing S NS (W ⊗n , k 1 , k 2 ) in the symmetrized linear program. We have combined them with uniform q 1 , q 2 , as the form of those non-signaling codes coming from our optimization program is symmetric. We have evaluated the achievable corner points for all k 1 , k 2 ≤ 2 n for n ≤ 5 copies which led to Figure 4 The red point depicts the zero-error non-signaling assisted capacity region (Proposition 5.3). The blue curve depicts achievable non-signaling rates pairs obtained from C(W ⊗5 BAC,ε,ε [P ]) through the numerical method described in Proposition 5.2.

Compared to the noiseless BAC, we can rst notice that the classical capacity region is slightly smaller, with a classical sum-rate capacity of 1.478 at most. On the other hand, although the zero-error nonsignaling assisted capacity of W BAC,ε,ε is completely trivial, we have with our concatenated codes strategy found signicant rate pairs achievable with non-signaling assistance. In particular, we have reached a non-signaling assisted sum-rate capacity of 1.493 which beats the best classical sum-rate capacity. Thus, it shows that non-signaling assistance can improve the capacity of the noisy binary adder channel as well.

Conclusion

In this work, we have studied the impact of non-signaling assistance on the capacity of multiple-access channels. We have developed an ecient linear program computing the success probability of the best non-signaling assisted code for a nite number of copies of a multiple-access channel. In particular, this gives lower bounds on the zero-error non-signaling assisted capacity of multiple-access channels. Applied to the binary adder channel, these results were used to prove that a sum-rate of log 2 (72) 4

1.5425 can be reached with zero error, which beats the maximum classical sum-rate capacity of 3 2 . For noisy channels, we have developed a technique giving lower bounds through the use of concatenated codes. Applied to the noisy binary adder channel, this technique was used to show that non-signaling assistance still improves the sum-rate capacity.

Our results suggest that quantum entanglement may also increase the capacity of such channels. However, even for the binary adder channel, this question remains open. One could also ask if such ecient methods to compute the best non-signaling assisted codes can be extended to Gaussian multipleaccess channels. Finally, the existence of a single-letter formula for the non-signaling assisted capacity of multiple-access channels remains open, even for the binary adder channel. An intriguing question is whether the non-signaling assisted capacity of multiple access channels is given by the same expression as in Theorem 1.1 and dropping the requirement that X 1 and X 2 are independent.

  and then decode these messages from the output in Y with d : Y → [k 1 ] × [k 2 ], as depicted in Figure 2.1. This leads to the following optimization program for S(W, k 1 , k 2 ):

Lemma 3 . 11 .

 311 Let τ ∈ O G (A × B), and call ν := τ A and µ := τ B . For x ∈ ν, let us call B x τ := {y : (x, y) ∈ τ }. Then, |B x τ | = |B x τ | =: c ν τ for any x, x ∈ ν, and furthermore, we have that c ν τ = |τ | |ν| . Symmetrically, the same occurs for A y τ := {x : (x, y) ∈ τ } with y ∈ µ, where one gets that |A y τ | = |A y τ | =: c µ τ = |τ | |µ| for y, y ∈ µ. Proof. Let x, x ∈ ν. Thus there exists g ∈ G such that x = g • x. Let:

  so y = y . Thus we get that |B x τ | ≤ |B x τ |. By a symmetric argument with x replacing x and g -1 replacing g, we get that |B x τ | ≤ |B x τ |, and so |B x τ | = |B x τ | =: c ν τ . Furthermore, {B x τ } x∈ν is a partition of τ , so x∈ν |B x τ | = |ν|c ν τ = |τ |, and thus c ν τ = |τ | |ν| . Lemma 3.12. For any (x, y) ∈ A × B and v (x,y) G variable indexed by orbits of A × B, let us dene the variable v x,y := v (x,y) G

( 21 )

 21 Lemma 3.13. For any τ ∈ O G (A × B), µ ∈ O G (B) and v x,y variable indexed by elements of A × B, let us dene v τ := (x,y)∈τ v x,y . We have:

Figure 4 :

 4 Figure 4: Capacity regions of the noisy binary adder channel W BAC,ε,ε for ε = 10 -3 . The black dashed curve depicts the classical capacity region C(W BAC,ε,ε ) which was found numerically using Theorem 1.1.

  One can prove an equivalent formulation of the linear program computing S NS (W, k 1 , k 2 ) with a number of variables and constraints polynomial in only |X 1 |, |X 2 | and |Y| and independent of k 1 and k 2 : Proposition 3.1. For a MAC W : X 1 × X 2 → Y and k 1 , k 2 ∈ N * , we have:

	3	Basic Properties and Computational Aspects of Non-Signaling As-
		sisted Codes for MACs
	3.1	A Smaller Linear Program Computing S NS (W, k 1 , k 2 )

  is not achievable with non-signaling assistance. Symmetrically, R 2 > log 2 |X 2 | is not achievable with non-signaling assistance. Furthermore, if one takes R 1 +R 2 > log 2 |Y|, then in particular k 1 k 2 > |Y|, so by the second property of Proposition 3.5, S NS (W ⊗n

  log 2 |Y| is not achievable with non-signaling assistance.3. Since (R 1 , R 2 ) is achievable with non-signaling assistance, we have S NS (W ⊗n , 2 nR 1 , 2 nR 2 ) → But, for all positive integer n, we have that 2 nR 1 ≤ 2 nR 1 and 2 nR 2 ≤ 2 nR 2 , so by the third property of Proposition 3.5, we have that S NS (W ⊗n ,2 nR 1 , 2 nR 2 ) ≥ S NS (W ⊗n , 2 nR 1 , 2 nR 2 ). Thus S NS (W ⊗n , 2 nR 1 , 2 nR 2 → n→+∞ 1since it is upper bounded by 1, and so (R 1 , R 2 ) is achievable with non-signaling assistance.

n→+∞ 1. Proposition 3.7. C NS 0 (W ) is the closure of the set of rate pairs (R 1 , R 2 ) such that:

  BAC ) C NS (W BAC ).

			2 (72) 8	, log 2 (72) 8	∈ C NS 0 (W BAC ) but log 2 (72) 8	, log 2 (72) 8	∈ C(W BAC ), and as
	a consequence, we have that C(W Proof. Since 2 8 log 2 (72)
	log 2 (72) 8	, log 2 (72) 8	∈ C NS 0 (W BAC ) by Proposition 3.7. However, log 2 (72) 8	+ log 2 (72) 8	> 3 2 so	log 2 (72) 8	, log 2 (72) 8	∈
	C(W

8

= 72 and numerically S NS (W ⊗8 BAC , 72, 72) = 1 thanks to Corollary 3.10, we get that BAC ) by Theorem 1.1 applied to W BAC . Since C(W BAC ) ⊆ C NS (W BAC ) and C NS 0 (W BAC ) ⊆ C NS (W BAC ), we thus get that C(W BAC ) C NS (W BAC ).

Acknowledgements

We would like to thank Mario Berta and Andreas Winter for discussions about the use of non-signaling correlations for multiple access channels. This work is funded by the European Research Council (ERC Grant Agreement No. 851716).

In particular, we have:

Then, one can easily check that P is non-signaling, and thus:

This implies that lim

Thanks to Proposition 5.1, we have for any non-signaling code P , C(W

. Thus, applying Theorem 1.1 on W ⊗n [P ] leads to lower bounds on C NS (W ): Proposition 5.2 (Numerical Method to nd lower bounds on C NS (W )). For any number of copies n,

following the product law q 1 × q 2 , and J ∈ [ ] the outcome of W ⊗n [P ] on inputs I 1 , I 2 . In particular, the corner points of this capacity region are given by: I(I 1 : J|I 2 ) n , I(I 2 : J) n and I(I 1 : J) n , I(I 2 : J|I 1 ) n .

Application to the Noisy Binary Adder Channel

We will now apply this strategy to a noisy version of the BAC. We will consider ip errors ε 1 , ε 2 of inputs

x 1 , x 2 on W BAC , which leads to the following denition of W BAC,ε 1 ,ε 2 :

First, let us note that the zero-error non-signaling assisted capacity region of W BAC,ε 1 ,ε 2 is trivial, which won't help us to understand C NS (W BAC,ε 1 ,ε 2 ):

2 . Indeed, we have for an optimal p, r that:


Denis Marion
email: denis.marion@u-bordeaux.fr

Philippe Balcou

Christophe Féral

Antoine Rohm

AND Jérôme Lhermite

Index-leveling for forced-flow turbulent face-cooling of laser amplifiers

Direct laser slab face-cooling by a fluid crossing the main and pump laser beams is an important method to reach high average laser powers. However, the flow regime is usually maintained at low Reynolds numbers, to prevent the onset of turbulence features in the flow, that would degrade wavefront quality. We show here how bringing the fluid temperature to the thermooptical null point, close to the water/ice transition in the case of water, allows one to mitigate the optical consequences of hydrodynamic instabilities, by bleaching optically the temperature inhomogeneities within the flow. This optical process, dubbed index-leveling, opens the door to a highly efficient forced-flow, weakly turbulent face-cooling regime that should be instrumental to boost the kilowatt capabilities of next generation highpower lasers.

http://dx.doi.org/10.1364/ao.XX.XXXXXX Average powers of research-class lasers, such as used in ultra-high intensity laser matter interactions, have increased steadily in the last few years, thanks to few key technologies, such as Large Mode Fibers [1], thin disk technologies [2], and cryogenic helium cooling [3], leading however to severe problems of thermal management. Indeed, a large fraction of the power deposited by pump lasers is downgraded into heat [4], which has to be efficiently removed, otherwise the laser medium heats up, thus reducing amplification, and inducing potentially catastrophic internal stress leading to wavefront deformation, birefringence, and ultimately medium breakdown.

An efficient cooling method makes use of a cooling liquid that flows directly onto the surface of the amplifier slab to extract the heat [5,6]. In this scheme the coolant is crossed by the pump laser beams and by the amplified laser, leading to concerns for the wavefront quality after propagation through a liquid that is subject to complex hydrodynamic and thermal processes.

Different cooling liquids have been proposed, such as heavy water [7], organic solvents and special oils; however de-ionized water remains the most common coolant, thanks to the ease of use, low price and large thermal capacity of water. Many studies have also been devoted to the hydrodynamics of water under thermal charges, or optical transmission in turbulent media [8,9], allowing the laser physicist to benefit from decades-long insights by physicists of fluid mechanics. In the usual case of no external heat input, the flow is known to occur in either the laminar regime, with smooth thermo-and hydrodynamic fields, or in the turbulent regime. Transition between laminar and turbulent regimes occurs when the dimensionless Reynolds number Re, whose significance will be recalled in the following, reaches values of the order of 2300. The regularity and homogeneity of low-Re flows allow one to cool with negligible wavefront distortions, but those exhibit low heat exchange coefficients with the slab. Flows with higher Re are in a transition, or weak turbulence regime, up to Re = 10000 where strong turbulence sets in. High-Re flows display higher exchange coefficients, but when a turbulent fluid is in contact with a heating surface, unstable fluid elements with different temperatures appear randomly, leading to inhomogeneities in temperatures and hence in optical indices n, through the thermo-optical coefficient dn dT , leading to significant scattering, strong wavefront distortions, and ultimately poor Strehl ratios and low focused intensities.

In this letter, we show experimentally how bringing the temperature of a weakly turbulent cooling liquid close to a point for which dn dT ≃ 0, may result in the strong mitigation of turbulenceinduced scattering thanks to index-leveling. We discuss the potential to optimize the laser beam quality, or to push further the technological limits on high average-powers lasers.

Fig. 1. a) Liquid face cooling of a high power laser slab in a transmission geometry. b) Reflective ("active mirror") geometry used in the setup for analysis of wavefront perturbations. Fig. 1 presents typical face-cooling mounts of a laser amplifier slab, in a straight configuration (a), and in a reflective configuration, such as used for "active mirrors" or thin-disks (b). The coolant is sent into the head with a fixed overpressure given by an external hydraulic system. It is separated into two or more thin layers over the faces of the slab structure, which may be in a single slab or multi-slab configuration. The coolant canals therefore lie between an optical window and the slab, or between two slabs, with a separation d and a transverse dimension D usually exceeding the slab width. The coolant temperature is usually set above the condensation temperature of the room [10].

The turbulence regime in each canal is specified by Re = U b δ ν , where U b is the mean coolant velocity, measured as the ratio of flow rate to canal area, ν its kinematic viscosity, and δ the hydraulic diameter for each canal, defined as four times the ratio between area and wet perimeters: δ = 2 • dD/(d + D).

Our new approach mitigates wavefront deformations by operating the coolant close to a null thermo-optical point and at a high-Re transition regime. This concept stems from the progress in the understanding of free space optical beam communications, namely scintillation phenomena and loss of resolution power [11]. In complex transparent media, a laser beam goes through inhomogeneities of optical index, that, to first order, depend linearly on the local temperature and pressure:

n(T, P) = n 0 + dn dT dT + dn dP dP. (1)
The pressure profile in the coolant flow is dominated by the constant hydrostatic pressure variation due to the external hydraulic system, along the flow direction, leading to a small and constant optical prismaticity effect due to the dn dP term. However, in each transverse plane, the pressure can be assumed constant in very good approximation [12], as all velocities within the flow are extremely small with respect to the sound velocity. This leaves T as the essential thermodynamic variable whose spatial fluctuations affect the optical index [8]. In a turbulent regime, the stochastic index inhomogeneities were shown to induce an average spectrum Φ n of spatial frequencies κ after propagation, that presents the following dependence for κ larger than λ -1 , where λ is the laser wavelength:

Φ n ≈ 0.23 C 2 n η 2/3 κ -3 , ( 2
)
where η is the Kolmogorov scale, and C n the so-called structure parameter of n in the flow, dependent on |dn/dT| and on the stochastic average of the temperature gradient ⟨∇T⟩ [8, 13]. |dn/dT| thus appears as the key figure controlling the optical effects of turbulence. Fig. 2 illustrates the state of knowledge on the temperature dependence of the dn/dT coefficient of pure water and of D 2 O. The inset shows the behavior of the optical index of water, with a paraboloid shape around a temperature of index maximum T IM (data from [14]). The index presents a maximum around the melting point at ambient pressure. The main figure displays the fits for -dn/dT from selected studies: We have chosen the reflective configuration of Fig. 1(b) to test this proposal, and evaluate the extent to which temperature control around a null thermo-optical point allows one to mitigate wavefront corrugation. Fig. 3 shows the experimental setup. Thanks to the reflective configuration, we could replace the hot laser crystal by a metallic mirror M heated from the back by an electrical resistance H, allowing us to tune the thermal power to extract, and hence the temperature difference between the optical surface and the incoming water coolant. The latter enters the mock-up amplifier head from the top, goes first into a 10-cm long turbulence decay section, then enters a 3-mm thick canal between the entrance window, and the mirror surface. The flow follows a vertical top-down axis. The mirror itself is made of copper, with a high thermal conductivity ensuring an uniform temperature, and is layered with gold for good IR reflectivity. The electric power dissipated by H was regulated at 150 W.

The water circulation is operated by an external hydraulic system comprising an hydraulic pump with adjustable overpressure, and a thermally isolated tank. The water temperature is fixed by a thermostat between 0 °C and 20 °C. Indeed, as stated above, T IM lies close to the water's melting point. This thermodynamic coincidence makes the water thermostat technically challenging. To cool down the water very close to 0 °C, we spilled ice chips directly in the water tank, letting it operate as a dual phase mixture, with the ice floating in the upper part, and the water derivation taken from the bottom of the tank. The water temperature was measured in the tank by the sensor T1, and at the entrance and exit ports of the head by resp. T2 and T3, with a typical difference of 0.3 °C in the conditions of Fig. 4. Sensor T4 was embedded in the copper close to M to monitor its temperature. All sensors (DS18B20) have a sensitivity of 0.06 °C. Temperatures below 10 °C usually induce condensation on the optical surfaces. We solved this issue by adding a transparent chamber (not shown) in front of the window, filled with dry air and dessicant.

A high spatial quality fiber laser was used to perform the optical qualification of the setup, displayed in the lower-right part of Fig. 3. We used a 10-mW source obtained by putting a 1-m Yb:glass active fiber in ring-cavity configuration, operating it as a spectrally-multimode laser centered at λ = 1030 nm. The initially diverging beam is first collimated with a full width at half maximum of 1 cm and later impinges on the mock-up laser head after going through a beam splitter BS. As a result, the laser beam goes back and forth through the entrance window and the coolant flow. On its way back, the beam is deflected by BS to an optical characterization setup, and split by the beam splitter BS1 into two optical imaging lines for the far-and near-fields.

In the latter, the laser profile at the mirror position is imaged onto the charge-coupled device camera CCD1 by means of a lens L1 with focal length f 1 = 50 cm. A needle N is inserted at the intermediate focus between L1 and CCD1. This gives a direct strioscopic image of index inhomogeneities near the mirror M.

The second beamline uses L2 (focal length f 2 = 30 cm) to obtain a far-field profile at its focus, positioned at the object plane of the objective of CCD2, with the needle N removed. The light scintillation induced by the turbulent fluid will translate into photons arriving in the focal plane away from the central laser spot, generating a wide spatial pedestal on the image. Fig. 4 shows a series of strioscopic near-field images (upper pictures), and of far-field high dynamic, logarithmic-scale images (lower pictures), taken at coolant temperatures of 1 °C, 5 °C, 10 °C, 15 °C and 20 °C (a to e), along with a set of reference images taken without heat load at 15 °C. The hydrodynamic and thermal conditions were actively controlled to be identical for all temperatures, with Re = 4500 and a temperature difference of 17 °C between the mirror (sensor T4) and the coolant (sensor T2). This required to adjust finely the flow rate to account for the temperature dependence of the kinematic viscosity. In such conditions, the turbulence regime was deemed identical for all data sets.

The near-field images show that the flow instabilities arise as a series of narrow threads, directed along the flow direction, and appearing randomly. Somehow similar features can be noticed in [19]. Our pattern is much more regular in shape, possibly due to the geometry of the water canal, starting high above the mirror, bound to lead to a strictly parallel flow. The laser scatters off these turbulence threads, leading to bright areas in strioscopic imaging. The diffraction pattern is thus bound to present a preferential direction orthogonal to the threads' axis, namely, along the horizontal direction. This is indeed what is observed on the far-field log-scale images, with the appearance of comet-like horizontal features, superposed to the constant spatial pedestal of the beam, mainly due to surface irregularities of the metallic mirror. Lengths and widths of the bright turbulence threads are similar throughout the series. Only their intensities fade away when the temperature approaches the thermo-optical null point, showing an almost complete optical bleaching of the turbulence structures. These qualitative considerations can be made quantitative by an analysis of the far-field data. In our numerical procedure [20], we plot the energy profile of the far-field image in each polar direction, starting from the center of the focal spot, as shown in the inset of Fig. 5. In logarithmic scale, the obtained curve displays a parabolic shape for small radii, characteristic of a Gaussian beam. The integral of the image intensity in this area provides the energy within the main focal spot. The curve at larger radii departs strongly from a parabola, indicating the onset of the beam spatial pedestal that can be spatially integrated. Defining the polar contrast C as the ratio between pedestal energy (blue shading) and main beam energy (pink shading) in each angular sector [θ, θ + dθ] of the far-field profile, we can plot the polar distribution of the spatial contrast C(θ) as a function of water temperature, thus yielding a fully quantitative determination of the energy scattered off the beam, as shown in the polar plots of Fig. 5. For example, C = 1 means that half of the beam energy is lost in the pedestal, whereas C = 0 characterizes a quasi-Gaussian beam with only low-order aberrations.

The polar plots show essentially constant profiles in the up and down directions, due to the intrinsic beam defects; plus sharp spikes, especially visible at 15 °C and 20 °C. In contrast, polar plots obtained at 1 °C and 5 °C are almost superposable. ratios are simply constant; lateral contrast ratios exhibit quasilinear increases. The dashed curves are numerical regressions of the form C = α + β dn dT (T), with dn dT (T) following the formula derived in [17] (cf. Fig. 2). The improvement of C(θ) appears spectacular at 0°and 180°. C 180 is eg. decreased by a factor 7 between 20 °C and 1 °C, a value limited by the pre-existing static spatial pedestal visible on CCD2 without heating (cf. Fig. 4, top left set).

In usual geometries, the heat transfer coefficient scales as Re 0.5 in the laminar regime [21] and Re 0.8 in the turbulent regime [10]. While Re in the literature rarely exceeds 1100 for immersed amplifiers [19] to maintain an acceptable beam quality, the present study demonstrates the optical viability of the indexleveling method at least up to Re = 4500, that should hence lead to a several-fold mitigation of the temperature rise in face-cooled optics. Larger Re values should be investigated in the future.

Our simple setup already dissipates 150 W on a 1-inch single surface. To put this cooling capacity in perspective, we may take the example of a Yb:YAG triple-slab amplifier in a straight geometry [6], pumped at its zero-phonon line (λ = 970 nm). A power of 6 × 150 W = 900 W represents the local, non-radiative losses associated to the quantum defect of the 1030-nm emission line of Yb 3+ when pumped at a power level of 15 kW. With a typical efficiency of 15% in pulsed mode, such an amplifier may output a power level of 2300 W. This simple evaluation shows the potential of the method to boost the average power of intense lasers beyond the kilowatt, provided the issues of condensation and chiller design can be dealt with at that scale. However, as hinted by Fig. 2, using D 2 O at 7 °C would be very helpful on these issues, even if costly, with the additional benefit of reduced laser and pump absorption, as its extinction length is about ten times higher than that of H 2 O in the near-IR range.

The heat exchange capacity demonstrated here appears already superior to room-temperature He gas cooling [22]. Further studies are required to evaluate the advantages and drawbacks of index-leveling with respect to other technologies such as thin disks and cryogenic gas cooling [23]. Its potential should in particular be investigated for large laser slabs used in frontier kilojoule high-repetition lasers, such as the ELI Beamlines [24].

In conclusion, the proposed index-leveling method using a null thermo-optic point allows to operate face-cooled laser amplifiers in a new high-Re, weakly turbulent regime, thus enabling stronger exchange coefficients more efficient cooling. In such conditions, the beam scattering over the turbulence threads is effectively suppressed, as the optical index becomes independent of local temperatures to first order. As such, the method may help to simplify the design of high average-power amplifier heads, and ultimately open up a host of new laser applications from satellite deorbitation to medical X-ray generation.

Fig. 2 .

 2 Fig. 2. Optical index n (inset) and thermo-optical coefficient dn dT of H 2 O and D 2 O as measured by several authors.

Fig. 3 .

 3 Fig. 3. Experimental setup used for the optical characterization of turbulence-induced wavefront perturbations.

Fig. 4 .

 4 Fig. 4. For each set: strioscopic near-field (up), logarithm of far-field profiles (down) at Re = 4500. Top left: without heating, a to e: 150 W heating, water temperature 1 to 20 °C.

Fig. 5 .

 5 Fig. 5. Inset: graphical definition of the polar energy contrast ratio C. Polar plot: distributions of C(θ) for temperatures increasing from 1 °C to 20 °C.

Fig. 6

 6 shows the values of C for the cardinal directions θ = 0°(circles), θ = ±90°((left and right pointing arrows), and θ ≃ 180°(crosses, along the light tail). Up and down contrast

Fig. 6 .

 6 Fig. 6. Temperature dependence of C(θ) at cardinal directions.

  Hawkes et al. [HA 15], Saubade [Sa 14], Abbate et al. [Ab 16], and the approximation formula for the H 2 O index of Bashkatov and Gelina [BG 17]. The water's T IM lies in the range [-3, +2] • C depending on studies; the necessary use of overfusion water for these measurements is indeed delicate, explaining minor discrepancies in the literature. The dependence in λ appears negligible between the visible and near-infrared ranges. The T IM of D 2 O is located around 7 °C [Ab2 18].

Acknowledgments. This work is part of the LEAP project, supported by Région Aquitaine (contract 16005645), European Structural Funds (contract 2779610), Université de Bordeaux and CNRS. Discussions with D. Descamps and J.-P. Hulin are gratefully acknowledged.

Data availability. Data presented in this letter are not publicly available at this time but may be obtained upon reasonable request.

Disclosures.

The authors declare no conflict of interest.