## Waist on a torus

Last year I worked on a interesting problem which asks about the possibility of partitioning a convex set in a plane in to ${n}$ internally disjoint convex pieces of equal area and perimeter. The problem has since been proved when ${n}$ is a prime power, by Aronov and Hubard and Roman Karasev for all dimensions. Here in this post I discuss a crucial lemma i worked while attempting to prove the n is a “power of two” case. In the simplest case, the lemma goes like this: given a continuous function ${f:(S^{1})^{2} \rightarrow \mathrm{I\!R}}$ which has the ${y}$-antipodal property: ${f(x,-y) = -f(x,y)}$, there is a pair of separators of a torus along its “waist” that map to zero under ${f}$. More specifically, there is a subset ${\Lambda}$ of the zero set of ${f}$ which is such that the projection map ${p_1(x,y) = x}$ restricted to ${\Lambda}$ is not null homotopic. For larger powers of ${2}$, the notation gets a little unwieldy but the proof scales up well. Lets tackle notation first:

Label the coordinates of ${(S^1)^{2^n}}$ in a binary system, with words using the letters ${0}$, ${1}$ and ${2}$. The words that can be formed using these letters can be treated as vertices in a binary tree, with the word ${0}$ as the root node. The root node has a unique child vertex as the word ${1}$. Other vertices consist of words ${w}$ in letters ${\{1,2\}}$ ( of length ${) each having child nodes ${w1}$ and ${w2}$. For example, the binary tree for ${n=3}$ would have vertices as below:

If we impose the dictionary ordering on such words, ${0 < 1 < 2 < 11 < 12 < 21 < 22 < 111 < 222 \ldots, 12\ldots2}$, then each word of length ${l \le n}$ uniquely identifies a coordinate in ${(S^1)^{2^n}}$. For example, a point ${x}$ in ${S^{8}}$ can be written as ${(x_0,x_1,x_{11},x_{12},x_{111},x_{112},x_{121},x_{122})}$.

Let ${W}$ be the set of words representing indices to coordinates of points in ${(S^1)^{2^n}}$ that have letters in 0,1 and 2, with 0 appearing only as the starting letter and are of length not more than ${n}$. For each word ${w \in W}$ of length ${k\le n}$ we define ${p_{w}:(S^1)^{2^n} \rightarrow S}$ to be the projection map: ${p_{w}(x_0,x_1,\ldots,x_{w},\ldots) = x_{w}}$. Given ${w\in W}$, we define a map ${\omega_{w}: (S^1)^{2^n} \rightarrow (S^1)^{2^n}}$ as follows:

$\displaystyle p_{w1w'}(\omega_{w}(x)) = x_{w2w'}, \text{ for all words} \quad w1w' \in W$

$\displaystyle p_{w2w'}(\omega_{w}(x)) = x_{w1w'}, \text{ for all words} \quad w2w' \in W$

$\displaystyle p_w(\omega_w(x)) = -x_w$

and for every other word ${v \in W}$, ${p_v( \omega_w(x)) = x_v}$.

For instance, for ${x \in S^{8}}$ and ${w = 1}$, we have,

$\displaystyle \omega_{1}(x) = \omega_{1}(x_0,x_1,x_{11},x_{12},x_{111},x_{112},x_{121},x_{122}) = (x_0,-x_1,x_{12},x_{11},x_{121},x_{122},x_{111},x_{112})$

Thus, ${\omega_{w}}$ changes the sign of the coordinate with index ${w}$ and swaps coordinates with indexes ${w1v}$ with ${w2v}$, leaving all the other coordinates fixed. If ${w_k}$ represents a subword of ${w}$ consisting of first ${k}$ letters from ${w}$, then using the definition of ${\omega_k}$, we note in particular, that ${p_{w_k}( \omega_w(x)) = x_{w_k}}$. Finally let ${\text{len}: W \rightarrow \mathrm{I\!N}}$ to be the map that gives the length of a word ${w}$ in ${W}$.

Definition 1 (${w}$-antipodal map) For ${w \in W}$, we say that a map ${P:(S^1)^{2^n} \rightarrow \mathrm{I\!R}^{2^n-1}}$ is ${w}$-antipodal, if,

$\displaystyle {\tilde p_w}(P(\omega_{w}(x))) = -{\tilde p_w}(P(x))$

.

Theorem 2 Let ${{f}: (S^1)^{2^n} \rightarrow \mathrm{I\!R}^{2^n-1}}$ be a continuous map with the ${w}$-antipodal property for each word ${w \in W}$. Suppose there exists ${\mathbf{c} \in (S^1)^{2^n}}$ such that ${f(\mathbf{c}) = \mathbf{0}}$. Then the zero set of ${f}$ contains a connected subset ${\Lambda}$ which can be approximated arbitrarily closely in the Hausdorff distance by a smooth loop ${L}$, for which the projection map: ${p_0 : L \rightarrow S^1}$, ${p_0(y_0,y_1,\ldots) = y_0}$ is not null-homotopic.

The second lemma is a Borsuk Ulam type theorem which has a cleaner and simpler proof:

Lemma 2 Let ${P}$ be a real valued function defined on the connected closed subset ${\Lambda}$ on the torus ${(S^1)^{k}}$ such that projection ${p_1:S^1 \times (S^1)^{k-1} \rightarrow S^1}$ defined by ${p_1(x,\mathbf{y}) = x}$ is not null-homotopic. Then there exists two points ${(x,\mathbf{y_1})}$ and ${(-x,\mathbf{y_2})}$ in ${\Lambda}$ such that ${P(x,\mathbf{y_1}) = P(-x,\mathbf{y_2})}$.

Lets tackle this in a more natural setting shall we? which is a pdf document rather than html. Here it is.

Categories: Uncategorized

## q-binomials

The binomial like coefficients that we saw in earlier posts:

$\displaystyle C_r^n(y) = \prod_{i=1}^r \frac{(y^{n-i+1}-1)}{y^i-1}$

are called ${q}$-binomial coefficients. In keeping with the existing convention we will use ${q}$ as the indeterminate instead of ${y}$ and write ${\binom{n}{r}_q}$ for ${C_r^n(q)}$

It was established in an earlier post that:

$\displaystyle \prod_{i=1}^n(y^i-1) = \prod_{i=1}^n\Phi_i(y)^{\lfloor {n/i} \rfloor}$

Using this identity we may reduce the ${q}$-binomial coefficient to:

$\displaystyle \binom{n}{r}_q = \prod_{i=2}^n \Phi_i(q)^{\lfloor n/i \rfloor - \lfloor r/i \rfloor - \lfloor (n-r)/i \rfloor } \ \ \ \ \ (1)$

We also made use of the identity:

$\displaystyle \prod_{i=0}^n(t-q^i) = \sum_{j=0}^n \binom{n}{j}_q t^{n-j+1} q^{j(j+1)/2} (-1)^j \ \ \ \ \ (2)$

If we put ${t=-1}$ in the above equation, we get

$\displaystyle \prod_{i=0}^n (1+q^i) = \sum_{j=0}^n \binom{n}{j}_q q^{j(j+1)/2}$

We now discuss a few consequences of the above identities:

1. For any natural number ${n}$, and ${ 0 < r < n}$, ${\binom{n}{r}_q}$ is divisible by ${\Phi_n(q)}$. For the special case where ${n}$ is a prime, ${\binom{n}{r}_q}$ is divisible by ${(q^n-1)/(q-1)}$ ( for which we will use the shorter notation ${[n]_q}$ as in wikipedia). Consequently we have,

$\displaystyle \prod_{i=1}^n (1+q^i) -1 -q^{n (n+1)/2} = \sum_{r=1}^{n-1} \binom{n}{r}_q q^{r(r+1)/2} = 0 \mod [n]_q$

For odd primes ${n=p}$, ${q^{p(p+1)/2} = 1}$ modulo ${[p]_q}$. Thus,

$\displaystyle \prod_{i=1}^{p} (1+q^i) = 2 \mod [p]_q$

Also, observe that last term in the above product : ${(1+q^p)}$, reduces to ${2}$ modulo ${[p]_q}$. So we may further simplify the above identity to,

$\displaystyle \ \prod_{i=1}^{p-1} (1+q^i) = 1 \mod [p]_q$

We emphasize again that this is true only for odd primes ${p}$.

2. The exponents in the identity (1)

$\displaystyle e(n,r,d) = {\lfloor n/d \rfloor - \lfloor r/d \rfloor - \lfloor (n-r)/d \rfloor }$

are all either ${1}$ or ${0}$ , according as the the remainder when ${d}$ divides ${r}$ is greater or smaller than remainder when ${d}$ divides ${n}$. In particular, since ${d |n \Leftrightarrow e(n,d+1,d) = 1}$, it follows that,

$\displaystyle \Phi_{d}(q) | \binom{n}{d+1}_q \Leftrightarrow \quad d|n$

Stated differently, this means that

$\displaystyle \Phi_d(q) | \binom{n}{r}_q \text{whenever} \quad d | \text{gcd}(n,r-1)$

Using the above result, a primality condition can be given, similar to the ones involving standard binomial coefficients can be given in terms of ${q}$-binomials as well. A number ${n}$ is prime if and only if:

$\displaystyle \binom{n}{d}_q = 0 \mod [n]_q \quad \text{for all d, s.t} \quad 0

Categories: Uncategorized

## ponder problem now on last legs

This post culminates our efforts in solving the problem:

If ${x,y}$ are positive integers with ${y>1}$ and satisfying the following ${x^n-1}$ is divisible by ${y^n-1}$ for all positive integers ${n}$, then ${x}$ is a power of ${y}$.

First recap a few facts from this post: We began by showing that:

$\displaystyle p(n) = (x-y)\cdot (x-y^2) \cdots (x-y^n)$

is divisible by ${(y^r-1)^{\lfloor n/r \rfloor}}$ for all ${r \leq n}$ and therefore by the lcm,

$\displaystyle l(n) = \text{lcm} ( (y-1)^n, (y^2-1)^{ \lfloor n/2 \rfloor } , \ldots, (y^r-1)^{\lfloor n / r \rfloor }, \ldots , (y^n-1) )$

We however wanted a stronger divisibility condition that ${p(n)}$ should be divisible by,

$\displaystyle q(n) = \prod_{i=1}^n(y^i-1)$

For then, the sequence,

$\displaystyle p(n)/q(n), \text{ for } n = 1,2,\ldots$

consists of integers only, and if we let ${g = (x,y)}$, this will in turn show that the sequence ${\frac{p(n)}{g^n \cdot q(n)}}$ also consists of integers only. But as, ${\frac{p(n)}{g^n \cdot q(n) }}$ converges to ${0}$ as ${n \rightarrow \infty}$, this will prove that for large enough integer ${r}$, ${p(r)}$ vanishes, showing that ${x=y^r}$. For the skeptics amongst us, here is a quick proof of the fact that ${\frac{p(n)}{ g^n q(n)} \rightarrow 0}$ as ${n \rightarrow \infty}$. We recall from our analysis courses that the product of

$\displaystyle \prod_{i=1}^n(1 - (x-1)/(y^i-1))$

converges absolutely iff ${\sum_{i=1} (x-1)/(y^i-1)}$ converges absolutely, provided ${1> (x-1)/(y^i-1)}$ for all large i. Now the result that ${\frac{p(n)}{g^n \cdot q(n)} \rightarrow 0}$ as ${n \rightarrow \infty}$ follows by verifying these facts and the fact that ${1/g^n \rightarrow 0}$.

So to wind up the proof, we need to show that ${q(n) | p(n)}$. Since we know that ${l(n) | p(n)}$ we will show that ${q(n) | p(n)}$, by proving that each prime power dividing ${q(n)/l(n)}$ also divides ${p(n)}$

The last post allowed us to write ${l(n)}$ and ${q(n)}$ in terms of cyclotomic polynomials:

$\displaystyle l(n) = \text{lcm}( \Phi_1(y)^n , \Phi_2(y)^{\lfloor n/2 \rfloor} , \ldots , \Phi_n(y) )$

and

$\displaystyle q(n) = \prod_{r=1}^n {\Phi_r(y)^{\lfloor n/r \rfloor}}$

In an earlier post we also showed that for distinct integers ${1\leq i, ${\text{gcd} (\Phi_i(y), \Phi_j(y))}$ is a prime number ${p}$ or ${1}$. If not ${1}$, it is the prime ${p}$ only if ${j=p^s\cdot i}$ for some ${s\ge 0}$. Also if ${p |\Phi_{ip^m}(y)}$ then using the formula,

$\displaystyle \Phi_{ip^m}(y) = \Phi_{ip}(y^{p^{m-1}})$

and going modulo ${p}$, we get

$\displaystyle 0 = \Phi_{ip^m}(y) \mod p = \Phi_{ip}(y^{p^{m-1}}) \mod p = \Phi_{ip}(y) \mod p$

Let ${p}$ be a prime such that ${p |\Phi_{i}(y)}$ and ${p {\not |} \Phi_j{y}}$ for positive integers ${j < i}$. The highest power of ${p}$ in the product,

$\displaystyle q(n) = \prod_{j=1}^n\Phi_j(y)^{ \lfloor n/j \rfloor}$

is,

$\displaystyle p^{s\lfloor n/i \rfloor + \lfloor n/ip \rfloor + \lfloor n/{ip^2} \rfloor + \ldots \lfloor n/{ip^m} \rfloor } \ \ \ \ \ (1)$

where ${s}$ is the highest power on ${p}$ dividing ${\Phi_i(y)}$ and ${m}$ is the largest integer (${\leq n}$) such that ${(\Phi_{ip^m}(y),\Phi_i(y) ) = p}$. The number ${m}$ is bounded by the integer ${m'}$ satisfying ${n/p \le ip^{m'} \le n}$.

On the other hand, the highest power of the prime ${p}$ dividing ${l(n)}$ is ${p^{s \lfloor n/i \rfloor}}$. To show that ${q(n) | p(n)}$ it is enough to show that for each such ${p}$, the highest prime power of ${p}$ in ${l(n)/q(n)}$

$\displaystyle p^{ \lfloor n/i \rfloor + \lfloor n/ip \rfloor + \lfloor n/{ip^2} \rfloor + \ldots \lfloor n/{ip^m} \rfloor }$

also divides ${p(n)}$.

From our first post on the problem, if ${p | \Phi_{i}(y)}$ then ${p |\prod_{j=1}^{i} (x-y^j))}$. If ${i}$ is the smallest integer for which ${p | \Phi_i(y)}$, there exists a unique ${a_1}$ in ${\{1\ldots i\}}$, such that ${x=y^{a_1} \mod p}$. In fact, if ${s}$ is largest integer such that ${p^{s} | \Phi_i(y)}$, then ${x = y^{a_1} \mod p^{s}}$ by the minimality of ${i}$. Now consider the numbers,

