If $q$ an odd prime, is the inequality $2^n(q!)^n\mid 2(nq\text{)}!,\text{ where } n=1,2,3,4,... $ true?

Question

Because of my research work in mathematics I have been led to believe that the following is true:

Let $q$ an odd prime. Then $$2^n(q!)^n\mid 2(nq\text{)}!,\text{ where }n=1,2,3,4,... $$ This result feels true (and I also checked it with several examples) but I've failed to prove it. I tried to prove the (easier?) relation $$(q!)^n\mid(nq)!,\text{ where } n=1,2,3,4,...$$ (because it seems to be enough for my purposes, despite not being completely satisfactory) by induction, and I also tried to use $p$-adic valuations and Legendre formula, but to no avail.

Probably this is simple, but I'm missing something. Can someone help me, please?

Answer 1

Using Legendre's formula works for your second result but you need the identity

$$ \left\lfloor \frac{nx}{y}\right\rfloor \geq n\left\lfloor \frac{x}{y}\right\rfloor$$

which might be well known, but also you can prove by noting that $\left\lfloor \frac{x}{y}\right\rfloor = \frac{x}{y}-\epsilon$ for $0\leq \epsilon < 1$, so that

$$ \left\lfloor \frac{nx}{y}\right\rfloor = \left\lfloor n\left\lfloor \frac{x}{y}\right\rfloor - n\epsilon\right\rfloor = n\left\lfloor \frac{x}{y}\right\rfloor - \left\lceil n\epsilon \right\rceil $$

From Legendre's formula this gives that $(q!)^n \vert (nq)!$.

For the stronger statement, we can focus on just the $2$-adic valuation. We can do

$$ v_2((nq)!) -v_2((q!)^n) = \sum_{i=1}^\infty \left\lfloor \frac{nq}{2^i}\right\rfloor - \sum_{i=1}^\infty n\left\lfloor \frac{q}{2^i}\right\rfloor$$

and note that for each $i$, the difference of sequential terms in the sum is positive, so we can focus on $i=1$: $$ v_2((nq)!) - v_2((q!)^n) \geq \lfloor \frac{nq}{2}\rfloor -n\lfloor\frac{q}{2}\rfloor$$ We know that $\lfloor \frac{q}{2}\rfloor = \frac{q-1}{2}$, and $\lfloor\frac{nq}{2}\rfloor \geq \frac{nq-1}{2}$ (since $q$ is odd, but $n$ might not be) so

$$\lfloor \frac{nq}{2}\rfloor -n\lfloor\frac{q}{2}\rfloor \geq \frac{n-1}{2}$$

which gives you that $2^{\frac{n-1}{2}}(q!)^n \vert (nq)!$ for odd $q$.

The other thing you can do is consider $k$ such that $2^{k-1} < q < 2^k$. Then for the $k$th term, we have that

$$\lfloor \frac{nq}{2^k}\rfloor -n\lfloor\frac{q}{2^k}\rfloor = \lfloor\frac{nq}{2^k}\rfloor$$

By construction, you know that $\frac{q}{2^k} \geq \frac{1}{2}$. So $\frac{nq}{2^k} \geq \frac{n}{2}$, meaning $\lfloor\frac{nq}{2^k}\rfloor \geq \frac{n-1}{2}$.

I think if you combine these two results you get $v_2((nq)!) - v_2((q!)^n) \geq n-1$, which gives your result.

Please double-check my reasoning and proofs before trusting this.

Answer 2

We only need the assumption that $q$ is odd and greater than $1$ for this result to hold.

For your easier problem of proving $(q!)^n \mid (qn)!$, note that the quotient $$ \frac{(qn)!}{(q!)^n}=\binom{qn}{q,q,\dots,q} $$ is a multinomial coefficient. This can be proven to be an integer by induction on the upper index the multi-dimensional version of Pascal's rule, or combinatorially. In particular, the integer $(qn)!/(q!)^n$ counts the number of sequences of length $qn$, where each entry is an element of $\{1,\dots,n\}$, such that each number appears exactly $q$ times in the sequence. I will refer to this set of sequences as $S$, so $|S|=(qn)!/(q!)^n$.

You want to prove $2^n (q!)^n \mid 2(qn)!$, which is equivalent to proving $2^{n-1}$ divides $|S|$. It suffices to a find a group $G$ with cardinality $2^{n-1}$, together with a group action of $G$ on $S$, such that the action has no fixed points.

Partition $\{1,\dots,n\}$ into $\lfloor n/2\rfloor $ pairs of numbers of the form $\{2i-1,2i\}$ for $i\in \{1,\dots,\lfloor n/2\rfloor\}$. For each of these $i$, we define two operations $\newcommand{\Flip}{\text{Flip}}\newcommand{\Flop}{\text{Flop}}\Flip_i$ and $\Flop_i$ on $S$ as follows:

• $\Flip_i$ replaces all entries which are $2i-1$ with $2i$, and all entries which are $2i$ with $2i-1$.

• To compute $\Flop_i$, look at the $2q$ entries of $S$ which are either $2i-1$ or $2i$. Divide these into pairs $(a_1,b_1),(a_2,b_2),\dots,(a_q,b_q)$, such that these $2q$ entries appear in $S$ in the order $$ \dots a_1 \dots b_1 \dots a_2 \dots b_2 \dots\quad \cdots \quad\dots a_q\dots b_q \dots $$ For each $j\in \{1,\dots,q\}$, you either have $a_j=b_j$, or $a_j\neq b_j$. It cannot be the case that $a_j=b_j$ for all $j\in \{1,\dots,q\}$, because $q$ is odd. Therefore, there exists a smallest $j$ such that $a_j\neq b_j$. To perform $\Flop_i$, simply switch $a_j$ with $b_j$ for this smallest $j$.

It should be clear that $\Flip_i$ and $\Flop_i$ have order $2$, i.e. they are their own inverse. Furthermore, it is obvious that $\Flip$'s and $\Flop$'s with index $i$ commute with $\Flip$'s and $\Flop$'s with index $k$ for $k\neq i$, since they are acting on disjoint entries. It is less obvious is that $\Flip_i$ commutes with $\Flop_i$; this is true since $\Flip_i$ does not change which pairs $(a_j,b_j)$ are equal or not. Finally, it is obvious that neither $\Flip_i$ nor $\Flop_i$ have any fixed points. We conclude that all of the $\Flip$'s and $\Flop$'s generate a group action on $S$ with size $ 2^{2\lfloor n/2\rfloor } $. Since $2\lfloor n/2\rfloor\ge n-1$, we have found our group with cardinality $2^{n-1}$ acting on $S$ without fixed points, giving a partition of $S$ into $2^{n-1}$ equal groups. QED.