Sankhanil Dey

Ranjan Ghosh
email: rghosh47@yahoo.co.in

4, 8, 32, 64 bit Substitution Box generation using Irreducible or Reducible Polynomials over Galois Field GF(p q )

Keywords: Substitution Boxes, Irreducible Polynomials, Galois Fields, Finite Fields

Substitution Box or S-Box had been generated using 4-bit Boolean Functions (BFs) for Encryption and Decryption Algorithm of Lucifer and Data Encryption Standard (DES) in late sixties and late seventies respectively. The S-Box of Advance Encryption Standard have also been generated using Irreducible Polynomials over Galois field GF(2 8 ) adding an additive constant in early twenty first century. In this paper Substitution Boxes have been generated from Irreducible or Reducible Polynomials over Galois field GF(p q ). Binary Galois fields have been used to generate Substitution Boxes. Since the Galois Field Number or the Number generated from coefficients of a polynomial over a particular Binary Galois field (2 q ) is similar to log 2 q+1 bit BFs. So generation of log 2 q+1 bit S-Boxes is Possible. Now if p = prime or non-prime number then generation of S-Boxes is possible using Galois field GF (p q ). where, q = p-1. 1.

Introduction. Polynomials over Finite field or Galois field GF(p q ) have been of utmost importance in Public Key Cryptography [1]. The polynomials over Finite field or Galois field GF(p q ) that cannot be factored into polynomials with less degree of d and q-d where d ={1,2,…..,(q-1)/2} have been termed as Irreducible polynomials over Finite field or Galois field GF(p q ) and the rest have been termed as Reducible polynomials over Finite field or Galois field GF(p q ) [2]. The polynomials over Galois field GF(p q ) with coefficient of the highest degree term as 1 have been termed as Monic polynomials Galois field GF(p q )and rest have been termed as Non-monic Polynomials Galois field GF(p q ) [3]. The polynomials Galois field GF(p q ) with degree q have been termed as Basic Polynomials or BPs over Galois field GF(p q ) and Polynomials with degree q-1 have been termed as Elemental Polynomials or EPs over Galois field GF(p q ) [4].

q bit proper Substitution box or S-Box have 2 q elements in an array where each element is unique and distinct and arranged in a random fashion varies from 0 to q. Polynomials over Galois field GF(p q ) have been termed as binary polynomials if p = 2. The binary number constructed with q = 0 at LSB and q = q at MSB has been termed as binary Coefficient Number or BCN of log 2 q+1 bits. The Binary Coefficient Number or BCN over Galois field GF(p q ) has been similar with log 2 q+1 bit BFs. The log 2 q+1 bit S-Boxes have been generated using log 2 q+1 bit BCNs.

In this paper proper 4, 5, 6, 7, and 8 bit S-Boxes have been generated using BCNs and the procure has been continued as a future scope to generate 16 and 32 bit S-Boxes. The non-repeated Coefficients of BPs over Galois field GF(p q ), where P = 2 (log 2 q+1) and q = p-1 have been used to generate log 2 q+1 bit S-Boxes. In this paper proper 4, 5, 6, 7, and 8 bit S-Boxes have been generated using BCNs and the procure has been continued as a future scope to generate 16 and 32 bit S-Boxes.

In this paper Polynomials over Galois field GF(p q ) and Substitution Boxes have been reviewed in section.2. The generation of 4 and 8 bit S-Boxes using BCNs have been elaborated in section 3. The generation of S-Boxes of 4 and 8 bit using Coefficients of Non-binary Galois Field Polynomials have been depicted in section 4. Conclusion, Acknowledgement and Reference has been given in section 5, 6 and 7.

2. Polynomials over Galois field GF(p q ) and log 2 q+1 bit S-Boxes. In this section the sub section 2.1. has been devoted to a small review of Polynomials. The sub section 2.2. has been of Utmost importance since in it A four bit bijective Crypto or Proper S-Box has been defined in brief. At last in sub section 2.3. The equation among 2 15 Galois field Polynomials and a 4-bit Bijective Crypto S-Box has been elaborated in details.

Polynomials over Galois field GF(p q

). Polynomials over Galois field GF(p q ) have been of utmost importance in Cryptographic Applications. Polynomials with degree q have been termed as Basic Polynomials and Polynomials with degree less than q have been termed as Elemental Polynomials over Galois field GF(p q ). Polynomials with leading coefficient as 1 have been termed as Monic Polynomials irrespective of BPs and EPs. An example, of the said criteria have been described as follows, the Example of Basic Polynomial or BP over Galois field GF(p q ) has been given below, BP(x) = co q x q + co q-1 x q-1 + co q-1 x q-2 +…………………….+ co 2 x 2 + co 1 x 1 + a 0 ………………………………(i) In equation (i) BP(x) has been represented as Basic Polynomial over Galois field GF(p q )since the highest degree term of the said Polynomial over Galois field GF(p q ) is €q. The BP has been called as a Monic BP if co q = 1. The number of Terms in a BP over Galois field GF(p q ) has been 0 to q i.e. (q+1). The number of possible values of a particular coefficient co q, where 0≤q≤q has been from 0 to p i.e. € (p+1). If the value of q has been ˂q then The Polynomial over Galois field GF(p q ) has been termed as Elemental Polynomial over Galois field GF(p q ). If a BP over Galois field GF(p q ) can be factored into two non-constant EPs then the BP can be termed as Reducible Polynomials over Galois field GF(p q ). If the two factor of a BP over Galois field GF(p q ) have been the BP itself and a constant Polynomial then The BP have been said as an Irreducible Polynomial over Galois field GF(p q ).

2.2.

4-bit Crypto S-Boxes: A 4-bit bijective Crypto S-Box can be written as Follows, where the each element of the first row of Table .1, entitled as index, are the position of each element of the S-Box within the given S-Box and the elements of the 2 nd row, entitled as S-Box, are the elements of the given Substitution Box. It can be concluded that the 1 st row is fixed for all possible bijective crypto S-Boxes. The values of each element of the 1st row are distinct, unique and vary between 0 and F. The values of the each element of the 2 nd row of a bijective crypto S-Box are also distinct and unique and also vary between 0 and F. The values of the elements of the fixed 1 st row are sequential and monotonically increasing where for the 2 nd row they can be sequential or partly sequential or non-sequential. Here the given Substitution Box is the 1 st 4-bit S-Box of the 1 st S-Box out of 8 of Data Encryption Standard [5][6][7].

Row

Relation between 4-bit S-Boxes and Polynomials over Galois field GF (2 15

). Index of Each element of a 4-bit bijective crypto S-Box and the element itself is a hexadecimal number and that can be converted into a 4-bit bit sequence. From row 2 through 5 and row 7 through A of each column from 1 through G of Table .2. shows the 4-bit bit sequences of the corresponding hexadecimal numbers of the index of each element of the given S-Box and each element of the S-Box itself. Each row from 2 through 5 and 7 through A from column 1 through G constitutes a 16 bit, bit sequence that is a Basic Polynomial over Galois field GF(2 15 ). column 1 through G of Row 2 is termed as 4 th IGFP, Row 3 is termed as 3 rd IGFP Row 4 is termed as 2 nd IGFP and Row 5 is termed as IGFP whereas column 1 through G of Row 7 is termed as 4 th OGFP, Row 8 is termed as 3 rd OGFP, Row 9 is termed as 2 nd OGFP and Row A is termed as 1 st OGFP. The decimal equivalent of each IGFP and OGFP are noted at column H of respective rows. Where IGFP stands for Input Galois Field Polynomial and OGFP stands for Output Galois Field Polynomials. The respective Polynomials have been shown in Row 1 through 8 of column 3 of Table . ) where q €15 and 255 respectively. In this paper 4 and 8 bit Identity S-Boxes have been taken for example for generation of 4 and 8 bit S-Boxes over Binary Galois Fields GF(2 q ) where q €15 and 255 respectively. The generation of Identity 4-bit S-Box from four BCNs over Binary Galois Field GF(2 15 ) have been elaborated in sub section 3.1 and The generation of Identity 8-bit S-Box from Eight BCNs over Binary Galois Field GF(2 255 ) have been elaborated in sub section 3.2. The Algorithm for generation of log 2 q+1 bit S-Boxes over Binary Galois Field GF(2 q ) has been depicted with Time Complexity of the algorithm in sub section 3.3. It can be concluded that the 1 st row is fixed for all possible bijective crypto S-Boxes. The values of each element of the 1st row are distinct, unique and vary between 0 and F. The values of the each element of the 2 nd row of the Identity crypto S-Box are also distinct and unique and also vary between 0 and F. The values of the elements of the fixed 1 st row are sequential and monotonically increasing where for the 2 nd row, they can be sequential or partly sequential or non-sequential. Here the given Substitution Box is the 4-bit Identity Crypto S-Box.

3. 7 8 9 A B C D E F G H. Decimal Equivalent 1 Index 0 1 2 3 4 5 6 7 8 9 A B C D E F 2 IBF4 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 00255 3 IBF3 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 03855 4 IBF2 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 13107 5 IBF1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 21845 6 S-Box E 4 D 1 2 F B 8 3 A 6 C 5 9 0 7 7 OBF4 1 0 1 0 0 1 1 1 0 1 0 1 0 1 0 0 42836 8 OBF3 1 1 1 0 0 1 0 0 0 0 1 1 1 0 0 1 58425 9 OBF2 1 0 0 0 1 1 1 0 1 1 1 0 0 0 0 1 36577 A OBF1 0 0 1 1 0 1 1 0 1 0 0 0 1 1 0 1 13965

Generation of 4-bit

Row Column

1 2 3 4 5 6 7 8 9 A B C D E F G 1 Index 0 1 2 3 4 5 6 7 8 9 A B C D E F 2 S-Box 0 1 2 3 4 5 6 7 8 9 A B C D E F

Table.4. 4-bit Identity Crypto S-Box.

Index of Each element of a 4-bit bijective crypto S-Box and the element itself is a hexadecimal number and that can be converted into a 4-bit bit sequence. From row 2 through 5 and row 7 through A of each column from 1 through G of Table .5. shows the 4-bit bit sequences of the corresponding hexadecimal numbers of the index of each element of the given S-Box and each element of the S-Box itself. Each row from 2 through 5 and 7 through A from column 1 through G constitutes a 16 bit, bit sequence that is a Basic Polynomial over Galois field GF(2 15 ). column 1 through G of Row 2 is termed as 4 th IGFP, Row 3 is termed as 3 rd IGFP Row 4 is termed as 2 nd IGFP and Row 5 is termed as IGFP whereas column 1 through G of Row 7 is termed as 4 th OGFP, Row 8 termed as 3 rd OGFP, Row 9 is termed as 2 nd OGFP and Row A is termed as 1 st OGFP. The decimal equivalent of each IGFP and OGFP are noted at column H of respective rows. Where IGFP stands for Input Galois Field Polynomial and OGFP stands for Output Galois Field Polynomials. The respective Polynomials have been shown in Row 1 through 8 of column 3 of Table .6. .7, entitled as index, are the position of each element of the S-Box within the given S-Box and the elements of the column 1 through G of 2 nd to 17 th row, entitled as S-Box, are the elements of the given 8-bit Identity Substitution Box sequentially. It can be concluded that the 1 st row is fixed for all possible 8-bit bijective crypto S-Boxes. The values of each element of the 1st row are distinct, unique and vary between 0 and F. The values of the each element of the column 1 through G of 2 nd row to 17 th row of the 8-bit Identity crypto S-Box are also distinct and unique and vary between 0 and 256. The values of the elements of the fixed 1 st row are sequential and monotonically increasing where for the 2 nd to 17 th row, they can be sequential or partly sequential or non-sequential. Here the given Substitution Box is the 8-bit Identity Crypto S-Box. Index of Each element of an 8-bit bijective crypto S-Box and the element itself is a hexadecimal number and that can be converted into a 256-bit long 8 bit bit sequence. From row 2 through 9 and row A through H of column 2 of Table .8. shows the 8-bit bit sequences of the corresponding hexadecimal numbers of the index of each element of the given S-Box and each element of the S-Box itself. Each row from 2 through 9 and A through H of column 2 constitutes a 256 bit, bit sequence that is a Basic Polynomial over Galois field GF(2 255 ). column 2 of Row 2 is termed as 8 th IGFP, Row 3 is termed as 7 th IGFP, Row 4 is termed as 6 th IGFP ,Row 5 is termed as 5 th IGFP, Row 6 is termed as 4 th IGFP, Row 7 is termed as 3 rd IGFP, Row 8 is termed as 2 nd IGFP and Row 9 is termed as 1 st IGFP whereas column 2 of Row A is termed as 8 th OGFP, Row B is termed as 7 th OGFP, Row C is termed as 6 th OGFP, Row D is termed as 5 th OGFP, Row E is termed as 4 th OGFP, Row F is termed as 3 rd OGFP, Row G is termed as 2 nd OGFP and Row H is termed as 1 st IGFP.

Row Column 1 2 3 4 5 6 7 8 9 A B C D E F G H. Decimal Equivalent 1 Index 0 1 2 3 4 5 6 7 8 9 A B C D E F 2 IBCN4 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 00255 3 IBCN3 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 03855 4 IBCN2 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 13107 5 IBCN1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 21845 6 S-Box 0 1 2 3 4 5 6 7 8 9 A B C D E F 7 OBCN4 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 00255 8 OBCN3 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 03855 9 OBCN2 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 13107 A OBCN1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 21845

BCNs of

Polynomial

IGFP8 &OGFP8

x 127 + x 126 + x 125 + x 124 + x 123 + x 122 + x 121 + x 120 + x 119 + x 118 + x 117 + x 116 + x 115 + x 114 + x 113 + x 112 +

x 111 + x 110 + x 109 + x 108 + x 107 + x 106 + x 105 + x 104 + x 103 + x 102 + x 101 + x 100 + x 99 + x 98 + x 97 + x 96 +

x 95 + x 94 + x 93 + x 92 + x 91 + x 90 + x 89 + x 88 + x 87 + x 86 + x 85 + x 84 + x 83 + x 82 + x 81 + x 80 +

x 79 + x 78 + x 77 + x 76 + x 75 + x 74 + x 73 + x 72 + x 71 + x 70 + x 69 + x 68 + x 67 + x 66 + x 65 + x 64 +

x 63 + x 62 + x 61 + x 60 + x 59 + x 58 + x 57 + x 56 + x 55 + x 54 + x 53 + x 52 + x 51 + x 50 + x 49 + x 48 +

x 47 + x 46 + x 45 + x 44 + x 43 + x 42 + x 41 + x 40 + x 39 + x 38 + x 37 + x 36 + x 35 + x 34 + x 33 + x 32 +

x 31 + x 30 + x 29 + x 28 + x 27 + x 26 + x 25 + x 24 + x 23 + x 22 + x 21 + x 20 + x 19 + x 18 + x 17 + x 16 +

x 15 + x 14 + x 13 + x 12 + x 11 + x 10 + x 9 + x 8 + x 7 + x 6 + x 5 + x 4 + x 3 + x 2 + x+ 1. 4. 4 and 8 bit S-Box Generation by respective BCNs over Non Binary Galois Field GF(16 15 ) and Galois Field GF(256 255 ) respectively. The coefficients of each polynomial over Non Binary Galois Field GF(16 15 ) forms a 4bit S-Box. The Coefficient of highest or lowest degree term must be the 1 st element in 4-bit S-box, the value of other elements are the value of coefficients with immediate degree less than or greater than the previous one. Let The Polynomial be, BP(x) = 0x 15 +1x 14 +2x 13 +3x 12 +4x 11 +5x 10 +6x 9 +7x 8 +8x 7 +9x 6 +10x 5 +11x 4 +12x 3 +13x 2 +14x+15…………..(ii) For the above Polynomial The Constituted 4-bit S-Box have been given in Table 10.

Row Column 1 2 3 4 5 6 7 8 9 A B C D E F G 1 Index 0 1 2 3 4 5 6 7 8 9 A B C D E F 2 S-Box 0 1 2 3 4 5 6 7 8 9 A B C D E F Table.10. constituted 4-bit Crypto S-Box.
The Polynomial with coefficients in reverse order, BP(x) = 15x 15 +14x 14 +13x 13 +12x 12 +11x 11 +10x 10 +9x 9 +8x 8 +7x 7 +6x 6 +5x 5 +4x 4 +3x 3 +2x 2 +1x+0…………….(iii) For the above Polynomial The Constituted 4-bit S-Box have been given in Table 11. 192 193 194 195 196 197 198 199 200 201 Note. The 32-bit S-Boxes can be constituted by Polynomials over Galois field GF[(2 32 ) (2^32-1) ] and the 64-bit S-Boxes can be constituted by Polynomials over Galois field GF[(2 64 ) (2^64-1) ].

Row

Conclusion.

From this Research Article in can be concluded that 4, 8, 32, 64 bit Substitution boxes can be constituted using Basic Polynomials or BPs over Galois Fields GF(16 15 ), GF(256 255 ), GF[(2 32 ) (2^32-1) ] and GF[(2 64 ) (2^64-1) ] respectively. For this reason Generation of 4, 8, 32, 64 bit S-Boxes have been generated very easily with very less complexity. It is a very important work in modern cryptography since the work has been dedicated to crypto community for upgradation of complexity of crypto algorithms.

6. Acknowledgement. For this work I would like to acknowledge my Supervisor Dr. Ranjan Ghsoh for his continuous encouragement and support. I would also like to acknowledge Prof. Debatosh Guha for providing me the infrastructure to do this work very elegantly.

References.

[1] Church R., "Tables of Irreducible Polynomials for the first four Prime Moduli", Annals of Mathematics, Vol. 36(1), pp. 198 -209, January, 1935.

[2] Das, S, Zaman, J.K.M.S. Uz, Ghosh, R, "Generation of AES S-Boxes with various modulus and additive constant polynomials and testing their randomization", Proceedings (CIMTA) 2013, Procedia Technology vol. 10.( 2013), pp: 957 -962.

[3] Jacques C'almet And Riidiger Loos, "An Improvement of Rabin's Probabilistic Algorithm For Generating Irreducible Polynomials Over Gf(P)", Information Processing Letters, 20 October 1980, Volume 11, No. 2.

[4] Zaman , J K M Sadique Uz, Dey sankhanil, Ghosh, R, "An Algorithm to find the Irreducible Polynomials over Galois Field GF(p m )", International Journal of Computer Applications (0975 -8887) Volume 109 -No. 15, January 2015.

Table . 1. 4-bit bijective Crypto S-Box.

 .

Table . 2. Input and Output BCNs of the Substitution Box

 .

	Col	1	2	3
	Row	Index

DCM Eqv. Polynomials over Galois Field GF(2 15 ).

	1	IGFP4	00255	BP(x) = x 7 +x 6 +x 5 +x 4 +x 3 +x 2 +x 1 +1.
	2	IGFP3	03855	BP(x) = x 11 +x 10 +x 9 +x 8 +x 3 +x 2 +x 1 +1.
	3	IGFP2	13107	BP(x) = x 13 +x 12 +x 9 +x 8 +x 5 +x 4 +x 1 +1.
	4	IGFP1	21845	BP(x) = x 14 +x 12 +x 10 +x 8 +x 6 +x 4 +x 2 +1.
	5	OGFP4	42836	BP(x) = x 15 +x 13 +x 10 +x 9 +x 8 +x 6 +x 4 + x 2 .
	6	OGFP3	58425	BP(x) = x 15 +x 14 +x 13 +x 10 +x 5 +x 4 +x 3 +1.
	7	OGFP2	36577	BP(x) = x 15 +x 11 +x 10 +x 9 +x 7 +x 6 +x 5 +1.
	8	OGFP1	13965	BP(x) = x 13 +x 12 +x 10 +x 9 +x 7 +x 3 +x 2 +1.