$\displaystyle r(k) = \frac{(x-y^{a_1 +ki} )}{p^{s}}$

where ${k}$ is an integer such that ${n \ge a_1 + ki \ge 0}$. It is clear that the numbers ${r(k)}$ are integers. Taking any ${p}$ consecutive integer values of ${k}$, we get ${p}$ distinct numbers ${r(k)}$ no two of which are same modulo ${p}$, for otherwise, ${p^s}$ would not be the largest prime power dividing ${y^i-1}$. Thus, there is ${a_2}$ such that ${p |r(a_2)}$. There are ${\lfloor n/i \rfloor}$ disjoint groups of consecutive terms of size ${i}$, in the product ${\prod_{i=1}^n(x-y^i)}$ each giving us an additional factor of ${p^{ \lfloor n/i \rfloor }}$ in the product. Likewise, if we consider numbers ${(x-y^{a_1+a_2i+lip})/p^{s+1}}$ where ${l}$ is any integer for which ${n \ge a_1+a_2i + lip \ge 0}$, repeating the arguments in the previous paragraph, for every ${p}$ consecutive values of ${l}$, there exists ${l}$ such that ${(x-y^{a_1+a_2i+lip })/p^{h+1}}$ is a multiple of ${p}$. Since there are ${\lfloor n/ip \rfloor}$ groups of consecutive terms of size ${ip}$ in the product ${p(n)}$, giving us ${ p^{ \lfloor n/(ip ) \rfloor }}$ additional prime powers in ${p(n) = \prod_{j=1}^n(x-y^j )}$. We can continue this process until we get all the additional prime powers

