Pierre Lescanne

The risk of divergence

Keywords: divergence, decision, infinite game, sequential game, coinduction

We present infinite extensive strategy profiles with perfect information and we show that replacing finite by infinite changes the notions and the reasoning tools. The presentation uses a formalism recently developed by logicians and computer science theoreticians, called coinduction. This builds a bridge between economic game theory and the most recent advance in theoretical computer science and logic. The key result is that rational agents may have strategy leading to divergence.

Introduction

Strategies are well described in the framework of sequential games, aka. games in extensive forms with perfect information. In this paper, we describe rational strategies leading to divergence. 1 Indeed divergence understands that the games, the strategies and the strategy profiles are infinite. We present the notion of infinite strategy profiles together with the logical framework to reason on those objects, namely coinduction.

Decisions in Finite Strategy Profiles

To present strategy reasoning, we use one of the most popular framework, namely extensive games with perfect information ( [START_REF] Osborne | An Introduction to Game Theory[END_REF] Chapter 5 or [START_REF] Hargreaves-Heap | Game Theory: A Critical Introduction[END_REF]) and we adopt its terminology. In particular we call strategy profile an organized set of strategies, merging the decisions of the agents. This organization mimics this of the game and has the same structure as the game itself. They form the set2 StratProf. By "organized", we mean that the strategic decisions are associated with the nodes of a tree which correspond to positions where agents have to take decisions. In our approach strategy profiles are first class citizens and games are byproduct. In other words, strategy profiles are defined first and extensive games are no more than strategy profiles where all the decisions have been erased. Therefore we will only speak about strategy profiles, keeping in mind the underlying extensive game, but without giving them a formal definition 3 . For simplicity and without loss of generality, we consider only dyadic strategy profiles (i.e.; double choice strategy profiles) , that are strategy profiles with only two choices at each position. Indeed it is easy to figure out how multiple choice extensive strategy profiles can be represented by double choice extensive strategy profiles. We let the reader imagine such an embedding. Therefore, we consider a set of choices: Choice = {1, 2}.

Along the paper, our examples need only a set of two agents: Agent = {A, B}. In this paper we use coinduction and corecursion as basic tools for reasoning correctly about and defining properly infinite objects. Readers who want to know more about those concepts are advised to read introductory papers [START_REF] Jacobs | Introduction to Coalgebra. Towards Mathematics of States and Observations[END_REF][START_REF] Jan | Universal coalgebra: a theory of systems[END_REF], while specific applications to infinite strategy profiles and games are introduced in [START_REF] Lescanne | Intelligent escalation and the principle of relativity[END_REF].

Definition 1 A finite strategy profile is defined by induction as follows:

• either given a utility assignment u (i.e., a function u : Agent → R) u is a finite strategy profile, which corresponds to an ending position.

• or given an agent a, a choice c and two finite strategy profiles s 1 and s 2 , a, c, s 1 , s 2 is a finite strategy profile.

For instance, a strategy profile can be drawn easily with the convention that 1 is represented by going down and 2 is represented by going right. The chosen transition is represented by a double arrow 7 E . The other transition is represented by a simple arrow A A . For instance

G G A 2 3 A 1 Ù Ù B 2 7 7 1 Õ 0, 5 1, 0.5 2, 1
is a graphic representation of the strategy profile

s α = A, 2, A → 1, B → 0.5 , B, 1, A → 2, B → 1 , A → 0, B → 5 .
From a finite strategy profile, say s, we can define a utility assignment, which we write s and which we define as follows:

• u = u • a, c, s 1 , s 2 = case c of 1 → s 1 | 2 → s 2 For instance s α (A) = 2 and s α (B) = 1.
We define an equivalence s = g s among finite strategy profiles, which we read as "s and s have the same (underlying) game".

Definition 2

We say that two strategy profiles s and s have the same game and we write s = g s iff by induction

• either s = u and s = u

• or s = a, c, s 1 , s 2 and s = a , c , s 1 , s 2 and a = a , s 1 = g s 1 and s 2 = g s 2 .

We can define a family of finite strategy profiles that are of interest for decisions. First we start with backward induction. Following [START_REF] Vestergaard | A Constructive Approach to Sequential Nash Equilibria[END_REF], we consider 'backward induction', not as a reasoning method, but as a predicate that specifies some strategy profiles.

Definition 3 (Backward induction) A finite strategy profile s is backward induction if it satisfies the predicate BI, where BI is defined recursively as follows:

• BI( u ), i.e., by definition an ending position is 'backward induction'.

• BI( a, 1, s 1 , s 2 ) ⇔ BI(s 1 ) ∧ BI(s 2 ) ∧ s 1 ≥ s 2 . • BI( a, 2, s 1 , s 2 ) ⇔ BI(s 1 ) ∧ BI(s 2 ) ∧ s 2 ≥ s 1 .
In other words, a strategy profile which is not an ending position is 'backward induction' if both its direct strategy subprofiles are and if the choice leads to a better utility, as shown by the comparison of the utility assignments to the direct strategy subprofiles. The two following strategy profiles are 'backward induction' [START_REF] Osborne | An Introduction to Game Theory[END_REF](Example 158.1)

G G A 2 7 7 1 Õ B 2 7 7 1 Õ 2, 1 1, 2 0, 1 G G A 2 3 A 1 Ù Ù B 2 3 A 1 Ù Ù 2, 1 1, 2 0, 1
An agent is rational if she makes a choice dictated by backward induction and if she keeps being rational in the future. We write this predicate Rat f where the index f insists on finiteness making it distinct from the predicate Rat ∞ on infinite strategy profiles.

Definition 4 (Rationality for finite strategy profiles) The predicate Rat f is defined recursively as follows:

• Rat f ( u ), • Rat f ( a, c, s 1 , s 2 ) ⇔ ∃ a, c, s 1 , s 2 ∈ StratProf, -a, c, s 1 , s 2 = g a, c, s 1 , s 2 -BI( a, c, s 1 , s 2 ) -Rat f (s c )
Then we can state a variant of Aumann theorem [START_REF] Aumann | Backward Induction and Common Knowledge of Rationality[END_REF] saying that backward induction coincides with rationality.

Theorem 5 ∀s ∈ StratProf, Rat f (s) ⇔ BI(s).

Decisions in Infinite Strategy Profiles

We extend the concept of backward induction and the concept of rationality to infinite strategy profiles. For that, we replace induction by coinduction. 4 Notice that we mix up recursive and corecursive definitions, and that we reason sometime by induction and sometime by coinduction. Therefore we advise the reader to be cautious and to pay attention to when we use one or the other. 5 We write InfStratProf the set of finite or infinite strategy profiles.

Definition 6

The set finite or infinite strategy profiles InfStratProf is defined corecursively as follows:

• either given a utility assignment u, then u ∈ InfStratProf, which corresponds to an ending position.

• or given an agent a, a choice c and two strategy profiles

s 1 ∈ InfStratProf and s 2 ∈ InfStratProf, then a, c, s 1 , s 2 ∈ InfStratProf.
We cannot define the utility assignments on all infinite strategy profiles, only on those on which the utility can be "computed". The strategy profiles on which utility assignments are defined are called convergent, since when one follows the path indicated by the choices one "converges", that is that one gets to an ending position, i.e., a position where utilities are actually attributed. The predicate convergent is defined by induction, meaning that, on s, after finitely many steps following the choices of s an ending position is reached. "Finitely many steps" is a finite aspect and this is why we use an inductive definition.

Definition 7 (Convergent) Saying that s is convergent is written ↓ s. ↓ s is defined by induction as follows:

• ↓ u or • if ↓ s 1 then ↓ a, 1, s 1 , s 2 or • if ↓ s 2 then ↓ a, 2, s 1 , s 2 or
On convergent strategy profiles we can assign utilities. The resulting function is written ŝ when applied to a strategy profile s.

Definition 8 (Utility assignment) ŝ is defined corecursively on every strategy profile.

when s = u s = f when s = a, 1, s 1 , s 2 s = s 1 when s = a, 2, s 1 , s 2 s = s 2
The function • has to be specified on an infinite object and this is why we use a corecursive definition.

Proposition 9 If ↓ s, then ŝ returns a value.

Actually convergent strategy profiles are not enough as we need to know the utility assignment not only on the whole strategy profile but also on strategy subprofiles. For that, we need to insure that from any internal position we can reach an ending position, which yields that on any position we can assign a utility. We call always-convergent such a predicate 6 and we write it ↓.

Definition 10 (Always-convergent) 5 Notice that not all the authors are as cautious. For instance, Hargreaves-Heap and Varoufakis write ( [START_REF] Hargreaves-Heap | Game Theory: A Critical Introduction[END_REF] p.27) "The idea [of common knowledge] reminds one what happens when a camera is pointing to a television screen that conveys the same image recorded by the same camera: an infinite self-reflection". Indeed common knowledge is typically inductive whereas infinite self-reflection is typically coinductive. 6 Traditionally is the notation for the modality (i.e., the predicate transformer) always.

• ↓ u that is that for whatever u, u is always-convergent

• ↓ a, c, s 1 , s 2 if
a, c, s 1 , s 2 is convergent (i.e., ↓ a, c, s 1 , s 2 ), and s 1 is always-convergent (i.e., ↓ s 1 ), and s 2 is always-convergent (i.e., ↓ s 2 ).

Proposition 11 ↓ s ⇒ ↓ s.
s 2 in Figure 1 is a typically non convergent strategy profile, wherever s 12 2 in the same figure is a typically convergent and not always-convergent strategy profile.

G G A 2 3 A 1 Ù Ù B 2 i 1 Ù Ù 1, 0 0, 1 G G A 2 B B 1 Õ B 2 8 F 1 Ù Ù A 2 3 A 1 Ù Ù B 2 i 1 Ù Ù 0, 1 1, 0 0, 1 1, 0 s 2 s 1 2
Figure 1: Two examples of strategy profiles Using the concept of always-convergence we can generalize the notion of backward induction to this that the tradition calls subgame perfect equilibrium [START_REF] Selten | Spieltheoretische Behandlung eines Oligopolmodells mit Nachfrageträgheit[END_REF] and which we write here SPE. In short SPE is a corecursive generalization of BI. First we define an auxiliary predicate.

Definition 12 (PE)

PE(s) ⇔ ↓ s ∧ s = a, 1, s 1 , s 2 ⇒ s 1 (a) ≥ s 2 (a) ∧ s = a, 2, s 1 , s 2 ⇒ s 2 (a) ≥ s 1 (a)
We define SPE as always-PE. In other words, a strategy profile s is a subgame perfect equilibrium if PE(s). applies to a predicate.

Definition 13 (Always) Given a predicate P, the predicate P is defined corecursively as follows.

• if P( u ) then P( u ) and

• if P(s 1 ), P(s 2 ) and P( a, c, s 1 , s 2 ) then P( a, c, s 1 , s 2 )

Formally SPE is PE. Besides we may notice that the notation used for alwaysconvergence (Definition 10) is consistent with Definition 13. Now thanks to SPE we can give a notion of rationality for infinite strategy profiles. Like for finite strategy profiles we define corecursively, this time, an equivalence s = g s on infinite strategy profiles (read s and s have the same game). Two strategy profiles have the same game if at each step, they have the same agent and their respective direct strategy subprofiles have the same game and only the choices differ.

Definition 14

We say that two strategy profiles s and s have the same game and we write s = g s iff corecursively

• either s = u and s = u

• or s = a, c, s 1 , s 2 and s = a , c , s 1 , s 2 and a = a , s 1 = g s 1 and s 2 = g s 2 .

Definition 15 (Rationality for finite or infinite strategy profiles) Rat ∞ is defined corecursively as follows.

• Rat ∞ ( u ),

• Rat ∞ ( a, c, s 1 , s 2 ) ⇔ ∃ a, c, s 1 , s 2 ∈ InfStratProf, a, c, s 1 , s 2 = g a, c, s 1 , s 2 ∧ SPE( a, c, s 1 , s 2 ) ∧ Rat ∞ (s c )
The reader may notice the similarity with Definition 4 of rationality for finite games.

The difference is twofold: the definition is corecursive instead of recursive and BI has been replaced by SPE. Let us now define a predicate that states the opposite of convergence 7 Definition 16 (Divergence) ↑ s is defined corecursively as follows:

• if ↑ s 1 then ↑ a, 1, s 1 , s 2 , • if ↑ s 2 then ↑ a, 2, s 1 , s 2 .
s 2 in Figure 1 is a typical divergent strategy profile. The main theorem of this paper can then be stated, saying that there exists a strategy profile that is both divergent and rational.

Theorem 17 (Risk of divergence) ∃s ∈ InfStratProf, Rat ∞ (s) ∧ ↑ s.

Witnesses of divergent and rational strategy profiles will be given in Section 4.2 and Section 5.

Extrapolating the centipede

As an illustration of the above concepts, we show, in this section, two simple extensions to infinity of a folklore example. The centipede has been proposed by Rosenthal [START_REF] Rosenthal | Games of perfect information, predatory pricing and the chainstore paradox[END_REF]. Starting from a wording suggested by Aumann [START_REF] Aumann | Backward Induction and Common Knowledge of Rationality[END_REF] we study two infinite generalization 8 . Wikipedia [START_REF]Centipede game -Wikipedia, The Free Encyclopedia[END_REF] says: Consider two players: Alice and Bob. Alice moves first. At the start of the game, Alice has two piles of coins in front of her: one pile contains 4 coins and the other pile contains 1 coin. Each player has two moves available: either "take" the larger pile of coins and give the smaller pile to the other player or "push" both piles across the table to the other player. Each time the piles of coins pass across the table, the quantity of coins in each pile doubles. 7 People used to coinduction know why it is better to define divergence directly instead of defining it as the negation of convergence. 8 The reason why we call them ∞pede and ωpede. 4.1 The ∞pede P ∞ (s) is a set of strategy profiles extending the strategy profiles of the centipede. Such an infinite strategy profile can only be is sketched on Figure 2 . Actually proposing an infinite extension of the centipede is quite natural for two reasons. First there is no natural way to make the game finite. Indeed in the definition of the game, nothing precise is said about its end, when no player decides to take a pile. For instance, Wikipedia [START_REF]Centipede game -Wikipedia, The Free Encyclopedia[END_REF] says:

G G A 2 8 F 1 Ø Ø B 2 8 F 1 Ø Ø A 2 8 F 1 Ø Ø B 2 B B 1 Ô A 2 8 F 1 Ø Ø B 2 B B 1 Ô A 2 6 D 1 Ø Ø 1 8 8 2 Ø Ø 4,
The game continues for a fixed number of rounds or until a player decides to end the game by pocketing a pile of coins.

We do no know what the utilities are in the end position described as "a fixed number of rounds". Since A started, we can assume that the end after a fixed number of rounds is B's turn and that there are outcomes like:

1. B receives 2 n+1 coins and A receives 2 n+3 coins like for the previous B rounds and that is all.

2. B chooses between (a) receiving 2 n+1 coins whereas A receives 2 n+3 or (b) sharing with A, each one receiving 2 n+2 .

3. Both A and B receive nothing.

Moreover the statement "Each player has two moves available: either "take" ... or push..." is not true, in the ending position. We are not hair-splitting since the end positions are the initializations of the (backward) induction and must be defined as precisely as the induction step. Ending with 2.(b) does not produce the same backward induction as the others. Let us consider the strategy profiles

p n = A, 1, A → 2 2n+2 , B → 2 2n , π n π n = B, 1, A → 2 2n+1 , B → 2 2n+3 , p n+1
In words, the p n 's and the π n 's are the strategy subprofiles of the ∞pede in which Alice and Bob stop always. Notice that

p n (A) = 2 2n+2 p n (B) = 2 2n π n (A) = 2 2n+1 π n (B) = 2 2n+3
Theorem 18

1. ∀n ∈ N, SPE(p n ) ∧ SPE(π n ), 2. ∀s ∈ InfStratProf, s = g p 0 ∧ SPE(s) ⇔ s = p 0 .
In other words, all the p n 's and the π n 's are 'backward induction'. Moreover for the ∞pede, p 0 is the only 'backward induction'. strategy profile.

Proof: One can easily prove that for all n, ↓ p n and ↓ π n .

Assuming SPE(π n ) and SPE(p n+1 ) (coinduction) and since

A → 2 2n+2 , B → 2 2n (A) ≥ π n (A) we conclude that SPE( A, 1, A → 2 2n+2 , B → 2 2n , π n ) that is SPE(p n ). The proof of SPE(π n ) is similar.
For the proof of 2. we notice that in a strategy profile in SPE with the same game as p 0 , there is no strategy subprofile such that the agent chooses 2 and the next agent chooses 1. Assume the strategy subprofile is

s n = A, 2, A → 2 2n+2 , B → 2 2n , B, 1, A → 2 2n+1 , B → 2 2n+3 , σ n .
ans that SPE(s n ) and SPE(σ n ). If it would be the case and if we write

t = A → 2 2n+2 , B → 2 2n and t = B, 1, A → 2 2n+1 , B → 2 2n+3 , σ n , we notice that t(A) = 2 2n+2 > t (A) = 2 2n+1 . This is in contradiction with SPE(s n ).
We deduce that the strategy profile d 0 , which diverges, is not in Rat ∞ and more generally there is no strategy profile in Rat ∞ for the ∞pede.

