Nazim Fatès

Critical phenomena in cellular automata: perturbing the update, the transitions, the topology *

We survey the effect of perturbing the regular structure of a cellular automaton. We are interested in critical phenomena, i.e., when a continuous variation in the local rules of a cellular automaton triggers a qualitative change of its global behaviour. We focus on three types of perturbations: (a) when the updating is made asynchronous, (b) when the transition rule is made stochastic, (c) when the topological defects are introduced. It is shown that although these perturbations have various effects on CA models, they generally produce the same effects, which are identified as first-order or second-order phase transitions. We present open questions related to this topic and discuss implications on the activity of modelling.

Introduction 1.Position of the Problem

The thesis of this paper is that cellular automata (CA) should not only be studied with various initial conditions but also with various perturbations in order to assess how they resist modifications of their structure. Why do we need to examine the effect of perturbations on cellular automata? When considering a cellular automaton, why should we spend some efforts to estimate its robustness to various perturbations? There are different reasons for asking these questions and it will be convenient to answer depending on the context where we are using a cellular automaton. A useful dichotomy is to separate the CA models that mimic natural phenomena and those designed to study massively parallel computations.

Firstly, if the CA model is meant to mimic a natural phenomenon, it is important to know which of the implicit hypotheses of the model are necessary to re-produce the phenomenon. By 'implicit' hypotheses we have in mind the mathematical regularities which define the "structure" of CA, by opposition to the local rule which varies from a model to another. For instance, let us consider an epidemic modelling with a simple contamination rule: a cell gets infected if one of its neighbours is infected. Clearly, the evolution of the "contamination pattern" will depend on the type of neighbourhood chosen. It will also strongly depend on the type of updating. How do we choose the right updating scheme? Since there is no clock in nature that synchronises transitions, we are free to choose the updating procedure as we wish and this freedom may shed some doubts on the relevance of using cellular automata as a modelling tool [START_REF] Ingerson | Structure in asynchronous cellular automata[END_REF][START_REF] Huberman | Evolutionary games and computer simulations[END_REF]. On the other hand, if we observe this system from a higher viewpoint, we may also declare the behaviour robust since we always observe that the whole lattice is progressively contaminated. Is this a better definition of robustness? All depends on how we observe the system. It is thus important to note that there is no unique way of defining robustness. It is the "level of granularity" we decide to observe the system with which will guide our definition of robustness. Since CA are mainly used for developing qualitative predictions, testing the robustness to various perturbations is necessary for knowing which of the "structure" is involved in the production of a given behaviour.

Secondly, we examine the case where CA are models of massively parallel computation. In this context, we are in the domain of mathematics and we do not ask whether a hypothesis is "realistic" since we may choose our hypotheses freely, as mathematicians do when they build new worlds. The question here might more be oriented as a challenge: how can we build massively parallel computation tools that resist various perturbations? Can we imitate living organisms or natural societies to achieve this goal? Answering these questions would open the way for important innovations. For example, it is well known that the existence of a central clocks to synchronise components brings important limitations to the design of novel devices. How can we overcome this constraint? Can we build asynchronous or partially synchronous computing devices? (see e.g., [KIP + 08]). These issues illustrate some of the scientific motivations to explore CA robustness.

Although the idea of perturbing cellular automata is not new, it is surprising to see that only a few researchers have turned their attention to it. To date, defining the robustness of a system is more of an art than a science; it mainly consists in finding the right balance between a too narrow definition, which renders the system sensitive to any perturbation, and a too loose definition, which would result in considering the system as robust to any perturbation.

Critical Phenomena

In this paper, we choose to tackle the robustness of CA models from the angle of critical phenomena. By critical phenomena, we designate all the cases where a continuous variation in the local rules of a cellular automaton triggers a qualitative change of its global behaviour. Why is this viewpoint interesting? Its main advantage is that it allows us to build a bridge between CA and statis-tical physics. In this context, abrupt changes of behaviour can be studied as phase transitions, which obey well-structured scaling laws. In particular, near the critical point, the system's behaviour obeys power laws which exponents, the critical exponents, are not arbitrary but are generally found in well-known classes. It has been observed that different models with very dissimilar local rules exhibit the same critical exponents, we say that they belong to the same universality class. For computer scientists, this other type of universality brings out an interesting method of classification, which, as we will see later, is largely uncorrelated to the traditional classifications. Grouping cellular automata according to their critical behaviour might give us novel insights on how complex global behaviours may emerge from simple local interactions.

Methodology

To present the effect of various perturbations on different CA models, we may either proceed by examining the effect of each perturbation on one model or by examining the effect of each perturbation separately. We adopt the latter choice and we will divide our survey by considering perturbations one type after the other. This presentation is meant to emphasise the fact that different models, which do not share much in common, sometimes react identically to a given perturbation. For the sake of brevity, we will select a few models, mainly chosen from our own research activity. Each time possible, we will broaden our point of view by linking our observations to wider research questions on cellular automata.

The structure of the paper follows the three main properties found in the structure of "regular" CA: (a) synchronous updating, (b) determinism of the transitions, and (c) regular arrangement of cells. In Section 2, we will survey the existing works which examine how the asynchronous updating may trigger phase transitions. We will then examine in Section 3 the case where the local transition rule is made stochastic. The effect of topology perturbations is surveyed in Section 4. Each section is devoted to a perturbation type and in each section, we mainly concentrate on simple models such as the Game of Life, Elementary Cellular Automata or the Greenberg-Hastings model.

Asynchronous updating 2.1 The Game of Life

The asynchronous version of Game of Life, or simply Life, will provide us with a sound introduction to the topic of robustness. Let us recall the rules which define the "game". A cell takes one of the two values: occupied or empty. The state of each cell depends on its current state and on the sum σ of occupied sites among the 8-nearest neighbours. An empty cell becomes occupied if and only if σ = 3; an occupied cell remains occupied if and only if σ ∈ {2, 3}. Since its invention by Conway in 1970, this cellular automaton has been shown to have a global behaviour rich enough to embed a universal Turing machine [START_REF] Berlekamp | Winning Ways for your Mathematical Plays[END_REF]. Now what happens to the system if the cells are no longer updated synchronously at each time step ? There are various methods for defining asynchronous systems and we will here restrict our scope to the two most intuitive ways: (a) we call α-asynchronous updating the procedure which consists in updating a cell with probability α at each time step, otherwise keeping its state constant; (b) we call fully asynchronous updating the procedure where cells are updated sequentially and where the cells to update are chosen randomly and independently without any memory.

Figure 1 displays three evolutions of Life with different updating schemes. The asynchronous updating has overwhelmed the global behaviour in such a way that the system evolves into a steady state which consists of "labyrinth" patterns. This strange modification was first reported by Bersini and Detours [START_REF] Bersini | Asynchrony induces stability in cellular automata based models[END_REF] for the fully asynchronous case and was studied quantitatively by Blok and Bergersen for the α-asynchronous updating [START_REF] Blok | Effect of boundary conditions on scaling in the "game of Life[END_REF]. Their results indicate that the systems obeys phase transition with a critical threshold located at α ∼ 0.910. The transition between the two phases belongs to the directed percolation (DP) universality class (see [START_REF] Hinrichsen | Nonequilibrium critical phenomena and phase transitions into absorbing states[END_REF]). Above the threshold, the system's behaviour is similar to the synchronous case, although the periodic stable structures disappear. Below this threshold, the "labyrinth" phase develops, its development on the grid increases as the synchrony rate α decreases. A first study on how labyrinth phase develops on the grid was proposed by Fatès and Morvan [START_REF] Fatès | Perturbing the topology of the game of life increases its robustness to asynchrony[END_REF] but a detailed description of the properties of this phase is still needed.

Many questions emerge for these observations. What is the effect of asynchronous updating on "complex" CA such as Life? Bersini and Detours suggested that it was a "stabilisation" of the system. In our view, it is not so clear whether the asynchronous system is more stable as the stability strongly depends on the system's size. For small-sized system, i.e., for a grid length smaller or equal to 20, it is indeed possible to observe the system reach a fixed point, but as soon as the grid becomes large enough, for instance for L = 30, one no longer sees the system freeze on a fixed point, even for very long simulation times. So the state of the labyrinth phase is a meta-stable phase: it evolves rather erratically until by chance, it "touches" a fixed point. In mathematical terms we say that the system is a metastable state and it is an open problem to prove this property. More generally, how is the existence of phase transition related to the Turing-universality of Life? How frequent asynchrony-induced phase transitions are in the space of CA? In the next paragraph, we start to gain insights on these issues by turning our attention from a single rule to a small set of rules, namely the Elementary Cellular Automata (ECA).

Elementary Cellular Automata

Ingerson and Buvel were the first authors to question the importance of synchronous updating in the emergence of structures in cellular automata [START_REF] Ingerson | Structure in asynchronous cellular automata[END_REF].

According to their own words, it is necessary to estimate how much of the interesting behaviour of cellular automata comes from synchronous modelling and how much comes is intrinsic to the iteration process. Although their study consisted mainly in describing qualitatively the effect of asynchronous updating, they proposed a first panorama of the effects observed on the 256 ECA rules (binary 1D nearest-neighbour rules). A quantitative assessment of the effect of asynchrony on ECA was conducted by Fatès and Morvan [START_REF] Fatès | An experimental study of robustness to asynchronism for elementary cellular automata[END_REF]. Results showed that quantifying the behaviour with the density produced a discrimination between the robust and non-robust rules. Four classes were proposed ; depending on whether the perturbation of behaviour occurred for α = 1 and for α < 1. More specifically, a first set of rules was identified as having a nontrivial critical phenomenon. Seven of these rules were characterised as belonging to the DP universality class [START_REF] Fatès | Directed percolation phenomena in asynchronous elementary cellular automata[END_REF] and another rule, ECA 178, was identified in another universality class specific to the case where the states 0 and 1 are symmetric [START_REF] Fatès | Asynchronism induces second order phase transitions in elementary cellular automata[END_REF].

