Are all GCD-Sequences Divisor Product sequences too?

Question

I attended a math camp few years ago, where I studied two types of sequences called GCD-Sequences and Divisor Product sequences. They are defined as follows;

---

GCD-Sequences: Define an integer sequence $A=\left(a_n\right)_{n\geq 1}$ to be a GCD Sequence if $$\gcd(a_m, a_n) = a_{\gcd(m, n)}.$$

---

Divisor Product Sequences: Define an integer sequence $A=\left(a_n\right)_{n\geq 1}$ to be a Divisor-Product Sequence if there exists an integer sequence $B=\left(b_n\right)_{n\geq 1}$ such that for every index $n$: $$a_n = \prod_{d \mid n} b_d.$$

---

Recently, I revisited these sequences, and found many results. I remember my friend from the program told me, that;

all GCD-Sequences might be divisor product sequences.

I can't find a way to prove this. Here are two examples of GCD-Sequences. As it turns out, they are also divisor products sequences; \begin{align*} &a_n=n^k\text{ for some }k\in\mathbb{Z}^+\\ &a_n=\alpha^n-\beta^n\text{ for }\alpha,\beta\in\mathbb{Z}^+ \end{align*}

This seems like a good research problem. If anyone has an idea or possibly a proof, you can share. Here's a formal problem statement;

---

Let $(a_n)_{n\geq 1}$ be a sequence of positive integers such that for all $m,n\in \mathbb{Z}^+,$ we have $a_{\gcd(m,n)}=\gcd(a_m,a_n),$ then there exists a sequence $(b_n)_{n\geq 1}$ such that for all positive integers $n,$ we have; $$a_n=\prod_{d\mid n}{b_d}.$$

---

Answer 1

Welcome to MSE!

I had actually solved this after attending Ross Program a few years ago. I had saved the proof. It was a beautiful proof using $p$-adic valuations. Here's how I proved it.

Suppose that $(a_n)$ is a sequence that satisfies the property of a GCD-Sequence. Fix a prime number $p.$ We define the sequence $(i^p_n)_{n\geq 1}$ as; $$i^p_n=v_p(a_n)$$ for all $n\geq 1.$ The sequence $(i^p_n)$ is dependent on the prime number $p.$

Since $(a_n)_{n\geq 1}$ is a GCD-Sequence, for all $m,n\geq 1,$ we have; $$\gcd(a_m,a_n)=a_{\gcd(m,n)}.$$

Now, consider the $p$-adic valuation of both the sides. The $p$-adic valuation of the left side is $v_p(\gcd(a_m,a_n))=\min(v_p(a_m),v_p(a_n)).$

But since $v_p(a_m)=i^p_m$ $\text{and }v_p(a_n)=i^p_n,$ we have that; $$\min(v_p(a_m),v_p(a_n))=\min(i^p_m,i^p_n).$$

The $p$-adic valuation of the right side is $v_p(a_{\gcd(m,n)})=i^p_{\gcd(m,n)}.$ Since both the sides are equal, their $p$-adic valuations are also equal. Thus, for all $m,n\geq 1$, we have that; $$i^p_{\gcd(m,n)}=\min(i^p_m,i^p_n).$$ We will call this property the GCD-Closure Property of the sequence $(i^p_n)_{n\geq 1}.$

Consider the set of all the integers in the sequence $(i^p_n).$ We can rearrange (and remove repetitions) of these integers to get a sequence $(j^p_n).$ The sequence contains $(j^p_n)$ has all the terms of the sequence $(i^p_n)$ such that; $$0\leq j^p_1<j^p_2<\cdots$$

Now let $j^p_k$ be a term of $(j^p_n),$ where $k$ is a fixed positive integer. We define the set $S^p_k$ as the set of all positive integers $l$ such that $i^p_l=j^p_k.$ (Note that $S^p_k$ is dependent on both $k$ and $p$ which are fixed). This can be written as; $$S^p_k=\{l\mid i^p_l=j^p_k\}.$$