d n = A, 2, A → 2 2n+2 , B → 2 2n , π n δ n = B, 2, A → 2 2n+1 , B → 2 2n+3 , p n+1 G G A 2 B B 1 Ô B 2 B B 1 Ô A 2 B B 1 Ô B 2 B B 1 Ô A 2 B B 1 Ô B 2 B B 1 Ô A 2 @ @ 1 Ô 1 8 8 2 Ø Ø 4,
G G A 2 8 F 1 Ø Ø B 2 8 F 1 Ø Ø A 2 8 F 1 Ø Ø B 2 8 F 1 Ø Ø A 2 8 F 1 Ø Ø B 2 8 F 1 Ø Ø A 2 6 D 1 Ø Ø 1 8 8 2 Ø Ø 4,

The ωpede

We know 9 that "trees don't grow to the sky". In our case this means that there is a natural number ω after which piles cannot be doubled.footnotePeople speak of limited payroll. In other words, after ω, the piles keep the same size 2 ω . An example of strategy profile is sketched on Figure 4. In this family of strategy profiles, which we write P ω , the utilities stay stable after the ω th positions. Every always-convergent strategy profile of P ω , such that agents push until ω is in SPE. We conclude the existence of rational divergent strategy profiles in P ω . In other words in the ω pede there is a risk of divergence. Theorem 19 ∃s ∈ P ω , Rat ∞ (s)∧ ↑ s.

G G A 2 8 F 1 Ø Ø B 2 8 F 1 Ø Ø A 2 8 F 1 Ø Ø B 2 4 B 1 Ø Ø 8 F A 2 8 F 1 Ø Ø B 2 B B 1 Ô A 2 8
One may imagine that divergence is when optimistic agents hope a reverse of the tendency.

Comments:

The ωpede example is degenerated, but it is interesting in two respects. First, it shows a very simple and naive case of rational divergence. Second it shows that cutting the infinite game, case 2. (b) is the most natural way, with a equilibrium in which agents take until the end.

5 Two examples 0, 1 strategy profiles 0, 1 strategy profiles are strategy profiles with the shape of an infinite "comb" in which the utilities are 0 for the agent who quits and 1 for the other agent. It can be shown [START_REF] Lescanne | A Simple Case of Rationality of Escalation[END_REF] that strategy profiles where one agent continues always and the other quits infinitely often (in other words the other agent never continues always) are in SPE. For this reason, the strategy profile where both agents continue always is in Rat ∞ , which shows that divergence is rational.

The dollar auction The dollar auction is a well known game [START_REF] Shubik | The Dollar auction game: A paradox in noncooperative behavior and escalation[END_REF][START_REF] Leininger | Escalation and cooperation in conflict situations[END_REF][START_REF] Barry | International escalation and the dollar auction[END_REF]. Its strategy profiles have the same infinite comb shape as the 0, 1 strategy profiles, the ∞pede and the ωpede with the sequence of pairs of utilities:

(0, 100) (95, 0) (-5, 95) (90, -5) (-10, 90) (85, -10) . . . (-5n, 100 -5n) (100 -5(n + 1), -5n) . . . and corresponds to an auction in which the bet of the looser is not returned to her. We have shown [START_REF] Lescanne | Backward" coinduction, Nash equilibrium and the rationality of escalation[END_REF] that the dollar auction may diverge with rational agents. People speak of escalation in this case. The divergent strategy profile of the dollar auction is in Rat ∞ .

Reflection

Je est un autre (I is another) Arthur Rimbaud (1854-1891)

Examples like the dollar auction or the 0, 1 raise the following question: "How is it possible in an escalation that the agents do not see that they are entering a hopeless process?". The answer is "reflection". Indeed, when reasoning, betting and choosing, the agents should leave the world where they live and act in order to observe the divergence. If they are wise, they change their beliefs in an infinite world as soon as they realize that they go nowhere [START_REF] Stanovich | Two minds: Dual processis and beyond[END_REF]. This ability is called reflection and is connected to observability, from the theoretical computer science point of view, which is itself connected to coalgebras and to coinduction [START_REF] Jacobs | Introduction to Coalgebra. Towards Mathematics of States and Observations[END_REF]. In other words, agents should leave the environment in which they are enclosed and observe themselves.Like the poet, they should be able to claim "I is another" whom I consider as an object.

Singularities and divergence

Divergence is called singularity, bubble, crash, escalation, or turbulence according to the context or the scientific field. In mechanics this is considered as a topics by itself. Leonardo da Vinci's drawings (Fig. 5 left)show that he considered early turbulence and vortices and only Reynolds during the XIX th century studied it from a scientific point of view. In many other domains, phenomena of this family are rejected from the core of the field, despite they have been observed experimentally. Scientists, among them mainstream economists [START_REF] Colander | The Changing Face of Mainstream Economics[END_REF], prefer smoothness, continuity and equilibria [START_REF] Weintraub | Neoclassical Economics. Library of Economics and Liberty[END_REF] and they often claim that departing from this leads to "paradoxes" [START_REF] Shubik | The Dollar auction game: A paradox in noncooperative behavior and escalation[END_REF]. In [START_REF] Lescanne | Rationality and Escalation in Infinite Extensive Games[END_REF], we surveyed Zeno of Elea's paradox from the point of view of coinduction, as well as Weierstrass function [START_REF] Weierstrass | Über continuirliche Funktionen eines reellen Arguments, die für keinen Werth des letzteren einen bestimmten Differentialquotienten besitzen[END_REF], the first mathematical example showing discontinuity at the infinite.

Here we would like to address two other cases. In 1935, that is one year before his , Alan Turing wrote a paper [START_REF] Turing | First draft of précis of 'Computable Numbers[END_REF] presenting his result for a publication in the Proceedings of the French Academy of Science. In this paper he calls "nasty" a machine that terminates and "nice" a machine that does not terminate, showing his positive view of non ter-minating computations. 10 In 1795, Laplace published his book Exposition du Système du Monde and proposed the first clear vision of the notion of blackhole(Fig. 5 right), but probably in order not to hurt his contemporaries, he found wiser to remove this presentation from the third edition of his book. Then we had to wait Schwartzschild in 1915, few months after the publication by Einstein of the general theory of relativity, for a second proposal of the concept of blackhole. But at that time the general relativity was not yet fully accepted as were not blackholes. Only recently, at the end of the last century, the general relativity has been considered as "the" theory of gravitation and there is no more doubt on the existence of blackholes. Since blackholes are singularities in gravitation, they are for the general theory of relativity the equivalent of divergent strategy profiles for game theory.

Contribution of this paper

Unlike previous presentations of similar results [START_REF] Lescanne | Backward" coinduction, Nash equilibrium and the rationality of escalation[END_REF][START_REF] Lescanne | A Simple Case of Rationality of Escalation[END_REF][START_REF] Vestergaard | Cascaded Games[END_REF] here we focus on the concept of strategy profile which is central for the those of convergence, of divergence and of equilibrium and is more targeted for a workshop on strategy reasoning. Moreover we introduce the ωpede (a new infinite version of the centipede) and "divergent" strategy profiles are those that where called "escalation" in previous literature. This terminology seems better fitted for its duality with convergence.

Conclusion

We have shown that strategy profiles in which no fixed limit is set must be studied as infinite objects using coinduction and corecursion. In these infinite objects, the risk of divergence is real and should be considered seriously.

Figure 2 :

 2 Figure 2: A sketch of a strategy profile of the ∞pede.

Figure 3 :

 3 Figure 3: Strategy profiles p 0 and d 0 of the ∞pede.

Figure 4 :

 4 Figure 4: A 'backward induction' strategy profile for the ωpede.

Figure 5 :

 5 Figure 5: Da Vinci's drawings (left) and a artist view of a blackhole (right) Wikimedia commons

  [START_REF] Lescanne | A Simple Case of Rationality of Escalation[END_REF]

							1
							Ô
	4, 1	2, 8	16, 4	8, 32	2 ω , 2 ω	2 ω , 2 ω	2 ω , 2 ω

In this paper we use "divergence" instead of "escalation" since it is somewhat dual convergence a concept which plays a key role in what follows.

To be correct, we should say the "they form the coalgebra".

A direct definition of games is possible, but is not necessary in this paper.

For readers not familiar with coinduction and not willing to read[START_REF] Jacobs | Introduction to Coalgebra. Towards Mathematics of States and Observations[END_REF] or[START_REF] Jan | Universal coalgebra: a theory of systems[END_REF], we advise her to pretend just that corecursive definitions define infinite objects and coinduction allows reasoning specifically on their infinite aspects, whereas recursive definition define finite objects and induction allows reasoning on their finite aspects.

Usually agents do not believe this. See[START_REF] Lescanne | Intelligent escalation and the principle of relativity[END_REF] for a discussion of the beliefs of the agents w.r.t. the infiniteness of the world.

The risk of divergence