The key point emerging from the exploration of asynchronous ECA is that there exists no direct relationship between the "traditional" classifications of cellular automata in terms of dynamical systems and their classifications with regard to their robustness to asynchronism. For example, ECA 18 and ECA 50 are respectively class-3 (chaotic) and class-2 cellular automata according to Wolfram's informal classification but they are both found to display DP behaviour (see Fig. 2). This implies that two cellular automata that do not have anything in common may have the same macroscopic behaviour when simulated near their critical threshold. Rouquier and Morvan also observed similar behaviour with coalescing automata, i.e., asynchronous evolutions of CA that use the same source of randomness [START_REF] Rouquier | Coalescing cellular automata: Synchronization by common random source for asynchronous updating[END_REF]. It is to date an open problem to determine which are the "ingredients" that makes a rule belong to the DP universality class.

Other Models

Regarding other two-dimensional binary CA, we point out the recent work by Fatès and Gerin on totalistic CA [START_REF] Fatès | Examples of fast and slow convergence of 2D asynchronous cellular systems[END_REF] and by Regnault et al. on the minority rule [START_REF] Regnault | Progresses in the analysis of stochastic 2D cellular automata: A study of asynchronous 2D minority[END_REF] which develop an analysis of the system with some tools from the stochastic process theory -see references in these two papers for a wider scope. Apart from the two-state models mentioned so far, we must acknowledge that there are not many models whose robustness have been estimated with different types of asynchronous updating, and even less where critical phenomena have been observed.

An interesting exception lies in the debate set out by Huberman and Glance, who illustrated how in the spatial version of the Prisoner's Dilemma a change from synchronous to fully asynchronous updating turned the system to a different attractor where all players are defecting [START_REF] Huberman | Evolutionary games and computer simulations[END_REF]. These results were later re-examined independently by Mukherji et al. [START_REF] Mukherji | Robustness of cooperation[END_REF] and by Grilo and Correia [START_REF] Grilo | Asynchronous stochastic dynamics and the spatial prisoner's dilemma game[END_REF] who showed that the α-asynchronous updating leads to different attractors, and that the transition from one attractor to another could be abrupt. Recently, Saif and Gade discovered that the asynchronous version of the spatial Prisoner's dilemma triggers first-order phase transitions [START_REF] Saif | The prisoner's dilemma with semi-synchronous updates: evidence for a first-order phase transition[END_REF]. This behaviour is rather unusual as the phase transitions found in similar situations are generally second-order, i.e., continuous. It would be interesting to explore whether other cases of discontinuous behaviour are present in other systems.

Perturbations of the Transition Rule

We now broaden our perspective by considering that the outcome of a local transition is no longer deterministic. This defines the probabilistic CA or stochastic CA, a class which contains the α-asynchronous CA (but not the fully asynchronous CA). An abundant literature is available on this topic. For the sake of conciseness, we will here only mention a few stochastic CA which are obtained as perturbations of a well-known deterministic model. For instance, Ising or Domany-Kinzel models will be out of consideration since they are "intrinsically" stochastic -the deterministic behaviour obtained with some settings are more degenerate cases than common cases.

The Game of Life

The idea to test how Life resists noise dates from as early as 1978 with paper by Schulman and Seiden [START_REF] Schulman | Statistical mechanics of a dynamical system based on conway's game of life[END_REF]. They examined how the introduction of a stochastic element in the local evolution rule would perturb the long term evolution of the system. They replaced the deterministic transitions p k,s -which are equal to 0 or 1 if a cell in state k with s lives neighbours dies or leaves -by p k,s (T ) which are the probabilities to be in state 1 at the next iteration. They take p k,s (T ) = (p k,s + d.T )/(1 + T ) , where d is the current density and T is the stochastic parameter, named "temperature" by analogy with the physical parameter. Interestingly, this parameter is chosen such as not to influence the evolution towards increasing or decreasing the density -this property is also valid for the α parameter. One problem with this approach is that the calculus of the probabilities is not local: the density should first be computed using the state of the whole grid before the transitions are determined. Despite this difficulty, the authors performed first order and improved mean-field analysis. Their findings can be summed up by saying that mean-field analysis fails to predict the evolution of the classical deterministic Life but succeeds with high-temperature models. More surprisingly, their analysis shows that a phase transition exists which would separate two regimes where the system is attracted to the null density and to an attractor of density 0.37. However, no characterisation of the phase transition was made. It is very likely that the effect of the "temperature" is similar to that of the asynchrony.

Other Stochastic CA

The existence of phase transitions were also observed by Kaneko and Akutsu for 4-neighbour-outer-totalistic cellular automata with the 0/1 symmetry [START_REF] Kaneko | Phase transitions in twodimensional stochastic cellular automata[END_REF]. Noting that "noise plays an important role for the formation of patterns in nonequilibrium systems", their perturbation consisted in flipping cells randomly. They observed the apparition of first-order transitions and classified the various types of patterns observed (labyrinth, turbulence, glassy, ferro, anti-ferro, etc.). A quantitative study of these phenomena still remains to be performed.

Adding Topology Perturbations

Let us now complete our panorama of the perturbations by considering topological modifications. Here again there are so many ways of modifying the topology that it is difficult to be exhaustive. We choose to mainly focus on the cases where locality of the connections between cells is conserved. We point out that generalising the CA model of computation to any topology is a rather

The Game of Life

In all the preceding situations, phase transitions appeared when the local rule was modified. Is it possible to obtain similar effects by changing only the links between cells? Huang et. al. answered the question positively in a study where they perturbed the Game of Life by (arbitrarily) rewiring links between cells [START_REF] Huang | Network-induced nonequilibrium phase transition in the "game of life[END_REF]. They found similar effects to those of asynchrony, i.e., that Life exhibits a phase transition from an "inactive-sparse" phase to an "active-dense" phase. Surprisingly enough, this phase transition was identified as belonging to the DP universality class although the links between cells were not local. Indeed, locality of interaction is one of the hypotheses of the Janssen-Grassberger's conjecture [START_REF] Janssen | On the nonequilibrium phase transition in reactiondiffusion systems with an absorbing stationary state[END_REF] on the occurrence of DP (see the reviews by Hinrichsen and Ódor for a detailed account [START_REF] Hinrichsen | Nonequilibrium critical phenomena and phase transitions into absorbing states[END_REF][START_REF] Ódor | Universality classes in nonequilibrium systems[END_REF]). What happens if asynchronous updating and topology perturbations are added ? This combination was examined by Fatès and Morvan [START_REF] Fatès | Perturbing the topology of the game of life increases its robustness to asynchrony[END_REF] by removing links randomly and independently in the neighbourhood of the cells. They observed that the phase transition was progressively "wiped out" by the link removal and that if more than 10% of the links were destroyed, no phase transition was observed. Figure 3 illustrates this disappearance of the phase transition. A first explanation was proposed for this phenomenon: as some links were missing, it became more difficult for the labyrinth (or active-dense) phase to spread. However, things are not as trivial as they appear. We may note that in the Life, a condition for the survival of a cell is that it is to avoid overcrowding, i.e., to have less than four occupied neighbours. The removal of links should thus not only favour death of cells but also their survival. It is to date an open question to get more insight on the mechanisms involved in the suppression of asynchrony-induced phase transitions by topology perturbations. In particular, what would happen if links were added or simply rewired? Would the effects be similar?

The Greenberg-Hastings Model

Finally, how do the topological perturbations combine with the stochastic perturbations of a CA rule? The subject is again very wide and could be tackled in various ways. To close our tour of critical phenomena, we report on a recent study we conducted on the stochastic Greenberg-Hastings model [START_REF] Fatès | Robustness of the critical behaviour in a discrete stochastic reaction-diffusion medium[END_REF]. The local rule is as follows: a cell can be either neutral, excited or refractory. A neutral cell stays neutral unless it has at least one excited neighbour, it then becomes excited with a given probability (the excitability). An excited cell becomes refractory in one step, and then it stays refractory during M steps until it becomes again neutral.

For the regular grid, varying the excitability triggers a second-order phase transition from an "active" phase, where the waves survive an arbitrary long time, and an "extinct" phase where the waves disappear. With no surprise, the phase transition was found in the DP universality class for various neighbourhoods tested. More interesting was the analysis of the position of the critical threshold. The simulation results showed that as links were removed, the critical excitability was progressively increased and became more difficult to measure ("blurring effect"). However, contrarily to Life, the limit here was attained for about 40% of topological defects. These unexpected phenomena were interpreted as a result of the combination of the effects of classical percolation and directed percolation. Although the prediction of the position of the critical threshold is a difficult problem in general, we could here verify that this position varied as the inverse of the neighbourhood size. It is an open question to determine whether this law applies for other systems.

Discussion

This short survey presented an introduction to the literature on critical phenomena in cellular automata. We aimed to illustrate how cellular automata, despite their simplicity of definition, may exhibit unexpected changes of behaviours when their structure is slightly perturbed. We focused on three perturbations: from synchronous to asynchronous updating, from deterministic to stochastic transitions, from regular to irregular grids.

Each of these perturbations could trigger first-order or second-order transitions, and when combined, the perturbations could lead to the disappearance of the phase transitions. In our view, keeping in mind these observations is primordial for a better use of cellular automata in the modelling field. As the science of complex systems is in its young days, we should be careful when using CA models to mimic real world phenomena. The issue discrete versus continuous tools has been a long-lasting debate and we believe that a careful assessment of the robustness of CA may plead in favour of their use in a modelling context. With this review, we simply wanted to emphasise that many cellular automata have limits: when submitted to structural perturbations, their behaviour may be robust, or it might be immediately overwhelmed, or it might resist only up to a certain amount of perturbations. As we see it, gaining insights on critical phenomena in CA now requires a wide "cartography" project where large panel of models could be explored from the robustness angle.

Figure 1 :

 1 Figure 1: Three snapshots showing evolutions of Life for a random initial configuration : (left) synchronous updating t = 200 , (middle) α-asynchronous updating with α = 0.5, t = 400 , (right) fully asynchronous updating t = 200.

  Figure 2: Four space-time diagrams showing the evolution of two ECA with (left) synchronous updating and (right) with α-asynchronous updating near the critical point (similar evolutions). Time goes from left to right, rings are made of 50 cells (see ref. [Fat09] for more details).

Figure 3 :

 3 Figure3: Disappearance of the phase transition in Life. MLR (missing link rate) represents the probability that a cell does not "see" one of its neighbour (the modification is definitive). Each surface shows the steady-state density density (z-axis) as a function of the initial density (x-axis) and the synchrony rate α (y-axis). See ref.[START_REF] Fatès | Perturbing the topology of the game of life increases its robustness to asynchrony[END_REF].

The author is grateful for the INRIA ARC Amybia support


Jean Sallantin

Antoine Seilles
email: antoine.seilles@lirmm.fr

n-opposition theory to structure debates

come

Introduction

In the era of participatory democracy and web2.0, does a solution to debate exist on the web? Is it even possible? Existing solutions are very limited (chats, forums...). Many sites exist, for Web-users to express their opinion, but can they build structured arguments and confront them? We try to answer these questions by offering new software based on logic. But then, what kind of logic can describe the arguments of a debate? What is the role of n-opposition theory?

In this paper we compare the results of three experiments. First we will introduce some important notions, then we will present our experimental protocol and finally we will present detailed discussion system. We will also explain how we use the n-opposition theory to structure debate and reason. To conclude, we will discuss experiments contexts and results.

1 Toward a web2.0 debate

The work we will present began in 2007. Today it is related to the Intermed project. The Intermed project aims to provide a set of interoperable tools to debate on the web. This first chapter presents our actual model of debate and define some important notions.

Modeling

We did not create any debate model for our first experiment (Betapolitique 2007). All we had was a set of documents (political articles of betapolitique website www.betapolitique.fr) and users had the opportunity to annotate and express their point of view. We present Annotation in the next part of this chapter. The users point of view or argument as we will define it later, comprised part of a text, a judgment and a comment.

For our second experiment (ECAP 2008 www.lirmm.fr/ECAP08), the documents are the texts of the congress speakers. Arguments are more structured and selected text can now be rephrased.

For our third experiment (the first Intermed experiment), we had the opportunity to work with N.Desquinabo (phD in Cemagref UMR G-Eau ). N.Desquinabo thesis is about interlocutivs kinds in TV shows [START_REF] Desquinabo | Caractéristiques et contraintes des genres interlocutifs dans les émissions de plateaux télévisées: analyses pragma-discursives et en réception[END_REF]. N.Desquinabo tasks in the Intermed project revolve around interlocutivs kinds in debates on web [START_REF] Desquinabo | Dynamiques et impacts des propositions politiques dans les webforums partisans[END_REF]. This collaboration lead us to produce a first relational model based on the following principles :

• A debate is firstly defined by a subject and reflects a problem (to be resolved or restate . . . ).

• Each debate is associated with a body of documents called references.

• Documents can be put in categories.

• Participants can create group to defend a same opinion.

• Participants can link arguments to a document.

• Relations link arguments together. Some ideas in le discours acteur du monde by G.Vignaux [START_REF] Vignaux | Le discours acteur du monde[END_REF] illusrates our approach.

• p55 : An argumentation is a set of reasoning to enhance a thesis. It means argumentations are done to solve, enhance or defend and an argumentation is firstly defined by a problem.

• definition of the dialectical discussion p30 quoted by G.Vignaux from the introduction of the Aristotle's Topiques by Brunschwig [START_REF] Brunschwig | Aristote Topiques. Les belles lettres[END_REF]: A two players game; It's a binary opposition, affirmation and negation, victory and defeat.

• p57 : Argumentation consists in confronting arguments and find an issue.

Arguments and annotation

First we present our mecanism to write arguments based on annotation. An argument is a statement supporting a thesis or against a thesis. A thesis is a point-of-view regarding a debate. A thesis can be, for example, an opinion (for or against Nanotechnologies?) or an important conclusion (Nanotechnologies are dangerous) that is to be argued. Arguments are judgments that are expressed regarding a statement. A set of arguments for a thesis is called an argumentation. Today forums, chats or emails are used to debate via the web. We have decided to build a different system using annotation because it can precisely localize the part of a text that a user wants to comment (or argue upon).

Definition of Annotation : An annotation is a data attached to a document or a part of a document.

We had first developped ad-hoc annotations systems for our first and second experiment platforms (Betapolitique was built with SPIP www.spip.net, and ECAP website was built with XWiki www.xwiki.com). For our third experiment, we have developed a solution based on Annotea protocol (www.w3.org/2001/ Annotea) and Annozilla (Annozilla is a client for the Annotea protocol developped by Mozilla for firefox web browser annozilla.mozdev.org). This solution is currently a prototype and is independent of website platforms.

There are other annotation systems existing (we recommend the lecture of [START_REF] Hugues | Towards interoperable secondary annotations in the e-social science domain[END_REF] ) but choosing Annotea was done for the following reasons :

• It allows to annotate HTML documents.

• Annotea is a w3c web standard protocol. This guarantees interoperability.

• Annotations can be stored in RDF database.

• This is an asynchronous solution based on client-server architecture.

We have added to the current Annozilla implementation the possibility to design forms for annotation on a specified category of texts.

In our experiments, an argument is an "illocutionary-act". The statement is selected in a document and must be rephrased to be judged, and user has to justify his act by a comment.

Experimental protocol

This section deals with the experimental protocol we have built from our experiments. Judgments and relations between judgments are defined with respect to the community of users, the subject of the debate, and the categories of documents. A body of documents is created. Users read documents and can annotate to express their point of view and argue. They select and rephrase a statement in a document, state their judgement on it and justify it. Then, each argument can be discussed. When the protocol ends, a summary of the debate must be produced.

1. Define a subject for the debate.

2. Create forms for annotation (define judgments users can choose).

3. Reading documents.

Production of arguments.

5. Discussion of arguments (there is a loop between the fourth and fifth step cause this discussion leads to produce new arguments).

End of the experiment, production of a summary

In a following section of this document, we present three experiments. Criterias given to compare these experiments are :

• Subject of the debate.

• Categories of documents.

• Do users know each other ?

• Links between judgments.

• Aim of the debate (Is this debate going to produce a new document?).

• Duration of the experiment.

• Content of justifications (is there a model of a justification for a kind of judgment?).

Aim of each experiment:

1. First experiment was done as a test to see if it is natural to use judgments to annotate.

2. Second experiment was done as a test to see if users rephrase their selection and justify their judgment.

3. Third experiment was done to test the structure that is itself based on the n-opposition theory.

Relations between arguments and n-opposition theory

The annotation forms we have designed force users to make a judgement. We propose to use structures of the n-opposition theory to define relations between judgments. Experiments are to confirm if users naturally respect or not these structures (Do users respect the structure without explanation?). This section presents the n-opposition theory and structures we designed for our three experiments.

The n-opposition theory

To define relations between judgments, we design a n-opposition structure based on the n-opposition theory [START_REF] Moretti | Geometry for modalities? yes: through n-opposition theory[END_REF]. This theory is a geometrical generalisation of Aristotle's classical opposition theory. The most famous structure of Aristotle's opposition theory is Aristotle's logical square of oppositions. Following definitions are quoted from [START_REF] Luzeaux | Logical extensions of aristotle's square[END_REF].

• sub-alternation : it is defined as the impossibility of having the first term true without having also the second true.

• contrariety : Contrariety between two terms is the impossibility that both terms are true, but the possibility that both terms are false.

• sub-contrariety : Sub-contrariety is the impossibility that both terms are false, but the possibility that both are true.

• contradiction : Contradiction between two terms is defined as the impossibility for them to be both true and both false. Today, our system doesn't assist users because we test if users naturally respect the structure. If a structure appears to be adapted for a debate and its users, it will become possible to assist users by signaling them when they violate the structure.

The following section presents structures we tested in our experiments.

Structures of opposition

We defined six judgments for our first experiment. Two for a theoretical level : i agree, i don't agree.

Two for a practical level : it works, it doesn't work. Two for an emotional level : I like, i don't like. We suggest a structure in which emotional level is a consequence of theoretical level and practical level is a consequence of emotional level. We considered instinct can be educated by theory and acts are consequences of instinct.

Figure 3: structure of opposition for the betapolitique experiment D.Luzeaux [START_REF] Luzeaux | Logical extensions of aristotle's square[END_REF] shows how to translate a n-opposition structure into an epistemistic logic. We had found modalitites of a defeasible logic introduced in [START_REF] Antoniou | A flexible framework for defeasible logic[END_REF] organized in a n-opposition structure according to their definitions. This structure looks like the one we designed for the experiment. Defeasible reasonings deals with conflictual statements. Defeasible logics were introduced by D.Nute [START_REF] Nute | Defeasible logic[END_REF].

A defeasible theory is a triple (F,R,>) where F is a set of facts, R a set of rules and > a superiority relation. There are three kinds of rules, strict rules, defeasible rules and defeaters.

1. Facts are a set of literals and represent indisputable knowledge .

2. Strict rules are denoted by A-> B and are interpreted in the classical sense.

3. Defeasible rules are rules that can be defeated by contrary evidences. [START_REF] Desquinabo | Dynamiques et impacts des propositions politiques dans les webforums partisans[END_REF]. Defeaters are rules that cannot be used to draw any conclusions. Their only use is to prevent conclusions. In other words, they are used to defeat some defeasible rule by producing evidence to the contrary.

5. A superiority relation on R is an acyclic relation > on R. r1 > r2 expresses that r1 may override r2 if they lead to conclusive decision that contradict each other.

A conclusion in a defeasible theory D is a tagged litteral with one of the following modality:

1. +∆q means that q is definitely provable in D. q is proved with only facts and strict rules.

2.

-∆q means that q is not definetly provable in D. q is not proved with only facts and strict rules.

3. +δq means that q is defeasibly provable in D. A defeater to contradict q can exist. The superiority relation leads to conclude q before ¬q.

4.

-δq means that q is not defeasibly provable in D. No set of rules lead to conclude q or for every set of rules leading to conclude q, the superiority relation leads to conclude ¬q before.

5. +δ ap q means q is provable with ambiguity in D. There is a set of rules that can lead to conclude q. The superiority relation is not taken into account.

6. -δ ap q means that q is not provable even with ambiguity in D. There is no set of rules that can lead to conclude q.

Figure 4: structure of opposition for a defeasible logic However, we didn't look any deeper to confirm the matching between these two structures. This observation was the result of intuition. In our experiments, we focused on defining structures and testing their efficiency. Translation of n-opposition structures into logic is one of our future task.

For the second experiment (ECAP), we had defined six judgments:

• I agree, I don't agree to judge a statement on its purpose.

• Correct syntax, uncorrect syntax to judge a statement on its syntax.

• This confirms, this contradicts to add supporting references or contradictory references to the statement.