$\displaystyle p^{\lfloor n/i \rfloor + \lfloor n/(ip ) \rfloor +\ldots + \lfloor n/(ip^m )\rfloor} )$

in ${p(n)}$, where ${m}$ is such that ${n/p \le ip^m \le n}$. This prime power is clearly divisible by the prime power of ${p}$ in ${q(n)/l(n)}$ in (1).

Categories: number theory

## another nugget concerning cyclotomic polynomials

April 26, 2011 1 comment

In our build up to a proof of this problem., we established that the product

$\displaystyle p(n) = \prod_{i=1}^n(x-y^i)$

is a multiple of each of the numbers ${(y^i-1)^{\lfloor n/i \rfloor }}$ for ${1\leq i \leq n}$. But we wished to show the stronger result that ${p(n)}$ is divisible by ${q(n) = \prod_{i=1}^n(y^i-1)}$. One way to proceed to estimate how the lcm,

$\displaystyle l(n) = \text{lcm}\{(y-1)^n, (y^2-1)^{\lfloor n/2 \rfloor}, \ldots, (y^r-1)^{\lfloor n/r \rfloor} , \ldots, (y^n-1) \}$

differs from the product ${q(n) = \prod_{i=1}^n(y^i-1)}$ and see if ${ l(n)/q(n)}$ also divides ${p(n)}$. We take the cyclotomic route, using the identity,