Table.3. Respective Polynomials of IGFP4 through IGFP1 and OGFP4 through OGFP1 3. 4 and 8 bit S-Box Generation by respective BCNs over Binary Galois Field GF(2 q

Identity Crypto S-Box from four Polynomials over Binary Galois Field GF(2 15 ).

  The Concerned 4-bit Identity S-Box has been shown in table.4 where each element of the first row of Table.4, entitled as index, are the position of each element of the S-Box within the given S-Box and the elements of the 2 nd row, entitled as S-Box, are the elements of the given Identity Substitution Box.

Table . 5. Input and Output BCNs of the Identity Substitution Box

 .

	Col	1	2	3
	Row	Index DCM Eqv.	Polynomials over Galois Field GF(2 15 ).
	1	IGFP4	00255	BP(x) = x 7 +x 6 +x 5 +x 4 +x 3 +x 2 +x 1 +1.
	2	IGFP3	03855	BP(x) = x 11 +x 10 +x 9 +x 8 +x 3 +x 2 +x 1 +1.
	3	IGFP2	13107	BP(x) = x 13 +x 12 +x 9 +x 8 +x 5 +x 4 +x 1 +1.
	4	IGFP1	21845	BP(x) = x 14 +x 12 +x 10 +x 8 +x 6 +x 4 +x 2 +1.
	5	OGFP4	00255	BP(x) = x 7 +x 6 +x 5 +x 4 +x 3 +x 2 +x 1 +1.
	6	OGFP3	03855	BP(x) = x 11 +x 10 +x 9 +x 8 +x 3 +x 2 +x 1 +1.
	7	OGFP2	13107	BP(x) = x 13 +x 12 +x 9 +x 8 +x 5 +x 4 +x 1 +1.
	8	OGFP1	21845	BP(x) = x 14 +x 12 +x 10 +x 8 +x 6 +x 4 +x 2 +1.

Table . 6. Respective Polynomials of IGFP4 through IGFP1 and OGFP4 through OGFP1 3.2. Generation of 8-bit Identity Crypto S-Box from Eight Polynomials over Binary Galois Field GF(2 255 ).

 . The Concerned 8-bit Identity S-Box has been shown in table.7 where each element of the first row of Table

Table . 7. 8-bit Identity Crypto S-Box.

 .

			1	2	3	4	5	6	7	8	9	A	B	C	D	E	F	G
	1	Index	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
	2		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
	3		16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
	4		32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47
	5		48	49	50	51	52	53	54	55	56	57	58	59	60	61	62	63.
	6		64	65	66	67	68	69	70	71	72	73	74	75	76	77	78	79
	7		80	81	82	83	84	85	86	87	88	89	90	91	92	93	94	95
	8		96	97	98	99 100 101 102 103 104 105 106 107 108 109 110 111
	9 10	S-Box	112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
	11		144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
	12		160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
	13		176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191
	14		192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207
	15		208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223
	16		224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239
	17		240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255

Table . 8. BCNs for 8 IGFPs and OGFPs.

 . The Binary Coefficient Number of each IGFP and OGFP from MSB[256 th bit] to LSB[0 th bit] have been given in corresponding rows of each IGFP and OGFP. Where IGFP stands for Input Galois Field Polynomial and OGFP for Output Galois Field Polynomials. The respective Polynomial for IGFP8 and OGFP8 has been shown in Table.9

			0000000000000000111111111111111100000000000000001111111111111111
		IGFP 5	0000000000000000111111111111111100000000000000001111111111111111 0000000000000000111111111111111100000000000000001111111111111111
			0000000000000000111111111111111100000000000000001111111111111111
			0000000011111111000000001111111100000000111111110000000011111111
	6	IGFP 4	0000000011111111000000001111111100000000111111110000000011111111 0000000011111111000000001111111100000000111111110000000011111111
			0000000011111111000000001111111100000000111111110000000011111111
			0000111100001111000011110000111100001111000011110000111100001111
	7	IGFP 3	0000111100001111000011110000111100001111000011110000111100001111 0000111100001111000011110000111100001111000011110000111100001111
			0000111100001111000011110000111100001111000011110000111100001111
			0011001100110011001100110011001100110011001100110011001100110011
	8	IGFP 2	0011001100110011001100110011001100110011001100110011001100110011 0011001100110011001100110011001100110011001100110011001100110011
			0011001100110011001100110011001100110011001100110011001100110011
			0101010101010101010101010101010101010101010101010101010101010101
	9	IGFP 1	0101010101010101010101010101010101010101010101010101010101010101 0101010101010101010101010101010101010101010101010101010101010101
			0101010101010101010101010101010101010101010101010101010101010101
			0000000000000000000000000000000000000000000000000000000000000000
	A	OGFP8	0000000000000000000000000000000000000000000000000000000000000000 1111111111111111111111111111111111111111111111111111111111111111
			1111111111111111111111111111111111111111111111111111111111111111
			0000000000000000000000000000000000000000000000000000000000000000
	B	OGFP 7	1111111111111111111111111111111111111111111111111111111111111111 0000000000000000000000000000000000000000000000000000000000000000
			1111111111111111111111111111111111111111111111111111111111111111
			0000000000000000000000000000000011111111111111111111111111111111
	C	OGFP 6	0000000000000000000000000000000011111111111111111111111111111111 0000000000000000000000000000000011111111111111111111111111111111
			0000000000000000000000000000000011111111111111111111111111111111
			0000000000000000111111111111111100000000000000001111111111111111
	D	OGFP 5	0000000000000000111111111111111100000000000000001111111111111111 0000000000000000111111111111111100000000000000001111111111111111
			0000000000000000111111111111111100000000000000001111111111111111
			0000000011111111000000001111111100000000111111110000000011111111
	E	OGFP 4	0000000011111111000000001111111100000000111111110000000011111111 0000000011111111000000001111111100000000111111110000000011111111
	.		0000000011111111000000001111111100000000111111110000000011111111
	Row 1 2 F G	Col. 1 IGFP8 OGFP 3 OGFP 2	MSB 0000111100001111000011110000111100001111000011110000111100001111 Polynomials (BCNs)[col.2] LSB 0000111100001111000011110000111100001111000011110000111100001111 0000111100001111000011110000111100001111000011110000111100001111 0000000000000000000000000000000000000000000000000000000000000000 0000111100001111000011110000111100001111000011110000111100001111 0000000000000000000000000000000000000000000000000000000000000000 0011001100110011001100110011001100110011001100110011001100110011 1111111111111111111111111111111111111111111111111111111111111111 1111111111111111111111111111111111111111111111111111111111111111 0011001100110011001100110011001100110011001100110011001100110011 0011001100110011001100110011001100110011001100110011001100110011
			0000000000000000000000000000000000000000000000000000000000000000 0011001100110011001100110011001100110011001100110011001100110011
	3 H	IGFP 7 OGFP 1	1111111111111111111111111111111111111111111111111111111111111111 0101010101010101010101010101010101010101010101010101010101010101 0000000000000000000000000000000000000000000000000000000000000000 1111111111111111111111111111111111111111111111111111111111111111 0101010101010101010101010101010101010101010101010101010101010101 0101010101010101010101010101010101010101010101010101010101010101
			0000000000000000000000000000000011111111111111111111111111111111 0101010101010101010101010101010101010101010101010101010101010101
	4	IGFP 6	0000000000000000000000000000000011111111111111111111111111111111 0000000000000000000000000000000011111111111111111111111111111111
			0000000000000000000000000000000011111111111111111111111111111111

Table . 9. Respective Polynomial of IGFP8 and OGFP8 of the Given 8 bit S-Box. 3.3 Algorithm to generate S-Box from Polynomials over Galois field GF(2 15 ) or GF(2 255 ).

 . Choose 4 Galois field Polynomials over Galois field GF(2 15 ) or 8 Galois field Polynomials over Galois field GF(2 255 ). Step.01. If Number of Terms in BCNs are Half of Number of total terms Then Step 02. Else Step 0A. Step.02. Convert to decimal the 4 or 8 bit binary number generated by bits in same position of 4 BCNs for Galois field Polynomials over Galois field GF(2 15 ) or 8 Galois field Polynomials over Galois field GF(2 255 ).

	START.
	Step OA.

STOP. Time Complexity of the given Algorithm. O(n).

  The coefficients of each polynomial over Non Binary Galois Field GF(256 255 ) forms a 8-bit S-Box. The Coefficient of highest or lowest degree term must be the 1 st element in 4-bit S-box, the value of other elements are the value of coefficients with immediate degree less than or greater than the previous one. Let The Polynomial be, Let the Polynomial be given in Table.12., .x 225 + 31.x 224 +32. X 223 + 33. x 222 + 34.x 221 + 35.x 220 + 36.x 219 + 37.x 218 + 38.x 217 +39. x 216 +40. x 215 + 41.x 214 + 42.x 213 + 43.x 212 + 44.x 211 + 45.x 210 + 46.x 209 + 47.x 208 +48.x 207 + 49.x 206 + 50.x 205 + 51.x 204 + 52.x 203 + 53.x 202 + 54.x 201 + 55.x 200 + 56.x 199 + 57.x 198 + 58.x 197 + 59.x 196 + 60.x 195 + 61.x 194 + 62.x 193 + 63.x 192 + 64.x 191 + 65.x 190 + 66.x 189 + 67.x 188 +68.x 187 + 69.x 186 + 70.x 185 + 71.x 184 + 72.x 183 + 73.x 182 + 74.x 181 + 75.x 180 + 76.x 179 + 77.x 178 + 78.x 177 + 79.x 176 +80.X 175 + 81.x 174 + 82.x 173 + 83.x 172 +84. x 171 + 85.x 170 + 86.x 169 + 87.x 168 +88. x 167 + 89.x 166 + 90.x 165 + 91.x 164 + 92.x 163 + 93.x 162 + 94.x 161 + 95.x 160 +96.x 159 + 97.x 158 + 98.x 157 + 99.x 156 + 100.x 155 + 101.x 154 + 102.x 153 + 103.x 152 + 104.x 151 +105.x 150 +106.x 149 + 107.x 148 +108. x 147 +109.x 146 +110. x 145 + 111.x 144 +112.X 143 +113.x 142 +114.x 141 +115.x 140 +116.x 139 +117. x 138 +118. x 137 +119. x 136 +120. x 135 +121.x 134 +122.x 133 +123.x 132 + 124.x 131 +125.x 130 + 126.x 129 + 127.x 128 +128.x 127 +129. x 126 + 130.x 125 +131.x 124 + 132.x 123 +133.x 122 +134.x 121 + 135.x 120 + 136.x 119 + 137.x 118 + 138.x 117 + 139.x 116 + 140.x 115 + 141.x 114 + 142.x 113 + 143.x 112 +144.x 111 + 145.x 110 + 146.x 109 + 147.x 108 + 148.x 107 + 149.x 106 + 150.x 105 + 151.x 104 + 152.x 103 + 153.x 102 + 154.x 101 + 155.x 100 + 156.x 99 + 157.x 98 + 158.x 97 + 159.x 96 +160.x 95 + 161.x 94 + 162.x 93 + 163.x 92 + 164.x 91 + 165.x 90 + 166.x 89 + 167.x 88 + 168.x 87 + 169.x 86 + 170.x 85 + 171.x 84 + 172.x 83 + 173.x 82 + 174.x 81 + 175.x 80 +176.x 79 + 177.x 78 + 178.x 77 + 179.x 76 + 180.x 75 + 181.x 74 + 182.x 73 + 183.x 72 + 184.x 71 + 185.x 70 + 186.x 69 + 187.x 68 + 188.x 67 + 189.x 66 + 190.x 65 + 191.x 64 +192.x 63 +193. x 62 + 194.x 61 + 195.x 60 + 196.x 59 + 197.x 58 + 198.x 57 + 199.x 56 + 200.x 55 + 201.x 54 + 202.x 53 + 203.x 52 + 204.x 51 + 205.x 50 + 206.x 49 + 207.x 48 +208.x 47 + 209.x 46 + 210.x 45 + 211.x 44 + 212.x 43 + 213.x 42 + 214.x 41 + 215.x 40 + 216.x 39 + 217.x 38 + 218.x 37 +219.x 36 + 220.x 35 + 221.x 34 + 222.x 33 + 223.x 32 +224.x 31 + 225.x 30 + 226.x 29 + 227.x 28 + 228.x 27 + 229.x 26 + 230.x 25 + 231.x 24 + 232.x 23 + 233.x 22 + 234.x 21 + 235.x 20 + 236.x 19 + 237.x 18 + 238.x 17 + 239.x 16 +240.x 15 + 241.x 14 +242. x 13 + 243.x 12 + 244.x 11 + 245.x 10 + 246.x 9 + 247.x 8 + 248.x 7 + 249.x 6 + 250.x 5 + 251.x 4 + 252.x 3 + 253.x 2 + 254x+ 255.

							Polynomial BP(x) =
	0.x 255 + 1.x 254 + 2.x 253 + 3.x 252 + 4.x 251 + 5.x 250 + 6.x 249 + 7.x 248 + 8.x 247 + 9.x 246 + 10.x 245 + 11.x 244 + 12.x 243 + 13.x 242 + 14.x 241 +
	15.x 240 +16.x 239 + 17.x 238 + 18. x 237 + 19.x 236 + 20.x 235 + 21.x 234 + 22.x 233 + 23.x 232 + 24.x 231 + 25.x 230 + 26.x 229 + 27.x 228 + 28x 227 +
	29.x 226 + 30
		Column 1	2	3	4	5	6 7 8 9 A B C D E F G
	1	Index	0	1	2	3	4	5 6 7 8 9 A B C D E F
	2	S-Box	15 14 13 12 11 10 9 8 7 6	5 4 3 2 1 0
				Table.11. constituted 4-bit Crypto S-Box.

Table . 12. Polynomial to Construct 8-bit Identity S-Box.

 . For the above Polynomial The Constituted 8-bit S-Box have been given in Table13.

	Row Column	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F	G
	1	Index	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
	2		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
	3		16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
	4		32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47
	5		48	49	50	51	52	53	54	55	56	57	58	59	60	61	62	63.
	6		64	65	66	67	68	69	70	71	72	73	74	75	76	77	78	79
	7		80	81	82	83	84	85	86	87	88	89	90	91	92	93	94	95
	8		96	97	98	99 100 101 102 103 104 105 106 107 108 109 110 111
	9 10	S-Box	112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
	11		144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
	12		160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
	13		176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191
	14


Faouzi Triki
email: faouzi.triki@univ-grenoble-alpes.fr

Chun-Hsiang Tsou
email: chun-hsiang.tsou@univ-grenoble-alpes.fr

Inverse inclusion problem: A stable method to determine disks

Keywords: 1991 Mathematics Subject Classification. Primary: 35R30 Inverse problems, uniqueness, inclusion, unique continuation, disks, stability estimates

In this paper we are interested in inverse inclusion problem in the plane. We derive uniqueness and Hölder stability results of the inclusion recovery problem using a single boundary measurement, under the assumption that the inclusion has a circular shape. We also propose a simple minimizing scheme for the recovery of a disk. Our numerical results show that the Hölder power in the stability estimate is close to one.

Introduction

Let Ω be a simply connected Lipschitz domain in R 2 , and let D be a subdomain of Ω satisfying D ⊂ Ω. Let g ∈ H -1/2 (∂Ω) satisfying ∂Ω gdσ = 0, fix k ∈ R + \ {0, 1}, and let u ∈ H 1 (Ω) be the unique solution to where χ D is the characteristic function of the inclusion D and k is the value of a physical parameter in D (electric or thermal conductivity for example). The inverse inclusion problem is to recover D from the knowledge of a finite number of Cauchy pairs (g, u)| ∂Ω . This inverse problem has a main application in medical imaging, but variants are used in geophysics and other domains. In medical imaging this problem is known under the name of electrical impedance tomography, which is a method of imaging the interior of a body by measurements of current flows and voltages on its surface. On the surface one prescribes current sources g and measures voltage u| ∂Ω for some or all positions of these sources.

When an infinite number of Cauchy pairs are available, the associated boundary Dirichlet-to-Neumann operator can assumed to be known, and in this case there is a considerable amount of studies. We refer the reader to the survey papers [START_REF] Uhlmann | Electrical impedance tomography and calderón's problem[END_REF][START_REF] Alessandrini | Open issues of stability for the inverse conductivity problem[END_REF], and to the books [START_REF] Isakov | Inverse problems for partial differential equations[END_REF][START_REF] Choulli | Une introduction aux problèmes inverses elliptiques et paraboliques[END_REF]. As it is not possible in any concrete experiment to have the access to infinitely many Cauchy pairs, we are interested in recovering the inclusion from a finite number of Cauchy pairs. Assuming that k is known, the question whether one measurement uniquely determines D has already been addressed in several papers, when D is a ball or a convex polyhedron in R 3 (see for instance [START_REF] Friedman | On the uniqueness in the inverse conductivity problem with one measurement[END_REF][START_REF] Barceló | The inverse conductivity problem with one measurement: uniqueness for convex polyhedra[END_REF][START_REF] Kang | Inverse conductivity problem with one measurement: Uniqueness of balls in R 3[END_REF]). The question of stability has been investigated in the case of disks in [START_REF] Fabes | Inverse conductivity problem with one measurement: Error estimates and approximate identification for perturbed disks[END_REF] and [START_REF] Kang | The inverse conductivity problem with one measurement: stability and estimation of size[END_REF]. Kwon [START_REF] Kwon | A real time algorithm for the location search of discontinuous conductivities with one measurement[END_REF] has established a real-time scheme to locate the unknown inclusion with the hypothesis that its size is small compared with that of Ω. Other works concern the case of inclusions of small sizes, while knowledge about their number, location and conductivity may be derived from the knowledge of a certain number of generalized polarization tensors (Ammari and Kang [START_REF] Ammari | Reconstruction of small inhomogeneities from boundary measurements[END_REF]).

In the first part of this paper, we assume that k is a known fixed constant and we focus on the uniqueness and the stability issues for the inverse inclusion problem when D is a disk centering on X 0 with a radius R. Kang and Seo have previously established a Hölder-type stability estimate under a well-chosen current density for the same problem [START_REF] Fabes | Inverse conductivity problem with one measurement: Error estimates and approximate identification for perturbed disks[END_REF]. In this work, we drop the last assumption, i.e. we give a new and a more precise Hölder type stability estimate for any non zero Neumann data g. Moreover, we provide in this work a simple minimizing scheme for the recovery of a disk from a single Cauchy data.

The paper is organized as follows. In section 2, we derive uniqueness and stability results of the inclusion recovery problem using a single measurement, under the assumption that the inclusion has a circular shape. We propose a simple minimizing scheme for the recovery of a disk in section 3. Our numerical simulations in section 4 show that the Hölder stability coefficient in the stability estimate is close to one.

Uniqueness and stability estimates

Since k is fixed we further denote u the unique solution to the system (1.1). Let D = B R (X 0 ) ⊂ Ω 0 be the disk of radius R centered at X 0 , where Ω 0 := {x ∈ Ω|dist(x, ∂Ω) > δ 0 } for some small constant δ 0 > 0. As we assume D is a disk, we only need to determine its center X 0 and its radius R from the knowledge of a single Cauchy pair f = u| ∂Ω and g.

Denoting respectively the solution in the interior of the disk D by u i , and the solution in the exterior by u e , the equation (1.1) can also be formulated as follows:

(2.1)

                     u e = 0 in Ω \ D u i = 0 in D u e = u i on ∂D ∂u e ∂ν = k ∂u i ∂ν on ∂D ∂u ∂ν = g on ∂Ω ∂Ω u e (x)dσ x = 0.
2.1. Integral and complex representations. 2.1.1. Integral representation. We introduce the fundamental solution of the Laplace operator in the plane.

Γ(x) = 1 2π log |x|,
and the single and double layer potentials defined for φ ∈ H -1 2 (∂D) by

S D φ(x) = ∂D Γ(x -y)φ(y)dσ y x ∈ R 2 , D D φ(x) = ∂D ∂ ∂ν y Γ(x -y)φ(y)dσ y x ∈ R 2 \ ∂D.
Using integration by parts, for x ∈ Ω\ D, the solution to (1.1) can be represented in the form:

u e (x) = ∂Ω u(y) ∂ ∂ν y Γ(x -y) - ∂u ∂ν (y)Γ(x -y)dσ y - ∂D u(y) ∂ ∂ν y Γ(x -y) - ∂u ∂ν (y)Γ(x -y)dσ y =H(x) + S D ∂u e ∂ν (x) -D D u e (x), (2.2) and, for x ∈ D u i (x) = ∂D u(y) ∂ ∂ν y Γ(x -y) - ∂u ∂ν (y)Γ(x -y)dσ y = -S D ∂u i ∂ν (x) + D D u i (x), (2.3)
where the harmonic function H is entirely determined by the Cauchy data (f, g)

(2.4) H(x) = ∂Ω u(y) ∂ ∂ν y Γ(x -y) - ∂u ∂ν (y)Γ(x -y)dσ y = D Ω f -S Ω g.
Theorem 2.1. The solution to (2.1) admits the following representation

(2.5)      u i (x) = H(x) + 1 -k 1 + k (H(x) -H(X 0 )) x ∈ D u e (x) = H(x) + 1 -k 1 + k H(X 0 + R 2 (x -X 0 ) x -X 0 2 ) -H(X 0 ) , x ∈ Ω \ D Proof.
With the jump condition on ∂D, we have [START_REF] Ammari | Reconstruction of small inhomogeneities from boundary measurements[END_REF]

D D φ(x)| ± = (∓ 1 2 I + K D )φ(x) x ∈ ∂D,
where K is the Neumann-Poincaré operator defined on L 2 (∂Ω) by

K D φ(x) = 1 2π ∂D y -x, ν y |x -y| 2 φ(y)dσ y .
When D is a disk in R 2 of radius R, the operator K has a very simple form [3]

K D φ(x) = 1 4πR ∂D φ(
u i (x) = -S D ∂u i ∂ν (x) + ( 1 2 I + K D )u i (x).
Adding (2.6) to k times (2.7), and using the mean value propriety for harmonic functions, we obtain for x ∈ ∂D,

u(x) = 2 k + 1 H(x) + 2(k -1) k + 1 K D u(x) = 2 k + 1 H(x) + k -1 k + 1 u i (X 0 ).
As H is harmonic in D, it follows that u i coincides with the above right-hand side in D:

u i (x) = 2 k + 1 H(x) + k -1 k + 1 u i (X 0 ).
And, at X 0 ,

u i (X 0 ) = 2 k + 1 H(X 0 ) + k -1 k + 1 u i (X 0 ),
which implies u i (X 0 ) = H(X 0 ). Then we have the representation of u i , (2.8)

u i (x) = H(x) + 1 -k 1 + k (H(x) -H(X 0 )) x ∈ D
We represent each point x ∈ Ω as x = X 0 + r cos θ sin θ , with θ ∈ [0, 2π) and r > 0, and we write the function H as a sum of harmonic functions r n cos(nθ) and r n sin(nθ):

(2.9)

H(x) = H(X 0 ) + ∞ n=1 r n (a n cos(nθ) + b n sin(nθ)).
By (2.8) and the transmission conditions, we immediately have:

u i (x) = H(X 0 ) + 2 k + 1 ∞ n=1 r n (a n cos(nθ) + b n sin(nθ)), x ∈ D, (2.10
)

u e (x) = H(X 0 ) + ∞ n=1 (r n + 1 -k 1 + k ( R 2 r ) n )(a n cos(nθ) + b n sin(nθ)), x ∈ Ω \ D.
(2.11)

Let Ψ D (x) denote the point obtained by reflecting x over ∂D

Ψ D (x) = X 0 + R 2 (x -X 0 ) x -X 0 2 x ∈ R 2 \ {X 0 }.
We can thus write (2.12)

u e (x) = H(x) + 1 -k 1 + k (H(Ψ D (x)) -H(X 0 )) x ∈ Ω \ D,
which concludes the proof.

2.1.2. Analysis in complex variables. Using the representation (2.5) of u e and u i , we study our problem in the complex plane C. We introduce a harmonic conjugate G of the harmonic function H, so that the function F := H +iG is holomorphic in Ω. Also, the reflection has an explicit expression in terms of complex variables:

Ψ D (z) = Z 0 + R 2 z -Z0 z ∈ C \ {Z 0 }.
By (2.12) and (2.1), the function H • Ψ D is harmonic in Ω \ D. We can also express its harmonic conjugate G for x ∈ Ω \ D as

∇ G(x) = A∇H • Ψ D (x) = ADΨ D (x)∇H(Ψ D (x)), (2.13)
where A = 0 -1 1 0 , and where

DΨ D (x) = R 2 x -X 0 2 (x -X 0 ) 2 2 -(x -X 0 ) 1 2 -2(x -X 0 ) 1 (x -X 0 ) 2 -2(x -X 0 ) 1 (x -X 0 ) 2 (x -X 0 ) 1 2 -(x -X 0 ) 2 2 .
Notice that

DΨ D = -DΨ D A,
combined with (2.13), which yield:

∇ G(x) = A∇H • Ψ D (x) = ADΨ D (x)∇H(Ψ D (x)) = -DΨ D (x)A∇H(Ψ D (x)) = -DΨ D (x)∇G(Ψ D (x)) = -∇G • Ψ D (x).
Thus, the function -G • Ψ D is a harmonic conjugate of the function H • Ψ D , and therefore the function

z → H • Ψ D (z) -iG • Ψ D (z) = F • Ψ D (z) is holomorphic and its real part is equal to H • Ψ D .
Assuming that F is analytic in Ω, we can write F as a sum

F (z) = ∞ n=0 c n (z -Z 0 ) n , z ∈ Ω.
Also, the holomorphic function F • Ψ D admits the following development:

(2.14) F • Ψ D (z) = ∞ n=0 cn R 2n (z -Z 0 ) n , z ∈ Ω \ D.
Therefore, denoting by v e a harmonic conjugate of u e , and given any C ∈ R, the function:

h(z) := u e (z) + iv e (z) = F (z) + 1 -k 1 + k ( F • Ψ D (z) -H(Z 0 ) + iC), z ∈ Ω \ D, is holomorphic.
2.2. Uniqueness and stability estimate. We next derive uniqueness and Hölder-type stability estimate for the recovery of the center and radius of the disk. Let D 1 , D 2 denote 2 disks centered at the points z 1 , z 2 and with radii R 1 , R 2 . For i = 1, 2, let u i be the solutions of the problem (1.1). We assume that the two solutions satisfy the same non-zero Neumann data g on ∂Ω, and that the L ∞norm of the difference between their traces on ∂Ω (the Dirichlet data) is a small quantity ε. We denote by Ω 1 , Ω 2 the images of C \ Ω by the reflections Ψ D1 , Ψ D2 .

Theorem 2.2. If u 1 = u 2 on ∂Ω, then D 1 = D 2 .
Proof. From (2.4), the function H linked to each solution of (1.1) depends uniquely on the Cauchy data. As u 1 and u 2 have the same Cauchy data, their functions H are the same, and we will note this function by H in this proof. Using the unique continuation propriety, we have:

u 1 = u 2 in Ω \ (D 1 ∪ D 2 ). Case 1 : D 1 ∩ D 2 = ∅.
In this case, u e 1 has a harmonic continuation in D 1 , which coincides with u e 2 i.e. u e 2 = u i 1 in D 1 . Then, on ∂D 1 , we have:

(2.15)

∂u i 1 ∂ν = ∂u e 2 ∂ν = ∂u e 1 ∂ν = k ∂u i 1 ∂ν ,
which implies ∂u i 1 ∂ν = 0 on ∂D 1 , so that u i 1 = 0, and thus u 1 = 0 and g = 0. Hence the contradiction.

Let z and Z be defined as (2.24). Case 2 : ∂D 1 ∩ ∂D 2 = ∅. In this case, from (2.24), ∂D 1 ∩ ∂D 2 = {z , Z }. Then, from the continuity of the solutions, we have:

(2.16) u i 1 (z ) = u e 1 (z ) = u e 2 (z ) = u i 2 (z ) Using (Theorem 2.1), we have H(z 1 ) = H(z 2 ) and u i 1 = u i 2 in D 1 ∩ D 2 . So, on ∂(D 1 -D 2 ), u 1 -u 2 = 0, which implies u i 1 = u e 2 in D 1 -D 2 .
Then, on the arc D 1 ∩ ∂D 2 , we have:

(2.17)

∂u i 2 ∂ν = ∂u i 1 ∂ν = ∂u e 2 ∂ν = k ∂u i 2 ∂ν ,
which implies

∂u i 1 ∂ν = ∂u i 2 ∂ν = 0.
For the same reason, we also have:

∂u i 1 ∂ν = ∂u i 2 ∂ν = 0 on the arc D 2 ∩ ∂D 1 . It follows that, ∂u i 1 ∂ν = ∂u i 2 ∂ν = 0 in ∂(D 1 ∩ D 2
). This also implies u i 1 = 0 and then g = 0. Hence the contradiction.

Case 3 : D 1 ⊂ D 2 . In this case, we have: z ∈ D 1 and Z ∈ C \ D 2 . The functions u e j -H, j = 1, 2 have a harmonic extension in C \ D 2 , and they are equal in Ω \ D 1 , so from (2.1), we have:

(2.18) H(Ψ 1 (z)) -H(z 1 ) = H(Ψ 2 (z)) -H(z 2 ) in C \ D 2 .
Applying (2.18) on z , we have H(z 1 ) = H(z 2 ) and then

u 1 = u 2 in D 1 ∩ D 2 = D 1 .
The rest of the proof follows the same argument as in the previous cases. That completes the proof Lemma 2.3. Let F (z) be a non-zero holomorphic function in Ω, and assuming that D 1 = D 2 , then there exists 0 < β < 1, which only depends on F , such that

(2.19) ∂Ω |Ψ 1 (z) -Ψ 2 (z)| |F (Ψ 1 (z)) -F (Ψ 2 (z))| β ds < ∞.
Proof. We first show that the set Z := {z ∈ ∂Ω|F (Ψ 1 (z)) -F (Ψ 2 (z)) = 0} is finite. Indeed, assume that Z has infinity elements. Then, by an argument of compactness, Z has a limit point. As the functions

F • Ψ i , i = 1, 2 are anti- holomorphic, it follows that F (Ψ 1 (z)) = F (Ψ 2 (z)) on C \ (D 1 ∪ D 2 )
. Thus, from the explicit formula of solutions, we can construct two solutions to (1.1) related to D 1 and D 2 , which have the same Cauchy data on ∂Ω. This contradicts the uniqueness of the inverse problem (Theorem 2.2).

As the function F(z)

:= F (Ψ 1 (z)) -F (Ψ 2 (z)) is holomorphic in C \ (D 1 ∪ D 2 ), if z ∈ Z, there is m(z) ∈ N such that, in a neighborhood of z, F(z) = n≥m(z) q n (z -z) n , with q m(z) = 0. Let γ ∈ C 1 ([a, b]
) be a parametrization of ∂Ω, and set z = γ( t). Then, in a neighborhood of t, we have

F(γ(t)) = n≥m(z) q n (t -t) n ,
with q m(z) = 0. We choose 0 < β < 1 m where m := max z∈Z m(z). Then, for t -δ < t < t + δ we have,

1 |F(γ(t))| β ≤ C|t -t| -βm(z) , with 0 < βm(z) < 1. Therefore, t+δ t-δ 1 |F(γ(t))| β dt < ∞. Thus, ∂Ω |Ψ 1 (z) -Ψ 2 (z)| |F (Ψ 1 (z)) -F (Ψ 2 (z))| β ds = b a |Ψ 1 (γ(t)) -Ψ 2 (γ(t))| |F(γ(t))| β |γ (t)|dt < ∞.
and (2.19) follows.

Theorem 2.4. Assume that (2.20)

u 1 | ∂Ω -u 2 | ∂Ω L ∞ (∂Ω) = ε.
Then, there exist constants 0 < α, β < 1 and C > 0, such that

(2.21) |z 1 -z 2 | ≤ Cε αβ , and
(2.22) |R 1 -R 2 | ≤ Cε αβ ,
where α := ω(z ) > 0, and where ω and z are given by the following equations

(2.23)    ω = 0 in Ω \ Ω 1 ∪ Ω 2 ω = 1 on ∂Ω ω = 0 on ∂(Ω 1 ∪ Ω 2 ), (2.24) z 1 + R 2 1 z -z1 = z 2 + R 2 2 z -z2 = Z ∈ C,
where β only depends on the boundary Cauchy data.

Remark 2.5. About the location of the points z and Z , we observe that • Z is the image of z by the reflection with respect to ∂D 1 and with respect to ∂D 2 .

• in the case where ∂D 1 ∩∂D 2 = ∅, z = Z is one of the intersection points.

• in the case where

D 1 ∩ D 2 = ∅, then either z ∈ D 1 and Z ∈ D 2 or z ∈ D 2 and Z ∈ D 1 . • in the case where D 1 ⊂ D 2 (resp. D 2 ⊂ D 1 ), then z ∈ D 1 (resp. z ∈ D 2 )
and

Z ∈ C \ D 2 (resp. Z ∈ C \ D 1
). • at least one of the points z and Z is in Ω. We can always assume that z ∈ Ω.

Proof. According to the position of the point Z , we distinguish two cases: Case 1 : both z and Z are in Ω. Because Z is the image of z by Ψ D1 and vice-versa, one of z or Z is in D1 , the other lies in Ω \ D 1 . We may assume that z ∈ Ω \ D 1 . We define (2.25)

hi (z) = h i (z) -h i (z ) = F i (z) -F i (z ) + 1 -k 1 + k F i (z i + R 2 i z -zi ) -F i (Z ) .
By construction, the function h 1 -h 2 can be holomorphically extended in Ω \ Ω 1 ∪ Ω 2 and satisfies (2.26)

M := sup{|h 1 -h 2 | : z ∈ Ω \ Ω 1 ∪ Ω 2 } ≤ C||g|| L 2 (∂Ω) , (2.27
)

|h 1 -h 2 | ≤ ε on ∂Ω.
Consequently, for z ∈ ∂Ω,

h1 (z) -h2 (z) = h 1 (z) -h 2 (z) -[h 1 (z ) -h 2 (z )] = F 1 (z) -F 2 (z) + F 1 (z ) -F 2 (z ) + 1 -k 1 + k F 1 (z 1 + R 2 1 z -z1 ) -F 2 (z 2 + R 2 2 z -z2 ) + F 2 (Z ) -F 1 (Z ) . (2.28)
Let ω be the solution to the Dirichlet problem (2.23), the function

ω log ε + (1 - ω) log M is therefore harmonic in Ω \ Ω 1 ∪ Ω 2 . On the other hand, log |h 1 -h 2 | = (log(h 1 -h 2 )) is also a harmonic function in Ω \ Ω 1 ∪ Ω 2 .
From (2.26) and (2.27), we have

(2.29) log |h 1 (z) -h 2 (z)| ≤ ω(z) log ε + (1 -ω(z)) log M, z ∈ ∂(Ω \ Ω 1 ∪ Ω 2 )
Then, by the maximum principle,

(2.30) log |h 1 (z ) -h 2 (z )| ≤ ω(z ) log ε + (1 -ω(z )) log M Hence, (2.31) |h 1 (z ) -h 2 (z )| ≤ Cε α , with α := ω(z ).
Using the assumption (2.20) and the definition (2.4) of H, we have

(2.32) ∀z ∈ Ω, |F 1 (z) -F 2 (z)| ≤ Cε.
Further, from (2.28) we have that for all z ∈ ∂Ω,

F 1 (z 1 + R 2 1 z -z1 ) -F 1 (z 2 + R 2 2 z -z2 ) = F 1 (Z ) -F 2 (Z ) + 1 + k 1 -k [F 2 (z) -F 1 (z) + F 2 (z ) -F 1 (z ) + h 1 (z) -h 2 (z) + h 2 ( ) -h 1 (z )]. (2.33)
Applying (2.27), (2.31) and (2.32), we obtain:

(2.34) |F 1 (z 1 + R 2 1 z -z1 ) -F 1 (z 2 + R 2 2 z -z2 )| ≤ Cε α , ∀z ∈ ∂Ω.
Then, using (2.34) and (2.19), we have the following estimate:

∂Ω |Ψ 1 (z) -Ψ 2 (z)|ds = ∂Ω |Ψ 1 (z) -Ψ 2 (z)| |F 1 (Ψ 1 (z)) -F 1 (Ψ 2 (z))| β |F 1 (Ψ 1 (z)) -F 1 (Ψ 2 (z))| β ds ≤ ∂Ω |Ψ 1 (z) -Ψ 2 (z)| |F 1 (Ψ 1 (z)) -F 1 (Ψ 2 (z))| β ds × Cε αβ ≤ C ε αβ . (2.35)
On the other hand, we have:

∂Ω |Ψ 1 (z) -Ψ 2 (z)|ds = ∂Ω |Ψ 1 (z) -Ψ 2 (z)|ds ≥ | ∂Ω Ψ 1 (z) -Ψ 2 (z)dz| = | ∂Ω z1 -z2 + R 2 1 z -z 1 - R 2 2 z -z 2 dz| = |R 2 1 -R 2 2 |. So, we have: (2.36) |R 1 -R 2 | ≤ Cε αβ .
Using (2.36), we have: for all z ∈ ∂Ω,

|Ψ 1 (z) -Ψ 2 (z)| = |z 1 -z2 + R 2 1 z 1 -z 2 (z -z 1 )(z -z 2 ) | + O(ε αβ ).
So, from (2.35),

Cε αβ ≥ ∂Ω |z 1 -z2 + R 2 1 z 1 -z 2 (z -z 1 )(z -z 2 ) |ds = |z 1 -z 2 | ∂Ω |e -2i arg(z1-z2) + R 2 1 (z -z 1 )(z -z 2 ) |ds with ∂Ω |e -2i arg(z1-z2) + R 2 1 (z -z 1 )(z -z 2 ) |ds > 0.
Thus,

(2.37)

|z 1 -z 2 | ≤ Cε αβ . Case 2 : z ∈ Ω, Z ∈ C \ Ω. We define (2.38) hi (z) = h i (z) -(h i (Z ) -f i (Z )) = f i (z) + 1 -k 1 + k F i (z i + R 2 i z -zi ) -F i (z ) .
By (2.14), the holomorphic functions h i -F i , i = 1, 2 can be extended to C \ Di and they vanish as |z| → ∞. Let Ω be an open set containing Ω and the point Z * , and consider a harmonic function ω solution to the following equation

(2.39)    ω = 0 in Ω \ Ω ω = 1 on ∂Ω ω = 0 on ∂ Ω.
Define α = ω(Z ). Thus, from (2.27) and ( 2.32) we have

(2.40) |(h 1 -F 1 ) -(h 2 -F 2 )| ≤ Cε on ∂Ω.
We apply the maximum principle on Ω \ Ω to the harmonic function

ω log ε + (1 -ω) log M -log |(h 1 -F 1 ) -(h 2 -F 2 )| to obtain: (2.41) log |(h 1 -F 1 )(Z ) -(h 2 -F 2 )(Z )| ≤ ω(Z ) log ε + (1 -ω(Z )) log M, so that (2.42) |(h 1 -F 1 )(Z ) -(h 2 -F 2 )(Z )| ≤ Cε α .
In fact, we can choose, Ω = B ρ (z 1 ) with ρ as large as we want. We denote ω ρ the solution to the associated equation (2.39) and we also consider the harmonic function ωρ solution to (2.43)

   ωρ = 0 in B(z 1 , ρ) \ B(z 1 , R 1 ) ωρ = 1 on ∂B(z 1 , R 1 ) ωρ = 0 on ∂B(z 1 , ρ).
The function ωρ has the explicit expression

(2.44) ωρ (r) = log(r) -log(ρ) log(R) -log(ρ) , with r := |z -z 1 |. By the maximum principle, ωρ ≤ ω ρ in B(z 1 , ρ) \ Ω. So, we have (2.45) 1 > ω ρ (Z ) ≥ ωρ (Z ) = log(r) -log(ρ) log(R) -log(ρ) -→ ρ→∞ 1.
From (2.42), we have

(2.46) |(h 1 (Z ) -F 1 (Z )) -(h 2 (Z ) -F 2 (Z ))| ≤ Cε β , 0 < β < 1.
Thus,

(2.47)

|(h 1 (Z ) -F 1 (Z )) -(h 2 (Z ) -F 2 (Z ))| ≤ Cε.
The rest of the proof follows the same argument as that of case 1.

Reconstruction from two measurements.

It follows from the analysis of section 2.1.2 that we can obtain some geometric elements of the disk from a simple contour integration. Thus, we can reconstruct the center, the radius and the conductivity k if we have two distinct measures under the assumption that ∇u = 0 in Ω. The method of reconstruction is described as follows. We calculate the following integral:

(2.48)

I := 1 2πi ∂Ω h(z)dz.
Using the representation (2.14) and the Residue Theorem on Ω, we have

I : = 1 2πi ∂Ω h(z)dz = 1 2πi ∂Ω F (z) + 1 -k 1 + k ( F • Ψ D (z) -H(Z 0 ) + iC)dz = 1 2πi [ ∂Ω F (z)dz + 1 -k 1 + k ( ∂Ω ∞ n=0 cn R 2n (z -Z 0 ) n dz + ∂Ω -H(Z 0 ) + iCdz)] = 1 2πi 1 -k 1 + k ∞ n=1 cn R 2n ∂Ω 1 (z -Z 0 ) n dz = 1 -k 1 + k c1 R 2 = 1 -k 1 + k F (Z 0 )R 2 .
(

Using the same arguments, we can also calculate the following integral

1 2πi ∂Ω zh(z)dz = 1 2πi ∂Ω zF (z) + 1 -k 1 + k z( F • Ψ D (z) -H(Z 0 ) + iC)dz = 1 2πi [ ∂Ω zF (z)dz + 1 -k 1 + k ( ∂Ω ∞ n=0 cn zR 2n (z -Z 0 ) n dz + ∂Ω z(-H(Z 0 ) + iC)dz)] = 1 2πi 1 -k 1 + k ∞ n=1 cn R 2n ∂Ω z (z -Z 0 ) n dz = 1 2πi 1 -k 1 + k ∞ n=1 cn R 2n ∂Ω 1 (z -Z 0 ) n-1 + Z 0 (z -Z 0 ) n dz = 1 -k 1 + k (Z 0 c1 R 2 + c2 R 4 ).
(2.50)

Denoting by f 1 , f 2 two functions f corresponding to two distinct measurements, from (2.49) we have (2.51)

Ī1 Ī2 = F 1 (Z 0 ) F 2 (Z 0 ) So, Z 0 is a zero of the holomophic function z → F 1 (z) F 2 (z) - Ī1 Ī2 (F 2 (z) = 0 ∀z ∈ Ω as
we supposed that ∇u = 0). Once Z 0 is determined, R and k can be easily found from (2.49) and (2.50).

Optimization algorithms

In this section, we consider a numerical scheme to reconstruct a disk contained in a subset Ω 0 ⊂ Ω with dist(∂Ω 0 , ∂Ω) ≥ δ 0 > 0, using a single measurement. The scheme is based on minimizing the functional

J(u) = 1 2 ∂Ω |u -u meas | 2 dσ,
where u meas is the measured Dirichlet data and where u is the solution to (1.1) associated to a disk

D = B(X 0 , R) ⊂ Ω 0 . Given (c 1 , c 2 , R) ∈ R 3
, the gradient of the functional J at this point can be calculated as follows.

Theorem 3.1. Let u be the solution to the problem (1.1) associated to a disk and let w be the solution to the following problem 3 , such that the disk D centered at (c 1 , c 2 ), with radius R is included in Ω 0 . Denote u (receptively ũ) the solutions to (1.1) associated to the disk B R (c 1 , c 2 ) (respectively B R (c 1 + dx 1 , c 2 )). Then we have

(3.1) div((1 + (k -1)χ D )∇w) = 0 in Ω, ∂w ∂ν = u -u meas on ∂Ω. Then ∂J ∂c 1 = (k -1) D ∂ ∂x 1 (∇u∇w)dX (3.2) ∂J ∂c 2 = (k -1) D ∂ ∂x 2 (∇u∇w)dX (3.3)
∂J ∂R = k -1 R D 2∇u∇w + i=1,2 (x i -c i ) ∂ ∂x i (∇u∇w)dX. (3.4) Proof. Let (c 1 , c 2 , R) ∈ R
J(c 1 + dc 1 , c 2 , R) -J(c 1 , c 2 , R) = 1 2 ∂Ω |ũ -u meas | 2 dσ - 1 2 ∂Ω |u -u meas | 2 dσ = 1 2 ∂Ω (ũ -u)(ũ + u -2u meas )dσ = 1 2 ∂Ω (ũ -u)(ũ -u + 2(u -u meas ))dσ = ∂Ω (u -u meas )vdc 1 dσ + O(|dc 1 | 2 ).
Therefore, Combining the variational forms of (1.1) for u and for ũ, we have that for all φ ∈ H 1 (Ω), (3.6)

Ω (1 + (k -1)χ D )∇ũ∇φdX - ∂Ω gφdσ = 0, and (3.7
)

Ω (1 + (k -1)χ D )∇u∇φdX - ∂Ω gφdσ = 0.
By applying a result of shape derivative (see [START_REF] Allaire | Structural optimization using sensitivity analysis and a level-set method[END_REF]), (3.6)-(3.7) give us:

0 = 1 dc 1 [ Ω (1 + (k -1)χ D )∇ũ∇φdX - Ω (1 + (k -1)χ D )∇u∇φdX] = Ω ∇v∇φdX + k -1 dc 1 ( D ∇ũ∇φdX - D ∇u∇φdX) = Ω (1 + (k -1)χ D )∇v∇φdX + k -1 dc 1 ( D ∇u∇φdX - D ∇u∇φdX) + O(|dc 1 |) = Ω (1 + (k -1)χ D )∇v∇φdX + (k -1) ∂D e 1 • ν∇u∇φdσ + O(|dc 1 |).
It follows that v satisfies, for all φ ∈ H 1 (Ω), As D is a disk, we have ν = x-X0 R so that the previous integral becomes

∂D ∇u∇wdσ = ∂D ν • ν∇u∇wdσ = ∂D x -X 0 R • ν∇u∇wdσ = 1 2R ∂D ∂|x -X 0 | 2 ∂ν ∇u∇wdσ = 1 2R ( D ∇|x -X 0 | 2 ∇(∇u∇w)dX + D (|x -X 0 | 2 )∇u∇wdX) = 1 R D 2∇u∇w + i=1,2 (x i -c i ) ∂ ∂x i (∇u∇w)dX,
and (3.4) follows.

The expression of the shape derivative is the basis of the following iterative algorithm:

(1) Chose an initial disk D = B(X 0 , R 0 ).

(2) For each iteration, i > 0: (a) Calculate the solution to (1.1) u i , associated to the disk

D i = B(X i , R i ). (b) Calculate the shape derivatives ∂J ∂c1 , ∂J ∂c2 , ∂J ∂R (c) Update the parameters of the disk (X i+1 , R i+1 ) = (X i , R i )-δ∇J(X i , R i ) with δ > 0. (d) If the updated disk is not entirely in Ω or if R becomes negative,
reduce the size δ. (3) When J(X i , R i ) becomes smaller than a fixed threshold, we stop.

Numerical examples

The setting of all numerical tests is as follows:

• We use FreeFem++ for our numerical experiments [START_REF] Hecht | New development in freefem++[END_REF].

• Ω is a centered ellipse defined by the equation:

x 2 1 4 2 + x 2 2 3 2 ≤ 1.
• the conductivity k is a fixed constant, here we set k = 5.

• the Neumann data g := ∂u ∂ν is defined by: g = e, ν on ∂Ω where e = 2 3 .

• We use P2 finite elements for the numerical resolution of the PDEs.

• At each iteration, we remesh the domain to adapt to the new predicted position of the disk. In this subsection, we show three examples according to the disk's size, and its distance to the boundary ∂Ω,

(1) The target is close to the boundary ∂Ω. (3) The target has a small size. Figure 1c shows the solution to (1.1) when the target disk is centered at X 0 = 2.4 -1.2 and has radius R = 0.3. In these three cases, we exercise our algorithm with the same initial guess: the disk centered at 0 0 with radius 2.5.

Figure 2 shows the decay of log(J) during the iterations in the first case. We can observe that J decays exponentially to 0. To illustrate the dependence between the [START_REF] Ammari | Reconstruction of small inhomogeneities from boundary measurements[END_REF][START_REF] Barceló | The inverse conductivity problem with one measurement: uniqueness for convex polyhedra[END_REF][START_REF] Choulli | Une introduction aux problèmes inverses elliptiques et paraboliques[END_REF], where X i and R i denote the center and radius of the disk at the i-th iteration. In order to show the Hölder-type stability, it is also interesting to draw linear regression lines to each of these curves. Thus, the inclination of the linear regression lines present a numerical estimation of the Hölder exponent. -There is no clear evidence of a relation between the Hölder exponents α and the distance between the target disk and ∂Ω.

-We always choose δ near 0.1. Roughly speaking, when δ exceed 0.5, J does not decay during the iterations.

-For the same target, different initial guesses do not change the number of iterations to reach convergence.

-Exceptionally, if the center of the initial guess coincide with the target's center, only about 10 iterations are needed to reach the target.

-When the target disk is too small, more iterations are needed.

Conclusion

We have established the uniqueness of the inclusion recovery problem using a single measurement, under the assumption that the inclusion has a circular shape and we improved the stability estimate result in [START_REF] Fabes | Inverse conductivity problem with one measurement: Error estimates and approximate identification for perturbed disks[END_REF]. Our stability estimate is valid even for non-zero input electrical current. Our numerical simulations show that the

  (k -1)χ D )∇u) = 0 in Ω, ∂u ∂ν = g on ∂Ω, ∂Ω u(x)dσ x = 0,(1.1)

Ω ( 1 +( 1 +

 11 (k -1)χ D )∇v∇φdX + (k -1) ∂D e 1 • ν∇u∇φdσ. Introducing the function w defined by (3.1), and taking w as φ in (3(k -1)χ D )∇v∇wdX + (k -1) ∂D e 1 • ν∇u∇wdσ. On the other hand, 0 = Ω div[(1 + (k -1)χ D )∇w]vdX = ∂Ω v(u -u meas )dσ + Ω (1 + (k -1)χ D )∇v∇wdX. follows. By the same argument, we can obtain (3.3) and ∂J ∂R = (k -1) ∂D ∇u∇wdσ.

Figure 1a shows the solution to ( 1 . 1 ) 2 )

 112 when the target disk is centered at X 0 The target is apart from the boundary ∂Ω.

  Figure 1b shows the solution to (1.1) when the target disk is centered at X 0 = 0.5 0.5 and has radius R = 0.7.

3 Figure 1 .

 31 Figure 1. Numerical solutions of (1.1)

Figure 2 .

 2 Figure 2. Decay of log(J) during iterations

Figure 3 .

 3 Figure 3. Case X 0 = (2, 0.8), R = 1

Figure 4 .

 4 Figure 4. Case X 0 = (-0.3, 0.5), R = 0.7

  ∂ Ω |u i -u meas | 2 dσ) log(|R i -R 0 | 2 ) y=0.9069x-4.5595 log(|X i -X 0 | 2 ) y=1.0316x+2.4516