Judgments were just opposed by contradiction. The Aim of this experiment was to test if users would accept to rephrase their selections and justify their judgments and we didn't propose a complete structure.

For the third experiment (Intermed), we proposed three levels of judgments :

1. Proved 2. Unclear

incorrect

For each annotation, students had to judge with a combination of an affirmative or negative judgment per level (yes it is proved or no it is not proved and yes it is unclear or no it is not unclear and yes it is incorrect or no it is not incorrect). We tested relations of sub-alternation of the figure 5.

Conditions of experiments

Before dealing with results and observations of experiments, we present context of these experiments. For the first experiment, we worked with the development team of betapolitique. Betapolitique is a web blog of politic news. The duration of experiment was three months (February to may 2007) during French presidential elections. No help nor explications were provided to users. There was no objective nor a subject of debate defined. Users of betapolitique are anonymous to each other and were not forced to participate. They could read their arguments on the right of the article (figure 6) and use a treemap (developed by the society Pikko www.pikkosoftware.com) to see which article was the most annotated (figure 7). For the second experiment, we collaborated with the organization committee of ECAP congress. The web site of ECAP was designed to read and discuss texts of the speakers of the congress. The experiment begun few days before the congress and ended to the end of the congress (but the website still exists). A tutorial is accessible. Participants of the congress were unknown each other. Their arguments were displayed on the right of the text and corresponding selections were highlighted into the text (figure 8). The goal of the debate was to enhance the quality of presentations by taking into account remarks from others. For the third experiment, a group of experts of the domain of nanotechnologies wrote a body of documents to answer the following questions :

1. Do nanotechnologies really bring innovations or is it just a buzzword for well known technologies? 2. Are nanotechnologies a chance for the developping countries, or is it still another divide between north and south?

3. Is it sacrilege or progress to let nanotechnologies alter human nature?

4. Do the nanosciences and nanotechnologies harbor still unknown risks? What is a responsible attitude : should research be stopped and the precautionary principle be applied, or should we be confident that further research will identify the actual risks and provide means to control them?

5. Is the lack of proof that nanotechnologies are harmful or harmless a justification for pursuing production and research, or is it a justification for stopping them?

These texts were the documents that students have annotated. The subject of the debate was : Should we write a moratorium on nanosciences and nanotechnologies? And the goal was to produce a summary of argumentations. The experiment was done during two class sessions. Our team was present to assist them. Their annotations were listed on the left of the texts. The parts of text discussed were highlighted by a background color (fig 10). Each of these experiments made evolve our experimental protocol. We decided to define a subject of debate for the third experiment. Maybe, to not define clearly a subject for the two first experiments was the reason of the lack of discussions whereas in the third experiment, each argument was discussed.

It appeared clearly for the second experiment that judgments have to be defined depending the community. For the third experiment, we defined judgments depending the subject of the debate. We are now convinced that judgments must be defined depending the categories of documents. People don't judge scientific statements the same way as philosophical statements.

With the second experiment we introduced the obligation to rephrase the selection. This enhances comprehension between users. A judgment is associated to the new statement (rephrasing the selection) , not to the selected part of document. So, even if there is a misunderstanding of the selected part of document, user precise the statement he judge.

Observations and results

We present in this section the conclusions of these three experiments.

The first experiment confirmed the use of judgments and the choice of annotation as a solution for implementing debate. We had 870 annotations for three months of experiment. Judgments were all adopted (figure 12).

Figure 12: Repartition of judgments in betapolitique

The second experiment validated the need of an ergonomic interface and of a gratification function. The goal of the experiment was not taken into account by participants. We did interviews as well as polls and the general feeling was that the idea is interesting but the tool is too complicated to be used. We analysed frequencies of visit on the site through Google analytics tool (www.google.com/analytics). The Congres was held from the 16th to the 18th of June 2008. The highest number of visits appened on the 16th of June, 147 visitors for 80 participants registered to the congress. We had 306 visitors from the 15th to the 19th of June. The average time of visit during this period was of four minutes. Though we had so much visitors, we had only 95 annotations, most of them done before 19th June. The text the most annotated has been annotated 7 times (there were 70 texts). Nearly nobody attempted to discuss through the tool. The third experiment validated the interest of rephrasing the annotated statement. The most interesting observation is the fact that there seems to be models of justifications for judgments. Users adopt the same kind of locution for a same combination of judgments to justify their choice. Satisfaction, interest and evolution of the opinions were evaluated with a survey. Most of students have appreciated the quality of debates using our tool. They suggested enhancements for the tool that are possible with our technological and conceptual choices.

Most of the arguments are of ethical content. They are on managing risks or on managing conflicts between nanotechnologies potential danger and public health.

Opinions become more precise with controversies. They made 39 arguments during the first session and 19 during the second one. Each argument was systematically discussed.

The content of justifications leads to the following conclusions:

• If a statement is tagged proved, the justification explains the statement.

• If a statement is tagged incorrect, the justification is a negative reason.

• If a statement is tagged with two criteria ( proved and unclear or proved and incorrect), the justification shows a contradiction and suggests a new direction.

• If a statement is tagged not incorrect, unclear and not proved, the justification is expression of a belief or of a conviction.

If these results are confirmed by more experiments, it means that we can guide users in justification of their choices of judgment. 41 annotations were well-formed ( i.e a judgment per level), the figure 14 presents the repartition of these annotations with respect to relations of sub-alternation of our structure. Notions of desire and pleasure have appeared during our experiments. Desire is an impulsion for users to participate. Pleasure is a satisfaction, a gratification. The third experiment was the most representative of the need to not neglect these notions. Every frustration (misunderstanding of the software, technical issues, lack of information) can block the participation but an ergonomic interface (nice and easy to use) can enhance desire to debate. Pleasure depends on quality and goal of the debate. Reasoning and arguing, clarifying one's own opinion and producing a summary of one's argumentation are pleasurable activities. These two notions (desire and pleasure) deserve more attention in our future works. But we have seen we could mesure desire and pleasure with poll. Students of the Intermed experiment attributed an average mark of 4/5 for the quality of the debate and of 3,5/5 for the ergonomy and the interest of the website.

Conclusion

Facing the lack of web 2.0 solutions to make debates of quality, we propose to create web tools founded on logic to enhance debates structure and comprehension. In our solution, arguments are justified judgments on statements. The experiments we presented show that our model of argumentation is natural and easy to adopt. The n-opposition theory is a geometrical tool we use to define relations between judgments and to categorize relations between arguments. That's a first step to describe reasonings. The third experiment showed that it is possible to define for each judgment an "illocutionary-act". We can associate an interpretation to each judgment. But, is it natural to represent a judgment with a logical modality? What kind of logic can express relations between judgments?

In our future experiments, we suggest the implementation of an help system that will suggest to users a form of justification for their judgments. We have to define notions of desire and pleasure in the context of the debate. We want to develop an agent founded on n-opposition and logic for helping users when reasoning.

Figure 1 :

 1 Figure 1: traditional Aristotle's logical square of opposition

Figure 2 :

 2 Figure 2: Aristotle's square of opposition in predicate logic Figure 1 shows four kinds of relations (arrows and colored line) between four judgments, traditionally represented by letters A,E,I,O. A and E represent universal judgments (A is the affirmative universal judgment, E is the negative universal judgment). I and O represent particular judgments (I is the affirmative particular judgment, O is the negative particular judgment). Arrows between universal and particular judgments represent relations of sub-alternation. The blue line between A and E represents a relation of contrariety. The green line between I and O represents a relation of subcontrariety. Red lines represent contradiction. Figure 2 shows an example of square of oppositions in predicate logic.Following definitions are quoted from[START_REF] Luzeaux | Logical extensions of aristotle's square[END_REF].

Figure 5 :

 5 Figure 5: structure of opposition for the Intermed experiment

Figure 6 :

 6 Figure 6: screenshot of annotations for Betapolitique

Figure 7 :

 7 Figure 7: A treemap to visualize annotated documents

Figure 8 :

 8 Figure 8: screenshot of annotations for ECAP

Figure 9 :

 9 Figure 9: A graph to cartography debates based on opposition

Figure 10 :

 10 Figure 10: A screenshot of annotations for Intermed

Figure 11 :

 11 Figure 11: Comparison of conditions of experiments

Figure 13 :

 13 Figure 13: Statistics of visits of ECAP website

Figure 14 :

 14 Figure 14: Sub-alternation in Intermed

We thank JB.Soufron for its help during the first experiment. J.B.Soufron was responsible of the website betapolitique. Thank to V.Pinet and P.Thomaso and their students for testing our tools. Thank to N.Desquinabo and all the team of the Intermed project. Thank to Pikko-software society and specially its developers for technical help. Thank to J.Divol, N.Rodriguez, A.Gouaich for their help at LIRMM. And a special thank to M.Hornby for her help during translation of this paper.


Clément Abi

Rebeca Vetil

Laura Kate Wood

PhD • Marc-Michel Rohe

PhD • Alexandre Bône

PhD • Hedvig Karteszi

MD, FRCR • Marie-Pierre Vullierme

Automatic detection of pancreatic lesions and main pancreatic duct dilatation on portal venous CT scans using deep learning

Keywords: Computed Tomography., DL: Deep Learning Main Pancreatic Duct., PDAC: Pancreatic Ductal Adenocarcinoma Neuroendocrine Tumor., IPMN: Intraductal Papillary Mucinous Neoplasm., SCA: Serous Cystadenoma., NSD: Normalized Surface Dice., HU: Hounsfield Unit Pancreatic neoplasm. Main Pancreatic Duct. Portal venous CT. Lesion detection. Deep Learning

Objectives

This study proposes and evaluates a deep learning method to detect pancreatic neoplasms and to identify main pancreatic duct (MPD) dilatation on portal venous computed tomography (CT) scans.

Materials and Methods

A total of 2890 portal venous CT scans from 9 institutions were acquired, among which 2185 had a pancreatic neoplasm and 705 were healthy controls. Each scan was reviewed by one in a group of 9 radiologists. Physicians contoured the pancreas, pancreatic lesions if present, and the MPD if visible.

They also assessed tumor type and MPD dilatation. Data was split into a training and independent testing set of 2134 and 756 cases, respectively.

A method to detect pancreatic lesions and MPD dilatation was built in three steps. First, a segmentation network was trained in a 5-fold cross-validation manner. Second, outputs of this network were postprocessed to extract imaging features: a normalized lesion risk, the predicted lesion diameter, and the MPD diameter in the head, body, and tail of the pancreas. Third, two logistic regression models were calibrated to predict lesion presence and MPD dilatation, respectively.

Performance was assessed on the independent test cohort using receiver operating characteristic analysis. The method was also evaluated on subgroups defined based on lesion types and characteristics.

Results

The area under the curve (AUC) of the model detecting lesion presence in a patient was 0.98 (95% CI: 0.97, 0.99). A sensitivity of 0.94 (469 of 493, 95% CI: 0.92, 0.97) was reported. Similar values were obtained in patients with small (less than 2cm) and isodense lesions with a sensitivity of 0.94 (115 of 123, 95% CI: 0.87, 0.98) and 0.95 (53 of 56, 95% CI: 0.87, 1.0), respectively. The model sensitivity was also comparable across lesion types with values of 0.94 (95% CI: 0.91, 0.97), 1.0 (95% CI: 0.98, 1.0), 0.96 (0.97, 1.0) for pancreatic ductal adenocarcinoma, neuroendocrine tumor and intraductal papillary neoplasm, respectively. Regarding MPD dilatation detection, the model had an AUC of 0.97 (95% CI: 0.96, 0.98).

Conclusions

The proposed approach showed high quantitative performance to identify patients with pancreatic neoplasms and to detect MPD dilatation on an independent test cohort. Performance was robust across subgroups of patients with different lesion characteristics and types. Results confirmed the interest to combine a direct lesion detection approach with secondary features such as the MPD diameter, thus indicating a promising avenue for the detection of pancreatic cancer at early stages.

Introduction

Pancreatic cancer is currently the 11 th most common cancer and the 7 th leading cause of cancer-related deaths worldwide [START_REF] Rawla | Epidemiology of pancreatic cancer: Global trends, etiology and risk factors[END_REF] . With a predicted incidence expected to increase up to 78% during the period 2018-2040, it is a major healthcare issue on the rise [START_REF] Rawla | Epidemiology of pancreatic cancer: Global trends, etiology and risk factors[END_REF] . Due to the increase of pancreatic cancer incidence, combined with its dramatically low 5-year survival rate of 9%, the disease could become the third leading cause of cancer-related deaths by 2025 [START_REF] Sung | GLOBOCAN Estimates of Incidence and Mortality Worldwide for 36 Cancers in 185 Countries. CA: A Cancer Journal for Clinicians[END_REF] .

Most patients with early pancreatic cancer present with non-specific symptoms hence, if investigated, often undergo routine computer tomography (CT) examination performed in portal venous phase.

Image interpretation might be difficult, as in early stages, pancreatic lesions tend to be small (less than 2cm) and isodense, with a reported sensitivity ranging from 58% to 77% 3 4 . In addition, radiologists' heavy workload as well as their level of expertise and experience might further affect the interpretation of a CT scan. As the disease progresses rapidly [START_REF] Raman | Impact of the time interval between MDCT imaging and surgery on the accuracy of identifying metastatic disease in patients with pancreatic cancer[END_REF] , pancreas cancer is mostly detected during late stages for which limited therapeutic options are available, thus explaining the observed low 5-year survival rate. To date only 10% [START_REF] Lucas | Screening for Pancreatic Cancer[END_REF] of patients undergo pancreatic resection, the sole curative treatment.

However, in the past years the proportion of patients diagnosed with stage 1A pancreatic cancer has increased [START_REF] Blackford | Recent trends in the incidence and survival of stage 1A pancreatic cancer: A surveillance, Epidemiology, and End Results analysis[END_REF] . At this stage, the patients are more frequently eligible for pancreatic resection and adjuvant chemotherapy and as such, the 5-year survival rate of these patients now exceeds 80% [START_REF] Blackford | Recent trends in the incidence and survival of stage 1A pancreatic cancer: A surveillance, Epidemiology, and End Results analysis[END_REF] . This highlights however, the importance for the earliest possible detection of pancreas cancer. To identify findings that should alert radiologists about the potential presence of pancreatic cancer, studies retrospectively analyzed CT scans of patients with pancreatic cancer before the histopathological diagnosis 8 9 10 11 . A consensus emerged on the fact that subtle secondary signs, such as main pancreatic duct (MPD) dilatation, were often visible up to 1 year before the cancer diagnosis. This is due to the fact that pancreas cancer is mainly a ductal adenocarcinoma and the malignant tumor is responsible for a stricture of the MPD, thus causing upstream dilatation. Dilatation is usually defined as a duct larger than 3mm in the head and 2mm in the body and tail of the pancreas. In addition, enlargement upstream to a stenosis, reported to be a focal disappearing of MPD lumen, is also a pathologic pattern.

Given this context, Deep Learning (DL) methods could play an important role to assist with diagnosis, by issuing alerts for patients at risk of pancreatic cancer. Promising results have already been obtained for several diseases such as bone tumors [START_REF] Fritz | Radiomics and Deep Learning for Disease Detection in Musculoskeletal Radiology[END_REF] , prostate cancer [START_REF] Netzer | Fully Automatic Deep Learning in Bi-institutional Prostate Magnetic Resonance Imaging[END_REF] , kidney cancer [START_REF] Toda | Deep Learning Algorithm for Fully Automated Detection of Small (≤4 cm) Renal Cell Carcinoma in Contrast-Enhanced Computed Tomography Using a Multicenter Database[END_REF] . In addition, DL models could help radiologists in their daily practice. Recently, an algorithm for breast cancer detection significantly decreased the false positive and false negative rates on two large datasets, while substantially reducing the radiologists' workload [START_REF] Mckinney | International evaluation of an AI system for breast cancer screening[END_REF] . Other studies applied DL on Positron Emission Tomography (PET)/CT scans to detect lesions in the whole body, thus allowing to compute a global tumor burden potentially predictive of a patient response to treatment 16 17 18 19 . Efforts have also been directed towards pancreas cancer [START_REF] Kenner | Artificial Intelligence and Early Detection of Pancreatic Cancer: 2020 Summative Review[END_REF] with attempts to use DL for lesion detection 21 22 . These works proposed DL models to detect pancreatic neoplasms and validated them on independent databases of patients. While they showed promising results, these approaches focused on lesion detection and did not propose to detect key secondary findings such as the MPD dilatation.

In this work, a DL pipeline allowing to predict patients at risk of pancreas cancer is proposed and evaluated. The contribution is twofold: (i) a lesion segmentation algorithm is combined with information related to the lesion and MPD size, thus improving pancreatic neoplasm detection performance compared to current state-of-the-art DL models; (ii) the proposed method can also be used to predict MPD dilatation. To demonstrate the reliability of the approach the model is validated on an external test cohort.

Materials and Methods

Dataset

Data was collected from 9 medical centers in Europe, USA, and Brazil. Inclusion criteria were as follows:

(i) presence of a portal venous CT scan; (ii) maximum slice thickness of 3mm; (iii) for patient with confirmed pancreatic neoplasm, studies were acquired prior to any treatment or surgery. This led to a total of 2890 cases that were further split in a training and independent testing set of 2134 and 756 subjects, respectively (see Figure 1). Classification of Diseases (ICD-10) for the rest of the subjects. In addition, control portal CT scans were extracted from a private cohort of patients with bone lesions. The radiological reports of these patients were inspected to only keep subjects without abnormalities in the pancreas. Then, their portal CT scans were further reviewed to ensure that no pancreatic lesion was visible, thus leading to a total of 442 controls. Table 1 describes the patients characteristics. The 2134 subjects were composed of 1174 (55%) women and 960 men (45%) and showed a median age of 64 years old (range [56, 73] years).

1184 patients had Pancreatic Ductal Adenocarcinoma (PDAC), 134 had Neuroendocrine Tumor (NET) and 158 had unclassified solid lesion. There were also 81 subjects with Intraductal Papillary Mucinous Neoplasm (IPMN), 34 with Mucinous Cystic Neoplasm (MCN) and 42 with Serous Cystadenoma (SCA), as well as 59 subjects with unclassified cystic lesion. Finally, 43% (907) of the subjects had dilated MPD.

The external test set included 756 subjects collected from both public and private data in 4 institutions (cf. Figure 1). These institutions were different from the ones used in the training set. Public data contained 361 portal venous CT scans among which 281 had a pancreatic lesion and 80 were healthy 24 25 . The private dataset was composed of 212 portal venous CT scans of patients with histopathological confirmation of pancreatic neoplasm. In addition, routine portal CT scans from the gastroenterology department of a private institution were acquired. Scans were further reviewed by the radiologists pool to confirm that they did not have a pancreatic lesion, leading to a total of 183 control cases. Demographic information was not available for the subjects from the test set. This database was composed of patients with PDAC (n=360), NET (n=48) and unclassified solid lesions (n=12), as well as IPMN (n=18) and unclassified cystic lesions (n=53) (cf. Table 1). Finally, 276 subjects had dilated MPD.

Annotation Protocol

Each portal venous CT scan was reviewed and annotated by one in a group of 9 radiologists. The annotators segmented the pancreas on each image. When a lesion was identified by the radiologist it was systematically segmented. The radiologists characterized the tumor type based on the CT scan.

Possible types were: PDAC, NET, IPMN, MCN and SCA. Cases for which the lesion type could not be determined were labeled as unclassified. In addition, lesion density was characterized with four possible answers: hyper-enhancing, hypo-enhancing, isodense, and unclassified. A lesion was considered isodense when its density was similar to the one of the adjacent pancreatic parenchyma and there was a secondary sign, such as abrupt cutoff of the MPD or the common bile duct, allowing to confirm lesion presence. In total, 2526 lesions were segmented. Lesion segmentation variability was investigated in Appendix 1. This analysis estimated that the average inter-annotator variability ranged from 0 to 0.12 Dice score points, which is a reasonable variability threshold for pancreatic lesions whose contours can be hard to define. Finally, the radiologists segmented the MPD when it was visible and visually assessed MPD dilatation. In practice, CT scans were annotated using a custom module of the 3D Slicer 26 27 software that was developed internally. For each case, the ground truth 3D segmentation was generated by segmenting the pancreas, lesions, and MPD slice by slice. The customized version of 3D Slicer also allowed the radiologists to answer questions regarding lesions' characteristics and MPD dilatation.