$\displaystyle y^n-1 = \prod_{d|n} \Phi_d(y)$

to rewrite ${l(n)}$ as,

$\displaystyle l(n) = \text{lcm} \{ \Phi_1(y)^n, \ldots, \Phi_{r}(y)^{\lfloor n /r \rfloor} , \ldots, \Phi_n(y)\}$

We also write $q(n)$ using cyclotomic polynomials as,

$\displaystyle \prod_{i=1}^n(y^i-1) = \prod_{r=1}^n {\Phi_r(y)^{\lfloor n /r \rfloor}}$

To see this, we write,

$\displaystyle \Phi_r(y) = \prod_{d|r}(y^d-1)^{\mu(r/d)}$

where ${\mu}$ is the Mobius function. Then the power on ${(y^d-1)}$ in the product,

$\displaystyle \prod_{r=1}^n (\prod_{d|r} (y^d-1)^{\mu(r/d)}) ^ { \lfloor n/r \rfloor}$

is

$\displaystyle \sum_{r,d|r}^n \mu(r/d) {\lfloor n/r \rfloor } = \sum_{1\leq i \leq n}^{n/d} \mu(i) {\lfloor {n/id} \rfloor}$

The later sum is of the form

$\displaystyle \sum_{1 \le i \le x} \mu(i) G(x/i)$

