Skip to main content
added 192 characters in body
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

Proof. Denote $c={\rm LCM}(a,b)$ and choose $\eta\in \Theta(c)$. Then we may find integers $k,\ell$ such that $w=\eta^k$, $g(w)=\eta^\ell$. So, the polynomial $P(x):=g(x^k)-x^\ell$ has a root $x=\eta$. Thus any element of $\Theta(c)$ is a root of $P$, since cyclotomics are irreducible. For any integer $t$ coprime to $c$ we have $\eta^c\in \Theta(c)$$\eta^t\in \Theta(c)$, so $g(w^t)-(g(w))^t=P(\eta^t)=0$. Try to choose $t$ such that $w=w^{t}$ but $g(w)^t\ne g(w)$, this would yield a contradiction. Our requirements for $t$ are, in other words: $a$ divides $t-1$; but $b$ does not divide $t-1$. Assume that $b$ does not divide $a$, and, if $a$ is odd, then $b$ does not divide $2a$. This allows to choose a prime $p$ such that $s:=\nu_p(b)$ (notation means that $p^s$ is the maximal power of $p$ which divides $b$) satisfies $s>\nu_p(a)$ and either $p$ is odd, or $p=2$ and $s\geqslant 2$. Using Chinese remainders theorem, choose $t$ be congruent to $1+p^{s-1}$ modulo $p^s$ and $t$ be congruent to 1 modulo $c/p^{s}$. Then $t$ is coprime with $c$, $a$ divides $t-1$ but $b$ does not divide $t-1$. This yields a necessary contradiction.

Let now $a>1$ be a divisor of $n$, choose $w\in \Theta(a)$ let. Let $g(w)\in \Theta(b)$. If $a$ is odd and $b$ is an even divisor of $2a$, then $-g(w)\in \Theta(b/2)$. Thus in all cases of Lemma 1 we have $f(w)=\pm w^m$ for certain $m$. Then this equation $f(x)=\pm x^m$ holds for all $x\in \Theta(a)$, since cyclotomics are still irreducible.

We proceed with proving the consistency of signs $\delta_i$ and exponents $m_i$. Let's start with signs. Assume that $\delta_i=-\delta_j$ for some $i<j$. This yields that $x^{m_i}+x^{m_j}$ is divisible by $1+x+\ldots+x^{n/(p_ip_j)-1}$. Substituting $x=1$, we get that $2$ is divisible $n/(p_ip_j)$, that is, $n=p_ip_j$ or $n=2p_ip_j$. In the latter case, if $1<i<j$, then replacing the pair $i<j$ to $1<i$ or $1<j$ in the above argument, we get a contradiction. So, $n=p_ip_j$ or $n=4p_j$. TheseIf $p_1=2$ and $n=2p_2$, then the signs may be chosen consistently because $-1=x$ on $T(2)$. The cases are to be considered separately.$n=pq$ with odd primes $p\ne q$ and $n=4p$ with odd prime $p$ are to be considered separately, this is done at the end of this answer.

Proof. Denote $c={\rm LCM}(a,b)$ and choose $\eta\in \Theta(c)$. Then we may find integers $k,\ell$ such that $w=\eta^k$, $g(w)=\eta^\ell$. So, the polynomial $P(x):=g(x^k)-x^\ell$ has a root $x=\eta$. Thus any element of $\Theta(c)$ is a root of $P$, since cyclotomics are irreducible. For any integer $t$ coprime to $c$ we have $\eta^c\in \Theta(c)$, so $g(w^t)-(g(w))^t=P(\eta^t)=0$. Try to choose $t$ such that $w=w^{t}$ but $g(w)^t\ne g(w)$, this would yield a contradiction. Our requirements for $t$ are, in other words: $a$ divides $t-1$; but $b$ does not divide $t-1$. Assume that $b$ does not divide $a$, and, if $a$ is odd, then $b$ does not divide $2a$. This allows to choose a prime $p$ such that $s:=\nu_p(b)$ (notation means that $p^s$ is the maximal power of $p$ which divides $b$) satisfies $s>\nu_p(a)$ and either $p$ is odd, or $p=2$ and $s\geqslant 2$. Using Chinese remainders theorem, choose $t$ be congruent to $1+p^{s-1}$ modulo $p^s$ and $t$ be congruent to 1 modulo $c/p^{s}$. Then $t$ is coprime with $c$, $a$ divides $t-1$ but $b$ does not divide $t-1$. This yields a necessary contradiction.

Let now $a>1$ be a divisor of $n$, choose $w\in \Theta(a)$ let $g(w)\in \Theta(b)$. If $a$ is odd and $b$ is an even divisor of $2a$, then $-g(w)\in \Theta(b/2)$. Thus in all cases of Lemma 1 we have $f(w)=\pm w^m$ for certain $m$. Then this equation $f(x)=\pm x^m$ holds for all $x\in \Theta(a)$, since cyclotomics are still irreducible.

