Etienne Baudrier

Loïc Mazo

Étienne Baudrier

Combinatorics of the Gauss digitization under translation in 2D

Introduction

For a given grid step and a given digitization method, a planar object produces several digital objects in function of its position on the grid. The digitally estimated object characteristics depend on the obtained digital object. The performances of the digital estimators on a set of digital objects coming from the same continuous object up to a translation is an information that can be useful for the digital-estimator assessment. Nevertheless, it can only rely on a knowledge of the combinatorics of the digitization up to a translation and on an ecient generator of translated digital objects. Thereby, as a rst step, a study of the digitization combinatorics under translation is presented in this paper.

The link between geometrical primitives and their digitizations is widely studied. For instance, for the straight segments, it is possible to give the digitization in function of the segment slope and oset. Then, for a digital straight segment, its preimage by this latter function forms the parameter set of all the continuous straight segments whose digitization is equal to the given digital segment. The preimage is used for digital straight segment generation, combinatorics and recognition [START_REF] Dorst | Discrete Representation of Straight Lines[END_REF]. The preimage has been generalized to polygons [START_REF] Feschet | An approach for the estimation of the precision of a real object from its digitization[END_REF]. Nevertheless, the study proposed here comes from another point of view: instead of focusing on the continuous objects giving the same digital object, 1 we study the set of digital objects given by a single continuous object under translation.

A similar approach can be found in the studies of the generation and combinatorics of the disc digitization set in function of its radius and center position [START_REF] Heath-Brown | Lattice points in the sphere[END_REF][START_REF] Mazo | Lattice points in high-dimensional spheres[END_REF][START_REF]On the number of ways to occupy n lattice points by balls in d-dimensional space[END_REF][START_REF] Huxley | On the number of digitizations of a disc depending on its position[END_REF][START_REF]On the number of digital discs[END_REF][START_REF] Nagy | An algorithm to nd the number of the digitizations of discs with a xed radius[END_REF][START_REF] Huxley | Dierent digitisations of displaced discs[END_REF][START_REF] Huxley | The number of N -point digital discs[END_REF][START_REF] Huxley | The number of dierent digital N -discs[END_REF] and to the combinatorics of the strictly convex sets [START_REF] Huxley | The number of congurations in lattice point counting I[END_REF].

In the general case, the digital-object set can be seen as the consequence (through a digitization) of the action of the rigid motion group on the continuous object 1 . In this article, we limit ourselves to the simplest digitization scheme: the Gauss digitization. The Gauss scheme just performs the intersection of the object with the set of the integer points, Z 2 . Then, a function, so-called dual, linking the translation group and the produced digital objects is used by the authors to study the digital-object set up to a translation, for function graphs in [START_REF] Baudrier | Curve digitization variability[END_REF] and for planar object in [START_REF] Mazo | Study on the digitization dual combinatorics and convex case[END_REF]. In the latter case, the dual has been proved to be piecewise constant in function of the translation parameters. This paper focuses on the dual combinatorics. The results on the general and the convex case have already been presented in [START_REF] Mazo | Study on the digitization dual combinatorics and convex case[END_REF]. The paper extends these results to the polygonal case.

The paper layout is the following: two upper bounds are given for the number of digitizations of a planar solid object whose boundary is a Jordan curve. The rst one is expressed in terms of the number of grid cells crossed by the boundary and the second one in terms of the number of intersections when plotting the continuous-object boundary on the torus R 2 /Z 2 . The latter bound is proved to be quadratic in the convex case and to be asymptotically quadratic in the resolution in the polygon case. Some examples are provided in order to compare the two upper bounds both in the convex and the non-convex cases. A conclusion and some perspectives end the paper.

Background

Let us consider a connected compact set S in R 2 whose boundary is a simple closed (Jordan) curve Γ. Thanks to the Jordan curve theorem, we may assume a continuous map f : R 2 → R such that Γ and S are implicitly dened by

Γ = {f (z) = 0 | z ∈ R 2 } S = {z ∈ R 2 | f (z) ≤ 0} .
The common methods to model the digitization of the set S are closely related to each other. In this paper, we assume a Gauss digitization. This method associates to the set S the grid points that lie inside S , that is S ∩ Z 2 , or, equivalently, the binary image dened on Z 2 whose 1's are the points inside S.

We are interested in the variability of the Gauss digitization when the group of the translations acts on S, that is on the sets (u + S) ∩ Z 2 , u ∈ R 2 . In 1 Remark that group actions on a digital object (i.e. a digital object moved in another digital object) were studied for the group of rigid motions in e.g. [START_REF] Nouvel | Congurations induced by discrete rotations: periodicity and quasi-periodicity properties[END_REF][START_REF] Ngo | Combinatorial structure of rigid transformations in 2D digital images Computer[END_REF]17]. In these works, the digitization step is out of the scope and beside, the case of the translations is obvious.

this paper, we focus on the combinatorial aspects of this variance. Of course, the variance has to be understood up to integer translations. This is the reason why we dened in a previous paper [START_REF] Mazo | Study on the digitization dual combinatorics and convex case[END_REF] the dual by translation2 of the digitizations of S as a set-valued function ϕ S dened on the torus T = R 2 /Z 2 which maps each point t ∈ T to the produced digital object, up to integer translations, of u + S where the vector u is any representative of t in R 2 . Let us pick a representative in each class of T so as to form a connected set M called the structuring element. We note C the symmetric of M with respect to the origin: C = -M . The family of sets p + C, p ∈ Z 2 , is a tiling of R 2 . For instance, we can take M = [0, 1) 2 , C = (-1, 0] 2 . From now on, to simplify the notations, we identify t ∈ T with its representative in M and the subsets of Z 2 with their orbits for the action of the integer translations so we can write ϕ S (t) = (t + S) ∩ Z 2 . For any point or set X in R 2 , we denote by proj(X) its projection on the quotient space T. We proved in [START_REF] Mazo | Object digitization up to a translation[END_REF] that the plot of the curve Γ on the torus T, proj(Γ), delineates regions on which the dual function ϕ S is constant.

We dene the grid boundary B as the set of grid points that lie in the (morphological) dilation of the boundary Γ of S by the structuring element M :

B = (Γ ⊕ M ) ∩ Z 2 ,
where ⊕ denotes the Minkowski sum. The set B contains all the points of Z 2 whose membership to the digitization may change when the set S is shifted by a vector u ∈ M . Nevertheless, since R 2 is connected, M is not open so there may exist some points in B ∩ S not liable to change, namely those points p in B for which p + C ⊆ S (see Fig. 1). That is why we have in fact to consider the toggling boundary B as the set of grid points whose membership eectively toggle for some translation by a vector u ∈ M :

B = B \ {p ∈ Z 2 | p + C ⊆ S} .
The set S ∩Z 2 \B of the grid points that are in any digitization of u+S, u ∈ M , is called the digitization core.

Finally, for any p ∈ Z 2 , we set

Γ p = -p + Γ ∩ (p + C) = (-p + Γ) ∩ C , so Γ p = ∅ if p /
∈ B, and we denote by 1 p the indicator function of the set

(-p + S) ∩ C , so 1 p is not constant i p ∈ B. Then, ϕ S (t) = {p ∈ Z 2 | 1 p (-t) = 1} .
In the rest of the article, we use the notation |E| for the cardinal of a set E (|E| ∈ N ∪ {∞}), CC(A) for the family of the connected components of a subset A of R 2 and I J for the disjoint union of the sets I and J. the point q is in B \ B for the square q + C intersects the boundary Γ but is included in S; the point r is in the digitization core for the square r + C is included in S and does not intersect Γ (b) Black: a Jordan curve, medium red discs: the toggling boundary, big blue discs: two points that lie in the grid boundary but that cannot change their membership, small green discs: the digitization core.

In the following section, upper bounds are given for the number of digitizations up to a translation. The rst upper bound is naive. For the second one, the idea is to link the digitization number to the number of the intersection of the translated curves Γ p . Indeed, the dual induces a partition of the torus whose cells frontiers are arcs of the curve proj(Γ). Then, we bound from above the partition size by counting the number of curve intersections in proj(Γ).

3 The general case of Hilbert curves and it is possible to extend the set to prevent multiple counts so that the theoretical upper bound 2 |B| is obtained (see Appendix B).

Bounding up by counting the intersections

In Sec. 3.2, we assume a parametrization of Γ. It induces an order on the points of the curve Γ (for Γ is simple) that is used in the proof of the following proposition.

The dual ϕ S can be regarded as the projection, on the torus T of a nite labeled partition of the tile C (whose cells need not be connected). For the order by renement on the partitions, this partition is lower bounded by the inmum p∈B P p of the binary partitions P p associated to the indicator functions 1 p , p ∈ B. Since some cells of p∈B P p need to be merged whenever the corresponding digitizations are equivalent up to an integer translation, the size of the partition p∈B P p is generally greater than the number of digitizations. For instance, the The next proposition proposes an upper bound on the size of the partition p∈B P p and thereby an upper bound to the number of digitizations by inductively counting the intersections between the curves Γ p , p ∈ B. The idea is to count the partition cells created when adding a curve Γ p . To do this we count the intersection of Γ p with the already added curves. Nevertheless, such an intersection can be with one (Fig. 3b) or more curves (Fig. 3c) and can be a singleton (Fig. 3c), a set of several points (Fig. 3b) or an arc (Fig. 3d). Then, let us specify how we handle intersections in this context.

Denition 1. Let

B = {b 1 , • • • , b i , • • • , b n }, n ≥ 1. Let k ∈ [2, n].
Then, we set:

• inter γ,I = CC γ ∩ i∈I Γ bi \ j∈J Γ bj , where γ ∈ CC(Γ b k ) and I J = [1, k -1]; • # inter k = γ∈CC(Γ b k ) ∅⊂I⊆[1,k-1] w I |inter γ,I | ,
where w I = min(|I| , 2).

Note that the components of all the inter γ,I are two by two disjoint and that # inter k may be innite. The set inter γ,I stands for the set of the connected intersections of the arc γ ⊆ Γ b k with the curves whose indexes are in a subset I, excluding any other curve Γ bi whose index is not in I. The necessity to have all the index subsets comes from the fact that intersections between multiple curves can occur. In Fig. 3b where γ is the green curve Γ b2 , I = {1} and J = ∅, inter γ,I contains four connected components, the four intersection points. In Fig. 3c where γ is the brown curve Γ b3 , we consider that the intersection of γ with the blue curve alone, or with the green curve alone, is empty but the intersection of γ with both curves has one connected component, the triple intersection point. Nevertheless, in # inter 3 , the weighted sum of the cardinals, inter Γ b 3 ,{1,2} is counted twice (the weights are limited to 2 for we show in the proof that if the number of intersections is nite, an intersection creates at most 2 new cells). In Fig. 3d where γ is the red curve Γ b4 , the curve γ has a single intersection with the blue curve, which is an arc, and a single intersection that involves the three other curves, which is then counted twice.

(a) (b) (c) (d) Figure 3: (Color online) (a) Blue: Γ b 1 . (b) Green: Γ b 2 ; # inter2 = inter Γ b 2 ,{1} = 4. (c) Brown: Γ b 3 ; # inter3 = inter Γ b 3 ,{1} + inter Γ b 3 ,{2} +2 inter Γ b 3 ,{1,2} = 0+0+2 = 2. (d) Red: Γ b 4 ; # inter4 = inter Γ b 4 ,{1} + 2 inter Γ b 4 ,{1,2,3} = 2 + 2 = 4.
We are now able to state the proposition that relates the number of digitizations and the number of intersections # inter k .

Proposition 3.2. The size of the partition p∈B P p is upper bounded by

2 + n k=2 # inter k + |CC(Γ b k )| . (1)
Proof. The proposition is proved by a nite induction: we show that the size of the partition m i=1 P bi is upper bounded by 2 + i=1 P bi of the tile C induces a partition Q of Γ bm , as a subset of C, with N m cells (these cells of Γ bm need not be connected). Then, the idea of the proof is to map each cell of Q to its supremum, for the order induced by the parametrization of Γ, namely to the intersection, as dened in Def. 1, its supremum belongs to, or to the empty set when no such intersection exists. Then, though this mapping is not one-to-one, a careful examination of the dierent cases will permit to conclude that N m is upper bounded by # inter m + |CC(Γ bm )|. The congurations studied in the proof are illustrated by Fig. 4.

m k=2 # inter k + |CC(Γ b k )| for m = 1, 2, • • • , n. For m = 1,
Let γ be a connected component of Γ bm and s ∞ be the supremum of γ for the order induced by the parametrization of Γ. Let Q γ be the restriction of Q to γ. We set inter γ = ∅⊂I⊆[1,m-1] inter γ,I , and we assume the following facts that will be proved further:

a) each component in inter γ is included in a cell of Q γ ; b) if a cell of Q γ has a supremum s distinct from s ∞ , then s belongs to some component of inter γ ; c) if a cell K 0 of Q γ has its supremum s in some component K of inter γ and s / ∈ K 0 , then s is the inmum of K. d) if two cells K 1 , K 2 of Q γ have the same supremum s and s / ∈ K 1 ∪ K2, then inter γ has innitely many components; e) if two cells K 1 , K 2 of Q γ have their supremums s 1 , s 2 in the same com-
ponent of inter γ and s 1 ∈ K 1 while s 2 / ∈ K2, then either s 2 = s ∞ and s ∞ belongs to some component of inter γ , or s 2 belongs to at least two curves Γ bi and Γ bj where i, j < m. Then, with these ve assumptions, we deduce the desired upper bound as follows. We map each cell of Q γ to the component of inter γ its supremum belongs to, if any. The other cells are mapped on the empty set. We denote by ψ this mapping.

• If a component K of inter γ has three, or more, preimages by the mapping ψ, then from Fact a, and because Q γ is a partition, we derive that at least two of these preimages do not contain their supremums. Then, from Fact c, we get that these supremums are equal (to the inmum of K). Note that for two cells of Q (in yellow and green), the number of connected components depends on the location of the shape S: if Γ rotates clockwise the yellow cell has 5 components and the green cell one component; otherwise, the yellow cell has 4 components and the green cell does not exist (and the magenta cell is much bigger). (h) By modifying the curve Γ b 2 , replacing the damped sinusoid of x by a damped sinusoid of 1/x, we obtain an example where the number of intersections in interγ is innite.

I ⊆ [1, m -1], and two distinct cells K 1 , K 2 of m-1 i=1 P bi such that K ∩ K 1 = ∅ and K ∩ K 2 = ∅. Let c 1 ∈ K ∩ K 1 and c 2 ∈ K ∩ K 2 . Since K 1 = K 2 , there exists i ∈ [1, m -1] such that 1 bi (c 1 ) = 1 bi (c 2 ).
i ∈ [1, m -1], s is in the open set (1 bi = 0) or in the interior of (1 bi = 1). Thus, there exists an open neighborhood U of s in the tile C which does not intersect any curve Γ bi , 1 ≤ i < m. Thereby, U is included in a cell of the partition m-1 i=1 P bi . Since s = sup(K), there is no point t in γ ∩ U such that t > s. Thus, s = s ∞ . c) Let K 0 be a cell of Q γ whose supremum s is in a component K ∈ inter γ and not in K 0 . Let K 1 be the cell of Q γ which includes the component K (Fact a). Since s / ∈ K 0 , then K 1 = K 0 and s is a limit point of K 0 . If s is not the inmum of K then there exists an interval [u, s], with u < s, in K ⊆ K 1 (for K is connected) and s is not a limit point of K 0 . Contradiction. d) Let K 1 , K 2 be two cells of Q γ that share the same supremum s that is not in K 1 nor in K 2 . Then, s a limit point for the two cells.

Let k ∈ [1, m -1] such that 1 b k takes two distinct values on K 1 and K 2 . For instance, K 1 ⊆ (1 b k = 0) and K 2 ⊆ (1 b k = 1)
. Then, we can inductively build an innite sequence

c 1 < c 2 < • • • < c i < • • • < s such that c 2i-1 ∈ K 1 and c 2i ∈ K 2 for any i ≥ 1. In particular, we have 1 b k (c 2i-1 ) = 0 and 1 b k (c 2i ) = 1 for any i ≥ 1. Then, c 2i-1 / ∈ Γ b k and [c 2i-1 , c 2 * i ] intersects Γ b k .
Therefore, inter γ contains innitely may components between c 1 and s.

e) Let K 1 , K 2 be two cells of Q γ whose supremums s 1 , s 2 belong to the same component K of inter γ . Furthermore, assume s 1 ∈ K 1 and s 2 / ∈ K 2 . Since s 2 / ∈ K 2 , s 2 is a limit point of K 2 and s 2 is the inmum of K (Fact c). In particular, s 2 ≤ s 1 . Let I be the subset of [1, m -1] such that K is a component of inter γ,I . As in the proof of Fact b, we derive that there exists an open neighborhood U of s 1 in C which does not intersect any curve Γ bi , i / ∈ I. Suppose that I is a singleton, say I = {b 1 }. Then, taking a point in K 1 ∩ U (recall that s 2 is a limit point of K 2 ), we found that necessarily 1 b1 = 0 on K 2 , while 1 b1 = 1 on K 1 (for s 1 ∈ K ∩ K 1 ), and 1 bi , i = 1, coincides on K 1 and K 2 . If s 1 = s ∞ , there exists a point u in γ ∩ U greater than s 1 . This point is not in K 1 for s 1 = sup(K 1 ). Since U does not intersect any curve Γ bi , i / ∈ I, we derive that u ∈ K 2 which contradicts s 2 ≤ s 1 . Thus, either s ∞ = s 1 ∈ K, or I is not a singleton.

In the simplest case where the curve segments Γ bm all have one connected component and where the intersections are sets of points belonging to at most two curves, Formula 1 reduces to 1+|B|+I where I is the number of intersection points between the curve segments Γ bm . Furthermore, when projecting the partition n i=1 P bi on the torus T, the cells that touch the boundary of C are identied two by two, which decreases the number of cells in the partition.

Unfortunately, it is dicult to count these cells in the general case.

The convex case

It seems plain that the structure of the dual should be simpler when the set S is convex compared to a set with a winding boundary. We could even hope that the digitizations coincide with the cells of the partition p∈B Γ p , after sewing the boundary of the tile C, and with the connected regions of the torus T delineated by the curve Γ. they are disconnected, it is not possible to continuously move to one conguration to the other without hurting a black toggling point. Note that the triangle could be slightly inated so as to provide a strictly convex counterexample.

inter γ,I is simple when the set S is strictly convex (its boundary does not include any segment) and permits to obtain a quadratic bound for the complexity of the dual in terms of the grid boundary size (to be compare to the exponential bound of Prop. 3.1).

Proposition 4.1. We assume a convex quadrilateral structuring element M .

Let n = |B|. The number of Gauss digitizations of a strictly convex planar object up to a translation is upper bounded by

4n 2 + 4n -6 .
Proof. The proof invokes Lemma A.3 which is stated and proved in the appendix. Let N be the digitization number. Thanks to Prop. 3.2, we have

N ≤ 2 + n m=2 # inter m + |CC(Γ bm )| . (2)
From Lemma A.3, we derive that, for any m ∈

[1, n], γ ∈ CC(Γ bm ), i ∈ [1, m-1], I i |inter γ,I | ≤ 2 |CC(Γ bi )| .
Then,

# inter m ≤ 2 m-1 k=1 |CC(Γ b k )| .
Eventually, Eq (2) turns into

N ≤ 2 + 2 n m=2 m-1 k=1 |CC(Γ b k )| + n m=2 |CC(Γ bm )| ≤ 2 1 + n k=1 (n -k + 1) |CC(Γ b k )| -|CC(Γ b1 )| .
It can easily be seen (from Lemma A.2 for instance) that, for any convex curve Γ and any convex polygon P with c edges, the number of connected arcs in the intersection Γ ∩ P is upper bounded by c. Then, if we assume that the tile C is a convex quadrilateral, we straightforwardly obtain the desired bound.

The term 4n 2 in Prop. 4.1 comes down to n 2 for suciently high resolutions because each curve Γ bi then have just one connected component instead of possibly 4 in the general case. Then, when S a disc of radius r, the result of Prop. 4.1 is close to the one in [START_REF] Huxley | Dierent digitisations of displaced discs[END_REF] which states that the number of digitizations of the disc is asymptotically 4πr 2 + O(r). As the ratio between the size of the grid boundary and the radius r is 8 for the disc, our upper bound in function of the radius r of the disc is asymptotically equivalent to 64r 2 .

The polygonal case

The aim of this section is to give the asymptotic order of the digitization number of a polygon when the digitization step h tends toward 0. Since the upper bound given in Prop. 3.2 relies on the intersection combinatorics, the following propositions focus on the intersection number asymptotic estimation.