Figure 5 . 3 -

 53 Figure 5. Case X 0 = (2.4, -1.2), R = 0.3

FAOUZI TRIKI AND CHUN-HSIANG TSOU

Hölder stability coefficient α in the stability estimate is close to 1, which indicates that the dependence might actually be Lipschitz.

Acknowledgments

This work has been partially supported by the LabEx PERSYVAL-Lab (ANR-11-LABX-0025-01).


Zaaraoui
email: hind.zaaraoui@orange.com

Zwi Altman
email: zwi.altman@orange.com

Eitan Altman
email: eitan.altman@sophia.inria.fr

Tania Jimenez
email: tania.jimenez@univ-avignon.fr

Analytical results for two users' forecast scheduling

I. INTRODUCTION

The concept of Forecast Scheduling (FS) has been introduced in [START_REF] Zaaraoui | Forecast scheduling for mobile users[END_REF], where it is shown that the knowledge of the present and future rates along the users' trajectories can be exploited by the scheduler in order to significantly improve the average user throughput. The throughput gain is achieved by exploiting long term time and spatial diversity along the users' trajectory. The FS is posed as a convex optimization problem that can be solved using fast convex optimziation solvers. The randomness of the traffic, i.e. arrival and departure of communications on the one hand and randomenss in the user trajectories can be incorporated into the FS solution [START_REF]Forecast scheduling and its extensions to account for random events[END_REF].