Notice that he changed his terminology in[START_REF] Turing | First draft of précis of 'Computable Numbers[END_REF] and calls "circular" the terminating machine and "circular-free" the non terminating machine.


Arturo Guizar
email: arturo.guizar@insa-lyon.fr

Claire Goursaud
email: claire.goursaud@insa-lyon.fr

Jean-Marie Gorce
email: jean-marie.gorce@insa-lyon.fr

Modeling the Impact of node speed on the ranging estimation with UWB Body Area Networks

The purpose of this paper is to evaluate the impact of the node speed on the ranging estimation for location applications with Wireless Body Area Networks (WBAN). While estimated with the 3-Way ranging protocol (3-WR) , this distance between two nodes placed on the body can be affected by the human movements. Thus, we study theoretically the ranging error with the 3-WR, based on a perfect channel, a MAC layer based on TDMA using two scheduling strategies (Single node localization (P2P-B) and Aggregated & Broadcast (A&B)) and a PHY layer based on Ultra Wideband (IR-UWB). We demonstrate the accuracy of the model, and show that the distance error is highly correlated with the speed of nodes, while the associated mobility model has an impact on the design of MAC strategies by simulation.

I. INTRODUCTION

Wireless Body Area Networks (WBAN) refers to a new disruptive technology composed of a group of nodes embedded on a person. These nodes communicate with each other for diverse applications, e.g. sport analysis, civil security or ehealth [START_REF] Cavallari | A survey on wireless body area networks: Technologies and design challenges[END_REF]. In this context, radio-location techniques are highly studied, because there is a strong interest for the analysis of body movement. This is possible, among others techniques, with the transmission of pulses in Ultra Wideband (IR-UWB) [START_REF] Xiao | A survey on impulse-radio UWB localization[END_REF]. The high temporal resolution of the pulses makes possible to calculate the distance between two nodes by estimating the the Time of Flight (ToF) of three packets as defined by the Three Way Ranging Protocol (3-WR). Several research works have addressed the localization problems with IR-UWB, particularly to compensate the clock's desynchronization and the channel effects [START_REF] Soganci | Accurate positioning in ultrawideband systems[END_REF]. However, most of studies suggest solutions for static or low mobile nodes in Wireless Sensor Networks (WSN). In the case of WBAN, nodes are affected by different variations in the speed of the human body. Therefore, the distances estimated vary during the 3-WR transactions, inducing positioning errors (Fig. 1).

The goal of this work is to analyze the impact of speed on the ranging estimation. For this, we propose a theoretical model that takes into account this impact. Then, we show the relation of speed of nodes with the estimated distances by evaluating our theoretical model with the simulated ranging estimation. Moreover, we give some important key points to consider when designing MAC protocols to perform localization applications. Our results show a high correlation between the type of performed movement (and therefore, the speed of nodes) and the error in the ranging estimation.

The remaining of the paper is organized as follows. Section II briefly describes the network configuration involved for the localization purposes, along with the realistic mobility model description. In Section III, we present our theoretical model and we describe the MAC strategies used for the simulation by giving the main assessments. Section IV reports the results for both theoretical and simulated ranging errors obtained through discrete-event simulation. Finally, Section V draws the conclusion and perspectives of this work.

II. SYSTEM MODEL

A. Network Topology

In this work, we consider a wireless body area network (WBAN) embedded on a person. This network is considered as full-mesh and all nodes (N t ) can directly communicate in pairs. We use a physical layer based on Ultra Wide Band (UWB) pulses. The network is characterized by two types of sensors: the anchor nodes that have perfect knowledge of their position at any time and the mobile nodes who want to estimate their position. The anchors perform a Local Coordinate System (LCS) associated with the body, which is mobile under a Global Coordinate System (GCS). To achieve the localization, a node i must estimate its distance with an anchor j, denoted dij (t), then estimate its position Pi (t).

B. Ranging estimation with 3WR

As shown in Figure 2, the distance between an anchor node and a mobile node can be evaluated with the Time of Arrival (ToA) estimation of 3 packets sent at different instants, as defined by the 3-Way Ranging protocol (3-WR) [START_REF] Xiao | A survey on impulse-radio UWB localization[END_REF], i.e. the 3-WR is an extension of the 2-Way Ranging protocol considering the drift clock between the nodes:

• At time t 0 , the node i send a Request packet (Q ij ) to the anchor j.

• At time t 1 , the anchor j answers with a Response 1 packet (R1 ij ). Thus, the node i is able to estimate the Time of Flight (ToF) of the pulses and therefore, a first ranging estimation (2-WR).

• Finally, at t 2 , the anchor j sends a Response 2 packet (R2 ij ). In fact, since the localization precision can be reduced by non-synchronization of clocks between the nodes, this last packet allows to evaluate and compensate the clock drift. From these transactions, we define the times T 1, T 3 and T 5 as the moments where the nodes sends the Q ij , R1 ij and R2 ij packets respectively. Similarly, we note T 2, T 4 and T 6 as the ToA of these same packets respectively. Thus, the distance dij (t) is evaluated with the Equation (1):

dij (t) = 1 2 c [((T 4 -T 1 ) -∆t1) -((T 6 -T 4 ) -∆t2)] (1)
where c represents the speed of pulses transmission (i.e. c = 3 * 10 8 m/s) and ∆t1 (resp. ∆t2) is the delay between (T 3 -T 2 ) (resp. (T 5 -T 3 )).

C. Mobility Model

In this study, we consider a realistic Yoga Model, obtained by measurement. The mobility traces were obtained during the measurement campaign related to the CORMORAN project at the M2S laboratory, ENS Cachan, France in June 2014 [START_REF] Denis | Qualitative Analysis of RSSI Behavior in Cooperative Wireless Body Area Networks for Mobility Detection and Navigation Applications[END_REF]. This model was generated using a motion capture system (Vicon [START_REF]Vicon[END_REF]) based on infrared at a rate of 100Hz. For this, we deployed 16 cameras in a confined space of 10x6 m 2 . Thus, we were able to calculate the position and the instantaneous velocity of each node. Accordingly, we consider a scenario of 100 s which consist in the representation of Yoga activity. The interest in this scenario is the study of the presence or absence of movement which separates the impact of the speed and the other error factors on the accuracy. The series of the static positions (realizing yoga postures (e.g. put both feet together and hands above the head)) is performed in the same place, so only the articulations of the body perform a movement. Here, we consider a network composed of 4 anchors and 4 mobile nodes, as shown in Figure 3(b). The anchors are positioned on the most static parts of the body: the right chest (A 1 ), the left chest (A 2 ), the left hip (A 3 ) and the back (A 4 ). The mobile nodes are located on the right arm (N 5 ), the left arm (N 6 ), the right foot (N 7 ) and the head (N 8 ).

III. MODELING THE RANGING ESTIMATION WITH NODES UNDER MOBILITY

As presented in Section II-B, the 3-Way Ranging protocol was proposed for the ranging estimation between quasi-static nodes. However, WBANs are exposed to strong mobility, having a direct impact on the estimated distances dij (t). In fact, the 3-WR packets travel through varying distances, hence, the ToF change as well. In our previous work [START_REF] Guizar | Impact of MAC scheduling on positioning accuracy for motion capture with UWB body area networks[END_REF], we showed that the ranging accuracy depends on the duration of ∆t1 and ∆t2. In particular, the delay ∆t1 to send the first response R1 ij (t) has more impact than the time taken ∆t2 for the second response R2 ij (t). Therefore, the nodes present a bigger displacement when these delays increase.

A. Theoretical Model

In this study, we aim to quantify the impact of node speed on the ranging estimation. For this, we consider a three-Dimensional Euclidean space (O g , x g , y g , z g ). We define P (t) = --→ OgP as the position vector between the origin point and the node's position at time t. Moreover, we note d ij (t) = P j (t) -P i (t) as the distance vector between node i and anchor j during a 3-WR packet transmission (Q ij , R1 ij and R2 ij ) at a given moment (t).

However, the 3-WR packets (Fig. 2) are sent at different moments, which are long enough to let the nodes move. Therefore, the initial distance is affected by different displacements (t 0 ⇒ t 1 and t 1 ⇒ t 2 ), leading to 3 distances for the same ranging estimation. Note that the distance vector norm is expressed in terms of the speed of propagation of an UWB pulse as || d ij (t)|| = c * (T Rj -T Ei ), where T Ei (resp. T Rj ) represents the moment of a packet transmission (resp. reception) by the node i (resp. j) at time t. As result, Equation (1) can be written as:

dij (t) = 1 2 c [((T 4 -T 3 ) + (T 2 -T 1 )) -((T 6 -T 5 ) -(T 4 -T 3 ))] dij (t) = 1 2 (|| d ij (t 1 )|| + || d ij (t 0 )||) -(|| d ij (t 2 )|| -|| d ij (t 1 )||) dij (t) = 1 2 || d ij (t 0 )|| + 2|| d ij (t 1 )|| -|| d ij (t 2 )|| (2)
In our model, we aim to express dij (t) as a function of the node speed and the initial distance d ij (t 0 ) = P j (t 0 ) -P i (t 0 ). For this, we define the average speed of the node i at time ( P j (t 1 ) -P i (t 1 )) = ( P j (t 0 ) -P i (t 0 )) -( P i (t 1 ) -P i (t 0 )) +( P j (t 1 ) -P j (t 0 ))

d ij (t 1 ) = d ij (t 0 ) -V i (t 1 )(T 4 -T 1 ) + V j (t 1 )∆t1
When using the same relation for d ij (t 2 ), we can obtain the following system of equations with 3 variables:

     d ij (t 0 ) = P j (t 0 ) -P i (t 0 ) d ij (t 1 ) = d ij (t 0 ) -V i (t 1 )(T 4 -T 1 ) + V j (t 1 )∆t1 d ij (t 2 ) = d ij (t 1 ) -V i (t 2 )(T 6 -T 4 ) + V j (t 2 )∆t2 (3)
This proposition is strictly true if we assume that nodes do not move during 1 packet transmission. In practice, this assumption can be considered if we neglect the speed of a node (< 10m/s) compared to the pulse speed propagation (c). Therefore, the movement of nodes between (T 4 -T 3 ) and (T 2 -T 1 ) are negligible. As result, T 4 -T 1 can be written as T 4 -T 1 = (T 4 -T 3 ) + T 3 -T 2 + (T 2 -T 1 ) ∆t1. Similarly, T 6 -T 4 ∆t2 which yields to the simple formulation of the system of equations (3) as:

     d ij (t 0 ) = P j (t 0 ) -P i (t 0 ) d ij (t 1 ) = d ij (t 0 ) -( V i (t 1 ) -V j (t 1 ))∆t1 d ij (t 2 ) = d ij (t 1 ) -( V i (t 2 ) -V j (t 2 ))∆t2 (4)

B. Scheduling MAC Protocols

In this paper, we want to characterize only the impact of speed on the ranging estimation accuracy. For this, we assume a perfect channel and we ignore the shadowing effects of the body. Thus, for positioning in a three-dimensional space, the node estimates its distance with (at least) 4 anchors, and then calculates its position with a positioning algorithm (e.g. TDOA) [START_REF] Xiao | A survey on impulse-radio UWB localization[END_REF]. The frame holds enough slots for an individual location of all nodes. Moreover, ∆t1 and ∆t2 are fixed by the scheduling strategies at the MAC layer. In order to validate our theoretical analysis, we implement two scheduling MAC strategies as the one described in [START_REF] Guizar | Quantifying the impact of scheduling and mobility on IR-UWB localization in body area networks[END_REF]:

• Single node localization (P2P-B) where each node i intend to send the requests Q i to the anchors in broadcast. Then, each anchor answers with R1 ji and R2 ji successively in single-links to the nodes.

• Aggregated and Broadcast (A&B) [START_REF] Macagnano | MAC performances for localization and tracking in wireless sensor networks[END_REF] where nodes send the requests Q i in broadcast. Thereafter, each anchor j gathers the ToA of each request and sends an aggregated response (R1 j ) to all nodes, followed by the second response (R2 j ). Thus, A&B increases the ∆t1 delay even though it reduces the frame size.

IV. PERFORMANCE EVALUATION

A. Simulation tools and methodology

In this work, we adopt a discrete event simulation with WSNet [START_REF] Chelius | [END_REF], suitable for the test of our theoretical model on the experiment movement traces.In particular, we implemented an UWB PHY layer as defined by the standard IEEE802.15.6 in default mode (OOK modulation and 0.4875 Mb/s). At the MAC layer, we implemented a protocol based on TDMA, the P2P-B and A&B algorithms, as detailed in Section III-B. Finally, we created a mobility model which exploits the traces of both scenarios acquired during the CORMORAN project, as described in Section II-C.

Within this framework, we run the simulation on the 100s of data acquisition with our mobility scenario and then, we compare with the calculated theoretical distance with the node speed and the delays ∆t1 and ∆t2 (depending on the MAC scheduling employed for each simulation). The temporal data resolution is the one from the Vicon cameras calibration (one position measured every 10ms).

B. Relation between nodes speed and ranging estimation

First, we consider the Yoga scenario in order to evaluate our model in a case with a controlled and slow evolution of nodes positions. Figure 5(a) shows the speed of nodes calculated from the mobility model. The anchors are quasi-static (Figure not presented), contrary to the mobile nodes (Fig. 5(a)) which move according to the performed Yoga positions (< 3m/s). Therefore, we can assume that our ranging estimation will be affected mostly by the mobile nodes movement.

For a preliminary analysis, we evaluate by simulation the error on the estimated distances and quantify the impact on the design of the MAC layer. For this purpose, we simulated the P2P-B and A&B strategies to perform the 3-WR ranging estimation for the Yoga scenario. For our network composed of 4 anchors and 4 nodes, we use a TDMA frame duration of ≈ 54 ms for P2P-B and ≈ 18 ms for A&B. Figures 5(b) and 5(c) represents the ranging error with P2P-B and A&B respectively, between the mobile nodes and the anchor N 4 (which is the worst case because of a bigger ∆t1). First, we can observe that the ranging error (for both strategies) follows the evolution of the node speed (Fig. 5(a)). Accordingly, we can easily distinguish the static periods (where all nodes have a low speed leading to small errors), and the activity periods (in which at least one node is moving). In fact, we note that not all the nodes move simultaneously, only the hands (N 5 and N 6 ) are always active. Thus, we can differentiate in Figure 6(b) the three main periods of activity: Sb1 (0 -50s), Sb2 (50 -70s) and Sb3 (70 -100s).

In the case of Sb1, the subject raised and dropped both hands several times above his head. Accordingly, the nodes on the hands show the most of variation errors for a node speed depending on the performed postures (Half moon and Mountain poses); whereas the nodes on the foot (N 7 ) and the head (N 8 ) are quasi-static. For Sb2, the person stretches his legs (Warrior pose), which yields in an error on the estimation with N 7 .We can notice that, at the end of this phase, the foot node approaches to the anchor 4 (Tree pose), leading to a positive error. Finally, for Sb3, the subject leans forward to touch his feet with his hands (bend forward pose), which explains the error for nodes N 5 , N 6 and N 7 . Here, the mobile nodes come close to the anchors.

C. Validation of the theoretical model

In this second study, we aim to evaluate our theoretical model by quantifying the error produced by the node speed between the initial distance of a 3-WR transaction (|| d ij (t 0 )||) and the theoretical estimated distance ( dij (t), Eq. 2). Then, we compare this theoretical error with the error obtained by simulation (Figures 5 and6). For this, we fixed ∆t1 and ∆t2 to the delays related with P2P-B and A&B. Figure 6(b) (resp. 6(c)) illustrates the theoretical ranging error on the distances between the nodes and the anchor N 4 with P2P-B (resp. A&B). As before, the theoretical error is correlated with the evolution of the speed of mobile nodes (Fig. 5(a)).

If we analyze our theoretical errors (Figs. 6(b) and 6(c)) with the real distance between nodes and A 4 (Fig. 6(a)), we can observe a clear correspondence with the variation of the distances estimated. In fact, when nodes and anchors move away (resp. get closer), there is an increase (resp. decrease) of the distance estimated by simulation, but also a theoretical negative (resp. positive) error. This is most visible with N 7 in Sb3 where we clearly observe that its distance with A 4 change from ≈ 1.1m (70s) to ≈ 0.55m (72s) leading into a positive error of (≈ 1.2 cm). This kind of information is important to collect in order to make a control of the distance estimations. Knowing when the error is positive or negative give us the key to infer when the nodes are getting closer or not.

Moreover, the theoretical results are similar to the simulated errors for both strategies. However, the error with A&B has visibly an increased level of error in the ranging estimation compared to P2P-B, yet this is not entirely true. In fact, the delay ∆t1 is shorter with P2P-B which favors the ranging accuracy (Section III). On the other hand, A&B reduces the frame duration which means a greater detail of the estimated distances. This is due to the fact that A&B performs 3 times more the motion capture than P2P-B. In other words, P2P-B is able to estimate accurate distances but makes a subsample of motion, preventing the detection of some movements and consequently a greater temporal error, contrary to A&B which detects the movements with more detail even though it presents a higher spatial error. To illustrate this last hypothesis, we can observe at second 30, a high peak variation of speed for N 5 , which is not perceived by the P2P-B protocol, but it is detected by the A&B protocol. This last observation is important because if a localization system requires precise detection of movements at a given time, P2P-B would not be the best option, since the duration of the frame skips some movements.