Detection Pipeline

Segmentation

A 3D nnUNet [START_REF] Isensee | nnU-Net: a self-configuring method for deep learning-based biomedical image segmentation[END_REF] was trained to segment the pancreas, lesions and the MPD in a 5-fold cross-validation setting. The nnUNet is a self-configuring segmentation framework which automatically determines for a given dataset a suited image preprocessing pipeline, as well as an adapted UNet architecture. In this case, images were resampled to a target spacing of (0.79, 0.79, 2) mm/voxel using 3 rd order bspline When applied on a new image, the trained nnUNet generated a segmentation of the pancreas, pancreatic lesion and MPD, as well as a lesion probability map assigning to each voxel a probability to be a lesion (cf. Figure 2).

Feature extraction

Using the output of the nnUNet, features were extracted as follows: (i) a lesion risk between 0 and 1, computed based on the 3D probability map given by the nnUNet. To do so, all the candidate lesions outside the pancreas were eliminated using the segmentation map. Then for each connected component a lesion risk between 0 and 1 was computed by averaging the probabilities of all its voxels.

Connected components with a lesion risk lower than 0.05 were automatically removed; (ii) the maximum diameter of the lesion segmented by the nnUNet, computed as the maximum 2D Feret diameter [START_REF] Van Der Walt | scikit-image: image processing in Python[END_REF] of the lesion segmented by the nnUNet. If no lesion was segmented it was set to 0; (iii) the maximum MPD diameter in the head, body, and tail of the pancreas. Computation was carried out using the IMEA [START_REF] Kroell | imea: A Python package for extracting 2D and 3D shape measurements from images[END_REF] library. Details on how the head, body, and tail of the pancreas were identified are provided in Appendix 3. The maximum value of the MPD diameter in the pancreas was also computed by taking the maximum diameter between head, body, and tail. For each region the MPD diameter was set to 0 if there was no segmentation.

Logistic Regression

We proposed to predict lesion presence in a patient as well as MPD dilatation using two logistic regression models relying on the features previously defined. In practice, the nnUNet was applied on the validation set of each fold, leading to a total of 2134 3D probability maps and segmentations, from which features were extracted. Two logistic regression models were trained using the Scikit-Learn library [START_REF] Pedregosa | Scikit-learn: Machine Learning in Python[END_REF] . To reduce the potential impact of class imbalance, the two logistic regression models were regularized by balancing the cost function with the inverse class frequencies. The first logistic regression predicted lesion presence based on three features: 1) lesion risk; 2) lesion diameter; 3) maximum MPD diameter in the pancreas. These features were extracted for all candidate lesions of each case. Candidate lesions matching a ground truth lesion (Dice score greater than 0.1) were considered as true positives, while candidate lesions that did not match a ground truth lesion were considered as false positives. Based on these target classes the logistic regression could be calibrated on the training set.

The second logistic regression model predicted MPD dilatation using the MPD diameter in the head, body, and tail of the pancreas.

Once the two logistic regressions were trained, evaluation of a test subject comprised three steps: 1) computing the lesion probability map as well as the segmentation of the pancreas, lesion and MPD using the nnUNet; 2) features extraction; 3) applying the two logistic regression models previously trained to predict lesion presence as well as MPD dilatation (see Figure 2).

Statistical Analysis

To evaluate performance, the receiver operating characteristic (ROC) curve was constructed by plotting sensitivity against false positive rate at different thresholds. The area under the curve (AUC)

was measured, as well as sensitivity, specificity, positive predictive value (PPV) and negative predictive value (NPV) at the operating point maximizing the balanced accuracy. The evaluation was performed at the case-level for both lesion presence and MPD dilatation. For instance, in the case of lesion detection, sensitivity was defined as the ratio of the number of patients correctly detected with a lesion by the model to the total number of patients with a pancreatic lesion. Computation of the other metrics was defined accordingly. Details on how each metric was computed are provided in Appendix 4 and 5.

Bootstrap sampling was used to provide median values and 95% confidence intervals (CI) for AUC, sensitivity, specificity, PPV and NPV.

Finally, segmentation performance was evaluated by calculating the Dice and the Normalized Surface Dice (NSD) scores, which measure the overlap between the reference and predicted segmentation for each test patient. The NSD allows a tolerance error between the reference and predicted segmentation 32 . This metric is well-suited to evaluate structures such as pancreatic lesions and the MPD which can be hard to accurately delineate. In this study, the tolerance error was set to 2mm along each spatial dimension. To distinguish between segmentation error types, voxel-level False Positive Rate (FPR) and False Negative Rate (FNR) were computed. The FPR was defined for each class as the number of wrongly segmented voxels to the total number of segmented voxels. The FNR was computed accordingly.

Results

Detecting Patients with Pancreatic Neoplasms

The model performance on the test set is reported in Figure 3 In order to compare with other methods, the model performance on public data (defined in Figure 1)

is also reported in Table 2. Evaluation metrics remained similar to the ones obtained on the whole test set.

The model was also evaluated on subjects with specific lesions characteristics and types. Five subgroups of the cohort were further investigated: (i) patients with lesions less than 2cm in diameter;

(ii) patients with isodense lesions; (iii) patients with PDAC; (iv) patients with NET; (v) patients with IPMN. Performances obtained on these subsets are reported in Table 2. The AUC, sensitivity, and specificity remained consistent across the subgroups and equivalent to the ones obtained on the whole test set. The model performed best on the NET subgroup with a sensitivity of 1.0 (95% CI: 0.98, 1.0).

Specificity was slightly lower on small lesions compared to the other subsets.

Feature Importance on Lesion Detection Sensitivity

The logistic regression model used to predict lesion presence in a patient was based on three features: lesion risk, lesion diameter and MPD diameter (cf. Section 2.3.2). To evaluate the effect of combining these features on performance, an ablation study was carried out. Two additional logistic regression models were trained: a first one with two features, lesion risk and lesion diameter; and a second one using only lesion risk. Table 3 reports the sensitivity of these three models on the test set, as well as on the subsets previously defined in Section 3.1.

Using the MPD diameter and the lesion diameter systematically improved lesion detection sensitivity across all groups. On the whole test set, adding the MPD diameter and lesion diameter led to a sensitivity improvement of 4% compared to the baseline model using the lesion risk only. The effect of these two features was particularly strong on isodense lesions with a sensitivity gain of 10% with respect to the model with one feature only.

Discussion

In this study, we presented a method to automatically detect patients with pancreatic neoplasms and to identify cases with MPD dilatation. The proposed approach was validated on an independent cohort of 756 subjects. We showed how using the MPD dilatation information could improve sensitivity for lesion detection compared to a baseline approach solely relying on a segmentation network output.

Finally, we evaluated the ability of our model to correctly localize the pancreas, lesions, and the MPD, by assessing its segmentation performance.

The model was assessed on subgroups of patients based on lesion characteristics and types. Similar AUC, sensitivity and specificity were observed across the different subgroups, thus highlighting the robustness of our approach. A greater variability was observed in the case of PPV and NPV, mostly due to the imbalance between healthy and diseased subjects in some subgroups such as NET (49 of 312) and IPMN (18 of 290). More generally, the test set was mostly composed of subjects with pancreatic lesions (65% of the cases). Given this distribution, a model that tends to over-detect lesions could be favored compared to an unbiased model. However, it can be noticed in Table 2 that class imbalances change depending on the sub-analysis. In the isodense subgroup only 18% of cases had a pancreatic lesion while the rest were controls. Conversely, the public data subgroup was mostly composed of pathological cases (78%). Yet, a median AUC of 0.97 and 0.99, a median sensitivity of 0.95 and 0.94, and a median specificity of 0.94 and 0.95 were reported for the isodense and public data subgroups, respectively. This result shows that on two subsets with radically different class distribution, the lesion detection model led to comparable results, highlighting its robustness to class imbalance.

The results on public data can be compared to competing DL models that used this database to test their approach. In 33 the authors reported an AUC of 0.91 and in [START_REF] Liu | Deep learning to distinguish pancreatic cancer tissue from noncancerous pancreatic tissue: a retrospective study with cross-racial external validation[END_REF] they obtained an AUC of 0.92 (95% CI: 0.89, 0.95). Our algorithm showed notably higher performance with an AUC of 0.99 (95% CI: 0.98, 0.99). This might be explained by the size of our training database (more than 2000 cases), which is larger than what competing DL approaches reported so far 21 22 , thus allowing better generalization on independent cohorts. Moreover, generalization was also helped by the diversity of the training data which was composed of various types of tumors such as PDAC, NET, or IPMN.

However, improved performance can also be attributed to the combination of specific features to predict lesion presence. While recent approaches tend to either rely on a pure DL segmentation model or combined segmentation-classification networks, we used the lesion risk, the MPD diameter, and lesion diameter, to predict lesion presence via a separate logistic regression. The advantage of this approach compared to end-to-end DL methods is twofold: (i) it does not require to modify the UNet architecture by incorporating a classification module which may overfit; (ii) it relies on both a small number of interpretable features and an explainable classification method, thus better allowing to understand the model predictions. To evaluate the effect of combining features, the sensitivity of the logistic regression was measured according to the features used to train it. The logistic regression model using only the lesion risk, the one most closely resembling state-of-the-art approaches, had a lower sensitivity on all subsets compared to the models using two or three features. In particular, using the MPD diameter systematically improved sensitivity, especially for isodense lesions (plus 5%). This is probably due to the fact that MPD dilatation is often observed on CT scans during early stages of pancreatic cancer, thus helping to identify iso-attenuating tumors [START_REF] Yoon | Small (< 20 mm) Pancreatic Adenocarcinomas: Analysis of Enhancement Patterns and Secondary Signs with Multiphasic Multidetector CT[END_REF] . Improvement of sensitivity for PDAC detection (plus 5%) when using the lesion and MPD diameter was also observed. Regarding pancreas NET, a milder effect was observed (plus 2% sensitivity). However, as NETs are not linked to MPD dilatation, effect on sensitivity in patient with NET was not anticipated. Finally, even though adding MPD diameter and lesion diameter strongly improved sensitivity in the case of IPMN (plus 6%), the low number of cases (18 of 290) have prevented from drawing any conclusion.

