Verifying an intuition about a sequence of consecutive integers

152 Views Asked by At

Let $x>0$ be the first integer in a sequence and $n>0$ be the number of consecutive integers in the sequence.

For example, if $x=12,n=3$ the sequence would be $\{ 12,13,14\}$

Let $v_p(x,n)$ be the highest power of $p$ that divides $x+i$ where $0 \le i < n$

Is it true that:

$$\frac{(x+n-1)!}{(x-1)!} \div \prod\limits_{p | \frac{(x+n-1)!}{(x-1)!}} p^{v_p(x,n)} \le (n-1)! $$

Below is my argument. Please let me know if anything is unclear or if I have made any mistakes.

I have attempted to make the argument as short as possible and as clear as possible.

(1) Let $r = \frac{(x+n-1)!}{(x-1)!} \div \prod\limits_{p | \frac{(x+n-1)!}{(x-1)!}} p^{v_p(x,n)}$

(2) For each distinct $p$ that divides $r$, there exists $k_{p,0}$ such that $p^{v_p(x,n)} | (x+ k_{p,0})$ and there exists a distinct integer $k_{p,1}$ such that $p^t | (x+k_{p,1})$ and $t \le v_p(x,n)$ and $p^t | (k_{p,0} - k_{p,1})$ and $p^t$ is the greatest power of $p$ that divides $(x + k_{p,1})$

(3) If $p$ divides $\frac{r}{p^t}$, then we can repeat this process $w$ times until we have $p \nmid \frac{r}{\prod\limits_{1 \le j \le w}p^{t_j}}$ and we have $w$ distinct integers: $k_{p,1}, \dots, k_{p,w}$ that map to $w$ distinct integers less than $n$ where for each: $p^{t_j} | abs(k_{p,0} - k_{p,j})$

(4) We can repeat this same argument for each distinct $p$ that divides $r$ until $r$ divided by all these primes $= 1$

(5) Since each distinct prime $p$ that divides $r$ also distinctly divides $(n-1)!$, it follows that $r \le (n-1)!$

1

There are 1 best solutions below

0
On BEST ANSWER

As didgogns's question comment states, $\prod\limits_{p | \frac{(x+n-1)!}{(x-1)!}} p^{v_p(x,n)}$ is just $\operatorname{lcm}(x, x + 1, \ldots, x + n - 1)$. This is because the largest exponent of each prime that divides the $\operatorname{lcm}$ is the maximum of the exponents of $p$ among the $x+i$ for $0 \le i \lt n$, which is your definition of $v_p(x,n)$.

Your argument has the right idea, but there's a fairly subtle flaw in it. I didn't notice this flaw myself until I was almost finished writing my original answer, and I then spent some time figuring out how to resolve it. The issue is that although your $k_{p,j}$ for $1 \le j \le w$ are all distinct integers, so their differences of $k_{p,0} - k_{p,j}$ are as well, they will often include both positive and negative integers. Thus, mapping them to $\left| k_{p,0} - k_{p,j}\right|$ so they're all positive integers will result in duplicates.

You therefore haven't shown you can state in your (5) that "... each distinct prime $p$ that divides $r$ also distinctly divides $(n-1)!$, ...". That step implicitly assumes the number of factors of $p$ among the duplicated integers is less than or equal to that of those positive integers $\le n - 1$ which are congruent to $k_{p,0}$ modulo $p$ which weren't included. My alternate proof below shows this to always be true.

Also with your (2), there is one very minor mistake and I have a couple of suggestions where you wrote

... there exists a distinct integer $k_{p,1}$ such that $p^t | (x+k_{p,1})$ and $t \le v_p(x,n)$ and $p^t | (k_{p,0} - k_{p,1})$ and $p^t$ is the greatest power of $p$ that divides $(x + k_{p,1})$

The definition of $v_p(x,n)$ gives $t \le v_p(x,n)$, so this doesn't need to be stated. Also, to keep the wording simpler, you could use the $p$-adic order function where $t = \nu_p(x + k_{p,1})$ is defined to be the highest exponent $t$ such that $p^t \mid x+k_{p,1}$. Finally, it's $t$, not $p^t$, which is the greatest power of $p$ that divides $(x + k_{p,1})$.

As such, your text shown above could be written more succinctly as

... there exists a distinct integer $k_{p,1}$ where, with $t = \nu_p(x+k_{p,1})$, then $p^t \mid (k_{p,0} - k_{p,1})$

Note a somewhat different version of your proof is one which uses a direct argument instead of recursion, with this being longer but possibly being a bit simpler to read & understand for some people. In particular, your (2) to (5) could be replaced with the following.


First, for simpler algebra, let

$$\begin{equation}\begin{aligned} f(x,n) & = \frac{(x+n-1)!}{(x-1)!} \\ & = \prod_{i=0}^{n-1}(x + i) \end{aligned}\end{equation}\tag{1}\label{eq1A}$$

$$m = \operatorname{lcm}(x, x + 1, \ldots, x + n - 1) \tag{2}\label{eq2A}$$

which means, from your (1) and what I discussed at the top, we have

$$r = \frac{f(x,n)}{m} \tag{3}\label{eq3A}$$

For any prime $p \mid r$, there's at least one $i$ where

$$\nu_p(x + i) = \nu_p(m) = q \tag{4}\label{eq4A}$$

Choose one of these $i$ and call it $j$. Next,

$$\begin{equation}\begin{aligned} \nu_p(r) & = \nu_p\left(\prod_{i = 0, \, i \neq j}^{n-1}(x + i)\right) \\ & = \sum_{i = 0, \, i \neq j}^{n-1}\nu_p(x + i) \end{aligned}\end{equation}\tag{5}\label{eq5A}$$

For each $i \neq j$ where $\nu_p(x + i) = s \gt 0$, we have $p^s \mid x + j$ and $p^s \mid x + i$ so $p^s \mid (x + j) - (x + i)$, giving

$$\nu_p((x + j) - (x + i)) = \nu_p(j - i) \ge \nu_p(x + i) \tag{6}\label{eq6A}$$

Thus, the $p$-adic order of the product of $x + i$ for all $0 \le i \le n - 1$ where $p \mid j - i$ is less than or equal to that of the products of $j - i$. However, using $\left|j - i\right|$ to map these to positive integers will in most cases involve duplicates due to the set of $j - i$ values being a mixture of positive and negative integers. Nonetheless, the $p$-adic order of the product of the duplicates is less than or equal to that of the product of the positive multiples of $p$ less than $n$ which aren't being used.

To see this, the $\left|j - i\right|$ values for $i \lt j$ are $p$, $2p$, $\ldots$, $up$ for some $u \ge 0$, and for $i \gt j$ they are $p$, $2p$, $\ldots$, $vp$ for some $v \ge 0$. Since $p \mid r$, at least one of $u$ and $v$ are non-zero, so choose the larger value (or either one if they are the same), say WLOG $u$. Start with those values. If $v$ is $0$, then we're done. Otherwise, map each of those other values to be $up$ larger, so they then go up to $(u + v)p$. Note since for some $0 \le i_1, i_2 \le n - 1$, with $i_2 \gt i_1$, we have $up = j - i_1$ and $vp = i_2 - j$ so $(u + v)p = i_2 - i_1 \le n - 1$. Since the integers with no factor of $p$ don't affect the $p$-adic order of the product, we can include them in the product, giving that what we want to prove is

$$\begin{equation}\begin{aligned} & \sum_{i=up+1}^{(u+v)p}{\nu_p(i)} \ge \sum_{i=1}^{vp}{\nu_p(i)} \\ & \sum_{i=1}^{(u+v)p}{\nu_p(i)} - \sum_{i=1}^{up}{\nu_p(i)} \ge \nu_p((vp)!) \\ & \nu_p(((u+v)p)!) - \nu_p((up)!) - \nu_p((vp)!) \ge 0 \end{aligned}\end{equation}\tag{7}\label{eq7A}$$

To show this, consider the following alternate form of Legendre's formula

$$\nu_p(n!) = \frac{n - s_p(n)}{p - 1} \tag{8}\label{eq8A}$$

where $s_p(n)$ is the digit sum of $n$ in base $p$ (FYI, for a different, fairly intuitive explanation of this, please see Hands-on argument for base p version of Legendre's formula). Using \eqref{eq8A} in the left side of \eqref{eq7A} gives

$$\begin{equation}\begin{aligned} & \nu_p(((u+v)p)!) - \nu_p((up)!) - \nu_p((vp)!) \\ & = \frac{(u+v)p - s_p((u+v)p)}{p - 1} - \frac{up - s_p(up)}{p - 1} - \frac{vp - s_p(vp)}{p - 1} \\ & = \frac{(u+v)p - up - vp - s_p((u+v)p) + s_p(up) + s_p(vp)}{p - 1} \\ & = \frac{s_p(up) + s_p(vp) - s_p((u+v)p)}{p - 1} \end{aligned}\end{equation}\tag{9}\label{eq9A}$$

To show for any positive integers $A$ and $B$ that

$$s_p(A) + s_p(B) \ge s_p(A + B) \tag{10}\label{eq10A}$$

(note this is asked about in Digit Sum Inequality Equation), first note if there are no carries, then \eqref{eq10A} is an equality. Otherwise, for each carry, the digit being carried from is reduced by $p$ and the next higher-power digit is increased by $1$, for a net decrease in the digit sum of $p - 1$, so the right side then becomes that much less.

This confirms \eqref{eq7A} is true, which leads to

$$\nu_p(r) \le \nu_p((n-1)!) \implies p^{\nu_p(r)} \mid (n - 1)! \tag{11}\label{eq11A}$$

Combining \eqref{eq11A} for all the distinct primes $p \mid r$ gives

$$r \mid (n-1)! \implies r \le (n - 1)! \tag{12}\label{eq12A}$$