3
$\begingroup$

Crossposted from math.stackexchange since there are no answers there.

Consider the sequence $a_k$ of $3$-smooth numbers (see OEIS A003586), i.e. the elements of:

$$S = \{ 2^i 3^j : i,j \ge 0 \}$$

in increasing order.

Further define:

$$ [a_n]! = \prod_{k = 1}^n a_k$$

Similarly to the property $\frac{(m+n)!}{m!n!} \in \mathbb{Z}$, is the following statement true:

$$\frac{[a_{m+n}]!}{[a_m]![a_n]!} \in S$$

and if so, how is it possible to prove it? And then, is it possible to generalize it to any couple of prime numbers other than $2$ and $3$?

Note, that in general the property does not always hold for $n$-smooth numbers. For example, given the sequence $b_k$ of $5$-smooth numbers, $[b_{17}]!$ is not a multiple of $[b_2]![b_{15}]!$ (from a comment in the original post).

Improve this question
$\endgroup$
3
  • $\begingroup$ Do you have some reason for believing the statement is true? $\endgroup$
    – Gerry Myerson
    Commented Jul 10, 2023 at 12:43
  • $\begingroup$ @GerryMyerson not really. I have just verified all cases with $m+n \le 98$ and $m \le 12$ using OEIS A022328 and A022329. A conterexample seems more difficult with $m \gt 12$ from numerical tests. Maybe I can try to interpolate the above sequences to have a stronger evidence. $\endgroup$
    – Fabius Wiesner
    Commented Jul 10, 2023 at 13:55
  • $\begingroup$ Interpolation gives $\nu_2([a_n]!) \approx 0.4n^{1.56}$ and $\nu_3([a_n]!) \approx 0.2n^{1.6}$ so the statement seems plausible. $\endgroup$
    – Fabius Wiesner
    Commented Jul 10, 2023 at 15:25

1 Answer 1

Reset to default
2
$\begingroup$

The statement is false in general. Define $b_N$ to be the exponent of the $2$-part of $[a_N]!$; that is, the largest power of $2$ dividing $[a_N]!$. We can estimate $b_N$ as follows. Note that $2^x 3^y, x,y \in \mathbb{Z}_{\geq 0}, xy \ne 0$ appears in $S$ with index at most $N$ if and only if

$$\displaystyle x \log(2) + y \log(3) \leq \log N.$$

It follows that

$$\displaystyle b_N = \sum_{i=0}^{\left\lfloor \frac{\log N}{\log 2} \right \rfloor} i \left(\left \lfloor \frac{\log N}{\log 3} - i \frac{\log 2}{\log 3}\right\rfloor \right). $$

Reindexing (it is helpful to draw a picture here) and using symmetry, we obtain a convenient expression for $2b_N$:

$$\displaystyle 2b_N = \sum_{i=0}^{\left \lfloor \frac{\log N}{\log 2} \right \rfloor} i \left \lfloor \frac{\log N}{\log 3} \right \rfloor + O((\log N)^2).$$

Evaluating, this gives the asymptotic formula

$$\displaystyle b_N \sim \frac{(\log N)^3}{4 (\log 2)^2 \log 3}.$$

In order for $\frac{[a_{M+N}]!}{[a_M]! [a_N]!} \in \mathbb{Z}$, we require

$$\displaystyle b_M + b_N \leq b_{M+N}.$$

In particular, asymptotically we must have

$$\displaystyle (\log M)^3 + (\log N)^3 \leq (\log(M+N))^3.$$

Now set $M = N$. We then require

$$\displaystyle 2 (\log N)^3 \leq (\log N + \log 2)^3,$$

and it is clear that this inequality fails for $N$ sufficiently large.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Note that 'sufficiently large' N here for the inequality is roughly N=14; i.e., just outside of OP's tested range. Of course, the fact that the formula is asymptotic means that that's not exact, but it suggests that a counterexample might not be too far outside of the already-tested range. $\endgroup$
    – Steven Stadnicki
    Commented Jul 10, 2023 at 17:56
  • 1
    $\begingroup$ I'm confused starting with the first inequality. The number of lattice points in the first quadrant satisfying $x\log 2+y\log 3\le \log N$ is on the order of $(\log(N))^2$. But it seems like there should be $N$ of them exactly according to the "if and only if" claim? My conjecture: this answer assumes $[a_n]!$ is defined as the product of the 3-smooth numbers less than $n$, whereas the OP defines them as the product of the first $n$ 3-smooth numbers?? $\endgroup$
    – aorq
    Commented Jul 10, 2023 at 18:00
  • $\begingroup$ Thank you. However I think that $N$ must be replaced with $a_N$ in the first inequality. Then, if we use the rough asympotics at the OEIS page for $a_N$, the last inequality holds. $\endgroup$
    – Fabius Wiesner
    Commented Jul 10, 2023 at 21:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .