Prove using Dyck naturals: for $n \in \mathbb{N}_{+}$ and big enough $k \in \mathbb{N}_{+}$, $p_{k-1} < \cdots < np_{k-a_{n}}$ (a is A073093)

Question

While conducting research in connection with arXiv:2102.02777 ("Recursive Prime Factorizations: Dyck Words as Numbers"), I noticed certain interesting patterns, one of which inspired the following conjecture:

Conjecture. Let $n \in \mathbb{N}_{+}$. Then there exists a positive integer $k_{\text{min}}$ such that for all integers $k \ge k_{\text{min}}$,

$p_{k-1} < \cdots < np_{k-a_{n}},$

where $a_{n}$ is the number of prime power divisors of $n$, i.e., $a$ is Sequence A073093 in the Online Encyclopedia of Integer Sequences (OEIS).

Example. Let $n = 10$, and let $k$ be an integer greater than or equal to $k_{\text{min}} = 51$. Then I conjecture that

$p_{k-1} < 2p_{k-2} < 3p_{k-2} < 4p_{k-3} < 5p_{k-2} < 6p_{k-3} < 7p_{k-2} < 8p_{k-4} < 9p_{k-3} < 10p_{k-3}$.

These inequalities are very easily obtained by observing trends in the Dyck naturals (ibid., Definition 2.9). Let $\theta(n)$ be that finite subsequence of $\mathbb{N}$ such that every term in the subsequence is represented by a Dyck natural of semilength $n$. For example, $\theta(4) = (5,6,8,9,16)$, since the Dyck natural representations of the terms in $\theta(4)$ are $()()(()), (())(()), (()(())), ()((()))$ and $(((())))$ respectively, all of these being words of semilength 4. I call this "the stripe of semilength 4" (ibid., Definition 5.1), which may be somewhat misleading, as "semilength" refers not to the stripe itself but to the lengths of the recursive prime factorizations (RPFs) of the terms in the stripe. With that caveat, let us consider stripes $\theta(0)$ through $\theta(10)$, looking for patterns in the $i$th term of each stripe having an $i$th term.

$\theta(0) = (0)$

$\theta(1) = (1)$

$\theta(2) = (2)$

$\theta(3) = (3,4)$

$\theta(4) = (5,6,8,9,16)$

$\theta(5) = (7, 10, 12, 15, 18, 25, 27, 32, 64, 81, 256, 512, 65536)$

$\theta(6) = (11, 14, 20, 21, 24, 30, 35, 36, 45, 48, 49, 50, 54, \ldots,\theta(6)_{\text{last}})$

$\theta(7) = (13, 22, 28, 33, 40, 42, 55, 60, 63, 70, 72, 77, 80, \ldots,\theta(7)_{\text{last}})$

$\theta(8) = (17, 26, 39, 44, 56, 65, 66, 84, 91, 99, 110, 112, 120, \ldots,\theta(8)_{\text{last}})$

$\theta(9) = (19, 34, 51, 52, 78, 85, 88, 117, 119, 130, 132, 168, 176, \ldots,\theta(9)_{\text{last}})$

$\theta(10) = (23, 38, 57, 68, 95, 102, 104, 133, 153, 156, 170, 208, 209, \ldots,\theta(10)_{\text{last}})$

That should be enough to give an idea of the pattern inspiring the conjecture. For example, the pattern as manifested in the first terms is obvious: for stripes $\theta(k)$ where $k \ge 2$, the first term in $\theta(k)$ is the prime number $p_{k-1}$. Also, for stripes $\theta(k)$ where $k \ge 3$, the second term is the semiprime $2p_{k-2}$. And for stripes $\theta(k)$ where $k \ge 8$, the third term is the semiprime $3p_{k-2}$.

For the next revision of arXiv:2102.02777, I plan to include a modification of the conjecture expressing the idea in terms of recursive prime factorizations. But obviously a theorem would be better than a conjecture (if the conjecture is true, of course), so I wonder whether someone could point the way. The conjecture would read like this:

Conjecture. Let $n \in \mathbb{N}_{+}$. Then there exists a positive integer $k_{\text{min}}$ such that for all positive integers $k \ge k_{\text{min}}$, the $n$th term in stripe $\theta(k)$ is equal to $np_{k-a_{n}}$, where $p_{i}$ is the $i$th prime number and $a_{n}$ is the number of prime power divisors of $n$, i.e., $a$ is Sequence A073093 in the Online Encyclopedia of Integer Sequences (OEIS).

I asked a related question on Math Stackexchange (https://math.stackexchange.com/questions/4033170/how-might-i-prove-or-disprove-this-conjecture-7p-k-2-8p-k-4-for-all-k), and users @lulu and @QC_QAOA were extremely helpful, but I cannot immediately see how their proof strategies could be adapted to prove that the patterns apply to Dyck naturals (which doesn't invalidate their strategies, because I did not constrain the form of the desired answer to involve Dyck naturals). A different kind of approach seems more suitable, something in the realm of formal language theory (perhaps using combinatorics on words?), since this is all coming from patterns observed in Dyck language representations of numbers. Can anyone out there help me find a proof? And does someone out there see a pattern in the sequence of $k_{\text{min}} = (2,3,8,8,13,13,35,35,10,14,\ldots)$? Any help would be greatly appreciated...

Answer 1

The conjecture is true, and the actual sequence $(a_n)$ is irrelevant. Indeed, by the prime number theorem, we have $$\lim_{k\to\infty}\frac{p_{k-a}}{p_{k-b}}=1\qquad\text{for any} \qquad a,b\in\mathbb{N}.$$ Hence the fraction exceeds $1-1/n$ for $k>k_0(a,b,n)$, and the result follows.