We proceed with proving the consistency of signs $\delta_i$ and exponents $m_i$. Let's start with signs. Assume that $\delta_i=-\delta_j$ for some $i<j$. This yields that $x^{m_i}+x^{m_j}$ is divisible by $1+x+\ldots+x^{n/(p_ip_j)-1}$. Substituting $x=1$, we get that $2$ is divisible $n/(p_ip_j)$, that is, $n=p_ip_j$ or $n=2p_ip_j$. In the latter case, if $1<i<j$, then replacing the pair $i<j$ to $1<i$ or $1<j$ in the above argument, we get a contradiction. So, $n=p_ip_j$ or $n=4p_j$. These cases are to be considered separately.

Proof. Denote $c={\rm LCM}(a,b)$ and choose $\eta\in \Theta(c)$. Then we may find integers $k,\ell$ such that $w=\eta^k$, $g(w)=\eta^\ell$. So, the polynomial $P(x):=g(x^k)-x^\ell$ has a root $x=\eta$. Thus any element of $\Theta(c)$ is a root of $P$, since cyclotomics are irreducible. For any integer $t$ coprime to $c$ we have $\eta^t\in \Theta(c)$, so $g(w^t)-(g(w))^t=P(\eta^t)=0$. Try to choose $t$ such that $w=w^{t}$ but $g(w)^t\ne g(w)$, this would yield a contradiction. Our requirements for $t$ are, in other words: $a$ divides $t-1$; but $b$ does not divide $t-1$. Assume that $b$ does not divide $a$, and, if $a$ is odd, then $b$ does not divide $2a$. This allows to choose a prime $p$ such that $s:=\nu_p(b)$ (notation means that $p^s$ is the maximal power of $p$ which divides $b$) satisfies $s>\nu_p(a)$ and either $p$ is odd, or $p=2$ and $s\geqslant 2$. Using Chinese remainders theorem, choose $t$ be congruent to $1+p^{s-1}$ modulo $p^s$ and $t$ be congruent to 1 modulo $c/p^{s}$. Then $t$ is coprime with $c$, $a$ divides $t-1$ but $b$ does not divide $t-1$. This yields a necessary contradiction.

Let now $a>1$ be a divisor of $n$, choose $w\in \Theta(a)$. Let $g(w)\in \Theta(b)$. If $a$ is odd and $b$ is an even divisor of $2a$, then $-g(w)\in \Theta(b/2)$. Thus in all cases of Lemma 1 we have $f(w)=\pm w^m$ for certain $m$. Then this equation $f(x)=\pm x^m$ holds for all $x\in \Theta(a)$, since cyclotomics are still irreducible.

We proceed with proving the consistency of signs $\delta_i$ and exponents $m_i$. Let's start with signs. Assume that $\delta_i=-\delta_j$ for some $i<j$. This yields that $x^{m_i}+x^{m_j}$ is divisible by $1+x+\ldots+x^{n/(p_ip_j)-1}$. Substituting $x=1$, we get that $2$ is divisible $n/(p_ip_j)$, that is, $n=p_ip_j$ or $n=2p_ip_j$. In the latter case, if $1<i<j$, then replacing the pair $i<j$ to $1<i$ or $1<j$ in the above argument, we get a contradiction. So, $n=p_ip_j$ or $n=4p_j$. If $p_1=2$ and $n=2p_2$, then the signs may be chosen consistently because $-1=x$ on $T(2)$. The cases $n=pq$ with odd primes $p\ne q$ and $n=4p$ with odd prime $p$ are to be considered separately, this is done at the end of this answer.

added 1609 characters in body
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

Finally, the cases of not consistent signs with $n=4p$ and $n=pq$. Well, they are similar to the above analysis.

If $n=pq$ with distinct odd primes $p$, $q$, and $f(x)=x^a$ on $\Theta(p)$, $f(x)=-x^b$ on $\Theta(q)$, $f(x)=x^c$ on $\Theta(pq)$, then replacing $f$ to $f^n$ we may suppose that $f$ equals 1 on $\Theta(p)$ and $\Theta(pq)$ and $f=-1$ on $\Theta(q)$. Thus $$ 1-f(x)=\frac2{pq}\left(\sum_{\xi\in \Theta(q)} \xi\cdot \frac{x^n-1}{x-\xi}+(1+x+\ldots+x^{n-1})\right) $$ and $1-f(0)=2/p$, a contradiction.