Now, we will prove that the set $S^p_k$ is the set of all positive multiples of a minimal element. To see this, we will first show that the GCD of any two positive integers $s,t\in S^p_k$ is also a positive integer in $S^p_k.$

Since $s,t\in S^p_k,$ we can say that; $$i^p_s=j^p_k$$ $$\text{and }i^p_t=j^p_k.$$

By the GCD-Closure Property, we can infer that; \begin{align*} i^p_{\gcd(s,t)} &=\gcd(i^p_s,i^p_t)\\ &=\gcd(j^p_k,j^p_k)\\ &=j^p_k. \end{align*}

Hence, we have that $i^p_{\gcd(s,t)}=j^p_k,$ so $\gcd(s,t)$ must also be an element of the set $S^p_k.$

This proves that the GCD of any two elements of $S^p_k$ in also in $S^p_k.$ Now let $m^p_k$ be the minimum element of $S^p_k,$ then for all $l\in S^p_k,$ we have $\gcd(m^p_k,l)\in S^p_k.$

But then $\gcd(m^p_k,l)\leq m^p_k$ and since $m^p_k$ is the least element of $S^p_k,$ we have that; $$\gcd(m^p_k,l)=m^p_k$$ $$\implies m^p_k\mid l.$$

Hence, all the elements of $S^p_k$ are multiples of the minimum element $m^p_k.$ Now, we will no longer have $k$ fixed.

We have created another sequence $(m^p_k),$ we will now prove that this sequence satisfies $m^p_1\mid m^p_2\mid m^p_3\mid \cdots$.

Let $k<l$ be two positive integers. Then we have by the GCD-Closure Property that; \begin{align*} i^p_{\gcd(m^p_k,m^p_l)} &=\min(i^p_{m^p_k},i^p_{m^p_l})\\ &=\min(j^p_k,j^p_l)\\ &=j^p_k. \end{align*}

Hence, we have that $i^p_{\gcd(m^p_k,m^p_l)}=j^p_k.$ But then, we have that $\gcd(m^p_k,m^p_l)\in S^p_k,$ and thus; \begin{align*} m^p_k &\mid \gcd(m^p_k,m^p_l)\\ \implies m^p_k &\mid m^p_l. \end{align*}

Hence, in the sequence $(m^p_k)$, each term divides each later term. Moreover, the sequence begins with $1,$ since it is obvious that $m^p_1=1.$

Now, we let $m$ be a positive integer. We know that $m^p_1=1,$ and $m^p_1\mid m.$ Hence, for any number $l\in \mathbb{Z}^+,$ there exists some largest term of the sequence $(m^p_n)$ which divides $m$.

Then we have $\gcd(m^p_k,m)=m^p_k,$ by the GCD-Closure Property, we have; \begin{align*} \min\left(i^p_{m^p_k},i^p_m\right) &=i^p_{\gcd(m^p_k,m)}\\ &=i^p_{m^p_k}\\ &=j^p_k\\ \implies i^p_{m}&\geq j^p_k. \end{align*}

On the other hand, we have $m^p_{k+1}\nmid m.$ Then, we have; \begin{align*} \gcd(m^p_{k+1},m)&\mid m^p_{k+1}\\ \text{and }\gcd(m^p_{k+1},m)&\neq m^p_{k+1}\\ \implies \gcd(m^p_{k+1},m)&<m^p_{k+1}. \end{align*}

Now, applying the GCD-Closure Property again gives us; \begin{align*} \min\left(i^p_{m^p_{k+1}},i^p_{m}\right) &=i^p_{\gcd(m^p_{k+1},m)}\\ &<j^p_{k+1}\\ \implies i^p_{m}&<j^p_{k+1}. \end{align*}

All the values in the sequence $(i^p_k)$ are among $j^p_1,j^p_2,\dots,$ and $j^p_k\leq i^p_{m}<j^p_{k+1},$ so we have $i^p_m=j^p_k.$

