ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.00924 J. Algebra Comb. Discrete Appl. 3(2) • 105–123 Received: 30 October 2015 Accepted: 25 January 2016 Journal of Algebra Combinatorics Discrete Structures and Applications Erratum to “A further study for the upper bound of the cardinality of Farey vertices and applications in discrete geometry” [J. Algebra Comb. Discrete Appl. 2(3) (2015) 169-190] Erratum Daniel Khoshnoudirad Abstract: The equation (4) on the page 178 of the paper previously published has to be corrected. We had only handled the case of the Farey vertices for which min (⌊ 2m sr′ ⌋ , ⌊ n s′r ⌋) ∈ N∗. In fact we had to distinguish two cases: min (⌊ 2m sr′ ⌋ , ⌊ n s′r ⌋) ∈ N∗ and min (⌊ 2m sr′ ⌋ , ⌊ n s′r ⌋) = 0. However, we highlight the correct results of the original paper and its applications. We underline that in this work, we still brought several contributions. These contributions are: applying the fundamental formulas of Graph Theory to the Farey diagram of order (m, n), finding a good upper bound for the degree of a Farey vertex and the relations between the Farey diagrams and the linear diophantine equations. 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 In [9], 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 [17], I found that the number of straight Farey lines is asymptotically mn(m + n) ζ(3) when m and n go to infinity. Daniel Khoshnoudirad (email: daniel.khoshnoudirad@hotmail.com). 105 http://eds.yildiz.edu.tr/AjaxTool/GetArticleByPublishedArticleId?PublishedArticleId=2169 http://eds.yildiz.edu.tr/AjaxTool/GetArticleByPublishedArticleId?PublishedArticleId=2169 D. Khoshnoudirad / J. Algebra Comb. Discrete Appl. 3(2) (2016) 105–123 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 [17] with some tools of number theory. The work which has been done for the case where min (⌊ 2m sr′ ⌋ , ⌊ n s′r ⌋) ∈ N∗, remains correct. But the case where min (⌊ 2m sr′ ⌋ , ⌊ n s′r ⌋) = 0 has to be handled. The goal of this study is to understand better how to bound |FV (m,n)| in an optimal way. 2. Preliminaries Let J−m,mK denote the set {−m,.. . ,−1,0,1, . . . ,m} of consecutive integers between −m and m. Definition 2.1. [17](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 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 [14] as a forthcoming modern reference work on the Farey sequences. Several standard variants of the notion of Farey diagram are mentioned there. Definition 2.3. (Farey vertex) A Farey vertex of order (m,n) is the intersection of two Farey lines in [0,1]2. 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.4. (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, d e denotes the upper 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. ϕ denotes the Euler’s totient function. Card(A) or |A| denotes the cardinality of the set A. Definition 2.5. (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. (Farey graph) The Farey graph of order (m,n) is the graph FG(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 [9] shows that the set of (m,n)-cubes of the discrete planes Pα,β,γ only depends of (α,β), and is denoted by Cm,n,α,β. Definition 2.8. [9]((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. 106 D. Khoshnoudirad / J. Algebra Comb. Discrete Appl. 3(2) (2016) 105–123 Figure 1. Farey lines of order (3, 3) Definition 2.9. [9]((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α,β,γ. Now, we recall some results obtained in [9], and some direct consequences of this result. Proposition 2.10. (Recall [9]) 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 107 D. Khoshnoudirad / J. Algebra Comb. Discrete Appl. 3(2) (2016) 105–123 Figure 2. Example of two (4, 3)-cubes (red and green) 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. [9] 1. ∀(α,β,γ) ∈ [0,1]2 ×R,w0,0(α,β,γ) = w0,0(α,β,〈γ〉) 108 D. Khoshnoudirad / J. Algebra Comb. Discrete Appl. 3(2) (2016) 105–123 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. [9] 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 • 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)∣∣∣. 3. Fundamental properties and lemmas 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 [17], 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 ([9]). 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. Moreover, we remind the Euler’s Formula: Theorem 3.3. (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 109 D. Khoshnoudirad / J. Algebra Comb. Discrete Appl. 3(2) (2016) 105–123 4. Bound for the degree of a farey vertex 4.1. Modeling Corollary 4.1. In FG(m,n), |FE(m,n)| ≤ ∑ x∈FV (m,n) nl(x,m,n) where nl(x,m,n) denotes the number of Farey lines of order (m,n) passing through the vertex x. Proof. In FG(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 }) (1) So, by the handshaking proposition 3.2, 2 |FE(m,n)| ≤ ∑ x∈FV (m,n) 2nl(x,m,n) We simplify by 2, and we obtain the result. Theorem 4.2. (Gauss theorem) If (a,b,c) ∈ Z3, such that a | bc, and a∧ b = 1. Then, a | c. Theorem 4.3. [2](Asymptotic development of the harmonic series) If x ≥ 1, then∑ n≤x 1 n = log x + C +O( 1 x ). where C is Euler’s constant, and τ the divisor function. We can apply this theorem and we are able to say in particular: Corollary 4.4. There exists K > 0 such that, ∀n ∈ N\{0,1}, we have n∑ i=1 1 i ≤ K log n. Lemma 4.5. Let (a,b) ∈ N∗ ×N. Let x ∈ R.⌊ bbxc a ⌋ = ⌊ bx a ⌋ Proof. There is a classical equality which already exists, where a = b. Here, we generalize it : bbxc a −1 < ⌊ bbxc a ⌋ ≤ bx a We multiply by a all the members : bbxc−a < a ⌊ bbxc a ⌋ ≤ bx ⇔bbxc−a + 1 ≤ a ⌊ bbxc a ⌋ ≤ bx 110 D. Khoshnoudirad / J. Algebra Comb. Discrete Appl. 3(2) (2016) 105–123 So, using the definition of the integer part of bx, we have bx−a < a ⌊ bbxc a ⌋ ≤ bx ⇔ bx a −1 < ⌊ bbxc a ⌋ ≤ bx a So, by the definition of the integer part of bx a , we obtain the claim. Proposition 4.6. (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′ (2) Let us define nlmax(P,m,n) as following: nlmax(P,m,n) = ( min (⌊ 2m sr′ ⌋ , ⌊ n s′r ⌋) + 1 ) × ( 2 ⌊ 1 d ( m p q + n p′ q′ )⌋) + 2 ⌊ m sd′ ⌋ + min (⌊ 2m sr′ ⌋ , ⌊ n s′r ⌋) . • If (p,p′) ∈ N∗2. Then, we have nl(P,m,n) ≤ nlmax(P,m,n) • If p = 0 then we have nl ( 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 } • If p′ = 0, then we have nl ( 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.) 111 D. Khoshnoudirad / J. Algebra Comb. Discrete Appl. 3(2) (2016) 105–123 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 } . Then, it remains to handle the general case: (p,p′) ∈ N∗2 So, we are looking for an optimal bound for the cardinality of (u,v,w) ∈ J−m,mK × J0,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. (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 4.2 implies that s | u. So, { ∃u′ ∈ Z such that u = su′ ∃v′ ∈ Z such that v = s′v′ (3) If v = 0, then we have: u = qk ⇒ 1 ≤ |k| ≤ ⌊ m sd′ ⌋ w = −pk ⇒ 1 ≤ |k| ≤ ⌊ 1 p ( m p q + n p′ q′ )⌋ 112 D. Khoshnoudirad / J. Algebra Comb. Discrete Appl. 3(2) (2016) 105–123 So, in the case where v = 0, 1 ≤ |k| ≤ min (⌊ m sd′ ⌋ , ⌊ 1 p ( m p q + n p′ q′ )⌋) . We come back to the general equation (with v′ ≥ 1): In particular, 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 4.2) ⇒ (p∧p′) | w and (q ∧q′) | u′r + v′r′. And because of the non-redundancy hypothesis, we have: u′ ∧v′ | q ∧q′ The diophantine equation becomes: u′r + v′r′ = − w d d′ (4) 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 (5) where (u0,v0) is a particular solution of the diophantine equation in (x,y): rx + r′y = 1. In particular,   − ⌊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′ (6) The determinant of this system in ( w p∧p′ ,k ) is: u0q ∧q′r + v0(q ∧q′)r′ = (q ∧q′)[u0r + v0r′] = q ∧q′ Moreover, we have seen that as we have: |w| ≤ m p q + n p′ q′ , 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′ )⌋ Now, we distinguish 2 cases: 113 D. Khoshnoudirad / J. Algebra Comb. Discrete Appl. 3(2) (2016) 105–123 • If w = 0, by the lemma 4.5, the number of suitable integers k is bounded by min ( 2 ⌊ m sr′ ⌋ , ⌊ n s′r ⌋) • w 6= 0. We can always choose u0 < 0 and v0 > 0. In these conditions, the number of suitable integers k is bounded by: min (⌊ 2m sr′ ⌋ , ⌊ n s′r ⌋) and the number of ( k, w d ) is bounded by: ( 1 + min (⌊ 2m sr′ ⌋ , ⌊ n s′r ⌋)) ×2 ⌊ 1 d ( m p q + n p′ q′ )⌋ And finally, the total number of couples ( k, w d ) is at most: ( min (⌊ 2m sr′ ⌋ , ⌊ n s′r ⌋) + 1 ) × ( 2 ⌊ 1 d ( m p q + n p′ q′ )⌋) + 2 min (⌊ m sd′ ⌋ , ⌊ 1 p ( m p q + n p′ q′ )⌋) + min (⌊ 2m sr′ ⌋ , ⌊ n s′r ⌋) That is, ( min (⌊ 2m sr′ ⌋ , ⌊ n s′r ⌋) + 1 ) × ( 2 ⌊ 1 d ( m p q + n p′ q′ )⌋) + 2 ⌊ m sd′ ⌋ + min (⌊ 2m sr′ ⌋ , ⌊ n s′r ⌋) So, nl(P,m,n) ≤ nlmax(P,m,n) Lemma 4.7. If we consider a Farey vertex V = ( p q , p′ q′ ) of order (m,n), then q ∨q′ ≤ 2mn. Proof. ( p q , p′ q′ ) ∈ FV (m,n) ⇒   ∃((u,u′),(v,v′),(w,w′)) ∈ J−m,mK2 × J−n,nK2 ×Z2 u′v −uv′ 6= 0 such that: ( p q , p′ q′ ) = ( |w′v −wv′| |uv′ −u′v| , |wu′ −w′u| |uv′ −u′v| ) . 114 D. Khoshnoudirad / J. Algebra Comb. Discrete Appl. 3(2) (2016) 105–123 So, q ∨q′ | |uv′ −u′v|. In particular, q ∨q′ ≤ 2mn. In particular, ss′d′ ≤ 2mn. Proposition 4.8. Let ( p q , p′ q′ ) ∈ FV (m,n).   A(m,n,p,q,p′,q′) = min (⌊ 2m sr′ ⌋ , ⌊ n s′r ⌋) B(m,n,p,q,p′,q′) = 2 ⌊ 1 d ( m p q + n p′ q′ )⌋ C(m,n,p,q,p′,q′) = A(m,n,p,q,p′,q′)×B(m,n,p,q,p′,q′) A′(m,n) = ∑ 0≤p 0,∀(m,n) ∈ (N\{0,1})2, A′(m,n) ≤ Km2n2(m + n) ln2(mn). Proof. A′(m,n) ∑ 0≤p 1 in the sums in order to use the corollary 4.4 (and the same for d′s′). ∃K > 0,∀(m,n) ∈ (N\{0,1})2, A′(m,n) ≤ 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) A′(m,n) ≤ 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) ∃K > 0,∀(m,n) ∈ (N\{0,1})2, 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) ≤ K′′n2m3 ln2(mn) Proposition 4.10. ∃K > 0,∀(m,n) ∈ (N\{0,1})2, B′(m,n) ≤ Km2n2(m + n). Proof. B′(m,n) = ∑ 0≤p 0,∀(m,n) ∈ (N\{0,1})2, C′(m,n) ≤ Km2n2(m + n) ln(mn). Proof. C′(m,n) = ∑ 0≤p 0,∀(m,n) ∈ (N\{0,1})2, C ′ 1(m,n) ≤ mn 2mn∑ d′=1 b2mn d′ c∑ s=1 b2mn d′s c∑ s′=1 d′s∑ r=1 b n s′c≥r d′s′∑ r′=1 b2ms c≥r′ ⌊ min( d ′s r , d ′s′ r′ ) ⌋∑ d=1 1 ss′d′ ≤ mn 2mn∑ d′=1 b2mn d′ c∑ s=1 b2mn d′s c∑ s′=1 d′s∑ r=1 b n s′c≥r d′s′∑ r′=1 b2ms c≥r′ d′s′ r′ 1 ss′d′ ≤ mn 2mn∑ d′=1 b2mn d′ c∑ s=1 b2mn d′s c∑ s′=1 d′s∑ r=1 b n s′c≥r d′s′∑ r′=1 b2ms c≥r′ d′s′>1 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 C ′ 2(m,n). 4.3. Cases of the vertices for which p = 0 or p′ = 0 Now, we treat the two simple cases where p = 0 or p′ = 0 of the proposition 4.6: Proposition 4.12. ∃K > 0,∀(m,n) ∈ N∗2, ∑ p′ q′∈Fn nl ( 0, p′ q′ ) + ∑ p q ∈Fm nl ( p q ,0 ) ≤ Kmn(m2 + n2). Proof. • [( 1 + ⌊ n q′ ⌋) (2m + 1) ] ≤ 2m + 1 + 2nm + n ≤ 5mn + 1 ∑ p′ q′∈Fn nl ( 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 nl ( p q ,0 ) ≤ ∑ p q ∈Fm [( 1 + 2 ⌊ m q ⌋) (n + 1) ] ≤ ∑ p q ∈Fm (5mn + 1) ≤ (5mn + 1) |Fm| 120 D. Khoshnoudirad / J. Algebra Comb. Discrete Appl. 3(2) (2016) 105–123 We know [12] that |Fn| = 1 + n∑ k=1 ϕ(k) ∼ +∞ n2 2ζ(2) So there exists K > 0 such that∑ p′ q′∈Fn nl ( 0, p′ q′ ) + ∑ p q ∈Fm nl ( p q ,0 ) ≤ Kmn(m2 + n2). 4.4. Case of the vertices for which min (⌊ 2m sr′ ⌋ , ⌊ n s′r ⌋) = 0 It remains to handle the case of the vertices for which min (⌊ 2m sr′ ⌋ , ⌊ n s′r ⌋) = 0. At this stage of our research, we are not yet able to bound this term D′(m,n). 5. Conclusion of this strategy By the strategy of the Farey vertices, we obtained some interesting results: • We applied the fundamental formulas of Graph Theory to the Farey diagram of order (m,n). • We found a good upper bound for the degree of a Farey vertex. • We made relations between the Farey diagrams and the linear diophantine equations by solving explicit systems of linear diophantine equations. However, at the moment, this method does not help to improve the known upper bound for the cardinality of the Farey vertices. We suggest two possible ways of future research for bounding this term D′(m,n). • Either ∃K > 0,∀(m,n) ∈ (N\{0,1})2, D′(m,n) ≤ Km2n2(m + n) ln2(mn). In that case, we could conclude that : ∃K > 0,∀(m,n) ∈ (N\{0,1})2, ∣∣∣FV (m,n)∣∣∣ ≤ Km2n2(m + n) ln2(mn) • Otherwise we have to search a bound whose order is between 5 and 6. If the optimal order is 6, that would strenghten the importance of our work [17], as it would probably mean that the order of the cardinality of Farey vertices is a homogeneous polynomial of order 6. Acknowledgment: Many thanks to Grégory Apou for his help. I am greatly thankful to the referee for his remarks, helps, propositions of improvements. And many thanks to the members of the team of J. Algebra Comb. Discrete Appl., for their patience. 121 D. Khoshnoudirad / J. Algebra Comb. Discrete Appl. 3(2) (2016) 105–123 References [1] D. M. Acketa, J. D. Žunić, On the number of linear partitions of the (m,n)−grid, Inform. Process. Lett. 38(3) (1991) 163–168. [2] T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976. [3] T. Asano, N. Katoh, Variants for the Hough transform for line detection, Comput. Geom. 6(4) (1996) 231–252. [4] C. A. Berenstein, D. Lavine, On the number of digital straight line segments, IEEE Trans. Pattern Anal. Mach. Intell. 10(6) (1988) 880–887. [5] J. M. Chassery, D. Coeurjolly, I. Sivignon, Duality and geometry straightness, characterization and envelope, Discrete geometry for computer imagery, 1–16, Lecture Notes in Comput. Sci., 4245, Springer, Berlin, 2006. [6] J. M. Chassery, A. Montanvert, Geometrical representation of shapes and objects for visual percep- tion, Geometrical representation of shapes and objects for visual perception. In: Geometric Reasoning for Perception and Action, vol. 708 of LNCS, pp. 163–182. Springer, Berlin, 1993. [7] D. Coeurjolly, Algorithmique et géométrie discrete pour la caractérisation des courbes et des surfaces, Phd-Thesis, Université Lumière-Lyon II, 2002. [8] D. Coeurjolly, I. Sivignon, F. Dupont, F. Feschet, J. -M. Chassery, On digital plane preimage struc- ture, Discrete Appl. Math. 151(1-3) (2005) 78–92. [9] A. Daurat, M. Tajine, M. Zouaoui, About the frequencies of some patterns in digital planes applica- tion to area estimators, Comput. Graph. 33(1) (2009) 11–20. [10] I. Debled-Rennesson, Etude et reconnaissance des droites et plans discrets, PhD thesis, Université Louis-Pasteur, 1995. [11] E. Domenjoud, D. Jamet, D. Vergnaud, L. Vuillon, Enumeration formula for (2,n)−cubes in discrete planes, Discrete Appl. Math. 160(15) (2012) 2158–2171. [12] G. H. Hardy, E. M. Wright, Introduction À La Théorie Des Nombres, Traduction de François Sauvageot, Springer, 2007. [13] P. Haukkanen, J. K. Merikoski, Asymptotics of the number of threshold functions on a two- dimensional rectangular grid, Discrete Appl. Math. 161(1-2) (2013) 13–18. [14] A. Hatcher, Topology of Numbers, Unpublished book, in preparation; see http://www.math.cornell.edu/~hatcher/TN/TNpage.html. [15] W. Hou, C. Zhang, Parallel-beam ct reconstruction based on mojette transform and compressed sensing, Int. J. Comput. Electr. Eng. 5(1) (2013) 83–87. [16] Y. Kenmochi, L. Buzer, A. Sugimoto, I. Shimizu, Digital planar surface segmentation using local geometric patterns, Discrete geometry for computer imagery, 322–333, Lecture Notes in Comput. Sci., 4992, Springer, Berlin, 2008. [17] D. Khoshnoudirad, Farey lines defining Farey diagrams and application to some discrete structures, Appl. Anal. Discrete Math. 9(1) (2015) 73–84. [18] A. O. Matveev, Relative blocking in posets, J. Comb. Optim. 13(4) (2007) 379–403. Corrigendum: arXiv:math/0411026. [19] A. O. Matveev, A note on Boolean lattices and Farey sequences, Integers. 7(A20) (2007) 1–7. [20] A. O. Matveev, A note on Boolean lattices and Farey sequences II, Integers. 8(A24) (2008) 1–8. [21] A. O. Matveev, Neighboring fractions in Farey subsequences, arXiv:0801.1981, 2008. [22] M. D. Mcllroy, A note on discrete representation of lines, AT&T Tech. J. 64(2) (1985) 481–490. [23] E. Remy, E. Thiel, Structures dans les sphéres de chanfrein, RFIA. (2000) 483–492. [24] E. Remy and E. Thiel, Exact medial axis with euclidean distance, Image Vision Comput. 23(2) (2005) 167–175. [25] I. Svalbe, A. Kingston, On correcting the unevenness of angle distributions arising from integer ratios lying in restricted portions of the Farey plane, Combinatorial image analysis, 110–121, Lecture Notes in Comput. Sci., 3322, Springer, Berlin, 2005. [26] E. Szemerédi, W. T. Trotter Jr., Extremal problems in discrete geometry, Combinatorica. 3(3-4) 122 http://dx.doi.org/10.1016/0020-0190(91)90240-I http://dx.doi.org/10.1016/0020-0190(91)90240-I http://dx.doi.org/10.1016/0925-7721(95)00023-2 http://dx.doi.org/10.1016/0925-7721(95)00023-2 http://dx.doi.org/10.1109/34.9109 http://dx.doi.org/10.1109/34.9109 http://dx.doi.org/10.1007/11907350_1 http://dx.doi.org/10.1007/11907350_1 http://dx.doi.org/10.1007/11907350_1 http://dx.doi.org/10.1007/3-540-57132-9_10 http://dx.doi.org/10.1007/3-540-57132-9_10 http://dx.doi.org/10.1007/3-540-57132-9_10 https://tel.archives-ouvertes.fr/tel-00167370/document https://tel.archives-ouvertes.fr/tel-00167370/document http://dx.doi.org/10.1016/j.dam.2005.02.022 http://dx.doi.org/10.1016/j.dam.2005.02.022 http://dx.doi.org/10.1016/j.cag.2008.11.001 http://dx.doi.org/10.1016/j.cag.2008.11.001 http://www.loria.fr/~debled/TheseDebledRennesson.pdf http://www.loria.fr/~debled/TheseDebledRennesson.pdf http://dx.doi.org/10.1016/j.dam.2012.05.029 http://dx.doi.org/10.1016/j.dam.2012.05.029 http://dx.doi.org/10.1016/j.dam.2012.08.012 http://dx.doi.org/10.1016/j.dam.2012.08.012 https://www.math.cornell.edu/~hatcher/TN/TNpage.html https://www.math.cornell.edu/~hatcher/TN/TNpage.html ~ http://dx.doi.org/10.7763/IJCEE.2013.V5.669 http://dx.doi.org/10.7763/IJCEE.2013.V5.669 http://dx.doi.org./10.1007/978-3-540-79126-3_29 http://dx.doi.org./10.1007/978-3-540-79126-3_29 http://dx.doi.org./10.1007/978-3-540-79126-3_29 http://dx.doi.org/10.2298/AADM150219008K http://dx.doi.org/10.2298/AADM150219008K http://dx.doi.org/10.1007/s10878-006-9028-2 http://www.emis.de/journals/INTEGERS/papers/h20/h20.pdf http://www.emis.de/journals/INTEGERS/papers/i24/i24.pdf http://arxiv.org/abs/0801.1981 http://dx.doi.org/10.1002/j.1538-7305.1985.tb00359.x http://pageperso.lif.univ-mrs.fr/~edouard.thiel/print/2000-rfia12-remy-thiel.pdf http://dx.doi.org/10.1016/j.imavis.2004.06.007 http://dx.doi.org/10.1016/j.imavis.2004.06.007 http://dx.doi.org/10.1007/978-3-540-30503-3_9 http://dx.doi.org/10.1007/978-3-540-30503-3_9 http://dx.doi.org/10.1007/978-3-540-30503-3_9 http://dx.doi.org/10.1007/BF02579194 http://dx.doi.org/10.1007/BF02579194 D. Khoshnoudirad / J. Algebra Comb. Discrete Appl. 3(2) (2016) 105–123 (1983) 381–392. [27] G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, Cambridge University Press, 1995. [28] E. Thiel, Les distances de chanfrein en analyse d’images:fondements et applications,PhD thesis, Université Joseph-Fourier-Grenoble I, 1994. [29] E. Thiel, A. Montanvert, Chamfer masks: discrete distance functions, geometrical properties and optimization, Pattern Recognition, 1992. Vol. III. Conference C: Image, Speech and Signal Analysis, Proceedings., 11th IAPR International Conference on. IEEE, 1992. [30] R. Tomás, From Farey sequences to resonance diagrams, Phys. Rev. ST Accel. Beams. 17(1) (2014) 014001-1–014001-3. [31] 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. [32] V. Trifonov, L. Pasqualucci, R. Dalla-Favera, R. Rabadan, Fractal-like distributions over the rational numbers in high-throughput biological and clinical data, Sci. Rep. 1(591) (2011). 123 http://dx.doi.org/10.1007/BF02579194 http://dx.doi.org/10.1007/BF02579194 https://hal.inria.fr/file/index/docid/46382/filename/tel-00005113.pdf https://hal.inria.fr/file/index/docid/46382/filename/tel-00005113.pdf http://dx.doi.org/10.1109/ICPR.1992.201971 http://dx.doi.org/10.1109/ICPR.1992.201971 http://dx.doi.org/10.1109/ICPR.1992.201971 http://dx.doi.org/10.1103/PhysRevSTAB.17.014001 http://dx.doi.org/10.1103/PhysRevSTAB.17.014001 http://arxiv.org/abs/1406.6991 http://arxiv.org/abs/1406.6991 http://dx.doi.org/doi:10.1038/srep00191 http://dx.doi.org/doi:10.1038/srep00191 Introduction Preliminaries Fundamental properties and lemmas Bound for the degree of a farey vertex Conclusion of this strategy References