Finally, the difference between the simulated errors and theoretical errors (for both strategies) is due to the limit of simulation related to the mobility model. In our case, the vicon system was calibrated to detect the node's positions every 10ms. Since each MAC strategy has different frame duration, the ranging estimation will be affected by the mobility model sampling. However, the theoretical model has not such a problem because it calculates the speed progressively. To illustrate this, Figure 7 shows the theoretical error with the P2P-B delays for anchors A 1 , A 2 and A 3 . We observe for all the cases, that the error evolves with the speed and the delays for each anchor. But this is not the case in the simulation for P2P-B. If the duration of one 3-WR transaction is lower than 10ms, the level of error will not be affected by the speed, since the simulation change the positions of nodes according to the mobility sampling. Considering this issue with more anchors, we can expect to have the same level of ranging error with the anchors performing their transactions during the same interval. Therefore, when designing MAC protocols through simulation, it is necessary to consider the correct sampling of mobility to achieve accurate performance results.

V. CONCLUSION

In this paper, we investigated the impact of speed on the ranging estimation of mobile nodes in a WBAN. We modeled this impact with a theoretical model of the 3-WR protocol with nodes under mobility. Then, we quantified this effect by using a realistic Yoga scenario and we evaluate the ranging error by simulation with two MAC strategies: P2P-B and A&B. Moreover, we show that the theoretical error is correlated with the variation of the nodes speed which let us determine the movement direction depending on the sign of the error. Finally, we showed with the theoretical results that the nodes speed (and its associated mobility model) has an impact on the design of MAC strategies. In the future, we will extend this analysis to other scenarios and with a physical channel.

Fig. 1 .

 1 Fig. 1. Ranging error estimation between static node and mobile node

Fig. 2 .

 2 Fig. 2. Three Way Ranging protocol applied with mobile nodes

Fig. 3 .

 3 Fig. 3. (a) Camera snapshot during the measurement of the Yoga activity. (b) Multi-cylinder Body reconstruction -the red (resp. blue) points refer to the mobile nodes (resp. anchors).

Fig. 4 .

 4 Fig. 4. Details of the P2P-B and A&B schedulingt as V i (t) = Pi(t)-Pi(t-1) δt . Accordingly, the distance vector d ij (t 1 ), after the first movement t 0 ⇒ t 1 , can be expressed with the Chasles relation ( AD = AB + BC -DC) as:

Fig. 5 .

 5 Fig. 5. Calculated speed of nodes and simulated ranging errors between mobile nodes and anchor A 4 with the Yoga scenario.

Fig. 6 .

 6 Fig. 6. Validation of the theoretical ranging errors between mobile nodes and anchor A 4 with the Yoga scenario.

3 Fig. 7 .

 37 Fig. 7. Ranging Error for the Yoga Scenario with the P2P-B MAC scheduling.

ACKNOWLEDGMENT

This work has been carried out in the frame of the CORMORAN project, which is funded by the French National Research Agency (ANR) under the contract number ANR-11-INFR-010. A part of this research has been realized at the LINCS laboratory. We thank all the involved researchers from ENS/IRISA and M2S Lab for their precious support during the measurement campaign.


David Dureisseix

Searching for optimal polygon | remarks about a general construction and application to heptagon and nonagon

Introduction

Results obtained in a rst paper, Dureisseix 97], deal with positioning optimal polygons | i.e. largest regular polygons within a square. Such polygons have two particularities: symmetry with respect to at least one diagonal of the square and the fact that each edge of the square touches one vertex of the polygon.

The technique used for pentagon (building the stellated pentagon) can be generalised for any number of edges. Complete construction in this case still remains open. Nevertheless, it seems necessary to begin with the construction of an angle n , which is then enough to build the optimal polygon with the technique proposed herein.

With procedures for folding 7 and 9 that are described herein, examples of heptagon and nonagon are performed.

General case of an n-edged polygon

In order to get a construction for regular polygon with n edges, the technique used for the pentagon in Dureisseix 97] can be generalised. Reaching a fraction of the angle n as well as a length are necessary to position the polygon. The idea proposed herein is to take for this length a particular edge of one stellated version of the polygon.

We consider polygons | either stellated or not | for which one edge touches two sides of the square. thanks to previously demonstrated symmetry with respect to one diagonal, at least one edge is parallel to the other diagonal: this is the interesting edge, l i or l j , gure 1. One can notice that the largest edge of any stellated versions, l, as been used in Dureisseix 97] for nding the optimal position of the polygon.

M i , M s and M j denote the vertices of the polygon that touch the sides of the circumscribed square; i denotes the angle between ????! M 0 M 1 and ???! M 0 M i , gure 2. It is easy to show that i = n (i ? 1). The searched edge of the stellated polygon has then to satisfy i + opt = 4 or

M 0 M i M s M j l i l j l θ opt α i π 2
Figure 1: Remarkable edges of stellated polygon Let's nd rst the vertex M i , gure 1, that touches the right side of the circumscribed square. i is such that 2 opt + 2(i ? 1) n < 2 + 2 n and then i = E( n 4 ? opt n 2 ) + 1. Once more, we have to separate sub-cases: if p is even: with opt = 4n , i = E( p 2 + 1 8 ) + 1 and as p = 2k,

M 0 M 1 M 2 M k 2π n α k
i = k + 1 = p 2 + 1 = n + 3 4 ; i = 4 ? 4n if p is odd, with opt = 3 4n , i = E( p 2 ? 1 8 ) + 1 and as p = 2k + 1, i = k + 1 = p + 1 2 = n + 1 4 ; i = 4 ? 3 4n
Each time, we have opt + i = 4 : this is the searched edge.

It will happen to be interesting to consider also the vertex M j , gure 1, that touches the left side of the circumscribed square. j is such that 3 2 opt + 2(j ? 1) n < 3 2 + 2 n 2 and then j = E( 3n 4 ? opt n 2 ) + 1.

if p is even: with opt = 3 4n , j = E( 3p 2 + 3 8 ) + 1 and as p = 2k,

j = 3k + 1 = 3p 2 + 1 = 3n + 1 4 ; j = 3 4 ? 3 4n
if p is odd: with opt = 4n , j = E( 3p 2 + 5 8 ) + 1 and as p = 2k + 1, j = 3k + 3 = 3(p + 1) 2 = 3(n + 1) 4 ; j = 3

? 4n

We have again opt + j = 4 : this is an admissible solution again. Building the interesting edge is easier when the expression of its length is simple. This is the case when one of the vertices M i or M j is exactly between vertices M 0 and M q .

M 0 M i M s M j l i l j l β j
Case where p is even

M 0 M i M s M j l i l j l β i
Case where p is odd Figure 3: Remarkable edge when n is odd if p is even: the best vertex is M j , gure 3. j ? s = n ? 1 4 = n ? j and then j = j ? s = n (j ? s) = 4 ? 4n and l j = l 2 cos j = A=2 cos 4n cos( 4 ? 4n )

if p is odd: the best vertex is M i , gure 3.

i ? 0 = n + 1 4 = s ? i and then i = s ? i = n (s ? i) = 4 + 4n and l i = l 2 cos i = A=2 cos 4n cos( 4 + 4n )

For each case, folding the interesting length depends now of the initial construction of angle 4n , gure 4. If p is even, the construction follows the pattern of the gure 5, else, it follows the pattern of the gure 6. This construction can be realised more or less easily for several particular cases.

Case of an even number of edges: n = 2p

Case for which n is even has similar framework of folding. Now, i = E( p 2 ) + 1, j = E( 3p 2 ) + 1.

Particular vertices

If p is even: with opt = 0 and p = 2k,

i = k + 1 = p 2 + 1 = n 4 + 1; i = 4 j = 3k + 1 = 3p 2 + 1 = 3n 4 + 1; j = 3 4
If p is odd: with opt = 2n and p = 2k + 1,

i = k + 1 = p + 1 2 = n + 2 4 ; i = 4 ? 2n j = 3k + 2 = 3p + 1 2 = 3n + 2 4 ; j = 3 4 ? 2n
These results are also collected in table 1.

Particular edges

Now, interesting lengths correspond to vertex M i . They are more complex than those used when n was odd.

x y z