Hence, if $k$ is the largest number such that $m^p_k$ divides $m,$ then we have $i^p_m=j^p_k.$

Now, we finally prove the statement. We recall that all of these sequences were defined on basis of the chosen prime $p.$ We will now ``unfix'' the prime $p$ which was fixed till now.

Let $n$ be fixed, then we define the term $b_n$ by defining all of its $p$-adic valuations for prime nubers $p.$

We define $v_p(b_n)$ as follows; $$ v_p(b_n)= \begin{cases} j^p_1 & \text{if }n=1 \\ j^p_k-j^p_{k-1} & \text{if } n=m^p_k \text{ for } k\in \mathbb{Z} \\ 0 & \text{if }n\notin (m^p_k) \\ \end{cases} $$

This way, if $p$ is a prime number, then we consider the following expression; \begin{align*} v_p\left(\prod_{d\mid n}{b_d}\right) &=\sum_{d\mid n}{v_p(b_d)}. \end{align*}

Many terms of this sequence are $0$ if $b_d$ is not one of the terms in $m^p_1,m^p_2,\dots$ (note that this sequence depends on the prime $p$).

Hence, all the numbers $d$ that matter in the summation are the ones that are a term in the sequence $m^p_1,m^p_2,\dots$

So if $m^p_k$ is the largest number in the sequence that divides $n.$ Then, $d=m^p_1,m^p_2,\dots,m^p_k$ are the only values in the summation that matter. We have that; \begin{align*} v_p\left(\prod_{d\mid n}{b_d}\right) &=\sum_{d\mid n}{v_p(b_d)}\\ &=\sum_{m^p_i\mid n}{v_p(b_{m^p_i})}\\ &=\sum^k_{i=1}{v_p(b_{m^p_i})}. \end{align*}

We will simplify this last summation by noting that; $$ v_p(b_n)= \begin{cases} j^p_1 & \text{if }n=1 \\ j^p_k-j^p_{k-1} & \text{if } n=m^p_k \text{ for } k\in \mathbb{Z} \\ 0 & \text{if }n\notin (m^p_k) \\ \end{cases} $$

This gives us; \begin{align*} v_p\left(\prod_{d\mid n}{b_d}\right) &=\sum^k_{i=1}{v_p(b_{m^p_i})}\\ &=v_p(b_{m^p_1})+\sum^k_{i=2}{v_p(b_{m^p_i})}\\ &=j^p_1+\sum^k_{i=2}{j^p_i-j^p_{i-1}}\\ &=j^p_1+\sum^k_{i=2}{\left(j^p_i-j^p_{i-1}\right)}\\ &=j^p_1+\left(j^p_k-j^p_{1}\right)\\ &=j^p_k. \end{align*}

We know that $m_k^p$ is the largest number in the sequence $(m^p_k)$ that divides $n,$ thus we have $j^p_k=i^p_n.$ Hence; \begin{align*} v_p\left(\prod_{d\mid n}{b_d}\right) &=j^p_k\\ &=i^p_n. \end{align*}

But $i^p_n$ is the $p$-adic valuation of $a_n.$ Hence, we have; $$v_p\left(\prod_{d\mid n}{b_d}\right)=i^p_n=v_p(a_n).$$

This proves that for all prime numbers $p,$ the $p$-adic valuations of; $$\prod_{d\mid n}{b_d}\text{ and }a_n$$ are all equal.

Hence, we have; $$\prod_{d\mid n}{b_d}=a_n,$$ and thus we have found an integer sequence $(b_n)$ such that for all $n\geq 1,$ we have; $$a_n=\prod_{d\mid n}{b_d}.$$

Hope this helps :)

Answer 2

See the paper Strong divisibility and lcm-sequences, Andrzej Nowicki, which shows that $b_n = \frac{\text{lcm}(a_1, a_2, ..., a_n)}{\text{lcm}(a_1, a_2, ..., a_{n-1})}$ which is always an integer.