with ${x = n/d}$ and ${G(x) = \lfloor x \rfloor = \sum_{1\leq i \leq x} 1}$ , reminding us, that we can use the Mobius inversion formula to obtain,

$\displaystyle \sum_{1\leq i \leq n/d}^n \mu(i) {\lfloor { n/id} \rfloor} = 1$

Thus,

$\displaystyle \prod_{r=1}^n\Phi_{r}(y)^{\lfloor n/r \rfloor} = \prod_{r=1}^n (y^r-1) = q(n)$

Our next task is to estimate ${q(n)/l(n)}$ which we will do in the next post.

## a result concerning cyclotomic polynomials

April 24, 2011 1 comment

In this post we record a useful result concerning cyclotomic polynomials. This will help us prove what is claimed in this post.

Theorem: For distinct positive integers ${i,j}$ the GCD of the values of cyclotomic polynomials ${\Phi_i(y)}$ and ${\Phi_j(y)}$ , is ${p}$ only if ${j = i \cdot p^k}$ for some integer ${k \ge 1}$. On the other hand, if ${j = i \cdot p^k}$ for some ${k \ge 1}$, ${(\Phi_i(y) , \Phi_j(y)) = p \text{ or } 1}$.

Proof: (${\Leftarrow}$) We show that ${j = i \cdot p^k}$ for some ${k \ge 1}$ if ${p | (\Phi_j(y), \Phi_i(y))}$. We will start by proving that the gcd ${g=(i,j)=i}$. Then show that $j/i$ is a prime power. Let ${g = (i,j)}$ and assume to the contrary that ${g < i}$. The cyclotomic polynomials ${\Phi_i(y)}$ and ${\Phi_j(y)}$ divide ${\frac{(y^j-1)}{(y^g-1)}}$ and ${\frac{(y^i-1)}{(y^g-1)}}$ resp. But, ${\frac{(y^i-1)}{(y^g-1)}}$ and ${\frac{(y^j-1)}{(y^g-1)}}$ are relatively prime (easy exercise), and so their divisors ${\Phi_i(y)}$ and ${\Phi_j(y)}$ are also relatively prime. This shows that if for ${1 \le i < j}$, the values of cyclotomic polynomials ${\Phi_i(y)}$ and ${\Phi_j(y)}$ have a factor in common then ${\text{gcd}(i,j) = i}$.

Now suppose ${j= m \cdot i}$ and that, a prime ${p}$, divides the values of cyclotomic polynomials ${\Phi_i(y)}$ and ${\Phi_j(y)}$. But ${\Phi_j(y)}$ divides

$\displaystyle \frac{ (y^j-1)}{(y^i-1)}=1+y^i+ \ldots + y^{i(m-1)},$

and so ${p}$ also divides it. Going modulo ${p}$, we see that ${(y^j-1)/(y^i-1) \mod p=m}$. This proves that ${m}$ is a multiple of ${p}$. Next we show that ${m}$ is a power of ${p}$.

Let ${p^h}$ be the largest power of ${p}$ dividing ${i}$ and ${p^k}$ be the largest power of ${p}$ that divides ${j = i\cdot m}$. Now using Thm 1.1 of \cite{YVES}, we have,

$\displaystyle \Phi_{i}(y) | \Phi_{i/p^h}(y^{p^h}) \text{ and } \Phi_{im} (y) | \Phi_{im/p^k} (y^{p^k})$

Now, ${\Phi_{i/p^h}(y^{p^h}) \mod p = \Phi_{i/p^h} (y)}$ and ${\Phi_{im/p^k} (y^{p^k}) \mod p = \Phi_{im/p^k} (y)}$. Since ${p | \Phi_i(y)}$ and ${p | \Phi_j(y)}$, ${p}$ divides both ${ \Phi_{im/p^k}(y)}$ and ${ \Phi_{i/p^h}(y)}$. From the arguments in the first paragraph of this proof, this is possible only if ${im/p^k = i/p^h}$ or ${m = p^{k-h}}$. Hence ${j = i p^{k-h}}$.

(${\Rightarrow}$) Let ${j = i \cdot p^k}$ (${k>0}$). From the proof in the “only if” direction ${p}$ is the only prime that can possibly divide ${ (\Phi_i(y), \Phi_j(y))}$. To show that