Finally, if $n=4p$, $f(x)=x^a$ on $T(2p)=\Theta(2)\sqcup \Theta(p)$, $f(x)=-x^b$ on $T(4)=\Theta(4)\sqcup \Theta(2)$, $f(x)=x^c$ on $\theta(4p)$ (tofor $\Theta(4p)$ the sign may be finishedchosen as we wish by the already used "$-1=x^{2p}$ on $\Theta(4p)$" trick). As before, we may suppose that $a=0$ and that $c$ is divisible by $p$ (otherwise replace $f$ to $(f/x^a)^p$). Also, $b$ is odd since $1=f(-1)=(-1)^{b+1}$. Next point is that $c$ must be even. Assume that, on the contrary, $c$ is odd multiple of $p$. Choose $w\in \Theta(4p)$, then $-w\in \Theta(2p)$ and $\rho:=\frac{f(w)-f(-w)}{w-(-w)}$ must be an algebraic integer. We have $f(-w)=1$ and $f(w)=\pm i$, thus $w\rho=(-1\pm i)/2$ is an algebraic integer, but it is not. So, $c$ is divisible by $2p$. Then the polynomial $g(x):=x^{c}-f(x)$ equals 0 on $T(2p)\sqcup \Theta(4p)$, and takes values $\pm 1\pm i$ at two elements of $\Theta(4)$. Therefore (reducing as usually $g$ modulo $1+x+\ldots+x^{n-1}$) we get $$ g(x)=\frac1{4p}\left(\sum_{\xi\in \Theta(4)} g(\xi)\cdot \xi\cdot \frac{x^{4p}-1}{x-\xi}-\sum_{\xi\in \Theta(4)}\xi g(\xi)(1+x+\ldots+x^{4p-1})\right). $$ This does not have integer coefficients simply because the coefficients are too small.

Finally, the cases of not consistent signs with $n=4p$ and $n=pq$. Well, they are similar to the above analysis. (to be finished)

Finally, the cases of not consistent signs with $n=4p$ and $n=pq$. Well, they are similar to the above analysis.

If $n=pq$ with distinct odd primes $p$, $q$, and $f(x)=x^a$ on $\Theta(p)$, $f(x)=-x^b$ on $\Theta(q)$, $f(x)=x^c$ on $\Theta(pq)$, then replacing $f$ to $f^n$ we may suppose that $f$ equals 1 on $\Theta(p)$ and $\Theta(pq)$ and $f=-1$ on $\Theta(q)$. Thus $$ 1-f(x)=\frac2{pq}\left(\sum_{\xi\in \Theta(q)} \xi\cdot \frac{x^n-1}{x-\xi}+(1+x+\ldots+x^{n-1})\right) $$ and $1-f(0)=2/p$, a contradiction.

Finally, if $n=4p$, $f(x)=x^a$ on $T(2p)=\Theta(2)\sqcup \Theta(p)$, $f(x)=-x^b$ on $T(4)=\Theta(4)\sqcup \Theta(2)$, $f(x)=x^c$ on $\theta(4p)$ (for $\Theta(4p)$ the sign may be chosen as we wish by the already used "$-1=x^{2p}$ on $\Theta(4p)$" trick). As before, we may suppose that $a=0$ and that $c$ is divisible by $p$ (otherwise replace $f$ to $(f/x^a)^p$). Also, $b$ is odd since $1=f(-1)=(-1)^{b+1}$. Next point is that $c$ must be even. Assume that, on the contrary, $c$ is odd multiple of $p$. Choose $w\in \Theta(4p)$, then $-w\in \Theta(2p)$ and $\rho:=\frac{f(w)-f(-w)}{w-(-w)}$ must be an algebraic integer. We have $f(-w)=1$ and $f(w)=\pm i$, thus $w\rho=(-1\pm i)/2$ is an algebraic integer, but it is not. So, $c$ is divisible by $2p$. Then the polynomial $g(x):=x^{c}-f(x)$ equals 0 on $T(2p)\sqcup \Theta(4p)$, and takes values $\pm 1\pm i$ at two elements of $\Theta(4)$. Therefore (reducing as usually $g$ modulo $1+x+\ldots+x^{n-1}$) we get $$ g(x)=\frac1{4p}\left(\sum_{\xi\in \Theta(4)} g(\xi)\cdot \xi\cdot \frac{x^{4p}-1}{x-\xi}-\sum_{\xi\in \Theta(4)}\xi g(\xi)(1+x+\ldots+x^{4p-1})\right). $$ This does not have integer coefficients simply because the coefficients are too small.

added 1810 characters in body
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

I think, they are all of them. Let me be more concrete and accurate than in the initial answer. But this also makes the answer sometimes boring. Shortcuts are welcome.

In the case 2), we get $$1-f(0)=\frac{1}n\left(\varphi(n)+\frac{\varphi(n)}{p-1}-\mu(n)+\sum \xi^{n/p+1}\right).$$ Since ${\rm GCD}(n/p+1,n)$ is either 1 or $p$, the sum $\sum \xi^{n/p+1}$ equals either to $\mu(n)$, or to $(p-1)\mu(n/p)$. In the first case
$$ \varphi(n)+\frac{\varphi(n)}{p-1}-\mu(n)+\sum \xi^{n/p+1}= \frac{p}{p-1}\varphi(n)=n\prod_{q\, \text{is prime},q\ne p,q|n}(1-1/q) $$ which clearly is not divisible by $n$ (recall that $n$ is not a prime power, so the product over $q$ is strictly smaller than 1). In the second case, since $\mu(n)+\mu(n/p)=0$, we need $$n\prod_{q\, \text{is prime},q\ne p,q|n}(1-1/q)+p\mu(n/p)$$ to be divisible by $n$. This is the case only if $n=2p$ (otherwise it is too small). But $p$ divides $n/p+1=3$, so $p=3$, $n=6$. In this case the coefficient of $x^4$ in $1-f(x)$ is not an integer.

In the case 3), the number $p^{\alpha-2}+1$ is coprime to $n=p^\alpha$, thus $\sum \xi(1-f(\xi))=0$. We have $\sum \xi^j=0$ for $j$ not divisible by $p^{\alpha-1}$, but if $\nu_p(j)=\alpha-1$ then $\sum \xi^j=-p^{\alpha-1}$. Thus, between the coefficients of $1-f(x)$ we may find $\pm\frac1n\cdot p^{\alpha-1}=\pm 1/p$, a contradiction.

Finally, the cases of not consistent signs with $n=4p$ and $n=pq$. Well, they are similar to the above analysis. (to be finished)

I think, they are all of them.

In the case 2), we get $$1-f(0)=\frac{1}n\left(\varphi(n)+\frac{\varphi(n)}{p-1}-\mu(n)+\sum \xi^{n/p+1}\right).$$ Since ${\rm GCD}(n/p+1,n)$ is either 1 or $p$, the sum $\sum \xi^{n/p+1}$ equals either to $\mu(n)$, or to $(p-1)\mu(n/p)$. In the first case
$$ \varphi(n)+\frac{\varphi(n)}{p-1}-\mu(n)+\sum \xi^{n/p+1}= \frac{p}{p-1}\varphi(n)=n\prod_{q\, \text{is prime},q\ne p,q|n}(1-1/q) $$ which clearly is not divisible by $n$ (recall that $n$ is not a prime power, so the product over $q$ is strictly smaller than 1)

I think, they are all of them. Let me be more concrete and accurate than in the initial answer. But this also makes the answer sometimes boring. Shortcuts are welcome.

In the case 2), we get $$1-f(0)=\frac{1}n\left(\varphi(n)+\frac{\varphi(n)}{p-1}-\mu(n)+\sum \xi^{n/p+1}\right).$$ Since ${\rm GCD}(n/p+1,n)$ is either 1 or $p$, the sum $\sum \xi^{n/p+1}$ equals either to $\mu(n)$, or to $(p-1)\mu(n/p)$. In the first case
$$ \varphi(n)+\frac{\varphi(n)}{p-1}-\mu(n)+\sum \xi^{n/p+1}= \frac{p}{p-1}\varphi(n)=n\prod_{q\, \text{is prime},q\ne p,q|n}(1-1/q) $$ which clearly is not divisible by $n$ (recall that $n$ is not a prime power, so the product over $q$ is strictly smaller than 1). In the second case, since $\mu(n)+\mu(n/p)=0$, we need $$n\prod_{q\, \text{is prime},q\ne p,q|n}(1-1/q)+p\mu(n/p)$$ to be divisible by $n$. This is the case only if $n=2p$ (otherwise it is too small). But $p$ divides $n/p+1=3$, so $p=3$, $n=6$. In this case the coefficient of $x^4$ in $1-f(x)$ is not an integer.

In the case 3), the number $p^{\alpha-2}+1$ is coprime to $n=p^\alpha$, thus $\sum \xi(1-f(\xi))=0$. We have $\sum \xi^j=0$ for $j$ not divisible by $p^{\alpha-1}$, but if $\nu_p(j)=\alpha-1$ then $\sum \xi^j=-p^{\alpha-1}$. Thus, between the coefficients of $1-f(x)$ we may find $\pm\frac1n\cdot p^{\alpha-1}=\pm 1/p$, a contradiction.

Finally, the cases of not consistent signs with $n=4p$ and $n=pq$. Well, they are similar to the above analysis. (to be finished)

added 1810 characters in body
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459
Loading
added 45 characters in body
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459
Loading
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459
Loading