Characterization of regular convolutions

In this paper, we present a characterization of regular convolution.

Збережено в:
Бібліографічні деталі
Дата:2018
Автор: Sagi S.
Формат: Стаття
Мова:English
Опубліковано: Інститут прикладної математики і механіки НАН України 2018
Назва видання:Algebra and Discrete Mathematics
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/188354
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Characterization of regular convolutions / S. Sagi // Algebra and Discrete Mathematics. — 2018. — Vol. 25, № 1. — С. 147-156. — Бібліогр.: 12 назв. — англ.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-188354
record_format dspace
spelling irk-123456789-1883542023-02-24T01:27:26Z Characterization of regular convolutions Sagi S. In this paper, we present a characterization of regular convolution. 2018 Article Characterization of regular convolutions / S. Sagi // Algebra and Discrete Mathematics. — 2018. — Vol. 25, № 1. — С. 147-156. — Бібліогр.: 12 назв. — англ. 1726-3255 2010 MSC: 06B10, 11A99. http://dspace.nbuv.gov.ua/handle/123456789/188354 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language English
description In this paper, we present a characterization of regular convolution.
format Article
author Sagi S.
spellingShingle Sagi S.
Characterization of regular convolutions
Algebra and Discrete Mathematics
author_facet Sagi S.
author_sort Sagi S.
title Characterization of regular convolutions
title_short Characterization of regular convolutions
title_full Characterization of regular convolutions
title_fullStr Characterization of regular convolutions
title_full_unstemmed Characterization of regular convolutions
title_sort characterization of regular convolutions
publisher Інститут прикладної математики і механіки НАН України
publishDate 2018
url http://dspace.nbuv.gov.ua/handle/123456789/188354
citation_txt Characterization of regular convolutions / S. Sagi // Algebra and Discrete Mathematics. — 2018. — Vol. 25, № 1. — С. 147-156. — Бібліогр.: 12 назв. — англ.
series Algebra and Discrete Mathematics
work_keys_str_mv AT sagis characterizationofregularconvolutions
first_indexed 2025-07-16T10:22:42Z
last_indexed 2025-07-16T10:22:42Z
_version_ 1837798642140839936
fulltext “adm-n1” — 2018/4/2 — 12:46 — page 147 — #149 Algebra and Discrete Mathematics RESEARCH ARTICLE Volume 25 (2018). Number 1, pp. 147–156 c© Journal “Algebra and Discrete Mathematics” Characterization of regular convolutions Sankar Sagi Communicated by V. V. Kirichenko Abstract. A convolution is a mapping C of the set Z+ of positive integers into the set P(Z+) of all subsets of Z+ such that, for any n ∈ Z+, each member of C(n) is a divisor of n. If D(n) is the set of all divisors of n, for any n, then D is called the Dirichlet’s convolution [2]. If U(n) is the set of all Unitary(square free) divisors of n, for any n, then U is called unitary(square free) convolution. Corresponding to any general convolution C, we can define a binary relation 6C on Z+ by ‘m 6C n if and only if m ∈ C(n)’. In this paper, we present a characterization of regular convolution. Introduction A convolution is a mapping C of the set Z+ of positive integers into the set P(Z+) of subsets of Z+ such that, for any n ∈ Z+, C(n) is a nonempty set of divisors of n. If C(n) is the set of all divisors of n, for each n ∈ Z+, then C is the classical Dirichlet convolution [2]. If C(n) = {d / d|n and (d, n d ) = 1}, then C is the Unitary convolution [1]. As another example if C(n) = {d / d|n and mk does not divide d for any m ∈ Z+}, then C is the k-free convolution. Corresponding to any convolution C, we can define a binary relation 6C in a natural way by m 6C n if and only if m ∈ C(n). 2010 MSC: 06B10, 11A99. Key words and phrases: semilattice, lattice, convolution, multiplicative, co- maximal, prime filter, cover, regular convolution. “adm-n1” — 2018/4/2 — 12:46 — page 148 — #150 148 Characterization of regular convolutions 6C is a partial order on Z+ and is called partial order induced by the convolution C [11], [12]. W. Narkiewicz [2] first proposed the concept of a regular convolution, and in this paper we present a lattice theoretic characterization of regular convolution and prove that the Dirichlet’s con- volution is the unique regular convolution that induces a lattice structure on (Z+,6C). 1. Preliminaries Let us recall that a partial order on a non-empty set X is defined as a bi- nary relation 6 on X which is reflexive (a 6 a), transitive (a 6 b, b 6 c =⇒ a 6 c) and antisymmetric (a 6 b, b 6 a =⇒ a = b) and that a pair (X,6) is called a partially ordered set (poset) if X is a non-empty set and 6 is a partial order on X. For any A ⊆ X and x ∈ X, x is called a lower(upper) bound of A if x 6 a (respectively a 6 x) for all a ∈ A. We have the usual notations of the greatest lower bound (glb) and least upper bound (lub) of A in X. If A is a finite subset {a1, a2, · · · , an}, the glb of A (lub of A) is denoted by a1 ∧ a2 ∧ · · · ∧ an or n ∧ i=1 ai (respectively by a1 ∨ a2 ∨ · · · ∨ an or n ∨ i=1 ai). A partially ordered set (X,6) is called a meet semi lattice if a ∧ b (=glb{a, b}) exists for all a and b ∈ X. (X,6) is called a join semi lattice if a ∨ b (=lub{a, b}) exists for all a and b ∈ X. A poset (X,6) is called a lattice if it is both a meet and join semi lattice. Equivalently, lattice can also be defined as an algebraic system (X,∧,∨), where ∧ and ∨ are binary operations which are associative, commutative and idempotent and satisfying the absorption laws, namely a ∧ (a ∨ b) = a = a ∨ (a ∧ b) for all a, b ∈ X; in this case the partial order 6 on X is such that a ∧ b and a ∨ b are respectively the glb and lub of {a, b}. The algebraic operations ∧ and ∨ and the partial order 6 are related by a = a ∧ b ⇐⇒ a 6 b ⇐⇒ a ∨ b = b. Throughout the paper Z+, N , and P denote the set of positive integers, the set of non-negative integers, and set of prime numbers respectively. Theorem 1 ([12]). Let 6C be the binary relation induced by convolution C. Then (1) 6C is reflexive if and only if n ∈ C(n). (2) 6C is transitive if and only, for any n ∈ Z+, ⋃ m∈C(n) C(m) ⊆ C(n). (3) 6C is always antisymmetric. “adm-n1” — 2018/4/2 — 12:46 — page 149 — #151 S. Sagi 149 Corollary 1 ([12]). The binary relation 6C induced by convolution C on Z+ is a partial order if and only if n ∈ C(n) and ⋃ m∈C(n) C(m) ⊆ C(n) for all n ∈ Z+. Definition 1 ([12]). Let X and Y be non-empty sets and R and S be binary relations on X and Y respectively. A bijection f : X → Y is said to be a relation isomorphism of (X,R) into (Y, S) if, for any elements a and b in X, aRb in X if and only if f(a)Sf(b) in Y. Theorem 2 ([12]). Let θ : Z+ → ∑ P N be the bijection defined by θ(n)(p) = the largest a in N such that pa divides n, Then a convolution C is multiplicative if and only if θ is a relation isomor- phism of (Z+,6C) onto ( ∑ P N,6C). Theorem 3 ([9], [10]). For any multiplicative convolution C, (Z+,6C) is a lattice if and only if (N,6p C ) is a lattice for each prime p. Now we state the following theorems on co-maximality and prime filters. Theorem 4 ([5]). Let (S,∧) be any meet semi lattice with smallest element 0 satisfying the descending chain condition. Also, suppose that every proper filter of S is prime. Then the following are equivalent to each other. (1) For any x and y ∈ S, x‖y =⇒ x ∧ y =0. (2) S − {0} is a disjoint union of maximal chains. (3) Any two incomparable filters of S are co-maximal. Theorem 5 ([5]). Let C be any multiplicative convolution such that (Z+,6C) is a meet semi lattice. Then any two incomparable prime filters of (Z+,6C) are co-maximal if and only if any two incomparable prime filters of (N,6p C ) are co-maximal, for each p ∈ P . Theorem 6 ([3]). Let p be a prime number. Then every proper filter in (N,6p C ) is prime if and only if [pa) is a prime filter in (Z+,6C) for all n > 0. Theorem 7 ([3]). A filter F of (Z+,6C) is prime if and only if there exists unique p ∈ P such that F p is a prime filter of (N,6p C ) and F q = N for all q 6= p in P and, in this case, F = {n ∈ Z+ | θ(n)(p) ∈ F p}. “adm-n1” — 2018/4/2 — 12:46 — page 150 — #152 150 Characterization of regular convolutions Theorem 8 ([3]). Let F be a filter of (Z+,6C). Then F = [pa) for some prime number p and a positive integer a which is join-irreducible in (Z+,6C). Definition 2. Any complex valued function defined on the set Z+ of pos- itive integers is called an arithmetical function. The set of all arithmetical functions is denoted by A. The following is a routine verification using the properties of addition and multiplication of complex numbers. Theorem 9. For any arithmetical functions f and g, define (f + g)(n) = f(n) + g(n) and (f · g)(n) = f(n)g(n) for any n ∈ Z+. Then + and · are binary operations on the set A of arithmetical functions and (A,+, ·) is a commutative ring with unity in which the constant map 0̄ and 1̄ are the zero element and unity element respectively. Definition 3. Let C be a convolution and f and g arithmetical functions and C be the field of complex numbers. Define fCg : Z+ → C by (fCg)(n) = ∑ d∈C(n) f(d)g( n d ). We can consider C as a binary operation, as defined above, on the set A of arithmetical functions. W.Narkiewicz proposed the following definition. Definition 4 ([2]). A convolution C is called regular if the following are satisfied. (1) (A,+, C) is a commutative ring with unity, where + is the point-wise addition. This ring will be denoted by AC . (2) If f and g are multiplicative arithmetical functions, then so is the product fCg (f is said to be multiplicative if f(mn) = f(m)f(n).) (3) The constant function 1̄, defined by 1̄(n) = 1 for all n ∈ Z+, is a unit in the ring AC . It can be easily verified that the arithmetical function e, defined by e(n) = { 1 if n = 1, 0 if n > 1 is the unity (the identity element with respect to the binary operation C). “adm-n1” — 2018/4/2 — 12:46 — page 151 — #153 S. Sagi 151 W. Narkiewicz proved the following two theorems. Theorem 10 ([2]). A convolution C is regular if and only if the following conditions are satisfied for any m,n and d ∈ Z+. (1) C is multiplicative convolution; i.e., (m,n)=1 ⇒ C(mn)=C(m)C(n). (2) d ∈ C(m) and m ∈ C(n) ⇔ d ∈ C(n) and m d ∈ C(n d ). (3) d ∈ C(n) ⇒ n d ∈ C(n). (4) 1 ∈ C(n) and n ∈ C(n). (5) For any prime number p and any a∈Z+, C(pa) = {1, pt, p2t, · · · , prt}, rt = a for some positive integer t and pt ∈ C(p2t), p2t ∈ C(p3t),. . . , p(r−1)t ∈ C(pa). Theorem 11 ([2]). Let K be the class of all decompositions of the set of non-negative integers into arithmetic progressions (finite or infinite) each containing 0 and no two progressions belonging to same decomposition have a positive integer in common. Let us associate with each p ∈ P , a member πp of K. For any n = pa11 pa22 · · · parr , where p1, p2, · · · , pr are distinct primes and a1, a2, · · · , ar ∈ N , define C(n) = {pb11 pb22 · · · pbrr | bi 6 ai, and bi and ai belong to the same progression in πpi .} Then C is a regular convolution and, conversely every regular convolution can be obtained in this way. From the above theorems, it is clear that any regular convolution C is uniquely determined by a sequence {πp}p∈P of decompositions of N into arithmetical progressions (finite or infinite) and we denote this by expression C ∼ {πp}p∈P . Definition 5. For any two elements a and b in a partially ordered set (X,6), a is said to be covered by b (b is a cover of a) if a < b and there is no c ∈ X such that a < c < b. This is denoted by a− < b. We note that θ : Z+ → ∑ P N defined by θ(a)(p) = the largest n in N such that pn divides a, for any a ∈ Z+ and p ∈ P is a bijection. 2. Main results In the following two theorems, we prove that any regular convolution C gives a meet semi lattice structure on (Z+,6C) and the convolution C is “adm-n1” — 2018/4/2 — 12:46 — page 152 — #154 152 Characterization of regular convolutions completely characterized by certain lattice theoretic properties of (Z+,6C). In particular Dirichlet’s convolution is the only regular convolution C which gives a lattice structure on (Z+,6C). Theorem 12. Let C be a convolution and 6C the relation on Z+ induced by C. Then C is a regular convolution if and only if the following properties are satisfied. (1) θ : (Z+,6C) → ∑ p∈P (N,6p C ) is a relation isomorphism. (2) (Z+,6C) is a meet semi lattice. (3) Any two incomparable prime filters of (Z+,6C) are co-maximal. (4) F is a prime filter of (Z+,6C) if and only if F = [pa) for some p ∈ P and a ∈ Z+. (5) For any m and n ∈ Z+, m− <C n =⇒ 1− <C n m 6C n. Proof. Suppose that C is a regular convolution. By Theorem 11, C ∼ {πp}p∈P , where each πp is a decomposition of N into arithmetic progressions (finite or infinite) in which each progression contains 0 and no positive integer belongs to two distinct progressions. For any a, b ∈ N and p ∈ P , let us write for convenience, 〈a < b〉 ∈ πp ⇐⇒ a and b belong to the same progression of πp. Since C is regular, C satisfies properties (1)–(5) of Theorem 10. From (2) and (4) of Theorem 10 and Corollary 1, it follows that 6C is a partial order on Z+. Since C is multiplicative, it follows from Theorem 2 that θ : Z+ → ∑ P N is an order isomorphism. Therefore the property (1) is satisfied. For simplicity and convenience, we shall write n̄ for θ(n). For each n ∈ Z+, n̄ is the element in the direct sum ∑ P N defined by n̄(p) = the largest a in N such that pa divides n. n 7→ n̄ is an order isomorphism of (Z+,6C) onto ∑ p∈P (N,6p C ), where for each p ∈ P , 6p C is the partial order on N defined by a 6 p C b if and only if pa ∈ C(pb). For any m and n ∈ Z+, let m ∧ n be the element in Z+ defined by m ∧ n(p) = { 0 if 〈m(p), n(p)〉 /∈ πp, min{m(p), n(p)} otherwise. for all p ∈ P . If 〈m(p), n(p)〉 ∈ πp, then m(p) 6p C n(p) or n(p) 6p C m(p) “adm-n1” — 2018/4/2 — 12:46 — page 153 — #155 S. Sagi 153 and hence m ∧ n(p) 6 m(p) and n(p) for all p ∈ P . Therefore m ∧ n is a lower bound of m and n in (Z+,6C). Let k be any other lower bound of m and n. For any p ∈ P , if 〈m(p), n(p)〉 ∈ πp, then, since k(p) 6p C m(p) and k(p) 6p C n(p), we have k(p) 6p C m ∧ n(p). If 〈m(p), n(p)〉 /∈ πp, then k(p) = 0 = m ∧ n(p). Thus k 6 m∧n. Therefore, m∧n is the greatest lower bound of m and n in (Z+,6C). Thus (Z+,6C) is a meet semi lattice and hence the property (2) is satisfied. To prove (3), by Theorem 5, it is enough if we prove that any two incomparable prime filters if (N,6p C ) are co-maximal for all p ∈ P . For any positive a and b, if a and b are incomparable in (N,6p C ), then 〈a, b〉 /∈ πp and hence a and b have no upper bound and therefore a∨ b does not exist in (N,6p C ). Also, each progression in πp is a maximal chain in (N,6p C ) and, for any a and b ∈ N , a and b are comparable if and only if 〈a, b〉 ∈ πp. Therefore (Z+,6p C ) is a disjoint union of maximal chains. Thus, by Theorem 4, any two incomparable prime filters of (N,6p C ) are co-maximal. Therefore, by Theorem 5, any two incomparable prime filters of (Z+,6C) are co-maximal. This proves (3). (4) follows from Theorem 6 and Theorem 7 and from the discussion made above. To prove (5), let m and n ∈ Z+ such that m− <C n. By Theorem 10 (3), we get that m n 6C n. Let us write n = pb11 pb22 · · · pbrr and m = pa11 pa22 · · · parr where p1, p2, · · · , pr are distinct primes and each bi > 0 such that 0 6 pi C ai 6 pi C bi. Since m 6= n, there exists i such that ai 6 pi C bi. Now, if aj 6 pi C bj for some j 6= i, then the element k = pc11 pc22 · · · pcrr , where cs = { as if s 6= i, bs if s = i. will be between m and n (that is, m <C k <C n) which is a contradiction. Therefore aj = bj for all j 6= i and hence n m = pai−bi i . “adm-n1” — 2018/4/2 — 12:46 — page 154 — #156 154 Characterization of regular convolutions Since 〈ai, bi〉 ∈ pipi , there exists t > 0 such that bi = ut and ai = vt for some u and v with v < u. Also, vt, (v + 1)t, · · · , ut are all in the same progression. Since m− <C n, it follows that u = v + 1 and hence n m = pti. Since 0− < t in (N,6pi C ), we get that 1− <C pt = n m 6C n. This proves (5). Conversely suppose that C satisfies properties (1)–(5), since [pa) is prime filter of (Z+,6C) for all p ∈ P and a ∈ Z+, by Theorem 6, every proper filter of (N,6p C ) is prime, for any p ∈ P . Since any two incomparable prime filters of (Z+,6C) are co-maximal, by Theorem 8 and Theorem 5, we get that (Z+,6p C ) is a disjoint union of maximal chains. Fix p ∈ P . Then Z+ = ∐ i∈I Yi where each Yi is a maximal chain in (Z+,6p C ) such that, for any i 6= j ∈ I, Yi ∩ Yj = φ and each element of Yi is incomparable with each element of Yj . Now, we shall prove that each Yi is an arithmetical progression (finite or infinite). Let i ∈ I. Since N is countable, Yi is at most countable. Also, since (N,6p C ) satisfies the descending chain condition, we can express Yi = {a1− <C a2− <C a3− < . . . } By using induction on r, we shall prove that ar = ra1 for all r. Clearly, this is true for r = 1. Assume that r > 1 and as = sa1 for all 1 6 s < r. Since (r − 1)a1 = ar−1− < ar in (N,6p C ), we have par−1− <C par in (Z+,6C) and hence, by condition (5), 1− <C par−ar−1 6C par . Therefore, 0 6= ar − ar−1 6 p C ar and hence ar − ar−1 ∈ Yi (since ar ∈ Yi). Also, since 0− < ar − ar−1 in (N,6p C ), we have ar − ar−1 = a1 and therefore ar = ar−1 + a1 = (r − 1)a1 + a1 = ra1. Hence, for any prime p “adm-n1” — 2018/4/2 — 12:46 — page 155 — #157 S. Sagi 155 and a ∈ Z+, C(pa) = {1, pt, p2t, · · · , pst} and st = a for some positive integers t and s and pt ∈ C(p2t), p2t ∈ C(p3t), · · · , p(s−1)t ∈ C(pa). The other conditions given in Theorem 10 are clearly satisfied. Thus, by Theorem 10, C is a regular convolution. Theorem 13. Let C be a convolution, then the following conditions are equivalent to each other. (1) (Z+,6C) is a lattice. (2) (N,6p C ) is a lattice for each p ∈ P . (3) (N,6p C ) is a totally ordered set for each p ∈ P . (4) For any p ∈ P and a and b ∈ N , a 6 p C b ⇐⇒ a 6 b. (5) For any n and m ∈ Z+, n 6C m ⇐⇒ n divides m. (6) C(n) = The set of positive divisors of n. Proof. Since C is regular, C ∼ {πp}p∈P . (1) =⇒ (2) follows from Theorem 3. (2) =⇒ (3) Let p ∈ P . Suppose that (N,6p C ) is a lattice. If πp contains two progressions, then choose an element a in one progression S and b in another progression T in πp. Since a 6 p C a∨ b and b 6p C a∨ b, a∨ b ∈ S∩T . A contradiction. Therefore πp contains only one progression, which must be N = {0 <p C 1 <p C 2 <p C 3 <p C . . . }. Thus (N,6p C ) is a totally ordered set. (3) =⇒ (4) It is trivial. (4) =⇒ (5) Let m and n ∈ Z+ and we write n = ∏r i=1 P ai i and m = ∏r i=1 P bi i , where p1, p2, · · · , pr are distinct primes and ai, bi ∈ N . Now, n divides m ⇐⇒ ai 6 bi for all 1 6 i 6 r ⇐⇒ ai 6 p C bi for all 1 6 i 6 r ⇐⇒ n 6C m. (5) =⇒ (6) For any n ∈ Z+, C(n) = {m ∈ Z+ | m 6C n} = {m ∈ Z+ | m divides n} = D(n). “adm-n1” — 2018/4/2 — 12:46 — page 156 — #158 156 Characterization of regular convolutions (6) =⇒ (1) If C = D, then 6C=6D and, for any n,m ∈ Z+, n ∧m = gcd{n,m} and n ∨m = lcm{n,m} in (Z+,6C). The above Theorem implies that the Dirichlet’s convolution D is the only regular convolution for which (Z+,6C) is a lattice. References [1] Cohen, E. Arithmetical functions associated with the unitary divisors of an integer. Math.Z.,74,66-80. 1960. [2] Narkiewicz, W. On a class of arithmetical convolutions. Collow.Math.,10,81- 94.1963. [3] Sankar Sagi. Characterization of Prime Filters in (Z+ ,6C). International Journal of Pure and Engineering Mathematics, Vol.3, No III, 2015. [4] Sankar Sagi. Characterization of Prime Ideals in (Z+ ,6D). European Journal of Pure and Applied Mathematics,Vol. 8, No.1(15-25)2015. [5] Sankar Sagi. Co-maximal Filters in (Z+ ,6C). International Journal of Mathemat- ics and it’s Applications,Vol.3, Issue 4-C, 2015. [6] Sankar Sagi. Filters in (Z+ ,6C) and (N ,6 p C ). Journal of Algebra, Number Theory: Advances and Applications, Vol 11, No.2 (93-101)2014. [7] Sankar Sagi. Ideals in (Z+ ,6D). Algeba and Discrete Mathematics, Vol 16(2013), Number 1, pp 107-115. [8] Sankar Sagi. Irreducible elements in (Z+ ,6C). International Journal of Mathe- matics and it’s Applications, Vol.3, Issue 4-C, 2015. [9] Sankar Sagi. Lattice Structures on Z+ Induced by Convolutions. European Journal of Pure and Applied Mathematics, Vol. 4, No.4(424-434) 2011. [10] Sankar Sagi, Lattice Theory of Convolutions, Ph.D. Thesis, Andhra University, Waltair, Visakhapatnam, India. 2010. [11] Swamy, U.M., Rao, G.C., Sita Ramaiah, V. On a conjecture in a ring of arithmetic functions. Indian J.pure appl.Math.,14(12)1983. [12] Swamy, U.M., Sankar Sagi. Partial orders induced by convolutions. International journal of Mathematics and Soft Computing,Vol. 2, No.1(25-33) 2012. Contact information Sankar Sagi Assistant Professor of Mathematics, College of Applied Sciences, Sohar, Sultanate of Oman E-Mail(s): sagi−sankar@yahoo.co.in Received by the editors: 09.10.2015 and in final form 03.02.2018.