l i A/2 A/2 π 2n π n = = { = = 2π n
l i A/2 A/2 π 2n π 2n
Figure 8: Construction when n is even and p is odd If p is even, i ? 0 = n 4 + 1 and s ? i = n 4 ? 1. With gure 9, we can nd i = s ? i = n (s ? i) = 4 ? n and l i = A=2 cos 2n cos( 4 ? n ) (1 + sin 2 n )

Figure 7 shows the construction of this edge.

If p is odd, i ? 0 = n 4 + 1 2 and s ? i = n 4 ? 1 2 . With gure 9, we can nd i = s ? i = n (s ? i) = 4 ? 2n and l i = A=2 cos 2n cos( 4 ? 2n ) (1 + sin 2 n )

Figure 8 shows the construction of this edge.

Example of the heptagon

With the previous notations, n = 7 = 2p + 1 with p = 3 = 2k + 1 and k = 1.

Interesting vertex is M i with i = 2; it is built from the length l i .

M 0 M i M s l i l β i α 2 = π/n M i-1 M i-2
Case where p is even

M 0 M i M s l i l β i M i-1
Case where p is odd Figure 9: Remarkable edge when n is even Here, the angle 4n = 28 is folded with the technique used in Geretschl ager 97]. One can notice that this construction is non euclidean: it is impossible to perform it with the only tools that are compass and straight edge. Figure 10 shows the whole construction. The angle 4n = 36 is folded with the trisection classical technique (see for instance Fusimi 80], Hull 96]); it is again a non euclidean technique. Figure 11 shows the whole construction.

Example of the hexagon

Cases where n is even are simpler to perform, at least for small values of n. The previous technique is still applicable, and the construction can often be simpli ed by use of special properties of corresponding angles.

The hexagon case is presented as an example in the gure 12. Optimal polygon constructions are precise and simple when using stellated particular versions. General case of a polygon with n edges is performed as soon as the angle n have been built. With small values of n, it is easy to obtain; this allowed the folding of polygons till the nonagon.

Figure 2 :

 2 Figure 2: Angles with respect to rst edge 2.1 Case of an odd number of edges: n = 2p + 1 2.1.1 Particular vertices

Figure 5 :Figure 6 :

 56 Figure 4: Initial angle 4n

Figure 7 :

 7 Figure 7: Construction when n and p are even

Figure 10 :

 10 Figure 10: Finding the optimal heptagon Stages 1 and 2: building a fold with slope 2 cos 2 7 . Stages 3 to 5: building the angle 28 . Stages 6 to 8: construction the heptagon. 4 Example of the nonagon This time, n = 9 = 2p + 1 with p = 4 = 2k and k = 2. Interesting vertex is again M i with i = 2.The angle 4n = 36 is folded with the trisection classical technique (see for instance Fusimi 80], Hull 96]); it is again a non euclidean technique. Figure11shows the whole construction.

Figure 11 :

 11 Figure 11: Finding the optimal nonagon

x y z π 12 Figure 12 :

 1212 Figure 12: Finding the optimal hexagon 5 Conclusions

Table 1

 1

		summarises the situation.
	n	p	s	i	i	j	j	opt
	n = 2p n = 2p + 1 p pair n + 1 p pair n 2 p impair n 2 2 p impair n + 1 2	n 4 + 1 n + 2 4 n + 3 4 n + 1 4	4 4 ? 2n 4 ? 4n 4 ? 3 4n	3n 4 + 1 3n + 2 4 3n + 1 4 3(n + 1) 4	3 4 4 ? 2n 2n or 3 2n 0 or n 3 3 4 ? 3 4n 4n or 3 4n 3 4 ? 4n 4n or 3 4n
	3	1	2	1		3		12 or 4
	4	2	2	2		4		0 or
	5	2	3	1		4		20 or
	6	3	3	2		5		12 or 4
	7	3	4	2		6		28 or
	8	4	4	3		7		0 or
	9	4	5	2		7		36 or
		Table 1: Position of particular vertices
	2.1.2	Particular edges

. opt positions the optimal polygon within the square, for which previous results are in table 1.


Searching for optimal polygon | application to the pentagon case David DUREISSEIX September 1997

1 Introduction

Besides classical beginning square, several models are built from various di erent forms of paper. Among them, regular polygons are often used for geometric models or modules. A usual feature related to this kind of constructions is to get the largest regular polygon within a given square. A large number of folding procedures, exact or approximated, simple or complex, using more or less of the paper area, exists.

The goal is herein to nd the optimal polygon (i.e. the regular polygon which size is the largest one, within a given square). Several folding procedures are compared for the pentagon case; moreover, a new exact and optimal construction is proposed, while trigonometry is the main tool needed as well as the integer part.

Construction principle

One can easily show that at least one vertex of optimal polygon intersect (in a large sense) an edge of the square. An auxiliary question is the following: nd the smallest rectangle circumscribed to the given polygon. Thought this question is more general, the answer is paradoxically easier to nd than these related to the circumscribed square. This last case is a particular one; the previous answer will then H and B will denote the height and width of circumscribed rectangles, n, the number of edges for the regular polygon and R, the radius of the circumscribed circle. The -angle positions the polygon from the considered circumscribed rectangle, as described by the gure 1.

This problem posses similarities with the problem of ow irregularities of axial piston hydrostatic components for power uid transmissions Fayet 91], Cognard 93]. Cases where n is odd or even have to be separated, as we do herein. For 2 n ; 2 n ]; H( ) = l cos( ? 3 2n ) Moreover, this function is n -periodic as shown in the gure 3. It is then easy to show that the number of the vertex M s for the rectangle height is s = n + 1 2 . The corresponding width is get as well:

H(θ) θ M s M 0
θ 2π n π n h = 2R sin π n R - π 2 2π n 2π n l = 2R cos π 2n π 2n M s M 0
B( ) = H( ? 2 )
In order to get a phase shift within 0; n ], one has to use the integer part function E:

q = E( n 2 + 1)
such as n 2 < q n 2 + 1, and 0 < = n q ? 2 n , and then B( ) = H( + ). Herein, n is odd, so: q = n 2 + 1 2 ; = 2n .

For a given position , H( ) and B( ) are the minima height and width respectively. Using a circumscribed rectangle leads to two uncoupled minimisation problems. For the special case of the square, itself has to be circumscribed to the rectangle; its edge is then A( ) = max(H( ); B( )). The smallest square is get for the position opt :

A opt = min A( ) = A( opt )

Here, the gure 3 illustrates the result: opt = 4n or 3 4n ; and A opt = l cos 4n

Case of an even number of edges

This time, n = 2p, where p is an integer. The con guration is given on the gure 4.

For 2 0; 2 n ]; H( ) = l 0 cos( ? n ) the function is moreover 2 n -periodic, gure 5. This time, the number of vertex M s used for the rectangle height is s = n 2 ; it is opposed to vertex M 0 . 3 the result is this time 0 = 2 n q 0 ? 2 2 ]0; 2 n ] and q 0 = E( n 4 + 1). 2 sub-cases have to be treated: if p is even: p = 2k, n = 4k and

l' = 2R R θ - π 2 2π n 2π n 2π n π n M s M 0 Figure 4: Even case notations 0 θ 2π/n H(θ) H(θ+π/n) 4π/n
q 0 = E(k + 1) = k + 1 = n 4 ; 0 = 2 4k ? 2 = 2k = 2 n ; B( ) = H( )
Then ( gure 5) opt = 0 or 2 n ; and A opt = H( opt ) = l 0 cos n if p is odd : p = 2k + 1, n = 4k + 2 et

q 0 = E(k + 3 2 ) = k + 1 = n + 2 4 ; 0 = 2(2k + 1) = n ; B( ) = H( + n )
Then ( gure 5) opt = n or 3 n ; and A opt = H( opt ) = l 0 cos 2n

Remark: as for each case, the minimum is obtained for H( ) = B( ), each edge of the circumscribed square touches a vertex of the optimal polygon.

Results

In order to quantify the fact that the polygon is or is not the largest one, an indicator, , is built as the ratio between areas:

= S p S c 1

where S c is the square area and S p , the area of the polygon. S c = A 2 opt ; S p = nR 2 sin n cos n Table 1 summarises the previous results. It is easy to show that each polygon has one diagonal as symmetry axis.

Example of the pentagon

The pentagon is a classical example, it has been several times treated. Remarkable quantities are: Following references are obviously not exhaustive; they refer to one existing presentation of the quoted technique. Some of these techniques are presented herein for the pentagon. They have been designed also in more general cases, for instance in Hilton and Pederson 83], Gibbs 83], Scimemi 89], Huzita 94], Geretschl ager 97a], Geretschl ager 97b].

Exact constructions

Quoted from Kasahara 89], page 253, gure 6.

x y For which an other construction can be found in Kasahara 88], page 73, gure 11. Step 4: building l = A=(cos( =20)).

= = = h A z { 1 1 1 5 -1 = = = =
Step 5: one edge of the stellated pentagon : : :

Steps 6 to 8: : : : and the others. These folding constructions are e ectively optimal, as the indicator is = opt 0:67365.

Figure

  Figure 1: Construction principle

FigureFigure 3 :

 3 Figure 2: Odd case notations

Figure 5 :

 5 Figure 5: Characteristic function for even case As B( ) = H( ? 2 ) = H( + 0 )

Figure 6 :

 6 Figure 6:

  Figure 7: There two constructions are characterised by A = 2, h = p 5 ? 1 1:23607, = 5 4 h 2A 2 tan 5 0:65716. They are not optimal ones, as < opt .

  Figure 10:

  Figure 11:

  Figure 13:

  Figure 19:

Exact constructions for optimal pentagon

Historically, the rst exact construction for the pentagon has to be credited to Morassi 89], gure 18. The technique proposed herein has been developed inde- pendently from the previous one. She leads to a little simpler construction, gure 19, while using the property: l cos 20 = A.