This repport investigates the FS for the case of n = 2 users and derives closed form expressions for the FS allocation rules.

II. FORECAST SCHEDULING MODEL AND ANALYTICAL RESULTS

In this Section we first briefly recall the basic formulation of the FS as presented in [START_REF] Zaaraoui | Forecast scheduling for mobile users[END_REF]. Then, using Karush-Kuhn-Tucker (KKT) conditions, we provide a closed form solution for n = 2 users with the main steps for deriving it.

A. Basic formulation

Consider a macro-cell (Base Station (BS)) surrounded by interfering BSs. We suppose that the Signal to Interference plus Noise Ratio (SINR) for the users in mobility at any location is provided to the BS by a Radio Environment Map (REM). Consider n full buffer users moving at a constant speed during a time interval T -the scheduling period, over which n is considered constant. Suppose that time is in a discrete space: t ∈ {1, 2, .., T } = [|1, T |] and let i denote the user number, i ∈ {1, 2, .., n} = [|1, n|].

We suppose that during the scheduling duration there are no arrivals or departures of users (this assumption can be relaxed [START_REF]Forecast scheduling and its extensions to account for random events[END_REF]).

A scheduling period T (typically of the order of seconds) is divided into scheduling time slots denoted here for simplicity as time units (e.g. of 1 ms), during which the bandwidth is shared among the scheduled users. Let a i (t) denote the bandwidth proportion allocated to a user i at time t, a i (t) ∈ [0, 1], according to the scheduling strategy, where ∀t, n i=1 a i (t) = 1, and W -the total bandwidth. Using the Shannon equation, we write the throughput as a function φ of the SINR of user i as follows ai(t)φ(SIN Ri(t)) = ai(t)W log2(1 + SIN Ri(t)). [START_REF] Zaaraoui | Forecast scheduling for mobile users[END_REF] Denote by S t i the predicted SINR (i.e. the one provided by the REM). The FS allocation policy is defined by the following optimization problem, with α = 1:

maximize : f (a) = n i=1 ( T t=1 ai(t)φ(S t i )) 1-α 1 -α (2) subject to : ∀i, ∀t, ai(t) ≥ 0 ∀t, n i=1 ai(t) = 1
and for α → 1, the optimization problem with the same constraints reads:

maximize : f (a) = n i=1 log( T t=1 ai(t)φ(S t i )). (3)
Both equations ( 2) and ( 3) have concave functions f for α ≥ 0, and can be solved using convex optimization. The size of the optimization problem is defined by the number of unknown variables, namely n × T .

The interpretation of ( 2) and ( 3) is the following: resources are shared fairly among the users according to the data-rate variation in their future trajectories. For example, if a user has a large enough coverage hole in his future trajectory, the forecast scheduler will take this into account and may allocate this user as much data as possible before reaching the coverage hole so as to remain fair with respect to the other users.

B. Analytical model for n = 2 two users

We derive presently the KKT conditions for the problem [START_REF]Forecast scheduling and its extensions to account for random events[END_REF]. The optimization problem (2) has a nonlinear objective function f with regular equality and inequality conditions i.e. differentiable constraint functions. The objective and constraint functions [START_REF]Forecast scheduling and its extensions to account for random events[END_REF] are continuously differentiable at any a = (a 1 (1), a 1 (2), ...a 1 (T ), a 2 (1), ..., a n (T )) ∈ R nT , then there exist multipliers λ k,j and ν j , where k ∈ [|1, n|] and j ∈ [|1, T |], called KKT multipliers ([3], Chap.5) with the following Lagrangian function:

L(a, ν, λ) = f (a)+ T j=1 ν j ( n k=1 a k (j)-1)+ k,j λ k,j a k (j), (4
) where λ k,j ≥ 0.

We define the Lagrange dual function as the maximum value of L over a. Let a * maximizes the Lagrangian function (4) for the optimal multipliers λ * k,j and ν * j , where k ∈ [|1, n|] and j ∈ [|1, T |], therefore its gradiant is null at this point:

∇L(a * , ν * , λ * ) = 0.
(5)

From (5) one obtains for all i ∈ [|1, n|] and t ∈ [|1, T |] the KKT conditions:

∂f (a) ∂a i (t) + ∂ ∂a i (t) T j=1 ν j ( n k=1 a k (j) -1) + ∂ ∂a i (t) k,j λ k,j a k (j) = 0, a i (t) ≥ 0, n i=1 a i (t) = 1, λ i,t a i (t) = 0, λ i,t ≥ 0, which is equivalent to : φ(S t i )( T j=1 a * i (j)φ(S j i )) -α + ν * t + λ * i,t = 0, (6)
a * i (t) ≥ 0, (7)
n k=1 a * k (t) = 1, (8)
λ * i,t a * i (t) = 0 (9) λ * i,t ≥ 0. (10)
We note from (6) that at any time t, for all users i and w with w = i φ(S t i )(

T j=1 a * i (j)φ(S j i )) -α + λ * i,t = φ(S t w )( T j=1 a * w (j)φ(S j w )) -α + λ * w,t (11)
and also from (6), for all user i, we have for all times t and u:

λ * i,t + ν * t φ(S t i ) = λ * i,u + ν * u φ(S u i ) (12)
as ν * t does not depend on the users, and T j=1 a * i (j)φ(S j i ) does not depend on the time. The equality (11) explicits the resource balancing among users at each time relatively to α in the sense of equalizing the two expressions of each user.

C. KKT resolution for the case of two users

In all the calculations that follow, we rewrite a = a * , λ = λ * and ν = ν * .

Suppose there are two users in the cell, i.e. n = 2 in problem [START_REF]Forecast scheduling and its extensions to account for random events[END_REF]. There are still more unknown variables than equations. We introduce the following property to allow the resolution of the problem:

1) Problem assumptions: With some data rates condition, if the two (all, for the general case) users are scheduled simultaneously at some time t = K then only one user is scheduled in all other times within [1, T ] and different from K Theorem 1. If the following conditions are verified: 1/ There exists a time t = K where ∀i,a i (K) > 0 i.e. both users are scheduled simultaneously at time K, 2/ ∀i, j,

φ(S t i ) φ(S k i ) = φ(S t j ) φ(S k j ) , Then ∀t = K in [1, T ]
, there exists only one j(t) such as a j(t) (t) > 0.

See the proof in the annexe.

From Theorem 1, one can deduce that only two cases exist:

• both users are scheduled simultaneously at time K and in other times only one of them is scheduled; • only one user is scheduled at each time i.e. no such time K exists.

The assumption 2 of Theorem 1 comes from the fact that the data rates fractions are almost surely not equal between users in reality as they have almost never the same trajectories at the same time. It is noted that numerical experiments have shown that the case described in Theorem 1 does not occur often. In the next two subsections we check the existence of the time K.

2) If time K exists then users are scheduled at the same time K: We suppose in the following that time K exists and that at a given time t = K the user 1 is scheduled (and hence user 2 is not scheduled) then from equation (12):

λ 1,t = 0, λ 1,K = 0 ⇔ ν K φ(S K 1 ) = ν t φ(S t 1 ) (13)
λ 2,t ≥ 0, λ 2,K = 0 ⇔ ν K φ(S K 2 ) ≥ ν t φ(S t 2 ) (14)
Denote by ψ t i = φ(S t i ) φ(S K i ) , then:

ψ t 1 > ψ t 2 ( 15
)
The inequality is strict as assumed in 1/ of the Theorem 1. User 1 is scheduled at t with the condition of existence of a time K if and only if the three conditions below are verified:

Inequality(15), a 1 (t) + a 2 (t) = 1, a 1 (t), a 2 (t) ≥ 0.
Theorem 2. If we suppose that a time K exists then for all time t = K the users 1 and 2 are scheduled with the following scheduling strategy:

a 1 (t) = 1 ψ t 1 ≥ψ t 2 a 2 (t) = 1 ψ t 2 ≥ψ t 1 (16)
We can now check if a certain K exists by verifying if for both users a i (K) > 0 using Theorem 2. If it is not the case then K does not exist. a 1 (K) > 0 and a 2 (K) > 0 can be written as following (see within proof of Theorem 3 in Annexe):

a 1 (K) = 1 φ(S K 1 ) (( -ν K φ(S K 1 ) ) -1/α - t =K φ(S t 1 )1 ψ t 1 ≥ψ t 2 ) > 0 (17) a 2 (K) = 1 φ(S K 2 ) (( -ν K φ(S K 2 ) ) -1/α - t =K φ(S t 2 )1 ψ t 2 ≥ψ t 1 ) > 0, (18)
where

ν K = - (φ(S K 1 ) 1/α-1 +φ(S K 2 ) 1/α-1 ) α (1+ t =K ψ t 1 1 ψ t 1 ≥ψ t 2 +ψ t 2 1 ψ t 2 ≥ψ t 1 ) α . Note that a 2 (t) = 1 -a 1 (t). Using φ(S K i )ψ t i = φ(S t i ), denoting by φ 1 = φ(S K 1 ) and φ 2 = φ(S K
2 ), and using ( 17) and (18), we can summarize the result in Theorem 3 below. Theorem 3. K exists if and only if the following two inequalities are verified:

φ 1 α 2 t =K φ(S t 1 )1 ψ t 1 >ψ t 2 -φ 1 α 1 t =K φ(S t 2 )1 ψ t 2 >ψ t 1 < φ 1 α 1 φ 2 , -φ 1 α 2 t =K φ(S t 1 )1 ψ t 1 >ψ t 2 + φ 1 α 1 t =K φ(S t 2 )1 ψ t 2 >ψ t 1 < φ 1 α 2 φ 1 . (19)
If one of the conditions of Theorem 3 is not verified then time K does not exist and another scheduling strategy (rule) should be derived as described presently.

3) If time K does not exist: We suppose in this section that at time u = 1 user 1 is scheduled and therefore λ 1,1 = 0. We need to verify this assumption, namely that user 1 is indeed selected at time u = 1. For all time t, the sign of λ 1,t -λ 2,t determines the scheduling decision: if it is positive then the user 2 is scheduled at time t (λ 1,t ≥ λ 2,t ⇐⇒ a 2 (t) ≥ a 1 (t) by equation (10)). One of the lambdas must be null and the other one positive for the case of two users.

With equation (12), as λ 1,1 = 0, we have:

λ 1,t -λ 2,t = ν 1 ψ t/1 1 -ν 1 ψ t/1 2 -λ 2,1 ψ t/1 2 (20)
where ψ t/u i = φ(S t i ) φ(S u i ) . We have then:

As λ 2,1 ψ t/1 2 > 0 we divide the equation (21) by λ 2,1 ψ t/1 2 and hence the sign studied is the same as the sign of

-1. Note that from (6), ν 1 is negative.

then λ 1,t -λ 2,t < 0 hence user 1 will be scheduled at time t. We cannot say more using this method.

Theorem 4. If user 1 is supposed scheduled at time u = 1, then:

=⇒ user 1 is scheduled at time t.

Denote by A u

1 and A u 2 the following sets:

For u = 1 and using Theorem 4 i.e. if t ∈ A 1 then we have that user 1 is surely scheduled at time t > 1 with the assumption that the user is scheduled at time 1. We have the following result (with the corresponding proof in the Annexe):

Theorem 5. User 1 is scheduled at time u if and only if:

Equivalent scheduling rule can be written for user 2.

III. ANNEXE Proof of Theorem 1:

Suppose that the two users are scheduled together at two time instants K and h, then using the equivalence (9) and (12) thus:

, therefore:

The data rates are almost surely not equal between users, as two users will never have two same positions in space at the same time, hence they cannot be scheduled simultanesouly in more than one time instance.

Proof of Theorem 3:

If we suppose that the two users (1 and 2) are scheduled at some time K i.e. a i (K) = 0 with i ∈ {1, 2}, and that T > 1, then according to Theorem 2 for all times t = K there is at most one user scheduled at time t. Let i 1 and i 2 be in {1, 2}, and for all i ∈ {1, 2}:

Therefore:

We know that:

then we have:

We can now check if really a certain K exists or not by verifying whether a i (K) > 0 for i = 1, 2 supposing the scheduling allocation for t = K satisfies eq.16 in Theorem 2. If it is not the case then K does not exist. a 1 (K) and a 2 (K) are then expressed as follows:

)

)

with ν K defined in equation ( 26). Therefeore a 2 (K) > 0 is equivalent to:

We multiply the both sides of the inequality with the both denominators we have then:

Using φ(S K i )ψ t 1 = φ(S t i ), and denote by φ 1 for φ(S K 1 ) and φ 2 for φ(S K 2 ) the last inequality is equivalent to:

and a 1 (K) > 0 is equivalent to:

If the inequalities (31) and (III) are verified then we have an expression for a 1 (K) and a 2 (K), and for all t = K the user i(t) scheduled is:

.

Proof of Theorem 5:

1/ We first demonstrate "if user 1 is scheduled at time u = 1 then we have the inequatiy of Theorem 5":

Using KKT condition with λ 2,1 ≥ 0 then for user 2:

and for user 1 λ 1,1 = 0:

or written differently:

(34) Using the fact that if ψ t 1 > ψ t 2 the user 1 is scheduled in time t. For sake of simplicity, we denote by

is scheduled at time t, hence from inequality (34) we deduce:

Since 0 ≤ a 2 (j) ≤ 1:

This inequality must also be valid for all k ∈ A 1 if user 1 is selected at time t = 1:

Consider next the case where λ 2,1 = 0 (rarely occurs when user 2 is not scheduled), therefore from equation (21):

From the sign of (38), user 1 is scheduled if and only if t ∈ A 1 and user 2 is scheduled at any t ∈ A 2 . Using equations ( 31) and (32):

We can write:

and a similar expression can be written for user 2. If t ∈ A 1 we have:

2/ We demonstrate the reciprocal "if we have the inequality of the theorem 5 then the user 1 is scheduled at time u=1": ⇐ we suppose that; which is a contradiction, and therefore user 1 is scheduled if the inequality of theorem 5 is verified. The theorem is valid for all time u.