Convolution product of arithmetic functionsAn arithmetic function is a real-valued function whose domain is the set of positive integers. Define the convolution product of two arithmetic functions f and g to be the arithmetic function f ⋆ g, where ( f ⋆ g ) ( n ) = ∑ i j = n f ( i ) g ( j ) , and f ⋆ k = f ⋆ f ⋆ ⋯ ⋆ f ( k times ) .We say that two arithmetic functions f and g are dependent if there exists a nontrivial polynomial of two variables P ( x , y ) = ∑ i , j a i j x i y j with real coefficients such that P ( f , g ) = ∑ i , j a i j f ⋆ i ⋆ g ⋆ j = 0and say that they are independent if they are not dependent. Let p and q be two distinct primes and set f 1 ( n ) = { 1 if n = p , 0 otherwise ; f 2 ( n ) = { 1 if n = q , 0 otherwise . Prove that f 1 and f 2 are independent.My book says that f 1 ⋆ i ⋆ f 2 ⋆ j ( n ) = { 1 if n = p i q j 0 otherwise and the result follows from that, but how do they get that and how does the result follow from that?

Question

Convolution product of arithmetic functionsAn arithmetic function is a real-valued function whose domain is the set of positive integers. Define the convolution product of two arithmetic functions f and g to be the arithmetic function   f  ⋆  g, where  (  f  ⋆  g  )  (  n  )  =      ∑          i      j      =      n        f  (  i  )  g  (  j  )  ,   and       f          ⋆      k        =  f  ⋆  f  ⋆  ⋯  ⋆  f     (  k   times  )  .We say that two arithmetic functions f and g are dependent if there exists a nontrivial polynomial of two variables   P  (  x  ,  y  )  =      ∑          i      ,      j            a          i      j            x    i        y    j   with real coefficients such that  P  (  f  ,  g  )  =      ∑          i      ,      j            a          i      j            f          ⋆      i        ⋆      g          ⋆      j        =  0and say that they are independent if they are not dependent. Let p and q be two distinct primes and set      f    1    (  n  )  =      {                            1                    if           n          =          p          ,                                      0                    otherwise          ;                                  f    2    (  n  )  =      {                            1                    if           n          =          q          ,                                      0                    otherwise          .                        Prove that       f    1   and       f    2   are independent.My book says that      f          1              ⋆      i        ⋆      f          2              ⋆      j        (  n  )  =      {                            1                              if                              n          =                      p                          i                                            q                          j                                                            0                              otherwise                        and the result follows from that, but how do they get that and how does the result follow from that?

Aiden Villa · Accepted Answer

Step 1Let us write the convolution      f    1    ⋆      f    1    (  n  )  =      ∑          i      ⋅      j      =      n            f    1    (  i  )      f    1    (  j  )  .The function       f    1    (  i  )  ≠  0    ⟺    i  =  p, hence the only way to get a nonzero product inside the sum above is to put   i  =  j  =  p. This implies that      f    1          ⋆      2        (  n  )  =      {                            1          ,                          n          =                      p            2                    ,                                      0          ,                          n          ≠                      p            2                    .                        By using the same technique, you will get that      f    1          ⋆      k        (  n  )  =      {                            1          ,                          n          =                      p            k                    ,                                      0          ,                          n          ≠                      p            k                    .                        Can you now apply the same technique to       f    1          ⋆      k        ⋆      f    2          ⋆      p      ?

Answered question

Answer & Explanation

New Questions in Algebra II