For a given ane function y = αx + β, its values at integer points follow an arithmetical sequence. There is a classical result about its fractional part [START_REF] Weyl | Über die Gleichverteilung von Zahlen mod. Eins [On the distribution of numbers modulo one[END_REF]: if the common dierence of the sequence is irrational, the fractional-part sequence is equidistributed over [0, 1), and if it is rational, the distribution is periodic. The idea is to exploit the equidistribution theorem for the sequence of the intersections between integer squares and a straight segment. Nevertheless, some adaptation is needed since the start point is a family, indexed by the grid step h, of nite sequences of intersections.

In this section, d 1 denotes the L 1 -distance.

Diagonal sequences of a straight line

All along the section, we consider a non-vertical straight line D with positive slope (the case where D has a negative slope is similar and leads to the same results).

For any k ∈ Z, we dene v k the intersection of the line D with the straight line ∆ k : x + y = k (see Figure 6). With a negative slope, we would consider the lines ∆ k : x -y = k. Thanks to the modulo-1 equivalence relation, we project the straight lines D, ∆ k and the points v k on the unit square 3 M = [0, 1)×(0, 1] (M = M = [0, 1) 2 if the slope of D is negative). Let us consider the points p = (0, 1) and q = (1, 0) (when the slope is negative, p = (0, 0) and q = (1, 1)). Each line ∆ k projects on the semi-open interval [p, q) while each point v k projects on a point t k ∈ [p, q). Then, we dene the real l k ∈ [0, 1) such that t k = p + l k (q -p).

D l k t q k p U
In the sequel, we refer to the sequences v k k∈Z , t k k∈Z , l k k∈Z as, respectively, the diagonal sequence of D, the 2D-torus diagonal sequence of D and the 1Dtorus diagonal sequence of D. We also dene the corresponding nite sequences with any segment of D. Eventually, we say that [p, q) is the torus diagonal related to D.

The two following lemmas are obvious but useful for our enumeration of the intersections. 3 We project on M rather than M to ensure that the lines ∆ k are projected on a segment. Lemma 5.1. Let D be a non-vertical straight line. Then, the d 1 distance between two consecutive elements of the diagonal sequence of D is equal to 1.

Proof. Putting v k (x k , y k ) and v k+1 (x k+1 , y k+1 ), we derive from the hypotheses Proof. Let us nd the relation that links l k to l k+1 . From Lemma 5.1, we derive that either t k+1 -t k + p (Fig. 7, left), t k+1 -t k + q (Fig. 7, center), is collinear to the line D. Note that in the case depicted in Fig. 7-right, both vectors are collinear to D. Let u be the direction vector of D and s the slope of D. Setting ψ = det(•, u), r = ψ(p) ψ(p)-ψ(q) = 1 1+s and noting that t k+1 -t k = (l k+1 -l k )(q-p), an elementary calculus yields l k+1 -l k = r or l k+1 -l k = r -1. We derive that the sequence (l k ) k∈Z is an arithmetic progression on R/Z with an irrational common dierence 1 1+s . By the equidistribution theorem, we get that the real l k are equidistributed over [0, 1).

v k ∈ ∆ k , v k+1 ∈ ∆ k+1 that (x k+1 -x k ) + (y k+1 -y k ) = 1.

Intersection sequence of two straight lines

Given two non-parallel straight lines projected on the torus, we aim at estimating the number of intersection points. Firstly, we dene the intersection sequence.

Let D 1 , D 2 be two non-parallel straight lines of R 2 . Let [p 1 , q 1 ) and [p 2 , q 2 ) be the torus diagonals related to D 1 and D 2 . For any x, y in [0, 1), the straight lines parallel to D 1 and D 2 passing respectively through p 1 + x(q 1 -p 1 ) and p 2 + y(q 2 -p 2 ) intersect in a point ϕ(x, y).

Let l 1 i , l 2 j be the 1D-torus diagonal sequences of D 1 and D 2 . The sequence ϕ(l 1 i , l 2 j ) i,j∈Z is called the intersection sequence of D 1 and D 2 . An Illustration is given in Figure 8, where the two cases with the intersection in and out of the square are represented. The coordinates (a, b) of the intersection ϕ(x, y) in R 2 are obtained by solving a linear system given by the equations of two straight lines parallel to D 1 and D 2 passing through points that depend anely on x and y. Then the function ϕ is an ane function in (x, y). As a consequence, the set ϕ

-1 (M ) = {(x, y) ∈ [0, 1) 2 |ϕ x,y ∈ M } is measurable. Let dene the function f : (x, y) ∈ [0, 1) 2 → 1 M (ϕ(x, y)) .
Clearly, f is Riemann integrable. Then the criterion of Weyl-Riemann applies to the pairs (l 1 i , l 2 j ) which are equidistributed in [0, 1) 2 (Prop. 5.1):

m i=0 n j=0 f (l 1 i , l 2 j ) -→ m,n→∞ 1 0 1 0 f (x, y)

dx dy

This integral of the indicator function is the area of ϕ -1 (M ) which is a subset of the unit square M . Let us show that this area is equal to the inverse of the area of the parallelogram ϕ([0, 1) 2 ). The fact that ϕ is ane induces that it conserves the ratios:

area(ϕ -1 (M )) area(ϕ -1 (ϕ([0, 1) 2 ))) = area(M ) area(ϕ([0, 1) 2 ))
.

So, we obtain

1 0 1 0 f (x, y)dx dy = 1 area(ϕ([0, 1) 2 )
.

Let us now compute the area of the codomain of ϕ.

Proposition 5.3 (Area of ϕ([0, 1) 2 )). Let D 1 , D 2 be two straight lines in R 2

with distinct irrational slopes s 1 = s 2 . The surface of the intersection set is given by the following formula:

area(ϕ([0, 1) 2 )) = (1 + |s 1 |)(1 + |s 2 |) |s 2 -s 1 | . (3)
Proof. The formula is obtained by an analytic calculus of the area of a parallelogram. The vertices of the parallelogram need to be computed to obtain the parallelogram area: let note c i,j = ϕ(i, j) for i, j ⊂ {0, 1}.

First case: s 1 s 2 ≥ 0. We begin with the subcase s 1 ≥ 0, s 2 ≥ 0 (see .

Firstly we compute the coordinates of the point c 0,1 = ϕ(0, 1), intersection of the straight line parallel to D 1 including the vertex p 1 and the straight line parallel to D 2 including the vertex q 1 :

x c0,1 = s 1 -1 s 2 -s 1 ; y c0,1 = -s 1 (1 + s 2 ) s 2 -s 1 .
Then, the absolute value of the determinant det(c 0,1 c 0,0 , c 0,1 c 1,1 ) gives the result.

area(ϕ([0, 1) 2 )) = (1 + s 1 )(1 + s 2 ) |s 2 -s 1 | .
When the slopes s 1 and s 2 are non-positive, we make a horizontal symmetry to use the previous result. So, the general formula in the case where the two slopes share the same sign is

area(ϕ([0, 1) 2 )) = (1 + |s 1 |)(1 + |s 2 |) |s 2 -s 1 | .
Second case: s 1 s 2 ≤ 0. We begin with the subcase s 1 ≥ 0 and s 2 ≤ 0 (see Then,

x c0,0 = -1 s 1 -s 2 ; y c0,0 = -s 2 s 1 -s 2 ; x c0,1 = -s 2 s 1 -s 2 ; y c0,1 = 1 - s 2 s 1 s 1 -s 2 ; x c1,0 = -s 1 s 1 -s 2 ; y c1,0 = s 1 s 2 s 1 -s 2 .
Then, the desired result is given by the absolute value of the determinant det(c 0,0 c 0,1 , c 0,0 c 1,0 ).

area(ϕ([0, 1) 2 )) = (1 + s 1 )(1 -s 2 ) s 1 -s 2 = (1 + |s 1 |)(1 + |s 2 |) |s 2 -s 1 | .
The second subcase, s 1 ≤ 0 and s 2 ≥ 0 is obtained by inverting D 1 and D 2 which does not change the formula.

We now extend the previous result to the edges of a polygon when the grid step tend toward zero.

Proposition 5.4 (Two polygon edge formula). Let E, F be two edges of a polygon P in R 2 with distinct irrational slopes. For h > 0, we note i(E, F, h) the number of intersections of the edge projections on the torus (R/hZ) 2 . Then,

i(E, F, h) ∼ h→0 n E,h n F,h area(S E,F ) (4)
where The second part of the proof is here to show the equivalence between the straight line case and the case of segments when the grid step tends toward 0.

We assume that E and F are parameterized by

E = {a + tb | t ∈ [0, 1]} and F = {c + ud | u ∈ [0, 1]} where a, b, c, d ∈ R 2 .
Then, nding the intersections of the edge projections on (R/hZ) Remark 5.1. The case where at least one of the slopes is rational leads to replace area(S E,F ) by a discrete approximation depending on the rational denominators in Formula 4.

From the formula (3) and Prop. 5.4, it can be said that two almost parallel edges lead to a large area parallelogram and few intersections. Conversely, if one edge is almost horizontal and the other is almost vertical, the number of intersections is close to the supremum n E,h n F,h .

5.3

Modulo-1 polygon intersection set Theorem 1 (Number of intersections for a polygon). Let P be a polygon whose edges (e i ) m i=1 have distinct irrational slopes. Then, when h tends toward 0, the number of intersections is equivalent to Proof. We apply Prop. 5.4 to each pair of edges.

The result on the intersections can be used is the Gauss digitization upper bound exhibited in Section 3.2.

Corollary 5.1 (Polygon digitization combinatorics). Let P be a polygon whose edges (e i ) m i=1 have distinct irrational slopes and let n h be cardinal of the toggling boundary in the h-grid. The number of Gauss digitizations of the polygon P in a grid of step h is a O(n 2 h ) when h tends toward 0. Proof. Formula (5) has to be transformed to make the toggling boundary cardinal appear. As the intersection sets all contain a unit square, their areas are greater than or equal to 1, that is, for any pair i = j, The term i e i 1 /h is asymptotically equivalent to the toggling boundary cardinal n h . Therefore, the intersection number is a O(n 2 h ). Using this polygon intersection asymptotic upper bound O(n 2 h ) in Formula

(
(1) leads to the result.

Conclusion

We present in this paper two general upper bounds on the number of digital objects obtained from continuous object up to a translation. The rst one is exponential in the cardinal of the the so-called toggling boundary and a generic example reaching this bound is given. The second one is based on the correspondence between the dual connected-components and number of intersections of the tore-projected continuous boundary.

The intersection based upper bound is then derived in two cases. In the convex case, it yields to an upper bound quadratic in the perimeter pixel size. An example of a convex object is given where the set of translations corresponding to a given digitization is not connected. Eventually in the polygon case, provided the slopes are irrational, an upper bound depending on the lengths and slopes of the edges is obtained. This upper bound is asymptotically quadratic in the toggling boundary cardinal.

The perspectives of this work are the following: Firstly to extend the polygonal case method to splines since the equidistribution theorem also applies in this case; then to propose an ecient algorithm for the digital object generation, to study the combinatorics of the digital object set under the rigid transformations (including rotations) and to extend the results to 3D. squares K n+1 i,j (H 0 is just the center of the unit square). Thereby, the partition n i=1 P i is coarser than the partition {K n+1 i,j | 1 ≤ i, j < n} (the boundaries of the squares K k i,j are assigned to the cells so as to coincide with P n ). Since H n+1 passes through the center of each of the squares K n+1 i,j , it passes in each cell of n i=1 P i which gives the claim.

Figure 1 :

 1 Figure 1: (Color online) (a) A Jordan curve Γ and a set of tiles z + C, z ∈ Z 2 and C = (-1, 0] 2 . The point p is in B for the square p + C intersects both Γ and Z 2 \ S;the point q is in B \ B for the square q + C intersects the boundary Γ but is included in S; the point r is in the digitization core for the square r + C is included in S and does not intersect Γ (b) Black: a Jordan curve, medium red discs: the toggling boundary, big blue discs: two points that lie in the grid boundary but that cannot change their membership, small green discs: the digitization core.

Figure 2 :

 2 Figure 2: (a) A circle with diameter 1.7 and the four pixels in the toggling boundary (which is equal to the grid boundary): a, b, c, d. (b) The (atten) dual of the closed disc bounded by the circle. Among the 16 = 2 4 potential digitizations provided by the 4-pixels a,b, c, d, three of them does not actually appear (∅, ac and bd) and some others appear multiple times (the four singular digitizations, which are obviously congruent, and the vertical and horizontal pairs which each appear twice. Eventually, there are only 8 digitizations (and actually the (sewed) dual is divided into 8 regions).

  circle of Fig 2 induces 4 binary partitions of the unit square by the 4 quarters of circle. The inmum of these four partitions yields the partition in 13 classes shown in Fig 2b which is ner than the partition in the 8 classes of digitization (up to integer translations).

  the result is obvious since, for any p ∈ B, P p is a binary partition. Let m > 1. We assume that the number of cells of the partition m-1 i=1 P bi is upper bounded by 2 + m-1 k=2 # inter k + |CC(Γ b k )|. The cells of m-1 i=1 P bi which are included in one of the two cells of P bm , namely the sets (1 bm = 1) and (1 bm = 0), stay unchanged in the partition m i=1 P bi . Conversely, the cells of m-1 i=1 P bi that are intersected by both (1 bm = 0) and (1 bm = 1), which obviously are cells intersected by Γ bm , are each divided in two new cells. Thereby, the number N m of new cells is upper bounded by N m , the number of cells in m-1 i=1 P bi intersected by Γ bm . Besides, the partition m-1

  Fig 4a). Indeed, in such case, the component of inter γ right of the center point is closed and included in the cyan cell while the supremum of the yellow cell is the center point which belongs to the cyan cell.

Figure 4 :

 4 Figure 4: (a) From left to right, the three rst grid squares crossed by a Jordan curve Γ. (b) The two rst curve segments plotted on the tile C: Γ b 1 , Γ b 2 . (c) The partition P b 1 ∧ P b 2 . (d) The third segment γ = Γ b 3 of the curve Γ is plotted on C. (e) The 9 intersections (connected components) in interγ. (f)-(g) The partition Q induced by P b 1 ∧ P b 2 on γ.Note that for two cells of Q (in yellow and green), the number of connected components depends on the location of the shape S: if Γ rotates clockwise the yellow cell has 5 components and the green cell one component; otherwise, the yellow cell has 4 components and the green cell does not exist (and the magenta cell is much bigger). (h) By modifying the curve Γ b 2 , replacing the damped sinusoid of x by a damped sinusoid of 1/x, we obtain an example where the number of intersections in interγ is innite.

Figure 5 Figure 5 :

 55 Figure 5: (Color on-line) (a) A triangle and its toggling boundary. (b) The dual of the (lled) triangle. The four colored regions correspond to the same digitization: the horizontal pair. Red region: cell bc of the partition p∈B Γp. The red region is disconnected by the unique point of the cell abcd. Orange region: cell cd. Pink region: cell ae. (c) The congurations of the shifted triangle in the two red components. Since

Figure 6 :

 6 Figure 6: Example of a diagonal sequence for a straight line D.

  Besides, for the slope of D is positive, x k+1 -x k and y k+1 -y k share the same sign. Then, they are both positive and the result holds. Lemma 5.2. Let [a, b] be a straight segment with irrational slope. For a grid of step h, we note n a,b,h the number of grid squares intersected by the segment [a, b]. Then n a,b,h ∼ h→0 d 1 (a, b) h . Proof. Since the slope of the segment [a, b] is irrational, it contains at most one grid point. Then, it is plain that the number of grid squares crossed by the segment [a, b] diers from the size of the diagonal sequence of [a, b] by at most 2. Using Lemma 5.1 on the h-grid, we conclude straightforwardly. Proposition 5.1 (Diagonal sequence equidistribution). Let D be a non-vertical straight line whose slope is irrational. Then, the 1D-torus diagonal sequence of D is equidistributed over [0, 1).

Figure 7 :

 7 Figure 7: Illustration of the three cases encountered for two consecutive pixels intersected by a straight line.

2 Figure 8 :

 28 Figure 8: Crossing of straight lines. Left: notations ; Center: intersection (white dot) in the square ; Right: intersection (black dot) out of the square.

Fig 9 -

 9 Fig 9-right).

Figure 9 :

 9 Figure 9: Scheme of parallelogram S used for the edge intersection asymptotic number computation. Left: slopes in the same quadrant; right: slopes in distinct quadrant.

  e on the basis (b, d), gives k + tb = ud where t ∈ [0, 1/h + e b ), u ∈ [0, 1/h + e d ) and e b and e d are bounded. The latter constraint equation also expresses as {tb} = {ud} where t ∈ [0, 1/h + e b ), u ∈ [0, 1/h + e d ). Finally, we fall back to the problem of nding the intersection sequence elements of D E and D F that lie in the unit square. Then, we get the result from the rst part of the proof.

1 h 2 i<j≤m e i 1 e j 1

 121 |s ej -s ei | (1 + |s ei |)(1 + |s ej |)

Figure 10 :

 10 Figure 10: (Color online) The boundary of the depicted set is obtained by connecting n-th approximations of the Hilbert lling curve, 0 ≤ n ≤ 4. Red square and red disc: digitization core. Red circle: the ve points in the toggling boundary. The red disc is both in the grid boundary and in the digitization core. Furthermore, it is maximal for both coordinates which ensures that there is no proper congruent digitizations in the image of the dual. The set S has 2 5 digitizations.

  |B| . As |B| is also the number of tiles p + C, p ∈ Z 2 , crossed by the frontier of S, we can state the following proposition.

	3.1	Bounding up by counting the crossed tiles
	Since the grid boundary B contains any integer point whose value may change
	when shifting the set S, we have a rst, obvious, upper bound on the number
	of Gauss digitizations given by 2 Proposition 3.1. The number of Gauss digitizations, up to integer translations,
	is upper bounded by 2 a(Γ) where a(Γ) is the number of tiles crossed by Γ.
	Generally, the digitization enumeration provided by Prop. 3.1 includes false
	positives and multiple counts. For instance, the grid boundary of a circle with
	diameter 1.7 involves 4 to 8 pixels, depending on the grid position, which gives
	an upper bound according to Prop. 3.1 equals to 16, while there exists only 8
	digitizations (see Fig 2). Nevertheless, from any set, it is possible to build a
	new set that avoids false positives by replacing the initial boundary by a family

  By summing on all the connected components of Γ bm , we derive that N m , the number of cells of Q, is upper bounded by # inter m + |CC(Γ bm )| which achieves the proof.Let us now prove the ve facts stated above.

Finally, from Fact d, we conclude that |inter γ | = ∞ which implies that # inter m is also innite. So, N m is obviously upper bounded by # inter m + |CC(Γ bm )|.

Alike, if the empty set has two, or more, preimages by ψ, we derive from Fact b and the denition of ψ that the supremum of these preimages is s ∞ and that s ∞ does not belong to any component of inter

γ . If s ∞ ∈ C, since γ \ K∈interγ K = γ \ i<m Γ bi is an open set of C, all the indicator functions 1 bi would be constant in a neighborhood of s ∞ which contradicts the assumption that s ∞ is the supremum of two cells of Q γ . So, s ∞ / ∈ C

and we conclude as above by invoking Fact d.

• If a component K of inter γ has exactly two preimages K 1 and K 2 by the mapping ψ and if Fact d does not apply (otherwise, we conclude straightforwardly as above), then, from Fact e, and the very denition of # inter m , we see that K is the component of inter y that contains s ∞ and the empty set has no preimage, or the weight of K in # inter m is 2, which corresponds to the number of its preimages.

We readily conclude that the number of cells of Q γ is upper bounded by 1 + ∅⊂I⊆[1,m-1] w I |inter γ,I | where w I = min(2, |I|). a) We demonstrate Fact a by contradiction. Suppose it exists K in inter γ,I ,

  S E,F is the intersection set and n E,h , respectively n F,h , is the number of boundary grid squares crossed by the edge E, respectively F . Proof. Let D E and D F be the straight lines parallel to E and F and passing through the origin. As the slope of the edges E and F are irrational, we derive from Prop. 5.2 that the proportion of elements in the intersection sequence of D E and D F that lie in the unit square tends toward 1/area(S E,F ). Besides, there are n E,h boundary grid squares crossed by the edge E and n F,h other boundary grid squares crossed by the edge F . Then, there are n E,h n F,h pairs of boundary grid squares that can yield an intersection. We derive that the number of elements in the intersection sequence of D E and D F that lie in the unit square is equivalent to n E,h n F,h /area(S E,F ).

  2 amounts to solve {a/h + tb} = {c/h + ud} where {•} denotes the fractional part and t, u lie in [0, 1/h]. It is equivalent to solve k + e + tb = ud where k ∈ Z 2 , e ∈ [0, 1) 2 and t, u lie in [0, 1/h]. Projecting

  1 + |s ei |)(1 + |s ej |) |s ej -s ei | ≥ 1 . i<j≤m e i 1 e j 1 |s ej -s ei | (1 + |s ei |)(1 + |s ej |)

	Then,
	1
	h 2
	≤	1 h 2	i<j≤m	e i 1 e j 1
	≤	1 2

i e i 1 h 2 .

The dual term is an analogy with the algebraic dual because our construction transforms a set of binary images on a discrete set (Z 2 ) in a labeled image on a set of transformations (the translations).

Appendix

A Convex sets

The proof of Lemma A.3 relies on the two following lemmas about convex sets that seem obvious at the rst glance. Nevertheless, since we did not nd any result related to these lemmas in the literature, we provide our own justications of the two statements. Proof. Since [a, b] Γ, the line (ab) does not support S at any point (the notion of supporting line of a convex set is exposed for instance in [2]). So, there exists two supporting lines of S at a and b that cross the line (ab). Then, (ab Proof. Let H -and H + be the two open half-planes bounded by (ab). Since

Lemma A.3 (Intersection of two segments of a convex curve). Let Γ be a Jordan curve whose interior is convex. Let Γ 1 and Γ 2 two disjoint closed segments of the curve Γ and τ a vector of R 2 . Then the intersection of Γ 1 and τ + Γ 2 is composed of none, one, two points or a line segment. Proof. Let p, q be two distinct points in Γ 1 ∩ (τ + Γ 2 ) if such a pair exists.

We denote by Σ 1 the open segment of Γ 1 between p and q. Alike, Σ 2 is the open segment of Γ 2 between -τ + p and -τ + q. We set Σ 1 = Σ 1 ∪ {p, q} and Σ 2 = Σ 2 ∪ {p, q}. Firstly, we prove that Σ 1 ∪ (τ + Σ 2 ) is a straight line segment whenever it contains more than two points. First case: Σ 1 ∪ (τ + Σ 2 ) ⊆ (pq). Then, since Σ 1 and Σ 2 are connected and Γ is simple,

where H 1 is the open half-plane bounded by the 20 line (pq) and containing x, and -τ + p is in R 2 \ H 1 . Then, it can easily be seen that -τ + H 1 is the open half-plane bounded by the line joining -τ + p and -τ + q and including p. Thanks to Lemma A.2, we derive that Σ 2 does not intersect -τ + H 1 . Thus, τ + Σ 2 does not intersect H 1 . In particular, (τ + Σ 2 ) ∩ Σ 1 = ∅. This achieves the rst part of the proof. Now, let r be a point in Γ 1 ∩ (τ + Γ 2 ) which is not in Σ 1 (if such a point exists). For instance, p belongs to the segment of Γ 1 between q and r. Then, the rst part of the proof, applied to the points q and r, implies that Γ 1 ∩ (τ + Γ 2 ) includes the segments [q, r].We straightforwardly concludes that either the intersection of Γ 1 and τ + Γ 2 is composed of at most two points or it is a line segment.

B Examples and counterexamples B.1

Building examples without proper congruent digitizations in the image of the dual Let u and v be two vectors in [0, 1) 2 such that the sets u + S and v + S have distinct but congruent digitizations. Then, there exists an integer vector w, w = 0, such that (u + S)

Then, at least one of the vectors w + v or -w + u has one of its coordinates which is negative.

We derive that if there exists a point in the digitization core which is maximal in S for both coordinates then there is no proper congruent digitizations in the dual. An example with such a maximal point in the digitization core is provided in Fig. 10.

B.2

Building toric partitions in one-to-one correspondence with the power set of the toggling boundary

In this section, we exhibit a way to modify the boundary of the set S in order to ensure that any subset of the toggling boundary is represented in the dual.

To do so, we move along B, ordered in the same way as in Def. 1. Then, a new boundary is built thanks to the approximations of the Hilbert lling curve: the segment of Γ intersecting the n-th cell of B is replaced by a n-th approximation of the Hilbert lling curve H n (extended at its extremities to ensure the continuity of the boundary): see Fig. 10. We consider the family of binary partitions P n of the unit square that comes with the curves H n . We claim that each curve H n+1 crosses each cell of the partition n i=1 P i so that the size of the nal torus partition is 2 N where N is the cardinal of the toggling boundary. To justify our claim, we divide the unit square in a family of 2 n × 2 n small squares (K n i,j ) 1≤i,j≤2 n (n ≥ 0) whose sizes are 1 2 n × 1 2 n . It can be seen that on the one hand, the Hilbert curve H n passes through the center of each of the squares K n i,j and, on the other hand, does not intersect any of the interior of the


Loïc Mazo Icube

Multi-scale arithmetization of linear transformations

A constructive nonstandard interpretation of a multiscale affine transformation scheme is presented. It is based on the Ω-numbers of Laugwitz and Schmieden and on the discrete model of the real line of Reeb and Harthong. In this setting, the nonstandard version of the Euclidean affine transformation gives rise to a sequence of quasi-linear transformations over integer spaces, allowing integer-only computations.

Introduction

In the past decade, a series of papers [3-6, 9, 17] was devoted to the the arithmetization of the continuum with the goal to solve numerical problems using only integers. In particular, a multi-scale arithmetization of the Euler scheme for solving differential equations was developed and used to produce discrete representations of continuous functions and curves. These works are rooted, on the one hand, in the studies of G. Reeb and J. Harthong on nonstandard analysis [START_REF] Diener | Analyse non standard[END_REF][START_REF] Harthong | Une théorie du continu[END_REF] that led to a discrete model of R, the Harthong-Reeb line. This model, though it requires to dispose of an infinitely large number (which was axiomatically assumed), allowed J.P. Reveillès [START_REF] Reveillès | Géométrie discrète, calcul en nombres entiers et algorithmique[END_REF][START_REF] Reveillès | Back and forth between continuous and discrete for the working computer scientist[END_REF] to construct a discretization scheme that resulted in its seminal work on the digital line. On the other hand, D. Laugwitz and C. Schmieden [START_REF] Laugwitz | Ω-calculus as a generalization of field extension: An alternative approach to nonstandard analysis[END_REF][START_REF] Schmieden | Eine erweiterung der infinitesimalrechnung[END_REF] proposed a constructive definition of infinitely large numbers: the Ω-numbers. Defining the Harthong-Reeb line with the Ω-numbers was done in the PhD thesis of A. Chollet [START_REF] Chollet | Non classical formalisms for the computing treatment of the topology and the discrete geometry[END_REF] and gave rise to the Ω-arithmetization scheme.

In the present paper, we aim at using the multi-scale discretization scheme of Chollet et al. to obtain a multiscale discretization of affine transformations between Euclidean spaces. In her PhD thesis [START_REF] Jacob | Applications quasi-affines[END_REF], M.A. Jacob-Da Col, who was a student of Reveillès, studied the properties of an arithmetization of the affine transformations of R 2 , called quasi-affine transformations (QAT). Then, the study was extended to the nD-spaces [START_REF] Blot | Quasi-affine transformation in higher dimension[END_REF][START_REF] Coeurjolly | Quasiaffine transformation in 3-d: Theory and algorithms[END_REF][START_REF] Col | Applications quasi-affines et pavages du plan discret[END_REF][START_REF] Col | nD quasi-affine transformations[END_REF][START_REF] Col | Gaussian numeration systems[END_REF][START_REF] Col | Quasi-linear transformations and discrete tilings[END_REF][START_REF] Nehlig | Applications quasi-affines : pavages par images réciproques[END_REF]. Nevertheless, in these works, the QAT are studied per se and do not result from a discretization scheme, a fortiori not from a multi-scale one. Here, we exhibit the link between an Ω-arithmetization scheme derived from the one of Chollet et al. and sequences of QATs. The arithmetization scheme of Chollet et al. provide a multiscale arithmetic representation of the plane curve y = x(t) solution of the Cauchy problem x = F(t, x), x(t 0 ) = x 0 . A linear transformation T of the Euclidean plane R 2 can be represented by the 2D-plane y = T (x) in the 4D-space of the pair (x, y), that is

R 2 × R 2 .
What is initiated here is to show that the arithmetization scheme of Chollet et al. can be extended to yield a multiscale arithmetic representation of the plane y = T (x) as a sequence of 2D discrete quasi-planes of Z 2 × Z 2 . We prove the convergence of the scheme toward the Euclidean transformation and we prove that the sequence itself contains the same information as the transformation T since there exists an isomorphism (that we provide) between the Euclidean linear transformations and the quasi-linear integer transformation sequences.

Let us end this introduction by two warnings. Firstly, the reader will not find in the article any solution to the issues raised by the computation of linear transformations, for instance rotations: bijectivity, connectivity and so on. It is just a first step toward a constructive, multi-scale, model of such transformations. Secondly, although the tools we use have been designed using non-standard analysis, the presentation we make of them, and our own statements, are within the framework of classical analysis and no knowledge of nonstandard concepts is required to understand the work presented in the remainder of this article.

Background

The Harthong-Reeb line

The constructive version of the Harthong-Reeb line is quite natural. In short, real numbers are modeled by Cauchy sequences of rationals which in turn are converted to integers thanks to a given sequence of increasing scales. Nevertheless, since a real can be modeled by many rational sequences, it is necessary to use an equivalence relation on such sequences and then to transfer the relation into the integer sequences. Moreover, the addition and the multiplication of the real numbers have to be translated in the language of the integer sequence classes (for the obtained equivalence relation). The most problematic issue is to induce the order relation. In this paper, as we focus on an application to elementary linear algebra, we will not tell anything about the order relation over the Harthong-Reeb line. The reader who would like a more deep insight into the Harthong-Reeb line should look at [START_REF] Chollet | Foundational aspects of multiscale digitization[END_REF]Sec. 5].

The two sets, rational sequences and integer sequences, are presented below. A very basic example will end the exposition of the construction. But before, let us give our notations on equivalence relations. In the sequel, given an equivalence relation ∼ on a set X, we denote by [a] the equivalence class of a ∈ X and by ĉ any representative of the class c ∈ X/ ∼ (all the operations defined below are well-defined, that is, they do not depend on the choice of the representatives). Note that the issue of choosing the best representative (in some sense to be precised) is not addressed here. It will be treated in a future work.

Firstly, we present the classes of rational sequences and their operations. Using the Landau notation, we consider the subsets O(1) and o(1) of the rational sequences and we denote by Q lim the quotient space O(1)/o(1) of the bounded sequences of rational up to the sequences converging toward 0. Then, two sequences that share the same limit are in the same equivalence class and, in a given class, all the sequences converge toward the same limit or no sequence converges.

The two operations of the field Q extend without difficulty to Q lim . For any (π, ρ) ∈ Q lim , we set:

π + ρ def = [ π + ρ] , π × ρ def = [ π × ρ] ,
where + and × are the termwise operations on the rational sequences. In a general way, throughout the article, the operations on the sequences are always performed termwise. The restriction of Q lim to the classes of the Cauchy sequences is noted Q Cau . The limit operator provides an isomorphism from (Q Cau , +, ×) to (R, +, ×).

Next, we have to transform rationals into integers. Let ω be a strictly increasing sequence of positive integers. In the theory of Laugwitz and Schmieden [START_REF] Laugwitz | Ω-calculus as a generalization of field extension: An alternative approach to nonstandard analysis[END_REF], such a sequence is called an infinitely large number. Though our work is presented in a classical way (without any other reference to nonstandard analysis), we keep this denomination which recall from where the framework is originated. So, given the infinitely large number ω, we consider the subsets O(ω) and o(ω) of Z N (Landau notation) and we define the Harthong-Reeb line, H R ω , as the quotient space O(ω)/o(ω). We denote by = ω the corresponding equivalence relation. Then, two integer sequences u, v are equivalent for = ω iff the rational sequence u/ω and v/ω are equivalent (u/ω and v/ω are in the same class of Q lim ).

The Harthong-Reeb line is equipped with the following operations.

u + v def = [ û + v] , u × ω v def = [( û × v) ÷ ω] ,
where ÷ denotes the (termwise) integer division: a ÷ b = a/b . The multiplication is indexed by the corresponding infinitely large number for we will use several of these numbers in the sequel. It is unnecessary for the addition. Note that, in particular, the multiplication is defined to be compatible with the multiplication of Q lim , that is, forgetting the equivalence classes, u/ω × v/ω = (u × ω v)/ω.

It was proved in [START_REF] Chollet | Foundational aspects of multiscale digitization[END_REF][START_REF] Chollet | Insight in discrete geometry and computational content of a discrete model of the continuum[END_REF][START_REF] Magaud | Formalizing a discrete model of the continuum in coq from a discrete geometry perspective[END_REF] that the tuple (H R ω , +, × ω ) is a commutative ring which is isomorphic to Q lim via the map ϕ ω and its converse ψ ω (both maps are well-defined):

ϕ ω : H R ω → Q lim ψ ω : Q lim → H R ω ϕ ω (u) = [ û/ω] ψ ω (π) = [ ω × π ]
It should be noted that neither H R ω nor Q lim are fields in the classical sense since many of their elements do not have any inverse 1 .

We end this section about the Harthong-Reeb line by an example. Let ω be the sequence 10 n . To obtain the image of √ 3 in H R ω , we need a sequence of rationals converging toward

Ω-arithmetization scheme

The Ω-arithmetization scheme provides a way to digitize a real function which is the solution of a Cauchy problem x (t) = f (t, x(t)) and x(t 0 ) = x 0 . The differential equation is solved using the Euler scheme through nonstandard analysis, substituting H R ω to R and infinitely small steps to standard steps. Then, going back to the very definition of the Harthong-Reeb line and taking any section 2 of the nonstandard solution, one obtains a sequence of integer functions that converges in some sense toward the real function x that is the solution of the Cauchy problem. The commutative diagram of Fig. 1 summarizes the relation between a real continuous function and the corresponding multi-scale integer function in the Ω-arithmetization scheme as presented in [START_REF] Chollet | Foundational aspects of multiscale digitization[END_REF].

In the diagram, we use several new notations:

1 In [START_REF] Chollet | Foundational aspects of multiscale digitization[END_REF] and [START_REF] Magaud | Formalizing a discrete model of the continuum in coq from a discrete geometry perspective[END_REF] it is stated that ∀x ∈ H R ω , x = ω 0, ∃y ∈ H R ω such that x × ω y = ω 1 but the relation = ω is not the negation of the relation = ω (in [START_REF] Magaud | Formalizing a discrete model of the continuum in coq from a discrete geometry perspective[END_REF], the implementation in the Coq system relies on the intuitionistic logic, so it does not make use of the law of the excluded middle). In this paper, the structure (H R ω , +, × ω ) needs not be a field, just a ring and we make no use of the relation = ω so the assertions can be understood in both classical and intuitionistic logics.

2 Given an equivalence relation, a section is the choice of a representative while the converse operation is called projection.

• E , where E = R, Q or Z, is the set of the bounded sequences in E;

• Z ω is the set of the integer sequences bounded above by the infinitely large number ω (up to a constant factor).

• n s : sequence whose nth term is n s;

• i : x ∈ R → n x ∈ R , where n x = x for any n.
Furthermore, to avoid to introduce too much notations for similar notions, we make an abuse of notations by writing ϕ ω and ψ ω for functions defined on distinct sets but that perform essentially the same calculations:

ϕ ω : t → t/ω, ψ ω : t → ω × t ,
where t is a sequence and the calculation is done termwise, or t is a class of sequences and the calculation is done on each element of the class (then, it is assumed that ϕ ω or ψ ω is well defined). Let us take an example. In order to obtain a multiscale representation of the function

√ 1 + x on [0, 1],
we solve the differential equation

x (t) = 1 2x(t) with x(0) = 1.
Taking β = 2 n and, as in [START_REF] Chollet | Foundational aspects of multiscale digitization[END_REF], ω = β 2 , the nonstandard Euler scheme of Chollet et al. yields the sequences of integer values shown on Table 1. Each line of the table gives the arithmetization ( n f ) of the function √ 1 + t, t ∈ [0, 1] for the pair of scales ( n β , n ω). For instance, ( 2 f )(4) = 21 with scales ( 2 β , 2 ω) = (4, 16). Then, using the functions ϕ ( 2 β ) : t → t/4 and ϕ ( 2 ω) : x → x/16, we obtain a discrete rational approximation of

√ 1 + t, t ∈ [0, 1]
, that is shown in Fig. 2: It was proved in [5, Theorem 1] that the sequence of function n f n converges pointwise toward the solution of the Cauchy problem, that is toward the function √ 1 + x.

Quasi affine transformations

Let f :

Z d → Z d be an affine transformation (d, d ≥ 2)
whose linear part is f 0 . Let r be a positive integer. The QAT (quasi affine transformation) f r is defined by

f r : Z d p → f (p) ÷ r ∈ Z d , R t ∈ R X ∈ R R Q n t ∈ Z β n x ∈ Z ω Q Q lim H R β H R ω Q lim • • Euler scheme R x x H R • f f f / / n f / / F / / O O sections/projections O O O O O O ϕ β •ψ β ϕ ω •ψ ω ψ β / / o o ϕ β ϕ ω o o / / ψ ω ψ β / / o o ϕ β / / ψ ω ϕ ω o o i o o i / / 4 4 lim i i lim Figure 1:
The skeleton of the arithmetization scheme described in [START_REF] Chollet | Foundational aspects of multiscale digitization[END_REF] which links the Euclidean function f with a sequence of integer functions n f . Basically, the integer function n f is the arithmetized expression at the scale n of the Euclidean function f . The sequence n f itself is obtained as a section of the function F which translate f when R is replaced by the Harthong-Reeb line. The function F is computed using a nonstandard version of the Euler scheme for solving differential equations. where ÷ stands for the integer division : p ÷ q = p/q .

A QLT (quasi linear transformation) is a QAT that leaves invariant the origin: f r is a QLT if f (p) = f 0 (p) + q where 0 ≤ q < r coordinatewise. In practice, the parameter q is used to set the rounding mode of the computation.

Given a QLT g, the triple (r, f 0 , q) defining g that has the smallest r is called the canonical representative of g and r is called the scale of g. The QLTs model the Euclidean linear transformations when they are carried out by a computer on a discrete grid. For instance, a rotation about the origin through an angle of π/3 could be modeled by the QLT whose canonical representative is 100, 50 -173 173 50 , 50 . The reader interested by the properties of QATs and QLTs is referred back to the articles cited in the introduction.

In the following section, we show that the Ω-arithmetization scheme extends well to linear transformations between Euclidean spaces, involving sequences of QLTs.

Ω-arithmetization of affine transformations

Let us consider again the commutative diagram presented in Fig. 1. In this section, we want to generalize it by replacing the Euclidean function f by a linear transformation between R d and R d . Since affine transformations are easily characterized by their matrices, we don't need to use any numerical algorithm like the Euler scheme. Generally, when computing a linear transformation of a picture, one tunes the calculus precision independently of the space resolution. So, we need two infinitely large numbers, denoted by α and ω. Practically, for a linear transformation over R d , the sequence α can be viewed as a sequence of resolutions-or a sequence of finer and finer grids-while the sequence ω allows to quantify the matrix coefficients more and more accurately. Nevertheless, multiplying integers modeling real numbers with distinct scales requires to specify the scale of the result. Technically, α = ω implies generally that the rings H R α and H R ω are distinct. Thus, we need to extend the inner product of H R ω to an outer product over H R ω × H R α with values in a third ring H R β . It is natural to choose β as the geometric mean of α and ω: β 2 = α × ω. This is confirmed by the following property which expresses that, when a pair in H R ω × H R α is sent in H R β via the maps ϕ • and ψ • , the product is expressed as the inner product of H R β .

Lemma 1. Let α, β , ω be three infinitely large numbers such that β 2 is equal to α × ω asymptotically:

β 2 ∼ α × ω. Then, for any u ∈ H R α , v ∈ H R ω , ψ β • ϕ ω (v) × β ψ β • ϕ α (u) = [( û × v) ÷ β ] . Proof. Let A be a representative of ψ β • ϕ ω (v) × β ψ β • ϕ α (u).
Going back to the very definitions of ϕ, ψ and × β , we have

[A] = β v ω × β β û α and then, A = β β v ω × β û α ÷ β .
Then, writing β v/ω and β û/ω as β v/ω + O(1) and

β û/ω + O(1), we get A = β β 2 αω v û + O(β v ω ) + O(β û α ) ÷ β .
Since, by hypothesis,

β 2 /αω = 1 + o(1), v ∈ O(ω), û ∈ O(α), we derive A = β ( v û + o( v û) + O(β )) ÷ β .
Invoking again the same hypotheses, we obtain

A = β ( v û) ÷ β + o(β ) + O(1).
Because β is an infinitely large number and by definition of the relation = β the latter equation implies

[A] = ( v û) ÷ β .
Then, given two infinitely large numbers α, ω whose geometric mean is asymptotically equal to the infinitely large number β , we define the outer product × ω α as follows:

H R ω × H R α -→ H R β (v, u) -→ v × ω α u def = [( û × v) ÷ β ] .
From Lemma 1, because the maps ψ and ϕ are morphisms, we readily derive that this product is well-defined and satisfies the following two properties which ensure the linearity of the product:

∀u 1 , u 2 ∈ H R α , ∀v ∈ H R ω , v × ω α (u 1 + u 2 ) = v × ω α u 1 + v × ω α u 2 ; ∀λ , u ∈ H R α , ∀v ∈ H R ω , v × ω α (λ u) = ψ β • ϕ α (λ )(v × ω α u).
Provided α × ω ∼ β 2 , the outer product × ω α allows to define a matrix product from

M d d (H R ω ) ×M d,1 (H R α ) to M d ,1 (H R β )
. Note that this matrix product is a shortcut for a succession of morphisms. Indeed, thanks to the pair of converse isomorphisms (ϕ, ψ), the Harthong-Reeb lines H R α and H R β are bound to H R ω via the following isomorphisms:

ψ ω • ϕ α : H R α -→ H R ω x -→ ω x α ψ ω • ϕ β : H R β -→H R ω x -→ ω x β .
Then, using the outer matrix product is equivalent to applying ψ ω • ϕ α on the vector coordinates, then to perform the inner matrix product and finally to apply ψ β • ϕ ω on the resulting coordinates. Eventually, the proposed arithmetization scheme for the Euclidean linear transformations is defined in the commutative diagram of Fig. 4. In the scheme, the starting point is the d × d matrix F with real coefficients. These coefficients yield Harthong-Reeb versions in H R ω which results in a matrix L and a map between the modules H R α d and H R β d . We say that is an Ωlinear transformation (Ω-LT) derived form the matrix L. In the following section, we study the relation between the map and the Euclidean linear map f .

Ω-LT

In the commutative diagramme of Fig 3, following the external arrows from R e to H R γ e , where (e, γ) ∈ {(d, α), (d , β )}, we observe that, for any real vector x,

ψ γ ( ϕ γ • ψ γ (i(x)) ) = ψ γ • ϕ γ • ψ γ (i(x)) = ψ γ (i(x)) = [ γx ] .
The second equality is true because ψ γ • ϕ γ is the floor function and ψ γ (i(x)) is an integer. Note that we still make an abuse of notation. Indeed, x is a vector and the calculus must be understood as a parallel calculus on each coordinate of x. Now, we denote by ξ HR γ the function from R e to H R γ e that maps x to [ γx ]. This function is a ring morphism since the maps i, ϕ, ψ and the projection map of the equivalence relation are all ring morphisms. Furthermore, ξ HR γ is an injection. Indeed, γx = γ γy implies γ(x -y) ∈ o(γ) and then x = y since x and y are constant vectors. The converse function, defined on ξ HR γ (R e ), maps a vector u ∈ ξ HR γ (R e ) to the real vector lim ρ where ρ = ϕ γ (u). Indeed, assume

u = ξ HR γ (x), that is, u = [ γx ].
Then, by definition of ϕ γ , ρ = γx /γ and the sequence γx /γ converge toward x. Note that the choice of the representative ρ does not matter since, by definition of Q lim , all the sequences belonging to the class ρ share the same limit if any. The converse map can be extended to H R γ e by the function χ HR γ : H R γ e → R e defined by χ HR γ (u) = lim sup( ρ) where ρ = ϕ γ (u). Again, we observe that the choice of the representative ρ does not matter since two sequences whose difference tends toward zero have the same upper limit. We have χ HR γ • ξ HR γ = id where id is the identity map. The converse map ξ HR γ • χ HR γ is neither injective nor surjective. Nevertheless, its restriction to ξ HR γ R d is the identity map.

We are now able to specify the relation between the linear map and the Ω-LT in the commutative diagram of Fig 3 .   Proposition 1. Let f be a linear transformation between R d and R d whose matrix is F = (F i, j ) and α, β be two infinitely large numbers such that α ∈ o(β 2 ). Then, setting

ω = β 2 ÷ α, the Ω-LT from H R α d to H R β d whose matrix is L = ξ HR ω (F i, j ) is such that ξ HR β • f = • ξ HR α .
In other words, one has the commutative diagram:

x F y = FX u L v = LU ξ HR α ξ HR β ξ HR ω f / / / /
Proof. Firstly, we observe that, for any infinitely large number γ, one has

ξ β = ψ β • ϕ γ • ξ γ (1)
because β ωx /ω = β β x for any x ∈ R. Then, since ξ HR β is a ring morphism,

ξ HR β (F x) = ξ HR β ∑ F i, j × X j j = ∑ ξ HR β (F i, j ) × β ξ HR β (X j ) j . R d R d R d R d Q d Z α d Z β d Q d Q lim d H R α d H R β d Q lim d i o o i / / f / / n g / / / / o o ϕ α ψ α / / / / ϕ β ψ β o o o o ϕ α ψ α / / ψ β o o / / ϕ β O O O O O O sections / projections O O ϕ α •ψ α ϕ β •ψ β 1 1 lim m m lim • • Matrix F R y y H R f f Figure 3:
The Ω-arithmetization scheme which associates to the linear transformation f the sequence of quasi-affine transformations n g from Z α d to Z β d . This sequence is obtained as a section of a translation of the matrix F of f using Harthong-Reeb coefficients.

Thus, using (1),

ξ HR β (F x) = ∑ ψ β • ϕ ω ξ HR ω (F i, j ) × β ψ β • ϕ α ξ HR α (X j ) j .
Then, from Lemma 1,

ξ HR β (F x) = ∑ ξ HR ω (F i, j ) × ω α ξ HR α (X j ) j = Lu.
Prop. 1 enables to compute the linear map f from the Ω-LT and, conversely, to compute from f but only for the vectors of H R α that lie in ξ HR α (R d ). Note that we are mostly interested in the former computation which allow us to compute a Euclidean linear transformation at given scales through integer only computations. (2)

ξ HR α (R d ) = ξ HR β • f • χ α . (3)
Before giving the proof, observe that, since the map χ β is essentially a limit operator, Eq. ( 2) is a pointwise convergence property of some sequences of maps from R d to Q d toward the linear map f . It is the object of Sec. 3.2 to describe more precisely these maps while Sec. In the following section we study the relation between the map and the sequence of maps n g in the diagram of Fig. 3. We will show that the maps n g are QLTs.

Ω-LTs and QATs

Tentatively, forgetting the scheme illustrated in Fig. 3, we now focus on the understanding of the Ω-LTs per se, that is going back to the very definition of H R ω .

Firstly, we show that the definition of the multiplication in H R ω has a natural extension with matrices.

Lemma 2. Let α, β , ω be three infinitely large numbers such that αω ∼ β 2 . Let W ∈ M d ,d (H R ω ) be a matrix and U ∈ M d,1 (H R α ) be a column vector. Then,

WU = W U ÷ β ,
where W is any matrix ( W i, j ) i, j , U is any vector ( U j ) j .

Proof. Starting from the matrix product definition, we have

WU = ∑ j W i, j × ω α U j i = ∑ j ( W i, j × U j ) ÷ β i ,
and, since

+ is compatible with = β , WU = ∑ j ( W i, j × U j ) ÷ β i = W U ÷ β .
It appears that Lemma 2 is the key to introduce the relation between Ω-LTs defined over Harthong-Reeb spaces and quasi-linear transformations over integer spaces. Let : H R α d → H R β d be an Ω-LT whose matrix is noted

L (L ∈ M d ,d (H R ω )
where ω = β 2 ÷α). Let L = n L be a sequence of integer matrices such that n L i, j = L i, j . We write ˆ , or n , for the sequence of QLTs whose canonical representatives are ( n β , n L, 0) and, given a sequence p = n p of integer vectors, we denote by ˆ (p) the sequence n n p . Let us illustrate these notations with an example. We consider the matrix F of the rotation through an angle of π/3:

F = 1/2 - √ 3/2 √ 3/2 1/2 ,
and we assume α = 2 n and ω = 10 n . Then, for β , we take the geometric mean of α and ω:

β = √ 20 n . The corresponding matrix in M d d (H R ω ) is L = L 1,1 L 1,2 L 2,1 L 2,2
where

L 1,1 = L 2,2 = [ 0, 5
, 50, 500, . . . ] and,

L 2,1 = -L 1,2 = [ 0, 8, 86, 866, . . . ] .
Then, the sequence of matrices L = n L can be set as

0 L = 0 0 0 0 , 1 L = 5 -8 8
Taking p = (0, 0), (1, 1), (2, 2), (5, 5)
, . . . , whose equivalence class represents the vector exp(iπ/4) in H R α , the sequence of vectors L(p) is (0, 0), (-1, 3), (-3, 13), (-21, 76), . . .

(to be compare with the vector exp(i(7π/12)) at the scales yielded by β ). Then, from Lemma 2, we derive the next assertion that links Ω-LTs and the related sequences of QLTs, that is, basically, matrices of sequences and sequences of matrices.

Corollary 2. Let : H R α d → H R β d be an Ω-LT.
Then, for any vector u ∈ H R α d , one has

(u) = ˆ ( û) .
Proof. Let L and U be the matrices arising from and u.

On the one hand, the nth element of the sequence ˆ ( û) is the vector n n û which, by definition of n , has matrix n L n U ÷ n β . On the other hand, from Lemma 2, the vector (u) has matrix L U ÷ β and, since +, × and ÷ are termwise

operations in Z N , the nth element of the sequence L U ÷ β is n L n û ÷ n β .
The following theorem characterizes the relationship between the Ω-LT from H R d α to H R d β and the quasilinear transformations from

Z d to Z d . Theorem 1. Let be a map from H R α d to H R β d where α ∈ o(β 2 ). Let ω = β 2 ÷ α.
If is an Ω-LT with matrix L, then, for any sequence n g of QLTs with canonical representatives n γ, n G, n p such that n γ = β β , n G ∞ ∈ O(ω) and [ n G ] = L, one has, for any u ∈ H R α d , (u) = n g n û . Conversely, is an Ω-LT if there exists a sequence of QLTs n g with scales n γ such that n γ = ω β , n G ∞ ∈ O(ω) and, for any u ∈ H R α d , there exists û such that (u) = n g n û .

Proof. Firstly, we assume that is an Ω-LT. Let L ∈ M d,d (H R ω ) be the matrix of . Let n g be a sequence of QLTs whose canonical representatives are are the triples n γ, n G, n p where n γ = β β and [ n G ] = L. We derive from Corollary 2 that, for any vector u ∈ H R α d , (u) has a representative whose nth term is n G n û ÷ n β . Then, to achieve the first part of the proof, it suffices to show that the sequences n G n û ÷ n β and n g( n û) are equivalent for the relation = β .

n G( n û) ÷ n β -n g( n û)

= n G( n û) ÷ n β -( n G( n û) + n p) ÷ n γ ≤ 1 + n G( n û) n β - n G( n û) + n p n γ ≤ 1 + n G( n û) n β 1 - n β n γ + n p n γ .
Since, for any integer n, n g is a QLT, we derive that

n G( n û) ÷ n β -n g( n û) ≤ 2 + n G( n û) n β 1 - n β n γ . As u ∈ H R α d , n û ∞ is in O(α) and n G ∞ is in O(β 2 ÷ α), the ratio n G( n û)/ n β is in O(β ).
Moreover, by hypothesis, the ratio n β / n γ tends toward 1. Therefore, the difference between n G n û ÷ n β and n g( n û) is in o(β ), that is, n G n û ÷ n β = β n g( n û) . Conversely, we assume a sequence of QLTs n g with scales n γ such that n γ = β β , n G ∞ ∈ O(β 2 ÷ α) and, for any u ∈ H R α d , there exists û such that (u) = n g n û . Let n G be the matrix of the canonical representative of n g. Since, as shown in the first part of the proof, the sequences n G n û ÷ n β and n g( n û) are equivalent for the relation = β , we derive that, for any u there exists û such that

(u) = n G n û ÷ n β .
Actually, since n G ∞ ∈ O(β 2 ÷ α), the latter equality is true for any representative of u.

We are now able to prove the linearity of .

(u + v) = [ n G( n û + n v) ÷ n β ] = n G( n û) + n G( n v) ÷ n β = [ n G( n û) ÷ n β + n G( n û) ÷ n β + n R ] ,
where n R ∈ {0, 1} d . Thus,

(u + v) = [ n G( n û) ÷ n β ] + [ n G( n û) ÷ n β ] = (u) + (v).
Alike, we prove that (λ

× α u) = ψ β • ϕ α (λ ) × β (u)
for any λ ∈ H R α . On the one hand, from the definition of the product × α , we have λ × α u = n λ n û ÷ n α . Thereby,

(λ × α u) = n G( n λ n û ÷ n α) ÷ n β .
Then, picking a representative a in (λ × α u),

a = β n G( n λ n û ÷ n α) ÷ n β = β n λ n α n β n G( n û) + O β α = β n λ n α n β n G( n û) .
On the other hand,

ψ β • ϕ α (λ ) × β (u) = β λ α × β n G( n û) ÷ n β . Picking a representative b in ψ β • ϕ α (λ ) × β (u), b = β n β n λ n α n G( n û) ÷ n β ÷ n β = β n λ n α n β n G( n û) + O n λ n α + O n G( n û) ( n β ) 2 + O(1)
From the hypotheses, we derive that n λ ∈ O( n α ) and

n G( n û) ∈ O( n β 2 ). Thus, b = β n λ n α n β n G( n û) + O(1) = β n λ n α n β n G( n û) . Therefore a = β b , that is, (λ × α u) = ψ β • ϕ α (λ ) × β (u)
. Eventually, we conclude that is an Ω-LT.

In Sec. 3.2, we have shown that sequences of QLTs arise from the Ω-LTs between H R α d and H R β d and in Sec. 3.1, it was established that those Ω-LTs are in correspondance with the Euclidean linear maps. Thereby, we can achieve the Ω-arithmetization scheme for the Euclidean linear maps. This is the purpose of the next section.

Convergence

Corollary 1 establishes a pointwise convergence property of some sequences of maps-involving Ω-LTs-toward the Euclidean linear transformations. The main result of this section, Theorem 2, enforces the latter result by showing that the convergence is uniform on any compact subset of R n and by describing the convergence speed. Furthermore, rather than appealing to Ω-LT, the result is now expressed in terms of sequences of QLTs.

Before stating and proving our theorem, let us assess the relations between Euclidean linear maps, QLTs and Ω-LT through a new commutative diagram (Fig 4). Besides, in the same way we defined in Sec.

γ : ξ Z γ is an injective map and χ Z γ • ξ Z γ is the identity map of R e . Furthermore, the restriction of ξ Z γ • χ Z γ to ξ Z γ (R e ) is the identity map of ξ Z γ (R e ).
Then, the linear subspace y = f (x) of R 2 × R 2 , which perfectly defines the linear transformation f , is in one-to-one correspondence with the sequence of quasiplanes y = n (x) of Z 2 × Z 2 , providing a multiscale integer model of the plane y = f (x) for the sequence of scales ( n α, n β ) .

R d R d Z α d Z β d H R α d H R β d f / / n / / / / O O sections/projections O O ξ Z α O O χ Z α ξ Z β O O χ Z β ξ HR α # # ; ; χ HR α ξ HR β | | c c χ HR β Figure 4:
The skeleton of the Ω-arithmetization scheme of a Euclidean linear map f . The Ω-LT has for matrix the Harthong-Reeb version (over the ring H R ω where ω = β 2 ÷ α) of the matrix of f . The sections of the Ω-LT for the involved equivalence relations give raise to sequences of QLTs n which uniformly converge, up to a rescaling, toward the linear map f . Theorem 2. Let f : R d → R d be a linear transformation, F its matrix and K ⊂ R d a compact set. Given α, β , ω three infinitely large numbers such that β 2 ∼ αω, we consider the sequence n g where n g is the QLT whose canonical representation is ( n β , n ω F , 0). Then, for any

x ∈ K, f (x) - n g n αx n β ∞ ≤ F ∞ n α + ( F ∞ + 1 + d)( x ∞ + 1) n ω + 1 n β .
Proof. We set p = n (ξ Z α (x)) = n α x and G = n (ξ Z ω (F)) = n ω F . Moreover, we write α, β , ω instead of n α, n β and n ω. The column matrices of the vectors p and x are noted P and X respectively. Then, according to the definition of n g, the column matrix of the vector f (x) -n g p /β is F X -1

β 1 β G P .
We split this vector in four parts whose norms will then be bounded from above. α ω (ω F -G) P+

β 2 αω -1 1
β 2 G P + 1 β 1 β G P - 1 β G P .
The four terms of the latter sum are now bounded from above in infinite norm.

• Because P = α X , one has

(1/α)F (αX -P) ∞ ≤ (1/α) F ∞ (αX -P ∞ ≤ (1/α) F ∞ ;
• the coefficients of the matrix ωF -G are fractional parts: (ωF -G) i, j = ωF i, j -ωF i, j . Then,

(1/αω)(ωF -G) P ∞ ≤ (1/αω) ωF -G ∞ P ∞ < (d/αω) P ∞ .

Since p ∞ < α x ∞ + 1 ≤ α( x ∞ + 1), it follows that (1/αω)(ωF -G) P ∞ is less than (d/ω)( x ∞ + 1);

• By definition of ω, β 2αω < α. Furthermore, G ∞ < ω( F ∞ + 1) and p ∞ < α( x ∞ + 1). Then, the term (β 2 /αω) -1 (1/β 2 )G P ∞ is bounded from above by (1/ω)( F ∞ + 1)( x ∞ + 1).

• (1/β ) (1/β ) G P -(1/β ) G P ∞ is clearly bounded from above by 1/β . Putting together all these upper bounds, we obtain the desired inequality.

Conclusion

Via a constructive version of the real numbers, the Harthong-Reeb line, we have obtained a multi-scale arithmetization scheme of the Euclidean affine transformations. In this framework, an infinite sequence of quasilinear transformations is the translation of a single Euclidean affine map. Depending, on the choices of the infinitely large numbers α, β , ω, the obtained sequence can be more or less obvious. Nevertheless, the merit of this approach is to bring an insight into the properties of discrete computations of affine maps and to open a new field of study. Indeed, it is well known that computer affine transformation implementations are not one-to-one, do not preserve fixed points, topology and so on. But the Harthong-Reeb model show that such implementations operate on sections of equivalence classes instead of equivalence classes. Then, for instance, a Euclidean vector may have a singular preimage while its section on a computer have a non-singular preimage which contains the points of the equivalence class that are exposed by the section (preimage structures are studied in the papers [START_REF] Col | nD quasi-affine transformations[END_REF][START_REF] Col | Quasi-linear transformations and discrete tilings[END_REF] among others). Then, the next task in the proposed framework is to revisit the properties of the quasilinear transformations under this multi-scale interpretation derived from the Harthong-Reeb line.

√ 3 .

 3 So, using the Babylonian algorithm, we set b(0) = 3 and b(n + 1) = (b(n) + 3/b(n))/2 for any n ∈ N. Then the projection of b on Q lim represents the real √ 3 in Q lim . Finally, the morphism ψ ω yields the Harthong-Reeb number which represents √ 3 in H R ω . It is the class (for the relation = ω ) of the sequence 10 n b(n) , that is the sequence 3, 20, 175, 1732, 17320, 173205, . . . up to sequences dominated by 10 n asymptotically.

Figure 2 :

 2 Figure 2: The discretization of the curve y = √ 1 + x at the scale (4, 16) provided by the Ω-arithmetization scheme.

Corollary 1 .

 1 With the notations of Prop. 1, one has f = χ β • • ξ HR α ;

  3.3 study more precisely the convergence. Proof. (of Corollary 1) In the diagram of Prop. 1, we have u ∈ ξ HR α (R d and v ∈ ξ HR β (R d . Since the restriction of χ α to ξ HR α R d is the inverse function of ξ HR α and, alike, the restriction of χ β to ξ HR β R d is the converse function of ξ HR β , we conclude straightforwardly.

  3.1 the maps ξ HR γ : R e → H R γ e and χ HR γ : H R γ e → R e (e ≥ 1), we now define, for any infinitely large number ω, the maps ξ Z ω : R e → Z ω e and χ Z ω : Z ω e → R e by ξ Z ω (x) = ωx and χ Z ω ( n p ) = lim sup n p/ n ω . These maps have the same properties as ξ HR γ and χ HR

1 αF

 1 (αX -P) + 1

Table 1 :

 1

	n\t 0	1	2	3	4	5	6	7	8
	0	1	1
	1	4	5	5
	2	16 18 19 20 21
	3	64 68 71 74 77 80 83 86 88
	4	256 264 271 278 285 292 299 305 311

The function t → √ 1 + t, t ∈ [0, 1], represented as a function from H R 2 n to H R 4 n (see text).

  5 ,

		2 L =	50 -86 86 50	, 3 L =	500 -866 866 500	, . . .
	Thereby, the sequence of QLTs ˆ is defined by
	P	0 -→	0 0 0 0	P ,		P	1 -→	1 4	5 -8 8 5	P ,
	P	2 -→	1 20	50 -86 86 50	P , P	3 -→	1 89	500 -866 866 500	P ,
		. . .