Jonathan Vacher
email: vacher@ceremade.dauphine.fr

Andrew Isaac Meso
email: andrew.meso@univ-amu.fr

Laurent Perrinet
email: laurent.perrinet@univ-amu.fr

Gabriel Peyré
email: peyre@ceremade.dauphine.fr

Biologically Inspired Dynamic Textures for Probing Motion Perception

Perception is often described as a predictive process based on an optimal inference with respect to a generative model. We study here the principled construction of a generative model specifically crafted to probe motion perception. In that context, we first provide an axiomatic, biologically-driven derivation of the model. This model synthesizes random dynamic textures which are defined by stationary Gaussian distributions obtained by the random aggregation of warped patterns. Importantly, we show that this model can equivalently be described as a stochastic partial differential equation. Using this characterization of motion in images, it allows us to recast motion-energy models into a principled Bayesian inference framework. Finally, we apply these textures in order to psychophysically probe speed perception in humans. In this framework, while the likelihood is derived from the generative model, the prior is estimated from the observed results and accounts for the perceptual bias in a principled fashion.

Motivation

A normative explanation for the function of perception is to infer relevant hidden parameters from the sensory input with respect to a generative model [START_REF] Gregory | Perceptions as hypotheses[END_REF]. Equipped with some prior knowledge about this representation, this corresponds to the Bayesian brain hypothesis, as has been perfectly illustrated by the particular case of motion perception [START_REF] Weiss | Motion illusions as optimal percepts[END_REF]. However, the Gaussian hypothesis related to the parameterization of knowledge in these models -for instance in the formalization of the prior and of the likelihood functions-does not always fit with psychophysical results [START_REF] Wei | Efficient coding provides a direct link between prior and likelihood in perceptual bayesian inference[END_REF]. As such, a major challenge is to refine the definition of generative models so that they conform to the widest variety of results.

From this observation, the estimation problem inherent to perception is linked to the definition of an adequate generative model. In particular, the simplest generative model to describe visual motion is the luminance conservation equation. It states that luminance I(x, t) for (x, t) ∈ R 2 × R is approximately conserved along trajectories defined as integral lines of a vector field v(x, t) ∈ R 2 × R. The corresponding generative model defines random fields as solutions to the stochastic partial differential equation (sPDE),

v, ∇I + ∂I ∂t = W, (1)
1 where •, • denotes the Euclidean scalar product in R 2 , ∇I is the spatial gradient of I. To match the statistics of natural scenes or some category of textures, the driving term W is usually defined as a colored noise corresponding to some average spatio-temporal coupling, and is parameterized by a covariance matrix Σ, while the field is usually a constant vector v(x, t) = v 0 accounting for a full-field translation with constant speed.

Ultimately, the application of this generative model is essential for probing the visual system, for instance to understand how observers might detect motion in a scene. Indeed, as shown by [START_REF] Nestares | Likelihood functions and confidence bounds for total-least-squares problems[END_REF][START_REF] Weiss | Motion illusions as optimal percepts[END_REF], the negative log-likelihood corresponding to the luminance conservation model [START_REF] Adelson | Spatiotemporal energy models for the perception of motion[END_REF] and determined by a hypothesized speed v 0 is proportional to the value of the motion-energy model [START_REF] Adelson | Spatiotemporal energy models for the perception of motion[END_REF] || v 0 , ∇(K I) + ∂(K I) ∂t || 2 , where K is the whitening filter corresponding to the inverse of Σ, and is the convolution operator. Using some prior knowledge on the distribution of motions, for instance a preference for slow speeds, this indeed leads to a Bayesian formalization of this inference problem [START_REF] Weiss | Velocity likelihoods in biological and machine vision[END_REF]. This has been successful in accounting for a large class of psychophysical observations [START_REF] Weiss | Motion illusions as optimal percepts[END_REF]. As a consequence, such probabilistic frameworks allow one to connect different models from computer vision to neuroscience with a unified, principled approach.

However the model defined in [START_REF] Adelson | Spatiotemporal energy models for the perception of motion[END_REF] is obviously quite simplistic with respect to the complexity of natural scenes. It is therefore useful here to relate this problem to solutions proposed by texture synthesis methods in the computer vision community. Indeed, the literature on the subject of static textures synthesis is abundant (see [START_REF] Wei | State of the art in example-based texture synthesis[END_REF] and the references therein for applications in computer graphics). Of particular interest for us is the work of Galerne et al. [START_REF] Galerne | Micro-Texture synthesis by phase randomization[END_REF], which proposes a stationary Gaussian model restricted to static textures. Realistic dynamic texture models are however less studied, and the most prominent method is the non-parametric Gaussian auto-regressive (AR) framework of [START_REF] Doretto | Dynamic textures[END_REF], which has been refined in [START_REF] Xia | Synthesizing and mixing stationary gaussian texture models[END_REF].

Contributions. Here, we seek to engender a better understanding of motion perception by improving generative models for dynamic texture synthesis. From that perspective, we motivate the generation of optimal stimulation within a stationary Gaussian dynamic texture model. We base our model on a previously defined heuristic [START_REF] Sanz-Leon | Motion clouds: modelbased stimulus synthesis of natural-like random textures for the study of motion perception[END_REF][START_REF] Simoncini | More is not always better: adaptive gain control explains dissociation between perception and action[END_REF] coined "Motion Clouds". Our first contri- bution is an axiomatic derivation of this model, seen as a shot noise aggregation of dynamically warped "textons". This formulation is important to provide a clear understanding of the effects of the model's parameters manipulated during psychophysical experiments. Within our generative model, they correspond to average translation speed and orientation of the "textons" and standard deviations of random fluctuations around this average. Our second contribution is to demonstrate an explicit equivalence between this model and a class of linear stochastic partial differential equations (sPDE). This shows that our model is a generalization of the well-known luminance conservation equation. This sPDE formulation has two chief advantages: it allows for a real-time synthesis using an AR recurrence and it allows one to recast the log-likelihood of the model as a generalization of the classical motion energy model, which in turn is crucial to allow for a Bayesian modeling of perceptual biases. Our last contribution is an illustrative application of this model to the psychophysical study of motion perception in humans. This application shows how the model allows us to define a likelihood, which enables a simple fitting procedure to determine the prior driving the perceptual bias.

Notations. In the following, we will denote (x, t) ∈ R 2 × R the space/time variable, and (ξ, τ ) ∈ R 2 × R the corresponding frequency variables. If f (x, t) is a function defined on R 3 , then f (ξ, τ ) denotes its Fourier transform. For ξ ∈ R 2 , we denote ξ = ||ξ||(cos(∠ξ), sin(∠ξ)) ∈ R 2 its polar coordinates. For a function g in R 2 , we denote ḡ(x) = g(-x). In the following, we denote with a capital letter such as A a random variable, a we denote a a realization of A, we let P A (a) be the corresponding distribution of A.

Axiomatic Construction of a Dynamic Texture Stimulation Model

Solving a model-based estimation problem and finding optimal dynamic textures for stimulating an instance of such a model can be seen as equivalent mathematical problems. In the luminance conservation model ( 1), the generative model is parameterized by a spatio-temporal coupling function, which is encoded in the covariance Σ of the driving noise and the motion flow v 0 . This coupling (covariance) is essential as it quantifies the extent of the spatial integration area as well as the integration dynamics, an important issue in neuroscience when considering the implementation of integration mechanisms from the local to the global scale. In particular, it is important to understand modular sensitivity in the various lower visual areas with different spatio-temporal selectivities such as Primary Visual Cortex (V1) or ascending the processing hierarchy, Middle Temple area (MT). For instance, by varying the frequency bandwidth of such dynamic textures, distinct mechanisms for perception and action have been identified [START_REF] Simoncini | More is not always better: adaptive gain control explains dissociation between perception and action[END_REF]. However, such textures were based on a heuristic [START_REF] Sanz-Leon | Motion clouds: modelbased stimulus synthesis of natural-like random textures for the study of motion perception[END_REF], and our goal here is to develop a principled, axiomatic definition.

From Shot Noise to Motion Clouds

We propose a mathematically-sound derivation of a general parametric model of dynamic textures. This model is defined by aggregation, through summation, of a basic spatial "texton" template g(x). The summation reflects a transparency hypothesis, which has been adopted for instance in [START_REF] Galerne | Micro-Texture synthesis by phase randomization[END_REF]. While one could argue that this hypothesis is overly simplistic and does not model occlusions or edges, it leads to a tractable framework of stationary Gaussian textures, which has proved useful to model static micro-textures [START_REF] Galerne | Micro-Texture synthesis by phase randomization[END_REF] and dynamic natural phenomena [START_REF] Xia | Synthesizing and mixing stationary gaussian texture models[END_REF]. The simplicity of this framework allows for a fine tuning of frequency-based (Fourier) parameterization, which is desirable for the interpretation of psychophysical experiments.

We define a random field as

I λ (x, t) def. = 1 √ λ p∈N g(ϕ Ap (x -X p -V p t)) (2)
where ϕ a : R 2 → R 2 is a planar warping parameterized by a finite dimensional vector a. Intuitively, this model corresponds to a dense mixing of stereotyped, static textons as in [START_REF] Galerne | Micro-Texture synthesis by phase randomization[END_REF]. The originality is two-fold. First, the components of this mixing are derived from the texton by visual transformations ϕ Ap which may correspond to arbitrary transformations such as zooms or rotations, illustrated in Figure 1. Second, we explicitly model the motion (position X p and speed V p ) of each individual texton. The parameters (X p , V p , A p ) p∈N are independent random vectors. They account for the variability in the position of objects or observers and their speed, thus mimicking natural motions in an ambient scene. The set of translations (X p ) p∈N is a 2-D Poisson point process of intensity λ > 0.

The following section instantiates this idea and proposes canonical choices for these variabilities. The warping parameters (A p ) p are distributed according to a distribution P A . The speed parameters (V p ) p are distributed according to a distribution P V on R 2 . The following result shows that the model (2) converges to a stationary Gaussian field and gives the parameterization of the covariance. Its proof follows from a specialization of [5, Theorem 3.1] to our setting.

Proposition 1. I λ is stationary with bounded second order moments. Its covariance is Σ(x, t, x , t ) = γ(xx , tt ) where γ satisfies

∀ (x, t) ∈ R 3 , γ(x, t) = R 2 c g (ϕ a (x -νt))P V (ν)P A (a)dνda (3)
where c g = g ḡ is the auto-correlation of g. When λ → +∞, it converges (in the sense of finite dimensional distributions) toward a stationary Gaussian field I of zero mean and covariance Σ.

Definition of "Motion Clouds"

We detail this model here with warpings as rotations and scalings (see Figure 1). These account for the characteristic orientations and sizes (or spatial scales) in a scene with respect to the observer

∀ a = (θ, z) ∈ [-π, π) × R * + , ϕ a (x) def. = zR -θ (x),
where R θ is the planar rotation of angle θ. We now give some physical and biological motivation underlying our particular choice for the distributions of the parameters. We assume that the distributions P Z and P Θ of spatial scales z and orientations θ, respectively (see Figure 1), are independent and have densities, thus considering

∀ a = (θ, z) ∈ [-π, π) × R * + , P A (a) = P Z (z) P Θ (θ).
The speed vector ν is assumed to be randomly fluctuating around a central speed v 0 , so that

∀ ν ∈ R 2 , P V (ν) = P ||V -v0|| (||ν -v 0 ||). (4)
In order to obtain "optimal" responses to the stimulation (as advocated by [START_REF] Young | The gaussian derivative model for spatial-temporal vision: II. cortical data[END_REF]), it makes sense to define the texton g to be equal to an oriented Gabor acting as an atom, based on the structure of a standard receptive field of V1. Each would have a scale σ and a central frequency ξ 0 . Since the orientation and scale of the texton is handled by the (θ, z) parameters, we can impose without loss of generality the normalization ξ 0 = (1, 0). In the special case where σ → 0, g is a grating of frequency ξ 0 , and the image I is a dense mixture of drifting gratings, whose power-spectrum has a closed form expression detailed in Proposition 2. Its proof can be found in Section D.1. We call this Gaussian field a Motion Cloud (MC), and it is parameterized by the envelopes (P Z , P Θ , P V ) and has central frequency and speed (ξ 0 , v 0 ). Note that it is possible to consider any arbitrary textons g, which would give rise to more complicated parameterizations for the power spectrum ĝ, but we decided here to stick to the simple case of gratings.

Proposition 2. When g(x) = e i x, ξ0 , the image I defined in Proposition 1 is a stationary Gaussian field of covariance having the power-spectrum

∀ (ξ, τ ) ∈ R 2 × R, γ(ξ, τ ) = P Z (||ξ||) ||ξ|| 2 P Θ (∠ξ) L(P ||V -v0|| ) - τ + v 0 , ξ ||ξ|| , (5)
where the linear transform L is such that ∀u ∈ R, L(f

)(u) = π -π f (-u/ cos(ϕ))dϕ. Remark 1.
Note that the envelope of γ is shaped along a cone in the spatial and temporal domains. This is an important and novel contribution when compared to a Gaussian formulation like a classical Gabor. In particular, the bandwidth is then constant around the speed plane or the orientation line with respect to spatial frequency. Basing the generation of the textures on all possible translations, rotations and zooms, we thus provide a principled approach to show that bandwidth should be proportional to spatial frequency to provide a better model of moving textures.

Biologically-inspired Parameter Distributions

We now give meaningful specialization for the probability distributions (P Z , P Θ , P ||V -v0|| ), which are inspired by some known scaling properties of the visual transformations relevant to dynamic scene perception.

First, small, centered, linear movements of the observer along the axis of view (orthogonal to the plane of the scene) generate centered planar zooms of the image. From the linear modeling of the observer's displacement and the subsequent multiplicative nature of zoom, scaling should follow a Weber-Fechner law stating that subjective sensation when quantified is proportional to the logarithm of stimulus intensity. Thus, we choose the scaling z drawn from a log-normal distribution P Z , defined in [START_REF] Galerne | Micro-Texture synthesis by phase randomization[END_REF]. The bandwidth σ Z quantifies the variance in the amplitude of zooms of individual textons relative to the set characteristic scale z 0 . Similarly, the texture is perturbed by variation in the global angle θ of the scene: for instance, the head of the observer may roll slightly around its normal position. The von-Mises distribution -as a good approximation of the warped Gaussian distribution around the unit circle -is an adapted choice for the distribution of θ with mean θ 0 and bandwidth σ Θ , see [START_REF] Galerne | Micro-Texture synthesis by phase randomization[END_REF]. We may similarly consider that the position of the observer is variable in time. On first order, movements perpendicular to the axis of view dominate, generating random perturbations to the global translation v 0 of the image at speed νv 0 ∈ R 2 . These perturbations are for instance described by a Gaussian random walk: take for instance tremors, which are constantly jittering, small ( 1 deg) movements of the eye. This justifies the choice of a radial distribution (4) for P V . This radial distribution P ||V -v0|| is thus selected as a bell-shaped function of width σ V , and we choose here a Gaussian function for simplicity, see [START_REF] Galerne | Micro-Texture synthesis by phase randomization[END_REF]. Note that, as detailed in Section B.3 a slightly different bell-function (with a more complicated expression) should be used to obtain an exact equivalence with the sPDE discretization mentioned in Section 2.4.

The distributions of the parameters are thus chosen as

P Z (z) ∝ z 0 z e - ln ( z z 0 ) 2 2 ln ( 1+σ 2 Z ) , P Θ (θ) ∝ e cos(2(θ-θ 0 )) 4σ 2 Θ and P ||V -v0|| (r) ∝ e -r 2 2σ 2 V . (6)
Remark 2. Note that in practice we have parametrized P Z by its mode m Z = argmax z P Z (z) and standard deviation d Z = z 2 P Z (z)dz, see Section B.4 and [START_REF] Field | Relations between the statistics of natural images and the response properties of cortical cells[END_REF]. Plugging these expressions (6) into the definition (5) of the power spectrum of the motion cloud, one obtains a parameterization which is very similar to the one originally introduced in [START_REF] Simoncini | More is not always better: adaptive gain control explains dissociation between perception and action[END_REF]. The following table gives the speed v 0 and frequency (θ 0 , z 0 ) central parameters in terms of amplitude and orientation, each one being coupled with the relevant dispersion parameters. Figure 1 and2 shows a graphical display of the influence of these parameters.

z 0 σ Z σ V ξ 1 τ Slope: ∠v 0 ξ 2 ξ 1 θ 0 z 0 σ Θ σ Z Two different projections of γ in Fourier space t MC of two different spatial frequencies z

Speed

Freq. orient. Freq. amplitude (mean, dispersion)

(v 0 , σ V ) (θ 0 , σ Θ ) (z 0 , σ Z ) or (m Z , d Z ) Remark 3.
Note that the final envelope of γ is in agreement with the formulation that is used in [START_REF] Sanz-Leon | Motion clouds: modelbased stimulus synthesis of natural-like random textures for the study of motion perception[END_REF]. However, that previous derivation was based on a heuristic which intuitively emerged from a long interaction between modelers and psychophysicists. Herein, we justified these different points from first principles.

sPDE Formulation and Numerical Synthesis Algorithm

The MC model can equally be described as a stationary solution of a stochastic partial differential equation (sPDE). This sPDE formulation is important since we aim to deal with dynamic stimulation, which should be described by a causal equation which is local in time. This is crucial for numerical simulations, since, this allows us to perform real-time synthesis of stimuli using an auto-regressive time discretization. This is a significant departure from previous Fourier-based implementation of dynamic stimulation [START_REF] Sanz-Leon | Motion clouds: modelbased stimulus synthesis of natural-like random textures for the study of motion perception[END_REF][START_REF] Simoncini | More is not always better: adaptive gain control explains dissociation between perception and action[END_REF]. This is also important to simplify the application of MC inside a bayesian model of psychophysical experiments (see Section 3)The derivation of an equivalent sPDE model exploits a spectral formulation of MCs as Gaussian Random fields. The full proof along with the synthesis algorithm can be found in Section 2.4.

Psychophysical Study: Speed Discrimination

To exploit the useful features of our MC model and provide a generalizable proof of concept based on motion perception, we consider here the problem of judging the relative speed of moving dynamical textures and the impact of both average spatial frequency and average duration of temporal correlations.

Methods

The task was to discriminate the speed v ∈ R of MC stimuli moving with a horizontal central speed v 0 = (v, 0). We assign as independent experimental variable the most represented spatial frequency m Z , that we denote in the following z for easier reading. The other parameters are set to the following values

σ V = 1 t z 0 , θ 0 = π 2 , σ Θ = π 12 , d Z = 1.0 c/ • .
Note that σ V is thus dependent of the value of z 0 (that is computed from m Z and d Z , see Remark 2 and Section B.4 ) to ensure that t = 1 σ V z0 stays constant. This parameter t controls the temporal frequency bandwidth, as illustrated on the middle of Figure 2. We used a two alternative forced choice (2AFC) paradigm. In each trial a grey fixation screen with a small dark fixation spot was followed by two stimulus intervals of 250 ms each, separated by a grey 250 ms inter-stimulus interval. The first stimulus had parameters (v 1 , z 1 ) and the second had parameters (v 2 , z 2 ). At the end of the trial, a grey screen appeared asking the participant to report which one of the two intervals was perceived as moving faster by pressing one of two buttons, that is whether

v 1 > v 2 or v 2 > v 1 .
Given reference values (v , z ), for each trial, (v 1 , z 1 ) and (v 2 , z 2 ) are selected so that

v i = v , z i ∈ z + ∆ Z v j ∈ v + ∆ V , z j = z where ∆ V = {-2, -1, 0, 1, 2}, ∆ Z = {-0.
(v -v , z -z ) ∈ ∆ V × ∆ Z , the value φv ,z (v, z)
is the empirical probability (each averaged over the typically 40 trials) that a stimulus generated with parameters (v , z) is moving faster than a stimulus with parameters (v, z ).

To assess the validity of our model, we tested four different scenarios by considering all possible choices among z = 1.28 c/ • , v ∈ {5 • /s, 10 • /s}, t ∈ {0.1s, 0.2s}, which corresponds to combinations of low/high speeds and a pair of temporal frequency parameters. Stimuli were generated on a Mac running OS 10.6.8 and displayed on a 20" Viewsonic p227f monitor with resolution 1024 × 768 at 100 Hz. Routines were written using Matlab 7.10.0 and Psychtoolbox 3.0.9 controlled the stimulus display. Observers sat 57 cm from the screen in a dark room. Three observers with normal or corrected to normal vision took part in these experiments. They gave their informed consent and the experiments received ethical approval from the Aix-Marseille Ethics Committee in accordance with the declaration of Helsinki.

Bayesian modeling

To make full use of our MC paradigm in analyzing the obtained results, we follow the methodology of the Bayesian observer used for instance in [START_REF] Stocker | Noise characteristics and prior expectations in human visual speed perception[END_REF][START_REF] Sotiropoulos | Contrast dependency and prior expectations in human speed perception[END_REF][START_REF] Jogan | Signal integration in human visual speed perception[END_REF]. We assume the observer makes its decision using a Maximum A Posteriori (MAP) estimator

vz (m) = argmin v [-log(P M |V,Z (m|v, z)) -log(P V |Z (v|z))] (7)
computed from some internal representation m ∈ R of the observed stimulus. For simplicity, we assume that the observer estimates z from m without bias. To simplify the numerical analysis, we assume that the likelihood is Gaussian, with a variance independent of v. Furthermore, we assume that the prior is Laplacian as this gives a good description of the a priori statistics of speeds in natural images [START_REF] Dong | Maximizing causal information of natural scenes in motion[END_REF]:

P M |V,Z (m|v, z) = 1 √ 2πσ z e - |m-v| 2 2σ 2 z and P V |Z (v|z) ∝ e azv 1 [0,vmax] (v). ( 8
)
where v max > 0 is a cutoff speed ensuring that P V |Z is a well defined density even if a z > 0.

Both a z and σ z are unknown parameters of the model, and are obtained from the outcome of the experiments by a fitting process we now explain.

Likelihood and Prior Estimation

Following for instance [START_REF] Stocker | Noise characteristics and prior expectations in human visual speed perception[END_REF][START_REF] Sotiropoulos | Contrast dependency and prior expectations in human speed perception[END_REF][START_REF] Jogan | Signal integration in human visual speed perception[END_REF], the theoretical psychophysical curve obtained by a Bayesian decision model is

ϕ v ,z (v, z) def. = E(v z (M v,z ) > vz (M v ,z ))
where

M v,z ∼ N (v, σ 2 z ) is a Gaussian variable having the distribution P M |V,Z (•|v, z).
The following proposition shows that in our special case of Gaussian prior and Laplacian likelihood, it can be computed in closed form. Its proof follows closely the derivation of [12, Appendix A], and can be found in Section D.2. Proposition 3. In the special case of the estimator (7) with a parameterization (8), one has

ϕ v ,z (v, z) = ψ v -v -a z σ 2 z + a z σ 2 z σ 2 z + σ 2 z ( 9
)
where

ψ(t) = 1 √ 2π t
-∞ e -s 2 /2 ds is a sigmoid function.

One can fit the experimental psychometric function to compute the perceptual bias term µ z,z ∈ R and an uncertainty λ z,z such that

φv ,z (v, z) ≈ ψ v -v -µ z,z λ z,z . (10)
Remark 4. Note that in practice we perform a fit in a log-speed domain ie we consider ϕ ṽ ,z (ṽ, z) where ṽ = ln(1 + v/v 0 ) with v 0 = 0.3 • /s following [START_REF] Stocker | Noise characteristics and prior expectations in human visual speed perception[END_REF].

By comparing the theoretical and experimental psychopysical curves ( 9) and ( 10), one thus obtains the following expressions

σ 2 z = λ 2 z,z - 1 2 λ 2 z ,z and a z = a z σ 2 z σ 2 z - µ z,z σ 2 z .
The only remaining unknown is a z , that can be set as any negative number based on previous work on low speed priors or, alternatively estimated in future by performing a wiser fitting method.

Psychophysic Results

The main results are summarized in Figure 3 showing the parameters µ z,z in Figure 3(a) and the parameters σ z in Figure 3(b). Spatial frequency has a positive effect on perceived speed; speed is systematically perceived as faster as spatial frequency is increased, moreover this shift cannot simply Stimuli of lower frequency with respect to the reference (intersection of dotted horizontal and vertical lines gives the reference stimulus) are perceived as going slower, those with greater mean frequency are perceived as going relatively faster. This effect is observed under all conditions but is stronger at the highest speed and for subject 1. (b) The estimated σ z appear noisy but roughly constant as a function of z for each subject. Widths are generally higher for v = 5 (red) than v = 10 (blue) traces. The parameter t does not show a significant effect across the conditions tested. be explained to be the result of an increase in the likelihood width (Figure 3(b)) at the tested spatial frequency, as previously observed for contrast changes [START_REF] Stocker | Noise characteristics and prior expectations in human visual speed perception[END_REF][START_REF] Sotiropoulos | Contrast dependency and prior expectations in human speed perception[END_REF]. Therefore the positive effect could be explained by a negative effect in prior slopes a z as the spatial frequency increases. However, we do not have any explanation for the observed constant likelihood width as it is not consistent with the speed width of the stimuli σ V = 1 t z0 which is decreasing with spatial frequency.

Discussion

We exploited the principled and ecologically motivated parameterization of MC to ask about the effect of scene scaling on speed judgements. In the experimental task, MC stimuli, in which the spatial scale content was systematically varied (via frequency manipulations) around a central frequency of 1.28 c/ • were found to be perceived as slightly faster at higher frequencies slightly slower at lower frequencies. The effects were most prominent at the faster speed tested, of 10 • /s relative to those at 5 • /s. The fitted psychometic functions were compared to those predicted by a Bayesian model in which the likelihood or the observer's sensory representation was characterised by a simple Gaussian. Indeed, for this small data set intended as a proof of concept, the model was able to explain these systematic biases for spatial frequency as shifts in our a priori on speed during the perceptual judgements as the likelihood width are constant across tested frequencies but lower at the higher of the tested speeds. Thus having a larger measured bias given the case of the smaller likelihood width (faster speed) is consistent with a key role for the prior in the observed perceptual bias.

A larger data set, including more standard spatial frequencies and the use of more observers, is needed to disambiguate the models predicted prior function.

Conclusions

We have proposed and detailed a generative model for the estimation of the motion of images based on a formalization of small perturbations from the observer's point of view during parameterized rotations, zooms and translations. We connected these transformations to descriptions of ecologically motivated movements of both observers and the dynamic world. The fast synthesis of naturalistic textures optimized to probe motion perception was then demonstrated, through fast GPU implementations applying auto-regression techniques with much potential for future experimenta-tion. This extends previous work from [START_REF] Sanz-Leon | Motion clouds: modelbased stimulus synthesis of natural-like random textures for the study of motion perception[END_REF] by providing an axiomatic formulation. Finally, we used the stimuli in a psychophysical task and showed that these textures allow one to further understand the processes underlying speed estimation. By linking them directly to the standard Bayesian formalism, we show that the sensory representations of the stimulus (the likelihoods) in such models can be described directly from the generative MC model. In our case we showed this through the influence of spatial frequency on speed estimation. We have thus provided just one example of how the optimised motion stimulus and accompanying theoretical work might serve to improve our understanding of inference behind perception.

A Graphical Display of MC

We recall that MC are stationary Gaussian random field with a parameterized power spectrum having the form

∀ (ξ, τ ) ∈ R 3 , γ(ξ, τ ) = P Z (||ξ||) ||ξ|| 2 P Θ (∠ξ) L(P ||V -v0|| ) ||v 0 || cos(∠v 0 -∠ξ) - τ ||ξ|| . (11)
Similarly as was previously proposed in [START_REF] Sanz-Leon | Motion clouds: modelbased stimulus synthesis of natural-like random textures for the study of motion perception[END_REF]. We show in Figure 4 two examples of such stimuli for different spatial frequency bandwidths. In particular, by tuning this bandwidth we could dissociate their respective role in action and perception [START_REF] Sanz-Leon | Motion clouds: modelbased stimulus synthesis of natural-like random textures for the study of motion perception[END_REF][START_REF] Simoncini | More is not always better: adaptive gain control explains dissociation between perception and action[END_REF]. Extending the study of visual perception to other dimensions, such as orientation or speed bandwidths, should provide essential data to titrate their respective role in motion integration.

B sPDE Formulation and Numerics

The formulation of the MC gives an explicit parameterization [START_REF] Simoncini | More is not always better: adaptive gain control explains dissociation between perception and action[END_REF] of the covariance over the Fourier domain. We show here that it can be equivalently discretized by the solutions of a local PDE driven by a Gaussian noise. This formulation is important since we aim to deal with dynamic stimulation, which should be described by a causal equation which is local in time. This is indeed crucial to offer a fast simulation algorithm (see Section B.5) and to offer a coherent Bayesian inference framework, as shown in Section C.

B.1 Dynamic Textures as Solutions of sPDE

A MC I with speed v 0 can be obtained from a MC I 0 with zero speed by the constant speed time warping I(x, t)

def. = I 0 (x -v 0 t, t). ( 12
)
We now restrict our attention to I 0 .

We consider Gaussian random fields defined by a stochastic partial differential equation (sPDE) of the form

D(I 0 ) = ∂W ∂t (x) where D(I 0 ) def. = ∂ 2 I 0 ∂t 2 (x) + α ∂I 0 ∂t (x) + β I 0 (x) (13)
This equation should be satisfied for all (x, t), and we look for Gaussian fields that are stationary solutions of this equation. In this sPDE, the driving noise ∂W ∂t is white in time (i.e. corresponding to the temporal derivative of a Brownian motion in time) and has a 2-D covariance Σ W in space and is the spatial convolution operator. The parameters (α, β) are 2-D spatial filters that aim at enforcing an additional correlation in time of the model. Section B.2 explains how to choose (α, β, Σ W ) so A B Figure 4: Broadband vs. narrowband stimuli. We show in (A) and (B) instances of the same Motion Clouds with different frequency bandwidths σ Z , while all other parameters (such as z 0 ) are kept constant. The top column displays iso-surfaces of the spectral envelope by displaying enclosing volumes at different energy values with respect to the peak amplitude of the Fourier spectrum. The bottom column shows an isometric view of the faces of the movie cube. The first frame of the movie lies on the x-y plane, the x-t plane lies on the top face and motion direction is seen as diagonal lines on this face (vertical motion is similarly see in the y-t face). The Motion Cloud with the broadest bandwidth is thought to best represent natural stimuli, since, as those, it contains many frequency components. (A) σ Z = 0.25, (B) σ Z = 0.0625. that the stationary solutions of ( 13) have the power spectrum given in [START_REF] Simoncini | More is not always better: adaptive gain control explains dissociation between perception and action[END_REF] (in the case that v 0 = 0), i.e. are motion clouds. This sPDE formulation is important since we aim to deal with dynamic stimulation, which should be described by a causal equation which is local in time. This is crucial for numerical simulation (as explained in Section B.5) but also to simplify the application of MC inside a bayesian model of psychophysical experiments (see Section C).

While it is beyond the scope of this paper to study theoretically this equation, one can show existence and uniqueness results of stationary solutions for this class of sPDE under stability conditions on the filers (α, β) (see for instance [START_REF] Unser | An Introduction to Sparse Stochastic Processes[END_REF]) that we found numerically to be always satisfied in our simulations. Note also that one can show that in fact the stationary solutions to [START_REF] Stocker | Noise characteristics and prior expectations in human visual speed perception[END_REF] all share the same law. These solutions can be obtained by solving the sODE ( 14) forward for time t > t 0 with arbitrary boundary conditions at time t = t 0 , and letting t 0 → -∞. This is consistent with the numerical scheme detailed in Section B.5.

B.2 Equivalence Between Spectral and sPDE MC Formulations

The sPDE equation ( 13) corresponds to a set of independent stochastic ODEs over the spatial Fourier domain, which reads, for each frequency ξ,

∀ t ∈ R, ∂ 2 Î0 (ξ, t) ∂t 2 + α(ξ) ∂ Î0 (ξ, t) ∂t + β(ξ) Î0 (ξ, t) = σW (ξ) ŵ(ξ, t) (14)
where Î0 (ξ, t) denotes the Fourier transform with respect to the space variable x only. Here, σW (ξ) 2 is the spatial power spectrum of ∂W ∂t , which means that

Σ W (x, y) = c(x -y) where ĉ(ξ) = σ2 W (ξ). (15)
Here ŵ(ξ, t) ∼ N (0, 1) and w is a white noise in space and time. This formulation makes explicit that (α(ξ), β(ξ)) should be chosen in order to make the temporal covariance of the resulting process equal (or at least approximate) the temporal covariance appearing in [START_REF] Simoncini | More is not always better: adaptive gain control explains dissociation between perception and action[END_REF] in the motion-less setting (since we deal here with I 0 ), i.e. when v 0 = 0. This covariance should be localized around 0 and non-oscillating. It thus makes sense to constrain (α(ξ), β(ξ)) for the corresponding ODE ( 14) to be critically damped, which corresponds to imposing the following relationship

∀ ξ, α(ξ) = 2 ν(ξ)
and

β(ξ) = 1 ν2 (ξ)
for some relaxation step size ν(ξ). The model is thus solely parameterized by the noise variance σ W (ξ) and the characteristic time ν(ξ).

The following proposition shows that the sPDE model ( 13) and the motion cloud model ( 11) are identical for an appropriate choice of function P ||V -v0|| .

Proposition 4. When considering

∀ r > 0, P ||V -v0|| (r) = L -1 (h)(r/σ V ) where h(u) = (1 + u 2 ) -2 (16)
where L is defined in [START_REF] Simoncini | More is not always better: adaptive gain control explains dissociation between perception and action[END_REF], equation (14) admits a solution I which is a stationary Gaussian field with power spectrum (11) when setting

σ2 W (ξ) = 1 ν(ξ)||ξ|| 2 P Z (||ξ||)P Θ (∠ξ), and ν(ξ) = 1 σ V ||ξ|| . (17)
Proof. For this proof, we denote I MC the motion cloud defined by [START_REF] Simoncini | More is not always better: adaptive gain control explains dissociation between perception and action[END_REF], and I a stationary solution of the sPDE defined by [START_REF] Stocker | Noise characteristics and prior expectations in human visual speed perception[END_REF]. We aim at showing that under the specification [START_REF] Wei | Efficient coding provides a direct link between prior and likelihood in perceptual bayesian inference[END_REF], they have the same covariance. This is equivalent to show that I MC 0 (x, t) = I MC (x + ct, t) has the same covariance as I 0 . One shows that for any fixed ξ, equation ( 14) admits a unique (in law) stationary solution Î0 (ξ, •) which is a stationary Gaussian process of zero mean and with a covariance which is σ2 W (ξ)r r where r is the impulse response (i.e. taking formally a = δ) of the ODE r + 2r /u + r /u 2 = a where we denoted u = ν(ξ). This impulse response is easily shown to be r(t) = te -t/u 1 R + (t). The covariance of Î0 (ξ, •) is thus, after some computation, equal to σ2

W (ξ)r r = σ2 W (ξ)h(•/u) where h(t) ∝ (1 + |t|)e -|t| .
Taking the Fourier transform of this equality, the power spectrum γ0 of I 0 thus reads

γ0 (ξ, τ ) = σ2 W (ξ)ν(ξ)h(ν(ξ)τ ) where h(u) = 1 (1 + u 2 ) 2
and where it should be noted that this h function is the same as the one introduced in (16). The covariance γ MC of I MC and γ MC 0 of I MC 0 are related by the relation

γMC 0 (ξ, τ ) = γMC (ξ, τ -ξ, v 0 ) = 1 ||ξ|| 2 P Z (||ξ||)P Θ (∠ξ) h - τ σ V ||ξ|| .
where we used the expression [START_REF] Simoncini | More is not always better: adaptive gain control explains dissociation between perception and action[END_REF] for γMC and the value of L(P ||V -v0|| ) given by [START_REF] Wei | State of the art in example-based texture synthesis[END_REF]. Condition [START_REF] Wei | Efficient coding provides a direct link between prior and likelihood in perceptual bayesian inference[END_REF] guarantees that expression (B.2) and (B.2) coincide, and thus γ0 = γMC 0 .

B.3 Expression for P ||V -v0||

Equation [START_REF] Wei | State of the art in example-based texture synthesis[END_REF] states that in order to obtain a perfect equivalence between the MC defined by [START_REF] Simoncini | More is not always better: adaptive gain control explains dissociation between perception and action[END_REF] and by [START_REF] Stocker | Noise characteristics and prior expectations in human visual speed perception[END_REF], the function has L -1 (h) to be well-defined. It means we need to compute the inverse of the transform of the linear operator

L ∀u ∈ R, L(f )(u) = 2 π/2 0 f (-u/ cos(ϕ))dϕ.
to the function h. The following proposition gives a closed-form expression for this function, and shows in particular that it is a function in L 1 (R), i.e. it has a finite integral, which can be normalized to unity to define a density distribution. Figure 5 shows a graphical display. Proposition 5. One has

L -1 (h)(u) = 2 -u 2 π(1 + u 2 ) 2 - u 2 (u 2 + 4)(log(u) -log( √ u 2 + 1 + 1)) π(u 2 + 1) 5/2
.

In particular, one has

L -1 (h)(0) = 2 π and L -1 (h)(u) ∼ 1 2πu 3 when u → +∞.
Proof. The variable substitution x = cos(ϕ) allows to rewrite (B.3) as

∀u ∈ R, L(h)(u) = 2 1 0 h - u x x √ 1 -x 2 dx x .
In such a form, we recognize a Mellin convolution which could be inverted by the use of Mellin convolution table.

P Z (z) ∝ z 0 z e - ln ( z z 0 ) 2 2 ln ( 1+σ 2 Z ) .
The parameters (z 0 , σ Z ) are convenient to write the distribution but they do not reflect remarkable values of a log-normal random variable. Instead, we prefer to fix directly the mode m Z = argmax z P Z (z) and standard deviation d Z = R+ z 2 P Z (z)dz. These couples of variable are linked by the following equations,

m Z = z 0 1 + σ 2 Z and d Z = z 0 σ 2 Z (1 + σ 2 Z ).
Such formula could be inverted by finding the unique positive root of

P (x) = x 2 (1 + x 2 ) 2 - d Z m Z because P (σ Z ) = 0 and finally set z 0 = m Z (1 + σ 2 Z ).
Parametrization by mode and octave bandwidth Another choice would be to parametrize P Z by its mode m Z and octave bandwidth B Z which is defined by

B Z = ln z+ z- ln (2)
where (z -, z + are the half-power cutoff frequencies ie verifies P Z (z -) = P Z (z

+ ) = P Z (m Z ) 2
. This last condition comes down to study the roots of the following polynomial

Q(X) = X 2 + 2 ln(1 + σ 2 Z )X -2 ln(2) ln(1 + σ 2 Z ) + 1 2 ln(1 + σ 2 Z ) 2
where X = ln z z0 . It follows that [START_REF] Dong | Maximizing causal information of natural scenes in motion[END_REF] .

B Z = 8 ln(1 + σ 2 Z ) ln
Conversely,

σ Z = exp ln(2) 8 B 2 Z -1.

B.5 AR(2) Discretization of the sPDE

Most previous works (such as [START_REF] Galerne | Micro-Texture synthesis by phase randomization[END_REF] for static and [START_REF] Sanz-Leon | Motion clouds: modelbased stimulus synthesis of natural-like random textures for the study of motion perception[END_REF][START_REF] Simoncini | More is not always better: adaptive gain control explains dissociation between perception and action[END_REF] for dynamic textures) have used global Fourier-based approach that makes use of the explicit power spectrum expression 11. The main drawbacks of such an approach are: (i) it introduces an artificial periodicity in time and thus can only be used to synthesize a finite number of frames; (ii) the discrete computational grid may introduce artifacts, in particular when one of the bandwidths is of the order of the discretization step; (iii) these frames must be synthesized at once, before the stimulation, which prevents real-time synthesis.

To address these issues, we follow the previous works of [START_REF] Doretto | Dynamic textures[END_REF][START_REF] Xia | Synthesizing and mixing stationary gaussian texture models[END_REF] and make use of an auto-regressive (AR) discretization of the sPDE [START_REF] Stocker | Noise characteristics and prior expectations in human visual speed perception[END_REF]. In contrast with these previous works, we use a second order AR(2) regression (in place of a first order AR(1) model). Using higher order recursions is crucial to be consistent with the continuous formulation [START_REF] Stocker | Noise characteristics and prior expectations in human visual speed perception[END_REF]. Indeed, numerical simulations show that AR(1) iterations lead to unacceptable temporal artifacts: in particular, the time correlation of AR(1) random fields typically decays too fast in time.

The discretization computes a (possibly infinite) discrete set of 2-D frames (I ( ) 0 ) 0 separated by a time step ∆, and we approach at time t = ∆ the derivatives as

∂I 0 (•, t) ∂t ≈ ∆ -1 (I ( ) 0 -I ( -1) 0
) and

∂ 2 I 0 (•, t) ∂t 2 ≈ ∆ -2 (I ( +1) 0 + I ( -1) 0 -2I ( ) 0 ),
which leads to the following explicit recursion

∀ 0 , I (
+1) 0 = (2δ -∆α -∆ 2 β) I ( ) 0 + (-δ + ∆α) I ( -1) 0 + ∆ 2 W ( ) , (18)
where δ is the 2-D Dirac distribution and where (W ( ) ) are i.i.d. 2-D Gaussian field with distribution N (0, Σ W ), and (I

( 0-1) 0 , I ( 0 -1) 0
) can be arbitrary initialized.

One can show that when 0 → -∞ (to allow for a long enough "warmup" phase to reach approximate time-stationarity) and ∆ → 0, then I ∆ 0 defined by interpolating I ∆ 0 (•, ∆ ) = I ( ) converges (in the sense of finite dimensional distributions) toward a solution I 0 of the sPDE [START_REF] Stocker | Noise characteristics and prior expectations in human visual speed perception[END_REF]. We refer to [START_REF] Unser | A unified formulation of gaussian versus sparse stochastic processes -part II: Discrete-Domain theory[END_REF] for a similar result in the 1-D case (stochastic ODE). We implemented the recursion (18) by computing the 2-D convolutions with FFT's on a GPU, which allows us to generate high resolution videos in real time, without the need to explicitly store the synthesized video.

C Experimental Likelihood vs. the MC Model

In our paper, we propose to directly fit the likelihood P M |V,Z (m|v, z) from the experimental psychophysical curve. While this makes sense from a data-analysis point of view, this required strong modeling hypothesis, in particular, that the likelihood is Gaussian with a variance σ 2 z independent of the parameter v to be estimated by the observer.

In this section, we direct a likelihood model directly from the stimuli, by making another (of course questionnable) hypothesis, that the observer uses a standard motion estimation process, based on the motion energy concept [START_REF] Adelson | Spatiotemporal energy models for the perception of motion[END_REF], that we adapt here to the MC distribution. In this setting, this corresponds to using a MLE estimator, and making use of the sPDE formulation of MC.

C.1 MLE Speed Estimator

We first show how to compute this MLE estimator. To be able to achieve this, the following proposition derive the sPDE satisfied by a motion cloud with a non-zero speed. Proposition 6. A MC I with speed v 0 can be defined as a stationary solution of the sPDE

D(I) + G(I), v 0 + H(I)v 0 , v 0 = ∂W ∂t ( 19
)
where D is defined in (13), ∂ 2 x I is the hessian of I (second order spatial derivative), where

G(I)

def.

= α ∇ x I + 2∂ t ∇ x I and H(I)

def.

= (∂ 2

x I) and (α, β, Σ W ) are defined in Proposition 4.

Proof. This follows by derivating in time the warping equation [START_REF] Sotiropoulos | Contrast dependency and prior expectations in human speed perception[END_REF], denoting y

def. = x + v 0 t ∂ t I 0 (x, t) = ∂ t I(y, t) + ∇I(y, t), v 0 , ∂ 2 t I 0 (x, t) = ∂ 2 t I(y, t) + 2 ∂ t ∇I(y, t), v 0 + ∂ 2 x I(y, t)v 0 , v 0
and plugging this into (13) after remarking that the distribution of ∂W ∂t (x, t) is the same as the distribution of ∂W ∂t (xv 0 t, t).

Equation ( 19) is useful from a Bayesian modeling perspective, because, informally, it can be interpreted as the fact that the Gaussian distribution of MC as the following appealing form, for any function

I : R 2 × R → R P I (I) = 1 Z I exp(-||D(I) + G(I), v 0 + H(I)v 0 , v 0 || 2 Σ -1 W )
where Z I is a normalization constant which is independent of v 0 and

||I|| 2 Σ -1 W def. = I, I Σ -1 W and I 1 , I 2 Σ -1 W def. = Î1 (ξ, t) Î2 (ξ, t) * σ2 W (ξ) dξdt
where σW is defined in [START_REF] Unser | A unified formulation of gaussian versus sparse stochastic processes -part II: Discrete-Domain theory[END_REF].

(I) + v G(I), (1, 0) + v 2 H(I)(1, 0), (1, 0) || 2 Σ -1 W ( 20
)
where we used the fact that the normalizing constant Z I is independent of v 0 . Expanding the squares shows that [START_REF] Xia | Synthesizing and mixing stationary gaussian texture models[END_REF] is the optimization of a fourth order polynomial, whose solution can be computed in closed form as one of the roots of the derivative of this polynomial, which is hence a third order polynomial.

C.2 MLE Modeling of the Likelihood

In our paper, following several previous works such as [START_REF] Stocker | Noise characteristics and prior expectations in human visual speed perception[END_REF][START_REF] Sotiropoulos | Contrast dependency and prior expectations in human speed perception[END_REF], we assumed the existence of an internal representation parameter m, which was assumed to be a scalar, with a Gaussian distribution conditioned on (v, z). We explore here the possibility that this internal representation could be directly obtained from the stimuli by the usage by the observer an "optimal" speed detector (an MLE estimate).

Denoting I v,z a MC, which is a random Gaussian field of power spectrum [START_REF] Simoncini | More is not always better: adaptive gain control explains dissociation between perception and action[END_REF], with central speeds v 0 = (v, 0) and central spacial frequency z (the other parameters being fixed as explained in the experimental section of the paper), this means that we consider the internal representation as being the following scalar random variable

M v,z
As detailed in [START_REF] Xia | Synthesizing and mixing stationary gaussian texture models[END_REF] it can be efficiently computed numerically.

As shown in Figure 6(a), we observed that M v,z is well approximated by a Gaussian random variable. Its mean is nearly constant and very close to v, and Figure 6(b) shows the evolution of its variance. Our main finding is that this optimal estimation model (using an MLE) is not consistent with the experimental finding because the estimated standard deviations of observers don't show a decreasing behavior as in Figure 6(b). We recall the expression of the covariance

∀ (x, t) ∈ R 3 , γ(x, t) = R 2
c g (ϕ a (xνt))P V (ν)P A (a)dνda

We denote (θ, ϕ, z, r) ∈ Γ = [-π, π) 2 × R 2 + the set of parameters. According to Proposition 1, the covariance of I is γ defined by (22). Denoting h(x, t) = c g (zR θ (xνt)), one has, in the sense of distributions (taking the Fourier transform with respect to (x, t)) ĥ(ξ, τ ) = z -2 ĝ(z -1 R θ (ξ)) 2 δ Q (ν) where Q = ν ∈ R 2 ; τ + ξ, ν = 0 .

Taking the Fourier transform of (22) and using this computation, one has γ(ξ, τ ) = Γ 1 z 2 |ĝ z -1 R θ (ξ) | 2 δ Q (v 0 + r(cos(ϕ), sin(ϕ)))P Θ (θ)P Z (z)P ||V -v0|| (r) dθ dz dr dϕ.

In the special case of g being a grating, i.e.

Figure 1 :

 1 Figure 1: Parameterization of the class of Motion Clouds stimuli. The illustration relates the parametric changes in MC with real world (top row) and observer (second row) movements. (A) Orientation changes resulting in scene rotation are parameterized through θ as shown in the bottom row where a horizontal a and obliquely oriented b MC are compared. (B) Zoom movements, either from scene looming or observer movements in depth, are characterised by scale changes reflected by a scale or frequency term z shown for a larger or closer object b compared to more distant a. (C) Translational movements in the scene characterised by V using the same formulation for static (a) slow (b) and fast moving MC, with the variability in these speeds quantified by σ V . (ξ and τ ) in the third row are the spatial and temporal frequency scale parameters. The development of this formulation is detailed in the text.

Figure 2 :

 2 Figure 2: Graphical representation of the covariance γ (left) -note the cone-like shape of the envelopes-and an example of synthesized dynamics for narrow-band and broad-band Motion Clouds (right).

1 v

 1 * = 5, t * = 100 v * = 5, t * = 200 v * = 10, t * = 100 v * = 10, t *

Figure 3 :

 3 Figure 3: 2AFC speed discrimination results. (a) Task generates psychometric functions whichshow shifts in the point of subjective equality for the range of test z. Stimuli of lower frequency with respect to the reference (intersection of dotted horizontal and vertical lines gives the reference stimulus) are perceived as going slower, those with greater mean frequency are perceived as going relatively faster. This effect is observed under all conditions but is stronger at the highest speed and for subject 1. (b) The estimated σ z appear noisy but roughly constant as a function of z for each subject. Widths are generally higher for v = 5 (red) than v = 10 (blue) traces. The parameter t does not show a significant effect across the conditions tested. be explained to be the result of an increase in the likelihood width (Figure3(b)) at the tested spatial frequency, as previously observed for contrast changes[START_REF] Stocker | Noise characteristics and prior expectations in human visual speed perception[END_REF][START_REF] Sotiropoulos | Contrast dependency and prior expectations in human speed perception[END_REF]. Therefore the positive effect could be explained by a negative effect in prior slopes a z as the spatial frequency increases. However, we do not have any explanation for the observed constant likelihood width as it is not consistent with the speed width of the stimuli σ V = 1 t z0 which is decreasing with spatial frequency.

Figure 5 :

 5 Figure 5: Functions h and L -1 (h).

  This convenient formulation allows to re-write the MLE estimator of the horizontal speed v parameter of a MC as vMLE (I) def. = argmax v P I (I) where v 0 = (v, 0) ∈ R 2 used to analyse psychophysical experiments as vMLE (I) = argmin v ||D

P

  M |V,Z (I|v, z),

Figure 6 :and a z = a z σ 2 z σ 2 z- µ z,z σ 2 z 2 z σ 2 z

 62222 Figure 6: Estimates of M v,z defined by (21) and its standard deviation as a function of z.

10 Figure 7 :

 107 Figure 7: Example of decreasing a z . The unknown a z choosen so that z a 2 z is minimum. D Proofs D.1 Proof of Proposition 2

  |ĝ| 2 = δ ξ0 , one has in the sense of distributionsz -2 |ĝ z -1 R θ (ξ) | 2 = δ B (θ, z) where B = (θ, z) ; z -1 R θ (ξ) = ξ 0 . Observing that δ Q (ν)δ B (θ, z) = δ C (θ, z, r) where C = (θ, z, r) ; z = ||ξ||, θ = ∠ξ, r = -τ ||ξ|| cos(∠ξϕ) -||v 0 || cos(∠ξ -∠v 0 ) cos(∠ξϕ)one obtains the desired formula.D.2 Proof of Proposition 3One has the closed form expression for the MAP estimator vz (m) = ma z σ 2 z , and hence, denoting N (µ, σ 2 ) the Gaussian distribution of mean µ and variance σ 2 ,vz (M v,z ) ∼ N (va z σ 2 z , σ 2 z )where ∼ means equality of distributions. One thus hasvz (M v,z )vz (M v ,z ) ∼ N (vva z σ 2 z + a z σ 2 z , σ 2 z + σ 2 z), which leads to the results by taking expectation.

  Ten repetitions of each of the 25 possible combinations of these parameters are made per block of 250 trials and at least four such blocks were collected per condition tested. The outcome of these experiments are summarized by psychometric curves φv ,z , where for all

48, -0.21, 0, 0.32, 0.85}, where (i, j) = (1, 2) or (i, j) = (2, 1) (i.e. the ordering is randomized across trials), and where z values are expressed in cycles per degree (c/ • ) and v values in • /s.

Acknowledgements

We thank Guillaume Masson for useful discussions during the development of the experiments. We also thank Manon Bouyé and Élise Amfreville for proofreading. LUP was supported by EC FP7-269921, "BrainScaleS". The work of JV and GP was supported by the European Research Council (ERC project SIGMA-Vision). AIM and LUP were supported by SPEED ANR-13-SHS2-0006.


Éric Sopena
email: eric.sopena@labri.fr.

A NEW SUBTRACTION DIVISION GAME

Keywords: Combinatorial games, Subtraction games, Subtraction division games, Sprague-Grundy sequence, Aperiodicity Mathematics Subject Classification (MSC 2010): 91A46

Given two finite sets of integers S ⊆ N \ {0} and D ⊆ N \ {0, 1}, the impartial combinatorial game i-Mark(S, D) is played on a heap of tokens. From a heap of n tokens, each player can move either to a heap of ns tokens for some s ∈ S, or to a heap of n/d tokens for some d ∈ D if d divides n. Such games can be considered as an integral variant of Mark-type games, introduced by Elwyn Berlekamp and Joe Buhler and studied by Aviezri Fraenkel and Alan Guo, for which it is allowed to move from a heap of n tokens to a heap of ⌊n/d⌋ tokens for any d ∈ D.

Under normal convention, it is observed that the Sprague-Grundy sequence of the game i-Mark(S, D) is aperiodic for any sets S and D. However, we prove that, in many cases, this sequence is almost periodic and that the set of winning positions is periodic. Moreover, in all these cases, the Sprague-Grundy value of a heap of n tokens can be computed in time O(log n).

We also prove that, under misère convention, the outcome sequence of these games is purely periodic.

Introduction

The impartial combinatorial game Mark, due to Mark Krusemeyer according to Elwyn Berlekamp and Joe Buhler [START_REF] Berlekamp | Puzzles Column[END_REF], is played on a heap of tokens. On their turn, each player can move from a heap of n tokens, n ≥ 1, either to a heap of n -1 tokens or to a heap of ⌊n/2⌋ tokens. Under normal convention, the first player unable to move (when the heap is empty) loses the game. This game is a particular case of a more general family of games, that we call subtraction division games following [START_REF] Kupin | Subtraction division games[END_REF], defined as follows 1 . Let us denote by [a, b], a ≤ b, the set of integers {i | a ≤ i ≤ b}, by N ≥i , i ∈ N, the set N \ [0, i -1] and let S ⊆ N ≥1 and D ⊆ N ≥2 be two finite sets of integers. The subtraction division game SD(S, D) is played on a heap of n tokens, n ≥ 0. From a heap of n tokens, each player can move either to a heap of ns tokens for some s ∈ S, or to a heap of ⌊n/d⌋ tokens for some d ∈ D. The Mark game is therefore the game SD({1}, {2}).

In this paper, we study a variant of such subtraction division games, that we propose to name i-Mark(S, D) for integral Mark, obtained by restricting divisiontype moves, allowing a move from a heap of n tokens to a heap of ⌊n/d⌋ tokens, d ∈ D, only when d divides n, so that ⌊n/d⌋ = n/d.

1.1. Combinatorial Game Theory: basic notions and terminology. We first briefly recall the main notions of Combinatorial Game Theory that we will need in this paper. More details can be found on any of the reference books [START_REF] Michael | Lessons in Play: An Introduction to Combinatorial Game Theory[END_REF], [START_REF] Berlekamp | Winning Ways for your Mathematical Plays[END_REF], [START_REF] Conway | On Numbers and Games[END_REF] or [START_REF] Siegel | Combinatorial Game Theory[END_REF].

Let us call a heap-game any impartial combinatorial game played on a heap of tokens. We denote by n a heap of n tokens, or n Game if we want to specify that the considered game is Game. Those heaps n for which the Next player to move has a winning strategy are N-positions, whereas those for which the Previous player has a winning strategy are P-positions. We denote by N the set of P-positions and by P the set of P-positions. Note that a position n is in P if and only if every move from n leads to a position in N , whereas n is in N if and only if there exists at least one move from n to a position in P. We also say that the outcome of a position n is N if n ∈ N and P otherwise. It is not difficult to prove that any position of an impartial combinatorial game is either an N-position or a P-position, which implies that the two sets N and P are complementary -that is, N ∩ P = ∅ and N ∪ P = N.

Heap-games can be played on any finite number of heaps, by means of sums of games. In that case, a player move consists in first selecting one of the heaps and then making a legal move on that heap. Knowing whether each heap is an N-or a P-position is not sufficient to determine whether the whole game is an Nor a P-position. Under normal convention, we use the Sprague-Grundy function which assigns to every position G of an impartial game its g-value g(G) (sometimes called nim-value or nimber), defined as the unique positive integer k such that G is equivalent to the Nim position k Nim . (Equivalence here means that the sum G + k Nim is a P-position.) Therefore, a position is in P if and only if its g-value is 0. The g-value of any position G of an impartial game can be inductively computed using the mex function, defined by mex(S) = min(N \ S) for every finite set S ⊆ N. We then have

g(G) = mex(opt(G)),
where opt(G) denotes the set of options of G -that is, the set of positions that can be reached from G by making a legal move. Note here that if a position has k options then its g-value is at most k.

Let ⊕ denote the nim-sum function, defined by

n 1 ⊕ n 2 = R -1 (R(n 1 ) XOR R(n 2 ))
for any two positive integers n 1 and n 2 , where R denotes the function that associates with each integer its binary representation. For a position G = G 1 + . . . + G p of a sum of games, the g-value of G is then given by

g(G) = g(G 1 ) ⊕ . . . ⊕ g(G p ).
Computing the g-value of a game recursively using the mex function can be exponential in the 'size' of G and thus inefficient. For a heap-game Game we define the Sprague-Grundy sequence (sometimes called the nim-sequence) of Game as the sequence

G(Game) = (g(1 Game ), g(2 Game ), . . .).
Knowing this sequence clearly allows to compute the g-value of any position of Game on a finite number of heaps. This can be efficient whenever the Sprague-Grundy sequence has "nice properties", in particular if it is periodic. We say that an integer sequence (a i ) i∈N is periodic, with preperiod of length q ≥ 0 and period of length p ≥ 1, if for every i ≥ q, a i = a i+p . In such a case, any value a i of the sequence is determined by the value of a i mod p, which can be computed in time O(log a i ) for a fixed p. This is namely the case for all subtraction games -that is, games of the form SD(S, ∅) -whenever the subtraction set S is finite [START_REF] Berlekamp | Winning Ways for your Mathematical Plays[END_REF].

Similarly, we say that a set of integers S ⊆ N is periodic if there exist q, p, with q ≥ 0 and p ≥ 1, such that for every i ≥ q, i ∈ S if and only if i + p ∈ S. Note that since the sets N and P of any heap-game are complementary, either both these sets are periodic or none of them is periodic.

We define the outcome sequence of a game Game as the sequence (o i ) i∈N given by o i = N if i is an N-position for Game and o i = P otherwise. We will say that such an outcome sequence is periodic whenever the sets N and P are periodic.

1.2. The game Mark. In [START_REF] Aviezri | Aperiodic subtraction games[END_REF][START_REF] Aviezri | The vile, dopey, evil and odious game players[END_REF], Aviezri Fraenkel developped a study of the Mark game SD({1}, {2}) and gave a characterization of the corresponding sets N and P. Although aperiodic, these two sets reveals a nice structure: a Mark position n is in N if and only if the binary representation R(n) of n has an even number of trailing 0's2 . This allows to compute the outcome of any Mark position n in time O(log n). It is also proved that the Sprague-Grundy sequence G(Mark) has the following property (note that since any Mark position has at most two options, g(n) ≤ 2 for any Mark position n):

• g(n) = 0 is and only if R(n) has an odd number of trailing 0's, • g(n) = 1 if and only if R(n) has an even number of trailing 0's and an odd number of 1's, • g(n) = 2 if and only if R(n) has an even number of trailing 0's and an even number of 1's.

Again, this allows to compute the g-value g(n) of any Mark position n in time O(log n).

Aviezri Fraenkel also studied the Mark game under misère convention (the first player unable to move wins the game), the game UpMark (allowing moves from n to ⌈n/2⌉ instead of ⌊n/2⌋) and introduced the general game Mark-t = SD([1, t -1], {t}), for any given t ≥ 1, whose sets N and P again are aperiodic for every t.

This latter game has been studied by Alan Guo in [START_REF] Guo | Winning strategies for aperiodic subtraction games[END_REF]. He proved that the gvalue of any Mark-t position can be computed in quadratic time. More precisely, he proved that g(n) = k, k ≤ t -2, if and only if R t (n) has an odd number of trailing k's, where R t (n) denotes the representation of n written in base t, and that deciding whether g(n) = t -1 or g(n) = t can be done in quadratic time.

1.3. The game i -Mark: an integral subtraction division game. We study in this paper an integral variant of Mark-type games. For any two sets S ⊆ N ≥1 and D ⊆ N ≥2 , the allowed moves in the game i-Mark(S, D) are those leading from a position n to any of the positions ns, with s ∈ S, or n/d, with d ∈ D and d|n.

As for the game Mark, the Sprague-Grundy sequence of the game i-Mark(S, D) is aperiodic whenever the set D is non-empty: Theorem 1. For every finite set S ⊆ N ≥1 and every non-empty finite set D ⊆ N ≥2 , the Sprague-Grundy sequence of the game i-Mark(S, D) is aperiodic.

Proof. Assume to the contrary that G(i-Mark(S, D)) is periodic, with preperiod of length q and period of length p, and let d ∈ D. Let n be any position with n = kp ≥ q for some k ≥ 1. Since d ∈ D, there is a move from dn to n and, therefore g(dn) = g(n). This contradicts our assumption since dnn = (d -1)n = (d -1)kp.

However, and in contrast to the game Mark, we will prove that the outcome sequence of such integral games is periodic in many cases. Moreover, the Sprague-Grundy sequence appears to be "almost periodic" in most of these cases, in the following sense: Definition 1. An integer sequence (a i ) i∈N is ℓ-almost periodic for some ℓ ≥ 0, with preperiod of length q ≥ 0, period of length p > ℓ and exception set E = {j 1 , . . . , j ℓ } ⊆ [0, p -1] if, for every i ≥ q with (i mod p) / ∈ E, a i = a i+p .

Intuitively speaking, a sequence is ℓ-almost periodic if it is "periodic, except on ℓ columns of the period". A 0-almost periodic sequence is thus a periodic sequence.

1.4. Organisation of the paper. In the next section, we provide more details on the results proposed by Aviezri Fraenkel in [START_REF] Aviezri | Aperiodic subtraction games[END_REF] on the game Mark and consider its integral version i-Mark({1}, {2}) as an introductory example.

We then study games of the form i-Mark([1, t -1], {d}), with t, d ≥ 2, in Section 3, and of the form i-Mark({a, 2a}, {2}), with a ≥ 2, in Section 4.

We finally consider the misère version of the game i-Mark in Section 5 and propose some open questions in Section 6.

A first sample game: i-Mark({1}, {2})

We consider in this section the simple game i-Mark({1}, {2}) since it corresponds to our variant of the original game Mark. We first briefly recall some results presented by Aviezri Fraenkel in [START_REF] Aviezri | Aperiodic subtraction games[END_REF].

2.1. The game Mark. Let A = (a n ) n≥1 and B = (b n ) n≥0 be the two sequences recursively defined by:

a n = mex{a i , b i | 0 ≤ i < n}, b 0 = 0 and b n = 2a n , n ≥ 1.
These two sequences are clearly complementary and respectively correspond to the sequences A003159 and A036554 of the "On-Line Encyclopedia of Integer Sequences" of Neil Sloane [START_REF] Neil | The On-Line Encyclopedia of Integer Sequences[END_REF].

A position n is then an N-position for Mark if and only if n ∈ A, and thus a P-position for Mark if and only if n ∈ B. The first elements of these two sequences are given in the following table : n 0 1 2 3 4 5 6 7 8 9 Moreover, it can be observed that both these sets are aperiodic and, therefore, the Sprague-Grundy sequence G(Mark) is aperiodic. The first elements of this sequence are the following: n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

g(n) 0 1 0 2 1 2 0 1 0 2 0 1 2 1 0 2 1 2.2.
The game i-Mark({1}, {2}). Let us now consider the integral version of the game Mark, denoted i-Mark({1}, {2}). By Theorem 1, we know that the Sprague-Grundy sequence of the game i-Mark({1}, {2}) is aperiodic. We first prove that its outcome sequence is periodic.

Theorem 2. The outcome sequence of the game i-Mark({1}, {2}) is periodic, with preperiod of length 4 and period of length 2. More precisely, we have

(i) N = {1, 3} ∪ {2k | k ≥ 2}, (ii) P = {0, 2} ∪ {2k + 1 | k ≥ 2}.
Proof. Clearly, 0 ∈ P. Since opt(1) = {0}, opt(2) = {1}, opt(3) = {2} and opt(4) = {2, 3}, we get 1, 3, 4 ∈ N and 2 ∈ P. The result then follows by induction since (i) opt(n) = {n -1} for every odd n, so that n ∈ P, and (ii) for every P-position n, n ∈ opt(n + 1) and thus n + 1 is an N-position.

The first elements of the Sprague-Grundy sequence G(i-Mark({1}, {2})) are the following: n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 g(n) 0 1 0 1 2 0 2 0 1 0 1 0 1 0 1 0 n 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 g(n) 2 0 1 0 2 0 1 0 2 0 1 0 2 0 1 0 By Theorem 1, we know that this sequence is aperiodic. By Theorem 2, we know that g(n) = 0 for every odd n, n ≥ 5, and g(n) ∈ {1, 2} for every even n, n ≥ 4. Hence, this sequence is 1-almost periodic. We now prove that deciding whether g(n) = 2 for any position n is easy.

For every integer n > 0, we denote by R 1 (n) the binary number obtained from the binary representation R(n) of n by deleting all the trailing 0's. Then we have: Theorem 3. Let n be any position of the game i-Mark({1}, {2}). Then g(n) = 2 if and only if n is even and either:

(i) R 1 (n) = 11 2 and
R(n) has an odd number of trailing 0's, or (ii) R 1 (n) = 11 2 and R(n) has an even number of trailing 0's.

Proof. The theorem clearly holds for n ≤ 6. Suppose now that the theorem holds up to position n -1, n ≥ 7, and consider the position n.

If n is odd, we know by Theorem 2 that n ∈ P and thus g(n) = 0. Assume thus that n is even, so that opt(n) = {n/2, n -1}. Since g(n -1) = 0, we get g(n) = 2 if and only if g(n/2) = 1 and the result directly follows from the induction hypothesis.

Let N 2 denote the set of integers n such that g(n) = 2. The set N 2 is as follows: Note that from Theorems 2 and 3, we get that computing the g-value of any position n for the game i-Mark({1}, {2}) can be done in time O(log n).

N 2 = {4,

The game i-Mark([1, t -1], {d})

We consider in this section the game i-Mark([1, t -1], {d}), with t ≥ 2 and d ≥ 2. If t = d = 2, we get the game i-Mark({1}, {2}) considered in the previous section. More generally, if t = d, we get the integral version of the game Mark-t introduced by Aviezri Fraenkel in [START_REF] Aviezri | The vile, dopey, evil and odious game players[END_REF] and studied by Alan Guo in [START_REF] Guo | Winning strategies for aperiodic subtraction games[END_REF].

We will prove that for every t ≥ 2 and d ≥ 2, d ≡ 1 (mod t), the outcome sequence of the game i-Mark([1, t -1], {d}) is periodic, while its Sprague-Grundy sequence is 1-almost periodic.

We first consider the outcome sequence of the game i-Mark([1, t -1], {d}) when d ≡ 1 (mod t), and prove the following: Theorem 4. For every integers t ≥ 2 and d ≥ 2, d ≡ 1 (mod t), the outcome sequence of the game i-Mark([1, t -1], {d}) is periodic, with preperiod of length d(t -1) + 2 and period of length t. More precisely, the set P of P-positions is given by

P = {qt | 0 ≤ q < d} ∪ {qt + 1 | q ≥ d}.
Proof. We clearly have 0 ∈ P, which implies {1, . . . , t -1} ⊆ N since 0 is an option of all these positions. Suppose now that the theorem holds up to position n -1, n ≥ t, and consider the position n. Let n = qt + r, with q > 0 and r ∈ [0, t -1].

If q < d and r = 0 then qt ∈ opt(n) and thus, since qt ∈ P by induction hypothesis, n ∈ N .

If q < d and r = 0, opt(n) = {(qtt + 1, . . . , qt -1} and thus, since all these options are in N by induction hypothesis, n ∈ P.

If q = d and r = 0 -that is, n = dt -then, since t ∈ opt(n) and t ∈ P by induction hypothesis, n ∈ N .

If q > d and r = 0 then, since (q -1)t + 1 ∈ opt(n) and (q -1)t + 1 ∈ P by induction hypothesis, n ∈ N .

If q ≥ d and r = 1 we consider two cases. If d |n then opt(n) = {(q -1)t + 2,. . ., qt} and thus, since all these options are in N by induction hypothesis, n ∈ P. If d|n then opt(n) = {n/d} ∪ {(q -1)t + 2, . . . , qt}. Since d ≡ 1 (mod t) and n ≡ 1 (mod t) we have n/d ≡ 1 (mod t). Hence, all the options of n are in N by induction hypothesis, and thus n ∈ P.

Finally, if q ≥ d and r > 1 then, since qt + 1 ∈ opt(n) and qt + 1 ∈ P by induction hypothesis, n ∈ N .

This gives that the outcome sequence of the game i-Mark([1, t -1], {d}) is periodic, with preperiod of length dt -1 and period of length t.

Using computer check, it seems that, for every integers t ≥ 2 and d ≥ 2, d ≡ 1 (mod t), the Sprague-Grundy sequence of the game i-Mark([1, t -1], {d}) is 1almost periodic with period of length t. However, the length of the preperiod seems to be more "erratic".

We thus prove this property only for two particular cases, namely d = t and d = 2. Moreover, we will also prove that, in these two cases, the non-periodic column has a nice structure, so that the g-value of any position n can be computed in time O(log n).

3.1.

The game i-Mark([1, t -1], {t}). We now prove that the Sprague-Grundy sequence of the game i-Mark([1, t -1], {t}) is 1-almost periodic for every t ≥ 2 and that the g-value of any position n can be computed in time O(log n).

Theorem 5. For every t ≥ 2, the Sprague-Grundy sequence of the game i-Mark([1, t -1], {t}) is 1-almost periodic, with preperiod of length t 2 -1, period of length t and exception set E = {0}. More precisely, for every integer n = qt + r with q ≥ 0 and r ∈ [0, t -1], we have (i) if q < t and r = 0, or q ≥ t and r = 1, then g(n) = 0, (ii) if q < t and r = 0, then g(n) = r, (iii) if q ≥ t and r > 1, then g(n) = r -1, (iv) if q ≥ t and r = 0, then g(n) ∈ {t -1, t}.

Proof. Claim (i) direclty follows from Theorem 4. For the remaining claims, the proof easily follows by induction. Suppose that the theorem holds up to position n -1, n ≥ 1, and consider the position n. Let n = qt + r > 1, with q ≥ 0 and r ∈ [0, t -1].

If q = 0 and r = 0 then opt(n) = {0, . . . , r -1} and the result follows thanks to the induction hypothesis.

Similarly, if q > 0 and r = 0 then opt(n) = {qt + rt + 1, . . . , qt + r -1} and the result follows thanks to the induction hypothesis.

Finally, if q ≥ t and r = 0 then opt(n) = {q} ∪ {qtt + 1, . . . , qt -1} and, again, the result follows thanks to the induction hypothesis.

Hence, the Sprague-Grundy function G(i-Mark-t) is 1-almost periodic, with preperiod of length t 2 -1, period of length t and exception set E = {0}.

As quoted in Section 1, Alan Guo obtained in [START_REF] Guo | Winning strategies for aperiodic subtraction games[END_REF] a result with a similar flavour for the game Mark-t. He also proved that the g-value of any position n can be computed in time O(n 2 ), using the representation of n in base t.

Our next result, combined with Theorem 5, shows that the situation for the game i-Mark([1, t -1], {t}) is easier since the g-value of any position n can be computed in time O(log n).

For every integer n ≥ 0, let us denote by R t (n) the representation of n in base t and by R 1 t (n) the number in base t obtained from R t (n) by deleting all the trailing 0's. We then have: Theorem 6. Let t ≥ 2 be an integer. Let n be any position of the game i-Mark([1, t -1], {t}) with n = qt, q ≥ t. Then g(n) = t if and only if either:

(i) R 1 t (n) ∈ {R 1 t (k) | k < t 2 , k ≡ t -1 (mod t)} and R t (q)
has an odd number of trailing 0's, or

(ii) R 1 t (n) / ∈ {R 1 t (k) | k < t 2
, k ≡ t-1 (mod t)} and R t (q) has an even number of trailing 0's.

Proof. From Theorem 5, we know that for every position n, with n = qt and q ≥ t, g(n) = t if and only if g(q) = t -1, which happens only if either q = q ′ t -1 with q ′ ≤ t, or q = q ′ t with q ′ ≥ t and g(q ′ ) = t.

The result directly follows from this observation.

3.2.

The game i-Mark([1, t -1], {2}). For the game i-Mark([1, t -1], {2}) we will prove that the Sprague-Grundy sequence is 1-almost periodic for every t ≥ 3 and that the g-value of any position n can be computed in time O(log n).

Note that the case t = 2 corresponds to the game i-Mark({1}, {2}) considered in Subsection 2.2. We will consider separately the case t = 3, and then the general case t ≥ 4.

The game i-Mark([1, 2], {2}

). We first consider the case t = 3 and prove that the Sprague-Grundy sequence of the game i-Mark([1, 2], {2}) is 1-almost periodic.

Theorem 7. The Sprague-Grundy sequence of the game i-Mark([1, 2], {2}

) is 1almost periodic, with preperiod of length 18, period of length 3, and exception set E = {0}. More precisely, for every integer n = 3q + r with q ≥ 6 and r ∈ [0, 2], we have

(i) if r = 1 then g(n) = 0, (ii) if r = 2 then g(n) = 1, (iii) if r = 0 then g(n) ∈ {2, 3}.
Proof. We will determine the value of g(n) for every position n, n ≥ 0, from which the theorem will follow. An easy calculation gives the following first values of G(i-Mark([1,2],{2})): n 0 1 2 3 4 5 6 7 8 9 10 g(n) 0 1 2 0 1 2 3 0 2 1 0 n 11 12 13 14 15 16 17 18 19 20 21 g(n) 2 1 0 2 1 0 2 3 0 1 2

In particular, g(18) = 3, g(19) = 0 and g(20) = 1, so that the claimed property holds for q = 6 and r ∈ [0, 2]. Suppose now that the theorem holds up to n -1, n ≥ 21, and consider the position n. Let n = 3q + r, with q ≥ 7 and r ∈ [0, 2].

If r = 1, the options of n are 3(q -1) + 2, 3q, and (3q + 1)/2 if q is odd. Since (3q + 1)/2 ≡ 2 (mod 3) if q is odd, these three potential options are all N-positions thanks to the induction hypothesis, which gives g(n) = 0.

If r = 2, the options of n are 3q, 3q + 1, and (3q + 2)/2 if q is even. Since (3q+2)/2 ≡ 1 (mod 3) if q is even, the g-value of any of these three potential options is either 0, 2 or 3, thanks to the induction hypothesis, which gives g(n) = 1.

Finally, if r = 0, the options of n are 3(q -1) + 1, 3(q -1) + 2, and 3q/2 if q is even. Thanks to the induction hypothesis, we have g(3(q -1) + 1) = 0 and g(3(q -1) + 2) = 1. Moreover, since 3q/2 ≡ 0 (mod 3) if q is even, we have g(3q/2) ∈ {2, 3} and, therefore, g(n) = 2 if q is odd, or q is even and g(3q/2) = 3, and g(n) = 3 otherwise.

Hence, the Sprague-Grundy sequence of the game i-Mark([1, 2], {2}) is 1-almost periodic, with preperiod of length 18, period of length 3, and exception set E = {0}.

From the proof of Theorem 7, we can see that the set of integers n, n ≥ 18, for which g(n) = 3 has somehow a nice structure. This fact is stated in a more explicit way in the following theorem: Theorem 8. Let n be any position of the game i-Mark( [START_REF] Michael | Lessons in Play: An Introduction to Combinatorial Game Theory[END_REF][START_REF] Berlekamp | Puzzles Column[END_REF], {2}) with n = 3q, q ≥ 6. Then g(n) = 3 if and only if either:

(i) q is even, R 1 (q) = 1 2 or R 1 (q) = 101 2 , and R(q) has an even number of trailing 0's, or (ii) q is even, R 1 (q) = 1 2 , R 1 (q) = 101 2 , and R(q) has an odd number of trailing 0's.

Proof. The proof directly follows from the last part of the proof of Theorem 7, by observing that g(24) = 2 (which corresponds to the case q = 8, 8 = 1000 2 ), g(30) = 2 (which corresponds to the case q = 10, 10 = 1010 2 ), while g(18) = 3 (which corresponds to the case q = 6, 6 = 110 2 ), and g(3q) = 2 for every odd q, q ≥ 6.

Let N 3 denote the set of integers n such that g(n) = 3. The set N 3 is as follows: From Theorems 7 and 8, we get that the g-value of any position n of the game i-Mark( [START_REF] Michael | Lessons in Play: An Introduction to Combinatorial Game Theory[END_REF][START_REF] Berlekamp | Puzzles Column[END_REF], {2}) can be computed in time O(log n).

N 2 = {6,

3.2.2.

The game i-Mark([1, t -1], {2}), t ≥ 4. We now turn to the general case and prove that the Sprague-Grundy sequence G(i-Mark([1, t -1], {2})) is 1-almost periodic for every t ≥ 4, as for the game considered in the previous subsection, except that the g-values 1 and 2 are "switched". Theorem 9. For every t ≥ 4, the Sprague-Grundy sequence of the game i-Mark([1, t -1], {2}) is 1-almost periodic, with preperiod of length 2t -1, period of length t, and exception set E = {0}. More precisely, for every integer n = qt + r with q ≥ 0 and r ∈ [0, t -1], we have (i) if q < 2 and r = 0, or q ≥ 2 and r = 1, then g(n) = 0, (ii) if q < 2 and r = 0, then g

(n) = r, (iii) if q ≥ 2 and r = 2, then g(n) = 2, (iv) if q ≥ 2 and r = 3, then g(n) = 1, (v) if q ≥ 2 and r > 3, then g(n) = r -1, (vi) if q ≥ 2 and r = 0, then g(n) ∈ {t -1, t}.
Proof. The proof is similar to the proof of Theorem 7. Claim (i) direclty follows from Theorem 4 since, in that case, n has an option in P and is thus an N-position. For the remaining claims, the proof easily follows by induction. Suppose the theorem holds up to position n -1, n ≥ 1, and consider the position n.

Let n = qt + r > 1, with q ≥ 0 and r ∈ [0, t -1].

If q = 0 and r = 0 then opt(n) = {0, . . . , r -1} and the result follows thanks to the induction hypothesis.

Similarly, if q > 0 and r = 0 then opt(n) = {qt + rt + 1, . . . , qt + r -1} and the result follows thanks to the induction hypothesis.

Finally, if q > 0 and r = 0 then opt(n) = {qtt + 1, . . . , qt -1} if q and t are odd, and opt(n) = {qt/2} ∪ {qtt + 1, . . . , qt -1} otherwise. Hence, thanks to the induction hypothesis, we get g(n) = t -1 if q and t are odd, or at least one of them is even and g(n/2) = t, and g(n) = t otherwise.

Hence, the Sprague-Grundy sequence of the game i-Mark([1, t -1], {2}) is 1almost periodic, with preperiod of length 2t -1, period of length t, and exception set E = {0}.

As for the game i-Mark( [START_REF] Michael | Lessons in Play: An Introduction to Combinatorial Game Theory[END_REF][START_REF] Berlekamp | Puzzles Column[END_REF], {2}), the g-value of any position n of the game i-Mark([1, t -1], {2}) can be computed in time O(log n), thanks to Theorem 9 and the following characterization, the proof of which is similar to the proof of Theorem 8 and is thus omitted: Theorem 10. Let t ≥ 2 be an integer. Let n be any position of the game i-

Mark([1, t -1], {2}) with n = qt, q ≥ 2, m be the smallest integer such that m ≥ 2t and R 1 (n) = R 1 (m), and z n (resp. z m ) denote the number of trailing 0's of R(n) (resp. of R(m)). Then g(n) = t if

and only if either:

(i) qt is even, g(m) = t -1 and z nz m is odd, or (ii) qt is even, g(m) = t and z nz m is even.

The game i-Mark({a, 2a}, {2})

We consider in this section the game i-Mark({a, 2a}, {2}), a ≥ 1. Note that when a = 1, this game is the game i-Mark( [START_REF] Michael | Lessons in Play: An Introduction to Combinatorial Game Theory[END_REF][START_REF] Berlekamp | Puzzles Column[END_REF], {2}) considered in Subsection 3.2.1. We will prove that, in some cases, the outcome sequence of the game i-Mark({a, 2a}, {2}) is 1-almost periodic. We will also prove that, in those cases, the g-value of any position n can be computed in time O(log n).

For any even a, the g-value of any position n, n odd, is easy to determine. For every integer sequence A = (a i ) i∈N , we define the odd subsequence of A as the subsequence A odd = (a 2q+1 ) q∈N . We then have: Theorem 11. For every integer a ≥ 2, a even, the odd subsequence of the Sprague-Grundy sequence of the game i-Mark({a, 2a}, {2}) is purely periodic, with period of length 3a. More precisely, for every integer n with n = 3qa + r, q ≥ 0 and r ∈ [1, 3a -1], r odd, we have

(i) If r < a then g(n) = 0, (ii) If a < r < 2a then g(n) = 1, (iii) If r > 2a then g(n) = 2.
Proof. If n < a then n has no option and, therefore, g(n) = 0. If a < n < 2a then opt(n) = {n -a} and, therefore, g(n) = 1. If 2a < n < 3a then opt(n) = {n -2a, n -a} and, therefore, g(n) = 2. Hence, the theorem holds for every position n with n odd, n < 3a. The result then easily follows by induction since, for every odd n, opt(n) = {n -2a, n -a}.

However, the whole Sprague-Grundy sequence of the game i-Mark({a, 2a}, {2}) is not always 1-almost periodic with period of length 3a. The smallest length of the period for which this sequence is 1-almost periodic is for instance 18 if a = 3, 60 if a = 5 and 36 if a = 6.

The Sprague-Grundy sequence of the game i-Mark({a, 2a}, {2}) has been proved to be 1-almost periodic with period of length 3a when a = 1 in Theorem 7. We will consider the cases a = 2 and a = 4 in the two following subsections.

4.1.

The game i-Mark({2, 4}, {2}). We first consider the case a = 2 and prove that the Sprague-Grundy sequence of the game i-Mark({2, 4}, {2}) is 1-almost periodic.

Theorem 12. The Sprague-Grundy sequence of the game i-Mark({2, 4}, {2}) is 1-almost periodic, with preperiod of length 11, period of length 6, and exception set E = {0}. More precisely, for any integer n ≥ 11, n = 6q + r with r ∈ [0, 5], we have

(i) if r = 1 or r = 4 then g(n) = 0, (ii) if r = 2 or r = 3 then g(n) = 1, (iii) if r = 5 then g(n) = 2, (iii) if r = 0 then g(n) ∈ {2, 3}.
Proof. We will determine the value of g(n) for every position n, n ≥ 0, from which the theorem will follow.

An easy calculation gives the following first values of G(i-Mark({2,4},{2})): n 0 1 2 3 4 5 6 7 8 9 10 11 g(n) 0 0 1 1 2 2 0 0 1 1 3 2 n 12 13 14 15 16 17 18 19 20 21 22 23 g(n) 2 0 1 1 0 2 2 0 1 1 0 2 Hence, the theorem holds up to n = 23, that is q = 3 and r = 5. Suppose now that the theorem holds up to n -1, n ≥ 23, and consider the position n. Let n = 6q + r, with q ≥ 4 and r ∈ [0, 5].

If r is odd, the options of n are n -2 and n -4 and the claim follows thanks to the induction hypothesis.

If r is even, the options of n are n -2, n -4 and n/2. Again, the claim follows thanks to the induction hypothesis.

Hence, the Sprague-Grundy sequence of the game i-Mark({2, 4}, {2}) is 1almost periodic, with preperiod of length 11, period of length 6, and exception set E = {0}.

From the proof of Theorem 12, we can see that the set of integers n, n ≥ 11, for which g(n) = 3 is not difficult to characterize: Theorem 13. Let n be any position of the game i-Mark({2, 4}, {2}) with n = 6q, q ≥ 2. Then g(n) = 3 if and only if either:

(i) q is even, q ≥ 4, R 1 (q) = 1 2 and R(q) has an even number of trailing 0's, or (ii) q is even, q ≥ 4, R 1 (q) = 1 2 , and R(q) has an odd number of trailing 0's.

Proof. The theorem clearly holds for q = 2 and q = 3 since g(12) = g(18) = 2. Assume the theorem holds up to q -1, q ≥ 4 and consider the position n, n = 6q. We have opt(n) = {n -2, n -4, n/2} with, by Theorem 12, g(n -2) = 0 and g(n -4) = 1. Therefore, g(n) = 3 if and only if g(n/2) = 2. This happens only if q is even -since, if q is odd then n/2 ≡ 3 (mod 6) and g(n/2) = 1 by Theorem 12 -and, thanks to the induction hypothesis, if either R 1 (q) = 1 2 and R(q) has an even number of trailing 0's, or R 1 (q) = 1 2 and R(q) has an odd number of trailing 0's.

From Theorems 12 and 13, we get that the g-value of any position n of the game i-Mark({2, 4}, {2}) can be computed in time O(log n).

4.2.

The game i-Mark({4, 8}, {2}). We now consider the case a = 4. The results are similar to the previous ones and we omit the proofs, which use the same technique.

Theorem 14. The Sprague-Grundy sequence of the game i-Mark({4, 8}, {2}) is 1-almost periodic, with preperiod of length 17, period of length 12, and exception set E = {0}. More precisely, for any integer n ≥ 17, n = 12q + r with r ∈ [0, 11], we have

(i) if r ∈ {1, 3, 4, 10} then g(n) = 0, (ii) if 5 ≤ r ≤ 8 then g(n) = 1, (iii) if r ∈ {2, 9, 11} then g(n) = 2, (iii) if r = 0 then g(n) ∈ {2, 3}.
We just give the first values of G(i-Mark({4,8},{2})), including the preperiod and the period: The set of integers n, n ≥ 17, for which g(n) = 3 is characterized as follows:

Theorem 15. Let n be any position of the game i-Mark({4, 8}, {2}) with n = 12q, q ≥ 2. Then g(n) = 3 if and only if R(q) has an odd number of trailing 0's.

From Theorems 14 and 15, we get that the g-value of any position n of the game i-Mark({4, 8}, {2}) can be computed in time O(log n).

i-MiMark: i-Mark under misère convention

We consider in this section the game i-Mark under misère convention -that is, when the first player unable to move wins the game -, called i-MiMark. The position 0 is thus a P-position for the game i-MiMark.

In [START_REF] Aviezri | The vile, dopey, evil and odious game players[END_REF], Aviezri Fraenkel characterized the sets of N-and P-positions of the game MiMark -Mark under misère convention -and, as for the normal convention, these two sets appeared to be aperiodic.

We will show that the outcome sequence of the game i-MiMark(S, D) is purely periodic -that is, with no preperiod -in many cases, in particular for most of the cases considered in the previous sections.

5.1. The game i-MiMark([1, t -1], D). We first consider the case S = [1, t -1] with t ≥ 2. We first prove the following general result: Theorem 16. For every integer t ≥ 2 and every set D ∈ N ≥2 such that d ≡ 1 (mod t) for every d ∈ D, the outcome sequence of the game i-MiMark([1, t-1], D) is purely periodic with period of length t. More precisely, the set P of P-positions is given by

P = {qt + 1 | q ≥ 0}.
Proof. We clearly have 0 ∈ N and 1 ∈ P. Hence, for every n ∈ [2, t], n ∈ N since, in that case, 1 ∈ opt(n). Consider now the position n, n = qt + r, q ≥ 1 and r ∈ [0, t -1], and assume that the theorem is true up to position n -1.

If r = 0, then (q -1)t + 1 ∈ opt(n) and thus n ∈ N since (q -1)t + 1 ∈ P by induction hypothesis. Similarly, if r > 1 then qt + 1 ∈ opt(n) and thus n ∈ N since qt + 1 ∈ P by induction hypothesis.

Finally, if r = 1 then

opt(n) = {qt -t + 2, . . . , qt} ∪ {(qt + 1)/d | d ∈ D, d|n}.
Since d ≡ 1 (mod t) for every d ∈ D, (qt + 1)/d ≡ 1 (mod t) and, therefore, n ∈ P thanks to induction hypothesis. Hence, the outcome sequence of the game i-MiMark([1, t -1], D) is purely periodic with period of length t.

Note that for every integer t ≥ 3 the game i-MiMark([1, t -1], {t}) -the misère version of the game considered in Subection 3.1, or in Subsection 3.2 if t = 2 -satisfies the hypothesis of Theorem 16. 5.2. The game i-MiMark({a, 2a}, {2}). We now consider the case S = {a, 2a}, a ≥ 1, and D = {2}. We will prove that the sets N and P are purely periodic, with period of length 3a, whenever a = 2 or a is odd.

This claim is easy to prove when a = 2:

Lemma 17. Let n be any position of the game i-MiMark({2, 4}, {2}). We then have n ∈ P if and only if n ≡ 2 (mod 6) or n ≡ 3 (mod 6).

Proof. We prove this result by induction. We clearly have 0, 1 ∈ N and 2 ∈ P. Suppose now that the theorem holds up to n -1, n ≥ 4, and consider the position n. If n ≡ 0, 1, 4 or 5 (mod 3) then n ∈ N since n -4, n -4, n -2 or n -2, respectively, are P-positions thanks to the induction hypothesis. If n ≡ 3 (mod 6) then n ∈ P since, thanks to the induction hypothesis, n -2 ∈ N and n -4 ∈ N . Finally, if n ≡ 2 (mod 6) then n ∈ P since, thanks to the induction hypothesis, n -2 ∈ N , n -4 ∈ N and n/2 ∈ N .

We now consider the case of a odd. The following lemma gives the outcome of any position n with n < a. When a is even, a ≥ 4, the outcome sequence of the game i-MiMark({a, 2a}, {2}) seems to be more "erratic". Using computer check, we observed that the outcome sequence seems to be always periodic, also with period of length 3a, but with a preperiod of, at that time, undetermined length.

We show in Table 2, for the first even values of a, the observed length of the preperiod and the number of exceptions contained in the preperiod -by exception we mean here a position whose outcome is different from the outcome to which it would correspond in the period. The last exception is thus considered as the last element of the preperiod.

Discussion

In this paper, we initiated the study of a new family of impartial combinatorial games -the integral subtraction division games -obtained by restricting in a natural way the availability of division-type moves in subtraction division games. We proved that in many cases these games have a "nice behaviour" since, under normal convention, their Sprague-Grundy sequence is almost periodic and the g-value of any heap of n tokens can be computed in time O(log n). Moreover, we proved that, under misère convention and again in many cases, the outcome sequence is purely periodic.

We finally list below a few open questions related to integral subtraction division games that could be of interest.

(1) Do there exist sets S and D for which the outcome sequence of the game i-Mark(S, D) under normal convention is not periodic? (2) Is it true that, for every d ≡ 1 (mod t), the Sprague-Grundy sequence of the game i-Mark([1, t -1], {d}) is 1-almost periodic with period of length t? (3) What can be said about games of the form i-Mark([1, t -1], {d}), when d ≡ 1 (mod t), under normal convention? under misère convention? (4) Is it true that, for every a ≥ 1, the Sprague-Grundy sequence of the game i-Mark({a, 2a}, {2}) is 1-almost periodic? (5) What can be said about games of the form i-Mark({a, 2a, . . . , ka}, {2}), k ≥ 3, under normal convention? under misère convention?

  a

  6, 16, 20, 24, 28, 36, 44, 52, 60, 64, 68, 76, 80, 84, 92, 96, 100, 108, 112, . . .}.

Table 2 .

 2 Preperiod of the outcome sequence of the game i-MiMark({a, 2a}, {2}), a even R(na) has an even number of trailing 0's (case (ii.b)). Finally, by Proposition 20, n/2 ∈ P if and only if either n/2 is even, which means n ≡ 0 (mod 4) (case (ii.c)), or n/2 is odd, which means n ≡ 2 (mod 4), and R(n/2a) has an even number of trailing 0's (case (ii.d)).

	4	6	8	10	12	14	16
	length of the preperiod 7	9	61 193 105 105 313
	number of exceptions 2	2	6	6	10	8	14
	a 18 20 22 24	26	28	30
	length of the preperiod 345 397 425 497 1129 1217 585
	number of exceptions 10 14 12 26	16	28	18

Aviezri Fraenkel called such numbers vile numbers, and dopey numbers those numbers whose binary representation has an odd number of trailing 0's.

 [START_REF] Aviezri | The vile, dopey, evil and odious game players[END_REF]What can be said about games of the form i-Mark(S, D), with |D| > 1, under normal convention? under misère convention? (7) Is it true that for every even integer a ≥ 4 the outcome sequence of the game i-MiMark({a, 2a}, {2}) is periodic with period of length 3a ? (8) What can be said, when a is odd, about the outcome sequence of the game i-MiMark({a, 2a}, {2})?

This work has been supported by the ANR-14-CE25-0006 project of the French National Research Agency.

1 In [8], Elizabeth Kupin used a slightly different definition for subtraction division games, where division-type moves leave a heap of ⌈n/d⌉ tokens, instead of ⌊n/d⌋ tokens, and the game stops as soon as the heap contains a unique token, instead of no token at all. 1

Lemma 18. Let n be any position of the game i-MiMark({a, 2a}, {2}), a odd, with n ∈ [0, a -1]. We then have n ∈ N if and only if n = 0 or R(n) has an even number of trailing 0's.

Proof. Clearly, the result holds for n = 0. Assume now that n > 0. We use induction on the number z(n) of trailing 0's of R(n). If z(n) = 0 then n is odd, so that n has no option, which implies n ∈ N . Suppose that the result holds up to z(n) = k ≥ 0 and let n be such that z(n) = k + 1. Since n is even, opt(n) = {n/2}, so that n is an N-position if and only if n/2 is a P-position and the result follows thanks to the induction hypothesis.

Incidently, note that Lemma 18 also holds when a is even. We are now able to prove the main result of this subsection:

Theorem 19. Let a be an integer, a ≥ 1. If a = 2 or a is odd then the outcome sequence of the game i-MiMark({a, 2a}, {2}) is purely periodic with period of length 3a.

Proof. The case a = 2 directly follows from Lemma 17. Suppose now that a is odd. We will prove by induction that, for every n ≥ 0, positions n and n + 3a have the same outcome.

Since 0, 1 ∈ N and opt(a) = {0, 1}, we have a ∈ P. Therefore, 3a ∈ N since a ∈ opt(3a), and thus the property holds for n = 0.

Suppose now that the theorem holds up to n -1, n ≥ 1, and consider the position n. We consider two cases, according to the outcome of n.

(1) n ∈ P.

In that case, we have n + a, n + 2a ∈ N . If n is even then n + 3a is odd and thus opt(n + 3a) = {n + a, n + 2a}. Hence, n + 3a ∈ P and we are done. Suppose now that n is odd and, to the contrary, that n + 3a ∈ N . Note first that since n ∈ P we necessarily have n ≥ a by Lemma 18. Since opt(n + 3a) = {n + a, n + 2a, (n + 3a)/2} and n + a, n + 2a ∈ N , we necessarily have (n + 3a)/2 ∈ P, which implies (n + a)/2 ∈ N and (na)/2 ∈ N . Since n ∈ P, we also have na ∈ N which implies that at least one option of na is in P. The possible options of na are (i) (na)/2, but (na)/2 ∈ N as observed above, (ii) n -2a if n ≥ 2a, but in that case n -2a ∈ N since n ∈ P, and (iii) n -3a if n ≥ 3a, which therefore necessarily exists and must be in P. This implies (n -3a)/2 ∈ N and we finally get

which contradicts the induction hypothesis.

(2) n ∈ N .

If n + a ∈ P or n + 2a ∈ P then n + 3a ∈ N and we are done. Suppose therefore that n, n + a, n + 2a ∈ N . By induction hypothesis, this implies in particular na ∈ N if n ≥ a. If n is even then n + a is odd, so that opt(n + a) = {na, n} (resp. opt(n + a) = {n}) if n ≥ a (resp. n < a) and thus n + a ∈ P, contradicting our assumption. Similarly, if n is odd then n + 2a is odd, so that opt(n + 2a) = {n, n + a} and thus n + 2a ∈ P, again contradicting our assumption. This concludes the proof. 1. Period of the outcome sequence of the game i-MiMark({a, 2a}, {2})

Table 1 shows the period, of length 3a, of the outcome sequence of the game i-MiMark({a, 2a}, {2}) for a = 2 or a odd, a ≤ 11.

The period of the outcome sequence of the game i-MiMark({2, 4}, {2}) is given by Lemma 17. The next two propositions will determine the outcome of any position n, with a ≤ n ≤ 3a -1, for the game i-MiMark({a, 2a}, {2}), a odd. These two propositions, together with Lemma 18, thus determine the corresponding outcome sequences.

Proposition 20. Let n be any position of the game i-MiMark({a, 2a}, {2}), a odd, with n ∈ [a, 2a -1]. We then have:

has an even number of trailing 0's.

Proof. Suppose first that n is even. This implies that n-a is odd, so that na ∈ N by Lemma 18. Since na ∈ opt(n), we then get n ∈ P. Suppose now that n is odd. If n = a then opt(n) = {0, 1} which gives n ∈ P since 0, 1 ∈ N by Lemma 18. If n = a, the result again follows from Lemma 18 since opt(n) = {n -a} and na ∈ N if and only if R(na) has an even number of trailing 0's.

Proposition 21. Let n be any position of the game i-MiMark({a, 2a}, {2}), a odd, with n ∈ [2a, 3a -1]. We then have: Proof. Since a ∈ P by Proposition 20, we have 2a ∈ N . If n is odd then na is even, which implies n ∈ N since na ∈ opt(n) and na ∈ P by Proposition 20 (case (i)). Suppose now that n is even, n = 2a. We then have n ∈ N if and only if at least one of the positions n -2a, na, n/2 is in P (note that n/2 ∈ [a+1, a+(a-1)/2]). By Lemma 18, n -2a ∈ P if and only if R(n -2a) has an odd number of trailing 0's (case (ii.a)). Since na is odd, by Proposition 20, na ∈ P if and only if