Analogy to Legendre's formula for $N!$

145 Views Asked by At

Suppose $A$ is a product of primes $p\le x$. For any $m$ let $A(m)$ be the largest such $A$ dividing $m$.

Proposition 1. For any $N$ sufficiently large, $$\prod_{i=1}^NA(i) < \prod_{p\le x}p^{\frac{N}{p-1}}.$$

Question. Can someone supply a proof for Proposition 1?

Remarks. It may be the case that this holds for all $N$ instead of all $N$ sufficiently large. It seems like it may be possible to prove a uniform bound in $i\le N$: $$A(i) \le \prod_{p\le x}p^{\frac{1}{p-1}},$$ but I haven't been able to do so (or rule it out).

For context, this is the first inequality in Lemma 1 of Erdős' paper A Generalization of a Theorem of Besicovitch. Erdős mentions this is analogous to Legendre's formula for $N!$, but I am not sure if that is helpful for considering how to prove Proposition 1.


Here is a more precise definition of $A(m)$ that I am using. (Note that Erdős writes "$A$ is an integer composed entirely of primes not greater than $x$", so what follows is the interpretation I gave to this.) Consider the prime factorization of $m$, $$ m = p_1^{a_1}p_2^{a_2}\dots p_r^{a_r}, $$ where the primes $p_j$ are distinct for $j=1,\dots,r$, and the exponents $a_j\ge 1$. Let $$A(m) = \prod_{j : p_j \le x} p_j^{a_j}.$$

1

There are 1 best solutions below

1
On BEST ANSWER

For any $p\le x$, the exponent of $p$ in the prime factorization of $A(m)$ is the same as the exponent of $p$ in $m$ (this exponent is often denoted $v_p(m)$). Essentially, $A(m)$ is just $m$ after discarding any prime factors that are $>x$. In particular, $A(mn) = A(m) A(n)$, in other words $A$ is completely multiplicative.

So the LHS $\prod_{i=1}^N A(i)$ is equivalent to $A(\prod_{i=1}^N i) = A(N!)$. This is the connection to Legendre's formula.

The exact value of $A(N!)$ is just $\prod_{p\le x} p^{v_p(N!)}$, and Legendre's formula gives $$v_p(N!) = \Big\lfloor \frac{N}p \Big\rfloor + \Big\lfloor \frac{N}{p^2} \Big\rfloor + \cdots.$$

Compare this to the infinite geometric series $$\frac{N}{p-1} = \frac{N}{p} + \frac{N}{p^2} + \cdots,$$

and the inequality $v_p(N!) < N/(p-1)$ is obvious. The Proposition follows by multiplying out all of the terms (which are necessarily positive, retaining the strict inequality). It is indeed uniform for all $N>1$, not just sufficiently large $N$.