JACODESMATH / ISSN 2148-838X J. Algebra Comb. Discrete Appl. 2(3) • 169-190 Received: 17 March 2015; Accepted: 17 July 2015 DOI 10.13069/jacodesmath.79416 Journal of Algebra Combinatorics Discrete Structures and Applications A further study for the upper bound of the cardinality of Farey vertices and application in discrete geometry∗ Research Article Daniel Khoshnoudirad∗∗ Abstract: The aim of the paper is to bring new combinatorial analytical properties of the Farey diagrams of order (m, n), which are associated to the (m, n)-cubes. The latter are the pieces of discrete planes occurring in discrete geometry, theoretical computer sciences, and combinatorial number theory. We give a new upper bound for the number of Farey vertices FV (m, n) obtained as intersections points of Farey lines ([14]): ∃C > 0,∀(m, n) ∈ N∗2, ∣∣∣FV (m, n)∣∣∣ ≤ Cm2n2(m + n) ln2(mn) Using it, in particular, we show that the number of (m, n)-cubes Um,n verifies: ∃C > 0,∀(m, n) ∈ N∗2, ∣∣∣Um,n∣∣∣ ≤ Cm3n3(m + n) ln2(mn) which is an important improvement of the result previously obtained in [6], which was a polynomial of degree 8. This work uses combinatorics, graph theory, and elementary and analytical number theory. 2010 MSC: 05A15, 05A16, 05A19, 05C30, 68R01, 68R05, 68R10 Keywords: Combinatorial number theory, Farey diagrams, Theoretical computer sciences, Discrete planes, Diophantine equations, Arithmetical geometry, Combinatorial geometry, Discrete geometry, Graph theory in computer sciences 1. Introduction Discrete geometry is the meeting point between several domains of mathematics and computer sciences: combinatorics, graph theory and number theory. To understand better the images, one studies ∗ The subject of this research was initiated at the University of Strasbourg under the contract Conv 10, Blanc-205 of the A.N.R. The research was precised, pursued, and accomplished after the end of the contract by my own means. ∗∗ E-mail: daniel.khoshnoudirad@hotmail.com 169 A new upper bound for Farey vertices in Farey diagrams and application to (m,n)-cubes very advanced theoretical problems coming from pure mathematics. In 2D, many progresses have been done. In 3D, there is a very active research in understanding the discretization of planes. This article brings progress to the combinatorial studies of 3D-patterns. Paul Erdös obtained many results in the field of combinatorial geometry for some particular configurations (see [9] for example). One particular instance of configurations are the Farey diagrams. These diagrams and Farey sequences have many applications. In particular, Farey sequences and Farey diagrams are directly involved in medicine. For instance, in cardiology to modelize optimized systems for pacemakers, or in research against cancer, in imagery and surgery [28]. A very active field of research is the tomography and reconstruction, in which Farey sequences and Farey diagrams also apply [12]. Another example of application to vision is given in [20]. They can also be used for the detection of pieces of discrete planes in 3D-image. For example in [28]. Tomás proves in [27] and [26] that there is an important link between accelerator physics and Farey diagrams. We notice that the Farey diagram of order (n,n) has the same degree as the resonance diagram of order n. The asymptotic behaviour of the two different structures only differs by a factor. There are some similarities between (m,n)-cubes, that we redefine below, and threshold functions on a two-dimensional rectangular grid, for which an asymptotic value for the cardinality of these functions has been derived in [11]. And Farey diagrams are used, since long time in computer science: for example, they are also used when we study the preimage of a discrete piece of plane in discrete mathematics, and the Farey diagram for discrete segments were studied by McIlroy in [19]. Some problems related to Farey diagrams remain unsolved. We are going to focus on this field to study the Farey diagrams from the point of view of combinatorics and number theory. In [6], one of the strategies for the enumeration of pieces of discrete planes, was to estimate the number of vertices in a Farey diagram. This work, combined with a basic property of graph theory, yields an upper bound. This upper bound is an homogeneous polynomial of degree 8: m3n3(m + n)2. In her thesis [7], Debled-Rennesson also studied this problem. Another step forward has been taken by Domenjoud, Jamet, Vergnaud, and Vuillon in [8] where an exact formula (from combinatorial number theory) for the cardinality of the (2,n)-cubes has been derived. In [14], I found that the number of straight Farey lines is asymptotically mn(m + n) ζ(3) when m and n go to infinity. Henceforth, the strategy consisting in focusing on Farey lines to study Farey vertices combinatorics is not sufficient if we want to have a deeper understanding of the combinatorics of the (m,n)-cubes, and we can directly focus on the Farey vertices [14] with some tools of number theory. In the following, I derive an upper bound of degree strictly lower than 6, and not 6, as it was the case in [6]. 2. Preliminaries Let J−m,mK denote the set {−m,.. . ,−1,0,1, . . . ,m} of consecutive integers between −m and m. Definition 2.1. [14](Farey lines of order (m,n)) A Farey line of order (m,n) is a line whose equation is uα + vβ + w = 0 with (u,v,w) ∈ J−m,mK × J−n,nK × Z, and which has at least 2 intersection points with the frontier of [0,1]2. (u,v,w) are the coefficients. (α,β) are the variables. Let denote the set of Farey lines of order (m,n) by FL(m,n). Definition 2.2. [14](Farey vertex) A Farey vertex of order (m,n) is the intersection of two Farey lines. We will denote the set of Farey vertices of order (m,n), obtained as intersection points of Farey lines of order (m,n), by FV (m,n). Definition 2.3. [14](Farey diagrams for the pieces of discrete planes of order (m,n) (or (m,n)-cubes)) The Farey diagram for the (m,n)-cubes of order (m,n) is the diagram defined by the passage of Farey lines in [0,1]2. We recall that b c denotes the integer part, and 〈 〉 denotes the fractional part. If a and b are two integers, a∧ b denotes the greatest common divisor of a and b, and a∨ b denotes the least common multiple. 170 Daniel Khoshnoudirad Figure 1. Farey lines of order (3, 3) ϕ denotes the Euler’s totient function. Card(A) denotes the cardinality of the set A. Definition 2.4. [10](Farey sequences of order n) The Farey sequence of order n is the set Fn = { 0 }⋃{p q , ∣∣∣1 ≤ p ≤ q ≤ n,p∧q = 1} . We mention [10] as a forthcoming modern reference work on the Farey sequences. Several standard variants of the notion of Farey diagram are mentioned there. Definition 2.5. [14](Farey edge) A Farey edge of order (m,n) is an edge of the Farey diagram of order (m,n). We denote the set of Farey edges by FE(m,n). Definition 2.6. [14](Farey graph) The Farey graph of order (m,n) is the graph GF(m,n) = (FV (m,n),FE(m,n)). Definition 2.7. (Farey facet) A Farey facet of order (m,n) is a facet of the Farey graph of order (m,n). We will denote the set of Farey facets of order (m,n) by FF(m,n). Let m and n be two positive integers. We let Fm,n denote the set = J0,m− 1K × J0,n− 1K. Um,n denotes the set of all (m,n)-cubes. Furthermore, the Proposition 3 of [6] shows that the set of (m,n)- cubes of the discrete planes Pα,β,γ only depends of (α,β), and is denoted by Cm,n,α,β. 171 A new upper bound for Farey vertices in Farey diagrams and application to (m,n)-cubes Definition 2.8. [6]((m,n)-pattern) Let m and n be two positive integers. A (m,n)-pattern is a map w:Fm,n −→ Z. m × n is called the size of the (m,n)-pattern w. The set of the (m,n)-patterns will be denoted by Mm,n. Definition 2.9. [6]((m,n)-cube, see figure 2) The (m,n)-cube wi,j(α,β,γ) at the position (i,j) of a discrete plane Pα,β,γ is the (m,n)-pattern w defined by: w(i′,j′) = pα,β,γ(i + i ′,j + j′)−pα,β,γ(i,j) for all (i′,j′) ∈Fm,n = bα(i + i′) + β(j + j′) + γc−bαi + βj + γc for all (i′,j′) ∈Fm,n where pα,β,γ(i,j) = bαi + βj + γc and { (i,j,pα,β,γ(i,j)), ∣∣∣(i,j) ∈ Z2} defines the discrete plane Pα,β,γ. This definition shows that: ∀ (i,j) ∈ Z2,∀(α,β,γ) ∈ R3, wi,j(α,β,γ) = w0,0(α,β,αi + βj + γ). Now, we recall some results obtained in [6], and some direct consequences of this result. Proposition 2.10. (Recall [6]) 1. The (k,l)-th point of the (m,n)-cube at the position (i,j) of the discrete plane Pα,β,γ can be computed by the formula : wi,j (α,β,γ) (k,l) = { bαk + βlc if 〈αi + βj + γ〉 < Cα,βk,l bαk + βlc+ 1 else where Cα,βk,l = 1−〈αk + βl〉. 2. The (m,n)-cube wi,j(α,β,γ) only depends on the interval [B α,β h ,B α,β h+1[ containing 〈αi + βj + γ〉 where the Bα,βh are the number C α,β k,l ordered by ascending order. 3. For all h ∈ J0,mn−1K, if [Bα,βh ,B α,β h+1[ is non-empty, then there exists i,j such that 〈αi + βj + γ〉 ∈ [B α,β h ,B α,β h+1[. Such a way, the number of (m,n)-cubes in the discrete plane Pα,β,γ is equal to card ({ C α,β k,l ∣∣∣(k,l) ∈Fm,n}) ≤ mn. Corollary 2.11. ([6]) 1. ∀(α,β,γ) ∈ [0,1]2 ×R,w0,0(α,β,γ) = w0,0(α,β,〈γ〉). 2. ∀(α,β,γ) ∈ [0,1]2 ×R,∀(i,j) ∈ Z2, wi,j(α,β,γ) = w0,0(α,β,αi + βj + γ) = w0,0(α,β,〈αi + βj + γ〉). 3. By the Proposition 2.10, the set of (m,n)-cubes of the discrete planes Pα,β,γ only depends of (α,β) and is denoted by Cm,n,α,β. Corollary 2.12. ([6]) Let O be a Farey connected component, then O is a convex polygon and if p1,p2,p3 are distinct vertices of the polygon O, then : • for any point p ∈O, Cm,n,p = Cm,n,p1 ∪Cm,n,p2 ∪Cm,n,p3. 172 Daniel Khoshnoudirad Figure 2. Example of two (4, 3)-cubes (red and green) • for any point p ∈O in the interior of the segment of vertices p1 and p2, Cm,n,p = Cm,n,p1 ∪Cm,n,p2. By this corollary, all the (m,n)-cubes are associated to Farey vertices. And according to the Propo- sition 2.10, there are at most mn (m,n)-cubes associated to a Farey vertex, therefore∣∣∣Um,n∣∣∣ ≤ mn∣∣∣FV (m,n)∣∣∣. 173 A new upper bound for Farey vertices in Farey diagrams and application to (m,n)-cubes 3. Fundamental properties Lemma 3.1. (Reminder of Graph Theory) Let us consider n straight lines. The number of vertices constructed from these n lines is at most n(n−1) 2 . We know by [14], that the number of Farey lines, is equivalent to a polynomial of degree 3 in m and n, when m and n go to infinity. According to Lemma 3.1, these lines form a number of vertices, given at most by a polynomial of order 6 ([6]). But this method is far from giving an optimal upper bound for the cardinality of the Farey vertices. In order to obtain a new and more powerful result of combinatorics on this set of vertices, we are going to study the properties of the Farey lines passing through a Farey vertex. Our idea is to use the theorem: Proposition 3.2. (Reminder of Graph Theory) In a simple graph G = (V,E), we have:∑ x∈V deg(x) = 2 |E| where V is the set of vertices, and E is the set of edges, and deg(x) is the degree of the vertex x, that is the number of edges which are adjacent to the vertex x. Theorem 3.3. (Gauss theorem) If (a,b,c) ∈ Z3, such that a | bc, and a∧ b = 1. Then, a | c. 4. Modeling of the problem of Farey vertices of order (m, n) To have a precise estimate on the number of edges in the Farey graph of order (m,n), it is sufficient to compute the degree of any Farey vertex. Henceforth, below we to study in more detail the mapping defined on FV (m,n): x 7→ deg(x). Proposition 4.1. (Upper bound for the number of Farey lines of order (m,n) passing through a Farey vertex of order (m,n)) Let P = ( p q , p′ q′ ) be a Farey vertex of order (m,n). Let us define r,r′,s,s′,d and d′ as follows:  p = (p∧p′)r, q = (q ∧q′)s p′ = (p∧p′)r′, q′ = (q ∧q′)s′ d = p∧p′, d′ = q ∧q′. (1) • If (p,p′) ∈ N∗2, then we have deg(P) ≤ 2 [ 2 ⌊ 1 dr ( m p q + n p′ q′ )⌋ + min ( 2 ⌊ m sr′ ⌋ , ⌊ n s′r ⌋) + 2 ⌊ 1 dr′ ( m p q + n p′ q′ )⌋ + min ( 2 ⌊ m sr′ ⌋ , ⌊ n s′r ⌋) ×2 ⌊ 1 d ( m p q + n p′ q′ )⌋] . • If p = 0 then we have deg ( 0, p′ q′ ) ≤ ( 1 + ⌊ n q′ ⌋) (2m + 1). The vertices such that p = 0, are the vertices of the set{( 0, p′ q′ ) with p′ q′ ∈ Fn } . 174 Daniel Khoshnoudirad • If p′ = 0, then we have deg ( p q ,0 ) ≤ ( 1 + 2 ⌊ m q ⌋) (n + 1). The vertices such that p′ = 0 are the vertices of the set{( p q ,0 ) with p q ∈ Fm } . Proof. We can always suppose that in the equation of a Farey line, (of the type: uα + vβ + w = 0, with (u,v,w) ∈ J−m,mK × J−n,nK ×Z), we have v ≥ 0. Because if v < 0, it is sufficient to multiply the equation by −1. And we obtain the same line, but (−u,−v,−w) ∈ J−m,mK × J0,nK ×Z. First, we handle the case where p = 0 or p′ = 0. p = 0 ⇒ p′v + q′w = 0 ⇒ { v = q′k w = −p′k ⇒ 0 ≤ k ≤ n q′ (because of the preliminary). There are at most 1 + ⌊ n q′ ⌋ such integers. And there are 2m + 1 integers in the interval J−m,mK. The vertices such that p = 0, are the vertices of the set{( 0, p′ q′ ) with p′ q′ ∈ Fn } . p′ = 0 ⇒ pu + qw = 0 ⇒ { u = qk w = −pk ⇒ 0 ≤ |k| ≤ m q . There are at most 1 + 2 ⌊ m q ⌋ such integers. The vertices such that p′ = 0, are the vertices of the set {( p q ,0 ) with p q ∈ Fm } . Now, we can handle the general case remaining: (p,p′) ∈ N∗2 In GF(m,n), because a Farey line generates at most 2 edges passing through the Farey vertex P , we have: deg(P) ≤ 2×Card ({ Farey Lines passing through P }) (2) So, we are looking for an optimal bound for the cardinality of (u,v,w) ∈ J−m,mK × J1,nK ×Z such that u p q + v p′ q′ = −w ⇔ upq′ + vp′q qq′ = −w (with the condition u∧v ∧w = 1), that is u(p∧p′)r(q ∧q′)s′ + v(p∧p′)r′(q ∧q′)s qq′ = −w. 175 A new upper bound for Farey vertices in Farey diagrams and application to (m,n)-cubes (p∧p′)(q ∧q′) urs′ + vr′s (q ∧q′)2ss′ = −w. After simplification: (p∧p′) urs′ + vr′s (q ∧q′)ss′ = −w. (p∧p′)(urs′ + vr′s) = −w(q ∧q′)ss′ (p∧p′)urs′ = −w(q ∧q′)ss′ − (p∧p′)vr′s ⇒ s | (p∧p′)urs′ As s∧ [(p∧p′)rs′] = 1, the Gauss theorem (Theorem 3.3) implies that s | u. So,{ ∃u′ ∈ Z such that u = su′ ∃v′ ∈ Z such that v = s′v′. So, 0 ≤ |u′| ≤ m s and 1 ≤ v′ ≤ n s′ . (p∧p′) su′rs′ + s′v′r′s (q ∧q′)ss′ = −w ⇒ (p∧p′) u′r + v′r′ (q ∧q′) = −w (theorem of Gauss) ⇒ (p∧p′) | w and (q ∧q′) | u′r + v′r′. When w is fixed, the consequence of the hypothesis of primality enables to solve this diophantine equation: Let us fix w,   u′ = u0 ( − w p∧p′ (q ∧q′) ) + r′k v′ = v0 ( − w p∧p′ (q ∧q′) ) −rk for k ∈ Z (3) where (u0,v0) is a particular solution of the diophantine equation in (x,y): rx + r′y = 1. The determinant of this system in ( w p∧p′ ,k ) is: u0q ∧q′r + v0(q ∧q′)r′ = (q ∧q′)[u0r + v0r′] = q ∧q′. So, one can determine ( w p∧p′ ,k ) by the Cramer formulas: ( w p∧p′ k ) =  − rq ∧q′ − r ′ q ∧q′ v0 −u0  ( u′ v′ ) . As in [14], we can always suppose that v ≥ 0 (else we mutiply uα + vβ + w = 0, by −1). Moreover, we have seen that as we have: |w| ≤ m p q + n p′ q′ , 176 Daniel Khoshnoudirad and as p∧p′ | w, we can deduce that there exists w′ such that w = w′(p∧p′). So, 0 ≤ |w′| ≤ ⌊ 1 p∧p′ ( m p q + n p′ q′ )⌋ . As for a Farey line, (u,v) 6= (0,0), we deduce that (u′,v′) 6= (0,0). First we handle the case where v = 0 ⇒ v′ = 0 ⇒ v0 ( w p∧p′ ) q∧q′ +rk = 0 ⇒ p | w. As ru0 +r′v0 = 1, we deduce by the Bezout theorem that r ∧ v0 = 1. In addition to it, we have r ∧ (q ∧ q′) = 1. So, r ∧ (v0(q ∧ q′)) = 1. And by the Gauss theorem, we have that r | w d . In this case, it is impossible that w = 0, else k = 0 and u = v = w = 0. So, there are at most 2 ⌊ 1 p ( m p q + n p′ q′ )⌋ . Farey lines passing through the Farey vertex. In the second case, v > 0, so we have  − ⌊m s ⌋ ≤ u′ ≤ ⌊m s ⌋ , 1 ≤ v′ ≤ ⌊n s′ ⌋ . When w is fixed,   r′k = u′ + u0 ( w p∧p′ ) q ∧q′, rk = v0 ( − w p∧p′ ) q ∧q′ −v′ for k ∈ Z. So,   − ⌊m s ⌋ + u0 ( w p∧p′ ) q ∧q′ ≤ r′k ≤ ⌊m s ⌋ + u0 ( w p∧p′ ) q ∧q′, − ⌊n s′ ⌋ + v0 ( − w p∧p′ ) q ∧q′ ≤ rk ≤−1−v0 ( w p∧p′ ) q ∧q′ for k ∈ Z. Now, we distinguish 2 cases: • If w = 0, the number of suitable integers k is bounded by min ( 2 ⌊ m sr′ ⌋ , ⌊ n s′r ⌋) . • w 6= 0 – The case where r′k = u0 ( w p∧p′ ) q ∧q′ ⇒ r′ | ( w p∧p′ ) . Then, the number of suitable w dr′ is at most 2 ⌊ 1 dr′ ( m p q + n p′ q′ )⌋ . – Else r′k 6= u0 ( w p∧p′ ) q ∧q′, so the number of suitable integers k is bounded by min ( 2 ⌊ m sr′ ⌋ , ⌊ n s′r ⌋) 177 A new upper bound for Farey vertices in Farey diagrams and application to (m,n)-cubes and the number of ( k, w d ) is bounded by: min ( 2 ⌊ m sr′ ⌋ , ⌊ n s′r ⌋) ×2 ⌊ 1 d ( m p q + n p′ q′ )⌋ . And, of course, the existence of such couples implies that: min ( 2 ⌊ m sr′ ⌋ , ⌊ n s′r ⌋) ×2 ⌊ 1 d ( m p q + n p′ q′ )⌋ ≥ 1. In particular,   ⌊ m sr′ ⌋ ≥ 1⌊ n s′r ⌋ ≥ 1. (4) So Card ({ Farey Lines passing through P }) ≤ 2 ⌊ 1 dr ( m p q + n p′ q′ )⌋ + min ( 2 ⌊ m sr′ ⌋ , ⌊ n s′r ⌋) + 2 ⌊ 1 dr′ ( m p q + n p′ q′ )⌋ + min ( 2 ⌊ m sr′ ⌋ , ⌊ n s′r ⌋) ×2 ⌊ 1 d ( m p q + n p′ q′ )⌋ and by (2), we have deg(P) ≤ 2 [ 2 ⌊ 1 dr ( m p q + n p′ q′ )⌋ + min ( 2 ⌊ m sr′ ⌋ , ⌊ n s′r ⌋) + 2 ⌊ 1 dr′ ( m p q + n p′ q′ )⌋ + min ( 2 ⌊ m sr′ ⌋ , ⌊ n s′r ⌋) ×2 ⌊ 1 d ( m p q + n p′ q′ )⌋] which proves the claim. 5. Bound for |FV (m, n)| The equations in (1) are:   r = p p∧p′ ,s = q q ∧q′ , r′ = p′ p∧p′ ,s′ = q′ q ∧q′ , d = p∧p′,d′ = q ∧q′. 178 Daniel Khoshnoudirad Proposition 5.1. Let  A(m,n,p,q,p′,q′) = 2 min ( 2 ⌊ m sr′ ⌋ , ⌊ n s′r ⌋) B(m,n,p,q,p′,q′) = 4 ⌊ 1 dr′ ( m p q + n p′ q′ )⌋ C(m,n,p,q,p′,q′) = 4 ⌊ 1 dr ( m p q + n p′ q′ )⌋ D(m,n,p,q,p′,q′) = 2 ⌊ 1 d ( m p q + n p′ q′ )⌋ E(m,n,p,q,p′,q′) = 2A(m,n,r,r′,s,s′,d′)×D(m,n,r′,p,q,p′,q′) A′(m,n) = ∑ 0≤p 0 such that, ∀n ∈ N\{0,1}, we have n∑ i=1 1 i ≤ K log n. Proposition 5.5. ∃K > 0,∀(m,n) ∈ N∗2, A′(m,n) ≤ Km2n2(m + n) ln2(mn). Proof. A′(m,n) = ∑ 1≤p 1 in the sums in order to use the Corollary 5.4 (and the same for d′s′). A′ ≤ 2mn∑ d′=1 b2mn d′ c∑ s=1 b2mn d′s c∑ s′=1 d′s∑ r=1 d′s>1 d′s′∑ r′=1 d′s′>1 d′ n rr′ + Km2n3 ln2(mn) ≤ K′n ln2(mn) 2mn∑ d′=1 d′ b2mn d′ c∑ s=1 b2mn d′s c∑ s′=1 1 + Km2n3 ln2(mn) ≤ K′n ln2(mn) 2mn∑ d′=1 d′ b2mn d′ c∑ s=1 2mn d′s + Km2n3 ln2(mn) 181 A new upper bound for Farey vertices in Farey diagrams and application to (m,n)-cubes ≤ K′n ln2(mn) 2mn∑ d′=1 b2mn d′ c∑ s=1 2mn s + Km2n3 ln2(mn) ≤ K′n ln2(mn) 2mn∑ s=1 b2mns c∑ d′=1 2mn s + Km2n3 ln2(mn) ≤ K′m2n3 ln2(mn) 2mn∑ s=1 1 s2 + Km2n3 ln2(mn) ≤ K”m2n3 ln2(mn) A′(m,n) = ∑ 1≤p1 d′s′∑ r′=1 d′s′>1 d′ m rr′ + Kn2m3 ln2(mn) ≤ K′m ln2(mn) 2mn∑ d′=1 d′ b2mn d′ c∑ s=1 b2mn d′s c∑ s′=1 1 + Kn2m3 ln2(mn) ≤ K′m ln2(mn) 2mn∑ d′=1 b2mn d′ c∑ s=1 2mn d′s + Kn2m3 ln2(mn) ≤ K′m2n ln2(mn) 2mn∑ d′=1 b2mn d′ c∑ s=1 1 s + Kn2m3 ln2(mn) 182 Daniel Khoshnoudirad ≤ K”n2m3 ln2(mn). Proposition 5.6. ∃K > 0,∀(m,n) ∈ N∗2, B′(m,n) ≤ Km2n2(m + n) ln2(mn). Proof. B′(m,n) = ∑ 1≤p 1 in the sum in order to use the Corollary 5.4. B ′ 1(m,n) ≤ K ′m 2mn∑ d′=1 b2mn d′ c∑ s=1 b2mn d′s c∑ s′=1 d′s ln(d′s′) + Km3n2 ln2(mn) ≤ K′m ln(2mn) 2mn∑ d′=1 b2mn d′ c∑ s=1 d′s 2mn d′s + Km3n2 ln2(mn) 183 A new upper bound for Farey vertices in Farey diagrams and application to (m,n)-cubes ≤ K′m2n ln(2mn) 2mn∑ d′=1 b2mn d′ c∑ s=1 1 + Km3n2 ln2(mn) ≤ K′m2n ln(2mn) 2mn∑ d′=1 2mn d′ + Km3n2 ln2(mn) ≤ K”m3n2 ln2(mn). B ′ 2(m,n) ≤ n 2mn∑ q=1 q∑ p=1 p∧q=1 2mn∑ q′=1 q′∑ p′=1 p′∧q′=1 1 d′s′ ≤ n 2mn∑ d′=1 b2mn d′ c∑ s=1 b2mn d′s c∑ s′=1 d′s∑ r=1 d′s′∑ r′=1 ⌊ min( d ′s r , d ′s′ r′ ) ⌋∑ d=1 1 d′s′ ≤ n 2mn∑ d′=1 b2mn d′ c∑ s=1 b2mn d′s c∑ s′=1 d′s∑ r=1 d′s′∑ r′=1 1 r′ ≤ K′n 2mn∑ d′=1 b2mn d′ c∑ s=1 b2mn d′s c∑ s′=1 d′s ln(d′s′) + Kn3m2 ln2(mn) ≤ K′n ln(2mn) 2mn∑ d′=1 b2mn d′ c∑ s=1 d′s 2mn d′s + Kn3m2 ln2(mn) ≤ K′n2m ln(2mn) 2mn∑ d′=1 b2mn d′ c∑ s=1 1 + Kn3m2 ln2(mn) ≤ K′n2m ln(2mn) 2mn∑ d′=1 2mn d′ + Kn3m2 ln2(mn) ≤ K”n3m2 ln2(mn). Proposition 5.7. ∃K > 0,∀(m,n) ∈ N∗2, C′(m,n) ≤ Km2n2(m + n) ln2(mn). Proof. C′(m,n) = ∑ 1≤p 0, ∀(m,n) ∈ N∗2,E′(m,n) ≤ Km2n2(m + n) ln(mn). Proof. E′(m,n) = ∑ 1≤p1 1 r′s + Km2n3 ln(mn) ≤ K′mn2 ln(mn) 2mn∑ d′=1 b2mn d′ c∑ s=1 b2mn d′s c∑ s′=1 1 ss′ + Km2n3 ln(mn) ≤ K′m2n3 ln(mn) b2mn d′ c∑ s=1 b2mn d′s c∑ s′=1 1 s2s′2 + Km2n3 ln(mn) ≤ K”m2n3 ln(mn). The computation is exactly the same for E ′ 2(m,n). It remains to treat the two simple cases where p = 0 or p′ = 0 of the Proposition 4.1: Proposition 5.9. ∃K > 0,∀(m,n) ∈ N∗2, ∑ p′ q′ ∈Fn deg ( 0, p′ q′ ) + ∑ p q ∈Fm deg ( p q ,0 ) ≤ Kmn(m2 + n2). Proof. • [( 1 + ⌊ n q′ ⌋) (2m + 1) ] ≤ 2m + 1 + 2nm + n ≤ 5mn + 1 ∑ p′ q′ ∈Fn deg ( 0, p′ q′ ) ≤ ∑ p′ q′ ∈Fn [( 1 + ⌊ n q′ ⌋) (2m + 1) ] ≤ ∑ p′ q′ ∈Fn (5mn + 1) ≤ (5mn + 1) |Fn| • [( 1 + 2 ⌊ m q ⌋) (n + 1) ] ≤ n + 1 + 2mn + 2m ≤ 5mn + 1 ∑ p q ∈Fm deg ( p q ,0 ) ≤ ∑ p q ∈Fm [( 1 + 2 ⌊ m q ⌋) (n + 1) ] ≤ ∑ p q ∈Fm (5mn + 1) ≤ (5mn + 1) |Fm| We know [29] that |Fn| = 1 + n∑ k=1 ϕ(k) ∼ +∞ n2 2ζ(2) . 187 A new upper bound for Farey vertices in Farey diagrams and application to (m,n)-cubes So there exists K > 0 such that∑ p′ q′ ∈Fn deg ( 0, p′ q′ ) + ∑ p q ∈Fm deg ( p q ,0 ) ≤ Kmn(m2 + n2). Hence, we have: ∃K > 0,∀(m,n) ∈ N∗2, 2|FE(m,n)| = ∑ x∈FV (m,n) deg(x) ≤ Km2n2(m + n) ln2(mn). So, we can say that: ∃K ≥ 0, |FE(m,n)| ≤ Km2n2(m + n) ln2(mn). Hence, in the Farey graph of order (m,n), we have: Proposition 5.10. ∃K > 0,∀(m,n) ∈ N∗2, |FE(m,n)| ≤ Km2n2(m + n) ln2(mn). Moreover, as the Farey graph of order (m,n) is planar, we can apply to it the Euler’s Formula: Theorem 5.11. (Recall)(Euler’s formula for the connex planar graphs) In a connex planar multi-graph, having V vertices, E edges, and F facets, we have: V −E + F = 2. In particular, this involves that we have V ≤ E + 2. ∃K > 0,∀(m,n) ∈ N∗2, |FV (m,n)| ≤ Km2n2(m + n) ln2(mn). This greatly improves the upper bound previously found in [6]. And we can add: ∃K > 0,∀(m,n) ∈ N∗2, |FF(m,n)| ≤ Km2n2(m + n) ln2(mn). Corollary 5.12. (Upper bound for the (m,n)-cubes) ∃K > 0,∀(m,n) ∈ N∗2, |Umn| ≤ Km3n3(m + n) ln2(mn). 6. Summary-conclusion In order to improve the upper bound for ∣∣∣Um,n∣∣∣, an interesting work using combinatorics, graph theory, and number theory, has been to focus on the diophantine aspects of Farey diagrams, combined with some other arguments of graph theory to estimate better the cardinality of Farey vertices. And in this work, we obtained two important results: • ∃C > 0,∀(m,n) ∈ N∗2, ∣∣∣FV (m,n)∣∣∣ ≤ Cm2n2(m + n) ln2(mn) whereas the previous published result was a polynomial of degree 6 [6]. 188 Daniel Khoshnoudirad • And we obtained: ∃C > 0,∀(m,n) ∈ N∗2, ∣∣∣Um,n∣∣∣ ≤ Cm3n3(m + n) ln2(mn) whereas the previous published result existing was a polynomial of degree 8 [6]. Acknowledgment: I dedicate this work to the memory of my beloved father, who did his best for me and for the science. I also want to thank my brother(and his wife) and my sister(and her husband) for their support during the preparation of this article. I am thankful to Grégory Apou for his help. I also would like to thank the Professor Andre Leroy for his meaningful help, his expertise in algebra, and for having given to me an invitation to give a successful seminar on Combinatorics and Number Theory, and their applications to Computer Sciences, in the L.M.L. of the University of Artois, on January, 2015. I also thank the director of the I.M.B., the Professor Alain Bachelot for his help, and two other persons: Professor Hugues Talbot, and Professor Pierre Villon for their great kindness. And I also thank the experts of Number Theory: Henri Cohen and Yuri Bilu for their advises. My gratitude also goes to David, and Jacques(and his wife) the friends of my father, for their encouragement to publish this article. This work could not take his final version without the meaningful help of the anonymous referees to whom I express my sincere acknowledgements for their insightful remarks, as they carefully reviewed my work and gave generously of their time and their expertise. References [1] D. M. Acketa and J. D. Žunić, On the number of linear partitions of the (m, n)-grid, Inform. Process. Lett., 38(3), 163-168, 1991. [2] T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976. [3] T. Asano and N. Katoh, Variants for the hough transform for line detection, Comput. Geom., 6(4), 231-252, 1996. [4] J. M. Chassery, D. Coeurjolly and I. Sivignon, Duality and geometry straightness, characterization and envelope, Discrete Geometry for Computer Imagery, Springer, 1-16, 2006. [5] J. M. Chassery and A. Montanvert, Geometrical representation of shapes and objects for visual perception, Geometric Reasoning for Perception and Action, Springer, 163-182, 1993. [6] A. Daurat, M. Tajine and M. Zouaoui, About the frequencies of some patterns in digital planes application to area estimators, Comput. Graph., 33(1), 11-20, 2009. [7] I. Debled-Rennesson, Etude et reconnaissance des droites et plans discrets, PhD thesis, 1995. [8] E. Domenjoud, D. Jamet, D. Vergnaud and L. Vuillon, Enumeration formula for (2, n)-cubes in discrete planes, Discrete Appl. Math., 160(15), 2158-2171, 2012. [9] E. Szemerédi and W. T. Trotter Jr., Extremal problems in discrete geometry, Combinatorica, 3(3-4), 381-392, 1983. [10] A. Hatcher, Topology of numbers, Unpublished manuscript, in preparation; see http://www.math.cornell.edu/~hatcher/TN/TNpage.html. [11] P. Haukkanen and J. K. Merikoski, Asymptotics of the number of threshold functions on a two- dimensional rectangular grid, Discrete Appl. Math., 161(1), 13-18, 2013. [12] W. Hou and C. Zhang, Parallel-beam ct reconstruction based on mojette transform and compressed sensing, International Journal of Computer and Electrical Engineering, 5(1), 83-87, 2013. [13] Y. Kenmochi, L. Buzer, A. Sugimoto and I. Shimizu, Digital planar surface segmentation using local geometric patterns, Discrete Geometry for Computer Imagery, Springer, 322-333, 2008. [14] D. Khoshnoudirad, Farey lines defining Farey diagrams, and application to some discrete structures, Appl. Anal. Discrete Math., 9(1), 73-84, 2015. [15] A. O. Matveev, A note on Boolean lattices and Farey sequences, Integers, 7, A20, 2007. [16] A. O. Matveev, Relative blocking in posets, J. Comb. Optim., 13(4), 379-403, 2007, Corrigendum: arXiv:math/0411026. 189 ~ A new upper bound for Farey vertices in Farey diagrams and application to (m,n)-cubes [17] A. O. Matveev, Neighboring fractions in Farey subsequences, arXiv:0801.1981, 2008. [18] A. O. Matveev, A note on Boolean lattices and Farey sequences II, Integers, 8, A24, 2008. [19] M. D. McIlroy, A note on discrete representation of lines, AT&T Technical Journal, 64(2), 481-490, 1985. [20] E. Remy and E. Thiel, Exact medial axis with euclidean distance, Image and Vision Computing, 23(2), 167-175, 2005. [21] E. Remy and E. Thiel, Structures dans les spheres de chanfrein, RFIA, 483-492, 2000. [22] I. Svalbe and A. Kingston, On correcting the unevenness of angle distributions arising from integer ratios lying in restricted portions of the Farey plane, Combinatorial Image Analysis, Springer, 110- 121, 2005. [23] G. Tenenbaum, Introduction to analytic and probabilistic number theory, 46, Cambridge University Press, 1995. [24] E. Thiel, Les distances de chenfrein en analyse d’images : fondements et applications, Thélse de doctorat, UJF Grenoble, 1994. [25] E. Thiel and A. Montanvert, Chamfer masks: Discrete distance functions, geometrical properties and optimization, Pattern Recognition, Vol. III. Conference C: Image, Speech and Signal Analysis, Proceedings., 11th IAPR International Conference on, IEEE, 244-247, 1992. [26] R. Tomás, Asymptotic behavior of a series of Euler’s totient function ϕ(k) times the index of 1/k in a Farey sequence, arXiv:1406.6991, 2014. [27] R. Tomás, From farey sequences to resonance diagrams, Physical Review Special Topics-Accelerators and Beams, 17(1), 014001, 2014. [28] V. Trifonov, L. Pasqualucci, R. Dalla-Favera and R. Rabadan, Fractal-like distributions over the rational numbers in high-throughput biological and clinical data, Scientific reports, 1, 2011. [29] G. H. Hardy and E. M. Wright, Introduction à la théorie des nombres, Traduction de François Sauvageot, Springer. 190 Introduction Preliminaries Fundamental properties Modeling of the problem of Farey vertices of order (m,n) Bound for |FV(m,n)| Summary-conclusion References