$\displaystyle {(\Phi_i(y),\Phi_j(y) = p \text{ or } 1}$

it will be enough to show that

$\displaystyle {p | (\Phi_i(y) , \Phi_j(y)) } \Rightarrow {p^2 {\not |} \Phi_j(y)}$

First suppose ${p^k \neq 2}$. Since ${p | \Phi_i(y)}$, we must have, ${p | (y^i-1)}$ and so we may write ${y^i \mod p^2= 1 + ap \mod p^2}$, for some ${a \in \{0,\ldots, p-1\}}$. Also, as ${\Phi_j(y) | (y^{i p^k} -1 ) / (y^i-1)}$, it is enough to show that ${p^2 {\not |} (y^{i p^k} -1 ) / (y^i-1)}$ to show that ${p^2 {\not |} \Phi_j(y)}$. Consider,

$\displaystyle (y^{i p^k} -1 ) / (y^i-1) \mod p^2 = 1 + y^i + \ldots + y^{(p^k-1)i} \mod p^2$

$\displaystyle = p + ap + 2 ap + 3 ap + \ldots + (p^k-1) ap \mod p^2$

$\displaystyle = p + ap ( p^k ( p^k-1)/2 ) \mod p^2 = p \mod p^2$

Thus ${p^2 {\not |} (y^{i p^k} - 1) / (y^i-1)}$. If ${j = 2i}$ with ${p=2}$, and ${i}$ is an even number then ${\Phi_j(y) | (y^{2i}-1) / (y^i-1) = 1 + y^i \mod 4 \neq 0}$. If ${i}$ is odd then,

$\displaystyle \Phi_{2i} (y) = \Phi_i(-y) | (y^{i} + 1)/(y+1) = 1 - y + y^2 - \ldots + y^{i-1}$

. The last value modulo ${4}$ is an odd number and so is not a multiple of ${4}$. Hence in any case ${p^2 {\not |} (y^{j}-1)/(y^i-1)}$

This shows that ${p^2 {\not |}\Phi_j(y)}$ and that ${(\Phi_j(y),\Phi_i(y) ) = p \text{ or } 1}$.

{9} \bibitem{YVES} Y. Gallot, Cyclotomic polynomials and Prime Numbers, \url{http://perso.orange.fr/yves.gallot/papers/cyclotomic.pdf}

## an old ponder problem

It is well-known that if natural numbers ${x>1}$ and ${y>1}$ satisfy ${x = y^n}$, for some ${n>0}$, then ${(x^i-1)}$ is a multiple of ${ y^i-1}$ for all ${i>0}$,. April 2005 ponder asks whether the converse is true, that is if for integers ${ x>1,y>1}$, the number ${ x^i-1}$ is a multiple of ${ y^i-1}$ for all ${ i > 0}$, then ${x}$ a power of ${ y}$.

While trying to prove this I stumbled on this interesting polynomial identity:

$\displaystyle \prod_{i =1 }^n ( x - y^i) = \sum_{r=0}^n (-1)^{n-r}x^{r} y^{\frac{(n-r) (n-r+1)}{2}} C^n_{n-r}(y)$

where

$\displaystyle C^n_r(y) = \prod_{j=1}^r \frac{(y^{n-j+1}-1) }{y^j - 1}$

${C^n_r(y)}$ looks similar to the binomial coefficient ${C^n_r = \prod_{j=1}^r (n-j+1)/j}$. Importantly, ${C^n_r(y)}$ is an integer for integer values of ${y>1}$.

To use this identity for the problem at hand, we first note that setting ${x=y}$ causes LHS to vanish and so we may replace each of the terms ${x^r}$ in RHS by ${(x^r-y^r)}$ without changing the value of the expansion. But wait, ${(x^r-y^r)}$ is a multiple of ${y^r-1}$ for ${r>0}$ by hypothesis. We may pull out the denominator ${y^r-1}$ and the numerator ${y^n-1}$ in the RHS to rewrite this identity as:

$\displaystyle \prod_{i=1}^n ( x - y^i) = \sum_{r=1}^n {(-1)^{n-r}(x^r - y^r) \cdot \frac{(y^n-1)}{(y^r-1)} y^{\frac{(n-r) (n-r+1)}{2}} \prod_{j=1}^{r-1} \frac{(y^{n-j}-1 ) }{y^{j} - 1 }}$

It is now apparent that each of the terms in the summand in RHS is a multiple of ${ y^n - 1}$ and therefore product

$\displaystyle p(n) = \prod_{i=0}^n{(x-y^i )} \text{ is a multiple of } (y^n-1)$

In fact, one easily sees that,

$\displaystyle p(n) \text{ is a multiple of } (y^r-1)^{ \lfloor n/r \rfloor }$

for each ${r}$ in ${1\ldots n}$. If we up our optimism a bit, we are led to suspect that

$\displaystyle p(n) = \prod_{i=1}^n (x-y^i) \text{ is a multiple of } q(n) = \prod_{i=1}^n(1-y^i)$

Among the factors of ${p(n)}$ that are relatively prime to ${q(n)}$, one candidate is ${g^n}$ where ${g = \text{gcd}(x,y)}$. But is ${g>1}$?. We can squeeze out this easy fact from the hypothesis: Every prime ${p}$ that does not divide ${y}$ also does not divide ${x}$. For if ${p {\not |} y}$ then ${p | y^s-1}$ for some ${s\ge 1}$ and so ${p | x^s-1}$ and therefore ${p}$ cannot divide ${x}$. Stated differently, this says that every prime that divides ${x}$ also divides ${y}$. Given that both ${x,y}$ are greater than ${1}$, this means that ${\text{gcd}(x,y) = g>1}$.

It is still not clear whether ${q(n) | p(n)}$, but if we take this to be true how can we prove the ponder problem?. To see this, observe that

$\displaystyle r(n) = \frac{p(n)}{g^n q(n)}$

approaches zero as ${n \rightarrow \infty}$, so if we show that each of the terms in the sequence ${r(n)}$ is an integer, it would mean that the numerator ${p(n)}$ of ${r(n)}$ vanishes for some large ${n}$, proving that ${x = y^n}$ for some ${n\geq 1}$.

Given that ${g}$ and ${q(n)}$ are relatively prime, we just need to show that ${p(n)/q(n)}$ is an integer in order to show that ${r(n)}$ is an integer. Which is what we will proceed to do in the next few posts.

Categories: Uncategorized