Steps 1 and 2: folding the golden ratio.

Step 3: building the angles =5, =10, =20.


domain: phys chim

text:
Alexander Kamasah

Chamara Abeysekera

Yuanyuan Shi

Baptiste Joalland

James M Oldham

Arthur G Suits

A New Pulsed Valve for High-Intensity Supersonic Jet

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Valve design!

A"NEW"PULSED"VALVE"FOR"HIGH2INTENSITY"SUPERSONIC"JET" "

Alexander)Kamasah,)Chamara)Abeysekera,)Yuanyuan)Shi,)Baptiste)Joalland,)James)Oldham,)and)Arthur)G.)Suits) Department)of)Chemistry,)Wayne)State)University,)Detroit)MI)48202)USA)

Experimental set-up! Molecular beam characterizations! Pulsed supersonic expansion is now a ubiquitous technique used in all laboratories interested in spectroscopic and reaction dynamics studies. The conversion of enthalpy to mass flow leads to the production of low temperature flows with well-defined kinetic energy. High speed valves are used to make short pulses allowing for high beam intensities with lower pumping requirements. Solenoid as well as piezoelectric disk valves have played a significant role but still show important shortcomings: low repetition rates, limited operational times and gas flows. To overcome these limitations, we have developed a new valve based on a high force piezo stack actuator. In this poster, we present the design of this new valve along with molecular beam characterizations obtained via DC slice ion imaging. This design can also be used to generate low temperature pulsed uniform supersonic flow as can be seen in the poster Abeysekara et al.

Fig 1 :Fig. 3 :

 13 Fig 1: Cut view of the valve assembly. The piezostack actuator (Physik Instrumente, P-212.80, blue) is mounted in a stainless steel valve body (light grey). The position of the plunger (green) is adjusted by a micrometer. The different o-ring positions are symbolized by red disks. In particular, the plunger is sealed at two positions, i.e. by an o-ring at the nozzle it-self (Kalrez), and by another o-ring fixed at the top of the plunger, with its tightness adjusted by varying the pressure applied by the back plate.!

Table 1 !

 1


text:
Baptiste Joalland

Yuanyuan Shi

Nitin Patel

Richard Van Camp

Arthur G Suits

Dynamics of Cl + propane, butanes revisited: a crossed-beam slice imaging study

Keywords:

Propane and isotopologues:

-Concerning translational energy recoil, FW and SW CD3CH2CD3 distributions peak at lower ET* than regular propane and CH3CD2CH3, while all FW distributions peak at similar ET*, reflecting a more effective energy disposal into the CD3CHCD3 propyl degrees of freedom for the ''rebound-like'' mechanism. => the role of vibrational excitation of the propyl product -The angular distribution of D2 is affected by the deuteration. => a kinematic effect

P(ET) T(Θ)

Phys. Chem. Chem. Phys. This journal is c the Owner Societies 2013 limit of 7.9 eV, all the vertical IEs of the primary abstraction products for all systems lie above. One could expect to detect the latter, those undertaking important nuclear relaxation after ionization, if they were ''hot'' enough once the reaction occurred. However, experiments with partially deuterated hydrocarbon are the opportunity to make a clear disentanglement here: the VUV probe does not ionize these products when its beam is unfocused. That is, no primary abstraction product is detected for the selectively deuterated propane systems. This is an indirect consequence of the radical source improvement that makes possible the use of an unfocused probe laser beam: although we could have access to primary abstraction products as already shown by multiphoton ionization with a focused VUV probe, 15,21 we believe our results here are site-selective even in the case of non-labeled butanes, given the similarity in the vertical IEs of propane and butane. We will therefore discuss all velocity-flux maps as measured for secondary H(D) abstractions in propane and n-butane, and solely tertiary H abstraction in isobutane. Fig. 3 shows the reduced translational energy distributions for the forward (FW), sideways (SW) and backward (BW) scattering regions, along with the center-of-mass angular distributions for all systems. We choose to plot the ET distributions reduced by ET* = ET/EC to highlight the deviation from the kinematic dynamical picture of heavy-light-heavy reactive systems, for which the acute skew angle implies the conservation of translational energy. Table 2 compiles the average translational energy release and fraction of the collision energy appearing in translation and of the By taking advantage of an improved atomic chlorine source, we have measured velocity-contour flux maps of H-D abstractions in the reactions of chlorine with selected alkanes at an unprecedented level of detail. Angular and reduced translational energy distributions for the set of studied alkanes, namely propane, its two selectively labeled isotopologues CD3CH2CD3 and CH3CD2CH3, and butane isomers nbutane and isobutane for which none or only interpolated differential cross sections were measured in the past, show distinct differences that allow us to revisit the ''reaction picture'' of this family of reactions.

  c.o.m. angle / deg.

Fig. 3

 3 Fig.3Reduced translational energy distributions for forward (30-601), sideways (60-1201), and backward (120-1801) scattered products and the center-of-mass angular distributions. Top panel corresponds to propane reactions with propane in blue, D1 in purple and D2 in red. Bottom panel corresponds to butane reactions with n-butane in black and isobutane in gold. Each distribution is normalized to its backward component that dominates the translational energy distributions of all the systems in this range of integrated angles.

  Crossed-beam DC slice imaging set-up -Radical hydrocarbon products are ionized with a VUB beam at 157nm. -The ionized cloud is accelerated and stretched by a set of four ion optics lenses, and detected by a MCP/phosphor screen. -Raw images are recorded using a CCD camera and our new acquisition program NuAcq-2. A high-density Cl source: photolysis/ablation -Raw images at m/z = 35 without (a) and with (b) ablation. -Signal intensity multiplied by 4 in image a. -(c) Corresponding chlorine beam profiles. Advantages: -Enhanced S/N ratio => Unfocused probe -Probe/interaction region overlap -Little density-to-flux correction -No multiple photon ionization => Product selection with ionization energies asuits@chem.wayne.edu joalland@chem.wayne.edu Imaging Differential Cross Sections Thermochemical data -Reduced translational energy distributions for forward (30-60 deg.), sideways (60-120 deg.), and backward (120-180 deg.) scattered products and the center-of-mass angular distributions. -Top panel corresponds to propane reactions. Bottom panel corresponds to butane reactions. -Each distribution is normalized to its backward component that dominates the translational energy distributions of all the systems in this range of integrated angles. -Left: Reduced translational energy distributions for 10 deg. steps of the angular distributions of reactions of chlorine with n-butane and isobutane. -Right: Fractions fC and ftot of collision energy EC and available energy Etot, respectively.

Conclusions

  Butane isomers: Compared to n-butane distributions, isobutane distributions exhibit a more sharply peaked angular distribution with a broader translational energy distribution in the FW direction, even possibly a bimodal distribution. => vibrationallly excited HCl or steric hindrance effect? => Need for state-resolved experiments This work is funded by -Bond dissociation energies (BDEs) and reaction enthalpies at 0 K (DH(0 K)) for all the possible H-D abstractions, and adiabatic and vertical energies of the corresponding products. -Values calculated at the CBS-QB3 level of theory. => Velocity-flux maps measured for secondary H(D) abstractions in propane and n-butane, and tertiary H abstraction in isobutane.

Table 1

 1 Bond dissociation energies (BDEs) and reaction enthalpies at 0 K (DH(0 K)) for all the possible H-D abstractions, and adiabatic and vertical energies of the corresponding products. Values calculated at the CBS-QB3 level of theory

	Reactant	Product	BDE (kcal mol À1 )	DH(0 K) (kcal mol À1 )	Vertical IE (eV)	Adiabatic IE (eV)
	Propane D1, D2	n-Propyl
		CH3CH2CH2 CD3CH2CD2 CH3CD2CH2 Isopropyl	100.6 103.1 100.6	À2.8 À1.5 À2.8	8.40 8.41 8.42	7.66 7.61 7.64
		CH3CHCH3 CD3CHCD3 CH3CDCH3	97.0 97.3 99.4	À6.4 À6.1 À5.2	7.74 7.75 7.73	7.47 7.48 7.46
	n-Butane	n-Butyl
		CH3CH2CH2CH2 2-Butyl	100.5	À3.0	8.32	7.51
		CH3CH2CHCH3	97.3	À6.1	7.67	7.32
	Isobutane	2-Methylene-propane
		(CH3)2CHCH2 Isobutyl	100.6	À2.8	8.33	6.64
		(CH3)3C	95.3	À8.1	7.22	6.87