The segmentation network was also leveraged to design a logistic regression model predicting MPD dilatation based on its diameter in the head, body, and tail of the pancreas (see Section 2.3.3). An AUC of 0.97 (95% CI: 0.96, 0.98) was reported. We highlight that even if other DL methods allow to segment the MPD 36 37 , none of them took advantage of the MPD segmentation to provide an alert on its potential dilatation, which is a key finding for radiologists when assessing the pancreas.

Segmentation performance of the algorithm on the pancreas, lesions, and MPD was also assessed.

Regarding the pancreas, there were no competing DL methods which evaluated the Dice score on the same datasets as in this study. However, three DL models which reported a mean Dice score of 0.87 on their test set were found in 38 39 40 . The segmentation network presented in this work obtained a similar result on public data and a higher mean Dice score on the whole test set. As for lesion segmentation, a mean Dice score of 0.63 was obtained on public data. This is a 9% improvement over the nnUNet trained in [START_REF] Isensee | nnU-Net: a self-configuring method for deep learning-based biomedical image segmentation[END_REF] which reported a Dice score of 0.54 on this dataset. Finally, we could not find Dice scores obtained by other DL approaches for the MPD. However, given the small size of the MPD and compared to the Dice score obtained on lesions, the model seemed to show satisfactory performance corroborated by an NSD score of 0.71 on the test set. While higher than in published work, mean Dice score values remained below 0.7 for lesions and the MPD. The reason for this is twofold: (i) for false negative and false positive cases, the associated Dice score will be 0, thus strongly deteriorating the mean value. We show in Appendix 8 that using the median instead of the mean allows to be more robust to these extreme cases. A median Dice score of 0.83 and 0.69 were reported for lesions and the MPD, respectively; (ii) Lesions and the MPD are difficult to segment, with potentially few voxels, and contours hard to define. The Dice score strongly penalizes segmentation errors in this scenario. Using the NSD better highlights the predicted segmentation quality for these structures.

Compared to the Dice score, a gain of 0.08 and 0.13 points were observed for the NSD in the case of lesions and the MPD, respectively. There were several limitations to this study. First, tumor type was visually assessed by the radiologists, which, due to some cases being indeterminate, led to a significant number of unclassified lesion types: 218 in the training set and 65 in the test set. These cases were not included for the subgroup analysis in Tables 2 and3. Second, the number of subjects with specific lesions characteristics or tumor types was rather limited for some subgroups, especially in the case of isodense lesions (56 of 319), patients with NETs (49 of 312), and patients with IPMN (18 out of 290). Future work should focus on creating more diverse test cohorts to evaluate our algorithm. Third, MPD dilatation was assessed visually and not based on a quantitative measure of the MPD diameter.

In conclusion, the presented DL approach showed promising results to detect subjects with pancreatic neoplasm and to identify cases with MPD dilatation. In particular, the combination of the output of a segmentation network with secondary features increased lesion detection performance. Future efforts should focus on acquiring additional data with greater diversity of lesions characteristics to increase the model robustness. The model should also be further validated on a test cohort more representative of typical missed cases (small and isodense lesions). A different study design could also be proposed, by applying the model on a longitudinal cohort of patients which were eventually diagnosed with pancreatic neoplasm. This type of study would be of great interest to assess the ability of the model to detect early-stage pancreas cancer. Such an evaluation could be conducted via a retrospective study in collaboration with clinical institutions having sufficiently large volume of patients.

Currently, the model can be used as a pipeline taking a portal CT scan as input and generating a segmentation of the pancreas, lesion if detected, and the MPD if visible. It also generates an alert stating if a lesion is present and if the MPD is dilated. However, this pipeline has not been industrialized yet and can only be used in a research environment. Therefore, a software development effort needs to be undertaken to reach clinical deployment. Ultimately, we aim to provide a diagnostic tool assisting radiologists in routine clinical practice by issuing an alert when a pancreatic lesion is suspected by the model, with an emphasis on detection of early-stage tumors to improve long-term outcome for patients with pancreatic cancer.

Figure 1 :

 1 Figure 1: Composition of the training and testing sets. Data in the training and testing sets come from different institutions. ICD: International Classification of Diseases.

  interpolation. Based on the training cases, a mean and standard deviation intensity of 68.7 Hounsfield Unit (HU) and 51.0 HU were computed and used to perform a z-normalization on the images. A batch size of 2 and a patch size of (192, 128, 56) along the x, y, and z axes, were selected. The loss function consisted in the sum of the Cross-entropy and Soft Dice loss functions. The model was optimized using Stochastic Gradient Descent with a learning rate of 0.01 and polynomial decay. Details on the heuristics allowing to infer the parameters values are provided in Appendix 2, as well as a figure of the resulting UNet architecture.

Figure 2 :

 2 Figure 2: The algorithm is composed of three steps: 1) Based on a portal venous CT scan, the nnUNet generates a lesion probability map as well as a segmentation of the pancreas (red), lesions (green) and MPD (blue). 2) Lesion and MPD features are extracted. 3) Lesion presence and MPD dilatation are predicted using two logistic regression models. MPD: Main Pancreatic Duct. CT: Computed Tomography.

Figure 3 :

 3 Figure 3: Left) ROC curve of the logistic regression model predicting lesion presence. The central line represents the average curve and shadowed areas the 95% confidence interval. Right) Confusion matrix of the model obtained at the operating point maximizing the balanced accuracy. ROC: Receiver Operating Characteristic. AUC: Area Under the Curve.

Figure 4 :

 4 Figure 4: Left column: Axial portal venous CT slices of four patients. White arrows indicate lesions location for the first three rows and the MPD for the last row. Right column: Segmentation of pancreas (red), lesions (green) and MPD (blue) output by our model. PDAC: Pancreatic Ductal Adenocarcinoma.

Table 1 :

 1 Demographic and clinical information for the different datasets. If not specified data

	are number of patients with percentages in parentheses. * Data are medians with interquartile
	range in square brackets. CT: Computed Tomography. GE: General Electric. PDAC: Pancreatic
	Ductal Adenocarcinoma. NET: Neuroendocrine Tumor. IPMN: Intraductal Papillary Mucinous
	Neoplasm. MCN: Mucinous Cystic Neoplasm. SCN: Serous Cystadenoma. NA: Not Available.

  and Table 2. The model reached an AUC

	of 0.98 (95% CI: 0.97, 0.99) as well as a sensitivity of 0.94 (469 of 493, 95% CI: 0.92, 0.97) and a
	specificity of 0.95 (246 of 262, 95% CI: 0.92, 0.98). A boxplot showing the evaluation metrics
	distributions is provided in Appendix 6.

Table 2 :

 2 Evaluation

		AUC	Sensitivity	Specificity	PPV	NPV
	Test set (493/756)	0.98 [0.97, 0.99] 0.94 [0.92, 0.97] 0.95 [0.92, 0.98] 0.97 [0.96, 0.99] 0.90 [0.85, 0.94]
	Public data (281/361)	0.99 [0.98, 0.99] 0.94 [0.88, 0.98]	0.95 [0.90, 1.0]	0.99 [0.97, 1.0]	0.82 [0.67, 0.94]
	Lesions characteristics
	D ≤2cm (123/386)	0.97 [0.95, 0.98] 0.94 [0.87, 0.98] 0.91 [0.85, 0.96] 0.83 [0.74, 0.92] 0.97 [0.94, 0.99]
	Isodense (56/319)	0.97 [0.95, 0.99]	0.95 [0.87, 1.0]	0.94 [0.85, 0.98] 0.78 [0.57, 0.90]	0.99 [0.97, 1.0]
	Lesions type
	PDAC (418/681)	0.98 [0.98, 0.99] 0.94 [0.91, 0.97] 0.96 [0.92, 0.98] 0.97 [0.95, 0.99] 0.92 [0.88, 0.96]
	NET (49/311)	0.99 [0.98, 1.0]	1.0 [0.98, 1.0]	0.96 [0.92, 0.98] 0.81 [0.69, 0.92]	1.0 [1.0, 1.0]
	IPMN (18/290)	0.98 [0.95, 0.99]	0.96 [0.87, 1.0]	0.94 [0.91, 0.98]	0.56 [0.29, 0.8]	1.0 [0.99, 1.0]

metrics obtained for lesion detection on the test set as well as on specific subsets of patients. In parenthesis for each group, number of patients with pancreatic neoplasm to the total number of patients. Data are median values with 95% confidence interval in square brackets. AUC: Area Under the Curve. PPV: Positive Predictive Value. NPV: Negative Predictive Value. D: Diameter. PDAC: Pancreatic Ductal Adenocarcinoma. NET: Neuroendocrine Tumor. IPMN: Intraductal Papillary Mucinous Neoplasm.

Table 3 :

 3 Sensitivity of the logistic regression predicting lesion presence depending on the features used

	to train it. In parenthesis for each group, number of patients with pancreatic neoplasm to the total
	number of patients Median values and 95% confidence intervals in square brackets. D: Diameter. PDAC:
	Pancreatic Ductal Adenocarcinoma. NET: Neuroendocrine Tumor. IPMN: Intraductal Papillary
	Mucinous Neoplasm.

Table 5 :

 5 Dice score, NSD score, FPR, and FNR measured on the whole test set and public data. The Dice score, the FPR, and the FNR were computed for the pancreas, lesions, and the main pancreatic duct. The NSD score was measured for lesion and the main pancreatic duct only. Data are mean values plus/minus standard deviation. NSD: Normalized Surface Dice. FPR: False Positive Rate. FNR: False Negative Rate.

Research study funded by Guerbet and BPI France within the scope of the France 2030 project.

MPD Dilatation Detection Performance

Regarding MPD dilatation performance, the model of Section 2.3.3 was also evaluated on the test set.

Results are reported in Table 4. An AUC of 0.97 (95% CI: 0.96, 0.98) was reached as well as a sensitivity of 0.94 (259 of 276, 95%: CI: 0.89, 0.97) and a specificity of 0.90 (432 of 480, 95%CI: 0.86, 0.94). A boxplot showing the evaluation metrics distributions is provided in Appendix 6.

Segmentation Performance

Segmentations predicted by the nnUNet of Section 2.3.1 were evaluated both quantitatively and qualitatively. The Dice score between the ground truth and the nnUNet segmentation maps is reported in Table 5 for the pancreas, lesions, and the MPD. The FPR and FNR were also computed for the three structures. The NSD score was computed for lesions and the MPD. These metrics were also measured on public data only in order to compare our segmentation network to other works. Qualitative examples of the model segmentations are provided in Figure 4. Additional cases are presented in Appendix 7.

On the whole test set, the mean Dice score was 0.91 (± 0.06), 0.69 (± 0.34) and 0.58 (± 0.37) for the pancreas, lesions, and MPD, respectively. The mean NSD score was 0.71 (± 0.39) and 0.77 (± 0.33) for the MPD and lesions, respectively. While the FPR and FNR were similar for the pancreas on both the whole test set and public data, the FNR was systematically higher than the FPR for lesions and the MPD. A boxplot illustrating segmentation performance over the complete cohort is provided in Appendix 8.

AUC


S D Adhikari

R Balasubramanian

S Eliahou

D J Grynkiewicz

ON THE DEGREE OF REGULARITY OF A PARTICULAR LINEAR EQUATION

There are many interesting results and open questions regarding the degree of regularity of Diophantine equations. The Fox and Kleitman conjecture [5] concerning the maximum degree of regularity of the equation x1 +

. We here consider the problem of finding the degree of regularity of some specializations of the above equation.

Introduction

For given a 1 , . . . , a k and b in the set Z of integers, we consider the linear Diophantine equation L:

k i=1 a i x i = b.
Following [START_REF] Rado | Studien zur Kombinatorik[END_REF], given n ∈ N + , the set of positive integers, equation L is said to be n-regular if, for every n-coloring of N + , there exists a monochromatic solution x = (x 1 , . . . , x k ) ∈ N k + to L. The degree of regularity of L is the largest integer n ≥ 0, if any, such that L is n-regular. This (possibly infinite) number is denoted by dor(L). If dor(L) = ∞, then L is said to be regular.

A well-known and challenging conjecture (known as Rado's Boundedness Conjecture) due to Rado [START_REF] Rado | Studien zur Kombinatorik[END_REF] states that there is a function r : N + → N + such that, given any n ∈ N + and any equation α 1 x 1 + • • • + α n x n = 0 with integer coefficients, if this equation is not regular over N + , then it fails to be r(n)-regular. Even though there is a more general version, we state it here for a single homogeneous equation, as it has been proved by Rado [6] that if the conjecture is true for a single equation, then it is true for a system of finitely many linear equations, and as Fox and Kleitman [START_REF] Fox | On Rado's Boundedness Conjecture[END_REF] have shown, if the conjecture is true for a linear homogeneous equation, then it is true for any linear equation.

The first nontrivial case of the conjecture has been proved by Fox and Kleitman [START_REF] Fox | On Rado's Boundedness Conjecture[END_REF] by establishing the bound r(3) ≤ 24. In the same paper [START_REF] Fox | On Rado's Boundedness Conjecture[END_REF], the authors made the following conjecture for a very specific linear Diophantine equation.

Conjecture 1.1. Let k ≥ 1. There exists an integer b k ≥ 1 such that the degree of regularity of the 2k-variable equation L k (b k ), Fox and Kleitman [START_REF] Fox | On Rado's Boundedness Conjecture[END_REF] had proved the following.

x 1 + • • • + x k -y 1 -• • • -y k = b k ,
Proposition 1.2. For any b ∈ N + , the equation L k (b) is not 2k-regular.
After some initial results ([1], [START_REF] Adhikari | Equation-regular sets and the Fox-Kleitman conjecture[END_REF]) for small values of k, the full conjecture of Fox and Kleitman has been very recently established by Schoen and Taczala in [START_REF] Schoen | The degree of regularity of the equation n i=1 xi = n i=1 yi + b[END_REF] by generalizing a theorem of Eberhard, Green and Manners [START_REF] Eberhard | Sets of integers with no large sum-free subset[END_REF].

In [3], Bialostocki et al. considered equation L, that is k i=1 a i x i = b,
where k i=1 a i = 0 and b = 0. Among other things, the paper [START_REF] Bialostocki | On the degree of regularity of some equations[END_REF]

established dor(x 1 + x 2 -2y 1 = b) under the condition x 1 < y 1 < x 2 .
Here in Section 4, following some line of arguments in [START_REF] Adhikari | On a conjecture of Fox and Kleitman on the degree of regularity of a certain linear equation[END_REF], we furnish a somewhat different proof for the result on dor(x 1 + x 2 -2y 1 = b); because of Proposition 1.2, the result here is unconditional.

The Equation

x 1 + x 2 -2y 1 = b
As mentioned in the introduction, Bialostocki et al. [START_REF] Bialostocki | On the degree of regularity of some equations[END_REF] established dor(

x 1 + x 2 -2y 1 = b), under the condition x 1 < y 1 < x 2 .
Here, following the line of arguments in [START_REF] Adhikari | On a conjecture of Fox and Kleitman on the degree of regularity of a certain linear equation[END_REF], we give a proof of the following.

x 1 + x 2 -2y 1 = b.
For all positive integers b, we have

dor(L (b)) =      1 if b ≡ 1 (mod 2), 2 if b ≡ 2, 4 (mod 6), 3 if b ≡ 0 (mod 6). Proof. Because of Proposition 1.2, dor(L (b)) ≤ dor(L 2 (b)) ≤ 3. Again, since L (b) is solvable in N + , we have 1 ≤ dor(L (b)). Thus, 1 ≤ dor(L (b)) ≤ 3.
The proof will be complete with the following observations. Observation 1. Consider the 2-coloring of N + given by coloring each integer according to its residue class modulo 2. Let (λ 1 , λ 2 , λ 3 ) be a monochromatic solution to L (b) under this coloring.

This will imply

λ 1 + λ 2 -2λ 3 ≡ 0 (mod 2).
Therefore, if b is odd, there cannot be a monochromatic solution in N Since, for any 2-coloring of N + , at least two elements in the set {b + 1, h + 1, 1} must be of the same color, at least one of the above three solutions must be monochromatic, and hence dor(L (b)) ≥ 2 when b is even. Observation 3. If b ≡ 0 (mod 3), then coloring each integer according to its residue class modulo 3 gives a coloring of N + for which there cannot be any monochromatic solution to L (b), and hence dor(L (b)) ≤ 2 in this case.

Observation 4. Here we consider the case b ≡ 0 (mod 6). Since the sum of coefficients is zero, it is easy to see that if L ( 6) is proved to be 3-regular, then so is L (b).

Let c : N + → {0, 1, 2} be an arbitrary 3-coloring of N + . Consider the following families of special solutions to L (6) parametrized by a ∈ N + :

(a + 6, a, a), (a + 5, a + 1, a), (a + 4, a + 2, a), (a + 3, a + 3, a), (a + 8, a, a + 1), (a + 1, a + 9, a + 2).

The underlying sets for each of these solutions can be assumed to be multi-chromatic, and thus all sets from E = {a, a+3}, {a, a+6}, {a, a+2, a+4}, {a, a+1, a+5}, {a, a+1, a+8}, {a+1, a+9, a+2} , where a ranges through N + , are multi-chromatic sets under c.

As just observed, the integer a must be colored distinctly from both a+3 and a+6. Moreover, if c(a + 6) = c(a + 3), then we would obtain the monochromatic solution (a + 6, a + 6, a + 3). It follows that {c(a), c(a + 3), c(a + 6)} = {0, 1, 2} = {c(a + 3), c(a + 6), c(a + 9)}, with the second equality following by the same argument used for the first, only replacing a by a + 3. Hence c(a) = c(a + 9).

Thus the color of an integer only depends on its residue class modulo 9. So, denoting the elements of Z/9Z by 0, 1, . . . , 8 and their respective colors under c by c 0 , c 1 , . . . , c 8 (with indices modulo 9), we may depict the distribution of colors by the following table:

7 Feb 2018 20:39:44 PST Version 2 -Submitted to Acta Arith. Since the sets {a, a + 2, a + 4}, {a, a + 1, a + 5} and {a + 1, a + 2, a + 9} belong to E for all a ∈ N + , and are assumed to be multichromatic under c, for all i ∈ Z/9Z, we have

{c i , c i+2 , c i+4 } ≥ 2, ( 1
)
{c i , c i+1 , c i+5 } ≥ 2, ( 2
)
{c i , c i+1 , c i+2 } ≥ 2. ( 3
)
We may assume that the first column (c 0 , c 3 , c 6 ) of C is equal to (0, 1, 2) and the table is as follows:

Table 2 0 c 1 c 2 1 c 4 c 5 2 c 7 c 8
The second and third columns of C being permutations of its first column, there are nine possible pairs holding the remaining two 0's in C: Hence none of the pairs from (4) can equal (0, 0), contradicting that the two remaining 0's in C must lie in one of the pairs from (4).

7 Feb 2018 20:39:44 PST Version 2 -Submitted to Acta Arith.

1 7

 1 Feb 2018 20:39:44 PST Version 2 -Submitted to Acta Arith. is exactly 2k -1.

Theorem 2 . 1 .

 21 Consider the equation L (b):

  3 + and hence dor(L (b)) = 1 in this case.

Observation 2 .

 2 Let b be even and write h = b/2 with h ∈ N + . The following three vectors in N 3 + are solutions to L (b): (b + 1, 1, 1), (h + 1, h + 1, 1), (b + 1, b + 1, h + 1).

(c 1

 1 , c 2 ), (c 1 , c 5 ), (c 1 , c 8 ); (c 4 , c 2 ), (c 4 , c 5 ), (c 4 , c 8 ); (4) (c 7 , c 2 ), (c 7 , c 5 ), (c 7 , c 8 ). However, recalling that c 0 = 0, we have {c 0 , c 1 , c 2 } ≥ 2 by (3), {c 0 , c 1 , c 5 } ≥ 2 by (2), {c 8 , c 0 , c 1 } ≥ 2 by (3); {c 0 , c 2 , c 4 } ≥ 2 by (1), {c 4 , c 5 , c 0 } ≥ 2 by (2), {c 8 , c 0 , c 4 } ≥ 2 by (2); {c 7 , c 0 , c 2 } ≥ 2 by (1), {c 5 , c 7 , c 0 } ≥ 2 by (1), {c 7 , c 8 , c 0 } ≥ 2 by (3).

Table 1 .

 1 The color table C c 0 c 1 c 2 c 3 c 4 c 5 c 6 c 7 c 8