of 19

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]

7 views
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
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]
Transcript
  ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.00924 J. Algebra Comb. Discrete Appl.3(2)  •  105–123Received: 30 October 2015Accepted: 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 indiscrete 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 hadonly handled the case of the Farey vertices for which  min  2 msr ′  ,   ns ′ r   ∈  N ∗ . In fact we hadto distinguish two cases:  min  2 msr ′  ,   ns ′ r   ∈  N ∗ and  min  2 msr ′  ,   ns ′ r   = 0 . However, wehighlight the correct results of the srcinal paper and its applications. We underline that in thiswork, we still brought several contributions. These contributions are: applying the fundamentalformulas of Graph Theory to the Farey diagram of order  ( m,n ) , finding a good upper bound for thedegree of a Farey vertex and the relations between the Farey diagrams and the linear diophantineequations. 2010 MSC:  05A15, 05A16, 05A19, 05C30, 68R01, 68R05, 68R10 Keywords:  Combinatorial number theory, Farey diagrams, Theoretical computer sciences, Discrete planes, Diophantineequations, Arithmetical geometry, Combinatorial geometry, Discrete geometry, Graph theory in computersciences 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:  m 3 n 3 ( 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  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 combinatoricsis not sufficient if we want to have a deeper understanding of the combinatorics of the  ( m,n ) -cubes, andwe 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  2 msr ′  ,   ns ′ r   ∈ N ∗ , remains correct. Butthe case where  min  2 msr ′  ,   ns ′ 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   − m,m   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 )  ∈   − m,m  ×  − n,n  × 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  F  n  =  0   pq ,  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  ⌊ ⌋  denotes the integer part,  ⌈ ⌉  denotes the upper integer part, and     denotes thefractional 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 |  denotesthe 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  F  m,n  denote the set  =   0 ,m − 1  ×  0 ,n − 1  .  U  m,n denotes the set of all  ( m,n ) -cubes. Furthermore, the proposition 3 of  [9] shows that the set of   ( m,n ) -cubesof the discrete planes  P  α,β,γ   only depends of   ( α,β  ) , and is denoted by  C  m,n,α,β . Definition 2.8.  [ 9  ](  ( m,n ) -pattern) Let   m  and   n  be two positive integers. A  ( m,n ) -pattern is a map w : F  m,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   M m,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   w i,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 ′ )  ∈ F  m,n =  ⌊ α ( i + i ′ ) + β  (  j  +  j ′ ) + γ  ⌋−⌊ αi + βj  + γ  ⌋  for all   ( i ′ ,j ′ )  ∈ F  m,n where   p α,β,γ  ( i,j ) =  ⌊ αi + βj  + γ  ⌋  and   ( i,j,p α,β,γ  ( i,j )) ,  ( i,j )  ∈ Z 2   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 : w i,j  ( α,β,γ  )( k,l ) =  ⌊ αk  + βl ⌋  if    αi + βj  + γ    < C  α,βk,l ⌊ αk  + βl ⌋ + 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   w i,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  ∈   0 ,mn − 1  , 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 )  ∈ F  m,n   ≤  mn . Corollary 2.11.  [ 9  ] 1. ∀ ( α,β,γ  )  ∈  [0 , 1] 2 × R ,w 0 , 0 ( α,β,γ  ) =  w 0 , 0 ( α,β,  γ   ) 108  D. Khoshnoudirad / J. Algebra Comb. Discrete Appl. 3(2) (2016) 105–123  2. ∀ ( α,β,γ  )  ∈  [0 , 1] 2 × R , ∀ ( i,j )  ∈ Z 2 , w i,j ( α,β,γ  ) =  w 0 , 0 ( α,β,αi + βj  + γ  )=  w 0 , 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   C  m,n,α,β . Corollary 2.12.  [ 9  ]  Let   O  be a Farey connected component, then   O  is a convex polygon and if   p 1 ,p 2 ,p 3 are distinct vertices of the polygon   O , then : •  for any point   p  ∈ O , C  m,n,p  =  C  m,n,p 1  ∪C  m,n,p 2  ∪C  m,n,p 3 •  for any point   p  ∈ O  in the interior of the segment of vertices   p 1  and   p 2 , C  m,n,p  =  C  m,n,p 1  ∪C  m,n,p 2 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   U  m,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 atmost 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 combinatoricson this set of vertices, we are going to study the properties of the Farey lines passing through a Fareyvertex. 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
Related Search
Advertisements
Related Docs
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks