6
$\begingroup$

I try to prove that for every positive integers $m\ge n$, the following product is an integer: $$\prod_{k=0}^{n-1}\frac{2^{2^m}-2^{2^k}}{2^{2^n}-2^{2^k}}.$$

But no luck.

$\endgroup$
1
  • 1
    $\begingroup$ @SamHopkins I must confess that, at first, I also didn't read the "is an integer" part of your question. XD $\endgroup$ Apr 14 at 0:16

1 Answer 1

13
$\begingroup$

The fraction equals $$\prod_{k=0}^{n-1}\frac{2^{2^m-2^k}-1}{2^{2^n-2^k}-1},$$ hence it suffices to show that $$\prod_{k=0}^{n-1}\frac{x^{2^m-2^k}-1}{x^{2^n-2^k}-1}\in\mathbb{Z}[x].$$ The numerator and the denominator factor into cyclotomic polynomials. If $a(d)$ and $b(d)$ are the multiplicties of the $d$-th cyclotomic polynomial in the numerator and the denominator, then it suffices to show that $a(d)\geq b(d)$. Now $a(d)$ equals the number of $k\in\{0,\dotsc,n-1\}$ such that $d\mid 2^m-2^k$, while $b(d)$ equals the number of $k\in\{0,\dotsc,n-1\}$ such that $d\mid 2^n-2^k$.

Let us write $d=2^r e$ with $e$ odd. If $r\geq n$, then $a(d)=b(d)=0$, and we are done. Assume now that $r<n$. Then $a(d)$ is the number of $k\in\{r,\dotsc,n-1\}$ such that $e\mid 2^{m-k}-1$, while $b(d)$ is the number of $k\in\{r,\dotsc,n-1\}$ such that $e\mid 2^{n-k}-1$. Let $s$ be the multiplicative order of $2$ modulo $e$. Then $a(d)$ is the number of elements of $\{m-n+1,\dotsc,m-r\}$ divisible by $s$, while $b(d)$ is the number of elements of $\{1,\dotsc,n-r\}$ divisible by $s$. Hence $$a(d)=\left\lfloor\frac{m-r}{s}\right\rfloor-\left\lfloor\frac{m-n}{s}\right\rfloor,\qquad b(d)=\left\lfloor\frac{n-r}{s}\right\rfloor,$$ and we are left with proving $$\left\lfloor\frac{m-r}{s}\right\rfloor\geq\left\lfloor\frac{m-n}{s}\right\rfloor+\left\lfloor\frac{n-r}{s}\right\rfloor.$$ However, this is clear from the inequality $\lfloor u+v\rfloor\geq\lfloor u\rfloor+\lfloor v\rfloor$, and we are done.

$\endgroup$
4
  • 2
    $\begingroup$ Thanks a lot for this very clear answer. $\endgroup$
    – joaopa
    Apr 14 at 2:41
  • 1
    $\begingroup$ @joaopa Thanks for the nice question. It was a pleasure answering it. $\endgroup$
    – GH from MO
    Apr 14 at 2:44
  • 1
    $\begingroup$ Sice note: since $\lfloor u+v\rfloor \le \lfloor u\rfloor + \lfloor v\rfloor + 1$, it seems this proof shows that the rational-function-that's-actually-a-polynomial is in fact squarefree as well. $\endgroup$ Apr 14 at 21:11
  • $\begingroup$ @GregMartin Excellent point! $\endgroup$
    – GH from MO
    Apr 14 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.